{"title":"Cluster Based Ant Colony Routing Algorithm for Mobile Ad-Hoc Networks","authors":"Alaa E. Abdallah, Bajes Y. Alskarnah","volume":92,"journal":"International Journal of Electronics and Communication Engineering","pagesStart":1386,"pagesEnd":1391,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/9999119","abstract":"<p>Ant colony based routing algorithms are known to<br \/>\r\ngrantee the packet delivery, but they suffer from the huge overhead<br \/>\r\nof control messages which are needed to discover the route. In this<br \/>\r\npaper we utilize the network nodes positions to group the nodes<br \/>\r\nin connected clusters. We use clusters-heads only on forwarding<br \/>\r\nthe route discovery control messages. Our simulations proved that<br \/>\r\nthe new algorithm has decreased the overhead dramatically without<br \/>\r\naffecting the delivery rate.<\/p>\r\n","references":"[1] A.E. Abdallah, T. Fevens, and J. Opatrny. High delivery rate routing algorithms\r\nfor 3d ad hoc network. Computer Communications, 31(4):807\u2013\r\n817, 2008.\r\n[2] A.E. Abdallah, T. Fevens, and J. Opatrny. 3d local algorithm for\r\ndominating sets of unit disk graphs. In Proceedings of the Canadian\r\nConference on Computational Geometry (CCCG), pages 35\u201338,\r\nWinnipeg-Manitoba, August 2010.\r\n[3] A.E. Abdallah, T. Fevens, and J. Opatrny. 3d local algorithm for\r\ndominating sets of unit disk graphs. Ad Hoc Sensor Wireless Networks,\r\n19(1-2):21\u201341, 2013.\r\n[4] A.E. Abdallah, T. Fevens, J. Opatrny, and I. Stojmenovic. Poweraware\r\n3d position-based routing algorithms using adjustable transmission\r\nranges for ad hoc and sensor networks. Ad Hoc Networks, 8(1):15\u2013\r\n29, 2010.\r\n[5] K. Alzoubi, X. Li, Y. Wang, P. Wan, and O. Frieder. Geometric spanners\r\nfor wireless ad hoc networks. IEEE Transactions on Parallel and\r\nDistributed Systems, 14(4):408\u2013421, 2003.\r\n[6] K. Alzoubi, P. Wan, and O. Frieder. Distributed heuristics for connected\r\ndominating sets in wireless ad hoc networks. Journal of Communications\r\nNetworks, 4(1):141\u2013149, 2002.\r\n[7] K. Alzoubi, P. Wan, and O. Frieder. Message-optimal connecteddominating-\r\nset construction for routing in mobile ad hoc networks. In\r\nProc. of the Third ACM international Symp. Mobile Ad Hoc Networking\r\nand Computing (MobiHoc 02), pages 157\u2013164, Lausanne, June 2002.\r\n[8] L. Barri`ere, P. Fraigniaud, L. Narayanan, and J. Opatrny. Robust\r\nposition-based routing in wireless ad hoc networks with irregular\r\ntransmission ranges. Wireless Communications and Mobile Computing\r\nJournal, 3(2):141\u2013153, 2003.\r\n[9] S. Basagni, I. Chlamtac, and V. Syrotiuk. Dynamic source routing\r\nfor ad hoc networks using the global positioning system. In\r\nProc. of the IEEE Wireless Communications and Networking Conference(\r\nWCNC\u201999), pages 21\u201324, New Orleans LA, September 1999.\r\n[10] S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward. A distance\r\nrouting effect algorithm for mobility (DREAM). In Proc. of the 4th\r\nannual ACM\/IEEE international conference on Mobile computing and\r\nnetworking (MOBICOM), pages 76\u201384, Dallas, 1998.\r\n[11] P. Bose and P. Morin. Online routing in triangulations. In 10th Annual\r\nInternational Symposium on Algorithms and Computation (ISAAC \u201999),\r\nvolume 1741 of LNCS, pages 113\u2013122, India, December 1999.\r\n[12] P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with\r\nguaranteed delivery in ad hoc wireless networks. Wireless Networks\r\njournal, 7(6):609\u2013616, 2001.\r\n[13] J. Broch, D. Maltz, D. Johnson, Y. Hu, and J. Jetcheva. A performance\r\ncomparison of multi-hop wireless ad hoc network routing protocols.\r\nIn Proc. of the Fourth Annual ACM\/IEEE International Conference on\r\nMobile Computing and Networking, pages 85\u201397, Dallas TX, October\r\n1998.\r\n[14] S. Capkun, M. Hamdi, and J.-P. Hubaux. Gps-free positioning in mobile\r\nad-hoc networks. Cluster Computing Journal, 5(2):118\u2013124, 2002.\r\n[15] G. Caro and M. Dorigo. Ant colonies for adaptive routing in packetswitched\r\ncommunications networks. In Proceedings of the 5th ACM\r\nInternational Conference on Parallel Problem Solving from Nature,\r\npages 673\u2013682, 1998.\r\n[16] I. Chlamtac, M. Conti, and J. Liu. Mobile ad hoc networking: Imperative\r\nand challenges. Ad Hoc Network Journal, 1(1):13\u201364, 2003.\r\n[17] V. Chvatal. A greedy heuristic for the set covering problem. Math.\r\nOper. Res. 4, pages 233\u2013235, 1979.\r\n[18] T. Clausen and P. Jacquet. Optimized link state routing protocol (OLSR).\r\nIn RFC 3626, IETF Network Working Group, October 2003.\r\n[19] D. Caro Gianni Gambardella Dorigo, Marco and L. Maria. Ant\r\nalgorithms for discrete optimization. Artif. Life, 1999.\r\n[20] Caro Gianni Gambardella Ducatelle, Frederick and L. Maria. Ant\r\nAgents for Hybrid Multipath Routing in Mobile Ad Hoc Networks. In\r\nProceedings of the conference on Wireless On-demand Network Systems\r\nand Services, pages 44\u201353, Swizerland, January 2005.\r\n[21] T. Fevens, A.E. Abdallah, and B. Bennani. Randomized ab-face-ab\r\nrouting algorithms in mobile ad hoc network. In 4th International\r\nConference on AD-HOC Networks and Wireless, volume 3738 of LNCS,\r\npages 43\u201356, Mexico, October 2005.\r\n[22] F. Ducatelle G. Caro and L. Gambardella. Anthocnet: An adaptive\r\nnature-inspired algorithm for routing in mobile ad hoc networks. Self-\r\nOrganisation in Mobile Networking,, 16(5):443\u2013455, 2005.\r\n[23] S. Giordano, I. Stojmenovic, and L. Blazevic. Postion based routing\r\nalgorithms for ad hoc networks for ad hoc networks: A taxonomy. In\r\nAd hoc wireless Networking (ed. X. Cheng, X. Huang, and D.Z. Du),\r\nKluwer, pages 103\u2013136, July 2003.\r\n[24] J. Hightower and Borriello G. Location systems for ubiquitous computing.\r\nComputer, 34(8):57\u201366, 2001.\r\n[25] D. Johnson. Approximation algorithms for combinatorial problems.\r\nJournal of Computer and System Sciences, pages 256\u2013278, 1974.\r\n[26] D. Johnson and D. Malts. Dynamic source routing in ad hoc wireless\r\nnetworks. In Mobile Computing (ed. T. Imielinski and H. Korth), chapter\r\n5, pages 153\u2013181. Kluwer Academic Publishers, 1996.\r\n[27] S. Kamali and J. Opatrny. A position based ant colony routing algorithm\r\nfor mobile ad-hoc networks. JOURNAL OF NETWORKS, 3(4):31\u201341,\r\n2008.\r\n[28] E. Kaplan. Understanding GPS. Artech house, 1996.\r\n[29] Y. Ko and N. Vaidya. Location-aided routing (LAR) in mobile ad\r\nhoc networks. ACM\/Baltzer Wireless Networks (WINET), 6(4):307\u2013321,\r\n2000.\r\n[30] F. Kuhn, R. Wattenhofer, and A. Zollinger. Ad-hoc networks beyond unit\r\ndisk graphs. In Proc. of the 2003 joint workshop on the foundation of\r\nmobile computing (DIALM-POMC), pages 69\u201378, San Diego, September\r\n2003.\r\n[31] J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris. A scalable\r\nlocation service for geographic ad-hoc routing. In Proc. of the 6th\r\nACM International Conference on Mobile Computing and Networking\r\n(MobiCom), pages 120\u2013130, Boston, August 2000.\r\n[32] U. Sorges M. Gunes and I. Bouazizi. Ara - the ant-colony based routing\r\nalgorithm for manets. In Proceedings of the International Conference on\r\nParallel Processing Workshops, pages 79\u201389, Vancouver, August 2002.\r\n[33] M. Mauve, J. Widmer, and H. Hartenstein. A survey of position-based\r\nrouting in mobile ad-hoc networks. IEEE Network Magazine, 15(6):30\u2013\r\n39, 2001.\r\n[34] C. Perkins and P. Bhagwat. Highly dynamic destination sequenced\r\ndistance-vector routing (DSDV) for mobile computers. In Proc. of the\r\nSIGCOMM, Conference on Communications Architectures, Protocols\r\nand Applications, pages 234\u2013244, London, September 1994.\r\n[35] C. Perkins and E. Royer. Ad hoc on-demand distance vector routing.\r\nIn Proc. of the 2nd IEEE Workshop on Mobile Computing System and\r\nApplication(WMCSA), pages 90\u2013100, San Juan, February 1999.\r\n[36] E. Royer and C. Toh. A review of current routing protocols for ad hoc\r\nmobile wireless networks. IEEE Personal Communications, 6(4):46\u201355,\r\n1999.\r\n[37] P. Slavik. A tight analysis of the greedy algorithm for set cover. In\r\nProc. of the 28th ACM Symposium on Theory of Computing (STOC),\r\npages 435\u2013441, 1996.\r\n[38] I. Stojmenovic. Location updates for efficient routing in ad hoc networks.\r\nIn Handbook on Wireless Networks and Mobile Computing, pages 451\u2013\r\n471, 2002.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 92, 2014"}