無線メッシュ網のチャンネル割当手法
研究代表者

吉 廣 卓 哉

和歌山大学システム工学部 准教授

1 はじめに無線メッシュ網（Wireless Mesh Networks: WMN）は、メッシュ状に接続された無線ノードで構成される通信ネットワークである。有線インフラストラクチャへの依存を減らすことにより、低コストで広域のブロードバンドインターネットアクセスを実現する技術として注目されている[1] [2]。高度な無線技術の開発により、マルチチャネル無線（Multi-Channel Multi-Radio: MCMR）技術は、WMN のネットワーク性能を大幅に向上させることが可能である[3-7]。 MCMR 無線メッシュ網では各ノードに複数の無線インタフェースが装備されており、各インタフェースには 1 つの周波数チャネルが割り当てられる。単一チャネル、または単一インタフェースの場合と比較して、MCMR はネットワーク容量を大幅に増強し、柔軟な接続を提供し、隣接リンク間の干渉を低減することができる。費用が少なく、展開が容易なため、MCMR WMNs には一般的な IEEE802.11デバイスが使用されることが多い。しかし、各メッシュノードで使用可能なネットワークインターフェースカード（NIC）の数、および使用可能な直交チャネルの制限（IEEE802.11 2.4GHz 帯では直交周波数チャネルは 3 つしか確保できない）を考慮すると、多くのリンクが同じチャネル上で動作することを余儀なくされるため、無線リンク間で深刻な干渉が発生する。各ノードの各無線インタフェースカードに適切にチャネルを割り当ててネットワーク性能を最大化することは有用な最適化課題である。チャネル割り当てアルゴリズム
は、干渉の影響を軽減するためにノードのインタフェースに異なるチャネルを割り当てる必要があるだけでなく、転送経路を確保できるように各リンクのチャネルを選択する必要がある。したがって、チャネルの割り当てとルーティングを組み合わせることで、効率的なチャネル割当手法を設計できる。しかし、現在の技術水準では、３〜４のチャネルでフレーム衝突のない経路制御を考慮したチャネル割当方式は提案されていない。本研究の目標は、IEEE802.11 で実用的な WMN を実現する高度に最適化された、経路制御機能を含んだチャネル割り当てスキームを設計することである。
一般に、干渉を最小限に抑えるためのチャネル割り当ては、Conflict Graph と呼ばれるモデルに基づいて行われる。Marina 他は、MCMR WMN の干渉を抑えたチャネル割り当て（CLICA）アルゴリズムを提案した[8]。
この手法は、Conflict Graph の下で干渉の影響を最小限に抑えることを目的として、チャネルを無線インターフェースに割り当てる。チャネル割り当て問題は NP 困難であることが知られているため、著者らは干渉リンクペアの数を最小限に抑えるための発見的アルゴリズムを提案した。しかし、この手法では 3〜4 チャネルの衝突のない伝送を実現できていない。
我々は、直交するチャネル数を 3〜4 に制限した場合でも、MCMR WMN に対する衝突のない静的チャネル割り当てを実現する手法 CASCA（CSMA-Aware Static Channel Assignment）スキームを提案した[9]。 CASCA
は Conflict Graph ではなく、CSMA の動作を考慮した干渉モデルを導入している。これにより、キャリア検知範囲内にある 2 つのリンクが同じチャネルを使用できるようになる一方で、隠れ端末問題の原因となる 2つのリンクは異なるチャネルを使用する。隠し端末の問題による悪影響を排除するために、CASCA はルーテ
ィング機能を部分的に導入する。つまり、パケットを転送するリンクの集合から一部を除外すると同時に、任意の送信元と宛先のノードペアに対して経路の存在を保証する。ただし、CASCA は完全に自由な経路制御を許していないため、トラフィックエンジニアリングの観点で柔軟性に欠ける。つまり、CASCA は通信パターンの変動に対応できず、入力された通信要求の変動下で一部のリンクの過負荷を容易に引き起こす。
本研究では、所与の通信要求の下でトラフィックエンジニアリングを考慮して、3〜4 個の直交チャネルで衝 突 の な い チ ャ ネ ル 割 り 当 て を 実 現 す る 、 新 た な 経 路 制 御 を 含 ん だ チ ャ ン ネ ル 割 当 方 式 TACCA（Traffic-demand Aware Collision-free Channel Assignment）を提案する。チャネル割当問題は NP 困難であるため、CASCA は問題を PMAX-SAT（部分 MAX-SAT）問題として定式化する。しかし、PMAX-SAT はバイナリ値（0/1 の値）を処理するが、実数値は処理できない。このため、通信要求を処理するために、問題を混合整数線形計画問題（MILP）として数学的に定式化し、リンク容量、干渉、利用可能な無線インタフェースの数、チャネルなどを組み込む。本研究の貢献を以下に示す。
1）CASCA に通信要求配列を導入し、MILP フレームワーク内でチャネルの割り当てと経路制御の両方を実行

