(57)【要約】      （修正有）【課題】ワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分する。【解決手段】ワイヤレスメッシュネットワークはノードと、ノードを相互接続するリンクとを含む。ネットワークの容量を増加させ輻輳を回避するために、ネットワークアドミニストレータは、ネットワークノードの動作を制御する様々なパラメータを調節して、ネットワークトラフィックを管理する。ネットワークアドミニストレータは、ノードとリンクの構成を示すトポロジ情報と、各ソースノード・デスティネーションノード・ペアを重み付ける相対的トラフィックデマンドを示すトラフィックマトリックスとを特定する。ネットワークアドミニストレータ帯域幅割り当てを用いて各ノードのパラメータを計算する。そのパラメータはノードが使用する帯域幅の大きさに影響を与える。これらのパラメータをそれぞれのノードに送信する。【選択図】図１
2008228292.tif 000002
【特許請求の範囲】
【請求項１】
ワイヤレスメッシュネットワークにおける帯域幅分配方法であって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する段階と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較して重み付けする相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する段階と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する段階と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する段階と、
各パラメータをそれに対応するワイヤレスノードに送信する段階とを有する方法。
【請求項２】
前記帯域幅割り当てを計算する段階は、前記トラフィックマトリックスと前記トポロジ情報とを線形計画問題に入力する段階を有し、
前記線形計画問題は、前記ワイヤレスノードにおけるフローの保存と、干渉範囲内にあるワイヤレスノードに関連するワイヤレスリンクのチャネル利用とを示す制約条件を含む、請求項１に記載の方法。
【請求項３】
各ワイヤレスノードについて、
負荷は前記ワイヤレスノードからのワイヤレスリンクの帯域幅割り当ての合計に等しく、
前記ワイヤレスノードに対応するパラメータは、前記ワイヤレスノードが使用する帯域幅の大きさを前記負荷に近づける、請求項１に記載の方法。
【請求項４】
前記ワイヤレスメッシュネットワーク中のトラフィックを輻輳が少ないワイヤレスリンクに向けるルーティングテーブルを前記トラフィックマトリックスから計算する段階と、
前記ルーティングテーブルを前記ワイヤレスノードの少なくとも一部に送信する、請求項１に記載の方法。
【請求項５】
前記トラフィックマトリックスにおける前記相対的トラフィックデマンドは各ソースノード・デスティネーションノード・ペアのトラフィック量の時間的平均を表す、請求項１に記載の方法。
【請求項６】
前記トポロジ情報は、ノード数と、前記ノードの位置と、各ノードが通信できるエリアを示す各ノードの通信距離と、各ノードが他の通信と干渉するエリアを示す各ノードの干渉距離とを示す、請求項１に記載の方法。
【請求項７】
前記トポロジ情報は、各ワイヤレスノードについて、前記ワイヤレスノードによる送信と干渉する他のワイヤレスノードと、前記他のワイヤレスノードにより生じる干渉のレベルとを示す、請求項１に記載の方法。
【請求項８】
ワイヤレスメッシュネットワークにおいて帯域幅を分配するネットワークアドミニストレータであって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報と、各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスとを含むメモリと、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算し、各ワイヤレスノードが使用する帯域幅の大きさに影響する前記ワイヤレスノードのパラメータを前記帯域幅割り当てから計算するコントローラと、
各パラメータをそれに対応するワイヤレスノードに送信するネットワークインターフェイスとを有するネットワークアドミニストレータ。
【請求項９】
ワイヤレスメッシュネットワークにおいて帯域幅を分配する論理であって、前記論理は媒体にエンコードされ、実行された時、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する段階と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する段階と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する段階と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する段階と、
各パラメータをそれに対応するワイヤレスノードに送信する段階とを実行させる論理。
【請求項１０】
ワイヤレスメッシュネットワークにおける帯域幅分配システムであって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する手段と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する手段と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する手段と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する手段と、
各パラメータをそれに対応するワイヤレスノードに送信する手段とを有するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してネットワーキングに関し、より具体的にはワイヤレスメッシュネットワークにおけるトラフィックエンジニアリングに関する。
【背景技術】
【０００２】
近年、ワイヤレスメッシュネットワークの利用が増加している。これらのネットワークはメッシュ状に無線で相互接続された複数のノードにより形成される。従来のワイヤレスＬＡＮ（local  area  network）とは異なり、これらのノードは、移動端末（mobile  device）との間でデータトラフィックを転送し、かつノード間の通過トラフィック（transit  traffic）を中継する役割も有している。結果として、これらのノードはワイヤレスマルチホップネットワークを形成する。かかるネットワークのスループットはネットワークの設計及び計画において重要な問題である。
【発明の開示】
【課題を解決するための手段】
【０００３】
本発明により、ワイヤレスメッシュネットワークにおけるトラフィックエンジニアリングの方法を説明する。一部の実施形態では、これらの方法はワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分する。
【０００４】
一部の実施形態では、ワイヤレスメッシュネットワークにおける帯域幅分配方法はトポロジ情報を特定する段階を含む。トポロジ情報は、ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示す。本方法は、ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する。トラフィックマトリックスは、各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較して重み付けする相対的トラフィックデマンドを示す。本方法は、トポロジ情報とトラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅配分を計算し、帯域幅配分から各ワイヤレスノードのパラメータを計算する。そのパラメータはワイヤレスノードが使用する帯域幅の大きさに影響を与える。本方法は、各パラメータをそれに対応するワイヤレスノードに送信する。
【０００５】
本発明の実施形態は様々な技術的有利性を提供する。例えば、これらの方法によりワイヤレスネットワークのスループットを大きくできる。ワイヤレス資源をよりインテリジェントに配分することにより、トラフィック量が大きいエリアにおける輻輳問題を補償し低減することができる。ある実施形態では、ワイヤレスネットワークにおける干渉を認めて、帯域幅パラメータを修正して是正することができる。干渉によりノードがチャネルに頻繁にアクセスできなくなるが、これらの方法は、ノードに、アクセス後、より長い時間送信させ有効帯域幅を大きくすることにより、干渉の効果を低減できる。一部の実施形態では、干渉するノードに帯域幅を分配することによりチャネルへの比較的「公平な」アクセスをさせる。一部の実施形態では、ネットワークにおける帯域幅割り当ては、ＩＥＥＥ８０２．１１ワイヤレス通信プロトコル等の既存の標準規格にすでにあるパラメータを修正することにより実現できる。これによりワイヤレスネットワークは既存の標準規格と完全に互換性を保つことができ、既存のインフラストラクチャに最小限の変更を加えるだけでよい。また、一部の実施形態では、これらの方法により、現在のワイヤレスネットワーキング標準及び技術は、ワイヤレスメッシュネットワークに固有の複雑性に適応することができる。
【０００６】
本発明の他の技術的有利性は、以下の図面、詳細な説明、及び特許請求の範囲に基づき、当業者には容易に明らかとなるであろう。さらに、具体的な有利性を上記したが、様々な実施形態は上記の有利性のすべてまたは一部を含んでもよいし、全く含まなくてもよい。
【０００７】
本発明及びその有利性を完全に理解してもらうため、添付した図面を参照しつつ以下に説明する。
【発明を実施するための最良の形態】
【０００８】
図１は、ワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分するシステム（参照符号１０で示す）を示す図である。図示したように、システム１０はワイヤレスメッシュネットワーク１２とネットワーク１４とを含み、これらは任意の適切な方法またはプロトコルを用いて相互接続されている。一般的に、ワイヤレスメッシュネットワーク１２のエレメントは、ワイヤレスメッシュネットワーク１２にインテリジェントに帯域幅を配分するように相互運用する。キャパシティを増加させて輻輳を回避するために、ネットワークアドミニストレータは、ワイヤレスメッシュネットワーク１２における干渉を判断して、ネットワークノードの動作を制御する様々なパラメータを調節して、ネットワークトラフィックを管理（regulate）する。
【０００９】
ワイヤレスメッシュネットワーク１２はメッシュトポロジ（topology）を有するワイヤレスネットワークを論理的に示したものである。図示した実施形態では、ワイヤレスメッシュネットワーク１２はノード１６と、ワイヤレス端末（wireless  device）１８と、ネットワークアドミニストレータとを含む。図示はしていないが、ワイヤレスメッシュネットワーク１２はその他の任意の適切な装置を含み、帯域幅をインテリジェントに配分するワイヤレスマルチホップネットワークを提供してもよい。一部の実施形態では、ワイヤレスメッシュネットワーク１２は許可を受けた者のみがアクセスできる私企業ネットワークであり、他の実施形態では、ワイヤレスメッシュネットワーク１２は誰でもアクセスできる公的ネットワークである。
【００１０】
一般的に、ノード１６は相互接続してワイヤレスメッシュネットワーク１２を形成する。各ノード１６は他のノードや移動端末１８に信号（communications）を送信し、各ノード１６は他のノード１６及び移動端末１８から信号を受信する。一部の実施形態では、ノード１６はネットワークアドミニストレータ２０から管理メッセージ（management  messages）を受信する。ノード１６は、ネットワークアドミニストレータから受信したメッセージに従うために、これらのメッセージを処理し、送信パラメータ、ルーティングテーブル、及び／またはその他の適切なメモリ及び／または手順を更新する。一部の実施形態では、ノード１６は、ＩＥＥＥ８０２．１１やＩＥＥＥ８０２．１６などの標準規格に則ったプロトコルに従って通信する。一般的に、ノード１６は任意の適切なハードウェア、ソフトウェア、制御論理の集合（collection）であり、ワイヤレスメッシュネットワーク１２において信号（communications）を送信、受信、及び／または処理する。
【００１１】
図示した実施形態では、ワイヤレスメッシュネットワーク１２はノード１６ａ、１６ｂ、１６ｃ、１６ｄ、及び１６ｅを含む。ワイヤレスリンク（点線で示した）が次のノード間にある：（１）ノード１６ａと１６ｂ、（２）ノード１６ｂと１６ｄ、（３）ノード１６ｄと１６ｃ、（４）ノード１６ｄと１６ｅ、（５）ノード１６ｃと１６ｅ、及び（６）ノード１６ｅと１６ａ。一部の実施形態では、ノード１６は限られた範囲において、ワイヤレスメッシュネットワーク１２中の他のノード１６、移動端末１８、またはその他の装置と通信することができる。例えば、ノード１６ｃの範囲には、例示したワイヤレスリンク（点線）で示したようにノード１６ｄと１６ｅが入っているが、その他のノード１６は含まれていない。さらに、ノード１６は無線で通信するので、１つのノード１６が送信した通信は他のノード１６巻の通信と干渉することがある。一部の実施形態では、一ノード１６の干渉範囲はそのノード１６の通信可能範囲よりも広い。例えば、一実施形態では、各ノード１６は他のノード１６と２５０メートルまで離れても通信できるが、５５０メートル離れた他の無線通信と干渉することがある。一方、ワイヤレスメッシュネットワーク１２は、５つのノードを有するものとして図示し、説明したが、言うまでもなく、任意の適切な数のノード１６を有していてもよい。
【００１２】
例示したように、ワイヤレスメッシュネットワーク１２は無線端末１８を含み、その無線端末１８のユーザは音声、ビデオ、データ、その他の任意の適切な信号を送受信できる。無線端末１８は、他の無線端末１８、ノード１６、その他のワイヤレスメッシュネットワーク１２内のエレメントと通信するため、他の１つ以上のノード１６を介して接続する。一部の実施形態では、無線端末１８は、ネットワーク１４またはその他の外部ネットワークや外部装置にアクセスするために、１つ以上のノード１６を介して通信する。一部の実施形態では、無線端末（wireless  devices）にはパーソナルコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、ＶｏＩＰ電話、携帯電話、またはネットワークにおいて無線通信できる適切なその他の装置が含まれる。ワイヤレスメッシュネットワーク１２には２つの無線端末１８のみを示したが、言うまでもなく、ワイヤレスメッシュネットワーク１２に含まれる無線端末１８の数はいくつでもよい。
【００１３】
ネットワーク１４は、通信端末を相互接続するハードウェア、ソフトウェア、その他の制御論理の任意の適切な集合を表している。例示した実施形態では、ネットワーク１４はワイヤレスメッシュネットワーク１２の外部にあるネットワークである。一部の実施形態では、ネットワーク１４は、電気通信ネットワーク、衛星ネットワーク、ケーブルネットワーク、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、インターネット、イーサネット(登録商標)、その他の適切なネットワーク等を含み得る。
【００１４】
一部の実施形態では、ノード１６ｅは有線接続によりネットワーク１４と接続されている（両者を結ぶ実線で示した）。その他のノード１６は、ノード１６ｅを介してネットワーク１４またはそのネットワーク１４に接続された装置と通信できる。一部の実施形態では、ノード１６ｅはネットワーク１４とワイヤレスメッシュネットワーク１２中のエレメント（element）（例えば、その他のノード１６や無線端末１８）との間でメッセージを中継する。一部の実施形態では、ノード１６ｅは、ゲートウェイその他の適切な装置を介してネットワーク１４に接続されてもよく、異質のネットワーク間の相互運用をサポートするゲートウェイ機能を提供してもよい。システム１０は、１つのネットワーク１４のみがノード１６ｅを介してワイヤレスメッシュネットワーク１２に接続されているとして例示したが、言うまでもなく、任意の適切な数のネットワーク１４やその他の適切な装置やその組合せを任意の適切な方法でワイヤレスメッシュネットワーク１２に接続してもよい。
【００１５】
ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２における帯域幅をインテリジェントに配分するために、ワイヤレスメッシュネットワーク１２に関する情報を集め（determine）、その情報を処理し、ノード１６に命令を与える。ネットワークアドミニストレータ２０は任意の適切な方法でノード１６と通信できる。一部の実施形態では、ネットワークアドミニストレータ２０は、その通信範囲内にあるノード１６と無線通信し、ワイヤレスメッシュネットワーク１２中のその他のノード１６と通信するため、その通信範囲内にあるノード１６を介してメッセージをルーティングする。他の一部の実施形態では、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２中の各ノード１６と無線通信できる。一部の実施形態では、ネットワークアドミニストレータ２０は、有線接続（図示せず）その他の任意の適切な方法でノード１６と通信する。ネットワークアドミニストレータ２０は、独立した装置として例示したが、ノード１６の１つと一体になっていてもよい。ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２において帯域幅のインテリジェントな配分を指示する任意の適切なハードウェア、ソフトウェア、制御論理の集合（collection）である。
【００１６】
動作中、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２のトポロジ情報（topology  information）を特定する。ネットワークアドミニストレータ２０は、そのトポロジ情報を用いて、ワイヤレスメッシュネットワーク１２における干渉（interference）の存否、程度、場所を判断できる。一部の実施形態では、ワイヤレスメッシュネットワーク１２においては、外部の装置やネットワーク等の影響により、干渉が生じることもある。トポロジ情報には、これらの外部からの影響により生じる干渉の情報が含まれていてもよい。一部の実施形態では、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２のトラフィック情報（traffic  information）を調べる（determine）。トラフィック情報はソースノード（source  node）１６とデスティネーションノード（destination  node）１６との間で必要とされるトラフィック負荷の情報を含んでいてもよい。トラフィック情報は、一部の実施形態では推定値であってもよく、他の実施形態では実際のトラフィックフローを表す情報であってもよい。一例として、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２の動作を問い合わせ、または直接調べてトラフィック情報を判断する。ネットワークアドミニストレータ２０は、ノード１６等の他の装置を使って（rely  on）トラフィック情報を監視し、報告させてもよい。一部の実施形態では、ネットワークアドミニストレータ２０は、このトラフィック情報を、各ノード１６からその他のすべてのノード１６への相対的なトラフィック量を示すトラフィックマトリックスとして表してもよい。トラフィックマトリックス（traffic  matrix）は、ソースノード１６とデスティネーションノード１６の各ペアに対して、そのペアを他のペアと比較した相対的なトラフィックの需要を示す。ワイヤレスメッシュネットワーク１２中の各ソースノード１６から各デスティネーションノード１６への実際のトラフィック負荷を求めるには、トラフィックマトリックスにスカラー値をかければよい。ネットワークアドミニストレータ２０は、そのスカラー値を最大化するために帯域幅を配分する。一部の実施形態では、ネットワークアドミニストレータ２０は、トラフィック情報を利用してワイヤレスメッシュネットワーク１２を介したパケットのインテリジェントなルーティングを指示する。
【００１７】
ネットワークアドミニストレータ２０は、トポロジ情報とトラフィック情報とを用いて、場合によってはワイヤレスメッシュネットワーク１２中の各リンクに対し、帯域幅の割り当てを計算する。各帯域幅割り当ては、リンクの望ましい帯域幅を表している。一部の実施形態では、ネットワークアドミニストレータ２０は、リンクのスループットではなくノード１６のスループットを用いて計算を簡単にする。そうするために、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２中の各ノードの帯域幅割り当てを計算する。帯域幅割り当てを決定してから、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２中の各ノード１６のパラメータを計算する。これらのパラメータはノード１６に送られ、組み入れられる。このパラメータの値によりノード１６の動作が制御され、そのノード１６の帯域幅利用が決定され、ネットワークアドミニストレータ２０により選択された帯域幅配分が実現される。一部の実施形態では、ネットワークアドミニストレータ２０は、対応する帯域幅配分をリンクまたはノード１６が使用する帯域幅に近づけるように、各ノード１６のパラメータを計算する。
【００１８】
ワイヤレスメッシュネットワーク１２内の装置がＩＥＥＥ８０２．１１ワイヤレス通信プロトコルに従って通信するとき、ネットワーク中の相異なるリンク及び／またはノード１６の実際の帯域幅を決める（affect）ためにいくつかのパラメータを使用する。ＩＥＥＥ８０２．１１を使用するネットワークでは、ネットワークアドミニストレータ２０は、ノード１６の帯域幅利用を決めるために、ＴＸＯＰ（transmission  opportunity）の値を変更する。ＴＸＯＰは、ＩＥＥＥ８０２．１１標準で規定されたパラメータであり、あるノード１６が一度媒体にアクセスした時にパケットを送信できる最大時間を表している。送信されるパケットの長さがＴＸＯＰより小さい場合、ノード１６はＴＸＯＰに達するまで、より多くのパケットを連続的に送信することができる。ＴＸＯＰパラメータの本来の目的を拡張して、ノード１２ごとにＴＸＯＰの値を選択して、ワイヤレスメッシュネットワーク１２中のノード１６に帯域幅を割り当ててもよい。ＴＸＯＰの値が大きければ大きいほど、対応するノード１６が一旦チャネルを獲得した時にパケットを送信できる時間が長くなる。ＴＸＯＰの値が小さければ、対応するノード１６が一旦チャネルを獲得してからパケットを送信できるウィンドウが小さくなる。従って、ネットワークアドミニストレータ２０は、所望の帯域幅配分（bandwidth  allocation）を実現するために、ノード１６のＴＸＯＰ値を計算する。別の実施形態では、別のＩＥＥＥ８０２．１１パラメータを使用してノード１６の有効帯域幅を決める（affect）ことができる。例えば、ＩＦＳ（interframe  slot）及びコンテンションウィンドウ（contention  window）を修正して、ワイヤレスメッシュネットワーク１２のノード１６及び／またはリンクの実際の帯域幅を変更できる。様々なパラメータを調節することにより、ネットワークアドミニストレータ２０はノード１６の動作を制御しトラフィックを操作でき、干渉を考慮してキャパシティを増やし輻輳を回避することができる。
【００１９】
ＩＥＥＥ８０２．１１プロトコルを参照してワイヤレスメッシュネットワーク１２を説明したが、言うまでもなく他の実施形態では、ワイヤレスメッシュネットワーク１２中の装置は別のプロトコルで通信してもよい。例えば、ワイヤレスメッシュネットワーク１２はＷｉＭＡＸ（すなわちＩＥＥＥ８０２．１６）通信プロトコルにより動作するものであってもよい。それらの実施形態では、ネットワークアドミニストレータ２０は実際のノードの帯域幅を修正するために、任意の適切なパラメータを使用できる。
【００２０】
ワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分するシステムの実施形態を説明したが、すべてを含む必要はない。エレメントの一定の設定と構成を含むものとしてワイヤレスメッシュネットワーク１２を説明したが、留意すべきこととして、これは論理的表示であって、ワイヤレスメッシュネットワーク１２の構成要素や機能は必要に応じて論理的及び物理的に結合されても、分離されても、分散されてもよい。また、コンポーネントの任意の適切な集合と構成によりワイヤレスメッシュネットワーク１２の機能を実現してもよい。「パラメータ」として説明したが、言うまでもなく、ここで使用する「パラメータ」には任意の適切なパラメータ、特性、アルゴリズム、機能、テーブル、プロトコル、変数などが含まれる。
【００２１】
図２は、ワイヤレスメッシュネットワーク１２において帯域幅の配分を決定するネットワークアドミニストレータ２０を示すブロック図である。図示したように、ネットワークアドミニストレータ２０はネットワークインターフェイス５２と、コントローラ５４と、メモリ５６とを含む。
【００２２】
ネットワークインターフェイス５２はシステム１０のその他のエレメントとの通信をサポートする。一部の実施形態では、ネットワークインターフェイス５２はワイヤレスメッシュネットワーク１２中の各ノード１６と通信するためのワイヤレスインターフェイスである。ネットワークインターフェイス５２はワイヤレスメッシュネットワーク１２中の他の装置と無線で通信してもよい。一部の実施形態では、ネットワークインターフェイス５２は、ワイヤレスメッシュネットワーク１２を含む複数のネットワークと接続できる。例えば、ネットワークインターフェイス５２はイーサネット(登録商標)やインターネット（図示せず）等の有線ネットワークに接続することもできる。ネットワークインターフェイス５２は、ネットワークアドミニストレータ２０内の単一のコンポーネントとして例示したが、これは言うまでもなく論理的な表現である。ネットワークインターフェイス５２は、ネットワークアドミニストレータ２０をシステム１０の他のエレメントとインターフェイスさせる任意の適切なコンポーネント、ハードウェア、ソフトウェア、及び／または論理よりなる。
【００２３】
一般的に、コントローラ５４はネットワークアドミニストレータ２０の動作、計算、及び機能を制御する。コントローラ５４はネットワークインターフェイス５２を介してネットワークアドミニストレータ２０が受信した情報を処理する。一部の実施形態では、コントローラ５４は、ノード１６の帯域幅割り当てとパラメータとを計算するために、メモリから機能、アルゴリズム、データをロードし、ネットワークアドミニストレータ２０内の単一エレメントとして示したが、言うまでもなく、コントローラ５４の機能は１つ以上のエレメントにより実行されてもよい。コントローラ５４は、ネットワークアドミニストレータ２０の動作を制御するその他の任意の適切な機能を有する。
【００２４】
メモリ５６はネットワークアドミニストレータ２０が使用するデータとアルゴリズムを格納する。例示した実施形態では、メモリ５６は、動作論理５８、ネットワークトポロジ６０、トラフィックマトリックス６２、帯域幅アルゴリズム６４、及び帯域幅データ６６を含む。動作論理５８は、実行されたとき、ネットワークアドミニストレータ２０中の様々なエレメントの動作を制御し、ネットワークアドミニストレータ２０が必要とするその他の任意の機能を実行する、任意の適切なプログラム、ソフトウェア、論理、回路を含む。
【００２５】
ネットワークトポロジ６０はワイヤレスメッシュネットワーク１２のトポロジに関する情報を含む。一部の実施形態では、トポロジ情報はノード１６の数、ノード１６の設定（configuration）、各ノード１６の信号強度、及び／またはその他の任意の適切な情報を含む。ネットワークトポロジ６０はワイヤレスメッシュネットワーク１２の様々な部分の干渉の大きさを示す。一部の実施形態では、ネットワークアドミニストレータ２０は所望の帯域幅配分を決定するためにネットワークトポロジ６０を使用する。一部の実施形態では、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２を介してパケットをいかにルーティングするか決定するために、ネットワークトポロジ６０を使用する。トラフィックマトリックス６２はワイヤレスメッシュネットワーク１２の様々な部分のトラフィック量に関する情報を含む。トラフィックマトリックス６２は、実際の無線トラフィック、（例えば、シミュレーションによる）トラフィック予想、履歴データ、またはトラフィック情報の適切な組合せを反映している。ネットワークアドミニストレータ２０は、データのタイプや情報の取得方法に基づき、適切であれば、トラフィックマトリックス６２を更新する。一部の実施形態では、トラフィックマトリックス６２は各ソースノード１６から各デスティネーションノード１６への相対的なパケットのフローを示す。このように、トラフィックマトリックス６２は、ワイヤレスメッシュネットワーク１２中の各ノード１６間のフローを含む２次元配列として表される。
【００２６】
帯域幅アルゴリズム６４は、ノード１６の帯域幅配分とパラメータを計算するために、ネットワークアドミニストレータ２０が利用する式とアルゴリズムを含む。例えば、帯域幅アルゴリズム６４は、帯域幅配分を求めるためにネットワークトポロジ６０とトラフィックマトリックス６２を処理するアルゴリズムと、場合によってはその他のデータとをともに含む。同様に、帯域幅アルゴリズム６４は、ノード１６のパラメータ値を決定するために帯域幅配分（bandwidth  allocation）を入力するアルゴリズムを含む。帯域幅データ６６は計算された帯域幅配分とパラメータ値を格納する。一部の実施形態では、帯域幅アルゴリズム６４は図５に参照して以下に説明する式と同様の式を含む。一般的に、メモリ５６は、記憶要素の任意の適切な組合せ及び構成から形成され、ネットワークアドミニストレータ２０が使用するデータとアルゴリズムを格納する。
【００２７】
メモリ５６は具体的な構成のモジュールを含む単一のエレメントとして例示して説明したが、これは論理的な表示であって、メモリ５６のコンポーネントと機能は１つ以上の物理的な場所にある任意の適切なエレメントを含む。メモリ５６はネットワークアドミニストレータ２０が使用する情報を格納する。
【００２８】
動作中、ネットワークアドミニストレータ２０は、ネットワークトポロジ６０に格納された情報にアクセスして、ワイヤレスメッシュネットワーク１２のトポロジに関する情報を特定してもよい。ネットワークアドミニストレータ２０は、トラフィックマトリックス６２にアクセスして、ワイヤレスメッシュネットワーク１２のトラフィック情報を取得（determine）してもよい。一部の実施形態では、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２中の１つ、多数、またはすべてのノード１６から状態メッセージを受け取り、処理した後、トラフィック情報を決定してもよい。ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２中のトラフィックフローに関する情報を、ワイヤレスメッシュネットワーク１２中の他の装置に問い合わせてもよい。他の実施形態では、ネットワークアドミニストレータ２０は別の装置またはエレメントからトラフィック情報を受け取る。ネットワークアドミニストレータ２０は、この情報を、定期的に、ネットワークアドミニストレータ２０が送信する要求に応答して、またはトラフィック情報に変化があったときに受け取ることもできる。
【００２９】
ネットワークアドミニストレータ２０はネットワークトポロジ６０、トラフィックマトリックス６２、及び帯域幅アルゴリズム６４を使用して、ワイヤレスメッシュネットワーク１２中の帯域幅配分を計算する。帯域幅配分はワイヤレスメッシュネットワーク１２中の各リンク及び／または各ノード１６の帯域幅の望ましい使用を示している。一部の実施形態では、帯域幅配分はワイヤレスメッシュネットワーク１２の一部が使用する望ましい帯域幅を示す。例えば、トラフィックマトリックス６２が、ワイヤレスメッシュネットワーク１２の一部分に大量のトラフィックがあることを示す場合、ネットワークアドミニストレータ２０はそのワイヤレスメッシュネットワーク１２の一部分のために帯域幅を計算する。ネットワークアドミニストレータ２０は帯域幅データ６６に帯域幅配分を格納する。
【００３０】
帯域幅配分と帯域幅アルゴリズム６４とを用いて、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２の帯域幅に影響を与える１つ以上のパラメータを計算する。ネットワークアドミニストレータ２０は１つ以上のノード１６に対して相異なるパラメータを選択して、対応するノード１６が使用する帯域幅が望ましい帯域幅配分に近づくようにする。一部の実施形態では、ネットワークアドミニストレータ２０は各ノード１６のＴＸＯＰ値を選択する。あるノード１６に割り当てられたＴＸＯＰ値が大きいと、そのノード１６はチャネルを取得したときにデータを送信する時間が長くなり、その結果、そのノード１６の帯域幅が大きくなる。ＴＸＯＰ値が小さいと、ノード１６がデータを送信する時間が短くなり、その結果、ノード１６の帯域幅が小さくなる。一部の実施形態では、ネットワークアドミニストレータ２０はＴＸＯＰの値を計算し、使用帯域幅が望ましい帯域幅配分に近づくようにする。この計算の実施形態は図５を参照して説明する。別の実施形態では、別のＩＥＥＥ８０２．１１パラメータを使用してノード１６の有効帯域幅を決める（affect）ことができる。例えば、ＩＦＳ（interframe  slot）とコンテンションウィンドウ（contention  window）を修正して各ノード１６の有効帯域幅を変更する。適切であれば、ネットワークアドミニストレータ２０は異なるパラメータを使用して、各ノード及び／またはリンクが使用する帯域幅を設定または調節する。帯域幅アルゴリズム６４はこれらのパラメータのためのアルゴリズム、式などを格納している。
【００３１】
一部の実施形態では、ネットワークアドミニストレータ２０は、ワイヤレスメッシュネットワーク１２を介したパケットのルーティングを制御してスループットを改善するようにも動作する。例えば、ネットワークアドミニストレータ２０はノード１６が持っているパケットルーティングテーブルを監視し、エントリーを入れ（populate）、調節し、あるいは制御してもよい。具体的な例として、ネットワークアドミニストレータ２０は、トラフィックマトリックス６２を調べて（evaluate）、ノード１６ｄからノード１６ｅに、及びノード１６ｂからノード１６ｅに大量のトラフィックが流れていると判断する。その判断後、ネットワークアドミニストレータ２０はネットワークトポロジ６０を調べて（evaluate）、パケットをノードｂからノード１６ｅにどのようにルーティングするか判断する。図１に示したネットワークにおいて、これらのパケットはノード１６ａまたはノード１６ｄのいずれかを介してルーティングできる。ノード１６ａのトラフィックがノード１６ｄのトラフィックより少なければ、ネットワークアドミニストレータ２０は、ノード１６ｂからノード１６ｅへのトラフィックをノード１６ｄではなくノード１６ａを介してルーティングするように、ノード１６のルーティングテーブルを更新する。簡単な例で説明したが、この考え方は様々なルーティングデザインに適用できる。
【００３２】
ネットワークアドミニストレータ２０の具体的な実施形態を説明したが、これらすべてを含む必要はない。一定の設定と構成のエレメントを含むものとしてネットワークアドミニストレータ２０を説明したが、留意すべきこととして、これは論理的表示であって、ネットワークアドミニストレータ２０の構成要素や機能は必要に応じて論理的及び物理的に結合されても、分離されても、分散されてもよい。また、コンポーネントの任意の適切な集合と構成によりネットワークアドミニストレータ２０の機能を実現してもよい。一部の実施形態では、ネットワークアドミニストレータ２０はノード１６の１つと一体になっていてもよい。一部の実施形態では、ネットワークアドミニストレータ２０の機能はワイヤレスメッシュネットワーク１２中のノード１６の一部またはすべてに分散していてもよい。一部の実施形態では、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２の外部にあってもよい。ネットワークアドミニストレータ２０は複数のワイヤレスメッシュネットワークに帯域幅をインテリジェントに配分することもできる。また、ネットワークアドミニストレータ２０はその他の任意の適切なコンポーネント、エレメント、装置、及び機能を有していてもよい。例えば、ネットワークアドミニストレータ２０は、ユーザ（individual）にワイヤレスメッシュネットワーク１２中のトラフィックフロー及び帯域幅配分を監視させ、場合によっては制御させるユーザインターフェイスを有していてもよい。要約すると、ネットワークアドミニストレータ２０の様々なコンポーネントが実行する機能は、ワイヤレスメッシュネットワーク１２において帯域幅をインテリジェントに配分する任意の適切な装置により実現することができる。
【００３３】
図３Ａ乃至図３Ｃは、ワイヤレスメッシュネットワークの一例のトポロジと、ネットワークノード間の帯域幅の配分のために選択されたパラメータと、帯域幅配分のシミュレーション結果とを示す。図３Ａは、１０個のノード１０２ａ−ｊを含むワイヤレスメッシュネットワーク１００の一例を示す図である。例示した実施形態において、ノード１０２は、２５０メートル間隔で配置され、２５０メートルまで離れた他のノード１０２と通信することができる。従って、ノード１０２は、矢印で示したように、隣接したノード１０２のみと通信できる。例示したように、ノード１０２ａはノード１０２ｂのみと通信でき、ノード１０２ｂはノード１０２ａまたはノード１０２ｃのいずれかと通信できる。また、ノード１０２は５５０メートル離れても干渉を起こす。ワイヤレスメッシュネットワーク１００はネットワークアドミニストレータ（図示せず）も含む。このネットワークアドミニストレータはネットワークアドミニストレータ２０でもよい。
【００３４】
図３Ｂはノード１０２に対して選択されたパラメータを示すテーブル１０４である。例示した実施形態では、ノード１０２はＩＥＥＥ８０２．１１ワイヤレス通信プロトコルに従ってメッセージを送受信する。各ノード１０２はその隣接するノード１０２の各々と一定ビットレート（ＣＢＲ）接続を確立する。テーブル１０４は各ノード１０２のＴＸＯＰの値を示している。この値は、図５を参照して説明する式と方法により計算できる。
【００３５】
テーブル１０４では、ノード１０２ａと１０２ｊのＴＸＯＰ値は１であり、ノード１０２ｂと１０２ｉのＴＸＯＰ値は３．６９１であり、ノード１０２ｃと１０２ｈのＴＸＯＰ値は５．８５２であり、ノード１０２ｄと１０２ｇのＴＸＯＰ値は７．３６１であり、ノード１０２ｅと１０２ｆのＴＸＯＰ値は８．０８４である。メッシュの中心のノード１０２（例えば、ノード１０２ｅと１０２ｆ）が受ける干渉は他のノードよりも大きい。ワイヤレスメッシュネットワーク１００中のより多くのノード１０２からの干渉を受けるからである。しかし、ワイヤレスメッシュネットワークの端のノード１０２（例えば、ノード１０２ａと１０２ｊ）は他のノード１０２からの干渉が少ない。テーブル１０４は、これらの中心付近のノード１０２に割り当てられる値が端に近いノード１０２に割り当てられるノード１０２より大きいことを示している。従って、テーブル１０４に示された帯域幅配分により、すべてのノードがより「公平（fair）」に帯域幅を利用できる。
【００３６】
図３Ｃは、テーブル１０４に示したＴＸＯＰ割り当ての例による効果を示すグラフ１０６である。グラフ１０６は、これらの割り当てたＴＸＯＰ値をシミュレーションしたワイヤレスメッシュネットワーク１００のノード１０２に適用してものである。グラフ１０６の横軸１０８は、ノード１０２に対応するノードインデックスを示す。グラフ１０６の縦軸１１０は、到達比率（delivery  ratio）、すなわちパケット総数に対する到達したパケットの比率を示す。
【００３７】
凡例１１２にグラフ１０６に示した４つの線の意味が説明されている。凡例１１２中の一番上の線１１４は、すべてのノードのＴＸＯＰが等しく、送信データレートが４００キロビット毎秒である場合の、ノード１０２の配信比率を示している。凡例１１２中の二番目の線１１６は、すべてのノードのＴＸＯＰが等しく、送信データレートが６００キロビット毎秒である場合の、ノード１０２の配信比率を示している。凡例１１２中のその次の線１１８は、ＴＸＯＰがテーブル１０４にＴＸＯＰ値に設定され、送信データレートが４００キロビット毎秒である場合の、ノード１０２の配信比率を示している。凡例１１２中の一番下の線１２０は、ＴＸＯＰがテーブル１０４にＴＸＯＰ値に設定され、送信データレートが６００キロビット毎秒である場合の、ノード１０２の配信比率を示している。グラフ１０６から分かるように、最も干渉が大きいノード１０２の配信比率は、そのノードに他のノード１０２のＴＸＯＰ値よりも大きなＴＸＯＰ値を設定することにより、大幅に高くなる。
【００３８】
ワイヤレスメッシュネットワークの具体的な実施形態を説明したが、これらすべてを含む必要はない。ワイヤレスメッシュネットワーク１００はエレメントの一定の設定及び構成を含むものとして説明したが、これは一例に過ぎないことに留意すべきである。同様に、例示したパラメータ（すなわち、ＴＸＯＰ）やそのパラメータの値は、単に例示した具体的な実施形態を説明するために設けたものである。
【００３９】
図４は、ワイヤレスメッシュネットワーク１２においてネットワークアドミニストレータ２０が帯域幅を割り当てる方法１５０を示すフローチャートである。方法１５０はステップ１５２で始まり、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２のトポロジを特徴付ける情報を特定する。このトポロジ情報はワイヤレスメッシュネットワーク１２の構成（configuration）を示す。一部の実施形態では、トポロジ情報はノード１６の数、場所、設定を特定する。一部の実施形態では、トポロジ情報を使用して、ワイヤレスメッシュネットワーク１２中の相異なる場所における干渉量を決定することができる。この決定は、その干渉がノード１６等のワイヤレスメッシュネットワーク１２内の装置によるものか、外部の要因によるものかに拘わらずできる。ある実施形態では、トポロジ情報はネットワークトポロジ６０としてネットワークアドミニストレータ２０に格納される。
【００４０】
ステップ１５４において、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２のトラフィック情報（traffic  information）を調べる（determine）。トラフィック情報はワイヤレスメッシュネットワーク１２の相異なる部分を介したトラフィックフローを示す。一部の実施形態では、トラフィック情報は各ソースノード１６から各デスティネーションノード１６へのパケットの平均数の詳細を示す。トラフィック情報は、ワイヤレスメッシュネットワーク１２中のトラフィックの総量または相異なるノード１６間の相対的ネットワークトラフィックの表示を含む。ある実施形態では、トラフィック情報はトラフィックマトリックス６２としてネットワークアドミニストレータ２０に格納される。一部の実施形態では、ステップ１５４はステップ１５２の前に実行しても、同時に実行してもよい。次に、ステップ１５６において、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２中のリンクの帯域幅割り当てを計算する。ネットワークアドミニストレータ２０は、帯域幅割り当てを計算するためにトラフィック情報とトポロジ情報とを使用する。一リンクの帯域幅割り当て（bandwidth  assignment）は、そのリンクへの所望の帯域幅配分（bandwidth  allocation）を示す。一部の実施形態では、ネットワークアドミニストレータ２０は、トラフィックエンジニアリングを要するワイヤレスメッシュネットワーク１２の一部に対する帯域幅割り当てを計算する。しかし、他の実施形態では、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２中の各リンクの帯域幅割り当てを計算する。一部の実施形態では、ネットワークアドミニストレータ２０は帯域幅データ６６に帯域幅割り当てを格納する。帯域幅割り当ての計算の実施形態を図５を参照して例示して説明する。
【００４１】
ステップ１５８において、ネットワークアドミニストレータ２０は、帯域幅割り当てを用いて各ノード１６のパラメータを計算する。パラメータにより各ノード１６が利用できる帯域幅が変化する。一部の実施形態では、パラメータはＴＸＯＰ値である。各ノード１６はそれに割り当てられたＴＸＯＰ値を用いて、そのノード１６が使用する帯域幅を変更する。パラメータ計算の実施形態を図５を参照して例示して説明する。図４のステップ１６０において、ネットワークアドミニストレータ２０はパラメータをそれぞれにノード１６に送信する。この送信は任意の適切な方法で実現できる。ステップ１６２において、ネットワークアドミニストレータ２０は、パラメータを更新するかどうか決定する。一部の実施形態では、前のパラメータ割り当ての有効性に関するデータを見てからこの決定を行う。他の実施形態では、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２におけるトラフィックのレベルまたは構成の違いに基づき、パラメータを更新するかどうか判断（evaluate）する。ネットワークアドミニストレータ２０は、パラメータを更新するとき、ステップ１５４に戻り、ワイヤレスメッシュネットワーク１２の更新されたトラフィック情報を決定する。しかし、ネットワーク２０がパラメータを更新しないと決定すると、方法１５０は終了する。
【００４２】
図４を参照して説明した方法は単なる例示であり、言うまでもなく動作のしかたやその動作を実行する装置は任意の適切なように修正してもよい。本方法では、具体的なステップを特定の順序で実行するものとして説明したが、言うまでもなく、ワイヤレスメッシュネットワーク１２は任意の適切なエレメントの集合及び配置が、任意の動作可能な順序で、これらのステップの一部または全部を実行しても、またはどのステップを実行しなくてもよい。例えば、一部の実施形態では、ネットワークアドミニストレータ２０は各ノード１６の２つ以上のパラメータを計算する。
【００４３】
図５は、リンク帯域幅割り当ての計算とノード１６のパラメータの計算の方法２００の一実施形態を示すフローチャートである。方法２００は、ステップ２０２で始まり、ネットワークアドミニストレータ２０はトラフィック情報とトポロジ情報とを利用して線形計画問題を定式化する。一部の実施形態では、ネットワークアドミニストレータ２０は、ステップ１５４で決定したトラフィック情報と、ステップ１５２で特定したトポロジ情報とを利用する。線形計画問題は次のように定式化できる：
【数１】
2008228292.tif 000003
表示を分かりやすくするため、各記号の意味を表１に示した。
【表１】
2008228292.tif 000004
【００４４】
ある実施形態では、トポロジ情報はＶ，Ｅ，ＥＩ及びＣ（ｅ）を含み、トラフィック情報はレートベクトルｒで表される。レートベクトルｒはソースノード１６とデスティネーションノード１６の各ペアのトラフィック負荷を示す。これらの変数は上記の線形計画問題に入力される。式（２）と（３）は、それぞれソースノード１６と中間ノード１６におけるフローの保存を示す。式（４）はワイヤレスメッシュネットワーク１２におけるトラフィックフローの干渉による制約を表す。ここで、
【数２】
2008228292.tif 000005
はリンクｅ′を通るすべてのフロー（flows  of  all  commodities）の合計を表す。互いに干渉範囲内にあるノード１６のペアについて、いずれのノード１６に関連するリンクのチャネル利用を合計すると１以下になる。各リンクｅの望ましいリンクレートｆ（ｅ）は、ステップ２０４で示したように、式（１）乃至（４）により表される線形計画問題を解くことにより求められる。一部の実施形態では、この値は帯域幅データ６６に格納される。
【００４５】
ステップ２０６において、ネットワークアドミニストレータ２０はノード１６の期待スループットを推定する。例示した実施形態では、ノード１６は８０２．１１ワイヤレス通信プロトコルで通信し、ネットワークアドミニストレータ２０はワイヤレスメッシュネットワーク１２において帯域幅を配分するためにＴＸＯＰをパラメータとして使用する。一部の実施形態では、ネットワークアドミニストレータ２０は出て行くすべてのリンクに対して同じＴＸＯＰとし、各リンクのスループットを使わずにノード１６のスループットを用いて、計算を簡単にすることができる。しかし、他の実施形態では、ネットワークアドミニストレータ２０はノードを制約せずに、出て行くすべてのリンクに対して同じパラメータを使用しない。
【００４６】
ノード１６の１つｖに分配された帯域幅の部分は次式で表される：
【数３】
2008228292.tif 000006
ここで、ｖはノードであり、ＴＸ（ｖ）はノードｖのＴＸＯＰ値であり、ｗ（ｖ）はチャネルにアクセスできる頻度である。ノードｖはその干渉範囲内の隣接ノードＮＩ（ｖ）のすべてのノードとチャネルを共有する必要があるので、ノードｖに分配された帯域幅の部分は次に関係する：（１）ノードｖがチャネルの獲得に成功する確率ｗ（ｖ）と、（２）ノードｖがチャネルの獲得に成功するたびにどれくらい長い間（すなわち、ＴＸＯＰ）データを送信するか。
【００４７】
ステップ２０８において、ネットワークアドミニストレータ２０は、ノードｖがチャネルのアクセスに成功する頻度ｗ（ｖ）を決定する。ある実施形態では、ノードｖの重みであるｗ（ｖ）の物理的意味は、ノードｖが長い期間に送信の機会を取得する回数である。シングルホップネットワークの場合、干渉近傍（interference  neighborhood）がすべてのノードを含み、各ノードはデータを送信する機会が等しくなるので、重みはすべてのノードで同じになる。一部の実施形態では、ノード１６がマルチホップネットワークを形成すると、ネットワークアドミニストレータ２０はｗ（ｖ）の推定を簡単化する。ネットワークアドミニストレータ２０は、あるノード１６の干渉範囲内のすべてのノード１６がシングルホップネットワークを形成すると仮定する。シングルホップネットワークについて得られるマルコフ連鎖モデルに基づき、媒体へのアクセスが２回成功する間の平均時間は（フリージングアイドル期間（freezing  idle  period）を考えないと）：
【数４】
2008228292.tif 000007
ここで、Ｗは最初の最大コンテンションウィンドウであり、ｍは最大バックオフステージであり、ｐは衝突確率である。ＴとＰは、あるノード１６の干渉範囲内にあるノード１６の数に関係する。干渉範囲はネットワークトポロジに依存する。言い換えると、他のノード１６が多数いるエリアに、あるノード１６がいるとき、チャネルへのアクセスが２回成功する間の時間は長くなる。パラメータｗ（ｖ）は時間Ｔ（ｖ）の逆数として推定できる。ある実施形態では、ネットワークアドミニストレータ２０は、任意の適切な技術、式、アルゴリズム、及び／または方法を利用して、ノードｖがチャネルへのアクセスに成功する頻度ｗ（ｖ）を決定する。
【００４８】
ステップ２１０において、ネットワークアドミニストレータ２０は各ノード１６のＴＸＯＰ値を求めるのに不等式を特定する。一部の実施形態では、ネットワークアドミニストレータ２０は、（式（５）に示した）期待ノードスループットを対応するノード１６の負荷と等しいとして、ノード１６のＴＸＯＰを計算する。すなわち、
【数５】
2008228292.tif 000008
ここで、ｆ（ｅ）はステップ２０４において決定されたものである。シングルホップネットワークにおいては、（式（５）に示した）期待ノードスループットの式の分母はすべてのノードで同じである。分母が等しければ、ノード１６のＴＸＯＰ値は対応するノード１６の負荷Ｆ（ｖ）に単に比例する。
【００４９】
例えば、マルチホップネットワークを含む一部の実施形態では、不等式を最大化することによりＴＸＯＰの計算を簡単化できる。ある実施形態では、ネットワークアドミニストレータ２０は、各ノード１６に分配された帯域幅を公平に扱う。従って、他のスケーリングファクタｓ′を導入して、各ノード１６に分配される帯域幅が対応するノード１６の負荷Ｆ（ｖ）を越えないように（at  least  a  portion）する。次の不等式を解いて各ノード１６のＴＸＯＰパラメータを求める：
【数６】
2008228292.tif 000009
【００５０】
一部の実施形態では、ネットワークアドミニストレータ２０は帯域幅アルゴリズム６４を利用及び／またはロードすることにより、この不等式を特定する。ネットワークアドミニストレータ２０は、不等式を特定すると、各ノード１６のＴＸＯＰ値を求める。そして、方法２００は終了する。
【００５１】
ネットワークアドミニストレータ２０は、これらのステップを用いて、リンクへの帯域幅分配を計算し、ノード１６のパラメータを計算し、それによりノード１６の動作を制御してワイヤレスメッシュネットワーク１２における容量を増加させ輻輳を回避する。しかし、図５を参照して説明した方法は特定の実施形態の単なる例示であり、言うまでもなく動作のしかたやその動作を実行する装置は任意の適切なように修正してもよい。本方法では、具体的なステップを特定の順序で実行するものとして説明したが、言うまでもなく、ワイヤレスメッシュネットワーク１２は任意の適切なエレメントの集合及び配置が、任意の動作可能な順序で、これらのステップの一部または全部を実行しても、またはどのステップを実行しなくてもよい。説明したステップや使用した式は任意の適切な方法で修正して、ワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分してもよい。
【００５２】
本発明をいくつかの実施形態により説明したが、当業者は無数の変更や修正を考えられるであろう。添付した請求項に含まれる変更や修正は本発明に含まれる。
【００５３】
いくつかの実施形態は以下のように整理できる。
（付記１）  ワイヤレスメッシュネットワークにおける帯域幅分配方法であって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する段階と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較して重み付けする相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する段階と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する段階と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する段階と、
各パラメータをそれに対応するワイヤレスノードに送信する段階とを有する方法。
（付記２）  前記帯域幅割り当てを計算する段階は、前記トラフィックマトリックスと前記トポロジ情報とを線形計画問題に入力する段階を有し、
前記線形計画問題は、前記ワイヤレスノードにおけるフローの保存と、干渉範囲内にあるワイヤレスノードに関連するワイヤレスリンクのチャネル利用とを示す制約条件を含む、付記１に記載の方法。
（付記３）  各ワイヤレスノードについて、
負荷は前記ワイヤレスノードからのワイヤレスリンクの帯域幅割り当ての合計に等しく、
前記ワイヤレスノードに対応するパラメータは、前記ワイヤレスノードが使用する帯域幅の大きさを前記負荷に近づける、付記１に記載の方法。
（付記４）  前記ワイヤレスメッシュネットワークはＩＥＥＥ８０２．１１ワイヤレス通信プロトコルにより動作し、前記パラメータはＴＸＯＰ値である、付記１に記載の方法。
（付記５）  前記ワイヤレスメッシュネットワーク中のトラフィックを輻輳が少ないワイヤレスリンクに向けるルーティングテーブルを前記トラフィックマトリックスから計算する段階と、
前記ルーティングテーブルを前記ワイヤレスノードの少なくとも一部に送信する、付記１に記載の方法。
（付記６）  前記トラフィックマトリックスにおける前記相対的トラフィックデマンドは各ソースノード・デスティネーションノード・ペアのトラフィック量の時間的平均を表す、付記１に記載の方法。
（付記７）  前記トポロジ情報は、ノード数と、前記ノードの位置と、各ノードが通信できるエリアを示す各ノードの通信距離と、各ノードが他の通信と干渉するエリアを示す各ノードの干渉距離とを示す、付記１に記載の方法。
（付記８）  前記トポロジ情報は、各ワイヤレスノードについて、前記ワイヤレスノードによる送信と干渉する他のワイヤレスノードと、前記他のワイヤレスノードにより生じる干渉のレベルとを示す、付記１に記載の方法。
（付記９）  ワイヤレスメッシュネットワークにおいて帯域幅を分配するネットワークアドミニストレータであって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報と、各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスとを含むメモリと、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算し、各ワイヤレスノードが使用する帯域幅の大きさに影響する前記ワイヤレスノードのパラメータを前記帯域幅割り当てから計算するコントローラと、
各パラメータをそれに対応するワイヤレスノードに送信するネットワークインターフェイスとを有するネットワークアドミニストレータ。
（付記１０）  前記帯域幅割り当てを計算する段階は、前記トラフィックマトリックスと前記トポロジ情報とを線形計画問題に入力する段階を有し、
前記線形計画問題は、前記ワイヤレスノードにおけるフローの保存と、干渉範囲内にあるワイヤレスノードに関連するワイヤレスリンクのチャネル利用とを示す制約条件を含む、付記９に記載のネットワークアドミニストレータ。
（付記１１）  各ワイヤレスノードについて、
負荷は前記ワイヤレスノードからのワイヤレスリンクの帯域幅割り当ての合計に等しく、
前記ワイヤレスノードに対応するパラメータは、前記ワイヤレスノードが使用する帯域幅の大きさを前記負荷に近づける、付記９に記載のネットワークアドミニストレータ。
（付記１２）  前記ワイヤレスメッシュネットワークはＩＥＥＥ８０２．１１ワイヤレス通信プロトコルにより動作し、前記パラメータはＴＸＯＰ値である、付記９に記載のネットワークアドミニストレータ。
（付記１３）  前記コントローラは、さらに、前記ワイヤレスメッシュネットワーク中のトラフィックを輻輳が少ないワイヤレスリンクに向けるルーティングテーブルを前記トラフィックマトリックスから計算し、
前記ネットワークインターフェイスは、さらに、前記ルーティングテーブルを前記ワイヤレスノードの少なくとも一部に送信する、付記９に記載のネットワークアドミニストレータ。
（付記１４）  前記トラフィックマトリックスにおける前記相対的トラフィックデマンドは各ソースノード・デスティネーションノード・ペアのトラフィック量の時間的平均を表す、付記９に記載のネットワークアドミニストレータ。
（付記１５）  前記トポロジ情報は、ノード数と、前記ノードの位置と、各ノードが通信できるエリアを示す各ノードの通信距離と、各ノードが他の通信と干渉するエリアを示す各ノードの干渉距離とを示す、付記９に記載のネットワークアドミニストレータ。
（付記１６）  前記トポロジ情報は、各ワイヤレスノードについて、前記ワイヤレスノードによる送信と干渉する他のワイヤレスノードと、前記他のワイヤレスノードにより生じる干渉のレベルとを示す、付記９に記載のネットワークアドミニストレータ。
（付記１７）  ワイヤレスメッシュネットワークにおいて帯域幅を分配する論理であって、前記論理は媒体にエンコードされ、実行された時、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する段階と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する段階と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する段階と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する段階と、
各パラメータをそれに対応するワイヤレスノードに送信する段階とを実行させる論理。
（付記１８）  前記帯域幅割り当てを計算する段階は、前記トラフィックマトリックスと前記トポロジ情報とを線形計画問題に入力する段階を有し、
前記線形計画問題は、前記ワイヤレスノードにおけるフローの保存と、干渉範囲内にあるワイヤレスノードに関連するワイヤレスリンクのチャネル利用とを示す制約条件を含む、付記１７に記載の論理。
（付記１９）  各ワイヤレスノードについて、
負荷は前記ワイヤレスノードからのワイヤレスリンクの帯域幅割り当ての合計に等しく、
前記ワイヤレスノードに対応するパラメータは、前記ワイヤレスノードが使用する帯域幅の大きさを前記負荷に近づける、付記１７に記載の論理。
（付記２０）  前記ワイヤレスメッシュネットワークはＩＥＥＥ８０２．１１ワイヤレス通信プロトコルにより動作し、前記パラメータはＴＸＯＰ値である、付記１７に記載の論理。
（付記２１）  さらに、
前記ワイヤレスメッシュネットワーク中のトラフィックを輻輳が少ないワイヤレスリンクに向けるルーティングテーブルを前記トラフィックマトリックスから計算する段階と、
前記ルーティングテーブルを前記ワイヤレスノードの少なくとも一部に送信する段階とを実行させる、付記１７に記載の論理。
（付記２２）  前記トラフィックマトリックスにおける前記相対的トラフィックデマンドは各ソースノード・デスティネーションノード・ペアのトラフィック量の時間的平均を表す、付記１７に記載の論理。
（付記２３）  前記トポロジ情報は、ノード数と、前記ノードの位置と、各ノードが通信できるエリアを示す各ノードの通信距離と、各ノードが他の通信と干渉するエリアを示す各ノードの干渉距離とを示す、付記１７に記載の論理。
（付記２４）  前記トポロジ情報は、各ワイヤレスノードについて、前記ワイヤレスノードによる送信と干渉する他のワイヤレスノードと、前記他のワイヤレスノードにより生じる干渉のレベルとを示す、付記１７に記載の論理。
（付記２５）  ワイヤレスメッシュネットワークにおける帯域幅分配システムであって、
ワイヤレスメッシュネットワークを形成する複数のワイヤレスノードと前記ワイヤレスノードを相互接続する複数のワイヤレスリンクの構成を示すトポロジ情報を特定する手段と、
各ノードから他の各ノードへのソースノード・デスティネーションノード・ペアに対して、そのソースノード・デスティネーションノード・ペアを他の各ソースノード・デスティネーションノード・ペアと比較した相対的トラフィックデマンドを示す、前記ワイヤレスメッシュネットワークのトラフィックマトリックスを決定する手段と、
前記トポロジ情報と前記トラフィックマトリックスとを用いて各ワイヤレスリンクの帯域幅割り当てを計算する手段と、
前記ワイヤレスノードが使用する帯域幅の大きさに影響する、各ワイヤレスノードのパラメータを前記帯域幅割り当てから計算する手段と、
各パラメータをそれに対応するワイヤレスノードに送信する手段とを有するシステム。
【図面の簡単な説明】
【００５４】
【図１】ワイヤレスメッシュネットワークにおいて帯域幅をインテリジェントに配分するシステムを示す概略図である。
【図２】ワイヤレスメッシュネットワークにおいて帯域幅の配分を決定するネットワークアドミニストレータを示すブロック図である。
【図３】Ａは、ワイヤレスメッシュネットワークの一例のトポロジを示す図である。Ｂは、ネットワークノード間の帯域幅を配分するために選択されたパラメータを示す図である。Ｃは、帯域幅配分のシミュレーション結果を示すグラフである。
【図４】ワイヤレスメッシュネットワークにおいてネットワークアドミニストレータが帯域幅を配分する方法を示すフローチャートである。
【図５】リンク帯域幅割り当ての計算とノードのパラメータの計算の方法の一実施形態を示すフローチャートである。
【符号の説明】
【００５５】
１０  システム
１２  ワイヤレスメッシュネットワーク
１４  ネットワーク
１６  ノード
１８  無線装置
２０  ネットワークアドミニストレータ
５２  ネットワークインターフェイス
５４  コントローラ
５６  メモリ
５８  オペレーティングロジック
６０  ネットワークトポロジ
６２  トラフィックマトリックス
６４  帯域幅アルゴリズム
６６  帯域幅データ
【図１】
2008228292.tif 000010
【図２】
2008228292.tif 000011
【図３】
2008228292.tif 000012
【図４】
2008228292.tif 000013
【図５】
2008228292.tif 000014