マルチチャネルCSMA無線ネットワークにおけるチャネル割当方式に関する研究

Presentation on theme: "マルチチャネルCSMA無線ネットワークにおけるチャネル割当方式に関する研究"— Presentation transcript:

1 マルチチャネルCSMA無線ネットワークにおけるチャネル割当方式に関する研究
政策・メディア研究科 修士課程 2年 学籍番号 古坂 大地 それでは，「マルチチャネルCSMA無線ネットワークにおけるチャネル割当方式に関する研究」という題目で，発表させていただきます．政策メディア研究科修士課程2年の古坂です．よろしくお願い致します．

2 発表概要 研究背景 シングルチャネルCSMA無線網の問題点 本研究の目的 負荷分散型チャネル選択方式の提案 シミュレーション評価
搬送波検知，RTS/CTSの弊害 本研究の目的 負荷分散型チャネル選択方式の提案 LSCS : Load Sensitive Channel Selection Scheme シミュレーション評価 まとめと今後の展望 本日の発表概要はまずはじめに研究背景について述べ，次にシングルチャネルCSMA無線網の問題点について触れます．これらの問題の解決から本研究の目的を述べ，本研究において提案する負荷分散型チャネル選択方式，LSCS の提案をします．この方式の性能評価をシミュレーションにより行い，マルチチャネルCSMA無線網の利点と本方式の有用性を示します．最後に，まとめと今後の展望について述べます．

3 はじめに コンピューティングパラダイムの変化 無線通信技術の問題 可搬性の高いデバイスの出現 無線ネットワークの爆発的な普及
移動型コンピューティング環境の変化 無線通信技術の問題 乏しい帯域資源 高遅延，低通信速度 電波干渉 同一チャネル干渉問題，ブロッキング問題 近年，携帯電話やPDA，ラップトップなどポータブルデバイスの出現，それと，セルラネットワークや無線LANのような無線ネットワークの爆発的な普及によって，移動型計算機環境も急速に進化しています，そのような環境で，無線通信技術が非常に注目されていますが，乏しい帯域資源，電波干渉などの問題があり，その制御技術はまだ改善されなければならない状況にあります．

4 研究背景 (1) 有線･無線網接続形態の変化 従来型無線通信 アドホックネットワーク シングルホップ無線網 マルチホップ無線網
Wireless Wired Wireless Wired 現在，我々のプロジェクトでは無線網の新しい接続形態を研究しています．従来の無線ネットワークでは，シングルホップ型の通信が大部分を占めています．つまり，有線基盤網に接続された無線基地局へのラスト１ホップの通信やピアツーピアの無線通信です．またその一方，近年ではモバイルアドホックネットワーク つまり MANET に代表されるような，マルチホップ型無線通信の研究も盛んに行われています．アドホック・ネットワークは実際の用途は軍事目的や被災地ネットワークなどかなり特殊化されていますが，我々は有線基盤網との接続性を考慮したマルチホップ無線網により，今後マルチホップ無線網への期待は高まっていくと考えています． Infrastructure (FWA) Independent (Ad-Hoc)

5 シングルチャネルCSMAの問題点 搬送波検知メカニズムの弊害 RTS/CTSメカニズムの弊害 見え過ぎる端末問題 隠れ端末問題
NAVブロッキング問題 従来の無線網はシングルチャネル アクセスが大多数 マルチホップ無線網では顕著に起こる 従来の無線網の多くはシングルチャネルアクセスが大多数を占めています．しかし，シングルチャネルCSMAではチャネルの利用効率を著しく低下させる原因があります．またさらに，それらの問題はマルチホップ無線網において顕著に起こります．一つが，搬送波検知メカニズムによる弊害と，もう一つが，隠れ端末対策用のRTS/CTSメカニズムによる弊害です．

6 シングルチャネルMACの問題点 (1) 搬送波検知メカニズムの弊害
隠れ端末問題 見え過ぎる端末問題 C D C D 搬送波検知メカニズムの問題では，キャリアは検知できなかったにも関わらず，送信すると衝突が発生してしまうという，隠れ端末問題と，送信をしても衝突は発生しないにも関わらず，キャリアを検知したために送信できないという，「見え過ぎる端末問題」があります． A B A B

