Comments
Description
Transcript
0.6MB - 高知工科大学
平成 27 年度 学士学位論文 WMN の制御通信の削減を目的とした 経路制御手法の改良 Improvement of WMNs routing method for the purpose of reduction of control communications 1160365 矢野進也 指導教員 植田和憲 2016 年 2 月 29 日 高知工科大学 情報学群 要 旨 WMN の制御通信の削減を目的とした 経路制御手法の改良 矢野進也 本研究グループでは、無線メッシュネットワークの制御パケットの削減を目的とした経路 制御手法である MBCR を提案し、研究してきた。MBCR では独自の仮想アドレス情報を 生成することでネットワークに参加する。その仮想アドレスに必要な情報は隣接するノード のみで収集することができ、宛先への送信を行う場合も自ノードと隣接ノード、宛先ノード の仮想アドレスだけでパケットの経由が可能である。しかし、現在の MBCR では宛先ノー ドの仮想アドレスの取得方法が確立されていない。本研究では宛先仮想アドレスの取得方法 の確立を行う。 キーワード 無線メッシュネットワーク, MBCR(Multiple Branch Collection Routing) –i– Abstract Improvement of WMNs routing method for the purpose of reduction of control communications Shinya YANO Our research group have proposed MBCR that is WMNs routing method for the purpose of reduction of control communications. In MBCR, to participate in the network by generating its own virtual address. The information required for the virtual address can be collected only on the adjacent nodes. At the time of transmission to the destination, to determine via node based on only the virtual address of Own node and the adjacent node, the destination node. But, it is not established method of obtaining the destination node virtual address. It establishes a method for acquiring the destination node virtual address in this research. key words WMN(Wireless Mesh Network), MBCR – ii – 目次 第1章 はじめに 1 第2章 無線メッシュネットワーク 3 2.1 無線メッシュネットワークの概要 . . . . . . . . . . . . . . . . . . . . . . 3 2.2 無線メッシュネットワークの経路制御手法 . . . . . . . . . . . . . . . . . 5 2.3 HWMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 MBCR 8 3.1 MBCR の概要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 仮想アドレス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.1 仮想アドレスの要素 . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.2 IPv6 形式の仮想アドレス . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.3 仮想アドレスの決定パターン . . . . . . . . . . . . . . . . . . . . . 12 3.2.4 ビーコンを用いたネットワークへの参加 . . . . . . . . . . . . . . . 14 経路制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 研究内容 18 4.1 仮想アドレスの収集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 宛先仮想アドレスの取得 . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 シミュレーション 21 5.1 設定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.2 結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 まとめ 26 第3章 3.3 第4章 第5章 第6章 – iii – 目次 謝辞 27 参考文献 28 – iv – 図目次 2.1 無線メッシュネットワーク . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 RM-AODV の RREQ と RREP の送信 . . . . . . . . . . . . . . . . . . . 7 3.1 仮想アドレスによる木構造化 . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 仮想アドレスの要素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 IPv6 形式の仮想アドレスの内訳 . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 決定パターン 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 決定パターン 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.6 ビーコンを用いた仮想アドレスの決定 . . . . . . . . . . . . . . . . . . . . 15 3.7 送信方向が下方向となる例 . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1 上位ノードへの通知とノード情報の保持 . . . . . . . . . . . . . . . . . . . 18 4.2 上位ノードへの問い合わせ . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1 パケット到達数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 制御通信数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.3 制御通信数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.4 制御通信数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 –v– 第1章 はじめに 現在、無線通信の需要が高まっており、安定した無線環境への要求も高まってきている。 そして、無線メッシュシュネットワーク (WMN: Wireless Mesh Network) と呼ばれる、有 線で行われていたアクセスポイント間の通信を無線マルチホップ通信に置き換えることに よって通信を行うネットワーク技術が注目されている。 無線マルチホップ通信は目的となるノードと直接通信できない場合に、無線で他のノード を経由することによって目的となるノードまでパケットを送信する技術である。アクセスポ イントの設置を行う際に有線の敷設を不要とすることによりコストの削減が見込め、ネット ワークの拡張が容易に行える。また、自律的に経路を生成する特徴により、ノードの故障が 発生した場合に迂回路を形成することから耐障害性にも優れている。 しかし、無線メッシュネットワークではデータパケットを通信するために自律的に経由す るノードの決定を行うため、複雑な経路制御を行う必要がある。そのため、各ノードが相互 に経路制御のための情報をやり取りする制御通信が発生する。制御パケットは通常のデータ パケットと同じ帯域で通信されている。制御パケットが増加するとデータパケットとの衝突 の可能性が増加し、通信性能の低下が考えられる。そのため、制御通信の数を削減すること が出来れば、データパケットの到達率が向上し、配送効率を高めることが可能であると考え られる。 本 研 究 グ ル ー プ で は 、制 御 パ ケット の 削 減 を 目 的 と し た 経 路 制 御 手 法 で あ る MBCR(Multiple Branch Collection Routing) を提案し、研究してきた。MBCR では、仮 想アドレスと呼ばれる独自の位置情報を形成し、それを基にリンク状態を木構造で表現可能 にしている。新規参加ノードがネットワークに参加する際、隣接ノードとの制御通信だけで –1– 参加することができるため、制御通信の数を削減することが可能となる。また、経路制御に 必要となるのは、予め保有している自ノードと隣接ノードの仮想アドレスの他に宛先の仮想 アドレスのみでよいため、宛先仮想アドレスの取得が出来ればデータパケットの送信が可能 となる。 本研究グループでは、先行研究 [1] によって、MBCR の基本概念と仮想アドレスを用いた 仮想空間の定義が行われ、それを基に MBCR で使用する仮想アドレスの作成手法とその仮 想アドレスを用いたデータパケットの送信経路の決定手法を提案してきた [2]。また、ノー ドの故障やリンクの状態の変動が発生した場合にも対応できるように MBCR が拡張された [3]。この拡張に伴い追加されたパラメータの値を変化させることによって、性能にどのよう に影響を与えるかの検証も行われている [4]。 しかし、現在は経路制御に必要になる宛先仮想アドレスの取得方法が確立されておらず、 何らかの方法で取得できていることを前提として研究されている。本研究では、MBCR で の宛先仮想アドレスの取得方法の提案を行う。 –2– 第2章 無線メッシュネットワーク 本章では無線メッシュネットワークについての概要や経路制御についてを説明する。ま た、IEEE802.11s で標準経路制御手法として採用されている HWMP について説明も行う。 2.1 無線メッシュネットワークの概要 無線メッシュネットワークは無線マルチホップ通信を用いて無線アクセスポイント間の通 信を行う [5]。無線マルチホップ通信とは、送信ノードと宛先ノードの距離が遠い場合や障 害物によって通信が阻まれている場合などの理由で直接通信することが困難な状況におい て、他のノードを中継することによりデータパケットを宛先まで送信するネットワーク技術 のことである。従来の無線通信では、アクセスポイントとクライアントとの間のみで無線 のやり取りを行っており、アクセスポイント間の通信は有線インフラを敷設し、有線を介し て通信を行っている。無線メッシュネットワークはアクセスポイント間の通信を無線マルチ ホップ通信に置き換えているため、有線インフラの敷設に掛かっていたコストの削減が可能 となる。有線の敷設が不要であることから、震災などの理由から有線の敷設が困難な場合や 臨時的に無線ネットワークを構築したい場合に有用であると考えられる。また、ノードの故 障が発生した場合に中継することが可能なノードが他に存在していれば、迂回路を生成し通 信を継続することが可能なため、耐障害性にも優れている。 図 2.1 は無線メッシュネットワークの構成要素を示しており、無線メッシュネットワーク のノードは大きく分類すると 2 種類の役割を持っている。 Mesh STA, Root Mesh STA は無線メッシュネットワーク内の維持管理を行う、メッシュ –3– 2.1 無線メッシュネットワークの概要 ZŽŽƚDĞƐŚ^d ᭷⥺ DĞƐŚ^d DĞƐŚ^d DĞƐŚ^d DĞƐŚ^d ↓⥺䝯䝑䝅䝳䝛䝑䝖䝽䞊䜽 図 2.1 無線メッシュネットワーク 機能を持ったノードである。Mesh STA は無線マルチホップ通信を行い、無線メッシュネッ トワークの構築を行うノードのことである。Root Mesh STA は無線メッシュネットワーク 内と有線の先にある外部のネットワークを繋ぐ役割を持っている。現在、メッシュ機能を持 つ STA は、従来のメッシュ機能を持たない無線 LAN 端末である STA と直接通信しないこ ととなっている [6]。DS(distribution system) を介して無線メッシュネットワークと STA の構成しているネットワークは通信を行うことが可能となる。 無線メッシュネットワークは耐障害性や低コストなインフラ構築という面で注目されてい るが、経路制御が複雑になるという問題点がある。これは、無線による通信なため電波状況 が環境の影響で変動しやすく、データパケットを送信するためにリンク状態の変動に合わせ て、経由するノードを自律的に決定する必要があることから発生する問題である。そのた め、経由するノードの決定に十分な情報を取得するための通信をネットワーク内のノード同 士で行う必要がある。この通信のことを制御通信と呼び、制御通信でやり取りされるパケッ トのことを制御パケットと呼ぶ。制御パケットは通常のデータパケットと同じ帯域でやり取 りされるため、制御通信の数が増加すると、制御パケットと通常のデータパケットが衝突す る可能性も増加する。 –4– 2.2 無線メッシュネットワークの経路制御手法 2.2 無線メッシュネットワークの経路制御手法 無線メッシュネットワークでの経路制御手法には、大きく分類してリアクティブ型とプロ アクティブ型の 2 種類に分けることができる。 リアクティブ型の経路制御手法は、ノードがデータパケットを送信する前に制御通信を行 うことで経路情報を取得し、取得した経路情報から経由するノードを決定する。送信を行 う直前に経路情報を取得するため、最新の経路情報を基に通信でき、通信が発生しない場 合には制御通信を行う必要がないという利点がある。しかし、送信する前に経路情報を収 集するため、送信まで時間が掛かることが考えられる。代表的なリアクティブ型の経路制 御手法には、AODV(Ad hoc On-Demand Distance Vector)[7] や DSR(Dynamic Source Routing)[8] などがある。 プロアクティブ型の経路制御手法は、各ノードが一定間隔で制御通信を行うことでネッ トワーク状態を把握し、保持している経路情報を元に経由するノードを決定する。ノー ドが保持している情報を基に経由するノードを決定することにより、リアクティブ型の経 路制御手法に比べて送信開始までの時間を短くすることが可能である。しかし、データパ ケットの送信がない場合でも、経路の把握のために制御通信が発生する。代表的なプロア クティブ型の経路制御手法として OLSR(Optimized Link State Routing protocol)[9] や TBRPF(Topology Broadcast Based on Reverse-Path Forwarding)[10] などがある。 また、これら以外の経路制御手法にネットワーク内の各ノードから GPS などの機能を 用いて位置情報を取得し、この位置情報を基に経路を決定する経路制御手法も提案されて いる。このような経路制御手法の代表的な例として、GPSR(Greedy Perimeter Stateless Routing)[11] がある。 これまでに例として挙げたものは、無線マルチホップアドホックネットワークを構築する ために設計された経路制御手法である。無線メッシュネットワークでは、無線マルチホップ 通信を行うノードは無線アクセスポイントに限られるため、ノードの移動がほとんど発生し ないことを想定している。このことを考慮して無線メッシュネットワークに最適化した経路 –5– 2.3 HWMP 制御手法が現在までに複数提案されている [12]。 2.3 HWMP HWMP(Hybrid Wireless Mesh Protocol) は、無線メッシュネットワークの国際規格であ る IEEE802.11s で採用されている経路制御手法である。HWMP は、リアクティブ型である RM-AODV(RAdio Metric AODV) とプロアクティブ型である TBR(Tree Bace Routing) を状況に応じて使い分け、多様な無線メッシュネットワークの利用形態に対応できるように 設計された経路制御手法である。原点ノードが存在する場合はリアクティブ型とプロアク ティブ型のハイブリッドとして動作し、原点ノードが存在しない場合はリアクティブ型とし て動作する。RM-AODV と TBR についての説明を以下で行う。 RM-AODV はリアクティブ型の経路制御手法である。図 2.2 では、RM-AODV での挙 動を簡単に示している。RM-AODV による通信の宛先までの経路探索では、パケットの送 信要求が発生した際に、送信元となるノードが RREQ(Route Request) と呼ばれる制御パ ケットをブロードキャストする。ブロードキャストとは、不特定多数の相手に同時にデータ を送信することである。図 2.2 上側の S から A と B に向けて送信している部分に該当する。 RREQ を受け取った他のノードは、その RREQ にノード間のリンク品質の指標となるを 付与し、フラッディングを行う。フラッディングとは、接続しているノード全てにパケット を転送することである。図 2.2 上側の A と B が D に向けて送信している部分に該当する。 最終的な宛先まで RREQ が到達した場合、宛先ノードは RREP(Route Reply) と呼ばれる メッセージを RREQ を中継した通信経路で RREQ の送信元まで転送し、RREQ 送信元で は通信所要時間などのメトッリク情報を評価することによって最適な通信経路を決定する。 図 2.2 下側で行われている通信に該当する。これらの動作を経て、データパケットの送信を 開始する。RM-AODV ではノードが複数の無線デバイスインターフェースを持つ場合に、 それぞれのインターフェースごとの使用率を考慮してメトリックを決定することで無線通信 帯域の利用効率を向上させている。また、一度探索した経路情報を一定時間保持し続けるこ –6– 2.3 HWMP とによって経路探索のコストを抑えることが可能である。 ZZY ŵ͗ϱƉ͗^Ŷ͗ ^ ZZY䛾㏦ಙ ϱ ^ ㏦ಙඖ䝜䞊䝗 ϰ ϰ ϯ ZZY ŵ͗ϵƉ͗ ZZY ŵ͗ϳƉ͗ ZZY ŵ͗ϰƉ͗^Ŷ͗ ⤒⏤䝜䞊䝗 ᐄඛ䝜䞊䝗 ŵ ྛ䝸䞁䜽䛾䝯䝖䝸䝑䜽䛾 ⤒㊰ୖ䛾⥲ Ɖ ϭ䛴๓䛻⤒⏤䛧䛯䝜䞊䝗 ZZW䛾㏦ಙ ZZW ŵ͗ϵƉ͗ ZZW ŵ͗ϳƉ͗ ZZW ŵ͗ϵƉ͗Ŷ͗^ ^ ϱ 図 2.2 ZZY䝤䝻䞊䝗䜻䝱䝇䝖䛥䜜䜛 ไᚚ䝟䜿䝑䝖 ZZWZZY䜢୰⥅䛧䛯⤒㊰䛷 ㏦ಙඖ䛻䝴䝙䜻䝱䝇䝖 䛥䜜䜛ไᚚ䝟䜿䝑䝖 ϰ ϰ ZZW ŵ͗ϳƉ͗Ŷ͗^ Ŷḟ䛻㌿㏦䛥䜜䜛䝜䞊䝗 ϯ RM-AODV の RREQ と RREP の送信 HWMP において TBR は、無線メッシュネットワーク内に原点ノードが存在するときに 利用される。原点ノードとして設定されたノードは定期的に RANN(Route Announce) と 呼ばれるメッセージを送信し、他のノードは原点ノードから発行された RANN を再送する。 この動作により、ネットワーク内にツリー上の経路を作成し、通信時には作成した経路を基 にした経路決定を行う。ただし、RANN のみによって作成されるツリー上の経路はルート ノードを中心とした経路となるため、経路が冗長となる場合がある。その問題に対応するた めにも TBR では RM-AODV の RREQ を用いた経路の作成による、原点ノードを経由し ない経路の作成も可能である。 –7– 第3章 MBCR 本章では、本研究グループで研究されてきている MBCR について説明する。 3.1 MBCR の概要 MBCR(Multiple Branch Collection Routing) は、無線メッシュネットワークの制御通信 の削減を目的とした経路制御手法である。この経路制御手法の特徴として、ノード間のリン ク状態から独自のアドレスを生成し、通信の際にこのアドレスを用いることで経路制御を行 う。この仮想的なアドレスを仮想アドレスと呼び、図 3.1 のようにノード間のリンク状態を 木構造で表現可能にする位置情報としての役割を担っている。仮想アドレスを基に表現され る木構造を仮想木と呼び、無線メッシュネットワークの Root Mesh STA を原点として形成 される。 ZŽŽƚDĞƐŚ^d Ϭ͘Ϭ Ϭ Ϭ͘Ϭ Ϭ ௬䜰䝗䝺䝇 Ϭ͘ϳ ϭ Z Ϭ͘Ϭ Ϭ͘ϲ Ϭ͘Ϭ Ϭ Ϭ Ϭ Ϭ͘Ϭ Ϭ 図 3.1 ϭ͘ϰ ϭ Ϭ͘Ϭ Ϭ͘ϲ Ϭ͘ϵ Ϭ Ϭ ϭ 仮想アドレスによる木構造化 MBCR で通信を行うためには自身の仮想アドレスを保持している必要があり、Root Mesh STA 以外のノードは新規にネットワークに参加するときか、隣接ノードとのリンクが –8– 3.2 仮想アドレス 切断されて再び参加するときに仮想アドレスが付与される。隣接ノードとは、無線メッシュ ネットワークに存在しているノードであり、無線通信が直接可能なノードのことである。仮 想アドレスは新規参加ノードと隣接ノードが制御通信を行うことで決定される。また、経 路制御に必要な情報は自ノードと隣接ノード、宛先ノードの三種類の仮想アドレスのみであ る。このことから、仮想アドレスの決定までに必要な制御通信の数が少なく、送信元ノード が宛先仮想アドレスを取得できれば、経由するノードは送られてきたパケットから宛先仮想 アドレスを取得することで次に送信するノードを決定でき、制御通信の数を削減できる。 3.2 仮想アドレス MBCR の仮想アドレスは実際のノード間のリンク状態を木構造として表現可能にし、少 ない情報で経路制御を可能にするために用いられる。仮想アドレスが付与されるタイミング は、新規に参加するときとリンクを切断されたノードが再び参加するときの 2 パターンで ある。 3.2.1 仮想アドレスの要素 仮想アドレスを表現する情報は以下の 4 種類によって構成されている。 • 所属している木を表すツリー ID • アドレス次元 • ノードの端点情報 • 木の原点からの距離 所属している木のツリー ID は、無線メッシュネットワーク内に複数存在している木構造 を識別するための情報で、仮想木ごとに一意な値を使用する。ノードの端点情報、アドレス 次元、木の原点からの距離については図 3.2 を用いて説明を行う。また、図 3.2 は図 3.1 の ノード D を例にしている。 –9– 3.2 仮想アドレス 䜰䝗䝺䝇ḟඖ ௬䜰䝗䝺䝇 Ϭ͘Ϭ Ϭ͘ϲ Ϭ͘ϵ Ϭ Ϭ ϭ 䝜䞊䝗䛾➃Ⅼሗ Ϭ͘Ϭ Ϭ Ϭ͘ϲ Ϭ͘ϵ Ϭ ϭ ᮌ䛾ཎⅬ䛛䜙䛾㊥㞳 図 3.2 仮想アドレスの要素 アドレス次元は、最初は 1 次元であり、自ノードまでに仮想木が分岐した数と自身が分岐 した数を足し合わせた値になる。また、その最大値は 8 である。図 3.2 では、自身が枝とし て分岐していないため、自ノードまでに 2 回分岐していることが分かり、5 回まで分岐が可 能であることが分かる。 ノードの端点情報は、ノードが木構造上の端点である場合は 1、端点でない場合は 0 が記 入される。図 3.2 では端点情報に 1 が記入してあるため、このノードは端点であることが分 かる。 木の原点からの距離は、新規参加ノードと隣接ノードとの間の電波強度を基に推定される おおよその距離を算出し、ノード間の相対的な距離を足し合わせることで決定する。図 3.1 と図 3.2 から、ノード D は原点ノードの 1 回目の分岐から 0.6、そこからさらに 1 回分岐し た先から 0.9 の距離が離れていることが分かる。このように遠方のノードでも宛先の仮想ア ドレスが分かれば、大まかな距離値を推定することが可能である。仮想アドレスの決定の際 に、電波強度を基にしておおよその距離値を算出するには、式 3.2 を使用する。式 3.2 は式 3.1 のフリスの伝搬公式を変形したもので、ノードが無線通信の際に使用する電波の周波数 と電波を受信した際の受信電波強度によって距離値を算出する。 λ 2 Pr = Gt Gr Pt 4πd – 10 – (3.1) 3.2 仮想アドレス √ λ Pt (GtGr) d= 4π Pr drelative = (3.2) dreal dmax (3.3) まず、隣接ノードとの通信時に取得した電波強度 Pr [dBm] から式 3.2 を用いて自ノードと のおおよその距離 d[km] を計算する。式 3.3 にて、実際の電波強度を基に計算した dreal と 最大電波強度を基に計算した dmax から、相対的な距離 drelative を算出することで、仮想ア ドレスの決定の際に足し合わせる数値が求められる。 3.2.2 IPv6 形式の仮想アドレス MBCR では独自の仮想アドレスを用いて経路制御を行うため、既存の通信と併用する 場合、既存の通信に用いられている IP アドレスを利用することが出来ない。そのため、 MBCR では既存の通信と併用させるための方法として、128 ビットの IPv6 アドレスに変 換して利用する。 /Wǀϲ䜰䝗䝺䝇;ϭϮϴďŝƚͿ 䝥䝺䝣䜱䝑䜽䝇 ϴďŝƚ 䝒䝸䞊/ ϴďŝƚ ௬䜰䝗䝺䝇 ϭϭϮďŝƚ ௬䜰䝗䝺䝇;ϭϭϮďŝƚͿ ḟඖϭ ϭϰďŝƚ ḟඖϮ ϭϰďŝƚ ḟඖϯ ϭϰďŝƚ ḟඖϰ ϭϰďŝƚ ḟඖϱ ϭϰďŝƚ ḟඖϲ ϭϰďŝƚ ḟඖϳ ϭϰďŝƚ ḟඖϴ ϭϰďŝƚ ḟඖෆ䛾ሗ;ϭϰďŝƚͿ ➃Ⅼሗ ϭďŝƚ ᣦᩘሗ ϯďŝƚ ௬ᩘሗ ϭϬďŝƚ 図 3.3 IPv6 形式の仮想アドレスの内訳 図 3.3 を用いて IPv6 形式の仮想アドレスの内訳を説明する。IPv6 アドレスの先頭から 8 ビットはプレフィックスと呼ばれるネットワークを識別する値である。その 8 ビットの後 ろ 8 ビットを、仮想木を識別するためのツリー ID として利用し、残りの 112 ビットが仮想 – 11 – 3.2 仮想アドレス アドレスの情報値なる。各次元の情報は 14 ビットで表現され、8 次元まで枝情報を表現で きる。14 ビットの内訳として先頭 1 ビットを枝の端点情報として利用し、残りの 13 ビット が距離の値として扱われる。13 ビットの内 3 ビットは枝の距離の指数を表現し、残りの 10 ビットは枝の距離値の仮数として表現する。これにより、仮想アドレスの距離は式 3.4 で元 の数値に戻すことができる。 (距離値) = 2(指数情報) × (仮数情報) 3.2.3 (3.4) 仮想アドレスの決定パターン 仮想アドレスは仮想木によってリンク状態を表現できるようにするものであるため、付 与される仮想アドレスは木の延長か枝に分岐するようにしなくてはならない。そのため、 MBCR における仮想アドレスの決定には、新規参加ノードと隣接ノードのリンク状態から 2 つの決定パターンを用いて処理している。 Ϭ͘ϯ Ϭ 䝜䞊䝗ϭ䛜ཧຍ䛧䛯ሙྜ Ϭ͘ϴ Ϭ Ϭ͘ϴ ϭ ϭ ϭ͘ϰ ϭ ϭ 図 3.4 決定パターン 1 Ϭ͘ϯ Ϭ 䝜䞊䝗Ϯ䛜ཧຍ䛧䛯ሙྜ Ϭ͘ϯͮϬ͘Ϭ ϬͮϬ Ϭ͘ϴ ϭ Ϯ Ϯ ϭ͘ϰ ϭ Ϭ͘ϯͮϬ͘ϰ Ϭͮϭ ϭ 図 3.5 決定パターン 2 – 12 – 3.2 仮想アドレス 図??はパターン 1 の仮想アドレスの決定方法である。図??のように新規参加ノードの決 定元となるノードが木構造上の端点であった場合に選ばれるパターンで、新規参加ノードは 決定元となる仮想アドレスの距離値に、受信電波強度から算出される相対的な距離値を足し 合わせて仮想アドレスを決定する。また、そのときに決定元となったノードは自身の端点情 報を 0 にすることで、木構造上の端点でないことを分かるようにする。 図 3.5 はパターン 2 の仮想アドレスの決定手法である。図 3.5 のように新規参加ノードの 決定元となるノードが木構造上の端点でない場合に選ばれるパターンで、新規参加ノードは 決定元となる仮想アドレスに次元を増やし、新たな次元の距離値に受信電波強度から算出さ れる相対的な距離値を足し合わせて仮想アドレスを決定する。決定元ノードも新規参加ノー ドがネットワークに参加した際に、自身の仮想アドレスの次元を追加して距離値を 0.0 に設 定する。 この仮想アドレスの決定方法では、新規にネットワークに参加するノードと制御通信を行 うノードが隣接ノードのみで済むため、少ない制御通信の数でネットワークへの参加が可能 となる。これにより、従来の経路制御通信と比較して、制御通信の数を削減できる。 決定元となる隣接ノードが複数存在する場合、仮想アドレスの決定パターンがパターン 1 になるように決定元ノードを選択する。これは枝の分岐が発生により仮想アドレスのアドレ ス次元が増加してしまい、仮想アドレスの情報量も増加してしまうことを防ぐのが目的で ある。 仮想アドレス次元の増加を抑えた場合でも、リンクの切断が頻発する環境の場合、仮想ア ドレスの破棄が行われ、再決定の際にも分岐が発生するとアドレス次元が増加してしまう。 現在のアドレス次元の上限は 8 次元と設定されているため、8 次元を超える場合の具体的な 動作が決定されていない。過去の研究では、仮想木の再構築などを行うことで対応が出来る のではないかと提案がされていた。 – 13 – 3.2 仮想アドレス 3.2.4 ビーコンを用いたネットワークへの参加 MBCR におけるネットワークの参加についての手順を説明する。MBCR で仮想アドレ スの決定が発生するのは、新規参加ノードの発生時とリンクが切断されたノードの再決定時 である。また、リンクが切断されたノードの再決定の際には、それまで保持していた仮想ア ドレスの情報を破棄し、新規参加ノードと同じ動作でネットワークに参加することとなる。 MBCR では、新規参加時の仮想アドレスの決定や既存ノードのリンク切断の検知をするた めに、小さな情報を追加ビーコンパケットを用いた定期的な制御通信が行われている。ビー コンパケットに記載されている情報は以下のものである。 • ビーコン送信元の所属しているメッシュネットワークの ID • ビーコン送信元の MAC アドレス • ビーコン送信元の IPv6 形式の仮想アドレス 無線メッシュネットワークの ID はノードが参加している無線メッシュネットワークを識 別するために必要な情報である。ビーコン送信元の MAC アドレスはノードの識別に必要な 情報で、ビーコン送信元の IPv6 形式の仮想アドレスは木構造上でのノードの位置を把握す るのに必要な情報である。 一定周期で送信されてくるビーコンパケットを受信した隣接ノードは以下のような情報を 保持する。 • ビーコン送信元の所属しているメッシュネットワークの ID • ビーコン送信元の MAC アドレス • ビーコン送信元の IPv6 形式の仮想アドレス • 受信時間 • 受信回数 • ビーコン受信時の受信電波強度 – 14 – 3.2 仮想アドレス この中でもビーコン受信電波強度は直近から一定回数分の値を保持し、電波の変動が発生 した場合でも平均的な値を算出可能な状態にする。 ネットワークに参加するノードは、隣接ノードから送られてくるビーコンの情報を用いて 仮想アドレスの決定を行う。図 3.6 を用いて、ビーコンパケットを使った仮想アドレスの決 定処理を説明する。ネットワーク内の既存のノードは、ビーコンの送信を定期的に行ってい ᪤Ꮡ䝜䞊䝗 ᪂つཧຍ䝜䞊䝗 DZ䜢㛤ጞ 㞄᥋ሗ䜢㞟䛩䜛 䝍䜲䝬䞊䜢䝉䝑䝖 䝡䞊䝁䞁 䝡䞊䝁䞁௨እ䛾 ไᚚ䝟䜿䝑䝖 䝍䜲䝬䞊䜢⤊ ௬䜰䝗䝺䝇䜢௬Ỵᐃ 䝻䝑䜽䝍䜲䝬䞊㛤ጞ ;ϭͿ ௬䜰䝗䝺䝇䛾 ᭩䛝䛘 ;ϮͿ ௬䜰䝗䝺䝇䜢ᮏỴᐃ 図 3.6 ビーコンを用いた仮想アドレスの決定 る。新規参加ノードは、MBCR が有効になると隣接情報を収集するためにタイマーをセッ トして一定時間の間、隣接ノードのビーコン情報を収集する。タイマーが終了すると、ビー コン送信元の仮想アドレスや受信電波強度を指標とし、仮想アドレスの決定元となるノード を選択する。決定元ノードの仮想アドレスから、仮想アドレスの決定パターンを選択し、新 規参加ノードは仮想アドレスを仮決定する。仮決定された仮想アドレスと仮想アドレスの決 定元ノードのビーコン情報を、決定元ノードに対して送信する。この処理は図 3.6 の (1) で 送信される制御パケットである。図 3.6 の (1) では、受信した決定元ノードの仮想アドレス が変化してしまうことが考えられるため、受信した決定元ノードが他の新規参加ノードによ る制御パケットを受け付けないようにし、競合が起こることを防いでいる。図 3.6 の (1) を 受信した決定元ノードは、送信されてきたビーコン送信元の仮想アドレスが自身が持つ仮想 アドレスと一致することを確認し、一致する場合は決定パターンに応じて自身の仮想アドレ スを書き換える。自身の仮想アドレスの書き換えが成功した場合、新規参加ノードに仮想ア – 15 – 3.3 経路制御 ドレスの変更が成功したことを通知し、隣接ノードのリストにアドレスを分け与えたノード として追加する。この通知が図 3.6 の (2) である。通知を受け取った新規参加ノードは、通 知してきたノードを隣接ノードのリストに決定元ノードとして追加する。そして、新規参 加ノードはネットワークに参加し、既存ノードとしてビーコンパケットの送信を一定周期で 行う。 3.3 経路制御 MBCR では、各ノードの保有している仮想アドレスを基に経路制御を行っている。経路 制御に必要となる情報は自ノードと隣接ノード、宛先ノードの 3 種類の仮想アドレスのみで ある。宛先の仮想アドレスが分かれば、自身の仮想アドレスと比較して木構造上の上方向か 下方向かを判別することができ、方向さえ決まれば隣接ノードの仮想アドレスから適した経 由ノードの決定が行えるためである。 方向の決定についての具体的な説明を行う。宛先仮想アドレスが原点となるノードの場 合、送信方向は上となる。経由しているノードの仮想アドレスが原点のノードである場合、 送信方向は下となる。図 3.7 を例として、送信方向が下方向となる場合を説明する。 㠀ඹ㏻ḟඖ;ĚϭͿ ௬䜰䝗䝺䝇Ỵᐃึᮇ䛾ḟඖ;ĚϮͿ Ěϭ сĚϮ 䛾ሙྜ Ěϭ хĚϮ 䛾ሙྜ ㏦ಙඖ ௬䜰䝗䝺䝇 Ϭ͘ϬͮϬ͘ϰͮϬ͘ϱͮϬ͘Ϭ ϬͮϬͮϬͮϬ Ϭ͘ϬͮϬ͘ϰͮϬ͘ϱͮϬ͘Ϭ ϬͮϬͮϬͮϬ ᐄඛ ௬䜰䝗䝺䝇 Ϭ͘ϬͮϬ͘ϰͮϬ͘ϵͮϬ͘Ϭ ϬͮϬͮϬͮϬ Ϭ͘ϬͮϬ͘ϰͮϬ͘ϱͮϬ͘ϳ ϬͮϬͮϬͮϬ 図 3.7 送信方向が下方向となる例 d1 >= d2 (3.5) (送信元の [d1 ] 次元の値) < (宛先の [d1 ] 次元の値) (3.6) 式 3.5 と式 3.6 の両方を満たす場合に下方向へと送信される。式 3.5 の d1 と d2 が等しい とき、図 3.7 の左側のように送信元と宛先は木構造上の同じ枝に存在しており、式 3.6 とな – 16 – 3.3 経路制御 るときは宛先ノードが原点ノードよりも遠い位置にあるため、送信方向は下方向になる。式 3.5 の d1 が d2 よりも大きいとき、図 3.7 の右側のように送信元ノードで分岐した先に宛先 ノードが存在しているため、送信方向は下方向になる。また、式 3.5 の d1 が d2 よりも大き いときは、送信元の d2 より大きい次元の距離値が 0.0 となることから、式 3.6 の条件を満 たす。式 3.5 と式 3.6 を満たさない場合、送信方向は上方向となる。 上方向に送信される場合、送信元ノードは自身の仮想アドレスの決定元ノードを次ホップ ノードとして、送信を行う。下方向に複数の隣接ノードが存在する場合、d2 次元より低い次 元の距離値が全て共通しており、d2 次元の距離値が異なるノードを次ホップノードとして 決定する。 このように MBCR では、3 種類の仮想アドレスのみで経路制御が可能であることが分か る。しかし、今までの MBCR の研究は宛先仮想アドレスが何らかの方法で取得されること を前提に研究されており、宛先仮想アドレスの取得方法が未確立である。 – 17 – 第4章 研究内容 MBCR では、現在宛先仮想アドレスの取得方法が未確立である。本章では、本研究で提 案する宛先仮想アドレスの取得方法について説明を行う。 4.1 仮想アドレスの収集 MBCR における宛先仮想アドレスの取得を行うために、図 4.1 のように自ノード以下の 仮想アドレスの収集を行う機能を追加する。既存ノードによる新規参加ノードの仮想アドレ ZŽŽƚ DĞƐŚ^d ,䛾ሗ䜢ཎⅬ䝜䞊䝗䜎䛷㏻▱ ⤒⏤䛧䛯䝜䞊䝗䜒ሗ䜢ಖᣢ 䝛䝑䝖䝽䞊䜽䛻ཧຍ , ' 㞄᥋䝜䞊䝗 ㏻▱䛥䜜䜛䝜䞊䝗 ಖᣢ䛧䛶䛔䜛䝜䞊䝗ሗ & Z & ' , 図 4.1 ͕ Z͕ Z͕͕ ͕͕͕&͕'͕, & '͕, Z͕͕͕͕͕͕&͕'͕, Z͕͕͕& Z͕͕͕͕'͕, ͕' ͕͕' ͕, ͕͕, ͕& ͕͕& ͕& ͕' ͕, 上位ノードへの通知とノード情報の保持 – 18 – 4.2 宛先仮想アドレスの取得 スの決定が行われた際に、既存ノードは自身が原点ノードでない場合、図 4.1 の D のように 自身の上位ノードに新規参加ノードの情報を通知する。通知する内容は、新規参加ノードの MAC アドレスと IPv6 形式の仮想アドレスである。図 4.1 の原点ノードやノード B のよう に通知を受け取った上位ノードは、受け取った情報から自身以下の情報を保持しているリス トに追加し、自身が原点ノードでない場合は同様に上位ノードへと通知を行う。この処理を 原点ノードまで行うことによって各ノードは自身より下位のノードの仮想アドレスの情報を 保持していることとなる。 4.2 宛先仮想アドレスの取得 MBCR での宛先仮想アドレスの取得を行うにあたって、ノードを識別する情報を MAC アドレスとし、MAC アドレスを用いて宛先の仮想アドレスの取得を行う。送信を行いたい ZŽŽƚ DĞƐŚ^d ;ϭͿᐄඛ'䛻䛴䛔䛶 ၥ䛔ྜ䜟䛫 ' , ;ϮͿᐄඛ'䛻䛴䛔䛶 䛜▱䛳䛶䛔䜛䛯䜑 '䛾䜰䝗䝺䝇䜢㏉ಙ & 㞄᥋䝜䞊䝗 ㏻▱䛥䜜䜛䝜䞊䝗 ಖᣢ䛧䛶䛔䜛䝜䞊䝗ሗ Z & ' , ͕ Z͕ Z͕͕ ͕͕͕&͕'͕, Z͕͕͕͕͕͕&͕'͕, & '͕, Z͕͕͕& Z͕͕͕͕'͕, ͕' ͕͕' ͕, ͕͕, ͕& ͕͕& ͕& ͕' ͕, 図 4.2 上位ノードへの問い合わせ – 19 – 4.2 宛先仮想アドレスの取得 ノードは、宛先の MAC アドレスを基に自身が保持している情報の中に宛先仮想アドレスが ないかの確認を行う。宛先仮想アドレスを見つけることが出来た場合、その仮想アドレスを 基に送信を行う。宛先仮想アドレスが見つけられなかった場合、図 4.2 の (1) のように自身 の上位ノードに問い合わせ通知を行う。問い合わせ通知の際に送信する情報は自身の MAC アドレスと IPv6 形式の仮想アドレス、宛先の MAC アドレスである。問い合わせ通知を受 けた上位ノードも、自身が保有している情報の中に宛先仮想アドレスがないかの確認を行 う。宛先仮想アドレスを見つけることが出来た場合、通知されてきた送信元の情報を基に、 図 4.2 の (2) のように宛先の IPv6 形式の仮想アドレスを送信する。宛先仮想アドレスを見 つけられなかった場合、上位ノードに送られてきた問い合わせ通知を送信する。同様の処理 を原点ノードまで行うことによってネットワーク内の宛先仮想アドレスならば、宛先 MAC アドレスから取得することが可能となる。 – 20 – 第5章 シミュレーション この章では、本研究での研究対象の MBCR について、ネットワークシミュレータを用い た他のプロトコルとの性能の比較を行う。その際に QualNet と呼ばれるシミュレーターを 利用する。シミュレーションの環境設定として、すべてのシミュレーションで共通のものを 表 5.1 に表示する。 表 5.1 共通のシミュレーション設定 シミュレーション空間 電波伝送モデル 3000 × 3000 FREE-SPACE 最大電波到達距離 100 m 電波周波数 2.4 GHz 物理層プロトコル PHY802.11b 自動制御レート 無効 データレート 11 Mbps IP 層プロトコル IPv4 ルーティングの性能を比較するための対象は国際規格である IEEE802.11s で採用されて いる経路制御手法 HWMP を比較対象としている。 – 21 – 5.1 設定 5.1 設定 無線メッシュネットワークにおいて、電波強度がの変動がない環境でのシミュレーショ ンを行った。ノード数は 15 と 28 とし、ノード配置は固定して MBCR において分岐の 発生が多くなる配置と少なくなる配置で検討する。アプリケーションプロトコルである CBR(Constant Bit Rate) による非同期通信を規定回数実施する。CBR はアプリケーショ ン層で動作するプロトコルであり、ネットワーク層の UDP プロトコルによって宛先まで送 信される。UDP プロトコルは、送信されたパケットが途中で破損した場合に再送を行わな い。そのため、不安定な通信環境で送信するとパケットの到達率が低下する。表 5.2 に CBR 表 5.2 CBR の設定 送信時間 10 秒 送信レート 24 kbps パケットサイズ 300 byte 通信回数 100 パターン の設定を示す。シミュレーションの評価の指標として、制御通信の数とパケットの到達数を 使用する。 5.2 結果 まずは、疑似的な送信を行うことによって機能を実装した場合の制御通信の数やパケット の到達数を検討した。分岐が多いノード数 15、分岐が少ないノード数 15、分岐が多いノー ド数 28、分岐が少ないノード数 28 でシミュレーションを 20 回行い、その平均を取ったも のが図 5.1 と図 5.2 である。 図 5.1 はパケット到達数を表している図である。分岐が少ない場合の方がパケットの到達 率が少し向上するが図 5.1 からわかる。また、HWMP に比べてパケットの到達数が多いこ とから、宛先仮想アドレスの取得を行っても既存の経路制御よりも性能が向上することが予 – 22 – 5.2 結果 䝟䜿䝑䝖฿㐩ᩘ ϵϬϬϬϬ ϴϬϬϬϬ ϳϬϬϬϬ ϲϬϬϬϬ ϱϬϬϬϬ ϰϬϬϬϬ ϯϬϬϬϬ ϮϬϬϬϬ ϭϬϬϬϬ Ϭ DZ ,tDW ᭱䝟䜿䝑䝖ᩘ 図 5.1 パケット到達数 想できる。 図??は制御通信数を表している図である。制御通信の数が HWMP と比較して制御パケッ ϰϬϬϬϬϬ ไᚚ㏻ಙᩘ ϯϱϬϬϬϬ ϯϬϬϬϬϬ ϮϱϬϬϬϬ ϮϬϬϬϬϬ ϭϱϬϬϬϬ ϭϬϬϬϬϬ ϱϬϬϬϬ Ϭ DZ ,tDW ηZ&͊ 図 5.2 制御通信数 トの大幅に削減されている。また、分岐が多いものと分岐が少ないものの差があまりなく、 制御通信数が安定している。ノード数が増加すると定期的に制御パケットを送信するビーコ – 23 – 5.2 結果 ンの数が増えるが、HWMP のように開始時にブロードキャストするプロトコルと比較する と、ノードが増加しても上がり幅が控えめとなることが予測される。 次に、問い合わせ機能まで実装したシミュレーションで同様の検討を行い、図 5.3 と図 5.4 の結果により、図 5.1 と図 5.2 の近い形で実装することができた。 今後の課題として、 䝟䜿䝑䝖฿㐩ᩘ ϵϬϬϬϬ ϴϬϬϬϬ ϳϬϬϬϬ ϲϬϬϬϬ ϱϬϬϬϬ ϰϬϬϬϬ ϯϬϬϬϬ ϮϬϬϬϬ ϭϬϬϬϬ Ϭ DZ ,tDW ᭱䝟䜿䝑䝖ᩘ 図 5.3 制御通信数 ϰϬϬϬϬϬ ไᚚ㏻ಙᩘ ϯϱϬϬϬϬ ϯϬϬϬϬϬ ϮϱϬϬϬϬ ϮϬϬϬϬϬ ϭϱϬϬϬϬ ϭϬϬϬϬϬ ϱϬϬϬϬ Ϭ DZ ,tDW ηZ&͊ 図 5.4 制御通信数 – 24 – 5.2 結果 リンク切断時にノードリストから適切な仮想アドレスの削除を行い、リンクの変動がある環 境でのシミュレーションを検討している。 – 25 – 第6章 まとめ 本研究グループでは、無線メッシュネットワークにおける制御通信の削減を目的とした経 路制御手法を提案してきた。MBCR では、ノード間のリンク状態から独自の位置情報を表 す仮想アドレスを生成し、木構造で表現可能なネットワークを構築する。データパケットの 送信を行いたいノードは、自ノードと隣接ノード、宛先ノードの仮想アドレスのみで次ホッ プノードを決定できる。しかし、これまでの研究では宛先の仮想アドレスを取得できている ことが前提で研究されてきていたため、宛先仮想アドレスの取得方法が未確立であった。 本研究では、仮想アドレスの決定時に上位ノードへ新規参加ノードの情報を通知するこ とで、上位ノードは下位ノードの情報を保持し、木構造上の原点に存在するノードがネット ワーク全体の情報を把握可能にする。各ノードは自身が保持しているノード情報の中に宛先 の情報を持っていなくても、上位ノードに問い合わせることによってネットワーク上に存在 しているノードの仮想アドレスならば知ることが可能となる。 – 26 – 謝辞 本研究を行う上で多くのアドバイスをしていただいた植田和憲講師、梗概提出の際に貴重 な意見をいただいた横山和俊講師と浜村昌則講師、夜遅くまで協力していただいた M2 の小 林亘氏、研究の相談に乗っていただいた B4 の今田七海氏、入福優星氏、片岡裕貴氏、川田 圭人氏、山中俊哉氏に感謝します。 – 27 – 参考文献 [1] 高橋 武尊, 植田 和憲, 『無線メッシュネットワークにおける初期経路確立手法の提案 (nw 制御)』, 電子情報通信学会技術研究報告. ICM, 情報通信マネジメント, vol109, no.463, pp.19-24, Mar 2010. [2] 丸岡 優大, 植田 和憲, 『WMN における隣接関係を考慮した経路制御手法の提案と性 能評価』 マルチメディア通信と分散処理ワークショップ 2012 論文集, pp.43-50, Oct 2012. [3] Yuta Maruoka, Kazunori Ueda『A Method for Establishing Routes and IPv6 Addressing Based on the Estimated Distance from Neighboring Nodes in Wireless Mesh Networks』 2013 Workshops of 27th International Conference on Advanced Information Networking and Applications (WAINA), Mar 2013. [4] Wataru Kobayashi, Yuta Maruoka, Kazunori Ueda『Routing Method Based on Relationships between Neighboring Nodes in Wireless Mesh Networks』 2014 Workshops of 28th International Conference on Advanced Information Networking and Applications (WAINA), May 2014. [5] 間瀬 憲一, 阪田 史郎, 『アドホック・メッシュネットワーク -ユビキタスネットワーク 社会の実現に向けて-』 コロナ社, Sep 2007. [6] IEEE, 『Information technology - Information technologyTelecommunications 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』 Institute of Electrical and Electronics Engineers, Inc. 2012. [7] C. E. Perkins, E. Belding-Royer, and S. Das 『Ad Hoc On-Demand Distance Vector(AODV) Routing』 IETF RFC 3561, Jul 2003. – 28 – 参考文献 [8] D. Johnson, Y. Hu, and D.Maltz 『The Dynamic Source Routing Protocol(DSR) for Mobile AdHoc Netoworks for IPv4』 IETF RFC 4728, Feb 2007. [9] T. Clausen, and P. Jacquet, 『Optimized Link State Routing Protocol(OLSR)』 IETF RFC3626, Oct 2003. [10] R. G. Orier, F. Templin, and M.Lewis 『Topology Dissemination Based on ReversePath Forwarding(TBRPF)』 IETF RFC3684, Feb 2014. [11] H. Frey, 『Scalable geographic routing algorithms for ad hoc networks』 Network, IEEE, vol.18, no.4, pp.18-22, Jul-Aug 2004. [12] 阪田 史郎, 青木 秀憲, 間瀬 憲一 『アドホックネットワークと無線 LAN メッシュネッ トワーク (特集:無線アドホックネットワーク技術論文)』, 電子情報通信学会論文誌. B, 通信, vol.89, no.6, pp.811-823, Jun 2006. – 29 –