Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods

ABSTRACT

Location-free boundary recognition is crucial and critical for many fundamental network functionalities in wireless ad hoc and sensor networks. Previous designs, often coarse-grained, fail to accurately locate boundaries, especially when small holes exist. To address this issue, we propose a fine-grained boundary recognition approach using connectivity information only. This algorithm accurately discovers inner and outer boundary cycles without using location information. To the best of our knowledge, this is the first design being able to determinately locate all hole boundaries no matter how small the holes are. Also, this distributed algorithm does not rely on high node density. We formally prove the correctness of our design, and evaluate its effectiveness through extensive simulations.

REFERENCES

• 1: Xiaole Bai , Santosh Kumar , Dong Xuan , Ziqiu Yun , Ten H. Lai, Deploying wireless sensors to achieve both coverage and connectivity, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132921]
• 2: E.W. Chambers, V. de Silva, J. Erickson, and R. Ghrist. Rips complexes of planar point sets. Preprint, ArXiv:0712.0395, 2007.
• 3: Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
• 4: V. De Silva , R. Ghrist, Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology, International Journal of Robotics Research, v.25 n.12, p.1205-1222, December 2006 [doi>10.1177/0278364906072252]
• 5: Q. Fang, J. Gao, and L.J. Guibas. Locating and bypassing holes in sensor networks. In Proc. of IEEE INFOCOM, 2004.
• 6: S.P. Fekete, M. Kaufmann, A. Kröller, and N. Lehmann. A new approach for boundary recognition in geometric sensor networks. In Proc. 17th Canadian Conference on Computational Geometry, 2005.
• 7: S.P. Fekete, A. Kröller, D. Pfisterer, S. Fischer, and C. Buschmann. Neighborhood-based topology recognition in sensor networks. In Proc. of the 1st Int. Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2004.
• 8: Stefan Funke, Topological hole detection in wireless sensor networks and its applications, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080819]
• 9: Stefan Funke , Christian Klein, Hole detection or: "how much geometry hides in connectivity?", Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137911]
• 10: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 11: Robert Ghrist , Abubakr Muhammad, Coverage and hole-detection in sensor networks via homology, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 12: A. Hatcher. Algebraic Topology. Cambridge University Press, 2002.
• 13: Alexander Kröller , Sándor P. Fekete , Dennis Pfisterer , Stefan Fischer, Deterministic boundary recognition and topology extraction for large sensor networks, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1000-1009, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109668]
• 14: X. Li, G. Calinescu, P. Wan, and Y. Wang. Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems, 14(10):1035--1047, 2003.
• 15: Christian Liebchen , Romeo Rizzi, Classes of cycle bases, Discrete Applied Mathematics, v.155 n.3, p.337-355, February, 2007 [doi>10.1016/j.dam.2006.06.007]
• 16: J.R. Munkres. Topology, Second Edition. Prentice Hall, 2000.
• 17: Ananth Rao , Sylvia Ratnasamy , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 18: Olga Saukh , Robert Sauter , Matthias Gauger , Pedro José Marrón , Kurt Rothermel, On Boundary Recognition without Location Information in Wireless Sensor Networks, Proceedings of the 7th international conference on Information processing in sensor networks, p.207-218, April 22-24, 2008 [doi>10.1109/IPSN.2008.11]
• 19: Ivan Stojmenovic , Xu Lin, Power-Aware Localized Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1122-1133, November 2001 [doi>10.1109/71.969123]
• 20: W. Tutte. How to draw a graph. Proc. London Math. Soc, 13(3):743--768, 1963.
• 21: Yue Wang , Jie Gao , Joseph S.B. Mitchell, Boundary recognition in sensor networks by topological methods, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161104]
• 22: H. Whitney. Congruent graphs and the connectivity of graphs. Amer. J. Math, 54(1):150--168, 1932.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Theory

Keywords:
fgp transformation, fine-grained boundary recognition, wireless ad hoc and sensor networks