7 シングルチャネルMACの問題点 (1) 搬送波検知メカニズムの弊害
見え過ぎる端末問題 隠れ端末問題 A C この2つの問題はマルチホップ無線網でさらに顕著に見られます．スライドのようなトポロジを用いて説明すると，各点は無線局を表し，線は経路，円は電波到達範囲を表しています．このトポロジで，AからB，CからDへの2本のフローがあるとき，これらの同時送信では，見え過ぎる端末問題が発生し，これらの同時送信では，隠れ端末問題が発生します．また，CSMA無線網においては隠れ端末が存在すると著しくスループットの性能低下が起こることが知られています．今見られたとおり，マルチホップ無線網では隠れ端末が存在する確率は極めて高いと言えます． B D

8 シングルチャネルMACの問題点 (2) RTS/CTSメカニズムによる弊害
B RTS CTS DATA ACK そこで隠れ端末問題を回避するために提案されたメカニズムがRTS/CTSですが，このメカニズムもマルチホップ無線網においては弊害となります．データの送受信局がRTS/CTSを交換すると，送受信局に隣接する局はデータの送受信完了まで送信を完全に抑制されます．これにより，さらに1ホップ先の局達も結果としてその経路に向かって送信ができなくなります．我々は，この現象をNAVブロッキング問題と呼んでいます．NAVとはNetwork Allocation Vectorの略で，データ受信局以外のRTS/CTSを受信した局が送信抑制されるベクトルを意味します． C D NAVブロッキング問題

9 シングルチャネルMACの問題点 (2) RTS/CTSメカニズムによる弊害
シングルチャネル無線網では，効率的なマルチホップ通信を実現することができない A C 先ほどと同じトポロジーで今度は，AからC，DからBへの2本のフローがあるとき，各ホップでRTS/CTSを交換すると隣接する2ホップでの送受信が抑制されるため，すべての局の送信バッファでデータが停滞する原因となります．これは，フローの本数や送信量に関係し，バッファオーバフローの原因となります．このようにシングルチャネル無線網では効率的なマルチホップ通信を実現することができません．なぜなら，これらの弊害はシングルチャネル無線網においては回避することができない問題だからです． B D

10 マルチチャネル無線網の適応 不要な衝突および ブロッキングの回避 A C B D
そこで本研究ではマルチチャネル無線網にすることによりこれらの問題を回避します．マルチチャネルにすることにより，隣接する局間で相互干渉しないチャネルを選択利用することにより，不要な衝突やブロッキングのオーバヘッドを回避することができ，これによりマルチホップ･シングルチャネル無線網においてボトルネックであった問題を解決できます． B D 不要な衝突および ブロッキングの回避

11 本研究の目的 マルチホップ/マルチチャネルCSMA無線網における効率的なチャネル利用の実現 負荷分散型チャネル選択方式
LSCS : Load Sensitive Channel Selection 各局における自律分散機能 RTS/CTS の交換による通信 しかしたとえ，マルチチャネルCSMA無線網が実現されたとしても，各局が適切に通信チャネルを選択しなければチャネル利用率の観点から効果的な無線網システムであるとは言えません．本研究では，マルチホップ/マルチチャネルCSMA無線網における効率的なチャネル利用の実現を目的とし，負荷分散型チャネル選択方式LSCSを提案します．LSCSは各局において機能する自律分散型メカニズムであるため，従来のようなシングルホップ無線網にも適応することができます．また，隠れ端末問題に対応するためにRTS/CTSメカニズムを用います．本研究により，現在シングルチャネル/マルチホップ無線網の抱えている問題点を解決し，マルチホップ無線網の性能を改善することが可能と考えます．

12 負荷分散型チャネル選択方式 LSCS : Load Sensitive Channel Selection
トラフィックの監視・記録 トラフィック・グラフの生成 トラフィックの場の抽出 チャネル利用率の計算 各トラフィックの場の総トラフィック量の算出 チャネル利用率の期待値の計算 通信チャネルの選択 各チャネル利用率の比較 通信チャネルの切替 本方式では各チャネルのトラフィック量を元に適切な通信チャネルの選択を行います．本方式の動作手順は大きく3段階になります．トラフィックの監視記録，チャネル利用率の計算，通信チャネルの選択です．

