JP4974901B2 - アドホック無線ピアツーピアネットワークを確立及び編成する方法 - Google Patents

Description

［発明の背景］
［発明の分野］
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、通信をほぼ瞬時に達成するために、移動デバイス間にアドホック無線ネットワークを確立及び維持することに関する。

［関連出願］
本出願は、２００５年１月１１日に出願の米国特許仮出願第６０／６４３，３７３号に関連し、その優先権を主張する。

［関連技術の記載］
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でＷｉＦｉ技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。８０２．１１ａ／ｂ／ｇのような無線ネットワーキング技術によって、ＷｉＦｉ機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。

これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、２００４年７月２９日に、ミシガン州グランドヘブンは、６平方マイルの都市を網羅し、ミシガン湖まで１５マイルにわたって広がる、都市全域の無線ネットワークを構築して、「全米最初のＷｉＦｉ都市」であるという栄誉を主張した。多数の市当局者は、ＷｉＦｉを、下水・電力・電話及び交通機関と同様に企業を誘致・維持するために不可欠なインフラストラクチャと見ている。そのようなシステムの市当局者にとっての利点は、市職員の間での通信手段を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまで多岐にわたる。

このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路及び高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。

さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが差し迫った状況に陥る前に、必要な措置を講じることができるようになる。この特徴が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが
、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更又は合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。

車両安全通信（「ＶＳＣ」）は、大きく、車車間通信とインフラストラクチャを介した車両通信とに分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。

重要なＶＳＣ性能要件には、衝突回避のような種々のＶＳＣアプリケーションを支援するために、遅延時間が短いこと（約１００ミリ秒）、及びスループットを維持すること（別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ）が含まれる。

単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。

その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。

さらに、各車両が他の車両のネットワーク構成と整合しないであろう。

移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい（すなわち、どの車両も、予めその近くにいる車両について何も知らない）。車両間安全通信を構築するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行うことができるようにしなければならない。協調しない車両の移動度が高いということは、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ（移動度、アドレス、名前、メディアセッションのための）を用いることが難しいということを意味する。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。

ホットスポットのような他の場所で利用されるＷｉＦｉ方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、３車線の高速道路の１２００メートル長当たりの車両が６００台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速３０〜６０マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。

具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両
が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。

車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、ＦｌｅｅｔＮｅｔおよびＣａｒＴａｌｋ２０００はいずれも、車車間通信ネットワークを構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でＧＰＳシステムを使用する。ＦｌｅｅｔＮｅｔは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノード及び移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費及び間接費が生じる。さらに、ＦｌｅｅｔＮｅｔシステムは、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。

ＣａｒＴａｌｋ２０００も位置に基づくプロトコルを用いる。ＣａｒＴａｌｋ２０００による車車間システムに参加する各車両は、常に現在位置を検出するために、ＧＰＳデバイスを搭載していなければならない。さらに、ＣａｒＴａｌｋ２０００は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。

ＣａｒＴａｌｋ２０００システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。

しかしながら、これらのＧＰＳネットワークは大きな欠点を有する。移動度の高い車両環境では、ＧＰＳ情報はすぐに有効でなくなる。ＧＰＳ位置ルーティングを実行するために、車両間で絶えず変化するＧＰＳ情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなＧＰＳ位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。

したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なＶＳＣ性能要件を達成することができるアドホックネットワークを構成することが必要とされている。

［発明の簡単な概要］
したがって、本発明の目的は、複数の移動デバイスをローカルピアグループ（「ＬＰＧ」）のような管理グループにグループ化することによって、移動デバイス間通信に適した通信境界を作り出し、メッセージ伝送を調整及び中継し、メッセージ伝搬の範囲及び方向を制御することである。さらに、本発明の目的は、ローカルピアグループを確立及び維持し、識別情報を動的に割り当て、移動デバイスの相対的な順序を周期的に更新するための簡単なプロトコルを提供することである。

複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法が開示される。当該方法は、複数の移動デバイスを少なくとも１つのローカルピアグル
ープ（ＬＰＧ）にグループ化するステップと、各ＬＰＧ内の複数のデバイスのそれぞれの相対的な位置に基づいて、各ＬＰＧ内の複数のデバイスを順序付けするステップと、複数の移動デバイスのそれぞれに固有の識別子を割り当てるステップとを含み、固有の識別子は、対応する移動デバイスが位置するＬＰＧに部分的に基づく。

２つのタイプのＬＰＧ、すなわち固定ＬＰＧ及び動的ＬＰＧがある。固定ＬＰＧの位置及びサイズは予め定義されており、各移動デバイスのメモリ内にプログラミングされる。動的ＬＰＧは、複数の移動デバイスのうちの１つ又は複数のクラスタリングに基づいて形成される。ネットワークは、固定ＬＰＧ及び動的ＬＰＧのいずれか又は両方を含むことができる。

各ＬＰＧは、移動デバイスのグループによって定義される等価セル（ＥＣ）に分割される。このグループ内の各移動デバイスは互いに１ホップ内に存在し、一度のメッセージ伝送のみによって、このＥＣ内のどの移動デバイスとも通信できる。各ＥＣは、等価セルヘッダ（ＥＣＨ）によって制御される。

移動デバイスの相対的な位置を更新して、複数の移動デバイスの移動によって生じる再順序付けに対処する。順序付け及び再順序付けは、各ＬＰＧ内の各移動デバイスの相対的な位置を表す位置ベクトルを作成することによって達成することができる。

位置ベクトルは、位置ベクトルを初期化し、初期化された位置ベクトルをＬＰＧに参加している別の移動デバイスに送信し、別の移動デバイスが、自身の位置を送信に含まれる位置情報と比較し、その比較に基づいて、この別の移動デバイスの位置値を位置ベクトルに挿入し、更新された位置ベクトルを、ＬＰＧ内の他の全ての移動デバイスに送信することによって生成される。

別法では、移動デバイスの順序付け及び再順序付けは、第１の移動デバイスの位置と意図したメッセージ方向の指示と送信時刻とを含むメッセージを送信し、第２の移動デバイスが、送信メッセージを受信し、受信された送信メッセージに基づいて、第１の移動デバイスの変位を推定し、推定された変位及び第１の移動デバイスの位置に基づいて第１の移動デバイスの現在の位置を計算し、計算された現在の位置と第２の移動デバイスの位置とを比較することによって達成することができる。第２の移動デバイスは、第２の移動デバイスが意図したメッセージ方向に沿っているものと判定されるときにだけ、メッセージを中継又は転送する。

移動デバイス毎の固有の識別子はＬＰＧ特有である。それゆえ、移動デバイスの固有の識別子は、移動デバイスがＬＰＧを変更するときに変更される。さらに、２つの隣接するＬＰＧの境界付近に、又は隣接するＬＰＧの重なり合うエリア内に位置する移動デバイスは、２つのＩＰアドレスを割り当てられ、隣接するＬＰＧ間で通信できるようにする。

この固有の識別子は、ＩＰアドレスであってもよい。ＩＰアドレスは、固有のＬＰＧ識別情報及び固有の移動デバイス識別情報と連結される所定のネットワークプレフィックスに基づいて割り当てることができる。固有のＬＰＧ識別情報及び固有の移動デバイス識別情報はハッシュ関数から計算することができる。別法では、固有のＬＰＧ識別情報及び固有の移動デバイス識別情報は、移動デバイスと通信している外部無線デバイスから与えることができる。

移動デバイスはそれぞれ、移動デバイスのタイプに従って分類することができ、この分類に基づいて、固有の識別子を割り当てることができる。

