Approximate isocontours and spatial summaries for sensor networks

ABSTRACT

We consider the problem of approximating a family of isocontours in a sensor fleld with a topologically-equivalent family of simple polygons. Our algorithm is simple and distributed, it gracefully adapts to any user-specified representation size k, and it delivers a worst-case guarantee for the quality of approximation. In particular, we prove that the topology-respecting Hausdorff error in our k -vertex approximation is within a small constant factor of the optimal error possible with Θ(k/log m) vertices, where m is the number of contours. Evaluation of the algorithm on real data suggests that the size increase factor in practice is a constant near 2 .6, and shows no error increase. Our simulation results using a variety of synthetic and real data show that the algorithm smoothly handles complex isocontours, even for representation sizes as small as 32 or 48. Because isocontours are widely used to represent and communicate bi-variate signals, our technique is broadly applicable to innetwork aggregation and summarization of spatial data in sensor networks.

REFERENCES

• 1: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 2: C. Buragohain, S. Gandhi, J. Hershberger, and S. Suri. Contour approximation in sensor networks. In DCOSS, 2006.
• 3: K. Chintalapudi and R. Govindan. Localized edge detection in sensor fields. In SNPA, 2003.
• 4: David Culler , Prabal Dutta , Cheng Tien Ee , Rodrigo Fonseca , Jonathan Hui , Philip Levis , Joseph Polastre , Scott Shenker , Ion Stoica , Gilman Tolle , Jerry Zhao, Towards a sensor network architecture: lowering the waistline, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.24-24, June 12-15, 2005, Santa Fe, NM
• 5: A. Dhariwal, B. Zhang, B. Stauffer, C. Oberg, et al. NAMOS: Networked aquatic microbial observing system. In ICRA, 2006.
• 6: D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Canadian Cartographer, 1973.
• 7: Regina Estkowski , Joseph S. B. Mitchell, Simplifying a polygonal subdivision while keeping it simple, Proceedings of the seventeenth annual symposium on Computational geometry, p.40-49, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378612]
• 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: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 10: Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055597]
• 11: L. Guibas, J. Hershberger, J. Mitchell, and J. Snoeyink. Approximating polygons and subdivisions with minimum-link paths. In ISAAC, 1992.
• 12: J. Hellerstein, W. Hong, S. Madden, and K. Stanek. Beyond average: Toward sophisticated sensing with queries. In IPSN, 2003.
• 13: J. Hershberger and J. Snoeyink. Speeding up the Douglas-Peucker line simplification algorithm. In SDH,1992.
• 14: C. Jordan. Cours d'Analyze de l'cole Polytechnique. 1887.
• 15: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 16: A. Kolesnikov. Efficient Algorithms for Vectorization and Polygonal Approximation. PhD thesis,Department of Computer Science,University of Joensuu, 2003.
• 17: 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]
• 18: P. Liao, M. Chang, and C. Kuo. Contour line extraction with wireless sensor networks. In ICC, 2005.
• 19: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 20: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 21: K. Mayer, K. Ellis, and K. Taylor. Cattle health monitoring using wireless sensor networks. In ICCCN, 2004.
• 22: X. Meng, L. Li, T. Nandagopal, and S. Lu. Event contour: An efficient and robust mechanism for tasks in sensor networks. Computer Networks.
• 23: R. Nowak and U. Mitra. Boundary estimation in sensor networks: Theory and methods. In IPSN, 2003.
• 24: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 25: M. Singh, A. Bakshi, and V. Prasanna. Constructing topographic maps in networked sensor systems. In ASWAN, 2004.
• 26: Ignacio Solis , Katia Obraczka, Ef.cient Continuous Mapping in Sensor Networks Using Isolines, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.325-332, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.26]
• 27: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]
• 28: 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]
• 29: G. Werner-Allen, J. Johnson, M. Ruiz, J. Lees, et al. Monitoring volcanic eruptions with a wireless sensor network. In EWSN, 2005.
• 30: Wenwei Xue , Qiong Luo , Lei Chen , Yunhao Liu, Contour map matching for event detection 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.1142491]
• 31: Y. Yao and J. Gehrke. The Cougar approach to in-network query processing in sensor networks. In SIGMOD, 2002.
• 32: Y. Zhao, R. Govindan, and D. Estrin. Residual energy scan for monitoring sensor networks. In WCNC, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Theory

Keywords:
approximations, data aggregation, sensor networks