JRM Vol.19 No.4 pp. 459-465
doi: 10.20965/jrm.2007.p0459


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

January 11, 2007
April 16, 2007
August 20, 2007
small world, ad hoc network, local negotiation

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.

Cite this article as:
Daisuke Kurabayashi, Tomohiro Inoue, Akira Yajima, and
and Tetsuro Funato, “Emergence of a Small-World Like Communication Network Through Local Ad Hoc Negotiation,” J. Robot. Mechatron., Vol.19, No.4, pp. 459-465, 2007.
Data files:
  1. [1] A. L. Barabashi, “The new science of networks,” Perseus Books Group, 2002.
  2. [2] D. Watts, “Small Worlds,” Princeton U. Press, 1999.
  3. [3] R. Choen, D. ben Avraham, and S. Hvlin, “Percolation critical exponents in scale-free networks,” Physical Review E, 66, 015104, 2002.
  4. [4] R. Albert, H. Jeong, and A. L. Barabashi, “Error and attack tolerance of complex network,” Nature, 406, pp. 378-382, 2000.
  5. [5] S. Milgram, “The Small World – World Problem,” Phycology Today, Vol.2, pp. 60-67, 1967.
  6. [6] M. Marchirori and V. Latora, “Harmony in the Small-world,” Physica A, Vol.285, pp. 539-546, 2000.
  7. [7] N. Mathias and V. Gopal, “Small Worlds: How and Why,” Physical Review E, Vol.63, No.2, 2001.
  8. [8] J. M. Montoya and R. V. Sole, “Small World Patterns in Food Webs,” 2000.
  9. [9] L. Adamic, “The Small World Web,” Proc. ECDL99, pp. 443-452, 1999.
  10. [10] D. Watts and S. Strogatz, “Collective Dynamics of Small-world Networks,” Nature, Vol.393, pp. 440-442, 1998.
  11. [11] B. Bollobas, “Random Graphs,” Academic Press, 1999.
  12. [12] M. E. J. Newman and M. Giravan, “Finding and evaluating community structure in networks,” Physical Review E, 69, 026113, 2004.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 01, 2021