Wireless sensor networks are known to have properties that make it challenging to design communication protocols. They typically consist of small-scale sensing devices in massive numbers, each limited in hardware capabilities and battery life. Once deployed, such sensor nodes form a dense ad hoc mesh topology through which they communicate the data they have extracted from the physical environment. Recent trends indicate that future sensor networks are anticipated to become widely established general networking infrastructures that allow open and ubiquitous access to sensory information by diverse applications. In this thesis we explore novel networking protocols aimed at providing scalable and efficient communication in such a scenario. We particularly focus on making two concrete types of communication protocols applicable by having them adapt to temporally and spatially local networking conditions such as regionally varying node densities or changing redundancy qualities of data traffic traversing the network nodes.

First, we propose a protocol on the routing layer that dynamically coordinates stateless geographic forwarding and traditional topology-based route discovery. While the former generally constitutes a scalable and efficient data delivery method, it suffers in its performance from local minima in the spatial network topology and from inaccurate node coordinates. To make geographic routing feasible in large-scale sensor meshes nonetheless, we bridge such conditions by constructing and maintaining a limited number of topology-based routes in a spatial extent necessary to uphold the geographic forwarding functionality. That way we keep the overhead of maintaining routing state localized and the overall routing process scalable, while preserving the efficient nature of the paths selected.

In our second contribution, we propose a protocol for identifying and suppressing redundant data transfers on the network link level. These occur when transmissions carry partially identical data such as repeating sensor readings or address fields. Faced with stringent memory limitations at each sensor node, we resort to probabilistically tracking the most frequently reoccurring data fragments in the traffic stream passing every network link. We make the node at the receiving end of a link selectively cache the thereby identified data contents, so that it becomes able to reference and reconstruct the repeating data locally for subsequent transmissions. As a result we succeed in preventing unnecessary communication traffic throughout the network that would otherwise waste valuable transmission energy.

本論文は「Adaptive Communication Protocols for Wireless Sensor Networks」(無線センサネットワークにおける適応的コミュニケーションプロトコル)と題し、汎用性の高い観測基盤を実現する手段として、効率性ならびに拡張性が高く、適用範囲が広いルーティングプロトコルとデータ圧縮プロトコルを提案している。

本論文は以下の6つの章から構成されている。

まず第1章では、研究概要を述べている。第2章では、近年の研究トレンドを取り上げ、無線センサネットワークを用いた汎用性が高い観測基盤の重要性や、実現に向けた課題を整理している。

第3章では、効率のよいジオグラフィックルーティングプロトコルを提案している。ジオグラフィックルーティングプロトコルは、ノードの位置情報を活用し、1ホップ圏内でパケットが目標地点に近づくノードへの転送を繰り返すことで目的ノードまでメッセージを届ける。この手法は局所的な情報のみを活用するために、一般的なルーティングプロトコルと比べて拡張性が高く、地理的に広域に展開された無線センサネットワークでも小さいオーバヘッドで通信することができる。しかし、1ホップ圏内のノードの情報しか扱わないため、トポロジによっては、行き止まり状態に陥り、目的ノードまでメッセージが到達しない問題が存在する。また、ノードの位置情報の精度が低い場合、目標地点にノードへ転送が行われず効率の悪い経路で転送されてしまう場合がある。本研究では、これらの問題を解決するプロトコルを提案している。まず、本研究では、既存研究を踏まえ、行き止まりからの脱出経路を発見する際に、その過程で得られた経路情報を各ノードにキャッシュし、次に行き止まりとなったメッセージに対して、キャッシュされた経路を活用することで通信量を削減する。従来手法では、ノードアドレスに基づいて活用可能な経路情報の判定を行っていたため、キャッシュされた経路情報の再利用性が低いという問題があったが、本提案では、宛先となる位置情報を基に判定を行うことで、宛先は異なるが類似する方向へ送信されるメッセージに対しても脱出経路の再利用が可能となる。従って、通信量を低減することができる。さらに、パケット転送を行う際に、位置情報の不確かさを踏まえて、目的地点まで確実に近づくと判断できるノードまで部分的な経路を構築する手法を提案した。この手法によって、位置情報の精度が低くとも、効率よい経路でメッセージ送信することが可能となる。提案手法はシミュレーション上で従来の手法と比較し、拡張性ならびにルートの効率性における有効性を示している。

第4章では、ノード間の通信データ量を削減するデータ圧縮プロトコルを提案している。データ圧縮プロトコルは、各ノード間の通信において、過去の送信データと同じ内容のデータがあった場合、その部分の送信を省略し、受信側で保存した受信データのキャッシュから再現することで、通信データ量を削減する。インターネットを対象とした既存のデータ圧縮プロトコルでは、送信側では送信データの履歴を保持するために、受信側では再現のためのデータをキャッシュするために、多量のメモリ容量を消費する。さらに、通信データの性質が一定であるため、性質に合わせた固定的なパラメータ設定を行っている。一方で、汎用性が高い観測基盤として無線センサネットワークを用いる場合、ノードのメモリ容量が貧弱である上、通信データの性質が一定ではないため、既存の手法を適用できない。そこで、本研究はこのような制約下で効率のよいデータ圧縮プロトコルを実現するためのキャッシングアルゴリズムを提案している。まず、出現頻度とデータサイズから、データを最も効果的な粒度に分割する手法を提案している。さらに、送受信側でのメモリ消費量を抑えるために、データの出現頻度を固定長で管理するデータ構造を提案している。このデータ構造では、ハッシュを用いることでデータ毎の出現頻度を固定長のメモリ消費量で管理可能としている。加えて、通信データの性質変化に対応するために、出現頻度データのエイジング手法や、データ構造の自己最適化手法を提案している。なお、本章では、理想的なデータ分析手法と比較して、提案手法が、センサノードのメモリ制約下でどの程度冗長な通信を取り除くことが可能かを評価している。多様な冗長性を持つデータセットで実験を行った結果、メモリ制限がない場合の性能に近い結果が得られることが示している。

第5章では、3、4章で提案したプロトコルが、2章で示した汎用性が高い観測基盤に対してどのような貢献があるかを論じ、第6章で論文の内容を纏めている。

以上のように本論文は、無線センサネットワークによる汎用性が高い観測基盤を実現するという大きな目標に向けて着実に技術を進歩させている。各アプリケーション依存の手法を提案している従来研究に対して、本研究は適応性という性質を取り入れることにより汎用性が高いソリューションを生み出している。従って、ルーティングとデータ圧縮という通信課題におけるそれぞれの提案手法はこの分野で高い適用可能性を秘めている。以上のように情報理工学における創造的実践の観点でも価値が認められる。

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