DEIM Forum 2014 C9-4

マルチホップマルチレートネットワークでの接続先選択ポリシーと接続元別重み付けスケジューリングにおける通信性能評価
藤井 聡佳†

村瀬勉††

小口 正人†† お茶の水女子大学 〒 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 ダイレクトを用いた仮想マルチホップ網の構成技術などにより，近接かつ多数のノードが連携するマルチホップネットワークの実現性が高まってきた．従来とは異なり，近接かつ多数のノードが連携するマルチホップネットワークでは，その QoS(例えばスループット) は，トラヒックリレー時の各ユーザの接続先選択方法に大きく依存する．例えば，1 端末でも遠方に低レートで接続してしまうと，マルチホップネットワーク全体が，Performance anomaly と呼ばれる通信品質劣化を起こしてしまう．しかし，近距離でマルチホップ通信時には，中継ノードは，それ自身が能動的な端末であるため，転送トラヒックだけでなく自身のトラヒックも送信する可能性が高いことも特徴として挙げられる．このような条件において，マルチホップ通信での転送トラヒックと自身のトラヒックの優先制御を行うスケジューリングや，マルチレート通信における特性を考慮した接続先選択制御に関する研究がそれぞれ行われてきたが，これらを同時に考慮した適切な接続先選択と，そのときのスループットとの関係はほとんど明らかになっていない．筆者らの研究において，すでに，マルチホップマルチレートネットワークにおいて，伝送レートと送信スケジューリング方法の組み合わせが全体スループットに与える影響について基本的なモデルで評価している．そこで本稿では，これを拡張して，異なる複数の経路から最大のスループットを得るために接続先選択を行った場合の，送信スケジューリング方法が全体スループットに与える影響について評価する．
キーワード

マルチホップネットワーク，無線 LAN，接続先選択，スループット

Performance evaluation with packet schedulingin multi-hop multi-rate network with weighted round robin schedulingand connecting node selection
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. は じ め には，QoS を考慮し，新たなノードが MANET に接続する場合に，ノードの QoS ポリシーに沿った接続を行い，中継各ノー

Wi-Fi での通信カバーエリア拡大のために，モバイルアド

ドは，経由トラヒックと自身のトラヒックとの優先制御を行う

ホックネットワーク (MANET) 技術を用いた中継通信方法が送信スケジューリング方法が全体のスループットに与える影響注目されている．経由ノードとして，スマートフォンなどのについて調査する．

Wi-Fi ユーザ端末を想定した場合，中継端末自身の経由メリッ送信目的ノードまでの接続経路が複数存在し，それぞれに伝トの考慮や自身のトラヒックの優先制御も必要である．本稿で送レートが異なる（マルチレート）ような MANET のスルー

プットは接続先選択に大きく依存する．この接続先選択においanomaly と呼ばれる状況が生じる [6]．本稿では，キャリアセンて，本稿で検討対象とするのは次の二つの特性である；一つは，ス範囲内にすべてのノードが含まれるような小規模な MANETノードからの距離が遠くなるにつれてマルチレート制御によっを対象としており，Performance anomaly はシステム全体に影て伝送レートが低下するため, スループットが低下してしまう響を及ぼす．

こと，もう一つは，ホップ数増加にともなって CSMA/CA のPerformance anomaly を考慮した，送信端末数 n 台，1 ホッ

送信機会の関係からスループットが大幅に低下してしまうこと

プの場合のマルチレートの端末 1 台あたりのスループットは，である．本稿では，さらに，中継ノードは転送トラヒックだけでなく自身のトラヒックも送信し，中継トラヒックと自身のトラヒックをノード自身が決めた配分で送信制御 (スケジューリング) する，という仮定をおく．このとき，このスケジューリ

1

各端末の伝送レート vi の調和平均

Pnによって，おおよ

1i=1vi
その値を求めることができる [5] とされているため，本稿でもングの内容はあらかじめ決められた後で広告され，他ノードは，この計算式でスループットを算出している．たとえば，802.11g

このスケジューリングと伝送レートとホップ数を考慮して，接において，54Mbps 送信端末が 1 台と 6Mbps 送信端末が 1 台