13 LSCSの動作概要 (1) RTS/CTS情報の利用 全チャネル同時監視 トラフィック量 送信元アドレス 送信先アドレス 隣接局アドレス
トラフィック監視 開始 RTS/CTS情報の利用 トラフィック量 送信時間量 送信元アドレス 送信先アドレス 隣接局アドレス 隣接関係補間情報 全チャネル同時監視 チャネル選択 RTS/CTS受信 チャネル 利用率計算 トラフィック量 記録 総トラフィック量 計算 トラフィック グラフ生成 LSCSでは，RTS/CTSフレームに含まれる情報を利用し，チャネル利用率を計算します．その情報には，データを送信するために要する時間と，送信元のアドレス，送信先のアドレス，互い隣接関係を補間するための隣接局アドレス情報が含まれます．また，このマルチチャネルCSMA無線網では全チャネルを同時に聞くことができるものとし，各チャネルのトラフィックを同時に測定します．トラフィックの監視により，周辺のトラフィックの状況を認識し，チャネル利用率の計算のためのグラフ処理を行います．その処理結果から，チャネル利用率を計算します．最後に各チャネル利用率の比較を行い，最も低い利用率のチャネルを新しい通信チャネルとして選択します． NO トラフィック グラフ処理 監視終了? YES

14 LSCSの動作概要 (2) チャネル番号 利用率 チャネル 1 0.745 チャネル 2 0.437 チャネル 3 0.571
具体的な大まかな動作を説明すると，赤丸で囲まれた無線局が周辺のRTS/CTSを自分自身も受信し，その情報を蓄積していきます．一定時間を経過すると，この局は各チャネルで周辺にどれだけトラフィックが発生したかどうかを加算し，この場合チャネル2が最も利用率が低いと判断し通信チャネルを2番に切替えます．

15 LSCSの動作概要 (3) 相互干渉しない位置関係 Traffic 2 Traffic 1 ｔ チャネル利用率の 見積もり誤り
ただし，このような場合には2組の局間は互いに干渉関係にないために同時にトラフィックを発生させることがあり得ます．このような場合，測定したトラフィック量を単純に加算した場合，チャネル利用率の見積もりを誤ることになります．本方式では，互いの電波干渉関係を調べ，同時に発生するトラフィックを考慮してチャネル利用率を見積もるために，その確率的な期待値を求めます．しかし，すべての干渉関係を調べることは現実的ではなく，計算量のオーバヘッドも大きくなります． ｔ チャネル利用率の 見積もり誤り Traffic 1 Traffic 2 Traffic 1+2 期待値

16 「トラフィックの場」の概念 トラフィック量の単純加算可能な局の集合単位 条件:同時にトラフィックが発生しない
すべての局が相互干渉関係にある局の集合 そこで本方式では，トラフィックの場と呼ばれる概念を用いて単純に加算可能な局の集合の単位を導き出します．トラフィックの場内では，各局は同時にトラフィックを発生できないような位置関係にあるものとします．本方式では，測定局の周辺に同時に存在可能なトラフィックの場を求めます．このような位置関係で通信される時，同時に存在可能なトラフィックの場は，このようになります．

17 トラフィック・グラフの生成 そのために隣接関係を示すグラフ，トラフィック・グラフを生成する必要があります．これは，RTS/CTSのアドレス情報を処理することにより実現されます．先ほどの局の隣接関係をグラフにするとこのようになります．ただ，これは空の上から見た場合です．測定局から，監視できるものは，隣接局のトラフィックのみで，隠れ端末間のトラフィックは監視できません．また，グラフの規模を抑えるために測定局自身に関するトラフィックは別処理します．従って，測定局ではこのようなトラフィック・グラフを生成することになります．

18 トラフィックの場の抽出 (1) トラフィックの場の条件 同時存在可能条件 隣接局の重み付け 隣接局のクリーク 極大クリーク 頂点を共有しない
測定局から最大限離れている 隣接局の重み付け 受信信号出力 次に，トラフィックの場をトラフィック・グラフから抽出します．隣接局間でクリークを形成することが分かります．その同時存在可能条件は，各クリークが頂点を共有しない極大クリークであるということです．一般に極大クリーク発見はNP問題であることが知られていますが，次の条件によりNP問題を回避し，かつ，できるだけ多くの同時存在可能なトラフィックの場を抽出します．その条件は，測定局から最大限離れているということです．そこで，測定局との距離関係を表す指標として，RTS/CTSの受信時に得られた受信信号出力を用います．測定局はその値に比例した重み付けを送信局に付加します．

