DEIM Forum 2016 H2-1

アドホックネットワークにおける 2 フェーズ MaxRS 検索手法
中山侑紀†

天方 大地†

原隆浩†

西尾章治郎††† 大阪大学大学院情報科学研究科マルチメディア工学専攻 〒 565–0871 大阪府吹田市山田丘 1–5†† 大阪大学 〒 565–0871 大阪府吹田市山田丘 1–1
E-mail: †{nakayama.yuki,amagata.daichi,hara,nishio}@ist.osaka-u.ac.jp
あらまし 本稿では，アドホックネットワークにおける MaxRS（Maximizing Range Sum）検索について考える．ア
ドホックネットワークを構成する各端末が，スコアをもつ位置データをそれぞれ所持していると想定する．MaxRS 検
索は，クエリ発行端末がある大きさの長方形を指定し，その長方形に包含される位置データのスコアの和が最大となる長方形の位置を取得するものである．例えば，災害地での救護活動において，救急隊員が MaxRS 検索を行い，負傷者が密集している場所を特定するといった応用例が考えられる．正確な解を検索する単純な手法は，クエリ発行端末
がネットワーク内の全てのデータを収集するものである．しかし，アドホックネットワークは通信帯域に制限があり，全てのデータを収集する方法は効率的でない．そこで本稿では，アドホックネットワークにおける効率的な MaxRS
検索手法を提案する．提案手法は、1 フェーズ目に，MaxRS 検索の結果を取得するために必要なデータが存在する領域を特定する. さらに，2 フェーズ目に，特定した領域に存在するデータのみを収集することにより，不必要なデータの送信を抑制する．シミュレーション実験の結果から，提案手法は MaxRS 検索処理に必要なデータを効率的に取得できることを確認した．
キーワード

アドホックネットワーク，MaxRS 検索，位置データ

1. は じ め に
近年，IEEE802.11 や Bluetooth，Wi-Fi Direct などの無線通信技術の発展や，スマートフォンおよびタブレット端末などの計算機の小型化や高性能化に伴い，無線通信端末のみで一時的に構成されるアドホックネットワークへの関心が高まっている [8]．アドホックネットワークは既存の通信インフラが必要でないため，災害地などのインターネットが利用できない環境へܾܽ

図 1 MaxRS 検索の一例の応用が期待されている [1]．
通信インフラを利用できない災害地において，アドホック

太線の長方形はネットワーク領域，ネットワーク領域内の破線

ネットワークを用いて，救急隊員が救護活動を行うことを考えおよび実線の長方形はクエリ発行端末が指定した大きさの長方

る．救急隊員は，それぞれ無線通信端末を保持し，それらの端形，黒点はスコアをもつ位置データを表している．簡単化のた末によりアドホックネットワークが構成されている．また，救め，位置データのスコアは全て 1 とする．この例では，最も多急隊員は救護活動中に取得した負傷者情報を自身の端末に保くの黒点を包含している実線の長方形が MaxRS 検索の解の 1

持する．このような状況において救護活動を効率的に行うたつである．

めに，ある救急隊員が，最も救護が必要とされている場所を検索することが考えられる．このような要求を満たすものとして，MaxRS(Maximizing Range Sum) 検索が存在する [5]．

MaxRS 検索は，クエリ発行端末がある大きさの長方形を指定し，その長方形に包含される位置データのスコアの和が最大となる長方形の位置を取得するものである．上記に示した例を考えると，データの位置を負傷者の位置，データのスコアを負傷
者の負傷度として MaxRS 検索を実行することにより，負傷者の負傷度の和が最大となる位置，つまり，最も救護が必要と考えられる場所を検索できる．以下の例を用いて，MaxRS 検索を説明する．

MaxRS 検索は，例 1.2 のようなアプリケーションに適応することも考えられる．
例 1.2．アドホックネットワークの一種であるモバイルセンサ
ネットワークを考える．ネットワークを構成するセンサ端末が一秒毎に位置情報を記録して，その情報を保持しているものとする．例えば，それぞれの端末内で保持したある一定時間の位
置情報データをデータ集合として MaxRS 検索を実行すると，ある一定時間中にセンサ端末が最も集中して存在していた場所を特定できる．モバイルセンサネットワークは，様々な位置のセンサ値を取得したいといった要求があり，上記の MaxRS 検索を実行することにより，センサ端末が密集している場所を把例 1.1．図 1 は MaxRS 検索の一例を表している．最も外側の握し，センサ端末の位置を分散させることができる．

上記のように実用的なアプリケーションが存在するにも関わらず，アドホックネットワークにおける MaxRS 検索はこれまでに研究されていない．そこで本稿では，アドホックネット
ワークにおける効率的な MaxRS 検索手法を提案する．提案手法は 2 フェーズによる MaxRS 検索を行う．1 フェーズ目では，ܾܽMaxRS 検索の解となり得る領域を限定する．さらに，2 フェー
ズ目で，1 フェーズ目で特定した領域に存在するデータを取得
し，クエリ発行端末が正確な MaxRS 検索の解を計算する．このように，不要なデータの送信を抑制することにより，効率的に MaxRS 検索を実行できる．シミュレーション実験により，提案手法は取得精度を高く維持しつつ，トラヒックを削減できることを確認した．
以下では，2. で本稿での問題定義および単純手法について説明し，3. で提案手法について述べる．4. でシミュレーション実験により，提案手法の性能を評価する．5. で関連研究について述べ，最後に，6. で本稿をまとめる．

2. 事 前 準 備
本章では，まず，想定環境および MaxRS クエリを定義する．
その後，アドホックネットワークにおける MaxRS クエリ処理の単純な手法について述べる．

2. 1 問 題 定 義
想定環境. n 台の端末（識別子：M1 , M2 , . . . , Mn ）でアドホッ
クネットワークが構成され，各々が自由に移動する．各端末は，端末が移動する最大範囲であるネットワーク領域を把握しているものとする．また，各端末 Mi が保持しているデータ集合を

Oi と表す．あるデータ o ∈ Oi は，二次元の位置情報（o.x, o.y ）ܾ(a) MaxRS 問題（∀o ∈ O につܽ(b) RI 問題

いて，o.score = 1）

