メッシュネットワークにおける クラスタリングチャネル割り当て方 式の提案 東京電機大学 情報環境学部 情報環境基盤技術研究室 講演者 松本 太 勝見祐介、冬爪成人.

Presentation on theme: "メッシュネットワークにおける クラスタリングチャネル割り当て方 式の提案 東京電機大学 情報環境学部 情報環境基盤技術研究室 講演者 松本 太 勝見祐介、冬爪成人."— Presentation transcript:

1 メッシュネットワークにおける クラスタリングチャネル割り当て方 式の提案 東京電機大学 情報環境学部 情報環境基盤技術研究室 講演者 松本 太 勝見祐介、冬爪成人

2 メッシュネットワークについ て メッシュネットワークと は バックボーンをメッシュ（マルチ ホップ）ネットワークで構成 ノードごとの役割 メッシュ機能と外部とのゲート ウェイ機能を持つ MPP メッシュ機能とアクセスポイン トの機能を持つ MAP メッシュ機能のみを持つ MP 特徴 自律的にネットワークを形成 各ノードが自律的にネットワー クを形成する MAP-MPP 間で問題が発生 MAP-MPP 間がメッシュネット ワークであるため、不公平問題 や不安定問題などが発生し、通 信性能が著しく劣化 MP MAP MP MPP STA LAN MPP:Mesh Portal Point MAP:Mesh Access Point MP:Mesh Point STA:Station

3 研究目的 メッシュネットワークにおける問題点 不公平問題 セッションが他のセッションに干渉を受け、通信状態が著 しく劣化 十分な帯域の確保が必要 適切なチャネル割り当て手法の検討

4 クラスタリングチャネル割り当て方式の 提案 提案するクラスタリングチャネル割り当て方 式 CGSR をベースとしたアルゴリズムを用いて、自律 的に数ノードからなるクラスタを形成 分割したクラスタごとに最も干渉の少ないチャネル を 割り当て 単純なアルゴリズムで、適切な動的チャネル割り当てが 可能

5 クラスタリングアルゴリズム 隣接ノード情報の取得 自ノード情報を hello パケットに載せ、一定間隔ごとに送信、 隣接ノード情報を取得 各ノードは隣接ノードテーブルを保持 ロールの決定 決定アルゴリズムに LCC(Least Cluster Change) を使用 テーブルを参照し、自律的にロールを決定

6 ノードロールの決定 ノード ID 1 ３ ロール CH 隣接ノード 数 ６ ノード ID 1 ７ ロール CH 隣接ノード 数 ３ RG ノード ID 1 ６ ロール CH 隣接ノード 数 ６ RG 隣接ノードと自ノード情報を交換し、隣接ノード情報を取得する 隣接ノード数が多いほうが Cluster-Head になり、 少なかったほうの Cluster-Head は Regular-Node となる (Highest Connectivity) 隣接ノード数が同じ場合、ノード ID が小さいほうが Cluster-Head になる（ Lowest ID ） Regular-Node クラスタに所属す る 一般ノード 指標において一番強いノードが Cluster-Head であり続け、 そのノードを中心にクラスタが形成される Cluster-Head 中心となり クラスタを形成 同様に、周辺でもクラスタが形成される２つ以上のクラスタに所属するノードは Gateway となる Gateway クラスタ間の 中継ノード

7 チャネル割り当てアルゴリズム テーブル情報交換により、チャネル情報を取 得 hello パケットを N ホップ先のクラスタまで送信 今回のデフォルト値は 2 ホップ 使用チャネル情報を周辺クラスタと交換 使用チャネル情報にはクラスタで使用するチャネル及び MAP （アクセスポイント）で使用するチャネル 最も干渉の少ないチャネルを割り当て 周辺クラスタのチャネルの使用状況を取得 最も干渉の少ないチャネルを選出し、割り当てる

8 チャネル割り当てアルゴリズムの動作手 順 クラスタ ID 使用チャネ ル 3 2 2 １ 3 1，51，5 4，74，7 3 13 20 11 8 Hop ID ： 13 Ch ： 3 ID ： 13 Ch ： 2 ID ： 11 Ch ： 4 ID ： 8 Ch ： 3 ID ： 6 Ch ： 2 ID:20 Ch ： 1 ID ： 8 の情報が ID:11 を中継して伝わり、 ID ： 13 は ID ： 8 が自クラスタと同一のチャネルを使用していることを認識する ID ： 13 はテーブルを参照し、使用されていないチャネル 2 を割り当てる 32

9 提案手法の評価 クラスタリングに関する評価 クラスタリングによるノードのカバー率の評価 通信性能に関する評価 提案手法により通信性能がどの程度改善するかの 評価

