DEIM Forum 2016 A8-1

アドホックネットワークにおける凸包領域の継続的な検索手法
駒井 友香†

原隆浩†† 大阪大学大学院情報科学研究科マルチメディア工学専攻 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{komai.yuka,hara}@ist.osaka-u.ac.jp
あらましアドホックネットワークにおける位置依存サービスの一つとして，ネットワークの地理的な凸包領域の算出が可能な凸包検索がある．筆者らはこれまでに，アドホックネットワークにおいて，小さなトラヒックでリアルタイムに凸包の頂点となる端末の情報を取得する手法を提案した．ここで，アドホックネットワークでは端末が移動するため，凸包の形状が時刻により変化する．そのため，ネットワークの凸包領域を継続的に把握（モニタリング）することは有用である．しかし，既存の凸包検索手法は単発の検索を想定したものであり，継続的な検索を効率的に実現することはできない．そこで，アドホックネットワークにおいて，トラヒックを削減しつつ検索精度の維持を目的とする継続的な凸包検索手法を提案する．
キーワード

アドホックネットワーク，継続的な凸包検索，位置依存サービス

1. は じ め に

凸包

救急隊員が存在している領域を知りたい．

近年，無線通信技術の発展と，計算機の小型化や高性能化に伴い，ルータ機能をもつ端末のみで一時的な無線ネットワークを形成するアドホックネットワークへの関心が高まっている [6]．
アドホックネットワークでは，端末が自身の無線通信範囲内に存在する端末と通信する場合，基地局を介さずに直接通信でき返信る．一方，自身の無線通信範囲内に存在しない端末と通信する
場合，これらの端末の間に存在する端末がパケットを中継して，マルチホップ通信を行う．アドホックネットワークは既存の通信基盤を必要とせずに，端末のみで自律分散的にネットワークを構築できるため，災害時の救助活動やイベント会場での情報共有，およびセンサネットワークでの情報収集などへの応用が期待されている．
広い領域において多数の端末がアドホックネットワークを構成している状況では，ネットワークの地理的な形状を把握する等，位置に依存した情報を検索するような位置依存サービスが求められている．そのための有効な方法として，ネットワークの凸包の頂点となる端末の情報を取得する凸包検索がある [1], [3]．
図 1 は，災害地域において，救急隊員がアドホックネットワークを構築し，ある救急隊員が凸包検索を行う例を示している．
凸包検索により，ネットワークの凸包を検出することができる
ため，端末の存在する領域の把握，最遠点対となる端末の発見など様々なアプリケーションへの応用が考えられる．
筆者らの研究グループでは，これまでの研究において，アドホックネットワークにおいてトラヒックを削減しつつ取得精度の維持を目的とした凸包検索手法を提案した [5]．提案手法では，検索クエリの受信により取得した情報より，各端末が自律的に返信する情報を判断することで，ネットワークの凸包の算出に必要な情報のみを取得する．具体的には，Local Wrapping(LW) 法では，領域全体を xy 平面とみなし，まず y 座標が小さい端末へクエリを転送し，その後，ネットワークを囲うように，ネットワークの外周に存在する端末へ順にクエリを伝搬す

図1

凸包検索例

ることで，凸包の頂点となる端末の情報を取得する．これにより，ネットワーク内の全ての端末の位置情報を取得することなく，小さなトラヒックによる凸包検索が可能である．
ここで，アドホックネットワークでは端末が移動するため，刻々とネットワークの凸包の形状が変化する．そのため，単発の凸包検索のみではなく，継続的にネットワークの凸包を把握したいという要求もあると考えられる．継続的にネットワークの凸包を把握するための単純な方法として，単発の凸包検索を定期的に行う方法がある．しかし，端末の移動によって凸包の形状は刻々と変化するため，非常に頻繁に凸包検索を行わなければならず，トラヒックが増大してしまう．特に，凸包の形状にほぼ変化がない場合にも検索が行われ，トラヒックが増大する．そのため，凸包の形状に変化がある場合を検出し，必要な端末のみで凸包の更新を行うことが重要である．
そこで本稿では，アドホックネットワークにおいて，トラヒックの削減，および検索結果の取得精度の維持を目的とする継続的な凸包検索手法を提案する．この研究では，ユーザが定義したマージン内での凸包の変化は許容するものとして，凸包を継続的に把握（モニタリング）する．提案手法では，まず従来手法である LW 法を用いて凸包の頂点端末を検索し，凸包の形状をネットワーク内の全ての端末で共有する．各端末は，凸包M1がマージン以上変化しないことを保証できる領域として，Safezone を算出し，この範囲内から移動する場合に，凸包の再検索

