JP2012199990A - 車両ピアグループの効率的編成及び効率的なｖ２ｒ通信のための方法 - Google Patents

Abstract

【課題】ＶＡＮＥＴにおける効率的な制御メッセージ配布のための方法を提供する。
【解決手段】選択されたキーノードによる限られた数の再ブロードキャストによってフラッディングの目的を達成するために、効率的なフラッディングメカニズムが提供される。抑制ベースの効率的なフラッディングメカニズムは、軽度抑制技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観測したときにそのフラッディングメッセージのブロードキャストを断念することによって、フラッディング中継の数を減少させる。また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノードを選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。ＲＮは、「ｋ」回の前制御メッセージサイクルにおいて、例えばメンバシップレポートなどの少なくとも１つの制御メッセージをアップストリームノードに中継するノードである。
【選択図】図７Ａ

Description

本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、マルチホップ車両アドホックネットワーク（ＶＡＮＥＴ）における制御メッセージの効率的配布のための方法に関するものである。

本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network（アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス）」と題された、２００６年１０月２３日出願の共同所有の米国同時係属特許出願第１１／５８５，０４７号（「’０４７出願」）に関連している。

無線通信は、それが無線ホームネットワーク若しくは無線オフィスネットワークであれ、ローカルカフェ、ファストフードチェーン、若しくはホテルにおけるいわゆる「ホットスポット」ネットワークであれ、又はひいては都市規模でのＷｉＦｉ技術の実施であれ、今日の生活のあらゆる局面において普及してきている。無線通信社会を追い求めるこのような要求は、移動車両などの移動デバイスにまで広がっている。このタイプの無線ネットワーク構築は、道路障害物に関する緊急警告、交差点の調整、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含む、多くの車両安全応用の局面において出現する可能性がある。

車両間安全通信（「ＶＳＣ」）は、車両間通信、及びインフラストラクチャを介した車両通信に大別することができる。車両間通信では、車両同士は、固定されたインフラストラクチャからの支援を受けることなく通信しあう。車両同士は、互いに同じ電波範囲内にあるときに、又はその他の車両を通じたマルチホップ中継が可能であるときに、通信しあう。インフラストラクチャを介した車両通信では、車両同士は、路側の無線アクセスポイントなどのインフラストラクチャの支援を受けて通信しあう。このケースでは、車両は、インフラストラクチャのみと通信することもできる。

重要なＶＳＣ性能要件は、衝突回避などの様々なＶＳＣ応用形態を支援するために、待ち時間が短いこと（約１００ミリ秒）及びスループットを維持すること（別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合）を含む。’０４７出願は、１つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してＬＰＧを維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループ（ＬＰＧ）に編成するための方法を記載している。ＬＰＧは、ハートビート（ＨＢ）及びメンバシップレポート（ＭＲ）などの制御メッセージの伝送によって形成される。ＨＢメッセージは、フラッディングメカニズムを使用して実装されている。移動車両は、ユニキャスト及びマルチキャストのルーティングに適応される。

しかしながら、フラッディングは、ユニキャストプロトコル及びマルチキャストプロトコルを含むＬＰＧベースのルーティングプロトコルの主要な制御オーバーヘッドである。各ＨＢサイクルにおいて、ＨＢは、少なくともＬＰＧ内のメンバの数と同じ回数だけ再ブロードキャストされる。交通渋滞などのように、近くにあるノードの数が大きい状況では、ＨＢの重複によって、このオーバーヘッドが大幅に増大される。フラッディングは、全てのノードに対してフラッディングメッセージの再ブロードキャストを要求する。これらの状況では、フラッディングによって、更には大きいＬＰＧ内では制御メッセージの大サ
イズになるために、ネットワーク帯域幅が消費し尽くされる恐れがある。制御メッセージの配布は、ＬＰＧベースのプロトコルの中核的要素であるので、効率的な制御メッセージ配布が必要とされている。

本発明は、ＶＡＮＥＴにおける効率的な制御メッセージ配布のためのシステム及び方法を提供する。選択されたキーノードによる限られた数の再ブロードキャストによってフラッディング（接続された全てのノードにメッセージを配信する）の目的を達成するために、効率的なフラッディングメカニズムが提供される。

抑制ベースの効率的なフラッディングメカニズムは、軽度抑制（ＬＳ：Light Suppression）技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。

また、中継ノードベースの効率的なフラッディングメカニズムは、中継ノード（ＲＮ）を選択し、制御メッセージ配信のための効率的なフラッディングツリーを形成する。ＲＮは、「ｋ」回の前制御メッセージサイクルにおいて、例えばダウンストリームノードのメンバシップレポート（ＭＲ）などの少なくとも１つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、ＬＰＧのためのグループヘッダ（ＧＨ）であってもよい。

一実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを効率的に散布するための方法である。方法は、少なくとも１つのルーティングパラメータを含む第１の制御メッセージをグループヘッダノードから受信することと、第１の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、もし第１の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、第１の制御メッセージを破棄することと、もし第１の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、もし上記時間の間に第１の制御メッセージをブロードキャストしたダウンストリームノードがないならば、上記時間の終了時に第１の制御メッセージをブロードキャストすることと、を含む。方法は、更に、シーケンス番号を使用して、第１の制御メッセージが順序通りであるかどうかを判定することと、もし順序通りでないならば、第１の制御メッセージを破棄することと、を含む。

第１の制御メッセージは、複数のルーティングパラメータを内包している。複数のルーティングパラメータは、シーケンス番号と、グループリストと、グループヘッダノードまでのホップカウントと、グループヘッダノードへの次ホップとを含む。本方法は、更に、第１の制御メッセージの、グループヘッダノードまでのホップカウントを、現ノードの、グループヘッダノードまでのホップカウントと比較することを含み、もし２つのホップカウントが等しいならば、第１の制御メッセージはピアノードによってブロードキャストされている。もし第１の制御メッセージのホップカウントが、現ノードのホップカウントよりも小さいならば、第１の制御メッセージは、破棄される。もし第１の制御メッセージのホップカウントが、現ノードのホップカウントよりも大きいならば、時間は取り消され、制御メッセージの状態は「送信された」に設定される。

本方法は、更に、第１の制御メッセージ内の複数のルーティングパラメータの少なくとも１つに基づいて、ルーティングテーブルを更新することと、少なくとも１つの追加のルーティングパラメータを含む第２の制御メッセージを、ローカルピアグループ内のグルー
プノードから受信することと、少なくとも１つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。この転送テーブルに基づいて、パケットがルーティングされてよい。

本方法は、更に、第２の制御メッセージに対するソースを判定することと、第２の制御メッセージの直接の送信者を判定することと、第２の制御メッセージ内の少なくとも１つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第２の制御メッセージ内の少なくとも１つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。第１の制御メッセージの受信後に、ノードは、第１の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第１の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。ノードは、上記の増分及び挿入を実施した後に、第１の制御メッセージを転送し、第２の制御メッセージの受信後に、第２の制御メッセージをグループヘッダノードに転送する。

本方法は、更に、第１の制御メッセージが路側機（ＲＳＵ：road side unit）から受信されたかどうかを判定することと、もしそうであるならば、ＲＳＵのルーティングテーブルを更新すること及び第１の制御メッセージをブロードキャストすることと、を含む。

別の実施形態では、本発明は、無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、グループヘッダノードから第１の制御メッセージを受信することと、第１の制御メッセージをブロードキャストすることと、第１の制御メッセージに応じてローカルピアグループ内のグループノードから第２の制御メッセージを受信することと、第２の制御メッセージのシーケンス番号を格納することと、グループヘッダノードから第３の制御メッセージを受信することと、第３の制御メッセージのシーケンス番号を第２の制御メッセージのシーケンス番号と比較することと、第３の制御メッセージのシーケンス番号が、第２の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、第３の制御メッセージをブロードキャストすることと、を含む方法である。

本方法は、更に、第３の制御メッセージのシーケンス番号が、第２の制御メッセージのシーケンス番号からプリセット定数を差し引いた値よりも小さい場合に、第３の制御メッセージを破棄することを含む。プリセット定数は、第３の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する。