10 クラスタリングに関する評価 シミュレーション環境 トポロジ： 間隔 50m で 5×5 のグリッド配置 ランダム配置 ノード数：２５台 シミュレーション方法 配置したノードに対してクラスタ リングを実行 クラスタリングによりカバーされ 、通信できるノードの割合を測定 各トポロジ 20 試行ずつ行い、平均 カバー率を測定 ネットワーク分断が発生し、通信できな い例

11 クラスタリングに関する評価 シミュレーション結果 クラスタリングにより、ネットワーク分断及びはぐ れノードの発生による通信不可能なノードがないこ とを確認 （両配置共に平均カバー率 100% ） 5×5 グリッド配置のクラスタリン グ例 ランダム配置のクラスタリング例

12 通信性能に関する評価 シミュレーション環境 無線チャネル数：４チャネル 送出トラフィック： FTP (TCP 通信 ) シミュレーション方法 メッシュネットワークにおいて、問 題の発生する MAP ｰ MPP 間の通信を想 定 ランダムで MPP1 台と MAP5 台を選出 提案方式を用いた場合と用いない場 合で、 MAP から MPP へのセッション を、 MAP1 から MAP5 まで 1 ずつ増やし 、最大 5 セッションで測定 MPP MAP1 MAP2 MAP3 MAP4 MAP5 シミュレーショ ン例

13 通信性能に関する評価 比較方法 スループットと公平性の二点 で比較 公平性は Fairness Index によ り比較 公平性結果 5×5 のグリッド配置、ランダ ム配置共に改善を確認した 干渉により通信できないノー ドを減少させることができた x i は各通信ノードのスループッ ト 1 に近づくほど公平性が高い 5×5 のグリッド配置の公平 性 ランダム配置の公平性

14 通信性能に関する評価 スループット結果 公平性同様、 5×5 のグリッド 配置、ランダム配置共に改善 を確認した まとめ 公平性、スループット共に改 善を確認 適切なチャネル割り当てが可 能となり、ノード間の通信干 渉が緩和 5×5 のグリッド配置のスループッ ト ランダム配置のスループッ ト

15 まとめ メッシュネットワークで発生するマルチホッ プネットワークに起因する問題に対して、ク ラスタリングチャネル割り当て方式の提案を 行い、スループット及び不公平問題の改善に 効果があることを確認した。 今後の予定 クラスタリングアルゴリズムの改良 チャネル割り当てアルゴリズムの改良

16 チャネル割り当てアルゴリズムの動作手 順 ID ： 13 ID ： 20 ID ： 11 ID ： 8 ID ： 6 ID ： 13 Hop ： 3 ID ： 20 Hop ： 3 ID ： 8 Hop ： 3 ID ： 6 Hop ： 3 Cluster-Head がテーブルの保持とチャネルの選出、割り当てを行う Cluster ID は Cluster-Head のノード ID を使用する テーブルの先頭には自クラスタ情報が入っている ID ： 11 Hop ： 3 ID ： 20 Hop ： 3 ID ： 13 Hop ： 2 ID ： 11 Hop ： 2 ID ： 11 Hop ： 3 ID ： 13 Hop ： 2 ID ： 8 Hop ： 3 ID ： 11 Hop ： 2 ID ： 13 Hop ： 1 ID ： 13 Hop ： 3 ID ： 11 Hop ： 2 Gateway を中継して隣接クラスタへテーブル情報を送信し、 さらに隣接クラスタがその情報を送信することにより、隣々接クラスタへ情報が到達す る ID ： 13 Hop ： 3 ID ： 20 Hop ： 2 ID ： 11 Hop ： 2 ID ： 8 Hop ： 1 ID ： 11 Hop ： 3 ID ： 13 Hop ： 2 ID ： 20 Hop ： 2 ID ： 8 Hop ： 2 ID ： 6 Hop ： 1 ID ： 20 Hop ： 3 ID ： 13 Hop ： 2 ID ： 11 Hop ： 2 ID ： 8 Hop ： 1 ID ： 8 Hop ： 3 ID ： 11 Hop ： 2 ID ： 13 Hop ： 1 ID ： 6 Hop ： 2 ID ： 6 Hop ： 3 ID ： 8 Hop ： 2 ID ： 11 Hop ： 1 同様の動作を各クラスタが繰り返すことにより、テーブルの更新が進む そのことにより各クラスタは周辺クラスタの情報を取得できる

17 ノードのロール LCC(Least Cluster Change) Highest-Connectivity と Lowest ID を指標に Cluster-Head を決定 Cluster-Head 以外のロールは、テーブル内の Cluster-Head 数（ 所属するクラスタ数）により決定 Cluster Head Regular Node Gateway ① ① ②② ③ ④ Cluster-Head 数に変化があった際に役割変更 ①：他の Cluster-Head に指標で劣った場合 ②： Cluster-Head 数が０になった場合 ③： Cluster-Head が 1 になった場合 ④： Cluster-Head が複数になった場合 ： Cluster-Head ： Gateway ： Regular-Node