クエリ
発行端末

M8を行う．凸包の再検索時には，新たな凸包の頂点端末を部分的に検索して共有することで，効率的なモニタリングを行う．
以下では，2. で関連研究について述べる．その後，3. で従来手法について述べ，4. で提案手法について述べる．最後に，5.
で本稿のまとめについて述べる．

M3M2M5M7 M4 M3
M1M8M6M7M4検索クエリ

2. 関 連 研 究
筆者らの知る限り，アドホックネットワークにおける継続的図 2 LW 法による凸包検索

な凸包検索に関しての研究は，これまでに行われていない．そこで本章では，センサネットワークにおける境界モニタリング計算量を小さくすることができている．文献 [2] では，ユーザに関する従来研究，および位置に依存する検索クエリのモニタが指定した円領域の情報を取得するレンジクエリのモニタリンリングに関する従来研究について紹介する．さらに，本研究とグ手法について提案している．この手法では，各オブジェクト従来研究を比較し，その相違点について述べる．の位置を中心とした円の重なりを基に Safe zone を算出する．

2. 1 センサネットワークにおける境界モニタリング

検索する円領域が移動し，その円の中心点が Safe zone の外に

文献 [4] では，ガスの拡散領域など対象の領域を，配置したセ出た場合，検索結果を更新し，少ない計算量で再度 Safe zone

ンサ端末から情報を収集することによって検出し，モニタリンを算出するためのアルゴリズムについても提案されている．文グする方法を提案している．この手法では，領域の境界に存在

献 [7] では，検索の条件として位置とキーワードが指定されるする端末を地理的にいくつかのクラスタに分け，各クラスタのSpatial Keyword クエリのモニタリングにおいて Safe zone を代表の端末がクラスタ内の端末の情報を集約してシンクに送信用いる手法を提案している．それぞれの文献では，対象とするすることで効率的に領域を把握する．対象の領域が変形，移動，検索クエリに対応した Safe zone を提唱し，効果的なモニタリ合併，分割する場合は，代表の端末が新たなクラスタとその代ングを実現している．本研究では，凸包領域のモニタリングの表端末を選択し，領域のモニタリングを行う．文献 [9] では，セ際に有効な Safe zone を提案しており，新しい試みである．まンサネットワークにおいて観測値の地理的な境界線をローカルた，検索対象となるオブジェクトを固定としている従来研究とにモニタリングする方法を提案している．この手法では，各端は違い，本研究では検索対象（端末）が移動するという点でも末が周辺の隣接端末の観測値を基に境界端末となるか判断し，これらの研究とは異なる．

その境界が無効になると周辺端末とメッセージを交換して部分的に境界線の修復を行う．これにより，継続的に境界線を把握

3. 従来手法：LW 法することができる．これらの手法により，分散環境において効LW 法は，ネットワークの外周端末を順に巡回してクエリを果的に境界のモニタリングを行うことができる．しかし，各文伝搬することにより，全ての端末にクエリを送信することなく献において定義している境界のモニタリングを行うものであり，小さなトラヒックにより検索を行うため，単発の凸包検索におそれぞれの定義に特化したアプローチを採用している．一方，いて有用な手法である．LW 法では，まず，位置情報を用いた

本研究では，凸包領域のモニタリングを目的とし，凸包領域がルーティング（ジオルーティング）により y 座標が小さい端末変化するタイミングの検出および凸包領域の部分的な更新を効へクエリを送信し，この端末からネットワークの外周端末へ順果的に行う方法を提案しており，これらの研究とは異なる．にクエリを伝搬する．図 2 は，端末 M5 がクエリを発行した場

2. 2 位置に依存する検索クエリのモニタリング

合の LW 法による凸包検索を行う例を示している．図に示すよ

位置に依存する検索クエリのモニタリングは，位置情報を持うに，y 座標が小さい端末 M7 へクエリを転送した後，反時計つオブジェクト（検索対象）に対して，ユーザが検索の中心点やまわりに外周端末へクエリを伝搬する．外周端末へ効率的にク領域を移動させながら，それに伴って変化する検索結果を継続

エリを伝搬するために，LW 法では，転送元の端末とのなす角的に把握するものであり，ムービングクエリとも呼ばれる．こが小さいほど返信の待ち時間を小さく設定し，なす角が小さい，のようなモニタリングの際には，検索の中心点や領域が移動しつまり，より外側に存在する端末を次にクエリを転送する端末ても結果に影響を与えないことが保証できる領域（Safe zone）として選択する．

