(57)【要約】方法は、ノードのクラスターにグループ化された複数のノードと該複数のノードと接続する複数の無線リンクとを有し、各クラスターは指定されたクラスター・リーダー・ノードを持っているモバイル・アドホック・ネットワークにおいてデータを送信するために提供される。方法は、送り元クラスターの送り元ノードから送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル要求を送信し、上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、複数の上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定することを有しても良い。更に、少なくとも１つのクラスター目標ノードが、上記クラスターレベル・ルートに沿ってクラスター内で指定されても良く、そして、上記送り元ノードから上記少なくとも１つのクラスター目標ノードを有する上記送り先ノードへのノードレベル・ルートが決定されるようにしても良い。加えて、方法は、また、上記送り元ノードのアドレスと、少なくとも１つのクラスター目標ノードのアドレスと、データを転送するために特命データ・パケットを生成することを有しても良い。
2005524337.tif 000002
【特許請求の範囲】
【請求項１】
ノードのクラスターにグループ化された複数のノードと該複数のノードと接続する複数の無線リンクとを有し、各クラスターは指定されたクラスター・リーダー・ノードを持っているモバイル・アドホック・ネットワークにおいてデータを送信する方法であって、
送り元クラスターの送り元ノードから送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル要求を送信し、
上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、複数の上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定し、
上記クラスターレベル・ルートに沿ってクラスター内の少なくとも１つのクラスター目標ノードを指定し、
上記送り元ノードから上記少なくとも１つのクラスター目標ノードを有する上記送り先ノードでノードレベル・ルートを決定し、
上記送り元ノードのアドレスと、少なくとも１つのクラスター目標ノードのアドレスと、上記ノードレベル・ルートと、上記クラスターレベル・ルートとを有する特命データ・パケットを生成し、
上記特命データ・パケットに基づいて、上記ノードレベル・ルートを介して、上記送り元ノードから上記送り先ノードへデータを転送する方法。
【請求項２】
上記ノードレベル・ルートを決定することは、上記クラスターレベル・ルートに沿って次の隣接するクラスターに対して上記送り元ノードからクラスター目標ノードへの上記ノードレベル・ルートを決定し、上記クラスターレベル・ルートに沿って各クラスター目標ノードから次のクラスター目標ノードへのノードレベル・ルートを決定することを更に有する請求項１記載の方法。
【請求項３】
上記特命データ・パケットは、上記次のクラスター目標ノードのアドレスとそのノードへの上記ノードレベル・ルートを有するため、上記クラスターレベル・ルートに沿って各クラスター目標ノードで特命データ・パケットを更新することを有する請求項１記載の方法。
【請求項４】
上記送り元クラスターと上記送り先クラスターとが同じクラスターである場合、上記少なくとも１つのクラスター目標ノードの上記アドレスと上記クラスターレベル・ルートとが所定値と等しい請求項１記載の方法。
【請求項５】
上記クラスターレベル・ルートと、上記少なくとも１つのクラスター目標ノードの上記アドレスと、上記ノードレベル・ルートとを有する上記送り元ノードへの階層的な送り元ルートを送り元ノードにて格納することを更に有する請求項１記載の方法。
【請求項６】
少なくとも上記送り元クラスター・リーダー・ノードと上記送り先クラスター・リーダー・ノードとを有する複数の上記クラスター・リーダー・ノードをリーダー・ノード・クラスターへとグループ化し、上記リーダー・ノード・クラスター内の上記送り元クラスターの上記クラスター・リーダー・ノードから上記送り先クラスターの上記クラスター・リーダー・ノードへの高いレベルのルートを決定することを更に有し、上記クラスターレベル・ルートは、少なくとも、高いレベルのルートに沿って対応するクラスター・リーダー・ノードを持っている上記クラスターを有する請求項１記載の方法。
【請求項７】
上記クラスターレベル・ルートを決定することは、
上記クラスター・リーダー・ノード間の指定された通信リンクを決定し、
上記指定された通信リンクを介して、上記送り元クラスターのクラスター・リーダー・ノードから残りのクラスー・リーダーへとクラスター・リーダー・ノード・ルート要求を送信し、
上記クラスター・リーダー・ノード・ルート要求の配信に沿って、上記送り先クラスターのクラスター・リーダー・ノードから上記送り元クラスターの上記クラスター・リーダー・ノードへとクラスター・リーダー・ノード・ルート返信を送り返す請求項１記載の方法。
【請求項８】
遅延、リンク可能性、及び利用可能性のうち少なくとも１つに基づいて、配信ルートを決定することを更に有する請求項７記載の方法。
【請求項９】
各クラスター・ノードは指定されたクラスター・リーダー・ノードを持っている、クラスター・ノードへグループ化された複数のノードと、
上記複数のノードを接続する複数の無線リンクとを有し、
上記複数のノードは、
送り元クラスターの送り元ノードから上記送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル・ルート要求を送信し、
上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定し、
上記クラスターレベル・ルートに沿って、クラスター内の少なくとも１つのクラスター目標ノードを指定し、
上記送り元ノードから、上記少なくとも１つのクラスター目標ノードを有する上記送り先ノードへのノードレベル・ルートを決定し、
上記送り先ノードのアドレスと、上記少なくとも１つ以上のクラスター目標ノードのアドレスと、上記ノードレベル・ルートと、上記クラスターレベル・ルートとを有する特命データ・パケットを生成し、
上記特命データ・パケットに基づいて、上記ノードレベル・ルートを介して、上記送り元ノードから上記送り先ノードへデータを転送することを有する無線アドホック・ネットワーク。
【請求項１０】
上記ノードレベル・ルートは、上記クラスターレベル・ルートに沿って次の隣接するクラスターに対して上記送り元ノードからクラスター目標ノードへのノードレベル・ルートと、上記クラスターレベル・ルートに沿って各クラスター目標ノードから次のクラスター目標ノードへのノードレベル・ルートとを有する請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１１】
上記送り先ノードの上記アドレスが、上記送り元クラスターに対して、クラスター・リーダー・ノードで上記対応するクラスター・リーダー・ノードのアドレスに従って格納される請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１２】
上記送り元ノードで、上記クラスターレベル・ルートと、上記少なくとも１つのクラスター目標ノードの上記アドレスと、上記ノードレベル・ルートとを有するように、上記送り先ノードへの階層的な送り元ルートが格納される請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１３】
上記クラスター・リーダー・ノードと接続する指定された通信リンクを更に有し、上記クラスターレベル・ルートは、上記指定された通信リンクを介して、上記送り元クラスターの上記クラスター・リーダー・ノードから上記残りのクラスター・リーダーへとクラスター・リーダー・ノード・ルート要求を送信し、上記クラスター・リーダー・ノード・ルート要求の配信に沿って、上記送り先クラスターの上記クラスター・リーダー・ノードから上記送り元クラスターの上記クラスター・リーダー・ノードへとクラスター・リーダー・ノード・ルート返信を送り戻すことによって、決定される請求項９記載のモバイル・アドホック・ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークの分野に関し、特に、モバイル・アドホック無線ネットワーク、及びその方法に関する。
【背景技術】
【０００２】
無線ネットワークは、過去１０年間で高まる開発を経験してきた。最も休息に開発されている領域の一つは、モバイル・アドホック・ネットワークである。物理的に、モバイル・アドホック・ネットワークは、共通の無線チャンネルを共有する多くの地域分散型のモバイル・ノードの可能性を有している。セルラーネットワークや衛星ネットワークのようなネットワークの他のタイプと比較しても、モバイル・アドホック・ネットワークの最も顕著な特徴は、いかなる定着した構造基盤も欠如していることである。ネットワークは、モバイル・ノードのみで形成され、ノードが転送したり、他ノードから受信したりするよう「空中」で作り出される。ネットワークは特定のノードに依存せず、いくつかのノードが参加したり他のノードが離れて言ったりする際に動的に調整している。
【０００３】
これら独特の特徴のため、頻繁なトポロジー変化に適応することが可能な、アドホック・ネットワーク内のデータ・フローを規定するためのルーティング・プロトコルが要求される。アドホック・ルーティングの２つの基本的なカテゴリーが近年出現してきており、それは、主に、リアクティブ又は「オンデマンド」プロトコル、そして、プロアクティブ又はテーブル駆動プロトコルである。リアクティブ・プロトコルは、ルート要求に応じて送り先へ要求される。リアクティブ・プロトコルの例には、アドホック・オンデマンド・ディスタンス・ベクトル（ＡＯＤＶ）ルーティング、ダイナミック・ソース・ルーティング（ＤＳＲ）及び、テンポラリ・オーダー・ルーティング・アルゴリズム（ＴＯＲＡ）が含まれる。
【０００４】
一方で、プロアクティブ・ルーティング・プロトコルは、ネットワーク内の各ノードから他ノードへの矛盾がない最新の情報を保持しようとする。そのようなプロトコルは、概して各ノードにルーティング情報を格納するための１つ又はそれ以上のテーブルを保持することを要求し、ネットワークの一貫した観点を保持するためにネットワーク全体に更新を広めることによってネットワーク・トポロジー内の変化に応じている。そのようなプロアクティブ・ルーティング・プロトコルの例には、Ｐｅｒｋｉｎｓの米国特許番号５、４１２、６５４号に開示されるデスティネーション・シーケンス・ディスタンス・ベクトル（ＤＳＤＶ）ルーティングと、無線ルーティング・プロトコル（ＷＲＰ）、そしてクラスターヘッド・ゲートウェイ・スイッチ・ルーティング（ＣＧＳＲ）を含む。送り元ノードからの距離に基づいてプロアクティブ型とリアクティブ型手法の両方を用いたハイブリッドプロトコルは、Ｈａａｓの米国特許番号６、３０４、５５６に開示されるゾーン・ルーティング・プロトコル（ＺＲＰ）である。
【０００５】
アドホック・ネットワーク開発の前進への１つの挑戦は、多数のノードを包含するためのそのようなネットワークを拡張することである。１つの従来技術において、Ｄａｓ等によって「Routing  in  Ad-Hoc  Networks  using  Minimum  Connected  Dominating  Sets」、  IEEE  Int.  Conf.  On  Commun.  (ICC  '97),  1997.に開示される最適のスパイン・ルーティング（ＯＳＲ）手法のような「スパイン」ルーティングを利用する試みがなされている。この手法では、スパイン又は「仮想バックボーン」は、各ネットワーク・ノードがスパイン・ノードから１つのホップしかないように定義されている。全体的なトポロジー（リンク状態）は、各スパイン・ノードで保持されており、リンク状態ルーティング・アルゴリズムは、各送り先への現在のルートを生成するために、各スパイン・ノードにて実行される。
【０００６】
他の関連する手法は、Ｄａｓ等によって「Routing  in  Ad-Hoc  Networks  using  a  Spine」、IEEE  Int.  Conf.  On  Computer  Commun.  and  Networks  (IC3N  '97),  1997にて開示されているクラスター・スパイン・ルーティングである。この手法は、クラスター内のノードをグループ化することによって、また、ＯＳＲ手法へ第二階層的レベルを加えることによって、より大きいネットワークサイズへスパイン・ルーティングの適応性を拡大しようとするものである。また他の手法は、Ｓｉｖａｋｕｍａｒ等によって「The  Clade  Vertebrata:  Spines  and  Routing  in  Ad-Hoc  Networks」、IEEE  Symposium  On  Computer  and  Commun.,  1998にて開示される部分的知識スパイン・ルーティング（ＰＳＲ）として知られている。
【０００７】
上述した従来技術の各クラスター／スパイン手法の一つの共通の特長は、夫々がプロアクティブ・ルーティングに依存しているということである。プロアクティブ・ルーティングの１つの潜在的な欠点は、一般に、常に全送り先への最良のルートを保持するために相当量のルーティング・オーバーヘッドが要求されていることである。この問題は、非常に多数のノードを有するアドホック・ネットワークに適応した場合、特に重大となる。
【発明の開示】
【課題を解決するための手段】
【０００８】
前述の背景技術に鑑みて、本発明は、比較的大きいノード数を持つネットワークに特に良く適しており、かつアドホック・ネットワークにおいて、データを送信するための方法を提供することを目的とする。
【０００９】
本発明に係る上記及び他目的、特徴、効果は、ノードのクラスターにグループ化された複数のノードと該複数のノードと接続する複数の無線リンクとを有し、各クラスターは指定されたクラスター・リーダー・ノードを持っているモバイル・アドホック・ネットワークにおいてデータを送信する方法によって提供される。方法は、送り元クラスターの送り元ノードから送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル要求を送信し、上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、複数の上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定することを有しても良い。更に、少なくとも１つのクラスター目標ノードが、上記クラスターレベル・ルートに沿ってクラスター内で指定されても良く、そして、上記送り元ノードから上記少なくとも１つのクラスター目標ノードを有する上記送り先ノードへのノードレベル・ルートが決定されるようにしても良い。加えて、方法は、また、上記送り元ノードのアドレスと、少なくとも１つのクラスター目標ノードのアドレスと、上記ノードレベル・ルートと、上記クラスターレベル・ルートとを有する特命データ・パケットを生成することを有しても良い。データは、上記特命データ・パケットに基づいて、上記ノードレベル・ルートを介して、上記送り元ノードから上記送り先ノードへと転送されても良い。
【００１０】
更に特に、上記少なくとも１つのクラスター目標ノードを決定することは、上記クラスターレベル・ルートに沿ってクラスター毎に対応するクラスター目標ノードを決定することを有しても良い。更に、上記ノードレベル・ルートを決定することは、上記ノードレベル・ルートは上記クラスターレベル・ルートに沿って次の隣接するクラスターに対して上記送り元ノードからクラスター目標ノードへの上記ノードレベル・ルートを決定しても良いし、また、ノードレベル・ルートは上記クラスターレベル・ルートに沿って各クラスター目標ノードから次のクラスター目標ノードで決定されても良い。また、上記特命データ・パケットを生成することは、更に、上記次のクラスター目標ノードのアドレスとそのノードへの上記ノードレベル・ルートを有するため、上記クラスターレベル・ルートに沿って各クラスター目標ノードで特命データ・パケットを更新することを有しても良い。
【００１１】
上記少なくとも１つのクラスター目標ノードの上記アドレスと上記クラスターレベル・ルートとは、上記送り元クラスターと上記送り先クラスターとが同じクラスターである場合、所定値と等しくても良い。方法は、更に、上記クラスターレベル・ルートと、上記少なくとも１つのクラスター目標ノードの上記アドレスと、上記ノードレベル・ルートとを有する上記送り元ノードへの階層的な送り元ルートを送り元ノードにて格納することを更に有しても良い。また、階層的な送り元は、上記送り元ノードで送り先ノードへと格納される。階層的な送り元ルートは、上記クラスターレベル・ルートと、上記少なくともクラスター目標ノードの上記アドレスと、ノードレベル・ルートとを有しても良い。加えて、上記クラスターレベル・ルートは、上記送り元クラスターのために、クラスター・リーダー・ノードで格納されても良い。
【００１２】
更に、方法は、少なくとも上記送り元クラスター・リーダー・ノードと上記送り先クラスター・リーダー・ノードとを有する複数の上記クラスター・リーダー・ノードをリーダー・ノード・クラスターへとグループ化することを有しても良い。高いレベルのルートは、上記リーダー・ノード・クラスター内の上記送り元クラスターの上記クラスター・リーダー・ノードから上記送り先クラスターの上記クラスター・リーダー・ノードで決定されても良い。また、上記クラスターレベル・ルートは、少なくとも、高いレベルのルートに沿って対応するクラスター・リーダー・ノードを持っている上記クラスターを有しても良い。
【００１３】
上記クラスターレベル・ルートを決定することは、上記クラスター・リーダー・ノード間の指定された通信リンクを決定し、上記指定された通信リンクを介して、上記送り元クラスターのクラスター・リーダー・ノードから残りのクラスー・リーダーへとクラスター・リーダー・ノード・ルート要求を送信することを有しても良い。更に、クラスター・リーダー・ノード・ルート返信は、上記クラスター・リーダー・ノード・ルート要求の配信に沿って、上記送り先クラスターのクラスター・リーダー・ノードから上記送り元クラスターの上記クラスター・リーダー・ノードへと送り返されても良い。
【００１４】
また特に、上記指定された通信リンクのうち少なくとも１つは、クラスター・リーダー・ノードでないノードを有しても良い。更に、各クラスター・リーダー・ノードは、隣接するクラスター・リーダー・ノードのアイデンティティを格納しても良いし、また、上記クラスター・リーダー・ノード・ルート要求を送信することは、各クラスター・リーダー・ノードからその隣接するクラスター・リーダー・ノードへとクラスター・リーダー・ノード・ルート要求を送信することを有しても良い。また、上記隣接するクラスター・リーダー・ノードは、その現在のアドレスを維持するために、周期的に問い合わせされても良い。更に、上記配信ルートは、上記送り元及び送り先クラスターの上記クラスター・リーダー・ノード間で最小のクラスター・リーダー・ノード数を有しても良い。遅延、リンク可能性、及び利用可能性などのような他パス・メトリックが、最良のルートを決定することに役立てても良い。
【００１５】
モバイル・アドホック・ネットワークは、また、モバイル・アドホック・ネットワークは、また、本発明に従って提供され、各クラスター・ノードが指定されたクラスター・リーダー・ノードを持っていて、ノードのクラスターへグループ化した複数のノードと、上記複数のノードと接続する複数の無線リンクとを有するようにしても良い。上記に簡単に概要説明したように、複数のノードがノード間でデータを送信しても良い。
【発明を実施するための最良の形態】
【００１６】
本発明は、以下に、最良の実施例が示される添付の図面を参照して詳しく説明する。しかしながら、本発明は、幾つかの異なる形態に具現化され得るし、また、ここに示される実施例に限定されるように解釈されるべきではない。むしろ、これら実施例は、この開示を通して完了し、また、当業者へ発明の範囲を十分に伝えるように提供されている。全体を通して符号は要素を参照し、主要な及び多数の主要な表記は、選択的な実施例において同様の要素を示すように使用されている。
【００１７】
最初に図１を参照すると、本発明に係るモバイル・アドホック・ネットワーク１０は例示的に、無線通信リンク１３によって接続される複数のノード１１を有する。ノード１１は、当業者によって理解されるような、他も同様に、無線モデムを備えたコンピュータ、パーソナル・データ・アシスト（ＰＤＡｓ）等のような、無線アドホック・ネットワーク内で通信可能な無線通信装置のいかなる適したタイプでも良い。もちろん、必要に応じて、ノード１１が固定通信構造基盤に随意的に接続されても良いことは確かであることを理解されるであろう。
【００１８】
本発明によれば、ノード１１は、好ましくは、図１において、ノードの夫々のグループを囲む円で例示的に示されるクラスター１２へとグループ化される。クラスター１２へのノード１１のグループ化は、以下に更に詳細に説明する。クラスター１２の夫々に対して、それらのノード１１の一つは、クラスター・リーダー・ノード２１から３３の夫々として指定される。クラスター・リーダー・ノード２１から３３を指定するための処理及び機能を以下に更に説明する。説明を明確にするため、ここで、クラスター１２が個別に説明される場合、特定クラスターがその対応するクラスター・リーダー・ノードの参照番号によって参照される。例えば、クラスター・リーダー・ノード２１は、クラスター２１など内にある。
【００１９】
本発明に係るアドホック・ネットワークにおいてデータを送信するための方法は、図４から図６のフロー図を参照しつつ説明する。方法は、ブロック４１でノード１１をクラスター１２へとグループ化することによって開始される（ブロック４０）。種々の手法をクラスター１２内のノード１１をグループ化するために使用しても良い。一般的に、好ましくは、クラスターにするための決定及びクラスター・リーダーの選択は、当業者によって理解されるような、特定のネットワーク要件を満たすために選択されたパラメーターで一般化された計測基準に基づいている。
【００２０】
一例として、ノード１１がクラスター関連性メトリックに基づいて結合するためのクラスター１２を選択しても良い。このメトリック（測定基準）は、ノード１１が関連付ける潜在的なクラスター１２毎に計算されても良し、ノードがどれほど良く該当のクラスターに「適している」かに基づいても良い。クラスター関連性メトリックは、ホップ・カウントがクラスター・リーダー・ノードへの経路に対して計算されるホップ・カウント・メトリックのように単純とすることもできる。この単純な場合、ノードは、ホップ・カウント内で最も近いクラスター・リーダー・ノードと関連するであろう。
【００２１】
他メトリックは、例えば、ｋＮホップ内の全クラスター・メンバーへのパス・メトリック、ｋＮホップ内のクラスター・メンバーの数、クラスター・リーダーへのパス・メトリック、及び／又はクラスター・リーダー・メトリックのような異なる測定を考慮しても良い。クラスター関連性に対する統合されたメトリックを作成するために、これら測定方法を組み合わせることが可能な幾つかの方法がある。１つの例として、ノードがクラスター・リーダー・ノードｍに関連付けるためのメトリック
【００２２】
【数１】
2005524337.tif 000003
を計算する重み付けした合計が、
【００２３】
【数２】
2005524337.tif 000004
として計算される。ここで、ｎｍはクラスターｍ内にあるｋＮホップ近傍内のノード数であり、
【００２４】
【数３】
2005524337.tif 000005
は、その近傍でのｉ番目のノードへのパス・メトリックであり、
【００２５】
【数４】
2005524337.tif 000006
は、クラスター・リーダー・ノードｍへのパス・メトリックであり、
【００２６】
【数５】
2005524337.tif 000007
は、クラスター・リーダー・メトリックであり、ａ、ｂ、及びｃは、ネットワーク要件に合わせたパラメーターである。もちろん、当業者によって理解されるような他の適切な手法を使用しても良い。
【００２７】
上記パラメーターは、可能な限りクラスター内の多くのノード１１への最小のパス・メトリックによるクラスター・リーダー・ノード２１から３３の選択間の関連性において妥協を許している。ノード１１は、結合するためのリーダーとして、最小のクラスター関連性メトリック
【００２８】
【数６】
2005524337.tif 000008
を持っているクラスター・リーダー・ノード２１から３３を選択する。更に、ホップ・カウント制限は、クラスター毎のノード数における制限ＬＣＬと同様に、クラスター・リーダー・ノードのホップＫＣ内にあるべき新たなクラスターを要求するように確立されても良い。
【００２９】
上記計算で使用されるパス・メトリックは、当業者によって理解されるような他の適切な方法が使用されても良いが、例えば、ノード又はリンク・メトリックとして、ホップ・カウント、遅延、利用可能能力、ノード耐久性、及び／又はリンク耐久性などのような１つ又はそれ以上の構成要素を含んでいても良い。パス・メトリックは、また、経路に沿ってリンク及びノード・メトリック構成要素の重み付け合計として計算されても良い。
【００３０】
上記クラスター関連性メトリックがある限界内にない場合、ノード１１は、ブロック４２にて、クラスター・リーダー・ノードとなり新たなクラスター１２を形成するように選択する。この際に、クラスター・リーダーの選択ではそのＫＮホップ近傍で競合するかもしれない。他のメトリック、クラスター・リーダー・メトリックがこの目的のために使用されても良い。一般に、クラスター・リーダー・メトリックは、ノード１１がそのＫＮホップ近傍に対するクラスター・リーダー・ノードのタスクをどのくらい良く実行するかに基づいている。
【００３１】
更に具体的に言うと、クラスター・リーダー・メトリックは、いくつかの形式の一つをとる。ＫＮホップ近傍内で達成可能なノード数と同じくらい単純であってよい。しかしながら、メトリックに対する追加構成要素は、あるアプリケーションで説明される。クラスター・リーダーは、好ましくは、クラスター・リーダーとしてその動作の観点から、すなわち、パワーアップとスリープモードとの間を断続的に選択することよりは、「耐久性がある」ことである。クラスター・リーダー・ノードを断続的に動作させることは、当業者によって理解されるように、階層的トポロジーでは破壊的な動きを引き起こし易い。
【００３２】
したがって、クラスター・リーダーとなるべき主張しているノード１１が、例えば、ＫＮホップ近傍内で達成可能なノード数、これらノードへのパス・メトリック、隣接クラスター・ノード２１から３３へのパス・メトリック、中心点のリンク可能性の合計、ノード耐久性、そして、ノードの相対的移動性のような１つ又はそれ以上の構成要素を用いるクラスター・リーダー・メトリック
【００３３】
【数７】
2005524337.tif 000009
を計算する。もちろん、当業者によって理解される他のメトリック構成要素が使用されても良い。与えられたネットワーク・アプリケーションに対して、クラスター・リーダー・メトリックが、当業者によって理解されるようなクラスター関連性メトリックに対して、上記等式（１）での例示と同等な方法にてそのアプリケーションのために必要とされるこれら構成要素の適切な組み合わせとして形成される。
【００３４】
以下に更に説明されるように、各クラスター・リーダー・ノード２１から３３は、クラスター・リーダー・ノード・アナウンス（ＣＬＮＡＮＮ）を周期的に（例えば、ｎＣＬホップの伝達制限を伴って）ブロードキャストする。このメッセージの伝達制限は、全ての隣接するクラスターのクラスター・リーダー・ノードと同様に、全クラスター・メンバーに到達することができるような制限である。このメッセージは、クラスター・リーダー・ノードとしてノードに通知し、そのノードに対してクラスター・リーダー・メトリックを含んでいる。更に、当業者によって理解されるように、伝達されるいかなる経路に対してもパス・メトリックの累積を許容するために代替物を含んでも良い。
【００３５】
パス・メトリックの幾つかの形式が可能であり、当業者によって理解されるように、パス・メトリックは１つ又はそれ以上の構成要素として、又は、ＣＬＮＡＮＮメッセージを再送信し、ベクトル・メトリックへの貢献を付加する各ノードのベクトルとして蓄積され得る。パス・メトリック及びクラスター・リーダー・メトリックは、ノードにクラスター関連性メトリックの計算を許容する。クラスターと結合又は連携するための手順及びクラスター・リーダー・ノードを選択するための手順は、説明を明確にするためにここに別途説明されるが、実際、幾つかの実施例においてそれらがひとつの複合法に実装されるように密接に関連しても良いことは、理解されることである。
【００３６】
クラスター連携性及びクラスター・リーダー・ノードの選択の動作詳細を、新たなクラスター・リーダー・ノードの選択のための筋書きが概略的に例示されている図１０を参照しつつ説明する。
【００３７】
クラスター１０１及び１０２は、指定されたクラスター・リーダー・ノード１０１及び１０２を夫々有する。例示及び説明を明確にするため、特定のクラスター・リーダー・ノードのために使用される同一参照符号はその夫々のクラスターを指定するために使用される。図１０に例示される例を用いて、周期的に行うメッセージに連動される動作詳細、ノードのパワーアップ選択及びクラスター関連性、クラスター・リーダー・ノード選択、リンク失敗、ノード失敗、そして、新たなリンク追加について説明する。
【００３８】
周期的に行われるメッセージに対して、２つのタイプの周期的メッセージが使用される。クラスター・リーダー・ノード１０１及び１０２は、上記簡単に説明したように、周期的なＣＬＮＡＮＮメッセージを発行している。このメッセージは、クラスター・リーダー・ノードとしてのノードの存在を通知する。隣接するクラスター、特に、隣接するクラスター・リーダー・ノード内でメッセージが全ノード１１に達するようにｎＣＬホップに対して伝達される。このメッセージは、横切った各経路に沿って、クラスター・リーダー・ノードからノードへの経路に対するパス・メトリックを蓄積するために、クラスター・リーダー・メトリック及びメッセージを再ブロードキャストするノードの代替物を有している。
【００３９】
クラスター・リーダー・メトリックは、また、このメトリックのクラスター内の他ノードに通知するために使用されても良い。このメトリックに基づいてリーダーシップのために競合した場合、より良いクラスター・リーダーとなる他ノードが決定できるようにすることができる。各普通のノード１１は、ノードのｋＮホップ近隣では、全ノードに達するようにｋＮホップに対して伝達されるＨＥＬＬＯメッセージを近隣にブロードキャストする。このことは、ｋＮホップ近隣の全ノードに対してそれら近隣の全ノードへパス・メトリック情報を収集することを許容する。この方法にて取得したパス・メトリックは、クラスター・リーダー及びクラスター関連性メトリックの両方を形成することに使用可能である。
【００４０】
ノード・パワーアップ及びクラスター関連性に関して、ノード１１をパワーアップすることは、以下の手順を実行する。ノード１１は、結合する可能性のある潜在的なクラスターを識別するためにクラスターを連接することにおいてクラスター・リーダー・ノードから周期的なＣＬＮＡＮＮメッセージを「聞こう」とする。更に、パス・メトリック情報を収集するためにｋＮホップ近隣内のノード１１からそのｋＮホップ近隣内の全ノードへ周期的なＨＥＬＬＯメッセージを聞こうとする。加えて、周期的なＨＥＬＬＯメッセージがそのｋＮホップ近隣内の全ノードへブロードキャストされる。クラスター関連性メトリック
【００４１】
【数８】
2005524337.tif 000010
は、隣接するクラスター・リーダーｍ毎に形成され、及びクラスター・リーダー・ノードｍは結合するクラスターとして最小クラスター関連性メトリック
【００４２】
【数９】
2005524337.tif 000011
にて選択される。
【００４３】
メトリック
【００４４】
【数１０】
2005524337.tif 000012
は、考慮されるノードが結合されるクラスターに十分に近いことを指定するために閾値Ｔｊ以下であることが好ましい。この閾値が満たされる場合、クラスター結合メッセージＣＬＪＯＩＮは、クラスター・リーダー・ノードｍへ送信される。クラスターがクラスター毎のノード数での制限ＬＣＬより以下である場合、クラスター・リーダー・ノードはクラスター内のノードｗ受け付けて、そのノードへ受付メッセージＣＬＡＣＣＥＰＴを送信する。クラスター・リーダー・ノードは他メンバーを受け付けることができない場合、拒否メッセージＣＬＲＥＪＥＣＴをノードへ送信する。加えて、ノードが拒否されたら、次の最も良いクラスター・リーダー・ノードをそのバックアップとして選択し、そのクラスターに結合するために処理を繰り返す。
【００４５】
上記処理に続いてノード１１は、パワーアップしてすぐに通常通りにクラスター１２のメンバーになるだろう。場合によって、そのようなネットワークの始動では、例えば、関連性を完了すべき受付可能なクラスター・リーダー・ノード２１から３３を見つけることができない。この場合、ノード１１はクラスター・リーダー・ノードになるために主張することを決定しても良い。
【００４６】
通常ノード１０３がクラスター・リーダー・ノードになることを主張する決意をした場合、以下の手順が開始される。ノード１０３は、ノードによって計算されたクラスター・リーダー・メトリックを含んでいる、クラスター・リーダー・ノードになるために入札を通知する、特別タイプのＣＬＮＡＮＮをそのｋＮ近隣の全ノード１１へブロードキャストする。信頼性のために、ｋＮ近隣の各ノード１１が、好ましくは、ＣＬＮＡＮＮメッセーイに応答する。当業者によって理解されるように、例えば、応答しないどのノード１１にもフォローアップＣＬＮＡＮＮメッセージをユニキャストを介して送信される。
【００４７】
肯定的にＣＬＮＡＮＮメッセージに応答しているノード１１は、ノード１０３がクラスター・リーダー・ノードになることができる同意を示すＣＬＮＡＮＮメッセージを返答する。これは、クラスター・リーダー・ノード自身になるための立場にない、或いは、オリジナルＣＬＮＡＮＮメッセージで受信したものより大きいクラスター・リーダー・メトリックかのいずれかである。ＣＬＮＡＮＮメッセージに否定的に応答するノード１１は、オリジナルＣＬＮＡＮＮメッセージで受信したものよりより良いクラスター・リーダー・メトリックを持っていて、より良いクラスター・リーダーを作ることを通知する。クラスター・リーダー引き分けの事象では、クラスター・リーダーシップの役割は、例えば、他の同点決勝を使用しても良いが、最も低いノードＩＤを持つノードに落札されるようにしても良い。
【００４８】
全ＣＬＮＡＮＮメッセージの応答が肯定的ある、或いは、論争があり、ノード１０３がクラスター・リーダー・ノードの役割を勝ち取った場合、そのノードがクラスター・リーダー・ノードの役割と仮定する。隣接するクラスター１２及び隣接するクラスター・リーダー・ノードにおいて全ノード１１に達するためにｎＣＬホップに対して広められる通常のＣＬＮＡＮＮメッセージの周期的なブロードキャストを開始する。他ノード１１は、この新たなクラスターと結合すべきか否かの判断を開始する。他ノードがノードの役割の同意を示すことに成功した場合、ノード１０３はこの新たなクラスター・リーダー・ノードのクラスターに結合するべきか否かを判断する。
【００４９】
リンク／ノード失敗及びルート・リカバリーについて、概略説明がこの時点では、クラスターリングとクラスター・リーダー・ノード指定の脈略について適切になされ、以下に詳細に説明する。さらに具体的に言うと、ノード１１が近隣ノードへのリンクを失った場合、ある行動が成される。すなわち、同一のクラスター内に留まることができるか否かを判断するためにそのクラスター・リーダー・ノードへの経路をテストする。クラスター・リーダー・ノードへのノードレベル・ルートを見つけ出せなかった場合、他クラスター・リーダー・ノードに関連付けても良い。一方、ノード１１がクラスター・リーダー・ノードへの経路を未だ持っていると判断した場合、このクラスター・リーダー・ノードと隣接するクラスターのためのクラスター・リーダー・ノードとに対するクラスター関連性メトリックを再度評価する。
【００５０】
クラスター関連性メトリックは上記他の閾値ＴＬ、すなわち、
【００５１】
【数１１】
2005524337.tif 000013
の値まで増加した場合、好ましくは、前述したように、そのクラスターをそのままにし、そのクラスター関連性メトリックが結合するための基準に合った隣接するクラスターを発見することができるかもしれない。また、ノード１１は、隣接するクラスター・リーダー・ノードより良いクラスター関連性メトリックを持っていることが判るかもしれない。その現在の関連性がクラスター・リーダー・ノードｍによるものであり、その最良な隣接するからスター・リーダー・ノードがノードｋである場合、ノードｋが特定される閾値によってより良くなるクラスター関連性メトリックを持っているならば、ノードは隣接するクラスターと関連付けても良い。すなわち、もし、
【００５２】
【数１２】
2005524337.tif 000014
であるならば、クラスターｍからクラスターｋへ切り替える。種々の場合に、ノードは、当業者によって理解されるように、ノードは、新たなクラスターを形成し、上述した手順を用いたクラスター・リーダーシップに対する主張することを試みるべきであることが判るかもしれない。
【００５３】
ノード失敗について、通常ノード又はクラスター・リーダー・ノード２１から３３のいずれかが失敗をするか又は停止する。通常ノード（つまり、クラスター・リーダー・ノード２１から３３以外のノード）の失敗は、近隣のノードによって検出されるように、いくつかのリンク失敗と潜在的に同一である。これらの各ノードは、あたかもリンク失敗であったかのようにこの失敗に応答し、上記の手順に従って処理を進める。この失敗は、リンク損失によって近隣ノードによって、また、周期的なＣＬＮＡＮＮメッセージのブロードキャストの損失によるクラスター内の他のノードによって、検出される。同一クラスター内のノードは、例えば、クラスター関連性メトリックが上記手順を用いて十分に良い状態であるなら連携することができる隣接クラスター・リーダーを選択する。また、１つ又はそれ以上のノードが上記クラスター・リーダー選択手順を用いるクラスター・リーダー・ノード２１から２３になるために主張しても良い。
【００５４】
上記ノード及びリンク失敗によって引き起こされた位相力学に加えて、リンク追加はまたトポロジー変化を引き起こすかもしれない。リンク及びノード失敗は、ノード１１を更に位相的に遠のかせる傾向にある。逆に言えば、リンク追加は、ノード１１を位相的に互いに近づける傾向にある。トラフィック力学が同様の効果を有する。これは、結局は一つのクラスター内のノードに隣接するクラスターによるより良いクラスター関連性メトリックを持つようにさせる効果を有する。当業者によって理解されるように、ノード１１は、そのクラスター関連性を切り替えるべきか否かを判断するために、上記定義した同様の手順を使用することができる。ノードの現在の関連性がクラスター・リーダー・ノードｍによるものであり、その最良の隣接したクラスター・リーダー・ノードがノードｋである場合、ノードｋが特定される閾値によってより良くなるクラスター関連性メトリックを持っているならば、ノードはその隣接するクラスターと関連付けしても良い。つまり、
【００５５】
【数１３】
2005524337.tif 000015
であれば、クラスターｍからクラスターｋへ切り替える。
【００５６】
更に、２つのクラスター・リーダー・ノードは、クラスター・リーダー・ノードの一つを取り除くことが望ましい結果となる程、互いに非常に近づいているかもしれない。２つのクラスター・リーダー・ノード間の経路が特定の閾値Δｐより以下であり、かつ、それらの１が両方のクラスターに対するクラスター・メンバー数の合計をサポートすることができるならば、最良のクラスター・リーダー・ノードが決定され、他ノードがそのクラスター・リーダー・ノードの役割を放棄すれば良い。クラスター・リーダー・ノードが互いに近づくように移動する際、通常ノードはクラスター・リーダー・ノードとして通常ノードにとって最良の選択となるために、自然に移動するためのクラスター関連性メトリックを使用しても良い。よって、２つのノードのうちどれを残りのクラスター・リーダー・ノードとすべきかの決定は、ノード及びそのクラスター・リーダー・メトリック毎にクラスター・メンバーの数に基づいてなされる。ノードの一つがクラスター・リーダー・ノードの役割を放棄した後、それに関連付けられた通常ノードは、クラスター・リーダー・ノード又はそれら他の隣接するクラスター・リーダー・ノードのいずれか残っているノードと関連することを選択する。
【００５７】
送り元クラスター内（図１に例示される例のクラスター２１）の特定の送り元ノード１４が送り先クラスター内（ここでは、クラスター３２）の送り先ノード１５へデータを送信する必要がある場合、送り元ノードは、ブロック４３にて、有利にクラスターレベル・ルート要求（ＣＬＲＲ）をその対応するクラスター・リーダー・ノード（ここでは、ノード２１）に送信する。送り元クラスター２１は、ブロック４４にて、クラスターレベル・ルートに対応する、送り元クラスター２１と送り先クラスター３２との間のクラスターレベル・ルートを決定する処理を開始する。すなわち、クラスターレベル・ルートは、従来のスパイン／クラスター・ルーティングのために使用されるプロアクティブ手法に相反するように、リアクティブ方法にて確立される。
【００５８】
クラスターレベル・ルートは、送り元クラスターから送り先クラスターへのルート内のクラスター１２の特定のシーケンスである。図５を更に特に参照すると、クラスターレベル・ルートの決定についてより詳細に説明する。この処理は、ブロック５１にて、クラスター・リーダー・ノード２１から３３の間に指定された通信リンク１６を決定する（又は確立する）ことによって、開始する（ブロック５０）。指定された通信リンク１６は、例示的に図１の点線で示され、概念的に、クラスター・リーダー・ノード２１から３３の間の「仮想」リンクとして考えても良い。各指定された通信リンクは、隣接するクラスター１２内のクラスター・リーダー・ノード２１から３３を接続するシングルホップ又はマルチホップを含む。すなわち、指定されたリンクの夫々が、クラスター・リーダー・ノード２１から３３ではない１つ又はそれ以上の中間ノードを含んでいても良い、或いは、そのような中間ノードがノード間に存在しなくても良い。
【００５９】
指定されたリンク１６の決定は、指定されたクラスターのためのクラスター・リーダー・ノードある、クラスター・リーダー・ノードによって、全ての隣接するクラスターに通知するために、制限されたブロードキャストを介してクラスター・リーダー・ノード・アナウンス（ＣＬＮＡＮＮ）メッセージを送信することを含んでいる。ここでは、「連接するクラスター」は、クラスターの一つの中の少なくとも１つのノード１１が他クラスター内の少なくとも１つのノードと直接接続されるような２つのクラスター１２である。
【００６０】
一旦、クラスター・リーダー・ノード２１から３３が他クラスター・リーダー・ノードが隣接するクラスター内に存在することを知ると、そのクラスター・リーダー・ノード（つまり、クラスター・リーダー・ノード間の指定された通信リンク１６）からノードレベル・ルートを取得する。これら２つのクラスター・リーダー・ノードがそれらの間の指定された通信リンク１６とそれらに関連するメトリックとを維持する。当業者によって理解されるように、このメトリックは、指定された通信リンク１６におけるホップ数と、帯域幅、利用可能性等のようなサービス品質（ＱｏＳ）パラメーターとを有している。そのようなメトリックは、好ましくは、同様に他の指定されたリンク１６に対して使用されても良い。
【００６１】
各クラスター・リーダー・ノードがその隣接するクラスター・リーダー・ノードの全てのアドレスを格納し、隣接するクラスター・リーダー・ノードの夫々への指定された通信リンク１６を保持する。一旦、指定された通信リンクが確立すると、送り元ノード１４によって要求されたクラスターレベル・ルートが送り元クラスターへ隣接するクラスターの一つへのルートではない場合、送り元クラスター・リーダー・ノード２１がクラスターレベル・ルート発見処理を開始する。
【００６２】
処理は、ブロック２２にて、指定された通信リンク１６を介して残っているクラスター・リーダー・ノード２２から３１へと、送り元クラスターのクラスター・リーダー・ノード２１からクラスター・リーダー・ノード・ルート要求（ＣＬＮＲＲ）を送信することによって開始される。更に、特に、クラスター・リーダー・ノード・ルート要求を送り元クラスター・リーダー・ノード２１から、図１に例示される例ではクラスター・ノード２３及び２５である隣接するクラスター・リーダー・ノードの夫々へ送信されることによってなされる。クラスター・リーダー・ノード２３及び２５は、クラスター・リーダー・ノード・ルート要求がクラスター・リーダー・ノード２１から３３の全てによって受信されるまで、順に、そのクラスター・リーダー・ノード・ルート要求をその隣接するクラスター・リーダー・ノードの夫々へ転送する。
【００６３】
上記手法が、全体的にブロードキャストが使用されないため、オーバーヘッド・トラフィックにおいて著しい節約を提供することが、当業者によって理解されるであろう。つまり、無線ライン１３のサブセットのみがブロードキャストのために要求される。更に通信が要求されるオーバーヘッド転送に制限されるために、この処理において拡張するリングの検索を使用することができる。更に、クラスター・リーダー・ノード・ルート要求を、１つのクラスター、クラスターのリスト、又は全クラスターへのルートを発見するために、目標とすることができる。クラスター・リーダー・ノード要求は、また、発見された各クラスターレベル・ルートの望ましさを示すことができる蓄積されたメトリックを含んでも良い。一例として、蓄積されたメトリックは、目標とされた送り先クラスター３２へのルートに沿ってクラスター・リーダー・ノード２１から３３の間の指定された通信リンク１６のためのリンク・メトリックの蓄積であっても良い。
【００６４】
クラスター・リーダー・ノード・ルート要求は、ブロック５３で、送り先クラスター・リーダー・ノード１２によって受信された場合、送り先クラスター・リーダー・ノードは、先クラスター・リーダー・ノード・ルート返信（ＣＬＲＲＥＰ）によって返信する。このクラスター・リーダー・ノード・ルート返信は、送り元クラスター・リーダー・ノード２１へクラスターレベル・ルートへ返送するために、送り先クラスター・リーダー・ノード３２によって使用される。このメッセージは、クラスター・リーダー・ノード・ルート要求が移動した配信ルート、つまり、送り元クラスター・リーダー・ノード２１と送り先クラスター・リーダー・ノード３２とに接続している指定された通信リンク１６を介して送り返される。
【００６５】
以下に更に説明されるように、クラスター・リーダー・ノード・ルートにおける情報は、配信ルート上の一連のクラスターを有するようにしても良く、また、他変形も可能である。また、特定の配信ルートのためのパス・メトリック（又は、パス・メトリックを形成するために組み合わせ可能な構成要素）が返送されても良い。もちろん、送り先クラスター・リーダー・ノード１２は、その隣接するクラスター・リーダー・ノード（すなわち、図１に例示される例におけるクラスター・リーダー・ノード２６、３１、及び３３）の一つ以上から同一のクラスター・リーダー・ノード・ルート要求を受信することは可能である。このような場合、送り元クラスター・リーダー・ノード３２は、また、これら隣接するクラスター・リーダー・ノードの夫々に関連付けられる配信ルート毎に、クラスター・リーダー・ノード・ルート返信を返送すれば良い。
【００６６】
一旦、送り元クラスター・リーダー・ノード２１は、与えられたクラスター・リーダー・ノード・ルート要求に対応するクラスター・リーダー・ノード・ルート返信の全てを収集すると、ブロック５４にて、クラスターレベル・ルートとして配信ルート間から最良のルートを選択するために、各配信ルートのパス・メトリックを使用する。もちろん、いくつかの実施例において、送り元ノード１５は、それら利用可能なルートから最良の配信ルートを選択し、クラスターレベル・ルートを決定することによって、最良の経路に沿ってクラスター・リーダー・ノード・ルート返信を単に返送する。
【００６７】
いずれの事象においても、一旦、最良のルートが選択されると、ルーティング・キャッシュ又はテーブルに格納される。一例として、クラスターレベル・ルートを選択するために使用されるパス・メトリックは、配信ルートが最小のクラスター・リーダー・ノード数を含んでいるもの（つまり、最小のクラスター１２の数を含んでいるもの）である。もちろん、上記した特定のＱｏＳメトリックのように、他メトリックも使用可能である。ＱｏＳパラメーターを用いるルートを選択するための１つの特別に有効は手法が、本譲渡人に譲渡され言及することによりその全体が盛り込まれる、２００２年４月２９日出願の代理人事件番号GCSD-1201  (51264)の「モバイル・アドホック・ネットワークのためのサービス品質（ＱｏＳ）ルーティングを決定するための方法及びシステム」を名称とする同時継続出願の米国特許出願第１０／１３４，７１５号によって開示されている。一旦、送り元クラスター・リーダー・ノード２１が最良のクラスターレベル・ルートを決定すると、ブロック５７にて、クラスターレベル・ルート・返信（ＣＬＲＲＥＰ）内で要求している送り元ノード１４へ転送される。
【００６８】
ブロック５５にて、クラスター・リーダー・ノード２１から３３の夫々が現在のアドレスを保持するためにその隣接するクラスター・リーダー・ノードに問い合わせし、例示的に方法を終了する（ブロック５６）。これは、隣接クラスター・リーダー・ノードが各新しい要求によって決定されないため、クラスター・レベル・ノード・ルート要求を転送する処理を有利に効率よく行える。この問い合わせステップは、図５に例示されるクラスターレベル・ルート発見処理内の最終ステップ（ブロック５５）として例示的に示される
一方で、このステップは、隣接するクラスター・リーダー・ノード２１から３３の間の指定された通信リンク１６が確立した後にいつでも実行しても良いし、また所望の間隔で実行しても良い。
【００６９】
一旦、クラスターレベル・ルートが確立されると、ブロック４５にて、データは、送り元ノード１４から、クラスターレベル・ルートを使用する送り先ノード１５へ転送され、図４に例示される方法が終了する（ブロック４６）。クラスターレベル・ルートを用いるデータを転送する処理を、指定された通信リンク１６が例示を明確にするために取り除かれた図２に例示されるアドホック・ネットワーク１０の概略図と、図６のフロー図とを参照しつつ説明する。この例では、送り元ノード１４によって選択されたクラスターレベル・ルートがクラスター２１（送り元）、２５、２４、２９、２６、そして３２（送り先）を含んでいると仮定する。
【００７０】
この処理は、ブロック６１にて、データが送信される先の、クラスターレベル・ルートに沿った次のクラスター内の目標ノード１７を指定することによって開始する（ブロック６０）。本発明によれば、データ転送するためにクラスター目標ノードを使用する必要はない一方、以下に更に説明するように、クラスター目標ノードは、クラスターレベル・ルートに沿って各クラスターへの入り口となる都合の良いポイントを提供し、そのことによって、それらの間のノードレベル・ルートを確立することを容易にする。
【００７１】
また特に、送り元ノード１４は、クラスターレベル・ルート（ここでは、クラスター２５）に沿った次の隣接するクラスター内のクラスター目標ノード１７ａを選択する。これは、例えば、潜在的なクラスター目標ノードを識別するために、拡張しているリング検索を用いる隣接するクラスター目標ノード発見パケットをブロードキャストすることによってなされる。このブロードキャストは、次の隣接するクラスター（ここでは、クラスター２５）に有利に制限される。つまり、ブロードキャストがアドホック・ネットワーク１０における超過したトラフィックを低減するためにある程度制限されている。
【００７２】
隣接するクラスター２５でのどのノードも、送り元ノード１４がメトリック及び潜在的なクラスター目標ノードへのルートに従って、潜在的なクラスター目標ノードのアイデンティティを種集することを許容する隣接するクラスター目標ノード発見応答パケットを送り返す。アルゴリズムは、受信した隣接するクラスター目標ノード発見応答の全てに基づいて、また、それら応答に含まれているメトリックに基づいて、隣接するクラスター２５内の最良の隣接するクラスター目標ノードを選択するために使用される。ここで再び、使用されたパス・メトリックは、クラスターレベル・ルートの選択に関して上述したように同様に、最小のホップ数、ＱｏＳパラメーターなどを含むようにしても良い。
【００７３】
隣接クラスター目標ノード２５は、好ましくは、送り元クラスター２７への距離内で可能な限り近く、また、高い能力を持つノードである。また、同様に、クラスター・リーダー・ノードが高いリンク可能性を持つならば特に有効となる、隣接するクラスターのクラスター・リーダー・ノードがクラスター目標ノードとして役割を果たす。
【００７４】
種々の手法がクラスター目標ノードを確立するために可能である。例えば、プロアクティブ手法は、各クラスター１２内の各ノード１１がそれ自身のクラスターへ隣接する各クラスターに対してクラスター目標ノードを指定するために、上記手順を使用することで、適応される。隣接するクラスター目標ノード「ｈｅｌｌｏ」メッセージは、そのようなクラスター目標ノードへのノードレベル・ルートを維持するために使用しても良い。このメッセージは、ルートがまた利用可能であることを確認するために、周期的に、各隣接するクラスター目標ノードへ転送される。クラスター目標ノードは、そのルートが未だ有効であることを示すために、同様のパケットタイプで返信する。もしルートが失敗したら、下記に更に説明するように、失敗がこの処理によって検出され、隣接クラスター目標ノードへｈｅｌｌｏメッセージを送信したノードは、他隣接クラスター目標ノードの検索を開始する。
【００７５】
隣接するクラスター目標ノードにｈｅｌｌｏメッセージを要求しない他の手法では、要求されたときにリアクティブベースでのみ隣接クラスター目標ノードを発見する。更に、これら隣接するクラスター目標ノードはそれらが使用される限りにおいてのみ維持される。ここで再び、これは、結果としてネットワーク・トラフィックを少なくし、当業者によって理解されるように、あるアプリケーションの長所となる。いずれの場合においても、個別に各ノードにその隣接するクラスター目標ノードを選択させることによって、クラスター毎に使用されるクラスター目標ノードがたった１つとならにようにし、たった一つのクラスター目標ノードを介して引き起こされるかもしれない通過トラフィックの集中を低減する。もちろん、当業者によって理解されるように、必要であれば、一つのクラスター目標ノードが幾つかの実施例にて使用されうる。
【００７６】
一旦、次のクラスター目標ノードが決定されると（図２に例示される例におけるノード１７ａ）、ブロック６２にて、次のクラスター目標ノードへのノードレベル・ルートが決定される。これは、例えば、ＤＳＲ又はＡＯＤＶのような基礎ルーティング・プロトコルを用いて次ぎのクラスター目標ノード１７ａへノードレベル・ルート要求を送信することによってなされる。これら２つのプロトコルを用いた本発明の特定の実施例を以下に呈示する。
【００７７】
一般に、ノードレベル・ルート要求は、同一のクラスター内の他ノードのために、又は、制限されたブロードキャスト（又はリング検索を拡張することによって）隣接するクラスター内のクラスター目標ノードのためにルートを発見するために使用される。送り先ノード１５は送り元ノード１４と同様のクラスター内にある。この場合、クラスターレベル・ルートが送り元ノード・クラスターの外側で送り先ノードに到達するためだけに使用されるように、ノードレベル・ルートのみが使用される。この場合は、また、基礎ルーティング・プロトコルとして、ＤＳＲの議論と関連して以下に更に説明する。
【００７８】
一旦、クラスターレベル・ルートに沿って次のクラスター目標ノードへのノードレベル・ルートが確立されると、データは、ブロック６３にて、ノードレベル・ルートを介して、送り元ノード１４から次のクラスター目標ノード１７ａへ転送される。ここで再び、このデータ転送は、使用されている根底にある基礎ルーティング・プロトコルによって管理される。一般に、データは、ノードレベル転送、クラスターレベル・ルート、又はそれら両方に適した情報を含む特命データ・パケット又はヘッダーに従って転送される。特命データ・パケットの使用について、ＤＳＲ及びＡＯＤＶが基礎ルーティング・プロトコルとして使用される特定の場合において以下に説明する。
【００７９】
ブロック６１から６３で例示される上記ステップは、ブロック６４にて、データが送り先目標ノード１７ｅに転送されるまで、クラスターレベル・ルートと対応するノードレベル・ルートに沿って各次のクラスター目標ノード１７ｂ、１７ｃ、１７ｄ、１７ｅを決定するために繰り返される。一旦、データが送り先クラスター目標ノード１７ｅに到達すると、送り先クラスター目標ノードから送り先ノード１５へのノードレベル・ルートが決定され（ブロック６５）、上述したように、このノードレベル・ルートを介してその間をデータが転送される（ブロック６６）、そして、ブロック６７にて、方法が終了する。再び、これらステップは、例えば、ＤＳＲ又はＡＯＤＶのような基礎ルーティング・プロトコルに従って実行される。
【００８０】
図２で分かるように、クラスターレベル・ルートに沿った種々のノードレベル・ルートがクラスター・リーダー・ノードを含んだり、含まなかったりする。幾つかの実施例において、可能なところで、クラスター・リーダー・ノードを含まないようにノードレベル・ルートを定義することは、特に有利であり、このことがクラスター・リーダー・ノードでの過剰なトラフィックの緩和を促進する。ノードレベル・ルート発見処理は、ルートがクラスター・リーダー・ノードを有するか否かを示す潜在的ルート毎にメトリックを使用することを含んでおり、例えば、ルートを要求するノードは、当業者によって理解されるように、その選択処理においてこのメトリックを使用しても良い。
【００８１】
ＤＳＲが基礎ルーティング・プロトコルとして使用される場合を図７を参照しつつ説明する。基礎ＤＳＲプロトコルは、図７で再現される図６のブロック６１及び６２を参照しつつ説明したステップを実行するために使用されるルート要求及びルート返信のようなメッセージタイプを有している。本発明に従ったノードレベル・ルートのためのルート発見処理は、非常に従来のＤＳＲ手法のルート発見処理と似ている。つまり、制御されるブロードキャスト検索は、ネットワーク１０全体よりもむしろ、現在のクラスター内のみを検索するため、或いは、隣接するクラスター内のクラスター目標ノード（又はクラスター・リーダー・ノード）へのルートを検索するためである。標準ＤＳＲパケットタイプは、最小ホップカウント以外の経路選択基準を使用することが所望される場合、簡潔に上述したように、当業者によって理解されるように、メトリックタイプ及びメトリック値のためのフィールドを備えるように変更されても良い。
【００８２】
一方、発明に係るクラスターレベル・ルート発見処理は、従来のＤＳＲ手法から幾分変化している。すなわち、この処理は、制限された全体的な検索を含んでいる。これは、全ての隣接クラスター・リーダー・ノード２１から３３の間の指定された通信リンク１６の存在（対応するノードレベル送り元ルート）のためである。言い換えると、ルート発見パケットは、上述したように、ネットワーク１０内の全リンク１３よりむしろ、指定された通信リンク１６のみを行き来する。クラスター・リーダー・ノードから転送されたクラスター・リーダー・ノード・ルート要求は、好ましくは、メッセージが転送されている次のクラスター・リーダー・ノードへのノードレベル送り元ルートを含んでいる。再び、全ての隣接するクラスター内のクラスター・リーダー・ノードへのこのやり方で転送される。
【００８３】
上述したように、基礎プロトコルに従ったデータ転送は、通常、特命データ・パケットのある形式又はヘッダーがデータに伴なって生成される。発明に従ってＤＳＲを用いる場合、ブロック７０’の開始で、送り元ノード１４によって生成された特命データ・パケット（ブロック７１’）が、好ましくは、送り先ノードのアドレス、次のクラスター目標ノード１７ａのアドレス、及びクラスターレベル・ルートを含む。当業者によって理解されるように、次のクラスター目標とクラスターレベル・ルーティングのフィールドは、本発明へ適用のための随意的なパケットタイプとして定義されても良い。
【００８４】
このデータは、ブロック６３で、次のクラスター目標ノード１７ａへのノードレベル・ルートに沿った特命データ・パケットに基づいて転送される。次のクラスター目標ノード１７ａ’は、ブロック６１及びブロック６２（図６）で例示されるステップを繰り返し、従って、特命データ・パケットを更新する。更に特に、特命データ・パケットは、新しいクラスター目標ノードとそれへの新しいノードレベル・ルートとを含むために、クラスターレベル・ルートに沿って、各クラスター目標ノード１７ａ、１７ｂ、１７ｃ、１７ｄで更新される。
【００８５】
この処理は、送り先クラスター目標ノード１７ｅに到達するまで継続する（ブロック６４’）。この送り先クラスター・ノード１７ｅは、特命データ・パケット内のクラスターレベル・ルートによって、データが送り先クラスター３２に到達したことを判断する。そして、送り先ノード１５へのノードレベル・ルートが決定される（ブロック６５’）。特命データ・パケットは、送り先ノード１５へのルートは、クラスター間ルートであるため、クラスターレベル・ルートと次のクラスター目標ノートとに対してヌル値を含むように更新される。データは、上述されるように、ブロック６６’で送り先ノード１５へ転送される。
【００８６】
送り元ノード１４と送り先ノード１５は、場合によっては、同一のクラスター内に位置することは、上述した通りである。この場合、送り元ノード１４は、単に、特命データ・パケット内のクラスター目標ノードのアドレスとクラスターレベル・ルートを所定値と等しくなるように設定する。例えば、これは、送り先クラスター目標ノード１７ｅに対して上述したようにヌル値であっても良い。従来のＤＳＲルーティング手順は、よって、データを転送するために使用される。
【００８７】
再び、送り元ノード１４は、送り先ノード１５が同一のクラスター内にあると既に分かっているような場合に、クラスターレベル・ルートを要求する必要がない。これは、データがそこへ送信された場合であり、その記録が送り元ノード１４のメモリー又はキャッシュに格納されている。
【００８８】
その際、上記ステップにて決定された種々のルーティング情報は、ブロック７３’にて、有利に、以降のルーティング動作のために使用されるように、１つ又はそれ以上のキャッシュ内に格納され、処理を終了する（ブロック７４’）。結果として、そのようなルーティング情報がタイムアウト或いは破棄された場合、クラスター／ノードレベル発見処理の全体又は一部を完了することなく再び、使用しても良い。
【００８９】
一例として、以下のタイプのキャッシュが保持される。クラスターレベル・ルート・キャッシュは、ルートが現在保持されている送り先クラスターへのクラスターレベル・ルートをキャッシュする。このキャッシュは、例えば、クラスター・リーダー・ノード２１から３３ごとに保持され、要求に応じて分かっているクラスターレベル・送り元ルートを提供するために、送り先クラスターによって索引が付けられている。
【００９０】
他のキャッシュが、ルートが現在保持されている、同一のクラスター内又は隣接するクラスター内（クラスター目標ノード１７のような）のいかなるノードへのノードレベル・ルートをキャッシュするノードレベル・ルート・キャッシュを含む。このキャッシュが個々のノード１１毎に保持され、送り先ノード・アドレスによって索引が付けられており、各ノード１１に利用可能なときに分かっているノードレベル送り元ルートを提供する。
【００９１】
また、各ノード１１で保持されている階層的ルート・キャッシュは、ルートが現在保持されているいかなる送り先ノードへの階層的ルートをキャッシュする。このキャッシュは、また、送り先ノード・アドレスによって索引が付けられており、キャッシュは、送り元ルート上の最初のクラスターにおける、送り先クラスターへのクラスターレベル送り元ルートとクラスター目標ノード（例示される例において、ノード１７ａ）へのノードレベル送り元ルートとを含む階層的ルートを返す。
【００９２】
有用であることを立証する他のキャッシュのタイプは、送り先ノード・アドレスによって索引付けされるテーブルであって、隣接クラスター目標ノード・キャッシュに加えて、ノードが現在メンバーであるクラスターのアドレスを返すクラスター・キャッシュを含む。このキャッシュは、隣接するクラスター・アドレスによって索引付けされ、そのクラスターのために隣接クラスター・ノード・アドレスを返す。
【００９３】
アドホック・ネットワークの動的な性質が与えられると、アドレスの種々のタイプが個々のノード及びクラスターに対して使用される。特定のアプリケーションに使用されるアドレッシングの特定のタイプに依存して、種々の他の変更が与えられた基礎プロトコルのために必要となる。例えば、固定アドレスが使用される場合、プロトコルは、当業者によって理解されるように、ノード変更クラスターとして現在のクラスター・メンバーシップを配信するために含まれるようにすれば良い。そのようなプロトコルが使用されない場合、クラスター・メンバーシップは、例えば、ＣＬＮＲＲルート発見処理を使用するリアクティブ方法にて決定することができる。一方、アドレスが、ノードが位置する場所で、特定のクラスター、階層的レベル（更に以下に明確にされる）などに基づいて動的に割り当てられる場合、当業者によって理解されるように、ダイナミック・ネーム・サーバーが、送り元ノードが固定ノード名に対する現在のアドレスを決定することを許容するために、随意的に設置しても良い。
【００９４】
ＡＯＤＶが基礎ルーティング・プロトコルとして使用される別の実施例について、図８のフロー図を参照しつつ説明する。ＡＯＤＶプロトコルによれば、ノードレベル・ルートは、上述したＤＳＲの場合のように、ルート要求とルート返信を用いて確立される。また、ノードレベル・ルートと対応するクラスターレベル・ルートが決定される方法は、ＤＳＲでの方法とは幾分異なっている。
【００９５】
また特に、図８のブロック８１で開始し、クラスター・リーダー・ノード・ルート要求が、指定された通信リンク１６を介して、当業者によって知られている従来のＡＯＤＶを用いて送信される。一般に、ＡＯＤＶプロトコルによれば、ルート要求が送信されると、ルートに沿って各ノード１１は前のノードのアドレスを格納する。ルート要求は、前のノードから受信し、次のノードへ転送される。この方法において、ルート返信が最終的にこのルートに沿って送り戻される場合、各ノード１１に格納されたアドレスが戻りルートに沿って次のホップの位置を提供する。更に、ルート返信が戻りルートに沿ってあるノード１１から次ノードへ転送されるように、各ノードは、ルート返信をそこに転送したノードのアドレスを格納する。よって、これらアドレスは、データがルートに沿って転送されると、ルートに沿って次のホップの位置を提供する。
【００９６】
本発明によれば、上述した処理は、ブロック８１から８２にて、上記参照されたクラスター・リーダー・ノード・ルート要求とクラスター・リーダー・ノード・ルート返信とを用いて、クラスターレベル・ルートを決定するためにクラスターレベルで開始する。更に、この処理は、同様に、上述したようにノードレベル・ルート要求及びノードレベル・ルート返信を用いて、ブロック８３から８４にて、クラスターレベル・ルートに沿ってノードレベル・ルートを決定するために、ノードレベルで実装される。ここで再び、クラスター目標ノードは、必要に応じて上述したように使用され、クラスター目標ノードを、当業者によって理解されるように、ＡＯＤＶの標準仕組みによって上述したように決定しても良い。
【００９７】
ブロック８５で、特命データ・パケットは、各ノードレベル・ルートの開始で（つまり、送り元ノード１４又はクラスター目標ノード１７のいずれかによって）、生成され、データは、特命データ・パケットに基づいて定義される種々のノードレベル・ルートに沿って転送される。ＡＯＤＶプロトコルに従って、ノードレベル・ルートのホップは、ルート上で種々のノード１１に既に格納されているので、特命データ・パケットは、通常、送り先ノード１５のアドレスのみ要求する。
【００９８】
特命データ・パケットは、クラスターレベル・ルートに沿って次のクラスターの位置を持っていないため、各クラスター目標ノード１７が次ぎのクラスター・アドレスについて対応するクラスター・リーダー・ノードに問い合わせる。よって、クラスター・リーダー・ノードが、次ぎのクラスター・アドレスに基づいて次ぎのクラスター目標ノードを決定する。もちろん、当業者によって理解されるように、クラスター・リーダー・ノードに問い合わせる必要がないように、他の手法が、特命データ・パケット内に含めるものとして定義された随意的なデータ・パケット内で使用されても良い。
【００９９】
データは、ブロック８６にて、送り先クラスター目標ノード１７ｅに到達するまで、種々のノードレベル・ルートに沿って転送される。ブロック８７にて、送り先ノード１５へのノードレベル・ルートは、再び標準ＡＯＤＶ技術、及びそこへ転送されたデータを用いて定義され、よって、処理が終了する（ブロック８８）。
【０１００】
種々テーブルが、本発明に従ってＡＯＤＶを実装するために、必須のルーティング情報を格納するために使用される。特に、送り先クラスター・アドレスによって索引付けされるクラスターレベル・ルート・テーブルは、ルートが保持されている送り先クラスターへの経路上の次の隣接クラスターを送り返す。更に、送り先ノード・アドレスによって再び索引付けされるノードレベル・ルート・テーブルは、ルートが保持されている同様のクラスター内（クラスター目標ノード１７のような）又は隣接するクラスター内のノードへの経路上での次のノード１１のアドレスを送り返す。また、送り先ノード・アドレスによって索引付けられたクラスター・キャッシュが、送り先ノードが現在メンバーであるクラスターのアドレスを送り返す。隣接するクラスター・アドレスによって索引付けされる隣接するクラスター目標ノード・キャッシュは、隣接するクラスターのために隣接するクラスター目標ノード・アドレスを送り返す。加えて、送り先ノード・アドレスによって索引付けされる階層的ルート・テーブルは、ルートが保持されている、ネットワーク全体におけるいかなる送り先ノードへの経路上の次のノードのアドレスを送り返す。上記同様に、上記テーブルで保持されるデータは、新しいクラスターレベル又はノードレベル情報が生成される毎に格納しても良い。よって、この情報は、今後のルートに対して利用可能とり、発見要求及び返信メッセージが回避されるため、トラフィックの軽減が促進される。もちろん、この情報は、例えば、古くなった情報の記憶領域を削減するために、ある期間の後破棄しても良い。
【０１０１】
無線モバイル・アドホック・ネットワークの動的な性質のため、対処しなければならない共通の問題は、ネットワーク１０のログオフしているノード１１、無線通信リンク１６内の切断などによるルート失敗の問題である。通常、基礎ルーティング・プロトコルは、ルート認識及び回復に対処するための仕組みを有している。ＤＳＲ及びＡＯＤＶプロトコルを用いたルート回復に特に重点を置いて、本発明の文脈におけるルート回復について、図９のフロー図に関して更に説明する。図９の目的において、クラスターレベル及びノードレベル・ルート送り先処理（図５及び図６）が以前に実行されていると仮定する。
【０１０２】
従って、ブロック９０で開始して、クラスターレベル・ルート失敗が、ブロック９１にて、クラスターレベル・ルートに従って隣接するクラスター間で発生した場合、上述したように、クラスターレベル及びノードレベル・ルート発見処理を再び開始する、クラスターレベル・ルート・エラー・メッセージが送り元ノード１４へ送信される（ブロック９２）。この特定ルート要求がとっている形式は、使用されている基礎ルーティング・プロトコルに依存する。
【０１０３】
例えば、使用されている基礎プロトコルはＡＯＤＶである場合、クラスター・リーダー・ノードの夫々が、送り先クラスター・リーダー・ノード３２へのクラスターレベル・ルートに沿って、各「ダウンストリーム（下流の）」クラスター・リーダー・ノードのアドレスを格納することが呼び起こされる。従って、クラスターレベル・ルート・エラー・メッセージがクラスターレベル・ルートへの「アップストリーム（上流の）」のクラスターレベル・ルートへ戻っていくように、ブロック９３にて、クラスターレベル・ルートがもはや有効ではないため、エラー・メッセージを受信するクラスター・リーダー・ノードの夫々が、その対応するキャッシュから次のホップ・アドレスを削除する。
【０１０４】
ＤＳＲが基礎プロトコルとして使用されている場合には、クラスターレベル・ルート・エラー・メッセージが、隣接するクラスター全てにおいて、クラスター・リーダー・ノードとともに、接続の損失を発見するクラスター・リーダー・ノードからそのクラスター内の他ノード全てへブロードキャストされる。このブロードキャストは、クラスター内の他ノード全てと同様に、他クラスター内のノードによって隣接するクラスター目標ノード１７として選択されている全ノードに到達する。もはや隣接しないクラスターを介して転送するためにパケットを受信するクラスター目標ノード１７は、クラスターレベルでルートが失敗したことを通知するデータ・パケットの元の送信者へクラスターレベル・ルート・エラー・メッセージを転送する。隣接するクラスターの全てにおいてクラスター・リーダー・ノードへブロードキャストしたクラスターレベル・ルート・エラー・メッセージは、また、必要に応じて、ネットワーク１０内の全クラスター・リーダー・ノードへブロードキャストされる。それによって、クラスターレベル・ルートが古くなったことを通知する。これは、クラスター・リーダー・ノードの全てに、対応するキャッシュに以前に格納された情報に単に返信するのではなくて、新しいクラスターレベル・ルート要求を受信するためのルート発見クエリーの新たなラウンドを開始することを促す。
【０１０５】
一方で、ブロック９４にて、ノードレベル・ルート失敗が、ノードレベル・ルート内の隣接するノード間で発生すると、ブロック９５にて、新しいノードレベル・ルートが、使用されている基礎プロトコルに従って決定され、よって、処理を終了する（ブロック９６）。また特に、送り先ノード１５又は隣接するクラスター目標ノード１７へ使用されたノードレベル・ルートに対して、ルート・エラー・メッセージを使用する基礎ルーティング・プロトコルのために確立された基礎手順は、当業者によって理解されるように、経路失敗の適切なノードの通知を蓄積する。
【０１０６】
本発明の上述した方法は、また、図３に例示されるように、任意の階層的レベル数へと有効に拡張しても良い。図３において、図１及び図２に例示される模範的なアドホック・ネットワーク１０は、階層の４つのレベルへと拡張されている。階層の第一レベルは、前の例からネットワークレベル（つまり、ノード１１）である。第二レベルは、クラスター１２を含む階層によって構成されている。
【０１０７】
階層の第三レベル１７は、仮想ノード及び仮想リンクから構成される。第三レベルでの各仮想ノードは、第二レベルでのクラスター１２全体を示している。接近して接続される、第三レベル１７の仮想ノードは第三レベル・クラスターへとグループ化され、これら仮想ノードの一つは、第三レベルの仮想クラスター・リーダー・ノードとして選択される。第三レベル１７の仮想クラスター・リーダー・ノードとして選択された物理ノードは、第二及び第三レベル・クラスターの両方に対してクラスター・リーダー・ノードを実行する第二レベル・クラスターからの実際のクラスター・リーダー・ノードであるかもしれない。
【０１０８】
図１０に斜線で示される第三レベル１７の仮想リンクは、第二レベルで示される隣接するクラスター内のクラスター・リーダー・ノード間のマルチホップ仮想リンクである。例示的に斜線で示されるように、第三レベル１７のクラスター・リーダー・ノード間の仮想リンクが確立される。当業者によって理解されるように、この階層的組織化処理は、いかなるレベル数に対しても継続することができる。
【０１０９】
各第三レベル１７のクラスターが第四レベルにおける仮想ノードとなる、第四レベル１８のクラスターは、また、図３に例示的に示される。第四レベル１８で示される仮想リンクは、第三レベル１７のクラスター・リーダー・ノード仮想リンクである。第四レベル１８のクラスター・リーダー・ノードとして選択された物理ノードは、第二、第三、及び第四レベルのクラスターに対するクラスター・リーダー・ノード機能を実行する、第三レベル１７のクラスターから実際のクラスター・リーダー・ノードである。当業者によって理解されるように、ネットワークがより広ければ、階層的組織はクラスターへさえも拡張することができる。
【０１１０】
上記メッセージの複数が、任意の階層的レベル数での処理を増大させるかもしれない。例えば、クラスター・リーダー・ノード・ルート要求のメッセージタイプは、階層的クラスターレベル毎に異なるタイプである。このメッセージは、送り先クラスター・リーダー・ノード全てに対してブロードキャストされるが、隣接するクラスター・リーダー・ノードに接続する仮想リンクへユニキャストのみを含む、適切な階層的レベルでのクラスター・リーダー・ノード全てに接続する仮想リンクへ送信される。更に、クラスター・リーダー・ノード・ルート要求のように、クラスター・リーダー・ノード・ルート返信メッセージが、当業者によって理解されるように、階層的クラスターレベル毎に異なるタイプを同様に持っている。
【０１１１】
更に、クラスターレベル・ルート要求は、階層的クラスターレベル毎に異なるタイプを持っても良い。また特に、特定のレベルで、メッセージはそのレベルのためにＡＬＮに送信される。更に、クラスターレベル・ルート返信に対して、送り元ノードは、そのクラスター・リーダー・ノードへの短い距離へ送信される処理によって、送り先へのクラスターレベル・ルート（要求の特定の階層的レベル）を取得することができる。
【０１１２】
図３で分かるように、第四レベル１８は、送り元クラスターのクラスター・リーダー・ノード２１から送り先クラスターのクラスター・リーダー・ノード３２へと高いレベルのルートを決定するための都合よい基準を有利に提供する一つのクラスターを有している。また特に、この一つのクラスターは、送り元及び送り先のリーダー・ノード・クラスター２１及び３２を含むため、高いレベルのルートは、上記に概要説明した種々のステップを用いてそれらの間で決定される。高いレベルのルートは、順に、第二階層レベルのためにクラスターレベル・ルートを決定するために使用される。つまり、クラスターレベル・ルートは、少なくとも、高いレベルのルートに沿って対応するクラスター・リーダー・ノード、ここでは、クラスター・リーダー・ノード２１、２４及び３２を持つクラスターを含んでいる。
【図面の簡単な説明】
【０１１３】
【図１】本発明に係るアドホック・ネットワークの概略図である。
【図２】クラスターレベル・ルートに沿ってノードレベル・ルートを例示する図１のアドホック・ネットワークの概略図である。
【図３】複数の階層的レベルを例示する図１のアドホック・ネットワークの概略図である。
【図４】本発明に係るアドホック・ネットワーク内にてデータを送信するための方法を例示するフロー図である。
【図５】更に詳細に図５のクラスターレベル・ルート発見処理を例示するフロー図である。
【図６】更に詳細に図５のノードレベル・ルート発見処理及びデータ転送を例示するフロー図である。
【図７】ダイナミック・ソース・ルーティング（ＤＳＲ）を使用する図５の方法の他の実施例を例示するフロー図である。
【図８】アドホック・オンデマンド・ベクトル（ＡＯＤＶ）を使用する本発明の更に他の実施例を例示するフロー図である。
【図９】本発明に係るルート・エラー・リカバリーのための方法を例示するフロー図である。
【図１０】本発明に従って送り先のクラスター及びクラスター・リーダー・ノードのグループ化を例示する概略図である。
【図１】
2005524337.tif 000016
【図２】
2005524337.tif 000017
【図３】
2005524337.tif 000018
【図４】
2005524337.tif 000019
【図５】
2005524337.tif 000020
【図６】
2005524337.tif 000021
【図７】
2005524337.tif 000022
【図８】
2005524337.tif 000023
【図９】
2005524337.tif 000024
【図１０】
2005524337.tif 000025
【手続補正書】
【提出日】平成16年5月26日(2004.5.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノードのクラスターにグループ化された複数のノードと該複数のノードと接続する複数の無線リンクとを有し、各クラスターは指定されたクラスター・リーダー・ノードを持っているモバイル・アドホック・ネットワークにおいてデータを送信する方法であって、
送り元クラスターの送り元ノードから送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル要求を送信し、
上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、複数の上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定し、
上記クラスターレベル・ルートに沿ってクラスター内の少なくとも１つのクラスター目標ノードを指定し、
上記送り元ノードから上記少なくとも１つのクラスター目標ノードへの第一のノードレベル・ルートを決定し、
上記送り元ノードのアドレスと、少なくとも１つのクラスター目標ノードのアドレスと、上記第一のノードレベル・ルートと、上記クラスターレベル・ルートとを有する上記送り元ノードで特命データ・パケットを生成し、
上記特命データ・パケットに基づいて、少なくとも１つのクラスター目標ノードから上記送り先ノードへの第二のノードレベル・ルートを決定し、上記特命データ・パケットに基づいて、上記第一及び第二のノードレベル・ルートを介して、上記送り元ノードから上記送り先ノードへデータを転送する方法。
【請求項２】
上記少なくとも１つのクラスター目標ノードは、上記クラスターレベル・ルートに沿ってクラスター毎に対応するクラスター目標ノードを有し、上記第一のノードレベル・ルートを決定することは、上記クラスターレベル・ルートに沿って次の隣接するクラスターに対して上記送り元ノードからクラスター目標ノードへのノードレベル・ルートを決定し、上記第二のノードレベル・ルートを決定することは、上記クラスターレベル・ルートに沿って各連続するクラスター目標ノード間のノードレベル・ルートを決定することを有する請求項１記載の方法。
【請求項３】
上記特命データ・パケットは、上記次のクラスター目標ノードのアドレスとそのノードへの上記ノードレベル・ルートを有するため、上記クラスターレベル・ルートに沿って各クラスター目標ノードで特命データ・パケットを更新することを有する請求項１記載の方法。
【請求項４】
上記送り元クラスターと上記送り先クラスターとが同じクラスターである場合、上記少なくとも１つのクラスター目標ノードの上記アドレスと上記クラスターレベル・ルートとが所定値と等しい請求項１記載の方法。
【請求項５】
上記クラスターレベル・ルートと、上記少なくとも１つのクラスター目標ノードの上記アドレスと、上記第一のノードレベル・ルートとを有する上記送り元ノードへの階層的な送り元ルートを送り元ノードにて格納することを更に有する請求項１記載の方法。
【請求項６】
少なくとも上記送り元クラスター・リーダー・ノードと上記送り先クラスター・リーダー・ノードとを有する複数の上記クラスター・リーダー・ノードをリーダー・ノード・クラスターへとグループ化し、上記リーダー・ノード・クラスター内の上記送り元クラスターの上記クラスター・リーダー・ノードから上記送り先クラスターの上記クラスター・リーダー・ノードへの高いレベルのルートを決定することを更に有し、上記クラスターレベル・ルートは、少なくとも、高いレベルのルートに沿って対応するクラスター・リーダー・ノードを持っている上記クラスターを有する請求項１記載の方法。
【請求項７】
上記クラスターレベル・ルートを決定することは、
上記クラスター・リーダー・ノード間の指定された通信リンクを決定し、
上記指定された通信リンクを介して、上記送り元クラスターのクラスター・リーダー・ノードから残りのクラスー・リーダーへとクラスター・リーダー・ノード・ルート要求を送信し、
上記クラスター・リーダー・ノード・ルート要求の配信に沿って、上記送り先クラスターのクラスター・リーダー・ノードから上記送り元クラスターの上記クラスター・リーダー・ノードへとクラスター・リーダー・ノード・ルート返信を送り返す請求項１記載の方法。
【請求項８】
遅延、リンク能力、及び利用可能性のうち少なくとも１つに基づいて、配信ルートを決定することを更に有する請求項７記載の方法。
【請求項９】
各クラスター・ノードは指定されたクラスター・リーダー・ノードを持っている、クラスター・ノードへグループ化された複数のノードと、
上記複数のノードを接続する複数の無線リンクとを有し、
上記複数のノードは、
送り元クラスターの送り元ノードから上記送り元クラスターのクラスター・リーダー・ノードへとクラスターレベル・ルート要求を送信し、
上記送り元クラスターと、上記クラスターレベル・ルート要求に応じた送り先ノードを有し、上記クラスター・リーダー・ノードを使用する送り先クラスターとの間のクラスターレベル・ルートを決定し、
上記クラスターレベル・ルートに沿って、クラスター内の少なくとも１つのクラスター目標ノードを指定し、
上記送り元ノードから、上記少なくとも１つのクラスター目標ノードへの第一のノードレベル・ルートを決定し、
上記送り先ノードのアドレスと、上記少なくとも１つ以上のクラスター目標ノードのアドレスと、上記第一のノードレベル・ルートと、上記クラスターレベル・ルートとを有する上記送り元ノードで特命データ・パケットを生成し、
上記特命データ・パケットに基づいて、少なくとも１つのクラスター目標ノードから上記送り先ノードへの第二のノードレベル・ルートを決定し、上記特命データ・パケットに基づいて、上記第一及び第二のノードレベル・ルートを介して、上記送り元ノードから上記送り先ノードへデータを転送することを有する無線アドホック・ネットワーク。
【請求項１０】
上記少なくとも１つのクラスター目標ノードは、上記クラスターレベル・ルートに沿ってクラスター毎に対応するクラスター目標ノードを有し、上記第一の上記ノードレベル・ルートは、上記クラスターレベル・ルートに沿って次の隣接するクラスターに対して上記送り元ノードからクラスター目標ノードへのノードレベル・ルートと、上記クラスターレベル・ルートに沿って各クラスター目標ノードから次のクラスター目標ノードへのノードレベル・ルートとを有し、上記第二のノードレベル・ルートは、上記クラスターレベル・ルートに沿って連続するクラスター目標ノード間のノードレベル・ルートを有する請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１１】
上記送り先ノードの上記アドレスが、上記送り元クラスターに対して、クラスター・リーダー・ノードで上記対応するクラスター・リーダー・ノードのアドレスに従って格納される請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１２】
上記送り元ノードで、上記クラスターレベル・ルートと、上記少なくとも１つのクラスター目標ノードの上記アドレスと、上記第一のノードレベル・ルートとを有するように、上記送り先ノードへの階層的な送り元ルートが格納される請求項９記載のモバイル・アドホック・ネットワーク。
【請求項１３】
上記クラスター・リーダー・ノードと接続する指定された通信リンクを更に有し、上記クラスターレベル・ルートは、上記指定された通信リンクを介して、上記送り元クラスターの上記クラスター・リーダー・ノードから上記残りのクラスター・リーダーへとクラスター・リーダー・ノード・ルート要求を送信し、上記クラスター・リーダー・ノード・ルート要求の配信に沿って、上記送り先クラスターの上記クラスター・リーダー・ノードから上記送り元クラスターの上記クラスター・リーダー・ノードへとクラスター・リーダー・ノード・ルート返信を送り戻すことによって、決定される請求項９記載のモバイル・アドホック・ネットワーク。
【国際調査報告】
2005524337.tif 000026