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

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.

• Lada-On Lertsuwanakul
• Herwig Unger

• Routing algorithm
• Small-World network
• Ant Colony Optimization
• and Peer-to-peer System.

[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