1
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

する問題を定式化する。ここで、通信要求配列は静的に定義するが、通信用級は時間とともに動的に変化することを断っておく。実際には、通信要求の変動は短期的にはそれほど大きくないため、時間変化を包含する通信容量を設定する（例えば、最大通信容量を通信要求配列として入力するなど）ことで、この問題は静的な通信要求でも解決可能である。
2）「CSMA 対応」の共有リンク容量モデルを新たに導入する。これにより、CSMA の特性を利用してリンク容量の計算とトラフィックエンジニアリングを行う。ネットワークの性能を最適化するための経路制御においては、チャネル割り当てと連動する容量モデリングが不可欠である。CSMA 対応の干渉モデルでは、キャリア
センス範囲内のリンクに同じチャネルを割り当てることができる。この場合、CSMA の特性により、これらのリンクはキャリアセンス範囲内のリンク容量を共有することになる。
3）我々の知る限り、提案手法 TACCA は、少数のチャネルを使用して衝突のない送信を実現する、初めての経路制御機能を含んだチャネル割当手法である。CSMA に対応した干渉モデルと共有リンク容量モデルが導入されたことで、与えられた通信要求の下で MCMR WMN を最適化する、フレーム衝突のないチャネル割り当てが実現できた。通信需要を考慮しない CASCA とは異なり、TACCA は、リンク容量の制約を満たす経路制御と、チャネル割り当てによって衝突を常に回避することの両方を実現できる。

2 提案手法2.1 ネットワークモデル
有向ネットワーク G =（V、E）が与えられる。ここで、V はノード集合であり、E は有向リンク集合である。
ネットワークは、IEEE802.11 に基づいたの WMN であり、各ノードに複数の NIC を装備することにより、複数の周波数チャネルを用いて通信することができる。各 NIC は、IEEE802.11 の通信帯域内の直交周波数チャネルで動作する。各リンク l∈E には容量 C があり、容量 C はそれがリンク l が許容できる通信量を表す。チャネル q∈Q を使用して、ノード u からノード v に向かうリンク l∈E は、l =（u、v、q）と表記される。ここで、Q は直交チャネル集合であり、そのチャネル数は|Q|で表される。図 1（a）は、|Q|=3 の場合のネットワーク G を示す。ここで 3|Q|リンクは全ての隣接ノード間に定義される。この場合、全ノードに 3 つの NIC が装備されており、それぞれに異なる 3 つのチャネルが割り当てられていると想定することになる。図 1（a）に示すように、ここで q1、q2、および q3 は Q の 3 つの直交チャネルである。リンク l は、
（u、v、q）と表記することもできる。ここで、u および v はノードである。
任意のノードペア（s、d）∈V×V に対して、ノード s から d への通信要求の量を表す通信要求行列 D が与えられる。s から d への需要は D（s、d）と記述される。各ペア（s、d）と各リンク l で、（s、d）間のの通信フローがリンク l を通過するかどうかを示す変数 Pl（s、d）∈{0、1}を定義する。つまり、Pl（s、d）=1 の場合、s から d への経路はリンク l を含む。それ以外の場合は、Pl（s、d）= 0 である。リンク l がある s から d への通信経路に含まれる場合、つまり、s と d の少なくとも 1 つのペアに対して Pl（s、d）= 1 の場合、リンク l はパケット送信に使用されるため、アクティブである。このために変数 Al∈{0、1}が定義され、Al = 1 はリン
ク l がアクティブであり、Al = 0 は非アクティブであることを示す。
各ノード v には Nv 個の NIC が装備されており、ノード上の各 NIC は Q に含まれる一つの周波数チャネルで動作する。したがって、リンク l =（u、v、q）がアクティブな場合、チャネル q を両端ノード u と v の NICに割り当てる必要がある。
ノード v に周波数チャネル q が割り当てられているかどうかを示す変数 Fvq∈{0,1}を定義する。つまり、ノード v に周波数チャネル q が割り当てられている NIC がある場合には Fvq=1、そうでなければ 0 である。本研究の問題定義では、D のすべてのゼロでない通信要求ノードペア（s、d）に対して、単一経路を割り当てる。全ての通信要求ノードペアに対して経路を割り当てた状態において、リンク容量制約と無衝突制約の両方が満たされ、各リンクの使用率を最小化する問題を定義する。リンク使用率とは、リンク容量 C に対するトラフィック量の比率であり、Σ(s,d)∈V×V,l∈ED（s、d）Pl（s、d）/ C で表すことができる。
我々の目的は、（s、d）∈V×V、l∈E に対して、ネットワーク内の全リンク l に対するリンク使用率の最大値を最小化することである。このために、全リンクに対するリンク利用率を表す変数 0≤Umax≤1 を定義する。図1（b）は、全ノードから他の全ノードへの通信フローを定義する通信要求行列 D に基づくチャンネル割当（スケジュール）である。このスケジュールでは、変数の値として、D（s、d）= 1 (Unit)とリンク容量 C = 60（Unit）をそれぞれ用いている。また、図中で各リンクに付与されている番号は、リンクを通過するトラフ
ィック負荷の量を示し、この図のチャンネル割当では Umax = 0.85 である。

