SS17-6
通信距離とノード数に対する無線通信ネットワークの連結性○片田喜章 （摂南大学）
概要
マルチホップ通信を利用する無線通信ネットワークでは，中継ノードの存在により各ノードの通信距離を越える範囲であってもネットワーク内であれば各ノードは相互に通信できる．そのためには，無線通信ネットワークの連結性が保証されている必要がある．本研究では，無線通信ネットワークの連結性を満たす通信距離とノード数に関してパーコレーション理論をもとに計算機実験を行う．
キーワード: 無線通信ネットワーク，連結性，マルチホップ通信

1

はじめに2

多数の無線通信端末からなる無線通信ネットワークが注目されている．その中でも，中継ノードの存在により多段階の通信が可能となるマルチホップ通信を用いて，端末同士が相互接続できるアドホックネットワー
クがあり，固定された基地局インフラを必要としないことなどから様々な用途に応用可能である．各端末にセンシング機能が組み込まれているものはワイヤレス
センサネットワーク 1) ，さらに移動機能をもつものはモバイルワイヤレスセンサネットワーク，とよばれている．
マルチホップ通信を利用する無線通信ネットワーク
では，各端末ノードの無線通信距離を越える範囲であってもネットワーク内であれば各ノードは相互に通信できる．そのためには，無線通信ネットワークの連結性(connectivity) が保証されている必要がある 1) ．
ワイヤレスセンサネットワークの研究では連結性よりも被覆 (coverage) が主として議論されることが多い
2)．被覆とは観測対象の領域に対する，センサにより測定できる領域の割合のことである．この理由は，一般的にセンサによる測定可能距離は無線通信可能距離よ
りもはるかに短く，被覆度が高い，つまり，「ぬけ」がな
いくらいに対象領域を覆うほど多数のノード数が配置されているならば，陽に考慮しなくても連結性は満たされているはずである，ということである 3) ．ワイヤレスセンサネットワークではノードの位置が固定されていることを仮定することが多い．一方，モバイルワ
イヤレスセンサネットワークは各端末が移動可能であるため，時系列的な被覆度の増加や観測対象である移動ターゲットの追跡などに焦点が当てられており，その前提として連結性が議論されている．
本稿では，無線通信ネットワークの連結性のみを扱う．我々の研究グループではモバイルワイヤレスセンサネットワークと捉えられる，無線通信機能をもつスワームロボット 4, 5, 6) ネットワークと情報集約を行う基地局との連結性について議論してきた 7, 8, 9, 10) ．とくに文献 7, 9) では正方形の環境において，連結性を満たす通信可能距離とノード数の関係を計算機実験により調べている．そこで，本稿では文献 7, 9) をもとに異なる長方形の環境における，通信距離とノード数に対する無線通信ネットワークの連結性を調べる．ここで，ノード間の「つながり」はパーコレーション理論 11) を用いた実験を行っている．

̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲̲システム・情報部門学術講演会2015（2015年11月18日-20日・函館）

パーコレーション

本節ではパーコレーションについて簡単に紹介する．
正方格子の格子点上に確率 p で要素（サイト）を配置する．p を 0 から大きくしていくと，要素がクラスター (かたまり) を形成するようになり，ある臨界値 pc に達すると正方格子の上下および左右の端がつながる (percolate:パーコレートする，浸透する) ような巨大なクラスターが出現する．このようなクラスターの構築過程をサイト過程いう．また，別のクラスターの作り方として，要素を配置するのではなく，格子点間につながり（ボンド）を配置していくボンド過程がある．このように系を構成する要素間のつながり方およびつながった要素集合の特性を扱う理論がパーコレーションである 11) ．
無限に大きな系を考えると，そこで無限に大きなクラスターが出現する臨界値は格子の形によって決まることが知られており，2 次元・3 次元の基本的な格子に関しては厳密解が得られている．厳密解が得られないものに関しては計算機実験により近似値を得ている．また，無限という極限状態において，パーコレートする確率および臨界値にはある関数系が存在し，その関数系を規定するパラメータ (臨界指数) は格子の形には依存せず，次元によって決まることが報告されている．
格子におけるパーコレーションだけではなく，連続空間に要素を配置する場合に関しても研究が行われている 11)12)13) ．連続空間では格子点のように要素が「隣接する」という概念がないため，要素間の「つながり」を定義する必要がある．2 次元連続平面において要素同士がつながる範囲を半径 R の円で設定する例を Fig. 1に示す．このとき，要素間の距離を d とすると，d < Rのときに要素間につながりが存在する．

R

Fig. 1: Illustration of the bonding criteria for twodimensional ramdom-lattice site problem- 1135 -SY0010/15/0000-1135 © 2015 SICE

(0,h)

(w,h)

1
0.8

R: Communication
Range

P

0.6
0.4
0.2

Nodes

(0,0)

0(w,0)

Fig. 2: Experimental setup for two-dimensionalramdom-lattice site problem

3

計算機実験

3.1

