ワイヤレスセンサネットワークにおけるセンサ数の決定問題
M2010MM006 長谷川遼太
指導教員：鈴木敦夫

1

はじめに

2

研究の準備

本研究では，ワイヤレスセンサネットワーク（以後セン問題の設定を行う．本研究ではセンサネットワークをサネットワーク）におけるセンサ数の決定を行う．その 設置する領域は正方形であるとする．また，研究内の数
際，センサ機能による領域の被覆と通信機能によるネッ 値実験時は単位正方形で考える．また，センサはヘリコトワークの構築を考慮する．
プターなどで領域の上空から撒かれると仮定し，一様にセンサネットワークとは，センサ付無線端末のネット ランダムで配置されるとする．そして，センサのセンサワークのことである．領域内にセンサネットワークを設置 機能と通信機能が届く範囲は，センサを中心とした半径することで，環境や物理的状況のデータ（温度，光，音， 固定の円であるとする．このとき，センサのバッテリー湿度など）を収集することができる．遠隔の情報をリア や風の影響など，その他の要因は一切考慮しない．ここルタイムで収集することができるため，様々な場面で利 でカバー率と連結状態という２つの要素を定義する．
用が期待されている．例えば，森林火災への対策 [3] であカバー率は，センサのセンサ機能によって領域が被覆る．まず事前に森林の中にセンサネットワークを設置す されている割合と定義する．カバー率の例を図 1 に示す．
る．そして，森林で火災が発生した時に火災の発生源を 正方形内が対象領域，各点がセンサ，センサの周囲の円すぐに特定することが出来る．そのため，早期に鎮火作 内が被覆されている領域である．図 1 の左図は，領域の業をすることができ，被害を抑えることが可能となる．他 全体が被覆されているのでカバー率が高く，理想的な状には，病院での患者の健康管理や野生生物の観察，戦場 態である．また，図 1 の右図は，領域が疎らにしか被覆での戦略などがある [3]．
されておらず，カバー率は低い．
近年，技術の発達によりセンサは小型化され，さまざまなアプリケーションのセンサ上での利用が可能となっている．そのため，以前に比べてセンサネットワークはより実用的となった．しかし，センサには通信機能やバッテリーなどの機能面での問題がある．センサネットワー
クのこうした制約を考慮した研究も多くされている [3]．
センサネットワークでは，センサ機能により周辺のデータを収集し，通信機能によるネットワークで利用者に収集した情報を伝達する．そして，センサのセンサ機能と
図 1 カバー率の例
通信機能が届く範囲は，どちらも有限である．そのため，配置されるセンサ数が不足しているとデータの収集や情連結状態とは，センサが通信可能な距離以下で，領域報の伝達が出来なくなり，センサネットワークとして機 内の全てのセンサが１つの構造木となることが出来る状能しない．しかし，センサネットワークとして機能させ 態と定義する．連結状態の例を図 2 に示す．正方形内がるために大量にセンサを配置すれば，以下のような問題 対象領域，各点がセンサ，連結であるセンサ間は線で繋が発生する．
がっている．図 2 の左図は，全てのセンサが一定の距離以• 同時に通信するセンサ数の増加による，干渉の発生• 干渉が原因で発生する再送信などの通信回数の増加による，バッテリーの消耗下で１つの構造木となっているため連結状態であり，望ましい状態である．また，図 2 の右図は，センサが１つの構造木となっていないため，連結状態ではない．

• 必要なコストの増加• 環境に悪影響を与える可能性
そのため，領域に配置されるセンサ数は適量が望ましい．
領域の被覆とネットワークの構築を確保するセンサ数の計算は，過去にもされている [2]．しかし，[2] の研究の評価指標では実際より過大評価となっている．そのため，実用的なセンサ数の見積が出せない．また，他の研究の評価指標でも適量なセンサ数の見積が出せず，決定的な図 2 連結状態の例解法が見つからなかった．そこで，本研究では，センサネットワークの領域の被覆とネットワークの構築を確保
上記のカバー率と連結状態となることを考慮し，センするセンサ数の評価指標を作る．このとき，領域の被覆 サ数を計算する．また，計算を行う際には [2] の研究に注とネットワークの構築はそれぞれ別で考える．
目をし，研究を進める．

3

カバー率を考慮したセンサ数の決定

3.1

過去の研究

