研究背景

Advanced
NetworkArchitecture
ResearchGroup

ネットワークの大規模化・複雑化

インターネットへの多様なデバイスの接続
WSN，P2Pネットワークでのノード故障，加入や離脱

センサネットワークのロバスト性に見る集中制御と自己組織的制御の違い

集中制御の限界• 全体からの情報収集が困難• 変化し続けるネットワークへ迅速に対応できない• 障害の影響が全体へ波及し得る

木利友一*1， 菅野正嗣*2， 村田正幸*1

自己組織型制御
制御局は存在しない
構成要素は局所的な情報を基に，次の行動を決定する個々の行動が，全体としての望ましい制御として発現

大阪大学*1

大阪府立大学*2

現状の問題点対象とするネットワーク
センサネットワーク

Q. 自己組織型制御は，本当に集中制御より望ましいのか？
自己組織型制御への期待

情報収集用ネットワーク

集中制御に対する優位性は必ずしも自明ではない• 適応性• ロバスト性• スケーラビリティ

2

NS研究会

2007/07/19

ノードが周辺状況をセンシング取得したデータをシンクへ送信

特徴

ノード数はときに数百から数千
故障や電力枯渇，伝送誤りによるネットワークの状況変化両制御手法を比較しないまま一般論としての自己組織型制御の望ましさの概念が定着

サーバ

センサノード研究の目的
ロバスト性という観点で自己組織型制御と集中制御を比較
両制御手法の振る舞いの違いを明らかにする
シンク

観測領域
3

NS研究会

2007/07/19

集中制御:
集中制御: 経路構築
文献[5]を参考にした制御サーバが全センサノードの位置・電力を把握

シンク

4

NS研究会

2007/07/19

集中制御:
集中制御: 故障への対応

サーバ

故障検出
Helloパケットが一定時間届かないと故障と判断

故障からの回復故障通知をシンクまで送信

シンクを基準点としたVoronoi分割でセンサノード
クラスタリング
センサノードからシンクまでの経路を計算

データパケット用の経路を用いる

故障ノードを含まない経路を計算・配布

故障検出

各リンクにコストを設定– 距離に関する増加関数– 残余電力に関する減少関数

故障検出
故障

最小コストパスを使用

経路情報を含むパケット（コマンドパケット）を[5] M. Younis, M. Youssef and K. Arisha:
ブロードキャスト

誤検出への対応"Energy-aware routing in cluster-based
sensor networks", Proc. 10th IEEE
International Symposium on Modeling,
Analysis and Simulation of Computer andTelecommunications Systems (2002)

2007/07/19

NS研究会

故障検出

5

干渉・伝送誤り等によりHelloパケットが届かない可能性
故障と判断したノードからHelloパケットが届くようになると:故障回復通知をシンクまで送信

2007/07/19

NS研究会

61

自己組織型制御:
自己組織型制御: 局所的な情報交換

自己組織型制御:
自己組織型制御: 経路構築
クラスタ内ルーティング

2つの群知能を利用

クラスタリング

ノードが自律的に，次ホップノードを確率的に選ぶ

Ant-based clustering [8,9]クラスタリング
Ant Colony Optimization (ACO) [7]クラスタ内ルーティング

ノードが自律的に，属するクラスタを確率的に選ぶ

確率:
フェロモンの値で定義

確率:
クラスタフェロモンの値で定義– 残余電力
– シンクへの距離– クラスタ内ノードのフェロモン

値が大きいクラスタほど選ばれる確率が高い

値が大きいノードほど選ばれる確率が高い

局所的な情報交換を繰り返しながら実行

hop-by-hopのルーティング

各センサノードが自律的に次の行動を決定
どのクラスタに属すべきかどのセンサノードに中継するべきか

フェロモン: 次ホップノードとしての評価値
クラスタフェロモン: クラスタとしての評価値
Helloパケットによって，周期的に交換
7

NS研究会

2007/07/19

8

NS研究会

2007/07/19

自己組織型制御:
自己組織型制御: 故障への対応

シミュレーションモデル

故障検出

