JP4294689B2 - 通信システム内の経路探索用の方法及び装置 - Google Patents

Description

本発明は通信システムに関する。より詳細には、本発明は通信システム内の経路探索用の方法及び装置に関する。

通信システム内の経路探索についてはよく知られている。特に、メッセージ・フラッディング（ｆｌｏｏｄｉｎｇ）手続は、オンデマンドによる経路探索及びネットワーク初期化の基準であることが多い。基本的には、メッセージ・フラッディングは全ネットワークを覆うブロードキャスト手続として規定され、次のように動作する。ネットワークの一のノード、即ち、リモートユニットは、ネットワークの別のノードへの経路を探索しようとするとき、宛先アドレスを指定して、自身の近隣の全てにメッセージをブロードキャストする。メッセージを受信すると、近隣のノードの全ては、自身の近隣にそのメッセージを再びブロードキャストする。ノードは同じメッセージを再び受信すると、そのメッセージを破棄する。この手続が、ネットワークのノードの全てが到達されるまで、又はメッセージの生存時間が経過するまで繰り返される。既述のように、経路選択アルゴリズムにおいてネットワークをフラッディングする目的は、本質的には、データを宛先へ送信するパスを検出することである。通常、メッセージの内容は経路探索のリクエストである。

メッセージ・フラッディングはネットワーク内で経路を検出するための信頼できる手法であるが、フラッディングにより過度の量のシステムのトラフィック及び干渉が生じることが分かっている。特に、検索された領域の各ホストが経路探索パケットを再びブロードキャストする必要があることから、シグナリングメッセージは指数関数的に増大し、深刻な冗長、競合及び衝突が生じる。したがって、メッセージ・フラッディングにより生じるシステム干渉を最小とする、通信システム内の経路探索用の方法及び装置が必要である。

通信システム内の経路探索の必要に対処するため、本明細書にてフラッディング用の方法及び装置を提供する。アドホック通信ネットワークにおける経路探索中、オーバーレイトランシーバは発信元ノードと宛先ノードとの間に存在する複数の「シード（ｓｅｅｄ）」ノードを判定する。シードノードには、発信元ノードと宛先ノードとの間の経路を探索するという要求が通知される。要求が通知されると、シードノードは即座に経路探索メッセージをブロードキャストする。アンダーレイ通信システム内のいずれかのノードが、同一の経路識別子を有する経路探索メッセージを受信した場合、オーバーレイトランシーバには２つのシード間の経路情報が与えられ、オーバーレイ通信システムにはシード間の「パス」が与えられる。オーバーレイトランシーバは、全シード間の経路情報を受信すると、送信元デバイスと宛先デバイスとの間の適切な経路を判定し、その経路情報を送信元デバイス及び宛先デバイスにブロードキャストする。メッセージ・フラッディングはアンダーレイ通信システム１１０内の全シードから同時に生じるため、非常に減少される。

本発明にはオーバーレイ通信システムの動作方法が含まれる。この方法は、アンダーレイ通信システム内の第１のノードと第２のノードとの間に経路が必要であることをオーバーレイ通信システムに通知する経路必要メッセージをアンダーレイ通信システムの第１のノードから受信する工程を含む。アンダーレイ通信システム内のシードノードの位置を判定するとともに、メッセージをシードノードに発信することによりシードノードに経路探索メッセージのブロードキャストを開始させる。次に、アンダーレイ通信システム内のノ
ードから複数の区間経路を受信し、区間経路に基づき経路を判定する。最後に、経路をアンダーレイ通信システム内の第１のノードに発信する。

これに加えて、本発明にはアドホック通信システム内のノードの動作方法が含まれる。この方法は、第１の経路探索メッセージを受信する工程と、第１の経路探索メッセージにより第１の経路探索メッセージの発信された第１のシードノードの識別子を判定する工程と、第１の経路探索メッセージにより第１の経路識別子を判定する工程と、以前に受信した経路探索メッセージは同様の経路識別子を含む異なるシードノードから受信されたか否かを判定する工程とを含む。以前に受信した経路探索メッセージは同様の経路識別子を含む異なるシードノードから受信されたとの判定に基づき、２つの経路探索メッセージから取得された経路情報をオーバーレイ通信システムに発信する。

