On-line sensing task optimization for shared sensors

ABSTRACT

Shared sensing infrastructures that allow multiple applications to share deployed sensors are emerging and Internet protocol based access for such sensors has already been prototyped and deployed. As a large number of applications start accessing shared sensors, the efficiency of resource usage at the embedded nodes and in the network infrastructure supporting them becomes a concern. To address this, we develop methods that detect when common data and common stream processing is requested by multiple applications, including cases where only some of the data is shared or only intermediate processing steps are common. The communication and processing is then modified to eliminate the redundancies. Specifically, we use an interval-cover graph to minimize communication redundancies and a joint data flow graph optimization to remove computational redundancies. Both methods operate online and allow application requests to be dynamically added or removed. The proposed methods are evaluated using applications on a road traffic sensing infrastructure.

References

1. K. Aberer, M. Hauswirth, and A. Salehi. Infrastructure for data processing in large-scale interconnected sensor networks. In International Conference on Mobile Data Management, May 2007.
2. J. Cocke. Global common subexpression elimination. In Proceedings of symposium on Compiler Optimization, 1970.
3. A. Dunkels. Full TCP/IP for 8-bit architectures. In ACM MobiSys, 2003.
4. S. B. Eisenman, E. Miluzzo, N. D. Lane, R. A. Peterson, G.-S. Ahn, and A. T. Campbell. The bikenet mobile sensing system for cyclist experience mapping. In Sensys, 2007.
5. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57). North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands, 2004.
6. C.-C. Han, R. K. Rengaswamy, R. Shea, E. Kohler, and M. Srivastava. Sos: A dynamic operating system for sensor networks. In MobiSys, 2005.
7. E. Horvitz, J. Apacible, R. Sarin, and L. Liao. Prediction, expectation, and surprise: Methods, designs, and study of a deployed traffic forecasting service. In UAI, 2005.
8. R. Huebsch, M. Garofalakis, J. M. Hellerstein, and I. Stoica. Sharing aggregate computation for distributed queries. In SIGMOD, 2007.
9. J. W. Hui and D. Culler. The dynamic behavior of a data dissemination protocol for network programming at scale. In SenSys, 2004.
10. J. W. Hui and D. E. Culler. IP is dead, long live IP for wireless sensor networks. In ACM Sensys, 2008.
11. B. Hull, V. Bychkovsky, Y. Zhang, K. Chen, M. Goraczko, A. Mui, E. Shih, H. Balakrishnan, and S. Madden. Cartel: A distributed mobile sensor computing system. In Sensys, 2006.
12. A. Kansal, S. Nath, J. Liu, and F. Zhao. Senseweb: An infrastructure for shared sensing. IEEE Multimedia, 14(4), 2007.
13. S. Krishnamurthy, M. J. Franklin, G. Jacobson, and J. M. Hellerstein. The case for precision sharing. In VLDB, 2004.
14. S. Krishnamurthy, C. Wu, and M. J. Franklin. On-the-fly sharing for streamed aggregation. In SIGMOD, June 2006.
15. B. Kusy, E. Cho, K. Wong, and L. Guibas. Enabling data interpretation through user collaboration in sensor networks. In Workshop on Applications, Systems, and Algorithms for Image Sensing (ImageSense), November 2008.
16. P. Levis and D. Culler. Mate: a tiny virtual machine for sensor networks. In ASPLOS, 2002.
17. M. Li, T. Yan, D. Ganesan, E. Lyons, P. Shenoy, A. Venkataramani, and M. Zink. Multi-user data sharing in radar sensor networks. In SenSys, 2007.
18. S. Madden, M. Shah, J. M. Hellerstein, and V. Raman. Continuously adaptive continuous queries over streams. In SIGMOD, 2002.
19. M. Ocean, A. Bestavros, and A. Kfoury. snbench: Programming and virtualization framework for distributed multitasking sensor networks. In Proceedings of the Second Int'l Conference on Virtual Execution Environments, June 2006.
20. N. B. Priyantha, A. Kansal, M. Goraczko, and F. Zhao. Tiny web services: Design and implementation of interoperable and evolvable sensor networks. In ACM Sensys, 2008.
21. O. Riva and C. Borcea. The urbanet revolution: Sensor power to the people! IEEE Pervasive Computing, 6(2):41--49, 2007.
22. P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. Efficient and extensible algorithms for multi query optimization. In SIGMOD, 2000.
23. J. Shneidman, P. Pietzuch, M. Welsh, M. Seltzer, and M. Roussopoulos. A cost-space approach to distributed query optimization in stream based overlays. In Proceedings of the 1st IEEE International Workshop on Networking Meets Databases, 2005.
24. N. Trigoni, Y. Yao, A. J. Demers, J. Gehrke, and R. Rajaraman. Multi-query optimization for sensor networks. In DCOSS, pages 307--321, 2005.
25. S. Wang, E. Rundensteiner, S. Ganguly, and S. Bhatnagar. State-slice: New paradigm of multi-query optimization of window-based stream queries. In VLDB, 2006.
26. S. Xiang, H. B. Lim, K.-L. Tan, and Y. Zhou. Two-tier multiple query optimization for sensor networks. In ICDCS, 2007.
27. J. Yoon, B. Noble, and M. Liu. Surface street traffic estimation. In MobiSys, 2007.

Index Terms

• Human-centered computing

  • Collaborative and social computing

    • Collaborative and social computing systems and tools

• Information systems

  • World Wide Web