マルチホップネットワークにおける経路選択の特性評価
藤井 聡佳

1

(指導教員：小口 正人)

はじめにスループットが向上する，スループット押し上げ効果と呼ばれる状況が生じる．

テザリングやモバイルルータなどの移動無線ノードの普及および Wi-Fi ダイレクトを用いた仮想マルチホップ網の構成技術などにより，移動メッシュネットワークの実現性が高まってきた．移動メッシュネット
ワークでは，ノード間でのパケットリレーにより，近隣の AP から所望の目的地に通信が可能であるが，その QoS（例えばスループット）は，AP 選択方法に大きく依存する．AP 選択を決める大きな要因は，無線LAN の特徴であるマルチレート通信と送信機会均等制御である．
本稿では，複数のモバイル端末やモバイルルータがマルチホップネットワークを構成し，目的のサーバに接続するために，伝送レートが異なり，なおかつ経由ノード段数も異なる複数の経路が可能であるネットワークを想定する．ネットワーク全体の合計スループットが最大になるような AP 選択方法を提案し，その性能評価を行う．

2

3.3 電波モデル[3] では，市街地カフェなどの公衆無線 LAN スポットでの実際のスループット計測結果が示されている．
理想的あるいは理論的な距離対スループット特性と比較して，距離によるスループット減少が著しく，比較的近距離でも低スループットとなっている．そこで本稿でも，1 ホップの距離は高伝送レート，2 ホップの距離は低伝送レートというモデルを採用する．

4

マルチホップマルチレートにおける AP選択方法と合計スループット

図 1 に示すようなマルチレートマルチホップ無線
LAN において，伝送レートの組み合わせとホップ数を変えて，合計スループットを評価した．主なシミュレー
ション諸元を表 1 に示す．伝送レートは IEEE 802.11g
無線 LAN を想定して，3.3 節で述べたように，端末から AP1 へ直接接続する場合 (1 ホップ) には低伝送レート 6Mbps，中継端末を利用する場合 (2 ホップ) には高伝送レート 54Mbps を設定した．

従来研究

メッシュあるいはマルチホップネットワークにおける AP 選択方法は数多く検討されており，またマルチレートでの AP 選択方法についても，多くの研究がある．本稿では，これらを同時に考慮するマルチホップマルチレートでの AP 選択方法を示す．[1] では，既存端末に加えて新規端末を収容するときの AP 選択方法を示しているが，本稿では，一般的に，端末数と AP選択結果が性能にどのような影響を与えるかを評価し，理想的な AP 選択方法を検討する．また従来の研究では，理想的あるいは理論的な伝搬モデルを用いたものが多いが，本稿では，現実に即したモデルを計測結果を基に利用している．

図 1: マルチレートマルチホップトポロジ
表 1: シミュレーション諸元

3

マルチホップとマルチレートの特性および電波モデル

3.1 マルチホップ
マルチホップ網では，リンク容量は，リレー時に送信および受信のために 2 度使用されることにより，中継ごとにスループットが低下する．例えば，エッジノードにおいては，端末数が n で，リレー先が一ヶ所のとき，uplink 方向のスループットは 1/n 程度になる．従って，端末数が多いほどマルチホップは不利になる．
3.2 マルチレート
フレーム受信状況に応じて適切な伝送を行うため，可変の伝送レートが用いられる．低伝送レートでは，フレーム送信に時間がかかる．一方，CSMA/CA では，送信機会はどの伝送レートに対しても均等である．そのため，既存高伝送レート端末に対して，低伝送レート端末が加わると，低伝送レート端末の送信終了を待つ時間が長くなり，高伝送レート端末および全体のスループットが著しく低下する，Performance anomalyと呼ばれる状況が生じる [2]．逆に，既存低伝送レート端末に対して，高伝送レート端末が加わると，全体のシミュレータ

QualNet 6.1

トラヒック特性

CBR

データサイズ

1500Bytes

送信間隔

1μs

物理層（無線）
伝送レート

IEEE 802.11g
無線: 6, 54Mbps
有線: 100Mbps

バッファサイズ

150packets

シミュレーション時間30s

