論

次世代ネットワークソフトウェア論文特集

文

無線アドホックネットワークにおけるフロー間の公平性の改善
オユーンチメグ シャグダル†中川 健治††

張兵†

Achieving Per-Flow Fairness in Wireless Ad Hoc Networks
Oyunchimeg SHAGDAR† , Kenji NAKAGAWA†† , and Bing ZHANG†

あらまし 無線アドホックネットワークは，将来のモバイル通信の一形態として最も注目されており，IEEE
802.11 準拠の無線 LAN デバイスの利用が一般的と考えられる．無線アドホックネットワークの広い実現のため，
QoS（Quality of Service）制御の要求が高まっている．その中でも，フロー間の公平性は非常に重要な要素である．伝統的な有線ネットワークでは，フロー間における公平性の問題は，主にリンク層によるものだが，無線アドホックネットワークにおいては，MAC 層にも大きく起因する．具体的には，IEEE 802.11MAC は無線端末間に公平なチャネル割当を行っているが，フロー間の公平を実現するには，フロー数に応じてチャネル割当を行う方式が必要となる．そこで，本研究では，各フローに同等なチャネルアクセスを割り当てることで，MAC層でのフロー間の公平を実現する方式を提案する．提案方式は公平性の改善だけでなく，ネットワーク全体のパ
フォーマンス，チャネルユーティリティなども改善できる．また，ネットワークシミュレータによる特性評価を行い，提案方式の有効性を確認した．
キーワード

無線アドホックネットワーク，公平性，IEEE 802.11MAC，DCF

1. ま え が きトワークにおいて，フロー間の公平性が劣る主な原因

アドホックネットワークは，基地局や交換機等のイ

ワーク上に UDP トラヒックと TCP トラヒックが混

ンフラストラクチャに依存しないネットワークであ在する場合において，ボトルネックでふくそうが発生は，異なるトラヒックの混在である．例えば，ネット

り，将来のモバイル通信の一形態として，最も注目さすると，TCP はふくそう制御を行い，転送レートを減れている [1]．無線アドホックネットワークにおいて，少させるが，UDP は転送レートを変化させない．こIEEE 802.11 準拠の無線 LAN デバイスの利用が一般のような非対称的な対応の結果，最悪の場合，TCP的であり，その応用はセンサネットワーク，パーソナ

トラヒックが停止されるという最も不公平な状態も発

ル・エリア・ネットワーク，第四世代セルラシステム

生し得る．有線ネットワークで生じる公平性の問題のにおける基地局中継網などの，様々なアプリケーショ改善策として，バッファ・マネージメント [3]，またはンへの適用が想定されている [2]．

スケジューリング [4], [5] といったリンク層に着目した

無線アドホックネットワークの広い実現のため，QoS

方式が多く提案されている．しかし，無線アドホック（Quality of Service）制御の要求が高まっている．QoS

ネットワークにおける公平性の問題は，MAC 層にもはサービスの品質を意味し，公平性，安定性，通信の大きく影響されるため，従来の手法だけでは十分に解パフォーマンスなどの様々な要素に着目しなければな決されない．無線アドホックネットワークで発生する

らない．その中でも，フロー間の公平性は重要な要素

フロー間の公平性の問題は，下記のように分類できる．

である．今まで，公平性に関する研究は，有線ネット（ 1 ） リンク層におけるフロー間の公平性の問題

ワークを対象に数多く行われてきた [3]〜[5]．有線ネッ†

ATR 適応コミュニケーション研究所，京都府
ATR††

無線アドホックネットワークは，専用ルータや基地局などのインフラに依存しないネットワークである．

Adaptive

Communication

Research

Laboratories,

直接通信が行えない端末間の通信は，途中の端末のKyoto-fu, 619–0288 Japan

中継によって行われる．このように，他のフローに中長岡技術科学大学，長岡市

継サービスを与える無線端末のバッファは，複数のフNagaoka University of Technology, Nagaoka-shi, 940–2188

ローに共有される．したがって，中継端末のバッファJapan

電子情報通信学会論文誌 B Vol. J88–B

c （社）電子情報通信学会 2005
No. 3 pp. 539–550 

539

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3が各フローに不公平に割り当てられることが原因で，フロー間の公平性が劣るという問題が生じる．このように発生するフロー間の不公平の問題は，従来のリンク層に着目した方式で改善できると考えられる．

図 1 リンク層におけるフロー間の不公平の例
Fig. 1 Per-ﬂow unfairness due to the link layer.

（ 2 ） MAC 層におけるフロー間の公平性の問題
無線アドホックネットワークでは，複数の移動端末がえる．この場合，M1 及び M2 で発生するトラヒック

無線チャネルを共有するため，お互いの通信範囲に位のレートを G，無線リンク帯域幅を B ，更に，M1 と置する無線端末が，同時にパケット送信を行うと衝突が起こり，通信が失敗する．そこで，MAC 層では，各M2 間及び，M2 と M3 間に使用される帯域幅をそれ
ぞれ B12 と B23 とする．また，M2 のリンク層におい端末に均等にチャネル割当を行う DCF（Distributed
Coordination Function）チャネルアクセス方式 [6] が（First In First Out）が使用される場合，バッファに使用されている．しかし，複数のフローをもつ端末と，格納されている Flow1 と Flow2 のパケット数の割合て，最も一般的なスケジューリング方式である FIFO

一本のフローしかもたない端末が，同一通信範囲に存を QF low1 : QF low2 とし，各フローが得るスループッ

在する場合，フロー間の公平性が劣る．そのため，端ト（T h(F low1) と T h(F low2)）を計算する．

末に平等にチャネルを割り当てるだけでなく，フロー

ここで，計算上の簡略化のため，無線空間においてパ数に応じたチャネルアクセス方式が必要とされる．

