E-27

2013 年度情報処理学会関西支部 支部大会

省電力モバイルセンシングのための近隣デバイス間連携機構
A Neighbor Collaboration Mechanism for Energy-Eﬃcient Mobile Sensing
樋口 雄大 † 1† 2
Takamasa Higuchi

山口 弘純 † 1
Hirozumi Yamaguchi

1. は じ め に

東野 輝夫 † 1
Teruo Higashino
センサ情報の収集 /環境情報の発信 (DTN)

携帯電話端末から取得される位置情報やセンサの計測値を

高井 峰生 † 1† 3† 4
Mineo Takai

ローカル
サーバ

3G/WiFi ネットワークを介してサーバ上へ集約することで，

3G/WiFi
ネットワークも併用

インターネット
ローカルネットワーク(Bluetooth)

イベント会場等における混雑度や公共交通機関の運行状況といった環境情報をリアルタイムに認識するモバイルセンシング技術が近年高い注目を集めている [1, 2]．これに伴い，多数のモバイル端末 (ノード) 群から，環境認識に必要なセンサ情報を効率的に収集するための仕組みが求められている．既存のモクラスタ間:DTN によるセンサ情報の集約

バイルセンシングシステムの多くは，サービスに参加するすべ

図1

クラスタ内:
センサ情報の常時共有分散型モバイルセンシングての端末が 3G/WiFi ネットワーク等を介してセンサ情報を定期的にサーバへアップロードすることを想定しているが，こうである．ノード同士が互いの通信範囲内にいる間に確実にデーした集中型のアーキテクチャでは，サーバへ同時に接続可能なタの転送を行い，情報共有の遅延を軽減するためには，各ノーノード数の上限など，スケーラビリティの制約が問題となる．

ドが高い頻度で近隣デバイスの探索を繰り返す必要がある．一また，通信インフラに障害が発生した場合にはシステムの利用

方，デバイス探索の実行には一般に多くの電力が消費されるたそのものが困難になることから，避難支援等の災害時アプリ

め，端末の消費電力を軽減するためには，探索の実行頻度を可

ケーションへの応用が難しいといった課題もある．

能な限り抑えることが望ましい．また，スマートフォン等の市

ノード数に対するスケーラビリティやシステムのロバスト性

販デバイス上でシステムを動作させるためには，デバイスに実を高めるためには，Bluetooth 等の近距離無線通信を用いて近装された無線通信方式の制約を考慮してプロトコルを設計する

隣ノードとの間でローカルにセンサ情報を共有・集約する分散必要がある．例えば，Bluetooth の場合，ピコネット内のデバ

型のアーキテクチャ (図 1) が適していると考えられる．ノーイス数が 8 つに制限されているほか，デバイス探索の実行中

ドの移動によってネットワーク内の接続関係が頻繁に変化する

は他のノードからの探索に対して応答できないといった性質が環境において効率的なデータ配送を行うためには，データを一ある．文献 [3–9] で提案されているような既存の DTN プロト

時的に端末内のローカルなストレージに蓄積し，ノードが移動

コルでは，こうした無線通信の下位層に起因する問題はあまりによって他のノードの通信範囲内に入った時点で転送を行う遅考慮されていないが，特にノード密度が高い環境においては，

延耐性ネットワーク (DTN) のアプローチが有効であることが通信リンクの次数制約や，デバイス探索の同時実行によるノー知られている [3–9]. 各ノードは，DTN を介して近隣ノード

ド間のコンタクト検出率の低下によって通信機会の損失が頻繁との間でセンサデータを共有するとともに，環境内に遍在するに発生し，情報共有の効率が低下する可能性が高い．

デジタルサイネージ等の公共デバイス (ローカルサーバ) の通

本稿では，イベント会場や商業施設など多くの歩行者が往来

信範囲内を通過した際に，集約したセンサ情報をローカルサーする環境において，モバイル端末上で定期的に発生するセンサ

バへアップロードする．ローカルサーバ上でこれらのセンサ情情報を，DTN を介してモバイル端末間で効率的に共有するた報を分析し，環境認識結果を近距離無線通信やサイネージ等をめのプロトコルを提案する．上記のような環境では，一般に，通じて近隣の群衆へ発信すれば，災害時など通信インフラの利

知人同士の集団や，同じ目的地へ向かう人の流れ等，互いに類用が困難な環境においても，持続的なサービスの提供が可能と似した移動の振る舞いをとる グループ が存在する．提案手法なる．また，インターネットを介してローカルサーバ間を接続

では，ノード間の接続関係の履歴をもとに，こうした群衆内のすることで，より広域の環境情報を提供することもできる．

グループを検出し，同一のグループに属すると推定されるノー

しかし，DTN の仕組みを前述のモバイルセンシングシステ

ド間で連結なネットワーク (クラスタ) を構成する．その上で，ムにおけるセンサ情報の共有に適用するためには，次のような近隣ノードの探索をクラスタメンバ間で協調的に実行するこ

課題を解決する必要がある．1 つは，パケットが宛先ノードへとで，コンタクト検出率を保ちつつ，1 ノードあたりのデバイ

到達するまでの遅延時間と，端末の消費電力とのトレードオフ

ス探索の実行頻度の軽減を図る．また，異なるクラスタに属するノードとの接続状況を常時メンバ間で共有し，クラスタ間に† 1 大阪大学 大学院情報科学研究科
Graduate School of Information Science and Technology, Osaka
University† 2 日本学術振興会 特別研究員 DC
JSPS Research Fellow† 3 Space-Time Engineering, LLC† 4 University of California, Los Angeles

