JAIST Repository
https://dspace.jaist.ac.jp/Title

地理的空間上の人口分布に応じた自律分散ネットワー
クの構築法

Author(s)林, 幸雄

Citation

科学研究費助成事業研究成果報告書: 1‑5

Issue Date

2013‑05‑10

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/11361

RightsDescription

研究種目：基盤研究（Ｃ）, 研究期間：2009〜2012,
課題番号：21500072, 研究者番号：70293397, 研究分
野： 複雑ネットワーク科学, 科研費の分科・細目：情報学 計算機システム・ネットワーク

Japan Advanced Institute of Science and Technology

様式Ｃ－１９
科学研究費助成事業（科学研究費補助金）研究成果報告書
平成２５年

５月１０日現在

機関番号：13302
研究種目：基盤研究（Ｃ）
研究期間：2009～2012
課題番号：21500072
研究課題名（和文） 地理的空間上の人口分布に応じた自律分散ネットワークの構築法
研究課題名（英文） Construction methods of an autonomous-distributed network on ageographical space according to population
研究代表者
林 幸雄（HAYASHI YUKIO）
北陸先端科学技術大学院大学・知識科学研究科・准教授
研究者番号：70293397
研究成果の概要（和文）：近未来の広域通信で予想される人口に応じてスケーラブルに増大する利用状況に適応的な、幾何学的な再帰分割やリンク淘汰に基づくネットワーク構築法を提案した。理論解析と数値実験から、提案モデルが分散ルーティングによる短い経路長で高い通信効率を持ち、不慮の故障や悪意のある攻撃に対する結合耐性が強い事を示すとともに、渋滞解消戦略や頑健性の向上策を見出した。
研究成果の概要（英文）：We have proposed construction methods of geographical networks based on recursive
divisions of faces or link survivals, in which positions of nodes as base-stations
are adaptive to scalably increasing request on future wide-area communicationaccording to population. From theoretical analyses and computer simulations, we showthat the proposed network models are efficient in the decentralized routings on shortpaths and robust in the connectivity against node removals of random failures andintentional attacks. In addition, we find several strategies to avoid traffic
congestion and to improve the robustness by adding shortcuts.
交付決定額（金額単位：円）2009 年度
2010 年度
2011 年度
2012 年度
年度
総 計

直接経費
800,000
900,000
800,000
800,000間接経費
240,000
270,000
240,000
240,000

3,300,000

990,000

合計
1,040,000
1,170,000
1,040,000
1,040,000
4,290,000