センサネットワークのカバー率のみに注目をして考える．ここではセンサのセンサ機能が届く範囲の半径（センサ距離）を rs とする．[2] では，領域内に一様にランダムで O( r3s log r3s + r1s log σ1 ) 個だけセンサを配置する場合を考えている．このとき，少なくとも (1 − σ) の確率で領域のほぼ全体が被覆されるとしている．

3.2

新しい評価指標の提案[4] の最近隣距離の分布関数によりカバー率を考慮したセンサ数の見積を行う．最近隣距離の分布は式 (1) の通りである．
2
F1 (rs ) = 1 − e−ρπrs(1)rt とする．[2] の研究では，連結状態となるのに必要なセンサ数を見積もるのに，式 (3) を利用している．
Pcon (rt ) = (1 − e−ρπrt )n2(3)式 (3) は，最近隣距離の最大値の分布を表している．最大値の分布とは，ある分布関数に従い n 個のデータをサンプリングしたときの最大値，を表す分布である．式 (3)は，n 個のセンサを密度 ρ で配置したとき，センサ間の最近隣距離の中で最大である長さを表す分布である．[2]の研究では，全てのセンサが半径 rt 以内に少なくとも１つは他のセンサがある状態であれば，センサが連結状態になると考えている．

4.2

最小木についてのシミュレーション

3.3

連結状態になる確率 (Pcon)

式 (3) によるセンサ数の見積の精度を，シミュレーショ
最近隣距離とは，「平面に点が分布しており，さらにこ ンにより確かめる．本研究では，センサにより最小木をの平面の任意の位置に点 Q をとり，点 Q から最も近い 構築し，その中で最大の枝長が r 以下であれば，センサt他の点までの距離 R」[4] のことをいう．式 (1) では，点 は連結状態であると考える．最大の枝長が r 以下であれtが密度 ρ でポアソン分布にしたがって分布している場合， ば，当然，全センサが距離 r 以下で１つの構造木となるt
半径 rs 以内に少なくとも１つは他の点がある確率を意味 からである．シミュレーションでは，センサを一様にラする．任意の点 Q から rs 以内に他の点があるというこ ンダムに配置し，最小木を構築する．その後，最小木のとは，相手の点から考えても rs 以内に点 Q は存在する． 中で最大の枝長を調べる．以上の試行を 10,000 回繰り返
つまり，式 (1) は点 Q が他の点が被覆している領域内に し，調べた枝長を累積して式 (3) と比較する．比較したある確率と考えられるので，式 (1) の確率がそのままカ 結果は，図 3 の通りである．図 3 はセンサの密度が 1,000バー率を表す．本研究では一定のカバー率を確保するの （個／領域面積）の場合である．に必要なセンサ数の見積を出すことが目的である．その1
ため，式 (1) をセンサ数の関数へ変形し，式 (2) を得る．
Pcov がカバー率，n がセンサ数，S は対象とする領域面0.8積である．
−S log (1 − Pcov )
0.6
n=(2)
πrs2
ρ=1,000
シミュレーションによる評価指標の性能の比較

0.4

最小木のシミュレーション

0.2[2] の研究と式 (2) で見積もったセンサ数でそれぞれカ最近隣距離の最大値の分布（式(3)）
バー率を求めるシミュレーションを行い，精度を確かめ
00.04
0.05
0.06
0.07
0.08
る．シミュレーションは，センサでボロノイ図を作り，セ通信距離(rt)ンサとボロノイ点間の角度とセンサ距離を利用し，面積を計算する．ここでは，面積を 1,000 回求めた結果の平図 3 最近隣距離の最大値の分布と均を使用する．比較した結果は表 1 の通りである．表 1
最小木についてのシミュレーションの比較
は，単位正方形を 99 ％被覆する場合である．表 1 から，
式 (2) が高い精度でセンサ数の見積が出来ている．その4.3 過去の研究の問題点と考察ため，カバー率を考慮するセンサ数の見積には，最近隣
図 3 より，式 (3) は最小木の最大の枝長より通信距離が距離の分布である式 (2) を使う．
短い分布である．よって，最近隣距離の最大値の分布で
表 1 領域の被覆に必要なセンサ数の見積の比較
は，センサが連結状態となることを示すことは難しいと
最近隣距離
過去の研究
センサ距離
考える．ここで，連結状態を表すことが難しいと考えら[rs]
センサ数 カバー率 センサ数 カバー率れる原因を２つ示す．
0.100
148.0898.12% 146.59
97.87%
0.075
0.050
0.025

208.95337.76758.7096.40% 260.60
91.73% 586.35
76.59% 2345.39

4連結状態となるセンサ数の決定

4.1

