DEIM Forum 2013 A5-1

モバイルアドホックネットワークにおける Top-k 検索のための複製配置
およびメッセージ処理手法
佐々木勇和†

原隆浩†

西尾章治郎†† 大阪大学大学院情報科学研究科マルチメディア工学専攻 〒 565–0871 大阪府吹田市山田丘 1 番 5 号
E-mail: †{sasaki.yuya,hara,nishio}@ist.osaka-u.ac.jp
あらまし

本稿では，モバイルアドホックネットワークにおいて，正確な結果の取得と，遅延およびオーバヘッドの削減を目的とし，Top-k 検索処理と複製配置を組み合わせた手法を提案する．これまでの研究では，Top-k 検索のための最適な複製配置，および精度を維持する Top-k 検索手法は提案されていない．そこで，まず最適な複製の配置率を計算し，それに基づいて複製を配置する FReT(topology-Free Replication for Top-k query) とよぶ複製配置法を提案する．さらに，正確な結果を取得するまで TTL を増加しながら検索を繰り返す Top-k 検索のメッセージ処理手法を提案する．TTL の増加方法として，探索端末数の減少を目的とする Expanding ring 法と，探索遅延の減少を目的とする

Bundling 法の二つの方法を用いる．シミュレーション実験より，提案手法が高い性能を達成していることを確認した．
キーワード

モバイルアドホックネットワーク，Top-k 検索，複製配置

Yuya SASAKI† , Takahiro HARA† , and Shojiro NISHIO†† Department of Multimedia Engineering, Graduate School of Information Science and Technology,
Osaka University, 1-5 Yamadaoka, Suita, Osaka, 565–0871 Japan
E-mail: †{sasaki.yuya,hara,nishio}@ist.osaka-u.ac.jp

1. は じ め にTop-k 検索は，ユーザが指定する検索条件とスコアリング関数に基づいて，最も関連のある上位 k 個のデータを検索する．

Top-k 検索は，重要なアプリケーションで頻繁に利用されるため，数多くの研究が行われている．例えば，ウェブや検索エン
ジンにおいて，語句の出現率やテキストの関連性の抽出，セン
サネットワークにおいて，はずれ値の検出，P2P ネットワーク
おいて，興味のあるデータの共有などがある．同様に，モバイ
ルアドホックネットワークにおいても，Top-k 検索は有効である．モバイルアドホックネットワークは，災害地における救助活動などへの応用が期待されており，レスキュー隊員が自身のもつ端末に被災者や建物の情報を入力し，Top-k 検索によって重傷患者や損壊の激しい建物を検索することが考えられる．しかし，モバイルアドホックネットワークにおける Top-k 検索の研究は，解決すべき問題が多いにも関わらず，ほとんど行われていない．
モバイルアドホックネットワークにおける，Top-k 検索処理において，考えるべき点は 4 つあげられる．まず，移動端末であるため，容量やバッテリに制約があることがあげられる．2
つ目として，基地局が存在しないことや，パケットロスにより，結果の精度を保証することが難しい．3 つ目として，端末が自由に移動するため，ネットワークトポロジが動的に変化する．
最後に，頻繁にメッセージ交換すると，オーバヘッドが大きくなり，パケット衝突が発生する．これらを解決するためには，限られた範囲から上位 k 個のデータを取得し，かつその範囲を周囲の環境に従って動的に決定することが求められる．そこ
で，本稿では，これを実現するために，複製配置を組み合わせ
た Top-k 検索手法について検討する．複製配置は，データの有用性の向上および検索範囲を小さくすることが可能で，モバイ
ルアドホックネットワークの分野では，頻繁に研究されている．
これまでに，モバイルアドホックネットワークにおいて，Top-k
検索と複製配置を効果的に組み合わせた手法は提案されていな
い．さらに，多くの複製配置手法では，移動端末が事前にネットワークの情報（領域サイズや，端末数，ネットワークトポロジなど）を把握していることを前提としている．
そこで，本稿では，モバイルアドホックネットワークにおいて，限られた狭い検索範囲から正確な結果の取得を保証する，
複製配置を組み合わせた Top-k 検索のメッセージ処理手法を提案する．提案手法では，ネットワークの情報が未知であると想定するため，まず上位 k 個のデータ，およびネットワークの情報を取得し，これらをネットワーク内の端末に配布する．ネット

ワークの情報および上位 k 個のデータを受信した端末は，ネッ

上位 k 個のデータの識別子を知る必要がある．本稿で提案するトワークの情報を記録し，提案する複製配置手法である F ReT

手法では，まず上位 k 個のスコアをもつデータを収集し，配布(topology-Free Replication for Top-k query) に従って，データをすることにより，結果の保証および最適な複製配置を行う．

複製として配置する．FReT では，複製配置率と各端末がもつ複

本稿では，上位 k 個のデータを取得するために必要な平均探製の組合せを，Top-k 検索の際にアクセスする端末数が最少に

索端末数，An(kq)，を最小にする複製配置を行う．An(kq) はなるように決定する．Top-k 検索を行う端末（クエリ発行端末）

以下の式で計算する．

は，正確な結果を取得するまで TTL を増加しながら検索を繰り返す．TTL の増加方法として，探索端末数の減少を目的とす

An(kq) =る Expanding ring 法と，探索遅延の減少を目的とする BundlingK∑kqi · An(ki ).

(1)

i=1

法の二つの方法を用いる．両方の手法とも，小さい遅延およびAn(ki ) は，クエリ発行端末が ki を指定した場合の平均探索端

