Location-based broadcasting for dense mobile ad hoc networks

ABSTRACT

We consider broadcasting protocols in mobile ad hoc networks that propagate a message from a node to all of the nodes of a network. In order to reduce the impact of mobility on protocols, instead of relying on the frequently changing communication topology, our approaches depend on a less frequently changing and more stable characteristic --- the distribution of mobile nodes. We propose two broadcasting approaches. For each approach, we provide specific constraints on distribution and mobility of mobile nodes to guarantee that all the nodes receive the broadcast data. Under these constraints, given a network with area A, our approaches achieve broadcasting in O(A/R²) steps, where R is the transmission range.

REFERENCES

• 1: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 2: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 3: Y. Chen. Design and Analysis of Distributed Primitives for Mobile Ad Hoc Networks. PhD thesis, Texas A&M University, Auguet 2005.
• 4: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
• 5: Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Elad Schiller , Alex A. Shvartsman , Jennifer Welch, Brief announcement: virtual mobile nodes for mobile ad hoc networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011845]
• 6: S. Dolev, S. Gilbert, N. A. Lynch, A. A. Shvartsman, and J. L. Welch. Geoquorums: Implementing atomic memory in ad hoc networks. In Proc. 17th International Symposium on Distributed Computing, pages 306--320, Oct. 2003.
• 7: R. Gallager. A perspective on multiaccess channels. IEEE Trans. Inform. Theory, 31:124--142, 1985.
• 8: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014 ]
• 9: T. Imielinski and B. R. Badrinath. Wireless graffiti - data, data everywhere matters. In Proc. 28th International Conference on Very Large Data Bases (VLDB), pages 9--19, Hong Kong, China, August 2002.
• 10: T. Imielinski and S. Goel. Dataspace: Querying and monitoring deeply networked collections in physical space. IEEE Personal Communications Magazine, 7(5):4--9, October 2000.
• 11: E. Kaplan. Understanding GPS. Artech House, Boston, MA, 1996.
• 12: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 13: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 14: S. S. Kulkarni and U. Arumugam. Collision-free communication in sensor networks. In Proc. 6th Symposium on Self-Stabilizing Systems (SSS), pages 17--31, San Francisco, CA, June 2003.
• 15: A. Qayyum , L. Viennot , A. Laouiti, Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.298, January 07-10, 2002
• 16: Hyojun Lim , Chongkwon Kim, Multicast tree construction and flooding in wireless ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346865]
• 17: M. Mauve, J. Widmer, and H. Hartenstein. A survey on position-based routing in mobile ad hoc networks. IEEE Network Magazine, 15(6):30--39, November 2001.
• 18: 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]
• 19: Dragos Niculescu , Badri Nath, Trajectory based forwarding and its applications, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939012]
• 20: Elena Pagani, Providing reliable and fault tolerant broadcast delivery in mobile ad-hoc networks, Mobile Networks and Applications, v.4 n.3, p.175-192, Oct 1999 [doi>10.1023/A:1019198815518]
• 21: 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
• 22: Karim Seada , Ahmed Helmy , Ramesh Govindan, On the effect of localization errors on geographic face routing in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984633]
• 23: M. Shur and S. Wagner. Sensitive skin. IEEE Sensors Journal, 1(1):41--51, June 2001.
• 24: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 25: J. Sucec and I. Marsic. An efficient distributed network-wide broadcast algorithm for mobile ad hoc networks. Technical Report CAIP 248, Rutgers University, Piscataway, NJ, September 2000.
• 26: Brett Warneke , Matt Last , Brian Liebowitz , Kristofer S. J. Pister, Smart Dust: Communicating with a Cubic-Millimeter Computer, Computer, v.34 n.1, p.44-51, January 2001 [doi>10.1109/2.963443 ]
• 27: 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]
• 28: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]

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.4 Distributed Systems

General Terms:
Algorithms, Theory

Keywords:
broadcasting, location-based algorithm, mobile ad hoc networks