100 m x 100 mの観測領域
300台のセンサノードをランダムに配置
4台のシンクを既定の位置へ配置

集中制御と同じ検出法

Helloパケットが一定時間届かないと故障と判断(25,75)

ns-2を用いたシミュレーション

故障からの回復候補

検出したノードは，故障ノードを次ホップノードの候補から外す

誤検出への対応(75,75)IEEE 802.15.4

Helloパケットを故障検出
受信トラフィック

各センサノードが10秒ごとにデータを送信

故障発生(25,25)

100 m

評価項目

故障と判断したノードからHelloパケットが届くようになると:(75,25)構築される経路の品質
伝送誤りに対するロバスト性
ノード故障に対するロバスト性

再び次ホップノードの候補に入れる(0, 0)
100 m

9

NS研究会

伝送誤りに対するロバスト性
Data collection rate構築される経路の品質
集中制御:
ホップ数と遅延で両制御手法を比較
集中制御:

サーバは全体情報を把握
伝送誤り・故障の無い理想環境下サーバは全体情報を把握
最適な経路構築が可能
最適な経路構築が可能
ホップ数・遅延とも，2つのグラフは似た傾向
自己組織型制御:

自己組織型制御:
ローカルな情報のみ使用
集中制御は値の小さい部分に多く分布
ローカルな情報のみ使用
最適な経路を選ぶことが困難
自己組織型制御はテールが長くなる
最適な経路を選ぶことが困難

Centralized
Self-organized

10.8
0.6
0.4
0.2
00.06
Percentage

Percentage– ホップ数が900を超えるものも確認

0.14
0.12
0.10
0.08
0.06
0.04
0.02
0

BER=1e-5
BER=5e-4
BER=1e-4
BER=1e-5
BER=1e-4
BER=5e-4

0200

0.05

Centralized

0.04
0.03

800

集中制御
立ち上がりが遅い
コマンドパケットの廃棄

Self-organized

0.02

400
600
Time [s]0.0102007/07/19

102030
Hop count

4050
NS研究会

000.1

10

NS研究会

2007/07/19

0.2

0.3 0.4 0.5
Delay [s]

0.6
11

適応の遅さ
一箇所の綻びが全体に波及
2007/07/19

1000

Average data collection rate

2007/07/19

10.8-0.4993log(x)-2.8891

0.6

self-organized

0.4-0.7629log(x)-5.6905
0.2
centralized
0
1.0e-05

1.0e-04

1.0e-031.0e-02

BER

自己組織型制御
BERが高い場合も収集率を維持
個々のパケットの重要性が低い
制御が誤っていても，その影響は限定的高いロバスト性NS研究会

122Data collection rate

センサノード故障に対するロバスト性
特定の座標から半径10 mの円内にあるノードをt=200において同時に故障させる

10.8
0.6
0.4

自己組織型制御:
自己組織型制御:
影響を受けにくい．
影響を受けにくい．
受けても回復傾向を示す
受けても回復傾向を示す
集中制御:
集中制御:
回復することは無い
回復することは無い(20,20)(15,15)(15,15)(25,25)(25,25)(20,20)

0.2
0まとめ

0200

集中制御

400 600 800
Time [s]

故障エリア

集中制御:

無駄の無い経路構築
伝送誤り・ノード故障に対して脆弱– 重要度の高いパケットの存在– 正しい情報が伝わらなければ制御が無力

1000

自己組織型制御

集中制御と自己組織型制御をセンサネットワークのロバスト性という観点で評価

自己組織型制御:
故障通知がシンクに到達していない
正しくない情報を基にした制御100%
たった一つのノード故障でも同様の問題を引き起こし得る遅延の上限が決められない
高いロバスト性– 局所的な情報しか扱わないが故に，影響が局所的

今後の課題

他の制御手法を通した，本結論の一般性の確認
自律分散的な面と集中制御的な面を持つ制御手法の評価

0%

影響を大きく受けるエリア
2007/07/19

NS研究会

13

2007/07/19

NS研究会

14

ご清聴ありがとうございました

2007/07/19

NS研究会

153