情報処理学会第68回全国大会

3F-3

センサネットワークのためのトポロジ構成方式の基本評価
茂木信二†

吉原貴仁†

浩規†

堀内(株)KDDI 研究所†
１． はじめにセンサネットワークの利用可能時間を長くするためにはセンサノードの電力消費の抑制が重要となる．ノードが用いる無線の送信電力は電力消費の主要因であり，その削減が有効となる．各ノードが送信電力を増減すると通信範囲が変わりノード間を接続する無線リンクの接続形態（以下ネットワークトポロジと呼ぶ）が変化する．その結果ネットワークの接続性が失われてしまうことがある．
そこで筆者らは各ノードが自律分散的に送信電力を増減しても接続性を確保した上で省電力なトポロジの構成可能とする方式を提案している[1]．本稿ではシミュレーションを用いて提案方式を評価した結果を報告する．
２．従来方式
従来の代表的なネットワークトポロジ構成方式[2]は隣接ノードの位置情報に基づいて送信電力を削減する方式を提案している．送信電力はノード間の距離により一意に決まることを仮定している．その上で接続性が確保できることを示している．しかしながら，その仮定は必ずしも成立しないことが実際のセンサノードを用いた実験結果で示されている[3]．よって接続性が失われセンサデータの収集が困難になってしまう問題がある．
３．提案方式の概要
3.1 隣接ノードの探索
各ノードは起動するとパケットの広報により隣接ノードを探索する．新たな隣接ノードを発見すると，パケットの送信電力を変えた複数パケットの送受信によりそのノードへの必要最小限の送信電力を求める．その結果，発見した隣接ノードの ID とそのノードまでの送信電力の値の組からなるリスト（以下 Connectivity Set(CS)と呼ぶ）を作成する．CS の最大の送信電力を用いれば，CS 内の全てのノードを通信範囲に含むことができる．よって，各ノードは，送信電力を CS の中の最大値に設定する．
3.2 論理的な重みの導入と計算
2 つのノード i，j 間は，具体的には i→j と i←j の 2 つの無線リンクで相互接続される．CS 内の各ノードへの送信電力の中で最大の値を用いれば CS 内の全ノードに無線が伝達し接続性を保つことができる．つまり CS の中で最大の送信電力を用いれば，それ以下の送信電力でよい CS 内の他のノードにも新たな送信電力を用いなくても無線が伝達する状況となる．これよりここで導入するノード i の CS(以下 CSi と呼ぶ)の各ノードへの論理的な重み TPi→j(j∈CSi)は，j への送信電力が CS の中で最大ならば，その送信電力の値と同一となる．それ以外の場合は TPi→j は 0 となる．2 ノード i，j 間の論理的な重み TPi⇔j は{TP | max (TPi→j , TPi←j) }とする．図 1(ア)Basic Evaluation of Topology configurationfor Sensor Network†Shinji Motegi, Kiyohito Yoshihara and Hiroki Horiuchi

3A433345C(ア)D6A00C6B50005C(イ)4D (エ)00D6A

B54(ウ)

120AB

5B

31233CD

図 1 送信電力制御によるトポロジ構成例
は隣接ノードへの実際の送信電力例を示す．簡単のため送信電力の値は整数としている．図 1(イ)は各ノードが求めた TPi→j を示す．例えば，CSA={(B,3),(C,4)}となるノード A は，TPA→B は 0，TPA→C を 4 とする．図 1(ウ)は TPi⇔j を示す．
3.3 CS の更新手順
各ノードは以下の手順を実行する．これより CS の中で送信電力が最大のノードが順次取り除かれ，その結果として送信電力を削減する．
(1) CS 内で送信電力が最大となるノードを X とする．
(2) X との直接のリンクを除き X に至る経路を広報の利用により探索する．
(3) 探索の結果見つかった経路上の重み TPi⇔j が，自身と X 間よりも小さい場合， CS から X を除く．
(4) CS のノード数が 1 ならば終了する．CS 中で未終了のノード数が 1 の場合も終了する．それ以外の場合(1)に戻る．終了したら CS 内のノードに終了を通知する．
例えば，図 1(ウ)のノード B はノード A が X となる．
経路探索の結果，ノード B は経路 B⇔C⇔A を見つけ
TPB⇔A < TPB⇔C，TPB⇔A < TPC⇔A を満たすことから A をCSB から取り除く．その結果 A との直接の接続はなくなるが間接的な接続を可能とする他の経路の存在を確認した上で上記(3)を実行することから A との接続性は確保できる．ノード D も同様の処理で，ノード C を CSD から取り除く．その結果，ノード A と D は CS の数が１となり本手順を終了する．またノード B と C は CS 内で本手順が未終了なノード数が 2 つ以上存在しなくなる．これよりそれらは本手順を終了する(図 1(エ))．以上の手順を各ノードが自律分散的に実行することでネットワークの接続性を確保した上で送信電力を削減可能となる．

