一般論文

DBSJ Journal, Vol.8, No.4
March 2010

巡回収集ノードによるセンサデータ
ベース構築のためのデータ収集量を考慮した通信方式
Communication Methods for Sensor
Database Construction by Rounding Sink
Considering Amount of Data Collection

センサデータベース
営業所
移動型収集ノード義久 智樹♥

西尾 章治郎♦Tomoki YOSHIHISA Shojiro NISHIO

近年，巡回収集ノードがセンシング領域を巡回しながらセンサからデータを収集してセンサデータベースを構築する研究が盛んに行われている．巡回収集ノードを用いる
ことで，センサネットワークを構築することなくデータを収集でき，大規模なデータ収集が可能になる．これらの研究のほとんどは，各センサから収集するデータ量を考慮していないため，データ収集量の公平性を確保できないという問題があった．そこで本研究では，各センサからのデー
タ収集量を考慮した巡回収集ノードの通信方式を提案する．提案方式では，各センサが保持するデータ量や通信時間に応じて巡回収集ノードが収集するデータ量を決定す
る．評価の結果，提案手法は各センサから収集するデータ量に公平性を与えられることを確認した．
Recently, many researches focus on database
construction by rounding data sink, which collects datafrom sensors while traveling in the sensing field. By
using rounding sink, we can collect sensor data without
constructing sensor networks and can realize
large-scale data collection. Most of these researches
have a problem that the rounding sink cannot collectdata fairly for sensors since these do not consider thedata amount to be collected from each sensor. In thispaper, we propose communication methods forrounding sink considering the amount of datacollection. Our proposed methods calculate the amountof data collection based on the data amount that eachsensor has or the communication time. Evaluation
results demonstrated their abilities to ensure fairness
for the data amount to be collected from each sensor.

1. はじめに
近年のセンシング技術の発達にともない，大規模なセンサデータベースに対する注目が高まっている．温度や映像
といったセンサデータを格納した大規模センサデータベースを用いることで，環境把握や人探しといった応用が可♥正会員 大阪大学サイバーメディアセンター
yoshihisa@cmc.osaka-u.ac.jp♦
監事 大阪大学大学院情報科学研究科
nishio@ist.osaka-u.ac.jp

図1

センサ

建物

信号

巡回収集ノードによるセンサデータベース構築
Fig.1

Sensor Database Construction
by Rounding Sink
能になる．センサデータベースを構築するためには複数のセンサからデータを収集する必要があり，センサネットワークと呼ばれる通信ネットワークをセンサで構築してデータを収集する方式が研究されている．しかし，センサネ
ットワークでは，幾つかのセンサを経由してデータ収集するため，センサが多い場合に通信量が非常に大きくなる．
また，ネットワークを構築するためにセンサが互いの通信範囲内になければならないという問題がある．このため，移動型収集ノードを用いてセンサデータベースを構築する研究が盛んに行われている[1-7]．移動型収集ノードを用いたデータ収集では，センサがある領域を移動型収集ノードが移動しながら各センサからデータを収集する．図1の例では，収集ノードを備えたタクシーが街中を移動し，移動型収集ノードとしての役割を果たしている．タクシー
は営業所を出発して客を乗せ，信号で止まったりしながら移動中に通信できたセンサからデータ収集する．営業終了
後，営業所に戻って収集したデータをセンサデータベースにアップロードする．既に運行しているタクシーやバスを活用することで追加コストを抑えられる．移動型収集ノードには，車やロボット，動物といった幾つかの種類がある
が，本研究ではタクシーのように巡回してからデータをアップロードする巡回収集ノードを用いる．
しかし，このような巡回収集ノードを用いた方式では，
巡回収集ノードが通信とは無関係に巡回しているため，各センサが保持するすべてのデータを通信時間内に収集できない可能性があり，巡回収集ノードは収集するデータを取捨選択する必要がある．巡回収集ノードを用いたデータ
収集では，各センサの保持するデータ量と，通信時間の観点から2種類の公平性を確保することが重要と考える．具体的には以下の状況が考えられる．
z 各センサが保持するデータ量に対して収集するデー
タ量を公平にすることが重要な状況：巡回収集ノードが異種のセンサからデータ収集する場合，データ数が均一になるように，各センサが保持するデータ量に対して収集するデータ量を公平にする．例えば，カメラの静止画
1枚のデータ量は温度センサの1回分のデータ量に比べて多い．このため，収集するデータの個数を等しくする
ため，各センサが保持するデータ量に対して同じ割合でデータ収集する．
z 通信時間の公平性が重要な状況：巡回収集ノードが同種のセンサからデータ収集する場合，各センサからのデータ収集量が均一になるように，各センサとの通信時間