本方法は、更に、第１の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも１つに基づいて、ルーティングテーブルを更新することと、第２の制御メッセージに含まれる少なくとも１つの追加のルーティングパラメータに基づいて、ルーティングテーブルを更新することと、上記の更新するステップの両方が完了したら、ルーティングテーブルをもとに転送テーブルを生成することと、を含む。

本方法は、更に、第２の制御メッセージに対するソースを判定することと、第２の制御メッセージの直接の送信者を判定することと、第２の制御メッセージ内の少なくとも１つの追加のルーティングパラメータに基づいて、直接の送信者を通じてソースに対する次ホップを変更することと、第２の制御メッセージ内の少なくとも１つの追加のルーティングパラメータに基づいて、直接の送信者に対する次ホップを変更することと、を含む。転送テーブルは、情報のパケットをルーティングするために使用される。第３の制御メッセージの受信後に、ノードは、第３の制御メッセージ内のホップカウントを増分させ、ノードの識別を、第３の制御メッセージ内の、グループヘッダノードへの次ホップに挿入する。
ノードは、上記の増分及び挿入を実施した後に、第３の制御メッセージを転送する。第２の制御メッセージの受信後に、ノードは、第２の制御メッセージをグループヘッダに転送する。

特許請求の範囲の方法は、更に、第３の制御メッセージが路側機（ＲＳＵ）から受信される場合に、ＲＳＵのルーティングエントリを更新すること及び第３の制御メッセージをブロードキャストすることを含む。

発明にしたがった、アドホックネットワークの一例を示している。 本発明の典型的実施形態にしたがった、路側機（ＲＳＵ）の基本的要素のブロック図を示している。 本発明の典型的実施形態にしたがった、ハートビート制御メッセージのフォーマットの一例を示している。 本発明の典型的実施形態にしたがった、メンバレポート制御メッセージのフォーマットの一例を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための軽度抑制方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。 本発明の典型的実施形態にしたがった、制御メッセージを処理するための中継ノード方法を示している。 本発明の典型的実施形態にしたがった、ＲＳＵからのハードビートメッセージを処理するための方法を示している。 本発明の典型的実施形態にしたがった、ＲＳＵからのハードビートメッセージを処理するための方法を示している。

本発明にしたがうと、アドホックネットワークは、２つのタイプのノードに、すなわち路側機（Road Side Unit：以下「ＲＳＵ」）と移動車両とに分けられる。ＲＳＵが固定ノードである一方で、車両はグループで移動することができる。

図１は、本発明にしたがった、アドホックネットワークの一例を示している。ＲＳＵ１００は、道路の側辺に沿って位置している。ネットワークにおいて使用されるＲＳＵ１００の数は、ＲＳＵ１００の電波アンテナの範囲、所望の通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの数々の要因に依存する。図１は、２つのＲＳＵ１００を示している。丸で囲われたエリアは、各ＲＳＵ１００の電波範囲を表わしている。各ＲＳＵ１００は、単独又はグループのいずれかで走行している移動車両１１０と通信するために使用することができる。

移動車両１１０は、管理可能なグループに編成することができる。これらのグループは、ノード間のデータの伝送を調整するために使用される。グループは、隣接するノードの
相対的位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ１１５内で及び複数のＬＰＧ間で電波信号をルーティングするための基礎である。

図１は、３つのＬＰＧ１１５を示している。各ＬＰＧ１１５は、少なくとも１つの移動車両１１０で構成される。図１は、ＬＰＧ１ １１５₁が３つの移動車両を含むこと、Ｌ
ＰＧ２ １１５₂が２つの移動車両を含むこと、及びＬＰＧ３ １１５₃が３つの移動車両を含むことを示している。ＲＳＵ１００は、ＬＰＧ１１５内に存在して特別なＬＰＧノードとして振る舞うことができる、又はＬＰＧ１１５の外側において別個のノードとして存在することができる。ＲＳＵ１００がＬＰＧ１１５内のノードではなく、ＬＰＧ１１５と連携して使用されるときは、ＲＳＵ１００は、ＬＰＧ間通信用の境界ノードとして振る舞うことができる。通常、１つのＲＳＵ１００の電波有効範囲は、１つのＬＰＧのサイズよりも大きい、すなわち、１つのＲＳＵ１００の電波範囲内には、２つ以上のＬＰＧ１１５がある。このような場合が図１に示されている。したがって、１つのＬＰＧ１１５からのメッセージは、ＲＳＵ１００を使用して別のＬＰＧにブロードキャストすることができる。この場合、ＲＳＵ１００は、そのメモリに格納されたＬＰＧに関する情報を含む。

移動車両１１０は、車両−車両（Ｖ−Ｖ）チャネルを通じて互いに通信する。移動車両は、車両−路側（Ｖ−Ｒ）チャネルを通じて路側機と通信する。また、ＲＳＵ１００は、Ｒ−Ｒチャネル又はＲ−Ｂ（バックボーン）チャネルを通じて互いに通信する。Ｒ−Ｒ通信は、専用チャネルつまり有線バックボーンを使用するので、この通信は、Ｖ−Ｖ通信又はＶ−Ｒ通信に干渉しない。Ｖ−ＶチャネルとＶ−Ｒチャネルとの間のチャネル共有についての代案が幾つかある。好ましい実施形態では、Ｖ−Ｒ通信用の専用チャネルがある。残りのチャネルは、Ｖ−Ｖ通信及び／又はＶ−Ｒ通信用に共有される。Ｖ−Ｒチャネルは、その他のチャネルと同じＲＦ周波数帯域にあってよい。或いは、Ｖ−Ｒチャネルは、異なるＲＦ周波数帯域にあって、異なる通信範囲及び異なるデータ速度を可能にしてよい。

別の実施形態では、全てのチャネルが、Ｖ−Ｖ及びＶ−Ｒの両方のために動的に共有される。この手法は、性能の最適化を可能にする。しかしながら、干渉しないチャネルの探索及び選択において複雑性がもたらされる。

別の実施形態にしたがうと、Ｖ−Ｒ用にのみ専用チャネルが割り当てられ、その他のチャネルは、Ｖ−Ｖ用だけに共有される。或いは、Ｖ−Ｒ用に専用チャネルが、そしてＶ−Ｖ用に第２の専用チャネルが使用される。残りのその他のチャネルは、Ｖ−Ｖ通信及びＶ−Ｒ通信用に共有される。発明の説明を続ける目的で、好ましい実施形態のチャネル割り当てが使用される。ＲＳＵ１００は、ルータ、アプリケーションサーバ、又はそれらの組み合わせなどの、多くの機能を有することができる。

ＬＰＧ１１５には、固定ＬＰＧ、動的ＬＰＧ、及びハイブリッドＬＰＧなどの、幾つかのタイプのＬＰＧ１１５がある。固定ＬＰＧは、特定の位置又はエリアによって画定される。すなわち、もしノードが、例えばエリアＡを画定するエリアにあるならば、そのノードは、ＬＰＧ Ａに所属する。もしノードが、例えばエリアＢなどの異なるエリアにあるならば、そのノードは、ＬＰＧ Ｂに所属し、以下同様である。固定ＬＰＧの具体的なサイズは、例えば電波アンテナの範囲、通信範囲、移動デバイスの数、土地の形状、環境条件、交通パターン、及び人口密度などの様々な要因に依存する、設計上の一選択肢である。固定ＬＰＧの位置及びサイズは固定である。しかしながら、場所が異なると交通パターン及び人口（移動車両１１０）密度が異なるゆえに、各固定ＬＰＧは、それぞれ異なるサイズであってよい。もしＲＳＵ１００が所定のＬＰＧ１１５内にあるならば、そのＲＳＵ１００の電波範囲によって、固定ＬＰＧのサイズが画定される。

