学位論文紹介

PhD Thesis Review, No. 15

ア ド ホック ネット ワ ー ク に お け る
Top-k 検索のためのルーティング技術に関する研究

1.

Research on Routing Techniques for Topk Data Retrieval in Ad hoc Networks

また，ユーザが必要とするデータのみを検索する技術は，これま

はじめに

近年，無線通信端末のみで自律分散的にネットワークを構築するアドホックネットワークへの関心が高まっており，緊急災害時などのインフラが利用できない環境での利用が期待されている．
でに多くの関心を集めており，ユーザが指定した条件からデータをスコア付けし，その上位 k 個のデータを検索する Top-k 検索は，その一つの技術である．アドホックネットワークにおいても

天方 大地

♡

Top-k 検索は実用的な検索手段であり，災害地において優先的な救援を必要とする重症患者の検索支援など，様々な状況で効果的

Daichi AMAGATAに利用できる．例えば，図 1 に示すように，利用可能な医療資源（救急車など）が 1 つの場合，Top-1 検索を行うことによって，本研究は，アドホックネットワークにおける Top-k 検索のため負傷 Lv. の高い被災者のデータを得ることできる．の効率的なルーティング手法の実現を目的とする．近年の無線通筆者の研究グループでは，これまでにアドホックネットワーク信技術の進化により，無線通信端末のみで構築されるアドホックにおける Top-k 検索手法を提案した [2, 4, 5]．しかし，既存手ネットワークに関心が高まっている．また，Top-k 検索は，スコ法では，ネットワーク内の全ての端末にメッセージを送信して上アに基づく上位 k 個のデータを検索する方法である．例えば，災位 k 個のデータを検索するため，通信量および遅延が大きい．そ害地において構築されたアドホックネットワーク上で Top-k 検こで，本研究では，アドホックネットワークにおいて，効率的な索を行うことにより，災害救助を効率化するといった応用例が考えられる．アドホックネットワークは無線で通信を行なうため，Top-k 検索を実現するためのルーティング手法を提案する．

通信量を可能な限り削減する必要がある．そこで，上位 k 個の課題 1（通信量の削減）. 無線で通信を行うアドホックネット

データを取得するために必要な端末にのみメッセージを送信する

ワークでは，パケットロスや端末の電力消費を抑制する必要があ

ルーティング手法を提案する．これにより，高精度，小さい通信るため，通信量を削減しなければならない．つまり，ネットワー量，および低遅延といった要件を満たし，アドホックネットワー

ク内の全ての端末にメッセージを送信する手法は効率的ではな

ク上におけるデータ検索技術に貢献する．

く，特にパケットロスにより必要なデータを取得できなくなるという問題が発生する．この問題を解決するためには，上位 k 個のを維持できる．
課題 2（モバイル環境への対応）. ネットワークを構成する端末が自由に移動するモバイルアドホックネットワークでは，ネットワークトポロジが動的に変化するため，メッセージの送信経路を⿕⅏⪅ ㈇യLv.

1

C

20B

15

D

8㈇യLv.䛾኱䛝䛔⿕⅏⪅䜢1ே
▱䜚䛯䛔䠊

9F

2…

⿕⅏⪅ ㈇യLv.

A

E…

⿕⅏⪅ ㈇യLv.

…
⿕⅏⪅ ㈇യLv.
G10H

5…

…

大阪大学大学院情報科学研究科

ング手法を実現することにより，通信量を削減しつつ，検索精度…

正会員

チが有効であり，これを可能とする Top-k 検索のためのルーティ…

♡

データを取得するために必要な端末のみで検索を行なうアプロー…

This work aims at processing eﬃcient top-kquery processing by routing techniques in ad hocnetworks. Due to the recent advance in wirelesscommunication technologies, ad hoc networks, whichconstructed only by wireless nodes, have been receiving a signiﬁcant attention. The top-k query processing is to rank data based on scores and retrieve
the k data with the best score. Top-k query processing in ad hoc networks have practical applications,for example, rescue eﬀort at disaster sites. Becauseof wireless communications, we need to minimize
communication cost. We therefore propose routing
methods that query only nodes which are necessary
to obtain the top-k data. We satisfy high-accuracy,
small communication cost, and small delay, which
contributes to the advance in data retrieval techniques in ad hoc networks.

amagata.daichi@i
図 1 アドホックネットワーク上での Top-k 検索例

