ネットワーク技術の目覚ましい発展に伴い,小型の無線端末を用いていつでもどこでも世界中のあらゆる情報を取得が可能となる,いわゆるユビキタス環境が近い将来実現するであろうと考えられている.現在,無線を利用する通信の形態としては,高速で広帯域の無線 LAN や携帯電話網,WiMAX を利用したものなどが開発されつつあるが,従来は基地局やアクセスポイントなど,有線ネットワークに繋がっている親機に相当する装置にユーザの子機が接続して通信を行うというのが主流であった.将来のユビキタス環境では,このような通信手法に加えて,無線端末同士が互いにリンクを張り,パケットを中継してルーティングすることにより,あらゆる端末同士の通信が可能となる無線マルチホップネットワークが広く利用されるようになると考えられる.無線マルチホップネットワークを用いれば,基地局装置や固定の有線のバックボーンネットワークを持たなくても,あらゆる無線端末同士がP2P的に手軽に通信を行うことが可能になるため,例えば,ある街の店舗情報や交通情報,環境情報や観光名所の情報など,ある地域の局所的なユーザ間でリアルタイムなデータを自由に交換するのに有効な手段となるのではないかと考えられる.このため,無線マルチホップネットワークに関しては,モバイルアドホックネットワーク技術や無線センサネットワーク技術の分野で盛んに研究が行われている.

これらの技術に加えて,近年ではカーナビゲーションシステムや GPS 付きの携帯端末などの研究開発が盛んに行われ,さらに, Google Maps のようなウェブ上で利用可能な地図情報サービスの登場により,位置依存型サービス (location based service: LBS) を誰でも手軽に利用できるようになりつつある.LBS と 無線マルチホップネットワーク技術とを統合し,ある地域に存在するローカルなユーザ同士で P2P 通信を行うことにより,広帯域のバックボーンネットワークや高速処理が可能な巨大データベースサーバを用いずとも,その地域に関連する情報をいつでも取得することが可能となるような,新しい LBS が創出されるようになるのではないかと考えられる.

LBS システムを構築するためには,ある位置に関連した情報(位置依存情報)が重要な役割を担う.位置依存情報は,ある人物や物体,イベントなどの情報を,緯度経度座標や住所などの位置情報を用いて記述するデータである.現在,位置依存情報を記述するためのマークアップ言語として KML や GMLなどが存在する.これらの記述言語を用いることにより,ユーザが興味を示している地点 (point of interest: POI) に関連する位置依存情報を,ネットワークを通じて相互に交換することが可能になり,あらゆるユーザがあらゆる地点に関連する情報を得ることができるようになる.したがって,このような位置依存情報をユーザ間で分散共有可能にする方法を考案することがLBS を構築する上で重要な課題となる.

また,位置依存情報を利用するアプリケーションによっては,サービス対象エリア内で扱うデータが頻繁に更新され,ユーザがなるべく最新のデータを取得することが可能になるように,システムを適切に設計しなくてはならないものもある.例えば,ある地域や位置に関連した最新のニュースの配信,環境情報のモニタリング,店舗の商品管理などのビジネスロジスティックスへの活用,ライフログやUrban Computing に関連したアプリケーションなど,ユーザの取得するデータに対してリアルタイム性が求められるような場合,従来の地図情報サービスで用いられている静的なデータのみならず,時間によって変動する動的なデータをどのようにユーザ間で共有するかを考案することが非常に重要となる.

無線マルチホップネットワーク上でこのような位置依存情報をやりとりするためには,有線ネットワーク上に構築可能な P2P オーバーレイを用いた分散共有手法とは異なり,無線マルチホップネットワークの性質に合った方法を考案する必要がある.位置依存情報が頻繁に更新される場合,論理的なネットワークを維持したり,情報交換を行ったりするためのオーバーヘッドは無視できないものとなる.まず,位置依存情報の作成者は,データの更新毎にサーバとなる離れた端末まで該当データを転送しなくてはならない.この作業はデータ作成者にとってアップロードの手間がかかるだけではなく,無線マルチホップネットワークを用いる場合は,新しい位置依存情報をサーバまで送信するときに,目的端末と作成者との間に存在するすべての中継端末がそのデータを転送しなくてはならない.これはネットワークに大きなトラフィック負荷を生じさせることになる.さらに,無線マルチホップネットワークは端末の移動によりトポロジーが頻繁に変化するため,各端末間のリンクが不安定となる.このため,位置依存情報が更新された際に,必ずしもデータ作成者が離れたサーバに接続可能である保証がない.さらに,たとえサーバ上にデータをアップロードできたとしても,ユーザの端末がサーバに接続可能でなければ,ユーザは古いデータを持ち続けることになる.よって,位置依存情報の作成者が持つデータとサーバに存在するデータ,もしくはユーザの所有するデータとの間にデータの一貫性の問題が生じることになる.