過去の研究

98.07%
98.33%
98.67%

センサネットワークが連結状態であるかのみに注目して考える．センサの通信可能な範囲の半径 (通信距離) を

4.3.1

最近隣の枝だけで連結状態とならない可能性

最小木を構成する枝が最近隣の辺だけではないことが，古山の研究 [1] により分かっている．実際には，最小木を構成する枝には第２近隣や第３近隣，それ以降の近隣辺も含まれる．そのため，最近隣距離の最大値の分布では，連結状態であることを示すことができない．ここで，シミュレーションにより最小木の枝の構成比を調べる．シ

ミュレーションでは，ランダム配置した点で最小木を作り，その最小木の枝が何番目に近い点を結んだ辺であるかの割合を調べる．各センサの密度に対し 10,000 回調べた結果の平均が表 2 となる．表 2 より，最近隣の辺は最小木の枝の７割程度でしかないことが分かる．また，最小木の枝の構成比はセンサの密度にほとんど左右されていない．
表 2 最小木を枝の構成比
センサの密度
100
1000
10000

169.64%68.97%
68.84%

第n近隣の辺の割合
2321.54%
6.55%
22.28%
6.70%
22.52%
6.70%の通りである．

F2 (rt ) = 1 − e−ρπrt − ρπrt2 e−ρπrt(4)−ρπrt2(5)2Pcon = (1 − e22− ρπrt2 e−ρπrt )n

境界の影響を考慮した最近隣距離の分布

4.4.2

センサを境界付近に配置すると，境界の外に通信可能な範囲が出る．通信可能な範囲の面積の変化に合わせ，図5 のように領域を分割して考える．式 (3) では確率全体か
rt

4以上
2.27%
2.05%
1.95%

rtrt

124.3.2

領域の境界の影響を考慮していない点

a34

最近隣距離の分布はポアソン分布にしたがっているため，対象領域は無限領域である．しかし，現実には対象領域は有限領域である．そのため，図 4 のような状態になる可能性がある．
境界外

境界内

境界外

境界内

rta

図 5 領域の分割

ら，面積 πrt2 内に点が１つもない確率を引いて計算をしている．ここで，面積 πrt2 を，領域の境界を考慮したときの，センサの通信範囲の面積の期待値として計算を行う．次に，配置されるセンサ数は，一様にランダムで配有限領域無限領域置することより，その領域の面積比に比例することを考慮する．各領域の面積と，その領域にセンサが配置され
図 4 境界による影響た場合の通信範囲の面積の期待値を式 (6)〜式 (13) に示
図 4 は，センサが無限領域と有限領域に配置された場 す．このとき，領域全体の一辺を a，領域 i = {1, 2, 3, 4}合の，最小木の構築方法の差を表す．図の各点はセンサ， の面積を Si ，領域 i にセンサが配置された場合の通信範
最小木の枝はセンサ間を線で繋いで表している．図 4 の 囲の面積の期待値を Ci とする．
左図では無限領域に配置されたセンサで最小木を構築しS1 = (a − 2rt )2(6)ている．図 4 の右図では，無限領域から領域を切り取り，その内部のセンサで最小木を構築している．そのため，領S2 = 4rt (a − 2rt )(7)
域の境界の外にあるセンサとは最小木を構築できない．つ2S3 = πrt(8)まり，境界付近のセンサは実際のセンサの密度よりも低
2S4 = (4 − π)rt(9)い状態になっていると考えられる．そのため，実際は無2
C1 = πrt(10)限領域で考えたときより遠いセンサ同士で構造木を作る
2ことになる．これより，無限領域の時よりも必要な通信
C2 = rt2 (π − )(11)3
距離が長くなる可能性がある．
rt2 2C=(π + 1)
(12)3
4.4 最近隣距離の分布を利用した評価指標の作成
2π2r2 (4π − π2 − 16
最小木の枝長の分布を計算することは非常に難しい．そ3 )C4 = t(13)のため，最近隣距離の分布を利用し，最小木の枝長に近4−πい分布を作ることでセンサ数の評価指標を作る．
式 (6)〜式 (13) を利用し，式 (3) を境界を考慮して変形すると，式 (14) の通りとなる．
4.4.1 第２近隣距離の分布
最近隣距離の最大値の分布では最小木の枝長より短い分布となった．そこで，第２近隣距離の最大値の分布を使用する．最近隣距離は最も近い点までの距離を表すが，第２近隣距離は２番目に近い点までの距離を表す．第２近隣距離の分布と，その最大値の分布は，式 (4)，式 (5)Pcon =4∏nSi

