Regional gossip routing for wireless ad hoc networks

ABSTRACT

Many routing protocols have been proposed for wireless ad hoc networks, and most of them are based on some variants of flooding. Thus many routing messages are propagated through the network unnecessarily despite various optimizations. Gossip based routing method has been used and re-investigated to reduce the number of messages in both wired networks and wireless ad hoc networks. However, the global gossiping still generates many unnecessary messages in the area that could be far away from the line between sender node and receiver node. We propose a regional gossip approach, where only the nodes within some region forward a message with some probability, to reduce the overhead of the route discovery in the network. We show how to set the forwarding probability based on the region and the network density both by theoretical analysis and by extensive simulations. Our simulations show that the number of messages generated using this approach is much less than the simple global gossiping method, which already saves many messages compared with global flooding. We expect that the improvement should be even more significant in larger networks.

REFERENCES

• 1: 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
• 2: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 3: Gruia Calinescu , Ion I. Mandoiu , Alexander Zelikovsky, Symmetric Connectivity with Minimum Power Consumption in Radio Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.119-130, August 25-30, 2002
• 4: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, The Power Range Assignment Problem in Radio Networks on the Plane, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.651-660, February 01, 2000
• 5: {5} P. Gupta and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks, in: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, eds. W.M. McEneaney, G. Yin and Q. Zhang (1998).
• 6: {6} J. Monks, V. Bharghavan and W.-M Hwu, A power controlled multiple access protocol for wireless packet networks, in: IEEE INFOCOM (2001).
• 7: {7} M. Sanchez, P. Manzoni and Z. Haas, Determination of critical transmission range in ad-hoc networks, in: Multiaccess, Mobility and Teletraffic for Wireless Communications (MMT'99) (1999).
• 8: {8} M. Bahramgiri, M.T. Hajiaghayi and V.S. Mirrokni, Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks, in: Proc. of the 11th Annual IEEE Internat. Conf. on Computer Communications and Networks (ICCCN) (2002) pp. 392-397.
• 9: {9} L. Hu, Topology control for multihop packet radio networks, IEEE Transactions on Communications 41(10) (1993).
• 10: {10} X.-Y. Li, P.-J. Wan, Y. Wang and O. Frieder, Sparse power efficient topology for wireless networks, Journal of Parallel and Distributed Computing (2002) to appear; preliminary version appeared in: ICCCN (2001).
• 11: {11} X.-Y. Li, G. Calinescu, P.-J. Wan and Y. Wang, Localized delaunay triangulation with application in wireless ad hoc networks, IEEE Transactions on Parallel and Distributed Systems (2003); short version appeared in: IEEE INFOCOM (2002).
• 12: {12} X.-Y. Li, G. Calinescu and P.-J. Wan, Distributed construction of planar spanner and routing for ad hoc wireless networks, in: 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3 (2002).
• 13: {13} R. Ramanathan and R. Rosales-Hain, Topology control of multihop wireless networks using transmit power adjustment, in: IEEE INFOCOM (2000).
• 14: {14} R. Wattenhofer, L. Li, P. Bahl and Y.-M. Wang, Distributed topology control for wireless multihop ad-hoc networks, in: IEEE INFOCOM'01 (2001).
• 15: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 16: Ivan Stojmenovic , Xu Lin, Power-Aware Localized Routing in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1122-1133, November 2001 [doi>10.1109/71.969123]
• 17: {17} J. Wu, F. Dai, M. Gao and I. Stojmenovic, On calculating poweraware connected dominating sets for efficient routing in ad hoc wireless networks, IEEE/KICS Journal of Communication and Networks 4(1) (2002) 59-70.
• 18: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 19: {19} B. Das and V. Bharghavan, Routing in ad-hoc networks using minimum connected dominating sets, in: 1997 IEEE Internat. Conf. on Communications (ICC'97), Vol. 1 (1997) pp. 376-380.
• 20: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 21: {21} D.B. Johnson and D.A. Maltz, Dynamic source routing in ad hoc wireless networks, in: Mobile Computing, eds. Imielinski and Korth, Vol. 353 (Kluwer Academic, Dordrecht, 1996).
• 22: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 23: Young Ko , Vaidya Nitin, Using Location Information to Improve Routing in Ad Hoc Networks, Texas A & M University, College Station, TX, 1997
• 24: {24} Z. Haas, J. Halpern and L. Li, Gossip-based ad hoc routing, in: IEEE INFOCOM (2002).
• 25: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 26: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 27: {27} C. Perkins, Ad-hoc on-demand distance vector routing, in: MILCOM '97 (November 1997).
• 28: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 29: {29} P. Sinha, R. Sivakumar and V. Bharghavan, CEDAR: Core extraction distributed ad hoc routing algorithm, IEEE Journal on Selected Areas in Communications 17(8) (1999) 1454-1465.
• 30: {30} P. Sinha, R. Sivakumar and V. Bharghavan, Enhancing ad hoc routing with dynamic virtual infrastructures, in: Proc. of IEEE INFOCOM 2001, Vol. 3 (2001) pp. 1763-1772.
• 31: {31} J. Wu and H. Li, A dominating-set-based routing scheme in ad hoc wireless networks, Telecommunication Systems (Special Issue on Wireless Networks) 3 (2001) 63-84.
• 32: {32} M. Joa-Ng and I.-T. Lu, A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks, IEEE Journal on Selected Areas in Communications 17(8) (1999) 1415-1425.
• 33: {33} E. Royer and C. Toh, A review of current routing protocols for adhoc mobile wireless networks, IEEE Personal Communications (April 1999).
• 34: S. Ramanathan , Martha Steenstrup, A survey of routing techniques for mobile communications networks, Mobile Networks and Applications, v.1 n.2, p.89-104, Oct. 1996 [doi>10.1007/BF01193330]
• 35: {35} M. Mauve, J. Widmer and H. Harenstein, A survey on position-based routing in mobile ad hoc networks, IEEE Network Magazine 15(6) (2001) 30-39.
• 36: {36} P. Hall, On continuum percolation, The Annals of Probability 13(4) (1985).
• 37: {37} R. Meester and R. Roy, Continuum Percolation (Cambridge Univ. Press, Cambridge, 1996).
• 38: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 39: Zygmunt J. Haas , Ben Liang, Ad Hoc mobility management with uniform quorum systems, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.228-240, April 1999 [doi>10.1109/90.769770]
• 40: {40} I. Stojmenovic, A routing strategy and quorum based location update scheme for ad hoc wireless networks, Technical Report TR-99-09, Computer Science, SITE, University of Ottawa (1999).
• 41: Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999 [doi>10.1023/A:1019186624837]
• 42: {42} P.-J. Wan, K.M. Alzoubi and O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, in: INFOCOM (2002).
• 43: K. Alzoubi , P.-J. Wan , O. Frieder, New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297, January 07-10, 2002
• 44: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in 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.513820]
• 45: {45} K.N. Amouris, S. Papavassiliou and M. Li, A position based multizone routing protocol for wide area mobile ad-hoc networks, in: Proc. of the 49th IEEE Vehicular Technology Conf. (1999) pp. 1365-1369.
• 46: Gruia Călinescu , Ion Măndoiu , Peng-Jun Wan , Alexander Zelikovsky, Selecting forwarding neighbors in wireless Ad Hoc networks, Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, p.34-43, July 2001, Rome, Italy [doi>10.1145/381448.381453]
• 47: {47} M. Penrose, The longest edge of the random minimal spanning tree, Annals of Applied Probability 7 (1997) 340-361.
• 48: {48} X.-Y. Li, Y. Wang, C.-W. Yi, P.-J. Wan and O. Frieder, Robust wireless ad hoc networks, in: IEEE ICC (2003) accepted for publication.
• 49: {49} P.-J. Wan, C.-W. Yi, X.-Y. Li, Y. Wang and O. Frieder, Asymptotic distribution of critical transmission range for k -connectivity in wireless ad hoc networks (2002) submitted for publication.
• 50: {50} B. Bollobás, Random Graphs (Cambridge Univ. Press, Cambrige, 2001).
• 51: {51} H. Dette and N. Henze, Some peculiar boundary phenomena for extremes of rth nearest neighbor links, Statistics & Probability Letters 10 (1990) 381-390.
• 52: {52} M. Penrose, Extremes for the minimal spanning tree on normally distributed points, Advances in Applied Probability 30 (1998) 628-639.
• 53: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 54: {54} M. Penrose, A strong law for the longest edge of the minimal spanning tree, Annals of Probability 27 (1999) 246-260.
• 55: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
• 56: {56} C. Cooper and A. Frieze, On the connectivity of random kth nearest neighbour graphs, Combinatorics, Probability and Computing 4 (1995) 343-362.
• 57: {57} M. Grossglauser and D. Tse, Mobility increases the capacity of ad-hoc wireless networks, in: INFOCOMM, Vol. 3 (2001) pp. 1360-1369.
• 58: {58} P. Gupta and P. Kumar, Capacity of wireless networks, Technical Report University of Illinois, Urbana-Champaign (1999).
• 59: {59} O.D. Patrick, Connectivity in ad-hoc and hybrid networks, in: IEEE INFOCOM (2002).
• 60: Paolo Santi , Douglas M. Blough, An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.89-102, June 23-26, 2002
• 61: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 62: Tamás Lukovszki, New Results of Fault Tolerant Geometric Spanners, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.193-204, August 11-14, 1999

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Performance, Reliability

Keywords:
fault tolerance, gossip, routing, wireless ad hoc networks