Abstract
Recent work on algebraic-topological methods for verifying coverage in planar sensor networks relied exclusively on centralized computation: a limiting constraint for large networks. This paper presents a distributed algorithm for homology computation over a sensor network, for purposes of verifying coverage. The techniques involve reduction and coreduction of simplicial complexes, and are of independent interest. Verification of the ensuing algorithms is proved, and simulations detail the improved network efficiency and performance.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Arai Z., Hayashi K., Hiraoka Y.: Mayer-Vietoris sequences and coverage problems in sensor networks. Jpn. J. Ind. Appl. Math. 28, 237–250 (2011)
Awerbuch B., Gallager R.: A new distributed algorithm to find breadth first search trees. IEEE Trans. Inf. Theory. 33(3), 315–322 (1987)
Barrière, L., Fraigniaud, P., Narayanan, L.: Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In: Proc. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. (2001)
Carlsson, G., de Silva, V.: Zigzag persistence. In: Proc. Found. of Computational Mathematics. (2009)
Carlsson, G., de Silva, V., Morozov, D.: Zigzag persistent homology and real-valued functions. In: Proc. Symp. on Comput. Geometry. (2009)
Chambers E., de Silva V., Erickson J., Ghrist R.: Rips complexes of planar point sets. Discret. Comput. Geom. 44(1), 75–90 (2010)
Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. In: Proc. IEEE Int. Conf. Robot. Autom., vol. 2, pp. 1327–1332. Washington, DC (2002)
Damian, M., Pandit, S., Pemmaraju, S.: Local approximation schemes for topology control. In: Proc. ACM Symp. on Prin. of Dist. Comput. (PODC), pp. 208–217 (2006)
de Silva V., Ghrist R.: Coordinate-free coverage in sensor networks with controlled boundaries via homology. Int. J. Robot. Res. 25, 1205–1222 (2006)
de Silva V., Ghrist R.: Homological sensor networks. Notices Am. Math. Soc. 54(1), 10–17 (2007)
Eckmann B.: Harmonische funktionen und randwertaufgaben einem komplex. Comment. Math. Helvetici. 17, 240–245 (1945)
Estrin D., Culler D., Pister K., Sukhatme G.: Connecting the physical world with pervasive networks. IEEE Pervasive Comput. 1(1), 59–69 (2002)
Fekete, S., Kröller, A., Pfisterer, D., Fischer, S.: Deterministic boundary recongnition and topology extraction for large sensor networks. In: Algorithmic Aspects of Large and Complex Networks. (2006)
Gelfand S., Manin Y.: Methods of Homological Algebra, 2nd edn. Springer, Berlin (2003)
Ghrist, R., Hiraoka, Y.: Applications of sheaf cohomology and exact sequences to network coding. Proc. NOLTA: Nonlinear Theory Appl. 266–269 (2011)
Kempe, D., Dobra, A., Gehrke, J.: Computing aggregate information using gossip. In: Proc. Foundations of Computer Science, Cambridge, MA (2003)
Koskinen, H.: On the coverage of a random sensor network in a bounded domain. In: Proceedings of 16th ITC Specialist Seminar, pp. 11–18. (2004)
Kuhn F., Wattenhofer R., Zollinger A.: Ad-hoc networks beyond unit disk graphs. Wirel. Netw. 14(5), 715–729 (2008)
Li X.-Y., Wan P.-J., Frieder O.: Coverage in wireless ad-hoc sensor networks. IEEE Trans. Comput. 52(6), 753–763 (2003)
Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.: Coverage problems in wireless ad-hoc sensor networks. In: IEEE INFOCOM, pp. 1380–1387 (2001)
Mrozek M., Batko B.: Coreduction homology algorithm. Discret. Comput. Geom. 41, 96–118 (2009)
Mrozek M., Wanner Th.: Coreduction homology algorithm for inclusions and persistent homology. Comput. Math. Appl. 60(10), 2812–2833 (2010). doi:10.1016/j.camwa.2010.09.036
Muhammad, A., Egerstedt, M.: Control using higher order Laplacians in network topologies, In Proc. of the 17th International Symposium on Mathematical Theory of Networks and Systems, pp. 1024–1038. (2006)
Muhammad, A., Jadbabaie, A.: Decentralized computation of homology groups in networks by gossip. In: Proc. of American Control Conference, pp. 3438–3443 (2007)
Robinson, M.: Inverse problems in geometric graphs using internal measurements. arXiv:1008.2933v1 (2010)
Robinson, M.: Asynchronous logic circuits and sheaf obstructions. arXiv:1008.2729v1 (2010)
Tahbaz Salehi A., Jadbabaie A.: Distributed coverage verification in sensor networks without location information. IEEE Trans. Autom. Control 55(8), 1837–1849 (2010)
Tahbaz Salehi, A., Jadbabaie, A.: Distributed coverage verification in sensor networks without location information. In: IEEE Conference on Decision and Control (2008)
Xue F., Kumar P.R.: The number of neighbors needed for connectivity of wireless networks. Wirel. Netw. 10(2), 169–181 (2004)
Zhang, H., Hou, J.: Maintaining coverage and Connectivity in large sensor networks. In: International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks, Florida (2004)
The RedHom homology algorithms library: http://redhom.ii.uj.edu.pl
Computational Homology Project: http://chomp.rutgers.edu
Sensor Network Simulator: http://redhom.ii.uj.edu.pl/sensors/
Acknowledgments
The first, third and fourth author are partially supported by Polish MNiSW, Grant N201 037 31/3151 and N N201 419639. The first author is partially supported by Polish MNiSW Grant N N206 625439. The second author is supported by the ONR and by DARPA SToMP # HR0011-07-1-0002.
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Dłotko, P., Ghrist, R., Juda, M. et al. Distributed computation of coverage in sensor networks by homological methods. AAECC 23, 29–58 (2012). https://doi.org/10.1007/s00200-012-0167-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00200-012-0167-7