論

ユビキタスサービスを支えるネットワーキング技術論文特集

文

センサネットワークにおける耐故障性の高い確率的配置の実現
石塚 美加† a)

会田 雅樹†† b)

Stochastic Node Placement Improving Fault Tolerance in Wireless Sensor Networks
Mika ISHIZUKA†a) and Masaki AIDA††b)

あらまし センサノードは，屋外に放置されるため故障が発生しやすく，電池容量も少ないため，電池切れにより通信不能になる可能性も高い．したがって，ランダム故障，電池切れ故障によりセンサノードが通信不能になった場合でも，センサネットワークとしての性能を最大限維持できる（つまり，耐故障性の高い）ネットワー
ク技術が必要である．従来，電池切れ故障耐性を高めるために，センサのオン・オフ制御等によりセンサの電池
容量を最大限に生かす技術が検討されてきた．ランダム故障耐性，電池切れ故障耐性を向上させるためには，これらの制御に加えてセンサノードの配置技術の検討が必要である．しかし，従来の配置法に関する検討は，一つひとつのセンサノードの座標を決める確定的配置であった．確定的配置には，多数のセンサを広域に配置する場
合の配置コストが高く，実際のセンサノードの位置が規定の位置から外れた場合の影響も明確でないという欠点がある．確定的配置におけるこれらの問題を回避するためには，ノードの大体の位置を確率密度関数で決める確率的配置が有効である．そこで我々は，ランダム故障，電池切れ故障に対して高い耐故障性をもち，実現が容易な確率的配置法について検討してきた．以前の研究では，最初のステップとして，ノードの次数分布（隣接ノード数の分布）がべき分布に従うような確率的配置（べき配置）を提案し，耐故障性について評価を行った．その結果，べき配置のパラメータを適切に設定する（これは，べき分布の指数を調整することと等価である）ことにより，一般的な確率的配置よりも高い耐故障性を実現することを示した．本論文では，次のステップとして，高い耐故障性をもつだけでなく，実現も容易である確率的配置法を提案する．そのために，確率的配置がべき配置と同等の耐故障性をもつための条件を求め，最も簡単に実現できる確率的配置（単純拡散配置）の繰返しにより，求めた条件に合致する配置を実現する方法を提案する．
キーワード

センサネットワーク，耐故障性，確率的配置，拡散方程式維持できる，つまり耐故障性の高いネットワーク技術

1. ま え が きが必要である．

通信機能を有する省電力，小型センサにより構成さ省電力 MAC プロトコル，電池残量を考慮した経路

れるセンサネットワークは，広域での情報収集を可能

選択，センサのオン・オフ制御は電池切れ故障に対すにするため，様々な分野への応用が期待されている．

る耐故障性の向上に有効であり，数多くの研究が進め

センサノードは，屋外に放置されるため故障が発生しられてきた [1]〜[8]．ランダム故障耐性，電池切れ故障

やすく，電池容量も少ないため，電池切れにより通信耐性を高めるためには，これらの制御に加えて，すべ不能になる可能性も高い [9]．したがって，ランダムてのデータが基地局へ送信されることを考慮して，セ故障や電池切れ故障によりセンサノードが通信不能とンサノードの配置方法を工夫することが有効である．

なった場合でも，ネットワークとしての性能を最大限しかし，従来の配置方法に関する研究は一つひとつのセンサの座標を決める確定的配置 [9]〜[11] を対象と†††していた（図 1）．確定的配置は，一つひとつのセンサ

NTT 情報流通プラットフォーム研究所，武蔵野市
NTT Information Sharing Platform Labs., NTT Corpora-を決められた座標に置くので配置コストが高く，実際

tion, 3–9–11 Midori-cho, Musashino-shi, 180–8585 Japanのセンサ位置が規定の位置から外れた場合の影響も不首都大学東京，システムデザイン学部，日野市
Faculty of System Design, Tokyo Metropolitan University,

明である．そこで我々は，ノードの位置を確率密度関

6–6 Asahigaoka, Hino-shi, 191–0065 Japan

数により記述する確率的配置（図 2）を用いることにa) E-mail: ishizuka.mika@lab.ntt.co.jpb) E-mail: maida@cc.tmit.ac.jp

電子情報通信学会論文誌 B Vol. J88–B

より，確定的配置におけるこれらの欠点を緩和できるc （社）電子情報通信学会 2005
No. 11 pp. 2181–2191 

2181

電子情報通信学会論文誌 2005/11 Vol. J88–B No. 11

価ではないことを意味している．

•

最適化問題を数値的に解くことによりパラメー

タを決定しているため，決定変数が多い場合に，最適なパラメータを求める計算が，複雑かつ時間を要する．
図 1 確定的配置のイメージ
Fig. 1 Concept of deterministic node placement.

加えて大域的な最適解が求まる保証がない．
そこで，本論文では，最適化問題によるパラメータ
決定，シミュレーションによる妥当性の判断を行うことなく，単純拡散配置の繰返しにより，べき配置と同等の耐故障性をもつ配置を実現する方法を検討する．
そのために，べき配置が高い耐故障性を示す理由を理論的に考察し，確率的配置がべき配置と同等の耐故障性をもつための条件を求める．その上で，求めた条件に合致するように，単純拡散配置のパラメータを決定

Fig. 2

図 2 確率的配置のイメージ
Concept of stochastic node placement.

する方法を提案する．
本論文の構成は以下のとおりである．2. で，通信モ
デルと一般的な確率的配置と我々が提案するべき配置と考え，ランダム故障，電池切れ故障に対して高い耐を説明する．3. では，耐故障性の評価方法，確率的配故障性をもち，実現が容易な確率的配置法について検置の耐故障性を評価した結果を，文献 [17] に基づき説討してきた．

