図面 (/)

技術 車両ネットワークにおけるゾーンベースの密度認知パケット転送

出願人 ウニヴェルシダージドポルトカーネギーメロンユニバーシティ
発明者 ジョアンフランシスココルデイロドオリヴェイラバロスルイマニュエルパチェコメイレレスピーターアルフォンスロナルドスティーンキスト
出願日 2013年9月30日 (5年10ヶ月経過) 出願番号 2015-540233
公開日 2016年2月12日 (3年6ヶ月経過) 公開番号 2016-504787
状態 特許登録済
技術分野 移動無線通信システム
主要キーワード 部分接続 本解決策 正方形エリア 空間セル 可変ノード 空間経路 データ収集ノード ゾーンベース
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年2月12日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題・解決手段

車両間アドホックネットワークにおけるデータパケットマルチホップ転送のための方法を開示する。各ノードは、自身と送信先の両方の地理的座標を知る。ワンホップネイバー座標は、周期的なブロードキャスト協調認識メッセージ(Cooperative Awareness Messages (CAMs))から得られる。方法は、パケットを受信するにあたり各ノードによって実行される、以下の分散連携方式を含む。1)候補となるフォワーダの組を計算する。2)有用性メトリックに従って候補となるフォワーダを順位付ける。3)トップの順位であれば、順位に比例した時間の周期後にパケットを転送し、そうでなければパケットを落とす。フォワーダを順位付けるために用いる基本的な有用性メトリックは、送信先までの距離の逆数である。さらに、このメトリックが、送信先に到達するパケット送信予想数の逆数に置きかえられるような拡張も開示する。後者のメトリックは、ネットワーク内のノードによって協調的に収集される空間接性情報に基づいて計算される。

概要

背景

本発明は、無線ネットワークの分野におけるいくつかの重要な結果に基づく。第一は、車両ネットワークが、既存の車両プロトコル対処していない問題であるグレーゾーン現象を受けるという観測である。第二として、不信頼性チャネルに適時的に取り組むために無線ダイバーシティを用いることができるというアイデアが、WLAN及びメッシュネットワークの面から提案されたが、車両ネットワーク面では提案されていない。

VANETでの部分的な接続性に大きなグレーゾーンが存在することは、Baiらによって初めて指摘された[3]。彼らの実験では、20%から80%の中間パケット配送レートを有する確率が50%になるということが分かった。

Kaulらは、車両の異なる部分に配置したアンテナを使用して、多重無線ダイバーシティの効果を検討した[17]。彼らの実験では、第二の無線装置を付加することで10‐15%のパケットエラーレートの減少を報告した。アンテナが互いに近接して配置されたとすれば、これが、車両環境での無線ダイバーシティの利益に対する下限になると思われる。

ほとんどのVANETルーティングプロトコルは、ダイバーシティを用いない。代わりに、中継選択に用いるメトリックがほとんど異なるように、ホップ毎に単一の中継を選択するという、ネイバーベース方策焦点をあてる。GPSR[10]、A−STAR[4]、及びGytar[5]では、送信先に最も近いネイバーを選択するが、VANETに存在するグレーゾーン現象を与える、リスクを伴う選択である。ACAR[12]は、エンドツーエンドエラー確率を最小化しようとする、修正された予想送信カウント(Expected Transmission Count (ETX))メトリック[18]を用いる。これは良い改良ではあるが、それでも単一障害点を有する。

BLR[19]及びCBF[20]は、受信サイド転送決定を行う2つのVANETプロトコルである。しかしながら、レプリケーションの影響を受けやすく、高密度環境で競合を減らすために、フォワーダの数を制限できない。DOT[21]は、優先度付け確立するが、フォワーダの数を制限しない。

ダイバーシティは、以前は、ロスを回復するために他の競合に対して用いられていた。多重無線ダイバーシティ(Multi-Radio Diversity (MDR))[8]は、WLANに対するローレベルの方式であり、様々なAPで受信する誤りフレーム中心ノードで合わされて、多数の誤りコピーから正しいフレームを抽出しようと試みる。この方式は、中心ノードに共有されるチャネルを必要とし、車両使用に対しては不適切である。

適時的なルーティングはまた、最も有名なプロトコルであるExOR[6]及びMORE[22]を用いたメッシュネットワークの面からも探究されてきた。両者は、多数の中継を用いることでダイバーシティに影響を与え、ネイバーの組ごとの間でチャネル品質に関するネットワークワイドな知識を仮定し、その知識はメッシュネットワークに対しては合理的であるがVANETでは成り立たない。

PRO[7]は、インフラストラクチャWLANに対する分散適時方式である。PROでは、送信が失敗する時、送信先に向けて良いRSSIを有する中継が、送信源に代わって適時的にパケット再送信し、信頼性を高める。PROは、全ての送信源及び送信先の間でRSSIを判断するノードを必要とする。これは、WLANでは可能であるが、VANETの全ノードはセンダ及びレシーバとなる可能性があり、その上、チャネルが非常に動的である。代わりに、DAZLはRSSIというよりもむしろ距離に基づいて中継を順位付けする。

候補となる送信機の数を減らして、MAC層競合を避けるアイデアは、ブロードキャストストーム問題[23]への解決策として最初に出された。SAPF[24]及びP−パーシステンス[25]のようないくつかの方式は、優先度付けなしに、フォワーダの数を制御するための単純で確率的なルールを用いる。時間上にフォワーダを広げるためのスロッティングが、Lindaらによって紹介され[26]、その後スロットされたp−パーシステンス(Slotted p-persistence)[25]に用いられた。これらのアプローチでは、スロットの定数を使用し、従って、異なるノード密度に適用できない。作業負荷及び密度に基づいた適応なスロッティングが、802.11pとは互換性のない、いくつかのTDMAベースのMACプロトコル[27][28]で提案された。

概要

車両間アドホックネットワークにおけるデータパケットマルチホップ転送のための方法を開示する。各ノードは、自身と送信先の両方の地理的座標を知る。ワンホップネイバー座標は、周期的なブロードキャスト協調認識メッセージ(Cooperative Awareness Messages (CAMs))から得られる。方法は、パケットを受信するにあたり各ノードによって実行される、以下の分散連携方式を含む。1)候補となるフォワーダの組を計算する。2)有用性メトリックに従って候補となるフォワーダを順位付ける。3)トップの順位であれば、順位に比例した時間の周期後にパケットを転送し、そうでなければパケットを落とす。フォワーダを順位付けるために用いる基本的な有用性メトリックは、送信先までの距離の逆数である。さらに、このメトリックが、送信先に到達するパケット送信予想数の逆数に置きかえられるような拡張も開示する。後者のメトリックは、ネットワーク内のノードによって協調的に収集される空間接性情報に基づいて計算される。

目的

セルラーが、時折選択肢となることもあるが、車両ネットワークは、レイテンシ帯域、及びコストの点から利点をもたらし、効率的なマルチホップ通信を重要課題とする

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ノード間の車両通信に対する、地理的座標に基づく分散マルチホップパケット転送のための方法であり、各ノードは自身の地理的座標と、1つの前記車両通信の送信先ノードの地理的座標とを有し、前記方法は、各ノードがネイバーノードからの周期的なブロードキャストビーコンからワンホップの前記ネイバーノードの座標を得るステップを含み、前記方法は、各ホップで各ノードがパケットを受信すると、自ノードの位置及び前記パケットのヘッダ情報に基づき、前記自ノードが先行ホップよりも前記送信先に近いかどうかを確かめ、そうでなければ、前記パケットを落とすステップと、前記先行ホップよりも前記送信先に近いワンホップの前記ネイバーノードである潜在的なフォワーダノードの有用性に対して、前記自ノードの前記フォワーダとしての有用性を順位付けするステップと、前記自ノードが、ベストな有用性で順位付けされた予め設定された数のフォワーダノードのうちの1つであれば、前記自ノードが転送ゾーンにあると判断し、そうでなければ、前記パケットを落とすステップと、前記自ノードが前記転送ゾーンにある場合、前記パケットを転送する前に、前記自ノードの有用性順位に反比例する時間の周期だけ待機するステップと、待機中、前記自ノードが、同じ前記パケットを転送する他のノードを漏れ聞く場合、前記パケットの前記転送を中止するステップと、を含み、前記パケットヘッダは、元のパケット送信源、パケット送信先、及びパケットの先行ホップの3つのノードアドレスを含み、各アドレスは、それぞれのノード識別子及び地理的座標の両方を含み、前記ノードは、車両ノード又は車両ノード及び固定ノードの混合である、方法。

請求項2

各ノードが、自身のパケットの転送によって、前記パケットの送信があったことを前記先行ホップノードに対して通知するステップをさらに含む、請求項1に記載の方法。

請求項3

各ノードが、予め設定された制限時間の後パケットの通知を受信しなかった場合、前記パケットを再送信するステップをさらに含む、請求項1及び2に記載の方法。

請求項4

各ノードが漏れ聞いたパケットの履歴を保持し、前記履歴に存在する場合、パケットを落とすステップをさらに含む、請求項1乃至3に記載の方法。

請求項5

パケット受信後、複数の転送スロットに時間を分割することで、ネットワーク層で転送スロッティングを導入するステップを含み、潜在的な前記フォワーダノードは、明示的な連携なしに、前記スロットにわたって、送信のために自身を分散させ、各ノードは、1つのスロットにのみ割り当てられ、各スロットは、0以上のノードを有し、スロット間隔は十分に長く、異なる転送スロットにあるノードが、コンテンションウィンドウオーバーラップする場合に、MACレベル競合せず、前記スロット間隔は、レイテンシが軽減するほど十分に短く、特に、前記スロット間隔は、MAC層の平均コンテンションウィンドウより長いが、それほどより長くはない、請求項1乃至4に記載の方法。

請求項6

自ノードの潜在的なフォワーダとしての前記有用性を順位付けし、前記自ノードが前記転送ゾーンにあるかどうか判断し、前記自ノードの有用性順位に反比例する時間の周期だけ待機するために、各ホップ及び各パケットに対し各潜在的なフォワーダノードが、現パケットに対して潜在的なフォワーダの前記ノードの組を定義し、前記組は、前記先行ホップよりも前記送信先ノードに近く、前記自ノードの無線範囲内にある前記ノードから構成されるステップと、前記組からアレー構築し、前記送信先ノードに最も近い前記ノードから前記送信先ノードから最も遠い前記ノードの順で、前記アレーをソートするステップと、ノードがフォワーダとしての有用性順位である前記アレーに現れる前記インデックスを判断するステップと、前記組にある各ノードに対して、予め設定されたスロット毎のノードの数で割った、前記ノードの有用性順位の分割数以上の最小整数の値によって計算される転送スロットに割り当てるステップと、を含み、前記ノードが、ベストな有用性順位を付けた、予め設定された数のフォワーダノードのうちの1つではない場合、各ノードは転送を控える、請求項5に記載の方法。

