車両用通信を使用した分散交通ナビゲーション
車両用ネットワークにおける分散交通ナビゲーションのための方法を提示する。ネットワークに入る各車両において、車両用ネットワークに関係付けられた情報を取得し、記憶し、目的地アドレスをルート要求としてブロードキャストする。ネットワークにおける各車両において、車両間通信を通して記憶した情報を更新する。各ジャンクションにおいて、ブロードキャストを待ち受けて行列の存在を判定するヘッダ車両を選択する。行列が存在しない場合、ヘッダ車両の記憶した情報に基づいて、行列を初期化する。ヘッダ車両は、行列に基づいて道路区分上の移動時間をさらに推定し、区分移動時間およびルート要求に基づいてバックログ・インジケータを計算する。ヘッダ車両は、行列をさらに更新し、行列に基づいてルートを生成する。行列を、ヘッダ車両からブロードキャストする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、車両間通信、パーソナルナビゲーション、環境にやさしいルーティング、および交通渋滞回避などの自動車テレマティクスに関する。より詳細には、本発明は、中央ユニットから独立した、分散交通ナビゲーションのシステムおよび方法に関する。
【背景技術】
【０００２】
関連出願の相互参照
本発明は、共に２００９年８月１０日に出願された、米国特許仮出願第６１／２３２，５３６号明細書および米国特許仮出願第６１／２３２，５３８号明細書の利益を主張するものであり、その全内容および開示を、本明細書において十分に説明するように、参照により本明細書に援用する。
【０００３】
車両用交通の渋滞は、時間、金銭、および環境への影響に関して甚大な費用につながる。状況認識を通してその影響を軽減するために、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）、およびＴｏｔａｌ Ｔｒａｆｆｉｃ（登録商標）などのさまざまな交通サービスプロバイダが、交通情報およびルート情報を運転者に提供している。これらの情報プロバイダは、センサ、ＧＰＳプローブ、料金所データ、Ｂｌｕｅｔｏｏｔｈセンサなどのホストに依拠して、情報を収集する。収集した情報は、独自の方法を通して処理され、加入者に提示される。
【０００４】
図１は、渋滞情報を考慮に入れてルート計算を実装する、従来のインフラストラクチャベースの交通情報システム１００のアーキテクチャ図を示す。システム１００は、道路センサ、カメラ、プローブなどから交通データを収集するデータ取得層１０２を含む。収集したデータは、事故、道路工事などに関係していることがある。収集したデータは、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）などのサービスプロバイダによって提供可能な、中央ユニットを含む交通集約層１０４において、集約され、処理される。中央ユニットは、車道上の車両に対して短縮した移動時間ルートを計算する機能を含む、さまざまな機能を実行する。
【０００５】
交通集約層１０４によって処理されたデータは、続いて、たとえばＦＭラジオまたは衛星ラジオによって実装される無線配信層１０６を通して配信される。交通渋滞に関連した情報は、交通情報を運転者に伝える、車載ナビゲーションデバイス、スマートフォン、または移動電話を含むデバイス層１０８に供給される。
【０００６】
しかしながら、既存の交通ナビゲーションシステムでは、交通情報は主要道路に限定される。したがって、幹線道路および脇道上に流出したものに関連した情報は、ほとんど入手することができない。これは、ほとんどの状況下で、代わりのルートを提案する能力を限定する。主要道路上でさえ、情報を収集し、それをユーザに送信する時間が重大になる。さまざまな試みを使用して、統計的分布を収集したデータに当てはめる。しかしながら、特に短い時間フレーム内（たとえば、数分）では、正確さが低下する。
【０００７】
センサの状態に関する情報の欠如もまた、交通情報の集約に対して重大な課題を投げかける。これは、ＧＰＳプローブのステータス、その密度に関する情報、および事故、悪天候、道路条件、パーキング、短期間の渋滞などの他のローカルな条件に関する情報の欠如の結果である。これは、車道環境における動的な変化に応答すべき交通情報サービスの能力を著しく限定する。
【０００８】
さらに、すべての交通関連データを集中して収集するために、ルート計算などの目的で、すべての幹線道路およびローカルな道路からデータを集めることは極めて難しく、その結果、出発条件のみに基づいたルート計算となり、さまざまな道路または道路区分上の交通負荷の変化に対する適応が非常に限定される。
【０００９】
したがって、マルチホップの車両用ネットワークを活用してローカルな情報を集め、中央ユニットから独立して最短時間の移動経路をローカルに決定する、分散車両交通ナビゲーションのシステムおよび方法を提供することが望ましい。
【００１０】
さらに、プローブデータおよび／またはセンサデータの分散された情報集約に依拠して車道交通認識を構築し、交通情報プロバイダからのサービスを補完する、分散車両交通データ管理のシステムおよび方法を提供することが望ましい。
【発明の概要】
【００１１】
本発明の一態様に従って、車両用ネットワークにおける分散交通ナビゲーションのための方法を提供する。車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、道路区分上で運転される複数の車両を含む。当該方法は、ネットワークに入る各車両で、車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、目的地アドレスを生成するステップと、目的地アドレスをルート要求としてブロードキャストするステップとを含む。当該方法は、ネットワークにおける各車両で、少なくとも１つの通信可能な車両との通信を通して、記憶した情報を更新するステップをさらに含む。当該方法は、各ジャンクションで、ヘッダ車両を選択するステップと、ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、行列が存在しないとき、ヘッダ車両が、ヘッダ車両の記憶した情報に基づいて行列を初期化するステップと、ヘッダ車両が、行列に基づいて道路区分上の移動時間を推定するステップと、ヘッダ車両が、移動時間およびルート要求に基づいてバックログ・インジケータを計算するステップと、ヘッダ車両が、バックログ・インジケータに基づいて行列を更新するステップと、ヘッダ車両が、行列に基づいてルートを生成するステップと、ヘッダ車両が、行列をブロードキャストするステップとをさらに含む。
【００１２】
本明細書で説明する方法を実行するために、マシンによって実行可能な命令のプログラムを明確に具体化し、マシンによって読み取り可能な、コンピュータ可読媒体などのプログラム記憶デバイスもまた、提供することができる。
【図面の簡単な説明】
【００１３】
本発明の実施形態を非限定的に説明する目的で、注目すべき図面を参照して、本発明を以下の詳細な説明においてさらに説明し、図面では、同様の参照番号が、図面の全体を通して、同様の部品を表す。しかしながら、理解すべきように、本発明は、示される厳密な構成および手段には限定されない。
【００１４】
【図１】従来のインフラストラクチャベースの交通ナビゲーションシステムのアーキテクチャ図である。
【図２】車両間通信による分散車両交通ナビゲーションシステムのアーキテクチャ図である。
【図３】分散車両交通データ管理システムのハイレベル機能ブロック図である。
【図４ａ】車両用ネットワークの表現を示す図である。
【図４ｂ】ジャンクションをノードとし、道路区分をエッジとして、図４（ａ）に示すネットワークのモデル化したグラフである。
【図５】道路ネットワークを通る異なる交通フローを示すモデル化したグラフである。
【図６】行列を更新するための分散アルゴリズムを示す図である。
【図７】分散車両交通ナビゲーション方法のハイレベルフロー図である。
【図８】図７に示す分散車両交通ナビゲーション方法の詳細なフロー図である。
【発明を実施するための形態】
【００１５】
本発明は、車道上の車両に対して最短移動時間でのルートを計算する分散車両交通ナビゲーションのシステムおよび方法を有利に提供する。
【００１６】
図２は、本発明の例示的な実施形態に従った、車両間通信による分散車両交通ナビゲーションシステム２００のアーキテクチャ図を示す。システム２００は、道路センサ、カメラ、プローブなどから交通データを収集するデータ取得層２０２を含む。収集したデータは、事故、道路工事などに関係する場合がある。システム２００は、分散交通データルーティング層２０４をさらに含み、ここで、交通データは、すべての交通関連データの集中した集約を受けずに、車両間で通信され、やり取りされる。このようにしてローカルな情報を取得して、交通データを管理し、ナビゲートするシステムの能力を高めることができる。デバイス層２０６は、交通情報を運転者に伝える、スマートフォン、移動電話などの車載ナビゲーションデバイスを含む。
【００１７】
図３は、本発明の態様に従った、分散車両交通データ管理システム３００のハイレベル機能ブロック図を示す。詳細には、各車両で実行される動作が、分散データ管理スキームをサポートする。図３において、ブロック矢印は、情報フロー、クエリ、イベントトリガなどを意味し、線矢印は、情報フローを意味する。
【００１８】
ハイレベルにおいて、システム３００は、情報入力モジュール３１０と、情報記憶モジュール３２０（短期間または直近のデータベース３３０、および履歴データベース３４０を含む）と、データ解析モジュール３５０と、ルート計算モジュール３６０と、運転者情報モジュール３７０と、フィードバックモジュール３８０とを含む。
【００１９】
情報入力モジュール３１０は、一連のセンサ、運転者の選好、他の車両から受動的に入手した情報、ルックアップテーブルを介して他の車両から入手した情報などを含む。短期間または直近情報データベース３３０は、現在入手した情報、解析されている情報、および秒または分単位の時間依存の情報を記憶する。これには、たとえば、道路区分上の移動時間の現在の推定などを含むことができる。履歴データベース３４０は、信頼でき、かつ比較的安定している情報を記憶する。短期間情報は、数日から数週間で変わる公称の渋滞プロファイル、イベント更新、道路条件を含むことができる。長期間情報は、数ヶ月で変わる道路マップ、建設工事などを含むことができる。
【００２０】
データ解析モジュール３５０は、以下の機能を実行する。データ解析モジュール３５０は、時間の感度に基づいて情報をカテゴライズし、履歴データベース３４０に記憶する平均値を生成し、更新する。データ解析モジュール３５０は、たとえば、渋滞レベルの評価、公称の交通プロファイルから大きく外れるなどの外れ値の排除などを含む、情報の統計的解析を実行する。
【００２１】
ルート計算モジュール３６０は、交通渋滞プロファイルに関する情報、隣接する車両のルート、短期間に集約される渋滞に関する情報、などの交通データに基づいて、車両のための最適なルートを計算する機能を実行する。運転者情報モジュール３７０は、車道認識に対する情報を運転者に提供する機能を実行する。たとえば、運転者は、運転者情報モジュール３７０を通してルックアップテーブルから取り出される情報を要求することができる。フィードバックモジュール３８０は、運転者の観察、運転者の選好、および他の入力に基づいて、記憶した情報を更新する機能を実行する。
【００２２】
以下の表１は、車両におけるサンプル情報データベースを示す。
【００２３】
【表１】
【００２４】
データベースは、たとえば、テーブル形式とすることができ、ここで各行は、それぞれＡ、Ｂ、およびＣと名付けた情報属性に対応する。各行において、位置、地域、時間、その他などの補助的な情報を記憶する。テーブルは、交通、道路条件、パーキング、路面のくぼみ、安全、イベント、その他に関連した情報などの、新たな交通データが入手できるときに、即時に、またはリアルタイムに更新される。
【００２５】
しかしながら、本発明の趣旨から逸脱せずに、より複雑なデータベースを実現するためにさまざまな他の情報属性をテーブルにまとめることができ、データベースはまた、異なる記憶フォーマットで実装することができることを、当業者は理解すべきである。
【００２６】
上で説明した例示的な実施形態に従って、交通データ管理システム３００は、車道上に散在した情報を利用して、運転者に意味のある情報を提供する。当該情報は、運転者が入手できる前に、中央位置において集約され処理されていないので、車両間でやり取りされるデータの適時性および正確性を大幅に向上させることができ、それが結果として、迅速な応答および柔軟な適応となる。さらに、中央ユニットの地理的および論理的な制限なしに、近い期間の短距離の情報を運転者に提供することができる。
【００２７】
従来のインフラストラクチャベースのシステムと比較して、本発明に従った交通データ管理システム３００により実現される分散データの集約は、交通ネットワークから入手できる情報の質を実質的に向上させることができる。たとえば、車両交通渋滞予測のアプリケーションでは、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）、およびＴｏｔａｌ Ｔｒａｆｆｉｃ（登録商標）などの商業的に利用できるサービスプロバイダが、道路センサ、料金徴収所などを使用して、車両の分布を集める。しかしながら、車両の点密度から区分占有率への変換は、車両レベルの長さおよび運転行動情報にアクセスしないことには、依然として困難なタスクである。したがって、既存のサービスプロバイダによって提供される車両交通渋滞予測のアプリケーションは、依然として満足できるものではない。本発明の分散データ管理システムは、小規模地域において、車両レベルの長さおよび運転行動情報にアクセスすることができるので、はるかに正確な予測を達成することができる。
【００２８】
さらに、交通データ管理システム３００は、車両間の効率的なデータ通信を実現するために独立して使用できるだけではなく、運転者に動的な車道情報へのアクセスを提供することによって既存のシステムを補完し得るように、既存の交通ベースのナビゲーションシステムと両立して使用して、既存のシステムの機能性を高め、強化することもできる。
【００２９】
加えて、当該システムは、オンデマンド方式で情報をルックアップする能力を有し、それにより、バックエンドサーバインフラストラクチャでは入手できないことがある情報へのアクセスを運転者に提供し、運転者に、近い期間の短距離の情報にアクセスさせることを可能にする。
【００３０】
車両のための最短移動時間ルートを生成し、移動ルートを動的に更新するために使用されるシステムモデルを、以下のように定義する。
【００３１】
図４（ａ）は、車両用ネットワークの表現をグラフとして示し、図４（ｂ）は、図４（ａ）に示すネットワークのモデル化したグラフを示す。図４（ａ）および４（ｂ）において、道路区分をエッジとして示し、道路区分を、交差点および／またはインターチェンジなどの複数のジャンクションを通して接続し、ジャンクションをノードとして示す。本発明の車両用ネットワークは、ジャンクションを通して接続した道路区分と、道路区分上で運転する車両とを含む。図４（ａ）および４（ｂ）に示すエッジの方向は、通り（一方通行または対面通行）上の車両の方向である。大都市間の移動などのより大きなエリアを考える場合は、地理的地域を、主要道路をエッジとみなした頂点として扱うこともできる。用語、ジャンクションは、たとえば、道路交差点（一時停止標識および交通信号を含むがこれらに限定はしない）と、ハイウェイの道路インターチェンジ（ランプ、橋梁などを含むがこれらに限定はしない）とを含む。ジャンクションは、ｉおよびｊによってインデックス付けされ、ｉｊは、ｉとｊとの間の道路を意味する。
【００３２】
各道路区分ｉｊについて、いくつかのローカルなパラメータを定義する。
【００３３】
Ｄijは、道路区分ｉｊ上で経験される移動時間を意味する。
【００３４】
Ｃijは、道路区分ｉｊ上の単位時間当たりの車両の最大数を表すことにする。
【００３５】
Ｃijは、道路の長さ、レーンの数、速度規制、安全な車間距離などに依存していてもよい。Ｄijは、道路区分に入る車両の数、道路の長さ、レーンの数、速度規制、安全な車間距離などに依存する。車の長さは、点密度から区分占有率に正確に変換するために活用することができる追加的なパラメータである。このようなローカルな情報の入手しやすさにより、車両通信システムを使用して、既存の交通情報ソースからのサービスを補完する魅力が高まる。
【００３６】
さらに、各道路区分上の交通条件および道路条件は、時間とともに急速に変化することがあり、それらの条件は、既知の交通情報サービスによって提案される経路には反映されない。本発明に従ったシステムおよび方法は、変化する車道条件の影響、および異なる車両における決定間の相互依存を取り込みながら、移動時間を最小限にすることを保証するように、分散アルゴリズムを使用して近隣情報から動的に計算することによって、この問題に取り組む。
【００３７】
図５は、車両用ネットワークを通る異なる交通フローを示すモデル化したグラフを示す。図５において、ノードＳ1、Ｓ2、およびＳ3は、車両の出発点、すなわち、車両が道路ネットワークに入る点を意味し、ノードＤ1、Ｄ2、およびＤ3は、車両の目的地点、すなわち、車両が道路ネットワークを出ることをシステムが仮定する点を意味する。異なる出発点および目的地点を持つ非常に多くの車両が、ネットワーク中を移動する。車両が任意の所与の道路区分を通過する可能性は、意図する目的地、車両密度、掲示された速度制限、現在の速度、などの、複数の要因に依存する。
【００３８】
表２は、車両によって、維持され、各ジャンクションで更新される行列を示す。
【００３９】
【表２】
【００４０】
表２において、「目的地」は、１、２、および３と番号が付けられた目的地を意味する。各行は、名前Ａ、Ｂ、Ｃ、およびＤを持つ隣接するジャンクションに対応する。たとえば、現在のジャンクションにあり、目的地２に向かった車両を考える。Ｂ，２のエントリ（０．６）は、単位時間当たりの、ジャンクションＢに向かって進むはずである車両の数を示す。ジャンクションにおけるこのレートを、局所的なポーリングに基づいて制御することができる。
【００４１】
区分時間および収容能力は、アウトゴーイング道路区分のためのパラメータの推定値である。この行列は、反復ごとに非同期的に更新される。
【００４２】
図６は、表２で示した行列を更新するための分散アルゴリズムを示す。図６に示すアルゴリズムにおいて、Ｘkjrは、単位時間当たりの、目的地ｒを意図して車道ｋｊに入る、ジャンクションｋにおける車両の数を決定する変数を意味する。εは、出入りする交通量基づいて計算される。αは、各道路区分上の単位時間当たりの合計車両に基づいて計算され、ジャンクションにおいて計算されてもよい。ｆkrは、新たな車両がジャンクションｋに到着して目的地ｒに向かうレートである。ｇkrは、ジャンクションｋにある車両がその目的地ｒに達するレートである。
【００４３】
したがって、ｋ≠のとき、ｇkr＝０である。ｆkrおよびｇkrは、共に局所的に既知である。Ｃkjは、最小速度レベルを保証するために、車道ｋｊにおける単位時間当たりの車両の最大数を表す。Ｃkjは、道路の長さ、レーンの数、安全な車間距離などの関数であってよい。Ｄkjは、ｋからｊに移動するための時間の現在の推定を表し、道路区分に入る車両、ならびに道路の長さ、レーンの数、道路条件などの関数である。Ｄ’kjは、交通フローレートに対する移動時間関数の導関数を意味する。γは、移動時間の最小導関数よりも大きい任意の数字であってよい。関数が微分可能でない点において、仮定は劣勾配の場合に成り立つ。
【００４４】
変数Ｘkjn,rは、ｎ番目の反復におけるＸkjrの値である。［・］＋は、［０，∞］での予測を意味する。Ｄ’kjが微分可能でない点では、劣勾配を代わりに使用する。反復計算は、現在ジャンクションにある車両によって、ジャンクションでのみ実行される。反復ｎにおいて、バックログ・インジケータεnr,kを、ジャンクションで計算する。インジケータを、２ビットのみを使用して表すことができ、車両転送を通して隣接するジャンクションにのみ通信する必要がある。アウトゴーイング道路区分上の現在の渋滞推定に基づいて、単一ビット渋滞インジケータαnkjを、ジャンクションで計算する。
【００４５】
計算を、異なるジャンクションの車両で非同期的に行うことができ、これが時刻同期の必要性を排除することに留意することが重要である。さらに、計算は、車両間通信により集めることができる局所的な情報にのみ依存している。
【００４６】
プロトコルステップは、以下の通りである。
システムに入る車両で、
１）目的地アドレスをルート要求として周期的にブロードキャストする。
目的地における車両で、
１）システムを出る前に、退出メッセージをブロードキャストする。
ジャンクション付近の／ジャンクションでの車両で、
１）車両は、オンボードマップおよびＧＰＳ情報を通してジャンクションの位置を知る。
２）たとえば、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて、ヘッダ車両（ＨＶ）として車両を選択する。
３）ジャンクションの行列ブロードキャストを待ち受ける。ブロードキャストを受信しない場合、ＨＶは、行列を初期化し、アウトゴーイング道路区分上で経験される移動時間を推定する。ルート要求を維持する。
４）ＨＶは、経験される移動時間、およびすべての車両からの現在のルート要求に基づいて、バックログを計算する。
５）図６に示す分散アルゴリズムに従って、行列を更新する。
６）ＨＶは、行列のレートに基づいて、ルートを選択し、ルートを隣接する車両に割り当てる。
７）ＨＶは、次の目的地に到着するまで、周期的な間隔で行列をブロードキャストする。
【００４７】
図７は、本発明の方法のハイレベルフロー図である。ステップＡ１で、アウトゴーイング道路区分に対するレートを、車両間メッセージを通して計算する。加えて、車両は、フローレートを知ることにつながる、前のジャンクションに向かう移動時間を返信し、これが結果として、各アウトゴーイング道路区分で経験される移動時間の変更の推定となる。ステップＡ２で、行列を維持し、更新するために、ジャンクションにおける任意の車両をランダムに選択することができる。当該車両はジャンクションを出る間に、別の車両に行列を引き渡す。このステップにおける初期化を、ナビゲーションデバイスによって提供される通常の経路情報に基づいて実行することができ、これにより、収束が大幅に加速することになる。さらに、セクタに基づく階層的な様式でのルート計算が、行列に維持されている状態情報を大幅に減らし、すなわち、各セクタは、一組の配列されたジャンクションを含むことができる。ステップＡ３で、図６に示す分散アルゴリズムに従って行列を更新し、行列の内容に基づいて最適な移動ルートを選択する。ステップＡ４で、異なるジャンクション（次のジャンクションなど）で、行列が存在するかどうかを判定する。行列が存在する場合、プロセスは、行列を更新するステップＡ３に進み、そうでない場合、プロセスは行列を初期化するステップＡ２に進む。
【００４８】
図８は、本発明の方法に従った詳細なステップを示すフロー図である。車両用ネットワークに入る車両において、ステップＳ１で、送信するデータを入手することができる。ステップＳ２で、当該車両は、車両用ネットワークに関連付けられた情報を取得し、記憶し、当該情報は、車両用ネットワークの交通量および渋滞レベルなどを含むが、これらに限定はしない。ステップＳ３で、入る車両によって目的地アドレスを生成し、続いてステップＳ４で、目的地アドレスを、ルート要求としてブロードキャストする。ステップＳ５で、道路ネットワークに入る車両は、アプリケーションからの追加のデータを待つ。
【００４９】
任意選択で、目的地におりシステムを出ようとするとみなされる車両において、ステップＳ６で、送信するデータを入手することできる。ステップＳ７で、システムを出る車両が、退出メッセージをブロードキャストする。ステップＳ８で、システムを出る車両は、アプリケーションからの追加のデータを待つ。
【００５０】
ジャンクションにある車両において、ステップＳ９で、送信するデータを入手することができる。ジャンクションの車両において、複数の分散されたタスクを実行し、この際ジャンクションにある各車両は、オンボードマップおよびＧＰＳ情報を通して、その位置を入手する。車両の位置を判定する他の方法もまた使用することができる。ステップＳ１０で、ヘッダ車両（ＨＶ）としての車両を選択する。選択を、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行することができる。他の選択の方法もまた使用することができる。ステップＳ１１で、ＨＶは、行列によるブロードキャストを待ち受ける。ステップＳ１２で、ブロードキャストを受信していないと判定した場合、すなわち、行列が存在しない場合（Ｓ１２＝いいえ）、ステップＳ１３で、行列を初期化する。引き続きステップＳ１４で、ＨＶは、行列に基づいて、道路区分上の移動時間を推定する。ブロードキャストを受信した場合、すなわち、行列が存在する場合（Ｓ１２＝はい）、プロセスはステップＳ１４に進む。
【００５１】
ステップＳ１５で、ＨＶは、道路区分上で経験される移動時間およびルート要求に基づいて、バックログ・インジケータを計算する。ステップＳ１６で、ＨＶは、バックログ・インジケータを考慮しながら、図６に示す分散アルゴリズムに従って行列を更新する。
【００５２】
ステップＳ１７で、行列の内容に基づいて、最適な移動ルートをＨＶによって生成し、当該ルートを隣接する車両に割り当てる。ステップＳ１８で、ＨＶが次のジャンクションに到着するまで、ＨＶは、周期的な間隔で行列をブロードキャストする。
【００５３】
本発明は、異なる道路区分における条件に基づいて動的に更新するルート計算を可能にする利益を提供する。その方法は、車両間通信を活用して、局所的な近隣における渋滞情報の限定された普及を実現する。渋滞状況においては、転送する車両が入手しやすいため、車両間通信が上手く機能する。車両がまばらである状況においては、車両間での転送は不十分になるが、渋滞は自動的に緩和される。したがって、車両間通信は、渋滞情報を普及させるための自然な選択となる。
【００５４】
先行のソリューションは、ルート計算のためにすべての情報を中央位置において集約する。これが結果として、遅い応答となり、ルートの適応を欠くことになる。さらに、より激しい交通渋滞のために、大量の数の要求が生成されることがあり、このようなシステムは、ネットワークインフラストラクチャの重い負荷のために十分に機能しないことがある。
【００５５】
本開示のさまざまな態様を、コンピュータ、プロセッサ、および／またはマシン上で実行するとき、コンピュータまたはマシンに方法のステップを実行させる、コンピュータ、またはマシンで使用可能なもしくは読み取り可能な媒体において具体化されるプログラム、ソフトウェア、またはコンピュータ命令として具体化することができる。本開示において説明するさまざまな機能性および方法を実行するために、マシンによって実行可能な命令のプログラムを明確に具体化し、マシンによって読み取り可能な、プログラム記憶デバイスもまた提供する。
【００５６】
本開示のシステムおよび方法を、汎用コンピュータシステムまたは特殊用途コンピュータシステム上で実装し、動作させることができる。コンピュータシステムは、既知の任意のタイプとすることができ、または既知のシステムであり、一般に、プロセッサ、メモリデバイス、記憶デバイス、入力／出力デバイス、内部バス、および／または、通信ハードウェアおよびソフトウェアと連携して他のコンピュータシステムと通信する通信インターフェースなどを含むことができる。
【００５７】
用語「コンピュータシステム」および「コンピュータネットワーク」を、本出願において使用する場合、固定された、および／または持ち運び可能なコンピュータハードウェア、ソフトウェア、周辺装置、および記憶デバイスのさまざまな組合せを含むことができる。コンピュータシステムは、協働して機能するようにネットワーク化された、または他の方法でリンクされた複数の個々のコンポーネントを含むことができ、または１つもしくは複数のスタンドアローンコンポーネントを含むことができる。本出願のコンピュータシステムのハードウェアコンポーネントおよびソフトウェアコンポーネントは、デスクトップ、ラップトップ、およびサーバなどの、固定された、および持ち運び可能なデバイスを含むことができ、それらの中に含まれてもよい。モジュールは、ソフトウェア、ハードウェア、ファームウェア、電子回路、またはその他として具体化され得るいくつかの「機能性」を実装するデバイス、ソフトウェア、プログラム、またはシステムのコンポーネントとすることができる。
【００５８】
上で説明した実施形態は、説明のための例であり、本発明がこれらの特定の実施形態に限定されると解釈するべきではない。したがって、添付の特許請求の範囲において定義される通りの本発明の趣旨または範囲から逸脱せずに、さまざまな変更形態および修正形態を、当業者がもたらすことができる。
【技術分野】
【０００１】
本発明は、一般に、車両間通信、パーソナルナビゲーション、環境にやさしいルーティング、および交通渋滞回避などの自動車テレマティクスに関する。より詳細には、本発明は、中央ユニットから独立した、分散交通ナビゲーションのシステムおよび方法に関する。
【背景技術】
【０００２】
関連出願の相互参照
本発明は、共に２００９年８月１０日に出願された、米国特許仮出願第６１／２３２，５３６号明細書および米国特許仮出願第６１／２３２，５３８号明細書の利益を主張するものであり、その全内容および開示を、本明細書において十分に説明するように、参照により本明細書に援用する。
【０００３】
車両用交通の渋滞は、時間、金銭、および環境への影響に関して甚大な費用につながる。状況認識を通してその影響を軽減するために、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）、およびＴｏｔａｌ Ｔｒａｆｆｉｃ（登録商標）などのさまざまな交通サービスプロバイダが、交通情報およびルート情報を運転者に提供している。これらの情報プロバイダは、センサ、ＧＰＳプローブ、料金所データ、Ｂｌｕｅｔｏｏｔｈセンサなどのホストに依拠して、情報を収集する。収集した情報は、独自の方法を通して処理され、加入者に提示される。
【０００４】
図１は、渋滞情報を考慮に入れてルート計算を実装する、従来のインフラストラクチャベースの交通情報システム１００のアーキテクチャ図を示す。システム１００は、道路センサ、カメラ、プローブなどから交通データを収集するデータ取得層１０２を含む。収集したデータは、事故、道路工事などに関係していることがある。収集したデータは、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）などのサービスプロバイダによって提供可能な、中央ユニットを含む交通集約層１０４において、集約され、処理される。中央ユニットは、車道上の車両に対して短縮した移動時間ルートを計算する機能を含む、さまざまな機能を実行する。
【０００５】
交通集約層１０４によって処理されたデータは、続いて、たとえばＦＭラジオまたは衛星ラジオによって実装される無線配信層１０６を通して配信される。交通渋滞に関連した情報は、交通情報を運転者に伝える、車載ナビゲーションデバイス、スマートフォン、または移動電話を含むデバイス層１０８に供給される。
【０００６】
しかしながら、既存の交通ナビゲーションシステムでは、交通情報は主要道路に限定される。したがって、幹線道路および脇道上に流出したものに関連した情報は、ほとんど入手することができない。これは、ほとんどの状況下で、代わりのルートを提案する能力を限定する。主要道路上でさえ、情報を収集し、それをユーザに送信する時間が重大になる。さまざまな試みを使用して、統計的分布を収集したデータに当てはめる。しかしながら、特に短い時間フレーム内（たとえば、数分）では、正確さが低下する。
【０００７】
センサの状態に関する情報の欠如もまた、交通情報の集約に対して重大な課題を投げかける。これは、ＧＰＳプローブのステータス、その密度に関する情報、および事故、悪天候、道路条件、パーキング、短期間の渋滞などの他のローカルな条件に関する情報の欠如の結果である。これは、車道環境における動的な変化に応答すべき交通情報サービスの能力を著しく限定する。
【０００８】
さらに、すべての交通関連データを集中して収集するために、ルート計算などの目的で、すべての幹線道路およびローカルな道路からデータを集めることは極めて難しく、その結果、出発条件のみに基づいたルート計算となり、さまざまな道路または道路区分上の交通負荷の変化に対する適応が非常に限定される。
【０００９】
したがって、マルチホップの車両用ネットワークを活用してローカルな情報を集め、中央ユニットから独立して最短時間の移動経路をローカルに決定する、分散車両交通ナビゲーションのシステムおよび方法を提供することが望ましい。
【００１０】
さらに、プローブデータおよび／またはセンサデータの分散された情報集約に依拠して車道交通認識を構築し、交通情報プロバイダからのサービスを補完する、分散車両交通データ管理のシステムおよび方法を提供することが望ましい。
【発明の概要】
【００１１】
本発明の一態様に従って、車両用ネットワークにおける分散交通ナビゲーションのための方法を提供する。車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、道路区分上で運転される複数の車両を含む。当該方法は、ネットワークに入る各車両で、車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、目的地アドレスを生成するステップと、目的地アドレスをルート要求としてブロードキャストするステップとを含む。当該方法は、ネットワークにおける各車両で、少なくとも１つの通信可能な車両との通信を通して、記憶した情報を更新するステップをさらに含む。当該方法は、各ジャンクションで、ヘッダ車両を選択するステップと、ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、行列が存在しないとき、ヘッダ車両が、ヘッダ車両の記憶した情報に基づいて行列を初期化するステップと、ヘッダ車両が、行列に基づいて道路区分上の移動時間を推定するステップと、ヘッダ車両が、移動時間およびルート要求に基づいてバックログ・インジケータを計算するステップと、ヘッダ車両が、バックログ・インジケータに基づいて行列を更新するステップと、ヘッダ車両が、行列に基づいてルートを生成するステップと、ヘッダ車両が、行列をブロードキャストするステップとをさらに含む。
【００１２】
本明細書で説明する方法を実行するために、マシンによって実行可能な命令のプログラムを明確に具体化し、マシンによって読み取り可能な、コンピュータ可読媒体などのプログラム記憶デバイスもまた、提供することができる。
【図面の簡単な説明】
【００１３】
本発明の実施形態を非限定的に説明する目的で、注目すべき図面を参照して、本発明を以下の詳細な説明においてさらに説明し、図面では、同様の参照番号が、図面の全体を通して、同様の部品を表す。しかしながら、理解すべきように、本発明は、示される厳密な構成および手段には限定されない。
【００１４】
【図１】従来のインフラストラクチャベースの交通ナビゲーションシステムのアーキテクチャ図である。
【図２】車両間通信による分散車両交通ナビゲーションシステムのアーキテクチャ図である。
【図３】分散車両交通データ管理システムのハイレベル機能ブロック図である。
【図４ａ】車両用ネットワークの表現を示す図である。
【図４ｂ】ジャンクションをノードとし、道路区分をエッジとして、図４（ａ）に示すネットワークのモデル化したグラフである。
【図５】道路ネットワークを通る異なる交通フローを示すモデル化したグラフである。
【図６】行列を更新するための分散アルゴリズムを示す図である。
【図７】分散車両交通ナビゲーション方法のハイレベルフロー図である。
【図８】図７に示す分散車両交通ナビゲーション方法の詳細なフロー図である。
【発明を実施するための形態】
【００１５】
本発明は、車道上の車両に対して最短移動時間でのルートを計算する分散車両交通ナビゲーションのシステムおよび方法を有利に提供する。
【００１６】
図２は、本発明の例示的な実施形態に従った、車両間通信による分散車両交通ナビゲーションシステム２００のアーキテクチャ図を示す。システム２００は、道路センサ、カメラ、プローブなどから交通データを収集するデータ取得層２０２を含む。収集したデータは、事故、道路工事などに関係する場合がある。システム２００は、分散交通データルーティング層２０４をさらに含み、ここで、交通データは、すべての交通関連データの集中した集約を受けずに、車両間で通信され、やり取りされる。このようにしてローカルな情報を取得して、交通データを管理し、ナビゲートするシステムの能力を高めることができる。デバイス層２０６は、交通情報を運転者に伝える、スマートフォン、移動電話などの車載ナビゲーションデバイスを含む。
【００１７】
図３は、本発明の態様に従った、分散車両交通データ管理システム３００のハイレベル機能ブロック図を示す。詳細には、各車両で実行される動作が、分散データ管理スキームをサポートする。図３において、ブロック矢印は、情報フロー、クエリ、イベントトリガなどを意味し、線矢印は、情報フローを意味する。
【００１８】
ハイレベルにおいて、システム３００は、情報入力モジュール３１０と、情報記憶モジュール３２０（短期間または直近のデータベース３３０、および履歴データベース３４０を含む）と、データ解析モジュール３５０と、ルート計算モジュール３６０と、運転者情報モジュール３７０と、フィードバックモジュール３８０とを含む。
【００１９】
情報入力モジュール３１０は、一連のセンサ、運転者の選好、他の車両から受動的に入手した情報、ルックアップテーブルを介して他の車両から入手した情報などを含む。短期間または直近情報データベース３３０は、現在入手した情報、解析されている情報、および秒または分単位の時間依存の情報を記憶する。これには、たとえば、道路区分上の移動時間の現在の推定などを含むことができる。履歴データベース３４０は、信頼でき、かつ比較的安定している情報を記憶する。短期間情報は、数日から数週間で変わる公称の渋滞プロファイル、イベント更新、道路条件を含むことができる。長期間情報は、数ヶ月で変わる道路マップ、建設工事などを含むことができる。
【００２０】
データ解析モジュール３５０は、以下の機能を実行する。データ解析モジュール３５０は、時間の感度に基づいて情報をカテゴライズし、履歴データベース３４０に記憶する平均値を生成し、更新する。データ解析モジュール３５０は、たとえば、渋滞レベルの評価、公称の交通プロファイルから大きく外れるなどの外れ値の排除などを含む、情報の統計的解析を実行する。
【００２１】
ルート計算モジュール３６０は、交通渋滞プロファイルに関する情報、隣接する車両のルート、短期間に集約される渋滞に関する情報、などの交通データに基づいて、車両のための最適なルートを計算する機能を実行する。運転者情報モジュール３７０は、車道認識に対する情報を運転者に提供する機能を実行する。たとえば、運転者は、運転者情報モジュール３７０を通してルックアップテーブルから取り出される情報を要求することができる。フィードバックモジュール３８０は、運転者の観察、運転者の選好、および他の入力に基づいて、記憶した情報を更新する機能を実行する。
【００２２】
以下の表１は、車両におけるサンプル情報データベースを示す。
【００２３】
【表１】
【００２４】
データベースは、たとえば、テーブル形式とすることができ、ここで各行は、それぞれＡ、Ｂ、およびＣと名付けた情報属性に対応する。各行において、位置、地域、時間、その他などの補助的な情報を記憶する。テーブルは、交通、道路条件、パーキング、路面のくぼみ、安全、イベント、その他に関連した情報などの、新たな交通データが入手できるときに、即時に、またはリアルタイムに更新される。
【００２５】
しかしながら、本発明の趣旨から逸脱せずに、より複雑なデータベースを実現するためにさまざまな他の情報属性をテーブルにまとめることができ、データベースはまた、異なる記憶フォーマットで実装することができることを、当業者は理解すべきである。
【００２６】
上で説明した例示的な実施形態に従って、交通データ管理システム３００は、車道上に散在した情報を利用して、運転者に意味のある情報を提供する。当該情報は、運転者が入手できる前に、中央位置において集約され処理されていないので、車両間でやり取りされるデータの適時性および正確性を大幅に向上させることができ、それが結果として、迅速な応答および柔軟な適応となる。さらに、中央ユニットの地理的および論理的な制限なしに、近い期間の短距離の情報を運転者に提供することができる。
【００２７】
従来のインフラストラクチャベースのシステムと比較して、本発明に従った交通データ管理システム３００により実現される分散データの集約は、交通ネットワークから入手できる情報の質を実質的に向上させることができる。たとえば、車両交通渋滞予測のアプリケーションでは、Ｎａｖｔｅｑ（登録商標）、Ｉｎｒｉｘ（登録商標）、およびＴｏｔａｌ Ｔｒａｆｆｉｃ（登録商標）などの商業的に利用できるサービスプロバイダが、道路センサ、料金徴収所などを使用して、車両の分布を集める。しかしながら、車両の点密度から区分占有率への変換は、車両レベルの長さおよび運転行動情報にアクセスしないことには、依然として困難なタスクである。したがって、既存のサービスプロバイダによって提供される車両交通渋滞予測のアプリケーションは、依然として満足できるものではない。本発明の分散データ管理システムは、小規模地域において、車両レベルの長さおよび運転行動情報にアクセスすることができるので、はるかに正確な予測を達成することができる。
【００２８】
さらに、交通データ管理システム３００は、車両間の効率的なデータ通信を実現するために独立して使用できるだけではなく、運転者に動的な車道情報へのアクセスを提供することによって既存のシステムを補完し得るように、既存の交通ベースのナビゲーションシステムと両立して使用して、既存のシステムの機能性を高め、強化することもできる。
【００２９】
加えて、当該システムは、オンデマンド方式で情報をルックアップする能力を有し、それにより、バックエンドサーバインフラストラクチャでは入手できないことがある情報へのアクセスを運転者に提供し、運転者に、近い期間の短距離の情報にアクセスさせることを可能にする。
【００３０】
車両のための最短移動時間ルートを生成し、移動ルートを動的に更新するために使用されるシステムモデルを、以下のように定義する。
【００３１】
図４（ａ）は、車両用ネットワークの表現をグラフとして示し、図４（ｂ）は、図４（ａ）に示すネットワークのモデル化したグラフを示す。図４（ａ）および４（ｂ）において、道路区分をエッジとして示し、道路区分を、交差点および／またはインターチェンジなどの複数のジャンクションを通して接続し、ジャンクションをノードとして示す。本発明の車両用ネットワークは、ジャンクションを通して接続した道路区分と、道路区分上で運転する車両とを含む。図４（ａ）および４（ｂ）に示すエッジの方向は、通り（一方通行または対面通行）上の車両の方向である。大都市間の移動などのより大きなエリアを考える場合は、地理的地域を、主要道路をエッジとみなした頂点として扱うこともできる。用語、ジャンクションは、たとえば、道路交差点（一時停止標識および交通信号を含むがこれらに限定はしない）と、ハイウェイの道路インターチェンジ（ランプ、橋梁などを含むがこれらに限定はしない）とを含む。ジャンクションは、ｉおよびｊによってインデックス付けされ、ｉｊは、ｉとｊとの間の道路を意味する。
【００３２】
各道路区分ｉｊについて、いくつかのローカルなパラメータを定義する。
【００３３】
Ｄijは、道路区分ｉｊ上で経験される移動時間を意味する。
【００３４】
Ｃijは、道路区分ｉｊ上の単位時間当たりの車両の最大数を表すことにする。
【００３５】
Ｃijは、道路の長さ、レーンの数、速度規制、安全な車間距離などに依存していてもよい。Ｄijは、道路区分に入る車両の数、道路の長さ、レーンの数、速度規制、安全な車間距離などに依存する。車の長さは、点密度から区分占有率に正確に変換するために活用することができる追加的なパラメータである。このようなローカルな情報の入手しやすさにより、車両通信システムを使用して、既存の交通情報ソースからのサービスを補完する魅力が高まる。
【００３６】
さらに、各道路区分上の交通条件および道路条件は、時間とともに急速に変化することがあり、それらの条件は、既知の交通情報サービスによって提案される経路には反映されない。本発明に従ったシステムおよび方法は、変化する車道条件の影響、および異なる車両における決定間の相互依存を取り込みながら、移動時間を最小限にすることを保証するように、分散アルゴリズムを使用して近隣情報から動的に計算することによって、この問題に取り組む。
【００３７】
図５は、車両用ネットワークを通る異なる交通フローを示すモデル化したグラフを示す。図５において、ノードＳ1、Ｓ2、およびＳ3は、車両の出発点、すなわち、車両が道路ネットワークに入る点を意味し、ノードＤ1、Ｄ2、およびＤ3は、車両の目的地点、すなわち、車両が道路ネットワークを出ることをシステムが仮定する点を意味する。異なる出発点および目的地点を持つ非常に多くの車両が、ネットワーク中を移動する。車両が任意の所与の道路区分を通過する可能性は、意図する目的地、車両密度、掲示された速度制限、現在の速度、などの、複数の要因に依存する。
【００３８】
表２は、車両によって、維持され、各ジャンクションで更新される行列を示す。
【００３９】
【表２】
【００４０】
表２において、「目的地」は、１、２、および３と番号が付けられた目的地を意味する。各行は、名前Ａ、Ｂ、Ｃ、およびＤを持つ隣接するジャンクションに対応する。たとえば、現在のジャンクションにあり、目的地２に向かった車両を考える。Ｂ，２のエントリ（０．６）は、単位時間当たりの、ジャンクションＢに向かって進むはずである車両の数を示す。ジャンクションにおけるこのレートを、局所的なポーリングに基づいて制御することができる。
【００４１】
区分時間および収容能力は、アウトゴーイング道路区分のためのパラメータの推定値である。この行列は、反復ごとに非同期的に更新される。
【００４２】
図６は、表２で示した行列を更新するための分散アルゴリズムを示す。図６に示すアルゴリズムにおいて、Ｘkjrは、単位時間当たりの、目的地ｒを意図して車道ｋｊに入る、ジャンクションｋにおける車両の数を決定する変数を意味する。εは、出入りする交通量基づいて計算される。αは、各道路区分上の単位時間当たりの合計車両に基づいて計算され、ジャンクションにおいて計算されてもよい。ｆkrは、新たな車両がジャンクションｋに到着して目的地ｒに向かうレートである。ｇkrは、ジャンクションｋにある車両がその目的地ｒに達するレートである。
【００４３】
したがって、ｋ≠のとき、ｇkr＝０である。ｆkrおよびｇkrは、共に局所的に既知である。Ｃkjは、最小速度レベルを保証するために、車道ｋｊにおける単位時間当たりの車両の最大数を表す。Ｃkjは、道路の長さ、レーンの数、安全な車間距離などの関数であってよい。Ｄkjは、ｋからｊに移動するための時間の現在の推定を表し、道路区分に入る車両、ならびに道路の長さ、レーンの数、道路条件などの関数である。Ｄ’kjは、交通フローレートに対する移動時間関数の導関数を意味する。γは、移動時間の最小導関数よりも大きい任意の数字であってよい。関数が微分可能でない点において、仮定は劣勾配の場合に成り立つ。
【００４４】
変数Ｘkjn,rは、ｎ番目の反復におけるＸkjrの値である。［・］＋は、［０，∞］での予測を意味する。Ｄ’kjが微分可能でない点では、劣勾配を代わりに使用する。反復計算は、現在ジャンクションにある車両によって、ジャンクションでのみ実行される。反復ｎにおいて、バックログ・インジケータεnr,kを、ジャンクションで計算する。インジケータを、２ビットのみを使用して表すことができ、車両転送を通して隣接するジャンクションにのみ通信する必要がある。アウトゴーイング道路区分上の現在の渋滞推定に基づいて、単一ビット渋滞インジケータαnkjを、ジャンクションで計算する。
【００４５】
計算を、異なるジャンクションの車両で非同期的に行うことができ、これが時刻同期の必要性を排除することに留意することが重要である。さらに、計算は、車両間通信により集めることができる局所的な情報にのみ依存している。
【００４６】
プロトコルステップは、以下の通りである。
システムに入る車両で、
１）目的地アドレスをルート要求として周期的にブロードキャストする。
目的地における車両で、
１）システムを出る前に、退出メッセージをブロードキャストする。
ジャンクション付近の／ジャンクションでの車両で、
１）車両は、オンボードマップおよびＧＰＳ情報を通してジャンクションの位置を知る。
２）たとえば、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて、ヘッダ車両（ＨＶ）として車両を選択する。
３）ジャンクションの行列ブロードキャストを待ち受ける。ブロードキャストを受信しない場合、ＨＶは、行列を初期化し、アウトゴーイング道路区分上で経験される移動時間を推定する。ルート要求を維持する。
４）ＨＶは、経験される移動時間、およびすべての車両からの現在のルート要求に基づいて、バックログを計算する。
５）図６に示す分散アルゴリズムに従って、行列を更新する。
６）ＨＶは、行列のレートに基づいて、ルートを選択し、ルートを隣接する車両に割り当てる。
７）ＨＶは、次の目的地に到着するまで、周期的な間隔で行列をブロードキャストする。
【００４７】
図７は、本発明の方法のハイレベルフロー図である。ステップＡ１で、アウトゴーイング道路区分に対するレートを、車両間メッセージを通して計算する。加えて、車両は、フローレートを知ることにつながる、前のジャンクションに向かう移動時間を返信し、これが結果として、各アウトゴーイング道路区分で経験される移動時間の変更の推定となる。ステップＡ２で、行列を維持し、更新するために、ジャンクションにおける任意の車両をランダムに選択することができる。当該車両はジャンクションを出る間に、別の車両に行列を引き渡す。このステップにおける初期化を、ナビゲーションデバイスによって提供される通常の経路情報に基づいて実行することができ、これにより、収束が大幅に加速することになる。さらに、セクタに基づく階層的な様式でのルート計算が、行列に維持されている状態情報を大幅に減らし、すなわち、各セクタは、一組の配列されたジャンクションを含むことができる。ステップＡ３で、図６に示す分散アルゴリズムに従って行列を更新し、行列の内容に基づいて最適な移動ルートを選択する。ステップＡ４で、異なるジャンクション（次のジャンクションなど）で、行列が存在するかどうかを判定する。行列が存在する場合、プロセスは、行列を更新するステップＡ３に進み、そうでない場合、プロセスは行列を初期化するステップＡ２に進む。
【００４８】
図８は、本発明の方法に従った詳細なステップを示すフロー図である。車両用ネットワークに入る車両において、ステップＳ１で、送信するデータを入手することができる。ステップＳ２で、当該車両は、車両用ネットワークに関連付けられた情報を取得し、記憶し、当該情報は、車両用ネットワークの交通量および渋滞レベルなどを含むが、これらに限定はしない。ステップＳ３で、入る車両によって目的地アドレスを生成し、続いてステップＳ４で、目的地アドレスを、ルート要求としてブロードキャストする。ステップＳ５で、道路ネットワークに入る車両は、アプリケーションからの追加のデータを待つ。
【００４９】
任意選択で、目的地におりシステムを出ようとするとみなされる車両において、ステップＳ６で、送信するデータを入手することできる。ステップＳ７で、システムを出る車両が、退出メッセージをブロードキャストする。ステップＳ８で、システムを出る車両は、アプリケーションからの追加のデータを待つ。
【００５０】
ジャンクションにある車両において、ステップＳ９で、送信するデータを入手することができる。ジャンクションの車両において、複数の分散されたタスクを実行し、この際ジャンクションにある各車両は、オンボードマップおよびＧＰＳ情報を通して、その位置を入手する。車両の位置を判定する他の方法もまた使用することができる。ステップＳ１０で、ヘッダ車両（ＨＶ）としての車両を選択する。選択を、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行することができる。他の選択の方法もまた使用することができる。ステップＳ１１で、ＨＶは、行列によるブロードキャストを待ち受ける。ステップＳ１２で、ブロードキャストを受信していないと判定した場合、すなわち、行列が存在しない場合（Ｓ１２＝いいえ）、ステップＳ１３で、行列を初期化する。引き続きステップＳ１４で、ＨＶは、行列に基づいて、道路区分上の移動時間を推定する。ブロードキャストを受信した場合、すなわち、行列が存在する場合（Ｓ１２＝はい）、プロセスはステップＳ１４に進む。
【００５１】
ステップＳ１５で、ＨＶは、道路区分上で経験される移動時間およびルート要求に基づいて、バックログ・インジケータを計算する。ステップＳ１６で、ＨＶは、バックログ・インジケータを考慮しながら、図６に示す分散アルゴリズムに従って行列を更新する。
【００５２】
ステップＳ１７で、行列の内容に基づいて、最適な移動ルートをＨＶによって生成し、当該ルートを隣接する車両に割り当てる。ステップＳ１８で、ＨＶが次のジャンクションに到着するまで、ＨＶは、周期的な間隔で行列をブロードキャストする。
【００５３】
本発明は、異なる道路区分における条件に基づいて動的に更新するルート計算を可能にする利益を提供する。その方法は、車両間通信を活用して、局所的な近隣における渋滞情報の限定された普及を実現する。渋滞状況においては、転送する車両が入手しやすいため、車両間通信が上手く機能する。車両がまばらである状況においては、車両間での転送は不十分になるが、渋滞は自動的に緩和される。したがって、車両間通信は、渋滞情報を普及させるための自然な選択となる。
【００５４】
先行のソリューションは、ルート計算のためにすべての情報を中央位置において集約する。これが結果として、遅い応答となり、ルートの適応を欠くことになる。さらに、より激しい交通渋滞のために、大量の数の要求が生成されることがあり、このようなシステムは、ネットワークインフラストラクチャの重い負荷のために十分に機能しないことがある。
【００５５】
本開示のさまざまな態様を、コンピュータ、プロセッサ、および／またはマシン上で実行するとき、コンピュータまたはマシンに方法のステップを実行させる、コンピュータ、またはマシンで使用可能なもしくは読み取り可能な媒体において具体化されるプログラム、ソフトウェア、またはコンピュータ命令として具体化することができる。本開示において説明するさまざまな機能性および方法を実行するために、マシンによって実行可能な命令のプログラムを明確に具体化し、マシンによって読み取り可能な、プログラム記憶デバイスもまた提供する。
【００５６】
本開示のシステムおよび方法を、汎用コンピュータシステムまたは特殊用途コンピュータシステム上で実装し、動作させることができる。コンピュータシステムは、既知の任意のタイプとすることができ、または既知のシステムであり、一般に、プロセッサ、メモリデバイス、記憶デバイス、入力／出力デバイス、内部バス、および／または、通信ハードウェアおよびソフトウェアと連携して他のコンピュータシステムと通信する通信インターフェースなどを含むことができる。
【００５７】
用語「コンピュータシステム」および「コンピュータネットワーク」を、本出願において使用する場合、固定された、および／または持ち運び可能なコンピュータハードウェア、ソフトウェア、周辺装置、および記憶デバイスのさまざまな組合せを含むことができる。コンピュータシステムは、協働して機能するようにネットワーク化された、または他の方法でリンクされた複数の個々のコンポーネントを含むことができ、または１つもしくは複数のスタンドアローンコンポーネントを含むことができる。本出願のコンピュータシステムのハードウェアコンポーネントおよびソフトウェアコンポーネントは、デスクトップ、ラップトップ、およびサーバなどの、固定された、および持ち運び可能なデバイスを含むことができ、それらの中に含まれてもよい。モジュールは、ソフトウェア、ハードウェア、ファームウェア、電子回路、またはその他として具体化され得るいくつかの「機能性」を実装するデバイス、ソフトウェア、プログラム、またはシステムのコンポーネントとすることができる。
【００５８】
上で説明した実施形態は、説明のための例であり、本発明がこれらの特定の実施形態に限定されると解釈するべきではない。したがって、添付の特許請求の範囲において定義される通りの本発明の趣旨または範囲から逸脱せずに、さまざまな変更形態および修正形態を、当業者がもたらすことができる。
【特許請求の範囲】
【請求項１】
車両用ネットワークにおける分散交通ナビゲーションのための方法であって、前記車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、前記道路区分上で運転される複数の車両とを含み、前記方法は、
前記ネットワークに入る各車両において、
前記車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、
目的地アドレスを生成するステップと、
前記目的地アドレスをルート要求としてブロードキャストするステップと、
前記ネットワークにおける各車両において、
少なくとも１つの通信可能な車両との通信を通して、前記記憶した情報を更新するステップと、
各ジャンクションにおいて、
ヘッダ車両を選択するステップと、
前記ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、
前記行列が存在しないとき、前記ヘッダ車両が、前記ヘッダ車両の前記記憶した情報に基づいて前記行列を初期化するステップと、
前記ヘッダ車両が、前記行列に基づいて前記道路区分上の移動時間を推定するステップと、
前記ヘッダ車両が、前記移動時間および前記ルート要求に基づいてバックログ・インジケータを計算するステップと、
前記ヘッダ車両が、前記バックログ・インジケータに基づいて前記行列を更新するステップと、
前記ヘッダ車両が、前記行列に基づいてルートを生成するステップと、
前記ヘッダ車両が、前記行列をブロードキャストするステップと
を含むことを特徴とする方法。
【請求項２】
前記ルートを少なくとも１つの隣接する車両に割り当てるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
各ジャンクションにおいて、前記ジャンクションの位置に関連付けられたデータを入手するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
選択する前記ステップは、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行されることを特徴とする請求項１に記載の方法。
【請求項５】
前記目的地アドレスをルート要求としてブロードキャストする前記ステップは、周期的に実行されることを特徴とする請求項１に記載の方法。
【請求項６】
前記ヘッダ車両において、前記行列をブロードキャストする前記ステップは、前記ヘッダ車両が異なるジャンクションに到着するまで周期的な間隔で実行されることを特徴とする請求項１に記載の方法。
【請求項７】
前記ネットワークを出る各車両において、退出メッセージをブロードキャストするステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
車両用ネットワークにおける分散交通ナビゲーションのための、コンピュータ上で動作するコンピュータ可読プログラムを有するコンピュータ可読媒体であって、前記車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、前記道路区分上で運転される複数の車両とを含み、前記プログラムは、
前記ネットワークに入る各車両において、
前記車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、
目的地アドレスを生成するステップと、
前記目的地アドレスをルート要求としてブロードキャストするステップと、
前記ネットワークにおける各車両において、
少なくとも１つの通信可能な車両との通信を通して、前記記憶した情報を更新するステップと、
各ジャンクションにおいて、
ヘッダ車両を選択するステップと、
前記ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、
前記行列が存在しないとき、前記ヘッダ車両が、前記ヘッダ車両の前記記憶した情報に基づいて前記行列を初期化するステップと、
前記ヘッダ車両が、前記行列に基づいて前記道路区分上の移動時間を推定するステップと、
前記ヘッダ車両が、前記移動時間および前記ルート要求に基づいてバックログ・インジケータを計算するステップと、
前記ヘッダ車両が、前記バックログ・インジケータに基づいて前記行列を更新するステップと、
前記ヘッダ車両が、前記行列に基づいてルートを生成するステップと、
前記ヘッダ車両が、前記行列をブロードキャストするステップと
を、前記コンピュータに実行させる命令を含むことを特徴とするコンピュータ可読媒体。
【請求項９】
前記ルートを少なくとも１つの隣接する車両に割り当てるステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【請求項１０】
各ジャンクションにおいて、前記ジャンクションの位置に関連付けられたデータを入手するステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【請求項１１】
選択する前記ステップは、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行されることを特徴とする請求項８に記載のプログラム。
【請求項１２】
前記目的地アドレスをルート要求としてブロードキャストする前記ステップは、周期的に実行されることを特徴とする請求項８に記載のプログラム。
【請求項１３】
前記ヘッダ車両において、前記行列をブロードキャストする前記ステップは、前記ヘッダ車両が異なるジャンクションに到着するまで周期的な間隔で実行されることを特徴とする請求項８に記載のプログラム。
【請求項１４】
前記ネットワークを出る各車両において、退出メッセージをブロードキャストするステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【請求項１】
車両用ネットワークにおける分散交通ナビゲーションのための方法であって、前記車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、前記道路区分上で運転される複数の車両とを含み、前記方法は、
前記ネットワークに入る各車両において、
前記車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、
目的地アドレスを生成するステップと、
前記目的地アドレスをルート要求としてブロードキャストするステップと、
前記ネットワークにおける各車両において、
少なくとも１つの通信可能な車両との通信を通して、前記記憶した情報を更新するステップと、
各ジャンクションにおいて、
ヘッダ車両を選択するステップと、
前記ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、
前記行列が存在しないとき、前記ヘッダ車両が、前記ヘッダ車両の前記記憶した情報に基づいて前記行列を初期化するステップと、
前記ヘッダ車両が、前記行列に基づいて前記道路区分上の移動時間を推定するステップと、
前記ヘッダ車両が、前記移動時間および前記ルート要求に基づいてバックログ・インジケータを計算するステップと、
前記ヘッダ車両が、前記バックログ・インジケータに基づいて前記行列を更新するステップと、
前記ヘッダ車両が、前記行列に基づいてルートを生成するステップと、
前記ヘッダ車両が、前記行列をブロードキャストするステップと
を含むことを特徴とする方法。
【請求項２】
前記ルートを少なくとも１つの隣接する車両に割り当てるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
各ジャンクションにおいて、前記ジャンクションの位置に関連付けられたデータを入手するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
選択する前記ステップは、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行されることを特徴とする請求項１に記載の方法。
【請求項５】
前記目的地アドレスをルート要求としてブロードキャストする前記ステップは、周期的に実行されることを特徴とする請求項１に記載の方法。
【請求項６】
前記ヘッダ車両において、前記行列をブロードキャストする前記ステップは、前記ヘッダ車両が異なるジャンクションに到着するまで周期的な間隔で実行されることを特徴とする請求項１に記載の方法。
【請求項７】
前記ネットワークを出る各車両において、退出メッセージをブロードキャストするステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項８】
車両用ネットワークにおける分散交通ナビゲーションのための、コンピュータ上で動作するコンピュータ可読プログラムを有するコンピュータ可読媒体であって、前記車両用ネットワークは、複数の道路ジャンクションを通して接続された複数の道路区分と、前記道路区分上で運転される複数の車両とを含み、前記プログラムは、
前記ネットワークに入る各車両において、
前記車両用ネットワークに関連付けられた情報を取得し、記憶するステップと、
目的地アドレスを生成するステップと、
前記目的地アドレスをルート要求としてブロードキャストするステップと、
前記ネットワークにおける各車両において、
少なくとも１つの通信可能な車両との通信を通して、前記記憶した情報を更新するステップと、
各ジャンクションにおいて、
ヘッダ車両を選択するステップと、
前記ヘッダ車両が、ブロードキャストを待ち受けて行列の存在を判定するステップと、
前記行列が存在しないとき、前記ヘッダ車両が、前記ヘッダ車両の前記記憶した情報に基づいて前記行列を初期化するステップと、
前記ヘッダ車両が、前記行列に基づいて前記道路区分上の移動時間を推定するステップと、
前記ヘッダ車両が、前記移動時間および前記ルート要求に基づいてバックログ・インジケータを計算するステップと、
前記ヘッダ車両が、前記バックログ・インジケータに基づいて前記行列を更新するステップと、
前記ヘッダ車両が、前記行列に基づいてルートを生成するステップと、
前記ヘッダ車両が、前記行列をブロードキャストするステップと
を、前記コンピュータに実行させる命令を含むことを特徴とするコンピュータ可読媒体。
【請求項９】
前記ルートを少なくとも１つの隣接する車両に割り当てるステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【請求項１０】
各ジャンクションにおいて、前記ジャンクションの位置に関連付けられたデータを入手するステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【請求項１１】
選択する前記ステップは、ランダム・カウントダウン・タイマおよび車両ＩＤに基づいて実行されることを特徴とする請求項８に記載のプログラム。
【請求項１２】
前記目的地アドレスをルート要求としてブロードキャストする前記ステップは、周期的に実行されることを特徴とする請求項８に記載のプログラム。
【請求項１３】
前記ヘッダ車両において、前記行列をブロードキャストする前記ステップは、前記ヘッダ車両が異なるジャンクションに到着するまで周期的な間隔で実行されることを特徴とする請求項８に記載のプログラム。
【請求項１４】
前記ネットワークを出る各車両において、退出メッセージをブロードキャストするステップをさらに含むことを特徴とする請求項８に記載のプログラム。
【図１】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２０１３−５０１９３８（Ｐ２０１３−５０１９３８Ａ）
【公表日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願番号】特願２０１２−５２４７６６（Ｐ２０１２−５２４７６６）
【出願日】平成２２年８月９日（２０１０．８．９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４４８２７
【国際公開番号】ＷＯ２０１１／０１９６２７
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＢＬＵＥＴＯＯＴＨ
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
【公表日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願日】平成２２年８月９日（２０１０．８．９）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４４８２７
【国際公開番号】ＷＯ２０１１／０１９６２７
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＢＬＵＥＴＯＯＴＨ
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【Ｆターム（参考）】
[ Back to top ]