MANET における TCP スループットを考慮したルーティングアルゴリズムの提案と評価
M2015SC019 山下瑞樹
指導教員

1

はじめに河野浩之

2.1

DSR

DSR は，IETF MANET WG で提案された経路制御
今まで MANET と呼ばれるアクセスポイントを必要としない機器間無線通信ネットワークを構築する研究は多 プロトコルの一つである．DSR はその中でもリアクティ
くなされている [3][4]．通常，MANET における経路選択 ブ型のルーティングプロトコルであり，経路要求がされ手法は最短経路を選択するようになっている．しかし，地 て初めて送信元ノードから宛先ノードまでの経路を確立
形や障害物による無線の減衰，ノードの密度，通信性能 する．通信に関しては，送信パケットのヘッダ内のオプによる電波品質の良し悪しによって，必ずしも最短経路 ション (Route Request) に送信元ノードから宛先ノードを選択することが最善の経路であるとはいえない．また， までの IP アドレスを指定するソースルーティング方式にノードによって様々な方向や速度で移動するため急激な 従う．各ノードはまわりのノードと通信するたびに，宛トポロジ変化を引き起こし，安定したネットワークを維 先ノードまでの経路を Route Cache として保持する．も持し続けることを困難にしている．これらの問題に対し し，Route Cache に宛先ノードまでの経路が存在していて MANET をクラスタリングすることによるフラッディ ない場合，送信元ノードは経路要求をブロードキャストングの効率化，トラフィック状況を基に評価値を設定する する．宛先ノードまでの経路が複数存在した場合は，ホッことによる最善な経路選択手法を提案した研究があるが， プ数の最も少ない経路を選択する．宛先ノードまたは宛どれも UDP 通信によるもので TCP 通信を考慮した研究 先ノードまでの経路をキャッシュしているノードが経路要は非常に少ない．現在モバイル利用者におけるトラフィッ 求に対する応答 (Route Reply) が返されなければ，Routeクの 94%が TCP 通信であることを考えると，MANET Cache からその経路を破棄する．ノード間のパケット転送の数に比例し，ヘッダ情報も多くなりオーバーヘッド上でおいても同様の利用が想定される．
本研究では，TCP スループットを考慮したメトリクス も増加するため，数十ノードを越える長距離通信は考慮を導入することにより，実世界で利用されると想定され されていない．
た環境下においてネットワークの安定化と純粋な TCP 通 2.2 クラスタポイントを用いたクラスタリング [4]
信のためのスループット向上を図る．また，MANET よ鳴海らは，高移動・高通信頻度環境化において各クラり利用が想定される状況から通信頻度とバッテリ消耗のスタにクラスタの中心点(クラスタポイント) と評価値を少ないリアクティブ型プロトコルである Dynamic Source設け，常に最適なClusterHead(CH) を選出することで，Routing(DSR) を採用する．我々は，これを本研究用に改良することにより目的を実現する．実験には，ネット 安定的なクラスタの形成と維持を実現させた．効率的なワークシミュレータ 3.25(ns-3) を用いて MANET におけ フラッディングを実現するためには，各 CH はクラスタるモビリティシナリオを構築し，提案するルーティング の中心位置にいることが望ましい．しかし，動的な環境アルゴリズムの追加モジュールを C++で実装し，性能を において CH が常にクラスタの中心に滞在することは困難であるため，評価式 (1) を用いて CH を動的に選出す評価する．
本稿は，全 5 章構成となっている．2 章では，MANET る．n はクラスタ数，vavg はノードの平均移動速度，d はにおける諸問題を解決するために提案されたクラスタリ クラスタポイントとの距離，C は定数である．
ングや経路選択アルゴリズムについて紹介する．3 章で√は，本稿で提案する MANET 環境下における TCP スルー
En = C × d + vavg log10 (vavg + 1)
(1)
プットを考慮したルーティングアルゴリズムについて説CH からのビーコンを受信したノードは，クラスタポ明する．4 章では，提案したルーティングアルゴリズムイントに対する評価値を算出し，評価値の最も低いノーを ns-3 により構築した環境化でシミュレートし．既存のルーティングアルゴリズムと比較・評価する．5 章では， ドを新たな CH に選出する．旧 CH は新 CH からビーコンを受信すると旧 CH が保持していたノードリストを新本研究の総括を述べる．
CH へ送信し Cluster Member(CM) となる．この一連の2 関連研究動作を定期的に実行することで高移動・高通信頻度環境
この章では，本研究で提案するアルゴリズムに用いる 下においても安定したクラスタの維持ができる．
ルーティング・プロトコルと関連する研究について説明
2.3 優先度メトリクスに基づくルーティングアルゴリズする．
ム [3]
浅沼らは，各ノード間のトラフィック量を考慮したルーティングアルゴリズムを提案したことにより，高移動型

