An Improved Greedy Routing Algorithm For Grid Using Pheromone-Based Landmarks

• Main Authors: Lada-On Lertsuwanakul, Unger, Herwig
• Format: Text
• Language: English
• Published: Zenodo 2009
• Subjects: Routing algorithm; Small-World network; Ant Colony Optimization; and Peer-to-peer System.; Canada; Martel; Rojas; Newfoundland
• Online Access: https://dx.doi.org/10.5281/zenodo.1077116; https://zenodo.org/record/1077116

This paper objects to extend Jon Kleinberg-s research. He introduced the structure of small-world in a grid and shows with a greedy algorithm using only local information able to find route between source and target in delivery time O(log2n). His fundamental model for distributed system uses a two-dimensional grid with longrange random links added between any two node u and v with a probability proportional to distance d(u,v)-2. We propose with an additional information of the long link nearby, we can find the shorter path. We apply the ant colony system as a messenger distributed their pheromone, the long-link details, in surrounding area. The subsequence forwarding decision has more option to move to, select among local neighbors or send to node has long link closer to its target. Our experiment results sustain our approach, the average routing time by Color Pheromone faster than greedy method. : {"references": ["C. Martel and V. Nguyen, \"Analyzing Kleinberg-s (and other) Smallworld\nmodels\", Proc. 23rd ACM symposium on Principles of distributed\ncomputing, St. John-s, Newfoundland, Canada, pp. 179-188, 2004.", "D. Berg, P. Sukjit, and H. Unger, \"Grid Generation in Decentralized\nSystems\", Proceeding of IDNS Conference, Klagenfurt, Austria, 2009.", "D. Watts and S. Strogatz, \"Collective dynamics of small-world\nnetworks\", Nature 393, pp.440-442, 1998.", "E. Michlmayr, \"Ant Algorithms for Search in Unstructured Peer-to-Peer\nNetworks\", 22nd International Conference on Data Engineering\nWorkshops (ICDEW-06), pp. x142, 2006.", "E.K. Lua, J. Crowcroft, M. Pias, R. Scharma, and S. Lim, \"A Survey and\nComparison of Peer-to-Peer Overlay Network Schemes\", IEEE\nCommunications Survey and Tutorial, March, 2004.", "F. Zou, Y. Li, L. Zhang, F. Ma, and M. Li, \"A Novel Approach for\nConstructing Small World in Structured P2P Systems\" , LNCS, Vol.\n3251, pp. 807-810, 2004.", "G. Di Caro and M. Dorigo, \"AntNet: Distributed Stigmergetic Control\nfor Communications Networks\", Journal of Artificial Intelligence\nResearch, Vol. 9, pp. 317-365, 1998.", "J.Kleinberg, \"The small-world phenomenon: an algorithm perspective\",\nProceeding of the Thirty-Second Annual ACM Symposium on theory of\nComputing (STOC-00), New York, pp.163-170, 2000.", "K.M. Sim and W.H. Sun, \"Ant colony optimization for routing and loadbalancing:\nsurvey and new directions\", IEEE Transactions on Systems,\nMan and Cybernetics, Part A, Vol. 33, No. 5., pp. 560-572, 2003.\n[10] M. Dorigo, V. Maniezzo, and A. Colorni, \"Ant System: Optimization by\na Colony of Cooperating Agents\", IEEE Transactions on Systems, Man,\nand Cybernetics - Part B, 26(1):29-41, 1996.\n[11] M. Naor and U. Wieder, \"Know the Neighbor-s Neighbor: Better\nRouting for Skip-Graphs and Small Worlds\", LNCS, Vol. 3279, pp. 269-\n277, 2005.\n[12] M. Rojas, H. Unger, and H. Coltzau, \"Self-Balanced and Self-Adaptive\nRoutes in Unstructured P2P Networks\", 2nd International Conference on\nSystems (ICONS'07), IEEE Computer Society, France, 2007.\n[13] The Tech FAQ, \"What is HSV?\", Retrieved September 10, 2009, from\nhttp://www.tech-faq.com/hsv.shtml"]}