ＲＳＵ１００を使用することによって、移動車両１１０は、ＲＳＵ１００からのハードビート制御メッセージ又はＡＰ３３０からのビーコンのいずれかをヒアリングすることによって固定ＬＰＧの位置を検出することができる。移動車両１１０は、自身の位置変化とともに、固定ＬＰＧを変更していく。或いは、移動デバイスは、ＬＰＧ１１５及びそれらの位置のデータベースを含む。別の実施形態において、もしとあるエリア内に複数のＲＳＵ１００がある場合は、少なくとも１つのＲＳＵ１００が、近隣にあるその他のＲＳＵ１００の相対的なポジション又は位置に関する情報を提供することによって、移動車両１００がＬＰＧ１１５を迅速に突き止められるようにして、複数のＬＰＧ１１５間のハンドオフを容易にすることができる。

固定ＬＰＧは、たとえ一部のＬＰＧ１１５が空である又は多くの移動車両１１０を有さない場合でも、バックボーンアクセス又はＬＰＧ間通信を提供するように無線インフラストラクチャとの統合をサポートするという、重要な利点を有している。各固定ＬＰＧは、通信を容易にするように、一意の識別子を割り当てられている。どの固定ＬＰＧエリアも明確に画定されているので、ＬＰＧ１１５の形成及び命名は、動的ＬＰＧよりも容易である。また、固定ＬＰＧを使用する場合、ＬＰＧ１１５の併合及び分割に関する規則は問題ではない。

第２のタイプのＬＰＧ１１５は、動的ＬＰＧである。固定ＬＰＧとは反対に、動的ＬＰＧは、隣接するノードの電波有効範囲に基づいて形成され、それにより、ノードは、他のノードの厳密な位置を考慮することなく通信を調整することができる。

動的ＬＰＧは、電波有効範囲に基づいて形成されるので、ＬＰＧ１１５内の移動車両１１０は、シングルホップ伝送又はマルチホップ伝送を通じて互いに及びＲＳＵ１００と常に通信することができる。ＬＰＧ１１５内の１つのノードは、低遅延で且つ効率的な通信を実施することができるように、各ＬＰＧ１１５内のノードの数を又はこのノードから動的ＬＰＧの端までの電波ホップの数を適度に少なく維持するために、動的ＬＰＧのサイズを制御することができる。このノードは、後ほど詳述されるように、グループヘッダ（ＧＨ）と称される。また、固定ＬＰＧとは対照的に、動的ＬＰＧは、各ＬＰＧ１１５内で常に通信が可能であることを確実にする。動的ＬＰＧでは、固定ＬＰＧと異なり、ＲＳＵ１００の電波範囲の外にＬＰＧ１１５を形成することができる。

一実施形態では、アドホックピアツーピアネットワークを、１つ若しくは２つ以上の固定ＬＰＧ又は１つ若しくは２つ以上の動的ＬＰＧで作成することができる。別の実施形態では、アドホックピアツーピアネットワークを、ハイブリッドＬＰＧネットワークとして、固定ＬＰＧ及び動的ＬＰＧの両方で作成することができる。ハイブリッドＬＰＧネットワークは、固定ＬＰＧ及び動的ＬＰＧの両者の利点を融合しつつ、それぞれを個別に利用した場合に生じる問題を排除する。

ハイブリッド手法は、道路形状をうまく活用する。特に、インフラストラクチャが利用可能でないときに、動的ＬＰＧを使用してネットワークを形成する。一部のエリアにおいてインフラストラクチャが利用可能になると、固定ＬＰＧを使用して、動的ＬＰＧ及びインフラストラクチャとのネットワークを形成することができる。例えば、道路インフラストラクチャなどのインフラストラクチャは、道路−車両通信又は道路支援通信を可能にする。

一実施形態では、ＲＳＵ１００は、ＬＰＧ１１５内のノードであってよく、移動車両１１０と同様のネットワーク機能を実行することができる。ＲＳＵ１００は、グループヘッダ（ＧＨ）又はグループノード（ＧＮ）のいずれかとしてＬＰＧ１１５に参加することができる。ＧＨは、いかなるノード順番付け又はいかなるインフラストラクチャもなしにＬ
ＰＧ１１５を維持及び制御するように指定された、ＬＰＧ１１５内の移動デバイス又はノードである。通常、ＬＰＧ１１５内にＧＨは１つのみである。ＬＰＧ１１５内のその他の全てのノードは、一般的なノードすなわちグループノード（「ＧＮ」）である。ＧＮは、ＧＨを通じてＬＰＧ１１５に参加する。

各ＲＳＵ１００は、上述のようにルータ及びアプリケーションサーバに加えて、ＧＨ又はＧＮとして動作することができる。このように、各ＲＳＵ１００は、ノードをそれぞれＧＨ又はＧＮとして機能させる又は動作させることを可能にする要素又は手段及びネットワーキングプロトコルを含む。したがって、たとえＲＳＵ１００がＧＨ又はＧＮのいずれかとして動作する場合でも、ＧＨ及びＧＮの両方のための全ての構造的な要素又は手段が存在し、ただし、動作のモードに基づいて特定の要素のみが機能している。ＲＳＵ１００は、したがって、ＧＨ又はＧＮの機能性を提供するためのハードウェア及びソフトウェアの両方を含んでいる。

図２は、ＲＳＵ１００の基本的要素のブロック図を示している。ＲＳＵは、メモリセクション２１００と、クロック２１０５と、タイマ２１１０と、送受信セクション２１２０と、制御手段２１２５と、電源２１３０とを含む。メモリセクション２１００は、ＤＲＡＭ、ＳＲＡＭ、又はＦｌａｓｈを含む、任意のタイプのメモリであってよい。好ましい実施形態では、短期メモリは、キャッシュである。メモリセクション２１００は、グループＩＤ（ＧＩＤ）、グループヘッダＩＤ、グループリスト、既定の最大ＬＰＧサイズ、ＬＰＧ内のノードの数、及びその他のタイプの制御パラメータなどの、ＬＰＧに関する情報を格納する。

クロック２１０５は、ＲＳＵ１００のためのタイミングを維持するために使用される。特に、クロック２１０５は、内部クロックとして機能し、タイマ２１１０を設定するための基準として使用される。タイマ２１１０は、様々なメッセージをいつブロードキャストするべきかを判定するために使用される、すなわち、ＧＨの場合はハードビート間隔（Ｔ）を、又はＧＨの場合は応答メッセージを判定する。制御手段２１２５又はマイクロプロセッサは、メッセージの生成、ルーティング、及びタイマを含む、ＲＳＵ１００の全てのプロセスを制御する。送受信セクション２１２０は、制御手段２１２５と協働して、メモリセクション２１００に格納されているデータからメッセージを作成又は生成する役割を担う。

ＲＳＵ１００は、その電波範囲内にある全ての移動車両１１０及びその他のＲＳＵに対し、ビーコン又はハードビート制御メッセージを定期的に伝送する。この期間は、固定間隔である。ハードビート間隔（Ｔ）の値は、設計上又は動作上の必要性に基づいて選択可能である。

ＬＰＧ１１５がＲＳＵ１００の近くを移動するときは、ヘッダ解決プロトコルに基づいてＧＨが選出される。ＬＰＧ１１５のＧＨである移動車両は、Ｖ−Ｖチャネル及びＶ−Ｒチャネルの両方にハードビート制御メッセージを送出する。やはりＧＨとして振る舞うＲＳＵ１００は、Ｖ−Ｒチャネルのみにハートビートを送出する。２つ以上のＧＨがハートビート制御メッセージを送信すると、ヘッダ解決が発生する。これは、同じＬＰＧ１１５内に複数のＧＨがあるのを回避するためである。なぜならば、同じＬＰＧ１１５内に複数のＧＨがあると、結果として、そのＬＰＧ１１５内において冗長な（混乱を招く可能性すらある）制御信号が伝送又はブロードキャストされ、帯域幅及び容量が無駄遣いされるからである。ヘッダ解決は、少なくとも２つのＧＨから１つのＧＨを選択する働きをする。