st.osaka-u.ac.jp

15 - 1

日本データベース学会

学位論文紹介PhD Thesis Review, No. 15䜽䜶䝸䝯䝑䝉䞊䝆㡰఩ ᐄඛ

静的に管理すると検索精度が低下する．そのため，小さい通信量㡰఩ ᐄඛ

でメッセージの送信経路を動的に管理することが重要である．
課題 3（多様な検索条件への対応）. Top-k 検索の検索条件は，

1J

2

M

1F

2JNI㡰఩ ᐄඛ K
1Iのためのルーティングについて考える．後者の場合，条件によっ22H㡰఩ ᐄඛDHえられる．本研究では，これら二つに対する効率的な Top-k 検索

EFM

コアが一意の場合），およびユーザが個々に指定できる場合が考

1

G

J

アプリケーションが統一している場合（またはデータに対してス䜽䜶䝸Ⓨ⾜➃ᮎ㡰఩Uᐄඛ

1A

2E

E
ALB

㡰఩ ᐄඛ

Mてデータの順位が変わるため，どのような条件においても，必要1Aな端末にのみメッセージを送信できるアプローチが必要である．

2HC(a) 提案手法（2.1 節）

本研究では，上の課題に取り組み，アドホックネットワークにおける効率的な Top-k 検索を実現する．検索精度を高く維持し䜽䜶䝸䝯䝑䝉䞊䝆㡰఩ ᐄඛ㡰఩ ᐄඛ 㡰఩X ᐄඛ1I
1Jつつ，小さい通信量を達成するためには，Top-k データの取得に必要な端末のみで検索することが有効である．そのため，これを2MN2実現する Top-k 検索のためのルーティング手法の提案を目的す

1 WF
2JMI

1E

2H

GJる．また，検索条件やネットワークトポロジの変化に影響せず，

H

㡰఩ ᐄඛ

DFM

効率的に上位 k 個のデータを検索できるルーティング手法が望ま䜽䜶䝸Ⓨ⾜➃ᮎ

㡰఩Uᐄඛ

1

しい．この手法を実現するためのステップとして，本研究では，

2

1

H端末のみで Top-k 検索を実行できる手法について考え，クエリ

2M

A

㡰఩
L ᐄඛ㡰఩ ᐄඛ

検索条件およびネットワーク環境にそれぞれ制約を置き，必要なA

E

K
1E

2K

CCE

B

㡰఩ ᐄඛ
1A

2H

C

ルーティングの有効性を検証する．

(b) 拡張手法（2.1 節）

2.

提案手法

2.1

経路表を用いたルーティング手法

本節では，統一された検索条件の下で Top-k 検索を行う環境を想定し，経路表を用いたルーティング手法を紹介する．このような環境では，各端末が上位のデータを取得するために必要な情報を経路表で管理することにより，無駄なメッセージの転送を削減できる．例えば，各データを取得するためにクエリメッセージを転送する必要がある隣接端末を管理することで，検索を要求された順位に対する隣接端末を特定でき，その端末にのみクエリメッセージを送信すれば，上位 k 個のデータを持つ端末にアクセ

図 2 クエリルーティングの例（2.1 節）

転送を複数経路により行うことで，ネットワークトポロジ変化の影響を小さくする．例えば，図 2(b) では，端末 F も k 位までの宛先にクエリメッセージを送信することにより，複数経路による転送が実現できていることがわかる．拡張手法は，提案手法よりもメッセージの転送率を高くできるため，検索精度を高く維持することが可能である．

2.2

クラスタを用いたルーティング手法

スできる．これを実現するために，経路表を用いた Top-k 検索

本節は，2.1 節と同じ環境を想定し，クラスタを用いたルーのためのルーティング手法を提案する．提案手法では，まず各端ティング手法を紹介する．モバイルアドホックネットワークでは，末が，ネットワーク内で初めて Top-k 検索が行われる際に経路ネットワークトポロジが頻繁に変化する環境や，多くの端末によ表を作成し，経路表で管理された情報に従って Top-k 検索を行り構成される大規模な環境も存在する．そのため，このような環う．Top-k 検索の際には，クエリメッセージに検索要求順位を添境に対応できる Top-k 検索手法が必要である．特に，端末数が付し，このメッセージを受信した端末は，要求された順位のデー多い場合，全ての端末がクエリメッセージを送信してしまうと，タのみを検索する．これにより，クエリメッセージの無駄な転送通信量が大きくなり，帯域が圧迫されるため，パケットロスが生やデータの送信を削減できる．例えば，図 2(a) では，端末 I がじやすい．そのため，検索に必要な端末のみによる検索は効果

