Spatiotemporal multicast in sensor networks

ABSTRACT

Sensor networks often involve the monitoring of mobile phenomena. We believe this task can be facilitated by a spatiotemporal multicast protocol which we call "mobicast". Mobicast is a novel spatiotemporal multicast protocol that distributes a message to nodes in a delivery zone that evolves over time in some predictable manner. A key advantage of mobicast lies in its ability to provide reliable and just-in-time message delivery to mobile delivery zones on top of a random network topology. Mobicast can in theory achieve good spatiotemporal delivery guarantees by limiting communication to a mobile forwarding zone whose size is determined by the global worst-case value associated with a compactness metric defined over the geometry of the network (under a reasonable set of assumptions). In this work, we first studied the compactness properties of sensor networks with uniform distribution. The results of this study motivate three approaches for improving the efficiency of spatiotemporal multicast in such networks. First, spatiotemporal multicast protocols can exploit the fundamental tradeoff between delivery guarantees and communication overhead in spatiotemporal multicast. Our results suggest that in such networks, a mobicast protocol can achieve relatively high savings in message forwarding overhead by slightly relaxing the delivery guarantee, e.g., by optimistically choosing a forwarding zone that is smaller than the one needed for a 100% delivery guarantee. Second, spatiotemporal multicast may exploit local compactness values for higher efficiency for networks with non uniform spatial distribution of compactness. Third, for random uniformly distributed sensor network deployment, one may choose a deployment density to best support spatiotemporal communication. We also explored all these directions via simulation and results are presented in this paper.

REFERENCES

• 1: 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]
• 2: Jeff Boleng , Tracy Camp , Vishy Tolety, Mesh-based Geocast Routing Protocols in an Ad Hoc Network, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.184, April 23-27, 2001
• 3: Prosenjit Bose , Luc Devroye , William S. Evans , David G. Kirkpatrick, On the Spanning Ratio of Gabriel Graphs and beta-skeletons, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.479-493, April 03-06, 2002
• 4: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 5: M. Chu, H. Haussecker, and F. Zhao. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks. Int'l J. High Performance Computing Applications, 2002.
• 6: D. Eppstein. Spanning trees and spanners. In In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425--461, Amsterdam, 1999. Elsevier Science.
• 7: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 8: Qingfeng Huang , Gruia-Catalin Roman , Chenyang Lu, Spatiotemporal multicast and partitionable group membership service, 2003
• 9: Q. Huang, C. Lu, and G.-C. Roman. Mobicast: Just-in-time multicast for sensor networks under spatiotemporal constraints. In IPSN'03, 2003.
• 10: T. Imielinski and J. C. Navas. Gps-based addressing and routing. RFC2009, Computer Sciece, Rutgers University, March 1996.
• 11: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 12: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 13: Young Ko , Nitin Vaidya, Anycasting and Geocasting in Mobile Ad Hoc Networks, Texas A & M University, College Station, TX, 2000
• 14: D. Li, K. Wong, Y. Hu, and A. Sayeed. Detection, classification and tracking of targets in distributed sensor networks. IEEE Signal Processing Magazine, 19(2), March 2002.
• 15: W.-H. Liao, Y.-C. Tseng, K.-L. Lo, and J.-P. Sheu. Geogrid: A geocasting protocol for mobile ad hoc networks based on grid. Journal of Internet Technology, 1(2):23--32, 2000.
• 16: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 17: Giri Narasimhan , Michiel Smid, Approximating the Stretch Factor of Euclidean Graphs, SIAM Journal on Computing, v.30 n.3, p.978-989, 2000 [doi>10.1137/S0097539799361671]
• 18: Julio C. Navas , Tomasz Imielinski, GeoCast—geographic addressing and routing, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.66-76, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262132]
• 19: 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]
• 20: 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
• 21: A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical Report Research Report RR-3898, INRIA, Feb. 2000.
• 22: I. Stojmenovic. Voronoi diagram and convex hull based geocasting and routing in wireless networks. TR TR-99-11, University of Ottawa, December 1999.
• 23: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]
• 24: Hu Zhou , Suresh Singh, Content based multicast (CBM) in ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Experimentation, Performance, Reliability, Theory

Keywords:
mobicast, network geometry, protocols, spatiotemporal multicast, wireless ad hoc networks