これに加えて、本発明にはオーバーレイ通信システム内に存在する装置が含まれる。この装置は、アンダーレイ通信システム内の複数のノードから複数の区間経路を受信する受信器と、複数の区間経路によりアンダーレイ通信システム内の第１のノードと第２のノードとの間の経路を判定する論理回路と、アンダーレイ通信システム内の第１のノードに経路を発信する発信器とからなる。

これに加えて、本発明にはアンダーレイ通信システム内に存在する装置が含まれる。この装置は、第１のノード及び第２のノードから第１の経路探索メッセージ及び第２の経路探索メッセージを受信する受信器と、第１の経路探索メッセージ及び第２の経路探索メッセージにより第１の経路識別子及び第２の経路識別子を判定するとともに、第１の経路識別子及び第２の経路識別子が同様であるか否かを判定する論理回路と、第１の経路識別子と第２の経路識別子とが異なるとき、第１の経路探索メッセージ及び第２の経路探索メッセージから取得された経路情報を発信する発信回路とからなる。

ここで図面を参照する。図面において類似の参照符号は類似の構成要素を示す。図１には、通信システム１００のブロック図を示す。通信システム１００は、アドホック・アンダーレイ通信システム１１０を含む。好適には、アンダーレイ通信システム１１０は、Ｍｏｔｏｒｏｌａ（登録商標）社（ｗｗｗ．ｍｏｔｏｒｏｌａ．ｃｏｍ）により市販されるｎｅｕＲＦｏｎ（商標）通信システムであり、以下に述べる機能を実行するように修正されている。しかしながら、本発明の代替の実施形態では、アンダーレイ通信システム１１０には、以下に限定されるものではないが、通常はＩＥＥＥ８０２．１１ｂアドホックネットワーキングプロトコルを利用するＷＬＡＮネットワーク、又は、Ｎｏｋｉａ（登録商標）社により製造されたＲｏｏｆＴｏｐ（商標）ワイヤレスルーティングメッシュネットワークなど、任意のアドホックネットワークが含まれる。これに加えて、通信システム１００は、セルラー符号分割多重接続（ＣＤＭＡ）通信システムなど、オーバーレイ通信システム１２０を含む。

示すように、通信システム１１０は複数のノード１０１を含む。複数のノード１０１はアンダーレイ通信ネットワークを形成しており、各ノード１０１には近隣のノードに対する短距離通信のみが可能である。オーバーレイ通信システム１２０は複数のトランシーバ１０４，１０５を含んでおり、アンダーレイ通信ネットワーク１１０の各ノード１０１と通信することが可能である。本発明の好適な実施形態では、トランシーバ１０４，１０５は好適にはセルラー基地局であるが、代替の実施形態では、トランシーバ１０４，１０５はビーコンなど、他の発信／受信装置を含んでよい。

当業者には認められるであろうように、一般に、アンダーレイ通信システム１１０内の２つのノード間の伝送は介在するノードを通じて生じ、介在するノードは発信元の伝送を
受信すると、発信元の伝送が宛先ノードに到達するまで発信元の伝送を「繰り返す」。したがって、第１のノードは、第２のノードへの情報を伝送しようとすると、まず最初に第１のノードと第２のノードとの間の経路（即ち、それらに介在するノード）を判定する必要がある。従来技術のシステムでは、このことはメッセージ・フラッディングにより行われている。

上述のように、メッセージ・フラッディングは通信システム１００内でパスを検出するための信頼できる手法であるが、フラッディングにより、過度の量のシステム干渉が生じる。この問題に対処するため、本発明の好適な実施形態では、オーバーレイ通信システム１２０がアンダーレイ通信システム１１０の経路判定を補助する。詳細には、通信システム１１０内の第１のノードは、第２のノードへの経路情報を判定しようとするとき、経路が必要であること（ＲＴ＿ＮＥＥＤ）を通信システム１２０内のトランシーバ（例えば、トランシーバ１０４）へ発信する。経路必要のメッセージにより、第１のノードから第２のノードまでの経路を判定するという要求が、オーバーレイ通信システム１２０に対し通知される。本発明の好適な実施形態では、ＲＴ＿ＮＥＥＤメッセージには第１のノードの識別性及び第２のノードの識別性が含まれる。