日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月

一般論文
を公平に与える．例えば，温度分布把握専用のセンサデ
ータベースを構築するために巡回収集ノードが温度センサのみからデータ収集する場合，各地点の温度データの収集量を均一にすることが考えられる．
短時間で多くのデータを収集するために幾つかの研究が行われているが，各センサから収集するデータ量を考慮していないため，多くのデータをもっているにも関わらず少しのデータしか収集されず，データ収集量の公平性を確保できないという問題があった．
そこで本研究では，各センサからのデータ収集量を考慮した巡回収集ノードの通信方式を2種類提案する．1つめの提案方式では，各センサが保持するデータ量に対して収集するデータ量の公平性を確保し，もう一方の提案方式では，通信時間の公平性を確保する．これらの提案方式では，巡回収集ノードが周辺のセンサを探索し，発見したセンサの1つと通信する．公平性を確保するために，各センサから収集するデータ量や通信時間に上限を設定し，上限に達す
ると，他のセンサからのデータ収集を試みる．
以下，2章で関連研究を説明し，3章でデータ収集する想定環境を説明する．4章で提案手法を説明し，5章で評価を行う．最後に6章で本論文をまとめる．

2. 関連研究セ ン サ デ ー タ ベ ー ス シ ス テ ム と し て TinyDB[8] やCougar[9]が開発されているが，これらはセンサネットワ
ークを用いており，移動型収集ノードを用いていない．
Shah らは Data MULE と呼ぶ移動型収集ノードを提案している[3]．Data MULE はランダムに移動し，通信範囲内にセンサがあるとデータを収集する．環境内には幾つかのアクセスポイントがあり，通信範囲内にアクセスポイン
トがあると，収集したデータを送信し，データの転送を完了する．データ転送の成功率や消費電力が評価されているが，Data MULE の移動経路選択について議論されていな
かった[4]．そこで Sugihara らは Data MULE の経路選択問題を明確に定義している[5,6]．これら研究では，Data
MULE の経路選択や通信プロトコルを制御できると想定しており，出来る限り短い時間で全てのセンサからデータを収集するための Data MULE の制御方法について議論している．また，MobiRoute[7]では，アンカーポイントと呼ばれる地点を巡回してデータ収集する手法が提案されている．MobiRoute では，巡回や停止といった制御が可能
な巡回収集ノードを想定しており，巡回収集ノードを用いることでセンサの消費電力削減につながることが示されている．
しかし，これらのいずれの研究においても各センサからのデータ収集量が考慮されていない．本論文では，巡回収集ノードがデータ収集量を考慮してデータ収集する点が異なる．

3. 想定環境
3.1 移動型収集ノード
移動型収集ノードには，移動を自由に制御できる種類と制御できない種類のものが考えられる．例えば，人が歩きながらや自転車に乗ってデータ収集する場合，自由に速度を下げたり止まったりできるが，タクシーやバスの場合，信号や客の指定場所，バス停で止まることはできるが自由に止まるといった制御ができない．移動を自由に制御できる場合，止まったりすることで公平性を簡単に確保できる

DBSJ Journal, Vol.8, No.4
March 2010
ため，本研究では，タクシーやバスといった移動を自由に制御できない巡回収集ノードを対象とする．巡回収集ノー
ドは巡回終了後，事務所等で収集したデータをセンサデー
タベースにアップロードする．

3.2 通信方法
巡回収集ノードまたはセンサからデータが送信されると，相手側は通信衝突を回避するためにランダムな時間だ
け待ってから応答を返す．この応答のデータサイズは非常に小さく，送受信にかかる時間は無視できる．ランダムな待ち時間はバックオフ時間と呼ばれ，衝突回避のためによく使われる方法である．待ったにもかかわらず衝突が発生すると，バックオフ時間を更新し，再び更新されたバックオフ時間だけまって返信を行う．
巡回収集ノードは，コストの面から一つの通信モジュー
ルしか備えておらず，同時に一つのセンサとしか通信を行えない．巡回収集ノードは移動しており，通信しているセンサが通信範囲外になると，応答が届かないことから通信範囲外になったと判断し，即座にそのセンサとの通信を終了する．

