車両ピアグループの効率的編成及び効率的なV2R通信のための方法
【課題】VANETにおける効率的な制御メッセージ配布のための方法を提供する。
【解決手段】選択されたキーノードによる限られた数の再ブロードキャストによってフラッディングの目的を達成するために、効率的なフラッディングメカニズムが提供される。抑制ベースの効率的なフラッディングメカニズムは、軽度抑制技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観測したときにそのフラッディングメッセージのブロードキャストを断念することによって、フラッディング中継の数を減少させる。また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノードを選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばメンバシップレポートなどの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。
【解決手段】選択されたキーノードによる限られた数の再ブロードキャストによってフラッディングの目的を達成するために、効率的なフラッディングメカニズムが提供される。抑制ベースの効率的なフラッディングメカニズムは、軽度抑制技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観測したときにそのフラッディングメッセージのブロードキャストを断念することによって、フラッディング中継の数を減少させる。また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノードを選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばメンバシップレポートなどの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、マルチホップ車両アドホックネットワーク(VANET)における制御メッセージの効率的配布のための方法に関するものである。
【0002】
本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network(アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス)」と題された、2006年10月23日出願の共同所有の米国同時係属特許出願第11/585,047号(「’047出願」)に関連している。
【背景技術】
【0003】
無線通信は、それが無線ホームネットワーク若しくは無線オフィスネットワークであれ、ローカルカフェ、ファストフードチェーン、若しくはホテルにおけるいわゆる「ホットスポット」ネットワークであれ、又はひいては都市規模でのWiFi技術の実施であれ、今日の生活のあらゆる局面において普及してきている。無線通信社会を追い求めるこのような要求は、移動車両などの移動デバイスにまで広がっている。このタイプの無線ネットワーク構築は、道路障害物に関する緊急警告、交差点の調整、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含む、多くの車両安全応用の局面において出現する可能性がある。
【0004】
車両間安全通信(「VSC」)は、車両間通信、及びインフラストラクチャを介した車両通信に大別することができる。車両間通信では、車両同士は、固定されたインフラストラクチャからの支援を受けることなく通信しあう。車両同士は、互いに同じ電波範囲内にあるときに、又はその他の車両を通じたマルチホップ中継が可能であるときに、通信しあう。インフラストラクチャを介した車両通信では、車両同士は、路側の無線アクセスポイントなどのインフラストラクチャの支援を受けて通信しあう。このケースでは、車両は、インフラストラクチャのみと通信することもできる。
【0005】
重要なVSC性能要件は、衝突回避などの様々なVSC応用形態を支援するために、待ち時間が短いこと(約100ミリ秒)及びスループットを維持すること(別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合)を含む。’047出願は、1つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してLPGを維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループ(LPG)に編成するための方法を記載している。LPGは、ハートビート(HB)及びメンバシップレポート(MR)などの制御メッセージの伝送によって形成される。HBメッセージは、フラッディングメカニズムを使用して実装されている。移動車両は、ユニキャスト及びマルチキャストのルーティングに適応される。
【0006】
しかしながら、フラッディングは、ユニキャストプロトコル及びマルチキャストプロトコルを含むLPGベースのルーティングプロトコルの主要な制御オーバーヘッドである。各HBサイクルにおいて、HBは、少なくともLPG内のメンバの数と同じ回数だけ再ブロードキャストされる。交通渋滞などのように、近くにあるノードの数が大きい状況では、HBの重複によって、このオーバーヘッドが大幅に増大される。フラッディングは、全てのノードに対してフラッディングメッセージの再ブロードキャストを要求する。これらの状況では、フラッディングによって、更には大きいLPG内では制御メッセージの大サ
イズになるために、ネットワーク帯域幅が消費し尽くされる恐れがある。制御メッセージの配布は、LPGベースのプロトコルの中核的要素であるので、効率的な制御メッセージ配布が必要とされている。
【発明の概要】
【0007】
本発明は、VANETにおける効率的な制御メッセージ配布のためのシステム及び方法を提供する。選択されたキーノードによる限られた数の再ブロードキャストによってフラッディング(接続された全てのノードにメッセージを配信する)の目的を達成するために、効率的なフラッディングメカニズムが提供される。
【0008】
抑制ベースの効率的なフラッディングメカニズムは、軽度抑制(LS:Light Suppression)技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。
【0009】
また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノード(RN)を選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばダウンストリームノードのメンバシップレポート(MR)などの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、LPGのためのグループヘッダ(GH)であってもよい。
【0010】
一実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを効率的に散布するための方法である。方法は、少なくとも1つのルーティングパラメータを含む第1の制御メッセージをグループヘッダノードから受信することと、第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、もし第1の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、第1の制御メッセージを破棄することと、もし第1の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、もし上記時間の間に第1の制御メッセージをブロードキャストしたダウンストリームノードがないならば、上記時間の終了時に第1の制御メッセージをブロードキャストすることと、を含む。方法は、更に、シーケンス番号を使用して、第1の制御メッセージが順序通りであるかどうかを判定することと、もし順序通りでないならば、第1の制御メッセージを破棄することと、を含む。
【0011】
第1の制御メッセージは、複数のルーティングパラメータを内包している。複数のルーティングパラメータは、シーケンス番号と、グループリストと、グループヘッダノードまでのホップカウントと、グループヘッダノードへの次ホップとを含む。本方法は、更に、第1の制御メッセージの、グループヘッダノードまでのホップカウントを、現ノードの、グループヘッダノードまでのホップカウントと比較することを含み、もし2つのホップカウントが等しいならば、第1の制御メッセージはピアノードによってブロードキャストされている。もし第1の制御メッセージのホップカウントが、現ノードのホップカウントよりも小さいならば、第1の制御メッセージは、破棄される。もし第1の制御メッセージのホップカウントが、現ノードのホップカウントよりも大きいならば、時間は取り消され、制御メッセージの状態は「送信された」に設定される。
【0012】
本方法は、更に、第1の制御メッセージ内の複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、少なくとも1つの追加のルーティングパラメータを含む第2の制御メッセージを、ローカルピアグループ内のグルー
プノードから受信することと、少なくとも1つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。この転送テーブルに基づいて、パケットがルーティングされてよい。
【0013】
本方法は、更に、第2の制御メッセージに対するソースを判定することと、第2の制御メッセージの直接の送信者を判定することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。第1の制御メッセージの受信後に、ノードは、第1の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第1の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。ノードは、上記の増分及び挿入を実施した後に、第1の制御メッセージを転送し、第2の制御メッセージの受信後に、第2の制御メッセージをグループヘッダノードに転送する。
【0014】
本方法は、更に、第1の制御メッセージが路側機(RSU:road side unit)から受信されたかどうかを判定することと、もしそうであるならば、RSUのルーティングテーブルを更新すること及び第1の制御メッセージをブロードキャストすることと、を含む。
【0015】
別の実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、グループヘッダノードから第1の制御メッセージを受信することと、第1の制御メッセージをブロードキャストすることと、第1の制御メッセージに応じてローカルピアグループ内のグループノードから第2の制御メッセージを受信することと、第2の制御メッセージのシーケンス番号を格納することと、グループヘッダノードから第3の制御メッセージを受信することと、第3の制御メッセージのシーケンス番号を第2の制御メッセージのシーケンス番号と比較することと、第3の制御メッセージのシーケンス番号が、第2の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、第3の制御メッセージをブロードキャストすることと、を含む方法である。
【0016】
本方法は、更に、第3の制御メッセージのシーケンス番号が、第2の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも小さい場合に、第3の制御メッセージを破棄することを含む。プリセット定数は、第3の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する。
【0017】
本方法は、更に、第1の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、第2の制御メッセージに含まれる少なくとも1つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記の更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。
【0018】
本方法は、更に、第2の制御メッセージに対するソースを判定することと、第2の制御メッセージの直接の送信者を判定することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。転送テーブルは、情報のパケットをルーティングするために使用される。第3の制御メッセージの受信後に、ノードは、第3の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第3の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。
ノードは、上記の増分及び挿入を実施した後に、第3の制御メッセージを転送する。第2の制御メッセージの受信後に、ノードは、第2の制御メッセージをグループヘッダに転送する。
【0019】
特許請求の範囲の方法は、更に、第3の制御メッセージが路側機(RSU)から受信される場合に、RSUのルーティングエントリを更新すること及び第3の制御メッセージをブロードキャストすることを含む。
【図面の簡単な説明】
【0020】
【図1】発明にしたがった、アドホックネットワークの一例を示している。
【図2】本発明の典型的実施形態にしたがった、路側機(RSU)の基本的要素のブロック図を示している。
【図3】本発明の典型的実施形態にしたがった、ハートビート制御メッセージのフォーマットの一例を示している。
【図4】本発明の典型的実施形態にしたがった、メンバレポート制御メッセージのフォーマットの一例を示している。
【図5A】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5B】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5C】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5D】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図6A】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図6B】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図6C】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図7A】本発明の典型的実施形態にしたがった、RSUからのハードビートメッセージを処理するための方法を示している。
【図7B】本発明の典型的実施形態にしたがった、RSUからのハードビートメッセージを処理するための方法を示している。
【発明を実施するための形態】
【0021】
本発明にしたがうと、アドホックネットワークは、2つのタイプのノードに、すなわち路側機(Road Side Unit:以下「RSU」)と移動車両とに分けられる。RSUが固定ノードである一方で、車両はグループで移動することができる。
【0022】
図1は、本発明にしたがった、アドホックネットワークの一例を示している。RSU100は、道路の側辺に沿って位置している。ネットワークにおいて使用されるRSU100の数は、RSU100の電波アンテナの範囲、所望の通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの数々の要因に依存する。図1は、2つのRSU100を示している。丸で囲われたエリアは、各RSU100の電波範囲を表わしている。各RSU100は、単独又はグループのいずれかで走行している移動車両110と通信するために使用することができる。
【0023】
移動車両110は、管理可能なグループに編成することができる。これらのグループは、ノード間のデータの伝送を調整するために使用される。グループは、隣接するノードの
相対的位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ(「LPG」)は、1つのLPG115内で及び複数のLPG間で電波信号をルーティングするための基礎である。
【0024】
図1は、3つのLPG115を示している。各LPG115は、少なくとも1つの移動車両110で構成される。図1は、LPG1 1151が3つの移動車両を含むこと、L
PG2 1152が2つの移動車両を含むこと、及びLPG3 1153が3つの移動車両を含むことを示している。RSU100は、LPG115内に存在して特別なLPGノードとして振る舞うことができる、又はLPG115の外側において別個のノードとして存在することができる。RSU100がLPG115内のノードではなく、LPG115と連携して使用されるときは、RSU100は、LPG間通信用の境界ノードとして振る舞うことができる。通常、1つのRSU100の電波有効範囲は、1つのLPGのサイズよりも大きい、すなわち、1つのRSU100の電波範囲内には、2つ以上のLPG115がある。このような場合が図1に示されている。したがって、1つのLPG115からのメッセージは、RSU100を使用して別のLPGにブロードキャストすることができる。この場合、RSU100は、そのメモリに格納されたLPGに関する情報を含む。
【0025】
移動車両110は、車両−車両(V−V)チャネルを通じて互いに通信する。移動車両は、車両−路側(V−R)チャネルを通じて路側機と通信する。また、RSU100は、R−Rチャネル又はR−B(バックボーン)チャネルを通じて互いに通信する。R−R通信は、専用チャネルつまり有線バックボーンを使用するので、この通信は、V−V通信又はV−R通信に干渉しない。V−VチャネルとV−Rチャネルとの間のチャネル共有についての代案が幾つかある。好ましい実施形態では、V−R通信用の専用チャネルがある。残りのチャネルは、V−V通信及び/又はV−R通信用に共有される。V−Rチャネルは、その他のチャネルと同じRF周波数帯域にあってよい。或いは、V−Rチャネルは、異なるRF周波数帯域にあって、異なる通信範囲及び異なるデータ速度を可能にしてよい。
【0026】
別の実施形態では、全てのチャネルが、V−V及びV−Rの両方のために動的に共有される。この手法は、性能の最適化を可能にする。しかしながら、干渉しないチャネルの探索及び選択において複雑性がもたらされる。
【0027】
別の実施形態にしたがうと、V−R用にのみ専用チャネルが割り当てられ、その他のチャネルは、V−V用だけに共有される。或いは、V−R用に専用チャネルが、そしてV−V用に第2の専用チャネルが使用される。残りのその他のチャネルは、V−V通信及びV−R通信用に共有される。発明の説明を続ける目的で、好ましい実施形態のチャネル割り当てが使用される。RSU100は、ルータ、アプリケーションサーバ、又はそれらの組み合わせなどの、多くの機能を有することができる。
【0028】
LPG115には、固定LPG、動的LPG、及びハイブリッドLPGなどの、幾つかのタイプのLPG115がある。固定LPGは、特定の位置又はエリアによって画定される。すなわち、もしノードが、例えばエリアAを画定するエリアにあるならば、そのノードは、LPG Aに所属する。もしノードが、例えばエリアBなどの異なるエリアにあるならば、そのノードは、LPG Bに所属し、以下同様である。固定LPGの具体的なサイズは、例えば電波アンテナの範囲、通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの様々な要因に依存する、設計上の一選択肢である。固定LPGの位置及びサイズは固定である。しかしながら、場所が異なると交通パターン及び人口(移動車両110)密度が異なるゆえに、各固定LPGは、それぞれ異なるサイズであってよい。もしRSU100が所定のLPG115内にあるならば、そのRSU100の電波範囲によって、固定LPGのサイズが画定される。
【0029】
RSU100を使用することによって、移動車両110は、RSU100からのハードビート制御メッセージ又はAP330からのビーコンのいずれかをヒアリングすることによって固定LPGの位置を検出することができる。移動車両110は、自身の位置変化とともに、固定LPGを変更していく。或いは、移動デバイスは、LPG115及びそれらの位置のデータベースを含む。別の実施形態において、もしとあるエリア内に複数のRSU100がある場合は、少なくとも1つのRSU100が、近隣にあるその他のRSU100の相対的なポジション又は位置に関する情報を提供することによって、移動車両100がLPG115を迅速に突き止められるようにして、複数のLPG115間のハンドオフを容易にすることができる。
【0030】
固定LPGは、たとえ一部のLPG115が空である又は多くの移動車両110を有さない場合でも、バックボーンアクセス又はLPG間通信を提供するように無線インフラストラクチャとの統合をサポートするという、重要な利点を有している。各固定LPGは、通信を容易にするように、一意の識別子を割り当てられている。どの固定LPGエリアも明確に画定されているので、LPG115の形成及び命名は、動的LPGよりも容易である。また、固定LPGを使用する場合、LPG115の併合及び分割に関する規則は問題ではない。
【0031】
第2のタイプのLPG115は、動的LPGである。固定LPGとは反対に、動的LPGは、隣接するノードの電波有効範囲に基づいて形成され、それにより、ノードは、他のノードの厳密な位置を考慮することなく通信を調整することができる。
【0032】
動的LPGは、電波有効範囲に基づいて形成されるので、LPG115内の移動車両110は、シングルホップ伝送又はマルチホップ伝送を通じて互いに及びRSU100と常に通信することができる。LPG115内の1つのノードは、低遅延で且つ効率的な通信を実施することができるように、各LPG115内のノードの数を又はこのノードから動的LPGの端までの電波ホップの数を適度に少なく維持するために、動的LPGのサイズを制御することができる。このノードは、後ほど詳述されるように、グループヘッダ(GH)と称される。また、固定LPGとは対照的に、動的LPGは、各LPG115内で常に通信が可能であることを確実にする。動的LPGでは、固定LPGと異なり、RSU100の電波範囲の外にLPG115を形成することができる。
【0033】
一実施形態では、アドホックピアツーピアネットワークを、1つ若しくは2つ以上の固定LPG又は1つ若しくは2つ以上の動的LPGで作成することができる。別の実施形態では、アドホックピアツーピアネットワークを、ハイブリッドLPGネットワークとして、固定LPG及び動的LPGの両方で作成することができる。ハイブリッドLPGネットワークは、固定LPG及び動的LPGの両者の利点を融合しつつ、それぞれを個別に利用した場合に生じる問題を排除する。
【0034】
ハイブリッド手法は、道路形状をうまく活用する。特に、インフラストラクチャが利用可能でないときに、動的LPGを使用してネットワークを形成する。一部のエリアにおいてインフラストラクチャが利用可能になると、固定LPGを使用して、動的LPG及びインフラストラクチャとのネットワークを形成することができる。例えば、道路インフラストラクチャなどのインフラストラクチャは、道路−車両通信又は道路支援通信を可能にする。
【0035】
一実施形態では、RSU100は、LPG115内のノードであってよく、移動車両110と同様のネットワーク機能を実行することができる。RSU100は、グループヘッダ(GH)又はグループノード(GN)のいずれかとしてLPG115に参加することができる。GHは、いかなるノード順番付け又はいかなるインフラストラクチャもなしにL
PG115を維持及び制御するように指定された、LPG115内の移動デバイス又はノードである。通常、LPG115内にGHは1つのみである。LPG115内のその他の全てのノードは、一般的なノードすなわちグループノード(「GN」)である。GNは、GHを通じてLPG115に参加する。
【0036】
各RSU100は、上述のようにルータ及びアプリケーションサーバに加えて、GH又はGNとして動作することができる。このように、各RSU100は、ノードをそれぞれGH又はGNとして機能させる又は動作させることを可能にする要素又は手段及びネットワーキングプロトコルを含む。したがって、たとえRSU100がGH又はGNのいずれかとして動作する場合でも、GH及びGNの両方のための全ての構造的な要素又は手段が存在し、ただし、動作のモードに基づいて特定の要素のみが機能している。RSU100は、したがって、GH又はGNの機能性を提供するためのハードウェア及びソフトウェアの両方を含んでいる。
【0037】
図2は、RSU100の基本的要素のブロック図を示している。RSUは、メモリセクション2100と、クロック2105と、タイマ2110と、送受信セクション2120と、制御手段2125と、電源2130とを含む。メモリセクション2100は、DRAM、SRAM、又はFlashを含む、任意のタイプのメモリであってよい。好ましい実施形態では、短期メモリは、キャッシュである。メモリセクション2100は、グループID(GID)、グループヘッダID、グループリスト、既定の最大LPGサイズ、LPG内のノードの数、及びその他のタイプの制御パラメータなどの、LPGに関する情報を格納する。
【0038】
クロック2105は、RSU100のためのタイミングを維持するために使用される。特に、クロック2105は、内部クロックとして機能し、タイマ2110を設定するための基準として使用される。タイマ2110は、様々なメッセージをいつブロードキャストするべきかを判定するために使用される、すなわち、GHの場合はハードビート間隔(T)を、又はGHの場合は応答メッセージを判定する。制御手段2125又はマイクロプロセッサは、メッセージの生成、ルーティング、及びタイマを含む、RSU100の全てのプロセスを制御する。送受信セクション2120は、制御手段2125と協働して、メモリセクション2100に格納されているデータからメッセージを作成又は生成する役割を担う。
【0039】
RSU100は、その電波範囲内にある全ての移動車両110及びその他のRSUに対し、ビーコン又はハードビート制御メッセージを定期的に伝送する。この期間は、固定間隔である。ハードビート間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。
【0040】
LPG115がRSU100の近くを移動するときは、ヘッダ解決プロトコルに基づいてGHが選出される。LPG115のGHである移動車両は、V−Vチャネル及びV−Rチャネルの両方にハードビート制御メッセージを送出する。やはりGHとして振る舞うRSU100は、V−Rチャネルのみにハートビートを送出する。2つ以上のGHがハートビート制御メッセージを送信すると、ヘッダ解決が発生する。これは、同じLPG115内に複数のGHがあるのを回避するためである。なぜならば、同じLPG115内に複数のGHがあると、結果として、そのLPG115内において冗長な(混乱を招く可能性すらある)制御信号が伝送又はブロードキャストされ、帯域幅及び容量が無駄遣いされるからである。ヘッダ解決は、少なくとも2つのGHから1つのGHを選択する働きをする。
【0041】
ユニキャストルーティングプロトコルは、各ノード内におけるルーティングテーブルの作成に基づく。ルーティングテーブルは、少なくとも、メッセージについての宛先及び次
ホップを含む。LPG115内の全ての移動車両110は、ルーティング機能を実施し、その他の車両がシングルホップ又はマルチホップのいずれかで通信するのを助ける。LPG内ルーティングテーブルは、LPG形成メッセージを使用してブロードキャストモードにおいて制御メッセージを交換することによって構成される。ユニキャストルーティングでは、追加の制御メッセージは不要である。LPG形成に使用されるのと同じ制御メッセージが、ルーティングプロトコルのためのルーティングテーブルの作成、維持、及び更新のために使用される。ルーティングテーブルは、LPG内ルーティングに使用される。不要なノードに外部制御メッセージが伝搬されることがないように、あらゆる制御メッセージにLPG識別子が埋め込まれる。全ての外部制御メッセージは、終了される又は中継されない。
【0042】
制御メッセージメッセージは、GHからのハートビート(HB)及びGNからのメンバシップレポート(MR)である。ハードビート制御メッセージは、LPGの領域を画定する。ハートビートメッセージと、それに続くメンバシップレポートとが、1つの制御メッセージサイクルを構成する。
【0043】
’047出願で説明されている別の実施形態では、LPGネットワークは、マルチキャストメッセージ機能をサポートすることができる。ユニキャストでは、送信ノード(例えば事故の目撃者)は、1つの特定の受信者にメッセージを送信する又は向かわせるので、同じ情報を複数の受信者に送信するためには複数のメッセージが必要である。これは、大量のネットワーク帯域幅の消費及びメッセージの遅延を引き起こす結果となる。マルチキャスト伝送では、送信者は、メッセージの重複コピーを生成せず、1つのメッセージを全ての受け手に対して送信する。マルチキャストによって、ネットワーク帯域幅は大幅に節約される。
【0044】
<HBメッセージ>
図3は、ハートビート制御メッセージ300のフォーマットの一例を示している。ハートビート制御メッセージ300は、LPG識別子すなわちGID305及びグループヘッダ310の両方を含む一意の識別子を含む。
【0045】
GID305及びグループヘッダID310は、各LPG115を識別する。GID305には、幾つかの可能なフォーマットがある。一実施形態では、GID305は、LPG115のためにランダムに選択された識別番号であってよい。或いは、GID305は、LPGの形成の順番に基づいて割り当てられた識別番号であってよい。例えば、第1のLPGは、LPG1というGID305を有することができ、第2のLPGのGID305は、LPG2であり、以下同様である。しかしながら、GHの変化とともに、GID305も変化し、その結果、ノードは、そのLPGが変化したのか又は単にLPG115のIDが変化したのかを区別することができなくなる。他方で、GHが去るときに、GID305を元のIDに固定してもよい。しかしながら、これは、1つのLPGが分裂するときに、GID305の重複を生じる可能性がある。その結果、2つ又は3つのグループが、同じGID305を有することになる。一実施形態では、GID305は、LPG115を一意に識別するために、LPG ID番号及びGH ID番号の両方に基づいて符号化される。
【0046】
GHは、グループヘッダID310を与えられる。最初、GID305は、グループヘッダID310に結び付いている。したがって、グループヘッダID310は、最初は、GID305の一部分として使用されるが、GHの変化とともに、新しいグループヘッダID310を含むように変化する。各GHは、グループヘッダID310を割り当てられる。グループヘッダID310は、(パブリック又はプライベート)IPアドレスに基づいて割り当てられる。図3に示されるように、グループヘッダID310は、IPv6
IPアドレスである。別の実施形態では、グループヘッダID310は、IPv4アドレスであってよい。
【0047】
ハードビート制御メッセージは、また、シーケンス番号(sequence number:Seq.
No.)315も含む。Seq.No.315は、ハートビート制御メッセージの順番を追跡して、受信されたハートビート制御メッセージ300が新しいすなわち新着であるかどうかを判定するために使用される。GNは、受信されたハートビート制御メッセージのSeq.No.315を記憶している。新たなすなわち新着のハートビート制御メッセージは、次のSeq.No.315を伴う最初のハートビート制御メッセージによって示される。Seq.No.315は、また、どのハートビート制御メッセージが(次ホップノードに)中継されるべきかを判定するためにも使用される、すなわち、先着のみ中継(FCRO:first come relay only)戦略を使用することができる。新たな(すなわち新着
の)ハートビート制御メッセージのみが中継されるべきである。ノードは、先のシーケンス番号を記憶しており、それを着信ハートビート制御メッセージのシーケンス番号と比較して、そのハートビート制御メッセージが新しいすなわち新着であるかどうかを判定する。もし適切なGID305を伴うハートビート制御メッセージのSeq.No.315が、現時点で格納されているシーケンス番号よりも大きいならば、それは、新たなすなわち新着のハートビート制御メッセージ300であり、したがって、FCROが使用される場合は中継される。GNに先に格納されていたシーケンス番号は、破棄され、新たなシーケンス番号に置き換えられる。
【0048】
ハートビート制御メッセージ300は、更に、ハートビート期間(HB期間)320に関する情報も含む。この期間は、固定間隔(T)である。間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。HB期間320は、次のハートビート制御メッセージがいつブロードキャストされるかを、全てのGNに対して示す。GNは、HB期間320内にハートビート制御メッセージを受信しない場合は、ハートビート制御メッセージが連続的に送信されるように、新たなハートビート制御メッセージを伝送する。もし元のGHが依然としてLPG115内にあるならば、ヘッダ解決が発生する。制御オーバーヘッドを低減させるために、GHは、HB期間320を調整することができる。調整は、LPGのサイズ、LPG内のノードの位置、負荷、速度、及び数に基づくことができる。
【0049】
ハートビート制御メッセージ300は、例えば、完全なグループリストを伴う、漸増性のグループリストを伴う、又はグループリストを伴わないなどの、ハートビート制御メッセージのタイプも含む。一実施形態では、ハートビート制御メッセージは、全てのメッセージ内に、完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビート制御メッセージには、大量の帯域幅が必要である。ハートビート間隔(T)は、制御オーバーヘッドを低減させるように調整することができる。別の実施形態では、(n−1)個おきの各ハートビート制御メッセージが完全グループリストを含む。例えば、2つおきの各ハートビート制御メッセージが完全グループリストを含む。これは、平均のハートビート制御メッセージに対する帯域幅を低減させる。しかしながら、LPG115内のノードの大半は、速いペースで移動しているので、受信されるグループリストは、古くなっている可能性がある。言い換えると、ノードによって新たなグループリストが受信された時点で、グループの幾つかのメンバは、別のLPG115内にある可能性がある。別の実施形態では、進行性のグループリスト又は漸増性のグループリストを配布することができる。グループリストは、そのリスト内のメンバシップに変更があるときにのみ配布される。進行性のグループリスト又は漸増性のグループリストもまた、メンバシップリストが古くなる可能性がある。
【0050】
或いは、ハートビート制御パッケージのタイプは、ハイブリッドグループリスト更新であってよい。メンバシップに変更があるときは、ハートビート制御メッセージに進行性のグループリストを含めることができ、更に、(n−1)個おきの各ハートビート制御メッセージには、完全なグループリストを含めることができる。ToHB(type of heartbeat)325は、ハートビート制御メッセージのタイプを示す。ハートビート制御メッセー
ジのタイプは、LPG115のトポロジ変化速度及びハートビート制御メッセージのブロードキャストの頻度によって影響される。LPG115のトポロジ変化速度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性が高まる。ハートビート制御メッセージのブロードキャストの頻度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性は減少する。
【0051】
ハートビート制御メッセージは、GHからのホップカウント(HC)330を含む。最初、HC330は、例えば1などの既定の値に設定される。ハートビート制御メッセージがノードによって中継されるたびに、中継ノードは、HC330の値を1だけ増加させる、すなわち、HC=HC+1とする。HC値は、LPGサイズを制限するため、ハートビート制御メッセージ内の情報の古さを示すため、及び制御メッセージのルーティングを制御してオーバーヘッドを低減させるために使用することができる。LPGごとに、例えば10などの、ルーティングの最大ホップカウントがある。HCが最大ホップカウントまで増分されると、例えばハートビート制御メッセージなどの制御メッセージは、中継されなくなる。
【0052】
ホップカウントは、中継戦略にも使用することができる。一実施形態では、ハートビート制御メッセージは、最低のホップカウントを有する場合に中継するようにしてもよい。この方法は、GHからの正しいホップカウントを保証するが、ただし、待ち遅延がある。ノードは、ハートビート制御メッセージについて最低のホップカウントを判定する必要があるので、同ハートビート制御メッセージを中継する前に、全てのアップストリームノードからハートビート制御メッセージが受信されるまで待機する必要がある。したがって、最低のホップカウント及び上記の先着のみ中継戦略の両方を使用した、複合的な中継戦略を実装することができる。ハートビート制御メッセージは、より低いホップカウントのハートビート制御メッセージがノードによって受信されるまでは、先着のみ中継戦略を使用して中継される。ノードAは、ハートビート制御メッセージを転送するときに、ハートビート制御メッセージを誰が中継したのかを次ホップノードが知ることができるように、メッセージ内にID情報を含ませる。メッセージを転送するノード(ノードA)は、すると、ノードAから初めてハートビート制御メッセージを受信した次ホップノードにとって、(GHに向けてMRを送信するための)MR中継ノードにもなる。
【0053】
最大ホップカウント、HC330、及びSeq.No.315を利用することによって、LPG115内における制御メッセージのフラッディングの無限の重複が阻止される。本発明の一実施形態にしたがうと、ノードは、フラッディングソースからのホップカウント(HC)が自身のものよりも小さいようなフラッディング中継を横聞き(overhear)すると、そのフラッディングメッセージの中継を中止する。この方法は、図5において更に説明される。ノードは、新たなハートビート制御メッセージ300を受信すると、そのハートビートを中継する前に、設定時間(HB送信待機タイマによって定められる)の間、待機する。もしこの時間の間に、ダウンストリームノード又はピアノードがそのハートビートを再ブロードキャストする場合は、その再ブロードキャストされたハードビートのHCが、現(格納されている)HC330と比較される。もし受信されたHCが現HC330よりも小さいならば、ハートビートが不必要にブロードキャストされないように、メッセージは破棄される。もし2つのHCが同じであるならば、再ブロードキャストしているノードはピアノードであり、現ノードは、自身がキーノードにならない可能性を増やすために、HB送信待機タイマを増加させる又はリセットする。もし受信されたHCが現HC
よりも大きいならば、現HB送信待機タイマは取り消され、ハートビートは送信される。より詳しくは、図5を参照せよ。
【0054】
別の実施形態では、効率的な制御メッセージ中継ツリーを構築するために、中継ノード(RN)が選択される。この方法は、メッセージを中継するか否かを判定するために、ハートビート制御メッセージ300のSeq.No.315を使用する。中継ノードは、少なくとも1つのメンバレポート(MR)をアップストリームノードに又はGHに中継するノードである。この方法は、図6において更に説明される。通常、ハートビート制御メッセージ300は、ノードからのメンバシップレポート(MR)をトリガする。MRの内容は、次項及び図4において説明される。ノードは、MRを中継するときはいつも、MRの最新のシーケンス番号(HBのSeq.No.315に対応する)を格納し、MRを複製し、次ホップを置き換え、MRをブロードキャストする。後続のHB300が受信され、そのSeq.No.315が、格納されているMRのSeq.No.と比較される。MRの配信は、(’047出願に記載されているように)中継ノードを自動的に選択するので、シーケンス番号の比較は、選択された中継ノードのみが後続のHB制御メッセージを展開することを確実にし、そうして、HBフラッディング中における不要な制御メッセージの量を低減させる。
【0055】
上記のように、ハートビート制御メッセージは、グループリスト335も含むことができる。グループリスト335は、LPG115内のメンバの数、各数のIPアドレス、GHからのホップカウント、及び分類などの、LPG115のメンバに関する情報を含むことができる。
【0056】
分類は、例えばアップリンク、ダウンリンク、及びピアなどのような、GHノードからの相対的方向に言及したコードであってもよい。ピア分類は、ノードがGHから同じ無線有効範囲内にあることを示している、すなわち、全てのピアノードは、GHからのホップカウントが同じである。アップストリームノードは、ハートビート制御メッセージによって判定される。ダウンストリームノードは、メンバシップレポート(MR)に基づいて判定される。アップストリーム伝送は、GHに向かう通信を表しており、ダウンストリーム伝送は、GHから離れる通信を表している。この分類は、相対的表現である。各GNは、自身に隣接するノードを3つの異なるクラスに分類することができる。もし別のGNのメンバシップレポートが、自身のHCよりも1だけ小さいホップカウント(HC)を有するならば、GN(自身)はアップストリームノードである。もし別のGNのHCが、自身のHCと同じであるならば、GN(自身)はピアである。もし別のGNのHCが、自身のHCよりも1だけ大きいならば、GN(自身)はダウンストリームノードである。
【0057】
図4は、メンバシップレポート(MR)400を示している。MR400は、GNによってブロードキャストされ、GHによって受信される制御メッセージである。MRは、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードに対する次ホップなどの、収集可能なルーティング情報を含んでいる。MRは、ハートビート制御メッセージ300と同じ情報の幾つかを、すなわちGID305及びグループヘッダID310を含んでいる。MR400は、また、MR SEQ.NO.405も含む。MR Seq.No.は、ハートビート制御メッセージ300のSeq.No.315と同様であり、MRの順番を維持するために使用される。MR SEQ.NO.405は、1つの特定のノードに対するMRの順番である。通常、MR SEQ.NO.405は、MRをトリガしたハートビート制御メッセージ300のSeq.No.315と同じ値を有する。
【0058】
したがって、図6において更に説明される本発明の一実施形態では、MR400のSeq.No.405は、現ノードのメモリに格納され、後続のハートビート制御メッセージ
のそれと比較される。もし到着したメッセージのSeq.No.が、現時点で格納されているSeq.No.405からプリセット数kを差し引いたものよりも大きいならば、そのノードは、中継ノードである。定数kは、冗長性を実装してLPGの崩壊を阻止するために、kサイクルの緩和を導入する。
【0059】
発信元ノードの、すなわちMRを生成したノードの、ノードID410も、MR400に含まれる。MRは、次ホップ中継ID415も含む。次ホップ中継ID415は、GHに向かうMR400に対する中継命令である。次ホップ情報は、受信されたハートビート制御メッセージ300をもとに直接決定される。ノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、いかなるメッセージ処理よりも前に、IP層及びMAC層をもとにして前中継ノードの識別を再取得する。以前の中継ノードの識別は、メモリに格納されており、MRに対する次ホップ中継ID415として使用される。ハートビート制御メッセージを転送するときに、ノードは、そのIDをメッセージ内に含ませる。受信側の次ホップノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、このIDを、GHに到達するための次ホップ中継IDとして格納する。新たなすなわち新着のハートビート制御メッセージは、最低のHCを伴う、より新しいシーケンス番号を有するメッセージである。
【0060】
MR400は、また、「MRのタイプの指標」420も含む。MRには、2つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバMRは、発信元ノードからのMRのみを含む。統合複数メンバレポートは、2つ以上のノードのMRを含む。統合レポートは、オーバーヘッド、及び制御メッセージに必要な帯域幅を低減させるために使用することができる。複数のMRを含む1つのMRが送信される。
【0061】
また、MRは、GHからのホップカウント(HCGH)425を含むことができる。(HCGH)425は、GHからMRの発信元ノードまでのHC値である。別の実施形態では、MRは、累積メンバシップリスト430及びその他の追加の情報435を含むことができる。累積メンバシップリスト430は、LPGのメンバのIPアドレス、メンバの数、及び対応するホップカウントを含む。
【0062】
MR400は、逆経路方法又は逆フラッディング方法を使用してGHに配信又は中継することができる。逆経路方法は、ハートビート制御メッセージ300を中継するために使用されたものと同じ経路を使用して、MRをGHに向けて中継する。MRが中継されるときに、中継ノードは、次ホップ中継415を、GHに向かう次ホップに置き換える。対応するIDを有するノードのみが、MRメッセージを中継する。この方法は、伝送における対称性を想定している。もし非対称リンクが存在する場合は、逆フラッディング方法が使用される、すなわち、発信元ノードとGHとの間の全てのノードがMRを中継する。これは、後続のハートビート制御メッセージ配信のための中継ノード(RN)を選択するために使用可能な選択手続きである。
【0063】
各ノードは、LPGベースのルーティングのための転送テーブルとして使用することができるルーティングテーブルを作成するために、ハートビート制御メッセージ300及びMR400の両方を使用する。好ましい実施形態では、各ハートビート制御メッセージは、完全なグループリストを含み、LPG115内の全てのGNが、それに対してMRで応答する。ハートビート制御メッセージは、先着のみ中継方法を使用して中継され、MRは、逆経路方法を使用して、単一MRとしてGHに向けて中継される。
【0064】
<軽度抑制ベースの効率的なフラッディング>
抑制ベースの効率的なフラッディングメカニズムは、軽度抑制(LS:Light Suppress
ion)技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。図5Aは、この方法を示している。最初、ステップ500において、各ノードはアイドル状態にある。ステップ501において、メッセージが到着すると、ノードは、ステップ502において、メッセージがハートビート制御メッセージ300であるか又はMR400であるかを判定する。制御メッセージのタイプに応じて、ノードは、特別なメッセージ処理を実施する。もし制御メッセージがハートビート制御メッセージ300であるならば、ノードは、ステップ503から始まるメッセージ処理を行う。ノードは、ステップ503において、メッセージがネイティブであるかどうかを判定する。メッセージは、同じLPG115に対するメッセージである場合に、すなわち、同じGID305を有する場合に、ネイティブである。ノードは、GID305を、メモリに格納されているグループ識別と比較する。もしGID305が、メモリに格納されている識別と一致しないならば、ノードは、ステップ504において、外部HB処理を開始させる。通常、外部HB処理は、ノードがメッセージを破棄する結果となる。もしGIDが、メモリに格納されている識別と一致するならば、ノードは、ハートビート制御メッセージ300が順序通りであるかどうかを判定する。ノードは、Seq.No.315を、メモリ内のシーケンス番号と比較する。もしSeq.No.315が、メモリに格納されている値よりも小さいならば、ノードは、ステップ505において、そのメッセージを無視する。もしSeq.No.315が、メモリに格納されている値よりも大きいならば、ハートビート制御メッセージ300は、順序通りであり、ノードは、次いで、ステップ506において、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビート制御メッセージが新しいかどうかを判定する。
【0065】
もしノードが、メッセージを新しくないと判定するならば、ハートビート制御メッセージ300は、図5Bに明らかにされた軽度抑制プロセスステップ507を経る。もしHB300が新しくなく、そのノードによって又はダウンストリームノードによって送信されたものならば、そのHBは、破棄される。しかしながら、もし、ソースからのホップカウント(HC)330が自身の値と同じであるノード(ピアノード)によってHB300が受信される場合は、ノードは、キーノードにならない可能性を増やすために、待ち時間を延長する(ステップ571)。同様に、メッセージが新しい場合も、メッセージは、やはり、直ちに再ブロードキャストされるのではなく、HB送信待機タイマを使用してランダム時間の間(図5Cに示される)、又はダウンストリームノードがHBを再ブロードキャストするまで、キャッシュされる。ステップ572において、HBが再ブロードキャストされると、HB送信が真になり、HBは破棄される。
【0066】
再び図5Aに戻り、もしノードが、メッセージを新しいものと判定するならば、ノードは、自身がGHであるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ508において実施される。もしノードがGHであるならば、ステップ509において、ノードは、送信者のルーティングエントリを更新し、ハートビート制御メッセージ300は、中継されず、ノードは、アイドル状態500になる。しかしながら、もしノードがGN1500であるならば、ノードは、上述のように且つ図5Cにあるように、ステップ510において、全てのグループメンバエントリについてルーティングテーブルを更新し、HB制御メッセージ300を処理する。可能性のあるピアノード又はダウンストリームノードがHBを再ブロードキャストするまでHB送信待機タイマを待つことによって、ノードは、軽度に抑制され、不要なHB制御メッセージがブロードキャストされないことを確実にすることができる。
【0067】
もし制御メッセージがMR400であるならば、ノードは、ステップ511から始まるメッセージ処理を行う。ノードは、ステップ511において、メッセージがネイティブであるかどうかを判定する。ノードは、GID305を、メモリに格納されているグループ
識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノードは、ステップ512において、外部MR処理を開始させる。もしGIDが、メモリに格納されている識別と一致するならば、ノードは、そのMR400を送信したノードが、LPG115のメンバであるかどうかを判定する。ノードは、ノードID410を、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ノードは、ステップ514において、MR400をただ中継する。MRが中継されることによって、新しいグループノードは、完全なハートビートサイクルを待つ必要なくLPGに参加することができる。もしMRを送信したノードが参加リストに挙げられていない場合は、そのノードは、参加ノードであるとみなすことができる。ルーティングテーブルには、参加ノードのルーティングエントリはない。一実施形態では、ノードは、MRをGHに向けて転送することができる。ノードは、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノードは、(MRの)発信元ノードを宛先リストに追加することができる、すなわち、発信元ノードについてのルーティングエントリを予約しておくことができる。ノードは、中継ノード情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ300が受信されるときに、ノードは、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。更に、HCGH425を保存し、新しいハートビート制御メッセージのHC330と比較することができ、上記判定の結果は、新しいハートビート制御メッセージを転送するか否かを判定するために使用される。この中継ノード手続きは、図6において更に説明される。
【0068】
もし一致があるならば、ノードは、ステップ515において、MR400が順序通りであるかどうかを判定する。ノードは、MR SEQ.NO.405を、メモリ内のシーケンス番号と比較する。もしMR SEQ.NO.405が、メモリに格納されている値よりも小さいならば、ノードは、そのメッセージを無視し、アイドル状態500になる。もしMR SEQ.NO.405が、メモリに格納されている値よりも大きい又はその値と等しいならば、MR400は、順序通りであり、ノードは、次いで、ステップ516において、現シーケンス番号の発信元からノードが既にMRを受信しているかどうかを(最後に格納されたシーケンス番号と比較することによって)チェックすることによって、MRが新しいかどうかを判定する。もしノードが、メッセージを新しくないと判定するならば、ステップ517において、送信者のルーティングエントリのみが更新される。MRは、中継されない。もしノードが、メッセージを新しいと判定するならば、ノードは、自身がGHであるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ518において実施される。もしノードがGHであるならば、ステップ519において、ノードは、直接の送信者及び発信元のルーティングエントリを更新する。MR1800は、中継されず、ノードは、アイドル状態500になる。しかしながら、もしノードがGNであるならば、ノードは、ステップ520において、送信者及び発信元についてルーティングテーブルを更新し、MRを中継する。更に、MR400のSeq.No.405は保存され、後続のハートビート制御メッセージ300と比較される。この手続きは、図6A〜Cにおいて説明される。
【0069】
<中継ノードベースの効率的なフラッディング>
中継ノードベースの効率的なフラッディングメカニズムは、中継ノード(RN)を選択して、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばメンバシップレポート(MR)などの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、LPGのグループヘッダ(GH)であってもよい。
【0070】
図6A、B、及びCは、本発明の典型的実施形態にしたがった、このプロセスを示して
いる。手続きは、その大部分が図5の手続きに匹敵し、したがって、詳細な説明は省略される。大きな違いは、ステップ607、610、及び620において発生する。ステップ607は、HB配信がホップカウントと先行HB300との比較を条件としないという点で、軽度抑制方法と異なる。もしノードが、メッセージを新しくないと判定するならば、ステップ607において、送信者のルーティングエントリのみが更新される。ハートビート制御メッセージは、中継されない。ステップ620では、MR中継機能が、図6Cに示されたステップを反映するように変更される。もしノードが、MR400の次ホップであるならば、MR400のSeq.No.405は、ステップ621において格納され、MR中継機能622は、通常通りに呼び出される。そして、後続のハートビート制御メッセージ300の到着時において、ステップ610に達すると、図6Bの手続きが呼び出される。もしHB300のHC330が、ステップ611において上限内であるならば、HB300をブロードキャストするか否かを判定するために、ステップ612においてSeq.No.315とSeq.No.405との比較が行われる。具体的には、もし着信HBのSeq.No.315が、前MR400のSeq.No.405からプリセット定数を差し引いたものよりも大きいならば、HB300は、ステップ613において、通常通りにブロードキャストされる。しかしながら、もし新しいHBのSeq.No.315が、MR SEQ.NO.405からプリセット定数kを差し引いたものよりも小さいならば、HBは、破棄される。定数kは、制御メッセージのサイクルの数を定めるために設定された任意の数であってよい。kは、HBメッセージの頻度及びその他の要因に応じて動的パラメータとして実装されてよい。kは、可変であってよいが、値を5〜10サイクルに設定することによって良い結果を得られることが示されている。
【0071】
更に、メッセージを中継する効率を高めるため及び適時な配信を確実にするために、受動応答が追加されてよい。上述の実施形態では、ノードから、HBが受信されたという応答はない。したがって、HBの紛失に起因する構造的破壊を回避するために、ノードは、他のノードから伝送されたHBの受信者からの受動応答を、設定時間にわたって待つことができる。上記受動応答が受信されないときは、ノードは、第2のHB中継を発行し、フェイルセーフメカニズムとしてブラインドフラッディングをトリガすることができる。
【0072】
<GHとしてのRSUの使用>
RSUの役割は、LBRのユニキャスト性能に影響を及ぼす。前述のように、RSUは、GHとして使用されてもよい。RSUがGHになった場合は、RSU LPGの領域内の全ての車両は、LPGに属している。言い換えると、通行車両は、それがメンバであったLPGを破棄してよい。この場合、固定のLPG(RSU LPG)は、LBRを開始させず、RSUへのルートを形成するだけである。固定のLPG(RSU LPG)は、車両の再グループ分けを行わないが、RSUは、MRをトリガしない特別なHBを発行する。この特別なHBは、RSUへのルートを構築するためだけに使用される。RSUが車両へのルートを必要とするときは、RSUは、モバイルLPGのLPG制御メッセージ(HB及びMR)を使用することによって、車両へのルートを構築することができる。
【0073】
図7A及び図7Bは、図5において説明された軽度抑制技術と組み合わせた、この特別なHBを含むための改良方法を示している。具体的には、ステップ602及び603の追加が、この方法と図5との違いを示している。もしHBが、RSUからブロードキャストされるならば、そのHBは、図7Bのステップに基づいて、いずれかのフラッティング技術を経ることができる。
【0074】
本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかになるであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。
【符号の説明】
【0075】
100 RSU
110 移動車両
115 LPG
【技術分野】
【0001】
本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、マルチホップ車両アドホックネットワーク(VANET)における制御メッセージの効率的配布のための方法に関するものである。
【0002】
本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network(アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス)」と題された、2006年10月23日出願の共同所有の米国同時係属特許出願第11/585,047号(「’047出願」)に関連している。
【背景技術】
【0003】
無線通信は、それが無線ホームネットワーク若しくは無線オフィスネットワークであれ、ローカルカフェ、ファストフードチェーン、若しくはホテルにおけるいわゆる「ホットスポット」ネットワークであれ、又はひいては都市規模でのWiFi技術の実施であれ、今日の生活のあらゆる局面において普及してきている。無線通信社会を追い求めるこのような要求は、移動車両などの移動デバイスにまで広がっている。このタイプの無線ネットワーク構築は、道路障害物に関する緊急警告、交差点の調整、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含む、多くの車両安全応用の局面において出現する可能性がある。
【0004】
車両間安全通信(「VSC」)は、車両間通信、及びインフラストラクチャを介した車両通信に大別することができる。車両間通信では、車両同士は、固定されたインフラストラクチャからの支援を受けることなく通信しあう。車両同士は、互いに同じ電波範囲内にあるときに、又はその他の車両を通じたマルチホップ中継が可能であるときに、通信しあう。インフラストラクチャを介した車両通信では、車両同士は、路側の無線アクセスポイントなどのインフラストラクチャの支援を受けて通信しあう。このケースでは、車両は、インフラストラクチャのみと通信することもできる。
【0005】
重要なVSC性能要件は、衝突回避などの様々なVSC応用形態を支援するために、待ち時間が短いこと(約100ミリ秒)及びスループットを維持すること(別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合)を含む。’047出願は、1つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してLPGを維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループ(LPG)に編成するための方法を記載している。LPGは、ハートビート(HB)及びメンバシップレポート(MR)などの制御メッセージの伝送によって形成される。HBメッセージは、フラッディングメカニズムを使用して実装されている。移動車両は、ユニキャスト及びマルチキャストのルーティングに適応される。
【0006】
しかしながら、フラッディングは、ユニキャストプロトコル及びマルチキャストプロトコルを含むLPGベースのルーティングプロトコルの主要な制御オーバーヘッドである。各HBサイクルにおいて、HBは、少なくともLPG内のメンバの数と同じ回数だけ再ブロードキャストされる。交通渋滞などのように、近くにあるノードの数が大きい状況では、HBの重複によって、このオーバーヘッドが大幅に増大される。フラッディングは、全てのノードに対してフラッディングメッセージの再ブロードキャストを要求する。これらの状況では、フラッディングによって、更には大きいLPG内では制御メッセージの大サ
イズになるために、ネットワーク帯域幅が消費し尽くされる恐れがある。制御メッセージの配布は、LPGベースのプロトコルの中核的要素であるので、効率的な制御メッセージ配布が必要とされている。
【発明の概要】
【0007】
本発明は、VANETにおける効率的な制御メッセージ配布のためのシステム及び方法を提供する。選択されたキーノードによる限られた数の再ブロードキャストによってフラッディング(接続された全てのノードにメッセージを配信する)の目的を達成するために、効率的なフラッディングメカニズムが提供される。
【0008】
抑制ベースの効率的なフラッディングメカニズムは、軽度抑制(LS:Light Suppression)技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。
【0009】
また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノード(RN)を選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばダウンストリームノードのメンバシップレポート(MR)などの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、LPGのためのグループヘッダ(GH)であってもよい。
【0010】
一実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを効率的に散布するための方法である。方法は、少なくとも1つのルーティングパラメータを含む第1の制御メッセージをグループヘッダノードから受信することと、第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、もし第1の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、第1の制御メッセージを破棄することと、もし第1の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、もし上記時間の間に第1の制御メッセージをブロードキャストしたダウンストリームノードがないならば、上記時間の終了時に第1の制御メッセージをブロードキャストすることと、を含む。方法は、更に、シーケンス番号を使用して、第1の制御メッセージが順序通りであるかどうかを判定することと、もし順序通りでないならば、第1の制御メッセージを破棄することと、を含む。
【0011】
第1の制御メッセージは、複数のルーティングパラメータを内包している。複数のルーティングパラメータは、シーケンス番号と、グループリストと、グループヘッダノードまでのホップカウントと、グループヘッダノードへの次ホップとを含む。本方法は、更に、第1の制御メッセージの、グループヘッダノードまでのホップカウントを、現ノードの、グループヘッダノードまでのホップカウントと比較することを含み、もし2つのホップカウントが等しいならば、第1の制御メッセージはピアノードによってブロードキャストされている。もし第1の制御メッセージのホップカウントが、現ノードのホップカウントよりも小さいならば、第1の制御メッセージは、破棄される。もし第1の制御メッセージのホップカウントが、現ノードのホップカウントよりも大きいならば、時間は取り消され、制御メッセージの状態は「送信された」に設定される。
【0012】
本方法は、更に、第1の制御メッセージ内の複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、少なくとも1つの追加のルーティングパラメータを含む第2の制御メッセージを、ローカルピアグループ内のグルー
プノードから受信することと、少なくとも1つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。この転送テーブルに基づいて、パケットがルーティングされてよい。
【0013】
本方法は、更に、第2の制御メッセージに対するソースを判定することと、第2の制御メッセージの直接の送信者を判定することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。第1の制御メッセージの受信後に、ノードは、第1の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第1の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。ノードは、上記の増分及び挿入を実施した後に、第1の制御メッセージを転送し、第2の制御メッセージの受信後に、第2の制御メッセージをグループヘッダノードに転送する。
【0014】
本方法は、更に、第1の制御メッセージが路側機(RSU:road side unit)から受信されたかどうかを判定することと、もしそうであるならば、RSUのルーティングテーブルを更新すること及び第1の制御メッセージをブロードキャストすることと、を含む。
【0015】
別の実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、グループヘッダノードから第1の制御メッセージを受信することと、第1の制御メッセージをブロードキャストすることと、第1の制御メッセージに応じてローカルピアグループ内のグループノードから第2の制御メッセージを受信することと、第2の制御メッセージのシーケンス番号を格納することと、グループヘッダノードから第3の制御メッセージを受信することと、第3の制御メッセージのシーケンス番号を第2の制御メッセージのシーケンス番号と比較することと、第3の制御メッセージのシーケンス番号が、第2の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、第3の制御メッセージをブロードキャストすることと、を含む方法である。
【0016】
本方法は、更に、第3の制御メッセージのシーケンス番号が、第2の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも小さい場合に、第3の制御メッセージを破棄することを含む。プリセット定数は、第3の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する。
【0017】
本方法は、更に、第1の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、第2の制御メッセージに含まれる少なくとも1つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記の更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。
【0018】
本方法は、更に、第2の制御メッセージに対するソースを判定することと、第2の制御メッセージの直接の送信者を判定することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第2の制御メッセージ内の少なくとも1つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。転送テーブルは、情報のパケットをルーティングするために使用される。第3の制御メッセージの受信後に、ノードは、第3の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第3の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。
ノードは、上記の増分及び挿入を実施した後に、第3の制御メッセージを転送する。第2の制御メッセージの受信後に、ノードは、第2の制御メッセージをグループヘッダに転送する。
【0019】
特許請求の範囲の方法は、更に、第3の制御メッセージが路側機(RSU)から受信される場合に、RSUのルーティングエントリを更新すること及び第3の制御メッセージをブロードキャストすることを含む。
【図面の簡単な説明】
【0020】
【図1】発明にしたがった、アドホックネットワークの一例を示している。
【図2】本発明の典型的実施形態にしたがった、路側機(RSU)の基本的要素のブロック図を示している。
【図3】本発明の典型的実施形態にしたがった、ハートビート制御メッセージのフォーマットの一例を示している。
【図4】本発明の典型的実施形態にしたがった、メンバレポート制御メッセージのフォーマットの一例を示している。
【図5A】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5B】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5C】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図5D】本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。
【図6A】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図6B】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図6C】本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。
【図7A】本発明の典型的実施形態にしたがった、RSUからのハードビートメッセージを処理するための方法を示している。
【図7B】本発明の典型的実施形態にしたがった、RSUからのハードビートメッセージを処理するための方法を示している。
【発明を実施するための形態】
【0021】
本発明にしたがうと、アドホックネットワークは、2つのタイプのノードに、すなわち路側機(Road Side Unit:以下「RSU」)と移動車両とに分けられる。RSUが固定ノードである一方で、車両はグループで移動することができる。
【0022】
図1は、本発明にしたがった、アドホックネットワークの一例を示している。RSU100は、道路の側辺に沿って位置している。ネットワークにおいて使用されるRSU100の数は、RSU100の電波アンテナの範囲、所望の通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの数々の要因に依存する。図1は、2つのRSU100を示している。丸で囲われたエリアは、各RSU100の電波範囲を表わしている。各RSU100は、単独又はグループのいずれかで走行している移動車両110と通信するために使用することができる。
【0023】
移動車両110は、管理可能なグループに編成することができる。これらのグループは、ノード間のデータの伝送を調整するために使用される。グループは、隣接するノードの
相対的位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ(「LPG」)は、1つのLPG115内で及び複数のLPG間で電波信号をルーティングするための基礎である。
【0024】
図1は、3つのLPG115を示している。各LPG115は、少なくとも1つの移動車両110で構成される。図1は、LPG1 1151が3つの移動車両を含むこと、L
PG2 1152が2つの移動車両を含むこと、及びLPG3 1153が3つの移動車両を含むことを示している。RSU100は、LPG115内に存在して特別なLPGノードとして振る舞うことができる、又はLPG115の外側において別個のノードとして存在することができる。RSU100がLPG115内のノードではなく、LPG115と連携して使用されるときは、RSU100は、LPG間通信用の境界ノードとして振る舞うことができる。通常、1つのRSU100の電波有効範囲は、1つのLPGのサイズよりも大きい、すなわち、1つのRSU100の電波範囲内には、2つ以上のLPG115がある。このような場合が図1に示されている。したがって、1つのLPG115からのメッセージは、RSU100を使用して別のLPGにブロードキャストすることができる。この場合、RSU100は、そのメモリに格納されたLPGに関する情報を含む。
【0025】
移動車両110は、車両−車両(V−V)チャネルを通じて互いに通信する。移動車両は、車両−路側(V−R)チャネルを通じて路側機と通信する。また、RSU100は、R−Rチャネル又はR−B(バックボーン)チャネルを通じて互いに通信する。R−R通信は、専用チャネルつまり有線バックボーンを使用するので、この通信は、V−V通信又はV−R通信に干渉しない。V−VチャネルとV−Rチャネルとの間のチャネル共有についての代案が幾つかある。好ましい実施形態では、V−R通信用の専用チャネルがある。残りのチャネルは、V−V通信及び/又はV−R通信用に共有される。V−Rチャネルは、その他のチャネルと同じRF周波数帯域にあってよい。或いは、V−Rチャネルは、異なるRF周波数帯域にあって、異なる通信範囲及び異なるデータ速度を可能にしてよい。
【0026】
別の実施形態では、全てのチャネルが、V−V及びV−Rの両方のために動的に共有される。この手法は、性能の最適化を可能にする。しかしながら、干渉しないチャネルの探索及び選択において複雑性がもたらされる。
【0027】
別の実施形態にしたがうと、V−R用にのみ専用チャネルが割り当てられ、その他のチャネルは、V−V用だけに共有される。或いは、V−R用に専用チャネルが、そしてV−V用に第2の専用チャネルが使用される。残りのその他のチャネルは、V−V通信及びV−R通信用に共有される。発明の説明を続ける目的で、好ましい実施形態のチャネル割り当てが使用される。RSU100は、ルータ、アプリケーションサーバ、又はそれらの組み合わせなどの、多くの機能を有することができる。
【0028】
LPG115には、固定LPG、動的LPG、及びハイブリッドLPGなどの、幾つかのタイプのLPG115がある。固定LPGは、特定の位置又はエリアによって画定される。すなわち、もしノードが、例えばエリアAを画定するエリアにあるならば、そのノードは、LPG Aに所属する。もしノードが、例えばエリアBなどの異なるエリアにあるならば、そのノードは、LPG Bに所属し、以下同様である。固定LPGの具体的なサイズは、例えば電波アンテナの範囲、通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの様々な要因に依存する、設計上の一選択肢である。固定LPGの位置及びサイズは固定である。しかしながら、場所が異なると交通パターン及び人口(移動車両110)密度が異なるゆえに、各固定LPGは、それぞれ異なるサイズであってよい。もしRSU100が所定のLPG115内にあるならば、そのRSU100の電波範囲によって、固定LPGのサイズが画定される。
【0029】
RSU100を使用することによって、移動車両110は、RSU100からのハードビート制御メッセージ又はAP330からのビーコンのいずれかをヒアリングすることによって固定LPGの位置を検出することができる。移動車両110は、自身の位置変化とともに、固定LPGを変更していく。或いは、移動デバイスは、LPG115及びそれらの位置のデータベースを含む。別の実施形態において、もしとあるエリア内に複数のRSU100がある場合は、少なくとも1つのRSU100が、近隣にあるその他のRSU100の相対的なポジション又は位置に関する情報を提供することによって、移動車両100がLPG115を迅速に突き止められるようにして、複数のLPG115間のハンドオフを容易にすることができる。
【0030】
固定LPGは、たとえ一部のLPG115が空である又は多くの移動車両110を有さない場合でも、バックボーンアクセス又はLPG間通信を提供するように無線インフラストラクチャとの統合をサポートするという、重要な利点を有している。各固定LPGは、通信を容易にするように、一意の識別子を割り当てられている。どの固定LPGエリアも明確に画定されているので、LPG115の形成及び命名は、動的LPGよりも容易である。また、固定LPGを使用する場合、LPG115の併合及び分割に関する規則は問題ではない。
【0031】
第2のタイプのLPG115は、動的LPGである。固定LPGとは反対に、動的LPGは、隣接するノードの電波有効範囲に基づいて形成され、それにより、ノードは、他のノードの厳密な位置を考慮することなく通信を調整することができる。
【0032】
動的LPGは、電波有効範囲に基づいて形成されるので、LPG115内の移動車両110は、シングルホップ伝送又はマルチホップ伝送を通じて互いに及びRSU100と常に通信することができる。LPG115内の1つのノードは、低遅延で且つ効率的な通信を実施することができるように、各LPG115内のノードの数を又はこのノードから動的LPGの端までの電波ホップの数を適度に少なく維持するために、動的LPGのサイズを制御することができる。このノードは、後ほど詳述されるように、グループヘッダ(GH)と称される。また、固定LPGとは対照的に、動的LPGは、各LPG115内で常に通信が可能であることを確実にする。動的LPGでは、固定LPGと異なり、RSU100の電波範囲の外にLPG115を形成することができる。
【0033】
一実施形態では、アドホックピアツーピアネットワークを、1つ若しくは2つ以上の固定LPG又は1つ若しくは2つ以上の動的LPGで作成することができる。別の実施形態では、アドホックピアツーピアネットワークを、ハイブリッドLPGネットワークとして、固定LPG及び動的LPGの両方で作成することができる。ハイブリッドLPGネットワークは、固定LPG及び動的LPGの両者の利点を融合しつつ、それぞれを個別に利用した場合に生じる問題を排除する。
【0034】
ハイブリッド手法は、道路形状をうまく活用する。特に、インフラストラクチャが利用可能でないときに、動的LPGを使用してネットワークを形成する。一部のエリアにおいてインフラストラクチャが利用可能になると、固定LPGを使用して、動的LPG及びインフラストラクチャとのネットワークを形成することができる。例えば、道路インフラストラクチャなどのインフラストラクチャは、道路−車両通信又は道路支援通信を可能にする。
【0035】
一実施形態では、RSU100は、LPG115内のノードであってよく、移動車両110と同様のネットワーク機能を実行することができる。RSU100は、グループヘッダ(GH)又はグループノード(GN)のいずれかとしてLPG115に参加することができる。GHは、いかなるノード順番付け又はいかなるインフラストラクチャもなしにL
PG115を維持及び制御するように指定された、LPG115内の移動デバイス又はノードである。通常、LPG115内にGHは1つのみである。LPG115内のその他の全てのノードは、一般的なノードすなわちグループノード(「GN」)である。GNは、GHを通じてLPG115に参加する。
【0036】
各RSU100は、上述のようにルータ及びアプリケーションサーバに加えて、GH又はGNとして動作することができる。このように、各RSU100は、ノードをそれぞれGH又はGNとして機能させる又は動作させることを可能にする要素又は手段及びネットワーキングプロトコルを含む。したがって、たとえRSU100がGH又はGNのいずれかとして動作する場合でも、GH及びGNの両方のための全ての構造的な要素又は手段が存在し、ただし、動作のモードに基づいて特定の要素のみが機能している。RSU100は、したがって、GH又はGNの機能性を提供するためのハードウェア及びソフトウェアの両方を含んでいる。
【0037】
図2は、RSU100の基本的要素のブロック図を示している。RSUは、メモリセクション2100と、クロック2105と、タイマ2110と、送受信セクション2120と、制御手段2125と、電源2130とを含む。メモリセクション2100は、DRAM、SRAM、又はFlashを含む、任意のタイプのメモリであってよい。好ましい実施形態では、短期メモリは、キャッシュである。メモリセクション2100は、グループID(GID)、グループヘッダID、グループリスト、既定の最大LPGサイズ、LPG内のノードの数、及びその他のタイプの制御パラメータなどの、LPGに関する情報を格納する。
【0038】
クロック2105は、RSU100のためのタイミングを維持するために使用される。特に、クロック2105は、内部クロックとして機能し、タイマ2110を設定するための基準として使用される。タイマ2110は、様々なメッセージをいつブロードキャストするべきかを判定するために使用される、すなわち、GHの場合はハードビート間隔(T)を、又はGHの場合は応答メッセージを判定する。制御手段2125又はマイクロプロセッサは、メッセージの生成、ルーティング、及びタイマを含む、RSU100の全てのプロセスを制御する。送受信セクション2120は、制御手段2125と協働して、メモリセクション2100に格納されているデータからメッセージを作成又は生成する役割を担う。
【0039】
RSU100は、その電波範囲内にある全ての移動車両110及びその他のRSUに対し、ビーコン又はハードビート制御メッセージを定期的に伝送する。この期間は、固定間隔である。ハードビート間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。
【0040】
LPG115がRSU100の近くを移動するときは、ヘッダ解決プロトコルに基づいてGHが選出される。LPG115のGHである移動車両は、V−Vチャネル及びV−Rチャネルの両方にハードビート制御メッセージを送出する。やはりGHとして振る舞うRSU100は、V−Rチャネルのみにハートビートを送出する。2つ以上のGHがハートビート制御メッセージを送信すると、ヘッダ解決が発生する。これは、同じLPG115内に複数のGHがあるのを回避するためである。なぜならば、同じLPG115内に複数のGHがあると、結果として、そのLPG115内において冗長な(混乱を招く可能性すらある)制御信号が伝送又はブロードキャストされ、帯域幅及び容量が無駄遣いされるからである。ヘッダ解決は、少なくとも2つのGHから1つのGHを選択する働きをする。
【0041】
ユニキャストルーティングプロトコルは、各ノード内におけるルーティングテーブルの作成に基づく。ルーティングテーブルは、少なくとも、メッセージについての宛先及び次
ホップを含む。LPG115内の全ての移動車両110は、ルーティング機能を実施し、その他の車両がシングルホップ又はマルチホップのいずれかで通信するのを助ける。LPG内ルーティングテーブルは、LPG形成メッセージを使用してブロードキャストモードにおいて制御メッセージを交換することによって構成される。ユニキャストルーティングでは、追加の制御メッセージは不要である。LPG形成に使用されるのと同じ制御メッセージが、ルーティングプロトコルのためのルーティングテーブルの作成、維持、及び更新のために使用される。ルーティングテーブルは、LPG内ルーティングに使用される。不要なノードに外部制御メッセージが伝搬されることがないように、あらゆる制御メッセージにLPG識別子が埋め込まれる。全ての外部制御メッセージは、終了される又は中継されない。
【0042】
制御メッセージメッセージは、GHからのハートビート(HB)及びGNからのメンバシップレポート(MR)である。ハードビート制御メッセージは、LPGの領域を画定する。ハートビートメッセージと、それに続くメンバシップレポートとが、1つの制御メッセージサイクルを構成する。
【0043】
’047出願で説明されている別の実施形態では、LPGネットワークは、マルチキャストメッセージ機能をサポートすることができる。ユニキャストでは、送信ノード(例えば事故の目撃者)は、1つの特定の受信者にメッセージを送信する又は向かわせるので、同じ情報を複数の受信者に送信するためには複数のメッセージが必要である。これは、大量のネットワーク帯域幅の消費及びメッセージの遅延を引き起こす結果となる。マルチキャスト伝送では、送信者は、メッセージの重複コピーを生成せず、1つのメッセージを全ての受け手に対して送信する。マルチキャストによって、ネットワーク帯域幅は大幅に節約される。
【0044】
<HBメッセージ>
図3は、ハートビート制御メッセージ300のフォーマットの一例を示している。ハートビート制御メッセージ300は、LPG識別子すなわちGID305及びグループヘッダ310の両方を含む一意の識別子を含む。
【0045】
GID305及びグループヘッダID310は、各LPG115を識別する。GID305には、幾つかの可能なフォーマットがある。一実施形態では、GID305は、LPG115のためにランダムに選択された識別番号であってよい。或いは、GID305は、LPGの形成の順番に基づいて割り当てられた識別番号であってよい。例えば、第1のLPGは、LPG1というGID305を有することができ、第2のLPGのGID305は、LPG2であり、以下同様である。しかしながら、GHの変化とともに、GID305も変化し、その結果、ノードは、そのLPGが変化したのか又は単にLPG115のIDが変化したのかを区別することができなくなる。他方で、GHが去るときに、GID305を元のIDに固定してもよい。しかしながら、これは、1つのLPGが分裂するときに、GID305の重複を生じる可能性がある。その結果、2つ又は3つのグループが、同じGID305を有することになる。一実施形態では、GID305は、LPG115を一意に識別するために、LPG ID番号及びGH ID番号の両方に基づいて符号化される。
【0046】
GHは、グループヘッダID310を与えられる。最初、GID305は、グループヘッダID310に結び付いている。したがって、グループヘッダID310は、最初は、GID305の一部分として使用されるが、GHの変化とともに、新しいグループヘッダID310を含むように変化する。各GHは、グループヘッダID310を割り当てられる。グループヘッダID310は、(パブリック又はプライベート)IPアドレスに基づいて割り当てられる。図3に示されるように、グループヘッダID310は、IPv6
IPアドレスである。別の実施形態では、グループヘッダID310は、IPv4アドレスであってよい。
【0047】
ハードビート制御メッセージは、また、シーケンス番号(sequence number:Seq.
No.)315も含む。Seq.No.315は、ハートビート制御メッセージの順番を追跡して、受信されたハートビート制御メッセージ300が新しいすなわち新着であるかどうかを判定するために使用される。GNは、受信されたハートビート制御メッセージのSeq.No.315を記憶している。新たなすなわち新着のハートビート制御メッセージは、次のSeq.No.315を伴う最初のハートビート制御メッセージによって示される。Seq.No.315は、また、どのハートビート制御メッセージが(次ホップノードに)中継されるべきかを判定するためにも使用される、すなわち、先着のみ中継(FCRO:first come relay only)戦略を使用することができる。新たな(すなわち新着
の)ハートビート制御メッセージのみが中継されるべきである。ノードは、先のシーケンス番号を記憶しており、それを着信ハートビート制御メッセージのシーケンス番号と比較して、そのハートビート制御メッセージが新しいすなわち新着であるかどうかを判定する。もし適切なGID305を伴うハートビート制御メッセージのSeq.No.315が、現時点で格納されているシーケンス番号よりも大きいならば、それは、新たなすなわち新着のハートビート制御メッセージ300であり、したがって、FCROが使用される場合は中継される。GNに先に格納されていたシーケンス番号は、破棄され、新たなシーケンス番号に置き換えられる。
【0048】
ハートビート制御メッセージ300は、更に、ハートビート期間(HB期間)320に関する情報も含む。この期間は、固定間隔(T)である。間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。HB期間320は、次のハートビート制御メッセージがいつブロードキャストされるかを、全てのGNに対して示す。GNは、HB期間320内にハートビート制御メッセージを受信しない場合は、ハートビート制御メッセージが連続的に送信されるように、新たなハートビート制御メッセージを伝送する。もし元のGHが依然としてLPG115内にあるならば、ヘッダ解決が発生する。制御オーバーヘッドを低減させるために、GHは、HB期間320を調整することができる。調整は、LPGのサイズ、LPG内のノードの位置、負荷、速度、及び数に基づくことができる。
【0049】
ハートビート制御メッセージ300は、例えば、完全なグループリストを伴う、漸増性のグループリストを伴う、又はグループリストを伴わないなどの、ハートビート制御メッセージのタイプも含む。一実施形態では、ハートビート制御メッセージは、全てのメッセージ内に、完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビート制御メッセージには、大量の帯域幅が必要である。ハートビート間隔(T)は、制御オーバーヘッドを低減させるように調整することができる。別の実施形態では、(n−1)個おきの各ハートビート制御メッセージが完全グループリストを含む。例えば、2つおきの各ハートビート制御メッセージが完全グループリストを含む。これは、平均のハートビート制御メッセージに対する帯域幅を低減させる。しかしながら、LPG115内のノードの大半は、速いペースで移動しているので、受信されるグループリストは、古くなっている可能性がある。言い換えると、ノードによって新たなグループリストが受信された時点で、グループの幾つかのメンバは、別のLPG115内にある可能性がある。別の実施形態では、進行性のグループリスト又は漸増性のグループリストを配布することができる。グループリストは、そのリスト内のメンバシップに変更があるときにのみ配布される。進行性のグループリスト又は漸増性のグループリストもまた、メンバシップリストが古くなる可能性がある。
【0050】
或いは、ハートビート制御パッケージのタイプは、ハイブリッドグループリスト更新であってよい。メンバシップに変更があるときは、ハートビート制御メッセージに進行性のグループリストを含めることができ、更に、(n−1)個おきの各ハートビート制御メッセージには、完全なグループリストを含めることができる。ToHB(type of heartbeat)325は、ハートビート制御メッセージのタイプを示す。ハートビート制御メッセー
ジのタイプは、LPG115のトポロジ変化速度及びハートビート制御メッセージのブロードキャストの頻度によって影響される。LPG115のトポロジ変化速度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性が高まる。ハートビート制御メッセージのブロードキャストの頻度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性は減少する。
【0051】
ハートビート制御メッセージは、GHからのホップカウント(HC)330を含む。最初、HC330は、例えば1などの既定の値に設定される。ハートビート制御メッセージがノードによって中継されるたびに、中継ノードは、HC330の値を1だけ増加させる、すなわち、HC=HC+1とする。HC値は、LPGサイズを制限するため、ハートビート制御メッセージ内の情報の古さを示すため、及び制御メッセージのルーティングを制御してオーバーヘッドを低減させるために使用することができる。LPGごとに、例えば10などの、ルーティングの最大ホップカウントがある。HCが最大ホップカウントまで増分されると、例えばハートビート制御メッセージなどの制御メッセージは、中継されなくなる。
【0052】
ホップカウントは、中継戦略にも使用することができる。一実施形態では、ハートビート制御メッセージは、最低のホップカウントを有する場合に中継するようにしてもよい。この方法は、GHからの正しいホップカウントを保証するが、ただし、待ち遅延がある。ノードは、ハートビート制御メッセージについて最低のホップカウントを判定する必要があるので、同ハートビート制御メッセージを中継する前に、全てのアップストリームノードからハートビート制御メッセージが受信されるまで待機する必要がある。したがって、最低のホップカウント及び上記の先着のみ中継戦略の両方を使用した、複合的な中継戦略を実装することができる。ハートビート制御メッセージは、より低いホップカウントのハートビート制御メッセージがノードによって受信されるまでは、先着のみ中継戦略を使用して中継される。ノードAは、ハートビート制御メッセージを転送するときに、ハートビート制御メッセージを誰が中継したのかを次ホップノードが知ることができるように、メッセージ内にID情報を含ませる。メッセージを転送するノード(ノードA)は、すると、ノードAから初めてハートビート制御メッセージを受信した次ホップノードにとって、(GHに向けてMRを送信するための)MR中継ノードにもなる。
【0053】
最大ホップカウント、HC330、及びSeq.No.315を利用することによって、LPG115内における制御メッセージのフラッディングの無限の重複が阻止される。本発明の一実施形態にしたがうと、ノードは、フラッディングソースからのホップカウント(HC)が自身のものよりも小さいようなフラッディング中継を横聞き(overhear)すると、そのフラッディングメッセージの中継を中止する。この方法は、図5において更に説明される。ノードは、新たなハートビート制御メッセージ300を受信すると、そのハートビートを中継する前に、設定時間(HB送信待機タイマによって定められる)の間、待機する。もしこの時間の間に、ダウンストリームノード又はピアノードがそのハートビートを再ブロードキャストする場合は、その再ブロードキャストされたハードビートのHCが、現(格納されている)HC330と比較される。もし受信されたHCが現HC330よりも小さいならば、ハートビートが不必要にブロードキャストされないように、メッセージは破棄される。もし2つのHCが同じであるならば、再ブロードキャストしているノードはピアノードであり、現ノードは、自身がキーノードにならない可能性を増やすために、HB送信待機タイマを増加させる又はリセットする。もし受信されたHCが現HC
よりも大きいならば、現HB送信待機タイマは取り消され、ハートビートは送信される。より詳しくは、図5を参照せよ。
【0054】
別の実施形態では、効率的な制御メッセージ中継ツリーを構築するために、中継ノード(RN)が選択される。この方法は、メッセージを中継するか否かを判定するために、ハートビート制御メッセージ300のSeq.No.315を使用する。中継ノードは、少なくとも1つのメンバレポート(MR)をアップストリームノードに又はGHに中継するノードである。この方法は、図6において更に説明される。通常、ハートビート制御メッセージ300は、ノードからのメンバシップレポート(MR)をトリガする。MRの内容は、次項及び図4において説明される。ノードは、MRを中継するときはいつも、MRの最新のシーケンス番号(HBのSeq.No.315に対応する)を格納し、MRを複製し、次ホップを置き換え、MRをブロードキャストする。後続のHB300が受信され、そのSeq.No.315が、格納されているMRのSeq.No.と比較される。MRの配信は、(’047出願に記載されているように)中継ノードを自動的に選択するので、シーケンス番号の比較は、選択された中継ノードのみが後続のHB制御メッセージを展開することを確実にし、そうして、HBフラッディング中における不要な制御メッセージの量を低減させる。
【0055】
上記のように、ハートビート制御メッセージは、グループリスト335も含むことができる。グループリスト335は、LPG115内のメンバの数、各数のIPアドレス、GHからのホップカウント、及び分類などの、LPG115のメンバに関する情報を含むことができる。
【0056】
分類は、例えばアップリンク、ダウンリンク、及びピアなどのような、GHノードからの相対的方向に言及したコードであってもよい。ピア分類は、ノードがGHから同じ無線有効範囲内にあることを示している、すなわち、全てのピアノードは、GHからのホップカウントが同じである。アップストリームノードは、ハートビート制御メッセージによって判定される。ダウンストリームノードは、メンバシップレポート(MR)に基づいて判定される。アップストリーム伝送は、GHに向かう通信を表しており、ダウンストリーム伝送は、GHから離れる通信を表している。この分類は、相対的表現である。各GNは、自身に隣接するノードを3つの異なるクラスに分類することができる。もし別のGNのメンバシップレポートが、自身のHCよりも1だけ小さいホップカウント(HC)を有するならば、GN(自身)はアップストリームノードである。もし別のGNのHCが、自身のHCと同じであるならば、GN(自身)はピアである。もし別のGNのHCが、自身のHCよりも1だけ大きいならば、GN(自身)はダウンストリームノードである。
【0057】
図4は、メンバシップレポート(MR)400を示している。MR400は、GNによってブロードキャストされ、GHによって受信される制御メッセージである。MRは、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードに対する次ホップなどの、収集可能なルーティング情報を含んでいる。MRは、ハートビート制御メッセージ300と同じ情報の幾つかを、すなわちGID305及びグループヘッダID310を含んでいる。MR400は、また、MR SEQ.NO.405も含む。MR Seq.No.は、ハートビート制御メッセージ300のSeq.No.315と同様であり、MRの順番を維持するために使用される。MR SEQ.NO.405は、1つの特定のノードに対するMRの順番である。通常、MR SEQ.NO.405は、MRをトリガしたハートビート制御メッセージ300のSeq.No.315と同じ値を有する。
【0058】
したがって、図6において更に説明される本発明の一実施形態では、MR400のSeq.No.405は、現ノードのメモリに格納され、後続のハートビート制御メッセージ
のそれと比較される。もし到着したメッセージのSeq.No.が、現時点で格納されているSeq.No.405からプリセット数kを差し引いたものよりも大きいならば、そのノードは、中継ノードである。定数kは、冗長性を実装してLPGの崩壊を阻止するために、kサイクルの緩和を導入する。
【0059】
発信元ノードの、すなわちMRを生成したノードの、ノードID410も、MR400に含まれる。MRは、次ホップ中継ID415も含む。次ホップ中継ID415は、GHに向かうMR400に対する中継命令である。次ホップ情報は、受信されたハートビート制御メッセージ300をもとに直接決定される。ノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、いかなるメッセージ処理よりも前に、IP層及びMAC層をもとにして前中継ノードの識別を再取得する。以前の中継ノードの識別は、メモリに格納されており、MRに対する次ホップ中継ID415として使用される。ハートビート制御メッセージを転送するときに、ノードは、そのIDをメッセージ内に含ませる。受信側の次ホップノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、このIDを、GHに到達するための次ホップ中継IDとして格納する。新たなすなわち新着のハートビート制御メッセージは、最低のHCを伴う、より新しいシーケンス番号を有するメッセージである。
【0060】
MR400は、また、「MRのタイプの指標」420も含む。MRには、2つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバMRは、発信元ノードからのMRのみを含む。統合複数メンバレポートは、2つ以上のノードのMRを含む。統合レポートは、オーバーヘッド、及び制御メッセージに必要な帯域幅を低減させるために使用することができる。複数のMRを含む1つのMRが送信される。
【0061】
また、MRは、GHからのホップカウント(HCGH)425を含むことができる。(HCGH)425は、GHからMRの発信元ノードまでのHC値である。別の実施形態では、MRは、累積メンバシップリスト430及びその他の追加の情報435を含むことができる。累積メンバシップリスト430は、LPGのメンバのIPアドレス、メンバの数、及び対応するホップカウントを含む。
【0062】
MR400は、逆経路方法又は逆フラッディング方法を使用してGHに配信又は中継することができる。逆経路方法は、ハートビート制御メッセージ300を中継するために使用されたものと同じ経路を使用して、MRをGHに向けて中継する。MRが中継されるときに、中継ノードは、次ホップ中継415を、GHに向かう次ホップに置き換える。対応するIDを有するノードのみが、MRメッセージを中継する。この方法は、伝送における対称性を想定している。もし非対称リンクが存在する場合は、逆フラッディング方法が使用される、すなわち、発信元ノードとGHとの間の全てのノードがMRを中継する。これは、後続のハートビート制御メッセージ配信のための中継ノード(RN)を選択するために使用可能な選択手続きである。
【0063】
各ノードは、LPGベースのルーティングのための転送テーブルとして使用することができるルーティングテーブルを作成するために、ハートビート制御メッセージ300及びMR400の両方を使用する。好ましい実施形態では、各ハートビート制御メッセージは、完全なグループリストを含み、LPG115内の全てのGNが、それに対してMRで応答する。ハートビート制御メッセージは、先着のみ中継方法を使用して中継され、MRは、逆経路方法を使用して、単一MRとしてGHに向けて中継される。
【0064】
<軽度抑制ベースの効率的なフラッディング>
抑制ベースの効率的なフラッディングメカニズムは、軽度抑制(LS:Light Suppress
ion)技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。図5Aは、この方法を示している。最初、ステップ500において、各ノードはアイドル状態にある。ステップ501において、メッセージが到着すると、ノードは、ステップ502において、メッセージがハートビート制御メッセージ300であるか又はMR400であるかを判定する。制御メッセージのタイプに応じて、ノードは、特別なメッセージ処理を実施する。もし制御メッセージがハートビート制御メッセージ300であるならば、ノードは、ステップ503から始まるメッセージ処理を行う。ノードは、ステップ503において、メッセージがネイティブであるかどうかを判定する。メッセージは、同じLPG115に対するメッセージである場合に、すなわち、同じGID305を有する場合に、ネイティブである。ノードは、GID305を、メモリに格納されているグループ識別と比較する。もしGID305が、メモリに格納されている識別と一致しないならば、ノードは、ステップ504において、外部HB処理を開始させる。通常、外部HB処理は、ノードがメッセージを破棄する結果となる。もしGIDが、メモリに格納されている識別と一致するならば、ノードは、ハートビート制御メッセージ300が順序通りであるかどうかを判定する。ノードは、Seq.No.315を、メモリ内のシーケンス番号と比較する。もしSeq.No.315が、メモリに格納されている値よりも小さいならば、ノードは、ステップ505において、そのメッセージを無視する。もしSeq.No.315が、メモリに格納されている値よりも大きいならば、ハートビート制御メッセージ300は、順序通りであり、ノードは、次いで、ステップ506において、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビート制御メッセージが新しいかどうかを判定する。
【0065】
もしノードが、メッセージを新しくないと判定するならば、ハートビート制御メッセージ300は、図5Bに明らかにされた軽度抑制プロセスステップ507を経る。もしHB300が新しくなく、そのノードによって又はダウンストリームノードによって送信されたものならば、そのHBは、破棄される。しかしながら、もし、ソースからのホップカウント(HC)330が自身の値と同じであるノード(ピアノード)によってHB300が受信される場合は、ノードは、キーノードにならない可能性を増やすために、待ち時間を延長する(ステップ571)。同様に、メッセージが新しい場合も、メッセージは、やはり、直ちに再ブロードキャストされるのではなく、HB送信待機タイマを使用してランダム時間の間(図5Cに示される)、又はダウンストリームノードがHBを再ブロードキャストするまで、キャッシュされる。ステップ572において、HBが再ブロードキャストされると、HB送信が真になり、HBは破棄される。
【0066】
再び図5Aに戻り、もしノードが、メッセージを新しいものと判定するならば、ノードは、自身がGHであるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ508において実施される。もしノードがGHであるならば、ステップ509において、ノードは、送信者のルーティングエントリを更新し、ハートビート制御メッセージ300は、中継されず、ノードは、アイドル状態500になる。しかしながら、もしノードがGN1500であるならば、ノードは、上述のように且つ図5Cにあるように、ステップ510において、全てのグループメンバエントリについてルーティングテーブルを更新し、HB制御メッセージ300を処理する。可能性のあるピアノード又はダウンストリームノードがHBを再ブロードキャストするまでHB送信待機タイマを待つことによって、ノードは、軽度に抑制され、不要なHB制御メッセージがブロードキャストされないことを確実にすることができる。
【0067】
もし制御メッセージがMR400であるならば、ノードは、ステップ511から始まるメッセージ処理を行う。ノードは、ステップ511において、メッセージがネイティブであるかどうかを判定する。ノードは、GID305を、メモリに格納されているグループ
識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノードは、ステップ512において、外部MR処理を開始させる。もしGIDが、メモリに格納されている識別と一致するならば、ノードは、そのMR400を送信したノードが、LPG115のメンバであるかどうかを判定する。ノードは、ノードID410を、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ノードは、ステップ514において、MR400をただ中継する。MRが中継されることによって、新しいグループノードは、完全なハートビートサイクルを待つ必要なくLPGに参加することができる。もしMRを送信したノードが参加リストに挙げられていない場合は、そのノードは、参加ノードであるとみなすことができる。ルーティングテーブルには、参加ノードのルーティングエントリはない。一実施形態では、ノードは、MRをGHに向けて転送することができる。ノードは、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノードは、(MRの)発信元ノードを宛先リストに追加することができる、すなわち、発信元ノードについてのルーティングエントリを予約しておくことができる。ノードは、中継ノード情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ300が受信されるときに、ノードは、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。更に、HCGH425を保存し、新しいハートビート制御メッセージのHC330と比較することができ、上記判定の結果は、新しいハートビート制御メッセージを転送するか否かを判定するために使用される。この中継ノード手続きは、図6において更に説明される。
【0068】
もし一致があるならば、ノードは、ステップ515において、MR400が順序通りであるかどうかを判定する。ノードは、MR SEQ.NO.405を、メモリ内のシーケンス番号と比較する。もしMR SEQ.NO.405が、メモリに格納されている値よりも小さいならば、ノードは、そのメッセージを無視し、アイドル状態500になる。もしMR SEQ.NO.405が、メモリに格納されている値よりも大きい又はその値と等しいならば、MR400は、順序通りであり、ノードは、次いで、ステップ516において、現シーケンス番号の発信元からノードが既にMRを受信しているかどうかを(最後に格納されたシーケンス番号と比較することによって)チェックすることによって、MRが新しいかどうかを判定する。もしノードが、メッセージを新しくないと判定するならば、ステップ517において、送信者のルーティングエントリのみが更新される。MRは、中継されない。もしノードが、メッセージを新しいと判定するならば、ノードは、自身がGHであるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ518において実施される。もしノードがGHであるならば、ステップ519において、ノードは、直接の送信者及び発信元のルーティングエントリを更新する。MR1800は、中継されず、ノードは、アイドル状態500になる。しかしながら、もしノードがGNであるならば、ノードは、ステップ520において、送信者及び発信元についてルーティングテーブルを更新し、MRを中継する。更に、MR400のSeq.No.405は保存され、後続のハートビート制御メッセージ300と比較される。この手続きは、図6A〜Cにおいて説明される。
【0069】
<中継ノードベースの効率的なフラッディング>
中継ノードベースの効率的なフラッディングメカニズムは、中継ノード(RN)を選択して、制御メッセージ配信のための効率的なフラッディングツリーを形成する。RNは、「k」回の前制御メッセージサイクルにおいて、例えばメンバシップレポート(MR)などの少なくとも1つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、LPGのグループヘッダ(GH)であってもよい。
【0070】
図6A、B、及びCは、本発明の典型的実施形態にしたがった、このプロセスを示して
いる。手続きは、その大部分が図5の手続きに匹敵し、したがって、詳細な説明は省略される。大きな違いは、ステップ607、610、及び620において発生する。ステップ607は、HB配信がホップカウントと先行HB300との比較を条件としないという点で、軽度抑制方法と異なる。もしノードが、メッセージを新しくないと判定するならば、ステップ607において、送信者のルーティングエントリのみが更新される。ハートビート制御メッセージは、中継されない。ステップ620では、MR中継機能が、図6Cに示されたステップを反映するように変更される。もしノードが、MR400の次ホップであるならば、MR400のSeq.No.405は、ステップ621において格納され、MR中継機能622は、通常通りに呼び出される。そして、後続のハートビート制御メッセージ300の到着時において、ステップ610に達すると、図6Bの手続きが呼び出される。もしHB300のHC330が、ステップ611において上限内であるならば、HB300をブロードキャストするか否かを判定するために、ステップ612においてSeq.No.315とSeq.No.405との比較が行われる。具体的には、もし着信HBのSeq.No.315が、前MR400のSeq.No.405からプリセット定数を差し引いたものよりも大きいならば、HB300は、ステップ613において、通常通りにブロードキャストされる。しかしながら、もし新しいHBのSeq.No.315が、MR SEQ.NO.405からプリセット定数kを差し引いたものよりも小さいならば、HBは、破棄される。定数kは、制御メッセージのサイクルの数を定めるために設定された任意の数であってよい。kは、HBメッセージの頻度及びその他の要因に応じて動的パラメータとして実装されてよい。kは、可変であってよいが、値を5〜10サイクルに設定することによって良い結果を得られることが示されている。
【0071】
更に、メッセージを中継する効率を高めるため及び適時な配信を確実にするために、受動応答が追加されてよい。上述の実施形態では、ノードから、HBが受信されたという応答はない。したがって、HBの紛失に起因する構造的破壊を回避するために、ノードは、他のノードから伝送されたHBの受信者からの受動応答を、設定時間にわたって待つことができる。上記受動応答が受信されないときは、ノードは、第2のHB中継を発行し、フェイルセーフメカニズムとしてブラインドフラッディングをトリガすることができる。
【0072】
<GHとしてのRSUの使用>
RSUの役割は、LBRのユニキャスト性能に影響を及ぼす。前述のように、RSUは、GHとして使用されてもよい。RSUがGHになった場合は、RSU LPGの領域内の全ての車両は、LPGに属している。言い換えると、通行車両は、それがメンバであったLPGを破棄してよい。この場合、固定のLPG(RSU LPG)は、LBRを開始させず、RSUへのルートを形成するだけである。固定のLPG(RSU LPG)は、車両の再グループ分けを行わないが、RSUは、MRをトリガしない特別なHBを発行する。この特別なHBは、RSUへのルートを構築するためだけに使用される。RSUが車両へのルートを必要とするときは、RSUは、モバイルLPGのLPG制御メッセージ(HB及びMR)を使用することによって、車両へのルートを構築することができる。
【0073】
図7A及び図7Bは、図5において説明された軽度抑制技術と組み合わせた、この特別なHBを含むための改良方法を示している。具体的には、ステップ602及び603の追加が、この方法と図5との違いを示している。もしHBが、RSUからブロードキャストされるならば、そのHBは、図7Bのステップに基づいて、いずれかのフラッティング技術を経ることができる。
【0074】
本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかになるであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。
【符号の説明】
【0075】
100 RSU
110 移動車両
115 LPG
【特許請求の範囲】
【請求項1】
無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
少なくとも1つのルーティングパラメータを含む第1の制御メッセージをグループヘッダノードから受信することと、
前記第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、
もし前記第1の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、前記第1の制御メッセージを破棄することと、
もし前記第1の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、
もし前記時間の間に前記第1の制御メッセージをブロードキャストしたダウンストリームノードがないならば、前記時間の終了時に前記第1の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項2】
請求項1に記載の方法であって、更に、
シーケンス番号を使用して、前記第1の制御メッセージが順序通りであるかどうかを判定することと、
もし順序通りでないならば、前記第1の制御メッセージを破棄することと、
を備える方法。
【請求項3】
請求項2に記載の方法であって、
前記第1の制御メッセージは、複数のルーティングパラメータを含み、前記複数のルーティングパラメータは、更に、シーケンス番号と、グループリストと、前記グループヘッダノードまでのホップカウントと、前記グループヘッダノードへの次ホップとを含む、方法。
【請求項4】
請求項3に記載の方法であって、
前記第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することは、更に、
前記第1の制御メッセージの、前記グループヘッダノードまでの前記ホップカウントを、前記現ノードの、前記グループヘッダノードまでのホップカウントと比較することであって、もし前記2つのホップカウントが等しいならば、前記第1の制御メッセージはピアノードによってブロードキャストされている、ことを含む、方法。
【請求項5】
請求項4に記載の方法であって、更に、
もし前記第1の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも小さいならば、前記第1の制御メッセージを破棄することと、
もし前記第1の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも大きいならば、前記時間を取り消し、前記複数のルーティングパラメータ内における前記制御メッセージの状態を「送信済み」に設定することと、
を備える方法。
【請求項6】
請求項5に記載の方法であって、更に、
前記複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、
少なくとも1つの追加のルーティングパラメータを含む第2の制御メッセージを、前記ローカルピアグループ内のグループノードから受信することと、
前記少なくとも1つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
を備える方法。
【請求項7】
請求項6に記載の方法であって、更に、
前記第2の制御メッセージに対するソースを判定することと、
前記第2の制御メッセージの直接の送信者を判定することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
前記第2の制御メッセージ内の上記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
を備える方法。
【請求項8】
請求項7に記載の方法であって、
前記転送テーブルは、情報のパケットをルーティングするために使用される、方法。
【請求項9】
請求項8に記載の方法であって、
前記第1の制御メッセージの受信後に、ノードは、前記第1の制御メッセージ内の前記ホップカウントを増分させ、前記ノードの識別を、前記第1の制御メッセージ内の、前記グループヘッダノードへの前記次ホップに挿入する、方法。
【請求項10】
請求項9に記載の方法であって、
前記ノードは、前記増分及び前記挿入を実施した後に、前記第1の制御メッセージを転送する、方法。
【請求項11】
請求項9に記載の方法であって、
前記第2の制御メッセージの受信後に、ノードは、前記第2の制御メッセージを前記グループヘッダノードに転送する、方法。
【請求項12】
請求項5に記載の方法であって、更に、
もし前記第1の制御メッセージが路側機(RSU)から受信されるならば、前記RSUの前記ルーティングテーブルを更新することと、
前記第1の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項13】
無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
グループヘッダノードから第1の制御メッセージを受信することと、
前記第1の制御メッセージをブロードキャストすることと、
前記第1の制御メッセージに応じて前記ローカルピアグループ内のグループノードから第2の制御メッセージを受信することと、
前記第2の制御メッセージのシーケンス番号を格納することと、
前記グループヘッダノードから第3の制御メッセージを受信することと、
前記第3の制御メッセージの前記シーケンス番号を前記第2の制御メッセージの前記シーケンス番号と比較することと、
前記第3の制御メッセージの前記シーケンス番号が、前記第2の制御メッセージの前記シーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、前記第3の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項14】
請求項13に記載の方法であって、更に、
前記第3の制御メッセージの前記シーケンス番号が、前記第2の制御メッセージの前記シーケンス番号から前記プリセット定数を差し引いた値よりも小さい場合に、前記第3の制御メッセージを破棄することを備える方法。
【請求項15】
請求項14に記載の方法であって、
前記プリセット定数は、前記第3の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する、方法。
【請求項16】
請求項14に記載の方法であって、更に、
前記第1の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、
前記第2の制御メッセージに含まれる前記少なくとも1つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
を備える方法。
【請求項17】
請求項16に記載の方法であって、更に、
前記第2の制御メッセージに対するソースを判定することと、
前記第2の制御メッセージの直接の送信者を判定することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
を備える方法。
【請求項18】
請求項17に記載の方法であって、
前記転送テーブルは、情報のルーティングパケットのために使用される、方法。
【請求項19】
請求項18に記載の方法であって、
前記第3の制御メッセージの受信後に、ノードは、前記第3の制御メッセージ内のホップカウントを増分させ、前記ノードの識別を、前記第3の制御メッセージ内の、グループヘッダノードへの前記次ホップに挿入する、方法。
【請求項20】
請求項19に記載の方法であって、
前記ノードは、前記増分及び前記挿入を実施した後に、前記第3の制御メッセージを転送する、方法。
【請求項21】
請求項20に記載の方法であって、
前記第2の制御メッセージの受信後に、ノードは、前記第2の制御メッセージを前記グループヘッダに転送する、方法。
【請求項22】
請求項15に記載の方法であって、更に、
前記第3の制御メッセージが路側機(RSU)から受信される場合に、前記RSUの前記ルーティングエントリを更新することと、
前記第3の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項1】
無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
少なくとも1つのルーティングパラメータを含む第1の制御メッセージをグループヘッダノードから受信することと、
前記第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、
もし前記第1の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、前記第1の制御メッセージを破棄することと、
もし前記第1の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、
もし前記時間の間に前記第1の制御メッセージをブロードキャストしたダウンストリームノードがないならば、前記時間の終了時に前記第1の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項2】
請求項1に記載の方法であって、更に、
シーケンス番号を使用して、前記第1の制御メッセージが順序通りであるかどうかを判定することと、
もし順序通りでないならば、前記第1の制御メッセージを破棄することと、
を備える方法。
【請求項3】
請求項2に記載の方法であって、
前記第1の制御メッセージは、複数のルーティングパラメータを含み、前記複数のルーティングパラメータは、更に、シーケンス番号と、グループリストと、前記グループヘッダノードまでのホップカウントと、前記グループヘッダノードへの次ホップとを含む、方法。
【請求項4】
請求項3に記載の方法であって、
前記第1の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することは、更に、
前記第1の制御メッセージの、前記グループヘッダノードまでの前記ホップカウントを、前記現ノードの、前記グループヘッダノードまでのホップカウントと比較することであって、もし前記2つのホップカウントが等しいならば、前記第1の制御メッセージはピアノードによってブロードキャストされている、ことを含む、方法。
【請求項5】
請求項4に記載の方法であって、更に、
もし前記第1の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも小さいならば、前記第1の制御メッセージを破棄することと、
もし前記第1の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも大きいならば、前記時間を取り消し、前記複数のルーティングパラメータ内における前記制御メッセージの状態を「送信済み」に設定することと、
を備える方法。
【請求項6】
請求項5に記載の方法であって、更に、
前記複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、
少なくとも1つの追加のルーティングパラメータを含む第2の制御メッセージを、前記ローカルピアグループ内のグループノードから受信することと、
前記少なくとも1つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
を備える方法。
【請求項7】
請求項6に記載の方法であって、更に、
前記第2の制御メッセージに対するソースを判定することと、
前記第2の制御メッセージの直接の送信者を判定することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
前記第2の制御メッセージ内の上記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
を備える方法。
【請求項8】
請求項7に記載の方法であって、
前記転送テーブルは、情報のパケットをルーティングするために使用される、方法。
【請求項9】
請求項8に記載の方法であって、
前記第1の制御メッセージの受信後に、ノードは、前記第1の制御メッセージ内の前記ホップカウントを増分させ、前記ノードの識別を、前記第1の制御メッセージ内の、前記グループヘッダノードへの前記次ホップに挿入する、方法。
【請求項10】
請求項9に記載の方法であって、
前記ノードは、前記増分及び前記挿入を実施した後に、前記第1の制御メッセージを転送する、方法。
【請求項11】
請求項9に記載の方法であって、
前記第2の制御メッセージの受信後に、ノードは、前記第2の制御メッセージを前記グループヘッダノードに転送する、方法。
【請求項12】
請求項5に記載の方法であって、更に、
もし前記第1の制御メッセージが路側機(RSU)から受信されるならば、前記RSUの前記ルーティングテーブルを更新することと、
前記第1の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項13】
無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
グループヘッダノードから第1の制御メッセージを受信することと、
前記第1の制御メッセージをブロードキャストすることと、
前記第1の制御メッセージに応じて前記ローカルピアグループ内のグループノードから第2の制御メッセージを受信することと、
前記第2の制御メッセージのシーケンス番号を格納することと、
前記グループヘッダノードから第3の制御メッセージを受信することと、
前記第3の制御メッセージの前記シーケンス番号を前記第2の制御メッセージの前記シーケンス番号と比較することと、
前記第3の制御メッセージの前記シーケンス番号が、前記第2の制御メッセージの前記シーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、前記第3の制御メッセージをブロードキャストすることと、
を備える方法。
【請求項14】
請求項13に記載の方法であって、更に、
前記第3の制御メッセージの前記シーケンス番号が、前記第2の制御メッセージの前記シーケンス番号から前記プリセット定数を差し引いた値よりも小さい場合に、前記第3の制御メッセージを破棄することを備える方法。
【請求項15】
請求項14に記載の方法であって、
前記プリセット定数は、前記第3の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する、方法。
【請求項16】
請求項14に記載の方法であって、更に、
前記第1の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも1つに基づいて、ルーティングテーブルを更新することと、
前記第2の制御メッセージに含まれる前記少なくとも1つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
を備える方法。
【請求項17】
請求項16に記載の方法であって、更に、
前記第2の制御メッセージに対するソースを判定することと、
前記第2の制御メッセージの直接の送信者を判定することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
前記第2の制御メッセージ内の前記少なくとも1つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
を備える方法。
【請求項18】
請求項17に記載の方法であって、
前記転送テーブルは、情報のルーティングパケットのために使用される、方法。
【請求項19】
請求項18に記載の方法であって、
前記第3の制御メッセージの受信後に、ノードは、前記第3の制御メッセージ内のホップカウントを増分させ、前記ノードの識別を、前記第3の制御メッセージ内の、グループヘッダノードへの前記次ホップに挿入する、方法。
【請求項20】
請求項19に記載の方法であって、
前記ノードは、前記増分及び前記挿入を実施した後に、前記第3の制御メッセージを転送する、方法。
【請求項21】
請求項20に記載の方法であって、
前記第2の制御メッセージの受信後に、ノードは、前記第2の制御メッセージを前記グループヘッダに転送する、方法。
【請求項22】
請求項15に記載の方法であって、更に、
前記第3の制御メッセージが路側機(RSU)から受信される場合に、前記RSUの前記ルーティングエントリを更新することと、
前記第3の制御メッセージをブロードキャストすることと、
を備える方法。
【図1】
【図2】
【図3】
【図4】
【図5A】
【図5B】
【図5C】
【図5D】
【図6A】
【図6B】
【図6C】
【図7A】
【図7B】
【図2】
【図3】
【図4】
【図5A】
【図5B】
【図5C】
【図5D】
【図6A】
【図6B】
【図6C】
【図7A】
【図7B】
【公開番号】特開2012−199990(P2012−199990A)
【公開日】平成24年10月18日(2012.10.18)
【国際特許分類】
【出願番号】特願2012−128655(P2012−128655)
【出願日】平成24年6月6日(2012.6.6)
【分割の表示】特願2011−509582(P2011−509582)の分割
【原出願日】平成21年5月11日(2009.5.11)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
【公開日】平成24年10月18日(2012.10.18)
【国際特許分類】
【出願日】平成24年6月6日(2012.6.6)
【分割の表示】特願2011−509582(P2011−509582)の分割
【原出願日】平成21年5月11日(2009.5.11)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
[ Back to top ]