明する．更に，これらの結果をもとに，べき配置が高まず最初に文献 [17] で，ノードの次数分布（隣接い耐故障性を示す理由を考察し，確率的配置がべき配ノード数の分布）がべき分布に従う確率的配置（べき置と同等の耐故障性をもつための条件を求める．4. で配置）を提案し，シミュレーションにより耐故障性のは，べき配置と同等の耐故障性をもつ確率的配置を単評価を行った．その結果，べき配置はパラメータを調純拡散配置の繰返しにより実現する方法を提案する．

節する（これは，べき分布の指数を調節することとまず最初に，単純拡散配置の繰返しに関する理論的背等価である）ことにより，一般的な確率的配置よりも景を説明した後，3. で求めた条件に合致する単純拡散

高い耐故障性を示すことを示した．次に，べき配置

配置のパラメータを求める方法を提案する．5. では，を簡単に精度良く実現する方法について，検討を行っ数値例により提案方法の妥当性を検証する．最後に，た [18], [19]．これらの検討では，任意の確率的配置は，

6. でまとめを行う．

空中の一点からセンサノードを拡散させるという最も簡単な配置法（単純拡散配置）の繰返しにより実現で

2. 準

備

きるという理論的背景 [12] に基づき，単純拡散配置の

2. 1 通信モデル

繰返しにより実現される確率密度関数（近似密度関数）

本論文で扱うセンシングプロセスを図 3 を用いてとべき配置の確率密度関数の平均二乗誤差を最小化す説明する．本論文では，センシング対象の位置が事前る最適化問題を解くことにより，各々の単純拡散配置に分からないアプリケーション（例，森林での動物ののパラメータを求めていた．しかし，このパラメータ

探索）を想定し，センシング対象は領域 D 内のラン決定方法には次のような問題があった．

•

ダムな位置に発生するとし，センサノードも領域 D

同じ平均二乗誤差となる配置でも，異なる耐故内に配置されるとする．領域 D は，基地局を中心と障性を示す．したがって，得られたパラメータの妥当する円領域を仮定する．各センサノードは，検知可能性を判断するために，別途シミュレーション評価を必距離（sensing range）内に存在するセンシング対象

要とし，パラメータ決定に時間がかかる．加えて，パのみ検知できる．また，センサノードは通信可能距

ラメータの妥当性をシミュレーション評価により検証

離（radio-transmission range）内に存在するセンサするため，評価条件が異なる場合の妥当性が不明であノードに対してのみ，データを送受信することができる．これは，平均二乗誤差を最小化することは，べきる．センシング対象が発生すると，センシング対象を配置と同等の耐故障性をもつ配置を実現することと等検知可能なすべてのセンサノードが一定期間，基地局

2182

論文／センサネットワークにおける耐故障性の高い確率的配置の実現

度一定配置）とべき配置について説明する．
確率的配置では，センサ位置は確率密度関数で定義される．極座標系 (r, θ) における，センサ位置の確率密度関数を f (r, θ) と表す（注 1）．センサノードは基地局を中心とする半径 R の円領域 D に配置されるとする．
すべてのセンサノードが領域 D 内に配置される場合，

D

f (r, θ)dθdr = 1 が成り立つ．なお，特に断らない限り，基地局の位置を原点とする．
単純拡散配置 最も簡単に確率的配置を実現する方法は，基地局の真上からセンサノードを拡散させる方法である．本論文では，この配置法を単純拡散配置と
図 3 センシングプロセスの例
Fig. 3 Sensing and transmitting data.

呼ぶ．センサノードは非常に軽く，空中から拡散させるときには十分に大きな空気抵抗を受けると考える．
このとき，空気の流れが十分に弱いとすると，センサに向けてセンシング情報を送信する．センサノード

ノードは拡散方程式に従って分布する．拡散方程式のと基地局間の経路は，ホップ数が最短となるものを選解は，二次元正規分布となるため，単純拡散配置のセ択する．なお，本論文の通信モデルはアグリゲーショ

ンサノードの位置の確率密度関数 fs (r, θ) は次のようン制御 [14], [15] を前提としていない．アグリゲーショに書ける．

ン制御は電池切れ故障耐性の向上に有効であるが，文献 [14] で述べられているようにアグリゲーション制御の効果が得られるアプリケーションは限定されること，
文献 [15] のようにセンサが同期して発呼するアプリ
ケーション以外ではアグリゲーションのための遅延が発生するため，アグリゲーション制御が有効な状況も限定されることから，アグリゲーション制御を前提としない本論文の通信モデルも十分実用的である．
センサノードは，センシング情報を送受信するたびにデータ量に比例した電池エネルギーを消費する．センサノードは，初期電池エネルギーを使い切ると通信不能となる．センシング情報の送信中に，中継センサ
ノードが通信不能になった場合，代替経路が存在すれば，経路の切換を行う．

2. 2 記号の定義
2. 1 の通信モデルに基づき，以下のように記号を定義する．

R：領域 D の半径
Sr ：検知可能距離
T ：通信可能距離
N ：センサ数
Er：単位データ量受信時に消費する電池エネルギー
Et：単位データ量送信時に消費する電池エネルギー
EI ：初期電池エネルギー
2. 3 センサノードの確率的配置
ここでは，一般的な確率的配置（単純拡散配置，密Cr
h0 (r; σ),
2πσ 2


r2

