データ収集型ワイヤレスセンサネットワークの稼働時間 延長のための可動ノードを用いた通信経路の構築手法

勝間　亮 (0651029)

近年，広域に設置された多数の小型センサがセンシングした情報を無線マルチ ホップ通信により交換することで環境情報の収集やオブジェクトの追跡などを行 うワイヤレスセンサネットワーク（以下，WSN）およびそのアプリケーションが 注目されている．WSN における各センサは長期間の動作を要求されるが，ネッ トワークのノードとしてデータ送受信も行う必要があり，その動作時間はバッテ リ容量および通信量，通信距離等に応じて変わってくる．WSN のより長期間の 動作を可能にするために，静止ノードのみからなるWSN を対象とした省電力化 手法が幾つか提案されている．一方，自力で領域内を移動可能な可動ノードを導 入して，故障した静止ノードや未設置の領域に移動させ広範囲のセンシング領域 を確保する手法が近年になって提案されている．しかし，広いセンシング領域の 確保とWSN の稼働時間の最大化を同時に扱っている研究はない． 本論文では，データ収集を目的とする，静止ノードと可動ノードから構成され るWSN において，広範囲のセンシング領域をできるだけ長時間保持するような， 可動ノードの適切な移動先，および，データ収集のためのマルチホップ通信経路 を構築する手法を提案する．対象問題を，センシング対象領域をk 重被覆（領域 内のどの地点もk 個以上のセンサのセンシング範囲内にある状態）し，かつWSN の稼働時間を最大化するような，可動ノードの移動先を含むデータ収集経路を求 める問題として定式化する．本問題は組み合わせ最適化問題であるため，遺伝的 アルゴリズム(Genetic Algorithm，以下GA) に基づいた近似アルゴリズムを考 案した． 提案アルゴリズムでは，各可動ノードの移動先および各静止ノード，可動ノー ドのデータ収集経路における次のノードを解候補として符号化する．そして最初 にランダムに値を設定した複数の解候補（初期解）を与えて，評価，交叉，突然 変異，選択の操作を行い，解を進化させる．この際，良い解が導出できるかどう かは初期解の品質に依存する．品質の良い初期解を構築するため，基地局ノード に近いノードは，より遠方のノード（子孫ノードという）のデータを中継するた め通信回数（通信量）が多くなることに着目し，基地局に直接接続するノードお よびその数を，子孫ノードのデータの中継に必要な通信量も考慮した上で決定す るよう工夫した． 提案手法を実装し，性能評価のためシミュレーション実験を行い，対象センシ ング領域をk 重被覆する稼働ノードの配置およびデータ収集経路を求めた．その 結果，提案手法は，7 静止ノード，3 可動ノードのWSN に対し，WSN 稼働時間 において最適解との違いが約-2.9%の解を算出できた．また，75 静止ノード，25 可動ノードのWSNに対し，他の手法よりWSN稼働時間を78〜165%延長できる ことを確認し，31.4 秒程度と実用的な時間で解を求めることができることを確認 できた．