ケットロスが発生しないと仮定する．まず，G < B/2

そこで，本研究では，無線アドホックネットワーク
において，リンク層だけでなく，MAC 層においても，フロー間の公平性の改善を行う方式を提案する．具体的には，まず，リンク層において，フローごとにバッファを設け，RR（Round Robin）スケジューラ [4] を用いることにより，各フローのパケットを MAC 層へ平等に送信する．次に，MAC 層での公平の実現のた
め，DCF チャネルアクセス方式をもとに，各フローが同等なチャネルアクセスを行う方式を提案する．本
提案方式はフロー間の公平性だけでなく，ネットワー
ク全体のパフォーマンス，チャネルユーティリティなども改善できる．
以下，2. では，リンク層及び MAC 層におけるフロー間の公平性が劣る実例を挙げ，それについて考察する．3. で関連研究を紹介し，4. で提案方式の説明
及び，特性解析を行う．5. では，提案方式の有効性を評価する．最後に，6. で結論を述べる．

2. 無線アドホックネットワークにおける公平性の問題
無線アドホックネットワークにおいてフロー間の不公平の主な原因はリンク層及び，MAC 層に存在する．
ここで，フロー間の公平性が劣る実例を挙げ，それについて考察を行う．

2. 1 リンク層におけるフロー間の不公平の例
図 1 で示すように，端末 M1 が端末 M2 を経由して端末 M3 へデータ送信（Flow1）し，更に端末 M2
からも端末 M3 へデータ送信（Flow2）する場合を考
540の場合を考える．このとき B12 = G であるため，

QF low1 : QF low2 = G : G = 1 : 1(1)となる．ここで M2 と M3 間における残りの帯域は，

B − B12 =B − G であるため，式 (1) より，Flow1 とFlow2 が使用できる最大帯域幅はそれぞれ， B−Gと2なる．各フローが得るスループットは，T h(F low1) = T h(F low2) = G



(if

G < (B − G)/2)


T h(F low1) = T h(F low2) = (B − G)/2



(if

(2)

(B − G)/2 ≤ G < B/2)となる．ここで式 (2) の上段は，G が使用できる最大帯域幅より小さい場合であり，各フローのスループッ
トは G に等しくなる．式 (2) の下段は，G が使用できる最大帯域幅より大きい場合を表し，各フローのス
ループットは使用できる最大帯域幅となる．
次 に ，G ≥ B/2 の 場 合 を 考 え る ．こ の と き

B12 =B/2 であるため，
QF low1 : QF low2 = B/2 : G(3)となる．式 (3) より，M2 と M3 間において，Flow1 と
B/2
Flow2 に割り当てられる帯域幅はそれぞれ， G+B/2
×G
B23 と G+B/2 × B23 となる．B23 = B − B12 = B/2

であるため，各フローが得るスループットは， T h(F low1) =B2(if2(B + 2G)

 T h(F low2) = BG
(if
B + 2GG ≥ B/2)(4)
G ≥ B/2)

論文／無線アドホックネットワークにおけるフロー間の公平性の改善となる．式 (2) と式 (4) に基づいて，各フローのスルー
プットを図 2 に表す．図 2 より，G の増加に伴って，フロー間の公平性が著しく悪化することが分かる．このようなフロー間の不公平の問題は，転送端末のバッ
T h0 = T h1 = GT h0 = G,(if G < B/3)
T h1 = (B − G)/2
(if B/3 ≤ G < B/2)

T h0 = B/2,

ファが各フローに不公平に割り当てられるため発生し，T h1 = B/4(if

G ≥ B/2)(5)

これはリンク層での不公平が原因と考えられる．

2. 2 MAC 層におけるフロー間の不公平の例

式 (5) の上段は，G が低いために，無線帯域が保証

図 3 のトポロジーを考える．本モデルは，S1 と M1

され，各フローのスループットが G に等しくなるこ

間及び，S1 と M2 間にそれぞれ，Flow1 と Flow2 がとを示す．式 (5) の下段は，各送信端末（S0 と S1）存在する．更に，S1 と同一通信範囲に位置する S0 とが無線リンク帯域の半分以上の使用を要求される場

M0 間に Flow0 が存在する．前例と同様に，送信端末で発生する各トラヒックのレートを G，無線リンク帯合である．この場合，802.11MAC ベースの従来方
式は端末に平等にチャネルを割り当てるため，S0 とと Flow2 のスループットが等しくなり，それを T h1

S1 がそれぞれ，B/2 帯域を使用する．このときのチャネル割当の様子を図 4 に示す（ここで，短時間における端末間の不公平（ [7]）が問題とならないとと記す．更に，Flow0 のスループットを T h0 と記す．

仮定する）．図 4 から分かるように，S0 と S1 は順

域幅を B とする．S1 のリンク層において，バッファがフロー間に平等に割り当てられている場合，Flow1

802.11MAC ベースの従来方式では，端末間に平等な番にチャネルアクセスし，パケットを 1 個ずつ送信す

チャネルアクセス権利を与えるため，各フローが得る

る．したがって，フロー間のチャネルアクセスの割合

スループットは式 (5) で表される．

は，Flow0 : Flow1 : Flow2 = 2 : 1 : 1 と不公平になる．なお，式 (5) の中段は，S0 端末が要求する帯域 G
が B/2 に満たないため，S0 が G 帯域を使用し，残りの無線帯域 (B − G) が S1 がもつ Flow1 と Flow2の送信に割り当てられることを表す．式 (5) に基づいて，各フローのスループットを図 5 に示す．図 5 から分かるように，図 3 で示すモデルにおいても，フロー間の不公平の問題がある．この問題は，MAC 層でのFig. 2図 2 各フローのスループット（例 1）
Throughput achieved by individual ﬂows.