４．基本評価4.1 評価環境提案方式を用いることで構成されるネットワークトポロ
ジの接続性と送信電力の削減効果について評価する．
提案方式と従来方式[2]のシミュレーション・モデルをTOSSIM と呼ばれるシミュレータ[4]に実装した．通信速

3-409

情報処理学会第68回全国大会

度は 40 Kbps であり，MAC (Media Access Control)プロ
トコルには CSMA(Carrier Sense Multiple Access)を用いる．TOSSIM のパケット損失率モデルは，ある１つの送信電力の値を用いた実験結果を反映したモデルのみとなっている．そこで Mote と呼ばれる市販のセンサノードを用いて送信電力の値を変更した場合の実験を行い，パケット損失率モデルを新たに作成した．[3]の報告と同様，送信電力がノード間距離に必ずしも依存しない実験結果となった．センサノードは予め指定した縦 100 m，横 100 m の領域内に無作為に配置し移動はしないものとした．なおノード数は 50 ノードとした．
4.2 評価結果
図 2 は提案方式及び従来方式を適用する前のネットワークトポロジであり，各ノードは設定可能な最大の送信電力を用いている．図中の丸い点はノードを表し点間を結ぶ実線は無線リンクを表している．図 2 のトポロジに対して従来方式を適用した後のトポロジが図 3，提案方式の適用後が図 4 のトポロジとなる．従来方式と提案方式の双方が図 2 のトポロジに比べ無線リンクの数が減っている．これは送信電力を削減したことで通信範囲が狭まったことによる．
従来方式はネットワークが分裂してしまっている．図 3の点線は分裂した箇所を示す．分裂した箇所間では通信できないことから，それらの間でのセンサデータの収集が困難となる．これよりネットワークの接続性を確保するためには，従来方式は適用せず元々のネットワークトポロジのままの方がよいと言える．
提案方式はネットワークの分裂はなく接続性を確保している．更に各ノードの送信電力は図 2 の最大の送信電力を用いる場合に比べ平均 73 %程度削減している．
従来方式は平均 81 %程度削減するが，その削減割合を直接比較することはできない．なぜなら削減割合が提案方式よりも大きいのは，分裂の原因となった他のノードと接続できず送信電力を 0 としたノードの値が平均を求める際に含まれるためである．以上，提案方式は従来方式に比べネットワークの接続性を確保した上で送信電力を削減可能であることから有効であると言える．

図 2 本来のネットワークトポロジ

図 3 従来方式を適用したネットワークトポロジ

４．おわりに
本稿では送信電力の制御によるセンサネットワークのトポロジ構成方式のシミュレーション評価を行った．その結果，提案方式は従来方式に比べネットワークの接続性を維持した上で送信電力の削減を可能とすることを明らかにした．なお，ノード密度に対する詳細評価などが今後の課題である．最後に日頃ご指導頂く(株)KDDI研究所秋葉所長，長谷川執行役員に感謝する．
参考文献[1]茂木他，“センサネットワークのトポロジ構成方式の検討,”
電子情報通信学会，ソサエティ大会論文集，pp.177，2005．
[2]N. Li et al., “Topology Control in Heterogeneous Wireless
Networks: Problems and Solutions,” Proc. of the IEEE
conference on computer communications (INFOCOM),
pp.243-254, March 2004.
[3]D. Son et al., “Experimental study of the effects oftransmission power control and blacklisting in wireless

図 4 提案方式を適用したネットワークトポロジ
sensor networks,” Proc. of the IEEE conference on sensorand ad hoc communications and networks (SECON),
pp.289-298, Oct. 2004.
[4]P. Levis et al., "TOSSIM: Accurate and Scalable Simulationof Entire TinyOS Applications," Proc. of the First ACM
Conference on Embedded Networked Sensor Systems(SenSys), pp.126 – 137, 2003.

3-410