研究分野： 複雑ネットワーク科学
科研費の分科・細目：情報学 計算機システム・ネットワーク
キーワード：人口分布、ネットワーク科学、自己組織化、ルーティング、トラフィック特性、再帰分割、ショートカット、淘汰
１．研究開始当初の背景
今世紀初頭のネットワーク科学の誕生とほぼ同時期から、自己組織/自律分散的なSF(Scale-Free)ネットワークの生成モデルを用いた通信効率や頑健性=結合耐性に関する理論解析や数値実験、コンピュータウィルス等の拡散と電力崩壊やパケット渋滞等における過負荷伝搬の防御策を検討して来た。また、より現実的なモデル化を目指してノードの空間配置も考慮して、ランダムに選択した三角形の細分を繰り返して空間上で SF 構造を生成できるモデル(RA)から、そのつぶれた三角形の斜辺に現れる長距離リンクを局所的操作で解消するモデル(DLSF)に拡張し、その最適経路の平均距離やホップ数の特性を調べると伴に、従来の木構造を仮定した理論値に比べて地理的に近接なサイクルの存在で結合耐性がさらに弱まる問題点を明らかにしてきた。
但し、DLSF では、経路長や最大次数は RA より多少抑えられるものの、ハブ攻撃に対する脆弱性は同様で、計算機科学におけるドロネー三角分割(DT)には及ばない。一方、DT では対角変形操作を可能な限り全域的に波及させる必要があり、局所的な操作だけでは構築できない。そこで、双方の長所が持てるように、別の幾何学的な構築法を探ることを考えた。
２．研究の目的
計算機科学と統計物理の両アプローチから、近未来の広域通信に適したネットワーク構築法を検討する。特に、地理的空間上の人口分布に応じた現実的なアクセス要求に従った基地局ノードの配置、自律分散処理に基づくルーティングの効率化と故障や攻撃に対する結合耐性の強化、パケット転送能力やキュー量に依存した渋滞発生メカニズムの解明とその解消策などの観点から、近未来の情報通信の基盤技術となり得る自律分散型ネットワークの設計原理を探り、アルゴリズムレベルの解決策を見出す。
３．研究の方法
地理的空間上のアクセス増加に応じて自律分散的に成長し、経路長が短く結合耐性も強いネットワークの構築アルゴリズムを下記の(1)-(4)に関して検討する。分析指標となる、各ノードやリンクを流れるパケット量や（故障や攻撃による）ノード除去率に対する連結成分のサイズ等を主にネットワーク科学の方法論を用いて、数値実験と理論解析から求める。また、ノードの空間分布や結合形態、ルーティング法、障害回避戦略等に関するさまざまな条件比較や性能等を表すパラメータの組み合わせに対して、PCクラスタ上の分散処理によって効率良く計算する。
(1) 人口分布に従ったネットワーク構築法
総務省・統計局の地域メッシュ統計データを用いて、正三角形や正方形をその面内人口に比例した確率で選択して分割を繰り返すことで、地理的空間上で成長するネットワークを構築する。ノードはマルチホップ中継用の基地局を、リンクは基地局間の（無線あるいは有線の）通信回線を表し、任意の位置から各ユーザは最も近い基地局にアクセスする。人口密度に従って大小さまざまな自己相似形が平面上に出来ることから、電波干渉の原因となるリンク交差が存在しないのみならず、任意のノード間の最短経路長がその直線距離のt倍以内に抑えられるt-spanner性を持つ。定量的に各最短距離経路のt値の分布とリンク長分布を調べて通信効率を計る。
(2) 故障や攻撃に対する結合耐性の強化
上記の構築法では 3 種類の低い次数のみで SF 構造にならず、高い結合耐性を持ち得ることが最近のパーコレーション理論から期待できるので、ランダ
ム故障やハブ攻撃によるノード除去率に対する最大連結成分 GC のサイズ変化、GC 崩壊で全体がバラバラになるノード除去率の臨界値、ショートカット追加の効果を数値実験から求めて、その結合耐性を調べる。また、渋滞が発生しやすい箇所への攻撃を想定した場合の結合耐性を GC のサイズ等から分析して、ショートカットの追加や自己修復的なリンク張り替えによる強化策を検討する。
(3) トラフィック特性解析と渋滞解消策
人口密度に応じたパケットの発生消滅率を考え、そのトラフィック特性として、ノードやリンクへのパケットの集中度合を媒介中心性から測り、従来の問題設定（各ノードが一様な発生消滅率を持つ）と比較する。ここで、各パケットの独立かつ並列な動作を仮定し、距離やホップ数をそれぞれ最小化基準とした標準的な経路において、渋滞個所の発生傾向をシミュレーション実験から調べる。さらに、インターネ
ット実データに基づくネットワーク構
造上で、ランダムウォークを拡張した統計物理の Zero Range Process(ZRP)モデルを用いて、渋滞/自由流の相転移メカニズムを解明し、渋滞解消策を検討する。
(4) 解析用ツール化と分散処理
Wiki 上に記述を加えながら、プログラムのモジュール化を随時進める。
各クライアントが自身の計算資源の空き状況に応じてサーバに随時タスクを要求するワークプール方式の分散処理を基本として、ネットワークダイナミ
クス分析に適したマルチスレッド化やタスク分割方法なども検討する。
４．研究成果近未来の広域通信で予想されるスケーラブ
ルに増大する利用状況に適応的なネットワー
クの構築法として、人口密度に比例した現実的なアクセス要求に従った基地局ノードの配置、自律分散処理に基づく効率的なルーティング、悪意な攻撃等に対しても結合耐性を強化できる障害回避戦略、渋滞発生メカニズムの解明とその解消策を探り、具体的アルゴリズムを開発し、以下の成果を得た。
(1) 人口分布に従ったネットワーク構築法
統計データに基づく人口密度に比例して、正三角形や正方形の自己相似な分割を繰り返して成長するネットワーク構築法を提案した。また、その自己相似な階層性を持つネットワーク生成をマルコフ連鎖として捉えて、フラクタル次元の効率的な近似計算法を提示した。
上記の自己相似分割における二等分から任意の点で分割可能とするより現実的なモデルを考えて、正方形の再帰的面分割を長方形に拡張し、その面積分布を解析的に示した。
さらに、その長方形分割に基づくネットワーク上の乱歩が、生物の最適餌探索と類似する移動距離分布を示す事を発見し、優れた探索効率を持つ基本特性を明らかにした。
(2) 故障や攻撃に対する結合耐性の強化(1)の自己相似な再帰分割で生成されるネットワークの頑健性を、他の代表的な優先的選択や幾何学的なネットワーク構築モデルと比較しながら数値実験より示した。
また、空間に一様分布したノード同士が一定の電波到達範囲内で結合する無線通信網の初期構成から、人口密度に比例したパケット送受信要求に基づくパケットフローでリンク淘汰される新たなネットワーク構築法も提案した。これと類似した平面上に拘束される粘菌にはないショートカット追加を施すと、短いリンクでホップ数も小さく効率的（サイズNで平均ホップ数がO(log N)のSmall-World性を満たす）で結合耐性も強化できることを示した。
一方、SF 以外の種々のネットワークに対してリワイヤリングを施した Onion-like 構造による頑健性の向上や、都市道路網の実データにおける面積分布の対数正規性を数値実験より得た。
(3) トラフィック特性解析と渋滞解消策
インターネットなど広く現実のネットワークに潜む SF 構造における ZRP の理論解析と数値実験から、局所情報である次数のべき乗に比例して隣接ノードを選ぶ確率的ルーティングのトラフィック特性を分析し、渋滞解消に適したパラメータ値やルーティング戦略を把握した。
また、(1)の自己相似な再帰分割で生成されるネットワークの通信効率を、リンク長の平均値や分布、t-spanner な経路の t 値の分布、ノードやリンクにかかる最大負荷のスケーリング則（ネット規模に対する渋滞の深刻度）等から定量的に明らかにした。
(4) 解析用ツール化と分散処理独自開発している複雑ネットワークに適した Java 分析ツールに、トラフィ
ック解析など新たに加えた統合化モジ
ュールの記述や効率的なプログラミン
グ技法の説明を充実させ、Wiki 上に整備した。但し、Java のバージョンアップに伴う基本部分の修正が広範囲に及んだ事や、ノード数等の大規模化によるメモリ消費の為に JavaRMI が余り有効でない事も判明し、分散処理に関する当初の計画に至るまでの実現は出来なかった。
５．主な発表論文等（研究代表者、研究分担者及び連携研究者には下線）〔雑誌論文〕（計７件）① Yukio Hayashi, Takayuki Komaki,
Yusuke Ide, Takuya Machida, and Norio
Konno,
Combinatorial
andapproximative analyses in a spatiallyrandom division process, Physica A,
査 読 有 , Vol.392, No.9, (2013),
pp.2212-2225.
②YukioHayashi,
Adaptive
Fractal-like Network Structure forEfficient Search of Targets at Unknown
Positions,Proc.
ofthe4thInternational Conference on Adaptive
andSelf-adaptive
Systems
andApplications, 査 読 有 , (2012),
pp.63-68, ISBN:978-1-61208-219-6
http://arxiv.org/pdf/1207.6814v1.pdf③ Yukio Hayashi, and Yuki Meguro,
Self-organized network design by linksurvivals and shortcuts, Physica A,
査読有, Vol.391, (2011), pp.872-879.
④ Yukio Hayashi, and Yasumasa Ono,Traffic properties for stochastic
routing on scale-free networks, IEICE
Trans. Communications, 査 読 有 ,Vol.E-B, No.5, (2011), pp.1311-1322.
⑤ Yukio Hayashi, An approximative
calculation of the fractal structure
in self-similar tilings, IEICE Trans.
Fundamentals, 査 読 有 , Vol.E94-A,