19 トラフィックの場の抽出 (2) 4 5 6 7 3 9 12 10 1 先ほどのトラフィック・グラフからトラフィックの場を抽出すると，このように3つのトラフィックの場が得られます． 2 11 8

20 チャネル利用率の計算 チャネル利用率λとは トラフィックの場毎の 総トラフィック量の計算  単純総和計算 チャネル利用率の期待値を求める
あるチャネルにおいてトラフィック監視期間に対してトラフィックの発生した割合ρ トラフィックの場毎の 総トラフィック量の計算  単純総和計算 チャネル利用率の期待値を求める トラフィックの場毎の独立事象 チャネル利用率とは，あるチャネルにおいてトラフィック監視期間に対してトラフィック発生時間の割合とします．トラフィック発生時間はトラフィックの場毎の総トラフィック量の計算で得られ，そこから確率的な期待値を求めます．計算式では，このようになります．

21 関連研究 マルチホップ/マルチチャネル無線MAC マルチチャネルCSMA無線MAC マルチホップ負荷分散型無線MAC [Haas97]
予約割当方式，ポーリング マルチチャネルCSMA無線MAC [Nasipuri00] SINRベース，隠れ端末問題 マルチホップ負荷分散型無線MAC [Ozugur98] シングルチャネル (AIR)，コンテンション時間，ポーリング 関連研究としては，Haasの，予約割当方式のマルチチャネル/マルチチャネル無線MACプロトコル．Nasipuri の，マルチチャネルCSMA無線網における信号品質ベースのチャネル選択方式．Ozugurの，シングルチャネル/マルチホップ無線網における負荷分散方式があります．

22 関連研究との比較 チャネル数 アクセス 方式 負荷分散 制御 コスト 装置導入コスト Haas Multi Channel
Slotted-TDMA △ × Nasi puri CSMA ○ Ozu gur Single Channel CSMA+ RTS/CTS LSCS これらの研究をまとめると，Haasは，制御パケットのポーリングによるオーバヘッドが大きい点と，予約割当方式である点で，Nasipuriは，制御パケットは一切行わないが，隠れ端末問題についてあまり考慮していない点と，通信装置に関する現実的な考慮が足りない点で，Ozugurは，制御パケットのオーバヘッドの大きさと，シングルチャネルである点で本方式と異なります．本方式では，隠れ端末問題に効率的なRTS/CTSメカニズムを併用し，その制御情報から負荷分散を実現している点と，マルチチャネル･マルチホップ無線網に対する考慮をした方式である点として他研究よりも優れていると言える．

23 シミュレーション評価 Network Simulator 2 (NS-2) による シミュレーション評価
評価1 シングル・マルチチャネルCSMA 無線網の性能評価 評価2 チャネル選択アルゴリズムの性能評価 本研究では，マルチチャネルCSMA無線網の優位性と，提案方式のアルゴリズムの有効性を示すために，シミュレーションによる評価を行った．シミュレーションには，ネットワーク・シミュレータ ns-2を用いた．

24 シミュレーションモデル (1) 平面 1000m×1000m ノード数 100台 格子状静止配置 配置間隔 100m 伝送距離 250m
ノード数　　　　　　　100台 格子状静止配置 配置間隔 m 伝送距離 m シミュレーションは，1000メートル四方のフィールドに100台の無線端末を格子状に静止配置したトポロジーを用いた．配置間隔は100メートルとし，また無線の伝送距離は約250メートルと設定した．

25 シミュレーションモデル (2) 固定長パケットの送信 呼の発生は指数分布に従う 1000秒間のフロー測定 経路制御プロトコル DSR
パケット長 512 Bytes パケット送信 レート 5, 10, 20, 50, 100 pkts/sec チャネル帯域幅 2.0 Mbps トラフィックモデルでは，トラフィックモデルには，固定長のパケットを呼の到達率が指数分布に従う形で発生させ，一定レートの2本のフローをトポロジーの左上と左下からクロスさせる形で流しました．チャネルの帯域幅は，2.0Mbpsとしシミュレーションを行いました．

26 評価 1: シングル/マルチチャネルCSMA無線網の評価
チャネル数 1, 2, 3, 4 測定項目 平均スループット 衝突パケット数 中継局におけるパケット損失 (バッファオーバフロー数)

