WMNにおける隣接関係を考慮した経路制御手法の提案と性能評価

WMN

における隣接関係を考慮した

経路制御手法の提案と性能評価

丸岡 優大

1,a)

_{植田 和憲}

1,b) 概要：ネットワークノードの故障に対する高いロバスト性や低コストでの無線アクセスポイントの設置を 可能にする等の利点を持つネットワークとして、無線メッシュネットワークが近年注目されている。しか し、現在の無線メッシュネットワークでは従来の無線ネットワークに比べ複雑なパケットの中継経路の制 御が必要であり、そのために多くの制御通信が発生し、データ通信中にパケットの衝突が発生する場合が ある。今までに本研究グループでは、この制御通信を減らすことを目的として、ノード同士の隣接情報と 独自の位置情報を含むアドレスを用いた無線メッシュネットワークの経路制御手法を提案してきた。本稿 では、以前提案した手法の独自のアドレスを使用したルーティングに関わる部分を一部変更し、データパ ケットの送信時に通信経路の探索を行わずにルーティングを行う手法を新たに提案する。また、本手法と、 既存のルーティング手法との制御通信数の比較をネットワークシミュレータを用いて行って、制御通信数 では既存のプロトコルより少ないという結果を得たが、データパケットの到達率では現時点では既存のプ ロトコルに劣るという結果を得た。

1.

はじめに

近年、無線デバイスを活用したネットワークの利用法に 関する研究が著しい。特にその中でも無線メッシュネット

ワーク(Wireless Mesh Networks)[1]は無線デバイスを利

用した新しい形のネットワークとして注目され、通信効率 の向上や利用方法に関する様々な研究が行われている。 無線メッシュネットワークとは、直接電波の届かない範 囲に存在するノードに対して通信を行うために電波の届く 範囲のノードを経由したパケットの中継を行うことで通信 を行うマルチホップネットワークの一種である。無線メッ シュネットワークでは、マルチホップ通信を行ためにノー ドとして無線アクセスポイントを想定しており、従来の有 線インフラによって接続されていた無線アクセスポイント 間の通信をマルチホップ通信で行う。これにより、通信の 際に複数経路を利用することによるネットワークの堅牢 化と、アクセスポイントの設置の際に有線インフラの敷設 を省略し、低コストでのアクセスポイントの設置を実現で きる。 しかし、無線メッシュネットワークのデメリットとし 1 _{高知工科大学}

Kochi University of Technology Kochi 782–8502, Japan a) _{[email protected]} b) _{[email protected]} て、データパケットを遠方のノードに対して送信する際の 経路制御が従来のインフラストラクチャ型ネットワーク に対して複雑になっており、経路決定制御に多くの制御通 信が発生してしまい、データ通信の帯域を圧迫する場合が ある。無線メッシュネットワークのデータパケット配送の 際の経路制御は無線の特徴を考慮したルーティングプロ トコルによって行われており、様々な特徴を持つ複数の手 法が現在までに提案されている。最近標準化が行われた IEEE802.11s[2]では複数のルーティングプロトコルを状況 によって使い分けることが可能なHWMP (Hybrid Wirelss

Mesh network routing Protocol)[7]と呼ばれるプロトコル

が採用されている。 本研究グループでは、少ない回数の制御通信でのルーティ ングを行うことが可能な無線メッシュネットワークルー ティング手法 MBCRを現在までに提案してきた。MBCR は制御通信の数を抑え、無線メッシュネットワークでの データ通信における通信帯域を向上することを目的として いる。MBCRでは、無線を使用した周辺ノードの探索を行 い、その結果を基にしてノードの隣接情報を生成する。ま た、この位置情報を独自のアドレスに置き換えてルーティ ングに使用することで、従来のルーティングプロトコルに 比べて少ない制御通信でのルーティングを実現する。これ まで、我々の研究グループではMBCRの基本的な動作[3] と、データ通信開始時に独自のアドレスを用いた通信経路

の探索を行い、その結果得られた通信経路を基にしたルー ティングを行う手法[4]を提案しているが、本稿では、通 信経路の探索を行わずに独自のアドレスを用いた通信を行 う仕組みについて提案を行う。また、ネットワークシミュ レータ上に今回提案する仕組みを用いたMBCRを実装し、 シミュレーションによりHWMPとの比較を行った結果を 示す。

2.

関連研究

