ノードが休止する無線センサネットワークにおける高信頼性通信と時刻同期の提案
2007MI048 平松 孝基
指導教員

1 はじめに
近年，無線センサを利用し情報を収集，処理をする無線センサネットワークが注目されている．このシステムは省エネルギー管理，居住環境，自然保護，健康管理，交通状況などのモニタで利用される．しかし，無線センサは電源の供給ができないので，電力消費を抑えシステムの長寿命化をすることが重要となる．そのため，特定のノードを休止させるなどして電力の消費を抑えることを考えなくてはならない．また，監視カメラなどのセキュリティシステムやスケジューリングされた処理をするプログラムでは時刻同期が取れた情報が重要となる．もし時刻同期がされていない場合，セキュリティシステム
では，いつの情報か分からず信頼性に欠け，スケジューリング処理では，正確な時刻にプログラムが処理されなくなる．この問題を防ぐために時刻同期の取れたネットワークを構成する必要がある．
本研究は，過去の修士論文 (2011 年発行)[4] の引き継ぎである．先行研究 [4] では，過去の研究の end-to-endの通信成功率を上げることを目標にし，ルーティング方式を新たに作成し比較をした．しかし，ルーティングの実装方法に問題があり，信憑性の高い結果が得られない状態である．
そこで本研究では先行研究の 50 ノード以下の小規模ネットワークを用いて先行研究のルーティング方式を改良し，通信成功率，信頼性の向上を目指す．そして新たに時刻同期機能を追加し，正確なデータを処理するネットワークを作成する．本研究におけるネットワーク寿命の定義は先行研究と同じく無線ノードが一つでも通信不可能 (電池切れ) となる場合ネットワーク寿命とする．これを GINE (Goto’s IP Network Emulator 以下GINE[2]) によるエミュレーションによって評価する．
本研究で休止状態での時刻同期の実装が成功すれば，省電力を考えつつ正確なデータ通信をすることができると予想される．主に平松が時刻同期，石田がルーティングを担当する．

2 システムの概要
本節では，本研究の対象でもある無線センサネットワークの特徴を述べ，システムの構成を述べる．また，本研究では，先行研究のネットワーク構成，ノードの仕様を引き継ぎ，新たなルーティング方式と休止があるシステムでの時刻同期の実装を提案する．

2008MI067 石田 純平

後藤 邦夫
ネットワーク構成
先行研究では，集合住宅を想定したネットワークを構成した．それに加えて，世の中には様々な建物が存在することを考え，本研究では新たにオフィスビルを想定したネットワークを構成した．条件は次の通りである．

2.1

1. 先行研究のネットワーク• 集合住宅におけるセキュリティシステムなどのネットワーク• ネットワーク中の任意のノードを基地局として外部ネットワークに接続し，外部データ送信• 住宅内のネットワークでは隣接ノード間で通信を繰り返すことで end-to-end の通信を確立
先行研究における条件• 無線通信においてデータを送信する際に，端末間の距離が遠すぎると通信ができなくなるので，隣接端末間を 10m に設定
2. 本研究で追加したネットワーク• オフィスの省エネ化システムのネットワーク• 20 階建てのオフィスビルを 5 階毎に区切り，最下層にある１つのノードを基地局とし外部ネットワークに接続し，外部データ送信• オフィス内のネットワークでは隣接ノード間で通信を繰り返すことで end-to-end の通信を確立
本研究における条件• 条件は先行研究と同じであるが階層の違う端末間を 5m に設定
ノードの仕様ノードの仕様について表 1 のようにパラメータを設定する．各値は一般的な無線端末を参考にした値である．

2.2

表112345678

ノード仕様

休止時
受信待機時
受信時
送信時
バッテリ容量
通信速度
送信データ
ビーコン（送信間隔）

1.2µA 程度
1.2mA 程度
25mA 程度
20mA 程度
7560mAh 程度
100kbps100bytes
40octets (3.5sec)

1 から 4 の値が単位時間毎に減っていく．バッテリ容量が 0 になるまでの時間をネットワーク寿命とする．想定している無線ノードは低機能をコンセプトとしデータ通信，ビーコン送信の 2 種類を有している．ビーコン送
信はビーコン送信をしたノードがビーコンを受信ノードに対してデータ受信可能ということを知らせるためのものである．データを送信するノードはビーコンの発信源を宛先としてデータを送信する．

3 実験のモデル実験で利用するモデルは先行研究と同じ集合住宅におけるネットワークシステム (図 1) と，本研究では他の様々な建物を想定して新たに作成したオフィスビルにおけるネットワークシステム (図 2) とする．
先行研究の集合住宅について説明する．図 1 中の四角内の数字はノード ID を示している．ノード 25 を基地局としてグローバルネットワークに接続する．各ノード
は 1 日 1 回基地局と通信する．
globalnet
1m
2526272829301920212223241314151617187891011125m

