Managing evolving shapes in sensor networks

ABSTRACT

This work addresses the problem of efficient distributed detection and tracking of mobile and evolving/deformable spatial shapes in Wireless Sensor Networks (WSN). The shapes correspond to contiguous regions bounding the locations of sensors in which the readings of the sensors satisfy a particular threshold-based criterion related to the values of a physical phenomenon that they measure. We formalize the predicates representing the shapes in such settings and present detection algorithms. In addition, we provide a light-weight protocol and aggregation methods for energy-efficient distributed execution of those algorithms. Another contribution of this work is that we developed efficient techniques for detecting a co-occurrence of shapes within a given proximity from each other. Our experiments demonstrate that, when compared to the centralized techniques -- which is, predicates being detected in a dedicated sink -- as well as distributed periodic contours construction, our methodologies yield significant energy/communication savings.

References

1. R. Adaikkalavan and S. Chakravarthy. Event specification and processing for advanced applications: Generalization and formalization. In Database and Expert Systems Applications, pages 369--379, 2007.
2. K. Akkaya and M. Younis. A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3(3), 2005.
3. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: A survey. Comput. Netw., 38(4):393--422, Mar. 2002.
4. M. Celik, S. Shekhar, J. P. Rogers, and J. A. Shine. Mixed-drove spatiotemporal co-occurrence pattern mining. IEEE Trans. on Knowl. and Data Eng., 20(10):1322--1335, Oct. 2008.
5. I. Demirkol, C. Ersoy, and F. Alagoz. Mac protocols for wireless sensor networks: A survey. IEEE Communication Magazine, 2006.
6. M. Duckham, L. Kulik, M. Worboys, and A. Galton. Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recogn., 41(10):3224--3236, Oct. 2008.
7. S. Duttagupta, K. Ramamritham, and P. Kulkarni. Tracking dynamic boundaries using sensor network. Parallel and Distributed Systems, IEEE Transactions on, 22(10):1766--1774, Oct 2011.
8. H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane. Information Theory, IEEE Transactions on, 29(4):551--559, Jul 1983.
9. M. Erwig and M. Schneider. Spatio-temporal predicates. IEEE Trans. on Knowl. and Data Eng., 14(4):881--901, July 2002.
10. M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental clustering for mining in a data warehousing environment. In PROC. 24TH INT. CONF. VERY LARGE DATA BASES, VLDB, pages 323--333, 1998.
11. M. Ester, H. peter Kriegel, J. S, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. pages 226--231. AAAI Press, 1996.
12. M. Fayed and H. T. Mouftah. Localised alpha-shape computations for boundary recognition in sensor networks. Ad Hoc Netw., 7(6):1259--1269, Aug. 2009.
13. S. Gandhi, J. Hershberger, and S. Suri. Approximate isocontours and spatial summaries for sensor networks. In Proceedings of the 6th International Conference on Information Processing in Sensor Networks, IPSN '07, pages 400--409, New York, NY, USA, 2007. ACM.
14. O. C. Ghica, G. Trajcevski, P. Scheuermann, Z. Bischof, and N. Valtchanov. Sidnet-swans: A simulator and integrated development platform for sensor networks applications. In Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems, SenSys '08, pages 385--386, New York, NY, USA, 2008. ACM.
15. C. Hartung, R. Han, C. Seielstad, and S. Holbrook. Firewxnet: a multi-tiered portable wireless system for monitoring weather conditions in wildland fire environments. In MobiSys, 2006.
16. A. Hinze and A. Voisard. A parametrized algebra for event notification services. In TIME, 2002.
17. N. Hubbell and Q. Han. Dragon: Detection and tracking of dynamic amorphous events in wireless sensor networks. Parallel and Distributed Systems, IEEE Transactions on, 23(7):1193--1204, July 2012.
18. K. Iwanicki and M. van Steen. A case for hierarchical routing in low-power wireless embedded networks. TOSN, 8(3):25, 2012.
19. J. Jeong, T. Hwang, T. He, and D. H.-C. Du. Mcta: Target tracking algorithm based on minimal contour in wireless sensor networks. In INFOCOM, 2007.
20. J. Jiang, M. Worboys, and S. Nittel. Qualitative change detection using sensor networks based on connectivity information. GeoInformatica, 15(2):305--328, 2011.
21. S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tinydb: An acquisitional query processing system for sensor networks. ACM Trans. Database Syst., 30(1):122--173, Mar. 2005.
22. N. Megiddo, N. Megiddo, N. Megiddo, and N. Megiddo. Linear-time algorithms for linear programming in r3 and related problems. In Foundations of Computer Science, 1982. SFCS '08. 23rd Annual Symposium on, pages 329--338, Nov 1982.
23. M. M. A. Mohamed, A. A. Khokhar, and G. Trajcevski. Energy efficient in-network data indexing for mobile wireless sensor networks. In SSTD, pages 165--182, 2013.
24. K. G. Pillai, R. A. Angryk, and B. Aydin. A filter-and-refine approach to mine spatiotemporal co-occurrences. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL'13, pages 104--113, New York, NY, USA, 2013. ACM.
25. F. Qian, Q. He, K. Chiew, and J. He. Spatial co-location pattern discovery without thresholds. Knowledge and Information Systems, 33(2):419--445, 2012.
26. R. Szewczyk, A. M. Mainwaring, J. Polastre, J. Anderson, and D. E. Culler. An analysis of a large scale habitat monitoring application. In SenSys, pages 214--226, 2004.
27. G. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE MELECON âĂŹ83, pages 10--02, 1983.
28. M. Umer, L. Kulik, and E. Tanin. Spatial interpolation in wireless sensor networks: localized algorithms for variogram modeling and kriging. GeoInformatica, 14(1):101--134, 2010.
29. Y. Wang, J. Gao, and J. S. B. Mitchell. Boundary recognition in sensor networks by topological methods. In MOBICOM, pages 122--133, 2006.
30. G. Werner-Allen, K. Lorincz, M. Welsh, O. Marcillo, J. Johnson, M. Ruiz, and J. Lees. Deploying a wireless sensor network on an active volcano. IEEE Internet Computing, 10(2), 2006.
31. A. Woo, S. Madden, and R. Govindan. Networking support for query processing in sensor networks. Communications of the ACM, 47:2004, 2004.
32. F. Zhou, G. Trajcevski, O. Ghica, R. Tamassia, A. Khokhar, and P. Scheuermann. Deflection aware tracking principal selection in active wireless sensor networks. IEEE Trans. on Vehicular Technology, 61(7), 2012.
33. X. Zhu, R. Sarkar, J. Gao, and J. Mitchell. Light-weight contour tracking in wireless sensor networks. In INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, pages --, April 2008.

Index Terms

• Information systems