おけるメッセージの送受信を少数の通信リンクへ集約すること
で，ノードの次数制約に起因するメッセージ到達遅延の増加を抑制する．
ネットワークシミュレータ The ONE [10] によるシミュレー
ション実験の結果，すべてのノードがランダムな時間間隔で独立に近隣ノードの探索を繰り返し，検出されたすべての隣接では，ノード群の中から連結な支配集合を発見し，支配ノード

ノードへ接続要求を行った場合と比較して，メッセージの到達のみをルート探索の対象とすることで，ルーティングの探索空率を維持しつつ，各ノードの平均的なデバイス探索の実行頻度間を限定する．ただし，ノードの移動による局所的なトポロ

を 46 % 軽減できることを確認している．

ジの変化を契機として，ネットワーク全体で大規模なクラスタ

2. 関 連 研 究の再構成が生じる場合があることから，ノードのモビリティが高い環境では，一般に十分な性能が得られない．これに対し，

モビリティによってノード間の接続関係が頻繁に変化する非クラスタの維持や再構成のオーバヘッドを抑えた低コストなク

連結なネットワーク上においてメッセージを宛先ノードへと効

ラスタリング手法も提案されている．LCC プロトコル [15] で率的に配送することを目指して，DTN 向けのルーティングプ

は，隣接ノードの中で最小の ID を持つノードがクラスタヘッ

ロトコルが活発に研究されている．Epidemic Routing [3] は，

ドとなることで，1 ホップのクラスタを構成する．ノードの移ノード同士が遭遇した際に，互いのノードが保持するメッセー

動によって 2 つのクラスタヘッドが互いの通信範囲内に入ったジの複製を送受信することにより，ノード間でメッセージの拡場合には，一方のノードがクラスタヘッドの役割を終了するこ散を行う．この方式は，遅延が小さく，またルーティングのたとで，クラスタの統合を行う．3hBAC [16] は，クラスタヘッ

めの事前知識が不要であるという利点があるが，ノード間のド間の最短距離が 3 ホップとなるような重複のないクラスタ

メッセージ転送が高頻度で発生するため，端末の消費電力が大を構成する．クラスタメンバを介してクラスタヘッドと 2 ホッ

きくなるといった課題がある．Epidemic Routing を拡張した

プで通信する “cluster guest” と呼ばれるノードを許容するこ

プロトコルとして，ノード同士の過去の遭遇履歴情報から宛とで，クラスタヘッドと直接通信できなくなったノードのため先ノードへのメッセージ配送確率を算出し，それに基づきメッに新たなクラスタを構成する必要をなくし，クラスタ維持のセージの転送先や送信順序を制御することで，メッセージの複

オーバヘッドを軽減している．また，クラスタの構成時にノー製回数を抑制する手法も提案されている [4–6]．RAPID [7] は，ドの移動特性を考慮することで，クラスタの安定性を高めるア

パケットの複製を行った場合の効用を定義し，単位メッセー

プローチも提案されている．MOBIC [17] は，隣接するノード

ジサイズあたりの効用が最も大きいメッセージから順に送信群に対する相対速度のばらつきが小さいノードをクラスタヘッを行う．効用関数の定義によって，平均/最大遅延の最小化やドとして選択することで，クラスタの再構成の発生頻度を抑メッセージ到達率の最大化など，様々な指標に基づくルーティ

える．MobDHop [18] は，MOBIC のプロトコルを d ホップ

ングの最適化を可能にしている．また，端末のバッテリ残量やに拡張することで，ネットワーク内のクラスタ数のさらなる軽ユーザ間のソーシャルな関係性を考慮して，メッセージの送信減を図っている．MobHiD [19] は，ノードの過去の移動履歴

回数をより効率的に軽減する手法も提案されている [8, 9]．提をもとに将来のモビリティを予測し，将来的に隣接ノード集合

案手法は DTN のルーティングプロトコルと近距離無線通信の変化が少ないと推定されるノードをクラスタヘッドに選択すの MAC/PHY 層の中間でミドルウェアとして動作し，クラる．これらの手法では，クラスタの構成と維持のため，各ノースタの構成やトポロジ管理等を行う．このため，提案手法はドが定期的に隣接ノードの探索を行うことを想定している．特ルーティングプロトコルとは独立であり，上記のような任意のに，ノードのモビリティが高い環境においては，隣接ノード情DTN 向けルーティング手法を適用することができる．

報を最新の状態に保つため，各ノードが高い頻度で近隣デバイ

DTN を支える要素技術として，ノード間のコンタクトを効スの探索を繰り返すことが求められる．一方，1 章で述べた通率的に検出する手法も活発に検討されている．文献 [11] では，り，Bluetooth など，市販の携帯電話端末で利用可能な無線通デバイス探索の実行頻度とコンタクトの検出漏れ率とのトレー信方式では，デバイス探索の実行時に多くの電力が消費される

ドオフを理論解析によって明らかにしている．eDiscovery [12]ほか，探索が完了するまでに長い時間を要するため，隣接ノーは，検出された隣接ノードの数に応じてデバイス探索の実行頻

ド情報の更新頻度に厳しい制約がある．これに対し，提案手法

度を動的に調整することで，コンタクトの検出率を維持しつ

では，隣接ノードの探索をクラスタメンバ間で協調的に行う

つ，省電力化を実現している．これらの文献では，いずれも各ことで，クラスタの構成や維持に要するオーバヘッドの軽減を

ノードがデバイス探索の実行頻度を独立に決定することを想定図っている．なお，本稿では，議論の簡単化のため，過去一定している．これに対し，提案手法では，近隣ノード間で協調的期間のコネクティビティ情報のみを利用してクラスタの構成をに探索のタイミングを決定することで，1 ノードあたりのデバ行うことを想定しているが，MOBIC や MobHiD のように，

