社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS
信学技報
TECHNICAL REPORT OF IEICE.
[ポスター展示] バックオフによる優先制御を考慮した隠れ端末存在環境に
おける IEEE802.11e 無線マルチホップネットワークスループット解析
下山田祐太†
眞田 耕輔†
関屋
大雄†
小室
信喜†
阪田 史郎†
† 千葉大学大学院融合科学研究科 〒 263-8522 千葉県千葉市稲毛区弥生町 1-33
E-mail: †{shimoyamada,k.sanada}@chiba-u.jp, ††{sekiya,kmr,sakata}@faculty.chiba-u.jp
あらまし 本稿では, バックオフによる優先制御を考慮し, 隠れ端末が存在する IEEE 802.11e 無線マルチホップネット
ワークのスループット解析を行う. 具体的には, 直線状片方向マルチホップネットワークについて検討し, 優先フロー,
非優先フローが混在するフローごとのスループットを解析的に導出する. IEEE 802.11e EDCA(Enhanced Disributed
Channel Access) では, アクセスカテゴリ (AC) が AC に応じた EDCA パラメータに従い自律的にアクセス競合をす
ることにより優先制御が可能である. 得られる解析表現は, 端末内の AC 間の CWmin , CWmax の違いが反映される.
シミュレーションと解析結果の比較により解析の妥当性を示す.
キーワード
IEEE 802.11e EDCA, 無線マルチホップネットワーク, スループット解析, 隠れ端末
Throughput Analysis for IEEE 802.11e Multi-hop Networks in The
Presence of Hidden Nodes Taking into Account Backoff-Based Priority
Differentiation
Yuta SHIMOYAMADA† , Kosuke SANADA† , Hiroo SEKIYA† , Nobuyoshi KOMURO† , and
Shiroo SAKATA†
† Graduate School of Advanced Integration Science, Chiba University
1-33, Yayoi-cho, Inage-ku, Chiba, 263-8522, Japan
E-mail: †{shimoyamada,k.sanada}@chiba-u.jp, ††{sekiya,kmr,sakata}@faculty.chiba-u.jp
Abstract This manuscript presents throughput analysis for IEEE 802.11e wireless multi-hop networks in the
presence of hidden nodes taking into account backoff-based priority differentiation. String network topology is
investigated and the end-to-end throughputs of high and low priority flows are obtained analytically. Priority
differentiations are realized by the EDCA (Enhanced Disributed Channel Access) parameters among access categories(ACs). The analytical results express the difference of CWmin and CWmax among ACs. The validities of
the analytical expressions are confirmed from the quantitative agreements between the analytical and simulation
results.
Key words IEEE 802.11e multi-hop networks, throughput analysis, hidden nodes.
1. は じ め に
ロトコルであるため, 無線マルチホップネットワークにそのまま
適用すると, 隠れ端末問題などによる衝突によりスループット
無線アドホックネットワークは中央制御局や既存のネットワー
や QoS(Quality of Service) に著しく影響を及ぼす. プロトコ
クインフラが不要であり, 柔軟かつ容易にネットワークを構築で
ルによる個々の端末における制御とマルチホップネットワーク
きる. 無線アドホックネットワークにおける MAC プロトコル
に内在する諸問題が影響しあい, ネットワークにどのような挙
として CSMA/CA(Carrier Sense Multiple Access/Collision
動が発生するかということを明らかにすることは, ネットワー
Avoidance) 方式を用いた IEEE 802.11 DCF(Distributed Co-
クの理解及びネットワークの設計においても重要である.
ordination Function) が検討されている. しかし, IEEE 802.11
無線マルチホップネットワークの解析としてこれまでに, IEEE
DCF は無線 LAN(Local Area Networks) を想定した MAC プ
802.11 DCF を用いた無線マルチホップネットワークの最大ス
—1—
ループット解析 [2]- [4], 非飽和状態及び飽和スループット解析 [5]
EDCA では, はじめに同端末内の AC 間で仮想的にアクセス
が行われている. しかし, これらの解析は IEEE 802.11 DCF
競合を行い送信権を得る. 端末内部において複数の AC が同時
に限定している.
にバックオフタイマー (BT) を 0 とする場合, 高優先の AC が
IEEE 802.11 DCF を基に拡張され QoS 保証を実現する MAC
送信権を得る. このとき, 送信権を得られなかった AC は, 仮想
プロトコルに IEEE 802.11e EDCA [1] がある. EDCA 端末は,
的に衝突と見なし, 再送処理を行う. この仮想的な衝突は内部衝
データの種類に応じて異なるバッファをもつ AC をもち, 各 AC
突と呼ばれる. その後, 送信権を得た AC は他の端末とチャネ
には異なる EDCA パラメータが割り当てられている. 各 AC
ルへのアクセス競合を行う. IEEE 802.11e EDCA の優先制御
はそのパラメータに応じて独立にバックオフ動作をすることに
について, 無線 LAN において多くの解析が行われている. まず
より, バックオフによる優先制御と IFS による優先制御が得ら
AC 間の CWmin , CWmax による優先制御を考慮した解析 [6],
れる. このバックオフによる優先制御は, AC 間の Contention
AIF S による優先制御を考慮した解析が確立された. そして,
Window(CW) の差により生じる. これらの優先制御を解析的
それらの解析技術を応用し, IEEE 802.11e EDCA の優先制御
に表現するため, 無線 LAN において, IEEE 802.11e EDCA の
を考慮した性能解析が行われている.
解析が行われている. 解析の流れとして, まずバックオフによ
る優先制御の解析 [6], IFS による優先制御の解析, それらの解
析技術を組み合わせた IEEE 802.11e EDCA の解析が行われ
ている.
2. 2 無線マルチホップネットワークにおけるスループット
解析
これまで無線マルチホップネットワークのスループット解析
については多くの研究が行われている. 初期段階は LAN を対
IEEE 802.11e EDCA 無線マルチホップネットワークの解
象としたものであったが, その解析技術が拡張され, また新たな
析では, すべての端末がキャリアセンス範囲内に存在すること
解析技術が提案されることにより、マルチホップネットワーク
を仮定したスループット解析 [8], RTS/CTS(Request To Send
における解析も徐々に充実したものになっている. 著者らが知
/Clear To Send) の衝突を考慮したスループット解析 [9] が行
る限り, 隠れ端末による衝突を考慮した無線マルチホップネット
われている. しかし隠れ端末によるデータフレームの衝突を考
ワークの最大スループット解析 [2] が最初である. [2] では, IEEE
慮した解析手法は確立されていない. IEEE 802.11e EDCA 無
802.11 DCF 無線マルチホップネットワークの端末ごとのエア
線マルチホップネットワークにおいても隠れ端末問題はネット
タイム, 衝突を解析的に表現し, フローの条件式で関連付けする
ワークに大きな影響を与えるため, その明確な解析的表現の確
ことにより最大スループットを導出している. その後, VoIP ア
立が必要である.
プリケーションの使用を想定した双方向フローに対する最大ス
本稿では, バックオフによる優先制御を考慮し, 隠れ端末が存
ループット解析 [4], Bianchi [7] らによるマルコフ遷移図を用い
在する IEEE 802.11e 無線マルチホップネットワークのスルー
た解析技術を組み合わせた解析 [5] が行われている. これらの
プット特性を解析的に得る. 本解析では, 直線状片方向トポロ
解析技術の提案により, 隠れ端末の衝突が生じる端末の状態を
ジーを検討し, 優先, 非優先フローが存在する場合について,
より詳細に表すことができ, 結果として非飽和, 飽和状態のネッ
ネットワークスループットを優先度ごとに導出することを目的
トワークの挙動を表すことができる.
とする. また, 本解析では CW の差別化の効果を表現する. 得
一方, IEEE 802.11e EDCA 無線マルチホップネットワークに
られた解析結果とシミュレーションの比較により解析の妥当性
関してのスループット解析も始められている [8]- [9]. しかし, [8]
を示す.
では EDCA に関するスループット解析はまだ初期段階といえ,
2. IEEE 802.11e EDCA とこれまでのスルー
プット解析の流れ
例えば簡単化のためにすべての端末が送信を互いにキャリアセ
ンスできると仮定しており, 隠れ端末が存在するネットワーク
トポロジーには対応していない. また, [9] では, RTS/CTS を用
2. 1 IEEE 802.11e EDCA とその解析 [1]
いて隠れ端末の衝突を回避した場合を想定し解析が行われてい
IEEE 802.11e EDCA は, IEEE 802.11 DCF を基本として,
るが, 隠れ端末によるフレームの衝突を考慮した解析は行われ
QoS を保証する MAC プロトコルである. EDCA では, 各端末
ていない. QoS 保証を実現する IEEE 802.11e EDCA を用い
はデータの種類に応じた 4 つの AC があり, それぞれの AC に
た無線マルチホップネットワークにおいて, 隠れ端末の衝突を
マッピングされる. 各 AC は, 優先度に応じた EDCA パラメー
解析的に表現することは, ネットワークを理解する上で有益で
タである CWmin , CWmax , AIFS によってバックオフ動作を
あり, 且つ MAC プロトコルの応用に期待ができる.
し, アクセス競合を行う.
CWmin , CWmax は, AC のバックオフタイマー (BT) 値を
決定するのに用いられる. これらの値が小さいほどチャネルア
クセスする頻度が高まるため, 優先度の差別化を図ることがで
3. バックオフによる優先制御を考慮した隠れ端
末が存在する IEEE 802.11e 無線マルチホッ
プネットワークの解析
きる. また, AIFS はビジー状態のチャネルがアイドル状態に変
本解析では, バックオフによる優先制御を考慮し, 隠れ端末が
化したときの待機時間を決定する. AIFS が小さい AC はチャ
存在する IEEE 802.11e 無線マルチホップネットワークの解析
ネルをビジーと検知した後, その他の AC よりも短い待機時間
を行う. 本解析では, 図 1 に示す IEEE 802.11e EDCA 端末に
で BT のカウントを開始できる.
よって構成されるホップ数が N の直線状片方向トポロジーを
—2—
Carrier Sensing Range of Node i
Carrier Sensing Range of Node i + 3
Transmission Range of Node i
Transmission Range of Node i+ 3
割合を端末 i の送信エアタイム xi と定義する. xi は xi,h を用
いて
xi = xi,1 + xi,2 (1 − τi,1 )
0
1 ・・・・ i-2
i-1
i
i+1
i+2
i+3
i+4
i+5 ・・・・ N-1
N
(2)
と表せる. ここで, τi,1 は, 端末 i の AC h の送信確率であり,
(1 − τi,1 ) は端末 i の AC 2 が内部衝突をする割合を表す.
xi,h を用いて, 端末 i の AC h のスループットは
図 1 解析, シミュレーションに用いるホップ数 N の直線状ネット
ワーク
Ei,h = xi,h × (1 − γi,h ) ×
P
T
(3)
と表せる. ここで, γi,h は端末 i の AC h の送信フレームが
想定する. 図 1 のネットワークでは, AC 1 と AC 2 のフローが
衝突する確率 (衝突率), P はデータペイロードサイズ, T は
存在する. そのうち, AC 1 が高優先のフローである. 解析は以
データフレーム送信によりチャネルが占有される時間であり，
下の仮定に従う.
T =tDAT A +tSIF S +tACK +tDIF S である. tDAT A はデータフ
1. 端末は 1 ホップ先の端末までデータフレームを送信可能
であり, 2 ホップ先までの端末の送信を検知することができる.
2. チャネルは理想状態であり, 送信の失敗はデータフレー
ムの衝突によってのみ生じる.
レーム送信時間, tSIF S は SIFS 時間, tACK は ACK フレーム
送信時間, tDIF S は, DIFS 時間である.
3. 2 キャリアセンスエアタイムとアイドルエアタイム
[0, T ime] のうち, 端末 i がキャリアセンスを行った時間の割
3. AC 1 と AC 2 のデータフレームサイズは等しい.
合であるキャリアセンスエアタイム yi とする. yi はキャリアセ
4. 端 末 0 に お い て 端 末 N を 宛 先 と し た デ ー タ フ レ ー
ンス範囲内にある端末の送信エアタイムの和からエアタイムが
ムを発生する. データフレームの発生は AC h の送信負荷
of f eredloadh に従う.
<i<
5. 中継端末 i (1 =
= N − 1) はその端末自身でのデータ
フレームの発生はなく, フレームを受信することによりバッファ
にデータフレームが発生する.
6. AC 1, 2 の送信バッファ長は有限で K 個である.
本稿では, AC h のバックオフステージ j の CW の値を
{
2j Wh,min
0<
=j<
= mh ,
(1)
Wh,j =
mh
2 Wh,min = Wh,max mh < j <
= Rh ,
と表す. ここで, Wh,min , Wh,max は AC h の最小, 最大の CW
W
であり, mh は mh = log 2 Wh,max , Rh は AC h の最大再送回
h,min
数である. また, 本解析ではバックオフによる優先制御に着目
するため, 各 AC の AIF S は DIF S と同じとする.
本解析では, [5] をもとに解析を行う. [5] では, まず端末の個
の動作を表すエアタイム, 送信確率, 衝突率を解析的に表現し,
得られたそれらをフローごとの条件式で関連付けすることによ
りそれぞれの値を導出し, 任意の負荷状態におけるスループッ
トを導出している. 本解析では, 端末内にある複数の AC を考
慮するため, まず端末の AC ごとのエアタイム, 送信確率, 衝突
率を表現する. 次に, AC 個々の表現から端末のエアタイム, 送
信確率, 衝突率を表現する. そして, フローの条件式で端末間の
関連付けを行い, フローごとのスループットを導出を行う.
3. 1 送信エアタイムとスループット
十分に長い時間 [0, T ime] のうち, 端末 i の AC h が送信を
行った割合を送信エアタイム xi,h と定義する. 送信エアタイム
は, 端末 i の AC h の送信成功及び送信失敗に費やした時間を
含む. 送信失敗とは, AC 1 の場合, 他の端末との送信フレーム
の衝突である. また, AC 2 の場合, それに加え同端末内の AC
1 との内部衝突に費やした時間を含む.
また, [0, T ime] において端末 i が実際に送信をした時間の
重複する部分を引くことで,
∑
yi =
xk − Φi − Θi
(4)
ν(i)∋k,k=i
|
と表される. ここで, ν(i) は端末 i のキャリアセンス範囲のノー
ドの集合, Φi は端末 i における隠れ端末衝突によるエアタイム
の重複, Θi は端末 i のキャリアセンスエアタイムのうち同時送
信による重複である. Φi は文献 [5] より,
0,
f or i=0, N −1,
x0 x3
,
f or i=1,
1 −x2
1−x
xi−2
xi+1
xi−1 xi+2
xi−2 xi+2
+
+
,
Φi =
1
−
x
−
x
1−x
−x
1−xi
i−1
i
i
i+1
f or 1<i<N −2,
xN −4 xN −1
,
f or i=N −2,
1−xN −3 −xN −2
(5)
である.
次に端末 i の同時送信によるエアタイムの重複 Θi を考慮す
る. 端末 i が端末 k と同時送信により重複したエアタイムは, 端
末 i が送信をしたとき, 端末 k と同時に送信する確率は τk なの
で, xi (1 − γiHID )τk と表せる. ここで, γiHID は端末 i の隠れ端
末のフレーム送信による衝突率である. また, 本解析の仮定に
おいて, 端末 i のキャリアセンス範囲内において同時に送信を
行う他の端末数は最大で 4 であるが, 3 ホップ以上先の端末が
同時に BT を 0 とした場合は隠れ端末の衝突にも含まれる. し
たがって, 隠れ端末の衝突となる同時送信の組み合わせを含め
ないとすると, 端末 i のキャリアセンス範囲内において同時送
信が生じるのは最大で 3 端末の場合である. このとき, Θi は,
Θi =
1
2
∑
(xk (1 − γkHID )
ν(i)∋k
−
∑
τl )
(ν(k)∩ν(i))∋l
j+2
j+2
i
∏
2 ∑ ∑
τl )
xk (1 − γkHID )
(
3 j=i−2
k=j
(6)
l=k,l=j
|
—3—
1 / Wh,0
1-γi, h
1
1
・・・
0, 1
0, 0
i, h
i, h
λ
0, Wh,0- 1
0
i, h
γi, h / Wh,1
・・・・
・・・
1
1-γi, h
Fh , 1
Fh, 0
i, h
i, h
・・・
Fh , δ
i, h
Fh+1, 0
1
i, h
Fh+1, 1
Fh , Wh,F -2
1
i, h
K
・・・ K-1
μ
μ
図 3 バッファの状態遷移図
Fh, Wh,F-1
i, h
γi, h / Wh,F+1
・・・
1-γi, h
・・・
1
λ
2
1
μ
・・・
1
λ
1
i, h
・・・・
・・・
・・・
Fh+1, δ
i, h
・・・
1
F+1,W
-2
h,F+1
h
1
i, h
である. また, σ はシステムスロットタイム, X(γi,h ) は 1 フ
F+1,W
-1
h
h,F+1
i, h
レームを送信しきるまでに BT をカウントする平均回数であり,
・・・
γi, h / Wh,L
1
1
1
Lh , 0
Lh, 1
i, h
i, h
1
・・・
Lh , δ
i, h
・・・
1
Lh,Wh,L-2
i, h
Lh,Wh,L-1
i, h
X(γi,h ) =
図 2 端末 i の AC h のアイドル時間における状態遷移図
(12)
と表される. ここで X(γi,h ) は, AC に応じて異なる CW を用
と表せる.
いているため異なり, 優先度による差別化を表現している.
[0, T ime] のうち, 端末 i が送信とキャリアセンスを行ってい
る時間を除いた時間をアイドル時間とし, [0, T ime] のうち, ア
イドル時間の割合を zi とする. zi は定義より,
zi = 1 − xi − yi .
端末 i の AC h は送信時間中はデータフレームを保持して
いる. 端末 i の AC h のキャリアセンス時間においてデータフ
レームを保持している時間の割合は qi,h と等しいと仮定する
(7)
と, ρi,h は,
ρi,h = xi,h + (1 − xi,h )min(qi,h , 1.0)
と表される.
3. 3 送 信 確 率
端末 i の AC h のバックオフカウントの動作をマルコフ連鎖
モデルで表す. 図 2 に飽和状態時の端末 i の AC h のバックオ
フ動作の状態遷移図を示す. この状態遷移図を文献 [5] に従い
解くことにより, 端末 i, AC h の送信確率は,
Rh
∑
τi,h = ρi,h
Rh
Wh,0 + Wh,1 γi,h · · · + Wh,Rh γi,h
2
∑
j=0
j
γi,h
である.
次に, 端末 i の AC h においてバッファ漏れする確率を導出
する. 図 3 はアイドル時間におけるバッファの遷移図を表す.
バッファ漏れが生じるのはバッファの状態が最大の K 個保持
しているときであり, K 個のフレームが存在する定常状態確率
を文献 [5] に従い求めると, バッファ漏れする確率は,
j
γi,h
j=0
Rh
(13)
(8)
Wh,j + 1
2
pbi,h =
K
qi,h
(1 − qi,h )
(14)
K+1
1 − qi,h
と表せる.
で与えられる. ここで, ρi,h は送信後にバッファに少なくとも
3. 5 衝 突 率
フレームをもつ確率である.
端末 i より端末 i の AC が送信をするとき, キャリアセンス
次に, 端末 i の送信確率を導出する. 端末 i は, AC 1, AC 2
範囲内の端末との同時送信によるフレーム衝突と隠れ端末の関
が少なくとも一方が BT を 0 としたとき, 送信を行う. したがっ
係にある端末とのフレーム衝突が生じうる. γiCON , γiHID をそ
て, 端末 i の送信確率は,
れぞれ端末 i の同時送信による衝突率, 隠れ端末の送信による
τi = 1 − (1 − τi,1 )(1 − τi,2 )
(9)
3. 4 フレーム保持確率とバッファ破棄確率
端末 i はフレームを受信することで, 送信フレームが発生す
る. そのため, 送信時間及びキャリアセンス時間において送信
フレームは発生せず, フレームの発生はアイドル時間において
のみ生じる. qi,h をアイドル時間において, 端末 i の AC h にフ
レームが存在する確率 (フレーム保持確率) とする. qi,h は,
λi,h Xi,h σ
λi,h
=
= zi
zi
Xi,h σ
(10)
と表せる. ここで λi は端末 i の単位時間におけるフレームの発
生頻度 (到着率) であり,
of f eredloadh ,
P
λi,h =
Ei−1,h
,
P
高優先である AC 1 と同時に BT を 0 としたとき, 内部衝突が
生じる. これを考慮すると, 端末 i の AC h の衝突率 γi,h は,
と表せる.
qi,h
衝突率とする. EDCA の動作において, AC 2 は同じ端末内の
f or i = 0,
f or i ∈ [1, N − 1].
(11)
γi,1 = γiCON + γiHID ,
γi,2 = 1 − (1 − τi,1 )(1 −
(15)
(γiCON
+
γiHID )).
(16)
と表される.
端末 i の同時送信による衝突は, 端末 i のキャリアセンス範
囲の端末が少なくとも１つ同時に送信をしたとき生じる. した
がって, γiCON は,
1 − (1 − τ1 )(1 − τ2 ), f or i=0,
1 − (1 − τ0 )(1 − τ2 )(1 − τ3 ), f or i=1,
1 − (1 − τ )(1 − τ )(1 − τ ),
i−1
i+1
i+2
γiCON =
(17)
f
or
1<i<N
− 2,
1 − (1 − τN −3 )(1 − τN −1 ), f or i=N − 2,
1 − (1 − τ
N −2 ), f or i=N − 1,
—4—
と表される.
表 1 シミュレーション諸元
Data frame
172 bytes
MAC header
28
bytes
PHY header
24
bytes
が送信中であるため, 端末 i による送信は端末 i+3 の送信を
ACK size
10
bytes
検知し端末 i+1 において衝突となる (Protocol Hidden Node
Data rate
18
Mbps
Collision). もう 1 つは, 端末 i が送信中に隠れ端末である端末
ACK bit rate
12
Mbps
隠れ端末の関係にある端末との衝突は 2 種類ある [2]. 1 つ
は, 端末 i が送信を開始したときに隠れ端末である端末 i+3
Transmission range
i+3 が送信を開始し, 端末 i+1 において生じるフレームの衝突
である (Physical Hidden Node Colllision).
axi+3
1 − xi+1 − xi+2
端 末 i の Physical Hidden Node Collision に よ る 衝 突 率
γiP HY は, 端末 i が送信中に端末 i+3 の AC の BT が 0 と
なる確率である. これは端末 i が送信を開始するとき, 端末 i+3
の AC h の BT が端末 i の送信フレームと衝突をしうる状態で
あり, 且つキャリアセンスを行わない確率と等しい. 端末 i の送
tDAT A
信フレームと衝突する状態とは, BT の値が δ=
以下の
σ
値である. これを AC 1, AC 2 についてそれぞれ考慮すること
により γiP HY は,
End-to-end Throughput per ACs
[Mbps]
と表せる. ここで, a = tDAT A /(tDIF S +tDAT A +tSIF S +tACK )
γiP HY = (qi+3,1 zi+3 Ωi+3,1 [1 − (xi+3,2 +yi+3 −xi+1 −xi+2 )]
/(1−xi+1 −xi+2 ) (19)
と表せる. ここで, Ωi+3,h は, 図 2 の状態遷移図において BT
の値が 1 から δ 以下の状態である定常状態確率の和であり,
Fh −1 Wh,j −1
∑
j=0
k=1
m
16
µsec
9
µsec
7
W1,min
7
W2,min
15
W1,max
15
W2,max
1023
∑
Rh
b(j, k)i+3 +
δ
∑
AC 1 for 4hop (Num)
AC 2 for 4hop (Num)
1.4
AC 1 for 4hop (Sim)
AC 2 for 4hop (Sim)
AC 1 for 6hop (Num)
AC 2 for 6hop (Num)
AC 1 for 6hop (Sim)
AC 2 for 6hop (Sim)
1.2
1
0.8
0.6
0.4
0.2
0
0
+ qi+3,2 zi+3 Ωi+3,2 [1−(xi+3,1 +yi+3 −xi+1 −xi+2 )])
∑
45
(18)
である.
Ωi+3,h =
m
Distance of each node
Rk (Retry limit)
送信中である確率である. γiP RO は, [2] より,
γiP RO =
115
σ (slot time)
は, 端末 i において送信を開始したときに端末 i+3 が
m
Carrier sensing range
SIFS time
端 末 i の Protocol Hidden Node Collision に よ る 衝 突 率
γiP RO
60
0.25
0.5
0.75
1
1.25
1.5
Offered load per ACs [Mbps]
図 4 4, 6 ホップネットワークにおける, 同じ送信負荷に対する AC 1,
2 のネットワークスループット
る. したがって, AC h のネットワークスループットは, EN −1,h
である.
b(j, k)i+3 (20)
j=Fh k=1
ホップ数 N の IEEE 802.11e EDCA 無線マルチホップネット
ワークにおいて式 (8), (15), (16), (21), (22) より, 6N 個の方程
δ+1
である. ここで, Fh = min{j|j >
} である.
=log2 W
式が得られる. 任意の送信負荷 Of f eredload1 , Of f eredload2
h,min
3. 6 フロー制限とネットワークスループット
を与えることにより, 6N 個の式を数値的に解くことができ, 未
個々の端末の AC を関連付ける. 図 1 のマルチホップネット
知数 xi,h , τi,h , γi,h を得ることができる. 本解析では, 数値計算
ワークにおいて, 端末 i の AC h のスループットは端末 i−1 の
AC h のスループットと等しい. しかし端末 i の AC h のスルー
にニュートン法を用いている.
4. 解析の評価
プットは, 端末 i の AC h におけるバッファ漏れ, 再送による破
本章では, シミュレーション結果と解析結果の比較を行い, 本
棄をされた分は除かれるため,
解析の妥当性を示す. シミュレーションには, ns-2 シミュレー
Ei,h = Ei−1,h (1 −
R +1
γi,hh )(1
−
pbi,h ),
f or 1 <
=i<
=N −1
(21)
タを用いた. 表 1 にシミュレーション諸元を示す. シミュレー
ションでは, 端末 0 において無作為に送信フレームが発生し, 中
継端末を経由し, 端末 N へ送られる.
を満たす. またフレームの発生を端末 0 の AC 1, 2 では,
x0,h (1 − γ0,h )
P
= Of f eredloadh (1 − pbi,h )
T
(22)
を満たす.
図 1 のトポロジーにおいて, AC h のネットワークスループッ
図 4 は, ホップ数 4, 6 における AC ごとの送信負荷に対する
AC 1, 2 のネットワークスループットである. 図 4 より, 解析結
果はシミュレーションと定量的に一致していることが確認でき
る. 図 4 において, AC 2 のネットワークスループットが最大と
なる送信負荷以下では, AC 1, 2 のフローともに, フロー上の端
トとは端末 N が単位時間中に受信した AC h のデータ量であ
—5—
末においてそれぞれ高い結果となる. 図 4 及び図 5, 6 より解析
0.9
AC 1 in Node 0 (Num)
AC 1 in Node 1 (Num)
AC 1 in Node 2 (Num)
AC 1 in Node 3 (Num)
0.8
Collision Probability of AC 1
0.7
結果はシミュレーション結果と定量的に一致していることから,
AC 1 in Node 0 (Sim)
AC 1 in Node 1 (Sim)
AC 1 in Node 2 (Sim)
AC 1 in Node 3 (Sim)
解析手法の妥当性が確認できる.
5. まとめと今後の課題
0.6
本稿では, バックオフによる優先制御を考慮し, 隠れ端末が存
0.5
在する IEEE 802.11e 無線マルチホップネットワークのスルー
0.4
プット特性を解析的に得た. 本解析では直線状片方向マルチネッ
0.3
トワークを検討し, 優先, 非優先フローが存在する場合につい
0.2
て, ネットワークスループットを優先度ごとに導出した. また,
0.1
本解析では CW の差別化の効果を表現した. 得られた解析結果
とシミュレーションの比較により解析の妥当性を示した.
0
0
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Offered load per ACs [Mbps]
図 5 4 ホップネットワークにおける, 送信負荷に対する AC 1 の衝
考慮し, 無線マルチホップネットワークのスループット特性を
解析的に導出することが挙げられる. AIFS の差により, AC 間
突率
でアクセス競合が可能な期間が異なるため, さらに細部まで考
0.9
AC 2 in Node 0 (Num)
AC 2 in Node 1 (Num)
AC 2 in Node 2 (Num)
AC 2 in Node 3 (Num)
0.8
0.7
Collision Probability of AC 2
今後の課題として, 本稿において考慮していない AC 間の
AIFS による効果を含めた IEEE 802.11e EDCA の優先制御を
慮する必要性がある.
AC 2 in Node 0 (Sim)
AC 2 in Node 1 (Sim)
AC 2 in Node 2 (Sim)
AC 2 in Node 3 (Sim)
謝
辞
本 研 究 の 一 部 は 科 学 研 究 費 補 助 金 (No.
0.6
23656249, No.
23360167) の補助を受けて行われた．ここに深謝の意を表する．
0.5
文
0.4
0.3
0.2
0.1
0
0
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Offered load per ACs [Mbps]
図 6 4 ホップネットワークにおける, 送信負荷に対する AC 2 の衝
突率
末が常に送信フレームを保持していないため, 発生したデータ
量と同じ量を転送することができる. しかし, 送信負荷が高く
なると, AC 2 のフローは優先制御により, AC 1 よりも低い負
荷で最大となる. AC 1 のフローのネットワークスループット
が最大となる送信負荷以下においては, AC 1 は常にフレーム
を保持しておらず送信負荷に従いスループットが増加する. 対
して, AC 2 は優先制御により両端端末間スループットは低下す
る. さらに高い送信負荷のとき, AC 1 のフロー上のある端末が
常に送信フレームをもつようになり, AC 1 のネットワークス
ループットは最大となる.
図 5, 6 は, ホップ数 4 における送信負荷に対する端末 i の AC
1, 2 の衝突率である. 4 ホップネットワークでは, 隠れ端末によ
る送信フレームの衝突は端末 0 においてのみ生じる. そのため,
端末 0 の衝突率は AC 1, 2 ともに他端末よりも高い. また, AC
2 は同端末内の AC 1 と同時に BT を 0 とするとき内部衝突が
生じる. そのため, AC 2 の衝突率は AC 1 の衝突率よりも各端
献
[1] IEEE Std 802.11e specific requirements Part 11: Wireless
Lan Medium Access Control (MAC) and Physical Layer
(PHY) Specifications, Amendment 8:Medium Access Control (MAC) Quality of Service Enhancements, 2005.
[2] Y. Gao, D. Chui, and J. C. S. Lui,”Determining the end-toend throughput capacity in multi-hop networks: methodology applications,” Proc. The SIGMETRICS/Performance
2006, pp. 39-50, June. 2006.
[3] M. Inaba, Y. Tsuchiya, H. Sekiya, S. Sakata, and K. Yagyu,
”Analysis and experiments of maximum throughput in wireless multi-hop networks for VoIP application,” IEICE Trans.
on Communications, vol.E92-B, no.11, pp.3422-3431, Nov.
2009.
[4] Y. Tsuchiya, M. Inaba, M. Matsumoto, H. Sekiya, S.
Sakata, and K.Yagyu, ”Analysis of maximum UDP throughput of short-hop string networks for VoIP applications,”
Proc. WPMC, September. 2009.
[5] 眞田 耕輔, 史 進, 関屋大雄, 阪田 史郎, ”隠れ端末問題を考慮し
た無線マルチホップネットワークにおけるマルコフ遷移図を用
いたスループット及び遅延解析”, 電子情報通信学会複雑コミュ
ニケーションサイエンスワークショップ, Aug. 2013.
[6] Y. Xiao, “ Performance Analysis for Priority Schemes for
IEEE 802.11 and IEEE 802.11e Wireless LANs, ” IEEE
Trans. Wireless Comm., vol. 4, no. 4, pp. 1506-1515, 2005.
[7] G. Bianchi, ”Performance analysis of the IEEE 802.11 distributed coodination function” IEEE J. Sel Commun., vol.
18, no. 3, pp. 535-547, Mar. 2000.
[8] 下山田 祐太, 眞田 耕輔, 史 進, 関屋 大雄, ”IEEE 802.11e
EDCA 直線状無線マルチホップネットワークにおける非飽和及
び飽和スループット解析”, 電子情報通信学会ネットワークシス
テム研究会, July. 2013.
[9] B. Xiang, M. Yu-Ming, and X. Jun, ”Performance investigation of IEEE802.11e EDCA under non-saturation condition
based on the M/G/1/K model,” in Proc. ICIEA, 2007, pp.
298-304
—6—
© Copyright 2024 ExpyDoc