オーバーレイトランシーバ１０４は経路必要のメッセージを受信すると、アンダーレイ通信システム１１０内の全ノードの粗位置推定を実行する。粗位置は、以下に限定されるものではないが、到来角（ＡＯＡ）手法、到来時間差（ＴＯＤＡ）、三角測量などを含む、種々の測位手法により得られる。通信システム１１０内の全ノードの粗位置が判定されると、オーバーレイトランシーバ１０４は、発信元ノードと宛先ノードとの間に存在する複数の「シード」ノード（発信元ノード及び宛先ノードを含む）を判定する。シードノードは、発信元ノードと宛先ノードとの間の経路を判定するという要求を（ＳＥＥＤ＿ＮＯＴＩＦメッセージにより）通知する。ＳＥＥＤ＿ＮＯＴＩＦメッセージには、各シードノードに対するユニークなシード識別子や、探索が試行される経路をユニークに識別する経路探索識別番号が含まれる。シードは、ＳＥＥＤ＿ＮＯＴＩＦメッセージを受信すると、即座に経路探索（ＲＴ＿ＤＩＳＣ）メッセージをブロードキャストする。シードノードは、ＲＴ＿ＤＩＳＣメッセージ内に経路識別子及びシードノードの識別子を含める。このように、いずれかのノードがオーバーレイトランシーバ１０４に経路探索の必要を通知する結果、複数のシードノードが経路探索メッセージのブロードキャストを開始する。

アンダーレイ通信システム１１０内の全てのノード１０１は、定期的にＲＴ＿ＤＩＳＣメッセージを聴取する。ノードは、ＲＴ＿ＤＩＳＣメッセージを受信すると、メッセージを検査し、発信された「シード」及び経路探索識別番号を判定する。アンダーレイ通信システム１１０内のいずれかのノードは、ＲＴ＿ＤＩＳＣメッセージを受信した場合、ＲＴ＿ＤＩＳＣメッセージ内に含まれる情報を記憶する。続いて、同一の経路識別子を有する他のシードから、任意の他のＲＴ＿ＤＩＳＣメッセージが受信されたか否かの判定が行われる。受信されていた場合、オーバーレイトランシーバ１０４には２つのシード間の経路情報が与えられ、オーバーレイ通信システムにはＲＴ＿ＩＮＦＯメッセージによりシード間の「パス」が与えられる。応答して、オーバーレイ通信システムは２つのシードの地理的領域内のノードに、ＲＴ＿ＤＩＳＣメッセージの伝送を中止するように指示する。

オーバーレイトランシーバ１０４は、全シード間の経路情報を受信すると、アンダーレイ通信システム１１０内の全ノードにメッセージ・フラッディングを停止するように指示することにより、システムのシグナリング及び干渉を制限する。続いて、オーバーレイトランシーバ１０４は第１のデバイスと第２のデバイスとの（発信元デバイスと宛先デバイスとの）間の適切な経路を判定し、第１のノードと第２のノードとの間に通信が生じるように、その情報を第１のノードへのＲＴ＿ＩＮＦＯメッセージにより発信元デバイス及び宛先デバイスにブロードキャストする。

メッセージ・フラッディングはアンダーレイ通信システム１１０内の全シードから同時に生じるため、非常に減少される。実際に、検索ステップ数における改良の平均値は５．０２５回、標準偏差は１．６１回であり、フラッディングしたノード数における減少は１４．７１回、標準は８．２７回であることが、シミュレーションにおいて示されている。システムの改良を、探索時間の減少対送信元−宛先間距離（ホップ数での）のグラフである図２に示す。

