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

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.

• Alaa E. Abdallah
• Bajes Y. Alskarnah

• Ant colony-based routing
• position-based routing
• MANET.

[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.