DEIM Forum 2014 E8-4

複数拠点統合型センサネットワークにおけるモバイルセンサデータの空間インデックスの構築手法
川住涼†

義久 智樹†

原隆浩†

西尾章治郎†† 大阪大学大学院情報科学研究科マルチメディア工学専攻
E-mail: †{kawasumi.ryo,yoshihisa,hara,nishio}@ist.osaka-u.ac.jp
あらまし近年，モバイルセンサデータと呼ばれる，スマートフォンなどの移動型端末から得られるセンサデータが注目されている．広範囲にわたる多数のモバイルセンサデータを管理するため，複数のセンサネットワーク拠点を連携させて統合的に利用する複数拠点統合型センサネットワークが利用されることがある．しかし，従来の複数拠点統合型センサネットワークでは，モバイルセンサデータの位置情報を各拠点のみが把握していたため，所望のモバイル
センサデータを有する拠点の検索に時間がかかっていた．そこで本稿では，複数拠点統合型センサネットワークにおけるモバイルセンサデータの空間インデックス構築手法を提案する．提案手法では，各拠点が有するモバイルセンサ
データの位置情報の範囲を木構造を用いてインデックスサーバで管理する．評価の結果，所望のデータを有する拠点を高精度に取得しつつ，従来のインデックス構築手法より検索時間を短縮できることが分かった．
キーワード

センシング，空間データベース，インデクシング

1. は じ め に

サーバのみが把握していたため，所望のモバイルセンサデータを有するセンサネットワーク拠点の検索に時間がかかっていた．

近年，位置や温度といったセンサデータを取得できるスマー

例えば，移動先付近の人の混み具合を調べる場合，その場所付

トフォンなどの小型の移動型端末が急速に普及している．移動

近のモバイルセンサデータを管理するセンサネットワーク拠点型端末から得られるセンサデータはモバイルセンサデータとを検索するために，すべてのセンサネットワーク拠点に問い合呼ばれ，多くの人が持つスマートフォン等から周期的にセンサわせる必要があった．文献 [4] では，センサネットワーク拠点

データを収集することで，広範囲にわたる多数のモバイルセンの位置情報を用いて問い合わせを行うセンサネットワーク拠点

サデータを収集できる ( [1], [2]) ．より多くのモバイルセンサを取捨選択する手法が提案されているが，固定型端末から得らデータを収集するため，複数の組織が運営するセンサデータ収れるセンサデータを対象としていた．移動型端末から得られる集拠点を連携させて統合的に利用する複数拠点統合型センサ

センサデータの場合，モバイルセンサデータが取得された位置

ネットワークが利用されることがある ( [3], [4]) ．複数拠点統とセンサネットワーク拠点の位置が近いとは限らず，問い合わ

合型センサネットワークの構成を図 1 に示す．各センサネット

せを行うセンサネットワーク拠点を適切に取捨選択できない問

ワーク拠点には管理サーバがあり，モバイルセンサデータの収題があった．

集や検索などを管理している．各センサネットワーク拠点で収

そこで本稿では，複数拠点統合型センサネットワークにおけ集されたモバイルセンサデータは，各センサネットワーク拠点

るモバイルセンサデータの空間インデックス構築手法を提案すにあるセンサデータベースに格納される．複数拠点統合型センる．提案手法では，複数拠点統合型センサネットワークにおいサネットワークでは，管理サーバが相互にネットワークで接続て，各センサネットワーク拠点がセンサデータベースに格納しされている．

ているモバイルセンサデータの位置情報の範囲を木構造を用いほとんどの複数拠点統合型センサネットワークでは，モバイてインデックスサーバで管理する．各センサネットワーク拠点

ルセンサデータの位置情報を各センサネットワーク拠点の管理においても，モバイルセンサデータの位置情報を木構造を用いて管理し，距離的に近い複数の位置情報を一つにまとめること
で，インデックスの数とインデックスサーバへの送信トラヒッ
クを削減する．さらに，本稿では，提案手法を実装し，実行速度や精度に関する評価を行った．評価の結果，所望のデータを有する拠点を高精度に取得しつつ，従来の R*-tree [5] を用いた
インデックス構築手法による検索より検索時間を短縮できる場
合があることが分かった．
本稿の構成を以下に示す．2 章では，本研究に関連する既存