図３は、本発明の好適な実施形態による経路探索を示すメッセージフロー図である。詳細には、図３には、第２のノードへの経路を探索しようとする第１のノードと、オーバーレイ通信ネットワーク内のトランシーバとの間に生じるメッセージ交換を示す。示すように、ノードは、経路を探索しようとするとき、経路必要（ＲＴ＿ＮＥＥＤ）メッセージをトランシーバ１０４へ発信する。応答して、トランシーバ１０４は、通信システム１１０内のシードノードにＳＥＥＤ＿ＮＯＴＩＦメッセージを発信し、通常の経路探索手続を開始するように指示する。詳細には、全てのシードノードがＲＴ＿ＤＩＳＣメッセージを開始する。以前の（ＲＴ＿ＤＩＳＣ）メッセージの複製ではない経路探索メッセージ（ＲＴ＿ＤＩＳＣ）を受信した各ノードは、ブロードキャストされたメッセージの生存時間が生じるまで、その経路探索メッセージ（ＲＴ＿ＤＩＳＣ）を再びブロードキャストする。上述のように、本発明の好適な実施形態を除く、通常のスケジューリング及びメッセージ・フラッディングは、第３のノードが同一の経路識別子を有する２つのノードから（ＲＴ＿ＤＩＳＣ）フラッディング・メッセージを受信したときに生じ、経路情報がトランシーバ１０４に与えられ、トランシーバ１０４に２つのシードの地理的領域内の全ノードに対しフラッディング停止（ＦＬＯＯＤ＿ＳＴＯＰ）メッセージをブロードキャストさせる。トランシーバ１０４により全シード間の経路情報が受信されると、経路情報（ＲＴ＿ＩＮＦＯ）メッセージにより第１のノードに経路情報が与えられる。本発明の好適な実施形態では、経路情報メッセージには、第１のノードから第２のノードへの各ノードに対応する一連の介在するＩＰアドレスなどの情報が含まれる。

図４は、トランシーバ１０４とシードノードとの間を流れるメッセージを示すメッセージフロー図である。上述のように、第１のノードは第２のノードへの経路を探索しようとして、トランシーバ１０４への経路必要メッセージ（ＲＴ＿ＮＥＥＤ）を開始する。まず最初に、トランシーバ１０４からの経路探索認識（ＳＥＥＤ＿ＮＯＴＩＦ）メッセージブロードキャストにより、シードノードに通信の要求を認識させる。応答して、シードノードは（ＲＴ＿ＤＩＳＣ）メッセージを用いて通常の経路探索手続を開始し、通信システム１１０をフラッディングする。上述のように、ＲＴ＿ＤＩＳＣメッセージには、特定の経路識別子や、メッセージの発信された特定のシードノードの識別子が含まれる。第３のノードは、２つのシードノードから（ＲＴ＿ＤＩＳＣ）フラッディング・メッセージを受信すると、経路情報（ＲＴ＿ＩＮＦＯ）メッセージをトランシーバ１０４に発信し、フラッディング停止（ＦＬＯＯＤ＿ＳＴＯＰ）メッセージを自身の地理的領域内の全ノードに対し送信させる。

図５は、トランシーバ１０４と第３のノードとの間を流れるメッセージを示すメッセージフロー図である。上述のように、第１のノードは第２のノードへの経路を探索しようとして、トランシーバ１０４への経路必要（ＲＴ＿ＮＥＥＤ）メッセージを開始し、シードノードにＲＴ＿ＤＩＳＣメッセージのフラッディングを開始させる。第３のノードは、ＲＴ＿ＤＩＳＣメッセージの定期的監視中、同一の経路識別子を各々有する異なるシードから２つのＲＴ＿ＤＩＳＣメッセージを受信する。応答して、第３のノードは経路情報（ＲＴ＿ＩＮＦＯ）メッセージにより、トランシーバ１０４に第３のノードの地理的領域内の全ノードに対しフラッディング停止（ＦＬＯＯＤ＿ＳＴＯＰ）メッセージを送信させる。