実験設定

102103

N
R=1.0
R=0.9

R=0.8
R=0.7

R=0.6
R=0.5

R=0.4R=0.3

R=0.2
R=0.1

Fig. 3: Connectivity for each communication range

本実験では 2 次元連続空間における離散パーコレーションをモデルとする 13) ．Fig. 2 に示す h × w の平面に N 個の点を一様分布させる．それらの点のつながりは，各点を中心として半径 R の円をえがき，互いの円内に入った点の間に生じるものとする．ワイヤレ
スセンサネットワークと対応させると，N は単位面積におけるノード数，点 i(i ∈ {1, · · · , N }) は任意のノード，R は各ノードの通信可能距離，をそれぞれ表す．ただし，R は全てのノードで同じ値に設定する．環境の左下の原点に各ノードと同じ通信可能距離をもつ無線基地局を設置し，基地局と各ノードの連結性を調べる．
つまり，ノードの台数 N を一定に保って通信可能距離R を増加させる，もしくは，R を一定に保って N を増加させると，あるところで大部分のノード間につながりが生じ（パーコレーションが起こり），マルチホップ通信による基地局との通信が可能となる．なお，上述のように無線通信は幾何学的なつながりだけを考慮しており，発生するノイズや干渉，環境からの散乱・回折・反射などの影響 3) は考慮していない．本実験では h ∈ {0.5, 1.0}，w ∈ {0.025, 0.05, 0.1, 0.25, 0.5, 1.0}
R = {0.1, 0.2, · · · , 1.0}，N ∈ {2, · · · , 1000} とし，ノードの位置をランダムに設定した実験を各 (R, N ) に関して 10000 回行った．なお，以上の設定では各点に配置するノードに大きさを想定していない．これは，一般的に無線通信可能距離と比べてノードの大きさは無視できるほど小さく，大きさを 0 に近づけていくとノードに大きさを想定しない場合の結果に収束することが先行研究でわかっているためである 7, 9) ．

3.210110.8P0.60.40.20102103

N
w=1.0
w=0.5

w=0.25w=0.10w=0.050
w=0.025(a) h = 1.010.8P0.60.40.20101102103

N
w=0.5
w=0.25

実験結果

基地局から直接的もくしはノードを介して間接的に連結したノード数の割合である連結度 P （試行回数に対する平均）を縦軸に，そのときの N を横軸にとった片対数グラフを Fig. 3 に示す．各 R に関して，N を大きくしていくと P が 1.0 に収束する N の臨界値 Nc が存在することがわかる．また，R が大きくなると，Pが大きくなる．
つぎに環境の大きさを縮小した結果を，R = 0.1 の場合について Fig. 4 に示す．環境が小さくなると同じN に対し，P が大きくなる．他の R についても同様の傾向を確認した．各 (h, w) について，N の臨界値 Nc101

w=0.10w=0.050

w=0.025(b) h = 0.5

Fig. 4: Effect of the size of the environment on connectivity for R = 0.1
を Table 1 に示す．Nc は h の値を固定した場合に w に対し相関があることがわかる．また，環境の面積 (hw)が小さく R が大きいと，当然のことながらノード一台(Nc = 1) で全環境を通信可能範囲で覆うことができる．
上記の結果について，(h, w) = (1, 1) に対する，各(h, w) の面積の相対値および臨界値の相対値が各 R においてどのような関係にあるかを調べた．横軸に面積- 1136 -Table 1: Critical values of N for each R and h, w, above which a network is fully connected.
h1.0
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.5

size
w
1.0
0.5
0.25
0.1
0.05
0.025
0.5
0.25
0.1
0.05
0.025

0.1
1388
549
293
170
170
147
341
168
67
67
60

0.2
341
168
70
67
60
60
83
33
23
23
23

0.3
163
70
39
39
39
39
34
13
13
13
12

Table 2: Regression coefficient of critical N rate foreach area rate relative to the square
R
0.1
0.2
0.3
0.4
0.5

slope
0.919714
0.904598
0.848601
0.814750
0.803171R
0.6
0.70.80.91.0R0.5502018181818733210.48333272323231687770.81687777111110.9977777111111.0833211111111) Li, J., Andrew, L.L.H., Foh, C. H., Zukerman, M.,
Hsiao-Hwa, C.: Connectivity, Coverage and Placement in Wireless Sensor Networks, Sensors, Vol.9,No.10, 7664/7693 (2009)2) Mulligan, R., Ammari, H.M.: Coverage and connectivity issues in wireless sensor networks: A survey, Network Protocols and Algorithms, Vol.2, No.2,27/53 (2010)
3) Ghosha, A. and Das, S.K.: Coverage and connectivity
issues in wireless sensor networks: A survey, Pervasiveand Mobile Computing volume 4, issue 3, 303/334(2008)
4) Sahin, E.: Swarm Robotics: From Sources of Inspiration to Domains of Application, Lecture Notes in
Computer Science, Volume 3342, 10/20 (2005)

