Approximate minimum-energy multicasting in wireless ad hoc networks
Author:
- 24 April 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 5 (4) , 377-387
Abstract
A wireless ad hoc network consists of mobile nodes that are equipped with energy-limited batteries. As mobile nodes are battery-operated, an important issue in such a network is to minimize the total power consumption for each operation. Multicast is one of fundamental operations in any modern telecommunication network including wireless ad hoc networks. Given a multicast request consisting of a source node and a set of destination nodes, the problem is to build a minimum-energy multicast tree for the request such that the total transmission power consumption in the tree is minimized. Since the problem in a symmetric wireless ad hoc network is NP-complete, we instead devise an approximation algorithm with provable approximation guarantee. The approximation of the solution delivered by the proposed algorithm is within a constant factor of the best-possible approximation achievable unless P = NP.Keywords
This publication has 25 references indexed in Scilit:
- A cooperative nearest neighbours topology control algorithm for wireless ad hoc networks2004
- Maximizing static network lifetime of wireless broadcast ad hoc networks2004
- Design and analysis of an MST-based topology control algorithm2004
- Algorithmic aspects of topology control problems for ad hoc networks2002
- Constructing minimum-energy broadcast trees in wireless ad hoc networks2002
- Resource management in energy-limited, bandwidth-limited, transceiver-limited wireless networks for session-based multicastingComputer Networks, 2002
- A Survey of Energy Efficient Network Protocols for Wireless NetworksWireless Networks, 2001
- Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating SetsInformation and Computation, 1999
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner TreesJournal of Algorithms, 1995
- A design concept for reliable mobile radio networks with frequency hopping signalingProceedings of the IEEE, 1987