を算出することが有効であり，Safe zone を用いた効果的なモLW 法における周辺端末への検索クエリ伝搬のアルゴリズム

ニタリング手法が多く提案されている．文献 [8] では，ユーザを Algorithm 1 に示す．検索クエリを受信した y 座標が小さいが指定した位置から近い k 個のオブジェクトを算出する k 最近

端末はネットワークの淵に存在する端末へのクエリ転送を開始傍検索のモニタリング手法について提案している．この手法でする．まず，検索クエリを受信した端末は自身の位置情報を凸は，オブジェクトのボロノイ図を Safe zone として利用し，検包のデータとして加え，凸包の頂点端末を算出する．その後，索結果が変化しない場合にクエリ処理を行わなくてよいため，次にクエリを転送する端末を選択するため，凸包データの最後

Algorithm 1 LW 法における検索クエリ伝搬∠Mq Mt Mp1

1: if 検索クエリを受信 then2:

自身の位置情報を凸包データに追加

3:

凸包データに含まれる頂点端末以外のデータを削除

4:

隣接端末に次端末検索メッセージを送信

Mp2
次端末
検索
Mq

5: end if

検索クエリ

6: if 次端末検索メッセージを受信 then
7:

返信待ち時間 T を頂点端末とのなす角を基に設定

Mp1

Mt

∠Mq Mt Mp1∠Mq Mt Mp2

8: end if

Mp2

9: if T 経過 then
10:

次端末検索

隣接端末に次端末返信メッセージを送信

11: end if

Mq

12: if 次端末返信メッセージを受信 then
13:

Mp1

Mt

検索クエリ

∠Mq Mt Mp2

if 次端末検索メッセージの送信元端末 then
次端末返信メッセージの送信元端末へ検索クエリ（凸包デー

14:

図 3 LW 法におけるなす角タを添付）を送信
15:

else
次端末返信メッセージの送信を中止

16:
17:

ネットワークの凸包マージンエリア：

end if

18: end if

凸包B

dd’
尾から 2 つの端末の識別子と位置情報を含む次端末検索メッ

凸包A

セージを隣接端末に送信する．次端末検索メッセージを受信した端末は，返信待ち時間 T を設定する．T の値は，受信した凸包データ内の 2 つの端末と受信端末とのなす角が小さい端末ほど小さくなる．例えば，図 3 は，Mt が送信した Mq および Mtの情報が含まれた次端末検索メッセージを受信した端末 Mp1および Mp2 のそれぞれのなす角である．この場合，Mp1 の方が小さい T を設定し，Mp2 よりも早く返信を行う．T 経過後，最もなす角の小さい端末が次端末返信メッセージを送信し，この端末へ検索クエリの転送を行う．検索クエリを受信した端末は，クエリ伝搬を開始した端末まで，同様にクエリの転送を続ける．

LW 法は単発の凸包検索を想定したものであり，継続的な検索を効率的に実現するためには新たな手法が必要である．

4. 凸包領域の継続的な検索手法
本章では，本稿で提案する継続的な凸包検索手法を説明する．
以下では，まず想定環境について述べ，次に，提案手法のアイデアについて述べる．その後，提案手法の詳細な手順について説明する．

4. 1 想 定 環 境
本稿では，アドホックネットワークを構成する各端末が，ネットワークの地理的な凸包を継続的に検索する環境を想定する．
凸包検索を行う端末は，検索クエリを発行し，ネットワーク内の端末の中から，凸包の頂点となる端末の情報を継続的に取得する．ここで，頂点端末の移動に沿って変化する凸包の形状変化を逐次正確に把握することは現実的および実用的ではないと考えられるため，本研究では，ユーザは凸包の変化を許容するマージンエリアを指定し，この範囲内に凸包の外周が収まる場

図4マージンエリア

合，通知の必要はないと定義する．マージンエリアは，図 4 で表されるとおり，検出した凸包の各辺からユーザが指定した距
離 d だけ拡大した凸包 A および距離 d′ だけ縮小した凸包 B に囲まれる範囲（凸包 A ∩ 凸包 B ）と定義する．
ネットワーク内には，同等の性能（通信伝搬距離 rm 程度）を持つ n 個の端末（識別子：M1 ,M2 , · · · ,Mn ）が存在し，各々が自由に移動する．ネットワークに参加する端末は既知であり，ネットワークを構築する前に各端末に一意の識別子が付与されているものとする．各端末は，GPS などにより自身の位置情報 (x, y) を把握しているものとする．なお，経度を x 座標，緯度を y 座標に対応するものとする．