図 3 MAC 層におけるフロー間の不公平の例
Fig. 3 Per-ﬂow unfairness due to the MAC layer.

チャネルアクセス方式に起因するため，その解決は，Fig. 5図 5 各フローのスループット（例 2）Throughput achieved by individual ﬂows.

図 4 802.11MAC におけるチャネル割当の様子
Fig. 4 Channel access operation of the 802.11MAC.

541

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3

MAC 層に着目しなければならない．

3. 関 連 研 究
無線ネットワークにおける，フロー間の公平性に関する研究はいくつか行われてきた（ [8]〜[13]）．

を悪化させるおそれがある．

4. 提 案 方 式
DCF チャネルアクセス方式に基づき，無線アドホッ
クネットワークにおける，フロー間の公平性を改善す[8] はチャネルユーティリティと公平性の相互関係る方式を提案する．提案方式は，802.11MAC ベースに着目し，チャネルユーティリティの改善を優先しなの従来方式に若干の修正を加えるだけで，フロー間のがら，より公平なサービスを与えるパケット転送スケ

公平性だけでなく，ネットワーク全体のパフォーマン

ジューリングモデルを提案した．しかし，[8] はネット

ス，チャネルユーティリティなどを改善できる．

ワークトポロジー及び，各フローの情報を集中的に

4. 1 リンク層におけるフロー間の公平性の改善管理するスケジューラが存在すると仮定しているた

2. 1 から分かるように，フロー間の公平性がリンめ，アドホックネットワークには適用的でないと考えク層における不公平が原因で劣る場合がある．このよられる．

うな公平性の問題を解決するためには，リンク層に[9] はリンク層だけでなく，MAC 層でも優先順位

おけるフロー間の公平性を改善する必要がある．RRをもつバッファを設け，公平性及びチャネルユーティ（Round Robin）スケジューリング方式は FIFO スケ

リティの改善を行う方式を提案した．また，[10] はア

ジューリング方式に比べて，リンク層におけるフロー

クセスポイントが集中的にパケット転送スケジューリ

間の公平性が改善できると考えられる．FIFO スケ

ングを行うことで，フロー間の公平性を改善した．[11]

ジューラを使用する無線端末はすべてのフローに対しは MAC 層がパケットロスを観測し，トラヒックレーて 1 個のバッファしかもたないため，その名のとおり，

トをコントロールする方式を提案した．しかし，[9]〜パケットがバッファに格納された順で送信される．し[11] では，リンク層におけるフロー間の公平性の問題
だけを改善し，MAC 層におけるフロー間の公平性のたがって，パケットがフロー間における不公平な状態
でバッファに格納されていれば，パケットは不公平の問題に未着手であるため，トポロジー依存となる．更ままで MAC 層へ送信されることとなる．それに対しに，[10] はアクセスポイントなどのインフラを必要とて，RR スケジューラはフローごとに異なるバッファ

する欠点がある．

を設けることにより，パケットを MAC 層へ送信する

MACAW [12] では，コンテンションウィンドウ [6]とき，各バッファからバケットを 1 個ずつ取り出してのばらつきによって生じる不公平を指摘し，その解決送信を行うため，リンク層においてフロー間の公平性方法として，無線端末同士がバックオフに関するパラを改善することができる．

メータを交換することによって，コンテンションウィ

本提案方式では，リンク層におけるフロー間の不公

ンドウを一致させる方式を提案した．この方式は，短平を改善するために，リンク層に RR スケジューラを時間における端末間の公平性の問題（ [7]）に有効で使用する．具体的には，送信すべきパケットがリンクあるが，フロー間の公平性には対応できない．更に，層に到着すると，パケットに含まれるソケット情報（送MACAW では複数のフローの送信端末に，複数のバッ受信端末の IP アドレスとポート番号）をもとに，どクオフカウンタをもたせることによって，フロー間ののフローのパケットであるかを識別し，異なるフロー

公平性が改善できると述べているが，それに対する詳のパケットを異なるバッファに格納する．パケットをしい検討は行われていない．また，このような手法は，バッファから取り出すときは，各バッファからパケッ

MAC802.11e [13] でも提案された．MAC802.11e は，トを 1 個ずつ取り出して MAC 層へ送信する．提案方

フロー間のプライオリティに注目した研究であるが，式の MAC 層は，チャネルアクセス権利を獲得してか

フロー間の公平性にも有効であると考えられる．しから，異なるフローのパケットを複数送信するが，そのし，公平性に関する検討が十分に検証されていないの

フロー数の決定はリンク層で行われる．図 6 に，そのが現実である．MACAW や MAC802.11e における複アルゴリズムを示す．これは，各バッファにパケット数のフローの送信端末に，複数のバックオフカウンタが格納されているかをチェックし，送信するフロー数をもたせる方式は，フロー数が増加するに伴ってチャを求めるものである．図 6 における MAX f について

ネル競争が激しくなり，干渉やチャネルユーティリティ

は，後述する．

542

論文／無線アドホックネットワークにおけるフロー間の公平性の改善

4. 2 MAC 層におけるフロー間の公平性の改善

いった様々な要素によって異なる．現段階では，同一複数のフローをもつ無線端末は，チャネルアクセスの通信範囲に位置する無線端末において，MAX f を権利を獲得してから，フロー数に応じて複数のパケッ決める各要素が同様であると考え，同一通信範囲に位ト送信を可能にする．つまり，従来の DCF チャネル

置するすべての無線端末における MAX f が同一であ

アクセス方式においては，送信端末はパケット送信がることを前提条件とする．

成功すれば，ポストバックオフ処理（通信が成功した

