(57)【要約】経路距離係数（ｐａｔｈ  ｄｉｓｔａｎｃｅ  ｆａｃｔｏｒ；ＰＤＦ）を用いるメッシュ状ネットワークにおける無線周波数管理（ｒａｄｉｏ  ｆｒｅｑｕｅｎｃｙ  ｍａｎａｇｅｍｅｎｔ；ＲＦＭ）のための方法およびシステムが開示される。一実施形態に従った、コンピュータ実装型の方法は、第一のメッシュルータとポータルとの間の経路距離係数（ＰＤＦ）を計算することを包含する。フレームが第二のメッシュルータに送信され、該フレームは、経路距離係数を含んでいる。
2010519833.tif 000002
【特許請求の範囲】
【請求項１】
第一のメッシュルータとポータルとの間の経路距離係数（ＰＤＦ）を計算することと、
フレームを第二のメッシュルータに送信することであって、該フレームは、該経路距離係数を含む、ことと
を包含する、コンピュータ実装型の方法。
【請求項２】
前記フレームは、ビーコンである、請求項１に記載のコンピュータ実装型の方法。
【請求項３】
前記フレームは、プローブ応答管理フレームである、請求項１に記載のコンピュータ実装型の方法。
【請求項４】
前記第一のメッシュルータが電力を供給されるときに、前記ＰＤＦを無限大の距離を表す値に初期化することをさらに包含する、請求項１に記載のコンピュータ実装型の方法。
【請求項５】
前記第一のメッシュルータが前記ポータルであるときに、前記ＰＤＦを所定の値に設定することをさらに包含する、請求項１に記載のコンピュータ実装型の方法。
【請求項６】
第一のメッシュルータにおいてビーコンを受信することであって、該ビーコンは、第二のメッシュルータの第二のＰＤＦを含む、ことと、
該第二のＰＤＦを用いて該第一のメッシュルータの第一のＰＤＦを計算することと
を包含する、コンピュータ実装型の方法。
【請求項７】
前記第二のメッシュルータが前記第一のメッシュルータの隣のリスト上に存在するか否かを決定することと、
該第二のメッシュルータが該隣のリスト上にない場合には、該第一のメッシュルータのトポロジデータベースを更新することと
をさらに包含する、請求項６に記載のコンピュータ実装型の方法。
【請求項８】
前記第二のメッシュルータへのリンクを確立することをさらに包含する、請求項７に記載のコンピュータ実装型の方法。
【請求項９】
前記第一のＰＤＦは、前記第二のＰＤＦを含む複数のＰＤＦ値の最小のＰＤＦ値である、請求項６に記載のコンピュータ実装型の方法。
【請求項１０】
前記トポロジデータベースにおいてループなしのトポロジを生成するために、拡散更新アルゴリズムを用いることをさらに包含する、請求項７に記載のコンピュータ実装型の方法。
【請求項１１】
その上に複数の命令を格納するようにされたコンピュータ読み取り可能な媒体であって、該複数の命令は、コンピュータによって実行されるときに、該コンピュータに、
第一のメッシュルータとポータルとの間の経路距離係数（ＰＤＦ）を計算することと、
フレームを第二のメッシュルータに送信することであって、該フレームは、該経路距離係数を含む、ことと
を実行させる、コンピュータ読み取り可能な媒体。
【請求項１２】
前記フレームは、ビーコンである、請求項１１に記載のコンピュータ読み取り可能な媒体。
【請求項１３】
前記フレームは、プローブ応答管理フレームである、請求項１１に記載のコンピュータ読み取り可能な媒体。
【請求項１４】
その上に追加の命令を格納するようにされた請求項１１に記載のコンピュータ読み取り可能な媒体であって、該追加の命令は、コンピュータによって実行されるときに、該コンピュータに、
前記第一のメッシュルータが電力を供給されるときに、前記ＰＤＦを無限大の距離を表す値に初期化すること
をさらに実行させる、請求項１１に記載のコンピュータ読み取り可能な媒体。
【請求項１５】
その上に追加の命令を格納するようにされた請求項１１に記載のコンピュータ読み取り可能な媒体であって、該追加の命令は、コンピュータによって実行されるときに、該コンピュータに、
前記第一のメッシュルータが前記ポータルであるときに、前記ＰＤＦを所定の値に設定すること
をさらに実行させる、請求項１１に記載のコンピュータ読み取り可能な媒体。
【請求項１６】
その上に複数の命令を格納するようにされたコンピュータ読み取り可能な媒体であって、該複数の命令は、コンピュータによって実行されるときに、該コンピュータに、
第一のメッシュルータにおいてビーコンを受信することであって、該ビーコンは、第二のメッシュルータの第二のＰＤＦを含む、ことと、
該第二のＰＤＦを用いて該第一のメッシュルータの第一のＰＤＦを計算することと
を実行させる、コンピュータ読み取り可能な媒体。
【請求項１７】
その上に追加の命令を格納するようにされた請求項１６に記載のコンピュータ読み取り可能な媒体であって、該追加の命令は、コンピュータによって実行されるときに、該コンピュータに、
前記第二のメッシュルータが前記第一のメッシュルータの隣のリスト上に存在するか否かを決定することと、
該第二のメッシュルータが該隣のリスト上にない場合には、該第一のメッシュルータのトポロジデータベースを更新することと
をさらに実行させる、請求項１６に記載のコンピュータ読み取り可能な媒体。
【請求項１８】
その上に追加の命令を格納するようにされた請求項１７に記載のコンピュータ読み取り可能な媒体であって、該追加の命令は、コンピュータによって実行されるときに、該コンピュータに、
前記第二のメッシュルータへのリンクを確立すること
をさらに実行させる、請求項１７に記載のコンピュータ読み取り可能な媒体。
【請求項１９】
前記第一のＰＤＦは、前記第二のＰＤＦを含む複数のＰＤＦ値の最小のＰＤＦ値である、請求項１６に記載のコンピュータ読み取り可能な媒体。
【請求項２０】
その上に追加の命令を格納するようにされた請求項１７に記載のコンピュータ読み取り可能な媒体であって、該追加の命令は、コンピュータによって実行されるときに、該コンピュータに、
前記トポロジデータベースにおいてループなしのトポロジを生成するために、拡散更新アルゴリズムを用いること
をさらに実行させる、請求項１７に記載のコンピュータ読み取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（分野）
本発明の分野は、概して無線ネットワークに関し、特に、経路距離係数（ｐａｔｈ  ｄｉｓｔａｎｃｅ  ｆａｃｔｏｒ；ＰＤＦ）を用いるメッシュ状ネットワークにおける無線周波数管理（ｒａｄｉｏ  ｆｒｅｑｕｅｎｃｙ  ｍａｎａｇｅｍｅｎｔ；ＲＦＭ）のための方法およびシステムに関する。
【背景技術】
【０００２】
（背景）
コンピュータおよび無線通信における最近の技術的な進歩によって、携帯型の無線コンピューティングは、ますます広範囲に及ぶ使用および用途を見てきた。有線によって束縛されることなく、携帯型コンピューティングデバイスを有するユーザは、固定された構造基盤が全く存在しない情況において、自由に動き回ることができ、そして互いに通信することができる。そのような場合において、ユーザらは、携帯型のアドホック（ａｄ−ｈｏｃ）ネットワーク（ＭＡＮｅｔ）または携帯型の無線メッシュ状ネットワークを形成することができる。携帯型の無線メッシュ状ネットワークは、何らの基礎をなすバックボーンおよび構造基盤を伴うことなく、無作為に移動し、そして任意のネットワークへとそれ自体を再編成することができる無線の携帯型ルータ（そして、関連するホスト）の自律システムである。
【０００３】
有線のインターネットの構造を反映して、ルーティングされた無線メッシュ状ネットワークは、非常に柔軟であり、本質的にフォールトトレラントである。それは、視線（ｌｉｎｅ−ｏｆ−ｓｉｇｈｔ）問題を簡素化し、最小限の量のネットワーク構造基盤および相互接続コストによってネットワークの到達距離および到達範囲を拡張する。
【０００４】
インターネットが人気を獲得し続けるときに、ブロードバンドアクセスに対する要求が、多くの領域において有線の構造基盤を追い越してきた。無線ブロードバンドネットワークは、有線の構造基盤が存在しないか、あるいは旧式または実用的でないところで、高性能のアクセスを可能にする。しかしながら、以前の無線ブロードバンド技術は、技術的な制約と高い展開コストとの組み合わせに起因して、価格志向型の大衆市場展開に対して実用的ではなかった。
【０００５】
当初は軍用のために開発されたけれども、無線メッシュ技術は、地下鉄、企業、キャンパスおよび公衆安全用途などの商用部門においても大きな価値を示してきた。世界中の数百の都市が、展開したか、またはそれらの都市を非有線にするために無線メッシュ状ネットワークを展開し、それらの市民、企業および政府に無線ブロードバンドサービスを提供することを計画している。無線メッシュ技術は勢いを獲得している。
【発明の概要】
【課題を解決するための手段】
【０００６】
（概要）
経路距離係数（ＰＤＦ）を用いるメッシュ状ネットワーク内の無線周波数管理（ＲＦＭ）のための方法およびシステムが開示される。一実施形態に従った、コンピュータ実装型の方法は、第一のメッシュルータとポータルとの間の経路距離係数（ＰＤＦ）を計算することを包含する。フレームが第二のメッシュルータに送信され、該フレームは、経路距離係数を含んでいる。
【０００７】
実装および要素の組み合わせの様々な新規の詳細を含む上記および他の好適な特徴が、ここで添付の図面を参照してさらに具体的に記載され、そして特許請求の範囲において示される。特定の方法および装置が、限定としてではなく単に例示として示されることが理解されるであろう。当業者によって理解されるように、本明細書中に説明された原理および特徴は、様々な数多くの実施形態において利用され得る。
【図面の簡単な説明】
【０００８】
本明細書の一部として含まれる添付の図面は、本発明の原理を説明し、教示するために役立つ、上記された一般的な説明および以下に与えられる好適な実施形態の詳細な説明とともに本発明の好適な実施形態をこれから例示する。
【図１】図１は、一実施形態に従った、例示的な無線メッシュ状ネットワークのトポロジを示す。
【図２】図２は、一実施形態に従った、メッシュ状ネットワーク内のメッシュルータの例示的な経路距離係数（ＰＤＦ）更新プロセスを示す。
【図３】図３は、一実施形態に従った、ＰＤＦを含んでいる例示的なビーコンフレームを示す。
【図４】図４は、一実施形態に従った、ＰＤＦの例示的なタイムアウトプロセスを示す。
【図５】図５は、一実施形態に従った、ＰＤＦを用いるループなしのツリーを構築するための例示的なプロセスを示す。
【図６】図６は、一実施形態に従った、例示的な経路距離ベクトル（ＰＤＶ）プロセスのフローチャートを示す。
【図７】図７は、一実施形態に従った、冗長なリンクおよびＰＤＶを用いる速い回復のための例示的なプロセスを示す。
【０００９】
図が必ずしも正確な縮尺で描かれておらず、同様な構造または機能の要素が、例示目的のために図にわたって一般に同様な参照数字によって表されることは留意されたい。図が、本明細書中に記載される様々な実施形態の説明を容易にすることを単に意図していることもまた留意されたい。図は、本明細書中に開示される教示のすべての局面を記載しておらず、そして特許請求の範囲を限定しない。
【発明を実施するための形態】
【００１０】
（詳細な説明）
経路距離係数（ＰＤＦ）を用いるメッシュ状ネットワークにおける無線周波数管理（ＲＦＭ）のための方法およびシステムが開示される。一実施形態に従った、コンピュータ実装型の方法は、第一のメッシュルータとポータルとの間の経路距離係数（ＰＤＦ）を計算することを包含する。フレームが第二のメッシュルータに送信され、該フレームは、経路距離係数を含んでいる。
【００１１】
本明細書中に開示される特徴および教示のそれぞれは、経路距離係数（ＰＤＦ）を用いるメッシュ状ネットワーク内の無線周波数管理（ＲＦＭ）のための方法およびシステムを提供するために、個別にかまたは他の特徴および教示とともに利用され得る。これらの追加の特徴および教示の多くを利用する代表的な例が、個別と組み合わせとの両方において、添付の図面を参照してさらに詳細に記載される。この詳細な説明は、本教示の好適な局面を実施するために、さらなる詳細を当業者に教示することを単に意図しており、特許請求の範囲を限定することを意図していない。従って、以下の詳細な説明において開示される特徴の組み合わせは、最も広い意味合いにおいて教示を実施することに必要でないことがあり得、代わりに、特に本教示の代表的な例を単に記載するために教示される。
【００１２】
説明目的のための以下の説明において、特定の専門用語が、本明細書中に開示される様々な発明の概念に関する理解を容易にするために記述される。しかしながら、これらの特定の詳細が、本明細書中に開示される様々な発明の概念を実施するために必要とされないことは当業者に明らかとなるであろう。
【００１３】
本発明は、本明細書中の動作を実行するための装置とも関連している。この装置は、要求される目的に対して特別に構築され得るか、あるいはコンピュータ内に格納されたコンピュータプログラムによって選択的に起動または再構成される汎用コンピュータを備え得る。そのようなコンピュータプログラムは、これらに限定されないけれども、フロッピィ（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、および光磁気ディスクを含む任意のタイプのディスク、読み出し専用メモリ、ランダムアクセスメモリ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、あるいは電子的な命令の格納に適する任意のタイプの媒体などのコンピュータ読み取り可能なストレージ媒体において格納され得、それぞれは、コンピュータのシステムバスに連結される。
【００１４】
本明細書中に提示される方法は、何らの特定のコンピュータまたは他の装置と本質的に関連していない。様々な汎用システムが、本明細書中の教示に従ったプログラムによって用いられ得るか、または必要とされる方法のステップを実行するために、さらに特殊化された装置を構築するために便利であることを示し得る。様々なこれらのシステムに対して必要とされる構造は、以下の説明から明らかとなる。さらに、本発明は、何らの特定のプログラミング言語に関して記載されていない。様々なプログラミング言語が、本明細書中に記載されるような本発明の教示を実施するために用いられ得ることが認識される。
【００１５】
さらに、代表的な実施例および従属請求項の様々な特徴が、本教示の追加の有用な実施形態を提供するために、特に明示的に列挙されない方法において組み合わされ得る。構成要素のグループのすべての値の範囲または指標が、当初の開示目的、および特許請求の範囲の主題を限定する目的のために、すべての可能な中間の値または中間の構成要素を開示することもまた明確に示される。図に示される構成要素の寸法および形状が、どのように本教示が実施されるかを理解することに役立つように計画されたけれども、実施例において示される寸法および形状を限定することを意図していないこともまた明確に示される。
【００１６】
ＰＤＦを用いるメッシュ状ネットワーク内の無線周波数管理のための方法およびシステムが開示される。経路距離ベクトル（ｐａｔｈ  ｄｉｓｔａｎｃｅ  ｖｅｃｔｏｒ；ＰＤＶ）の改良バージョンもまた開示される。
【００１７】
無線メッシュ状ネットワークは、いくつかのネットワーク管理および制御の属性を有している。ほとんどの場合において、別個の帯域外の制御チャネルは提供されない。ネットワーク制御または管理メッセージは、データトラフィックと同じチャネルにおいて送達される。しかしながら、データトラフィックと異なり、ネットワーク制御または管理メッセージは、通常ポータルノードから始動する。なぜならば、制御または管理メッセージを管理しているほとんどのネットワーク管理システム（ＮＭＳ）が、ポータルノード上またはその背後に配置されるからである。さらに、メッシュ状ネットワークを通過するルートは、データ転送のためにしばしば最適化される。結果として、管理または制御の経路は、部分最適であり得る。
【００１８】
図１は、一実施形態に従った、例示的な無線メッシュ状ネットワークのトポロジ１００を示す。メッシュルータ１１０ａは、有線のネットワーク接続１０２を介して有線のネットワークサーバ１０１に接続されるポータルである。リンク１０５、１１１、１１２および１１３は、メッシュルータ１１０の間の無線接続を表している。データは、メッシュ状ネットワーク１００内の１つのメッシュルータ１１０から任意の他のメッシュルータ１１０に送信され得る。
【００１９】
ネットワーク管理メッセージは、様々な方法でメッシュルータに送達される。ネットワーク管理システム（例えば、ＳＮＭＰ、ＸＭＬベースのＮＭＳ、ＨＴＴＰベースのウェブ管理、ＳＳＨ／テルネットベースのコマンドラインインターフェイス（ＣＬＩ）セッション）にかかわらず、ネットワーク管理メッセージは、有線のネットワークからリンク１０５、１１１、１１２および１１３を介してメッシュ状ネットワーク１００内のすべてのメッシュルータ１１０に送信される。
【００２０】
ネットワーク管理メッセージを送達するために、スパニングツリー（ｓｐａｎｎｉｎｇ  ｔｒｅｅ）が形成される。スパニングツリーは、メッシュ状ネットワークに対してポータルベースのツリー構造を生成する目的にかなっている。管理メッセージは、スパニングツリーの根元から始動し、そして階層方式においてメッシュ状ネットワーク１００に広がる。
【００２１】
スパニングツリープロトコル（ＳＴＰ）が用いられる場合には、ポータル１１０ａが根元になる。ブリッジプロトコルデータユニット（ｂｒｉｄｇｅ  ｐｒｏｔｏｃｏｌ  ｄａｔａ  ｕｎｉｔ；ＢＰＤＵ）が、スパニングツリーを形成するためにメッシュノードの間において交換される。スパニングツリーが収束するときには、ループなしで、かつ階層のツリートポロジが形成される。ネットワーク管理メッセージは、根元からスパニングツリーに沿ってすべてのメッシュノードに到達する。
【００２２】
管理メッセージは、ポータル１１０ａから始動し、最初にリンク１１１を介してポータル１１０ａの直接的に隣の１１０ｂ〜１１０ｄのすべてに到達する。管理メッセージにおける変更が、２つのメッシュルータ１１０の間の接続性に影響する場合には、そのような変更は、正しい順序において起こらなければならず、そうでなければ、２つのメッシュルータ１１０の間の接続性が恒久的に失われ得る。例えば、変更する必要があるメッシュルータ１１０ａと、その直接的に隣のメッシュルータ１１０ｂとの間のリンク１１１を変更するために、リンク管理メッセージが発行される場合には、メッシュルータ１１０ｂでの変更が、リンク失敗を避けるために、メッシュルータ１１０ａでの変更の前に起こらなければならない。変更が最初にメッシュルータ１１０ａで起こる場合には、メッシュルータ１１０ａと１１０ｂとの間のリンク１１１が失われ得る。結果として、リンク管理メッセージは、もはやメッシュルータ１１０ｂに送達され得ず、メッシュルータ１１０ｂの予定された変更は決して起こらない。
【００２３】
変更が最初にメッシュルータ１１０ｂで起こる場合に、メッシュルータ１１０ａと１１０ｂとの間のリンク１１１がその後失われ得る場合でさえも、リンク管理メッセージは、メッシュルータ１１０ｂと１１０ａとの両方に連続して送達される。なぜならば、有線のネットワークサーバ１０１から発行されたリンク管理メッセージは、ネットワーク管理サーバ１０１により近いメッシュルータ１１０が、ネットワーク管理サーバ１０１からより遠いメッシュルータ１００よりも早くメッセージを受信するような方法で送達されるからである。
【００２４】
同じ状況は、メッシュ状ネットワーク１００内の他のメッシュルータ１１０にあてはまる。メッシュルータ１１０ｄと１１０ｇとの間のリンク１１２を管理するために、ネットワーク管理サーバ１０１からメッシュルータ１１０ｇへのいくつかの経路（例えば、１１０ａ−１１０ｄ−１１０ｇおよび１１０ａ−１１０ｂ−１１０ｄ−１１０ｈ−１１０ｇ）が使われ得る。経路１１０ａ−１１０ｄ−１１０ｇはより信頼できる。なぜならば、メッシュルータ１１０ａから、メッシュルータ１１０ｄよりも相対的に遠く離れているメッシュルータ１１０ｈを通り抜けないからである。構成の変更が最初にメッシュルータ１１０ｄで起こる場合には、そのことは、１１０ｄ−１１０ｈの間、および１１０ｄ−１１０ｇの間のリンクを含むすべてのリンクに影響し得る。従って、変更がメッシュルータ１１０ｄで起こった後においては、メッシュルータ１１０ｇへのすべての経路が利用可能なわけではない。結果として、メッシュルータ１１０ｇおよびその背後のネットワークはその後到達不可能になる。
【００２５】
メッシュルーティングは、メッシュ状ネットワーク１００内のノード１１０の各対の間の最適経路問題を解決するけれども、従来のメッシュ状ネットワークは、ネットワーク管理に対する固有の問題を有している。メッシュ状ネットワークの管理ソースは、メッシュ状ネットワーク１００の外側に配置され、管理のための別個の制御チャネルが提供されない。さらに、スパニングツリープロトコルは、以下の欠点を有する。
１．  ＳＴＰは、大きいメッシュ状ネットワークに合わせて調整しない。
２．  ＳＴＰ制御メッセージは、かなりの負担をメッシュ復路の容量に追加する。
３．  ＳＴＰは、信頼性に対する冗長経路を提供しない。
４．  ＳＴＰは、一般に１つだけの根元をサポートする。複数の根元をサポートするためには、複数のＳＴＰが同時に実行される必要があり、そのことが、さらに復路通信を遅くする。
【００２６】
いくつかの従来のツリーベースのメッシュルーティングプロトコルが、同時にメッシュルーティングとメッシュ管理との両方によって、これらの問題に対処するために提案されてきた。ツリーベースのメッシュルーティングプロトコルのツリーベースのトポロジは、単純であり、そして相対的に安定しており、複数の根元をサポートし得る。しかしながら、ツリーベースのトポロジは、データ転送に対して最適ではない。なぜならば、ピアツーピアのトラフィックが、共通の親ノードを通り抜ける必要があるからである。ツリーベースのトポロジはまた、ネットワーク全体の冗長性と負荷とのバランスを提供することにおいて難点を有する。
【００２７】
メッシュネットワーキングが直面する別の挑戦的な問題は収束問題である。１つの接続されたネットワークへのすべてのメッシュルータの収束がいつも保証されるわけではない。例えば、メッシュ状ネットワーク１００のすべてのメッシュルータ１１０が同時に電源オンになる場合に、単一のメッシュ状ネットワークを形成することは保証されない。メッシュルータ１１０ａ、１１０ｂおよび１１０ｃが１つのネットワークを形成し得、メッシュルータ１１０ｄ、１１０ｇおよび１００ｈが別のネットワークを形成し得、メッシュルータ１１０ｅ、１１０ｆおよび１１０ｉが別のネットワークを形成し得る。さらに、チャネル割当ての動的な性質に起因して、メッシュルータへの最適なチャネル割当てを実装することは困難である。
【００２８】
現在のＩＥＥＥ８０２．１１ドラフトは、同じチャネルに収束することをすべてのメッシュルータに強制することによって、メッシュ状ネットワークの収束問題を解決する計画を提案する。しかしながら、そのことは望ましくない。なぜならば、同じチャネル上で作業するすべてのメッシュルータが、互いに干渉し、従って、転送性能を低下させるからである。
【００２９】
一実施形態に従った、メッシュ状ネットワーク１００は、８０２．１１レベルにおけるメッシュ状ネットワークの管理問題および収束問題を解決するためにＰＤＦプロセスを用いる。ＰＤＦプロセスは、８０２．１１のビーコンを利用し、追加の負担をメッシュ状ネットワーク１００に対して追加しない。ＰＤＦプロセスはまた、ノードまたはリンクの失敗の場合における速い回復を保証するために、ネットワーク全体の冗長性を提供する。
【００３０】
ＰＤＦは、最も近いポータル（例えば、メッシュルータ１１０ａ）へのメッシュルータ（例えば、メッシュルータ１１０ｉ）の距離である。距離は、ポータル１１０ａへのホップの総数か、ポータル１１０ａからパケットを送信または受信する絶対的時間（ホップの数にかかわらない）か、ポータル１１０ａへの物理的な距離か、あるいは同様な距離計算によって測定され得る。一実施形態に従った、ポータルのＰＤＦは、異なるポータルに対して異なる重みを与えるために、ゼロまたはゼロよりも大きい任意の値に設定され得る。複数のポータルをサポートするために、無線周波数管理（ＲＦＭ）の情報要素（ｉｎｆｏｒｍａｔｉｏｎ  ｅｌｅｍｅｎｔ；ＩＥ）は、メッシュルータがポータルであるか否かを示すために、特別なフラグを導入する。
【００３１】
図３は、一実施形態に従った、ＰＤＦ３１３を含んでいる例示的なビーコンフレーム１５０を示す。ＰＤＦ３１３などのＩＥ拡張が、ルータ１１０によって８０２．１１のビーコンフレーム１５０内に追加され得る。ビーコンフレーム１５０は、メッシュルータ１１０の間の通信を確立し、そして維持するために、メッシュルータ１１０から近隣のメッシュルータ１１０に定期的に同報通信される。ビーコンフレーム１５０は、ビーコンヘッダ３０１と、ビーコンフレーム３１０と、ＣＲＣ３２０とを含む。ビーコンヘッダ３０１は、送信元および宛先の媒体アクセス制御（ＭＡＣ）アドレス、および通信プロセスに関する他の情報を含んでいる。ビーコンのフレーム本体部３１０は、ビーコンフレームの間の同報通信時間を表すビーコン間隔、送信元と宛先との間の同期のために用いられるタイムスタンプ、ならびにサービスセット識別子（ＳＳＩＤ）、サポートするデータレートおよび暗号化キーなどの他の接続属性を含む。一実施形態に従った、ビーコンフレーム１５０内のＰＤＦ３１３は定期的に更新される。プローブ応答フレームなどの他の管理フレームが、ＰＤＦ３１３を同様に含み得る。一実施形態に従った、ＰＤＦ３１３は、３２ビット整数値を格納し得る。
【００３２】
一実施形態に従った、ＰＤＦ３１３だけを含める代わりに、メッシュルータ１１０はまた、ポータル１１０ａまでの経路上のメッシュルータ１１０の１つ以上の識別子をビーコン１５０および／またはプローブ応答管理フレームへと挿入するとともに、それ自体の一意の識別子をＩＤ３１２においてフレーム１５０へと挿入する。
【００３３】
ビーコン１５０およびプローブ応答管理フレームが、到達領域内の隣のメッシュルータ１１０によって受信されるので、それらは単に局所的に同報通信される。すべてのメッシュノードの最新のＰＤＦ３１３は、到達領域内の近隣の１１０に対して公表される。対照的に、ＳＴＰプロトコルは、プロトコルメッセージおよびタイマを用い、従って、より大きな負担を限定された無線接続に追加する。
【００３４】
電源をオンされるときに、各メッシュルータ１１０は、それ自体のＰＤＦ３１３を無限大に初期化する。そのことは、各メッシュルータ１１０が何らのポータルへの有効なリンクを有しないことを暗示している。メッシュルータ１１０が、ポータル１１０ａである場合には、そのことは構成またはユーザＣＬＩのいずれかから知られており、ポータル１１０ａは、それ自体のＰＤＦ３１３をユーザに指定された値またはデフォルトの事前に構成されたポータルＰＤＦ（例えば、最も簡単な場合においてゼロ）に変更する。各メッシュルータ１１０が、ビーコン１５０を介してそのＰＤＦ３１３を定期的に同報通信するときには、すべての隣のメッシュルータ１１０が、更新されたＰＤＦ値３１３を受信する。
【００３５】
図２は、一実施形態に従った、メッシュ状ネットワーク１００内のメッシュルータ１１０の例示的なＰＤＦ更新プロセスを示す。メッシュルータ１１０は、ビーコン（２０１）を受信することによって、そのＰＤＦに対する更新を実行する。メッシュルータの各無線部は、候補リストと呼ばれる、すべての走査される隣のリストを含んでいるトポロジのデータベースを維持する。無線部は、候補リストから有効なリンクを有する隣のメッシュルータを選択する。メッシュルータとの有効なリンクを有する隣のメッシュルータは隣のリストを形成する。隣のメッシュルータからＰＤＦの更新を受信すると、メッシュルータは、隣が新しい隣のメッシュルータであるか否かをチェックする（２０２）。
【００３６】
隣がメッシュルータ１１０に対して新しい場合には、それはメッシュルータのトポロジデータベースに追加される（２０５および２０６）。この時点で、隣およびメッシュルータ１１０のＰＤＦが、ポータルへの接続性のためにチェックされる。ポータルに接続されるときには、メッシュルータ１１０または隣のＰＤＦ３１３が有限の数字に設定される。メッシュルータ１１０および隣のＰＤＦ３１３が両方とも無限大でない場合には、すなわち、隣またはメッシュルータ１１０のいずれかがポータルとの有効な接続を有しており、隣へのインターフェイスを介するメッシュルータ１１０のＰＤＦは、隣のＰＤＦと隣に対するコストとの合計に設定される（２０５）。隣へのコストは、様々な係数（例えば、メッシュルータと隣との間の物理的距離、リンクに利用可能なチャネルの数、信号強度および雑音レベル）によって決定される。
【００３７】
隣が新しくない場合には、メッシュルータは、それが隣への既存のリンクを有するか否かをチェックする（２０４）。メッシュルータが隣への既存のリンクを有する場合には、メッシュルータは、そのＰＤＦが更新される必要があるか否かをチェックする（２０７）。メッシュルータが隣への有効なリンクを有しない場合には、該隣は、候補リスト内に残り、トポロジデータベースがそれに応じて更新される（２０８）。
【００３８】
メッシュルータのＰＤＦ３１３を更新するときに、メッシュルータ自体のＰＤＦが無限大であるけれども、隣のＰＤＦが有限の数字であることが可能である。その場合においては、メッシュルータはまだ、「アイランド（ｉｓｌａｎｄ）」状態の内にある（例えば、メッシュルータがポータルに到達するための確立された経路を有しないけれども、隣がすでに有効な経路を有している）。この情況下において、メッシュルータは、リンク確立要求を隣に対して直ちに送出することによって、「アイランド」状態を脱出する。
【００３９】
各隣へのインターフェイスは、隣と関連づけられたＰＤＦを有しており、メッシュルータの全部のＰＤＦは、すべてのインターフェイスのＰＤＦの最小値によって決定される（２０９）。
【００４０】
【数１】
2010519833.tif 000003
ここで、Ｎは、メッシュルータについての隣の総数である。ＰＤＦが計算されるときに、それはメッシュルータのトポロジデータベース内に格納される。
【００４１】
一実施形態に従った、複数のポータルは、異なるＰＤＦを異なるポータルに対して割り当てることによってサポートされ得る。複数のポータルは、異なる初期のＰＤＦ値を与えられ、従って、ポータルへのリンクがＰＤＦによって定量的に表され、それによって、ポータルへの負荷が、効率的に監視され、バランスを保ち得る。
【００４２】
一実施形態に従った、各隣のＰＤＦは、タイムアウトタイマと関連づけられる。メッシュルータがタイムアウトの期間内に隣からビーコンまたはプローブ応答メッセージを受信しない場合には、隣のＰＤＦは、ポータルとの接続が失われていることを示す無限大にリセットされる。新しいＰＤＦは、それに応じて、トポロジデータベースにおいて更新される。
【００４３】
図４は、一実施形態に従った、ＰＤＦ３１３の例示的なタイムアウトプロセスを示す。ＰＤＦ更新が、あるメッシュルータでタイムアウトするときには、そのことが隣に報告される（４０１）。ＰＤＦ更新プロセスに類似して、メッシュルータは、タイムアウトを報告した隣に対するリンクの妥当性をチェックする（４０２）。隣への有効なリンクが存在しない場合には、メッシュルータのトポロジデータベースが単に更新される（４０３）。隣への有効なリンクが検出される場合には、隣は、隣のリストから候補リストに移動されるか、または「ダウン（ｄｏｗｎ）」状態に設定される（４０４）。隣が候補リストから除去される場合に、ＰＤＦが変更されたときには、メッシュルータのＰＤＦが更新され（４０５）、新しいＰＤＦ値に設定される（４０６）。
【００４４】
一実施形態に従った、ＰＤＦの方法は、メッシュ状ネットワーク内にループなしのツリートポロジを組み立てる。このループなしのツリートポロジは、リンクの冗長性をサポートする。リンクがタイムアウトプロセスにより除去されるか、または何らかの理由で壊れているときに、隣のうちの１つへの別のリンクが、メッシュルータにおいて利用可能な最小値のＰＤＦに基づいて形成される。各リンクの重みが、リンクのＰＤＦを計算するときに考慮される。複数のポータルは、所与のメッシュルータに対する複数のポータルへの接続の順番に優先度を付けるために、複数のポータルに異なるＰＤＦの重みを与えることによってサポートされる。
【００４５】
ループなしのツリーを保証するために、ＰＤＦの方法は、向上された拡散更新アルゴリズム（ｄｉｆｆｕｓｉｎｇ  ｕｐｄａｔｅ  ａｌｇｏｒｉｔｈｍ；ＤＵＡＬ）を用いる。ＤＵＡＬは、メッシュルーティングのトポロジループの問題を解決するために設計される。ＤＵＡＬのフルセットは不要である。
【００４６】
各ノードは、すべての隣から受信されたＰＤＦ情報によって、そのトポロジを組み立てる。トポロジデータベースは、各隣のＰＤＦと、各隣に対するＰＤＦのコストとを格納する。隣のＰＤＦは、最も近いポータルに対する隣のコストである。メッシュルータのＰＤＦは、隣のＰＤＦと、その隣に対するメッシュルータのコストとの合計である。最小値のＰＤＦを提供する隣は、メッシュルータの後続と称される。
【００４７】
図５は、一実施形態に従った、ＰＤＦを用いるループなしのツリーを構築するための例示的なプロセスを示す。宛先ＸまでのメッシュルータＢの報告された距離（ｒｅｐｏｒｔｅｄ  ｄｉｓｔａｎｃｅ；ＲＤ）は９０である。メッシュルータＣもまた、宛先Ｘまでの代替のルートを有し、それもまた９０のＲＤを有する。メッシュルータＡから宛先ＸまでのＰＤＦは、後続のＲＤと後続に対するコストとの合計によって決定される。メッシュルータＡからメッシュルータＣまでのコスト（２０）が、メッシュルータＡからメッシュルータＢまでのコスト（１０）よりも高いので、メッシュルータＡは、後続としてメッシュルータＢを選び、宛先ＸまでのメッシュルータＡのＰＤＦを１００として設定する。
【００４８】
メッシュルータＡは、後続としてメッシュルータＣを用いないけれども、メッシュルータＡはなお、そのトポロジデータベース内に宛先ＸまでのメッシュルータＣのＲＤ（すなわち、ＰＤＦ）とともにメッシュルータＣの情報を保存する。メッシュルータＡからメッシュルータＢまでのリンクが壊れる場合には、メッシュルータＡは、新しい後続としてメッシュルータＣを選び、メッシュルータＣに対するコスト（２０）と、メッシュルータＣから宛先ＸまでのＲＤ（９０）を合計することによって、宛先ＸまでのそのＰＤＦを１１０に更新する。
【００４９】
メッシュルータＡは、メッシュルータＣのＲＤ（９０）をメッシュルータＡの当初の実行可能な距離（ｆｅａｓｉｂｌｅ  ｄｉｓｔａｎｃｅ；ＦＤ）（１００）と比較することによって、宛先Ｘまでの経路がループなしであるか否かを安全に決定する。メッシュルータＣのＲＤがメッシュルータＡの当初のＦＤを下回る場合には、メッシュルータＣが、ＤＵＡＬ計算における実行可能性の条件（ｆｅａｓｉｂｉｌｉｔｙ  ｃｏｎｄｉｔｉｏｎ；ＦＣ）を満足し、メッシュルータＡの実行可能な後続（ｆｅａｓｉｂｌｅ  ｓｕｃｃｅｓｓｏｒ；ＦＳ）となる。図５の例によると、宛先ＸまでのメッシュルータＣのＲＤ（９０）が、宛先ＸまでのメッシュルータＡの当初のＦＤ（１００）を下回る。このことは、宛先ＸまでのメッシュルータＣの経路がメッシュルータＡを通っていないことを示しており、従って、メッシュルータＡは、メッシュルータＣを新しい後続として安全に選ぶことができる。
【００５０】
メッシュルータＣのＲＤ値がメッシュルータＡの当初のＦＤよりも高い場合には、宛先ＸまでのメッシュルータＣの経路が、メッシュルータＡを通っていることがあり得、そのことがループの形成につながり得る。当初のＦＤと後継候補のＲＤとを比較する向上されたＤＵＡＬアルゴリズムは、ループなしのツリーの構築を保証している。
【００５１】
各メッシュルータは、すべての候補ＦＳを介する宛先へのＰＤＦを計算し、そのＰＤＦとして最小値のＰＤＦを選び取る。複数のＦＳが同じ最小値のＰＤＦをもたらす場合には、それらはすべてメッシュルータの後続になり得る。メッシュ状ネットワークのトポロジが変更されるときには、トポロジデータベースにおいて局所的に利用可能なＦＳの存在が収束を容易にする。ＦＳが局所的に利用可能でない場合には、メッシュルータは隣に対してクエリを送出する。クエリは、メッシュルータのＦＳによってクエリが受信されるまで、伝播する（または、「拡散する」）。一実施形態に従った、クエリへの応答においてＦＳを見出さなかった隣は、ＦＳが到達可能でないことを通知するメッセージを戻す。
【００５２】
隣が選択された後、より大きいＰＤＦを有する一方が、他方の端部に対してリンク確立要求を送出する。メッシュルータが、より小さいＰＤＦを有する隣からリンク確立要求を受信する場合には、要求は拒否される。そのことは、ループなしのツリーを形成することを保証するために、より大きいＰＤＦを有する隣だけからの要求が受容されることを可能にする。
【００５３】
一実施形態に従った、メッシュ状ネットワークの形成プロセスは方向性がある。より大きいＰＤＦを有する一方が、リンク確立イニシエータである。このことは、単にループなしのツリーを保証するよりも多くの利益をもたらす。受信側がリンク確立要求を取得するときには、受信側は、全体のチャネル利用状態を評価し、どのチャネル上で接続が確立されることを可能にされるかを指定する。
【００５４】
メッシュルータの各無線インターフェイスは、独立のステートマシンを実行する。一実施形態に従った、ステートマシンは４つの異なる状態からなり、それらは、ＤＩＳＣＯＶＥＲＩＮＧと、ＳＣＡＮＮＩＮＧと、ＣＯＮＮＥＣＴＩＮＧと、ＣＯＮＮＥＣＴＥＤとである。ＤＩＳＣＯＶＥＲＩＮＧ状態は、無線部が受動的走査または能動的走査のいずれかを行う状態である。この状態は、無線部が復路モードを可能にされ、その無線分配システム（ＷＤＳ）モードが自動に設定されるときには、初期状態である。任意の隣が、ＳＣＡＮＮＩＮＧ状態にあることを見出される場合には、メッシュルータの無線部は、ＣＯＮＮＥＣＴＩＮＧ状態に入り、隣への有効な接続を確立することを試みる。任意の有効なリンク結合が確立され、メッシュルータのＰＤＦが有限であると確認される場合には、無線部は、ＣＯＮＮＥＣＴＥＤ状態に入る。
【００５５】
任意の状態において、無線インターフェイスが、より大きいＰＤＦを有する隣から接続するための要求を受信する場合には、無線インターフェイスは接続要求に応答する。各無線部は、有効なリンクが確立された後でさえも定期的に受動的走査モードに入るので、無線部が結局は、すべての利用可能なチャネル上のすべての隣を見出す。
【００５６】
ＰＤＦの伝播は、根元（すなわち、ポータル）から始動し、メッシュ状ネットワーク内のすべてのノードに到達する。収束の後に、ループなしのツリーが構築される。ポータルが有限のＰＤＦを与えられるので、ポータルのうちの１つへの有効な経路を見出した後に、他のノードは、それらのデフォルトのＰＤＦ（無限大）を有限値に変更する。メッシュルータがなおデフォルトのＰＤＦを有する場合には、メッシュルータは、アイランド状態にあるとみなされる。メッシュルータは、アイランド状態に留まる一方で、アイランド状態を脱出するために、隣との接続を確立することを試みる。
【００５７】
ＰＤＦプロセスは、ポータルを根元としたメッシュ状ネットワークの収束を保証する。ＰＤＦプロセスはまた、メッシュを形成する間にチャネル選択を最適化するためのメカニズムを提供する。根元のメッシュルータ（すなわち、ポータル）は、最もよいチャネルを最初に選択し、その選択を子のメッシュルータに伝播させる。子のメッシュルータは続いて、すべての子のメッシュルータがそれらの隣へのチャネルを選択するまで、残りのチャネルプールから最もよいチャネルを選択する。
【００５８】
根元のメッシュルータは、メッシュ形成の時点で利用可能な最もよいチャネルを選択することにおいて、子のルータメッシュよりも高い優先度を有する。各メッシュルータは、それが根元または子であるか否かにかかわらず、様々な条件（例えば、隣との干渉、信号強度および雑音レベル）を考慮して、最もよいチャネルを選択する局所的な決定を行う。この手順は、メッシュ状ネットワーク全体に対して最適に近いチャネル選択スキームを提供する。
【００５９】
チャネル選択が絶対的な方式でチャネルプランナ（例えば、第三のデバイスのメッシュルータ）によって実行される場合には、チャネルプランナは、最適のチャネル選択に対してメッシュ状ネットワーク全体の包括的な理解を有することを要求される。実際には、メッシュ状ネットワーク全体の包括的な理解は、一般にメッシュ状ネットワーク内のどの単一のメッシュルータにも利用可能ではない。最適に近いチャネル選択スキームがツリー組み立てプロセスに続いており、子のメッシュルータが、それらの最もよいチャネルを選択する機会を得る前に、ポータル（すなわち、根元のメッシュルータ）が最もよいチャネルを選択することを可能にする。
【００６０】
各メッシュルータは、ビーコンおよび／またはプローブ応答フレーム内に複数のＰＤＦと複数の一意のＩＤ（ノードＩＤと名付けられる）とを含む。＜ノードＩＤ，ＰＤＦ＞の各対は、経路距離ベクトル（ＰＤＶ）と呼ばれるＰＤＦベクトルを形成する。一実施形態に従った、ＰＤＶ情報は、メッシュルータのＦＳを選択するために用いられる。メッシュルータは、そのＰＤＶ情報を同報通信し、そして該メッシュルータのすべての隣からＰＤＶ情報を収集する。隣が実行可能性の条件を満足している場合には、それはメッシュルータのＦＳになる。実行可能性の条件は、隣のＰＤＶがメッシュルータを含むか否かをチェックする。メッシュルータの有効なＦＳになるためには、隣のＰＤＶがメッシュルータを含んではならない。隣のＰＤＶがメッシュルータを含む場合には、ループするツリーが形成され、該隣は実行可能性の条件に違反する。
【００６１】
ＰＤＶは、メッシュルータがポータルへのその全部の経路または部分的な経路を公表することを可能にし、そのことは、メッシュ形成およびエラー回復に役立つかなり多くの情報を提供する。図１において、メッシュルータ１１０ｇは、ポータル１１０ａへの経路（すなわち、１１０ｇ−１１０ｄ−１１０ａ）をビーコンフレーム内に含んでいる。同様に、メッシュルータ１１０ｉは、ポータル１１０ａへの経路（１１０ｉ−１１０ｆ−１１０ｃ−１１０ａ）を公表する。
【００６２】
ＰＤＶアプローチは、メッシュルータに全部の経路またはすべての可能な経路を公表することを要求しない。一実施形態に従った、ＰＤＶしきい値が、管理フレーム内に公表され得るメッシュノードの総数を制限するために用いられる。その最小値は２であり、メッシュ状ネットワークの規模に応じて、４と１０との間にあることが推奨される。ＰＤＶしきい値は、２つの目的にかなう。その目的とは、ビーコンおよび／またはプローブ応答フレームのサイズを制限することと、メッシュ状ネットワークを層に分割することとである。
【００６３】
ＰＤＶしきい値は、各メッシュルータが管理フレーム内に公表し得るメッシュノードの最大の数を指定する。図１を参照して、ＰＤＶしきい値が２に設定される場合には、各メッシュルータは、最高２つまでのＰＤＶを公表し得る。例えば、ポータル１１０ａは、ビーコンを用いて、＜１１０ａ，０＞を公表する。メッシュルータ１１０ｂは、＜１１０ｂ，１＞と＜１１０ａ，０＞とを公表する。メッシュルータ１１０ｉは、＜１１０ｉ，６＞と＜１１０ｆ，３＞とを公表する。ＰＤＦしきい値は、メッシュ状ネットワークをＰＤＦの異なる範囲を有する異なる層に分割する。例えば、［０，１］の範囲のＰＤＦを有するすべてのメッシュルータが第一の層を形成し、［２，３］の範囲のＰＤＦを有するすべてのメッシュルータが第二の層を形成する、などである。
【００６４】
図６は、一実施形態に従った、例示的なＰＤＶプロセスのフローチャートを示す。メッシュルータが隣からビーコンまたはプローブ応答を受信するときには、メッシュルータは、ＰＤＶを更新するために、以下の動作を実行する。メッシュルータがすでに隣とのリンクを有する場合には（６０１）、隣に対するＰＤＶが、前の値から変更されたか否かチェックされる（６０２）。ＰＤＶが変更された場合には、それはメッシュルータのトポロジデータベース上で更新され（６０４）、そうでなければ、何らの動作も必要とされない（６０５）。何らのリンクも隣と確立されていない場合には、隣に対するＰＤＶが、メッシュルータと同じ層内に該隣があるか否かチェックされる（６０３）。該隣が同じ層内にある場合には、メッシュルータはさらに、その経路が隣を含むか否かをチェックする（６０６）。経路が隣を含む場合には、メッシュルータはさらに、隣への経路が最適化され得るか否かをチェックし（６０７）、そうでなければ、メッシュルータは隣を単に受容し、そしてトポロジデータベース上で更新する（６０９）。隣がメッシュルータと同じ層内にない場合には（６０３）、隣の層はさらに、隣が上の層に付属しているか否か検査される（６０８）。隣が上の層に付属している場合には、隣が受容され、そしてメッシュルータのトポロジデータベースが更新される（６０９）。そうでなければ、メッシュルータは、何らの行動もとらずに戻る（６１０）。結果として、ＰＤＶプロセスは、上の層内のメッシュルータだけが、低い層内のメッシュルータに接続することを可能にし、従って、メッシュ状ネットワーク内にループを形成することを防止する。
【００６５】
ＰＤＶプロセスは、管理フレーム内においてより多くのフィールドを必要としているので、ループを防止するために、多くの論理比較を実行する。しかしながら、ＰＤＶプロセスは、完全なＤＵＡＬアルゴリズムを実行する必要がなく、従って、ＲＤデータベースを維持する必要性が存在しない。ＰＤＶの方法はまた、良好なスケーラビリティを提供する。なぜならば、ＰＤＶしきい値が、異なるメッシュ規模に適応するように動的に調整されるからである。
【００６６】
部分的な経路情報によって、ＰＤＶプロセスは速い回復を達成する。図７は、一実施形態に従った、冗長なリンクおよびＰＤＶを用いる速い回復のための例示的なプロセスを示す。メッシュルータＸとメッシュルータＹとは、互いに審問することができると仮定する。メッシュルータＡとメッシュルータＢともまた、互いに審問することができる。メッシュルータＸとメッシュルータＹとの両方は、層の境界７０１に直接的に接続するために、無線インターフェイス０を用いる。
【００６７】
本ＰＤＦプロセスに従った、すべてのリンク７１０が、ループなしのツリーを形成するように組み立てられる。リンク７１０および７１１は、リンク確立イニシエータから始動される。ＰＤＶプロセスが用いられる場合には、リンク７１１もまた確立される。なぜならば、メッシュルータＸおよびＹが、同じＰＤＦを有するからである。メッシュルータＹが、メッシュルータＸの実行可能性の条件を満足していないので、どちらもメッシュルータＸを実行しない。しかしながら、メッシュルータＸはまた、層の境界７０１へのメッシュルータＹの経路が、メッシュルータＸ自体を含んでいたか否かをチェックすることができる。それが含まれない場合には、メッシュルータＸは、メッシュルータＹを有効な隣として選択する。メッシュルータＢは、同じ理由によりメッシュルータＡを有効な隣として選択する。
【００６８】
メッシュルータＢは、層の境界７１０に到達する２つの経路（例えば、Ｙを介する経路およびＡ−Ｘを介する経路）を有するけれども、その最も短い経路をビーコンフレーム内に書き込む。
【００６９】
ノード失敗の場合に、メッシュルータは、ＰＤＶの方法を用い、冗長経路によって、より速く失敗を回復し得る。ＰＤＦの場合において、メッシュルータＸの無線インターフェイス０が失敗する場合には、メッシュルータＸは、それ自体のＰＤＦを無限大に設定し、次いで、すべての隣がメッシュルータＡを新しい親として見出すように走査する。これに対して、ＰＤＶの場合には、メッシュルータＸは、何らのトラフィック損失を伴うことなく、直ちにメッシュルータＹへのリンク７１１を用いる。リンク７１１は、信頼できるループなしのリンクである。なぜならば、メッシュルータＹがリンク確立要求を初期化するときに、メッシュルータＸが行ったように、メッシュルータＹがループなしのチェックをすでに行ったからである。両端がループなしのチェックをすでに行ったので、リンク７１１は、追加の妥当性検証なしに直ちに用いられ得る。
【００７０】
ＰＤＶの方法は、ループなしのツリーを組み立てない。ＰＤＶの方法は、より伝統的なメッシュ状ネットワークを実際に組み立てる。タイムアウトメカニズムと最大のＰＤＦとが、ループを防止するために実装される。しかしながら、ＰＤＶの方法は、ビーコンまたは他の管理フレームにおいて告知された部分的または全体の経路情報に起因して、何らの伝統的な距離ベクトル問題（例えば、無限大までカウントすること）をも有しない。ＰＤＶの方法は、同じ層内の局所的なループ化を効率的に防止する。ＰＤＶの方法は、隣が上の層内または同じ層内にあるが経路に含まれていない場合にのみ、メッシュルータが新しい隣を受容するという点において、任意の伝統的な距離ベクトルの方法から目立っている。
【００７１】
ＰＤＶの方法によって、メッシュ状ネットワーク内のすべてのノードが、部分的または全体の経路情報を最も近いポータルに報告する。すべてのノードは、受信された情報に基づいて、層の規則に従った隣のリストを構築する。それと対照的に、ＰＤＦは、層の概念を全く有しない。ＰＤＦ内の各ノードは、ループなしのツリーを組み立てるために、最も近いポータルに対してその距離のみを公表する。ＰＤＦの方法は、収束されたメッシュ状ネットワークを保証し、そしてメッシュ状ネットワーク内の各メッシュルータに対して深さ情報を追加する。
【００７２】
図１を参照して、アクティブな接続が存在せず、ポータル１１０ａを除くすべてのメッシュルータ１１０ｂ〜１１０ｉがちょうど今電源オンされたと仮定する。
【００７３】
メッシュルータ１１０ｂ〜１１０ｉがポータル１１０ａなしに電源オンされ、すべてのそれらのＰＤＦがデフォルトで無限大に設定されるので、メッシュルータ１１０ｂ〜１１０ｉは、ＤＩＳＣＯＶＥＲＩＮＧ状態に入る。それらは、ＤＩＳＣＯＶＥＲＩＮＧ状態の間に接続する隣を見出すことができるけれども、それらのＰＤＦは無限大のままである。
【００７４】
図１のリンク１１２および１１３などの有効なリンクが、メッシュルータ１１０ｂ〜１１０ｉの間において形成され得る。しかしながら、これらのリンクは、メッシュルータのＰＤＦを変更させない。なぜならば、それらがみな同じ無限大のＰＤＦを有するからである。ポータル１１０ａが起動するときに、ポータル１１０ａは、その有限のＰＤＦ（例えば、０）を、ビーコンフレームを用いてその直接的に隣に対して公表し始める。
【００７５】
ポータル１１０ａが起動した後、メッシュルータ１１０ｂ、１１０ｃおよび１１０ｄは、ポータル１１０ａのビーコンを受信する。メッシュルータ１１０ｂ、１１０ｃおよび１１０ｄがすべて無限大のＰＤＦを有するので、ポータル１１０ａのビーコンが受信されたときに、メッシュルータ１１０ｂ、１１０ｃおよび１１０ｄは、リンク確立要求をポータル１１０ａに送出する。
【００７６】
ポータル１１０ａは次いで、どのチャネルの接続が可能にされるかを決定し、それらのリンク確立要求を受容し、そしてどのチャネルのリンクを確立するかを通知する。ポータル１１０ａへの有効なリンクを確立した後、メッシュルータ１１０ｂ、１１０ｃおよび１１０ｄが適切にそれらのＰＤＦを設定し、ビーコンフレーム内に新しいＰＤＦを公表する。残りのメッシュルータ１１０ｅ〜１１０ｉは続いて、それらの隣の更新されたＰＤＦを受信し、同じリンク要求およびＰＤＦ更新のプロセスが繰り返す。一部の以前に確立されたリンクが、最後のチャネル割当てにおいて除去され得ることに留意されたい。例えば、メッシュルータ１１０ｄは、メッシュルータ１１０ｅ、１１０ｇおよび１１０ｈに対して確立された、いくつかのリンクをすでに有し得る。ポータル１１０ａが、それ自体へのリンクを既存のリンクのチャネルと異なる特定のチャネル上に確立するためにメッシュルータ１１０ｄに対して通知した後に、メッシュルータ１１０ｄ上の既存のリンクが除去され得る。
【００７７】
同じメッシュ状ネットワーク構築プロセスは、ネットワーク内のすべてのメッシュルータに伝播する。結果として、ループなしのツリーがメッシュ状ネットワーク内に構築され、最適に近いチャネル割当てスキームが、ポータルからメッシュ状ネットワーク内のすべてのメッシュルータに対して達成される。
【００７８】
ノード回復のプロセスを説明するために、メッシュルータ１１０ｄがダウンしていると仮定する。２つの場合が考慮されるべきである。メッシュルータ１１０ｄがゆっくりとダウンする場合には、メッシュルータ１１０ｄが、リンクダウン通知をその隣に送信するので、従って、メッシュルータ１１０ｅ、１１０ｇおよび１１０ｈが、ダウンイベントをゆっくりと処理する。しかしながら、メッシュルータ１１０ｄが何らの通知もなく突然ダウンする場合には、メッシュルータ１１０ｅ、１１０ｇおよび１１０ｈが、メッシュルータ１１０ｄに対する接続をタイムアウトするために、タイムアウトメカニズムに頼る必要がある。
【００７９】
メッシュルータ１１０ｄへのリンクがダウンした後に、メッシュルータ１１０ｇのＰＤＦが再び無限大になる。このことは、メッシュルータ１１０ｄへのリンクが、メッシュルータ１１０ｇからポータル１１０ａへの唯一のリンクだからである。リンクがダウンした後に、メッシュルータ１１０ｇの他のリンク（すなわち、メッシュルータ１１０ｈへのリンク）が有限のＰＤＦを有し得る。この場合において、メッシュルータ１１０ｇは、ポータル１１０ａへの新しい経路を見出すために、ＤＩＳＣＯＶＥＲＩＮＧ状態に入る。メッシュルータ１１０ｂと１１０ｈとが見出されたと仮定する。メッシュルータ１１０ｂが、メッシュルータ１１０ｈよりも小さいＰＤＦを有するので、メッシュルータ１１０ｇは、メッシュルータ１１０ｂを選ぶリンク確立要求を送出する。メッシュルータ１１０ｂが、新しいリンクを受容するための帯域幅をまだ有する場合には、それはメッシュルータ１１０ｇの要求を受容する。そうでなければ、メッシュルータ１１０ｇは、メッシュルータ１１０ｂとのいくつかのリトライの後、メッシュルータ１１０ｈを試みる。プロセスを容易にするために、メッシュルータ１１０ｂは、最初の試行の後にメッシュルータ１１０ｇに拒絶を送り返し得、メッシュルータ１１０ｇは、そのリトライなしにメッシュルータ１１０ｈを試すことができる。
【００８０】
メッシュルータ１１０ｂがメッシュルータ１１０ｇの要求を受容するときには、新しいリンクが確立され、メッシュルータ１１０ｇは、そのＰＤＦを適切に更新する。メッシュルータ１１０ｄがダウンした後、メッシュルータ１１０ｅは、ＤＩＳＣＯＶＥＲＩＮＧ状態に帰る必要がない。なぜならば、メッシュルータ１１０ｅが、ルータ１１０ｃメッシュへのバックアップリンクを有するからである。メッシュルータ１１０ｅは、そのＰＤＦを状況に応じて更新し、ポータル１１０ａに到達するために、メッシュルータ１１０ｃへのリンクを用いる。ＰＤＶプロセスが用いられる場合には、経路情報もまた更新される。メッシュルータ１１０ｈはまた、メッシュルータ１１０ｅへのバックアップリンクを有する。メッシュルータ１１０ｈは、このリンクを用い、状況に応じてそのＰＤＦを更新する。
【００８１】
経路距離係数（ＰＤＦ）を用いるメッシュ状ネットワークにおける無線周波数管理（ＲＦＭ）のための方法およびシステムが開示されてきた。本発明の好適な実施形態が、例示され、そして詳細に記載されたけれども、本発明の精神または添付の特許請求の範囲から逸脱することなくその内において、様々な修正が行われ得ることが当業者に対して容易に明らかとなるであろう。
【図１】
2010519833.tif 000004
【図２】
2010519833.tif 000005
【図３】
2010519833.tif 000006
【図４】
2010519833.tif 000007
【図５】
2010519833.tif 000008
【図６】
2010519833.tif 000009
【図７】
2010519833.tif 000010
【国際調査報告】
2010519833.tif 000011