続先のノードを最適に選択するとする．
以下，2 章でマルチホップマルチレートネットワークに関する従来研究での制御について述べ，3 章ではマルチレート通信の特性とスケジューリングを考慮したモデルについて述べる．

4 章でこのモデルの評価について述べ，最後に，4 章でまとめとする．の無線 LAN では，それぞれのスループットは，前計算式より，5.4Mbps となり，システム容量の 20 ％程度のスループットしか得られないことを意味している．

3. 接続制御とスケジューリング制御
3. 1 システムモデル
本研究では，図 1 に示すような無線中継ノードと未接続ノー

2. 従 来 研 究

ドと無線基地局 (AP と表記) とからなる無線 LAN システムを

2. 1 関 連 研 究仮定する．AP と有線接続されている端末以外は，全てのノーマルチホップあるいはメッシュネットワークにおける AP 選

ドは，お互いに相手をキャリアセンスドメインに含み，全ての択方法は数多く検討されている [1] [2] [3]．さらに，マルチホッノードは同じチャネルを用いて通信を行う．未接続ノード (テプ無線ネットワークにおける制御として，中継ノードにおいてナントと呼ぶ) は，中継ノード (オーナーと呼ぶ) に接続し，有異なるフローのトラヒックに重みを付けて送出するスケジュー線端末と通信する．モデルにおいては，テナントとオーナーリング技術も既に知られている．[4] では，自身のアップリンクと AP は，非対称な位置関係にある．この位置関係がもたらすトラヒックのパケットを一つ送信するたびに転送アップリンク

ノード間距離と伝送レートの関係について説明する．全テナトラヒックのパケットを一つ転送することで，ホップ数の異なントは同じ位置にあり，それらとオーナー 1 は，比較的近いのるユーザ間のスループット差異を解消するスケジューリング方で，48Mbps の高伝送レートで接続できる．また，オーナー 2法を提案しているが，マルチレート通信における特性には言とは，少し離れているため，伝送レートは，24Mbps 程度にな及していない．さらに，接続トポロジの変化，すなわち，スケる．一方，オーナー 1 と AP 間は少し遠いので，48Mbps となジューリングの有利不利を考慮した下流ノードの接続方法につり，オーナー 2 と AP 間は，高速な 54Mbps で通信可能であいては，考慮されていない．一方，[5] では，無線メッシュ網にる．このとき，テナントは，高いスループットを得るためには，接続するユーザが目的のサーバに到達するまでの経路上のマル

次の 2 つの条件を満足する必要がある．

チレート通信性能を考慮することで，最大のスループットを得(1) システム全体のスループットを高めるように接続する．

られる AP 選択手法を提案しているが，スケジューリング方法

これは，システム全体のスループットの一部が端末のスルーには言及していない．しかしながら，これらスケジューリングプットになるからである．そのためには，Performance anomaly

方法と接続先選択制御を組み合わせた場合の通信特性は，よりを避けて，出来るだけ高い伝送レートで接続するべきである．

複雑なものとなる．なぜなら，下流ノードは，スケジューリン(2) 混雑を考慮して，接続する．

グ方法により異なる接続先を選択することで自身のポリシーに

これは，マルチホップの場合には，同じノードに接続してい従う，あるいは自身の効用を高くできる場合があり，そのようる n 台の端末トラヒックが，中継時には１つに集約されるため，な接続を行う振る舞いにともなってシステム全体のリンク容量になってしまうからである．
n
このためには，高伝送レートで接続できるオーナーばかりに集が変化するという依存関係が存在するからである．

2. 2 マルチレートと Performance anomaly
無線 LAN では，フレーム受信状況に応じて適切な伝送を行うため，各端末それぞれに適した伝送レートが用いられる．

CSMA/CA の送信機会均等性により既存の高伝送レート端末に対して低伝送レート端末が加わると，高伝送レート端末およびシステム合計スループットが著しく低下する Performance

