TY - JOUR

T1 - Cooperative multihop broadcast for wireless networks

AU - Maric, Ivana

AU - Yates, Roy D.

N1 - Funding Information:
Manuscript received July 15, 2003; revised February 1, 2004. This work was supported in part by the New Jersey Commission on Science and Technology and in part by the National Science Foundation (NSF) under Grant NSF ANI 0338805.

PY - 2004/8

Y1 - 2004/8

N2 - 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.

AB - 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.

KW - Distributed algorithm

KW - Minimum-energy broadcast

KW - Reliable forwarding

KW - Wideband regime

UR - http://www.scopus.com/inward/record.url?scp=4344599235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4344599235&partnerID=8YFLogxK

U2 - 10.1109/JSAC.2004.830912

DO - 10.1109/JSAC.2004.830912

M3 - Article

AN - SCOPUS:4344599235

SN - 0733-8716

VL - 22

SP - 1080

EP - 1088

JO - IEEE Journal on Selected Areas in Communications

JF - IEEE Journal on Selected Areas in Communications

IS - 6

ER -