ノードにおいて安定した通信の実現と動的に経路を入れ 送信元ノードから宛先ノードまでのパケット喪失率 P を替えることによりネットワーク全体のスループットの向 計算し，TCP スループットの推定値 T を算出する．
上を実現した．DSR をベースとしたクラスタベースルー
Padhye らによるモデルを以下に示す．
ティングは単一経路のみを使用するに対し，提案手法は
1√√(4)T ≈通常の経路 (プライマリ経路) の他に代替経路 (セカンダ3bP2)
RT T 2bP+Tmin(1,3)P(1+32P038リ経路) を 1 本以上用意する．経路を複数用意することで経路内に別の通信トラフィックが発生し，輻輳が生じた
式 (4) の Padhye らによるモデルは，経路上の平均遅延場合にも送信元ノードから宛先ノードまでの通信経路の RTT，1 つあたりの ACK によって確認できるパケット数
ホップ数，トラフィック量，すべての隣接ノードとのリン b，送信元ノードから宛先ノードまでのパケット喪失率 P，ク状態における平均値，バッテリ残量を総合的に判断し， タイムアウトの発生時間 T を計算し，TCP スループッ
0
プライマリ経路とセカンダリ経路を比較することで常に トの推定値 T を算出する．
最適な経路を選択することができるようになり，ネット以上のモデルを基に TCP スループットを算出した結ワーク全体の安定化とスループットの向上を図る．以下 果，Floyd らによるモデルと Padhye らによるモデルは以の評価式 (2) により優先度メトリクスを用いて評価値を 下の表 1，表 2 となった．なお，式 (4) のパラメータの設算出することができる．
定値は，通常の TCP に従って b を 2，T を 4RTT，セ0

グメントサイズを 1500byte としている．

W = ω1 ×3

1
11+ ω2 ×+ ω3 ×N
traf f ic
LLT(2)
1+ ω4 ×B

表 1 Floyd らによる TCP スループット算出モデル
喪失率 \ 遅延時間

0.01%
0.02%
0.03%

提案アルゴリズム

10ms

20ms

30ms

40ms

50ms

1837kbps
1300kbps
1061kbps

919kbps
650kbps
530kbps

612kbps
433kbps
354kbps459kbps325kbps
265kbps

367kbps260kbps
212kbps

この章では，本研究で提案するルーティングアルゴリズムについて述べる．

3.1

提案手法

表 2 Padhye らによる TCP スループット算出モデル
喪失率 \ 遅延時間

本研究は，動的なノードに対して有効的な手法であるクラスタリングを用いた DSR を拡張し，TCP スループットを考慮した複数のメトリックによる評価式を適用することで TCP 通信のための最適な経路を選択するルーティングアルゴリズムを提案する．一般的に TCP スループッ
トは，送信元ノードから宛先ノードまでの通信経路のホップ数，隣接ノードとの往復遅延時間，パケット損失率，経路上のトラフィック量，ノードの移動速度，電波品質などが影響を与える要素として考えられる．特に，遅延が少ないこと，パケット損失率が低いことが TCP スループットの増加に寄与する．そのため本研究では，これらのメトリックを用いることにより，効率的で安定的な TCP 通信とノードのバッテリ消費を制限し，大規模な MANET環境下においても通信動作の向上を図る．

0.01%
0.02%
0.03%

10ms

20ms

30ms40ms

50ms

1825kbps
1284kbps
1043kbps

913kbps
642kbps521kbps

608kbps
428kbps
348kbps451kbps
317kbps260kbps

358kbps
244kbps
202kbps

本研究で用いる TCP スループットを考慮した経路選択
は，複数ある経路の中から TCP スループットが高い経路を優先的に選択するルーティングアルゴリズムである．そのため，この経路選択においては精確な TCP スループッ
トを算出する必要はなく，あくまで複数ある経路の中でTCP スループットの優劣が判定できれば良い．TCP ス
ループットの指標として表 1，表 2 を比較した際，両モデルによる数値からグラフの線形が酷似していることがわかる．そのため，両モデルによる TCP スループットの推定の精確性も同等であることがわかる．また，Floyd らの研究は Padhye らの研究を参考にしている．その結果，本研究で用いる TCP スループット算出モデルは，計算が3.2 TCP スループット算出モデル
TCP スループットを算出するモデルを用いることで， 比較的簡単である Floyd らのモデルとした．