Top-2 検索を行う．
（1 位のデータは端末 A が，2 位のデータは端末 M が保持しているものとする．
）端末 I は 1 位のデータ検索のためのクエリメッセージを F に，2 位のデータの検索のためのクエリメッセージを J に送信する．

的である．ここで，端末数が多い場合には，隣接端末の数も多く

しかし，この手法では，各データを検索するためのメッセージ通信量で隣接端末の情報を更新する必要がある．これらの問題をは，それぞれ単一の経路で転送されるため，端末の移動により同時に解決し，小さい通信量で高い精度を維持する Top-k 検索

ネットワークトポロジの変化が起きた場合のメッセージ転送の信を実現する．

なるため，必要なデータを取得するためのクエリメッセージの転送先となる端末を，適切に選択する必要がある．さらに，ネットワークトポロジが頻繁に変化する環境にも対応するため，小さい頼性が低い．そこで，提案手法を拡張し，クエリメッセージを受そこで，クラスタを用いた Top-k 検索のためのルーティング信した端末がそれぞれ k 位までのデータを検索し，メッセージの手法を提案する．この手法では，ネットワーク内で初めて Top-k15 - 2

日本データベース学会

学位論文紹介PhD Thesis Review, No. 15下の式で計算される．

NIJGDFMHf (o) =Ed∑

wi · o.pi

i=1KALB

ユーザは，w =< w1 , ..., wd > を指定でき，各次元に対する重みを表す．また，o.pi は，次元 i における o の（属性）値である．

C: =wGMfQW: UŠMdâƒŽ

提案手法では，スカイライン [1] の概念を利用し，いかなる wにおいても高順位となりやすいデータを持つ端末をクラスタヘッ: =wGMfQW, ÚUŠMdâƒŽè¥þƒŽ

ドとするクラスタリングを行う．これにより，2.2 節の手法と同様に，高順位のデータを持つ端末間での Top-k 検索を実現する．

図 3 クラスタ構築の例（2.2 節）

また，クラスタリングの際に，隣接端末が保持する上位 k 個に含検索が行われる際に 1 ホップクラスタを構築し（図 3），クラスまれる可能性があるデータ（K-スカイバンド [3]）の情報を収集

タヘッド間でクエリメッセージのルーティングを行うことにより，する．ある f (·) が与えられたとき，隣接端末が保持するデータ上位 k 個のデータを取得する．このクラスタリングでは，上位のスコアを計算し，それらが上位 k 個に含まれ得るものか確認のデータを保持する端末をクラスタヘッドとしているため，高順する．このとき，上位 k 個に含まれる可能性がないデータのみを位のデータを持つ端末間のみによる検索を実現できる．さらに，保持している端末である場合，クエリメッセージの無駄な転送を各端末はクラスタヘッドのみとの無線リンクを管理すればよいた

抑制することができ，通信量を削減するとともに，高速な Top-kめ，ネットワークトポロジの変化や隣接端末が多い場合にも対応検索を実現できる．さらに，クエリメッセージに，転送経路中にしやすい．クラスタヘッドは定期的にメッセージを送信すること存在するデータのうち，上位のもののスコアを添付することによにより，各端末は無線接続しているクラスタヘッドを確認できる

り，隣接端末以外の端末が持つデータ集合における上位のデータため，メンテナンスにかかる通信量も小さい．のスコアを把握することができる．これにより，上位 k 個のデー

2.3

タを取得するためにクエリメッセージを送信する必要がない隣接

多次元データに対する Top-k 検索のためのルーティング手法端末をさらに特定でき，クエリメッセージの不要な転送をさらに削減し，無駄なデータの返信を防ぐことが可能である．

ネットワーク内の各端末が，それぞれ異なる検索条件を指定す

2.4