図 7 は，パケット送信アルゴリズムであり，提案際，次に送信すべきパケットの有無にかかわらず，特方式において追加した動作を太字で示す．つまり，パ定のバックオフ時間を待つ処理）に入るが，本方式にケット送信が成功し，次に送信すべき異なるフローのおいて，複数のフローのパケットをもつ送信端末は，パケットが存在すれば，ポストバックオフ処理に入らパケット送信が成功した後にポストバックオフ処理をず，次のパケットを送信する．これを繰り返すことで，行わず，DIFS（DCF Inter Frame Space）[6] 時間だ

1 回のチャネルアクセスで異なるフローのパケットをけを待ってから，次の異なるフローのパケットを送信

複数送信することができる．
図 8 に，図 3 で示すネットワークモデルに提案方式

する．
無線端末が 1 回のチャネルアクセスで送信するパを適用した場合のチャネル割当の様子を示す．図 3 モケットの最大数を MAX f とすると，端末がもっている

デルにおいて，S1 は 2 本のフローをもつため，図 8 でフロー数が MAX f を超える場合は，MAX f だけ送信示すように，1 回のチャネルアクセスにおいて Flow1を行う．この場合，公平性は若干劣るが，802.11MACと Flow2 のパケットをそれぞれ 1 個ずつ送信する．しベースの従来方式より公平性の改善ができると考えらたがって，提案方式は，各フローにおいて同等なス

れる．MAX f は，無線帯域，無線リンクの状態，ネッ
トワークトポロジー，チャネルを共有するフロー数とFig. 6図 6 フロー数の決定
Determining number of ﬂows.

Fig. 8図 7 パケット送信アルゴリズム
Fig. 7 Packet transmission algorithm.

図 8 提案方式におけるチャネル割当の様子
Channel access operation of the proposed scheme.

543

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3

ループットが得られ，フロー間の公平が実現できる．

と，Th は次式で表される．



4. 3 提案方式の特性と解析
ここで，提案方式の特性を理論的に解析する．解析Th =は，公平性及び，チャネルユーティリティに着目する．
また，解析に使用するパラメータの定義及び，説明を行う．
提案方式の公平性に関する特性を検証する．まず，複数のフローからなるシステムの公平性を評価するパラメータである FairnessIndex の説明を行う．
本研究では，[14] において，式 (6) のように定義された FairnessIndex を使用する．

FairnessIndex = 1 −i=1G < B/3)
G ≥ B/3)(8)

式 (8) と式 (6) より，提案方式における FairnessIndex
両方式における FairnessIndex の比較を図 9 に示す．
点線は 802.11MAC ベースの従来方式，実線は提案方式における FairnessIndex である．
次に，図 3 で示すモデルを対象に，802.11MAC
ベースの従来方式と提案方式における FairnessIndexを求める．802.11MAC ベースの従来方式おける FairnessIndex は，式 (5) と式 (6) より，式 (9) となる．

|xi − Ave|2(n − 1)Ave