TCP スループットが最も高い経路を選択することが可能になる．TCP スループットを算出するモデルとして一般的に有名なものは，Mathis らが提案したモデルに改良を加えた Floyd らのモデル [1] と Padhye らが提案したモデル [2] が存在する．
Floyd らによるモデルを以下に示す．
√
1.5 23 × B
√
T ≤
(3)
RT T × P
式 (3) の Floyd らによるモデルは，TCP の最大セグメン
トサイズ B，経路上の最小遅延 RTT(Round Trip Time)，

3.3

RTT&RTPL 算出モジュール

Floyd らの式 (3) より TCP スループットの推定値を算出するためには，送信元ノードから宛先ノードまでの RTTと往復パケット喪失率 (RTPL1 ) が必要になる．特に，このメトリクスを取得するにあたって通信経路は，往路と復路ともに同一でなければならない．そのため，送信元ノードは宛先までの全ての経路を指定するソースルーティング方式である DSR を採用する．送信元ノードが TCPスループットの推定値の算出に必要な各種メトリクスを取得する手順を以下に説明し，図 1 に示す．
1 Round Trip Packet Loss ratio

(1) 各ノードは，起動したときから今までに転送したパケットからリンク毎にパケット喪失率を計算する．送信元ノードは宛先ノードに向けて通信を始めると，送信元ノードから宛先ノードまでの RTT と RTPL を要求するパケット (RTTPL2 要求) を一定間隔で送信する．
(2) 送信元ノードと宛先ノードの中間経路に存在するノードは，RTTPL 要求を受信すると各リンクとのパケッ
ト喪失率を RTTPL 要求に付加して，宛先ノードへ転送する．
(3) 宛先ノードが RTTPL 要求を受信したら各リンクのパケット喪失率から RTPL を計算し，RTTPL 応答を送信元ノードに送信する．
(4) 送信元ノードが RTTPL 応答を受信したら，RTTPL応答から RTPL を取得し，RTT は RTTPL 要求を送信してから RTTPL 応答を受信するまでにかかった時間を計算することで求める．
以上の手順により入手した RTT と RTPL を Floyd らの式 (3) に代入することで TCP スループットの推定値を算出する．

RTTPL 要求を Nn へ向けて送信し，中間ノードである
Ni が RTTPL 要求を受信した場合，Ni は Pi,i−1 と Pi,i+1を RTTPL 要求のパケットに格納し，次のノードであるNi+1 へ転送する．よって，宛先ノード Nn が RTTPL 要
求を受信したときパケットに含まれるパケット喪失率は全部で，P1,2 ，P2,3 ，...，Pn−1,n ，Pn,n−1 ，...，P3,2 ，P2,1 となる．
ちなみに，Nn は式 (5) から算出した RTPL を RTTPL 応答へ格納し，N1 へ送信する．

RT P L = 1 −送信元ノードは，RTTPL 要求を送信する際，そのパケットへタイムスタンプを付加する．宛先ノードは，RTTPL要求のタイムスタンプを RTTPL 応答に入れ送信元ノードに送信する．そして，送信元ノードが RTTPL 応答を受信した時刻と RTTPL 応答のタイムスタンプの差を RTTとする．

RTPL 算出手法
各ノードは隣接ノードとのリンク状態からパケット喪失率を測定する．N1 ，N2 ，...，Ni ，...，Nn−1 ，Nn 個のノードからなる経路において，Ni から Ni+1 へ向かうリンクのパケット喪失率を Pi,i+1 とすると，i 番目のノードである Ni は Ni から Ni−1 へのパケット喪失率 Pi,i−1 と Ni
から Ni+1 へのパケット喪失率 Pi,i+1 を管理する．N1 が
2 Round Trip Time and Packet Loss ratio(5)

ここで，もし送信元ノードが RTTPL 要求を送信したにも関わらず，宛先ノードから RTTPL 応答が返ってこない場合，RTTPL 要求もしくは RTTPL 応答が途中の経路上で喪失したことになる．その場合は，改めて送信元ノードが RTTPL 要求を送信し，RTPL を算出する．

3.4

TCP スループットをメトリクスに加えた経路選択機構

後述する 3.3，3.4 節で測定したメトリクスを用いて送信元ノードは最終的に経路を決定する優先度 W を算出する．以下に優先度 W を算出する式 (6) を示す．

11+ ω2 ×+ ω3 × B
NT(6)

ここで，N は送信元ノードから宛先ノードまでのホップ数，T は送信元ノードから宛先ノードまでの TCP ス
ループット，B は宛先ノードまでの経路上に存在する各CH のバッテリ残量の平均を表す．また，ω1 ，
ω2 ，
ω3 により重み付けがされる．本研究において，最もネットワー
クのスループットに左右されるメトリクスは TCP スループットである．続いてホップ数，バッテリ残量の順に重み付けをしていく．

