車両間通信するために車両のローカルピアグループを編成するためのグループヘッダに基づく方法
ローカルピアグループ（ＬＰＧ）としてグループ化される複数の移動デバイスを有するネットワークを確立及び維持するための方法、及び対応するアドホック移動デバイス間ネットワークが開示される。ＬＰＧ内の複数の移動無線デバイスから、グループヘッダノード（ＧＨ）が選択される。ＧＨは、一定のインターバルで、ハートビートメッセージを含む複数の制御メッセージを送信することによってＬＰＧを制御及び管理する。またＬＰＧは、少なくとも１つのグループノード（ＧＮ）も含む。少なくとも１つのＧＮは、この少なくとも１つのＧＮとＧＨとの間に構築されるネットワークリンクを介してＧＨと通信することができる。ＧＮは、ＧＨを介してＬＰＧに参加する。１つのＬＰＧ内に２つ以上のＧＨが存在する場合には、ヘッダ解決を行って、１つのＧＨだけが選択される。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、通信をほぼ瞬時に達成するために、移動デバイス間にアドホック無線ネットワークを確立及び維持することに関する。
【０００２】
［関連出願の相互参照］
本出願は、米国特許法第１１９条に基づいて、２００５年１１月２２日にShengwei Cai他によって出願された「Group-Header Based Method to Organize Local Peer Group of Vehicles for Inter-Vehicle Communication」と題する米国特許出願第１１／２８５，５９３号からの優先権を主張し、また２００５年１１月２２日にWai Chen他によって出願された「Linked Equivalent Cell Header-based Approach and Protocol for organizing an Ad-Hoc Network」と題する米国特許出願第１１／２８４，７３１号に関連し、それらの特許出願はそれぞれ参照により本明細書に援用される。
【背景技術】
【０００３】
［関連技術の記載］
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【０００４】
これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、２００４年７月２９日に、ミシガン州グランドヘブンは、６平方マイルの都市を網羅し、ミシガン湖まで１５マイルにわたって広がる、都市全域の無線ネットワークを構築して、「全米最初のＷｉＦｉ都市」であるという栄誉を主張した。多数の市当局者は、ＷｉＦｉを、下水・電力・電話及び交通機関と同様に企業を誘致・維持するために不可欠なインフラストラクチャと見ている。そのようなシステムの市当局者にとっての利点は、市職員の間での通信手段を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまで多岐にわたる。
【０００５】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路及び高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【０００６】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが、差し迫った状況に陥る前に必要な措置を講じることができるようになる。この特徴が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更又は合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【０００７】
車両安全通信（「ＶＳＣ」）は、大きく、車車間通信とインフラストラクチャを介した車両通信とに分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【０００８】
重要なＶＳＣ性能要件には、衝突回避のような種々のＶＳＣアプリケーションを支援するために、遅延時間が短いこと（約１００ミリ秒）、及びスループットを維持すること（別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ）が含まれる。
【０００９】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【００１０】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【００１１】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。
【００１２】
移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい（すなわち、どの車両も、予めその近くにいる車両について何も知らない）。車両間安全通信を構築するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行うことができるようにしなければならない。協調しない車両の移動度が高いということは、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ（移動度、アドレス、名前、メディアセッションのための）を用いることが難しいということを意味する。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【００１３】
ホットスポットのような他の場所で利用されるＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【００１４】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【００１５】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔおよびＣａｒＴａｌｋ２０００はいずれも、車車間通信ネットワークを構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノード及び移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費及び間接費が生じる。さらに、ＦｌｅｅｔＮｅｔシステムは、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【００１６】
ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車車間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。さらに、ＣａｒＴａｌｋ２０００は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【００１７】
ＣａｒＴａｌｋ２０００システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【００１８】
しかしながら、これらのＧＰＳネットワークは大きな欠点を有する。移動度の高い車両環境では、ＧＰＳ情報はすぐに有効でなくなる。ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなＧＰＳ位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【００１９】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
［発明の簡単な概要］
したがって、本発明の目的は、複数の移動デバイスをローカルピアグループ（「ＬＰＧ」）のような管理グループにグループ化することによって、移動デバイス間通信に適した通信境界を作り出し、メッセージ伝送を調整及び中継し、メッセージ伝搬の範囲及び方向
を制御することである。さらに、本発明の目的は、ローカルピアグループを確立及び維持するための簡単なプロトコル、及びローカルピアグループ内においてノード間で管理データを伝送するためのプロトコルを提供することである。
【課題を解決するための手段】
【００２１】
したがって、本明細書では、複数の移動ノード間でアドホック無線ネットワークを確立および維持するための方法が提供される。それらのノードは、ノードを順序付けすることなく、ローカルピアグループ（ＬＰＧ）を動的に形成する。ＬＰＧを制御するために、複数の移動ノードからグループヘッダノード（ＧＨ）が選択される。ＧＨは、ハートビートメッセージ（heartbeat message）を含む複数の制御メッセージを送信することによって、この制御を行う。ハートビートメッセージは、一定のインターバルで送信される。またＧＨは、他の移動ノードがＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定する。他の移動ノードがグループノード（ＧＮ）としてＬＰＧに参加することができるものと判定される場合には、ＧＨと他の移動ノードとの間にネットワークリンクを確立することによって、アドホックネットワークが構成される。
【００２２】
ＧＨは、固有のグループヘッダ識別情報を割り当てられ、上記ＬＰＧを制御および管理する機能を果たす。複数の制御メッセージには、さらに、ＬＰＧ内の全てのＧＮの識別情報、ＬＰＧ、ＧＨ識別情報およびタイムスタンプを含むグループメンバーシップメッセージ（group membership message）が含まれる。ＬＰＧ内のＧＮの識別情報は、ＧＮから送信されるステータスメッセージを介して周期的に更新される。グループメンバーシップリストメッセージは、ハートビートメッセージの中に含むことができ、上記一定のインターバルで送信することができる。
【００２３】
ＬＰＧ内に２つ以上のＧＨが存在する場合には、そのＬＰＧのただ１つのＧＨを選択するために、ヘッダ解決（header resolution）が行われる。ＬＰＧ内の全てのＧＨが、ヘッダ解決メッセージ（header resolution message）を送信する。その後、ＧＨは、ヘッダ解決モードで動作し、所定の選択判定基準に基づいて、ＬＰＧのＧＨとして唯一のＧＨを選択してヘッダ解決を実行する。新たなＧＨが選択された後に、その新たなＧＨは、ＧＨ選択メッセージ（GH selected message）を送信し、他のＧＨは、その新たなＧＨを介して、ＧＮとしてそのＬＰＧに参加する。所定の選択判定基準のうちの１つは、ハートビートメッセージを最初に送信したＧＨが新たなＧＨとして選択されるというものである。
【００２４】
ＧＨの無線通信エリアの範囲内にある全てのノードがハートビートメッセージを受信する。そのノードは、ＧＨに対してローカルピアグループ参加メッセージ（join Local Peer Group message）を送信するか否かを判定する。この判定は、少なくとも１つのパラメータと所定の閾値との比較に基づく。この少なくとも１つのパラメータは、上記ＬＰＧ内のノードの数及び上記ホップカウントである。所定の閾値は、上記ＬＰＧ内で許容されるノードの最大数か、最大ホップかのいずれかである。少なくとも１つのパラメータのうちのいずれか又は両方が対応する所定の閾値を超えない場合には、ローカルピアグループ参加メッセージを送信する。少なくとも１つのパラメータのいずれかが、その対応する所定の閾値を超える場合には、ＬＰＧ参加メッセージを送信しない。
【００２５】
別法では、ノードは、判定することなく、ＧＨに対してローカルピアグループ参加メッセージを送信する。そして、ＧＨが、同じパラメータ及び所定の閾値に基づいて、その判定を実行する。
【００２６】
アドホックネットワークを確立及び維持する方法はさらに、ＧＮにおいて、ＧＨからのハートビートメッセージを受信するステップと、ＬＰＧ内の各ＧＮにおいて、タイマをハートビート周期よりも大きな値にランダムに設定するとともに次のハートビートメッセー
ジを待ち受けるステップと、ハートビートメッセージがＧＮによって受信されないときに、タイマの時間を減らしていくステップとを含み、次のハートビートメッセージを受信する前にタイマが満了する場合には、最初にタイマが満了したＧＮが自らのハートビートメッセージを送信して、新たなＧＨとして動作し、ハートビートメッセージを送信する最初のＧＮがＬＰＧの新たなＧＨになる。
【００２７】
さらに、ＬＰＧ内のＧＮリストを最新の状態に保つために、あるＧＮがＬＰＧから出るとき、所定の時間インターバル後にステータスメッセージがそのＧＮから受信されなければ、そのＧＮの識別情報をグループメンバーシップメッセージから削除する。別法では、そのＧＮは、ＬＰＧから出る際に、積極的にメッセージを送信しても良い。
【００２８】
本発明の別の実施形態では、ＬＰＧの少なくとも１つのゲートウエイノードを選択するステップをさらに含み、その少なくとも１つのゲートウエイノードは、複数のメッセージをＧＮからＧＨに中継する機能を果たす。少なくとも１つのゲートウエイノードは、ＧＮから受信される複数のステータスメッセージを収集し、所定の時間が経過した後に、その複数のステータスメッセージをメモリに格納し、その複数のステータスメッセージの集合を含む１つのメッセージをＧＨに対して送信する。
【００２９】
本発明のさらに別の実施形態では、少なくとも１つの二次ＧＨを選択するステップをさらに含む。ＧＨがＬＰＧから出るとき、その少なくとも１つの二次ＧＨが、ＬＰＧの新たなＧＨになる。
【００３０】
また、少なくとも１つのローカルピアグループ（ＬＰＧ）を含むアドホック無線ネットワークシステムも開示される。そのＬＰＧは、順序付けされない複数の移動無線デバイスから動的に形成される。ＬＰＧは、１つのグループヘッダノード（ＧＨ）を含み、それは、複数の移動無線デバイスから選択され、固有のグループヘッダ識別情報を割り当てられる。ＧＨは、一定のインターバルで、ハートビートメッセージを含む複数の制御メッセージを送信することによって、ＬＰＧを制御するとともに管理する。またＬＰＧは、少なくとも１つのグループノード（ＧＮ）を含み、それは、少なくとも１つのＬＰＧにおいて、所定の閾値に達していないときに、ＧＨの無線範囲内にある複数の移動無線デバイスのうちの残りの移動無線デバイスから形成される。少なくとも１つのＧＮは、この少なくとも１つのＧＮとＧＨとの間に形成されるネットワークリンクを介してＧＨと通信することができる。少なくとも１つのＧＮは、そのＧＮについての情報を含むステータスメッセージをＧＨに送信する。
【００３１】
本発明のこれらの、及び他の特徴、利益及び利点は、添付の図面を参照することによって明らかになる。なお、図面を通して、類似の参照符号は類似の構造を指している。
【発明を実施するための最良の形態】
【００３２】
［発明の詳細な説明］
本発明によれば、複数のノード又は移動デバイスが管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて構築される。このグループ化すなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ内や複数のＬＰＧ間でのルーティングの基礎および本発明によるアドホック無線ネットワーク内における伝送の組織化の基礎となり、限定はしないが、車両安全や情報アプリケーションを含む、無線通信を支援する。
【００３３】
ＬＰＧの目的は、近くにあるノード間での種々の程度の連携を確立することである。これらの近くにあるノードは、無線通信能力を有する移動デバイスである。移動無線デバイスは、ＰＤＡ、ノートパソコン、携帯電話、又は無線デバイスが設置若しくは内蔵された
移動車両であってもよい。具体的には、移動デバイスは、車両内に設置されるか、又は車両内に個別に持ち込まれる、関連する通信デバイスを備える車両、及び通信デバイスを携帯した歩行者を含む。好ましい実施形態は、通信デバイスを内蔵している移動する車両である。
【００３４】
連携の程度には、２つのタイプがある。第１のタイプは直ぐ近くにある移動デバイスの密な連携であり、それは、概ね瞬時のメッセージ伝送の支援に利用されるＬＰＧ内通信のために用いられる。たとえば、緊急道路障害物警告又は別のタイプの他の緊急メッセージ又は安全メッセージを送信することは、ＬＰＧ内メッセージ伝送を用いて実行される。これらのメッセージでは、遅延が通常約１００ｍｓｅｃ以下であることが要求する。
【００３５】
第２のタイプは、疎な連携、すなわち近くにある移動デバイスをグループ化することである。このタイプの組み合わせは、リンク又は相互接続されているＬＰＧ間のＬＰＧ間通信を支援するために用いられる。たとえば、ＬＰＧ間通信は、道路認識アプリケーションや、及びドライバの視界拡張のために用いることができる。
【００３６】
ＬＰＧは、直ぐ近くにある複数のノードから動的に形成される。具体的には、第１のノードが無線信号を送信し、第１のノードの範囲内にある他のノードが、その無線信号を受信する能力を有する。ＬＰＧは無線通信エリアに基づいて形成されるので、ＬＰＧ内のノードは、固定インフラストラクチャなしに、シングルホップ又はマルチホップで互いに通信することができる。
【００３７】
図１は２つのＬＰＧを示しており、第１のＬＰＧ１００は、４つのノード１１０、１１１、１１２及び１１３を含む。これら４つのノード１１０、１１１、１１２及び１１３はそれぞれ、互いにデータを送信することができる。第２のＬＰＧ１２０は、ノード１２１、１２２、１２３、１２４、１２５及び１２６を含む。ノード１２１〜１２６はそれぞれ、互いにデータを送信することができる。このタイプの伝送は、ＬＰＧ内伝送であり、瞬時に行われる。ＬＰＧ１００内のノード１１０〜１１３は、ＬＰＧ間通信を用いることによって、ＬＰＧ１２０内のノード１２１〜１２５にデータを送信することができる。２つのＬＰＧ１００、１６０は、アドホックネットワーク１５０を形成する。
【００３８】
本発明の第１の実施形態では、ＬＰＧは２つの異なるタイプのノード、すなわちグループヘッダ（ＧＨ）及びグループノード（ＧＮ）から形成される。
【００３９】
ＧＨは、ＬＰＧ内の移動デバイス又はノードであり、ノードを順序付けすることなく、また、インフラストラクチャを用いることなく、ＬＰＧを維持するとともに制御するために指定される。
【００４０】
各ノード又は移動無線デバイスは、ＧＨ又はＧＮとして動作することができる。その場合に、各ノードは、そのノードがそれぞれＧＨ又はＧＮとして機能又は動作できるようにする構成要素又は手段を含む。図２Ａ及び図２Ｂは、そのノードがＧＨ（図２Ａ）又はＧＮ（図２Ｂ）として動作できるようにする手段又は構成要素のうちのいくつかを示す。しかしながら、或るノードがＧＨ又はＧＮのいずれかとして動作する場合であっても、ＧＨ及びＧＮの両方のための構造的な構成要素又は手段が全て存在し、動作モードに基づいて、特定の構成要素だけが機能する。
【００４１】
さらに、図２Ａ及び図２Ｂは、そのノードがそれぞれＧＨ又はＧＮのいずれかであるときに機能する、特定の手段又は特徴のみを示す。しかしながら、図示される特徴は、説明を目的とするものであり、他の特徴及び構成要素が存在することができるし、実際にそのノードの中に含まれる。さらに、説明の目的上、２つの特徴及びそれらの機能の混同を避
けるために、ＧＨのメモリセクションやＧＮのメモリ手段のような特徴に個別な名称を用いる。しかしながら、実際には、全てのノードの場合に構成要素、すなわちメモリは同じである。ただし、その構成要素は、そのノードがＧＨとして動作するか、ＧＮとして動作するかによって、異なるように機能する。
【００４２】
図２Ａは、或るノードがＧＨ１０として選択されるときに機能する、移動デバイスに接続される無線デバイスの内部構造の一部のブロック図を示す。移動デバイス又はノードがＧＨ１０として選択されるとき、少なくとも以下の構成要素が機能する；メモリセクション２００、クロック２０５、タイマ２１０、ハートビート発生手段２１５、送信／受信セクション２２０、制御手段２２５及び電源２３０。メモリセクション２００は、ＤＲＡＭ、ＳＲＡＭ又はフラッシュを含む、任意のタイプのメモリであってもよい。好ましい実施形態では、短期メモリはキャッシュである。メモリセクションは、ＬＰＧ ＩＤ、ＧＨ ＩＤ、グループリスト、所定の最大ＬＰＧサイズ、ＬＰＧ内のノードの数、及び他のタイプの制御パラメータのような、そのＬＰＧに関する情報を格納する。
【００４３】
クロック２０５は、ＧＨ１０のタイミングを維持するために用いられる。具体的には、クロック２０５は内部クロックとしての役割を果たし、タイマ２１０を設定するための基準として用いられる。タイマ２１０は、ハートビートメッセージ５１０を送信するタイミングを決定するために、すなわちハートビートインターバル（Ｔ）を決定するために用いられる。制御手段２２５又はマイクロプロセッサは、ハートビートメッセージ５１０の生成、タイマ２１０に基づくハートビートメッセージ５１０の送信のタイミング、及び或るノードがＧＨに入るのを許可するか拒否するかを含む、ＧＨの全ての処理を制御する。さらに、制御手段はヘッダ解決の役割も担っており、それは後に詳細に説明される。ハートビート発生手段２１５は、メモリセクション２００に格納されているデータからハートビートメッセージ５１０を作成又は生成するための役割を担う。
【００４４】
ＧＨ１０は、ＬＰＧを特定するとともにそのＬＰＧに関する情報を提供する「ハートビート」と呼ばれる信号又はハートビートメッセージ５１０を周期的に送出する。ハートビートメッセージ５１０は後にさらに詳細に説明される。この周期は一定のインターバル（Ｔ）である。そのインターバル（Ｔ）の値は、設計又は動作上の要件に基づいて選択することができる。またＧＨ１０は、ＬＰＧ内の全てのノードのリストも維持する。このリストはメモリセクション２００に格納される。このリストは、ＬＰＧに入るノード及びＬＰＧから出るノードに基づいて絶えず変化する。このリストは、或るノードがＬＰＧに入った時刻、又はそのノードからのステータス更新（それにより、そのノードが依然としてＬＰＧ内に存在することが通知される）がＧＨ１０によって受信された時刻のタイムスタンプを含む。このリストは、ＬＰＧのための種々の管理及び制御機能のために用いられる。たとえば、そのリストを用いて、グループサイズを追跡することができ、特定のノードを遮断することができ、ヘッダ解決を実施することができる。さらに、このリストは、ＬＰＧ内の全ての他のノードに周期的に送信される。
【００４５】
ＬＰＧハートビートメッセージ５１０は、ＧＨ１０の無線範囲（radio vicinity）内の全てのノードに送信される。そのメッセージは、制御チャネルを介して、ＧＨ１０から他のノードに送信される。このチャネルは、制御及びシグナリングに専用の無線チャネルであってもよく、又は情報交換のために全てのノードによって共有される無線チャネルであってもよい。そのようなチャネルの使用は、いくつかの無線媒体アクセス制御プロトコルによって支配されることがある。ハートビートメッセージ５１０は、ＬＰＧ ＩＤ及びＧＨ ＩＤの両方を含む固有の識別子を含み、それについては、後にさらに詳細に説明される。ハートビートメッセージ５１０又はメッセージはさらに、次のハートビートの時刻、ＬＰＧ内のノードの数、ＬＰＧの所定の最大サイズ、伝送のためのホップの数、及び許容されるホップの数の最大閾値等の、ＬＰＧの他のパラメータも含む。本発明の代替の実施
形態では、ハートビートメッセージ５１０は、グループメンバーシップリストメッセージ５４０も含むことができる。
【００４６】
ＧＨ１０は、ＬＰＧ内の全てのアクティブなＧＮ２０にグループメンバーシップリストメッセージ５４０を送出する。グループメンバーシップリストメッセージ５４０は、ヘッダ解決のために用いられ、またＧＨがＧＮのＬＰＧステータスを最新の状態に保つためにも用いられる。グループメンバーシップリストメッセージ５４０は、ＬＰＧ ＩＤ及びＧＨ ＩＤ、グループメンバーシップリストメッセージが送出される時刻のタイムスタンプ、及び各ＧＮのＩＤを含む。
【００４７】
ＧＨ１０はＬＰＧを制御する。他の全てのノードはＧＨ１０を介してＬＰＧに参加する。ＧＨ１０は、ノードから参加メッセージ５５０を受信し、そのノードがＬＰＧに参加できるか否かを判定する。その判定は、少なくとも１つの所定の閾値に基づく。所定の閾値は、ＬＰＧの最大ノードサイズ、又はＬＰＧに許容できる最大ホップカウントであってもよい。
【００４８】
具体的には、ＧＨ１０が、送信／受信セクションを介してノードからの参加メッセージ５５０を受信すると、制御手段２２５が、メモリ２００からノードカウント又はホップカウントのいずれかを検索する。さらに、制御手段２２５は、対応する所定の閾値を検索する。その後、制御手段２２５は、所定の閾値を、対応するパラメータと比較して、所定の閾値よりも大きいか否かを判定する。たとえば、ＧＨ１０は、ノードカウントを最大ノードサイズ値と比較する。別法では、ＧＨ１０は、ホップカウントを許容される最大ホップカウントと比較することができる。別法では、両方の比較を行うことができる。
【００４９】
所定の閾値の一方又は両方よりも大きい場合には、ＧＨ１０は、そのノードがＬＰＧに入るのを拒否する。その後、ＧＨ１０は、そのノードに拒否メッセージを送信する。所定の閾値よりも小さい場合には、ＧＨ１０は、そのノードが入るのを許可する。その後、ＧＨ１０はそのノードに受諾メッセージを送信する。そのノードがＧＮ２０になると、ＧＨ１０は、ノードカウントをインクリメントし、新たな値をメモリセクションに格納する。
【００５０】
通常、ＬＰＧ内にはただ１つのＧＨ１０が存在する。そのＬＰＧ内の他の全てのノードは一般的なノード、すなわちグループノード（「ＧＮ」）である。ＧＮ２０は、ＧＨ１０を通してＬＰＧに入り、ＧＮ２０に対してステータス信号５６０を周期的に送信する。これらのノードは、ＧＨ１０に対してノード参加メッセージ５５０を送信し、そのノードがＬＰＧに参加したいことを表明する。このメッセージは、ノードＩＤ及びタイムスタンプを含む。そのノードは、ＬＰＧに参加してＧＮ２０になると、ＧＨ１０に対してノードステータスメッセージ５６０を周期的に送信する。このＧＮステータスメッセージ５６０は、ＧＨ１０によって、メンバーシップリストを最新の状態に維持するために用いられる。ノードステータスメッセージ５６０はノードＩＤ及びタイムスタンプを含むので、参加メッセージ５５０に類似である。ＧＮ内の外部クロックが、タイムスタンプを決定する。通常、１つのＬＰＧ内に２つ以上のＧＮ２０が存在する。したがって、一度に複数のノードステータスメッセージ５６０が送信されることに起因する干渉を避けるために、ノードステータスメッセージ５６０は、ハートビートインターバル（Ｔ）よりも短い、ランダムに選択されたインターバルで送信される。それゆえ、各ＧＮ２０は、別のＧＮ２０とは異なる時刻に、そのノードステータスメッセージ５６０を送信する。
【００５１】
図２Ｂは、ノードがＬＰＧに参加してＧＮになるときに機能する、移動デバイスに接続される無線デバイスの内部構造の一部のブロック図を示す。ノード又は移動デバイスに接続される無線デバイスは、メモリ手段２５０と、クロック２５５と、タイマ２５６と、送信／受信セクション２６０と、制御手段２６５と、電源２７０とを備える。メモリ手段２
５０は、ＤＲＡＭ、ＳＲＡＭ又はフラッシュを含む、任意のタイプのメモリであってもよい。好ましい実施形態では、短期メモリはキャッシュである。クロック２５５は、ＧＮ２０のタイミングを維持するために用いられる。具体的には、クロック２５５は、内部クロックとしての役割を果たし、タイマ２５６を設定するための基準として用いられ、タイマ２５６は、信号を送信するタイミングを決定するために用いられる。制御セクション２５６又はマイクロプロセッサは、他のＧＮ又はＧＨ１０への信号の伝送又は送信、ＬＰＧに入るための要求送出、及びメモリ手段への情報の格納を含む、ＧＮ２０の全ての処理を制御する。
【００５２】
ＧＮ２０は周期的に、ＧＨ１０に対してステータスメッセージ５６０を送出し、ＧＨ１０からハートビートメッセージ５１０を受信する。ＬＰＧの近くにある新たなノードは、既にグループの一部となっている直ぐ近くのノードと通信することによって、又は周期的に送出されるＬＰＧハートビートを検出することによって、ＬＰＧを検出する。その後、新たなノードは、ＧＨ１０に対して、ＬＰＧへの参加を要求することができる。特定のＬＰＧに関する情報は、ＧＨ１０から受信されるハートビートメッセージ５１０から求められる。
【００５３】
ＧＨ１０は、新たなノードがＬＰＧに参加することができるか否かを判定する。ＧＨ１０が、新たなノードが参加できるものと判定する場合には、その新たなノードは、そのグループにＧＮ２０として参加する。
【００５４】
ここで、ＧＮ２０の動作が説明される。ＧＮ２０は、ＧＨ１０からハートビートメッセージ５１０を受信する。ハートビートメッセージ５１０は、後にさらに詳細に説明されるように、ＬＰＧの固有の識別子、及び他のタイプの制御情報のような情報を含む。ハートビートメッセージ５１０を受信した後に、ＧＮ２０内の制御セクション２６５は、タイマ２５６を、ハートビート周期に等しい最小値を有するランダム値（Ｔ＋？）に設定する。その周期内に次のハートビートが受信される場合には、ＧＮ２０は、依然としてＧＨ１０がその近くにあることがわかる。ハートビートが聞こえない場合には、ＧＮ２０は自らをＧＨ１０として選択する。
【００５５】
具体的には、現在のＧＨのハートビートメッセージ５１０がハートビートインターバルＴよりも長い時間にわたって聞こえないときに、新たなＧＨの選択が行われる。各ＧＮ２０は、そのタイマ２５６を、Ｔよりも大きなランダム値、たとえばＴ＋？に設定し、ハートビートメッセージ５１０を待ち受ける。現在のＧＨ又は新たなＧＨからハートビートメッセージ５１０を受信する前にタイマが満了する場合には、そのノードは自らを新たなＧＨとして選択して、新たなハートビートメッセージ５１０を送出する。これにより、ＬＰＧ内の他のノードは、現時点でＧＨが存在することがわかる。タイマが満了した最初のノードが、現在既知のＬＰＧ ＩＤを含む自らのハートビートメッセージ５１０を送出し、自らをＧＨ１０として選択する。ＬＰＧハートビートメッセージ５１０を受信すると、他のノード（ＧＮ）２０は、その情報を、メモリ手段２５０に以前に格納され、ＬＰＧを特定する少なくとも１つの固有の識別子を含む、ＬＰＧハートビート情報と比較する。ＬＰＧ ＩＤが同じであるが、ＧＨが変わっていた場合には、そのノードは、グループが分割された可能性があるか、又は以前のＧＨ１０が移動した（たとえば、ＧＨ車両が高速道路を出たか、道路の交差点で異なる方に曲がったか、又は単に車両の速度が異なることに起因してグループから離れていった）ものと認識する。ＧＨ１０の変化は、ノードＧＮ２０が、以前のグループと同じＬＰＧ ＩＤを有するグループに移動したことを意味することもある。ＬＰＧ ＩＤが異なり、ＧＨ１０が異なる場合には、ノードは、新たなグループに移動し、ＧＨ１０を介してそのグループに参加したことがわかる。
【００５６】
これらの場合のいずれにおいても、ノードは最終的には、ハートビート情報を介して、
そのＬＰＧの一部であるものと判定する。何らかの理由から、そのノードがそのＬＰＧの一部になっていなかったことがわかった場合には、そのノードは、ＧＨへの要求を介して参加することができる。
【００５７】
固有の識別子が各ＬＰＧを特定する。固有の識別子は、いくつかの形式を取ることができる。ＬＰＧは固有の識別子を介して特定することができ、固有の識別子はＧＨ番号に基づいて符号化される。しかしながら、ＧＨ１０が変化すると、ＬＰＧの固有の識別子も変化し、結果として、ノードは、そのＬＰＧが変わったのか、そのＬＰＧのＩＤだけが変わったのかを見分けることができなくなる。一方、ＧＨ１０が出て行くときに、ＬＰＧの固有の識別子は元のＩＤに固定することができる。しかしながら、この結果として、１つのＬＰＧが分割すると、ＬＰＧの固有の識別子が重複することになる。２つ以上のグループが同じ固有の識別子を有することになる。好ましい実施形態では、ＬＰＧを一意に特定するために、固有の識別子は、ＬＰＧ ＩＤ及びＧＨ ＩＤ番号の両方に基づいて符号化される。ＧＨ１０には、ＧＨ ＩＤ番号を与えられる。そのネットワーク内の第１のＧＨ１０にＧＨ１が付され、次のＧＨがＧＨ２などとなる。最初に、ＬＰＧ ＩＤがＧＨ番号に結び付けられる。それゆえ、最初はＧＨ番号が固有の識別子を決定するが、ＧＨが変わると、そのＬＰＧ ＩＤの固有の識別子は、新たなＧＨ番号を含むように変化する。さらに、１つのＬＰＧが複数のＬＰＧに分割するとき、ＬＰＧ ＩＤは、２つ以上の新たなＬＰＧに共通になるが、ＧＨ ＩＤが異なり、固有の識別子が異なることになるので、ＧＨ ＩＤを用いて同じＬＰＧ ＩＤを有するＬＰＧを区別することができる。
【００５８】
近くにある２つ以上のノードからＬＰＧが形成される。図３は、１つ又は複数のノードから１つのＬＰＧを形成および維持する過程を示す。最初に、各移動デバイスが、自らを（自分自身のみを含むＬＰＧの）ＧＨとして特定してもよい（ステップ１）。複数の移動デバイスが互いに接近してくると（たとえば、車両が交差点にあるとき、高速道路の進入車線にあるとき、又は道路上での車両の速度の差に起因して）、それらのデバイスは、互いに同じ無線通信エリア内に入る（単一ホップ又はマルチホップ）。これらの移動デバイスは、同じ無線通信エリア内にあり、２つ以上のノードを含むＬＰＧを形成し始める。通常、ハートビートメッセージ５１０を最初に送出するノードがＧＨ１０と見なされる。個々のノードはそれぞれ、自らのＬＰＧとして動作を始め、それゆえ、自らのＬＰＧ内のＧＨ１０と見なされる。その場合に、各ＧＨ１０は、後に図５において示されるように、ハートビートメッセージ５１０を送信する。ＧＨ１０から無線波が進行することができる半径距離によって、ＬＰＧの最大の物理的サイズが決定される。この距離内にあるいずれのノードも、ＬＰＧ内のＧＮ２０になることができる。ＬＰＧ内に２つ以上のＧＨが存在する場合には、ヘッダ解決が行われる。
【００５９】
ＬＰＧの近くにある新たなノードは、既にグループの一部となっている直ぐ近くのノードと通信することによって、又は周期的に送出されるＬＰＧハートビートを検出することによって、ＬＰＧを検出する。その後、新たなノードは、ＧＨ１０に対して、ＬＰＧへの参加を要求する（ステップ２）。その後、ＧＨは、そのノードがＬＰＧに参加することができるか否かを判定する（ステップ３）。この判定に基づいて、ＧＨは、そのノードを受け入れるか（ステップ４ａ）、又はそのノードがＬＰＧに入るのを拒む（ステップ４ｂ）。ステップ４ｂにおいて、所定の数のノードが既にＬＰＧ内に存在する場合、又は伝送するために必要なホップの数が閾値限界を超えている場合には、ＧＨ１０は参加を拒否する。別法では、新たなノードが、受信されたＬＰＧハートビート情報からサイズ限界を検査することによって、図７に示される所定の判定基準に基づいて、自らがそのグループに参加することができるか否かを判定することができる。これによって、既にサイズ限界に達している場合に、ＧＨ１０に、それ以上の不要なメッセージが送信されるのを避けることができる。これは、参加メッセージ５５０を送信する前に行われる。
【００６０】
具体的には、ステップ７００において、ＧＮ２０は、ＧＨ１０からハートビートメッセージ５１０を受信する。このハートビートメッセージ５１０は、ノードカウント、そのＬＰＨの所定の最大ノードサイズ、ホップカウント及び所定の最大ホップカウントを含む。その後、ステップ７１０では、ＧＮ２０が、ノードカウント若しくはホップカウントのいずれか、又は両方を、その対応する閾値、すなわち所定の最大ＬＰＧノードサイズ又は所定の最大ホップカウントとの比較に基づいて、ＬＰＧに参加することができるか否かを判定する。その後、ＧＮ２０内の制御セクション２６５は、所定の最大閾値を、その対応するパラメータと比較し、所定の閾値を超えるか否かを判定する。たとえば、ＧＮ２０は、ノードカウント値を最大ＬＰＧノードサイズ値と比較する。別法では、ＧＮ２０は、ホップカウントを許容される最大ホップカウントと比較することができる。別法では、両方の比較を行うことができる。
【００６１】
所定の最大閾値の一方又は両方を超える場合には、ステップ７２０において、ＧＮ２０は、参加メッセージ５５０をＧＨ１０に送信しない。その後、ＧＮ２０は、異なるＧＨ１０を介して、別のＬＰＧに参加する。両方の所定の閾値を超えない場合には、ステップ７３０において、ＧＮ２０は、参加メッセージ５５０をＧＨ１０に送信する。ＧＮが既に、いずれの所定の閾値にも達していないものと判定しているので、この参加メッセージ５５０を受信すると、ＧＮ１０は受諾メッセージを送信する。その後、ＧＮは、ステータスメッセージ５６０を周期的に送信し始める。
【００６２】
ＬＰＧ内の全てのＧＮの現在のリストを維持することはＧＨの役割であるので、ステップ５において、ＧＨは、ＧＮが出て行ったか否かを絶えずモニタする。或るノードがＬＰＧから出るとき、ＧＨ１０は、離脱するノードから周期的なメンバーステータス更新を受信できなくなるので、ＧＨのメモリセクション２００に格納されるグループリストからＧＮ２０を「無効にする（age）」。この無効処理は以下のように機能する。ＧＨ１０は、ＧＮ２０からステータスメッセージ５６０を受信した後に、或る時間にわたって各ＧＮ２０のメンバーシップを有効状態にしておく（ステップ５ａ）。ＧＮ２０がＬＰＧから離脱すると、ＧＨ１０は、ＧＮ２０からステータスメッセージ５６０を受信しなくなり、ＬＰＧにおいてＧＮ２０のメンバーシップを維持するのを止める。その後、ＧＨ１０は、或る時間の後に、ＬＰＧリストからそのノードを削除する（ステップ５ｂ）。ＧＨ２０からステータス更新を受信することなく、ＧＨ１０がＧＮ２０のメンバーシップを保持する実際のタイムリミットは、システム設計又は動作パラメータである。たとえば、そのタイムリミットは概ね、Ｔ＋Ｄに、ＧＮ２０がステータスメッセージ５６０を送信する最大周期を加えた時間にすることができる。そのタイムリミットの終了時に、ＧＨ１０は、そのメモリ２００からＧＮ２０の記録を削除する。これは、ＧＨ１０が更新されたメンバーシップリスト、及びＬＰＧ内のノードの数に関する現在のカウントを維持するのを助け、所定の最大サイズ値に達していない場合に、新たなノードがＬＰＧへのメンバーシップを許可されないようにする。別法では、離脱するノードは暗黙のうちに、ＧＨ１０に対して、もはや自身がＬＰＧの一部でないというメッセージを送信することができる。
【００６３】
上記のように、ハートビートメッセージ５１０は、グループメンバーシップリストメッセージ５４０を含むことができる。別法では、グループメンバーシップリストメッセージ５４０は、別個に送信されるメッセージであってもよい。他のいくつかのタイプのメッセージもＧＨ１０によって送信される。たとえば、ヘッダ解決の処理を開始するために、ヘッダ解決メッセージ５２０が送信される。このタイプのメッセージは、１つのＬＰＧ内に２つ以上のＧＨ１０が存在するときにだけ送信される。さらに、ヘッダ解決メッセージ５２０は、ＧＨ１０から、ＬＰＧ内の別のＧＨ１０にだけ送信される。ヘッダ解決メッセージ５２０は、ＧＨ ＩＤ、ＬＰＧ ＩＤ及びグループメンバーシップリストを含む。
【００６４】
ヘッダ解決が行われた後に、ＧＨ１０間でさらなるメッセージが送信される。そのＬＰ
Ｇの新たなＧＨの選択をＧＨ１０に通知するために、ＧＨ選択メッセージ５３０が用いられる。ＧＨ選択メッセージ５３０は、そのグループのＧＨ ＩＤ及びＬＰＧ ＩＤを含む。
【００６５】
同じＬＰＧ内に、又は同じ近傍域内に２つ以上の稼動中のＧＨ１０が存在する場合には、ヘッダ解決の判定が行われる（ステップ１ａ）。この目的は、同じＬＰＧ内に複数のＧＨ１０がある結果として、そのＬＰＧ内で余分な（さらには混乱させる可能性がある）制御信号が伝送又は送信され帯域幅及び容量を無駄にすることになるので、同じＬＰＧ内に複数のＧＨ１０を有するのを避けることである。ヘッダ解決は、少なくとも２つのＧＨから１つのＧＨを選択するように機能する。ステップ６において、各ＧＨはＧＨヘッダ解決メッセージ５２０を送信する。これは、ステップ７において、全てのＧＨにヘッダ解決モードにおいて動作するように通知する。新たなＧＨが、所定の選択判定基準に基づいて選択される。４つの異なる判定基準があり、いずれか１つを用いることができる。第１の判定基準は、最も小さなＩＤ番号を有するＧＨが選択されることである。第２の判定基準は、最も大きなＩＤ番号を有するＧＨが選択されることである。第３の判定基準は、最初にハートビートメッセージ５１０を送信するＧＨが選択されることであり得る。最後に、ＬＰＧ内の最も多くの現在のノードを有するＧＨ、すなわちグループメンバーシップリストと一致する最も多くのノードを有するＧＨが選択される。
【００６６】
図３Ａ〜図３Ｃは、ヘッダ解決ルールのうちの１つを用いる、本発明の一実施形態によるヘッダ解決の３つの異なる例を示す。図３Ａは、２つのＧＨ１０（各ＬＰＧはサイズ１である）が同じ近傍域に入るときの例を示す。個々のノードは、自らのＬＰＧとして動き始めており、それゆえ、そのＬＰＧ内のＧＨ１０である。２つの１ノードＬＰＧが互いに接近するとき、それらのＬＰＧは、どちらがサイズ２のＬＰＧの新たなＧＨになるかを解決する必要がある。それらのＧＨ１０のうちの一方は、そのＬＰＧのＧＨ１０のままであるのに対して、他方は、そのＬＰＧのＧＮ２０になる。
【００６７】
図３Ａでは、各ノードＧＨ Ａ及びＧＨ Ｅ、それぞれ（３００及び３１０）が、互いのハートビートメッセージ５１０を聞く。ＧＨ Ａ３００はＬＰＧ１の中にあり、ＧＨ Ｅ３０１はＬＰＧ３の中にある。それを受信すると、ＧＨ１０は、ヘッダ解決メッセージ５２０を送信し、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１はグループリストを交換して、それらのノードが同じＬＰＧ内のＧＨ１０を複製しているか否かを判定する。別法では、グループリストは、ヘッダ解決メッセージ５２０の一部である。ＬＰＧ内に１つのノードしかないこの構成では、それらのノードは、このグループリストを調べることによって、自身が各ＬＰＧ内の唯一のノードであることを見いだす。各グループリストは、１つのノードだけを有する。そのグループリストは、メモリ又はキャッシュ内のグループリストと比較される。これは、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１のうちの一方が余分なＧＨ１０であることを示す。それゆえ、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１のうちの一方は、そのＬＰＧのＧＨ１０にとどまり、他方はただのレギュラーＧＮ２０になり、新たなＧＨ１０を介して、そのＬＰＧに参加する。
【００６８】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどちらが、そのＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、小さなＩＤを有するノードをＧＨとして選択することができる。別法では、大きなＩＤ番号を有するノードをＧＨとして選択することができる。選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ａの例に示されるように、小さいＩＤを有するノードが、そのＬＰＧのＧＨ１０にとどまる。さらに、新たなＬＰＧのＧＨ１０としてとどまるＧＨ１０のＬＰＧ ＩＤが、新たなＬＰＧのＬＰＧ ＩＤを決定する。たとえば、図３Ａに示されるように、新たなグループのＬＰＧ ＩＤはＬＰＧ １ ３０５であり、ＧＮはノードＥ ３０６である。ヘッダ解決が終了した後に、ＧＨ１０は、古いＧＨに対してＧＨ選択メッセージ５３
０を送信し、そのノードに、そのＧＨ１０が新たなＧＨであることを通知する。
【００６９】
図３Ｂは、ヘッダ解決の第２の例である。この例では、１つ又は複数のＧＮ２０内のランダムに設定されたタイマ２５６のうちの１つが、ＧＨ１０からハートビートメッセージ５１０を受信することなく満了したために、１つのＬＰＧ内に２つ以上のＧＨ１０が存在しており、ＧＨ１０がＬＰＧから離脱した可能性があることを示している。ＧＮ２０は、古いＧＨ１０がＬＰＧから出たものと仮定し、それゆえ、自らを新たなＧＨ１０として選択する。しかしながら、ＧＮ２０が何故ハートビートメッセージ５１０を受信し損なったかに関しては、いくつかの理由がある。たとえば、複数の他の信号が同じ帯域幅上で送信されることによって引き起こされる無線チャネルの輻輳が、ハートビートメッセージ５１０との干渉を引き起こし、ＧＮが信号を受信するのを妨げる可能性がある。
【００７０】
したがって、多数のＧＨハートビートメッセージ５１０が同じＬＰＧ内で送信されるとともに受信される。図３Ｂに示されるように、ＬＰＧ３３０内には３つのＧＨ１０、すなわちＧＨ Ａ３３１、ＧＨ Ｃ３３３及びＧＨ Ｅ３３５が存在する。各ＧＨ３３１、３３３及び３３５はそれぞれ、受信したヘッダ解決メッセージ５２０の一部であるグループリストを、メモリセクション２００に格納されているグループリストと比較する。しかしながら、ＧＨ３３１、３３３及び３３５がそれぞれ、同じＬＰＧ３３０内に既に存在しているので、そのリスト上の全ての、又は概ね全てのノードは同じである。しかし、余分な制御になることから、１つのＬＰＧには２つ以上のＧＨを有することができないので、ノードＧＨ３３１、３３３、３３５のうちの１つがそのＬＰＧのＧＨにとどまる。他のノードは、単なるレギュラーＧＮになり、新たなＧＨを介してＬＰＧに参加する。
【００７１】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどれがＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、新たなハートビートメッセージ５１０を既に送出したノードが、ＬＰＧ３３０の新たなＧＨとして選択される。別法では、元のＧＨを新たなＧＨとして再び選択することができる。その選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ｂの例に示されるように、ＬＰＧ３３０は、ある時点において、３つのＧＨ３３１、３３３、３３５、それぞれＧＨ Ａ、ＧＨ Ｃ及びＧＨ Ｅを有する。この例の便宜上、ＧＨ Ｃ３３３が元のＧＨであるが、ＧＨ Ａ３３１においてタイマ２５６が満了するとき、ＧＨ Ａはハートビートメッセージ５１０を送信し、自らをＧＨ１０として選択する。好ましい実施形態では、ＧＨ Ａ３３１が最も新しいハートビートメッセージ５１０を送出するので、ＧＨ Ａ３３１がそのＬＰＧの新たなＧＨ３３１になる。他の２つのＧＨ、ＧＨ Ｃ３３３及びＧＨ Ｅ３３５はそれぞれ、レギュラーノードＧＮ３４２及び３４４になる。さらに、ＧＨ Ａ３３１のＬＰＧ ＩＤが、後に残るＬＰＧのＬＰＧ ＩＤを決定する。ヘッダ解決が終了した後に、ＧＨ１０は、古いＧＨに対してＧＨ選択メッセージ５３０を送信し、そのノードに、そのＧＨ１０が新たなＧＨであることを通知する。
【００７２】
図３Ｃは、ヘッダ解決の第３の例を示す。第３の例では、別のＬＰＧからのＧＨが、既に１つのＧＨを有する１よりも大きなサイズのＬＰＧに移動することにより、１つのＬＰＧ内に２つ以上のＧＨが存在する。図３Ｃに示されるように、ノードＡがＬＰＧ３６２のＧＨ Ａ３６０であり、ノードＥがＬＰＧ３７２のＧＨ Ｅ３７０である。２つのＧＨ３６０及び３７０はそれぞれ、そのハートビートメッセージ５１０を送信し、ＬＰＧ３７２のＧＨ ＥがＬＰＧ３６２の無線受信範囲内に移動したので、２つのＧＨ３６０及び３７０はそれぞれ、互いのハートビートメッセージ５１０を受信する。このハートビートメッセージ５１０は、それぞれ、そのＬＰＧ３６２及び３７２の中の全てのノードに関する情報を含むグループリスト信号を含むことができる。別法では、ＧＨ３６０及び３７０は、別個のグループリスト信号を送信することができる。さらに、そのＬＰＧ内に２つ以上のＧＨが存在するものと判定された場合には、ＧＨ３６０及び３７０は、グループメンバー
シップリストを含むヘッダ解決メッセージ５１０を送信する。
【００７３】
ＧＨ３６０及び３７０はそれぞれ、受信されたグループメンバーシップリストを、メモリセクション２００に格納されているグループリストと比較する。それらのＧＨは異なるＬＰＧから来たものなので、そのグループリストは共通のノードを全く、又は少ししか持たない。別法では、各ＧＨ３６０及び３７０は、そのメモリセクション２００内に格納されているグループリスト上にあるいくつか又は全てのノードに問い合わせて、ノードが依然としてＬＰＧ内に存在するか否かを判定することができる。あるＧＨが、ノードが同じでない（たとえば、ＬＰＧ内にない）と判定する場合には、ＧＨ（Ｅ）は新たなグループ（ＬＰＧ３６２）に入ったことがわかる。ここで、そのＬＰＧ（ＬＰＧ３６２）内に２つ以上のＧＨが存在しており、余分な制御になるため、１つのＬＰＧは２つ以上のＧＨを有することができないので、ヘッダ解決によって、それらのノードのうちのＧＨになるべきノードを選択しなければならない。それゆえ、図３Ｃでは、ノードＧＨ３６０のうちの１つが、そのＬＰＧのＧＨにとどまり、他のノードが単なるレギュラーＧＮになり、残ったＧＨを介して、そのＬＰＧに参加する。
【００７４】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどれがＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、最も多くの現在のノードグループを有するノードが、ＬＰＧ３６２のＧＨとして選択されることになる。たとえば、メモリセクション２００の中のグループリストを、他のＧＨから送信される受信されたグループリストと比較するときに、より多くの数の一致するノードを有するＧＨを選択する。別法では、別のＬＰＧに移動したと判定するＧＨは、そのＬＰＧが既に１つのＧＨを有するので、そのＬＰＧ内のＧＮに降格され、ＧＨを介してＬＰＧに参加することができる。その選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ｃの例に示されるように、ＬＰＧ３６２及び３７２はそれぞれ、１つのＧＨ３６０及び３７０だけを有する。ＧＨ Ｅ３７０がＬＰＧ３６２の近傍域に入り、ＬＰＧ３６０内に２つのＧＨが存在することになる。ＧＨ３６０及び３７０はいずれも、そのハートビートメッセージ５１０を送信する。
【００７５】
好ましい実施形態では、ＧＨ３６０は、いずれかの選択判定基準を用いて、現在のＬＰＧと共通のノードを最も多く有することになるので、そのＬＰＧの新たなＧＨになる。他方のＧＨ Ｅ３７０は、ＬＰＧ内のレギュラーノードすなわちＧＮ３８２になる。さらに、ＧＨ Ａ３６０のＬＰＧ ＩＤが、そのＬＰＧのＬＰＧ ＩＤを決定する。ヘッダ解決が終了した後に、そのＧＨは、古いＧＨに対して、ＧＨ選択メッセージ５３０を送信して、そのノードに、そのＧＨが新たなＧＨであることを通知する。ヘッダ解決が終了した後に、ステップ８において、新たなＧＨはＧＨ選択メッセージ５３０を送信する。その後、過程はステップ１に戻り、新たなＧＨがハートビートメッセージ５１０を送信する。
【００７６】
図４は、ＧＨに基づいてＬＰＧを形成するための有限状態機械を示す。グループヘッダ（ＧＨ）に基づくＬＰＧの場合、ノード（移動デバイス）がＧＨとして選択／選出される。各移動デバイスが、ターンオン状態４００中に初期化される。車両又はノードが１つしかない場合には、その移動デバイスは、遷移４０５を介して、自らのＬＰＧ及びＧＨになることによって、状態を状態４００から状態４１０に変更する。他の移動デバイスと出合うとき、その移動デバイスは、遷移４１５を介して、そのグループにグループノード（ＧＮ）として参加することによって、その状態を状態４００から状態４２０に変更する。別法では、他のノードと出合うとき、遷移４３５において、それぞれが自らのハートビートメッセージ５１０を送出して、ヘッダ解決が行われる（４３０）。上記のように、１つのＬＰＧ内に２つ以上のＧＨが存在するときに、ヘッダ解決が行われ、遷移４３５において複数のハートビートの送信が行われる。ヘッダ解決４３０によって、１つのノードが、状態４３０から状態４１０への遷移４４５を介してＧＨになり、他の全てのノードが、状態
４３０から状態４２０への遷移４５５を介してＧＮになる。各ノードは、ＧＨ又はＧＮになる能力を有する。たとえば、１つのＬＰＧ内の１つのＧＨが出て行ったとき、グループノードが新たなＧＨになることができ、ヘッダ解決が行われるとき、ＧＨがグループノードになることができる。さらに、ＧＮ内の設定されたタイマ２５６が満了する場合には、状態４２０から状態４１０への遷移４２５を介して、グループノードがＧＨになることができる。
【００７７】
図５は、本発明の一実施形態による、ＧＨによって制御されるＬＰＧに基づいて、２つのノードから１つのＬＰＧを形成する一例を示す。
【００７８】
図５は、２つのノードＡ５００及びＢ５０２を示しており、これらのノードはそれぞれ最初に、自らのＬＰＧを形成してＧＨになる。いずれも、ハートビートメッセージ５１０を送信し、互いのハートビートメッセージ５１０を受信する。信号を受信すると、ＧＨ１０はいずれも、別のＧＨがその近傍域内に存在することを理解し、ヘッダ解決メッセージ５２０を送信する。その後、両方のＧＨがヘッダ解決モード（ステップ７）に入り、２のグループサイズを有するＬＰＧに対して、１つのＧＨ１０が選択される。先に説明され図３Ａに示されるように、所定の選択判定基準を用いて、１つのノードが選択される。ノードＡ５００がＧＨ１０として選択され、ＧＨ Ａ５０４になり、ノードＢ５０２が、ＧＨ
Ａ５０４を介して、そのＬＰＧに参加しなければならない。ＧＨ Ａ５０４は、ＧＨ選択メッセージ５３０を送信して、ノードＢ５０２に通知する。それぞれ予め決定された一定の周期（Ｔ）で、ＧＨ Ａ５０４は、そのハートビートメッセージ５１０を送信する。またＧＨ Ａ５０４は、グループメンバーシップリストメッセージ５４０も送出する。このメンバーシップリスト５４０は、ハートビートメッセージ５１０に含まれることができる。別法では、グループメンバーシップリストメッセージ５４０は別個のメッセージであってもよく、より低い頻度（Ｔ＋ｂ）で伝送又は送信されることができる。ノードＢ５０２がこのハートビートメッセージ５１０を受信すると、ノードＢ５０２は、ＧＨ１０にＬＰＧ参加メッセージ５５０を送信し、そのノードがそのＬＰＧに参加することを要求する。
【００７９】
ＧＨ Ａ５０４は、ノードＢ５０２がＬＰＧに入るのを許可するか否かを判定する。この判定は、そのＬＰＧの最大許容サイズに基づくことができる。さらに、これは、そのグループの最大許容ホップによって判定することもできる。これらの判定基準を設けて、ＬＰＧ内の全てのＧＮ２０に対して情報が送信されるのにかかる時間を制限し、且つＬＰＧ内の制御メッセージ送信の回数を制限する。これは、ＬＰＧが車両安全通信の用途に対応する場合に考慮すべき重要な事柄である。
【００８０】
具体的には、ＧＨ１０は、送達されるまでにＬＰＧハートビートが進むことができるホップの数を制限することができる。しかしながら、ＧＨ１０が変化するとき、新たなＧＨが、ＬＰＧの異なる部分の中に存在することがあり、同じホップカウントでもＬＰＧの構造が変化し、たとえば、ＬＰＧの一部であったいくつかのノードが出て行って、ＬＰＧの一部でないノードが、その時点で、ＬＰＧの一部になることができるので、グループのメンバーが変化する可能性がある。ＧＨ１０が変化しても、ＬＰＧのメンバーシップを安定させておくための１つの方法は、ＧＨ１０から１ホップだけ離れているノードが、よりの多くのホップだけ離れているノードよりも早く満了するように、タイマ２５６の周期を変更することである。これは、ＧＨ１０が出て行く場合に、古いＧＨに近いノードほど、それを引き継ぐ傾向が強くなるという可能性を高めることができる。こうして、遠く離れたノードの場合を除いて、ＬＰＧのメンバーシップが過度に変化しないようにすることができる。
【００８１】
図５に示されるように、ＧＨ Ａ５０４が、ノードＢ５０２がＬＰＧに入るのを許可す
る場合には、ノードＢ５０２はＧＮ Ｂになる。その後、ＧＮ Ｂは、ＧＨ Ａ５０４に対してステータスメッセージ５６０を送信して、ＧＨ Ａ５０４にステータス更新を送信し、ＧＨ Ａ５０４が、そのグループ内の全てのノードの更新されたメンバーシップリストを維持できるようにする。ステータスメッセージ５６０は、無線チャネルを介して、ランダムな時間インターバル（ハートビートインターバルＴより短い時間）で、ＧＮ２０からＧＨ１０に送信される。これは、ステータスメッセージ５６０が全て、一斉にＧＮ２０からＧＨ１０に送信されて、無線チャネルが輻輳するのを避けるためである。理想的には、各ＧＮ２０は、異なる時刻に、ステータスメッセージ５６０を送信する。
【００８２】
さらに多くのノードがＬＰＧの近傍域に入るとき、新たな各ノードは、ＧＨのハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信することによってＬＰＧに参加することを要求する。ＬＰＧの最大許容サイズ又は最大許容ホップに達していない限り、ＧＨ１０は、ノードがグループのＧＮ２０になるのを許可する。
【００８３】
２つ以上のＬＰＧが同じ近傍域内に存在するときに、ＬＰＧの合併（merge）が行われる。しかしながら、ＬＰＧ全体が、他のＬＰＧとまとめて合併するわけではない。あるＬＰＧのノードは、１ノードずつＧＨ１０を介して他のＬＰＧに参加することによって、他のＬＰＧと「合併」する。これは、個々の車両がそれぞれの速度で、且つ他の車両との間に特定の間隔を空けて進行している路上の車両の場合に典型的である。それゆえ、ＬＰＧ内への車両の合併は典型的には、一度に１台ずつ行われる。これは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していないことも確保する。
【００８４】
図６Ａ〜図６Ｃは、起こり得る合併シナリオの３つの異なる例を示す。図６Ａは第１の例を示しており、この場合、２つのＬＰＧグループのうちの一方だけがＧＨ１０、ＧＨ Ａ６００を有する。ＬＰＧ１ ６５０は、４つのノードＡ、Ｂ、Ｃ、Ｄから成り、ノードＡ６００はＧＨ１０であり、ノードＢ、Ｃ及びＤはそれぞれ、ＧＮ６０１、６０２及び６０３である。ＬＰＧ２ ６６０は３つのノード、Ｅ、Ｐ及びＱ、それぞれ６０５、６０６及び６０７を含む。ＬＰＧ２ ６６０にはＧＨがない。ＬＰＧ２ ６６０は、各ノードＥ、Ｐ及びＱに、ＧＨ Ａ６００に対する信号の送信によりＬＰＧ１（ＬＰＧ６５０）への参加を要求させることによって、ＬＰＧ１ ６５０と合併する。ノードＥ、Ｐ及びＱは、ＧＨ Ａ６００からハートビートメッセージ５１０を受信し、ＧＨ Ａ６００に対して参加メッセージ５５０を送信することによって応答する。ＧＨ Ａ６００は、ＬＰＧの最大許容サイズ又は最大許容ホップカウントを判定することによって、ノードＥ６０５、Ｐ６０６及びＱ６０７がＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントを超えていない場合には、ＧＨ Ａ６００は、それらのノードがＧＮになるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮは、ＧＨ１０に対して、そのステータスメッセージを周期的に送信する。
【００８５】
図６Ｂは第２の例を示しており、この場合、いずれのグループともＧＨ１０を持たない。図６Ｂでは、ＬＰＧ１ ６５０は、４つのノードＡ、Ｂ、Ｃ、Ｄ、それぞれ６１０〜６１３から成る。ＬＰＧ２は、先に示されたのと同じ３つのノード、Ｅ、Ｐ、Ｑ６０５〜６０７から成る。この状況では、必要であれば（すなわち２つ以上のＧＨ１０があれば）、上記のようなヘッダ解決ルールを用いて、ハートビートメッセージ５１０を送信する最初のノードが、ＧＨ１０になる。各ノードはランダムに設定されたタイマ２５６を有し、それは、ノードがハートビートメッセージ５１０を受信しない場合には満了する。それゆえ、新たなＧＨ１０は、そのタイマが最初に満了したノードである。
【００８６】
その後、新たなＧＨ１０は、新たなＬＰＧを編成する。新たなＬＰＧ ＩＤ番号は、ＧＨ番号に基づく。新たなＧＨ１０は、そのハートビートメッセージ５１０を周期的に送信
し、他のノードは、新たなＧＨを介してＬＰＧに参加する。
【００８７】
具体的には、他のノードは、新たなＧＨに対して参加メッセージ５５０を送信する。新たなＧＨは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達しているか否かを判定することによって、ノードがＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していない場合には、新たなＧＨは、それらのノードがＧＮ２０になるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮは、ＧＨ１０に対して、そのステータスメッセージ５６０を周期的に送信する。
【００８８】
図６Ｃは、両方のＬＰＧがＧＨ１０を有し、且つ異なるＬＰＧからのノードが参加する、合併の第３の例を示す。図６Ｃでは、ＬＰＧ１ ６５０がＧＨ Ａ６００を有し、ＬＰＧ２ ６６０がＧＨ Ｑ６４０を有する。ＬＰＧ１ ６５０はＧＮ Ｂ、Ｃ及びＤ、それぞれ６０１〜６０３を有し、ＬＰＧ２ ６６０はＧＮ Ｅ６０６及びＧＮ Ｐ６０７を有する。ヘッダ解決を用いて、合成されたＬＰＧの１つのＧＨ１０が決定される。ＧＨ Ａ６００及びＧＨ Ｑ６４０は、ヘッダ解決メッセージ５２０を送信し、ヘッダ解決モードに入る。新たに合成されたＬＰＧのＧＨ１０は、上記のヘッダ解決ルールに基づいて、たとえば、所定の選択判定基準に基づいて決定される。新たなＧＨ１０が選択されると、新たなＧＨ１０はその後、新たなＬＰＧを編成する。その後、新たなＧＨは、そのハートビートメッセージ５１０を周期的に送信し、他のノードは、新たなＧＨ１０を介してＬＰＧに参加する。
【００８９】
他のノードは、新たなＧＨ１０に対して参加メッセージ５３０を送信する。新たなＧＨは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達しているか否かを判定することによって、ノードがＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していない場合には、新たなＧＨは、それらのノードがＧＮ２０になるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮ２０は、ＧＨ１０に対して、そのステータスメッセージ５６０を周期的に送信する。新たなＬＰＧ ＩＤ番号は、ＧＨ番号に基づく。
【００９０】
ＬＰＧ内のいずれかのノードが、通信できないようにＧＨ１０から離隔されるとき、たとえば無線伝送の範囲外になるとき、ＬＰＧの分割が行われる。この場合、ＧＨ１０を有するグループは、それまでと同様に動作を継続する。ＧＨ１０からもはやハートビートメッセージ５１０を受信できないノードは、そのＬＰＧから分割し、自らのＬＰＧを形成するか、又は別のＬＰＧに参加する。或るノードがＬＰＧから分割するとき、ＧＨ１０は、離れつつあるノードから周期的な更新又はステータスメッセージ５６０を受信しなくなるので、上記のように、ＧＨのメモリセクション２００に格納されるグループリストからＧＮ２０を「無効にする（age）」。その後、ＧＨ１０は、予め設定された時間が経過した後に、ＬＰＧリストから、そのノードを削除する。これは、ＧＨが更新されたメンバーシップリスト、及びＬＰＧ内のノードの数に関する現在のカウントを維持するのを助け、所定の最大サイズ値に達していない場合に、新たなノードがＬＰＧへのメンバーシップを許可されないようにする。
【００９１】
元のＬＰＧから分割するノードが、新たなグループを形成する場合には、新たなＧＨ１０を選択する必要がある。ハートビートインターバル（Ｔ）中にハートビートメッセージ５１０が聞こえなかった後にタイマ２５６が満了すると、ノードのうちの１つが新たなＧＨ１０になる。新たなＧＨ１０は、必要であれば（すなわち２つ以上のＧＨ１０があれば）、ヘッダ解決ルールを用いて選択される。新たなグループは、古いグループと同じＬＰＧ ＩＤを用いることになるが、新たなＧＨ ＩＤを用いて固有性を与える。元のＬＰＧから分割する他のノードは、新たなＧＨ１０を通して新たなＬＰＧに参加する。ノードは
、新たなＧＨ１０からハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信する。ＧＨ１０は、ＬＰＧのための所定の最大サイズに達するまで、又は最大ホップカウントに達するまで、全てのノードが参加するのを許可する。別法では、ノードがこの判定を行うことができる。
【００９２】
一方、元のＬＰＧから分割するノード、たとえばノードＥ、Ｐ及びＧ、Ｆは、別のＬＰＧに参加することができる。これらのノードは、他のＬＰＧのＧＨ１０を介して参加する。それらのノードは、ＧＨ１０からハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信して、他のＬＰＧへの参加を要求する。ＧＨ１０は、予め決定された閾値に基づいて、それらのノードがＬＰＧに参加できるか否かを判定する。
【００９３】
或るノードがＬＰＧから出るとき、他のノードは、ＬＰＧのステータスの変化を通知されなければならない。ＧＮ２０がそのグループから出る場合には、そのＧＮ２０は、自身が離れつつあることをＧＨ１０に積極的に通知することができる。その後、ＧＨ１０は、そのメモリセクション２００から、そのＧＮ ＩＤを積極的に削除する。別法では、ＧＮ２０がＬＰＧから出る場合には、ＧＨ１０は、ＧＮ２０からランダムに送信されるステータスメッセージ５６０を受信しなくなる。その際、上記のように、ＧＨ１０はノードを「無効」にし、予め設定された時間が経過した後に、ＧＨ１０は、そのメモリセクションからＧＮ ＩＤを削除する。
【００９４】
離脱するノードがＧＨ１０である場合には、ハートビートメッセージ５１０が送信されなくなり、ＧＮ２０がいずれもハートビートメッセージ５１０を受信しなくなる。それゆえ、新たなＧＨ１０が選択されなければならない。新たなハートビートメッセージ５１０を最初に送信するＧＮ２０が、新たなＧＨ１０と見なされる。タイマ２５６が満了したノードが、このハートビートメッセージ５１０を送信する。その後、新たなＧＨ１０はハートビートメッセージ５１０と、メモリに格納される最新の既知のグループリストとを送出する。その他のノードは、ＬＰＧ内にＧＮ２０のまま存在し続ける。ここで、それらのノードは、新たなＧＨ１０に対して、ステータスメッセージ５６０を送信する。
【００９５】
図８は本発明の第２の実施形態を示す。第２の実施形態によれば、複数の二次ヘッダノード又はコアノード８００を用いて、ＬＰＧ８１０の調整及び制御を助けることができる。複数の二次ヘッダノード８００は、ＧＨ１０と同じように動作し、且つグループリスト情報を受信するように選択される。一次ＧＨ１０が依然としてＬＰＧ８１０内に存在するとき、ＬＰＧ８１０内の二次ＧＨノード８００は、一次ＧＨ１０に対するホットスタンバイとしての役割を果たすために情報を収集する。すなわち、二次ＧＨノード８００は情報を収集するが、他の点では、ＬＰＧ８１０を管理するための一次ＧＨ１０ノードとしての役割は果たさない。二次ＧＨノード８００は、一次ＧＨ１０がＬＰＧ８００から出るときに、新たなＧＨがＬＰＧ８１０の構造に最小限の影響しか及ぼさないように、すなわち、一次ＧＨへの最大ホップカウント内にあるノードが依然として新たなＧＨ１０への最大ホップカウント内に存在するように、そのノードの一次ＧＨへの近さに基づいて選択される。ＬＰＧ構造の安定性を助長するための１つの方法は、一次ＧＨ１０からのホップの数に基づいて、二次ＧＨノード８００を選択することである。
【００９６】
一次ＧＨ１０がＬＰＧ８１０から出るとき、二次ヘッダノード８００のうちの１つがＧＨを引き継ぐ。一次ＧＨ１０ノードがＬＰＧ８１０から出るとき、そのＧＨ１０は、コアノードに対して新たなＧＨ１０ノードになるよう通知する。二次ＧＨノード８００に通知できない場合には、二次ＧＨノード８００は、出て行った一次ＧＨ１０ノードからのハートビートメッセージが聞こえないためにタイマが満了することによって、一次ＧＨ１０ノードが出て行ったことを見出す。その後、二次ＧＨノード８００は、新たなＧＨ１０ノードになる。二次ＧＨノード８００はＧＨと同じように動作し、グループリスト情報を受信
しているので、ＧＨの移行は概ね瞬時に行われる。ホットスタンバイ状態の二次ノード８００が２つ以上存在する場合には、それらのうちの１つが選択される。その選択は、ＧＨ１０ノードの引き継ぎに関して予め確立された序列に基づくこともできるし、あるいは離れつつある一次ＧＨ１０ノードに最も近い（すなわち、ホップ数が最も小さい）ものが、新たなＧＨ１０ノードを引き継ぐこともできる。ＬＰＧ８１０内の残りのノードはレギュラーノード８１５である。
【００９７】
図９は、本発明の第３の実施形態を示す。この実施形態では、ＬＰＧ９１０は、１つのグループヘッダノード（ＧＨ）１０、複数のゲートウエイノード９００及びレギュラーノード９０５から形成される。ＧＨ１０は、特別なゲートウエイノード又はクラスタヘッドである。この実施形態では、ＧＨ１０及びゲートウエイノード９００だけがメッセージを転送することができる。これは、上記のように、ＧＨだけを基にする編成から、無線チャネル内のメッセージの流れを削減する。上記の実施形態では、ＧＨ１０と各ノードとの間で情報を交換するために、またＬＰＧ９１０の構造を維持するために、複数の制御メッセージが送出される。この結果として、無線チャネルが、これらのメッセージによって占有され、妨害されることがある。
【００９８】
この実施形態では、ＧＨ１０は、第１の実施形態の場合に開示されたのと同じヘッダ解決を用いて選択され、ＬＰＧ９１０は、ＬＰＧ９１０内に１つの中心を成すＧＨ１０を有する。この時点で、ＬＰＧ内に他のノードは存在せず、他の構造も存在しない。その後、ＧＨ１０は、無線伝送範囲内（そのＧＨへの第１のホップ距離内）にある任意のノードに対して、ハートビートメッセージ５１０を送信する。ハートビートメッセージ５１０を受信するノードは、その無線伝送範囲内にハートビートメッセージ５１０を送信し直す。ハートビートメッセージ５１０は、ホップカウント限界に達するまで、ノードによって再送信され続ける。各ノードは、種々の近くにあるノードから、ハートビートメッセージ５１０の複数のコピーを受信することができる。最初の複製でないハートビートメッセージ５１０を転送する各ノードは、そのゲートウエイノード９００になり、ゲートウエイノード９００は通知される。ＧＨ１０又はゲートウエイノード９００でない全てのノードはレギュラーノード９０５になる。
【００９９】
所定の選択判定基準に基づいて、いくつかのノードは、ＬＰＧ９１０のためのゲートウエイノード９００として選択されることになり、他の全てのノードはレギュラーノード９０５になる。レギュラーノード９０５はメッセージを送信することができる。しかしながら、レギュラーノード９０５は、メッセージを転送することはできない。ＬＰＧ９１０内のＧＨ１０及び少なくとも１つのゲートウエイノード９００が、メッセージ送達を扱う。さらに、ハートビートメッセージ５１０そのものが、ＬＰＧ構造を維持するために用いられるので、ＬＰＧを編成する目的を果たすために、他の制御メッセージを生成する必要はない。さらに、いくつかのノードが異なる場所に移動した場合であっても、その度に、ハートビートメッセージ５１０を用いて新たな構造が構成される。
【０１００】
具体的には、ゲートウエイノード９００は、ＧＨの初期最大伝送範囲９１５を越えてＧＨ１０の無線範囲を拡張するために用いられる（拡張された範囲９２０）。各レギュラーノード９０５は、ゲートウエイノード９００にステータスメッセージ５６０を送信することができ、ゲートウエイノードは、ステータスメッセージ５６０をＧＨ１０に中継する。ゲートウエイノード９００は、所定の時間（Ｐ）だけ待機し、受信する全てのステータスメッセージ５６０を収集する。ステータスメッセージ（複数可）５６０は、メモリに格納される。所定の時間が満了すると、ゲートウエイノード（複数可）９００は、所定の時間（Ｐ）中にゲートウエイノード（複数可）９００が受信した複数のステータスメッセージ５６０の集合を含む１つのメッセージを送信する。このメッセージは、他のゲートウエイノード９００を介してＧＨ１０に中継することができる。
【０１０１】
グループヘッダに基づくＬＰＧの１つの利点は、各ＬＰＧの無線帯域幅負荷を制限するようにＬＰＧのサイズ（すなわち、各ＬＰＧ内のノードの数）を制御して、各ＬＰＧ内の通信待ち時間に下限を与えることができることである。グループヘッダに基づくＬＰＧの別の利点は、各ＬＰＧ内のＧＨノード及びＧＮノードの知識である。そのような知識を用いて、各ノードが、そのルーティングテーブルを作成する際に、宛先として、（ＬＰＧ内の）全ての他のノードに向かって次のホップノードをより効率的に選択できるようになるので、ＧＨノードから離れるホップの数によって、ルーティング及びマルチキャストプロトコル（ＬＰＧ内通信用）を効率的にすることができる。コアノードを使用することによって、グループヘッダに基づくＬＰＧの安定性がさらに増す。これはルーティング及びマルチキャスト通信にとって極めて重要である。ゲートウエイノードを使用することによって、（ＬＰＧを維持するための）制御トラフィックの量を削減することができ、それにより、無線帯域幅の利用を改善し、通信遅延時間を短縮することができる。
【０１０２】
各移動無線デバイス又はノードは、そのデバイスが上記の機能を実行できるようにする、メモリ手段に導入されるプログラムを含む。
【０１０３】
このプログラム又はソフトウエアパッケージは、製造時に、移動中の無線デバイスに導入することができる。別法では、そのプログラムは、導入後に、遠隔の場所から移動中の無線デバイスにアップロードすることができる。
【０１０４】
本明細書において、本発明が、特定の例示的な実施形態を参照しながら説明されてきた。本発明の範囲から逸脱することなく、特定の改変又は変更が当業者には明らかであろう。それらの例示的な実施形態は、説明することを意図しており、添付の特許請求の範囲によって規定される本発明の範囲を限定することは意図していない。
【図面の簡単な説明】
【０１０５】
【図１】本発明による２つのローカルピアグループの一例を示す図である。
【図２Ａ】本発明によるグループヘッダノード（ＧＨ）内の内部構造の一部のブロック図である。
【図２Ｂ】本発明によるグループノード（ＧＮ）の内部構造の一部のブロック図である。
【図３】本発明の一実施形態によるＬＰＧの形成及び維持のフローチャートである。
【図３Ａ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の一例を示す図である。
【図３Ｂ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の異なる例を示す図である。
【図３Ｃ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の異なる例を示す図である。
【図４】本発明の一実施形態による、ＧＨに基づくＬＰＧ形成のための有限状態機械（finite state machine）を示す図である。
【図５】本発明の一実施形態による２つのノードからのＬＰＧの形成を示す図である。
【図６Ａ】本発明の一実施形態による、起こり得る合併シナリオの一例を示す図である。
【図６Ｂ】本発明の一実施形態による、起こり得る合併シナリオの異なる例を示す図である。
【図６Ｃ】本発明の一実施形態による、起こり得る合併シナリオの異なる例を示す図である。
【図７】或るノードがＬＰＧに参加することができるか否かを判定する別の方法を示す図である。
【図８】本発明の第２の実施形態によるＬＰＧを示す図である。
【図９】本発明の第３の実施形態によるＬＰＧを示す図である。
【技術分野】
【０００１】
［発明の背景］
［発明の分野］
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、通信をほぼ瞬時に達成するために、移動デバイス間にアドホック無線ネットワークを確立及び維持することに関する。
【０００２】
［関連出願の相互参照］
本出願は、米国特許法第１１９条に基づいて、２００５年１１月２２日にShengwei Cai他によって出願された「Group-Header Based Method to Organize Local Peer Group of Vehicles for Inter-Vehicle Communication」と題する米国特許出願第１１／２８５，５９３号からの優先権を主張し、また２００５年１１月２２日にWai Chen他によって出願された「Linked Equivalent Cell Header-based Approach and Protocol for organizing an Ad-Hoc Network」と題する米国特許出願第１１／２８４，７３１号に関連し、それらの特許出願はそれぞれ参照により本明細書に援用される。
【背景技術】
【０００３】
［関連技術の記載］
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【０００４】
これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、２００４年７月２９日に、ミシガン州グランドヘブンは、６平方マイルの都市を網羅し、ミシガン湖まで１５マイルにわたって広がる、都市全域の無線ネットワークを構築して、「全米最初のＷｉＦｉ都市」であるという栄誉を主張した。多数の市当局者は、ＷｉＦｉを、下水・電力・電話及び交通機関と同様に企業を誘致・維持するために不可欠なインフラストラクチャと見ている。そのようなシステムの市当局者にとっての利点は、市職員の間での通信手段を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまで多岐にわたる。
【０００５】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路及び高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【０００６】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが、差し迫った状況に陥る前に必要な措置を講じることができるようになる。この特徴が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更又は合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【０００７】
車両安全通信（「ＶＳＣ」）は、大きく、車車間通信とインフラストラクチャを介した車両通信とに分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【０００８】
重要なＶＳＣ性能要件には、衝突回避のような種々のＶＳＣアプリケーションを支援するために、遅延時間が短いこと（約１００ミリ秒）、及びスループットを維持すること（別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ）が含まれる。
【０００９】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【００１０】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【００１１】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。
【００１２】
移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい（すなわち、どの車両も、予めその近くにいる車両について何も知らない）。車両間安全通信を構築するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行うことができるようにしなければならない。協調しない車両の移動度が高いということは、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ（移動度、アドレス、名前、メディアセッションのための）を用いることが難しいということを意味する。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【００１３】
ホットスポットのような他の場所で利用されるＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【００１４】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【００１５】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔおよびＣａｒＴａｌｋ２０００はいずれも、車車間通信ネットワークを構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノード及び移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費及び間接費が生じる。さらに、ＦｌｅｅｔＮｅｔシステムは、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【００１６】
ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車車間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。さらに、ＣａｒＴａｌｋ２０００は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【００１７】
ＣａｒＴａｌｋ２０００システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【００１８】
しかしながら、これらのＧＰＳネットワークは大きな欠点を有する。移動度の高い車両環境では、ＧＰＳ情報はすぐに有効でなくなる。ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなＧＰＳ位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【００１９】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００２０】
［発明の簡単な概要］
したがって、本発明の目的は、複数の移動デバイスをローカルピアグループ（「ＬＰＧ」）のような管理グループにグループ化することによって、移動デバイス間通信に適した通信境界を作り出し、メッセージ伝送を調整及び中継し、メッセージ伝搬の範囲及び方向
を制御することである。さらに、本発明の目的は、ローカルピアグループを確立及び維持するための簡単なプロトコル、及びローカルピアグループ内においてノード間で管理データを伝送するためのプロトコルを提供することである。
【課題を解決するための手段】
【００２１】
したがって、本明細書では、複数の移動ノード間でアドホック無線ネットワークを確立および維持するための方法が提供される。それらのノードは、ノードを順序付けすることなく、ローカルピアグループ（ＬＰＧ）を動的に形成する。ＬＰＧを制御するために、複数の移動ノードからグループヘッダノード（ＧＨ）が選択される。ＧＨは、ハートビートメッセージ（heartbeat message）を含む複数の制御メッセージを送信することによって、この制御を行う。ハートビートメッセージは、一定のインターバルで送信される。またＧＨは、他の移動ノードがＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定する。他の移動ノードがグループノード（ＧＮ）としてＬＰＧに参加することができるものと判定される場合には、ＧＨと他の移動ノードとの間にネットワークリンクを確立することによって、アドホックネットワークが構成される。
【００２２】
ＧＨは、固有のグループヘッダ識別情報を割り当てられ、上記ＬＰＧを制御および管理する機能を果たす。複数の制御メッセージには、さらに、ＬＰＧ内の全てのＧＮの識別情報、ＬＰＧ、ＧＨ識別情報およびタイムスタンプを含むグループメンバーシップメッセージ（group membership message）が含まれる。ＬＰＧ内のＧＮの識別情報は、ＧＮから送信されるステータスメッセージを介して周期的に更新される。グループメンバーシップリストメッセージは、ハートビートメッセージの中に含むことができ、上記一定のインターバルで送信することができる。
【００２３】
ＬＰＧ内に２つ以上のＧＨが存在する場合には、そのＬＰＧのただ１つのＧＨを選択するために、ヘッダ解決（header resolution）が行われる。ＬＰＧ内の全てのＧＨが、ヘッダ解決メッセージ（header resolution message）を送信する。その後、ＧＨは、ヘッダ解決モードで動作し、所定の選択判定基準に基づいて、ＬＰＧのＧＨとして唯一のＧＨを選択してヘッダ解決を実行する。新たなＧＨが選択された後に、その新たなＧＨは、ＧＨ選択メッセージ（GH selected message）を送信し、他のＧＨは、その新たなＧＨを介して、ＧＮとしてそのＬＰＧに参加する。所定の選択判定基準のうちの１つは、ハートビートメッセージを最初に送信したＧＨが新たなＧＨとして選択されるというものである。
【００２４】
ＧＨの無線通信エリアの範囲内にある全てのノードがハートビートメッセージを受信する。そのノードは、ＧＨに対してローカルピアグループ参加メッセージ（join Local Peer Group message）を送信するか否かを判定する。この判定は、少なくとも１つのパラメータと所定の閾値との比較に基づく。この少なくとも１つのパラメータは、上記ＬＰＧ内のノードの数及び上記ホップカウントである。所定の閾値は、上記ＬＰＧ内で許容されるノードの最大数か、最大ホップかのいずれかである。少なくとも１つのパラメータのうちのいずれか又は両方が対応する所定の閾値を超えない場合には、ローカルピアグループ参加メッセージを送信する。少なくとも１つのパラメータのいずれかが、その対応する所定の閾値を超える場合には、ＬＰＧ参加メッセージを送信しない。
【００２５】
別法では、ノードは、判定することなく、ＧＨに対してローカルピアグループ参加メッセージを送信する。そして、ＧＨが、同じパラメータ及び所定の閾値に基づいて、その判定を実行する。
【００２６】
アドホックネットワークを確立及び維持する方法はさらに、ＧＮにおいて、ＧＨからのハートビートメッセージを受信するステップと、ＬＰＧ内の各ＧＮにおいて、タイマをハートビート周期よりも大きな値にランダムに設定するとともに次のハートビートメッセー
ジを待ち受けるステップと、ハートビートメッセージがＧＮによって受信されないときに、タイマの時間を減らしていくステップとを含み、次のハートビートメッセージを受信する前にタイマが満了する場合には、最初にタイマが満了したＧＮが自らのハートビートメッセージを送信して、新たなＧＨとして動作し、ハートビートメッセージを送信する最初のＧＮがＬＰＧの新たなＧＨになる。
【００２７】
さらに、ＬＰＧ内のＧＮリストを最新の状態に保つために、あるＧＮがＬＰＧから出るとき、所定の時間インターバル後にステータスメッセージがそのＧＮから受信されなければ、そのＧＮの識別情報をグループメンバーシップメッセージから削除する。別法では、そのＧＮは、ＬＰＧから出る際に、積極的にメッセージを送信しても良い。
【００２８】
本発明の別の実施形態では、ＬＰＧの少なくとも１つのゲートウエイノードを選択するステップをさらに含み、その少なくとも１つのゲートウエイノードは、複数のメッセージをＧＮからＧＨに中継する機能を果たす。少なくとも１つのゲートウエイノードは、ＧＮから受信される複数のステータスメッセージを収集し、所定の時間が経過した後に、その複数のステータスメッセージをメモリに格納し、その複数のステータスメッセージの集合を含む１つのメッセージをＧＨに対して送信する。
【００２９】
本発明のさらに別の実施形態では、少なくとも１つの二次ＧＨを選択するステップをさらに含む。ＧＨがＬＰＧから出るとき、その少なくとも１つの二次ＧＨが、ＬＰＧの新たなＧＨになる。
【００３０】
また、少なくとも１つのローカルピアグループ（ＬＰＧ）を含むアドホック無線ネットワークシステムも開示される。そのＬＰＧは、順序付けされない複数の移動無線デバイスから動的に形成される。ＬＰＧは、１つのグループヘッダノード（ＧＨ）を含み、それは、複数の移動無線デバイスから選択され、固有のグループヘッダ識別情報を割り当てられる。ＧＨは、一定のインターバルで、ハートビートメッセージを含む複数の制御メッセージを送信することによって、ＬＰＧを制御するとともに管理する。またＬＰＧは、少なくとも１つのグループノード（ＧＮ）を含み、それは、少なくとも１つのＬＰＧにおいて、所定の閾値に達していないときに、ＧＨの無線範囲内にある複数の移動無線デバイスのうちの残りの移動無線デバイスから形成される。少なくとも１つのＧＮは、この少なくとも１つのＧＮとＧＨとの間に形成されるネットワークリンクを介してＧＨと通信することができる。少なくとも１つのＧＮは、そのＧＮについての情報を含むステータスメッセージをＧＨに送信する。
【００３１】
本発明のこれらの、及び他の特徴、利益及び利点は、添付の図面を参照することによって明らかになる。なお、図面を通して、類似の参照符号は類似の構造を指している。
【発明を実施するための最良の形態】
【００３２】
［発明の詳細な説明］
本発明によれば、複数のノード又は移動デバイスが管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて構築される。このグループ化すなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ内や複数のＬＰＧ間でのルーティングの基礎および本発明によるアドホック無線ネットワーク内における伝送の組織化の基礎となり、限定はしないが、車両安全や情報アプリケーションを含む、無線通信を支援する。
【００３３】
ＬＰＧの目的は、近くにあるノード間での種々の程度の連携を確立することである。これらの近くにあるノードは、無線通信能力を有する移動デバイスである。移動無線デバイスは、ＰＤＡ、ノートパソコン、携帯電話、又は無線デバイスが設置若しくは内蔵された
移動車両であってもよい。具体的には、移動デバイスは、車両内に設置されるか、又は車両内に個別に持ち込まれる、関連する通信デバイスを備える車両、及び通信デバイスを携帯した歩行者を含む。好ましい実施形態は、通信デバイスを内蔵している移動する車両である。
【００３４】
連携の程度には、２つのタイプがある。第１のタイプは直ぐ近くにある移動デバイスの密な連携であり、それは、概ね瞬時のメッセージ伝送の支援に利用されるＬＰＧ内通信のために用いられる。たとえば、緊急道路障害物警告又は別のタイプの他の緊急メッセージ又は安全メッセージを送信することは、ＬＰＧ内メッセージ伝送を用いて実行される。これらのメッセージでは、遅延が通常約１００ｍｓｅｃ以下であることが要求する。
【００３５】
第２のタイプは、疎な連携、すなわち近くにある移動デバイスをグループ化することである。このタイプの組み合わせは、リンク又は相互接続されているＬＰＧ間のＬＰＧ間通信を支援するために用いられる。たとえば、ＬＰＧ間通信は、道路認識アプリケーションや、及びドライバの視界拡張のために用いることができる。
【００３６】
ＬＰＧは、直ぐ近くにある複数のノードから動的に形成される。具体的には、第１のノードが無線信号を送信し、第１のノードの範囲内にある他のノードが、その無線信号を受信する能力を有する。ＬＰＧは無線通信エリアに基づいて形成されるので、ＬＰＧ内のノードは、固定インフラストラクチャなしに、シングルホップ又はマルチホップで互いに通信することができる。
【００３７】
図１は２つのＬＰＧを示しており、第１のＬＰＧ１００は、４つのノード１１０、１１１、１１２及び１１３を含む。これら４つのノード１１０、１１１、１１２及び１１３はそれぞれ、互いにデータを送信することができる。第２のＬＰＧ１２０は、ノード１２１、１２２、１２３、１２４、１２５及び１２６を含む。ノード１２１〜１２６はそれぞれ、互いにデータを送信することができる。このタイプの伝送は、ＬＰＧ内伝送であり、瞬時に行われる。ＬＰＧ１００内のノード１１０〜１１３は、ＬＰＧ間通信を用いることによって、ＬＰＧ１２０内のノード１２１〜１２５にデータを送信することができる。２つのＬＰＧ１００、１６０は、アドホックネットワーク１５０を形成する。
【００３８】
本発明の第１の実施形態では、ＬＰＧは２つの異なるタイプのノード、すなわちグループヘッダ（ＧＨ）及びグループノード（ＧＮ）から形成される。
【００３９】
ＧＨは、ＬＰＧ内の移動デバイス又はノードであり、ノードを順序付けすることなく、また、インフラストラクチャを用いることなく、ＬＰＧを維持するとともに制御するために指定される。
【００４０】
各ノード又は移動無線デバイスは、ＧＨ又はＧＮとして動作することができる。その場合に、各ノードは、そのノードがそれぞれＧＨ又はＧＮとして機能又は動作できるようにする構成要素又は手段を含む。図２Ａ及び図２Ｂは、そのノードがＧＨ（図２Ａ）又はＧＮ（図２Ｂ）として動作できるようにする手段又は構成要素のうちのいくつかを示す。しかしながら、或るノードがＧＨ又はＧＮのいずれかとして動作する場合であっても、ＧＨ及びＧＮの両方のための構造的な構成要素又は手段が全て存在し、動作モードに基づいて、特定の構成要素だけが機能する。
【００４１】
さらに、図２Ａ及び図２Ｂは、そのノードがそれぞれＧＨ又はＧＮのいずれかであるときに機能する、特定の手段又は特徴のみを示す。しかしながら、図示される特徴は、説明を目的とするものであり、他の特徴及び構成要素が存在することができるし、実際にそのノードの中に含まれる。さらに、説明の目的上、２つの特徴及びそれらの機能の混同を避
けるために、ＧＨのメモリセクションやＧＮのメモリ手段のような特徴に個別な名称を用いる。しかしながら、実際には、全てのノードの場合に構成要素、すなわちメモリは同じである。ただし、その構成要素は、そのノードがＧＨとして動作するか、ＧＮとして動作するかによって、異なるように機能する。
【００４２】
図２Ａは、或るノードがＧＨ１０として選択されるときに機能する、移動デバイスに接続される無線デバイスの内部構造の一部のブロック図を示す。移動デバイス又はノードがＧＨ１０として選択されるとき、少なくとも以下の構成要素が機能する；メモリセクション２００、クロック２０５、タイマ２１０、ハートビート発生手段２１５、送信／受信セクション２２０、制御手段２２５及び電源２３０。メモリセクション２００は、ＤＲＡＭ、ＳＲＡＭ又はフラッシュを含む、任意のタイプのメモリであってもよい。好ましい実施形態では、短期メモリはキャッシュである。メモリセクションは、ＬＰＧ ＩＤ、ＧＨ ＩＤ、グループリスト、所定の最大ＬＰＧサイズ、ＬＰＧ内のノードの数、及び他のタイプの制御パラメータのような、そのＬＰＧに関する情報を格納する。
【００４３】
クロック２０５は、ＧＨ１０のタイミングを維持するために用いられる。具体的には、クロック２０５は内部クロックとしての役割を果たし、タイマ２１０を設定するための基準として用いられる。タイマ２１０は、ハートビートメッセージ５１０を送信するタイミングを決定するために、すなわちハートビートインターバル（Ｔ）を決定するために用いられる。制御手段２２５又はマイクロプロセッサは、ハートビートメッセージ５１０の生成、タイマ２１０に基づくハートビートメッセージ５１０の送信のタイミング、及び或るノードがＧＨに入るのを許可するか拒否するかを含む、ＧＨの全ての処理を制御する。さらに、制御手段はヘッダ解決の役割も担っており、それは後に詳細に説明される。ハートビート発生手段２１５は、メモリセクション２００に格納されているデータからハートビートメッセージ５１０を作成又は生成するための役割を担う。
【００４４】
ＧＨ１０は、ＬＰＧを特定するとともにそのＬＰＧに関する情報を提供する「ハートビート」と呼ばれる信号又はハートビートメッセージ５１０を周期的に送出する。ハートビートメッセージ５１０は後にさらに詳細に説明される。この周期は一定のインターバル（Ｔ）である。そのインターバル（Ｔ）の値は、設計又は動作上の要件に基づいて選択することができる。またＧＨ１０は、ＬＰＧ内の全てのノードのリストも維持する。このリストはメモリセクション２００に格納される。このリストは、ＬＰＧに入るノード及びＬＰＧから出るノードに基づいて絶えず変化する。このリストは、或るノードがＬＰＧに入った時刻、又はそのノードからのステータス更新（それにより、そのノードが依然としてＬＰＧ内に存在することが通知される）がＧＨ１０によって受信された時刻のタイムスタンプを含む。このリストは、ＬＰＧのための種々の管理及び制御機能のために用いられる。たとえば、そのリストを用いて、グループサイズを追跡することができ、特定のノードを遮断することができ、ヘッダ解決を実施することができる。さらに、このリストは、ＬＰＧ内の全ての他のノードに周期的に送信される。
【００４５】
ＬＰＧハートビートメッセージ５１０は、ＧＨ１０の無線範囲（radio vicinity）内の全てのノードに送信される。そのメッセージは、制御チャネルを介して、ＧＨ１０から他のノードに送信される。このチャネルは、制御及びシグナリングに専用の無線チャネルであってもよく、又は情報交換のために全てのノードによって共有される無線チャネルであってもよい。そのようなチャネルの使用は、いくつかの無線媒体アクセス制御プロトコルによって支配されることがある。ハートビートメッセージ５１０は、ＬＰＧ ＩＤ及びＧＨ ＩＤの両方を含む固有の識別子を含み、それについては、後にさらに詳細に説明される。ハートビートメッセージ５１０又はメッセージはさらに、次のハートビートの時刻、ＬＰＧ内のノードの数、ＬＰＧの所定の最大サイズ、伝送のためのホップの数、及び許容されるホップの数の最大閾値等の、ＬＰＧの他のパラメータも含む。本発明の代替の実施
形態では、ハートビートメッセージ５１０は、グループメンバーシップリストメッセージ５４０も含むことができる。
【００４６】
ＧＨ１０は、ＬＰＧ内の全てのアクティブなＧＮ２０にグループメンバーシップリストメッセージ５４０を送出する。グループメンバーシップリストメッセージ５４０は、ヘッダ解決のために用いられ、またＧＨがＧＮのＬＰＧステータスを最新の状態に保つためにも用いられる。グループメンバーシップリストメッセージ５４０は、ＬＰＧ ＩＤ及びＧＨ ＩＤ、グループメンバーシップリストメッセージが送出される時刻のタイムスタンプ、及び各ＧＮのＩＤを含む。
【００４７】
ＧＨ１０はＬＰＧを制御する。他の全てのノードはＧＨ１０を介してＬＰＧに参加する。ＧＨ１０は、ノードから参加メッセージ５５０を受信し、そのノードがＬＰＧに参加できるか否かを判定する。その判定は、少なくとも１つの所定の閾値に基づく。所定の閾値は、ＬＰＧの最大ノードサイズ、又はＬＰＧに許容できる最大ホップカウントであってもよい。
【００４８】
具体的には、ＧＨ１０が、送信／受信セクションを介してノードからの参加メッセージ５５０を受信すると、制御手段２２５が、メモリ２００からノードカウント又はホップカウントのいずれかを検索する。さらに、制御手段２２５は、対応する所定の閾値を検索する。その後、制御手段２２５は、所定の閾値を、対応するパラメータと比較して、所定の閾値よりも大きいか否かを判定する。たとえば、ＧＨ１０は、ノードカウントを最大ノードサイズ値と比較する。別法では、ＧＨ１０は、ホップカウントを許容される最大ホップカウントと比較することができる。別法では、両方の比較を行うことができる。
【００４９】
所定の閾値の一方又は両方よりも大きい場合には、ＧＨ１０は、そのノードがＬＰＧに入るのを拒否する。その後、ＧＨ１０は、そのノードに拒否メッセージを送信する。所定の閾値よりも小さい場合には、ＧＨ１０は、そのノードが入るのを許可する。その後、ＧＨ１０はそのノードに受諾メッセージを送信する。そのノードがＧＮ２０になると、ＧＨ１０は、ノードカウントをインクリメントし、新たな値をメモリセクションに格納する。
【００５０】
通常、ＬＰＧ内にはただ１つのＧＨ１０が存在する。そのＬＰＧ内の他の全てのノードは一般的なノード、すなわちグループノード（「ＧＮ」）である。ＧＮ２０は、ＧＨ１０を通してＬＰＧに入り、ＧＮ２０に対してステータス信号５６０を周期的に送信する。これらのノードは、ＧＨ１０に対してノード参加メッセージ５５０を送信し、そのノードがＬＰＧに参加したいことを表明する。このメッセージは、ノードＩＤ及びタイムスタンプを含む。そのノードは、ＬＰＧに参加してＧＮ２０になると、ＧＨ１０に対してノードステータスメッセージ５６０を周期的に送信する。このＧＮステータスメッセージ５６０は、ＧＨ１０によって、メンバーシップリストを最新の状態に維持するために用いられる。ノードステータスメッセージ５６０はノードＩＤ及びタイムスタンプを含むので、参加メッセージ５５０に類似である。ＧＮ内の外部クロックが、タイムスタンプを決定する。通常、１つのＬＰＧ内に２つ以上のＧＮ２０が存在する。したがって、一度に複数のノードステータスメッセージ５６０が送信されることに起因する干渉を避けるために、ノードステータスメッセージ５６０は、ハートビートインターバル（Ｔ）よりも短い、ランダムに選択されたインターバルで送信される。それゆえ、各ＧＮ２０は、別のＧＮ２０とは異なる時刻に、そのノードステータスメッセージ５６０を送信する。
【００５１】
図２Ｂは、ノードがＬＰＧに参加してＧＮになるときに機能する、移動デバイスに接続される無線デバイスの内部構造の一部のブロック図を示す。ノード又は移動デバイスに接続される無線デバイスは、メモリ手段２５０と、クロック２５５と、タイマ２５６と、送信／受信セクション２６０と、制御手段２６５と、電源２７０とを備える。メモリ手段２
５０は、ＤＲＡＭ、ＳＲＡＭ又はフラッシュを含む、任意のタイプのメモリであってもよい。好ましい実施形態では、短期メモリはキャッシュである。クロック２５５は、ＧＮ２０のタイミングを維持するために用いられる。具体的には、クロック２５５は、内部クロックとしての役割を果たし、タイマ２５６を設定するための基準として用いられ、タイマ２５６は、信号を送信するタイミングを決定するために用いられる。制御セクション２５６又はマイクロプロセッサは、他のＧＮ又はＧＨ１０への信号の伝送又は送信、ＬＰＧに入るための要求送出、及びメモリ手段への情報の格納を含む、ＧＮ２０の全ての処理を制御する。
【００５２】
ＧＮ２０は周期的に、ＧＨ１０に対してステータスメッセージ５６０を送出し、ＧＨ１０からハートビートメッセージ５１０を受信する。ＬＰＧの近くにある新たなノードは、既にグループの一部となっている直ぐ近くのノードと通信することによって、又は周期的に送出されるＬＰＧハートビートを検出することによって、ＬＰＧを検出する。その後、新たなノードは、ＧＨ１０に対して、ＬＰＧへの参加を要求することができる。特定のＬＰＧに関する情報は、ＧＨ１０から受信されるハートビートメッセージ５１０から求められる。
【００５３】
ＧＨ１０は、新たなノードがＬＰＧに参加することができるか否かを判定する。ＧＨ１０が、新たなノードが参加できるものと判定する場合には、その新たなノードは、そのグループにＧＮ２０として参加する。
【００５４】
ここで、ＧＮ２０の動作が説明される。ＧＮ２０は、ＧＨ１０からハートビートメッセージ５１０を受信する。ハートビートメッセージ５１０は、後にさらに詳細に説明されるように、ＬＰＧの固有の識別子、及び他のタイプの制御情報のような情報を含む。ハートビートメッセージ５１０を受信した後に、ＧＮ２０内の制御セクション２６５は、タイマ２５６を、ハートビート周期に等しい最小値を有するランダム値（Ｔ＋？）に設定する。その周期内に次のハートビートが受信される場合には、ＧＮ２０は、依然としてＧＨ１０がその近くにあることがわかる。ハートビートが聞こえない場合には、ＧＮ２０は自らをＧＨ１０として選択する。
【００５５】
具体的には、現在のＧＨのハートビートメッセージ５１０がハートビートインターバルＴよりも長い時間にわたって聞こえないときに、新たなＧＨの選択が行われる。各ＧＮ２０は、そのタイマ２５６を、Ｔよりも大きなランダム値、たとえばＴ＋？に設定し、ハートビートメッセージ５１０を待ち受ける。現在のＧＨ又は新たなＧＨからハートビートメッセージ５１０を受信する前にタイマが満了する場合には、そのノードは自らを新たなＧＨとして選択して、新たなハートビートメッセージ５１０を送出する。これにより、ＬＰＧ内の他のノードは、現時点でＧＨが存在することがわかる。タイマが満了した最初のノードが、現在既知のＬＰＧ ＩＤを含む自らのハートビートメッセージ５１０を送出し、自らをＧＨ１０として選択する。ＬＰＧハートビートメッセージ５１０を受信すると、他のノード（ＧＮ）２０は、その情報を、メモリ手段２５０に以前に格納され、ＬＰＧを特定する少なくとも１つの固有の識別子を含む、ＬＰＧハートビート情報と比較する。ＬＰＧ ＩＤが同じであるが、ＧＨが変わっていた場合には、そのノードは、グループが分割された可能性があるか、又は以前のＧＨ１０が移動した（たとえば、ＧＨ車両が高速道路を出たか、道路の交差点で異なる方に曲がったか、又は単に車両の速度が異なることに起因してグループから離れていった）ものと認識する。ＧＨ１０の変化は、ノードＧＮ２０が、以前のグループと同じＬＰＧ ＩＤを有するグループに移動したことを意味することもある。ＬＰＧ ＩＤが異なり、ＧＨ１０が異なる場合には、ノードは、新たなグループに移動し、ＧＨ１０を介してそのグループに参加したことがわかる。
【００５６】
これらの場合のいずれにおいても、ノードは最終的には、ハートビート情報を介して、
そのＬＰＧの一部であるものと判定する。何らかの理由から、そのノードがそのＬＰＧの一部になっていなかったことがわかった場合には、そのノードは、ＧＨへの要求を介して参加することができる。
【００５７】
固有の識別子が各ＬＰＧを特定する。固有の識別子は、いくつかの形式を取ることができる。ＬＰＧは固有の識別子を介して特定することができ、固有の識別子はＧＨ番号に基づいて符号化される。しかしながら、ＧＨ１０が変化すると、ＬＰＧの固有の識別子も変化し、結果として、ノードは、そのＬＰＧが変わったのか、そのＬＰＧのＩＤだけが変わったのかを見分けることができなくなる。一方、ＧＨ１０が出て行くときに、ＬＰＧの固有の識別子は元のＩＤに固定することができる。しかしながら、この結果として、１つのＬＰＧが分割すると、ＬＰＧの固有の識別子が重複することになる。２つ以上のグループが同じ固有の識別子を有することになる。好ましい実施形態では、ＬＰＧを一意に特定するために、固有の識別子は、ＬＰＧ ＩＤ及びＧＨ ＩＤ番号の両方に基づいて符号化される。ＧＨ１０には、ＧＨ ＩＤ番号を与えられる。そのネットワーク内の第１のＧＨ１０にＧＨ１が付され、次のＧＨがＧＨ２などとなる。最初に、ＬＰＧ ＩＤがＧＨ番号に結び付けられる。それゆえ、最初はＧＨ番号が固有の識別子を決定するが、ＧＨが変わると、そのＬＰＧ ＩＤの固有の識別子は、新たなＧＨ番号を含むように変化する。さらに、１つのＬＰＧが複数のＬＰＧに分割するとき、ＬＰＧ ＩＤは、２つ以上の新たなＬＰＧに共通になるが、ＧＨ ＩＤが異なり、固有の識別子が異なることになるので、ＧＨ ＩＤを用いて同じＬＰＧ ＩＤを有するＬＰＧを区別することができる。
【００５８】
近くにある２つ以上のノードからＬＰＧが形成される。図３は、１つ又は複数のノードから１つのＬＰＧを形成および維持する過程を示す。最初に、各移動デバイスが、自らを（自分自身のみを含むＬＰＧの）ＧＨとして特定してもよい（ステップ１）。複数の移動デバイスが互いに接近してくると（たとえば、車両が交差点にあるとき、高速道路の進入車線にあるとき、又は道路上での車両の速度の差に起因して）、それらのデバイスは、互いに同じ無線通信エリア内に入る（単一ホップ又はマルチホップ）。これらの移動デバイスは、同じ無線通信エリア内にあり、２つ以上のノードを含むＬＰＧを形成し始める。通常、ハートビートメッセージ５１０を最初に送出するノードがＧＨ１０と見なされる。個々のノードはそれぞれ、自らのＬＰＧとして動作を始め、それゆえ、自らのＬＰＧ内のＧＨ１０と見なされる。その場合に、各ＧＨ１０は、後に図５において示されるように、ハートビートメッセージ５１０を送信する。ＧＨ１０から無線波が進行することができる半径距離によって、ＬＰＧの最大の物理的サイズが決定される。この距離内にあるいずれのノードも、ＬＰＧ内のＧＮ２０になることができる。ＬＰＧ内に２つ以上のＧＨが存在する場合には、ヘッダ解決が行われる。
【００５９】
ＬＰＧの近くにある新たなノードは、既にグループの一部となっている直ぐ近くのノードと通信することによって、又は周期的に送出されるＬＰＧハートビートを検出することによって、ＬＰＧを検出する。その後、新たなノードは、ＧＨ１０に対して、ＬＰＧへの参加を要求する（ステップ２）。その後、ＧＨは、そのノードがＬＰＧに参加することができるか否かを判定する（ステップ３）。この判定に基づいて、ＧＨは、そのノードを受け入れるか（ステップ４ａ）、又はそのノードがＬＰＧに入るのを拒む（ステップ４ｂ）。ステップ４ｂにおいて、所定の数のノードが既にＬＰＧ内に存在する場合、又は伝送するために必要なホップの数が閾値限界を超えている場合には、ＧＨ１０は参加を拒否する。別法では、新たなノードが、受信されたＬＰＧハートビート情報からサイズ限界を検査することによって、図７に示される所定の判定基準に基づいて、自らがそのグループに参加することができるか否かを判定することができる。これによって、既にサイズ限界に達している場合に、ＧＨ１０に、それ以上の不要なメッセージが送信されるのを避けることができる。これは、参加メッセージ５５０を送信する前に行われる。
【００６０】
具体的には、ステップ７００において、ＧＮ２０は、ＧＨ１０からハートビートメッセージ５１０を受信する。このハートビートメッセージ５１０は、ノードカウント、そのＬＰＨの所定の最大ノードサイズ、ホップカウント及び所定の最大ホップカウントを含む。その後、ステップ７１０では、ＧＮ２０が、ノードカウント若しくはホップカウントのいずれか、又は両方を、その対応する閾値、すなわち所定の最大ＬＰＧノードサイズ又は所定の最大ホップカウントとの比較に基づいて、ＬＰＧに参加することができるか否かを判定する。その後、ＧＮ２０内の制御セクション２６５は、所定の最大閾値を、その対応するパラメータと比較し、所定の閾値を超えるか否かを判定する。たとえば、ＧＮ２０は、ノードカウント値を最大ＬＰＧノードサイズ値と比較する。別法では、ＧＮ２０は、ホップカウントを許容される最大ホップカウントと比較することができる。別法では、両方の比較を行うことができる。
【００６１】
所定の最大閾値の一方又は両方を超える場合には、ステップ７２０において、ＧＮ２０は、参加メッセージ５５０をＧＨ１０に送信しない。その後、ＧＮ２０は、異なるＧＨ１０を介して、別のＬＰＧに参加する。両方の所定の閾値を超えない場合には、ステップ７３０において、ＧＮ２０は、参加メッセージ５５０をＧＨ１０に送信する。ＧＮが既に、いずれの所定の閾値にも達していないものと判定しているので、この参加メッセージ５５０を受信すると、ＧＮ１０は受諾メッセージを送信する。その後、ＧＮは、ステータスメッセージ５６０を周期的に送信し始める。
【００６２】
ＬＰＧ内の全てのＧＮの現在のリストを維持することはＧＨの役割であるので、ステップ５において、ＧＨは、ＧＮが出て行ったか否かを絶えずモニタする。或るノードがＬＰＧから出るとき、ＧＨ１０は、離脱するノードから周期的なメンバーステータス更新を受信できなくなるので、ＧＨのメモリセクション２００に格納されるグループリストからＧＮ２０を「無効にする（age）」。この無効処理は以下のように機能する。ＧＨ１０は、ＧＮ２０からステータスメッセージ５６０を受信した後に、或る時間にわたって各ＧＮ２０のメンバーシップを有効状態にしておく（ステップ５ａ）。ＧＮ２０がＬＰＧから離脱すると、ＧＨ１０は、ＧＮ２０からステータスメッセージ５６０を受信しなくなり、ＬＰＧにおいてＧＮ２０のメンバーシップを維持するのを止める。その後、ＧＨ１０は、或る時間の後に、ＬＰＧリストからそのノードを削除する（ステップ５ｂ）。ＧＨ２０からステータス更新を受信することなく、ＧＨ１０がＧＮ２０のメンバーシップを保持する実際のタイムリミットは、システム設計又は動作パラメータである。たとえば、そのタイムリミットは概ね、Ｔ＋Ｄに、ＧＮ２０がステータスメッセージ５６０を送信する最大周期を加えた時間にすることができる。そのタイムリミットの終了時に、ＧＨ１０は、そのメモリ２００からＧＮ２０の記録を削除する。これは、ＧＨ１０が更新されたメンバーシップリスト、及びＬＰＧ内のノードの数に関する現在のカウントを維持するのを助け、所定の最大サイズ値に達していない場合に、新たなノードがＬＰＧへのメンバーシップを許可されないようにする。別法では、離脱するノードは暗黙のうちに、ＧＨ１０に対して、もはや自身がＬＰＧの一部でないというメッセージを送信することができる。
【００６３】
上記のように、ハートビートメッセージ５１０は、グループメンバーシップリストメッセージ５４０を含むことができる。別法では、グループメンバーシップリストメッセージ５４０は、別個に送信されるメッセージであってもよい。他のいくつかのタイプのメッセージもＧＨ１０によって送信される。たとえば、ヘッダ解決の処理を開始するために、ヘッダ解決メッセージ５２０が送信される。このタイプのメッセージは、１つのＬＰＧ内に２つ以上のＧＨ１０が存在するときにだけ送信される。さらに、ヘッダ解決メッセージ５２０は、ＧＨ１０から、ＬＰＧ内の別のＧＨ１０にだけ送信される。ヘッダ解決メッセージ５２０は、ＧＨ ＩＤ、ＬＰＧ ＩＤ及びグループメンバーシップリストを含む。
【００６４】
ヘッダ解決が行われた後に、ＧＨ１０間でさらなるメッセージが送信される。そのＬＰ
Ｇの新たなＧＨの選択をＧＨ１０に通知するために、ＧＨ選択メッセージ５３０が用いられる。ＧＨ選択メッセージ５３０は、そのグループのＧＨ ＩＤ及びＬＰＧ ＩＤを含む。
【００６５】
同じＬＰＧ内に、又は同じ近傍域内に２つ以上の稼動中のＧＨ１０が存在する場合には、ヘッダ解決の判定が行われる（ステップ１ａ）。この目的は、同じＬＰＧ内に複数のＧＨ１０がある結果として、そのＬＰＧ内で余分な（さらには混乱させる可能性がある）制御信号が伝送又は送信され帯域幅及び容量を無駄にすることになるので、同じＬＰＧ内に複数のＧＨ１０を有するのを避けることである。ヘッダ解決は、少なくとも２つのＧＨから１つのＧＨを選択するように機能する。ステップ６において、各ＧＨはＧＨヘッダ解決メッセージ５２０を送信する。これは、ステップ７において、全てのＧＨにヘッダ解決モードにおいて動作するように通知する。新たなＧＨが、所定の選択判定基準に基づいて選択される。４つの異なる判定基準があり、いずれか１つを用いることができる。第１の判定基準は、最も小さなＩＤ番号を有するＧＨが選択されることである。第２の判定基準は、最も大きなＩＤ番号を有するＧＨが選択されることである。第３の判定基準は、最初にハートビートメッセージ５１０を送信するＧＨが選択されることであり得る。最後に、ＬＰＧ内の最も多くの現在のノードを有するＧＨ、すなわちグループメンバーシップリストと一致する最も多くのノードを有するＧＨが選択される。
【００６６】
図３Ａ〜図３Ｃは、ヘッダ解決ルールのうちの１つを用いる、本発明の一実施形態によるヘッダ解決の３つの異なる例を示す。図３Ａは、２つのＧＨ１０（各ＬＰＧはサイズ１である）が同じ近傍域に入るときの例を示す。個々のノードは、自らのＬＰＧとして動き始めており、それゆえ、そのＬＰＧ内のＧＨ１０である。２つの１ノードＬＰＧが互いに接近するとき、それらのＬＰＧは、どちらがサイズ２のＬＰＧの新たなＧＨになるかを解決する必要がある。それらのＧＨ１０のうちの一方は、そのＬＰＧのＧＨ１０のままであるのに対して、他方は、そのＬＰＧのＧＮ２０になる。
【００６７】
図３Ａでは、各ノードＧＨ Ａ及びＧＨ Ｅ、それぞれ（３００及び３１０）が、互いのハートビートメッセージ５１０を聞く。ＧＨ Ａ３００はＬＰＧ１の中にあり、ＧＨ Ｅ３０１はＬＰＧ３の中にある。それを受信すると、ＧＨ１０は、ヘッダ解決メッセージ５２０を送信し、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１はグループリストを交換して、それらのノードが同じＬＰＧ内のＧＨ１０を複製しているか否かを判定する。別法では、グループリストは、ヘッダ解決メッセージ５２０の一部である。ＬＰＧ内に１つのノードしかないこの構成では、それらのノードは、このグループリストを調べることによって、自身が各ＬＰＧ内の唯一のノードであることを見いだす。各グループリストは、１つのノードだけを有する。そのグループリストは、メモリ又はキャッシュ内のグループリストと比較される。これは、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１のうちの一方が余分なＧＨ１０であることを示す。それゆえ、ノードＧＨ Ａ３００及びＧＨ Ｅ３０１のうちの一方は、そのＬＰＧのＧＨ１０にとどまり、他方はただのレギュラーＧＮ２０になり、新たなＧＨ１０を介して、そのＬＰＧに参加する。
【００６８】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどちらが、そのＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、小さなＩＤを有するノードをＧＨとして選択することができる。別法では、大きなＩＤ番号を有するノードをＧＨとして選択することができる。選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ａの例に示されるように、小さいＩＤを有するノードが、そのＬＰＧのＧＨ１０にとどまる。さらに、新たなＬＰＧのＧＨ１０としてとどまるＧＨ１０のＬＰＧ ＩＤが、新たなＬＰＧのＬＰＧ ＩＤを決定する。たとえば、図３Ａに示されるように、新たなグループのＬＰＧ ＩＤはＬＰＧ １ ３０５であり、ＧＮはノードＥ ３０６である。ヘッダ解決が終了した後に、ＧＨ１０は、古いＧＨに対してＧＨ選択メッセージ５３
０を送信し、そのノードに、そのＧＨ１０が新たなＧＨであることを通知する。
【００６９】
図３Ｂは、ヘッダ解決の第２の例である。この例では、１つ又は複数のＧＮ２０内のランダムに設定されたタイマ２５６のうちの１つが、ＧＨ１０からハートビートメッセージ５１０を受信することなく満了したために、１つのＬＰＧ内に２つ以上のＧＨ１０が存在しており、ＧＨ１０がＬＰＧから離脱した可能性があることを示している。ＧＮ２０は、古いＧＨ１０がＬＰＧから出たものと仮定し、それゆえ、自らを新たなＧＨ１０として選択する。しかしながら、ＧＮ２０が何故ハートビートメッセージ５１０を受信し損なったかに関しては、いくつかの理由がある。たとえば、複数の他の信号が同じ帯域幅上で送信されることによって引き起こされる無線チャネルの輻輳が、ハートビートメッセージ５１０との干渉を引き起こし、ＧＮが信号を受信するのを妨げる可能性がある。
【００７０】
したがって、多数のＧＨハートビートメッセージ５１０が同じＬＰＧ内で送信されるとともに受信される。図３Ｂに示されるように、ＬＰＧ３３０内には３つのＧＨ１０、すなわちＧＨ Ａ３３１、ＧＨ Ｃ３３３及びＧＨ Ｅ３３５が存在する。各ＧＨ３３１、３３３及び３３５はそれぞれ、受信したヘッダ解決メッセージ５２０の一部であるグループリストを、メモリセクション２００に格納されているグループリストと比較する。しかしながら、ＧＨ３３１、３３３及び３３５がそれぞれ、同じＬＰＧ３３０内に既に存在しているので、そのリスト上の全ての、又は概ね全てのノードは同じである。しかし、余分な制御になることから、１つのＬＰＧには２つ以上のＧＨを有することができないので、ノードＧＨ３３１、３３３、３３５のうちの１つがそのＬＰＧのＧＨにとどまる。他のノードは、単なるレギュラーＧＮになり、新たなＧＨを介してＬＰＧに参加する。
【００７１】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどれがＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、新たなハートビートメッセージ５１０を既に送出したノードが、ＬＰＧ３３０の新たなＧＨとして選択される。別法では、元のＧＨを新たなＧＨとして再び選択することができる。その選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ｂの例に示されるように、ＬＰＧ３３０は、ある時点において、３つのＧＨ３３１、３３３、３３５、それぞれＧＨ Ａ、ＧＨ Ｃ及びＧＨ Ｅを有する。この例の便宜上、ＧＨ Ｃ３３３が元のＧＨであるが、ＧＨ Ａ３３１においてタイマ２５６が満了するとき、ＧＨ Ａはハートビートメッセージ５１０を送信し、自らをＧＨ１０として選択する。好ましい実施形態では、ＧＨ Ａ３３１が最も新しいハートビートメッセージ５１０を送出するので、ＧＨ Ａ３３１がそのＬＰＧの新たなＧＨ３３１になる。他の２つのＧＨ、ＧＨ Ｃ３３３及びＧＨ Ｅ３３５はそれぞれ、レギュラーノードＧＮ３４２及び３４４になる。さらに、ＧＨ Ａ３３１のＬＰＧ ＩＤが、後に残るＬＰＧのＬＰＧ ＩＤを決定する。ヘッダ解決が終了した後に、ＧＨ１０は、古いＧＨに対してＧＨ選択メッセージ５３０を送信し、そのノードに、そのＧＨ１０が新たなＧＨであることを通知する。
【００７２】
図３Ｃは、ヘッダ解決の第３の例を示す。第３の例では、別のＬＰＧからのＧＨが、既に１つのＧＨを有する１よりも大きなサイズのＬＰＧに移動することにより、１つのＬＰＧ内に２つ以上のＧＨが存在する。図３Ｃに示されるように、ノードＡがＬＰＧ３６２のＧＨ Ａ３６０であり、ノードＥがＬＰＧ３７２のＧＨ Ｅ３７０である。２つのＧＨ３６０及び３７０はそれぞれ、そのハートビートメッセージ５１０を送信し、ＬＰＧ３７２のＧＨ ＥがＬＰＧ３６２の無線受信範囲内に移動したので、２つのＧＨ３６０及び３７０はそれぞれ、互いのハートビートメッセージ５１０を受信する。このハートビートメッセージ５１０は、それぞれ、そのＬＰＧ３６２及び３７２の中の全てのノードに関する情報を含むグループリスト信号を含むことができる。別法では、ＧＨ３６０及び３７０は、別個のグループリスト信号を送信することができる。さらに、そのＬＰＧ内に２つ以上のＧＨが存在するものと判定された場合には、ＧＨ３６０及び３７０は、グループメンバー
シップリストを含むヘッダ解決メッセージ５１０を送信する。
【００７３】
ＧＨ３６０及び３７０はそれぞれ、受信されたグループメンバーシップリストを、メモリセクション２００に格納されているグループリストと比較する。それらのＧＨは異なるＬＰＧから来たものなので、そのグループリストは共通のノードを全く、又は少ししか持たない。別法では、各ＧＨ３６０及び３７０は、そのメモリセクション２００内に格納されているグループリスト上にあるいくつか又は全てのノードに問い合わせて、ノードが依然としてＬＰＧ内に存在するか否かを判定することができる。あるＧＨが、ノードが同じでない（たとえば、ＬＰＧ内にない）と判定する場合には、ＧＨ（Ｅ）は新たなグループ（ＬＰＧ３６２）に入ったことがわかる。ここで、そのＬＰＧ（ＬＰＧ３６２）内に２つ以上のＧＨが存在しており、余分な制御になるため、１つのＬＰＧは２つ以上のＧＨを有することができないので、ヘッダ解決によって、それらのノードのうちのＧＨになるべきノードを選択しなければならない。それゆえ、図３Ｃでは、ノードＧＨ３６０のうちの１つが、そのＬＰＧのＧＨにとどまり、他のノードが単なるレギュラーＧＮになり、残ったＧＨを介して、そのＬＰＧに参加する。
【００７４】
この選択過程は、所定の選択判定基準を用いて、それらのノードのうちのどれがＬＰＧのＧＨとして選択されることになるかを判定する。たとえば、最も多くの現在のノードグループを有するノードが、ＬＰＧ３６２のＧＨとして選択されることになる。たとえば、メモリセクション２００の中のグループリストを、他のＧＨから送信される受信されたグループリストと比較するときに、より多くの数の一致するノードを有するＧＨを選択する。別法では、別のＬＰＧに移動したと判定するＧＨは、そのＬＰＧが既に１つのＧＨを有するので、そのＬＰＧ内のＧＮに降格され、ＧＨを介してＬＰＧに参加することができる。その選択判定基準は、ＬＰＧが構成される前に予め決定される。図３Ｃの例に示されるように、ＬＰＧ３６２及び３７２はそれぞれ、１つのＧＨ３６０及び３７０だけを有する。ＧＨ Ｅ３７０がＬＰＧ３６２の近傍域に入り、ＬＰＧ３６０内に２つのＧＨが存在することになる。ＧＨ３６０及び３７０はいずれも、そのハートビートメッセージ５１０を送信する。
【００７５】
好ましい実施形態では、ＧＨ３６０は、いずれかの選択判定基準を用いて、現在のＬＰＧと共通のノードを最も多く有することになるので、そのＬＰＧの新たなＧＨになる。他方のＧＨ Ｅ３７０は、ＬＰＧ内のレギュラーノードすなわちＧＮ３８２になる。さらに、ＧＨ Ａ３６０のＬＰＧ ＩＤが、そのＬＰＧのＬＰＧ ＩＤを決定する。ヘッダ解決が終了した後に、そのＧＨは、古いＧＨに対して、ＧＨ選択メッセージ５３０を送信して、そのノードに、そのＧＨが新たなＧＨであることを通知する。ヘッダ解決が終了した後に、ステップ８において、新たなＧＨはＧＨ選択メッセージ５３０を送信する。その後、過程はステップ１に戻り、新たなＧＨがハートビートメッセージ５１０を送信する。
【００７６】
図４は、ＧＨに基づいてＬＰＧを形成するための有限状態機械を示す。グループヘッダ（ＧＨ）に基づくＬＰＧの場合、ノード（移動デバイス）がＧＨとして選択／選出される。各移動デバイスが、ターンオン状態４００中に初期化される。車両又はノードが１つしかない場合には、その移動デバイスは、遷移４０５を介して、自らのＬＰＧ及びＧＨになることによって、状態を状態４００から状態４１０に変更する。他の移動デバイスと出合うとき、その移動デバイスは、遷移４１５を介して、そのグループにグループノード（ＧＮ）として参加することによって、その状態を状態４００から状態４２０に変更する。別法では、他のノードと出合うとき、遷移４３５において、それぞれが自らのハートビートメッセージ５１０を送出して、ヘッダ解決が行われる（４３０）。上記のように、１つのＬＰＧ内に２つ以上のＧＨが存在するときに、ヘッダ解決が行われ、遷移４３５において複数のハートビートの送信が行われる。ヘッダ解決４３０によって、１つのノードが、状態４３０から状態４１０への遷移４４５を介してＧＨになり、他の全てのノードが、状態
４３０から状態４２０への遷移４５５を介してＧＮになる。各ノードは、ＧＨ又はＧＮになる能力を有する。たとえば、１つのＬＰＧ内の１つのＧＨが出て行ったとき、グループノードが新たなＧＨになることができ、ヘッダ解決が行われるとき、ＧＨがグループノードになることができる。さらに、ＧＮ内の設定されたタイマ２５６が満了する場合には、状態４２０から状態４１０への遷移４２５を介して、グループノードがＧＨになることができる。
【００７７】
図５は、本発明の一実施形態による、ＧＨによって制御されるＬＰＧに基づいて、２つのノードから１つのＬＰＧを形成する一例を示す。
【００７８】
図５は、２つのノードＡ５００及びＢ５０２を示しており、これらのノードはそれぞれ最初に、自らのＬＰＧを形成してＧＨになる。いずれも、ハートビートメッセージ５１０を送信し、互いのハートビートメッセージ５１０を受信する。信号を受信すると、ＧＨ１０はいずれも、別のＧＨがその近傍域内に存在することを理解し、ヘッダ解決メッセージ５２０を送信する。その後、両方のＧＨがヘッダ解決モード（ステップ７）に入り、２のグループサイズを有するＬＰＧに対して、１つのＧＨ１０が選択される。先に説明され図３Ａに示されるように、所定の選択判定基準を用いて、１つのノードが選択される。ノードＡ５００がＧＨ１０として選択され、ＧＨ Ａ５０４になり、ノードＢ５０２が、ＧＨ
Ａ５０４を介して、そのＬＰＧに参加しなければならない。ＧＨ Ａ５０４は、ＧＨ選択メッセージ５３０を送信して、ノードＢ５０２に通知する。それぞれ予め決定された一定の周期（Ｔ）で、ＧＨ Ａ５０４は、そのハートビートメッセージ５１０を送信する。またＧＨ Ａ５０４は、グループメンバーシップリストメッセージ５４０も送出する。このメンバーシップリスト５４０は、ハートビートメッセージ５１０に含まれることができる。別法では、グループメンバーシップリストメッセージ５４０は別個のメッセージであってもよく、より低い頻度（Ｔ＋ｂ）で伝送又は送信されることができる。ノードＢ５０２がこのハートビートメッセージ５１０を受信すると、ノードＢ５０２は、ＧＨ１０にＬＰＧ参加メッセージ５５０を送信し、そのノードがそのＬＰＧに参加することを要求する。
【００７９】
ＧＨ Ａ５０４は、ノードＢ５０２がＬＰＧに入るのを許可するか否かを判定する。この判定は、そのＬＰＧの最大許容サイズに基づくことができる。さらに、これは、そのグループの最大許容ホップによって判定することもできる。これらの判定基準を設けて、ＬＰＧ内の全てのＧＮ２０に対して情報が送信されるのにかかる時間を制限し、且つＬＰＧ内の制御メッセージ送信の回数を制限する。これは、ＬＰＧが車両安全通信の用途に対応する場合に考慮すべき重要な事柄である。
【００８０】
具体的には、ＧＨ１０は、送達されるまでにＬＰＧハートビートが進むことができるホップの数を制限することができる。しかしながら、ＧＨ１０が変化するとき、新たなＧＨが、ＬＰＧの異なる部分の中に存在することがあり、同じホップカウントでもＬＰＧの構造が変化し、たとえば、ＬＰＧの一部であったいくつかのノードが出て行って、ＬＰＧの一部でないノードが、その時点で、ＬＰＧの一部になることができるので、グループのメンバーが変化する可能性がある。ＧＨ１０が変化しても、ＬＰＧのメンバーシップを安定させておくための１つの方法は、ＧＨ１０から１ホップだけ離れているノードが、よりの多くのホップだけ離れているノードよりも早く満了するように、タイマ２５６の周期を変更することである。これは、ＧＨ１０が出て行く場合に、古いＧＨに近いノードほど、それを引き継ぐ傾向が強くなるという可能性を高めることができる。こうして、遠く離れたノードの場合を除いて、ＬＰＧのメンバーシップが過度に変化しないようにすることができる。
【００８１】
図５に示されるように、ＧＨ Ａ５０４が、ノードＢ５０２がＬＰＧに入るのを許可す
る場合には、ノードＢ５０２はＧＮ Ｂになる。その後、ＧＮ Ｂは、ＧＨ Ａ５０４に対してステータスメッセージ５６０を送信して、ＧＨ Ａ５０４にステータス更新を送信し、ＧＨ Ａ５０４が、そのグループ内の全てのノードの更新されたメンバーシップリストを維持できるようにする。ステータスメッセージ５６０は、無線チャネルを介して、ランダムな時間インターバル（ハートビートインターバルＴより短い時間）で、ＧＮ２０からＧＨ１０に送信される。これは、ステータスメッセージ５６０が全て、一斉にＧＮ２０からＧＨ１０に送信されて、無線チャネルが輻輳するのを避けるためである。理想的には、各ＧＮ２０は、異なる時刻に、ステータスメッセージ５６０を送信する。
【００８２】
さらに多くのノードがＬＰＧの近傍域に入るとき、新たな各ノードは、ＧＨのハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信することによってＬＰＧに参加することを要求する。ＬＰＧの最大許容サイズ又は最大許容ホップに達していない限り、ＧＨ１０は、ノードがグループのＧＮ２０になるのを許可する。
【００８３】
２つ以上のＬＰＧが同じ近傍域内に存在するときに、ＬＰＧの合併（merge）が行われる。しかしながら、ＬＰＧ全体が、他のＬＰＧとまとめて合併するわけではない。あるＬＰＧのノードは、１ノードずつＧＨ１０を介して他のＬＰＧに参加することによって、他のＬＰＧと「合併」する。これは、個々の車両がそれぞれの速度で、且つ他の車両との間に特定の間隔を空けて進行している路上の車両の場合に典型的である。それゆえ、ＬＰＧ内への車両の合併は典型的には、一度に１台ずつ行われる。これは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していないことも確保する。
【００８４】
図６Ａ〜図６Ｃは、起こり得る合併シナリオの３つの異なる例を示す。図６Ａは第１の例を示しており、この場合、２つのＬＰＧグループのうちの一方だけがＧＨ１０、ＧＨ Ａ６００を有する。ＬＰＧ１ ６５０は、４つのノードＡ、Ｂ、Ｃ、Ｄから成り、ノードＡ６００はＧＨ１０であり、ノードＢ、Ｃ及びＤはそれぞれ、ＧＮ６０１、６０２及び６０３である。ＬＰＧ２ ６６０は３つのノード、Ｅ、Ｐ及びＱ、それぞれ６０５、６０６及び６０７を含む。ＬＰＧ２ ６６０にはＧＨがない。ＬＰＧ２ ６６０は、各ノードＥ、Ｐ及びＱに、ＧＨ Ａ６００に対する信号の送信によりＬＰＧ１（ＬＰＧ６５０）への参加を要求させることによって、ＬＰＧ１ ６５０と合併する。ノードＥ、Ｐ及びＱは、ＧＨ Ａ６００からハートビートメッセージ５１０を受信し、ＧＨ Ａ６００に対して参加メッセージ５５０を送信することによって応答する。ＧＨ Ａ６００は、ＬＰＧの最大許容サイズ又は最大許容ホップカウントを判定することによって、ノードＥ６０５、Ｐ６０６及びＱ６０７がＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントを超えていない場合には、ＧＨ Ａ６００は、それらのノードがＧＮになるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮは、ＧＨ１０に対して、そのステータスメッセージを周期的に送信する。
【００８５】
図６Ｂは第２の例を示しており、この場合、いずれのグループともＧＨ１０を持たない。図６Ｂでは、ＬＰＧ１ ６５０は、４つのノードＡ、Ｂ、Ｃ、Ｄ、それぞれ６１０〜６１３から成る。ＬＰＧ２は、先に示されたのと同じ３つのノード、Ｅ、Ｐ、Ｑ６０５〜６０７から成る。この状況では、必要であれば（すなわち２つ以上のＧＨ１０があれば）、上記のようなヘッダ解決ルールを用いて、ハートビートメッセージ５１０を送信する最初のノードが、ＧＨ１０になる。各ノードはランダムに設定されたタイマ２５６を有し、それは、ノードがハートビートメッセージ５１０を受信しない場合には満了する。それゆえ、新たなＧＨ１０は、そのタイマが最初に満了したノードである。
【００８６】
その後、新たなＧＨ１０は、新たなＬＰＧを編成する。新たなＬＰＧ ＩＤ番号は、ＧＨ番号に基づく。新たなＧＨ１０は、そのハートビートメッセージ５１０を周期的に送信
し、他のノードは、新たなＧＨを介してＬＰＧに参加する。
【００８７】
具体的には、他のノードは、新たなＧＨに対して参加メッセージ５５０を送信する。新たなＧＨは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達しているか否かを判定することによって、ノードがＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していない場合には、新たなＧＨは、それらのノードがＧＮ２０になるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮは、ＧＨ１０に対して、そのステータスメッセージ５６０を周期的に送信する。
【００８８】
図６Ｃは、両方のＬＰＧがＧＨ１０を有し、且つ異なるＬＰＧからのノードが参加する、合併の第３の例を示す。図６Ｃでは、ＬＰＧ１ ６５０がＧＨ Ａ６００を有し、ＬＰＧ２ ６６０がＧＨ Ｑ６４０を有する。ＬＰＧ１ ６５０はＧＮ Ｂ、Ｃ及びＤ、それぞれ６０１〜６０３を有し、ＬＰＧ２ ６６０はＧＮ Ｅ６０６及びＧＮ Ｐ６０７を有する。ヘッダ解決を用いて、合成されたＬＰＧの１つのＧＨ１０が決定される。ＧＨ Ａ６００及びＧＨ Ｑ６４０は、ヘッダ解決メッセージ５２０を送信し、ヘッダ解決モードに入る。新たに合成されたＬＰＧのＧＨ１０は、上記のヘッダ解決ルールに基づいて、たとえば、所定の選択判定基準に基づいて決定される。新たなＧＨ１０が選択されると、新たなＧＨ１０はその後、新たなＬＰＧを編成する。その後、新たなＧＨは、そのハートビートメッセージ５１０を周期的に送信し、他のノードは、新たなＧＨ１０を介してＬＰＧに参加する。
【００８９】
他のノードは、新たなＧＨ１０に対して参加メッセージ５３０を送信する。新たなＧＨは、ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達しているか否かを判定することによって、ノードがＬＰＧに入るのを許可するか否かを判定する。ＬＰＧの最大許容サイズ又は最大許容ホップカウントに達していない場合には、新たなＧＨは、それらのノードがＧＮ２０になるのを許可し、カウンタをインクリメントして、ＬＰＧ内のノードの数を更新する。その後、新たなＧＮ２０は、ＧＨ１０に対して、そのステータスメッセージ５６０を周期的に送信する。新たなＬＰＧ ＩＤ番号は、ＧＨ番号に基づく。
【００９０】
ＬＰＧ内のいずれかのノードが、通信できないようにＧＨ１０から離隔されるとき、たとえば無線伝送の範囲外になるとき、ＬＰＧの分割が行われる。この場合、ＧＨ１０を有するグループは、それまでと同様に動作を継続する。ＧＨ１０からもはやハートビートメッセージ５１０を受信できないノードは、そのＬＰＧから分割し、自らのＬＰＧを形成するか、又は別のＬＰＧに参加する。或るノードがＬＰＧから分割するとき、ＧＨ１０は、離れつつあるノードから周期的な更新又はステータスメッセージ５６０を受信しなくなるので、上記のように、ＧＨのメモリセクション２００に格納されるグループリストからＧＮ２０を「無効にする（age）」。その後、ＧＨ１０は、予め設定された時間が経過した後に、ＬＰＧリストから、そのノードを削除する。これは、ＧＨが更新されたメンバーシップリスト、及びＬＰＧ内のノードの数に関する現在のカウントを維持するのを助け、所定の最大サイズ値に達していない場合に、新たなノードがＬＰＧへのメンバーシップを許可されないようにする。
【００９１】
元のＬＰＧから分割するノードが、新たなグループを形成する場合には、新たなＧＨ１０を選択する必要がある。ハートビートインターバル（Ｔ）中にハートビートメッセージ５１０が聞こえなかった後にタイマ２５６が満了すると、ノードのうちの１つが新たなＧＨ１０になる。新たなＧＨ１０は、必要であれば（すなわち２つ以上のＧＨ１０があれば）、ヘッダ解決ルールを用いて選択される。新たなグループは、古いグループと同じＬＰＧ ＩＤを用いることになるが、新たなＧＨ ＩＤを用いて固有性を与える。元のＬＰＧから分割する他のノードは、新たなＧＨ１０を通して新たなＬＰＧに参加する。ノードは
、新たなＧＨ１０からハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信する。ＧＨ１０は、ＬＰＧのための所定の最大サイズに達するまで、又は最大ホップカウントに達するまで、全てのノードが参加するのを許可する。別法では、ノードがこの判定を行うことができる。
【００９２】
一方、元のＬＰＧから分割するノード、たとえばノードＥ、Ｐ及びＧ、Ｆは、別のＬＰＧに参加することができる。これらのノードは、他のＬＰＧのＧＨ１０を介して参加する。それらのノードは、ＧＨ１０からハートビートメッセージ５１０を受信し、参加メッセージ５５０を送信して、他のＬＰＧへの参加を要求する。ＧＨ１０は、予め決定された閾値に基づいて、それらのノードがＬＰＧに参加できるか否かを判定する。
【００９３】
或るノードがＬＰＧから出るとき、他のノードは、ＬＰＧのステータスの変化を通知されなければならない。ＧＮ２０がそのグループから出る場合には、そのＧＮ２０は、自身が離れつつあることをＧＨ１０に積極的に通知することができる。その後、ＧＨ１０は、そのメモリセクション２００から、そのＧＮ ＩＤを積極的に削除する。別法では、ＧＮ２０がＬＰＧから出る場合には、ＧＨ１０は、ＧＮ２０からランダムに送信されるステータスメッセージ５６０を受信しなくなる。その際、上記のように、ＧＨ１０はノードを「無効」にし、予め設定された時間が経過した後に、ＧＨ１０は、そのメモリセクションからＧＮ ＩＤを削除する。
【００９４】
離脱するノードがＧＨ１０である場合には、ハートビートメッセージ５１０が送信されなくなり、ＧＮ２０がいずれもハートビートメッセージ５１０を受信しなくなる。それゆえ、新たなＧＨ１０が選択されなければならない。新たなハートビートメッセージ５１０を最初に送信するＧＮ２０が、新たなＧＨ１０と見なされる。タイマ２５６が満了したノードが、このハートビートメッセージ５１０を送信する。その後、新たなＧＨ１０はハートビートメッセージ５１０と、メモリに格納される最新の既知のグループリストとを送出する。その他のノードは、ＬＰＧ内にＧＮ２０のまま存在し続ける。ここで、それらのノードは、新たなＧＨ１０に対して、ステータスメッセージ５６０を送信する。
【００９５】
図８は本発明の第２の実施形態を示す。第２の実施形態によれば、複数の二次ヘッダノード又はコアノード８００を用いて、ＬＰＧ８１０の調整及び制御を助けることができる。複数の二次ヘッダノード８００は、ＧＨ１０と同じように動作し、且つグループリスト情報を受信するように選択される。一次ＧＨ１０が依然としてＬＰＧ８１０内に存在するとき、ＬＰＧ８１０内の二次ＧＨノード８００は、一次ＧＨ１０に対するホットスタンバイとしての役割を果たすために情報を収集する。すなわち、二次ＧＨノード８００は情報を収集するが、他の点では、ＬＰＧ８１０を管理するための一次ＧＨ１０ノードとしての役割は果たさない。二次ＧＨノード８００は、一次ＧＨ１０がＬＰＧ８００から出るときに、新たなＧＨがＬＰＧ８１０の構造に最小限の影響しか及ぼさないように、すなわち、一次ＧＨへの最大ホップカウント内にあるノードが依然として新たなＧＨ１０への最大ホップカウント内に存在するように、そのノードの一次ＧＨへの近さに基づいて選択される。ＬＰＧ構造の安定性を助長するための１つの方法は、一次ＧＨ１０からのホップの数に基づいて、二次ＧＨノード８００を選択することである。
【００９６】
一次ＧＨ１０がＬＰＧ８１０から出るとき、二次ヘッダノード８００のうちの１つがＧＨを引き継ぐ。一次ＧＨ１０ノードがＬＰＧ８１０から出るとき、そのＧＨ１０は、コアノードに対して新たなＧＨ１０ノードになるよう通知する。二次ＧＨノード８００に通知できない場合には、二次ＧＨノード８００は、出て行った一次ＧＨ１０ノードからのハートビートメッセージが聞こえないためにタイマが満了することによって、一次ＧＨ１０ノードが出て行ったことを見出す。その後、二次ＧＨノード８００は、新たなＧＨ１０ノードになる。二次ＧＨノード８００はＧＨと同じように動作し、グループリスト情報を受信
しているので、ＧＨの移行は概ね瞬時に行われる。ホットスタンバイ状態の二次ノード８００が２つ以上存在する場合には、それらのうちの１つが選択される。その選択は、ＧＨ１０ノードの引き継ぎに関して予め確立された序列に基づくこともできるし、あるいは離れつつある一次ＧＨ１０ノードに最も近い（すなわち、ホップ数が最も小さい）ものが、新たなＧＨ１０ノードを引き継ぐこともできる。ＬＰＧ８１０内の残りのノードはレギュラーノード８１５である。
【００９７】
図９は、本発明の第３の実施形態を示す。この実施形態では、ＬＰＧ９１０は、１つのグループヘッダノード（ＧＨ）１０、複数のゲートウエイノード９００及びレギュラーノード９０５から形成される。ＧＨ１０は、特別なゲートウエイノード又はクラスタヘッドである。この実施形態では、ＧＨ１０及びゲートウエイノード９００だけがメッセージを転送することができる。これは、上記のように、ＧＨだけを基にする編成から、無線チャネル内のメッセージの流れを削減する。上記の実施形態では、ＧＨ１０と各ノードとの間で情報を交換するために、またＬＰＧ９１０の構造を維持するために、複数の制御メッセージが送出される。この結果として、無線チャネルが、これらのメッセージによって占有され、妨害されることがある。
【００９８】
この実施形態では、ＧＨ１０は、第１の実施形態の場合に開示されたのと同じヘッダ解決を用いて選択され、ＬＰＧ９１０は、ＬＰＧ９１０内に１つの中心を成すＧＨ１０を有する。この時点で、ＬＰＧ内に他のノードは存在せず、他の構造も存在しない。その後、ＧＨ１０は、無線伝送範囲内（そのＧＨへの第１のホップ距離内）にある任意のノードに対して、ハートビートメッセージ５１０を送信する。ハートビートメッセージ５１０を受信するノードは、その無線伝送範囲内にハートビートメッセージ５１０を送信し直す。ハートビートメッセージ５１０は、ホップカウント限界に達するまで、ノードによって再送信され続ける。各ノードは、種々の近くにあるノードから、ハートビートメッセージ５１０の複数のコピーを受信することができる。最初の複製でないハートビートメッセージ５１０を転送する各ノードは、そのゲートウエイノード９００になり、ゲートウエイノード９００は通知される。ＧＨ１０又はゲートウエイノード９００でない全てのノードはレギュラーノード９０５になる。
【００９９】
所定の選択判定基準に基づいて、いくつかのノードは、ＬＰＧ９１０のためのゲートウエイノード９００として選択されることになり、他の全てのノードはレギュラーノード９０５になる。レギュラーノード９０５はメッセージを送信することができる。しかしながら、レギュラーノード９０５は、メッセージを転送することはできない。ＬＰＧ９１０内のＧＨ１０及び少なくとも１つのゲートウエイノード９００が、メッセージ送達を扱う。さらに、ハートビートメッセージ５１０そのものが、ＬＰＧ構造を維持するために用いられるので、ＬＰＧを編成する目的を果たすために、他の制御メッセージを生成する必要はない。さらに、いくつかのノードが異なる場所に移動した場合であっても、その度に、ハートビートメッセージ５１０を用いて新たな構造が構成される。
【０１００】
具体的には、ゲートウエイノード９００は、ＧＨの初期最大伝送範囲９１５を越えてＧＨ１０の無線範囲を拡張するために用いられる（拡張された範囲９２０）。各レギュラーノード９０５は、ゲートウエイノード９００にステータスメッセージ５６０を送信することができ、ゲートウエイノードは、ステータスメッセージ５６０をＧＨ１０に中継する。ゲートウエイノード９００は、所定の時間（Ｐ）だけ待機し、受信する全てのステータスメッセージ５６０を収集する。ステータスメッセージ（複数可）５６０は、メモリに格納される。所定の時間が満了すると、ゲートウエイノード（複数可）９００は、所定の時間（Ｐ）中にゲートウエイノード（複数可）９００が受信した複数のステータスメッセージ５６０の集合を含む１つのメッセージを送信する。このメッセージは、他のゲートウエイノード９００を介してＧＨ１０に中継することができる。
【０１０１】
グループヘッダに基づくＬＰＧの１つの利点は、各ＬＰＧの無線帯域幅負荷を制限するようにＬＰＧのサイズ（すなわち、各ＬＰＧ内のノードの数）を制御して、各ＬＰＧ内の通信待ち時間に下限を与えることができることである。グループヘッダに基づくＬＰＧの別の利点は、各ＬＰＧ内のＧＨノード及びＧＮノードの知識である。そのような知識を用いて、各ノードが、そのルーティングテーブルを作成する際に、宛先として、（ＬＰＧ内の）全ての他のノードに向かって次のホップノードをより効率的に選択できるようになるので、ＧＨノードから離れるホップの数によって、ルーティング及びマルチキャストプロトコル（ＬＰＧ内通信用）を効率的にすることができる。コアノードを使用することによって、グループヘッダに基づくＬＰＧの安定性がさらに増す。これはルーティング及びマルチキャスト通信にとって極めて重要である。ゲートウエイノードを使用することによって、（ＬＰＧを維持するための）制御トラフィックの量を削減することができ、それにより、無線帯域幅の利用を改善し、通信遅延時間を短縮することができる。
【０１０２】
各移動無線デバイス又はノードは、そのデバイスが上記の機能を実行できるようにする、メモリ手段に導入されるプログラムを含む。
【０１０３】
このプログラム又はソフトウエアパッケージは、製造時に、移動中の無線デバイスに導入することができる。別法では、そのプログラムは、導入後に、遠隔の場所から移動中の無線デバイスにアップロードすることができる。
【０１０４】
本明細書において、本発明が、特定の例示的な実施形態を参照しながら説明されてきた。本発明の範囲から逸脱することなく、特定の改変又は変更が当業者には明らかであろう。それらの例示的な実施形態は、説明することを意図しており、添付の特許請求の範囲によって規定される本発明の範囲を限定することは意図していない。
【図面の簡単な説明】
【０１０５】
【図１】本発明による２つのローカルピアグループの一例を示す図である。
【図２Ａ】本発明によるグループヘッダノード（ＧＨ）内の内部構造の一部のブロック図である。
【図２Ｂ】本発明によるグループノード（ＧＮ）の内部構造の一部のブロック図である。
【図３】本発明の一実施形態によるＬＰＧの形成及び維持のフローチャートである。
【図３Ａ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の一例を示す図である。
【図３Ｂ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の異なる例を示す図である。
【図３Ｃ】本発明の一実施形態による、ヘッダ解決ルールを用いるヘッダ解決の異なる例を示す図である。
【図４】本発明の一実施形態による、ＧＨに基づくＬＰＧ形成のための有限状態機械（finite state machine）を示す図である。
【図５】本発明の一実施形態による２つのノードからのＬＰＧの形成を示す図である。
【図６Ａ】本発明の一実施形態による、起こり得る合併シナリオの一例を示す図である。
【図６Ｂ】本発明の一実施形態による、起こり得る合併シナリオの異なる例を示す図である。
【図６Ｃ】本発明の一実施形態による、起こり得る合併シナリオの異なる例を示す図である。
【図７】或るノードがＬＰＧに参加することができるか否かを判定する別の方法を示す図である。
【図８】本発明の第２の実施形態によるＬＰＧを示す図である。
【図９】本発明の第３の実施形態によるＬＰＧを示す図である。
【特許請求の範囲】
【請求項１】
複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法であって、該複数の移動ノードは、該複数の移動ノードを順序付けすることなく、動的に形成されるローカルピアグループ（ＬＰＧ）に分割され、該方法は、
前記複数の移動ノードから、一意のグループヘッダ識別情報が割り当てられるとともに前記ＬＰＧを制御及び管理する、前記ＬＰＧのグループヘッダノード（ＧＨ）を選択するステップと、
前記選択されたＧＨから、ハートビートメッセージ信号を含む複数の制御メッセージを、一定のインターバルで送信するステップと、
前記複数の移動ノードのうちの他のノードが前記ＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定するステップと、
前記複数の移動ノードのうちの前記他のノードがグループノード（ＧＮ）として前記ＬＰＧに参加することができるものと判定される場合には、前記複数の移動ノードのうちの前記他のノード間にネットワークリンクを構築するステップと
を含む、複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項２】
前記ＬＰＧ内に２つ以上のＧＨが存在する場合には、前記選択するステップは、
前記２つ以上のＧＨのそれぞれからヘッダ解決メッセージを送信するステップと、
所定の選択判定基準に基づいてヘッダ解決を実行して、前記ＬＰＧのＧＨとしてＧＨを１つだけ選択するステップと、
選択された新たなＧＨによってＧＨ選択メッセージを送信し、前記２つ以上のＧＨの他のＧＨが、前記新たなＧＨを介して前記ＬＰＧに参加するステップと
をさらに含む、請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項３】
前記所定の選択判定基準は、前記ハートビートメッセージを送信する前記２つ以上のＧＨのうちの最初のノードに基づく、請求項２に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項４】
前記ハートビートメッセージは、ローカルピアグループ識別情報と、ＧＨ識別番号と、前記ＬＰＧ内のノードの数と、該ＬＰＧ内で許可されるノードの最大数と、ホップカウントと、最大ホップと、次のハートビートメッセージの時刻とを含む、請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項５】
無線範囲内の前記複数の移動ノードのうちの前記他のノードによって前記ハートビートメッセージを受信するステップと、
前記ＧＨに対してローカルピアグループ参加メッセージを送信するか否かを判定するステップと
をさらに含み、
前記判定は、少なくとも１つのパラメータと前記所定の閾値との比較に基づき、
前記少なくとも１つのパラメータは、前記ＬＰＧ内の前記ノードの数及び前記ホップカウントを含み、
前記所定の閾値は、該ＬＰＧ内で許可されるノードの前記最大数及び前記最大ホップであり、
前記複数の移動ノードのうちの前記他のノードは、前記少なくとも１つのパラメータが前記所定の閾値を超えない場合には、前記ローカルピアグループ参加メッセージを送信し、前記少なくとも１つのパラメータが前記所定の閾値を超える場合には、該ＬＰＧ参加メッセージを送信しない、
請求項４に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持す
る方法。
【請求項６】
前記ハートビートメッセージを受信すると、前記複数の移動ノードのうちの前記他のノードは、前記ＧＨに対してローカルピアグループ参加信号を送信し、
前記ＧＨによって実行される、前記複数の移動ノードのうちの前記他のノードが参加できるか否かを判定する前記ステップは、少なくとも１つのパラメータと前記所定の閾値との比較に基づき、
前記少なくとも１つのパラメータは前記ＬＰＧ内のノードの数及びホップカウントを含み、
前記所定の閾値は、該ＬＰＧ内で許可されるノードの最大数及び最大ホップであり、
前記ＧＨは、前記少なくとも１つのパラメータが前記所定の閾値を超えない場合には、前記複数の移動ノードのうちの前記他のノードがＧＮとして前記ＬＰＧに参加するのを許可し、前記少なくとも１つのパラメータが前記所定の閾値を超える場合には、前記複数の移動ノードのうちの前記他のノードがＧＮとして該ＬＰＧに参加するのを許可しない、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項７】
前記複数の制御メッセージは、前記ＬＰＧ内の全てのＧＮの識別情報と、ローカルピアグループ識別情報と、ＧＨ識別情報と、タイムスタンプとを含むグループメンバーシップメッセージをさらに含み、
前記ＬＰＧ内のＧＮの前記識別情報は、該ＧＮから送信されるステータスメッセージを介して周期的に更新される、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項８】
所定の時間インターバル後に前記ステータスメッセージが前記ＧＮから受信されない場合、又は前記ＧＮからの積極的な離脱メッセージが前記ＧＨによって受信された場合には、該ＧＮの前記識別情報が前記グループメンバーシップメッセージから削除される、
請求項７に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項９】
前記ＧＮにおいて前記ＧＨからの前記ハートビートメッセージを受信するステップと、
前記ＬＰＧ内の各ＧＮにおいて、タイマを前記ハートビート周期よりも大きな値にランダムに設定するとともに次のハートビートメッセージを待つステップと、
ハートビートメッセージが受信されないときに前記タイマの時間を減らしていくステップと
をさらに含み、
次のハートビートメッセージを受信する前に前記タイマが満了する場合には、最初にタイマが満了した前記ＧＮが自らのハートビートメッセージを送信して、新たなＧＨとして動作し、該ハートビートメッセージを送信する最初のＧＮが、前記ＬＰＧの前記新たなＧＨになる、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１０】
前記グループメンバーシップメッセージは前記ハートビートメッセージに含まれ、前記一定のインターバルで送信される、
請求項７に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１１】
前記ＬＰＧに対して少なくとも１つのゲートウエイノードを選択するステップをさらに
含み、該少なくとも１つのゲートウエイノードは、複数のメッセージを前記ＧＮから前記ＧＨに中継する機能を果たす、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１２】
前記少なくとも１つのゲートウエイノードは、前記ＧＮから受信される複数のステータスメッセージを収集し、該複数のステータスメッセージをメモリに格納し、所定の時間が経過した後に、前記ＧＨに対して、該複数のステータスメッセージの集合を含む１つのメッセージを送信する、
請求項１１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１３】
少なくとも１つの二次ＧＨを選択するステップをさらに含み、
前記ＧＨが前記ＬＰＧから出る場合に、該少なくとも１つの二次ＧＨが該ＬＰＧの新たなＧＨになる、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１４】
アドホック無線ネットワークシステムであって、
順序づけされない複数の移動無線デバイスから動的に形成される、少なくとも１つのローカルピアグループ（ＬＰＧ）を含み、該ＬＰＧは、
前記複数の移動無線デバイスから選択され、一意のグループヘッダ識別情報を割り当てられるグループヘッダノード（ＧＨ）であって、ハートビートメッセージを含む複数の制御メッセージを一定のインターバルで送信することによって、前記ＬＰＧを制御及び管理する、グループヘッダノード（ＧＨ）と、
前記少なくとも１つのＬＰＧにおいて、所定の閾値に達していないときに、前記ＧＨの無線範囲内の前記複数の移動無線デバイスのうちの残りの移動無線デバイスから生成される少なくとも１つのグループノード（ＧＮ）と
を備え、
前記少なくとも１つのＧＮは、該少なくとも１つのＧＮと前記ＧＨとの間に形成されるネットワークリンクを介して前記ＧＨと通信することができ、また、該ＧＮについての情報を含むステータスメッセージを前記ＧＨに送信する、アドホック無線ネットワークシステム。
【請求項１５】
前記複数の移動無線デバイスのうちの前記残りの移動無線デバイスから選択される少なくとも１つのゲートウエイノードをさらに備え、
該少なくとも１つのゲートウエイノードは、複数のメッセージを前記少なくとも１つのＧＮから前記ＧＨに中継する機能を果たし、
該複数のメッセージは、前記少なくとも１つのＧＮから前記ＧＨへのステータスメッセージを含み、
前記少なくとも１つのゲートウエイノードは、前記少なくとも１つのＧＮから受信される前記ステータスメッセージを収集し、該ステータスメッセージを格納し、所定の時間が経過した後に、該所定の時間中に該少なくとも１つのゲートウエイノードによって受信される全ての該ステータスメッセージの集合を含む１つの集合ステータスメッセージを前記ＧＨに対して送信する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１６】
前記移動無線デバイスは、メモリセクションと、タイマと、制御手段と、送受信セクションと、ハートビート生成手段とを備え、
前記ハートビート生成手段は、前記一定のインターバルでハートビートメッセージを生
成し、
該ハートビートメッセージは、ＬＰＧ識別番号、ＧＨ識別情報、前記ＬＰＧのノードの数、該ＬＰＧにおいて許可されるノードの最大数、ホップカウント、最大ホップ及び次のハートビートメッセージの時刻を含み、
前記移動無線デバイスが前記ＧＨとして選択されるとき、前記一定のインターバルは前記タイマによってカウントされ、
該タイマが満了するとき、前記ハートビート発生セクションは、前記メモリセクションに格納されている情報に基づいて、前記ハートビートメッセージを送信し、
前記制御セクションは、所定の値と少なくとも１つのパラメータとを比較することによる前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの１つが前記ＬＰＧに参加できるか否かの判定を含む、前記ＧＨの制御を行い、
前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの前記１つが前記ＬＰＧに参加できるものと判定される場合には、前記制御セクションは、前記送信受信セクションに、ＧＮ受諾メッセージを送信するように指示し、一方、該制御セクションが、前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの前記１つが参加できないものと判定する場合には、該制御手段は、該送受信セクションに、ＧＮ拒否メッセージを送信するように指示する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１７】
前記残りの複数の移動無線デバイスがＧＮとして選択されるとき、該ノードは、メモリ手段と、タイマと、制御セクションと、送受信セクションとを備え、
前記送受信セクションは、前記ＧＨに対して一定のインターバルでステータスメッセージを送信し、
前記一定のインターバルは前記タイマによってカウントされ、
該タイマが満了するとき、前記送受信セクションは、前記メモリ手段に格納されている情報に基づいて、前記ステータスメッセージを送信し、
また前記タイマは前記ハートビート周期よりも長いランダムな時間に設定され、
前記送受信セクションが前記ハートビートメッセージを受信すると、前記タイマは別のハートビートメッセージを受信するためにリセットされ、
該タイマが満了する前に、該送受信セクションがハートビートメッセージを受信しない場合には、前記制御手段は、該送受信セクションに、前記メモリ手段に格納されている、前記ＬＰＧに関する情報を含む自らのハートビートメッセージを送信し、該ＬＰＧの新たなＧＨとして動作するように指示する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１８】
前記ＬＰＧ内に２つ以上のＧＨが存在する場合には、該２つ以上のＧＨは、互いに対してヘッダ解決メッセージを送信し、ヘッダ解決モードに入って、所定の選択判定基準に基づいて、前記ＬＰＧの前記ＧＨとして１つのＧＨを選択し、１つのＧＨが選択された後に、該１つのＧＨは、前記ＬＰＧ内の他の全てのＧＮに対してＧＨ選択メッセージを送信し、その後、前記ハートビートメッセージを送信し、前記２つ以上のＧＨの他のＧＨは、前記新たなＧＨを介して、前記ＬＰＧに参加する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１９】
前記残りの複数の移動無線デバイスが前記ハートビートメッセージを受信するとき、該残りの複数の移動無線デバイスは、前記ＧＨに対してＬＰＧ参加メッセージを送信するか否かを判定し、
該判定は、少なくとも１つのパラメータを所定の閾値と比較することに基づき、
該少なくとも１つのパラメータが前記所定の閾値を超えないものと判定される場合には、前記残りの複数の移動無線デバイスは、前記ＬＰＧ参加メッセージを送信し、該少なくとも１つのパラメータが前記所定の閾値を超える場合には、前記ＬＰＧ参加メッセージを
送信しない、
請求項１４に記載のアドホック無線ネットワーク。
【請求項２０】
複数の移動ノード間にアドホック無線ネットワークを確立及び維持するためのアドホックネットワークであって、該複数の移動デバイスは、該複数の移動ノードを順序付けすることなく、動的に形成されるローカルピアグループ（ＬＰＧ）に分割され、該ネットワークはコンピュータ読取り可能記憶媒体上に与えられるコンピュータ読取り可能プログラムコードを実行するためのプロセッサを備え、該コンピュータ読取り可能プログラムコードは命令を有し、該命令によって、該プロセッサは、
前記複数の移動ノードから、一意のグループヘッダ識別情報を割り当てられるとともに前記ＬＰＧを制御及び管理する、前記ＬＰＧのグループヘッダノード（ＧＨ）を選択するステップと、
前記選択されたＧＨから、ハートビートメッセージを含む複数の制御メッセージを一定のインターバルで送信するステップと、
前記複数の移動ノードのうちの他のノードが前記ＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定するステップと、
前記複数の移動ノードのうちの前記他のノードがグループノード（ＧＮ）として前記ＬＰＧに参加することができるものと判定される場合には、該複数の移動ノードのうちの前記他のノード間にネットワークリンクを構築するステップと
を実行する、複数の移動ノード間にアドホック無線ネットワークを確立及び維持するためのアドホックネットワーク。
【請求項２１】
前記複数の無線デバイスは少なくとも１つの車両である、請求項１４に記載のアドホック無線ネットワーク。
【請求項２２】
前記複数の無線デバイスは、車両に接続されるか、又は内蔵される少なくとも１つの無線デバイスである、請求項１４に記載のアドホック無線ネットワーク。
【請求項１】
複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法であって、該複数の移動ノードは、該複数の移動ノードを順序付けすることなく、動的に形成されるローカルピアグループ（ＬＰＧ）に分割され、該方法は、
前記複数の移動ノードから、一意のグループヘッダ識別情報が割り当てられるとともに前記ＬＰＧを制御及び管理する、前記ＬＰＧのグループヘッダノード（ＧＨ）を選択するステップと、
前記選択されたＧＨから、ハートビートメッセージ信号を含む複数の制御メッセージを、一定のインターバルで送信するステップと、
前記複数の移動ノードのうちの他のノードが前記ＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定するステップと、
前記複数の移動ノードのうちの前記他のノードがグループノード（ＧＮ）として前記ＬＰＧに参加することができるものと判定される場合には、前記複数の移動ノードのうちの前記他のノード間にネットワークリンクを構築するステップと
を含む、複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項２】
前記ＬＰＧ内に２つ以上のＧＨが存在する場合には、前記選択するステップは、
前記２つ以上のＧＨのそれぞれからヘッダ解決メッセージを送信するステップと、
所定の選択判定基準に基づいてヘッダ解決を実行して、前記ＬＰＧのＧＨとしてＧＨを１つだけ選択するステップと、
選択された新たなＧＨによってＧＨ選択メッセージを送信し、前記２つ以上のＧＨの他のＧＨが、前記新たなＧＨを介して前記ＬＰＧに参加するステップと
をさらに含む、請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項３】
前記所定の選択判定基準は、前記ハートビートメッセージを送信する前記２つ以上のＧＨのうちの最初のノードに基づく、請求項２に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項４】
前記ハートビートメッセージは、ローカルピアグループ識別情報と、ＧＨ識別番号と、前記ＬＰＧ内のノードの数と、該ＬＰＧ内で許可されるノードの最大数と、ホップカウントと、最大ホップと、次のハートビートメッセージの時刻とを含む、請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項５】
無線範囲内の前記複数の移動ノードのうちの前記他のノードによって前記ハートビートメッセージを受信するステップと、
前記ＧＨに対してローカルピアグループ参加メッセージを送信するか否かを判定するステップと
をさらに含み、
前記判定は、少なくとも１つのパラメータと前記所定の閾値との比較に基づき、
前記少なくとも１つのパラメータは、前記ＬＰＧ内の前記ノードの数及び前記ホップカウントを含み、
前記所定の閾値は、該ＬＰＧ内で許可されるノードの前記最大数及び前記最大ホップであり、
前記複数の移動ノードのうちの前記他のノードは、前記少なくとも１つのパラメータが前記所定の閾値を超えない場合には、前記ローカルピアグループ参加メッセージを送信し、前記少なくとも１つのパラメータが前記所定の閾値を超える場合には、該ＬＰＧ参加メッセージを送信しない、
請求項４に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持す
る方法。
【請求項６】
前記ハートビートメッセージを受信すると、前記複数の移動ノードのうちの前記他のノードは、前記ＧＨに対してローカルピアグループ参加信号を送信し、
前記ＧＨによって実行される、前記複数の移動ノードのうちの前記他のノードが参加できるか否かを判定する前記ステップは、少なくとも１つのパラメータと前記所定の閾値との比較に基づき、
前記少なくとも１つのパラメータは前記ＬＰＧ内のノードの数及びホップカウントを含み、
前記所定の閾値は、該ＬＰＧ内で許可されるノードの最大数及び最大ホップであり、
前記ＧＨは、前記少なくとも１つのパラメータが前記所定の閾値を超えない場合には、前記複数の移動ノードのうちの前記他のノードがＧＮとして前記ＬＰＧに参加するのを許可し、前記少なくとも１つのパラメータが前記所定の閾値を超える場合には、前記複数の移動ノードのうちの前記他のノードがＧＮとして該ＬＰＧに参加するのを許可しない、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項７】
前記複数の制御メッセージは、前記ＬＰＧ内の全てのＧＮの識別情報と、ローカルピアグループ識別情報と、ＧＨ識別情報と、タイムスタンプとを含むグループメンバーシップメッセージをさらに含み、
前記ＬＰＧ内のＧＮの前記識別情報は、該ＧＮから送信されるステータスメッセージを介して周期的に更新される、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項８】
所定の時間インターバル後に前記ステータスメッセージが前記ＧＮから受信されない場合、又は前記ＧＮからの積極的な離脱メッセージが前記ＧＨによって受信された場合には、該ＧＮの前記識別情報が前記グループメンバーシップメッセージから削除される、
請求項７に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項９】
前記ＧＮにおいて前記ＧＨからの前記ハートビートメッセージを受信するステップと、
前記ＬＰＧ内の各ＧＮにおいて、タイマを前記ハートビート周期よりも大きな値にランダムに設定するとともに次のハートビートメッセージを待つステップと、
ハートビートメッセージが受信されないときに前記タイマの時間を減らしていくステップと
をさらに含み、
次のハートビートメッセージを受信する前に前記タイマが満了する場合には、最初にタイマが満了した前記ＧＮが自らのハートビートメッセージを送信して、新たなＧＨとして動作し、該ハートビートメッセージを送信する最初のＧＮが、前記ＬＰＧの前記新たなＧＨになる、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１０】
前記グループメンバーシップメッセージは前記ハートビートメッセージに含まれ、前記一定のインターバルで送信される、
請求項７に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１１】
前記ＬＰＧに対して少なくとも１つのゲートウエイノードを選択するステップをさらに
含み、該少なくとも１つのゲートウエイノードは、複数のメッセージを前記ＧＮから前記ＧＨに中継する機能を果たす、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１２】
前記少なくとも１つのゲートウエイノードは、前記ＧＮから受信される複数のステータスメッセージを収集し、該複数のステータスメッセージをメモリに格納し、所定の時間が経過した後に、前記ＧＨに対して、該複数のステータスメッセージの集合を含む１つのメッセージを送信する、
請求項１１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１３】
少なくとも１つの二次ＧＨを選択するステップをさらに含み、
前記ＧＨが前記ＬＰＧから出る場合に、該少なくとも１つの二次ＧＨが該ＬＰＧの新たなＧＨになる、
請求項１に記載の複数の移動ノード間にアドホック無線ネットワークを確立及び維持する方法。
【請求項１４】
アドホック無線ネットワークシステムであって、
順序づけされない複数の移動無線デバイスから動的に形成される、少なくとも１つのローカルピアグループ（ＬＰＧ）を含み、該ＬＰＧは、
前記複数の移動無線デバイスから選択され、一意のグループヘッダ識別情報を割り当てられるグループヘッダノード（ＧＨ）であって、ハートビートメッセージを含む複数の制御メッセージを一定のインターバルで送信することによって、前記ＬＰＧを制御及び管理する、グループヘッダノード（ＧＨ）と、
前記少なくとも１つのＬＰＧにおいて、所定の閾値に達していないときに、前記ＧＨの無線範囲内の前記複数の移動無線デバイスのうちの残りの移動無線デバイスから生成される少なくとも１つのグループノード（ＧＮ）と
を備え、
前記少なくとも１つのＧＮは、該少なくとも１つのＧＮと前記ＧＨとの間に形成されるネットワークリンクを介して前記ＧＨと通信することができ、また、該ＧＮについての情報を含むステータスメッセージを前記ＧＨに送信する、アドホック無線ネットワークシステム。
【請求項１５】
前記複数の移動無線デバイスのうちの前記残りの移動無線デバイスから選択される少なくとも１つのゲートウエイノードをさらに備え、
該少なくとも１つのゲートウエイノードは、複数のメッセージを前記少なくとも１つのＧＮから前記ＧＨに中継する機能を果たし、
該複数のメッセージは、前記少なくとも１つのＧＮから前記ＧＨへのステータスメッセージを含み、
前記少なくとも１つのゲートウエイノードは、前記少なくとも１つのＧＮから受信される前記ステータスメッセージを収集し、該ステータスメッセージを格納し、所定の時間が経過した後に、該所定の時間中に該少なくとも１つのゲートウエイノードによって受信される全ての該ステータスメッセージの集合を含む１つの集合ステータスメッセージを前記ＧＨに対して送信する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１６】
前記移動無線デバイスは、メモリセクションと、タイマと、制御手段と、送受信セクションと、ハートビート生成手段とを備え、
前記ハートビート生成手段は、前記一定のインターバルでハートビートメッセージを生
成し、
該ハートビートメッセージは、ＬＰＧ識別番号、ＧＨ識別情報、前記ＬＰＧのノードの数、該ＬＰＧにおいて許可されるノードの最大数、ホップカウント、最大ホップ及び次のハートビートメッセージの時刻を含み、
前記移動無線デバイスが前記ＧＨとして選択されるとき、前記一定のインターバルは前記タイマによってカウントされ、
該タイマが満了するとき、前記ハートビート発生セクションは、前記メモリセクションに格納されている情報に基づいて、前記ハートビートメッセージを送信し、
前記制御セクションは、所定の値と少なくとも１つのパラメータとを比較することによる前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの１つが前記ＬＰＧに参加できるか否かの判定を含む、前記ＧＨの制御を行い、
前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの前記１つが前記ＬＰＧに参加できるものと判定される場合には、前記制御セクションは、前記送信受信セクションに、ＧＮ受諾メッセージを送信するように指示し、一方、該制御セクションが、前記複数の移動デバイスのうちの前記残りの移動無線デバイスのうちの前記１つが参加できないものと判定する場合には、該制御手段は、該送受信セクションに、ＧＮ拒否メッセージを送信するように指示する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１７】
前記残りの複数の移動無線デバイスがＧＮとして選択されるとき、該ノードは、メモリ手段と、タイマと、制御セクションと、送受信セクションとを備え、
前記送受信セクションは、前記ＧＨに対して一定のインターバルでステータスメッセージを送信し、
前記一定のインターバルは前記タイマによってカウントされ、
該タイマが満了するとき、前記送受信セクションは、前記メモリ手段に格納されている情報に基づいて、前記ステータスメッセージを送信し、
また前記タイマは前記ハートビート周期よりも長いランダムな時間に設定され、
前記送受信セクションが前記ハートビートメッセージを受信すると、前記タイマは別のハートビートメッセージを受信するためにリセットされ、
該タイマが満了する前に、該送受信セクションがハートビートメッセージを受信しない場合には、前記制御手段は、該送受信セクションに、前記メモリ手段に格納されている、前記ＬＰＧに関する情報を含む自らのハートビートメッセージを送信し、該ＬＰＧの新たなＧＨとして動作するように指示する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１８】
前記ＬＰＧ内に２つ以上のＧＨが存在する場合には、該２つ以上のＧＨは、互いに対してヘッダ解決メッセージを送信し、ヘッダ解決モードに入って、所定の選択判定基準に基づいて、前記ＬＰＧの前記ＧＨとして１つのＧＨを選択し、１つのＧＨが選択された後に、該１つのＧＨは、前記ＬＰＧ内の他の全てのＧＮに対してＧＨ選択メッセージを送信し、その後、前記ハートビートメッセージを送信し、前記２つ以上のＧＨの他のＧＨは、前記新たなＧＨを介して、前記ＬＰＧに参加する、
請求項１４に記載のアドホック無線ネットワーク。
【請求項１９】
前記残りの複数の移動無線デバイスが前記ハートビートメッセージを受信するとき、該残りの複数の移動無線デバイスは、前記ＧＨに対してＬＰＧ参加メッセージを送信するか否かを判定し、
該判定は、少なくとも１つのパラメータを所定の閾値と比較することに基づき、
該少なくとも１つのパラメータが前記所定の閾値を超えないものと判定される場合には、前記残りの複数の移動無線デバイスは、前記ＬＰＧ参加メッセージを送信し、該少なくとも１つのパラメータが前記所定の閾値を超える場合には、前記ＬＰＧ参加メッセージを
送信しない、
請求項１４に記載のアドホック無線ネットワーク。
【請求項２０】
複数の移動ノード間にアドホック無線ネットワークを確立及び維持するためのアドホックネットワークであって、該複数の移動デバイスは、該複数の移動ノードを順序付けすることなく、動的に形成されるローカルピアグループ（ＬＰＧ）に分割され、該ネットワークはコンピュータ読取り可能記憶媒体上に与えられるコンピュータ読取り可能プログラムコードを実行するためのプロセッサを備え、該コンピュータ読取り可能プログラムコードは命令を有し、該命令によって、該プロセッサは、
前記複数の移動ノードから、一意のグループヘッダ識別情報を割り当てられるとともに前記ＬＰＧを制御及び管理する、前記ＬＰＧのグループヘッダノード（ＧＨ）を選択するステップと、
前記選択されたＧＨから、ハートビートメッセージを含む複数の制御メッセージを一定のインターバルで送信するステップと、
前記複数の移動ノードのうちの他のノードが前記ＬＰＧに参加することができるか否かを、所定の閾値に基づいて判定するステップと、
前記複数の移動ノードのうちの前記他のノードがグループノード（ＧＮ）として前記ＬＰＧに参加することができるものと判定される場合には、該複数の移動ノードのうちの前記他のノード間にネットワークリンクを構築するステップと
を実行する、複数の移動ノード間にアドホック無線ネットワークを確立及び維持するためのアドホックネットワーク。
【請求項２１】
前記複数の無線デバイスは少なくとも１つの車両である、請求項１４に記載のアドホック無線ネットワーク。
【請求項２２】
前記複数の無線デバイスは、車両に接続されるか、又は内蔵される少なくとも１つの無線デバイスである、請求項１４に記載のアドホック無線ネットワーク。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７】
【図８】
【図９】
【図２Ａ】
【図２Ｂ】
【図３】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７】
【図８】
【図９】
【公表番号】特表２００９−５１６９５７（Ｐ２００９−５１６９５７Ａ）
【公表日】平成２１年４月２３日（２００９．４．２３）
【国際特許分類】
【出願番号】特願２００８−５４１１９２（Ｐ２００８−５４１１９２）
【出願日】平成１８年１０月２７日（２００６．１０．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０４２１３６
【国際公開番号】ＷＯ２００７／０６１５７３
【国際公開日】平成１９年５月３１日（２００７．５．３１）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【Ｆターム（参考）】
【公表日】平成２１年４月２３日（２００９．４．２３）
【国際特許分類】
【出願日】平成１８年１０月２７日（２００６．１０．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０４２１３６
【国際公開番号】ＷＯ２００７／０６１５７３
【国際公開日】平成１９年５月３１日（２００７．５．３１）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【Ｆターム（参考）】
[ Back to top ]