ユニキャストルーティングプロトコルは、各ノード内におけるルーティングテーブルの作成に基づく。ルーティングテーブルは、少なくとも、メッセージについての宛先及び次
ホップを含む。ＬＰＧ１１５内の全ての移動車両１１０は、ルーティング機能を実施し、その他の車両がシングルホップ又はマルチホップのいずれかで通信するのを助ける。ＬＰＧ内ルーティングテーブルは、ＬＰＧ形成メッセージを使用してブロードキャストモードにおいて制御メッセージを交換することによって構成される。ユニキャストルーティングでは、追加の制御メッセージは不要である。ＬＰＧ形成に使用されるのと同じ制御メッセージが、ルーティングプロトコルのためのルーティングテーブルの作成、維持、及び更新のために使用される。ルーティングテーブルは、ＬＰＧ内ルーティングに使用される。不要なノードに外部制御メッセージが伝搬されることがないように、あらゆる制御メッセージにＬＰＧ識別子が埋め込まれる。全ての外部制御メッセージは、終了される又は中継されない。

制御メッセージメッセージは、ＧＨからのハートビート（ＨＢ）及びＧＮからのメンバシップレポート（ＭＲ）である。ハードビート制御メッセージは、ＬＰＧの領域を画定する。ハートビートメッセージと、それに続くメンバシップレポートとが、１つの制御メッセージサイクルを構成する。

’０４７出願で説明されている別の実施形態では、ＬＰＧネットワークは、マルチキャストメッセージ機能をサポートすることができる。ユニキャストでは、送信ノード（例えば事故の目撃者）は、１つの特定の受信者にメッセージを送信する又は向かわせるので、同じ情報を複数の受信者に送信するためには複数のメッセージが必要である。これは、大量のネットワーク帯域幅の消費及びメッセージの遅延を引き起こす結果となる。マルチキャスト伝送では、送信者は、メッセージの重複コピーを生成せず、１つのメッセージを全ての受け手に対して送信する。マルチキャストによって、ネットワーク帯域幅は大幅に節約される。

＜ＨＢメッセージ＞
図３は、ハートビート制御メッセージ３００のフォーマットの一例を示している。ハートビート制御メッセージ３００は、ＬＰＧ識別子すなわちＧＩＤ３０５及びグループヘッダ３１０の両方を含む一意の識別子を含む。

ＧＩＤ３０５及びグループヘッダＩＤ３１０は、各ＬＰＧ１１５を識別する。ＧＩＤ３０５には、幾つかの可能なフォーマットがある。一実施形態では、ＧＩＤ３０５は、ＬＰＧ１１５のためにランダムに選択された識別番号であってよい。或いは、ＧＩＤ３０５は、ＬＰＧの形成の順番に基づいて割り当てられた識別番号であってよい。例えば、第１のＬＰＧは、ＬＰＧ１というＧＩＤ３０５を有することができ、第２のＬＰＧのＧＩＤ３０５は、ＬＰＧ２であり、以下同様である。しかしながら、ＧＨの変化とともに、ＧＩＤ３０５も変化し、その結果、ノードは、そのＬＰＧが変化したのか又は単にＬＰＧ１１５のＩＤが変化したのかを区別することができなくなる。他方で、ＧＨが去るときに、ＧＩＤ３０５を元のＩＤに固定してもよい。しかしながら、これは、１つのＬＰＧが分裂するときに、ＧＩＤ３０５の重複を生じる可能性がある。その結果、２つ又は３つのグループが、同じＧＩＤ３０５を有することになる。一実施形態では、ＧＩＤ３０５は、ＬＰＧ１１５を一意に識別するために、ＬＰＧ ＩＤ番号及びＧＨ ＩＤ番号の両方に基づいて符号化される。

ＧＨは、グループヘッダＩＤ３１０を与えられる。最初、ＧＩＤ３０５は、グループヘッダＩＤ３１０に結び付いている。したがって、グループヘッダＩＤ３１０は、最初は、ＧＩＤ３０５の一部分として使用されるが、ＧＨの変化とともに、新しいグループヘッダＩＤ３１０を含むように変化する。各ＧＨは、グループヘッダＩＤ３１０を割り当てられる。グループヘッダＩＤ３１０は、（パブリック又はプライベート）ＩＰアドレスに基づいて割り当てられる。図３に示されるように、グループヘッダＩＤ３１０は、ＩＰｖ６
ＩＰアドレスである。別の実施形態では、グループヘッダＩＤ３１０は、ＩＰｖ４アドレスであってよい。

ハードビート制御メッセージは、また、シーケンス番号（sequence number：Ｓｅｑ．
Ｎｏ．）３１５も含む。Ｓｅｑ．Ｎｏ．３１５は、ハートビート制御メッセージの順番を追跡して、受信されたハートビート制御メッセージ３００が新しいすなわち新着であるかどうかを判定するために使用される。ＧＮは、受信されたハートビート制御メッセージのＳｅｑ．Ｎｏ．３１５を記憶している。新たなすなわち新着のハートビート制御メッセージは、次のＳｅｑ．Ｎｏ．３１５を伴う最初のハートビート制御メッセージによって示される。Ｓｅｑ．Ｎｏ．３１５は、また、どのハートビート制御メッセージが（次ホップノードに）中継されるべきかを判定するためにも使用される、すなわち、先着のみ中継（ＦＣＲＯ：first come relay only）戦略を使用することができる。新たな（すなわち新着
の）ハートビート制御メッセージのみが中継されるべきである。ノードは、先のシーケンス番号を記憶しており、それを着信ハートビート制御メッセージのシーケンス番号と比較して、そのハートビート制御メッセージが新しいすなわち新着であるかどうかを判定する。もし適切なＧＩＤ３０５を伴うハートビート制御メッセージのＳｅｑ．Ｎｏ．３１５が、現時点で格納されているシーケンス番号よりも大きいならば、それは、新たなすなわち新着のハートビート制御メッセージ３００であり、したがって、ＦＣＲＯが使用される場合は中継される。ＧＮに先に格納されていたシーケンス番号は、破棄され、新たなシーケンス番号に置き換えられる。

ハートビート制御メッセージ３００は、更に、ハートビート期間（ＨＢ期間）３２０に関する情報も含む。この期間は、固定間隔（Ｔ）である。間隔（Ｔ）の値は、設計上又は動作上の必要性に基づいて選択可能である。ＨＢ期間３２０は、次のハートビート制御メッセージがいつブロードキャストされるかを、全てのＧＮに対して示す。ＧＮは、ＨＢ期間３２０内にハートビート制御メッセージを受信しない場合は、ハートビート制御メッセージが連続的に送信されるように、新たなハートビート制御メッセージを伝送する。もし元のＧＨが依然としてＬＰＧ１１５内にあるならば、ヘッダ解決が発生する。制御オーバーヘッドを低減させるために、ＧＨは、ＨＢ期間３２０を調整することができる。調整は、ＬＰＧのサイズ、ＬＰＧ内のノードの位置、負荷、速度、及び数に基づくことができる。

ハートビート制御メッセージ３００は、例えば、完全なグループリストを伴う、漸増性のグループリストを伴う、又はグループリストを伴わないなどの、ハートビート制御メッセージのタイプも含む。一実施形態では、ハートビート制御メッセージは、全てのメッセージ内に、完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビート制御メッセージには、大量の帯域幅が必要である。ハートビート間隔（Ｔ）は、制御オーバーヘッドを低減させるように調整することができる。別の実施形態では、（ｎ−１）個おきの各ハートビート制御メッセージが完全グループリストを含む。例えば、２つおきの各ハートビート制御メッセージが完全グループリストを含む。これは、平均のハートビート制御メッセージに対する帯域幅を低減させる。しかしながら、ＬＰＧ１１５内のノードの大半は、速いペースで移動しているので、受信されるグループリストは、古くなっている可能性がある。言い換えると、ノードによって新たなグループリストが受信された時点で、グループの幾つかのメンバは、別のＬＰＧ１１５内にある可能性がある。別の実施形態では、進行性のグループリスト又は漸増性のグループリストを配布することができる。グループリストは、そのリスト内のメンバシップに変更があるときにのみ配布される。進行性のグループリスト又は漸増性のグループリストもまた、メンバシップリストが古くなる可能性がある。