4. 提案方式
データ収集量を考慮した巡回収集ノードの通信方式を提案する．

4.1 PCDR 方式
PCDR（Polling and Communicate considering Data
Ratio）方式は，収集するデータ量を出来る限り少なくせずに，各センサが保持するデータ量に対して収集するデー
タ量の公平性を確保することを目的とした通信方式である．
巡回収集ノードを用いたデータ収集では，巡回収集ノー
ドはどのタイミングでどのセンサと通信できるかあらか
じめ把握できない．そこで PCDR 方式では，巡回収集ノードが周辺のセンサを探索し，発見したセンサの一つと通信する．公平性を確保するために，各センサから収集するデータ量を計算して最大でこのデータ量を収集すると，通信を終了する．センサが保持するデータ量に対するデータ収集量の割合をデータ収集率と呼ぶ．例えば，センサ i が保持するデータ量を Di，センサ i からのデータ収集量を Ciとすると，データ収集率は Ci /Di になる．巡回収集ノード
が各センサから収集する最大のデータ収集率を限界デー
タ収集率 CDRL (Communication Data Ratio Limit) と呼ぶ．限界データ収集率はすべてのセンサに対して同じ値である．
4.1.1 巡回収集ノードのアルゴリズム
PCDR 方式における巡回収集ノードのアルゴリズムを以下に示す．以下の 3 つのステップで通信を行う．
z 探索
巡回収集ノードがビーコンを送信して周辺のセンサを探索する．ビーコンは探索のための非常にデータサイズの小さいデータである．あるセンサがビーコンに応答すると，巡回収集ノードはそのセンサと通信を試みる．
z 通信開始ビーコンに応答したセンサが通信範囲内になく通信が失敗すると，巡回収集ノードは，探索開始時刻pから探索周期Pまで待ってから再び探索を開始する．すなわ
ち，現在時刻がp+P以下であれば他のセンサの応答を待つ．センサの応答を受信すると，巡回収集ノードはその日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月

一般論文
センサと通信を試みる．通信を開始できると，そのセンサからデータを収集する．
z 通信終了センサi が持つすべてのデータを巡回収集ノードが収集するか，センサが通信範囲から外れる，または次の式が満たされると，そのセンサとの通信を終え，次の探索
周期まで他のセンサの応答を待つ．センサi のデータ収集率をRiとする．
Ri > CDRL（1）
通信終了時点ですでに探索周期を越えていると，通信終了後すぐに探索を開始する．
4.2.2 センサのアルゴリズム
まず，センサはビーコンの到着を待つ．センサがビーコンを受信すると，バックオフ発生器 B を初期化する．バッ
クオフ発生器とは，衝突回避のためのバックオフ時間 b を計算するための値であり，初めは Binitial で与えられる．
B を用いて b は B×r（0< r <1）で与えられる．バックオ
フ時間にはランダムな要素があり，センサ毎に異なるため，衝突回避が可能になる．しかし，それでも衝突が発生すると，バックオフ発生器を更新し，バックオフ時間だけ待ってから返信を行う．バックオフ発生器は Bupdate=2.0×B の計算式にて更新する．Bupdate は更新された B あり，B は更新前の値である．衝突が発生しなければ，センサは巡回収
集ノードに返信する．巡回収集ノードとの通信開始時には，ビーコンの応答と同様にバックオフを用いる．

4.2 PCFC 方式
PCFC （ Polling and Communicate with Fairness
Control）方式は，収集するデータ量を出来る限り少なくせずに，通信時間の公平性を確保することを目的とした通信方式である．
公平性を確保するために，各センサとの通信時間に上限を設ける．この上限を限界通信時間 CTL（Communication
Time Limit）で示す．限界通信時間はすべてのセンサに対して同じ値とする．巡回収集ノードが通信しているセンサとの通信時間が限界通信時間に達すると，そのセンサとの通信を終了する．PCFC 方式では，限界通信時間を調整することで，通信時間の公平性とデータ収集量を制御できる．
センサのアルゴリズムは PCDR 方式と同じであるため，以下に巡回収集ノードのアルゴリズムを以下に示す．
探索，通信開始のステップは PCDR 方式と同じであるが，通信終了のステップで，式（1）とは別に次式を満たすとセンサとの通信を終了する．巡回収集ノードとセンサとの通信時間を Li とする．
Li > CLT（2）
データ収集率ではなく，通信時間に上限を与える点がPCDR方式と異なる．