図1

拠点統合型センサネットワーク

研究を紹介し，本研究との関連について述べる．3 章では，本研究が想定する環境について述べる．4 章では，提案手法について述べる．5 章では，提案手法の性能評価について述べる．
最後に 6 章で，まとめと今後の課題について述べる．

2. 関 連 研 究

QTree よりも木の再構築に要する時間を削減している．
2. 3 P2P 環境における空間インデックスの利用
文献 [9] では，P2P 環境において，インデックスサーバを用
いて各ピアが管理するデータの範囲を共有している．文献 [9]本研究では，複数拠点統合型センサネットワークにおける空では，各ピアが管理するデータの範囲に重複がないことを前提

間インデックス構築手法を提案している．関連研究として，2. 1としているが，運営組織が異なれば重複していることがある．

節で複数拠点統合型センサネットワークに関する研究，2. 2 節

各ピアが管理する範囲に重複がある場合には，結局全てのピア

で空間インデックス構築手法に関する研究を紹介する．2. 3 節に問い合わせることになり，ピアの検索に時間がかかる問題がでは，P2P 環境における空間インデックス構築手法に関する研発生する．

究ついて紹介する．

2. 1 複数拠点統合型センサネットワーク
GSN (Global Sensor Network, [3]) は，各センサネットワー

3. 想 定 環 境
3. 1 概要

ク拠点の管理サーバで P2P オーバレイを構築している．P2P

本研究では，図 2 に示す構成の複数拠点統合型センサネット

オーバレイでは，ピア同士がサーバを介さずに直接通信を行

ワークを想定する．1 章で述べたとおり，複数拠点統合型センサ

うため，サーバへの負荷集中が発生しない．文献 [6] において，ネットワークには，異なる組織で運営される複数のセンサネッ

GSN を用いてスマートフォンからモバイルセンサデータを収

トワーク拠点があり，各センサネットワーク拠点の管理サーバ

集する研究が行われているが，所望のモバイルセンサデータをがネットワークで接続されている．異なる組織で運営されてお有するセンサネットワーク拠点検索のための空間インデックス

り管理責任の都合等から単一の大きなセンサネットワーク拠点が構築されておらず，検索に時間がかかる問題がある．

として運営できない．また，複数拠点統合型センサネットワー

広域に分布する複数センサネットワークの統合利用システ

クには，モバイルセンサデータの検索時に利用できるインデッ

ムとして X-Sensor2.0 が開発されている [4]．X-Sensor2.0 もクスサーバがある．管理サーバやインデックスサーバは，従来GSN と同様に各センサネットワーク拠点をノードとして P2Pの研究 ( [3], [4], [6]) においてサーバへの負荷集中が発生しない

オーバレイを構築している．X-Sensor2.0 では，ピア間を移動と確認されている P2P オーバーレイを構築しており，サーバするプログラムであるモバイルエージェントを用いることで，を介さずに直接通信できる．モバイルセンサデータは空間デー

データを処理しながら検索を行うことが可能である．また，収タであり，緯度と経度の地理情報が付加されている．例えば，集の対象となるセンサデータの時間的，空間的な条件および

北緯 45 度，東経 135 度の温度は 20 度といった温度データや，データへの処理を記述できる STQL (Spatio Temporal Query

北緯 46 度，東経 136 度の気圧は 1000hPa といった気圧データ

Language) を提案している．しかし，X-Sensor2.0 は固定センが挙げられる．本研究では，地理情報以外の部分については特

サネットワーク拠点の統合を想定して設計されており，所望のに規定しない．

モバイルセンサデータを有する拠点の検索に時間がかかるとい3. 2 応 用 例

う問題がある．

モバイルセンサデータ収集サービスにより，スマートフォン

2. 2 空間インデックス

等からモバイルセンサデータが収集される．例えば，無料のモ

位置情報を持つ空間データに対するインデックス構築手法とバイルセンサデータ収集サービス (センサネットワーク拠点 A

して，最小方形領域 (Minimum Bounding Rectangle, MBR)が運営) を利用しているスマートフォン所有者のスマートフォを利用した R-tree [7] およびその拡張である R*-tree [5] がある．