F1 (rt ) a2i=1=4∏nSi(1 − e−ρCi ) a2i=1(14)4.4.3境界の影響を考慮した第２近隣距離の分布

4.4.2 の境界の影響を考慮した計算を，4.4.1 の第２近隣距離の分布で行う．実際の分布は式 (15) に示す．
Pcon =4∏nSi

F2 (rt ) a2とき，センサの通信距離から，必要なセンサの密度の目安となるグラフを近似的に作る．実際には，式 (15) で確率が 99 ％となるようなセンサの密度を，通信距離を 0.01刻みで計算する．計算した値を基に曲線を描くことで，近似的に連結状態となるのに必要なセンサ数のグラフを作る．グラフは図 7 の通りである．

i=1=4∏nSi(1 − e−ρCi − ρCi e−ρCi ) a210000(15)

Pcon=0.99

i=18000

最小木の枝の構成比を利用した分布

センサ密度 (ρ)

4.4.4

最小木の枝の構成比を再現することを考えて，表 2 を利用する．実際には，センサ数の 69 ％を最近隣距離，22％を第２近隣距離，7 ％を第３近隣距離，2 ％を第４近隣距離の分布として計算する．計算した評価指標の分布は
式 (16) の通りである．また，各近隣距離の分布は式 (17)〜式 (20) の通りである．

6000

4000

2000

00.02

0.070.12

通信距離(rt)Pcon = F1 (rt )0.69n F2 (rt )0.22n
図 7 連結状態となるのに必要なセンサ数の目安

F3 (rt )0.07n F4 (rt )0.02n (16)F1 (rt ) = 1 − e−ρπrt2(17)2F2 (rt ) = F1 (rt ) − ρπrt2 e−ρπrt(ρπrt2 )2 −ρπrt2F3 (rt ) = F2 (rt ) −e(18)(19)

2(ρπrt2 )3 −ρπrt2eF4 (rt ) = F3 (rt ) −64.5(20)

各評価指標の比較と考察

各評価指標と最小木についてのシミュレーション結果を比較したグラフを図 6 に示す．

連結状態になる確率 (Pcon)

10.8

ρ=1,000

0.6

最小木シミュレーション
最近隣の最大値の分布

0.4

第2近隣距離の分布
境界を考慮

0.2

第2近隣で境界を考慮
最小木の構成比を考慮

00.04

0.05

0.06

0.07

0.08

通信距離(rt)

図 6 各評価指標と最小木シミュレーションの比較

5まとめ

本研究では，センサネットワークのカバー率と連結状態となることを考慮したセンサ数の評価指標を作成した．
カバー率を確保するために必要なセンサ数は，高い精度で見積を出すことができた．また，連結状態を確保するセンサ数の見積は，連結状態になる確率が 95 ％以上では高い精度で見積を出すことができた．
連結状態になる確率を最近隣距離の分布を使用し，より正確にセンサ数の見積を出すことは難しいと考える．そのため，より正確にセンサ数の見積を出すには，全く別の分布を作ること必要であると考える．また，本研究では対象とする領域を正方形としたが，現実には領域の形は様々な場合が考えられる．式 (15) では，正方形の領域でしか見積ができないので，一般化した評価指標を考える必要があると考える．

参考文献[1] 古山正雄：地域間ネットワークにおける最短結合と近隣結合に関する理論的考察．都市計画論文集 Vol.38-3，2003．
[2] Volkan Isler，Sampath Kannan，Kostas Daniilidis：Sampling Based Sensor-Network Deployment，Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems，Sendai
Japan，pp.1780-1785，2004.

図 6 のグラフの中で，境界の影響を考慮した第２近隣距離の分布だけが，最小木によるシミュレーションの結果を上から抑えることができている．また，連結状態となる確率が 95 ％以上では，かなり分布は近くなっている． [3] Ivan Stojmenovic:Handbook of Sensor Networks
そのため，本研究では，式 (15) の境界の影響を考慮した
Algorithms and Architectures，Wiley Interscience，第２近隣距離の分布を，連結状態となるのに必要なセン
2005.
サ数の評価指標とする．
[4] 谷村秀彦，梶秀樹，池田三郎，腰塚武志：都市計画数
本研究では連結状態となることを考慮したセンサ数の見理．朝倉書店，東京，1986.
積を出したい．しかし，式 (15) からセンサ数の関数を作ることは難しい．そこで，連結状態となる確率が 99 ％の