このような問題の解消法として,端末の位置情報を用いて無線マルチホップネットワーク上でデータを分散共有する手法が従来いくつか提案されている.これらの手法は structured なオーバーレイを利用する手法とは異なり,unstructured P2P 手法であるため,無線マルチホップネットワーク上に容易に実装が可能である.したがって,これらの従来手法を用いることにより,最適手法ではないと雖も,位置依存情報をユーザ間で共有することが可能になると考えられる.しかし,従来手法はトラフィック負荷やメモリ消費量などのオーバーヘッドを考慮した場合,必ずしも効率が良いものではない.また,手法によっては位置依存情報が頻繁に更新される場合,複数の端末が保有するデータの一貫性が保証できないものもある.

本論文では,位置依存情報が頻繁に更新される環境でも適用可能な,無線マルチホップネットワーク上で動作する新しい位置依存情報分散化手法を提案する.我々の手法では,まず位置依存情報を,その配信源の近くの領域に存在する端末のみに配置する.これにより,データ作成者のアップロードのコスト削減と,データの一貫性維持を図る.そして,高いデータ発見率を実現するため,データの配信源から離れた領域に存在する端末には,ユーザのクエリをデータ配置領域まで転送するためのルーティングテーブルを作成する.ここで述べるルーティングテーブルとは,アプリケーションレイヤにおいてクエリを転送するために,クエリの転送先を記述しているテーブルを指す.ルーティングテーブル内に格納された各エントリには,クエリがマッチするかどうかの指標と,その指標にマッチした場合の転送先領域情報が記されている.エントリに記述された目的地までは,GPSR を用いてクエリは転送される.GPSR は,無線マルチホップネットワーク上で動作する位置情報ルーティングのひとつである.ユーザの作成したクエリは,POI に関する情報を持つ端末までルーティングテーブルにより適切に転送されるため,ユーザの欲するデータを発見することができる.したがって,ユーザ間で位置依存情報の分散共有が可能になる.

ルーティングテーブル内に格納する,クエリのマッチングに利用するための指標として,本論文では位置依存情報から生成されるハッシュ値を用いる手法,および,位置依存情報から抽出可能な階層的なデータ構造を用いる手法の二つを提案する.

本手法ではルーティングテーブルを用いるため,その配置やメンテナンスのためには,制御パケットによるネットワークへのトラフィック負荷の増大や,テーブルを保持するための端末のメモリ消費のオーバーヘッドの問題が生じる.しかし,本手法では POI の位置情報から作成した R-Tree の構造に沿ってルーティングテーブルを集約的に配置することにより,この問題を解消する.R-Tree の上位層の領域,つまり,POI から遠い位置に存在する端末にはアブストラクトなマッチング指標を持つエントリを配置し,下位層の領域,つまり,POI に近い位置に存在する端末にはより具体的なマッチング指標を持つものを配置する.R-Tree の上位層ほど,その領域にはより多くの端末が存在することになるが,それらの端末のもつルーティングテーブルのエントリはアブストラクトであるため,保持すべき情報量が少なく,ルーティングテーブルの情報交換や維持のためのオーバーヘッドは非常にわずかなものとなる.また,ルーティングテーブルの情報の交換に関しては,各端末の位置が大きく変化した場合のみ行われるため,メンテナンスのためのトラフィックも頻繁に発生しない.

本手法を評価するため,ネットワークシミュレータを作成し,クエリのマッチング指標に関して位置依存情報のハッシュ値を用いたもの,データ構造を用いたもの,および実際の KML データを用いたものそれぞれに関してシミュレーションを行った.その結果,我々の手法は従来手法と比較して,位置依存情報の一貫性を保ちつつも,低トラフィック量,低メモリ消費量でユーザの POI に距離的に近いデータを高い確率で発見可能であることが確認された.したがって,本論文の提案手法の有効性が示された.

本論文は「無線マルチホップネットワークにおける位置依存情報分散共有手法」と題し、無線端末群が相互に接続することによって構成可能な無線マルチホップネットワーク上において、位置依存型サービスで利用される位置依存情報を分散的に配置し、それを効率的に発見してユーザが共有可能にすることを目的とし、全六章から構成されている。

第一章は「序論」であり、本論文の主題となる無線マルチホップネットワーク、および位置依存型サービス(LBS : Location Based Service)について概観し、位置依存型サービスにおける位置依存情報共有の重要性を論じている。その上で、無線マルチホップネットワーク上で位置依存情報を分散共有するための従来手法の問題点を整理し、この問題を解消するために本論文で紹介する提案手法とその利点の概観を行っている。