上述の手続を図６〜８に示す。図６において、ノード６０１はノード６０３への経路を探索しようとする。この事実がオーバーレイトランシーバ１０４に通知されることにより、トランシーバ１０４はアンダーレイ通信システム内の全ノードの地理的位置を判定し、いずれのノードがシードノードとなるかを判定する。いずれのノードがシードノードとなるかを判定する際、トランシーバ１０４は、ノード密度、発信元と目標とを結ぶ直線からのノードの距離、伝播データ、ノードの活動、トラフィックパターン、ノードの電源レベル、ノードのモビリティ（例えば、移動体ノードより固定中継器が好適であるなど）、などの基準を用いてよい。シードのモビリティ、電源レベル又はトラフィック負荷に基づきシードを適正に選択することにより、システムの全スループットや、経路の信頼性及び可用性が改良される。本発明の好適な実施形態では、発信元ノード（ノード６０１）と宛先ノード（ノード６０３）とを結ぶ直線に最も近いユニットが選択される。より詳細には、発信元と目標との間の伝播状況に関する追加の情報が存在しない場合、シードが発信元と目標との間の直線に近いように、シード選択が行われる。シード数は発信元と目標との間の距離に比例する。

続いて、図７において、ノード６０１，６０３に加え、ノード７０１〜７０５がシードノードとして識別される（発信元ノード及び宛先ノードは常にシードノードである）。シードノード６０１，６０３，７０１〜７０５は、自身のシードノード状態が通知されると、即座に経路探索メッセージのブロードキャストを開始する。上述のように、アドホックネットワークの任意のノードは、同一の経路識別子を有する２つのシードからメッセージを受信すると、それらの２つのシードの間に位置する探索されたノードのＩＤ一覧を含むメッセージをオーバーレイネットワークに送信する。この探索されたノードの一覧により、区間経路が構成される。オーバーレイトランシーバ１０４は、発信元と目標との間の全ての区間経路が識別されると、検索を停止する。これを図８に示す。

代替の実施形態では、オーバーレイシステムは、何らかの関連の履歴に基づき、信頼性のない区間経路に対する予備の区間経路を取得することを決定できる。これに加えて、検索パケットの生存時間（ＴＴＬ）は、全期待値の１／Ｎに設定される。ここでＮはアルゴリズムにおけるシード数である。アドホック密度が一様でない場合、オーバーレイネットワークは、周囲のアドホック密度が低いノードには大きなＴＴＬを設定し、かつ、周囲のノード密度が高いノードには小さなＴＴＬを設定するように、発信元及び目標に対して異なるＴＴＬを設定することができる。なお、これらの総和が宛先と目標との間の経路の期待長と等しい必要がある。

検索する時間は１／Ｎに減少する可能性がある。しかしながら、中間のノードの周辺のシグナリング（チャネルリクエスト）数が増大することによる、見込みの時間増分の減少はわずかである。したがって、目標と宛先との間のホップ数が中程度であるか又は大きいとき、この方法はより魅力的なものとなる。目標までの距離が２〜３ノードに過ぎない（即ち、ＴＴＬが非常に小さい）とき、目標又は発信元はいずれも周囲のノード密度が低く、目標又は発信元からの検索は無指向性となる。通常のトラフィックにおいて、経路が分断される場合、オーバーレイネットワークは損傷を受けた区間の再探索を開始する。この探索は、それぞれの区間を規定するシードから開始される。区間のシードの一方又は両方が利用可能でない場合、オーバーレイネットワーク（エージェント）は隣接する区間から新たなシードを選択する。