本発明のこれらの及び他の特徴、利益及び利点は、添付の図面を参照することによって明らかになるであろう。なお、図面を通して、類似の参照符号は類似の構造を指している。

［発明の詳細な説明］
本発明によれば、複数のノードすなわち移動デバイスが、管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて、又は固定された位置に基づいて構築される。このグループ化すなわちローカルピアグループ（「ＬＰＧ」）は、単一のＬＰＧ内や複数のＬＰＧ間での無線信号のルーティングを実施するための基礎となる。無線信号は、車両安全アプリケーションや情報アプリケーションを含む。

ＬＰＧの目的は、近くにある複数のノード間の連携（coordination）の程度を構築することである。これら近くにあるノードは、無線通信能力を有する移動デバイスである。移動無線デバイスは、ＰＤＡ、ノートパソコン、携帯電話、又は無線デバイスが取り付けられるか内蔵されている車両であってもよい。具体的には、移動デバイスには、車両内に設置されたり車両内に個別に持ち込まれたりする通信デバイスを備える車両や、通信デバイスを携帯した歩行者が含まれる。

連携の程度には、２つのタイプがある。第１のタイプは隣接する移動デバイスの密な連携であり、ＬＰＧ内通信のために用いられる。ＬＰＧ内通信は、概ね瞬時のメッセージ伝送の支援に利用される。たとえば、緊急道路障害物警告や他のタイプの緊急メッセージ又は安全メッセージの送信は、ＬＰＧ内メッセージ伝送を用いて実行されるであろう。これらのメッセージは、一般的に、遅延時間が１００ｍｓｅｃ程度であることを要求する。

第２のタイプは、緩やかな連携、すなわち近くにある移動デバイスをグループ化することである。このタイプの連携は、リンク又は相互接続されているＬＰＧ間のＬＰＧ間通信を支援するために用いられる。たとえば、ＬＰＧ間通信は、道路認識アプリケーションや、ドライバの視界拡張のために用いることができる。

ＬＰＧは、効率的且つ信頼性のある移動デバイス間通信を支援するだけでなく、移動デバイス及び道路インフラストラクチャを、１つの完全な通信ネットワークとして統合できるように、移動デバイスと固定インフラストラクチャ間の通信も支援することができる。

図１は２つのＬＰＧを示しており、第１のＬＰＧ１００は、４つのノード１１０、１１１、１１２及び１１３を含む。これら４つのノード１１０、１１１、１１２及び１１３はそれぞれ、互いにデータを送信することができる。第２のＬＰＧ１２０は、ノード１２１、１２２、１２３、１２４、１２５及び１２６を含む。ノード１２１〜１２６はそれぞれ、互いにデータを送信することができる。このタイプの伝送は、ＬＰＧ内伝送であり、瞬時に行われる。ＬＰＧ１００内のノード１１０〜１１３は、ＬＰＧ間通信を用いることによって、ＬＰＧ１２０内のノード１２１〜１２６にデータを送信することができる。２つのＬＰＧ１００、１２０は、アドホックネットワーク１５０を形成する。

ＬＰＧには２つのタイプ、すなわち固定ＬＰＧ及び動的ＬＰＧがある。固定ＬＰＧは、予め割り当てられたグループ位置定義を用いて、移動デバイスを分割する。対照的に、動的ＬＰＧは、近くにある移動デバイスが通信するための（動的な）無線通信エリアに基づいて、移動デバイスを適当に組み合わせることができる。

図２は、複数の固定ＬＰＧ（ＬＰＧ１〜８）２００〜２０７を示す。各ＬＰＧは、特定
の位置又はエリアによって画定される。すなわち無線デバイス又は移動デバイスがエリア１内にある場合には、そのデバイスはＬＰＧ１である。無線デバイス又は移動デバイスがエリア２内にある場合には、そのデバイスはＬＰＧ２であり、他も同様である。固定ＬＰＧの個々のサイズは設計上の選択事項であり、種々の要因、たとえば無線アンテナの範囲、通信範囲、移動デバイスの数、地形、環境条件、交通パターン及び人口密度にしたがって決められる。固定ＬＰＧの位置及びサイズは固定であるが、交通パターン及び人口（移動デバイス）密度は場所によって異なるので、各固定ＬＰＧは異なるサイズであっても良い。一般的には、ＬＰＧサイズを、無線通信範囲よりも大きくして、マルチホップ通信できるようにすべきである。さらに、効率的なＬＰＧ間通信を容易にするために、固定ＬＰＧは、隣接するＬＰＧ間のエリアと重なり合うこともできる。重なり合うエリアは、変化に富んだ状況（たとえば移動デバイスによって速度が異なること）に適応するために、状況に合わせたサイズを有することができる。

本発明の一実施形態によれば、固定ＬＰＧのための境界は、郵便番号や市外局番のような所定のエリアに基づく。通常、郵便番号は人口密度に相当する。或るエリアの人口密度は、そのエリア内の交通パターンや移動デバイスの数の良好な指標である。

固定ＬＰＧに基づくネットワークアーキテクチャでは、移動デバイスが、全地球測位システム（ＧＰＳ）又は他の何らかの位置情報を備える必要がある。これにより、移動デバイスは、その移動デバイスが属する固定ＬＰＧを特定又は検出できるようになる。移動デバイスは、位置を変更するのに応じて、固定ＬＰＧを変更する。それゆえ、移動デバイスは、更新された位置データを周期的に受信する必要がある。この周期は、移動デバイスが移動する速さ又は速度に依存する。移動デバイスは、ＬＰＧ及びそれらの位置のデータベースを含む。

固定ＬＰＧは、いくつかのＬＰＧが空であったり、ＬＰＧ内に多数の移動デバイスがないときであっても、無線インフラストラクチャと統合して、バックボーンアクセスやＬＰＧ間通信を提供できるという大きな利点を有する。

各固定ＬＰＧは、通信を容易にするために、固有の識別子を割り当てられる。本発明の一実施形態では、固定ＬＰＧのための固有の識別子は、そのＬＰＧの郵便番号に基づいて割り当てられる。この方法は、既存の郵便番号データベースを活用する。したがって、新たな識別番号を作成する必要はない。別法として、別の実施形態では、固定ＬＰＧのＧＰＳ座標を用いることができる。同じように、その方法は、あらかじめ定められたデータベースを利用する。別の実施形態では、ＬＰＧの固有の識別子として、州名及び都市名を用いることができる。別法では、上記の実施形態の任意の組み合わせを用いて、ＬＰＧ固有の識別子を割り当てることができる。ＬＰＧの固有の識別子は、後に説明されるように、移動デバイスの固有の識別子の一部として用いられる。

全ての固定ＬＰＧエリアは明確であるので、ＬＰＧを形成及び命名するのは、動的ＬＰＧよりも容易である。さらに、固定ＬＰＧを用いるとき、ＬＰＧの合併や分割に関するルールを心配する必要はない。

図３は、複数の動的ＬＰＧ（ＬＰＧ Ａ〜Ｅ）、それぞれ３００〜３０４を示す。固定ＬＰＧとは対照的に、動的ＬＰＧは、移動デバイスがその厳密な位置を気にすることなく通信を連携できるように、近くにある移動デバイスの無線通信エリアに基づいて形成される。

動的ＬＰＧは無線通信エリアに基づいて形成されるので、そのＬＰＧ内の移動デバイスは常に、１ホップ又はマルチホップの伝送を介して、互いに通信することができる。各Ｌ
ＰＧ内の移動デバイスの数を適度に少なく保持し、通信を短い遅延で効率的に実行できるようにするために、移動デバイスは動的ＬＰＧのサイズを制御することができる。さらに、固定ＬＰＧとは対照的に、動的ＬＰＧは、各ＬＰＧ内で常に通信が可能であることを保証する。