slope
0.806499
0.7008020.7781190.662824
0.843162

5) スワーム：群れの創発的挙動生成，計測と制御, Vol.52.
No.3, 179/276 (2013)
6) Brambilla, M., Ferrante, E., Birattari, M., Dorigo,
M.: Swarm Robotics: A Review from the Swarm
Engineering Perspective, Swarm Intelligence, Vol.7,
No.1, 1/41 (2013)7) 西口晃央，片田喜章: パーコレーション理論を用いたス
ワームロボットネットワークの連結性―通信距離とロボッ
ト数に関する考察―，ロボティクス・メカトロニクス講
演会’14, 講演論文集 CD-ROM, 2A2-X06 (2014)8) 西口晃央，片田喜章, 森脇和也，渡壁亮介: 探索問題におけるスワームロボットネットワークの連結性に関する実機検証, 計測自動制御学会 システム・情報部門学術講
演会 2014, 93/95 (2014)9) Katada, Y.: Connectivity of Swarm Robot Networks
for Communication Range and the Number of Robots
Using Percolation Theory, Proceedings of the 2014
IEEE/SICE International Symposium on System Integration, 93/98 (2014)

おわりに

本稿では，異なる複数の長方形環境における，通信可能距離とノード数に対する無線通信ネットワークの連結性に関する計算機実験を行った．連結性は通信可能距離と環境の大きさに依存し，連結性を満たすノード数には臨界値が存在することを確認した．また，正方形環境を縮小した長方形環境では，その面積比により連結性を満たすのに必要なノード数が予測できることがわかった．

0.72081111111121111

参考文献

比 hw/1.0 を，縦軸に臨界値の比 Nch,w /Nc1,1 をとったグラフを Fig. 5 に示す．また，各 R に関する結果を最小二乗法で直線近似した結果も併せて Fig. 5 に示す．
すべての R で高い相関が見られる．とくに R が環境に対し小さい場合には，最小二乗法による近似直線の傾き (回帰係数) は 1 に近くなる．R が大きくなると，臨界値は環境が小さくなるにつれ飽和することから近似直線の傾きは 1 からしだいに小さくなる．回帰係数の値を Table 2 に示す．以上の結果より，R が環境に対し小さい場合には，各 R に関して正方形環境に対する面積比により連結性を満たすのに必要なノード数がほぼ予測できることがわかった．

40.63413131312124111110) 片田喜章，西口晃央，森脇和也, 渡壁亮介: レヴィフラ
イトを用いたスワームロボットネットワークのターゲッ
ト探索, ロボティクス・メカトロニクス講演会’15, 講演
論文集 CD-ROM, 2A1-K06 (2015)11) 小田垣孝: パーコレーションの科学，裳華房 (1993)
12) Gilbert, E.N.: Random Plane Networks， J. Soc. Indust. Appl. Math, Vol. 9, No. 4, 533/543 (1961)
13) Pike, G. E. and Seager, C. H.: Percolation and Conductivity: A Computer Study. I, Phys. Rev. B, volume 10, issue 4, 1421/1434 (1974)- 1137 -1

least squares approximation
experimental result

0.8

Relative critical N rate

Relative critical N rate

10.6
0.4
0.2
0

least squares approximation
experimental result

0.8
0.6
0.4
0.2
00

0.2

0.4
0.6
Relative area rate

0.8

10(a) R = 0.1
1

least squares approximation
experimental result

0.8
0.6
0.4
0.2
01

0.2

0.4
0.6
Relative area rate

0.8

0.8

10.8

10.8

10.8

10.80.6
0.4
0.2

100.2

0.4
0.6
Relative area rate(d) R = 0.4
1

least squares approximation
experimental result

0.8

Relative critical N rate

Relative critical N rate

1

least squares approximation
experimental result(c) R = 0.3

0.6
0.4
0.2
0

least squares approximation
experimental result

0.8
0.6
0.4
0.2
000.2

0.4
0.6
Relative area rate

0.810(e) R = 0.5
1

0.2

0.4
0.6
Relative area rate(f) R = 0.6
1

least squares approximation
experimental result0.8

Relative critical N rate

Relative critical N rate

0.8

000.6
0.4
0.20

least squares approximation
experimental result

0.8
0.6
0.4
0.2
000.2

0.4
0.6
Relative area rate

0.8

10(g) R = 0.7
10.2

0.4
0.6
Relative area rate(h) R = 0.8
1least squares approximation
experimental result

0.8

Relative critical N rate

Relative critical N rate

0.4
0.6
Relative area rate(b) R = 0.2

Relative critical N rate

Relative critical N rate

10.2

0.6
0.4
0.2
0least squares approximation
experimental result

0.8
0.6
0.4
0.2
000.2

0.4

0.6

0.8

1

Relative area rate

00.2

0.4

0.6

Relative area rate(i) R = 0.9(j) R = 1.0

Fig. 5: Critical N rate for each area rate relative to the square- 1138 -