Minimizing Energy and Maximizing Network Lifetime Multicasting in Wireless Ad Hoc Networks
Date
2005
Authors
Liang, Weifa
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE Inc)
Abstract
Most mobile nodes in a wireless ad hoc network are powered by energy limited batteries, the limited battery lifetime imposes a constraint on the network performance. Therefore, energy efficiency is paramount of importance in the design of routing protocols for the applications in such a network, and efficient operations are critical to enhance the network lifetime. In this paper we consider energy-efficient routing for the minimizing energy and maximizing network lifetime multicast problem in ad hoc networks. We aim to construct a multicast tree rooted at the source and spanning the destination nodes such that the minimum residual battery energy (also referred to the network lifetime) among the nodes in the network is maximized and the total transmission energy consumption is minimized. Due to the NP-hardness of the concerned problem, all previously proposed algorithms for it are heuristic algorithms, and there is little known about the analytical performance of these algorithms in terms of approximation ratios. We here focus on devising approximation algorithms for the problem with provably guaranteed approximation ratios. Specifically, we present an approximation algorithm for finding a multicast tree such that the total transmission energy consumption is no more than γ times of the optimum, under the constraint that the network lifetime is no less than β times of the optimum, where γ is either 4ln K or O(K∈), depending on whether the network is symmetric or not, ∈ and β are constants with 0 < ∈, β ≤ 1, and K is the number of destination nodes in a multicast session.
Description
Keywords
Keywords: Algorithms; Computer networks; Energy efficiency; Energy utilization; Heuristic methods; Mobile computing; Network protocols; Approximation algorithms; Routing protocols; Transmission energy consumption; Wireless ad hoc networks; Multicasting
Citation
Collections
Source
Proceedings of the 2005 IEEE International Conference on Communications
Type
Conference paper