或いは、ハートビート制御パッケージのタイプは、ハイブリッドグループリスト更新であってよい。メンバシップに変更があるときは、ハートビート制御メッセージに進行性のグループリストを含めることができ、更に、（ｎ−１）個おきの各ハートビート制御メッセージには、完全なグループリストを含めることができる。ＴｏＨＢ（type of heartbeat）３２５は、ハートビート制御メッセージのタイプを示す。ハートビート制御メッセー
ジのタイプは、ＬＰＧ１１５のトポロジ変化速度及びハートビート制御メッセージのブロードキャストの頻度によって影響される。ＬＰＧ１１５のトポロジ変化速度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性が高まる。ハートビート制御メッセージのブロードキャストの頻度が増すにつれて、全てのハートビート制御メッセージに完全なグループリストを含める必要性は減少する。

ハートビート制御メッセージは、ＧＨからのホップカウント（ＨＣ）３３０を含む。最初、ＨＣ３３０は、例えば１などの既定の値に設定される。ハートビート制御メッセージがノードによって中継されるたびに、中継ノードは、ＨＣ３３０の値を１だけ増加させる、すなわち、ＨＣ＝ＨＣ＋１とする。ＨＣ値は、ＬＰＧサイズを制限するため、ハートビート制御メッセージ内の情報の古さを示すため、及び制御メッセージのルーティングを制御してオーバーヘッドを低減させるために使用することができる。ＬＰＧごとに、例えば１０などの、ルーティングの最大ホップカウントがある。ＨＣが最大ホップカウントまで増分されると、例えばハートビート制御メッセージなどの制御メッセージは、中継されなくなる。

ホップカウントは、中継戦略にも使用することができる。一実施形態では、ハートビート制御メッセージは、最低のホップカウントを有する場合に中継するようにしてもよい。この方法は、ＧＨからの正しいホップカウントを保証するが、ただし、待ち遅延がある。ノードは、ハートビート制御メッセージについて最低のホップカウントを判定する必要があるので、同ハートビート制御メッセージを中継する前に、全てのアップストリームノードからハートビート制御メッセージが受信されるまで待機する必要がある。したがって、最低のホップカウント及び上記の先着のみ中継戦略の両方を使用した、複合的な中継戦略を実装することができる。ハートビート制御メッセージは、より低いホップカウントのハートビート制御メッセージがノードによって受信されるまでは、先着のみ中継戦略を使用して中継される。ノードＡは、ハートビート制御メッセージを転送するときに、ハートビート制御メッセージを誰が中継したのかを次ホップノードが知ることができるように、メッセージ内にＩＤ情報を含ませる。メッセージを転送するノード（ノードＡ）は、すると、ノードＡから初めてハートビート制御メッセージを受信した次ホップノードにとって、（ＧＨに向けてＭＲを送信するための）ＭＲ中継ノードにもなる。

最大ホップカウント、ＨＣ３３０、及びＳｅｑ．Ｎｏ．３１５を利用することによって、ＬＰＧ１１５内における制御メッセージのフラッディングの無限の重複が阻止される。本発明の一実施形態にしたがうと、ノードは、フラッディングソースからのホップカウント（ＨＣ）が自身のものよりも小さいようなフラッディング中継を横聞き（overhear）すると、そのフラッディングメッセージの中継を中止する。この方法は、図５において更に説明される。ノードは、新たなハートビート制御メッセージ３００を受信すると、そのハートビートを中継する前に、設定時間（ＨＢ送信待機タイマによって定められる）の間、待機する。もしこの時間の間に、ダウンストリームノード又はピアノードがそのハートビートを再ブロードキャストする場合は、その再ブロードキャストされたハードビートのＨＣが、現（格納されている）ＨＣ３３０と比較される。もし受信されたＨＣが現ＨＣ３３０よりも小さいならば、ハートビートが不必要にブロードキャストされないように、メッセージは破棄される。もし２つのＨＣが同じであるならば、再ブロードキャストしているノードはピアノードであり、現ノードは、自身がキーノードにならない可能性を増やすために、ＨＢ送信待機タイマを増加させる又はリセットする。もし受信されたＨＣが現ＨＣ
よりも大きいならば、現ＨＢ送信待機タイマは取り消され、ハートビートは送信される。より詳しくは、図５を参照せよ。

別の実施形態では、効率的な制御メッセージ中継ツリーを構築するために、中継ノード（ＲＮ）が選択される。この方法は、メッセージを中継するか否かを判定するために、ハートビート制御メッセージ３００のＳｅｑ．Ｎｏ．３１５を使用する。中継ノードは、少なくとも１つのメンバレポート（ＭＲ）をアップストリームノードに又はＧＨに中継するノードである。この方法は、図６において更に説明される。通常、ハートビート制御メッセージ３００は、ノードからのメンバシップレポート（ＭＲ）をトリガする。ＭＲの内容は、次項及び図４において説明される。ノードは、ＭＲを中継するときはいつも、ＭＲの最新のシーケンス番号（ＨＢのＳｅｑ．Ｎｏ．３１５に対応する）を格納し、ＭＲを複製し、次ホップを置き換え、ＭＲをブロードキャストする。後続のＨＢ３００が受信され、そのＳｅｑ．Ｎｏ．３１５が、格納されているＭＲのＳｅｑ．Ｎｏ．と比較される。ＭＲの配信は、（’０４７出願に記載されているように）中継ノードを自動的に選択するので、シーケンス番号の比較は、選択された中継ノードのみが後続のＨＢ制御メッセージを展開することを確実にし、そうして、ＨＢフラッディング中における不要な制御メッセージの量を低減させる。

上記のように、ハートビート制御メッセージは、グループリスト３３５も含むことができる。グループリスト３３５は、ＬＰＧ１１５内のメンバの数、各数のＩＰアドレス、ＧＨからのホップカウント、及び分類などの、ＬＰＧ１１５のメンバに関する情報を含むことができる。

分類は、例えばアップリンク、ダウンリンク、及びピアなどのような、ＧＨノードからの相対的方向に言及したコードであってもよい。ピア分類は、ノードがＧＨから同じ無線有効範囲内にあることを示している、すなわち、全てのピアノードは、ＧＨからのホップカウントが同じである。アップストリームノードは、ハートビート制御メッセージによって判定される。ダウンストリームノードは、メンバシップレポート（ＭＲ）に基づいて判定される。アップストリーム伝送は、ＧＨに向かう通信を表しており、ダウンストリーム伝送は、ＧＨから離れる通信を表している。この分類は、相対的表現である。各ＧＮは、自身に隣接するノードを３つの異なるクラスに分類することができる。もし別のＧＮのメンバシップレポートが、自身のＨＣよりも１だけ小さいホップカウント（ＨＣ）を有するならば、ＧＮ（自身）はアップストリームノードである。もし別のＧＮのＨＣが、自身のＨＣと同じであるならば、ＧＮ（自身）はピアである。もし別のＧＮのＨＣが、自身のＨＣよりも１だけ大きいならば、ＧＮ（自身）はダウンストリームノードである。

図４は、メンバシップレポート（ＭＲ）４００を示している。ＭＲ４００は、ＧＮによってブロードキャストされ、ＧＨによって受信される制御メッセージである。ＭＲは、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードに対する次ホップなどの、収集可能なルーティング情報を含んでいる。ＭＲは、ハートビート制御メッセージ３００と同じ情報の幾つかを、すなわちＧＩＤ３０５及びグループヘッダＩＤ３１０を含んでいる。ＭＲ４００は、また、ＭＲ ＳＥＱ．ＮＯ．４０５も含む。ＭＲ Ｓｅｑ．Ｎｏ．は、ハートビート制御メッセージ３００のＳｅｑ．Ｎｏ．３１５と同様であり、ＭＲの順番を維持するために使用される。ＭＲ ＳＥＱ．ＮＯ．４０５は、１つの特定のノードに対するＭＲの順番である。通常、ＭＲ ＳＥＱ．ＮＯ．４０５は、ＭＲをトリガしたハートビート制御メッセージ３００のＳｅｑ．Ｎｏ．３１５と同じ値を有する。