請求項7

ベストな有用性順位を付けたフォワーダノードの前記予め設定された数は、5以下、10以下、又は15以下である、請求項1乃至6に記載の方法。

請求項8

前記送信先ノードは、地理的座標の先行知識又は位置特定サービスを通じて、地理的座標により位置指定可能である、請求項1乃至7に記載の方法。

請求項9

前記ノードのフォワーダとしての前記有用性を順位付けするステップは、前記送信先までの距離、特にホップ長距離によって順位付けするステップを含む、請求項1乃至8に記載の方法。

請求項10

前記ノードのフォワーダとしての前記有用性を順位付けするステップは、収集され、統合され、及び分散される空間接性情報に基づいて、前記ノードのフォワーダとしての前記有用性を順位付けするステップを含み、各ノードは、時間の一周期又は複数周期にわたって、自身の位置に関する情報及び他のノードから受信した協調認識メッセージ(Cooperative Awareness Messages (CAMs))を記録するステップと、各ノードは、CAMデータ記録を空間接続性サーバーアップロードし、前記CAMデータ記録は、収集された前記CAMを送った前記ノードの各々の前記地理的座標と、随意に前記CAMのRSSIを含むステップと、前記空間接続性サーバーが、ノードは地理的な位置であり、エッジは空間リンクである、前記ノード及び前記エッジを含む空間接続性グラフに、前記CAMデータ記録を統合、処理するステップであって、各空間リンクは、2つの地理的な位置間の接続であり、1)予想パケット配送レート、2)利用可能であれば、予想平均受信信号強度(Received Signal Strength (RSSI))、及び3)前記接続された位置にある車両の存在確率という3つの品質メトリックのうち1つ以上を含む、前記ステップと、各ノードが、前記空間接続性サーバーから前記空間接続性グラフをダウンロードするステップと、前記空間接続性グラフを、ノードのフォワーダとしての前記有用性を順位付けするために用いるステップと、を含み、前記有用性は、自ノードと前記送信先ノード間のグラフ経路の最小予想パケット送信カウントであるか、又は、前記有用性は、前記自ノードと前記送信先ノード間の前記グラフ経路の最大予想平均受信信号強度(Received Signal Strength (RSSI))であるか、又は、前記有用性は、前記自ノードと前記送信先ノード間の前記グラフ経路にある車両の最大予想存在確率である、請求項1乃至9に記載の方法。

請求項11

各ノードが、エッジが2つの地理的な位置間の接続である空間リンクであり、前もって統合、処理された前記空間接続性グラフの前記エッジの前記品質メトリックを、前記2つの地理的な位置間の前記接続を利用可能である時の、前記エッジの前記品質メトリックのリアルタイムに収集されるデータと、置きかえるステップを含む、請求項10に記載の方法。

請求項12

地理的な位置は、予め設定された固定又は可変サイズ空間セルである、請求項10又は11に記載の方法。

請求項13

前記空間セルは、四角形エリア、特に正方形エリア、特に50m四方の正方形エリアである、請求項12に記載の方法。

請求項14

ノードのフォワーダとしての前記有用性は、前記空間接続性グラフに基づいて計算され、前記自ノード及び送信先ノードの位置の両方を、前記空間接続性グラフの送信源及び送信先空間セルにマッピングするステップと、送信源セルから、送信源ノードから各潜在的なフォワーダに対する送信先ノードまでの最小予想送信総数を有する送信先セルまでの前記経路を、前記品質メトリックとして前記グラフの各空間リンクと関連付けられる前記パケット配送レートを用いて、計算するステップと、送信源ノードから、各潜在的なフォワーダに対して前もって計算された前記経路の送信先ノードまでの最小予想送信総数に従って潜在的なフォワーダの前記アレーをソートするステップと、を含む、請求項11又は12に記載の方法。

請求項15

各ノードが、前記グラフの前記エッジにある隣接する地理的な位置の各組の間で前記パケットを配送するために必要となる予想送信数を、利用可能な時の、隣接する地理的な位置の各組に対してリアルタイムに収集されるデータと置きかえるステップを含む、請求項14に記載の方法。

請求項16

前記CAMデータ記録の各々は、循環する各時間の周期に対して、タイムスタンプ、前記自ノード自身の地理的な位置、前記自ノードによって送信されたCAMの数、前記自ノードによって受信された前記CAMを送った前記ノードのノードID、及び前記自ノードによって受信された前記CAMの数及び平均RSSIを含む、請求項10乃至14に記載の方法。

請求項17

ノード間の車両通信に対する地理的座標に基づく分散マルチホップパケット転送のための装置であって、各ノードが請求項1乃至16のうち任意の1つの請求項の前記方法を実行するために構成されるデータ処理モジュールを備える地理的座標モジュールを備える、装置。

請求項18

プログラムデータプロセッサ上で走る時、請求項1乃至15のうち任意の請求項の前記方法を実行するために適用される前記コンピュータプログラム命令を有する、コンピュータ可読データ搬送体

技術分野

0001

本発明は、データスイッチングネットワークによるデジタル情報の送信、特にデータスイッチングネットワーク、ストアアンドフォワードスイッチングシステム、又はパケットスイッチングシステムでのルーティング又はパケット経路探索に関する。

背景技術

0002

本発明は、無線ネットワークの分野におけるいくつかの重要な結果に基づく。第一は、車両ネットワークが、既存の車両プロトコル対処していない問題であるグレーゾーン現象を受けるという観測である。第二として、不信頼性チャネルに適時的に取り組むために無線ダイバーシティを用いることができるというアイデアが、WLAN及びメッシュネットワークの面から提案されたが、車両ネットワーク面では提案されていない。

0003

VANETでの部分的な接続性に大きなグレーゾーンが存在することは、Baiらによって初めて指摘された[3]。彼らの実験では、20%から80%の中間パケット配送レートを有する確率が50%になるということが分かった。

0004

Kaulらは、車両の異なる部分に配置したアンテナを使用して、多重無線ダイバーシティの効果を検討した[17]。彼らの実験では、第二の無線装置を付加することで10‐15%のパケットエラーレートの減少を報告した。アンテナが互いに近接して配置されたとすれば、これが、車両環境での無線ダイバーシティの利益に対する下限になると思われる。

0005

ほとんどのVANETルーティングプロトコルは、ダイバーシティを用いない。代わりに、中継選択に用いるメトリックがほとんど異なるように、ホップ毎に単一の中継を選択するという、ネイバーベース方策焦点をあてる。GPSR[10]、A−STAR[4]、及びGytar[5]では、送信先に最も近いネイバーを選択するが、VANETに存在するグレーゾーン現象を与える、リスクを伴う選択である。ACAR[12]は、エンドツーエンドエラー確率を最小化しようとする、修正された予想送信カウント(Expected Transmission Count (ETX))メトリック[18]を用いる。これは良い改良ではあるが、それでも単一障害点を有する。

0006

BLR[19]及びCBF[20]は、受信サイド転送決定を行う2つのVANETプロトコルである。しかしながら、レプリケーションの影響を受けやすく、高密度環境で競合を減らすために、フォワーダの数を制限できない。DOT[21]は、優先度付け確立するが、フォワーダの数を制限しない。

0007

ダイバーシティは、以前は、ロスを回復するために他の競合に対して用いられていた。多重無線ダイバーシティ(Multi-Radio Diversity (MDR))[8]は、WLANに対するローレベルの方式であり、様々なAPで受信する誤りフレーム中心ノードで合わされて、多数の誤りコピーから正しいフレームを抽出しようと試みる。この方式は、中心ノードに共有されるチャネルを必要とし、車両使用に対しては不適切である。

0008

適時的なルーティングはまた、最も有名なプロトコルであるExOR[6]及びMORE[22]を用いたメッシュネットワークの面からも探究されてきた。両者は、多数の中継を用いることでダイバーシティに影響を与え、ネイバーの組ごとの間でチャネル品質に関するネットワークワイドな知識を仮定し、その知識はメッシュネットワークに対しては合理的であるがVANETでは成り立たない。

0009

PRO[7]は、インフラストラクチャWLANに対する分散適時方式である。PROでは、送信が失敗する時、送信先に向けて良いRSSIを有する中継が、送信源に代わって適時的にパケットを再送信し、信頼性を高める。PROは、全ての送信源及び送信先の間でRSSIを判断するノードを必要とする。これは、WLANでは可能であるが、VANETの全ノードはセンダ及びレシーバとなる可能性があり、その上、チャネルが非常に動的である。代わりに、DAZLはRSSIというよりもむしろ距離に基づいて中継を順位付けする。

0010

候補となる送信機の数を減らして、MAC層競合を避けるアイデアは、ブロードキャストストーム問題[23]への解決策として最初に出された。SAPF[24]及びP−パーシステンス[25]のようないくつかの方式は、優先度付けなしに、フォワーダの数を制御するための単純で確率的なルールを用いる。時間上にフォワーダを広げるためのスロッティングが、Lindaらによって紹介され[26]、その後スロットされたp−パーシステンス(Slotted p-persistence)[25]に用いられた。これらのアプローチでは、スロットの定数を使用し、従って、異なるノード密度に適用できない。作業負荷及び密度に基づいた適応なスロッティングが、802.11pとは互換性のない、いくつかのTDMAベースのMACプロトコル[27][28]で提案された。

先行技術

0011

F. Bai, H. Krishnan, V. Sadekar, G. Holl, and T. Elbatt, "Towardscharacterizing and classifying communication-based automotive applications from a wireless networking perspective," in Proceedings ofIEEE Workshop on Automotive Networking and Applications (AutoNet), 2006.
R. Meireles, M. Boban, P. Steenkiste, 0. Tonguz, and J. Barros, "Experimental study on the impact of vehicular obstructions in vanets," in Vehicular Networking Conference (VNC), 2010 IEEE, 2010.
F. Bai, D. D. Stancil, and H. Krishnan, "Toward understanding characteristics of dedicated short range communications (dsrc) from a perspective of vehicular network engineers," in Proceedings of the 16th annual international conference on Mobile computing and networking, ser. MobiCom '10.ACM, 2010.
B.-C. Seet, G. Liu, B.-S. Lee, C.-H. Foh, K.-J. Wong, and K.-K. Lee, "A-star: A mobile ad hoc routing strategy for metropolis vehicular communications," in NETWORKING 2004., ser. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2004, vol. 3042.
M. Jerbi, S.-M. Senouci, R. Meraihi, and Y. Ghamri-Doudane, "An improved vehicular ad hoc routing protocol for city environments," Communications, ICC 07'. IEEE International Conference on, 2007.
S. Biswas and R. Morris, "ExOR: opportunistic multi-hop routing for wireless networks," Computer Communication Review, vol. 35, no. 4, 2005.
M.-H. Lu, P. Steenkiste, and T. Chen, "Design, implementation and evaluation of an efficient opportunistic retransmission protocol," in Proceedings of the 15th annual international conference on Mobile computing and networking, ser. MobiCom '09. ACM, 2009.
A. Miu, H. Balakrishnan, and C. E. Koksal, "Improving loss resilience with multi-radio diversity in wireless networks," in Proceedings of the 11th annual international conference on Mobile computing and networking, ser. MobiCom '05. ACM, 2005.
D. B. Johnson and D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," in Mobile Computing. Kluwer Academic Publishers, 1996.
B. Karp and H. T. Kung, "Gpsr: Greedy perimeter stateless routing for wireless networks," in Mobile Computing and Networking, 2000.
F. Bai and B. Krishnamachari, "Spatio-temporal variations of vehicle traffic in vanets: facts and implications," 2009.
Q. Yang, A. Lim, S. Li, J. Fang, and P. Agrawal, "Acar: Adaptive connectivity aware routing for vehicular ad hoc networks in city scenarios," Mobile Networks and Applications, vol. 15, 2010.
A. Festag, R. Baldessari, W. Zhang, L. Le, A. Sarma, and M. Fukukawa, "Car-2-x communication for safety and infotainment in europe,"NECTechnical Journal, vol. 3, no. 1, 2008.
CAR-2-CAR Communication Consortium, "Manifesto - Overview of the C2C-CC system," 2007.
J. Li, J. Jannotti, D. De Couto, D. Karger, and R. Morris, "A scalable location service for geographic ad hoc routing," in Proceedings of the 6thannual international conference on Mobile computing and networking, ser. MobiCom '00. ACM, 2000.
J. S. Otto, F. E. Bustamante, and R. A. Berry, "Down the block and around the corner - the impact of radio propagation on inter-vehicle wireless communication," in Proc. of IEEE International Conference on Distributed Computing Systems (ICDCS), 2009.
S. Kaul, K. Ramachandran, P. Shankar, S. Oh, M. Gruteser, I. Seskar, and T. Nadeem, "Effect of antenna placement and diversity on vehicular network communications," in Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON '07. 4th Annual IEEE Communications Society Conference on, 2007.
D. Couto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless routing," Wireless Networks, vol. 11, no. 4, 2005.
M. Heissenbuttel, T. Braun, T. Bernoulli, and M. Walchli, "Blr: Beaconless routing algorithm for mobile ad-hoc networks," Elseviers Computer Communications Journal (Special Issue), vol. 27, 2003.
H. Fusler, J. Widmer, M. Kasemann, M. Mauve, and H. Hartenstein, "Contention- based forwarding for mobile ad hoc networks," Ad Hoc Networks, vol. 1, no. 4, 2003.
R. S. Schwartz, K. Das, H. Scholten, and P. Havinga, "Exploiting beacons for scalable broadcast data dissemination in vanets," in Proceedings of the 9th ACM international workshop on Vehicular inter-networking, systems, and applications, ser. VANET '12. ACM, 2012.
S. Chachulski, M. Jennings, S. Katti, and D. Katabi, "Trading structure for randomness in wireless opportunistic routing," in Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, 2007.
S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J. -P. Sheu, "The broadcast storm problem in a mobile ad hoc network," in Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, ser. MobiCom '99. ACM, 1999.
Y. Mylonas, M. Lestas, and A. Pitsillides, "Speed adaptive probabilistic flooding in cooperative emergency warning," in Proceedings of the 4th Annual International Conference on Wireless Internet, ser. WICON '08. ICST, 2008.
N. Wisitpongphan, O. Tonguz, J. Parikh, P. Mudalige, F. Bai, and V. Sadekar, "Broadcast storm mitigation techniques in vehicular ad hoc networks," Wireless Communications, IEEE, vol. 14, no. 6, 2007.
L. Briesemeister, "Group membership and communication in highly mobile ad hoc networks," Ph.D. dissertation, Technischen Universitat Berlin, 2001.
W. Li, J.-B. Wei, and S. Wang, "An evolutionary-dynamic tdma slot assignment protocol for ad hoc networks," in Wireless Communications and Networking Conference, 2007.WCNC2007. IEEE, 2007.
S. Kamruzzaman and M. Alam, "Dynamic tdma slot reservation protocol for cognitive radio ad hoc networks," in Computer and Information Technology (ICCIT), 2010 13th International Conference on, 2010.

課題を解決するための手段

0012

地理的な領域にある任意のノードが送信先に向けてパケットを転送できる、ゾーンベース転送方式、ここで言うDAZLを示す。プロトコルは、完全に分散型であり、局所情報のみに依存する。従来のネイバーベースのプロトコルと対照的に、ゾーンベースの転送は、車両ネットワークで露見する予測できないパケット配送レートに対して転送をロバストにする内在した冗長性を有する。高密度のシナリオで競合を減らすために、本開示は、局所ノード密度に従った転送ゾーンのサイズを適用するスロットベースアルゴリズムを用いる。さらに、ホップ長最大化するために、フォワーダを優先度付けする。このアプローチにより、高スループット低レイテンシ及びレプリケーションの間の良いバランスを得る。

0013

実験とシミュレーションの両方を用いて、本開示を評価する。スループットでおよそ60%の改善とともに、全てのノード密度に対してネイバーベースの方式よりも性能が優れていることが分かった。さらに、スループットは、実際問題としては実行することはできないものであり、パケットを受信し、失うことを知っている管理者プロトコルで達成できるスループットの90%にまで至る。

0014

本開示は、ノード間の車両通信に対する、地理的座標に基づく分散マルチホップパケット転送のための方法であり、各ノードは自身の地理的座標と、1つの前記車両通信の送信先ノードの地理的座標とを有し、前記方法は、各ノードがネイバーノードからの周期的なブロードキャストビーコンからワンホップの前記ネイバーノードの座標を得るステップを含み、前記方法は、各ホップで各ノードがパケットを受信すると、
自ノードの位置及び前記パケットのヘッダ情報に基づき、前記自ノードが先行ホップよりも前記送信先に近いかどうかを確かめ、そうでなければ、前記パケットを落とすステップと、
前記先行ホップよりも前記送信先に近いワンホップの前記ネイバーノードである潜在的なフォワーダノードの有用性に対して、前記自ノードの前記フォワーダとしての有用性を順位付けするステップと、
前記自ノードが、ベストな有用性で順位付けされた予め設定された数のフォワーダノードのうちの1つであれば、前記自ノードが転送ゾーンにあると判断し、そうでなければ、前記パケットを落とすステップと、
前記自ノードが前記転送ゾーンにある場合、前記パケットを転送する前に、前記自ノードの有用性順位に反比例する時間の周期だけ待機するステップと、
待機中、前記自ノードが、同じ前記パケットを転送する他のノードを漏れ聞く場合、前記パケットの前記転送を中止するステップと、を含み、
前記パケットヘッダは、元のパケット送信源、パケット送信先、及びパケットの先行ホップの3つのノードアドレスを含み、
アドレスは、それぞれのノード識別子及び地理的座標の両方を含み、
前記ノードは、車両ノード又は車両ノード及び固定ノードの混合である、
方法を含む。

0015

実施形態は、各ノードが、自身のパケットの転送によって、前記パケットの送信があったことを前記先行ホップノードに対して通知するステップを含む。

0016

実施形態は、各ノードが、予め設定された制限時間の後パケットの通知を受信しなかった場合、前記パケットを再送信するステップを含む。

0017

実施形態は、各ノードが漏れ聞いたパケットの履歴を保持し、前記履歴に存在する場合、パケットを落とすステップを含む。

0018

実施形態は、パケット受信後、複数の転送スロットに時間を分割することで、ネットワーク層で転送スロッティングを導入するステップを含み、
潜在的な前記フォワーダノードは、明示的な連携なしに、前記スロットにわたって、送信のために自身を分散させ、各ノードは、1つのスロットにのみ割り当てられ、各スロットは、0以上のノードを有し、
スロット間隔は十分に長く、異なる転送スロットにあるノードが、コンテンションウィンドウオーバーラップする場合に、MACレベルで競合せず、前記スロット間隔は、レイテンシが軽減するほど十分に短く、特に、前記スロット間隔は、MAC層の平均コンテンションウィンドウより長いが、それほどより長くはない。

0019

実施形態は、自ノードの潜在的なフォワーダとしての前記有用性を順位付けし、前記自ノードが前記転送ゾーンにあるかどうか判断し、前記自ノードの有用性順位に反比例する時間の周期だけ待機するために、各ホップ及び各パケットに対し各潜在的なフォワーダノードが、
現パケットに対して潜在的なフォワーダの前記ノードの組を定義し、前記組は、前記先行ホップよりも前記送信先ノードに近く、前記自ノードの無線範囲内にある前記ノードから構成されるステップと、
前記組からアレー構築し、前記送信先ノードに最も近い前記ノードから前記送信先ノードから最も遠い前記ノードの順で、前記アレーをソートするステップと、
ノードがフォワーダとしての有用性順位である前記アレーに現れる前記インデックスを判断するステップと、
前記組にある各ノードに対して、予め設定されたスロット毎のノードの数で割った、前記ノードの有用性順位の分割数以上の最小整数の値によって計算される転送スロットに割り当てるステップと、を含み、
前記ノードが、ベストな有用性順位を付けた、予め設定された数のフォワーダノードのうちの1つではない場合、各ノードは転送を控える。

0020

実施形態では、ベストな有用性順位を付けたフォワーダノードの前記予め設定された数は、5以下、10以下、又は15以下である。

0021

実施形態では、前記送信先ノードは、地理的座標の先行知識又は位置特定サービスを通じて、地理的座標により位置指定可能である。

0022

実施形態では、前記ノードのフォワーダとしての前記有用性を順位付けするステップは、前記送信先までの距離、特にホップ長距離によって順位付けするステップを含む。

0023

実施形態では、前記ノードのフォワーダとしての前記有用性を順位付けするステップは、収集され、統合され、及び分散される空間接性情報に基づいて、前記ノードのフォワーダとしての前記有用性を順位付けするステップを含み、
各ノードは、時間の一周期又は複数周期にわたって、自身の位置に関する情報及び他のノードから受信した協調認識メッセージ(Cooperative Awareness Messages (CAMs))を記録するステップと、
各ノードは、CAMデータ記録を空間接続性サーバーアップロードし、前記CAMデータ記録は、収集された前記CAMを送った前記ノードの各々の前記地理的座標と、随意に前記CAMのRSSIを含むステップと、
前記空間接続性サーバーが、ノードは地理的な位置であり、エッジは空間リンクである、前記ノード及び前記エッジを含む空間接続性グラフに、前記CAMデータ記録を統合、処理するステップであって、各空間リンクは、2つの地理的な位置間の接続であり、1)予想パケット配送レート、2)利用可能であれば、予想平均受信信号強度(Received Signal Strength (RSSI))、及び3)前記接続された位置にある車両の存在確率という3つの品質メトリックのうち1つ以上を含む、前記ステップと、
各ノードが、前記空間接続性サーバーから前記空間接続性グラフをダウンロードするステップと、
前記空間接続性グラフを、ノードのフォワーダとしての前記有用性を順位付けするために用いるステップと、を含み、
前記有用性は、自ノードと前記送信先ノード間のグラフ経路の最小予想パケット送信カウントであるか、又は、前記有用性は、前記自ノードと前記送信先ノード間の前記グラフ経路の最大予想平均受信信号強度(Received Signal Strength (RSSI))であるか、又は、前記有用性は、前記自ノードと前記送信先ノード間の前記グラフ経路にある車両の最大予想存在確率である。

0024

実施形態は、各ノードが、エッジが2つの地理的な位置間の接続である空間リンクであり、前もって統合、処理された前記空間接続性グラフの前記エッジの前記品質メトリックを、前記2つの地理的な位置間の前記接続を利用可能である時の、前記エッジの前記品質メトリックのリアルタイムに収集されるデータと、置きかえるステップを含む。

0025

実施形態では、地理的な位置は、予め設定された固定又は可変サイズ空間セルである。

0026

実施形態では、前記空間セルは、四角形エリア、特に正方形エリア、特に50m四方の正方形エリアである。

0027

実施形態では、ノードのフォワーダとしての前記有用性は、前記空間接続性グラフに基づいて計算され、
前記自ノード及び送信先ノードの位置の両方を、前記空間接続性グラフの送信源及び送信先空間セルにマッピングするステップと、
送信源セルから、送信源ノードから各潜在的なフォワーダに対する送信先ノードまでの最小予想送信総数を有する送信先セルまでの前記経路を、前記品質メトリックとして前記グラフの各空間リンクと関連付けられる前記パケット配送レートを用いて、計算するステップと、
送信源ノードから、各潜在的なフォワーダに対して前もって計算された前記経路の送信先ノードまでの最小予想送信総数に従って潜在的なフォワーダの前記アレーをソートするステップと、を含む。

0028

実施形態は、各ノードが、前記グラフの前記エッジにある地理的な位置の各組の間で前記パケットを配送するために必要となる予想送信数を、利用可能な時の、地理的な位置の各組に対してリアルタイムに収集されるデータと置きかえるステップを含む。

0029

実施形態では、前記CAMデータ記録は、循環する各時間の周期に対して、タイムスタンプ、前記自ノード自身の地理的な位置、前記自ノードによって送信されたCAMの数、前記自ノードによって受信された前記CAMを送った前記ノードのノードID、及び前記自ノードによって受信された前記CAMの数及び平均RSSIを含む。

0030

本開示はまた、ノード間の車両通信に対する地理的座標に基づく分散マルチホップパケット転送のための装置であって、各ノードが上記の方法のうちの任意を実行するために構成されるデータ処理モジュールを備える地理的座標モジュールを備える、
装置も含む。

0031

本開示はまた、プログラムデータプロセッサ上で走る時、上記の方法のうちの任意を実行するために適用される前記コンピュータプログラム命令を有する、
コンピュータ可読データ搬送体も含む。

0032

以下の図は、説明を図示するための好ましい実施形態を提供し、発明の範囲を限定するものとして、以下の図を見るべきではない。

図面の簡単な説明

0033

既存のネイバーベースの転送の提案を示す。これらは、リンク不安定性として対処すべき障害及び可変なノード密度を有する。
転送が所定のノードというよりはむしろ地理的ゾーンに基づく、提案した実施形態を表す。
実験データからの計算によって、チャネル変動性を克服するための方法として、車両ダイバーシティの重要性を示す。多数のレシーバを合わせることで、よりずっと良い性能が得られることを示す。単一のレシーバのパケット配送レート(Packet Delivery Rate (PDR))を表す。
実験データからの計算によって、チャネル変動性を克服するための方法として、車両ダイバーシティの重要性を示す。多数のレシーバを合わせることで、よりずっと良い性能が得られることを示す。3つのレシーバの合わさったPDRを表す。
実験データからの計算によって、チャネル変動性を克服するための方法として、車両ダイバーシティの重要性を示す。多数のレシーバを合わせることで、よりずっと良い性能が得られることを示す。様々なレシーバの組合せに対する平均PDRを表す。
実験データからの計算によって、チャネル変動性を克服するための方法として、車両ダイバーシティの重要性を示す。多数のレシーバを合わせることで、よりずっと良い性能が得られることを示す。付加的なレシーバから得られるダイバーシティ利得を表す。
スロッティングが、チャネル競合を制御するために、位置に従って時間上で潜在的なフォワーダをどのように広げるかを表す。
実施形態の実験的な評価に用いた2ホップネットワークトポロジー
提案した実施形態の実験結果。スループット。
提案した実施形態の実験結果。エンドツーエンドのレイテンシ。
提案した実施形態の実験結果。送信先で観測される複製の数。
提案した実施形態の実験結果。中継ダイバーシティ。
提案した実施形態のシミュレーション結果。スループット。
提案した実施形態のシミュレーション結果。エンドツーエンドのレイテンシ。
提案した実施形態のシミュレーション結果。送信先で観測される複製の数。
提案した実施形態のシミュレーション結果。提案した実施形態に対する候補vs実際のフォワーダ(10mの車両間スペーシング)。
異なるプロトコルによって選ばれる空間通路。提案した実施形態の認知されたパケットは、川を渡ってホップでき、より短い経路(1)を選ぶ。従来技術のロードマップベースのプロトコルはこれを無視し、より長い経路(2)を選ぶ。
空間接続性情報の収集および分散のためのハイレベルデータフロー。サーバーは、全てのデータ収集ノードからの空間接続性データを合わせ、統計的な空間経路コストを計算する。
空間接続性情報を記録するためにノードによって用いられるデータ構造
LOS条件が、いかにして、ノードが送信先に対してより近いほど中継がより良くなるという仮定を覆すことができるかを表す。この場合、大きなトラックが信号を遮り、ノードbが送信先DSTと通信することを防ぐ。ノードbよりもDSTから遠いが、ノードaが、透き通ったLOSによりDSTと通信できる。
提案した空間接続性拡張が、いかにして、統計的及びリアルタイムな接続性情報を合わせて、ルーティング経路を見つけることができるかの例を与える。

実施例

0034

地理的座標に基づくマルチホップメッセージ転送は、車両通信に対する主要な基礎的要素である。しかしながら、不安定なリンク及び広範なノード密度により、車両使用に適したアルゴリズムを設計することは、チャレンジングである。斬新な方法で3つのコンセプトを合わせる新しい転送プロトコル、ここで言うDAZLを紹介する。第一に、多数のノードが、パケット転送で協調する。従来の単一中継方式と比較して、トポロジー及びパケット配送レートの変化に対するロバスト性がもたらされる。第二に、高密度のシナリオで、重複及び競合を制御するために、ネットワーク層スロッティングを用いる。第三に、ホップ長を適時的に最大化するために、分散優先度付けアルゴリズムを用いる。実験とシミュレーションの両方を通じて、本開示は単一の中継転送にわたるスループットで最大60%の改善をもたらす一方で、低レイテンシ及びレプリケーションを保証することを示す。

0035

車両間アドホックネットワーク(Vehicular Ad-Hoc Networks (VANETs))は、安全から交通効率及びインフォテイメントにまでわたる分野で斬新な応用を可能とすることにより、陸上輸送の改善をねらう。インターネットアクセスセンサデータ収集、及び協調的な車ルーティングのような、多くのこれらの応用は、増大した通信範囲に対してマルチホップ通信を必要とする[1]。セルラーが、時折選択肢となることもあるが、車両ネットワークは、レイテンシ、帯域、及びコストの点から利点をもたらし、効率的なマルチホップ通信を重要課題とする。

0036

VANETで転送するマルチホップパケットは、2つの理由でチャレンジングである。第一に、車両の機動性豊富散乱環境、及び障害物によって生じる妨害により、リンク品質が大きく変動する[2]。これにより、非常に動的なパケット配送レート及び部分的な接続性の大きなグレーゾーン[3]につながる。第二に、ノード密度が、空間及び時間の両方で大きく変動し、適用可能なプロトコルを必要とする。車両がまばらな時、パケットロスを防ぐために、転送は活発になる必要がある。それに対して、交通渋滞では、輻輳崩壊を避けるために、転送は不活発になる必要がある。

0037

VANETルーティングに関する先行研究は、単一の中継パラダイムに焦点をあてており、各ホップで、パケットを転送するために単一のネイバーが選ばれる。このアプローチは、単一のリンクの品質に依存しているので、VANETで露見するグレーゾーン現象の影響を受けやすい。いくつかのプロトコル(例えば、[4]、[5])は、無線範囲の端にあり、最も不安定になりやすい、可能な最長のホップを選ぶことで、さらにこの問題を悪化させる。この観測に基づいて、ゾーンベースの密度認知制限転送、ここで言うDAZLのような新しいパケット転送アルゴリズムを示す。アルゴリズムは、斬新な方法で3つの重要なアイデアを合わせる。

0038

第一に、様々な車両へのチャネルは様々なフェージング条件を受けるので、通信範囲内にある多数の車両の存在は、リンク不安定性の問題点に対処するのに役立つ。これを活用して、DAZLノードは、所定のネイバーにパケットを転送しないが、代わりに地理的な領域又はゾーンに転送し、そのゾーン内にある任意の車両はパケットを転送できる。ネクストホップは、センダによって演繹的に選択されないので、転送動作は、利用可能でベストなチャネルを適時的に用いることができる。これは、「車両ダイバーシティ」と呼ばれる。第二に、分散優先度付けアルゴリズムの使用を通じて、このアプローチは、利用可能であれば送信先により近いフォワーダを適時的に選択することができ、従って、ホップ数を減らす。最後に、大きく変動する車両密度を扱うために、DAZLは密度認知とする。特に、高密度のシナリオでは、パケットを転送するよう試みる車両の比率が減るため、ネットワーク内の競合を最小化する。

0039

DAZLは、インフラストラクチャ及びメッシュネットワークでうまく利用されてきた、ダイバーシティ及び適時的な送信の一般的なアイデアを合わせ、それらをVANET面に応用する。従前の適時的なプロトコルは、トポロジー情報[6][7]及び連携のために共有されるチャネル[8]に依存しており、その両方がVANETで利用できない。従って、DAZLの重要な貢献の一つは、レプリケーション及び干渉を減らす一方で潜在的な中継が協調できる、分散型でインプリシットな斬新な中継連携方法である。

0040

リンク不安定性
従来のルーティング方式は、ノードが、固定化されるか又はゆっくりと変化するネイバーの組を有し、ネイバーは互いに良く接続されるという前提に基づいている。しかしながら、これらの仮定はVANETに対しては成り立たず、トポロジーは急速に変化し、リンクがよく弱くなることが、測定によって示された。この不安定性の理由は、高機動性に伴う豊富な散乱領域の組合せから生じる。位置に依存して、信号を散乱させ、ほんの小さな移動とともに急速に変化するマルチパス効果が生じる木、建物、及びとともに道路が引かれるので、結果的にリンク品質に大きな揺らぎが生じる。ノードの移動はまた、シャドウイング条件の変化にもつながる。例えば、車両が建物の角を曲がる時、その信号は直ちに減衰する[2]。さらに、ノードが静的な時でさえ、LOS条件の変化が通信に影響を与える。例えば、図1では、高いトラックがノードa及びbの間に入るところであり、それらのLOSをふさぐ。

0041

従来、送信源と送信先間の経路は、一連の所定のノードとして定義される。図1の例では、経路を構成する車a、b、及びcが印(a、b、c)として示されている。経路選択の方策は変化する。周期的なルーティング方式では、ルートは事前計算され、ネクストホップがルーティング表に保存される。例えば[9]のルーティングに基づく送信源では、経路は送信源によって選択され、パケットヘッダに保存される。動的なVANET環境ではルートが急速に廃れるので、これらの方策では問題がある。例えば[10]のような地理的ルーティングでは、ネクストホップが、先行ノード(previous node)のネイバー及び送信先の座標に基づいて先行ノードによって選択される。中継選択を実行中、これにより地理的転送はより適応となり、車両プロトコルに対する定番の選択となる。

0042

近年、Baiらは、他の環境と異なり、受信が(ほぼ)完璧である大きな送信範囲を、車両は有さないことを観測した[3]。代わりに、ほとんどの無線範囲は、中間のパケット配送レートを有するグレーゾーンである。言い換えると、VANETでは良いリンクは非常に少なくなり、そのリンクは短くなりやすく、従って、転送に対しては魅力的でない。このため、既存のプロトコルがそうであるように、パケットを転送するために単一のネクストホップノードに依存することは危険である。「車両ダイバーシティ」に影響を与えることで、この問題に対処することを提案し、様々なフェージング条件に対する主体である多数の車両が、パケットの転送で協調できるようにする。車両ダイバーシティについては、「車両ダイバーシティ」及び「ゾーンベースの転送プロトコル」でさらに詳説する。

0043

ホップ長トレードオフ
車両ネットワークで出くわすリンク不安定性は、良いネクストホップの選択を困難にする。できるだけ遅くに選択がなされるので、地理的ルーティングは良い選択肢である。しかしながら、任意のプロトコルは、根本的なトレードオフに直面する点に注意する。近くのノードを選択することで、平均的により高いパケット配送レートとなるが、送信先まで到達するためにより多くのホップを必要とする。より遠くのノードを選択することで、ホップの数は減るが、より低いチャネル品質によってロスが増大し、従って、より多くの再送信が生じるであろう。また、例えば隠れ端末による干渉ロスも増大する可能性がある。このため、このトレードオフをうまく取り扱ってスループットを最適化することが困難である。

0044

優先度付けした車両によってこの問題に対処することを提案する。我々の解決策では、送信先により近いノードが優先度を与えられるが、センダにより近いノードは、そのようなロングレンジのノードが利用できない時に介入する。これにより、信頼性を損なうことなく、ホップ長が最大となる。「順位を通じたフォワーダ優先度付け」でより詳細を述べる。

0045

可変ノード密度
交通密度は、空間及び時間上で大きく変動する。Baiらは、トロントのフリーウェイで、その日の時間に依存して、6から500メートルの範囲で車両間スペーシングを報告した[11]。例えば、図1のような道路工事のために、同じ道路上でも異なる密度が同時に露見する可能性さえある。

0046

低密度のシナリオは、ネットワーク分割の影響を受けやすく、通常は、保存及び搬送の手順を踏んで対処される。高密度では、他のクラスの問題が生じる。例えば、車両がより多くなればなるほど、より多くのメッセージが送信されることが多くなり、輻輳が増大する。これにより干渉ロスが生じて、前述したリンク不安定性の問題点をさらに悪くし、802.11pのバックオフメカニズムによって高い負荷を処理できない場合、崩壊にさえつながる。ネットワーク層プロトコルは、MAC層にある負担を適用して、制御する必要がある。

0047

いくつかの提案(例えば、[4]、[12])では、信頼性を増すための試みとして、密集した領域に向けてパケットを積極的に誘導してみてはいるが、一方で、これは低密度のシナリオで有効であり、ノード密度が高い時は問題となる。「スロッティングを通じたフォワーダ連携」で説明するように、潜在的なフォワーダの数を制限し、時間上でそれらを広げることでこの問題点に取り組む。

0048

プロトコル設計−車両ダイバーシティ
従来の転送アルゴリズムでは、パケットは所定のネクストホップノードに転送され、これはVANETでは問題となる。リンクが大きなグレーゾーンを有するので、(非常に短いリンク以外の)ほんのわずかなリンクが安定である。これに対抗するために、DAZLはゾーンベースの転送を用い、新しいパラダイムでは、図2のように、所定のノードではなく、先行ホップ(previous hop)と送信先の間に位置する地理的ゾーンに対して、パケットを転送する。ゾーン内にある任意の車は、その後、パケットを転送できる。それらの物理的な隔たりのために、ノードは異なるフェージング、LOS、及び干渉条件を受け、多数の潜在的なフォワーダによって、パケットロスの可能性が減る。

0049

車両ダイバーシティの潜在的な利益を評価するために、駐車された車両がセンダとして振る舞う一方で、3つのレシーバはその周り順路運転し、互いに近接を維持して、集団の中で乗っているサイクリストのように周期的に位置を入れ替えるという実験を行った。車両には、IEEE802.11pベースの車両通信[13]用のプラットフォームである、NECのLinkBird−MXを搭載した。5.9GHzを中心とする10MHzチャネル内で、6Mbpsデータレート及び18dBm送信パワーで、一秒ごとに100個の500バイトメッセージを送信した。

0050

図3aは、第一のレシーバr1のパケット配送レート(Packet Delivery Rate (PDR))のヴァイオリプロットを示す。PDRは、一秒ごとにサンプルされ、100mのセンダ‐レシーバ距離ビンに対してサンプルをグループ分けする。ヴァイオリンプロットは、ボックスプロットからの中央値と四分位をカーネル密度プロットと合わせ、分布の形状及び主なパラメータの両方を見ることができる。300と600mの間で中間のPDRとともに、部分的な接続性の大きなグレーゾーンを観測できる。図3bでは、3つのレシーバのうち少なくとも1つのレシーバがパケットをデコードできる長さだけパケットが配送されたと考える時、何が起こるかを示す。500と600mの距離ビンのみで観測されている部分接続性とともに、グレーゾーンのサイズの減少が明白である。

0051

1、2、及び3つのレシーバに対する平均PDRを、距離の関数として図3cにプロットする。単一のレシーバr1から2つのレシーバr1+r2に変わることで、20%のPDR増加をもたらす。第三のレシーバr3は、さらに10%を付加する。

0052

ダイバーシティ利得は、参照レシーバr1によって失われるメッセージの数で割った、車両ダイバーシティによって回復できるメッセージの割合として定義される。図3dは、距離の関数としてこの利得を示す。付加したr2によって、400mまでで、ロスの少なくとも75%をシステムが回復できる。r1及びr2にr3を付加することで、同じ距離までで、全ロスの95%が除去される。

0053

これらの結果は、車両ダイバーシティを活用できるプロトコルによって得る重大な利益があることを示す。次に、そのようなプロトコルを述べる。

0054

プロトコル設計−ゾーンベースの転送プロトコル
ゾーンベースの密度認知制限転送、DAZL(Density Aware Zone-based Limited forwarding)は、グレーゾーン現象を克服するためにゾーンベースの転送を用いる地理的な転送プロトコルである。この節では、ハイレベルのアルゴリズムを示し、一方で次に述べる節で、各個別品についてのさらなる詳細を提供する。

0055

ノードは、それ自身の座標を知っており、周期的なブロードキャストビーコン[14]からワンホップネイバーの座標を得ることができるものと仮定する。送信先は、先行知識又は位置特定サービス[15]を通じて位置指定可能である。パケットヘッダは、元の送信源、送信先、及びパケットを送信したフォワーダ(先行ホップ)の3つのアドレスを保存する。各アドレスは、車に対するノード識別子及び地理的座標の両方を含む。各ホップでは、パケットを受信する各車両は、以下のプロトコルを実行する。
−その位置及びヘッダ情報に基づいて、先行ホップよりも送信先に近いかどうかを確認する。そうでなければ、パケットを落とす。
−その近傍にある他の潜在的なフォワーダがもたらす有用性と、フォワーダとしてのその有用性を比較する順位アルゴリズムを走らせる。
−もしノードがnベストな潜在的フォワーダの1つであると考えられるのであれば、転送ゾーン(forwarding zone)にあると宣言される。そうでない場合、パケットを落とす。
−車両がゾーン内にある場合、パケットを転送する前に、その順位に反比例する時間の周期だけ待機する。これは、順位ベースのスロッティング(rank-based slotting)と呼ばれる。
待機状態にある間に、車両が、他の車両がこのパケットを転送することを漏れ聞いた場合、送信は必要ないと判断し、動作を中止する。
最後のステップのインプリシット通知方式(implicit acknowledgement scheme)はまた、先行ホップによっても使用され、転送動作の成功について判断する。ロスは中断によって検出され、再送信を通じて処理される。ノードが互いの転送を聞かない場合、レプリケーションが生じる。この問題点を軽減するために、DAZLは、単純な重複抑圧方式を実装する。各ノードは、漏れ聞いたメッセージの履歴を維持し、入ってくるメッセージを落とすべきかどうかを確認するためにそれを用いる。

0056

より多くのレシーバが高密度のシナリオでは付加されるので、増大した競合により車両ダイバーシティの利益が無効となり始める。DAZLは、パラメータである数nでフォワーダの量を制限することで、このトレードオフを制御する。nが5を宣言するよう設定される場合、低密度のシナリオでの信頼性と高密度の状況での競合減少の両方を達成できる。

0057

DAZLによって用いられる分散順位アルゴリズムによって、ノードが明示的な通信なしに協調でき、オーバーヘッドを減らす。順位はまた、ホップ長(すなわち、伝搬した距離)を最大化できる優先度付けメカニズムとしての役割も果たす。制限数nのフォワーダに加えて、転送レベルで生じるディレイは、高密度の状況でレプリケーション及び競合を減らすように働く。以下でさらにこれらのメカニズムを詳説する。

0058

ここで述べる転送プロトコルは、(例えば、ハイウェイで)送信源及び送信先座標間で道路に沿ってパケットを転送できる。例えば横断する一連の道路のような、より詳細な経路情報ルーティングヘッダに付加することで、より複雑なトポロジーをサポートできる。

0059

プロトコル設計−スロッティングを通じたフォワーダ連携
ゾーンベースの転送によって生じる冗長性は、空間エリアで本質的に有益である一方で、高密度によって持ち出される挑戦に対処する必要がある。転送ゾーンの内側にある非常に多くのノードが、同時に転送を試みる場合、802.11pのバックオフメカニズムは、高いパケット衝突レートを避けることができない。さらに、あまりに多くのフォワーダを有することで、ネットワーク上に所望しない負荷を付加するような重複が増大する可能性がある。

0060

802.11pMAC分散連携機能(Distributed Coordination Function (DCF))は、我々に対していくつかの基本的な連携をすでに実装する。DCFでは、ビジー状態のチャネルを検出するノードは、各ノードが、(典型的には)16スロットのコンテンションウィンドウからスロットをランダムに選び、順番を待つようなバックオフ手順を実行する。チャネルが現在フリーであると分かる場合、パケットを送信する。そうでない場合、手順を繰り返す。これは、適度の数のノード間で衝突を避けるには十分であるが、一方で密集したシナリオでは十分ではない。さらに、MAC層スロットは短いので、転送を待機しているノードが他のフォワーダの送信を漏れ聞いて、その送信を中止する十分な時間がない。最終的に、ノードは優先度付けを与えない。

0061

本解決策は、ネットワーク層でスロッティングの付加的なレベルを導入するためのものである。DAZLは、図4のように、複数の転送スロットへのパケット受信の後、時間を分割する。潜在的なフォワーダは、明示的な連携なしに、スロットにわたってそれら自身を分散させる。各スロットの間隔は、重要なパラメータである。スロットがあまりに長い場合、レイテンシが悪化する。スロットがあまりに短い場合、異なる転送スロットのノードは、コンテンションウィンドウが重なれば、MACレベルでさらに競合する可能性がある。スロットは、平均的なMAC層のコンテンションウィンドウよりもわずかに長いのが理想であり、これにより、異なるスロットのノードは競合せず、不必要に待ちわびることもない。

0062

プロトコル設計−順位を通じたフォワーダ優先度付け
長距離ホップは、より少ないホップで送信先に到達することを意味し、結果的に、より低いレイテンシ、トラフィック負荷、及び干渉を意味するので、長距離ホップが望ましい。従って、送信先に最も近いノードに優先度を与えることが望ましい。しかしながら、これらのノードがパケットを受信しない時、信頼性を保証するためにさらに離れたノードが介入し、上記で指摘したホップ長トレードオフに効果的に対処する。

0063

DAZLは、転送スロットへのノードのスマートな割り当てを通じて優先度付けを達成する。送信先に近いノードは、最初のスロットを得て、一方で、送信先からより遠いノードは後のスロットを得る。これは、以下のように完遂する。周期的なビーコン[14]に基づいて、ノードは、ワンホップネイバーの位置の表を作成する。また、先行ホップの座標及び予想される無線範囲がパケットヘッダに含まれる。その後、潜在的な各フォワーダは、以下の手順を実行する。
−先行ホップよりも送信先に近く、かつ、無線範囲内にあるノードによって構成される、メッセージmに対して予想されるフォワーダの組ESf、mを定義する。
−組ESf、mからアレーrを構築する。ここで、送信先までの各ノードの距離に従ってrをソートする。ノードがrに現れるインデックスiは、現在のその順位である。
−ESf、mの各ノードに対して、転送スロットs=ceil(rank/nps)を割り当てる。プロトコルパラメータ、rankはノードの順位であり、npsはスロット毎のノードの数である。ceil(x)はx以上の最も小さい整数の値である。
最後のルールは、距離に関して、送信先に向けて最も前方へと進展させるノードに最初の転送スロットが与えられることを保証する。npsパラメータは、レプリケーションとレイテンシ間のトレードオフを制御する。より多くのノードがスロット毎に許容される場合、予想されるレイテンシは減る一方で、レプリケーションは増す。また、フォワーダの制限数nよりも大きな順位のノードは、過度のレプリケーションを避けるために転送を控える点にも注意する。

0064

例を見直すために、図2を用いる。簡単のために、転送ゾーンは描かれた通り定義され、ゾーン内の各ノードは、ネイバーの表にある同じゾーン内の他の全てのノードを有し、各ノードはそれ自身の転送スロット(nps=1)を得るものと仮定する。例として、最初のホップでは、パケットを受信するノードの組はASf、m={a、b、d}であると考える。これらのノードは、cがパケットを失ったことを知らず、その順位にcを含めて、ESf、m={a、b、c、d}を形成する点に注意する。送信先までの距離に従ってノードを整理することで、あらゆるノードが同じ順位r=[d、c、b、a]に到達する。ここで、ノードdを1番目の転送スロットに割り当て、c、b及びaを、2番目、3番目、及び4番目のスロットにそれぞれ割り当てる。1番目のスロットへの割り当てが実現することで、ノードdは直ちにパケットを転送する。その後、ノードa及びbは、dのパケットを漏れ聞き、任意の重複を避けるためにそれ自身の転送を中止する。

0065

同じスロットにあるフォワーダは、MAC層でさらにバックオフするので、アルゴリズムは、様々なノードによって計算される順位の小さな変動に関してロバストである点に注意する。また、GPSエラーは、プロトコルの動作に対して致命的ではない。その効果は、やや最適な順位が生成されることにとどまる。

0066

本開示の結果と実施形態
DAZLは、地理的なルーティングアプローチに従う従来のネイバーベースプロトコルと比較される。パケットを保持するノードは、周期的なビーコンを通して得られる局所近傍の知識に影響を与え、パケットを送信する前にネクストホップを選ぶ。前述したとおり、ネクストホップを選ぶことで、配送レートと距離間の困難なトレードオフが伴う。

0067

前方への進展と信頼性の両方を兼ね備える、メトリックに基づく旧式のアルゴリズムを用いるプロトコルを実装した。特に、送信先に最も近いネイバーによって得られる前方への進展の50%をもたらすことに最も近いノードを、各ホップで選ぶ。例えば、それぞれ200、100、及び50mに3つのネイバーa、b、及びcがあるノードは、中継としてbを選ぶであろう。50%の値が図3cの結果から得られ、通信範囲の後半では、単一レシーバのPDRは80%より下にとどまる。送信先に最も近いネイバーを選ぶ貪欲なアプローチと、ランダムなネイバーを用いるランダムなアプローチを用いたネイバーベースの転送はまた評価もされるが、その性能は一貫して非常に乏しかった。

0068

完璧で包括的な情報にアクセスする理想的なプロトコルに、DAZLがどの程度近づいているかを試験できるように、管理者(oracle)が存在する最適なゾーンベースプロトコルも実装した。管理者ベースプロトコルは、以下のように働く。
−現在選択されているノード(最初は送信源)が、パケットをブロードキャストする。
−ネットワーク上のあらゆるノードが、パケットをうまく受信したかどうか管理者に伝える。
−管理者は、全ノードから聞こえれば、送信先に最も近いレシーバを選び、フォワーダとする。
実際問題として、このプロトコルを実施することはできないため、シミュレーション評価で考えるのみである。

0069

この実験評価は、5つのノードの小さな環境に限定される。本明細書の後半で、より大きなトポロジーのDAZLを評価するために、シミュレーションを用いる。

0070

建物は、VANET通信に対して重大な悪影響を与えることで知られている[2][16]。図5の環境を用いたような条件で、DAZLを実験的に評価した。送信源及び送信先の車は、建物の2つの隣接したサイドに駐車され、直接通信することはできない。しかしながら、建物の角に近い3つのノードが、パケットを転送するのに役立つ。

0071

各車両は、IEEE802.11p標準と互換性のあるNECのLinkBird−MX[13]を搭載する。プラットフォームの制限のために、プロトコルは、イーサネット(登録商標)を通じてLinkbirdに接続されるラップトップ上で走るアプリケーションとして実装される。これは、パケットは2つのプロトコルスタックにわたって、有線上で伝搬する必要があることを意味する。これにより、DAZLに対して主に2つのことが示唆される。第一に、全レイテンシは、悪化するであろう。第二に、漏れ聞いたパケットは、処理により長い時間かかり、不要なレプリケーションの可能性が増す。これを軽減するために、25msecよりも長い転送スロットを用い、漏れ聞いたパケットの処理に対してより長い時間をプロトコルに与える。

0072

旧式のネイバーベースプロトコルは、本ケースではaにあたるような、無線範囲の半分に最も近いノードを選ぶ。転送スロット毎に1つで(nps=1)、3つのフォワーダ(n=3)まで許容するようにDAZLを構成した。プロトコル間のロバスト性の違いを強調させるために、全方式で再送信を不可能とした。システム構成パラメータを表1にまとめる。各プロトコルに対して、毎秒250個(mps)のレートで100,000個のメッセージを送信した。

0073

0074

図6aは、秒毎のメッセージ(messages per second)という単位で、ネイバーベースの転送に対してDAZLによって達成される平均スループットを比較する。範囲を用いて、95%の信頼区間を示す。ネイバーベースの方式は単一の中継を選ぶので、その性能は、送信源と中継間のリンクのロスに非常に影響される。事実、送信先に対しては84mps、33%の送信源レートを得るのがやっとである。一方で、DAZLは、任意の単一ノードに依存しない。多数の中継に影響を与え、様々な転送スロットにそれらを分けることができる。これにより、137mpsという63%のスループット改善が得られる。

0075

図6bは、2つのプロトコルに対するエンドツーエンドの平均レイテンシを示す。プラットフォームの制限のために、絶対値は、本番環境での値よりも大きくなる。ネイバーベースからゾーンベースの転送に移行する場合、相対的におよそ25msecのディレイ増加が見られる。これは、スロッティングによって生じるレイテンシによるものである。本番バージョンでは、レイテンシはよりずっと低いであろう。プロトコルスタックは、単一のデバイスに実装され、例えば数100マイクロ秒のような、よりずっと短いスロットを許容する。

0076

図6cは、送信先で観測される複製の平均数を示す。メッセージロスによる再送信を不可能としたので、ネイバーベースプロトコルは、レプリケーションを生成しなかった。DAZLは、平均で20%のレプリケーションを生成した。この数は、Linkbirdの無線環境のために不自然に高い。ノードが他の中継から転送パケットを漏れ聞く時、転送を控えるべきである。これは、転送プロトコルが、送信キューから現在の冗長なメッセージを落とすようにMACに伝えることによって行われる。しかしながら、これを行うLinkbirdのMAC層を変えることは不可能であり、結果として重複パケットが生じる。本番システムは、DAZLの単一のスタック実装を用い、この問題は生じない。シミュレータはまた、転送中止を正しく実行する。

0077

最後は、車両ダイバーシティ、すなわち、送信先に到達する全パケットが各中継から生じる割合であり、プロットを図6dに示す。旧式のネイバーベースの方式では、時間のおおまかに90%でaが選ばれる。中継b及びcに起因する10%は、ノードaが送信源との接続性を時折失うためである。

0078

DAZLは、送信先に対して距離に基づくスロットを割り当て、ノードcは1番目のスロットを、bは2番目のスロットを、aは3番目のスロットを得る。ノードcは、最も高い優先度を有し、送信先でおよそ50%のパケットを占める。ノードbは40%を、ノードaは10%を占め、その値はそれらのスロット割り当てと一致する。

0079

これらの結果は、ほんの数個のフォワーダのみが利用可能な時でさえ、DAZL方式の利益を強調する。

0080

シミュレーション評価に関しては、より大きなスケール評価のために、802.11pサポートのns3シミュレータを選んだ。シミュレーションパラメータを表2に示す。

0081

0082

実際のハイウェイを代表する指数関数分布[11]に従って1km長の道路にノードを配置した。80メートル(まばらだが接続されている)から10メートル(交通渋滞)の範囲にある車両間の平均距離を用いた。道路の一端にあるセンダは、322バイトのデータパケットを毎秒200個のレートで他端の送信先に送信する。再送信の最大数を、2に設定した。スロット毎に1つのノード(nps=1)で、DAZL転送スロットを2msに設定する。フォワーダの数を7に制限し、予想範囲を150mに設定した。1Hzのビーコンを用いて、ネイバーディスカバリを行った。5回の60秒ランにわたって、異なるランダムなシードで結果を平均する。

0083

図7は、前述した旧式のネイバーベースプロトコル及び管理者が存在するゾーンベースプロトコルの性能とDAZLの性能を比較する。縦線及びハッシュマークは、利用可能な、95%の信頼区間を表す。

0084

図7aは、3つの方式に対するスループットを示す。ネイバーベースプロトコルは、110mps(送信源レートの55%)前後で推移する。これは、パケットロスの結果であり、45%の時間、選択されたネクストホップがメッセージをうまく受信できない。しかしながら、管理者方式は、任意の所定のノードに依存せず、少なくとも1つのノードでその方式が働く限り、任意のノードはパケットを受信する。このため、200mpsの送信源レートに非常に近くなる。DAZLは、185mpsとなり、管理者プロトコルの10%内にある。その理由は、7つまでの潜在的なフォワーダを使用できるからである。また、DAZLのスループットがより高い密度で減らないという事実は、フォワーダのスロッティング及び制限数が、過度の競合及びロスを防ぐ点で有効的であることを示す。

0085

図7bは、全てのプロトコルに対するエンドツーエンドのレイテンシを示す。DAZLは、管理者プロトコルに非常に類似してふるまう。両者は10msecを下回るレイテンシを有し、その結果は密度にわたってかなり一致する。これは、スロッティングを通じてDAZLによって生じる小さなディレイが、全レイテンシに重大な影響を与えないことを指し示す。また、DAZLの内在する冗長性により、ネイバーベースプロトコルよりも非常に低いレイテンシを得る。その理由は、ネイバーベースの転送により、より多くのパケットロスが生じ、従って、多くの再送信が生じるからである。これらは、付加的な送信時間のためだけでなく、最終的に中断及び再送信する前にノードが待機する必要があるため、非常にコストがかかる。

0086

図7cは、送信先で観測される複製の数を示す。予想通り、管理者プロトコルは、任意の複製を生成しない。一方で、ネイバーベースの方式は、ロスのために60%までのかなりの量のレプリケーションを生成する。先行ホップとフォワーダ間のパケット配送率は、完璧ではないので、時折、後者によってなされる転送を前者が聞かず、偽りの再送信につながる。

0087

DAZLは、潜在的なフォワーダが互いに聞くことに失敗する時、レプリケーションを生成する。しかしながら、レプリケーションはよく抑えられており、18%を決して越えない。これは、採用された消去メカニズムによるものであり、その動作を図7dで観測できる。このグラフは、10mの車両間スペーシングというシナリオに対する実際のフォワーダの数と潜在的なフォワーダの数を比較する。ここで、97%の時間、潜在的なフォワーダは2つ以上あり、レプリケーションにつながるという状況を観測できる。しかしながら、99%の時間、実際のフォワーダは1つのみであり、我々の方式の有効性を証明する。

0088

ここで表れた結果は、車両無線ネットワークでのゾーンベース転送の利点を明確に実証する。DAZLは、局所的な情報及び分散アルゴリズムのみをその間用いる管理者プロトコルとほぼ同じくらい上手く働く。

0089

さらなる及び/又は代わりの実施形態
上記の方法は、ハイウェイのようなシナリオに対して特に有用であり、パケットはほぼ直線の道路形状をたどって、送信先に到達できる。しかしながら、交差点や建物のような障害物がある都会環境では、上記の方法を改善する必要がある。都会環境では、パケットが転送され、送信先まで到達するための空間通路は、無線接続性に依存して直線と大きく相違し、道路ネットワークトポロジー及び地域トポグラフィの両方によって厳しく制約される。

0090

従来、地理的VANETの都会ルーティングプロトコルは、道路マップを用い、パケットが転送される送信源から送信先までの一連の道路を選択するのに役立つ(例えば、GSRSAR、GvGrid)。いくつかはまた、統計的な交通情報も付加し、より良く接続されている道路を選択するのに役立つことで、配送確率が増す(例えば、ACAR、Gytar)。

0091

方策GSR、SAR、GvGrid、ACAR及びGytarに基づく道路マップは、潜在的な改善をもたらす。それらは、無線接続性が道路トポロジーを正確に模倣することを仮定しており、実際、地域トポグラフィも同時に重要となる。例えば、図8には、両方の土手にある道路に接する川がある。道路マップベースプロトコル(2)は、送信源から送信先まで進行する車が通るルートと似たような、橋を使って川を渡る長く巻きついた通路を選ぶ。しかしながら、これは、他の土手が無線範囲内にある限り、パケットは任意のポイントで川を渡ることができるという事実を無視している。この認識により、ずっと短く、最適化された空間接続性ベースプロトコル(1)に結び付く。

0092

本開示に従ったプロトコルは、都会環境でパケットのより良い転送通路を選択するために、空間接続性情報を用いる。

0093

前述した周期的なブロードキャストビーコンのような、協調認識メッセージ(Cooperative Awareness Messages (CAMs))は、センダの位置及び速度ベクトルの両方を含むメッセージである。これらは、あらゆるノードによって周期的に送信され、各ノードは、ETSIによる又はDSRCの高度道路交通システム(Intelligent Transport System (ITS))で例えば定義されるような、現在のネットワーク近傍の認識を有する。

0094

本開発では、空間接続性情報を収集するために、CAMに影響を与えることを提案する。CAMは、センダの位置を含み、標準の一部であり、任意の付加的な漏れ聞こえを生じさせることなく用いることができるので、魅力的である。代わりに、特にメッセージがブロードキャストメッセージである場合、センダの位置を含む任意の他の種類のメッセージを用いることもできる。

0095

受信されるCAMに関するGeo参照情報は、時間の一周期又は複数周期にわたって収集され、各ノードによってサーバーに適時的(例えば、路側機(Road-Side Unit (RSU))のそばを通過する時)にアップロードされる。多数の車両から統合されたデータは、サーバーによって合わせられ、処理されることで、地域又はに対する統計的な空間接続性マップを得る。ノードが空間位置を表し、エッジがパケット配送レート、信号強度及び/又は存在している車両の確率の点でそれらの間の無線接続性の品質を表すグラフとして、このマップをモデル化できる。ここでは、このグラフのエッジに対する同義語として、空間リンクを用いる。その後、ルーティングプロトコルに用いるために、車両はグラフを適時的(繰り返しで例えば、RSUのそばを通過する時)にダウンロードする。トポグラフィ、従って、平均の空間接続性、がゆっくりと変化し、たまのアップデートで十分であるので、これは実行可能な提案である。全データフローを図9に示す。

0096

ここで、図10をもとに、サーバーにアップロードするために各ノードによって収集されたデータについて述べる。GPS(又は機能的に同等な)レシーバを用いて、各ノードは、各タイムスタンプに対するその座標を登録する、位置の表を保持する。送信されたCAMの数もまた、各項目に保存される。タイムスタンプの分解能は、用いた粒度のレベルを必要とする。例えば、1HzGPSレシーバによって、ノードは1秒毎に最大1つの区別された項目を有することができる。タイムスタンプデータを用い、そのようなタイムスタンプに従ってサーバーでデータを統合することにより、収集されたCAMデータを単純化でき、従って、車両ノード上の作業負荷を軽減する。

0097

位置の表の傍らで、各ノードはまた、CAM受信表も保持する。この表の主な要点は、(タイムスタンプ、センダid)の組である。各列は、ノードから発するCAMの数、所定のタイムスタンプに受信されたセンダidを記載する。CAMに対する平均RSSIもまた保存される。

0098

RSUのそばを通過する時、ノードは2つの表を単純化して圧縮し、それらを既知のアドレスで聞いているサーバーにアップロードする。複数のノードからデータを受信することで、サーバーは、ノードにわたって同期されるGPSタイムスタンプを使用でき、位置の表及び受信表に加わって、以下を判断する。
(1)どの空間リンクが存在しているか。空間リンクは、位置の組(L1、L2)であり、ノードaがL1にあり、ノード2がL2にある場合、それらが通信できる確率は0ではない。
(2)受信したCAMの数を送信したCAMの数で割ることで、各空間リンクに対して予想されるPDRを推測でき、及び/又は、
(3)RSSIデータを平均することで、各空間リンクに対して予想される信号品質を推測でき、及び/又は、
(4)各空間リンク(L1、L2)に対して、ノードの位置の表を用いることで、サーバーは、位置L1及びL2の両方に同時に少なくとも1つのノードがある確率を計算できる。これは、実効的にはリンクが存在する確率である。
計算を単純化するために、緯度及び経度の座標を、個々のグリッド(例えば、50×50mセルの正方形グリッド)上にマップできる。その後、空間リンクは、一組の空間セル間のリンクとなる。

0099

例えば、図10では、ノード1のノードは、ノード2によって送信された全10個のCAMパケットのうち、それぞれ−90dBmのRSSIで、5個のCAMパケットをノード2からタイムスタンプ1で受信した。従って、PDRは50%であり、平均RSSIは−90dBmである。タイムスタンプ2で、ノードが依然として同じ位置にあるが、一切通信できなかった場合、ノード2がタイムスタンプ2で10個のメッセージを(10+10=20)送信したと仮定すると、PDRは25%(20個のうち5個)に下がるであろう。

0100

空間接続性のグラフで空間リンクによって接続された地理的な位置又は空間セルは、隣接しなくてよく、例えば、空間リンクは、(例えば、離れたセルが、好都合なLOS条件により接続される時)グリッド内で、1つ以上のセルにわたってホップして、非隣接のセルに接続できる。また、多数の異なる経路(経路は、1つ以上のリンクの連結によって構成される)は、空間セルの組の間に存在する。この例を見ると、2つの空間セルC1及びC2間の接続性を遮る大きな建物を考えている。パケットは、左側か右側のどちらか一方で建物を迂回して行くことができるものと仮定する。すると、C1及びC2間に2つの空間経路がある。これらの特徴により、グラフは正確に空間接続性を反映でき、以前のプロトコルでは不可能であった方法でトポグラフィ条件に順応できる。

0101

空間リンクは、2つの方向L1→L2及びL2→L1に対してデータを統合し、又は分けることで、一方向性又は双方向性と捉えることができる。さらに、周期的又は連続的に、より古い統合データを使用しなくなる。空間接続性は、ゆっくりと変化するので(変化は、新しい建物、道路等のトポグラフィの変化にたいていは由来する)、これもまた、遅い処理である。サーバーは、各空間リンクに適する多数のメトリックを保存するが、全てを同時に使用する必要はない。次の節で、PDRデータのみを用いるルーティングプロトコルによって、この空間接続性情報をいかにして用いることができるかを述べる。

0102

先の実施形態は、送信先までの距離に基づいて潜在的なフォワーダを順位付ける。しかしながら、非一様な無線伝搬条件のために、これが常に完璧なメトリックであるとは限らない。例えば、図11では、ノードbは送信先DSTに最も近いが、大きな車両(例えば、トラック)によって生じる妨害のために、送信先DSTと通信できない。一方で、ノードaは送信先に対して妨害のないLOSを有するので、さらに遠くなるにも関わらず、ノードaは送信先と通信できる。

0103

ルーティングプロトコルの目標は、各ステップで、送信先にパケットをうまく、かつ、迅速に配送することとなるベストな見込みがある候補を選ぶことである。あらゆるノードが、絶えず最新の状態の全トポロジー情報を得ることは不可能なので、プロトコルは、ヒューリスティックに依存する必要がある。上記で、なぜ空間接続性が都会環境でのルーティングに対して良いヒューリスティックであるのかを述べた。

0104

以下の通り、転送処理に空間接続性を組み入れることができる。先の実施形態の方法の原理は同じままであるが、順位アルゴリズムによる距離ベースの候補の順位の代わりに、予想経路コスト(Expected Path Cost (EPC))と呼ばれる新しいコスト機能を用いる。各ノードに対するEPCは、以下の通り計算される。
1)統計的な空間接続性グラフ(Gstat)を出発点として用いる。
2)ノードがリアルタイムな情報を得る局所近傍に属するGstatのエッジは、Gstat+rtとなるリアルタイムな情報を反映するエッジによって取り除かれ、置きかえられる。これにより、利用可能な最も新しい情報を用いることを保証する。しかしながら、リアルタイムな情報が利用可能でない場合、プロトコルは、単独で統計的なデータを使用し続ける。
3)ノードと意図した送信先との間の最小EPC経路は、グラフGstat+rtに対して計算される。EPCは、経路を構成する全てのエッジに対する予想送信カウント(Expected Transmission Counts (ETXs))の総和として定義され、従って、全経路に対する予想送信カウントとなる。ETXは、リンク上でパケットをうまく移すための予想送信数を表し、リンクで観測されるパケット配送レートに基づく。それは、1/(PDRfw*PDRrv)と定義され、PDRfwは、リンクの順方向でのPDRであり、PDRrvは、逆方向でのPDRである。従って、EPCは、全ての経路リンクにわたってETXを足し合わせることで、各所定の経路に対して、自ノードから意図した送信先(エンドツーエンドのコスト)へパケットを配送するために、どの程度の送信が必要となるのかということの見積もりとなる。最小EPCは、最も低いEPCの経路に対して、自ノードから意図した送信先へパケットを配送するために、どの程度の送信が必要となるのかということ(エンドツーエンドのコスト)の見積もりとなる。一度リンクコストが確立されれば、例えば、良く知られたFloyd−Warshallアルゴリズムを用いて、最小コストの経路を計算できる。
従って、最も低い最小EPCのノードは、ベストな順位と最も高い転送優先度を与えられる。従って、ノードの有用性は、EPCと反比例して結合される。より低い順位を付けたノードを、先の実施形態のようにただのバックアップとして用いる。この方策は、局所近傍と他の位置に対する統計的なデータの両方に対するリアルタイムな情報を兼ね備える。これにより、プロトコルは、障害物を迂回してルートを決めることができ、配送確率を最大化し、同時にレイテンシを最小化する転送通路を選べる。

0105

実際問題としてプロトコルがどのように働くのかという例を図12に示す。この場合、目標は、SRCとDSTでマークされたセル間の最小コスト経路を見つけることである。簡単のために、全ての空間リンク/エッジは、単位コストを有し、現在、経路を評価しているノードはSRCセルにあるものと仮定する。統計的なマップは、マップの上部にわたって進むツーホップ経路として、最も短い(そして唯一の)経路を示す。しかしながら、リアルタイムな近傍情報は、統計的なデータによって予測された上部左のセルにネイバーがないことを示す。その後、プロトコルは、現存しないリンクを取り除き、リアルタイムな情報からのリンクに置きかえる。これにより、マップの下部に沿った3ホップ経路を見つけることができ、できない場合は、未検出状態となる。

0106

プロトコルを走らせるために、車両ノードは、802.11p通信をサポートする適正サイズのコンピュータ(例えば、Miktronik RB411UAHR)を搭載すべきである。

0107

空間接続性情報サーバーは、標準的なサーバーハードウェア及びソフトウェア(例えば、GNU/Linux(登録商標)で走るインテルベースのプロセッサ)を使用できる。ソフトウェア面では、データベースエンジン(例えば、MySQL)及びウェブサーバーが必要となる(例えば、Apache)。

0108

述べた方法は、移動する車両間の通信に基づくものであるが、駐車した車両又は車両通信性能を有する固定化したアクセスポイント(例えば、路側機(RSU))を用いた通信も含めることができる。

0109

駐車した車両又は固定化したアクセスポイントを含むネットワークに対するルーティング方策は、固定化した位置及びゼロ速度によって特徴付けられるいくつかのノードを単純に組み入れることで、移動する車両のみのネットワークに対するルーティング方策と同じである。適応又は修正なしに、本開示の方法によって、容易にこれらを用いることができる。

0110

さらに、静的なノードの存在は、移動するノードを構成するネットワークの一部として通信範囲を改善し、特に、戦略的地理的位置に駐車又は配置する場合、交差点及び建物のような障害物がある都会環境でルーティング方策を改善できる。

0111

上記の実施形態は、組合せ可能である。以下の従属項は、発明の特定の実施形態を提示する。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