Conventional proactive routing protocols, due to their inherent nature based on shortest paths, select longer links which are amenable to rapid breakages as nodes move around. In this paper, we propose a novel adaptive probabilistic approach to handle routing information in dense mobile ad hoc networks in a way to improve the proactive routing pertinence as a function of network dynamics. We first propose a new proactive routing framework based on probabilistic decisions and a generic model to compute the existence probabilities of nodes and links. Then, we present a distributed algorithm to collect the cartography of the network. This cartography is used to instantiate the existence probabilities. Conducted simulations show that our proposal yields substantially better routing validity. Nonetheless, it amounts to much longer routes. We proposed then a bounding technique to adapt and overcome this side effect and defined two probabilistic proactive routing variants. Conducted simulations show that our proposed bounded probabilistic proactive routing schemes outperform conventional routing protocols and yield up to 66 percent increase in throughput. 1. Introduction Mobile ad hoc networks (MANETs) are spontaneous networks that do not require any infrastructure for their operations. The task of routing packets from a source to a destination is the sole responsibility of all participating nodes and is distributed among them, where a node can serve as a traffic source, a destination, or a relaying router. All nodes should cooperate, under normal conditions, to fulfill such a requirement. In these networks, nodes and links can appear and disappear spontaneously as a consequence of several facts such as the behavior of users, the depletion of energy resources, but more inherently and subtly the underlying random mobility of the different nodes. These aspects imply a dynamic and randomly evolving topology in both time and space making the routing a real challenging task. A host of routing protocols and algorithms were proposed, though, only very few of them are actually standardized. The standardized routing protocols are classified into reactive and proactive protocols. Reactive protocols, such as DSR [1] and AODV [2], calculate routes only when needed, and as such they are supposed to generate low signaling overhead. Proactive protocols, like the Optimized Link State Routing protocol (OLSR [3]) and the Destination Sequenced Distance Vector routing protocol (DSDV [4]), establish paths for all known source-destination pairs in advance by periodically exchanging
References
[1]
D. B. Johnson, D. A. Maltz, and Y.-C. Hu, “The dynamic source routing protocol for mobile Ad Hoc Networks (DSR),” Internet-Draft. IETF MANET Working Group, 2004.
[2]
C.E. Perkins, E.M. Royer, and I.D. Chakeres, “Ad Hoc On demand distance vector routing protocol,” Internet Draft, MANET Working Group, 2003.
[3]
T. Clausen and P. Jacquet, “Optimized link state routing protocol (OLSR. m inus 0.4em Request for Comment 3626),” MANET Working Group, 2003.
[4]
C.E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” in Proceedings of the ACM Conference on Communications Architectures, Protocols and Applications (SIGCOMM’94), 1999.
[5]
T. Clausen, P. Jacquet, and L. Viennot, “Comparative study of routing protocols for mobile Ad Hoc networks,” in Proceedings of the The 1st Annual Mediterranean Ad Hoc Networking Workshop, 2002.
[6]
J. Novatnack, L. Greenwald, and H. Arora, “Evaluating ad hoc routing protocols with respect to quality of service,” in Proceedings of the IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, (WiMob'05), pp. 205–212, August 2005.
[7]
C. Mbarushimana and A. Shahrabi, “Comparative study of reactive and proactive routing protocols performance in mobile ad hoc networks,” in Proceedings of the 21st International Conference on Advanced Information Networking and ApplicationsWorkshops, (AINAW'07), pp. 679–684, May 2007.
[8]
W.-H. Chung, “Probabilistic analysis of routes on mobile ad hoc networks,” IEEE Communications Letters, vol. 8, no. 8, pp. 506–508, 2004.
[9]
R. Dube, C. D. Rais, K. Y. Wang, and S. K. Tripathi, “Signal stability-based adaptive routing (SSA) for ad hoc mobile networks,” IEEE Personal Communications, vol. 4, no. 1, pp. 36–45, 1997.
[10]
C.-K. Toh, “Associativity-Based Routing for Ad-Hoc Mobile Networks,” Wireless Personal Communications, vol. 4, no. 2, pp. 103–139, 1997.
[11]
M. A. Abid and A. Belghith, “Stability routing with constrained path length for improved routability in dynamic MANETs,” The International Journal of Personnal and Ubiquitous Computing, vol. 15, no. 8, pp. 799–810, 2011.
[12]
R. Beraldi, L. Querzoni, and R. Baldoni, “A hint-based probabilistic protocol for unicast communications in MANETs,” Ad Hoc Networks, vol. 4, no. 5, pp. 547–566, 2006.
[13]
H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli, “Age matters: efficient route discovery in mobile ad hoc networks using encounter ages,” in Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '03), pp. 257–266, Annapolis, Md, USA, June 2003.
[14]
M. Roth and S. Wicker, “Termite: emergent ad-hoc networking,” in Proceedings of The 2nd Mediterranean Workshop on Ad-Hoc Networks, Mehdia, Tunisia, 2003.
[15]
M. A. Abid and A. Belghith, “Period size self tuning to enhance routing in MANETs,” International Journal of Business Data Communications and Networking, vol. 6, no. 4, pp. 21–37, 2010..
[16]
D. Yu, H. Li, and I. Gruber, “Path availability in ad hoc network,” in Proceedings of the 10th International Conference on Telecommunications (ICT'03), vol. 1, pp. 383–387, 2003.
[17]
T. Camp, J. Boleng, and V. Davies, “A survey of mobility models for Ad Hoc network research,” Wireless Communication and Mobile Computing, vol. 2, no. 5, pp. 483–502, 2002.
[18]
H. Zhang and Y.-N. Dong, “A novel path stability computation model for wireless ad hoc networks,” IEEE Signal Processing Letters, vol. 14, no. 12, pp. 928–931, 2007.
[19]
Y. C. Tseng, Y. F. Li, and Y. C. Chang, “On route lifetime in multihop mobile ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 2, no. 4, pp. 366–376, 2003.
[20]
R. Marie, M. Molnar, and H. Idoudi, “A simple automata based model for stable routing in dynamic Ad-Hoc networks,” in Proceedings of the 2nd ACM International Workshop on Performance Monitoring, Measurement, and Evaluation of Heterogeneous Wireless and Wired Network(PM2HW2N '07), Crete Island, Greece, 2007.
[21]
L. Kleinrock, Queueing Systems, vol. 1: Theory, 1975, Wiley Interscience.
[22]
T. H. Cormen, C. E. Leiserson, Ronald L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, Cambridge, Mass, USA, 2nd edition, 2001.
[23]
D. Bertsekas and R. Gallager, Data Networks, Prentice-Hall, Englewood Cliffs, NJ, USA, 1987.
[24]
S. Giordano and I. Stojmenovic, Position-Based Ad Hoc Routes in Ad Hoc Networks, CRC Press, Inc, Boca Raton, FL, USA, 2003.
[25]
D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks,” Telecommunication Systems, vol. 22, no. 1-4, pp. 267–280, 2003.
