Paper Info
Title
Distributed Sleep Scheduling in Wireless Sensor Networks via Fractional Domatic Partitioning
Abstract
We consider setting up sleep scheduling in sensor networks. We formulate the problem as an instance of the fractional domatic partition problem and obtain a distributed approximation algorithm by applying linear programming approximation techniques. Our algorithm is an application of the Garg-Könemann (GK) scheme that requires solving an instance of the minimum weight dominating set (MWDS) problem as a subroutine. Our two main contributions are a distributed implementation of the GK scheme for the sleep-scheduling problem and a novel asynchronous distributed algorithm for approximating MWDS based on a primal-dual analysis of Chvátal's set-cover algorithm. We evaluate our algorithm with ns2 simulations.
Year
DOI
Venue
2009
10.1007/978-3-642-05118-0_44
SSS
Keywords
Field
DocType
main contribution,linear programming approximation technique,fractional domatic partitioning,fractional domatic partition problem,ns2 simulation,minimum weight,approximation algorithm,gk scheme,wireless sensor networks,primal-dual analysis,set-cover algorithm,sleep-scheduling problem,dominating set,sensor network,distributed algorithm,scheduling problem,linear program,set cover,wireless sensor network
Approximation algorithm,Dominating set,Mathematical optimization,Scheduling (computing),Brooks–Iyengar algorithm,Distributed algorithm,Linear programming,Wireless sensor network,Mathematics,Domatic number
Conference
Volume
ISSN
Citations 
5873
0302-9743
2
PageRank 
References 
Authors
0.40
20
2
Name
Order
Citations
PageRank
André Schumacher1717.26
Harri Haanpää2336.37