本章では、本研究に関連する無線メッシュネットワーク について、その構造と要の技術であるルーティングについ て説明する。無線メッシュネットワークは、従来のインフ ラストラクチャ型無線ネットワークにおけるアクセスポイ ント間の有線による接続を無線によるマルチホップアド ホック通信に置き換えることで、複数の通信経路を使用し てネットワーク全体の堅牢性を高め、アクセスポイントの 敷設コストを低減することが可能なネットワークである。 本研究では、この無線メッシュネットワーク上で動作する ルーティングプロトコルについての手法の提案を行うこと から、以下では、無線メッシュネットワークの構成とこの ネットワーク上でのルーティングの役割並びに代表的な ルーティングプロトコルについて説明する。 2.1 無線メッシュネットワークの構造 無線メッシュネットワークにおける通信では、直接電波 の届かない範囲にあるノードに対して、電波の届く範囲に あるノードがパケットの中継を繰り返し、最終的な宛先と の通信を行う。このパケット中継のことをフラッティング と呼び、パケットの宛先までのフラッティングを行うノー ドはルーティングプロトコルにより決定される。無線メッ シュネットワークを構成するノードは、表1に示すとおり、 機能と用途別にMPP, MP, MAP, STAの4種類が定義さ れている。これらのノードを使用した無線メッシュネット ワークの構成例を図1に示す。無線メッシュネットワーク では、STAノード以外のノードがマルチホップアドホッ ク通信による通信を行うと規定されている。無線メッシュ ネットワークとマルチホップアドホックネットワークとの 違いは、マルチホップアドホックネットワークがすべての 端末でアドホック通信を行うことを想定しているのに対し、 無線メッシュネットワークでは、アドホック通信を行う端 末の種類が限定されている点である。また、マルチホップ アドホックネットワークではすべてのノードを対等な関係 で扱うことが想定されているが、無線メッシュネットワー クでは、ネットワーク制御の中心となるルートノードを設 定可能な場合がある。そのため、ルートノードの設定する ことが可能な条件を考慮して、フラッティングによるネッ トワークへの負荷を抑えたルーティングプロトコルが現在 までに複数提案されている。それらについては次節で説明 表1 無線メッシュネットワークのノード種別

Table 1 Node types on WMNs

MP(Mesh Point) メッシュを利用して通信を行うノー ド。メッシュ上でメッシュパケット の中継が可能なノード。 MPP(Mesh Portal) MPに外部ネットワークへのゲート ウェイの機能を付与したもの。有線 ネットワークとの接続点に用いられ る。

MAP(Mesh Access Point) MPにメッシュ機能を持たないノー

ド(STA)を接続するためのアクセ スポイントとしての機能を提供する。 STA(station) メッシュ機能を持たないノード。従 来のインフラストラクチャ通信によ りMAPをアクセスポイントとす ることで通信を行う。 ↓⥺࣓ࢵࢩࣗࢿࢵࢺ࣮࣡ࢡ ᭷⥺ࢿࢵࢺ࣮࣡ࢡ 㻹㻼㻼 㻹㻼 㻹㻼 㻿㼀㻭 㻹㻭㻼 㻹㻼 㻿㼀㻭 図1 無線メッシュネットワークの例 Fig. 1 Example of WMNs する。 2.2 ルーティング 無線メッシュネットワークにおけるルーティングプロト コルは現在までに複数のものが提案されているが、大きく 分けてリアクティブ型とプロアクティブ型の2種類に大別 可能である。 リアクティブ型ルーティングプロトコルは、ノードから データパケットの送信要求が発生した際に、ネットワーク の通信経路をフラッティングにより探索し、経路を決定す るプロトコルである。この方式では、通信を行わないノー ドはフラッティングを行わないため、通信の宛先が少な いネットワークでは有効な方法である。しかし、データパ ケットの送信要求が発生したタイミングで経路探索を行う ため、データパケット送信までの遅延が大きいという問題 点がある。 プロアクティブ型ルーティングプロトコルは、ネット ワークの作成時から経路情報をフラッティングにより作成 し、定期的に経路情報を各ノードが交換し合うことで経路 情報を保持する手法である。この手法では、データパケッ

トの送信要求が発生した際に即座に通信を開始すること が可能であるが、定期的に経路情報を交換する為のフラッ ティングが発生し、ネットワーク負荷となるという問題が ある。以下では、無線メッシュネットワークにおける主な ルーティングプロトコルを紹介する。 2.2.1 HWMP

HWMP (Hybrid Wireless Mesh network Protocol)は、

最近標準化された802.11sにおいてルーティングプロト コルとして採用されているプロトコルである。HWMPで は、無線メッシュネットワーク内にルートノード(MPP) が設定されていない状態では、RFC3561で勧告されてい るAODV[5]を無線メッシュネットワーク向けに仕様変更 したRM-AODVプロトコルによるリアクティブ型のルー ティング動作を行う。また、無線メッシュネットワーク 内にルートノードが設定されている場合には、TBR (Tree Base Routing)プロトコルによるプロアクティブ型のルー ティング動作を行う。これらの動作は、ネットワーク別に 任意に設定が可能であり、利用方法に応じたプロトコルを 選択可能である。例えば、リアクティブ型の動作では経路 作成にかかるコストは少ないが、グッドプットはわずかに プロアクティブ型に劣る[8]など、HWMPでは動作によっ て特性に違いが発生する。また、ノード配置やパラメータ の変更によってもスループットやパケットの配送遅延に違 いが生じることから最適なパラメータについては現在も議 論が行われている[9]。 2.2.2 RA-OLSR

