An Improved Greedy Routing Algorithm for Grid using Pheromone-Based Landmarks

Authors: Lada-On Lertsuwanakul, Herwig Unger

Abstract:

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.

Keywords: Routing algorithm, Small-World network, Ant Colony Optimization, and Peer-to-peer System.

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

References:

[1] C. Martel and V. Nguyen, "Analyzing Kleinberg-s (and other) Smallworld models", Proc. 23rd ACM symposium on Principles of distributed computing, St. John-s, Newfoundland, Canada, pp. 179-188, 2004.
[2] D. Berg, P. Sukjit, and H. Unger, "Grid Generation in Decentralized Systems", Proceeding of IDNS Conference, Klagenfurt, Austria, 2009.
[3] D. Watts and S. Strogatz, "Collective dynamics of small-world networks", Nature 393, pp.440-442, 1998.
[4] E. Michlmayr, "Ant Algorithms for Search in Unstructured Peer-to-Peer Networks", 22nd International Conference on Data Engineering Workshops (ICDEW-06), pp. x142, 2006.
[5] E.K. Lua, J. Crowcroft, M. Pias, R. Scharma, and S. Lim, "A Survey and Comparison of Peer-to-Peer Overlay Network Schemes", IEEE Communications Survey and Tutorial, March, 2004.
[6] F. Zou, Y. Li, L. Zhang, F. Ma, and M. Li, "A Novel Approach for Constructing Small World in Structured P2P Systems" , LNCS, Vol. 3251, pp. 807-810, 2004.
[7] G. Di Caro and M. Dorigo, "AntNet: Distributed Stigmergetic Control for Communications Networks", Journal of Artificial Intelligence Research, Vol. 9, pp. 317-365, 1998.
[8] J.Kleinberg, "The small-world phenomenon: an algorithm perspective", Proceeding of the Thirty-Second Annual ACM Symposium on theory of Computing (STOC-00), New York, pp.163-170, 2000.
[9] K.M. Sim and W.H. Sun, "Ant colony optimization for routing and loadbalancing: survey and new directions", IEEE Transactions on Systems, Man and Cybernetics, Part A, Vol. 33, No. 5., pp. 560-572, 2003.
[10] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26(1):29-41, 1996.
[11] M. Naor and U. Wieder, "Know the Neighbor-s Neighbor: Better Routing for Skip-Graphs and Small Worlds", LNCS, Vol. 3279, pp. 269- 277, 2005.
[12] M. Rojas, H. Unger, and H. Coltzau, "Self-Balanced and Self-Adaptive Routes in Unstructured P2P Networks", 2nd International Conference on Systems (ICONS'07), IEEE Computer Society, France, 2007.
[13] The Tech FAQ, "What is HSV?", Retrieved September 10, 2009, from http://www.tech-faq.com/hsv.shtml