まず，Performance anomaly を考慮した 1 ホップの場合のマルチレートの 1 端末当たりのスループットは，リレー回線での転送も含めて，各端末の伝送レート viの調和平均式 (T hru) で表すことができる [1]．この式
による送信端末台数 10 台までの合計スループットの推移を図 2 に示す．

1T hru = ∑n1i=1 vi

41

数から低伝送レートが有利であることが確認できた．
しかしながら，逆転後も差分はそれほど大きくないた
め，逆転前の性能を考慮して AP を割り当てることが重要だと思われる．また伝送レートの混在すなわち，1ホップと 2 ホップの経路の混在使用は不利であることも確認した．
従って，AP 選択方法としては，2 ホップ高伝送レートで接続しておくのが良く，接続台数が，ある程度多くなったときに，1 ホップ低伝送レートに AP を切り替えるといった選択が理想である．
図 2: マルチレート通信時の合計スループット理論値
次に，今回のモデルにおける合計スループットの近似式 (T hru(m)) を示す．2 ホップの場合には，最終的なスループットは，2 ホップ目だけで決まるため，1 ホップ目のスループットは計上しないとすると，次式のようになる．ここで，m = (6Mbps の台数)+min(1, (54Mbps の台数)) とし，min の値は，2 ホップ経由する端末が無いときは 0，1 つ以上ある時は，常に 1 として，リレー回線のスループットだけを乗算する．

m
T hru(m) = ∑n 1

図 4: マルチホップ通信時の合計スループット

i=1 vi

本近似式には，コリジョン及びバックオフの影響が含まれていないため，実際には，コリジョンの影響をより多く受ける 2 ホップのスループットは低くなる．
本近似式による送信端末台数 10 台までの合計スループットの推移を図 3 に示す．
本近似式から，n = 1 の時には，低伝送レート (1ホップ) よりも高伝送レート（2 ホップ）の場合の方が高スループットである．しかし，台数が増えると共に，大幅に減少する．一方，n 台すべてが低伝送レートの場合には，スループットはほとんど減少しないので，この両極端の場合のスループットは，台数が増えると (今回のパラメータ設定では，n = 10 において）逆転する．また，低伝送レートと高伝送レートを混在させるのは，得策ではない．

5

まとめと今後の課題

複数の端末に適切な AP 選択を行わせるために，Performance anomaly とマルチホップによるスループットの低下の影響を考慮しつつ，伝送レートとマルチホップ段数の組み合わせと合計スループットとの関係を調査した．低伝送レートで少ない段数 (シングルホップ)の経路と高伝送レートで多い段数の経路とが選択できるときに，複数の端末を最大スループットで収容するためには，全ての端末をどちらか一方の経路に振り分けるように AP を選択すべきであることを定量的に評価して確認した．
今後は，距離と伝送レートとの関係に基づいた伝送レート設定を行い，中継ノードの個数を増やすなど，より現実的なモデルについてシミュレーションを行う必要がある．

参考文献[1] 三木冨美枝, 野林大起, 福田豊, 池永全志:無線メッ
シュ網における経路特性を考慮した AP 選択手法,
信学技報, IN2009-158, pp.85-90, 2010 年 3 月.
[2] M. Heusse, F. Rousseau, G. Berger-Sabbatel andA. Duda, Performance anomaly of 802.11b,
Proc. of IEEE Inforcom 2003, vol.2, pp.836-843,Mar.2003.
図 3: 近似式における合計スループット[3] 金井謙治, 赤松祐莉, 甲藤二郎, 村瀬勉:無線 LANの実スループット特性に基づく寄り道経路探索の評価, 信学技報, NS2011-265, pp.487-492, 2012
年 3 月.

次に，シミュレーション結果を図 4 に示す．図 4 では，それぞれの n 値において，2 ホップ高伝送レートで通信する端末数と 1 ホップ低伝送レートで通信する端末数とをそれぞれ，0 ∼ n と n ∼0 に変えたときの合計スループットを各色で示している．得られた結果
は，近似式 (T hru(m)) と同じ特性であるが，逆転は，4 台の時に発生し，近似式の結果と比較して少ない台[4] 藤 井 聡 佳, 村 瀬 勉, 小 口 正 人:マ ル チ ホップ
ネット ワ ー ク に お け る 経 路 選 択 の 特 性 評 価(DEIM2013,2013 年 3 月発表予定)

42