h0 (r; σ) = exp − 2 ,2σfs (r, θ) =

C=

1



2

R
1 − exp − 2σ
2

(1a)
(1b)

 , 0 ≤ r ≤ R.

(1c)

式 (1) において σ 2 は分散を表す．σ 2 はセンサノー
ドの形状，重さ，センサノードを拡散させる高度等により決まる．空気の流れが強い場合は，拡散方程式に空気の流れを加味する必要があるが，このような場合
は検討の対象外とする．
密度一定配置 センサネットワークにおける多くの研究では [3], [6], [7], [16]，センサ密度が一定となる配置を用いている．この配置を密度一定配置と呼ぶ．
べき配置 べき配置は確率密度関数 fp (r, θ; α) がr/R の α 乗に比例する配置で，次式で定義される．

 

α+1 r α,2πR R
0 < r ≤ R, 0 ≤ θ < 2π.

fp (r, θ; α) =(2)

式 (2) は，直感的には半径 r に存在するセンサ数がr/R の α 乗に比例することを意味している．確率密度
f (r, θ; α) = 1 を満たす
D p

関数 fp (r, θ; α) は，条件

（注 1）：セ ン サ が 領 域 X = {r1 ≤ r ≤ r2 , q1 ≤ θ ≤ q2 }に 存 在 す る 確 率 は ，確 率 密 度 関 数を 用 
いて以下のように書ける．
r2q2
P {r1 ≤ r ≤ r2 , q1 ≤ θ ≤ q2 } =f (r, θ)dθdr ．
r1

q1

2183

電子情報通信学会論文誌 2005/11 Vol. J88–B No. 11

Fig. 4図 4 各種確率的配置の確率密度関数
Examples of p.d.f. for various placements.

必要があるので，−1 < α である．

D に配置されるとした．単純拡散配置の密度は基地局

べき配置は，二つの特徴をもつ．一つは，センサに近いほど高く，基地局から離れるにつれて徐々に低ノードの密度が基地局に近いほど高いことである．実

下し，領域 D の境界近傍で急激に小さくなる．領域

際，位置 (r1 , θ1 ) におけるセンサ密度 ρ(r1 , θ1 ; α) は次

D の境界近傍の密度は，単純拡散配置が一番小さい．

のように書ける．

べき配置の密度も，基地局に近いほど高く，基地局の近傍で急激に低下する．しかし，領域 D の境界近傍

ρ(r1 , θ1 ; α) r1 +δr  θ1 +δθr1= lim lim

θ1の密度は単純拡散配置よりも大きい．α の値が小さい

fp (r, θ; α)dθdr

ほど，基地局近傍の密度が大きく，領域 D の境界近傍

δr→0 δθ→0 S(r1 ≤ r ≤ r1 + δr, θ1 ≤ θ ≤ θ1 + δθ)

α + 1 r1α−1.
=
2π Rα+1(3)

ここで，S(a ≤ r ≤ b, c ≤ θ ≤ d) は領域 X = {a ≤での密度が小さい．密度一定配置は，密度に偏りがな
いため，領域 D の境界近傍での密度が一番大きい．

3. 確率的配置と耐故障性の関係r ≤ b, c ≤ θ ≤ d} の面積を表す．二つ目の特徴は，

3. 1 耐故障性の評価方法

ノードの次数分布がべき分布に従うことである．セン

次に，ランダム故障，電池切れ故障発生時のセンサ

サノードは，通信可能距離内に存在するセンサノード

ネットワークとしての性能（耐故障性）を評価するたとのみ通信を行う．よって，通信可能距離に比べて領めの評価尺度と評価シナリオについて説明する．

域 D が十分に大きい場合，ノードの次数分布の漸近

センシング対象から検知可能距離内に少なくとも一的挙動は，通信可能距離内に存在するセンサノード数つのセンサノードが存在し，これらのセンサノードのの確率密度関数で書き表せる．この場合，ノードの次中の少なくとも一つが基地局への経路をもっている場

数分布 g(x; α) は，次のように計算できる．

合に，“センシングは成功である” と定義する．

g(x; α) =

d
dx

∝x

 

2
α−1

センサネットワークの性能を測る評価尺度としては，

fp (r, θ; α)drdθ

仮想センシング成功率を用いる．仮想センシング成功

ρ(r1 ,θ1 ;α)≤x2，2πR < x．
2α−1率は，領域 D 内に一様に発生するセンシング対象に(4)ついてのセンシングが成功する確率であり，任意時点に比例し，べき配置はの センシング成功率（耐故障性）を評価できる．な

α < 1 とすることにより，ノードの次数分布がべき分

お，本論文の主眼は耐故障性の高い配置方法の実現で布に従うことが分かる．

あることから，スループット等のトラヒック特性は評式 (4) より，g(x; α) は x

各々の確率的配置の特徴を，確率密度関数のグラフ

価尺度としていない（注 2）．

により説明する（図 4）．この図において，R = 500 mとした．単純拡散配置については，99% のセンサノー
ドが領域 D に配置されるように分散を設定した．その他の配置については，すべてのセンサノードが領域
2184（注 2）：トラヒック特性には，アクティブな隣接ノード数が大きな影響を及ぼす．本論文の通信モデルでは，センシング対象を検知可能なセン
サ数が同数の場合，アクティブな隣接ノード数は配置方法に依存せず，
トラヒック特性も配置によらない．

論文／センサネットワークにおける耐故障性の高い確率的配置の実現

1. で述べたように，故障の種類としては，ランダム
故障と電池切れ故障を扱う．