23454 ルーティング
本研究では RIP と，先行研究でも利用されたフラッディングを応用した 2 種類の方法で高信頼性, 省電力を目指す．
4.1 RIP の応用
RIP をもとにしたルーティング方式を提案している.
経路決定の基準は最短ホップ数の経路を選択することである. さらにスリープ機能の追加し, インターフェース
メトリックを通信距離に加えることで消費電力の偏りをなくしている. ルーティングは以下のような流れになる.

1. インターフェースメトリックの値は (最大電力/電力残量)-1 の整数部分
2. 各ノードが隣接ノードに自分の持つ経路情報を定期10m1たものである．このビルを 5 階ずつに区切り，それぞれ１つの基地局を設置する．この基地局が外部ネットワー
クと通信をする．5 階ずつに区切る理由は，基地局との距離が遠くなるからである．ノードが遠くなると到達するまでの経由地点が多くなり，通信の成功率が格段に下がってしまう．
図 2 中の丸はノードの位置を表している．建物の中心にはヴォイドコア（吹き抜け）が通り抜けておりその両側に階段がある．中心の二重丸は各区切りの最下層にだけ存在し基地局を示している．

6

的に送信

3. RIP では経路情報をブロードキャストするが, この方式では各隣接ノードに個別に送信

図1

集合住宅の例

次にオフィスビルについて説明する．
20m20mofficeoffice10office

510office10問題点として遠いノードからビーコンを受信して隣接ノードとして認識した場合, 中継を依頼すると成功率が低下することがあげられる．このような問題に対処するために一定時間更新がない経路はルーティングテーブルから削除する．また，経路を設定し最短距離でデータを送信した場合，途中で通信が失敗するとそこでデータを損失してしまう．そこでデータ損失に対処するため，別ルートでのデータ送信をすることで目的ノードへの通信成功確率を向上させる．図 3 のように second route を作成する．2 つの同じデータが目的地へ向かう．
first route(meeting)(meeting)void

10
stairs15m

officesecond routeoffice(meeting)

EV EV(meeting)

10m
図2

オフィスの例：平面図

図 2 は 20 階建てビルの一部を切り出した図である．
この図は一般的なビルの平面図を参考にし独自に作成し

図 3 RIP データの流れフラッディング
先行研究で考察されたフラッディングの概要は次のようになっている.

4.2

1. データ送信回数を増やして end-to-end の通信成功率の向上を目指す

2. 50 ノード以下の小規模ネットワークにおいて, ノードは通信の際に一意に通信するノードを決めるのではなく, 起動しているすべての隣接ノードに送信したいデータを送る
3. ノードの状態には大きく分けて sleep 状態と通信可能状態がある
4. 通信可能状態にあるノードのうちデータ受信待ちの場合はその状態を隣接ノードに伝えるためビーコンを送信する
5. データ送信待ちのノードは受信したビーコンを送ってきたノードに対して送信する
本研究ではノードが複数のデータを保持できるように仕様を変更する．
図 4 はフラッディングでのデータの流れを表している．データは様々な方向に送信されながら目的地を目指す．

図4

フラッディングデータの流れ

5 時刻同期
本節では，時刻同期の必要性，時刻同期技術の種類，時刻同期方法について述べる．
5.1 時刻同期の必要性
監視カメラなどのセキュリティシステムやスケジューリングされた処理をするプログラムでは時刻同期が取れた情報が重要となる．もし時刻同期がされていない場
合，セキュリティシステムでは，いつの情報か分からず信頼性に欠け，スケジューリング処理では，正確な時刻にプログラムが処理されなくなる．本研究では，バッテリ駆動を想定して実験をするため，消費電力が少なく同期精度の高い同期手法を選択する必要がある．
5.2 時刻同期技術の種類
時刻同期技術には次の 5 種類ある．

• システム– GPS (Global Positioning System)• プロトコル– NTP (Network Time Protocol)– RBS (Reference Broadcast Synchronization)– TPSN (Timing-sync Protocol for Sensor Network)– FTSP (Flooding Time Synchronization Protocol)
送信側
send

accesstransmission

伝播時間
reception

受信側

図5

receive

遅延発生の原因

ノード間で通信をするときには，図 5 の中にある
send，access，transmission，reception，receive によって遅延が発生してしまうため，いかにこの 5 種類の遅延と電力消費を抑えられるかが重要となる．時刻同期手法
としてよく知られている GPS や NTP は，電源の制約やノードの多様性を持つ無線ノードに対しては最適ではない．そこで本研究では，上の 3 つの中で一番同期精度が高く 5 種類の遅延の影響を受けにくい FTSP を利用し時刻同期をする．しかし，先行研究のノードの仕様ではノードが休止状態である場合，なにも情報を受け付けないことになっているため，休止状態における時刻同期方法を考える必要がある．