端末あたりでは，送信レートの1中することを避けることも必要になる．
テナントとオーナーは，それぞれ，接続制御とスケジューリング制御をおこなう．それぞれについて次に説明する．

本稿では，基本的な特性をまず明らかにするため，全てのテナントは，同一の目的を持ち，またスケジューリングメカニズムは同一とする．ただし，スケジューリングメカニズムで用いるパラメータ，すなわち各オーナーにおけるキューのウエイト付けは各オーナーで目的に適した値を個別に設定するものとする．

図1

システムモデル3. 2 接 続 制 御テナントは，任意のオーナーに接続が可能であるとし，その接続先の選択を接続制御と呼ぶ．このテナントの接続方法について説明する．テナントは，それぞれ，何を目的として接続するオーナーを選択するかを決めているものとする．これをテナントのポリシーと呼ぶ．ここでは，テナントは，下記 5 種類の

図 2 スケジューリング方法

目的関数のうちいずれを最大化したいか (以下，接続ポリシー(i)〜(v) と呼ぶ) のいずれかを選択するものとする．
(i) システム全体スループット(ii) オーナー j(の自身のトラヒック分) のスループット(iii) オーナー 1〜m(の自身の総トラヒック分) の合計スループット

3. 4 接続制御とスケジューリング制御との関係
オーナーとテナントは，それぞれの制御方法を相手に公開するものとする．ただし，(1) テナントが先に接続ポリシーを決め, それを公開する (手順 1 とする)，(2) それに応じて，オーナーは，自己の目的を実現するようにスケジューリングを決め,(iv) テナント k のスループットそれを公開するものとする (手順 2 とする)．さらに，このス(v) テナント 1〜n の合計スループット

ケジューリングを考慮して，テナントは先に決めた自己のポリ

これらのポリシーを選択する理由として，次のような例が考シーに合致するようなオーナーに接続する．

えられる．

このスケジューリングおよび接続先を決定するとき，テナン(i) 無線リソースの有効利用

トもオーナーもシステムの他の全ての情報 (伝送レート，接続(ii)(iii) 中継というオーナーのボランティア行為に対する便宜状況) は，知ることが出来るとし，オーナーもテナントも，最(iv)(v) テナント自身の通信品質の向上

適値を計算できるものとする．これにより，オーナーは適切な

前記 5 種類のポリシーは，それぞれ独立の関係にある．あスケジューリングをとることで，テナントの接続を誘導でき，るポリシーに沿って接続したときに，それが，他のポリシーを所望の目的を達成することが可能になる．

とった場合の接続結果と同じになることもあり得る．本稿では，本稿では，オーナーのスケジューリング目的とテナントの接基本的な特性をまず明らかにするため，全てのテナントは，同続ポリシーは，短期的にはダイナミックに変動せず，固定であ一のポリシーであるとする．

るものとする．

3. 3 スケジューリング制御
オーナーのスケジューリングの目的について述べる．オー

4. スループット評価

ナーもテナントと同一の 5 種類の目的のうちいずれかを選択す

4. 1 評価モデルるものとする．この目的を達成するために，スケジューリングオーナーのスケジューリング内容と接続先選択との関係を調制御を行う．スケジューリング制御とは，データ送信の優先制査するために，図 1 に示すトポロジで，オーナー，テナント，御に相当する．具体的には，テナント毎に送信待ちバッファをシステム全体のそれぞれのスループットを評価した．n(>= 1)

持ち，さらにオーナーの送信待ちバッファを持ち，これらのバッ台のテナントはオーナー 1〜m，AP を経由し，AP と有線接ファからの送信量を変化させることで優先制御を行う．図 2 に続されている受信端末へ向けて片方向の飽和 UDP トラヒック

これを示す．ここでは，簡単のため，各バッファは Weightedを流す．各オーナーも同方向に自身の UDP トラヒックを流す．

Round Robin(WRR) キューで実現されるものとし，優先制御簡単化のため，m = 2(オーナーはオーナー 1 とオーナー 2 のは，このキューからの取り出しの重み (ウエイト) 付けで実現す2 ノードのみ) とし，テナント数を変化させて特性を評価する．