イス探索実行頻度のさらなる軽減と，コンタクト検出率の向上

ノード間の相対速度や過去の遭遇履歴情報を活用すれば，情報を図っている．なお，本稿では，それぞれのクラスタが一定の共有の効率をさらに高めることができると考えられる．

時間間隔で近隣クラスタとのコンタクトの探索を行うことを想

MANET 上に存在するすべてのノードに対してメッセージを定しているが，検出された近隣ノードの数等に応じて探索の実

効率的にフラッディングするためのプロトコルについても，様々

行間隔をクラスタ単位で動的に調整すれば，コンタクトの検出な検討が行われている．Multipoint Relaying [20] や Domi-

効率のさらなる向上が期待できる．

nant Pruning [21] では，送信元ノード u の隣接ノードの中か

また，大規模な MANET におけるルーティングのオーバヘッ

ら，2 ホップ以内のすべてのノードを被覆する最小の部分集合

ドを軽減するため，MANET 向けのクラスタリング手法が数多(relay point 集合) をヒューリスティックに選択する．ここで，く提案されている．支配集合に基づくクラスタリング [13, 14]

ノードが被覆されるとは，u が送信したメッセージを，直接ま

0.8

1.0

uj

通信距離 R

0.2

0.4

0.6

ui

図 4 dicoverer によるカバレッジのモデル

0.0

Inquiry success probability

rij

0

2

4

6

8

10

Inquiry time [sec.]
図 2 Inquiry の実行時間と成功率の関係 [23]は，各ノードが高い頻度でデバイス探索を繰り返すことが求められるが，一方で，近隣ノードとの間でデバイス探索の同時実行が発生する可能性も高まるため，各ノードが非同期に探索を実行した場合には，一定の割合で検出漏れが発生する．提案手法では，クラスタメンバ間の地理的な近接性を活用して，図 3

discoverer
クラスタ内の通信リンクを介して検出結果をメンバ間で共有のように，クラスタ内の一部のノードのみがデバイス探索を実行し，その結果をクラスタ内で共有することで，近隣ノードによる探索への応答性を高め，コンタクト検出率の向上を図る．
時刻 t におけるクラスタメンバの集合を M(t)，メンバ

discoverer によるコンタクト検出のカバレッジ
図 3 協調コンタクト検出ui ∈ M(t) の隣接ノード集合を Ni (t) とする．一般に，uiの隣接ノード u ∈ Ni (t) が他のメンバ uj ∈ M(t) にも隣接している確率 P (u ∈ Nj (t)|u ∈ Ni (t)) は，図 4 のように，uiと uj の通信範囲が重なる領域の面積に比例すると考えられる．

たは他ノードによる再送信によって間接的に受信できる状態を

各ノードの無線到達距離を R，ui と uj の間の距離を rij = r

表す．送信ノードによって relay point に選択されたノードのとすると，P (u ∈ Nj (t)|u ∈ Ni (t), rij = r) は式 (1) により与みがメッセージの再送信を行うことで，ネットワーク全体におえられる．

想定しているが，あらかじめノード間で分散的に連結な支配集

P (u ∈ Nj (t)|u ∈ Ni (t), rij = r) =
{
( )
}
r
r√ 2
1
2
2
2R
arccos
−
4R
−
r
(1)
πR2
2R
2

合を求め，送信元ノードによらず，固定の relay point 集合を

ここで，時刻 t において，クラスタ内で n 個のメンバ用いることで，メッセージのオーバヘッドを軽減する手法も提D(t) ⊆ M(t) だけがデバイス探索を実行するような場合を案されている [22]．これらのフラッディングプロトコルでは，考える．なお，本稿では，デバイス探索を行うメンバを dis-

relay point 集合を構成するため，前述のクラスタリング手法

coverer，それ以外のメンバを non-discoverer と呼ぶ．non-と同様，各ノードが隣接ノード集合を定期的に収集する必要が

discoverer ui とクラスタ内の各メンバとの地理的な距離 r がある．本稿では，3 章および 4 章で述べる協調コンタクト検出

確率分布 f (r) に従うとすると，ui の隣接ノード u がクラスタの仕組みによってデバイス探索のオーバヘッドの軽減を図ると内の discoverer uj によって検出される確率 P (Xij ) は式 (2)ともに，理論解析およびシミュレーション実験を通じて，そのにより与えられる．なお，Xij は ui の隣接ノードが uj によっ有効性を示している．

て検出される事象を表すものとする．

ける再送信の回数を軽減している．上記の手法では，送信ノー
ドが relay point 集合の情報をメッセージ内に格納することを

3. 協調コンタクト検出
Bluetooth のデバイス探索では，通信範囲内にいるすべてのノードを高い確率で検出するため，周波数チャネルを高速に切∫ ∞f (rij = r) · P (Xij |rij = r)dr

P (Xij ) =∫ ∞0f (rij = r) · P (u ∈ Nj (t)|u ∈ Ni (t), rij = r)dr

=

(2)

0

り替えながら繰り返し INQUIRY メッセージを送信する．こここで，non-discoverer ui の隣接ノードが，クラスタ内の少なのため，探索中は，他ノードからの INQUIRY に対する応答

くとも 1 つの discoverer によって検出される確率を考える．n率が著しく低下するほか，消費電力が高い状態が持続する．あ個の discoverer を u1 , u2 , . . . , un とし，ui とそれぞれの dis-

るノード ui がデバイス探索を実行した時，ui の通信範囲内

