Cooperative multihop broadcast for wireless networks

Ivana Maric, Roy D. Yates

Research output: Contribution to journalArticlepeer-review

152 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1080-1088
Number of pages9
JournalIEEE Journal on Selected Areas in Communications
Issue number6
StatePublished - Aug 2004

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Distributed algorithm
  • Minimum-energy broadcast
  • Reliable forwarding
  • Wideband regime


Dive into the research topics of 'Cooperative multihop broadcast for wireless networks'. Together they form a unique fingerprint.

Cite this