Maximizing the Lifetime of Dominating Sets
Citations Over TimeTop 10% of 2005 papers
Abstract
We investigate the problem of maximizing the lifetime of wireless ad hoc and sensor networks. Being battery powered, nodes in such networks have to perform their intended task under rigid energy restrictions that forces the designers to impose a judicious power management and scheduling. For the purpose of saving energy, dominating set based clustering has turned out to be a useful and generic concept in such networks. In data gathering applications, for example, only nodes in the dominating set must be active, while all other nodes can remain in the energy-efficient sleep mode. Prolonging the duration of such a dominating set based clustering is a key algorithmic challenge. In this paper, we define the maximum cluster-lifetime problem which asks for a schedule that maximizes the time the network is clustered by a dominating set. We give approximation algorithms with an approximation ratio of O(log n) for several variants of the maximum cluster-lifetime problem. Our approach is based on results given in a paper by Feige, Ilalldorsson, Kortsarz, and Srinivasan on the domatic partition problem.
Related Papers
- → Clustering in wireless sensor networks(2009)71 cited
- → Algorithms on Graphs with Small Dominating Targets(2006)7 cited
- → ALGORITHMS FOR MINIMUM CONNECTED CAPACITATED DOMINATING SET PROBLEM(2011)4 cited
- On constructing 2-connected 2-dominating set using two centralized algorithms(2009)
- Algorithms for Dominating Set Problems in OTIS Networks(2012)