DEIM Forum 2013 F1-5

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

村瀬勉††

小口 正人†† お茶の水女子大学 〒 112–8610 東京都文京区大塚 2–1–1†† NEC 〒 211–8666 神奈川県川崎市中原区下沼部 1753
E-mail: †satoka@ogl.is.ocha.ac.jp, ††t-murase@ap.jp.nec.com, †††oguchi@computer.org
あらまし近年，テザリングやモバイルルータなどの移動無線ノードの普及および Wi-Fi ダイレクトを用いた仮想マルチホップ網の構成技術などにより，メッシュあるいはマルチホップネットワークの実現性が高まってきた．移動
メッシュネットワークでは，ノード間でのパケットリレーにより，近隣のアクセスポイント（AP）から所望の目的地に通信が可能であるが，その QoS（例えばスループット）は，AP 選択方法に大きく依存する．AP 選択を決める大きな要因は，無線 LAN の特徴であるマルチレート通信と送信機会均等制御であり，マルチホップネットワークでの AP選択方法やマルチレートでの AP 選択方法については，それぞれ多くの研究がある．そこで本稿ではこれらを同時に考慮し，複数のモバイル端末やモバイルルータがマルチホップネットワークを構成し，目的のサーバに接続するために，伝送レートが異なり，なおかつ経由ノード段数も異なる複数の経路が可能であるネットワークを想定する．そのような環境において，ネットワーク全体の合計スループットが最大になる AP 選択方法を提案し，その性能評価を行う．その結果，全ての端末をどちらか一方の経路に振り分けるように AP を選択すべきであることを明らかにした．
キーワード

マルチホップネットワーク，無線 LAN，経路選択，モバイルルータ，スループット

Performance Evaluation of a route selection for Multi-hop Network
Satoka FUJII† , Tutomu MURASE†† , and Masato OGUCHI†† Ochanomizu University Otsuka 2–1–1,Bunkyo-Ku, Tokyo 112–8610 Japan†† NEC Corporation
1753 Shimonumabe, Nakahara-ku, Kawasaki, Kanagawa, 211–8666, Japan
E-mail: †satoka@ogl.is.ocha.ac.jp, ††t-murase@ap.jp.nec.com, †††oguchi@computer.org

1. は じ め に
テザリングやモバイルルータなどの移動無線ノードの普及および Wi-Fi ダイレクトを用いた仮想マルチホップ網の構成技術などにより，移動メッシュネットワークの実現性が高まってきた．移動メッシュネットワークでは，ノード間でのパケットリ
レーにより，近隣のアクセスポイント（AP）から所望の目的地

AP 選択方法を提案し，その性能評価を行う．
以下，2 章で従来研究での AP 選択方法について述べ，3 章
ではマルチホップとマルチレートの特性および電波モデルについて説明する．4 章でシングルレートでの通信性能評価実験について述べた後，5 章でマルチホップマルチレートネットワー
クにおける経路選択の評価実験について述べる．最後に，6 章でまとめを述べる．に通信が可能であるが，その QoS（例えばスループット）は，AP 選択方法に大きく依存する．AP 選択を決める大きな要因は，無線 LAN の特徴であるマルチレート通信と送信機会均等制御である．

2. 従 来 研 究
メッシュあるいはマルチホップネットワークにおける AP 選

本稿では，複数のモバイル端末やモバイルルータがマルチ択方法は数多く検討されている [1] [2] [3]．一般的に，端末は AP

ホップネットワークを構成し，目的のサーバに接続するために，から定期的に送信されるビーコンの RSSI に基づいて AP 選択

伝送レートが異なり，なおかつ経由ノード段数も異なる複数のを行うが，この方法では，端末とそれが接続する AP とのリン経路が可能であるネットワークを想定する．そのような環境ク品質のみ考慮しており，AP からゲートウェイまでの間に発において，ネットワーク全体の合計スループットが最大になる生し得るボトルネックについては考慮できていない．そこで [1]では，これを考慮することで，エンドツーエンドの性能を向上できることを示している．またマルチレートでの AP 選択方法についても，多くの研究がある．新規端末の伝送レートを考慮した AP 選択として，[4] では，端末が満足できる最低限度のスループットと，移動可能距離を考慮することによってシステム内のスループットを最大化する手法について述べている．本稿
では，これらを同時に考慮するマルチホップマルチレートでのAP 選択方法を示す．[5] では，既存端末に加えて新規端末を収容するときの AP 選択方法を示しているが，本稿では，一般的に，端末数と AP 選択結果が性能にどのような影響を与えるか

図 1 公衆無線 LAN スポットでのスループット計測結果を評価し，理想的な AP 選択方法を検討する．また従来の研究では，理想的あるいは理論的な伝搬モデルを用いたものが多い
が，本稿では，現実に即したモデルを計測結果 [6] をもとに利用している．