5. 評価
提案方式を計算機シミュレーションで評価した．

5.1 評価環境
5.1.1 巡回収集ノード
巡回収集ノードは，センサがある領域を巡回し，初めの地点に戻る．巡回の経路として様々な経路が考えられるが，すべての経路を網羅する評価を行うことは経路が無数にあり困難なため，本評価では，図 1 のように四角形を描く
ように巡回するものとする．経路上には信号や前方を横切る物体があり，巡回収集ノードは同じ速度で動き続けられ

DBSJ Journal, Vol.8, No.4
March 2010
速度

最大速度

信号距離
信号停止時間
青信号

赤信号

図2
Fig.2

青信号 時間

巡回収集ノードの速度変化

Change of Velocity for Rounding Sink

表1

シミュレーションに用いたパラメタ

Tab.1 Parameters for Simulation
パラメタ
値
最大速度*
11.1m/sec.
発進時加速度
1.11m/sec.2
停止時加速度
2.22m/sec.2
探索周期，P
0.1sec.
最大サンプリングレート
96bps
256Kbps
通信帯域
10m
通信半径
620usec.
初期バックオフ発生器
3km
経路の 1 辺500m
信号の間隔
60sec.
赤信号の時間るとは限らない．例えば，巡回収集ノードとしてタクシー
やバスを用いる場合，信号で停止することが考えられる．
本評価では，信号で停止することを考え，信号がある度に巡回収集ノードに図 2 に示す速度変化を与える．
センサデータベースへのデータのアップロードは巡回後に行うため時間的な制約は特にない．さらに，一巡する間に各センサが蓄積するデータ量は等しいため，二巡目においても同じ評価結果が得られる．このため，評価では巡回収集ノードが巡回を開始してから一巡するまでのみをシミュレートする．
5.1.2 センサ
センサは巡回収集ノードと通信できる範囲内にランダムに配置されている．各センサは一定のサンプリングレー
トでデータをバッファに蓄えており，巡回収集ノードが一巡する間にセンシングしたデータすべてをバッファに蓄えられるようにサンプリングレートを設定している．評価
では，最大のサンプリングレートを与え，最大サンプリン
グレート以下のサンプリングレートを各センサにランダ
ムに与える．
5.1.3 パラメタ
各方式のパラメタとして，限界データ収集率 CDRL や，
限界通信時間 CTL，探索周期 P がある．
評価に関して，特に明記しない限り表 1 に示すパラメタ
をシミュレーションで用いる．
5.1.4 公平性の定義
本論文では，公平性 Fairness を以下で定義する．
Fairness = 1-Gini（3）
Gini はジニ係数で，ジニ係数は公平性を示すための指標としてよく用いられており，本研究でも利用する[10]．Gini
はローレンツ曲線を用いて計算できる．ローレンツ曲線のx 軸を x，y 軸を y とすると，収集されたデータ量が多い順

日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月

一般論文
CDRL=0.1
CDRL=0.2
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0 (No Control)

Fairness for Collected Data Ratio

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2

Total Collected Data [MBytes]

DBSJ Journal, Vol.8, No.4
March 2010

50

40

30

20

CDRL=0.1
CDRL=0.2
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0 (No Control)

10

0.1
0

0
0

0.05

0.1

0.15

0

0.2

0.05

Density

Fig.3

Fairness for Collected Data Ratioof the PCDR Methodに xN 個のセンサのデータ収集率の合計が yA となる．こ
こで，N はセンサの数，A は全てのセンサのデータ収集率の合計である．特に y=x の直線は均等分布線と呼ばれ，この線よりローレンツ曲線は下側になり，離れているほど不公平であることを示す．Fairness は 0 以上 1 以下の数である．Fairness が大きいほど公平であることを示し，小さいほど不公平であることを示す．ローレンツ曲線が均等分布線と等しく，データ収集率が全て等しい場合にはFairness=1.0 となる．また，ローレンツ曲線が x 軸と等し
く，一つのセンサが収集されたデータ率がデータ収集率の合計と等しく，他のセンサと通信が行われていない場合には，Fairness=0.0 となる．