一実施形態では、アドホックピアツーピアネットワークを、１つ又は複数の固定ＬＰＧから構築することができるし、１つ又は複数の動的ＬＰＧから構築することもできる。別の実施形態では、アドホックピアツーピアネットワークは、固定ＬＰＧ及び動的ＬＰＧの両方から、ハイブリッドＬＰＧネットワークとして構築することができる。ハイブリッドＬＰＧネットワークは、固定ＬＰＧ及び動的ＬＰＧを別個に採用した場合に生じる問題を取り除きながら、それぞれの利点を兼ね備える。

固定ＬＰＧの利点のうちの１つは、エリアによって移動デバイスを容易にグループ化することができること、及びインフラストラクチャとやりとりできることである。さらに、後で詳細に説明されるように、固定ＬＰＧによれば、移動デバイス毎にアドレス指定用識別子すなわち固有の識別子を簡単に割り当てることができるようになる。さらに、全てのノードが、ネットワーク全体のトポロジ及び構造を把握している。それゆえ、ノード又は移動デバイスを容易に追跡することができる。

動的ＬＰＧにはいくつかの利点がある。それらの利点のうちの１つは、ネットワークがノードのクラスタリングに基づいて形成されるので、動的ＬＰＧは事前の設定が必要ないことである。さらに、動的ＬＰＧは、ＬＰＧの形成や合併、分割をより自由に行うことができ、一度形成されると、全ての車両が一斉に通信することができる。それゆえ、近くにある移動デバイス間での通信がさらに容易である。

固定ＬＰＧの欠点は、より広くに遍在する路側無線アクセスポイント、路側ゲートウエイ、路側データ記憶装置（入力（deposit）及び検索用）を必要とすることであり、動的ＬＰＧの場合に不要であるのとは対照的である。

ハイブリッド手法は、道路の敷設状況（topology）を利用する。具体的には、インフラストラクチャが利用できないとき、動的ＬＰＧを用いて、ネットワークが形成される。或るエリアにおいて、インフラストラクチャを利用できるようになるとき、固定ＬＰＧを用いて、動的ＬＰＧ及びインフラストラクチャとともにネットワークを形成することができる。

たとえば、道路インフラストラクチャのようなインフラストラクチャによって、路車間通信及び道路支援（車路車間）通信を実現できるようになる。これは、固定ＬＰＧを用いるときに特に有用である。さらに、道路インフラストラクチャは、インフラストラクチャから車両への通信を容易にする。このタイプの通信は、隠れた私道に対する警告、電子道路標識、路面条件、踏切警告、経路案内及びナビゲーション、ハイウエイ合流支援、交差点衝突警告、及び工事区間警告等の、特定の緊急情報を行き渡らせるために重要である。

ＬＰＧには主に２つの種類がある。１つは順序付けされないＬＰＧであり、もう１つは相対的に順序付けされるＬＰＧである。相対的に順序付けされるＬＰＧでは、移動デバイスのうちの少なくともいくつかが、近くにある移動デバイスの相対的な位置を認識する。相対的な順序付けは、ＬＰＧ内でメッセージをルーティングするための基礎である。近くにある移動デバイスの相対的な順序や相対的な方向を検出・認識できると、ＬＰＧ環境内でのメッセージルーティングを効率的に行えるようになる。この効率的なルーティングは、メッセージが道路環境における緊急メッセージであるときに重要である。たとえば、或る車両によって、警告メッセージがＬＰＧの後方に進むように指定されることがある。Ｌ
ＰＧにおいて送信する車両の前方にある車両は、そのメッセージを受信又は中継する必要はない。その車両は相対的な方向がわかるので、適当な方向に向かってメッセージを誘導し、それにより、中継トラフィック及び使用される帯域幅の量を削減することができる。

方向の検出又は認識は、移動デバイスの相対的な順序から導出することができる。一実施形態では、相対的な順序付けは、「必要に応じて（on-demand）」行われる。別の実施形態では、相対的な順序付けは周期的に維持される。

図４は、本発明の一実施形態による、「必要に応じて」ＬＰＧを順序付けする方法を示す。その過程は、ステップ４００において開始する。第１の移動デバイスが。その移動デバイスのＧＰＳ位置、現在の速度及びタイムスタンプを含むメッセージを、意図したメッセージ方向とともに送信する。ステップ４１０では、第２の移動デバイスがこのメッセージを受信する。ステップ４２０において、第２の移動デバイスは、第１の移動デバイスの現在の位置を推定する。第１の移動デバイスの現在の位置の推定は、既にわかっている第１の移動デバイスの以前の位置からの第１の移動デバイスの起こり得る変位に基づいて行うことができる。以前の位置は、受信されたメッセージから直に求められる。起こり得る変位は、推定された速度及び時間差に基づいて計算される。受信されたメッセージはタイムスタンプを含むので、第２の移動デバイスは時刻、すなわちそのタイムスタンプから、メッセージが受信された時刻までの差を計算する。この場合、それらの移動デバイスにおいて、クロック及びＧＰＳ情報の両方の時間が同期している、すなわちＧＰＳデバイスが同期している必要がある。推定速度は、いくつかの異なる態様で計算することができる。一実施形態では、第１の移動デバイスの（瞬間）速度は、第１の移動デバイスによって送出されるメッセージに含まれる。この速度は、第２の移動デバイスが第１の移動デバイスの現在の速度を推定する際に用いることができる。別の実施形態では、第２の移動デバイスは、第１の移動デバイスの速度として自らの速度を用いることができる。別法では、予め決定された推定速度を用いることができる。予め決定された推定速度は、制限速度、時刻、場所、気象条件及び地形に基づいて変わることがあるデータベースとして、移動デバイスのメモリ内に予め格納されるであろう。第２の移動デバイスは、推定速度と、時間差とを乗算して、起こり得る変位を求める。この値は、以前の位置からの起こり得る変位であり、第１の移動デバイスの以前の位置を調整して、第１の移動デバイスの推定位置を求めるために用いられる。

本発明の一実施形態では、第１の移動デバイスの変位は、向きの成分を有する。この実施形態では、推定される変位は、向きの変化を考慮に入れる。第１の移動デバイスの以前の位置に、位置の変化が移動方向に対して加えられる。一実施形態では、第１の移動デバイスは、そのメッセージ内にＧＰＳの向き（たとえば、ＮＷ、ＳＥ３５°）を（その位置、タイムスタンプ等とともに）含むことができ、この向きの情報が、厳密な変位を推定するために、第２の移動デバイスによって用いられる。別法として、別の実施形態では、第２の移動デバイスが、局所的な地形情報を利用することによって、（第１の移動デバイスが、向きの情報を送信することなく）第１の移動デバイスの向きを推定することができる。すなわち、両方の移動デバイスが同じ道路に沿って進行していることがあるので、それを利用して第１の移動デバイスの向きを推定する。それゆえ、第２の移動デバイスは、計算された変位を、（第１の移動デバイスの）以前の位置に、第２の移動デバイスが移動している方向に対して加えることができる。

ステップ４３０では、第２の移動デバイスが、第１の移動デバイスの計算された推定位置と、自ノードの現在の位置とを比較して、２つの移動デバイスの相対的な順序を決定する。

第２の移動デバイスは、自ノードが意図されたメッセージ方向にあるものと判定される
ときにだけ、そのメッセージを中継又は転送する。自ノードの位置及び向きが送信側の移動デバイスと受信側の移動デバイスとの間にある場合には、移動デバイスは意図したメッセージ方向に沿っている。具体的には、第２の移動デバイスは、計算された相対的な順序又は位置を用いて、第２の移動デバイスが意図された経路に沿っているか否かを判定する。

一実施形態では、向きの情報を用いて、第２の移動デバイスが意図した経路に沿っているか否かが判定される。この向きの情報は、上記のように、第１の移動デバイスの推定される位置を導出するために、第２の移動デバイスによって用いられる。上記のように２つの移動デバイス間の相対的な序列が決定されると、第２の移動デバイスは、第１の移動デバイスのメッセージに含まれる第１の移動デバイスの向きと、自らの向きとを用いることによって、第２の移動デバイスが第１の移動デバイスの意図したメッセージ伝送の経路上にあるか否かを判定することができる。たとえば、両方の移動デバイスが類似の向きを有し（すなわち同じ道路に沿って進行しており）、第２の移動デバイスが第１の移動デバイスの前方にある（その相対的な順序によって判定される）場合、意図されたメッセージの方向が同じ向きに沿っているときには、第２の移動デバイスがその（第１の移動デバイスの）メッセージを転送するのに対して、意図されたメッセージの方向が反対の向きを有するときには、第２の移動デバイスはそのメッセージを転送しない。第１の移動デバイスがその向きの情報をメッセージとして送信しない別の実施形態では、第２の移動デバイスは、上記のように、たとえば、以前の位置に対する変位を推定することによって、第１の移動デバイスの向きを推定することができる。２つの移動デバイスの向き及び相対的な順序がわかると、第２の移動デバイスは、先に説明されたのと同じようにして、第２の移動デバイスが第１のデバイスの意図したメッセージ伝送の経路に沿っているか否かを判定することができる。

第２の移動デバイスがその経路内に存在しない場合には、そのメッセージは転送されない。本実施形態による移動デバイスの順序付けは、移動デバイスの順序付けが重要でないときに、帯域幅が順序付け要求で輻輳しないという利点を有する。

本発明の別の実施形態では、移動デバイスの相対的な順序は、位置ベクトルを用いて周期的に更新される。図５は、この方法を用いてＬＰＧを順序付けする一例を示す。図５は、ＬＰＧ５００を、ＬＰＧ位置ベクトルＶ５１０とともに示す。ＬＰＧは、一次元のアレイすなわちベクトルＶ５１０にマッピングされる。ＬＰＧ５００の各移動デバイスは１つのベクトルＩＤを有することになる。ベクトルＩＤはまさに、Ｖの位置インデックスである。図５に示されるように、ベクトルＶ５１０は、移動デバイスの位置の順序を表す。図５では、６つの異なる相対的な順序１〜６が存在する。その矢印は、移動デバイスの移動方向、たとえば、交通の流れを示す。

位置ベクトルＶ５１０によって、移動デバイスは、情報伝送の方向を制御できるようになる。詳細には、位置ベクトルＶ５１０を用いて、ピアグループ内で情報をルーティングすることができる。たとえば、図５に示されるように、インデックス３を有する送信側の移動デバイスが、そのメッセージが３よりも小さなインデックスを有する移動デバイスに向けられていることを指示する場合には、インデックスｊ＜３を有する移動デバイスだけが、そのメッセージを中継する。これは、そのメッセージがｊより小さいインデックスを有する車両に向けられていることを指示することによって達成される。その中継は、そのメッセージがＬＰＧの後方境界ノードに達するまで、又はそのメッセージが最大ホップ数に達するまで続く。同じようにして、前方への情報伝搬を達成することができる。

さらに、位置ベクトルＶ５１０を用いることによって、ルーティング優先度を促進することもできる。ＭＡＣ層は、この位置ベクトル５１０に基づいて、アクセス優先度を生成
することができる。一般的に、そのネットワークでは、前方にある移動デバイスが警告事象を観測し、より高い優先度で無線チャネルを使用するに値する可能性が高いので、より低い位置インデックスを有する移動デバイス（ＬＰＧの前方部分にある移動デバイス）に、より高いアクセス優先度が与えられる。

図６は、本発明の一実施形態による、位置ベクトルＶ５１０を作成する方法を示す。その過程は、ステップ６００において、移動デバイス、たとえばノードＮがＬＰＧに参加するときに、位置インデックスＩを初期化することによって開始する。ノードＮが、既にＬＰＧ内にある少なくとも１つの他の移動デバイス（たとえばノードＬ）からメッセージを受信することにより、このノードと接触する。ステップ６０２において、ノードＮは、ノードＬのＧＰＳ位置を含む受信メッセージに基づいて、ノードＬの位置を知る。ノードＮは、受信した位置情報と、自らのＧＰＳ情報とを比較し、その比較に基づいて、ベクトルＶ５１０の中に自らを挿入する。その後、ノードＮは、ＬＰＧ内の他の移動デバイス（たとえばノードＬ）に、新たな位置ベクトルＶ５１０を送信する。たとえば、ノードＮがノードＬの前方にあり、ノードＬがＮのインデックスを有する前方端位置であった場合には、ステップ６０５において、ノードＮは自らに、その位置インデックスとしてＮ−１の値を割り当て、ＬＰＧの新たな前方端になる。一方、ノードＮがノードＬの後方にあり、Ｌがｎの指標を有する後方端位置である場合には、ステップ６１０において、ノードＮは自らに、その位置インデックスとしてＮ＋１の値を割り当て、その後方端位置を引き継ぐ。

ｎのインデックスを有する移動デバイス（たとえばノードＬ）が前方端でも後方端でもない場合には、ノードＮはＬＰＧの中央に参加している。その際、ノードＮは、上述したように、ステップ６１５において、ＧＰＳとノードＬとを比較することによって、自らを位置Ｖの中に挿入し、その後、ステップ６２０において、挿入点の後方にある全ての移動デバイスのインデックスの更新をトリガする。その際、挿入点の後方にある他のノードは、そのＧＰＳ位置の変化に基づいて、その位置インデックスを更新する。

別法では、新たなノード又は移動デバイスの挿入時に他の移動デバイスの更新を自動的にトリガする代わりに、新たな移動デバイスはインデックスｎ＋１を割り当てられ、ｎよりも大きな指標を有する全ての移動デバイスが、それらの指標を１だけインクリメントする。

位置ベクトルＶ５１０を自動的に更新したりインクリメントしたりすることに対する別の代替形態は、所定の位置インターバル内にある他の移動デバイスをインクリメントすることである。これは、インデックス更新の頻度を削減するであろう。中央に参加するノードＮは、ｎとｎ＋Ｋとの間の値のインターバルから得られるインデックスを割り当てられ、ｎ＋Ｋよりも大きな位置を有する移動デバイスのインデックスをインクリメントする必要はない。このインターバル（ｎ〜ｎ＋ｋ）の中にある移動デバイスだけが、それらの位置インデックスを更新する必要がある。

さらに、ＬＰＧ内の移動デバイスの相対的な順序を維持するために、すなわち、移動デバイスがＬＰＧに参加したときに、位置ベクトルＶ５１０を更新することができる。各移動デバイスは、その位置インデックスを周期的に更新することができる。ＬＰＧ内の移動デバイスの位置インデックス（ｉ）は、位置ベクトルＶ５１０がＬＰＧ内の移動デバイスの現在の相対的な位置を含むように維持することができる。詳細には、移動デバイスがすれ違って相対的な位置を変わるときに、位置インデックスを更新することができる。移動デバイスの位置インデックスは、２つの移動デバイスがその相対的な位置を入れ替えるときに入れ替えられる。たとえば、周期的なインターバルで、移動デバイスは、そのＧＰＳ位置を交換又は送信し、それらの相対的な位置が入れ替わった場合には、位置インデックスを入れ替える。その周期は、ネットワークのタイプ、地形、時刻、交通パターン及びメ
ッセージのタイプ、又はＬＰＧの位置に基づいて調整することができる。たとえば、移動デバイスが出口／入口ランプ又は交差点の周囲にあるときに、更新の頻度が高くなり、出口／入口ランプ間又は交差点間にあるときに更新の頻度が小さくなる。更新インターバルを大きくすることによって、順序付けの整合性を維持するためのオーバーヘッドを削減することができる。

