ローカルピアグループ(LPG)間ルーティング方法
複数のローカルピアグループ(LPG)間でデータをルーティングするオンデマンドな方法。各LPGは、複数の移動ノードを含む。方法は、ソースノードからルート要求メッセージを伝送することと、ルート要求メッセージをネイティブ境界ノードへ中継することと、ルート要求メッセージを外部境界ノードへ転送することと、宛先ノードが外部境界ノードのLPG内であるかどうかを判定することと、もし宛先ノードが上記LPG内でないならば、ルート要求メッセージを別の境界ノードへ中継することと、もし宛先ノードが上記LPG内であるならば、ルート要求メッセージを宛先ノードへ中継することと、宛先ノードにおいてルート要求メッセージを受信することと、ルーティング応答をソースノードへ伝送することと、ルート要求によって発見された経路を通じてルーティング応答をソースノードへ中継することと、ソースノードにおいてルーティング応答を受信することと、データを伝送することとを含む。
【発明の詳細な説明】
【技術分野】
【0001】
本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network(アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス)」と題された、2006年10月23日出願の共同所有の米国同時係属特許出願第11/585,047号(「’047出願」)に関連している。
【0002】
本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、複数のローカルピアグループ間でメッセージをルーティングするための方法に関する。
【背景技術】
【0003】
’047出願は、1つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してローカルピアグループ(LPG)を維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループに編成するための方法を記載している。移動車両は、シングルホップ伝送又はマルチホップ伝送のいずれかを使用してデータをルーティングするように適応される。‘047出願は、各ノード又は各移動車両内のローカルルーティングテーブルをもとにして具体的なLPG内ルートが決定されることを記載している。ローカルルーティングテーブルは、ノードによってLPG内の他のノードから受信される情報をもとにして作成される。ルーティング経路は、絶えず更新される。LPGのサイズは、LPGが管理サイズであることを保証するためにプリセットされる。サイズは、ホップカウント限界に基づいてプリセットされる。
【0004】
ネットワークは、複数のLPGを含むと考えられ、各LPGは、幾つかの移動車両を含む。メッセージは、例えばLPG内通信のようにLPG内で伝送される。しかしながら、例えばLPG間通信のように複数のLPGの間での伝送を必要とするメッセージもある。道路障害物の緊急警告、交差点との連係、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含むこれらのメッセージは、LPG間で効率良く伝送可能でなければならない。
【0005】
性能要件は、衝突回避などの様々なVSC応用形態を支援するために、待ち時間が短いこと(約100ミリ秒)及びスループットを維持すること(別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合)を含む。
【0006】
したがって、複数のローカルピアグループ間で伝送するための方法が必要とされる。
【発明の概要】
【0007】
ゆえに、複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法が開示される。各ローカルピアグループ(Local Peer Group)は、複数の移動ノードを含む。本方法は、ソースノードからルート要求メッセージを伝送するステップであって、ルート要求メッセージは、宛先ノード、ソースノードのLPG識別子、及び前LPG識別子を少なくとも含む、ステップと、ルーティング要求メッセージを宛先ノードへ中継するステップと、ルーティング応答を発行するステップと、応答をソースへルーティングするステップと、ルート要求メッセージをネイティブ境界ノードへ中継するステップと、ソースノードにおいてルーティング応答を受信するステップと、ルーティング応答の受信を受けてデータを伝送するステップと、を含む。データは、初めは、ルーティング応答を伝送したノードを使用して中継されるが、実際のルートは、更新後のローカルルーティングテーブルをもとにして決定される。
【0008】
ルート要求メッセージは、ルート要求メッセージを外部境界ノードへ転送すること、宛先ノードが外部境界ノードのLPG内であるかどうかを判定すること、宛先ノードが上記LPG内でないならば、ルート要求メッセージを別の境界ノードへ中継すること、及び宛先ノードが上記LPG内であるならば、ルート要求メッセージを宛先ノードへ中継することによって、宛先ノードへ中継される。
【0009】
宛先ノードは、ルート要求の受信を受けて、ルーティング応答をソースノードへ伝送する。ルーティング応答は、ルート要求を通じて発見された経路を通じてソースノードへ中継される。
【0010】
オンデマンドな方法は、更に、ルート要求メッセージを受信するノードが宛先ノード又は宛先ノードのLPG内の境界ノードであるかどうかを判定するステップを含む。
【0011】
オンデマンドな方法は、更に、宛先ノードがルート要求メッセージを受信しているノードと同じLPG内であるかどうかを判定するステップと、ルート要求メッセージを受信しているノードが入口境界ノードであるかどうかを判定するステップと、ソースノードの識別子によって宛先リストを更新するステップとを含む。
【0012】
オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定することを含む。
【0013】
オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルート要求メッセージ内の前LPG識別子を出口境界ノードのLPGのLPG識別子で置き換えるステップとを含む。
【0014】
オンデマンドな方法は、更に、ソースノードがルーティング応答を受信しているノードと同じLPG内であるかどうかを判定するステップと、ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、宛先ノードの識別子によって宛先リストを更新するステップとを含む。
【0015】
オンデマンドな方法は、更に、ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを含む。
【0016】
オンデマンドな方法は、更に、ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルーティング応答内の次LPG識別子を出口境界ノードのLPGのLPG識別子で置き換えるステップとを含む。
【0017】
オンデマンドな方法は、更に、宛先ノードによってデータが受信されるまでソースノードから宛先ノードへのルートを維持するステップを含む。
【0018】
ルートを維持するステップは、ノードがLPGを変更したかどうかを検出するサブステップと、ノードがLPGを変更したという通知をLPG内の全てのノードへ伝送するサブステップと、変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、LPGを変更したノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップとを含む。
【0019】
ルーティング要求メッセージは、宛先ノード識別子及び前ノード識別子を含む。
【0020】
また、複数のローカルピアグループ間での通信のために境界ノードを選択するための方
法が開示される。方法は、既定のノードを発信元とする第1の制御パケットを受信するステップと、第1の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、もし第1の制御パケットが外部ローカルピアグループを発信元とするならば、パケットをグループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、少なくとも1つの候補からの伝送されたパケットをグループヘッダにおいて受信するステップと、受信されたパケットに基づいて候補のリストを作成するステップと、候補のリストから1つの候補を境界ノードとして選択するステップと、選択された境界ノードの識別子を含むデータパケットを伝送するステップとを含む。既定のノードは、グループヘッダである。
【0021】
候補のリストは、プリセット期間にわたって有効である。期間は、Time−to−Live値である。Time−to−Live値は、第1の制御パケットの伝送期間の倍数である。方法は、更に、プリセット期間が満了したかどうかを判定するステップと、もしプリセット期間が満了したならば候補を削除するステップとを含む。方法は、更に、同じ候補の識別子を含むデータパケットをグループヘッダが受信したときにTime−to−Live値をリフレッシュするステップを含む。
【0022】
境界ノードは、各候補についての、グループヘッダからのホップカウントに基づいて選択される。
【0023】
本方法は、更に、選択された境界ノードの識別子を含むデータパケットを受信するステップと、選択された境界ノードの識別子を受信ノードの識別子と比較するステップと、比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、を含む。
【0024】
本方法は、更に、ステータスを境界ノードに変更した後に定期的に第2の制御パケットを伝送するステップを含む。
【0025】
本方法は、グループヘッダから上記境界ノードと反対の相対方向にある第2の境界ノードを選択するステップを含む。
【0026】
本発明のこれらの及びその他の特徴、利益、及び利点は、以下の図面を参照することによって明らかになる。なお、図面を通じて、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0027】
【図1】発明の一実施形態にしたがった、LPG間通信に適応され尚且つ互いの近くにある複数のローカルピアグループを示している。
【図2】典型的なハートビートメッセージを示している。
【図3】典型的なメンバシップレポートメッセージを示している。
【図4】発明の一実施形態にしたがった、境界ノード(BN)を選択するための方法の流れ図を示している。
【図5】発明の一実施形態にしたがった、境界ノード(BN)を選択するための方法の流れ図を示している。
【図6】発明の一実施形態にしたがった、BNの選択のための有限状態図を示している。
【図7】発明の一実施形態にしたがった、ルーティングテーブルを作成してルーティングテーブルのエントリを更新する方法の流れ図を示している。
【図8】別のローカルピアグループ内のノードから受信されたデータパケットを処理する方法の流れ図を示している。
【図9】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図10】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図11】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図12】発明の一実施形態にしたがった、移動度検出方法の流れ図を示している。
【図13】発明の一実施形態にしたがった、ローカルピアグループからの離脱ノードが検出されたことをノードに知らせる方法の流れ図を示している。
【図14】発明の一実施形態にしたがった、義務外部宛先リストを広める方法の流れ図を示している。
【発明を実施するための形態】
【0028】
本発明にしたがうと、ノード又は移動デバイスは、管理可能なグループに編成される。これらのグループは、ノード間でのデータの伝送を調整するために使用される。グループは、隣接するノードの相対位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ(「LPG」)は、1つのLPG115内で及び複数のLPG間で電波信号をルーティングするための基礎である。電波信号は、車両の安全性の応用及び情報の応用を含む。
【0029】
図1は、2つのLPG(一般に1として表示される)、すなわちLPG A(1a)及びLPG B(1b)を示している。LPG A1aは、3つの個々のノードを含む(ノードは、一般に「10」として表示される)。LPG1内の1つのノードが、グループのリーダになるべく選択される。リーダは、GHと称され、LPG A1aの場合はGHaとして表わされる(GHは、一般に「25」として表示される)。GH25は、LPG1を管理する。また、GH25は、特殊なノードを境界ノード(BN:一般に「20」として表示される)にするべく選択する。BN20は、複数のLPG1間でデータを中継する役割を担うノード10である。BN20は、複数のLPG1の電波有効範囲が重なるエリア内に物理的に位置している。BN20は、オンデマンドなルート検索及び維持管理の役割を担う。BN20は、また、LPG間通信のための有効ルートを維持する役割も担う。BN20は、そのメンバシップレポート(MR)300の一部として特定の外部宛先リストを他のノード10に報告する。特定の外部宛先リストは、義務(obligated)外部宛先を含む。義務外部宛先は、通信経路がアクティブで尚且つ外部宛先の次ホップLPGがBNの位置しているLPG1であるような宛先を含む。また、BN20は、複数のLPG1からハートビートメッセージ200及びMR300を横聞き(overhear)するので、BN20は、離脱ノード又は移動ノードの通知も支援する。
【0030】
LPG1のサイズは、所定のLPG1内のノード10が多くなりすぎないように制御される。より詳細には、GH25は、特定のフォーマットを有する電波信号をブロードキャストし、GH25の範囲内の他のノード10は、その電波信号を受信する能力を有する。電波信号は、ホップカウント、又は信号が有効であるTime−to−Live(TTL)値を含む。すなわち、もし信号が、指定された値を上回るホップカウントにわたって中継されるならば、ノードは、LPG1に参加しない。この電波信号は、ハートビートメッセージ200と呼ばれる。GHの形成、維持管理、及び選択、並びにLPG1の制御は、参照によって本明細書に組み込まれる’047出願に記載されている。
【0031】
上記のように、2つの異なるLPG1からの電波信号がヒアリング可能な領域がある。この領域では、ノードは、2つの異なるハートビートメッセージ200を受信するが、ノード10が参加できるのは、1つのLPG1のみである。この重複エリアは、LPG交差エリア(LIA)と呼ばれる。ノード10は、最も優先度の高いLPG1に参加する。一実施形態では、優先度は、LPG識別子に基づいて判定される。例えば、図1では、2つのLPG1と2つのGH25がある。
【0032】
LIA内のノード10は、BN20の候補であることができる。しかしながら、LIA内にノード10がある保証はない。したがって、エッジハートビートが使用される。エッジハートビートは、有効HC限界よりも1ホップだけ大きいHCを伴うハートビートメッセージである。ノード10は、エッジハートビートを受信した後はLPG1に参加することができない。ハートビートメッセージ200と異なり、エッジハートビートは中継されない。
【0033】
図2は、発明にしたがったハートビートメッセージ200の一例を示している。GH25は、ハートビートメッセージ200を定期的に送出し、LPGを識別するとともにLPGに関する情報を提供する。この期間は、固定間隔(T)である。間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。GH25は、また、LPG内の全てのノードのリストを維持する。このリストは、ノードがLPGにいつ入ったか又はGH25がノード10からいつステータス更新を受信したかについてのタイムスタンプを含む。リストは、LPGに対する様々な管理機能及び制御機能のために使用される。例えば、リストは、グループサイズの追跡、マルチキャストルーティングテーブルの作成及び更新、並びにヘッダ解決に使用することができる。また、このリストは、LPG1内の他の全てのノードに定期的にブロードキャストされる。LPGハートビートメッセージ200は、GH25の電波周辺内の全てのノードにブロードキャストされる。
【0034】
ハートビートメッセージ200は、LPGの識別子、GH識別、シーケンス番号、及び例えば完全なグループリストを伴うハートビート、漸増性のグループリストを伴うハートビート、又はグループリストを伴わないハートビートなどのハートビートメッセージのタイプを含む。一実施形態では、ハートビートメッセージは、全てのメッセージ内に完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビートメッセージには、大量の帯域幅が必要である。別の実施形態では、(n−1)個おきの各ハートビートメッセージ200が完全なグループリストを含む。例えば、2つおきの各ハートビートが完全なグループリストを含む。ToHb(type of heartbeat)は、ハートビートメッセージ200のタイプを示す。ハートビートメッセージのタイプは、LPG1のトポロジ変化速度と、ハートビートのブロードキャストの頻度とによって影響される。LPG1のトポロジ変化速度が増すにつれて、全てのハートビートメッセージ200に完全なグループリストが含まれている必要性が高まる。
【0035】
ハートビートメッセージ200は、GHからのホップカウント(HC)を含む。最初、HCは、例えば1などの既定の値に設定される。ハートビートメッセージ200がノードによって中継されるたびに、中継ノードは、HCの値を1だけ増加させる、すなわちHC=HC+1とする。HC値は、LPGサイズを制限するため、ハートビートメッセージ200内の情報の古さを示すため、及び制御パケットのルーティングを制御して上記のようにオーバーヘッドを低減させるために使用することができる。HCが最大ホップカウントまで増分されると、制御パケットは、中継されなくなる。
【0036】
最大ホップカウント、HC、及びSeq.No.を利用することによって、LPG1内で制御パケットが無限に重複する事態が阻止される。ホップカウントは、中継戦略にも使用することができる。ノードは、ハートビートメッセージを転送するときに、そのハートビートメッセージ200を誰がリレーしたのかを次ホップノードが知ることができるように、自身のID情報をメッセージ内に含ませる。
【0037】
上記のように、ハートビートメッセージ200は、グループリストも含むことができる。グループリストは、LPG1内のメンバの数、各数のIPアドレス、GHからのホップ
カウント、BN20としてのステータス、BNの有効期限、及び分類などの、LPG1のメンバに関する情報を含むことができる。
【0038】
分類は、例えばアップリンク、ダウンリンク、及びピアのような、GHからの相対方向に言及したコードであってもよい。ピア分類は、ノードがGH25から同じ無線有効範囲内にあることを示す、すなわち、全てのピアノードは、GHからのホップカウントが同じである。アップストリームノードは、ハートビートによって決定される。ダウンストリームノードは、後述されるメンバシップレポート(MR)300に基づいて決定される。アップストリーム伝送は、GH25に向かう通信を表し、ダウンストリーム伝送は、GH25から離れる通信を表す。この分類は、相対的な表現である。各ノードは、自身に隣接するノードを3つの異なるクラスに分類することができる。もし別のノードのメンバシップレポートが、自身のホップカウント(HC)よりも1だけ小さいHCを有するならば、ノードは、アップストリームノードである。もし別のノードのHCが、自身のHCと同じであるならば、ノードは、ピアである。もし別のノードのHCが、自身のHCよりも1だけ大きいならば、ノードは、ダウンストリームノードである。分類は、BN候補のグループから、GH25の各側について1つずつBN20を選択するために使用される。
【0039】
図3は、メンバシップレポート(MR)300の一例を示している。MR300は、GH25ではない他のノードによってブロードキャストされる制御パケットであり、その受け手はGH25である。MR300は、ハートビートメッセージ200に応答して生成される。MR300は、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードのための次ホップなどの、収集可能なルーティング情報を含む。MR300は、ハートビートメッセージ200と同じ情報を幾つか、すなわちGID及びグループヘッダIDを含む。MR300は、また、MR Seq.No.も含む。MR Seq.No.は、ハートビートメッセージ200のSeq.No.と同様であり、MRの順番を維持するために使用される。MR Seq.No.は、1つの特定のノードに対するMRの順番である。通常、MR Seq.No.は、MR300をトリガしたハートビートメッセージ200のSeq.No.と同じ値を有する。
【0040】
発信元ノードすなわちMR300を生成したノードのノードIDも、MR300に含まれる。
【0041】
MR300は、次ホップ中継IDも含む。次ホップ中継IDは、GH25に向かうMR300のための中継命令である。次ホップ情報は、受信されたハートビートメッセージ200をもとにして直接決定される。ノード10は、新たなすなわち新着のハートビートメッセージ200を受信すると、いかなるパケット処理よりも前に、IP層及びMAC層をもとにして前中継ノードの識別を回復させる。前中継ノードの識別は、メモリに格納されており、MR300のための次ホップ中継IDとして使用される。ノード10は、ハートビートメッセージ200を転送するときに、そのIDをパケット内に含ませる。受信する次ホップノードは、新たなすなわち新着のハートビートメッセージ200を受信すると、このIDを、GH25に到達するための次ホップ中継IDとして格納する。新たなすなわち新着のハートビートメッセージ200は、最低のHCを伴った、より新しいシーケンス番号を有する。
【0042】
MR300は、また、「MRのタイプの指標」(Type of MR indicator, ToMR)も含む。MR300には、2つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバのMRは、発信元ノードからのMR300のみを含む。統合された複数メンバのレポートは、2つ以上のノード10のMR300を含む。統合されたレポートは、オーバーヘッド、及び制御パケットに必要な帯域幅を低減させるために使用することができる。複数のMRを含む1つのMR300が送信される。
【0043】
また、MR300は、GHからのホップカウント(HCGH)を含むことができる。(HCGH)は、GHからMR300の発信元ノードまでのHC値である。MR300は、報告ノードのための使用可能チャネルリストを含む。また、MR300は、マルチキャストメッセージを中継することに対するそのステータス又は有効性、すなわち転送ノードステータスを含む。MRは、また、BN20の候補指名を含む、すなわちノード10は、自身がBN20の候補であることを宣言してGH25に通知する。MRは、もし可能な場合は、隣接LPGリスト及びアクティブLPG間ノードリストを含む。
【0044】
図4及び図5は、発明の一実施形態にしたがった、BNを選択するための方法を示している。図4は、GH25ではない全てのノードについての機能ブロックを示している。図5は、GH25であるノード10の機能ブロックを示している。
【0045】
ノード10は、ハートビートメッセージ200又はエッジハートビートのいずれかである外部ハートビートをヒアリングすると、BN候補になる。外部ハートビートは、同じLPG1からのノード10によって生成されたのではないメッセージ又はパケットである。選択されたBN20のみが、エッジハートビートをブロードキャストする。もしLPGのエッジにBN20がある場合は、ノード10は、エッジハートビートをブロードキャストする。BN20は、ハートビートメッセージのホップカウント限界にある場合にLPG1のエッジにある。エッジハートビートは、ハートビートメッセージのホップカウントに対する追加のホップでブロードキャストされ、隣接するLPGが別のLPG1の存在に気づくことを可能にする。外部ノードは、エッジハートビートを受けると、LPG1に参加しない。エッジハートビートは、転送されない。
【0046】
機能ブロック400において、非GHノードはアイドル状態にある。説明のために、非GHノードは、一般的ノード(GN:General Node)として言及される。ブロック405では、ハートビートメッセージ200が到着する。ハートビートメッセージ200は、LPGの識別子を含む。GNは、パケットフォーマットに基づいて、パケットがハートビートメッセージ200であるかどうかを判定する。ブロック410では、GNは、ハートビートメッセージ200が例えば別のLPG1からのハートビートメッセージ200のような外部HBであるかどうかを判定する。GNは、ハートビートメッセージ200に含まれるLPG識別子を、GNが入っているLPGの識別子と比較する。もしこれらの識別子が同じでないならば、ブロック415において、GNは、自身をBN候補として宣言する。GNは、そのステータスを「BN候補」に変更する。GHは、MR300を使用して、BNへの立候補をGH25に通知する。ブロック420において、GNは、次のMRサイクル中にGHへMR300をブロードキャストする。MRは、例えばBNへの立候補などの、ノードステータスのためのフィールドを含む。その後、GNは、ブロック400のアイドル状態に戻り、BN20の決定のために、次のハートビートメッセージ200を待つ。
【0047】
もしブロック410において、GNがLPG識別子を同じだと判定するならば、方法は、機能ブロック425に進む。ブロック425では、GNは、ハートビートメッセージに含まれる任意のBN情報を抽出する。BN情報は、選択されたBNのノード識別子と、その選択されたBNに対応する任意の有効期間(Time−to−Live)値とを含む。有効期間値は、選択されたBNが境界ノードとして機能する期間を表わす。有効期間は、ハートビートサイクルで表わされる。
【0048】
ブロック430では、GNは、自身が選択されたBNであるかどうかを判定する。GNは、ハートビートメッセージ200に含まれる選択されたBNの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック435において、GNは、自身をLPGのBN20であると宣言する。GNは、そのステータスをBN候補からB
N20に変更する。GNは、次のMRサイクルで、自身がBN20であることをLPGの全てのメンバに通知する。MR300は、新しいステータスを含む。
【0049】
その後、ブロック440では、GN(今ではBN20)は、ノード10がハートビートメッセージ200を転送する必要があるかどうかを判定する。より詳細には、BN20は、ノード10がハートビートメッセージ200のためのホップカウント限界に位置するかどうかを判定する。この判定は、ハートビートメッセージ200に含まれるGHへのホップカウントと、ハートビートメッセージ200のための最大ホップカウントとに基づく。ハートビートメッセージ200が転送されるたびに、GHへのホップカウントは、1だけ増分される。GHへのホップカウントは、最大ホップカウントと比較される。もしGHへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ200は、転送されない、すなわち中継されない。その代わり、ブロック450において、BN20は、エッジハートビートをブロードキャストする。エッジハートビートのフォーマットは、ハートビートメッセージ200と同じであり、唯一の違いは、どのエッジハートビート内のHCも、ハートビートメッセージ200が持つことのできる最大ホップカウントよりも1だけ大きいことである。BN20は、次いで、ブロック400のアイドル状態に戻る。
【0050】
もしGHへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック445において、ハートビートメッセージ200は転送される、すなわち中継される。
【0051】
もしブロック430において、選択されたBN20の識別子がGNの識別子と一致しないならば、プロセスは、ブロック440に移動し、GNは、通常ハートビートメッセージ200中継機能を実施する。ブロック440において、GNは、ノード10がハートビートメッセージ200を転送する必要があるかどうかを判定する。GHへのホップカウントが、最大ホップカウントと比較される。もしGHへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ200は、転送されない、すなわち中継されない。BN20は、次いで、ブロック400のアイドル状態に戻る。もしGHへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック445において、ハートビートメッセージ200は転送される、すなわち中継される。GHへのホップカウントは、1だけ増分される。
【0052】
次に、GH25についてのBN選択プロセスが説明される。ブロック400において、GH25ノードはアイドル状態にある。ブロック405では、ハートビートメッセージ200が到着する。ハートビートメッセージ200は、LPGの識別子を含む。GH25は、パケットフォーマットに基づいて、パケットがハートビートメッセージ200であるかどうかを判定する。ブロック410では、GH25は、ハートビートメッセージ200が例えば別のLPG1からのハートビートメッセージ200のような外部HBであるかどうかを判定する。GH25は、ハートビートメッセージ200に含まれるLPG識別子を、GH25が制御しているLPGの識別子と比較する。もしこれらの識別子が同じでないならば、GH25は、ブロック500において、自身をBN候補として宣言する。GHは、ハートビートがエッジハートビート又はハートメッセージ200のいずれであるかに関係なく自身を候補として宣言する。GH25は、そのステータスを「BN候補」に変更する。もしハートビートメッセージ200に含まれるLPG識別子が、GH自身のLPG識別子と同じであるならば、ブロック505において、ハートビートメッセージ200は、BN選択を目的として無視される。
【0053】
もしMR300が到着する場合は、プロセスは、ブロック510から開始する。ブロック515において、GH25は、MR300からBN候補情報を抽出する。GH25は、BN候補について、MR300のステータスフィールドを調べる。もしステータスフィー
ルドが、ノード10がBN候補であることを示すならば、ブロック520において、GH25は、そのノード(GN)の識別子を候補リストに記録する。GH25は、可能性のある全ての候補の候補リストを維持する。G25は、このリストを使用して、少なくとも1つのBN20を選択する。
【0054】
ブロック525において、GH25は、既存のBN25及びBN候補について、有効期間(TTL)値を調整及びリフレッシュする。もしGH25が、BNへの立候補を伴わないMR300をBN20から受信する場合は、GH25は、BN候補のなかから新しいBN20を選ぶことによって、BN20を直ちに置き換える。もしGH25が、BNへの立候補を伴うMR300をBN20から受信する場合は、GH25は、TTLをリセットする。もしGH25が、ハートビート間隔内にMR300を受信しない場合は、GH25は、TTL値を減らす。TTL値が0になると、GH25は、BN20を再選する。その後、GH25は、ブロック400のアイドル状態になる。
【0055】
上述のように、GH25は、ハートビートメッセージ200を定期的にブロードキャストする。この期間は、ハートビート間隔として知られる。GH25内のタイマは、ハートビート間隔のタイミングを追跡記録する。ハートビート間隔の時間が満了すると、ブロック530において、タイマは、ハートビートメッセージ200の生成をトリガする。ハートビートメッセージ200のブロードキャストに先立って、GH25は、BN候補リストからBN20を選択する。一実施形態では、選択基準は、GHからのホップの数である。GH25は、GHからのホップカウントの数が最大であるノード10(GN)を選択する。BN候補リストは、その場合、ホップカウント情報を含む。
【0056】
別の実施形態では、選択基準は、ノード10がLPG1のメンバになっている期間である。この実施形態では、GH25は、各ノード10について持続時間の履歴を維持している。持続時間の履歴は、ハートビートサイクルの数を単位として測られる。GH25は、BN候補リストから、最も長い関係を持つノード10をBN20として選択する。
【0057】
別の実施形態では、選択基準は、BN候補が所定の時間内に受信した外部ハートビートの数である。この実施形態では、ノード10(GN)は、外部ハートビートのシーケンス番号、及び外部ハートビートのLPG識別子を追跡する。GH25に向けてブロードキャストされるMR300は、BN候補としてのステータス、オーバヒアリングされた外部ハートビートの数、外部ハートビートに対応する識別子、及び各外部ハートビートのシーケンス番号を含む。GH25は、この情報をMR300から抽出し、BN候補リストに追加する。GH25は、同じシーケンス番号を有する外部ハートビートメッセージ200を最多数オーバヒアリングしているノード10をBN20として選択する。
【0058】
別の実施形態では、選択基準は、GH25に対するBN候補の相対移動度である。この実施形態では、ノードは、それらの平均速さを監視している。平均速さは、外部の速度測定装置又は速さ測定装置からの入力に基づいて決定することができる。速さ情報は、MR300に追加され、GH25へ発せられる。GHは、各BN候補の平均速さを自身の平均速さと比較する。平均速さの差が小さいほど、BN候補としての優先度が高くなる。
【0059】
別の実施形態では、BN候補リストから、GH25からの相対方向ごとに1つずつ、計2つのBN20が選択される。BN候補の相対方向は、例えばアップストリーム又はダウンストリームなどのノードの分類に基づいて決定される。
【0060】
(1つ又は2つ以上の)BN20が選択された後は、ハートビートメッセージ200にBN情報が付加される。ブロック540では、GH25は、ハートビートメッセージ200をブロードキャストする。ハートビートメッセージ200がブロードキャストされた後
、GH25は、BN候補リスト内の全てのBN候補について、TTL値を減少させる。TTL値は、1だけ減らされる。BN20がGH25に報告を行うたびに、すなわち、ステータスをBN20としてMR300を送信するたびに、TTLは、例えばTハートビートサイクルなどの元の状態にリフレッシュされる。
【0061】
ブロック550において、GH25は、次いで、BN候補が古いかどうかを判定する。BN候補は、TTL値がゼロに等しい場合に古いとされる。もしBN候補のTTL値がゼロであるならば、ブロック555において、そのBN候補はBN候補リストから外される。判定は、各BN候補について繰り返される。BN候補リストが更新されると、ブロック430において、GH25は、選択されたBN20が例えば自身のようにGH25であるかどうかを判定する。GH25は、ハートビートメッセージ200に含まれる選択されたBNの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック435において、GH25は、自身をLPGのBN20として宣言する。もしこれらの識別子が同じでないならば、GH25は、ブロック400のアイドル状態になる。
【0062】
図6は、BN20の選択のための有限状態マシンを示している。ノード10は、3つの異なる状態、すなわちBN候補状態600、非BN状態605、及びBN状態610になることができる。非BN状態605にあるノード10は、外部ハートビート又はエッジハートビートを受信すると、BN候補状態600に変わる。BN候補状態600にあるノードは、GH25がそれをBN20として選択すると、BN状態610に変わる。ノード10は、外部ハートビート又はエッジハートビートを受信する限り、BN候補状態600にとどまる。ノード10は、外部ハートビート又はエッジハートビートを受信しなくなると、BN候補状態600から非BN状態605に戻る。ノード10は、外部ハートビート又はエッジハートビートを受信する限り、BN状態610にとどまる。
【0063】
ノード10は、外部ハートビート又はエッジハートビートを受信しなくなると、又はTTL値が古くなる、すなわちTTL=0になると、BN状態610から非BN状態605に戻る。
【0064】
BN20は、LPG間ルーティングを促進する。ルーティング経路は、各ノード内のルーティングテーブルに基づいて決定される。ルーティングテーブルは、データを中継するための次ホップ、次LPG、及びLPG1のためのBN20に関する情報を含む。ルーティングテーブルは、ハートビートメッセージ200及びMR300に含まれる情報をもとにして作成される。また、ルーティングテーブルは、外部ハートビート及びエッジハートビートからオーバヒアリングされる情報によって更新される。
【0065】
図7は、ルーティングテーブルを作成及び更新するためにハートビートメッセージ200及びMR300を処理するための方法を示している。最初、各ノード10は、アイドルステップ700にある。ステップ702において、パケットが到着すると、ステップ704において、ノード10は、パケットがハートビートメッセージ200であるか又はMR300であるかを判定する。制御パケットのタイプに応じて、ノード10は、特別なパケット処理を実施する。もし制御パケットがハートビートメッセージ200であるならば、ノード10は、ステップ706から開始してパケットを処理する。ステップ706において、ノード10は、パケットがネイティブであるかどうかを判定する。パケットは、同じLPG1に対するものである場合に、すなわち同じGID(グループ識別子)を有する場合に、ネイティブである。ノード10は、GIDを、メモリに格納されているグループ識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノード10は、外部HB処理を開始し、ステップ800に進む。外部HB処理は、図8において詳しく説明される。もしGIDが、メモリに格納されている識別と一致するならば、ステップ708において、ノード10は、ハートビートメッセージ200が順序通りであるか
どうかを判定する。ノード10は、Seq.No.を、メモリ内のシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10は、パケットを無視する。もしSeq.No.が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ200は、順序通りであり、ステップ710において、ノード10は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ200が新しいかどうかを判定する。もしノード10が、パケットを新しくないと判定するならば、ステップ712において、送信者のルーティングエントリのみが更新される。ハートビートメッセージ200は、中継されない。もしノード10が、メッセージ又はデータパケットを新しいと判定するならば、ノード10は、ノードがGH25であるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ714において実施される。もしノード10がGH25であるならば、ステップ716において、ノード10は、送信者のルーティングエントリを更新する。ハートビートメッセージ200は中継されず、ノードはアイドル状態700になる。しかしながら、もしノード10がGNであるならば、ステップ718において、ノード10は、全てのLPG内ルーティングエントリ及びLPG間ルーティングエントリについてルーティングテーブルを更新し、ハートビートメッセージ200を中継する。LPG間ルーティング情報は、ノード10が外部LPGからのメッセージを横聞き又はBN20から直接情報を受信するときに得られる。また、LPG間ルーティング情報は、GH25からのハートビートメッセージ200に含められる。ノード10は、任意の新しい宛先、宛先への次ホップ、新しい宛先があるLPGの識別子、及びLPG1のためのBN20を、ルーティングテーブルに追加する。また、ルーティングテーブルは、宛先が義務宛先であればフラグを含む。義務外部宛先を伴うBN20又はGNは、フラグを使用し、義務宛先を外部宛先として自身のMR300に含ませる。GH25を含むアップストリームノードは、義務外部宛先を伴うBN20又はGNからのMR300を横聞きすることによって、外部宛先を学習する。義務外部宛先については後述される。GHは、LPG1内の残りのノード10に知らせるために、次のハートビートメッセージ200に外部宛先を含ませる。ルーティングテーブルに既に挙げられている宛先については、ノード10は、テーブル内の情報と異なる任意の情報を更新する。例えば、ノード10は、次ホップ、LPG、及びBN20を更新することができる。
【0066】
もし制御パケットがMR300であるならば、ノード10は、ステップ720から開始してパケットを処理する。ステップ720において、ノード10は、パケットがネイティブであるかどうかを判定する。ノードは、GIDを、メモリに格納されているグループ識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノード10は、外部MR処理を開始し、ステップ800に進む。もしGIDが、メモリに格納されている識別と一致するならば、ステップ722において、ノード10は、そのMR300を送信したノード10がLPG1(同じLPG)のメンバであるかどうかを判定する。ノード10は、ノードIDを、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ステップ724において、ノード10は、MR300をただ中継する。MR300の中継によって、新しいグループノード(GN)は、完全なハートビートサイクルにわたって待つ必要なくLPG1に参加することができる。
【0067】
もしMR300を送信したノードが、参加リストに挙げられていない場合は、そのノード10は、参加ノードであるとみなされる。ルーティングテーブルに、参加ノードについてのルーティングエントリはない。一実施形態では、ノード10は、GH25に向けてMR300を転送することができる。ノード10は、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノード10は、(MR300の)発信元ノードを宛先リストに追加することができる、すなわち発信元ノードについてのルーティングエントリを確保することができる。ノード10は、中継ノードの情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ200が受信
されると、ノード10は、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。
【0068】
もし一致があるならば、ステップ726において、ノード10は、MR300が順序通りであるかどうかを判定する。ノード10は、MR Seq.No.を、メモリ内のシーケンス番号と比較する。もしMR Seq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、アイドル状態700になる。もしMR Seq.No.が、メモリに格納されている値よりも大きい又はその値と等しいならば、MR300は順序通りであり、ステップ728において、ノード10は、現シーケンス番号を伴う発信元からのMR300をノードが既に受信しているかどうかを(最後に格納されたシーケンス番号と比較することによって)チェックすることによって、MR300が新しいかどうかを判定する。もしノード10が、メッセージを新しくないと判定するならば、ステップ730において、送信者のルーティングエントリのみが更新される。MR300は中継されない。もしノード10が、メッセージを新しいと判定するならば、ノード10は、GH25であるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ732において実施される。もしノード10がGH25であるならば、ステップ734において、ノード10は、直接の送信者及び発信元のルーティングエントリを更新する。もしMR300が、少なくとも1つの外部宛先も運んでいるならば、ステップ734において、ノード10は、エントリを外部宛先リストに追加する。LPG1とのLPG間ルートを維持するために、収集された外部宛先リストは、次のハートビートメッセージ200に含められる。更新は、LPG内ルート及びLPG間ルートの両方を変更することを含む。もしMR300が、少なくとも1つの義務外部宛先を有するノード10からであるならば、受信ノード10は、義務外部宛先情報を使用して、LPG間ルートを更新する。義務外部宛先情報をもとにして、受信ノード10は、MR300を発信したノード10から到達することができる全ての外部宛先(ノード)を学習する。これらの外部宛先に向かう次ホップは、MR300を発信したノード10である。更新は、上述されており、再度の詳しい説明はされない。GH25は、また、任意の新しい宛先ノードをメンバシップリストに追加することによって、メンバシップリストを更新する。新しいメンバシップリストは、次のハートビートメッセージ200に含められる。MR300は中継されず、ノードはアイドル状態700になる。
【0069】
しかしながら、もしノード10がGNであるならば、ステップ736において、ノード10は、送信者及び発信元についてルーティングテーブルを更新し、MR300を中継する。例えば発信元の場合、発信元のための次ホップは、直接の送信者である。もしMR300が、外部宛先リスト、外部エントリも含むならば、外部宛先に向かう次ホップは、送信者である。発信元は、ダウンストリームノードである。更新は、LPG内ルート及びLPG間ルートの両方を変更することを含む。更新は、上述されており、再度の詳しい説明はされない。
【0070】
図8は、外部データパケット又はメッセージを処理するための方法を示している。外部データパケット又はメッセージは、異なるLPG内のノード10を発信元とするメッセージである。外部データパケットの判定は、データパケット内のLPG識別子に基づく。ステップ800において、外部LPGからデータパケットが受信される。ステップ805では、ノード10は、外部データバケットがハートビートメッセージ200であるか又はMR300であるかを判定する。制御パケットのタイプに応じて、ノード10は、特別なパケット処理を実施する。ステップ810では、ノード10は、データパケットが新しいLPGを発信元とするかどうかを判定する。このステップは、ハートビートメッセージ200及びMR300の両方に対して実施される。ノード10は、外部データパケット内のLPG識別子を、ルーティングテーブル内のLPG識別子と比較する。もし外部データパケ
ットが新しいLPG1からでないならば、ステップ815において、ノード10は、外部データパケットが順序通りに到着したかどうかを判定する。
【0071】
もし外部データパケットが新しいLPGからで、尚且つそのデータパケットがハートビートメッセージ200であるならば、プロセスは、ステップ820に進む。ステップ820では、LPG1が登録される。LPG識別子がメモリに格納され、ルーティングテーブルに追加される。タイムスタンプも記録される。一実施形態では、タイムスタンプは、ルーティングテーブルから古い情報を消去するために使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。
【0072】
また、ノード10は、LPG識別子、GH識別子、メンバリスト、及びGHへの次ホップなどの、新しいLPGに関連した情報を含む新しいデータ構造を、新しいLPG用に作成する。この情報は、ルーティングテーブルとは別に格納される。ステップ830において、ノード10は、ルーティングテーブル内のLPG間ルーティングエントリを更新する。ルーティングエントリは、ハートビートメッセージ200に含まれるメンバシップリストから抽出される。ノード10は、メンバシップリストからの各メンバを宛先として追加する。各宛先について、ルーティングテーブルは、次ホップ、BN20、及びノードがあるLPG1を含む。また、ルーティングテーブルは、義務外部宛先のためのフラグを含む。義務外部宛先は、アクティブに通信しているノード10であって、通信相手がLPG内にある又はLPG1を越えたところにあるノード10である。ノード10は、また、外部ハートビートメッセージを横聞きしたときからBN候補にもなる。一実施形態では、ルーティングテーブルから古い情報を消去するために、外部ハートビートカウンタが使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。ステップ830では、外部ハートビートカウンタは、新しい外部ハートビートが受信されるたびにリセットされる。
【0073】
もしハートビートメッセージ200が新しくないならば、ステップ815において、ノード10は、データパケットが順序通りに到着したかどうかを判定する。ノード10は、Seq.No.を、メモリに格納されているシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、外部データパケットは破棄される。もしSeq.No.が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ200は順序通りであり、ステップ825において、ノード10は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ200が新しいかどうかを判定する。もしノード10が、パケットを新しくないと判定するならば、ステップ835において、ノード10は、より良いルートが発見されたかどうかを判定する。新着のHBは、必ずしも最短経路を通って来たとは限らない。もし後のHBパケットが(たとえ新着でなくても)、より短い経路を通って来たならば、GHへの経路は、更新されるべきである。ルーティングテーブルは、外部ハートビートメッセージ200内の新しい情報に基づいて更新される。ステップ825において、もし外部データパケットが新しいと判定されるならば、プロセスは、ステップ830に進む。ステップ830は上述されており、再度の詳しい説明はされない。
【0074】
もし外部データパケットがMR300であるならば、ステップ810において、ノード10は、LPG1が新しいか否かを判定する。もしLPG1が新しいならば、プロセスは、ステップ840に進む。ステップ840において、ノード10は、送信者、発信元、及び外部GHへの次ホップ中継について、ルーティングテーブル内のLPG間ルーティングエントリを更新する。ノードは、例えば送信者、発信元、及び次ホップ中継ノードなどの3タイプのノードについて、次ホップ情報及び宛先情報を更新する。また、ノード10は、より良いルートがあるかもチェックする。より良いルートは、普通は、より短いホップ
のルートを意味する。たとえ、例えば送信者、発信元、及びGHへの次ホップ中継などの3つの外部宛先がBN20に知られている場合でも、GNは、送信者への直接経路、発信元へのより短い経路、及び次ホップ中継を有する。もしMR300が新しくないならば、ノード10は、ステップ815において、データパケットが順序通りに到着したかどうかを判定する。ノード10は、Seq.No.を、メモリ内のシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、外部データパケットは破棄される。もしSeq.No.が、メモリに格納されている値よりも大きいならば、MR300は順序通りであり、プロセスはステップ840に進む。ステップ840は上述されており、再度の詳しい説明はされない。
【0075】
ステップ830、835、及び840の各ステップの後、プロセスは、ステップ845に進む。ステップ845では、離脱ノードが検出される。検出プロセスは、後ほど詳しく説明される。
【0076】
図9〜11は、オンデマンドなルートの決定方法を示している。オンデマンドなルートは、ルート要求(R_Req)データパケット及びルート応答(R_Resp)データパケットを使用して決定され維持される。アクティブ通信のためのルートが発見され維持される。とあるソースが外部宛先すなわち異なるLPG1内の宛先への通信を開始する必要があるとき、ノード10は、ユニキャストR_ReqメッセージをネイティブBN20に送信する。ネイティブBNは、同じLPG1内のBN20である。R_Reqは、中継ノードによって中継される。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノード10である。具体的なルートは、ルーティングテーブル内の次ホップ情報によって決定される。R_Respは、宛先ノード又は宛先ノードに対してネイティブなBN20のいずれかによって開始されるメッセージである。R_Reqは、宛先ノードが見つかるまで又は最大ホップカウントに達するまで中継される。最大ホップカウントは、R_Reqが誤った方向に無限に中継されるのを阻止する。R_Reqが中継されるたびに、ホップカウントは1だけ増分される。R_Reqは、中継ノードによってのみ中継され、フラッディングしない。
【0077】
もしBN20がR_Respを発行できないならば、BN20は、R_Reqを隣接するBNに向けて中継する。BN20は、最大ホップカウントに達するまで又はBN20がR_Respを発行できるまで、R_Reqを他のBN20に転送する。BN20がR_Respを発行するとき、そのR_Respは、隣接するLPGに宛先があることを示す。
【0078】
R_Reqは、R_Reqのタイプ、最大ホップカウント、前LPG識別子、宛先、宛先シーケンス番号、ソース識別子、及びソースシーケンス番号を含む。R_Reqのタイプは、通常や応答済みなどであってよい。R_Reqのタイプは、R_Reqが宛先に達する前に応答されたかどうかを識別するために使用され、もしR_Reqが宛先ノードに達する前に既に応答されているならば、宛先ノードは、R_Respを発行する必要はない。上述のように、最大ホップカウントは、ルーティング検索を制限するために使用される。前LPG識別子は、すぐ隣りのLPG1の識別子であり、もしR_Reqが別のLPGから来たものならば、そのLPG1は、R_Reqが直前に中継されていたところである。前LPG識別子は、ソースノードが属しているLPG1における現LPG識別子に等しい。宛先IDは、宛先ノードの識別子である。ソースIDは、ソースノードの識別子である。ソースシーケンス番号は、各R_Reqデータパケット及びR_Reqの順番を一意に識別するために使用される。別の実施形態では、R_Reqは、更に、ターゲットBN識別子、ターゲットBNに向かう次ホップ識別子、及び前ホップを含む。ターゲットBN識別子は、ノード10が同じLPG1内のBN20を区別することを可能にする。LPG1内に2つ以上のBN20がある場合、ノード10は、どの方向にR_Reqを中継す
るかを知ることができる。ターゲットBNに向かう次ホップ識別子は、中継ノードがR_ReqをターゲットBNに向けて中継するために使用される。次ホップのみが、R_Reqを中継する。逆経路の場合、ノード10は、前ホップを使用する。R_Respは、中間ノードのルーティングテーブルに基づいて中継されてソースに戻される。ソースは、R_Reqが転送されるときにルーティングテーブルに挿入され、ルーティングエントリは、義務外部宛先としてソースノードを有するノードによって、各LPG内において維持される。前ホップを含ませることによる利点は、R_Respが複数のLPGを通って移動する場合、中間LPG1がルーティングテーブル内にソースノードを有さないかもしれないことにある。中間LPGは、ソースLPGと宛先LPGとの間にあるLPGである。ソースLPG、中間LPG、宛先LPGを含むノードは、全て、ソース及び宛先のルーティング情報を有する。前ホップは、R_Reqから抽出され、後の使用に備えてメモリに格納される。
【0079】
R_Respは、ホップカウント、次LPG識別子、宛先識別子、宛先シーケンス番号、ソース識別子、ソースシーケンス番号、及び次ホップ中継を含む。ホップカウントは、宛先ノードがソースノードから離れているホップ数である。次LPG識別子は、R_Respがこれから中継される次のLPGの識別子である。
【0080】
図9に示されるように、ノード10は、ステップ400においてアイドル状態にある。ステップ900において、R_Req又はR_Respが到着する。ステップ905では、ノード10は、受信されたデータパケットがR_Reqであるか又はR_Respであるかを判定する。この判定は、到着データパケットのフォーマット及びそれに含まれる情報に基づく。
【0081】
もし到着データパケットがR_Reqであるならば、プロセスは、ステップ910に進む。ステップ910では、ノード10は、R_Reqが新しい要求であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわちソースシーケンス番号に基づく。R_Reqパケットが受信されるたびに、パケットからソースシーケンス番号が抽出され、メモリに格納される。新しいR_Reqパケットが到着すると、最後に格納されたソースシーケンス番号が、到着R_Reqパケットのソースシーケンス番号と比較される。もしソースシーケンス番号が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、パケットは破棄される。もしソースシーケンス番号が、メモリに格納されている値よりも大きいならば、R_Reqは新しく、ステップ915において、ノード10は、R_Reqに対する応答が既に発行されているかどうかを判定する。判定は、R_Reqに含まれるR_Reqタイプの指標に基づく。もしR_Reqタイプが、R_Reqに対する応答が既に発行されたことを示すならば、ステップ930において、ノード10は、R_Reqを宛先へ中継する。R_Reqが応答されていないときは、ステップ920において、ノード10は、それが宛先のLPG内のBN20であるか又は宛先であるかを判定する。
【0082】
もしノード10が、宛先のLPG内のBN20又は宛先のいずれかであるならば、ステップ925において、ノード10は、R_Respを発行し、R_Reqのタイプを「応答済み」に変更する。その後、ノードは、ステップ930において、R_Req中継機能を実施する。R_Req中継機能は、後述される。R_Req中継機能が実施された後、ステップ935において、ノード10は、R_Reqのソースのためのルーティングを更新する、すなわちソースの次ホップを、R_Reqが来たところにする。
【0083】
もしR_Reqのタイプが、R_Reqに対する応答が発行されていないことを示すならば、ステップ920において、ノード10は、自身が応答を発行できるかどうかを判定する。R_Reqを発行できるのは、宛先ノード又はBN20のみである。ノード10は
、R_Reqから宛先識別子を抽出し、それを自身の識別子と比較する。もし識別子が一致するならば、ノード10は宛先ノードである。もし識別子が一致しないならば、ノード10は宛先ノードではない。また、宛先識別子を使用して、ノード10は、宛先ノード用のBN20について、ルーティングテーブル内を調べる。ノード10は、BN20の識別子を自身の識別子と比較する。もし識別子が一致するならば、ノード10は、宛先ノード用のBN20である。もし識別子が一致しないならば、ノード10は、宛先ノード用のBN20ではない、すなわち宛先ノードがあるLPG1内のBNではない。
【0084】
もしノード10が、宛先ノード、又は宛先ノードのLPG1内のBN20のいずれかであるならば、ステップ925において、BN20又はノード10は、R_Respを発行する。また、ノード10は、R_Reqのタイプを応答済みに変更し、ステップ930において、R_Reqは宛先へ中継される。
【0085】
(ステップ920において、)もしノード10が、宛先ノード、又は宛先ノードのLPG1内のBN20のいずれでもないならば、ステップ930において、ノード10は、R_ReqをBN20又は宛先ノードに向けて中継する。ソースノードは、BN20にとっての義務外部宛先になり、BN20は、ソースノードにとっての入口BNである。R_Req中継機能は、図10に記載されており、後ほど詳しく説明される。
【0086】
ステップ935において、ノード10は、ルーティングテーブル内の、ソースノードについてのルーティング情報を、R_Reqからの情報によって更新する。例えば、ノード10は、ソースノード識別子、ソースノードについてのLPG情報、及びソースノードについてのホップカウントを追加することができる。
【0087】
もし到着データパケットがR_Respであるならば、プロセスは、ステップ940に進む。ステップ940において、ノード10は、R_Respが新しい応答であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわち宛先シーケンス番号に基づく。データパケットが受信されるたびに、パケットから宛先シーケンス番号が抽出され、メモリに格納される。新しいデータパケットが到着すると、最後に格納された宛先シーケンス番号が、到着データパケットの宛先シーケンス番号と比較される。もし宛先シーケンス番号が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、パケットは破棄される。もし宛先シーケンス番号が、メモリに格納されている値よりも大きいならば、R_Respは新しく、ステップ945において、R_Respは、ソースノードに向けて中継される。
【0088】
R_Resp中継機能は、図11に記載されており、後ほど詳しく説明される。
【0089】
ステップ950において、ノード10は、ルーティングテーブル内の、宛先ノードについてのルーティング情報を、R_Respからの情報によって更新する。例えば、ノード10は、宛先ノード識別子、宛先ノードについてのLPG情報、及び宛先ノードについてのホップカウントを追加することができる。
【0090】
図10は、R_Reqのための中継プロセスを説明している。プロセスは、ステップ1000から開始する。ステップ1005において、ノード10は、宛先ノードが同じLPG1内であるか、すなわちローカルな宛先であるかどうかを判定する。ノード10は、ルーティングテーブルを調べ、宛先ノードがLPG内宛先であるかどうかをチェックする。もし宛先ノードがLPG内ルーティングエントリとして挙げられているならば、宛先は、同じLPG内である。もし宛先がローカルである、すなわちLPG内であるならば、ノード10は、R_Reqが宛先ノードに到達したか、すなわち宛先ノードの識別子が現ノードの識別子と同じであるかどうかを判定する。宛先ノードは、自身に宛てられたR_Re
qを受信すると、R_Reqの転送を終了させる。
【0091】
ステップ1010、1015、1030、及び1035は、ローカルな宛先及び非ローカルな宛先のどちらの場合も実施される。ステップ1010では、ノード10は、自身がソースにとっての入口(ingress)BNであるかどうかを判定する。入口BNは、LPG1内のノード10のなかで別のLPG1内のノード10からのR_Reqを最初に受信するBN20、又は義務外部宛先リスト内にR_Reqのソースを既に有しているBN20である。義務外部宛先は、そのLPGの外側のノードについての特別なルーティングエントリである。とあるノードが義務外部宛先を有しているときは、そのノードを通じて外部宛先に到達可能であることを知らせるために、それらの義務外部宛先のノードIDがノードのMR(メンバレポート)の一部として含まれる。中継ノードは、「k」回の前制御メッセージサイクル内においてダウンストリームノードの少なくとも1つのMR300をアップストリームノードへ中継するノードである。
【0092】
もしノード10がソースの入口BNであるならば、ステップ1015において、ノード10は、ソースノードについてのエントリによって、ルーティングテーブルを更新する。ソースノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード(入口BN)は、自身のLPG1にルーティング情報を知らせる又は公示する役割を担う。
【0093】
ノード10がルーティングテーブルを更新した後、ステップ1035において、ノード10(入口BN)は、R_Reqをブロードキャストする。ブロードキャストに先立ち、ステップ1032において、ノード10は、ホップカウントを1だけ増分させる。また、ステップ1034において、ノード10は、R_Reqの最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、R_Reqに含まれる。ノード10は、最大ホップカウントを、例えば受信されたR_Reqのホップカウント+1などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、R_Reqは転送されず、ステップ1040において、ノード10は停止する。
【0094】
もし宛先ノードがローカルであり、ノード10が入口BNではないならば、ステップ1030において、ノード10は、自身が中継ノードであるかどうかを判定する。次ホップ中継は、ルーティングテーブル内の情報に基づく。もしノード10が中継ノードであるならば、ステップ1035において、R_Reqはブロードキャストされる。プロセスは、次いで、ステップ1040において終了する。ブロードキャストに先立ち、ステップ1032において、中継ノードは、ホップカウントを1だけ増分させる。また、ステップ1034において、中継ノードは、R_Reqについての最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、R_Reqに含まれる。中継ノードは、最大ホップカウントを、例えば受信されたR_Reqのホップカウント+1などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、R_Reqは転送されず、ステップ1040において、中継ノードは停止する。
【0095】
もし宛先ノードが非ローカルな宛先であり、ノード10が入口BNではないならば、ノード10は、自身が出口(egress)BNであるかどうかを判定する。出口BNは、自身のLPG内のノード10からR_Reqを受信するBN、又は(義務宛先ではないが)その外部宛先としてR_Reqのソースを既に有しているBNである。出口BN機能は、隣接するLPGがR_Reqを受信できるように、R_Reqを隣接するLPGへブロードキャストすることである。もしノード10が出口BNであるならば、ステップ1025において、ノード10は、前LPG識別子を自身のLPG識別子で置き換え、ステップ1035において、R_Reqをブロードキャストする。ホップカウントが最大ホップカウントに達すると、R_Reqは、これ以上は再ブロードキャストされない。
【0096】
もし宛先ノードが非ローカルであり、ノード10が入口BNでも出口BNでもないならば、ステップ1030において、ノード10は、自身が中継ノードであるかどうかを判定する。
【0097】
次ホップ中継は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノード10である。もしノード10が中継ノードでないならば、R_Reqは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1035において、R_Reqはブロードキャストされる。プロセスは、次いで、ステップ1040において終了する。
【0098】
図11は、R_Respのための中継プロセスを説明している。プロセスは、ステップ1100から開始する。ステップ1105において、ノード10は、ソースノードが同じLPG1内であるか、すなわちローカルなソースであるかどうかを判定する。ノード10は、ルーティングテーブル内を調べ、ソースノードのLPG1のLPG識別子を読み出す。ソースノードのLPG識別子は、ノード10のLPG識別子と比較される。もし識別子が一致するならば、ソースノードは同じLPG1内である。中継プロセスは、非ローカルな宛先の場合に2つ余分にステップがあることを除き、ローカルな宛先及び非ローカルな宛先のどちらの場合も同様である。
【0099】
ステップ1110、1115、1130、及び1135は、ローカルなソース及び非ローカルなソースのどちらの場合も実施される。ステップ1110では、ノード10は、別のLPG内のノードからR_Respを受信するときに、自身が宛先にとっての入口BNであるかどうかを判定する。入口BNは、別のLPG1内のノード10からR_Respを受信するBNである。
【0100】
もしノード10が入口BNであるならば、ステップ1115において、ノード10は、宛先ノードについてのエントリによって、ルーティングテーブルを更新(inserts updates)する。宛先ノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード(入口BN)は、自身のLPG1にルーティング情報を知らせる又は公示する役割を担う。
【0101】
ノード10がルーティングテーブルを更新した後、ステップ1135において、ノード10(入口BN)は、R_Respをブロードキャストする。一実施形態では、R_Respは、R_Reqと同じ経路を通って中継される。
【0102】
もしソースノードがローカルであり、ノード10が入口BNではないならば、ステップ1130において、ノード10は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノードである。もしノード10が中継ノードでないならば、R_Respは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1135において、R_Respはブロードキャストされる。プロセスは、次いで、ステップ1140において終了する。
【0103】
もしソースノードが非ローカルなソースであり、ノード10が入口BNではないならば、ステップ1120において、ノード10は、自身が出口BNであるかどうかを判定する。出口BN機能は、隣接するLPGがR_Respを受信できるように、R_Respを隣接するLPGへブロードキャストすることである。もしノード10が出口BNであるならば、ステップ1125において、ノード10は、次LPG識別子を自身のLPG識別子で置き換え、ステップ1135において、R_Respをブロードキャストする。
【0104】
もしソースノードが非ローカルであり、ノード10が入口BNでも出口BNでもないならば、ステップ1130において、ノード10は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノードである。もしノード10が中継ノードでないならば、R_Respは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1135において、R_Respはブロードキャストされる。プロセスは、次いで、ステップ1140において終了する。
【0105】
ひとたびソースノードがR_Respを受信すると、ソースノードは、宛先ノードに対するメッセージやデータの伝送、又は通信を開始させる。
【0106】
上述のように、BN20は、アクティブな通信経路を維持する及び他のノードに移動ノード又は離脱ノードについて知らせる役割を担う。図12は、離脱ノードを検出するプロセスを示している。プロセスは、ステップ400においてBN20がアイドル状態にあるところから開始する。ステップ1200において、離脱ノードが検出される。離脱ノードは、2つの方法のうちの1つを使用して検出される。離脱ノードは、外部ハートビートメッセージ200のオーバヒアリングによって検出することができる。詳細には、離脱ノードは、外部ハートビートメッセージ200に含まれるメンバシップリストに自身の識別子を含まれている。BN20は、自身のLPG1内にあったノードが外部メンバシップリストに挙げられたときに、そのノードがLPGを離脱したと判定する。或いは、離脱ノードは、その離脱ノードが外部LPG1の識別子を伴うMR300をブロードキャストしたときに検出することができる。BN20は、これまで同じLPG内にあったノードからMR300をオーバヒアリングする。BN20は、自身のLPG識別子を、MR300内の識別子と比較する。もし識別子が異なるならば、ノード10は離脱している。1つのノード10は、1つのLPG1のメンバであることしかできない。
【0107】
ステップ1205において、BN20は、自身のルーティングテーブルを離脱ノードについて更新する。具体的には、BN20は、離脱ノードのLPGを変更する。ルーティングテーブルが更新されたら、BNは、ステップ400のアイドル状態に戻る。BNは、次いで、離脱ノードに関連した情報を公示する。
【0108】
別の実施形態では、(BN20だけでなく)任意のノードが、外部ハートヒート又は外部MR300をオーバヒアリングすることによって離脱ノードを検出することができる。
【0109】
BN情報は、ルーティングテーブルから取り出される。もしノード10がBN20であるならば、BN20は、次のMR300に離脱ノード通知を含ませる。通知は、ノードがLPG1から離れたことの肯定声明である。通知は、離脱ノードの識別子と、新しいLPGの識別子とを含む。ステップ1325において、BN20は、次いで、その離脱ノードについてアクティブな通信が継続中であるかどうかを判定する。通信は、もし離脱ノードが通信の宛先又はソースのいずれかであるならば継続中である。もしアクティブな通信が継続中でないならば、BN20は、アイドル状態(ステップ400)に戻る。しかしながら、もしアクティブな通信が継続中であるならば、BN20は、ルートを維持しなければならない。ルートは、ステップ1330において、義務外部宛先のリストに離脱ノードを追加してルーティングテーブルを更新することによって維持される。このリストは、次のMR300に含められてブロードキャストされ、後に、ハートビートメッセージ200に含められる。BN20は、次いで、アイドル状態(ステップ400)に戻る。
【0110】
もしステップ1305において、ノード10がBN20ではないならば、ノード10は
、BN20が離脱ノード通知を既に送信したかどうかを判定する。ステップ1310において、ノード10は、BN20から受信された最新のMR300を離脱ノード通知についてチェックする。もしMR300が離脱ノード通知を含んでいたならば、ノード10は、アイドル状態に戻る。ノード10は、離脱ノード通知に含まれる情報によって、ルーティングテーブルを更新する。
【0111】
もしBN20からのMR300が離脱ノード通知を含んでいなかったならば、ノード10は、別のノードが既に離脱ノート通知を送信したかどうかを判定する。ステップ1315において、ノード10は、任意のノードから受信された最新のMR300を離脱ノード通信についてチェックする。もしMR300が離脱ノード通知を含んでいたならば、ノード10は、アイドル状態に戻る。
【0112】
もしどのノード10からも離脱ノード通知が受信されなかったならば、プロセスは、ステップ1320に進み、ここで、ノード10は、自身のMR300に離脱ノード通知を挿入する。ノード10は、次いで、(あたかも自身がBN20であるかのように)ステップ1325及び1330を実施する。
【0113】
図14は、義務外部宛先を他のノードに公示又は通知するプロセスを示している。義務外部宛先リストの公示は、ハートビートメッセージ200及びMR300を使用して達成される。義務外部宛先リストは、ハートビートメッセージ200及びMR300に追加される。
【0114】
図14に示されるように、ノード10は、ステップ400のアイドル状態から開始する。ハートビートメッセージ200及びMR300は、定期的にブロードキャストされる。期間は、ハートビートサイクル又はMRサイクルである。一連のハートビートメッセージ200又はMR300の間の期間は、タイマ又は計時手段によってカウントされる。ハートビートメッセージ200及びMR300は、サイクル期間の満了によってトリガされる。ステップ1400において、ハートビートメッセージ200又はMR300のいずれかが、タイマの1つの満了によってトリガされる。ステップ1405において、ノード10は、自身が通常ノード(GN)であるか又はGH25であるかを判定する。もしノード10がGH25であるならば、ステップ1410において、義務外部宛先リストは、LPG1の外部宛先としてハートビートメッセージ200に追加される又は符号化される。ステップ1415において、ハートビートメッセージ200はブロードキャストされる。GH25は、その後、アイドル状態(ステップ400)に戻る。
【0115】
もしノード10がGNであるならば、ステップ1420において、義務外部宛先リストは、MR300に追加される又は符号化される。ステップ1425において、MR200はブロードキャストされる。GNは、その後、アイドル状態(ステップ400)に戻る。
【0116】
ステップ1430において、GH25は、MR300を受信する。ステップ1435において、GHは、義務外部宛先リストをMR300から抽出し、後のブロードキャストに備えて格納する。格納された義務宛先リストは、次のハートビートメッセージに含められる。その後、GH25は、アイドル状態(ステップ400)に戻る。
【0117】
本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。
【技術分野】
【0001】
本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network(アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス)」と題された、2006年10月23日出願の共同所有の米国同時係属特許出願第11/585,047号(「’047出願」)に関連している。
【0002】
本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、複数のローカルピアグループ間でメッセージをルーティングするための方法に関する。
【背景技術】
【0003】
’047出願は、1つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してローカルピアグループ(LPG)を維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループに編成するための方法を記載している。移動車両は、シングルホップ伝送又はマルチホップ伝送のいずれかを使用してデータをルーティングするように適応される。‘047出願は、各ノード又は各移動車両内のローカルルーティングテーブルをもとにして具体的なLPG内ルートが決定されることを記載している。ローカルルーティングテーブルは、ノードによってLPG内の他のノードから受信される情報をもとにして作成される。ルーティング経路は、絶えず更新される。LPGのサイズは、LPGが管理サイズであることを保証するためにプリセットされる。サイズは、ホップカウント限界に基づいてプリセットされる。
【0004】
ネットワークは、複数のLPGを含むと考えられ、各LPGは、幾つかの移動車両を含む。メッセージは、例えばLPG内通信のようにLPG内で伝送される。しかしながら、例えばLPG間通信のように複数のLPGの間での伝送を必要とするメッセージもある。道路障害物の緊急警告、交差点との連係、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含むこれらのメッセージは、LPG間で効率良く伝送可能でなければならない。
【0005】
性能要件は、衝突回避などの様々なVSC応用形態を支援するために、待ち時間が短いこと(約100ミリ秒)及びスループットを維持すること(別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合)を含む。
【0006】
したがって、複数のローカルピアグループ間で伝送するための方法が必要とされる。
【発明の概要】
【0007】
ゆえに、複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法が開示される。各ローカルピアグループ(Local Peer Group)は、複数の移動ノードを含む。本方法は、ソースノードからルート要求メッセージを伝送するステップであって、ルート要求メッセージは、宛先ノード、ソースノードのLPG識別子、及び前LPG識別子を少なくとも含む、ステップと、ルーティング要求メッセージを宛先ノードへ中継するステップと、ルーティング応答を発行するステップと、応答をソースへルーティングするステップと、ルート要求メッセージをネイティブ境界ノードへ中継するステップと、ソースノードにおいてルーティング応答を受信するステップと、ルーティング応答の受信を受けてデータを伝送するステップと、を含む。データは、初めは、ルーティング応答を伝送したノードを使用して中継されるが、実際のルートは、更新後のローカルルーティングテーブルをもとにして決定される。
【0008】
ルート要求メッセージは、ルート要求メッセージを外部境界ノードへ転送すること、宛先ノードが外部境界ノードのLPG内であるかどうかを判定すること、宛先ノードが上記LPG内でないならば、ルート要求メッセージを別の境界ノードへ中継すること、及び宛先ノードが上記LPG内であるならば、ルート要求メッセージを宛先ノードへ中継することによって、宛先ノードへ中継される。
【0009】
宛先ノードは、ルート要求の受信を受けて、ルーティング応答をソースノードへ伝送する。ルーティング応答は、ルート要求を通じて発見された経路を通じてソースノードへ中継される。
【0010】
オンデマンドな方法は、更に、ルート要求メッセージを受信するノードが宛先ノード又は宛先ノードのLPG内の境界ノードであるかどうかを判定するステップを含む。
【0011】
オンデマンドな方法は、更に、宛先ノードがルート要求メッセージを受信しているノードと同じLPG内であるかどうかを判定するステップと、ルート要求メッセージを受信しているノードが入口境界ノードであるかどうかを判定するステップと、ソースノードの識別子によって宛先リストを更新するステップとを含む。
【0012】
オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定することを含む。
【0013】
オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルート要求メッセージ内の前LPG識別子を出口境界ノードのLPGのLPG識別子で置き換えるステップとを含む。
【0014】
オンデマンドな方法は、更に、ソースノードがルーティング応答を受信しているノードと同じLPG内であるかどうかを判定するステップと、ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、宛先ノードの識別子によって宛先リストを更新するステップとを含む。
【0015】
オンデマンドな方法は、更に、ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを含む。
【0016】
オンデマンドな方法は、更に、ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルーティング応答内の次LPG識別子を出口境界ノードのLPGのLPG識別子で置き換えるステップとを含む。
【0017】
オンデマンドな方法は、更に、宛先ノードによってデータが受信されるまでソースノードから宛先ノードへのルートを維持するステップを含む。
【0018】
ルートを維持するステップは、ノードがLPGを変更したかどうかを検出するサブステップと、ノードがLPGを変更したという通知をLPG内の全てのノードへ伝送するサブステップと、変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、LPGを変更したノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップとを含む。
【0019】
ルーティング要求メッセージは、宛先ノード識別子及び前ノード識別子を含む。
【0020】
また、複数のローカルピアグループ間での通信のために境界ノードを選択するための方
法が開示される。方法は、既定のノードを発信元とする第1の制御パケットを受信するステップと、第1の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、もし第1の制御パケットが外部ローカルピアグループを発信元とするならば、パケットをグループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、少なくとも1つの候補からの伝送されたパケットをグループヘッダにおいて受信するステップと、受信されたパケットに基づいて候補のリストを作成するステップと、候補のリストから1つの候補を境界ノードとして選択するステップと、選択された境界ノードの識別子を含むデータパケットを伝送するステップとを含む。既定のノードは、グループヘッダである。
【0021】
候補のリストは、プリセット期間にわたって有効である。期間は、Time−to−Live値である。Time−to−Live値は、第1の制御パケットの伝送期間の倍数である。方法は、更に、プリセット期間が満了したかどうかを判定するステップと、もしプリセット期間が満了したならば候補を削除するステップとを含む。方法は、更に、同じ候補の識別子を含むデータパケットをグループヘッダが受信したときにTime−to−Live値をリフレッシュするステップを含む。
【0022】
境界ノードは、各候補についての、グループヘッダからのホップカウントに基づいて選択される。
【0023】
本方法は、更に、選択された境界ノードの識別子を含むデータパケットを受信するステップと、選択された境界ノードの識別子を受信ノードの識別子と比較するステップと、比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、を含む。
【0024】
本方法は、更に、ステータスを境界ノードに変更した後に定期的に第2の制御パケットを伝送するステップを含む。
【0025】
本方法は、グループヘッダから上記境界ノードと反対の相対方向にある第2の境界ノードを選択するステップを含む。
【0026】
本発明のこれらの及びその他の特徴、利益、及び利点は、以下の図面を参照することによって明らかになる。なお、図面を通じて、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0027】
【図1】発明の一実施形態にしたがった、LPG間通信に適応され尚且つ互いの近くにある複数のローカルピアグループを示している。
【図2】典型的なハートビートメッセージを示している。
【図3】典型的なメンバシップレポートメッセージを示している。
【図4】発明の一実施形態にしたがった、境界ノード(BN)を選択するための方法の流れ図を示している。
【図5】発明の一実施形態にしたがった、境界ノード(BN)を選択するための方法の流れ図を示している。
【図6】発明の一実施形態にしたがった、BNの選択のための有限状態図を示している。
【図7】発明の一実施形態にしたがった、ルーティングテーブルを作成してルーティングテーブルのエントリを更新する方法の流れ図を示している。
【図8】別のローカルピアグループ内のノードから受信されたデータパケットを処理する方法の流れ図を示している。
【図9】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図10】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図11】発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。
【図12】発明の一実施形態にしたがった、移動度検出方法の流れ図を示している。
【図13】発明の一実施形態にしたがった、ローカルピアグループからの離脱ノードが検出されたことをノードに知らせる方法の流れ図を示している。
【図14】発明の一実施形態にしたがった、義務外部宛先リストを広める方法の流れ図を示している。
【発明を実施するための形態】
【0028】
本発明にしたがうと、ノード又は移動デバイスは、管理可能なグループに編成される。これらのグループは、ノード間でのデータの伝送を調整するために使用される。グループは、隣接するノードの相対位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ(「LPG」)は、1つのLPG115内で及び複数のLPG間で電波信号をルーティングするための基礎である。電波信号は、車両の安全性の応用及び情報の応用を含む。
【0029】
図1は、2つのLPG(一般に1として表示される)、すなわちLPG A(1a)及びLPG B(1b)を示している。LPG A1aは、3つの個々のノードを含む(ノードは、一般に「10」として表示される)。LPG1内の1つのノードが、グループのリーダになるべく選択される。リーダは、GHと称され、LPG A1aの場合はGHaとして表わされる(GHは、一般に「25」として表示される)。GH25は、LPG1を管理する。また、GH25は、特殊なノードを境界ノード(BN:一般に「20」として表示される)にするべく選択する。BN20は、複数のLPG1間でデータを中継する役割を担うノード10である。BN20は、複数のLPG1の電波有効範囲が重なるエリア内に物理的に位置している。BN20は、オンデマンドなルート検索及び維持管理の役割を担う。BN20は、また、LPG間通信のための有効ルートを維持する役割も担う。BN20は、そのメンバシップレポート(MR)300の一部として特定の外部宛先リストを他のノード10に報告する。特定の外部宛先リストは、義務(obligated)外部宛先を含む。義務外部宛先は、通信経路がアクティブで尚且つ外部宛先の次ホップLPGがBNの位置しているLPG1であるような宛先を含む。また、BN20は、複数のLPG1からハートビートメッセージ200及びMR300を横聞き(overhear)するので、BN20は、離脱ノード又は移動ノードの通知も支援する。
【0030】
LPG1のサイズは、所定のLPG1内のノード10が多くなりすぎないように制御される。より詳細には、GH25は、特定のフォーマットを有する電波信号をブロードキャストし、GH25の範囲内の他のノード10は、その電波信号を受信する能力を有する。電波信号は、ホップカウント、又は信号が有効であるTime−to−Live(TTL)値を含む。すなわち、もし信号が、指定された値を上回るホップカウントにわたって中継されるならば、ノードは、LPG1に参加しない。この電波信号は、ハートビートメッセージ200と呼ばれる。GHの形成、維持管理、及び選択、並びにLPG1の制御は、参照によって本明細書に組み込まれる’047出願に記載されている。
【0031】
上記のように、2つの異なるLPG1からの電波信号がヒアリング可能な領域がある。この領域では、ノードは、2つの異なるハートビートメッセージ200を受信するが、ノード10が参加できるのは、1つのLPG1のみである。この重複エリアは、LPG交差エリア(LIA)と呼ばれる。ノード10は、最も優先度の高いLPG1に参加する。一実施形態では、優先度は、LPG識別子に基づいて判定される。例えば、図1では、2つのLPG1と2つのGH25がある。
【0032】
LIA内のノード10は、BN20の候補であることができる。しかしながら、LIA内にノード10がある保証はない。したがって、エッジハートビートが使用される。エッジハートビートは、有効HC限界よりも1ホップだけ大きいHCを伴うハートビートメッセージである。ノード10は、エッジハートビートを受信した後はLPG1に参加することができない。ハートビートメッセージ200と異なり、エッジハートビートは中継されない。
【0033】
図2は、発明にしたがったハートビートメッセージ200の一例を示している。GH25は、ハートビートメッセージ200を定期的に送出し、LPGを識別するとともにLPGに関する情報を提供する。この期間は、固定間隔(T)である。間隔(T)の値は、設計上又は動作上の必要性に基づいて選択可能である。GH25は、また、LPG内の全てのノードのリストを維持する。このリストは、ノードがLPGにいつ入ったか又はGH25がノード10からいつステータス更新を受信したかについてのタイムスタンプを含む。リストは、LPGに対する様々な管理機能及び制御機能のために使用される。例えば、リストは、グループサイズの追跡、マルチキャストルーティングテーブルの作成及び更新、並びにヘッダ解決に使用することができる。また、このリストは、LPG1内の他の全てのノードに定期的にブロードキャストされる。LPGハートビートメッセージ200は、GH25の電波周辺内の全てのノードにブロードキャストされる。
【0034】
ハートビートメッセージ200は、LPGの識別子、GH識別、シーケンス番号、及び例えば完全なグループリストを伴うハートビート、漸増性のグループリストを伴うハートビート、又はグループリストを伴わないハートビートなどのハートビートメッセージのタイプを含む。一実施形態では、ハートビートメッセージは、全てのメッセージ内に完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビートメッセージには、大量の帯域幅が必要である。別の実施形態では、(n−1)個おきの各ハートビートメッセージ200が完全なグループリストを含む。例えば、2つおきの各ハートビートが完全なグループリストを含む。ToHb(type of heartbeat)は、ハートビートメッセージ200のタイプを示す。ハートビートメッセージのタイプは、LPG1のトポロジ変化速度と、ハートビートのブロードキャストの頻度とによって影響される。LPG1のトポロジ変化速度が増すにつれて、全てのハートビートメッセージ200に完全なグループリストが含まれている必要性が高まる。
【0035】
ハートビートメッセージ200は、GHからのホップカウント(HC)を含む。最初、HCは、例えば1などの既定の値に設定される。ハートビートメッセージ200がノードによって中継されるたびに、中継ノードは、HCの値を1だけ増加させる、すなわちHC=HC+1とする。HC値は、LPGサイズを制限するため、ハートビートメッセージ200内の情報の古さを示すため、及び制御パケットのルーティングを制御して上記のようにオーバーヘッドを低減させるために使用することができる。HCが最大ホップカウントまで増分されると、制御パケットは、中継されなくなる。
【0036】
最大ホップカウント、HC、及びSeq.No.を利用することによって、LPG1内で制御パケットが無限に重複する事態が阻止される。ホップカウントは、中継戦略にも使用することができる。ノードは、ハートビートメッセージを転送するときに、そのハートビートメッセージ200を誰がリレーしたのかを次ホップノードが知ることができるように、自身のID情報をメッセージ内に含ませる。
【0037】
上記のように、ハートビートメッセージ200は、グループリストも含むことができる。グループリストは、LPG1内のメンバの数、各数のIPアドレス、GHからのホップ
カウント、BN20としてのステータス、BNの有効期限、及び分類などの、LPG1のメンバに関する情報を含むことができる。
【0038】
分類は、例えばアップリンク、ダウンリンク、及びピアのような、GHからの相対方向に言及したコードであってもよい。ピア分類は、ノードがGH25から同じ無線有効範囲内にあることを示す、すなわち、全てのピアノードは、GHからのホップカウントが同じである。アップストリームノードは、ハートビートによって決定される。ダウンストリームノードは、後述されるメンバシップレポート(MR)300に基づいて決定される。アップストリーム伝送は、GH25に向かう通信を表し、ダウンストリーム伝送は、GH25から離れる通信を表す。この分類は、相対的な表現である。各ノードは、自身に隣接するノードを3つの異なるクラスに分類することができる。もし別のノードのメンバシップレポートが、自身のホップカウント(HC)よりも1だけ小さいHCを有するならば、ノードは、アップストリームノードである。もし別のノードのHCが、自身のHCと同じであるならば、ノードは、ピアである。もし別のノードのHCが、自身のHCよりも1だけ大きいならば、ノードは、ダウンストリームノードである。分類は、BN候補のグループから、GH25の各側について1つずつBN20を選択するために使用される。
【0039】
図3は、メンバシップレポート(MR)300の一例を示している。MR300は、GH25ではない他のノードによってブロードキャストされる制御パケットであり、その受け手はGH25である。MR300は、ハートビートメッセージ200に応答して生成される。MR300は、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードのための次ホップなどの、収集可能なルーティング情報を含む。MR300は、ハートビートメッセージ200と同じ情報を幾つか、すなわちGID及びグループヘッダIDを含む。MR300は、また、MR Seq.No.も含む。MR Seq.No.は、ハートビートメッセージ200のSeq.No.と同様であり、MRの順番を維持するために使用される。MR Seq.No.は、1つの特定のノードに対するMRの順番である。通常、MR Seq.No.は、MR300をトリガしたハートビートメッセージ200のSeq.No.と同じ値を有する。
【0040】
発信元ノードすなわちMR300を生成したノードのノードIDも、MR300に含まれる。
【0041】
MR300は、次ホップ中継IDも含む。次ホップ中継IDは、GH25に向かうMR300のための中継命令である。次ホップ情報は、受信されたハートビートメッセージ200をもとにして直接決定される。ノード10は、新たなすなわち新着のハートビートメッセージ200を受信すると、いかなるパケット処理よりも前に、IP層及びMAC層をもとにして前中継ノードの識別を回復させる。前中継ノードの識別は、メモリに格納されており、MR300のための次ホップ中継IDとして使用される。ノード10は、ハートビートメッセージ200を転送するときに、そのIDをパケット内に含ませる。受信する次ホップノードは、新たなすなわち新着のハートビートメッセージ200を受信すると、このIDを、GH25に到達するための次ホップ中継IDとして格納する。新たなすなわち新着のハートビートメッセージ200は、最低のHCを伴った、より新しいシーケンス番号を有する。
【0042】
MR300は、また、「MRのタイプの指標」(Type of MR indicator, ToMR)も含む。MR300には、2つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバのMRは、発信元ノードからのMR300のみを含む。統合された複数メンバのレポートは、2つ以上のノード10のMR300を含む。統合されたレポートは、オーバーヘッド、及び制御パケットに必要な帯域幅を低減させるために使用することができる。複数のMRを含む1つのMR300が送信される。
【0043】
また、MR300は、GHからのホップカウント(HCGH)を含むことができる。(HCGH)は、GHからMR300の発信元ノードまでのHC値である。MR300は、報告ノードのための使用可能チャネルリストを含む。また、MR300は、マルチキャストメッセージを中継することに対するそのステータス又は有効性、すなわち転送ノードステータスを含む。MRは、また、BN20の候補指名を含む、すなわちノード10は、自身がBN20の候補であることを宣言してGH25に通知する。MRは、もし可能な場合は、隣接LPGリスト及びアクティブLPG間ノードリストを含む。
【0044】
図4及び図5は、発明の一実施形態にしたがった、BNを選択するための方法を示している。図4は、GH25ではない全てのノードについての機能ブロックを示している。図5は、GH25であるノード10の機能ブロックを示している。
【0045】
ノード10は、ハートビートメッセージ200又はエッジハートビートのいずれかである外部ハートビートをヒアリングすると、BN候補になる。外部ハートビートは、同じLPG1からのノード10によって生成されたのではないメッセージ又はパケットである。選択されたBN20のみが、エッジハートビートをブロードキャストする。もしLPGのエッジにBN20がある場合は、ノード10は、エッジハートビートをブロードキャストする。BN20は、ハートビートメッセージのホップカウント限界にある場合にLPG1のエッジにある。エッジハートビートは、ハートビートメッセージのホップカウントに対する追加のホップでブロードキャストされ、隣接するLPGが別のLPG1の存在に気づくことを可能にする。外部ノードは、エッジハートビートを受けると、LPG1に参加しない。エッジハートビートは、転送されない。
【0046】
機能ブロック400において、非GHノードはアイドル状態にある。説明のために、非GHノードは、一般的ノード(GN:General Node)として言及される。ブロック405では、ハートビートメッセージ200が到着する。ハートビートメッセージ200は、LPGの識別子を含む。GNは、パケットフォーマットに基づいて、パケットがハートビートメッセージ200であるかどうかを判定する。ブロック410では、GNは、ハートビートメッセージ200が例えば別のLPG1からのハートビートメッセージ200のような外部HBであるかどうかを判定する。GNは、ハートビートメッセージ200に含まれるLPG識別子を、GNが入っているLPGの識別子と比較する。もしこれらの識別子が同じでないならば、ブロック415において、GNは、自身をBN候補として宣言する。GNは、そのステータスを「BN候補」に変更する。GHは、MR300を使用して、BNへの立候補をGH25に通知する。ブロック420において、GNは、次のMRサイクル中にGHへMR300をブロードキャストする。MRは、例えばBNへの立候補などの、ノードステータスのためのフィールドを含む。その後、GNは、ブロック400のアイドル状態に戻り、BN20の決定のために、次のハートビートメッセージ200を待つ。
【0047】
もしブロック410において、GNがLPG識別子を同じだと判定するならば、方法は、機能ブロック425に進む。ブロック425では、GNは、ハートビートメッセージに含まれる任意のBN情報を抽出する。BN情報は、選択されたBNのノード識別子と、その選択されたBNに対応する任意の有効期間(Time−to−Live)値とを含む。有効期間値は、選択されたBNが境界ノードとして機能する期間を表わす。有効期間は、ハートビートサイクルで表わされる。
【0048】
ブロック430では、GNは、自身が選択されたBNであるかどうかを判定する。GNは、ハートビートメッセージ200に含まれる選択されたBNの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック435において、GNは、自身をLPGのBN20であると宣言する。GNは、そのステータスをBN候補からB
N20に変更する。GNは、次のMRサイクルで、自身がBN20であることをLPGの全てのメンバに通知する。MR300は、新しいステータスを含む。
【0049】
その後、ブロック440では、GN(今ではBN20)は、ノード10がハートビートメッセージ200を転送する必要があるかどうかを判定する。より詳細には、BN20は、ノード10がハートビートメッセージ200のためのホップカウント限界に位置するかどうかを判定する。この判定は、ハートビートメッセージ200に含まれるGHへのホップカウントと、ハートビートメッセージ200のための最大ホップカウントとに基づく。ハートビートメッセージ200が転送されるたびに、GHへのホップカウントは、1だけ増分される。GHへのホップカウントは、最大ホップカウントと比較される。もしGHへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ200は、転送されない、すなわち中継されない。その代わり、ブロック450において、BN20は、エッジハートビートをブロードキャストする。エッジハートビートのフォーマットは、ハートビートメッセージ200と同じであり、唯一の違いは、どのエッジハートビート内のHCも、ハートビートメッセージ200が持つことのできる最大ホップカウントよりも1だけ大きいことである。BN20は、次いで、ブロック400のアイドル状態に戻る。
【0050】
もしGHへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック445において、ハートビートメッセージ200は転送される、すなわち中継される。
【0051】
もしブロック430において、選択されたBN20の識別子がGNの識別子と一致しないならば、プロセスは、ブロック440に移動し、GNは、通常ハートビートメッセージ200中継機能を実施する。ブロック440において、GNは、ノード10がハートビートメッセージ200を転送する必要があるかどうかを判定する。GHへのホップカウントが、最大ホップカウントと比較される。もしGHへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ200は、転送されない、すなわち中継されない。BN20は、次いで、ブロック400のアイドル状態に戻る。もしGHへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック445において、ハートビートメッセージ200は転送される、すなわち中継される。GHへのホップカウントは、1だけ増分される。
【0052】
次に、GH25についてのBN選択プロセスが説明される。ブロック400において、GH25ノードはアイドル状態にある。ブロック405では、ハートビートメッセージ200が到着する。ハートビートメッセージ200は、LPGの識別子を含む。GH25は、パケットフォーマットに基づいて、パケットがハートビートメッセージ200であるかどうかを判定する。ブロック410では、GH25は、ハートビートメッセージ200が例えば別のLPG1からのハートビートメッセージ200のような外部HBであるかどうかを判定する。GH25は、ハートビートメッセージ200に含まれるLPG識別子を、GH25が制御しているLPGの識別子と比較する。もしこれらの識別子が同じでないならば、GH25は、ブロック500において、自身をBN候補として宣言する。GHは、ハートビートがエッジハートビート又はハートメッセージ200のいずれであるかに関係なく自身を候補として宣言する。GH25は、そのステータスを「BN候補」に変更する。もしハートビートメッセージ200に含まれるLPG識別子が、GH自身のLPG識別子と同じであるならば、ブロック505において、ハートビートメッセージ200は、BN選択を目的として無視される。
【0053】
もしMR300が到着する場合は、プロセスは、ブロック510から開始する。ブロック515において、GH25は、MR300からBN候補情報を抽出する。GH25は、BN候補について、MR300のステータスフィールドを調べる。もしステータスフィー
ルドが、ノード10がBN候補であることを示すならば、ブロック520において、GH25は、そのノード(GN)の識別子を候補リストに記録する。GH25は、可能性のある全ての候補の候補リストを維持する。G25は、このリストを使用して、少なくとも1つのBN20を選択する。
【0054】
ブロック525において、GH25は、既存のBN25及びBN候補について、有効期間(TTL)値を調整及びリフレッシュする。もしGH25が、BNへの立候補を伴わないMR300をBN20から受信する場合は、GH25は、BN候補のなかから新しいBN20を選ぶことによって、BN20を直ちに置き換える。もしGH25が、BNへの立候補を伴うMR300をBN20から受信する場合は、GH25は、TTLをリセットする。もしGH25が、ハートビート間隔内にMR300を受信しない場合は、GH25は、TTL値を減らす。TTL値が0になると、GH25は、BN20を再選する。その後、GH25は、ブロック400のアイドル状態になる。
【0055】
上述のように、GH25は、ハートビートメッセージ200を定期的にブロードキャストする。この期間は、ハートビート間隔として知られる。GH25内のタイマは、ハートビート間隔のタイミングを追跡記録する。ハートビート間隔の時間が満了すると、ブロック530において、タイマは、ハートビートメッセージ200の生成をトリガする。ハートビートメッセージ200のブロードキャストに先立って、GH25は、BN候補リストからBN20を選択する。一実施形態では、選択基準は、GHからのホップの数である。GH25は、GHからのホップカウントの数が最大であるノード10(GN)を選択する。BN候補リストは、その場合、ホップカウント情報を含む。
【0056】
別の実施形態では、選択基準は、ノード10がLPG1のメンバになっている期間である。この実施形態では、GH25は、各ノード10について持続時間の履歴を維持している。持続時間の履歴は、ハートビートサイクルの数を単位として測られる。GH25は、BN候補リストから、最も長い関係を持つノード10をBN20として選択する。
【0057】
別の実施形態では、選択基準は、BN候補が所定の時間内に受信した外部ハートビートの数である。この実施形態では、ノード10(GN)は、外部ハートビートのシーケンス番号、及び外部ハートビートのLPG識別子を追跡する。GH25に向けてブロードキャストされるMR300は、BN候補としてのステータス、オーバヒアリングされた外部ハートビートの数、外部ハートビートに対応する識別子、及び各外部ハートビートのシーケンス番号を含む。GH25は、この情報をMR300から抽出し、BN候補リストに追加する。GH25は、同じシーケンス番号を有する外部ハートビートメッセージ200を最多数オーバヒアリングしているノード10をBN20として選択する。
【0058】
別の実施形態では、選択基準は、GH25に対するBN候補の相対移動度である。この実施形態では、ノードは、それらの平均速さを監視している。平均速さは、外部の速度測定装置又は速さ測定装置からの入力に基づいて決定することができる。速さ情報は、MR300に追加され、GH25へ発せられる。GHは、各BN候補の平均速さを自身の平均速さと比較する。平均速さの差が小さいほど、BN候補としての優先度が高くなる。
【0059】
別の実施形態では、BN候補リストから、GH25からの相対方向ごとに1つずつ、計2つのBN20が選択される。BN候補の相対方向は、例えばアップストリーム又はダウンストリームなどのノードの分類に基づいて決定される。
【0060】
(1つ又は2つ以上の)BN20が選択された後は、ハートビートメッセージ200にBN情報が付加される。ブロック540では、GH25は、ハートビートメッセージ200をブロードキャストする。ハートビートメッセージ200がブロードキャストされた後
、GH25は、BN候補リスト内の全てのBN候補について、TTL値を減少させる。TTL値は、1だけ減らされる。BN20がGH25に報告を行うたびに、すなわち、ステータスをBN20としてMR300を送信するたびに、TTLは、例えばTハートビートサイクルなどの元の状態にリフレッシュされる。
【0061】
ブロック550において、GH25は、次いで、BN候補が古いかどうかを判定する。BN候補は、TTL値がゼロに等しい場合に古いとされる。もしBN候補のTTL値がゼロであるならば、ブロック555において、そのBN候補はBN候補リストから外される。判定は、各BN候補について繰り返される。BN候補リストが更新されると、ブロック430において、GH25は、選択されたBN20が例えば自身のようにGH25であるかどうかを判定する。GH25は、ハートビートメッセージ200に含まれる選択されたBNの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック435において、GH25は、自身をLPGのBN20として宣言する。もしこれらの識別子が同じでないならば、GH25は、ブロック400のアイドル状態になる。
【0062】
図6は、BN20の選択のための有限状態マシンを示している。ノード10は、3つの異なる状態、すなわちBN候補状態600、非BN状態605、及びBN状態610になることができる。非BN状態605にあるノード10は、外部ハートビート又はエッジハートビートを受信すると、BN候補状態600に変わる。BN候補状態600にあるノードは、GH25がそれをBN20として選択すると、BN状態610に変わる。ノード10は、外部ハートビート又はエッジハートビートを受信する限り、BN候補状態600にとどまる。ノード10は、外部ハートビート又はエッジハートビートを受信しなくなると、BN候補状態600から非BN状態605に戻る。ノード10は、外部ハートビート又はエッジハートビートを受信する限り、BN状態610にとどまる。
【0063】
ノード10は、外部ハートビート又はエッジハートビートを受信しなくなると、又はTTL値が古くなる、すなわちTTL=0になると、BN状態610から非BN状態605に戻る。
【0064】
BN20は、LPG間ルーティングを促進する。ルーティング経路は、各ノード内のルーティングテーブルに基づいて決定される。ルーティングテーブルは、データを中継するための次ホップ、次LPG、及びLPG1のためのBN20に関する情報を含む。ルーティングテーブルは、ハートビートメッセージ200及びMR300に含まれる情報をもとにして作成される。また、ルーティングテーブルは、外部ハートビート及びエッジハートビートからオーバヒアリングされる情報によって更新される。
【0065】
図7は、ルーティングテーブルを作成及び更新するためにハートビートメッセージ200及びMR300を処理するための方法を示している。最初、各ノード10は、アイドルステップ700にある。ステップ702において、パケットが到着すると、ステップ704において、ノード10は、パケットがハートビートメッセージ200であるか又はMR300であるかを判定する。制御パケットのタイプに応じて、ノード10は、特別なパケット処理を実施する。もし制御パケットがハートビートメッセージ200であるならば、ノード10は、ステップ706から開始してパケットを処理する。ステップ706において、ノード10は、パケットがネイティブであるかどうかを判定する。パケットは、同じLPG1に対するものである場合に、すなわち同じGID(グループ識別子)を有する場合に、ネイティブである。ノード10は、GIDを、メモリに格納されているグループ識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノード10は、外部HB処理を開始し、ステップ800に進む。外部HB処理は、図8において詳しく説明される。もしGIDが、メモリに格納されている識別と一致するならば、ステップ708において、ノード10は、ハートビートメッセージ200が順序通りであるか
どうかを判定する。ノード10は、Seq.No.を、メモリ内のシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10は、パケットを無視する。もしSeq.No.が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ200は、順序通りであり、ステップ710において、ノード10は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ200が新しいかどうかを判定する。もしノード10が、パケットを新しくないと判定するならば、ステップ712において、送信者のルーティングエントリのみが更新される。ハートビートメッセージ200は、中継されない。もしノード10が、メッセージ又はデータパケットを新しいと判定するならば、ノード10は、ノードがGH25であるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ714において実施される。もしノード10がGH25であるならば、ステップ716において、ノード10は、送信者のルーティングエントリを更新する。ハートビートメッセージ200は中継されず、ノードはアイドル状態700になる。しかしながら、もしノード10がGNであるならば、ステップ718において、ノード10は、全てのLPG内ルーティングエントリ及びLPG間ルーティングエントリについてルーティングテーブルを更新し、ハートビートメッセージ200を中継する。LPG間ルーティング情報は、ノード10が外部LPGからのメッセージを横聞き又はBN20から直接情報を受信するときに得られる。また、LPG間ルーティング情報は、GH25からのハートビートメッセージ200に含められる。ノード10は、任意の新しい宛先、宛先への次ホップ、新しい宛先があるLPGの識別子、及びLPG1のためのBN20を、ルーティングテーブルに追加する。また、ルーティングテーブルは、宛先が義務宛先であればフラグを含む。義務外部宛先を伴うBN20又はGNは、フラグを使用し、義務宛先を外部宛先として自身のMR300に含ませる。GH25を含むアップストリームノードは、義務外部宛先を伴うBN20又はGNからのMR300を横聞きすることによって、外部宛先を学習する。義務外部宛先については後述される。GHは、LPG1内の残りのノード10に知らせるために、次のハートビートメッセージ200に外部宛先を含ませる。ルーティングテーブルに既に挙げられている宛先については、ノード10は、テーブル内の情報と異なる任意の情報を更新する。例えば、ノード10は、次ホップ、LPG、及びBN20を更新することができる。
【0066】
もし制御パケットがMR300であるならば、ノード10は、ステップ720から開始してパケットを処理する。ステップ720において、ノード10は、パケットがネイティブであるかどうかを判定する。ノードは、GIDを、メモリに格納されているグループ識別と比較する。もしGIDが、メモリに格納されている識別と一致しないならば、ノード10は、外部MR処理を開始し、ステップ800に進む。もしGIDが、メモリに格納されている識別と一致するならば、ステップ722において、ノード10は、そのMR300を送信したノード10がLPG1(同じLPG)のメンバであるかどうかを判定する。ノード10は、ノードIDを、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ステップ724において、ノード10は、MR300をただ中継する。MR300の中継によって、新しいグループノード(GN)は、完全なハートビートサイクルにわたって待つ必要なくLPG1に参加することができる。
【0067】
もしMR300を送信したノードが、参加リストに挙げられていない場合は、そのノード10は、参加ノードであるとみなされる。ルーティングテーブルに、参加ノードについてのルーティングエントリはない。一実施形態では、ノード10は、GH25に向けてMR300を転送することができる。ノード10は、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノード10は、(MR300の)発信元ノードを宛先リストに追加することができる、すなわち発信元ノードについてのルーティングエントリを確保することができる。ノード10は、中継ノードの情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ200が受信
されると、ノード10は、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。
【0068】
もし一致があるならば、ステップ726において、ノード10は、MR300が順序通りであるかどうかを判定する。ノード10は、MR Seq.No.を、メモリ内のシーケンス番号と比較する。もしMR Seq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、アイドル状態700になる。もしMR Seq.No.が、メモリに格納されている値よりも大きい又はその値と等しいならば、MR300は順序通りであり、ステップ728において、ノード10は、現シーケンス番号を伴う発信元からのMR300をノードが既に受信しているかどうかを(最後に格納されたシーケンス番号と比較することによって)チェックすることによって、MR300が新しいかどうかを判定する。もしノード10が、メッセージを新しくないと判定するならば、ステップ730において、送信者のルーティングエントリのみが更新される。MR300は中継されない。もしノード10が、メッセージを新しいと判定するならば、ノード10は、GH25であるか又はGNであるかに応じて、2つの機能のうちの1つを実施する。ノードタイプの判定は、ステップ732において実施される。もしノード10がGH25であるならば、ステップ734において、ノード10は、直接の送信者及び発信元のルーティングエントリを更新する。もしMR300が、少なくとも1つの外部宛先も運んでいるならば、ステップ734において、ノード10は、エントリを外部宛先リストに追加する。LPG1とのLPG間ルートを維持するために、収集された外部宛先リストは、次のハートビートメッセージ200に含められる。更新は、LPG内ルート及びLPG間ルートの両方を変更することを含む。もしMR300が、少なくとも1つの義務外部宛先を有するノード10からであるならば、受信ノード10は、義務外部宛先情報を使用して、LPG間ルートを更新する。義務外部宛先情報をもとにして、受信ノード10は、MR300を発信したノード10から到達することができる全ての外部宛先(ノード)を学習する。これらの外部宛先に向かう次ホップは、MR300を発信したノード10である。更新は、上述されており、再度の詳しい説明はされない。GH25は、また、任意の新しい宛先ノードをメンバシップリストに追加することによって、メンバシップリストを更新する。新しいメンバシップリストは、次のハートビートメッセージ200に含められる。MR300は中継されず、ノードはアイドル状態700になる。
【0069】
しかしながら、もしノード10がGNであるならば、ステップ736において、ノード10は、送信者及び発信元についてルーティングテーブルを更新し、MR300を中継する。例えば発信元の場合、発信元のための次ホップは、直接の送信者である。もしMR300が、外部宛先リスト、外部エントリも含むならば、外部宛先に向かう次ホップは、送信者である。発信元は、ダウンストリームノードである。更新は、LPG内ルート及びLPG間ルートの両方を変更することを含む。更新は、上述されており、再度の詳しい説明はされない。
【0070】
図8は、外部データパケット又はメッセージを処理するための方法を示している。外部データパケット又はメッセージは、異なるLPG内のノード10を発信元とするメッセージである。外部データパケットの判定は、データパケット内のLPG識別子に基づく。ステップ800において、外部LPGからデータパケットが受信される。ステップ805では、ノード10は、外部データバケットがハートビートメッセージ200であるか又はMR300であるかを判定する。制御パケットのタイプに応じて、ノード10は、特別なパケット処理を実施する。ステップ810では、ノード10は、データパケットが新しいLPGを発信元とするかどうかを判定する。このステップは、ハートビートメッセージ200及びMR300の両方に対して実施される。ノード10は、外部データパケット内のLPG識別子を、ルーティングテーブル内のLPG識別子と比較する。もし外部データパケ
ットが新しいLPG1からでないならば、ステップ815において、ノード10は、外部データパケットが順序通りに到着したかどうかを判定する。
【0071】
もし外部データパケットが新しいLPGからで、尚且つそのデータパケットがハートビートメッセージ200であるならば、プロセスは、ステップ820に進む。ステップ820では、LPG1が登録される。LPG識別子がメモリに格納され、ルーティングテーブルに追加される。タイムスタンプも記録される。一実施形態では、タイムスタンプは、ルーティングテーブルから古い情報を消去するために使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。
【0072】
また、ノード10は、LPG識別子、GH識別子、メンバリスト、及びGHへの次ホップなどの、新しいLPGに関連した情報を含む新しいデータ構造を、新しいLPG用に作成する。この情報は、ルーティングテーブルとは別に格納される。ステップ830において、ノード10は、ルーティングテーブル内のLPG間ルーティングエントリを更新する。ルーティングエントリは、ハートビートメッセージ200に含まれるメンバシップリストから抽出される。ノード10は、メンバシップリストからの各メンバを宛先として追加する。各宛先について、ルーティングテーブルは、次ホップ、BN20、及びノードがあるLPG1を含む。また、ルーティングテーブルは、義務外部宛先のためのフラグを含む。義務外部宛先は、アクティブに通信しているノード10であって、通信相手がLPG内にある又はLPG1を越えたところにあるノード10である。ノード10は、また、外部ハートビートメッセージを横聞きしたときからBN候補にもなる。一実施形態では、ルーティングテーブルから古い情報を消去するために、外部ハートビートカウンタが使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。ステップ830では、外部ハートビートカウンタは、新しい外部ハートビートが受信されるたびにリセットされる。
【0073】
もしハートビートメッセージ200が新しくないならば、ステップ815において、ノード10は、データパケットが順序通りに到着したかどうかを判定する。ノード10は、Seq.No.を、メモリに格納されているシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、外部データパケットは破棄される。もしSeq.No.が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ200は順序通りであり、ステップ825において、ノード10は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ200が新しいかどうかを判定する。もしノード10が、パケットを新しくないと判定するならば、ステップ835において、ノード10は、より良いルートが発見されたかどうかを判定する。新着のHBは、必ずしも最短経路を通って来たとは限らない。もし後のHBパケットが(たとえ新着でなくても)、より短い経路を通って来たならば、GHへの経路は、更新されるべきである。ルーティングテーブルは、外部ハートビートメッセージ200内の新しい情報に基づいて更新される。ステップ825において、もし外部データパケットが新しいと判定されるならば、プロセスは、ステップ830に進む。ステップ830は上述されており、再度の詳しい説明はされない。
【0074】
もし外部データパケットがMR300であるならば、ステップ810において、ノード10は、LPG1が新しいか否かを判定する。もしLPG1が新しいならば、プロセスは、ステップ840に進む。ステップ840において、ノード10は、送信者、発信元、及び外部GHへの次ホップ中継について、ルーティングテーブル内のLPG間ルーティングエントリを更新する。ノードは、例えば送信者、発信元、及び次ホップ中継ノードなどの3タイプのノードについて、次ホップ情報及び宛先情報を更新する。また、ノード10は、より良いルートがあるかもチェックする。より良いルートは、普通は、より短いホップ
のルートを意味する。たとえ、例えば送信者、発信元、及びGHへの次ホップ中継などの3つの外部宛先がBN20に知られている場合でも、GNは、送信者への直接経路、発信元へのより短い経路、及び次ホップ中継を有する。もしMR300が新しくないならば、ノード10は、ステップ815において、データパケットが順序通りに到着したかどうかを判定する。ノード10は、Seq.No.を、メモリ内のシーケンス番号と比較する。もしSeq.No.が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、外部データパケットは破棄される。もしSeq.No.が、メモリに格納されている値よりも大きいならば、MR300は順序通りであり、プロセスはステップ840に進む。ステップ840は上述されており、再度の詳しい説明はされない。
【0075】
ステップ830、835、及び840の各ステップの後、プロセスは、ステップ845に進む。ステップ845では、離脱ノードが検出される。検出プロセスは、後ほど詳しく説明される。
【0076】
図9〜11は、オンデマンドなルートの決定方法を示している。オンデマンドなルートは、ルート要求(R_Req)データパケット及びルート応答(R_Resp)データパケットを使用して決定され維持される。アクティブ通信のためのルートが発見され維持される。とあるソースが外部宛先すなわち異なるLPG1内の宛先への通信を開始する必要があるとき、ノード10は、ユニキャストR_ReqメッセージをネイティブBN20に送信する。ネイティブBNは、同じLPG1内のBN20である。R_Reqは、中継ノードによって中継される。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノード10である。具体的なルートは、ルーティングテーブル内の次ホップ情報によって決定される。R_Respは、宛先ノード又は宛先ノードに対してネイティブなBN20のいずれかによって開始されるメッセージである。R_Reqは、宛先ノードが見つかるまで又は最大ホップカウントに達するまで中継される。最大ホップカウントは、R_Reqが誤った方向に無限に中継されるのを阻止する。R_Reqが中継されるたびに、ホップカウントは1だけ増分される。R_Reqは、中継ノードによってのみ中継され、フラッディングしない。
【0077】
もしBN20がR_Respを発行できないならば、BN20は、R_Reqを隣接するBNに向けて中継する。BN20は、最大ホップカウントに達するまで又はBN20がR_Respを発行できるまで、R_Reqを他のBN20に転送する。BN20がR_Respを発行するとき、そのR_Respは、隣接するLPGに宛先があることを示す。
【0078】
R_Reqは、R_Reqのタイプ、最大ホップカウント、前LPG識別子、宛先、宛先シーケンス番号、ソース識別子、及びソースシーケンス番号を含む。R_Reqのタイプは、通常や応答済みなどであってよい。R_Reqのタイプは、R_Reqが宛先に達する前に応答されたかどうかを識別するために使用され、もしR_Reqが宛先ノードに達する前に既に応答されているならば、宛先ノードは、R_Respを発行する必要はない。上述のように、最大ホップカウントは、ルーティング検索を制限するために使用される。前LPG識別子は、すぐ隣りのLPG1の識別子であり、もしR_Reqが別のLPGから来たものならば、そのLPG1は、R_Reqが直前に中継されていたところである。前LPG識別子は、ソースノードが属しているLPG1における現LPG識別子に等しい。宛先IDは、宛先ノードの識別子である。ソースIDは、ソースノードの識別子である。ソースシーケンス番号は、各R_Reqデータパケット及びR_Reqの順番を一意に識別するために使用される。別の実施形態では、R_Reqは、更に、ターゲットBN識別子、ターゲットBNに向かう次ホップ識別子、及び前ホップを含む。ターゲットBN識別子は、ノード10が同じLPG1内のBN20を区別することを可能にする。LPG1内に2つ以上のBN20がある場合、ノード10は、どの方向にR_Reqを中継す
るかを知ることができる。ターゲットBNに向かう次ホップ識別子は、中継ノードがR_ReqをターゲットBNに向けて中継するために使用される。次ホップのみが、R_Reqを中継する。逆経路の場合、ノード10は、前ホップを使用する。R_Respは、中間ノードのルーティングテーブルに基づいて中継されてソースに戻される。ソースは、R_Reqが転送されるときにルーティングテーブルに挿入され、ルーティングエントリは、義務外部宛先としてソースノードを有するノードによって、各LPG内において維持される。前ホップを含ませることによる利点は、R_Respが複数のLPGを通って移動する場合、中間LPG1がルーティングテーブル内にソースノードを有さないかもしれないことにある。中間LPGは、ソースLPGと宛先LPGとの間にあるLPGである。ソースLPG、中間LPG、宛先LPGを含むノードは、全て、ソース及び宛先のルーティング情報を有する。前ホップは、R_Reqから抽出され、後の使用に備えてメモリに格納される。
【0079】
R_Respは、ホップカウント、次LPG識別子、宛先識別子、宛先シーケンス番号、ソース識別子、ソースシーケンス番号、及び次ホップ中継を含む。ホップカウントは、宛先ノードがソースノードから離れているホップ数である。次LPG識別子は、R_Respがこれから中継される次のLPGの識別子である。
【0080】
図9に示されるように、ノード10は、ステップ400においてアイドル状態にある。ステップ900において、R_Req又はR_Respが到着する。ステップ905では、ノード10は、受信されたデータパケットがR_Reqであるか又はR_Respであるかを判定する。この判定は、到着データパケットのフォーマット及びそれに含まれる情報に基づく。
【0081】
もし到着データパケットがR_Reqであるならば、プロセスは、ステップ910に進む。ステップ910では、ノード10は、R_Reqが新しい要求であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわちソースシーケンス番号に基づく。R_Reqパケットが受信されるたびに、パケットからソースシーケンス番号が抽出され、メモリに格納される。新しいR_Reqパケットが到着すると、最後に格納されたソースシーケンス番号が、到着R_Reqパケットのソースシーケンス番号と比較される。もしソースシーケンス番号が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、パケットは破棄される。もしソースシーケンス番号が、メモリに格納されている値よりも大きいならば、R_Reqは新しく、ステップ915において、ノード10は、R_Reqに対する応答が既に発行されているかどうかを判定する。判定は、R_Reqに含まれるR_Reqタイプの指標に基づく。もしR_Reqタイプが、R_Reqに対する応答が既に発行されたことを示すならば、ステップ930において、ノード10は、R_Reqを宛先へ中継する。R_Reqが応答されていないときは、ステップ920において、ノード10は、それが宛先のLPG内のBN20であるか又は宛先であるかを判定する。
【0082】
もしノード10が、宛先のLPG内のBN20又は宛先のいずれかであるならば、ステップ925において、ノード10は、R_Respを発行し、R_Reqのタイプを「応答済み」に変更する。その後、ノードは、ステップ930において、R_Req中継機能を実施する。R_Req中継機能は、後述される。R_Req中継機能が実施された後、ステップ935において、ノード10は、R_Reqのソースのためのルーティングを更新する、すなわちソースの次ホップを、R_Reqが来たところにする。
【0083】
もしR_Reqのタイプが、R_Reqに対する応答が発行されていないことを示すならば、ステップ920において、ノード10は、自身が応答を発行できるかどうかを判定する。R_Reqを発行できるのは、宛先ノード又はBN20のみである。ノード10は
、R_Reqから宛先識別子を抽出し、それを自身の識別子と比較する。もし識別子が一致するならば、ノード10は宛先ノードである。もし識別子が一致しないならば、ノード10は宛先ノードではない。また、宛先識別子を使用して、ノード10は、宛先ノード用のBN20について、ルーティングテーブル内を調べる。ノード10は、BN20の識別子を自身の識別子と比較する。もし識別子が一致するならば、ノード10は、宛先ノード用のBN20である。もし識別子が一致しないならば、ノード10は、宛先ノード用のBN20ではない、すなわち宛先ノードがあるLPG1内のBNではない。
【0084】
もしノード10が、宛先ノード、又は宛先ノードのLPG1内のBN20のいずれかであるならば、ステップ925において、BN20又はノード10は、R_Respを発行する。また、ノード10は、R_Reqのタイプを応答済みに変更し、ステップ930において、R_Reqは宛先へ中継される。
【0085】
(ステップ920において、)もしノード10が、宛先ノード、又は宛先ノードのLPG1内のBN20のいずれでもないならば、ステップ930において、ノード10は、R_ReqをBN20又は宛先ノードに向けて中継する。ソースノードは、BN20にとっての義務外部宛先になり、BN20は、ソースノードにとっての入口BNである。R_Req中継機能は、図10に記載されており、後ほど詳しく説明される。
【0086】
ステップ935において、ノード10は、ルーティングテーブル内の、ソースノードについてのルーティング情報を、R_Reqからの情報によって更新する。例えば、ノード10は、ソースノード識別子、ソースノードについてのLPG情報、及びソースノードについてのホップカウントを追加することができる。
【0087】
もし到着データパケットがR_Respであるならば、プロセスは、ステップ940に進む。ステップ940において、ノード10は、R_Respが新しい応答であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわち宛先シーケンス番号に基づく。データパケットが受信されるたびに、パケットから宛先シーケンス番号が抽出され、メモリに格納される。新しいデータパケットが到着すると、最後に格納された宛先シーケンス番号が、到着データパケットの宛先シーケンス番号と比較される。もし宛先シーケンス番号が、メモリに格納されている値よりも小さいならば、ノード10はパケットを無視し、パケットは破棄される。もし宛先シーケンス番号が、メモリに格納されている値よりも大きいならば、R_Respは新しく、ステップ945において、R_Respは、ソースノードに向けて中継される。
【0088】
R_Resp中継機能は、図11に記載されており、後ほど詳しく説明される。
【0089】
ステップ950において、ノード10は、ルーティングテーブル内の、宛先ノードについてのルーティング情報を、R_Respからの情報によって更新する。例えば、ノード10は、宛先ノード識別子、宛先ノードについてのLPG情報、及び宛先ノードについてのホップカウントを追加することができる。
【0090】
図10は、R_Reqのための中継プロセスを説明している。プロセスは、ステップ1000から開始する。ステップ1005において、ノード10は、宛先ノードが同じLPG1内であるか、すなわちローカルな宛先であるかどうかを判定する。ノード10は、ルーティングテーブルを調べ、宛先ノードがLPG内宛先であるかどうかをチェックする。もし宛先ノードがLPG内ルーティングエントリとして挙げられているならば、宛先は、同じLPG内である。もし宛先がローカルである、すなわちLPG内であるならば、ノード10は、R_Reqが宛先ノードに到達したか、すなわち宛先ノードの識別子が現ノードの識別子と同じであるかどうかを判定する。宛先ノードは、自身に宛てられたR_Re
qを受信すると、R_Reqの転送を終了させる。
【0091】
ステップ1010、1015、1030、及び1035は、ローカルな宛先及び非ローカルな宛先のどちらの場合も実施される。ステップ1010では、ノード10は、自身がソースにとっての入口(ingress)BNであるかどうかを判定する。入口BNは、LPG1内のノード10のなかで別のLPG1内のノード10からのR_Reqを最初に受信するBN20、又は義務外部宛先リスト内にR_Reqのソースを既に有しているBN20である。義務外部宛先は、そのLPGの外側のノードについての特別なルーティングエントリである。とあるノードが義務外部宛先を有しているときは、そのノードを通じて外部宛先に到達可能であることを知らせるために、それらの義務外部宛先のノードIDがノードのMR(メンバレポート)の一部として含まれる。中継ノードは、「k」回の前制御メッセージサイクル内においてダウンストリームノードの少なくとも1つのMR300をアップストリームノードへ中継するノードである。
【0092】
もしノード10がソースの入口BNであるならば、ステップ1015において、ノード10は、ソースノードについてのエントリによって、ルーティングテーブルを更新する。ソースノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード(入口BN)は、自身のLPG1にルーティング情報を知らせる又は公示する役割を担う。
【0093】
ノード10がルーティングテーブルを更新した後、ステップ1035において、ノード10(入口BN)は、R_Reqをブロードキャストする。ブロードキャストに先立ち、ステップ1032において、ノード10は、ホップカウントを1だけ増分させる。また、ステップ1034において、ノード10は、R_Reqの最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、R_Reqに含まれる。ノード10は、最大ホップカウントを、例えば受信されたR_Reqのホップカウント+1などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、R_Reqは転送されず、ステップ1040において、ノード10は停止する。
【0094】
もし宛先ノードがローカルであり、ノード10が入口BNではないならば、ステップ1030において、ノード10は、自身が中継ノードであるかどうかを判定する。次ホップ中継は、ルーティングテーブル内の情報に基づく。もしノード10が中継ノードであるならば、ステップ1035において、R_Reqはブロードキャストされる。プロセスは、次いで、ステップ1040において終了する。ブロードキャストに先立ち、ステップ1032において、中継ノードは、ホップカウントを1だけ増分させる。また、ステップ1034において、中継ノードは、R_Reqについての最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、R_Reqに含まれる。中継ノードは、最大ホップカウントを、例えば受信されたR_Reqのホップカウント+1などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、R_Reqは転送されず、ステップ1040において、中継ノードは停止する。
【0095】
もし宛先ノードが非ローカルな宛先であり、ノード10が入口BNではないならば、ノード10は、自身が出口(egress)BNであるかどうかを判定する。出口BNは、自身のLPG内のノード10からR_Reqを受信するBN、又は(義務宛先ではないが)その外部宛先としてR_Reqのソースを既に有しているBNである。出口BN機能は、隣接するLPGがR_Reqを受信できるように、R_Reqを隣接するLPGへブロードキャストすることである。もしノード10が出口BNであるならば、ステップ1025において、ノード10は、前LPG識別子を自身のLPG識別子で置き換え、ステップ1035において、R_Reqをブロードキャストする。ホップカウントが最大ホップカウントに達すると、R_Reqは、これ以上は再ブロードキャストされない。
【0096】
もし宛先ノードが非ローカルであり、ノード10が入口BNでも出口BNでもないならば、ステップ1030において、ノード10は、自身が中継ノードであるかどうかを判定する。
【0097】
次ホップ中継は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノード10である。もしノード10が中継ノードでないならば、R_Reqは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1035において、R_Reqはブロードキャストされる。プロセスは、次いで、ステップ1040において終了する。
【0098】
図11は、R_Respのための中継プロセスを説明している。プロセスは、ステップ1100から開始する。ステップ1105において、ノード10は、ソースノードが同じLPG1内であるか、すなわちローカルなソースであるかどうかを判定する。ノード10は、ルーティングテーブル内を調べ、ソースノードのLPG1のLPG識別子を読み出す。ソースノードのLPG識別子は、ノード10のLPG識別子と比較される。もし識別子が一致するならば、ソースノードは同じLPG1内である。中継プロセスは、非ローカルな宛先の場合に2つ余分にステップがあることを除き、ローカルな宛先及び非ローカルな宛先のどちらの場合も同様である。
【0099】
ステップ1110、1115、1130、及び1135は、ローカルなソース及び非ローカルなソースのどちらの場合も実施される。ステップ1110では、ノード10は、別のLPG内のノードからR_Respを受信するときに、自身が宛先にとっての入口BNであるかどうかを判定する。入口BNは、別のLPG1内のノード10からR_Respを受信するBNである。
【0100】
もしノード10が入口BNであるならば、ステップ1115において、ノード10は、宛先ノードについてのエントリによって、ルーティングテーブルを更新(inserts updates)する。宛先ノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード(入口BN)は、自身のLPG1にルーティング情報を知らせる又は公示する役割を担う。
【0101】
ノード10がルーティングテーブルを更新した後、ステップ1135において、ノード10(入口BN)は、R_Respをブロードキャストする。一実施形態では、R_Respは、R_Reqと同じ経路を通って中継される。
【0102】
もしソースノードがローカルであり、ノード10が入口BNではないならば、ステップ1130において、ノード10は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノードである。もしノード10が中継ノードでないならば、R_Respは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1135において、R_Respはブロードキャストされる。プロセスは、次いで、ステップ1140において終了する。
【0103】
もしソースノードが非ローカルなソースであり、ノード10が入口BNではないならば、ステップ1120において、ノード10は、自身が出口BNであるかどうかを判定する。出口BN機能は、隣接するLPGがR_Respを受信できるように、R_Respを隣接するLPGへブロードキャストすることである。もしノード10が出口BNであるならば、ステップ1125において、ノード10は、次LPG識別子を自身のLPG識別子で置き換え、ステップ1135において、R_Respをブロードキャストする。
【0104】
もしソースノードが非ローカルであり、ノード10が入口BNでも出口BNでもないならば、ステップ1130において、ノード10は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってMR300を中継される少なくとも1つのダウンストリームノードを有するノードである。もしノード10が中継ノードでないならば、R_Respは中継されない、すなわち転送されない。もしノード10が中継ノードであるならば、ステップ1135において、R_Respはブロードキャストされる。プロセスは、次いで、ステップ1140において終了する。
【0105】
ひとたびソースノードがR_Respを受信すると、ソースノードは、宛先ノードに対するメッセージやデータの伝送、又は通信を開始させる。
【0106】
上述のように、BN20は、アクティブな通信経路を維持する及び他のノードに移動ノード又は離脱ノードについて知らせる役割を担う。図12は、離脱ノードを検出するプロセスを示している。プロセスは、ステップ400においてBN20がアイドル状態にあるところから開始する。ステップ1200において、離脱ノードが検出される。離脱ノードは、2つの方法のうちの1つを使用して検出される。離脱ノードは、外部ハートビートメッセージ200のオーバヒアリングによって検出することができる。詳細には、離脱ノードは、外部ハートビートメッセージ200に含まれるメンバシップリストに自身の識別子を含まれている。BN20は、自身のLPG1内にあったノードが外部メンバシップリストに挙げられたときに、そのノードがLPGを離脱したと判定する。或いは、離脱ノードは、その離脱ノードが外部LPG1の識別子を伴うMR300をブロードキャストしたときに検出することができる。BN20は、これまで同じLPG内にあったノードからMR300をオーバヒアリングする。BN20は、自身のLPG識別子を、MR300内の識別子と比較する。もし識別子が異なるならば、ノード10は離脱している。1つのノード10は、1つのLPG1のメンバであることしかできない。
【0107】
ステップ1205において、BN20は、自身のルーティングテーブルを離脱ノードについて更新する。具体的には、BN20は、離脱ノードのLPGを変更する。ルーティングテーブルが更新されたら、BNは、ステップ400のアイドル状態に戻る。BNは、次いで、離脱ノードに関連した情報を公示する。
【0108】
別の実施形態では、(BN20だけでなく)任意のノードが、外部ハートヒート又は外部MR300をオーバヒアリングすることによって離脱ノードを検出することができる。
【0109】
BN情報は、ルーティングテーブルから取り出される。もしノード10がBN20であるならば、BN20は、次のMR300に離脱ノード通知を含ませる。通知は、ノードがLPG1から離れたことの肯定声明である。通知は、離脱ノードの識別子と、新しいLPGの識別子とを含む。ステップ1325において、BN20は、次いで、その離脱ノードについてアクティブな通信が継続中であるかどうかを判定する。通信は、もし離脱ノードが通信の宛先又はソースのいずれかであるならば継続中である。もしアクティブな通信が継続中でないならば、BN20は、アイドル状態(ステップ400)に戻る。しかしながら、もしアクティブな通信が継続中であるならば、BN20は、ルートを維持しなければならない。ルートは、ステップ1330において、義務外部宛先のリストに離脱ノードを追加してルーティングテーブルを更新することによって維持される。このリストは、次のMR300に含められてブロードキャストされ、後に、ハートビートメッセージ200に含められる。BN20は、次いで、アイドル状態(ステップ400)に戻る。
【0110】
もしステップ1305において、ノード10がBN20ではないならば、ノード10は
、BN20が離脱ノード通知を既に送信したかどうかを判定する。ステップ1310において、ノード10は、BN20から受信された最新のMR300を離脱ノード通知についてチェックする。もしMR300が離脱ノード通知を含んでいたならば、ノード10は、アイドル状態に戻る。ノード10は、離脱ノード通知に含まれる情報によって、ルーティングテーブルを更新する。
【0111】
もしBN20からのMR300が離脱ノード通知を含んでいなかったならば、ノード10は、別のノードが既に離脱ノート通知を送信したかどうかを判定する。ステップ1315において、ノード10は、任意のノードから受信された最新のMR300を離脱ノード通信についてチェックする。もしMR300が離脱ノード通知を含んでいたならば、ノード10は、アイドル状態に戻る。
【0112】
もしどのノード10からも離脱ノード通知が受信されなかったならば、プロセスは、ステップ1320に進み、ここで、ノード10は、自身のMR300に離脱ノード通知を挿入する。ノード10は、次いで、(あたかも自身がBN20であるかのように)ステップ1325及び1330を実施する。
【0113】
図14は、義務外部宛先を他のノードに公示又は通知するプロセスを示している。義務外部宛先リストの公示は、ハートビートメッセージ200及びMR300を使用して達成される。義務外部宛先リストは、ハートビートメッセージ200及びMR300に追加される。
【0114】
図14に示されるように、ノード10は、ステップ400のアイドル状態から開始する。ハートビートメッセージ200及びMR300は、定期的にブロードキャストされる。期間は、ハートビートサイクル又はMRサイクルである。一連のハートビートメッセージ200又はMR300の間の期間は、タイマ又は計時手段によってカウントされる。ハートビートメッセージ200及びMR300は、サイクル期間の満了によってトリガされる。ステップ1400において、ハートビートメッセージ200又はMR300のいずれかが、タイマの1つの満了によってトリガされる。ステップ1405において、ノード10は、自身が通常ノード(GN)であるか又はGH25であるかを判定する。もしノード10がGH25であるならば、ステップ1410において、義務外部宛先リストは、LPG1の外部宛先としてハートビートメッセージ200に追加される又は符号化される。ステップ1415において、ハートビートメッセージ200はブロードキャストされる。GH25は、その後、アイドル状態(ステップ400)に戻る。
【0115】
もしノード10がGNであるならば、ステップ1420において、義務外部宛先リストは、MR300に追加される又は符号化される。ステップ1425において、MR200はブロードキャストされる。GNは、その後、アイドル状態(ステップ400)に戻る。
【0116】
ステップ1430において、GH25は、MR300を受信する。ステップ1435において、GHは、義務外部宛先リストをMR300から抽出し、後のブロードキャストに備えて格納する。格納された義務宛先リストは、次のハートビートメッセージに含められる。その後、GH25は、アイドル状態(ステップ400)に戻る。
【0117】
本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。
【特許請求の範囲】
【請求項1】
各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
ソースノードからルート要求メッセージを伝送するステップであって、前記ルート要求メッセージは、宛先ノードの識別子、ソースノードの識別子、及び前LPG識別子を少なくとも含む、ステップと、
前記ルート要求メッセージをネイティブ境界ノードへ中継するステップと、
前記ルート要求メッセージを外部境界ノードへ転送するステップと、
前記宛先ノードの識別子に対応する宛先ノードが前記外部境界ノードのLPG内であるかどうかを判定するステップと、
前記宛先ノードが前記LPG内でないならば、前記ルート要求メッセージを別の境界ノードへ中継するステップと、
前記宛先ノードが前記LPG内であるならば、前記ルート要求メッセージを前記宛先ノードへ中継するステップと、
前記宛先ノードにおいて前記ルート要求メッセージを受信するステップと、
前記宛先ノードによって前記ソースノードへルーティング応答を伝送するステップと、
前記ルート要求メッセージによって発見された第1の経路を通じて前記ルーティング応答を前記ソースノードへ中継するステップと、
前記ソースノードにおいて前記ルーティング応答を受信するステップと、
前記ルーティング応答の受信を受けて前記データを伝送するステップであって、前記データは、前記ルーティング応答によって発見された第2の経路を使用して中継される、ステップと、
を備える方法。
【請求項2】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信するノードが前記宛先ノード又は前記宛先ノードのLPG内の境界ノードであるかどうかを判定するステップを備える方法。
【請求項3】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記宛先ノードが前記ルート要求メッセージを受信しているノードと同じLPG内であるかどうかを判定するステップと、
前記ルート要求メッセージを受信しているノードが入口(ingress)境界ノードであるかどうかを判定するステップと、
前記ソースノードの識別子によって宛先リストを更新するステップと、
を備える方法。
【請求項4】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
【請求項5】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信しているノードが出口(egress)境界ノードであるかどうかを判定するステップと、
前記ルート要求メッセージ内の前記前LPG識別子を前記出口境界ノードのLPGのLPG識別子で置き換えるステップと、
を備える方法。
【請求項6】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ソースノードが前記ルーティング応答を受信しているノードと同じLPG内であるかどうかを判定するステップと、
前記ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、
前記宛先ノードの識別子によって宛先リストを更新するステップと、
を備える方法。
【請求項7】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
【請求項8】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、
前記ルーティング応答内の次LPG識別子を前記出口境界ノードのLPGのLPG識別子で置き換えるステップと、
を備える方法。
【請求項9】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記宛先ノードによって前記データが受信されるまでソースノードから宛先ノードへのルートを維持するステップを備える方法。
【請求項10】
請求項9に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
ルートを維持する前記ステップは、
ノードがLPGを変更したかどうかを検出するサブステップと、
ノードがLPGを変更したという通知をLPG内の全てのノードへ伝送するサブステップと、
変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、
前記ノードが境界ノードであると判定されたならば、LPGを変更した前記ノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップと、
を含む、方法。
【請求項11】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ソースノードによって前記ルーティング応答が受信されるまで前記第1の経路を維持するステップと、
前記宛先ノードによって前記データが受信されるまで前記第2の経路を維持するステップと、
を備える方法。
【請求項12】
複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
既定のノードを発信元とする第1の制御パケットを受信するステップであって、前記既定のノードはグループヘッダである、ステップと、
前記第1の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、
前記第1の制御パケットが外部ローカルピアグループを発信元とするならば、パケットを前記グループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、
少なくとも1つの候補からの前記伝送パケットを前記グループヘッダにおいて受信するステップと、
前記受信された伝送パケットに基づいて候補のリストを作成するステップと、
前記候補のリストから1つの候補を前記境界ノードとして選択するステップと、
前記選択された境界ノードの識別子を含むデータパケットを伝送するステップと、
を備える方法。
【請求項13】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記候補のリストは、プリセット期間にわたって有効であり、前記期間は、Time−to−Live値である、方法。
【請求項14】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記Time−to−Live値は、前記第1の制御パケットの伝送期間の倍数である、方法。
【請求項15】
請求項13に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記プリセット期間が満了したかどうかを判定するステップと、
前記プリセット期間が満了したならば候補を削除するステップと、
を備える方法。
【請求項16】
請求項13に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
同じ候補の識別子を含むデータパケットを前記グループヘッダが受信したときにTime−to−Live値をリフレッシュするステップを備える方法。
【請求項17】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記選択された境界ノードの識別子を含む前記データパケットを受信するステップと、
前記選択された境界ノードの前記識別子を受信ノードの識別子と比較するステップと、
前記比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、
を備える方法。
【請求項18】
請求項17に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
ステータスを境界ノードに変更した後に定期的に第2の制御パケットを伝送するステップを備える方法。
【請求項19】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記境界ノードは、各候補についての、前記グループヘッダからのホップカウントに基
づいて選択される、方法。
【請求項20】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記グループヘッダから前記境界ノードと反対の相対方向にある第2の境界ノードを選択するステップを備える方法。
【請求項1】
各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
ソースノードからルート要求メッセージを伝送するステップであって、前記ルート要求メッセージは、宛先ノードの識別子、ソースノードの識別子、及び前LPG識別子を少なくとも含む、ステップと、
前記ルート要求メッセージをネイティブ境界ノードへ中継するステップと、
前記ルート要求メッセージを外部境界ノードへ転送するステップと、
前記宛先ノードの識別子に対応する宛先ノードが前記外部境界ノードのLPG内であるかどうかを判定するステップと、
前記宛先ノードが前記LPG内でないならば、前記ルート要求メッセージを別の境界ノードへ中継するステップと、
前記宛先ノードが前記LPG内であるならば、前記ルート要求メッセージを前記宛先ノードへ中継するステップと、
前記宛先ノードにおいて前記ルート要求メッセージを受信するステップと、
前記宛先ノードによって前記ソースノードへルーティング応答を伝送するステップと、
前記ルート要求メッセージによって発見された第1の経路を通じて前記ルーティング応答を前記ソースノードへ中継するステップと、
前記ソースノードにおいて前記ルーティング応答を受信するステップと、
前記ルーティング応答の受信を受けて前記データを伝送するステップであって、前記データは、前記ルーティング応答によって発見された第2の経路を使用して中継される、ステップと、
を備える方法。
【請求項2】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信するノードが前記宛先ノード又は前記宛先ノードのLPG内の境界ノードであるかどうかを判定するステップを備える方法。
【請求項3】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記宛先ノードが前記ルート要求メッセージを受信しているノードと同じLPG内であるかどうかを判定するステップと、
前記ルート要求メッセージを受信しているノードが入口(ingress)境界ノードであるかどうかを判定するステップと、
前記ソースノードの識別子によって宛先リストを更新するステップと、
を備える方法。
【請求項4】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
【請求項5】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルート要求メッセージを受信しているノードが出口(egress)境界ノードであるかどうかを判定するステップと、
前記ルート要求メッセージ内の前記前LPG識別子を前記出口境界ノードのLPGのLPG識別子で置き換えるステップと、
を備える方法。
【請求項6】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ソースノードが前記ルーティング応答を受信しているノードと同じLPG内であるかどうかを判定するステップと、
前記ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、
前記宛先ノードの識別子によって宛先リストを更新するステップと、
を備える方法。
【請求項7】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
【請求項8】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、
前記ルーティング応答内の次LPG識別子を前記出口境界ノードのLPGのLPG識別子で置き換えるステップと、
を備える方法。
【請求項9】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記宛先ノードによって前記データが受信されるまでソースノードから宛先ノードへのルートを維持するステップを備える方法。
【請求項10】
請求項9に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
ルートを維持する前記ステップは、
ノードがLPGを変更したかどうかを検出するサブステップと、
ノードがLPGを変更したという通知をLPG内の全てのノードへ伝送するサブステップと、
変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、
前記ノードが境界ノードであると判定されたならば、LPGを変更した前記ノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップと、
を含む、方法。
【請求項11】
請求項1に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
前記ソースノードによって前記ルーティング応答が受信されるまで前記第1の経路を維持するステップと、
前記宛先ノードによって前記データが受信されるまで前記第2の経路を維持するステップと、
を備える方法。
【請求項12】
複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
既定のノードを発信元とする第1の制御パケットを受信するステップであって、前記既定のノードはグループヘッダである、ステップと、
前記第1の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、
前記第1の制御パケットが外部ローカルピアグループを発信元とするならば、パケットを前記グループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、
少なくとも1つの候補からの前記伝送パケットを前記グループヘッダにおいて受信するステップと、
前記受信された伝送パケットに基づいて候補のリストを作成するステップと、
前記候補のリストから1つの候補を前記境界ノードとして選択するステップと、
前記選択された境界ノードの識別子を含むデータパケットを伝送するステップと、
を備える方法。
【請求項13】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記候補のリストは、プリセット期間にわたって有効であり、前記期間は、Time−to−Live値である、方法。
【請求項14】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記Time−to−Live値は、前記第1の制御パケットの伝送期間の倍数である、方法。
【請求項15】
請求項13に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記プリセット期間が満了したかどうかを判定するステップと、
前記プリセット期間が満了したならば候補を削除するステップと、
を備える方法。
【請求項16】
請求項13に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
同じ候補の識別子を含むデータパケットを前記グループヘッダが受信したときにTime−to−Live値をリフレッシュするステップを備える方法。
【請求項17】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記選択された境界ノードの識別子を含む前記データパケットを受信するステップと、
前記選択された境界ノードの前記識別子を受信ノードの識別子と比較するステップと、
前記比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、
を備える方法。
【請求項18】
請求項17に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
ステータスを境界ノードに変更した後に定期的に第2の制御パケットを伝送するステップを備える方法。
【請求項19】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
前記境界ノードは、各候補についての、前記グループヘッダからのホップカウントに基
づいて選択される、方法。
【請求項20】
請求項12に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
前記グループヘッダから前記境界ノードと反対の相対方向にある第2の境界ノードを選択するステップを備える方法。
【図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】
【公表番号】特表2011−523269(P2011−523269A)
【公表日】平成23年8月4日(2011.8.4)
【国際特許分類】
【出願番号】特願2011−509581(P2011−509581)
【出願日】平成21年5月11日(2009.5.11)
【国際出願番号】PCT/US2009/043403
【国際公開番号】WO2009/140179
【国際公開日】平成21年11月19日(2009.11.19)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
【公表日】平成23年8月4日(2011.8.4)
【国際特許分類】
【出願日】平成21年5月11日(2009.5.11)
【国際出願番号】PCT/US2009/043403
【国際公開番号】WO2009/140179
【国際公開日】平成21年11月19日(2009.11.19)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
[ Back to top ]