【課題】メッセージをルーティングする方法及び通信デバイスを提供する。
【解決手段】ユニキャストメッセージをルーティングする方法は、グループヘッダノードからルーティングパラメータを含む第１の制御パケットを受信すること（１９０１）、ルーティングパラメータに基づいてルーティングテーブルを更新すること、グループノードから追加のルーティングパラメータを含む第２の制御パケットを受信すること、追加のルーティングパラメータに基づいてルーティングテーブルを更新すること（１９１９）、及び更新ステップの両方が完了するとルーティングテーブルから転送テーブルを生成することを含む。ユニキャストメッセージは、転送テーブルに基づいてルーティングされる。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動環境における通信のためのネットワークに関する。より詳細には、本発明は、通信パケットを処理し、ルーティングテーブル及び転送テーブルを生成し、ユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法に関する。
【背景技術】
【０００２】
無線ホームネットワーク若しくは無線オフィスネットワーク、又はローカルカフェ、ファーストフードチェーン若しくはホテルにおける、いわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び社会が全体として、コンピュータネットワーク、特にインターネットを広く受け入れると共に利用することによって享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内の物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【０００３】
これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、２００４年７月２９日に、ミシガン州グランドヘブンは、都市の６平方マイルを網羅し、ミシガン湖まで１５マイルにわたって広がる都市全域の無線ネットワークを実装して、「全米最初のＷｉＦｉ都市」であるという特徴を主張した。多数の市当局者は、ＷｉＦｉを、企業を誘致すると共に維持するために、下水、電力、電話及び交通機関と概ね同様に不可欠であるインフラストラクチャと見ている。そのようなシステムは、市当局者にとって、市職員の間での通信を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまでに及ぶ、多数の利点を有する。
【０００４】
このように、より広範囲にわたって無線で接続することを推し進めてきたが、日々の生活の或る領域が立ち遅れている。アメリカの道路及び高速道路は、基礎的な衛星システム及びセルラ電話システムよりも優れた無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することから、数多くの利点が得られる。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は、直ちに影響を及ぼされる可能性がある全ての車両に中継することができる。
【０００５】
さらに、自動車を互いにネットワーク接続することによって、近くにある他の車両に影響を及ぼす可能性がある車両についての情報を中継できるようになる。たとえば、１台の自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にある全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが多少の余裕をもって、必要な措置を講じることができるようになる。この態様が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが、緊急道路障害物警告、交差点の調整、隠れた私道に関する警告、車線変更又は合流の支援を含む、車両安全への応用形態の数多くの態様において現われる可能性がある。
【０００６】
車両安全通信（「ＶＳＣ」）は、車両間通信とインフラストラクチャを介した車両通信
とに大きく分けることができる。車両間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの同じ無線範囲内にあるときに、又は他の車両を介してマルチホップ中継できるときに、車両同士が通信することが可能である。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【０００７】
重要なＶＳＣ性能要件は、衝突回避のような種々のＶＳＣの応用形態を支援するために、待ち時間が短いこと（約１００ミリ秒）、及びスループットを維持すること（別の言い方をすると、近くにある車両が警告メッセージを受信するのに成功するパーセンテージ）を含む。
【０００８】
単に、移動中の車両に無線アンテナを取り付けて、その後、調整されないまま通信を伝送するだけでは、これらの要件を満たすには不十分であろう。具体的には、無線帯域幅が限られているため、調整されないままのデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、結果として、無線波の妨害が生じるであろう。
【０００９】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。さらに、各車両が他の車両のネットワーク構成と整合しないであろう。
【００１０】
移動度が高く、また固有の関係がないため、車両を事前に車両グループとして構成することは難しい（たとえば、どの車両も、予めその近くにある車両について何も知らない）。安全通信を設定するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならないので、グループ内の車両は概ねリアルタイムに自らを構成して、安全通信を行うことができるようにしなければならない。調整されていない車両の移動度が高いことは、近くにある車両又は車両グループが頻繁に変化することを暗示しており、車両グループ内で（移動度、アドレス、名前、メディアセッションのための）サポートサーバを用いることを困難にしている。これらの重大な違いが、既存の戦略的なアドホックネットワーク接続技術を、安全通信のために車両グループに直に適用できないようにしている。
【００１１】
ホットスポットのような、他の所で利用されているＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量及び待ち時間の問題のために実用的ではない。大都市付近の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイル（時速４８〜９６ｋｍ）の速度で個々の通信エリアを通り抜けていく。大部分の無線システムは、そのネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【００１２】
具体的には、或る車両が通信エリアに入るとき、その車両は、無線アクセスポイント又はルータによって特定されると共に構成命令を発行される必要がある。或る車両が通信エリアを出るとき、無線アクセスポイント又はルータは、その記録を更新して、そのネットワークから車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さが、情報更新、たとえば無線アクセスポイント又はルータによってブロードキャストされ、その範囲内の全ての車両によって応答されるべきハンドシェーキングの頻度を決定する。これら全ての車両が同時に情報を伝送すると、システムが取り扱えないほどの付加が容易にかかってしまう。
【００１３】
車両間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔ及びＣａｒＴａｌｋ２０００はいずれも、車両間通信ネットワークを開発している。これらのシステムはいずれも、位置情報を得るため、及びメッセージをルーティングするために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔシステムは、メッセージを中継するために、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのためのバックボーンとして、ＧＰＳ情報のような位置データが決定的な役割を果たす。
【００１４】
ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車両間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。しかしながら、これらのシステムの欠点は、車両が高速で移動しているため、位置情報がすぐに古くなるということである。
【００１５】
ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッド及び無線帯域幅の無駄が生じる。その結果、そのようなＧＰＳ位置ルーティング技術は、最小の通信遅延時間又はマルチホップスループットの維持を達成することができない。さらに、Ｃａｒｔａｌｋ２０００およびＦｌｅｅｔＮｅｔの両方においてすべての車両にＧＰＳを搭載する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００１６】
したがって、過度の帯域幅及び著しいプロトコルオーバーヘッドを必要とすることなく、最小の通信待ち時間、又はマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるネットワークのノードとして車両と路側機との両方を有するアドホックネットワークを構成することが必要とされている。
【課題を解決するための手段】
【００１７】
無線アドホックネットワークのローカルピアグループ内のノード間で情報のパケットをルーティングする方法を開示する。本方法は、グループヘッダノードから、少なくとも１つのルーティングパラメータを含む第１の制御パケットを受信すること、少なくとも１つのルーティングパラメータに基づいてルーティングテーブルを更新すること、ローカルピアグループ内のグループノードから、少なくとも１つの追加のルーティングパラメータを含む第２の制御パケットを受信すること、及び少なくとも１つの追加のルーティングパラメータに基づいてルーティングテーブルを更新することを含む。本方法は、これらの更新するステップの両方が完了すると、ルーティングテーブルから転送テーブルを生成することをさらに含む。
【００１８】
ユニキャストメッセージは、転送テーブルに基づいてルーティングされる。
【００１９】
少なくとも１つのルーティングパラメータは、グループリスト、ホップカウント及びグループヘッダへの次ホップを含む。第１の制御パケットに基づいてルーティングテーブルを更新することは、グループリストに基づいて宛先リストを変更すること、第１の制御パケットを直接中継した直接の中継ノードを除く前記宛先リスト内のすべての宛先に対し、宛先への次ホップを前記グループヘッダに初期化すること、及びグループヘッダへの次ホップを前記直接の中継ノードに変更することを含む。
【００２０】
ルーティングテーブルを更新することは、第１の制御パケット及び第２の制御パケットが順序通りである場合にのみ発生し、本方法は、第１の制御パケット及び第２の制御パケットが順序通りであるか否かを判定することを含む。
【００２１】
第１の制御パケットに基づいてルーティングテーブルを更新することは、第２の制御パケットに対するソースを判定すること、第２の制御パケットの直接の送信者を判定すること、第２の制御パケットの少なくとも１つの追加のルーティングパラメータに基づいて、直接の送信者を介してソースに対する次ホップを変更すること、及び第２の制御パケットの少なくとも１つの追加のルーティングパラメータに基づいて直接の送信者に対する次ホップを変更することを含む。
【００２２】
無線アドホックネットワークのローカルピアグループ内のノード間で情報のパケットをルーティングするルーティング方法も開示する。本方法は、ノードによって受信される制御パケットのタイプを判定すること、制御パケットがノードにより順序通りに受信されているか否かを判定すること、及び制御パケットが順序通りである場合に、制御パケットに含まれる情報に基づいてテーブルを更新することを含む。制御パケットは、ハートビート制御パケット又はメンバシップレポートであり得る。ローカルピアグループの各ノードは、グループヘッダ又はグループノードであり得る。ノードがグループノードであり、制御パケットのタイプがハートビート制御パケットである場合、更新するステップは、ハートビート制御パケットに含まれるグループメンバシップリストのすべてのメンバを含むようにテーブルを変更することを含む。
【００２３】
本方法はまた、ノードが制御パケットを順序通りに受信しているか否かを判定することも含む。この判定は、制御パケットに含まれるシーケンス番号値のメモリに格納されているシーケンス番号との比較に基づく。受信されたシーケンス番号値がメモリに格納されているシーケンス番号より大きい場合、制御パケットは順序通りに受信されている。
【００２４】
アドホックネットワークにおいてノードによって着信パケットを処理する方法も開示する。本方法は、着信パケットを受信すること、着信パケットがそのノード宛てであるか否かを判定すること、着信パケットがそのノード宛てでない場合、ルーティングテーブルのエントリを読み取ることに基づいて宛先への次ホップを判定すること、及び宛先への次ホップに着信パケットを中継することを含む。着信パケットがそのノード宛てである場合、ノードは着信パケットを処理し消費する。
【００２５】
アドホック無線ネットワークにおいてマルチキャストメッセージをルーティングする方法も開示する。本方法は、転送するためにマルチキャストメッセージを受信するステップと、マルチキャストメッセージのマルチキャストグループ宛先がマルチキャスト転送テーブルにあるか否かを判定するステップと、マルチキャストメッセージが以前に転送されているか否かを判定するステップと、マルチキャストメッセージが以前に転送されていると判定され、且つマルチキャストグループ宛先がマルチキャスト転送テーブルにあると判定された場合、マルチキャストメッセージを転送するステップと、マルチキャストメッセージが送信された後、マルチキャストメッセージを送信済みリストに追加するステップとを含む。
【００２６】
本方法は、マルチキャストメッセージが送信待ち行列にあるか否かを判定するステップをさらに含み、マルチキャストメッセージは、送信待ち行列にない場合、転送のために送信待ち行列に追加され、送信待ち行列にある場合、破棄される。
【００２７】
マルチキャスト転送テーブルを、ローカルピアグループ内の各ノードに対し分類を割り当てること、ローカルピアグループ内のすべてのノードから選択されたノードであるグループヘッダからのホップカウントを各ノードに対して判定すること、
【００２８】
マルチキャストメンバシップ情報を収集すること、並びに収集されたマルチキャストメンバシップ情報及びグループヘッダからのホップカウントに基づき、マルチキャストグルー
プに対するメッシュにおける転送ノードを選択することによって生成することができる。各選択された転送ノードは、マルチキャストグループ識別をマルチキャスト転送テーブルに格納する。分類、グループヘッダからのホップカウント及びマルチキャストメンバシップ情報は、グループヘッダからローカルピアグループ内の他のノードにブロードキャストされる。
【００２９】
マルチキャストルーティングテーブルを、グループヘッダに中継されたマルチキャストメンバシップ情報を含むメンバシップレポートに基づいて生成することも可能であり、マルチキャストメンバからグループヘッダにメンバシップレポートを中継するすべてのノードは、マルチキャストメンバを含むマルチキャストグループに対する転送ノードとなる。各転送ノードは、マルチキャスト転送テーブルにマルチキャストグループ宛先としてマルチキャストメンバシップ情報を記録する。
【００３０】
グループヘッダは、各マルチキャストメンバに対するグループヘッダからのホップカウントに基づいて、マルチキャストグループに対する転送ノードの数を調整する。調整は、グループヘッダと、特定のマルチキャストグループのグループヘッダに最も近いマルチキャストメンバであると判定されたマルチキャストメンバとの間のすべての転送ノードをプルーニングする。グループヘッダは、それ自体もプルーニングする。転送ノードは、プルーニングされると、マルチキャスト転送テーブルのマルチキャストグループ宛先から、プルーニングされたマルチキャストグループに対応するマルチキャストメンバシップ情報を削除する。
【００３１】
また、転送ノードは、マルチキャストグループに対応するマルチキャストメンバシップ情報を含むメンバシップレポートを受信せずに、プリセットされたタイマが満了する場合、マルチキャストグループノードの非転送ノードとなる。
【００３２】
マルチキャストメッセージをルーティングする方法は、マルチキャスト転送テーブルに列挙されているマルチキャストグループ宛先を有する各ノードに対し送信チャネルを選択すること、及びマルチキャスト転送テーブルに列挙されているマルチキャストグループ宛先を有する各ノードに対し受信チャネルを選択することをさらに含む。送信チャネル及び受信チャネルを、交互になるように選択することができる。たとえば、送信チャネル及び受信チャネルは、単一交互パターンで交互になるように選択される。代替的に、送信チャネル及び受信チャネルは二重交互パターンで交互になるように選択される。
【００３３】
本方法は、所定時間、送信されたマルチキャストメッセージをメモリに格納すること、送信されたマルチキャストメッセージが、隣接する転送ノードから所定時間内に受信さられているか否かを検出すること、及び送信されたマルチキャストメッセージが所定時間内に検出されない場合、転送ステップを繰り返すことをさらに含む。送信されたマルチキャストメッセージが所定時間内に検出された場合、マルチキャストメッセージはメモリから破棄される。
【００３４】
無線通信デバイスも開示する。本デバイスは、転送するためにマルチキャストメッセージを受信する手段と、マルチキャストメッセージに対するマルチキャストグループ宛先がマルチキャスト転送テーブルにあるか否かを判定する手段と、マルチキャストメッセージが先に転送されているか否かを判定する手段と、マルチキャストメッセージが先に転送されていないと判定される場合、且つマルチキャストグループ宛先がマルチキャスト転送テーブルにあると判定される場合、マルチキャストメッセージを転送する手段と、マルチキャストメッセージが送信された後にマルチキャストメッセージを送信済みリストに追加する手段とを備える。本デバイスは、マルチキャスト転送テーブル及び送信済みリストを格納する手段をさらに備える。
【００３５】
また、着信パケットを受信する手段と、着信パケットがそのノード宛てであるか否かを判定する手段と、着信パケットがそのノード宛てでない場合、ルーティングテーブルのエントリを読み取ることに基づいて宛先への次ホップを判定する手段と、着信パケットを宛先への次ホップに中継する手段とを開示する。
【００３６】
無線通信デバイスのそれぞれを、移動車両に設置することができる。
【００３７】
また、移動車両の無線通信デバイスにおける少なくとも１つのプロセッサによって実行されることが可能な、メッセージをルーティングするように少なくとも１つのプロセッサを制御するためのコンピュータ可読命令のセットを含むコンピュータ可読媒体も開示する。
【００３８】
本発明のこれらの特徴、利益及び利点、並びに他の特徴、利益及び利点は、以下の図面を参照することによって明らかになるであろう。なお、図面を通じて、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【００３９】
【図１】本発明による路側機に近接する複数のＬＰＧの一例を示す。
【図２】本発明の一実施形態によるルータとして機能する路側機を含むアドホックネットワークを示す。
【図３Ａ】本発明の一実施形態による、路側機が分離されているアドホックネットワークの一例を示す。
【図３Ｂ】本発明の一実施形態による、複数の路側機が路側機のリモートアクセスポイントと連動しているアドホックネットワークの一例を示す。
【図３Ｃ】本発明の一実施形態による、共に複数の路側機が路側機のリモートアクセスポイントと連動しているアドホックネットワークの第２の例を示す。
【図４】本発明の一実施形態によるリンクされた路側機を含むアドホックネットワークの一例を示す。
【図５】本発明の一実施形態によるリンクされた路側機を含むアドホックネットワークの第２の例を示す。
【図６】本発明の一実施形態による３つの路側機グループの一例を示す。
【図７】図６の３つの路側機グループに対するチャネル割当ての一例を示す。
【図８】本発明の一実施形態によるアプリケーションサーバとして機能する路側機を含むアドホックネットワークの一例を示す。
【図９】本発明の一実施形態によるアプリケーションサーバ及びルータとして機能する路側機を含むアドホックネットワークの一例を示す。
【図１０】本発明の一実施形態によるアプリケーションサーバ及びルータとして機能する路側機を含むアドホックネットワークの第２の例を示す。
【図１１】路側機のブロック図である。
【図１２】本発明の一実施形態によるヘッダ解決方法のフローチャートである。
【図１３】グループヘッダとして路側機を有する動的ローカルピアグループの一例を示す。
【図１４】それぞれがグループヘッダとして路側機を有する、２つの固定ローカルピアグループの一例を示す。
【図１５】グループノードとして路側機を有する動的ローカルピアグループの一例を示す。
【図１６】それぞれがグループノードとして路側機を有する、２つの固定ローカルピアグループの一例を示す。
【図１７】本発明の一実施形態による、ローカルピアグループを形成しユニキャストルーティングテーブル２３００を生成するために使用される、ハートビート制御パケットの一例を示す。
【図１８】本発明の一実施形態による、ローカルピアグループを形成しユニキャストルーティングテーブル２３００を生成するために使用される、メンバシップ報告パケットの一例を示す。
【図１９】ユニキャストルーティングテーブル２３００の生成及び維持のフローチャートである。
【図２０】本発明の一実施形態によるユニキャストパケットをルーティングするプロセスのフローチャートである。
【図２１】ユニキャストルーティングテーブル２３００を更新するプロセスのフローチャートである。
【図２２】ユニキャストパケットのルーティングに対する有限状態機械の図である。
【図２３】本発明の一実施形態による内部ユニキャストルーティングテーブル２３００の一例を示す。
【図２４】マルチキャストグループ２４００の一例を示す。
【図２５】本発明の一実施形態によるマルチキャストツリーの作成のフローチャートである。
【図２６】図２５に示す実施形態によって形成されるマルチキャストグループ２４００の一例を示す。
【図２７】図２５に示す実施形態によってマルチキャストツリーを作成するために使用されるハートビート制御パケットの一例を示す。
【図２８】図２５に示す実施形態によってマルチキャストツリーを作成するために使用されるメンバシップレポートパケットの一例を示す。
【図２９】図２５に示す実施形態によるマルチキャスト転送テーブルの生成及び維持のフローチャートである。
【図３０Ａ】図２５に示す実施形態によるグループヘッダに対する機能状態遷移図である。
【図３０Ｂ】図２５に示す実施形態によるグループメンバに対する機能状態遷移図である。
【図３１】本発明によるマルチキャスト転送テーブルの一例を示す。
【図３２】本発明の第２の実施形態によってマルチキャストツリーを作成するために使用されるメンバシップレポートパケットの一例を示す。
【図３３】本発明の第２の実施形態を使用してのマルチキャスト転送テーブルの生成及び維持のフローチャートである。
【図３４】本発明の第２の実施形態によるノードのための機能状態遷移図である。
【図３５】本発明の第３の実施形態によるマルチキャストツリーを作成するために使用されるプルーンパケットの一例を示す。
【図３６】第３の実施形態によるマルチキャスト転送テーブルの生成及び維持のフローチャートである。
【図３７Ａ】第３の実施形態によるグループヘッダに対する機能状態遷移図である。
【図３７Ｂ】第３の実施形態によるグループメンバに対する機能状態遷移図である。
【図３８Ａ】本発明の第２の実施形態によって形成されるマルチキャストグループ２４００を示す図である。
【図３８Ｂ】本発明の第３の実施形態によって形成されるマルチキャストグループ２４００を示す図である。
【図３９】本発明の一実施形態によるマルチキャストモードにおける転送ノードに対する階層機能を示す図である。
【図４０】本発明の一実施形態によるマルチキャストパケットをルーティングするプロセスのフローチャートである。
【図４１】本発明の別の実施形態によるマルチキャストパケットをルーティングするプロセスの階層ネットワーク層フローチャートである。
【図４２】本発明のさらに別の実施形態によるマルチキャストパケットをルーティングするプロセスの階層ネットワーク層フローチャートである。
【図４３】本発明の一実施形態によるチャネル割当て方式を示す。
【図４４】チャネル交互割当て方式による、送信チャネル及び受信チャネルに対するチャネル割当ての一例を示す。
【図４５】二重チャネル交互割当て方式による、送信チャネル及び受信チャネルに対するチャネル割当ての一例を示す。
【図４６】二重チャネル交互割当て方式により送信チャネル及び受信チャネルを割り当てるプロセスのフローチャートである。
【図４７】本発明の一実施形態による、認証サービスを提供する路側機の一例を示す。
【図４８】本発明の一実施形態によるネットワーク構成支援を提供する路側機の一例を示す。
【図４９】情報収集デバイスとして使用される路側機の一例を示す。
【図５０】本発明の一実施形態による安全警告ルーティングを提供する路側機の一例を示す。
【図５１】本発明の一実施形態による位置及び追跡機能を実行する路側機の一例を示す。
【図５２】本発明の一実施形態による車両整備サーバおよびデータベースとして機能する路側機の一例を示す。
【図５３】本発明の一実施形態による通行料収集デバイスとして機能する路側機の一例を示す。
【発明を実施するための形態】
【００４０】
本発明によれば、アドホックネットワークは、２つのタイプのノード、すなわち路側機（Ｒｏａｄ Ｓｉｄｅ Ｕｎｉｔ。以下、「ＲＳＵ」）と移動車両とに分けられる。ＲＳＵは固定ノードであり、車両はグループ内を移動することができる。
【００４１】
図１は、本発明によるアドホックネットワークの一例を示す。ＲＳＵ１００は、道路の側部に沿って位置している。ネットワークで使用されるＲＳＵ１００の数は、ＲＳＵ１００の無線アンテナの範囲、所望の通信範囲、移動デバイスの数、土地の地形、環境状態、交通パターン及び人口密度のような、いくつかの要因によって決まる。図１は、２つのＲＳＵ１００を示している。囲まれているエリアは、各ＲＳＵ１００の無線範囲を表している。各ＲＳＵ１００を使用して、単独で又はグループで走行している移動車両１１０と通信することができる。
【００４２】
移動車両１１０を、管理可能なグループに編成することができる。これらのグループは、ノード間のデータの伝送の調整に使用される。グループは、隣接するノードの相対位置に基づくか、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ（「ＬＰＧ」）は、単一ＬＰＧ１１５内で、且つ複数のＬＰＧ間で無線信号をルーティングするための基礎である。
【００４３】
図１は、３つのＬＰＧ１１５を示している。各ＬＰＧ１１５は、少なくとも１つの移動車両１１０から構成されている。図１は、ＬＰＧ１ １１５_１が３つの移動車両を含み、ＬＰＧ２ １１５_２が２つの移動車両を含み、ＬＰＧ３ １１５_３が３つの移動車両を含むことを示している。ＲＳＵ１００は、ＬＰＧ１１５内に存在して特別なＬＰＧノードとして機能することができ、又はＬＰＧ１１５の外で別個のノードとして存在することができる。ＲＳＵ１００は、ＬＰＧ１１５内のノードではなく、ＬＰＧ１１５と共に使用される場合、ＬＰＧ間通信用の境界ノードとして機能することができる。通常、１つのＲＳＵ
１００の無線有効範囲は、１つのＬＰＧのサイズより大きく、すなわち、１つのＲＳＵ１００の無線範囲内には２つ以上のＬＰＧ１１５があることになる。それを図１に示す。したがって、１つのＬＰＧ１１５からのパケットを、ＲＳＵ１００を使用して別のＬＰＧ１１５にブロードキャストすることができる。この場合、ＲＳＵ１００は、そのメモリに格納されたＬＰＧに関する情報を含むことになる。
【００４４】
移動車両１１０は、車車（Ｖ−Ｖ）チャネルによって互いに通信する。移動車両は、車路（Ｖ−Ｒ）チャネルを介して路側機と通信する。さらに、ＲＳＵ１００は、Ｒ−Ｒチャネル又はＲ−Ｂチャネル（バックボーン）を介して互いに通信する。Ｒ−Ｒ通信は専用チャネル又は有線バックボーンを使用するため、その通信は、Ｖ−Ｖ通信又はＶ−Ｒ通信に干渉しない。Ｖ−Ｖチャネル及びＶ−Ｒチャネル間でチャネルを共有することに対し、いくつかの代替方法がある。好ましい実施形態では、Ｖ−Ｒ通信用に専用チャネルがある。残りのチャネルは、Ｖ−Ｖ通信及び／又はＶ−Ｒ通信に対して共有される。Ｖ−Ｒチャネルは、他のチャネルと同じＲＦ周波数帯域にあってもよい。代替的に、Ｖ−Ｒチャネルは、異なる通信範囲及びデータレートを可能にするように異なるＲＦ周波数帯域にあってもよい。
【００４５】
別の実施形態では、すべてのチャネルがＶ−Ｖ及びＶ−Ｒの両方に対して動的に共有される。この手法により、性能の最適化が可能になる。しかしながら、干渉しないチャネルを厳密に調べて選択することで複雑性がもたらされる。
【００４６】
別の実施形態によれば、Ｖ−Ｒに対してのみ専用チャネルが割り当てられ、他のチャネルはＶ−Ｖのみが共有される。代替的に、Ｖ−Ｒに対し専用チャネルが使用され、Ｖ−Ｖに対し第２の専用チャネルが使用される。残りの他のチャネルは、Ｖ−Ｖ通信及びＶ−Ｒ通信によって共有される。本発明の説明を続ける目的で、チャネル割当ての好ましい実施形態を使用する。ＲＳＵ１００は、ルータ、アプリケーションサーバ又はそれらの組合せのような多くの機能を有することができる。
【００４７】
図２は、少なくとも１つのＲＳＵ１００がルータとして機能する場合のアドホックネットワークの一例を示す。アドホックネットワークは、ＲＳＵ１００と、バックボーン２００、たとえばインターネットと、移動車両１１０とを含む。ＲＳＵ１００は、３つのネットワーク階層、すなわちネットワーク層２１０、ＭＡＣ層２１５及び物理層２２０を含む。
【００４８】
物理層２２０は、ハブ、中継器及び無線機のようなデバイスを含む。物理層２２０の機能には、物理無線リンクのような通信チャネルにより、上位層データを表す信号の伝送がある。
【００４９】
ＭＡＣ（メディアアクセス制御）層２１５は、ネットワークエンティティ間でデータを転送する手続き、及び物理層２２０で発生する可能性のある誤りを検出し、場合によっては訂正するための手続きを処理する。たとえば、ＩＥＥＥ８０２．１１では、ＭＡＣ層２１５は、共有される無線チャネルへのアクセスを調整し、且つ無線媒体による通信を向上させるプロトコルを利用することにより、８０２．１１局（無線ネットワークカード及びアクセスポイント）間の通信を管理し維持する。８０２．１１ＭＡＣ層２１５は、８０２．１１ｂ又は８０２．１１ａ又は８０２．１１ｐのような８０２．１１物理（ＰＨＹ）層を使用して、８０２．１１フレームのキャリア検知、送信及び受信のタスクを実行する。
【００５０】
ネットワーク層２１０は、ネットワークエンティティ間のエンド・ツー・エンド通信のための機能を実行する。たとえば、機能には、ソースノードから宛先ノードへのメッセージのルーティング、同じマルチキャストグループのソースノードから宛先ノードへのメッ
セージのマルチキャスト、又はルーティングまたはマルチキャストの目的でのネットワークエンティティの移動度（位置）管理がある。ネットワーク層２１０は、データ経路としてユニキャスト／マルチキャストルートを発見して維持し、また、本明細書で説明するユニキャスト及びマルチキャストの手続き及びプロトコルに従って、エンドユーザ間のデータ配信方法を提供する。エンドユーザは、移動車両１１０であってもＲＳＵ１００であってもよい。
【００５１】
ＲＳＵ１００は、その無線有効範囲内のすべての移動車両１１０に対しデータをルーティングすることができる。さらに、ＲＳＵ１００は、その相対位置に応じて、ＲＳＵ１００間でデータをルーティングすることができる（たとえばＲ−Ｒ通信）。さらに、ＲＳＵ１００は、バックボーン２００から／バックボーン２００へデータをルーティングすることができ、たとえば、バックボーンから移動車両１１０にデータをルーティングすることができる。図２に示すように、移動車両１１０は、ネットワーク内の複数のＲＳＵ１００の無線範囲を通過して走行し、それにより頻繁なＩＰハンドオフがもたらされる。
【００５２】
ＲＳＵ１００に対していくつかの配置構成があり得る。一実施形態では、ＲＳＵ１００は、分離された位置に配置される。この実施形態では、ＲＳＵ１００は、互いの範囲外にあるため、他のＲＳＵ１００と連結されていない。ＲＳＵ１００のルーティング機能は、ＲＳＵのその無線範囲でのみ提供される。分離されたＲＳＵ１００の配置は、限られた利点しかないかもしれない。１つの利点は、ＲＳＵ１００が余裕をもって配置されている場合、チャネル干渉がない、ということである。複数のＲＳＵ１００における通信に対し、同じＶ−Ｒチャネルを使用することができる。さらに、ＲＳＵ１００を配置するコストが最小限である。わずかな数のＲＳＵ１００を使用して、いくつかの問題のあるエリア、たとえば混雑している交差点、既知の問題の起こり易い地域又は事故が多発する地域にサービスを提供することができる。この実施形態を、初期段階の配置に使用することが好ましい。しかしながら、ＲＳＵ１００は連結されておらず、近傍のＲＳＵ１００内の移動車両１１０を支援することができず、又は近傍のＲＳＵに関するいかなる情報も提供することができない。さらに、移動車両１１０は、隣接するすべてのＲＳＵ１００に情報が伝播されることを確認するために、各ＲＳＵ１００において情報を複製しなければならない可能性がある。
【００５３】
図３Ａは、２つの分離されたＲＳＵ１００を示す。ＲＳＵ１ １００_１は、移動車両１
１１０_１、車両２ １１０_２と通信することができるが、車両３ １１０_３〜車両６ １１０_６及びＲＳＵ２ １００_２とは通信することができない。同様に、ＲＳＵ２ １００_２は、車両５ １１０_５及び車両６ １１０_６と通信することができるが、車両１ １１０_１〜車両４ １１０_４とは通信することができない。
【００５４】
別の実施形態では、複数のリモートアクセスポイントと共に単一ＲＳＵ１００を配置することができる。この構成では、ＲＳＵ１００は、道路にある複数の無線アクセスポイント（ＡＰ）を制御する。ＲＳＵ１００は、ＡＰを介して移動車両１１０又はＬＰＧ１１５全体と通信する。車両に対するネットワーク層ピアはＲＳＵであり、移動車両１１０のＭＡＣ層及び物理層に対するピアはＡＰである。８０２．１１ａ通信又は８０２．１１ｐ通信の場合、移動車両１１０はＡＰを使用する。ネットワーク層通信を処理するために、移動車両１１０は、主にＲＳＵ１００と協働する。ＡＰはＲＳＵ１００に対するＭＡＣ層２１５機能及び物理層２２０機能を処理する。ＲＳＵ１００自体は、ネットワーク層機能２１０しか処理しない。ＡＰを実装することにより、ＲＳＵ１００のサービスエリアが拡大する。
【００５５】
複数の無線アクセスポイントを伴うＲＳＵ１００は、２つ以上のＡＰ間のルーティング機能を達成するためにスイッチ又はブロードキャストバスを含むことができる。
【００５６】
図３Ｂは、複数のＲＳＵ１００がスイッチベースの複数のアクセスポイントを使用するルーティング機能を有する、アドホックネットワークを示す。図示するように、ＲＳＵ１
１００_１は５つのＡＰ（まとめてＡＰ３３０）を制御する。ＲＳＵ２ １００_２もまた、５つのＡＰ（まとめてＡＰ３３０）を制御する。各ＲＳＵ１００とＡＰ３３０との間にハブスイッチ３２０が配置されており、それにより、１つのＡＰ３３０のみが、移動車両１１０との間の通信、すなわち移動車両１１０からのデータの受信、及び移動車両１１０へのデータの転送に関与する。移動車両１１０がＡＰの無線サービスエリア内にある時、ＭＡＣ層２１５及び物理層２２０は、ビーコン及びハンドシェイクを介して移動車両１１０とその特定のＡＰ３３０との関係を形成する。さらに、ＲＳＵ１００は、ＡＰ３３０から、各ＡＰのサービスエリア内の関連付けられている移動車両に関する情報を取得することができる。たとえば、ＡＰ５は、その無線範囲内のすべての車両に対するアクセスポイントである。各ＡＰは、２つの階層、すなわち物理層及びＭＡＣ層を含む。
【００５７】
この構成は、ユニキャストルーティング、マルチキャストルーティング及び移動度検出をサポートする。ユニキャストの場合、各ＲＳＵ１００は、ネットワーク内の各ノードに対して作成され且つメモリに格納されている転送テーブルに基づいて、各移動車両１１０に向けられるメッセージの次ホップを知る。ＲＳＵ１００は、ＬＰＧ１１５内のノードではない場合であっても、そのＶ−Ｒチャネル上のハートビート制御メッセージ１７００をオーバーヒアリングする（overhear）ことができる。ＲＳＵ１００は、この情報を、ＲＳＵ１００又はＡＰ３３０からＬＰＧ１１５及び移動車両１１０にルーティングするために使用することができる。次ホップは、移動車両１１０に関連付けられているＡＰ３３０である。言い換えれば、ＡＰ３３０は、移動車両のためのＭＡＣプロキシである。スイッチ３２０は、ＲＳＵ１００からメッセージを受信すると、そのメッセージを、特定の移動車両１１０に関連付けられている特定のＡＰ３３０に転送する。すなわち、ハブスイッチ３２０を使用して、ユニキャストメッセージは、指定されたＡＰ３３０のみに送信され、決してすべてのＡＰにはブロードキャストされない。
【００５８】
たとえば、移動車両４ １１０_４に対する次ホップはＡＰ５ ３３０_５である。したがって、ＲＳＵ１ １００_１は、移動車両４ １１０_４に対する次ホップとして、ＡＰ５ ３３０_５をそのメモリに記録する。言い換えれば、移動車両４ １１０_４がＡＰ５ ３３０_５の範囲内にある間、移動車両４ １１０_４に向けられたすべてのメッセージがＡＰ５
３３０_５を通じてルーティングされる。
【００５９】
マルチキャスト動作の場合、マルチキャストグループ２４００に参加している移動車両１１０に関連付けられるＡＰ３３０のみが、マルチキャストグループ２４００のマルチキャスト転送ノードとなる。マルチキャストグループ２４００については、後により詳細に説明する。スイッチ３２０は、いずれのＡＰ３３０が転送ノードであるかを知っており、マルチキャストパケットは、それらの転送ノードにのみ配信される。転送ノードは、マルチキャストグループ２４００にある宛先ノードに複数のメッセージを転送するノードである。
【００６０】
たとえば、マルチキャストメッセージが車両２ １１０_２及び車両４ １１０_４に向けられている場合、車両２ １１０_２及び車両４ １１０_４はマルチキャストグループ２４００に参加している。ＲＳＵ１ １００_１に次ホップ情報が記録されているため、ＲＳＵ１ １００_１は、このマルチキャストグループ２４００に対してＡＰ３ ３３０_３及びＡＰ５ ３３０_５が転送ノードであることを知っている。ＲＳＵ１ １００_１、ＡＰ３ ３３０_３及びＡＰ５ ３３０_５は、マルチキャストメッセージの転送ノードとなる。スイッチ３２０は、ＡＰ３ ３３０_３及びＡＰ５ ３３０_５にのみマルチキャストメッセージを配信する。この構成はまた、移動度検出もサポートする。ユニキャストの場合の次ホップ
情報及びマルチキャストの場合の転送ノード情報は、連続的に更新される。ＡＰ３３０又は移動車両１１０は、移動度検出を実行する。一実施形態では、ＡＰ３３０は、周期的ビーコンの使用に基づいて移動度を検出する。ビーコンは、ＡＰ識別を含む。移動車両１１０は、周期的ビーコンに応答する。ＡＰ３３０は、応答を受信すると、それ自体をその移動車両に対する次ホップ又は転送ノードとして維持する。一方、ＡＰ３３０は、応答を受信しない場合、ＲＳＵ１００に対し、移動車両がＡＰの無線範囲外に移動したことを通知する。ＲＳＵ１００は、その次ホップ情報及び転送ノード情報をその車両に関して更新する。
【００６１】
別の実施形態では、移動車両１１０は、ＲＳＵ１００に格納されている次ホップ情報及び転送ノード情報を積極的に変更する。この実施形態では、移動車両１１０は、受信したＳＮＲ値に基づいて、いずれのＡＰ３３０が次ホップ又は転送ノードであるべきかを判断する。移動車両は、この判断を、２つの別個の基準に基づいて行うことができる。一実施形態では、移動車両は、受信信号のＳＮＲを所定閾値と比較することができる。ＳＮＲが閾値を上回る場合、移動車両１１０は、チャネルがもはや利用可能でないと宣言し、次ホップ又は転送ノード２４１０として異なるＡＰ３３０を選出する。代替的に、移動車両１００は、移動車両の無線範囲内のすべてのＡＰ３３０から受信された信号強度の比較に基づいて、最強のチャネル、すなわち隣接するＡＰ３３０からの信号を選択することができる。移動車両１１０は、次ホップ情報及び転送ノード情報を更新するメッセージを新たなＡＰ３３０に送信する。新たなＡＰ３３０は、ＲＳＵ１００に対して移動度を通知し、それにより、ＲＳＵ１００に記録されている情報を変更することができる。移動車両１１０の移動により、ＡＰ３３０間にハンドオフがもたらされる。しかしながら、移動車両は、依然として同じＲＳＵ１００の無線範囲内にある。言い換えれば、このアーキテクチャでは、ハンドオフはＩＰ層下で実行され、ＭＡＣアドレス等のＭＡＣ情報のみが更新される。
【００６２】
たとえば、移動車両４ １１０_４がＡＰ５ ３３０_５からＡＰ４ ３３０_４まで移動する場合、ＡＰ４ ３３０_４は、車両４ １１０_４に対する新たなＭＡＣプロキシとなり、そのプロキシ状態をＲＳＵ１ １００_１に通知する。その後、ＲＳＵ１ １００_１は、ＡＰ４ ３３０_４に、車両４ １１０_４に向けられたメッセージを転送する。１つのＲＳＵ１００下でのＡＰ３３０間のハンドオフは、いかなるＩＰ層動作も必要としないため、ＩＰ層ハンドオフは、それほど頻繁には発生せず、移動車両１１０が１つのＲＳＵ１００から別のＲＳＵ１００に移動する時にのみ発生する。
【００６３】
図３Ｃは、複数のＲＳＵ１００が、ブロードキャストバスベースの複数のアクセスポイントを使用するルーティング機能を有する、アドホックネットワークを示す。図示するように、ＲＳＵ１ １００_１は５つのＡＰ（まとめてＡＰ３３０）を制御する。ＲＳＵ２ １００_２もまた、５つのＡＰ（まとめてＡＰ３３０）を制御する。図３Ｂに示すようなスイッチ３２０の代りに、図３Ｃに示すアーキテクチャでは、ブリッジバス３４０がＲＳＵ１００とそのＡＰ３３０とを接続する。スイッチベースの上記のアーキテクチャ（図３Ｂ）とは異なり、ＲＳＵ１００によって移動車両１１０に向けて送信されるメッセージは、ＲＳＵ１００下のすべてのＡＰ３３０に配信される。しかしながら、ブリッジバス３４０を使用することにより、宛先、すなわち移動車両１１０に関連するＡＰ３３０のみが、移動車両１１０にメッセージを転送する。
【００６４】
この構成は、ユニキャストルーティング、マルチキャストルーティング及び移動度検出をサポートするが、ＲＳＵは、これらの特徴のいずれを制御、維持又は管理するためにも使用されない。実施形態の利点は、ＲＳＵ１ １００_１がＡＰの車両とのいかなる関係に関する情報も維持する必要がない、ということである。転送動作はブリッジバス３４０を使用して簡略化される。それは、ブリッジバス３４０が次ホップ情報及び転送ノード情報
を維持するためのオーバーヘッドを最小限にするためである。しかしながら、ＡＰ３３０におけるオーバーヘッドは増大し、ＡＰ３３０は不要なトラフィックに直面する。
【００６５】
ユニキャスト動作では、１つの移動車両１１０に向けられるメッセージが、ＲＳＵ１ １００_１制御下のすべてのＡＰに転送される。ＲＳＵ１００は、移動車両のＭＡＣアドレスのみを直接接続として記録し、たとえば次ホップ情報又は転送ノード情報は記録しない。宛先車両に対するＭＡＣアドレスを有するＡＰ３３０のみが、メッセージを転送する。たとえば、メッセージが車両４ １１０_４に向けられている場合、ＲＳＵ１ １００_１はメッセージをすべてのＡＰ３３０に転送するが、ＡＰ５ ３３０_５のみが移動車両４ １１０_４にメッセージを転送することができる。
【００６６】
同様に、図３Ｂに関して上述したマルチキャスト動作では、マルチキャストグループ２４００に参加した車両に関連付けられるＡＰ３３０のみが、マルチキャストグループ２４００の転送ノード２４１０となる。しかしながら、図３Ｂにおいて説明した構成とは異なり、転送ＡＰのみでなく他のＡＰ（すなわち、これらのＡＰ下にマルチキャストメンバシップを有する車両がない）も、マルチキャストパケットを受信する。ＲＳＵ１００は、転送ノードに関するいかなる情報も記録しない。たとえば、マルチキャストメッセージは、移動車両２ １１０_２及び車両４ １１０_４に向けられており、車両２ １１０_２及び車両４ １１０_４はマルチキャストグループ２４００に参加している。ＲＳＵ１ １００_１はメッセージをＡＰ１ ３３０_１〜ＡＰ５ ３３０_５にルーティングする。しかしながら、ＡＰ３ ３３０_３及びＡＰ５ ３３０_５のみが、メッセージをそれぞれ車両２ １１０_２及び車両４ １１０_４に転送する。
【００６７】
移動度検出の場合、スイッチ３２０の代りにブリッジバス３４０を使用することにより、検出がより迅速になるという利点がある。これは、ＲＳＵ１００が検出プロセスに関与せず、且つ通知もされないためである。したがって、ＡＰ３３０とＲＳＵ１００との間のメッセージが回避される。ハンドオフは、移動車両と関連ＡＰとの間で完了する。移動度検出は、上述したものと同様に実行されるが、ＡＰ３３０のＭＡＣアドレスキャッシュのみが更新される。
【００６８】
上述した実施形態では、ＲＳＵ１００が互いから分離して配置されている場合を説明したが、本発明の別の実施形態では、ＲＳＵ１００を互いの無線範囲内に配置することができる。この実施形態では、ＲＳＵ１００が互いにリンクされることにより、ＲＳＵネットワークを形成する。リンクされたＲＳＵネットワークは、密度が高くても低くてもよい。これらのＲＳＵ１００は、互いの間に通信リンクを有し、他のＲＳＵ１００との連携を通じてＲＳＵ範囲外の機能を提供する。ＲＳＵ１００は、相互接続されている場合、情報のすべてを共有することができる。移動車両１１０は、通過するＲＳＵ１００のそれぞれに対して複製情報を送信する必要はない。互いにリンクされたＲＳＵ１００は、位置情報、ＩＰ及びＭＡＣチャネル情報を交換することにより、隣接するＲＳＵ１００への接続を移動車両が事前設定するのを支援することができる。さらに、リンクされたＲＳＵ１００を使用して、事故情報等のパケットを１つのエリアから別のエリアにルーティングすることができる。しかしながら、リンクされたＲＳＵ１００には、ＭＡＣチャネル干渉というトレードオフがある。ＲＳＵ１００がまばらに存在している場合、ＭＡＣチャネル干渉は最小であり、いかなるＲＳＵにも同じＶ−Ｒチャネルを使用することができる。しかしながら、所与のエリア内にＲＳＵ１００が密集している場合、Ｖ−Ｒチャネルに対しチャネル割当てが必要なＭＡＣチャネル干渉がある可能性がある。
【００６９】
図４は、まばらで互いにリンクされたＲＳＵ１００を含むアドホックネットワークの一例を示す。ＲＳＵ１ １００_１及びＲＳＵ２ １００_２は、互いに無線または有線でリンク４００されている。したがって、２つのＲＳＵ１００_１及び１００_２は情報を共有する
ことができる。２つのＲＳＵ１００_１及び１００_２はエリア内にまばらに存在しているため、同じＶ−Ｒチャネルを使用することができる。さらに、２つのＲＳＵ１００_１及び１００_２に対する無線範囲すなわち有効範囲を、干渉を考慮せずに広いエリアをカバーするように選択することができる。この構成は、通常、地方または人口密度の低いエリアで使用される。
【００７０】
図５は、密集しており相互接続されているＲＳＵ１００を含むアドホックネットワークを示す。図５に示すように、楕円形線は、各ＲＳＵ１００の無線範囲を表している。各ＲＳＵ１００の無線範囲は、まばらなＲＳＵの例より小さいように選択され、より少ない移動車両１１０を同時に処理するように設計されている。しかしながら、この設計により、各ＲＳＵ１００との車両の接続時間が短くなり、チャネル競合がもたらされ、ハンドオフが頻繁になり、アドレス割当ておよび認証の時間がほとんどなくなる。ハンドオフは数秒毎に発生しなければならなくなり、それにより移動車両１１０は、新たなアドレス、新たな接続を確立し、ハンドオフ毎にセキュリティメカニズムを経ることになる。
【００７１】
これらの問題を回避するために、ＲＳＵグループが形成される。ＲＳＵグループは、２つ以上のＲＳＵ１００から形成される。図６は、複数のＲＳＵグループ６００_１〜６００_３をそれぞれ示している。移動車両１１０は、ＲＳＵ１００を個々に扱うのではなく、ＲＳＵグループ６００_１〜６００_３を１つの機能単位として扱う。ＲＳＵグループ６００_１〜６００_３の動作のうちのいくつかは、チャネル予約及び調整、認証及びハンドオフハンドシェイクである。ダウンリンクの場合、データ損失を最小限にするために、ＲＳＵグループ６００又はサブグループにより同じダウンリンクストリームを送信することができる。いくつかのＲＳＵ１００を含む同じセットの構成パラメータが、ＲＳＵグループ６００を形成する隣接するＲＳＵに対して使用される。これにより、ハンドオフ及び構成変更が続くことを回避できる。移動車両１１０は、ＲＳＵグループ、たとえば６００_１に入ると、チャネル予約、認証及びハンドシェイクを一度だけ実行する。
【００７２】
ＲＳＵグループは、Ｖ−Ｒ及びＶ−バックボーン通信並びに緊急通信に使用される。また、ＲＳＵグループを使用して、ローカルピアグループ（ＬＰＧ）の形成、その追跡、調整及び最適化を支援することができる。
【００７３】
上述したように、移動車両１１０は、ＲＳＵ１００又はＲＳＵグループ６００_１〜６００_３に入ると、ＲＳＵ１００又はＲＳＵグループ６００_１〜６００_３にチャネル予約要求を送信する。ＲＳＵグループ、すなわち６００_１内の第１のＲＳＵ１００は、入ってくる移動車両に対してチャネル及びタイムスロットを割り当てる。この割当ては、Ｖ−Ｒ通信に使用される。チャネルは、いかなる干渉も回避するように複数のチャネルから選択される。各移動車両１１０には、ＲＳＵグループ６００が利用可能な特定のサブチャネルが割り当てられる。
【００７４】
チャネルアクセスには、２つの方式、すなわち同期アクセス及び非同期アクセスがあり得る。一実施形態では、同期アクセスが使用される。各移動車両１１０には、サブチャネル内の固定サイズのタイムスロットが割り当てられる。たとえば、１つの車両はチャネル４、タイムスロット２に割り当てられ、第２の車両はチャネル４、タイムスロット５に割り当てられる。車両は、それ自体の順番が来た時にしか通信せず、それ以外は通信しない（silent）状態にある。タイムスロット内では、帯域幅の一部がアップリンク通信に予約され、残りはダウンリンクに予約される。この方式により、各移動車両１１０は、電波に対して等しくアクセスする。同期アクセスの使用の利点は、競合解決に時間が浪費されないということである。隣接するＲＳＵグループは重ならないチャネルを使用するため、「隠れ端末」問題もまた存在しない。
【００７５】
別の実施形態では、非同期方式が使用される。各移動車両１１０はサブチャネルに割り当てられる。サブチャネル内の移動車両１１０は、競合解決、たとえばＣＳＭＡ方式を使用してチャネルアクセスに関して競合する。この方式はランダムアクセスに基づく。
【００７６】
図７は、複数のＲＳＵグループ６００に対するチャネル割当てを示す。ネットワークプロバイダ又はＲＳＵグループ管理エンティティが、ＲＳＵグループ６００へのチャネル割当てを実行することができる。図７に示すように、ＲＳＵグループ１ ６００_１にはチャネル１〜３が割り当てられ、ＲＳＵグループ２ ６００_２にはチャネル４〜６が割り当てられ、ＲＳＵグループ３ ６００_３にはチャネル１〜３が割り当てられている。隣接するＲＳＵグループ６００は異なるサブチャネルを使用するため、ＲＳＵグループ６００内の移動車両１１０は、別のＲＳＵグループ６００の車両に対する隠れ端末になることはできない。ＲＳＵグループ１ ６００_１及びＲＳＵグループ３ ６００_３には、それらの相対的な位置により、同じチャネルを割り当てることができる。ＲＳＵグループ１ ６００_１及びＲＳＵグループ３ ６００_３によってチャネル干渉はもたらされない。ＲＳＵグループ６００内では、各移動車両１１０はサブチャネル（チャネル）と共にタイムスロットに割り当てられている。これにより、常に１つの移動車両１１０のみに送信されることが確実になる。たとえば、図７において、第１の車両にはチャネル２、タイムスロット４が割り当てられており、第２の車両にはチャネル２、タイムスロット１が割り当てられている。
【００７７】
図８は、ＲＳＵ１００がアプリケーション／情報サーバとしてのみ作用するアドホックネットワークを示す。このアドホックネットワークは、ＲＳＵ１００と、バックボーン２００、たとえばインターネットと、移動車両１１０とを含む。ＲＳＵ１００は、４つのネットワーク階層、すなわちネットワーク層２１０、ＭＡＣ層２１５、物理層２２０及びアプリケーション層８００を含む。バックボーン２００は少なくとも１つのルータを含む。
【００７８】
この構成では、ＲＳＵ１００はいかなるルーティング機能も有しない。ＲＳＵ１００は、パブリックドメインのエンドホストとして機能する。ＲＳＵ１００は、アプリケーションサーバ、情報記憶デバイス、又はたとえば地方公告、リアルタイム交通管理若しくは地図更新等のサービスプロバイダである。各移動車両１１０には、ＲＳＵ１００によりプライベートＩＰアドレスが割り当てられ、各移動車両１１０はＲＳＵ１００を使用してバックボーン２００にアクセスすることができる。ＲＳＵ１００は、プライベートＩＰのネットワークアクセス変換（Network Access Translation）を提供することにより、バックボーン２００へのアクセスを提供する。ＲＳＵ１００は、アプリケーションサーバとしてのみ作用する場合、移動車両１１０の移動度をサポートしたり検出したりできない。
【００７９】
図９は、ＲＳＵ１００がアプリケーション／情報サーバ及びルータの両方として機能するアドホックネットワークを示す。このアドホックネットワークは、ＲＳＵ１００と、バックボーン２００、たとえばインターネットと、移動車両１１０とを含む。ＲＳＵ１００は、４つのネットワーク階層、すなわちネットワーク層２１０、ＭＡＣ層２１５、物理層２２０及びアプリケーション層８００と共に、ＲＳＵ１００と同じ場所に配置されているルータを含む。
【００８０】
このアーキテクチャには、ＮＡＴすなわちプライベートＩＰアドレスの割当ては不要である。車両にはパブリックＩＰアドレスを割り当てることができ、それによりインターネットへのアクセスが容易になる。このアーキテクチャに必要なＲＳＵ１００は、ルータ及びアプリケーションサーバの両方として機能するため、十分な計算能力を有する。ＲＳＵ１００を、リモートＡＰ３３０とともに使用してもよく、又はリモートＡＰ３３０なしで使用してもよい。
【００８１】
図１０は、ＲＳＵ１００がルータ及びアプリケーションサーバの両方として機能しているアドホックネットワークの一例を示す。図１０に示すように、ＲＳＵ１ １００_１及びＲＳＵ２ １００_２はそれぞれ、バックボーン２００のルータ１０１０及び１０２０にアクセスすることができる。ＲＳＵ１ １００_１及びＲＳＵ２ １００_２は、ルータ１０３０及びアプリケーションサービス１０４０から構成されている。さらに、ネットワークは、ＲＳＵ１ １００_１に対するリモートＡＰ１ ３３０_１〜ＡＰ５ ３３０_５及びＲＳＵ２ １００_２に対するＡＰ６ ３３０_６〜ＡＰ１０ ３３０_１０を含む。図１０は、図３Ｂ及び図３Ｃに類似しているが、ＲＳＵ１００は、図示されているルーティング機能のみではなく、ルータ機能及びアプリケーション機能を有する。さらに、図１０に示す構成は、ハブがスイッチ３２０（図３Ｂに示すように）であってもよく、又はブリッジバス３４０（図３Ｃに示すように）であってもよいことを示している。スイッチ３２０又はブリッジバス３４０のいずれかの選択は、いくつかの設計因子、たとえば、遅延時間性能及び設備稼働率等のシステム工学設計パラメータ及びコスト又はサポートされるべきサービス等のシステム要件によって決まる。
【００８２】
別の実施形態では、図４〜図７に示すアーキテクチャを、ＲＳＵ１００にアプリケーションサービス１０４０を追加することによって、ＲＳＵ１００に対しアプリケーションサーバ及びルータの機能を含むように変更することができる。
【００８３】
本発明の一実施形態では、ＲＳＵ１００は、ＬＰＧ１１５内のノードであり得る。ＬＰＧ１１５の目的は、隣接するノード間の連携の程度（degrees of coordination）を構築することである。これらの隣接するノードは、無線通信能力を有する移動デバイスか又は固定ノードである。移動無線デバイス又はノードは、ＰＤＡ、ラップトップ、携帯電話、もしくは無線デバイスが取り付けられるか又は内蔵されている移動車両であってもよい。好ましい実施形態では、移動無線デバイスは、関連付けられる通信デバイスが内部に設置されているか又は独立して持ち込まれる移動車両１１０、及び通信デバイスを携帯している歩行者である。本明細書における無線デバイスは、まとめて任意のノード又は移動車両１１０と呼ばれる。１つのローカルピアグループを編成している、直近のノード間での通信にはＬＰＧ内通信が使用される。近隣のノード間、すなわち隣接する異なるローカルピアグループに属するノード間での通信にはＬＰＧ間通信が使用される。
【００８４】
いくつかのタイプのＬＰＧ１１５、すなわち固定（stationary）ＬＰＧ、動的（dynamic）ＬＰＧ及びハイブリッドＬＰＧがある。固定ＬＰＧは、特定の位置又はエリアにより画定され、すなわち、ノードは、たとえばエリアＡを画定するエリアにある場合、ＬＰＧ
Ａに所属する。ノードは、異なるエリア、たとえばエリアＢにある場合、ＬＰＧ Ｂに所属し、他も同様である。固定ＬＰＧの詳細なサイズは、さまざまな要素、たとえば無線アンテナの範囲、通信範囲、移動デバイスの数、土地の地形、環境状態、交通パターン及び人口密度に依存する、設計上の選択である。固定ＬＰＧの位置及びサイズは固定である。しかしながら、場所が異なると交通パターン及び人口（移動車両１１０）密度が異なるため、各固定ＬＰＧのサイズが異なってもよい。ＲＳＵ１００が所定のＬＰＧ１１５内にある場合、そのＲＳＵ１００の無線範囲によって、固定ＬＰＧのサイズが画定される。
【００８５】
ＲＳＵ１００を使用することにより、移動車両１１０は、ＲＳＵ１００からのハートビート制御パケット１７００か又はＡＰ３３０からのビーコンをヒアリングすることにより、固定ＬＰＧの位置を検出することができる。移動車両１１０は、位置を変更する際に固定ＬＰＧを変更する。代替的に、移動車両は、ＬＰＧ１１５及びそれらの位置のデータベースを有している。別の実施形態では、所与のエリア内に複数のＲＳＵ１００がある場合、少なくとも１つのＲＳＵ１００が隣接する他のＲＳＵ１００の相対位置又は位置に関する情報を提供することにより、移動車両１００が迅速にＬＰＧ１１５の位置を特定することができるようにして、複数のＬＰＧ１１５間のハンドオフを容易にすることができる。
【００８６】
固定ＬＰＧは、いくつかのＬＰＧ１１５が空であるか、又はＬＰＧ１１５内に多くの移動車両１１０がない場合であっても、バックボーンアクセス又はＬＰＧ間通信を提供するように無線インフラストラクチャとの統合をサポートするという、重要な利点を有している。各固定ＬＰＧには、通信を容易にするように一意の識別子が割り当てられている。すべての固定ＬＰＧエリアが適切に画定されているため、ＬＰＧ１１５の形成及び命名は動的ＬＰＧより容易である。さらに、固定ＬＰＧを使用する場合、ＬＰＧ１１５の併合及び分割に関する規則は問題ではない。
【００８７】
第２のタイプのＬＰＧ１１５は動的ＬＰＧである。固定ＬＰＧとは反対に、動的ＬＰＧは、隣接するノードの無線有効範囲に基づいて形成され、それにより、ノードは、他のノードの正確な位置を考慮することなく通信を調整することができる。
【００８８】
動的ＬＰＧは無線有効範囲に基づいて形成されるため、ＬＰＧ１１５内の移動車両１１０は、常に、シングルホップ又はマルチホップ伝送を介して互いに且つＲＳＵ１００と通信することができる。ＬＰＧ１１５内の１つのノードは、通信を低遅延で効率よく実行することができるように、各ＬＰＧ１１５内のノードの数、又は代替的にこのノードから動的ＬＰＧの端までの無線ホップの数を適度に少なく維持するために、動的ＬＰＧのサイズを制御することができる。このノードを、後に詳細に説明するようにグループヘッダ（ＧＨ）と呼ぶ。さらに、固定ＬＰＧとは対照的に、動的ＬＰＧは、各ＬＰＧ１１５内で通信が常に可能であることを確実にする。動的ＬＰＧでは、固定ＬＰＧとは異なり、ＬＰＧ１１５を、ＲＳＵ１００無線範囲外に形成することができる。
【００８９】
一実施形態では、１つ又は複数の固定ＬＰＧもしくは１つ又は複数の動的ＬＰＧから、アドホックピア・ツー・ピアネットワークを作成することができる。別の実施形態では、アドホックピア・ツー・ピアネットワークを、ハイブリッドＬＰＧネットワークとして固定ＬＰＧ及び動的ＬＰＧの両方から作成することができる。ハイブリッドＬＰＧネットワークは、固定ＬＰＧ及び動的ＬＰＧの利点を組み合わせながら、それぞれを別個に採用した場合にもたらされる問題を取り除く。
【００９０】
ハイブリッド手法は、道路地形を利用する。特に、インフラストラクチャが利用可能でない場合、動的ＬＰＧを使用してネットワークを形成する。いくつかのエリアにおいてインフラストラクチャが利用可能となると、固定ＬＰＧを使用して、動的ＬＰＧ及びインフラストラクチャとのネットワークを形成することができる。たとえば、道路インフラストラクチャ等のインフラストラクチャは、路車間通信又は道路支援通信を可能とする。
【００９１】
一実施形態では、ＲＳＵ１００は、ＬＰＧ１１５内のノードであってもよく、移動車両１１０と同様のネットワーク機能を実行することができる。ＲＳＵ１００は、グループヘッダ（ＧＨ）１３００ノード又はグループノード（ＧＮ）１５００のいずれかとしてＬＰＧ１１５に参加することができる。ＧＨ１３００は、ノードのいかなる順序付け又はいかなるインフラストラクチャもなしにＬＰＧ１１５を維持し制御するように指定される、ＬＰＧ１１５内の移動デバイス又はノードである。通常、ＬＰＧ１１５内にはＧＨ１３００は１つしかない。ＬＰＧ１１５内の他のすべてのノードは、一般的なノードすなわちグループノード（「ＧＮ」）１５００である。ＧＮ１５００は、ＧＨ１３００を通じてＬＰＧ１１５に参加する。
【００９２】
各ＲＳＵ１００は、上述したようなルータ及びアプリケーションサーバに加えて、ＧＨ１３００又はＧＮ１５００として動作することができる。したがって、各ＲＳＵ１００は、ノードがそれぞれＧＨ１３００又はＧＮ１５００として機能するか又は動作するのを可能にする、要素又は手段及びネットワーキングプロトコルを有している。したがって、Ｒ
ＳＵ１００がＧＨ１３００又はＧＮ１５００のいずれかとして動作する場合であっても、ＧＨ１３００及びＧＮ１５００の両方に対し構造的要素又は手段のすべてが存在するが、特定の要素のみが動作のモードに基づいて機能する。したがって、ＲＳＵ１００は、ＧＨ１３００又はＧＮ１５００の機能を提供するハードウェア及びソフトウェアの両方を有している。
【００９３】
図１１は、ＲＳＵ１００の基本要素のブロック図を示す。ＲＳＵは、メモリセクション１１００、クロック１１０５、タイマ１１１０、送受信セクション１１２０、制御手段１１２５及び電源１１３０を含む。メモリセクション１１００は、ＤＲＡＭ、ＳＲＡＭ又はフラッシュを含むいかなるタイプのメモリであってもよい。好ましい実施形態では、短期メモリはキャッシュである。メモリセクション１１００は、ＧＩＤ１７０５、グループヘッダＩＤ１７１０、グループリスト、所定最大ＬＰＧサイズ、ＬＰＧにおけるノードの数及び他のタイプの制御パラメータ等、ＬＰＧに関する情報を格納する。
【００９４】
ＲＳＵ１００のタイミングの維持にクロック１１０５が使用される。特に、クロック１１０５は、内部クロックとして機能し、タイマ１１１０を設定するための基準として使用される。タイマ１１１０は、さまざまなメッセージをいつブロードキャストすべきかを判定するために使用され、すなわち、ＧＨ１３００の場合のハートビート間隔（Ｔ）又はＧＮ１５００の場合の応答メッセージを判定する。制御手段１１２５又はマイクロプロセッサは、メッセージの生成、ルーティング及びタイマを含む、ＲＳＵ１００のプロセスのすべてを制御する。さらに、制御手段１１２５はまた、後に詳細に説明するヘッダ解決にも関与している。送受信セクション１１２０は制御手段１１２５と協働して、メモリセクション１１００に格納されているデータからメッセージを作成又は生成する役割を果たす。
【００９５】
ＲＳＵ１００は、ビーコン又はハートビート制御パケット１７００を、ＲＳＵの無線範囲内のすべての移動車両１１０及び他のＲＳＵに定期的に送信する。この期間は固定間隔である。ハートビート間隔（Ｔ）の値は、設計又は動作の必要に基づいて選択可能である。
【００９６】
ＬＰＧ１１５がＲＳＵ１００の近くまで移動すると、ヘッダ解決プロトコルに基づいてＧＨ１３００が選出される。ＬＰＧ１１５のＧＨ１３００である移動車両は、Ｖ−Ｖチャネル及びＶ−Ｒチャネルの両方にハートビート制御パケット１７００を送出する。同様にＧＨ１３００として機能するＲＳＵ１００は、そのハートビートをＶ−Ｒチャネルにのみ送出する。２つ以上のＧＨ１３００、たとえばＬＰＧ１１５からのＧＨ１３００及びＲＳＵ１００がハートビート制御パケット１７００を送信すると、ヘッダ解決が発生する。これは、同じＬＰＧ１１５内に複数のＧＨ１３００があるのを回避するためであり、それは、同じＬＰＧ１１５に複数のＧＨ１３００があると、冗長な（混乱させる可能性さえある）制御信号がＬＰＧ１１５内で送信されるか又はブロードキャストされ、帯域幅及び容量を浪費することになるためである。ヘッダ解決は、少なくとも２つのＧＨから１つのＧＨ１３００を選択するように機能する。
【００９７】
図１２は、ヘッダ解決方法を示す。ステップ１２００において、ＬＰＧ１１５のＧＨ１３００及びＲＳＵ１００が共に、互いのハートビート制御パケット１７００を受信すると、ヘッダ解決メッセージを生成する。これは、ＲＳＵ１００及び任意のＧＨ１３００に対し、ヘッダ解決モードで動作するように通知する。ステップ１２１０のように、所定選択基準に基づいて新たなＧＨが選択される。好ましい実施形態では、ＲＳＵ１００が、新たなＧＨとして選択される。そして、ステップ１２２０において、ＲＳＵ１００は、新たなハートビート制御パケット１７００を無線範囲内の任意のノードに送信し、ＲＳＵ１００がＧＨ１３００であることを示す。ハートビート制御パケット１７００が、Ｖ−Ｒチャネルを介して再び送信される。ステップ１２３０において、他のノードが、ＲＳＵ１００を
介してＬＰＧ１１５に参加する。
【００９８】
図１３は、移動車両１１０のみを含む動的ＬＰＧがＲＳＵ１００に近接するように移動した時のＲＳＵ１００を含むＬＰＧ１１５の形成を示す。動的ＬＰＧの場合、ＬＰＧ１１５を、ＲＳＵ１００サービスエリア１３１０外で形成することができる。最初は、少なくとも１つの移動車両１１０からＧＨ１３００が選択される。ＬＰＧ１１５がＲＳＵ無線範囲内に移動すると、ＲＳＵ１００はＬＰＧ１１５に参加する。ＲＳＵ１００は最初に、ＧＨ１３００として機能し、ハートビート制御パケット１７００を送出する。ＲＳＵ１００とＧＨＡ１３００_Ａとの間にヘッダ解決が発生する。好ましい実施形態では、ＲＳＵ１００がＧＨＡ１３００_Ａを超える優先権を有し、ＬＰＧ１１５に対して唯一のＧＨ１３００となる。
【００９９】
ＬＰＧ１１５が、複数のＲＳＵ１００、たとえばリンクされたＲＳＵ１００又はＲＳＵグループ６００に近接するように移動すると、１つのＲＳＵ１００のみがＧＨ１３００になる。他のＲＳＵはＧＮ１５００になる。再びヘッダ解決が発生し、ＲＳＵ ＧＨの選択は、所定の優先権に基づいてもよく、又はＲＳＵ ＩＰアドレスの何らかのハッシュ関数によってもよく、又はＧＨ１３００の年功によってもよい（たとえば、ＧＨの古さ（age）が比較され、最も古いＧＨが勝ちＧＨとして選択される）。
【０１００】
２つ以上のＬＰＧ１１５内に１つのＲＳＵ１００があってもよい。通常、各ＬＰＧ１１５は、その中に、ＧＨ１３００として機能している１つのＲＳＵ１００を有することができる。１つのＲＳＵ１００が、その有効範囲内の複数のＬＰＧ１１５に対するＧＨ１３００となることも可能である。同じＬＰＧ１１５内の他のＲＳＵがＧＮ１５００になることが可能である。
【０１０１】
一実施形態では、同じＧＨ１３００、すなわちＲＳＵ１００を有する複数のＬＰＧ１１５が、同じＲＳＵ１００を有する別個のＬＰＧとして維持されることができる。代替的に、複数のＬＰＧが互いに併合して１つのより大きいＬＰＧ１１５を形成することができる。ＬＰＧ１１５のサイズが最大サイズ限度を超えると、ＬＰＧは２つの別個のＬＰＧに分かれる。
【０１０２】
固定ＬＰＧの場合、ＬＰＧ１１５は、ＲＳＵ１００の無線範囲外に存在しない。したがって、ＬＰＧはＲＳＵの位置によって画定される。移動車両は、ＲＳＵ１００を介してＧＮとしてＬＰＧに参加する。ＲＳＵ１００は、自動的にＧＨとなる。ＲＳＵ ＧＨは事前に既知であるか、他のＲＳＵ１１０を通じて発見されるか、又はＲＳＵ ＧＨハートビート制御パケット１７００を受信することによって発見される。固定ＬＰＧの場合、移動車両１１０自体はＬＰＧを形成せず、したがってＲＳＵ無線範囲外にＧＨがないため、ＲＳＵ１００と移動車両との間にヘッダ解決は不要である。
【０１０３】
図１４は、２つの固定ＬＰＧ１１５の形成を示す。図示するように、ＲＳＵ１ １００_１及びＲＳＵ１ １００_２はそれぞれ所定の無線範囲を有している。移動車両１及び２（１１０_１及び１１０_２）は、無線範囲内に移動すると、ＲＳＵ１ １００_１を介してＬＰＧ１ １１５_１に参加する。同様に、移動車両３ １１０_３は、ＲＳＵ２ １００_２を介してＬＰＧ２ １１５_２に参加する。車両ＢＮ１４００は、複数のＲＳＵ１００_１及び１００_２をヒアリングすることができ、２つのＬＰＧの間の境界ノード（Boundary Node）になる。境界ノードは、ＬＰＧ間中継ポイントとして機能する。この場合、車両ＢＮ１４００は、いずれのＬＰＧ（ＬＰＧ１ １１５_１及び１１５_２）に参加すべきかを選択することができる。
【０１０４】
ハイブリッドＬＰＧの場合、ＲＳＵ１００は固定ＬＰＧ位置の境界を画定する。ＲＳＵ
１００の位置が既知であり、したがって、固定ＬＰＧの位置が既知である。移動車両１１０は、固定ＬＰＧエリア外になると、移動車両１１０であるＧＨ１３００を有する動的ＬＰＧを形成する。動的ＬＰＧ内の１つ又は複数のノードがＲＳＵ１００と接触すると、ＬＰＧ全体が、ＧＨ１３００としてＲＳＵ１００を含む固定ＬＰＧに参加し、好ましい実施形態ではＧＮ１５００となる。
【０１０５】
一実施形態では、動的ＬＰＧメンバ間のＶ−Ｖチャネルを使用して、ＬＰＧ内通信が発生する。ＬＰＧ間通信は、Ｖ−Ｒチャネル及びＶ−Ｖチャネルを使用して、異なる動的ＬＰＧのメンバとＲＳＵ１００との間で発生する。
【０１０６】
別の実施形態では、ＲＳＵ１００は、ＧＮ１５００としてＬＰＧ１１５に参加することができる。この実施形態では、移動車両ＧＨ１３００とＲＳＵ１００との間のヘッダ解決により、車両ＧＨ１３００がＬＰＧ１１５に対する新たなＧＨとして選択されることとなる。
【０１０７】
図１５は、移動車両１１０のみを含む動的ＬＰＧがＲＳＵ１００に近接するように移動する場合のＲＳＵ１００を含むＬＰＧ１ １１５_１の形成を示す。最初に、少なくとも１つの移動車両１１０からＧＨ１３００が選択される。図１５に示すように、ＧＨ１３００はＧＨＡ１３００_Ａである。ＬＰＧ１１５がＲＳＵ無線範囲内に移動すると、ＲＳＵ１００はＬＰＧ１１５に参加してＬＰＧ１ １００_１を形成する。ＧＨＡ１３００_Ａは、最初にＧＨ１３００として機能し、ハートビート制御パケット１７００を送出する。ＲＳＵ１００とＧＨＡ１３００_Ａとの間でヘッダ解決が発生する。この実施形態によれば、ＧＨＡ１３００_Ａが、ＲＳＵ１００を超える優先権を有し、ＬＰＧ１ １１５_１に対する唯一のＧＨ１３００となる。図１５の破線は、新たなＬＰＧを表している。ＲＳＵ１００はＲＳＵ ＧＮ１５００としてＬＰＧ１ １１５_１に参加する。
【０１０８】
ＬＰＧ１ １１５_１が他のＲＳＵ１００と接触すると、すべてのＲＳＵ１００がＬＰＧ１ １１５_１のＧＮ１５００となる。ＬＰＧ１１５の最大サイズに達すると、ＬＰＧは２つ以上のＬＰＧに分かれる。固定ＬＰＧの場合、ＬＰＧはＲＳＵ１００の無線範囲外に存在しない。したがって、ＬＰＧ１１５は、ＲＳＵ位置によって画定される。移動車両１１０は、ＧＨ１３００としてＬＰＧ１１５に参加する。ＲＳＵ１００は、ＬＰＧ１１５内でＧＮ１５００となる。ＲＳＵ ＧＨは、事前に既知であるか、他のＲＳＵ１００を通じて発見されるか、又はＲＳＵ ＧＨハートビート制御パケット１７００が受信されることによって発見される。固定ＬＰＧでは、ＲＳＵ１００と移動車両１１０との間でヘッダ解決は不要である。
【０１０９】
図１６は、ＲＳＵ１００がＧＮ１５００となる２つの固定ＬＰＧ１１５の形成を示す。図示するように、ＲＳＵ１ １００_１及びＲＳＵ２ １００_２はそれぞれ、所定の無線範囲を有している。ＧＨ１３００のみが、ハートビート制御パケット１７００を定期的に送出して、ＬＰＧ１１５の形成を維持する。ＧＮ１５００は、次のハートビート制御パケット１７００を待つようにタイマをセットする。この場合、移動車両ＧＨ１３００が、ハートビート制御パケット１７００を定期的に送出する。各ＲＳＵ１００（ＧＮとして機能する）は、ハートビート制御パケット１７００を受信する（すなわち、ＧＨの無線範囲内になる）と、次のハートビート制御パケット１７００を待つようにタイマをセットする。ハートビート制御パケット１７００がＨＢ期間内に受信されない場合、ＧＮ１５００のうちの１つが、ＬＰＧ１１５に対するＧＨ機能を引き継ぐ。局所的な周辺に２つ以上のＧＨ１３００がある場合、ＧＨは、同じＬＰＧ１１５に対するものであるが自身が発したのではないハートビート制御パケット１７００をヒアリングする。この場合、１つのＧＨ１３００のみが、局所的な周辺にＬＰＧ１１５を維持するために選択されるべきである。競合するＧＨ間でヘッダ解決手続きが使用されて、勝ちのＧＨが選択される。
【０１１０】
形成後、ＧＨ１３００（移動車両）は、Ｖ−Ｖチャネル及びＶ−Ｒチャネル上にハートビート制御パケット１７００を送出する。すべてのＧＮ１５００が、Ｖ−Ｖチャネル及びＶ−Ｒチャネル上でハートビート制御パケット１７００を転送する。ハートビート制御パケット１７００がヒアリングされると、ノードは、移動車両であってもＲＳＵ１００であっても、参加メッセージを介してＬＰＧ１１５に参加する。
【０１１１】
別の実施形態では、ＲＳＵ１００は、特別な中継ノード（ＲＹＮ）としてＬＰＧ１１５に参加することができる。ＲＳＵ１００は、ＧＨ１３００を介してＬＰＧに参加する。ＧＨ１３００は、特別なノードとしてメンバシップリストにＲＳＵ１００を追加する。ＲＹＮ、すなわち特別な中継ノードは、ＬＰＧ１１５内の車両に対して、バックアップ経路として、又は重複するストリーム若しくはマルチパスストリーム用の経路としてのみ使用される。この場合、ＲＹＮはＬＰＧ１１５の一部であるが、すべてのメッセージは中継せず、又はすべての形成若しくは編成制御メッセージに積極的には関与しない。したがって、ＬＰＧがＲＳＵ１００エリアを出入りする際、ＬＰＧ構造を維持することができる。ＲＹＮは、中継ノードとして使用されることが可能であること又はその意志があることを示す特別なステータスインジケータを有することができる。この特別なステータスインジケータを使用して、ＲＳＵ１００に対する負荷を制御し主なボトルネックを回避することができる。ＲＳＵ１００に対する負荷が高い場合、ボトルネックが発生する。ＲＳＵ１００に対する負荷が高い時、ＲＳＵ１００は、特別なステータスインジケータが、ＲＳＵ１００が中継ノードとなる意志がないことを示すようにする。したがって、ＲＳＵ１００又はＲＹＮは、ルーティングテーブル２３００に残ることができるが、常にアクティブであるとは限らない。一実施形態では、ＲＳＵ１００又はＲＹＮは、その無線有効範囲内のすべてのノードに対し特別なステータスインジケータを事前にブロードキャストすることができる。ノードは、ＲＳＵ１００又はＲＹＮのステータスを含むようにルーティングテーブル２３００を更新し、すなわち、ルーティングテーブル２３００は、ステータスに対する追加のエントリ、すなわちアクティブか否かを含む。
【０１１２】
本発明の別の実施形態では、ステータスインジケータは、いずれのタイプのパケットをＲＳＵ１００又はＲＹＮによってルーティングすることができるかを選択的に判定するパラメータを含むことができる。たとえば、ＲＳＵ１００は、マルチキャストパケットのみを中継することができ、ユニキャストパケットは中継することができなくてもよい。ＲＳＵ１００又はＲＹＮは、その無線有効範囲内のすべてのノードに対し、パケットタイプ情報と共にステータスインジケータを事前にブロードキャストすることができる。すべてのノードが、ＲＳＵ１００又はＲＹＮのパケットタイプ情報を含むようにルーティングテーブル２３００を更新し、すなわち、ルーティングテーブル２３００は、タイプに対する追加のエントリ、すなわちユニキャスト、マルチキャスト又はブロードキャストを含む。ノードは、ＲＳＵ１００であっても移動車両１１０であっても、ＧＨ１３００として機能していてもＧＮ１５００として機能していても、メッセージをルーティングするために使用することが可能である。ルーティングには主に２つのタイプ、ユニキャスト及びマルチキャストがある。
【０１１３】
＜ユニキャスト＞
ユニキャストルーティングプロトコルは、各ノード内でルーティングテーブル２３００を作成することに基づく。ルーティングテーブル２３００は、メッセージ又はパケットについての少なくとも宛先及び次ホップを少なくとも含む。ＬＰＧ１１５内のすべての移動車両１１０が、ルーティング機能を実行し、他の車両がシングルホップ又はマルチホップのいずれかで通信するのを支援する。ＬＰＧ内ルーティングテーブル２３００は、ＬＰＧ形成メッセージを使用して制御パケットをブロードキャストモードで交換することによって構成される。ユニキャストルーティングには追加の制御メッセージは不要である。ＬＰ
Ｇ１１５形成に使用される同じ制御パケットが、ルーティングプロトコルのためのルーティングテーブル２３００を作成し、維持し、更新するために使用される。ルーティングテーブル２３００は、ＬＰＧ内ルーティングに使用される。ＬＰＧ識別子がすべての制御パケットに埋め込まれることにより、不要なノードに外部制御パケットが伝播するのが防止される。外部制御パケットはすべて、終了するか又は中継されない。
【０１１４】
制御パケットメッセージは、ＧＨ１３００からのハートビート（ＨＢ）及びＧＮ１５００からのメンバシップレポート（ＭＲ）である。ハートビート制御パケット１７００は、ＬＰＧの領域を画定する。
【０１１５】
図１７は、ハートビート制御パケット１７００のフォーマットの一例を示す。ハートビート制御パケット１７００は、ＬＰＧ識別子すなわちＧＩＤ１７０５及びグループヘッダＩＤ１７１０の両方を含む一意の識別子を含む。
【０１１６】
ＧＩＤ１７０５及びグループヘッダＩＤ１７１０は、各ＬＰＧ１１５を識別する。ＧＩＤ１７０５にはいくつかのフォーマットがあり得る。一実施形態では、ＧＩＤ１７０５は、ＬＰＧ１１５に対してランダムに選択された識別番号であってもよい。代替的に、ＧＩＤ１７０５は、ＬＰＧの形成の順序に基づいて割り当てられた識別番号であってもよい。たとえば、第１のＬＰＧは、ＬＰＧ１というＧＩＤ１７０５を有してもよく、第２のＬＰＧはＬＰＧ２であり、以下同様である。しかしながら、ＧＨ１３００が変化すると、ＧＩＤ１７０５も同様に変化し、その結果、ノードは、そのＬＰＧが変化したのか、単にＬＰＧ１１５のＩＤが変化したのかを識別できなくなる。他方で、ＧＨが離れる時に、ＧＩＤ１７０５を元のＩＤに固定してもよい。しかしながら、これにより、単一ＬＰＧが分割する場合にＧＩＤ１７０５が重複する可能性がある。２つ以上のグループが同じＧＩＤ１７０５を有することになる。一実施形態では、ＧＩＤ１７０５は、ＬＰＧ１１５を一意に識別するためにＬＰＧ ＩＤ番号及びＧＨ ＩＤ番号の両方に基づいて符号化される。
【０１１７】
ＧＨ１３００にはグループヘッダＩＤ１７１０が与えられる。最初に、ＧＩＤ１７０５は、グループヘッダＩＤ１７１０に結び付けられる。したがって、グループヘッダＩＤ１７１０は、最初は、ＧＩＤ１７０５の一部として使用されるが、ＧＨが変化すると、ＧＩＤ１７０５は新たなグループヘッダＩＤ１７１０を含むように変化する。各ＧＨにはグループヘッダＩＤ１７１０が割り当てられる。グループヘッダＩＤ１７１０は、（パブリック又はプライベート）ＩＰアドレスに基づいて割り当てられる。図１７に示すように、グループヘッダＩＤ１７１０はＩＰｖ６ＩＰアドレスである。別の実施形態では、グループヘッダＩＤ１７１０はＩＰｖ４アドレスであってもよい。
【０１１８】
ハートビート制御パケット１７００はまた、シーケンス番号（Ｓｅｑ．Ｎｏ．）１７１５も含む。Ｓｅｑ．Ｎｏ．１７１５は、ハートビート制御パケット１７００の順序を追跡して、受信されたハートビート制御パケット１７００が新しいすなわち新着（fresh）である否かを判定するために使用される。ＧＮ１５００は、受信したハートビート制御パケット１７００のＳｅｑ．Ｎｏ１７１５を記憶している。新たなすなわち新着のハートビート制御パケット１７００は、次のＳｅｑ．Ｎｏ．１７１５を有する第１のハートビート制御パケット１７００によって示される。シーケンス番号１７１５はまた、いずれのハードビート制御パケット１７００が（次のホップノードに）中継されるべきかを判定するためにも使用され、すなわち、ＦＣＲＯ（first come relay only）（先着のみ中継）戦略を使用することができる。新たな（すなわち新着の）ハートビート制御パケット１７００のみが中継されるべきである。ノードは、先のシーケンス番号を記憶しており、ハートビート制御パケット１７００の着信シーケンス番号を比較することにより、ハートビート制御パケット１７００が新しいすなわち新着であるか否かを判定する。適当なＧＩＤ１７０５を有するハートビート制御パケット１７００のＳｅｑ．Ｎｏ．１７１５が、現時点で格納
されているシーケンス番号より大きい場合、それは、新たなすなわち新着のハートビート制御パケット１７００であり、ＦＣＲＯが使用される場合、中継される。ＧＮに先に格納されていたシーケンス番号は、破棄され、新たなＳｅｑ．Ｎｏ．１７１５に置き換えられる。
【０１１９】
ハートビート制御パケット１７００は、ハートビート期間（ＨＢ期間）１７２０に関する情報をさらに含む。この期間は固定間隔（Ｔ）である。間隔（Ｔ）の値は、設計又は動作の必要に基づいて選択可能である。ＨＢ期間１７２０は、すべてのＧＮ１５００に対し、次のハートビート制御パケット１７００がいつブロードキャストされるかを示す。ＧＮ１５００は、ＨＢ期間１７２０内にハートビート制御パケット１７００を受信しない場合、新たなハートビート制御パケット１７００を送信し、それにより、ハートビート制御パケット１７００は連続的に送信される。元のＧＨ１３００が依然としてＬＰＧ１１５にある場合、ヘッダ解決が発生する。制御オーバーヘッドを低減するために、ＧＨ１３はＨＢ期間１７２０を調整することができる。調整は、ＬＰＧのサイズ、ＬＰＧ内のノードの位置、負荷、速度及び数に基づくことができる。
【０１２０】
ハートビート制御パケット１７００はまた、ハートビート制御パケット１７００のタイプ、たとえば完全なグループリストを有するハートビート、徐々に増加するグループリストを含むハートビート、又はグループリストのないハートビートも含む。一実施形態では、ハートビート制御パケット１７００は、すべてのパケットに完全なグループリストを含む。完全なグループリストを使用することは、ルーティングを制御しグループメンバの正しいリストを維持する最も正確な方法であるが、完全なグループを有するハートビート制御パケット１７００に対して大量の帯域幅が必要である。ハートビート間隔（Ｔ）を、制御オーバーヘッドを低減するように調整することができる。別の実施形態では、すべての第ｎのハートビート制御パケット１７００が完全なグループリストを含む。たとえば、各第３のハートビート制御パケット１７００が完全なグループリストを含む。これにより、平均ハートビート制御パケット１７００に対する帯域幅が低減する。しかしながら、ＬＰＧ１１５内のノードの大部分が急速なペースで移動しているため、受信されるグループリストは古くなっている可能性がある。言い換えれば、新たなグループリストがノードによって受信される時まで、グループのいくつかのメンバは別のＬＰＧ１１５内にある可能性がある。別の実施形態では、徐々に進行するか（progressive）又は徐々に増加する（incremental）グループリストを配信することができる。グループリストにメンバシップの変更がある場合にのみ、グループリストは配信される。徐々に進行するか又は徐々に増加するグループリストにもまた、メンバシップリストが古くなる可能性がある。代替的に、ハートビート制御パケット１７００のタイプはハイブリッドグループリスト更新であってもよい。メンバシップに変更がある場合に、ハートビート制御パケット１７００に徐々に進行するグループリストを含めることができ、さらにすべての第ｎのハートビート制御パケット１７００に完全なグループリストを含めることができる。ＴｏＨｂ１７２５は、ハートビート制御パケット１７００のタイプを示す。ハートビート制御パケット１７００のタイプは、ＬＰＧ１１５のトポロジ変化の速度及びハートビート制御パケット１７００のブロードキャストの頻度によって影響を受ける。ＬＰＧ１１５のトポロジ変化の速度が増大すると、すべてのハートビート制御パケット１７００に完全なグループリストを含める必要が増大する。ハートビート制御パケット１７００のブロードキャストの頻度が増大すると、すべてのハートビート制御パケット１７００に完全なグループリストを含める必要が低減する。
【０１２１】
ハートビート制御パケット１７００は、ＧＨからのホップカウント（ＨＣ）１７３０を含む。最初、ＨＣ１７３０は所定値、たとえば１に設定されている。ハートビート制御パケット１７００がノードによって中継される度に、中継ノードはＨＣ１７３０の値を１だけ増加させ、すなわちＨＣ＝ＨＣ＋１となる。ＨＣ値を使用して、ＬＰＧサイズを制限し
、ハートビート制御パケット１７００内の情報の古さを示すと共に、オーバーヘッドを低減するように制御パケットのルーティングを制御することができる。各ＬＰＧに対し、ルーティングの最大ホップカウントたとえば１０がある。ＨＣ１７３０が最大ホップカウントまでインクリメントされると、制御パケット、たとえばハートビート制御パケット１７００は中継されない。
【０１２２】
最大ホップカウント、ＨＣ１７３０及びＳｅｑ．Ｎｏ．１７１５を使用することにより、ＬＰＧ１１５内の制御パケットのフラッディングの無限の重複が防止される。フラッディングは、グループ内のすべてのノードによってパケットが配信されるパケット配信方法である。ネットワーク密度が高い場合には、フラッディングにより不要な数の重複中継が発生する。ネットワーク内の各すべてのノードがフラッディングパケット中継に参加し、各ノードがこれらのパケットをそのリンクのすべてに中継する。
【０１２３】
ホップカウントはまた、中継戦略に使用することもできる。一実施形態では、ハートビート制御パケット１７００は、最も短いホップカウントを有する場合に中継される。この方法により正しいホップカウントが保証されるが、待ち遅延がある。ノードは、ハートビート制御パケット１７００に対する最短ホップカウントを判定しなければならないため、ハートビート制御パケット１７００を中継する前に、すべてのアップストリームノードからハートビート制御パケット１７００を受信するまで待たなければならない。したがって、最短ホップカウント及び上述した先着のみ中継戦略の両方を使用して、結合された中継戦略を実装することができる。ハートビート制御パケット１７００は、ノードがより短いホップのハートビート制御パケット１７００を受信するまで、先着のみ中継戦略を使用して中継される。ノードＡは、ハートビート制御パケット１７００を転送する時、メッセージにＩＤ情報を含め、それにより、次ホップノードは、何がハートビート制御パケット１７００を中継したかを知る。そして、パケットを転送しているノード（ノードＡ）は、ノードＡからハートビート制御パケット１７００を受信した次ホップノードに対するＭＲ中継ノード（ＧＨ１３００に向かってＭＲ１８００を送信する）となる。
【０１２４】
上述したように、ハートビート制御パケット１７００は、グループリスト１７３５も含むことができる。グループリスト１７３５は、ＬＰＧ１１５内のメンバの数、各メンバに対するＩＰアドレス、ＧＨからのホップカウント及び分類のような、ＬＰＧ１１５のメンバに関する情報を含むことができる。
【０１２５】
分類は、ＧＨノードからの相対的な方向、たとえばアップリンク、ダウンリンク及びピアを指すコードであってもよい。ピア分類は、ノードがＧＨからの同じ無線サービスエリア内にあることを示し、すなわち、ピアノードのすべてがＧＨからの同じホップカウントを有する。アップストリームノードは、ハートビート制御パケット１７００によって判定される。ダウンストリームノードは、メンバシップレポート（ＭＲ）に基づいて判定される。アップストリーム伝送は、ＧＨ１３００に向かう通信を表し、ダウンストリーム伝送は、ＧＨ１３００から離れる通信を表す。この分類は相対的な用語である。各ＧＮ１５００は、その隣接するＧＮを３つの異なるクラスに分類することができる。ＧＮは、別のＧＮのメンバシップレポートがそのＧＮのＨＣより１つ少ないホップカウント（ＨＣ）を有する場合、アップストリームノードである。ＨＣ１７００がＧＮ１５００自体のＨＣ１７００と同じである場合、ＧＮ１５００はピアである。ＨＣ１７００がＧＮ自体のＨＣ１７００より１大きい場合、ＧＮはダウンストリームノードである。
【０１２６】
図１８は、メンバシップレポート（ＭＲ）１８００を示す。ＭＲ１８００は、ＧＨ１３００によって受信されるようにＧＮ１５００がブロードキャストする制御パケットである。ＭＲ１８００は、メンバシップリスト、ダウンストリームノード識別及びダウンストリームノードに対する次ホップのような収集可能なルーティング情報を含む。ＭＲ１８００
は、ハートビート制御パケット１７００と同じ情報のうちのいくつか、すなわちＧＩＤ１７０５及びグループヘッダＩＤ１７１０を含む。ＭＲ１８００はまた、ＭＲ Ｓｅｑ．Ｎｏ１８０５も含む。ＭＲ Ｓｅｑ．Ｎｏ．１８０５は、ハートビート制御パケット１７００のＳｅｑ．Ｎｏと同様であり、ＭＲの順序を維持するために使用される。ＭＲ．Ｓｅｑ．Ｎｏ．１８０５は１つの特定のノードに対するＭＲ順序である。通常、ＭＲ Ｓｅｑ．Ｎｏ．１８０５は、ＭＲ１８００をトリガしたハートビート制御パケット１７００のＳｅｑ．Ｎｏ．１７１５と同じ値を有する。
【０１２７】
ＭＲ１８００には、発信ノード、すなわちＭＲ１８００を生成したノードのノードＩＤ１８１０も含まれている。
【０１２８】
ＭＲ１８００は、次ホップ中継ＩＤ１８１５も含む。次ホップ中継ＩＤ１８１５は、ＧＨ１３００に向かうＭＲ１８００に対する中継命令である。次ホップ情報は、受信されたハートビート制御パケット１７００から直接判定される。ノードは、新たなすなわち新着のハートビート制御パケット１７００を受信すると、いかなるパケット処理をも行う前に、ＩＰ層及びＭＡＣ層から以前の中継ノードの識別を再取得する。以前の中継ノードの識別は、メモリに格納されており、ＭＲ１８００に対する次ホップ中継ＩＤ１８１５として使用される。ノードは、ハートビート制御パケット１７００を転送する時、パケットにそのＩＤを含める。受信側の次ホップノードは、新たなすなわち新着のハートビート制御パケット１７００を受信すると、このＩＤを、ＧＨ１３００に到達するための次ホップ中継ＩＤとして格納する。新たなすなわち新着のハートビート制御パケット１７００は、ＨＣが最低なより新しいシーケンス番号を有するパケットである。
【０１２９】
ＭＲ１８００はまた、「ＭＲのタイプ指標」ＴｏＭＲ１８２０も含む。ＭＲ１８００には２つのタイプ、すなわち単一メンバのレポートと統合された複数メンバのレポートとがある。単一メンバＭＲは、発信ノードからのＭＲ１８００のみを含む。統合複数メンバレポートは、２つ以上のノードのＭＲ１８００を含む。統合レポートを使用して、制御パケットに必要なオーバーヘッド及び帯域幅を低減することができる。複数のＭＲを含む１つのＭＲ１８００が送信される。
【０１３０】
さらに、ＭＲ１８００は、ＧＨからのホップカウント（ＨＣ_ＧＨ）１８２５を含むことができる。（ＨＣ_ＧＨ）１８２５は、ＧＨ１３００からＭＲ１８００の発信ノードまでのＨＣ値である。別の実施形態では、ＭＲ１８００は、累積メンバシップリスト１８３０と他の追加の情報１８３５とを含むことができる。累積メンバシップリスト１８３０は、ＬＰＧのメンバのＩＰアドレス、メンバの数及び対応するホップカウントを含む。
【０１３１】
ＭＲ１８００を、逆経路又は逆フラッディング方法を使用してＧＨ１３００に配信又は中継することができる。逆経路方法は、ハートビート制御パケット１７００を中継するために使用されたものと同じ経路を使用して、ＭＲ１８００をＧＨ１３００に向かって中継する。ＭＲ１８００が中継される時、中継ノードは、次ホップ中継１８１５をＧＨに向かうその次ホップに置き換える。対応するＩＤを有するノードのみが、ＭＲ１８００パケットを中継する。この方法により、伝送の対称性が保証される。非対称リンクが存在する場合、逆フラッディング方法が使用され、すなわち、発信ノードとＧＨ１３００との間のすべてのノードがＭＲ１８００を中継する。
【０１３２】
各ノードは、ハートビート制御パケット１７００及びＭＲ１８００の両方を使用して、ＬＰＧベースのルーティングのための転送テーブルとして使用可能なルーティングテーブル２３００を作成する。好ましい実施形態では、各ハートビート制御パケット１７００は、完全なグループリストを有し、ＬＰＧ１１５内のすべてのＧＮ１５００が、それに対してＭＲ１８００で応答する。ハートビート制御パケット１７００は、先着のみ中継方法を
使用して中継され、ＭＲ１８００は、単一ＭＲとして逆経路方法を使用してＧＨ１３００に向かって中継される。
【０１３３】
図１９は、ユニキャストメッセージのＬＰＧベースのルーティング方法を示す。最初、各ノードは、ステップ１９００においてアイドル状態である。ステップ１９０１においてパケットが到着すると、ステップ１９０２において、ノードは、パケットがハートビート制御パケット１７００であるか又はＭＲ１８００であるかを判定する。制御パケットのタイプに応じて、ノードは特別なパケット処理を実行する。制御パケットがハートビート制御パケット１７００である場合、ノードは、ステップ１９０３から始まるパケット処理を開始する。ステップ１９０３において、ノードは、パケットがネイティブ（native）であるか否かを判定する。パケットは、同じＬＰＧ１１５に対するものである、すなわち同じＧＩＤ１７０５を有する場合、ネイティブである。ノードは、ＧＩＤ１７０５を、メモリに格納されているグループ識別と比較する。ＧＩＤ１７０５が、メモリに格納されている識別と一致しない場合、ステップ１９０４において、ノードは、外部ＨＢ処理を開始する。通常、外部ＨＢ処理の結果、ノードはパケットを無視する。ＧＩＤがメモリに格納されている識別と一致する場合、ノードはその後、ハートビート制御パケット１７００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．１７１５をメモリのシーケンス番号と比較する。ステップ１９０５において、Ｓｅｑ．Ｎｏ．１７１５がメモリに格納されている値より小さい場合、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．１７１５がメモリに格納されている値より大きい場合、ハートビート制御パケット１７００は順序通りであり、ステップ１９０６において、ノードは、現シーケンス番号を最後に格納されたシーケンス番号と比較することによって、ハートビート制御パケット１７００が新しいか否かを判定する。ノードが、メッセージが新しくないと判定する場合、ステップ１９０７において、送信者のルーティングエントリのみが更新される。ハートビート制御パケット１７００は中継されない。ノードは、メッセージが新しいと判定した場合、ノードがＧＨ１３００であるか又はＧＮ１５００であるかに応じて、２つの機能のうちの１つを実行する。ステップ１９０８において、ノードタイプの判定を実行する。ノードがＧＨ１３００である場合、ステップ１９０９において、ノードは送信者のルーティングエントリを更新する。ハートビート制御パケット１７００は中継されず、ノードはアイドル状態になる（１９００）。しかしながら、ノードは、ＧＮ１５００である場合、ステップ１９１０において、すべてのグループメンバエントリに対してルーティングテーブル２３００を更新し、ハートビート制御パケット１７００を中継する。ルーティングテーブル２３００の更新については後により詳細に説明する。
【０１３４】
制御パケットがＭＲ１８００である場合、ノードはステップ１９１１から始まるパケット処理を開始する。ステップ１９１１において、ノードは、パケットがネイティブであるか否かを判定する。ノードは、ＧＩＤ１７０５をメモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別に一致しない場合、ステップ１９１２において、ノードは外部ＭＲ処理を開始する。ＧＩＤがメモリに格納されている識別と一致する場合、ノードは、そのＭＲ１８００を送信したノードがＬＰＧ１１５のメンバであるか否かを判定する。ノードは、ノードＩＤ１８１０をメモリに格納されているメンバシップリストと比較する。一致がない場合、ステップ１９１４において、ノードはＭＲ１８００を中継のみする。ＭＲは中継され、それにより、完全なハートビートサイクルを待つ必要なしに、新たなグループノードがＬＰＧに参加することができる。ＭＲ１８００を送信したノードが参加リストに列挙されていない場合、ノードを参加（joining）ノードとみなすことができる。ルーティングテーブル２３００には参加ノードのルーティングエントリがない。一実施形態では、ノードは、ＭＲ１８００をＧＨ１３００に向かって転送することができる。ノードは、ルーティングテーブル２３００のいかなるエントリも更新しない。別の実施形態では、ノードは、（ＭＲの）発信ノードを宛先リストに追加することができ、すなわち、発信ノードに対してルーティングエントリを予約することができる。ノ
ードは、中継ノード情報を次ホップとして保存することができ、新たなハートビート制御パケット１７００がメンバとしての発信ノードによって受信される場合、ルーティングテーブル２３００を、メモリにすでに格納されている情報で自動的に更新することができる。新たなルーティングエントリが最終決定されると、発信ノードをダウンストリームノードとして分類することができる。
【０１３５】
一致がある場合、ステップ１９１５において、ノードは、ＭＲ１８００が順序通りであるか否かを判定する。ノードは、ＭＲ Ｓｅｑ．Ｎｏ１８０５をメモリのシーケンス番号と比較する。ＭＲ Ｓｅｑ．Ｎｏ１８０５がメモリに格納されている値より小さい場合、ノードはパケットを無視し、アイドル状態になる（１９００）。ＭＲ Ｓｅｑ．Ｎｏ１８０５がメモリに格納されている値より大きいか又はそれと等しい場合、ＭＲ１８００は順序通りであり、ノードは、ステップ１９１６において、ノードが現シーケンス番号の発信者からすでにＭＲ１８００を受信しているか否かを（最後に格納されたシーケンス番号を比較することにより）判定することにより、ＭＲ１８００が新しいか否かを判定する。ノードが、メッセージが新しくないと判断する場合、ステップ１９１７において、送信者のルーティングエントリのみが更新される。ＭＲ１８００は中継されない。ノードは、メッセージが新しいと判定する場合、ノードがＧＨ１３００であるかＧＮ１５００であるかに応じて、２つの機能のうちの１つを実行する。ステップ１９１８において、ノードタイプの判定が行われる。ノードがＧＨ１３００である場合、ステップ１９１９において、ノードは、直接の送信者及び発信者のルーティングエントリを更新する。ＭＲ１８００は中継されず、ノードはアイドル状態になる１９００。しかしながら、ノードは、ＧＮ１５００である場合、ステップ１９２０において、送信者及び発信者についてルーティングテーブル２３００を更新し、ＭＲ１８００を中継する。ルーティングテーブル２３００の更新については、後により詳細に説明する。
【０１３６】
図２０及び図２１は、ノードがハートビート制御パケット１７００を受信したときのルーティングテーブル２３００更新方法を示す。ステップ２０００において、ノードが新着のハートビート制御パケット１７００を受信すると、ステップ２００５においてルーティングテーブル２３００が更新される。ノードは、新着のハートビート制御パケット１７００を受信すると、パケットがどこから来たか、すなわち直接の中継ノードを判定することができる。中継ノードは、ＧＨに対する次ホップである。ステップ２１００において、ノードは、ＧＨに対する次ホップを更新する。次に、ステップ２１０５において、ノードは宛先リストを追加するか又は更新する。宛先リストは、ＬＰＧ１１５のすべてのメンバのリストである。プロセスは、グループの元メンバのルーティング宛先を除去すること、及び新たなメンバに対するルーティングエントリを挿入することを含む。そして、ステップ２１１０において、ノードは、すべての宛先に対する次ホップをＧＨ１３００として設定する。ＧＨ１３００は、最初はすべての宛先に対する次ホップである。次ホップは、ＬＰＧ１１５に関するより多くの情報が利用可能となるにつれて変化する。そして、ステップ２０１０において、ノードは、情報の新鮮度（freshness）指標を更新する。特に、ノードは、ハートビート制御パケットを追跡するためにタイマをリセットする。ノードはまた、シーケンス番号をメモリに格納し、古くなった情報を破棄する。そして、ステップ２０１５において、ノードはホップカウントを１インクリメントする。さらに、ノードは、ハートビート制御パケット１７００を中継する前に、ステップ２０２０において、それ自体のＩＰアドレスを、ＧＨへの次ホップとしてパケットに挿入する。ステップ２０２５において、ノードは、ステップ２０００〜２０２０で説明したパケット処理後にメッセージを中継する。
【０１３７】
ステップ２０００において、ノードが重複したハートビート制御パケット１７００を受信すると、ステップ２０３０において、ルーティングテーブル２３００の直接の送信側のエントリのみが更新される。更新は、図２１のステップ２１００〜２１１０で説明した更
新プロセスを含む。さらに、ステップ２０３５において、新鮮度指標もまた更新される。
【０１３８】
新着のＭＲ１８００を受信する時はいつでも、ノードは、ＭＲ１８００からの情報を使用してルーティングテーブル２３００を変更する。ＭＲ１８００は、よりよいルーティングルートをもたらす追加のルーティング情報を提供する。各ノードは、すべてのダウンストリームノード、１ホップ離れたアップストリームノード又はピアノードからＭＲをヒアリングすることができる。ダウンストリームノード及びアップストリームノードの場合、ノードは、１ホップ内のすべてのノードのＭＲ１８００をヒアリングすることができる。ルーティングテーブル２３００は、ＭＲの中継ノードを対応するルーティングエントリの次ホップに設定することによって更新される。ノードは、ＭＲの発信者のルーティングエントリを検査する。次ホップが中継ノードでない場合、エントリが変更される。さらに、直接の送信者のルーティングエントリが更新され、直接接続、すなわち宛先への次ホップは、宛先である。ＭＲ１８００に関連付けられるルーティングエントリに対する新鮮度指標が更新され、ＭＲ１８００を送信する発信ノードのシーケンス番号が更新される。ルーティングテーブル２３００は、ハートビート制御パケット１７００及びＭＲ１８００が共に受信された後にのみ完成する。したがって、ルーティングテーブル２３００は、完成した後にメッセージを転送するためにのみ使用される。更新プロセス中、先のルーティングテーブル２３００が転送テーブルとして使用される。
【０１３９】
転送テーブルは、パケット転送に使用されるルーティング情報である。内部ルーティングテーブル２３００の構成が完了した後、ノードは、新たなルーティングデータを使用するパケット転送を可能にするように転送テーブルをリセットする。
【０１４０】
図２２は、ユニキャストＩＰパケット転送に対する有限状態機械を示す。ノードの初期状態はアイドル２２００である。ユニキャストパケットが到着すると、ノードは、パケットの最終宛先がそのノードであるか否かを判定する（状態２２０５）。最終宛先が一致すると、すなわち、パケットの宛先アドレスがノードＩＰアドレスと一致すると、ノードはパケットを消費する（状態２２１０）。ＩＰパケットは処理される。パケットがそのノード宛てでない場合、ノードはパケットを転送する（状態２２１５）。特に、ノードはまず、ルーティングテーブル２３００をＩＰパケットからの情報で更新し、次に、転送テーブルにおいて宛先アドレスを検索し、転送テーブルに列挙されている隣接する次ホップにパケットを転送する。
【０１４１】
図２３は、内部ルーティングテーブル（Internal Routing Table）２３００のフォーマットの一例を示す。ＩＲＴ２３００は、メモリに格納されているデータベースである。ＩＲＴ２３００の第１列は、ＬＰＧにおけるルーティング可能エントリ又は宛先のすべてを列挙する。第２列は、各宛先に対する次ホップを列挙する。別の実施形態では、ＩＲＴ２３００は、情報の新鮮度及びノード分類、すなわちアップストリーム、ピア、ダウンストリーム、参加を維持するか又は示すために、シーケンス番号又はタイムスタンプを含むことができる。
【０１４２】
＜マルチキャスト＞
別の実施形態では、ＬＰＧネットワークは、マルチキャストメッセージ機能をサポートすることが可能である。ユニキャストでは、送信ノード（たとえば事故の目撃者）は１つの特定の受信者にメッセージを送信するか又は向けるため、同じ情報を複数の受信者に送信するためには複数のメッセージが必要である。これにより、大量のネットワーク帯域幅が消費されメッセージが遅延する結果となる。たとえば、ユニキャストでは、特定のメッセージに対して６つの異なる受信者がいる場合、送信者とその隣接するノード、すなわち受信者との間のリンクに、６つの異なるメッセージ及び重複したメッセージが送信される。ネットワークは、同じメッセージを送信するために６回使用され、送信者の最後の送信
の受信者は他より長く待つ必要がある。さらに、送信者は、前もって各受信者、すなわち各受信者のＩＰアドレスを知っていなければならない。
【０１４３】
マルチキャスト伝送では、送信者はメッセージの重複したコピーを生成せず、すべての受信者に対し１つのメッセージを送信する。マルチキャストにより、ネットワーク帯域幅は大幅に節約される。たとえば、送信者は、６つの１ホップ隣接する受信者に１つのメッセージを送信する必要がある場合、６つの受信者すべてに対し１つのマルチキャストメッセージを生成する。使用される総帯域幅は１／６に低減される。さらに、ノードは、事前に完全に編成されている必要はなく、すなわち各ノードは他のすべてのノードのアドレスを知っている必要はなく、マルチキャストグループ２４００識別又はマルチキャストグループ２４００のＩＰアドレスさえ知っていればよい。マルチキャストグループ２４００内のすべてのノードが、マルチキャストメッセージを受信する。さらに、後述するマルチキャストツリー又はメッシュが、マルチキャストグループのすべてのマルチキャストメンバがソースノードであって互いに通信するようにサポートすることができる。別個のマルチキャストツリー、すなわち各ソースノードに対し他のノードと通信するための１つのツリーを作成する必要はない。
【０１４４】
ユニキャストとは異なり、マルチキャストは、マルチキャストセッション毎に複数のソース及び受信者を扱う。たとえば、ＲＳＵ１００は、複数のスクールバスに１つの緊急情報を流そうとする。情報を迅速に配信するために、メッセージを送信する前に、関与するスクールバス間の経路を確立しなければならない。マルチキャストでは、マルチキャストメンバ間のルーティング経路は、マルチキャストツリーに基づく。マルチキャストツリー又はメッシュが、事前対応型マルチキャストルーティング方法を使用して構築され、ノードの大部分が移動することによるアドホックネットワークの動的変化を考慮することができる。本発明によれば、マルチキャストメッセージが遅延し喪失することを回避するように、ツリー又はメッシュは迅速に調整される。
【０１４５】
本発明によるアドホックネットワークでは、参加者は通常、シングルホップすなわち直接隣接するホップか、又はマルチホップのいずれかにより接続されている。マルチキャストグループ２４００は、リーフノードと呼ばれるマルチキャストメンバから作成されている。各リーフ間のいかなるノードも、マルチキャスト転送ノード（ＦＮ）２４１０として選択し、関連付けられるマルチキャストメンバにマルチキャストパケットを転送するために使用することができる。
【０１４６】
図２４は、マルチキャストグループ２４００の一例を示す。マルチキャストグループ２４００は、３つのマルチキャストメンバＬＮ１ ２４０５_１、ＬＮ２ ２４０５_２及びＬＮ３ ２４０５_３を含む。マルチキャストグループ２４００はまた、転送ノードＦＮ１ ２０１０_１及びＦＮ２ ２０１０_２も含む。この例では、グループヘッダＧＨ１３００もまた転送ノード２４１０でもある。図２４に示す残りのノードはグループノード１５００である。ＬＰＧ１１５のすべてのノードが、リーフノード２４０５又は転送ノード２４１０又は両方であることが可能である。マルチキャストツリーは、すでに上述したパケットの同様の制御及び形成に基づいて作成される。マルチキャストツリーは、帯域幅の著しい増大及び制御パケットの追加の情報なしに、制御パケットに含まれている情報を活用する。制御パケットは、ハートビート制御パケット１７００及びＭＲ１８００を含む。マルチキャストツリーは、任意のソース、すなわちリーフから、受信者すべて、すなわち他のリーフへの経路を提供する。
【０１４７】
マルチキャストセッションを確立するため、マルチキャストセッションに関心のあるノードは、マルチキャストセッションに対応するマルチキャストアプリケーションプログラムを開始する。アプリケーションプログラムはメモリに格納されている。したがって、ノ
ードは、リーフノードとなり、ＬＰＧ１１５へのセッションに参加したいという関心を示す信号（ＭＲ１８００）を発する。これらの信号により、マルチキャストセッションのためのマルチキャストツリーの生成が開始する。
【０１４８】
ノードは、開始信号を受信すると、マルチキャストセッションのＦＮ２４１０となる。ＦＮ２４１０は、マルチキャストセッションに関連するマルチキャストパケットを受け入ると共に転送することができる。
【０１４９】
図２４を参照すると、ＬＮ１ ２４０５_１〜ＬＮ３ ２４０５_３は、マルチキャストセッション（たとえば気象サービスセッション）に関連付けられるマルチキャストアプリケーションプログラムを開始することによって、マルチキャストセッションに参加しリーフノード２４０５となる。ＦＮ２４１０としてＦＮ１ ２４１０_１、ＧＨ１３００、ＬＮ２
２４０５_２及びＦＮ２ ２４１０_２が選択されることにより、リーフノードＬＮ１ ２４０５_１〜ＬＮ３ ２４０５_３のすべてにわたるマルチキャストセッションのためのマルチキャストツリーが形成される。
【０１５０】
本発明によれば、マルチキャストツリーを２つの方法で作成することができる。図２５は、本発明の一実施形態によるマルチキャストツリーを形成する一方法を示す。この実施形態では、ＧＨがマルチキャストツリーの作成を制御する。ステップ２５００において、ＧＨは、ＬＰＧ１１５内の各ノードに対して分類を割り当てなければならない。分類は、ノードがＧＨ１３００からのアップストリームであるか又はダウンストリームであるかに基づく。ノードは、ＧＨ１３００からのアップストリームである場合、第１の分類が割り当てられ、ＧＨ１３００からのダウンストリームである場合、ノードに対し第２の分類が割り当てられる。たとえば、一方の分類は青であってもよく、青がＧＨ１３００の一方の側に位置するすべてのノードに割り当てられ、他方の分類は赤であってもよく、赤がＧＨ１３００の他方の側のすべてのノードに割り当てられる。ＧＨ１３００は、ＬＰＧ１１５内のすべてのノードに対し分類を含むハートビート制御パケット１７００をブロードキャストする。ステップ２５０５において、すべてのノードが、ＧＨからのホップカウントを判定する。ＧＨからのホップカウントは、ハートビート制御パケット１７００から直接判定される。ステップ２５１０において、ＧＨ１３００は、リーフノード２４０５に関する情報を収集する。この情報は、メンバシップレポートから直接判定される。ステップ２５１５において、ＧＨ１３００は、収集された情報に基づいて、リーフノード２４０５が関与するマルチキャストセッションの配信範囲（scope）を画定する。特に、ＧＨ１３００は、すべてのＭＲ１８００を処理して、いずれのノードがリーフノード２４０５（すなわちマルチキャストセッションのメンバ）であるかと、それらの分類と、ホップ距離とを見つける。たとえば、赤及び４ホップ距離、青及び１ホップ距離である。配信範囲により、マルチキャスト転送の範囲が限定される。マルチキャストセッションのためにＧＨ１３００によって画定される配信範囲内の中継ノードはＦＮ２４１０になる。ＦＮ２４１０のセットは、マルチキャストメッシュを表す。
【０１５１】
図２６は、この実施形態によるマルチキャストグループ２４００の一例を示す。陰付領域が、マルチキャストグループ２４００の配信範囲を表している。この例では、リーフノードＬＮ１ ２４０５_１はＧＨ１３００_ｍの一方の側にあり、リーフノードＬＮ２ ２４０５_２及びＬＮ３ ２４０５_３は他方の側にある。ＬＮ１ ２４０５_１の分類は第１の分類、すなわち赤であり、リーフノードＬＮ２ ２４０５_２及びＬＮ３ ２４０５_３の分類は第２の分類、すなわち青である。赤側では、最も遠いリーフノードはＧＨ１３００から４ホップはなれており、青側では、最も遠いリーフノードは２ホップ離れている。したがって、マルチキャストグループ２４００の配信範囲は、赤側に４ホップから青側に２ホップまでである。この配信範囲情報は、ハートビート制御パケット１７００を通じて中継ノードに公表される。中継ノードは、配信範囲情報を受信すると、ＦＮ２４１０となるか否
かを判定する。図２６に示すように、４ホップ赤から２ホップ青までの範囲内の中継ノードは、マルチキャストセッションのＦＮ２４１０となる。リーフノードＬＮ２ ２４０５_２は、リーフノード及びＦＮ２４１０の両方である。マルチキャストメッセージは、メンバ間の最短経路を使用してルーティングされる。
【０１５２】
上述したように、マルチキャストツリーは、ハートビート制御パケット１７００及びＭＲ１８００に基づいて作成される。ＧＨ１３００は、所定の間隔でハートビート制御パケットをブロードキャストする。ハートビート制御パケット１７００は、ＬＰＧ１１５内のすべてのノードに配信される。ハートビート制御パケット１７００に応答して、各ノードは、ＭＲ１８００をＧＨ１３００に送信する。ＧＨ１３００に向かってＭＲ１８００を中継するノードは、中継ノード（ＲＮ）である。マルチキャストの場合、ハートビート制御パケット１７００及びＭＲ１８００の内容は、マルチキャスト関連情報を含むように更新される。特に、分類情報及びマルチキャスト配信範囲情報がハートビート制御パケット１７００に追加され、メンバ分類及びＧＨへのホップ距離がＭＲ１８００に含まれる。図２７及び図２８は、マルチキャストツリーを作成するために使用されるハートビート制御パケット１７００及びＭＲ１８００の例である。
【０１５３】
ノードは、ハートビート制御パケット１７００を受信すると、その分類、そのホップ距離と共に、マルチキャスト配信範囲情報を取得する。中継ノードは、ハートビート制御パケット１７００の配信範囲情報に基づいて、ＦＮ２４１０になる必要があるか否かを判定する。特に、配信範囲内の中継ノードはＦＮ２４１０になる。マルチキャストセッションに対するすべてのＦＮ２４１０が、マルチキャスト転送テーブル（ＭＦＴ, Multicast Forwarding Table）３１００におけるエントリとしてそのマルチキャストセッションに対するマルチキャスト転送エントリに反映される。ＭＦＴ３１００は、マルチキャストツリーに対する構造を反映する。ＭＦＴ３１００は、ハートビートサイクル毎に、すなわちすべてのハートビート制御パケット１７００及びＭＲ１８００の後に更新される。言い換えれば、マルチキャストツリー及びＭＦＴ３１００は、参加したり離れたりするノードと共にマルチキャストメンバの移動度を反映するように更新される。
【０１５４】
図２９は、本発明のこの実施形態による、マルチキャストメッセージのＬＰＧベースのルーティング方法を示す。最初、各ノードはアイドル状態である（２９００）。パケットが到着すると（２９０１）、ノードは、パケットがハートビート制御パケット１７００であるか又はＭＲ１８００であるかを判定する。制御パケットのタイプに応じて、ノードは特別なパケット処理を実行する。ノードは、ステップ２９０２で制御パケットのタイプを判定する。制御パケットがハートビート制御パケット１７００である場合、ノードは、ステップ２９０３から始まるパケット処理を開始する。ステップ２９０３において、ノードは、パケットがネイティブであるか否かを判定する。パケットは、同じＬＰＧ１１５に対するものである、すなわち同じＧＩＤ１７０５を有する場合、ネイティブである。ノードは、ＧＩＤをメモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別と一致しない場合、ステップ２９０４において、ノードは、外部ハートビート制御パケット１７００処理を開始する。通常、外部ＨＢ処理により、ノードはパケットを無視することになる。ＧＩＤがメモリに格納されている識別と一致する場合、ノードは、ハートビート制御パケット１７００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．をメモリのシーケンス番号と比較する。ステップ２９０５において、Ｓｅｑ．Ｎｏ．がメモリに格納されている値より小さい場合、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より大きくかそれと等しい場合、ハートビート制御パケット１７００は順序通りであり、ステップ２９０６において、ノードは、ハートビート制御パケット１７００が新しい（すなわち、シーケンス番号が最後に格納されたシーケンス番号より大きい）か否かを判定する。ノードは、メッセージが新しくないと判定する場合、そのメッセージを無視し、アイドル状態になり、すなわちステップ２９００に
戻る。ハートビート制御パケット１７００が新しい場合、ステップ２９０７において、ノードは、それ自体が中継ノード（ＲＮ）であるか否かを判定する。ノードは、ＲＮでない場合、ステップ２９０８において、メモリにおけるＧＨからのホップカウント及び分類のような情報を更新する。他方で、ノードは、ＲＮである場合、ステップ２９０９において、当該ノードが配信範囲内にあるか否かを判定する。ＧＨ１３００は、受信したＭＲ１８００に基づいて配信範囲を画定する。ＧＨ１３００は、画定された配信範囲内に位置する場合、ＦＮ２４１０になる。ＲＮは、配信範囲内にある場合、ＦＮとなり、ステップ２９１０において、ＭＦＴ３１００に、マルチキャストセッションの識別、すなわちクラスＤマルチキャストＩＰアドレスを追加する。さらに、ノード、ここではＦＮ２４１０は、必要な場合、ホップカウント情報及び分類を更新する。ＲＮは、配信範囲内にない場合、ステップ２９０８において、メモリにおけるＧＨからのホップカウント及び分類のような情報を更新する。
【０１５５】
制御パケットがＭＲ１８００である場合、ノードは、ステップ２９１１から始まるパケット処理を開始する。ステップ２９１１において、ノードは、パケットがネイティブであるか否かを判定する。ノードは、ＧＩＤ１７０５を、メモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別と一致しない場合、ステップ２９１２において、ノードは、外部ＭＲ処理を開始する。パケットがネイティブである場合、ステップ２９１３において、ノードは、ＭＲ１８００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．をメモリのシーケンス番号と比較する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より小さい場合、ステップ２９１３において、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より大きいか又はそれと等しい、すなわちＭＲ１８００が順序通りである場合、ステップ２９１４において、ノードは、当該ノードがＧＨ１３００であるか否かを判断する。ノードは、ＧＨ１３００である場合、ステップ２９１５において、ＭＲ１８００に含まれる情報及び配信範囲を収集する。特に、ＭＲ１８００は、分類情報、ＧＨまでのホップカウント情報及びマルチキャストグループ２４００のメンバシップ情報を含む。ＧＨ１３００は、この情報を使用して、ハートビート制御パケット１７００を送信する前に、必要な場合、マルチキャストグループ２４００の配信範囲を調整することができる。さらに、ＧＨ１３００は、ＭＦＴ３１００を変更する、すなわちＦＮ２４１０としてそれ自体を追加する。最後に、ＧＨ１３００は、必要な場合、移動度を考慮するようにノードの分類を変更する。
【０１５６】
他方で、ノードは、ＧＨでない場合、ステップ２９１６において、それ自体がＲＮであるか否かを判定する。ノードのそれ自体のＩＤがＭＲ１８００の次ホップ中継ＩＤ（たとえばＩＰアドレス）と等しい場合、ノードはＭＲ１８００のＲＮである。すべてのノードが、ＧＨ、ＲＮ及びＦＮのようなそのノードステータスを維持する。ノードは、ＲＮでない場合、ステップ２９１７において、単に分類情報を更新する。ノードは、ＲＮである場合、ステップ２９１８において、そのノードステータスをＲＮとして設定し、分類情報を更新する。
【０１５７】
図３０Ａ及び図３０Ｂは、ＧＨ１３００（図３０Ａ）及びＲＮ（図３０Ｂ）両方に対する機能ノード状態遷移図を示す。ＧＨ１３００は、ＦＮ２４１０であってもなくてもよく、すなわち非ＦＮ３０００状態又はＦＮ３０１０状態のいずれかであり得る。ＧＨ１３００は、マルチキャストグループ２４００の配信範囲外に位置している場合、遷移３００５を介してマルチキャストグループ２４００の非ＦＮ状態３０００になる。ＧＨ１３００は、マルチキャストグループ２４００の配信範囲内にある場合、遷移３０１５を介してＦＮ２４１０状態３０１０に遷移する。ＦＮ状態３０１０になると、ＦＮ２４１０はＦＮタイマをセットする。ＦＮタイマを使用して、ノードがＦＮ２４１０である時間が制御される。タイマは、所定の期間にセットされる。ノードＦＮは、ＦＮ状態３０１０である間、ＦＮタイマが満了した時にのみ、遷移３０２５を通じて非ＦＮ状態に移動する。
【０１５８】
ＧＨ以外のノードは、４つの状態のうちの１つであり得る。すなわち、通常のノード（すなわち、非ＲＮ及び非ＦＮの両方）３０３０、ＲＮ状態３０４０、ＦＮ状態３０５０及びＦＮ／ＲＮ状態（ＦＮ及びＲＮ両方）３０６０である。図３０Ｂの有効ＭＲ（Valid MR）受信は、受信されたＭＲ１８００がそのノード宛てであることを意味する。通常のノード（状態３０３０）は、ＭＲ１８００を受信すると、遷移３０３５を介してＲＮ（状態３０４０）に遷移する。ＲＮ（状態３０４０）となると、ＲＮは、ハートビート制御パケット１７００を受信すると、３０５５を介してＦＮ２４１０（状態３０５０）に遷移するか、又は遷移３０４５を介して通常のノード（状態３０３０）に戻るように遷移する。ＲＮは、画定された配信範囲内にある場合、遷移３０５５を介してＦＮ（状態３０５０）になる。しかしながら、ＲＮ３０４０（状態３０４０）は、配信範囲内にない場合、通常のノード状態３０３０に遷移する。ＦＮ（状態３０５０）は、タイマが満了すると、遷移３０６５を通じてその状態を通常のノードに戻す。ＦＮ２４１０は、ＲＮ及びＦＮの両方であり得る。ＦＮ２４１０（状態３０５０）は、異なるＭＲ１８００を受信すると、遷移３０７５を介して状態３０６０に遷移してＲＮ／ＦＮ両方（状態３０６０）になる。ノードは、新たなハートビート制御パケット１７００を受信する（遷移３０８５）までＦＮ／ＲＮ両方として状態３０６０のままである。
【０１５９】
図３１は、本発明によるマルチキャストルーティングに使用されるＭＦＴ３１００の一例を示す。ＭＦＴ３１００のエントリは、マルチキャストグループアドレス（たとえばクラスＤ ＩＰアドレス）と発信インタフェースとから成る。マルチキャストグループ２４００が或るノードに対しＭＦＴ３１００に列挙されている場合、そのノードは、そのマルチキャストグループ２４００のＦＮ２４１０となる。各ＦＮ２４１０は、メモリにＭＦＴ３１００を格納している。したがって、ソース又は隣接するＦＮ２４１０からマルチキャストパケットを受信すると、それはマルチキャストパケットを転送する。
【０１６０】
非ＧＨの場合、ＭＦＴ３１００は、ハートビート制御パケット１７００のみに基づいて更新され、マルチキャストセッションに対するマルチキャストグループ２４００のアドレスは、ＭＦＴ３１００のエントリとして追加され、関連タイマ（すなわち、そのエントリに対するＦＮタイマ）が開始（又はエントリを更新する場合は再開）する。タイマが満了すると（すなわち更新は起こらない）、エントリはＭＦＴ３１００から取り除かれる。ＧＨ１３００は、ＭＲ１８００を受信するとＭＦＴ３１００を更新する。
【０１６１】
ＭＦＴ３１００は、ハートビート制御サイクル毎に更新される。ハートビート制御サイクルは、ハートビート制御パケット１７００の１つのセット及びＭＲ１８００の１つのセットの両方に対する時間を含む。ノードが可動であるという事実により、各ハートビート制御サイクルに対して中継ノードのセットが変化する可能性がある。この実施形態では、マルチキャストＦＮ２４１０はＲＮのサブセットであり、ＲＮが頻繁に変化する可能性があるため、マルチキャストメッシュ及びＭＦＴ３１００を、ハートビート制御サイクル毎に更新しなければならない。マルチキャストメンバシップの変更は、次のＨＢＣ（ハートビートサイクル）においてメッシュ及びＭＦＴ３１００に反映される。
【０１６２】
ＦＮタイマは、ＭＦＴ３１００の各エントリに関連付けられる。期間は、ハートビート間隔の倍数であるか、又はハートビート間隔よりわずかに大きい。ＦＮ２４１０が引き続き配信範囲内にある場合、ＦＮタイマは再開する。ノードが有効なＭＲ１８００及びハートビート制御パケット１７００を受信しない場合、ＦＮタイマは満了し、それは、ノードが所定の期間内の配信範囲内にあることを示す。ＭＦＴ３１００に列挙されるエントリに対するＦＭタイマが満了すると、エントリはＭＦＴから取り除かれ、すなわち、ノードは、そのエントリによって表されるマルチキャストセッションに対し非ＦＮとなる。
【０１６３】
リーフノード２４０５の移動度は、ＭＲ１８００及びハートビート制御パケット１７００伝送を通じて検出される。リーフノード２４０５の移動を検出し、メッシュすなわちＭＦＴ３１００を更新するためには、概ね２つのＨＢＣ（ハートビートサイクル？）が必要である。
【０１６４】
第２のマルチキャスト実施形態では、ＧＨ１３００はマルチキャストグループ２４００の配信範囲を画定しない。この実施形態では、マルチキャストメンバとＧＨ１３００との間のすべてのＲＮがＦＮ２４１０となる。この実施形態では、ＧＨ１３００が配信範囲を画定しないため、マルチキャストグループ２４００の形成がより迅速である。マルチキャストメンバは、自身のＭＲ１８００の中にマルチキャストメンバシップ情報を含める。メンバは、ＭＲ１８００にリーフノード（Leaf Node）ステータスをマルチキャストステータスとして設定する。ＲＮは、ＭＲ１８００を受信すると、関連付けられるマルチキャストグループ２４００に対するＦＮ２４１０になる。ＦＮ２４１０は、それ自体のＭＲ１８００にＦＮステータスを設定する。このマルチキャスト実施形態によれば、いかなる追加の情報もハートビート制御パケット１７００に追加する必要はない。パケットは、図１７に示すものと同じであってもよい。ＭＲ１８００は、図１８に示すＭＲ１８００に類似しているが、マルチキャストメンバシップに関する情報、たとえば関係するマルチキャストグループ２４００及びノードステータス、すなわちＦＮ２４１０又はリーフノード２４０５が追加される。
【０１６５】
図３２は、第２の実施形態による変更されたＭＲ１８００の一例を示す。この実施形態では、ノードステータスは、ＭＲ１８００のみに基づいて変化する。
【０１６６】
図３３は、本発明のこの実施形態によるマルチキャストメッセージのＬＰＧベースのルーティング方法を示す。最初、各ノードはアイドル状態である（３３００）。パケットが到着すると（３３０１）、ノードは、パケットがハートビート制御パケット１７００であるか又はＭＲ１８００であるかを判定する。制御パケットのタイプに応じて、ノードは特別なパケット処理を実行する。ステップ３３０２で、ノードは制御パケットのタイプを判定する。制御パケットがＭＲ１８００である場合、ノードはステップ３３０３から始まるパケット処理を開始する。ステップ３３０３において、ノードは、パケットがネイティブであるか否かを判定する。パケットは、同じＬＰＧ１１５に対するものである、すなわち同じＧＩＤ１７０５を有する場合に、ネイティブである。ノードは、ＧＩＤ１７０５をメモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別と一致しない場合、ステップ３３０４において、ノードは外部ＭＲ処理を開始する。通常、外部ＭＲ処理により、ノードはパケットを無視する。
【０１６７】
パケットがネイティブである場合、ステップ３３０５において、ノードは、ＭＲ１８００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．をメモリのシーケンス番号と比較する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より小さい場合、ステップ３３０５において、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より大きいか又はそれと等しい場合、ＭＲ１８００は順序通りであり、ステップ３３０６において、ノードは、ＭＲ１８００が元々リーフノード２４０５から送信されたか否かを判断する。ＭＲ１８００がリーフノード２４０５から送信されたものでない場合、ノードは、マルチキャストルーティングの目的でＭＲ１８００を無視する。ＭＲ１８００がリーフノード２４０５から送信されたものである場合、ステップ３３０７において、ノードは、それ自体がＧＨ１３００であるかＲＮであるかを判定する。ノードは、いずれの状態でもない場合、マルチキャストルーティングの目的でＭＲ１８００を無視する。ノードは、ＧＨ１３００又はＲＮいずれかである場合、ステップ３３０８において、ＭＦＴ３１００を更新し、すなわちＦＮ２４１０となる。この更新は、ＭＦＴ３１００にマルチキャストグループ２４００を追加することを含む。
【０１６８】
図３４は、この実施形態によるノードに対する機能状態遷移図を示す。ノードは、マルチキャストグループ２４００に対して非ＦＮ状態３４００か又はＦＮ状態３４１０のいずれかであり得る。状態３４００のノードは、リーフノードステータスを含むＭＲ１８００を受信すると、状態３４１０に遷移してＦＮ２４１０となる。ＦＮ２４１０は、マルチキャストセッションに対してＦＮタイマをセットする。マルチキャストグループ２４００に対するＦＮ時間が満了すると、ＦＮ２４１０はその状態を３４１０から３４００に変化させ、遷移３４２０を介して非ＦＮ（すなわち通常のノード）となる。状態３４１０の間、すなわちＦＮである間、タイマが満了しない場合、ＦＮ２４１０は遷移３４２５を介してＦＮのままである。
【０１６９】
第３のマルチキャスト実施形態では、ＧＨ１３００は、上記実施形態によって作成されたマルチキャストグループ２４００の配信範囲をプルーニングすることにより、ルーティングの効率を向上させることができる。プルーニング動作により、不要なＦＮが取り除かれる。ＧＨ１３００は、リーフノード２４０５からＭＲ１８００を収集した後、有効なプルーン適用範囲を画定し、必要な場合は、プルーンメッセージ３５００を送信する。プルーンメッセージ３５００は、ハートビート制御パケット１７００とは別個である。有効なプルーン適用範囲は、ＧＨから最も近いリーフノードへのホップカウントとして伝達される。プルーンメッセージ３５００は、有効なプルーン適用範囲内のＦＮのみによって処理され中継される。有効なプルーン適用範囲に位置するＦＮは、それらのＭＦＴ３１００の関連付けられるマルチキャスト転送エントリを除去し、通常のノードになる。
【０１７０】
図３５は、プルーンメッセージパケット３５００の一例を示す。プルーンメッセージパケット３５００は、グループ識別、グループヘッダ識別、シーケンス番号、マルチキャストメンバ識別及び有効なプルーン適用範囲を含む。マルチキャストメンバ識別は、マルチキャストグループ２４００に対するＩＰアドレスである。
【０１７１】
図３６は、本発明のこの実施形態によるマルチキャストメッセージのＬＰＧベースのルーティング方法を示す。最初、各ノードはアイドル状態である（３６００）。３６０１でパケットが到着すると、ノードは、パケットがハートビート制御パケット１７００であるか、ＭＲ１８００であるか又はプルーンメッセージパケット３５００であるかを判定する。制御パケットのタイプに応じて、ノードは特別なパケット処理を実行する。ステップ３６０２において、ノードは、制御パケットのタイプを判定する。制御パケットがＭＲ１８００である場合、ノードは、ステップ３６０３から始まるパケット処理を開始する。ステップ３６０３において、ノードはパケットがネイティブであるか否かを判定する。パケットは、同じＬＰＧ１１５に対するものである、すなわち、同じＧＩＤを有する場合、ネイティブである。ノードは、ＧＩＤをメモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別と一致しない場合、ステップ３６０４において、ノードは外部ＭＲ処理を開始する。パケットがネイティブである場合、ステップ３６０５において、ノードは、ＭＲ１８００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．をメモリのシーケンス番号と比較する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より小さい場合、ステップ３６０５において、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より大きいか又はそれと等しい場合、ＭＲ１８００は順序通りであり、ステップ３６０６において、ノードは、ＭＲが元々リーフノード２４０５から送信されたか否かを判断する。ＭＲ１８００がリーフノード２４０５から送信されていない場合、ノードは、マルチキャストルーティングの目的でＭＲ１８００を無視する。ＭＲ１８００がリーフノード２４０５から送信されたものである場合、ステップ３６０７において、ノードは、それ自体がＧＨ１３００であるか否かを判定する。ノードは、ＧＨでない場合、ステップ３６０８において、それ自体がＲＮであるか否かを判定する。ノードは、ＧＨでもＲＮでもない場合、マルチキャストルーティングの目的でＭＲ１８００
を無視する。ステップ３６０９において、ノードは、ＲＮである場合、ステップ３６０９においてＭＦＴ３１００を更新し、すなわちＦＮ２４１０となる。この更新には、ＭＦＴ３１００にマルチキャストグループ２４００を追加することが含まれる。
【０１７２】
ノードがＧＨ１３００である場合、ステップ３６１０において、ＧＨ１３００は、事前設定されたパラメータに基づいてプルーニングが必要であるか否かを判定する。事前設定されたパラメータは、ＧＨ１３００の一方の側にのみマルチキャストメンバがいるというものであってもよい。ＧＨ１３００は、ＧＨがマルチキャストグループ２４００にある必要はないことを判定する。ＧＨ１３００は、ＭＦＴ３１００からマルチキャストグループ２４００ＩＤを除去する。さらに、ＧＨ１３００は、ＧＨに最も近いマルチキャストメンバを判定する。この判定は、ＧＨからのホップカウントに基づく。プルーン適用範囲内に位置するいかなるＦＮ２４１０も、ＧＨから発信されるプルーンメッセージを受信する時にプルーニングされる。プルーンメッセージは、ＦＮ（リーフノードがなくプルーン適用範囲内に位置するＦＮ）をプルーニングすることによって中継され、ＧＨに最も近い、リーフノードを有するＦＮは、プルーンメッセージの中継を中止する。
【０１７３】
ステップ３６０２において、ノードが、パケットがプルーンメッセージパケット３５００であると判定すると、ステップ３６１１においてパケット処理が開始する。ステップ３６１１において、ノードは、パケットがネイティブであるか否かを判定する。パケットは、同じＬＰＧ１１５に対するものである、すなわち、パケットが同じＧＩＤを有する場合、ネイティブである。ノードは、ＧＩＤをメモリに格納されているグループ識別と比較する。ＧＩＤがメモリに格納されている識別と一致しない場合、ノードはパケットを無視し、アイドル状態になる。そして、ステップ３６１２において、ノードは、プルーンメッセージパケット３５００が順序通りであるか否かを判定する。ノードは、Ｓｅｑ．Ｎｏ．をメモリのシーケンス番号と比較する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より小さい場合、ステップ３６１３において、ノードはパケットを無視する。Ｓｅｑ．Ｎｏ．がメモリに格納されている値より大きいか又はそれと等しい場合、プルーンメッセージパケット３５００は順序通りであり、ステップ３６１４において、ノードはそれ自体がＦＮ２４１０であるか否かを判定する。ノードは、ＦＮでない場合、パケットを無視してアイドル状態になる。ノードは、ＦＮ２４１０である場合、ステップ３６１５においてそれ自体が有効なプルーン適用範囲内にあるか否かを判定する。最も近いリーフノードよりＧＨ１３００に近いいかなるＦＮ２４１０も、有効なプルーン適用範囲にある。この判定は、ＧＨへのホップカウントに基づく。ノードは、メモリに先に格納されているＧＨへのホップカウントを、有効なプルーン適用範囲におけるホップカウント情報と比較する。ＧＨへのホップカウントが有効なプルーン適用範囲からのホップカウントを下回る場合、ステップ３６１６において、ＦＮは非ＦＮになる。ノードは、ＭＦＴ３１００を更新し、ＭＦＴ３１００からマルチキャスト識別を除去する。ＧＨへのホップカウントが有効なプルーン適用範囲からのホップカウントを上回る場合、ノードはＦＮ２４１０のままである。
【０１７４】
ノードは、ステップ３６０２において、パケットがハートビート制御パケット１７００であると判定すると、ステップ３６１７において、単にメモリに格納されているホップカウント情報及び他の情報を更新する。
【０１７５】
図３７Ａ及び図３７Ｂは、この実施形態によるＧＨ１３００（図３７Ａ）及びＲＮ（図３７Ｂ）に対する機能状態遷移図を示す。図３７Ａに示すように、ＧＨ１３００は、マルチキャストグループ２４００に対して非ＦＮ状態３７００又はＦＮ状態３７１０のいずれかであり得る。状態３７００のノードは、リーフノードステータスを含むＭＲ１８００を受信すると、状態３７１０に遷移し、遷移３７０５を介してＦＮ２４１０になる。ＦＮ２４１０はマルチキャストセッションに対してＦＮタイマをセットする。マルチキャストグループ２４００に対するＦＮタイマが満了するか又はプルーンが確定されると、ＦＮ２４
１０はその状態を３７１０から３７００に変化させ、遷移３７２０を介して非ＦＮ（すなわち通常のノード）となる。状態３７１０の間、すなわちＦＮである間、タイマが満了とならないか又はリセットされる場合、ＦＮ２４１０は遷移３７１５を介してＦＮのままである。
【０１７６】
同様に、ＲＮは、マルチキャストグループ２４００に対して非ＦＮ状態３７００又はＦＮ状態３７１０のいずれかであり得る。状態３７００にあるノードは、リーフノードステータスを含むＭＲを受信すると、状態３７１０に遷移し、遷移３７０５を介してＦＮ２４１０になる。ＦＮ２４１０は、マルチキャストセッションに対してＦＮタイマをセットする。マルチキャストグループ２４００に対するＦＮ時間が満了するか、又はプルーンメッセージパケット３５００が受信されると、ＦＮ２４１０はその状態を３７１０から３７００に状態を変化させ、遷移３７２５を介して非ＦＮ（すなわち通常のノード）になる。状態３７１０の間、すなわちＦＮである間、タイマが満了しないか又はリセットされる場合、ＦＮ２４１０は遷移３７１５を介してＦＮのままである。
【０１７７】
ノードの大部分が移動するため、期間が異なるとＭＲ１８００がリーフノード２４０５からＧＨ１３００まで辿る経路は異なり、それによりＭＲ期間毎にＦＮ２４１０のセットが異なることになる。したがって、マルチキャストメッシュ又はＭＦＴ３１００は、ＦＮタイマ及び周期的ＭＲメッセージによって更新される。ＭＦＴ３１００を更新する効率を、ＦＮタイマの時間及び周期的ＭＲ１８００に間隔を制御することによって達成することができる。これらのパラメータを制御することにより、リーフノード２４０５及びＦＮ２４１０の両方の移動度を考慮するようにＭＦＴ３１００を更新することができる。
【０１７８】
新たなマルチキャストメンバは、進行中のマルチキャストセッションに参加したい場合、そのマルチキャストセッションに対するリーフノードステータスを有するそのＭＲ１８００を、当該マルチキャストメンバが参加したいセッションに対するマルチキャスト識別と共に送信する。
【０１７９】
図３８Ａ及び図３８Ｂは、２つのマルチキャストグループ、すなわちＭＲ１８００のみに基づいて形成された１つのグループ（図３８Ａ）と、ＭＲ１８００及びプルーンメッセージパケット３５００に基づいて形成された１つのグループとを示す。図３８Ａに示すように、リーフノードＬＮ１ ２４０５_１、ＬＮ２ ２４０５_２及びＬＮ３ ２４０５_３は、ＭＲ１８００をＧＨ１３００に向かって送信することによってマルチキャストグループ２４００に参加する。各リーフノードとＧＨ１３００との間のすべての中継ノード（ＲＮ）が、ＦＮ２４１０、たとえばＦＮ１、ＦＮ２、ＦＮ３及びＦＮ４（２４１０_１〜２４１０_４）になる。形成されたマルチキャストグループ２４００は、５つのホップ、サイズ５を有する。しかしながら、３つのリーフノードＬＮ１ ２４０５_１、ＬＮ２ ２４０５_２及びＬＮ３ ２４０５_３のすべてが互いに近接している、すなわちＧＨ１３００の同じ側にあるため、ＧＨ１３００はマルチキャストグループ２４００にある必要はない。したがって、ＧＨはそれ自体を最初にプルーニングすることによってプルーニングを開始し、それによりＧＨ１３００は非ＦＮになる（図３８Ｂ）。収集されたマルチキャスト情報に基づき、ＧＨ１３００は有効なプルーン適用範囲を決定する。この場合、ＬＮ３ ２４０５_３がＧＨ１３００に最も近く、２ホップ離れているため、プルーンは２ホップまで発生し、ＦＮ４ ２４１０_４及びＦＮ３ ２４１０_３が通常のノードになる。メッシュは、ＦＮ１ ２４１０_１及びＦＮ２ ２４１０_２のみから構成される。ＦＮ１ ２４１０_１及びＦＮ２ ２４１０_２のみが、ＭＦＴ３１００にマルチキャストグループ識別を有する。
【０１８０】
図３９は、各階層に対するＦＮのマルチキャスト転送機能の一例を示す。制御パケット３９３０が、ＵＤＰを通じて、アプリケーション層３９１０で実行しているマルチキャストプロセッサ３９１５に配信される。上述した方法のいずれかを使用するマルチキャスト
プロセッサ３９１５は、ＩＰマルチキャスト転送モジュールの一部である、ＩＰ層３９０５に実装されるマルチキャスト転送テーブル（ＭＦＴ）３１００を更新することができる。マルチキャストデータパケット入力３９３５は、最初にＭＡＣ層３９００によって受信され、ＩＰ３９０５に転送されて、そのマルチキャストデータパケット入力３９３５を中継するべきであるか又は除去するべきであるかがＭＦＴ３１００に基づいて判定される。この、ＭＦＴ３１００は、マルチキャストプロセッサ３９１５によって更新される。データパケット入力３９３５が転送されるべきであると判定されると、ＦＮ２４１０はパケットをマルチキャストデータパケット出力３９４０として転送する。マルチキャスト制御パケット３９３０及びマルチキャストデータパケット入力３９３５は、ＭＡＣ層３９００により除去されない。全マルチキャスト（AllMulticast）モードをＭＡＣ層３９００で有効にして、ＭＡＣのすべてのマルチキャストフレームを受け入れ可能、すなわちＭＡＣ層３９００によって除去せずにＩＰ層３９０５に転送可能、とする必要がある。インタフェース上で全マルチキャストモードを有効にすることにより、ネットワークへのすべてのマルチキャストパケット（パケットのマルチキャストアドレスに関わらず）がインタフェースによって受信される。全マルチキャストモードが有効でない場合、インタフェースは、マルチキャストアドレスがインタフェースに割り当てられているものと一致するマルチキャストパケットのみを受け入れる。
【０１８１】
図４０は、本発明の一実施形態によるＦＮ２４１０の転送機能のフローチャートを示す。最初、ステップ４０００においてＦＮ２４１０はアイドル状態である。ステップ４００５において、ＦＮ２４１０は、マルチキャストデータパケット入力３９３５を受信する。次に、ステップ４０１０において、ＩＰ層３９０５は、マルチキャストグループ２４００がＭＦＴ３１００にあるか否かを判定する。ＩＰ層３９０５は、マルチキャストデータパケット入力３９３５からのマルチキャストグループ２４００のＩＰアドレスを、ＭＦＴ３１００に格納されているＩＰアドレスと比較する。比較の結果に基づき、ＦＮは、ステップ４０１５においてマルチキャストデータパケット入力３９３５を破棄するか、又はマルチキャストデータパケット入力３９３５がＦＮ２４１０によってすでに送信されているか否かを判定する。各ＦＮ２４１０には、メモリに格納された、送信されるすべてのマルチキャストデータパケット入力３９３５に対する送信済みリストを有する。特に、送信済みリストは、事前設定された期間内に送信されるすべてのマルチキャストデータパケット入力３９３５に対する識別を含む。パケット識別は、マルチキャストデータパケット入力３９３５のソースアドレスと、ＩＰパケットヘッダからの識別情報とを含む。この事前設定された期間を、送信済みリストが過度に大きくならないように制御することができる。送信済みリストの機能は、重複するマルチキャストパケット伝送を防止することである。したがって、マルチキャストデータパケット入力３９３５は、短期間だが、パケットが重複でないことを確実にするには十分長いだけの間、送信済みリストに列挙されるだけでよい。ステップ４０２０において、ＩＰ層３９０５は、受信したマルチキャストデータパケット入力３９３５に対する、ソース、すなわちＩＰヘッダのソースＩＰアドレス、及びＩＤ、すなわちＩＰヘッダの識別を、送信済みリストのソース及び識別と比較することにより、マルチキャストデータパケット入力３９３５がすでに送信されているか否かを判定する。一致がある場合、ＦＮ２４１０は、ステップ４０１５においてマルチキャストデータパケット入力３９３５を破棄し、ステップ４０００においてアイドル状態になる。一致がない場合、マルチキャストデータパケット入力３９３５は先に送信されておらず、ステップ４０２５において、ＦＮ２４１０はマルチキャストデータパケット入力３９３５を送信する。ステップ４０２５において、ＦＮ２４１０はまた、送信済みリストを、マルチキャストデータパケット入力３９３５からのソース及びＩＤを送信済みリストに追加することによって更新する。
【０１８２】
本発明の別の実施形態では、同じ場所に位置するＦＮによる重複パケットの不要な伝送を防止するため（それは帯域幅の浪費である）、同じ場所に位置するＦＮの１つを除くす
べてが、マルチキャストデータパケット入力３９３５を送信しないように、すなわちパケットを中継しないようにする。同じ場所に位置するＦＮは、同じ無線範囲、すなわち同じホップ内のＦＮである。重複マルチキャストパケットは、同じマルチキャストデータパケット入力３９３５が、２つの異なるＦＮによって同じソースから同じ受信者に送信される場合に送信される。
【０１８３】
この実施形態によれば、ＦＮ２４１０は、マルチキャストデータパケット入力３９３５を受信すると、マルチキャストデータパケット入力３９３５があるかＭＡＣバックオフ待ち行列（MAC back-off Queue）を検査する。マルチキャストデータパケット入力３９３５は、待ち行列に存在する場合、当該待ち行列から除去され、パケットの送信は発生せず、すなわち、ＦＮ２４１０は、パケット送信のバックオフ期間中にパケットを受信する場合、送信を阻止する。ＩＰ層（ＩＰ転送モジュール）は、ＭＡＣに対しこうした阻止を行うように通知しなければならない。
【０１８４】
図４１は、層間動作、すなわちＭＡＣ層３９００及びＩＰ層３９０５に対する本発明のこの実施形態によるＦＮ２４１０の転送プロセスのフローチャートを示す。特に、図４１は、ＦＮ２４１０に対する層毎の転送ステップを示している。
【０１８５】
最初に、ＦＮ２４１０はマルチキャストデータパケット（図４１ではＭＰ［ｓ：ｇ］として参照）を受信する。パケットＭＰ［ｓ：ｇ］は、処理されるためにＩＰ層３９０５に転送される。ステップ４１０５において、ＩＰ層３９０５は、マルチキャストグループ２４００がＭＦＴ３１００にあるか否かを判定する。ＩＰ層３９０５は、ＭＰ［ｓ：ｇ］からのマルチキャストグループ２４００のＩＰアドレスをＭＦＴ３１００に格納されているＩＰアドレスと比較する。マルチキャストＩＰアドレスがＭＦＴ３１００のマルチキャストＩＰアドレスと一致しない場合、ステップ４１１０においてＩＰ層はＭＰ［ｓ：ｇ］を破棄する。マルチキャストＩＰアドレスがＭＦＴ３１００のマルチキャストＩＰアドレスと一致する場合、ステップ４１１５において、ＩＰ層３９０５は、ＭＰ［ｓ：ｇ］が送信されたか否かを判定する。次に、ＩＰ層３９０５は、受信したＭＰ［ｓ：ｇ］のソース及びＩＤを送信済みリストのソース及びＩＤと比較することにより、ＭＰ［ｓ：ｇ］がすでに送信されているか否かを判定する。一致がある場合、ＩＰ層３９０５は、ステップ４１２０において、ＭＰ［ｓ：ｇ］を破棄し、ステップ４１２５において、ＭＰ［ｓ：ｇ］がＭＡＣ層の送信バックオフ待ち行列にすでにあるか否かを判定する。パケットが送信バックオフ待ち行列にない場合、ステップ４１４５において、ノードはアイドル状態となる。一致がある場合、ＭＰ［ｓ：ｇ］は送信バックオフ待ち行列にあり、ステップ４１３０において、ＭＡＣ層は送信バックオフ待ち行列からパケットを削除する。送信済みリストに一致がない場合、ＭＰ［ｓ：ｇ］は送信済みリストに追加され、ステップ４１３５において送信のために送信バックオフ待ち行列に追加される。ステップ４１４０において、ＭＰ［ｓ：ｇ］は転送される。
【０１８６】
別の実施形態では、メッセージを中継する効率を向上させ且つ適時の配信を確実にするために、受動応答が追加される。上述した実施形態では、ノードから、パケットが受信されたという応答はない。したがって、リーフノードがパケットを受信したという確証はない。したがって、パケットが再送信されるべきであるという指示はない。
【０１８７】
この実施形態によれば、ＦＮ２４１０は、パケットを送信した後、隣接するＦＮによってパケットが二度目の転送をされるのを待つ。隣接するＦＮ２４１０がパケットを転送すると、最初のＦＮ２４１０がパケットを受信する。この受信パケットは、隣接するＦＮが最初の転送を受信したという受動応答である。事前設定された期間内に応答が受信されない場合、最初のＦＮはパケットを再送信することができる。
【０１８８】
図４２は、層間動作、すなわちＭＡＣ層３９００及びＩＰ層３９０５に対する、本発明のこの実施形態によるＦＮ２４１０の、受動応答を含む転送プロセスのフローチャートを示す。特に、図４２は、ＦＮ２４１０に対する層毎の転送ステップを示す。
【０１８９】
ステップ４２０５〜４２１５は先の実施形態と同じであり、したがって、再び詳細には説明しない。ステップ４２１５において、パケットＭＰが既に送信されている場合、ステップ４２２０において、新たなＭＰは破棄される。ステップ４２１５においてパケットＭＰが送信されていない場合、ステップ４２３５において、ノードは、パケット識別を送信済みリストに追加し且つ宛先をリストに追加することにより、送信済みリストを更新する。さらに、ノードは、応答タイマをセットし且つ応答ステータスパラメータを実行中にセットする。さらに、ステップ４２３５において、ノードは、パケット（ＭＰ）を待ち行列に入れるためにＭＡＣ層３９００に送信する。任意に、ノードは、パケットが所定期間内に特定のグループに送信される回数をカウントする送信済みカウンタをインクリメントすることができる。ステップ４２４０において、パケット（ＭＰ）は送信バックオフ待ち行列に追加される。
【０１９０】
パケットが既に送信されており、且つ新たなＭＰが破棄された場合、ステップ４２２５において、ノードは、応答のステータスを判定し、すなわちパケットが応答されたか否かを判定する。送信パケットが所定時間内に受信される場合、パケットは応答される。ステータスが実行中である、すなわち未応答の場合、ステップ４２３０において、ノードは応答タイマを停止させ、応答ステータスを応答済みに変更する。ステータスが応答済みである場合、ステップ４２６５においてノードはアイドル状態になる。同時に、ノードは、応答タイマを監視して、応答を受信することなくタイマが満了するか否かを判定する。パケットを受信することなく応答タイマが満了した場合、ステップ４２６０において、ノードはパケットを再送信する。さらに、ステップ４２６０において、ノードは、応答タイマをリセットし、応答ステータスを「実行中」として維持する。ステップ４２４０において、パケットは送信バックオフ待ち行列に追加される。
【０１９１】
一般に、移動車両１１０は、単一チャネル伝送又は複数チャネル伝送のいずれかを使用してパケットを転送することができる。複数チャネル伝送の場合、移動車両は、複数の宛先受信機と共に１つの送信機を使用するか又は１つの送受信機を使用することができる。前者の場合、移動車両１１０は、２つのチャネルのうちのいずれか一方のみで送信し、両方のチャネルを通じて受信することができる。しかしながら、同じチャネルで同時に送受信することはできない。後者の場合、移動車両１１０は、特定のチャネルを通じての送受信に制限されるが、送信チャネル及び受信チャネルは同じである必要はない。
【０１９２】
好ましい実施形態では、複数のチャネルを使用して送信が行われる。マルチキャストの場合、ＦＮ及びリーフノードは、マルチキャストパケットを送受信するためにチャネル（複数可）を能動的に選択する。マルチチャネルシステムでは、スループットが増大し、遅延が低減する。しかしながら、マルチチャネルシステムでは、ＦＮ４２１０間で事前のチャネル調整が必要である。
【０１９３】
本発明の一実施形態では、ＦＮ４２１０は、マルチキャスト転送がチャネル交互転送（Channel-alternate Forwarding）であるようにマルチチャネル環境を調整する。ＦＮは、送信チャネル及び受信チャネルを交互のパターンに構成することにより、送信チャネル及び受信チャネルが常に異なるようにする。すなわち、ＦＮ２４１０は、ＣＨＡからマルチキャストパケットを受信する場合、ＣＨＢを通じてマルチキャストパケットを転送し、またその逆も同様である。
【０１９４】
図４３は、本発明のこの実施形態によるチャネル交互転送割当ての一例を示す。図４３
に示すように、２つのチャネルＣＨ１ ４３１０及びＣＨ２ ４３２０がそれぞれある。６つのＦＮ、ＦＮ１〜ＦＮ６（２４１０_１〜２４１０_６）がある。ＦＮ間の陰付きエリアは、５つの無線有効範囲領域を示している。各ＦＮ、すなわちＦＮ１〜ＦＮ６（２４１０_１〜２４１０_６）は、ＣＨ１ ４３１０及びＣＨ２ ４３２０を介してパケットを送受信することができる。しかしながら、パケットは、ＣＨ１ ４３１０で受信される場合、ＣＨ２を通じて転送される。同様に、パケットは、ＣＨ２ ４３２０で受信される場合、ＣＨ１ ４３１０を通じて転送される。したがって、線形に接続されたＦＮ２４１０は、２つのチャネルを交互に使用する。
【０１９５】
移動車両１１０が単一チャネル受信デバイスを有する場合、送信チャネル及び受信チャネルの交互の配置は、ハートビート制御パケット１７００及びＭＲ１８００の送受信を通じて達成される。ハートビート制御パケット１７００は、チャネル情報、すなわちＧＨ１３００に対する送信チャネル及び受信チャネルを有する。ハートビート制御パケット１７００は、ブロードキャストされてすべてのＦＮによって受信される。ＧＨ１３００に最も近いＦＮ、すなわち、ＧＨへの最小ホップカウントは、まず、ハートビート制御パケット１７００の情報に基づいてそれらのチャネルを設定する。これらのＦＮの送信チャネル及び受信チャネルは、ＧＨのチャネルと交互になるように選択される。最も近いＦＮがそれらのチャネルを設定すると、次に近いＦＮがそれに従ってそれらの送信チャネル及び受信チャネルを割り当てる。これは、すべてのＦＮに対してチャネルのすべてが設定されるまで続く。
【０１９６】
図４４は、この実施形態による送信チャネル及び受信チャネルのチャネル割当ての一例を示す。図４４は、図４３に示すものと同じＦＮを使用する。ＦＮ４ ２４１０_４がＧＨ１３００である。ＧＨ１３００は、それ自体に、送信チャネル１ Ｔ−ＣＨ１及び受信チャネル２（Ｒ−ＣＨ２）を割り当てる。ＧＨ／ＦＮ４ ２４１０_４は、送信チャネル情報及び受信チャネル情報を含むそのハートビート制御パケット１７００をブロードキャストする。ＦＮ３ ２４１０_３及びＦＮ５ ２４１０_５は、それらの送信チャネル及び受信チャネルをＧＨ／ＦＮ４ ２４１０_４と交互になるように割り当てる。ＦＮ３ ２４１０_３及びＦＮ５ ２４１０_５は、それらの送信チャネル及び受信チャネルとしてそれぞれＴ−ＣＨ２及びＲ−ＣＨ１を割り当てる。そして、ＦＮ２ ２４１０_２及びＦＮ６ ２４１０_６は、ハートビート制御パケットの情報及びＧＨからのホップカウントに基づいてそれらの送信チャネル及び受信チャネルを割り当てる。ＦＮ２ ２４１０_２及びＦＮ６ ２４１０_６は、Ｔ−ＣＨ１及びＲ−ＣＨ２を割り当てる。最後に、ＦＮ１ ２４１０_１が、その送信チャネル及び受信チャネルを割り当てる。ＦＮ１ ２４１０_１は、Ｔ−ＣＨ２及びＲ−ＣＨ１を割り当てる。移動車両１１０が２チャネル受信デバイスを有する場合、上述した割当ては不要である。すべてのＦＮ２４１０が、ＣＨ１又はＣＨ２のいずれかで送信し両チャネルで受信することができる。
【０１９７】
受信されたマルチキャストパケットのチャネル情報は、ＭＡＣ層３９００のチャネルアクセスモジュールから提供される。着信マルチキャストパケットにはまず、受信チャネルがマークされている。これにより、マルチキャストパケットが、識別され受信チャネルとは異なる送信チャネルで転送されることが可能となる。マルチキャストパケットにＣＨ１がマークされている場合、マルチキャストパケットはＣＨ２を通じて転送される。リーフノード２４０５は、その送信チャネル及び受信チャネルを、内部チャネルアクセスメカニズムを介してそれらのＦＮ２４１０と同期させる。
【０１９８】
単一チャネルの交互転送プロセスにより、パケットが同じチャネルで同時に受信される場合、すなわち、ＦＮ３ ２４１０_３がチャネル１でＦＮ４ ２４１０_４及びＦＮ２ ２４１０_２の両方からパケットを受信する場合、隠れ端末問題がもたらされる可能性がある。
【０１９９】
別の実施形態では、送信チャネル及び受信チャネルは二重チャネル交互方法（double channel alternate manner）で割り当てられる。二重チャネル交互転送チャネル割当てには、隠れ端末状態が回避されるという利点がある。この方法は、送信チャネルを二重交互パターンに配置する。それは、排他的な送信チャネルの領域をもたらし、そうした領域を二重交互パターンに配置する。同じ送信チャネルでの排他的領域が２ホップ毎に現れる。ＦＮ２４１０は、両チャネルを通じてマルチキャストパケットを受信することができる。マルチキャストパケットは、受信されると、所与の送信チャネルを通じて転送される。
【０２００】
図４５は、ＦＮメッシュに対するこの実施形態による送信チャネル及び受信チャネルのチャネル割当ての一例を示す。図４５は、図４３に示すものと同じＦＮ、すなわちＦＮ１〜ＦＮ６（２４１０_１〜２４１０_６）を使用する。この例では、チャネルは、Ｔ−ＣＨ１
４５００に対して１つの排他的な送信チャネルエリアがあるように割り当てられる。Ｔ−ＣＨ２ ４５２０に対して２つの排他的な送信チャネルエリアがある。さらに、２つの混合チャネルエリア４５１０がある。ＦＮ１ ２４１０_１及びＦＮ２ ２４１０_２はＴ−Ｃｈ２で送信し、ＦＮ３ ２４１０_３及びＦＮ４ ２４１０_４はＴ−ＣＨ１で送信し、ＦＮ５ ２４１０_５及びＦＮ６ ２４１０_６はＴ−ＣＨ２で送信する。各ＦＮ、すなわちＦＮ１〜ＦＮ６（２４１０_１〜２４１０_６）は、Ｒ−ＣＨ１又はＲ−ＣＨ２のいずれかで受信することができる。
【０２０１】
図４６は、本発明の一実施形態による受信チャネル及び送信チャネル両方のチャネル割当てのフローチャートを示す。ステップ４６００において、ＧＨ１３００は、それ自体の送信チャネル、すなわちＴ−ＣＨ１を指定する。この送信チャネルは、残りのＦＮ２４１０がそれらの送信チャネルを設定するための基準送信チャネルとして使用される。そして、ステップ４６０５において、ＧＨ１３００は１つの分類方向（たとえば赤又は青）を選択する。選択された分類方向は、基準分類方向として使用される。そして、ステップ４６１０において、ＧＨ１３００は、ハートビート制御パケット１７００をすべてのＦＮ２４１０にブロードキャストする。この実施形態では、基準送信チャネル及び分類方向の情報はハートビート制御パケット１７００に含まれる。
【０２０２】
ステップ４６１５において、他のすべてのＦＮ２４１０が、ハートビート制御パケット１７００を受信し、基準送信チャネル、分類側及びＧＨからのホップ距離の情報に基づいて、それらの自体の送信チャネルを事前に割り当てる。ＦＮ２４１０は、基準側内に位置する（すなわち、基準分類方向及びＦＮの両分類が同じである）場合、式ｍｏｄ（ｉｎｔ［（１＋ｈ）／２］，２）に基づいてそれらの送信チャネルを判定する。ここで、ｍｏｄ（ａ，ｂ）はａをｂで割った正の剰余（reminder）であり、ｉｎｔ［］は数字の小数点以下を切り捨て、ｈはＧＨからのホップ距離である。ＦＮ２４１０は、基準分類方向ではない側に位置する場合、式ｍｏｄ（ｉｎｔ［ｈ／２］，２）を使用してそれらの送信チャネルを判定する。式の出力が１（いずれの場合でも）の場合、ＦＮ２４１０は基準送信チャネルとは異なるものとしてそれらの送信チャネルを割り当て、すなわち基準送信チャネルがＴ−ＣＨ１である場合、それらの送信チャネルをＴ−ＣＨ２として設定する。式の出力が０である場合、それらはそれらの送信チャネルを基準送信チャネルとして設定する。
【０２０３】
ＦＮ２４１０は、メモリに格納されているＧＨへのホップカウント情報とハートビート制御パケット１７００からの受信情報とを使用して、二重交互パターン割当てに従ってそれらの送信チャネルを割り当てる。
【０２０４】
マルチキャストルーティング及びユニキャストルーティングを別々のプロセスとして説明したが、これらのルーティング方法の両方を共に同じ移動車両１１０によって実行することができる。したがって、受信パケットは、一方のルーティング方法に関連しなくても
よいが、別のルーティング方法に関連することになる。したがって、制御パケットが無視されるように記述されており、特定のルーティングプロセスに対してノードがアイドル状態となっている場合、パケットを、他方のルーティングプロセスに対して無視しなくてもよく、ノードはアイドル状態にならなくてもよい。たとえば、ユニキャストルーティングの場合、ハートビート制御パケット１７００及びＭＲ１８００の両方を使用してルーティングテーブル２３００が更新されるが、実施形態に応じて、マルチキャストルーティングの場合、２つの制御パケットのうちの一方のみを必要としてもよい。
【０２０５】
さらに、ユニキャストルーティングプロセス及びマルチキャストルーティングプロセスを、主に移動車両及び移動ノードに関して説明したが、任意ノード、たとえばＲＳＵ１００によって実行することができる。
【０２０６】
移動車両の無線通信デバイスは、上述したプロトコル及び方法、たとえばユニキャスト及びマルチキャストを実行する。この無線通信デバイスは、図１１に示すようなＲＳＵ１００の通信デバイスと同様である。無線通信デバイスは、無線有効範囲におけるノード間の無線通信を提供するために、ブロードキャスト手段又は無線送受信機のような送受信手段を備える。さらに、制御手段、たとえばマイクロコントローラ、マイクロプロセッサ等が、送受信手段を通じて他のノードから信号を受信し、送受信手段を通じて他のノードに信号を送信するように構成される。制御手段はまた、上述したプロトコルをプロセッサ実行可能命令として実行することにより動作制御を提供する。記憶手段が、無線通信デバイス内に且つ制御手段と動作的に通信するように配置されている。記憶手段は、メモリモジュール、リムーバブルメディア、複数の記憶デバイスの組合せ等であってもよく、説明した実施形態のプロトコルを実行するために必要なプロセッサ実行可能命令を格納するようなサイズである。さらに、タイミング手段が、別個のコンポーネントとして又は制御手段の機能として提供される。タイミング手段は、説明した実施形態において言及したタイマのそれぞれに必要な時間間隔追跡を提供する。電源のような通電手段が無線通信デバイスのすべてのコンポーネントに電気的に接続されることにより、必要に応じてコンポーネントに動作電力を提供する。
【０２０７】
説明した実施形態を実行するためのプロセッサ実行可能命令を、ＥＰＲＯＭ、フラッシュメモリ又は他のこうした不揮発性記憶装置のような形態で記憶手段に組み込んでもよい。さらに、プロセッサ実行可能命令を、光媒体又は磁気媒体のようなコンピュータ可読媒体に格納してもよく、又はネットワーク（たとえばインターネット）によってダウンロード可能としてもよい。プロセッサ実行可能命令を、追加の拡張機能を利用可能となるとシステムに提供するために、必要に応じて、ユーザが定期的に更新することができることが好ましい。
【０２０８】
＜ＲＳＵを介するＬＰＧ間ルーティングサービス＞
本発明の一実施形態では、ＲＳＵ１００は、その無線有効範囲内の複数のＬＰＧ１１５間でパケットを中継することができる。この実施形態では、ＲＳＵ１００は、１つの特定のＬＰＧ１１５の一部ではない。ＲＳＵ１００は、ＲＳＵ無線有効範囲内の他のＬＰＧ１１５に情報をユニキャスト又はマルチキャストで伝播するために、複数のＬＰＧ１１５によって、境界ノードとして使用される。ＧＨ１３００、ＦＮ２４１０、ＧＮ１５００は、すべてのＬＰＧ間パケットをユニキャスト又はマルチキャストでＲＳＵ１００に転送する。そして、ＲＳＵ１００は、パケットを適当なＬＰＧ１１５又はノードに中継する。各ＬＰＧ１１５内では、各ノードは、上述したルーティングプロセスを使用して互いに通信する。ＲＳＵ１００は、互いにリンクされて情報を共有することが可能である。リンクされたＲＳＵ１００は、情報を、多数の局所ＬＰＧ１１５に達するように、隣接するＲＳＵ１００に中継する。バックボーンネットワークへのエッジノードであるＲＳＵ１００は、ＬＰＧ１１５間パケットを多数のＬＰＧ１１５及びこうした情報を収集するバックボーンサ
ーバに中継することができる。
【０２０９】
この実施形態によれば、ＲＳＵ１００は、単にＬＰＧ間中継ノードであって、ＬＰＧ１１５のメンバではない。これにより、ＲＳＵ１００を組み込むためのＬＰＧ１１５における編成及び役割割当て時間が低減する。ＲＳＵがＬＰＧ１１５に完全には関係していないため、初期ＬＰＧ構造が維持される。さらに、ＲＳＵ１００有効範囲内のＬＰＧ１１５内の移動車両１１０に対する境界ノード（ＢＮ）の選択プロセスが排除される。しかしながら、ＲＳＵエリア外になると、境界ノードは必要となる。ＬＰＧ１１５及び個々の車両は、ＲＳＵをいくつかの方法で発見する。車両はＲＳＵ１００の事前知識を有することができ、それにより前もってＬＰＧ間中継を識別することができる。この知識は、他のＲＳＵ１００（リンクされたＲＳＵの場合）により又は恐らくは先行する移動車両１１０により提供される。さらに、ＲＳＵ位置および情報を移動車両１１０において事前構成することができ、又はＲＳＵ１００を、ＬＰＧ間中継ノードとして指定しているＲＳＵ１００からのビーコンを介して動的に発見することができる。
【０２１０】
ＲＳＵ１００は、ＧＨ１３００からハートビート制御パケット１７００をリスンすることにより、そのエリア内のＬＰＧ１１５を追跡することができる。移動車両１１０又はノードは、Ｖ−Ｒチャネル及びＶ−Ｖチャネルの両方によってハートビート制御パケット１７００を送信する。Ｖ−Ｖチャネルは、ＬＰＧ内関連トラフィックに対して排他的に使用されるが、Ｖ−Ｒチャネルは、ＬＰＧ間トラフィックに使用される。
【０２１１】
＜他のＲＳＵサービス＞
ＲＳＵ１００を、複数のネットワークサービス及び車両サービスに使用することができる。たとえば、ＲＳＵ１００は、ノードに対する認証支援、ＲＳＵの位置及びＩＰアドレスのようなネットワーク情報収集、ＬＰＧ１１５及びＲＳＵ１００接続に対する構成支援、並びに移動ノードローミング支援を提供することができる。さらに、ＲＳＵ１００を、車両安全警告、ＲＳＵベース位置決め、車両整備情報、通行料収集、並びにエリア内の商品及びサービスに関する位置情報に使用することができる。上述したサービスのいくつかはバックボーンなしに機能することができるが、他のサービスはバックボーン接続が必要である。
【０２１２】
一実施形態では、ＲＳＵ１００は、移動車両１１０に対するネットワーク認証をサポートする。図４７は、認証プロセスをサポートするＲＳＵ１００の一例を示す。遠隔の認証／検証局（certification/validation authority）（ＣＡ／ＶＡ）４７００が、認証され許可されたノード４７０５のリストを保持し、認証サービスを提供する。通常、ネットワークに入る各ノードは、ＣＡ／ＶＡ４７００により個々に自身を認証する。しかしながら、移動度の高い環境では、移動車両が短い接続期間しかＣＡ／ＣＡ４７００の範囲内にないため、短期間、すなわち、ノードがＣＡ／ＶＡ４７００又は別の標準固定ノードの無線有効範囲内にある間に、認証を実行しなければならない。本発明のこの実施形態によれば、ＲＳＵ１００は、ＧＨ１３００がＲＳＵ１００と通信している間、すなわちＲＳＵ１００の無線サービスエリア内にある間に、ＧＨ１３００に対し認証情報をオフロードすることによってＣＡ／ＶＡ４７００を支援する。図４７において、破線は、ＲＳＵ１００の無線サービスエリアを示している。リストがＧＨ１３００にオフロードされた後、ＧＨ１３００はＣＡ／ＶＡ４７００のように作用する。ＧＨ１３００は、ハートビート制御パケット１７００及びＭＲ１８００を使用して他のノードを認証する。したがって、ＬＰＧ１１５がＲＳＵ１００の無線有効範囲内にない時に、引き続き認証プロセスを行うことができる。この実施形態では、ハートビート制御パケット１７００及びＭＲ１８００は、認証プロセスのためのパラメータを含むように変更される。しかしながら、認証プロセスに対し他のいかなる変更又はオーバーヘッドも不要である。ＧＨ１３００は、ＬＰＧ１１５のメンバをまとめて認証することができる。図示するように、ＧＨ１３００は、移動車両１１
０_１〜１１０_９及び移動車両１１０_１１を認証するが、移動車両１１０_１０は拒否しており、すなわち、移動車両１１０_１０は禁止されている。ＧＮ１５００は、ＧＨ１３００を使用して認証することができない場合、ＲＳＵ１００を直接使用してＣＡ／ＶＡ４７００で認証を完了するようにすることができる。この冗長性メカニズムは、リストのオフロード又は認証ハンドシェイクが完了する前にＧＨ１３００がＬＰＧ１１５又はＲＳＵ１００の範囲外に移動する場合を考慮する。
【０２１３】
別の実施形態では、ＲＳＵ１００を使用して、ネットワーク構成プロセス及びＬＰＧ１１５形成を支援することができる。特に、ＲＳＵ１００は、ネットワーク内の他のＲＳＵ１００及びその無線有効範囲内のすべてのＬＰＧ１１５を認識しているため、近づいているＲＳＵ１００に対して移動車両１１０を事前構成するか又はＬＰＧ１１５形成を支援することができる。ネットワーク構成パラメータは、タイムスロット割当て、チャネル割当て、近づいている、すなわちダウンストリームＲＳＵ１００のＩＰアドレス及びＥＳＳＩＤを含むことができる。
【０２１４】
ＲＳＵ１００はまた、ＬＰＧ１１５に対するＶ−Ｖチャネルの割当てを支援し、移動車両１１０が参加するＬＰＧ１１５を見つけるのを支援することも可能である。さらに、ＲＳＵ１００は、ＬＰＧ１１５の併合及び分割を支援することができる。
【０２１５】
図４８は、ＬＰＧ整備、形成を支援し、ネットワーク構成支援を提供する複数のＲＳＵ１００の一例を示す。
【０２１６】
ＲＳＵ２ １００_２は、ＲＳＵ１ １００_１のネットワーク設定に対し移動車両１１０_７〜１１０_１１を事前構成することができる。これは、接続遅延時間の低減に役立ち、ＲＳＵ１ １００_１の無線サービスエリア内に入るノードに対しより有効な通信時間を与える。陰付きエリアは、ＲＳＵ１００の無線サービスエリアを示している。たとえば、ＲＳＵ２ １００_２は、移動車両１１０_７に対して事前構成設定をブロードキャストする。この情報を、ＬＰＧ１１５内の他の移動車両１１０に中継することができ、又はＲＳＵ１００から直接受信することができる。ＲＳＵ１００事前構成支援を使用して、ノードは、さまざまなＲＳＵエリアを通過して移動する際に、ネットワーク全体との仮想接続を維持することができる。ＲＳＵ２ １００_２は、移動車両が走行していた方向を認識する必要があるため、適当なダウンストリームＲＳＵ１００、すなわち図４８におけるＲＳＵ１ １００_１を判定することができる。図４８はバックボーン２００の無いネットワークを示しているが、ネットワークは、すべてのＲＳＵ１００構成パラメータのデータベースを含むバックボーンを含んでもよい。
【０２１７】
さらに、ＲＳＵ１００は、チャネル干渉を回避するようにＬＰＧ内通信に対しＶ−Ｖチャネルを選択することができる。ＲＳＵ１００は、Ｖ−Ｒチャネルを使用して、ＬＰＧ１１５に対し、いずれのチャネルを使用することができるかを通知する。ＲＳＵ１００は、チャネル割当てをメンバに中継するためにＧＨ１３００に送信する。たとえば、ＬＰＧ１
１１５_１に対し、ＲＳＵ１ １００_１によりチャネルＡを割り当てることができ、それをこの情報を移動車両１１０_２にブロードキャストすることによって行うことができる。同様に、ＬＰＧ２ １１５_２に対しＲＳＵ１ １００_１によってチャネルＢを割り当てることができ、それをこの情報を移動車両１１０_５にブロードキャストすることによって行うことができる。移動車両１１０_１及び１１０_５は、各それぞれのＬＰＧ１１５内の他の車両に対してメッセージを中継する。
【０２１８】
ＲＳＵ１００は、ＬＰＧ１１５の移動度による競合を検出すると、ＬＰＧ１１５に対し更新したチャネル割当てを送信することができる。これは、干渉を防止し、形成済みのＬＰＧ１１５と新たに作成されたＬＰＧ１１５との両方を支援する。新たに作成されたＬＰ
Ｇ１１５の場合、ＲＳＵ１００はその新たに作成されたＬＰＧ１１５に対し利用可能なチャネルを割り当てる。
【０２１９】
さらに、ＲＳＵ１００は、移動車両１１０がＬＰＧ１１５を見つけるのを支援することができる。ＲＳＵ１００は、ＬＰＧ識別、チャネル割当て及びＶ−Ｒチャネルを使用するメンバの数のような、ＬＰＧ１１５に関する情報をブロードキャストすることができる。たとえば、ＲＳＵ１ １００_１は、ＬＰＧ１ １１５_１及びＬＰＧ２ １１５_２に対し移動車両１１０_６にこの情報をブロードキャストすることができる。この実施形態では、新たなメンバは、ハートビート制御パケット１７００をヒアリングする前にＬＰＧ１１５に参加することができる。ＲＳＵ１００は、分離されている場合、ＲＳＵ１００毎に局所的なＬＰＧ１１５の形成、すなわち無線サービスエリア内の車両及びＬＰＧ１１５しか支援することができない。しかしながら、ＲＳＵ１００がリンクされている場合、１つのＲＳＵ１００から別のＲＳＵ１１０に移動している新たな移動車両１１０を、ＲＳＵ１００を介して別のＬＰＧに参加するように事前構成することができる。
【０２２０】
ＲＳＵ１００は、２つのＬＰＧ１１５の併合を制御することができる。ＲＳＵ１００は、ＧＨの１つに、ＧＨ１３００に対しハートビート制御パケット１７００のブロードキャストを停止することを要求する制御パケットをブロードキャストし、ハートビート制御パケット１７００の配信範囲（ホップカウント）を拡張するように他のＧＨを呼び出して、他のＬＰＧ１１５の移動車両１１０が範囲拡張されたハートビート制御パケット１７００をヒアリングしＬＰＧ１１５に参加することができるようにする。同様に、ＲＳＵ１００は、１つのＬＰＧ１１５の分割を制御することができる。
【０２２１】
別の実施形態では、ＲＳＵ１００は、一時的なメッセージリポジトリ及び情報収集デバイスとしての役割を果たすことができる。すべての通過する移動車両１１０が、他の移動車両１１０が取り込むことができるようにＲＳＵ１００に情報を預けることができる。ＲＳＵ１００は、その局所エリアの情報を収集し集約する。さらに、ＲＳＵ１００は、他のＲＳＵ１００にリンクされている場合、局所的に収集された情報を共有することができる。さらに、バックボーン２００に接続されている場合、情報をバックボーン２００に中継して格納することができる。
【０２２２】
収集される情報は、交通情報、事故警告、気象情報及び道路状態に及んでもよい。この情報を、要求なしに通過する移動車両１１０にブロードキャストすることができる。代替的に、移動車両１１０がこの情報を能動的に要求してもよい。ＲＳＵ１００が分離されている場合、移動車両は、移動車両１１０が出くわす各ＲＳＵ１００に対し同じ情報をアップロードする必要がある。情報はまた、移動車両１１０が出くわす他のＲＳＵ１００に関する情報を含むことにより、ＲＳＵ１００のデータベースを構築し、すなわち通過する移動車両１１０を介して他のＲＳＵに関して学習することも可能である。
【０２２３】
図４９は、２つのリンクされたＲＳＵ（ＲＳＵ１ １００_１及びＲＳＵ２ １００_２）による情報収集プロセスの一例を示す。ＲＳＵ１ １００_１及びＲＳＵ２ １００_２は、接続４００によってリンクされている。この接続４００は、有線接続であっても無線接続であってもよい。両ＲＳＵ１ １００_１及びＲＳＵ２ １００_２は、Ｖ−Ｒチャネルで収集した情報をブロードキャストする。この実施形態では、ＲＳＵ１００はＬＰＧ１１５のノードではない。個々のノードは、上述したＬＰＧルーティングプロセスを使用して情報を預け且つ受信することができ、又はＶ−Ｒチャネルの情報を直接ブロードキャストすることができる。移動車両１１０は、ビーコンにより預け場所としてＲＳＵ１００を発見する。代替的に、移動車両は、アップストリームＲＳＵを介して他のＲＳＵを発見することができる。図４９に示すように、移動車両１１０_５及び１１０_６は、ＲＳＵ２ １００_２からＲＳＵ１ １００_１を発見することができる。ＲＳＵ１ １００_１は、移動車両１１
０_１〜１１０_４に対する預け場所であり、ＲＳＵ２ １００_２は、移動車両１１０_４〜１１０_６に対する預け場所である。移動車両１１０_４は、両ＲＳＵ１ １００_１及びＲＳＵ２ １００_２に対し情報を預けることができる。ＲＳＵ１ １００_１及びＲＳＵ２ １００_２がリンクされているため、預けられた情報のすべてを、移動車両１１０_１〜１１０_６のすべてが受信することができる。
【０２２４】
別の実施形態では、ＲＳＵ１００を使用して、安全情報を複数のＬＰＧ１１５に中継することができる。図５０は、２つのＲＳＵ、すなわちＲＳＵ１ １００_１及びＲＳＵ２ １００_２に対する安全情報をルーティングするネットワーク構成及び転送プロセスの一例を示す。各ＲＳＵ１００は、ルータ１０３０及び安全警告アプリケーションサービス５０００を含む。安全警告メッセージは、安全警告アプリケーションサービス５０００によって処理される。安全警告アプリケーションサービス５０００は、メッセージのタイプ及びメッセージの内容に従ってメッセージを処理する。それは、メッセージをルーティングすべきか又はメッセージのルーティングを停止すべきかを判定する。
【０２２５】
安全メッセージをルーティングする好ましい実施形態では、ネットワークはバックボーン２００を含む。バックボーン２００は、各ＲＳＵ１００に対するルータを含む。バックボーン２００とＲＳＵ１００との間に、それに応じて情報を仕向けるＲＳＵハブ５０１０がある。
【０２２６】
図５０は、５つのＬＰＧ１１５_１〜１１５_５を示し、それぞれが少なくとも１つの移動車両１１０を有する。図５０は、ＬＰＧ１ １１５_１における事故を示している。安全警告メッセージは、上述したルーティングプロセスのうちの１つに従って、ＬＰＧ内ルーティングを介してＬＰＧ１ １１５_１内で転送される。メッセージはまた、ＬＰＧ間ルーティング手続きを介してＬＰＧ１１５間でルーティングされる。さらに、メッセージは、ＲＳＵ１００及び安全警告アプリケーションサービス５０００を使用してＬＰＧ１１５間でルーティングされる。たとえば、ＬＰＧ１ １１５_１内の１つのノードが、安全メッセージをＲＳＵ１ １００_１にブロードキャストする。ＲＳＵ１００_１は、安全警告アプリケーションサービス５０００_１を使用してメッセージを処理することにより、メッセージが転送されるべきか否かを判定する。ＲＳＵ１ １００_１は、必要な場合に、メッセージをＬＰＧ２ １１５_２及びＬＰＧ３ １１５_３に転送することができる。さらに、ＲＳＵ１
１００_１は、安全メッセージをバックボーン２００に送信する。そして、メッセージは、ＲＳＵハブ５０１０を介してＲＳＵ２ １００_２にルーティングされる。ＲＳＵ２ １００_２は、安全警告アプリケーションサービス５０００_２を使用して安全メッセージを処理することにより、メッセージが転送されるべきか否かを判定する。ＲＳＵ２ １００_２は、メッセージをＬＰＧ４ １１５_４及びＬＰＧ５ １１５_５に転送することができる。図示するように、両ＲＳＵ、すなわちＲＳＵ１ １００_１及びＲＳＵ２ １００_２は、安全メッセージが残りのＬＰＧ１１５_１〜１１５_５に中継されるべきであると判定している。破線は、安全メッセージの中継を表す。
【０２２７】
別の実施形態では、ＲＳＵ１００を使用して、ＧＰＳシステムを使用することなく移動車両１１０の位置を追跡することができる。図５１は、２つのＲＳＵ、すなわちＲＳＵ１
１００_１及びＲＳＵ２ １００_２に対し移動車両１１０の位置を判定するネットワーク構成の一例を示す。この実施形態のネットワーク構成は、図５０に示すような先の実施形態に実質的に類似しているが、各ＲＳＵ１００の安全警告アプリケーションサービス５０００の代りに、位置アプリケーションサービス５１００が含まれている。
【０２２８】
位置アプリケーションサービス５１００は、その位置５１１０、すなわちＲＳＵ１００の位置を周期的にブロードキャストし、各移動車両１１０はその存在をＲＳＵ１００の位置アプリケーションサービス５１００に報告する。移動車両１１０は、報告を、ＭＲ１８
００を介して、Ｖ−Ｒチャネルを介してＲＳＵ１００に直接送信する。代替的に、各移動車両１１０は、ＭＲ１８００をＧＨに送信することができ、ＧＨはＲＳＵ１００に対して集合メッセージを送信する。これにより帯域幅が節約される。ＲＳＵ１ １００_１の無線有効範囲内のいずれの移動車両１１０もエリア１にあり、ＲＳＵ２ １００_２の無線有効範囲内のいずれの移動車両１１０もエリア２内にある。
【０２２９】
位置情報は、位置アプリケーションサービス５１００によりすべてのノードに配布される。位置情報は、他のＲＳＵ１００が使用するためにバックボーン２００に格納される。図５１は、例示のためにＬＰＧ１ １１５_１に向けられている１つのビーコン５１１０を示すが、ビーコン５１１０は、すべてのＬＰＧ１１５及び移動車両１１０にブロードキャストされる。
【０２３０】
この実施形態によれば、移動車両の相対位置、すなわちエリア１対エリア２を追跡することができる。より正確な位置測定のためには、位置追跡のためにリモートＡＰ３３０が使用される。ＡＰ３３０は、位置ビーコン５１１０を送出する。その有効範囲内の移動車両１１０は、ＭＲ１８００で応答する。相対位置情報は、ＲＳＵ１００及び位置アプリケーションサービス５１００に転送される。相対位置を、より狭いエリア、すなわちエリア１、サブＡ内で判定することができる。さらに、より正確な位置追跡のために、ビーコン５１１０及びＭＲ１８００の頻度を増大させることができる。ルータ１０３０からの破線は、他のＬＰＧ１１５_２〜１１５_５に転送されている位置情報を表している。
【０２３１】
この機能は、特に貨物を追跡するために有用である。さらに、それらの機能を使用して、移動ノードを追跡することにより、１対１通信をサポートすることができる。たとえば、ノードがＬＰＧ１１５外に移動する場合、ＬＰＧ１１５は、ノードに関するいかなる情報も有していない。通信の中間のノードは切り離される。したがって、この機能により、ノードは、ＬＰＧ１１５外に移動する際に接続を維持することができる。ＲＳＵ１００は、外部エージェントとしての役割を果たす。この場合、ＲＳＵ１００は、位置情報をバックボーン２００のサーバに送信し、サーバは、この情報を、トラフィックを移動ノードに転送する際に使用するために格納する。
【０２３２】
別の実施形態では、ＲＳＵ１００を、移動車両整備サービスに使用することができる。図５２は、整備サービスに使用される２つのＲＳＵ１００の一例を示す。この構成では、車両整備サーバ５２００がバックボーン２００に設置されている。ＲＳＵ１ １００_１及びＲＳＵ２ １００_２は共にリンクされており、バックボーン２００と通信することができる。移動車両１１０_１はＲＳＵ１ １００_１の無線範囲内にあり、移動車両１１０_２〜１１０_４はＲＳＵ２ １００_２の無線範囲内にある。この実施形態によれば、ＲＳＵ１００は、移動車両１１０から診断情報を受取り、緊急整備情報を提供することができる。診断情報は、車両整備サーバ５２００に送信されて格納される。そして、ＲＳＵ１００は、ガソリンスタンド、病院、タイヤ修理店、給油所等の位置のような情報を提供する。この情報は、上述したプロセス又はＲＳＵ１００の位置に基づいて判定された移動車両１１０の相対位置に基づく。たとえば、移動車両１１０_１は、ガソリンがなくなった場合、ＲＳＵ１００に対し最も近いガソリンスタンドの位置に関する情報を要求することができる。ＲＳＵ１ １００_１は、最も近いガソリンスタンドを判定し、その情報を移動車両１１０_１にブロードキャストする。同様に、移動車両１１０_２は、タイヤがパンクした場合、ＲＳＵ２ １００_２に対し、最も近いガソリンスタンドの位置に関する情報を要求することができる。ＲＳＵ２ １００_２は、最も近いタイヤ交換店を判定し、その情報を移動車両１１０_２にブロードキャストする。
【０２３３】
さらに、移動車両１１０_３にチェックエンジン信号表示が出た場合、移動車両１１０_３は、ＲＳＵ２ １００_２に対し、最も近いガソリンスタンドの位置に関する情報を要求す
ることができる。ＲＳＵ２ １００_２は、最も近いガソリンスタンドを判定し、その情報を移動車両１１０_３にブロードキャストする。ＲＳＵ１００はまた、移動車両１１０_３からの緊急事象を示すレポートを車両整備サーバ５２００に送信し、格納する。
【０２３４】
ＲＳＵ１００はまた、車両整備サーバ５２００の移動車両１１０に関する想起情報をサービスリマインダと共に追跡することもできる。サービスリマインダは、オイル交換、液体補充、タイヤローテーション及び検査を含むことができる。サービスが必要となるたびに、車両整備サーバ５２００からの情報を使用するＲＳＵ１００は、移動車両１１０に対し、サービスが必要であること及びサービスのタイプを示すリマインダを積極的に送信することができる。
【０２３５】
本発明の別の実施形態では、ＲＳＵ１００を使用して、通行料の収集を容易にすることができる。図５３は、通行料の収集に対するＲＳＵ１００構成の一例を示す。通行料収集システムは、バックボーン２００、ＲＳＵ１００及びＡＰ３３０を含む。図示するように、システムは５つのＡＰ３３０_１〜３３０_５を有する。ＲＳＵ１ １００_１は、ハブ３２０を介してＡＰ３３０_１〜３３０_５に接続されている。ＲＳＵ１ １００_１は、ルータ及び通行料収集アプリケーションサービス５３００を含む。ＡＰ３３０のうちの１つ、たとえばＡＰ１ ３３０_１に、通行料スキャンデバイスが設けられている。通行料スキャン領域に入る移動車両は、ＲＳＵ１ １００_１から通行料収集アプリケーションサービス５３００を介して、ＡＰ１ ３３０_１を通じて通行料収集プロセスを開始するために中継される初期通行料収集信号５３０５を受信する。移動車両１１０は、信号を受信すると、車両識別及びクレジットカード番号５３１０のような自身の情報で中継することにより通行料支払い送信を引き起こす。別の実施形態では、クレジットカード番号が不要であるように、クレジットカード番号は先に車両に関連付けられている。通行料収集アプリケーションサービス５３００は、取引を完了する。これらの実施形態によれば、移動車両１１０は通行料を支払うために停止するか又は減速する必要がない。
【０２３６】
たとえば、移動車両１１０_１は、ＡＰ１ ３３０_１の無線有効範囲に入り、通行料スキャンデバイスが移動車両１１０_１を検出し、その検出をＲＳＵ１ １００_１に中継する。通行料収集アプリケーションサービス５３００は、通行料収集パケットを、ＡＰ１ ３３０_１を通じて移動車両１１０_１に送信する。移動車両１１０_１は、識別情報を含む応答をＲＳＵ１ １００_１に送信し、ＲＳＵ１ １００_１は、応答を通行料収集アプリケーションサービス５３００に転送する。通行料収集アプリケーションサービス５３００は取引を完了し、その取引をバックボーン２００に格納する。通行料スキャンデバイスは、ＡＰ３３０のいずれに位置してもよい。
【０２３７】
本明細書では、本発明を特定の例示的な実施形態に関連して説明した。本発明の範囲から逸脱することなく、当業者には何らかの改変及び変更が明らかとなり得る。例示的な実施形態は、例示するものであることが意図されており、添付の特許請求の範囲によって規定される本発明の範囲を限定するように意図されるものではない。