RA-OLSR (Radio Aware - Optimized Link State Rout-ing)は無線メッシュネットワークを対象としたプロアク ティブ型のルーティングプロトコルである。マルチホップ アドホックネットワークを想定したルーティングプロトコ ルOLSR[6]をベースとしており、経路情報を各ノードで共 有する際に、MPRと呼ばれる経路情報の再送信を行うノー ドを選出することで、必要最小限のパケット中継で経路情 報を共有することが可能となっている。また、RA-OLSR では、無線メッシュネットワークにおけるMAPが収容し ているSTAの情報が経路情報として新たに加えられてい る。この情報はLAB(Local Association Base)と呼ばれ、 各STAからのパケットの送受信の為のルーティングに使 用される。

3.

MBCR

について

本章では、我々の提案するルーティング手法MBCRに ついて説明する。以下の説明のうち、特に記述のないもの は先行研究により定義されていた仕様について記述して いる。 3.1 概要

MBCR (Multiple Branches Collection Routing)は無線

㻭 㻮 㻯 㻱 㻭 㻮 㻯 㻰 㻱 㻲 㻰 㻲 ࣀ࣮ࢻࡢᐇ㓄⨨ 0%&5 ࡟ࡼࡿᮌᵓ㐀⾲⌧                   図2 MBCRによる木構造の例

Fig. 2 Example of tree structure by the MBCR メッシュネットワークにおいて、ルーティング制御に使用 する制御通信を減らすことを目的としたルーティングプロ トコルである。本手法は、ネットワーク上の各ノードが独 自の位置情報を保持し、通信時にこの独自の位置情報を利 用することで少ない制御通信でのルーティングを行う。こ の独自の位置情報を仮想アドレスと呼び、ネットワークへ の参加時に各ノードが仮想アドレスを決定して通信を行う ため、プロアクティブ型のルーティング手法に近い手法と なる。 仮想アドレスは個々のアドレスがネットワーク上のある 1台のノードを頂点とする木構造での位置情報を数値で表 現した構造となっている。仮想アドレスの詳しいフォー マットは後述するが、個々の仮想アドレスは木構造上での 場所によって値が変わるため、ネットワーク上で重複する 可能性は極めて低く、ノードの識別としても利用可能であ る。MBCRを利用したネットワークではネットワークに参 加するすべてのノードは必ず1つ以上の仮想アドレスを保 持する。ネットワークに新たに参加するノードは、自ノー ドの新しい仮想アドレスを生成する際に隣接ノードのみと 通信するだけで新しい仮想アドレスを生成することが可能 であるため、ネットワークに参加する際に遠方のノードに 対してフラッティングによるネットワークへの参加を通 知する通信を行う必要がなく、少ない制御通信でのネット ワークへの参加を可能としている。以下に現在のMBCR で使用している仮想アドレスと仮想アドレスを利用した ルーティングの詳細を説明する。 3.2 仮想木 MBCRで利用している仮想アドレスは、特定のネット ワーク上の特定のノードをルートノードとした木構造に よってノード同士のリンク状態を表現している。図2は、 あるノード配置と、配置を基にして生成したMBCRの仮 想アドレスで表現される仮想木を表現したものである。仮 想アドレスは図3で示すフォーマットにより表現する。こ のフォーマットの上段の数値は、ルートノードからの相対 的な距離を小数点数で表現しており、この値を基にルート ノードからのおよその距離を推定可能である。

















1.6 0.5 0.9 ௬᝿ⓗ࡞㊥㞳್ ᯞࡢ➃Ⅼ᝟ሗ ௬᝿࢔ࢻࣞࢫ ࢔ࢻࣞࢫḟඖ 図3 仮想アドレスの構造

Fig. 3 Structure of the virtual address