ンで収集されるモバイルセンサデータはセンサネットワーク拠これらの手法では，空間データの位置情報を地理的範囲で参照

点 A のセンサデータベースに格納され，有料だが消費電力のする木構造の空間インデックスを用いている．地理的範囲が重小さいモバイルセンサデータ収集サービス (センサネットワー

複しないようにインデックスを構築しているが，空間データがク拠点 B が運営) を利用しているスマートフォン所有者のス挿入されるたびに地理的範囲を再計算して木構造を再構築する必要があり，空間データの挿入に時間がかかっていた．

QTree [8] では，空間インデックスを構成する木構造の葉ノードとして，データへの参照ではなく，Bucket を用いている．

Bucket とは，ある地理的範囲内にある空間データの集合である．空間データは，自身の位置データが含まれる Bucket に挿入される．該当する Bucket がない場合には空間インデックスを再構築して Bucket を作成する．Bucket の数が多くなると，Bucket の統廃合を行う．データ挿入時に空間インデックスを再構築する頻度が抑えられるが，再構築時に Bucket 内のすべてのデータを参照するため，検索に時間がかかる．提案方式では，Bucket のインデックスとして R*-tree の木構造を採用し，

図2

想定環境

マートフォンで収集されるモバイルセンサデータはセンサネッ
トワーク拠点 B のセンサデータベースに格納される．

が大きい場合には Bucket の併合を行う．

4. 3. 1 モバイルセンサデータの挿入方法

モバイルセンサデータ検索サービスにより，モバイルセンサ

モバイルセンサデータを挿入するアルゴリズムを Algorithm

データ収集サービスで収集されたモバイルセンサデータを検索1 に示す．なお，fmax は各ノードが保持できる MBR の数でできる．モバイルセンサデータ検索サービスの運営組織は，複ある．このアルゴリズムの入力は，挿入するモバイルセンサ

数のモバイルセンサデータ収集サービスの運営組織と連携してデータが含まれる，新しく挿入する Bucket であり，これを Bいる．例えば，大阪市内の人流把握を行うために，センサネッとする．まず初めに，挿入先の決定を行う．挿入先を決定する

トワーク拠点 A とセンサネットワーク拠点 B から大阪市内のアルゴリズムは従来の R*-tree のアルゴリズムと同じものを用

モバイルセンサデータを検索して地図上に表示することが考えいる．B の挿入先を決定する関数を chooseLeaf とし，挿入先られる．また，環境観測のために，大阪市内の気圧データを複の木構造におけるノードへの参照を返す．chooseLeaf(B) の結数のセンサネットワーク拠点から収集することが考えられる．

果を C に代入し，以降は挿入先のノードを C とする．C は子4. 提 案 手 法

要素 C.child を持ち，i 番目の子要素には C.child.get(i) によってアクセスすることができる．次に，B が挿入先の兄弟ノード

本章では，本研究が提案する複数拠点統合型センサネットとなる Bucket に含まれるかどうかを調べ，含まれる場合にはワークにおけるモバイルセンサデータの空間インデックスの構挿入を行わずに処理を打ち切る (8 行目〜13 行目) ．含まれて築手法の詳細について述べる．

4. 1 概要いない場合は，兄弟ノードとの Bucket の併合を試みる．併合を行う関数を merge とする (次項で説明) ．併合を行った場合提案手法では，インデックスサーバ内に空間インデックスをには，併合後の Bucket と残っている兄弟ノードとの併合を試構築し，各センサネットワーク拠点の管理サーバが Bucket をみ，これを繰り返す (14 行目〜21 行目) ．併合を行った後に，管理する．空間インデックスをインデックスサーバがもつこと

インデックスサーバへのデータの送信を行う (22 行目〜28 行

で，すべての管理サーバに問い合わせることなく所望のモバイ

目)．最後に，木構造を維持するために，子要素が fmax を超え

ルセンサデータを取得できる場合が多くなり，検索にかかる時

る場合の分割処理や，包含も併合もされなかった Bucket の追間を短縮できる．また，Bucket に対する操作を，その Bucket

加処理を行う (29 行目〜34 行目) ．