図 2 MaxRS 問題の変換例とが示されている．図 2 を用いて，これを説明する．
図 2(a) において，黒点はデータの位置，白点は横および縦の長さがそれぞれ a および b の長方形が指定された場合の MaxRS
問題の解の 1 つ，長方形は白点を中心とする横および縦の長さがそれぞれ a および b の長方形を表している．このとき，データの位置を中心とする横および縦の長さがそれぞれ a および b の長方形の集合が与えられたときの RI 問題を考える（図 2(b)）．
この RI 問題の解は，図 2(b) における灰色の領域である．図 2に示す通り，MaxRS 問題の解の 1 つである白点は，RI 問題の解である灰色の領域中に存在する．このように，全てのデータのスコアが 1 である場合の MaxRS 問題を RI 問題に変換し，RI 問題を解くことにより，元の問題の解が得られる．さらに，
RI 問題は，文献 [7] において，平面走査法をもとにしたアルゴリズムが提案されており，O(n log n) の計算量で解くことができる（n は RI 問題で与えられる長方形の数）．ここまで，全てのデータのスコアが 1 である場合を考えていたが，本稿では，
データのスコアを 1 と限定しない．よって，RI 問題を拡張するために，以下の定義を導入する．

およびスコア（o.score）を保持している．また，スコアは何ら

定義 3（領域のスコア）. ネットワーク中の全てのデータの集

かのスコアリング関数により計算される 0 より大きい値とする．

合 O および大きさが指定された長方形が与えられたとき，それネットワーク中の全データ集合 O（= ∪Oi ）において，複製はらのデータの位置を中心とする指定された大きさをもつ長方形

存在しないものとする．

の集合 R が得られる．また，o.score を対応する長方形のスコ

定義 1（MaxRS 問題）．ネットワーク領域内の無限地点集合

P ，およびネットワーク中の全てのデータの集合 O が与えられる．また，大きさが指定された長方形の中心を p ∈ P とする．
∑
このとき， o∈O
o.score が最大となる長方形の中心 p をアとする．このとき，ある領域 s のスコアは，s に重なっている長方形のスコアの和である．
長方形のスコアを考慮し，文献 [7] で提案されているアルゴ
リズムを利用することにより，スコアが最も大きい領域を求R(p)MaxRS 問題の解とする．ただし，R(p) は地点 p を中心とするめることができる．つまり，0 より大きい値のスコアをもつ指定された大きさをもつ長方形，OR(p) は長方形 R(p) 内に存

n 個の位置データのデータ集合が与えられた MaxRS 問題は，

在するデータ集合である．

O(n log n) の計算量で解ける [5]，[6]．以下に，本稿で考えるク

ここで，地点集合 P の要素数が無限であるため，MaxRS 問

エリを定義する．

題を正確に解くためには，無限回のスコアの和の計算が必要と定義 4（MaxRS クエリ）. ネットワーク中の全てのデータ

なり，非現実的である．そこで，MaxRS 問題を次のように変の集合 O および大きさが指定された長方形が与えられたとき，換する．

ネットワーク領域中でスコアが最も大きい領域を求める．

定義 2（Rectangle intersection 問題（RI 問題））．二次元

本稿では，クエリ発行端末が，長方形の横の長さ a，縦の長平面上に存在している長方形の集合 R が与えられる．このとき，

さ b を指定し，上記の MaxRS クエリの解を取得する問題につ最も多くの長方形が交差している領域を RI 問題の解とする．

いて考える．また，指定した長方形の回転 [3] は考えない．

文献 [9] において，全てのデータのスコアが 1 である場合の

MaxRS 問題と MaxRS 問題におけるデータの位置を長方形の中心とした長方形の集合を入力とする RI 問題が等価であるこ

2. 2 単 純 手 法
MaxRS クエリの解を正確に取得する単純な手法として，クエリ発行端末が，ネットワーク内の全てのデータを収集し，収集したデータをもとに MaxRS 問題を解くことが考えられる．
以下に，その詳細を記す．
まず，クエリ発行端末がネットワーク内の全ての端末にデー
タ要求メッセージをフラッディングする．このメッセージには，
送信元端末 ID，親端末 ID，およびホップ数 (初期値は 0) が添付されている．データ要求メッセージを初めて受信した端末は，メッセージ中の送信元端末を自身の親端末とし，ホップ数を 1増やしたデータ要求メッセージをブロードキャストする．さらに，この端末は親端末を送信先とする ACK メッセージを送信する．また，この端末はデータ返信を行うまでの時間（データ
返信待ち時間 W T ）を以下のように設定する．

W T = Delaymax ·HOPmax − HOPcount
HOPmax‫ܥ‬Ǥ ݈݁݊݃‫݄ݐ‬‫ܥ‬Ǥ ‫݄ݐ݀݅ݓ‬

ܿସ଴

ܿସଵ

ܿସଶ

ܿସଷ

ܿସସ

ܿଶ଴

ܿଶଵ

ܿଶଶ

ܿଶଷ

ܿଶସ

ܿଷ଴
ܿଵ଴

ܿ଴଴

ܿଷଵ
ܿଵଵ

ܿ଴ଵ

ܿଷଶ
ܿଵଶ

ܿ଴ଶ

ܿଷଷ
ܿଵଷ

ܿ଴ଷ

図 3 ネットワーク領域の分割

ܿଷସ
ܿଵସ

ܿ଴ସ

た端末は，クエリに添付されているセルの各辺の長さを用いて，クエリ発行端末と同様にネットワーク領域をグリッド状に分割する．ネットワーク領域をグリッド上に分割した例を図 3 に示

ここで，Delaymax は最大待ち時間，HOPmax はネットワーク

す．この例では，ネットワーク領域を 5 × 5 の合計 25 個のセル中の最大ホップ数，HOPcount はクエリ発行端末までのホップ（セル c00 〜セル c44 ）に分割している．その後，セルの数分の数である．また，ある端末がデータ要求メッセージを受信した

スコアを格納できるサイズの配列を返信メッセージに添付し，時にメッセージ中の親端末 ID が自身の端末 ID であった場合，

葉端末から順にセルのスコアの和を親端末に送信する．全てのまたは自身を送信先とする ACK メッセージを受信した場合，端末でネットワーク領域の分割方法を共有しているため，セル

そのメッセージ中の送信元端末を自身の子端末とする．その後，と配列の格納位置の対応関係は全ての端末で共通である．

親端末 ID が自身の端末 ID であるメッセージを受信しなかった

以下に，1 フェーズ目における処理について説明する．まず，端末は，自身を葉端末とみなし，自身の保持する全てのデータ

