複数種類の環境情報が取得できる無線センサネットワーク(WSN)は,従来までの単一目的のWSNと異なって,一度の敷設で様々なアプリケーションに用いることができるため,敷設コストの面で有利である.またそのようなネットワークを複数のユーザで共有することで,ネットワーク管理者と利用者を分離する事ができ,利便性の面からも優位である.これらのことから共有型WSNは今後のユビキタスコンピューティングの基盤として期待される.そうした共有型WSNにおいて,各センサノードはバッテリ駆動であるため,ネットワーク管理者の利得を最大化するためには,タスクを注意深くセンサに割り当てる必要がある.また,ネットワークに投入されるタスクは事前には知る事が出来ない事が想定されるため,ネットワーク管理者はタスクの割当てを順次決定する必要があり,下した決定は取り消すことが出来ない.

本研究において,まず我々は投入されるタスクの分布に実用に即した仮定をもうけ,確率分布から得られる閾値を用いた分散割当てアルゴリズムを提案する.投入されるタスクの確率分布が未知である際も,提案アルゴリズムは適応的に閾値を変化させることで割当てを決定することができる.真の閾値からのずれは,経験分布関数に関する不等式によって抑えることができる.さらに我々は,通信に用いる電力の重要性に注目し,既存モデルの拡張を行う.また,WSNがクエリに応答するシステムであることを利用し,クエリに中継ノードの情報を上乗せし割当て決定に利用するアルゴリズムを提案する.提案したアルゴリズムを主双対法の枠組みで分析することによって,競合比を明らかにすることができる.また,我々は,先に提示した問題を確率分布に関する不等式を用いた枠組みで考慮することによって,二つの前提,すなわち,タスクの分布と通信電力を同時に考慮した問題についても割当てアルゴリズムが導出できることを示す.

提案した手法をシミュレーションによって評価し,実環境に近い設定において既存手法に対し優位であることを示す.また,実環境で標準的に用いられるTinyOS上に提案手法を実装する際の指針を示す.本研究により,共有型WSNを管理者の視点から見た際において,理論的保証のあり,かつ実用上オーバーヘッドが少なく効率の良い割当て手法が得られることを示す.

無線センサネットワークは,無線通信可能な多数の小型センサの集合体で,近年では各センサが多様なセンシング機能を有するようになり,アプリケーションの幅が格段に広がってきている.フィールドデータをネットワークで収集できる無線センサネットワークは社会や環境などの分野でこれまでになかった情報処理を可能にすると期待されており,今後の発展が見込まれる重要なプラットフォームである.

センシング機能の多様化により,一式の無線センサネットワークが様々なタスクをこなすことができるようになってきている.これにより,敷設者が一定の無線センサネットワークを敷設して,それを複数の利用者にサービスとして提供し,収益を上げるというモデルが現実的になってきている.これを共有型無線センサネットワークと呼ぶ.利用者は,自ら無線センサネットワークを敷設・メンテナンスすることなく,センシング情報を収集することができる.

本研究は,このようなサービスプラットフォームとしての共有型無線センサネットワークで必要となる基盤ソフトウェア技術のひとつとして,タスク割り当てについて研究したものである.センサノードはバッテリ駆動であることが多く,この場合,一定量のセンシングをした後で,バッテリもしくはノードの交換が必要となる.これが敷設者にとって大きなコストとなるため,敷設者にとっては与えられたバッテリ容量の制約条件のもとで利用者から得る利得を最大化することが求められる.本論文では,この利得最大化問題を,将来投入されるタスクは事前にはわからないオンライン性,および,データを中継するノードの電力消費,という現実に必要な 2 項目を新たに考慮して定式化したうえで,各ノードの情報を集中して持つノードがない分散型のアルゴリズムを示している.また提案手法の性能を理論的に証明している点が高く評価される.

本論文は以下に示す 8 章から成り立っている.

第1章では,共有型無線センサネットワークのコンセプトを提示するとともに,タスク割り当て問題の重要性を示している.また,従来研究におけるモデルで考慮されてこなかった要素として,利用者の利用形態が何らかのパターンを持つという仮定,マルチホップ通信が用いられるため中継ノードで電力消費が発生するという仮定を提示している.

第2章では無線センサネットワークの定義,特性,アプリケーション,研究課題について概観している.

第3章では共有型無線センサネットワークについて,その優位性を示すとともに,研究課題を示している.さらに既存研究におけるタスク割り当て問題への取り組みを総括し,本研究の位置づけを明確にしている.

第4章では,問題のオンライン性に着目してタスク割り当て問題に取り組んでいる.ここでは利用者からの query parameter が確率分布に従うと仮定し,経験確率分布を応用したアルゴリズムを提案している.提案手法の性能を理論的手法により分析するとともに,シミュレーションにより既存手法より10%程度の利得総和に関する改善を確認している.

第5章では,マルチホップ通信による中継ノードの電力消費を考慮したモデルを提案している.このモデルに対し,主双対法をベースに設計されたアルゴリズムを提案し,また理論的分析から競合比を明らかにしている.またシミュレーションにより既存手法から80% 程度利得総和が改善できることを示した.提案手法は query 情報に中継路の情報を上乗せすることで,電力増加を微小に抑えることができる.

第6章では,オンライン性とマルチホップ性の両方を同時に考慮したモデルに対するアルゴリズムを提案している.すなわち,最適オフラインアルゴリズムの動作を考察することで,期待値としてよい性能を持つタスク割り当てアルゴリズムを提案し,末端確率に関する分析から,アルゴリズムの失敗確率と競合比の関係を明らかにしている.

第7章では,第4章から第6章で扱ったモデルと現実の適用環境との間で残されている差について論じ,その差を埋める指針および他の取り組みとの組み合わせについて論じている.

第8章は本論文の貢献をまとめるとともに,今後の研究方向についても論じている.特に,提案手法が共有型無線センサネットワークの利用者の視点に立った取り組みにも適用可能であることを述べている.

以上をまとめると,本論文は,共有型無線センサネットワークを効率的に運用するために必要不可欠な技術を考察し,現実に即しているが従来研究では触れられていなかった2つの要素について,それらを取り入れたモデルを構築し,理論的保証があり,かつ実用上オーバーヘッドが少なく効率のよいタスク割り当て手法を提案している.共有型無線センサネットワークが情報理工学分野で今後果たしてゆく役割の重要性を考えると,これらは情報理工学分野の今後の発展に大いに寄与するものである.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。