(if
(if

は，G の全範囲で 1 となる．これらの結果に基づき，

4. 3. 1 公平性に関する特性

n


G
B/3

(6)

ここで，n は全フロー数，xi はフロー i のスループッ

FairnessIndex =ト，Ave はネットワークの平均スループットを示す．


1(if G < B/3)
 3(B − G)/(2B)(if B/3 ≤ G < B/2)


 3/4
(if G ≥ B/2)

(9)

式 (6) で定義される FairnessIndex は 0 から 1 の間の値をとり，その値が 1 に近いほど，フロー間の公平性

提案方式は図 8 より，フロー間において公平であるが優れていることを意味する．右辺の第 2 番目の項のため，G の全範囲において各フローのスループットが分子は，各フローのスループットと平均スループット

等しくなり，FairnessIndex = 1 となる．これらの結の差の絶対値の和を示し，分母は，ネットワークが一果に基づき，両方式における FairnessIndex の比較を

番不公平なとき，つまり，1 本のフローだけが帯域を

図 10 に示す．点線は 802.11MAC ベースの従来方式，

使用し，他のフローに帯域が割り当てられていない状

実線は提案方式における FairnessIndex である．図 9

態の，各フローのスループットと平均スループットのと図 10 から，提案方式は，802.11MAC ベースの従差の絶対値を示す．ここで，2. で挙げたネットワーク

来方式に比べて，フロー間の公平性が改善できること

モデルを対象に FairnessIndex を計算する．

が分かる．

まず，図 1 で示すモデルを対象に，802.11MAC
ベースの従来方式と提案方式における FairnessIndex

4. 3. 2 チャネルユーティリティに関する特性
チャネルユーティリティは，チャネルを有効に活用を計算する．802.11MAC ベースの従来方式におけるFairnessIndex は，式 (2) と式 (4) を式 (6) に代入す
ることにより，式 (7) となる．



 1

(if G < B/2)
(7)
FairnessIndex =2B/(2G + B)
(if G ≥ B/2)

図 9 各方式における FairnessIndex の比較（例 1）
Fig. 9 FairnessIndex comparison of each scheme.

提案方式はリンク層において RR スケジューラを用いるため，M2 における Flow1 用と Flow2 用の両方のバッファにパケットが格納されている限り，パケッ
トがフロー間に公平に MAC 層へ送信される．更に，MAC 層において，フロー間で公平にチャネル割当が行われるため，各フローのスループットは等しい．そこで，Flow1 と Flow2 ののスループットを Th と記す
544

図 10 各方式における FairnessIndex の比較（例 2）
Fig. 10 FairnessIndex comparison of each scheme.

論文／無線アドホックネットワークにおけるフロー間の公平性の改善

している度合を表し，各端末が無線チャネルを共有す

レートのトラヒックが混在しているが，本シミュレー

る無線アドホックネットワークでは，重要なパラメー

ションでは公平性に注目しているため，同一レートのタである．チャネルユーティリティを評価するためにトラヒックを用いることとする．本シミュレーション

式 (10) を用いる．

では，表 2 で示す三つの方式（ori(FIFO)，ori(RR)，

ChannelUtility =使用時間
× 100 [%] (10)トータル時間

ここで，使用時間は干渉などによって失敗に終わった
通信時間を除く，チャネルを有効に活用した時間を表す．
提案方式では，複数のフローをもつ送信端末は，1 回のチャネルアクセスで複数のパケット送信を行っているため，802.11MAC ベースの従来方式に比べ，パケッ
トごとの送信に必要なバックオフ時間が節約できる．
それによって，式 (10) での使用時間が増加し，チャネルユーティリティが向上する．また，チャネルユー
ティリティの向上は，ネットワーク全体のパフォーマンスの改善にもつながる．

proposed）の比較を行う．提案方式では，1 回のチャ
ネルアクセスで送信できる最大のフロー数 (MAX f)
を 4 に固定する．シミュレーションでは，MAC 層における公平性の改善を確認できるシングルホップモデ
ル，リンク層における公平性の改善を確認できるマル
チホップモデル更に，リンク層及び MAC 層における公平性の改善を総合的に確認できる複合型ネットワー
クモデルを対象に，特性評価を行う．

5. 1 シングルホップモデル
図 11 で示すネットワークモデルを対象に特性評価を行う．本モデルにおいて，S0 と S1 はお互いの通信範囲に位置する．S0 は 1 本のフロー，S1 は n 本のフローをもつとする．
まず，図 11 において n = 2 の場合を考える．図 12

5. シミュレーション評価に，CBR パケット送信間隔が 10 ミリ秒の場合の，各提案方式の有効性を確認するために，NS ネットワー

うに，ori(FIFO) では各フローのスループットの差がクシミュレータ [15] を用いて評価を行う．シミュレー

フローのスループット比較を示す．図 12 から分かるよ

ションで用いるパラメータを表 1 に示す．シミュレー
ション実験で，UDP トラヒックと TCP トラヒック両方において，各フローのスループット，ネットワークのトータルスループット，フロー間の公平性及び，チャ
ネルユーティリティの各面で評価を行う．公平性及び，Table 2方式
ori(FIFO)
ori(RR)
proposed

表 2 比較する方式の特徴
Characteristics of individual schemes.
リンク層
FIFO スケジューリング方式
RR スケジューリング方式
RR スケジューリング方式

MAC 層
IEEE 802.11b
IEEE 802.11b
提案方式

チャネルユーティリティは，それぞれ式 (6)，式 (10)で算出する．更に，CBR のパケット送信間隔は [16]を参照に，データ，ビデオ及び音声通信などを想定して設定した．[16] ではフロー間のプライオリティに注目してシミュレーションを行っているため，異なる

表 1 シミュレーションパラメータ
Table 1 Simulation parameters.
シミュレーション時間
50 [s]
アンテナ
Omni directional
無線伝搬モデルFree space & Two-ray
通信範囲250 [m]
MAC プロトコル
IEEE 802.11b（RTS/CTS 使用）
無線リンクの帯域
2 [Mbit/s]
バッファタイプ
FIFO, RR
バッファサイズ50 [pkts]
ルーティングプロトコル DSDV
トラヒックタイプ
UDP（CBR），TCP（FTP）
CBR パケット送信間隔
1〜20 [ms]TCP 最大ウィンドウサイズ 20 [pkts]
パケットサイズ512 [Byte]，1 [kByte]

図 11 シングルホップモデル
Fig. 11 Single-hop model.

図 12

各フローのスループット（シングルホップモデル）

Fig. 12

Throughput achieved by each ﬂow.

545

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3
表 3 トータルスループット（シングルホップモデル）
Table 3 Total throughput.
ori(FIFO)
ori(RR)
proposed

691.49 [kbit/s]
691.90 [kbit/s]
699.68 [kbit/s]

図 14 FairnessIndex の比較（CBR）
Fig. 14 FairnessIndex comparison (CBR).

図 13 FairnessIndex の比較（シングルホップモデル）
Fig. 13 FairnessIndex comparison of each scheme.

大きい．それに比べて，ori(RR) では Flow1 と Flow2のスループットはほぼ等しいが，Flow0 のスループッ
トが他のフローに比べて著しく高い．これらの従来

図 15 FairnessIndex の比較（TCP）
Fig. 15 FairnessIndex comparison (TCP).

方式では，Flow1 及び Flow2 のスループットの和はFlow0 のスループットに等しくなる．それに対し，提る．図 10 の横軸は CBR 送信レート (G) を表して案方式では，各フローのスループットがほぼ等しい値

おり，G が CBR のパケット送信間隔（ここで ∆t とになることが確認できた．

示す）と G = P acketSize/∆t の関係をもつ．ここネットワークのトータルスループットの比較を表 3

で，P acketSize（パケットサイズ）は一定であるたに示す．表 3 より，提案方式がその他の方式より約め，∆t の減少（図 13 の横軸）は G の増加（図 10 の

8 [kbit/s] 高いスループットを得ることができた．こ横軸）を意味し，図 10 と図 13 で示す FairnessIndexのトータルスループットの改善は，チャネルユーティ

は同様な傾向を示すことが明らかである．図 13 からリティの改善によるものであると考えられる．これら分かるように，proposed における FairnessIndex は，の結果から分かるように，提案方式はフロー間の公平

横軸の全範囲で 1 であるのに対して，ori(RR) にお性の改善だけでなく，ネットワーク全体のパフォーマ

いては，横軸の左端に 1 をとるが，その後は 1 からンスを改善できることが明らかとなった．

ほぼ 0.75(= 3/4) まで減少し，それ以降は 0.75 に定各方式における FairnessIndex の比較を表す．図の右

図 13 は，CBR パケットの送信間隔の変化に対する，

着する．これらの FairnessIndex は，図 10 で表す各
FairnessIndex と同様な傾向を示しており，理論的な

端に FTP の結果を併せて示す．ori(FIFO) は，CBR

解析の正当性が確認できた．

送信レートが増加するにつれて，フロー間の公平性が次に，S1 がもつフロー数 n が 1〜6 と変化する場合

著しく悪化する．ori(RR) は Flow1 と Flow2 間の公における，フロー間の公平性を調べた．図 14 は CBR

平性の改善ができた分，FairnessIndex が ori(FIFO)

通信（パケット送信間隔が 10 ミリ秒），図 15 は TCP

より優れるが，Flow0 のスループットが他のフローに通信を対象にした結果を示す．これらの結果より，S1

比べ，依然として高いため，FairnessIndex は提案方式がもつフローの数が増加するに伴って，両方の従来方より劣る．これらの従来方式において，CBR 送信レー式におけるフロー間の公平性が劣っていくことが分

トが増加するに伴って，フロー間の公平性が悪化する

かった．それに対して，提案方式は n の全範囲で公ことは，式 (5) で説明される．図 13 で示すように，提平性が優れており，S1 がもつフロー数 n が MAX f

案方式は，全送信レートにおいて，FairnessIndex が1 に近い値を得た．ここで，図 13 で表す ori(RR) と
proposed の FairnessIndex と 4. 3. 1 で得られた結果（図 10）で表す各 FairnessIndex の傾向について考え(= 4) を超える場合でも，公平性の改善が確認できた．
最後に，S1 がもつフロー数 n に対する，チャネルユー
ティリティの特性評価を行った．図 16 が CBR 通信（パケット送信間隔が 10 ミリ秒）を対象にした結果を546

論文／無線アドホックネットワークにおけるフロー間の公平性の改善
表4

トータルスループット（マルチホップモデル）
Table 4 Total throughput.
ori(FIFO)
ori(RR)
proposed

図 16 ChannelUtility の比較（シングルホップモデル）
Fig. 16 Channel utility comparison (single-hop model).

334.48 [kbit/s]
334.48 [kbit/s]
398.46 [kbit/s]

ファについて考える．ori(RR) における，802.11MAC
ベースの従来方式は，端末間に同等な帯域を割り当てており，M1 が 1 本のフロー（Flow1），M2 が 2 本のフロー（Flow1，Flow2）の送信を行うため，M1 が送信する Flow1（M2 が受信する）のレートは M2 が送信する Flow1 及び Flow2 のレートの和に等しくなる．
したがって，M2 が受信する Flow1 のレートは M2 が送信する Flow1 のレートより高いことが分かる．よっ図 17 各フローのスループット（マルチホップモデル）
Fig. 17 Throughput achieved by individual ﬂows.

て，M2 の Flow1 用のバッファにもパケットがたまることになり，RR スケジューラは，Flow1 用と Flow2用の両方のバッファからパケットを順番に取り出して示す．結果より，提案方式は従来方式と比べ，最大で送信することができ，フロー間に公平性が改善される．

約 2%近くのチャネルユーティリティの改善が確認でそれに対して，提案方式はフロー間に同等な帯域を割きた．

り当てるため，M2 に到着する Flow1 と M2 から送5. 2 マルチホップモデル

信される Flow1 のレートがほぼ等しくなる．したがっ

図 1 に示すマルチホップモデルを用いて，特性評価て，M2 の Flow1 用のバッファにおいて，パケットのを行う．M1 と M2 はそれぞれ，M3 へデータ通信を受信と送信は同等なレートで行われる．これによって，行っている．M2 は，M1 と M3 間のフローに中継サー
ミリ秒の場合の，各フローのスループット比較を示す．

M2 の Flow1 用のバッファが空となる状態がたびたび生じるため，RR スケジューラが Flow2 のパケットを連続して送信してしまい，Flow1 と Flow2 間の公平

図 17 から分かるように，ori(FIFO) では各フローの性が劣ったと考えられる．

ビスも与える．図 17 は，CBR パケット送信間隔が 10

スループット差が非常に大きい．それに比べ，提案方表 4 にネットワークのトータルスループットの比較

式は両フローのスループット差が小さい．しかし，本モを示す．表 4 で示されるように，提案方式は，従来方デルにおいて，ori(RR) が公平性の面では，提案方式

式に比べて 64 [kbit/s] 高いトータルスループットを得よりも優れている．その原因について以下のように考ることができた．表 3 と表 4 から，提案方式によるえる．図 1 において，M2 における RR スケジューラ

トータルスループットの改善は，シングルホップモデ

が Flow1 と Flow2 を公平に送信するためには，Flow1

ル（図 11）においてわずかであるが，本マルチホップ

用と Flow2 用の両方のバッファからパケットを順番にモデル（図 1）においてその改善は非常に大きいこと

取り出して送信する必要がある．もし，Flow1 用またが分かる．その原因は次のように考えられる．図 11

は Flow2 用のバッファのどちらかが空である状態が続のようなシングルホップモデル (n = 2) において，提くと，RR スケジューラがもう一方のフローのパケッ

案方式は，S0 に割り当てられる帯域を減少させ，そのトを連続して送ることになり，フロー間の公平性が劣分 S1 に割り当てる帯域を増加させることになる．こる．具体的に，図 1 に示す M2 における Flow2 用のれは，S0 がもつ Flow0 のスループットが ∆ Th だけバッファを考える場合，Flow2 は M2 で発生しており，減少し，S1 がもつ Flow1 と Flow2 のスループットのトラヒック発生レートが無線リンク帯域より高いた

和が ∆ Th だけ増加することを意味する．トータル

め，M2 のリンク層における Flow2 用のバッファにはスループットは，全フローのスループットの和で示さ

パケットがたまっている状態となる．次に，ori(RR)

れるため，提案方式によって得られるトータルスルーと提案方式において，M2 における Flow1 用のバッ

プットの改善分は次式で表される．
547

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3∆Total (SingleHop) = −∆T h + ∆T h + α = α

ここで，α は提案方式におけるチャネルユーティリ

99%，提案方式は 92%の公平性の改善ができた．しかし，TCP トラヒックの場合，FairnessIndex がすべての方式において，0.30 を上回らない．これは，Flow1の送信 TCP がランダムロスなどに敏感に反応し，頻ティの改善によるスループットの増加分を示す．一方，

繁にふくそう制御を行ってしまうためだと考えられる．

図 1 で示すマルチホップモデルにおいても，提案方式

この問題に関しては，TCP プロトコルが無線ネット(11)

は M1 に割り当てられる帯域を減少させ，その分 M2に割り当てられる帯域を増加させる．これは，M1 とM2 間で転送される Flow1 のスループットが ∆ Th だ
け減少し，M2 と M3 間で転送される Flow1 と Flow2のスループットの和が ∆ Th だけ増加することを意味する．しかし，本マルチホップモデルにおけるトー
タルスループットは，M2 が送信する Flow1 と Flow2のスループットの和で示されるため，提案方式によるトータルスループットの改善分は次式で表される．

∆Total (MultiHop) = ∆T h + α(12)

式 (11) で示すように，シングルホップモデルにおいて，トータルスループットの改善は，提案方式によるチャネルユーティリティの改善によるもののみである．
それに対して，式 (12) で示すように，本マルチホップ
モデルにおいて，トータルスループットの改善は，提案方式によるチャネルユーティリティの改善だけでなく，帯域幅の割当処理によるものもある．したがって，
図 11 のようなシングルホップモデルに比べて，本マ
ルチホップモデルにおけるトータルスループットの改善が大きいことが分かる．
図 18 に CBR パケット送信間隔の変化に対する，

ワークにおいてかかえている様々な問題 [17] を解決することが先決であると考えられる．最後に，図 19
は，CBR パケット送信間隔の変化に対する，チャネ
ルユーティリティの特性比較を表す．図 19 から，本マルチホップモデルにおいても，提案方式によるチャ
ネルユーティリティの改善が確認できた．

5. 3 複合型モデル
5. 1 と 5. 2 において，フロー間の不公平の原因が主に MAC 層またはリンク層に存在するネットワーク
モデル（図 11 と図 1）を対象に特性評価を行った．
ここで，図 11 と図 1 を包含するネットワークモデル（複合型モデルと呼ぶことにする）を対象に，フロー間の不公平の原因がリンク層と MAC 層の両方に存在す
る場合において，提案方式の特性評価を行う．複合型モデル（図 20）において，S0 と M0 間に Flow0，S0と M1 間に Flow1，更に S0 を経由して S1 と M2 間に Flow2 が存在する．図 21 は，CBR パケット送信間隔の変化に対するネットワークの公平性の比較を示す．図 21 から，ori(FIFO) と ori(RR) は CBR 送信
レートが増加するに伴って，フロー間の公平性が著しく悪化する．それに対して，提案方式はフロー間の公ネットワ ー ク の 公 平 性 の 比 較 を 表 す．図 18 で は ，ori(FIFO) において，CBR パケット送信間隔が 0.005
秒及び 0.001 秒の場合，FairnessIndex は 0.009 及び0.0005 という非常に小さい値をとる．図 18 から，ori(FIFO) で，CBR 送信レートが増加するに伴って，フロー間の公平性が著しく悪化することが確認できた．
これに対し，提案方式及び ori(RR) は，FairnesIndexが高いことが分かった．ここで，ori(RR) は最大で

図 19 ChannelUtility の比較（マルチホップモデル）
Fig. 19 Channel utility comparison of each scheme.

図 18 FairnessIndex の比較（マルチホップモデル）
Fig. 18 FairnessIndex comparison of each scheme.

図 20 複合型モデル
Fig. 20 Complex model.

548

論文／無線アドホックネットワークにおけるフロー間の公平性の改善の改善を確認できるマルチホップモデル更に，リンク層及び MAC 層におけるフロー間の公平性の改善を総合的に確認できる複合型ネットワークモデルを対象に提案方式の有効性を確認できた．
本論文では，1 回のチャネルアクセスで送信するパケット数を固定値にしているが，今後はネットワーク
図 21 FairnessIndex の比較（複合型モデル）
Fig. 21 FairnessIndex comparison of each scheme.

の状態に応じて，変更可能な方式を検討する．更に，今回のシミュレーションでは，無線端末の移動を考えていないが，今後はアドホックネットワークにおいて

表 5 トータルスループット（複合型モデル）
Table 5 Total throughput (complex model).
ori(FIFO)
ori(RR)
proposed592.69 [kbit/s]
591.40 [kbit/s]
597.87 [kbit/s]

モビリティに関する評価実験を行う予定である．
謝辞

本研究を進めるにあたり，日ごろからごべん

たつ頂く幣所小花所長，小宮山所長，有益な助言を頂いた情報通信研究機構主任研究員シラジ様，幣研究室研究員ボルジン様並びに研究員各位に感謝する．また，
本研究は独立行政法人「情報通信研究機構」の研究委
託により実施したものである．
文
[1]

献

M. Frodigh, S. Parkvall, C. Roobol, P. Johansson,
and P. Larsson, “Future-generation wireless networks,” IEEE Pers. Commun. Mag., vol.8, no.5,
pp.10–17, Oct. 2001.

図 22 ChannelUtility の比較（複合型モデル）
Fig. 22 Channel utility comparison of each scheme.

[2]

H.Y. Hsieh and R. Sivakumar, “Performance comparison of cellular and multi-hop wireless networks:
A quantitative study,” Proc. ACM SIGMETRICS,

平性を著しく改善することが確認できた．また，表 5

pp.113–122, Boston, MA, USA, June 2001.
[3]

T. Miyamura,

T. Kirimoto,

K. Nakagawa,

P.

は，CBR のパケット送信間隔が 0.01 秒の場合におけ

Dhananjaya, M. Aoki, and N. Yamanaka, “A buﬀer

るトータルスループットの比較を示す．最後に，図 22

management mechanism for achieving approximately

は，CBR パケット送信間隔の変化に対するチャネル

fair bandwidth allocation in high-speed networks,”
IEICE Trans. Commun., vol.E85–B. no.8, pp.1434–

ユーティリティの比較を，FTP の結果を図の右端に併せて表す．図 22 から，提案方式におけるチャネル

1441, Aug. 2002.
[4]

networks,” Proc. IEEE ICC, pp.103–107, June 1986.
[5]

6. む す びpurpose ATM switch chip,” IEEE J. Sel. Areas Commun., vol.9, no.8, pp.1265–1279, Oct. 1991.
[6]

ﬁcations,” 1999.
[7]

cess protocols,” ACM SIG-METRICS 2000, pp.118–

く，ネットワーク全体のパフォーマンス及び，チャネ

119, Santa Clara, CA, June 2000.
[8]

H. Luo, S. Lu, and V. Bharghavan, “A new model
for packet scheduling in multihop wireless networks,”

方式の有効性を確認するため，NS ネットワークシミュ
レータによる性能評価を行った．シミュレーションは，

C.E. Koksal, H. Kassab, and H. Balakrishnan, “Ananalysis of short-term fairness in wireless media ac-

干の修正を加えるだけで，フロー間の公平性だけでな
ルユーティリティなど，様々な面で有効である．提案

ANSI/IEEE Std 802.11, “Wireless LAN medium access control (MAC) and physical layer (PHY) speci-

複数送信する，フロー間の公平性の改善方式を提案した．提案方式は，802.11MAC ベースの従来方式に若M. Katevenis, S. Stefanos, and C. Courcoubetis,“Weighted round-robin sell multiplexing in a general-

本研究では，無線アドホックネットワークにおいて，

1 回のチャネルアクセスで異なるフローのパケットを“Round robinscheduling for fair control in data communication

ユーティリティが最大で 2%ぐらいの改善ができることが確認できた．

E.L. Hahne and R.G. Gallager,

MOBICOM, pp.76–86, Aug. 2000.
[9]

J. Jangeun and M.L. Sichitiu, “Fairness and QoS in

MAC 層におけるフロー間の公平性の改善を確認でき

multihop wireless networks,” IEEE Vehicular Tech-

るシングルホップモデル，リンク層におけるフロー間

nology Conference, vol.5, 6–9, pp.2936–2940, Oct.

549

電子情報通信学会論文誌 2005/3 Vol. J88–B No. 3

張

2003.
[10]

I. Gruber, A. Baessler, and H. Li, “Fair WLAN

昭 58 中国北京航空航天大学卒．平 2 広
島大大学院博士課程了．平 3 郵政省通信

scheduling for ad hoc networks with access points,”
poster, MobiHoc’04, Tokyo, Japan, May 2004.
[11]

総合研究所（現（独）情報通信研究機構）

A. Woo and D.E. Culler, “A transmission control

入所．以来，統合的画像処理，ニューラル
ネットワーク研究に従事．その間，平 7〜

scheme for media access in sensor networks,” MobiCom’01, pp.221–235, Rome, Italy, July 2001.
[12]

V. Bharghavan, A. Demers, S. Shenker, and L.
Zhang, “MACAW: A media access protocol for wireless LANs,” SIGCOMM’94, pp.212–225, Sept. 1994.

[13]

IEEE 802.11 WG, Draft Supplement to Part 11:
Wireless Medium Access Control (MAC) and physical layer (PHY) speciﬁcations: Medium Access Control (MAC) Enhancements for Quality of Service(QoS), IEEE 802.11e/D2.0, Nov. 2001.

[14]

D. Vardalis, On the Eﬃciency and Fairness ofWired/Wireless Networks, Master Thesis, State University of New York at Stony Brook, 2001.

[15]

USB/LBNL/VINT Network Simulator ns (version2),
http://www.isi.edu/nsnam/ns[16]

S. Choi, J. del Prado, S. Shankar, and S. Mangold,“IEEE

802.11e

contention-based channel

access(EDCF) performance evaluation,” Proc. IEEE ICC
2003, pp.1151–1156, Anchoragae, AL, USA, May
2003.
[17]

K. Pentikousis, “TCP in wired-cum-wireless environments,” IEEE Commun. Surveys, vol.3, no.4, pp.2–
14, Fourth Quarter, 2000.

（平成 16 年 6 月 28 日受付，10 月 12 日再受付）

オユーンチメグ
（正員）

シャグダル

平 14 長岡技科大・工・電気・電子シス
テム卒．平 16 同大大学院修士課程了．同
年 ATR 適応コミュニケーション研究所に入所．適応的 QoS 制御方式の研究に従事．

中川健治 （正員）昭 55 東工大・理・数学卒．昭 60 同大大学院博士課程満期退学．昭 60NTT 研究所
入社．平 4 長岡技科大工学部助教授．待ち行列，ネットワーク特性評価，大偏差理論等の研究に従事．理博．IEEE，情報理論とその応用学会，日本数学会各会員．

550

兵 （正員）

8 米国テネシー大学神経・解剖学科博士研究員．平 12 ATR 適応コミュニケーション研究所に出向．現

在，適応的 QoS 制御方式，無線 TCP の研究に従事．主任研究員．工博．