Minimum-Energy Broadcasting in Multi-hop Wireless Networks Using a Single Broadcast Tree

In this paper we address the minimum-energy broadcast problem in multi-hop wireless networks, so that all broadcast requests initiated by different source nodes take place on the same broadcast tree. Our approach differs from the most commonly used one where the determination of the broadcast tree depends on the source node, thus resulting in different tree construction processes for different source nodes. Using a single broadcast tree simplifies considerably the tree maintenance problem and allows scaling to larger networks. We first show that, using the same broadcast tree, the total power consumed for broadcasting from a given source node is at most twice the total power consumed for broadcasting from any other source node. We next develop a polynomial-time approximation algorithm for the construction of a single broadcast tree. The performance analysis of the algorithm indicates that the total power consumed for broadcasting from any source node is within 2H(n−1) from the optimal, where n is the number of nodes in the network and H(n) is the harmonic function. This approximation ratio is close to the best achievable bound in polynomial time. We also provide a useful relation between the minimum-energy broadcast problem and the minimum spanning tree, which shows that a minimum spanning tree may be a good candidate in sparsely connected networks. The performance of our algorithm is also evaluated numerically with simulations. A preliminary version of this work appeared in the Proceedings of WiOpt’04: Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, University of Cambridge, UK, March 2004. Ioannis Papdimitriou was fully supported for this work by the Public Benefit Foundation “ALEXANDER S. ONASSIS”, Athens, Greece. Ioannis Papadimitriou was born in Veria, Greece, in 1976. He received his five year Diploma from the Department of Electronic and Computer Engineering, Technical University of Crete (Chania), Greece, in 1999 (graduating 2nd in class). He is currently a postgraduate student - Ph.D. candidate at the Telecommunications division, Department of Electrical and Computer Engineering, Aristotle University of Thessaloniki, Greece. His doctoral thesis deals with the design of wireless ad hoc networks. His research interests include broadcast and multicast communication, energy conservation, routing and topology control protocols, MAC layer and QoS issues. During his studies he has been honored with awards and scholarships by the Technical University of Crete, the Hellenic Telecommunications Organization S.A.(OTE S.A.) and Ericsson Hellas S.A. Mr. Papadimitriou has been a member of the Technical Chamber of Greece (TEE) since March 2000, and he has been supported by the Public Benefit Foundation ALEXANDER S. ONASSIS, Athens, Greece, with a scholarship for his doctoral studies from October 2001 to March 2005. Leonidas Georgiadis received the Diploma degree in electrical engineering from Aristotle University, Thessaloniki, Greece, in 1979, and his M.S. and Ph.D. degrees both in electrical engineering from the University of Connecticut, in 1981 and 1986, respectively. From 1981 to 1983 he was with the Greek army. From 1986 to 1987 he was Research Assistant Professor at the University of Virginia, Charlottesville. In 1987 he joined IBM T.J. Watson Research Center, Yorktown Heights, as a Research Staff Member. Since October 1995, he has been with the Telecommunications Department of Aristotle University, Thessaloniki, Greece. His interests are in the area of wireless networks, high speed networks, distributed systems, routing,scheduling, congestion control, modeling and performance analysis. Prof. Georgiadis is a senior member of IEEE Communications Society. In 1992 he received the IBM Outstanding Innovation Award for his work on goal-oriented workload management for multi-class systems.x