サが電池切れを起こすと，残りの基地局近傍のセンサ
は中継ノードとして使われる可能性が更に高まり，電ランダム故障耐性の評価では，故障ノード数の割

池消費速度が早まる．つまり，基地局近傍で電池切れ

合 rb を変化させて仮想センシング成功率を評価する．

となるセンサが発生し始めると，基地局近傍で電池

各々の rb に対応する数のセンサノードをランダムに切れとなるセンサ数が加速度的に増えていく．この現選び，故障ノードとする．

象により，基地局近傍のセンサ密度の経路存在率に対電池切れ故障耐性については，センシング対象が領
域 D 内に一様に発生する状況のもとで，センシング対する寄与は，電池切れ故障耐性に対して特に顕著であった．

象の発生数と仮想センシング成功率の関係を評価する．

これらの結果から，検知可能率を劣化させない程度

センシング対象が発生すると，センシング対象から検に，基地局近くのセンサ密度が高い配置が，ランダム

知可能距離内に存在するすべてのセンサが，センシン

故障，電池切れ故障に対して高い耐故障性を示すと考グ期間（ts ）中，一定時間（TD ）ごとに一定量（V ）えられる．

のセンシングデータを送信する．ts は，指数分布に従

密度一定配置は，センサ密度が一様なので検知可能

うとする．一つのセンシング対象のセンシング期間が率は高い．しかし，基地局近くの密度が高くないので，終了してから tI 後に，次のセンシング対象が発生す

ランダム故障，電池切れ故障発生時に経路存在率が維る．tI も指数分布に従うとする．電池切れ故障耐性の持できない．単純拡散配置は，基地局近傍の密度が高評価では，センサノードはデータを送受信するごとにいのでランダム故障，電池切れ故障発生時の経路存在

電力を消費するので，センシング対象の発生数が増加

率は高い．しかし，分布の裾の部分で急激に密度が低するにつれて，電池切れ故障により通信不能になるセ下するので，基地局から離れた領域での検知可能率がンサノード数が増えていく．

低い．べき配置については，α を大きくするにつれてなお，通信モデル，評価シナリオにおけるパラメー

基地局近傍の密度が小さくなる．したがって，α が大タの中で，各確率的配置の耐故障性の優劣を比較する

きいほど，検知可能率が高く，ランダム故障，電池切際に影響をもつパラメータは，N ，Sr と T の比であれ故障発生時の経路存在率が低い．両確率をバランスる．したがって，文献 [17] では，N ，Sr と T の比の良く保つ α を用いることにより，ランダム故障，電池

みを変化させて評価を行った．

切れ故障に対して高い耐故障性が実現できる．

3. 2 耐故障性の評価結果の概説

3. 3 べき配置の耐故障性についての考察

本節では，文献 [17] で，各確率的配置の耐故障性を前節で説明したシミュレーション結果を踏まえ，べシミュレーションにより評価した結果を説明する．

き配置の耐故障性について考察する．

センシング成功率を高めるためには，センシング対センサの故障が発生した場合でも経路存在率を維持

象から検知可能距離内にセンサが存在する確率（検知するためには，センサの故障により断たれる経路の数

可能率）と，検知可能センサの中の少なくとも一つがを小さくする，つまり中継経路が重複しないようにす基地局への経路をもつ確率（経路存在率）の両方を高る必要がある．そのためには，基地局からの距離 r にめる必要がある．

存在するセンサと同数以上のセンサを基地局からの距

検知可能率が高いのは，センサ密度が一様な配置で離 r − T に配置するとよい（図 5）．ここで，次ホップある．一方，センサ故障発生時の経路存在率が高いのの位置を r − T とするのは，中継ノード間の距離を極

は，基地局に近いほどセンサ密度が高い配置であり，力大きくすることにより，有限個のセンサを効率的にこの特性はランダム故障，電池切れ故障に共通であっ配置できるからである．

た．これは，すべての情報が基地局に向けて送信されこの条件を式で表すと次のようになる．

るため，基地局近くのセンサが中継ノードとして使用

f (r, θ) − f (r − T, θ) ≤ 0, ∀T ≤ r ≤ R.

される可能性が高い，つまり基地局近くのセンサ密度
は，経路存在率に対する寄与が大きいためである．特(5)∂べき配置は，α ≤ 0 の場合， ∂r
fp (r, θ; α) ≤ 0 なので，に，電池切れ故障耐性の評価では，基地局近傍のセン式 (5) が任意の T について成り立つ．これは，べき配サの使用頻度が高いことにより，基地局近傍のセンサ

置は，α ≤ 0 の場合に限り，経路存在率を維持できる

は電池切れを起こしやすい．一部の基地局近傍のセンことを意味している．前節でも述べたように，α を小2185

電子情報通信学会論文誌 2005/11 Vol. J88–B No. 11

Fig. 5図 5 経路存在率維持のための条件
Maintaining a route to the base station.

さくするほど，中継経路上のセンサが故障した場合に代替経路となるセンサが存在する確率が高くなるが，

図 6 検知可能率の計算
Fig. 6 Calculating cover ratio.

基地局から離れた領域でのセンサ密度が低くなり，検知可能率が低下する．したがって，経路存在率を維持できる α の中で最も大きな値 α = 0 を用いることに経路存在率を維持するための条件 (6) は，基地局により，経路存在率を損なわずに検知可能率を最大化で近いほど，センサ密度を高くすることを意味している．

きる．つまり，両確率のバランスを最も良く保てるべ

しかし，基地局近傍の密度が高すぎると，基地局からき配置のパラメータは α = 0 だといえる．