に属するモバイルセンサデータを有する管理サーバのみで行う

4. 3. 2 Bucket の併合

ことで，インデックスサーバの更新にかかる送信負荷を抑える

新しく挿入された Bucket と既存の Bucket を併合する際，併ことができる．

合前の面積と併合後の面積の差が大きいほど，実際のデータ分

Bucket については 4. 2 節，各センサネットワーク拠点におけ

布との誤差が大きくなり，検索の精度に影響を及ぼす．そこで，る空間データの管理方法については 4. 3 節，インデックスサー

このような面積の差をエラー差分 ∆E (図 3) と定義し，併合

バにおける空間インデックスの構築方法については 4. 4 節で説する際の基準として利用する．overlap(S1 , S2 ) は S1 と S2 が明する．モバイルセンサデータの検索方法は 4. 5 節で説明する．

重なっている部分の面積である．Bucket 併合のアルゴリズム

4. 2 Bucket

を Algorithm 2 に示す．入力は新しく挿入する Bucket B と

2. 2 節で簡単に説明したとおり，Bucket とは，ある地理的

挿入先のノード C である．2 つの Bucket が重なっている部分

範囲内における空間データの存在を示す識別子である．例えの面積は getOverlap 関数によって取得できる．また，併合後

ば，北緯 45 度，東経 135 度の温度データをセンサネットワーの MBR は getExpandMbr 関数によって取得できる．しきい

ク拠点 A が持っており，北緯 46 度，東経 136 度の温度データ

値 Ej に対して，∆E <= Ej を満たす場合に Bucket の併合を行をセンサネットワーク拠点 A と B が持っている場合，北緯 45う．併合先の候補が複数存在する場合は，併合後の面積が最も度，東経 135 度から北緯 46 度，東経 136 度の範囲内には，セ大きくなる組を選択し，併合を行う (7 行目〜21 行目) ．併合

ンサネットワーク拠点 A と B の識別子 (IP アドレス等) を含むを行う場合には，既存の Bucket の領域を拡張する (22 行目〜

Bucket が存在する．モバイルセンサデータを検索する際，イ

30 行目) ．

ンデックスサーバから所望の地理的範囲内に存在する Bucketを発見し，その Bucket に含まれる管理サーバに対してモバイ
ルセンサデータの問い合わせを行う．

4. 4 インデックスサーバにおける空間インデックスの構築
方法
各センサネットワーク拠点は，インデックスサーバに挿入や

4. 3 各センサネットワーク拠点での空間データ管理方法

更新を行った Bucket の情報を通知する．インデックスサーバ

各センサネットワーク拠点では，モバイルセンサデータを挿は，更新された Bucket の情報を用いて R*-tree を構築し，モバ入する際に，そのデータの位置が既存の Bucket に含まれている場合にはインデックスの更新を行わず，既存の Bucket に含
まれていない場合にのみ，新たな Bucket を作成して，インデックスの更新を行う．初期の Bucket は点領域となる．データの挿入により Bucket の数が多くなりすぎると R*-tree の深さが深くなり，検索や挿入に時間がかかるため，Bucket の重複範囲

図 3 エラー差分 ∆Eイルセンサデータへのインデックス (モバイルセンサデータがAlgorithm 2 Bucket の併合含まれる Bucket を担当するセンサネットワーク拠点管理サー

1: merge(B, C):

バの識別子) を作成する．Bucket に含まれるインデックスに変

2: /* 初期化 */更がなくても木が再構築される頻度を少なくするため，Bucket

3: tarea ⇐ 0の面積が大きくなってセンサネットワーク拠点の担当範囲が広4: tobj ⇐ null

くなったときのみ再構築を行う．
インデックスサーバに Bucket の更新情報を送信するアルゴ

5: exist ⇐ −1
6: i ⇐ 0
7: /* 併合先の Bucket を探索 */リズムを Algorithm 3 に示す．挿入先のノードに属する Bucket

8: while i < c doの現在の面積 S と s の差 d が d = (S − s) > 0 となる場合に，

9:

if C.child.get(i).id == B.id thensendToIndexServer 関数によって，拠点 ID（各拠点ごとに一

10:exist ⇐ i

意な文字列）と Bucket の情報をインデックスサーバに送信し