【特許請求の範囲】
【請求項１】
無線アドホックネットワークのローカルピアグループ内のノード間で情報パケットをルーティングする方法であって、
（ａ）グループヘッダノードから、少なくとも１つのルーティングパラメータを含む第１の制御パケットを受信するステップと、
（ｂ）前記少なくとも１つのルーティングパラメータに基づいてルーティングテーブルを更新するステップと、
（ｃ）前記ローカルピアグループ内のグループノードから、少なくとも１つの追加のルーティングパラメータを含む第２の制御パケットを受信するステップと、
（ｄ）前記少なくとも１つの追加のルーティングパラメータに基づいて前記ルーティングテーブルを更新するステップと、
（ｅ）前記更新ステップの両方が完了した時に、前記ルーティングテーブルから転送テーブルを生成するステップと、
を含む、情報パケットルーティング方法。
【請求項２】
前記ステップ（ｂ）は、シーケンス番号を使用して、前記第１の制御パケットが順序通りであるか否かを判定するサブステップをさらに含む、請求項１に記載の情報パケットルーティング方法。
【請求項３】
前記ステップ（ｂ）は、前記第１の制御パケットが順序通りであると判定された場合にのみ実行される、請求項２に記載の情報パケットルーティング方法。
【請求項４】
前記少なくとも１つのルーティングパラメータは、グループリスト、ホップカウント及び前記グループヘッダへの次ホップを含む、請求項１に記載の情報パケットルーティング方法。
【請求項５】
前記ステップ（ｂ）は、
（ｉ）前記グループリストに基づいて宛先リストを変更するステップと、
（ｉｉ）前記第１の制御パケットに直接関連した直接の中継ノードを除く前記宛先リスト内のすべての宛先に対し、宛先への次ホップを前記グループヘッダに初期化するステップと、
（ｉｉｉ）前記グループヘッダへの前記次ホップを前記直接の中継ノードに変更するステップと、
をさらに含む、請求項４に記載の情報パケットルーティング方法。
【請求項６】
前記ステップ（ｂ）は、シーケンス番号を使用して、前記第１の制御パケットが新しいか否かを判定するサブステップをさらに含み、前記第１の制御パケットが新しくない場合は、前記更新するステップは、前記直接の中継ノードに対応する宛先ノードに対する次ホップのみを更新するサブステップを含む、請求項１に記載の情報パケットルーティング方法。
【請求項７】
前記ステップ（ｄ）は、
（ｉ）前記第２の制御パケットに対するソースを判定するステップと、
（ｉｉ）前記第２の制御パケットの直接の送信者を判定するステップと、
（ｉｉｉ）前記第２の制御パケットの前記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者を介して前記ソースに対する次ホップを変更するステップと、
（ｉｖ）前記第２の制御パケットの前記少なくとも１つの追加のルーティングパラメータに基づいて、前記直接の送信者に対する前記次ホップを変更するステップと、
をさらに含む、請求項１に記載の情報パケットルーティング方法。
【請求項８】
前記転送テーブルは、前記情報のパケットをルーティングするために使用される、請求項１に記載の情報のパケットをルーティングする方法。
【請求項９】
前記第１の制御パケットの受信後に、ノードは、前記第１の制御パケットのホップカウント値フィールドをインクリメントし、前記第１の制御パケットの前記グループヘッダへの次ホップフィールドに前記ノードの識別を挿入する、請求項１に記載の情報パケットルーティング方法。
【請求項１０】
前記ノードは、前記インクリメント及び挿入を行った後に前記第１の制御パケットを転送する、請求項９に記載の情報パケットルーティング方法。
【請求項１１】
前記第２の制御パケットの受信後に、ノードは、前記グループヘッダに向けて該第２の制御パケットを転送する、請求項１０に記載の情報パケットルーティング方法。
【請求項１２】
前記ステップ（ａ）〜（ｅ）は、前記ローカルピアグループのすべてのグループノードによって実行される、請求項１に記載の情報パケットルーティング方法。
【請求項１３】
無線アドホックネットワークのローカルピアグループ内のノード間で情報パケットをルーティングするルーティング方法であって、
ノードによって受信される制御パケットのタイプを判定すること、
前記制御パケットが前記ノードにより順序通りに受信されているか否かを判定すること、及び
前記制御パケットが順序通りである場合に、該制御パケットに含まれる情報に基づいてルーティングテーブルを更新すること、
を含む、ルーティング方法。
【請求項１４】
前記制御パケットのタイプは、ハートビート制御パケット又はメンバシップレポートである、請求項１３に記載のルーティング方法。
【請求項１５】
前記ノードがグループヘッダであるか又はグループノードであるかを判断することをさらに含む、請求項１４に記載のルーティング方法。
【請求項１６】
前記ノードが前記グループノードであり且つ前記制御パケットのタイプが前記ハートビート制御パケットである場合、前記更新するステップは、該ハートビート制御パケットに含まれるグループメンバシップリストのすべてのメンバを含むように前記ルーティングテーブルを変更することを含む、請求項１５に記載のルーティング方法。
【請求項１７】
前記制御パケットが前記ノードにより順序通りに受信されているか否かを判定することは、前記制御パケットに含まれるシーケンス番号値とメモリに格納されているシーケンス番号との比較に基づき、前記受信されたシーケンス番号値がメモリに格納されている前記シーケンス番号より大きい場合、制御パケットは順序通りに受信されている、請求項１３に記載のルーティング方法。
【請求項１８】
アドホックネットワークにおいてノードによって着信パケットを処理する方法であって、
前記着信パケットを受信するステップと、
前記着信パケットが前記ノード宛てであるか否かを判定するステップと、
前記着信パケットが前記ノード宛てでない場合、ルーティングテーブルのエントリを読
み取ることに基づいて、宛先への次ホップを判定するステップと、
前記宛先への次ホップに前記着信パケットを中継するステップと、
を含む、着信パケット処理方法。
【請求項１９】
前記着信パケットが前記ノード宛てである場合、該ノードは該着信パケットを処理し消費する、請求項１８に記載の着信パケット処理方法。
【請求項２０】
アドホック無線ネットワークにおいてマルチキャストメッセージをルーティングする方法であって、
転送するためにマルチキャストメッセージを受信するステップと、
前記マルチキャストメッセージのマルチキャストグループ宛先がマルチキャスト転送テーブルにあるか否かを判定するステップと、
前記マルチキャストメッセージが以前に転送されているか否かを判定するステップと、
前記マルチキャストメッセージが以前に転送されていないと判定され、且つ前記マルチキャストグループ宛先が前記マルチキャスト転送テーブルにあると判定された場合に、前記マルチキャストメッセージを転送するステップと、
前記マルチキャストメッセージが送信された後に、前記マルチキャストメッセージを送信済みリストに追加するステップと、
を含む、マルチキャストメッセージルーティング方法。
【請求項２１】
前記マルチキャストメッセージが送信待ち行列にあるか否かを判定するステップをさらに含み、前記マルチキャストメッセージは、前記送信待ち行列にない場合、転送のために送信待ち行列に追加され、前記送信待ち行列にある場合、破棄される、請求項２０に記載のマルチキャストメッセージルーティング方法。
【請求項２２】
前記マルチキャスト転送テーブルに列挙されている前記マルチキャストグループ宛先を有する各ノードに対し、送信チャネルを選択するステップと、
前記マルチキャスト転送テーブルに列挙されている前記マルチキャストグループ宛先を有する各ノードに対し、受信チャネルを選択するステップと、
をさらに含む、請求項２０に記載のマルチキャストメッセージルーティング方法。
【請求項２３】
前記送信チャネル及び前記受信チャネルは、交互になるように選択される、請求項２２に記載のマルチキャストメッセージルーティング方法。
【請求項２４】
前記送信チャネル及び前記受信チャネルは、単一交互パターンで交互になるように選択される、請求項２３に記載のマルチキャストメッセージルーティング方法。
【請求項２５】
転送ノードであるように選択される各ノードは、その送信チャネル及び受信チャネルを、グループヘッダからのハートビート制御パケットに含まれる基準送信チャネル及び受信チャネルと、同様に前記ハートビート制御パケットに含まれるグループヘッダからのホップカウントとに基づき、前記単一交互パターンに設定する、請求項２３に記載のマルチキャストメッセージルーティング方法。
【請求項２６】
前記マルチキャスト転送テーブルは、
ローカルピアグループ内の各ノードに対し分類を割り当てること、
前記ローカルピアグループ内のすべてのノードから選択されたノードであるグループヘッダからのホップカウントを各ノードに対して判定すること、
マルチキャストメンバシップ情報を収集すること、及び
前記収集されたマルチキャストメンバシップ情報及びグループヘッダからのホップカウントに基づき、マルチキャストグループに対するメッシュにおける転送ノードを選択する
こと、
を含む方法に基づいて生成される、請求項２０に記載のマルチキャストメッセージルーティング方法。
【請求項２７】
各選択された転送ノードは、マルチキャストグループ識別を前記マルチキャスト転送テーブルに格納する、請求項２６に記載のマルチキャストメッセージルーティング方法。
【請求項２８】
前記分類、グループヘッダからのホップカウント及びマルチキャストメンバシップ情報は、前記グループヘッダから前記ローカルピアグループ内の他のノードにブロードキャストされる、請求項２６に記載のマルチキャストメッセージルーティング方法。
【請求項２９】
前記転送ノードは、マルチキャストグループに対応する前記マルチキャストメンバシップ情報を含むメンバシップレポートを受信せずに、プリセットタイマが満了すると、前記マルチキャストグループに対する非転送ノードとなる、請求項２６に記載のマルチキャストメッセージルーティング方法。
【請求項３０】
前記マルチキャストルーティングテーブルは、グループヘッダに中継されたマルチキャストメンバシップ情報を含むメンバシップレポートに基づいて生成され、マルチキャストメンバから前記グループヘッダに前記メンバシップレポートを中継するすべてのノードは、前記マルチキャストメンバを含むマルチキャストグループに対する転送ノードとなり、各転送ノードは、前記マルチキャスト転送テーブルに前記マルチキャストグループ宛先を記録する、請求項２０に記載のマルチキャストメッセージルーティング方法。
【請求項３１】
マルチキャストグループに対する転送ノードの数は、各マルチキャストメンバに対する前記グループヘッダからの前記ホップカウントに基づいて、該グループヘッダにより調整される、請求項３０に記載のマルチキャストメッセージルーティング方法。
【請求項３２】
前記調整は、前記グループヘッダと、特定のマルチキャストグループの該グループヘッダに最も近いマルチキャストメンバであると判定されたマルチキャストメンバとの間のすべての転送ノードをプルーニングし、前記グループヘッダ自体をプルーニングする、請求項３１に記載のマルチキャストメッセージルーティング方法。
【請求項３３】
転送ノードは、プルーニングされると、前記マルチキャスト転送テーブルから、前記プルーニングされたマルチキャストグループに対応する前記マルチキャストグループ宛先を削除する、請求項３２に記載のマルチキャストメッセージルーティング方法。
【請求項３４】
所定時間、前記送信されたマルチキャストメッセージをメモリに格納するステップと、
前記送信されたマルチキャストメッセージが、隣接する転送ノードから前記所定時間内に受信されたか否かを検出するステップと、
前記マルチキャストメッセージが前記所定時間内に検出されなかった場合、前記転送ステップを繰り返すステップと、
をさらに含み、前記マルチキャストメッセージが前記所定時間内に検出された場合、前記マルチキャストメッセージはメモリから破棄される、請求項２０に記載のマルチキャストメッセージルーティング方法。
【請求項３５】
前記転送するステップが繰り返される回数をカウントするステップと、
前記カウントされた回数を事前設定された閾値と比較するステップと、
前記カウントされた回数が前記事前設定された閾値を上回る場合、前記マルチキャストメッセージを破棄するステップと、
をさらに含む、請求項３４に記載のマルチキャストメッセージルーティング方法。
【請求項３６】
前記送信チャネル及び前記受信チャネルは、二重交互パターンで交互になるように選択される、請求項３５に記載のマルチキャストメッセージルーティング方法。
【請求項３７】
前記二重交互パターンを設定する方法は、
（ａ）基準送信チャネルを指定するステップと、
（ｂ）基準分類方向を選択するステップと、
（ｃ）前記基準送信チャネル及び前記基準分類方向を含むハートビート制御パケットをブロードキャストするステップと、
（ｄ）前記基準分類方向及び前記基準送信チャネルに基づいて送信チャネルを割り当てるステップと、
を含む、請求項３６に記載のマルチキャストメッセージルーティング方法。
【請求項３８】
前記ステップ（ｄ）は、
転送ノードに対し分類方向を判定するサブステップと、
前記グループヘッダからのそのホップ距離を判定するサブステップと、
前記分類方向と前記基準分類方向との比較及び前記グループヘッダからの前記ホップ距離に基づいて、前記送信チャネルを割り当てるサブステップと、
を含む、請求項３７に記載のマルチキャストメッセージルーティング方法。
【請求項３９】
無線通信デバイスであって、
転送するために前記マルチキャストメッセージを受信する手段と、
前記マルチキャストメッセージのマルチキャストグループ宛先がマルチキャスト転送テーブルにあるか否かを確定する手段と、
前記マルチキャストメッセージが以前に転送されているか否かを判定する手段と、
前記マルチキャストメッセージが以前に転送されていないと判定され、且つ前記マルチキャストグループ宛先が前記マルチキャスト転送テーブルにあると判定された場合に、前記マルチキャストメッセージを転送する手段と、
前記マルチキャストメッセージが送信された後に、前記マルチキャストメッセージを送信済みリストに追加する手段と、
を備える、無線通信デバイス。
【請求項４０】
前記マルチキャスト転送テーブル及び前記送信済みリストを格納する手段をさらに備える、請求項３９に記載の無線通信デバイス。
【請求項４１】
新たなマルチキャストメッセージが以前に送信されているか否かを判定する手段と、
新たなマルチキャストメッセージが先に送信されている場合に前記新たなマルチキャストメッセージを破棄する手段と、
前記新たなマルチキャストメッセージが送信待ち行列にあるか否かを確定する手段と、
新たなマルチキャストメッセージが先に送信されており且つ前記送信待ち行列にある場合、該送信待ち行列からマルチキャストメッセージを除去する手段と、
をさらに備える、請求項３９に記載の無線通信デバイス。
【請求項４２】
移動車両に設置される、請求項３９に記載の無線通信デバイス。
【請求項４３】
無線通信デバイスであって、
前記着信パケットを受信する手段と、
前記着信パケットが前記ノード宛てであるか否かを判定する手段と、
前記着信パケットが前記ノード宛てでない場合、ルーティングテーブルのエントリを読み取ることに基づいて、宛先への次ホップを確定する手段と、
前記宛先への次ホップに前記着信パケットを中継する手段と、
を備える、無線通信デバイス。
【請求項４４】
移動車両に設置される、請求項４３に記載の無線通信デバイス。
【請求項４５】
移動車両の無線通信デバイスにおける少なくとも１つのプロセッサによって実行されることが可能な、メッセージをルーティングするように前記少なくとも１つのプロセッサを制御するためのコンピュータ可読命令のセットを含むコンピュータ可読媒体であって、前記ルーティングが、
転送するためにマルチキャストメッセージを受信するステップと、
前記マルチキャストメッセージのマルチキャストグループ宛先がマルチキャスト転送テーブルにあるか否かを判定するステップと、
前記マルチキャストメッセージが先に転送されているか否かを判定するステップと、
前記マルチキャストメッセージが先に転送されていないと確定され、且つ前記マルチキャストグループ宛先が前記マルチキャスト転送テーブルにあると判定された場合に、前記マルチキャストメッセージを転送するステップと、
前記マルチキャストメッセージが送信された後に、前記マルチキャストメッセージを送信済みリストに追加するステップと、
を含む、コンピュータ可読媒体。
【請求項４６】
着信パケットを受信するステップと、
前記着信パケットが前記ノード宛てであるか否かを判定するステップと、
前記着信パケットが前記ノード宛てでない場合、ルーティングテーブルのエントリを読み取ることに基づいて、宛先への次ホップを判定するステップと、
前記宛先への次ホップに前記着信パケットを中継するステップと、
を実行するための命令をさらに含む、請求項４５に記載の、移動車両の無線通信デバイスにおける少なくとも１つのプロセッサによって実行されることが可能な、メッセージをルーティングするように前記少なくとも１つのプロセッサを制御するためのコンピュータ可読命令のセットを含むコンピュータ可読媒体。