coverer との距離を ri1 , ri2 , . . . , rin とする．また，一般性を失のノード uj が ui の INQUIRY に対して応答できる確率 (探わず，ri1 ≤ ri2 ≤ . . . ≤ rin とする．このとき，ui がいずれか

索成功率) は，ui の探索時間 Td のうち，uj が探索を実行しの discoverer によって検出される確率 P (Xi1 ∨Xi2 ∨. . .∨Xin )ていない時間の長さ Tc (≤ Td ) に依存して決まる．

について，明らかに次の関係が成り立つ．

ここで，Tc とデバイス探索の成功率の関係を図 2 に示す．

P (Xi1 ∨ Xi2 ∨ . . . ∨ Xin ) ≥ P (Xi1 )(3)

探索の成功率は Tc が大きくなるほど増加し，Tc = 5.12 秒でui1 は，n 個の discoverer のうち ui との距離が最も近い

99% に達する．短時間のコンタクトを確実に検出するためにノードである．クラスタメンバとの距離の累積分布関数を

て環境内のすべてのノードへ拡散される．サーバは生成から一0.8定時間内に受信されたセンサ情報のみを用いて環境認識を行う

0.6

ものとし，あらかじめ定められた許容遅延時間を超過したメッ
セージは直ちに破棄されるとする．

0.4

4.2 プロトコルの概要

0.2

提案手法では，同じグループに属すると推定されるノード間
rmax= 5 m
rmax= 10 m
rmax= 15 m
rmax= 20 m

0.0

Neighbor detection probability

1.0

情報 (数十 bytes 〜数 Kbytes) は，ノード間の DTN を介し

1

2

3

4

5

6

7

で連結なネットワーク (クラスタ) を構成し，コンタクトの探索や通信リンクの管理をクラスタ単位で協調的に行うことにより，デバイス探索の実行頻度とリンク確立のオーバヘッドの軽8減を図る．初期状態においてはすべてのノードが自身をクラス

Number of discoverers

F (r) =

図 5 discoverer による隣接ノードの検出率 (理論値)

タヘッド (CH) とするサイズ 1 のクラスタを構成するものと∫r

し，その後は，各クラスタが以下の 3 つのフェーズを繰り返す

0

f (r)dr とすると，最も近くにいる discoverer との距離 ri1 の累積分布関数 F1 (r) は式 (4) で与えられる．

ことで，クラスタの維持とデータの送受信を行う．

(1)

F1 (r) = 1 − P (ri1 > r ∧ ri2 > r ∧ . . . ∧ rin > r)

隣接ノード集合を取得する (図 6 (a))．他のメンバは，= 1 − P (ri1 > r)P (ri2 > r) · · · P (rin > r)
= 1 − {1 − F (r)}n

クラスタ維持フェーズ: CH はデバイス探索を実行し，CH からのデバイス探索に応答するため，検出可能状態(4)で待機する．デバイス探索が完了すると，CH は，検出F1 (r) を距離 r について微分することで，ri1 の確率密度関数

された隣接ノード集合をもとにクラスタメンバを更新す

f1 (r) が得られる．

る．クラスタの構成と維持については 4.3 節で述べる．

dF1 (r)f1 (r) == n {1 − F (r)}n−1 f (r)
dr

(5)

(2)

から自身を含む n 個の discoverer をランダムに選択し，式 (2) および式 (5) を式 (3) へ代入すると，P (Xi1 ∨ Xi2 ∨ . . . ∨ Xin )∫ ∞n{1 − F (r)}n−1 f (r) ·
≥
πR2 0
{
( )
}
r
r√ 2
2R2 arccos−
4R − r2 dr.
2R
2

コンタクト検出フェーズ: CH は，クラスタメンバの中

discoverer 集合 D(t) をクラスタ内へフラッディングする．CH 以外の discoverer はデバイス探索を実行し，近隣クラスタとのコンタクトを検出する (図 6 (b))．

(3)
(6)

discoverer によるコンタクト検出率の特性を調べるため，ク
ラスタメンバとの距離が (0, rmax ) の一様分布に従うと仮定した場合の P (Xi1 ∨ Xi2 ∨ . . . ∨ Xin ) の下限を，式 (6) により算出した．無線通信距離 R は Bluetooth を想定して 10m とし，rmax を 5 〜 20m，discoverer の数 n を 1〜8 の間でそれぞれ変化させた．このとき，non-discoverer の隣接ノードがクラスタ内のいずれかの discoverer によって検出される確率の下限を図 5 に示す． rmax = 5m の時には，クラスタメン
バのうち 1 つのノードがデバイス探索を行うことで，他のメンバの隣接ノードも 84% 以上の確率で検出可能であることが分かる．このように，クラスタメンバの中で一部のノードのみ
がデバイス探索を実行することで，コンタクト検出率を保ちつ
つ，各メンバの平均的なデバイス探索の実行頻度を軽減することが可能である．メンバ間の距離が離れるにつれて検出漏れの発生頻度が増加しているが，この場合には，discoverer の数 nを増やすことで，検出率を高めることができる．なお，本稿では経験的に n = 2 とする．

通信フェーズ: discoverer は，クラスタ外の隣接ノードに対して接続要求を行い，互いのクラスタが保持するデータを送受信する (図 6 (c))．他クラスタからの接続要求への応答性を維持するため，クラスタ間の通信リン
クは，データの送受信が完了した時点で切断される．また，他クラスタから受信したデータおよびクラスタメン
バによって新たに取得されたセンサ情報は，クラスタ内のネットワークを介して即時にメンバ間で共有される．