11:

continue(4 行目，10 行目) ，それらの s を更新する (5 行目，11 行目) ．

12:

end if13:

mbr ⇐ getExpandMbr(B,C.child.get(i))

14:ovl ⇐ getOverlap(B,C.child.get(i))

各拠点からデータを受け取ったインデックスサーバは，受信したデータに従ってインデックスの更新を行う．まず，送られて15:きた Bucket の範囲内に存在する，同じ拠点 ID を持つ Bucket

err ⇐ (mbr.w ∗ mbr.h) − ((B.w ∗ B.h) + (C.child.get(i).w∗ C.child.get(i).h) − ovl)の削除を行う．その後，送られてきた Bucket に拠点 ID を付

16:

与し，挿入を行う．

17:

if tarea < (mbr.w * mbr.h) && err <= Ej thentarea ⇐ (mbr.w * mbr.h)tobj ⇐ C.child.get(i)18:Algorithm 1 Bucket の挿入

19:

end if

1: B : 挿入する Bucket

20:

i⇐i+1

2: C : 挿入先のノード

21: end while

3: c : l の子要素の数

22: /* 併合処理 */4: insert(B):

23: if tobj != null then

5: /* 挿入先の Bucket をチェック */24:

tobj ⇐ getExpandMbr(B, tobj)

6: C ⇐ chooseLeaf(B)25:

tobj.s ⇐ B.s + tobj.s

7: i ⇐ 026:

if exist > 0 then8: while i < c do

27:

9:

if B が C.child.get(i) に含まれる thenreturn10:

C.child.remove(exist)

28:

end if29:

return tobj

11:

end if

30: end if

12:

i⇐i+1

31: return null

13: end while

32: end

14: /* 併合処理 */15: merge cnt ⇐ 0

Algorithm 3 更新情報の送信

16: merge obj ⇐ merge(B, C)

1: sync(B, C):

17: /* 併合を繰り返す */2: /* 各 Bucket を調べる */18: while merge obj != null do

3: if B != null && (B.S - B.s) > 0 then19:merge cnt ⇐ merge cnt + 1

4:

sendToIndexServer(B)20:merge obj ⇐ merge(merge obj, C)

5:

B.s ⇐ B.S

21: end while

6: end if

22: /* 更新情報の送信 */7: i ⇐ 0

23: if merge cnt > 0 then8: while i < c do

24:

sync(null, C)

9:

25:

return10:

26: else27:

sync(B, C)

if (C.child.get(i).S - C.child.get(i).s) > 0 thensendToIndexServer(C.child.get(i))
C.child.get(i).s ⇐ C.child.get(i).S

11:
12:

end if

28: end if

13:

i⇐i+1

29: /* 併合もできなかった場合の処理 */14: end while

30: if c == fmax then15: end31:/* 再挿入，分割処理 */32: else
33:/* Bucket の追加処理 */34: end if
35: end4. 5 インデックスサーバにおける問い合わせ処理

また，本評価では，モバイルセンサデータとして，実際に得問い合わせ処理に関しては，従来の R-tree や R*-tree と同られたジオタグ付きのツイートデータと，一様乱数によって決様に，問い合わせに含まれる地理的範囲と重複する部分がある

定した位置情報が付加されたデータの 2 種類を用いた．ジオタ

MBR を順次探索する．MBR 内の Bucket と問い合わせに含まグ付きのツイートデータは，twitter のものであり，2011 年 10れる地理的範囲に重なりがある場合にデータが存在すると判定

月 24 日から 2012 年 5 月 31 日までに得られた 25853434 個のし，Bucket に含まれるセンサネットワーク拠点 ID を問い合わ

ツイートである．ジオタグ付きツイートなどの実データでは都せ先に加える．ただし，問合せ先として同じ拠点 ID を既に保市部などにデータが集中するため，併合処理が活発に行われる持している場合は，問合せ先への追加は行わない．検索アルゴと考えられる．モバイルセンサデータの数は，各評価でパラメ

リズムを Algorithm 4 に示す．入力は要求範囲 n であり，位置タとして与えた．

と大きさを持つものとする．結果集合は ret とし，初期状態は

5. 2 評 価 結 果