5.3 Flooding Time Synchronization Protocol
FTSP は送信側と受信側で図 5 の transmission，reception 時にタイムスタンプを取る．これにより，一方向の同期パケット送信のみで精密な同期を実現，図 5 のsend，receive，access における遅延を無視することが可能となる．この性質を利用し同期パケットのフラッティングによるネットワーク全体の同期もできる [3]．また，送信ノードのタイムスタンプを T 1，受信ノードのタイムスタンプを T 2，無線の通信速度を speed とすると，時刻の補正値 θ は，θ = T1 − T2 −1speed(1)によって求められる．式 (1) で求められた θ を複数回取得し，平滑化することで，図 5 における transmission お
よび reception 時の遅延を減らすことが可能となる．
FTSP を MICA に実装した結果，約 1µs の同期精度が確認されている [1]．
5.4 時刻同期方法
図 6 は時刻同期における状態遷移図である．本研究では使わないノードを休止させることで電力の消費を抑えているので，ノードが休止している状態でも時刻を同期させることを考えなければならない．そこで本研究では仕様を変更しネットワーク全体で時刻同期する際に，意図的にすべてのノードを時刻同期 START 状態に移行する．そして，時刻同期をし終えた段階で元が休止状態であったノードを再び休止状態に戻す．

時刻同期表 3 は FTSP を用いた時刻同期の実験結果である．

6.2

表3

実験環境
近距離同期精度
遠距離同期精度

not xmittime outSTARTbeaconxmit

some times sync & not xmit

ENDtimesync

同期結果

1対1
5µs
12µs

住宅

オフィス

2ms
5ms

5ms
20ms

data
receive wait

1 対 1 では，目標となる 10µs の同期精度に近くなり，住宅モデルやオフィスビルモデルでは，ms 程度の同期精度となった．この同期精度なら，監視カメラ程度のシステムに対しては実用可能である．しかし，1 対 1 通信
では µs の同期精度となっているのに対し，住宅，オフィ
スでは ms 程度の同期精度になってしまったので，同期方法を見直して精度を向上させる必要がある．

data
arriveneedxmit

data
receivingdata
xmit waitbeaconarrivedataxmittime out

図 6 時刻同期状態遷移図

本研究では実験環境の仕様上，各オブジェクトに現在時刻のタイムスタンプを格納する now-time 変数を持たせる．また，時計のずれの主な原因でもある drift を 1
日 8 秒前後ずれる様に表現した．各オブジェクトは時刻同期後 now-time 変数に同期されたタイムスタンプを格納する．受信側は受信直後に現在持っているタイムスタンプから現在時刻のタイムスタンプを図 7 のように取得し，２つのタイムスタンプを利用して時刻同期する．
現在時刻を知りたい

node 1
gettimeofday(1)gettimeofday(2)

本研究では RIP，フラッディングを利用した無線通信と時刻同期の提案し，GINE を用いて実装した．RIP，フラッディング，時刻同期の各振る舞いをするクラスの作成は完了し，実験結果を得ることができた．しかしend-to-end の通信が確実にできるとは言えない状態である．また現時点では最終目標である時刻同期機能の組み込みに至ることはできなかった．今後の課題として，• end-to-end の通信の確立• 時刻同期機能の組み込み• 時刻同期精度の向上

時刻同期完了後タイムスタンプをnow_timeに格納

7 おわりにtimeという点があげられる．

この間にdriftを足していく

参考文献

図 7 現在時刻の取得方法

6 実験
本節では先行研究の集合住宅とオフィスビルのルーティング，時刻同期のついて述べる．
6.1 ルーティング
RIP，フラッディングそれぞれの振る舞いをするクラスを作成し各モデルで実験をした．RIP ではデータの送信失敗が多く，通信のできないノードが存在するという問題点が残った．フラッディングは全ノードと通信が可能である．表 2 は住宅モデルを利用した実験結果である．送信回数よりも通信のタイミングが重要であると判明した．
表2

住宅モデルの実験結果

送信回数

3回

5回

10 回

1 日の平均消費電力

9.106 mAh
7 ノード

9.279 mAh
12 ノード9.366 mAh
15 ノード

平均通信成功ノード数[1] Maroti, M., Kusy, B., Simon, G. and Ledeczi, A.:
The ﬂooding time synchronization protocol, SenSys ’04 Proceedings of the 2nd international conference on Embedded networked sensor systems,ACM Press, pp. 39–42 (2004).
[2] Sugiyama, Y. and Goto, K.: Design and Implementation of a Network Emulator using Virtual
Network Stack, Proc. of the Seventh International
Symposium on Operations Research and Its Applications (ISORA2008), Lecture Notes in Operations Research, Vol.8, pp. 351–358 (2008).
[3] 鈴木 誠，猿渡 俊介，南 正輝，森川 博之：無線センサ
ネットワークにおける時刻同期技術の研究動向，技術報告，東京大学 先端科学技術研究センター 森川研究室 (2008).
[4] 泉井 雄仁：省電力端末を用いた無線センサネット
ワークにおける高信頼通信の提案，修士論文，南山大学 大学院 数理情報研究科 (2011).