3. マルチホップとマルチレートの特性および電波モデル
3. 1 マルチホップ
マルチホップ網では，リンク容量は，リレー時に送信および受信のために 2 度使用されることにより，スループットが低下する．例えば，エッジノードにおいては，端末数 n が増加
し，リレー先が 1 カ所のとき，uplink 方向のスループットは

図 2 本稿で採用した電波モデル

O(1/n) で減少することが示されている [7]．従って，端末数が多いほどマルチホップは不利になる．

3. 2 マルチレート
フレーム受信状況に応じて適切な伝送を行うため，可変の伝送レートが用いられる．低伝送レートでは，フレーム送信に時間がかかる．一方，CSMA/CA では，送信機会はどの伝送レートに対しても均等である．そのため，既存高伝送レート端末に対して，低伝送レート端末が加わると，低伝送レート端末の送信終了を待つ時間が長くなり，高伝送レート端末および全体のスループットが著しく低下する Performance anomaly と呼ばれる状況が生じる [8]．逆に，既存低伝送レート端末に対して，高伝送レート端末が加わると，全体のスループットが向上するスループット押し上げ効果と呼ばれる状況が生じる．

4. シングルレートにおける端末数と合計スループット
複数 n 台の無線送信端末 (TE) から AP を経由し 1 台の有線受信端末へ向けて飽和状態となるように UDP の片方向フローを同時に流したときの，送信端末増加にともなう合計スループットの変化をシミュレーションで測定した．トポロジを図 3に示す．図の点線部は無線 LAN 接続，実線部は有線接続を指す．AP と受信端末間は，ボトルネックにならない十分な帯域があると想定して有線としているが，無線でも同じ結果が得られる．主なシミュレーション諸元は表 1 の通りである．マルチレートの実験との比較のため，伝送レートを固定したシングルレートで測定を行った．全てのノード (端末と AP) は，お互いに相手をキャリアセンスドメインに含むものとした．

3. 3 電波モデル

結果を図 5 に示す．送信端末が増えると，同一チャネルを共[6] では，市街地カフェなどの公衆無線 LAN スポットでの実有する他端末との同時送信の可能性が高まり，コリジョンの発際のスループット計測結果が示されている．理想的あるいは理生率が高くなる．これがスループット低下の要因となるため，論的な距離対スループット特性と比較して，図 1 に示すように，送信端末台数の増加にともない合計スループットも減少する．

距離によるスループット減少が著しく，比較的近距離でも低ス

ただし，送信端末が 1 台の結果と 2 台の結果を比較すると，伝ループットとなっている．そこで本稿でも，2 ホップで通信す送レートが 36Mbps より高い場合には 2 台において 1 台よりる際の 1 ホップ分の距離は高伝送レート，2 ホップ分の距離をもスループットが高くなる．これは，CSMA/CA によって，送1 ホップで通信する際は低伝送レートというモデルを採用する

信端末が 1 台であっても，データ送信時にバックオフ時間待機(図 2)．

しなければならず，この余分な待ち時間がスループット低下要因になっており，送信端末が 2 台になるとこの問題が緩和され，スループットが向上するからである．低伝送レートでは，コリジョンによるスループット低下の影響をより強く受けるために，結果的にスループットは向上しない．

表 1 シミュレーション諸元

ン諸元は前章の実験と同様であるが，伝送レートとしては，3.3シミュレータ

QualNet 6.1

