Segmenting a sensor field: Algorithms and applications in network design

ABSTRACT

The diversity of the deployment settings of sensor networks is naturally inherited from the diversity of geographical features of the embedded environment, and greatly influences network design. Many sensor network protocols in the literature implicitly assume that sensor nodes are deployed inside a simple geometric region, without considering possible obstacles and holes in the deployment environment. When the real deployment setting deviates from that, we often observe degraded performance. Thus, it is highly desirable to have a generic approach to handle sensor fields with complex shapes. In this article, we propose a segmentation algorithm that partitions an irregular sensor field into nicely shaped pieces such that algorithms and protocols that assume a nice sensor field can be applied inside each piece. Across the segments, problem dependent structures specify how the segments and data collected in these segments are integrated. Our segmentation algorithm does not require any extra knowledge (e.g., sensor locations) and only uses network connectivity information. This unified spatial-partitioning approach makes the protocol design become flexible and independent of deployment specifics. Existing protocols are still reusable with segmentation, and the development of new topology-adaptive protocols becomes much easier. We verified the correctness of the algorithm on various topologies and evaluated the performance improvements by integrating shape segmentation with several fundamental problems in network design.

REFERENCES

• 1: Al-Karaki, J. N. and Kamal, A. E. 2004. Routing techniques in wireless sensor networks: a survey. IEEE Wireless Commun. 11, 6, 6--28.
• 2: Boulat A. Bash , John W. Byers , Jeffrey Considine, Approximately uniform random sampling in sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052206]
• 3: 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]
• 4: 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]
• 5: Ranveer Chandra , Lili Qiu , Kamal Jain , Mohammad Mahdian, Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks, Proceedings of the 12th IEEE International Conference on Network Protocols, p.271-282, October 05-08, 2004
• 6: Choi, H. I., Choi, S. W., and Moon, H. P. 1997. Mathematical theory of medial axis transform. Pacific J. Math. 181, 1, 57--88.
• 7: Dey, T. K., Giesen, J., and Goswami, S. 2003. Shape segmentation and matching with flow discretization. In Proceedings of Workshop on Algorithms and Data Structures (WADS). 25--36.
• 8: Alexandros G. Dimakis , Vinod Prabhakaran , Kannan Ramchandran, Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 9: Alexandros G. Dimakis , Anand D. Sarwate , Martin J. Wainwright, Geographic gossip: efficient aggregation for sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127791]
• 10: Jeremy Eric Elson , Deborah L. Estrin, Time synchronization in wireless sensor networks, University of California, Los Angeles, 2003
• 11: Fang, Q., Gao, J., Guibas, L., de Silva, V., and Zhang, L. 2005. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proceedings of the 24th Conference of the IEEE Communication Society (INFOCOM). Vol. 1. 339--350.
• 12: Fang, Q., Gao, J., and Guibas, L. J. 2006. Landmark-based information storage and retrieval in sensor networks. In Proceedings of the 25th Conference of the IEEE Communication Society (INFOCOM). 1--12.
• 13: Fekete, S. P., Kröller, A., Pfisterer, D., Fischer, S., and Buschmann, C. 2004. Neighborhood-based topology recognition in sensor networks. In ALGOSENSORS. Lecture Notes in Computer Science, vol. 3121. Springer, 123--136.
• 14: 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]
• 15: 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]
• 16: Stefan Funke , Nikola Milosavljevic, Network sketching or: "How Much Geometry Hides in Connectivity?--Part II", Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.958-967, January 07-09, 2007, New Orleans, Louisiana
• 17: 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]
• 18: Greenstein, B., Estrin, D., Govindan, R., Ratnasamy, S., and Shenker, S. 2003. DIFS: A distributed index for features in sensor networks. In Proceedings of 1st IEEE International Workshop on Sensor Network Protocols and Applications. 163--173.
• 19: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 20: 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]
• 21: 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]
• 22: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 23: Frederic F. Leymarie , Benjamin B. Kimia, The Shock Scaffold for Representing 3D Shape, Proceedings of the 4th International Workshop on Visual Form, p.216-228, May 28-30, 2001
• 24: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in 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.958500]
• 25: André Lieutier, Any open bounded subset of Rⁿ has the same homotopy type than its medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781620]
• 26: MacQueen, J. B. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. 281--297.
• 27: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 28: Sebastian, T., Klein, P., and Kimia, B. 2001. Recognition of shapes by editing shock graphs. In Proceedings of the International Conference on Computer Vision (ICCV). 755--762.
• 29: Shi, Y. and Hou, Y. T. 2007. Approximation algorithm for base station placement in wireless sensor networks. In Proceedings of the IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON). 512--519.
• 30: Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, Proceedings of the Sixth International Conference on Computer Vision, p.222, January 04-07, 1998
• 31: Primoz Skraba , Qing Fang , An Nguyen , Leonidas Guibas, Sweeps over wireless sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127802]
• 32: 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]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Performance

Keywords:
Shape segmentation, flow complex, network design, sensor networks, topology-adaptive protocols