4.3 クラスタの構成と維持
クラスタ維持フェーズでは，CH u0 がデバイス探索を実行し，近隣ノードに対して INQUIRY メッセージをブロードキャストする．INQUIRY を受信した近隣ノード ui は，自身と同一のクラスタに属するすべてのメンバの ID を格納した INQUIRY RESPONSE メッセージを u0 に対して返答する．これにより，CH u0 は，現時刻 t における隣接ノード集
合 N0 (t) と，各隣接ノード ui ∈ N0 (t) が属するクラスタのメンバ集合 Mi を取得することができる．なお，2 つの隣接
ノード ui , uj ∈ N0 (t) が同一のクラスタに属している場合には，Mi = Mj となる．Bluetooth では，デバイス探索に対する応答メッセージの中に，最大 2,048 バイトのデバイス名

4. プロトコル設計
4.1 想 定 環 境
各ノードは，加速度センサ等の内蔵センサから一定時間ごとに計測値を取得し，特徴量の抽出などアプリケーションに応じた前処理によってデータサイズの圧縮を行う．圧縮後のセンサ(任意の文字列) を格納することができる．このエントリにク
ラスタメンバの ID 情報を含めることで，新たなコネクションを確立することなく，デバイス探索と同時に近隣のクラスタ情報を収集することが可能となる．
このフェーズでは CH のみがデバイス探索を実行するため，

クラスタ内リンク (Bluetooth)
INQUIRY メッセージINQUIRY̲RESPONSE メッセージ
C3
C2

discovereru0 (CH)

C1

u0
(CH)

クラスタ間リンク
(DTN)
u0
(CH)

discoverer(a) クラスタ維持フェーズ(b) コンタクト検出フェーズ
図6(c) 通信フェーズ

プロトコルの動作例

クラスタ内のメンバは高い確率で INQUIRY メッセージに応BERSET UPDATED メッセージとしてクラスタ内へフラッ

答することが可能である．一方，ノードがデバイス探索や通ディングすることで，クラスタメンバに対してクラスタ内の信を行うタイミングはクラスタごとに独立に決定されるため，

ネットワークトポロジの更新を促す．

異なるクラスタに属するノードは，u0 と同時にデバイス探索

4.4 クラスタ間の通信リンクの管理を実行している可能性がある．前述の通り，隣接するノードがデバイス探索完了後，discoverer ui ∈ D(t) は，クラスタ外

同時にデバイス探索を実行した場合には互いの検出が困難との隣接ノード uj ∈/ Mi に対して接続要求を行う．これらの通なるため，こうしたクラスタ外の隣接ノードに対しては確率信リンクを通じて uj から受信したメッセージ，およびクラス

的に検出漏れが生じる．CH がクラスタの維持を行う際には，タメンバによって新たに取得されたセンサ情報は，クラスタ内

隣接ノードの検出漏れによってクラスタの安定性が低下するのネットワークを介して，直ちに他のメンバと共有される．こことを防ぐため，過去 W ラウンドの隣接ノード集合の履歴のため，クラスタ内のいずれかのメンバが，近隣クラスタとの< N0 (t), N0 (t − t1 ), . . . , N0 (t − tW −1 ) > を用いて，式 (7) に間で 1 本の通信リンクを確立すれば，互いのクラスタ内で保より，現在の隣接ノード集合 N0 (t) を補完する．

持するすべての情報を送受信することが可能である．

N0′ (t) = N0 (t) ∪ N0c (t)(7)
ここで，N0c (t) は，過去 W ラウンドのうち ⌈W/2⌉ 以上のラ収集した隣接ノード集合 Ni (t) および隣接ノード uj ∈ Ni (t)ウンドで検出された隣接ノードの集合とする．なお，本稿ではが属するクラスタのメンバ集合をもとに，接続すべき隣接クウインドウサイズを W = 3 とする．

ラスタの集合 Qi = {Mj |∃ uj ∈ Ni (t) ∩ Mj } を求める．そdiscoverer ui ∈ D(t) は，コンタクト検出フェーズにおいてデバイス探索が完了すると，CH は，隣接ノード集合の履歴の上で，それぞれの隣接クラスタ Mj ∈ Qi から，ui 自身とに基づき，クラスタのメンバを更新する．提案手法では，すべ隣接しているメンバ uk ∈ Ni (t) ∩ Mj を 1 つずつ選択し，そてのクラスタメンバ ui ∈ M0 が式 (8) の条件を満たすようにれらのノードに対して接続要求を行う．このとき，同一のク

メンバの追加と削除を行う．

ラスタに対して複数のメンバが接続要求を行うことを防ぐた∀ ′t ∈ (t − T, t]; ui ∈ N0′ (t′ )(8)め，次のような排他制御を行う．ui が隣接ノード uk への接続要求を行う際には，クラスタ内へ LOCK(uk ) メッセージを

ここで，T はノードのモビリティの特性に応じて決まるパラ

フラッディングする．これにより，他の discoverer は，uk とメータである．式 (8) より，u0 を CH とするクラスタに属す同一のクラスタに属する隣接ノードへの接続要求を一定期間抑ることができるのは，過去 T 秒以上にわたって u0 との隣接制される．uk との間で通信リンクの確立に成功すると，ui は関係が持続しているノードのみである．以上の定義に基づき，

CONNECTED(uk ) メッセージをクラスタ内へフラッディン

CH は下記の手順でクラスタのメンバ集合を更新する．

グする．CONNECTED(uk ) を受信すると，discoverer は，接

(1)

(2)

クラスタメンバ集合 M0 の中で，最新の隣接ノード集

続すべき隣接クラスタの集合 Q から uk が属するクラスタを合に含まれないノード ui ∈/ N0′ (t) は，式 (8) の条件を削除する．uk への接続が失敗した場合には，ui は Ni (t) ∩ Mk

満たさないため，メンバ集合から除外する．

に含まれる他のノードへの接続を試みる．以上により，隣接すクラスタメンバ以外の隣接ノード ui ∈/ M0 の中で，ui

