Comments
Description
Transcript
WMN におけるデータ転送効率の向上の ための経路制御
平成 27 年度 修士学位論文 WMN におけるデータ転送効率の向上の ための経路制御手法の提案 Proposal of routing method that improves transmission capability in WMN 1185081 小林 亘 指導教員 植田 和憲 講師 2016 年 2 月 26 日 高知工科大学大学院 工学研究科 基盤工学専攻 情報システム工学コース 要 旨 WMN におけるデータ転送効率の向上のための経路制御手法の 提案 小林 亘 近年、移動端末や Wi-Fi の普及に伴い無線メッシュネットワークが注目されている。無線 メッシュネットワークは簡単に広い範囲に無線ネットワークを構築できるため、災害時の一 時的な無線インフラとして活用が期待されている。しかし、無線メッシュネットワークには 課題もあり、従来の無線ネットワークよりも制御通信が増えて、データ転送の効率が落ちる 可能性がある。 本研究グループでは制御通信数をおさえることで無線メッシュネットワークでのデータ転 送効率の向上を図る経路制御手法を提案してきた。本稿ではこの経路制御手法を特定のノー ド配置に対応できるように拡張したものを提案する。そして拡張した経路制御手法でシミュ レーションを行い、特定のノード配置に対応できることを確認した。 キーワード 無線メッシュネットワーク、MBCR –i– Abstract Proposal of routing method that improves transmission capability in WMN KOBAYASHI Wataru In recent years, Wireless Mesh Network have been forcused along with the popularization of mobile terminal and Wi-Fi. Wireless Mesh Network is expected as a temporary wireless infrastructure in a time of disaster beacause it can build a wireless netowrk to easily wide range. However, wireless mesh network has a problem. It is a problem that efficency of data transfer decrease due to control conmmunication increase than wireless network. Our reseach group have proposed routing method MBCR for improvement of efficency of data transfer by reduction of control communications. Tnis manuscript extended routing method that can respond to specific node placement, and confirmed performance of extended routig method. key words Wireless Mesh Network, MBCR – ii – 目次 第1章 はじめに 1 第2章 無線メッシュネットワーク 3 2.1 概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 経路制御手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 HWMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 拡張前の MBCR の仕様 8 3.1 概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 仮想アドレスのフォーマット . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 仮想アドレス決定パターン . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 経路制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 第4章 拡張前の MBCR のシミュレーション 18 第5章 拡張後の MBCR の仕様 29 第3章 5.1 隣接ノードの評価方法の拡張 . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 拡張した MBCR の性能評価 . . . . . . . . . . . . . . . . . . . . . . . . . 32 まとめ 37 第6章 謝辞 38 参考文献 39 – iii – 第1章 はじめに 近年、移動端末や Wi-Fi の普及に伴い無線メッシュネットワーク (WMN:Wireless Mesh Network) が注目されている。従来の無線ネットワークではアクセスポイント間の通信は有 線を敷設して行うが、無線メッシュネットワークはアクセスポイントの通信をマルチホップ 無線通信で行い、ノードは自律的にネットワークを構築できる。そのため、有線の敷設にか かるコストを削減でき、さらに容易にネットワークの構築、拡大、縮小が可能である。また、 メッシュ状にトポロジーを形成する冗長構成により、耐障害性も高い。このような特性から イベントや災害時などの一時的な無線インフラとしての利用が期待されている。 しかし、従来の経路制御手法よりも複雑な経路制御が必要になるという課題もある。これ は、WMN ではデータを送信する際に各ノードが経路制御手法を基に自律的にデータパケッ トの転送先を決定するからである。この経路制御の際には、経路制御に必要な情報をノー ド間で送受信することになり、この通信を制御通信と呼ぶ。制御通信のパケットはデータパ ケットと同じ無線帯域で送受信されるため、制御通信が多くなるとデータパケットの転送効 率の低下を起こす。図 1.1 は制御通信のビーコン送信間隔 50ms、75ms、125ms に変化させ た場合の宛先へのデータパケット到達数を表すグラフである。ここから制御通信の間隔が短 いときはデータ転送効率が落ちることが確認できる。 本研究グループでは MWN でのデータ転送効率を向上させるために制御通信数を抑えた 経路制御手法 MBCR を提案してきた [1]。また、ノードの故障や電波強度の変動が発生し た場合に対応できるように MBCR の拡張を行ったり、パラメータの検証などが行われた [2][3]。検証の中でノード数が多いときに特定のノード配置だと MBCR の性能が大幅に落ち る問題が確認できた。本研究ではこの問題を解決するために MBCR のアルゴリズムの拡張 –1– ϭϭϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϬϬϬϬϬ ϵϬϬϬϬ ϴϬϬϬϬ ϳϬϬϬϬ ϲϬϬϬϬ ϱϬϬϬϬ ϰϬϬϬϬ ϭϬ ϮϬ ϱϬŵƐ 図 1.1 ϯϬ 䝜䞊䝗ᩘ ϳϱŵƐ ϰϬ ϱϬ ϭϮϱŵƐ ビーコンの送信間隔を変化させたときのデータパケット到達率 を行い、拡張した MBCR の性能評価を行う。 –2– 第2章 無線メッシュネットワーク 本章では研究分野である無線メッシュネットワークの概要の説明を行う。また、無線メッ シュネットワークで用いられる経路制御手法についても説明する。 2.1 概要 無線メッシュネットワーク (WMN:Wireless Mesh Network) はノード間の通信を無線マ ルチホップで行うネットワークである [4]。従来の無線ネットワークはアクセスポイント間 の通信は有線で行うが、無線メッシュネットワークの場合は無線で通信を行う。そのため、 配線のコストの削減や配線によるノード配置の制限がないというメリットがある。また、マ ルチホップ通信により直接通信できないノードにも他のノードを経由してデータを送信する ことができる。 無線メッシュネットワークの構成要素は MeshSTA、Route MeshSTA、STA から構成さ れる。MeshSTA は無線メッシュネットワークを構成するために必要なメッシュ機能を実装 したノードである。また、メッシュ機能を持たない従来の無線 LAN 端末からの接続を収容 する機能も持つ。Route MeshSTA はメッシュ機能に加えて無線メッシュネットワークと他 のネットワークとの接続のためのゲートウェイとしての機能を持つノードである。STA は メッシュ機能を持たない従来の無線 LAN 端末のことである。無線メッシュネットワークの 構成例を図 2.1 に示す。無線メッシュネットワークの実用化について阪田史郎の叙述に従っ てまとめる（阪田史郎,「M2M アドホックネットワーク、センサネットワークの今後の展開」 電子情報通信学会技術研究報告. CS, 通信方式 113(295),41 ページ, 2013-11-07. 参照 ）。 –3– 2.2 経路制御手法 ᭷⥺䝛䝑䝖䝽䞊䜽 ↓⥺㏻ಙ ZŽƵƚĞ DĞƐŚ^d DĞƐŚ ^d DĞƐŚ ^d DĞƐŚ ^d DĞƐŚ ^d ^d ^d ^d 図 2.1 無線メッシュネットワークの構成例 無線メッシュネットワークは災害時の一時的な無線インフラとしての活用や家庭内の AV 機器間の接続などへの活用が期待されている。しかし、実用化された例は少なく、 国内において災害時支援や環境モニタリング、観光地やショッピングモールでの情報提 供など様々な実証実験が行われたがほとんどが実験で終わっている。 この原因の一つとして複雑な経路制御のために制御通信が多くなり、無線帯域を圧迫して データ通信の効率が落ちることが挙げられる。 2.2 経路制御手法 無線メッシュネットワークでの経路制御手法は経路情報の生成のタイミングにより、プロ アクティブ型とリアクティブ型の大きく二つに分けられる。 プロアクティブ型は周期的に制御通信を行うことで各ノードが無線メッシュネットワーク 内すべてのノードへの経路情報を保持する。プロアクティブ型のメリットは常に経路情報を 保持しているため、通信要求が発生したときにすぐに通信を開始できるという点である。し かし、データの送受信が行われない間も周期的に制御通信を行うため、オーバーヘッドが 多くなる。代表的なプロアクティブ型の経路制御手法として OLSR(Optimized Link State Routing)[5] がある。 リアクティブ型は通信要求が発生してから経路情報の生成を行う。そのため無駄な制御通 –4– 2.3 HWMP 信を削減することができ、さらに最新の経路情報を用いて経路制御を行えるメリットがあ る。デメリットとしては通信要求が発生してから経路情報の生成を行うため、プロアクティ ブ型と比べて通信開始までに時間が掛かる点が挙げられる。代表的なリアクティブ型の経路 制御手法として AODV(Ad hoc On-Demand Distance Vector)[6] がある。 また、プロアクティブ型とリアクティブ型を組み合わせたハイブリッド型の経路制御手 法も存在する。代表的なハイブリッド型の経路制御手法として HWMP(Hybrid Wireless Mesh Protocol)[7] が挙げられる。 2.3 HWMP HWMP は無線メッシュネットワークの国際規格である IEEE802.11s[8] に採用されている 経路制御手法である。HWMP はリアクティブ型である RM-AODV(Radio Metric AODV) とプロアクティブ型である TBR(Tree Base Routing) を状況によって使い分けることで様々 な無線メッシュネットワークの利用形態に対応できる。リアクティブ型とプロアクティブ型 の切り替えはネットワーク内にネットワーク管理を行う代表ノードとなるルートノードが存 在するかどうかで決まる。ルートノードが存在しない場合は RM-AODV を用いて経路制御 を行い、存在する場合は RM-AODV と TBR を組み合わせて使う。 RM-AODV はリアクティブ型の経路制御手法である AODV を改良したものである。 AODV では通信を行いたいノードはまず経路要求 (RREQ:route request) メッセージをブ ロードキャストする。RREQ には生成元のアドレスや終点アドレスなどが含まれる。この RREQ を受信したノードはノード間のメトリック情報を付与して、RREQ の再ブロード キャストを行う。これを繰り返し、終点ノードが RREQ を受信したら、終点ノードは経路 応答 (RREP:route reply) メッセージを RREQ を中継した通信経路で RREQ の送信元ま でユニキャストする。この動作を経て、RREP は RREQ の生成元に到達し、終点への経路 が確立される。AODV の経路探索の例を図 2.2 に示す。ノード A がノード D にデータを送 信する場合を考える。送信元 A はノード D への経路探索を行うために、RREQ をブロード –5– 2.3 HWMP ZZY ZZWϭ ZZWϮ 図 2.2 AODV の経路探索 キャストする。RREQ を受信したノード B とノード C はノード A とのリンクメトリック 情報を RREQ に付与して再ブロードキャストを行う。ノード D はノード B とノード C か ら RREQ を受信し、ノード D は RREP を RREQ を中継した通信経路で送信元 A までユ ニキャストを行う。この例ではノード A からノード D にデータを送る経路はノード B を経 由するパターンとノード C を経由するパターンの 2 通り存在する。送信元のノード A はメ トリック情報を基にどちらの経路が最適かを評価して経路を決定する。これが AODV の経 路探索である。 RM-AODV はノードが複数の無線デバイスインターフェースを持つ場合、その中から無 線周波数帯の利用率が低いインターフェースを使用して無線通信帯域の利用効率を向上させ ている。また、経路制御機能を持たない STA が MeshSTA を介して経路制御を行えるよう にして無線メッシュネットワークに参加できるようになっている。 TBR はルートノードとして設定された MeshSTA が周期的に RANN(Route Announce) メッセージをブロードキャスト送信し、他の MeshSTA はルートノードから送信された RANN を再ブロードキャストする。この動作によりネットワーク内に木構造の経路を構築 し、通信は構築した経路を基に行う。TBR の経路構築の例を図 2.3 に示す。なお、RANN のみによって作成される木構造の経路はルートノードを中心とした経路となるため、経路が 冗長となる場合がある。その対策として TBR では RM-AODV の RREQ を用いたルート ノードを経由しない経路の構築もオプションとして使用できる。 –6– 2.3 HWMP 䝹䞊䝖䝜䞊䝗 䝹䞊䝖䝜䞊䝗 ZEE䜢ᇶ䛻 ᮌᵓ㐀䜢ᵓ⠏ ZEE 図 2.3 TBR の経路構築 –7– 第3章 拡張前の MBCR の仕様 本章では、本研究グループが提案するデータ転送効率の向上を目的とした経路制御手法 MBCR の仕組みについて説明する。 3.1 概要 MBCR(Multiple Branch Collection Routing) は無線メッシュネットワークでの経路制 御に必要な制御通信数を抑えることで無線帯域を有効活用し、データ転送効率を上げるこ とを目的とした経路制御手法である。MBCR では経路制御の際に仮想アドレスという本研 究グループで新たに定義したアドレスを用いる。仮想アドレスを用いてノードの位置とリ ンクを仮想的な木構造として見ることができる。この木構造を仮想木と呼び、仮想アドレ スはこの仮想木でのノードの位置を表す。この仮想木は無線メッシュネットワークの Route MeshSTA の機能を持つノードを原点として構築するのが基本である。実際のノード配置を 仮想木で表した例を図 3.1 に示す。MBCR では一つの無線メッシュネットワーク内に複数 の仮想木を作ることもできる。 MBCR が制御通信数を抑えて経路制御できるのは二つの要件を満たすからである。一つ は経路制御の際に仮想アドレスのみを用いることである。もう一つは仮想アドレスを隣接 ノードとの制御通信のみで決定することである。 MBCR はこれまでにいくつかの改良や検証がされてきた。ノードの故障や受信信号強度 の急激な変化へ対応できるように拡張 [1]、パラメータの検証 [2], リンクメトリックの検証 [9] などが行われてきた。 –8– 3.2 仮想アドレスのフォーマット 0.0 0.0 0 0 A C ௬䜰䝗䝺䝇 ᮌᵓ㐀䛷 䝸䞁䜽䜢⾲⌧ B 0.0 0.6 0 0 A D E F E 0.0 1.4 0 1 F ᐇ㝿䛾䝜䞊䝗㓄⨨ 図 3.1 B D 0.8 0.0 0 0 C 0.8 0.7 0 1 1.5 1 ᮌᵓ㐀䛷⾲⌧䛧䛯䝜䞊䝗㓄⨨ MBCR の仮想木の例 次に仮想アドレスについて詳しく説明していく。 3.2 仮想アドレスのフォーマット 仮想アドレスは実際のノードの配置やリンクを仮想木で表した際のノードの位置情報と なっている。仮想アドレスに含まれる情報は次の四つである。 • 所属する仮想木のツリー ID • 所属する仮想木の枝の原点からの仮想的な距離 • 所属する仮想木の枝の端点情報 • 仮想アドレス次元 ツリー ID は仮想木ごとに割り振られる識別番号であり、無線メッシュネットワーク内に複 数の仮想木が存在しても識別できるようにするための情報である。所属する仮想木の枝の原 点からの距離と所属する仮想木の枝の端点情報と仮想アドレス次元は各ノードの仮想木での 位置を表すために必要な情報である。これらの構成要素を表現するために、本研究グループ では図 3.2 のフォーマットを利用している。この仮想アドレスのフォーマットは上段の数値 が仮想木の枝の原点からの仮想的な距離を表しており、下段は仮想木の枝の端点情報を表し ている。上段と下段の値の一対が仮想木中の各枝での位置を表している。ノード A の仮想 –9– 3.2 仮想アドレスのフォーマット 䜰䝗䝺䝇ḟඖ 㟁Ἴᙉᗘ䛛䜙⟬ฟ䛥䜜䛯 0.0 0.0 ௬ⓗ䛺㊥㞳್ 0 0 A ཎⅬ䛛䜙䛾௬ⓗ䛺㊥㞳 Ϭ͘ϲ 0.8 0.0 0.6 0.8 B 0 0 D 0 Ϭ͘ϱ 0.0 1.1 E 0.7 1.5 ➃Ⅼሗ 0 1 C 1 図 3.2 仮想アドレスのフォーマット例 アドレスで上段と下段の値のセットが二つ並んでいるのは枝の分岐を表している。枝が分岐 するたびに上段と下段の値のセットが追加されていく。この枝の分岐によって追加される情 報のことをアドレス次元と呼ぶ。図 3.2 だとノード A のアドレス次元は 2、ノード B のアド レス次元は 1 である。仮想木の枝の端点情報は枝の端点であるかどうかを表しており端点の 場合は 1、そうでない場合は 0 の値となる。仮想的な距離値の算出方法について述べる ∗1 。 仮想木の枝の原点からの仮想的な距離は隣接ノードからの受信信号強度を基に算出さ れる。この数値は、まず隣接ノードとの通信時に取得した受信信号強度 Pr [dBm] から 隣接ノードとの相対的な距離 d[km] を式 3.1 により計算する。 √ λ d= × 4π Pt (Gt Gr ) Pr Pr λ 2 = Gt Gr ( ) Pt 4πd dreal drelative = dmax (3.1) (3.2) (3.3) 式 3.1 は式 3.2 のフリスの伝搬公式を変形したもので、ノードが無線通信で使用する電 波の周波数と受信信号強度によってノード間のおおよその距離を推定する式となってい る。隣接ノードとの相対的な距離 drelative は、実際の電波強度を用いて計算した距離 ∗1 丸岡 優大, 植田 和憲,“ WMN における隣接関係を考慮した経路制御手法の提案と性能評価, ”マルチメディ ア通信と分散処理ワークショップ 2012 論文集,pp.46,Oct.2012. を参照 – 10 – 3.3 仮想アドレス決定パターン dreal と最大受信信号強度を用いて計算した距離 dmax を式 3.3 により算出する。仮想ア ドレスを決定する際には求めた drelative を隣接ノードの保持する枝情報に足し合わせ ることで仮想アドレスを決定する。以上のことから、仮想アドレスがわかっていれば、 遠方のノードであってもおおよその距離を推定可能となっている。 仮想アドレスは上記のフォーマットをプログラム中で利用しようとすると、一つの仮想アド レスを表すための情報量は、浮動小数点値を枝の分岐した分だけ保持する必要がある。これ では非常にデータ量が大きくなってしまい、制御通信を行う際のヘッダ情報が肥大化してし まい無線帯域を圧迫する可能性が出てくる。また、パケットを送信するためのアドレスとし て仮想アドレスを使うためには、既存のプロトコルと親和性の高いフォーマットにする必要 がある。そこで、仮想アドレスの情報量圧縮と宛先情報として利用可能なアドレスとするた めに MBCR では仮想アドレスを IPv6 形式のアドレスに変換する。128bit の IPv6 アドレ スの先頭の 8bit はネットワーク識別のためのプレフィックスとして使用し、そこからさらに 8bit は仮想木を識別するためのツリー ID として使用する。そして残り 112bit を仮想アド レスとして使用する。各次元の情報を 14bit で表現するため、アドレス次元は最大 8 次元ま でになっている。各次元の情報の 14bit の内訳は先頭の 1bit が端点情報を表しており、残り 13bit で枝の原点からの仮想的な距離を表現する。仮想的な距離は式 3.4 に示す浮動小数点 数の変換式によって指数部と仮数部に分離し、指数部を 13bit の内の 3bit に格納し、仮数 部を残り 10bit に格納する。 距離値 = 2距離値の指数 ×距離値の仮数 3.3 (3.4) 仮想アドレス決定パターン 仮想アドレスはネットワーク参加時に隣接ノードとの制御通信により決定し付与される。 また、受信信号強度が大きく変動した場合には仮想アドレスの再決定を行う。新しく仮想ア ドレスを決定するノードは仮想木に所属している隣接ノードから枝を延長、もしくは分岐し て仮想アドレスを割り当てる。枝を延長するか分岐するかは新規参加ノードと隣接ノードの – 11 – 3.3 仮想アドレス決定パターン 位置関係によって決まる。枝を延長する場合をパターン 1、枝を分岐する場合をパターン 2 として説明する。 パターン 1 は新規参加ノードの隣接ノードが仮想木の枝の端点である場合に選択される。 パターン 1 が選択される場合のノード配置の例を図 3.3 に示す。新規参加ノード G は隣接 Ϭ͘ϱ Ϯ͘ϭ Ϭ Ϭ Ϭ͘ϱ ϭ͘ϰ Ϭ Ϭ ཧຍᚋ ' Ϭ͘ϵ Ϭ͘ϱ ϯ͘Ϭ Ϭ ϭ Ϭ͘ϱ Ϯ͘ϭ Ϭ ϭ ' 図 3.3 仮想アドレス決定パターン 1 ∗2 ノードであるノード E と制御通信を行う。ノード G はノード E の仮想アドレスをコピーし て、さらにノード E との間の受信信号強度を基に仮想的な距離値を算出し、コピーした仮 想アドレスに加算する。これでノード G は仮想木の枝を延長し端点としてネットワークに 参加する。また、ノード E は仮想木の端点ではなくなったので、自身の仮想アドレスの端点 情報を 1 から 0 に変更する。これがパターン 1 の仮想アドレス決定の流れである。 パターン 2 は新規参加ノードが同じ枝に所属する 2 台以上の隣接ノードの中間に配置され た場合に選択される。図 3.4 にパターン 2 が選択される場合のノード配置の例を示す。新規 参加ノード F は隣接ノード D を新しい枝の原点とする枝を生成して、生成した枝に新しく 参加する。隣接ノード D は新しい枝の原点となるために新しい次元を仮想アドレスに追加 ∗2 丸岡 優大, 植田 和憲,“ WMN における隣接関係を考慮した経路制御手法の提案と性能評価, ”マルチメディ ア通信と分散処理ワークショップ 2012 論文集,pp.46,Oct.2012. を基に作成 ∗3 注釈 2 と同様 – 12 – 3.3 仮想アドレス決定パターン Ϭ͘ϱ ϭ͘ϰ Ϭ Ϭ ཧຍᚋ Ϭ͘ϴ Ϭ͘ϴ ϭ & Ϭ͘ϱ ϭ͘ϰ Ϭ Ϭ Ϭ͘ϱ ϭ͘ϰ Ϭ Ϭ Ϭ͘Ϭ Ϭ 図 3.4 & 仮想アドレス決定パターン 2 ∗3 する。新規参加ノード F はその仮想アドレスをコピーして、受信信号強度から求めた仮想的 な距離値を加算し自分の仮想アドレスとして設定する。また、自分が枝の端点になるため、 端点情報を 0 から 1 に変更する。 MBCR ではこの二つのパターンを用いて仮想アドレスの決定を行う。しかし、無線メッ シュネットワーク内のノード数が増加していくとパターン 1 とパターン 2 どちらの状況に も当てはまる新規参加ノードが出現する可能性がある。この場合は、新規参加ノードの持つ すべての隣接ノードの情報を評価し、最も適切な隣接ノードを選択し仮想アドレスを決定す る。ここからは、この評価方法について説明していく。 隣接ノードの評価に用いられる情報は隣接ノードの所属するツリー ID、隣接ノードの受 信信号強度、隣接ノードの枝上での位置の観点から評価を行い、どちらのパターンを選択す るか決める。ツリー ID での評価は、Route MeshSTA から発生した仮想木か一時的に設定 されている仮想木かの判定を行う。一時的に設定されている仮想木とは、ノードの故障やリ ンク切断などの何らかの理由で Route MeshSTA から発生した仮想木から分離された仮想 木のことである。この一時的な仮想木は Route MeshSTA から発生した仮想木の隣接ノー ドを発見すると、アドレスを破棄して Route MeshSTA から発生した仮想木から新しく仮 想アドレスを取得するように動作する。仮想アドレスの決定中はデータ通信はできなくなっ – 13 – 3.3 仮想アドレス決定パターン てしまうため、できるだけ Route MeshSTA から発生した仮想木を基に仮想アドレスを決 定する必要がある。これがツリー ID の評価である。隣接ノードの受信信号強度の評価は隣 接ノードからの受信信号強度の比較を行い、その中から受信信号強度の強い隣接ノードを選 択する。これはノード間のリンクができるだけ切断されないようにするためである。最後に 隣接ノードの枝上での位置の評価は、できるだけ枝の分岐ではなく枝の延長を行うように、 仮想木の枝の端点である隣接ノードを優先する。これは、枝の分岐が発生するとアドレス次 元が増加するためである。アドレス次元が増加すると仮想アドレスの情報量が増えることに なり、情報量が大きくなりすぎると MBCR の性能が著しく低下したり、正常に動作しない などの問題が発生する。現在の仕様では仮想アドレス次元は最大 8 次元までとなっている。 すべての隣接ノードに対してこれら三つの評価を行い、最も評価の良い隣接ノードを仮想 アドレスの決定に用いる。しかし、実験を行う中でこれら三つの評価では特定のノード配置 の際に最適な隣接ノードが選ばれずに、枝の分岐が多発して仮想アドレス次元が 8 次元を超 えて性能が落ちることが確認された。この検証内容と問題については後の章で説明を行う。 今まで新規参加ノードが１台だけの際の説明したが、複数台のノードが同時にネットワー クに参加する場合もあり、通信のタイミングによっては仮想アドレスの競合や不整合が発生 する可能性がある。この問題の対策として新規参加ノードは隣接ノードの情報を基に仮想ア ドレスの仮決定を行う。自身の仮決定した仮想アドレスと隣接ノードから受信した情報を メッセージとして隣接ノードに送信する。このメッセージをロックメッセージと呼ぶ。ロッ クメッセージを受信した隣接ノードはロックメッセージに含まれる仮想アドレスと現在自身 が保持しているアドレスが一致するか確認する。一致した場合は仮想アドレスの決定パター ンに基づき仮想アドレスの変更を行う。そして、新規参加ノードに対して仮想アドレスに不 整合がないことを伝える応答メッセージを送信し、それを受け取った新規参加ノードは仮決 定していた仮想アドレスを自分の仮想アドレスとして本決定し、ネットワークに参加でき る。ロックメッセージに含まれる仮想アドレスが一致しなかった場合は、新規参加ノードに 応答メッセージを返さない。新規参加ノードは予め決められた時間だけ応答メッセージの返 信を待ち、時間内に応答メッセージが返ってこなければ仮想アドレスの競合または不整合が – 14 – 3.3 仮想アドレス決定パターン 発生したと判断し、仮想アドレスの決定を最初からやり直す。この決定処理により複数の ノードが同時に参加しても仮想アドレスの競合や不整合が発生しない。 MBCR ではノードの故障やリンクの切断に対応できるように仮想アドレスの更新機能を 持つ。これは周期的に隣接ノードとの制御通信を行うことでリンクの切断を検知すること ができ、検知した場合は仮想アドレスの再決定を行う。また、その際の制御通信でやり取り した情報を保持しておくことで新規参加ノードの仮想アドレスの決定時間を短縮するメリッ トもある。リンクの切断の検知や仮想アドレスの再決定のために各ノードはビーコンパケッ トを周期的に隣接ノードに送信する。このビーコンパケットに含まれる情報は以下三つで ある。 • 所属している無線メッシュネットワークの ID • ビーコン送信元の MAC アドレス • ビーコン送信元の IPv6 形式の仮想アドレス 無線メッシュネットワークの ID はノードが参加している無線メッシュネットワークを識別 するために用いる。また、受信側ノードはこれらの情報以外に以下の情報を保持する。 • 受信時間 • 受信回数 • ビーコンの受信信号強度 ビーコンの受信信号強度は一定回数分の値をスタックに保持しておくことで一時的に受信信 号強度が大きく変動しても平均的な受信信号強度を算出することができる。リンクの切断の 検知は、ビーコンパケットを送信した際に予め設定した時間まで隣接ノードからの応答がな ければリンクが切断されたと判断する。仮想アドレスの再決定の手順は、まず自身の保持し ている仮想アドレスを破棄して、その後に新規参加ノードと同じ手順で仮想アドレスの決定 を行う。 – 15 – 3.4 経路制御 3.4 経路制御 MBCR では、各ノードは無線メッシュネットワーク内で一意な仮想アドレスを保持して おり、経路制御の際にはこの仮想アドレスを用いて経路制御を行う。経路制御の流れはま ず、送信元ノードは自身の仮想アドレスと宛先ノードの仮想アドレスの比較を行う。そし て、隣接ノードの中から宛先ノードに最も近いノードを特定し、そのノードにデータを送信 する。データを受け取ったノードは同じように自身の仮想アドレスと宛先ノードの仮想アド レスを比較し、隣接ノードの中から宛先ノードに最も近いノードへとデータを送信する。こ の処理を宛先ノードに到達するまで繰り返すことでデータを宛先に送信する。図 3.5 の場合 の経路制御を例として説明する。送信元ノードを S として、宛先ノードを C とする。まず、 Ϭ͘Ϭ Ϭ Ϭ͘Ϭ Ϭ͘ϲ Ϭ ϭ Ϭ͘Ϭ Ϭ Ϭ͘ϴ Ϭ ^ ϭ͘ϱ ϭ ඹ㏻䛾ᯞ 図 3.5 経路制御の例 ノード S はノード C の仮想アドレスと自身の仮想アドレスの比較を行い、宛先ノードが上 方向にあるか下方向にあるかを調べる。共通の枝の値を調べた結果、宛先ノードは上方向に あると判断し、上方向で宛先に最も近いノードへのデータを転送する。この場合、隣接ノー ドはノード B のみなのでノード B にデータを送る。データを受け取ったノード B は同じよ – 16 – 3.4 経路制御 うに仮想アドレスの比較を行い、ノード A にデータを送信する。ノード A も同様に仮想ア ドレスの比較を行い、今度は下方向にデータを送る必要があると判断し、下方向にある宛先 ノード C へデータを送信する。 このように、MBCR では仮想アドレスのみを用いて経路制御を行うことができる。しか し、MBCR で使用する仮想アドレスは MBCR 独自のアドレスであり、そのままの形では 宛先に IP アドレスを用いる既存のアプリケーションで使用することができない。そのため、 MBCR では仮想アドレスを既存のアプリケーションでも利用できるように MBCR を IPv6 を利用したネットワーク層とリンク層のクロスレイヤプロトコルとして利用することを想定 している。現状の MBCR では宛先の仮想アドレスを何らかの形で取得できると仮定して開 発を進めている。 – 17 – 第4章 拡張前の MBCR のシミュレー ション 本章ではこれまでに開発してきた MBCR が実環境で使用する際に十分な性能を発揮する ことができるかどうか確認するために、実環境での使用を想定していくつかのシミュレー ションを行った。無線メッシュネットワークでは様々なノードの配置が考えられるが、今回 はラダー配置、ランダム配置、グリッド配置の三つでのシミュレーションを行い、それぞ れの配置で性能が発揮できるか確認した。図 4.1 ラダー配置は梯子のようにノードのリン クを繋いだ配置であり、グリッド配置は格子状にノードを配置したものである。また、無 䜾䝸䝑䝗㓄⨨ 䝷䝎䞊㓄⨨ 図 4.1 ノードの配置例 線メッシュネットワークでは無線マルチホップでの通信を行うため、実環境では受信信号 強度の変化が発生すると考えられるので、受信信号強度が変動しても安定した性能が発揮 できるかシミュレーションを行った。最後にネットワーク間のゲートウェイに負荷が集中す る環境で性能を発揮できるかシミュレーションを行った。ネットワークシミュレータには QualNet6.1[10] を使用する。すべてのシミュレーションで共通の設定を表 4.1 に示す。無線 メッシュネットワークではマルチホップ通信を行うが、マルチホップ通信はホップ数が増え – 18 – 表 4.1 シミュレーション設定 ランダム配置 3000m × 3000m シミュレーション空間 グリッド配置 3000m × 3000m ラダー配置 8000m × 3000m ランダム配置 10∼50 ノード数 グリッド配置 4∼36 ラダー配置 10∼50 電波伝送モデル 自由空間 無線 lan 規格 IEEE 802.11b 自動レート制御 無効 データレート 11Mbps るほどデータパケットの到達率が下がっていく特性がある。そのため、一つの無線メッシュ ネットワーク内のノード数は最大 50 台までとしている。純粋に性能の評価を行うために伝 搬伝搬モデルに自由空間を用いており、さらにフェージングの影響を考慮しないように設定 している。比較対象として既存の無線メッシュネットワークの経路制御手法である HWMP を用いる。シミュレーションシナリオは、シミュレーション時間が 0 のときはノードを空間 上に 1 台配置しておき、このノードをルートノードとする。そこから一定時間ごとにノー ドを 1 台ずつ追加していく。これは、MBCR が木構造を構築する際にノードのネットワー クの参加順序が重要になっていることによる配慮である。また、実環境においてはすべての ノードが一斉に通信を行える状態になることは稀であると考えられるため、この動作を採用 している。ランダム配置に関しては新しく配置されるノードはすでに空間に配置されている ノードと直接通信できる範囲にランダムに配置される。すべてのノードが配置された後に ネットワーク内から宛先ノードと送信元ノードをランダムに決定し、アプリケーションプロ トコルである CBR(Constant Bit Rate) による非同期通信を規定回数実施する。CBR はア プリケーション層で動作するプロトコルであり、トランスポート層の UDP を用いて宛先に – 19 – パケットを送信する。UDP はパケットの転送中にパケットロスが発生しても再送を行わな い。つまり、不安定な伝送路でパケットを送信すると宛先までのパケットの到達数が少なく なる特性を持っている。CBR アプリケーションの設定を表 4.2 に示す。評価方法としては、 表 4.2 CBR の設定 送信時間 10 秒 送信レート 24 kbps パケットサイズ 300 byte 通信回数 300 パターン CBR のデータパケットの宛先への到達数と制御通信パケットの送信数での比較を行う。こ の到達数は送信元ノードのアプリケーション層で生成されたデータパケットが宛先ノードの アプリケーションで動作している CBR サーバに到達した数の総数をシミュレーションごと に記憶して計算している。 まず、三つのノード配置それぞれで性能を発揮できるか確認するシミュレーションの結果 を示す。ランダム配置での結果を図 4.2 と図 4.3 に示す。 縦軸がデータパケット到達数で ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ ϰϬ ϱϬ ,tDW 図 4.2 ランダム配置でのデータパケット到達数の比較 – 20 – ϵϬϬϬϬϬ ϴϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϳϬϬϬϬϬ ϲϬϬϬϬϬ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ 図 4.3 ϰϬ ϱϬ ,tDW ランダム配置での制御パケット送信数の比較 横軸がノード数となっている。図 4.2 から MBCR の方が HWMP よりも全体的にデータパ ケット到達数が多くなっていることが確認できる。また、図 4.3 からすべてのノード数にお いて MBCR の方が制御パケット送信数が少なくなっていることがわかる。次にグリッド配 置の結果を図 4.4 と 4.5 に示す。 グリッド配置においても MBCR は HWMP よりも全体 ϭϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϰ ϵ ϭϲ 䝜䞊䝗ᩘ DZ Ϯϱ ϯϲ ,tDW 図 4.4 グリッド配置でのデータパケット到達数の比較 – 21 – ϲϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϰ ϵ ϭϲ 䝜䞊䝗ᩘ DZ 図 4.5 Ϯϱ ϯϲ ,tDW グリッド配置での制御パケット送信数の比較 的にデータパケット到達数が多くなっていることが確認できる。また、図 4.5 からすべての ノード数において MBCR は HWMP よりも制御パケット送信数が少なくなっている。次に ラダー配置の結果を図 4.6 と 4.7 に示す。 図 4.6 からノード数が 20 までは MBCR の方が ϭϬϬϬϬϬ ϵϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϴϬϬϬϬ ϳϬϬϬϬ ϲϬϬϬϬ ϱϬϬϬϬ ϰϬϬϬϬ ϯϬϬϬϬ ϮϬϬϬϬ ϭϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ 図 4.6 ϰϬ ϱϬ ,tDW ラダー配置でのデータパケット到達数の比較 データパケット到達数が多いが、ノード数が 30 以上になると HWMP の方がデータパケッ – 22 – ϵϬϬϬϬϬ ϴϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϳϬϬϬϬϬ ϲϬϬϬϬϬ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ 図 4.7 ϰϬ ϱϬ ,tDW ラダー配置での制御パケット送信数の比較 ト到達数が多くなっている。制御パケット送信数においてはすべてのノード数で MBCR の 方が HWMP よりも少なくなっている。MBCR のデータパケット到達数がノード数 30 以 上で大きく下がる原因を調べた結果、仮想アドレス次元が 8 次元を超えたことにより性能が 下がったことが確認できた。仮想アドレス次元が 8 次元を超えたのは仮想アドレス決定の際 の評価に問題があるためである。本研究では仮想アドレスの評価方法を拡張し、ラダー型に も対応できるようにする。 次に受信信号強度が変動する環境でのシミュレーションについてである。受信信号強度の 変動はネットワーク内のいくつかのノードを定期的に移動させることで実現しているため、 ノードの配置はランダム配置のみで行う。シミュレーションの結果を図 4.8 と図 4.9 に示す。 図 4.8 から MBCR はノード数が少ないときは HWMP よりもデータパケット到達数が少 なく、ノード数が多いときは HWMP よりもデータパケット到達数が多くなっている。これ は、ノード数が多いときは受信信号強度が変動しても迂回路を用いて通信できる可能性が高 いからだと考えられる。図 4.9 から MBCR の方が HWMP よりも制御パケット送信数が少 ないことが確認できる。 最後にネットワーク間のゲートウェイに負荷がかかる状況のシミュレーションである。 – 23 – ϴϬϬϬϬ ϳϴϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϳϲϬϬϬ ϳϰϬϬϬ ϳϮϬϬϬ ϳϬϬϬϬ ϲϴϬϬϬ ϲϲϬϬϬ ϲϰϬϬϬ ϲϮϬϬϬ ϲϬϬϬϬ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ 図 4.8 ϰϬ ϱϬ ,tDW 受信信号強度が変動する環境でのデータパケット到達数の比較 MBCR ではゲートウェイを仮想木の原点とするため、最初に配置された 1 台をゲートウェ イと仮定する。このシミュレーションではノード数を 10 に固定し、CBR アプリケーション の送信元ノードはランダムに選ぶが、宛先ノードはすべてゲートウェイのノードとする。こ うすることでゲートウェイへの負荷集中を実現する。また、データパケットの送信数を変化 ϵϬϬϬϬϬ ϴϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϳϬϬϬϬϬ ϲϬϬϬϬϬ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ DZ 図 4.9 ϰϬ ϱϬ ,tDW 受信信号強度が変動する環境での制御パケット送信数の比較 – 24 – させてシミュレーションを行う。まず、ランダム配置での結果を図 4.10 と図 4.11 に示す。 䝷䞁䝎䝮㓄⨨䛾ሙྜ ϭϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ ϮϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ ,tDW 図 4.10 ゲートウェイに負荷がかかる状況でのデータパケット到達数の比較 1 䝷䞁䝎䝮㓄⨨䛾ሙྜ ϭϮϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ 図 4.11 ϮϰϬϬϬϬ ,tDW ゲートウェイに負荷がかかる状況での制御パケット送信数の比較 1 図 4.10 より、データパケットの送信数を変化させても MBCR の方が HWMP よりもデー タパケットの到達数が多いことが確認できる。図 4.11 からすべてのデータパケットの送信 数で MBCR の方が制御パケット送信数が少ないことが確認できる。次にグリッド配置での – 25 – 結果を図 4.12 と図 4.13 に示す。 グリッド配置においても MBCR は HWMP よりもデー 䜾䝸䝑䝗㓄⨨䛾ሙྜ ϭϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ ϮϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ ,tDW 図 4.12 ゲートウェイに負荷がかかる状況でのデータパケット到達数の比較 2 䜾䝸䝑䝗㓄⨨䛾ሙྜ ϮϬϬϬϬϬ ϭϴϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϭϲϬϬϬϬ ϭϰϬϬϬϬ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ 図 4.13 ϮϰϬϬϬϬ ,tDW ゲートウェイに負荷がかかる状況での制御パケット送信数の比較 2 タパケット到達数は多く、制御パケット送信数は少ないという結果になった。最後にラダー 配置での結果を図 4.14 と図 4.15 に示す。 ラダー配置においては MBCR はデータパケッ ト送信数が 60000 の時は HWMP よりもデータパケット到達数が多いが、それを超えると – 26 – 䝷䝎䞊㓄⨨䛾ሙྜ ϴϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϳϬϬϬϬ ϲϬϬϬϬ ϱϬϬϬϬ ϰϬϬϬϬ ϯϬϬϬϬ ϮϬϬϬϬ ϭϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ ϮϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ ,tDW 図 4.14 ゲートウェイに負荷がかかる状況でのデータパケット到達数の比較 3 HWMP よりも到達数が少なくなる。これはラダー配置ではノードの配置の特性上輻輳が起 きやすいからだと考えられる。HWMP は通信要求が発生してから、リンク品質が良い経路 を選択するのに対して、MBCR は受信信号強度に変化がない限り同じ経路を使うので結果 に差が出たと考えられる。図 4.15 より制御パケット送信数は HWMP よりも MBCR の方 䝷䝎䞊㓄⨨䛾ሙྜ ϭϰϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϲϬϬϬϬ ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖㏦ಙ⥲ᩘ DZ 図 4.15 ϮϰϬϬϬϬ ,tDW ゲートウェイに負荷がかかる状況での制御パケット送信数の比較 3 – 27 – が少ないことが確認できた。 シミュレーションの結果をまとめると、受信信号強度の変動が少ないような環境ではラン ダム配置、グリッド配置は既存の経路制御手法である HWMP よりも良い結果になった。し かし、ラダー配置の場合はノード数が多くなるとデータパケットの到達数が落ちて HWMP よりも少なくなった。受信信号強度の変動が発生する環境では、ノード数が多いときは結果 が良かったが、ノード数が少ないときは結果が悪かったため改善が必要である。ゲートウェ イに負荷がかかるような状況では MBCR はランダム配置、グリッド配置では安定した性能 が発揮できていたが、ラダー配置ではまだ安定した性能が発揮できていない。 本研究ではラダー配置のシミュレーションで発生した仮想アドレス次元が大きくなり、性 能が低下してしまう問題を解決するために仮想アドレス決定の際の隣接ノ―ドの評価方法を 拡張する。 – 28 – 第5章 拡張後の MBCR の仕様 本章では MBCR の拡張内容の説明を行った後、性能評価によってラダー配置での性能低 下の問題が改善されたかを確かめる。 5.1 隣接ノードの評価方法の拡張 MBCR では新規参加ノードが仮想アドレスを決定する際には隣接ノードの持つ情報を評 価し、仮想アドレスの決定元となる隣接ノードを選択する。この評価に用いられるのは隣接 ノードのツリー ID、隣接ノードからの受信信号強度、そして隣接ノードの枝上での位置で あると説明した。しかし、これら三つの評価ではノードの配置の仕方によっては最適な隣接 ノードが選ばれない場合がある。最適な隣接ノードが選ばれない場合の例を図 5.1 に示す。 図 5.1 はノードが数字の順に無線メッシュネットワークに参加し、現在ノード 3 まで参加し 0.5 1 䠎 䠐 䠒 䠔 ϭ 䠏 䠑 䠓 0.0 0.0 0 0 図 5.1 0.0 0.5 0 1 問題が発生するノード配置例 ている状況である。次に参加するのはノード 4 であるが、ノード 4 の隣接ノードはノード 2 とノード 3 の二つがある。ノード 4 はノード 2 とノード 3 の情報を先ほどの三つで点で評 – 29 – 5.1 隣接ノードの評価方法の拡張 価する。しかし、ここでノード 2 とノード 3 の評価が同じだった場合、ノード 4 の隣接ノー ド格納配列の先頭にあるノードが選ばれることになる。ここでは、仮想アドレス次元の増加 を防ぐために、アドレス次元の小さい隣接ノード 2 が選択されるのが最適である。だが、現 在の仕様ではノード 3 が選ばれる可能性があり、さらにノード 3 が選ばれた場合にはノード 5 が参加する際にはノード 3 から枝を分岐して参加することになり、これを繰り返していく とアドレス次元がどんどん増えていくことになる。先ほどのラダー配置のシミュレーション ではこの状況に陥ったためアドレス次元がどんどん増加して性能が低下する結果となった。 この問題を解決するために隣接ノードの情報を評価する際にアドレス次元数も評価するよ うに拡張する。アドレス次元数の評価はアドレス次元が低いほうを優先するようにする。こ の評価を加えた仮想アドレスの評価の処理のアルゴリズムを説明する。評価アルゴリズムの 擬似コードを図 5.2 に示す。新規参加ノードがノード 1, ノード 2、ノード 3 の三つの隣接 ノードの情報を保持しているとする。隣接ノードの情報はノード 1、ノード 2、ノード 3 の 順に格納されているとする。まず、新規参加ノードが格納している先頭の隣接ノード 1 を評 価する。最初に評価されるノード 1 を候補 3 にする。また、ノード 1 が Route MeshSTA か ら派生した仮想木であれば候補 2 にもする。さらに、ノード 1 が枝の端点であれば候補 1 に もする。続いて 2 番目に格納されている隣接ノード 2 を評価する。ノード 1 よりもノード 2 の受信信号強度が強ければ、ノード 2 を候補 3 とする。また、ノード 2 が Route MeshSTA から発生した仮想木かつノード 1 よりも受信信号強度が強ければノード 2 を候補 2 とする。 さらに、ノード 2 が Route MeshSTA から派生した仮想木かつ枝の端点かつノード 1 より も受信信号強度が強ければノード 2 を候補 1 とする。受信信号強度が同じでアドレス次元が 小さい場合もノード 2 を候補 1 とする。この処理を隣接ノード情報すべてで行う。最終的に 候補 1 が存在すればそのノードを仮想アドレスの決定元の隣接ノードとする。候補 1 が存在 しなければ候補 2 の隣接ノードを選択する。候補 2 にも存在しなければ候補 3 の隣接ノード を選択する。 なお、実環境では受信信号強度が同じになることは稀であるため、受信信号強度の差が一 定値以下ならアドレス次元の低い方を優先するようにする必要があると考えられる。この一 – 30 – 5.1 隣接ノードの評価方法の拡張 ೃ⿵ϭсEh>> ೃ⿵ϮсEh>> ೃ⿵ϯс㞄᥋䝜䞊䝗ሗϬ &KZEсϭƚŽ㞄᥋䝜䞊䝗ሗ⥲ᩘ /&ೃ⿵䠏͘ཷಙಙྕᙉᗘ х㞄᥋䝜䞊䝗ሗE͘ཷಙಙྕᙉᗘ ೃ⿵䠏 с 㞄᥋䝜䞊䝗ሗE E/& /& 㞄᥋䝜䞊䝗ሗE͘䝒䝸䞊/͊с୍ⓗ䛺䝒䝸䞊/ /&ೃ⿵Ϯ͘ཷಙಙྕᙉᗘ ф㞄᥋䝜䞊䝗ሗE͘ཷಙಙྕᙉᗘ ೃ⿵Ϯ с 㞄᥋䝜䞊䝗ሗE E/& /&㞄᥋䝜䞊䝗ሗE͘௬䜰䝗䝺䝇 сᯞ䛾➃Ⅼ /& ೃ⿵ϭ͘ཷಙಙྕᙉᗘ ф 㞄᥋䝜䞊䝗ሗE͘ཷಙಙྕᙉᗘ ೃ⿵ϭ с 㞄᥋䝜䞊䝗ሗE E/& /&ೃ⿵ϭཷಙಙྕᙉᗘ фс㞄᥋䝜䞊䝗ሗE͘ཷಙಙྕᙉᗘ ΘΘೃ⿵ϭ͘䜰䝗䝺䝇ḟඖ х㞄᥋䝜䞊䝗ሗE͘䜰䝗䝺䝇ḟඖ ೃ⿵ϭ с㞄᥋䝜䞊䝗ሗE E/& E/& E/& E&KZ /&ೃ⿵ϭ͊сEh>> ZdhZEೃ⿵ϭ >^/&ೃ⿵Ϯ͊с Eh>> ZdhZEೃ⿵Ϯ E/& ZdhZEೃ⿵ϯ 図 5.2 隣接ノード評価アルゴリズム 定値は実際の環境で実験を行い調べる必要がある。 – 31 – 5.2 拡張した MBCR の性能評価 5.2 拡張した MBCR の性能評価 拡張した MBCR をシミュレータに実装して性能評価を行う。シミュレーション諸元は表 5.1 に示す。ランダム配置、グリッド配置、ラダー配置それぞれで実施し、受信信号強度の 表 5.1 シミュレーション設定 シミュレータ Qualnet6.1 ランダム配置 3000m × 3000m シミュレーション空間 グリッド配置 3000m × 3000m ラダー配置 8000m × 3000m ランダム配置 10∼50 ノード数 グリッド配置 4∼36 ラダー配置 10∼50 電波伝送モデル 自由空間 無線 lan 規格 IEEE 802.11b 自動レート制御 無効 データレート 11Mbps 変動はない環境とする。3.5 節と同様でネットワーク内で送信元ノードと宛先ノードをラン ダムで選択し、CBR を用いてデータ送信を行いデータパケットの到達数と制御パケット送 信数を評価する。まず、ランダム配置の結果を図 5.3 と図 5.4 に示す。 ランダム配置におい ては拡張前と拡張後ではほとんど性能に変化は見られなかった。次にグリッド配置の結果を 図 5.5 と図 5.6 に示す。 グリッド配置では拡張前よりも拡張後の方がデータパケット到達数 が少なくなる場合があるという結果になった。これは評価の際の処理が増えたことによるも のだと考えられる。詳しい原因は調査中である。制御パケット送信数に関してはほとんど変 化が見られなかった。最後にラダー配置での結果を図 5.7 と図 5.8 に示す。 ラダー配置では 拡張前よりも拡張後の MBCR の方がすべてのノード数においてデータパケット到達数が多 – 32 – 5.2 拡張した MBCR の性能評価 ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϭϬ ϮϬ ϯϬ 䝜䞊䝗ᩘ ,tDW DZͺᣑᙇ๓ ϰϬ ϱϬ DZͺᣑᙇᚋ 図 5.3 ランダム配置でのデータパケット到達数の比較 ϵϬϬϬϬϬ ϴϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϳϬϬϬϬϬ ϲϬϬϬϬϬ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϭϬ DZͺᣑᙇ๓ 図 5.4 ϮϬ ϯϬ 䝜䞊䝗ᩘ ,tDW ϰϬ ϱϬ DZͺᣑᙇᚋ ランダム配置での制御パケット送信数の比較 – 33 – 5.2 拡張した MBCR の性能評価 ϭϰϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϮϬϬϬϬ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϰ ϵ ϭϲ 䝜䞊䝗ᩘ ,tDW DZͺᣑᙇ๓ Ϯϱ ϯϲ DZͺᣑᙇᚋ 図 5.5 グリッド配置でのデータパケット到達数の比較 ϲϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϰ DZͺᣑᙇ๓ 図 5.6 ϵ ϭϲ 䝜䞊䝗ᩘ ,tDW Ϯϱ ϯϲ DZͺᣑᙇᚋ グリッド配置での制御パケット送信数の比較 – 34 – 5.2 拡張した MBCR の性能評価 ϭϮϬϬϬϬ 䝕䞊䝍䝟䜿䝑䝖฿㐩ᩘ ϭϬϬϬϬϬ ϴϬϬϬϬ ϲϬϬϬϬ ϰϬϬϬϬ ϮϬϬϬϬ Ϭ ϭϬ ϮϬ ,tDW DZͺᣑᙇ๓ 図 5.7 ϯϬ 䝜䞊䝗ᩘ ϰϬ ϱϬ DZͺᣑᙇᚋ ラダー配置でのデータパケット到達数の比較 ϵϬϬϬϬϬ ϴϬϬϬϬϬ ไᚚ䝟䜿䝑䝖㏦ಙᩘ ϳϬϬϬϬϬ ϲϬϬϬϬϬ ϱϬϬϬϬϬ ϰϬϬϬϬϬ ϯϬϬϬϬϬ ϮϬϬϬϬϬ ϭϬϬϬϬϬ Ϭ ϭϬ DZͺᣑᙇ๓ 図 5.8 ϮϬ ϯϬ 䝜䞊䝗ᩘ ,tDW ϰϬ ϱϬ DZͺᣑᙇᚋ ラダー配置での制御パケット送信数の比較 – 35 – 5.2 拡張した MBCR の性能評価 くなっている。また、HWMP においてもすべてのノード数でデータパケット到達数が多く なっている。図 5.8 ではわかりにくいが、制御パケット送信数に関しては、拡張前の MBCR より拡張後の MBCR の方が制御パケット送信数が減っていることが確認できた。 以上の結果より、拡張後の MBCR は拡張前よりもグリッド配置において多少データパ ケット到達数が落ちているが、既存の経路制御手法である HWMP よりは良い結果となっ ている。また、ラダー配置では拡張後の MBCR はデータパケット到達数が増加しており、 HWMP よりも良い結果となった。 – 36 – 第6章 まとめ 本研究グループでは無線メッシュネットワークでのデータ転送効率の向上のための経路制 御手法 MBCR を提案してきた。本研究では、MBCR で実環境を想定したシミュレーショ ンをするなかで、ラダー配置のような特定のノード配置の際に仮想アドレスの決定に用いる 隣接ノードの選択に最適な隣接ノードが選ばれず、仮想アドレス次元が大きくなるという問 題を発見したので、その問題を解決するように拡張を行った。拡張内容は隣接ノードの情報 の評価に仮想アドレス次元の評価を加えたものである。拡張した MBCR のシミュレーショ ンを行いラダー配置のような特定のノード配置でも適切な隣接ノードの選択が行えるように なり、性能が向上したことを確認した。しかし、今回の拡張は特定のノード配置での仮想ア ドレス次元の増加を抑えるものであり、根本的な解決のためには仮想アドレス次元の決定ア ルゴリズム自体の改良や仮想アドレス次元が最大値を超えた場合の仕組みなどを考える必要 がある。 – 37 – 謝辞 本研究を進めるにあたり、ご指導を頂いた植田和憲講師に心から感謝致します。また、論 文の副査を引き受けてくださった濵村昌則教授、吉田真一准教授に心から感謝致します。お 世話になりました研究室のメンバーに心から感謝致します。 – 38 – 参考文献 [1] 高橋 武尊, 植田 和憲“ , 無線メッシュネットワークにおける初期経路確立手法の提案 ” 電子情報通信学会技術研究報告.ICM. 情報通信マネジメント,vol.109, no.463,pp.19- 24,mar 2010. [2] 丸岡 優大, 植田 和憲,“ WMN における隣接関係を考慮した経路制御手法の提案と性能 評価, ”マルチメディア通信と分散処理ワークショップ 2012 論文集,pp.43-50,Oct.2012. [3] Wataru Kobayashi, Kazunori Ueda, and Yuta Maruoka,“ Performance evaluation of routing method based on neighboring node information in WMN ”, NBiS 2015, pp424-431, Sept 2015. [4] 間瀬 憲一, 阪田 史郎, 「アドホック・メッシュネットワーク メッシュネットワークユビ キタスネットワーク社会の実現に向けて」, コロナ社,2007. [5] T.Clausen and P.Jacquet,“ Optimized Link State Routing Protocol(OLSR), ”IETF RFC3626,Oct.2003. [6] C.E.Perkins, E.Belding-Royer, and S.Das“ Ad Hoc On-Demand Distance Vector(AODV) Routing, ”IETF RFC 3561,July 2003. [7] M.Bahr,“ Proposed routing for ieee 802.11s wlan mesh networks, ”2006. [8] “ IEEE Standard for Information technology Telecommunications and information exchange between systems Local and metropolitan area networks Specific requirements Part 11:Wireless LAN Medium Access Control(MAC) and Physical Layer (PHY)Specifications, ”IEEE Std 802.11 2012. [9] Shizuya Irimoto, Yuta Maruoka, Kazunori Ueda, ”Performance evaluation of WMN routing methods considering amount of control packets” , ICMU 2015, pp80-81, Jan 2015. [10] S.N.technologies, “ Qualnet,”http://web.scalable-networks.com/content/qualnet – 39 – 参考文献 (2016/1/31 アクセス) – 40 –