Detecting basic topological changes in sensor networks by local aggregation

ABSTRACT

Wireless sensor networks (WSNs) can provide real-time information about geospatial environments, and so have the potential to play an important role in the monitoring of geographic phenomena. The research reported in this paper uses WSNs to provide salient information about spatially distributed dynamic fields, such as regional variations in temperature or concentration of a toxic gas. The focus is on topological changes to areas of high-activity that occur during the evolution of the field. Topological changes investigated include region merging and splitting, and hole formation or elimination. Such changes are formally characterized, and an algorithm is developed that detects such changes by means purely of in-network processing. The efficiency of this algorithm is investigated both theoretically and using simulation experiments.

REFERENCES

• 1: Prowler-probabilistic wireless network simulator. http://www.isis.vanderbilt.edu/Projects/nest/prowler/. (Last accessed June 4, 2008).
• 2: B. Deb, S. Bhatnagar, and B. Nath. STREAM: Sensor topology retrieval at multiple resolutions. Telecommunication Systems, 26(2--4):285--320, 2004.
• 3: 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]
• 4: S. Fekete, A. Kröller, D. Pfisterer, S. Fischer, and C. Buschmann. Neighborhood-based topology recognition in sensor networks. In Algorithmic Aspects of Wireless Sensor Networks, LNCS 3121, pages 123--136, 2004.
• 5: 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]
• 6: A. Galton. Fields and objects in space, time, and space-time. Spatial Cognition and Computation, 4(1):39--68, 2004.
• 7: Sorabh Gandhi , John Hershberger , Subhash Suri, Approximate isocontours and spatial summaries for sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236411]
• 8: J. Jiang. Experiment video of topological change detection. http://www.spatial.maine.edu/~jixiang.jiang/tpchanges.zip, 2008. (Last accessed Sept. 5, 2008).
• 9: J. Jiang and M. Worboys. Specifying events by changes in topological properties (extended abstract). In 4th International Conference on Geographic Information Science (GIScience 2006), 2006.
• 10: A C Kilgour, Techniques for modelling and displaying 3D scenes, Advances in computer graphics II, Springer-Verlag New York, Inc., New York, NY, 1986
• 11: W. Kropatsch. Building irregulars pyramids by dual graph contraction. IEE Proceedings on Vision, Image and Signal Processing, 142(6):366--374, 1995.
• 12: M. Li and B. Yang. A survey on topology issues in wireless sensor network. In Proceedings of the 2006 International Conference on Wireless Networks, page 503, Las Vegas, Nevada, USA, 2006.
• 13: S. Nittel , A. Stefanidis , I. Cruz , M. Egenhofer , D. Goldin , A. Howard , A. Labrinidis , S. Madden , A. Voisard , M. Worboys, Report from the first workshop on geo sensor networks, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974146]
• 14: A. Rosenfeld. Adjacency in digital pictures. Information and Control, 26:24--33, 1974.
• 15: R. Sarkar, X. Zhu, J. Gao, L. Guibas, and J. Mitchell. Iso-contour queries and gradient descent with guaranteed delivery in sensor networks. In Proceedings of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), Phoenix, AZ, USA, 2008.
• 16: Markus Schneider , Thomas Behr, Topological relationships between complex spatial objects, ACM Transactions on Database Systems (TODS), v.31 n.1, p.39-81, March 2006 [doi>10.1145/1132863.1132865]
• 17: Michel Scholl , Agnés Voisard, Geographic applications: An experience with O2, Building an object-oriented database system: the story of 02, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 18: Adam Silberstein , Rebecca Braynard , Jun Yang, Constraint chaining: on energy-efficient continuous monitoring in sensor networks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142492]
• 19: E. Sokolowsky, H. Mitchell, and S. Maher. Wildfire growth around Yellowstone National Park in 1988 (WMS). http://svs.gsfc.nasa.gov/vis/a000000/a002900/a002909/index.html, 2004. (Last accessed Nov. 30, 2007).
• 20: N. Trigoni, Y. Yao, A. Demers, J. Gehrke, and R. Rajaraman. Multi-query optimization for sensor networks (DCOSS'05). In Proceedings of International Conference on Distributed Computing in Sensor Systems, pages 307--32, 2005.
• 21: Hilderick A. van der Meiden , Willem F. Bronsvoort, Tracking topological changes in feature models, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236295]
• 22: Michael F. Worboys , Petros Bofakos, A Canonical Model for a Class of Areal Spatial Objects, Proceedings of the Third International Symposium on Advances in Spatial Databases, p.36-52, June 23-25, 1993
• 23: M. Worboys and M. Duckham. Monitoring qualitative spatiotemporal change for geosensor networks. International Journal of Geographical Information Science, 20(10):1087--1108, 2006.
• 24: X. Zhu, R. Sarkar, J. Gao, and J. Mitchell. Light-weight contour tracking in wireless sensor networks. In Proceedings of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), Phoenix, AZ, USA, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms

Keywords:
sensor network, spatio-temporal, topological changes