安定性の高い経路を構築する車車間ルーティングプロトコルGVGridの性能評価

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2005−MBL−35（16） 2005−ITS −23（16） 2005／11／17. 安定性の高い経路を構築する車車間ルーティングプロトコル GVGrid の性能評価孫為華山口弘純楠本真二大阪大学大学院情報科学研究科コンピュータサイエンス専攻. 我々の研究グループでは，車車間通信を利用した位置情報ルーティングプロトコル GVGrid を提案している．GVGrid は移動しない送信ノードからある地理領域に存在する車両群へのデータ送信を行うための経路を構築する．電子地図情報を用い，なるべく車両流に沿った経路を構築することで，ノード移動による切断の可能性を低減させる．また，経路上の各ノードは，発見した経路の地理的形状を記憶することで，経路が切断した場合もその経路に近い形状の経路を少ないメッセージ数で再構築する．本稿では GVGrid の詳細設計を行うとともに，既存手法 GPCR と比較した性能評価を行った結果の考察を行う．. GVGrid: A Geographic Routing Protocol for Constructing Stable Route using Inter-Vehicle Communication Weihua Sun Hirozumi Yamaguchi Shinji Kusumoto Graduate School of Information Science and Technology of Osaka University We have proposed a position-based routing protocol called GVGrid on mobile ad hoc networks constructed among vehicles with short range commucation devices. GVGrid constructs a unicast route on-demand, which is used to transmit data continuously from a sender to vehicles that exist in a specified region. When the route is broken by movement of vehicles, GVGrid tries to fix the route using the location information of the original route. By simulation experiments, we have compared the performance of GVGrid with an existing position-based routing called GPCR to see the efficiency of GVGrid.. 1. まえがき. 近年，高度交通システムの普及を目指し，DSRC や VICS などの狭域通信器が徐々に路側や店舗などに設置されつつある．しかし，これらインフラの完全な整備と展開には膨大なコストと年月がかかる．さらに，技術の進歩や革新に対し，維持整備の観点から機器の更新は安易にできないといった問題点もある．これに対し，固定インフラを用いない車車間マルチホップ通信技術を利用し，固定インフラが発する情報の配信範囲を拡大する補完的な役割を持たせたり，また極めて局所的な情報伝達に用いたりすることが考えられている．我々は，車車間マルチホップ通信により，例えば DSRC 路側機のような近距離無線基地局や，あるいは事故現場などに停止した緊急車両から，指定された地理領域内に存在する車両群へデータを送信するための経路をオンデマンドで構築することにより，そのような基地局がカバーしない任意の地点に対して最新の駐車場情報，交通誘導情報，事故情報，店舗情報など局所的かつリアルタイムな情報を送信するアプリケーションを実現するためのプロトコル GVGrid を提案している [4]．GVGrid は，各車両がカーナビなどの電子地図を利用して道路形状を識別し，道路に沿って同一方向に移動する車両群からなる経路を構築することで，経路の耐切断性を向上させ，少ない経路維持コストでの通信を目指したモバイルアドホックネットワーク上. の位置情報ルーティングプロトコルである．さらに，それにより得られた経路の地理的形状を記憶し，経路切断時には記憶した経路になるべく近い経路を少ない経路再探索メッセージで発見する．GVGrid のアプリケーション例として，事故情報を現場に流入する道路上の車両に配信して迂回を促す，付近の交差点で信号待ちをしている車両に広告を配信する，などが考えられる (図 1)．本稿では，GVGrid の詳細設計について述べる．特に，文献 [5] で提案されているブラックバースト方式を改良して利用し，ノード密度が高い市街地における Hello メッセージ交換にかかるオーバヘッドを削減するようにしている．また，深さ優先探索を行うことで知られる位置情報ルーティング GPSR [1] の車両版である GPCR [2] をシミュレータ上に実装し，大阪府吹田市の市街地マップ (図 11) を用いたシミュレーションによる比較実験を行った．その結果，GVGrid において構築された経路がより安定していること，また経路再探索にかかるメッセージ数が極めて少ないことを示した．. 2. 関連研究. マルチホップ車車間通信による情報伝達やコミュニケーションを扱った研究はこれまでに多く存在する．. −113−.

(2) ゲーションシステムの装備率増加を受け，電子地図の参照が可能であるという仮定のもとで，指定領域内の道路に沿い，かつ車両がなるべく同一方向に移動していると想定される経路を幅優先探索で探索することで，高い耐切断性を持つ経路を発見する．また，それにより発見した初期経路が十分な耐切断性を持ち合わせているとの仮定のもとで，経路切断時にはその初期経路に近い経路のみを再探索することで経路探索メッセージ数を大幅に削減する．その意味で GVGrid は，車両の移動特性や，経路の特性を用いてメッセージ数を減らす工夫をするなどの独自性を維持しながら比較的シンプルなプロトコルで要求機能を実現している．. 図 1: 事故現場への流入地点となる交差点付近へ事故情報を送信する例. 3. ブロードキャストベースの情報散布プロトコルとして，文献 [7][8][3] などが提案されている．なかでも，UMB[7] は各車両が道路に沿ってなるべく遠方にある車両にメッセージを送信し，経路のホップ数の減少を図るプロトコルである．UMB では道路の各交差点にあらかじめリピータが設置してあると仮定しているため，実用性に乏しいといった欠点がある．RBM [8] はノード密度の低い高速道路での情報伝達を目的として，メッセージを受信したノードは通信範囲に他ノードが入ってくるまで送信を待機するプロトコルである．また，MDDV プロトコル [3] は電子地図と GPS 情報を利用して，予め設計された経路を構築し，継続的に情報を送信する手法である．この手法は事前に経路を設計するため，経路の安定性などの点で優れている．しかし，交通量変化の大きい地域では，環境変化への適応性に乏しい面がある．. GVGrid では，地理領域はあらかじめ正方形の領域群（グリッド）に分割されているとし，各グリッドは一意な ID を持っているとする．各車両（以降はノードと呼ぶ）は近距離無線デバイス（IEEE802.11 など）を装備し，一意な ID を持っているとする．また，各ノードは GPS 経由で自身の位置情報を取得できるとし，全車両の無線範囲は同じであるとする． GVGrid は移動しない発信源（以下 SRC ノードとよぶ）から，指定領域（以下 DEST 領域）内を通過する車両へのユニキャスト通信経路をオンデマンドに構築し，維持する位置情報ルーティングプロトコルである．GVGrid は以下の特長を持つ． 1. 同じ道路を走行する車両は比較的近い速度で移動するため，相対的な距離関係はそれほど大きく変化しないと考えられる．この特性を考慮し，なるべくリンク切断の少ない経路を発見するため，GVGrid は互いに接続された道路上の車両から構成される経路を経路候補として探索する．. ブロードキャスト型のプロトコルに対し，エンド間で経路を構築するルーティングプロトコルも幾つか提案されている．これらは基本的に経路探索メッセージを用いたオンデマンド経路発見手法を用いており，経路発見や維持にかかるメッセージオーバヘッドの減少などが重要な課題である．グリッドを用いて経路探索メッセージ数を低減させる位置情報ルーティングプロトコルとして CarNet [9] が提案されている．しかし，CarNet は高速にランダムな移動をするノードを対象としており，車両の移動特性や道路の地理特性などについては考慮していない．GPCR [2] は，各ノードが基本的には無線範囲内にある最も宛先領域に近いノードをグリーディに選択することで経路を構築し，かつ障害物を迂回した経路も発見可能な位置情報ルーティング GPSR[1] を車車間通信に応用したプロトコルである．GPCR は，路側の建築物などを電波の障壁と考え，電波の届く範囲で最も宛先領域に近い車両を経路探索メッセージとして選択し，交差点のない道路では道路に沿って経路を構築する．交差点では無線範囲内の車両の密度分布を用いて交差点を識別し，最も宛先領域に近い車両に経路探索メッセージを転送する．しかし，GPCR では現実に建造物間の隙間や，電波の障壁がないような地域において，複数の道路を跨る経路を構成する可能性がある．また，深さ優先で探索を行うため，道路の形状により，ノード間の距離が非常に長くなる可能性もある．このため，GPCR で構築した経路は車両の移動によるリンク断の影響を受けやすいと想定され，経路の維持にかかるオーバヘッドが大きいと想定される．我々の提案する GVGrid では，近年の車両におけるカーナビ. GVGrid プロトコル. 2. 1. の探索により得られた候補からあるメトリックに基づき決定された経路（これを初期経路とよぶ）は，比較的広範囲を探索して得られる経路であるため，そのメトリックにおいて比較的高品質な経路であると考えられる．この考えに基づき，初期経路発見時にその経路上の各ノードは初期経路の地理的形状をグリッド列番号により記憶しておき，経路が切断した場合はそのグリッド列上で代替ノードを発見する．これにより初期経路と同様の地理的形状を備えた経路を再構築する． GVGrid は，車両密度の高い都市部に適している．車両密度の高い都市部でフラッディング手法を使うと，各ノードが一斉にブロードキャストし，ブロードキャストストーム現象が起こり，通信効率が極端に低下することは文献 [10] などですでに指摘されている．我々はこの問題を想定し，経路の構築と維持のプロセスでメッセージ数を削減するとともに，品質のよい経路を構築することを目的とする．. 3.1. 地図情報とグリッドの設定. GVGrid では，各ノードは道路情報を共有しているものとする．ここでの道路情報とは一意な ID 付きの道路を辺とした無向グラフである．また，GVGrid は地理領域を複数の矩形領域（グリッド）に分割する．分割の仕方は下記の通りである．. −114−.

(3) n6 d. n7. w. n15 n3. n8 n13 図 2: 無線距離 d とグリッドサイズ w の関係. あるグリッドに隣接する周囲 8 グリッドをそのグリッドの隣接グリッドと呼ぶ．グリッドにある各ノードが隣接グリッド内のノードと通信できるように，グリッドサイズ w と無線範囲 d √ の関係を w = 2d/4 と定義する（図 2）．経緯度（0,0）始点として，各グリッドの ID をその左下頂点の経度緯度のグリッドサイズに対する倍数で定義する．NMEA 基準の GPS 情報は aaabb.cccccc のフォーマットとなる．aaa は度（0∼180），bb は分（0∼60），cccccc は分の小数表現（精度は 10−6 まで）を表す．グリッドサイズ w が各ノードにおいて既知の場合，経度 x 緯度 y に位置するノード v の存在するグリッド ID G(v) を下記のように定義することで，各ノードは共通のグリッド領域を持つことができる．ここで，1855.3285 は GRS80 系赤道長の 1 分ごとの長さを表す．. Gx (v) = (x - (x div 100 * 40)) * 1855.3285 div w Gy (v) = (y - (y div 100 * 40)) * 1855.3285 div w G(v) = Gx (v) * 106 + Gy (v). プロトコル記述. GVGrid は経路構築プロセスと経路維持プロセスからなる．経路構築プロセスでは，LAR[6] のメッセージ削減手法に基づき，メッセージを転送する際，SRC と DEST を含む転送領域を予め設定し，この領域内のみでメッセージを転送する．. ブラックバースト. 既存手法の多くはビーコン（Hello Message）を定期的に交換することで，周辺ノードのリストを生成し，経路探索メッセージの転送ノードを選定するが，市街地など狭い地域に大量の車両が存在している環境における頻繁なビーコン交換は，深刻なパケット衝突問題を引き起こす．しかし，ビーコンの交換頻度を下げれば，ノードの把握した隣接ノード情報（位置情報）の誤差が大きくなり，プロトコルの精度を下げる可能性がある．そこで，都市部などノード密度が高い状況での利用を前提としている GVGrid は，文献 [5] で提案されているブラックバースト手法と呼ばれる方式を改良して用い，経路構築プロセスにおいて最適な転送ノードをオンデマンドに選定する方法を採用する．ブラックバーストは，位置情報ルーティングにおいて，無線範囲内の送信ノードのうち，最も自身との距離が長いノード. SRC. n5. n4 n10. n12. n11. 図 3: 経路探索の例. を識別するために用いられる．送信ノードは自身の位置情報を含めたブラックバースト要求パケットをブロードキャストし，これを受信した隣接ノードは，自身と送信ノードの距離を計算し，最大通信距離に比例する時間長の雑音を発信する．たとえば，最大通信距離が 200m で，ブラックバースト要求パケットを受信したノード A とノード B があり，それぞれ送信ノードとの距離が 50m と 100m とすれば，A は 1/4 タイムスロット長，B は 1/2 タイムスロット長をバーストする．バースト完了直後に雑音を聞かないノードのみが送信ノードに返信することで，最も距離の長いノードを選定できる．. GVGrid ではブラックバーストを以下の通りに改良し，以降で述べる経路構築プロセスで用いる．送信ノードは，ノードを選定したいグリッド ID および道路 ID とそのグリッド内での位置を指定した経路探索メッセージをブロードキャストする．受信したノードはまず自身の位置するグリッド ID と道路 ID を判断し，指定されたものと異なればそのメッセージを破棄する．一致したノードは自身の位置とパケットで指定された位置との距離を計算し，近いほど長いタイムスロット長で送信することで，なるべく指定された位置に近いノードを選定する．. 3.2.2 3.2.1. n9. DEST. n14. 3.2. n2 n1. 経路構築プロセス. 経路構築プロセスは，SRC ノードから，DEST 領域として指定されたグリッド内の車両群への経路を探索する．. SRC ノードは DEST 領域までの経路情報を持ち合わせない場合，経路構築プロセスを開始する．SRC ノードは自身のグリッドに隣接する各グリッドごと，ノードが一つ以上存在すればそのうちの一つ（例えばグリッドの中央に近いノード）を選択し，経路探索メッセージ（Route REQuest，以下 RREQ）を上述の改良ブラックバーストを用いて送信する．選択した隣接ノードに RREQ を送信した後，SRC ノードはタイマを設定し，経路確定メッセージ（Route REPly，以下 RREP）待ち状態に入る．タイマが終了するまでに RREP を受信できなければ，SRC ノードは再度経路構築プロセスを実行する． SRC ノードから RREQ を受信した各ノードは，同様に自身のグリッドに隣接する各グリッドごとそのグリッド ID と，自身. −115−.

(4) の位置する道路と同じ道路かその道路に接続している道路の道路 ID を指定した改良ブラックバーストによりノードを選択し，自らが存在するグリッドの ID を RREQ に記録した上で送信し，その後 RREP 待ち状態に入る．それを受信した各隣接ノードも同じ操作を繰り返すことで，DEST 領域に RREQ が到達する． SRC. 一度 RREQ を転送したノードは，メッセージ数抑制の観点から，同じ経路探索における別経路からの RREQ であることを判断した場合，自動的に最長タイムスロットでのバーストを行い，他ノードの RREQ 受信を妨害することで，重複する経路の探索を抑制することも可能である．一般的には最小ホップ数でのメッセージが最初に到着すると予想されるため，ホップ数が経路品質を表す場合はこの方法はメッセージ数削減において有効である．しかし，これにより対象とする経路数を制限することになるため，複数の RREQ を転送することによるメッセージ数の増加と発見された経路候補数やその品質との間のトレードオフを今後追求する予定である．. 42. n5. 21. 31. 00 図 4: 経路探索により構築された経路例. DEST y. x. u v. w. SRC. SRC ノードが RREP メッセージを受信すれば経路が確定される．SRC ノードをはじめ，経路上にあるすべてのノードは，この経路が存在するグリッドの ID 列を初期経路の形状として記憶する．. DEST 代表ノードは RREQ に記録された経由ノード ID 列の情報を利用して，経路確定メッセージ（Route REPly，以下 RREP）を SRC に向けて送信する．図 3 では，DEST 代表ノードに複数 RREQ メッセージ（複数の経路候補）が到達したため， DEST 代表ノードはこの場合最小ホップの経路を選んで RREP. 11. DEST. RREQ が DEST 領域の隣接グリッドのあるノードに到達した場合，そのノードは次ホップが経路の終点であることがわかるため，DEST 領域に対し，ID の大きさに反比例するように指定したバースト要求をブロードキャストする．これにより，ノード ID の最も小さいノードを識別し，このノードに RREQ を転送する．このノードを DEST 領域の代表ノードと呼ぶ．代表ノードは到達した複数の RREQ から一つを選んで経路を確定し，RREP メッセージを SRC ノードに向けて送信する．複数の経路候補から選択する基準として，ホップ数，右左折数，道路幅などが挙げられるため，これらの要素を総合的に考察することを予定している．. 図 3 は経路探索プロセスの実行例である．SRC ノードは自身と DEST 領域を含むメッセージ転送領域を決め，各隣接グリッドごとに 1 ノードずつ選択し，RREQ メッセージを送信する（この例ではこの領域が転送領域であるとする）．図 3 で選択されたノードは n1，n2，n3，n4，n5 である．これらのノードは，自身の各隣接グリッドから自身と同じ道路上に存在するかその道路と接続している道路に存在するノードからそれぞれ 1 ノードを選択し，RREQ メッセージを転送する．この例では， n2 から n15 へ，n5 から n9 および n10 へ RREQ が転送される．n1，n3，n4 は隣接グリッド内に接続している道路がないか，すでに n2 と n5 により RREQ が送信されたため，これ以上 RREQ を送信しない状況を表している．これらのグリッドではバースト要求に対し，すでに RREQ を転送したノードが最長バーストを行うことで RREQ を棄却する．例えば n1 の RREQ は n2 および n3 により, n2 の RREQ は n15，n3 および n1 により，n4 の RREQ は n3，n5 および n10 により棄却されている．RREQ メッセージを受信した n13 は DEST 領域の隣接グリッドであるため，DEST 領域内でノード ID が最小であるノード（DEST 代表ノード）に対し，RREQ メッセージを送信する．同様に n14 も DEST 代表ノードへ RREQ を送信する．. n9. n13. 図 5: 経路維持 - 初期経路. を送信している．RREP メッセージを受信した各ノードはメッセージ内の経路情報を初期経路として保存し，RREP メッセージを SRC ノードへと転送する．例えば図 4 では，選ばれた経路は SRC-n5-n9-n13-DEST であるため，保存される初期経路のグリッド ID 列は 42-31-21-11-00 となる．RREP メッセージが SRC ノードに到達すると，経路構築プロセスが完了し，SRC ノードと DEST 代表ノード間の通信が可能となる．DEST 代表ノードは SRC から受信したデータを DEST 領域内に送信することで DEST 領域内の全ノードに伝播する．. 3.2.3. 経路維持プロセス. 経路維持プロセスは，経路が切断した場合，初期経路を表すグリッド上に存在しないノードを経路から切り離し，切断した箇所から代替ノードを探し，初期経路に沿った形で経路を復元させる．. SRC ノードから DEST 代表ノードまで経路を構築した後，中間ノードの移動や，DEST 代表ノードの DEST 領域からの離脱などにより，経路の切断が発生する．経路上の各ノードは，自身の前後ノードと切断した場合，自身が現在存在しているグリッドが初期経路グリッドの列に含まれないと判明すれば，自身と接続しているノードとのリンクを強制切断し，初期状態に戻る．これにより新たなリンク切断が発生し，初期経路グリッド上にないノードはこれと同じ動作を繰り返す．その結果，前. −116−.

(5) DEST. DEST. y y’ x. x’. v u v’. w. u’. SRC. w. SRC. 図 6: 経路維持 - 変形した経路. y. 図 8: 経路維持 - 経路復元. DEST. v. X. x. u. SRC. X. X. DEST. y’ x’. w. v’ u’. w. SRC. 図 7: 経路維持 - 連鎖離脱図 9: 経路維持 - DEST ノードの離脱方或いは後方ノードと切断状態で，かつ自身も経路から離脱したノードはすべて経路から外されることになる．前方ノード（経路上での DEST 側のノード）とのリンクが切断されたが初期経路グリッド列上にあるノードは，以下に述べる経路維持プロセスを開始する．各ノードは記憶した初期経路グリッド ID 列における自身のグリッドの前方グリッドから代替ノードを探し，自身の記憶した初期経路情報を含む経路維持メッセージ（Route RePaiR，以降 RRPR）を送信することで初期経路の情報を共有させる．前方グリッドから代替ノードを選択する際，切断した経路の残存ノードが存在すれば，そのノードを優先的に選択する（改良ブラックバーストを用い，経路をキャッシュしている残存ノードに最長バーストをさせることで実現できる）．これにより，初期経路グリッド列上にある残存経路を最大限に利用でき，リンク切断が発生した場合も局所的再接続により経路を再構築できる．再構築が不可能な場合，そのノードは経路エラーメッセージ（Route ERRor メッセージ，以下 RERR）を SRC ノードに送信する．この場合，SRC ノードは経路探索プロセスを実行し，新たな経路を探索する．図 5 ー図 10 を用いて経路維持プロセスを説明する．図 5 ー図 10 の灰色グリッドは，初期経路グリッドを表す．経路上の各ノードはこのグリッド ID 列を記憶している．この図にある経路は，SRC-u-v-w-x-y-DEST である．ノードは移動により，初期経路グリッドから離れることもあるが，各ノード間で通信が可能な間はそのまま経路を維持する（図 6）．ここで，図 7 のように，一部のノード（v ，y ）が経路上の隣接ノードとの距離が. 大きくなり，リンク切断が発生したとする．前後に経路が切断したノード u および x は，自身が初期経路グリッドから外れているため，リンク u-SRC，x-w を強制的に切断し，経路から離脱する．この後，図 8 のように，SRC ノードが前方グリッドから新たなノード u0 を，w は前方グリッドから新たなノード x0 をそれぞれ発見し，RRPR を送信して接続する．ノード w0 および x0 はさらに前方から v 0 および y 0 をそれぞれ発見する．ノード v 0 および y 0 はそれぞれノード w および DEST ノードと接続することで経路が復元される．なお，DEST 代表ノードが DEST 領域から外れる場合もある．図 9 では，DEST 代表ノードは強制的に後方ノードであるノード y 0 との接続を切断し，経路から離脱する．図 10 では，ノード y 0 は DEST 領域から新たな DEST 代表ノードを選択して接続することで，経路が復元された例を示している．移動しない SRC ノードとその前方ノード間のリンク，および DEST 代表ノードとその後方ノード間のリンクは経路上で最も切断しやすい個所であると想定される．GVGrid における経路維持プロセスを用いることで，少ないオーバヘッドでの局所的な再構築が可能となる．. −117−.

(6) 500. GVGrid GPCR. DEST. RREQ messages. 400. y’ x’. 300. 200. 100. v’ u’. w 0. 600. 800. 1000 Distance(m). 1200. 1400. 図 13: 経路探索プロセス-探索メッセージ数. SRC. 50. GVGrid GPCR. 図 10: 経路維持 - 代替 DEST ノード RRPR messages. 40. 30. 20. 10. 0. 600. 800. 1000 Distance(m). 1200. 1400. 図 15: 経路維持プロセス-探索メッセージ数. GPCR で経路を探索する時，各ノードは隣接ノードの中で最も DEST へ近いノードを選択し，メッセージを転送する．ノードの転送したメッセージが行き当たりに到達した場合，逆戻りして手前の交差点で逆時計周りの方向へ迂回路を探索することで，経路の発見率を向上させる．転送方向に交差点がある場合，交差点内のノードにメッセージを中継してもらうことで，建物などで発生した電波の遮断により経路ノード候補数の減少を防いでいる．経路が切断した場合，GPCR は SRC から DEST へ再探索を行う．. 図 11: 実験に使用したマップ (吹田市). 4 4.1. 評価実験シミュレーション設定. GVGrid の性能を評価するために，道路交通流シミュレータ N ET ST REAM [14] とネットワークシミュレータ GT N etS を使用した． N ET ST REAM は豊田中央研究所で開発されており，現実の車両の進路変更，速度制御などを取り入れ，長野冬季オリンピック [15] の交通量概算にも使われた道路交通流シミュレータである． N ET ST REAM で出力される 15 分間の車両データログファイルを GT N etS に導入することで，GVGrid プロトコルのシミュレーション実験を行った．シミュレーション設定はフィールドサイズが約 1200m x 1200m で，s と DST の直線距離が 500m，1000m，1500m で，同時存在ノード数が約 200，車両速度が 8.3m/s(30km/h)∼16.6/s(60km/h)，グリッドサイズが 70m，無線範囲が 200m，帯域 2Mbps，シミュレーション時間が 600sec とした． GVGrid の比較対象として，GPCR を実装した．GPCR は GPSR の車車間通信版で，高い経路の発見率を目指した深さ優先探索手法である．GPCR は，建物などで電波の周辺への伝播は阻害され，電波の届くノードは同じ道路上にある可能性が高いという前提の下で SRC から DEST への経路を構築する．. 4.2. 経路探索プロセスの性能. 経路発見率経路の発見率は，経路探索プロセスの総実行回数の内，経路を発見した回数の割合である．図 12 の通り，GPCR の経路発見率は距離による影響は小さく，常に高い発見率を保持している．GPCR は DEST に可能な経路があればそれを高い確率で発見する．これに対し，GVGrid は距離が長くなるにつれ，徐々に発見率が劣化してゆく．GVGrid は幅優先探索であるが，転送ノードを選択する基準がより厳しいため，転送ノード候補数は GPCR より少なく，繋がった後の経路安定性を最重視しているため，経路の発見率は GPCR より低い．しかし，都市部のような密度の高い環境下では，GVGrid の発見率と GPCR のそれとの差はほとんどない（図 12(a)）．. 探索メッセージ数探索メッセージ数は一回の経路探索プロセスで送信される RREQ の総数である．GPCR は深さ優先探索のため，探索メッセージ数は非常に少ない．これに対し，GVGrid は幅優先探索のため，探索メッセージ数は GPCR の数倍に到達したが，総数としては低い範囲に抑えている（図 13）．. −118−.

(7) 100. GVGrid GPCR. 80. 80. 60. 60. Discovery rate. Dicovery rate. 100. 40. 40. 20. 20. 0 400. GVGrid GPCR. 450. 500. 550. 600 Distance(m). 650. 700. 750. 0. 800. 2. (a) 密度 560 台/km. 600. 800. 1000 Distance(m). 1200. 1400. (b) 密度 140 台/km. 2. 図 12: 経路探索プロセス-経路探索率. 100. GVGrid GPCR. 80. 80. 60. 60. Recovery rate. Recovery rate. 100. 40. 40. 20. 20. 0 400. GVGrid GPCR. 450. 500. 550. 600 Distance(m). 650. 700. 750. 800. 0. 2. (a) 密度 560 台/km. 600. 800. 1000 Distance(m). 1200. (b) 密度 140 台/km. 1400. 2. 図 14: 経路維持プロセス-経路再探索率. 4.3. 経路維持プロセスの性能. 経路再探索率経路再探索率は，経路の切断回数に対し，その経路を回復できた回数の割合である（図 14）．GPCR の経路維持は，単純に SRC からの再探索であるため，経路発見率の部分で示した数値と大体一致している．これに対し，GVGrid は初期発見した経路のグリッドの列上でのみ経路を再探索するため，経路ノードの候補数が大きく抑えられているため，GPCR ほど高くない．GVGrid の維持能力は密度による影響が最も大きく，ノード密集度の高い地域では，高い維持率も可能である（図 14(b)）．. 探索メッセージ数経路維持の探索メッセージ数は経路維持プロセス内に送信された RRPR（GPCR は RREQ）の総数である．GPCR は経路の再探索であるため，経路探索能力の部分で示した探索メッセージ数とさほど変わらなかったが，GVGrid の探索メッセージ数は GPCR よりも少なかった．これは初期経路のグリッド内に対してのみメッセージを転送しているため，修復したグリッド個分のメッセージのみで済んでいることによる（図 15）．. 4.4. くなるに従い，GPCR の探索した経路の長さが大きく増加した． GPCR は深さ優先探索のため，シナリオによって非常に長い迂回路を探索してしまう可能性がある．これに対し，GVGrid は距離に応じて線形的に増加した．GVGrid は幅優先探索のため，安定した経路の長さを提供している（図 16(a)）．. リンク生存時間 GPCR は距離の増加に従い，切断回数は劇的に増加するため，リンクの生存時間は大きく下がる．GPCR は転送ノードを選定するときに，宛先領域への近さのみを基準しているため，高速に移動する車両ノードを対象とした環境では，非常に切断しやすいのは明らかである．GVGrid は同じ道路や接続しているノードを選択しており，かつグリッドを利用することで，選択したノードは自身との距離が近く，離れるまで時間がかかるため，切断回数は少なく，リンクの生存時間も相対的に長い（図 16(b)）．以上の結果より，GPCR は経路の発見率は高いが，安定でなく，切断しやすい特性を持つため，継続的な送受信に適せず，比較的サイズの小さなデータの配布に適している．GVGrid は経路の発見率は GPCR にかなわないが，経路は比較的安定しており，切断率が低いため，継続的な送受信に有効と考えられる．. 5. 経路品質の評価. 経路長経路長は経路全体のホップ数である．必ずしも経路が長いほど悪いわけではないが，経路が長くなるにつれ，ノードが増え，どこかで切断する確率が上昇するため，経路長も経路品質の重要なメトリックの一つである．SRC から DEST までの距離が短い場合，GPCR の経路長は非常に短いが，距離が長. あとがき. 本稿では，位置情報を用いた車車間ルーティングプロトコル GVGrid を提案した．GVGrid は，SRC から DEST まで，道路に沿って経路を構築し，経路切断時において，初期経路の形に沿って経路を回復することで，経路切断率を低減し，経路探索メッセージを抑制できるといった特性を持つ．. −119−.

(8) 30. GVGrid GPCR. 25. 25. 20. 20. Link life. Route length(hops). 30. 15. 15. 10. 10. 5. 5. 0. 600. 800. 1000 Distance(m). 1200. 0 400. 1400. GVGrid GPCR GVGrid link life GPCR link life. (a) 経路長. 600. 800. 1000 Distance(m). 1200. 1400. 1600. (b) リンクの生存時間図 16: 経路品質. ネットワークトポロジ，ノード密度などが GVGrid の性能に与える影響や，経路長と交差点数間などのメトリックが経路の切断率に与える影響を調べることなどが今後の課題である．. [9] R. Morris, J. Jannoti, F. Kaashoek, J. Li, and D. Decouto. CarNet: A scalable ad hoc wireless network system. In Proc. of SIGOPS European Work-shop, 2000. [10] S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu. The broadcast storm problem in a mobile ad hoc network. In Proc. of ACM/IEEE Mobicom, pages 151–162, 1999.. 参考文献 [1] B. Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Proc. of ACM/IEEE Mobicom, pages 243–254, 2000.. [11] M. Sun, W. Feng, T. Lai, K. Yamada, H. Okada, and K. Fujimura. GPS-based message broadcasting for intervehicle communication. In Proc. of Int. Conf. on Parallel Processing, pages 279–287, 2000.. [2] Christian Lochert,Martin Mauve,Holger Fusler,and Hannes Hartenstein. Geo-Graphic routing in city scenarios. ACM SIGMOBILE Mobile Computing and Communications Review, pages 69–72, 2005.. [12] C. Lochert, M. Mauve, H. Fusler, and H. Hartenstein. Geographic routing in city scenarios. ACM SIGMOBILE Mobile Computing and Communications Review, pages 69–72, 2005.. [3] Hao Wu,Richard Fujimoto,Randall Guensler,and Michael Hunter. MDDV:a mobility-centric data dissemination algorithm for vehicular networks. Proc.of the 1st ACM Workshop on Vehicular Ad Hoc Networks(VANET2004), pages 47–56, 2004.. [13] A. Mizumoto, H. Yamaguchi, and K. Taniguchi. Costconscious geographic multicast on manet. In Proc. of IEEE 1st. Int. Conf. on Sensor and Ad Hoc Communications and Network (SECON2004), pages 44–53, 2004.. [4] 孫為華，山口弘純，谷口健一. 車両の分布情報を利用した二地点間通信経路の車車間通信による構築と維持. マルチメディア，分散，協調とモバイルシンポジウム (DICOMO2005), pages 149–152, 2005.. [14] E. Teramoto, M. Baba, H. Mori, H. Kitaoka, I. Tanahashi, and et. al Y. Nishimura. Prediction of conditions for the nagano olympic winter games using traffic simulator NETSTREAM. In Proc. of 5th World Congress on Intelligent Transport Systems, pages 1801–1806, 1998.. [5] J.L.Sobrinho and A.S.Krisnakumar. Distributed multiple access procedures to provide voice communications over IEEE 802.11 wireless networks. Global Telecommunications Conference vol3, pages 1689–1694, 1996.. [15] G. F. Riley. The Georgia Tech network simulator. In Proc. of the ACM SIGCOMM Workshop on Models, Methods and Tools for Reproducible Network Research, pages 5 – 12, 2003.. [6] Y.-B. Ko and N. H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. In Proc. of ACM/IEEE Mobicom, pages 66–75, 1998. [7] G. Korkmaz, E. Ekici, F. Ozguner, and U. Ozguner. Urban multi-hop broadcast protocol for inter-vehicle communication systems. In Proc. of the 1st ACM Workshop on Vehicular Ad Hoc Networks (VANET 2004), pages 76–85, 2004. [8] L. Briesemeister and G. Hommel. Role-based multicast in highly mobile but sparsely connected ad hoc networks. In Proc. of ACM Mobihoc, pages 45–50, 2000. (poster paper).. −120−.

(9)