第二章は「無線マルチホップネットワークにおける LBS の応用と位置依存情報分散共有手法」と題し、まず、位置依存型サービスの紹介とその応用、位置依存型サービス構築に利用される位置依存情報について論じている。次に、無線マルチホップネットワークと位置依存型サービスとを統合したシステムのアプリケーションイメージについて述べ、そのシステムを実現させるために重要となる位置依存情報分散共有について、従来手法の問題点を整理する。そして、この問題点を解消するための提案手法について述べている。本手法では、位置依存情報の更新頻度が高い場合でもアップロードのコストを抑え、コピーされた位置依存情報の同期をとり易くするため、位置依存情報を配信源に地理的に近い領域にだけ局所配置する。局所配置したデータへユーザのクエリを適切に転送するために、本手法では各端末にルーティングテーブルを配置する。ルーティングテーブル内には Matching indicator と呼ばれる、ユーザのクエリにマッチするかどうかの指標となるパラメータが用意され、その指標にマッチした場合、ルーティングテーブルの指し示す領域に転送される。その領域にクエリを転送するためにGPSR を本手法用に改良したものを用いる。これにより、クエリはユーザの欲する事項にマッチし、なおかつ、ユーザの興味地点に近い情報を得ることが可能になる。提案手法により、端末あたりのトラフィック負荷、メモリ消費量のオーバーヘッドを最小限に抑えつつも、ユーザのクエリを効率的に転送するシステムが実現されている。

第三章は「ハッシュ値と位置情報を利用した位置依存情報分散共有手法」と題し、まず、DHTやGHTなどの従来のハッシュ値を利用した情報分散化手法の問題点を分析している。次に、第二章において述べた提案手法におけるルーティングテーブル内の Matching indicator の実装方法として、位置依存情報のハッシュ値を用いた手法の提案を行っている。この手法では、クエリのハッシュ値の上位ビットがテーブル内の Matching indicator のビット列に一致しているかどうかにより、ルーティングテーブルとクエリとのマッチングが行われる。そして、ルーティングテーブルの配置に関し、R-Tree の上位領域には少数のビット数、下位領域には長いビット数を持たせるという集約手法を用いることにより、ルーティングテーブル配置のコストを最小化する。また、R-Tree の各レイヤにおいて、端末が 保持すべきMatching indicator のハッシュ値のビット数について定量的な考察を行っている。あわせて、提案手法のシミュレーションによる評価を行い、提案手法が、広範な条件で適切に動作することを示している。

第四章は「位置情報とデータ構造を利用した位置依存情報分散共有手法」と題し、位置依存情報をセマンティックウェブ技術で用いられる RDF などを用いて構造化して記述が可能であることを述べ、それにより得られる検索のメリットを紹介し、その応用例を紹介している。次に、構造化されたデータの分散共有の問題点を述べ、提案手法として第二章で述べた手法に関して、 Matching indicator をデータ構造によって実装する手法について述べている。本手法では位置依存情報がツリー型の階層構造を持っていると仮定し、クエリの上位クラスが Matching indicator のクラス構造に一致するかによりマッチングが行われる。R-Tree の上位領域にはデータ構造の上位クラス、R-Treeの下位領域にはデータ構造の上位クラスに加えて下位クラスも Matching indicator として格納しておくことにより、ルーティングテーブルの集約的配置を実現される。あわせて本手法をシミュレーションにより評価し、ハッシュ値を用いた手法と同様に、低トラフィック量、低メモリ消費量でユーザの興味地点に近い位置依存情報を効率的に発見できることを解明している。

第五章は「実在する位置依存情報の分散共有手法」と題し、本手法の応用例として、実際に Google Maps で利用されている KML データを利用し、実在する位置依存情報を本手法により無線マルチホップネットワーク上で分散共有の実験を行っている。ここでは、空間情報を記述するための階層的なオントロジーをKMLデータに付加させることにより、KMLデータに階層構造を持たせ、KMLデータの分散化においても第四章で述べた手法を適用可能であるということを解明している。

第六章は「結論」であり、論文の成果と今後の展望をまとめている。

以上これを要するに、本論文は、無線マルチホップネットワーク上に位置依存情報を局所配置し、ルーティングテーブルの情報と端末の位置情報を用いることによりクエリの転送を行い、位置依存情報を高い成功率で発見する手法を提案すると共に、提案手法が位置依存情報の更新頻度が高い環境においても低トラフィック負荷、低メモリ消費量でユーザのクエリにマッチし、かつユーザの興味地点に近い位置依存情報を効率的に発見でき、無線マルチホップネットワーク上で位置依存情報を分散共有可能にする優れた手法であることを示したものでであり、電子情報学に貢献するところが少なくない。 よって本論文は博士(情報理工学)の学位論文として合格と認められる。