葉端末は自身のもつデータの位置に対応するセルにそのデーを親端末へ返信する．データを受信した端末は，送信元端末をタのスコアを加算する．対応するデータが存在しないセルのス

送信先とする ACK メッセージを送信する．自身を送信先とす

コアは 0 とする．このように作成した配列を返信メッセージ

る ACK メッセージを受信した端末は，データを親端末に送信に添付し，親端末に送信する．返信メッセージを受信した端末できたとみなし，これ以降なにもしない．一方，一定時間待っは，単純手法と同様に ACK メッセージを子端末へ送信する．

た後，自身を送信先とする ACK メッセージを受信していない

この ACK メッセージについては，単純手法のデータ返信時と端末は，データを親端末に送信できていないとみなし，データ同様の処理を行う．さらに，この端末は，葉端末と同様に，返を親端末へ再送信する．自身の全ての子端末からデータを受信

信メッセージ中のセル毎のスコアを格納した配列中の，自身のした端末，およびデータ返信待ち時間が経過した端末は，自身もつデータの位置に対応するセルに，そのデータのスコアを加の保持する全てのデータおよび子端末から受信した全てのデー

算し，親端末へ返信メッセージを送信する．複数の子端末からタを親端末へ返信する．これにより，クエリ発行端末はネット

返信メッセージを受信した場合，全ての返信メッセージ中のセワーク内の全てのデータを収集できる．その後，クエリ発行端

ル毎のスコアの和をとったものに，自身のもつデータのスコア

末は，文献 [7] で提案されているアルゴリズムを用いて，収集を加算する．これを，例を用いて説明する．

したデータおよび指定した長方形（a, b）から MaxRS クエリの解を求める．
このように，単純手法は，クエリ発行端末がネットワーク内のデータを全て収集する．したがって，ネットワーク内のデー
タ数が多い場合，トラヒックが大きくなり，パケット損失や通信遅延が起きる可能性が高くなるため，効率的ではない．

例 3.1．図 4 は 1 フェーズ目の返信の例を示している．ネット
ワーク領域の分割は図 3 に従い，返信メッセージには 25 個のスコアを格納できるサイズの配列を用いる．図 4 における左の表
は，データとそれを所持する端末の対応関係，吹出しの長方形
は返信メッセージ中の配列の中身の一部を表している．簡単化のため，データの位置をセル ID で表記しているが，実際は，緯3. 提 案 手 法
提案手法は，2 フェーズで MaxRS 検索を実行する．初めに，1 フェーズ目において，クエリ発行端末は，MaxRS ク
エリの解となり得る領域を求める．そのために，ネットワー
ク領域をグリッド状に分割し，分割したセルの各辺の長さ（C.width, C.length）をクエリに添付する．セルの各辺の長さはそれぞれ C.width = ka ，C.length = bl (k, l は自然数) とする．その後，クエリをネットワーク全体にフラッディングする．
このとき，単純手法と同様の方法で，クエリ発行端末を根とする木構造のネットワークトポロジを構築する．クエリを受信し度および経度の二次元の数値で表される．葉端末 M1 は，デー
タ D1 ，D2 および D3 の 3 つのデータを所持しており，それぞれの位置はセル c00 ，c00 および c01 に対応する．したがって，
返信メッセージ中の配列を c00 = 10 + 10 = 20，c01 = 20 とし（他のセルの値は 0），親端末 M2 に送信する．また，もう一台の葉端末 M3 も M1 と同様の方法により，返信メッセージを親
端末 M4 に送信する．M1 からのメッセージを受信した M2 は，自身がもつデータのスコアを返信メッセージ中の配列の対応する箇所に加算する．つまり，c00 = 20，c01 = 10 + 10 = 20，

c11 = 10 とする．M2 は，このようにして更新したメッセージ

ഈଜ
‫ܯ‬ଵ
‫ܯ‬ଶ
‫ܯ‬ଷ

‫ܯ‬ସ

ID

‫ܦ‬ଵ
‫ܦ‬ଶ
‫ܦ‬ଷ
‫ܦ‬ସ
‫ܦ‬ହ
‫଺ܦ‬
‫଻ܦ‬
‫଼ܦ‬
‫ܦ‬ଽ
‫ܦ‬ଵ଴
‫ܦ‬ଵଵ
‫ܦ‬ଵଶ
‫ܦ‬ଵଷ

崡崛崊 ਜ਼઼
10
ܿ଴଴
10
ܿ଴଴
10

10
10
10
30
30
10
50
20
30
70

ܿ଴ଵ

ܿ଴ଵ
ܿଵଵ
ܿ଴ଵ
ܿଵଵ
ܿଵଵ
ܿଵଶ
ܿଵଷ
ܿଶ଴
ܿଶ଴
ܿଶଵ

‫ܯ‬ଵ
‫ܯ‬ଶ

‫ܯ‬ସ

ܿ଴଴ ܿ଴ଵ
20 10ନਦ嵉崫崣嵤崠

… ܿସସ
… 0

ܿଷ଴

ܿ଴଴ ܿ଴ଵ … ܿଵଵ … ܿସସ
20 20 … 10 … 0ܿ଴଴ ܿ଴ଵ
0 10

ܿ଴଴ ܿ଴ଵ
20 30… ܿଵଵ ܿଵଶ… 60 10… ܿଵଵ ܿଵଶ ܿଵଷ… 70 10 50

ܿସ଴

… ܿସସ
… 0

… ܿଶ଴ ܿଶଵ… 50 70

‫ܯ‬ଷ

… ܿସସ
0

…

ܿଶ଴
ܿଵ଴

ܿ଴଴









ܿସଵ
ܿଷଵ
ܿଶଵ
ܿଵଵ

ܿ଴ଵ










ܿସଶ
ܿଷଶ
ܿଶଶ
ܿଵଶ

ܿ଴ଶ









ܿସଷ
ܿଷଷ
ܿଶଷ
ܿଵଷ

ܿ଴ଷ









ܿସସ
ܿଷସ
ܿଶସ
ܿଵସ






ଶଶ
ൌ
‫ܥ ݁ݎ݋ܿݏ‬଴ଷ



ܿ଴ସ



図 4 1 フェーズ目の返信例

図 5 セル毎のスコアの和の例

を親端末 M4 に送信する．M4 は，二台の子端末 M2 および M3

