Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

目次

センサネットワークの時刻同期手法におけるロバスト性の評価

z 研究の背景z 研究の目的z 評価対象とする時刻同期方式
z シミュレーションによる比較評価
z まとめと今後の課題

牟田園 明†， 菅野 正嗣‡， 村田 正幸††大阪大学‡大阪府立大学

2008/2/23

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

IN研究会

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

センサネットワーク

センサ端末

z 数百～数千個のセンサ端末を配置
z 環境情報を収集

z 不規則な配置
z 追加や故障
z 限られた通信距離z 不確実な通信{温度、湿度、位置、光、音など

z 様々なサービスを提供{環境観測{ホームセキュリティ

2008/2/23

end user2sink node

ロバスト性

sensor nodez バッテリで動く小型の装置
z バッテリの交換は困難
IN研究会

monitoring region

3

2008/2/23

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

IN研究会

4

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

電力消費の抑制

時刻同期の必要性

z スリープ制御

z 電力消費の抑制には時刻情報が必要
z 時刻情報を含むデータの収集{センシングや情報収集に関わらない端末をスリープ

z スケジューリング
{効率の良いデータ収集によりパケットの衝突を防ぐ

z 全ての端末の時刻が同じとは限らない

z クラスタリング{クロック周波数の違い{新規端末の追加{近距離端末との接続により通信距離を低減
z 電力消費は通信距離の2乗に比例

定期的な時刻同期が必要
2008/2/23

IN研究会

5

2008/2/23

IN研究会

61

Advanced Network Architecture Research Grouphttp://www.anarg.jp
http://www.anarg.jp

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

従来の時刻同期手法

研究の目的

z NTP (Network Time Protocol)z これまでの研究の問題点{時刻同期手法の比較評価は十分に行われていない{下位レイヤによる影響が考慮されていない{サーバの時刻にクライアントを同期{同期のとれた複数のサーバが必要

z CSMA/CAによる遅延
z パケット損失

z GPS (Global Positioning System){衛星情報を用いて同期{コストが高いz 対象とする時刻同期手法{自律分散制御方式{集中制御方式

これらの手法はセンサネットワークに適していない
2008/2/23

IN研究会

下位層の影響を考慮しつつロバスト性を比較評価する
7

2008/2/23

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

IN研究会

8

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

PCO [1]
Pulse Coupled Oscillator

PCO
Pulse Coupled Oscillatorz 生物界における同期メカニズムをモデル化

z 自律分散型の時刻同期手法{蛍の発光や心臓のペースメーカ細胞などに着想{近隣の端末との相互作用のみによって同期を達成{パラメータεの設定が重要{ノード間のやりとりにおける遅延が考慮されていない
11ε

状態

状態

刺激
ε

刺激

AA

2008/2/23[1] R. Mirollo and S. Strogatz, “Synchronization of pulse-coupled bilologicaloscillators,” Journal on Applied Mathematics, vol. 50, pp. 1645-1662, Dec. 1990

09

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

位相B

B
01

2008/2/23

位相1IN研究会

10Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

PCO
Pulse Coupled Oscillator

RBS [3]
Reference Broadcast Synchronizationz Reachback Firefly Algorithm [3] により遅延を考慮

z 集中型の時刻同期手法{発火時刻をタイムスタンプに含ませる{相対的な時間をやりとり{高精度の時刻同期を達成

z CSMA/CAによる遅延を受け手に知らせる{発火の影響をスタックに保存
z 一定時間待った後に位相を変化

Phase
is is
0.30.3Phase(1)Phase(1)
is 0.3Cluster time is 0.66.
Offset is -0.14

1

z パケットレベルのPCOを大規模なネットワークに適用

Phase
is 0.9is 0.9
Phase(3)Phase(3)
is 0.9A3d/2

Phase
is is0.8is
Phase(2)Phase(2)0.80.82[2] G. Werner-Allen, G. Tewari, A. Patel, M. Welsh and R. Nagpal: “Firefly-inspired sensor network synchronicity withrealistic radio effects”, Proceedings of the 3rd ACM International Conference on Embedded Network Sensor System,
pp. 142-153 (2005)
2008/2/23

IN研究会

11

[3] J. Elson, L. Girod, And D. Estrin, “Fine-grained network time synchronization using reference broadcast,”InProceedings of Operational Systems and Design Implementation , vol. 36, pp. 147-163, Dec. 2002.

122

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

マルチホップRBSマルチホップRBSz RBSはネットワークの規模の拡張性に欠ける
z RBSをマルチホップ型に拡張

Sink
Cluster head
Gateway node

{ネットワーク全体をクラスタに分割{クラスタごとにRBSを適用

clustering{相対的な同期時刻をマルチホップに伝達{ACKを用いた確実な通信方法によってデータ交換

schedule
information

cluster
information

RBS
RBS
RBS
informationsynchronization
time informationz 計算機上でシミュレーションを行い評価

announceannouncesynchronization

2008/2/23

IN研究会

13

2008/2/23

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

IN研究会

14

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

シミュレーションモデルおよび性能尺度

PCOの状態変位幅εの設定

z 円形状の観測領域に端末をランダムに配置
z CSMA/CAの上位層として時刻同期方式を実装

z εを適切に設定しなければPCOは同期できない

z 評価指標{時刻同期するノードの割合{ネットワーク全体が時刻同期する確率{時刻同期を確立するまでの時間

Time to synchronization [sec]Ratio of synchronized nodesz トポロジに応じた最適な値が存在する
1.00.80.60.4
node50
node100
node200

0.2
0.00.000 0.002 0.004 0.006 0.008 0.010

ε2008/2/23

IN研究会

15

2008/2/23

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp30252015
10

node50
node100
node200

500.000 0.002 0.004 0.006 0.008 0.010

ε = 0.0008

IN研究会

ε16

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

z 端末の通信距離をPCO（50m)、マルチホップRBS(100m)に設定
z 不安定な通信環境においてPCOは有効

1.0

PCO

0.80.6ノード間の強いコネクティビティが必要

0.4
0.2
0.0

マルチホップRBS
050

100 150 200 250 300

Radius of monitoring region [m]2008/2/23

1008060

アクセス遅延の蓄積

40

マルチホップRBS

200

マルチホップRBS

PCO

050

クラスタ内での時刻誤差がマルチホップ
通信により伝播100 150 200 250 300

Radius of monitoring region [m]IN研究会

Probability of synchronizationz PCOは広範囲の観測領域で有効
z マルチホップRBSは短時間で同期可能
Time to synchronization [sec]パケット損失に対するロバスト性

Ratio of synchronization nodes

ネットワークの規模に対する拡張性

1.0

PCO

PCO

0.8

マルチホップRBS

0.6

繰り返し刺激を与え合うことでパケット損失の影響を補う

0.4
0.2
000.10.20.3

0.4

Packet loss rate
17

2008/2/23

IN研究会

183

Advanced Network Architecture Research Group
http://www.anarg.jp
http://www.anarg.jp

まとめと今後の課題
z 下位層の影響を考慮した比較評価{PCO
z無線通信品質によらず安定した性能
z広範囲の観測領域にわたって有効{マルチホップRBS
z限定された条件下で短時間に高精度の同期を実現可能

z 今後の課題{ネットワーク環境に応じたPCOのεの設定{マルチホップRBSに適したクラスタリング手法の検討{電力消費についての評価
2008/2/23

IN研究会

194