5.2 密度センサの密度が大きくなると，通信範囲が重なるセンサの数が多くなるため，公平性に影響がでる．そこで，公平性とデータ収集量がどの程度になるか密度を変化させて評価を行った． PCDR 方式におけるデータ収集率の公平性を図 3，データ収集量を図 4 に示す．CDRL は限界デー
タ収集率を示す．CDRL が 1.0 の場合は，提案手法を用いずに，探索できたセンサからすべてのデータを収集するか
通信範囲外になるまで通信する，制御を行わない単純な手法に相当する．
図 3 より，PCDR 方式では，CDRL を調整することで公平性を与えられていることが分かる．また，密度が大きくなるにつれてデータ収集率の公平性が少なくなっている
ことがわかる．これは，多くのセンサがある場合にはセンサの通信範囲が重なり，必ずしもデータ収集率が限界デー
タ収集率になるまで通信できるとは限らないためである．
各センサとの通信にかけられる時間が短くなるほど限界
データ収集率になるまで収集できない確率が高くなるため，密度が大きいほど公平性が減少する．密度が比較的小
さく，巡回収集ノードがセンサからデータを収集していな
い時間がある状況では，上記の理由で密度が大きくなるほ
ど公平性が減少していくため上に凸のグラフになるが，密度が比較的大きく，巡回収集ノードが常にセンサからデー
タを収集している状況になると，密度が増えてもデータを収集されないセンサが増えるだけであるため下に凸となり，公平性が 0 に近づく．
一方，図 4 より密度が大きくなるにつれて全データ収集
量が多くなることが分かる．これは，多くのセンサがある

図4

0.15

0.2

Fig.4
600
500

PCDR 方式のデータ収集量

Total Collected Data of the PCDR Method
CDRL=0.1
CDRL=0.5
CDRL=1.0

60000

CDRL=0.3
CDRL=0.7

400
300
200

40000
30000
20000

100

10000

0

0

Collected Data Ratio

CDRL=0.1
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0

50000

Number of Sensors

PCDR 方式のデータ収集率の公平性

Number of Sensors

図3

0.1

Density

Collected Data Ratio

図 5 PCDR 方式のヒストグラム（左：密度=0.002，右：密度=0.2）
Fig.5 Histograms of the PCDR Method(Left: Density=0.002, Right: Density=0.2)
ほど巡回収集ノードがセンサからデータを収集していな
い時間が少なくなるためである．巡回収集ノードに停止する状態があるため，密度が十分大きくなっても全データ収
集量が緩やかに増えている．
公平性の理解を深めるために，PCDR 方式におけるデー
タ収集率のヒストグラムを図 5 に示す．左側は密度が疎な場合の代表として密度が 0.002 の場合の結果であり，右側は密な場合の代表として密度が 0.2 の結果である．密度が疎な場合には，ほぼ一つの区間（例えば，CDRL=0.5 の場
合，0.4-0.5 の区間）にセンサが多数あり，公平性が大きいことが分かる．一方，密度が密な場合には，0.0-0.1 の区間にセンサが多く，公平性が小さくなっていることが分かる．
0.0-0.1 の区間のセンサのほとんどは巡回収集ノードと全く通信していないセンサであり，密度が大きすぎて巡回収
集ノードがデータ収集できなかったことが分かる．また，ローレンツ曲線を図 6 に示す．横軸はセンサの割合であり，縦軸はデータ収集率の割合である．Perfect Fairness は均等分布線を示す．密度が疎な場合には，いずれの CDRL に
おいてもほぼ Perfect Fairness と等しいローレンツ曲線を描いており，Fairness が 1.0 に近いことが分かる．密度が密な場合には，CDRL が大きくなるほど Perfect Fairness
から離れ，Fairness が小さくなることが分かる．

5.3 PCFC 方式との比較
通信時間を公平にする PCFC 方式における通信時間の公平性を図 7，データ収集量を図 8 に示す．No Control と

日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月

一般論文

DBSJ Journal, Vol.8, No.4
March 2010

0.8
0.7
0.6

Ratio of Collected Data Ratio

Ratio of Collected Data Ratio

CDRL=0.1
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0
Perfect Fairness

0.5
0.4
0.3
0.2
0.1

CDRL=0.1
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0
Perfect Fairness

0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Ratio of Sensors

Ratio of Sensors

Total Collected Data [MBytes]

1

1
0.9

図 6 PCDR 方式のローレンツ曲線（左：密度=0.002，右：密度=0.2）

50

40

30
CTL=0.05
CTL=0.10
CTL=0.20
CTL=0.40
CTL=0.60
CTL=1.00
No Control

20

10

0
0

0.05

