メッシュ・ネットワークにおけるデータの許可制御のための方法および装置
【課題】新たなトラフィックストリームを収容するために利用可能なローカル無線帯域幅を決定する。
【解決手段】メッシュ・ネットワーク内のトラフィッ・ストリームを制御する装置および方法は、第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信することと、第２のノードのトラフィック負荷を判定することと、このトラフィック負荷を用いて、第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することとを備える。
【解決手段】メッシュ・ネットワーク内のトラフィッ・ストリームを制御する装置および方法は、第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信することと、第２のノードのトラフィック負荷を判定することと、このトラフィック負荷を用いて、第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することとを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュ・ネットワークに関し、更に詳しくは、メッシュ・ネットワークにおけるデータの許可制御のための方法および装置に関する。
【背景技術】
【０００２】
近年、高速データ・サービスへの広範囲なアクセスに対する需要が増加した。電気通信業界は、様々な無線製品およびサービスを提供することにより、要求の増加に応えた。これらの製品とサービスとを相互に運用可能にするために、電気電子技術者協会（ＩＥＥＥ）は、例えばＩＥＥＥ ８０２．１１のような無線ローカル・エリア・ネットワーク（ＷＬＡＮ）規格のセットを発布した。これらの規格に準拠する製品およびサービスは、無線によるポイント・トゥ・マルチポイント・コンフィグレーションで頻繁にネットワーク化される。１つのコンフィグレーションでは、それぞれ利用可能な帯域幅を共有する個々の無線デバイス（例えば、局）は、インターネット・アクセス・ポイントと直接的に通信することができる。
【０００３】
他のコンフィグレーションは、メッシュ・ネットワークでありうる。メッシュ・ネットワークは、多数の無線ノードを有する分散型ネットワークでありうる。各ノードは、トラフィック、送信ストリームまたは伝送ストリーム（ＴＳ）を受信することができ、また、次のノードへＴＳを中継することができる。ＴＳは、ノードからノードへ「ホッピング」することにより、始点ノードから宛先ノードへ進むことができる。ＴＳルーティング・アルゴリズムは、ＴＳが始点ノードから宛先ノードへと効率的にルーティングされることを保証する。ＴＳルーティング・アルゴリズムは、メッシュ・ネットワークにおける変化に動的に適応し、メッシュ・ネットワークをより効率的かつより回復力を高くすることが可能である。例えば、ノードがかなり混雑していてＴＳを取り扱うことができないか、ノードがメッシュ・ネットワークから出るイベントでは、ＴＳルーティング・アルゴリズムは、ＴＳを、ネットワーク内の他のノードを通じて宛先ノードへルーティングすることができる。
【０００４】
メッシュ・ネットワークは、異なる動作特性を備えたノードの階層を含むことができる。幾つかのメッシュ・ネットワーク・アーキテクチャでは、階層の最下部におけるノードは、局を含むことができる。局は、例えばラップトップ・コンピュータまたはパーソナル・デジタル・アシスタントのような個別の無線デバイスを含むことができる。メッシュ・ポイントは、局の上層であると考えられるノードを含むことができる。メッシュ・ポイントはまた、無線バックボーンを形成することができる。メッシュ・ポイントは、他のメッシュ・ポイントとの間でＴＳを送受信することができる。特別タイプのメッシュ・ポイントであるメッシュ・アクセス・ポイント（ＭＡＰ）は、局とメッシュ・ポイントとの間のゲートウェイまたは接続パスを提供することができる。メッシュ・アクセス・ポイントによって、ＴＳは、局とメッシュ・ポイントとの間で「ホップ」することができる。もう１つの特別タイプのメッシュ・ポイントであるメッシュ・ポータルは、例えば８０２．１１（ａ／ｂ／ｇ／ｎ）のような異なる無線規格に準拠するデバイスのためのゲートウェイを提供することができる。メッシュ・ポータルによって、非メッシュ・ネットワークからのＴＳが、メッシュ・ネットワークに入ったり、メッシュ・ネットワークから出ることができる。
【０００５】
８０２．１１に準拠する通信デバイスは、ＴＳに対する異なるサービス品質（ＱｏＳ）要求を持つことができる。ＱｏＳは、例えば、途切れたパケット数、パケット遅延時間、パケット・ジッタ、無秩序に配信されたパケット数、誤って受信されたパケット数のような多くのパラメータを含みうる。これらのパラメータを使用して、異なる通信デバイスについて、ユーザおよびアプリケーションが異なるＱｏＳを必要とすることがわかる。例えば、インターネット・テレフォニーは、双方向の会話が理解できるように、パケット遅延時間が短く、パケット・ジッタが小さいＱｏＳを必要としうる。ストリーミング・ビデオ講義も、見苦しくないビデオ・イメージおよびコヒーレントな一方向オーディオ・トラックを提供するために、小さなパケット・ジッタを必要とするが、長いパケット遅延を許容することができる。アプリケーション、ユーザ、および通信デバイスのダイバーシティが増加すると、ＱｏＳ要求は、更に重要かつ複雑になり始めうる。例えば、２つの異なる地理的領域における２人の間のリアル・タイム対話型ゲームは、非常に複雑で厳格なＱｏＳ要求を有しうる。
【０００６】
メッシュ・ネットワークにおける無線デバイスの大規模な配置は、多様なＱｏＳ要求および優先度を用いて、ＴＳの許可制御を行うことを含むネットワーク設計に対するチャレンジを提起する。
【発明の概要】
【０００７】
（３５Ｕ．Ｓ．Ｃ．§１１９の下の優先権主張）
本願は、本明細書の譲受人に譲渡され、本明細書において参照によって明確に組み込まれている２００５年１０月１８日出願の米国特許仮出願６０／７２８、２４７号の優先権を主張する。
【０００８】
メッシュ・ノード周辺のトラフィック負荷情報は、知られているか、または、比較的容易に判定されうる。メッシュ・ノードは、ノードの各々において、新たなトラフィック・ストリーム（ＴＳ）を収容するために利用可能なローカル無線帯域幅を決定するために、トラフィック負荷情報を用いることができる。ＴＳルーティング・アルゴリズムは、メッシュ・ノードを介した新たなＴＳのための可能なルートを評価することができる。始点ノードは、可能なＴＳルートとともに、新たなＴＳに対する許可要求を行うことができる。この許可は、始点ノードから宛先ノードへとノード毎に送られる。許可要求を受信する各ノードは、この許可要求を、ローカル・トラフィック負荷情報と比較し、新たなＴＳを収容することができるかを判定する。ＴＳを収容することができる場合、送信機会（ＴＸＯＰ）が無視され、許可要求が、可能なルートに沿って次のノードへと伝えられる。ＴＳを収容することができない場合、ＴＳ要求が拒否され、許可要求が、その他の可能なルートに沿って伝えられる。
【０００９】
メッシュ・ネットワークにおいてトラフィック・ストリームを制御する方法は、第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を第２のノードにおいて受信することと、第２のノードのトラフィック負荷を判定することと、このトラフィック負荷を用いて、第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することとを備える。
【００１０】
権利要求される主題が特に指摘され、明細書の結論において明確に権利要求される。しかしながら、そのような主題は、添付図面ととともに解釈される場合、以下の詳細記載を参照して理解されうる。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施形態に従った典型的なメッシュ・ネットワークの図である。
【図２】図２は、実施形態に従った典型的なメッシュ・ノードにおいて送受信されるトラフィック・ストリーム（ＴＳ）を示す図１の典型的なメッシュ・ネットワークの部分図である。
【図３】図３は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図４】図４は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図５】図５は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図６】図６は、実施形態に従って、可能なＴＳルートに沿った第１のノードにおけるＴＳの許可制御を例示するＴＳフロー図である。
【図７】図７は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御を例示するＴＳフロー図である。
【図８】図８は、実施形態に従って、可能なＴＳルートに沿った宛先ノードにおけるＴＳの許可制御を例示するフロー図である。
【図９】図９は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御の方法を例示するフロー図である。
【図１０】図１０は、実施形態に従った許可制御装置のための典型的な構成要素および手段を例示するブロック図である。
【発明を実施するための形態】
【００１２】
本開示の様々な機能の実施形態を実現する方法および装置が、図面に関連付けられて記載される。図面および関連する説明は、本開示の実施形態を例示するためであって、本開示の範囲を限定しないように提供される。「１つの実施形態」あるいは「実施形態」に対する明細書中の参照は、実施形態に関連して記載される具体的な特徴、構造、特性が、本開示の少なくとも１つの実施形態に含まれることを示すことが意図されている。明細書中の様々な場所におけるフレーズである「１つの実施形態において」または「実施形態」は、必ずしも全てが同じ実施形態を参照している必要はない。図面の全体にわたって、参照された要素間の対応を示すために参照番号が再使用される。更に、各参照番号の最初の桁は、その要素が最初に現れた図を示す。
【００１３】
図１は、実施形態に従った典型的なメッシュ・ネットワーク１００の図である。メッシュ・ネットワーク１００は、メッシュ・ノードからなる階層ネットワークであり、例えば、第１のノード１０１から第２３のノード１２３まで含みうる。凡例１３０によってこの本実施形態で示されるように、ネットワーク１００は、多くの異なるタイプのノードおよびデバイスを含みうる。メッシュ・ネットワーク１００は、例えば、第１のノード１０１から第１４のノード１１４までのような複数の局（ＳＴＡ）を含みうる。１つの実施形態では、１つの局（例えば１０１）は、別の局（例えば１０２）と関連していなくてもよい。局は、メッシュ・ネットワーク１００の無線規格に従うあらゆるデバイスでありうる。局は、例えば、コンピュータ、携帯情報端末、ネットワーク・ゲーム・デバイス、電話、テレビ、あるいは端末を含みうる。メッシュ・ネットワーク１００の無線規格は、任意の所有権付き規格、および／または、限定される訳ではないが、例えばＩＥＥＥ ８０２．１１規格のようなオープン・アーキテクチャ規格でもありうる。
【００１４】
メッシュ・ネットワーク１００は、例えばノード１１５−１１７および１１９のような１または複数のＭＡＰを含むことができる。局は、メッシュ・ネットワーク階層のベースを形成することができ、また、例えばメッシュ・アクセス・ポイント（ＭＡＰ）およびメッシュ・ポータルのようなゲートウェイ・ノードを介し、階層内のより高次のメッシュ・ノードにアクセスすることができる。ノード１０２のような局は、直接通信リンク１３４によって、例えばノード１１５のようなＭＡＰにアクセスすることができる。通信リンク１３４は、有線、無線、および／またはこれらの組み合わせでありうる。ノード１０１のような局は、ノード１０１からノード１１５およびノード１２２へ移動することによって、例えばノード１２２のようなメッシュ・ポイントへアクセスすることができる。
【００１５】
メッシュ・ポータルは、図１に示すような非メッシュ・デバイスと通信するノードを含むことができる。メッシュ・ネットワーク１００は、例えばノード１１８のような１または複数のメッシュ・ポータルを含むことができる。例えばノード１１８のようなメッシュ・ポータルは、例えばデバイス１４１−１４５のような非メッシュ・デバイスと通信することができる。非メッシュ・デバイスは、例えばイーサネット（登録商標）接続のような非メッシュ接続１１４を特徴付けるローカル・エリア・ネットワーク内にネットワークされうる。例えば、非メッシュ・デバイス１４１−１４５は、ツイスト・ペア銅線を用いて、星型コンフィグレーションで有線化することができる。非メッシュ・デバイス１４１−１４５の各々は、メッシュ・ネットワーク１００のプロトコルに準拠することができる場合もできない場合もある。
【００１６】
実施形態では、ノード１１８は、イーサネット・ハブであっても、メッシュ・ネットワーク・プロトコルに従うこともできる。ノード１１８は、非メッシュ・デバイス１４１−１４５の各々を始点とするＴＳが、メッシュ・ネットワーク１００内に移動できるようにすることができる。このように、メッシュ・ポータル１１８は、非メッシュ・デバイス１４１−１４５のためのメッシュ・ネットワーク１００ゲートウェイとなることができる。メッシュ・ポータル１１８および非メッシュ・デバイス１４１−１４５を特徴付けるネットワークは、イーサネット・ネットワークに制限されることはなく、その他のネットワークも構成され、同様に動作することができる。非メッシュ・デバイス１４１−１４５は、限定される訳ではないが、例えば、トークン・リング・ネットワーク、および／または８０２．１１ポイント・トゥ・マルチポイント・ネットワークおよび／またはこれらの組み合わせのような多くの異なるタイプのネットワークで構成されうる。
【００１７】
メッシュ・ポータル１１８は更に、例えばノード１１９を経由して、インターネットまたはその他の広域ネットワークへのリンクを有することができる。ノード１１９は、インターネット・バックボーンに接続されることができ、これによって、ノード１１９は、メッシュ・ポータルのみならずインターネット・アクセス・ポイントとなる。ノード１１９は、無線メッシュ・ネットワーク１００とインターネットとの間のブリッジを形成することができる。ブリッジは、メッシュ・ネットワーク１００内のノードのうちのいずれかと、インターネット可能デバイスとの間の接続として動作することができる。
【００１８】
メッシュ・ポイントは、他のメッシュ・ポイント、ＭＡＰ、および／またはメッシュ・ポータル間でデータを中継するノードを含むことができる。メッシュ・ネットワーク１００は、例えばノード１２０−１２３のような１または複数のメッシュ・ポイントを含むことができる。メッシュ・ポイント、ＭＡＰ、およびメッシュ・ポータルは、メッシュ・ネットワーク１００階層内のメッシュ・ノードの上部レイヤを形成することができる。局および非メッシュ・デバイスを始点とするＴＳは、メッシュ・ポータルおよびＭＡＰを介してこの上部レイヤに入ることができる。ＴＳは、他のメッシュ・ポータルおよび／またはＭＡＰを介して出て行くまで、メッシュ・ネットワーク１００の上部レイヤのノードに沿って移動する。
【００１９】
図１はまた、ＭＯと示すような典型的なトラフィック・ストリーム（ＴＳ）のルーティングをも示している。実施形態では、ＴＳ ＭＯは、メッシュ・ネットワーク１００内のノード１０８（例えば、局１０８）を始点とすることができる。ＴＳ ＭＯはまた、メッシュ・ネットワーク１００内のノード１１３（例えば、局１１３）を始点とすることもできる。ノード１０８からノード１１３への適切なＴＳルートは、ルーティング・アルゴリズムを用いて決定することができる。適切なＴＳルートが決定された後、アクセスおよびＴＸＯＰが、このルートに沿った各ノードにおいてネゴシエートされる。その後、ＴＳ ＭＯは、このルートに沿って送信されうる。ノード１０８は、ＴＳ ＭＯを、第１のホップＨ１で、ノード１１６へ送信することができる。ノード１１６は、ＴＳ ＭＯを受信することができる。そして、さらに、ＴＳ ＭＯを、第２のホップＨ２で、ノード１１７へ送信することができる。ノード１１７は、ＴＳ ＭＯを受信することができる。そして、ＴＳ ＭＯを、第３のホップＨ３で、ノード１２０へ送信することができる。ノード１２０は、ＴＳ ＭＯを受信することができる。そして、ＴＳ ＭＯを、第４のホップＨ４で、ノード１１９へ送信することができる。ノード１１９は、ＴＳ ＭＯを、この実施形態では最後である第４のホップＨ５で、ノード１１３へ送信することができる。
【００２０】
図２は、典型的なメッシュ・ノード１２０において送受信されるＴＳを示す図１の典型的なメッシュ・ネットワーク１００の部分図である。この実施形態では、ノード１２０は、他の４つのノード１１７、１１９、１２１および１２２との間でＴＳを送受信することができる。ノード１２０は、これらの４つのノードのネットワーク近傍にあると言うことができる。この実施形態では、ノード１２０は、ノード１１７、１２１および１２２から、ＴＳ Ｒ１７、Ｒ２１およびＲ２２をそれぞれ受信することができる。更に、ノード１２０は、ノード１１７、１１９および１２１に、ＴＳ Ｔ１７、Ｔ１９およびＴ２１をそれぞれ送信することができる。この例において、ノード１１７、１１９または１２１は「リーフ」ノードではなく、ＴＳ Ｒ１７、Ｒ２１およびＲ２２と、Ｔ１７、Ｔ１９およびＴ２１とは、ノード１１７、１１９または１２１におけるその他のＴＳのアグリゲートでありうることに注目されたい。
【００２１】
ノード１２０におけるトラフィックは、２つのベクトル（すなわち、送信ベクトルおよび受信ベクトル）によって表すことができる。実施形態では、ＴＳは、例えば、スケジュールされたサービス間隔（ＳＳＩ：scheduled service interval）のような確立された期間にわたって、ＴＳに関連付けられたデータを送信するために、チャネルを占有する時間割合によって表されうる。このコンテクストにおけるトラフィック負荷または媒体占有は、例えば、スケジュールされたサービス間隔（ＳＳＩ）のような確立された時間間隔にわたってビジー（busy）であるとしてチャネルにおける占有された時間長さを示すｔｂｕｓｙのような量によって表されうる。従って、送信ベクトルＴ２０（２１０と示される）は、４つの要素を有する。第１の要素は、ＴＳ Ｔ１７をノード１２０からノード１１７へ送信するための時間ｔＴ１７であり、第２の要素は、ＴＳ Ｔ１９をノード１２０からノード１１９へ送信するための時間ｔＴ１９であり、第３の要素は、ＴＳ Ｔ２１をノード１２０からノード１２１へ送信するための時間ｔＴ２１であり、第４の要素は、ＴＳ Ｔ２２をノード１２０からノード１２２へ送信するための時間ｔＴ２２である。この例において、送信ベクトルＴ２０ ２１０の第４の要素ｔＴ２２は、ゼロであろう。なぜならノード１２０は、ノード１２２に何れのＴＳも送信しないからである。ここで、ｔＴ１７は、ＳＳＩ毎に、ＴＳ Ｔ１７の送信のためにチャネルにおいて占有される時間である。
【００２２】
同様に、受信ベクトルＲ２０（２１２と示される）は、４つの要素を有する。第１の要素は、ＴＳ Ｒ１７をノード１１７から受信するための時間ｔＲ１７であり、第２の要素は、ＴＳ Ｒ１９をノード１１９から受信するための時間ｔＲ１９であり、第３の要素は、ＴＳ Ｒ２１をノード１２１から受信するための時間ｔＲ２１であり、第４の要素は、ＴＳ Ｒ２２をノード１２２から受信するための時間ｔＲ２２である。この例において、受信ベクトルＲ２０ ２１２の第２の要素ｔＲ１９は、ゼロであろう。なぜならノード１２０は、ノード１１９から何れのＴＳも受信しないからである。ここで、ｔＲ１７は、ＳＳＩ毎に、ＴＳ Ｒ１７の送信のためにチャネルにおいて占有される時間である。
【００２３】
ノード１２０周辺の媒体が、ノード１２０またはその他任意のノードにおいて、ＳＳＩの一部として負荷がかけられたと考えられる時間長さのようなトラフィック負荷（ｔｌｏａｄ）は、測定を含む様々な方法で判定することができる。実施形態では、ノード１２０は、ビジー時間（ｔｂｕｓｙ）を判定するために、ノード１２０の物理レイヤ（ＰＨＹ）によって検出されるようなクリア・チャネル・アセスメント（ＣＣＡ）ビジー表示をモニタすることができる。ＣＣＡビジー表示が、このチャネルがビジーではないことを示す場合であっても、ノード１２０は、ノード１２０が送信しない時間割合を示すネットワーク割当ベクトルの静寂時間（ｔｑｎａｖ）をモニタすることができる。ネットワーク割当ベクトル（ＮＡＶ）は、周囲のノードからの条件を処理することによって得られる。ノード１２０に接続されたノード１１７、１１９、１２１、１２２が、ノード１２０以外のノードからの通信を受信することができるように、静寂時間（ｔｑｎａｖ）は、チャネルが利用可能ではない時間を表すことができる。静寂時間（ｔｑｎａｖ）およびＣＣＡビジー表示によってチャネルが利用可能ではない時間長さは、トラフィック負荷（ｔｌｏａｄ）である。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷（ｔｌｏａｄ）は、以下の式によって表わすことができる。
【００２４】
ｔｌｏａｄ＝ｔｂｕｓｙ＋ｔｑｎａｖ
図３は、典型的なノード１２０と、典型的なノード１２０の近隣のノード１１７、１１９、１２１および１２２の各々のトラフィック・フロー情報を示す図１のメッシュ・ネットワーク１００の部分図である。実施形態では、近隣ノードは、ノードの１つの通信リンク内のノードとして定義することができる。ノード１２０の近隣ノードは、ノード１１７、１１９、１２１および１２２である。従って、図３は、ＴとＲ、および、ノード１２０とその近隣ノード１１７、１１９、１２１、１２２のおのおのの送受信のためにＳＳＩの間に費やされる時間部分を決定するために必要なノードを示す。実施形態では、各ノードは、ノードのビーコンの一部としてＴおよびＲを送信することができる。各ノードはまた、近隣ノードからトラフィック負荷情報を受信するために、他のノードのビーコンをモニタすることができる。例えば、ノード１２０は、ＴとＲのペアであるＴ２０およびＲ２０を送信することができる。Ｔ２０およびＲ２０は、ノード１２０の近隣ノードによってモニタされる。近隣ノード１１７、１１９、１２１および１２２はまた、他のノードがこれらパラメータをモニタできるように、それぞれのＴとＲのペア、すなわち、Ｔ１７とＲ１７、Ｔ１９とＲ１９、Ｔ２１とＲ２１、および、Ｔ２２とＲ２２を他のノードに送信することができる。
【００２５】
ノードはそれぞれ、近隣ノードのビーコンをモニタすることによって、ローカルなＴＳトラフィック負荷、そしてその利用可能な帯域幅を決定することができる。ノードの近隣におけるローカルなＴＳトラフィック負荷は、送受信マトリクス・ペアＴＸ、ＲＸを形成することによって判定されうる。ＴＸ、ＲＸペアのローおよびカラムは、メッシュ・ネットワーク１００内のノードの送信パラメータおよび受信パラメータに対応する。ＴＸおよびＲＸはその後、近隣ノードの各々から受信された個々のＴとＲのペアからの情報で埋められる。Ｔ、Ｒ、ＴＸ、およびＲＸはそれぞれ、値、ベクトル、またはマトリクスを表す。
【００２６】
例えば、ノード１２０は、近隣ノードの各々のビーコンをモニタすることができる。ノード１２０は、ノード１１７からＴ１７とＲ１７のペアを、ノード１１９からＴ１９とＲ１９のペアを、ノード１２１からＴ２１とＲ２１のペアを、ノード１２２からＴ２２とＲ２２のペアを受信することができる。ノード１２０は、ＴＸ２０とＲＸ２０とのマトリクスを埋めるために、受信したＴとＲのペアを解析することができる。ＴＸ２０とＲＸ２０の各ローおよびカラムは、メッシュ・ネットワーク１００のノードと少なくとも部分的に対応することができる。例えば、ＴＸ２０のロー１７、カラム１６は、ＴＳがノード１１７からノード１１６へ送信される時間長さで埋めることができる。この時間情報はまた、ノード１１７の送信ベクトルＴ１７と、ノード１１６の受信ベクトルＲ１６においても利用可能である。同様に、ＲＸ２０のロー２１、カラム２２は、ノード１２１がノード１２２からＴＳを受信する時間長さで埋められる。この時間情報はまた、ノード１２１の受信ベクトルＲ２１とノード１２２の送信ベクトルＴ２２においても利用可能である。
【００２７】
ノード１２０の周囲のトラフィック負荷は、ＴＸ２０およびＲＸ２０の各送信受信ペアについて最大値を合計することによって、ＴＸ２０およびＲＸ２０から判定することができる。例えば、ＴＳがノード１２１からノード１２２へ送信されるのに要する時間長さを表すＴＸ２０のロー２１、カラム２２は、ノード１２２がノード１２１からＴＳを受信するのに要する時間長さを表すＲＸ２０のロー２２、カラム２１と比較されうる。ＴＸ２０とＲＸ２０からなる各送信受信ペアの最大値は、ノード１２０における新たなＴＳについて、送信媒体が利用できないために、利用不可能な時間長さを表す。例えば、ロー２１、カラム２２の最大値は、送信媒体が利用できない時間長さをノード１２０に示すことができる。なぜなら、ＴＳは、ノード１２１とノード１２２との間で送信されるからである。ＴＸ２０とＲＸ２０のペアにわたる最大値の合計は、ノード１２０におけるローカル・トラフィック負荷を判定するために、少なくとも部分的に使用されうる。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷は、以下の式を用いることによって少なくとも部分的に判定することができる。
【数１】
【００２８】
その後、トラフィック負荷は、新たなＴＳを許可するために、ノード１２０の周囲で利用可能な適切なチャネル帯域幅が存在するかを判定するために、ノード１２０によって使用することができる。ノード１２０は、ノード１２０または近隣ノードにおいて送受信される他のＴＳと干渉することなく新たなＴＳが収容されることを保証することができる。ノード１２０がＴＳ許可要求を受信する場合、ノード１２０は、この許可要求を、ノード１２０におけるトラフィック負荷と比較し、ノード１２０またはノード１２０の近傍において、他のＴＳと干渉することなくＴＳを受信し、ＴＳをルート内の次のノードに送信することができるかを判定することができる。ノード１２０が新たなＴＳを収容することができる場合、ノード１２０はＴＳを許可することができる。ノード１２０が新たなＴＳを収容することができない場合、ノード１２０はＴＳを拒否することができる。そして、前のノードは、宛先ノードへの次の最も適切なルートおよび／または他の適切なルートを決定するために、ルーティング・アルゴリズムを起動することができる。これによって、ノード１２０を効果的にバイパスする。
【００２９】
図４は、典型的なノード１２０と、この典型的なノード１２０の近傍ノード１１７、１１９、１２１、１２２のそれぞれのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの部分図である。ノード１１７、１１９、１２１および１２２の近傍も示されている。ノード１２０は、合計ベクトルＳ２０を、近傍ノードのおのおのに送信することができる。また、各近隣ノードは、Ｓ１７を送信するノード１１７、Ｓ１９を送信するノード１１９、Ｓ２１を送信するノード１２１、Ｓ２２を送信するノード１２２のように、それぞれの合計ベクトルＳを送信することもできる。Ｓの各要素は、ノードとその近隣ノードのそれぞれとの間の送信時間および受信時間の集合を含むことができる。実施形態では、ノード１２０のＳ２０ベクトルは、４つの要素を含む。ここで、各要素は、ノード１２０の、近隣ノードのそれぞれとの送信時間と受信時間との合計を表す。第１の要素は、ノード１１７との送信時間と受信時間との合計であり、第２の要素は、ノード１１９との送信時間と受信時間との合計であり、第３の要素は、ノード１２１との送信時間と受信時間との合計であり、第４の要素は、ノード１２２との送信時間と受信時間との合計である。
【００３０】
実施形態において、ＴＸとＲＸの代わりにＳを送信することの１つの利点は、Ｓのサイズが、ＴＸおよびＲＸのサイズのほとんど半分と、小さくなることである。これは、トラフィック負荷情報を送信するために必要な時間および帯域幅を低減することができる。特に、高次のネットワーク・グラフを有するビジーなノード（多くの近隣を有するノード）にとって、オーバヘッドは深刻である。
【００３１】
ノード１２０は、ノード１２０の近隣ノードの送信をモニタし、近隣ノードの各々についてのＳベクトルを格納する。ノード１２０のトラフィック負荷は、メッシュ・ネットワーク１００内のメッシュ・ノードを表すローとカラムの各々を備えた負荷マトリクスＳＴを構築することによって判定されうる。負荷マトリクスＳＴは、ノード１２０の近隣ノードの各々についての送信時間と受信時間との合計で埋められうる。実施形態では、負荷マトリックスＳＴのロー２１は、ノード１２１からのＳベクトルを表わすＳ２１の要素で埋められうる。負荷マトリクスＳＴのロー２１、カラム２２は、ノード１２１とノード１２２との送信時間と受信時間との合計に対応するＳ２１の要素で埋められうる。その後、送信ロー・カラム・ペアと受信ロー・カラム・ペアとを比較し、相対的な最大値を選択することによって、ノード１２０の周囲のトラフィック負荷が、少なくとも部分的に判定されうる。例えばＳＴのロー２１、カラム２２は、ＳＴのロー２２、カラム２１と比較され、相対的な最大値が、負荷判定のために使用されうる。その後、全てのロー・カラム・ペア比較の合計が、ノード１２０の周囲のトラフィック負荷を判定するために少なくとも部分的に使用される。メッシュ・ネットワーク１００内の任意のノードの周囲のトラフィック負荷は、以下の式によって少なくとも部分的に判定される。
【数２】
【００３２】
計算されたトラフィック負荷情報は、新たなＴＳが許可されるかを判定するために、ノード１２０によって使用されうる。ノード１２０がＴＳ許可要求を受信した場合、ノード１２０は、この許可要求をトラフィック負荷と比較し、ノード１２０がＴＳを受信できるかを判定し、ノード１２０またはその近隣における他のノードにおいて他のＴＳを危険にさらすことなく、このＴＳをルート内の次のノードに転送する。ノード１２０が、ＴＳを受信し、転送することができるのであれば、ノード１２０は、ＴＳを許可することができる。ノード１２０が、ＴＳを受信することも、転送することもできないのであれば、ノード１２０は、ＴＳを拒否し、前のノードが、ノード１２０をバイパスするルーティング・アルゴリズムを起動することができる。従って、実施形態では、メッシュ・ネットワーク１００のノードは、近隣におけるトラフィック負荷を測定または計算し、そして、許可制御を実行するために、トラフィック負荷情報を用いることができる。
【００３３】
図５は、実施形態に従った、典型的なノード１２０と、典型的なノードの近隣のノード１１７、１１９、１２１、１２２の各々とのトラフィック・フロー情報を示す図１のメッシュ・ネットワーク１００の部分図である。メッシュ・ネットワーク１００の各ノードの周囲のトラフィック負荷は、スカラ・パラメータの近隣ノードの測定およびモニタリングによって判定することができる。ノード１１７、１１９、１２１および１２２の近隣も図５で示される。実施形態では、これらノードの各々は、例えばビジー時間のようなパラメータをブロードキャストすることができる。これらノードの各々は、各ＰＨＹによって検出されたようなチャネル・ビジー時間を測定することができる。その後、チャネル・ビジー時間は、これらノードの各々によってブロードキャストされる。
【００３４】
ノード１２０は、１または複数のビーコン間隔にわたるビジー表示のために、ＰＨＹをモニタすることができる。ノード１２０のＰＨＹが、チャネルがビジーであることをレポートする時間長さＴであるＴ２０がブロードキャストされうる。同様に、ノード１２０の近隣ノードは、チャネルがビジーであるとそれぞれのＰＨＹが示す時間長さを決定するために、それぞれのＰＨＹをモニタすることができる。これら近隣ノードはまた、測定されたビジー時間をブロードキャストすることができる。Ｔ２０は、その近隣ノード１１７、１１９、１２１、１２２によって使用することができる。ノード１２０は、それぞれの近隣ノードから、Ｔ１７、Ｔ１９、Ｔ２１、Ｔ２２を受信することができる。ノード１２０は、平均的な静寂ネットワーク・アクセス・ベクトル（ｔｑｎａｖ）時間もモニタすることができる。その後、ノード１２０は、Ｔ１、Ｔ２、Ｔ３およびＴ４を総和することにより、少なくとも部分的にノード１２０の周囲のトラフィック負荷を計算することができる。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷は、以下の式を用いて、少なくとも部分的に計算することができる。
【数３】
【００３５】
その後、トラフィック負荷は、新たなＴＳを許可する能力を判定するために、ノード１２０によって利用されうる。ノード１２０は、新たなＴＳが、近隣ノードにおいて現在送信され受信されているＴＳを危険にさらさないことを保証することができる。ノード１２０がＴＳ許可要求を受信する場合、ノード１２０は、この許可要求をトラフィック負荷と比較し、ノード１２０がＴＳを受信できるかを判定し、このＴＳを、他のＴＳを危険にさらすことなく次のノードへ転送することができる。ノード１２０が新たなＴＳを許可することができると判定された場合、ノード１２０はＴＳを許可することができる。ノード１２０が新たなＴＳを許可できないと判定された場合、ノード１２０は、ＴＳを拒否し、前のノードは、ノード１２０をバイパスするルーティング・アルゴリズムを実施することができる。
【００３６】
図６は、実施形態に従って、可能なＴＳルートに沿った第１のノード１１６におけるＴＳの許可制御を例示するＴＳフロー図である。実施形態では、始点局ＭＯであるノード１０８は、宛先局ＭＤであるノード１１３への可能なルートを決定するために、ルート・アルゴリズムを利用することができる。ノード１０８は、上述した方法のうちの１つに従って、トラフィック負荷を評価または判定することができる（９０４）。ノード１０８は、アプリケーションに特有な適切なルートを選択することができる。例えば、このルートは、次のホップへの距離、次のホップ・ノードにおけるトラフィック負荷、次のホップ・ノードの程度、および／またはその他の判定基準、および／またはこれらの組み合わせに基づいて選択することができる。
【００３７】
実施形態では、Ｈ１のスケジュール・サービス間隔（ＳＳＩ）中に転送されるメディア・アクセス制御（ＭＡＣ）サービス・データ・ユニット（ＭＳＤＵ）パケットの平均数が
計算される。パケット（Ｎ）の平均数は、公称パケット・サイズ（Ｌ）で除されたＳＳＩと保証データ・レート（Ｇ）との積でありうる。パケットの平均数は、下記式を用いることによって、少なくとも部分的に計算することができる。
【数４】
【００３８】
ダウンストリームＴＸＯＰでは、Ｈ１に必要とされるデータ送信のためにＳＳＩ毎にスケジュールされた時間部分も計算することができる。この場合、我々は、簡単な表記ＴＸＯＰを用いて期間ｔＴＸＯＰを示す。その計算は、Ｈ１に沿った既存のトラフィックに少なくとも部分的に依存する。既存のトラフィックが、ＭＯと同じクラスのＴＳを含んでおり、より短いＳＳＩを必要としない場合、ＭＯからのデータ・パケットは、追加オーバヘッドに対する必要なしで、既存のＴＳとともに集められる。実施形態では、Ｈ１のＴＸＯＰは、物理的送信レート（Ｒ）によって除された許容可能な最大ＭＳＤＵ（２３０４バイト）と、物理的送信レートによって除された公称パケット・サイズとデータ・パケットの平均数（Ｎ）との積とのうちの最大でありうる。ＴＸＯＰは、以下の式に少なくとも部分的に基づいて計算することができる。
【数５】
【００３９】
同じクラスのノード１０８とノード１１６との間に既存のＴＳがない場合、または、新たなデータ・ストリームがより小さなＳＳＩしか必要としない場合、ＴＸＯＰは、追加のクラスまたはより小さなＳＳＩを取り扱うための追加オーバヘッドを含みうる。より小さなＳＳＩは、データ・ビット毎のオーバヘッドが増加することを意味する。従って、より小さな数のホップを持つパスを選択することが望ましい。これによって、ネットワーク伝送能力全体を改善するのみならず、その効率をも高めることができる。この場合、ＴＸＯＰは、以下の式によって少なくとも部分的に決定することができる。
【数６】
【００４０】
ノード１０８における計画された全ダウンストリーム・トラフィック負荷は、Ｈ１のＳＳＩによって除されたＨ１のＴＸＯＰに、送信されるようにスケジュールされたその他全てのＴＳについて、各ＳＳＩによって除されたＴＸＯＰの総和を加えることによって少なくとも部分的に計算される。Ｈ１によるトラフィック負荷は、ノード１０８を出発するＴＳによる他の既存のトラフィック負荷とともに加えられる。ダウンストリーム・トラフィック負荷は、下記式によって少なくとも部分的に表すことができる。
【数７】
【００４１】
ノード１０８におけるアップストリーム・トラフィック負荷は変わらない。始点ではないノードについてのアップストリーム計算を以下に説明する。
【００４２】
ノード１０８は、ＭＯが収容されるかを判定するために、アップストリーム・トラフィック負荷と、ダウンストリーム・トラフィック負荷との合計を、予め定めた負荷しきい値と比較する。ＭＯが収容されると判定された場合、ノード１０８はＴＸＯＰを予約し、ビーコン信号内の負荷情報を更新し、ノード１１６へ許可要求を送る。ＭＯが収容されると判定されなかった場合、アクセスが拒否される。
【００４３】
実施形態では、ＴＸＯＰ計算およびしきい値は、ＱｏＳによって区分される。例えば、ノードは、トラフィックの３０％をＶＯＩＰタイプのＱｏＳに割り当て、１０％をリアルタイム・インタラクティブ・ゲーム・タイプのＱｏＳに割り当て、６０％をウェブ・ブラウジング・タイプのＱｏＳに割り当てる。その後、トラフィック負荷判定およびしきい値比較は、ＱｏＳ特有となりうる。データ・ストリームをサポートするのに十分な帯域幅がない場合、動的なＱｏＳ割り当てが行われうる。ノードは、別のＱｏＳのために区分された帯域幅の一部を、新たなデータ・ストリームのために再び割り当てることができる。
【００４４】
ノード１０８は、ダウンストリーム・ノードから許可の拒否を受け取るまで、ＴＸＯＰ予約を保持することができる。許可の拒否を受け取ると、始点局は、ＴＸＯＰ予約をキャンセルし、宛先局１１３への別のルートを決定するルーティング・アルゴリズムを起動することができる。適切なルートが見つかった場合、ノード１０８は、上述した許可処理を再開することができる。
【００４５】
図７は、実施形態に従って、可能なＴＳルートに従ったＴＳおよびＭＯの典型的なホップＨｉを示す。ノード１２０がノード１１７から許可要求を受け取ると、ノード１２０は、アップストリーム（第４のホップ）およびダウンストリーム（第３のホップ）のＴＸＯＰと、計画されたトラフィック負荷とを計算することができる。ノード１２０における許可制御の記述を簡略化および一般化するために、アップストリーム・ホップが、Ｈｉとして記述され、ダウンストリーム・ホップがＨｉ−１として記述される。ノード１２０の許可制御は、メッシュ・ネットワーク１００中の任意のＴＳの任意のノードまたはホップに適用されうる。
【００４６】
実施形態では、ＨｉのＳＳＩ中に転送されるＭＳＤＵパケットの平均数が計算される。パケットの平均数（Ｎ）は、保証されたデータ・レート（Ｇ）とＳＳＩとの積が、公称パケット・サイズ（Ｌ）で除されたものとなることができる。パケットの平均数は、以下の式によって少なくとも部分的に記述される。
【数８】
【００４７】
ＨｉのダウンストリームＴＸＯＰもまた計算することができる。この計算は、Ｈｉに沿った既存のトラフィックに少なくとも部分的に依存しうる。既存のトラフィックがＭＯと同じクラスのＴＳを含んでおり、より小さなＳＳＩを必要としないのであれば、Ｍからのデータ・パケットは、追加オーバヘッドに対する必要なしで、既存のＴＳとともに集められる。ＨｉのＴＸＯＰは、物理的送信レート（Ｒ）によって除された許容可能な相対的に最大のＭＳＤＵ（２３０４バイト）（Ｌｍａｘ）と、データ・パケットの平均数（Ｎ）と公称パケット・サイズとの積を物理的送信レートで除したものとのうちの最大値でありうる。ＴＸＯＰは、下記式に少なくとも部分的に基づいて記述することができる。
【数９】
【００４８】
ＴＸＯＰは、追加クラスまたはより小さなＳＳＩを取り扱うための追加オーバヘッドを含むことができる。この状態では、ＴＸＯＰは、下記式に少なくとも部分的に基づいて記述することができる。
【数１０】
【００４９】
ノード１２０において計画されたダウンストリーム・トラフィック負荷の合計は、Ｈｉについて、ＳＳＩによって除されたＴＸＯＰに、それぞれのノード１２０を出発するようにスケジュールされ、ＳＳＩによって除されたその他全てのトラフィック・ストリームのＴＸＯＰの総和を加えることによって少なくとも部分的に計算される。特に、Ｈｉによるトラフィック負荷は、近隣ノードｋのそれぞれ、すなわちノード１１７、ノード１１９、ノード１２１、およびノード１２２について、ノード１２０を出発するＴＳによるその他の既存のトラフィック負荷で合計される。ダウンストリーム・トラフィック負荷は、下記式に少なくとも部分的に基づいて記述される。
【数１１】
【００５０】
ノード１２０はまた、Ｈｉ−１のアップストリームＴＸＯＰを計算する。その計算は、リンクＨｉ−１に沿った既存のトラフィックに少なくとも部分的に基づくことができる。既存のトラフィックが、ＭＯと同じクラスのＴＳを含んでおり、より小さなＳＳＩを必要としないのであれば、ＭＯからのデータ・パケットは、追加のオーバヘッドのための必要性なく、既存のＴＳとともに集めることができる。Ｈｉ−１のＴＸＯＰは、物理的送信レート（Ｒ）によって除された最大許容可能なＭＳＤＵ（２３０４バイト）と、物理的送信レートによって除されたデータ・パケット平均数（Ｎ）と公称パケット・サイズとの積とのうちの最大値でありうる。ＴＸＯＰは、少なくとも部分的に以下の式に基づいて記述されうる。
【数１２】
【００５１】
ＴＸＯＰが、追加のクラスまたはより小さなＳＳＩを取り扱う追加オーバヘッドを含んでいるのであれば、ＴＸＯＰは、少なくとも部分的に以下の式に基づいて記述されうる。
【数１３】
【００５２】
ノード１２０における計画された全アップストリーム・トラフィック負荷は、Ｈｉ−１についてＳＳＩによって除されたＴＸＯＰに、ノード１２０に到着すると計画されたその他全てのトラフィック・ストリームの、各ＳＳＩによって除されたアップストリームＴＸＯＰの総和を加えることによって計算される。Ｈｉによるトラフィック負荷は、ノード１２０の近隣ｋの各々であるノード１１７、ノード１１９、ノード１２１、およびノード１２２からノード１２０に到着するＴＳによるその他の既存のトラフィック負荷と加算される。アップストリーム・トラフィック負荷は、少なくとも部分的に下記式に基づいて記載される。
【数１４】
【００５３】
ノード１２０は、上記計算を行った後に、アップストリーム・トラフィック負荷とダウンストリーム・トラフィック負荷との合計を、予め定めたしきい値と比較して、ＭＯが収容可能であるかを少なくとも部分的に判定することができる。ＭＯが収容可能であると判定された場合、ノード１２０は、ＴＸＯＰを予約し、そのビーコンにおける負荷情報を更新し、許可要求をノード１１９へ送る。ＭＯが収容可能ではないと判定された場合、アクセスが拒否され、ノード１２０は、ＴＳ ＭＯの許可を拒否するメッセージをノード１１７へ送る。
【００５４】
実施形態では、ＴＸＯＰ計算およびアクセスしきい値は、ＱｏＳによって区分されうる。トラフィック負荷判定およびしきい値比較は、ＱｏＳ特有でありうる。
【００５５】
図８は、宛先局であるノード１１３への最終ホップＨＤを示す。ＨＤのためのノード１１３における許可制御は、ダウンストリームＴＸＯＰ計算が省略されるという点を除いてホップＨｉのものと同じでありうる。次のホップ局への許可要求の発行も省略されうる。
【００５６】
Ｍ個のルートに沿ったノードの各々は、ダウンストリーム・ノードから許可の拒否を受け取るまで、それぞれのＴＸＯＰ予約を維持することができる。許可の拒否を受信すると、始点局は、ＴＸＯＰ予約をキャンセルし、宛先局であるノード１１３への別のルートを決定するためにルーティング・アルゴリズムを起動することができる。ルートに沿った各ノードの許可処理は、再度起動することができる。
【００５７】
メッシュ・ネットワーク１００またはノードのうちの何れかは、ＱｏＳ要求によってアクセスを区分することができる。ＱｏＳ許可制御の１つの方法は、ＴＳクラスを、例えば高優先度クラスや低優先度クラスのような多数のクラスへ分割するものである。高優先度クラスのＴＳは、ルートに沿ったそれぞれのノードにおいて、１つのＳＳＩ内でサービスされうる。最悪ケース遅延は、ホップ数にＳＳＩを掛けることにより計算されうる。例えば、音声アプリケーションでは、高々約５０ミリ秒の遅延時間しか許可されない。従って、高優先度のストリームは、約１０ミリ秒のＳＳＩを持つ高々５つのノードを介してルーティングされる。
【００５８】
図９は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御の方法を例示するフロー図である。ノードは、ＴＳ許可要求を受信する（９０２）。ＴＳ許可要求は、別のノードから送信されうる。あるいは、この許可要求は、ノード自体から出発するＴＳのためのものでありうる。このノードは、ノードの近隣のトラフィック負荷を判定することができる。ノードは、ノードにおける負荷を測定することによって、あるいはロードの近隣によって送信された情報からの負荷を判定することによって、トラフィック負荷を少なくとも部分的に判定することができる。トラフィック負荷計算および測定は、限定される訳ではないが、本明細書に記載した方法および／またはその均等物を含む様々な方法によって実施することができる。トラフィック負荷は、ノードの近隣から送信された測定値と結合されたノード自体における測定値から判定することができる。典型的なハイブリッド・トラフィック負荷計算も上述される。これもまた、トラフィック負荷を判定するために利用することができる。
【００５９】
ノードは、ＴＸＯＰを決定する（９０６）。ノードが始点ノードである場合、ダウンストリームＴＸＯＰを計算することができる。ノードが宛先ノードである場合、アップストリームＴＸＯＰを計算することができる。ノードが中間ノードである場合、アップストリームＴＸＯＰおよびダウンストリームＴＸＯＰを計算することができる。ノードは、ＴＸＯＰを、利用可能なＴＸＯＰと比較することができる（９０８）。利用可能な適切なＴＸＯＰが存在しないと判定された場合、ノードは、要求元のノードへ、ＴＳの許可が拒否されたことを通知する（９１０）。利用可能なＴＸＯＰが存在すると判定された場合、ノードはＴＸＯＰを予約し（９１２）、次のノードへＴＳ許可要求を送る（９１４）。
【００６０】
図１０は、実施形態に従った許可制御装置のための典型的な構成要素および手段を例示するブロック図である。装置１０００は、ＴＳ許可要求を処理するように構成された許可要求処理モジュール１００２と、ノードのトラフィック負荷を判定するように構成されたトラフィック負荷判定モジュール１００４と、アップストリームＴＸＯＰおよび／またはダウンストリームＴＸＯＰを決定するように構成されたＴＸＯＰ決定モジュール１００６と、アップストリームＴＸＯＰおよび／またはダウンストリームＴＸＯＰを予約するように構成されたＴＸＯＰ予約モジュール１００８とを含む。
【００６１】
当業者であれば、更に、本明細書で開示された実施形態に関連して記載された様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズム・ステップが、電子工学ハードウェア、コンピュータ・ソフトウェア、あるいはこれらの組み合わせとして実現されることを理解するであろう。ハードウェアとソフトウェアとの相互置換性を明確に説明するために、様々な例示的な部品、ブロック、モジュール、回路、およびステップが、それらの機能に関して一般的に記述された。それら機能がハードウェアとしてまたはソフトウェアとして実現されるかは、特定のアプリケーション及びシステム全体に課せられている設計制約に依存する。当業者であれば、各特定のアプリケーションに応じて変化する方法で上述した機能を実現することができる。しかしながら、この適用判断は、本開示の範囲からの逸脱をもたらすものと解釈されるべきではない。
【００６２】
本明細書で開示された実施形態に関連して記述された様々な例示的な論理ブロック、モジュール、および回路は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）あるいはその他のプログラマブル論理デバイス、ディスクリート・ゲートあるいはトランジスタ・ロジック、ディスクリート・ハードウェア部品、または上述された機能を実現するために設計された上記何れかの組み合わせを用いて実現または実行されうる。汎用プロセッサとしてマイクロプロセッサを用いることが可能であるが、代わりに、従来技術によるプロセッサ、コントローラ、マイクロコントローラ、あるいは状態機器を用いることも可能である。プロセッサは、例えばＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアに接続された１または複数のマイクロプロセッサ、またはその他任意のこのような構成である計算デバイスの組み合わせとして実現することも可能である。
【００６３】
本明細書で開示された実施形態に関して記載された装置、方法あるいはアルゴリズムは、ハードウェア、ソフトウェア、これらの組み合わせによって直接的に具体化することができる。ソフトウェアでは、方法またはアルゴリズムが、処理デバイスによって読み取られたり、実行されることが可能なコンピュータ・プログラム製品の一部であるコンピュータ読取可能媒体上に格納された１または複数の命令で具体化される。これら命令は、ＲＡＭメモリ、フラッシュ・メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、あるいは当該技術分野で知られているその他の型式の記憶媒体に収納されうる。典型的な記憶媒体は、プロセッサがそこから情報を読み取り、またそこに情報を書き込むことができるようにプロセッサに結合される。または、記憶媒体はプロセッサに統合されることができる。このプロセッサと記憶媒体とは、ＡＳＩＣ内に存在することができる。ＡＳＩＣは、ユーザ端末内に存在することもできる。あるいはこのプロセッサと記憶媒体とは、ユーザ端末内のディスクリート部品として存在することができる。
【００６４】
本明細書で開示された実施形態に関して記載された装置、方法あるいはアルゴリズムは、ハードウェア、ソフトウェア、これらの組み合わせによって直接的に具体化することができる。ソフトウェアでは、方法またはアルゴリズムが、処理デバイスによって実行される１または複数の命令で具体化される。これら命令は、ＲＡＭメモリ、フラッシュ・メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、あるいは当該技術分野で知られているその他の型式の記憶媒体に収納されうる。典型的な記憶媒体は、処理デバイスが記憶媒体から情報を読み取り、またこの記憶媒体に情報を書き込むことができるように処理デバイスに結合される。または、記憶媒体は処理デバイスに統合されることができる。この処理デバイスと記憶媒体とは、ＡＳＩＣ内に存在することができる。ＡＳＩＣは、ユーザ端末内に存在することもできる。あるいは、この処理デバイスと記憶媒体とは、ユーザ端末内のディスクリート部品として存在することができる。
【００６５】
開示された実施形態における上述の記載は、当業者をして、本開示の活用または利用を可能とするように提供される。これらの実施形態への様々な変形例もまた、当業者には明らかであって、本明細書で定義された一般的な原理は、本発明の主旨または範囲から逸脱することなく他の実施形態にも適用されうる。このように、本開示は、本明細書で示された実施形態に限定されるものではなく、本明細書に記載された原理および新規な特徴に一致した最も広い範囲に相当することが意図されている。
【００６６】
本開示は、その精神または本質的特質から逸脱することなく、その他の具体的な形式でも具体化することができる。記載された実施形態は、全ての点において、例示的としてのみ考慮され、限定的とは考慮されない。従って、本開示の範囲は、先の説明ではなく特許請求の範囲によって示される。特許請求の範囲の意味およびその均等物の範囲内にある全ての変更は、これら範囲内に含まれるべきである。
【技術分野】
【０００１】
本発明は、メッシュ・ネットワークに関し、更に詳しくは、メッシュ・ネットワークにおけるデータの許可制御のための方法および装置に関する。
【背景技術】
【０００２】
近年、高速データ・サービスへの広範囲なアクセスに対する需要が増加した。電気通信業界は、様々な無線製品およびサービスを提供することにより、要求の増加に応えた。これらの製品とサービスとを相互に運用可能にするために、電気電子技術者協会（ＩＥＥＥ）は、例えばＩＥＥＥ ８０２．１１のような無線ローカル・エリア・ネットワーク（ＷＬＡＮ）規格のセットを発布した。これらの規格に準拠する製品およびサービスは、無線によるポイント・トゥ・マルチポイント・コンフィグレーションで頻繁にネットワーク化される。１つのコンフィグレーションでは、それぞれ利用可能な帯域幅を共有する個々の無線デバイス（例えば、局）は、インターネット・アクセス・ポイントと直接的に通信することができる。
【０００３】
他のコンフィグレーションは、メッシュ・ネットワークでありうる。メッシュ・ネットワークは、多数の無線ノードを有する分散型ネットワークでありうる。各ノードは、トラフィック、送信ストリームまたは伝送ストリーム（ＴＳ）を受信することができ、また、次のノードへＴＳを中継することができる。ＴＳは、ノードからノードへ「ホッピング」することにより、始点ノードから宛先ノードへ進むことができる。ＴＳルーティング・アルゴリズムは、ＴＳが始点ノードから宛先ノードへと効率的にルーティングされることを保証する。ＴＳルーティング・アルゴリズムは、メッシュ・ネットワークにおける変化に動的に適応し、メッシュ・ネットワークをより効率的かつより回復力を高くすることが可能である。例えば、ノードがかなり混雑していてＴＳを取り扱うことができないか、ノードがメッシュ・ネットワークから出るイベントでは、ＴＳルーティング・アルゴリズムは、ＴＳを、ネットワーク内の他のノードを通じて宛先ノードへルーティングすることができる。
【０００４】
メッシュ・ネットワークは、異なる動作特性を備えたノードの階層を含むことができる。幾つかのメッシュ・ネットワーク・アーキテクチャでは、階層の最下部におけるノードは、局を含むことができる。局は、例えばラップトップ・コンピュータまたはパーソナル・デジタル・アシスタントのような個別の無線デバイスを含むことができる。メッシュ・ポイントは、局の上層であると考えられるノードを含むことができる。メッシュ・ポイントはまた、無線バックボーンを形成することができる。メッシュ・ポイントは、他のメッシュ・ポイントとの間でＴＳを送受信することができる。特別タイプのメッシュ・ポイントであるメッシュ・アクセス・ポイント（ＭＡＰ）は、局とメッシュ・ポイントとの間のゲートウェイまたは接続パスを提供することができる。メッシュ・アクセス・ポイントによって、ＴＳは、局とメッシュ・ポイントとの間で「ホップ」することができる。もう１つの特別タイプのメッシュ・ポイントであるメッシュ・ポータルは、例えば８０２．１１（ａ／ｂ／ｇ／ｎ）のような異なる無線規格に準拠するデバイスのためのゲートウェイを提供することができる。メッシュ・ポータルによって、非メッシュ・ネットワークからのＴＳが、メッシュ・ネットワークに入ったり、メッシュ・ネットワークから出ることができる。
【０００５】
８０２．１１に準拠する通信デバイスは、ＴＳに対する異なるサービス品質（ＱｏＳ）要求を持つことができる。ＱｏＳは、例えば、途切れたパケット数、パケット遅延時間、パケット・ジッタ、無秩序に配信されたパケット数、誤って受信されたパケット数のような多くのパラメータを含みうる。これらのパラメータを使用して、異なる通信デバイスについて、ユーザおよびアプリケーションが異なるＱｏＳを必要とすることがわかる。例えば、インターネット・テレフォニーは、双方向の会話が理解できるように、パケット遅延時間が短く、パケット・ジッタが小さいＱｏＳを必要としうる。ストリーミング・ビデオ講義も、見苦しくないビデオ・イメージおよびコヒーレントな一方向オーディオ・トラックを提供するために、小さなパケット・ジッタを必要とするが、長いパケット遅延を許容することができる。アプリケーション、ユーザ、および通信デバイスのダイバーシティが増加すると、ＱｏＳ要求は、更に重要かつ複雑になり始めうる。例えば、２つの異なる地理的領域における２人の間のリアル・タイム対話型ゲームは、非常に複雑で厳格なＱｏＳ要求を有しうる。
【０００６】
メッシュ・ネットワークにおける無線デバイスの大規模な配置は、多様なＱｏＳ要求および優先度を用いて、ＴＳの許可制御を行うことを含むネットワーク設計に対するチャレンジを提起する。
【発明の概要】
【０００７】
（３５Ｕ．Ｓ．Ｃ．§１１９の下の優先権主張）
本願は、本明細書の譲受人に譲渡され、本明細書において参照によって明確に組み込まれている２００５年１０月１８日出願の米国特許仮出願６０／７２８、２４７号の優先権を主張する。
【０００８】
メッシュ・ノード周辺のトラフィック負荷情報は、知られているか、または、比較的容易に判定されうる。メッシュ・ノードは、ノードの各々において、新たなトラフィック・ストリーム（ＴＳ）を収容するために利用可能なローカル無線帯域幅を決定するために、トラフィック負荷情報を用いることができる。ＴＳルーティング・アルゴリズムは、メッシュ・ノードを介した新たなＴＳのための可能なルートを評価することができる。始点ノードは、可能なＴＳルートとともに、新たなＴＳに対する許可要求を行うことができる。この許可は、始点ノードから宛先ノードへとノード毎に送られる。許可要求を受信する各ノードは、この許可要求を、ローカル・トラフィック負荷情報と比較し、新たなＴＳを収容することができるかを判定する。ＴＳを収容することができる場合、送信機会（ＴＸＯＰ）が無視され、許可要求が、可能なルートに沿って次のノードへと伝えられる。ＴＳを収容することができない場合、ＴＳ要求が拒否され、許可要求が、その他の可能なルートに沿って伝えられる。
【０００９】
メッシュ・ネットワークにおいてトラフィック・ストリームを制御する方法は、第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を第２のノードにおいて受信することと、第２のノードのトラフィック負荷を判定することと、このトラフィック負荷を用いて、第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することとを備える。
【００１０】
権利要求される主題が特に指摘され、明細書の結論において明確に権利要求される。しかしながら、そのような主題は、添付図面ととともに解釈される場合、以下の詳細記載を参照して理解されうる。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施形態に従った典型的なメッシュ・ネットワークの図である。
【図２】図２は、実施形態に従った典型的なメッシュ・ノードにおいて送受信されるトラフィック・ストリーム（ＴＳ）を示す図１の典型的なメッシュ・ネットワークの部分図である。
【図３】図３は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図４】図４は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図５】図５は、実施形態に従った典型的なノードのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの一部と、典型的なノードの近隣におけるノードの各々とを示す図である。
【図６】図６は、実施形態に従って、可能なＴＳルートに沿った第１のノードにおけるＴＳの許可制御を例示するＴＳフロー図である。
【図７】図７は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御を例示するＴＳフロー図である。
【図８】図８は、実施形態に従って、可能なＴＳルートに沿った宛先ノードにおけるＴＳの許可制御を例示するフロー図である。
【図９】図９は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御の方法を例示するフロー図である。
【図１０】図１０は、実施形態に従った許可制御装置のための典型的な構成要素および手段を例示するブロック図である。
【発明を実施するための形態】
【００１２】
本開示の様々な機能の実施形態を実現する方法および装置が、図面に関連付けられて記載される。図面および関連する説明は、本開示の実施形態を例示するためであって、本開示の範囲を限定しないように提供される。「１つの実施形態」あるいは「実施形態」に対する明細書中の参照は、実施形態に関連して記載される具体的な特徴、構造、特性が、本開示の少なくとも１つの実施形態に含まれることを示すことが意図されている。明細書中の様々な場所におけるフレーズである「１つの実施形態において」または「実施形態」は、必ずしも全てが同じ実施形態を参照している必要はない。図面の全体にわたって、参照された要素間の対応を示すために参照番号が再使用される。更に、各参照番号の最初の桁は、その要素が最初に現れた図を示す。
【００１３】
図１は、実施形態に従った典型的なメッシュ・ネットワーク１００の図である。メッシュ・ネットワーク１００は、メッシュ・ノードからなる階層ネットワークであり、例えば、第１のノード１０１から第２３のノード１２３まで含みうる。凡例１３０によってこの本実施形態で示されるように、ネットワーク１００は、多くの異なるタイプのノードおよびデバイスを含みうる。メッシュ・ネットワーク１００は、例えば、第１のノード１０１から第１４のノード１１４までのような複数の局（ＳＴＡ）を含みうる。１つの実施形態では、１つの局（例えば１０１）は、別の局（例えば１０２）と関連していなくてもよい。局は、メッシュ・ネットワーク１００の無線規格に従うあらゆるデバイスでありうる。局は、例えば、コンピュータ、携帯情報端末、ネットワーク・ゲーム・デバイス、電話、テレビ、あるいは端末を含みうる。メッシュ・ネットワーク１００の無線規格は、任意の所有権付き規格、および／または、限定される訳ではないが、例えばＩＥＥＥ ８０２．１１規格のようなオープン・アーキテクチャ規格でもありうる。
【００１４】
メッシュ・ネットワーク１００は、例えばノード１１５−１１７および１１９のような１または複数のＭＡＰを含むことができる。局は、メッシュ・ネットワーク階層のベースを形成することができ、また、例えばメッシュ・アクセス・ポイント（ＭＡＰ）およびメッシュ・ポータルのようなゲートウェイ・ノードを介し、階層内のより高次のメッシュ・ノードにアクセスすることができる。ノード１０２のような局は、直接通信リンク１３４によって、例えばノード１１５のようなＭＡＰにアクセスすることができる。通信リンク１３４は、有線、無線、および／またはこれらの組み合わせでありうる。ノード１０１のような局は、ノード１０１からノード１１５およびノード１２２へ移動することによって、例えばノード１２２のようなメッシュ・ポイントへアクセスすることができる。
【００１５】
メッシュ・ポータルは、図１に示すような非メッシュ・デバイスと通信するノードを含むことができる。メッシュ・ネットワーク１００は、例えばノード１１８のような１または複数のメッシュ・ポータルを含むことができる。例えばノード１１８のようなメッシュ・ポータルは、例えばデバイス１４１−１４５のような非メッシュ・デバイスと通信することができる。非メッシュ・デバイスは、例えばイーサネット（登録商標）接続のような非メッシュ接続１１４を特徴付けるローカル・エリア・ネットワーク内にネットワークされうる。例えば、非メッシュ・デバイス１４１−１４５は、ツイスト・ペア銅線を用いて、星型コンフィグレーションで有線化することができる。非メッシュ・デバイス１４１−１４５の各々は、メッシュ・ネットワーク１００のプロトコルに準拠することができる場合もできない場合もある。
【００１６】
実施形態では、ノード１１８は、イーサネット・ハブであっても、メッシュ・ネットワーク・プロトコルに従うこともできる。ノード１１８は、非メッシュ・デバイス１４１−１４５の各々を始点とするＴＳが、メッシュ・ネットワーク１００内に移動できるようにすることができる。このように、メッシュ・ポータル１１８は、非メッシュ・デバイス１４１−１４５のためのメッシュ・ネットワーク１００ゲートウェイとなることができる。メッシュ・ポータル１１８および非メッシュ・デバイス１４１−１４５を特徴付けるネットワークは、イーサネット・ネットワークに制限されることはなく、その他のネットワークも構成され、同様に動作することができる。非メッシュ・デバイス１４１−１４５は、限定される訳ではないが、例えば、トークン・リング・ネットワーク、および／または８０２．１１ポイント・トゥ・マルチポイント・ネットワークおよび／またはこれらの組み合わせのような多くの異なるタイプのネットワークで構成されうる。
【００１７】
メッシュ・ポータル１１８は更に、例えばノード１１９を経由して、インターネットまたはその他の広域ネットワークへのリンクを有することができる。ノード１１９は、インターネット・バックボーンに接続されることができ、これによって、ノード１１９は、メッシュ・ポータルのみならずインターネット・アクセス・ポイントとなる。ノード１１９は、無線メッシュ・ネットワーク１００とインターネットとの間のブリッジを形成することができる。ブリッジは、メッシュ・ネットワーク１００内のノードのうちのいずれかと、インターネット可能デバイスとの間の接続として動作することができる。
【００１８】
メッシュ・ポイントは、他のメッシュ・ポイント、ＭＡＰ、および／またはメッシュ・ポータル間でデータを中継するノードを含むことができる。メッシュ・ネットワーク１００は、例えばノード１２０−１２３のような１または複数のメッシュ・ポイントを含むことができる。メッシュ・ポイント、ＭＡＰ、およびメッシュ・ポータルは、メッシュ・ネットワーク１００階層内のメッシュ・ノードの上部レイヤを形成することができる。局および非メッシュ・デバイスを始点とするＴＳは、メッシュ・ポータルおよびＭＡＰを介してこの上部レイヤに入ることができる。ＴＳは、他のメッシュ・ポータルおよび／またはＭＡＰを介して出て行くまで、メッシュ・ネットワーク１００の上部レイヤのノードに沿って移動する。
【００１９】
図１はまた、ＭＯと示すような典型的なトラフィック・ストリーム（ＴＳ）のルーティングをも示している。実施形態では、ＴＳ ＭＯは、メッシュ・ネットワーク１００内のノード１０８（例えば、局１０８）を始点とすることができる。ＴＳ ＭＯはまた、メッシュ・ネットワーク１００内のノード１１３（例えば、局１１３）を始点とすることもできる。ノード１０８からノード１１３への適切なＴＳルートは、ルーティング・アルゴリズムを用いて決定することができる。適切なＴＳルートが決定された後、アクセスおよびＴＸＯＰが、このルートに沿った各ノードにおいてネゴシエートされる。その後、ＴＳ ＭＯは、このルートに沿って送信されうる。ノード１０８は、ＴＳ ＭＯを、第１のホップＨ１で、ノード１１６へ送信することができる。ノード１１６は、ＴＳ ＭＯを受信することができる。そして、さらに、ＴＳ ＭＯを、第２のホップＨ２で、ノード１１７へ送信することができる。ノード１１７は、ＴＳ ＭＯを受信することができる。そして、ＴＳ ＭＯを、第３のホップＨ３で、ノード１２０へ送信することができる。ノード１２０は、ＴＳ ＭＯを受信することができる。そして、ＴＳ ＭＯを、第４のホップＨ４で、ノード１１９へ送信することができる。ノード１１９は、ＴＳ ＭＯを、この実施形態では最後である第４のホップＨ５で、ノード１１３へ送信することができる。
【００２０】
図２は、典型的なメッシュ・ノード１２０において送受信されるＴＳを示す図１の典型的なメッシュ・ネットワーク１００の部分図である。この実施形態では、ノード１２０は、他の４つのノード１１７、１１９、１２１および１２２との間でＴＳを送受信することができる。ノード１２０は、これらの４つのノードのネットワーク近傍にあると言うことができる。この実施形態では、ノード１２０は、ノード１１７、１２１および１２２から、ＴＳ Ｒ１７、Ｒ２１およびＲ２２をそれぞれ受信することができる。更に、ノード１２０は、ノード１１７、１１９および１２１に、ＴＳ Ｔ１７、Ｔ１９およびＴ２１をそれぞれ送信することができる。この例において、ノード１１７、１１９または１２１は「リーフ」ノードではなく、ＴＳ Ｒ１７、Ｒ２１およびＲ２２と、Ｔ１７、Ｔ１９およびＴ２１とは、ノード１１７、１１９または１２１におけるその他のＴＳのアグリゲートでありうることに注目されたい。
【００２１】
ノード１２０におけるトラフィックは、２つのベクトル（すなわち、送信ベクトルおよび受信ベクトル）によって表すことができる。実施形態では、ＴＳは、例えば、スケジュールされたサービス間隔（ＳＳＩ：scheduled service interval）のような確立された期間にわたって、ＴＳに関連付けられたデータを送信するために、チャネルを占有する時間割合によって表されうる。このコンテクストにおけるトラフィック負荷または媒体占有は、例えば、スケジュールされたサービス間隔（ＳＳＩ）のような確立された時間間隔にわたってビジー（busy）であるとしてチャネルにおける占有された時間長さを示すｔｂｕｓｙのような量によって表されうる。従って、送信ベクトルＴ２０（２１０と示される）は、４つの要素を有する。第１の要素は、ＴＳ Ｔ１７をノード１２０からノード１１７へ送信するための時間ｔＴ１７であり、第２の要素は、ＴＳ Ｔ１９をノード１２０からノード１１９へ送信するための時間ｔＴ１９であり、第３の要素は、ＴＳ Ｔ２１をノード１２０からノード１２１へ送信するための時間ｔＴ２１であり、第４の要素は、ＴＳ Ｔ２２をノード１２０からノード１２２へ送信するための時間ｔＴ２２である。この例において、送信ベクトルＴ２０ ２１０の第４の要素ｔＴ２２は、ゼロであろう。なぜならノード１２０は、ノード１２２に何れのＴＳも送信しないからである。ここで、ｔＴ１７は、ＳＳＩ毎に、ＴＳ Ｔ１７の送信のためにチャネルにおいて占有される時間である。
【００２２】
同様に、受信ベクトルＲ２０（２１２と示される）は、４つの要素を有する。第１の要素は、ＴＳ Ｒ１７をノード１１７から受信するための時間ｔＲ１７であり、第２の要素は、ＴＳ Ｒ１９をノード１１９から受信するための時間ｔＲ１９であり、第３の要素は、ＴＳ Ｒ２１をノード１２１から受信するための時間ｔＲ２１であり、第４の要素は、ＴＳ Ｒ２２をノード１２２から受信するための時間ｔＲ２２である。この例において、受信ベクトルＲ２０ ２１２の第２の要素ｔＲ１９は、ゼロであろう。なぜならノード１２０は、ノード１１９から何れのＴＳも受信しないからである。ここで、ｔＲ１７は、ＳＳＩ毎に、ＴＳ Ｒ１７の送信のためにチャネルにおいて占有される時間である。
【００２３】
ノード１２０周辺の媒体が、ノード１２０またはその他任意のノードにおいて、ＳＳＩの一部として負荷がかけられたと考えられる時間長さのようなトラフィック負荷（ｔｌｏａｄ）は、測定を含む様々な方法で判定することができる。実施形態では、ノード１２０は、ビジー時間（ｔｂｕｓｙ）を判定するために、ノード１２０の物理レイヤ（ＰＨＹ）によって検出されるようなクリア・チャネル・アセスメント（ＣＣＡ）ビジー表示をモニタすることができる。ＣＣＡビジー表示が、このチャネルがビジーではないことを示す場合であっても、ノード１２０は、ノード１２０が送信しない時間割合を示すネットワーク割当ベクトルの静寂時間（ｔｑｎａｖ）をモニタすることができる。ネットワーク割当ベクトル（ＮＡＶ）は、周囲のノードからの条件を処理することによって得られる。ノード１２０に接続されたノード１１７、１１９、１２１、１２２が、ノード１２０以外のノードからの通信を受信することができるように、静寂時間（ｔｑｎａｖ）は、チャネルが利用可能ではない時間を表すことができる。静寂時間（ｔｑｎａｖ）およびＣＣＡビジー表示によってチャネルが利用可能ではない時間長さは、トラフィック負荷（ｔｌｏａｄ）である。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷（ｔｌｏａｄ）は、以下の式によって表わすことができる。
【００２４】
ｔｌｏａｄ＝ｔｂｕｓｙ＋ｔｑｎａｖ
図３は、典型的なノード１２０と、典型的なノード１２０の近隣のノード１１７、１１９、１２１および１２２の各々のトラフィック・フロー情報を示す図１のメッシュ・ネットワーク１００の部分図である。実施形態では、近隣ノードは、ノードの１つの通信リンク内のノードとして定義することができる。ノード１２０の近隣ノードは、ノード１１７、１１９、１２１および１２２である。従って、図３は、ＴとＲ、および、ノード１２０とその近隣ノード１１７、１１９、１２１、１２２のおのおのの送受信のためにＳＳＩの間に費やされる時間部分を決定するために必要なノードを示す。実施形態では、各ノードは、ノードのビーコンの一部としてＴおよびＲを送信することができる。各ノードはまた、近隣ノードからトラフィック負荷情報を受信するために、他のノードのビーコンをモニタすることができる。例えば、ノード１２０は、ＴとＲのペアであるＴ２０およびＲ２０を送信することができる。Ｔ２０およびＲ２０は、ノード１２０の近隣ノードによってモニタされる。近隣ノード１１７、１１９、１２１および１２２はまた、他のノードがこれらパラメータをモニタできるように、それぞれのＴとＲのペア、すなわち、Ｔ１７とＲ１７、Ｔ１９とＲ１９、Ｔ２１とＲ２１、および、Ｔ２２とＲ２２を他のノードに送信することができる。
【００２５】
ノードはそれぞれ、近隣ノードのビーコンをモニタすることによって、ローカルなＴＳトラフィック負荷、そしてその利用可能な帯域幅を決定することができる。ノードの近隣におけるローカルなＴＳトラフィック負荷は、送受信マトリクス・ペアＴＸ、ＲＸを形成することによって判定されうる。ＴＸ、ＲＸペアのローおよびカラムは、メッシュ・ネットワーク１００内のノードの送信パラメータおよび受信パラメータに対応する。ＴＸおよびＲＸはその後、近隣ノードの各々から受信された個々のＴとＲのペアからの情報で埋められる。Ｔ、Ｒ、ＴＸ、およびＲＸはそれぞれ、値、ベクトル、またはマトリクスを表す。
【００２６】
例えば、ノード１２０は、近隣ノードの各々のビーコンをモニタすることができる。ノード１２０は、ノード１１７からＴ１７とＲ１７のペアを、ノード１１９からＴ１９とＲ１９のペアを、ノード１２１からＴ２１とＲ２１のペアを、ノード１２２からＴ２２とＲ２２のペアを受信することができる。ノード１２０は、ＴＸ２０とＲＸ２０とのマトリクスを埋めるために、受信したＴとＲのペアを解析することができる。ＴＸ２０とＲＸ２０の各ローおよびカラムは、メッシュ・ネットワーク１００のノードと少なくとも部分的に対応することができる。例えば、ＴＸ２０のロー１７、カラム１６は、ＴＳがノード１１７からノード１１６へ送信される時間長さで埋めることができる。この時間情報はまた、ノード１１７の送信ベクトルＴ１７と、ノード１１６の受信ベクトルＲ１６においても利用可能である。同様に、ＲＸ２０のロー２１、カラム２２は、ノード１２１がノード１２２からＴＳを受信する時間長さで埋められる。この時間情報はまた、ノード１２１の受信ベクトルＲ２１とノード１２２の送信ベクトルＴ２２においても利用可能である。
【００２７】
ノード１２０の周囲のトラフィック負荷は、ＴＸ２０およびＲＸ２０の各送信受信ペアについて最大値を合計することによって、ＴＸ２０およびＲＸ２０から判定することができる。例えば、ＴＳがノード１２１からノード１２２へ送信されるのに要する時間長さを表すＴＸ２０のロー２１、カラム２２は、ノード１２２がノード１２１からＴＳを受信するのに要する時間長さを表すＲＸ２０のロー２２、カラム２１と比較されうる。ＴＸ２０とＲＸ２０からなる各送信受信ペアの最大値は、ノード１２０における新たなＴＳについて、送信媒体が利用できないために、利用不可能な時間長さを表す。例えば、ロー２１、カラム２２の最大値は、送信媒体が利用できない時間長さをノード１２０に示すことができる。なぜなら、ＴＳは、ノード１２１とノード１２２との間で送信されるからである。ＴＸ２０とＲＸ２０のペアにわたる最大値の合計は、ノード１２０におけるローカル・トラフィック負荷を判定するために、少なくとも部分的に使用されうる。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷は、以下の式を用いることによって少なくとも部分的に判定することができる。
【数１】
【００２８】
その後、トラフィック負荷は、新たなＴＳを許可するために、ノード１２０の周囲で利用可能な適切なチャネル帯域幅が存在するかを判定するために、ノード１２０によって使用することができる。ノード１２０は、ノード１２０または近隣ノードにおいて送受信される他のＴＳと干渉することなく新たなＴＳが収容されることを保証することができる。ノード１２０がＴＳ許可要求を受信する場合、ノード１２０は、この許可要求を、ノード１２０におけるトラフィック負荷と比較し、ノード１２０またはノード１２０の近傍において、他のＴＳと干渉することなくＴＳを受信し、ＴＳをルート内の次のノードに送信することができるかを判定することができる。ノード１２０が新たなＴＳを収容することができる場合、ノード１２０はＴＳを許可することができる。ノード１２０が新たなＴＳを収容することができない場合、ノード１２０はＴＳを拒否することができる。そして、前のノードは、宛先ノードへの次の最も適切なルートおよび／または他の適切なルートを決定するために、ルーティング・アルゴリズムを起動することができる。これによって、ノード１２０を効果的にバイパスする。
【００２９】
図４は、典型的なノード１２０と、この典型的なノード１２０の近傍ノード１１７、１１９、１２１、１２２のそれぞれのトラフィック・フロー情報を示す図１のメッシュ・ネットワークの部分図である。ノード１１７、１１９、１２１および１２２の近傍も示されている。ノード１２０は、合計ベクトルＳ２０を、近傍ノードのおのおのに送信することができる。また、各近隣ノードは、Ｓ１７を送信するノード１１７、Ｓ１９を送信するノード１１９、Ｓ２１を送信するノード１２１、Ｓ２２を送信するノード１２２のように、それぞれの合計ベクトルＳを送信することもできる。Ｓの各要素は、ノードとその近隣ノードのそれぞれとの間の送信時間および受信時間の集合を含むことができる。実施形態では、ノード１２０のＳ２０ベクトルは、４つの要素を含む。ここで、各要素は、ノード１２０の、近隣ノードのそれぞれとの送信時間と受信時間との合計を表す。第１の要素は、ノード１１７との送信時間と受信時間との合計であり、第２の要素は、ノード１１９との送信時間と受信時間との合計であり、第３の要素は、ノード１２１との送信時間と受信時間との合計であり、第４の要素は、ノード１２２との送信時間と受信時間との合計である。
【００３０】
実施形態において、ＴＸとＲＸの代わりにＳを送信することの１つの利点は、Ｓのサイズが、ＴＸおよびＲＸのサイズのほとんど半分と、小さくなることである。これは、トラフィック負荷情報を送信するために必要な時間および帯域幅を低減することができる。特に、高次のネットワーク・グラフを有するビジーなノード（多くの近隣を有するノード）にとって、オーバヘッドは深刻である。
【００３１】
ノード１２０は、ノード１２０の近隣ノードの送信をモニタし、近隣ノードの各々についてのＳベクトルを格納する。ノード１２０のトラフィック負荷は、メッシュ・ネットワーク１００内のメッシュ・ノードを表すローとカラムの各々を備えた負荷マトリクスＳＴを構築することによって判定されうる。負荷マトリクスＳＴは、ノード１２０の近隣ノードの各々についての送信時間と受信時間との合計で埋められうる。実施形態では、負荷マトリックスＳＴのロー２１は、ノード１２１からのＳベクトルを表わすＳ２１の要素で埋められうる。負荷マトリクスＳＴのロー２１、カラム２２は、ノード１２１とノード１２２との送信時間と受信時間との合計に対応するＳ２１の要素で埋められうる。その後、送信ロー・カラム・ペアと受信ロー・カラム・ペアとを比較し、相対的な最大値を選択することによって、ノード１２０の周囲のトラフィック負荷が、少なくとも部分的に判定されうる。例えばＳＴのロー２１、カラム２２は、ＳＴのロー２２、カラム２１と比較され、相対的な最大値が、負荷判定のために使用されうる。その後、全てのロー・カラム・ペア比較の合計が、ノード１２０の周囲のトラフィック負荷を判定するために少なくとも部分的に使用される。メッシュ・ネットワーク１００内の任意のノードの周囲のトラフィック負荷は、以下の式によって少なくとも部分的に判定される。
【数２】
【００３２】
計算されたトラフィック負荷情報は、新たなＴＳが許可されるかを判定するために、ノード１２０によって使用されうる。ノード１２０がＴＳ許可要求を受信した場合、ノード１２０は、この許可要求をトラフィック負荷と比較し、ノード１２０がＴＳを受信できるかを判定し、ノード１２０またはその近隣における他のノードにおいて他のＴＳを危険にさらすことなく、このＴＳをルート内の次のノードに転送する。ノード１２０が、ＴＳを受信し、転送することができるのであれば、ノード１２０は、ＴＳを許可することができる。ノード１２０が、ＴＳを受信することも、転送することもできないのであれば、ノード１２０は、ＴＳを拒否し、前のノードが、ノード１２０をバイパスするルーティング・アルゴリズムを起動することができる。従って、実施形態では、メッシュ・ネットワーク１００のノードは、近隣におけるトラフィック負荷を測定または計算し、そして、許可制御を実行するために、トラフィック負荷情報を用いることができる。
【００３３】
図５は、実施形態に従った、典型的なノード１２０と、典型的なノードの近隣のノード１１７、１１９、１２１、１２２の各々とのトラフィック・フロー情報を示す図１のメッシュ・ネットワーク１００の部分図である。メッシュ・ネットワーク１００の各ノードの周囲のトラフィック負荷は、スカラ・パラメータの近隣ノードの測定およびモニタリングによって判定することができる。ノード１１７、１１９、１２１および１２２の近隣も図５で示される。実施形態では、これらノードの各々は、例えばビジー時間のようなパラメータをブロードキャストすることができる。これらノードの各々は、各ＰＨＹによって検出されたようなチャネル・ビジー時間を測定することができる。その後、チャネル・ビジー時間は、これらノードの各々によってブロードキャストされる。
【００３４】
ノード１２０は、１または複数のビーコン間隔にわたるビジー表示のために、ＰＨＹをモニタすることができる。ノード１２０のＰＨＹが、チャネルがビジーであることをレポートする時間長さＴであるＴ２０がブロードキャストされうる。同様に、ノード１２０の近隣ノードは、チャネルがビジーであるとそれぞれのＰＨＹが示す時間長さを決定するために、それぞれのＰＨＹをモニタすることができる。これら近隣ノードはまた、測定されたビジー時間をブロードキャストすることができる。Ｔ２０は、その近隣ノード１１７、１１９、１２１、１２２によって使用することができる。ノード１２０は、それぞれの近隣ノードから、Ｔ１７、Ｔ１９、Ｔ２１、Ｔ２２を受信することができる。ノード１２０は、平均的な静寂ネットワーク・アクセス・ベクトル（ｔｑｎａｖ）時間もモニタすることができる。その後、ノード１２０は、Ｔ１、Ｔ２、Ｔ３およびＴ４を総和することにより、少なくとも部分的にノード１２０の周囲のトラフィック負荷を計算することができる。メッシュ・ネットワーク１００内の任意のノードにおけるトラフィック負荷は、以下の式を用いて、少なくとも部分的に計算することができる。
【数３】
【００３５】
その後、トラフィック負荷は、新たなＴＳを許可する能力を判定するために、ノード１２０によって利用されうる。ノード１２０は、新たなＴＳが、近隣ノードにおいて現在送信され受信されているＴＳを危険にさらさないことを保証することができる。ノード１２０がＴＳ許可要求を受信する場合、ノード１２０は、この許可要求をトラフィック負荷と比較し、ノード１２０がＴＳを受信できるかを判定し、このＴＳを、他のＴＳを危険にさらすことなく次のノードへ転送することができる。ノード１２０が新たなＴＳを許可することができると判定された場合、ノード１２０はＴＳを許可することができる。ノード１２０が新たなＴＳを許可できないと判定された場合、ノード１２０は、ＴＳを拒否し、前のノードは、ノード１２０をバイパスするルーティング・アルゴリズムを実施することができる。
【００３６】
図６は、実施形態に従って、可能なＴＳルートに沿った第１のノード１１６におけるＴＳの許可制御を例示するＴＳフロー図である。実施形態では、始点局ＭＯであるノード１０８は、宛先局ＭＤであるノード１１３への可能なルートを決定するために、ルート・アルゴリズムを利用することができる。ノード１０８は、上述した方法のうちの１つに従って、トラフィック負荷を評価または判定することができる（９０４）。ノード１０８は、アプリケーションに特有な適切なルートを選択することができる。例えば、このルートは、次のホップへの距離、次のホップ・ノードにおけるトラフィック負荷、次のホップ・ノードの程度、および／またはその他の判定基準、および／またはこれらの組み合わせに基づいて選択することができる。
【００３７】
実施形態では、Ｈ１のスケジュール・サービス間隔（ＳＳＩ）中に転送されるメディア・アクセス制御（ＭＡＣ）サービス・データ・ユニット（ＭＳＤＵ）パケットの平均数が
計算される。パケット（Ｎ）の平均数は、公称パケット・サイズ（Ｌ）で除されたＳＳＩと保証データ・レート（Ｇ）との積でありうる。パケットの平均数は、下記式を用いることによって、少なくとも部分的に計算することができる。
【数４】
【００３８】
ダウンストリームＴＸＯＰでは、Ｈ１に必要とされるデータ送信のためにＳＳＩ毎にスケジュールされた時間部分も計算することができる。この場合、我々は、簡単な表記ＴＸＯＰを用いて期間ｔＴＸＯＰを示す。その計算は、Ｈ１に沿った既存のトラフィックに少なくとも部分的に依存する。既存のトラフィックが、ＭＯと同じクラスのＴＳを含んでおり、より短いＳＳＩを必要としない場合、ＭＯからのデータ・パケットは、追加オーバヘッドに対する必要なしで、既存のＴＳとともに集められる。実施形態では、Ｈ１のＴＸＯＰは、物理的送信レート（Ｒ）によって除された許容可能な最大ＭＳＤＵ（２３０４バイト）と、物理的送信レートによって除された公称パケット・サイズとデータ・パケットの平均数（Ｎ）との積とのうちの最大でありうる。ＴＸＯＰは、以下の式に少なくとも部分的に基づいて計算することができる。
【数５】
【００３９】
同じクラスのノード１０８とノード１１６との間に既存のＴＳがない場合、または、新たなデータ・ストリームがより小さなＳＳＩしか必要としない場合、ＴＸＯＰは、追加のクラスまたはより小さなＳＳＩを取り扱うための追加オーバヘッドを含みうる。より小さなＳＳＩは、データ・ビット毎のオーバヘッドが増加することを意味する。従って、より小さな数のホップを持つパスを選択することが望ましい。これによって、ネットワーク伝送能力全体を改善するのみならず、その効率をも高めることができる。この場合、ＴＸＯＰは、以下の式によって少なくとも部分的に決定することができる。
【数６】
【００４０】
ノード１０８における計画された全ダウンストリーム・トラフィック負荷は、Ｈ１のＳＳＩによって除されたＨ１のＴＸＯＰに、送信されるようにスケジュールされたその他全てのＴＳについて、各ＳＳＩによって除されたＴＸＯＰの総和を加えることによって少なくとも部分的に計算される。Ｈ１によるトラフィック負荷は、ノード１０８を出発するＴＳによる他の既存のトラフィック負荷とともに加えられる。ダウンストリーム・トラフィック負荷は、下記式によって少なくとも部分的に表すことができる。
【数７】
【００４１】
ノード１０８におけるアップストリーム・トラフィック負荷は変わらない。始点ではないノードについてのアップストリーム計算を以下に説明する。
【００４２】
ノード１０８は、ＭＯが収容されるかを判定するために、アップストリーム・トラフィック負荷と、ダウンストリーム・トラフィック負荷との合計を、予め定めた負荷しきい値と比較する。ＭＯが収容されると判定された場合、ノード１０８はＴＸＯＰを予約し、ビーコン信号内の負荷情報を更新し、ノード１１６へ許可要求を送る。ＭＯが収容されると判定されなかった場合、アクセスが拒否される。
【００４３】
実施形態では、ＴＸＯＰ計算およびしきい値は、ＱｏＳによって区分される。例えば、ノードは、トラフィックの３０％をＶＯＩＰタイプのＱｏＳに割り当て、１０％をリアルタイム・インタラクティブ・ゲーム・タイプのＱｏＳに割り当て、６０％をウェブ・ブラウジング・タイプのＱｏＳに割り当てる。その後、トラフィック負荷判定およびしきい値比較は、ＱｏＳ特有となりうる。データ・ストリームをサポートするのに十分な帯域幅がない場合、動的なＱｏＳ割り当てが行われうる。ノードは、別のＱｏＳのために区分された帯域幅の一部を、新たなデータ・ストリームのために再び割り当てることができる。
【００４４】
ノード１０８は、ダウンストリーム・ノードから許可の拒否を受け取るまで、ＴＸＯＰ予約を保持することができる。許可の拒否を受け取ると、始点局は、ＴＸＯＰ予約をキャンセルし、宛先局１１３への別のルートを決定するルーティング・アルゴリズムを起動することができる。適切なルートが見つかった場合、ノード１０８は、上述した許可処理を再開することができる。
【００４５】
図７は、実施形態に従って、可能なＴＳルートに従ったＴＳおよびＭＯの典型的なホップＨｉを示す。ノード１２０がノード１１７から許可要求を受け取ると、ノード１２０は、アップストリーム（第４のホップ）およびダウンストリーム（第３のホップ）のＴＸＯＰと、計画されたトラフィック負荷とを計算することができる。ノード１２０における許可制御の記述を簡略化および一般化するために、アップストリーム・ホップが、Ｈｉとして記述され、ダウンストリーム・ホップがＨｉ−１として記述される。ノード１２０の許可制御は、メッシュ・ネットワーク１００中の任意のＴＳの任意のノードまたはホップに適用されうる。
【００４６】
実施形態では、ＨｉのＳＳＩ中に転送されるＭＳＤＵパケットの平均数が計算される。パケットの平均数（Ｎ）は、保証されたデータ・レート（Ｇ）とＳＳＩとの積が、公称パケット・サイズ（Ｌ）で除されたものとなることができる。パケットの平均数は、以下の式によって少なくとも部分的に記述される。
【数８】
【００４７】
ＨｉのダウンストリームＴＸＯＰもまた計算することができる。この計算は、Ｈｉに沿った既存のトラフィックに少なくとも部分的に依存しうる。既存のトラフィックがＭＯと同じクラスのＴＳを含んでおり、より小さなＳＳＩを必要としないのであれば、Ｍからのデータ・パケットは、追加オーバヘッドに対する必要なしで、既存のＴＳとともに集められる。ＨｉのＴＸＯＰは、物理的送信レート（Ｒ）によって除された許容可能な相対的に最大のＭＳＤＵ（２３０４バイト）（Ｌｍａｘ）と、データ・パケットの平均数（Ｎ）と公称パケット・サイズとの積を物理的送信レートで除したものとのうちの最大値でありうる。ＴＸＯＰは、下記式に少なくとも部分的に基づいて記述することができる。
【数９】
【００４８】
ＴＸＯＰは、追加クラスまたはより小さなＳＳＩを取り扱うための追加オーバヘッドを含むことができる。この状態では、ＴＸＯＰは、下記式に少なくとも部分的に基づいて記述することができる。
【数１０】
【００４９】
ノード１２０において計画されたダウンストリーム・トラフィック負荷の合計は、Ｈｉについて、ＳＳＩによって除されたＴＸＯＰに、それぞれのノード１２０を出発するようにスケジュールされ、ＳＳＩによって除されたその他全てのトラフィック・ストリームのＴＸＯＰの総和を加えることによって少なくとも部分的に計算される。特に、Ｈｉによるトラフィック負荷は、近隣ノードｋのそれぞれ、すなわちノード１１７、ノード１１９、ノード１２１、およびノード１２２について、ノード１２０を出発するＴＳによるその他の既存のトラフィック負荷で合計される。ダウンストリーム・トラフィック負荷は、下記式に少なくとも部分的に基づいて記述される。
【数１１】
【００５０】
ノード１２０はまた、Ｈｉ−１のアップストリームＴＸＯＰを計算する。その計算は、リンクＨｉ−１に沿った既存のトラフィックに少なくとも部分的に基づくことができる。既存のトラフィックが、ＭＯと同じクラスのＴＳを含んでおり、より小さなＳＳＩを必要としないのであれば、ＭＯからのデータ・パケットは、追加のオーバヘッドのための必要性なく、既存のＴＳとともに集めることができる。Ｈｉ−１のＴＸＯＰは、物理的送信レート（Ｒ）によって除された最大許容可能なＭＳＤＵ（２３０４バイト）と、物理的送信レートによって除されたデータ・パケット平均数（Ｎ）と公称パケット・サイズとの積とのうちの最大値でありうる。ＴＸＯＰは、少なくとも部分的に以下の式に基づいて記述されうる。
【数１２】
【００５１】
ＴＸＯＰが、追加のクラスまたはより小さなＳＳＩを取り扱う追加オーバヘッドを含んでいるのであれば、ＴＸＯＰは、少なくとも部分的に以下の式に基づいて記述されうる。
【数１３】
【００５２】
ノード１２０における計画された全アップストリーム・トラフィック負荷は、Ｈｉ−１についてＳＳＩによって除されたＴＸＯＰに、ノード１２０に到着すると計画されたその他全てのトラフィック・ストリームの、各ＳＳＩによって除されたアップストリームＴＸＯＰの総和を加えることによって計算される。Ｈｉによるトラフィック負荷は、ノード１２０の近隣ｋの各々であるノード１１７、ノード１１９、ノード１２１、およびノード１２２からノード１２０に到着するＴＳによるその他の既存のトラフィック負荷と加算される。アップストリーム・トラフィック負荷は、少なくとも部分的に下記式に基づいて記載される。
【数１４】
【００５３】
ノード１２０は、上記計算を行った後に、アップストリーム・トラフィック負荷とダウンストリーム・トラフィック負荷との合計を、予め定めたしきい値と比較して、ＭＯが収容可能であるかを少なくとも部分的に判定することができる。ＭＯが収容可能であると判定された場合、ノード１２０は、ＴＸＯＰを予約し、そのビーコンにおける負荷情報を更新し、許可要求をノード１１９へ送る。ＭＯが収容可能ではないと判定された場合、アクセスが拒否され、ノード１２０は、ＴＳ ＭＯの許可を拒否するメッセージをノード１１７へ送る。
【００５４】
実施形態では、ＴＸＯＰ計算およびアクセスしきい値は、ＱｏＳによって区分されうる。トラフィック負荷判定およびしきい値比較は、ＱｏＳ特有でありうる。
【００５５】
図８は、宛先局であるノード１１３への最終ホップＨＤを示す。ＨＤのためのノード１１３における許可制御は、ダウンストリームＴＸＯＰ計算が省略されるという点を除いてホップＨｉのものと同じでありうる。次のホップ局への許可要求の発行も省略されうる。
【００５６】
Ｍ個のルートに沿ったノードの各々は、ダウンストリーム・ノードから許可の拒否を受け取るまで、それぞれのＴＸＯＰ予約を維持することができる。許可の拒否を受信すると、始点局は、ＴＸＯＰ予約をキャンセルし、宛先局であるノード１１３への別のルートを決定するためにルーティング・アルゴリズムを起動することができる。ルートに沿った各ノードの許可処理は、再度起動することができる。
【００５７】
メッシュ・ネットワーク１００またはノードのうちの何れかは、ＱｏＳ要求によってアクセスを区分することができる。ＱｏＳ許可制御の１つの方法は、ＴＳクラスを、例えば高優先度クラスや低優先度クラスのような多数のクラスへ分割するものである。高優先度クラスのＴＳは、ルートに沿ったそれぞれのノードにおいて、１つのＳＳＩ内でサービスされうる。最悪ケース遅延は、ホップ数にＳＳＩを掛けることにより計算されうる。例えば、音声アプリケーションでは、高々約５０ミリ秒の遅延時間しか許可されない。従って、高優先度のストリームは、約１０ミリ秒のＳＳＩを持つ高々５つのノードを介してルーティングされる。
【００５８】
図９は、実施形態に従って、可能なＴＳルートに沿った典型的なノードにおけるＴＳの許可制御の方法を例示するフロー図である。ノードは、ＴＳ許可要求を受信する（９０２）。ＴＳ許可要求は、別のノードから送信されうる。あるいは、この許可要求は、ノード自体から出発するＴＳのためのものでありうる。このノードは、ノードの近隣のトラフィック負荷を判定することができる。ノードは、ノードにおける負荷を測定することによって、あるいはロードの近隣によって送信された情報からの負荷を判定することによって、トラフィック負荷を少なくとも部分的に判定することができる。トラフィック負荷計算および測定は、限定される訳ではないが、本明細書に記載した方法および／またはその均等物を含む様々な方法によって実施することができる。トラフィック負荷は、ノードの近隣から送信された測定値と結合されたノード自体における測定値から判定することができる。典型的なハイブリッド・トラフィック負荷計算も上述される。これもまた、トラフィック負荷を判定するために利用することができる。
【００５９】
ノードは、ＴＸＯＰを決定する（９０６）。ノードが始点ノードである場合、ダウンストリームＴＸＯＰを計算することができる。ノードが宛先ノードである場合、アップストリームＴＸＯＰを計算することができる。ノードが中間ノードである場合、アップストリームＴＸＯＰおよびダウンストリームＴＸＯＰを計算することができる。ノードは、ＴＸＯＰを、利用可能なＴＸＯＰと比較することができる（９０８）。利用可能な適切なＴＸＯＰが存在しないと判定された場合、ノードは、要求元のノードへ、ＴＳの許可が拒否されたことを通知する（９１０）。利用可能なＴＸＯＰが存在すると判定された場合、ノードはＴＸＯＰを予約し（９１２）、次のノードへＴＳ許可要求を送る（９１４）。
【００６０】
図１０は、実施形態に従った許可制御装置のための典型的な構成要素および手段を例示するブロック図である。装置１０００は、ＴＳ許可要求を処理するように構成された許可要求処理モジュール１００２と、ノードのトラフィック負荷を判定するように構成されたトラフィック負荷判定モジュール１００４と、アップストリームＴＸＯＰおよび／またはダウンストリームＴＸＯＰを決定するように構成されたＴＸＯＰ決定モジュール１００６と、アップストリームＴＸＯＰおよび／またはダウンストリームＴＸＯＰを予約するように構成されたＴＸＯＰ予約モジュール１００８とを含む。
【００６１】
当業者であれば、更に、本明細書で開示された実施形態に関連して記載された様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズム・ステップが、電子工学ハードウェア、コンピュータ・ソフトウェア、あるいはこれらの組み合わせとして実現されることを理解するであろう。ハードウェアとソフトウェアとの相互置換性を明確に説明するために、様々な例示的な部品、ブロック、モジュール、回路、およびステップが、それらの機能に関して一般的に記述された。それら機能がハードウェアとしてまたはソフトウェアとして実現されるかは、特定のアプリケーション及びシステム全体に課せられている設計制約に依存する。当業者であれば、各特定のアプリケーションに応じて変化する方法で上述した機能を実現することができる。しかしながら、この適用判断は、本開示の範囲からの逸脱をもたらすものと解釈されるべきではない。
【００６２】
本明細書で開示された実施形態に関連して記述された様々な例示的な論理ブロック、モジュール、および回路は、汎用プロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）あるいはその他のプログラマブル論理デバイス、ディスクリート・ゲートあるいはトランジスタ・ロジック、ディスクリート・ハードウェア部品、または上述された機能を実現するために設計された上記何れかの組み合わせを用いて実現または実行されうる。汎用プロセッサとしてマイクロプロセッサを用いることが可能であるが、代わりに、従来技術によるプロセッサ、コントローラ、マイクロコントローラ、あるいは状態機器を用いることも可能である。プロセッサは、例えばＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアに接続された１または複数のマイクロプロセッサ、またはその他任意のこのような構成である計算デバイスの組み合わせとして実現することも可能である。
【００６３】
本明細書で開示された実施形態に関して記載された装置、方法あるいはアルゴリズムは、ハードウェア、ソフトウェア、これらの組み合わせによって直接的に具体化することができる。ソフトウェアでは、方法またはアルゴリズムが、処理デバイスによって読み取られたり、実行されることが可能なコンピュータ・プログラム製品の一部であるコンピュータ読取可能媒体上に格納された１または複数の命令で具体化される。これら命令は、ＲＡＭメモリ、フラッシュ・メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、あるいは当該技術分野で知られているその他の型式の記憶媒体に収納されうる。典型的な記憶媒体は、プロセッサがそこから情報を読み取り、またそこに情報を書き込むことができるようにプロセッサに結合される。または、記憶媒体はプロセッサに統合されることができる。このプロセッサと記憶媒体とは、ＡＳＩＣ内に存在することができる。ＡＳＩＣは、ユーザ端末内に存在することもできる。あるいはこのプロセッサと記憶媒体とは、ユーザ端末内のディスクリート部品として存在することができる。
【００６４】
本明細書で開示された実施形態に関して記載された装置、方法あるいはアルゴリズムは、ハードウェア、ソフトウェア、これらの組み合わせによって直接的に具体化することができる。ソフトウェアでは、方法またはアルゴリズムが、処理デバイスによって実行される１または複数の命令で具体化される。これら命令は、ＲＡＭメモリ、フラッシュ・メモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブル・ディスク、ＣＤ−ＲＯＭ、あるいは当該技術分野で知られているその他の型式の記憶媒体に収納されうる。典型的な記憶媒体は、処理デバイスが記憶媒体から情報を読み取り、またこの記憶媒体に情報を書き込むことができるように処理デバイスに結合される。または、記憶媒体は処理デバイスに統合されることができる。この処理デバイスと記憶媒体とは、ＡＳＩＣ内に存在することができる。ＡＳＩＣは、ユーザ端末内に存在することもできる。あるいは、この処理デバイスと記憶媒体とは、ユーザ端末内のディスクリート部品として存在することができる。
【００６５】
開示された実施形態における上述の記載は、当業者をして、本開示の活用または利用を可能とするように提供される。これらの実施形態への様々な変形例もまた、当業者には明らかであって、本明細書で定義された一般的な原理は、本発明の主旨または範囲から逸脱することなく他の実施形態にも適用されうる。このように、本開示は、本明細書で示された実施形態に限定されるものではなく、本明細書に記載された原理および新規な特徴に一致した最も広い範囲に相当することが意図されている。
【００６６】
本開示は、その精神または本質的特質から逸脱することなく、その他の具体的な形式でも具体化することができる。記載された実施形態は、全ての点において、例示的としてのみ考慮され、限定的とは考慮されない。従って、本開示の範囲は、先の説明ではなく特許請求の範囲によって示される。特許請求の範囲の意味およびその均等物の範囲内にある全ての変更は、これら範囲内に含まれるべきである。
【特許請求の範囲】
【請求項１】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する方法であって、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信することと、
前記第２のノードのトラフィック負荷を判定することと、
前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することと
を備える方法。
【請求項２】
サービス間隔と呼ばれる期間を確立することと、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定することと
を更に備える請求項１に記載の方法。
【請求項３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項２に記載の方法。
【請求項４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択することを更に備える請求項１に記載の方法。
【請求項５】
サービス間隔と呼ばれる期間を確立することと、
近隣ノードから、送信時間割合および受信時間割合を受信することと
を更に備える請求項１に記載の方法。
【請求項６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信することを更に備える請求項１に記載の方法。
【請求項７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定することを更に備える請求項１に記載の方法。
【請求項８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項１に記載の方法。
【請求項９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタすることを更に備える請求項１に記載の方法。
【請求項１０】
コンピュータ読取可能媒体を備えるコンピュータ・プログラム製品であって、前記コンピュータ読取可能媒体は、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信する命令と、
前記第２のノードのトラフィック負荷を判定する命令と、
前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定する命令と
を備えるコンピュータ・プログラム製品。
【請求項１１】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する装置であって、
第１のノードから、トラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を受信するように構成された受信モジュールと、
前記トラフィック・ストリーム許可要求を受信する前記第２のノードのトラフィック負荷を判定し、前記トラフィック負荷を用いて、前記第１のノードからの要求に関するトラフィック・ストリームを許可するか拒否するかを決定するように構成された決定モジュールと
を備える装置。
【請求項１２】
サービス間隔と呼ばれる期間を確立するように構成されたサービス間隔モジュールと、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定するように構成された時間モジュールと
を更に備える請求項１１に記載の装置。
【請求項１３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項１２に記載の装置。
【請求項１４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択するように構成された選択モジュールを更に備える請求項１１に記載の装置。
【請求項１５】
サービス間隔と呼ばれる期間を確立するように構成されたサービス間隔モジュールと、
近隣ノードから、送信時間割合および受信時間割合を受信するように構成された時間モジュールと
を更に備える請求項１１に記載の装置。
【請求項１６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信するように構成された時間モジュールを更に備える請求項１１に記載の装置。
【請求項１７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定するように構成された測定モジュールを更に備える請求項１１に記載の装置。
【請求項１８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項１１に記載の装置。
【請求項１９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタするように構成されたモニタリング・モジュールを更に備える請求項１１に記載の装置。
【請求項２０】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する装置であって、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信する手段と、
前記第２のノードのトラフィック負荷を判定し、前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定するように構成された手段と
を備える装置。
【請求項２１】
トラフィック・ストリーム許可要求を許可または拒否する手段を更に備える請求項２０に記載の装置。
【請求項２２】
サービス間隔と呼ばれる期間を確立する手段と、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定する手段と
を更に備える請求項２０に記載の装置。
【請求項２３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項２０に記載の装置。
【請求項２４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択する手段を更に備える請求項２０に記載の装置。
【請求項２５】
サービス間隔と呼ばれる期間を確立する手段と、
近隣ノードから、送信時間割合および受信時間割合を受信する手段と
を更に備える請求項２０に記載の装置。
【請求項２６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信する手段を更に備える請求項２０に記載の装置。
【請求項２７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定する手段を更に備える請求項２０に記載の装置。
【請求項２８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項２０に記載の装置。
【請求項２９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタする手段を更に備える請求項２０に記載の装置。
【請求項１】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する方法であって、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信することと、
前記第２のノードのトラフィック負荷を判定することと、
前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定することと
を備える方法。
【請求項２】
サービス間隔と呼ばれる期間を確立することと、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定することと
を更に備える請求項１に記載の方法。
【請求項３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項２に記載の方法。
【請求項４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択することを更に備える請求項１に記載の方法。
【請求項５】
サービス間隔と呼ばれる期間を確立することと、
近隣ノードから、送信時間割合および受信時間割合を受信することと
を更に備える請求項１に記載の方法。
【請求項６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信することを更に備える請求項１に記載の方法。
【請求項７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定することを更に備える請求項１に記載の方法。
【請求項８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項１に記載の方法。
【請求項９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタすることを更に備える請求項１に記載の方法。
【請求項１０】
コンピュータ読取可能媒体を備えるコンピュータ・プログラム製品であって、前記コンピュータ読取可能媒体は、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信する命令と、
前記第２のノードのトラフィック負荷を判定する命令と、
前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定する命令と
を備えるコンピュータ・プログラム製品。
【請求項１１】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する装置であって、
第１のノードから、トラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を受信するように構成された受信モジュールと、
前記トラフィック・ストリーム許可要求を受信する前記第２のノードのトラフィック負荷を判定し、前記トラフィック負荷を用いて、前記第１のノードからの要求に関するトラフィック・ストリームを許可するか拒否するかを決定するように構成された決定モジュールと
を備える装置。
【請求項１２】
サービス間隔と呼ばれる期間を確立するように構成されたサービス間隔モジュールと、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定するように構成された時間モジュールと
を更に備える請求項１１に記載の装置。
【請求項１３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項１２に記載の装置。
【請求項１４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択するように構成された選択モジュールを更に備える請求項１１に記載の装置。
【請求項１５】
サービス間隔と呼ばれる期間を確立するように構成されたサービス間隔モジュールと、
近隣ノードから、送信時間割合および受信時間割合を受信するように構成された時間モジュールと
を更に備える請求項１１に記載の装置。
【請求項１６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信するように構成された時間モジュールを更に備える請求項１１に記載の装置。
【請求項１７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定するように構成された測定モジュールを更に備える請求項１１に記載の装置。
【請求項１８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項１１に記載の装置。
【請求項１９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタするように構成されたモニタリング・モジュールを更に備える請求項１１に記載の装置。
【請求項２０】
メッシュ・ネットワーク内のトラフィック・ストリームを制御する装置であって、
第１のノードからのトラフィック・ストリームを許可するためのトラフィック・ストリーム許可要求を、第２のノードにおいて受信する手段と、
前記第２のノードのトラフィック負荷を判定し、前記トラフィック負荷を用いて、前記第１のノードからのトラフィック・ストリームを許可するか拒否するかを決定するように構成された手段と
を備える装置。
【請求項２１】
トラフィック・ストリーム許可要求を許可または拒否する手段を更に備える請求項２０に記載の装置。
【請求項２２】
サービス間隔と呼ばれる期間を確立する手段と、
前記トラフィック・ストリームの送信機会のための、前記サービス間隔の時間割合を判定する手段と
を更に備える請求項２０に記載の装置。
【請求項２３】
前記送信機会は、保証レート、物理的な最小伝送レート、フレーム・サイズ、スケジュールされたサービス間隔、遅延間期間、およびビーコン間隔から成るグループから選択される請求項２０に記載の装置。
【請求項２４】
前記トラフィック・ストリーム許可要求が拒否されたのであれば、前記第２のノードの代替ノードを選択する手段を更に備える請求項２０に記載の装置。
【請求項２５】
サービス間隔と呼ばれる期間を確立する手段と、
近隣ノードから、送信時間割合および受信時間割合を受信する手段と
を更に備える請求項２０に記載の装置。
【請求項２６】
近隣ノードから、送信時間割合と受信時間割合との合計を受信する手段を更に備える請求項２０に記載の装置。
【請求項２７】
前記第１のノードを前記第２のノードに接続しているチャネルのチャネル・ビジー時間割合を測定する手段を更に備える請求項２０に記載の装置。
【請求項２８】
前記トラフィック・ストリーム許可要求は、前記トラフィック・ストリームを許可または拒否するかを決定するために使用されるトラフィック・ストリーム・クラスを含む請求項２０に記載の装置。
【請求項２９】
平均静寂ネットワーク・アクセス・ベクトル時間をモニタする手段を更に備える請求項２０に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−５４９５６（Ｐ２０１２−５４９５６Ａ）
【公開日】平成２４年３月１５日（２０１２．３．１５）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２１６６０９（Ｐ２０１１−２１６６０９）
【出願日】平成２３年９月３０日（２０１１．９．３０）
【分割の表示】特願２００８−５３６７７８（Ｐ２００８−５３６７７８）の分割
【原出願日】平成１８年１０月１８日（２００６．１０．１８）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公開日】平成２４年３月１５日（２０１２．３．１５）
【国際特許分類】
【出願番号】特願２０１１−２１６６０９（Ｐ２０１１−２１６６０９）
【出願日】平成２３年９月３０日（２０１１．９．３０）
【分割の表示】特願２００８−５３６７７８（Ｐ２００８−５３６７７８）の分割
【原出願日】平成１８年１０月１８日（２００６．１０．１８）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]