この数値は、まず隣接ノードとの通信時に取得した電波 強度Pr[dBm]から隣接ノードとの相対的な距離d[km]を 式(2)により計算し、仮想アドレスを求める際には電波強 度を取得したノードの持つルートノードとの距離と足し合 わせることにより決定する。この値は、ノードとノードの 間の物理的なメートル距離を相対的な距離で表現したも のとなっており、一度おおよその物理的なメートル距離を 算出する計算を行い、その後相対的な距離を計算する。式 (2)は、式(1)のフリスの伝搬公式の変形であるが、ノード が無線通信で使用する電波の周波数と、電波を受信した際 の受信電波強度によってノード間のおおよその距離を推定 する式となっている。隣接ノードとの相対的な距離は、こ の式により得られたノード間のおおよその物理距離を、式 (3)を用いて電波の受信強度として最大値を使って計算し た最大の電波の到達物理距離で正規化したものである。 Pr Pt = GtGr  λ 4πd 2 (1) d = λ 4π × Pt(GtGr) Pt (2) drelative= dreal dmax (3) 現在の仕様では、フリスの伝搬公式を基にした計算式の 下で相対的な距離を算出しているが、フリスの伝搬公式が 電波の干渉や空気の透過による電波減衰のない理想的環境 を想定している式であるため、実空間における使用では相 対的な距離の算出に影響を及ぼすことが想定できる。現在 はフリスの伝搬数式に基づいた相対的な距離の決定を行っ ているが、別の物理距離の推定式を利用した相対的な距離 の算出についても現在検討中である。 図3で示すフォーマットの下段の数値は、1か0の値で、 その仮想アドレスが木構造の枝の末端であるかどうかを示 すのに利用している。この数値が1の場合は、その仮想ア ドレスが木構造中で枝の末端であることを示し、0の場合 は他に枝の末端が存在する事を示している。 また、フォーマットのそれぞれの上下1対の数値は、木 構造上での1本の枝の情報となっており、木構造での枝 㻳 㻯 㻱 㻳 㻱 㻰 㻲 㻰 㻲 ཧຍᚋ                                   ࣃࢱ࣮ࣥ  ࣃࢱ࣮ࣥ  図4 仮想アドレスの決定パターン

Fig. 4 The patterns for determining virtual address

の分岐数として読み取ることが出来る。木構造での枝の分 岐数は、ルートノードからの距離と枝の末端情報の一対の 数によって表現される。仮想アドレスでの枝は上段の(1) ノード間の相対的距離と下段の(2)枝の末端を示す情報の 一対で1本の枝の状態を表しており、木構造で枝の分岐が 発生した際には、それまでの仮想アドレスを継承するため にアドレスのコピーを行い、コピーの右側に分岐元のノー ドをルートノードとした新しい仮想アドレスを付与する。 この付与された仮想アドレスの数のことを仮想アドレスの 次元数と呼んでおり、新たに新しい仮想アドレスを付与す る動作を仮想アドレス次元の増加と呼んでいる。 以下で、この仮想アドレスを隣接ノードとの通信によっ て決定する手法を説明する。 3.3 アドレスの決定方法 MBCRがルーティングの際に用いる仮想アドレスは、 ノードがネットワークに参加した際に、既にネットワーク に参加している隣接ノードとの仮想アドレスと電波強度 を取得する通信により決定する。仮想アドレスは、木構造 でノード間のリンク状態を示したものであるため、新たに ネットワークに参加するノードは木構造の枝の延長もしく は枝の分岐による仮想アドレスの割り当てを行う必要があ る。この仮想アドレスの決定では、新たにネットワークに 参加するノードとその隣接ノードの位置関係により2つの パターンの仮想アドレスの決定手法を使用している。以下 にそれぞれの仮想アドレス決定パターンを示す。 パターン1は、新たに木構造の枝を延長して枝の末端に 新規参加ノードを追加するようなパターンである。このパ ターンは図4の(2)に示すように、新しくネットワークに 参加するノードの隣接ノードが枝の端点を保持していた場 合に使用する。具体的には、新しくネットワークに参加す るノードは、枝の端点を保持している隣接ノードのルート ノードからの距離を継承するために仮想アドレスをコピー し、隣接ノードとの相対的な距離の数値を仮想アドレスの 数値に足し合わせて新しい仮想アドレスとする。また、仮 想アドレスのコピー元の隣接ノードは、木構造の端点では

