Abstract
Many self-configuration problems that occur in sensor networks, such as clustering or operator placement for in-network data aggregation, can be modeled as facility location problems. Unfortunately, existing distributed facility location algorithms are hardly applicable to multi-hop sensor networks. Based on an existing centralized algorithm, we therefore devise equivalent distributed versions which, to our knowledge, represent the first distributed approximations of the facility location problem that can be practicably implemented in multi-hop sensor networks with local communication. Through simulation studies, we demonstrate that, for typical instances derived from sensor-network configuration problems, the algorithms terminate in only few communication rounds, the runtime does not increase with the network size, and, finally, that our implementation requires only local communication confined to small network neighborhoods. In addition, we propose simple extensions to our algorithms to support dynamic networks with varying link qualities and node additions and deletions. Using link quality traces collected from a real sensor network deployment, we demonstrate the effectiveness of our algorithms in realistic multi-hop sensor networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Karl, H., Willig, A.: Protocols and Architectures for Wireless Sensor Networks. Wiley, Chichester (2005)
Cerpa, A., Estrin, D.: ASCENT: Adaptive Self-Configuring Sensor Networks Topologies. In: Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), New York (June 2002)
Basagni, S., Mastrogiovanni, M., Petrioli, C.: A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks. In: Proceedings of the 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS’04), IEEE Computer Society Press, Los Alamitos (2004)
Madden, S., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: a Tiny AGgregation Service for Ad-Hoc Sensor Networks. In: Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI’02), Boston, MA, USA (December 2002)
Gnawali, O., Greenstein, B., Jang, K.Y., Joki, A., Paek, J., Vieira, M., Estrin, D., Govindan, R., Kohler, E.: The TENET architecture for tiered sensor networks. In: Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SENSYS’06), Boulder, CO, USA (November 2006)
Gehweiler, J., Lammersen, C., Sohler, C.: A distributed O(1)-approximation algorithm for the uniform facility location problem. In: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’06), Cambridge, MA, USA (2006)
Moscibroda, T., Wattenhofer, R.: Facility location: Distributed approximation. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC’05), pp. 108–117. ACM Press, New York (2005)
Chudak, F., Erlebach, T., Panconesi, A., Sozio, M.: Primal-dual distributed algorithms for covering and facility location problems. Unpublished Manuscript (2005)
Frank, C., Römer, K.: Algorithms for generic role assignment in wireless sensor networks. In: Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SENSYS’05), San Diego, CA, USA (November 2005)
Vygen, J.: Approximation algorithms for facility location problems. Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45(4) (1998)
Hochbaum, D.S.: Heuristics for the fixed cost median problem. Mathematical Programming 22(1), 148–162 (1982)
Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. Journal of Algorithms 31, 228–248 (1999)
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, Springer, Heidelberg (2002)
Jain, K., Vazirani, V.V.: Primal-dual approximation algorithms for metric facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS’99), pp. 2–13. IEEE Computer Society Press, Los Alamitos (1999)
Krivitski, D., Schuster, A., Wolff, R.: A local facility location algorithm for sensor networks. In: Prasanna, V.K., Iyengar, S., Spirakis, P.G., Welsh, M. (eds.) DCOSS 2005. LNCS, vol. 3560, Springer, Heidelberg (2005)
Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Journal of the ACM 50, 795–824 (2003)
BTnodes (2006), www.btnode.ethz.ch
Woo, A., Tong, T., Culler, D.: Taming the underlying challenges of reliable multihop routing in sensor networks. In: Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SENSYS’03), Los Angeles, CA, USA (November 2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Frank, C., Römer, K. (2007). Distributed Facility Location Algorithms for Flexible Configuration of Wireless Sensor Networks. In: Aspnes, J., Scheideler, C., Arora, A., Madden, S. (eds) Distributed Computing in Sensor Systems. DCOSS 2007. Lecture Notes in Computer Science, vol 4549. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73090-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-73090-3_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73089-7
Online ISBN: 978-3-540-73090-3
eBook Packages: Computer ScienceComputer Science (R0)