| Autor: |
Schumacher, André, Haanpää, Harri |
| Zdroj: |
Stabilization, Safety & Security of Distributed Systems (9783642051173); 2009, p640-654, 15p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