なくなるため、仮想アドレスの端点情報を非端点となるよ うに変更する。 パターン2は、図4の(1)に示すように、新しくネット ワークに参加するノードが同じ枝に所属する2台以上の隣 接ノードの中間に配置されていた場合の仮想アドレスの決 定パターンである。この場合、新しくネットワークに参加 するノードは隣接ノードの1台を選んで、そのノードを新 しい枝の原点とする枝を生成する。仮想アドレスのコピー 元の隣接ノードは、木構造の新しい枝の原点となるため、 原点を表す新しい次元を仮想アドレスに付与する。 MBCRでは、これらの2つのパターンを使用してノー ドがネットワークに参加する際に仮想アドレスの決定を行 う。これらの仮想アドレスの決定では、新規にネットワー クに参加するノードが通信を行うのは隣接ノードのみであ るため他のプロアクティブ型のルーティングプロトコルと 比較して、狭い範囲での無線通信のみでネットワークに参 加することが可能である。従って、従来の手法より少ない 制御通信でのノードのネットワークへの参加を可能として いる。 3.4 ルーティング 本研究グループの以前の提案では、データパケットの送 信要求が発生した地点での仮想アドレスと木構造を用いた 通信経路の探索を行っていたが、本稿では以前の研究結果 を見直し、新たなデータパケットの配送を行う新たな手法 について提案を行う。この手法では以前使用していた経路 探索を使用しなくとも通信を可能である。以下では以前に 提案した手法との違いと、今回新たに提案する手法につい て解説する。 3.4.1 経路情報 現在の一般的な無線メッシュネットワークプロトコルで は、各ノードはネットワーク内の他のノードの物理アド レス(MACアドレス)とそのノードまでの経路を関連付け た通信経路テーブルを様々な形で保持している。例えば RA-OLSRでは、MPRを担当するノードがネットワーク内 の他のノードの物理アドレスと経路情報のテーブルを保持 しており、通信を行うノードは通信の宛先の物理アドレス をMPRに問い合わせれば、宛先までの通信経路が確立す る仕組みとなっている。以前に我々が提案した手法では、 この物理アドレスと経路情報のテーブルを通信の要求が発 生したタイミングで作成するために、MBCRの仮想アドレ スを用いた効率的なすべてのノードへのパケットのブロー ドキャストが可能である特長を活かし、MBCRの木構造 上にネットワーク全体に宛先物理アドレスの探索パケット を送信して通信経路を確立する仕組みをとっていた。しか し、事前の通信経路の作成にはデータパケットを送信する までのオーバーヘッドが発生することや、通信経路を得る ためだけに仮想アドレスと木構造を利用するのでは、制御 通信の削減効果が乏しいものとなるという結論に至った。 そこで、この手法は副次的に利用するものとし、MBCRが 利用する仮想アドレスによる情報で通信経路の決定を行っ た場合に最も効果の表れる使用方法を検討した。今回新 たに提案する手法では、経路探索を行わずに、アプリケー ションで通信を利用する場合に仮想アドレスをIPv6アド レスに変換した値を用いることで、通信を行う手法の提案 を行う。 3.4.2 データパケットの送信 今回新たに提案する手法では、MBCRの仮想アドレス 情報を用いて仮想アドレスの情報のみからデータパケット の次ホップノードの決定を行い、データパケットの配送を 行う。この手法では、以前に提案した通信経路の事前探索 を行わないため、経路探索にかかる制御通信を削減するこ とが可能であり、また、データパケットの送信までにかか る遅延をなくすことが可能としている。ただし、以前の手 法では経路探索によってネットワーク全体の中からアプリ ケーションによって指定されたIPアドレスを持つノード とそのノードまでの経路を得ることが可能であったが、こ の経路探索を行わない場合には、通信の開始時にノードが 持つ情報は仮想アドレスのみとなるため、一般的な通信は 行えない。そこで、今回提案する手法では、通信の宛先の 識別に仮想アドレスとIPv6アドレスを組み合わせること で、アプリケーションで宛先の設定を行えるネットワーク を実現する。 IPv6はIPv4に代わる新しいネットワークのアドレッシ ング体系として現在普及を進めている段階にあるプロトコ ルであるが、IPv4にはなかった概念として、膨大にある アドレス空間からネットワークへのブロック単位のアドレ ス割り当てや、エニーキャストアドレスを用いた近接ルー ターの探索などの機能を持っている。今回提案する手法で は、アプリケーションからの他のノードとの通信時には、 宛先情報としてIPv6のアドレスを指定することを前提と している。IPv6アドレスは128ビット(16ビット×8)の 範囲の値を持つアドレスであるが、提案手法では先頭の数 ビットをネットワークを識別するためのプレフィックスと して使用し、残りのビットに仮想アドレスを埋め込む。埋 め込み方として、仮想アドレスの各アドレス次元を16ビッ トの情報で表現すれば、プレフィックスを16ビットであ ると考えても、7次元の仮想アドレスをIPv6アドレスに 埋め込むことが可能であると考えている。現状、仮想アド レスの次元数がネットワークのノード数やノードの発生パ ターンでどの程度の大きさまで増加するかが不明であるた め、各アドレス次元を何ビットの情報にするかは未定であ るが、この手法を用いることで、仮想アドレスをIPv6ア ドレスとして表現する。この仮想アドレスを基に生成した IPv6アドレスをネットワークへの参加時に、各ノードが生 成し、通信の際には宛先情報としてアプリケーションで指

