モバイルアドホックネットワーク上での効率よい情報検索のための需要に基づいた情報複製配置方式

榎本 真 (0551020)


本研究では,モバイルアドホックネットワーク(以下,MANET)上で効率の良い情報検索を行うための新しい方式を提案する. 提案方式はユーザの需要情報を利用することにより, 少ない通信量と早い検索時間,高いデータ可用性(MANET上にあるデータが高い確率で検索可能なこと)を達成する. 提案方式では,効率の良い情報検索を行うため,予めカテゴリ分けされたレコード(共有データの単位)をそのカテゴリの需要が高い領域の 近傍に複製する.そのために対象とする領域をエリアと呼ぶ小さい領域に分割する. MANET上の移動ノードはカテゴリごとに各エリアで出されたクエリの数を集計 し互いに交換することで 得られる需要情報を集約・共有することで,カテゴリごとエリアごとの需要を決定する. レコード作成・登録時には,そのレコードのカテゴリに対する需要の高いエリアに,レコードを送信することで複製を作成する. また,レコード検索時には,検索したいレコードのカテゴリに対し需要の高いエリアをシステムが自動的に特定し,そのエリアに対しクエリを送信する.通信コストを抑え, 各ノードが特定のエリアのノード群に対してメッセージを効率よく送信できるようにするため,GeoCastプロトコルの一つであるGPSRに基づいた通信方式を考案し採用した. 平均検索時間と通信コストが最小に,レコードの可用性が最大となるように,各カテゴリのレコードの 複製先エリア集合を決定できることが望ましい.そのため,準最適な解を見つけるアルゴリズムを開発した. 大阪市中心部の地図を用いたシミュレーションを通して,提案方式が検索時間,通信コストの点で, 複製を情報作成地点の近傍に複製する方式と比べて,最大でそれぞれ,73%,29%良い性能を達成することを確かめた.