27 評価 1: 平均スル―プット 106％ 105％ グラフの横軸はフローの送信レート，縦軸はスループットで，各々単位はkbpsです．このグラフから，チャネル数を増やすことによりスループットが増加していることが分かります．また，○で示した部分はシングルチャネルよりも帯域利用率が高かった部分を示し，それぞれ105%,106%の値を示しています．

28 評価 1: 平均衝突パケット数 チャネル数増加により減少
次に平均衝突パケット数ですが，横軸には送信レートを，縦軸には衝突パケットの総数を取っています．チャネル数の増加により衝突数を抑えることが実現されています． チャネル数増加により減少

29 評価 1: オーバフロー数 チャネル数増加により減少
同様に，中継局でのバッファオーバフローによるパケット損失を測定しました．横軸は送信レート，縦軸はオーバフロー数です．これも中継局のオーバフローをチャネル数増加により大幅に抑えることができています． チャネル数増加により減少

30 評価 2: チャネル選択アルゴリズムの評価 STATIC RANDOM LSCS システム起動時にランダムで通信チャネルを選択
パケット送信時にランダムで通信チャネルを選択 LSCS 1秒間の各チャネルのチャネル利用率から送信チャネルを選択

31 評価 2: 平均スループット

32 評価 2: 平均衝突パケット数

33 評価 2: オーバフロー数

34 まとめ マルチチャネルCSMA無線網におけるMACプロトコルを提案 シングルチャネル/マルチチャネルCSMA無線網の基本性能評価を行った
LSCS : 負荷分散型チャネル選択方式 「トラフィックの場」の概念 チャネル利用率の計算 シングルチャネル/マルチチャネルCSMA無線網の基本性能評価を行った 最後に，本研究では，マルチチャネルCSMA無線網における負荷分散型チャネル選択方式LSCSを提案しました．マルチチャネルCSMA無線を実現するためにチャネル解決プロトコルCRPを用います．またLSCSでは「トラフィックの場」の概念を用い，チャネル利用率を計算します．今回は，シングルチャネルとマルチチャネルCSMA無線網の基本性能評価を行い，またこれによりマルチチャネルCSMA無線網によるチャネル利用効率が向上されることが分かりました．

35 今後の課題 シングルチャネルとマルチチャネルの トレードオフの評価 デバイスの実現性の考慮 アルゴリズムに信頼性
Dual Channel Wireless LANs アルゴリズムに信頼性 今後の課題としては，シングルチャネルとマルチチャネルのトレードオフの評価があります．マルチチャネルはマルチホップ無線網には適しているが，シングルホップではどうか？またバッテリへの負荷，チャネル切替えのオーバヘッドなどがあります．そして，本方式の実装および評価をしなければなりません．現在ns2上にシミュレーションモジュールを実装中です．以上で発表を終わりたいと思います．ありがとうございます．

36 主な発表論文一覧 古坂, 岩本, 永田, 西尾, 徳田　「無線LANにおけるセル制御システムに関する研究」　情報処理学会オペレーティング・システムおよびシステムソフトウェア研究会報告, 1999 Furusaka, Iwamoto, Nagata, Tokuda “Load-Sensitive Handover Scheme over Wireless Local Area Networks” IEEE ICDCS Workshop on WNMC, 2000 古坂, 徳田　「マルチチャネルCSMA無線網における負荷分散型チャネル選択方式に関する研究」マルチメディア,分散,協調およびモバイルシンポジウム (DiCoMo2001), 2001

37 チャネル利用率の計算 (2) トラフィックの発生した割合 チャネル利用率の期待値を求める
トラフィックの場毎の独立事象 CALCCHANNELUTILIZATION () utilization ← for each TrafficSpot K ∈ SPOT weight[K] ← CALCTRAFFIC (K) / PERIOD utilization ← utilization × (1 – weight[K]) return utilization この値を用いて，チャネル利用率を計算します．チャネル利用率はトラフィック監視時間に対するトラフィック発生時間の割合で表します．前に説明したように，相互干渉関係にないトラフィックは互いに独立して発生します．そこで，チャネル利用率は単純にトラフィックの場毎の総トラフィック量の総和を用いるのではなく，その期待値を求めます．それを式で表すとこのようになります．Ζはチャネル利用率の期待値，ρがトラフィックの場毎の総トラフィック量，Tがトラフィック監視時間です．従って，チャネル利用率の計算アルゴリズムはこのようになります．これらの処理を各チャネル毎に行い，最終的に最小チャネル利用率のチャネルを新しい受信チャネルとして選択します．