Randomized AB-Face-AB Routing Algorithms in Mobile Ad Hoc Networks

  • Thomas Fevens
  • Alaa Eddien Abdallah
  • Badr Naciri Bennani
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


One common design for routing protocols in mobile ad hoc networks is to use positioning information. We combine the class of randomized position-based routing strategies called AB (Above-Below) algorithms with face routing to form AB:Face2:AB routing algorithms, a new class of hybrid routing algorithms in mobile ad hoc networks. Our experiments on unit disk graphs, and their associated Yao sub-graphs and Gabriel sub-graphs, show that the delivery rates of the AB:Face2:AB algorithms are significantly better than either class of routing algorithms alone when routing is subject to a threshold count beyond which the packet is dropped. The best delivery rates were obtained on the Yao sub-graph. With the appropriate choice of threshold, on non-planar graphs, the delivery rates are equivalent to those of face routing (with no threshold) while, on average, discovering paths to their destinations that are several times shorter.


Mobile adhoc networks randomized routing position-based routing 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Basagni, S., Chlamtac, I., Syrotiuk, V., Woodward, B.: A distance routing effect algorithm for mobility (DREAM). In: Proc. of 4th ACM/IEEE Conference on Mobile Computing and Networking (Mobicom 1998), pp. 76–84 (1998)Google Scholar
  2. 2.
    Barrière, L., Fraigniaud, P., Narayanan, L., Opatrny, J.: Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wireless Communications and Mobile Computing Journal 3, 141–153 (2003)CrossRefGoogle Scholar
  3. 3.
    Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 609–616 (2001)Google Scholar
  4. 4.
    Bose, P., Morin, P.: Online routing in triangulations. In: Proc. of 10th Annual Inter. Symposium on Algorithms and Computation (ISAAC 1999), pp. 113–122 (1999)Google Scholar
  5. 5.
    Jain, R., Puri, A., Sengupta, R.: Geographical routing using partial information for wireless ad hoc networks. IEEE Personal Comm. Magazine 8, 48–57 (2001)CrossRefGoogle Scholar
  6. 6.
    Giordano, S., Stojmenovic, I., Blazevic, L.: Position based routing algorithms for ad hoc networks: A taxonomy. In: Cheng, X., Huang, X., Du, D. (eds.) Ad Hoc Wireless Networking. Kluwer, Dordrecht (2003)Google Scholar
  7. 7.
    Mauve, M., Widmer, J., Hartenstein, H.: A survey of position-based routing in mobile ad-hoc networks. IEEE Network Magazine 15, 30–39 (2001)CrossRefGoogle Scholar
  8. 8.
    Finn, G.: Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISU/RR-87-180, USC ISI, Marina del Ray, CA (1987)Google Scholar
  9. 9.
    Stojmenovic, I., Lin, X.: Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Transactions on Parallel and Distributed Systems 12, 1023–1032 (2001)CrossRefGoogle Scholar
  10. 10.
    Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proc. of Canadian Conf. on Computational Geometry (CCCG 1999), pp. 51–54 (1999)Google Scholar
  11. 11.
    Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proc. of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DAILM 2002) (2002)Google Scholar
  12. 12.
    Ansari, S., Narayanan, L., Opatrny, J.: A generalization of face routing to some non-planar networks. In: Proc. of Mobiquitous (2005)Google Scholar
  13. 13.
    Datta, S., Stojmenovic, I., Wu, J.: Internal node and shortcut based routing with guaranteed delivery in wireless networks. Cluster Computing 5, 169–178 (2002)CrossRefGoogle Scholar
  14. 14.
    Stojmenovic, I., Datta, S.: Power and cost aware localized routing with guaranteed delivery in wireless networks. In: Proc. Seventh IEEE Symposium on Computers and Communications ISCC, Taormina, Sicily, Italia, pp. 31–36 (2002)Google Scholar
  15. 15.
    Karp, B., Kung, H.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proc. of 6th ACM Conference on Mobile Computing and Networking, Mobicom 2000 (2000)Google Scholar
  16. 16.
    Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: Of theory and practice. In: Proc. of Principles of Distributed Comp. 2003 (2003)Google Scholar
  17. 17.
    Fevens, T., Haque, I., Narayanan, L.: A class of randomized routing algorithms in mobile ad hoc networks. In: Proc. of 1st Algorithms for Wireless and Ad-hoc Networks, A-SWAN (2004)Google Scholar
  18. 18.
    Gabriel, K., Sokal, R.: A new statistical approach to geographic variation analysis. Systematic Zoology 18, 259–278 (1969)CrossRefGoogle Scholar
  19. 19.
    Bose, P., Gudmundsson, J., Morin, P.: Ordered theta graphs. Computational Geometry: Theory and Applications 28, 11–18 (2004)zbMATHMathSciNetGoogle Scholar
  20. 20.
    Bose, P., Devroye, L., Evans, W., Kirkpatrick, D.: On the spanning ratio of gabriel graphs and beta-skeletons. In: Proceedings of the Latin American Theoretical Infocomatics, LATIN (2002)Google Scholar
  21. 21.
    Yao, A.C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Computing 11, 721–736 (1982)zbMATHCrossRefGoogle Scholar
  22. 22.
    Li, X.Y., Wan, P.J., Wang, Y.: Power efficient and sparse spanner for wireless ad hoc networks. In: Proc. of IEEE Int. Conf. on Computer Communications and Networks (ICCCN 2001), pp. 564–567 (2002)Google Scholar
  23. 23.
    Yamazaki, K., Sezaki, K.: The proposal of geographical routing protocols for location-aware services. Electronics and Communications in Japan 87 (2004)Google Scholar
  24. 24.
    Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-hoc networks beyond unit disk graphs. In: Proc. of the 2003 joint workshop on the found. of mobile comput., pp. 69–78 (2003)Google Scholar
  25. 25.
    Bose, P., Maheshwari, A., Narasimhan, G., Smid, M., Zeh, N.: Approximating geometric bottleneck shortest paths. Comp. Geom. Theory Appl. 29, 233–249 (2004)zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Thomas Fevens
    • 1
  • Alaa Eddien Abdallah
    • 1
  • Badr Naciri Bennani
    • 1
  1. 1.Department of Computer Science and Software EngineeringConcordia UniversityMontréalCanada

Personalised recommendations