Fig.6 Lorenz Curves of the PCDR Method(Left: Density=0.002, Right: Density=0.2)

図8
Fig.8

CTL=0.05
CTL=0.10
CTL=0.20
CTL=0.40
CTL=0.60
CTL=1.00
No Control

0.9
0.8
0.7

80

0.6
0.5
0.4
0.3
0.2
0.1
0
0

0.05

0.1

0.15

0.2

Density

図7
Fig.7

PCFC 方式の通信時間の公平性
Fairness for Communication Timeof the PFC Method

は PCFC 方式を用いない場合の性能で，PCDR 方式の
CDRL が 1.0 の場合に相当する．これらのグラフより，密度が大きくなるにつれて通信時間の公平性が少なくなり，データ収集量が多くなっていることがわかる．これも，PCDR 方式と同じく，密度が大きくなるほどセンサの通信範囲の重なりが多くなるためである．
PCDR 方式と PCFC 方式を比較した結果を図 9 に示す．
横軸は PCDR 方式のパラメタ CDRL である．PCFC 方式のパラメタ CLT は，各 CDRL の値における PCDR 方式とデータ収集率の公平性が等しくなるように設定した．縦軸はデータ収集量を示している．PCFC 方式が途切れているのは，本来データ収集率を考慮していないため，パラメタを調整しても PCDR 方式以上の公平性を与えられない場
合があるためである．このグラフより，PCDR 方式が，同
じデータ収集率の公平性のもとで PCFC 方式よりも多い
全データ収集量を実現していることがわかる．例えば，100㎡に 20 個のセンサがある（密度=0.02）場合，各センサか
ら 6 割のデータを収集するとする（CDRL=0.6）と，PCDR
方式では，公平性は 0.64 になり，36M バイトのデータを収集できセンサデータベースに追加できる．PCFC 方式で0.64 の公平性を実現する場合には 33M バイト程度であり，
PCDR 方式よりも少ない．このため，データ収集率の公平性を確保する場合には PCDR 方式の方が適しているといえる．

Total Collected Data [MBytes]

Fairness for Communication Time

1

0.1

0.15

0.2

Density

PCFC 方式のデータ収集量

Total Collected Data of the PCFC Method
PCDR (Density=0.002)
PCFC (Density=0.002)
PCDR (Density=0.02)
PCFC (Density=0.02)
PCDR (Density=0.2)
PCFC (Density=0.2)

70
60
50
40
30
20
10
0
0

0.2

0.4

0.6

0.8

1

Collected Data Ratio Limit, CDRL

図9
Fig.9

PCDR 方式と PCFC 方式の比較
Comparison with the PCDR Method
and the PCFC Method

5.4 探索周期の影響
探索周期を長くすると，巡回収集ノードがセンサとの通信範囲外になる可能性が高くなるため，データ収集量が短くなる可能性がある．そこで，探索周期について評価を行った．PCDR 方式と PCFC 方式で同様の傾向が見られたため，PCDR 方式のみの結果を図 10 および図 11 に示す．横軸は対数軸である．密度は 0.2 とした．これらのグラフより，探索周期が長くなると公平性，データ収集量ともに短くなっていることが分かる．特に，探索周期が数秒以上になると急激に短くなっている．これは，巡回収集ノードがセンサの通信範囲の直径を移動するのにかかる時間よりも探索周期が長くなると，ビーコンへの応答を受信できなくなる可能性が高くなるためである．巡回収集ノードが最大速度で常に移動しているとすると，この時間は20/11.1=1.8 秒となり，探索周期を 1.8 秒より短くすることが望ましい．

6. おわりに
本論文では，巡回収集ノードによるセンサデータベース
構築のためのデータ収集量を考慮した通信方式を提案した．PCDR 方式は各センサが保持するデータ量に対して収集するデータ量を公平にすることを目的とした方式であり，巡回収集ノードは限界データ収集率までデータ収集す日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月

一般論文

DBSJ Journal, Vol.8, No.4
March 2010

Total Collected Data [MBytes]

Fairness for Collected Data Ratio

1
0.9

CDRL=0.1
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0.01

0.1

1

10

60
50
40
30
20
10

CDRL=0.1
CDRL=0.3
CDRL=0.5
CDRL=0.7
CDRL=1.0

0
0.01

0.1

図 10

図 11

探索周期とデータ収集率の公平性