節で述べたように，端末から AP1 へ直接接続する場合 (1 ホットラヒック特性CBRプ) には低伝送レート 6Mbps，中継端末を利用する場合 (2 ホッ

データサイズ1500Bytes

送信間隔1μs

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

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

バッファサイズ150packets

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

1
T hru = Pn

i=1 vi

図 3 多数台通信時のトポロジ

図 6 マルチレート通信時の合計スループット理論値

次に，今回のモデルにおける合計スループットの近似式(T hru(m)) を示す．2 ホップの場合には，最終的なスループットは，2 ホップ目だけで決まるため，1 ホップ目のスループットは計
図4

マルチホップ通信時のトポロジ上しないとすると，次式のようになる．ここで，m = (6Mbps の台数) + min(1, (54Mbps の台数)) とし，min の値は，2 ホップ経由する端末が無いときは 0，1 つ以上ある時は，常に 1 として，リレー回線のスループットだけを乗算する．

mT hru(m) = Pn

i=1 vi

本近似式には，コリジョン及びバックオフの影響が含まれていないため，実際には，コリジョンの影響をより多く受ける 2ホップのスループットは低くなる．本近似式による送信端末台数 10 台までの合計スループットの推移を図 7 に示す．図 7 では，それぞれの n 値において，2 ホップ高伝送レートで通信す
図 5 多数台通信時の合計スループットる端末数と 1 ホップ低伝送レートで通信する端末数とをそれぞれ，0 ∼ n と n ∼0 に変えたときの合計スループットを各色で5. マルチホップマルチレートにおける AP 選択
方法と合計スループット
前章のスループット測定の結果を受け，ある一つの端末を中継端末として加え，マルチレートマルチホップ無線 LAN において伝送レートの組み合わせとホップ数を変えて，合計スループットを評価した．トポロジを図 4 に示す．主なシミュレーショ示している．
本近似式から，n = 1 台の時には，低伝送レート (1 ホップ)よりも高伝送レート（2 ホップ）の場合の方が高スループットである．しかし，台数が増えると共に，大幅に減少する．一方，n 台すべてが低伝送レートの場合には，スループットはほとん
ど減少しないので，この両極端の場合のスループットは，台数スループットとの関係を調査した．低伝送レートで少ない段数(シングルホップ) の経路と高伝送レートで多い段数の経路とが選択できるときに，複数の端末を最大スループットで収容するためには，全ての端末をどちらか一方の経路に振り分けるように AP を選択すべきであることを定量的に評価して確認した．
今後は，距離と伝送レートとの関係に基づいた伝送レート設定を行い，中継ノードの個数を増やすなど，より複雑なトポロジをもったモデルについてシミュレーションを行う必要がある．
謝辞 本研究は一部，独立行政法人情報通信研究機構の委託
研究「新世代ネットワークを支えるネットワーク仮想化基盤技
図 7 近似式における合計スループット術の研究開発・課題ウ 新世代ネットワークアプリケーションの研究開発」によるものである．

が増えると（今回のパラメータ設定では，n = 10 において）逆転する．また，低伝送レートと高伝送レートを混在させるのは得策ではなく，どちらかのみの経路とした方が良い．

図8

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

次に，シミュレーション結果を図 8 に示す．図 8 では，それぞれの n 値において，2 ホップ高伝送レートで通信する端末数と 1 ホップ低伝送レートで通信する端末数とをそれぞれ，0 ∼n と n ∼0 に変えたときの合計スループットを各色で示している．得られた結果は，近似式 (T hru(m)) と同じ特性であるが，逆転は，4 台の時に発生し，少ない台数から低伝送レートが有利であることが確認できた．しかしながら，逆転後も差分はそれほど大きくないため，逆転前の性能を考慮して AP を割り当てることが重要だと思われる．また，伝送レートの混在すなわ
ち，1 ホップと 2 ホップの経路の混在使用は不利であることも確認した．
従って，AP 選択方法としては，2 ホップ高伝送レートで接続しておくのが良く，接続台数が，ある程度多くなったときに，1 ホップ低伝送レートに AP を切り替えるといった選択が理想である．

6. まとめと今後の課題
複数の端末に適切な AP 選択を行わせるために，Performanceanomaly とマルチホップによるスループットの低下の影響を考慮しつつ，伝送レートとマルチホップ段数の組み合わせと合計

文

献[1] L. Luo, H. Liu, M. Wu, D. Li, End-to-end performanceaware association mechanism for wireless municipal meshnetworks, Computer Communications, v.31 n.8, pp.16021614, May.2008.
[2] H. Gong, K. Nahm, J. Kim, Distributed fair access point
selection for multi-rate IEEE 802.11 WLANs, Proc. ofIEEE CCNC 2008, pp.528-532, Jan.2008.
[3] D. Couto, D. Aguayo, J. Bicket and R. Morris, A HighThroughput Path Metric for Multi-Hop Wireless Routing,Proc.ACM/IEEE MOBICOM’03, pp.14-19, Sep.2003[4] S. Miyata, T. Murase, K. Yamaoka, Characteristic analysis of an access-point selection for user throughput andsystem optimization based on user cooperative moving,IEEE CCNC2012, Jan.2012.
[5] 三木冨美枝, 野林大起, 福田豊, 池永全志:無線メッシュ網における経路特性を考慮した AP 選択手法, 信学技報, IN2009-158,pp.85-90, 2010 年 3 月.
[6] 金井謙治, 赤松祐莉, 甲藤二郎, 村瀬勉:無線 LAN の実スループット特性に基づく寄り道経路探索の評価, 信学技報, NS2011-265,pp.487-492, 2012 年 3 月.
[7] J.Jun and M.L.Sichitiu, The Nominal Capacity of Wireless
Mesh Networks, IEEE Wireless Communications, vol.10,no.5, pp.8-14, Oct.2003.
[8] M. Heusse, F. Rousseau, G. Berger-Sabbatel and A. Duda,
Performance anomaly of 802.11b, Proc. of IEEE Inforcom
2003, vol.2, pp.836-843, Mar.2003.