リンクされた等価セルヘッダに基づいてアドホックネットワークを組織する手法およびプロトコル
移動アドホックネットワークを確立および維持することが提供される。アドホックネットワークは、リンクされた等価セルネットワークを形成する互いに通信可能にリンクされる複数の等価セルを含む。等価セルヘッダが各等価セルを管理する。さらに、等価セルネットワーク全体にわたって散在するレギュラーノードも設けることができる。レギュラーノードは、等価セルヘッダに比べて、通信特権に制約がある。しかしながら、等価セルネットワークによって要求されるのに応じて、等価セルヘッダをレギュラーノードに降格させ、レギュラーノードを等価セルヘッダに昇格させることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、ほぼ瞬時に通信を行うために、移動デバイス間にアドホック無線ネットワークを確立するとともに維持することに関する。
【０００２】
［関連出願の相互参照］
本願は、米国特許法第１１９条に基づいて、２００５年１１月２２日にWai Chen他によって出願された“Linked Equivalent Cell Header-based Approach and Protocol for organizing an Ad-Hoc Network”と題する米国特許出願第１１／２８４，７３１号からの優先権を主張し、また２００５年１１月２２日にShengwei Cai他によって出願された“Group-Header Based Method to Organize Local Peer Group of Vehicles for Inter-Vehicle
Communication”と題する米国特許出願第１１／２８５，５９３号に関連し、それらの特許出願はそれぞれ参照により本明細書に援用される。
【背景技術】
【０００３】
［発明の背景］
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーンまたはホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、および、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【０００４】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路および高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【０００５】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが差し迫った状況に陥る前に、必要な措置を講じることができるようになる。この特徴が、交通事故および交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更または合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【０００６】
車両安全通信（「ＶＳＣ」）は、車車間通信とインフラストラクチャを介した車両通信とに大きく分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【０００７】
重要なＶＳＣ性能要件には、衝突回避のような種々のＶＳＣアプリケーションを支援するために、遅延時間が短いこと（約１００ミリ秒）、およびスループットを維持すること（別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ）が含まれる。
【０００８】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【０００９】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【００１０】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい（すなわち、どの車両も、あらかじめその近くにいる車両について何も知らない）。車両間安全通信を構築するために必要とされる全ての情報を車両間で概ねリアルタイムに交換しなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行えるようにする必要がある。協調しない車両の移動度が高いと、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ（移動度、アドレス、名前、メディアセッションのための）を用いることが難しいことを示す。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【００１１】
ホットスポットのような他の場所で利用されるＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【００１２】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【００１３】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔおよびＣａｒＴａｌｋ２０００はいずれも、車車間通信ネットワーク
を構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノードおよび移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費および間接費が生じる。さらに、ＦｌｅｅｔＮｅｔシステムは、位置に基づくルーティングおよび位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【００１４】
ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車車間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。さらに、ＣａｒＴａｌｋ２０００は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【００１５】
ＣａｒＴａｌｋ２０００システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【００１６】
しかしながら、これらのＧＰＳネットワークは大きな欠点を有する。移動度の高い車両環境では、ＧＰＳ情報はすぐに有効でなくなる。ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなＧＰＳ位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【００１７】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
［発明の概要］
本発明の目的は、複数の移動デバイスをグループ化して、ローカルピアグループ（「ＬＰＧ」）のような１つの管理グループにし、メッセージ伝送を連携および中継し、メッセージ伝搬の範囲および方向を制御することによって、移動デバイス間通信に適した通信境界を創出することである。
【００１９】
さらに、本発明の目的は、ローカルピアグループを確立するための簡単なプロトコル、およびグループ内とグループ間の両方においてノード間でデータを伝送するためのプロトコルを提供することである。
【００２０】
さらに、本発明の目的は、ネットワークの少なくともいくつかのメンバが、ネットワークの他のメンバに対する、ネットワーク内での位置を認識する順序付きネットワークを提供することである。
【課題を解決するための手段】
【００２１】
したがって、本発明により、複数の移動無線デバイス間に移動アドホックネットワークを確立および維持する方法が提供される。本方法は、複数の移動無線デバイスのうちの第１のデバイスを第１の等価セルヘッダ（ＥＣＨ）として動作させるステップを含む。この第１のＥＣＨは、第１の等価セル（ＥＣ）を確立する。この第１のＥＣは第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつエリアの一部を占めるような大きさで形成される。ＥＣはＥＣＨによって管理される。
【００２２】
さらに、第１のＥＣＨからＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）メッセージを送信するステップが提供される。ＥＣＨ＿ＨＥＬＬＯメッセージは、複数の移動無線デバイスのうちの１つのデバイスが第１のＥＣＨであることを通知する。ＥＣＨ＿ＨＥＬＬＯメッセージ送信は、各ＥＣＨが他のＥＣＨとは異なる間隔を有するようにランダムに定められた一定の間隔で行われる。
【００２３】
さらに別のステップは、少なくとも第２のＥＣＨとして動作している少なくとも第２の移動無線デバイスから送信される少なくとも第２のＥＣＨ＿ＨＥＬＬＯメッセージを第１の無線デバイスによって受信すること、および、第２のＥＣＨが受信された唯一の他のＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、第１のＥＣＨノードと第２のＥＣＨノードとの間にリンクされた等価セルネットワークを形成することを提供する。しかしながら、受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、第１のデバイスは、リンクされた等価セルネットワーク内のレギュラーノードとして動作する。レギュラーノードは、リンクされた等価セルネットワークの一部であるが、ＥＣＨと比べて通信特権に制約がある。
【００２４】
さらに、等価セルネットワークに属するＥＣＨの移動度を検出するステップと、所定の選択判定基準に基づいて新たなＥＣＨを選択するステップとが提供される。ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行される。そのレギュラーノードは、移動度を検出されたＥＣＨによって管理される等価セルに対するそのレギュラーノードの位置に基づいて選択される。移動度は、新たなＥＣＨがＥＣネットワークに参加すること、リンクされたＥＣＨがＥＣネットワークを出ること、および、リンクされたＥＣＨが同じＥＣネットワークの別のＥＣＨによって管理されるＥＣ内に移動することを含む。
【００２５】
複数の移動デバイス間にモバイルアドホックネットワークを確立するシステムも提供される。そのシステムは、複数の移動無線デバイスのうちの第１のデバイスを第１の等価セルヘッダ（ＥＣＨ）として動作させる手段を含む。第１のＥＣＨは第１の等価セル（ＥＣ）を確立する。第１のＥＣは、第１のＥＣＨの無線通信範囲のエリア内に中心があり、そのエリアの一部を占めるような大きさで形成される。ＥＣはＥＣＨによって管理される。
【００２６】
さらに、第１のＥＣＨからＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）メッセージを送信する手段が提供される。ＥＣＨ＿ＨＥＬＬＯメッセージは、複数の移動無線デバイスのうちの１つのデバイスが第１のＥＣＨであることを通知する。ＥＣＨ＿ＨＥＬＬＯメッセージ送信は、各ＥＣＨが他のＥＣＨノードとは異なる間隔を有するようにランダムに定められた一定の間隔で行われる。
【００２７】
さらに別の手段は、少なくとも第２のＥＣＨとして動作している少なくとも第２の移動無線デバイスから送信される少なくとも第２のＥＣＨ＿ＨＥＬＬＯメッセージを第１の無線デバイスによって受信すること、および、第２のＥＣＨが受信された唯一の他のＥＣＨ
＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、第１のＥＣＨノードと第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成することを提供する。しかしながら、２つ以上の受信されたＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、第１のデバイスは、リンクされた等価セルネットワーク内のレギュラーノードとして動作する。レギュラーノードは、リンクされた等価セルネットワークの一部であるが、ＥＣＨに比べると通信特権に制約がある。
【００２８】
さらに、等価セルネットワークに属するＥＣＨの移動度を検出する手段と、所定の選択判定基準に基づいて新たなＥＣＨを選択するための手段が提供される。
【００２９】
本発明のこれらの、さらには別の特徴、態様および利点は、以下に記述される詳細な説明、添付の特許請求の範囲および添付の図面との関連で、さらに深く理解されるようになるであろう。
【発明を実施するための最良の形態】
【００３０】
［発明の詳細な説明］
本発明によれば、複数のノードすなわち移動デバイスが管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて構築される。このグループ化すなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ内や複数のＬＰＧ間でのルーティングの基礎および本発明によるアドホック無線ネットワーク内における伝送の組織化の基礎となり、限定はしないが、車両安全や情報アプリケーションを含む、無線通信を支援する。
【００３１】
ＬＰＧの目的は、近くにあるノード間での種々の程度の連携を確立することである。これら近くにあるノードは、無線通信の能力を備える移動デバイスである。移動デバイスの実施形態は、車両内に設置されたり車両内に個別に持ち込まれたりする通信デバイスを備える車両や、通信デバイスを携帯した歩行者を含む。好ましい実施形態は、固有の通信デバイスを備える移動車両である。しかしながら、携帯電話、ＰＤＡ、ノートパソコン等を含む他の通信デバイスも本発明の一部として用いることができ、唯一の必要条件は、その通信デバイスが、開示される実施形態の適当な動作のために必要な無線通信プロトコルに対応していることである。
【００３２】
連携の程度には、２つのタイプがある。第１のタイプは直ぐ近くにある移動デバイスの密な連携であり、概ね瞬時のメッセージ伝送の支援に利用されるＬＰＧ内通信のために用いられる。たとえば、緊急道路障害物警告や他のタイプの緊急メッセージまたは安全メッセージの送信は、ＬＰＧ内メッセージ伝送を用いて実行される。これらのメッセージでは、遅延が通常約１００ｍｓ以下であることが要求される。
【００３３】
第２のタイプは、近くにある移動デバイスの疎な連携である。このタイプの連携は、リンクまたは相互接続されているＬＰＧの間のＬＰＧ間通信を支援するために用いられる。たとえば、ＬＰＧ間通信は、道路認識アプリケーションや、ドライバの視界拡張のために用いることができる。
【００３４】
ＬＰＧは、直ぐ近くにある複数のノードから動的に形成される。具体的には、第１のノードが無線信号を送信し、第１のノードの範囲内にある他のノードが、その無線信号を受信する能力を有する。ＬＰＧは無線通信エリアに基づいて形成されるので、ＬＰＧ内のノードは、固定インフラストラクチャなしに、シングルホップまたはマルチホップで互いに通信することができる。
【００３５】
［用語集］
さらに説明を続ける前に、本開示を通して共通に用いられるいくつかの重要な用語を定義する必要がある。
【００３６】
用語「等価セル（equivalent cell）」（ＥＣとも呼ばれる）は、無線通信エリアの一
部を指している。ＥＣは、等価セルネットワークの基本編成構造を形成する。
【００３７】
用語「等価セルヘッダ（equivalent cell header）」（ＥＣＨとも呼ばれる）は、等価セルを定義、維持および管理するノードを指している。ＥＣＨはリンクされていなくても、リンクされていてもよい。リンクされたＥＣネットワークでは、メンバＥＣＨノードが、ネットワーク内通信バックボーンを提供する。ネットワーク内の全てのメッセージは、宛先に到着するまで、ＥＣＨ間で送信される。
【００３８】
用語「レギュラーノード（regular nodes）」は、リンクされたＥＣネットワークのメ
ンバノードを指す。レギュラーノードは、ネットワーク内での通信特権に制約がある。レギュラーノードは、ある特定の状況下において、ＥＣＨになることができる。レギュラーノードとＥＣＨとの違いは機能的な違いだけである。構造的には、いずれのノードタイプも同じであるものの、特定の機能が、特定の時点におけるノードタイプに応じて、その時点で実行できたり実行できなかったりする。
【００３９】
用語「リンクされた（linked）」は、２つ以上のＥＣＨがシングルホップまたはマルチホップで互いに無線通信していることを指している。リンクされたＥＣＨ（またはリンクされたＥＣ）ネットワークは、ＥＣＨノードに関連付けられた、シングルホップの通信範囲内にあるレギュラーノードを含むことができる。
【００４０】
用語「リンクされていない（unlinked）」は、ＥＣＨが他のＥＣＨと無線通信していないことを指している。リンクされていないＥＣＨは、自ネットワークの唯一のメンバＥＣＨであり、関連付けられるレギュラーノードを持たない。
【００４１】
用語「ｋのリンク度（linked degree of k）」は、２つのＥＣＨをリンクする無線ホップの数ｋを指している。たとえば、ＥＣＨ ＡとＥＣＨ Ｂが直にリンクされる場合には、リンク度は１（すなわちｋ＝１）である。しかしながら、ＥＣＨ ＡとＥＣＨ Ｂが互いを検出することができ、かつＥＣＨ ＢとＥＣＨＣが互いを検出することができるが、ＥＣＨ ＡとＥＣＨ Ｃが互いを検出できない場合には、ＥＣＨ ＡとＥＣＨ Ｃとの間のリンク度は２（すなわちｋ＝２）である。
【００４２】
用語「区別されたＥＣＨノード（distinct ECH nodes）」は、同じ等価セルネットワークのメンバでないＥＣＨノードを指している。区別されたＥＣＨノードは、リンクされていないＥＣＨノードであっても、リンクされたＥＣＨノードであってもよいが、異なる等価セルネットワークに属している。
【００４３】
用語「移動度（mobility）」は、リンクされたＥＣネットワークに対するＥＣＨの動きを指している。より具体的には、移動度は、リンクされたＥＣネットワークに入るＥＣＨの動き、メンバであるリンクされたＥＣネットワークから出るＥＣＨの動き、またはあるＥＣから別のＥＣＨによって管理される別のＥＣに移るＥＣＨの動きを指している。
【００４４】
［リンクされたＥＣネットワークの形成］
図１を参照すると、本発明は、動的かつ自己組織的なローカルピアグループ、すなわちリンクされた等価セルネットワーク１００を提供する。リンクされた等価セルネットワーク（Ｌ＿ＥＣ）１００の基本構成ブロックは、等価セルヘッダ（ＥＣＨ）１０４ａを中心
にした等価セル（ＥＣ）１０２ａである。複数のＥＣ１０２ａ、１０２ｂ、１０２ｃが無線で互いにリンクし、Ｌ＿ＥＣ１００を形成する。これ以降、ＥＣ１０２ａ、１０２ｂおよび１０２ｃをまとめて符号１０２によって参照し、ＥＣＨノード１０４ａ、１０４ｂおよび１０４ｃをまとめて符号１０４によって参照する。
【００４５】
ＥＣＨ１０４ａは、ＰＤＡ、ノートパソコンまたは車両搭載コンピューティングデバイスのような、移動無線ネットワーキングデバイスである。ＥＣＨ１０４ａは、外側に向かって全方向に広がる無線通信エリア１０８を有する無線送受信機を備えている。図１に示されるように、無線通信エリア１０８は、定義されるＥＣ１０２ａのエリアよりもかなり大きい。図１は、３つのＥＣノード１０２ａ、１０２ｂおよび１０２ｃを含む無線通信エリア１０８を示すが、これは例示にすぎず、唯一の構成と解釈されることを意図していないことに留意されたい。具体的には、定められた無線通信エリア内に、任意の数のＥＣ１０２が存在するようにすることができる。しかしながら、本発明の説明を簡単にするために、ＥＣＨノードの無線通信エリア１０８は、これ以降、３つのＥＣノード１０２を含む。
【００４６】
ＥＣＨノード１０４は、Ｌ＿ＥＣ１００のネットワーキングバックボーンを提供する。具体的には、全てのＥＣ間通信および制御データ送信は、ＥＣＨノード１０４によって実行される。さらに、ＥＣＨノード１０４ａは、割り当てられたＥＣ１０２ａの動作パラメータを管理する。そのような動作パラメータは、メンバすなわちＥＣＨノード１０４ｂのＥＣ１０２ｂ内に位置するレギュラーノード１０６を追跡すること、ＥＣノード１０４ｂと通信している他のＥＣＨノード１０４ａ、１０４ｃのリストを維持すること、およびＬ＿ＥＣ１００内でのその相対的な位置を含む。レギュラーノード１０６は、ＥＣ１０２内に配置される移動無線ネットワークデバイスである。任意の移動無線デバイスは、ＥＣＨ１０４として、またはレギュラーノード１０６として動作することができる。
【００４７】
図２を参照しながら、これ以降、アドホックネットワークの初期化および統合について説明する。ノード２０２、すなわち移動無線デバイスが、最初に、ＥＣＨとして動作し、自身が唯一のメンバであるリンクされていないＥＣ２０４を確立する。ＥＣＨ２０２は、第２のＥＣＨ２０６からの送信を検出すると、ＥＣＨ＿ＨＥＬＬＯメッセージで応答し、第２のＥＣＨ２０６に識別情報を与える。検出された他のＥＣＨがＥＣＨ２０６だけである場合には、その結果として、ＥＣＨ２０２およびＥＣＨ２０６を含むリンクされたＥＣ２１０になる。したがって、これら２つのＥＣＨ２０２および２０６は、ＥＣ２０４およびＥＣ２０８を含むネットワークを形成する、すなわち既に確立されているネットワークを拡張する。さらに、２つ以上のリンクされていないＥＣＨノードを検出するリンクされていないＥＣＨは、その２つ以上のリンクされていないＥＣＨノードとネットワークを形成し、全ての検出されたＥＣＨノードを含むリンクされたＥＣが構成される。
【００４８】
リンクされたＥＣ２１０にさらに別のリンクされていないＥＣＨノードが出合うと、そのノードは、さらなるリンクされたＥＣＨまたはレギュラーノードのいずれかとして、増大しているリンクされたＥＣに組み込まれる。具体的には、リンクされていないＥＣＨノードが、互いにリンクされている２つのＥＣＨノードを検出すると、レギュラーノードになる。たとえば、図３では、リンクされていないＥＣＨ３０２ａは、レギュラーノード３０２ｂになる。これらの移動無線デバイスは、レギュラーノードとして、全Ｌ＿ＥＣ１００内でメッセージを送受信することができる。しかしながら、全てのメッセージはＥＣＨノード２０２および２０６を通してルーティングされ、レギュラーノード間で直にはルーティングされない。このようにして、帯域幅が節約される。
【００４９】
別の方法では、図４に示されるように、リンクされていないＥＣＨノード４０２ａが他のＥＣＨ２０２を１つのみ検出する場合は、Ｌ＿ＥＣの一部であってもなくても、検出さ
れたＥＣＨ２０２にリンクし、リンクされたＥＣ４０４の長さを拡張してリンクされたＥＣＨ４０２ｂになるであろう。
【００５０】
レギュラーノードがただ１つのＥＣＨを検出する場合は、そのレギュラーノードはＥＣＨになり、そして、検出されたＥＣＨにリンクしてリンクされたＥＣネットワークを形成する。さらに、レギュラーノードまたはリンクされていないＥＣＨは、自ノードが「リンカー」であると検出した場合には、リンクされたＥＣＨになる。
【００５１】
リンカーは、複数の区別されたＥＣＨを検出するノード（レギュラーまたはＥＣＨ）である。ここで、検出されたＥＣＨノードは同じＥＣネットワークのメンバではない。これらの区別されたＥＣＨノードは、リンクされていないＥＣＨノード、異なるネットワークに属するリンクされたＥＣＨノード、またはその両方の組み合わせであり得る。
【００５２】
レギュラーノードが自ノードをリンカーであると認識するとき、レギュラーノードは新たなＥＣＨになり、これら複数の区別されたＥＣＨを接続して、より大きな１つのネットワークを形成する。レギュラーノードは、あるＥＣＨノードがネットワークの一部であるか否かを、そのＥＣＨノードが属するリンクされたＥＣネットワークのメンバＥＣＨノードのリスト（本明細書において、ＬＥＣＨリストと呼ばれる）を受信することによって検出する。ＬＥＣＨリストはＥＣＨメッセージに含まれる。レギュラーノードは、複数の区別されたＥＣＨノードのＬＥＣＨリストをそれぞれ比較することによって、自ノードが「リンカー」であるか判定する。
【００５３】
区別されたＥＣＨノードによって送信されるＥＣＨメッセージは、それらのリスト間で共有されるＥＣＨノードを持たない。すなわち、両方のリストにのるＥＣＨは存在しない。リンクされていないＥＣＨノードはそのネットワーク内の唯一のＥＣＨであるので、そのＬＥＣＨリストは自ノードへの参照だけを含む。図５の例では、リンクされていないＥＣＨ５００は、３つのリンクされているＥＣＨ５０１〜５０３からそれぞれＥＣＨ＿ＨＥＬＬＯメッセージを受信する。ＥＣＨ５０１はＥＣＨ５０６とリンクしてリンクされたＥＣ５０５を形成し、ＥＣＨ５０２はＥＣＨ５０７とリンクしてリンクされたＥＣ５１０を形成し、ＥＣＨ５０３はＥＣＨ５０８とリンクしてリンクされたＥＣ５１５を形成する。３つのＥＣＨ＿ＨＥＬＬＯメッセージを受信すると、リンクされていないＥＣＨ５００は、２つ以上のＥＣＨリスト内に共通に列挙されるＥＣＨがあるか否かを判定する。この事例では、３つのリンクされるＥＣＨリストは共通のメンバを持たない。したがって、リンクされていないＥＣＨ５００は、自ノードが「リンカー」ノードであると判定し、これら３つの離ればなれの区別されたリンクＥＣ５０５、５１０および５１５全てを１つにリンクし、１つのリンクされたネットワーク５２０を形成する。レギュラーノードも、そのノードが「リンカー」ノードであるか否かを判定するために、同様の評価を実行する。
【００５４】
リンクされたＥＣは、ＥＣＨ＿ＨＥＬＬＯメッセージにおいて送信される制御メッセージを介して維持される。ＥＣＨ＿ＨＥＬＬＯメッセージは、あらかじめ定義された間隔で、各ＥＣＨによって送信される。レギュラーノードはＥＣＨ＿ＨＥＬＬＯメッセージを受信するだけで、応答はしない。レギュラーノードまたはリンクされたＥＣＨノードがＥＣＨ＿ＨＥＬＬＯメッセージを受信するのに失敗すると、そのノードはリンクされていないＥＣＨになる。
【００５５】
ＥＣＨ＿ＨＥＬＬＯメッセージは、メッセージの発信元のＩＤと、発信元によって送信される現在のメッセージの番号を特定するシーケンス番号と、Ｌ＿ＥＣの第１の通信経路に沿って発信元が認識できるＥＣＨノードの第１のリスト（ＬＥＣＨリスト）と、Ｌ＿ＥＣの第２の通信経路に対する第２のＬＥＣＨリストとを含むことが好ましい。付加的なＬＥＣＨリストを提供してもよく、その場合、各ＬＥＣＨリストは、発信元ＥＣＨを中心と
したＬ＿ＥＣの１つのブランチ、すなわち通信経路、に沿って出合う全てのＥＣＨノードのＥＣＨ ＩＤを含む。さらに、ＥＣＨ＿ＨＥＬＬＯメッセージは、タイムアウト値を含むこともできる。タイムアウト値は、現在のＥＣＨ＿ＨＥＬＬＯメッセージの受信と次のＥＣＨ＿ＨＥＬＬＯメッセージの受信との間の最長経過時間を他のＥＣＨノードおよびレギュラーノードに通知するものであり、それにより、特定のＥＣＨがリンクされたＥＣネットワーク内に依然として存在するか否かを判定するための手段を提供する。
【００５６】
各Ｌ＿ＥＣは、ＬＰＧ＿ＩＤによって識別される。リンクされたＥＣＨノードのグループがＬ＿ＥＣを形成し、その際、ＬＰＧ＿ＩＤを割り当てられる。Ｌ＿ＥＣ内のリンクされるＥＣＨの数は、動作性能やネットワーク内の移動デバイス（すなわち、ノード）の台数または分布のような環境条件を考慮して柔軟に定義することができる。ＥＣＨ＿ＨＥＬＬＯメッセージを通して、ＬＰＧ＿ＩＤがメンバＥＣＨノードおよびレギュラーノードに通知される。このようにして、レギュラーノードは、現在どのＬ＿ＥＣに属しているかがわかる。
【００５７】
ＬＰＧ＿ＩＤは、個々のＬ＿ＥＣに割り当てられ、そのＬ＿ＥＣを識別する一意の識別子である。したがって、ＬＰＧ＿ＩＤは、メンバＥＣＨノードのＩＤや他の識別情報の組み合わせのような、個々のＬ＿ＥＣに固有な特性に基づいて作成することができる。また、ＬＰＧ＿ＩＤは、ランダムに生成されたコードであってもよい。そのような事例では、コードを形成するビット数または文字の数が、ＬＰＧ＿ＩＤの固有性を決定する。コード長が長くなるほど、短いコード長よりもランダムに繰り返される可能性が小さくなる。
【００５８】
［移動度検出およびＥＣＨ選択］
本明細書において定義される移動度検出は、リンクされたＥＣに出入りするＥＣＨの動き、および別のＥＣ内に入るＥＣＨの動きを検出することを指している。レギュラーノードの動きはリンクされたＥＣネットワークの動作に影響を及ぼさないが、ＥＣＨノードが動く結果として、リンクされたＥＣネットワークの動作が非効率的になったり、またはリンクされたＥＣネットワークが崩壊したりする可能性がある。移動によって、ＥＣＨノードが重複するＥＣを有する可能性がある。その結果、あまりにも近くでメッセージが再送されることに起因して、ネットワークのそのエリアにおけるデータ伝送が非効率的になり、所定の長さのネットワークを伝搬するのにより長い時間がかかるようになる。それとは別に、移動は反対の影響を及ぼす可能性もあり、ＥＣＨノードの動きによって、２つのＥＣＨノードの無線通信範囲間に隙間が形成され、その隙間を越えてメッセージが伝搬できないので、基本的には、その結果として、その場所においてリンクされたＥＣネットワークが崩壊する。
【００５９】
リンクされたＥＣネットワーク内の移動度を補正するために、移動度検出が必要とされる。移動度検出は、受動的または能動的に実行することができる。受動的な移動度検出法では、ＥＣＨ＿ＨＥＬＬＯメッセージを用いて、ノードの移動度を検出する。具体的には、この方法では、ＥＣＨがネットワークから外れたことをその周囲にあるＥＣＨノードまたはレギュラーノードが検出するためには、あらかじめ設定された時間が経過することが必要である。
【００６０】
全てのＥＣＨは自らのタイマーに基づいて動作し、各ＥＣＨはＴ秒毎にＥＣＨ＿ＨＥＬＬＯメッセージを送信する。時間Ｔの間に、各ＥＣＨは（およびレギュラーノードも）、近くにあるＥＣＨノードからＥＣＨ＿ＨＥＬＬＯメッセージを収集する。収集されたメッセージに基づいて、ＥＣＨは自身のＬＥＣＨリストおよび送信するＥＣＨ＿ＨＥＬＬＯメッセージを更新する。更新されたＥＣＨノードリストを維持するために、あるＥＣＨからＥＣＨ＿ＨＥＬＬＯメッセージを受信せずに所定の時間が経過すると、ＥＣＨリストからそのＥＣＨを自動的に削除する。有効期限または所定の時間は、Ｔよりも長くなければな
らず、たとえば３Ｔである。この検出の速さは完全に、ＥＣＨ＿ＨＥＬＬＯの時間Ｔによって決まる。あるＥＣＨからＥＣＨ＿ＨＥＬＬＯメッセージが受信されると、タイマーはリセットまたはリスタートされる。タイマーを用いて、ＥＣＨリスト内の全てのＥＣＨについてのＥＣＨ＿ＨＥＬＬＯメッセージを追跡する。
【００６１】
しかしながら、そのリストは、所定の時間が経過した後にはじめて更新される。すなわち、リンクされたＥＣネットワーク内にもはや存在しない古いＥＣＨが削除される。したがって、あるＥＣＨが送信範囲から既に移動しているが、それでもＥＣＨリスト内に列挙されている可能性がある。この受動的な方法では、結果として、メッセージ転送が途切れる可能性があり、Ｌ＿ＥＣネットワークの性能に影響を及ぼす。したがって、能動的な移動度検出法を用いて、ＥＣＨ移動度のより迅速な検出および解決を提供することができる。
【００６２】
能動的な移動度検出では、ＥＣＨ＿ＨＥＬＬＯメッセージと組み合わせて、新たな制御メッセージＭ＿ＤＥＴＥＣＴが用いられる。これにより、短い時間、すなわちＴよりも短い時間で移動度を検出することができる。Ｍ＿ＤＥＴＥＣＴメッセージは、発信者のＩＤと、移動した可能性のあるＥＣＨ（ｍＥＣＨ）、すなわち、その元の位置から離れているかまたはリンクされたＥＣネットワークから出ているＥＣＨのＩＤとを含む。Ｍ＿ＤＥＴＥＣＴメッセージは、予期しないＥＣＨ＿ＨＥＬＬＯメッセージを受信したＥＣＨによって送信される。Ｍ＿ＤＥＴＥＣＴメッセージは、発信者の１ホップ範囲内にあり、かつ送信側ＥＣＨまたはｍＥＣＨのいずれかに関連付けられるＥＣＨおよびレギュラーノードの両方を対象とする。
【００６３】
図６は、能動的な移動度検出方法のためのフローチャートを示す。この方法は、ステップ６０１において、レギュラーノード（ＲＮａ）がＭ＿ＤＥＴＥＣＴメッセージを受信するときに開始する。
【００６４】
Ｍ＿ＤＥＴＥＣＴメッセージを受信すると、ステップ６０３において、そのレギュラーノードはＥＣＨ選択を開始する。レギュラーノードのＥＣＨ選択処理の第１のステップは、ステップ６０３において、タイマー（選択ランダムタイマー）をランダムな値（たとえば、０〜ｋの範囲の値、ただしｋはＴ ＨＥＬＬＯ時間未満である）に設定することである。選択ランダムタイマーをランダムな時間に設定するのは、重複して選択が呼び出されるのを避けるためである。ステップ６０５において、選択ランダムタイマーが切れる場合には、ステップ６１１において、レギュラーノードがＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹメッセージを送信し、ステップ６１３において、第２のタイマーすなわちホールドタイマー（たとえば、４／Ｔ）を設定する。その後、レギュラーノードは、ステップ６１５において、近くにいるＥＣＨノードからＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージの形で応答を受信するのを待つ。近くにいるＥＣＨは、１ホップ送信距離内にいる、すなわち中継が不要なＥＣＨである。選択ランダムタイマーが依然として動作している他のレギュラーノードは、ＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹメッセージを受信すると、その選択ランダムタイマーを直ちに停止し、レギュラーノードとしてとどまる。
【００６５】
同時に、ＥＣＨは、ＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹを受信すると、応答ランダムタイマー（たとえば、０〜ｈの範囲、ただしｈは約４／Ｔ）のようなランダムタイマーを設定する。応答ランダムタイマーが経過する間、そのＥＣＨは他のＥＣＨノードからのＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを待ち受ける。応答ランダムタイマーが切れると、そのＥＣＨは、発信者ＩＤ、クエリー発信元ＩＤ、および応答ランダムタイマーが経過する間にＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを受信することによって検出された全てのＥＣＨノードのＩＤを含む、ＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを作成し送信する。
【００６６】
ホールドタイマーが切れる時点を判定するために、ホールドタイマーは監視される。ステップ６１７においてホールドタイマーが切れると、レギュラーノードは、ＥＣＨによって送信されたＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを収集し、リンク状態を解析して、自ノードがＥＣＨになるべきか否かをステップ６１９において判定する。応答したＥＣＨノードが少なくとも２のリンク度でシリアルにリンクされているとステップ６２１において判定される場合には、ステップ６０９に進み自ノードはレギュラーノードにとどまる。応答したＥＣＨノードが１のリンク度の１つのリンクだけを形成するとステップ６２３において判定される場合には、処理はステップ６２５に進み、自ノードがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを以前に送信しているか否かを判定する。ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージは、発信者ＩＤ、および以前のクエリーにおいて検出された全てのＥＣＨのＩＤを含む。
【００６７】
そのレギュラーノードが以前にＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信していた場合には、処理はステップ６０９に進み、レギュラーノードとしてとどまる。しかしながら、そのレギュラーノードが以前にＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信していなかった場合には、収集された現在の情報に基づいては判断を下すことができないので、ステップ６２９においてＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信する。そのレギュラーノードがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信した後に、処理はステップ６１３に進む。
【００６８】
しかしながら、ステップ６２３の条件が満たされない場合には、ステップ６２７において、そのレギュラーノードは自らをＥＣＨと宣言し、新たなＥＣＨ ＩＤとして設定される発信者ＩＤと、古いＥＣＨ ＩＤとを含むＦＲＥＳＨメッセージを送信する。こうして、ＦＲＥＳＨメッセージの受信者は、古いＥＣＨ ＩＤの代わりに新しいＥＣＨ ＩＤが用いられることを通知されるので、それに応じて、ＦＲＥＳＨメッセージの各受信者は、現在のＬＥＣＨリストを更新する。
【００６９】
ステップ６２９において、ＲＮaがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを
送信する場合に、その送信メッセージに応答して実行される手順を図７に示す。ステップ７０１では、レギュラーノード（ＲＮb）が、ＲＮaによって送信されるＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを受信する。ＲＮbの近くに、このステップおよび以下に
記述される後続のステップを実行する複数のレギュラーノードが存在し得る。ステップ７０３では、ＲＮbが、ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージにおいて列挙され
るＥＣＨノードの可視性を評価する。ステップ７０５に進むと、列挙されるＥＣＨノードのいずれもＲＮbが見えない場合には、ステップ７０７に進み、ＲＮbは選択ランダムタイマーを設定する。選択ランダムタイマーが設定されたインターバル中に、ＲＮbは、ステ
ップ７０９に示されるように、新たに選択されたＥＣＨノードによって送信されるＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを受信するのを待ち受ける。ＲＮbがＥＬＥＣＴＩＯ
Ｎ＿ＲＥＰＬＹメッセージを受信する前に、ステップ７１１において選択ランダムタイマーが切れる場合には、ステップ７１３においてＲＮbは自らをＥＣＨとして宣言する。ス
テップ７１５において、新たなＥＣＨはＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを送信する。しかしながら、ＲＮbの選択ランダムタイマーが切れる前に、ステップ７０９にお
いてＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージが受信される場合には、ＲＮaはレギュラ
ーノードにとどまる。ステップ７０５に戻ると、ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹにおいて列挙される少なくとも１つのＥＣＨがＲＮbから見える場合には、ＲＮbはレギュラーノードにとどまる。
【００７０】
レギュラーノードがＥＣＨになった後に、ＦＲＥＳＨメッセージを送信することによって、そのノードはリンクされたＥＣネットワーク内の他のＥＣＨノードに、その状態変化を通知する。このメッセージによって、受信側のＥＣＨノードは、移動によって古くなっ
てしまったＬＥＣＨリストを直ちに更新する。古いＥＣＨがＦＲＥＳＨメッセージを受信すると、その古いＥＣＨは自らをレギュラーノードに降格させる。
【００７１】
好ましい実施形態では、受動的および能動的の両方の移動度検出が用いられるが、いずれかの検出方法を独立して用いることもできる。
【００７２】
種々のタイマー、たとえば選択ランダムタイマー、ホールドタイマーおよびＥＣＨ＿ＨＥＬＬＯメッセージタイマーの値はランダムにあらかじめ設定されるが、選択されるランダムな時間は、各機能の動作性能や動作の遅延要求を満足するように選択される。しかしながら、選択ランダムタイマーおよびホールドタイマーは、ＴをＥＣＨ＿ＨＥＬＬＯ周期として、１Ｔよりもはるかに小さい値を有することが好ましい。こうして、ＥＣＨ選択動作は、１Ｔ以内にＥＣＨの移動に応答する。
【００７３】
［リンクされたＥＣネットワークの融合および分離］
２つ以上のリンクされたＥＣネットワークが互いに極めて近接するとき、それらのリンクされたＥＣネットワークは互いに融合することができる。しかしながら、リンクされたＥＣネットワーク全体が他のリンクされたＥＣネットワークに「融合する」のではなく、むしろ、近くにあるＥＣＨノードが互いにリンクする。具体的には、ＥＣＨノードは、互いに近づいていくと、ＥＣＨ＿ＨＥＬＬＯメッセージを交換する。ＥＣＨ＿ＨＥＬＬＯメッセージの交換を通して、それらのＥＣＨノードは、リンクされたＥＣネットワークのＩＤ（ＬＰＧ＿ＩＤ）、メンバＥＣＨノードの識別情報、レギュラーノード、およびＬＰＧ内のＥＣＨノードの数のような、互いのリンクされたＥＣネットワークに関する情報を得るであろう。
【００７４】
融合するリンクされたＥＣネットワークの結合したサイズが、所定の最大ＬＰＧサイズよりも小さい（または等しい）場合には、融合するリンクされたＥＣネットワークは１つの大きなリンクされたＥＣネットワークを形成する。隣接したＥＣＨノードが互いにリンクされるようになり、実効的には、全てのＥＣＨを結合して１つのネットワークが形成される。しかしながら、融合するリンクされたＥＣネットワークの結合したサイズが所定の最大ＬＰＧサイズよりも大きい場合には、融合するリンクされたＥＣネットワークは、２つの新たなリンクされたＥＣネットワークを形成することになり、その新たなネットワークは、元の融合するリンクされたＥＣネットワークとは、サイズおよびメンバＥＣＨノードが異なる。ＥＣＨノードの全数が所定の最大ＬＰＧサイズを超えなければ、任意の数のリンクされたＥＣネットワークを融合することができる。
【００７５】
所定の最大ＬＰＧサイズを超える場合には、リンクされたＥＣネットワークは２つの新たなリンクされたＥＣネットワークに分離することができる。しかしながら、そのようなリンクされたＥＣネットワークの分離は比較的稀である。大体の場合には、リンクされたＥＣネットワークは、所定の最大ＬＰＧサイズよりも少ない数のＥＣＨノードを含む。リンクされたＥＣネットワークが、所定の最大ＬＰＧサイズよりも多くの数のＥＣＨノードを含む場合には、２つのリンクされたＥＣネットワークに分離することになり、分離後のネットワークの個々のサイズは最大ＬＰＧサイズよりも小さい。
【００７６】
ＥＣＨは、そのＬＥＣＨリストから、リンクされたＥＣネットワークの現在のサイズを入手することができる。ＬＥＣＨリスト内の各エントリは、ＥＣＨ＿ＩＤおよび対応するＬＰＧ＿ＩＤを含む。あるＥＣＨが、そのＬＰＧサイズが所定の最大ＬＰＧサイズよりも大きいことを検出する場合には、そのＥＣＨは、新たなＬＰＧ＿ＩＤと、その新たなＬＰＧ＿ＩＤのＥＣＨノードの構成を反映する新しいＬＥＣＨリストとを含むＦＲＥＳＨメッセージを発行することによって、分離処理を呼び出すことができる。このメッセージを受信すると、新しいＬＥＣＨリスト内に列挙されるＥＣＨノードは、新たなＬＰＧ＿ＩＤで
、自らのＬＰＧ＿ＩＤを更新する。
【００７７】
リンクされたＥＣネットワーク内のＥＣＨノードの最大数は、動作性能、無線データトラフィックの性能、道路上の車両の台数または分布のような道路環境を考慮して定義されかつ動作中に柔軟に制御されることが好ましい。たとえば、一般的に、ＥＣＨノードの数が少なくなると、無線帯域幅への負荷が小さくなり、無線帯域幅が十分に活用されないことを犠牲にはするが、（遅延時間が短くなるという点で）性能が向上するようになる。対照的に、ＥＣＨノードの数が増えると、負荷が大きくなる傾向があり、ベストエフォートのアプリケーションにより適している。
【００７８】
あるＥＣＨが有するＬＥＣＨリスト内のＥＣＨノードの相対的な位置は、他のＥＣＨノードが有するＬＥＣＨリスト内のものと一致する。したがって、ＬＥＣＨリストのサイズが十分に長い場合（〜２＊リンクされたＥＣネットワーク内のＥＣＨノードの最大数）、各ＥＣＨは、ＬＥＣＨリストによって、特定のリンクされたＥＣネットワークについて、どのＥＣＨが先頭および末端ＥＣＨであるかがわかる。また、リンクされたＥＣネットワークが分離する場合には、ＥＣＨノードは、どのＥＣＨがリンクされたＥＣネットワーク分離を呼び出すべきであるかを予想することができる。たとえば、最大数＋１に配置されるＥＣＨを、リンクされたＥＣネットワーク分離を呼び出すようにあらかじめ決めておくことができる。
【００７９】
言い換えると、各ＥＣＨは、ＬＥＣＨリスト内のＥＣＨノードの数、およびＬＥＣＨリスト内における自らの位置がわかる。したがって、分離が必要とされるとき（たとえば、所定の最大サイズを超えるとき）、所定の方針を用いて、分離位置を選択することができる。第１の場合には、その分離は、ＬＥＣＨリストの中間において行うことができる。その分離処理を開始するために、中心付近の２つのＥＣＨノードによって分離が開始される（各ＥＣＨがリスト内の自らの位置がわかっているため）。別の場合には、分離は、最大サイズ＋１の位置において行われる。したがって、分離は、最大サイズ位置および最大サイズ＋１の位置にある２つのＥＣＨノードによって開始される。分離後に、２つの新たに形成されたリンクされたＥＣネットワークは、形成された２つのリンクされたＥＣネットワーク間の境界に位置するＥＣＨノードを通して、互いに通信する。
【００８０】
図８を参照すると、上記のプロトコルは、無線送受信機のような、無線通信範囲内のノード間での無線通信を提供するための送信手段８０２を含むコンピューティングデバイス８００によって実行される。さらに、たとえばマイクロコントローラ、マイクロプロセッサのような制御手段８０４が、送信手段８０２を通して他のノードから信号を受信し、また送信手段８０２を通して他のノードに信号を送信するように構成される。また、制御手段８０４は、プロセッサ実行可能命令として上記のプロトコルを実行することによって動作を制御する。記憶手段８０６がコンピューティングデバイス８００内に配置され、制御手段８０４と動作可能に通信する。記憶手段８０６は、メモリモジュール、取出し可能媒体、複数の記憶デバイスの組み合わせ等であってもよく、上述された実施形態のプロトコルを実施するために必要とされるプロセッサ実行可能命令を格納するだけの大きさを有する。さらに、タイミング手段８０８が、別個の構成要素として、または制御手段８０４の機能によって提供される。タイミング手段８０８は、上述の実施形態において参照される各タイマーに必要とされる時間インターバル追跡を提供する。電源供給装置のような電圧供給手段８１０が、必要に応じて構成要素に動作電力を供給するために、コンピューティングデバイス８００の全ての構成要素に電気的に接続される。
【００８１】
上記の実施形態を実行するためのプロセッサ実行可能命令は、ＥＰＲＯＭ、フラッシュメモリまたは他のそのような不揮発性記憶装置等の形態をとる記憶手段８０６に組み込むことができる。さらに、プロセッサ実行可能命令は、光媒体または磁気媒体のようなコン
ピュータ読取り可能媒体に格納することができるし、またはネットワーク（たとえばインターネット）を介してダウンロードすることができる。追加機能が利用できるようになるのに応じて、システムの機能強化を図るために、プロセッサ実行可能命令は、必要に応じてユーザが定期的に更新することができることが望ましい。
【００８２】
本発明の上記の実施形態は、限定ではなく例示を意図しており、また、本発明の全ての実施形態を表すことは意図していない。添付の特許請求の範囲において字義通りに述べられ、また法的に認められる均等物において述べられるような本発明の精神または範囲から逸脱することなく、種々の変更および変形を実施することができる。
【図面の簡単な説明】
【００８３】
【図１】本発明によるアドホック移動ネットワークを示す図である。
【図２】本発明による、２つのリンクされていない等価セルヘッダによるアドホック移動ネットワークの初期化を示す図である。
【図３】本発明による、リンクされていない等価セルヘッダがリンクされた等価セルネットワークに出合う第１の事例を示す図である。
【図４】本発明による、リンクされていない等価セルヘッダがリンクされた等価セルネットワークに出合う第２の事例を示す図である。
【図５】本発明による、リンクされていない等価セルヘッダが既存のリンクされた等価セルネットワークに出合う第３の事例を示す図である。
【図６】本発明の一実施形態による、能動的な移動度検出を実行するためのステップを示すフローチャートである。
【図７】図６の能動的な移動度検出のフローチャートに続く流れ図である。
【図８】本発明の一実施形態による、アドホックネットワークを構成および維持するシステムのブロック図である。
【技術分野】
【０００１】
［発明の分野］
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、ほぼ瞬時に通信を行うために、移動デバイス間にアドホック無線ネットワークを確立するとともに維持することに関する。
【０００２】
［関連出願の相互参照］
本願は、米国特許法第１１９条に基づいて、２００５年１１月２２日にWai Chen他によって出願された“Linked Equivalent Cell Header-based Approach and Protocol for organizing an Ad-Hoc Network”と題する米国特許出願第１１／２８４，７３１号からの優先権を主張し、また２００５年１１月２２日にShengwei Cai他によって出願された“Group-Header Based Method to Organize Local Peer Group of Vehicles for Inter-Vehicle
Communication”と題する米国特許出願第１１／２８５，５９３号に関連し、それらの特許出願はそれぞれ参照により本明細書に援用される。
【背景技術】
【０００３】
［発明の背景］
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーンまたはホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、および、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【０００４】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路および高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【０００５】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが差し迫った状況に陥る前に、必要な措置を講じることができるようになる。この特徴が、交通事故および交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更または合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【０００６】
車両安全通信（「ＶＳＣ」）は、車車間通信とインフラストラクチャを介した車両通信とに大きく分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【０００７】
重要なＶＳＣ性能要件には、衝突回避のような種々のＶＳＣアプリケーションを支援するために、遅延時間が短いこと（約１００ミリ秒）、およびスループットを維持すること（別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ）が含まれる。
【０００８】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【０００９】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【００１０】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい（すなわち、どの車両も、あらかじめその近くにいる車両について何も知らない）。車両間安全通信を構築するために必要とされる全ての情報を車両間で概ねリアルタイムに交換しなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行えるようにする必要がある。協調しない車両の移動度が高いと、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ（移動度、アドレス、名前、メディアセッションのための）を用いることが難しいことを示す。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【００１１】
ホットスポットのような他の場所で利用されるＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【００１２】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【００１３】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔおよびＣａｒＴａｌｋ２０００はいずれも、車車間通信ネットワーク
を構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノードおよび移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費および間接費が生じる。さらに、ＦｌｅｅｔＮｅｔシステムは、位置に基づくルーティングおよび位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【００１４】
ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車車間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。さらに、ＣａｒＴａｌｋ２０００は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【００１５】
ＣａｒＴａｌｋ２０００システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【００１６】
しかしながら、これらのＧＰＳネットワークは大きな欠点を有する。移動度の高い車両環境では、ＧＰＳ情報はすぐに有効でなくなる。ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなＧＰＳ位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【００１７】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００１８】
［発明の概要］
本発明の目的は、複数の移動デバイスをグループ化して、ローカルピアグループ（「ＬＰＧ」）のような１つの管理グループにし、メッセージ伝送を連携および中継し、メッセージ伝搬の範囲および方向を制御することによって、移動デバイス間通信に適した通信境界を創出することである。
【００１９】
さらに、本発明の目的は、ローカルピアグループを確立するための簡単なプロトコル、およびグループ内とグループ間の両方においてノード間でデータを伝送するためのプロトコルを提供することである。
【００２０】
さらに、本発明の目的は、ネットワークの少なくともいくつかのメンバが、ネットワークの他のメンバに対する、ネットワーク内での位置を認識する順序付きネットワークを提供することである。
【課題を解決するための手段】
【００２１】
したがって、本発明により、複数の移動無線デバイス間に移動アドホックネットワークを確立および維持する方法が提供される。本方法は、複数の移動無線デバイスのうちの第１のデバイスを第１の等価セルヘッダ（ＥＣＨ）として動作させるステップを含む。この第１のＥＣＨは、第１の等価セル（ＥＣ）を確立する。この第１のＥＣは第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつエリアの一部を占めるような大きさで形成される。ＥＣはＥＣＨによって管理される。
【００２２】
さらに、第１のＥＣＨからＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）メッセージを送信するステップが提供される。ＥＣＨ＿ＨＥＬＬＯメッセージは、複数の移動無線デバイスのうちの１つのデバイスが第１のＥＣＨであることを通知する。ＥＣＨ＿ＨＥＬＬＯメッセージ送信は、各ＥＣＨが他のＥＣＨとは異なる間隔を有するようにランダムに定められた一定の間隔で行われる。
【００２３】
さらに別のステップは、少なくとも第２のＥＣＨとして動作している少なくとも第２の移動無線デバイスから送信される少なくとも第２のＥＣＨ＿ＨＥＬＬＯメッセージを第１の無線デバイスによって受信すること、および、第２のＥＣＨが受信された唯一の他のＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、第１のＥＣＨノードと第２のＥＣＨノードとの間にリンクされた等価セルネットワークを形成することを提供する。しかしながら、受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、第１のデバイスは、リンクされた等価セルネットワーク内のレギュラーノードとして動作する。レギュラーノードは、リンクされた等価セルネットワークの一部であるが、ＥＣＨと比べて通信特権に制約がある。
【００２４】
さらに、等価セルネットワークに属するＥＣＨの移動度を検出するステップと、所定の選択判定基準に基づいて新たなＥＣＨを選択するステップとが提供される。ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行される。そのレギュラーノードは、移動度を検出されたＥＣＨによって管理される等価セルに対するそのレギュラーノードの位置に基づいて選択される。移動度は、新たなＥＣＨがＥＣネットワークに参加すること、リンクされたＥＣＨがＥＣネットワークを出ること、および、リンクされたＥＣＨが同じＥＣネットワークの別のＥＣＨによって管理されるＥＣ内に移動することを含む。
【００２５】
複数の移動デバイス間にモバイルアドホックネットワークを確立するシステムも提供される。そのシステムは、複数の移動無線デバイスのうちの第１のデバイスを第１の等価セルヘッダ（ＥＣＨ）として動作させる手段を含む。第１のＥＣＨは第１の等価セル（ＥＣ）を確立する。第１のＥＣは、第１のＥＣＨの無線通信範囲のエリア内に中心があり、そのエリアの一部を占めるような大きさで形成される。ＥＣはＥＣＨによって管理される。
【００２６】
さらに、第１のＥＣＨからＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）メッセージを送信する手段が提供される。ＥＣＨ＿ＨＥＬＬＯメッセージは、複数の移動無線デバイスのうちの１つのデバイスが第１のＥＣＨであることを通知する。ＥＣＨ＿ＨＥＬＬＯメッセージ送信は、各ＥＣＨが他のＥＣＨノードとは異なる間隔を有するようにランダムに定められた一定の間隔で行われる。
【００２７】
さらに別の手段は、少なくとも第２のＥＣＨとして動作している少なくとも第２の移動無線デバイスから送信される少なくとも第２のＥＣＨ＿ＨＥＬＬＯメッセージを第１の無線デバイスによって受信すること、および、第２のＥＣＨが受信された唯一の他のＥＣＨ
＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、第１のＥＣＨノードと第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成することを提供する。しかしながら、２つ以上の受信されたＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、第１のデバイスは、リンクされた等価セルネットワーク内のレギュラーノードとして動作する。レギュラーノードは、リンクされた等価セルネットワークの一部であるが、ＥＣＨに比べると通信特権に制約がある。
【００２８】
さらに、等価セルネットワークに属するＥＣＨの移動度を検出する手段と、所定の選択判定基準に基づいて新たなＥＣＨを選択するための手段が提供される。
【００２９】
本発明のこれらの、さらには別の特徴、態様および利点は、以下に記述される詳細な説明、添付の特許請求の範囲および添付の図面との関連で、さらに深く理解されるようになるであろう。
【発明を実施するための最良の形態】
【００３０】
［発明の詳細な説明］
本発明によれば、複数のノードすなわち移動デバイスが管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて構築される。このグループ化すなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ内や複数のＬＰＧ間でのルーティングの基礎および本発明によるアドホック無線ネットワーク内における伝送の組織化の基礎となり、限定はしないが、車両安全や情報アプリケーションを含む、無線通信を支援する。
【００３１】
ＬＰＧの目的は、近くにあるノード間での種々の程度の連携を確立することである。これら近くにあるノードは、無線通信の能力を備える移動デバイスである。移動デバイスの実施形態は、車両内に設置されたり車両内に個別に持ち込まれたりする通信デバイスを備える車両や、通信デバイスを携帯した歩行者を含む。好ましい実施形態は、固有の通信デバイスを備える移動車両である。しかしながら、携帯電話、ＰＤＡ、ノートパソコン等を含む他の通信デバイスも本発明の一部として用いることができ、唯一の必要条件は、その通信デバイスが、開示される実施形態の適当な動作のために必要な無線通信プロトコルに対応していることである。
【００３２】
連携の程度には、２つのタイプがある。第１のタイプは直ぐ近くにある移動デバイスの密な連携であり、概ね瞬時のメッセージ伝送の支援に利用されるＬＰＧ内通信のために用いられる。たとえば、緊急道路障害物警告や他のタイプの緊急メッセージまたは安全メッセージの送信は、ＬＰＧ内メッセージ伝送を用いて実行される。これらのメッセージでは、遅延が通常約１００ｍｓ以下であることが要求される。
【００３３】
第２のタイプは、近くにある移動デバイスの疎な連携である。このタイプの連携は、リンクまたは相互接続されているＬＰＧの間のＬＰＧ間通信を支援するために用いられる。たとえば、ＬＰＧ間通信は、道路認識アプリケーションや、ドライバの視界拡張のために用いることができる。
【００３４】
ＬＰＧは、直ぐ近くにある複数のノードから動的に形成される。具体的には、第１のノードが無線信号を送信し、第１のノードの範囲内にある他のノードが、その無線信号を受信する能力を有する。ＬＰＧは無線通信エリアに基づいて形成されるので、ＬＰＧ内のノードは、固定インフラストラクチャなしに、シングルホップまたはマルチホップで互いに通信することができる。
【００３５】
［用語集］
さらに説明を続ける前に、本開示を通して共通に用いられるいくつかの重要な用語を定義する必要がある。
【００３６】
用語「等価セル（equivalent cell）」（ＥＣとも呼ばれる）は、無線通信エリアの一
部を指している。ＥＣは、等価セルネットワークの基本編成構造を形成する。
【００３７】
用語「等価セルヘッダ（equivalent cell header）」（ＥＣＨとも呼ばれる）は、等価セルを定義、維持および管理するノードを指している。ＥＣＨはリンクされていなくても、リンクされていてもよい。リンクされたＥＣネットワークでは、メンバＥＣＨノードが、ネットワーク内通信バックボーンを提供する。ネットワーク内の全てのメッセージは、宛先に到着するまで、ＥＣＨ間で送信される。
【００３８】
用語「レギュラーノード（regular nodes）」は、リンクされたＥＣネットワークのメ
ンバノードを指す。レギュラーノードは、ネットワーク内での通信特権に制約がある。レギュラーノードは、ある特定の状況下において、ＥＣＨになることができる。レギュラーノードとＥＣＨとの違いは機能的な違いだけである。構造的には、いずれのノードタイプも同じであるものの、特定の機能が、特定の時点におけるノードタイプに応じて、その時点で実行できたり実行できなかったりする。
【００３９】
用語「リンクされた（linked）」は、２つ以上のＥＣＨがシングルホップまたはマルチホップで互いに無線通信していることを指している。リンクされたＥＣＨ（またはリンクされたＥＣ）ネットワークは、ＥＣＨノードに関連付けられた、シングルホップの通信範囲内にあるレギュラーノードを含むことができる。
【００４０】
用語「リンクされていない（unlinked）」は、ＥＣＨが他のＥＣＨと無線通信していないことを指している。リンクされていないＥＣＨは、自ネットワークの唯一のメンバＥＣＨであり、関連付けられるレギュラーノードを持たない。
【００４１】
用語「ｋのリンク度（linked degree of k）」は、２つのＥＣＨをリンクする無線ホップの数ｋを指している。たとえば、ＥＣＨ ＡとＥＣＨ Ｂが直にリンクされる場合には、リンク度は１（すなわちｋ＝１）である。しかしながら、ＥＣＨ ＡとＥＣＨ Ｂが互いを検出することができ、かつＥＣＨ ＢとＥＣＨＣが互いを検出することができるが、ＥＣＨ ＡとＥＣＨ Ｃが互いを検出できない場合には、ＥＣＨ ＡとＥＣＨ Ｃとの間のリンク度は２（すなわちｋ＝２）である。
【００４２】
用語「区別されたＥＣＨノード（distinct ECH nodes）」は、同じ等価セルネットワークのメンバでないＥＣＨノードを指している。区別されたＥＣＨノードは、リンクされていないＥＣＨノードであっても、リンクされたＥＣＨノードであってもよいが、異なる等価セルネットワークに属している。
【００４３】
用語「移動度（mobility）」は、リンクされたＥＣネットワークに対するＥＣＨの動きを指している。より具体的には、移動度は、リンクされたＥＣネットワークに入るＥＣＨの動き、メンバであるリンクされたＥＣネットワークから出るＥＣＨの動き、またはあるＥＣから別のＥＣＨによって管理される別のＥＣに移るＥＣＨの動きを指している。
【００４４】
［リンクされたＥＣネットワークの形成］
図１を参照すると、本発明は、動的かつ自己組織的なローカルピアグループ、すなわちリンクされた等価セルネットワーク１００を提供する。リンクされた等価セルネットワーク（Ｌ＿ＥＣ）１００の基本構成ブロックは、等価セルヘッダ（ＥＣＨ）１０４ａを中心
にした等価セル（ＥＣ）１０２ａである。複数のＥＣ１０２ａ、１０２ｂ、１０２ｃが無線で互いにリンクし、Ｌ＿ＥＣ１００を形成する。これ以降、ＥＣ１０２ａ、１０２ｂおよび１０２ｃをまとめて符号１０２によって参照し、ＥＣＨノード１０４ａ、１０４ｂおよび１０４ｃをまとめて符号１０４によって参照する。
【００４５】
ＥＣＨ１０４ａは、ＰＤＡ、ノートパソコンまたは車両搭載コンピューティングデバイスのような、移動無線ネットワーキングデバイスである。ＥＣＨ１０４ａは、外側に向かって全方向に広がる無線通信エリア１０８を有する無線送受信機を備えている。図１に示されるように、無線通信エリア１０８は、定義されるＥＣ１０２ａのエリアよりもかなり大きい。図１は、３つのＥＣノード１０２ａ、１０２ｂおよび１０２ｃを含む無線通信エリア１０８を示すが、これは例示にすぎず、唯一の構成と解釈されることを意図していないことに留意されたい。具体的には、定められた無線通信エリア内に、任意の数のＥＣ１０２が存在するようにすることができる。しかしながら、本発明の説明を簡単にするために、ＥＣＨノードの無線通信エリア１０８は、これ以降、３つのＥＣノード１０２を含む。
【００４６】
ＥＣＨノード１０４は、Ｌ＿ＥＣ１００のネットワーキングバックボーンを提供する。具体的には、全てのＥＣ間通信および制御データ送信は、ＥＣＨノード１０４によって実行される。さらに、ＥＣＨノード１０４ａは、割り当てられたＥＣ１０２ａの動作パラメータを管理する。そのような動作パラメータは、メンバすなわちＥＣＨノード１０４ｂのＥＣ１０２ｂ内に位置するレギュラーノード１０６を追跡すること、ＥＣノード１０４ｂと通信している他のＥＣＨノード１０４ａ、１０４ｃのリストを維持すること、およびＬ＿ＥＣ１００内でのその相対的な位置を含む。レギュラーノード１０６は、ＥＣ１０２内に配置される移動無線ネットワークデバイスである。任意の移動無線デバイスは、ＥＣＨ１０４として、またはレギュラーノード１０６として動作することができる。
【００４７】
図２を参照しながら、これ以降、アドホックネットワークの初期化および統合について説明する。ノード２０２、すなわち移動無線デバイスが、最初に、ＥＣＨとして動作し、自身が唯一のメンバであるリンクされていないＥＣ２０４を確立する。ＥＣＨ２０２は、第２のＥＣＨ２０６からの送信を検出すると、ＥＣＨ＿ＨＥＬＬＯメッセージで応答し、第２のＥＣＨ２０６に識別情報を与える。検出された他のＥＣＨがＥＣＨ２０６だけである場合には、その結果として、ＥＣＨ２０２およびＥＣＨ２０６を含むリンクされたＥＣ２１０になる。したがって、これら２つのＥＣＨ２０２および２０６は、ＥＣ２０４およびＥＣ２０８を含むネットワークを形成する、すなわち既に確立されているネットワークを拡張する。さらに、２つ以上のリンクされていないＥＣＨノードを検出するリンクされていないＥＣＨは、その２つ以上のリンクされていないＥＣＨノードとネットワークを形成し、全ての検出されたＥＣＨノードを含むリンクされたＥＣが構成される。
【００４８】
リンクされたＥＣ２１０にさらに別のリンクされていないＥＣＨノードが出合うと、そのノードは、さらなるリンクされたＥＣＨまたはレギュラーノードのいずれかとして、増大しているリンクされたＥＣに組み込まれる。具体的には、リンクされていないＥＣＨノードが、互いにリンクされている２つのＥＣＨノードを検出すると、レギュラーノードになる。たとえば、図３では、リンクされていないＥＣＨ３０２ａは、レギュラーノード３０２ｂになる。これらの移動無線デバイスは、レギュラーノードとして、全Ｌ＿ＥＣ１００内でメッセージを送受信することができる。しかしながら、全てのメッセージはＥＣＨノード２０２および２０６を通してルーティングされ、レギュラーノード間で直にはルーティングされない。このようにして、帯域幅が節約される。
【００４９】
別の方法では、図４に示されるように、リンクされていないＥＣＨノード４０２ａが他のＥＣＨ２０２を１つのみ検出する場合は、Ｌ＿ＥＣの一部であってもなくても、検出さ
れたＥＣＨ２０２にリンクし、リンクされたＥＣ４０４の長さを拡張してリンクされたＥＣＨ４０２ｂになるであろう。
【００５０】
レギュラーノードがただ１つのＥＣＨを検出する場合は、そのレギュラーノードはＥＣＨになり、そして、検出されたＥＣＨにリンクしてリンクされたＥＣネットワークを形成する。さらに、レギュラーノードまたはリンクされていないＥＣＨは、自ノードが「リンカー」であると検出した場合には、リンクされたＥＣＨになる。
【００５１】
リンカーは、複数の区別されたＥＣＨを検出するノード（レギュラーまたはＥＣＨ）である。ここで、検出されたＥＣＨノードは同じＥＣネットワークのメンバではない。これらの区別されたＥＣＨノードは、リンクされていないＥＣＨノード、異なるネットワークに属するリンクされたＥＣＨノード、またはその両方の組み合わせであり得る。
【００５２】
レギュラーノードが自ノードをリンカーであると認識するとき、レギュラーノードは新たなＥＣＨになり、これら複数の区別されたＥＣＨを接続して、より大きな１つのネットワークを形成する。レギュラーノードは、あるＥＣＨノードがネットワークの一部であるか否かを、そのＥＣＨノードが属するリンクされたＥＣネットワークのメンバＥＣＨノードのリスト（本明細書において、ＬＥＣＨリストと呼ばれる）を受信することによって検出する。ＬＥＣＨリストはＥＣＨメッセージに含まれる。レギュラーノードは、複数の区別されたＥＣＨノードのＬＥＣＨリストをそれぞれ比較することによって、自ノードが「リンカー」であるか判定する。
【００５３】
区別されたＥＣＨノードによって送信されるＥＣＨメッセージは、それらのリスト間で共有されるＥＣＨノードを持たない。すなわち、両方のリストにのるＥＣＨは存在しない。リンクされていないＥＣＨノードはそのネットワーク内の唯一のＥＣＨであるので、そのＬＥＣＨリストは自ノードへの参照だけを含む。図５の例では、リンクされていないＥＣＨ５００は、３つのリンクされているＥＣＨ５０１〜５０３からそれぞれＥＣＨ＿ＨＥＬＬＯメッセージを受信する。ＥＣＨ５０１はＥＣＨ５０６とリンクしてリンクされたＥＣ５０５を形成し、ＥＣＨ５０２はＥＣＨ５０７とリンクしてリンクされたＥＣ５１０を形成し、ＥＣＨ５０３はＥＣＨ５０８とリンクしてリンクされたＥＣ５１５を形成する。３つのＥＣＨ＿ＨＥＬＬＯメッセージを受信すると、リンクされていないＥＣＨ５００は、２つ以上のＥＣＨリスト内に共通に列挙されるＥＣＨがあるか否かを判定する。この事例では、３つのリンクされるＥＣＨリストは共通のメンバを持たない。したがって、リンクされていないＥＣＨ５００は、自ノードが「リンカー」ノードであると判定し、これら３つの離ればなれの区別されたリンクＥＣ５０５、５１０および５１５全てを１つにリンクし、１つのリンクされたネットワーク５２０を形成する。レギュラーノードも、そのノードが「リンカー」ノードであるか否かを判定するために、同様の評価を実行する。
【００５４】
リンクされたＥＣは、ＥＣＨ＿ＨＥＬＬＯメッセージにおいて送信される制御メッセージを介して維持される。ＥＣＨ＿ＨＥＬＬＯメッセージは、あらかじめ定義された間隔で、各ＥＣＨによって送信される。レギュラーノードはＥＣＨ＿ＨＥＬＬＯメッセージを受信するだけで、応答はしない。レギュラーノードまたはリンクされたＥＣＨノードがＥＣＨ＿ＨＥＬＬＯメッセージを受信するのに失敗すると、そのノードはリンクされていないＥＣＨになる。
【００５５】
ＥＣＨ＿ＨＥＬＬＯメッセージは、メッセージの発信元のＩＤと、発信元によって送信される現在のメッセージの番号を特定するシーケンス番号と、Ｌ＿ＥＣの第１の通信経路に沿って発信元が認識できるＥＣＨノードの第１のリスト（ＬＥＣＨリスト）と、Ｌ＿ＥＣの第２の通信経路に対する第２のＬＥＣＨリストとを含むことが好ましい。付加的なＬＥＣＨリストを提供してもよく、その場合、各ＬＥＣＨリストは、発信元ＥＣＨを中心と
したＬ＿ＥＣの１つのブランチ、すなわち通信経路、に沿って出合う全てのＥＣＨノードのＥＣＨ ＩＤを含む。さらに、ＥＣＨ＿ＨＥＬＬＯメッセージは、タイムアウト値を含むこともできる。タイムアウト値は、現在のＥＣＨ＿ＨＥＬＬＯメッセージの受信と次のＥＣＨ＿ＨＥＬＬＯメッセージの受信との間の最長経過時間を他のＥＣＨノードおよびレギュラーノードに通知するものであり、それにより、特定のＥＣＨがリンクされたＥＣネットワーク内に依然として存在するか否かを判定するための手段を提供する。
【００５６】
各Ｌ＿ＥＣは、ＬＰＧ＿ＩＤによって識別される。リンクされたＥＣＨノードのグループがＬ＿ＥＣを形成し、その際、ＬＰＧ＿ＩＤを割り当てられる。Ｌ＿ＥＣ内のリンクされるＥＣＨの数は、動作性能やネットワーク内の移動デバイス（すなわち、ノード）の台数または分布のような環境条件を考慮して柔軟に定義することができる。ＥＣＨ＿ＨＥＬＬＯメッセージを通して、ＬＰＧ＿ＩＤがメンバＥＣＨノードおよびレギュラーノードに通知される。このようにして、レギュラーノードは、現在どのＬ＿ＥＣに属しているかがわかる。
【００５７】
ＬＰＧ＿ＩＤは、個々のＬ＿ＥＣに割り当てられ、そのＬ＿ＥＣを識別する一意の識別子である。したがって、ＬＰＧ＿ＩＤは、メンバＥＣＨノードのＩＤや他の識別情報の組み合わせのような、個々のＬ＿ＥＣに固有な特性に基づいて作成することができる。また、ＬＰＧ＿ＩＤは、ランダムに生成されたコードであってもよい。そのような事例では、コードを形成するビット数または文字の数が、ＬＰＧ＿ＩＤの固有性を決定する。コード長が長くなるほど、短いコード長よりもランダムに繰り返される可能性が小さくなる。
【００５８】
［移動度検出およびＥＣＨ選択］
本明細書において定義される移動度検出は、リンクされたＥＣに出入りするＥＣＨの動き、および別のＥＣ内に入るＥＣＨの動きを検出することを指している。レギュラーノードの動きはリンクされたＥＣネットワークの動作に影響を及ぼさないが、ＥＣＨノードが動く結果として、リンクされたＥＣネットワークの動作が非効率的になったり、またはリンクされたＥＣネットワークが崩壊したりする可能性がある。移動によって、ＥＣＨノードが重複するＥＣを有する可能性がある。その結果、あまりにも近くでメッセージが再送されることに起因して、ネットワークのそのエリアにおけるデータ伝送が非効率的になり、所定の長さのネットワークを伝搬するのにより長い時間がかかるようになる。それとは別に、移動は反対の影響を及ぼす可能性もあり、ＥＣＨノードの動きによって、２つのＥＣＨノードの無線通信範囲間に隙間が形成され、その隙間を越えてメッセージが伝搬できないので、基本的には、その結果として、その場所においてリンクされたＥＣネットワークが崩壊する。
【００５９】
リンクされたＥＣネットワーク内の移動度を補正するために、移動度検出が必要とされる。移動度検出は、受動的または能動的に実行することができる。受動的な移動度検出法では、ＥＣＨ＿ＨＥＬＬＯメッセージを用いて、ノードの移動度を検出する。具体的には、この方法では、ＥＣＨがネットワークから外れたことをその周囲にあるＥＣＨノードまたはレギュラーノードが検出するためには、あらかじめ設定された時間が経過することが必要である。
【００６０】
全てのＥＣＨは自らのタイマーに基づいて動作し、各ＥＣＨはＴ秒毎にＥＣＨ＿ＨＥＬＬＯメッセージを送信する。時間Ｔの間に、各ＥＣＨは（およびレギュラーノードも）、近くにあるＥＣＨノードからＥＣＨ＿ＨＥＬＬＯメッセージを収集する。収集されたメッセージに基づいて、ＥＣＨは自身のＬＥＣＨリストおよび送信するＥＣＨ＿ＨＥＬＬＯメッセージを更新する。更新されたＥＣＨノードリストを維持するために、あるＥＣＨからＥＣＨ＿ＨＥＬＬＯメッセージを受信せずに所定の時間が経過すると、ＥＣＨリストからそのＥＣＨを自動的に削除する。有効期限または所定の時間は、Ｔよりも長くなければな
らず、たとえば３Ｔである。この検出の速さは完全に、ＥＣＨ＿ＨＥＬＬＯの時間Ｔによって決まる。あるＥＣＨからＥＣＨ＿ＨＥＬＬＯメッセージが受信されると、タイマーはリセットまたはリスタートされる。タイマーを用いて、ＥＣＨリスト内の全てのＥＣＨについてのＥＣＨ＿ＨＥＬＬＯメッセージを追跡する。
【００６１】
しかしながら、そのリストは、所定の時間が経過した後にはじめて更新される。すなわち、リンクされたＥＣネットワーク内にもはや存在しない古いＥＣＨが削除される。したがって、あるＥＣＨが送信範囲から既に移動しているが、それでもＥＣＨリスト内に列挙されている可能性がある。この受動的な方法では、結果として、メッセージ転送が途切れる可能性があり、Ｌ＿ＥＣネットワークの性能に影響を及ぼす。したがって、能動的な移動度検出法を用いて、ＥＣＨ移動度のより迅速な検出および解決を提供することができる。
【００６２】
能動的な移動度検出では、ＥＣＨ＿ＨＥＬＬＯメッセージと組み合わせて、新たな制御メッセージＭ＿ＤＥＴＥＣＴが用いられる。これにより、短い時間、すなわちＴよりも短い時間で移動度を検出することができる。Ｍ＿ＤＥＴＥＣＴメッセージは、発信者のＩＤと、移動した可能性のあるＥＣＨ（ｍＥＣＨ）、すなわち、その元の位置から離れているかまたはリンクされたＥＣネットワークから出ているＥＣＨのＩＤとを含む。Ｍ＿ＤＥＴＥＣＴメッセージは、予期しないＥＣＨ＿ＨＥＬＬＯメッセージを受信したＥＣＨによって送信される。Ｍ＿ＤＥＴＥＣＴメッセージは、発信者の１ホップ範囲内にあり、かつ送信側ＥＣＨまたはｍＥＣＨのいずれかに関連付けられるＥＣＨおよびレギュラーノードの両方を対象とする。
【００６３】
図６は、能動的な移動度検出方法のためのフローチャートを示す。この方法は、ステップ６０１において、レギュラーノード（ＲＮａ）がＭ＿ＤＥＴＥＣＴメッセージを受信するときに開始する。
【００６４】
Ｍ＿ＤＥＴＥＣＴメッセージを受信すると、ステップ６０３において、そのレギュラーノードはＥＣＨ選択を開始する。レギュラーノードのＥＣＨ選択処理の第１のステップは、ステップ６０３において、タイマー（選択ランダムタイマー）をランダムな値（たとえば、０〜ｋの範囲の値、ただしｋはＴ ＨＥＬＬＯ時間未満である）に設定することである。選択ランダムタイマーをランダムな時間に設定するのは、重複して選択が呼び出されるのを避けるためである。ステップ６０５において、選択ランダムタイマーが切れる場合には、ステップ６１１において、レギュラーノードがＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹメッセージを送信し、ステップ６１３において、第２のタイマーすなわちホールドタイマー（たとえば、４／Ｔ）を設定する。その後、レギュラーノードは、ステップ６１５において、近くにいるＥＣＨノードからＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージの形で応答を受信するのを待つ。近くにいるＥＣＨは、１ホップ送信距離内にいる、すなわち中継が不要なＥＣＨである。選択ランダムタイマーが依然として動作している他のレギュラーノードは、ＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹメッセージを受信すると、その選択ランダムタイマーを直ちに停止し、レギュラーノードとしてとどまる。
【００６５】
同時に、ＥＣＨは、ＥＬＥＣＴＩＯＮ＿ＱＵＥＲＹを受信すると、応答ランダムタイマー（たとえば、０〜ｈの範囲、ただしｈは約４／Ｔ）のようなランダムタイマーを設定する。応答ランダムタイマーが経過する間、そのＥＣＨは他のＥＣＨノードからのＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを待ち受ける。応答ランダムタイマーが切れると、そのＥＣＨは、発信者ＩＤ、クエリー発信元ＩＤ、および応答ランダムタイマーが経過する間にＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを受信することによって検出された全てのＥＣＨノードのＩＤを含む、ＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを作成し送信する。
【００６６】
ホールドタイマーが切れる時点を判定するために、ホールドタイマーは監視される。ステップ６１７においてホールドタイマーが切れると、レギュラーノードは、ＥＣＨによって送信されたＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを収集し、リンク状態を解析して、自ノードがＥＣＨになるべきか否かをステップ６１９において判定する。応答したＥＣＨノードが少なくとも２のリンク度でシリアルにリンクされているとステップ６２１において判定される場合には、ステップ６０９に進み自ノードはレギュラーノードにとどまる。応答したＥＣＨノードが１のリンク度の１つのリンクだけを形成するとステップ６２３において判定される場合には、処理はステップ６２５に進み、自ノードがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを以前に送信しているか否かを判定する。ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージは、発信者ＩＤ、および以前のクエリーにおいて検出された全てのＥＣＨのＩＤを含む。
【００６７】
そのレギュラーノードが以前にＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信していた場合には、処理はステップ６０９に進み、レギュラーノードとしてとどまる。しかしながら、そのレギュラーノードが以前にＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信していなかった場合には、収集された現在の情報に基づいては判断を下すことができないので、ステップ６２９においてＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信する。そのレギュラーノードがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを送信した後に、処理はステップ６１３に進む。
【００６８】
しかしながら、ステップ６２３の条件が満たされない場合には、ステップ６２７において、そのレギュラーノードは自らをＥＣＨと宣言し、新たなＥＣＨ ＩＤとして設定される発信者ＩＤと、古いＥＣＨ ＩＤとを含むＦＲＥＳＨメッセージを送信する。こうして、ＦＲＥＳＨメッセージの受信者は、古いＥＣＨ ＩＤの代わりに新しいＥＣＨ ＩＤが用いられることを通知されるので、それに応じて、ＦＲＥＳＨメッセージの各受信者は、現在のＬＥＣＨリストを更新する。
【００６９】
ステップ６２９において、ＲＮaがＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを
送信する場合に、その送信メッセージに応答して実行される手順を図７に示す。ステップ７０１では、レギュラーノード（ＲＮb）が、ＲＮaによって送信されるＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージを受信する。ＲＮbの近くに、このステップおよび以下に
記述される後続のステップを実行する複数のレギュラーノードが存在し得る。ステップ７０３では、ＲＮbが、ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹメッセージにおいて列挙され
るＥＣＨノードの可視性を評価する。ステップ７０５に進むと、列挙されるＥＣＨノードのいずれもＲＮbが見えない場合には、ステップ７０７に進み、ＲＮbは選択ランダムタイマーを設定する。選択ランダムタイマーが設定されたインターバル中に、ＲＮbは、ステ
ップ７０９に示されるように、新たに選択されたＥＣＨノードによって送信されるＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを受信するのを待ち受ける。ＲＮbがＥＬＥＣＴＩＯ
Ｎ＿ＲＥＰＬＹメッセージを受信する前に、ステップ７１１において選択ランダムタイマーが切れる場合には、ステップ７１３においてＲＮbは自らをＥＣＨとして宣言する。ス
テップ７１５において、新たなＥＣＨはＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージを送信する。しかしながら、ＲＮbの選択ランダムタイマーが切れる前に、ステップ７０９にお
いてＥＬＥＣＴＩＯＮ＿ＲＥＰＬＹメッセージが受信される場合には、ＲＮaはレギュラ
ーノードにとどまる。ステップ７０５に戻ると、ＥＬＥＣＴＩＯＮ＿ＲＥ＿ＱＵＥＲＹにおいて列挙される少なくとも１つのＥＣＨがＲＮbから見える場合には、ＲＮbはレギュラーノードにとどまる。
【００７０】
レギュラーノードがＥＣＨになった後に、ＦＲＥＳＨメッセージを送信することによって、そのノードはリンクされたＥＣネットワーク内の他のＥＣＨノードに、その状態変化を通知する。このメッセージによって、受信側のＥＣＨノードは、移動によって古くなっ
てしまったＬＥＣＨリストを直ちに更新する。古いＥＣＨがＦＲＥＳＨメッセージを受信すると、その古いＥＣＨは自らをレギュラーノードに降格させる。
【００７１】
好ましい実施形態では、受動的および能動的の両方の移動度検出が用いられるが、いずれかの検出方法を独立して用いることもできる。
【００７２】
種々のタイマー、たとえば選択ランダムタイマー、ホールドタイマーおよびＥＣＨ＿ＨＥＬＬＯメッセージタイマーの値はランダムにあらかじめ設定されるが、選択されるランダムな時間は、各機能の動作性能や動作の遅延要求を満足するように選択される。しかしながら、選択ランダムタイマーおよびホールドタイマーは、ＴをＥＣＨ＿ＨＥＬＬＯ周期として、１Ｔよりもはるかに小さい値を有することが好ましい。こうして、ＥＣＨ選択動作は、１Ｔ以内にＥＣＨの移動に応答する。
【００７３】
［リンクされたＥＣネットワークの融合および分離］
２つ以上のリンクされたＥＣネットワークが互いに極めて近接するとき、それらのリンクされたＥＣネットワークは互いに融合することができる。しかしながら、リンクされたＥＣネットワーク全体が他のリンクされたＥＣネットワークに「融合する」のではなく、むしろ、近くにあるＥＣＨノードが互いにリンクする。具体的には、ＥＣＨノードは、互いに近づいていくと、ＥＣＨ＿ＨＥＬＬＯメッセージを交換する。ＥＣＨ＿ＨＥＬＬＯメッセージの交換を通して、それらのＥＣＨノードは、リンクされたＥＣネットワークのＩＤ（ＬＰＧ＿ＩＤ）、メンバＥＣＨノードの識別情報、レギュラーノード、およびＬＰＧ内のＥＣＨノードの数のような、互いのリンクされたＥＣネットワークに関する情報を得るであろう。
【００７４】
融合するリンクされたＥＣネットワークの結合したサイズが、所定の最大ＬＰＧサイズよりも小さい（または等しい）場合には、融合するリンクされたＥＣネットワークは１つの大きなリンクされたＥＣネットワークを形成する。隣接したＥＣＨノードが互いにリンクされるようになり、実効的には、全てのＥＣＨを結合して１つのネットワークが形成される。しかしながら、融合するリンクされたＥＣネットワークの結合したサイズが所定の最大ＬＰＧサイズよりも大きい場合には、融合するリンクされたＥＣネットワークは、２つの新たなリンクされたＥＣネットワークを形成することになり、その新たなネットワークは、元の融合するリンクされたＥＣネットワークとは、サイズおよびメンバＥＣＨノードが異なる。ＥＣＨノードの全数が所定の最大ＬＰＧサイズを超えなければ、任意の数のリンクされたＥＣネットワークを融合することができる。
【００７５】
所定の最大ＬＰＧサイズを超える場合には、リンクされたＥＣネットワークは２つの新たなリンクされたＥＣネットワークに分離することができる。しかしながら、そのようなリンクされたＥＣネットワークの分離は比較的稀である。大体の場合には、リンクされたＥＣネットワークは、所定の最大ＬＰＧサイズよりも少ない数のＥＣＨノードを含む。リンクされたＥＣネットワークが、所定の最大ＬＰＧサイズよりも多くの数のＥＣＨノードを含む場合には、２つのリンクされたＥＣネットワークに分離することになり、分離後のネットワークの個々のサイズは最大ＬＰＧサイズよりも小さい。
【００７６】
ＥＣＨは、そのＬＥＣＨリストから、リンクされたＥＣネットワークの現在のサイズを入手することができる。ＬＥＣＨリスト内の各エントリは、ＥＣＨ＿ＩＤおよび対応するＬＰＧ＿ＩＤを含む。あるＥＣＨが、そのＬＰＧサイズが所定の最大ＬＰＧサイズよりも大きいことを検出する場合には、そのＥＣＨは、新たなＬＰＧ＿ＩＤと、その新たなＬＰＧ＿ＩＤのＥＣＨノードの構成を反映する新しいＬＥＣＨリストとを含むＦＲＥＳＨメッセージを発行することによって、分離処理を呼び出すことができる。このメッセージを受信すると、新しいＬＥＣＨリスト内に列挙されるＥＣＨノードは、新たなＬＰＧ＿ＩＤで
、自らのＬＰＧ＿ＩＤを更新する。
【００７７】
リンクされたＥＣネットワーク内のＥＣＨノードの最大数は、動作性能、無線データトラフィックの性能、道路上の車両の台数または分布のような道路環境を考慮して定義されかつ動作中に柔軟に制御されることが好ましい。たとえば、一般的に、ＥＣＨノードの数が少なくなると、無線帯域幅への負荷が小さくなり、無線帯域幅が十分に活用されないことを犠牲にはするが、（遅延時間が短くなるという点で）性能が向上するようになる。対照的に、ＥＣＨノードの数が増えると、負荷が大きくなる傾向があり、ベストエフォートのアプリケーションにより適している。
【００７８】
あるＥＣＨが有するＬＥＣＨリスト内のＥＣＨノードの相対的な位置は、他のＥＣＨノードが有するＬＥＣＨリスト内のものと一致する。したがって、ＬＥＣＨリストのサイズが十分に長い場合（〜２＊リンクされたＥＣネットワーク内のＥＣＨノードの最大数）、各ＥＣＨは、ＬＥＣＨリストによって、特定のリンクされたＥＣネットワークについて、どのＥＣＨが先頭および末端ＥＣＨであるかがわかる。また、リンクされたＥＣネットワークが分離する場合には、ＥＣＨノードは、どのＥＣＨがリンクされたＥＣネットワーク分離を呼び出すべきであるかを予想することができる。たとえば、最大数＋１に配置されるＥＣＨを、リンクされたＥＣネットワーク分離を呼び出すようにあらかじめ決めておくことができる。
【００７９】
言い換えると、各ＥＣＨは、ＬＥＣＨリスト内のＥＣＨノードの数、およびＬＥＣＨリスト内における自らの位置がわかる。したがって、分離が必要とされるとき（たとえば、所定の最大サイズを超えるとき）、所定の方針を用いて、分離位置を選択することができる。第１の場合には、その分離は、ＬＥＣＨリストの中間において行うことができる。その分離処理を開始するために、中心付近の２つのＥＣＨノードによって分離が開始される（各ＥＣＨがリスト内の自らの位置がわかっているため）。別の場合には、分離は、最大サイズ＋１の位置において行われる。したがって、分離は、最大サイズ位置および最大サイズ＋１の位置にある２つのＥＣＨノードによって開始される。分離後に、２つの新たに形成されたリンクされたＥＣネットワークは、形成された２つのリンクされたＥＣネットワーク間の境界に位置するＥＣＨノードを通して、互いに通信する。
【００８０】
図８を参照すると、上記のプロトコルは、無線送受信機のような、無線通信範囲内のノード間での無線通信を提供するための送信手段８０２を含むコンピューティングデバイス８００によって実行される。さらに、たとえばマイクロコントローラ、マイクロプロセッサのような制御手段８０４が、送信手段８０２を通して他のノードから信号を受信し、また送信手段８０２を通して他のノードに信号を送信するように構成される。また、制御手段８０４は、プロセッサ実行可能命令として上記のプロトコルを実行することによって動作を制御する。記憶手段８０６がコンピューティングデバイス８００内に配置され、制御手段８０４と動作可能に通信する。記憶手段８０６は、メモリモジュール、取出し可能媒体、複数の記憶デバイスの組み合わせ等であってもよく、上述された実施形態のプロトコルを実施するために必要とされるプロセッサ実行可能命令を格納するだけの大きさを有する。さらに、タイミング手段８０８が、別個の構成要素として、または制御手段８０４の機能によって提供される。タイミング手段８０８は、上述の実施形態において参照される各タイマーに必要とされる時間インターバル追跡を提供する。電源供給装置のような電圧供給手段８１０が、必要に応じて構成要素に動作電力を供給するために、コンピューティングデバイス８００の全ての構成要素に電気的に接続される。
【００８１】
上記の実施形態を実行するためのプロセッサ実行可能命令は、ＥＰＲＯＭ、フラッシュメモリまたは他のそのような不揮発性記憶装置等の形態をとる記憶手段８０６に組み込むことができる。さらに、プロセッサ実行可能命令は、光媒体または磁気媒体のようなコン
ピュータ読取り可能媒体に格納することができるし、またはネットワーク（たとえばインターネット）を介してダウンロードすることができる。追加機能が利用できるようになるのに応じて、システムの機能強化を図るために、プロセッサ実行可能命令は、必要に応じてユーザが定期的に更新することができることが望ましい。
【００８２】
本発明の上記の実施形態は、限定ではなく例示を意図しており、また、本発明の全ての実施形態を表すことは意図していない。添付の特許請求の範囲において字義通りに述べられ、また法的に認められる均等物において述べられるような本発明の精神または範囲から逸脱することなく、種々の変更および変形を実施することができる。
【図面の簡単な説明】
【００８３】
【図１】本発明によるアドホック移動ネットワークを示す図である。
【図２】本発明による、２つのリンクされていない等価セルヘッダによるアドホック移動ネットワークの初期化を示す図である。
【図３】本発明による、リンクされていない等価セルヘッダがリンクされた等価セルネットワークに出合う第１の事例を示す図である。
【図４】本発明による、リンクされていない等価セルヘッダがリンクされた等価セルネットワークに出合う第２の事例を示す図である。
【図５】本発明による、リンクされていない等価セルヘッダが既存のリンクされた等価セルネットワークに出合う第３の事例を示す図である。
【図６】本発明の一実施形態による、能動的な移動度検出を実行するためのステップを示すフローチャートである。
【図７】図６の能動的な移動度検出のフローチャートに続く流れ図である。
【図８】本発明の一実施形態による、アドホックネットワークを構成および維持するシステムのブロック図である。
【特許請求の範囲】
【請求項１】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法であって、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させること、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、前記ＥＣＨによって管理される第１の等価セルを確立すること、
前記複数の移動無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信すること、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信すること、
前記第２のＥＣＨが他の唯一の受信されたＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨに属する場合には、前記第１のＥＣＨと前記第２のＥＣＨとの間にリンクされた等価セルネットワークを構成すること、および
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨに属する場合には、前記第１のデバイスを前記リンクされた等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨに比べて通信特権に制約があるレギュラーノードとして動作させること、
を含む、複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項２】
前記レギュラーノードは、１つのＥＣＨ＿ＨＥＬＬＯメッセージだけを受信する場合に、該受信されたＥＣＨ＿ＨＥＬＬＯメッセージを送信したＥＣＨとリンクする新たなＥＣＨになり、
また、前記レギュラーノードは、リンクされていないＥＣＨから少なくとも１つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に新たなＥＣＨになる、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項３】
前記レギュラーノードは、異なるネットワークに属する少なくとも２つの異なるＥＣＨノードから、少なくとも２つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に、新たなＥＣＨとなって、異なるＥＣネットワークに属する前記少なくとも２つの異なるＥＣＨノードを互いにリンクして、１つの統合されたネットワークを作成する、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項４】
ＥＣＨは、該ＥＣＨと他のＥＣＨとの間の通信リンク、および前記リンクされたＥＣネットワークに属する異なる等価セルからのレギュラーノード間の通信リンクを提供する、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項５】
前記無線通信範囲の前記エリアは、前記中心にある等価セルに加えて、多数の他の等価セル（ＥＣ）を含み、
各ＥＣは唯一のＥＣＨによって管理される、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立
および維持する方法。
【請求項６】
リンクされたＥＣＨはそれぞれ、前記リンクされたＥＣネットワーク内の他のＥＣＨノードに対する自らの相対的な位置を認識しており、
該相対的な位置は、少なくとも１つの通信中のＥＣＨノードのリストから判定され、
該少なくとも１つのＥＣＨノードのリストの各リストは、前記リンクされた等価セルネットワークの１つの通信経路に沿ったＥＣＨノードの順序を示す、
請求項５に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項７】
前記等価セルネットワークに属するＥＣＨの移動度を検出するステップと、
所定の選択判定基準に基づいて、新たなＥＣＨを選択するステップと、
をさらに含む、請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項８】
前記ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項９】
前記移動度は、新たなＥＣＨが前記ＥＣネットワークに参加すること、リンクされたＥＣＨが該ＥＣネットワークから出ること、および、リンクされたＥＣＨが同じＥＣネットワークの別のＥＣＨによって管理されるＥＣの中に移動することを含む、
請求項７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項１０】
前記複数の移動無線デバイスのうちの少なくとも１つのデバイスは、車両内に設置または内蔵される、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項１１】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステムであって、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させる手段と、
前記複数の移動中の無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信する手段と、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、前記ＥＣＨによって管理される第１の等価セルを確立する手段と、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信する手段と、
前記第２のＥＣＨが他の唯一の受信されたＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、前記第１のＥＣＨノードと前記第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成する手段と、
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、前記第１のデバイスを前記リンク等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨと比べて通信特権に制約があるレギュラーノードとして動作させる手段と、
を備える、複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１２】
前記レギュラーノードが１つのＥＣＨ＿ＨＥＬＬＯメッセージだけを受信する場合に、該受信されたＥＣＨ＿ＨＥＬＬＯメッセージを送信したＥＣＨとリンクする新たなＥＣＨになり、
また、前記レギュラーノードは、リンクされていないＥＣＨから少なくとも１つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に新たなＥＣＨになる、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１３】
前記レギュラーノードは、異なるネットワークに属する少なくとも２つの異なるリンクされたＥＣＨノードから、少なくとも２つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に、新たなＥＣＨとなって、異なるＥＣネットワークに属する前記少なくとも２つの異なるＥＣＨノードを互いにリンクし、１つの統合されたネットワークを作成する、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１４】
各ＥＣＨは、互いの間の通信リンク、および前記リンクされた等価セルネットワークに属する異なる等価セルからのレギュラーノード間の通信リンクを提供する、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１５】
前記無線通信範囲の前記エリアは、前記中心にある等価セルに加えて、多数の他の等価セルを含み、各等価セルは唯一のＥＣＨによって管理されるとともに、リンクされた等価セルネットワークを構成する、
請求項１４に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１６】
ＥＣＨは、該ＥＣＨによって管理される等価セルの相対的な位置を認識しており、
該相対的な位置は、少なくとも１つの通信中のＥＣＨのリストから判定され、
該少なくとも１つのＥＣＨのリストの各リストは、前記リンクされた等価セルネットワークの１つの通信経路に沿った通信中のＥＣＨを示す、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１７】
前記等価セルネットワークに属するＥＣＨの移動度を検出する手段と、
所定の選択判定基準に基づいて、新たなＥＣＨを選択する手段と、
をさらに含む、請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１８】
前記ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項１７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確
立するシステム。
【請求項１９】
前記複数の移動無線デバイスのうちの少なくとも１つのデバイスは、移動中の車両内に設置または内蔵される、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項２０】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体であって、前記方法は、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させること、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、該ＥＣは前記ＥＣＨによって管理される第１の等価セルを確立すること、
前記複数の移動無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信すること、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信すること、
前記第２のＥＣＨが受信された唯一の他のＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、前記第１のＥＣＨノードと前記第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成すること、
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、前記第１のデバイスを前記リンクされた等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨに比べて通信特権に制約があるレギュラーノードとして動作させること
を含む、複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体。
【請求項２１】
前記方法は、
前記等価セルネットワークに属するＥＣＨの移動度を検出するステップと、
所定の選択判定基準に基づいて、新たなＥＣＨを選択するステップと
をさらに含み、
該ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項２０に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体。
【請求項２２】
前記コンピュータ読取り可能媒体はネットワークであり、
前記命令は、該ネットワークを介して送信可能な信号である、
請求項２０に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ
読取り可能媒体。
【請求項１】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法であって、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させること、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、前記ＥＣＨによって管理される第１の等価セルを確立すること、
前記複数の移動無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信すること、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信すること、
前記第２のＥＣＨが他の唯一の受信されたＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨに属する場合には、前記第１のＥＣＨと前記第２のＥＣＨとの間にリンクされた等価セルネットワークを構成すること、および
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨに属する場合には、前記第１のデバイスを前記リンクされた等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨに比べて通信特権に制約があるレギュラーノードとして動作させること、
を含む、複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項２】
前記レギュラーノードは、１つのＥＣＨ＿ＨＥＬＬＯメッセージだけを受信する場合に、該受信されたＥＣＨ＿ＨＥＬＬＯメッセージを送信したＥＣＨとリンクする新たなＥＣＨになり、
また、前記レギュラーノードは、リンクされていないＥＣＨから少なくとも１つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に新たなＥＣＨになる、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項３】
前記レギュラーノードは、異なるネットワークに属する少なくとも２つの異なるＥＣＨノードから、少なくとも２つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に、新たなＥＣＨとなって、異なるＥＣネットワークに属する前記少なくとも２つの異なるＥＣＨノードを互いにリンクして、１つの統合されたネットワークを作成する、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項４】
ＥＣＨは、該ＥＣＨと他のＥＣＨとの間の通信リンク、および前記リンクされたＥＣネットワークに属する異なる等価セルからのレギュラーノード間の通信リンクを提供する、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項５】
前記無線通信範囲の前記エリアは、前記中心にある等価セルに加えて、多数の他の等価セル（ＥＣ）を含み、
各ＥＣは唯一のＥＣＨによって管理される、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立
および維持する方法。
【請求項６】
リンクされたＥＣＨはそれぞれ、前記リンクされたＥＣネットワーク内の他のＥＣＨノードに対する自らの相対的な位置を認識しており、
該相対的な位置は、少なくとも１つの通信中のＥＣＨノードのリストから判定され、
該少なくとも１つのＥＣＨノードのリストの各リストは、前記リンクされた等価セルネットワークの１つの通信経路に沿ったＥＣＨノードの順序を示す、
請求項５に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項７】
前記等価セルネットワークに属するＥＣＨの移動度を検出するステップと、
所定の選択判定基準に基づいて、新たなＥＣＨを選択するステップと、
をさらに含む、請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項８】
前記ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項９】
前記移動度は、新たなＥＣＨが前記ＥＣネットワークに参加すること、リンクされたＥＣＨが該ＥＣネットワークから出ること、および、リンクされたＥＣＨが同じＥＣネットワークの別のＥＣＨによって管理されるＥＣの中に移動することを含む、
請求項７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項１０】
前記複数の移動無線デバイスのうちの少なくとも１つのデバイスは、車両内に設置または内蔵される、
請求項１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立および維持する方法。
【請求項１１】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステムであって、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させる手段と、
前記複数の移動中の無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信する手段と、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、前記ＥＣＨによって管理される第１の等価セルを確立する手段と、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信する手段と、
前記第２のＥＣＨが他の唯一の受信されたＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、前記第１のＥＣＨノードと前記第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成する手段と、
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、前記第１のデバイスを前記リンク等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨと比べて通信特権に制約があるレギュラーノードとして動作させる手段と、
を備える、複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１２】
前記レギュラーノードが１つのＥＣＨ＿ＨＥＬＬＯメッセージだけを受信する場合に、該受信されたＥＣＨ＿ＨＥＬＬＯメッセージを送信したＥＣＨとリンクする新たなＥＣＨになり、
また、前記レギュラーノードは、リンクされていないＥＣＨから少なくとも１つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に新たなＥＣＨになる、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１３】
前記レギュラーノードは、異なるネットワークに属する少なくとも２つの異なるリンクされたＥＣＨノードから、少なくとも２つのＥＣＨ＿ＨＥＬＬＯメッセージを受信する場合に、新たなＥＣＨとなって、異なるＥＣネットワークに属する前記少なくとも２つの異なるＥＣＨノードを互いにリンクし、１つの統合されたネットワークを作成する、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１４】
各ＥＣＨは、互いの間の通信リンク、および前記リンクされた等価セルネットワークに属する異なる等価セルからのレギュラーノード間の通信リンクを提供する、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１５】
前記無線通信範囲の前記エリアは、前記中心にある等価セルに加えて、多数の他の等価セルを含み、各等価セルは唯一のＥＣＨによって管理されるとともに、リンクされた等価セルネットワークを構成する、
請求項１４に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１６】
ＥＣＨは、該ＥＣＨによって管理される等価セルの相対的な位置を認識しており、
該相対的な位置は、少なくとも１つの通信中のＥＣＨのリストから判定され、
該少なくとも１つのＥＣＨのリストの各リストは、前記リンクされた等価セルネットワークの１つの通信経路に沿った通信中のＥＣＨを示す、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１７】
前記等価セルネットワークに属するＥＣＨの移動度を検出する手段と、
所定の選択判定基準に基づいて、新たなＥＣＨを選択する手段と、
をさらに含む、請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項１８】
前記ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項１７に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確
立するシステム。
【請求項１９】
前記複数の移動無線デバイスのうちの少なくとも１つのデバイスは、移動中の車両内に設置または内蔵される、
請求項１１に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立するシステム。
【請求項２０】
複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体であって、前記方法は、
前記複数の移動無線デバイスのうちの第１のデバイスを、無線通信範囲を有する第１の等価セルヘッダ（ＥＣＨ）として動作させること、
前記第１のＥＣＨのための第１の等価セル（ＥＣ）であって前記第１のＥＣＨの無線通信範囲のエリア内に中心があり、かつ該エリアの一部を占めるような大きさで形成されるとともに、該ＥＣは前記ＥＣＨによって管理される第１の等価セルを確立すること、
前記複数の移動無線デバイスのうちの前記１つのデバイスが前記第１のＥＣＨであることを通知するＥＣＨ情報（ＥＣＨ＿ＨＥＬＬＯ）を、ランダムに定められた一定の間隔で前記第１のＥＣＨから送信すること、
第２のＥＣＨとして動作する少なくとも１つの第２の移動無線デバイスから送信される第２のＥＣＨ＿ＨＥＬＬＯメッセージを、前記第１の無線デバイスによって受信すること、
前記第２のＥＣＨが受信された唯一の他のＥＣＨ＿ＨＥＬＬＯメッセージである場合、または受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージがリンクされていないＥＣＨノードに属する場合には、前記第１のＥＣＨノードと前記第２のＥＣＨノードとの間にリンクされた等価セルネットワークを構成すること、
受信された２つ以上のＥＣＨ＿ＨＥＬＬＯメッセージが統合された一連のリンクされたＥＣＨノードに属する場合には、前記第１のデバイスを前記リンクされた等価セルネットワーク内のレギュラーノードであって、前記リンクされた等価セルネットワークの一部であるとともにＥＣＨに比べて通信特権に制約があるレギュラーノードとして動作させること
を含む、複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体。
【請求項２１】
前記方法は、
前記等価セルネットワークに属するＥＣＨの移動度を検出するステップと、
所定の選択判定基準に基づいて、新たなＥＣＨを選択するステップと
をさらに含み、
該ＥＣＨ選択は、レギュラーノードをＥＣＨに選択的に昇格させることによって実行され、
該レギュラーノードは、前記検出されたＥＣＨによって管理される前記等価セルに対する該レギュラーノードの位置に基づいて選択される、
請求項２０に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ読取り可能媒体。
【請求項２２】
前記コンピュータ読取り可能媒体はネットワークであり、
前記命令は、該ネットワークを介して送信可能な信号である、
請求項２０に記載の複数の移動無線デバイス間にモバイルアドホックネットワークを確立する方法を実行するための、プロセッサによって実行可能な命令を有するコンピュータ
読取り可能媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２００８−５４１５７９（Ｐ２００８−５４１５７９Ａ）
【公表日】平成２０年１１月２０日（２００８．１１．２０）
【国際特許分類】
【出願番号】特願２００８−５１０３３７（Ｐ２００８−５１０３３７）
【出願日】平成１８年１０月２７日（２００６．１０．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０４２２３９
【国際公開番号】ＷＯ２００７／０６１５７７
【国際公開日】平成１９年５月３１日（２００７．５．３１）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【Ｆターム（参考）】
【公表日】平成２０年１１月２０日（２００８．１１．２０）
【国際特許分類】
【出願日】平成１８年１０月２７日（２００６．１０．２７）
【国際出願番号】ＰＣＴ／ＵＳ２００６／０４２２３９
【国際公開番号】ＷＯ２００７／０６１５７７
【国際公開日】平成１９年５月３１日（２００７．５．３１）
【出願人】（３９９０４７９２１）テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【Ｆターム（参考）】
[ Back to top ]