loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12
Maximizing the Lifetime of Dominating Sets
Denver, Colorado
April 04-April 08
ISBN: 0-7695-2312-9
Thomas Moscibroda, ETH Zurich, Switzerland
Roger Wattenhofer, ETH Zurich, Switzerland
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, Halld?rsson, Kortsarz, and Srinivasan on the domatic partition problem.
Citation:
Thomas Moscibroda, Roger Wattenhofer, "Maximizing the Lifetime of Dominating Sets," ipdps, vol. 13, pp.242b, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, 2005
Usage of this product signifies your acceptance of the Terms of Use.