Energy efficient broadcast routing in static ad hoc wireless networks
Authors:
- Xiaohua JiaXJXiaohua Jia
- Hai LiuHLHai Liu
- 19 July 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 3 (2) , 144-151
Abstract
In this paper, we discuss energy efficient broadcast in ad hoc wireless networks. The problem of our concern is: given an ad hoc wireless network, find a broadcast tree such that the energy cost of the broadcast tree is minimized. Each node in the network is assumed to have a fixed level of transmission power. We first prove that the problem is NP-hard and propose three heuristic algorithms, namely, shortest path tree heuristic, greedy heuristic, and node weighted Steiner tree-based heuristic, which are centralized algorithms. The approximation ratio of the node weighted Steiner tree-based heuristic is proven to be (1 + 2 ln(n - 1)). Extensive simulations have been conducted and the results have demonstrated the efficiency of the proposed algorithms.Keywords
This publication has 16 references indexed in Scilit:
- Energy-efficient broadcast and multicast routing in ad hoc wireless networks2003
- Energy-Efficient Broadcast and Multicast Trees in Wireless NetworksMobile Networks and Applications, 2002
- Distributed topology control for power efficient operation in multihop wireless ad hoc networks2002
- Minimum-energy broadcast routing in static ad hoc wireless networks2002
- Topology control of multihop wireless networks using transmit power adjustment2002
- Extended dominating-set-based routing in ad hoc wireless networks with unidirectional linksIEEE Transactions on Parallel and Distributed Systems, 2002
- On the construction of energy-efficient broadcast and multicast trees in wireless networks2002
- Algorithms for Energy-Efficient Multicasting in Static Ad Hoc Wireless NetworksMobile Networks and Applications, 2001
- Minimum energy mobile wireless networksIEEE Journal on Selected Areas in Communications, 1999
- Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating SetsInformation and Computation, 1999