Qingfeng Huang
Chenyang Lu
Gruia-Catalin Roman
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.
- B. Blum, P. Nagaraddi, A. Wood, T. Abdelzaher, S. Son, and J. Stankovic. An entity maintenance and connection service for sensor networks. In Proceedings of MobiSys, 2003. Google Scholar
Digital Library
- J. Boleng, T. Camp, and V. Tolety. Mesh-based geocast routing protocols in an ad hoc network. In Proceedings of the IPDPS in Wireless Networks and Mobile Computing, pages 184--193, April 2001. Google ScholarDigital Library
- P. Bose, L. Devroye, W. Evans, and D. Kirkpatrick. On the spanning ratio of gabriel graphs and β-skeletons. In Lecture Notes in Computer Science, volume 22862002, page 479, April 2002. Google ScholarDigital Library
- A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring: Application driver for wireless communications technology. In ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, 2001. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In HICSS, 2000. Google ScholarDigital Library
- Q. Huang. Spatiotemporal Multicast and Partitionable Group Membership Serivce. PhD thesis, Washington University, St. Louis, August 2003. Google ScholarDigital Library
- Q. Huang, C. Lu, and G.-C. Roman. Mobicast: Just-in-time multicast for sensor networks under spatiotemporal constraints. In IPSN'03, 2003. Google ScholarDigital Library
- T. Imielinski and J. C. Navas. Gps-based addressing and routing. RFC2009, Computer Sciece, Rutgers University, March 1996. Google ScholarDigital Library
- C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann. Impact of network density on data aggregation in wireless sensor networks. Proceedings of the (ICDCS-22), 2001. Google ScholarDigital Library
- C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Mobile Computing and Networking, pages 56--67, 2000. Google ScholarDigital Library
- Y. Ko and N. Vaidya. Geocasting in mobile ad hoc networks: Location-based multicast algorithms. TR 98-018, Texas A&M University, 1998. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- S. Madden, M. Franklin, J. Hellerstein, and W. Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. OSDI 2002, Boston MA. Google ScholarDigital Library
- G. Narasimhan and M. H. M. Smid. Approximating the stretch factor of euclidean graphs. SIAM J. Comput., 30(3):978--989, 2000. Google ScholarDigital Library
- J. C. Navas and T. Imielinski. Geocast - geographic addressing and routing. In Proceedings of MobiCom '97, pages 66--76, 1997. Google ScholarDigital Library
- S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. In Proceedings of the MobiCom'99, pages 152--162, August 1999. Google ScholarDigital Library
- W. Peng and X. Lu. On the reduction of broadcast redundancy in mobile ad hoc networks. In Proceedings of the ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2000. Google ScholarDigital Library
- 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.Google Scholar
- I. Stojmenovic. Voronoi diagram and convex hull based geocasting and routing in wireless networks. TR TR-99-11, University of Ottawa, December 1999.Google Scholar
- B. Williams and T. Camp. Comparison of broadcasting techniques for mobile ad hoc networks. In Proceedings of the ACM MOBIHOC'02, pages 194--205, 2002. Google ScholarDigital Library
- H. Zhou and S. Singh. Content based multicast (cbm) for ad hoc networks. MOBIHOC, August 2000. Google ScholarDigital Library
Index Terms
- Spatiotemporal multicast in sensor networks
Recommendations
A Mobicast Routing Protocol in Vehicular Ad-Hoc Networks
In this paper, we present a "spatiotemporal multicast", called a "mobicast", protocol for supporting applications which require spatiotemporal coordination in vehicular ad hoc networks (VANETs). The spatiotemporal character of a mobicast is to forward a ...
Design and Analysis of Spatiotemporal Multicast Protocols for Wireless Sensor Networks
We propose a new multicast communication paradigm called "spatiotemporal multicast" for supporting applications which require spatiotemporal coordination in wireless sensor networks. In this paper we focus on a special class of spatiotemporal multicast ...
A mobicast routing protocol in vehicular ad-hoc networks
GLOBECOM'09: Proceedings of the 28th IEEE conference on Global telecommunicationsIn this paper, we present a spatiotemporal multicast, called a mobicast, protocol for supporting applications which require spatiotemporal coordination in VANETs. The spatiotemporal character of a mobicast is to forward a mobicast message to vehicles ...
Comments