る．例えば，2 つのキューがあり，ウエイトが 1:2 の比でつけテナント s 台がオーナー 1 を経由，テナント t 台がオーナー 2られている場合，スループットも 1:2 となる．

を経由するとする．(n = s + t，s，t >= 0)
ここで，各テナントは密集している．マルチレート制御により，テナントからオーナー 1 までの距離は近いため高伝送レー

手順 1 において，テナントとしては，システム全体のスルートでの通信が可能であるが，オーナー 2 までの距離は遠いためプットをできるだけ大きくする必要がある．そのため，p の値低伝送レートでの通信となる．一方，AP からオーナー 2 までによらず，s = n，t = 0 が最適である．さらに，手順 2 においの距離はオーナー 1 までの距離よりも近く，ここでも伝送レーて，テナントが上記のように接続先を選択した場合，オーナートの差が生じる．Performance anomaly の発生するようなことしては，オーナー 1 のスループットをできるだけ大きくするの条件下で，オーナーのスケジューリング内容と接続先選択と必要があるため，p の値を最小にするのが最適である．実際に，の関係を調査する．

n = 3 のとき，手順 1 より，s = 3，t = 0 が最適となり (図 3)，

ここでは，スケジューリングのウエイトは，前述のように，各オーナーが個別に決定するのであるが，制御変数を少なくす

手順 2 より，この接続を行ったとき (図 4，黄色太線)，p = 0.05とするのが最適である．

るため，以下のように簡単化したモデルで評価を行う．
[オーナー 1 経由のテナントトラヒック合計スループット]=1: p[オーナー 2 自身のトラヒック分のスループット] :[オーナー 2 経由のテナントトラヒック合計スループット]५ঝ‫ش‬উॵॺ>0ESV@[オーナー 1 自身のトラヒック分のスループット] := 1 : (1-p)

これにより，パラメータ p の値を変化させることで，テナン

トにとって，オーナー 1 とオーナー 2 のどちらが，接続先として相対的に有利あるいは不利であるかを任意の割合で調整する

図3S



オーナー 2(の自身のトラヒック分) のスループットことができる．すなわち，この p の値を適値に設定することで，


手順 1 として，p の値に応じた最適な s，t の値は求まり，テナントはこれにしたがって接続する．これにより，p の値に応じた接続先は決定している．このため，オーナーは手順 2 として，この接続先と自身のスケジューリング目的を照らし合わせて最適な p の値を設定することとなる．手順 1,2 を目的関数の組み合わせすべてに対しておこなう．これにより，それぞれに५ঝ‫ش‬উॵॺ>0ESV@

各オーナーは目的に合致したスケジューリングを実現できる．







ついて最適な接続先選択とパラメータ設定を求める．表 1 のように，すべての組み合わせが考えられるが，本稿では，特に興S







図 4 オーナー 1〜2(の自身の総トラヒック分) の合計スループット

味深い特性が現れる例 1〜3 の 3 ケースについて，次章にて詳しく説明する．
【例 2】
表 1 調査するポリシー，目的の組み合わせパターン

・接続ポリシー...(ii) オーナー j(の自身のトラヒック分) のス५ॣ४গ‫ش‬জথॢ৯৓Lமਢএজ३‫ش‬

LLLLLLYYLLL

ここで，j = 1 とする．
୻୻LLL・スケジューリング目的...(v) テナント 1〜n の合計スループッ
ト (図 6)

LY
Y

ループット (図 5)

୻のとき

s = 0，t = n のとき，オーナー 1 のトラヒック分のスルー
4. 2 ポリシーとスループット