離れた領域でのセンサ密度が低くなり検知可能率が低文献 [17] の評価では，α > 0 のべき配置は経路存在下する．基地局から離れた領域での検知可能率を維持

率を維持できず耐故障性が低かった．また，ランダムするためには，領域 D の境界近傍の密度に制約を設

故障，電池切れ故障の両方に対して検知可能率と経路ける必要がある．そこで，領域 D の境界における検存在率を維持できる α は，α = 0, −0.1 であった．こ知可能率が，同領域における α = 0 のべき配置の検知

れらの結果は，上に述べた考察と合致している．

可能率とほぼ同等になるように，R − 2Sr ≤ r ≤ R に

3. 4 べき配置と同等の耐故障性をもつための条件

存在するセンサ数を決める（図 6 参照）．具体的には，前節での議論を踏まえ，本節では，確率的配置 f (r, θ)R − 2Sr ≤ r ≤ R に存在するセンサ数の下限を以下が α = 0 のべき配置 fp (r, θ; 0) と同等の耐故障性をもの式で与える．

 R

つための条件を求める．
経路存在率を維持するための条件は，式 (5) で与えられる．ここで，式 (5) を取扱いが容易な式に書き換 r+δr= lim

r+δr−Tf (t, θ)dt −

∂
∂r

r
r−T

 2π

 r

f (t, θ) dt ≤ 0 ∀T ≤ r ≤ R． (6)以降の議論では，経路存在率を維持するための条件として式 (6) を使用する．
ら 1 ホップの領域）のセンサ数については，べき配置と同数以上のセンサが存在すればよい．したがって，
式 (6) の初期条件は，次のように与えられる．

fp (r, θ; 0) dr ．

(9)

ここで，P0 (N ) は，r = R − Sr における α = 0 のべ発生時に，故障ノード数にかかわらず，r = R − Sr における検知可能率の差が Θ 以下であることを表している．
次に，条件 (9) から γ が満たすべき条件を求める．

 T
0P0 (N ) − P (N ) ≤ Θ ∀N > 0．

き配置の検知可能率を表す．式 (9) は，ランダム故障

式 (6) の初期条件，つまり r < T の領域（基地局かf (r, θ) dr ≥(8)

r = R − Sr における検知可能率 P (N ) がすべてのN (> 0) について次の条件を満たすように決める．

r−T

 T

f (r, θ)dθdr ．
0

式 (8) における γ の値は，センサ数が N の場合の，f (t, θ)dt

δr

δr→0

2186

 R

0

R−2Sr

f (r, θ) − f (r − T, θ)0

fp (r, θ; 0)dθdr
R−2Sr

≤

える．

=

 2π

γ

(7)

まず，センサ数が N の場合の，r = R − Sr における検知可能率 P (N ) を計算する．P (N ) は，基地局を中論文／センサネットワークにおける耐故障性の高い確率的配置の実現

心とする半径 R − Sr の円の円周が R − 2Sr ≤ r ≤ Rに存在するセンサの検知可能領域で覆われる割合を表−1
  γ−11γγ
  γ−1

1
γ

+

≤Θ

(15)

す（図 6）．
基地局からの距離 r に存在するセンサの検知可能領域が基地局を中心とする半径 R − Sr の円の円周を切り取る弧の長さを l(r) とする．l(r) の平均 1/µ は次

1
=
µ

 2π

l(r) 0
R−2S

Rr

 2π

R−2Sr

と次のようになる．

 R

f (r, θ)dθdr(10)．

fp (r, θ; 0) dθdr
R−2Sr

 R

ここで，R − 2Sr ≤ r ≤ R での確率密度の変化が十分

R
R−2Sr

R
R−2Sr

−

(11)

．

1
  γ−1∂∂rl(r)dr は半径 Sr の円の面積なので

1γγ
  γ−1

1
γ

+

≤ Θ，

f (t, θ) dt ≤ 0 ∀T ≤ r ≤ R，
r−T

(16b)
(16c)

 T

f (r, θ) dr ≥

(12)

(16a)

0

 r

 T

πSr
1
πSr2
=
≈
.
µ
2Sr
2

 2π
f (r, θ) dθdr ，

R−2Srl(r)dr2Sr0≤に小さく一定とみなせると仮定すると

1
≈
µ

 2π

γ

f (r, θ)dθdr0以上の議論より，確率的配置 f (r, θ) が α = 0 のべき配置と同等の耐故障性をもつための条件を整理するのように計算できる．

Rを満たす γ を用いることにより，条件 (9) が満たされる．

fp (r, θ; 0) dr ．

0

(16d)

0

センサは角度方向にランダムに配置されるので，基地局を中心とする半径 R − Sr の円の円周と検知可能領域が交わるセンサの数は，平均サービス時間 µ1 のM/G/∞ における系内客数とみなせる．ここで，平R
 2π
均到着間隔 λ1 は，n = N R−2S 0 f (r, θ)dθdr 個
rのセンサが長さ 2π(R − Sr ) の円周上にランダムに配2π(R−Sr )置されるので， λ1 =となる．M/G/∞ の系
n
内客数分布は，サービス時間分布に依存にしない [20]．

4. 単純拡散配置の重ね合わせによる実現
本章では，前章で求めた条件を満たす確率的配置を
単純拡散配置の重ね合わせにより実現する方法を提案する．単純拡散配置は，空中の一点からセンサを拡散させることにより実現でき，確率的配置を最も簡単に実現できる方法だと考えられる．したがって，単純拡したがって，P (N ) は，M/M/∞ において系内客数が散配置を用いた実現を検討することは，実現容易性の0 でない確率として計算できる．つまり，観点からも合理的である．

