Local approximation algorithms for scheduling problems in sensor networks

Workshop paper

Authors: Patrik Floréen, Petteri Kaski, Topi Musto, and Jukka Suomela
Title: Local approximation algorithms for scheduling problems in sensor networks
Workshop: 3rd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Wrocław, Poland, July 2007
Proceedings: Mirosław Kutyłowski, Jacek Cichoń, and Przemysław Kubiak (Eds.): Algorithmic Aspects of Wireless Sensor Networks. Third International Workshop, ALGOSENSORS 2007. Wrocław, Poland, July 14, 2007. Revised Selected Papers
Lecture Notes in Computer Science, volume 4837
Springer, Berlin, Germany, 2008
ISBN: 978-3-540-77870-7
pages 99–113
doi:10.1007/978-3-540-77871-4_10
Links: publisher’s version · authors’ version
© Springer 2008
presentation, 14 July 2007
poster, 26 May 2008
workshop · proceedings · series · DBLP
Abstract:
We study fractional scheduling problems in sensor networks, in particular, sleep scheduling (generalisation of fractional domatic partition) and activity scheduling (generalisation of fractional graph colouring). The problems are hard to solve in general even in a centralised setting; however, we show that there are practically relevant families of graphs where these problems admit a local distributed approximation algorithm; in a local algorithm each node utilises information from its constant-size neighbourhood only. Our algorithm does not need the spatial coordinates of the nodes; it suffices that a subset of nodes is designated as markers during network deployment. Our algorithm can be applied in any marked graph satisfying certain bounds on the marker density; if the bounds are met, guaranteed near-optimal solutions can be found in constant time, space and communication per node. We also show that auxiliary information is necessary—no local algorithm can achieve a satisfactory approximation guarantee on unmarked graphs.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.