Evolutionary construction of geographical networks with nearly optimal robustness and efficient routing properties

Autor: Yukio Hayashi
Rok vydání: 2009
Předmět:
Computational Geometry (cs.CG)
FOS: Computer and information sciences
Statistics and Probability
Physics - Physics and Society
Theoretical computer science
Wireless ad hoc network
Distributed computing
FOS: Physical sciences
Physics and Society (physics.soc-ph)
Computer Science - Networking and Internet Architecture
Geometric networks
Spatial network
Robustness (computer science)
Random geometric graph
Mathematics
Networking and Internet Architecture (cs.NI)
Adaptive quality of service multi-hop routing
Ad hoc wireless distribution service
Condensed Matter Physics
Geometric spanner
Shortcut link
Optimized Link State Routing Protocol
Physics - Data Analysis
Statistics and Probability
Population density
Computer Science - Computational Geometry
Decentralized routing
Wireless ad-hoc communication
Data Analysis
Statistics and Probability (physics.data-an)
Zdroj: Physica A: Statistical Mechanics and its Applications. 388:991-998
ISSN: 0378-4371
DOI: 10.1016/j.physa.2008.11.027
Popis: Robust and efficient design of networks on a realistic geographical space is one of the important issues for the realization of dependable communication systems. In this paper, based on a percolation theory and a geometric graph property, we investigate such a design from the following viewpoints: 1) network evolution according to a spatially heterogeneous population, 2) trimodal low degrees for the tolerant connectivity against both failures and attacks, and 3) decentralized routing within short paths. Furthermore, we point out the weakened tolerance by geographical constraints on local cycles, and propose a practical strategy by adding a small fraction of shortcut links between randomly chosen nodes in order to improve the robustness to a similar level to that of the optimal bimodal networks with a larger degree $O(\sqrt{N})$ for the network size $N$. These properties will be useful for constructing future ad-hoc networks in wide-area communications.
Comment: 14 pages, 10 figures, 1 table
Databáze: OpenAIRE
Externí odkaz: