「マルチメディア，分散，協調とモバイル(DICOMO2007)シンポジウム」 平成19年7月

車車間アドホックルーティングプロトコル GVGridの実装と評価
濱山田口淳
弘司†
純†

孫楠

本為真華†
二†

近年，固定基地局を用いない車車間マルチホップ通信技術が注目を集めており，我々の研究グループにおいても，車車間マルチホップ通信における位置情報ルーティングプロトコル GVGrid を提案している．GVGrid は車両の移動情報を利用し，生存時間の長い経路を生成する．本研究では，GVGridにより構築される経路の品質評価を目的とし，AODV の実装である AODV-UU を用いて GVGridのプロトタイプ実装を行った．ノード PC からなる小規模テストベッドを構築した上で，実マップにおける車両の移動を想定して作成したリンク切断シナリオをテストベッド上で再現し，GVGrid 実装
および AODV-UU により構築された経路上に ICMP パケットを連続送出することで，スループットの比較実験を行った．その結果，GVGrid はより高いスループットを達成でき，かつプロトコルの制御パケット数が少ないことを確認した．

Imprementation of VANET Routing Protocol GVGrid
and Its Evaluation
Junji Hamada,† Weihua Sun,† Hirozumi Yamaguchi†
and Shinji Kusumoto†In recent days, vehicular ad hoc network communication technology which does not requireﬁxed infrastructure has had much attention. Several routing protocols for vehicular ad hocnetworks (VANETs) have been designed so far, and we have also proposed GVGrid, a positionbased routing protocol for vehicular ad hoc networks. In this paper, we have impremented
the function of GVGrid. Using a scenario which consisted of vehicles’ movement on a realmap, we have evaluated throughput of ICMP packets which were successively transmitted by
the source. The results have shown that GVGrid could achieve more stable communicationand less control messeges than AODV.

ついては文献1),2) を参照されたい．しかし，GVGrid

1. ま え が きにより構築された経路が，通常構築される最短経路な

我々の研究グループでは，車車間ルーティングプロ
トコル GVGrid を提案している．GVGrid は車両の位どと比較しデータの遅延や損失がどの程度軽減されるかについてはまだわかっていない．

置，進行方向，道路地図を用い，2 地点間の通信経路

本研究では，GVGrid の機能の実装を行い，テストをオンデマンドに構築し，維持する位置情報ルーティ

ベッド上で AODV により構築された経路とのスルーングプロトコルである．領域をグリッド状に分割し，プット比較実験を行ったため，それについて述べる．具なるべく主要道路に存在し，同一道路上で同じ進行方

体的には，無線 LAN を備えたノート PC10 台程度の向である車両を優先的に中継車両として選択した経路

小規模テストベッドを構築し，実マップにおける車両のを発見することで，生存時間の長い経路を実現する．

移動を想定して作成したリンク切断シナリオを実現す

また，一度構築した経路に対応する道路を記憶しておるようにした．そのもとで，GVGrid 実装及び AODV

き，経路が切断した場合は，残存する経路を利用しな実装により構築された経路上にそれぞれ ICMP パケッ

がら，もとの道路上に経路を高速に復元する．詳細にトを送出し，そのスループットの比較評価を行った．

† 大阪大学大学院情報科学研究科
Graduate School of Information Science and Technology，Osaka University

その結果，GVGrid はより高いスループットを達成でき，かつプロトコルの制御パケット数が少ないことを確認した．

― 540 ―

リッドが道路経路グリッドに含まれる場合は，RRPR

2. GVGrid の実装（Route RePaiR，以下 RRPR）メッセージの作成を一般に，テストベッドでの性能評価試験では，テス行う．なお，GVGrid の RRPR メッセージと AODV-

トベッドを構成するノード (PC) の台数により，試験

UU の RREQ メッセージのフォーマットは同一であ内容が大きく制限される．本研究では主に，GVGrid

る．GVGrid では，RRPR メッセージの作成後，自身および AODV により構築された経路が，ノード移動のグリッドの前方グリッドから代替ノードを選択し，に伴いどのように維持されるか，またその維持過程が自身が記録しているグリッド列を含む RRPR メッセー

通信性能にどのような影響を与えるかについての試験ジを代替ノードに送信するが，本実装では RRPR メッを行う．したがって，GVGrid については，その経路セージをシナリオによって指定されたノードへ送信す構築プロセスや維持プロセスを直接実行するかわりに，るようにしている．

シミュレーション等で得られた情報をもとに，指定されたノード上に強制的に経路を構築・維持するように経路維持メッセージ受信時の処理

AODV-UU では，RREQ メッセージを受信したノードは，保持しているルーティングテーブルを検した．以下ではこれらについて述べる．

GVGrid の経路構築および維持プロセスの実装は，
3)査し，目的地への経路エントリを保持していない場合

AODV-UU の実装コードをもとに行った．AODVUU は，スウェーデンの Uppsala University で開発されている AODV プロトコルの実装である．
2.1 経路探索プロセスの実装
GVGrid の経路構築プロセスは，AODV-UU の経は，RREQ メッセージをブロードキャストで転送す路探索プロセスを改造し，外部より指定されたノード(1)る．また自身のルーティングテーブル内に目的地への経路エントリを保持している場合は，このノードは切断した通信経路の残存ノードであり，この場合は以下のいずれかの処理を行う．
目的地への経路が有効であり，経路エントリのを RREQ メッセージの受信先として選択するように目的地シーケンスナンバーが受信した RREQしている．これにより，テストベッドにおいて，予定メッセージ内のシーケンスナンバーより大きいするノードに経路を構築できるようにしている．

か等しい場合は，シーケンス番号が大きいほど2.2 経路維持プロセスの実装最新の経路であると考えられることから，このGVGrid の経路維持プロセスは，(i) 経路の切断を検知したノードが行う，不要なリンクの強制切断処理，(ii) 経路の切断を検知したノードが経路の修復を開始する時に行う，経路維持メッセージの作成および送信処理，(iii) 経路維持メッセージの受信時の処理，および (iv) 経路の修復に関係するノードが行う，ルーノードから目的地までの経路においては，経路エントリ内の経路が RREQ メッセージ内の経路よりも新しい経路であることがわかる．したがって，RREP メッセージを作成し，経路切断を検知したノードへ送信する．

(2)

目的地への経路が有効であり，経路エントリのティングテーブル更新の処理，からなる．以下では，目的地シーケンスナンバーが受信した RREQ

AODV-UU の実装コードをもとにした，GVGrid の上記の四つの処理からなる経路維持プロセスの実装法について述べる．

メッセージ内のシーケンスナンバーより小さい
場合は，シーケンス番号が大きいほど新しい経路であると考えられるため，このノードから目不要なリンクの強制切断処理

的地までの経路については，RREQ メッセー

GVGrid では，経路の切断を検知したノードは，自ジ内の経路が経路エントリ内の経路より新しい身が存在するグリッドが道路経路グリッド列に含まれ経路であることがわかる．したがって，最新のるか否かを判定し，存在しない場合は，自身と接続し経路を作成するために RREQ メッセージを作成し，ブロードキャストで転送する．ているノードとのリンクを強制切断し，通信を終了する．本実装では，経路の切断が発生した場合，経路の(3)目的地への経路が無効であるとき，目的地への新しい経路を作成するために，RREQ メッセー

切断を検知したノードが強制切断を行うかどうかを外ジをブロードキャスト送信する．

部のシナリオファイルに基づき決定し，実行する．

これに対し，GVGrid は RRPR メッセージ転送時

経路維持メッセージ作成および送信処理

AODV-UU では，経路の切断を検知したノードは，RREQ メッセージを作成してブロードキャスト送信する．これに対し，GVGrid では，自身が存在するグには，シーケンス番号における処理は行わず，目的地方向へのノードを選択してユニキャストで送信する手法をとっているため，AODV-UU を次のように修正― 541 ―することで，それを実現した．まず，RRPR メッセー

ティングテーブルの更新処理は，AODV-UU におけジを受信したノードは，自身のルーティングテーブル

る RREQ メッセージ受信時と RREP メッセージ受信を検査し，目的地への経路エントリを保持していない時のルーティングテーブルの更新処理と同じである．

場合は，RRPR メッセージをシナリオによって指定されたノードへ転送する．また自身のルーティングテー

3. テストベッドによる経路品質の評価実験

ブル内に目的地への経路を保持している場合は，切断GVGrid と AODV による経路品質を評価するためした通信経路の残存ノードであるため，以下のいずれのテストベッドを構築した．テストベッドは，ノードかの処理を行う．の移動性とマルチホップ通信を実験室レベルで実現す

(1)

(2)

目的地への経路が有効である場合は，RREPるために，iptables が持つ MAC 層でのフィルタ機能

メッセージを作成し，経路切断を検知したノーを使用し，任意のトポロジを擬似的に生成できるよドへ送信する．

うにした．これについては 3.2 節で述べる．このテス

目的地への経路が無効である場合は，目的地へトベッドを用い，実際の車両の移動状況をもとに，作の新たな経路を作成するために，RRPR メッ

成した経路構築・維持シナリオにおける GVGrid とセージをシナリオによって指定されたノードへAODV のスループットを測定した．

転送する．

3.1 既存のテストベッドとの位置づけ
MANET の テ ス ト ベッド と し て ，MobiEmu4) ，APE5) ，ORBIT6) などが知られているが，いずれも汎用のハードウェアを用いた実現が困難である，ある
いは汎用の実行環境を提供していない, などの理由か

ルーティングテーブル更新処理

AODV-UU では，経路維持プロセスにおけるルーティングテーブルの更新は，RREQ メッセージ受信時と RREP メッセージ受信時において行われる．RREQ
メッセージを受信したノードは，自身のルーティングら，本研究では汎用の Linux PC のみを用いて容易にテーブルを検査し，目的地への経路エントリを保持実現可能なテストベッドを独自に構築した．

していない場合は，送信元の情報とその RREQ メッ

評価用のテストベッドは，IEEE802.11b を備えたセージを送信した隣接ノードのアドレスを送信元へのノート PC 10 台からなる．各ノート PC に搭載して次ホップとしてルーティングテーブルに記録し，送信いる OS は，Vine Linux 3.2 である．

元方向の経路を確立する．RREP メッセージを受信しセージを送信した隣接ノードのアドレスを目的地方向

3.2 MAC 層におけるパケットフィルタ機能
トポロジの実現には，iptables7) が備える MAC 層でのフィルタ機能を利用している．これは，指定したMAC アドレスから送信されたフレームを全て破棄する機能である．この機能を利用することにより，実験への次ホップとしてルーティングテーブルに記録し，環境において，任意の 2 ノードが直接通信可能な完全目的地方向の経路を確立する．また目的地への経路エグラフトポロジの状態から任意のトポロジを作成するントリが存在し，かつ経路が無効状態である場合は，ことが可能である．

たノードは，ルーティングテーブルに目的地への経路エントリが存在するか検査し，目的地への経路エントリが存在しない場合は，目的地の情報と RREP メッ

経路を有効状態にするなどして経路エントリを更新す

図 1 を用いて，MAC 層でのフィルタ機能を利用しる．したがって，AODV-UU では双方向の経路の実たトポロジ作成の様子を説明する．まず，図 1(a) は，現に独立した二つの経路エントリを使用している．

テストベッドを構成する全ノードが，互いの無線範囲

これに対し，GVGrid では，RREP メッセージ受信に存在するよう，それらのノードを配置する．この状

時に，RREP メッセージ内に記録されているノード

態では，あるノードがブロードキャストを行うと無線ID 列から，一つの経路エントリへ自身の前方および後範囲内に存在する全ノードにパケットが届く．このも方のノードの情報を記録することにより，一つの経路とで，例えば，図 1(c) のようなトポロジを作成したエントリで双方向の経路を実現しているが，本実装でい場合，ノード A からのパケットをノード B 以外がは，AODV のルーティングテーブルと同様に一つの経破棄するようにすればよい．よってノード B 以外の各路エントリで片方向の経路を実現している．GVGrid

ノードに，ノード A からのパケットを破棄するルールの経路維持プロセスにおけるルーティングテーブルのを iptables を用いて実行させる．図 1(b) は，各ノー更新は，RRPR メッセージ受信時と RREP メッセードが図 1(c) のトポロジ作成に不必要な経路をフィル

ジ受信時において行われる．RRPR メッセージを受信タした様子である．これにより，任意のトポロジを擬した場合と RREP メッセージを受信した場合のルー似的に実現できる．なお，これはすべてのノードが相― 542 ―開始するノードは，経路が通過する道路として記憶しAていた道路における隣接グリッドに存在するノードを1 つ選択する．この際，可能であれば切断された経路の断片を保持するノードを発見し接続することで，残A

B

BHC

GHC

G

存した経路を積極的に利用し，経路復元を高速に行う．
DF

D

そのため，直線の道路上におけるノード間距離の増大

FEによる切断や交差する 2 道路上の車両間リンク切断でEは，初期の道路経路グリッド上に通信経路を再構築す(a) 物理トポロジるため，修復前後の経路が大きく変わる可能性は低い．

(b) フィルタ後の論理トポロジ

これらの状況をすべて試験できるように，GVGrid のシナリオを作成した．GVGrid の経路の変遷の様子を
図 2 に示す．一方で AODV では，切断リンクの上流Hノードが RREQ メッセージをブロードキャストしてそのノードから宛先ノードまでの新たな経路を発見Gする．したがって，修復後は比較的最短経路に近い経A

BC路に戻される．AODV の経路の変遷の様子を図 3 にE示す．
これらの車両の移動シナリオと経路切断状況は，3F分間のシナリオである．図 2(a) は GVGrid の初期経D路，図 3(a) は AODV の初期経路である．
(c) 作成したいトポロジ例
図1

図 2(b) はノード C，D 間のリンクがノード間距離の増大により，図 3(b) はノード D，E 間のリンクがMAC 層のフィルタ機能を利用した論理トポロジ生成例

障害物により切断した状態を表している．GVGrid の場合，リンク切断を検知したノード C が隣接グリッ互に無線範囲にあるため，実際より多いフレームコンドに存在するノード F を選択して経路修復を開始し，テンションが発生する可能性が高いが，本研究で行う残存経路と接続する (図 2(b))．AODV では，リンク実験ではそれほど大量のフレームを発生しない，クロ切断を検知したノード C が経路修復を開始し，またストラフィックを考慮していない，といった理由のた一部残存する経路を用いた経路が最新の経路であるとめ，その影響は小さいと考えられる．

判断して接続する (図 3(b))．

また本実験では，リンクの切断は，同様に iptables

図 2(c) と図 3(c) は，ノード B，C 間のリンクがの MAC 層のフィルタ機能を用いてリンク先のノード交差点における障害物の影響により切断した状態を表からのパケットを破棄することで実現している．

している．このとき GVGrid では，ノード B は自身3.3 車両の移動シナリオと経路切断状況
本節では，車両の移動シナリオと GVGrid と AODVにおける経路切断・復元状況について述べる．

が初期経路を表す道路グリッド列から外れたことを認識するため，接続しているノード A，B 間のリンクを強制切断する．そしてノード A は前方グリッドから車車間通信ではノードの移動が激しいため，ビルな代替ノード G を選択して経路の修復を開始し，残存どの障害物を考慮した場合，構築された通信経路が交経路と接続する (図 2(c))．これに対し，AODV では，差する 2 道路上の車両間リンクを含む場合，そのリンノード B が経路の修復を開始するが，このときノークの生存時間は短いことから切断回数が多くなる．まド F, 目的地 d 間の残存経路は最新の経路ではないとた，同一道路を走行する車両間のリンクでも，それら判断し，最新の経路を再構築する (図 3(c))．のノードの進行方向が逆である場合はノード間距離の

図 2(d) と図 3(d) は，送信元 s，ノード A 間のリ増大によりリンクが切断する確率が高くなる．その一ンクが距離の増大により切断した状態を表している．

方で，進行方向が同方向であり，かつ速度が同程度でこの場合 GVGrid では，送信元 s は前方グリッドからある場合はノード間距離はほぼ一定に保たれ，リンク代替ノード H を選択して経路の修復を開始し，残存切断が発生する確率は低くなる．

経路と接続する (図 2(d))．AODV は，リンク切断をGVGrid では，経路の切断が発生した場合，修復を検知した送信元 s が経路修復を開始し，また残存経路― 543 ―

M

LM

LK

Kdd

J
J

E

E
H

A
Bs

C

F
G

D

H

C

B

A

F

I

N

I

N

D

Gs(a)

(b)

M

L

M

L

K

J

dKd
E

J
E

H

C

B

C

B
A

F

H

Gs
N

As

I

F
G

N

(c)

I

(d)

J

M

L

L

M

J
E d

E
B

C K

BdCK

N
N
H

A

F
Gs

H

I

A

(e)

F
Gs

I(f)

図 2 車両の移動シナリオと GVGrid における経路切断状況

を最新の経路と判断して接続する (図 3(d))．

経路修復を開始し，最新の経路を再構築する．同時刻

図 3(e) では，AODV は，ノード J，K 間が障害において，GVGrid でリンクの切断は発生していない物により，ノード K，目的地 d 間のリンクが距離の(図 2(e))．
図 2(f ) は，GVGrid において，ノード G，F 間のリンクが距離の増大により，ノード F，E 間のリンク増大により切断が発生し，リンク切断を検知したノー
ド J が RREQ メッセージのブロードキャストによる― 544 ―

M

LM

L

K

Kdd

J
J

E

E
H

A
B

s

C

F
G

D

H

C

B

A

F

I

N

I

N

DGs(a)(b)

M

L

M

LK

JdKd

J

E

E

H

C

B

C

B
A

FHGsNAsI

FGN(c)

I(d)

JM

LL

M

JE dE
BC KBdCKNNHAFGsHIA(e)

FGs

I(f)

図 3 車両の移動シナリオと AODV における経路切断状況

は交差点における障害物などの影響により切断した状より切断が発生し，リンク切断を検知したノード A が態を表しており，ノード G は前方グリッドから代替経路修復を開始し，また残存経路を最新の経路と判断

ノード I を選択して経路の修復を開始して残存経路として接続する様子を表している．

接続する．これに対し図 3(f ) では，AODV においてノード A，B 間とノード B，J 間のリンクが障害物に3.4 計測ツール
GVGrid と AODV のスループットの計測は，実験― 545 ―で使用するノードとは別に実験中のパケットをキャプ

表 1 制御パケット数と ICMP パケット数
プロトコル名制御パケット数
ICMP パケット数

チャするノードが行う (以下パケットキャプチャノー

AODV
GVGridド)．パケットキャプチャノードは，無線 LAN の設定

2503
2201

34503453をプロミスキャスモードにすることで実現している．
プロミスキャスモードとは，任意の宛先のフレームを傍受することができるモードであり，これを利用することで実験において使用する全てのノードが送信するパケットをキャプチャすることができる．また，キャプチャしたパケットの分析には，パケット分析ツールである Ethereal8) を使用した．

3.5 評 価 結 果
ICMP パケットを ping プログラムにより連続送出し，3 分間の実験シナリオを元にした経路の切断と修復における GVGrid と AODV のスループットを計測した．図 4(a) は GVGrid，図 4(b) は AODV のス

図5GVGrid の TCP シーケンスループットを示している．
経路修復プロセスにおいて，切断が発生してから経のバッファ溢れが起こる可能性が減り，安定したデー路修復が完了するまでの間に送信されたパケットはタ送信を行うことができることを示している．また，バッファリングされ，経路修復完了後にバッファリン切断回数も少ないことから，通信に与える影響は極めグされていたパケットが送信される．そのため，経路て小さいものと考えられる．の切断が発生するとデータパケットの送信を停止し，

表 1 は，GVGrid と AODV におけるパケット数を経路修復のための制御パケットを送信するためスルー示している．GVGrid と AODV は，同程度の ICMPプットは低下し，経路修復後にはバッファリングしてパケット数を送信しているのに対し，制御パケット数いたデータパケットを送信するため，スループットがにはかなりの差が表れている．AODV は経路の切断が一時的に大きくなる．

発生した場合，RREQ メッセージをブロードキャスト

図 4(b) から，AODV では，各経路切断の際には送信して経路の修復を行い，また部分経路が存在するスループットが著しく低下しており，経路修復後のス

場合でもその経路が最新でないときは，制御メッセー

ループット値は一時的に大きくなっていることがわか

ジを利用して経路の探索を行う．これに対し，GVGrid