しかしながら、ＧＰＳ又は位置情報の交換は、道路環境において特に欠点を有する。具体的には、ＬＰＧ内の移動デバイスの数によって、（相対的な位置の変化に追従し続けようとして）大量のＧＰＳ座標が絶えず通信されることになる。さらに、ＧＰＳ座標の誤差が移動デバイスの離隔距離と同じ桁になる可能性があるので、結果として行われる位置計算が十分に正確でないことがある。さらに、上記の方法は、大量の計算を必要とし、一般的に、ＧＰＳ情報は、他の移動デバイスがそれらの情報を受信するときに既に古くなっている。

別の実施形態では、移動デバイスの相対的な順序を、ＧＰＳ情報を用いることなく、メッセージ及び位置ベクトルを用いることによって求めることができる。上記のように、ＧＰＳ手法を用いて順序付けを維持することは、著しいオーバーヘッドを被ることがあり、移動デバイスの数が多くなる場合には特にそうである。この実施形態では、ＬＰＧが、いくつかの小さなグループ、すなわち等価セル（ＥＣ）に分割される。各ＥＣは、１つの位置インデックスを割り当てられる。ＥＣは、同じ無線通信エリア内にある、近接する移動デバイスのグループである。ＥＣは、そのＥＣ内の全ての移動デバイスが同じベクトル指標を有するＬＰＧの１つのセグメントであり、メッセージ伝送は中継を要せずにＥＣ内の全ての移動デバイスで受信することができる。

ＥＣを基本ユニットとして用いて情報を広めるために、ＥＣは他のＥＣとリンクするように形成される。図７は、ＬＰＧ７００内の複数のＥＣ（ＥＣ１〜５）７０１〜７０５を示す。ＥＣ７０１〜７０５は、ＬＰＧ７００内に、無線通信エリアが重なり合うように配置することができる。図７に示されるネットワークでは、ＬＰＧの相対的な順序がＥＣ間で維持され、オーバーヘッドを低減する。さらに、ＥＣ当たり一度だけメッセージが中継され、帯域効率を改善する。

たとえば、１つのＥＣ内の移動デバイス間は、１回のパケット伝送で通信できる。各ＥＣは、必要に応じて、ＥＣ内のいくつかの移動デバイスがパケットを中継することができるように編成される。ＥＣはＬＰＧ内で順序付けすることができ、メッセージがＥＣに沿ってホップできるようにする。具体的には、ＥＣ３ ７０３内の１つの移動デバイスがパケットを送信したい場合には、その移動デバイスはパケットを（一度だけ）隣接するＥＣ２ ７０２及びＥＣ４ ７０４に送信する。これにより、ＥＣ２ ７０２及びＥＣ４ ７０４内の全ての移動デバイスにパケットが確実に届けられる。このパケットは、ＥＣ２ ７０２及びＥＣ４ ７０４によって、それらの個々の隣接するＥＣに、ＥＣ当たり１パケットだけ中継される。このタイプの、隣接セル当たり１パケットだけ行われる隣接ＥＣ間ルーティングは、ＬＰＧ内のパケット伝送を最小限に抑えることができる。

ＥＣは、１つの等価セルヘッダ（ＥＣＨ）によって維持及び制御される。各ＥＣＨ７１１〜７１５は、その隣接するＥＣＨとリンクされ、ＬＰＧ内の全てのＥＣＨ７１１〜７１５が、直接又は間接のいずれかによって、シリアルにリンクされるようになる。ＥＣＨ７１１〜７１５は、無線ホップカウントの順序で接続され、そのＬＰＧのための転送ノードを務める。ＥＣＨ７１１〜７１５だけがメッセージを中継するための役割を担い、それにより、不要なトラフィックが最小限に抑えられる。

この実施形態では、ＥＣＨは自らを順序付けし、それらの順序を維持して、ＬＰＧのた
めの順序付けを達成する。各ＥＣＨは、予め規定されたメッセージを送信することによって、そのＬＰＧ内で自らの存在を通知する。このメッセージは周期的に送信され、リンクされたＥＣＨのリストを通知する。すなわち、このメッセージは、送信するＥＣＨから見た位置順序の１ホップ先、２ホップ先、３ホップ先のＥＣＨノードを含む。そのリストは、他のＥＣＨによって受信され、それにより、他のＥＣＨは、自らのリストを更新し、そのリストをメモリに格納する。非ＥＣＨ７２０も自らのリストを更新する。これにより、全てのＥＣＨリストが互いに一致するようになる。そのリストは、各ＥＣＨの相対的な順序を表す。これは、移動の方向及び伝送の方向の判定を容易にする。

一実施形態では、送信メッセージは、メッセージを発信する発信元のＩＤと、順序付けして接続されるＥＣの第１の通信経路に沿って発信元が見ることができるＥＣＨノードの第１のリストと、オプションで、順序付けして接続されるＥＣの第２の通信経路に沿った第２のリストとを含む。さらに別のリストが提供されることもあり、各リンクＥＣＨ（ＬＥＣＨ）リストは、発信元ＥＣＨを中心にして、順序付けして接続されるＥＣの１つのブランチ、すなわち通信経路に沿って出会う全てのＥＣＨノードのＥＣＨ ＩＤを含む。

たとえば、各ＥＣＨは、その直に隣接するＥＣＨの相対的な位置を知っている。すなわちＥＣ３ ７０３のＥＣＨは、ＥＣ２ ７０２及びＥＣ４ ７０４のＥＣＨによってそれぞれ送信されるリスト又はベクトルに基づいて、ＥＣ２ ７０２及びＥＣ４ ７０４のＥＣＨが異なる方向にあることがわかっている。ＥＣ３ ７０３のＥＣＨは、この情報を含むメッセージを送信する。さらに、ＥＣ２ ７０２のＥＣＨは、ＥＣ１ ７０１及びＥＣ３ ７０３のＥＣＨによってそれぞれ送信されるリスト又はベクトルに基づいて、ＥＣ１
７０１及びＥＣ３ ７０３のＥＣＨが異なる方向にあることがわかっている。この情報が組み合わせられ、各ＥＣＨが維持するリストとして格納される。

その結果、ＥＣＨの相対的な順序を用いることによって、ＧＰＳ情報を全く用いることなく、適当な方向にメッセージをルーティングすることができる。

別法として、別の実施形態では、全ての移動デバイスが、重要な方向（たとえば、前、後、左及び右並びに取り得る斜めの方向）への指向性アンテナを備えており、これらの方向における他の移動デバイスの存在を検出することができる。任意の移動デバイスが、メッセージがピアグループの後方に向かって進んでいくように指示することができ、その後方を指している指向性アンテナにおいてのみメッセージを送信し、このメッセージを受信する移動デバイスは、その後方を指しているアンテナにおいてのみ中継することができる。この手法は、基本的な方向検出を提供するが、移動デバイス間の相対的な位置を提供しない。

本発明による移動デバイスは、その移動デバイスに取り付けられるか、内蔵されるか、又はそれと組み合わせて用いられる無線デバイスを含む。図８は、本発明による無線デバイスを示す。本発明による無線デバイスは、無線通信範囲内のノード間での無線通信を提供するために、無線トランシーバのような送信手段８０２を有するコンピューティングデバイス８００を含む。さらに、制御手段８０４、たとえばマイクロコントローラ、マイクロプロセッサ等が、送信手段８０２を通して他のノードから信号を受信するとともに、送信手段８０２を通して他のノードに信号を送信するように構成される。また制御手段８０４は、命令を実行することによって、動作制御も提供する。記憶手段８０６が、コンピューティングデバイス８００内に配置され、制御手段８０４と動作可能に通信する。記憶手段８０６として、メモリモジュール、取外し可能媒体、多数の記憶デバイスの組み合わせ等を用いることができ、その記憶手段は、上記の実施形態のプロトコルを実行するために必要とされるプロセッサ実行可能命令を格納するだけの容量を有する。さらに、タイミング手段８０８が、別個の構成要素として、又は制御手段８０４の１つの機能によって設け
られる。タイミング手段８０８は、上記の実施形態において参照された各タイマに必要とされる、時間インターバルの追跡を提供する。必要に応じて構成要素に動作電力を供給するために、電源のような電圧供給手段８１０が、コンピューティングデバイス８００の全ての構成要素に電気的に接続される。その無線デバイスは、無線デバイスのためのクロックを維持する内部クロックをさらに備え、全てのメッセージのためのタイムスタンプとして用いられる。さらに、その無線デバイスは、アドレス割当て手段８１２と、ネットワークインターフェース手段８１４とを備える。別法では、アドレス割当て手段８１２は、制御手段８０４の一部にすることができる。

上記の実施形態を実行するためのプロセッサ実行可能命令は、ＥＰＲＯＭ、フラッシュメモリ、又は他のそのような不揮発性記憶装置の形をとる記憶手段８０６に内蔵することができる。さらに、プロセッサ実行可能命令は、光媒体又は磁気媒体のようなコンピュータ読取り可能媒体上に格納することができるか、又はネットワーク（たとえば、インターネット）を介してダウンロードすることができる。ユーザは、必要に応じて、システムをさらに強化するために、利用可能になり次第プロセッサ実行可能命令を定期的に更新できることが好ましい。

各移動デバイスは、固有の識別子を割り当てられ、アドホックネットワークを介してメッセージを送信及び受信するのを容易にするであろう。固有の識別子は、１つのＬＰＧ内の移動デバイスが同じ固有の識別子を割り当てられないように、移動デバイスに固有に割り当てられる任意の番号を用いることができる。この識別子は、即時通信に対応するために、必要に応じて、迅速に割り当てられなければならない。上記のように、固有の識別子は、ＭＡＣアドレス、ＶＩＮ番号又はＩＰアドレスのような、通信を容易にする任意の番号又はアドレスを用いることができるが、ここでは例示を目的として、ＩＰアドレスの割当てについて説明する。通常、移動デバイスは少なくとも１つのＩＰアドレスを有する。しかしながら、一実施形態では、ＬＰＧ内通信及びＬＰＧ間通信の両方に対応するために、移動デバイスに２つのＩＰアドレスが割り当てられる。

好ましい実施形態では、ＩＰアドレスは、専用のネットワークプレフィックス、ＬＰＧの固有の識別子及び移動デバイスの識別情報に基づく。具体的には、ＩＰアドレスは、特定の移動デバイスに対応する固有の番号に所定のネットワークプレフィックスを連結したものに基づいて割り当てることができる。ここで、固有の番号は、移動デバイスが存在するＬＰＧ、及びその移動デバイスに対応する番号に基づく。

固定ＬＰＧ及び動的ＬＰＧの両方に対してアドレスを割り当てるために、類似の割当て技法を用いることができるが、アドレスの割当てを、ＬＰＧのタイプ毎に個別に説明する。

固定ＬＰＧの場合、本発明の一実施形態では、ＩＰアドレスは、ＭＡＣアドレス及びＶＩＮ番号又は時刻のハッシュ値と連結される標準的なネットワークプレフィックス及びＬＰＧ ＩＤであってもよい。ハッシュ関数の使用は、アドレス空間に限りがある場合、すなわちＩＰｖ４の場合に特に重要である。この実施形態によれば、移動デバイスは、その自らのＩＰアドレスを割り当てるであろう。

理想的な状況では、ＬＰＧは、アドレス空間の制約が実質的に問題にならないように、Ｎ個（Ｎは最大アドレス空間）の移動デバイスだけを有する。これにより、ＬＰＧ毎にプライベートクラスを簡単に割り当てることができるようになる。ＬＰＧ内の各移動デバイスは、ＩＰアドレスの異なる下位部分を有する。このＩＰアドレスは、ＬＰＧが互いに接近していない限り、異なるＬＰＧにおいて再利用することができる。

しかしながら、典型的には、ＬＰＧはＮ個の移動デバイスよりも多くなることがある。したがって、所定のハッシュ関数が、移動デバイスのメモリセクションに格納されるで。アドレス割当て手段８１２は、メモリからのこの所定のハッシュ関数にアクセスして、ＩＰアドレスの下位部分を割り当てる。ハッシュ関数は、複数の入力番号を、Ｍビット（ＭはＩＰアドレスの下位部分のビットの最大数）の番号に変換する。その複数の入力番号は、ＶＩＮ番号、ＭＡＣアドレス及び移動デバイスがＬＰＧに参加した時刻を含むことができる。

標準的なネットワークプレフィックスは、ＩＰアドレスの上位部分である。標準的なネットワークプレフィックスもメモリに格納される。さらに、ＩＰアドレスはＬＰＧ特有である。ＩＰアドレスの一部を用いて、移動デバイスが位置する特定のＬＰＧが特定される。ＬＰＧの位置及び関連するＬＰＧ ＩＤのデータベースもメモリに格納される。移動デバイスが新たなＬＰＧエリアに入るとき、移動デバイスは、そのＩＰアドレスを変更して、そのＬＰＧに関連付けられる特定のＩＰアドレスを反映しなければならない。固定ＬＰＧの利点は、ＬＰＧ位置が固定されており、明確であることである。これにより、ＬＰＧ
ＩＤを簡単に付与できるようになる。

別法では、本発明の別の実施形態において、ＩＰアドレスの一部又はアドレス全体が、ＬＰＧ内の固定無線デバイスによって割り当てられることができる。たとえば、ＩＰアドレスの一部は、移動デバイスがＬＰＧに入ったシーケンス又は順序を表すことができる。この場合、入ってくる移動デバイスに対してシーケンス番号を送信する外部無線デバイスが必要となる。問い合わせ−中継−応答タイプの動作を通して、接続を確立することができる。新たな移動デバイスがＬＰＧに入るとき、その移動デバイスは（送信を通して）問い合わせを行う。その問い合わせは、ＬＰＧ内の他の移動デバイスによって、所定の外部無線デバイスまで中継される。その外部無線デバイスは、路側ゲートウエイデバイス、リーダのような別の移動デバイス、又はＬＰＧ内の第１の移動デバイスを含むことができる。外部無線デバイスは、ＤＨＣＰサーバとしての役割を果たす。

外部無線デバイスは、シーケンス番号又はＩＰアドレスを生成し、応答を送信することによって問い合わせに応答する。このシーケンス番号は、ハッシュ値の代わりに、ＩＰアドレスの下位部分として用いられる。シーケンス番号は、先に述べられたように、ＩＰアドレスの上位部分と連結される。この方法を用いると、ＩＰアドレスは、移動デバイスが絶えず動く結果としてシーケンスが変更されるときに、連続して変化する可能性がある。別法では、アドレス全体を、ＬＰＧに入る移動デバイスに送信することができる。