λP (N ) = 1 − exp −µ

最初に，理論的側面から単純拡散配置の重ね合わせSr n= 1 − exp −4(R − Sr )ここで，n0 = N

R
R−2Sr

4. 1 理論的背景



 2π
0

による実現の妥当性を説明する．



単純拡散配置では，センサ位置の確率密度関数は二

(13)

．

次元正規分布となる．二次元正規分布は基底関数とな

fp (r, θ; 0)dθdr とおくと，式 (8)，(13) より，

P0 (N ) − P (N )

≤ − exp −のように書ける [12]．

FX (x) =

Sr n0
Sr γn0+ exp −．
4(R − Sr )4(R − Sr )(14)

式 (14) の右辺の最大値は，−ある．したがって，り得るため，直交座標系の任意の関数 FX (x) は，次1 1  γ−1γ+γ
 1  γ−1γp(c, σ)h(x; c, σ)dcdσ,h(x; c, σ) = exp −

x−c
2σ 2

(17a)


.

(17b)

式 (17) において，p(c, σ), c, σ 2 は，各々の正規分
で布の重み，中心，分散を表す．この式は，無限に単純
拡散配置を重ね合わせることにより任意の確率的配置2187

電子情報通信学会論文誌 2005/11 Vol. J88–B No. 11が実現できることを示している．しかし，実現容易性を考慮すると，無限回の重ね合わせは現実的ではない．
そこで，式 (17) の積分を有限個の和に置き換える．この場合，式 (17) は次のように書き換えられる．


(19b)

．

はじめに，条件 (16) を満たすような式 (19) のパラ
メータ (M, p, σ) を求めるための方針を説明し，次に具体的なパラメータ決定手順を説明する．

M

FX (x) ≈



pi r
r2
Fi (r, θ) =exp − 222πσi
2σipi (ci , σi )h(x; ci , σi ),i=1

x − cih(x; ci , σi ) = exp −
2σi2

(18a)

［パラメータ決定方針］

•


.

(18b)

式 (18) において，pi (ci , σi ), ci , σi2 は各々の正規分
布の重み，中心，分散を表す．また，M は重ね合わせの個数を表す．なお，式 (18) の精度は [13] で議論されている．

ま ず は じ め に ，条 件 (16b) を 満 た す γ を

決 め る ．求 め た γ に 対 し て ，F (r, θ; 1, p1 , σ1 ) =F1 (r, θ) が条件 (16a) を満すように {p1 , σ1 } を決める．F (r, θ; M, p, σ) ≥ F (r, θ; 1, p1 , σ1 ) なので，この条件から求めた {p1 , σ1 } を用いて F (r, θ; M, p, σ)を構成することにより，条件 (16a) が満たされる．
• 基地局からの距離 ri ≤ r の範囲で条件 (16c)を満たすように {pi , σi , ri } を決める．具体的には，

r

4. 2 パラメータ決定方法
有限個の単純拡散配置の重ね合わせにより，α = 0のべき配置と同等の耐故障性をもつ配置を実現することは，式 (18) のパラメータ (M, pi , ci , σi ) を式 (16)を満たすように決定することと等価である．本節では，これらのパラメータの決定方法について述べる．実現∂
σi < σi−1 ，ri < ri−1 とし，∂r
F (t, θ; i, p, σ) dt
r−T
が r = ri で 0，ri < r における最大値が 0 以下になるように {pi , σi , ri } を i の昇順に決める．
これを式で表すと，次のようになる．

Dj (r, θ) =容易性を考えると，センサの拡散操作の回数が少なく，拡散の中心の座標に何らかの規則があることが望まし

∂
∂r

 r

Fj (t, θ) dt

(20)

r−T

とおくと，

い．これらの条件を考慮し，最も簡単な実現方法として，すべての単純拡散配置の中心を基地局の真上に置くことを考える（本論文では，これを中心固定配置とi

Dj (ri , θ) = 0，呼ぶ）．これは，M 種類の異なる質量，形状の（つまり，σi が異なる）センサノードを基地局の真上から一度に拡散させることに相当する．センサの質量，形状

(21a)

j=1
i

Dj (r, θ) ≤ 0．

max
ri <r

(21b)

j=1

の変更は，センシングや通信に関する機能を変更することなく実現できるため，十分に現実的，簡単である．
なお，実際の質量，形状の設定については，散布の事
前の実験により決める必要があるが，このようなエア

図 7 に，条件 (21) により決まるi
Dj (r, θ) の
j=1

例を示す．

•

条件 (16d) を考慮して，

ロダイナミックな問題は本論文の検討の範囲外とする．
単純拡散配置によりセンサノードが到達可能な領域には上限があるため，この方法はセンサノードを配置する領域が比較的狭い場合に適用可能な方法である．ただし，以降で説明するパラメータ決定方法は，拡散の中心が基地局の真上以外にある場合にも応用することが可能である．
極座標系での中心固定配置の確率密度関数

F (r, θ; M, p, σ) を以下に示す．
M

F (r, θ; M, p, σ) =
i=1

2188

図7

Fi (r, θ)，(19a)Fig. 7ij=1

Dj (r, θ) の決定例（i = 2, 3）

Examples forij=1

Dj (r, θ) (i = 2, 3).

論文／センサネットワークにおける耐故障性の高い確率的配置の実現

 T

 T
F (r, θ; i, p, σ) dr ≥0

fp (r, θ; 0) dr (22)0を満たす最小の i を M とする．
［パラメータ決定手順］