4. 2 手法のアイデア
4. 1 節で定義した継続的な凸包検索を効率的に実現する場合，凸包の外周がマージンエリア内に収まらなくなるときを検出することが重要である．凸包がマージンエリアに収まらなくなる状況は大きく分けて２つある．まず，ある端末が凸包 A のある辺を超える場合である．このとき，凸包 A の辺を超えた端末は新たに検出する凸包の頂点端末になるため，凸包 A 外に移動する場合は，必ず通知する必要がある．
一方，マージンエリアに収まらなくなるもう 1 つの状況は，凸包の辺が縮小した凸包 B の辺と交わる場合である．ここで，Safe zone

クエリ発行
y座標が小さい端末へクエリ転送

凸包B

凸包A

凸包の頂点端末を検索
凸包の頂点端末の情報を全端末に共有
No
凸包A内？

NoYes

Safe zone内→外？

図 5 Safe zone

Yes
凸包の頂点端末を一部検索

凸包領域のモニタリングにおける Safe zone について考える．

Safe zone は，2. 2 節で述べたとおり，この範囲内であれば結果各辺および縮小した凸包 B の各辺を延ばした直線に囲まれる領域となる．例えば，図 5 のネットワークの場合，濃く塗りつぶされた領域が Safe zone となり，凸包の各頂点を含む複数の領域で成り立つことがわかる．凸包領域のモニタリングにおいては，各 Safe zone に少なくとも 1 台以上端末が存在する場合，凸包の外周はマージンエリア内に収まることが保証できる．そのため，各 Safe zone 内で端末が 1 台も存在しなくなる（空となる）タイミングを検出すれば，凸包が縮小する可能性のあるタイミングを知ることができる．
以上の 2 つの状況を検出した場合にのみ凸包を更新することで，定期的な凸包検索をすることなく，効果的に凸包領域をモニタリングすることができると考えられる．ただし，更新の際に，外周端末を全て（一周）探索すると，マージンエリア内に収まっている部分についても再度検索を行うこととなる．マージンエリアに収まらなくなった部分のみを再検索することができれば，より小さなトラヒックによるモニタリングができるはずである．ここで，凸包のある辺の両端の 2 つの Safe zone 内に端末が存在していると凸包のその辺はマージンエリア内に収まることが保証できる．そのため，外周端末を探索している途中で訪れたある Safe zone 内に端末が存在することを検知した
時点で検索を止めても凸包の更新が十分可能である．

4. 3 提 案 手 法
提案手法のフローチャートを図 6 に示す．提案手法ではまず，LW 法によりネットワークの凸包を検索する．クエリを発行した端末は，マージン d および d′ を指定したクエリをジオルー
ティングにより y 座標が小さい端末へ送信し，この端末からネットワークの外周端末へ順に Algorithm 1 に従いクエリを伝搬する．外周を周り終わり，クエリ発行時のネットワークの凸包を算出した端末は，凸包の頂点端末の情報を全端末に共有する．具体的には，算出した凸包の頂点の位置情報，d，およびd′ を含むメッセージを，初めて受信した端末が隣接端末に送信する動作を繰り返すことで，このメッセージをネットワーク全体へフラッディングする．これにより，各端末は凸包のマージ

Safe zone内が空？

No

図 6 提案手法のフローチャートが変わらない保証のある（結果を更新しなくてよい）領域のことであり，凸包のモニタリングにおいては，拡大した凸包 A のYesンエリアおよび Safe zone を算出することができ，自身が Safezone 内に存在するかを確認する．その後，4. 2 節で述べた通り，各端末は凸包 A 内にいるか，さらに，Safe zone 内から移動していないかを適宜確認することで，凸包の形状の変化に対応する．

•凸包 A 外に移動した場合ある端末が凸包 A のある辺を超えて凸包 A の外に移動した場合，凸包の外周はマージンエリアに収まらず，凸包の形状変化を通知しなければならない．そのため，新しい頂点端末として自身の情報を送信し，凸包を更新する．

•Safe zone 外に移動した場合

Safe zone 内の端末は，凸包 A 内には存在するが Safe zone外に移動した場合，まずその Safe zone 内に他の端末が存在するかどうかを確認する．そのため，Safe zone 内へ確認メッセー
ジを送信し，Safe zone 内に存在する端末は送信元端末へ返信を行う．返信を受信した確認メッセージの送信元端末は，凸包の再検索は行わず，引き続き凸包の形状変化を検出する動作を行う．一方，返信を受信しない場合，Safe zone が空になったと判断し，ネットワークの凸包の辺が凸包 B の辺と交わる可能性があるため，凸包の再検索を行う．
凸包を再検索する場合には，再検索を開始する端末から近接する Safe zone までの部分的な検索を行う．再検索を開始する
端末は，Algorithm 1 に従い，検索クエリを両方向（外周を時計回りおよび反時計まわり）に伝搬する．この際，返信待ち時
間 T は以下の式により設定する．