定することで、通信開始時に、宛先ノードの仮想アドレス 情報を得ることが可能である。 この宛先ノードの仮想アドレス情報を基にして、MBCR では宛先ノードまでのデータパケットの中継ノード決定を 行う。仮想アドレスを用いたルーティングでは、上位レイ ヤーからのデータパケットの配送要求が発生した地点で、 宛先のノードの仮想アドレスと自ノードの仮想アドレスを 比較して、次にデータパケットを転送するノードの決定を 行い、データパケットを送信する。この際、データパケッ トの転送の前に通信経路の確保などは行わず、直接データ パケットを中継ノードに転送するため、AODVのような通 信開始前の大きなオーバーヘッドが発生しない利点がある。 MBCRの仮想アドレスによる次ホップノードの決定方 法では、データパケットの送信ノードは、自ノードと最 終的なデータパケットの宛先の仮想アドレスの参照を行 う。仮想アドレスの各次元の仮想距離の差を計算すること で、宛先までのおおよその距離を計算する。計算結果で宛 先が1ホップ以上離れていると判定した場合、MBCRは 自ノードの周囲に隣接しているノードの仮想アドレスを参 照し、隣接しているノード内で木構造で考えた場合に最も 宛先までの距離の短いノードの選出を行う。そして、選出 したノードに対し、データパケットの転送を行う。データ パケットを受信した隣接ノードは、再度自ノードと宛先の 仮想アドレスの参照と各次元の仮想距離差を計算し、最も 最終的な宛先に近いノードを次ホップノードとして決定す る。MBCRではこれらの処理を繰り返すことで仮想アド レスを用いて最終的な宛先までのデータパケットの転送を 可能にする。 3.5 課題と今後の実装 現在研究を行っているMBCRのプロトコル仕様は以上 までのものである。しかし、現在のMBCRの仕様では、 他プロトコルに対して少ない制御通信数以外のフレキシビ リティやロバスト性の面では劣っていると考えている。例 えば、現状のMBCRのルーティングでは木構造を利用し てノード間のリンク状態を表現し、仮想アドレスとして利 用することで、データパケットの転送ノードの決定を行っ ているが、木構造で表したノード間リンクが必ずしもデー タパケットの送信ノードと受信ノードの間の最短距離にな るとは限らない。そのため、現状のMBCRでは他プロト コルより場合によっては多くのデータパケットの中継を行 う可能性が考えられる。我々の研究グループでは、この問 題の解決方法として、無線メッシュネットワーク上のいく つかのノードに対して木構造の原点ノードを割り当てて、 ネットワーク上に複数の木構造を生成する手法を現在考 えている。この手法では、ネットワークの各ノードは別々 のノードを原点とする複数の仮想アドレスを保持し、ルー ティングの際に、最も宛先のノードに近いノードに対して データパケットの中継を行わせる。これにより、通信経路 を現状のMBCRより短縮することが可能であり、現状よ りデータパケットの中継回数の少ない通信を行うことがで きるようになると考えている。また、複数経路をとるよう な通信に対してもこのMBCRの拡張により可能に出来る と考えている。 また、MBCRの仮想アドレスをIPv6アドレスに変換す る際に各アドレス次元に何ビットの情報を割り当てるべき かを検討していく必要があると考えている。各アドレス次 元に割り当てるビット数を減らせば、ネットワークで表現 可能な仮想アドレス次元の範囲を拡大することが可能であ るが、仮想距離を表現する値の範囲が狭くなるため、どの 程度のビット数が適切であるかを今後シミュレーションな どにより考えていくつもりである。 以上の仕様は現在検討中の仕様であるが、今後、これら の機能の追加によりMBCRのフレキシビリティやロバス ト性を向上可能であると考えられる。

4.

シミュレーション

本章では、提案手法のMBCRが他プロトコルに対して どの程度の有効性があるのかを検証した結果を示す。検証 の為に、現在決定している仕様を基にしたMBCRをネッ トワークシミュレータのQualNet[10]上に実装し、HWMP のRM-AODVを比較対象としたシミュレーションを行っ た。ただし、現在のMBCRの実装では、仮想アドレスを IPv6アドレスに変換する機構を設定していないため、宛 先ノードの物理アドレスと仮想アドレスを相互変換できる テーブルを用意し、そのテーブルを用いて、データパケッ トの送信要求が発生した地点で宛先ノードの仮想アドレ スを得るようにした。また、現在のMBCRの仕様では、 ノードの移動やノードの故障に対応する機能が実装されて いないため、これらが発生しない環境を想定してのシミュ レーションを行っている。それぞれの項目での結果を以下 に示す。 4.1 パケット到達数による比較 MBCRによるルーティングでは、木構造を基にした通信 経路が作成されるため、実際にはあまり距離の離れていな いノード同士でも木構造の生成工程によっては、余分な迂 回経路を通るような通信経路となってしまう場合がある。 無線メッシュネットワーク上の通信では、ノード同士の通 信が衝突したり、通信を行う距離が離れすぎていた場合 には電波減衰によってデータパケットが損失してしまう。 このため、通信経路の違いによってデータパケットのパ ケット到達率に変化が生じる。この通信経路の違いによる データパケットの到達率の違いを明らかにするために、無 線メッシュネットワーク内のノード間でCBR (Constant Bit Rate)プロトコルでのデータ通信を行うシナリオを作

表2 シミュレーション条件 Table 2 Simulation condition

