早稲田大学大学院 国際情報通信研究科 修士2年 樋口 太祐 佐藤研究室（旧富永研究室） 2017/2/28 MANETにおける確率密度関数を 用いたノードクラスタ化に関する検討 Nodes clustering method which uses probability density function in MANET ‘11/2/3 早稲田大学大学院 国際情報通信研究科 修士2年 樋口　太祐 佐藤研究室（旧富永研究室）

目次 研究背景、目的 既存手法 既存手法の問題点 提案手法 シミュレーション結果 結論、今後の予定 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

研究背景 今日，無線情報通信技術が発達し，様々な研究が行われている． 例.LAN: Local Area Network, MAN: Metropolitan Area Network 様々な端末デバイスに小型の無線機器が搭載され，MANET (Mobile Ad hoc NETwork)が注目されている． MANETは「いつでも」「どこでも」通信可能というユビキタス社会を実現する上で大きな力になる． 3

-> パケットを確実に到達させるためにクラスタ化を行い，リンクの総距離を減らす必要があると考えられる． 研究目的(1/2) MANETでは端末が移動性を有するため，ネットワークが不安定である． 従って，オーバーヘッドが発生してしまう． 送信先ノードが移動し，パケットが到達しない可能性がある． パケットを送信する際はより近くのノードに送信するべきであると考えられる． -> パケットを確実に到達させるためにクラスタ化を行い，リンクの総距離を減らす必要があると考えられる． 　　　　…node 　　　　…link

研究目的(2/2) MANETでノードが存在する場合として以下の2つがある． 本手法では後者，即ち，ある分散値をもったモデルを対象とする． ランダムに存在する場合(Gossipアルゴリズム†等) ノードがある一定の場所にある程度固まっている場合 本手法では後者，即ち，ある分散値をもったモデルを対象とする． †…”Multiscale Gossip for Efficient Decenrealied Averaging in Wireless Packet Networks,” Konstantions I. Tsianos and Michael G.Rabbat

既存手法(1/2): マルチキャストフラッディング すべてのノードがパケットを送信するので，MAENTの中ではパケット到達率は最大であると考えられる． しかし，すべてのノードがパケットを送信してしまうと，ネットワークに負荷がかかってしまう． ->リンクの数，距離を減らす工夫が必要である． d j i b u h a c g f e 5

N N N N 既存手法(2/2): OLSR 2 2 2 F S A H G D B E J C I L K M …Source …MPR WILL_ALWAYS F S A H G D B N N 2 E WILL_HIGH J C WILL_NEVER I N N 2 2 L K M …Source …MPR N

既存手法の問題点 リンクの距離が長くてもパケットを送信してしまうので送信先ノードにパケットが到達できない可能性がある． 各ノードは依然無駄なリンクを有している．特に，送信元ノードは送信可能範囲全てのノードへのリンクを有している． 　　　→これらの問題を解決するためにリンク数を抑え，リンク の総距離（コストと定義）を削減する手法を提案する．

提案手法 既存手法の問題点を解決するために，ネットワーククラスタリングを以下のフローによって行う． 1. 累積密度関数(CDF)作成 2. 確率密度関数(PDF)作成 3. ローカルクラスタ化 4. グローバルクラスタ化 5. クラスタの場合分け

1. 累積密度関数作成 ノードをクラスタ化するために確率密度関数を作成する．そのために，原始関数となる累積密度関数を作成する． X軸の値が大きくなるにしたがってY軸の値が大きくなる． 下図は距離のCDF． Observer 累積密度 距離

1. 累積密度関数作成 位相に関しても同様にCDFを作成する． 累積密度 位相

2. 確率密度関数 累積密度関数(CDF)を微分することによって確率密度関数(PDF)を作成する．本手法では位相のPDFを作成する． probability density function cumulative density function Maximum value

3. ローカルクラスタ化 作成されたPDFのなかで最大値のものを選択し，そのときのX軸の値をθsとし，以下の式で距離依存のクラスタ化を行う． そのときに作成されたクラスタをローカルクラスタとし，Clocalの範囲でクラスタが作成される． その範囲を登録し，ローカルクラスタとして登録する． 既に登録済みだった場合，該当クラスタを飛び越えて，別のクラスタとして登録する． 𝜃 𝑠 − 𝜋 𝑁 < 𝐶 𝑙𝑜𝑐𝑎𝑙 < 𝜃 𝑠 + 𝜋 𝑁

3. ローカルクラスタ化の例: 最大グループ数 = 4 2017/2/28 3. ローカルクラスタ化の例: 最大グループ数 = 4 Probability of density 3 4 3 1 3 4 2 4 3 phase 1 2 3 4 5 6 7 8 1