【図１】

【図２】

【図３Ａ】

【図３Ｂ】

【図３Ｃ】

【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

【図１１】

【図１２】

【図１３】

【図１４】

【図１５】

【図１６】

【図１７】

【図１８】

【図１９】

【図２０】

【図２１】

【図２２】

【図２３】

【図２４】

【図２５】

【図２６】

【図２７】

【図２８】

【図２９】

【図３０Ａ】

【図３０Ｂ】

【図３１】

【図３２】

【図３３】

【図３４】

【図３５】

【図３６】

【図３７Ａ】

【図３７Ｂ】

【図３８Ａ】

【図３８Ｂ】

【図３９】

【図４０】

【図４１】

【図４２】

【図４３】

【図４４】

【図４５】

【図４６】

【図４７】

【図４８】

【図４９】

【図５０】

【図５１】

【図５２】

【図５３】

【公開番号】特開２０１２−１６５３８７（Ｐ２０１２−１６５３８７Ａ）
【公開日】平成２４年８月３０日（２０１２．８．３０）
【国際特許分類】
【出願番号】特願２０１２−３３７０１（Ｐ２０１２−３３７０１）
【出願日】平成２４年２月２０日（２０１２．２．２０）
【分割の表示】特願２００９−５３４５６２（Ｐ２００９−５３４５６２）の分割
【原出願日】平成１９年１月２６日（２００７．１．２６）
【出願人】（３９９０４７９２１）テルコーディア　テクノロジーズ　インコーポレイテッド (61)
【出願人】（５０７３０２９００）トヨタ　インフォテクノロジー　センター，ユー．エス．エー．，インコーポレイテッド (10)
【Ｆターム（参考）】