アドホック無線ピアツーピアネットワークを確立及び編成する方法
【課題】複数の移動デバイス間で通信するためのアドホックネットワークを編成するとともに維持する方法が開示される。
【解決手段】本発明に係る方法は、複数の移動デバイスを少なくとも1つのローカルピアグループ(LPG)にグループ化するステップと、各LPG内の複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の複数のデバイスを順序付けするステップと、複数の移動デバイスのデバイス毎に固有の識別子を割り当てるステップとを含み、固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく。
【解決手段】本発明に係る方法は、複数の移動デバイスを少なくとも1つのローカルピアグループ(LPG)にグループ化するステップと、各LPG内の複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の複数のデバイスを順序付けするステップと、複数の移動デバイスのデバイス毎に固有の識別子を割り当てるステップとを含み、固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく。
【発明の詳細な説明】
【技術分野】
【0001】
[発明の背景]
[発明の分野]
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、通信をほぼ瞬時に達成するために、移動デバイス間にアドホック無線ネットワークを確立及び維持することに関する。
【0002】
[関連出願]
本出願は、2005年1月11日に出願の米国特許仮出願第60/643,373号に関連し、その優先権を主張する。
【背景技術】
【0003】
[関連技術の記載]
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でWiFi技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。802.11a/b/gのような無線ネットワーキング技術によって、WiFi機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【0004】
これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、2004年7月29日に、ミシガン州グランドヘブンは、6平方マイルの都市を網羅し、ミシガン湖まで15マイルにわたって広がる、都市全域の無線ネットワークを構築して、「全米最初のWiFi都市」であるという栄誉を主張した。多数の市当局者は、WiFiを、下水・電力・電話及び交通機関と同様に企業を誘致・維持するために不可欠なインフラストラクチャと見ている。そのようなシステムの市当局者にとっての利点は、市職員の間での通信手段を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまで多岐にわたる。
【0005】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路及び高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【0006】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが差し迫った状況に陥る前に、必要な措置を講じることができるようになる。この特徴が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが
、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更又は合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【0007】
車両安全通信(「VSC」)は、大きく、車車間通信とインフラストラクチャを介した車両通信とに分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【0008】
重要なVSC性能要件には、衝突回避のような種々のVSCアプリケーションを支援するために、遅延時間が短いこと(約100ミリ秒)、及びスループットを維持すること(別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ)が含まれる。
【0009】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【0010】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【0011】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。
【0012】
移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい(すなわち、どの車両も、予めその近くにいる車両について何も知らない)。車両間安全通信を構築するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行うことができるようにしなければならない。協調しない車両の移動度が高いということは、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ(移動度、アドレス、名前、メディアセッションのための)を用いることが難しいということを意味する。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【0013】
ホットスポットのような他の場所で利用されるWiFi方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、3車線の高速道路の1200メートル長当たりの車両が600台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速30〜60マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【0014】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両
が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【0015】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、FleetNetおよびCarTalk2000はいずれも、車車間通信ネットワークを構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でGPSシステムを使用する。FleetNetは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノード及び移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費及び間接費が生じる。さらに、FleetNetシステムは、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【0016】
CarTalk2000も位置に基づくプロトコルを用いる。CarTalk2000による車車間システムに参加する各車両は、常に現在位置を検出するために、GPSデバイスを搭載していなければならない。さらに、CarTalk2000は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【0017】
CarTalk2000システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【0018】
しかしながら、これらのGPSネットワークは大きな欠点を有する。移動度の高い車両環境では、GPS情報はすぐに有効でなくなる。GPS位置ルーティングを実行するために、車両間で絶えず変化するGPS情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなGPS位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【0019】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なVSC性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【0020】
[発明の簡単な概要]
したがって、本発明の目的は、複数の移動デバイスをローカルピアグループ(「LPG」)のような管理グループにグループ化することによって、移動デバイス間通信に適した通信境界を作り出し、メッセージ伝送を調整及び中継し、メッセージ伝搬の範囲及び方向を制御することである。さらに、本発明の目的は、ローカルピアグループを確立及び維持し、識別情報を動的に割り当て、移動デバイスの相対的な順序を周期的に更新するための簡単なプロトコルを提供することである。
【0021】
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法が開示される。当該方法は、複数の移動デバイスを少なくとも1つのローカルピアグル
ープ(LPG)にグループ化するステップと、各LPG内の複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の複数のデバイスを順序付けするステップと、複数の移動デバイスのそれぞれに固有の識別子を割り当てるステップとを含み、固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく。
【0022】
2つのタイプのLPG、すなわち固定LPG及び動的LPGがある。固定LPGの位置及びサイズは予め定義されており、各移動デバイスのメモリ内にプログラミングされる。動的LPGは、複数の移動デバイスのうちの1つ又は複数のクラスタリングに基づいて形成される。ネットワークは、固定LPG及び動的LPGのいずれか又は両方を含むことができる。
【0023】
各LPGは、移動デバイスのグループによって定義される等価セル(EC)に分割される。このグループ内の各移動デバイスは互いに1ホップ内に存在し、一度のメッセージ伝送のみによって、このEC内のどの移動デバイスとも通信できる。各ECは、等価セルヘッダ(ECH)によって制御される。
【0024】
移動デバイスの相対的な位置を更新して、複数の移動デバイスの移動によって生じる再順序付けに対処する。順序付け及び再順序付けは、各LPG内の各移動デバイスの相対的な位置を表す位置ベクトルを作成することによって達成することができる。
【0025】
位置ベクトルは、位置ベクトルを初期化し、初期化された位置ベクトルをLPGに参加している別の移動デバイスに送信し、別の移動デバイスが、自身の位置を送信に含まれる位置情報と比較し、その比較に基づいて、この別の移動デバイスの位置値を位置ベクトルに挿入し、更新された位置ベクトルを、LPG内の他の全ての移動デバイスに送信することによって生成される。
【0026】
別法では、移動デバイスの順序付け及び再順序付けは、第1の移動デバイスの位置と意図したメッセージ方向の指示と送信時刻とを含むメッセージを送信し、第2の移動デバイスが、送信メッセージを受信し、受信された送信メッセージに基づいて、第1の移動デバイスの変位を推定し、推定された変位及び第1の移動デバイスの位置に基づいて第1の移動デバイスの現在の位置を計算し、計算された現在の位置と第2の移動デバイスの位置とを比較することによって達成することができる。第2の移動デバイスは、第2の移動デバイスが意図したメッセージ方向に沿っているものと判定されるときにだけ、メッセージを中継又は転送する。
【0027】
移動デバイス毎の固有の識別子はLPG特有である。それゆえ、移動デバイスの固有の識別子は、移動デバイスがLPGを変更するときに変更される。さらに、2つの隣接するLPGの境界付近に、又は隣接するLPGの重なり合うエリア内に位置する移動デバイスは、2つのIPアドレスを割り当てられ、隣接するLPG間で通信できるようにする。
【0028】
この固有の識別子は、IPアドレスであってもよい。IPアドレスは、固有のLPG識別情報及び固有の移動デバイス識別情報と連結される所定のネットワークプレフィックスに基づいて割り当てることができる。固有のLPG識別情報及び固有の移動デバイス識別情報はハッシュ関数から計算することができる。別法では、固有のLPG識別情報及び固有の移動デバイス識別情報は、移動デバイスと通信している外部無線デバイスから与えることができる。
【0029】
移動デバイスはそれぞれ、移動デバイスのタイプに従って分類することができ、この分類に基づいて、固有の識別子を割り当てることができる。
【0030】
本発明のこれらの及び他の特徴、利益及び利点は、添付の図面を参照することによって明らかになるであろう。なお、図面を通して、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0031】
【図1】本発明による2つのローカルピアグループの一例を示す図である。
【図2】本発明による複数の固定LPGを示す図である。
【図3】本発明による複数の動的LPGを示す図である。
【図4】本発明の一実施形態による、「要求に応じて」LPGを順序付けする方法を示す図である。
【図5】本発明の別の実施形態による、移動デバイスを順序付けする一例を示す図である。
【図6】本発明の別の実施形態による、移動デバイスを順序付けする方法を示す図である。
【図7】1つのLPG内の複数のECを示す図である。
【図8】本発明による、移動デバイスに取り付けられるか、又は内蔵される無線デバイスを示す図である。
【図9】上記で特定した実施形態による、IPアドレスを割り当てる一例を示す図である。
【図10】本発明の別の実施形態による、IPアドレスのフォーマットを示す図である。
【図11】動的LPG内の移動デバイスにIPアドレスを割り当てる際に用いられる2つの異なるIPアドレスフォーマットを示す図である。
【図12】本発明による、LPG間通信のためにIPアドレスを割り当てるための実施形態を示す図である。
【図13】動的LPGの場合のLPG内通信用のIPアドレスの2つの異なるフォーマットを示す図である。
【図14】動的LPGの場合のLPG間通信用のIPアドレスの2つの異なるフォーマットを示す図である。
【発明を実施するための形態】
【0032】
[発明の詳細な説明]
本発明によれば、複数のノードすなわち移動デバイスが、管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて、又は固定された位置に基づいて構築される。このグループ化すなわちローカルピアグループ(「LPG」)は、単一のLPG内や複数のLPG間での無線信号のルーティングを実施するための基礎となる。無線信号は、車両安全アプリケーションや情報アプリケーションを含む。
【0033】
LPGの目的は、近くにある複数のノード間の連携(coordination)の程度を構築することである。これら近くにあるノードは、無線通信能力を有する移動デバイスである。移動無線デバイスは、PDA、ノートパソコン、携帯電話、又は無線デバイスが取り付けられるか内蔵されている車両であってもよい。具体的には、移動デバイスには、車両内に設置されたり車両内に個別に持ち込まれたりする通信デバイスを備える車両や、通信デバイスを携帯した歩行者が含まれる。
【0034】
連携の程度には、2つのタイプがある。第1のタイプは隣接する移動デバイスの密な連携であり、LPG内通信のために用いられる。LPG内通信は、概ね瞬時のメッセージ伝送の支援に利用される。たとえば、緊急道路障害物警告や他のタイプの緊急メッセージ又は安全メッセージの送信は、LPG内メッセージ伝送を用いて実行されるであろう。これ
らのメッセージは、一般的に、遅延時間が100msec程度であることを要求する。
【0035】
第2のタイプは、緩やかな連携、すなわち近くにある移動デバイスをグループ化することである。このタイプの連携は、リンク又は相互接続されているLPG間のLPG間通信を支援するために用いられる。たとえば、LPG間通信は、道路認識アプリケーションや、ドライバの視界拡張のために用いることができる。
【0036】
LPGは、効率的且つ信頼性のある移動デバイス間通信を支援するだけでなく、移動デバイス及び道路インフラストラクチャを、1つの完全な通信ネットワークとして統合できるように、移動デバイスと固定インフラストラクチャ間の通信も支援することができる。
【0037】
図1は2つのLPGを示しており、第1のLPG100は、4つのノード110、111、112及び113を含む。これら4つのノード110、111、112及び113はそれぞれ、互いにデータを送信することができる。第2のLPG120は、ノード121、122、123、124、125及び126を含む。ノード121〜126はそれぞれ、互いにデータを送信することができる。このタイプの伝送は、LPG内伝送であり、瞬時に行われる。LPG100内のノード110〜113は、LPG間通信を用いることによって、LPG120内のノード121〜126にデータを送信することができる。2つのLPG100、120は、アドホックネットワーク150を形成する。
【0038】
LPGには2つのタイプ、すなわち固定LPG及び動的LPGがある。固定LPGは、予め割り当てられたグループ位置定義を用いて、移動デバイスを分割する。対照的に、動的LPGは、近くにある移動デバイスが通信するための(動的な)無線通信エリアに基づいて、移動デバイスを適当に組み合わせることができる。
【0039】
図2は、複数の固定LPG(LPG1〜8)200〜207を示す。各LPGは、特定の位置又はエリアによって画定される。すなわち無線デバイス又は移動デバイスがエリア1内にある場合には、そのデバイスはLPG1である。無線デバイス又は移動デバイスがエリア2内にある場合には、そのデバイスはLPG2であり、他も同様である。固定LPGの個々のサイズは設計上の選択事項であり、種々の要因、たとえば無線アンテナの範囲、通信範囲、移動デバイスの数、地形、環境条件、交通パターン及び人口密度にしたがって決められる。固定LPGの位置及びサイズは固定であるが、交通パターン及び人口(移動デバイス)密度は場所によって異なるので、各固定LPGは異なるサイズであっても良い。一般的には、LPGサイズを、無線通信範囲よりも大きくして、マルチホップ通信できるようにすべきである。さらに、効率的なLPG間通信を容易にするために、固定LPGは、隣接するLPG間のエリアと重なり合うこともできる。重なり合うエリアは、変化に富んだ状況(たとえば移動デバイスによって速度が異なること)に適応するために、状況に合わせたサイズを有することができる。
【0040】
本発明の一実施形態によれば、固定LPGのための境界は、郵便番号や市外局番のような所定のエリアに基づく。通常、郵便番号は人口密度に相当する。或るエリアの人口密度は、そのエリア内の交通パターンや移動デバイスの数の良好な指標である。
【0041】
固定LPGに基づくネットワークアーキテクチャでは、移動デバイスが、全地球測位システム(GPS)又は他の何らかの位置情報を備える必要がある。これにより、移動デバイスは、その移動デバイスが属する固定LPGを特定又は検出できるようになる。移動デバイスは、位置を変更するのに応じて、固定LPGを変更する。それゆえ、移動デバイスは、更新された位置データを周期的に受信する必要がある。この周期は、移動デバイスが移動する速さ又は速度に依存する。移動デバイスは、LPG及びそれらの位置のデータベースを含む。
【0042】
固定LPGは、いくつかのLPGが空であったり、LPG内に多数の移動デバイスがないときであっても、無線インフラストラクチャと統合して、バックボーンアクセスやLPG間通信を提供できるという大きな利点を有する。
【0043】
各固定LPGは、通信を容易にするために、固有の識別子を割り当てられる。本発明の一実施形態では、固定LPGのための固有の識別子は、そのLPGの郵便番号に基づいて割り当てられる。この方法は、既存の郵便番号データベースを活用する。したがって、新たな識別番号を作成する必要はない。別法として、別の実施形態では、固定LPGのGPS座標を用いることができる。同じように、その方法は、あらかじめ定められたデータベースを利用する。別の実施形態では、LPGの固有の識別子として、州名及び都市名を用いることができる。別法では、上記の実施形態の任意の組み合わせを用いて、LPG固有の識別子を割り当てることができる。LPGの固有の識別子は、後に説明されるように、移動デバイスの固有の識別子の一部として用いられる。
【0044】
全ての固定LPGエリアは明確であるので、LPGを形成及び命名するのは、動的LPGよりも容易である。さらに、固定LPGを用いるとき、LPGの合併や分割に関するルールを心配する必要はない。
【0045】
図3は、複数の動的LPG(LPG A〜E)、それぞれ300〜304を示す。固定LPGとは対照的に、動的LPGは、移動デバイスがその厳密な位置を気にすることなく通信を連携できるように、近くにある移動デバイスの無線通信エリアに基づいて形成される。
【0046】
動的LPGは無線通信エリアに基づいて形成されるので、そのLPG内の移動デバイスは常に、1ホップ又はマルチホップの伝送を介して、互いに通信することができる。各LPG内の移動デバイスの数を適度に少なく保持し、通信を短い遅延で効率的に実行できるようにするために、移動デバイスは動的LPGのサイズを制御することができる。さらに、固定LPGとは対照的に、動的LPGは、各LPG内で常に通信が可能であることを保証する。
【0047】
一実施形態では、アドホックピアツーピアネットワークを、1つ又は複数の固定LPGから構築することができるし、1つ又は複数の動的LPGから構築することもできる。別の実施形態では、アドホックピアツーピアネットワークは、固定LPG及び動的LPGの両方から、ハイブリッドLPGネットワークとして構築することができる。ハイブリッドLPGネットワークは、固定LPG及び動的LPGを別個に採用した場合に生じる問題を取り除きながら、それぞれの利点を兼ね備える。
【0048】
固定LPGの利点のうちの1つは、エリアによって移動デバイスを容易にグループ化することができること、及びインフラストラクチャとやりとりできることである。さらに、後で詳細に説明されるように、固定LPGによれば、移動デバイス毎にアドレス指定用識別子すなわち固有の識別子を簡単に割り当てることができるようになる。さらに、全てのノードが、ネットワーク全体のトポロジ及び構造を把握している。それゆえ、ノード又は移動デバイスを容易に追跡することができる。
【0049】
動的LPGにはいくつかの利点がある。それらの利点のうちの1つは、ネットワークがノードのクラスタリングに基づいて形成されるので、動的LPGは事前の設定が必要ないことである。さらに、動的LPGは、LPGの形成や合併、分割をより自由に行うことができ、一度形成されると、全ての車両が一斉に通信することができる。それゆえ、近くにある移動デバイス間での通信がさらに容易である。
【0050】
固定LPGの欠点は、より広くに遍在する路側無線アクセスポイント、路側ゲートウエイ、路側データ記憶装置(入力(deposit)及び検索用)を必要とすることであり、動的LPGの場合に不要であるのとは対照的である。
【0051】
ハイブリッド手法は、道路の敷設状況(topology)を利用する。具体的には、インフラストラクチャが利用できないとき、動的LPGを用いて、ネットワークが形成される。或るエリアにおいて、インフラストラクチャを利用できるようになるとき、固定LPGを用いて、動的LPG及びインフラストラクチャとともにネットワークを形成することができる。
【0052】
たとえば、道路インフラストラクチャのようなインフラストラクチャによって、路車間通信及び道路支援(車路車間)通信を実現できるようになる。これは、固定LPGを用いるときに特に有用である。さらに、道路インフラストラクチャは、インフラストラクチャから車両への通信を容易にする。このタイプの通信は、隠れた私道に対する警告、電子道路標識、路面条件、踏切警告、経路案内及びナビゲーション、ハイウエイ合流支援、交差点衝突警告、及び工事区間警告等の、特定の緊急情報を行き渡らせるために重要である。
【0053】
LPGには主に2つの種類がある。1つは順序付けされないLPGであり、もう1つは相対的に順序付けされるLPGである。相対的に順序付けされるLPGでは、移動デバイスのうちの少なくともいくつかが、近くにある移動デバイスの相対的な位置を認識する。相対的な順序付けは、LPG内でメッセージをルーティングするための基礎である。近くにある移動デバイスの相対的な順序や相対的な方向を検出・認識できると、LPG環境内でのメッセージルーティングを効率的に行えるようになる。この効率的なルーティングは、メッセージが道路環境における緊急メッセージであるときに重要である。たとえば、或る車両によって、警告メッセージがLPGの後方に進むように指定されることがある。LPGにおいて送信する車両の前方にある車両は、そのメッセージを受信又は中継する必要はない。その車両は相対的な方向がわかるので、適当な方向に向かってメッセージを誘導し、それにより、中継トラフィック及び使用される帯域幅の量を削減することができる。
【0054】
方向の検出又は認識は、移動デバイスの相対的な順序から導出することができる。一実施形態では、相対的な順序付けは、「必要に応じて(on-demand)」行われる。別の実施形態では、相対的な順序付けは周期的に維持される。
【0055】
図4は、本発明の一実施形態による、「必要に応じて」LPGを順序付けする方法を示す。その過程は、ステップ400において開始する。第1の移動デバイスが。その移動デバイスのGPS位置、現在の速度及びタイムスタンプを含むメッセージを、意図したメッセージ方向とともに送信する。ステップ410では、第2の移動デバイスがこのメッセージを受信する。ステップ420において、第2の移動デバイスは、第1の移動デバイスの現在の位置を推定する。第1の移動デバイスの現在の位置の推定は、既にわかっている第1の移動デバイスの以前の位置からの第1の移動デバイスの起こり得る変位に基づいて行うことができる。以前の位置は、受信されたメッセージから直に求められる。起こり得る変位は、推定された速度及び時間差に基づいて計算される。受信されたメッセージはタイムスタンプを含むので、第2の移動デバイスは時刻、すなわちそのタイムスタンプから、メッセージが受信された時刻までの差を計算する。この場合、それらの移動デバイスにおいて、クロック及びGPS情報の両方の時間が同期している、すなわちGPSデバイスが同期している必要がある。推定速度は、いくつかの異なる態様で計算することができる。一実施形態では、第1の移動デバイスの(瞬間)速度は、第1の移動デバイスによって送出されるメッセージに含まれる。この速度は、第2の移動デバイスが第1の移動デバイスの現在の速度を推定する際に用いることができる。別の実施形態では、第2の移動デバイ
スは、第1の移動デバイスの速度として自らの速度を用いることができる。別法では、予め決定された推定速度を用いることができる。予め決定された推定速度は、制限速度、時刻、場所、気象条件及び地形に基づいて変わることがあるデータベースとして、移動デバイスのメモリ内に予め格納されるであろう。第2の移動デバイスは、推定速度と、時間差とを乗算して、起こり得る変位を求める。この値は、以前の位置からの起こり得る変位であり、第1の移動デバイスの以前の位置を調整して、第1の移動デバイスの推定位置を求めるために用いられる。
【0056】
本発明の一実施形態では、第1の移動デバイスの変位は、向きの成分を有する。この実施形態では、推定される変位は、向きの変化を考慮に入れる。第1の移動デバイスの以前の位置に、位置の変化が移動方向に対して加えられる。一実施形態では、第1の移動デバイスは、そのメッセージ内にGPSの向き(たとえば、NW、SE35°)を(その位置、タイムスタンプ等とともに)含むことができ、この向きの情報が、厳密な変位を推定するために、第2の移動デバイスによって用いられる。別法として、別の実施形態では、第2の移動デバイスが、局所的な地形情報を利用することによって、(第1の移動デバイスが、向きの情報を送信することなく)第1の移動デバイスの向きを推定することができる。すなわち、両方の移動デバイスが同じ道路に沿って進行していることがあるので、それを利用して第1の移動デバイスの向きを推定する。それゆえ、第2の移動デバイスは、計算された変位を、(第1の移動デバイスの)以前の位置に、第2の移動デバイスが移動している方向に対して加えることができる。
【0057】
ステップ430では、第2の移動デバイスが、第1の移動デバイスの計算された推定位置と、自ノードの現在の位置とを比較して、2つの移動デバイスの相対的な順序を決定する。
【0058】
第2の移動デバイスは、自ノードが意図されたメッセージ方向にあるものと判定されるときにだけ、そのメッセージを中継又は転送する。自ノードの位置及び向きが送信側の移動デバイスと受信側の移動デバイスとの間にある場合には、移動デバイスは意図したメッセージ方向に沿っている。具体的には、第2の移動デバイスは、計算された相対的な順序又は位置を用いて、第2の移動デバイスが意図された経路に沿っているか否かを判定する。
【0059】
一実施形態では、向きの情報を用いて、第2の移動デバイスが意図した経路に沿っているか否かが判定される。この向きの情報は、上記のように、第1の移動デバイスの推定される位置を導出するために、第2の移動デバイスによって用いられる。上記のように2つの移動デバイス間の相対的な序列が決定されると、第2の移動デバイスは、第1の移動デバイスのメッセージに含まれる第1の移動デバイスの向きと、自らの向きとを用いることによって、第2の移動デバイスが第1の移動デバイスの意図したメッセージ伝送の経路上にあるか否かを判定することができる。たとえば、両方の移動デバイスが類似の向きを有し(すなわち同じ道路に沿って進行しており)、第2の移動デバイスが第1の移動デバイスの前方にある(その相対的な順序によって判定される)場合、意図されたメッセージの方向が同じ向きに沿っているときには、第2の移動デバイスがその(第1の移動デバイスの)メッセージを転送するのに対して、意図されたメッセージの方向が反対の向きを有するときには、第2の移動デバイスはそのメッセージを転送しない。第1の移動デバイスがその向きの情報をメッセージとして送信しない別の実施形態では、第2の移動デバイスは、上記のように、たとえば、以前の位置に対する変位を推定することによって、第1の移動デバイスの向きを推定することができる。2つの移動デバイスの向き及び相対的な順序がわかると、第2の移動デバイスは、先に説明されたのと同じようにして、第2の移動デバイスが第1のデバイスの意図したメッセージ伝送の経路に沿っているか否かを判定することができる。
【0060】
第2の移動デバイスがその経路内に存在しない場合には、そのメッセージは転送されない。本実施形態による移動デバイスの順序付けは、移動デバイスの順序付けが重要でないときに、帯域幅が順序付け要求で輻輳しないという利点を有する。
【0061】
本発明の別の実施形態では、移動デバイスの相対的な順序は、位置ベクトルを用いて周期的に更新される。図5は、この方法を用いてLPGを順序付けする一例を示す。図5は、LPG500を、LPG位置ベクトルV510とともに示す。LPGは、一次元のアレイすなわちベクトルV510にマッピングされる。LPG500の各移動デバイスは1つのベクトルIDを有することになる。ベクトルIDはまさに、Vの位置インデックスである。図5に示されるように、ベクトルV510は、移動デバイスの位置の順序を表す。図5では、6つの異なる相対的な順序1〜6が存在する。その矢印は、移動デバイスの移動方向、たとえば、交通の流れを示す。
【0062】
位置ベクトルV510によって、移動デバイスは、情報伝送の方向を制御できるようになる。詳細には、位置ベクトルV510を用いて、ピアグループ内で情報をルーティングすることができる。たとえば、図5に示されるように、インデックス3を有する送信側の移動デバイスが、そのメッセージが3よりも小さなインデックスを有する移動デバイスに向けられていることを指示する場合には、インデックスj<3を有する移動デバイスだけが、そのメッセージを中継する。これは、そのメッセージがjより小さいインデックスを有する車両に向けられていることを指示することによって達成される。その中継は、そのメッセージがLPGの後方境界ノードに達するまで、又はそのメッセージが最大ホップ数に達するまで続く。同じようにして、前方への情報伝搬を達成することができる。
【0063】
さらに、位置ベクトルV510を用いることによって、ルーティング優先度を促進することもできる。MAC層は、この位置ベクトル510に基づいて、アクセス優先度を生成することができる。一般的に、そのネットワークでは、前方にある移動デバイスが警告事象を観測し、より高い優先度で無線チャネルを使用するに値する可能性が高いので、より低い位置インデックスを有する移動デバイス(LPGの前方部分にある移動デバイス)に、より高いアクセス優先度が与えられる。
【0064】
図6は、本発明の一実施形態による、位置ベクトルV510を作成する方法を示す。その過程は、ステップ600において、移動デバイス、たとえばノードNがLPGに参加するときに、位置インデックスIを初期化することによって開始する。ノードNが、既にLPG内にある少なくとも1つの他の移動デバイス(たとえばノードL)からメッセージを受信することにより、このノードと接触する。ステップ602において、ノードNは、ノードLのGPS位置を含む受信メッセージに基づいて、ノードLの位置を知る。ノードNは、受信した位置情報と、自らのGPS情報とを比較し、その比較に基づいて、ベクトルV510の中に自らを挿入する。その後、ノードNは、LPG内の他の移動デバイス(たとえばノードL)に、新たな位置ベクトルV510を送信する。たとえば、ノードNがノードLの前方にあり、ノードLがNのインデックスを有する前方端位置であった場合には、ステップ605において、ノードNは自らに、その位置インデックスとしてN−1の値を割り当て、LPGの新たな前方端になる。一方、ノードNがノードLの後方にあり、Lがnの指標を有する後方端位置である場合には、ステップ610において、ノードNは自らに、その位置インデックスとしてN+1の値を割り当て、その後方端位置を引き継ぐ。
【0065】
nのインデックスを有する移動デバイス(たとえばノードL)が前方端でも後方端でもない場合には、ノードNはLPGの中央に参加している。その際、ノードNは、上述したように、ステップ615において、GPSとノードLとを比較することによって、自らを位置Vの中に挿入し、その後、ステップ620において、挿入点の後方にある全ての移動
デバイスのインデックスの更新をトリガする。その際、挿入点の後方にある他のノードは、そのGPS位置の変化に基づいて、その位置インデックスを更新する。
【0066】
別法では、新たなノード又は移動デバイスの挿入時に他の移動デバイスの更新を自動的にトリガする代わりに、新たな移動デバイスはインデックスn+1を割り当てられ、nよりも大きな指標を有する全ての移動デバイスが、それらの指標を1だけインクリメントする。
【0067】
位置ベクトルV510を自動的に更新したりインクリメントしたりすることに対する別の代替形態は、所定の位置インターバル内にある他の移動デバイスをインクリメントすることである。これは、インデックス更新の頻度を削減するであろう。中央に参加するノードNは、nとn+Kとの間の値のインターバルから得られるインデックスを割り当てられ、n+Kよりも大きな位置を有する移動デバイスのインデックスをインクリメントする必要はない。このインターバル(n〜n+k)の中にある移動デバイスだけが、それらの位置インデックスを更新する必要がある。
【0068】
さらに、LPG内の移動デバイスの相対的な順序を維持するために、すなわち、移動デバイスがLPGに参加したときに、位置ベクトルV510を更新することができる。各移動デバイスは、その位置インデックスを周期的に更新することができる。LPG内の移動デバイスの位置インデックス(i)は、位置ベクトルV510がLPG内の移動デバイスの現在の相対的な位置を含むように維持することができる。詳細には、移動デバイスがすれ違って相対的な位置を変わるときに、位置インデックスを更新することができる。移動デバイスの位置インデックスは、2つの移動デバイスがその相対的な位置を入れ替えるときに入れ替えられる。たとえば、周期的なインターバルで、移動デバイスは、そのGPS位置を交換又は送信し、それらの相対的な位置が入れ替わった場合には、位置インデックスを入れ替える。その周期は、ネットワークのタイプ、地形、時刻、交通パターン及びメッセージのタイプ、又はLPGの位置に基づいて調整することができる。たとえば、移動デバイスが出口/入口ランプ又は交差点の周囲にあるときに、更新の頻度が高くなり、出口/入口ランプ間又は交差点間にあるときに更新の頻度が小さくなる。更新インターバルを大きくすることによって、順序付けの整合性を維持するためのオーバーヘッドを削減することができる。
【0069】
しかしながら、GPS又は位置情報の交換は、道路環境において特に欠点を有する。具体的には、LPG内の移動デバイスの数によって、(相対的な位置の変化に追従し続けようとして)大量のGPS座標が絶えず通信されることになる。さらに、GPS座標の誤差が移動デバイスの離隔距離と同じ桁になる可能性があるので、結果として行われる位置計算が十分に正確でないことがある。さらに、上記の方法は、大量の計算を必要とし、一般的に、GPS情報は、他の移動デバイスがそれらの情報を受信するときに既に古くなっている。
【0070】
別の実施形態では、移動デバイスの相対的な順序を、GPS情報を用いることなく、メッセージ及び位置ベクトルを用いることによって求めることができる。上記のように、GPS手法を用いて順序付けを維持することは、著しいオーバーヘッドを被ることがあり、移動デバイスの数が多くなる場合には特にそうである。この実施形態では、LPGが、いくつかの小さなグループ、すなわち等価セル(EC)に分割される。各ECは、1つの位置インデックスを割り当てられる。ECは、同じ無線通信エリア内にある、近接する移動デバイスのグループである。ECは、そのEC内の全ての移動デバイスが同じベクトル指標を有するLPGの1つのセグメントであり、メッセージ伝送は中継を要せずにEC内の全ての移動デバイスで受信することができる。
【0071】
ECを基本ユニットとして用いて情報を広めるために、ECは他のECとリンクするように形成される。図7は、LPG700内の複数のEC(EC1〜5)701〜705を示す。EC701〜705は、LPG700内に、無線通信エリアが重なり合うように配置することができる。図7に示されるネットワークでは、LPGの相対的な順序がEC間で維持され、オーバーヘッドを低減する。さらに、EC当たり一度だけメッセージが中継され、帯域効率を改善する。
【0072】
たとえば、1つのEC内の移動デバイス間は、1回のパケット伝送で通信できる。各ECは、必要に応じて、EC内のいくつかの移動デバイスがパケットを中継することができるように編成される。ECはLPG内で順序付けすることができ、メッセージがECに沿ってホップできるようにする。具体的には、EC3 703内の1つの移動デバイスがパケットを送信したい場合には、その移動デバイスはパケットを(一度だけ)隣接するEC2 702及びEC4 704に送信する。これにより、EC2 702及びEC4 704内の全ての移動デバイスにパケットが確実に届けられる。このパケットは、EC2 702及びEC4 704によって、それらの個々の隣接するECに、EC当たり1パケットだけ中継される。このタイプの、隣接セル当たり1パケットだけ行われる隣接EC間ルーティングは、LPG内のパケット伝送を最小限に抑えることができる。
【0073】
ECは、1つの等価セルヘッダ(ECH)によって維持及び制御される。各ECH711〜715は、その隣接するECHとリンクされ、LPG内の全てのECH711〜715が、直接又は間接のいずれかによって、シリアルにリンクされるようになる。ECH711〜715は、無線ホップカウントの順序で接続され、そのLPGのための転送ノードを務める。ECH711〜715だけがメッセージを中継するための役割を担い、それにより、不要なトラフィックが最小限に抑えられる。
【0074】
この実施形態では、ECHは自らを順序付けし、それらの順序を維持して、LPGのための順序付けを達成する。各ECHは、予め規定されたメッセージを送信することによって、そのLPG内で自らの存在を通知する。このメッセージは周期的に送信され、リンクされたECHのリストを通知する。すなわち、このメッセージは、送信するECHから見た位置順序の1ホップ先、2ホップ先、3ホップ先のECHノードを含む。そのリストは、他のECHによって受信され、それにより、他のECHは、自らのリストを更新し、そのリストをメモリに格納する。非ECH720も自らのリストを更新する。これにより、全てのECHリストが互いに一致するようになる。そのリストは、各ECHの相対的な順序を表す。これは、移動の方向及び伝送の方向の判定を容易にする。
【0075】
一実施形態では、送信メッセージは、メッセージを発信する発信元のIDと、順序付けして接続されるECの第1の通信経路に沿って発信元が見ることができるECHノードの第1のリストと、オプションで、順序付けして接続されるECの第2の通信経路に沿った第2のリストとを含む。さらに別のリストが提供されることもあり、各リンクECH(LECH)リストは、発信元ECHを中心にして、順序付けして接続されるECの1つのブランチ、すなわち通信経路に沿って出会う全てのECHノードのECH IDを含む。
【0076】
たとえば、各ECHは、その直に隣接するECHの相対的な位置を知っている。すなわちEC3 703のECHは、EC2 702及びEC4 704のECHによってそれぞれ送信されるリスト又はベクトルに基づいて、EC2 702及びEC4 704のECHが異なる方向にあることがわかっている。EC3 703のECHは、この情報を含むメッセージを送信する。さらに、EC2 702のECHは、EC1 701及びEC3 703のECHによってそれぞれ送信されるリスト又はベクトルに基づいて、EC1
701及びEC3 703のECHが異なる方向にあることがわかっている。この情報が組み合わせられ、各ECHが維持するリストとして格納される。
【0077】
その結果、ECHの相対的な順序を用いることによって、GPS情報を全く用いることなく、適当な方向にメッセージをルーティングすることができる。
【0078】
別法として、別の実施形態では、全ての移動デバイスが、重要な方向(たとえば、前、後、左及び右並びに取り得る斜めの方向)への指向性アンテナを備えており、これらの方向における他の移動デバイスの存在を検出することができる。任意の移動デバイスが、メッセージがピアグループの後方に向かって進んでいくように指示することができ、その後方を指している指向性アンテナにおいてのみメッセージを送信し、このメッセージを受信する移動デバイスは、その後方を指しているアンテナにおいてのみ中継することができる。この手法は、基本的な方向検出を提供するが、移動デバイス間の相対的な位置を提供しない。
【0079】
本発明による移動デバイスは、その移動デバイスに取り付けられるか、内蔵されるか、又はそれと組み合わせて用いられる無線デバイスを含む。図8は、本発明による無線デバイスを示す。本発明による無線デバイスは、無線通信範囲内のノード間での無線通信を提供するために、無線トランシーバのような送信手段802を有するコンピューティングデバイス800を含む。さらに、制御手段804、たとえばマイクロコントローラ、マイクロプロセッサ等が、送信手段802を通して他のノードから信号を受信するとともに、送信手段802を通して他のノードに信号を送信するように構成される。また制御手段804は、命令を実行することによって、動作制御も提供する。記憶手段806が、コンピューティングデバイス800内に配置され、制御手段804と動作可能に通信する。記憶手段806として、メモリモジュール、取外し可能媒体、多数の記憶デバイスの組み合わせ等を用いることができ、その記憶手段は、上記の実施形態のプロトコルを実行するために必要とされるプロセッサ実行可能命令を格納するだけの容量を有する。さらに、タイミング手段808が、別個の構成要素として、又は制御手段804の1つの機能によって設けられる。タイミング手段808は、上記の実施形態において参照された各タイマに必要とされる、時間インターバルの追跡を提供する。必要に応じて構成要素に動作電力を供給するために、電源のような電圧供給手段810が、コンピューティングデバイス800の全ての構成要素に電気的に接続される。その無線デバイスは、無線デバイスのためのクロックを維持する内部クロックをさらに備え、全てのメッセージのためのタイムスタンプとして用いられる。さらに、その無線デバイスは、アドレス割当て手段812と、ネットワークインターフェース手段814とを備える。別法では、アドレス割当て手段812は、制御手段804の一部にすることができる。
【0080】
上記の実施形態を実行するためのプロセッサ実行可能命令は、EPROM、フラッシュメモリ、又は他のそのような不揮発性記憶装置の形をとる記憶手段806に内蔵することができる。さらに、プロセッサ実行可能命令は、光媒体又は磁気媒体のようなコンピュータ読取り可能媒体上に格納することができるか、又はネットワーク(たとえば、インターネット)を介してダウンロードすることができる。ユーザは、必要に応じて、システムをさらに強化するために、利用可能になり次第プロセッサ実行可能命令を定期的に更新できることが好ましい。
【0081】
各移動デバイスは、固有の識別子を割り当てられ、アドホックネットワークを介してメッセージを送信及び受信するのを容易にするであろう。固有の識別子は、1つのLPG内の移動デバイスが同じ固有の識別子を割り当てられないように、移動デバイスに固有に割り当てられる任意の番号を用いることができる。この識別子は、即時通信に対応するために、必要に応じて、迅速に割り当てられなければならない。上記のように、固有の識別子は、MACアドレス、VIN番号又はIPアドレスのような、通信を容易にする任意の番号又はアドレスを用いることができるが、ここでは例示を目的として、IPアドレスの割
当てについて説明する。通常、移動デバイスは少なくとも1つのIPアドレスを有する。しかしながら、一実施形態では、LPG内通信及びLPG間通信の両方に対応するために、移動デバイスに2つのIPアドレスが割り当てられる。
【0082】
好ましい実施形態では、IPアドレスは、専用のネットワークプレフィックス、LPGの固有の識別子及び移動デバイスの識別情報に基づく。具体的には、IPアドレスは、特定の移動デバイスに対応する固有の番号に所定のネットワークプレフィックスを連結したものに基づいて割り当てることができる。ここで、固有の番号は、移動デバイスが存在するLPG、及びその移動デバイスに対応する番号に基づく。
【0083】
固定LPG及び動的LPGの両方に対してアドレスを割り当てるために、類似の割当て技法を用いることができるが、アドレスの割当てを、LPGのタイプ毎に個別に説明する。
【0084】
固定LPGの場合、本発明の一実施形態では、IPアドレスは、MACアドレス及びVIN番号又は時刻のハッシュ値と連結される標準的なネットワークプレフィックス及びLPG IDであってもよい。ハッシュ関数の使用は、アドレス空間に限りがある場合、すなわちIPv4の場合に特に重要である。この実施形態によれば、移動デバイスは、その自らのIPアドレスを割り当てるであろう。
【0085】
理想的な状況では、LPGは、アドレス空間の制約が実質的に問題にならないように、N個(Nは最大アドレス空間)の移動デバイスだけを有する。これにより、LPG毎にプライベートクラスを簡単に割り当てることができるようになる。LPG内の各移動デバイスは、IPアドレスの異なる下位部分を有する。このIPアドレスは、LPGが互いに接近していない限り、異なるLPGにおいて再利用することができる。
【0086】
しかしながら、典型的には、LPGはN個の移動デバイスよりも多くなることがある。したがって、所定のハッシュ関数が、移動デバイスのメモリセクションに格納されるで。アドレス割当て手段812は、メモリからのこの所定のハッシュ関数にアクセスして、IPアドレスの下位部分を割り当てる。ハッシュ関数は、複数の入力番号を、Mビット(MはIPアドレスの下位部分のビットの最大数)の番号に変換する。その複数の入力番号は、VIN番号、MACアドレス及び移動デバイスがLPGに参加した時刻を含むことができる。
【0087】
標準的なネットワークプレフィックスは、IPアドレスの上位部分である。標準的なネットワークプレフィックスもメモリに格納される。さらに、IPアドレスはLPG特有である。IPアドレスの一部を用いて、移動デバイスが位置する特定のLPGが特定される。LPGの位置及び関連するLPG IDのデータベースもメモリに格納される。移動デバイスが新たなLPGエリアに入るとき、移動デバイスは、そのIPアドレスを変更して、そのLPGに関連付けられる特定のIPアドレスを反映しなければならない。固定LPGの利点は、LPG位置が固定されており、明確であることである。これにより、LPG
IDを簡単に付与できるようになる。
【0088】
別法では、本発明の別の実施形態において、IPアドレスの一部又はアドレス全体が、LPG内の固定無線デバイスによって割り当てられることができる。たとえば、IPアドレスの一部は、移動デバイスがLPGに入ったシーケンス又は順序を表すことができる。この場合、入ってくる移動デバイスに対してシーケンス番号を送信する外部無線デバイスが必要となる。問い合わせ−中継−応答タイプの動作を通して、接続を確立することができる。新たな移動デバイスがLPGに入るとき、その移動デバイスは(送信を通して)問い合わせを行う。その問い合わせは、LPG内の他の移動デバイスによって、所定の外部
無線デバイスまで中継される。その外部無線デバイスは、路側ゲートウエイデバイス、リーダのような別の移動デバイス、又はLPG内の第1の移動デバイスを含むことができる。外部無線デバイスは、DHCPサーバとしての役割を果たす。
【0089】
外部無線デバイスは、シーケンス番号又はIPアドレスを生成し、応答を送信することによって問い合わせに応答する。このシーケンス番号は、ハッシュ値の代わりに、IPアドレスの下位部分として用いられる。シーケンス番号は、先に述べられたように、IPアドレスの上位部分と連結される。この方法を用いると、IPアドレスは、移動デバイスが絶えず動く結果としてシーケンスが変更されるときに、連続して変化する可能性がある。別法では、アドレス全体を、LPGに入る移動デバイスに送信することができる。
【0090】
本発明の別の実施形態では、IPプロトコルが広範なIPアドレスに対応する場合には、IPアドレスは、全MACアドレス又はVIN番号と連結される標準的なネットワーク識別子であってもよい。たとえば、IPv6プロトコルを用いるとき、ハッシュ関数を必要とすることなく、固有のアドレスを各移動デバイスに割り当てるための大量の空間が存在する。IPアドレスの上位64ビットはLPG ID専用にすることができ、下位のEUI64ビットは、MACアドレス又はVIN番号から直に計算することができる。
【0091】
IPアドレスの上位部分は、標準的なネットワークプレフィックス及び固有のLPG IDを含むことができる。下位のEUI部分は、MACアドレス又はVIN番号のそれぞれを含む。
【0092】
図9は、IPv4プロトコルに従ってIPアドレスを割り当てる一例を示す。図9は、4つの重なり合うLPG、LPG1 901、LPG2 902、LPG3 903及びLPG4 904を示す。IPアドレス内の最初の2つの3桁数字905は、標準的なネットワークプレフィックス「192.168」を表す。標準的なネットワークプレフィックス「192.168」は、ネットワーク内の全てのLPGの場合に同じである。第3の3桁数字906はLPG IDであり、LPG特有である。図9に示されるように、LPG1 901、LPG2 902、LPG3 903及びLPG4 904はそれぞれ、第3の3桁数字906内に1、2、3、4の値を有する。第4の3桁数字907は、個々の移動デバイスの識別情報を表す。この番号は、移動デバイスに基づいて変わる。この番号は、上記の実施形態のうちのいずれか1つを用いて割り当てることができる。
【0093】
図10は、IPv6プロトコルの場合のIPアドレスのための1つの例示的なフォーマットを示す。例示の目的で、図10では、図9で用いられたものと同じLPG参照符号を用いる。上位部分1000は、64ビットになるように示されており、LPG IDを表し、下位部分1001も64ビットであり、移動デバイスの識別情報(EUI)を表す。上位部分1000及び下位部分1001はいずれも、固定LPG毎に異なる。
【0094】
さらに、上述したように、移動デバイスにLPGを円滑に変更させるために、且つLPG間通信を支援するのを容易にするために、固定LPG間に、或る重なり合うエリアが存在することがある。好ましい実施形態では、重なり合うエリアでは、各移動デバイスが2つのIPアドレスを有し、両方のLPGにアクセスできるようにする。移動デバイスが重なり合うエリアに接近すると、アドレス割当て手段812は、その移動デバイスに対して第2のIPアドレスを割り当てる。具体的には、その移動デバイスは、メモリ内に格納される重なり合うエリアの位置を現在の位置と比較し、自分が重なり合うエリア又は境界エリアに位置するか否かを判定する。無線デバイスは、ネットワークインターフェース手段814(すなわち、802.11カード)を有する。1つの物理無線インターフェースによって、多数の論理インターフェースに対応することができる。各論理インターフェースは1つのIPアドレスを有する。それゆえ、各ネットワークインターフェース手段814
は、2つ以上のIPアドレスを有することができる。各IPアドレスは、上記で特定した実施形態のいずれかに従って割り当てることができる。
【0095】
動的LPGの場合にも、固定LPGに対するIPアドレス割当てと類似の技法を利用することができるが、動的LPGに対するIPアドレス割当ては、より動的である。これは、LPGの位置がもはや固定されていないためである。さらに、LPG IDも一定ではなく、絶えず変化する。さらに、動的LPGの場合には、LPG間通信へのIPアドレスの割当てが異なる。
【0096】
動的LPGのためのPLG内IPアドレス割当ての場合、その技法は、IPv4の場合の固定LPGにIPアドレスを割り当てるために用いられる技法と概ね同様である。図11a及び図11bは、IPv4プロトコルの場合のIPアドレスフォーマットの2つの異なる例を示す。いずれのフォーマットでも、IPアドレスの上位部分、すなわち最初の2つの3桁数字1100は、標準的なネットワークプレフィックス、たとえば、192.168、10.0及び172.12によって決定される。一実施形態では、標準的なネットワークプレフィックスは、プライベートアドレスになる。標準的なネットワークプレフィックスは、そのアドレスの最初の2つの3桁数字になるであろう。
【0097】
第3の3桁数字1101はLPG IDである。一実施形態では、LPG IDはランダムに生成される。第4の3桁数字は、移動デバイスの識別情報である。この識別番号は、図11aに示されるように、VIN又はMACアドレス1102aのハッシュ関数に基づいて割り当てることができるか、又は図11bに示されるように、移動デバイスがLPG1102bに入るシーケンスに基づいて割り当てることができる。ハッシュ関数及びシーケンシングは、固定IPアドレス割当てに関して先に説明されており、さらに説明はしない。
【0098】
このIPアドレスによって、LPGの中で通信、すなわちLPG内通信が可能となる。しかしながら、LPG間通信のためには、移動デバイスに対して、別個のIPアドレスが割り当てられなければならない。これは、公開IPアドレスになるであろう。この公開IPアドレスは、DHCPサーバとして動作する外部の無線デバイスによって、又はDHCPとして動作する別の移動デバイスによって割り当てることができる。このアドレス割当ては、移動デバイス(LPGの代表者としての役割を果たす)と外部デバイス(DHCPサーバとしての役割を果たす)との間のDHCPプロトコルに従う。
【0099】
本発明の一実施形態では、LPG内の1つの移動デバイスは、IPv4プロトコルを用いて、LPG間通信のための公開IPアドレスを割り当てられる。図12aに示されるように、1つのノード1202は、公開IPアドレスIPA1204を割り当てられる。このノード1202は、LPG内の最初の移動デバイス、リーダとして選択される移動デバイス、又は別の所定の選択判定基準に基づいて選択される移動デバイスであってもよい。別法では、その選択はランダムに行うことができる。残りのノード1201は、公開IPアドレスIPA1204を割り当てられない。
【0100】
別の実施形態では、所与のLPG内の各移動デバイスには、異なるIPアドレスが割り当てられる。図12bに示されるように、LPG1200は6つのノード1201を有する。各ノード1201は、異なるIPアドレスIPA1204〜IPF1209を割り当てられるであろう。
【0101】
第3の実施形態では、LPG内の全ての移動デバイスに対して、ただ1つのグローバル公開IPアドレスが割り当てられる。図12cに示されるように、LPG1200内の各移動デバイス又はノード1201には、同じ公開IPアドレス1204が割り当てられる
。この公開IPアドレス1204は、インターネットを介して通信するために、他のノードによってグローバルに認識することができる。たとえば、公開IPアドレスは239.5.5.5にすることができる。
【0102】
IPv6プロトコルの場合、LPG内通信のためのIPアドレスを割り当てるために2つの異なる方法がある。IPv6プロトコルを用いる無線デバイスは、2つの自動設定機能、すなわちリンクローカルアドレス及びルータ広告アドレス設定機能を有する。
【0103】
図13a及び図13bは、LPG内通信用のIPアドレスのフォーマットの2つの異なる例を示す。図13aに示されるように、第1の手法は、リンクローカルアドレス1300、たとえばfe80を用いる。リンクローカルアドレス1300は、IPアドレスの上位部分になる。下位部分、すなわちEUI1302は、64ビットであり、MACアドレス及び/又はVIN番号から計算される。しかしながら、リンクローカルアドレス手法は、LPG内においてのみ有効であり、LPG間通信のための第2の付加的なアドレスを必要とする。
【0104】
第2の手法は、図13bに示されるように、サイトローカルのような手法、又はルータ広告アドレスを用いることである。そのネットワークは、移動デバイスのネットワーク又は車両ネットワークに専用の所定の移動デバイスのプレフィックス1301を含む。この移動デバイスのプレフィックス1301は、「XXXX」1303として図13aに表されるように、上位64ビットになるようにLPG IDと組み合わせられる。下位64ビット、すなわちEUI64 1302は、図13aの場合と同じになるであろう。それゆえ、EUI64の番号は、両方のフォーマットの場合に同じになり、その差は、IDアドレスの上位部分である。
【0105】
両方のフォーマットにおいて、アドレスの一部として、LPG IDが用いられる。LPG IDは、LPG毎に固有でなければならない。本発明の一実施形態によれば、LPG IDは、ランダムに割り当てられる番号か、又はハッシュ関数によって予め定義される番号のいずれかであってもよい。ハッシュ関数は、LPGの位置、入手可能であるなら、LPG内の第1の移動デバイスのMACアドレス、又はLPG内の第1の移動デバイスのVIN番号から成ることができる。
【0106】
LPG間アドレスを割り当てる場合、一実施形態では、外部無線デバイスを用いて、IPアドレスの一部が割り当てられる。外部無線デバイスとして、LPGに対して、そのアドレス範囲及びプレフィックスを送信する、路側ゲートウエイ又は境界ルータのような任意のデバイスを用いることができる。ネットワークプレフィックスは、それらのゲートウエイ(ルータ)広告から入手することができる。受信されたネットワークプレフィックス1400は、IPアドレスの上位部分、たとえばIPアドレスのためのグローバルディレクトリとして用いられるであろう。IPアドレスの下位部分は、LPG内通信IPアドレスのために用いられるのと同じEUI番号64 1302を用いることができる。
【0107】
別の実施形態では、所定の車両又は移動デバイスのプレフィックス1301が作成され、各移動デバイスのメモリセクションに導入される。この移動デバイスのプレフィックス1301を、LPG ID1303と組み合わせて、上位64ビットが形成される。LPG IDは、LPG毎に固有でなければならない。本発明の一実施形態によれば、LPG
IDは、ランダムに割り当てられた番号か、又はハッシュ関数によって予め定義された番号のいずれかであってもよい。ハッシュ関数は、LPGの位置、入手可能であるなら、LPG内の第1の移動デバイスのMACアドレス、又はLPG内の第1の移動デバイスのVIN番号から成ることができる。IPアドレスの下位部分は、LPG内通信IPアドレスのために用いられるのと同じEUI番号64 1302を用いることができる。
【0108】
一実施形態では、任意の移動デバイスに、任意のIPアドレスを割り当てることができる。別の実施形態では、種々のクラスの移動デバイスのために、特定のIPアドレスを予約することができる。たとえば、緊急車両は、特定の範囲のIPアドレスを割り当てられることができる。この範囲内のIPアドレスは、救急車、パトカー及び消防車のような緊急車両のために保存される。外部無線デバイス又はゲートウエイは、特殊な移動デバイスを認識しており、特殊な移動デバイス又は移動デバイスの分類のリストをメモリ内に格納している。これらの特殊車両は、IPアドレスを要求するために特殊な問い合わせを用いなければならない。
【0109】
これによって、緊急車両からの優先メッセージが容易になる。言い換えると、特定の範囲のIPアドレスから発信される全てのメッセージは、伝送のために最も高い優先度を有する。
【0110】
本明細書において、本発明が、特定の例示的な実施形態を参照しながら説明されてきた。本発明の範囲から逸脱することなく、当業者には、特定の改変及び変更が明らかになり得る。例示的な実施形態は、例示することを意図しており、添付の特許請求の範囲によって規定される本発明の範囲を制限することは意図していない。
【技術分野】
【0001】
[発明の背景]
[発明の分野]
本発明は移動環境における通信のためのアドホック無線ネットワークに関する。より具体的には、本発明は、通信をほぼ瞬時に達成するために、移動デバイス間にアドホック無線ネットワークを確立及び維持することに関する。
【0002】
[関連出願]
本出願は、2005年1月11日に出願の米国特許仮出願第60/643,373号に関連し、その優先権を主張する。
【背景技術】
【0003】
[関連技術の記載]
無線ホームネットワーク、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワーク、さらには都市全体でWiFi技術を実施することのいずれにしても、無線技術は、今日の生活のあらゆる面において普及してきている。社会においてこのように無線を推し進める目的は、情報を入手しやすくすること、及び、コンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することによって社会全体が享受してきた生産性をさらに高めることである。802.11a/b/gのような無線ネットワーキング技術によって、WiFi機能を搭載したデバイスが、通信線のような制約を受けることなく、標準的な有線ネットワーク内に存在するかのように互いに接続できるようになる。ネットワーク通信エリア内であれば物理的な場所に関係なく、人々は自由に、ネットワークに接続された状態を維持することができる。
【0004】
これを目指して、いくつかの都市が、その都市のための無線ネットワークを構築しようとしてきた。たとえば、2004年7月29日に、ミシガン州グランドヘブンは、6平方マイルの都市を網羅し、ミシガン湖まで15マイルにわたって広がる、都市全域の無線ネットワークを構築して、「全米最初のWiFi都市」であるという栄誉を主張した。多数の市当局者は、WiFiを、下水・電力・電話及び交通機関と同様に企業を誘致・維持するために不可欠なインフラストラクチャと見ている。そのようなシステムの市当局者にとっての利点は、市職員の間での通信手段を提供することから、市民全体に行政サービス告知、注意報及び他の有用な情報を提供することまで多岐にわたる。
【0005】
このような無線での接続性を向上させる流れの中にあって、日常生活の一領域は立ち遅れている。アメリカの道路及び高速道路は、衛星測位システムや携帯電話システム以外の無線技術に関して、ほとんど手付かずのままである。しかしながら、アメリカの道路において無線ネットワーク技術を実施することには数多くの利点がある。最も注目すべきものの中には、交通情報、アンバーアラート、気象注意報等があり、それらの情報は影響がある全ての車両に即座に中継することができる。
【0006】
さらに、自動車を互いにネットワーク化することによって、近くの他の車両に影響がある車両情報を中継できるようになる。たとえば、自動車が突然ブレーキをかけることがある。この動作を、ブレーキをかけている自動車の後方にいる全ての車両に瞬時に報告することができ、それにより、他の車両のドライバが差し迫った状況に陥る前に、必要な措置を講じることができるようになる。この特徴が、交通事故及び交通渋滞を緩和するために意味があることは明らかである。このタイプの無線ネットワーキングは、限定はしないが
、緊急道路障害物警告、交差点での協調、隠れた車道に関する警告、車線変更又は合流の支援を含む、車両安全アプリケーションの数多くの面において現われる可能性がある。
【0007】
車両安全通信(「VSC」)は、大きく、車車間通信とインフラストラクチャを介した車両通信とに分けることができる。車車間通信では、固定されたインフラストラクチャからの支援を受けることなく、車両同士が通信する。車両が互いの無線範囲内にいるとき、または他の車両を介してマルチホップ中継できるときに、車両同士が通信する。インフラストラクチャを介した車両通信では、路側無線アクセスポイントのようなインフラストラクチャの支援を受けて、車両同士が通信する。この場合に、車両はインフラストラクチャだけと通信することもできる。
【0008】
重要なVSC性能要件には、衝突回避のような種々のVSCアプリケーションを支援するために、遅延時間が短いこと(約100ミリ秒)、及びスループットを維持すること(別の言い方をすると、近くにいる車両が警告メッセージを受信するのに成功するパーセンテージ)が含まれる。
【0009】
単に、移動する車両に無線アンテナを取り付けて、その後、協調性なく通信を行うだけでは、これらの要件を満足できないであろう。具体的には、無線帯域幅が限られているため、協調性なくデータを伝送することによって、通信電波が複数のメッセージで溢れることになり、無線波の妨害が生じるであろう。
【0010】
その場合に、これらの車両は、互いの伝送を妨害することになり、伝送用の無線帯域幅を得るために互いに競合することになる。さらに、所望の伝送方向を考慮することなく、全てのメッセージが全ての方向に伝搬することになる。
【0011】
さらに、各車両が他の車両のネットワーク構成と整合しないであろう。
【0012】
移動度が高く、また固有の関係がないので、車両を事前に車両グループとして構成することは難しい(すなわち、どの車両も、予めその近くにいる車両について何も知らない)。車両間安全通信を構築するために必要とされる全ての情報が車両間で概ねリアルタイムに交換されなければならず、また、グループ内の車両は概ねリアルタイムに自らを構成して安全通信を行うことができるようにしなければならない。協調しない車両の移動度が高いということは、近くにいる車両や車両グループが頻繁に変化し、車両グループ内でサポートサーバ(移動度、アドレス、名前、メディアセッションのための)を用いることが難しいということを意味する。これらの重大な違いのせいで、既存のアドホックネットワーキング技術を、安全通信のために車両グループに直に適用できない。
【0013】
ホットスポットのような他の場所で利用されるWiFi方法を用いることは、通信エリア、データトラフィック量、遅延時間の問題のために実用的ではない。大都市の通常のラッシュアワーの通勤は、3車線の高速道路の1200メートル長当たりの車両が600台にもなるという車両密度を生じる可能性がある。さらに、これらの車両は全て、時速30〜60マイルの速度で個々の通信エリアを通り抜けていく。たいていの無線システムは、ネットワーク内でそのような大きな変化率を取り扱うだけの能力がない。
【0014】
具体的には、車両が通信エリアに入るときに、無線アクセスポイントやルータによって識別されるとともに構成命令を受ける必要がある。車両が通信エリアを出るときは、無線アクセスポイントやルータは、レコードを更新して、ネットワークからその車両を削除する必要がある。したがって、特定の通信エリアを車両が通り抜ける速さによって、情報更新の頻度、すなわち無線アクセスポイントやルータによって送信され、その範囲内の全ての車両によって応答されるべきハンドシェーキング要件が決定される。これら全ての車両
が情報を同時に送信すると、すぐにシステムの容量を超えてしまう。
【0015】
車車間通信ネットワークを確立するために、いくつかの試みがなされてきた。たとえば、FleetNetおよびCarTalk2000はいずれも、車車間通信ネットワークを構築する。これらのシステムはいずれも、位置情報を得るために、各車両内でGPSシステムを使用する。FleetNetは、「アドホック」ネットワークのためのインフラストラクチャとして固定ノード及び移動ノードの両方を使用する。固定ノードは、サーバルータやゲートウエイルータやクライアントサーバルータとしての役割を果たす。このように複数の固定ノードを用いると、インフラストラクチャを設置、維持、管理するためにかなりの財務費及び間接費が生じる。さらに、FleetNetシステムは、位置に基づくルーティング及び位置認識を用いる。具体的には、実施される通信プロトコルにおいて、それらのシステムのための重要要素として、位置データが決定的な役割を果たす。
【0016】
CarTalk2000も位置に基づくプロトコルを用いる。CarTalk2000による車車間システムに参加する各車両は、常に現在位置を検出するために、GPSデバイスを搭載していなければならない。さらに、CarTalk2000は、トポロジカル情報ルーティングや、手続き型ルーティング、あるいはアドホック・オンデマンド・ディスタンス・ベクター型プロトコル、ダイナミック・ソース・ルーティング、ハイブリッド・ルーティングなどのリアクティブルーティングのような複数の異なるルーティングプロトコルを用いる。これらのプロトコルはそれぞれ、複雑な別個のプロトコルルールを用いる。
【0017】
CarTalk2000システムの主な欠点は、近くにあるノードを発見することが、データ転送量を著しく増やすことである。各ノードが、周期的にビーコンを送信して、その存在を近くの車両に対して通知する。トラフィックが高いエリアでは、この結果として、ビーコンメッセージが衝突する可能性がある。
【0018】
しかしながら、これらのGPSネットワークは大きな欠点を有する。移動度の高い車両環境では、GPS情報はすぐに有効でなくなる。GPS位置ルーティングを実行するために、車両間で絶えず変化するGPS情報を交換すると、過大なプロトコルオーバーヘッドや無線帯域幅の無駄が生じる。結果として、そのようなGPS位置ルーティング技術は、最低限の通信遅延時間やマルチホップスループットの維持を達成することはできない。
【0019】
したがって、過度の帯域幅や著しいプロトコルオーバーヘッドを必要とすることなく、最低限の通信遅延時間やマルチホップスループットの維持を達成しながら、過酷なVSC性能要件を達成することができるアドホックネットワークを構成することが必要とされている。
【発明の概要】
【発明が解決しようとする課題】
【0020】
[発明の簡単な概要]
したがって、本発明の目的は、複数の移動デバイスをローカルピアグループ(「LPG」)のような管理グループにグループ化することによって、移動デバイス間通信に適した通信境界を作り出し、メッセージ伝送を調整及び中継し、メッセージ伝搬の範囲及び方向を制御することである。さらに、本発明の目的は、ローカルピアグループを確立及び維持し、識別情報を動的に割り当て、移動デバイスの相対的な順序を周期的に更新するための簡単なプロトコルを提供することである。
【0021】
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法が開示される。当該方法は、複数の移動デバイスを少なくとも1つのローカルピアグル
ープ(LPG)にグループ化するステップと、各LPG内の複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の複数のデバイスを順序付けするステップと、複数の移動デバイスのそれぞれに固有の識別子を割り当てるステップとを含み、固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく。
【0022】
2つのタイプのLPG、すなわち固定LPG及び動的LPGがある。固定LPGの位置及びサイズは予め定義されており、各移動デバイスのメモリ内にプログラミングされる。動的LPGは、複数の移動デバイスのうちの1つ又は複数のクラスタリングに基づいて形成される。ネットワークは、固定LPG及び動的LPGのいずれか又は両方を含むことができる。
【0023】
各LPGは、移動デバイスのグループによって定義される等価セル(EC)に分割される。このグループ内の各移動デバイスは互いに1ホップ内に存在し、一度のメッセージ伝送のみによって、このEC内のどの移動デバイスとも通信できる。各ECは、等価セルヘッダ(ECH)によって制御される。
【0024】
移動デバイスの相対的な位置を更新して、複数の移動デバイスの移動によって生じる再順序付けに対処する。順序付け及び再順序付けは、各LPG内の各移動デバイスの相対的な位置を表す位置ベクトルを作成することによって達成することができる。
【0025】
位置ベクトルは、位置ベクトルを初期化し、初期化された位置ベクトルをLPGに参加している別の移動デバイスに送信し、別の移動デバイスが、自身の位置を送信に含まれる位置情報と比較し、その比較に基づいて、この別の移動デバイスの位置値を位置ベクトルに挿入し、更新された位置ベクトルを、LPG内の他の全ての移動デバイスに送信することによって生成される。
【0026】
別法では、移動デバイスの順序付け及び再順序付けは、第1の移動デバイスの位置と意図したメッセージ方向の指示と送信時刻とを含むメッセージを送信し、第2の移動デバイスが、送信メッセージを受信し、受信された送信メッセージに基づいて、第1の移動デバイスの変位を推定し、推定された変位及び第1の移動デバイスの位置に基づいて第1の移動デバイスの現在の位置を計算し、計算された現在の位置と第2の移動デバイスの位置とを比較することによって達成することができる。第2の移動デバイスは、第2の移動デバイスが意図したメッセージ方向に沿っているものと判定されるときにだけ、メッセージを中継又は転送する。
【0027】
移動デバイス毎の固有の識別子はLPG特有である。それゆえ、移動デバイスの固有の識別子は、移動デバイスがLPGを変更するときに変更される。さらに、2つの隣接するLPGの境界付近に、又は隣接するLPGの重なり合うエリア内に位置する移動デバイスは、2つのIPアドレスを割り当てられ、隣接するLPG間で通信できるようにする。
【0028】
この固有の識別子は、IPアドレスであってもよい。IPアドレスは、固有のLPG識別情報及び固有の移動デバイス識別情報と連結される所定のネットワークプレフィックスに基づいて割り当てることができる。固有のLPG識別情報及び固有の移動デバイス識別情報はハッシュ関数から計算することができる。別法では、固有のLPG識別情報及び固有の移動デバイス識別情報は、移動デバイスと通信している外部無線デバイスから与えることができる。
【0029】
移動デバイスはそれぞれ、移動デバイスのタイプに従って分類することができ、この分類に基づいて、固有の識別子を割り当てることができる。
【0030】
本発明のこれらの及び他の特徴、利益及び利点は、添付の図面を参照することによって明らかになるであろう。なお、図面を通して、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0031】
【図1】本発明による2つのローカルピアグループの一例を示す図である。
【図2】本発明による複数の固定LPGを示す図である。
【図3】本発明による複数の動的LPGを示す図である。
【図4】本発明の一実施形態による、「要求に応じて」LPGを順序付けする方法を示す図である。
【図5】本発明の別の実施形態による、移動デバイスを順序付けする一例を示す図である。
【図6】本発明の別の実施形態による、移動デバイスを順序付けする方法を示す図である。
【図7】1つのLPG内の複数のECを示す図である。
【図8】本発明による、移動デバイスに取り付けられるか、又は内蔵される無線デバイスを示す図である。
【図9】上記で特定した実施形態による、IPアドレスを割り当てる一例を示す図である。
【図10】本発明の別の実施形態による、IPアドレスのフォーマットを示す図である。
【図11】動的LPG内の移動デバイスにIPアドレスを割り当てる際に用いられる2つの異なるIPアドレスフォーマットを示す図である。
【図12】本発明による、LPG間通信のためにIPアドレスを割り当てるための実施形態を示す図である。
【図13】動的LPGの場合のLPG内通信用のIPアドレスの2つの異なるフォーマットを示す図である。
【図14】動的LPGの場合のLPG間通信用のIPアドレスの2つの異なるフォーマットを示す図である。
【発明を実施するための形態】
【0032】
[発明の詳細な説明]
本発明によれば、複数のノードすなわち移動デバイスが、管理しやすいグループに編成される。これらのグループを用いて、ノード間のデータ伝送が調整される。グループは、近くにあるノードの相対的な位置に基づいて、又は固定された位置に基づいて構築される。このグループ化すなわちローカルピアグループ(「LPG」)は、単一のLPG内や複数のLPG間での無線信号のルーティングを実施するための基礎となる。無線信号は、車両安全アプリケーションや情報アプリケーションを含む。
【0033】
LPGの目的は、近くにある複数のノード間の連携(coordination)の程度を構築することである。これら近くにあるノードは、無線通信能力を有する移動デバイスである。移動無線デバイスは、PDA、ノートパソコン、携帯電話、又は無線デバイスが取り付けられるか内蔵されている車両であってもよい。具体的には、移動デバイスには、車両内に設置されたり車両内に個別に持ち込まれたりする通信デバイスを備える車両や、通信デバイスを携帯した歩行者が含まれる。
【0034】
連携の程度には、2つのタイプがある。第1のタイプは隣接する移動デバイスの密な連携であり、LPG内通信のために用いられる。LPG内通信は、概ね瞬時のメッセージ伝送の支援に利用される。たとえば、緊急道路障害物警告や他のタイプの緊急メッセージ又は安全メッセージの送信は、LPG内メッセージ伝送を用いて実行されるであろう。これ
らのメッセージは、一般的に、遅延時間が100msec程度であることを要求する。
【0035】
第2のタイプは、緩やかな連携、すなわち近くにある移動デバイスをグループ化することである。このタイプの連携は、リンク又は相互接続されているLPG間のLPG間通信を支援するために用いられる。たとえば、LPG間通信は、道路認識アプリケーションや、ドライバの視界拡張のために用いることができる。
【0036】
LPGは、効率的且つ信頼性のある移動デバイス間通信を支援するだけでなく、移動デバイス及び道路インフラストラクチャを、1つの完全な通信ネットワークとして統合できるように、移動デバイスと固定インフラストラクチャ間の通信も支援することができる。
【0037】
図1は2つのLPGを示しており、第1のLPG100は、4つのノード110、111、112及び113を含む。これら4つのノード110、111、112及び113はそれぞれ、互いにデータを送信することができる。第2のLPG120は、ノード121、122、123、124、125及び126を含む。ノード121〜126はそれぞれ、互いにデータを送信することができる。このタイプの伝送は、LPG内伝送であり、瞬時に行われる。LPG100内のノード110〜113は、LPG間通信を用いることによって、LPG120内のノード121〜126にデータを送信することができる。2つのLPG100、120は、アドホックネットワーク150を形成する。
【0038】
LPGには2つのタイプ、すなわち固定LPG及び動的LPGがある。固定LPGは、予め割り当てられたグループ位置定義を用いて、移動デバイスを分割する。対照的に、動的LPGは、近くにある移動デバイスが通信するための(動的な)無線通信エリアに基づいて、移動デバイスを適当に組み合わせることができる。
【0039】
図2は、複数の固定LPG(LPG1〜8)200〜207を示す。各LPGは、特定の位置又はエリアによって画定される。すなわち無線デバイス又は移動デバイスがエリア1内にある場合には、そのデバイスはLPG1である。無線デバイス又は移動デバイスがエリア2内にある場合には、そのデバイスはLPG2であり、他も同様である。固定LPGの個々のサイズは設計上の選択事項であり、種々の要因、たとえば無線アンテナの範囲、通信範囲、移動デバイスの数、地形、環境条件、交通パターン及び人口密度にしたがって決められる。固定LPGの位置及びサイズは固定であるが、交通パターン及び人口(移動デバイス)密度は場所によって異なるので、各固定LPGは異なるサイズであっても良い。一般的には、LPGサイズを、無線通信範囲よりも大きくして、マルチホップ通信できるようにすべきである。さらに、効率的なLPG間通信を容易にするために、固定LPGは、隣接するLPG間のエリアと重なり合うこともできる。重なり合うエリアは、変化に富んだ状況(たとえば移動デバイスによって速度が異なること)に適応するために、状況に合わせたサイズを有することができる。
【0040】
本発明の一実施形態によれば、固定LPGのための境界は、郵便番号や市外局番のような所定のエリアに基づく。通常、郵便番号は人口密度に相当する。或るエリアの人口密度は、そのエリア内の交通パターンや移動デバイスの数の良好な指標である。
【0041】
固定LPGに基づくネットワークアーキテクチャでは、移動デバイスが、全地球測位システム(GPS)又は他の何らかの位置情報を備える必要がある。これにより、移動デバイスは、その移動デバイスが属する固定LPGを特定又は検出できるようになる。移動デバイスは、位置を変更するのに応じて、固定LPGを変更する。それゆえ、移動デバイスは、更新された位置データを周期的に受信する必要がある。この周期は、移動デバイスが移動する速さ又は速度に依存する。移動デバイスは、LPG及びそれらの位置のデータベースを含む。
【0042】
固定LPGは、いくつかのLPGが空であったり、LPG内に多数の移動デバイスがないときであっても、無線インフラストラクチャと統合して、バックボーンアクセスやLPG間通信を提供できるという大きな利点を有する。
【0043】
各固定LPGは、通信を容易にするために、固有の識別子を割り当てられる。本発明の一実施形態では、固定LPGのための固有の識別子は、そのLPGの郵便番号に基づいて割り当てられる。この方法は、既存の郵便番号データベースを活用する。したがって、新たな識別番号を作成する必要はない。別法として、別の実施形態では、固定LPGのGPS座標を用いることができる。同じように、その方法は、あらかじめ定められたデータベースを利用する。別の実施形態では、LPGの固有の識別子として、州名及び都市名を用いることができる。別法では、上記の実施形態の任意の組み合わせを用いて、LPG固有の識別子を割り当てることができる。LPGの固有の識別子は、後に説明されるように、移動デバイスの固有の識別子の一部として用いられる。
【0044】
全ての固定LPGエリアは明確であるので、LPGを形成及び命名するのは、動的LPGよりも容易である。さらに、固定LPGを用いるとき、LPGの合併や分割に関するルールを心配する必要はない。
【0045】
図3は、複数の動的LPG(LPG A〜E)、それぞれ300〜304を示す。固定LPGとは対照的に、動的LPGは、移動デバイスがその厳密な位置を気にすることなく通信を連携できるように、近くにある移動デバイスの無線通信エリアに基づいて形成される。
【0046】
動的LPGは無線通信エリアに基づいて形成されるので、そのLPG内の移動デバイスは常に、1ホップ又はマルチホップの伝送を介して、互いに通信することができる。各LPG内の移動デバイスの数を適度に少なく保持し、通信を短い遅延で効率的に実行できるようにするために、移動デバイスは動的LPGのサイズを制御することができる。さらに、固定LPGとは対照的に、動的LPGは、各LPG内で常に通信が可能であることを保証する。
【0047】
一実施形態では、アドホックピアツーピアネットワークを、1つ又は複数の固定LPGから構築することができるし、1つ又は複数の動的LPGから構築することもできる。別の実施形態では、アドホックピアツーピアネットワークは、固定LPG及び動的LPGの両方から、ハイブリッドLPGネットワークとして構築することができる。ハイブリッドLPGネットワークは、固定LPG及び動的LPGを別個に採用した場合に生じる問題を取り除きながら、それぞれの利点を兼ね備える。
【0048】
固定LPGの利点のうちの1つは、エリアによって移動デバイスを容易にグループ化することができること、及びインフラストラクチャとやりとりできることである。さらに、後で詳細に説明されるように、固定LPGによれば、移動デバイス毎にアドレス指定用識別子すなわち固有の識別子を簡単に割り当てることができるようになる。さらに、全てのノードが、ネットワーク全体のトポロジ及び構造を把握している。それゆえ、ノード又は移動デバイスを容易に追跡することができる。
【0049】
動的LPGにはいくつかの利点がある。それらの利点のうちの1つは、ネットワークがノードのクラスタリングに基づいて形成されるので、動的LPGは事前の設定が必要ないことである。さらに、動的LPGは、LPGの形成や合併、分割をより自由に行うことができ、一度形成されると、全ての車両が一斉に通信することができる。それゆえ、近くにある移動デバイス間での通信がさらに容易である。
【0050】
固定LPGの欠点は、より広くに遍在する路側無線アクセスポイント、路側ゲートウエイ、路側データ記憶装置(入力(deposit)及び検索用)を必要とすることであり、動的LPGの場合に不要であるのとは対照的である。
【0051】
ハイブリッド手法は、道路の敷設状況(topology)を利用する。具体的には、インフラストラクチャが利用できないとき、動的LPGを用いて、ネットワークが形成される。或るエリアにおいて、インフラストラクチャを利用できるようになるとき、固定LPGを用いて、動的LPG及びインフラストラクチャとともにネットワークを形成することができる。
【0052】
たとえば、道路インフラストラクチャのようなインフラストラクチャによって、路車間通信及び道路支援(車路車間)通信を実現できるようになる。これは、固定LPGを用いるときに特に有用である。さらに、道路インフラストラクチャは、インフラストラクチャから車両への通信を容易にする。このタイプの通信は、隠れた私道に対する警告、電子道路標識、路面条件、踏切警告、経路案内及びナビゲーション、ハイウエイ合流支援、交差点衝突警告、及び工事区間警告等の、特定の緊急情報を行き渡らせるために重要である。
【0053】
LPGには主に2つの種類がある。1つは順序付けされないLPGであり、もう1つは相対的に順序付けされるLPGである。相対的に順序付けされるLPGでは、移動デバイスのうちの少なくともいくつかが、近くにある移動デバイスの相対的な位置を認識する。相対的な順序付けは、LPG内でメッセージをルーティングするための基礎である。近くにある移動デバイスの相対的な順序や相対的な方向を検出・認識できると、LPG環境内でのメッセージルーティングを効率的に行えるようになる。この効率的なルーティングは、メッセージが道路環境における緊急メッセージであるときに重要である。たとえば、或る車両によって、警告メッセージがLPGの後方に進むように指定されることがある。LPGにおいて送信する車両の前方にある車両は、そのメッセージを受信又は中継する必要はない。その車両は相対的な方向がわかるので、適当な方向に向かってメッセージを誘導し、それにより、中継トラフィック及び使用される帯域幅の量を削減することができる。
【0054】
方向の検出又は認識は、移動デバイスの相対的な順序から導出することができる。一実施形態では、相対的な順序付けは、「必要に応じて(on-demand)」行われる。別の実施形態では、相対的な順序付けは周期的に維持される。
【0055】
図4は、本発明の一実施形態による、「必要に応じて」LPGを順序付けする方法を示す。その過程は、ステップ400において開始する。第1の移動デバイスが。その移動デバイスのGPS位置、現在の速度及びタイムスタンプを含むメッセージを、意図したメッセージ方向とともに送信する。ステップ410では、第2の移動デバイスがこのメッセージを受信する。ステップ420において、第2の移動デバイスは、第1の移動デバイスの現在の位置を推定する。第1の移動デバイスの現在の位置の推定は、既にわかっている第1の移動デバイスの以前の位置からの第1の移動デバイスの起こり得る変位に基づいて行うことができる。以前の位置は、受信されたメッセージから直に求められる。起こり得る変位は、推定された速度及び時間差に基づいて計算される。受信されたメッセージはタイムスタンプを含むので、第2の移動デバイスは時刻、すなわちそのタイムスタンプから、メッセージが受信された時刻までの差を計算する。この場合、それらの移動デバイスにおいて、クロック及びGPS情報の両方の時間が同期している、すなわちGPSデバイスが同期している必要がある。推定速度は、いくつかの異なる態様で計算することができる。一実施形態では、第1の移動デバイスの(瞬間)速度は、第1の移動デバイスによって送出されるメッセージに含まれる。この速度は、第2の移動デバイスが第1の移動デバイスの現在の速度を推定する際に用いることができる。別の実施形態では、第2の移動デバイ
スは、第1の移動デバイスの速度として自らの速度を用いることができる。別法では、予め決定された推定速度を用いることができる。予め決定された推定速度は、制限速度、時刻、場所、気象条件及び地形に基づいて変わることがあるデータベースとして、移動デバイスのメモリ内に予め格納されるであろう。第2の移動デバイスは、推定速度と、時間差とを乗算して、起こり得る変位を求める。この値は、以前の位置からの起こり得る変位であり、第1の移動デバイスの以前の位置を調整して、第1の移動デバイスの推定位置を求めるために用いられる。
【0056】
本発明の一実施形態では、第1の移動デバイスの変位は、向きの成分を有する。この実施形態では、推定される変位は、向きの変化を考慮に入れる。第1の移動デバイスの以前の位置に、位置の変化が移動方向に対して加えられる。一実施形態では、第1の移動デバイスは、そのメッセージ内にGPSの向き(たとえば、NW、SE35°)を(その位置、タイムスタンプ等とともに)含むことができ、この向きの情報が、厳密な変位を推定するために、第2の移動デバイスによって用いられる。別法として、別の実施形態では、第2の移動デバイスが、局所的な地形情報を利用することによって、(第1の移動デバイスが、向きの情報を送信することなく)第1の移動デバイスの向きを推定することができる。すなわち、両方の移動デバイスが同じ道路に沿って進行していることがあるので、それを利用して第1の移動デバイスの向きを推定する。それゆえ、第2の移動デバイスは、計算された変位を、(第1の移動デバイスの)以前の位置に、第2の移動デバイスが移動している方向に対して加えることができる。
【0057】
ステップ430では、第2の移動デバイスが、第1の移動デバイスの計算された推定位置と、自ノードの現在の位置とを比較して、2つの移動デバイスの相対的な順序を決定する。
【0058】
第2の移動デバイスは、自ノードが意図されたメッセージ方向にあるものと判定されるときにだけ、そのメッセージを中継又は転送する。自ノードの位置及び向きが送信側の移動デバイスと受信側の移動デバイスとの間にある場合には、移動デバイスは意図したメッセージ方向に沿っている。具体的には、第2の移動デバイスは、計算された相対的な順序又は位置を用いて、第2の移動デバイスが意図された経路に沿っているか否かを判定する。
【0059】
一実施形態では、向きの情報を用いて、第2の移動デバイスが意図した経路に沿っているか否かが判定される。この向きの情報は、上記のように、第1の移動デバイスの推定される位置を導出するために、第2の移動デバイスによって用いられる。上記のように2つの移動デバイス間の相対的な序列が決定されると、第2の移動デバイスは、第1の移動デバイスのメッセージに含まれる第1の移動デバイスの向きと、自らの向きとを用いることによって、第2の移動デバイスが第1の移動デバイスの意図したメッセージ伝送の経路上にあるか否かを判定することができる。たとえば、両方の移動デバイスが類似の向きを有し(すなわち同じ道路に沿って進行しており)、第2の移動デバイスが第1の移動デバイスの前方にある(その相対的な順序によって判定される)場合、意図されたメッセージの方向が同じ向きに沿っているときには、第2の移動デバイスがその(第1の移動デバイスの)メッセージを転送するのに対して、意図されたメッセージの方向が反対の向きを有するときには、第2の移動デバイスはそのメッセージを転送しない。第1の移動デバイスがその向きの情報をメッセージとして送信しない別の実施形態では、第2の移動デバイスは、上記のように、たとえば、以前の位置に対する変位を推定することによって、第1の移動デバイスの向きを推定することができる。2つの移動デバイスの向き及び相対的な順序がわかると、第2の移動デバイスは、先に説明されたのと同じようにして、第2の移動デバイスが第1のデバイスの意図したメッセージ伝送の経路に沿っているか否かを判定することができる。
【0060】
第2の移動デバイスがその経路内に存在しない場合には、そのメッセージは転送されない。本実施形態による移動デバイスの順序付けは、移動デバイスの順序付けが重要でないときに、帯域幅が順序付け要求で輻輳しないという利点を有する。
【0061】
本発明の別の実施形態では、移動デバイスの相対的な順序は、位置ベクトルを用いて周期的に更新される。図5は、この方法を用いてLPGを順序付けする一例を示す。図5は、LPG500を、LPG位置ベクトルV510とともに示す。LPGは、一次元のアレイすなわちベクトルV510にマッピングされる。LPG500の各移動デバイスは1つのベクトルIDを有することになる。ベクトルIDはまさに、Vの位置インデックスである。図5に示されるように、ベクトルV510は、移動デバイスの位置の順序を表す。図5では、6つの異なる相対的な順序1〜6が存在する。その矢印は、移動デバイスの移動方向、たとえば、交通の流れを示す。
【0062】
位置ベクトルV510によって、移動デバイスは、情報伝送の方向を制御できるようになる。詳細には、位置ベクトルV510を用いて、ピアグループ内で情報をルーティングすることができる。たとえば、図5に示されるように、インデックス3を有する送信側の移動デバイスが、そのメッセージが3よりも小さなインデックスを有する移動デバイスに向けられていることを指示する場合には、インデックスj<3を有する移動デバイスだけが、そのメッセージを中継する。これは、そのメッセージがjより小さいインデックスを有する車両に向けられていることを指示することによって達成される。その中継は、そのメッセージがLPGの後方境界ノードに達するまで、又はそのメッセージが最大ホップ数に達するまで続く。同じようにして、前方への情報伝搬を達成することができる。
【0063】
さらに、位置ベクトルV510を用いることによって、ルーティング優先度を促進することもできる。MAC層は、この位置ベクトル510に基づいて、アクセス優先度を生成することができる。一般的に、そのネットワークでは、前方にある移動デバイスが警告事象を観測し、より高い優先度で無線チャネルを使用するに値する可能性が高いので、より低い位置インデックスを有する移動デバイス(LPGの前方部分にある移動デバイス)に、より高いアクセス優先度が与えられる。
【0064】
図6は、本発明の一実施形態による、位置ベクトルV510を作成する方法を示す。その過程は、ステップ600において、移動デバイス、たとえばノードNがLPGに参加するときに、位置インデックスIを初期化することによって開始する。ノードNが、既にLPG内にある少なくとも1つの他の移動デバイス(たとえばノードL)からメッセージを受信することにより、このノードと接触する。ステップ602において、ノードNは、ノードLのGPS位置を含む受信メッセージに基づいて、ノードLの位置を知る。ノードNは、受信した位置情報と、自らのGPS情報とを比較し、その比較に基づいて、ベクトルV510の中に自らを挿入する。その後、ノードNは、LPG内の他の移動デバイス(たとえばノードL)に、新たな位置ベクトルV510を送信する。たとえば、ノードNがノードLの前方にあり、ノードLがNのインデックスを有する前方端位置であった場合には、ステップ605において、ノードNは自らに、その位置インデックスとしてN−1の値を割り当て、LPGの新たな前方端になる。一方、ノードNがノードLの後方にあり、Lがnの指標を有する後方端位置である場合には、ステップ610において、ノードNは自らに、その位置インデックスとしてN+1の値を割り当て、その後方端位置を引き継ぐ。
【0065】
nのインデックスを有する移動デバイス(たとえばノードL)が前方端でも後方端でもない場合には、ノードNはLPGの中央に参加している。その際、ノードNは、上述したように、ステップ615において、GPSとノードLとを比較することによって、自らを位置Vの中に挿入し、その後、ステップ620において、挿入点の後方にある全ての移動
デバイスのインデックスの更新をトリガする。その際、挿入点の後方にある他のノードは、そのGPS位置の変化に基づいて、その位置インデックスを更新する。
【0066】
別法では、新たなノード又は移動デバイスの挿入時に他の移動デバイスの更新を自動的にトリガする代わりに、新たな移動デバイスはインデックスn+1を割り当てられ、nよりも大きな指標を有する全ての移動デバイスが、それらの指標を1だけインクリメントする。
【0067】
位置ベクトルV510を自動的に更新したりインクリメントしたりすることに対する別の代替形態は、所定の位置インターバル内にある他の移動デバイスをインクリメントすることである。これは、インデックス更新の頻度を削減するであろう。中央に参加するノードNは、nとn+Kとの間の値のインターバルから得られるインデックスを割り当てられ、n+Kよりも大きな位置を有する移動デバイスのインデックスをインクリメントする必要はない。このインターバル(n〜n+k)の中にある移動デバイスだけが、それらの位置インデックスを更新する必要がある。
【0068】
さらに、LPG内の移動デバイスの相対的な順序を維持するために、すなわち、移動デバイスがLPGに参加したときに、位置ベクトルV510を更新することができる。各移動デバイスは、その位置インデックスを周期的に更新することができる。LPG内の移動デバイスの位置インデックス(i)は、位置ベクトルV510がLPG内の移動デバイスの現在の相対的な位置を含むように維持することができる。詳細には、移動デバイスがすれ違って相対的な位置を変わるときに、位置インデックスを更新することができる。移動デバイスの位置インデックスは、2つの移動デバイスがその相対的な位置を入れ替えるときに入れ替えられる。たとえば、周期的なインターバルで、移動デバイスは、そのGPS位置を交換又は送信し、それらの相対的な位置が入れ替わった場合には、位置インデックスを入れ替える。その周期は、ネットワークのタイプ、地形、時刻、交通パターン及びメッセージのタイプ、又はLPGの位置に基づいて調整することができる。たとえば、移動デバイスが出口/入口ランプ又は交差点の周囲にあるときに、更新の頻度が高くなり、出口/入口ランプ間又は交差点間にあるときに更新の頻度が小さくなる。更新インターバルを大きくすることによって、順序付けの整合性を維持するためのオーバーヘッドを削減することができる。
【0069】
しかしながら、GPS又は位置情報の交換は、道路環境において特に欠点を有する。具体的には、LPG内の移動デバイスの数によって、(相対的な位置の変化に追従し続けようとして)大量のGPS座標が絶えず通信されることになる。さらに、GPS座標の誤差が移動デバイスの離隔距離と同じ桁になる可能性があるので、結果として行われる位置計算が十分に正確でないことがある。さらに、上記の方法は、大量の計算を必要とし、一般的に、GPS情報は、他の移動デバイスがそれらの情報を受信するときに既に古くなっている。
【0070】
別の実施形態では、移動デバイスの相対的な順序を、GPS情報を用いることなく、メッセージ及び位置ベクトルを用いることによって求めることができる。上記のように、GPS手法を用いて順序付けを維持することは、著しいオーバーヘッドを被ることがあり、移動デバイスの数が多くなる場合には特にそうである。この実施形態では、LPGが、いくつかの小さなグループ、すなわち等価セル(EC)に分割される。各ECは、1つの位置インデックスを割り当てられる。ECは、同じ無線通信エリア内にある、近接する移動デバイスのグループである。ECは、そのEC内の全ての移動デバイスが同じベクトル指標を有するLPGの1つのセグメントであり、メッセージ伝送は中継を要せずにEC内の全ての移動デバイスで受信することができる。
【0071】
ECを基本ユニットとして用いて情報を広めるために、ECは他のECとリンクするように形成される。図7は、LPG700内の複数のEC(EC1〜5)701〜705を示す。EC701〜705は、LPG700内に、無線通信エリアが重なり合うように配置することができる。図7に示されるネットワークでは、LPGの相対的な順序がEC間で維持され、オーバーヘッドを低減する。さらに、EC当たり一度だけメッセージが中継され、帯域効率を改善する。
【0072】
たとえば、1つのEC内の移動デバイス間は、1回のパケット伝送で通信できる。各ECは、必要に応じて、EC内のいくつかの移動デバイスがパケットを中継することができるように編成される。ECはLPG内で順序付けすることができ、メッセージがECに沿ってホップできるようにする。具体的には、EC3 703内の1つの移動デバイスがパケットを送信したい場合には、その移動デバイスはパケットを(一度だけ)隣接するEC2 702及びEC4 704に送信する。これにより、EC2 702及びEC4 704内の全ての移動デバイスにパケットが確実に届けられる。このパケットは、EC2 702及びEC4 704によって、それらの個々の隣接するECに、EC当たり1パケットだけ中継される。このタイプの、隣接セル当たり1パケットだけ行われる隣接EC間ルーティングは、LPG内のパケット伝送を最小限に抑えることができる。
【0073】
ECは、1つの等価セルヘッダ(ECH)によって維持及び制御される。各ECH711〜715は、その隣接するECHとリンクされ、LPG内の全てのECH711〜715が、直接又は間接のいずれかによって、シリアルにリンクされるようになる。ECH711〜715は、無線ホップカウントの順序で接続され、そのLPGのための転送ノードを務める。ECH711〜715だけがメッセージを中継するための役割を担い、それにより、不要なトラフィックが最小限に抑えられる。
【0074】
この実施形態では、ECHは自らを順序付けし、それらの順序を維持して、LPGのための順序付けを達成する。各ECHは、予め規定されたメッセージを送信することによって、そのLPG内で自らの存在を通知する。このメッセージは周期的に送信され、リンクされたECHのリストを通知する。すなわち、このメッセージは、送信するECHから見た位置順序の1ホップ先、2ホップ先、3ホップ先のECHノードを含む。そのリストは、他のECHによって受信され、それにより、他のECHは、自らのリストを更新し、そのリストをメモリに格納する。非ECH720も自らのリストを更新する。これにより、全てのECHリストが互いに一致するようになる。そのリストは、各ECHの相対的な順序を表す。これは、移動の方向及び伝送の方向の判定を容易にする。
【0075】
一実施形態では、送信メッセージは、メッセージを発信する発信元のIDと、順序付けして接続されるECの第1の通信経路に沿って発信元が見ることができるECHノードの第1のリストと、オプションで、順序付けして接続されるECの第2の通信経路に沿った第2のリストとを含む。さらに別のリストが提供されることもあり、各リンクECH(LECH)リストは、発信元ECHを中心にして、順序付けして接続されるECの1つのブランチ、すなわち通信経路に沿って出会う全てのECHノードのECH IDを含む。
【0076】
たとえば、各ECHは、その直に隣接するECHの相対的な位置を知っている。すなわちEC3 703のECHは、EC2 702及びEC4 704のECHによってそれぞれ送信されるリスト又はベクトルに基づいて、EC2 702及びEC4 704のECHが異なる方向にあることがわかっている。EC3 703のECHは、この情報を含むメッセージを送信する。さらに、EC2 702のECHは、EC1 701及びEC3 703のECHによってそれぞれ送信されるリスト又はベクトルに基づいて、EC1
701及びEC3 703のECHが異なる方向にあることがわかっている。この情報が組み合わせられ、各ECHが維持するリストとして格納される。
【0077】
その結果、ECHの相対的な順序を用いることによって、GPS情報を全く用いることなく、適当な方向にメッセージをルーティングすることができる。
【0078】
別法として、別の実施形態では、全ての移動デバイスが、重要な方向(たとえば、前、後、左及び右並びに取り得る斜めの方向)への指向性アンテナを備えており、これらの方向における他の移動デバイスの存在を検出することができる。任意の移動デバイスが、メッセージがピアグループの後方に向かって進んでいくように指示することができ、その後方を指している指向性アンテナにおいてのみメッセージを送信し、このメッセージを受信する移動デバイスは、その後方を指しているアンテナにおいてのみ中継することができる。この手法は、基本的な方向検出を提供するが、移動デバイス間の相対的な位置を提供しない。
【0079】
本発明による移動デバイスは、その移動デバイスに取り付けられるか、内蔵されるか、又はそれと組み合わせて用いられる無線デバイスを含む。図8は、本発明による無線デバイスを示す。本発明による無線デバイスは、無線通信範囲内のノード間での無線通信を提供するために、無線トランシーバのような送信手段802を有するコンピューティングデバイス800を含む。さらに、制御手段804、たとえばマイクロコントローラ、マイクロプロセッサ等が、送信手段802を通して他のノードから信号を受信するとともに、送信手段802を通して他のノードに信号を送信するように構成される。また制御手段804は、命令を実行することによって、動作制御も提供する。記憶手段806が、コンピューティングデバイス800内に配置され、制御手段804と動作可能に通信する。記憶手段806として、メモリモジュール、取外し可能媒体、多数の記憶デバイスの組み合わせ等を用いることができ、その記憶手段は、上記の実施形態のプロトコルを実行するために必要とされるプロセッサ実行可能命令を格納するだけの容量を有する。さらに、タイミング手段808が、別個の構成要素として、又は制御手段804の1つの機能によって設けられる。タイミング手段808は、上記の実施形態において参照された各タイマに必要とされる、時間インターバルの追跡を提供する。必要に応じて構成要素に動作電力を供給するために、電源のような電圧供給手段810が、コンピューティングデバイス800の全ての構成要素に電気的に接続される。その無線デバイスは、無線デバイスのためのクロックを維持する内部クロックをさらに備え、全てのメッセージのためのタイムスタンプとして用いられる。さらに、その無線デバイスは、アドレス割当て手段812と、ネットワークインターフェース手段814とを備える。別法では、アドレス割当て手段812は、制御手段804の一部にすることができる。
【0080】
上記の実施形態を実行するためのプロセッサ実行可能命令は、EPROM、フラッシュメモリ、又は他のそのような不揮発性記憶装置の形をとる記憶手段806に内蔵することができる。さらに、プロセッサ実行可能命令は、光媒体又は磁気媒体のようなコンピュータ読取り可能媒体上に格納することができるか、又はネットワーク(たとえば、インターネット)を介してダウンロードすることができる。ユーザは、必要に応じて、システムをさらに強化するために、利用可能になり次第プロセッサ実行可能命令を定期的に更新できることが好ましい。
【0081】
各移動デバイスは、固有の識別子を割り当てられ、アドホックネットワークを介してメッセージを送信及び受信するのを容易にするであろう。固有の識別子は、1つのLPG内の移動デバイスが同じ固有の識別子を割り当てられないように、移動デバイスに固有に割り当てられる任意の番号を用いることができる。この識別子は、即時通信に対応するために、必要に応じて、迅速に割り当てられなければならない。上記のように、固有の識別子は、MACアドレス、VIN番号又はIPアドレスのような、通信を容易にする任意の番号又はアドレスを用いることができるが、ここでは例示を目的として、IPアドレスの割
当てについて説明する。通常、移動デバイスは少なくとも1つのIPアドレスを有する。しかしながら、一実施形態では、LPG内通信及びLPG間通信の両方に対応するために、移動デバイスに2つのIPアドレスが割り当てられる。
【0082】
好ましい実施形態では、IPアドレスは、専用のネットワークプレフィックス、LPGの固有の識別子及び移動デバイスの識別情報に基づく。具体的には、IPアドレスは、特定の移動デバイスに対応する固有の番号に所定のネットワークプレフィックスを連結したものに基づいて割り当てることができる。ここで、固有の番号は、移動デバイスが存在するLPG、及びその移動デバイスに対応する番号に基づく。
【0083】
固定LPG及び動的LPGの両方に対してアドレスを割り当てるために、類似の割当て技法を用いることができるが、アドレスの割当てを、LPGのタイプ毎に個別に説明する。
【0084】
固定LPGの場合、本発明の一実施形態では、IPアドレスは、MACアドレス及びVIN番号又は時刻のハッシュ値と連結される標準的なネットワークプレフィックス及びLPG IDであってもよい。ハッシュ関数の使用は、アドレス空間に限りがある場合、すなわちIPv4の場合に特に重要である。この実施形態によれば、移動デバイスは、その自らのIPアドレスを割り当てるであろう。
【0085】
理想的な状況では、LPGは、アドレス空間の制約が実質的に問題にならないように、N個(Nは最大アドレス空間)の移動デバイスだけを有する。これにより、LPG毎にプライベートクラスを簡単に割り当てることができるようになる。LPG内の各移動デバイスは、IPアドレスの異なる下位部分を有する。このIPアドレスは、LPGが互いに接近していない限り、異なるLPGにおいて再利用することができる。
【0086】
しかしながら、典型的には、LPGはN個の移動デバイスよりも多くなることがある。したがって、所定のハッシュ関数が、移動デバイスのメモリセクションに格納されるで。アドレス割当て手段812は、メモリからのこの所定のハッシュ関数にアクセスして、IPアドレスの下位部分を割り当てる。ハッシュ関数は、複数の入力番号を、Mビット(MはIPアドレスの下位部分のビットの最大数)の番号に変換する。その複数の入力番号は、VIN番号、MACアドレス及び移動デバイスがLPGに参加した時刻を含むことができる。
【0087】
標準的なネットワークプレフィックスは、IPアドレスの上位部分である。標準的なネットワークプレフィックスもメモリに格納される。さらに、IPアドレスはLPG特有である。IPアドレスの一部を用いて、移動デバイスが位置する特定のLPGが特定される。LPGの位置及び関連するLPG IDのデータベースもメモリに格納される。移動デバイスが新たなLPGエリアに入るとき、移動デバイスは、そのIPアドレスを変更して、そのLPGに関連付けられる特定のIPアドレスを反映しなければならない。固定LPGの利点は、LPG位置が固定されており、明確であることである。これにより、LPG
IDを簡単に付与できるようになる。
【0088】
別法では、本発明の別の実施形態において、IPアドレスの一部又はアドレス全体が、LPG内の固定無線デバイスによって割り当てられることができる。たとえば、IPアドレスの一部は、移動デバイスがLPGに入ったシーケンス又は順序を表すことができる。この場合、入ってくる移動デバイスに対してシーケンス番号を送信する外部無線デバイスが必要となる。問い合わせ−中継−応答タイプの動作を通して、接続を確立することができる。新たな移動デバイスがLPGに入るとき、その移動デバイスは(送信を通して)問い合わせを行う。その問い合わせは、LPG内の他の移動デバイスによって、所定の外部
無線デバイスまで中継される。その外部無線デバイスは、路側ゲートウエイデバイス、リーダのような別の移動デバイス、又はLPG内の第1の移動デバイスを含むことができる。外部無線デバイスは、DHCPサーバとしての役割を果たす。
【0089】
外部無線デバイスは、シーケンス番号又はIPアドレスを生成し、応答を送信することによって問い合わせに応答する。このシーケンス番号は、ハッシュ値の代わりに、IPアドレスの下位部分として用いられる。シーケンス番号は、先に述べられたように、IPアドレスの上位部分と連結される。この方法を用いると、IPアドレスは、移動デバイスが絶えず動く結果としてシーケンスが変更されるときに、連続して変化する可能性がある。別法では、アドレス全体を、LPGに入る移動デバイスに送信することができる。
【0090】
本発明の別の実施形態では、IPプロトコルが広範なIPアドレスに対応する場合には、IPアドレスは、全MACアドレス又はVIN番号と連結される標準的なネットワーク識別子であってもよい。たとえば、IPv6プロトコルを用いるとき、ハッシュ関数を必要とすることなく、固有のアドレスを各移動デバイスに割り当てるための大量の空間が存在する。IPアドレスの上位64ビットはLPG ID専用にすることができ、下位のEUI64ビットは、MACアドレス又はVIN番号から直に計算することができる。
【0091】
IPアドレスの上位部分は、標準的なネットワークプレフィックス及び固有のLPG IDを含むことができる。下位のEUI部分は、MACアドレス又はVIN番号のそれぞれを含む。
【0092】
図9は、IPv4プロトコルに従ってIPアドレスを割り当てる一例を示す。図9は、4つの重なり合うLPG、LPG1 901、LPG2 902、LPG3 903及びLPG4 904を示す。IPアドレス内の最初の2つの3桁数字905は、標準的なネットワークプレフィックス「192.168」を表す。標準的なネットワークプレフィックス「192.168」は、ネットワーク内の全てのLPGの場合に同じである。第3の3桁数字906はLPG IDであり、LPG特有である。図9に示されるように、LPG1 901、LPG2 902、LPG3 903及びLPG4 904はそれぞれ、第3の3桁数字906内に1、2、3、4の値を有する。第4の3桁数字907は、個々の移動デバイスの識別情報を表す。この番号は、移動デバイスに基づいて変わる。この番号は、上記の実施形態のうちのいずれか1つを用いて割り当てることができる。
【0093】
図10は、IPv6プロトコルの場合のIPアドレスのための1つの例示的なフォーマットを示す。例示の目的で、図10では、図9で用いられたものと同じLPG参照符号を用いる。上位部分1000は、64ビットになるように示されており、LPG IDを表し、下位部分1001も64ビットであり、移動デバイスの識別情報(EUI)を表す。上位部分1000及び下位部分1001はいずれも、固定LPG毎に異なる。
【0094】
さらに、上述したように、移動デバイスにLPGを円滑に変更させるために、且つLPG間通信を支援するのを容易にするために、固定LPG間に、或る重なり合うエリアが存在することがある。好ましい実施形態では、重なり合うエリアでは、各移動デバイスが2つのIPアドレスを有し、両方のLPGにアクセスできるようにする。移動デバイスが重なり合うエリアに接近すると、アドレス割当て手段812は、その移動デバイスに対して第2のIPアドレスを割り当てる。具体的には、その移動デバイスは、メモリ内に格納される重なり合うエリアの位置を現在の位置と比較し、自分が重なり合うエリア又は境界エリアに位置するか否かを判定する。無線デバイスは、ネットワークインターフェース手段814(すなわち、802.11カード)を有する。1つの物理無線インターフェースによって、多数の論理インターフェースに対応することができる。各論理インターフェースは1つのIPアドレスを有する。それゆえ、各ネットワークインターフェース手段814
は、2つ以上のIPアドレスを有することができる。各IPアドレスは、上記で特定した実施形態のいずれかに従って割り当てることができる。
【0095】
動的LPGの場合にも、固定LPGに対するIPアドレス割当てと類似の技法を利用することができるが、動的LPGに対するIPアドレス割当ては、より動的である。これは、LPGの位置がもはや固定されていないためである。さらに、LPG IDも一定ではなく、絶えず変化する。さらに、動的LPGの場合には、LPG間通信へのIPアドレスの割当てが異なる。
【0096】
動的LPGのためのPLG内IPアドレス割当ての場合、その技法は、IPv4の場合の固定LPGにIPアドレスを割り当てるために用いられる技法と概ね同様である。図11a及び図11bは、IPv4プロトコルの場合のIPアドレスフォーマットの2つの異なる例を示す。いずれのフォーマットでも、IPアドレスの上位部分、すなわち最初の2つの3桁数字1100は、標準的なネットワークプレフィックス、たとえば、192.168、10.0及び172.12によって決定される。一実施形態では、標準的なネットワークプレフィックスは、プライベートアドレスになる。標準的なネットワークプレフィックスは、そのアドレスの最初の2つの3桁数字になるであろう。
【0097】
第3の3桁数字1101はLPG IDである。一実施形態では、LPG IDはランダムに生成される。第4の3桁数字は、移動デバイスの識別情報である。この識別番号は、図11aに示されるように、VIN又はMACアドレス1102aのハッシュ関数に基づいて割り当てることができるか、又は図11bに示されるように、移動デバイスがLPG1102bに入るシーケンスに基づいて割り当てることができる。ハッシュ関数及びシーケンシングは、固定IPアドレス割当てに関して先に説明されており、さらに説明はしない。
【0098】
このIPアドレスによって、LPGの中で通信、すなわちLPG内通信が可能となる。しかしながら、LPG間通信のためには、移動デバイスに対して、別個のIPアドレスが割り当てられなければならない。これは、公開IPアドレスになるであろう。この公開IPアドレスは、DHCPサーバとして動作する外部の無線デバイスによって、又はDHCPとして動作する別の移動デバイスによって割り当てることができる。このアドレス割当ては、移動デバイス(LPGの代表者としての役割を果たす)と外部デバイス(DHCPサーバとしての役割を果たす)との間のDHCPプロトコルに従う。
【0099】
本発明の一実施形態では、LPG内の1つの移動デバイスは、IPv4プロトコルを用いて、LPG間通信のための公開IPアドレスを割り当てられる。図12aに示されるように、1つのノード1202は、公開IPアドレスIPA1204を割り当てられる。このノード1202は、LPG内の最初の移動デバイス、リーダとして選択される移動デバイス、又は別の所定の選択判定基準に基づいて選択される移動デバイスであってもよい。別法では、その選択はランダムに行うことができる。残りのノード1201は、公開IPアドレスIPA1204を割り当てられない。
【0100】
別の実施形態では、所与のLPG内の各移動デバイスには、異なるIPアドレスが割り当てられる。図12bに示されるように、LPG1200は6つのノード1201を有する。各ノード1201は、異なるIPアドレスIPA1204〜IPF1209を割り当てられるであろう。
【0101】
第3の実施形態では、LPG内の全ての移動デバイスに対して、ただ1つのグローバル公開IPアドレスが割り当てられる。図12cに示されるように、LPG1200内の各移動デバイス又はノード1201には、同じ公開IPアドレス1204が割り当てられる
。この公開IPアドレス1204は、インターネットを介して通信するために、他のノードによってグローバルに認識することができる。たとえば、公開IPアドレスは239.5.5.5にすることができる。
【0102】
IPv6プロトコルの場合、LPG内通信のためのIPアドレスを割り当てるために2つの異なる方法がある。IPv6プロトコルを用いる無線デバイスは、2つの自動設定機能、すなわちリンクローカルアドレス及びルータ広告アドレス設定機能を有する。
【0103】
図13a及び図13bは、LPG内通信用のIPアドレスのフォーマットの2つの異なる例を示す。図13aに示されるように、第1の手法は、リンクローカルアドレス1300、たとえばfe80を用いる。リンクローカルアドレス1300は、IPアドレスの上位部分になる。下位部分、すなわちEUI1302は、64ビットであり、MACアドレス及び/又はVIN番号から計算される。しかしながら、リンクローカルアドレス手法は、LPG内においてのみ有効であり、LPG間通信のための第2の付加的なアドレスを必要とする。
【0104】
第2の手法は、図13bに示されるように、サイトローカルのような手法、又はルータ広告アドレスを用いることである。そのネットワークは、移動デバイスのネットワーク又は車両ネットワークに専用の所定の移動デバイスのプレフィックス1301を含む。この移動デバイスのプレフィックス1301は、「XXXX」1303として図13aに表されるように、上位64ビットになるようにLPG IDと組み合わせられる。下位64ビット、すなわちEUI64 1302は、図13aの場合と同じになるであろう。それゆえ、EUI64の番号は、両方のフォーマットの場合に同じになり、その差は、IDアドレスの上位部分である。
【0105】
両方のフォーマットにおいて、アドレスの一部として、LPG IDが用いられる。LPG IDは、LPG毎に固有でなければならない。本発明の一実施形態によれば、LPG IDは、ランダムに割り当てられる番号か、又はハッシュ関数によって予め定義される番号のいずれかであってもよい。ハッシュ関数は、LPGの位置、入手可能であるなら、LPG内の第1の移動デバイスのMACアドレス、又はLPG内の第1の移動デバイスのVIN番号から成ることができる。
【0106】
LPG間アドレスを割り当てる場合、一実施形態では、外部無線デバイスを用いて、IPアドレスの一部が割り当てられる。外部無線デバイスとして、LPGに対して、そのアドレス範囲及びプレフィックスを送信する、路側ゲートウエイ又は境界ルータのような任意のデバイスを用いることができる。ネットワークプレフィックスは、それらのゲートウエイ(ルータ)広告から入手することができる。受信されたネットワークプレフィックス1400は、IPアドレスの上位部分、たとえばIPアドレスのためのグローバルディレクトリとして用いられるであろう。IPアドレスの下位部分は、LPG内通信IPアドレスのために用いられるのと同じEUI番号64 1302を用いることができる。
【0107】
別の実施形態では、所定の車両又は移動デバイスのプレフィックス1301が作成され、各移動デバイスのメモリセクションに導入される。この移動デバイスのプレフィックス1301を、LPG ID1303と組み合わせて、上位64ビットが形成される。LPG IDは、LPG毎に固有でなければならない。本発明の一実施形態によれば、LPG
IDは、ランダムに割り当てられた番号か、又はハッシュ関数によって予め定義された番号のいずれかであってもよい。ハッシュ関数は、LPGの位置、入手可能であるなら、LPG内の第1の移動デバイスのMACアドレス、又はLPG内の第1の移動デバイスのVIN番号から成ることができる。IPアドレスの下位部分は、LPG内通信IPアドレスのために用いられるのと同じEUI番号64 1302を用いることができる。
【0108】
一実施形態では、任意の移動デバイスに、任意のIPアドレスを割り当てることができる。別の実施形態では、種々のクラスの移動デバイスのために、特定のIPアドレスを予約することができる。たとえば、緊急車両は、特定の範囲のIPアドレスを割り当てられることができる。この範囲内のIPアドレスは、救急車、パトカー及び消防車のような緊急車両のために保存される。外部無線デバイス又はゲートウエイは、特殊な移動デバイスを認識しており、特殊な移動デバイス又は移動デバイスの分類のリストをメモリ内に格納している。これらの特殊車両は、IPアドレスを要求するために特殊な問い合わせを用いなければならない。
【0109】
これによって、緊急車両からの優先メッセージが容易になる。言い換えると、特定の範囲のIPアドレスから発信される全てのメッセージは、伝送のために最も高い優先度を有する。
【0110】
本明細書において、本発明が、特定の例示的な実施形態を参照しながら説明されてきた。本発明の範囲から逸脱することなく、当業者には、特定の改変及び変更が明らかになり得る。例示的な実施形態は、例示することを意図しており、添付の特許請求の範囲によって規定される本発明の範囲を制限することは意図していない。
【特許請求の範囲】
【請求項1】
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法であって、
(a)前記複数の移動デバイスを少なくとも1つのローカルピアグループ(LPG)にグループ化するステップと、
(b)各LPG内の前記複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の該複数の移動デバイスを順序付けするステップと、
(c)前記複数の移動デバイスのそれぞれに、固有の識別子を割り当てるステップと
を含み、
前記固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく、
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項2】
ステップ(b)は、前記複数の移動デバイスの移動によって引き起こされる該複数の移動デバイスの相対的な位置の変化に基づいて、該複数の移動デバイスを再順序付けすることを含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項3】
ステップ(c)は、移動デバイスがLPGを変更するときに、該移動デバイスの前記固有の識別子を変更することを含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項4】
前記複数の移動デバイスの前記順序付けに基づいて、さらには通信メッセージのタイプに基づいて、LPG内でメッセージがルーティングされる、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及びに維持する方法。
【請求項5】
前記固有の識別子はIPアドレスである、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項6】
ステップ(c)は、移動デバイスが、2つの隣接するLPGの境界付近に位置するとき、又は該隣接するLPGが重なり合うエリア内に位置するときに、2つのIPアドレスを割り当てて、該隣接するLPG間で通信できるようにすることを含む、
請求項5に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項7】
少なくとも1つのLPGは、予め定義された固定位置を有する固定LPGである、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項8】
前記LPGは、少なくとも1つの動的LPGであり、該動的LPGは前記複数の移動デバイスのうちの1つ又は複数のクラスタリングに基づいて形成される、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項9】
前記LPGは、移動デバイスのグループによって定義される等価セル(EC)に分割さ
れ、
該グループ内の移動デバイスは互いに1ホップ以内に存在し、該EC内の任意の移動デバイスのグループにメッセージを届けるために一度の伝送のみが必要であり、
前記ECは、等価セルヘッダ(ECH)によって制御される、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項10】
ステップ(b)は、
各LPG内の各移動デバイスの前記相対的な位置を表す位置ベクトルを作成するステップ
を含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項11】
前記IPアドレスは、固有のLPG識別情報及び固有の移動デバイス識別情報と連結される所定のネットワークプレフィックスに基づいて割り当てられる、
請求項5に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項12】
前記固有のLPG識別情報及び前記固有の移動デバイス識別情報は、ハッシュ関数から計算される、
請求項11に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項13】
前記固有のLPG識別情報及び前記固有の移動デバイス識別情報は、前記複数の移動デバイスと通信する外部無線デバイスから与えられる、
請求項11に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項14】
前記ステップ(b)は、
第1の移動デバイスの位置と、意図したメッセージ方向の指示と、送信時刻とを含むメッセージを送信するステップと、
第2の移動デバイスによって前記送信メッセージを受信するステップと、
前記受信された送信メッセージに基づいて、前記第1の移動デバイスの変位を推定するステップと、
前記推定された変位及び前記第1の移動デバイスの位置に基づいて、該第1の移動デバイスの現在の位置を計算するステップと、
前記計算された現在の位置を、前記第2の移動デバイスの位置と比較するステップと
を含む、請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項15】
前記位置ベクトルを作成するステップは、
位置ベクトルを初期化するステップと、
該初期化された位置ベクトルを、前記LPGに参加している別の移動デバイスに送信するステップと、
前記別の移動デバイスが、自身の位置を、前記送信に含まれる位置情報と比較するステップと、
該比較に基づいて、前記別の移動デバイスの位置値を前記位置ベクトルに挿入するステップと、
前記LPG内の全ての他の移動デバイスに対して、更新された位置ベクトルを送信する
ステップと
を含む、請求項10に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項16】
前記更新された位置ベクトルを受信すると、前記他の移動デバイスのうちの少なくとも1つが、自身の相対的な位置の変化に基づいて、前記更新された位置ベクトル内の自身の位置を変更する、
請求項15に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項17】
前記第2の移動デバイスが前記意図したメッセージ方向に沿っているものと判定されるとき、該第2の移動デバイスは前記メッセージを中継する、
請求項14に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項18】
前記複数の移動デバイスはそれぞれ、移動デバイスのタイプに基づいて分類され、前記固有の識別子は該分類に基づいて割り当てられる、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項1】
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法であって、
(a)前記複数の移動デバイスを少なくとも1つのローカルピアグループ(LPG)にグループ化するステップと、
(b)各LPG内の前記複数のデバイスのそれぞれの相対的な位置に基づいて、各LPG内の該複数の移動デバイスを順序付けするステップと、
(c)前記複数の移動デバイスのそれぞれに、固有の識別子を割り当てるステップと
を含み、
前記固有の識別子は、対応する移動デバイスが位置するLPGに部分的に基づく、
複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項2】
ステップ(b)は、前記複数の移動デバイスの移動によって引き起こされる該複数の移動デバイスの相対的な位置の変化に基づいて、該複数の移動デバイスを再順序付けすることを含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項3】
ステップ(c)は、移動デバイスがLPGを変更するときに、該移動デバイスの前記固有の識別子を変更することを含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項4】
前記複数の移動デバイスの前記順序付けに基づいて、さらには通信メッセージのタイプに基づいて、LPG内でメッセージがルーティングされる、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及びに維持する方法。
【請求項5】
前記固有の識別子はIPアドレスである、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項6】
ステップ(c)は、移動デバイスが、2つの隣接するLPGの境界付近に位置するとき、又は該隣接するLPGが重なり合うエリア内に位置するときに、2つのIPアドレスを割り当てて、該隣接するLPG間で通信できるようにすることを含む、
請求項5に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項7】
少なくとも1つのLPGは、予め定義された固定位置を有する固定LPGである、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項8】
前記LPGは、少なくとも1つの動的LPGであり、該動的LPGは前記複数の移動デバイスのうちの1つ又は複数のクラスタリングに基づいて形成される、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項9】
前記LPGは、移動デバイスのグループによって定義される等価セル(EC)に分割さ
れ、
該グループ内の移動デバイスは互いに1ホップ以内に存在し、該EC内の任意の移動デバイスのグループにメッセージを届けるために一度の伝送のみが必要であり、
前記ECは、等価セルヘッダ(ECH)によって制御される、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項10】
ステップ(b)は、
各LPG内の各移動デバイスの前記相対的な位置を表す位置ベクトルを作成するステップ
を含む、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項11】
前記IPアドレスは、固有のLPG識別情報及び固有の移動デバイス識別情報と連結される所定のネットワークプレフィックスに基づいて割り当てられる、
請求項5に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項12】
前記固有のLPG識別情報及び前記固有の移動デバイス識別情報は、ハッシュ関数から計算される、
請求項11に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項13】
前記固有のLPG識別情報及び前記固有の移動デバイス識別情報は、前記複数の移動デバイスと通信する外部無線デバイスから与えられる、
請求項11に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項14】
前記ステップ(b)は、
第1の移動デバイスの位置と、意図したメッセージ方向の指示と、送信時刻とを含むメッセージを送信するステップと、
第2の移動デバイスによって前記送信メッセージを受信するステップと、
前記受信された送信メッセージに基づいて、前記第1の移動デバイスの変位を推定するステップと、
前記推定された変位及び前記第1の移動デバイスの位置に基づいて、該第1の移動デバイスの現在の位置を計算するステップと、
前記計算された現在の位置を、前記第2の移動デバイスの位置と比較するステップと
を含む、請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項15】
前記位置ベクトルを作成するステップは、
位置ベクトルを初期化するステップと、
該初期化された位置ベクトルを、前記LPGに参加している別の移動デバイスに送信するステップと、
前記別の移動デバイスが、自身の位置を、前記送信に含まれる位置情報と比較するステップと、
該比較に基づいて、前記別の移動デバイスの位置値を前記位置ベクトルに挿入するステップと、
前記LPG内の全ての他の移動デバイスに対して、更新された位置ベクトルを送信する
ステップと
を含む、請求項10に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項16】
前記更新された位置ベクトルを受信すると、前記他の移動デバイスのうちの少なくとも1つが、自身の相対的な位置の変化に基づいて、前記更新された位置ベクトル内の自身の位置を変更する、
請求項15に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項17】
前記第2の移動デバイスが前記意図したメッセージ方向に沿っているものと判定されるとき、該第2の移動デバイスは前記メッセージを中継する、
請求項14に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【請求項18】
前記複数の移動デバイスはそれぞれ、移動デバイスのタイプに基づいて分類され、前記固有の識別子は該分類に基づいて割り当てられる、
請求項1に記載の複数の移動デバイス間で通信するためのアドホックネットワークを編成及び維持する方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2012−124936(P2012−124936A)
【公開日】平成24年6月28日(2012.6.28)
【国際特許分類】
【出願番号】特願2012−23058(P2012−23058)
【出願日】平成24年2月6日(2012.2.6)
【分割の表示】特願2007−550557(P2007−550557)の分割
【原出願日】平成18年1月11日(2006.1.11)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(502087460)株式会社トヨタIT開発センター (232)
【Fターム(参考)】
【公開日】平成24年6月28日(2012.6.28)
【国際特許分類】
【出願日】平成24年2月6日(2012.2.6)
【分割の表示】特願2007−550557(P2007−550557)の分割
【原出願日】平成18年1月11日(2006.1.11)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(502087460)株式会社トヨタIT開発センター (232)
【Fターム(参考)】
[ Back to top ]