るクラスタとの間で 1 組ずつ通信リンクが確立される．

が属するクラスタ Mi のすべてのメンバが式 (8) の条件を満たす場合には，M0 に Mi のすべてのメンバを追加することで，2 つのクラスタをマージする．
以上により，現在のラウンドにおける新たなメンバ集合 M′0が得られる．最後に，CH は変更後のメンバ集合 M′0 を MEM-

4.5 クラスタ内ネットワークの維持
Bluetooth では，1 つのピコネットに接続できるノード数に上限があるため，クラスタ内ネットワークを構成する際には，最小限のリンク数で連結なトポロジを実現できることが望ましい．そこで，提案手法では，クラスタ内において，CH を根ノードとするツリー状のネットワークを維持する．初期状態

表 1 シミュレーション結果 (Proposed/n=2)においては，すべてのクラスタは根ノードのみからなるサイデバイス探索実行間隔

ズ 1 のネットワークを構成する．クラスタのマージを行う際

平均メッセージ到達率には，CH u0 が，マージ先のクラスタの CH に対して接続要

1 ノードあたりの平均リンク確立頻度65.1 sec
57%
0.026 /sec.

求を行い，u0 自身がマージ後のクラスタの CH となる．また，また，あるノードからクラスタ内のメンバへの通信リンクが一定数を超えた場合には，ネットワークトポロジの再構成を行
い，ノードのリンク次数を軽減する．ノード u が 6 つ以上の隣接ノードを持つとき，それらの隣接ノードの中には，互いに隣接関係にあるノードが少なくとも 1 組存在する (これらをv, w とする) [24]．u は，v − w 間のリンク確立を促した後，

0.6
0.4

メンバとの通信リンクを切断した上で，自身を CH とする新たなクラスタを構成する．

Contact detection ratio

ラスタメンバ集合に自ノードが含まれない場合には，すべてのProposed
Naive (15 sec)

0.0

スタ内のネットワークを修復する．一方，CH から受信したク

0.2

身と非連結な他のメンバに対して接続要求を行うことで，クラ

0.8

1.0

ツリー上の親ノードとの通信リンクが切断された場合には，自

0

20

40

60

80

100

Contact duration time [sec]図 7 コンタクト検出率v または w とのリンクを切断することで，自身のリンク次数を軽減する．このように，クラスタメンバとの通信リンクの数を高々5 つに制限することで，他のクラスタのノードからの接続要求への応答性を維持する．

5. 性 能 評 価

バイス探索の持続時間は 5.12 秒とする．
なお，The ONE の MAC/PHY 層は，ノードの通信距離と通信速度のみを考慮した抽象モデルで実装されているが，本実
験では，デバイス探索による近隣ノードの検出率を文献 [23]のモデルに基づき確率的に決定することで，Bluetooth の特性

5.1 シミュレーション環境を再現している．また，各ノードの最大リンク次数は 7 とし，提案手法の有効性を評価するため，ネットワークシミュレー

接続要求を行ってからノード間で通信が開始するまでの間に

タ The ONE [10] によるシミュレーション実験を行った．シは，2 秒間の遅延が生じるものとした．

ミュレーション領域のサイズは 50m×50m とし，ノード数は以上の環境のもとで 3,600 秒間のシミュレーションを行い，100 とする．各ノードは，10 ノードからなるグループを構成し，提案手法の性能を，すべてのノードが Tinq ± 5 秒のランダム

以下のようなモビリティモデルに従って，フィールド内をラな時間間隔でデバイス探索を実行し，検出されたすべての隣接

ンダムに移動するものとする．まず，Reference Point Group

ノードに対して通信リンクの確立を試みるシンプルな通信プロ

Mobility モデル [25] と同様，各グループの平均的な振る舞い

トコル (Naive) と比較した．なお，Tinq は各ノードによるデを表す 10 個の参照点を作成する．それぞれの参照点は，Ran-

バイス探索の実行間隔の平均値を表すパラメータとする．

dom Waypoint モデルに従ってフィールド内を独立に移動す

5.2 シミュレーション結果

る．移動先の waypoint はフィールド内からランダムに選択さ5.2.1 コンタクト検出率

れ，参照点は目的地に向かって一定の速度で移動する．このとノード間のコンタクトの持続時間とコンタクト検出率の関き，移動速度は (vmin , vmax ) の一様分布からサンプリングす係を図 7 に示す．複数のノードが同時にデバイス探索を実行

る．vmin , vmax はそれぞれノードの最小・最大速度であり，本した場合に互いの検出率が著しく低下するという Bluetooth稿では vmin = 0.5 m/s，vmax = 1.5 m/s とする．目的地のの特性により，Naive において，すべてのノードが平均 15 秒

waypoint に到着すると，参照点は最大 120 秒間静止した後，間隔でデバイス探索を繰り返した場合にも，一定の割合でコ

次の目的地への移動を開始する．グループの参照点が次の目的

ンタクトの検出漏れが発生している．提案手法では，少数の地を選択すると，そのグループに属するノードは，参照点が選

discoverer のみがデバイス探索を実行するため，探索の空間

択した waypoint を中心とする半径 3m の領域内から自身の的なカバレッジは Naive に比べて低下するものの，近隣ノー

行き先 waypoint をランダムに選択する．以上により，各ノードとの間で探索の同時実行が発生する頻度が軽減されるため，

ドは，グループの参照点を中心として，集団的に振る舞う．

discoverer の通信範囲内に存在するノードは高い確率で検出す

各ノードは，10 秒間隔で，すべてのノードを宛先とする 2KB

