Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties

• Hayashi, Yukio

Abstract

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(√N) for the network size N. These properties will be useful for constructing future ad hoc networks in wide-area communications.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/9213

Journal

• Physica A: Statistical Mechanics and its Applications

  Physica A: Statistical Mechanics and its Applications 388 (6), 991-998, 2008-11-28

  Elsevier

Keywords

• Population density
• Geometric spanner
• Decentralized routing
• Shortcut link
• Wireless ad-hoc communication

Details

• CRID: 1050564287491687168
• NII Article ID: 120002511614
• ISSN: 03784371
• Web Site: http://hdl.handle.net/10119/9213
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles