車両アドホックネットワークにおける車両密度を考慮したジオルーティング手法の提案

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. 車両アドホックネットワークにおける車両密度を考慮したジオルーティング手法の提案菊地亮平†1. 佐藤文明†1. アドホックネットワークの応用として車々間通信を利用して形成される車両アドホックネットワークは，高度交通システムにおけるアプリケーションの実現に不可欠な要素として広く研究が行われている．従来研究の一つに道路トポロジに基づいた通信経路算出と，中継車両による動的経路修復により，通信量の増加を抑制しつつパケット到達性を改善する SRS という方法が提案されている．しかし，SRS では低車両密度の環境では十分なパケット到着率が得られないという課題があった．本研究では，交通量などの道路情報を使うことで，車両密度が低い経路を避け，車両密度が高いと推定される経路を選択することでパケットの到着率を改善するルーティング方式を提案する．また，再経路探索でも到達しない場合，DTN を組み合わせることで到着率の向上を目指す．提案方式の有効性を確認するため，シミュレーションによってパケット到着率を評価する．. 1.. はじめに. する必要があるため，従来のルーティング方法では，安定した通信が維持できない．この課題に対して，道路トポロ. 情報通信技術の発展に伴い，人と道路と車両との間で情. ジに基づいた通信経路算出と中継車両による動的経路修復. 報の交換を行い，交通事故や渋滞などの様々な道路交通問. により，通信量の増加を抑制しつつパケット到達性を改善. 題の課題解決を目的とした ITS(Intelligent Transport System :. する SRS（Source routing protocol based on Road network. 高度道路交通システム）が現在盛んに研究開発されている．. Structure）という方法が提案されている[2]．受信者ベース. 1996 年に国家プロジェクトとして発表されて以来，警察庁，. の中継を行うジオルーティングの１つで，道路構造に基き. 総務省，経済産業省，国土交通省の４省庁と関係外部団体. 道路セグメント単位の通信経路を算出し通信経路に沿って. を中心に国全体で推進されている[1]．現在では路側に設置. ルーティングを行う．これにより，行き止まりや迂回が必. された無線基地局を利用し，道路交通情報をカーナビゲー. 要な経路を回避することが可能になる．また，中継が失敗. ションシステム等の車載器に配信する道路交通システム等. した場合は，動的に経路を修復する．しかし，SRS では低. が提供されている．しかし，これらのようなサービスは固. 車両密度の環境では十分なパケット到着率が得られないと. 定の通信インフラを用いて提供するため利用可能範囲が制. いう課題がある．. 限される．さらに，固定インフラの設置や管理に膨大なコストがかかる．. 車々間通信の無線リンクの不安定性を克服する新たな情報伝達方法として DTN(Delay Tolerant Network)が提案さ. そこで近年，無線技術の進歩により無線ネットワークに. れている[3]．DTN とは中断や切断が多発したり，大きな. 関する研究が注目されている．特に，近隣の端末同士が基. 伝送遅延が生じたりする劣悪な通信環境でも，信頼性のあ. 地局を通さずに直接通信を行いネットワークを形成する，. るデータ転送を実現する通信方式である．DTN の課題は，. アドホックネットワークを走行中の自動車に用いた車両ア. 如何にして通信トラフィックを抑制しながら，到着率を向. ドホックネットワーク（VANET）の研究が多く行われてい. 上させるかであり，様々な提案がある．例えば，送信ノー. る．車々間通信を利用して形成される車両アドホックネッ. ドは自身の進行方向に移動する車両に送信するものや，目. トワークは高度交通システムにおけるアプリケーションの. 的地までの直線から一定距離以内の車両に送信するなどで. 実現に不可欠な要素として，広く研究が行われている．. ある[4][5]．これらの例では，応用や端末の条件によって. VANET における安定的な通信のサポートには通信トラフ. 最適な方法は異なっている．. ィックの抑制と高いパケット到達性のあるルーティングプロトコル技術が必要になる． VANET のルーティングにおいては，ノードのモビリティによるネットワークトポロジの変動や建物の存在を考慮 †1 東邦大学理学部情報科学科 Toho University，Faculty of Science，Department of Information Science. ⓒ2015 Information Processing Society of Japan. 本稿では，ジオルーティングと通信環境が劣悪な場合有効な DTN のハイブリッド型ルーティング方式として GDRT（Gio-source and DTN Routing based on Traffic density）を提案する．これは，SRS の車両密度が低い場合の到着率低下を改善することを目的としている．道路網情報内の車両密度が推定できることを前提にし，車両密度が高い経路. 1.

(2) 情報処理学会研究報告 IPSJ SIG Technical Report を優先的に選択することで到着率の改善をする．また，動. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. 2.1.2 SRS の特徴. 的な再経路探索でもパケット転送が行えない場合，DTN を. 道路網構造や建物の影響によって生じる問題と低密度. 利用する．この時，DTN の送信相手先選択は通信相手ノー. ゆえに通信可能な車両が存在せずパケットを伝搬できなく. ドが目的地までの車両密度の高い経路上に存在することが. なる状態であるデットエンドや，高車両密度な環境でも生. 条件である．. まれてしまうトラフィックホール，これら二つの問題を解. この論文の構成として，２章で関連研究である SRS と. 決することが SRS の目的である．SRS では，前提として全. DTN について述べる．３章において提案手法である，ハイ. ての車両が共通の道路網情報を持つものとする．この情報. ブリッドルーティング方式の詳細について述べる．４章で. を用いることで，送信車両はパケットを伝搬させるための. はシミュレーションによる性能評価を述べ，５章では，本. 通信経路を道路網を考慮して作成することが可能となる．. 論文の成果をまとめる．. 2.. 関連研究. 2.1 SRS の概要 2.1.1 SRS の背景. 中継パケットのオーバーヒアにより，中継が成功したか否かを判断することで，デッドエンドやトラフィックホールを検出し動的に経路修復を行う． 2.1.3 中継経路の算出送信車両は，自身の道路網情報を用いて目的地までの最. 車両ネットワークがサポートする典型的なアプリケー. 短経路を算出し，通過する交差点情報として保持する．こ. ションとして，基地局が広範囲の道路交通情報を収集する. の時，最短距離の計算にはダイクストラ法を用いて自身の. ことが考えられ，基地局に対する高いパケット到着率を実. 直近の交差点から目的地までの最短距離を計算する．. 現するルーティングプロトコルが求められる．SRS は，道. そして，パケットに経路情報として交差点情報を付与し. 路トポロジに基づいた通信経路算出と，中継車両による動. て送信する．またこの時，送信車両は受信先を指定しない．. 的経路修復により，通信量の増加を抑制しつつパケット到. 2.1.4 パケット中継方式. 達性を改善するルーティング方式である．車両ネットワー. 受信した車両は，自身が通信経路上に存在するか否かを. クのルーティングプロトコルはパケット中継におけるアプ. パケットの経路情報から判定する．もし，自身が経路上に. ローチの観点から，送信車両が中継車両を選択する送信車. いる場合はパケットを中継する．また，送信車両からの距. 両ベースのアプローチと，受信車両が自律的に中継判断を. 離に応じたバックオフ時間を設定することで，送信車両か. 行う受信車両ベースのアプローチの２つに分けられるが，. ら遠い車両が優先的に中継する．しかし，自身よりも遠い. 送信車両が次ホップの中継車両を指定する送信車両ベース. 車両の中継パケットが聞こえた車両は中継をしない．送信. の方式では，不要なパケット中継が少なく，通信トラフィ. したパケットが中継されたことがオーバーヒアによって確. ックの抑制が期待できる．しかしながら，車両ネットワー. 認できない時，通信経路を再計算し再送する．ただし，車. クではモビリティや建物の影響により車両のトポロジが時. 両密度が低いときは，中継に失敗することがある．. 間と共に大きく変動するため，周期的なビーコン情報に依. 2.2 DTN によるルーティング方式. 存する送信車両ベースのアプローチは動作しない場合があ. 2.2.1 被災情報収集ネットワークへの応用. る．一方，受信車両ベースのアプローチでは，トポロジ変化に臨機応変に対応できるため安心して動作する．受信車両ベースの中継アプローチは，受信車両自身の条. 文献[4]では，避難所間無線ネットワークと DTN ネットワークを組み合わせた被災情報の収集システムが研究されている．これは，メッセージの到着率と冗長送信数の削減. 件のみで中継判断を行う手法と CBF(Contention Based. を目的としており，ノードがメッセージ受信した際に，中. Forwarding)を用いることで協調的な判断を行う手法の二. 継を許可する領域を目的地までの直線距離から一定距離以. つに分かれる．前者には，送信車両より宛先に近い車両に. 内に限定することで，冗長メッセージを抑制する．しかし，. のみ中継を許可することで不要なパケット拡散を抑制する. 道路構造を考慮した中継可能領域の設定ではない．. DF(Directional Flooding)方式[6]，後者には，送信車両から. 2.2.2 車両の移動予定経路を用いた車々間通信. の距離に応じてバックオフ時間を設定することで送信車両. 文献[5]では，検索したい場所にクエリを発行した車両か. から遠い車両ほどバック追う時間が短くなるため遠い車両. らの応答を受け取るための DTN 通信のスケジューリング. が優先して中継を行う DDT (Distance Defer Time)方式[7]. について提案している．. がある．しかし，大きな二つの問題がある．道路網構造や. クエリを受信した車両は，制限時間までに，目的により. 建物の影響によって生じる問題と低密度ゆえに通信可能な. 近づく可能性のある車両にクエリを転送する．クエリには，. 車両が存在せずパケットを伝搬できなくなる状態であるデ. 発行車両の経路情報が含まれており，移動予定場所や時刻. ットエンドや，高車両密度な環境でも生まれてしまうネッ. が推定できる．応答は，クエリ発行車両の移動先により近. トワークの穴であるトラフィックホールである．. づく可能性のある車両に配布される．前提として，各車両は移動経路が分かっていることが前提である．各車両の移. ⓒ2015 Information Processing Society of Japan. 2.

(3) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. 動予定経路が予めわかるという制約は実環境では厳しい条件である．. 3.. ハイブリッドルーティング方式の提案. 3.1 提案方式の特徴本研究では，SRS で課題として上げた低車両密度において，より安定した到着率を達成するために，ジオルーティングと DTN のハイブリット型ルーティング方式として， GDRT(Gio-source and DTN Routing based on Traffic density) を提案する．提案方式の特徴として，大きく分けて二つある．一つは SRS で考慮していなかった道路の車両密度について考慮す. 図 2. 提案方式の経路. る．これは幹線道路かどうか，道幅が広い道かどうか，主要道路かどうかといった道の属性をダイクストラ法の重みに反映させることで道路網情報として利用する．二つ目は，. 3.3 パケット中継方式パケットを受信して中継する方法も経路修復までは SRS. DTN ルーティングとの連携が行われる点である．中継が失. と同様である．自身が通信経路上にあるかをパケットに付. 敗した場合，再経路探索を行うが，何度か再経路探索して. 与されている交差点情報から判断して中継するかを決定す. も失敗した場合，DTN モードとなる．. る．もし，自分が経路上にいる場合は，パケットを中継す. その他，以下の SRS の基本コンセプトを継承する．. る．ただし，送信車両からの距離に応じたバックオフ時間. . を設定することで，送信車両から遠い車両が優先的に中継. 各車両は，共通の道路網情報を持っている（主要道路といった道路の属性が付いている）．. する．自身よりも遠い車両の中継パケットが聞こえた車両. . 通信経路に沿ってパケット伝送を行う．. は，中継をしない．. . 受信車両が中継を自律的に判断する．. 送信したパケットが中継されたことがオーバーヒアによっ. . 中継が失敗した場合，通信経路を再計算して経路修. て確認できない時，通信経路を再計算し再送する(図 3，図. 復を試みる．. 4 参照)．. 3.2 中継経路の算出各車両は地図情報を持っている．地図は，交差点間の接続情報と距離情報，そして道路の属性情報からなる．車両密度が高いと推定される道路である主要な道路ほど選ばれやすくするため，主要な道路ほど小さなコストになるように道路にコストを付与する．送信車両は，交差点間の距離に道路のコストを加えた交差点の接続情報を使って最短経路を求め，通信経路とする．また，SRS と同様にパケットには，経路情報として交差点情報を付けて送信する(図 1，図 2 参照)．. 図 1. 図 3. 再経路探索前. 図 4. 再経路探索後. 従来方式の経路. ⓒ2015 Information Processing Society of Japan. 3.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. ただし，ｋ回の再送信によっても，中継が確認できない. この上限を超えた場合，DTN には入らずパケットを. 場合，DTN モードとなりパケットを保持する．DTN モードでｎ回コピーを配布できた時点で，保持していたパケットを破棄する．ｋ，ｎについては，実験により最も良い値. 破棄する．. 4.. シミュレーション. を確定していく予定であるが，現在は具体的な値は未定で. 提案方式の有効性を示すため，従来方式 SRS と提案方式. ある．中継アルゴリズムのフローチャートを図 5 に示す．. を比較するシミュレーション評価を行った．交通量の粗密を道路情報に含めることで先行手法と提案手法の性能を比較する．なお，本研究では DTN 部分の実装が間に合わなかったため，道路の車両密度を用いた経路選択の効果を中心に評価する． 4.1 シミュレーション条件図 6 にシミュレーションで用いた道路モデルを示す．道路は，1000m×1000m のフィールドに格子状に配置する．また，交差点間の距離は 100m，道路の幅は 10m とする．そして，横軸（X 軸）に並行に、縦軸（Y 軸）方向に 300m の位置にある道路１本を交通量の多い密度情報を付与した幹線道路とする．この時，幹線道路のみ最低でも車両数 50 台を走行させるものとする．また，Ｘ軸 500m，Y 軸 0m の地点に目標地点となる基地局を設置する．. 図 5. 提案方式の中継処理フローチャート. 3.4 DTN ルーティングとの連携 DTN モードになった場合，パケットを条件に合致した受図 6. 信車両に遭遇したときにコピーを配布する．配布条件は以. 提案方式のマップ. 下のとおり . 自身の現在位置から，目的地までの通信経路を 3．2 の. シミュレーションに使用する各種パラメータを表１に. 手法で求めた時，その経路上に存在するノードである. 示す．車両台数 N 及び，幹線道路である Y 軸 300m の道路. こと．. における経路探索に用いる重みと，通行している車両数は. ＜その他条件＞. 可変とした．交通流シミュレーションでは，車両がランダ. . 配布回数は，ｎ回とする．. ムに出発地点と目的地を設定し，最短経路を走行する．ま. . DTN モードの中継車両から受信した車両は，基本的. た，各車両は 40～60 ㎞/h の速度で移動する．提案手法の. にはジオルーティングモードで転送する．もし，この. 評価に当たり，各車両が一定周期ごとに走行情報を基地局. 車両も転送にｋ回失敗した場合，DTN モードとなる．. に向けて送信するシナリオを用いる．今回のシミュレーシ. パケットはジオルーティングと DTN とを繰り返し. ョンでは基地局を図 6 の様に配置した．シミュレーション. て転送される可能性があるが，無限の繰返しを避ける. 結果の値としては，10 回の試行結果の平均値をデータとし. ために，DTN モードに入る回数に上限値を設ける．. て採用した．. . ⓒ2015 Information Processing Society of Japan. 4.

(5) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. 提案手法の GDRT の評価では SRS 手法をベースラインプ. 次に，図 8 に無線の到達範囲を狭くした条件での車両台. ロトコルとして比較評価を行う．評価指標にはノード数に. 数 N に対するパケット到着率の比較を示す．またこの時，. 対するパケット到着率の変化を用いる．パケット到着率は，. 無線到達範囲は 200m，幹線道路を走る車両数は同じく 50. 各車両が生成したソースパケット数に対する，基地局が受. 台とする．図 7 の条件より，無線の到達範囲が狭く，厳し. 信したパケット数の割合である．. い条件のため到着率は全体的に低下した．図 8 より，GDRT は SRS と比較してパケット到着率が最大で約 5％改善する. 表1. シミュレーションパラメータ. パラメータ. 値. 空間の広さ. 1000m×1000m. 交差点配置. 100m 間隔の格子. 幹線道路配置. X 軸と平行な道路が 1 本. ことができた．. （Y 軸方向に 300m，500m）幹線道路車両数. 50 台，80 台. 目標地点. （500m，0m）. 車両台数. 50 台，100 台，150 台，200 台. 車両移動モデル. ランダムウェイポイントモデル. 車両の速度. 最高 60km/h~最低 40km/h. パケット送信間隔. 1sec. 4.2 シミュレーション結果ここでは，幹線道路という密度を加えた道路網情報（図 6）における提案手法 GDRT の通信特性を評価する．パケット到着率と総パケット数の指標において，SRS 方式との比較. 図8. ノード数に対するパケット到着率の変化. 無線到達範囲：200m，幹線道路の Y 座標：300，幹線道路だけを走るノード数：50 次に，図 9 に幹線道路の位置を変更した条件での車両台数 N に対するパケット到着率の比較を示す．またこの時，無線到達範囲は 300m，幹線道路を走る車両数は同じく 50 台とする．幹線道路の Y 座標を 500m の位置とした．幹線. を行う．図 7 に道路網情報に密度を付与した地図における車両台数 N に対するパケット到着率の比較を示す．またこの時，無線到達範囲は 300m，幹線道路を走る車両は 50 台とした．. 道路の位置を下げることで，影響を受ける車両の数が減り到着率は全体的に下がった．図 9 より，GDRT は SRS と比較してパケット到着率が最大で約 15％増加している．. 図 7 より，GDRT は SRS と比較してパケット到着率が最大で約 10％増加している．. 図9. ノード数に対するパケット到着率の変化. 無線到達範囲：300m，幹線道路の Y 座標：500，図7. ノード数に対するパケット到着率の変化. 無線到達範囲：300m，幹線道路の Y 座標：300，幹線道路だけを走るノード数：50. 幹線道路だけを走るノード数：50 最後に，図 10 に幹線道路を走る車両を変更した条件での車両台数 N に対するパケット到着率の比較を示す．またこのとき，無線到達範囲は 300m，幹線道路を走る車両数を. ⓒ2015 Information Processing Society of Japan. 5.

(6) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2015-DPS-164 No.4 Vol.2015-EIP-69 No.4 2015/9/10. 80 台とする．また，幹線道路の Y 座標を 300m の位置とし. ることである．また，動的な再経路探索でもパケット転送. た．図 10 より，GDRT は SRS と比較してパケット到着率. を失敗した場合，DTN を利用することでも到着率の改善を. は向上している．しかし，図 7 と比較した場合，幹線道路. 目指していることである．DTN におけるデータ配布先の選. の車両密度を増やしたにも関わらず，到着率の向上はほと. 択条件としては，通信可能となった車両が，目的地までの. んど見られない．これは，到着率向上の効果が幹線道路内. 車両密度の高い経路上に存在することである．これら二つ. の車両数が 50 台で既に飽和していたとも考えられる．. の提案により，SRS での課題である低車両密度での通信において発生するトラフィックホールやデッドエンドを回避することができ，到着率の改善をする．提案手法の評価では，DTN の実装が時間的に間に合わなかったため，DTN を含まない結果となっている．現状の評価では，ほぼ全てのシミュレーションにおいて従来方式を上回る結果が出ている．しかし，実際の通信に用いるには，まだ十分な到着率が得られていない．今後の課題は，DTN を実装し，より高い到着率を達成すること，通信トラフィック量や到達遅延時間を詳細に評価することである．. 図 10. ノード数に対するパケット到着率の変化. 無線到達範囲：300ｍ，幹線道路の Y 座標：300，幹線道路だけを走るノード数：80 4.3 考察車両密度を考慮しない SRS と車両密度の高い幹線道路の情報を用いた GDRT では，幹線道路情報を用いた GDRT のほうがすべての条件で高い到着率を示した．特に，ノード数が小さい領域ほど、改善効果が高いことが分かる．ノード数が小さい場合，ノード密度が小さい領域が生じやすく，幹線道路情報を使わない SRS の場合デッドエンドに陥りやすいことが原因と考えられる．一方、ノード数が多くなると，ノード密度小さい領域が減少し，提案方式の改善効果はやや小さくなった．今回のシミュレーションは，DTN を実装していないため，到着率が十分改善されているとは言えない．より高い到着率を達成するには，DTN によって一時的にパケットを蓄積する必要がある．. 5.. 参考文献 1) 国土交通省:ITS ，入手先〈http://www．mlit．go．jp/road/ITS/j-html/〉 2) 赤松諒介，小原啓志，重野寛: 車両アドホックネットワークにおける道路網構造を考慮したジオルーティング手法，情報処理学会論文誌，Vol．56，No．2，pp．1-9 (2015)． 3) 鶴正人，内田真人，滝根哲哉，永田晃，松田崇弘，巳波弘佳，山村新也: “DTN 技術の現状と展望”，電子情報通信学会通信ソサイエティマガジン No16 [春]，pp．57-68 (2011)． 4) 河本美穂，重安哲也："被災情報の収集を目的とした DTN におけるメッセージ到着率の向上と冗長送信数の削減を実現する自律的中継手法の提案"，情報処理学会マルチメディア通信と分散処理ワークショップ，pp．269-278 (2014)． 5) 中村正人，木谷友哉，孫為華，柴田直樹，安本慶一，伊藤実： "各車両の予定経路情報を利用した車々間通信による情報取得手法の提案"，情報処理学会 ITS 研究会研究報告 2009-ITS-36，pp． 23-29 (2009)． 6) Chou，L．and Yang，Y．: Location-Based Directional Broadcast for Inter-Vehicle Communications，Proc．IEEE Vehicular Technology Conference (VTC 2010-Fall)，pp．1–5 (2010)． 7) Bachir，A．and Benslimane，A．: A multicast protocol in ad hoc networks: inter-vehicle geocast，Proc．IEEE Vehicular Technology Conference (VTC 2003-Spring)，pp．2456–2460 (2003)．. まとめ. 本論文では，ジオルーティングと通信環境が劣悪な場合有効な DTN のハイブリッド型ルーティング方式として GDRT を提案した．従来研究の一つに道路トポロジに基づいた通信経路算出と，中継車両による動的経路修復により，通信量の増加を抑制しつつパケット到達性を改善する SRS という手法が提案されている．しかし，低車両密度では，十分な到着率が得られないという課題があった．GDRT は，その SRS の車両密度が低い場合の到着率低下を改善することを目的としている．提案手法の大きな特徴としては，道路網情報内の車両密度が推定できることを前提に，車両密度が高い経路を優先的に選択することで到着率を改善す. ⓒ2015 Information Processing Society of Japan. 6.

(7)