Tools from computational homology are introduced to verify coverage in an idealized sensor network. These methods are unique in that, while they are coordinate-free and assume no localization or orientation capabilities for the nodes, there are also no probabilistic assumptions. The key ingredient is the theory of homology from algebraic topology. The robustness of these tools is demonstrated by adapting them to a variety of settings, including static planar coverage, 3-D barrier coverage, and time-dependent sweeping coverage. Results are also given on hole repair, error tolerance, optimal coverage, and variable radii. An overview of implementation is given.
Allili, M. , Mischaikow, K. , and Tannenbaum, A. 2001. Cubical homology and the topological classification of 2D and 3D imagery . IEEE International Conference on Image Processing, pp. 173-176 .
2.
Ames, A.2005. A homology theory for hybrid systems: hybrid homology . Lecture Notes in Computer Science3414, pp. 86-102 .
3.
Batalin, M. and Sukhatme, G. 2002. Spreading out: a local approach to multi-robot coverage . Proceedings of 6th International Symposium on Distributed Autonomous Robotic Systems, Fukuoka, Japan.
4.
Batalin, M.Hattig, M. and Sukhatme, G. 2004. Mobile robot navigation using a sensor networkProceedings ICRA.
5.
Bekris, K. and Kavraki, L.2005. A review of recent results in robotic sensor networks . ACM Computing Surveys (submitted).
6.
Bulusu, N. , Heidelmann, J. and Estrin, D. 2001. Adaptive beacon placement . Proceedings of Conference on Distributed Computing Systems. Computational Geometry Algorithms Library, http://www.cgal/org/
7.
Corke, P. , Peterson, R. and Rus, D.2005. Localization and navigation assisted by cooperating networked sensors and robots . International Journal of Robotics Research24(9): 771-786 .
8.
Cortés, J. , Martínez, S. , Karatas, T. , and Bullo, F.2004. Coverage control for mobile sensing networks . IEEE Transactions on Robotics and Automation20(2): 243-255 .
9.
Delfinado, C. and Edelsbrunner, H.1995. An incremental algorithm for Betti numbers of simplicial complexes on the 3-spheres . Computer Aided Geometrical Design12(7): 771-784 .
10.
de Silva, V. and Carlsson, G. 2004. Topological estimation using witness complexes . Symposium on Point-Based Graphics, ETH Zurich.
11.
de Silva, V. and Ghrist, R.Coverage in sensor networks via persistent homology . Alg. Geom. Topology (to appear).
12.
de Silva, V. , Ghrist, R. and Muhammad, A.2005. Blind swarms for coverage in 2-d . Proceedings of Robotics: Systems and Science.
13.
Eckhoff, J.1993. Helly, Radon, and Carathéodory type theorems. In Handbook of Convex Geometry (eds P. M. Gruber and J. M. Wills ), pp. 389-448, North Holland, Amsterdam .
14.
Estrin, D. , Culler, D. , Pister, K. and Sukhatme, G.2002. Connecting the physical world with pervasive networks . IEEE Pervasive Computing1(1): 59-69 .
15.
Fekete, S. , Kröller, A. , Pfisterer, D. , and Fischer, S.2006. Deterministic boundary recongnition and topology extraction for large sensor networks . Algorithmic Aspects of Large and Complex Networks.
16.
Gage, D. W. 1992. Command control for many-robot systems . 19th Annual AUVS Technical Symposium, Huntsville, AL, USA, pp. 22-24 .
17.
Galstyan, A. , Krishnamachari, B. , Lerman, K. and Pattem, S.2003. Distributed online localization in sensor networks using a moving target. Preprint.
18.
Ghrist, R. , Lipsky, D. , Poduri, S. and Sukhatme, G. 2006. Node isolation in coordinate-free networks . Proceedings of the Sixth International Workshop on Algorithmic Foundations of Robotics.
19.
Gromov, M.1987. Hyperbolic Groups. Essays in Group Theory, MSRI: Springer-Verlag .
20.
Hatcher, A.2002. Algebraic Topology. Cambridge University Press .
21.
Hausmann, J.-C.1995. On the Vietoris-Rips complexes and a cohomology theory for metric spaces . Annals of Mathematical Studies138: 175-188 .
22.
Hsin, C.-F. and Liu, M. 2004. Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms . Proceedings of IPSN.
23.
Huang, C.-F. and Tseng, Y.-C. 2003. The coverage problem in a wireless sensor network . ACM International Workshop on Wireless Sensor Networks and Applications, pp. 115-121 .
24.
Kaczynski, T. , Mischaikow, K. and Mrozek, M.2004. Computational Homology, Applied Mathematical Sciences 157, Springer-Verlag .
25.
Koskinen, H. 2004. On the coverage of a random sensor network in a bounded domain . Proceedings of 16th ITC Specialist Seminar, pp. 11-18 .
26.
Kumar, S. , Lai, T. H. and Balogh, J. 2004. On k-coverage in a mostly sleeping sensor network . Proceedings of 10th International Conference on Mobile Computing and Networking.
27.
Li, X.-Y. , Wan, P.-J. and Frieder, O.2003. Coverage in wireless ad-hoc sensor networks . IEEE Transaction on Computers52(6): 753-763 .
28.
Liu, B. and Towsley, D. 2004. A study of the coverage of large-scale sensor networks . IEEE International Conference on Mobile Ad-hoc and Sensor Systems.
29.
Meguerdichian, S. , Koushanfar, F. , Potkonjak, M. , and Srivastava, M. 2001. Coverage problems in wireless ad-hoc sensor network . IEEE INFOCOM, pp. 1380-1387 .
30.
Mischaikow, K. , Mrozek, M. , Reiss, J. and Szymczak, A.1999. Construction of symbolic dynamics from experimental time series . Physical Revue Letters82(6): 1144-1144 .
31.
Moses, R. , Krishnamurthy, D. and Patterson, R.2002. A self-localization method for wireless sensor networks . EURASIP Journal of Applied Signal Processing4: 348-358 .
32.
Muhammad, A. , Ghrist, R. and Egerstedt, M.2006. Beyond graphs: higher dimensional structures for networked control systems . Control Systems Magazine (to appear).
33.
Plex, version 2.1, Jan, 2006, http://math.stanford.edu/comptop/programs/plex/
34.
Rao, A. , Ratnasamy, S. , Papdimitriou, C. , Shenker, S. , and Stoika, I. 2003. Geographic routing without location information . Proceedings ACM MOBICCOM.
35.
Simić, S. and Sastry, S.2003. Distributed environmental monitoring using random sensor networks . Lecture Notes in Computer Science2634, pp. 582-592 .
36.
Vietoris, L.1927Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen . Math. Ann.97: 454-472 .
37.
Xue, F. and Kumar, P. R.2004. The number of neighbors needed for connectivity of wireless networks .Wireless Networks10(2) 169-181 .
38.
Zhang, H. and Hou, J. 2004. Maintaining coverage and connectivity in large sensor networks . International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless and Peer-to-Peer Networks, Florida, USA, February.
39.
Zomorodian, A. and Carlsson, G. 2004. Computing persistent homology . Proceedings of 20th ACM Symposium on Computers in Geometry, pp. 346-356 .