拡張した DSR によるシミュレーション

4
RTT 算出手法(1 − Pi,i+1 )(1 − Pi+1,i )i=1

W = ω1 ×

図 1 TCP スループット算出手順例

n−1∏

この章では, 本研究で提案したルーティングアルゴリズ
ムのシミュレーションの概要について述べる.

4.1

シミュレーション環境の構築

提案手法の有用性を評価するために使用したツールと実装するプログラムについて説明する．DSR に C++で新たに記述した，追加モジュールを ns-3 に実装する．
追加モジュール
本研究で DSR に追加または拡張するモジュールについては以下のとおりである.

• 実験用シナリオ• 優先度を基にした経路選択モジュール• RTTPL 要求・転送・応答モジュール• TCP スループット算出モジュール

シミュレーション環境

130

シミュレーションで使用するパラメータを表 3 に示す．
Throughputs [kbps]

125

表 3 実験シナリオの設定パラメータシミュレート時間
100s
ノード数
25,50,75,100
ノード速度0〜10m/s
通信エリア
1000*1000m
各ノードの帯域幅
1Mbps
通信プロトコルTCP
移動モデル
Random Way Point
MAC プロトコル
IEEE802.11b

1201151101051009590DSR average
Proposal average85

25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
number of nodes

図 3 ノード数における平均 TCP スループット
シミュレーションでは, ノードを分散させるためシミュレーション開始 40 秒後から通信を開始する．

4.2

シミュレーション結果

表 3 で示したパラメータ環境で従来の DSR と本研究で提案する DSR をシミュレートする．以下の図 2 に，時間経過と TCP スループットの変化の関係性を示す．
140

Throughputs [kbps]

12010080604020

DSR
Proposal
DSR average
Proposal average

0-20010203040 50 60
Times [s]708090

図 2 時間経過における TCP スループット (ノード数:25)
以下の図 3 に，ノード数と TCP スループットの変化の関係性を示す．

4.3

シミュレーション結果の考察に 29%向上しており，ノード数が増加した場合においても，安定的な TCP スループットを維持できていることがわかる．

5

おわりにMANET における実験は数多くなされてきた．しかし，どれも UDP 通信によるもので TCP 通信を考慮した研究は非常に少ない．そのため本研究は,TCP 通信のための最適な経路を選択するルーティングアルゴリズムを提案した. ns-3 上に TCP 通信のための拡張した DSR を実装し,従来の DSR と比較した. 結果として, 提案したルーティ
ングアルゴリズムは, 通信の混在した MANET 環境においても安定した TCP スループットを維持することができた. 今後の課題としては, 実機を用いて実際に MANETを構築し評価をする. IEEE802.11g を用いた場合のノード間距離が 45m 以上離れると転送率が著しく悪化する問
題を解消することで, 同じシミュレーションシナリオにおいても安定して, より高い TCP スループットを実現できると考えられる.

参考文献[1] Floyd, S. and Fall, K.: Promoting the use of end-toend congestion control in the Internet, IEEE/ACM
Transactions on Networking, Vol. 7, No. 4, p. 458(1999).

図 2 の結果より，従来の DSR は通信開始から通信終 [2] Padhye, J., Firoiu, V., Towsley, D. and kurose, J.:
Modeling TCP Throughput: A Simple Model and了まで最大 28%TCP スループットが減少した. 一方, 本Its Empirical alidation, SIGCOMM Comput. Com研究で提案する DSR は, 通信開始から通信終了まで最大mun. Rev., Vol. 28, No. 4 (1998).
11%TCP スループットが減少した. また, 図 2 から提案する DSR と従来の DSR を比較して, 提案する DSR の方は [3] 浅沼佑紀，中村嘉隆， 高橋修：MANET におけるト
TCP スループットの乱れが小さいことがわかる. これは，ラフィック状況を考慮したクラスタベースルーティン
通信が混在したネットワークにおいても TCP スループッ
グアルゴリズムの提案，第 76 回全国大会講演論文集，トを考慮した経路選択がうまく機能しており，より安定Vol. 2014, No. 1, pp. 269–270 (2014).
的な経路選択ができていると考えられる．
[4] 鳴海寛之， 白石陽， 高橋修：MANET におけるまた，図 3 の結果より，従来の DSR はノード数の増加
高信頼クラスタベースルーティングアルゴリズムのに比例して TCP スループットが大きく減少している．特提案と実装・評価，研究報告システム LSI 設計技術，に，ノード数が 100 台のときの TCP スループットは，従Vol. 2010, No. 15, pp. 1–8 (2010).
来の DSR が 87kbps に対して提案する DSR は 123kbps