したがって、図６において更に説明される本発明の一実施形態では、ＭＲ４００のＳｅｑ．Ｎｏ．４０５は、現ノードのメモリに格納され、後続のハートビート制御メッセージ
のそれと比較される。もし到着したメッセージのＳｅｑ．Ｎｏ．が、現時点で格納されているＳｅｑ．Ｎｏ．４０５からプリセット数ｋを差し引いたものよりも大きいならば、そのノードは、中継ノードである。定数ｋは、冗長性を実装してＬＰＧの崩壊を阻止するために、ｋサイクルの緩和を導入する。

発信元ノードの、すなわちＭＲを生成したノードの、ノードＩＤ４１０も、ＭＲ４００に含まれる。ＭＲは、次ホップ中継ＩＤ４１５も含む。次ホップ中継ＩＤ４１５は、ＧＨに向かうＭＲ４００に対する中継命令である。次ホップ情報は、受信されたハートビート制御メッセージ３００をもとに直接決定される。ノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、いかなるメッセージ処理よりも前に、ＩＰ層及びＭＡＣ層をもとにして前中継ノードの識別を再取得する。以前の中継ノードの識別は、メモリに格納されており、ＭＲに対する次ホップ中継ＩＤ４１５として使用される。ハートビート制御メッセージを転送するときに、ノードは、そのＩＤをメッセージ内に含ませる。受信側の次ホップノードは、新たなすなわち新着のハートビート制御メッセージを受信すると、このＩＤを、ＧＨに到達するための次ホップ中継ＩＤとして格納する。新たなすなわち新着のハートビート制御メッセージは、最低のＨＣを伴う、より新しいシーケンス番号を有するメッセージである。

ＭＲ４００は、また、「ＭＲのタイプの指標」４２０も含む。ＭＲには、２つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバＭＲは、発信元ノードからのＭＲのみを含む。統合複数メンバレポートは、２つ以上のノードのＭＲを含む。統合レポートは、オーバーヘッド、及び制御メッセージに必要な帯域幅を低減させるために使用することができる。複数のＭＲを含む１つのＭＲが送信される。

また、ＭＲは、ＧＨからのホップカウント（ＨＣ_GH）４２５を含むことができる。（ＨＣ_GH）４２５は、ＧＨからＭＲの発信元ノードまでのＨＣ値である。別の実施形態では、ＭＲは、累積メンバシップリスト４３０及びその他の追加の情報４３５を含むことができる。累積メンバシップリスト４３０は、ＬＰＧのメンバのＩＰアドレス、メンバの数、及び対応するホップカウントを含む。

ＭＲ４００は、逆経路方法又は逆フラッディング方法を使用してＧＨに配信又は中継することができる。逆経路方法は、ハートビート制御メッセージ３００を中継するために使用されたものと同じ経路を使用して、ＭＲをＧＨに向けて中継する。ＭＲが中継されるときに、中継ノードは、次ホップ中継４１５を、ＧＨに向かう次ホップに置き換える。対応するＩＤを有するノードのみが、ＭＲメッセージを中継する。この方法は、伝送における対称性を想定している。もし非対称リンクが存在する場合は、逆フラッディング方法が使用される、すなわち、発信元ノードとＧＨとの間の全てのノードがＭＲを中継する。これは、後続のハートビート制御メッセージ配信のための中継ノード（ＲＮ）を選択するために使用可能な選択手続きである。

各ノードは、ＬＰＧベースのルーティングのための転送テーブルとして使用することができるルーティングテーブルを作成するために、ハートビート制御メッセージ３００及びＭＲ４００の両方を使用する。好ましい実施形態では、各ハートビート制御メッセージは、完全なグループリストを含み、ＬＰＧ１１５内の全てのＧＮが、それに対してＭＲで応答する。ハートビート制御メッセージは、先着のみ中継方法を使用して中継され、ＭＲは、逆経路方法を使用して、単一ＭＲとしてＧＨに向けて中継される。

＜軽度抑制ベースの効率的なフラッディング＞
抑制ベースの効率的なフラッディングメカニズムは、軽度抑制（ＬＳ：Light Suppress
ion）技術を用い、ノードが同じフラッディングメッセージのダウンストリーム中継を観
測したときにそのフラッディングメッセージのブロードキャストを中止することによって、フラッディング中継の数を減少させる。図５Ａは、この方法を示している。最初、ステップ５００において、各ノードはアイドル状態にある。ステップ５０１において、メッセージが到着すると、ノードは、ステップ５０２において、メッセージがハートビート制御メッセージ３００であるか又はＭＲ４００であるかを判定する。制御メッセージのタイプに応じて、ノードは、特別なメッセージ処理を実施する。もし制御メッセージがハートビート制御メッセージ３００であるならば、ノードは、ステップ５０３から始まるメッセージ処理を行う。ノードは、ステップ５０３において、メッセージがネイティブであるかどうかを判定する。メッセージは、同じＬＰＧ１１５に対するメッセージである場合に、すなわち、同じＧＩＤ３０５を有する場合に、ネイティブである。ノードは、ＧＩＤ３０５を、メモリに格納されているグループ識別と比較する。もしＧＩＤ３０５が、メモリに格納されている識別と一致しないならば、ノードは、ステップ５０４において、外部ＨＢ処理を開始させる。通常、外部ＨＢ処理は、ノードがメッセージを破棄する結果となる。もしＧＩＤが、メモリに格納されている識別と一致するならば、ノードは、ハートビート制御メッセージ３００が順序通りであるかどうかを判定する。ノードは、Ｓｅｑ．Ｎｏ．３１５を、メモリ内のシーケンス番号と比較する。もしＳｅｑ．Ｎｏ．３１５が、メモリに格納されている値よりも小さいならば、ノードは、ステップ５０５において、そのメッセージを無視する。もしＳｅｑ．Ｎｏ．３１５が、メモリに格納されている値よりも大きいならば、ハートビート制御メッセージ３００は、順序通りであり、ノードは、次いで、ステップ５０６において、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビート制御メッセージが新しいかどうかを判定する。

もしノードが、メッセージを新しくないと判定するならば、ハートビート制御メッセージ３００は、図５Ｂに明らかにされた軽度抑制プロセスステップ５０７を経る。もしＨＢ３００が新しくなく、そのノードによって又はダウンストリームノードによって送信されたものならば、そのＨＢは、破棄される。しかしながら、もし、ソースからのホップカウント（ＨＣ）３３０が自身の値と同じであるノード（ピアノード）によってＨＢ３００が受信される場合は、ノードは、キーノードにならない可能性を増やすために、待ち時間を延長する（ステップ５７１）。同様に、メッセージが新しい場合も、メッセージは、やはり、直ちに再ブロードキャストされるのではなく、ＨＢ送信待機タイマを使用してランダム時間の間（図５Ｃに示される）、又はダウンストリームノードがＨＢを再ブロードキャストするまで、キャッシュされる。ステップ５７２において、ＨＢが再ブロードキャストされると、ＨＢ送信が真になり、ＨＢは破棄される。

再び図５Ａに戻り、もしノードが、メッセージを新しいものと判定するならば、ノードは、自身がＧＨであるか又はＧＮであるかに応じて、２つの機能のうちの１つを実施する。ノードタイプの判定は、ステップ５０８において実施される。もしノードがＧＨであるならば、ステップ５０９において、ノードは、送信者のルーティングエントリを更新し、ハートビート制御メッセージ３００は、中継されず、ノードは、アイドル状態５００になる。しかしながら、もしノードがＧＮ１５００であるならば、ノードは、上述のように且つ図５Ｃにあるように、ステップ５１０において、全てのグループメンバエントリについてルーティングテーブルを更新し、ＨＢ制御メッセージ３００を処理する。可能性のあるピアノード又はダウンストリームノードがＨＢを再ブロードキャストするまでＨＢ送信待機タイマを待つことによって、ノードは、軽度に抑制され、不要なＨＢ制御メッセージがブロードキャストされないことを確実にすることができる。

