FIT2005(第4回情報科学技術フォーラム)M-024

センサネットワークにおけるネットワーク内集約方式の性能評価
Performance Evaluation of In-network Aggregation for Sensor Network Monitoring
茂木信二†
Shinji Motegi

吉原貴仁†
Kiyohito Yoshihara

１． はじめに温度等の環境計測等にセンサネットワークを用いてデータを収集するユーザにとって，収集データの正確さは計測結果を正しく理解する上で重要となる．従来，センサノードの電力消費量を抑制するためにネットワーク内でデータを集約しながら収集する方式が提案されていた．しかしながら，センサノードが利用する無線リンクはパケット損失率(送信パケット数に対し受信できなかったパケット数の割合)が大きい場合があり，集約したデータを途中で一度に失う結果，収集データの正確さが低下してしまう問題があった．そこで筆者らは，複数の中継ノードを利用することでパケット損失に対する耐性を図ったネットワーク内集約方式をすでに提案している[1]．本稿では，シミュレーシ
ョンを用いて提案方式を評価した結果を報告する．

2. シミュレーション評価環境提案方式[1]は，各ノードがシンクに向かう経路上の次の隣接ノード(以下，親ノードと呼ぶ）を複数持つことを許容した非循環有効グラフを構成する．1 ホップ先となる複数の親ノード間で 2 ホップ先のノードとなる親の親ノードが共通する場合，それら複数の親ノードを中継に利用して2 ホップ先のノードで集約処理を行う．なお，それ以外の場合，指定した 1 つの親ノードで集約処理を行う．センサ
ネットワークからデータ収集を行うノード（以下，シンクと呼ぶ）は，以上の集約結果を収集する．更に，シンクからネットワークの端のノードまでの実際のホップ数に応じてデータの送信タイミングを制御する．
ここでは，シンクが収集したデータの正確さの観点からの評価を行う．提案方式と二つの従来方式のシミュレーション・モデルを TinyOS シミュレータ[2]上に実装した．センサノードの通信速度は 40 Kbps であり，MAC (MediaAccess Control)プロトコルには CSMA(Carrier Sense MultipleAccess)を用いる．TinyOS シミュレータのパケット損失率モデルは，実機のセンサノードを用いた実験結果を反映する．具体的には，ノード間の距離が 0～3 m であればパケット損失率が 10 %程度，12 m 以上ではパケット損失率が100 %となり，その間パケット損失率はほぼ線形的に増加する．従来方式の概要を以下にまとめる．
•従来方式(A)：各ノードは 2 つの親ノードを指定し，それぞれの親ノードにデータの値の半分を送信し集約処理を進める[4]•従来方式(B)：シンクを頂点とする経路木を構成し，各ノードは 1 つの親ノードを指定してデータ送信し集約処理を進める[3]†（株）KDDI 研究所, KDDI R&D Laboratories Inc.

265

堀内浩規†
Hiroki Horiuchi

いずれの方式においても，シンクがデータ収集の開始を要求するメッセージ(以下，REQ と呼ぶ)をネットワーク全体にフラッディングし，各ノードがデータを格納したメッセージ(以下，REP と呼ぶ)を応答することによって，シンクはデータの収集を行う．なお，REP の応答は REQ 内に指定された周期，データ収集回数に基づいて定期的に行われる．従来方式(A)及び(B)における REP の送信タイミングの制御には，提案方式の制御方法を適用した．また，収集するデータはネットワーク内のノード数とした．ノード数は，所望のデータの平均値の算出時の利用に加え，その数の減少の有無をモニタすることで，例えば，電力残量の低下により通信できなくなったノードや故障したノード等の検出に利用することができる．ノード数は，親ノードが子ノードから受信した値と自身の値の和を求める集約処理によって求まるデータとなる．データの収集周期は 3 秒 ，収集回数 M は 100 回とした．シンクが収集したデータの正確さ表す指標として，実際のノード数に対しセンサネットワークから 100 回の収集を行った結果の標準偏差を用いた．
その計算式を以下に示す．Vt は t 回目の収集時にシンクが取得したデータの値であり，V は実際の値である．

1Vt=M∑ ( Vt − V) 2 / Mt =1

センサネットワークを構成するシンク及びセンサノードは直交等間隔の格子状に配置した．シンクは格子の隅の１つに配置し，センサノードはその他の各格子に１つずつ配置した．

3. 評価結果(1) パケット損失率に対する評価結果
パケット損失率に対するネットワーク内集約処理の耐性について評価した．パケット損失率モデルは主にノード間の距離に依存することから，ノード間距離を変えてシミュレーションを実行した．なお，センサノード数は 24 ノードとした．
図 1 は，ノード間距離に対する誤差を示す．横軸のノード間距離が長くなるにつれてパケット損失率が大きくなった．提案方式及び二つの従来方式のいずれもノード間距離が長くなりパケット損失率が増加すると誤差が大きくなっている．また，ノード間距離が長くなりノード密度が疎になると親ノードが１つしか存在しないノードの数が増加することになる．そのようなノードは，1 つの親ノードを指定して集約処理を進める従来方式 (B) と同様の処理手順になることから，ノード間距離が増加すると提案方式の誤差の抑制効果が小さくなったものと考えられる．しかしながら，いずれのノード間距離においても提案方式は従来方式に比べ小さい誤差を得ており，ノード間距離が 2.25 m 前後
では誤差を半減している．

FIT2005(第4回情報科学技術フォーラム)

1.0

1.0

提案方式
従来方式(A)
従来方式(B)

提案方式
0.8

0.8

従来方式(A)

誤差

誤差

従来方式(B)
0.6
0.4

0.6
0.4
0.2

0.2

0.0

0.0

3

1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 3.25 3.50 3.75 4.00

815243548

ノード数

ノード間の距離 (m)

図 3 ノード数と誤差．

各ホップ数のノードが占める割合

図 1 ノード間距離と誤差．
ホップ数: 1

ホップ数: 2

ホップ数: 3

ホップ数:4
ホップ数: 4

100%
80%
60%
40%
20%
0%
1.00 1.25 1.50 1.75 2.00 2.25 2.50 2.75 3.00 4.00

ノード間距離(m)

図 2 ノード間距離に対する各ホップ数のノードの割合．
図 2 は，ノード間距離を変えてシミュレーションを実行した際の，シンクまでの各ホップ数のノードが占める割合を示す．ノード間距離が 1 m の場合，ほとんどのノードがシンクから REQ を直接受信できるため，ノードの 92 %はホップ数が 1 であり，それらの親ノードはシンクのみとなる．提案方式において親ノード数が 1 つの場合，従来方式(B)と同様の処理手順になることから，図 1 で提案方式と従来方式 (B) の誤差は同様の結果になったと考えられる．わずかに提案方式の誤差が小さいのは，残りの 8%のノードはホップ数が 2 であり，平均 4 ノードの親ノードを経由して集約処理が行われたためである．ノード間距離の増加に伴い，ホップ数が 1 のノードが占める割合が小さくなり，ホップ数が 2 以上のノードが占める割合が大きくなっている．これは，ノード間距離が大きくなり，シンクから REQを直接受信できないノードは，自身よりもシンクまでの距離が近い他のセンサノードが中継した REQ を受信することになったためである．
図 1 で提案方式と従来方式(A)，(B)の誤差は，ノード間距離が 1.5 m 以上から違いが大きくなっている．ノード間距離が 1.5 m では，ホップ数が 2 のノードが占める割合は25 %となった．よって，ホップ数が 2 以上のノードの割合が 25 %以上になると，提案方式による誤差の抑制効果が顕著になると言える．

(2) ネットワークを構成するノード数に対する評価結果
センサノード数は，データ収集する地理的な領域の広さに応じて増減されることを想定し，ネットワークを構成するノード数を変えて評価した．ノード間距離を 2 m とし，センサノードの密度を一定に保った上でノード数を変化さ266せた．図 3 にネットワークを構成するノード数に対する誤差のシミュレーション結果を示す．ノード数が 3 及び 8 の双方において，シンクまでのホップ数が 1 となるノードが占める割合は 100 %となった．それらの場合，提案方式と従来方式の誤差は同様の値になっている．ネットワークを構成するセンサノード数が増加すると，提案方式は従来方式に比べ誤差を抑制している．15 ノード以上では，シンクまでのホップ数が 2 ホップ以上のノードが占める割合が増加し，例えば，48 ノードでは，ホップ数が 1，2，3 のノードが占める割合は，それぞれ 25 ％，65 %，10 %となった．
よって 15 ノード以上でセンサネットワークを構成する場
合，シンクまでのホップ数が多くなり複数ホップで集約処理を行う回数が増加することになる．そのような場合でも提案方式は従来方式に比べ誤差の増加を抑制している．
以上，パケット損失率やシンクまでのホップ数が増加した場合であっても提案方式は従来方式に比べ収集したデータの誤差を抑制可能とし，収集データの正確さを向上することから提案方式は有効であると言える．

4. まとめ
本稿では，センサネットワークのモニタのためのネットワーク内集約方式のシミュレーション評価を行った．その結果，提案方式は従来方式に比べ収集データの正確さを向上することを明らかにした．日頃ご指導頂く ( 株)KDDI 研
究所浅見所長に感謝する．本研究の一部は総務省からの受託研究の成果である．

参考文献[1][2][3][4]

茂木他, "センサネットワークのモニタのための高信頼なネットワーク内集約方式 ," 信学技報 , SN2004-12,
pp.77-82, 2004.
P. Levis, N. Lee and D. Culler, "TOSSIM: Accurate andScalable Simulation of Entire TinyOS Applications," Proc.
of the First ACM Conference on Embedded Networked
Sensor Systems (SenSys), pp.126 – 137, 2003.
J. Zhao et al., “Computing aggregates for monitoring
wireless sensor networks”, Proc. of First IEEE
International Workshop on Sensor Network Protocols andApplications, 2003.
S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong,"TAG: a Tiny AGgregation Service for Ad-Hoc Sensor
Networks," Proc. of the 5th Annual Symposium on
Operating Systems Design and Implementation (OSDI),
pp.131-146, 2002.