γ を，式 (16b) から計算する．{p1 , σ1 } は，F1 (r, θ)が次の条件を満たすように決める．

 R

 2π

 R

0

=

F1 (r, θ) dθdr ，

(23a)

0

max F1 (r, θ) = F1 (σ1 , θ) = fp (σ1 , θ; 0)． (23b)rことを意図している．条件 (25) だけでは，パラメータ{σi , ri , Ri } は決まらないので，センサ数 (pi ) は少ない方がよいという条件を考慮して，p(σi , ri ) を σi に

(26)

条件 (25)，(26) を満たすような {σi , ri , Ri } を数値的に求める．条件 (22) が満たされるまで，（step 2）を繰り返す．

（step 2） i := i + 1 とする．式 (21) を満たすような {pi , σi , ri } を求める．
き，pi を {σi , ri } の関数 p(σi , ri ) として表すことにより考慮する．
i
Dj (r, θ) は ri ≤ r で複数の極値をもつため，
j=1

条件 (21b) を満たすパラメータを解析的に求めるのは難しい．そこで我々は，以下のようなヒューリスティックを用いる．

5. 数 値 例
文献 [17] と同様に次の三つの場合について，提案方

条件 (21a) については，式 (21a) を pi について解i−1
Dj (r, θ) を直線 Li−1 (r) = ai−1 r+bi−1j=1で近似する．{ai−1 , bi−1 } は次の条件を満たすように決める（図 8）．

•
•

(25b)

∂
p(σi , ri ) = 0．
∂σi

 2π

R−2Sr

G(Ri , θ) = 0．

関して最小化する条件を追加する．

fp (r, θ; 0) dθdr
R−2Sr

(25a)

この条件は，G(r, θ; i) が r = Ri で極大値 0 をとる（step 1） i = 1 とする．事前に決めた Θ に対応する

γ∂
G(r, θ; i)
= 0，
∂r
r=Ri

法により中心固定配置のパラメータを求め，耐故障性を評価する．

case #1： Sr = 60 m，T = 100 m，N = 250．
case #2： Sr = 60 m，T = 100 m，N = 400．
case #3： Sr = 30 m，T = 100 m，N = 400．
条件 (16b) における Θ は 0.1 とした．条件 (16) は Nに依存しないので，case#1 と case#2 については，同じ確率密度関数が得られる．前節の方法により求めた
確率密度関数を図 9 に示す．次に，これらの確率的配i−1

r = ri−1 で j=1 Dj (r, θ) と交わる．
i−1r < ri−1 で j=1 Dj (r, θ) に接する．
i
この Li−1 (r) を用いて， j=1 Dj (r, θ) を次のような
関数 G(r, θ; i) で近似する．
G(r, θ; i) = Li−1 (r) + Di (r, θ)．

(24){σi , ri , Ri } を，次の条件を満たすように決める．

Fig. 9図 9 中心固定実現の確率密度関数（極座標）
Plots of approximated p.d.f. (polar coordinates).
表 1 シミュレーション条件
Table 1 Parameters setting.

図 8 パラメータ決定手順（step 2）の例（i = 2）
Fig. 8 An example of (step 2) at i = 2.

Parameters in Sect. 2.2.
R
500 m
Er 1.5e-07 J/bit
Et 2.5e-07 J/bit
EI 20 J

Parameters in Sect. 3.1.
ts
72 min
TD 18 sV
2560 Byte
tI
250 s

2189

電子情報通信学会論文誌 2005/11 Vol. J88–B No. 11

図 10 仮想センシング成功率（ランダム故障）
Fig. 10 Virtual sensing success ratio (random failure).

Fig. 11

図 11 仮想センシング成功率（電池切れ故障）
Virtual sensing success ratio (battery exhausion).

置の耐故障性をシミュレーション評価により検証する．
シミュレーション条件は，すべて文献 [17] と同じにし

6. む す び（表 1 参照），すべての評価は 15 回行った．比較のた

本論文では，ランダム故障，電池切れ故障に対してめに，単純拡散配置（simple diﬀusion），密度一定配高い耐故障性をもち，実現も容易な確率的配置法を提置（constant）の結果も併せて示す．電力消費に関す案した．そのために，べき配置が高い耐故障性を示す

るパラメータについては Et ，Er の比が意味をもつ．

理由を理論的に考察し，確率的配置がべき配置と同等

この比については，文献 [16] と同じ値を用いた．ただの耐故障性をもつための条件を求めた．更に，最も簡

し，文献 [4], [5] 等の制御が理想的に動作して通信に無単に実現できる確率的配置（単純拡散配置）の繰返し

関係な電力消費が発生しない状態を想定し，非通信時により，求めた条件を満たす配置を実現する方法を提の消費電力を 0 に変更した．また，送信トラヒックパ

案した．提案方法を用いることにより，べき配置と同ターンは耐故障性に影響がないため固定パラメータと等の高い耐故障性をもつ確率的配置を実現できることした．

を数値例により確認した．

ランダム故障耐性の評価について，故障センサノー

本論文の確率的配置は二次元空間を前提としていた．

ドの割合と仮想センシング成功率の関係を図 10 に示

高度を考慮した確率的配置，単純拡散配置の繰返しのす．また，電池切れ故障耐性の評価について，センシ適用が今後の課題である．
文

ング対象の発生数と仮想センシング成功率の関係を
図 11 に示す．これらのグラフより，前章の手順によ[1]

protocol and algorithm design for energy-eﬃcient

置と同等の耐故障性をもっていることが分かる．図 11