プットは p の値によらず一定である．一方，s >= 1 のとき，p前節の評価モデルにおいて，n = 3，0.05 <=p<= 0.95，m = 2の値が小さければ小さいほど，オーナー 1 のトラヒック分のスとし，台数比 s:t ごとの各スループットを図 3-6 に示す．
【例 1】
・接続ポリシー...(ii) オーナー j(の自身のトラヒック分) のス
ループット (図 3)
ここで，j = 2 とする．
・スケジューリング目的...(iii) オーナー 1〜m(の自身の総トラヒック分) の合計スループット (図 4)のときループットは大きくなる．したがって，手順 1 において，テナントとしては，p がより 0 に近い値のときは s = n，t = 0 が最適，p がより 1 に近い値のときは s = 0， t = n が最適である．この境界となる p の値を pa とする．また，手順 2 において，s = n，t = 0 のとき，テナントの合計スループットを最大化するためには，オーナー 1 のスループットをできるだけ大きくする必要があるため，p の値をできるだけ 1 に近づけるのが最適である．s = 0，t = n のときは，この逆である．したがって，p = pa が最適となる．実際に，n = 3 のとき，手順 1 より，となり (図 6)，手順 2 より，この接続を行ったとき (図 3，黄色p<= 0.6 のとき s = 3，t = 0 が最適，p >= 0.6 のとき s = 0，t = 3 が最適となり (図 5)，手順 2 より，この接続を行ったと太線)，p <= 0.9 とするのが最適である．

5. ま と め

き (図 6，黄色太線)，p = 0.6 とするのが最適である．

複数のモバイル端末やモバイルルータがマルチホップネット५ঝ‫ش‬উॵॺ>0ESV@

ワークを構成し，距離や伝送レートが異なる複数の経路が可能

であるネットワークにおいて，中継ノードが転送トラヒックお

よび自身の送信トラヒックに対して，あるスケジューリングを

設定することができる．ここで，各ノードはそれぞれが異なる

設定をおこなう．このとき，各目的関数に応じた最適な接続先

図5S

選択とスケジューリングパラメータ設定が求まることを示した．
文オーナー 1(の自身のトラヒック分) のスループット५ঝ‫ش‬উॵॺ>0ESV@


目的関数をもって接続先選択やスケジューリングパラメータの






S







図 6 テナント 1〜n の合計スループット【例 3】・接続ポリシー...(v) テナント 1〜n の合計スループット (図 6)・スケジューリング目的...(ii) オーナー j(の自身のトラヒック分) のスループット (図 3)
ここで，j = 2 とする．のとき
手順 1 において，スケジューリングにより，1 つのオーナーに接続するテナントのスループットは制限されているため，テナントの合計スループットを最大化するためには，s =| 0 かつt=| 0 にすべきである．また，このとき，システム全体のスループットをできるだけ大きくする必要があるため，s の値はできるだけ大きい値にすべきである．さらに p について，オーナー2 に接続することで Performance anomaly が発生し，システム全体のスループットが低下してしまうことも考慮する必要がある．したがって，p がより 0 に近い値の場合には，s = n + 1，t = 1 が最適であり，p がより 1 に近い値の場合には，s = n が最適である. この境界となる p の値を pb とする．また，手順 2において，オーナー 2 のスループットを最大化するためには，システム全体のスループットをできるだけ大きくする必要があ
るため，p の値によらず，s = n，t = 0 とするのがよく，このときのスループットは p によらず一定であるため，p >= pb が最適である．実際に，n = 3 のとき，手順 1 より，p <= 0.9 のとき s = 2，t = 1 が最適，p >= 0.9 のとき s = 3，t = 0 が最適

献[1] L. Luo, H. Liu, M. Wu, and D. Li, End-to-end performance aware association mechanism for wireless municipal
mesh networks, Computer Communications, Vol.31, No.8,
pp.1602-1614, 2008.
[2] H. Gong, K. Nahm, and J. Kim, Distributed fair accesspoint selection for multi-rate IEEE 802.11 WLANs, IEICE
TRANS. INF. ＆ SYST., Vol.E91-D, No.4, pp.1193-1196,
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, 2003.
[4] J. Jun, and M. L. Sichitiu, Fairness and QoS in Multihop Wireless Networks, IEEE VTC, Vol.5, pp.2936-2940,
Oct.2003.
[5] 三木冨美枝, 野林大起, 福田豊, 池永全志:無線メッシュ網における経路特性を考慮した AP 選択手法, 信学技報, IN2009-158,pp.85-90, 2010 年 3 月.
[6] 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.

，