4. グローバルクラスタ化 作成されたローカルクラスタの中でノードの数が最大のものを選択し，暫定平均ノード数𝐶𝐴𝑣によってクラスタ化する． ローカルクラスタを𝐶𝐴𝑣によって複数登録し，複数（場合によっては1つ）のローカルクラスタをグローバルクラスタ化する． 原則，そのローカルクラスタの隣接するローカルクラスタを同じクラスタとするが， 𝐶𝐴 𝑣 𝑛𝑒𝑤 を超えたらクラスタ化をしない． 𝐶𝐴 𝑣 𝑛𝑒𝑤 はグローバルクラスタ化毎に下記の式で再計算を行う． 𝐶𝐴 𝑣 𝑛𝑒𝑤 =𝐶𝐴 𝑣 𝑜𝑙𝑑 − 𝑛 𝜃 𝑖 −𝐶𝐴 𝑣 𝑜𝑙𝑑 𝑟𝑒𝑚𝑎𝑖𝑛𝐿𝐶

4. グローバルクラスタ化の例: 最大グループ数= 4 2017/2/28 4. グローバルクラスタ化の例: 最大グループ数= 4 Micro Clustering Probability of density 1/4< 1/4< 1 2 3 4 5 6 7 8 1 phase 1 2 3 4 1

4. グローバルクラスタ化の例: 最大グループ数= 4 Macro Clustering Probability of density phase 1 2 3 4 1

4. クラスタ化のイメージ: 最大グループ数= 4 Cluster 1 Cluster 4 Cluster 2 Cluster 3

5. クラスタの場合分け 距離rにおける確率密度関数 位相θにおける確率密度関数 PDF(r) PDF(θ) α γ a b β δ g2 2017/2/28 5. クラスタの場合分け 　　　距離rにおける確率密度関数　　　　　　　　　位相θにおける確率密度関数 PDF(r) PDF(θ) α γ a b β δ 0.5(積分値) 0.5(積分値) 0.25(積分値) 0.25(積分値) 0.25(積分値) 0.25(積分値) ( b , α ) ( b , α ) g2 g2 C_n通り分のクラスタ群が考えられる There are C_n clusters will be consider ( a , β ) ( a , α ) ( a , β ) ( a , β ) g1 g1 G_g1…( a , α ) G_g2…( b , β ) G_g3…( a , γ ) G_g4…( b , δ ) ・・・ G_g1…( a , α ) G_g2…( b , β ) G_g3…( a , γ ) G_g4…( b , δ ) ( a , γ ) ( a , δ ) ( b , γ ) ( b , δ ) ( b , δ ) ( b , γ ) g3 g3 g4 g4 … ノードクラスタ Cluster of Node

5. クラスタ群の予想 expectation of cluster group

シミュレーションモデル，評価項目 Javaで実装した． シミュレーションモデル 評価項目 2次元空間 (800m x 600m)モデルを用いる． ガウシアンに従ってノードが分布する． パラメータは基本的にノード数n=3000, 分散 σ=50を設定する. 評価項目 コスト(リンクの総距離) パケット到達率 min_p… クラスタ群のなかで最小のパターン p_g…パターンpの中のグループ数 n(g_k)…クラスタg_kにおけるノード数 n_l…クラスタg_kにおけるノード G_k…クラスタの重心 d_a,b…aとbの距離

シミュレーションモデル 800m Observer 600m

シミュレーションモデル

シミュレーション結果(1/4) ノード数とコストの関係 コスト[m] ノード数

シミュレーション結果(2/4) 分散値とコストの関係 コスト[m] 分散σ

シミュレーション結果(3/4) ノード数とパケット到達率の関係 パケット到達率 ノード数n

シミュレーション結果(4/4) 分散値とパケット到達率の関係 パケット到達率 分散σ

まとめと今後の予定 既存手法に比べ、総リンク数を最大約43％抑制することができ，分散値が小さいとより総リンク数を抑制できた． パケット到達率は分散値が大きいと，OLSRより劣るが，分散値が小さいとOLSRとほぼ同じ到達率であった． 今後の課題 位相のPDFを中心に使用したが，距離のPDFを使用したらどうなるか評価すべきであると考えられる． 同じ位相上でノードが密集しているときは適切なクラスタ化ができないと考えられるのでPDF値を使用した最適な提案を行いたい． 本手法は最大クラスタが固定値だったが，PDFによって変動する手法も必要であると考えられる．