Broadcast is a fundamental network operation, widely used in wireless networks to disseminate messages. The energy-efficiency of broadcast is important particularly when devices in the network are energy constrained. To improve the efficiency of broadcast, different approaches have been taken in the literature. One of these approaches is broadcast with energy accumulation. Through simulations, it has been shown in the literature that broadcast with energy accumulation can result in energy saving. The amount of this saving, however, has only been analyzed for linear multi-hop wireless networks. In this work, we extend this analysis to two-dimensional (2D) multi-hop networks. The analysis of saving in 2D networks is much more challenging than that in linear networks. It is because, unlike in linear networks, in 2D networks, finding minimum-energy broadcasts with or without energy accumulation are both NP-hard problems. Nevertheless, using a novel approach, we prove that this saving is constant when the path loss exponent alpha is strictly greater than two. Also, we prove that the saving is theta(log n) when alpha=2, where n denotes the number of nodes in the network.
We analyze the maximum gain that can be achieved through cooperative broadcast with energy accumulation and memory. We consider a linear network, where a known number of nodes are placed on a line, and derive an upper bound on @math , the gain of cooperative broadcast over noncooperative broadcast with respect to total power consumption. Specifically, we prove that, in linear networks with path loss exponent @math , @math , irrespective of the number of devices, the size of the network, the node placement strategy, and the cooperative broadcast strategy. We extend this result to any path loss exponent @math . We also show that the cooperation gain in short-range transmissions, wherein the circuit energy consumption is nonnegligible, is smaller than that in long-range transmissions. We further study the cooperative broadcast gain when the objective is to reduce the maximum transmission power used by any node in the network. In this case, we show that, when nodes are distributed uniformly at random, the maximum cooperation gain will be @math (log @math ), with high probability, where @math is the number of nodes in the network. These are important observations that should be considered in designing power-efficient broadcast algorithms in future network-wide cooperative broadcast. In all-wireless networks a crucial problem is to minimize energy consumption, as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. Several authors have conjectured that the problem of power-optimal broadcast is NP-complete. We provide here a formal proof, both for the general case and for the geometric one; in the former case, the network topology is represented by a generic graph with arbitrary weights, whereas in the latter a Euclidean distance is considered. We then describe a new heuristic, Embedded Wireless Multicast Advantage. We show that it compares well with other proposals and we explain how it can be distributed.