No.2, (2011), pp.846-849.
⑥
Yukio Hayashi, and Yasumasa Ono,
Geographical networks stochasticallyconstructed by a self-similar tilingaccording to population, Physical Review
E 査読有, Vol.82, (2010), pp.016108-1-9.
⑦ 林 幸雄, ネットワーク科学に基づいた
ロバストな情報通信ネットワーク, 電気学会 誌 , 査 読 有 , Vol.130, No.5, (2010),
pp.293-296.
〔学会発表〕（計 27）[1] Yukio Hayashi, On the Analysis of aScaling Law Related to Random Walks -forthe distributions of broken fragments ofglass, areas enclosed by city roads, anddivided faces in network models-, Proc. of
the International Conference on Nonlinear
Theory and its Applications, Organized
Session:Complex
NetworkScience,
pp.106-109, Palma, Majorca, Spain, Oct.
23-26 (2012).
[2] Yukio Hayashi, Adaptive Fractal-like
Network Structure for Efficient Search ofTargets at Unknown Positions, Proc. of the
4th International Conference on AdaptiveandSelf-adaptive
SystemsandApplications, Nice, France, July 23-26(2012).
[3] 小牧 嵩征, 林 幸雄, 非同期な情報交換を行うメッセージフェリーを用いたルー
ティング手法, 第 9 回ネットワーク生態学シンポジウム, CD 予稿集, pp.151-157, 沖縄国際大学, 12/15, 2012.
[4] Binbin Xing, 林 幸雄. Onion-like 構
造とネットワークの頑健性及び通信効率,
第 9 回ネットワーク生態学シンポジウム, CD予稿集, pp.183-184, 沖縄国際大学, 12/14,2012.
[5] 小牧 嵩征, 林 幸雄, レビィ飛行的な探索構造が埋め込まれた地理的ネットワー
クの効率性, 第 9 回ネットワーク生態学シンポジウム, CD 予稿集, pp.185-187, 沖縄国際大学, 12/14, 2012.
[6] 近藤 俊宏, 林 幸雄, 都市道路網の歴史的変化 -東京 23 区, 第 9 回ネットワーク生態学シンポジウム, CD 予稿集, pp.204-205,沖縄国際大学, 12/14, 2012.
[7] 松 久 保 潤 , 林 幸 雄 , Multi-ScaleQuartered モデルに対する階層の深さに基づくショートカット追加法, 第 9 回ネットワー
ク 生 態 学 シ ン ポ ジ ウ ム , CD 予 稿 集 ,pp.218-220, 沖縄国際大学, 12/14, 2012.
[8] 小牧 嵩征, 林 幸雄, 松下 貢, 長方形分割モデルを用いた餌探索と正方格子上の Levy Flight 餌探索の比較, 第 8 回ネット
ワ ー ク 生 態 学 シ ン ポ ジ ウ ム , CD 予 稿 集 ,pp.98-102, 慶応義塾大学,3/15, 2012.
[9] Binbin Xing, 林 幸雄, リンク淘汰とパス強化で自己組織化されたネットワークの頑健性に関する丘現象, 第 8回ネットワーク生態学シンポジウム, CD予稿集, pp.179-186, 慶応義塾大学,
3/15, 2012.
[10] 林 幸雄, リンク淘汰に基づくネットワーク自己組織化 -粘菌より優れた遠距離結合の追加-, 2012 年電子情報通信学会総合大会 企画セッション 依頼シンポジウムセッション 「情報ネットワーク科学が目指すもの」, 3/22,
2012, 岡山大学
[11] 林 幸雄, フラクタル階層分割によるネットワーク構築 -近未来の通信網に向けて-, 小研究集会 「大規模ネットワークの特徴を抽出するアルゴリズムの開発と社会行動の予測」, 2/9, 2012,
九州大学[12] Yukio Hayashi, A self-organizeddesign of efficient and strong robust
communication networks, Satelite
event in Netsci2011, Networks ofNetworks:
SystemicRiskandInfrastructural Interdependencies,
Budapest, Hunguary, June 7 (2011).
[13]
Jun Matsukubo, and Yukio
Hayashi, Shortcut effect based on ahierarchy structure in geometrical
networks divided into rectangle,
Netsci2011, Budapest, Hunguary, June
8-10 (2011).
[14] 林 幸雄, イントロ：相互に関連する社会技術, 企画セッション「社会的問題解決に挑戦する科学の新潮流 -複雑ネットワーク科学と社会物理学からの提言-」, 第 4 回横幹連合コンファレンス, 11/28, 2011, 北陸先端科学技術大学院大学[15] 松久保 潤, 林 幸雄, 小野 泰正,
長方形分割ネットワークにおける階層構造に基づくショートカットリンク効
果, 第 7 回ネットワーク生態学シンポジ
ウム, CD 予稿集, pp.128-144, 蒲田（東京）, 6/17, 2011.
[16] 目黒 有輝, 林 幸雄, リンク淘汰とショートカット付加によるネットワーク自己組織化，第 7 回ネットワーク
生 態 学 シ ン ポ ジ ウ ム , CD 予 稿 集 ,pp.110-119, 蒲田（東京）, 6/17, 2011.
[17] Binbin Xing, 林 幸雄, MSQ ネッ
トワークのフラクタル次元に依存した最適ショートカット, 第 7 回ネットワー
ク 生 態 学 シ ン ポ ジ ウ ム , CD 予 稿 集 ,pp.194-195, 蔵王（山形）, 3/10, 2011.
[18] 林 幸雄, 空間的階層とネットワ