2
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

図 1: (a)ネットワークモデルと(b)チャンネル割当の例

2.2 CSMA を考慮した干渉モデル
干渉は、WMN のパフォーマンス低下の主な原因である。衝突のない送信を実現するには、適用する干渉モデルを選択することが重要である。本研究では、CASCA [9]で導入された CSMA を考慮した干渉モデルを使用する。 CSMA 対応の干渉モデルは、通信範囲と干渉範囲の両方が R で示される Single Disk Model の上に構築される。つまり、二次元平面上のノードの位置から、ノード u と v の間の距離が R より小さく、u と v の両方に NIC がチャネル q で割り当てられている場合、リンク(u、v、q） ∈E が存在する。ご存知のように、CSMA は MAC（Media Access Control）プロトコルであり、各ノードは他のトラフィックがないことを確認してから、通信データを送信する。具体的には、CSMA では、ノードは送信を試みる前に、別のノードからのキャリア信号の存在を検出しようとする。キャリアが検出されると、ノードはその通信が終了するのを待ってから、自分の送信を開始する。CSMA を使用すると、複数のノードが衝突することなく、同じ通信媒体上で送受信できる。つまり、CSMA により、キャリア検知範囲内のリンク間の衝突が回避される。
我々は、２つの有向リンクが隠れ端末の関係にある場合にのみ、それらのリンクが干渉するものとする。l1=（u1、v1、q1）および l2 =（u2、v2、q2）を E に含まれる 2 つのリンクのペアとする。このとき、リンクl1 でフレームが送信されたとき、次の条件が満たされた場合、隠れ端末問題により l2 の通信が妨害される（つまり、l2 上で送信された通信フレームが衝突により到達できない）。
ケース 1：2 つのデータフレームの衝突（1）q1 = q2、（2）（u1、u2、q1）∈E ではない、（3）（u1、v2、q1）∈E.
ケース 2：データと Ack フレームの衝突（1）q1 = q2、（2）（u1、v2、q1）∈E ではない、（3）（v1、v2、q1）∈E.
ケース 1 は、l1 でのデータフレームの送信が l2 でのデータフレームの送信を妨害する場合を示している。
図 2（a）に示すように、ノード v2 はノード u1 と u2 の両方の送信範囲内にある。一方で、ノード u1 と u2は、互い伝送範囲外にあり、これらは相互に検知できない隠れ端末ノードである。したがって、ノード u1と u2 が同じチャネルを同時に使用して、それぞれが通信フレームをノード v1 と v2 に配信すると、ノードv2 は、衝突のため送信ノード u2 からのパケットを正常に受信できない。なお、ノード v1 と v2 は同じノードである場合がある。このようなリンク l1 と l2 のペアを干渉リンクペアと呼ぶ。たとえば、図 1（a）では、リンク（a、b、q1）と（c、b、q1）、およびリンク（a、b、q1）と（c、f、q1）はそれぞれ干渉リンクペアである。

3
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

図２：２タイプの干渉リンクペア

図３：リンク間の通信容量の共有

図 2（b）は、l1 での Ack フレームの送信が l2 でのデータフレームの送信に干渉するケース 2 を示している。よく知られているように、CSMA は明示的なパケット確認（ACK）を使用して衝突を回避しようとする。
これは、データパケットが無事に到着したことを確認するために受信ノードから ACK パケットが送信されることを意味する。パケットがそのまま受信された場合、受信ノードは ACK フレームを発行し、これを送信者が正常に受信すると、フレーム転送処理を完了する。データフレームが完全に受信されなかったか、ACK が受信されなかったために、送信ノードによって ACK フレームが検出されない場合には、送信ノードはフレームが損失したと見做し、再度ランダムバックオフを待ってからフレームが再送される。図 2（b）のノード u1と u2 は、同時に同じチャネルを使用して通信フレームをノード v1 と v2 にそれぞれ送信するときには、お互いの通信を検知できない。このとき、ノード v1 から送信される ACK フレームと、ノード u2 から送信されるデータフレームがノード v2 で衝突する可能性があり、このとき v2 がデータフレームを正常に受信できない。
この時にも、リンク l1 と l2 を干渉リンクペアと呼ぶ。図 1（a）の例では、リンク（a、b、q1）と（f、c、q1）のペアは、ケース 2 による干渉リンクペアである。
本研究では上記の CSMA を考慮した干渉モデルの下で、衝突のない経路制御機能を含んだチャネル割り当てを計算する。CSMA 対応の干渉モデルでは、バックオフ時間が同じである場合や、2 つの Ack フレームの同時送信による衝突は、発生確率が低いため無視される。この干渉モデルの下で衝突のないチャネル割り当てを計算できた場合には、実際の WMN における衝突確率は十分に低い水準であると考えられる。
2.2 CSMA を考慮した通信帯域共有モデル
無線ネットワークでは、通信媒体である周波数チャネルはキャリアセンス範囲内のノードによって共有されるため、近隣リンクが通信容量を共有する。再び図 1（b）を参照すると、リンク（e、b、q2）、（e、d、q2）、（e、f、q2）、（f、e、q2）、および（f、i、q2）は、いずれもキャリアセンスの範囲内に存在するノード eおよび f から送信するため、通信容量を共有する。したがって、MCMR WMNs の無線リンクは互いの同じ帯域幅を共有して使用するため、リンク毎に割り当てられる帯域幅は存在しない。通信要求に対して帯域を保証するためには、これら帯域を共有する全リンクの通信量が容量 C を超えないようにする必要がある。前述のように、図 1（b）のリンク（e、b、q2）、（e、d、q2）、（e、f、q2）、（f、e、q2）、および（f、i、q2）は通信容量を共有するリンクであり、共有容量制約（2 + 9 + 5 + 16 + 15）≤C を満たす必要がある。ここで、左辺の各値は、このスケジュールにおける各リンクの通信量である。
提案する通信帯域共有モデルを定義する。次のように、ノード a と周波数チャネル q に関して通信容量共有リンク集合を定義する。ノード a とチャネル q に対して、通信容量共有リンク集合 Saq は以下のように定義される。
Saq = {（a、u、q）|（a、u、q）∈E}∪{（u、a、q）|（u、a、q）∈E}∪{（u、v、q）|（a、u、q）∈E、（u、v、q）∈E、a!=v }図 3 を用いて説明する。u∈V はノード a∈V のキャリアセンス範囲内に含まれるが、v∈V は含まれず、vは u のキャリアセンス範囲には含まれる。このとき、リンク（a、u、q）、（u、a、q）、（u、v、q）に同じチャネル q が割り当てられている場合、a と隣接するノードを始点とするこれらのリンクは CSMA の下で通信容量C を共有する。

4
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

4. 定式化
前述のような CSMA を考慮した干渉モデル、及び通信容量共有モデルを用いて、与えられる通信要求に対して最適なチャネル割当と通信経路を計算する問題を混合整数線形計画問題（Mixed Integer and LinearProgramming: MILP）として定式化する。ここでは、定式化の解説は既発表論文に譲り、最終的な定式化結果のみを示す。ネットワークトポロジーG、通信要求行列 D、直交チャネル集合 Q、各 v∈V の NIC の数 Nv、提案干渉モデルの下での干渉ペア集合 IG のセット、リンク容量 C、制御係数 k が与えられるとき、提案する最適化問題は次のように表される。

5
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

5. 評価本研究の提案手法 TACCA の性能評価を行う。ネットワークシミュレータ Scenargie version 2.1 を用いてシミュレーション評価を行なった。6Mbps のリンク速度の IEEE802.11g を使用した。各ノードには 2 つの NICが装備されており、各 NIC は 3 つの直交チャネルの 1 つが割り当てられる。TACCA のパフォーマンスを測定するために、3 つの評価基準を選択した。 1 つ目は、通信スループットであり、単位時間あたりにネットワーク内のすべての宛先ノードに配信されたデータパケットの総量を表す。2 番目はパケット配信率であり、送信されたパケットに対する宛先に届けられたパケットの割合である。3 番目は、パケットの送達遅延であり、パケットが宛先に到達するのにかかる平均時間である。これらのパラメーターはすべて、60 秒の起動期間の後に、5 回の実行の平均として測定される。比較手法としては、CASCA だけでなく、TiMesh を用いた。
TiMesh は提案手法と同様に通信要求に対してチャネル割当と経路制御を同時に行う MILP に基づいた最適化手法であるが、フレーム間の衝突を RTS/CTS のみに基づいて解決しようとする点で TACCA と異なる。
つまり、TiMesh との比較を行うことで、適用する干渉モデルと通信容量共有モデルによる効果を測ることができる。
5.1 格子トポロジ
複数のネットワークトポロジを用いてシミュレーション評価を実施した。まず、無線メッシュ網の典型的トポロジである正方形格子トポロジを用いた。5×5 格子トポロジを用意し、水平および垂直に 12 本の CBR(Constant Bit Rate)フローを発生させた。各トラフィックフローの伝送レートは全て同じとし、この統一伝送レートを変動させて通信性能を測定した。経路延伸係数 k の値は 10 に設定された。これは、CASCA が衝突のないスケジュールを生成できる最小値である。
図 4（a）は、格子トポロジにおけるスループットのシミュレーション結果である。横軸は全フローの送信レート総計を、縦軸はスループット総計をそれぞれ示す。図 4（a）では、一定の送信レート以内（6000 Kbps）
であれば TACCA のスループットが 100％を維持できることがわかる。この状態は、送信レートが 7000 Kbpsに達するまで続く。つまり、ネットワーク容量が通信要求の範囲内であれば、TACCA は柔軟な経路制御により通信要求を満たせる能力を持つことがわかる。また、この通信負荷分散能力は既存手法である CASCA よりも優れており、TACCS はリンク利用率の最大値を最小化することにより、将来の通信変動のための余裕を持たせることができることも示している。送信レートがネットワーク容量を超えると、各ノードにおいて送信キューが溢れることにより、スループットが低下し始める。比較すると、CASCA と Timesh においては、ほぼ100%のスループットを維持できるのは、送信レートがそれぞれ 3700 Kbps と 840 Kbps 以内であり、TACCA を大幅に下回ることがわかる。CASCA では、負荷分散性能が低いために、一部のリンクが過負荷になり、パケットがドロップされることが原因で、このような結果となっている。TiMesh では、RTS/CTS により晒し端末問題が発生しているだけでなく、RTS/CTS の利用により適切な割合でノードがリンクを利用できないことや、RTS/CTS 自体の衝突によってパケット損失が発生していることが性能を押し下げる要因として挙げられる。
図 4（b）は、配送成功率のシミュレーション結果である。スループットと同じように、TACCA は一定の送信レートまでは 100％の配信率を維持できる。
図 4（c）は配信遅延のシミュレーション結果であり、TACCA は伝送速度（6000Kbps）以内では低い配信遅延を維持できることがわかる。ただし、送信レートがリンク容量を超えると、配信遅延が大幅に増加する。
この原因は 2 つ挙げられる。まず、ネットワーク内に滞留するパケットが増大するため、送信キューの中で待機する時間が増加することである。次に、キュー溢れのために損失した通信フレームは再送されるので、このための待機時間が長くなることである。一方で、TiMesh の配信遅延は、特にトラフィックの負荷が大きく過負荷である場合に、TACCA よりも低くなっている。これは、TiMesh が送信キューの長さを増大させないことに起因する。TiMesh は、RTS/CTS を発行しない CSMA と同様に、一定の確率で途中のノードでパケットを損失させるため、ネットワーク内にパケットが滞留しにくい性質がある。このため、図 4(b)に見られるように低い送信レートでも配送率が低下するが、これは逆にネットワーク内に滞留するパケット数を減少させることになるので、配送遅延はさほど増大することなく、比較的低い値を維持できる。ここで、TiMesh に見られる傾向は従来から無線メッシュ網に見られる傾向であるのに対して、CASCA や TACCA はどちらかと言えば有線ネットワークに見られる傾向である。つまり、衝突の少ないチャンネル割当によって、無線通信特有の電波干渉による影響がなくなり、有線ネットワークに近く性質的な変革が起こっていると考えられる。

6
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

図 4: 格子トポロジのシミュレーション結果
5.2 ランダムトポロジ
格子トポロジと同じように、ランダムトポロジを構築して性能評価を行なった。ここでは、1500×1500 [m]の正方形のフィールドに 30 ノードをランダム配置したランダムトポロジーを生成し、これを評価に用いた。
ネットワーク内では、10 本のランダムフローを生成する。つまり、送信元と宛先をランダム選択した通信フローを 10 本生成する。このために、各通信フローの伝送速度を一定に設定した 4 組のランダムな通信要求行列を生成する。経路延伸係数 k は 7 に設定した（これは、CASCA が衝突のないスケジュールを生成する最小値である）。シミュレーションでは、スループット、配信率、配信遅延は 60 秒の起動期間後に測定される。
最後に、4 つの通信要求行列の結果を平均し、これを比較する。
評価結果を図 5（d）、（e）、（f）に示す。この結果から、通信性能の傾向は格子トポロジーと似ていることがわかるが、性能差は格子トポロジーの場合と比較して開いており、TACCA がより優れた性能を示すことがわかる。これは、ランダムトポロジにおいては格子よりもボトルネック箇所が発生しやすく、CASCA と TiMeshはボトルネック箇所における性能低下が大きいのに対して、TACCA は負荷分散性能を発揮することでボトルネック箇所をうまく避けた経路制御ができていることがわかる。
図 4 と 5 から、格子トポロジとランダムトポロジの両方において、TACCA は従来手法よりも優れた性能を発揮できることが明らかとなった。また、TACCA と CASCA はネットワークシミュレーションでもフレーム衝突をほとんど起こしておらず、この点で本分野の既存手法を大きく凌駕することが明らかになった。

図 5: ランダムトポロジのシミュレーション結果

6. おわりにMCMR WMN では、チャネル割り当ては、ネットワーク上のトラフィック分布を決定する重要な最適化課題である。本研究では、与えられた通信要求行列に対して、効率的な通信経路を決定することを含めたチャネル割当手法に取り組み、このような問題を MILP 最適化問題として定式化した。TACCA は MATLAB や CPLEX 等の混合整数線形計画法ソルバを用いて解くことができ、最適な経路制御とチャネル割当を同時に実現すること

7
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

ができる。提案手法 TACCA では、IEEE802.11 を用いた無線メッシュ網を想定し、CSMA の動作を考慮した独自の干渉モデルと通信容量共有モデルを提案した。
また、これらのモデルに基づいて MILP 最適化問題を設計し、これを解くことで、従来では実現できなかった 3-5 チャネル程度での衝突のないチャネル割当を実現した。
また、チャネル割当に通信要求行列から計算される負荷分散機能を導入し、現実的なネットワーク上でも適切に負荷分散を行える機能を実現した。
シミュレーション評価の結果、提案手法 TACCA は既存手法 CASCA および TiMesh に対して、大きな性能向上を実現できることを示した。シミュレーションにおいても通信フレーム同士の衝突はほぼ発生せず、最適化計算された通りに通信がなされた。また、通信要求から計算された負荷分散もよく機能し、通信量が増大してもほぼ 100%のパケット到達率を実現できる送信レートが大幅に改善された。

【参考文献】[1] Akyildiz, Ian F., and Xudong Wang. Wireless mesh networks. Vol. 3. John Wiley & Sons, 2009,
pp.1-13.
[2] Benyamina, Djohara, Abdelhakim Hafid, and Michel Gendreau. "Wireless mesh networksdesign — A survey." IEEE Communications surveys & tutorials 14, no. 2 (2011): 299-310.
[3] Deng, Xiaoheng, Jie Luo, Lifang He, Qiang Liu, Xu Li, and Lin Cai. "Cooperative channel
allocation and scheduling in multi-interface wireless mesh networks." Peer-to-Peer Networking
and Applications 12, no. 1 (2019): 1-12.
[4] Hoque, Mohammad A., and Xiaoyan Hong. "Channel assignment al- gorithms for MRMC
wireless mesh networks." International Journal of Wireless & Mobile Networks 3, no. 5 (2011):
75.
[5] Hong, Xiaoyan, Bo Gu, Mohammad Hoque, and Lei Tang. "Exploring multiple radios andmultiple channels in wireless mesh networks [accepted from open call]." IEEE WirelessCommunications 17, no. 3 (2010): 76-85.
[6] Ding, Yong, and Li Xiao. "Channel allocation in multi-channel wireless mesh networks."
Computer Communications 34, no. 7 (2011): 803-815.
[7] Ramamurthi, Vishwanath, Abu Sayeem Reaz, Dipak Ghosal, Sudhir Dixit, and Biswanath
Mukherjee. "Channel, capacity, and flow assignment in wireless mesh networks." Computer
Networks 55, no. 9 (2011): 2241-2258.
[8] Marina, Mahesh K., Samir R. Das, and Anand Prabhu Subramanian. "A topology control
approach for utilizing multiple channels in multi-radio wireless mesh networks." Computernetworks 54, no. 2 (2010): 241-256.
[9] Yoshihiro, Takuya, and Taiki Nishimae. "Practical fast scheduling and routing over slotted
CSMA for wireless mesh networks." In 2016 IEEE/ACM 24th International Symposium on
Quality of Service (IWQoS), pp. 1-10. IEEE, 2016.
[10] Mohsenian-Rad, A. Hamed, and Vincent WS Wong. "Joint logical topol- ogy design, interface
assignment, channel allocation, and routing for multi-channel wireless mesh networks." IEEE
Transactions on Wireless Communications 6, no. 12 (2007): 4432-4440.

8
公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度

〈発題名A Traffic-Demand-Aware Routing andScheduling for CSMA-based Wireless MeshNetworks
A Traffic-Demand-Aware Collision-free
Channel Allocation for Multi-channel
Wireless Mesh Networks
Traffic-Demand-Aware
Collision-free
Channel Assignment for Multi-channel
Multi-radio Wireless Mesh Networks

表資料〉

掲載誌・学会名等

発表年月

2019
IEEEInternational
Conferenceon
Pervasive
Computing and Communications
Workshops (PerCom Workshops)
The12thInternational
Conference on Mobile ComputingandUbiquitousNetworking(ICMU2019)
IEEE Access2019 年 3 月

2019 年 10 月

2020 年 6 月9公益財団法人電気通信普及財団
研究調査助成報告書 第35号 2020年度