図９は、本発明の好適な実施形態によるトランシーバ９００のブロック図である。本発明の好適な実施形態では、全てのノード１０１と、トランシーバ１０４，１０５とは、トランシーバ９００に示す要素を備える。示すように、トランシーバ９００は、論理回路９０１、受信回路９０２、発信回路９０３及び記憶部９０４を備える。好適には、論理回路９０１は、以下に限定されるものではないが、Ｍｏｔｏｒｏｌａ（登録商標）Ｐｏｗｅｒ
ＰＣ（登録商標）マイクロプロセッサなど、マイクロプロセッサコントローラを備える。論理回路９０１は、トランシーバ９００を制御するための手段、メッセージの内容を解析し必要な作用を判定するための手段、及び複数の区間経路を与えるノード間の経路情報を判定するための手段として働く。これに加えて、受信回路及び発信回路９０２，９０３は、周知の通信プロトコルを利用する周知の一般的な通信用回路であり、メッセージを発信及び受信するための手段として働く。例えば、ノード１０１〜１０３において、受信器９０２及び発信器９０３は、ｎｅｕＲＦｏｎ（商標）通信システムプロトコルを利用する周知のｎｅｕＲＦｏｎ（商標）要素である。他の可能な発信器及び受信器には、以下に限定されるものではないが、ブルートゥース（登録商標）、ＩＥＥＥ８０２．１１又はハイパーラン（ＨｙｐｅｒＬＡＮ）プロトコルを利用するトランシーバが含まれる。同様に、トランシーバ１０４，１０５、受信器９０２及び発信器９０３は、オーバーレイ通信システムプロトコル（例えば、ＣＤＭＡ、ＴＤＭＡ、ＧＳＭ、ＷＣＤＭＡなど）を利用する周知の要素である。

トランシーバ９００は、別のノードへの経路を探索しようとするノードとして、２つの異なるノードの間の経路探索を補助するシードノードとして、２つの異なるノードの間の経路探索を補助する非シードノードとして、経路探索に関与するオーバーレイ通信システムにおけるトランシーバとして働く。これらの４つの事例におけるトランシーバ９００の動作を詳細に示すフローチャートを、図１０〜１３に示す。

図１０は、第２のノードへの経路を探索しようとする第１のノードとして作用するノード９００の動作を示すフローチャートである。論理フローは工程１００１にて開始する。工程１００１にて、第１のノードは発信器９０１を利用して、オーバーレイ通信システムにＲＴ＿ＮＥＥＤメッセージを発信し、第１のノードと第２のノードとの間の経路を探索することの必要をオーバーレイ通信システムに通知する。工程１００３にて、受信器９０２により、ＳＥＥＤ＿ＮＯＴＩＦメッセージが受信される。上述のように、ＳＥＥＤ＿ＮＯＴＩＦメッセージは、ユニークなシードノード識別子や、探索されている特定の経路に対する経路識別子を第１のノードに割り当てる。ＳＥＥＤ＿ＮＯＴＩＦメッセージを受信すると、論理回路９０１は発信器９０３にフラッディング・メッセージの発信を開始（工程１００５）するように指示する。上述のように、いずれかのノードが同一の経路識別子を有する異なるシードから２つのフラッディング・メッセージを受信すると、オーバーレイ通信システムに経路情報が与えられ、その地理的領域におけるフラッディングは停止する。これにより、工程１００７にて、受信器９０２によりＦＬＯＯＤ＿ＳＴＯＰメッセージが受信され、工程１００９にて、受信器９０２によりオーバーレイ通信システムから経路情報が受信される。

図１１は、シードノードとして作用するノード９００の動作を示すフローチャートである。論理フローは工程１１０１にて開始する。工程１１０１にて、受信器９０２によりＳＥＥＤ＿ＮＯＴＩＦメッセージが受信される。ＳＥＥＤ＿ＮＯＴＩＦメッセージを受信すると、論理回路９０１は発信器９０３にフラッディング・メッセージの発信を開始（工程１１０３）するように指示する。上述のように、いずれかのノードが同一の経路識別子を有する異なるシードから２つのフラッディング・メッセージを受信すると、オーバーレイ通信システムに経路情報が与えられ、その地理的領域におけるフラッディングは停止する。これにより、工程１１０５にて、受信器９０２によりＦＬＯＯＤ＿ＳＴＯＰメッセージが受信される。