空集合である．根から探索を行い，要求範囲と重なりのある要

5. 2. 1 データ挿入の評価

素について処理を行う (4 行目〜19 行目) ．重なりのある要素

データ挿入に関する性能評価として，データ挿入にかかる時が Bucket であり，その拠点 ID が ret に含まれていない場合

間と，挿入後のインデックスの数（エントリ数）を計測した．

は ret に拠点 ID を追加する (11 行目〜15 行目) ．重なりのあ

データ挿入にかかる時間は，ネットワークの通信帯域に依存しる要素が Bucket でない場合は次の探索候補として探索用のスて変化するが，性能を評価する上で，傾向を示すものとして 5

タックに追加する (16 行目) ．上記の処理をスタックが空にな

章始めに述べた環境で計測した．これらの評価指標は，Ej や挿るまで繰り返し．最終的な ret を問合せ先のリストとして返す．

入するデータ数に依存するため，これらを評価パラメタとして用いた．比較手法として，従来の R*-tree，葉ノードを Bucket

Algorithm 4 問合わせ先の検索
1: search(n):とした R*-tree (Bucket の併合は行わないもの)，QTree を用いた．なお，QTree は併合時に用いる評価関数に提案方式のエ2: ret = {Φ}3: stack = {root}

ラー増加率 ∆E と同じものを用い，エントリ数の上限 bmax を

4: /* 探索 */提案方式のエントリ数と同じ値にした上で挿入に要した時間を

5: while stack.size() > 0 do

比較した．

6:

P ⇐ stack.shift()

7:

i⇐0

入するデータ数を変えながら評価を行った結果を示す．Ej は

8:

while i < P .child.size() do

0.0001 とした．後に Ej を変えた場合の評価結果を示している．

9:c ⇐ P .child.get(i)10:

if getOverlap(c,n) > 0 then11:

if c は Bucket である then
if !ret.contains(c.peerID) then12:

ret.add(c.peerID)13:

end if

14:

else

15:

stack.add(c)16:

end if17:
18:

end if

19:

i⇐i+1

20:

end while

21: end while

データ挿入時の評価結果を以下の図 4-7 に示す．まず，挿図 4，5 がデータセットにジオタグつきツイートデータを用いた場合の評価結果であり，図 6，7 がデータセットに一様乱数を用いて生成したデータを用いた場合の評価結果である．
図 4 より，挿入するデータ数が多いほど，挿入に要した時間が増加しているが，増加率が小さくなっていることが分かる．
これは，木構造の深さがデータ数の対数に比例するためである．
また，挿入データ数が少ない場合には，提案手法で挿入に要した時間は他の手法より少し短くなっている．これは，提案手法
では，Bucket の併合によりエントリ数を削減できるためである．しかし，挿入データ数が多くなると，どちらの方式もエントリ数が増加し，削減量が小さくなっている．さらに，図 5 よ22: return ret

り，提案手法では，Bucket の併合によってエントリ数が削減

23: endされていることが分かる．その一方で，図 7 のように，一様乱数を用いて生成したデータを用いた場合は，併合が行われにく

5. 性 能 評 価
提案手法の有用性を確かめるためにデータの挿入と検索に関する性能評価を行った．本章ではその方法と結果について述べる．

く，提案手法のエントリ数は，他の手法と同じ程度になっている．これは，一様にデータが分布するために，都市部にデータが集中するツイートデータに比べてデータの分布が疎になり，

Bucket の併合が行われにくいためと考えられる．
Ej の値を変えながら評価を行った結果を図 8-11 に示す．一5. 1 評 価 手 法

例として，挿入データ数は 10000 とした．図 8，9 がデータセッ

性能評価を行うために，Java を用いて提案する空間インデッ

トにジオタグつきツイートデータを用いた場合の評価結果であクス構築手法を実装した．性能評価には，CPU が Intel(R)り，図 10，11 がデータセットに一様乱数を用いて生成したデーCore(TM) i7-3770 CPU @ 3.40GHz，メモリが 8GB の Cen-タを用いた場合の評価結果である．

tOS 6.3 で動作する計算機を用いた．

実データを用いた場合には，Ej が小さな値でも併合が行わ100000

