Document

MANETにおける確率密度関数を
用いたノードクラスタ化に関する検討
Nodes clustering method which uses probability density
function in MANET
‘11/2/3
早稲田大学大学院国際情報通信研究科修士2年
樋口太祐
佐藤研究室（旧富永研究室）
1/28
目次
• 研究背景、目的
• 既存手法
– Multicast flooding†
– OLSR (Optimized Link State Routing)‡
•
•
•
•
既存手法の問題点
提案手法
シミュレーション結果
結論、今後の予定
†…Young-Bae Ko，Nitin H. Vaidya，“Geocasting in Mobile Ad Hoc Networks
Location-BasedMulticast Algorithms，”Department of Computer ScienceTexas A ＆ M University
‡… T. Clausen and P. Jacquet : Optimized Link State Routing Protocol (OLSR),RFC 3626, 200
2/28
研究背景
• 今日，無線情報通信技術が発達し，様々な研究が行わ
れている．
– 例.LAN: Local Area Network, MAN: Metropolitan Area
Network
• 様々な端末デバイスに小型の無線機器が搭載され，
MANET (Mobile Ad hoc NETwork)が注目されている．
• MANETは「いつでも」「どこでも」通信可能というユビキタス
社会を実現する上で大きな力になる．
3/28
3
研究目的(1/2)
• MANETでは端末が移動性を有するため，ネットワークが不
安定である．
– 従って，オーバーヘッドが発生してしまう．
– 送信先ノードが移動し，パケットが到達しない可能性がある．
• パケットを送信する際はより近くのノードに送信するべきで
あると考えられる．
-> パケットを確実に到達させるためにクラスタ化を行い，
リンクの総距離を減らす必要があると考えられる．
…node
…link
4/28
研究目的(2/2)
• MANETでノードが存在する場合として以下の2つがある．
– ランダムに存在する場合(Gossipアルゴリズム†等)
– ノードがある一定の場所にある程度固まっている場合
• 本手法では後者，即ち，ある分散値をもったモデルを対象
とする．
†…”Multiscale Gossip for Efficient Decenrealied Averaging in Wireless Packet Networks,”
Konstantions I. Tsianos and Michael G.Rabbat
5/28
既存手法(1/2): マルチキャストフラッディング
• すべてのノードがパケットを送信するので，MAENTの中では
パケット到達率は最大であると考えられる．
• しかし，すべてのノードがパケットを送信してしまうと，ネット
ワークに負荷がかかってしまう．
->リンクの数，距離を減らす工夫が必要である．
d
j
i
b
u
h
g
a
c
f
6/28
e
5
既存手法(2/2): OLSR
WILL_ALWAYS
S
F
A
H
G
D
B
N
WILL_HIGH
C
WILL_NEVER
J
I
2
N
N
E
2
L
M
K
…Source
…MPR
N
7/28
既存手法の問題点
• リンクの距離が長くてもパケットを送信してしまうので送信先
ノードにパケットが到達できない可能性がある．
• 各ノードは依然無駄なリンクを有している．特に，送信元
ノードは送信可能範囲全てのノードへのリンクを有している．
→これらの問題を解決するためにリンク数を抑え，リンク
の総距離（コストと定義）を削減する手法を提案する．
8/28
提案手法
• 既存手法の問題点を解決するために，ネットワーククラスタ
リングを以下のフローによって行う．
1. 累積密度関数(CDF)作成
2. 確率密度関数(PDF)作成
3. ローカルクラスタ化
4. グローバルクラスタ化
5. クラスタの場合分け
9/28
1. 累積密度関数作成
• ノードをクラスタ化するために確率密度関数を作成する．そ
のために，原始関数となる累積密度関数を作成する．
• X軸の値が大きくなるにしたがってY軸の値が大きくなる．
• 下図は距離のCDF．
Observer d
3
d5
累積密度
d1
d1
d2
d4
1
d1
d2
d3
d4 d5
10/28
距離
1. 累積密度関数作成
累積密度
• 位相に関しても同様にCDFを作成する．
位相
11/28
2. 確率密度関数
• 累積密度関数(CDF)を微分することによって確率密度関
数(PDF)を作成する．本手法では位相のPDFを作成する．
• CDFが急である程，そこではノードが密集していることを意
味している．そこはPDFの極大値とほぼ同義である．
• PDFの極大値は次のノードクラスタで使用する．
probability density function
cumulative density function
Maximum value
d
dx
12/28
3. ローカルクラスタ化
• 作成されたPDFのなかで最大値のものを選択し，そのときの
X軸の値をθsとし，以下の式で距離依存のクラスタ化を行う．
• そのときに作成されたクラスタをローカルクラスタとし，Clocalの
範囲でクラスタが作成される．
𝜃𝑠 −
𝜋
𝜋
< 𝐶𝑙𝑜𝑐𝑎𝑙 < 𝜃𝑠 +
𝑁
𝑁
• その範囲を登録し，ローカルクラスタとして登録する．
• 既に登録済みだった場合，該当クラスタを飛び越えて，別
のクラスタとして登録する．
13/28
3. ローカルクラスタ化の例: 最大グループ数 = 4
Probability of density
3
4
3
1
3
4
2
4
3
2
1
2
3
4
5
14/28
6
7
8
1
phase
4. グローバルクラスタ化
• 作成されたローカルクラスタの中でノードの数が最大のもの
を選択し，暫定平均ノード数𝐶𝐴𝑣によってクラスタ化する．
• ローカルクラスタを𝐶𝐴𝑣によって複数登録し，複数（場合に
よっては1つ）のローカルクラスタをグローバルクラスタ化する．
• 原則，そのローカルクラスタの隣接するローカルクラスタを同
じクラスタとするが， 𝐶𝐴𝑣𝑛𝑒𝑤 を超えたらクラスタ化をしない．
• 𝐶𝐴𝑣𝑛𝑒𝑤 はグローバルクラスタ化毎に下記の式で再計算を
行う．
𝐶𝐴𝑣𝑛𝑒𝑤 = 𝐶𝐴𝑣𝑜𝑙𝑑 −
15/28
𝑛 𝜃𝑖 − 𝐶𝐴𝑣𝑜𝑙𝑑
𝑟𝑒𝑚𝑎𝑖𝑛𝐿𝐶
4. グローバルクラスタ化の例: 最大グループ数= 4
Probability of density
Micro Clustering
1/4<
1
2
3
4
1/4<
5
6
7
8
1
2
phase
1
2
3
16/28
4
1
4. グローバルクラスタ化の例: 最大グループ数= 4
Probability of density
Macro Clustering
2
phase
1
2
3
17/28
4
1
4. クラスタ化のイメージ: 最大グループ数= 4
Cluster 1
Cluster 4
Cluster 2
Cluster 3
2
18/28
5. クラスタの場合分け
距離rにおける確率密度関数
PDF(r)
a
位相θにおける確率密度関数
PDF(θ) γ
α
b
β
0.5(積分値)
0.5(積分値)
0.25(積分値)
(b,α)
(a,β)
g2
(a,α)
δ
0.25(積分値)
0.25(積分値)
0.25(積分値)
(b,α)
C_n通り分のクラスタ群が考えられる
(a,β)
, β )clusters will be consider
There are( aC_n
g1
G_g1…( a , α )
nd ・・・
G_g1…(
G_g2…( ab , α
β)
Cn  n( a ,!δ )
gk
(a,γ)
G_g2…(
G_g3…( b
a , γβ ))
k 1
ab , γδ ))( b , γ )
G_g4…(
( bG_g3…(
,δ)
G_g4…( b , δ )
g4
… ノードクラスタ
Cluster of Node
19/28

(b,γ)
(b,δ)
g3
5. クラスタ群の予想 expectation of cluster group
g2
g2
g3
g1
g1
g3
g4
20/28
g4
シミュレーションモデル，評価項目
• Javaで実装した．
• シミュレーションモデル
– 2次元空間 (800m x 600m)モデルを用いる．
– ガウシアンに従ってノードが分布する．
– パラメータは基本的にノード数n=3000, 分散 σ=50を設定する.
• 評価項目
– コスト(リンクの総距離)
– パケット到達率
pg n( g k )
Cost  min p (
d
k 1 l 1
Gk , nl
)
min_p… クラスタ群のなかで最小のパターン
p_g…パターンpの中のグループ数
n(g_k)…クラスタg_kにおけるノード数
n_l…クラスタg_kにおけるノード
G_k…クラスタの重心
d_a,b…aとbの距離
21/28
シミュレーションモデル
800m
Observer
600m
22/28
シミュレーションモデル
23/28
シミュレーション結果(1/4)
コスト[m]
ノード数とコストの関係
400000
350000
300000
提案手法(σ=50)
250000
OLSR(σ=50)
提案手法(σ=30)
200000
OLSR(σ=30)
提案手法(σ=70)
150000
OLSR(σ=70)
100000
50000
0
0
500
1000
1500
2000
24/28
2500
3000
ノード数
シミュレーション結果(2/4)
コスト[m]
分散値とコストの関係
300000
250000
提案手法(n=1000)
200000
OLSR(n=1000)
提案手法(n=500)
150000
OLSR(n=500)
提案手法(n=2000)
100000
OLSR(n=2000)
50000
0
0
20
40
60
80
25/28
100
120
分散σ
シミュレーション結果(3/4)
ノード数とパケット到達率の関係
パケット到達率
1
0.9
0.8
0.7
0.6
OLSR
0.5
提案手法
0.4
0.3
0.2
0.1
0
0
200
400
600
800
1000
1200
1400
1600
1800
2000
ノード数n
26/28
シミュレーション結果(4/4)
分散値とパケット到達率の関係
パケット到達率
1
0.9
0.8
0.7
0.6
OLSR
0.5
提案手法
0.4
0.3
0.2
0.1
0
0
5
10
15
20
25
30
35
40
45
50
分散σ
27/28
まとめと今後の予定
• 既存手法に比べ、総リンク数を最大約43％抑制すること
ができ，分散値が小さいとより総リンク数を抑制できた．
• パケット到達率は分散値が大きいと，OLSRより劣るが，分
散値が小さいとOLSRとほぼ同じ到達率であった．
• 今後の課題
– 位相のPDFを中心に使用したが，距離のPDFを使用したらどうな
るか評価すべきであると考えられる．
– 同じ位相上でノードが密集しているときは適切なクラスタ化ができ
ないと考えられるのでPDF値を使用した最適な提案を行いたい．
– 本手法は最大クラスタが固定値だったが，PDFによって変動する
手法も必要であると考えられる．
28/28

Download Report