もし制御メッセージがＭＲ４００であるならば、ノードは、ステップ５１１から始まるメッセージ処理を行う。ノードは、ステップ５１１において、メッセージがネイティブであるかどうかを判定する。ノードは、ＧＩＤ３０５を、メモリに格納されているグループ
識別と比較する。もしＧＩＤが、メモリに格納されている識別と一致しないならば、ノードは、ステップ５１２において、外部ＭＲ処理を開始させる。もしＧＩＤが、メモリに格納されている識別と一致するならば、ノードは、そのＭＲ４００を送信したノードが、ＬＰＧ１１５のメンバであるかどうかを判定する。ノードは、ノードＩＤ４１０を、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ノードは、ステップ５１４において、ＭＲ４００をただ中継する。ＭＲが中継されることによって、新しいグループノードは、完全なハートビートサイクルを待つ必要なくＬＰＧに参加することができる。もしＭＲを送信したノードが参加リストに挙げられていない場合は、そのノードは、参加ノードであるとみなすことができる。ルーティングテーブルには、参加ノードのルーティングエントリはない。一実施形態では、ノードは、ＭＲをＧＨに向けて転送することができる。ノードは、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノードは、（ＭＲの）発信元ノードを宛先リストに追加することができる、すなわち、発信元ノードについてのルーティングエントリを予約しておくことができる。ノードは、中継ノード情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ３００が受信されるときに、ノードは、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。更に、ＨＣ_GH４２５を保存し、新しいハートビート制御メッセージのＨＣ３３０と比較することができ、上記判定の結果は、新しいハートビート制御メッセージを転送するか否かを判定するために使用される。この中継ノード手続きは、図６において更に説明される。

もし一致があるならば、ノードは、ステップ５１５において、ＭＲ４００が順序通りであるかどうかを判定する。ノードは、ＭＲ ＳＥＱ．ＮＯ．４０５を、メモリ内のシーケンス番号と比較する。もしＭＲ ＳＥＱ．ＮＯ．４０５が、メモリに格納されている値よりも小さいならば、ノードは、そのメッセージを無視し、アイドル状態５００になる。もしＭＲ ＳＥＱ．ＮＯ．４０５が、メモリに格納されている値よりも大きい又はその値と等しいならば、ＭＲ４００は、順序通りであり、ノードは、次いで、ステップ５１６において、現シーケンス番号の発信元からノードが既にＭＲを受信しているかどうかを（最後に格納されたシーケンス番号と比較することによって）チェックすることによって、ＭＲが新しいかどうかを判定する。もしノードが、メッセージを新しくないと判定するならば、ステップ５１７において、送信者のルーティングエントリのみが更新される。ＭＲは、中継されない。もしノードが、メッセージを新しいと判定するならば、ノードは、自身がＧＨであるか又はＧＮであるかに応じて、２つの機能のうちの１つを実施する。ノードタイプの判定は、ステップ５１８において実施される。もしノードがＧＨであるならば、ステップ５１９において、ノードは、直接の送信者及び発信元のルーティングエントリを更新する。ＭＲ１８００は、中継されず、ノードは、アイドル状態５００になる。しかしながら、もしノードがＧＮであるならば、ノードは、ステップ５２０において、送信者及び発信元についてルーティングテーブルを更新し、ＭＲを中継する。更に、ＭＲ４００のＳｅｑ．Ｎｏ．４０５は保存され、後続のハートビート制御メッセージ３００と比較される。この手続きは、図６Ａ〜Ｃにおいて説明される。

＜中継ノードベースの効率的なフラッディング＞
中継ノードベースの効率的なフラッディングメカニズムは、中継ノード（ＲＮ）を選択して、制御メッセージ配信のための効率的なフラッディングツリーを形成する。ＲＮは、「ｋ」回の前制御メッセージサイクルにおいて、例えばメンバシップレポート（ＭＲ）などの少なくとも１つの制御メッセージをアップストリームノードに中継するノードである。アップストリームノードは、ＬＰＧのグループヘッダ（ＧＨ）であってもよい。

図６Ａ、Ｂ、及びＣは、本発明の典型的実施形態にしたがった、このプロセスを示して
いる。手続きは、その大部分が図５の手続きに匹敵し、したがって、詳細な説明は省略される。大きな違いは、ステップ６０７、６１０、及び６２０において発生する。ステップ６０７は、ＨＢ配信がホップカウントと先行ＨＢ３００との比較を条件としないという点で、軽度抑制方法と異なる。もしノードが、メッセージを新しくないと判定するならば、ステップ６０７において、送信者のルーティングエントリのみが更新される。ハートビート制御メッセージは、中継されない。ステップ６２０では、ＭＲ中継機能が、図６Ｃに示されたステップを反映するように変更される。もしノードが、ＭＲ４００の次ホップであるならば、ＭＲ４００のＳｅｑ．Ｎｏ．４０５は、ステップ６２１において格納され、ＭＲ中継機能６２２は、通常通りに呼び出される。そして、後続のハートビート制御メッセージ３００の到着時において、ステップ６１０に達すると、図６Ｂの手続きが呼び出される。もしＨＢ３００のＨＣ３３０が、ステップ６１１において上限内であるならば、ＨＢ３００をブロードキャストするか否かを判定するために、ステップ６１２においてＳｅｑ．Ｎｏ．３１５とＳｅｑ．Ｎｏ．４０５との比較が行われる。具体的には、もし着信ＨＢのＳｅｑ．Ｎｏ．３１５が、前ＭＲ４００のＳｅｑ．Ｎｏ．４０５からプリセット定数を差し引いたものよりも大きいならば、ＨＢ３００は、ステップ６１３において、通常通りにブロードキャストされる。しかしながら、もし新しいＨＢのＳｅｑ．Ｎｏ．３１５が、ＭＲ ＳＥＱ．ＮＯ．４０５からプリセット定数ｋを差し引いたものよりも小さいならば、ＨＢは、破棄される。定数ｋは、制御メッセージのサイクルの数を定めるために設定された任意の数であってよい。ｋは、ＨＢメッセージの頻度及びその他の要因に応じて動的パラメータとして実装されてよい。ｋは、可変であってよいが、値を５〜１０サイクルに設定することによって良い結果を得られることが示されている。

更に、メッセージを中継する効率を高めるため及び適時な配信を確実にするために、受動応答が追加されてよい。上述の実施形態では、ノードから、ＨＢが受信されたという応答はない。したがって、ＨＢの紛失に起因する構造的破壊を回避するために、ノードは、他のノードから伝送されたＨＢの受信者からの受動応答を、設定時間にわたって待つことができる。上記受動応答が受信されないときは、ノードは、第２のＨＢ中継を発行し、フェイルセーフメカニズムとしてブラインドフラッディングをトリガすることができる。

＜ＧＨとしてのＲＳＵの使用＞
ＲＳＵの役割は、ＬＢＲのユニキャスト性能に影響を及ぼす。前述のように、ＲＳＵは、ＧＨとして使用されてもよい。ＲＳＵがＧＨになった場合は、ＲＳＵ ＬＰＧの領域内の全ての車両は、ＬＰＧに属している。言い換えると、通行車両は、それがメンバであったＬＰＧを破棄してよい。この場合、固定のＬＰＧ（ＲＳＵ ＬＰＧ）は、ＬＢＲを開始させず、ＲＳＵへのルートを形成するだけである。固定のＬＰＧ（ＲＳＵ ＬＰＧ）は、車両の再グループ分けを行わないが、ＲＳＵは、ＭＲをトリガしない特別なＨＢを発行する。この特別なＨＢは、ＲＳＵへのルートを構築するためだけに使用される。ＲＳＵが車両へのルートを必要とするときは、ＲＳＵは、モバイルＬＰＧのＬＰＧ制御メッセージ（ＨＢ及びＭＲ）を使用することによって、車両へのルートを構築することができる。

図７Ａ及び図７Ｂは、図５において説明された軽度抑制技術と組み合わせた、この特別なＨＢを含むための改良方法を示している。具体的には、ステップ６０２及び６０３の追加が、この方法と図５との違いを示している。もしＨＢが、ＲＳＵからブロードキャストされるならば、そのＨＢは、図７Ｂのステップに基づいて、いずれかのフラッティング技術を経ることができる。

本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかになるであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。

１００ ＲＳＵ
１１０ 移動車両
１１５ ＬＰＧ