る．AODV では，経路の修復を開始すると最新の経では経路の切断が発生した場合，RRPR メッセージを路を構築しようとするため，部分経路が存在する場合特定のノードへ送信して経路の修復を行い，また部分でもその経路が最新でない場合は経路の探索を行う．

経路が存在する場合はその経路を再利用する．AODV

そのため経路修復にかかる時間が長くなり，経路の切と比較して GVGrid で制御メッセージが減った要因は，断を検知したノードにおける ICMP パケットのバッ

経路修復において，AODV では，残存経路が最新でなファリング数が増えたためであると考えられる．これい場合，修復された部分経路以外に最新の経路探索にに対し図 4(a) より，GVGrid は，各経路切断の際はおいても制御パケットが使用されているが，GVGrid

スループットは低下しているが，低下の度合は低く，は，修復された部分経路でのみ制御パケットが使用さ経路修復後のスループット値も AODV ほど大きくなれているためと考えられる．

い．GVGrid は，経路の修復において部分経路が存在最後に，同じシナリオを用い，GVGrid による経路する場合はその経路を再利用するため，経路修復にか上で TCP 通信を行った場合のパケット到着時刻を計かる時間が短く，経路の切断を検知したノードにおけ測した．結果を図 5 に示す．横軸が時刻，縦軸がそる ICMP パケットのバッファリング数が少ないための時刻までに受信を完了したシーケンス番号を示す．と考えられる．

おおよそスループットの大きな減少も観測されず，ス以上のことから，AODV と比較して GVGrid では，経路修復の間のデータのバッファリングが少なく済み，ムーズな通信が実現できている．

これは各ノードのバッファサイズを小さくできる，あ4. あ と が き

るいはビットレートを上げるなどした場合でもデータ

本研究では，研究グループが提案している車車間― 546 ―(a) GVGrid(b) AODV

図4GVGrid と AODV のスループット

ルーティングプロトコル GVGrid により構築される通信経路の品質を評価するためにそのプロトタイプ実装を行った．また，ノート PC10 台程度からなる小規模テストベッドを構築し，車両の移動を考慮して作成したリンク切断シナリオにもとづいて経路のリンク切断，復元をテストベッド上で実現し，ICMP パケットを連続送出した上で GVGrid と AODV による経路のスループット評価を行った．その結果，GVGrid はAODV と比較してより高いスループットを達成し，また制御パケット数が少ないことを確認した．
今後の課題としては，テストベッドの機能強化が挙げられる．例えばトラフィックシミュレータから得られる車両位置情報の利用，ストリーミング実験 (リアルタイム配信) を通した動画品質，デバッグ機能の実装などが挙げられる．

参考 文献1) 孫 為華，山口弘純，楠本真二：安定性の高い経路を構築する車車間ルーティングプロトコル，情報処理学会論文誌， Vol.47, No.7, pp.2141–2150(2006).
2) Sun, W., Yamaguchi, H., Yukimasa, K. andKusumoto, S.: GVGrid:A QoS Routing Protocol for Vehicular Ad Hoc Networks, Proc. of14th IEEE International Workshop on Qualityof Service (IWQoS2006), pp.130–139 (2006).
3) Uppsala University: aodv-uu. http://core.it.uu.se/core/index.php/AODV-UU.
4) Zhang, Y. and Li, W.: An Integrated Environment for Testing Mobile Ad-Hoc Networks, Proc. of ACM Int. Symp. on Mobile Ad
Hoc Networking and Computing (MobiHoc’02)(2002).
5) Nordstrom, E., Gunningberg, P. and Lundgren, H.: A Testbed and Methodology for Experimental Evaluation of Wireless Mobile Ad
hoc Networks, Proc. of IEEE TridentCom 2005(2005).
6) Ott, M., Seskar, I., Siracusa, R. and Singh,
M.: ORBIT Testbed Software Architecture:
Supporting Experiments as a service, Proc. ofIEEE TridentCom 2005 (2005).
7) : iptables. http://www.iptables.org.
8) : Ethereal. http://www.ethereal.com.
9) Perkins, C. E., Belding-Royer, E. M. andDas, S.: Ad Hoc On Demand Distance Vector(AODV) Routing, RFC 3561 (2003).

― 547 ―