る場合，上位 k 個のデータも条件によって異なる．特に，データ評価結果が複数の属性をもっている多次元データの場合，各属性（次元）ネットワークシミュレータ Qualnet1 を用いて，2.1，2.2，およをどの程度重視するかなどがユーザによって異なるため，様々なび 2.3 節で紹介した提案手法の性能評価を行った．これにより，検索条件が指定される．例えば，救援活動を行っている場合，優提案手法は既存手法よりも性能が高いことを確認した．また，端先度を決定するための事項（出血レベルや意識レベルなど）が末が移動する環境では，2.2 節の提案手法は，2.1 節の拡張手法

状況によって異なる場合や，物理的にアクセスできる範囲を考慮よりも性能が高いことを確認した．

し，検索範囲を制限することが考えられる．救援活動に代表される多くのアプリケーションでは，短い検索時間を要求するため，

3.

おわりにデータの取得に必要な端末のみで迅速に Top-k 検索を行うこと

本研究では，アドホックネットワークにおける Top-k 検索のが望ましい．ここで，上位 k 個のデータの取得に必要となる端ためのルーティング手法を提案した．2.1 節および 2.2 節では，末も検索条件によって異なるため，クエリメッセージを転送する

モバイルアドホックネットワークにおけるルーティング手法を設

隣接端末を，与えられた検索条件によって動的に決定する必要が計し，2.3 節では多次元データに対する Top-k 検索のためのルーある．また，指定される検索条件は事前に知り得ないため，あるティング手法を設計した．

データが取り得る順位を予め把握しておくことは不可能である．
つまり，上位 k 個に含まれるデータも事前に把握できないため，Top-k 検索中に，k 位以内となり得るデータ，および k 位以内になり得ないデータの判断を行う必要がある．この判断を効率よく行い，無駄なデータの送信を削減することが重要である．
本研究では，ネットワークトポロジが変化しないアドホックネットワークを想定し，いかなる検索条件が指定された場合においても，検索に必要がない端末へのクエリメッセージの転送を削減し，正確に Top-k 検索を行うルーティング手法を提案する．本

今後の課題．本研究では，いわゆるスナップショットクエリを想定したが，継続的に Top-k データをモニタリングしたいといった要求も考えられる．定期的にクエリ処理を行うアプローチも考えられるが，このアプローチでは離散的なモニタリングとなり，要求を完全には満たせない．アドホックネットワーク上で，通信量を抑制しつつ，データモニタリングを行うことができる技術の開拓は，今後解決すべき問題である．また，LTE-Direct2 の出現により，より大規模なアドホックネットワークが構築可能となっ研究では，検索条件の一つであるスコアリング関数 f (·) は単調1線系関数であるとし，ある d 次元データ o ∈ Rd のスコアは，以2

http://www.scalable-networks.com/.
https://www.qualcomm.com/invention/technologies/lte/direct

15 - 3

日本データベース学会

学位論文紹介PhD Thesis Review, No. 15

た．この技術により，約 500[m] 先の端末と通信することができ，スマートフォンなどの移動端末だけでなく，各 POI に設置されている端末と無線接続することで，街中でアドホック通信を利用しながらサービスを受ける機会が増加することが予想される．このような環境において発生する問題の提起および解決も今後重要となる．

[文献][1] Börzsönyi, S., Kossmann, D., and Stocker, K.: The skyline operator, Proc. Int. Conf. on Data Engineering,pp.421–430 (2001).
[2] Hagihara, R., Shinohara, M., Hara, T., and Nishio, S.:
A message processing method for top-k query for traﬃcreduction in ad hoc networks, Proc. Int. Conf. on MDM,pp.11–20 (2009).
[3] Papadias, D., Tao, Y., Fu, G., and Seeger, B.: Progressive skyline computation in database systems, ACM
TODS, vol.30, no.1, pp.41-82 (2005).
[4] Sasaki, Y., Hara, T., and Nishio, S.: A top-k query
method by estimating score distribution in mobile ad
hoc networks, Proc. Int. Conf. on Advanced Information Networking and Applications Workshops, pp.944–949 (2010).
[5] Sasaki, Y., Hara, T., and Nishio, S.: Two-phase top-kquery processing in mobile ad hoc networks, Proc. Int.
Conf. on NBiS, pp.42–49 (2011).

天方 大地 Daichi AMAGATA
2015 年大阪大学大学院情報科学研究科博士後期課程修了．博士（情報科学）．現在，大阪大学大学院情報科学研究科助教．モバイ
ルコンピューティング，分散データベース等の研究に従事．情報処理学会，日本データベース学会各会員．

15 - 4

日本データベース学会