Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks

ABSTRACT

In this paper we investigate efficient strategies for supporting on-demand information dissemination and gathering in large-scale vwireless sensor networks. In particular, we propose a "comb-needle" discovery support model resembling an ancient method: use a comb to help find a needle in sands or a haystack. The model combines push and pull for information dissemination and gathering. The push component features data duplication in a linear neighborhood of each node. The pull component features a dynamic formation of an on-demand routing structure resembling a comb. The comb-needle model enables us to investigate the cost of a spectrum of push and pull combinations for supporting discovery and query in large scale sensor networks. Our result shows that the optimal routing structure depends on the frequency of query occurrence and the spatial-temporal frequency of related events in the network. The benefit of balancing push and pull for discovery in large scale geometric networks are demonstrated. We also raise the issue of query coverage in unreliable networks and investigate how redundancy can improve the coverage via both theoretical analysis and simulation. Last, we study adaptive strategies for the case where the frequencies of query and events are unknown a priori and time-varying.

REFERENCES

• 1: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 2: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 3: 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]
• 4: J. Liu, D. Petrovic, and F. Zhao, "Multi-step information-directed sensor querying in distributed sensor networks," in Proceedings of the International Conference in Acoustics, Speech and Signal Processing (ICASSP), 2003.
• 5: D. Li, K. Wong, Y. Hu, and A. Sayeed, "Detection, classification and tracking of targets in distributed sensor networks," IEEE Signal Processing Magazine, vol. 19, no. 2, March 2002.
• 6: Brian Blum , Prashant Nagaraddi , Anthony Wood , Tarek Abdelzaher , Sang Son , Jack Stankovic, An entity maintenance and connection service for sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.201-214, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066122]
• 7: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 8: Qingfeng Huang , Chenyang Lu , Gruia-Catalin Roman, Spatiotemporal multicast in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958516]
• 9: N. Sadagopan, B. Krishnamachari, and A. Helmy, "Active query forwarding in sensor networks," Elsevier Journal of Ad Hoc Networks, 2003.
• 10: G. Simon, "Probabilistic wireless network simulator," 2003, http://www.isis.vanderbilt.edu/projects/nest/prowler/.
• 11: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 12: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958494]
• 13: S. M. Ross, Introduction to probability models, 7th ed. Harcourt Academic Press, 2000.
• 14: F. Ye, G. Zhong, S. Lu, and L. Zhang, "Gradient broadcast: A robust data delivery protocol for large scale sensor networks," ACM Wireless Networks (WINET), vol. 11, no. 2, March 2005.
• 15: Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 16: A. Qayyum, L. Viennot, and A. Laouiti, "Multipoint relaying: An efficient technique for flooding in mobile wireless networks," INRIA, Tech. Rep. Research Report RR-3898, Feb. 2000. {Online}. Available: citeseer.nj.nec.com/qayyum00multipoint.html
• 17: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 18: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 19: S. Shakkottai, "Asymptotics of query strategies over a sensor network," in Proceedings of the IEEE INFOCOM, Hongkong, China, March 2004.
• 20: John Heidemann , Fabio Silva , Deborah Estrin, Matching data dissemination algorithms to application requirements, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958517]
• 21: B. Krishnamachari and J. Heidemann, "Application-specific modelling of information routing in sensor networks," in Proceedings of the IEEE International on Performance, Computing, and Communications Conference.1em plus 0.5em minus 0.4em Phoenix, Arizona, USA: IEEE, April 2004, pp. 717--722.
• 22: M. Chu, H. Haussecker, and F. Zhao, "Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks," International Journal of High Performance Computing Applications, vol. 16, no. 3, 2002.
• 23: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 24: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 25: D. Ganesan, D. Estrin, and J. Heidemann, "DIMENSIONS: Why do we need a new data handling architecture for sensor networks?" in Proceedings of the First Workshop on Hot Topics In Networks (HotNets-I), Princeton, NJ, October 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design

Keywords:
data dissemination, pull, push, query, routing, sensor network