Fig.10 Polling Interval andFairness for Collected Data Ratio
る．PCFC 方式は通信時間を公平にすることを目的とした方式であり，通信時間の上限である限界通信時間を変えることで通信時間の公平性とデータ収集量を調整できる．評
価の結果，それぞれの手法が各公平性を確保できていることを確認した．また，データ収集率の公平性を確保する場
合には PCDR 方式の方が適していることを確認した．今後，
巡回収集ノードが自由に移動できる場合や，複数の移動型
収集ノードを用いる場合に公平性を確保する方式を考案
する．

[謝辞]
本研究の一部は，科学研究費補助金基盤研究(S)（課題番
号：21220002）および，若手研究(B)（課題番号：21700108）
によるものである．

[文献］[1] Jea, D., Somasundara, A. A. and Srivastava, M.
B.:“Multiple controlled mobile elements (data mules)
for data collection in sensor networks”, Proceedings ofIEEE International Conference on Distributed
Computing in Sensor Systems (DCOSS), pp. 244-257(2005).
[2] Kansal, A., Somasundara, A. A., Jea, D. D.,
Srivastava, M. B. and Estrin, D.:“Intelligent fluid
infrastructure for embedded networks”, Proceedingsof ACM International Conference on Mobile Systems,
Applications And Services (MobiSys), pp. 111-124(2004).
[3] Shah, R. C., Roy, S., Jain, S. and Brunette, W.:“Data
MULEs: Modeling a Three-tier Architecture forSparseSensorNetworks”,
ProceedingsofInternational Workshop on Sensor Network Protocols
and Applications, pp. 30-41 (2003).
[4] Jain, S., Shah, R. C., Brunette, W., Borriello, G. andRoy, S.:“Exploiting mobility for energy efficient datacollection in wireless sensor networks”, Mobile
Networks and Applications, Vol. 11, Issue 3, pp.
327-339 (2006).
[5] Sugihara, R. and Gupta, R. K.:“Scheduling under
Location and Time Constraints for Data Collection in
Sensor Networks”, Proceedings of IEEE Real-Time

1

10Polling Interval, P [sec.]

Polling Interval, P [sec.]

Fig.11

探索周期とデータ収集量

Polling Interval and Total Collected Data

Systems Symposium (RTSS) (2007).
[6] Sugihara, R. and Gupta, R. K.:“Improving the Data
Delivery Latency in Sensor Networks with Controlled
Mobility”, Proceedings of IEEE International
Conference on Distributed Computing in Sensor
Systems (DCOSS), pp. 386-399 (2008).
[7] Luo, J., Panchard, J., Piorkowski, M., Grossglauser,
M. and Hubaux, J.-P.:“MobiRoute: Routing towards a
Mobile Sink for Improving Lifetime in Sensor
Networks”, Proceedings of IEEE International
Conference on Distributed Computing in Sensor
Systems (DCOSS) (2006).
[8] Madden, S., Franklin, M. J., Hellerstein, J. M. andHong, W.:“Tag: A tiny aggregation service for ad-hoc
sensor networks”, Proceedings of International
Symposium on Operating System Design and
Implementation (OSDI) (2002).
[9] Yao, Y. and Gehrke, J.:“The cougar approach to
network query processing in sensor networks”, ACM
SIGMOD Record, 31(3), pp. 9-18 (2002).
[10] Ntarmos, N., Triantafillou, P. and Weikum,
G.:“Distributed hash sketches: Scalable, efficient, andaccurate cardinality estimation for distributed
multisets”, ACM Transactions on Computer Systems(TOCS), Vol. 27, Issue 1, Article 2 (2009).

義久 智樹 Tomoki YOSHIHISA大阪大学サイバーメディアセンター准教授．2005 大阪大学
大学院情報科学研究科博士後期課程修了，博士（情報科学）．
京都大学学術情報メディアセンター助教，カリフォルニア
大学アーバイン校客員研究員を経て現職．センサデータベ
ース，ビデオオンデマンドの研究に従事．日本データベース学会正会員．

西尾 章治郎 Shojiro NISHIO
大阪大学理事・副学長．1975 京都大学工学部卒業．1980
京都大学大学院工学研究科博士後期課程修了，工学博士．
1992 大阪大学工学部教授．大阪大学サイバーメディアセン
ター長，大学院情報科学研究科長を経て現職．データベー
ス，マルチメディアシステムの研究に従事．本学会理事，
監事を歴任．

日本データベース学会論文誌 Vol.8, No.4
2010 年 3 月