クロック２１０５は、ＲＳＵ１００のためのタイミングを維持するために使用される。特に、クロック２１０５は、内部クロックとして機能し、タイマ２１１０を設定するための基準として使用される。タイマ２１１０は、様々なメッセージをいつブロードキャストするべきかを判定するために使用される、すなわち、ＧＨの場合はハードビート間隔（Ｔ）を、又はＧＮの場合は応答メッセージを判定する。制御手段２１２５又はマイクロプロセッサは、メッセージの生成、ルーティング、及びタイマを含む、ＲＳＵ１００の全てのプロセスを制御する。送受信セクション２１２０は、制御手段２１２５と協働して、メモ
リセクション２１００に格納されているデータからメッセージを作成又は生成する役割を担う。

上記のように、ハートビート制御メッセージは、グループリスト３３５も含むことができる。グループリスト３３５は、ＬＰＧ１１５内のメンバの数、各メンバのＩＰアドレス、ＧＨからのホップカウント、及び分類などの、ＬＰＧ１１５のメンバに関する情報を含むことができる。

Claims (22)

1. 無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
   少なくとも１つのルーティングパラメータを含む第１の制御メッセージをグループヘッダノードから受信することと、
   前記第１の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することと、
   もし前記第１の制御メッセージがダウンストリームノードによってブロードキャストされていると判定されるならば、前記第１の制御メッセージを破棄することと、
   もし前記第１の制御メッセージがピアノードによってブロードキャストされていると判定されるならば、時間をランダム値に設定することと、
   もし前記時間の間に前記第１の制御メッセージをブロードキャストしたダウンストリームノードがないならば、前記時間の終了時に前記第１の制御メッセージをブロードキャストすることと、
   を備える方法。
2. 請求項１に記載の方法であって、更に、
   シーケンス番号を使用して、前記第１の制御メッセージが順序通りであるかどうかを判定することと、
   もし順序通りでないならば、前記第１の制御メッセージを破棄することと、
   を備える方法。
3. 請求項２に記載の方法であって、
   前記第１の制御メッセージは、複数のルーティングパラメータを含み、前記複数のルーティングパラメータは、更に、シーケンス番号と、グループリストと、前記グループヘッダノードまでのホップカウントと、前記グループヘッダノードへの次ホップとを含む、方法。
4. 請求項３に記載の方法であって、
   前記第１の制御メッセージがダウンストリームノード、アップストリームノード、又はピアノードからブロードキャストされているか否かを判定することは、更に、
   前記第１の制御メッセージの、前記グループヘッダノードまでの前記ホップカウントを、前記現ノードの、前記グループヘッダノードまでのホップカウントと比較することであって、もし前記２つのホップカウントが等しいならば、前記第１の制御メッセージはピアノードによってブロードキャストされている、ことを含む、方法。
5. 請求項４に記載の方法であって、更に、
   もし前記第１の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも小さいならば、前記第１の制御メッセージを破棄することと、
   もし前記第１の制御メッセージの前記ホップカウントが、前記現ノードの前記ホップカウントよりも大きいならば、前記時間を取り消し、前記複数のルーティングパラメータ内における前記制御メッセージの状態を「送信済み」に設定することと、
   を備える方法。
6. 請求項５に記載の方法であって、更に、
   前記複数のルーティングパラメータの少なくとも１つに基づいて、ルーティングテーブルを更新することと、
   少なくとも１つの追加のルーティングパラメータを含む第２の制御メッセージを、前記ローカルピアグループ内のグループノードから受信することと、
   前記少なくとも１つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
   前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
   を備える方法。
7. 請求項６に記載の方法であって、更に、
   前記第２の制御メッセージに対するソースを判定することと、
   前記第２の制御メッセージの直接の送信者を判定することと、
   前記第２の制御メッセージ内の前記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
   前記第２の制御メッセージ内の上記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
   を備える方法。
8. 請求項７に記載の方法であって、
   前記転送テーブルは、情報のパケットをルーティングするために使用される、方法。
9. 請求項８に記載の方法であって、
   前記第１の制御メッセージの受信後に、ノードは、前記第１の制御メッセージ内の前記ホップカウントを増分させ、前記ノードの識別を、前記第１の制御メッセージ内の、前記グループヘッダノードへの前記次ホップに挿入する、方法。
10. 請求項９に記載の方法であって、
    前記ノードは、前記増分及び前記挿入を実施した後に、前記第１の制御メッセージを転送する、方法。
11. 請求項９に記載の方法であって、
    前記第２の制御メッセージの受信後に、ノードは、前記第２の制御メッセージを前記グループヘッダノードに転送する、方法。
12. 請求項５に記載の方法であって、更に、
    もし前記第１の制御メッセージが路側機（ＲＳＵ）から受信されるならば、前記ＲＳＵの前記ルーティングテーブルを更新することと、
    前記第１の制御メッセージをブロードキャストすることと、
    を備える方法。
13. 無線アドホックネットワークのローカルピアグループ内のノード間において制御メッセージを散布するための方法であって、
    グループヘッダノードから第１の制御メッセージを受信することと、
    前記第１の制御メッセージをブロードキャストすることと、
    前記第１の制御メッセージに応じて前記ローカルピアグループ内のグループノードから第２の制御メッセージを受信することと、
    前記第２の制御メッセージのシーケンス番号を格納することと、
    前記グループヘッダノードから第３の制御メッセージを受信することと、
    前記第３の制御メッセージの前記シーケンス番号を前記第２の制御メッセージの前記シーケンス番号と比較することと、
    前記第３の制御メッセージの前記シーケンス番号が、前記第２の制御メッセージの前記シーケンス番号からプリセット定数を差し引いた値よりも大きい場合にのみ、前記第３の制御メッセージをブロードキャストすることと、
    を備える方法。
14. 請求項１３に記載の方法であって、更に、
    前記第３の制御メッセージの前記シーケンス番号が、前記第２の制御メッセージの前記シーケンス番号から前記プリセット定数を差し引いた値よりも小さい場合に、前記第３の制御メッセージを破棄することを備える方法。
15. 請求項１４に記載の方法であって、
    前記プリセット定数は、前記第３の制御メッセージをブロードキャスト又は破棄する前に経過する制御メッセージサイクルの数を決定する、方法。
16. 請求項１４に記載の方法であって、更に、
    前記第１の制御メッセージ内に含まれる複数のルーティングパラメータの少なくとも１つに基づいて、ルーティングテーブルを更新することと、
    前記第２の制御メッセージに含まれる前記少なくとも１つの追加のルーティングパラメータに基づいて、前記ルーティングテーブルを更新することと、
    前記更新するステップの両方が完了したら、前記ルーティングテーブルをもとに転送テーブルを生成することと、
    を備える方法。
17. 請求項１６に記載の方法であって、更に、
    前記第２の制御メッセージに対するソースを判定することと、
    前記第２の制御メッセージの直接の送信者を判定することと、
    前記第２の制御メッセージ内の前記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者を通じて前記ソースに対する次ホップを変更することと、
    前記第２の制御メッセージ内の前記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更することと、
    を備える方法。
18. 請求項１７に記載の方法であって、
    前記転送テーブルは、情報のルーティングパケットのために使用される、方法。
19. 請求項１８に記載の方法であって、
    前記第３の制御メッセージの受信後に、ノードは、前記第３の制御メッセージ内のホップカウントを増分させ、前記ノードの識別を、前記第３の制御メッセージ内の、グループヘッダノードへの前記次ホップに挿入する、方法。
20. 請求項１９に記載の方法であって、
    前記ノードは、前記増分及び前記挿入を実施した後に、前記第３の制御メッセージを転送する、方法。
21. 請求項２０に記載の方法であって、
    前記第２の制御メッセージの受信後に、ノードは、前記第２の制御メッセージを前記グループヘッダに転送する、方法。
22. 請求項１５に記載の方法であって、更に、
    前記第３の制御メッセージが路側機（ＲＳＵ）から受信される場合に、前記ＲＳＵの前記ルーティングエントリを更新することと、
    前記第３の制御メッセージをブロードキャストすることと、
    を備える方法。

Images