ノード数 10, 20, 30, 40, 50, 60 ノードの配置 ノードとノードの間隔が、ノードが 通信可能な距離以上にならないよう にランダムに生成 CBRの通信回数 20, 80 CBRの送信レート 1Mbps CBRの送信時間 10 sec 成し、宛先まで到着できたパケット数の測定を行った。測 定結果を図5に示す。シミュレーション結果から、MBCR とHWMPにおいて、無線メッシュネットワーク内でデー タパケットを実際に転送した際に、ルーティングの違いに よってパケット損失の発生数の違いを見て取ることがで きる。 シミュレーションに用いた条件は表2の通りである。無 線メッシュネットワーク内のノード数を設定し、すべて のノードの中からランダムな通信ペアによる通信を行い、 データパケットの到達数を測定するシミュレーションを 行った。図5の結果は、ノード数、CBRによる通信回数 を変えた試行をそれぞれ5回のずつ行った場合の平均値 を集計したものである。シミュレーションを実施している ノードの配置と通信を行う通信ペアやランダムシード、そ の他のアプリケーションの条件等については、MBCRと RM-AODVで同一である。 図5の結果より、データパケットの到達数はHWMPの ほうが現状のMBCRより高いことがわかる。通信数を変 えてみた場合においては、通信数が増加するにしたがって MBCRの方がHWMPに比べて劣っていることが見て取 れる。また、ノード数の変化によって、HWMPではある程 度ノード数が増えてもパケット到達数の下落は少ないが、 MBCRにおいてはノード数が増えた場合にパケット到達 数の下落がやや著しいことがわかる。これは、ルーティン グにより決定した通信経路がMBCRでは冗長となってい ることに起因しているものと考えられる。現状のMBCR による経路の決定では、1本の木構造を基に経路の決定を 行っているため、HWMPの複数の経路とメトリックを考 慮した上での経路の決定手法に比べデータパケットを転送 する経路が冗長となり、ノード間でのホップ中にデータパ ケットの損失が発生する割合が高くなる。また、MBCR は木構造で別の枝のノードと通信する場合は、一旦共通の 枝のノードを経由する通信経路を作成するため、ノード数 が増えて木構造の枝の末端までの距離が伸びてくると、共 通の枝のノードを経由する際に経路が冗長となりデータパ ケットの損失が発生している。今後この問題の解決のため にMBCRで複数の木構造を基にした経路決定手法を定義 していきたいと考えている。 0 50000 100000 150000 200000 250000 10 20 30 40 50 60 ࣃࢣ ࢵ ࢺ ᩘ ࣀ࣮ࢻᩘ 䝟䜿䝑䝖㏦ಙᩘ(80㏻ಙ) HWMP(80㏻ಙ) MBCR(80㏻ಙ) 䝟䜿䝑䝖㏦ಙᩘ(20㏻ಙ) HWMP(20㏻ಙ) MBCR(20㏻ಙ) 図5 データパケットの到達数の比較結果

Fig. 5 Simulation result of arrival number of data packet

4.2 制御パケット数による比較 無線メッシュネットワークにおいてデータパケットの転 送を行う際に各プロトコルがどの程度の制御通信を行っ ているのかを比較するシミュレーションを行った。このシ ミュレーションでは、ルーティングプロトコルが通信経路 の決定を行うために使用する制御通信の量を明かにする ために、先のパケット到達率の測定と同条件で特定数の 無線メッシュネットワーク内のノードを設定し、その中 からランダムに選出したノード同士を通信させるシミュ レーションシナリオを使用して各ノードがルーティング の為の制御通信として使用した制御パケットの送信数を 集計している。シミュレーション条件は、表2と同じであ るが、この集計対象として、MBCRでは仮想アドレスの 決定と隣接ノードへの仮想アドレスの通知に使用する制 御パケット数の合計を使用し、HWMPのRM-AODVで は、RREQ/RREP/RERR/RREP-ACKの4種類の制御パ ケット送信数の合計を使用している。 シミュレーション結果を示したものが図6である。結果 として、制御パケットの送信数ではMBCRの方がHWMP に比べて、極めて少ない制御パケット数で通信経路の決定 を行っている事がわかる。この結果は、HWMPがデータ パケットの送信要求が発生した地点で制御パケットを使用 して通信経路を探索して通信経路の決定を行っているのに 対し、MBCRの通信経路の決定は仮想アドレスの決定の みで行えることが顕著な差として表れている。ただし、今 回のシミュレーションでは、MBCRがノードの移動や故 障に対応した仕様を定義しておらず、それらを考慮しない 環境でのシミュレーションを行っている。現状のMBCR のルーティングの際に使用する仮想アドレスの決定は隣接 ノードとの通信のみによって行われているため、通信可能 状態にするまでの初期通信の制御パケット送信数は非常に 少ないが、実際の無線メッシュネットワークでは、ノード の移動や故障が相当の頻度で発生することは明らかである。 これらを考慮した場合、MBCRでも定期的な仮想アドレ スの更新機構などが必要であり、MBCRの制御パケット