100

80
エントリ数 (×103)

挿入に要した時間(ms)

90
10000

1000

100

70
60
50
40
30
20

R*‑treeusing bucket
proposal method

R*‑treeusing bucket
proposal method

10

10

0
10

20

30

40

50

60

70

80

90

100

10

20

30

40

50

3

70

80

90

100

3

挿入データ数 (×10 個)
図460

挿入データ数 (×10 個)

挿入に要した時間 (ツイートデータ)

図 7 エントリ数 (乱数データ)

100

900

90
800
挿入に要した時間(ms)エントリ数 (×103)

80
70
60
R*‑treeusing bucket
proposal method

50
40
30
20

700
600
500
400
300
200
R*‑treeusing bucket
proposal method

10
100
0
10

20

30

40

50

60

70

80

90

100

0
0.0001

3

0.001

0.01

0.1

挿入データ数 (×10 個)Ej
図 5 エントリ数 (ツイートデータ)

図8

10000

8000
10000
エントリ数

挿入に要した時間(ms)100000

挿入に要した時間 (ツイートデータ)

1000

6000

4000

100
R*‑treeusing bucket
proposal method

2000
R*‑treeusing bucket
proposal method

10
10

20

30

40

50

60

70

80

90

100

挿入データ数 (×103個)

00.0001

0.001

0.01

0.1

Ej
図6

挿入に要した時間 (乱数データ)

図 9 エントリ数 (乱数データ)

れ，エントリ数，挿入時間を削減できることが分かる．しかし

13 に示す．QTree も bmax を設定することによってエントリ数

一方で，乱数によるデータを用いた場合は Ej の値が小さい時を削減することは可能であるが，図 12，13 に示されるように，には併合が行われないことが分かる．これは，先述したように，

R*-tree を用いる場合に比べて挿入に要する時間がかかること

都市部にデータが集中するツイートデータに比べて一様乱数をが分かる．これは，QTree が Bucket の併合のために優先度付用いて生成したデータの分布は疎であり，併合後の MBR の面

き待ち行列を管理しており，R*-tree に比べ挿入時の計算量が積が大きくなるためである．

大きくなるためである．

さらに，挿入にかかる時間を QTree と比較した結果を図 12，900

1e+007
挿入に要した時間(ms)挿入に要した時間(ms)

800
700
600
500
400
300

1e+006
100000
10000
1000

200

100
R*‑treeusing bucket
proposal method

100
00.0001

QTree
proposal method
10
10

0.001

0.01

20

30

40

50

0.1

60

70

80

90

100

3

挿入データ数 (×10 個)Ej
図 10 挿入に要した時間 (乱数データ)

図 13 挿入に要した時間 (乱数データ)

70
クエリあたりの検索時間(ms)

10000

エントリ数

8000

6000

4000

2000
R*‑treeusing bucket
proposal method
00.0001

0.001

0.01

0.1

40
30
20
10

エントリ数 (乱数データ)

図 14 検 索 時 間

120
送信トラフィック量 (MByte)

1e+006
挿入に要した時間(ms)50

R*‑tree
proposal method01000 2000 3000 4000 5000 6000 7000 8000 9000 10000
各ピアのデータ数

Ej
図 11

60

100000

10000

1000

100
QTree
proposal method

100

80

60

40

20
R*‑tree
proposal method

10
10

20

30

40

50

60

70

80

90

100

挿入データ数 (×103個)
図 12 挿入に要した時間 (ツイートデータ)

5. 2. 2 データ検索の評価結果

01000 2000 3000 4000 5000 6000 7000 8000 9000 10000
各ピアのデータ数
図 15

送信トラフィック量

問合せの範囲内に含まれるモバイルセンサデータを有するセデータ検索に関する性能評価として，検索にかかる時間，イ

ンサネットワーク拠点を正解とし，正解の結果に対する適合率

ンデックスサーバの更新時に発生したトラヒック量，検索精度（問合せ結果の中に含まれる正解の割合）と再現率（正解集合を計測した．問合せは，ユーザが指定した地理的範囲内にモバのうち，問合せ結果が占めている割合）を評価指標として用い

イルセンサデータを有するセンサネットワーク拠点を検索する

