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.
The problem of cooperative broadcast with minimum energy can be broken into two sub-problems i) transmission scheduling, which determines the set of transmitters and the order of transmissions; ii) power allocation, in which the transmission powers are set. It was proven that, given a transmission scheduling, optimal power allocation can be computed in polynomial time, but finding an optimal scheduling that leads to a minimum power consumption is NP-hard @cite_0 @cite_5 .
@cite_0 @cite_5
2119940417 2136564093
Broadcasting is a method that allows the distributed nodes in a wireless sensor network to share its data efficiently among each other. Due to the limited energy supplies of a sensor node, energy efficiency has become a crucial issue in the design of broadcasting protocols. In this paper, we analyze the energy savings provided by a cooperative form of broadcast, called the opportunistic large arrays (OLA), and compare it to the performance of conventional multi-hop networks where no cooperation is utilized for transmission. The cooperation in OLA allows the receivers to utilize for detection the accumulation of signal energy provided by the transmitters that are relaying the same symbol. In this work, we derive the optimal energy allocation policy that minimizes the total energy cost of the OLA network subject to the SNR (or BER) requirements at all receivers. Even though the cooperative broadcast protocol provides significant energy savings, we prove that the optimum energy assignment for cooperative networks is an NP-complete problem and, thus, requires high computational complexity in general. We then introduce several suboptimal yet scalable solutions and show the significant energy-savings that one can obtain even with the approximate solutions We address the minimum-energy broadcast problem under the assumption that nodes beyond the nominal range of a transmitter can collect the energy of unreliably received overheard signals. As a message is forwarded through the network, a node will have multiple opportunities to reliably receive the message by collecting energy during each retransmission. We refer to this cooperative strategy as accumulative broadcast. We seek to employ accumulative broadcast in a large scale loosely synchronized, low-power network. Therefore, we focus on distributed network layer approaches for accumulative broadcast in which loosely synchronized nodes use only local information. To further simplify the system architecture, we assume that nodes forward only reliably decoded messages. Under these assumptions, we formulate the minimum-energy accumulative broadcast problem. We present a solution employing two subproblems. First, we identify the ordering in which nodes should transmit. Second, we determine the optimum power levels for that ordering. While the second subproblem can be solved by means of linear programming, the ordering subproblem is found to be NP-complete. We devise a heuristic algorithm to find a good ordering. Simulation results show the performance of the algorithm to be close to optimum and a significant improvement over the well known BIP algorithm for constructing energy-efficient broadcast trees. We then formulate a distributed version of the accumulative broadcast algorithm that uses only local information at the nodes and has performance close to its centralized counterpart.