近接作用に基づいた 自律分散クラスタリングにおける 消費電力量とデータ

2013/5/24
近接作用に基づいた
自律分散クラスタリングにおける
消費電力量とデータ転送効率の評価
○濱本 亮 †
会田 雅樹
††
高野 知佐
石田 賢治
†
†
† 広島市立大学大学院 情報科学研究科
† † 首都大学東京大学院 システムデザイン研究科
5月 情報ネットワーク科学研究会
Table of Contents
I. 研究背景
II. 近接作用に学ぶ自律分散的構造形成技術
III. 反応拡散方程式を用いたBio-inspired方式
IV. 階層ルーティングプロトコル Hi-TORA
V. シミュレーションによる評価
VI. まとめ, 今後の課題
2
Ⅰ. 研究背景
これまで…
– 近接作用に基づく自律分散制御の枠組みを研究
• 自律分散構造形成技術の提案
• アドホックネットワークにおけるクラスタリングの実現可能性
の検討
クラスタ
ノード
3
研究目的
検討したクラスタリング (提案方式) における
クラスタ構成時の消費バッテリー量についての評価
データ転送を考慮した評価は不十分
濱本 他, “消費電力とデータ転送効率に
基づく自律分散的に構成したクラスタの
評価，” 信学技報， IN-2012-179
クラスタのデータ転送効率と
消費バッテリー量共に考慮した特性評価
4
Ⅱ. 近接作用に学ぶ自律分散クラスタリング
• 提案方式のクラスタリング
– ネットワーク内にいる各ノードは分布量: q(x,t) を保持
• 実際には各ノードの電池残量の割合値など
– 分布の山を自律分散的に形成
• 隣接ノード間で分布量をやりとり
• 拡散方程式の解をさらにくりこみ変換した式を利用
分布の山の範囲 : クラスタ
分布の山の極大値 : 代表ノード
クラスタID
となるノード
q
代表
ノード
ノードID
5
分布量 q の時間発展方程式
分布量
ドリフト項
拡散項
c: 分布の変化の速さ，σ2 : 収束する正規分布の分散
(なお
)
: 逆拡散係数
6
Ⅲ. 反応拡散方程式を用いたBio-inspired方式
• 生物学的アプローチによる自律分散クラスタリング
(比較対象)
– 反応拡散方程式によるTuringパターンを利用
– 反応拡散方程式: 動物の皮膚模様の形成過程を説明する
際に用いられる数学モデル
Turingパターンの例
• 各ノードは活性因子 (a) と不活性因子 (h) を表す値を保持
• 2つの値の変化を連立微分方程式で表現
– 両者の値のバランスで分布の山を自律分散的に形成
7
活性, 不活性因子の時間発展方程式
活性因子
不活性因子
c, ρ0, ρ1: 因子の増加に関するパラメータ
μ, ν : 因子の減少に関するパラメータ
Da, Dh: 因子の拡散速度に関するパラメータ
8
構成したクラスタの比較 (提案, Bio-inspired)
100
分
布
の
山
t=0
t = 10000
初期分布量
(初期因子量)
代表ノード
100
50
50
0
0
ク
ラ
ス
タ
t = 100000
50
100
0
0
100
100
50
50
0
0
50
提案
100
0
0
50
100
50
100
Bio-inspired
9
提案方式とBio-inspired方式の違い
① パラメータの数
– 提案方式: 3つ (c, σ2, κ’)
– Bio-inspired方式: 7つ (c, μ, ν, ρ0, ρ1, Da, Dh)
② 構成されるクラスタ
– 提案方式は初期状態に応じたクラスタ構成
– Bio-inspired方式は初期状態によらずほぼ同じ形
10
Ⅳ. 階層ルーティング Hi-TORA
• 階層ルーティング(クラスタベースルーティング)の一種
– クラスタ内: リンクステート (最小ホップ)
– クラスタ間: クラスタをノードとみなしてTORAを適用
• 受信クラスタ（受信ノードが存在するクラスタ）に近い順に
heightを設定
– 受信クラスタのheight = 0
• 送信クラスタ (送信ノードが存在するクラスタ)は
より小さいheightを持つクラスタにデータを転送
– 同じheightならよりクラスタIDが小さいクラスタに転送
• 階層化の実現
– 提案方式
– Bio-inspired方式
11
Hi-TORAによるルーティング例
6
D
10
2
S
14
12
9
1
3
8
4
5
15
7
11
height
=1
クラスタB
height
=2
クラスタA
ノード
境界ノード
13
height
=0
クラスタC
代表ノード
12
Ⅴ. シミュレーションによる評価
• 次に挙げる3点をそれぞれの方式で構成した
◎ノード数を変化
クラスタについて評価
・ノードの平均移動速度を変化
1. クラスタ構成時のノードの生存率の時間変化
– 生存率[%] = (生存ノード数 / 全ノード数)×100
2. クラスタ構成時のFND時間
バッテリー残量>0
であるノード
– FND (First Node Die) 時間
– ネットワークが起動してから最初のノードが
バッテリー残量 = 0 になるまでの時間
3. sinkノードが収集したパケット数
13
実験環境 (ノード数を変化)
パラメータ
数値
ネットワーク
1,000m×1,000mのUDG
ノード数
101～501台 (うち1台: sinkノード)
ノードの平均移動速度
1.3m/s （sinkノードは固定）
移動方式
Random direction model
ノードの通信可能距離
250m
sinkノードの座標
(500m, 500m)
シミュレーション時間
20,000sec （約5時間30分）
シミュレーション回数
30回 (結果は30回の平均)
消費電力量
通信1bitあたり 1μ J
代表ノードの処理1secあたり 0.1μ J
14
ユニットディスクグラフ （UDG）
• ユニットディスクグラフ型ネットワーク
• 通信可能領域が被っていたらノードはリンクを張る
リンク
ネットワーク領域
通信可能半径
通信可能領域
ノード
ノードの初期配置例と初期バッテリー容量
• 初期バッテリー容量: [5, 15]の一様乱数×1J
– 初期分布量, 初期因子量は初期バッテリー容量と同一の値
High
sink
1000[m]
Low
1000[m]
16
その他条件
• sinkノード
– sinkノードは電源接続を仮定（常に稼働）
– パケットを確実に収集
• ルーティング
– クラスタ内: 制御パケット不要
– クラスタ間: 制御パケット必要
• 宛先クラスタに行くまでに通る全クラスタの境界ノードに
制御パケットを飛ばす→height の設定
– ルーティング制御パケットは1パケットあたり8Byte
• 経路の作成のみ制御パケットを使用
17
シミュレーションシナリオ
• 0秒≦ t ≦1000秒
– クラスタ構成のみ
– 毎秒隣接ノードと分布量，因子量を交換
– 1制御パケットあたり8Byte
• 1000秒 < t
– クラスタ構成+ルーティング
– ルーティングの仕様
簡単化のため
コリジョンは
考慮しない
• 各ノードはλ = 0.004の指数分布に従う
時間間隔でデータパケット（1.5kByte）を生成
• sinkノードまでデータパケットをマルチホップで送信
• 経路はデータパケットを送信完了するまで維持
– 送信後は破棄
18
生存率の時間変化についての比較
Alive Node[%]
100
Number of nodes: 101
Number of nodes: 201
Number of nodes: 301
Number of nodes: 401
Number of nodes: 501
90
80
70
Bio-inspired方式
60
0
1000
2000
3000
Time [sec]
Alive Node[%]
100
4000
5000
Number of nodes: 101
Number of nodes: 201
Number of nodes: 301
Number of nodes: 401
Number of nodes: 501
90
80
70
提案方式
60
0
1000
2000
3000
Time [sec]
4000
5000
19
FND時間についての比較
2000
Bio-inspired
11分
Proposed
Time [sec]
1500
6分
1000
5分
4分
3分
500
0
101
201
301
Number of nodes
401
501
20
sinkノードの総受信データ量についての比較
2000
1046pkt
Amount of received data [pkt]
Bio-inspired
Proposed
1151pkt
1047pkt
1500
665pkt
888pkt
1000
500
0
101
201
301
Number of nodes
401
501
21
シミュレーション実験より
• すべての評価項目において提案方式で
構成したクラスタが優位
– 提案方式はBio-inspired方式に比べて
消費エネルギーを抑えてデータ転送可能
• 実験した範囲内のノード数によらず
制御情報量の差
経由するクラスタ数
22
Ⅵ. まとめと今後の課題
• まとめ
– 提案方式とBio-inspired方式でクラスタを構成
生存率の時間変化
FND時間
データ転送効率
に着目した評価
– 提案方式で構成したクラスタが優位であることを確
認
• 今後の課題
– 他の電力消費方式での比較評価
– 消費電力とルーティングを考慮した代表ノードの
選択法を検討
23