た．比較手法には，従来の R*-tree を用いた．

ことを想定した．範囲の指定は正方形により行い，正方形の位

データ検索時の評価結果を以下の図 14-16 に示す．データ

置や大きさを変えながら測定を行った．検索精度に関しては，

セットはジオタグつきツイートデータを用いた．図 14 に示さ

1

[4]

検索精度

0.8

0.6
[5]

0.4

0.2
recallprecision
01000 2000 3000 4000 5000 6000 7000 8000 9000 10000
各ピアのデータ数[6]

図 16 検 索 精 度[7]れるように，提案方式を用いることにより，検索に要する時間を大幅に短縮することができる．また，図 16 から，該当する問合せ先ピアを抽出できていることが分かる．このことから，提[8]案方式では，エントリ数が削減され，既に問合せ先ピアの一覧
としてリストに追加している Bucket との比較回数を削減したことにより，検索に要する時間を短縮できていることが分かる．
また，図 15 に示されるように，提案方式でインデックスを構築することにより，各ピアからインデックスサーバへのデータ
送信量を削減が可能であることが分かる．Bucket の併合が進むと，新しく挿入する Bucket が既存の Bucket に包含される可能性が高くなり，更新情報を送信する頻度が抑えられるためである．

6. お わ り に
本稿では，複数拠点統合型センサネットワーク上で，モバイ
ルセンサデータを効率的に検索するためのインデックスの構築法を提案した．提案するシステムを Java で用いて実装し，性能評価を行った結果，提案手法に基づいて構築されたインデッ
クスサーバに問合わせることにより，従来の R*-tree を用いた手法に比べて高い精度を維持しつつ高速に問合せ先を取得可能であることを確認した．今後の課題として，Top-k クエリへの対応や，時間方向への拡張を考えている．

謝

辞

本研究の一部は，科学研究費補助金基盤研究 (S) (課題番号：

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

献

[1] J. Burke, D. Estrin, M. Hansen, A. Parker, N. Ramanathan,S. Reddy and M. B. Srivastava “Participatory Sensing”, in
Proc. of the 1st workshop on World Sensor Web, pp. 1–5,
Oct. 2006.
[2] T. Das, P. Mohan, V. N. Padmanabhan, R. Ramjee and A.
Sharma “PRISM: platform for remote sensing using smartphones”, in Proc. of the 8th international conference on
Mobile systems, applications, and services, pp. 63–76, June
2010.
[3] K. Aberer, M.Hauswirth, A. Salehi “Infrastructure for Data

[9]

Processing in Large-Scale Interconnected Sensor Networks”,
in Proc. of the 2007 International Conference on Mobile
Data Management, pp. 198–205, May 2007.
T. Yoshihisa, Y. Hamaguchi, Y. Ishi, Y. Teranishi, T. Haraand S. Nishio “A Sensor Data Aggregation System using
Mobile Agents”, Distributed Networks: Intelligence, Security, and Applications, Chapter 2, CRC Press, Taylor andFrancis, pp. 39–65, July 2013.
N. Beckmann, H. Kriegel, R. Schneider and B. Seeger “TheR*-tree: an eﬃcient and robust access method for points
and rectangles”, in Proc. of the 1990 ACM SIGMOD international conference on Management of data, pp. 322–331,
June 1990.
C. Perera, A. Zaslavsky, P. Christen, A. Salehi and D. Georgakopoulos “Capturing Sensor Data from Mobile Phones
using Global Sensor Network Middleware”, in Proc. of theIEEE 23rd International Symposium on Personal Indoor
and Mobile Radio Communications, pp. 24–29, Sep. 2012.
A. Guttman “R-trees: a dynamic index structure for spatial
searching”, in Proc. of the 1984 ACM SIGMOD international conference on Management of data, pp. 47–57, June
1984.
K. Hose, C. Lemke and K. Sattler “Processing relaxed skylines in PDMS using distributed data summaries”, in Proc.
of the 15th ACM international conference on Informationand knowledge management, pp. 425–434, Nov. 2006.
B. Nam and A. Sussman “Analyzing design choices for distributed multidimensional indexing”, The Journal of Supercomputing, vol.59, pp. 1552–1576, Mar. 2012.