ることができる．その結果，Naive と比較して，短時間のコンのメッセージ (センサ情報) を生成し，Epidemic Routing プロ
トコルによって，ノード間でメッセージを拡散する．メッセー

タクトをより高確率で検出することが可能となっている．

5.2.2 メッセージ到達率

ジの生存期間 (TTL) は 60 秒とし，生成から 60 秒以内に宛先提案手法によりノード間でセンサ情報の拡散を行った場合の，ノードへ到達したメッセージを配送成功と定義する．ノード間

1 ノードあたりのデバイス探索実行間隔，各ノードが DTN をの通信は Bluetooth v2.1+EDR を想定し，通信距離は 10m，介して許容遅延時間以内に収集することができたメッセージの通信速度は 2Mbps とする．また，それぞれのクラスタは 10〜

割合 (メッセージ到達率)，および 1 ノードあたりの接続要求

20 秒のランダムな間隔でコンタクト検出を行うものとし，デの実行頻度の平均値を表 1 に示す．また，Naive において，各

60
40
0

20

Number of Clusters

80

100

1.0
0.8
0.6
0.4

Message Delivery Ratio

0.2
0.0
15

25

35

45

55

65

0

Average Device Discovery Intervals [sec]
図 8 メッセージ到達率 (Naive)

1200

1800

2400

3000

3600

Simulation Time [sec]図 10

クラスタ数の時間変化

1.0

繰り返され，クラスタ数は 10 〜 20 の範囲に収束する．クラ

0.8

スタ内ではメンバ間の通信リンクを介してセンサ情報が即時に共有されるため，87% のメッセージが 5 秒以内の遅延時間で0.6

サーバへ到達している．一方，全シミュレーション時間を通したクラスタ数の平均値は 14.3 となり，サーバとのコネクションの総数は，すべてのノードがサーバと直接通信を行う集中

0.4

Probability

600

0.2

型のアーキテクチャと比較して，平均 86% 軽減されている．
また，60 秒以内にサーバへ到達するメッセージの割合は 94%

0.0となっており，高いデータ収集率が実現されていることが分か
0

10

20

30

40

50

60

Message collection delay [sec]
図 9 メッセージ収集遅延時間

ノードによるデバイス探索実行間隔の平均値 Tinq を 15 〜 65

る．以上のように，ノード間におけるローカルな情報共有が，ノード数に対するスケーラビリティの向上にも寄与することを確認している．

6. ま と め秒の間で変化させた場合のメッセージ到達率を図 8 に示す．提

本稿では，通信リンクの管理やコンタクト検出を近隣ノード

案手法では，60 秒以内に宛先ノードへ到達したメッセージの間で協調的に行うことにより，モバイル端末上で定期的に発生割合が 57% となり，Naive においてすべてのノードが平均 35するセンサ情報を，DTN を介して群衆間で効率的に共有する

秒間隔でデバイス探索を繰り返した場合と同等のメッセージための手法を提案した．シミュレーション実験の結果，すべて配送性能が得られることが分かった．一方，Naive では，Tinqのノードがランダムな時間間隔で独立にデバイス探索を実行が長くなるにつれて許容遅延時間内に宛先へ到達するメッセー

し，検出されたすべての隣接ノードへ接続要求を行う場合と比ジの割合が徐々に低下しており，各ノードのデバイス探索の実

較して，メッセージ到達率を維持しつつ，各ノードの平均的な行間隔を提案手法と同等の 65 秒とした場合には，メッセージ

デバイス探索の実行頻度を 46% 軽減できることを示した．ま

到達率が 49% まで低下している．このように，提案手法では，た，各クラスタの CH が保持するメッセージを 3G/WiFi ネッ

通信リンクの管理やコンタクト検出をクラスタメンバ間で協トワークを介してサーバへ集約した場合，すべてのノードが直調的に行うことにより，同等のデバイス探索実行頻度で，メッ接サーバとの通信を行う集中型のアーキテクチャと比較して平セージ到達率を 16% 改善することができている．なお，ノー

均的な通信リンクの数を 86% 軽減しつつ，87% のメッセージ

ド間のコンタクトが即時に検出され，通信リンクの次数制約がを 5 秒以内の遅延時間で収集できることが分かった．

存在しないと仮定した理想的な通信環境におけるメッセージ到

ノード群から位置情報や音声等のセンサ情報を収集する際，達率は 73%となった．

互いに地理的に近くにいるノードから取得される情報は，一般

5.2.3 データ収集率に，高い類似性を有すると想定される．このため，クラスタメ

最後に，各クラスタの CH が 3G/WiFi ネットワークを介

ンバ間でセンシングの実行タイミングをスケジューリングすれして自身が保持するメッセージをサーバへアップロードするとば，センサ情報のカバレッジを維持しつつ，各ノードによるセ

仮定し，メッセージが CH を介してサーバに到達するまでのンシングの実行頻度を軽減し，さらなる省電力化を実現するこ

遅延時間の分布を評価した結果を図 9 に示す．また，ノードとが可能になると考えられる．今後は，センサの計測値の特性群によって構成されたクラスタの総数の時間変化を図 10 に示

や端末の残余電力等を考慮してメンバ間で効率的なセンシング

す．初期状態においてはすべてのノードが自身を CH とするのスケジューリングを行うための手法の検討や，センサ情報のサイズ 1 のクラスタを構成するため，合計 100 個のクラスタ

集約・圧縮による通信トラフィックの軽減等に取り組んでいくが構成される．その後，時間の経過とともにクラスタの統合が予定である．