数も通信回数あるいは、シミュレーション時間の増加に比 例して多くなることが予想できる。 0 5000 10000 15000 20000 25000 30000 35000 40000 10 20 30 40 50 60 ㏦ಙࣃࢣ ࢵ ࢺ ᩘ ࣀ࣮ࢻᩘ HWMP(㏻ಙᩘ80) HWMP(㏻ಙᩘ20) MBCR(㏻ಙᩘ20䞉80) 図6 制御パケット数による比較結果

Fig. 6 Simulation result of the control communication number

上記のシミュレーション結果から、現状のMBCRでは 最適な環境においては、制御パケット数が既存プロトコル に比べて少ないことが分かったが、データパケットの到達 率に関しては、通信経路の決定方法の関係から既存プロト コルに劣っていることが分かった。しかし、今後の拡張に よりデータパケットの到着率については、データパケット の中継回数を減らして、中継によるデータパケットの損失 を少なくすることで現状より向上することが可能であると 考えられ、またノードの移動や故障への対応は可能にでき ると思われる。我々の研究グループでは、今後ノードの移 動や故障を考慮した仕様の設計を行い、これらの状況に対 応できるようにすることを考えている。

5.

まとめ

本研究では、無線メッシュネットワークの制御パケッ ト数の削減を目的としたルーティングプロトコルである MBCRについて、新たな仮想アドレスを用いたルーティン グ手法の提案とシミュレータへの実装を行った。無線メッ シュネットワークでは、ルーティングには複雑な制御とそ のための通信が多く発生し、データパケット転送の際のス ループットの低下につながる場合がある。本研究で提案し てきたルーティングプロトコルMBCRは、無線メッシュ ネットワークの各ノードの配置を木構造で捉え、木構造上 に位置し、木構造上の位置を独自のアドレスである仮想ア ドレスによって表現することでルーティングの際の通信経 路を明確に決定し、少ない制御通信でのルーティングを可 能にしている。本稿では、以前提案した木構造を用いた通 信経路の探索を行った上での通信経路の確立を行う手法を 改め、各ノードのアプリケーションが宛先情報としてIPv6 アドレスを指定する形でのMBCRの利用に絞り、IPv6ア ドレス内に仮想アドレスを埋め込むことでの通信を行う手 法の提案を行った。また、IPvsMBCRをシミュレータ上 に実装し、既存のプロトコルとの比較実験を行った結果を 示した。シミュレーション結果では、MBCRは既存の無線 メッシュネットワークプロトコルHWMPよりルーティン グ時の制御パケット数が少ないという結果を得た。しかし、 ネットワーク全体のデータパケットの到達率ではHWMP に対してMBCRは到達率が低いという結果となった。こ れは、MBCRによるルーティングによって決定した経路 がHWMPに比べて冗長になることが原因で、パケット中 継の過程でデータパケットの損失が発生しているためであ ると考えられる。 参考文献

[1] Ian F. Akyildiz, Xudong Wang, A Survey on Wireless Mesh Networks, IEEE Communications Magazine, vol. 43, no. 9, Sep 2005.

[2] ”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) specifica-tions Amendment 10: Mesh Networking,” IEEE Std 802.11s-2011 (Amendment to IEEE Std 802.11-2007 as amended by IEEE 802.11k-2008, IEEE 802.11r-2008, IEEE 802.11y-802.11r-2008, IEEE 802.11w-2009, IEEE 802.11n-2009, IEEE 802.11p-2010, IEEE 802.11z-2010, IEEE 802.11v-2011, and IEEE 802.11u-2011) , vol., no., pp.1-372, September 2011.

[3] Takeru Takahashi, Kazunori Ueda, Proposal of initial route method for wireless mesh networks , 2010-03-ICM ,vol.109, no.463, pp.19-24, March 2010.

[4] 丸岡優大,植田和憲,無線メッシュネットワークにおける

隣接関係を考慮した経路確立手法の有効性検証,マルチメ

ディア通信と分散処理ワークショップ2011論文集, 2011,

18–24, September 2011

[5] C. Perkins, E. Belding-Royer, S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC 3561, July 2003. [6] T. Clausen, P. Jacquet, Optimized Link State Routing

Protocol (OLSR), RFC 3626, October 2003.

[7] Michael Bahr, Proposed Routing for IEEE 802.11s WLAN Mesh Networks, 2nd Annual International Wireless Inter-net Conference (WICON), MA, USA, August 2006. [8] Cornils, M. and Bahr, M. and Gamer, T., Simulative

analysis of the Hybrid Wireless Mesh Protocol (HWMP), Wireless Conference (EW), 2010 European, April 2010. [9] M. Guesmia, M. Guezouri and N. Mbarek, Performance

evaluation of the HWMP proactive tree mode for IEEE 802.11s based Wireless Mesh Networks.

[10] Scalabe Network Technologies, QualNet Developer, http://www.scalable-networks.com/products/qualnet/, 2010/05/05.