Data Preservation in Data-Intensive Sensor Networks With Spatial Correlation

ABSTRACT

Many data-intensive sensor network applications are potential big-data enabler: they are deployed in challenging environments to collect large volume of data for a long period of time. However, in the challenging environments, it is not possible to deploy base stations in or near the sensor field to collect sensory data. Therefore, the overflow data of the source nodes is first offloaded to other nodes inside the network, and is then collected when uploading opportunities become available. We call this process data preservation in sensor networks. In this paper, we take into account spatial correlation that exist in sensory data, and study how to minimize the total energy consumption in data preservation. We call this problem data preservation problem with data correlation. We show that with proper transformation, this problem is equivalent to minimum cost flow problem, which can be solved optimally and efficiently. Via simulations, we show that it outperforms an efficient greedy algorithm.

References

1. Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
2. Luigi Atzori, Antonio Iera, and Giacomo Morabito. The internet of things: A survey. Comput. Netw., 54(15):2787--2805, October 2010.
3. Hans L. Bodlaender, Richard B. Tan, Thomas C. Dijk, and Jan Leeuwen. Integer maximum flow in wireless sensor networks with energy constraint. In Proc. of the 11th Scandinavian workshop on Algorithm Theory, SWAT 08, pages 102--113.
4. Thomas Corman, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 2009.
5. R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer. Network correlated data gathering with explicit communication: Np-completeness and algorithms. IEEE/ACM Trans. Netw., 14(1):41--54, 2006.
6. Fatme El-Moukaddem, Eric Torng, and Guoliang Xing. Mobile relay configuration in data-intensive wireless sensor networks. IEEE Transactions on Mobile Computing, 12(2):261--273, February 2013.
7. A. V. Goldberg. Andrew Goldberg's network optimization library. http://www.avglab.com/andrew/soft.html.
8. A. V. Goldberg. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22(1):1--29, 1997.
9. Rick W. Ha, Pin-Han Ho, X. Sherman Shen, and Junshan Zhang. Sleep scheduling for wireless sensor networks via network flow model. Comput. Commun., 29:2469--2481, August.
10. W. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In Proc. of HICSS 2000.
11. Xiang Hou, Zane Sumpter, Burson Lucas, and Bin Tang. Maximizing data preservation in intermittently connected sensor networks. In Proc. of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2012), short paper.
12. Sushant Jain, Rahul Shah, Waylon Brunette, Gaetano Borriello, and Sumit Roy. Exploiting mobility for energy efficient data collection in wireless sensor networks. MONET, 11(3):327--339, 2006.
13. D. Jea, A. A. Somasundara, and M. B. Srivastava. Multiple controlled mobile elements (data mules) for data collection in sensor networks. In Proc. of the IEEE DCOSS, pages 244--257, 2005.
14. A. Jindal and K. Psounis. Modeling spatially correlated data in sensor networks. ACM Trans. Sensor Networks (TOSN), 2(4):466--499, 2006.
15. S. Li, Y. Liu, and X. Li. Capacity of large scale wireless networks under gaussian channel model. In Proc. of MOBICOM 2008, pages 140--151.
16. Changlei Liu and Guohong Cao. Distributed monitoring and aggregation in wireless sensor networks. In Proc. of Infocom 2010.
17. L. Luo, Q. Cao, C. Huang, L. Wang, T. Abdelzaher, and J. Stankovic. Design, implementation, and evaluation of enviromic: A storage-centric audio sensor network. ACM Transactions on Sensor Networks, 5(3):1--35, 2009.
18. L. Luo, C. Huang, T. Abdelzaher, and J. Stankovic. Envirostore: A cooperative storage system for disconnected operation in sensor networks. In Proc. of INFOCOM 2007.
19. K. Martinez, R. Ong, and J.K. Hart. Glacsweb: a sensor network for hostile environments. In Proc. of SECON 2004, pages 81--87.
20. Ioannis Mathioudakis, Neil M. White, and Nick R. Harris. Wireless sensor networks: Applications utilizing satellite links. In Proc. of the IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC 2007), pages 1--5, 2007.
21. C.H. Papadimitriou and K. Steiglitz. Combinatorial optimization: Algorithms and complexities. Prentice Hall, 1982.
22. M. Patel, S. Venkatesan, and R. Chandrasekaran. Efficient minimum-cost bandwidth-constrained routing in wireless sensor networks. pecial Issue on "Wireless Networks and Pervasive Computing, Journal of Pervasive Computing and Communications (JPCC), 2(2), 2006.
23. S. Pattem, B. Krishnamachari, and R. Govindan. The impact of spatial correlation on routing with compression in wireless sensor networks. ACM Trans. Sensor Networks(TOSN), 4(8):24--33, 2008.
24. Divyashee Sharma. Efficient Information Access in Data-Intensive Sensor Networks. Ph.D. Thesis, University of Pittsburg, 2010.
25. Masaaki Takahashi, Bin Tang, and Neeraj Jaggi. Energy-efficient data preservation in intermittently connected sensor networks. In Proc. of the International Workshop on Wireless Sensor, Actuator and Robot Networks (WiSARN), in conjunction with IEEE INFOCOM 2011.
26. D. Takaishi, H. Nishiyama, N. Kato, and R. Miura. Toward energy efficient big data gathering in densely distributed sensor networks. IEEE Transactions on Emerging Topics in Computing, 2(3):388--397, 2014.
27. Bin Tang, Neeraj Jaggi, Haijie Wu, and Rohini Kurkal. Energy efficient data redistribution in sensor networks. In Proc. of IEEE MASS 2010, pages 352--361.
28. Bin Tang, Neeraj Jaggi, Haijie Wu, and Rohini Kurkal. Energy efficient data redistribution in sensor networks. ACM Transactions on Sensor Networks, 9(2):1--28, May 2013.
29. I. Vasilescu, K. Kotay, D. Rus, M. Dunbabin, and P. Corke. Data collection, storage, and retrieval with an underwater sensor network. In Proc. of SenSys 2005, pages 154--165.
30. M. Vuran, O. Akan, and I. Akyildiz. Spatio-temporal correlation: theory and applications for wireless sensor networks. Computer Networks, 45:245--259, 2004.
31. M. Vuran and I. Akyildiz. Spatial correlation-based collaborative medium access control in wireless sensor networks. IEEE/ACM Trans. Netw., 14(2):316--329, april 2006.
32. Lili Wang, Yong Yang, Dong Kun Noh, Hieu Le, Tarek Abdelzaher, Michael Ward, and Jie Liu. Adaptsens: An adaptive data collection and storage service for solar-powered sensor networks. In Proc. of the 30th IEEE Real-Time Systems Symposium (RTSS 2009).
33. Geoff Werner-Allen, Konrad Lorincz, Jeff Johnson, Jonathan Lees, and Matt Welsh. Fidelity and yield in a volcano monitoring sensor network. In Proc. of OSDI 2006, pages 381--396.
34. Xinyu Xue, Xiang Hou, Bin Tang, and Rajiv Bagai. Data preservation in intermittently connected sensor networks with data priorities. In Proc. of IEEE SECON 2013, pages 65--73.
35. Yuan Xue, Yi Cui, and Klara Nahrstedt. Maximizing lifetime for data aggregation in wireless sensor networks. Mob. Netw. Appl., 10(6):853--864, December 2005.
36. Yong Yang, Lili Wang, Dong Kun Noh, Hieu Khac Le, and Tarek F. Abdelzaher. Solarstore: enhancing data reliability in solar-powered storage-centric sensor networks. In Proc. of MobiSys 2009, pages 333--346, 2009.
37. K. Yuan, B. Li, and B. Liang. A distributed framework for correlated data gathering in sensor networks. IEEE Trans. Veh. Technol., 57(1):578--593, 2008.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

• Networks