The minimum-energy broadcast problem: A case study in symmetric wireless ad hoc networks

Fredrick Mtenzi, Yingyu Wan

Research output: Contribution to journalArticlepeer-review


Minimizing energy consumption in communication is a crucial problem in wireless ad hoc networks, as in most cases the nodes are powered by battery only. The minimum-energy broadcast problem is studied in this paper, for which it is well known that the broadcast nature of the radio transmission can be exploited to optimize energy consumption. This problem has been studied in a lot of literature on different models. In this paper a symmetric network is considered. First we propose an approximation algorithm, which takes O(mnα(m,n)) time, where m is the number of links, n is the number of nodes and α is the inverse of Ackerman's function. The algorithm delivers a broadcast tree with energy consumption being at most 2Hn-1 times of the optimal solution, where Hn-1 is the (n-1)st harmonic number. Since it has been proved that the minimum energy broadcast problem in general graph case (including symmetric case) cannot be approximated within a sub-logarithmic factor (unless P=NP), so the algorithm is almost optimal. For a special case where each node is equipped with the same type of battery it improves the known O(log3 n)-approximation algorithm. Moreover for some asymmetric but nearly symmetric network, the algorithm can also be applied with O(In n) performance guarantee. Finally a special case is studied, where the degree of network is bounded by a constant Δ and the ratio of the maximum transmission energy to the minimum transmission energy is bounded by another constant C. For the case we devise a 2(C + HΔ-1)-approximation algorithm.

Original languageEnglish
Pages (from-to)795-803
Number of pages9
JournalWSEAS Transactions on Computers
Issue number5
Publication statusPublished - May 2006
Externally publishedYes


  • Ad hoc network
  • Approximation algorithm
  • Broadcast
  • Energy efficient
  • Wireless network


Dive into the research topics of 'The minimum-energy broadcast problem: A case study in symmetric wireless ad hoc networks'. Together they form a unique fingerprint.

Cite this