図１２は、通信システム１００内の第３のノードとして作用するノード９００の動作を示すフローチャートである。詳細には、第１のノードは第２のノードへの経路を探索しようとする。第３のノードは、同一の経路識別子を有する異なるシードから２つのフラッディング・メッセージを受信すると、オーバーレイ通信システムに経路情報を発信すること
により、経路探索を補助する。論理フローは工程１２０１にて開始する。工程１２０１にて、受信器９０２により、第１のシードノードから第１の経路探索メッセージ（フラッディング・メッセージ）が受信される。このメッセージは、シードノード識別子、経路識別子及び経路情報を判定する（工程１２０３）ために、論理回路９０１により解析される。この情報は、工程１２０５にて、記憶部９０４に記憶される。工程１２０７にて、論理回路９０１は記憶部９０４を解析し、異なるシードノード識別子及び同様の経路識別子を有するフラッディング・メッセージが以前に受信されているか否かを判定する。受信されていた場合、論理フローは工程１２０９へ続く。工程１２０９にて、２つのフラッディング・メッセージから取得された経路（即ち、２つのシードノードの間の経路）がオーバーレイ通信システムをオーバーレイするために与えられ、工程１２１１にて、ＦＬＯＯＤ＿ＳＴＯＰメッセージが受信される。工程１２０７にて、第１のシード識別子と第２のシード識別子とは異ならない、又は、第１の経路識別子と第２の経路識別子とは異なると論理回路９０１が判定する場合、論理フローは工程１２１３へ続く。工程１２１３にて、メッセージは標準的なフラッディングとして再びブロードキャストされ、論理フローは工程１２０１に復帰する。

図１３は、オーバーレイ通信システムの動作を示すフローチャートである。論理フローは工程１３０１にて開始する。工程１３０１にて、オーバーレイ通信システム内の受信器はアンダーレイ通信システムの第１のノードからメッセージ（ＲＴ＿ＮＥＥＤ）を受信する。上述のように、ＲＴ＿ＮＥＥＤメッセージは、アンダーレイ通信システム内の第１のノードから第２のノードへの経路情報が必要とされることをオーバーレイ通信システムに示す表示であり、第１のノード及び第２のノードの両方を識別する識別情報を含む。応答して、論理回路９０１はアンダーレイ通信システム内のシードノードの位置を判定（工程１３０３）し、シードノードにメッセージ（ＳＥＥＤ＿ＮＯＴＩＦ）をブロードキャストして、シードノードに経路探索メッセージのブロードキャストを開始させる（工程１３０５）。工程１３０７にて、アンダーレイ通信システム内の種々のノードから複数の区間経路が受信される。上述のように、区間経路は２つのシードの間の経路情報を含む。区間経路から、論理回路はアンダーレイ通信システム内の第１のノードと第２のノードとの間の経路を判定する（工程１３０９）。最後に、工程１３１１にて、アンダーレイ通信システム内の第１のノードに経路が発信される。

特定の実施形態を参照して本発明を詳細に示したが、本発明の精神及び範囲から逸脱することなく形態及び詳細において種々の変更がなされてよいことが当業者には理解されるであろう。例えば、オーバーレイネットワーク１２０は第１のＲＯＵＴＥ＿ＩＮＦＯメッセージの受信後に工程を実行してもよく、コントローラ９０１は、ＦＬＯＯＤ＿ＳＴＯＰメッセージのブロードキャストより前に追加のＲＯＵＴＥ＿ＩＮＦＯメッセージが受信されるか否かを確認するために待機するタイマを設定する。これにより、冗長用の代替の経路を探索することが可能となる。タイマが経過する時間までに追加の経路が識別される場合、オーバーレイネットワークコントローラにより、第１のノードに経路の一覧が送信される。そのような変更も本発明の特許請求の範囲の内にあることを意図するものである。