本発明の別の実施形態では、ＩＰプロトコルが広範なＩＰアドレスに対応する場合には、ＩＰアドレスは、全ＭＡＣアドレス又はＶＩＮ番号と連結される標準的なネットワーク識別子であってもよい。たとえば、ＩＰｖ６プロトコルを用いるとき、ハッシュ関数を必要とすることなく、固有のアドレスを各移動デバイスに割り当てるための大量の空間が存在する。ＩＰアドレスの上位６４ビットはＬＰＧ ＩＤ専用にすることができ、下位のＥＵＩ６４ビットは、ＭＡＣアドレス又はＶＩＮ番号から直に計算することができる。

ＩＰアドレスの上位部分は、標準的なネットワークプレフィックス及び固有のＬＰＧ ＩＤを含むことができる。下位のＥＵＩ部分は、ＭＡＣアドレス又はＶＩＮ番号のそれぞれを含む。

図９は、ＩＰｖ４プロトコルに従ってＩＰアドレスを割り当てる一例を示す。図９は、４つの重なり合うＬＰＧ、ＬＰＧ１ ９０１、ＬＰＧ２ ９０２、ＬＰＧ３ ９０３及びＬＰＧ４ ９０４を示す。ＩＰアドレス内の最初の２つの３桁数字９０５は、標準的なネットワークプレフィックス「１９２．１６８」を表す。標準的なネットワークプレフィッ
クス「１９２．１６８」は、ネットワーク内の全てのＬＰＧの場合に同じである。第３の３桁数字９０６はＬＰＧ ＩＤであり、ＬＰＧ特有である。図９に示されるように、ＬＰＧ１ ９０１、ＬＰＧ２ ９０２、ＬＰＧ３ ９０３及びＬＰＧ４ ９０４はそれぞれ、第３の３桁数字９０６内に１、２、３、４の値を有する。第４の３桁数字９０７は、個々の移動デバイスの識別情報を表す。この番号は、移動デバイスに基づいて変わる。この番号は、上記の実施形態のうちのいずれか１つを用いて割り当てることができる。

図１０は、ＩＰｖ６プロトコルの場合のＩＰアドレスのための１つの例示的なフォーマットを示す。例示の目的で、図１０では、図９で用いられたものと同じＬＰＧ参照符号を用いる。上位部分１０００は、６４ビットになるように示されており、ＬＰＧ ＩＤを表し、下位部分１００１も６４ビットであり、移動デバイスの識別情報（ＥＵＩ）を表す。上位部分１０００及び下位部分１００１はいずれも、固定ＬＰＧ毎に異なる。

さらに、上述したように、移動デバイスにＬＰＧを円滑に変更させるために、且つＬＰＧ間通信を支援するのを容易にするために、固定ＬＰＧ間に、或る重なり合うエリアが存在することがある。好ましい実施形態では、重なり合うエリアでは、各移動デバイスが２つのＩＰアドレスを有し、両方のＬＰＧにアクセスできるようにする。移動デバイスが重なり合うエリアに接近すると、アドレス割当て手段８１２は、その移動デバイスに対して第２のＩＰアドレスを割り当てる。具体的には、その移動デバイスは、メモリ内に格納される重なり合うエリアの位置を現在の位置と比較し、自分が重なり合うエリア又は境界エリアに位置するか否かを判定する。無線デバイスは、ネットワークインターフェース手段８１４（すなわち、８０２．１１カード）を有する。１つの物理無線インターフェースによって、多数の論理インターフェースに対応することができる。各論理インターフェースは１つのＩＰアドレスを有する。それゆえ、各ネットワークインターフェース手段８１４は、２つ以上のＩＰアドレスを有することができる。各ＩＰアドレスは、上記で特定した実施形態のいずれかに従って割り当てることができる。

動的ＬＰＧの場合にも、固定ＬＰＧに対するＩＰアドレス割当てと類似の技法を利用することができるが、動的ＬＰＧに対するＩＰアドレス割当ては、より動的である。これは、ＬＰＧの位置がもはや固定されていないためである。さらに、ＬＰＧ ＩＤも一定ではなく、絶えず変化する。さらに、動的ＬＰＧの場合には、ＬＰＧ間通信へのＩＰアドレスの割当てが異なる。

動的ＬＰＧのためのＰＬＧ内ＩＰアドレス割当ての場合、その技法は、ＩＰｖ４の場合の固定ＬＰＧにＩＰアドレスを割り当てるために用いられる技法と概ね同様である。図１１ａ及び図１１ｂは、ＩＰｖ４プロトコルの場合のＩＰアドレスフォーマットの２つの異なる例を示す。いずれのフォーマットでも、ＩＰアドレスの上位部分、すなわち最初の２つの３桁数字１１００は、標準的なネットワークプレフィックス、たとえば、１９２．１６８、１０．０及び１７２．１２によって決定される。一実施形態では、標準的なネットワークプレフィックスは、プライベートアドレスになる。標準的なネットワークプレフィックスは、そのアドレスの最初の２つの３桁数字になるであろう。

第３の３桁数字１１０１はＬＰＧ ＩＤである。一実施形態では、ＬＰＧ ＩＤはランダムに生成される。第４の３桁数字は、移動デバイスの識別情報である。この識別番号は、図１１ａに示されるように、ＶＩＮ又はＭＡＣアドレス１１０２ａのハッシュ関数に基づいて割り当てることができるか、又は図１１ｂに示されるように、移動デバイスがＬＰＧ１１０２ｂに入るシーケンスに基づいて割り当てることができる。ハッシュ関数及びシーケンシングは、固定ＩＰアドレス割当てに関して先に説明されており、さらに説明はしない。

このＩＰアドレスによって、ＬＰＧの中で通信、すなわちＬＰＧ内通信が可能となる。しかしながら、ＬＰＧ間通信のためには、移動デバイスに対して、別個のＩＰアドレスが割り当てられなければならない。これは、公開ＩＰアドレスになるであろう。この公開ＩＰアドレスは、ＤＨＣＰサーバとして動作する外部の無線デバイスによって、又はＤＨＣＰとして動作する別の移動デバイスによって割り当てることができる。このアドレス割当ては、移動デバイス（ＬＰＧの代表者としての役割を果たす）と外部デバイス（ＤＨＣＰサーバとしての役割を果たす）との間のＤＨＣＰプロトコルに従う。

本発明の一実施形態では、ＬＰＧ内の１つの移動デバイスは、ＩＰｖ４プロトコルを用いて、ＬＰＧ間通信のための公開ＩＰアドレスを割り当てられる。図１２ａに示されるように、１つのノード１２０２は、公開ＩＰアドレスＩＰＡ１２０４を割り当てられる。このノード１２０２は、ＬＰＧ内の最初の移動デバイス、リーダとして選択される移動デバイス、又は別の所定の選択判定基準に基づいて選択される移動デバイスであってもよい。別法では、その選択はランダムに行うことができる。残りのノード１２０１は、公開ＩＰアドレスＩＰＡ１２０４を割り当てられない。

別の実施形態では、所与のＬＰＧ内の各移動デバイスには、異なるＩＰアドレスが割り当てられる。図１２ｂに示されるように、ＬＰＧ１２００は６つのノード１２０１を有する。各ノード１２０１は、異なるＩＰアドレスＩＰＡ１２０４〜ＩＰＦ１２０９を割り当てられるであろう。

