Boundary recognition in sensor networks by topological methods

ABSTRACT

Wireless sensor networks are tightly associated with the underlying environment in which the sensors are deployed. The global topology of the network is of great importance to both sensor network applications and the implementation of networking functionalities. In this paper we study the problem of topology discovery, in particular, identifying boundaries in a sensor network. Suppose a large number of sensor nodes are scattered in a geometric region, with nearby nodes communicating with each other directly. Our goal is to find the boundary nodes by using only connectivity information. We do not assume any knowledge of the node locations or inter-distances, nor do we enforce that the communication graph follows the unit disk graph model. We propose a simple, distributed algorithm that correctly detects nodes on the boundaries and connects them into meaningful boundary cycles. We obtain as a byproduct the medial axis of the sensor field, which has applications in creating virtual coordinates for routing. We show by extensive simulation that the algorithm gives good results even for networks with low density. We also prove rigorously the correctness of the algorithm for continuous geometric domains.

REFERENCES

• 1: Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564914]
• 2: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 3: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, MAP: medial axis based geometric routing in sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080839]
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: Jeremy Eric Elson , Deborah L. Estrin, Time synchronization in wireless sensor networks, 2003
• 6: Qing Fang , Jie Gao , Leonidas J. Guibas, Locating and bypassing holes in sensor networks, Mobile Networks and Applications, v.11 n.2, p.187-200, April 2006 [doi>10.1007/s11036-006-4471-y]
• 7: Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proc. 24th Conference of the IEEE Communication Society (INFOCOM) pp. 339--350, 2005.
• 8: 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 pp. 82--85, 2005.
• 9: S. P. Fekete, A. Kröller, D. P. Fisterer, S. Fischer, and C. Buschmann. Neighborhood-based topology recognition in sensor networks. In Proc. ALGOSENSORS Springer LNCS vol. 3121, pp. 123--136, 2004.
• 10: 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]
• 11: 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]
• 12: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 13: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. UCLA/CSD-TR 02-0013, UCLA, 2002.
• 14: 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
• 15: M. Held. Voronoi diagrams and offset curves of curvilinear polygons. Computer Aided Design 30(4):287--300,1998.
• 16: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 17: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 18: Y. -J. Kim, R. Govindan, B. Karp, and S. Shenker. Geographic routing made practical. In Proc. 2nd USENIX/ACM Sympos. Networked System Design and Implementation pp. 217--230, 2005.
• 19: 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]
• 20: J. S. B. Mitchell. A new algorithm for shortest paths among obstacles in the plane. Ann. Math. Artif. Intell. 3:83--106, 1991.
• 21: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J. -R. Sack and J. Urrutia, eds., Handbook of Computational Geometry pp. 633--701. Elsevier, 2000.
• 22: E. M. Royer, P. M. Melliar-Smith, and L. E. Moser. An analysis of the optimum node density for ad hoc mobile networks. In Proc. IEEE Internat. Conf. on Communications pp. 857--861, 2001.

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Theory

Keywords:
boundary detection, sensor networks, shortest path tree