T =αθ.
2π

ここで，α はシステム管理者が設定するパラメータ，θ は ̸(1)Mq

Mt Mp のなす角，つまり半直線 Mt Mq を始線として時計まわりもしくは反時計まわりに Mp までの角度（端末 Mt が送信した Mq および Mt の情報が含まれた次端末検索メッセージを受信した端末 Mp の場合）である．なお，Mt が開始端末の場合には，Mt を原点としたエリアマージンの垂線を始線とする．
また，Mq =Mp の場合，θ=2π とする．この式を用いることでM1

Safe zone
ネットワークの凸包検索

図 7 凸包の更新例

T の値は，なす角が小さい端末ほど小さくなる．近接する Safezone 内の端末までメッセージを転送後，検索した新たな凸包の頂点端末の位置情報を含むメッセージを，ネットワーク内の全ての端末へ送信して，凸包の情報を更新する．
図 7 を用いて，端末 M1 が Safe zone 内から移動し，そのSafe zone が空となった場合の動作について説明する．端末 M1は，検索クエリを外周に沿って両方向に送信する．それぞれの検索クエリは，Safe zone 内の端末まで転送された時点で検索を止め，これらの端末は M1 から Safe zone までの凸包の新しい辺を算出する．新たに算出した凸包の辺の情報をネットワー
ク内の端末に送信し，各端末は，新しい凸包のマージンエリアおよび Safe zone を算出してモニタリング動作に戻る．

5. 結論

本稿では，アドホックネットワークにおいて，トラヒックの削減，および検索結果の取得精度の維持を目的とする継続的な凸包検索手法を提案した．提案手法では，Safe zone を算出し，この範囲内から移動する場合に，凸包の再検索を行う．凸包の再検索時には，新たな凸包の頂点端末を部分的に検索して共有することで，効率的なモニタリングを行う．今後，提案手法の性能評価を行い，手法の有用性を示す予定である．

謝辞

本研究の一部は，文部科学省科学研究費補助金・特別研究員奨励費 (A15J024960) の研究助成によるものである．ここに記して謝意を表す．

文

献[1] Barber, C. B., Dobkin, D. P., and Huhdanpaa, H.: Thequickhull algorithm for convex hulls, ACM Trans. on Mathematical Software (TOMS), Vol. 22, No. 4, pp. 469–483(1996).
[2] Cheema, M. A., Brankovic, L., Lin, X., Zhang, W., andWang, W.: Multi-guarded safe zone: An eﬀective technique to monitor moving circular range queries, in Proc. ofInt’l Conf. on Data Engineering (ICDE 2010), pp. 189–200(2010).
[3] Graham, R. L.: An eﬃcient algorithm for determining theconvex hull of a ﬁnite planar set, Information Processing
Letters, Vol. 1, No. 4, pp. 132–133 (1972).

[4] Ji, X., Zha, H., Metzner, J. J., and Kesidis, G.: Dynamiccluster structure for object detection and tracking in wireless ad-hoc sensor networks, in Proc. of Int’l Conf. on Communications (ICC 2004), Vol. 7, pp. 3807–3811 (2004).
[5] Komai, Y., Hara, T., and Nishio, S.: Processing Convex
Hull Queries in MANETs, in Proc. of Int’l Conf. on Mobile
Data Management (MDM 2015), pp. 64–73 (2015).
[6] Perkins, C. E.: Ad hoc networking, Addison-Wesley Professional (2008).
[7] Wu, D., Yiu, M. L., Jensen, C. S., and Cong, G.: Eﬃcient
continuously moving top-k spatial keyword query processing, in Proc. of Int’l Conf. on Data Engineering (ICDE2011), pp. 541–552 (2011).
[8] Zhang, J., Zhu, M., Papadias, D., Tao, Y., and Lee, D. L.:
Location-based spatial queries, in Proc. of ACM SIGMOD
Int’l Conf. on Management of Data (SIGMOD 2003), pp.
443–454 (2003).
[9] Zhu, X., Sarkar, R., Gao, J., and Mitchell, J. S.: Lightweight contour tracking in wireless sensor networks, in Proc.
of Int’l Conf. on Computer Communications (INFOCOM2008) (2008).