第３の実施形態では、ＬＰＧ内の全ての移動デバイスに対して、ただ１つのグローバル公開ＩＰアドレスが割り当てられる。図１２ｃに示されるように、ＬＰＧ１２００内の各移動デバイス又はノード１２０１には、同じ公開ＩＰアドレス１２０４が割り当てられる。この公開ＩＰアドレス１２０４は、インターネットを介して通信するために、他のノードによってグローバルに認識することができる。たとえば、公開ＩＰアドレスは２３９．５．５．５にすることができる。

ＩＰｖ６プロトコルの場合、ＬＰＧ内通信のためのＩＰアドレスを割り当てるために２つの異なる方法がある。ＩＰｖ６プロトコルを用いる無線デバイスは、２つの自動設定機能、すなわちリンクローカルアドレス及びルータ広告アドレス設定機能を有する。

図１３ａ及び図１３ｂは、ＬＰＧ内通信用のＩＰアドレスのフォーマットの２つの異なる例を示す。図１３ａに示されるように、第１の手法は、リンクローカルアドレス１３００、たとえばｆｅ８０を用いる。リンクローカルアドレス１３００は、ＩＰアドレスの上位部分になる。下位部分、すなわちＥＵＩ１３０２は、６４ビットであり、ＭＡＣアドレス及び／又はＶＩＮ番号から計算される。しかしながら、リンクローカルアドレス手法は、ＬＰＧ内においてのみ有効であり、ＬＰＧ間通信のための第２の付加的なアドレスを必要とする。

第２の手法は、図１３ｂに示されるように、サイトローカルのような手法、又はルータ広告アドレスを用いることである。そのネットワークは、移動デバイスのネットワーク又は車両ネットワークに専用の所定の移動デバイスのプレフィックス１３０１を含む。この移動デバイスのプレフィックス１３０１は、「ＸＸＸＸ」１３０３として図１３ａに表されるように、上位６４ビットになるようにＬＰＧ ＩＤと組み合わせられる。下位６４ビット、すなわちＥＵＩ６４ １３０２は、図１３ａの場合と同じになるであろう。それゆえ、ＥＵＩ６４の番号は、両方のフォーマットの場合に同じになり、その差は、ＩＤアドレスの上位部分である。

両方のフォーマットにおいて、アドレスの一部として、ＬＰＧ ＩＤが用いられる。Ｌ
ＰＧ ＩＤは、ＬＰＧ毎に固有でなければならない。本発明の一実施形態によれば、ＬＰＧ ＩＤは、ランダムに割り当てられる番号か、又はハッシュ関数によって予め定義される番号のいずれかであってもよい。ハッシュ関数は、ＬＰＧの位置、入手可能であるなら、ＬＰＧ内の第１の移動デバイスのＭＡＣアドレス、又はＬＰＧ内の第１の移動デバイスのＶＩＮ番号から成ることができる。

ＬＰＧ間アドレスを割り当てる場合、一実施形態では、外部無線デバイスを用いて、ＩＰアドレスの一部が割り当てられる。外部無線デバイスとして、ＬＰＧに対して、そのアドレス範囲及びプレフィックスを送信する、路側ゲートウエイ又は境界ルータのような任意のデバイスを用いることができる。ネットワークプレフィックスは、それらのゲートウエイ（ルータ）広告から入手することができる。受信されたネットワークプレフィックス１４００は、ＩＰアドレスの上位部分、たとえばＩＰアドレスのためのグローバルディレクトリとして用いられるであろう。ＩＰアドレスの下位部分は、ＬＰＧ内通信ＩＰアドレスのために用いられるのと同じＥＵＩ番号６４ １３０２を用いることができる。

別の実施形態では、所定の車両又は移動デバイスのプレフィックス１３０１が作成され、各移動デバイスのメモリセクションに導入される。この移動デバイスのプレフィックス１３０１を、ＬＰＧ ＩＤ１３０３と組み合わせて、上位６４ビットが形成される。ＬＰＧ ＩＤは、ＬＰＧ毎に固有でなければならない。本発明の一実施形態によれば、ＬＰＧ
ＩＤは、ランダムに割り当てられた番号か、又はハッシュ関数によって予め定義された番号のいずれかであってもよい。ハッシュ関数は、ＬＰＧの位置、入手可能であるなら、ＬＰＧ内の第１の移動デバイスのＭＡＣアドレス、又はＬＰＧ内の第１の移動デバイスのＶＩＮ番号から成ることができる。ＩＰアドレスの下位部分は、ＬＰＧ内通信ＩＰアドレスのために用いられるのと同じＥＵＩ番号６４ １３０２を用いることができる。

一実施形態では、任意の移動デバイスに、任意のＩＰアドレスを割り当てることができる。別の実施形態では、種々のクラスの移動デバイスのために、特定のＩＰアドレスを予約することができる。たとえば、緊急車両は、特定の範囲のＩＰアドレスを割り当てられることができる。この範囲内のＩＰアドレスは、救急車、パトカー及び消防車のような緊急車両のために保存される。外部無線デバイス又はゲートウエイは、特殊な移動デバイスを認識しており、特殊な移動デバイス又は移動デバイスの分類のリストをメモリ内に格納している。これらの特殊車両は、ＩＰアドレスを要求するために特殊な問い合わせを用いなければならない。

これによって、緊急車両からの優先メッセージが容易になる。言い換えると、特定の範囲のＩＰアドレスから発信される全てのメッセージは、伝送のために最も高い優先度を有する。

本明細書において、本発明が、特定の例示的な実施形態を参照しながら説明されてきた。本発明の範囲から逸脱することなく、当業者には、特定の改変及び変更が明らかになり得る。例示的な実施形態は、例示することを意図しており、添付の特許請求の範囲によって規定される本発明の範囲を制限することは意図していない。

本発明による２つのローカルピアグループの一例を示す図である。 本発明による複数の固定ＬＰＧを示す図である。 本発明による複数の動的ＬＰＧを示す図である。 本発明の一実施形態による、「要求に応じて」ＬＰＧを順序付けする方法を示す図である。 本発明の別の実施形態による、移動デバイスを順序付けする一例を示す図である。 本発明の別の実施形態による、移動デバイスを順序付けする方法を示す図である。 １つのＬＰＧ内の複数のＥＣを示す図である。 本発明による、移動デバイスに取り付けられるか、又は内蔵される無線デバイスを示す図である。 上記で特定した実施形態による、ＩＰアドレスを割り当てる一例を示す図である。 本発明の別の実施形態による、ＩＰアドレスのフォーマットを示す図である。 動的ＬＰＧ内の移動デバイスにＩＰアドレスを割り当てる際に用いられる２つの異なるＩＰアドレスフォーマットを示す図である。 本発明による、ＬＰＧ間通信のためにＩＰアドレスを割り当てるための実施形態を示す図である。 動的ＬＰＧの場合のＬＰＧ内通信用のＩＰアドレスの２つの異なるフォーマットを示す図である。 動的ＬＰＧの場合のＬＰＧ間通信用のＩＰアドレスの２つの異なるフォーマットを示す図である。

Claims (1)

1. 道路上を走行する車両に設けられた複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法であって、
   （ａ）前記複数の移動デバイスを少なくとも１つのローカルピアグループ（ＬＰＧ）にグループ化するステップと、
   （ｂ）各ＬＰＧ内の前記複数のデバイスのそれぞれの相対的な位置に基づいて、各ＬＰＧ内での該複数の移動デバイスの前記道路に沿った方向における相対的な位置順序および相対的な方向を検出するステップと、
   （ｃ）前記複数の移動デバイスのそれぞれに、所定のネットワークプレフィックス、移動デバイスが属するＬＰＧの固有識別情報、及び移動デバイスの固有識別情報が連結されたＩＰアドレスを割り当てるステップと
   を含む、
   複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。

Images