Emergence of a Small-World Like Communication Network Through Local Ad Hoc Negotiation
Daisuke Kurabayashi*, Tomohiro Inoue**, Akira Yajima***,
and Tetsuro Funato*
*Dept. Mechanical and Control Engineering, Tokyo Institute of Technology, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8552, Japan
**Production Development Center, Ishikawajima-Harima Heavy Industries Co., Ltd., 1 Shin-Nakahara-cho, Isogo-ku, Yokohama-shi, Kanagawa 235-8501, Japan
***Human Machine Perception Laboratory, Canon Inc., 30-2 Shimomaruko 3-chome, Ohta-ku, Tokyo 146-8501, Japan
Focusing on an algorithm for realizing a small-world (SW) like ad hoc communication network among autonomous mobile agents, we discuss how the ad hoc network emerges through local negotiation without a central manager. We have started procedures that lend emerging networks the SW property, resulting in effective, low-cost communication. We formulate the expected number of communication links and degrees of agents, verifying the feasibility of our proposal through simulation.
-  A. L. Barabashi, “The new science of networks,” Perseus Books Group, 2002.
-  D. Watts, “Small Worlds,” Princeton U. Press, 1999.
-  R. Choen, D. ben Avraham, and S. Hvlin, “Percolation critical exponents in scale-free networks,” Physical Review E, 66, 015104, 2002.
-  R. Albert, H. Jeong, and A. L. Barabashi, “Error and attack tolerance of complex network,” Nature, 406, pp. 378-382, 2000.
-  S. Milgram, “The Small World – World Problem,” Phycology Today, Vol.2, pp. 60-67, 1967.
-  M. Marchirori and V. Latora, “Harmony in the Small-world,” Physica A, Vol.285, pp. 539-546, 2000.
-  N. Mathias and V. Gopal, “Small Worlds: How and Why,” Physical Review E, Vol.63, No.2, 2001.
-  J. M. Montoya and R. V. Sole, “Small World Patterns in Food Webs,” 2000.
-  L. Adamic, “The Small World Web,” Proc. ECDL99, pp. 443-452, 1999.
-  D. Watts and S. Strogatz, “Collective Dynamics of Small-world Networks,” Nature, Vol.393, pp. 440-442, 1998.
-  B. Bollobas, “Random Graphs,” Academic Press, 1999.
-  M. E. J. Newman and M. Giravan, “Finding and evaluating community structure in networks,” Physical Review E, 69, 026113, 2004.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.
Copyright© 2007 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.