wireless sensor networks,” Proc. ACM MobiCom ’01,において，センシング対象の発生数が多い領域で，近pp.272–286, July 2001.
[2]

べき配置より多くなっているためである．

A. Woo and D. Culler, “A transmission control
scheme for media access in sensor networks,” Proc.

成功率を若干上回っているのは，条件 (16d) より，基地局から 1 ホップ内に存在するセンサ数が，α = 0 の

E. Shih, S.H. Cho, N. Ickes, R. Min, A. Sinha, A.
Wang, and A. Chandrakasan, “Physical layer driven

り求めた確率的配置（近似配置）は，α = 0 のべき配似配置の仮想センシング成功率が α = 0 のべき配置の

献

ACM MobiCom ’01, pp.221–235, July 2001.
[3]

K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie,“Protocols for self-organization of a wireless sensor
network,” IEEE Pers. Commun., vol.7, no.5, pp.16–
27, Oct. 2000.

2190

論文／センサネットワークにおける耐故障性の高い確率的配置の実現[4]pp.2511–2520, Sept. 2004.

B. Chen, K. Jamieson, H. Balakrishnan, and R.
Morris, “Span: An energy-eﬃcient coordination algo-[18]

works,” Wierel. Netw., vol.8, no.5, pp.481–494, Sept.
2002.
[5]

[19]

X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, and C.

Conference on Embedded Networked Sensor Systems(SenSys), pp.28–39, Nov. 2003.
[6]

M. Ishizuka and M. Aida, “Achieving power-law
placement in wirless sensor networks,” Proc. ISADS

Gill, “Integrated coverage and connectivity conﬁguration in wireless sensor networks,” Proc. First ACM

石塚美加，会田雅樹，“センサーネットワークにおけるべ
き配置の実現方法に関する検討,” 信学技報，IN2004-103,
Nov. 2004.

rithm for topology maintenace in ad hoc wireless net-

2005, pp.661–666, April 2005.
[20]

R.W. Wolﬀ, Stochastic Modeling and the theory ofqueues, Prentice Hall, 1989.

（平成 17 年 2 月 25 日受付，6 月 14 日再受付）

W.R. Heinzelman, J. Kulik, and H. Balakrishnan,“Adaptive protocols for information dissemination in
wireless sensor networks,” Proc. ACM MobiCom ’99,
pp.174–185, Aug. 1999.

[7]

W.R.

Heinzelman,A.

Chandrakasan,

and

H.

Balakrishnan, “Energy-eﬃcient communication pro-[8]

美加 （正員）tocol for wireless microsensor networks,” Proc. IEEE平 4 慶大・理工・計測卒，平 6 同大大学

Hawaii Int’l Conf. Sys. Sci., pp.3005–3014, Jan. 2000.

院修士課程計測工学専攻了．同年日本電信

L. Li and Y. Halpern, “Minimum-energy mobile wire-

電話（株）入社．通信トラヒックの品質制
御，自律分散制御システムの研究に従事．

less networks revisited,” Proc. ICC ’01, pp.278–283,
June 2001.
[9]石塚

H. Saito and H. Minami, “Performance issues in sen-

平成 15 本会情報ネットワーク研究賞受賞．
日本 OR 学会会員．

sor networking,” Proc. 18th International Teletraﬃc
Congress, Berlin, 2003.
[10]

G. Hoblos, M. Staroswiecki, and A. Aitouche, “Optimal design of fault tolerant sensor networks,” Proc.
IEEE Int’l Conf. Cont. Apps., pp.462–472, Sept.
2000.

[11]

昭 62 立教大・理・物理卒．平元同大大学
院博士課程前期原子物理学専攻了．同年日
本電信電話（株）入社．平 17 首都大学東京・システムデザイン学部・准教授．博士“Upper bounds on the lifetime of sensor networks,”（工学）．通信トラヒック設計，通信品質測I. Daubechies, Ten Lectures on Wavelets. CBMS-NSF
Regional Conference Series in Applied Mathematics,
Society of Industrial and Applied Mathematics, 1992.

[13]

雅樹 （正員）M. Bhardwaj, T. Garnett, and P. Chandrakasan,
Proc. ICC ’01, pp.785–790, June 2001.

[12]

会田

定技術，自律分散制御技術，通信トラヒッ
クのべき乗則の研究に従事．平 7 本会学術奨励賞，平 13, 14,
15, 16 本会情報ネットワーク研究賞受賞．本会英文誌エディタ．
日本 OR 学会，IEEE 各会員．

B. Delyon, A. Juditsky, and A. Benveniste, “Accuracy analysis for wavelet approximations,” IEEE
Trans. Neural Netw., vol.6, no.2, pp.332–348, March
1995.

[14]

S. Madden, M.J. Franklin, J.M. Hellerstein, andW. Hong, “TAG: A tiny aggregation service for adhoc sensor networks,” Proc. 5th Annual Symposium
on Operating Systems Design and Implementation(OSDI), pp.131–146, Dec. 2002.

[15]

N. Wakamiya and M. Murata, “Synchronizationbased data gathering scheme for sensor networks,”
IEICE Trans. Commun., vol.E88-B, no.3, pp.873–
881, March 2005.

[16]

C. Intangonwiwat, R. Govindan, and D. Estrin, “Directed diﬀusion: A scalable and robust communication paradigm for sensor networks,” Proc. ACM MobiCom ’00, pp.56–67, Aug. 2000.

[17]

M. Ishizuka and M. Aida, “The reliability performance of wireless sensor networks conﬁgured bypower-law and other forms of stochastic node placement,” IEICE Trans. Commun., vol.E87-B, no.9,

2191