アドホック通信における通信機会公平性に関する研究
M2010MM033 岡田千明
指導教員：奥村康行

はじめに（Short Inter Frame Spacing） 時間後に送信する. このフレームを CTS（Clear to Send） といい， RTS と同
近年，多様な展開を広げている無線通信において，基様に，CTS を受信した周辺端末も NAV 時間通信を控え地局等の制御局を必要とせず，端末のみでネットワークる. そして CTS を受信した端末 A は SIFS 時間後に本を構成することが出来るアドホックネットワークが特にデータ送信を開始する. 端末 C が端末 A からのデータフ
注目されており，様々な研究がなされている.
レームを受信し終えると，SIFS 時間後に受信の完了を周アドホック通信はその特徴から，制御局が致命的な損囲に知らせるフレームを送信する. このフレームを ACK傷を被った場合において非常に有用であると言える. し（ACKnowledgment） という. ACK を受信した周辺端末
かし現在用いられている IEEE802.11 における MAC
は NAV を解除し，再度キャリアセンスを行い，バックオ(Medium Access Control） プロトコルは，通信を行う端フ時間を設定する. 以上が現在の通信手順である.[1]末の選定方法にランダムバックオフというランダムな待この方法では端末の選定方法がランダムであるため, 搬
ち時間を使用し，その待ち時間が少ない端末を通信端末送波同士の衝突の頻発するような環境を考慮していないことして選定，といったランダム性の強い方法が用いられ，とや端末の通信機会が公平に与えられない問題点がある.
端末間における通信機会の公平性において問題がある. さらには通信に搬送波を用いるので, 多数の端末が密集する高密度な環境である場合，搬送波同士の衝突が頻発し通信効率低下の問題点も存在する.
本研究ではそれぞれ通信機会の少ない端末に対し短い待ち時間を，多い端末に対し長い待ち時間を与えるようにランダムバックオフの設定を変更する. さらに短い待ち時間を与える端末を減らすことで一定時間内に搬送波を送信する端末数を減らし，衝突確率を下げ通信効率の低
図 1 通常のアドホック通信手順下を防ぐ. そうした低密度環境だけでなく高密度環境にも対応できる端末選定方法を提案する. その上で各端末
この問題に対し，先行研究 [2] のように RTS 送信回数毎の通信機会の公平性の向上や受信側で受信する UDP， による送信端末の階層化を用いる方法など，様々な研究
TCP 各スループット量を計測し，その均等化も図る.
が行われているが TCP，UDP 等のトラヒック種別は考慮していない方法なので，各スループット量に偏りが生
2 現在のアドホック通信手順と問題点じることや，非常に高密度な環境のみに対応しており，低始めに IEEE802.11 で用いられている RTS/CTS 方式 密度環境に即さないという問題点がある. 本研究ではこについて図 1 を用いて説明する. この図では端末 A，B れらの問題も解消するアルゴリズムを提案する.
が受信端末である端末 C に通信要求がある. 端末 A と3 提案するアルゴリズム
端末 B は端末 C が通信中かを判断するため，搬送波の検本研究ではランダムバックオフシステムに変更を加え出を試みるキャリアセンスを行う. 一定時間搬送波が検出されない場合，各端末はチャネルを利用可能と判断す ることで各均等化を目指す. これらを低密度環境，高密る. これにかかる時間を DIFS （Distributed Inter Frame 度環境の 2 つの状況を想定するため，それぞれの環境にSpacing） といい，DIFS 後は各端末はランダムな待ち時 適した 2 つのアルゴリズムを用意した.
間を設け，その間キャリアセンスを続ける. これをバック 3.1 低密度環境用アルゴリズム
オフという. ランダムな待ち時間を設定する事により，通まず，低密度環境用アルゴリズムを説明する. 本研究で信要求を持っている端末間のフレームの衝突を低減することが出来る. 図１ の例では端末 A が端末 B より短いバッ は通常のバックオフ時間に加え, 非適合端末バックオフ，クオフ値を設定したため，端末 A が先にバックオフを終 Ex バックオフという 2 つのバックオフを追加する. この了する. 次に端末 A は，通信の開始を周囲の端末に伝え アルゴリズムをアルゴリズム A とする.
るフレームを送信する. このフレームを RTS （Request 3.1.1 低密度環境用バックオフ設定to Send） といい， この時端末 B と端末 C は端末 A のまず各端末の通信機会を公平にするために，Ex バック
RTS を受信する. バックオフ中の端末 B は，端末 A のオフを設定する. Ex バックオフは受信端末と通信を行っ通信開始を知り，一定時間自身の通信を控える. この時た端末全てに通常のバックオフに付加される. 図 2 のよ間を NAV （Network Allocation Vector ） という. 一
うに Ex バックオフの付加された端末は他の端末より長方，端末 A の宛先である端末 C は，これから受信するこい待ち時間になるため他の端末全てに Ex バックオフがとを周囲に伝えるフレームを非常に短い時間である SIFS付加されない限り通信機会は与えられない.

1

そして TCP,UDP 各スループット量を調整するために非適合端末バックオフを設定する. このバックオフは図 2のように通常のものより長く，Ex バックオフより短いものを設定する. 図 2 において受信端末は TCP スループッ
ト量が UDP より少ないため、ACK で TCP 送信の要求している. その場合 TCP 端末は通常のバックオフを，UDP端末は非適合バックオフを設定する. こうしてプロトコルのスループット量を調整する. ただし非適合バックオフを設定している端末が連続で選ばれた場合，受信端末は要求する端末がないと判断し，非適合端末にも適合バックオフを設定する. こうしてなるべく無駄な時間を省く.

更を行う. このアルゴリズムをアルゴリズム B とし，図4，表 1 を用いて説明する.
アルゴリズム B はアルゴリズム A より通常のバックオフを設定する端末数を減らすことにより，その時間内において発生する搬送波の数が減り衝突確率を下げ通信効率の低下を防ぐ. アルゴリズム A においては，TCP，UDPのどちらかを要求プロトコルとし，そのプロトコルを持つ端末に通常のバックオフ時間を設定している. これでも一定時間に発生する搬送波数は通常のアドホック通信より減るが，それでも効果は薄い. そこでアルゴリズム
B では表 1 に示すように低密度用の条件に加え各送信端末の送信データ量も条件も加える.
表 1 各アルゴリズムのバックオフ条件
バックオフ条件 低密度用 高密度用
プロトコル
◯◯
通信回数
◯◯
送信データ量◯受信端末は送信端末からの TCP，UDP それぞれの純粋な送信データ量も計測する. そして図 4 のように一定時間内に受信端末が受信した TCP，UDP の各データ量の3.1.2 Ex バックオフの削除
差を取り現在どのプロトコルのどれだけのデータ量を受端末は通信を行うと Ex バックオフを付加する. その場 信端末が多く受信しているのかを割り出す. そして ACK
合最終的に全ての端末に対し Ex バックオフが付加され， にこの情報を付加して送信し， 送信端末は自身のプロト結果余分な待ち時間が発生し通信効率が低下してしまう. コルと送信予定データ量を比較する. 送信端末にはあらそれを防ぐため Ex バックオフを削除する必要がある. 削 かじめデータ量を比較するための閾値を設定し，その条件に基づいて送信データ量と要求データ量を比べ要求を除を行うタイミングについて図 3 を用いて説明する.
まず受信端末は図 3 のように通信終了の ACK を周囲 満たしていた場合，通常のバックオフ時間を与える. 条に送信した瞬間から一番早い RTS を受信するまでの時間 件を厳しくすることでそれを満たす端末が減りその時間を計測する. 計測した結果一番早い RTS が Ex バックオ 内の衝突確率が下がり通信効率の低下を防ぐ. ただしこ
フに状態である時, 全ての端末が１回ずつ通信を行ったと のアルゴリズムは TCP，UDP 各データ量の差分を取る判断する. そしてその通信終了後の ACK で今通信を行っ ため全体的に送信データ量の少ない端末がやや優先された端末以外の端末に対し, Ex バックオフを削除するよう てしまう特徴を持つが，最終的には全ての端末へ通信機に指示する. 図 3 において，端末 A だけが Ex バックオ 会を与えれるので問題無いと思われる.
図 2 アルゴリズム A

フにおいて通信を行ったので端末 A だけは削除をしない.

図 3 Ex バックオフの削除図 4 アルゴリズム B

3.2

高密度環境用アルゴリズム

上記のアルゴリズムは搬送波同士の衝突がほぼ発生し 3.2.1 アルゴリズム B における Ex バックオフ
アルゴリズム B における Ex バックオフの説明を図 5 をない低密度な環境においては有用であるが，搬送波衝突対してはそこまで高い効果を持っていないので，高密度 用いて説明する. アルゴリズム B においても Ex バック環境においては有用でないと思われる. よって受信端末 オフは使用するが，最終的に全ての端末に Ex バックオフが RTS 受信するまでに一定以上の時間を計測した場合， が付加された場合そこで衝突が生じてしまう. よって図
搬送波衝突が頻発していると判断し，アルゴリズムの変 5 の適合端末のように Ex バックオフの付加されている端末においても条件を満たす端末に対しては Ex バックオフの中でも短い時間，適合 Ex バックオフを与え，それ以外には長い待ち時間である非適合 Ex バックオフを与える，といったように 2 つの Ex バックオフを使用する. ただし非適合バックオフの最大待ち時間よりは長い. そうして衝突確率を低下させる. Ex バックオフの削除方法はアルゴリズム A と同様である

図 7 低密度 (a) におけるスループット比

図 5 低密度におけるスループット

4実験

図 8 は受信端末に送信された合計スループット量を示す. 図を見ると提案方法は非適合バックオフと Ex バックオフの通常より長い待ち時間を発生から，端末選定で既存方法より余分な待ち時間がかかる. 結果スループットが 5〜10Kbps 程下がり，10 ％程度の通信効率低下が見られた.

TCP，UDP 各送信端末とそれらを受信する受信端末が存在している環境を想定し実験を行う. 低密度環境では(a) TCP30 台，UDP20 台，受信端末１台の計 51 台の環境，(b) TCP5 台，UDP45 台の通信の偏った環境で，600秒の実験を行う. 高密度環境では TCP500 台，UDP500台，受信端末 1 台の計 1001 台の環境で 1000 秒の実験を行う. 低密度高密度共に全ての端末は 1 ホップ範囲内に存在しており遅延や隠れ端末等はないものとする. これらの環境下で提案方式を用いて様々なパラメータを [1] のIEEE802.11a の既存方法と比較していく.
4.1

低密度 (a) 実験結果

図 6 は各端末の通信回数を示している. 実線が提案方法で，点線が既存方法である. 既存方法では全ての端末に対し 0 回から 6 回までの通信機会が与えられており，公平でないといえるが，提案方法では全ての端末が 2，3 回の通信機会であり通信機会は公平になっているといえる.

図 8 低密度 (a) におけるスループット

4.2

低密度 (b) 実験結果

UDP45 台，TCP5 台という通信内容が大きく偏った環境 (b) での実験結果を示す. 図 9 は RTS を送った最速の時間である. 提案方法では１部において，非適合バックオフ，Ex バックオフが選ばれ既存方法より待ち時間が大きくなってしまっている部分あるのがわかる.

図 6 低密度 (a) における通信機会
図 7 は TCP，UDP のスループット比を示している. ス
ループット計測は受信端末で行い,20 秒毎にスループット比=((UDP スループット量)/(TCP スループット量)) を計算した. 既存方法は基本的に UDP スループット量が高く均等がとれていないのに対し，提案方法では 1 に収束する動きを見せており，均等にできているのがわかる.

図 9 低密度 (b) での最短バックオフ時間
図 10 は合計スループット量を示す. 非常に通信が偏っているので，通信開始直後の提案方法のスループット量が小さくなっている. これは TCP 端末が優先して通信しいるからである. その後は UDP 端末だけが通信を行う状況になり，通信効率が急激に上がっている. 所々通信効率の下がっている部分は TCP が連続で選ばれている箇所と考えられる. この様に非適合端末の連続選定が多発するのでスループット量の均等性は図れない. 非適合端末が連続で選ばれる場合においては非適合端末にも一番短い通常のバックオフを与えなるべく無駄な待ち時間を減らしてはいるが，それでも既存方法より無駄な待ち時間が長いため結果約 5Kbps 程下がり，3〜4 ％程度の通信効率低下となった.

図 12 高密度におけるスループット

5

図 10 低密度 (b) でのスループット

4.3

高密度実験結果

図 11 は TCP，UDP のスループット比を表している.
スループット比は低密度と同じ計算方法であり 20 秒毎に算出した. 既存方法は基本的に UDP スループットが高く，均等性が取れていないが，提案方法は１に収束しているので，低密度同様に TCP，UDP 各スループット量の均等化が出来ていることがわかる.

まとめと課題低密度 (a) では，通信機会，スループット比の均等性を確認できた. しかしわずかな合計スループット量の低下が起きてしまった. できる限り無駄な待ち時間を省くように設定したが，それでも既存方法より長い待ち時間が発生するのでその分通信効率の低下が示されてしまった.
低密度 (b) では，既存方法より提案方法のバックオフが所々大きくなる部分が存在した. しかし合計スループット量は低密度 (a) と同等程度の低下で収めることが出来た.
そして高密度な環境では，通信機会，スループット比は低密度と同様に均等性は確保できた. そして合計スループット量においても既存方法を上回り，高密度環境においての提案方法の有用性を示せた.
今後の課題として，今回は隠れ端末やその他物理的障害による通信障害を考慮しなかったが，これらを考慮すると受信端末に RTS が届かないことや，予期せぬ RTS 受信による通信自粛等が発生し，通信が行えず通信機会の不公平が発生すると考えられる. こうした端末に対し優先的に通信機会を与えるように変更する必要を加え，全ての端末に通信機会の均等性の維持が今後の課題である.
改善点を考慮しつつこの 2 つを状況に合わせ低密度用高密度用と切り替えて使うことで様々な環境に即したアルゴリズムになると思われる.

参考文献

図 11 高密度におけるスループット比[1] IEEE STANDARD， 802.11a-1999 - IEEE Standard for Telecommunications and Information Exchange Between Systems - LAN/MAN Specific Requirements - Part 11: Wireless Medium Access Control (MAC) and physical layer (PHY) specifications:High Speed Physical Layer in the 5 GHz band，IEEE，1999.

[2] 田中塁，神谷幸宏，梅林健太，鈴木康夫， 高トラフィッ
図 12 は受信端末に送信された合計スループット量を示
ク環境下における無線アドホックネットワークの通信す. 低密度実験では既存方法が提案方法を上回ったが，高機会公平性改善手法の提案， 信学技報 RCS2009-160，
密度環境においては提案方法が高い通信効率を示していpp159-164，2009.
るのがわかる. 低密度実験と同じく Ex バックオフや非適合バックオフに導入による待ち時間の増加は存在するが， [3] 銭飛， NS2 ネットワークシミュレーション， 森北出版，2006.
提案方法を用いることにより既存方法より搬送波同士の衝突回数が軽減され，結果既存方法に比べ 20Kbps 程高 [4] C-K.Toh， アドホックモバイルワイヤレスネットワー
ク， 共立出版，2003.
く，20 ％程度上回る通信効率を出すことができた.