参 考 文 献
1) Weppner, J. and Lukowicz, P.: Bluetooth based collaborative crowd density estimation with mobile phones,
Proceedings of the 11th International Conference on
Pervasive Computing and Communications (PerCom’13), pp.193–200 (2013).
2) Zhou, P., Zheng, Y. and Li, M.: How long to wait?:
predicting bus arrival time with mobile phone based
participatory sensing, Proceedings of the 10th International Conference on Mobile Systems, Applications andServices (MobiSys ’12), pp.379–392 (2012).
3) Vahdat, A. and Becker, D.: Epidemic routing forpartially-connected ad hoc networks, Technical report(2000).
4) Lindgren, A., Doria, A. and Schelén, O.: Probabilistic
routing in intermittently connected networks, SIGMOBILE Mob. Comput. Commun. Rev., Vol.7, No.3, pp.
19–20 (2003).
5) Burgess, J., Gallagher, B., Jensen, D. and Levine,B.: MaxProp: Routing for Vehicle-Based DisruptionTolerant Networks, Proceedings of the 25th IEEE International Conference on Computer Communications(INFOCOM ’06), pp.1–11 (2006).
6) Burns, B., Brock, O. and Levine, B.: MV routing andcapacity building in disruption tolerant networks, Proceedings of the 24th Annual Joint Conference of theIEEE Computer and Communications Societies (INFOCOM ’05), Vol.1, pp.398–408 (2005).
7) Balasubramanian, A., Levine, B. and Venkataramani,
A.: DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM ’07), pp.373–384 (2007).
8) Leguay, J., Friedman, T. and Conan, V.: Evaluating Mobility Pattern Space Routing for DTNs, Proceedings of the 25th IEEE International Conference on
Computer Communications (INFOCOM ’06), pp.1–10(2006).
9) Musolesi, M., Hailes, S. and Mascolo, C.: Adaptive
Routing for Intermittently Connected Mobile Ad Hoc
Networks, Proceedings of the 6th IEEE International
Symposium on World of Wireless Mobile and Multimedia Networks (WOWMOM ’05), pp.183–189 (2005).
10) Keränen, A., Ott, J. and Kärkkäinen, T.: The ONE
Simulator for DTN Protocol Evaluation, Proceedings ofthe 2nd International Conference on Simulation Tools
and Techniques (SIMUTools ’09) (2009).
11) Wang, W., Srinivasan, V. and Motani, M.: Adaptive
contact probing mechanisms for delay tolerant applications, Proceedings of the 13th annual ACM international conference on Mobile computing and networking(MobiCom ’07), pp.230–241 (2007).
12) Han, B. and Srinivasan, A.: eDiscovery: Energy eﬃcient device discovery for mobile opportunistic communications, Proceedings of the 20th IEEE International
Conference on Network Protocols (ICNP ’12), pp.1–10(2012).
13) Wu, J. and Li, H.: On calculating connected dominating set for eﬃcient routing in ad hoc wireless networks,

Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing andcommunications (DIALM ’99), pp.7–14 (1999).
14) Chen, Y.P. and Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks, Proceedings of the 3rd
ACM international symposium on Mobile ad hoc networking and computing (MobiHoc ’02), pp. 165–172(2002).
15) Chiang, C.-C., Wu, H.-K., Liu, W. and Gerla,
M.: Routing in Clustered multihop, mobile wireless networks with fading channel, Proceedings of theIEEE Singapore International Conference on Networks(SICON ’97), pp.197–211.
16) Yu, J. and Chong, P. H.J.: 3hBAC (3-hop between adjacent clusterheads): a novel non-overlapping clustering
algorithm for mobile ad hoc networks, 2003 IEEE Pacific Rim Conference on Communications, Computersand signal Processing (PACRIM ’03), Vol. 1, pp. 318–
321 (2003).
17) Basu, P., Khan, N. and Little, T.: A mobility based
metric for clustering in mobile ad hoc networks, Proceedings of International Conference on Distributed
Computing Systems Workshop, pp.413–418 (2001).
18) Er, I. and Seah, W.: Mobility-based d-hop clustering
algorithm for mobile ad hoc networks, Proceedings ofIEEE Wireless Communications and Networking Conference 2004 (WCNC ’04), Vol.4, pp.2359–2364 (2004).
19) Konstantopoulos, C., Gavalas, D. and Pantziou, G.:
Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction, Comput.
Netw., Vol.52, No.9, pp.1797–1824 (2008).
20) Qayyum, A., Viennot, L. and Laouiti, A.: Multipoint
relaying for flooding broadcast messages in mobile wireless networks, Proceedings of the 35th Annual HawaiiInternational Conference on System Sciences (HICSS’02), pp.3866–3875 (2002).
21) Lim, H. and Kim, C.: Flooding in wireless ad hoc networks, Computer Communications, Vol.24, No.34, pp.
353 – 363 (2001).
22) Wu, J. and Li, H.: A Dominating-Set-Based Routing
Scheme in Ad Hoc Wireless Networks, Telecommunication Systems Journal, Vol.3, pp.63–84 (1999).
23) Peterson, B., Baldwin, R. and Kharoufeh, J.: Bluetooth Inquiry Time Characterization and Selection,
IEEE Transactions on Mobile Computing, Vol.5, No.9,
pp.1173–1187 (2006).
24) Zaruba, G., Basagni, S. and Chlamtac, I.: Bluetrees– scatternet formation to enable Bluetooth-based ad
hoc networks, Proceedings of the IEEE International
Conference on Communications (ICC ’01), Vol.1, pp.
273–277 (2001).
25) Hong, X., Gerla, M., Pei, G. and Chiang, C.-C.: A
group mobility model for ad hoc wireless networks,
Proceedings of the 2nd ACM International Workshop
on Modeling, Analysis and Simulation of Wireless andMobile Systems (MSWiM ’99), pp.53–60 (1999).