通信システムのブロック図。 探索時間の減少対送信元−宛先間距離のグラフ。 図１の通信システムにおける種々のメッセージフローを示す図。 図１の通信システムにおける種々のメッセージフローを示す図。 図１の通信システムにおける種々のメッセージフローを示す図。 図１の通信システムにおけるメッセージ・フラッディングを示す図。 図１の通信システムにおけるメッセージ・フラッディングを示す図。 図１の通信システムにおけるメッセージ・フラッディングを示す図。 トランシーバのブロック図。 図１の通信システムの動作を詳細に示すフローチャート。 図１の通信システムの動作を詳細に示すフローチャート。 図１の通信システムの動作を詳細に示すフローチャート。 図１の通信システムの動作を詳細に示すフローチャート。

Claims (10)

1. オーバーレイ通信システムの動作方法であって、
   アンダーレイ通信システム内の第１のノードと第２のノードとの間に経路が必要であることをオーバーレイ通信システムに通知する経路必要メッセージをアンダーレイ通信システムの第１のノードから受信するメッセージ受信工程と、
   アンダーレイ通信システム内のシードノードの位置を判定する位置判定工程と、
   メッセージをシードノードに発信することによりシードノードに経路探索メッセージのブロードキャストを開始させるメッセージ発信工程と、
   アンダーレイ通信システム内のノードから複数の区間経路を受信する区間経路受信工程と、
   区間経路に基づき経路を判定する経路判定工程と、
   経路を第１のノードに発信する経路発信工程とからなる方法。
2. メッセージ発信工程は経路識別子をシードノードに発信することにより特定の経路が探索されたことを識別する工程を含む請求項１に記載の方法。
3. メッセージ受信工程は第１のノード及び第２のノードの識別子を含むメッセージを受信する工程を含む請求項１に記載の方法。
4. 区間経路受信工程は２つのシードの間の経路を各々含む複数の区間経路を受信する工程を含む請求項１に記載の方法。
5. 位置判定工程は発信元ノードと宛先ノードとを結ぶ線に最も近いノードを判定する工程を含む請求項１に記載の方法。
6. アドホック通信システム内のノードの動作方法であって、
   第１の経路探索メッセージを受信するメッセージ受信工程と、
   第１の経路探索メッセージにより第１の経路探索メッセージの発信された第１のシードノードの識別子を判定するノード識別子判定工程と、
   第１の経路探索メッセージにより第１の経路識別子を判定する経路識別子判定工程と、
   以前に受信した経路探索メッセージは同様の経路識別子を含む異なるシードノードから受信されたか否かを判定するメッセージ判定工程と、
   以前に受信した経路探索メッセージは同様の経路識別子を含む異なるシードノードから受信されたとの判定に基づき、２つの経路探索メッセージから取得された経路情報をオーバーレイ通信システムに発信する経路情報発信工程とからなる方法。
7. 経路情報発信工程は２つのシードノードの間の経路を発信する工程を含む請求項６に記載の方法。
8. オーバーレイ通信システム内に存在する装置であって、
   アンダーレイ通信システム内の複数のシードノードから複数の区間経路を受信する受信器と、
   アンダーレイ通信システム内において第１のノードと第２のノードとの間に位置する複数のシードノードを判定するとともに、複数の区間経路により第１のノードと第２のノードとの間の経路を判定する論理回路と、
   シードノードにメッセージを発信して経路探索メッセージのブロードキャストを開始させるとともに、アンダーレイ通信システム内の第１のノードに経路を発信する発信器とからなる装置。
9. アンダーレイ通信システム内に存在する装置であって、
   第１のノード及び第２のノードから第１の経路探索メッセージ及び第２の経路探索メッセージを受信する受信器と、
   第１の経路探索メッセージにより第１の経路探索メッセージの発信された第１のシードノードの識別子を判定し、第１の経路探索メッセージ及び第２の経路探索メッセージにより第１の経路識別子及び第２の経路識別子を判定するとともに、第１の経路識別子及び第２の経路識別子が同様であるか否かを判定する論理回路と、
   第１の経路識別子と第２の経路識別子とが異なるとき、第１の経路探索メッセージ及び第２の経路探索メッセージから取得された経路情報をオーバーレイ通信システムに発信する発信回路とからなる装置。
10. 経路情報は第１のノードと第２のノードとの間の経路を含む請求項９に記載の装置。

Images