22) は 80 である．これは，lbscoreび c14 のスコアの和 score(C03からメッセージを受信したとき，返信メッセージ中の配列の対応未満であるため，この時点ではセル c03 ，c04 ，c13 ，および c14

する箇所の和をとり，さらに自身のもつデータのスコアを対応

はデータ要求セル集合の要素とはならない．全てのセルに対する箇所に加算する．すなわち，c00 = 20，c01 = 20 + 10 = 30，

して計算を行ったとき，lbscore 以上のスコアとなるセル集合

c11 = 60 + 10 = 70，c12 = 10，c13 = 50，c20 = 20 + 30 = 50，

は，{c00 , c01 , c10 , c11 }，{c01 , c02 , c11 , c12 }，{c10 , c11 , c20 , c21 }，c21 = 70 とする．その後，M4 も同様に，更新したメッセージおよび {c11 , c12 , c21 , c22 } であり，それぞれのセル集合に対応すを親端末に送信する．

るスコアの和は 750，470，760，490 である．したがって，デー

これにより，1 フェーズ目において，クエリ発行端末はネッ
トワーク領域全体のセル毎のスコアの和を得る．次に，クエ
リ発行端末はセル毎のスコアの和から，正確な MaxRS クエリ

タ要求セル集合は {c00 , c01 , c02 , c10 , c11 , c12 , c20 , c21 , c22 } となり，図 5 における灰色の領域である．

2 フェーズ目では，クエリ発行端末は，1 フェーズ目で計算の解を求めるために必要であるデータが存在するセルの集合

したデータ要求セル集合に含まれるセル ID をデータ要求メッ（データ要求セル集合）を計算する．ここで，ある任意のセルセージに添付し，1 フェーズ目と同様の方法で，データ要求メッ

を cij とし，cij の 1 つ右のセルおよび 1 つ上のセルをそれぞ

セージをフラッディングする．以下，データ要求セル集合に含kl
れ ci(j+1) および c(i+1)j とする．このとき，セル集合 Cijをまれるセルの領域の和集合をデータ要求領域と呼ぶ．葉端末

kl
kl
Cij
= ∪j <∪ =y<i+l cyx ，セル集合 Cijに含まれるセル=x<j+k i<

は，データ要求領域に存在するデータを所持している場合，そklのスコアの和を score(Cij) と定義する．ただし，ネットワーのデータを親端末へ返信する．データを受信した端末は送信元

ク領域外のセルのスコアは 0 とみなす．また，ネットワーク領

端末を送信先とする ACK メッセージを送信する．この ACK域を分割した全てのセルの集合を Call と表す．まず，クエリ

メッセージは単純手法のデータ返信時と同様の処理を行う．ま発行端末はネットワーク領域を分割した全てのセル cij ∈ Call

た，全ての子端末からデータを受信した端末は，子端末から受klに対して score(Cij) を計算する．a = C.width × k および

信したデータおよびデータ要求領域に存在する自身のデータをkl
b = C.length × l であり，Cijの大きさがクエリ発行端末の指定

親端末へ送信する．一方，ある端末がデータ要求領域に存在す

kl
した長方形の大きさと等しいため，maxcij ∈Call {score(Cij)} はるデータを所持していない場合，データを添付せずに親端末にMaxRS クエリの解となる領域のスコアの下限値となる．これをメッセージを送信する．また，1 フェーズ目のメッセージを受

lbscore と表す．次に，クエリ発行端末はネットワーク領域を分割

信していない端末が 2 フェーズ目のメッセージを受信した場合，(k+1)(l+1)

した全てのセル cij ∈ Call に対して score(Cij) を計算

この端末はデータ要求領域を把握できないため，自身のデータ(k+1)(l+1)

を全て親端末へ送信する．ここで，親端末が 1 フェーズ目のに含まれるセルは，MaxRS クエリの解を求めるために必要でメッセージを受信していた場合，データ要求領域を把握していあるデータが存在する可能性があるため，データ要求セル集合

るため，子端末から送信されたデータのうちデータ要求領域にの要素とする．これにより，クエリ発行端末は，2 フェーズ目

含まれないデータは，これ以降送信しない．以下の例を用いて，においてデータを要求しなければならない領域を把握できる．

2 フェーズ目の返信を説明する．

(k+1)(l+1)

する．score(Cij)>= lbscore となるセル集合 Cij以下の例を用いて，k = l = 1 の場合の計算方法を説明する．

例 3.3．図 6 は，2 フェーズ目の返信の例を示している．まず，

例 3.2．図 5 は，クエリ発行端末が取得したセル毎のスコ

葉端末である M1 および M3 がそれぞれ親端末へメッセージアの和の例を示している．セル内の長方形に囲まれた数値を送信する．このとき，M1 はデータ要求領域に存在するデーは，セルのスコアを表している．例えば，セル c00 のスコア

タ（D1 ）を所持しているため，親端末 M2 にデータ D1 を送は 100，セル c01 のスコアは 80 である．k = l = 1 のため，信する．一方，M3 はデータ要求領域に存在するデータを所持

11
lbscore = maxcij ∈Call {score(Cij)} = 300（セル c11 ）である．

していないため，データを添付せずに親端末 M4 にメッセー

次に，ネットワーク領域を分割した全てのセル cij ∈ Call に対ジを送信する．その後，子端末 M3 から返信メッセージを受

22
して score(Cij) を計算する．例えば，セル c03 ，c04 ，c13 ，およ信した M4 は，データ要求領域に存在する自身のデータ D10 ，

ഈଜ

ID

‫ܯ‬ଵ

‫ܦ‬ଵ
‫ܦ‬ଶ

‫ܯ‬ଶ
‫ܯ‬ଷ
‫ܯ‬ସ

‫ܦ‬ଷ

‫ܦ‬ସ

‫ܦ‬ହ
‫଺ܦ‬
‫଻ܦ‬
‫଼ܦ‬
‫ܦ‬ଽ

‫ܦ‬ଵ଴

‫ܦ‬ଵଵ
‫ܦ‬ଵଶ

崡崛崊 ਜ਼઼
20
ܿଶ଴
50
ܿଷ଴
30
ܿସ଴
70
ܿ଴଴
50
20
20

20
20
20
30
40

ܿଵ଴
ܿଵଵ
ܿଵଷ

ܿଵସ
ܿଶଷ

ܿ଴ଶ

䝕䞊䝍せồ䝉䝹㞟ྜሼܿ଴଴ ǡ ܿ଴ଵ ǡ ܿ଴ଶ ǡ ܿଵ଴ ǡ ܿଵଵ ǡ ܿଵଶ ǡ ܿଶ଴ ǡ ܿଶଵ ǡ ܿଶଶ ሽ‫ܯ‬ଵ

表 1 パラメータ設定
パラメータ

意味

デフォルト値（範囲）

n[台]

端末数

80 (50–120)d[個]1 台の端末が持つデータ数

80 (1–160)

L[m]正方形の一辺の長さ40 (20–100)ନਦ嵉崫崣嵤崠

ॹ‫ܦॱش‬ଵ‫ܯ‬ଶॹ‫ॱش‬ऩख

‫ܯ‬ଷॹ‫ܦॱش‬ଵ଴ ǡ ‫ܦ‬ଵଵ ǡ ‫ܦ‬ଵଶ

‫ܯ‬ସ

ܿଵଶ
ܿଶଶ

ॹ‫ܦ ॱش‬ଵ ǡ ‫ܦ‬ସ ǡ ‫ܦ‬ହ ǡ ‫ ଺ܦ‬ǡ ‫ܦ‬ଵ଴ ǡ ‫ܦ‬ଵଵ ǡ ‫ܦ‬ଵଶ

図 6 2 フェーズ目の返信例

D11 ，および D12 を親端末 M2 に送信する．全ての子端末から(a) クラスタ分布

返信メッセージを受信した M2 は，子端末から受信したデータ

図7

D1 ，D10 ，D11 ，および D12 とデータ要求領域に存在する自身のデータ D4 ，D5 ，および D6 を親端末に送信する．

(b) 一様分布

データの位置分布

M axScorepq p· (p+1) + 20z
2w
2Distancew=+1
Distancemax

o.score =これにより，クエリ発行端末はデータ要求領域に存在する
データ，つまり，MaxRS クエリの解を求めるために必要なデー
タを収集できる．その後，クエリ発行端末は，収集したデータ

M axScore は [200,1000] の一様分布により決定した各クラスタ

および指定した長方形（横の長さ a，縦の長さ b）から MaxRSの中心地点のスコアの最大値，Distance はデータの位置とデークエリの解を求める．

4. シミュレーション評価

タの位置が属するクラスタの中心地点の距離，Distancemax は
データの位置が属するクラスタの中心地点からの最大距離，zは正規乱数である．p および q はパレート分布のパラメータで本章では，提案手法の性能評価のために行ったシミュレーショ

あり，本実験では p = 2 および q = 1 を用いた．このように計ン実験の結果を示す．本実験では，ネットワークシミュレータ

算したスコアを離散化し，[1,1000] の範囲の整数値とした．まQualnet6.1 （注 1） を用いた．また，MaxRS 問題を解くアルゴリ

た，生成したデータをランダムに各端末に配置した．本実験にズムは，C++で実装されており，実験は 3.4GHz Core i7 およ

おいて，クエリ発行端末は，MaxRS 検索における長方形を一辺び 8GB RAM で構成される PC 上で行った．

の長さが L である正方形で指定した．提案手法におけるセルサ

4. 1 シミュレーション環境

イズは，指定した正方形の大きさと等しいもの（k = 1, l = 1）

600[m]×600[m] の二次元平面上の領域に n 台の端末が存とした．上で設定したパラメータを表 1 に示し，太字をデフォ在する．各端末はランダムウェイポイントモデル [2] に従い，ルト値とする．デフォルトのデータセットとして，データの位[0,1.0][m/s] の速度で移動し，停止時間は 30[s] とした．各端

置をクラスタ分布，データのスコアをパレート分布で生成した

末は IEEE802.11b を使用し，通信帯域 11[Mbps]，通信伝播距

ものを使用した．

離が 100[m] 程度となる送信電力で通信する．各端末はデータ比較手法として，2. 2 節で述べた単純手法を用いた．また，ID，スコア，および二次元座標 (x, y) で構成されるデータを d

全ての手法において HOPmax = 9 とした．デフォルト値を用個保持するものとする．検索開始時におけるネットワーク全体

いた事前実験を行い，それぞれの手法において，取得精度の最のデータの位置分布およびスコア分布を以下で説明する．デー

大値を基に，最大待ち時間を決定した．具体的には，単純手法

タの位置分布はクラスタ分布および一様分布を用いた（図 7）．

は最大待ち時間を 29[s]，提案手法は 1 フェーズ目の最大待ち時

クラスタ分布は，クラスタの中心の x 座標および y 座標をそれ間を 3[s]，2 フェーズ目の最大待ち時間を 24[s] とした．また，ぞれ平均とする正規分布を用いて，データの位置の x 座標およ提案手法 (HALF) は，2 フェーズ目の最大待ち時間を提案手法

び y 座標をそれぞれ決定した．一様分布は，値の範囲が [0,600]の半分とした．つまり，1 フェーズ目の最大待ち時間は 3[s]，2の中の実数値である一様乱数を用いて，x 座標および y 座標をフェーズ目の最大待ち時間は 12[s] とした．

それぞれ決定した．また，データのスコア分布はパレート分布

以上のシミュレーション環境において，クエリ発行端末をラの確率密度関数を基にしてデータの位置との相関性を考慮しンダムに選び，クエリを発行するという処理を 100 回繰り返し，た分布（以下，パレート分布と呼ぶ），およびスコアの範囲が以下の評価値の平均を調べた．

[1,1000] の中の整数値である一様分布を用いた．パレート分布は以下の式でスコアの計算を行った．

•

トラヒック：送信されたメッセージの総バイト数．表 2

は、各手法における全てのメッセージサイズを示す．この表において，D はメッセージに含まれるデータ数，AllCell は分割
した全てのセルの数，ReqCell はデータを要求するセルの数を（注 1）：http://www.scalable-networks.com

表す．

1.2

༢⣧ᡭἲ

ᥦ᱌ᡭἲ

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

1

༢⣧ᡭἲ

ᥦ᱌ᡭἲ

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

30

༢⣧ᡭἲ

ᥦ᱌ᡭἲ

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

0.9
25

0.8

0.6
0.4

0.7

᳨⣴᫬㛫 㼇㼟㼉

ྲྀᚓ⢭ᗘ䝖䝷䝠䝑䜽 㼇㻹㻮㼉

1
0.8

0.6
0.5
0.4
0.3
0.2

0.2

20
15
10
5

0.1
0

0
ࡸLc+Sp࡯ ൅ ࡿࡼ

ࡸLc+Su࡯ ൅ ࡿࢁ

ࡸLu+Spࢁ ൅ ࡿࡼ

䝕䞊䝍䝉䝑䝖

ࡸLu+Suࢁ ൅ ࡿࢁ

0
ࡸLc+Sp࡯ ൅ ࡿࡼ

(a) トラヒック

ࡸLc+Su࡯ ൅ ࡿࢁ

ࡸLu+Spࢁ ൅ ࡿࡼ

䝕䞊䝍䝉䝑䝖

ࡸLu+Suࢁ ൅ ࡿࢁ

(b) 取得精度

ࡸLc+Sp࡯ ൅ ࡿࡼ

ࡸLc+Su࡯ ൅ ࡿࢁ

ࡸLu+Spࢁ ൅ ࡿࡼ

䝕䞊䝍䝉䝑䝖

ࡸLu+Suࢁ ൅ ࡿࢁ

(c) 検索時間

図 8 データセットによる影響

図 8(c) より，単純手法において，データセットは，検索時間

表 2 各メッセージのサイズ
手法

メッセージの種類

単純手法
提案手法

両手法

•

サイズ [B]にあまり影響しないことが分かる．一方，提案手法および提案

データ要求メッセージ16
24 + 16 × D

手法 (HALF) は，位置分布がクラスタ分布およびスコア分布がデータ返信メッセージ
クエリメッセージ

24

フェーズ 1 返信メッセージ

16 + 4 × AllCell

データ要求メッセージ

24 + 4 × ReqCell

データセットの場合，2 フェーズ目に収集すべきデータ数が最も少なくなるため，2 フェーズ目においてパケット損失が起きる可能性が低くなるからである．

データ返信メッセージ

24 + 16 × D

フェーズ 1 返信メッセージの ACK

12

メッセージフラッディング時の ACK

12

データ数 d を変化させた時の提案手法の性能を調べた．そのデータ返信メッセージの ACK

16

結果を図 9 に示す．横軸はデータ数 d を示し，縦軸は，図 9(a)取得精度：MaxRS 検索の正解を求めるために必要であるデータを取得した割合．

•

パレート分布の時に，検索時間が最も小さい．これは，上記の検索時間：クエリ発行端末がクエリを発行してからMaxRS 検索の解を取得するまでの時間．
4. 2 データセットの影響
データの位置分布およびスコア分布を変化させた時の単純手
法と提案手法の性能を調べた．その結果を図 8 に示す．横軸は用いたデータの位置分布およびスコア分布を示し，縦軸は，図8(a) はトラヒック，図 8(b) は取得精度，および図 8(c) は検索時間を表す．ここで，図中の LC および LU は，データの位置
分布がそれぞれクラスタ分布および一様分布であることを表し，

SP および SU は，データのスコア分布がそれぞれパレート分
布および一様分布であることを表す．また，LC + SP はデータセットが，LC および SP を用いて生成されたことを示す．
図 8(a) より，提案手法および提案手法 (HALF) はデータセッ
トに関わらず，単純手法よりもトラヒックが小さいことが分かる．特に，スコア分布がパレート分布の場合，提案手法および提案手法 (HALF) は，単純手法よりも大幅にトラヒックが小さい．具体的には，提案手法は，位置分布がクラスタ分布の時は単純手法の約 50%のトラヒック，データが一様分布の時は単純手法の約 35%のトラヒックである．これは，スコア分布がパレート分布の場合，提案手法は 1 フェーズ目でデータ要求を行うセルを効率的に限定でき，2 フェーズ目において，返信するデータ数が少なくなるためである．
図 8(b) は，データセットに関わらず，提案手法が単純手法よりも取得精度が高いことを示している．このことから，提案手法は 1 フェーズ目において，MaxRS 検索の計算に必要なデー
タが存在する領域を高い精度で特定できていることが分かる．

4. 3 データ数の影響はトラヒック，図 9(b) は取得精度，および図 9(c) は検索時間を表す．
図 9(a) および図 9(b) の結果より，全ての手法において，d が大きくなるとトラヒックが増加し，取得精度が低下することが分かる．これは，ネットワーク内に存在するデータ数が多くな
り，全ての手法において，返信するデータ数が多くなるためである．また，d が大きい場合，提案手法および提案手法 (HALF)
は，単純手法と比較してトラヒックが小さく，提案手法は，dに関わらず，高い取得精度を維持していることが分かる．これは，提案手法において，1 フェーズ目でデータ要求を行うセル
を限定することにより，2 フェーズ目で返信するデータ数を抑制できていることを示している．一方，提案手法 (HALF) は，提案手法よりも取得精度が低くなっている．これは，2 フェー
ズ目の最大待ち時間が短いため，同時にメッセージを送信する端末が多くなり，パケット損失が起こる可能性が高くなるからである．
図 9(c) より，全ての手法において，d が大きくなると検索時間が長くなっていき，最大待ち時間に収束することが分かる．
全ての手法において，d が大きくなると，送信するデータ数が多くなり，パケット損失が増加する．これにより，中継端末が，子端末からデータを受信できず，データ返信待ち時間が経過するまで待機する可能性が高くなるためである．しかし，提案手法は，他の手法に比べて，検索時間が最大待ち時間に収束する

d の値が大きい．
4. 4 正方形の一辺の長さの影響
正方形の一辺の長さ L を変化させた時の提案手法の性能を調べた．その結果を図 10 に示す．横軸は正方形の一辺の長さ Lを示し，縦軸は，図 10(a) はトラヒック，図 10(b) は取得精度，
および図 10(c) は検索時間を表す．

㻝

㻟

༢⣧ᡭἲ

㻜㻚㻤

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻜㻚㻣

㻝㻚㻡
㻝

㻜㻚㻡
㻜

㻞㻡

᳨⣴᫬㛫 㼇㼟㼉

㻞

㻟㻜

㻜㻚㻥

ᥦ᱌ᡭἲ

ྲྀᚓ⢭ᗘ

䝖䝷䝠䝑䜽 㼇㻹㻮㼉

㻞㻚㻡

㻜㻚㻢
㻜㻚㻡
㻜㻚㻠
㻜㻚㻟

༢⣧ᡭἲ

㻜㻚㻞

ᥦ᱌ᡭἲ

㻜㻚㻝

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻞㻜

㻠㻜

㻢㻜

㻤㻜

㻝㻜㻜

㻝㻞㻜

㻝㻠㻜

㻝㻜

༢⣧ᡭἲ
ᥦ᱌ᡭἲ

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕
㻜

㻜

㻝㻢㻜

㻝㻡

㻡

㻜

㻜

㻞㻜

㻞㻜

㻝ྎ䛾➃ᮎ䛜ᣢ䛴䝕䞊䝍ᩘ 㼇ಶ㼉

㻠㻜

㻢㻜

㻤㻜

㻝㻜㻜

㻝㻞㻜

㻝㻠㻜

㻜

㻝㻢㻜

㻞㻜

㻝ྎ䛾➃ᮎ䛜ᣢ䛴䝕䞊䝍ᩘ 㼇ಶ㼉(a) トラヒック

㻠㻜

㻢㻜

㻤㻜

㻝㻜㻜

㻝㻞㻜

㻝㻠㻜

㻝㻢㻜

㻝ྎ䛾➃ᮎ䛜ᣢ䛴䝕䞊䝍ᩘ 㼇ಶ㼉(b) 取得精度(c) 検索時間

図 9 データ数 d の影響
㻝

㻝㻚㻠

㻞㻡

㻜㻚㻤

㻜㻚㻤
㻜㻚㻢
㻜㻚㻠

㻜㻚㻞

㻜㻚㻣
㻜㻚㻢
㻜㻚㻡
㻜㻚㻠

༢⣧ᡭἲ

㻜㻚㻟

༢⣧ᡭἲ

ᥦ᱌ᡭἲ

㻜㻚㻞

ᥦ᱌ᡭἲ

㻜㻚㻝

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻞㻜

㻠㻜

㻢㻜

㻤㻜

㻞㻜

㻝㻜㻜

༢⣧ᡭἲ
ᥦ᱌ᡭἲ

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻠㻜

㻢㻜

㻜

㻝㻜㻜

㻤㻜

㻞㻜

㻠㻜

㻢㻜

㻤㻜

ṇ᪉ᙧ䛾୍㎶䛾㛗䛥 㼇㼙㼉(a) トラヒック(b) 取得精度(c) 検索時間

㻟㻜

㻜㻚㻥
㻜㻚㻣

㻝㻚㻡
㻝
㻜㻚㻡
㻜

㻞㻡

᳨⣴᫬㛫 㼇㼟㼉

㻜㻚㻤ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

ྲྀᚓ⢭ᗘ

ᥦ᱌ᡭἲ

㻜㻚㻢
㻜㻚㻡
㻜㻚㻠
㻜㻚㻟

༢⣧ᡭἲ

㻜㻚㻞

ᥦ᱌ᡭἲ

㻜㻚㻝

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻤㻜

㻥㻜

㻝㻜㻜

㻝㻝㻜

㻝㻞㻜

㻞㻜
㻝㻡
㻝㻜

༢⣧ᡭἲ
ᥦ᱌ᡭἲ

㻡

ᥦ᱌ᡭἲ㻔㻴㻭㻸㻲㻕

㻜

㻣㻜

㻝㻜㻜

正方形の一辺の長さ L の影響

㻝

༢⣧ᡭἲ

㻢㻜

㻝㻜

ṇ᪉ᙧ䛾୍㎶䛾㛗䛥 㼇㼙㼉

㻞㻚㻡

㻡㻜

㻝㻡

ṇ᪉ᙧ䛾୍㎶䛾㛗䛥 㼇㼙㼉

図 10

㻞

㻞㻜

㻡

㻜

㻜

䝖䝷䝠䝑䜽 㼇㻹㻮㼉᳨⣴᫬㛫 㼇㼟㼉㻝ྲྀᚓ⢭ᗘ䝖䝷䝠䝑䜽 㼇㻹㻮㼉

㻟㻜

㻜㻚㻥

㻝㻚㻞

㻜

㻡㻜

㻢㻜

㻣㻜

㻤㻜

㻥㻜

㻝㻜㻜

㻝㻝㻜

㻝㻞㻜

㻡㻜

㻢㻜

㻣㻜

㻤㻜

㻥㻜

➃ᮎᩘ 㼇ྎ㼉➃ᮎᩘ 㼇ྎ㼉➃ᮎᩘ 㼇ྎ㼉(a) トラヒック(b) 取得精度(c) 検索時間

㻝㻜㻜

㻝㻝㻜

㻝㻞㻜

図 11 端末数 n の影響

図 10(a) の結果より，単純手法は L の影響を受けずトラヒッ

通信を行うことで，返信するデータ数を削減しているためであクが一定であるのに対し，提案手法および単純手法 (HALF)

る．また，提案手法 (HALF) は L が 40 以上のとき，単純手法

は，L の影響を受けてトラヒックが変化していることが分かる．

より取得精度が小さい．これは，4. 3 節で述べたように，最大

これは，単純手法は L の大きさに関わらず，ネットワーク中の待ち時間が短く，同時にメッセージを送信する端末が多くなり，全てのデータを収集するためである．一方，提案手法および提パケット損失が多くなるためである．

案手法 (HALF) は L = 30 から L = 90 の時にトラヒックがほ

図 10(c) の結果より，単純手法は L の影響を受けず検索時間

ぼ変化せず，L = 100 の時にトラヒックが小さくなっているこがほぼ一定であるのに対し，提案手法および提案手法 (HALF)とが分かる．L が小さくなると，ネットワーク領域を分割したは，L の影響を受けて検索時間が変化している．2 フェーズ目

際のセルの数が増加するため，提案手法における 1 フェーズ目で取得する必要のあるデータ数が L によって変わるため，それのメッセージサイズが大きくなる．また，L = 30 から L = 90

らのデータを全て受信するまでの時間も変わるからである．

の時，分割した全てのセルの数に対するデータ要求セルの数の

4. 5 端末数の影響

割合が大きくなり，2 フェーズ目において返信するデータ数が端末数 n を変化させた時の提案手法の性能を調べた．その結多くなる．
図 10(b) より，単純手法は L の影響を受けず取得精度が一定であるのに対し，提案手法および提案手法 (HALF) は，L の影

果を図 11 に示す．横軸は端末数 n を示し，縦軸は，図 11(a)はトラヒック，図 11(b) は取得精度，および図 11(c) は検索時間を表す．

響を受けて取得精度が変化していることが分かる．これは，上

図 11(a) より，全ての手法において，端末数が多くなるとトに述べたように，単純手法が，L の大きさに依存しない手法でラヒックが増加することが分かる．これは，端末数が多くなるあるためである．また，提案手法は全ての場合において，単純と，ネットワーク内のデータ数が多くなり，返信するデータ数

手法よりも取得精度が高い．これは，提案手法が 2 フェーズのが多くなるためである．また，図 11(a) および図 11(b) より，

端末数に関わらず，提案手法および提案手法 (HALF) は，単純を収集する．さらに，収集した情報をもとにデータを収集する手法よりもトラヒックが小さく，ほとんどの場合において，単必要がある領域を限定し，2 フェーズ目で，特定した領域に存純手法よりも取得精度が高いことが分かる．これは，提案手法

在するデータのみを収集する．これにより，MaxRS 検索の解および提案手法 (HALF) において，1 フェーズ目でデータ要求の計算に不必要なデータの送信を抑制できる．シミュレーショ

セルを限定することが，取得精度を維持しつつトラヒックを削

ン実験の結果から，提案手法が高い取得精度を維持しつつ，ト減する上で有効であることを示している．

ラヒックを削減できていることを確認した．

図 11(c) より，全ての手法において，端末数に関わらず，検ネットワーク内のデータ数が多い場合，データを収集する

索時間がほぼ一定であることが分かる．これは，端末数により，必要がある領域を限定した場合でも，2 フェーズ目で返信する

平均ホップ数があまり変化しないためである．

データ数が多くなり，取得精度が低下してしまう．また，提案

5. 関 連 研 究
集中管理データベースの分野において，MaxRS 検索を効率的に行う様々な手法が提案されている [3]，[5]，[6]，[9]，[10]．文
献 [9] では，全てのデータをメモリ上に格納できる環境におい手法はデータのスコアの分布により，トラヒックおよび取得精度が大きく影響される．そこで，返信メッセージのトラヒック
をさらに抑制する手法を設計することを検討している．

謝

辞て，文献 [5]，[6] では，全てのデータをメモリ上に格納できない

本 研 究 の 一 部 は ，文 部 科 学 省 研 究 費 補 助 金・基 盤 研 究

環境において，正確な MaxRS 検索を実行する手法をそれぞれ(A)(26240013) および，挑戦的萌芽研究 (26540035)，JST 国

提案している．また，文献 [10] では，全てのデータをメモリ上際科学技術共同研究推進事業（戦略的国際共同研究プログラム）に格納できない環境における近似アルゴリズムを提案している．

の研究助成によるものである．ここに記して謝意を表す．

文献 [3] では，指定された長方形の回転を考慮したアルゴリズ
ムを提案している．これらの研究は，集中管理データベースにおいて，計算量の削減や，ディスク I/O の削減を目的としており，分散環境であるアドホックネットワークに適応することは困難である．
無線センサネットワークの分野において，領域検索問題を扱う研究が存在する [4]，[11]．文献 [11] では，消費電力の抑制を目的とした max regional aggregate（MaxRA）クエリ処理手法が提案されている．MaxRA クエリは，領域の大きさを指定
し，指定された大きさの領域内に含まれるセンサ端末のセンサ
値の集約値（平均値や合計値）が最も大きい領域を検索するものである．つまり，MaxRS クエリは MaxRA クエリの一部といえる．この文献では，精度を保証した上で，データを取得する領域およびセンサ端末をサンプリングする近似手法を用いている．また，文献 [4] では，region-based クエリ処理手法が提案されている．region-based クエリは，値の範囲および領域の大きさを指定し，指定された大きさの領域内に含まれるセンサ
端末のセンサ値の集約値が，指定された値の範囲に含まれる領域を検索するものである．この文献では，クラスタリングベー
スのクエリ処理手法を用いて，消費電力を抑制している．具体的には，基地局が，集約すべき領域を全て計算し，それに応じたクラスタヘッドの選択の最適化問題を解いている．これらの研究は，条件を満たす領域を検索するという点において，本研究における MaxRS クエリと同様であるが，本稿で扱う問題とは異なるため，これらの研究で提案されている手法は適用でき
ない．

6. お わ り に
本稿では，アドホックネットワークにおいて，高い取得精度を維持しつつトラヒックを削減することを目的とする MaxRS
検索処理手法を提案した．提案手法では，1 フェーズ目に，ネッ
トワーク領域をグリッド状に分割し，分割したセル毎のスコア

文

献[1] Amagata, D., Sasaki, Y., Hara, T. and Nishio, S.: CTR: An
Eﬃcient Cluster-based Top-k Query Routing in MANETs,
MoMM, pp. 225–234 (2014).
[2] Camp, T., Boleng, J. and Davies, V.: A survey of mobility
models for ad hoc network research, Wireless Communications and Mobile Computing, Vol. 2, No. 5, pp. 483–502(2002).
[3] Chen, Z., Liu, Y., Wong, R. C.-W., Xiong, J., Cheng, X.
and Chen, P.: Rotating MaxRS queries, Information Sciences, Vol. 305, pp. 110–129 (2015).
[4] Choi, D.-W. and Chung, C.-W.: REQUEST+: A framework for eﬃcient processing of region-based queries in sensor networks, Information Sciences, Vol. 248, pp. 151–167(2013).
[5] Choi, D.-W., Chung, C.-W. and Tao, Y.: A scalable algorithm for maximizing range sum in spatial databases,
PVLDB, Vol. 5, No. 11, pp. 1088–1099 (2012).
[6] Choi, D.-W., Chung, C.-W. and Tao, Y.: Maximizing Range
Sum in External Memory, ACM TODS, Vol. 39, No. 3, p. 21(2014).
[7] Imai, H. and Asano, T.: Finding the connected components
and a maximum clique of an intersection graph of rectangles in the plane, Journal of algorithms, Vol. 4, No. 4, pp.
310–323 (1983).
[8] Komai, Y., Sasaki, Y., Hara, T. and Nishio, S.: kNN Query
Processing Methods in Mobile Ad Hoc Networks, IEEE
TMC, Vol. 13, No. 5, pp. 1090–1103 (2014).
[9] Nandy, S. C. and Bhattacharya, B. B.: A unified algorithm
for finding maximum and minimum object enclosing rectangles and cuboids, Computers & Mathematics with Applications, Vol. 29, No. 8, pp. 45–61 (1995).
[10] Tao, Y., Hu, X., Choi, D.-W. and Chung, C.-W.: Approximate MaxRS in spatial databases, PVLDB, Vol. 6, No. 13,
pp. 1546–1557 (2013).
[11] Zhuang, Y. and Chen, L.: Max regional aggregate over sensor networks, ICDE, pp. 1295–1298 (2009).