Cluster Based Ant Colony Routing Algorithm for Mobile Ad-Hoc Networks

Authors: Alaa E. Abdallah, Bajes Y. Alskarnah

Abstract:

Ant colony based routing algorithms are known to grantee the packet delivery, but they suffer from the huge overhead of control messages which are needed to discover the route. In this paper we utilize the network nodes positions to group the nodes in connected clusters. We use clusters-heads only on forwarding the route discovery control messages. Our simulations proved that the new algorithm has decreased the overhead dramatically without affecting the delivery rate.

Keywords: Ant colony-based routing, position-based routing, MANET.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1094427

References:

[1] A.E. Abdallah, T. Fevens, and J. Opatrny. High delivery rate routing algorithms for 3d ad hoc network. Computer Communications, 31(4):807– 817, 2008.
[2] A.E. Abdallah, T. Fevens, and J. Opatrny. 3d local algorithm for dominating sets of unit disk graphs. In Proceedings of the Canadian Conference on Computational Geometry (CCCG), pages 35–38, Winnipeg-Manitoba, August 2010.
[3] A.E. Abdallah, T. Fevens, and J. Opatrny. 3d local algorithm for dominating sets of unit disk graphs. Ad Hoc Sensor Wireless Networks, 19(1-2):21–41, 2013.
[4] A.E. Abdallah, T. Fevens, J. Opatrny, and I. Stojmenovic. Poweraware 3d position-based routing algorithms using adjustable transmission ranges for ad hoc and sensor networks. Ad Hoc Networks, 8(1):15– 29, 2010.
[5] K. Alzoubi, X. Li, Y. Wang, P. Wan, and O. Frieder. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 14(4):408–421, 2003.
[6] K. Alzoubi, P. Wan, and O. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications Networks, 4(1):141–149, 2002.
[7] K. Alzoubi, P. Wan, and O. Frieder. Message-optimal connecteddominating- set construction for routing in mobile ad hoc networks. In Proc. of the Third ACM international Symp. Mobile Ad Hoc Networking and Computing (MobiHoc 02), pages 157–164, Lausanne, June 2002.
[8] L. Barri`ere, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. Wireless Communications and Mobile Computing Journal, 3(2):141–153, 2003.
[9] S. Basagni, I. Chlamtac, and V. Syrotiuk. Dynamic source routing for ad hoc networks using the global positioning system. In Proc. of the IEEE Wireless Communications and Networking Conference( WCNC’99), pages 21–24, New Orleans LA, September 1999.
[10] S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward. A distance routing effect algorithm for mobility (DREAM). In Proc. of the 4th annual ACM/IEEE international conference on Mobile computing and networking (MOBICOM), pages 76–84, Dallas, 1998.
[11] P. Bose and P. Morin. Online routing in triangulations. In 10th Annual International Symposium on Algorithms and Computation (ISAAC ’99), volume 1741 of LNCS, pages 113–122, India, December 1999.
[12] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks journal, 7(6):609–616, 2001.
[13] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. In Proc. of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pages 85–97, Dallas TX, October 1998.
[14] S. Capkun, M. Hamdi, and J.-P. Hubaux. Gps-free positioning in mobile ad-hoc networks. Cluster Computing Journal, 5(2):118–124, 2002.
[15] G. Caro and M. Dorigo. Ant colonies for adaptive routing in packetswitched communications networks. In Proceedings of the 5th ACM International Conference on Parallel Problem Solving from Nature, pages 673–682, 1998.
[16] I. Chlamtac, M. Conti, and J. Liu. Mobile ad hoc networking: Imperative and challenges. Ad Hoc Network Journal, 1(1):13–64, 2003.
[17] V. Chvatal. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, pages 233–235, 1979.
[18] T. Clausen and P. Jacquet. Optimized link state routing protocol (OLSR). In RFC 3626, IETF Network Working Group, October 2003.
[19] D. Caro Gianni Gambardella Dorigo, Marco and L. Maria. Ant algorithms for discrete optimization. Artif. Life, 1999.
[20] Caro Gianni Gambardella Ducatelle, Frederick and L. Maria. Ant Agents for Hybrid Multipath Routing in Mobile Ad Hoc Networks. In Proceedings of the conference on Wireless On-demand Network Systems and Services, pages 44–53, Swizerland, January 2005.
[21] T. Fevens, A.E. Abdallah, and B. Bennani. Randomized ab-face-ab routing algorithms in mobile ad hoc network. In 4th International Conference on AD-HOC Networks and Wireless, volume 3738 of LNCS, pages 43–56, Mexico, October 2005.
[22] F. Ducatelle G. Caro and L. Gambardella. Anthocnet: An adaptive nature-inspired algorithm for routing in mobile ad hoc networks. Self- Organisation in Mobile Networking,, 16(5):443–455, 2005.
[23] S. Giordano, I. Stojmenovic, and L. Blazevic. Postion based routing algorithms for ad hoc networks for ad hoc networks: A taxonomy. In Ad hoc wireless Networking (ed. X. Cheng, X. Huang, and D.Z. Du), Kluwer, pages 103–136, July 2003.
[24] J. Hightower and Borriello G. Location systems for ubiquitous computing. Computer, 34(8):57–66, 2001.
[25] D. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, pages 256–278, 1974.
[26] D. Johnson and D. Malts. Dynamic source routing in ad hoc wireless networks. In Mobile Computing (ed. T. Imielinski and H. Korth), chapter 5, pages 153–181. Kluwer Academic Publishers, 1996.
[27] S. Kamali and J. Opatrny. A position based ant colony routing algorithm for mobile ad-hoc networks. JOURNAL OF NETWORKS, 3(4):31–41, 2008.
[28] E. Kaplan. Understanding GPS. Artech house, 1996.
[29] Y. Ko and N. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. ACM/Baltzer Wireless Networks (WINET), 6(4):307–321, 2000.
[30] F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc networks beyond unit disk graphs. In Proc. of the 2003 joint workshop on the foundation of mobile computing (DIALM-POMC), pages 69–78, San Diego, September 2003.
[31] J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris. A scalable location service for geographic ad-hoc routing. In Proc. of the 6th ACM International Conference on Mobile Computing and Networking (MobiCom), pages 120–130, Boston, August 2000.
[32] U. Sorges M. Gunes and I. Bouazizi. Ara - the ant-colony based routing algorithm for manets. In Proceedings of the International Conference on Parallel Processing Workshops, pages 79–89, Vancouver, August 2002.
[33] M. Mauve, J. Widmer, and H. Hartenstein. A survey of position-based routing in mobile ad-hoc networks. IEEE Network Magazine, 15(6):30– 39, 2001.
[34] C. Perkins and P. Bhagwat. Highly dynamic destination sequenced distance-vector routing (DSDV) for mobile computers. In Proc. of the SIGCOMM, Conference on Communications Architectures, Protocols and Applications, pages 234–244, London, September 1994.
[35] C. Perkins and E. Royer. Ad hoc on-demand distance vector routing. In Proc. of the 2nd IEEE Workshop on Mobile Computing System and Application(WMCSA), pages 90–100, San Juan, February 1999.
[36] E. Royer and C. Toh. A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, 6(4):46–55, 1999.
[37] P. Slavik. A tight analysis of the greedy algorithm for set cover. In Proc. of the 28th ACM Symposium on Theory of Computing (STOC), pages 435–441, 1996.
[38] I. Stojmenovic. Location updates for efficient routing in ad hoc networks. In Handbook on Wireless Networks and Mobile Computing, pages 451– 471, 2002.