オーバヘッドで，正確な結果の取得を保証することができる．

末数を示す．

提案手法の有効性をシミュレーション実験により評価する．

2. 2 Top-k 検索のための複製配置における問題

以下では，2. で想定環境と問題定義について述べ，3. で関連

Top-k 検索では，アクセスするデータに大きな偏りがあるた

研究について述べる．その後，4. で提案手法について説明し，

め，単一データアクセスのための複製配置を，Top-k 検索のた

5. でシミュレーション実験の結果を示す．最後に 6. で本稿のまめの複製配置に用いることは有用とはいえない．例えば，非構とめと今後の課題について述べる．

造 P2P ネットワークにおける単一データアクセスのための複製

2. 想定環境と問題定義
本稿では，アドホックネットワークを構成する各端末が，自配置として，最適な複製数を決定する平方根配置方式が提案されている [1]．平方根配置では，データ di の複製配置率 ri を以下の式で決定する．

身と他の端末のもつデータに対して Top-k 検索を行う環境を想√qi
ri = ∑kmax √定する．クエリ発行端末は，検索条件を指定して検索クエリをj=1

発行し，ネットワーク内の上位 k 個のスコアをもつデータを取得することを目的とする．

qj

and l <
= ri <
= u.

(2)

1
1
qi は，di を指定する確率，および l (>= M ) は，
= M ·ρ ) と u (<ネットワーク内には，D 個のデータが存在し，識別子 d

最小および最大の複製配置率（少なくとも一台が複製を配置す= {d1 , d2 , · · · , dD } が割り当てられているものとする．本稿でる，およびいずれの端末も同じ複製を複数保持しないものとすは，識別子の添え字をデータの順位とする（つまり，d1 は最もる）を示す．

スコアが高いデータ，および dk は k 番目にスコアが高いデー

Top-k 検索では，スコアが高いデータがスコアが低いデータ

タとする）．それぞれのデータは，特定の端末が保持しており，より頻繁にアクセスされる．そのため，データ di の複製配置

簡単化のためデータのサイズは全て同じとし，更新はないも率は，データ di+1 の複製配置より大きくなる．

のとする．データのスコアは，検索条件とスコアリング関数にri >= ri+1 .

よって決定され，検索条件は，データの種類（被災者情報など）と属性値（重症度など）を指定する．本稿では，一つの検索条
件とスコアリング関数のみを使用するものとする．

(3)

しかし，平方根配置方式を用いた場合，スコアが高いデータの配置率が大きくなりすぎてしまい，データの多様性が低下す

ネット ワ ー ク 内 に は ，M 台 の 端 末 が 存 在 し ，識 別 子 mる．その場合，大きい k が指定された場合，遅延およびオーバ= {m1 , m2 , · · · , mM } が割り当てられているものとする．各端

ヘッドが大きくなってしまう．さらに，単一データアクセスの末は，自由に移動し，ρ 個のデータを複製として配置できるもための複製配置では，データアクセスの依存性を考慮していなのとする．各端末は，通信半径 R の通信機器を保持しているもい．Top-k 検索では，順位が近いデータが同時にアクセスされのとし，GPS などの機器により自身の位置を正確に把握できる

ることが多いと考えられる．

ものとする．
クエリ発行端末は， K 種類の k ，ki (ρ, kmax ] (i = 1, · · · , K)，を kqi の確率で指定する．各端末は，ある k が指定される確率を，統計情報などにより既知であるものとする．

2. 1 モバイルアドホックネットワークにおける Top-k 検索の問題

2. 3 モバイルアドホックネットワークにおける複製配置の問題
モバイルアドホックネットワークでは，端末は自身と近い端末と通信するため，必要なデータがクエリ発行端末の近くに存在する場合，オーバヘッドが小さくなる．そのため，モバイル
アドホックネットワークおよび無線センサネットワークの分野

クエリ発行端末は，検索条件と要求データ数 (k) を指定した

では，位置依存の複製配置手法が数多く提案されている．位置

メッセージを送信し，ネットワーク全体で上位 k 個のスコア依存の複製配置における，検索のためのコスト cost は，以下のをもつデータを取得する．Top-k 検索では，クエリ発行端末は式で計算される．

データの識別子を指定して検索を行わないため，正確な結果を取得できたかを判断することはできない．そのため，理想的な複製配置および結果の保証を行うためには，それぞれの端末がki
cost = Σx∈m ΣK
i=1 kqi Σj=1 dist(x, dj ).

(4)

dist(x, dj ) は，クエリ発行端末 x とデータ dj を保持する端末

との距離を示す．最小の cost を達成する場合，最適な複製配置

製配置手法は，スコアの低いデータを必要以上に多く配置してとなるが，NP 困難問題として知られている．さらに，モバイしまう可能性があり，理想的な複製配置数を達成することはで

ルアドホックネットワークでは，端末が自由に移動するため，きない．

最適な複製配置が動的に変化する．また，隣接端末数も同様に

3. 2 Top-k 検索処理

動的に変化するため，上位 k 個のデータを取得するために検索

様々なネットワーク環境において，Top-k 検索手法が提案さすべき範囲を決定することが難しい．この場合，複製が常に特れている．ここでは，無線センサネットワークおよびモバイル

定の領域に存在するように，各端末がその領域から移動する際

アドホックネットワークにおける Top-k 検索処理手法についてに，複製を交換することで，最適な複製配置を保つことができ説明する．

る．しかし，メンテナンスのためのオーバヘッドが発生し，さ無線センサネットワークにおける Top-k 検索では，通信量のらに端末の密度が変化した場合，複製が存在すべき領域に留め

削減とバッテリの高寿命化を目的して，シンクがマルチホップ通ることができない可能性がある．したがって，端末が移動して信でデータを収集する方法が数多く提案されている．文献 [12]も，メンテナンスのためのオーバヘッドが必要ない手法，およでは，各端末にフィルタを配布して，そのフィルタを通過する

び探索範囲を動的に決定する方法が有効と考えられる．

データのみをシンクに送信する手法を提案している．フィルタ

3. 関 連 研 究
様々なネットワーク環境において，複製配置手法，およびTop-k 検索手法が提案されている．ここでは，代表的な既存手法について説明する．

3. 1 複 製 配 置
モバイルアドホックネットワークにおける複製配置手法について説明する．文献 [3] では，データの可用性の向上を目的として，三つのアルゴリズムが提案されている．それぞれのアルゴ
リズムは，データのアクセス率，隣接端末が保持する複製，およびネットワークトポロジを考慮して，配置する複製を決定す
る．文献 [6] では，LACMA(location-aided content management

architecture) と呼ばれる位置依存の複製配置手法が提案されている．LACMA では，データは特定の区切られた領域（グリッド）に配置され，グリッド内を検索することによって要求データを取得できることを保証する．グリッドのサイズは，データのアクセス率によって決定され，より頻繁にアクセスされるデー
タが配置されるグリッドは小さくなる．端末が特定のグリッドから移動する際，そのグリッドに留めるべきデータをプッシュすることにより，データを特定のグリッドに存在させる．しかし，グリッド内に端末が存在しない場合，データのプッシュは成功しない．これらのプロトコルは，基本的に一回の検索で一つのデータを検索することを想定している．しかし，Top-k 検索のような，ランクベースのクエリでは，一度の検索で複数のデータの取得する．提案手法では，小さい探索端末数で k 個のデータを取得することを目的としており，これらの手法より複製データの配置を決定することが難しい．さらに，提案手法は，端末の移動に伴うメンテナンスコストが発生しないことも目的としている．
文献 [4] において，モバイルアドホックネットワークにおけを通過するデータは，上位 k 個のデータに影響を与えるデー
タとなる．文献 [5] では，文献 [13] で提案されている集中管理
データベースにおける効率的な Top-k 検索のためのデータ構造であるドミナントグラフを用いたフィルタにより Top-k 検索を効率的に行う方法を提案している．無線センサネットワークでは，固定端末およびネットワーク内で一つのシンクを想定している点で，モバイルアドホックネットワークとは異なる．
筆者らの知る限りでは，モバイルアドホックネットワークにおける Top-k 検索処理手法は，文献 [2], [9] [10], [11] でのみ提案されている．文献 [9] での想定環境 (例えば，仮想的な通貨)は，本稿で想定する環境と本質的に違う．文献 [2], [10], [11] では，クエリ発行端末が検索メッセージをネットワーク全体に送信し，受信した端末はスコアが高いデータのみを返信する．これにより，無駄な返信データの最小化を目的としている．これらの手法では，複製を考慮していない点，ネットワーク全体へメッセージを送信する点，およびパケットロスが発生した場合，正確な結果を取得することができない点が問題となる．しかし，本稿で提案する手法においても，初期手順として，ネットワー
ク全体からデータを収集することが必要となるため，文献 [2]を拡張した手法を用いる．文献 [2] では，自身が保持するデー
タの一部を基準値として，検索メッセージに添付し，上位 k 個に入らないデータを絞り込む．検索クエリ送信時に，基準値の更新および，クエリ発行端末を根とする木構造の親子関係を構築する．返信時は，まず子端末がいない端末が，基準値のうち最も小さい値を閾値として，閾値以上のスコアをもつデータのみ親端末へ返信する．全ての子端末から返信データを受信した
端末は，同様にデータを自身の親端末へ返信する．最終的に，クエリ発行端末は，パケットロスが発生しない限り，上位 k 個のスコアをもつデータを無駄な返信データを抑制しつつ，取得することができる．

る Top-k 検索のための複製配置手法が提案されている．この手法では，返信データを受信および中継した端末がそのデータを

4. 提 案 手 法

複製として配置する．その際，データのスコアと乱数を用いて本章では，複製配置手法，初期データ収集と配布の方法，お配置する複製を決定するため，スコアが高いデータがよく配置

よび Top-k 検索のメッセージ処理手法について説明する．

されつつ，多様性も維持することができる．しかし，この手法

4. 1 複製配置手法

では，複製配置手法のみを提案しており，複製が配置されてい4. 1. 1 複製組合せる状況における，Top-k 検索手法は提案されていない．この複Top-k 検索では，順位が近いデータを同時にアクセスする可能性が高い．そのため，各端末はデータを ρ 位毎に区切って複製するように決定する．

る（つまり，d1 から dρ ，dρ+1 から d2·ρ および d⌈ kmax ⌉·ρ−ρ+1

4. 2 初期収集および配布手法

から dkmax ）．ρ 位毎に区切られたデータの複製を複製組合せと最適な複製配置を行うためには，各端末がネットワークの情

呼び，それぞれの複製組合せの配置率を rci (i = 1, · · · , ⌈ kmax⌉)
ρ

報を知る必要がある．そのため，Top-k 検索を最初に行う端末とする．FReT では，最適な複製配置となるように，複製組み

Mc は，初期メッセージを転送し，上位 kmax 個のデータ，端合わせの配置率を決定する．

末数および端末の位置情報を収集する．収集のオーバヘッドをρ

できる限り小さくするために，文献 [8] で提案されている位置

4. 1. 2 複製配置率
最適に複製配置した場合，各端末は少数の端末の探索により，ベースフラッディングと，文献 [2] で提案されている Top-k 検

上位 k 個のデータを取得することができる．クエリ発行端末が索手法を組み合わせて，収集を行う．Mc は，情報を収集後に，アクセスできる端末数は，隣接端末数とホップ数によって決ま

上位 kmax 個のデータ，ネットワーク内の端末数および平均隣

り，ホップ数および隣接端末数が多くなるにつれて，アクセス

接端末数の情報を位置ベースフラッディングを用いて，全てのできる端末数は増加する．そこで，まず，あるホップ数 hop に端末に配布する．受信した端末は，上位 kmax 個のデータの識対して，アクセスできると予想される端末数 nh ，を以下の式

別子，ネットワーク内の端末数，および平均隣接端末数を把握で決定する．

し，複製を FReT に従って配置する．

nh = ann ×

hop∑

初期データ収集の手順をアルゴリズム 1 に示す．初期メッ

j.

(5)

セージ IM には，検索条件，kmax ，送信端末の識別子 (s)，送信端末の親端末の識別子 (p)，送信端末の位置，および基準値

j=1

ann は，平均隣接端末数を示す．この式では，端末が一様に存が含まれている．返信メッセージには，送信端末の識別子，送在すると仮定して，全ての端末が平均隣接端末数と同じ隣接端

信端末の親端末の識別子とスコア，端末の位置のリスト，閾値，

末数がいるものとし，計算している．隣接端末数が極端に多い

および閾値以上のスコアをもつデータが含まれている．初期場合，この式は正確ではないが，本稿では，それほど多い隣接

メッセージの転送時では，各端末は，ACK を送信することによ

端末数を想定していない．

り，親子関係を構築する．このメッセージ処理では，全ての子

さらに，nh 台の端末とアクセスできた場合に，上位 ki 個の行）．さらに，Mc が事前に設定した時間 (max wait) 内に全てデータを取得できる確率，P (ki , nh ) を次式で決定する．

の子端末から受信できなかった場合，もう一度初期メッセージP (ki , nh ) = 1 − (rc1 + · · · + rc⌈ ki ⌉ )の転送を行う（23–25 行）．これにより，すべての端末から情ρ+(rc1 + rc2 + · · · + rc⌈ ki ⌉−1 + rc⌈ ki ⌉ )ρ

報を収集することができる．

ρ

4. 3 Top-k 検索のメッセージ処理手法+···k⌈ ρi ⌉+(−1)

端末からの返信が返ってこない場合，返信を開始しない（18–20· rc1 + · · · + rc⌈ ki ⌉ .

(6)ρ

本 節 で は ，Top-k 検 索 手 法 で あ る ，Expanding ring 法 とBundling 法について説明する．両手法とも，クエリ発行端

ここで，rci は，(1 − rci )nh を示す．この式では，nh 台の端

末は，まず ‘初期検索クエリ’ を発行し，その後上位 k 個の末にアクセスした際に，それぞれ rc1 から rc⌈ ki ⌉ を保持する

データを取得するまで ‘再検索クエリ’ を繰り返し発行する．

端末にアクセスできない確率を求め，その余事象の確率を用い

Expanding ring 法と Bundling 法の違いは，TTL の決定法である．

て，全ての複製組合せにアクセスできる確率を求めている．こ

初期検索クエリと再検索クエリのメッセージ処理手順を，その際，nh が ⌈ kρi ⌉ より小さい場合，P (ki , nh ) は 0 とする．nh

れぞれアルゴリズム 2 およびアルゴリズム 3 に示す．初期検が増加するほど，必要なデータを取得できる確率が増加するた

索クエリ F Q は，クエリ発行端末の識別子，クエリの識別子，

め，P (ki , nh ) も増加する．しかし，nh は小さいほうがよく，

検索条件，k ，およびクエリ発行端末が保持する複製のリスト

P (ki , nh ) は大きい方がよいため，理想的なホップ数は，最小(listqi ) が含まれている．再検索クエリ RQ は，クエリ発行端ρnhの P (ki ,niを達成する値となる．加えて，P (ki , nh ) は，デー)末の識別子，クエリの識別子，要求するデータの識別子，送信タ d1 から dki がより多く配置されている場合に大きくなるが，端末の識別子 (s)，送信端末の位置，および TTL が含まれてい小さい k にだけ着目した場合，複製の多様性が低下してしまう．

る．両方のクエリに対する，返信メッセージは，クエリ発行端

そこで，全体として最小のアクセス端末数を達成するため，そ末の識別子，クエリの識別子，送信端末の識別子，送信端末のhi

れぞれ ki に対しての nh ，nhi を計算する．これらの要素を考

親端末の識別子，および返信データ (rd) が含まれている．それ慮して，平均探索端末数 An(kq)，を次式で決定する．

ぞれの端末は，メッセージを傍受し合うことにより，返信デー

K∑An(kq) =(kqi ·
i=1

タ数の削減を行う（アルゴリズム 2 内の 12–14 行，およびアルnh i)
P (ki , nhi )(7)An(kq) が最小となる場合，クエリ発行端末は，小さいホップ

ゴリズム 3 内の 31–33 行）．
初期検索クエリと再検索クエリには，大きく３つの違いがある．まず，前者では，k と検索条件を指定するのに対して，後数かつ高確率で要求するデータを取得することができる．従っ者は要求データの識別子を指定する．k と検索条件を指定したて，FReT では，複製組み合わせ配置率を An(kq) が最小とな方が，メッセージサイズは小さいが，再検索クエリの場合，単Algorithm 1 初期収集方法
Require: A query condition and kmax
Ensure: Data items with kmax highest scores and positions ofnodes
1: Mc broadcasts IM
2: if Node, Mr receives IM then3:
if Receives first then4:Stores the information on IM
5:
Sets a query timer
6:
end if7:
Updates SS and neighbor nodes
8: end if
9: if Mr expires its query timer then10:
Calculates communication range of neighbor nodes //Proposed in [8]11:if Communication range of Mr is not covered then
12:
Broadcasts IM
13:
Sets a reply timer
14:
else
15:
Sends a reply message to its parent
16:
end if
17: end if
18: if Mr expires its reply timer and has no children or receives
replies from its all children then19:
Sends a reply message to its parent
20: end if
21: if Mc receives replies from all its children then22:
Starts distributing the collecting information by using thelocation-based flooding
23: else if max wait has passed from sending IM by Mc then24:
Mc broadcasts IM again
25: end if

Algorithm 2 初期検索クエリ
Require: A query condition and k
Ensure: Data items with k highest scores
1: Mq broadcasts F Q
2: if Node, Mr receives F Q then3:
Stores the information on F Q
4:Sets a reply timer
5: end if
6: if Mr expires its reply timer then7:
for Replicas, di held by Mr that are not included listqi andare not overheard do8:
rd ← rd ∪ di9:
end for10:
Sends a reply message to the query issuer
11: end if
12: if Mr overhears a reply message then13:
Stores rd.
14: end if
15: if Mq acquires the top-k result then16:
Query is over
17: else if Mq wait a maximum reply timer then18:
Stores the number of nodes replied for the bundling method
19:
Go to Algorithm 3
20: end if
4. 3. 2 Bundling 法
Bundling 法では，クエリ発行端末は自身の隣接端末数を考慮して，TTL を設定する．しかし，クエリ発行端末は自身の現在の隣接端末数 cnn を知らないため，初期検索クエリの TTL は1 とする．初期検索クエリ発行後に，クエリ発行端末は，隣接端末の情報を更新できるため，最初の再検索クエリの TTL を純に必要なデータの条件を指定することができないため，識別子を添付する．また，初期検索クエリでは，クエリ発行端末が一度に大きくする．具体的には，クエリ発行端末が ki を指定するとき，以下の式を満たす TTL を設定する．

保持する複製が返信されるのを防ぐために，listqi を添付する．

cnn ×

次に，後者は位置ベースフラッディングを用いるのに対して，

前者では，TTL が 1 であるため，使う機会がない．そのため，メッセージサイズを不要に大きくすることを防ぐために，位置情報の添付を行わない．最後に，後者は，探索範囲を広げるた
めに TTL を設定するが，前者では行わない（TTL は常に 1）．
これは，上位 k 個のデータを近くの端末から取得するため，および現在の隣接端末数をできる限り早く取得するためである．

4. 3. 1 Expanding ring 法
P2P ネットワークにおける，Expanding ring 法は，文献 [7] で

j>

j=1

前者は行わない．これは，後者は，TTL が大きくなっていくた
め，位置ベースフラッディングを使う機会があるのに対して，

T
TL
∑

nh i
.
P (ki , nhi )(8)

nhi および P (ki , nhi ) は，それぞれ最適な複製配置をにおける，
式 (7) の値である．この式は，高い確率で上位 ki 個のデータを取得できる TTL(>= 2) を決定する．もし，クエリ発行端末が式(8) で設定した TTL で上位 k 個のデータを取得できなかった場
合，それ以降は 1 ずつ増加させる．Bundling 法では，TTL を一度に大きくできるため，遅延を小さくすることができるが，不必要に TTL を大きくしてしまった場合，Expanding ring 法に比べて，返信データ数は増加する．

5. 性 能 評 価

提案されており，探索端末数を最小にするため，TTL を徐々に本章では，提案手法の性能評価のために行ったシミュレーショ

増加させていく．提案する Expanding ring 法では，初期検索ク

ン実験の結果を示す．本実験では，ネットワークシミュレータ

エリの TTL を 1 に設定，および再検索クエリの TTL は，前回

Qualnet5.2 を用いた（注 1）．

のクエリの TTL より 1 増加させた値とする．この方法は，単純

5. 1 評 価 環 境

であるが，返信データ数を最小にすることができ，オーバヘッ

1,000[m]×1,000[m] の 2 次元平面上の領域に M 台の端末ド削減に効果的である．しかし，隣接端末数が少ない場合，再検索クエリの回数が多くなり，遅延が増加してしまう．

（注 1）：Scalable Networks: makers of QualNet and EXata, the only multi-core enabled

network simulation and emulation software. [Online]. Available: http://www.scalablenetworks.com/.

Algorithm 3 再検索クエリ
Require: Identifiers of demand data items
Ensure: Demand data items
1: Mq broadcasts RQ
2: if Node, Mr receives RQ then3:
if Receives first then4:Stores the information on RQ
5:
Decreases T T L by 1
6:
if Has demand data items then7:
Sends a reply message to its parent
8:
Demand data items ← demand data items - rd9:
end if10:
if T T L > 0 and demand data items =| N U LL then11:
Updates RQ
12:
Sets a query timer
13:
end if14:
end if15:
Updates neighbor node
16: end if
17: if Mr expires its query timer then18:
Calculates communication range of sender nodes
19:
if Communication range of Mr is not covered then
20:
Broadcasts RQ
21:
Sets a reply timer
22:
end if
23: end if
24: if Mr receives a reply message then25:
for Reply data items rdi are not sent to parent node, and are
not overheard do26:
rd ← rd ∪ rdi
27:
end for28:
if rd =
| N U LL then29:
Sends a reply message to its parent
30:
end if
31: else if Mr overhears a reply message then32:
Stores rd
33: end if
34: if Mq acquires the top-k result then35:
Query is over
36: else if Mq expires a timer determined based on TTL then37:
Updates RQ
38:
Mq broadcasts RQ again
39: end if

表 1 メッセージサイズ

メッセージ

サイズ [bytes]
288
初期収集返信32+128 · i1 +16 · i2
初期収集 (単純手法)
44
初期収集返信 (単純手法)
28+128 · i1 +16 · i2
ACK (初期収集)
16
配布
12844
初期検索クエリ36
再検索クエリ
36+4 · i3
LACMA におけるクエリ
40
返信 (全手法共通)
24+128 · i4
プッシュ (LACMA におけるメンテナンス) 32+128 · i5
初期収集

た平均時間．

•

初期オーバヘッド [Kbytes]: 初期データ収集および配布

における，初期メッセージの総バイト数．メッセージサイズを
表 1 に示す．この表において，i1 は，初期収集の返信メッセー
ジに含まれるデータ数，および i2 は，初期収集の返信メッセージ含まれる端末の位置情報数を示す．

•

検索オーバヘッド [Kbytes]: シミュレーション終了 (クエリ数 300) までに発生した検索クエリおよび返信メッセージの総バイト数． メッセージサイズを表 1 に示す．この表において，i3 は，再検索クエリに含まれる要求データの識別子数，i4
は，返信メッセージに含まれるデータ数，および i5 は，プッ
シュメッセージに含まれるデータ数を示す．

5. 2 比 較 手 法
位置依存の複製配置手法 LACMA と，提案手法である Ex-

panding ring 法および Bundling 法を比較する（グラフの凡例;
ER FReT，および B FReT）．
（ 1 ） LACMA（凡例; LACMA）: データは特定のグリッドに配置される．本実験では，グリッドのサイズは k のアクセス頻
度と端末数によって決定する（つまり，4 種類のグリッドが存在する）．検索の際は，クエリ発行端末は，検索メッセージを自身が所属するグリッドにフラッディングし，上位 k 個のデー
タを取得する．あらかじめ設定された時間内に，上位 k 個のデータを取得できない場合，検索を終了する．また，LACMA（m1 , . . . , mM ）が存在し，初期位置をランダムに決定した．各では，複製を特定のグリッドに留める必要があるため，端末が端末はランダムウォークモデルに従い，0.5 から 1[m/秒] の速自身が現在所属するグリッドから移動する際に，留めておくべ

度で移動する．各端末は，IEEE802.11b を使用し，伝送速度

き複製をプッシュし，その複製を自身の複製領域から削除する

11[Mbps]，通信伝搬距離が 100[m] 程度となる送信電力でデー（メンテナンスに係るオーバヘッドの凡例を LACMA M とす

タを送信する．各端末は，128[B] のサイズのデータをそれぞれる）．複製を受信した端末は，自身の複製領域に空きがあれば，100 個を保持するものとし，5 個のデータを複製として配置す

そのデータを複製として配置する．

ることができる (ρ = 5)．

（ 2 ） Reiterate LACMA（凡例; ReLACMA）: LACMA を用

クエリ発行端末は，k として，25，50，75，および 100 を等しい確率で指定し，30 秒間隔でクエリを発行する．
以上のシミュレーション環境において，端末台数を変化させ，クエリを 300 回発生させた場合の評価値を調べた．

•

検索精度: 上位 k 個のデータうち，取得できたデータ数の平均割合．

•

遅延 [秒]: 検索クエリ発行後，データ取得までに経過しいてデータを取得後，上位 k 個のデータを取得できなかった場合，クエリ発行端末は提案した再検索クエリを上位 k 個のデー
タを取得できるまで繰り返す．この際，最初の reierate query の√2
TTL を grid width·とし，その後，1 ずつ増加させる．
R

さらに，2 つの複製配置方式と提案手法 FReT と比較する．
（ 1 ） 一様配置: 全ての上位 k 個のデータを同じ確率で複製として配置する．

に従って，データを複製として配置する．
これらの複製配置方式と比較する際は，Expanding ring 法および Bundling 法を Top-k 検索処理手法として用いる（グラフの凡例; ER uni，B uni，ER SQRT，および B SQRT）．

5. 3 評 価 結 果
5. 3. 1 初期収集および配布
まず，初期収集および，初期配布手法の性能を端末数 M を変化させて調べた．比較手法として，単純なフラッディングお

12000
Proposed collection
Proposed disseminationNaïve collectionNaïve dissemination

10000
初期オーバヘッド（ 2 ） 平方根配置: 文献 [1] で提案されている平方根配置方式

8000
6000
4000
2000
0
300

400

500
600
端末数, M

700

800

図 1 初期収集および配布手法

よび自身の保持するデータと受信したデータのうち上位 k 個のデータを返信する単純手法（凡例; Naive collection，およびぼ同等のオーバヘッドを達成することができている．Reiterate

Naive dissemination）を用いる．その結果を図 1 に示す．このグ

LACMA は，非常に大きなオーバヘッドが発生しているのがわ

ラフにおいて，横軸は端末数 M を表し，縦軸は，初期オーバ

かる．これは，LACMA では，端末がグリッドを移動した際に，ヘッドを表す．

複製を削除するため，探索範囲が大きくなってしまうためであ

この結果から，提案した初期収集および配布手法は，単純手る．さらに，LACMA では，端末数が増加すると，メンテナン法より低いオーバヘッドを達成しているのがわかる．これは，スのオーバヘッドも増加する．ここで，初期収集のオーバヘッ

まず初期収集では，不必要なデータ返信および，メッセージ送ドは，要求データ数 k が 100 の時の Top-k 検索の 1 回分のオー信を抑制できているためである．初期配布においては，位置

バヘッドとほぼ同様と考えることができる．図 1 の初期オー

ベースフラッディングにより，メッセージ送信数を抑制できてバヘッドと検索オーバヘッドを比較して，検索オーバヘッドはいるためである．初期収集の方が初期配布に比べて，オーバ

Top-k 検索の 300 回分のオーバヘッドであるにも関わらず，非ヘッドが小さいのは，配布では，kmax (つまり，100) 個のデー

常に低く抑えられていることがわかる．これにより，複製の配タを送信するのに対し，収集では，基準値により返信データ数

置により探索範囲を小さくすることは，収集および配布にかかが kmax より小さいためである．また，単純手法における収集るオーバヘッドを考慮しても，ネットワーク全体として，オーと配布では，全ての端末が kmax 個のデータを送信するため，

バヘッドを大幅に抑制できていることがわかる．

ほぼ同じ結果となっている．

この結果より，提案手法は，小さい遅延およびオーバヘッド

5. 3. 2 Top-k 検索処理

で，取得精度を維持できていることがわかる．さらに，FReT

次に，Top-k 検索処理手法の性能を端末数 M を変化させてでは，位置依存の複製配置手法より，端末の移動に対して耐性調べた．その結果を図 2 に示す．これらのグラフにおいて，横があり，高い性能を達成していることがわかる．

軸は端末数 M を表し，縦軸は，図 2 (a) では，検索精度，図 2

5. 3. 3 複 製 配 置(b) では，遅延，および図 2 (c) では，検索オーバヘッドをそれ最後に，複製配置手法の性能を端末数 M を変化させて調べぞれ表す．
図 2 (a) より，提案手法は正確な結果を取得できていることがわかる．一方，再検索クエリを用いない LACMA では，正確な結果を取得できてない．これは，端末の移動，端末の疎密差，およびパケットロスが原因である．

た．その結果を図 3 に示す．これらのグラフにおいて，横軸は端末数 M を表し，縦軸は，図 3 (a) では，遅延，および図 3 (b)では，検索オーバヘッドをそれぞれ表す．
図 3 (a) より，FReT を用いた Bundling 法が最も小さい遅延を達成していることがわかる．また，FReT を用いた Expanding

図 2 (b) より，Bundling 法が最も小さい遅延を達成しているこ

ring 法も同様に小さい遅延を達成している．これは，FReT が適とがわかる．これは，TTL を一度に大きくすることにより，探切な複製の多様性を達成しているためである．一方で，平方根索範囲を上位 k 個のデータを高い確率で取得できる範囲に一度配置方式の性能は低くなっている．これは，複製の多様性が低で拡大できるためである．また，Expanidng ring 法も同様に小くなっており，再検索クエリの送信数が多くなってしまうため

さい遅延を達成している．これは，Bundling 法に比べ，検索クである．図 3 (b) より，FReT を用いた Expanding ring 法のオー

エリの送信回数は多いが，小さい探索範囲を達成できているた

バヘッドが最も小さい．また，FReT を用いた Bundling 法も他めである．端末数が多くなると，より近い端末から上位 k 個のの複製配置手法を用いた Bundling 法より小さいオーバヘッドを

データを取得しやすくなるため，Expanding ring 法と Bundling

達成している．ここで，一様配置手法と平方根配置方式のオー法の遅延の差が小さくなる．一方，LACMA では，提案手法よバヘッドがほぼ同様なのは，上位 k 個のデータを取得するため

り遅延が大きい．これは，上位 k 個のデータを取得できないこの平均ホップ数がほぼ同じとなっているためである．

とが多く，最大待ち時間まで待ってしまうためである．
図 2 (c) より，Expanding ring 法が最も小さいオーバヘッドを

この結果より，FReT では，遅延およびオーバヘッドの両方の観点において，高い性能を達成していることがわかる．

達成しているのがわかる．これは，より近くの端末から上位 k個のデータを取得できているためである．Bundling 法におい6. お わ り にても，正確な上位 k 個のデータを取得しながら，LACMA とほ

本稿では，モバイルアドホックネットワークにおける，複製ER_FReT

B_FReT

LACMA

ReLACMA
検索オーバヘッド

5
4
遅延

検索精度

6

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

ER_FReT
B_FReT

3
2

LACMA
1

ReLACMA

0
300

400

500
600
端末数, M

700

800

300

400

500
600
端末数, M(a) 検索精度

700

800

50000
45000
40000
35000
30000
25000
20000
15000
10000
5000
0

ER_FReTLACMA
LACMA_M

300(b) 遅延400

B_FReT
ReLACMA

500
600
端末数, M700(b) 検索オーバヘッド

図 2 Top-k 検索手法
8

18000
ER_FReT

ER_uniER_SQRT

B_FReT

B_uni

B_SQRT

16000

7

14000
検索オーバヘッド

6
遅延

5
4
3
2

12000
10000
8000
6000
4000

1

2000

0

0
300

400

500
600
端末数, M

700

800

300

(a) 遅延配置手法，FReT，では，複製のメンテナンスコストなしで，上位 k 個のデータを取得するための探索端末数を小さくすること[3]を実現した．提案した Top-k 検索のメッセージ処理手法では，検索クエリ発行端末が TTL を増加させながら，上位 k 個のデー
タを取得するまで，検索クエリを繰り返して送信する．TTL の[4]増加方法として，Expanding ring 法と Bundling 法を提案した．

Expanding ring 法では，最少の探索端末数を達成し，Bundling[5]

法では，より小さい遅延を達成した．それぞれの手法ともに，
上位 k 個のデータを確実に取得することができる．シミュレー
ション実験によって，提案手法が高い性能を示していることを

[6]

確認した．
本稿では，簡単化のため，いくつかの想定を単純化した．例[7]

えば，同じデータサイズ，同じサイズの複製領域，およびデー
タの更新が発生しないことなどがあげられる．しかし，これら[8]は，実環境において必ずしも正しいとはいえない．そのため，これらの想定を外した場合の複製法およびメッセージ処理手法[9]について，今後取り組む予定である．

辞

[10]

本研 究 の 一 部 は ，文 部 科 学省 研 究 費 補助 金・基 盤研 究 S（21220002），基盤研究 B（24300037），および特別研究員奨励費（24-293）の研究助成によるものである．ここに記して謝意

[11]

を表す．

[1]

[2]

ER_SQRT

B_uni

B_SQRT

400

500
600
端末数, M

700

800

複製配置手法

配置を組み合わせた Top-k 検索手法を提案した．提案した複製

文

ER_uni

B_FReT(b) 検索オーバヘッド
図3

謝

ER_FReT

献

E. Cohen and S. Shenker. Replication strategies in unstructured peer-to-peer
networks. In ACM SIGCOMM Computer Communication Review, volume 32,
pages 177–190. ACM, 2002.
R. Hagihara, M. Shinohara, T. Hara, and S. Nishio. A message processing

[12]

[13]

method for top-k query for traffic reduction in ad hoc networks. In Mobile DataManagement: Systems, Services and Middleware, 2009. MDM’09. Tenth International Conference on, pages 11–20. IEEE, 2009.
T. Hara. Effective replica allocation in ad hoc networks for improving data accessibility. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE
Computer and Communications Societies. Proceedings. IEEE, volume 3, pages
1568–1576. IEEE, 2001.
T. Hara, R. Hagihara, and S. Nishio. Data replication for top-k query processing in mobile wireless sensor networks. In Sensor Networks, Ubiquitous, andTrustworthy Computing (SUTC), 2010 IEEE International Conference on, pages
115–122. IEEE, 2010.
H. Jiang, J. Cheng, D. Wang, C. Wang, and G. Tan. A general framework
for efficient continuous multidimensional top-k query processing in sensor networks. Parallel and Distributed Systems, IEEE Transactions on, 23(9):1668–
1680, 2012.
S. Lee, S. Wong, K. Lee, and S. Lu. Content management in a mobile ad hoc network: Beyond opportunistic strategy. In INFOCOM, 2011 Proceedings IEEE,
pages 266–270. IEEE, 2011.
Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in
unstructured peer-to-peer networks. In Proceedings of the 16th international
conference on Supercomputing, pages 84–95. ACM, 2002.
S. Ni, Y. Tseng, Y. Chen, and J. Sheu. The broadcast storm problem in a mobile ad hoc network. In Proceedings of the 5th annual ACM/IEEE international
conference on Mobile computing and networking, pages 151–162. ACM, 1999.
N. Padhariya, A. Mondal, V. Goyal, R. Shankar, and S. Madria. Ecotop:
an economic model for dynamic processing of top-k queries in mobile-p2p
networks. In Database Systems for Advanced Applications, pages 251–265.
Springer, 2011.
Y. Sasaki, R. Hagihara, T. Hara, M. Shinohara, and S. Nishio. A top-k query
method by estimating score distribution in mobile ad hoc networks. In Advanced
Information Networking and Applications Workshops (WAINA), 2010 IEEE 24th
International Conference on, pages 944–949. IEEE, 2010.
Y. Sasaki, T. Hara, and S. Nishio. Two-phase top-k query processing in mobile
ad hoc networks. In Network-Based Information Systems (NBiS), 2011 14th
International Conference on, pages 42–49. IEEE, 2011.
M. Wu, J. Jianliang Xu, X. Xueyan Tang, and W.-C. Wang-Chien Lee. Top-kmonitoring in wireless sensor networks. IEEE Transactions on Knowledge andData Engineering, (7):962 –976, 2007.
L. Zou and L. Chen. Dominant graph: An efficient indexing structure to answer
top-k queries. In Proceedings of the 2008 IEEE 24th International Conferenceon Data Engineering, pages 536–545, 2008.

800