Emergence of a Small-World Like Communication Network Through Local Ad Hoc Negotiation

Daisuke Kurabayashi; Tomohiro Inoue; Akira Yajima; Tetsuro Funato

doi:10.20965/jrm.2007.p0459

single-rb.php

« previous

JRM Vol.19 No.4 pp. 459-465

doi: 10.20965/jrm.2007.p0459

(2007)

Paper:

Views over last 60 days: 439

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

Received:

January 11, 2007

Accepted:

April 16, 2007

Published:

August 20, 2007

Keywords:

small world, ad hoc network, local negotiation

Abstract

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:

D. Kurabayashi, T. Inoue, A. Yajima, and T. 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:

References

[1] A. L. Barabashi, “The new science of networks,” Perseus Books Group, 2002.
[2] D. Watts, “Small Worlds,” Princeton U. Press, 1999.
[3] R. Choen, D. ben Avraham, and S. Hvlin, “Percolation critical exponents in scale-free networks,” Physical Review E, 66, 015104, 2002.
[4] R. Albert, H. Jeong, and A. L. Barabashi, “Error and attack tolerance of complex network,” Nature, 406, pp. 378-382, 2000.
[5] S. Milgram, “The Small World – World Problem,” Phycology Today, Vol.2, pp. 60-67, 1967.
[6] M. Marchirori and V. Latora, “Harmony in the Small-world,” Physica A, Vol.285, pp. 539-546, 2000.
[7] N. Mathias and V. Gopal, “Small Worlds: How and Why,” Physical Review E, Vol.63, No.2, 2001.
[8] J. M. Montoya and R. V. Sole, “Small World Patterns in Food Webs,” 2000.
[9] L. Adamic, “The Small World Web,” Proc. ECDL99, pp. 443-452, 1999.
[10] D. Watts and S. Strogatz, “Collective Dynamics of Small-world Networks,” Nature, Vol.393, pp. 440-442, 1998.
[11] B. Bollobas, “Random Graphs,” Academic Press, 1999.
[12] 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.

[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.

Emergence of a Small-World Like Communication Network Through Local Ad Hoc Negotiation

Daisuke Kurabayashi*, Tomohiro Inoue**, Akira Yajima***, and Tetsuro Funato*

Daisuke Kurabayashi^, Tomohiro Inoue^, Akira Yajima^,
and Tetsuro Funato^*