ーク自己組織化, 社会物理学研究会, 1/6,東京, 2011.
[19] Yasumasa Ono, and Yukio Hayashi,
Robustness of the Internet at the AS Levelby the DDoS Attack, Proc. of the 8th
Asia-Pacific Symposium on Information andTelecommunicationTechnologies,
Vol.A-1-3,
APSITT2010,
ISBN978-4-88552-244-4C3055, Kuching Sarawak,
Malaysia, June 15-18 (2010).
[20] Yukio Hayashi, Optimal long-range
connections for transport networks
embedded in a space, International School
and Conference on Network Science, Boston
USA, May 10-14 (2010).
[21] 林 幸雄, 地理的空間上のネットワー
ク自己組織化, 第 4 回 複雑システムのネッ
トワーク科学研究会, （独）情報通信研究機
構：NICT 新世代ネットワーク戦略プロジェ
クト, 小金井（東京）, 11/29, 2010.
[22] Yukio Hayashi, and Yasumasa Ono,
Traffic properties for extended random
walks on scale-free networks 情報処理学
会研究報告 2009-MPS-77, 伊豆（静岡）, 3/4,
2010.
[23] Yasumasa Ono, and Yukio Hayashi,
Serious Damages in DDoS Attacks on theInternet at AS level, Proc. of the 9th
Asia-Pacific Complex Systems Conference,
pp.151-155, Nov 4-7, Tokyo Japan (2009).
[24] Yukio Hayashi, Robust and efficientdesign of geographical networks according
to a population density, NETSCI2009: The
4th International Workshop and Conference
on Network Science and their Applications,
July 2, Venice Italy (2009).
http://pilastro.phys.uniroma1.it/netsci/docs/submission_show_all.cgi.html#66[25] 近藤 俊宏, 林 幸雄, 小野 泰正, 佐藤 恵介, 地理的空間上の距離, 人口, 次数に対する優先的選択モデルの頑健性-ノード除去-, 第 6 回ネットワーク生態学シンポ
ジウム, CD 予稿集, pp.153-154, 産総研（つくば）, 12/17, 2009.
[26] 目黒 有輝, 林 幸雄, 小野 泰正, 佐藤 恵介, 地理的空間上の距離, 人口, 次数に対する優先的選択モデルの頑健性-リンク除去-, 第 6 回ネットワーク生態学シンポ
ジウム, CD 予稿集, pp.149-152, 産総研（つくば）, 12/17, 2009.
[27] 小野 泰正, 林 幸雄, インターネット
における局所情報による DoS 的なノード攻撃の脅威, 第 6 回ネットワーク生態学シンポジ
ウム, CD 予稿集, pp.119-121, 産総研（つくば）, 12/17, 2009.
〔図書〕（計 1 件）

① Yukio Hayashi, iConcept Press,
Rethinking of Communication Requests,
Routing, and Navigation Hierarchy on
Complex Networks -for a Biologically
Inspired Efficient Search on a
Geographical Space-, In "Networks-EmergingTopics
inComputerScience,",
Chapter4,
ISBN
978-1-922227-02-7, Arshin Rezazadeh,
Ladan Momeni, and Igor Bilogrevic Eds,
(2012), pp.67-88.
〔産業財産権〕○出願状況（計 0 件）
名称：
発明者：
権利者：
種類：
番号：
出願年月日：
国内外の別：○取得状況（計 0 件）
名称：
発明者：
権利者：
種類：
番号：
取得年月日：
国内外の別：〔その他〕① IARIA PAPER AWARD
http://www.iaria.org/conferences201
2/awardsADAPTIVE12/adaptive2012_a3.
pdf②
PRE Kaleidoscope Images: July2010
http://pre.aps.org/kaleidoscope/Jul
y2010/pre

６．研究組織(1)研究代表者
林 幸雄（HAYASHI YUKIO）
北陸先端科学技術大学院大学・知識科学研究科・准教授
研究者番号：70293397(2)研究分担者
無（）研究者番号：(3)連携研究者
無（研究者番号：）