無線ローカル・エリア・ネットワークにおいてアクセス・ポイントにかかる負荷を平衡化するための方法及びデバイス
【課題】 本発明は、ＷＬＡＮ内で負荷の不平衡を最小限に抑えるのに使用されることが可能である、より効果的なセル・ブリージング方法及び関連するデバイスを提供することを目的とする。
【解決手段】 無線ローカル・エリア・ネットワークＷＬＡＮにおけるアクセス・ポイントＡＰにかかる負荷が、いくつかの方法、及び関連するデバイスを使用して、最小限に抑えられる。１つの方法は、ほとんどの輻輳したＡＰの負荷を最小限に抑えるのに対して、第２の方法は、最適ミニマックス（優先度）負荷平衡化解を使用して、輻輳したＡＰと輻輳していないＡＰの両方にかかる負荷を平衡化する。最適解は、とりわけ、複雑な変更を要求することなしに得られる。両方の方法は、輻輳を低減するが、ＡＰデータ・トラフィック・チャネルの伝送電力レベルの調整を要求しない、ＡＰビーコン・メッセージの伝送電力レベルの調整を含む。
【解決手段】 無線ローカル・エリア・ネットワークＷＬＡＮにおけるアクセス・ポイントＡＰにかかる負荷が、いくつかの方法、及び関連するデバイスを使用して、最小限に抑えられる。１つの方法は、ほとんどの輻輳したＡＰの負荷を最小限に抑えるのに対して、第２の方法は、最適ミニマックス（優先度）負荷平衡化解を使用して、輻輳したＡＰと輻輳していないＡＰの両方にかかる負荷を平衡化する。最適解は、とりわけ、複雑な変更を要求することなしに得られる。両方の方法は、輻輳を低減するが、ＡＰデータ・トラフィック・チャネルの伝送電力レベルの調整を要求しない、ＡＰビーコン・メッセージの伝送電力レベルの調整を含む。
【発明の詳細な説明】
【背景技術】
【０００１】
無線ローカル・エリア・ネットワークＷＬＡＮにおいて、無線デバイスは、すべての利用可能なチャネルをスキャンして、近くのアクセス・ポイントＡＰを検出し、次に、最も強い受信信号強度指標ＲＳＳＩを有するＡＰに、そのようなＡＰ又は近くの他のＡＰにかかる負荷を考慮に入れることなしに、無線デバイスを関連付ける。
【０００２】
実用可能なＩＥＥＥ８０２．１１ ＷＬＡＮに関する最近の研究は、トラフィック負荷が、しばしば、ＷＬＡＮ内のＡＰの間で不均一に配分されていることを示している。通常、任意の所与の時点で、一部のＡＰには、重い負荷がかかる傾向があるのに対して（いわゆる「輻輳した」ＡＰ）、他のＡＰは、そうではない。この状況は、ＷＬＡＮ内で負荷の不平衡を生じさせる。負荷の不平衡は、ネットワークが、ネットワークの容量を完全に利用することを阻み、ネットワークがサービスを公平で均等な仕方で提供することを妨げるため、望ましくない。
【０００３】
現在、ＩＥＥＥ８０２．１１ ＷＬＡＮ規格は、負荷の不平衡を解決する決まった方法を提供しない。この欠点を克服するのに、様々な負荷平衡化スキームが、学界と業界の両方によって提案されている。これらの方法のほとんどは、ユーザによって操作されるデバイス（例えば、コンピュータ）において独自のクライアント・ソフトウェア、又は特別に設計されたＷＬＡＮカードを展開することによって、ユーザ−ＡＰ関連付けを直接にコントロールするというアプローチをとる。これらのアプローチでは、ＡＰは、変更されたビーコン・メッセージを介して、ＡＰの負荷レベルをユーザ・デバイス（時として、単に「ユーザ」と呼ばれる）にブロードキャストし、各ユーザは、かかっている負荷が最も小さいＡＰを選択する。
【０００４】
そのようなユーザ選択アプローチは、負荷平衡化を実現することができるものの、すべての（又はほとんどの）ユーザ・デバイスへの独自のクライアント・ソフトウェア／ハードウェアの展開は、実現するのが困難である。例えば、今日、ユーザは、ホテル、空港、ショッピングセンタ、及び大学キャンパスなどの様々なＷＬＡＮにアクセスする。これらの異なるネットワークは、異なる負荷平衡化機構をおそらく採用している異なる組織によって管理される。ユーザが、異なる各ネットワークに関して１つずつ、複数の異なるクライアント・モジュールを有すると見込むのは、非現実的である。
【０００５】
したがって、独自のクライアント・モジュールなどの使用を要求しない新たな負荷平衡化スキームを提供することが望ましい。
【０００６】
また、他のタイプのネットワークも、負荷平衡化の課題に直面する。例えば、ＣＤＭＡセルラーネットワークにおいて、セル内でアクティブなユーザの数が増えることにより、そのセルの基地局において感知される合計の干渉の増加が生じる。これにより、そのセルが輻輳することになる。セルが輻輳すると、そのセル内でユーザによって操作されるデバイスは、デバイスが基地局に送信する信号が、許容できる信号対雑音比で受信されることを確実にするために、より高い電力レベルで送信して、干渉の影響を克服する必要がある。セル内の電力レベルが高まるにつれ、生成された信号は、近隣のセルに対してより強い干渉を生じさせる。その結果、そのようなセルを含むネットワークの全体的な容量が、低下し始める。干渉のこれらの不要な増加を克服するのに、いわゆる「セル・ブリージング」技術が開発された。しかし、一般的に言えば、ＣＤＭＡネットワークのために開発された既存のセル・ブリージング技術は、ＷＬＡＮにおいてうまく機能しない。
【０００７】
ＷＬＡＮは、ＣＤＭＡネットワークの場合と同様の負荷平衡化の課題に直面するため、本発明者らは、既存のセル・ブリージング技術の欠点をまず認識することによって、これらの課題をどのように解決すべきかを研究することを開始した。例えば、図１（ａ）を参照すると、同一の最大電力レベルで伝送しているものと想定される３つのＡＰ、すなわち、ａ、ｂ、及びｃを有するＷＬＡＮ１が、示されている。簡明のため、数名のユーザを各ＡＰに割り当てる。図１（ａ）では、１名のユーザがＡＰａに、８名のユーザがＡＰｂに、１名のユーザがＡＰｃに最初に割り当てられる。この例において、ＡＰの負荷は、割り当てられた、又は関連付けられたユーザの数であるものと定義する。このシナリオを所与として、ＡＰｂは、ＡＰａ及びＡＰｃよりもはるかに高い負荷を有する。既存のセル・ブリージング技術によれば、ＡＰｂにかかる負荷を減らすのに、ＡＰｂの伝送電力が、低減されなければならない。このことは、ｂの伝送範囲／セル・サイズの縮小につながる。図１（ａ）では、範囲は、例えば、境界１０１から境界１０２に縮小する。図１（ａ）に示されるとおり、ＡＰｂから最も遠く離れて位置している４つのユーザ／デバイス１〜４が、セル・サイズのこの縮小の影響を受ける。セルの元のサイズにおいて、ユーザ１〜４は、セルの範囲内にあり、したがって、ＡＰｂ伝送の範囲内にある。セルが、サイズ１０１からサイズ１０２に縮小するにつれ、ユーザ１〜４は、ＡＰｂの範囲の丁度端ぎりぎりに（もちろん、時として、この範囲の外に）自らが位置していることに気付く。ＡＰｂから、より遠く離れていることは、通常、ユーザ１〜４によって使用されるデバイスにおける信号品質の低下をもたらす。より低い信号品質の検出に応答して、ユーザ１〜４によって使用されるデバイスは、より高い信号品質に関連するＡＰを選択するスキャン動作を開始する。例えば、図１（ａ）におけるユーザ１〜２の２名が、ＡＰａから、より高い信号品質を検出することが可能である一方で、ユーザ３〜４は、ＡＰｃから、より高い信号品質を検出する。より高い信号品質が検出されると、既存のセル・ブリージング技術によれば、これらのユーザは、ＡＰａ及びＡＰｃにそれぞれ移される。図１（ｂ）に示されるとおり、正味の効果は、ＷＬＡＮ１内で負荷／ユーザを、より均等に配分することである（すなわち、現時点で、３名のユーザがＡＰａに割り当てられ、４名のユーザがＡＰｂに割り当てられ、３名のユーザがＡＰｃに割り当てられているため）。
【０００８】
しかし、ＡＰｂの伝送電力の低減は、ＡＰｂと、ユーザ１〜４だけではなく、ＡＰｂのセル内のユーザのすべてとの間のチャネル／リンクの信号品質に影響を及ぼす。このため、別のＡＰに移されない（すなわち、ＡＰｂに関連付けられたままである）ユーザ／デバイス５〜８もまた、より低い信号品質を検出する。これに応答して、ユーザ５〜８によって使用されるデバイスは、より低いビットレートで通信しなければならない可能性がある。より低いビットレートにおいて、情報（時として、「トラフィック」と呼ばれる）が、ユーザ５〜８からＡＰｂに伝送されるのに、より長い時間がかかる可能性がある。このことは、各ユーザ５〜８が寄与する、ＡＰｂにかかる負荷を事実上、増大させる（ＡＰ負荷が、ユーザの数だけでなく、実効的なユーザ・スループットも考慮することによって算出される場合）。このため、ＡＰにかかる負荷を減らすどころか、既存のセル・ブリージング技術は、負荷を実際には増大させる可能性がある。
【０００９】
したがって、無線ネットワーク内で負荷の不平衡を回避する、又は最小限に抑える方法及びデバイスを提供することが望ましい。特に、ＷＬＡＮ内で負荷の不平衡を最小限に抑えるのに使用されることが可能である、より効果的なセル・ブリージング方法（及び関連するデバイス）を提供することが望ましい。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許仮出願第６０／７９３３０５号
【発明の概要】
【課題を解決するための手段】
【００１１】
本発明者らは、ＷＬＡＮなどの無線ネットワーク内で負荷の不平衡を最小限に抑えるが、前述した不平衡を回避する方法及びデバイスを見出した。本発明によれば、データ／トラフィックを伝送するのに使用される伝送電力レベルが、ビーコン・メッセージを伝送するのに使用される伝送電力レベルと分離され、ビーコン・メッセージを伝送するのに使用される伝送電力レベルだけが、低減される。
【００１２】
データを伝送するのにＡＰによって使用される電力レベルを維持することによって、そのＡＰの範囲内のデバイスの伝送ビットレートが、維持される。しかし、ＡＰ範囲内の各ユーザ／デバイス、又はＡＰに接近しているＡＰは、それらのユーザ／デバイスが、現在、割り当てられている（又は割り当てられることを求めている）ＡＰからの別個のビーコン・メッセージの信号品質を検出して、評価することによって、既存のＡＰに割り当てられたままにする（又は割り当てられる）、又は別のＡＰに切り替えるか否かを決定するため、ビーコン・メッセージを伝送するのに使用される電力レベルを低減することによって、本発明は、事実上、ＡＰのセルを縮小する。その結果、このことは、新たなユーザが、ＡＰに割り当てられないようにさせる。ＡＰが既に輻輳している事例において、このことは、ＡＰが、さらに輻輳することを防止する。
【００１３】
ＡＰにかかるトラフィック負荷を低減することは、負荷の不平衡を回避する問題解決法の一部である。その他の部分は、１つのＡＰから、過負荷になっていない近隣のＡＰにトラフィックを向ける、又は向け直す（一まとめにして、「向ける」）ことである。
【００１４】
１つのＡＰにかかるトラフィック負荷を減らすことを、他方で適切な近隣のＡＰにかかる負荷を増やすことと組み合わせることにより、ＷＬＡＮ内のトラフィック負荷が平衡化される。
【００１５】
局所最適化ヒューリスティックに主に依拠する、ＷＬＡＮ内でトラフィック負荷を平衡化する従前の試みとは異なり、本発明は、最適なセル・サイズ設定方法（及び関連するデバイス）を使用して、決定論的なミニマックス負荷平衡化解を見出す。
【００１６】
また、本発明によって提供される方法及びデバイスは、ＷＬＡＮ負荷平衡化のためのほとんどの既存の提案とは異なり、ユーザ支援、又は既存の８０２．１１標準の変更を要求しないため、特に魅力的でもある。
【００１７】
代わりに、本発明によって提供される方法は、既存のデバイスを制御するソフトウェアを変更することによって実施されることが可能である。より詳細には、例えば、ネットワーク・オペレーションズ・センタＮＯＣに配置されたネットワーク・コントローラ又はネットワーク管理ユニットによって使用されるソフトウェアを変更することによって実施されることが可能である。
【００１８】
本発明の一実施形態では、そのようなコントローラは、ＡＰのデータ・トラフィック・チャネルの伝送電力を変更することなしに、ＡＰのビーコン・メッセージの伝送電力を変更することによって、ＡＰのセル・サイズを小さくするように動作可能である。その後、コントローラは、このセルの境界近くのユーザ／デバイスを、それほど輻輳していないＡＰに向ける。今日、利用可能なＡＰは、複数の伝送電力レベルを既にサポートしており、したがって、本発明者らは、本発明が、例えば、ソフトウェア更新を既存のＡＰに配信すること／ダウンロードすることによって容易に実施されることが可能であるものと考える。
【００１９】
さらに、本発明によって提供される新規のセル・ブリージング方法は、特定の負荷定義に結び付けられておらず、広い範囲の負荷定義をサポートする。負荷寄与は、ＡＰに関連付けられたユーザの数といった単純なものであることが可能であり、あるいはより複雑であって、有効伝送ビットレート、平均トラフィック要求、又は乗法ユーザ負荷寄与のような要因を考慮に入れることが可能である。
【００２０】
本発明のさらなる実施形態において、ネットワーク・オペレーション・センタＮＯＣなどにおいて動作する、本発明によって提供される方法及びコントローラは、ＡＰから（例えば、Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ、「ＳＮＭＰ」メッセージを介して）負荷情報及び関連付け情報を収集する。利用可能な情報の範囲に応じて、次に、２つのモデル又は方法（この２つの語は、本明細書で互いに区別なく使用されることが可能である）の１つが、負荷平衡化を実行するのに使用されることが可能である。第１のモデルは、可能なユーザ−ＡＰ関連付け、及び対応するＡＰ負荷が、可能なすべてのビーコン電力割り当てに関してアプリオリに知られているＣＫ（完全知識）モデルである。そのような情報は、容易に入手可能でない可能性があるので、本発明は、現在のビーコン電力割り当てだけに関するユーザ−ＡＰ関連付け及びＡＰ負荷が入手可能である、ＬＫ（限定された知識）モデルも提供する。ＣＫモデルは、より実際的なＬＫモデルのための構成要素の役割をする。
【００２１】
本発明によって提供されるモデルのそれぞれは、一般に、２つのステップを含む。第１のステップは、負荷が、輻輳負荷と呼ばれる、最も輻輳したＡＰにかかる負荷を最小限に抑えることである。本発明は、各モデルに関して１つずつ、最適解を見出す２つの多項式時間アルゴリズム／方法（以降、「（１つ又は複数の）方法」と呼ばれる）を提供する。このことは、負荷平衡化問題が、強ＮＰ困難である（すなわち、限定された時間内に解くことが非常に困難である）ことが知られているため、重要な成果である。さらに、本発明者らが、ＬＫモデルにおいて使用されることが可能な多項式時間最適方法を見出したことは、特に重要である。本発明によれば、負荷平衡化問題を解くのに提供される解は、現在のＡＰ電力レベル設定が、最適な電力レベル設定より「優勢である」（すなわち、各ＡＰが、最適解における電力レベル以上の電力レベルを有する）限り、最適解は、それでも、一連の電力低減動作を実行することによって得られることが可能であるという、本発明者らによって見出された洞察に基づく。本発明によって提供される１つの例示的な方法において、最大電力レベルから始めて、選択されたＡＰセットの電力レベルが、繰り返し低減される。ＣＫモデルでは、ボトルネック・セットの概念を使用して、最適解への収束が確実にされる。ボトルネック・セットの中のすべてのＡＰの電力レベルを低減した後、各ＡＰの負荷が、電力レベル低減より前の初期の輻輳負荷と同一のままである、又は厳密により低いことが保証される。ＬＫモデルの場合、電力がそれ以上、低減されることが可能でなくなるまで、輻輳したＡＰの電力レベルが、徐々に低減され、その間中、電力の各回の低減の後に見出される最良の解が記録される、最適状態記録と呼ばれる異なるアプローチが、使用される。
【００２２】
第２のステップは、いわゆるミニマックス負荷平衡化解を見出すという問題を解くことを含む。本明細書において明瞭／簡単にするために証明は、省略されているものの、本発明者らは、この問題も、解決されるべき強ＮＰ困難問題であること、及び解を近似する許容できる方法は、全く存在しないことを発見／証明した。より具体的には、本発明者らは、座標に関する近似比を保証する方法は、全く存在しないことを証明しており、任意のプレフィックス合計近似アルゴリズムの近似比は、少なくともＰ（ｌｏｇ ｎ）であり、ただし、ｎは、ネットワークにおけるＡＰの数である。思いとどまることなく、本発明者らは、最適解が、両方のモデルに関して多項式時間内に計算されることが可能な、優先度負荷平衡化と呼ばれるミニマックス問題の変種を発見した。優先度負荷平衡化において、ＡＰ負荷は、ＡＰの関連付けられたユーザの集計された負荷寄与と、固有ＡＰ優先度との順序付けられたペアとして定義される。最適状態記録を使用して、ミニマックス優先度負荷平衡化解の各座標を繰り返し計算する方法が、構築された。
【図面の簡単な説明】
【００２３】
【図１ａ】本発明の特徴を示すのに使用されるＷＬＡＮの例を示す図である。
【図１ｂ】本発明の特徴を示すのに使用されるＷＬＡＮの例を示す図である。
【図２ａ】本発明の特徴を示すのに使用されるＷＬＡＮのさらなる例を示す図である。
【図２ｂ】本発明の特徴を示すのに使用されるＷＬＡＮのさらなる例を示す図である。
【図３】本発明による「ボトルネック・セット」を計算するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図４】本発明の完全知識方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図５ａ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｂ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｃ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｄ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図６】本発明の限定された知識方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図７ａ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｂ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｃ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｄ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図８】本発明のミニマックス優先度負荷平衡化方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図９ａ】本発明のミニマックス優先度負荷平衡化方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図９ｂ】本発明のミニマックス優先度負荷平衡化方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図１０】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１１】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１２】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１３】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１４】この説明全体で使用される記号のいくつか、及びそれらの記号の例示的な意味のリストである。
【図１５】本発明によって提供される限定された知識方法を実行するコントローラなどに関する例示的なランタイム統計を示す表である。
【発明を実施するための形態】
【００２４】
図１（ａ）を再び参照すると、ａ〜ｃで表されるＡＰのセットを有するＷＬＡＮ１０００が示されている。示されていないものの、ＡＰａ〜ＡＰｃのすべてが、有線インフラストラクチャ、例えば、インターネットに直接に接続されることが可能であるものと理解されたい。各ＡＰａ〜ＡＰｃは、或る伝送範囲を有し、そのＡＰの範囲内のユーザ１〜８だけにサービスを提供することが可能である。さらに、各ＡＰａ〜ＡＰｃは、複数の伝送電力レベルの１つを使用するように構成されることが可能である。簡単にするため、ＡＰａ〜ＡＰｃは、すべてのＡＰが、最小電力レベルで伝送している場合でさえ、すべてのユーザ１〜８が、少なくとも１つのＡＰによって範囲に入れられるように、ＡＰａ〜ＡＰｃの範囲間で高い度合いの重なり合いを確実にするように配備されるものと想定されることが可能である。
【００２５】
さらに、ユーザ１〜８は、準静的移動パターンを有するものと想定されることが可能である。つまり、ユーザは、自由に動くことができるが、同一の相対的位置に長時間にわたって留まる傾向にある。任意の所与の時点で、各ユーザ１〜８は、単一のＡＰａ〜ＡＰｃに関連付けられる。各ＡＰａ〜ＡＰｃは、ビーコン・メッセージを周期的に伝送して、そのＡＰａ〜ＡＰｃのプレゼンスを「公示する」。ユーザが、ＷＬＡＮ１０００に入ると、ユーザの関連付けられたデバイスは、ビーコン・メッセージを検出するために、ＷＬＡＮ１０００内のすべてのチャネルを走査する。ビーコン・メッセージを検出した後、ユーザのデバイスは、検出された各メッセージのＲＳＳＩを測定するようにさらに動作可能である。通常、デバイスは、次に、デバイスと、測定された最も強いＲＳＳＩに関連するＡＰとの間でリンクを作成するプロセスを開始する。その後、ユーザが確立したリンクの信号品質が、或る閾値を下回って低下し始めると必ず、ユーザに関連するデバイスは、ビーコン・メッセージのすべてを走査するプロセスを再び開始して、より強い信号が存在するかどうかを判定する。存在する場合、ユーザ／デバイスは、そのより強い信号に関連するＡＰと新たなリンクを確立しようと試みる。
【００２６】
前述した方法は、新たなユーザが、輻輳したＡＰに関連付けられないようにすることによって、ＷＬＡＮ内のＡＰにかかる負荷を平衡化する。しかし、このことは、輻輳したＡＰに即時の軽減をもたらさない可能性がある。即時の軽減（すなわち、負荷低減）のため、輻輳したＡＰに既に関連付けられているユーザ／デバイスが、その輻輳したＡＰを離れるように再割り当てされる必要がある。そのようにするのに、必要とされているのは、そのようなユーザ／デバイスが、別のＡＰからのビーコン・メッセージを検出するために走査動作を呼び出すよう、いわば、促す仕方である。これが行われることが可能な、いくつかの仕方が存在する。１つの仕方は、ＡＰのセル範囲が変更された後に、関連付け移転をトリガすることである。以降、説明を、ビーコン・メッセージの電力レベルだけに限定する。つまり、以降、「伝送電力」又は「電力レベル」又は「状態」という用語が使用される場合、これらの用語は、特に明記しない限り、又は文脈がそうでないことを示さない限り、ビーコン・メッセージを伝送するのに使用される電力だけと関係する。
【００２７】
前述したとおり、負荷の不平衡を最小限に抑える際の第１のステップは、ＷＬＡＮ内のＡＰにかかる負荷を最小限に抑えることである。本発明の一実施形態では、ＣＫモデルを使用して、負荷が最小限に抑えられる。代替の実施形態では、ＬＫモデルが使用される。
【００２８】
ネットワークは、ネットワーク（例えば、ＮＯＣ内のコントローラ）が、ＷＬＡＮ内のすべてのユーザ−ＡＰペアに関連する可能な信号減衰及び負荷寄与を検出する、又は収集することができる場合、「完全知識」を有するという言い方がされることが可能である。完全知識状態は、ユーザのすべてが、近くのすべてのＡＰからＲＳＳＩ情報を収集し、この情報を、ＮＯＣに配置されたコントローラに送信する場合、実現可能である。残念ながら、この能力は、既存のほとんどのＷＬＡＮにおいて、現在、利用可能ではない。それでも、ＣＫモデルは、現在の負荷割り当て及びユーザ割り当てを使用するＬＫモデルのための構成要素として有用である。
【００２９】
ネットワークは、ネットワーク（例えば、ＮＯＣに配置されたコントローラ）が、各ＡＰに、現在、割り当てられているユーザのセット、及びそのようなセットが割り当てられたＡＰにかかるそのような各ユーザの負荷寄与に関する情報だけしか検出する、又は収集することができない場合、限定された知識を有するという言い方がされることが可能である。
【００３０】
本発明の実施形態によれば、ＣＫモデルにおいて、コントローラが、ＷＬＡＮの状態を実際に変更することなしに、可能なすべての状態におけるユーザ−ＡＰ割り当て／関連付けをアプリオリに決定することができることが可能である。このことは、ＮＯＣが、所望される状態に関するオフライン計算を実行することを可能にする。そのようなオフライン計算は、ＬＫモデルにおいて実行可能ではない。
【００３１】
最適平衡化状態への、いずれのモデルの収束と関係する問題（すなわち、輻輳したＡＰにかかる負荷は、低下するが、別のＡＰにかかる負荷は、増加する）を克服するのにも、本発明は、以下の２つのさらなるアプローチの使用を提供する。ＣＫモデルに関して、本発明は、いわゆるボトルネック・セット電力低減をまず計算する。このアプローチは、最適状態に単調に収束する一連のセット電力低減を実行することを含む。このことにより、輻輳負荷が増加しないことが確実にされる。ＬＫモデルに関して、本発明は、最適状態記録をまず使用する。このアプローチでは、それまでに見つかった最良状態のレコードが、保持される。
【００３２】
本発明によれば、ボトルネック・セットは、すべての輻輳したＡＰ（負荷Ｙを有する）、ならびに、セット電力低減を実行したことの結果、負荷がＹ以上に上昇する可能性があるすべてのＡＰを含むＡＰの最小セットと定義されることが可能である。本発明者らは、ボトルネック・セットに関する形式的表現を作成した。しかし、この表現は、本発明の理解に必要とされず、本明細書では省略されている。代わりに、ボトルネック・セットの一例を次に提示する。
【００３３】
図２（ａ）に示されるＷＬＡＮ２０００を考慮されたい。ＡＰａ、ＡＰｂが、同一の電力レベルを有する場合、ＡＰａの電力レベルの低減は、ＡＰａの負荷を３から１まで低減する一方で、ＡＰｂにかかる負荷を２までしか増加させない。このため、この時点におけるボトルネック・セットは、ＡＰａだけを含むと言うことができる。しかし、図２（ｂ）に示されるとおり、ａが、ｂより低い電力レベルを有する場合、ｂの電力レベルを低減することは、ｂの負荷を２から０まで低減し、ａの負荷を３まで増加させる。この事例では、ボトルネック・セットは、ＡＰａとＡＰｂをともに含む。完全のため、ボトルネック・セットを計算するのに使用されることが可能な、本発明によって提供されるソフトウェア・プログラム／ルーチンの例が、図３に示される。
【００３４】
コントローラが、ＷＬＡＮの完全知識を有する事例において、ＷＬＡＮのボトルネック・セットは、容易に計算されることが可能である。最初に、各ＡＰａと各ユーザの間のＲＳＳＩが、計算される。この情報は、コントローラが、初期のユーザ−ＡＰ割り当て／関連付け、各ＡＰａにかかる負荷、及び最大負荷Ｙを決定することを可能にする。これらから、コントローラは、本発明者らによって作成された式を使用してボトルネック・セットを計算することができる。この場合も、そのような式の詳細は、本発明の理解に必要ではないが、前述したとおり、ボトルネック・セットを計算するルーチンの一例が、図３に示される。本発明者らによって導き出される証明のすべての正味の結果は、以下の発見であるとだけ言っておこう。すなわち、所与のＷＬＡＮに関するボトルネック・セットは、他のいずれのＡＰにかかる負荷も、最大負荷Ｙ以上に増加させない電力低減を使用して得られた輻輳したＡＰのセットを含むＡＰの最小セットである。ＡＰのボトルネック・セットを計算すると、本発明によって提供されるコントローラは、コントローラが、ＷＬＡＮの完全知識を有する場合、次に、このセットを使用して、ＷＬＡＮ内のＡＰ上の輻輳を最小限に抑える。
【００３５】
本発明の一実施形態によれば、ＣＫ方法は、すべてのＡＰが、最大電力状態にあり、ＡＰの最大伝送電力で伝送するものと初期に想定することによって、輻輳を最小限に抑える。その後、本発明によるコントローラによって実行されるＣＫ方法は、ボトルネック・セットを繰り返し計算する。計算されたセットを使用して、次に、方法は、別の電力低減動作が、適用される必要があるか、又は最適状態が見つかったかを判定する。この目的で、ＣＫ方法は、２つの終了条件（すなわち、電力低減の終了をトリガする条件）を利用する。第１の条件は、ボトルネック・セットが、ＡＰの完全なセットと等しいかどうかを判定する。この条件は、ＷＬＡＮ内のすべてのＡＰにかかる負荷が平衡化されており、したがって、さらなる電力低減が、ＡＰのいくつかにおける輻輳を、より軽くではなく、よりひどくする場合に、満たされることが可能である。第２の条件は、ボトルネック・セットが、最小電力レベルを使用して伝送しているＡＰを含むかどうかを判定する。含む場合、ボトルネック・セットの中のＡＰのすべてのＡＰの電力レベルは、等しく低減されることが可能でなく、方法は、終了される。そのような事例は、ＣＫ方法が、ＷＬＡＮ内のＡＰにかかる負荷が、平衡化されていないと判定し、輻輳したＡＰの電力レベルを繰り返し低減することによって最大負荷を減らすよう試みることを続ける場合に、通常、生じる。本発明によるＣＫ方法を実行するためのソフトウェア・プログラム又はルーチンの例が、図４に示される。
【００３６】
図５（ａ）は、ＷＬＡＮ３０００内のＡＰａ上、ＡＰｂ上、及びＡＰｃ上の輻輳が、本発明の例示的なＣＫ方法を使用して最小限に抑えられているＷＬＡＮ３０００の例を示す。図示されるとおり、ＡＰａ、ＡＰｂ、及びＡＰｃに加えて、ＷＬＡＮ３０００は、例示的なユーザｕ１、ｕ２、ｕ３、ｕ４、及びコントローラ３００１を含む。本発明の実施形態によれば、ＡＰａ、ＡＰｂ、及びＡＰｃは、ＡＰａ、ＡＰｂ、及びＡＰｃの関連するユーザ、負荷、及びさらなる関係のある情報をコントローラ３００１に提供するように動作可能である。この情報を受け取り、解析すると、コントローラ３００１は、現在、説明されているＣＫ方法を含め、本発明によって提供される方法を実行するように動作可能である。
【００３７】
続けると、ＡＰａ、ＡＰｂ、及びＡＰｃのそれぞれは、異なる３つの電力レベル０、１、及び２で動作することが可能である。図５（ａ）において、ユーザ−ＡＰ割り当て／関連付けが、実線又は破線として示され、ただし、実線は、ＡＰのそれぞれが、いつ同一の電力レベルで伝送するかを示し（デフォルトの関連付け）、破線は、可能な他の関連付けを示す。各線上の数字は、関連するＡＰにかかる負荷へのユーザによる寄与を示す。例えば、ｕ１は、ａだけに関連付けられることが可能であり、４という負荷をもたらす。ｕ３は、ＡＰのそれぞれに関連付けられることが可能であり、２という負荷をもたらす。ｕ３は、好ましくは、最高の電力レベルを有するＡＰを選択するが、互角の場合には、ｃを選好する。ｃが、ａ及びｂより低い電力レベルで伝送している場合、ｕ３は、ｂを選好する。アスタリスクは、２つの電力レベルの格差が、ユーザを移すのに要求されることを示し、例えば、ｕ２は、ＡＰａの電力レベルが、０であり、ＡＰｂの電力レベルが２である場合にだけ、関連付けをａからｂに変更することができる。
【００３８】
図５（ｂ）に示される初期状態において、ＡＰのすべては、２という同一の電力レベル／インデックスを有し、各ＡＰａ、ＡＰｂ、及びＡＰｃにかかる負荷は、それぞれ、７、０、及び１２である。本発明によって提供されるＣＫ方法の第１回目において、ボトルネック・セット（「Ｂ」）が、計算され、ＡＰｃが、このセットの中に含まれているものとして識別される。加えて、ｃの電力レベルが、１に低減される。その結果、ｕ３は、ｕ３の関連付けをＡＰｂに変更する。この新たなユーザ−ＡＰ関連付け及び負荷が、図５（ｃ）に示される。ｂは、依然として、輻輳したＡＰであることに留意されたい。しかし、ビーコン・メッセージを伝送するのにＡＰｃによって使用される電力レベルのさらなる低減は、ユーザｕ４が、ｕ４の関連付けをＡＰｂに変更するようにさせて、ＡＰｂにかかる負荷が、１７になるようにする。このため、図５（ｄ）に示される第２回目において、ボトルネック・セットは、ｃとｂをともに含む。ｐｃ＝０であるので、これが、最終回である。図５（ｄ）に示される最終状態は、輻輳を最小限に抑えるが、輻輳していないＡＰにかかる負荷を平衡化しない。そうすることは、後段で説明される本発明の第２のステップに任せられる。
【００３９】
さらなる発見において、本発明者らは、本発明によって提供されるＣＫ方法が、ＷＬＡＮの輻輳負荷を最小限に抑える最適状態を常に見出すことを発見した。本発明者らは、この発見を支える証明を作成した。しかし、これらの証明は、本発明の理解に必要ではなく、簡明のために省略されている。例えば、これらの証明は、ＣＫ方法が輻輳を最小限に抑えるのに、どのように使用されることが可能であるかについての理解に必要ではない。
【００４０】
次に、ＷＬＡＮの完全知識を獲得することが実現可能ではない場合に、輻輳を最小限に抑えるのに使用されることが可能な本発明の代替の実施形態に注目する。この第２の実施形態は、ＬＫ方法である。ＣＫ方法とは異なり、ＡＰのボトルネック・セットは、あらかじめ計算されることが可能でない。
【００４１】
しかし、この障害は、ネットワーク（例えば、ＷＬＡＮ）の状態が、最適未満であり（例えば、ＷＬＡＮにおけるＡＰにかかる負荷が、不平衡であり）、この状態が、最適解より優勢である限り、輻輳したＡＰのセットに関連するビーコン信号の電力レベルの、一連の同時の低減により、最適状態への（すなわち、ＷＬＡＮ内の負荷を平衡化する最適電力レベルへの）収束がもたらされることを、本発明者らが発見した際、本発明者らによって克服された。この発見は、それ自体のジレンマ、すなわち、そのような最適解に関連する終了条件（すなわち、低減をいつ停止するか）を識別するという課題を生じさせた。終了条件なしには、一連の低減は、最適未満の解を生じることになる可能性がある。そのような条件を決定するのに、本発明によって提供されるＬＫ方法は、最低の輻輳負荷に対応するすべてのＡＰの伝送電力レベルを記録する／格納する最適状態記録アプローチを使用する。より詳細には、最適状態記録アプローチは、２つの変数を定義する。第１の変数は、記録された状態（例えば、レベル）を保持し、第２の変数は、この記録された状態に関連する、記録された輻輳負荷と呼ばれる輻輳負荷値を保持する。
【００４２】
本発明の一実施形態によれば、ＬＫ方法は、以下のステップを含む。最初、方法は、すべてのＡＰが、記録された状態（例えば、電力レベル）、及び記録された輻輳負荷が、何らかの値に初期設定された最大電力状態（例えば、最大電力レベル）で動作しているところから始まる。次に、輻輳したＡＰのセットＤが、繰り返し計算され、このセットＤが、最小電力レベルにおけるＡＰ含まない限り、方法は、セットＤの中のＡＰの電力レベルを繰り返し低減する。各回の低減の後、新たな状態の現在の輻輳負荷が、測定され、現在の測定された負荷が、前の格納／記録された輻輳負荷より低い場合、その現在の（低減された）電力レベル、及び現在の輻輳負荷が、前に計算されたレベル及び負荷の代わりに格納される。最終回において、ＡＰの電力レベルは、最期に格納／記録された（低減された）電力レベル／状態を使用して設定される。本発明のＬＫ方法を実行するためのソフトウェア・プログラムの例が、図６に示される。この方法が、コントローラなどによって、どのように実行されることが可能であるかの例は、以下のとおりである。
【００４３】
図５（ａ）に示されるＷＬＡＮ３０００を使用して、初期状態において、ＡＰａ、ＡＰａ、及びＡＰｃのすべてが、２という同一の電力レベル／インデックスを有することを見て取ることができる。次に、図７（ａ）を参照すると、例示的な初期ユーザ−ＡＰ関連付け及びＡＰ負荷が、示されている。この例において、ｃは、輻輳したＡＰである。本発明によれば、ＬＫ方法は、図７（ｂ）及び図７（ｃ）に示されるとおり、連続する２回でＡＰｃの電力インデックスを２回、低減する。第１回目の後、ｃにかかる負荷は、１２から１０まで低減され、この状態が、記録／格納される。第２回目の後、ＡＰｂが、１７という輻輳負荷を有する輻輳したＡＰになる。第３回目において、ＬＫ方法が、ＡＰｂの電力レベル／インデックスを低減し、これに相応して、ユーザｕ３が、ｕ３の関連付けを変更する。その結果、ＡＰｃは、再び、輻輳したＡＰになる。ＡＰｃは、現時点で、最小電力レベルを使用して伝送しているため、方法は、終了される。最後に、方法（例えば、コントローラ）は、図７（ｂ）に示されるとおり、記録された状態を使用して、ＡＰａ、ＡＰｂ、及びＡＰｃを構成する（例えば、電力レベルをＡＰに割り当てる）。
【００４４】
前述したとおり、本発明者らは、ＬＫ方法が、ネットワーク輻輳負荷を最小限に抑える最適状態を常に見出すことを発見した。この場合も、本発明者らは、この発見の詳細な証明を作成したものの、これらの証明は、この説明を可能な限り簡単にしておくように省略されている。
【００４５】
前述した完全知識方法及び限定された知識方法は、ネットワーク輻輳負荷を最小限に抑えるが、輻輳していないＡＰにかかる負荷を必ずしも平衡化しない。このことを認識して、本発明は、ネットワーク輻輳負荷を最小限に抑えることと、輻輳していないＡＰにかかる負荷を平衡化することをともに行う方法（及び、関連するデバイス、例えば、コントローラ）を提供する。
【００４６】
残念ながら、このことを実現することは、通常、「ＮＰ困難」である（すなわち、解に到達するのにかかる時間を算出することが可能でない）問題を解くことを要求し、近似解を見出すことさえ困難である。そうであるにもかかわらず、本発明者らは、ミニマックス優先度負荷平衡化問題と呼ばれるミニマックス問題の変種を発見し、多項式時間（すなわち、算出／近似されることが可能な時間）内に見出されることが可能である、この変種に対する最適解をさらに発見した。
【００４７】
本発明者らによって発見された解を提示する前に、いくらかのさらなる背景情報をまず提示する。
【００４８】
負荷平衡化方法の品質を評価する一般的に使用されるアプローチは、その方法が、ミニマム−マックス（「ｍｉｎ−ｍａｘ」）負荷平衡化解を生成するか否かを判定することである。非公式には、ネットワーク状態は、同一以上の負荷を有する別のＡＰの負荷を増加させることなしに、いずれのＡＰの負荷も低減する方法が全く存在しない場合、ミニマックス負荷平衡化していると考えられる。本発明者らは、状態Ｓの負荷ベクトルＹを、大きい順に並べられた各ＡＰの負荷から成るセットと定義する。さらに、実現可能なネットワーク状態Ｓは、対応する負荷ベクトルＹが、他のいずれかの実現可能な状態Ｓ′の他のいずれかの負荷ベクトルＹ′と比べて、同一以下のレキシコグラフ値を有する場合、ミニマックス負荷平衡化しているという言い方がされる。
【００４９】
前述したとおり、ミニマックス負荷平衡化状態を見出す問題は、解くのがＮＰ困難である問題である。本発明者らは、このことを実証する詳細な証明を作成したが、前述の場合と同様に、これらの証明は、本発明の説明を簡略化するために省略されていることを理解されたい。さらに、本発明者らは、「より単純な」問題、すなわち、知られている最小輻輳負荷に関する輻輳したＡＰの最小セットを識別するという問題でさえ、単独で、ＮＰ困難であることを実証する証明も作成した。これらの証明もまた、省略されている。
【００５０】
これらの問題の解が、ＮＰ困難であることを認識して、次に、本発明者らは、ミニマックス負荷平衡化問題の変種を発見し、その後、多項式時間内に計算されることが可能な、この変種の最適解を発見した。本発明者らによって発見された変種において、ＡＰのセット内の各ＡＰａは、重みｗとも呼ばれる固有優先度を有するものと想定される。この重みは、そのＡＰの重要度を示す。本発明者らは、優先度負荷と呼ばれる新たなＡＰ負荷定義も作成した。
【００５１】
例えば、優先度ｗａを有するＡＰａを考慮し、ｌａを、ＡＰａの関連付けられたユーザのすべてのユーザの集計された負荷であるものとする。ｙａによって表されるＡＰａの優先度負荷は、順序付けられたペアｙａ＝（ｌａ，ｗａ）と定義される。簡明のため、ＡＰの優先度負荷を「ＡＰ負荷」と呼ぶ。ＡＰａは、ｙａ＝（ｌａ，ｗａ）が、ｙｂ＝（ｌｂ，ｗｂ）より高いレキシコグラフ値を有する（すなわち、以下の条件の１つが満たされる、すなわち、（１）ｌａ＞ｌｂである、又は（２）ｌａ＝ｌｂであり、かつｗａ＞ｗｂである）場合、ＡＰｂより高い負荷を有すると言うことが可能である。
【００５２】
同一の優先度を有する２つのＡＰは存在しないため、同一の（優先）負荷を有する２つのＡＰは存在しないということになる。この認識は、以下の特性を発見するように本発明者らを導いた。すなわち、任意のネットワーク状態において、輻輳したＡＰのセットは、単一のＡＰを常に含む（「特性１」）。
【００５３】
ミニマックス負荷平衡化問題の変種を発見した後、次に、本発明者らは、この問題の解を見出す作業に取り掛かった。本発明者らが発見した解は、後段で説明される。
【００５４】
以降の説明を簡単にするのに、本発明によって発見された新たなミニマックス負荷平衡化方法が、前述したＬＫモデルと組み合わせて提示される。とは言え、ミニマックス方法は、ＣＫモデルと組み合わせて使用されることも可能であることを理解されたい。
【００５５】
本発明の或る実施形態において、本発明によって提供されるミニマックス負荷平衡化方法は、最適負荷ベクトルＹ＊をもたらすミニマックス優先度負荷平衡化状態を繰り返し識別する。さらに、任意の回、ｍにおいて、方法は、前述したＬＫ方法／モデル又はＣＫ方法／モデルなどのルーチンを組み込んで、負荷ベクトルの第ｍ番の座標の優先度−負荷を最小限に抑えるネットワーク状態を計算する。本発明によって提供されるミニマックス方法は、次の２つの要件を満たす。すなわち、
（１）各回ｍの初期状態は、最適状態より優勢であるべきで、かつ
（２）第ｍ番の回における計算されたネットワーク状態は、前の回によって既に決定されているＡＰの負荷に影響を与える（増加させる）べきではない。
【００５６】
第１の要件を満たすのに、本発明によって提供される１つのミニマックス方法は、第１回目において最大電力状態で始まり、各回が、最適解の優勢状態で終わることを確実にする。さらに、第２の要件を満たすのに、前の回によって負荷が既に決定されている固定されたＡＰのセットＦが、定義される。初め、セットＦは空である。Ｆが、ＡＰのすべてを含むまで、各回において、新たなＡＰが、セットＦに追加される。輻輳負荷Ｙを、任意の固定されていないＡＰにかかる最大負荷と定義する。特性１から、任意の所与の時点で、輻輳負荷に関連する、輻輳したＡＰと呼ばれる固定されていないＡＰ、ｄが、１つだけが存在することになる。
【００５７】
各回ｍにおいて、ミニマックス方法は、ＬＫ方法（又はＣＫ方法）を呼び出して、負荷ベクトルの第ｍ番の座標を最小限に抑えることが可能である。第１の要件が、繰り返しの始めに満たされているものと想定すると、以下の３つの変数が生成され、格納される。すなわち、（１）それまでに見出された最適状態の輻輳負荷値を示す記録された輻輳負荷Ｙ、（２）輻輳負荷Ｙを有する第１の発見された状態を示す記録された状態変数Ｓ、及び（３）輻輳負荷に関連するＡＰを識別する記録された輻輳ＡＰ、ｄである。
【００５８】
本発明のさらなる実施形態によれば、ミニマックス方法は、変数Ｓ、Ｙ、及びｄをまず初期設定する。次に、方法は、輻輳したＡＰを繰り返し識別し、輻輳したＡＰが、最小電力レベルで既に伝送している場合、停止する。最小電力レベルで伝送していない場合、方法は、輻輳したＡＰの電力レベルを低減し、輻輳負荷、ならびに固定されたＡＰ（すなわち、伝送電力レベルが、前の回に既に計算されているＡＰは、現在、「固定されている」又は設定されている）の負荷を評価する。方法は、固定されたＡＰのいずれかが、高い負荷を被る場合、停止する。このことにより、固定されたＡＰの負荷を保つために、第２の要件が満たされることが確実にされる。さもなければ、より低い輻輳負荷を有する状態が発見された場合、方法は、変数を更新することによって、この状態のレコードを保持する。最後に、方法は、最後に格納された状態（電力レベル）に従ってＡＰの電力レベルを設定することを含み、記録された状態Ｓ、及び対応する輻輳したＡＰｄを戻す。言い換えると、電力レベル低減の後、１つのＡＰの電力レベルが固定になる。このＡＰが、次に、固定されたＡＰのセットに追加される。電力レベルが固定されていない１つ又は複数のＡＰが存在する場合、方法は、別の固定されていないＡＰの電力レベルを計算することによって続く。
【００５９】
方法は、この場合も、第（ｍ＋１）番の座標の負荷を最小限に抑えるためにＬＫ方法／モデル又はＣＫ方法／モデルを含むことが可能である。本発明によって提供されるミニマックス方法を表すソフトウェア・プログラム又はルーチンの例が、図８に示される。以下は、本発明によって提供されるミニマックス方法を実行するコントローラが、どのように実施されることが可能であるかの一例である。
【００６０】
この場合も、図５（ａ）に示されるＷＬＡＮ３０００を考慮されたい。ＬＫ方法の第１回の呼び出しの後、図９（ａ）に示されるネットワーク状態が、生成される。前段で実証されたとおり、この状態は、負荷ベクトルの第１の座標を最小限に抑える他のいずれの状態よりも優勢である。ＬＫ方法の第２回の呼び出しが、このネットワークの唯一のミニマックス負荷平衡化状態である（ＡＰ優先度にかかわらず）、図９（ｂ）に示される状態を生成する。
【００６１】
本発明者らは、本発明によって提供されるミニマックス負荷平衡化方法が、最適負荷ベクトル及びミニマックス負荷平衡化解を常に見出すことを発見した。証明は、前述の場合と同様に、本発明の説明をさらに簡明にするように省略されている。
【００６２】
本発明の他の特徴の説明に移る前に、１つのさらなるポイントが注目に値する。本発明者らによって発見されたミニマックス方法の複雑度は、Ｏ（Ｋ−／Ａ／４−／Ｕ／）であることが（本発明者らによって作成された証明を介して）示されることが可能である（Ｋ、Ａ、及びＵの定義に関しては、表１、行６、行１、及び行１３をそれぞれ参照）。
【００６３】
前述したとおり、本発明によって提供される方法のそれぞれは、コントローラなどによって実行されることが可能である。さらに、ＮＯＣが、前述した方法のいずれか１つを実行すると、ＮＯＣは、ＮＯＣが一部分を成すＷＬＡＮ内の各ＡＰと、それらのＡＰが、本発明によって提供される方法をコントローラが実行した際に生成される電力レベル低減及びユーザ割り当て／関連付け動作を実施することを確実にするために、メッセージ、命令などを交換するようにさらに動作できることが可能である。
【００６４】
とは言え、ユーザが、ＷＬＡＮに到着する、又はＷＬＡＮから離れるたびに、コントローラなどが、前述した最適化方法を実行するよう要求することは、頻繁な関連付け変更、及び進行中のユーザ・セッションの潜在的な妨げにつながる可能性がある。これを回避するのに、本発明者らは、関連付け変更の回数と、最適な負荷平衡化したＷＬＡＮを維持したいという望みとの間の釣り合いをとるオンライン戦略を作成した。そのようなオンライン戦略の基礎をなす概念は、「大域最適化」と「局所最適化」を組み合わせる。
【００６５】
局所最適化は、ＷＬＡＮの負荷が、ユーザが到着する、ならびに／又は出発するたびに絶えず平衡化される戦略であるのに対して、大域最適化は、本発明によって提供される方法が、定期的にだけ呼び出される、又は局所最適化戦略が、負荷平衡化状態を維持するのに失敗した場合には必ず呼び出される戦略を含む。本発明の或る実施形態によれば、オンライン戦略は、以下の３つの構成パラメータ、すなわち、最小負荷閾値、セル適応閾値、及び時間閾値を使用する。最初の２つのパラメータは、局所最適化が、取るに足らない利得しかもたらさない場合に、そのような最適化の使用を防止するため、及びアクティブなユーザに対するサービス割り込みを防止するために、局所最適化をいつ呼び出すかを決定する。最後のパラメータは、大域最適化が、どれだけ頻繁に呼び出されることが可能であるかを制御する。
【００６６】
局所最適化方法は、後段で簡単に説明されるとおり、ＡＰの電力レベルを低減する、又は増加させることが可能であるため、大域最適化方法とは異なる。
【００６７】
本発明によって提供される局所最適化方法において、各ＡＰａに関して、そのＡＰａの近隣のＡＰのすべてのＡＰのセットＮａを定義し、ｙａを、Ｎａの中のＡＰにかかる平均負荷とする。ＡＰａにかかる負荷が、いずれの理由であれ（例えば、ユーザ移動又は局所最適化動作）、低下すると、本発明によって提供されるオンライン方法は、その新たな負荷ｙａが、セル拡大条件を満たすか否かを検査し、この検査は、近隣ＡＰのセットの中のＡＰｂが、最小負荷閾値より大きい負荷を有し、かつ、その新たな負荷ｙａが、Ｎａの中のＡＰの平均負荷に値（１−セル適応閾値）を掛けることによって計算された値より小さい値を有するか否かを判定することである。この条件が満たされ、かつ、ＡＰａの電力インデックスｐａが、最大ではない場合、本発明のオンライン方法は、ＡＰａの電力レベルを１だけ増加させる。
【００６８】
逆に、ＡＰａにかかる負荷が増加した場合、本発明のオンライン方法は、セル縮小条件を検査し、この検査は、ｙａが、最小負荷閾値より大きく、かつ、Ｎａの中のＡＰの平均負荷に値（１＋セル適応閾値）を掛けることによって計算された値より大きいか否かを判定することである。この条件が満たされ、かつ、ＡＰａの電力インデックスｐａが最小ではない場合、オンライン方法は、ＡＰａの電力レベルを１だけ低減する。
【００６９】
最後に、これら２つの条件のいずれかが満たされるが、局所最適化動作が、電力レベルを調整することができない場合、大域最適化が、呼び出される。
【００７０】
本発明者らは、２つの既存の方法、すなわち、ＳＳＦ（Ｓｔｒｏｎｇｅｓｔ−Ｓｉｇｎａｌ−Ｆｉｒｓｔ）方法及び関連付け制御方法に対して、本発明者らの新規の負荷平衡化方法の性能を比較するシミュレーションを行った。ＳＳＦは、ＩＥＥＥ８０２．１１規格において使用されるデフォルトのユーザ−ＡＰ関連付け方法である。関連付け制御方法は、信号強度に単に基づいて関連付けを決定するのではなく、ミニマックス公平帯域幅割り当てを実現するユーザ−ＡＰ関連付けを決定する。ミニマックス公平問題は、ＮＰ困難であるため、関連付け制御方法は、ユーザが、複数のＡＰに同時に関連付けられることが可能であるという想定の下で分数最適解ＦＲＡＣをまず計算し、次に、単一の関連付け制約を満たすように丸めを介して整数解ＩＮＴを獲得する。本発明者らは、本発明者らの解の特性が知られているため、これらの方法をベンチマークとして選択した。
【００７１】
ＦＲＡＣ解は、厳密な性能上限（すなわち、可能な最低の輻輳負荷）をもたらすのに対して、ＩＮＴは、２近似タイプの解を保証する。さらに、ユーザの数が増えるにつれ、ＩＮＴは、ＦＲＡＣと収束する。本発明者らは、本発明者らの方法が、相当に、より高い自由度を有する最適関連付け制御方法より性能が優れているとは予期していなかった。ＩＮＴ解を本発明者らの方法と比較する際の本発明者らの目的は、本発明者らの方法が、ＩＮＴ方法において必要とされる、各移動体上の特別なクライアント・ソフトウェアの必要なしに、関連付け制御方法と同等の性能を実現することを示すことであった。しかし、意外なことに、本発明者らのシミュレーションの結果は、本発明によって提供される方法が、様々な負荷条件においてＩＮＴ解より性能が優れていることを示す。
【００７２】
これらのシミュレーションがどのように行われたかの詳細は、説明を簡明にするために省略されている。代わりに、本発明者らは、本発明者らのシミュレーション結果のサンプルのグラフを含めた。例えば、図１０は、１００名のランダムに分布したユーザを含む、負荷平衡化技術の比較を含むシミュレーション結果を示す。このユーザ数は、アクティブなユーザに対するＡＰの比が、５である、ほどほどに負荷のかかったネットワークをシミュレートするように選択された。Ｙ軸は、ｙａ（ＡＰ負荷）を表すのに対して、Ｘ軸は、ＡＰ電力レベル／インデックスを表す。ＡＰは、ｙａ値が大きい順に並べられることに留意されたい。各ｙａ値は、３００回のシミュレーション実行を平均することによって獲得される。整数ｘインデックスに対応するポイントだけが、意味がある（連続した線は、単に提示の目的で引かれている）。太い実線は、本発明者らのミニマックス方法を表し、細い実線は、本発明者らの最小輻輳方法を表す。両方の方法が、同一の最大ｙａ値を生成するが、ミニマックス方法は、最小輻輳方法と比べて、より低いレキシコグラフ次数を有する負荷ベクトルを生成することを見て取ることができる。太い破線は、ＩＮＴ解を表し、水平の細い破線は、ＦＲＡＣ解を表す。ミニマックス解とＩＮＴ解はともに、ＳＳＦ解よりも明らかに良好である。ミニマックス解とＩＮＴ解はともに、ＦＲＡＣより約３５％高い、非常に似通った最大ｙａ値をもたらす。
【００７３】
また、本発明者らは、５０名のユーザを使用する同様のシミュレーションも実行し、このシミュレーションの結果が、図１１に示される。図示されるとおり、本発明者らのミニマックス方法は、ＩＮＴ方法より大幅に性能が優れている。興味深いことに、ＦＲＡＣ及びＳＳＦと比べると、本発明者らのミニマックス方法の相対的性能は、ユーザの数によってひどく影響を受けているように見えない。同一の傾向は、本発明者らによって行われた他のシミュレーションにおいても観察された。例えば、２００名のユーザ（図示せず）が使用された場合、ＦＲＡＣと本発明者らの方法との格差は、３５％で変わらなかった。ネットワーク負荷条件（すなわち、ユーザの数）にかかわらず、ＦＲＡＣ解と比べた際の、本発明のミニマックス方法の安定した相対的性能は、本発明によって提供される方法の多くの長所の１つである。
【００７４】
また、本発明者らは、不平衡のユーザ分布の事例も考慮した。例えば、ユーザの２０％だけが、ランダムに分布しており、残りのユーザは、互いに重なり合わない２つのホットスポットに集中している。各ホットスポットは、７５メートル半径を有する円形の区域であることが可能である。１つのホットスポットは、他方のホットスポットより２倍多いユーザを含むことが可能である。この状況は、これらのホットスポットにおいて重い負荷条件を生じさせる。図１２は、ユーザの総数が１００名である場合の例示的な結果を示す。図１２は、本発明によって提供されるミニマックス方法が、ホットスポット（すなわち、重い負荷条件）が存在する場合に、さらに良好な性能を示し、ＩＮＴより優れていることを示す。
【００７５】
電力レベルの数（これまで、前述した例は、１０の電力レベルを使用した）の影響を調べるのに、本発明者らは、異なる４つの電力レベル範囲をシミュレートした。結果が、図１３に示される。図示されるとおり、電力レベルの数の影響は、本発明者らによって行われたシミュレーションにおいて５から１０までの間である或る電力レベル数を超えると、取るに足らなくなる。
【００７６】
本発明のＬＫ方法を実行する際に、コントローラが、いくつの動作を実行しなければならない可能性があるかの理解を得るのに、本発明者らは、そのような方法のシミュレーションを実行し、電力レベル調整及びユーザ関連付け変更の回数を数えた。収集された統計が、図１５に示す表ＩＩに要約されている。各テーブルエントリに関して、２つの数が与えられる。つまり、第１の数は、ＬＫ方法を呼び出したミニマックス方法に関するのに対して、第２の数は、ＬＫ（最小輻輳）方法／モデルだけに関する。一般に、ＬＫ方法は、かなり迅速に収束するのに対して、ミニマックス方法は、もう少し長くかかる。例えば、電力調整間隔が、１秒である場合、１００名のランダムなユーザのネットワークにおける負荷平衡化は、ＬＫ（最小輻輳）方法／モデルを使用して、約３３秒かかり、ＬＫ方法を呼び出すミニマックス方法を使用して、２分未満かかる。ユーザの数の増加は、収束時間を必ずしも増大させるように思われず、ホットスポットの存在も、収束時間を増大させるように思われない。実際、ＬＫ（最小輻輳）方法／モデルを使用して、収束時間は、短くなる。
【００７７】
前述した説明は、本発明のいくつかの例を示した。しかし、本発明の真の範囲は、添付の特許請求の範囲によって確定される。
【背景技術】
【０００１】
無線ローカル・エリア・ネットワークＷＬＡＮにおいて、無線デバイスは、すべての利用可能なチャネルをスキャンして、近くのアクセス・ポイントＡＰを検出し、次に、最も強い受信信号強度指標ＲＳＳＩを有するＡＰに、そのようなＡＰ又は近くの他のＡＰにかかる負荷を考慮に入れることなしに、無線デバイスを関連付ける。
【０００２】
実用可能なＩＥＥＥ８０２．１１ ＷＬＡＮに関する最近の研究は、トラフィック負荷が、しばしば、ＷＬＡＮ内のＡＰの間で不均一に配分されていることを示している。通常、任意の所与の時点で、一部のＡＰには、重い負荷がかかる傾向があるのに対して（いわゆる「輻輳した」ＡＰ）、他のＡＰは、そうではない。この状況は、ＷＬＡＮ内で負荷の不平衡を生じさせる。負荷の不平衡は、ネットワークが、ネットワークの容量を完全に利用することを阻み、ネットワークがサービスを公平で均等な仕方で提供することを妨げるため、望ましくない。
【０００３】
現在、ＩＥＥＥ８０２．１１ ＷＬＡＮ規格は、負荷の不平衡を解決する決まった方法を提供しない。この欠点を克服するのに、様々な負荷平衡化スキームが、学界と業界の両方によって提案されている。これらの方法のほとんどは、ユーザによって操作されるデバイス（例えば、コンピュータ）において独自のクライアント・ソフトウェア、又は特別に設計されたＷＬＡＮカードを展開することによって、ユーザ−ＡＰ関連付けを直接にコントロールするというアプローチをとる。これらのアプローチでは、ＡＰは、変更されたビーコン・メッセージを介して、ＡＰの負荷レベルをユーザ・デバイス（時として、単に「ユーザ」と呼ばれる）にブロードキャストし、各ユーザは、かかっている負荷が最も小さいＡＰを選択する。
【０００４】
そのようなユーザ選択アプローチは、負荷平衡化を実現することができるものの、すべての（又はほとんどの）ユーザ・デバイスへの独自のクライアント・ソフトウェア／ハードウェアの展開は、実現するのが困難である。例えば、今日、ユーザは、ホテル、空港、ショッピングセンタ、及び大学キャンパスなどの様々なＷＬＡＮにアクセスする。これらの異なるネットワークは、異なる負荷平衡化機構をおそらく採用している異なる組織によって管理される。ユーザが、異なる各ネットワークに関して１つずつ、複数の異なるクライアント・モジュールを有すると見込むのは、非現実的である。
【０００５】
したがって、独自のクライアント・モジュールなどの使用を要求しない新たな負荷平衡化スキームを提供することが望ましい。
【０００６】
また、他のタイプのネットワークも、負荷平衡化の課題に直面する。例えば、ＣＤＭＡセルラーネットワークにおいて、セル内でアクティブなユーザの数が増えることにより、そのセルの基地局において感知される合計の干渉の増加が生じる。これにより、そのセルが輻輳することになる。セルが輻輳すると、そのセル内でユーザによって操作されるデバイスは、デバイスが基地局に送信する信号が、許容できる信号対雑音比で受信されることを確実にするために、より高い電力レベルで送信して、干渉の影響を克服する必要がある。セル内の電力レベルが高まるにつれ、生成された信号は、近隣のセルに対してより強い干渉を生じさせる。その結果、そのようなセルを含むネットワークの全体的な容量が、低下し始める。干渉のこれらの不要な増加を克服するのに、いわゆる「セル・ブリージング」技術が開発された。しかし、一般的に言えば、ＣＤＭＡネットワークのために開発された既存のセル・ブリージング技術は、ＷＬＡＮにおいてうまく機能しない。
【０００７】
ＷＬＡＮは、ＣＤＭＡネットワークの場合と同様の負荷平衡化の課題に直面するため、本発明者らは、既存のセル・ブリージング技術の欠点をまず認識することによって、これらの課題をどのように解決すべきかを研究することを開始した。例えば、図１（ａ）を参照すると、同一の最大電力レベルで伝送しているものと想定される３つのＡＰ、すなわち、ａ、ｂ、及びｃを有するＷＬＡＮ１が、示されている。簡明のため、数名のユーザを各ＡＰに割り当てる。図１（ａ）では、１名のユーザがＡＰａに、８名のユーザがＡＰｂに、１名のユーザがＡＰｃに最初に割り当てられる。この例において、ＡＰの負荷は、割り当てられた、又は関連付けられたユーザの数であるものと定義する。このシナリオを所与として、ＡＰｂは、ＡＰａ及びＡＰｃよりもはるかに高い負荷を有する。既存のセル・ブリージング技術によれば、ＡＰｂにかかる負荷を減らすのに、ＡＰｂの伝送電力が、低減されなければならない。このことは、ｂの伝送範囲／セル・サイズの縮小につながる。図１（ａ）では、範囲は、例えば、境界１０１から境界１０２に縮小する。図１（ａ）に示されるとおり、ＡＰｂから最も遠く離れて位置している４つのユーザ／デバイス１〜４が、セル・サイズのこの縮小の影響を受ける。セルの元のサイズにおいて、ユーザ１〜４は、セルの範囲内にあり、したがって、ＡＰｂ伝送の範囲内にある。セルが、サイズ１０１からサイズ１０２に縮小するにつれ、ユーザ１〜４は、ＡＰｂの範囲の丁度端ぎりぎりに（もちろん、時として、この範囲の外に）自らが位置していることに気付く。ＡＰｂから、より遠く離れていることは、通常、ユーザ１〜４によって使用されるデバイスにおける信号品質の低下をもたらす。より低い信号品質の検出に応答して、ユーザ１〜４によって使用されるデバイスは、より高い信号品質に関連するＡＰを選択するスキャン動作を開始する。例えば、図１（ａ）におけるユーザ１〜２の２名が、ＡＰａから、より高い信号品質を検出することが可能である一方で、ユーザ３〜４は、ＡＰｃから、より高い信号品質を検出する。より高い信号品質が検出されると、既存のセル・ブリージング技術によれば、これらのユーザは、ＡＰａ及びＡＰｃにそれぞれ移される。図１（ｂ）に示されるとおり、正味の効果は、ＷＬＡＮ１内で負荷／ユーザを、より均等に配分することである（すなわち、現時点で、３名のユーザがＡＰａに割り当てられ、４名のユーザがＡＰｂに割り当てられ、３名のユーザがＡＰｃに割り当てられているため）。
【０００８】
しかし、ＡＰｂの伝送電力の低減は、ＡＰｂと、ユーザ１〜４だけではなく、ＡＰｂのセル内のユーザのすべてとの間のチャネル／リンクの信号品質に影響を及ぼす。このため、別のＡＰに移されない（すなわち、ＡＰｂに関連付けられたままである）ユーザ／デバイス５〜８もまた、より低い信号品質を検出する。これに応答して、ユーザ５〜８によって使用されるデバイスは、より低いビットレートで通信しなければならない可能性がある。より低いビットレートにおいて、情報（時として、「トラフィック」と呼ばれる）が、ユーザ５〜８からＡＰｂに伝送されるのに、より長い時間がかかる可能性がある。このことは、各ユーザ５〜８が寄与する、ＡＰｂにかかる負荷を事実上、増大させる（ＡＰ負荷が、ユーザの数だけでなく、実効的なユーザ・スループットも考慮することによって算出される場合）。このため、ＡＰにかかる負荷を減らすどころか、既存のセル・ブリージング技術は、負荷を実際には増大させる可能性がある。
【０００９】
したがって、無線ネットワーク内で負荷の不平衡を回避する、又は最小限に抑える方法及びデバイスを提供することが望ましい。特に、ＷＬＡＮ内で負荷の不平衡を最小限に抑えるのに使用されることが可能である、より効果的なセル・ブリージング方法（及び関連するデバイス）を提供することが望ましい。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許仮出願第６０／７９３３０５号
【発明の概要】
【課題を解決するための手段】
【００１１】
本発明者らは、ＷＬＡＮなどの無線ネットワーク内で負荷の不平衡を最小限に抑えるが、前述した不平衡を回避する方法及びデバイスを見出した。本発明によれば、データ／トラフィックを伝送するのに使用される伝送電力レベルが、ビーコン・メッセージを伝送するのに使用される伝送電力レベルと分離され、ビーコン・メッセージを伝送するのに使用される伝送電力レベルだけが、低減される。
【００１２】
データを伝送するのにＡＰによって使用される電力レベルを維持することによって、そのＡＰの範囲内のデバイスの伝送ビットレートが、維持される。しかし、ＡＰ範囲内の各ユーザ／デバイス、又はＡＰに接近しているＡＰは、それらのユーザ／デバイスが、現在、割り当てられている（又は割り当てられることを求めている）ＡＰからの別個のビーコン・メッセージの信号品質を検出して、評価することによって、既存のＡＰに割り当てられたままにする（又は割り当てられる）、又は別のＡＰに切り替えるか否かを決定するため、ビーコン・メッセージを伝送するのに使用される電力レベルを低減することによって、本発明は、事実上、ＡＰのセルを縮小する。その結果、このことは、新たなユーザが、ＡＰに割り当てられないようにさせる。ＡＰが既に輻輳している事例において、このことは、ＡＰが、さらに輻輳することを防止する。
【００１３】
ＡＰにかかるトラフィック負荷を低減することは、負荷の不平衡を回避する問題解決法の一部である。その他の部分は、１つのＡＰから、過負荷になっていない近隣のＡＰにトラフィックを向ける、又は向け直す（一まとめにして、「向ける」）ことである。
【００１４】
１つのＡＰにかかるトラフィック負荷を減らすことを、他方で適切な近隣のＡＰにかかる負荷を増やすことと組み合わせることにより、ＷＬＡＮ内のトラフィック負荷が平衡化される。
【００１５】
局所最適化ヒューリスティックに主に依拠する、ＷＬＡＮ内でトラフィック負荷を平衡化する従前の試みとは異なり、本発明は、最適なセル・サイズ設定方法（及び関連するデバイス）を使用して、決定論的なミニマックス負荷平衡化解を見出す。
【００１６】
また、本発明によって提供される方法及びデバイスは、ＷＬＡＮ負荷平衡化のためのほとんどの既存の提案とは異なり、ユーザ支援、又は既存の８０２．１１標準の変更を要求しないため、特に魅力的でもある。
【００１７】
代わりに、本発明によって提供される方法は、既存のデバイスを制御するソフトウェアを変更することによって実施されることが可能である。より詳細には、例えば、ネットワーク・オペレーションズ・センタＮＯＣに配置されたネットワーク・コントローラ又はネットワーク管理ユニットによって使用されるソフトウェアを変更することによって実施されることが可能である。
【００１８】
本発明の一実施形態では、そのようなコントローラは、ＡＰのデータ・トラフィック・チャネルの伝送電力を変更することなしに、ＡＰのビーコン・メッセージの伝送電力を変更することによって、ＡＰのセル・サイズを小さくするように動作可能である。その後、コントローラは、このセルの境界近くのユーザ／デバイスを、それほど輻輳していないＡＰに向ける。今日、利用可能なＡＰは、複数の伝送電力レベルを既にサポートしており、したがって、本発明者らは、本発明が、例えば、ソフトウェア更新を既存のＡＰに配信すること／ダウンロードすることによって容易に実施されることが可能であるものと考える。
【００１９】
さらに、本発明によって提供される新規のセル・ブリージング方法は、特定の負荷定義に結び付けられておらず、広い範囲の負荷定義をサポートする。負荷寄与は、ＡＰに関連付けられたユーザの数といった単純なものであることが可能であり、あるいはより複雑であって、有効伝送ビットレート、平均トラフィック要求、又は乗法ユーザ負荷寄与のような要因を考慮に入れることが可能である。
【００２０】
本発明のさらなる実施形態において、ネットワーク・オペレーション・センタＮＯＣなどにおいて動作する、本発明によって提供される方法及びコントローラは、ＡＰから（例えば、Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ、「ＳＮＭＰ」メッセージを介して）負荷情報及び関連付け情報を収集する。利用可能な情報の範囲に応じて、次に、２つのモデル又は方法（この２つの語は、本明細書で互いに区別なく使用されることが可能である）の１つが、負荷平衡化を実行するのに使用されることが可能である。第１のモデルは、可能なユーザ−ＡＰ関連付け、及び対応するＡＰ負荷が、可能なすべてのビーコン電力割り当てに関してアプリオリに知られているＣＫ（完全知識）モデルである。そのような情報は、容易に入手可能でない可能性があるので、本発明は、現在のビーコン電力割り当てだけに関するユーザ−ＡＰ関連付け及びＡＰ負荷が入手可能である、ＬＫ（限定された知識）モデルも提供する。ＣＫモデルは、より実際的なＬＫモデルのための構成要素の役割をする。
【００２１】
本発明によって提供されるモデルのそれぞれは、一般に、２つのステップを含む。第１のステップは、負荷が、輻輳負荷と呼ばれる、最も輻輳したＡＰにかかる負荷を最小限に抑えることである。本発明は、各モデルに関して１つずつ、最適解を見出す２つの多項式時間アルゴリズム／方法（以降、「（１つ又は複数の）方法」と呼ばれる）を提供する。このことは、負荷平衡化問題が、強ＮＰ困難である（すなわち、限定された時間内に解くことが非常に困難である）ことが知られているため、重要な成果である。さらに、本発明者らが、ＬＫモデルにおいて使用されることが可能な多項式時間最適方法を見出したことは、特に重要である。本発明によれば、負荷平衡化問題を解くのに提供される解は、現在のＡＰ電力レベル設定が、最適な電力レベル設定より「優勢である」（すなわち、各ＡＰが、最適解における電力レベル以上の電力レベルを有する）限り、最適解は、それでも、一連の電力低減動作を実行することによって得られることが可能であるという、本発明者らによって見出された洞察に基づく。本発明によって提供される１つの例示的な方法において、最大電力レベルから始めて、選択されたＡＰセットの電力レベルが、繰り返し低減される。ＣＫモデルでは、ボトルネック・セットの概念を使用して、最適解への収束が確実にされる。ボトルネック・セットの中のすべてのＡＰの電力レベルを低減した後、各ＡＰの負荷が、電力レベル低減より前の初期の輻輳負荷と同一のままである、又は厳密により低いことが保証される。ＬＫモデルの場合、電力がそれ以上、低減されることが可能でなくなるまで、輻輳したＡＰの電力レベルが、徐々に低減され、その間中、電力の各回の低減の後に見出される最良の解が記録される、最適状態記録と呼ばれる異なるアプローチが、使用される。
【００２２】
第２のステップは、いわゆるミニマックス負荷平衡化解を見出すという問題を解くことを含む。本明細書において明瞭／簡単にするために証明は、省略されているものの、本発明者らは、この問題も、解決されるべき強ＮＰ困難問題であること、及び解を近似する許容できる方法は、全く存在しないことを発見／証明した。より具体的には、本発明者らは、座標に関する近似比を保証する方法は、全く存在しないことを証明しており、任意のプレフィックス合計近似アルゴリズムの近似比は、少なくともＰ（ｌｏｇ ｎ）であり、ただし、ｎは、ネットワークにおけるＡＰの数である。思いとどまることなく、本発明者らは、最適解が、両方のモデルに関して多項式時間内に計算されることが可能な、優先度負荷平衡化と呼ばれるミニマックス問題の変種を発見した。優先度負荷平衡化において、ＡＰ負荷は、ＡＰの関連付けられたユーザの集計された負荷寄与と、固有ＡＰ優先度との順序付けられたペアとして定義される。最適状態記録を使用して、ミニマックス優先度負荷平衡化解の各座標を繰り返し計算する方法が、構築された。
【図面の簡単な説明】
【００２３】
【図１ａ】本発明の特徴を示すのに使用されるＷＬＡＮの例を示す図である。
【図１ｂ】本発明の特徴を示すのに使用されるＷＬＡＮの例を示す図である。
【図２ａ】本発明の特徴を示すのに使用されるＷＬＡＮのさらなる例を示す図である。
【図２ｂ】本発明の特徴を示すのに使用されるＷＬＡＮのさらなる例を示す図である。
【図３】本発明による「ボトルネック・セット」を計算するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図４】本発明の完全知識方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図５ａ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｂ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｃ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図５ｄ】本発明の完全知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図６】本発明の限定された知識方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図７ａ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｂ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｃ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図７ｄ】本発明の限定された知識方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図８】本発明のミニマックス優先度負荷平衡化方法を実行するのに使用されることが可能なソフトウェア・プログラムの例を示す図である。
【図９ａ】本発明のミニマックス優先度負荷平衡化方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図９ｂ】本発明のミニマックス優先度負荷平衡化方法の実行の結果としてのＷＬＡＮの変更の例を示す図である。
【図１０】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１１】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１２】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１３】本発明によって提供される方法と、既存の負荷平衡化方法との違いを示すグラフである。
【図１４】この説明全体で使用される記号のいくつか、及びそれらの記号の例示的な意味のリストである。
【図１５】本発明によって提供される限定された知識方法を実行するコントローラなどに関する例示的なランタイム統計を示す表である。
【発明を実施するための形態】
【００２４】
図１（ａ）を再び参照すると、ａ〜ｃで表されるＡＰのセットを有するＷＬＡＮ１０００が示されている。示されていないものの、ＡＰａ〜ＡＰｃのすべてが、有線インフラストラクチャ、例えば、インターネットに直接に接続されることが可能であるものと理解されたい。各ＡＰａ〜ＡＰｃは、或る伝送範囲を有し、そのＡＰの範囲内のユーザ１〜８だけにサービスを提供することが可能である。さらに、各ＡＰａ〜ＡＰｃは、複数の伝送電力レベルの１つを使用するように構成されることが可能である。簡単にするため、ＡＰａ〜ＡＰｃは、すべてのＡＰが、最小電力レベルで伝送している場合でさえ、すべてのユーザ１〜８が、少なくとも１つのＡＰによって範囲に入れられるように、ＡＰａ〜ＡＰｃの範囲間で高い度合いの重なり合いを確実にするように配備されるものと想定されることが可能である。
【００２５】
さらに、ユーザ１〜８は、準静的移動パターンを有するものと想定されることが可能である。つまり、ユーザは、自由に動くことができるが、同一の相対的位置に長時間にわたって留まる傾向にある。任意の所与の時点で、各ユーザ１〜８は、単一のＡＰａ〜ＡＰｃに関連付けられる。各ＡＰａ〜ＡＰｃは、ビーコン・メッセージを周期的に伝送して、そのＡＰａ〜ＡＰｃのプレゼンスを「公示する」。ユーザが、ＷＬＡＮ１０００に入ると、ユーザの関連付けられたデバイスは、ビーコン・メッセージを検出するために、ＷＬＡＮ１０００内のすべてのチャネルを走査する。ビーコン・メッセージを検出した後、ユーザのデバイスは、検出された各メッセージのＲＳＳＩを測定するようにさらに動作可能である。通常、デバイスは、次に、デバイスと、測定された最も強いＲＳＳＩに関連するＡＰとの間でリンクを作成するプロセスを開始する。その後、ユーザが確立したリンクの信号品質が、或る閾値を下回って低下し始めると必ず、ユーザに関連するデバイスは、ビーコン・メッセージのすべてを走査するプロセスを再び開始して、より強い信号が存在するかどうかを判定する。存在する場合、ユーザ／デバイスは、そのより強い信号に関連するＡＰと新たなリンクを確立しようと試みる。
【００２６】
前述した方法は、新たなユーザが、輻輳したＡＰに関連付けられないようにすることによって、ＷＬＡＮ内のＡＰにかかる負荷を平衡化する。しかし、このことは、輻輳したＡＰに即時の軽減をもたらさない可能性がある。即時の軽減（すなわち、負荷低減）のため、輻輳したＡＰに既に関連付けられているユーザ／デバイスが、その輻輳したＡＰを離れるように再割り当てされる必要がある。そのようにするのに、必要とされているのは、そのようなユーザ／デバイスが、別のＡＰからのビーコン・メッセージを検出するために走査動作を呼び出すよう、いわば、促す仕方である。これが行われることが可能な、いくつかの仕方が存在する。１つの仕方は、ＡＰのセル範囲が変更された後に、関連付け移転をトリガすることである。以降、説明を、ビーコン・メッセージの電力レベルだけに限定する。つまり、以降、「伝送電力」又は「電力レベル」又は「状態」という用語が使用される場合、これらの用語は、特に明記しない限り、又は文脈がそうでないことを示さない限り、ビーコン・メッセージを伝送するのに使用される電力だけと関係する。
【００２７】
前述したとおり、負荷の不平衡を最小限に抑える際の第１のステップは、ＷＬＡＮ内のＡＰにかかる負荷を最小限に抑えることである。本発明の一実施形態では、ＣＫモデルを使用して、負荷が最小限に抑えられる。代替の実施形態では、ＬＫモデルが使用される。
【００２８】
ネットワークは、ネットワーク（例えば、ＮＯＣ内のコントローラ）が、ＷＬＡＮ内のすべてのユーザ−ＡＰペアに関連する可能な信号減衰及び負荷寄与を検出する、又は収集することができる場合、「完全知識」を有するという言い方がされることが可能である。完全知識状態は、ユーザのすべてが、近くのすべてのＡＰからＲＳＳＩ情報を収集し、この情報を、ＮＯＣに配置されたコントローラに送信する場合、実現可能である。残念ながら、この能力は、既存のほとんどのＷＬＡＮにおいて、現在、利用可能ではない。それでも、ＣＫモデルは、現在の負荷割り当て及びユーザ割り当てを使用するＬＫモデルのための構成要素として有用である。
【００２９】
ネットワークは、ネットワーク（例えば、ＮＯＣに配置されたコントローラ）が、各ＡＰに、現在、割り当てられているユーザのセット、及びそのようなセットが割り当てられたＡＰにかかるそのような各ユーザの負荷寄与に関する情報だけしか検出する、又は収集することができない場合、限定された知識を有するという言い方がされることが可能である。
【００３０】
本発明の実施形態によれば、ＣＫモデルにおいて、コントローラが、ＷＬＡＮの状態を実際に変更することなしに、可能なすべての状態におけるユーザ−ＡＰ割り当て／関連付けをアプリオリに決定することができることが可能である。このことは、ＮＯＣが、所望される状態に関するオフライン計算を実行することを可能にする。そのようなオフライン計算は、ＬＫモデルにおいて実行可能ではない。
【００３１】
最適平衡化状態への、いずれのモデルの収束と関係する問題（すなわち、輻輳したＡＰにかかる負荷は、低下するが、別のＡＰにかかる負荷は、増加する）を克服するのにも、本発明は、以下の２つのさらなるアプローチの使用を提供する。ＣＫモデルに関して、本発明は、いわゆるボトルネック・セット電力低減をまず計算する。このアプローチは、最適状態に単調に収束する一連のセット電力低減を実行することを含む。このことにより、輻輳負荷が増加しないことが確実にされる。ＬＫモデルに関して、本発明は、最適状態記録をまず使用する。このアプローチでは、それまでに見つかった最良状態のレコードが、保持される。
【００３２】
本発明によれば、ボトルネック・セットは、すべての輻輳したＡＰ（負荷Ｙを有する）、ならびに、セット電力低減を実行したことの結果、負荷がＹ以上に上昇する可能性があるすべてのＡＰを含むＡＰの最小セットと定義されることが可能である。本発明者らは、ボトルネック・セットに関する形式的表現を作成した。しかし、この表現は、本発明の理解に必要とされず、本明細書では省略されている。代わりに、ボトルネック・セットの一例を次に提示する。
【００３３】
図２（ａ）に示されるＷＬＡＮ２０００を考慮されたい。ＡＰａ、ＡＰｂが、同一の電力レベルを有する場合、ＡＰａの電力レベルの低減は、ＡＰａの負荷を３から１まで低減する一方で、ＡＰｂにかかる負荷を２までしか増加させない。このため、この時点におけるボトルネック・セットは、ＡＰａだけを含むと言うことができる。しかし、図２（ｂ）に示されるとおり、ａが、ｂより低い電力レベルを有する場合、ｂの電力レベルを低減することは、ｂの負荷を２から０まで低減し、ａの負荷を３まで増加させる。この事例では、ボトルネック・セットは、ＡＰａとＡＰｂをともに含む。完全のため、ボトルネック・セットを計算するのに使用されることが可能な、本発明によって提供されるソフトウェア・プログラム／ルーチンの例が、図３に示される。
【００３４】
コントローラが、ＷＬＡＮの完全知識を有する事例において、ＷＬＡＮのボトルネック・セットは、容易に計算されることが可能である。最初に、各ＡＰａと各ユーザの間のＲＳＳＩが、計算される。この情報は、コントローラが、初期のユーザ−ＡＰ割り当て／関連付け、各ＡＰａにかかる負荷、及び最大負荷Ｙを決定することを可能にする。これらから、コントローラは、本発明者らによって作成された式を使用してボトルネック・セットを計算することができる。この場合も、そのような式の詳細は、本発明の理解に必要ではないが、前述したとおり、ボトルネック・セットを計算するルーチンの一例が、図３に示される。本発明者らによって導き出される証明のすべての正味の結果は、以下の発見であるとだけ言っておこう。すなわち、所与のＷＬＡＮに関するボトルネック・セットは、他のいずれのＡＰにかかる負荷も、最大負荷Ｙ以上に増加させない電力低減を使用して得られた輻輳したＡＰのセットを含むＡＰの最小セットである。ＡＰのボトルネック・セットを計算すると、本発明によって提供されるコントローラは、コントローラが、ＷＬＡＮの完全知識を有する場合、次に、このセットを使用して、ＷＬＡＮ内のＡＰ上の輻輳を最小限に抑える。
【００３５】
本発明の一実施形態によれば、ＣＫ方法は、すべてのＡＰが、最大電力状態にあり、ＡＰの最大伝送電力で伝送するものと初期に想定することによって、輻輳を最小限に抑える。その後、本発明によるコントローラによって実行されるＣＫ方法は、ボトルネック・セットを繰り返し計算する。計算されたセットを使用して、次に、方法は、別の電力低減動作が、適用される必要があるか、又は最適状態が見つかったかを判定する。この目的で、ＣＫ方法は、２つの終了条件（すなわち、電力低減の終了をトリガする条件）を利用する。第１の条件は、ボトルネック・セットが、ＡＰの完全なセットと等しいかどうかを判定する。この条件は、ＷＬＡＮ内のすべてのＡＰにかかる負荷が平衡化されており、したがって、さらなる電力低減が、ＡＰのいくつかにおける輻輳を、より軽くではなく、よりひどくする場合に、満たされることが可能である。第２の条件は、ボトルネック・セットが、最小電力レベルを使用して伝送しているＡＰを含むかどうかを判定する。含む場合、ボトルネック・セットの中のＡＰのすべてのＡＰの電力レベルは、等しく低減されることが可能でなく、方法は、終了される。そのような事例は、ＣＫ方法が、ＷＬＡＮ内のＡＰにかかる負荷が、平衡化されていないと判定し、輻輳したＡＰの電力レベルを繰り返し低減することによって最大負荷を減らすよう試みることを続ける場合に、通常、生じる。本発明によるＣＫ方法を実行するためのソフトウェア・プログラム又はルーチンの例が、図４に示される。
【００３６】
図５（ａ）は、ＷＬＡＮ３０００内のＡＰａ上、ＡＰｂ上、及びＡＰｃ上の輻輳が、本発明の例示的なＣＫ方法を使用して最小限に抑えられているＷＬＡＮ３０００の例を示す。図示されるとおり、ＡＰａ、ＡＰｂ、及びＡＰｃに加えて、ＷＬＡＮ３０００は、例示的なユーザｕ１、ｕ２、ｕ３、ｕ４、及びコントローラ３００１を含む。本発明の実施形態によれば、ＡＰａ、ＡＰｂ、及びＡＰｃは、ＡＰａ、ＡＰｂ、及びＡＰｃの関連するユーザ、負荷、及びさらなる関係のある情報をコントローラ３００１に提供するように動作可能である。この情報を受け取り、解析すると、コントローラ３００１は、現在、説明されているＣＫ方法を含め、本発明によって提供される方法を実行するように動作可能である。
【００３７】
続けると、ＡＰａ、ＡＰｂ、及びＡＰｃのそれぞれは、異なる３つの電力レベル０、１、及び２で動作することが可能である。図５（ａ）において、ユーザ−ＡＰ割り当て／関連付けが、実線又は破線として示され、ただし、実線は、ＡＰのそれぞれが、いつ同一の電力レベルで伝送するかを示し（デフォルトの関連付け）、破線は、可能な他の関連付けを示す。各線上の数字は、関連するＡＰにかかる負荷へのユーザによる寄与を示す。例えば、ｕ１は、ａだけに関連付けられることが可能であり、４という負荷をもたらす。ｕ３は、ＡＰのそれぞれに関連付けられることが可能であり、２という負荷をもたらす。ｕ３は、好ましくは、最高の電力レベルを有するＡＰを選択するが、互角の場合には、ｃを選好する。ｃが、ａ及びｂより低い電力レベルで伝送している場合、ｕ３は、ｂを選好する。アスタリスクは、２つの電力レベルの格差が、ユーザを移すのに要求されることを示し、例えば、ｕ２は、ＡＰａの電力レベルが、０であり、ＡＰｂの電力レベルが２である場合にだけ、関連付けをａからｂに変更することができる。
【００３８】
図５（ｂ）に示される初期状態において、ＡＰのすべては、２という同一の電力レベル／インデックスを有し、各ＡＰａ、ＡＰｂ、及びＡＰｃにかかる負荷は、それぞれ、７、０、及び１２である。本発明によって提供されるＣＫ方法の第１回目において、ボトルネック・セット（「Ｂ」）が、計算され、ＡＰｃが、このセットの中に含まれているものとして識別される。加えて、ｃの電力レベルが、１に低減される。その結果、ｕ３は、ｕ３の関連付けをＡＰｂに変更する。この新たなユーザ−ＡＰ関連付け及び負荷が、図５（ｃ）に示される。ｂは、依然として、輻輳したＡＰであることに留意されたい。しかし、ビーコン・メッセージを伝送するのにＡＰｃによって使用される電力レベルのさらなる低減は、ユーザｕ４が、ｕ４の関連付けをＡＰｂに変更するようにさせて、ＡＰｂにかかる負荷が、１７になるようにする。このため、図５（ｄ）に示される第２回目において、ボトルネック・セットは、ｃとｂをともに含む。ｐｃ＝０であるので、これが、最終回である。図５（ｄ）に示される最終状態は、輻輳を最小限に抑えるが、輻輳していないＡＰにかかる負荷を平衡化しない。そうすることは、後段で説明される本発明の第２のステップに任せられる。
【００３９】
さらなる発見において、本発明者らは、本発明によって提供されるＣＫ方法が、ＷＬＡＮの輻輳負荷を最小限に抑える最適状態を常に見出すことを発見した。本発明者らは、この発見を支える証明を作成した。しかし、これらの証明は、本発明の理解に必要ではなく、簡明のために省略されている。例えば、これらの証明は、ＣＫ方法が輻輳を最小限に抑えるのに、どのように使用されることが可能であるかについての理解に必要ではない。
【００４０】
次に、ＷＬＡＮの完全知識を獲得することが実現可能ではない場合に、輻輳を最小限に抑えるのに使用されることが可能な本発明の代替の実施形態に注目する。この第２の実施形態は、ＬＫ方法である。ＣＫ方法とは異なり、ＡＰのボトルネック・セットは、あらかじめ計算されることが可能でない。
【００４１】
しかし、この障害は、ネットワーク（例えば、ＷＬＡＮ）の状態が、最適未満であり（例えば、ＷＬＡＮにおけるＡＰにかかる負荷が、不平衡であり）、この状態が、最適解より優勢である限り、輻輳したＡＰのセットに関連するビーコン信号の電力レベルの、一連の同時の低減により、最適状態への（すなわち、ＷＬＡＮ内の負荷を平衡化する最適電力レベルへの）収束がもたらされることを、本発明者らが発見した際、本発明者らによって克服された。この発見は、それ自体のジレンマ、すなわち、そのような最適解に関連する終了条件（すなわち、低減をいつ停止するか）を識別するという課題を生じさせた。終了条件なしには、一連の低減は、最適未満の解を生じることになる可能性がある。そのような条件を決定するのに、本発明によって提供されるＬＫ方法は、最低の輻輳負荷に対応するすべてのＡＰの伝送電力レベルを記録する／格納する最適状態記録アプローチを使用する。より詳細には、最適状態記録アプローチは、２つの変数を定義する。第１の変数は、記録された状態（例えば、レベル）を保持し、第２の変数は、この記録された状態に関連する、記録された輻輳負荷と呼ばれる輻輳負荷値を保持する。
【００４２】
本発明の一実施形態によれば、ＬＫ方法は、以下のステップを含む。最初、方法は、すべてのＡＰが、記録された状態（例えば、電力レベル）、及び記録された輻輳負荷が、何らかの値に初期設定された最大電力状態（例えば、最大電力レベル）で動作しているところから始まる。次に、輻輳したＡＰのセットＤが、繰り返し計算され、このセットＤが、最小電力レベルにおけるＡＰ含まない限り、方法は、セットＤの中のＡＰの電力レベルを繰り返し低減する。各回の低減の後、新たな状態の現在の輻輳負荷が、測定され、現在の測定された負荷が、前の格納／記録された輻輳負荷より低い場合、その現在の（低減された）電力レベル、及び現在の輻輳負荷が、前に計算されたレベル及び負荷の代わりに格納される。最終回において、ＡＰの電力レベルは、最期に格納／記録された（低減された）電力レベル／状態を使用して設定される。本発明のＬＫ方法を実行するためのソフトウェア・プログラムの例が、図６に示される。この方法が、コントローラなどによって、どのように実行されることが可能であるかの例は、以下のとおりである。
【００４３】
図５（ａ）に示されるＷＬＡＮ３０００を使用して、初期状態において、ＡＰａ、ＡＰａ、及びＡＰｃのすべてが、２という同一の電力レベル／インデックスを有することを見て取ることができる。次に、図７（ａ）を参照すると、例示的な初期ユーザ−ＡＰ関連付け及びＡＰ負荷が、示されている。この例において、ｃは、輻輳したＡＰである。本発明によれば、ＬＫ方法は、図７（ｂ）及び図７（ｃ）に示されるとおり、連続する２回でＡＰｃの電力インデックスを２回、低減する。第１回目の後、ｃにかかる負荷は、１２から１０まで低減され、この状態が、記録／格納される。第２回目の後、ＡＰｂが、１７という輻輳負荷を有する輻輳したＡＰになる。第３回目において、ＬＫ方法が、ＡＰｂの電力レベル／インデックスを低減し、これに相応して、ユーザｕ３が、ｕ３の関連付けを変更する。その結果、ＡＰｃは、再び、輻輳したＡＰになる。ＡＰｃは、現時点で、最小電力レベルを使用して伝送しているため、方法は、終了される。最後に、方法（例えば、コントローラ）は、図７（ｂ）に示されるとおり、記録された状態を使用して、ＡＰａ、ＡＰｂ、及びＡＰｃを構成する（例えば、電力レベルをＡＰに割り当てる）。
【００４４】
前述したとおり、本発明者らは、ＬＫ方法が、ネットワーク輻輳負荷を最小限に抑える最適状態を常に見出すことを発見した。この場合も、本発明者らは、この発見の詳細な証明を作成したものの、これらの証明は、この説明を可能な限り簡単にしておくように省略されている。
【００４５】
前述した完全知識方法及び限定された知識方法は、ネットワーク輻輳負荷を最小限に抑えるが、輻輳していないＡＰにかかる負荷を必ずしも平衡化しない。このことを認識して、本発明は、ネットワーク輻輳負荷を最小限に抑えることと、輻輳していないＡＰにかかる負荷を平衡化することをともに行う方法（及び、関連するデバイス、例えば、コントローラ）を提供する。
【００４６】
残念ながら、このことを実現することは、通常、「ＮＰ困難」である（すなわち、解に到達するのにかかる時間を算出することが可能でない）問題を解くことを要求し、近似解を見出すことさえ困難である。そうであるにもかかわらず、本発明者らは、ミニマックス優先度負荷平衡化問題と呼ばれるミニマックス問題の変種を発見し、多項式時間（すなわち、算出／近似されることが可能な時間）内に見出されることが可能である、この変種に対する最適解をさらに発見した。
【００４７】
本発明者らによって発見された解を提示する前に、いくらかのさらなる背景情報をまず提示する。
【００４８】
負荷平衡化方法の品質を評価する一般的に使用されるアプローチは、その方法が、ミニマム−マックス（「ｍｉｎ−ｍａｘ」）負荷平衡化解を生成するか否かを判定することである。非公式には、ネットワーク状態は、同一以上の負荷を有する別のＡＰの負荷を増加させることなしに、いずれのＡＰの負荷も低減する方法が全く存在しない場合、ミニマックス負荷平衡化していると考えられる。本発明者らは、状態Ｓの負荷ベクトルＹを、大きい順に並べられた各ＡＰの負荷から成るセットと定義する。さらに、実現可能なネットワーク状態Ｓは、対応する負荷ベクトルＹが、他のいずれかの実現可能な状態Ｓ′の他のいずれかの負荷ベクトルＹ′と比べて、同一以下のレキシコグラフ値を有する場合、ミニマックス負荷平衡化しているという言い方がされる。
【００４９】
前述したとおり、ミニマックス負荷平衡化状態を見出す問題は、解くのがＮＰ困難である問題である。本発明者らは、このことを実証する詳細な証明を作成したが、前述の場合と同様に、これらの証明は、本発明の説明を簡略化するために省略されていることを理解されたい。さらに、本発明者らは、「より単純な」問題、すなわち、知られている最小輻輳負荷に関する輻輳したＡＰの最小セットを識別するという問題でさえ、単独で、ＮＰ困難であることを実証する証明も作成した。これらの証明もまた、省略されている。
【００５０】
これらの問題の解が、ＮＰ困難であることを認識して、次に、本発明者らは、ミニマックス負荷平衡化問題の変種を発見し、その後、多項式時間内に計算されることが可能な、この変種の最適解を発見した。本発明者らによって発見された変種において、ＡＰのセット内の各ＡＰａは、重みｗとも呼ばれる固有優先度を有するものと想定される。この重みは、そのＡＰの重要度を示す。本発明者らは、優先度負荷と呼ばれる新たなＡＰ負荷定義も作成した。
【００５１】
例えば、優先度ｗａを有するＡＰａを考慮し、ｌａを、ＡＰａの関連付けられたユーザのすべてのユーザの集計された負荷であるものとする。ｙａによって表されるＡＰａの優先度負荷は、順序付けられたペアｙａ＝（ｌａ，ｗａ）と定義される。簡明のため、ＡＰの優先度負荷を「ＡＰ負荷」と呼ぶ。ＡＰａは、ｙａ＝（ｌａ，ｗａ）が、ｙｂ＝（ｌｂ，ｗｂ）より高いレキシコグラフ値を有する（すなわち、以下の条件の１つが満たされる、すなわち、（１）ｌａ＞ｌｂである、又は（２）ｌａ＝ｌｂであり、かつｗａ＞ｗｂである）場合、ＡＰｂより高い負荷を有すると言うことが可能である。
【００５２】
同一の優先度を有する２つのＡＰは存在しないため、同一の（優先）負荷を有する２つのＡＰは存在しないということになる。この認識は、以下の特性を発見するように本発明者らを導いた。すなわち、任意のネットワーク状態において、輻輳したＡＰのセットは、単一のＡＰを常に含む（「特性１」）。
【００５３】
ミニマックス負荷平衡化問題の変種を発見した後、次に、本発明者らは、この問題の解を見出す作業に取り掛かった。本発明者らが発見した解は、後段で説明される。
【００５４】
以降の説明を簡単にするのに、本発明によって発見された新たなミニマックス負荷平衡化方法が、前述したＬＫモデルと組み合わせて提示される。とは言え、ミニマックス方法は、ＣＫモデルと組み合わせて使用されることも可能であることを理解されたい。
【００５５】
本発明の或る実施形態において、本発明によって提供されるミニマックス負荷平衡化方法は、最適負荷ベクトルＹ＊をもたらすミニマックス優先度負荷平衡化状態を繰り返し識別する。さらに、任意の回、ｍにおいて、方法は、前述したＬＫ方法／モデル又はＣＫ方法／モデルなどのルーチンを組み込んで、負荷ベクトルの第ｍ番の座標の優先度−負荷を最小限に抑えるネットワーク状態を計算する。本発明によって提供されるミニマックス方法は、次の２つの要件を満たす。すなわち、
（１）各回ｍの初期状態は、最適状態より優勢であるべきで、かつ
（２）第ｍ番の回における計算されたネットワーク状態は、前の回によって既に決定されているＡＰの負荷に影響を与える（増加させる）べきではない。
【００５６】
第１の要件を満たすのに、本発明によって提供される１つのミニマックス方法は、第１回目において最大電力状態で始まり、各回が、最適解の優勢状態で終わることを確実にする。さらに、第２の要件を満たすのに、前の回によって負荷が既に決定されている固定されたＡＰのセットＦが、定義される。初め、セットＦは空である。Ｆが、ＡＰのすべてを含むまで、各回において、新たなＡＰが、セットＦに追加される。輻輳負荷Ｙを、任意の固定されていないＡＰにかかる最大負荷と定義する。特性１から、任意の所与の時点で、輻輳負荷に関連する、輻輳したＡＰと呼ばれる固定されていないＡＰ、ｄが、１つだけが存在することになる。
【００５７】
各回ｍにおいて、ミニマックス方法は、ＬＫ方法（又はＣＫ方法）を呼び出して、負荷ベクトルの第ｍ番の座標を最小限に抑えることが可能である。第１の要件が、繰り返しの始めに満たされているものと想定すると、以下の３つの変数が生成され、格納される。すなわち、（１）それまでに見出された最適状態の輻輳負荷値を示す記録された輻輳負荷Ｙ、（２）輻輳負荷Ｙを有する第１の発見された状態を示す記録された状態変数Ｓ、及び（３）輻輳負荷に関連するＡＰを識別する記録された輻輳ＡＰ、ｄである。
【００５８】
本発明のさらなる実施形態によれば、ミニマックス方法は、変数Ｓ、Ｙ、及びｄをまず初期設定する。次に、方法は、輻輳したＡＰを繰り返し識別し、輻輳したＡＰが、最小電力レベルで既に伝送している場合、停止する。最小電力レベルで伝送していない場合、方法は、輻輳したＡＰの電力レベルを低減し、輻輳負荷、ならびに固定されたＡＰ（すなわち、伝送電力レベルが、前の回に既に計算されているＡＰは、現在、「固定されている」又は設定されている）の負荷を評価する。方法は、固定されたＡＰのいずれかが、高い負荷を被る場合、停止する。このことにより、固定されたＡＰの負荷を保つために、第２の要件が満たされることが確実にされる。さもなければ、より低い輻輳負荷を有する状態が発見された場合、方法は、変数を更新することによって、この状態のレコードを保持する。最後に、方法は、最後に格納された状態（電力レベル）に従ってＡＰの電力レベルを設定することを含み、記録された状態Ｓ、及び対応する輻輳したＡＰｄを戻す。言い換えると、電力レベル低減の後、１つのＡＰの電力レベルが固定になる。このＡＰが、次に、固定されたＡＰのセットに追加される。電力レベルが固定されていない１つ又は複数のＡＰが存在する場合、方法は、別の固定されていないＡＰの電力レベルを計算することによって続く。
【００５９】
方法は、この場合も、第（ｍ＋１）番の座標の負荷を最小限に抑えるためにＬＫ方法／モデル又はＣＫ方法／モデルを含むことが可能である。本発明によって提供されるミニマックス方法を表すソフトウェア・プログラム又はルーチンの例が、図８に示される。以下は、本発明によって提供されるミニマックス方法を実行するコントローラが、どのように実施されることが可能であるかの一例である。
【００６０】
この場合も、図５（ａ）に示されるＷＬＡＮ３０００を考慮されたい。ＬＫ方法の第１回の呼び出しの後、図９（ａ）に示されるネットワーク状態が、生成される。前段で実証されたとおり、この状態は、負荷ベクトルの第１の座標を最小限に抑える他のいずれの状態よりも優勢である。ＬＫ方法の第２回の呼び出しが、このネットワークの唯一のミニマックス負荷平衡化状態である（ＡＰ優先度にかかわらず）、図９（ｂ）に示される状態を生成する。
【００６１】
本発明者らは、本発明によって提供されるミニマックス負荷平衡化方法が、最適負荷ベクトル及びミニマックス負荷平衡化解を常に見出すことを発見した。証明は、前述の場合と同様に、本発明の説明をさらに簡明にするように省略されている。
【００６２】
本発明の他の特徴の説明に移る前に、１つのさらなるポイントが注目に値する。本発明者らによって発見されたミニマックス方法の複雑度は、Ｏ（Ｋ−／Ａ／４−／Ｕ／）であることが（本発明者らによって作成された証明を介して）示されることが可能である（Ｋ、Ａ、及びＵの定義に関しては、表１、行６、行１、及び行１３をそれぞれ参照）。
【００６３】
前述したとおり、本発明によって提供される方法のそれぞれは、コントローラなどによって実行されることが可能である。さらに、ＮＯＣが、前述した方法のいずれか１つを実行すると、ＮＯＣは、ＮＯＣが一部分を成すＷＬＡＮ内の各ＡＰと、それらのＡＰが、本発明によって提供される方法をコントローラが実行した際に生成される電力レベル低減及びユーザ割り当て／関連付け動作を実施することを確実にするために、メッセージ、命令などを交換するようにさらに動作できることが可能である。
【００６４】
とは言え、ユーザが、ＷＬＡＮに到着する、又はＷＬＡＮから離れるたびに、コントローラなどが、前述した最適化方法を実行するよう要求することは、頻繁な関連付け変更、及び進行中のユーザ・セッションの潜在的な妨げにつながる可能性がある。これを回避するのに、本発明者らは、関連付け変更の回数と、最適な負荷平衡化したＷＬＡＮを維持したいという望みとの間の釣り合いをとるオンライン戦略を作成した。そのようなオンライン戦略の基礎をなす概念は、「大域最適化」と「局所最適化」を組み合わせる。
【００６５】
局所最適化は、ＷＬＡＮの負荷が、ユーザが到着する、ならびに／又は出発するたびに絶えず平衡化される戦略であるのに対して、大域最適化は、本発明によって提供される方法が、定期的にだけ呼び出される、又は局所最適化戦略が、負荷平衡化状態を維持するのに失敗した場合には必ず呼び出される戦略を含む。本発明の或る実施形態によれば、オンライン戦略は、以下の３つの構成パラメータ、すなわち、最小負荷閾値、セル適応閾値、及び時間閾値を使用する。最初の２つのパラメータは、局所最適化が、取るに足らない利得しかもたらさない場合に、そのような最適化の使用を防止するため、及びアクティブなユーザに対するサービス割り込みを防止するために、局所最適化をいつ呼び出すかを決定する。最後のパラメータは、大域最適化が、どれだけ頻繁に呼び出されることが可能であるかを制御する。
【００６６】
局所最適化方法は、後段で簡単に説明されるとおり、ＡＰの電力レベルを低減する、又は増加させることが可能であるため、大域最適化方法とは異なる。
【００６７】
本発明によって提供される局所最適化方法において、各ＡＰａに関して、そのＡＰａの近隣のＡＰのすべてのＡＰのセットＮａを定義し、ｙａを、Ｎａの中のＡＰにかかる平均負荷とする。ＡＰａにかかる負荷が、いずれの理由であれ（例えば、ユーザ移動又は局所最適化動作）、低下すると、本発明によって提供されるオンライン方法は、その新たな負荷ｙａが、セル拡大条件を満たすか否かを検査し、この検査は、近隣ＡＰのセットの中のＡＰｂが、最小負荷閾値より大きい負荷を有し、かつ、その新たな負荷ｙａが、Ｎａの中のＡＰの平均負荷に値（１−セル適応閾値）を掛けることによって計算された値より小さい値を有するか否かを判定することである。この条件が満たされ、かつ、ＡＰａの電力インデックスｐａが、最大ではない場合、本発明のオンライン方法は、ＡＰａの電力レベルを１だけ増加させる。
【００６８】
逆に、ＡＰａにかかる負荷が増加した場合、本発明のオンライン方法は、セル縮小条件を検査し、この検査は、ｙａが、最小負荷閾値より大きく、かつ、Ｎａの中のＡＰの平均負荷に値（１＋セル適応閾値）を掛けることによって計算された値より大きいか否かを判定することである。この条件が満たされ、かつ、ＡＰａの電力インデックスｐａが最小ではない場合、オンライン方法は、ＡＰａの電力レベルを１だけ低減する。
【００６９】
最後に、これら２つの条件のいずれかが満たされるが、局所最適化動作が、電力レベルを調整することができない場合、大域最適化が、呼び出される。
【００７０】
本発明者らは、２つの既存の方法、すなわち、ＳＳＦ（Ｓｔｒｏｎｇｅｓｔ−Ｓｉｇｎａｌ−Ｆｉｒｓｔ）方法及び関連付け制御方法に対して、本発明者らの新規の負荷平衡化方法の性能を比較するシミュレーションを行った。ＳＳＦは、ＩＥＥＥ８０２．１１規格において使用されるデフォルトのユーザ−ＡＰ関連付け方法である。関連付け制御方法は、信号強度に単に基づいて関連付けを決定するのではなく、ミニマックス公平帯域幅割り当てを実現するユーザ−ＡＰ関連付けを決定する。ミニマックス公平問題は、ＮＰ困難であるため、関連付け制御方法は、ユーザが、複数のＡＰに同時に関連付けられることが可能であるという想定の下で分数最適解ＦＲＡＣをまず計算し、次に、単一の関連付け制約を満たすように丸めを介して整数解ＩＮＴを獲得する。本発明者らは、本発明者らの解の特性が知られているため、これらの方法をベンチマークとして選択した。
【００７１】
ＦＲＡＣ解は、厳密な性能上限（すなわち、可能な最低の輻輳負荷）をもたらすのに対して、ＩＮＴは、２近似タイプの解を保証する。さらに、ユーザの数が増えるにつれ、ＩＮＴは、ＦＲＡＣと収束する。本発明者らは、本発明者らの方法が、相当に、より高い自由度を有する最適関連付け制御方法より性能が優れているとは予期していなかった。ＩＮＴ解を本発明者らの方法と比較する際の本発明者らの目的は、本発明者らの方法が、ＩＮＴ方法において必要とされる、各移動体上の特別なクライアント・ソフトウェアの必要なしに、関連付け制御方法と同等の性能を実現することを示すことであった。しかし、意外なことに、本発明者らのシミュレーションの結果は、本発明によって提供される方法が、様々な負荷条件においてＩＮＴ解より性能が優れていることを示す。
【００７２】
これらのシミュレーションがどのように行われたかの詳細は、説明を簡明にするために省略されている。代わりに、本発明者らは、本発明者らのシミュレーション結果のサンプルのグラフを含めた。例えば、図１０は、１００名のランダムに分布したユーザを含む、負荷平衡化技術の比較を含むシミュレーション結果を示す。このユーザ数は、アクティブなユーザに対するＡＰの比が、５である、ほどほどに負荷のかかったネットワークをシミュレートするように選択された。Ｙ軸は、ｙａ（ＡＰ負荷）を表すのに対して、Ｘ軸は、ＡＰ電力レベル／インデックスを表す。ＡＰは、ｙａ値が大きい順に並べられることに留意されたい。各ｙａ値は、３００回のシミュレーション実行を平均することによって獲得される。整数ｘインデックスに対応するポイントだけが、意味がある（連続した線は、単に提示の目的で引かれている）。太い実線は、本発明者らのミニマックス方法を表し、細い実線は、本発明者らの最小輻輳方法を表す。両方の方法が、同一の最大ｙａ値を生成するが、ミニマックス方法は、最小輻輳方法と比べて、より低いレキシコグラフ次数を有する負荷ベクトルを生成することを見て取ることができる。太い破線は、ＩＮＴ解を表し、水平の細い破線は、ＦＲＡＣ解を表す。ミニマックス解とＩＮＴ解はともに、ＳＳＦ解よりも明らかに良好である。ミニマックス解とＩＮＴ解はともに、ＦＲＡＣより約３５％高い、非常に似通った最大ｙａ値をもたらす。
【００７３】
また、本発明者らは、５０名のユーザを使用する同様のシミュレーションも実行し、このシミュレーションの結果が、図１１に示される。図示されるとおり、本発明者らのミニマックス方法は、ＩＮＴ方法より大幅に性能が優れている。興味深いことに、ＦＲＡＣ及びＳＳＦと比べると、本発明者らのミニマックス方法の相対的性能は、ユーザの数によってひどく影響を受けているように見えない。同一の傾向は、本発明者らによって行われた他のシミュレーションにおいても観察された。例えば、２００名のユーザ（図示せず）が使用された場合、ＦＲＡＣと本発明者らの方法との格差は、３５％で変わらなかった。ネットワーク負荷条件（すなわち、ユーザの数）にかかわらず、ＦＲＡＣ解と比べた際の、本発明のミニマックス方法の安定した相対的性能は、本発明によって提供される方法の多くの長所の１つである。
【００７４】
また、本発明者らは、不平衡のユーザ分布の事例も考慮した。例えば、ユーザの２０％だけが、ランダムに分布しており、残りのユーザは、互いに重なり合わない２つのホットスポットに集中している。各ホットスポットは、７５メートル半径を有する円形の区域であることが可能である。１つのホットスポットは、他方のホットスポットより２倍多いユーザを含むことが可能である。この状況は、これらのホットスポットにおいて重い負荷条件を生じさせる。図１２は、ユーザの総数が１００名である場合の例示的な結果を示す。図１２は、本発明によって提供されるミニマックス方法が、ホットスポット（すなわち、重い負荷条件）が存在する場合に、さらに良好な性能を示し、ＩＮＴより優れていることを示す。
【００７５】
電力レベルの数（これまで、前述した例は、１０の電力レベルを使用した）の影響を調べるのに、本発明者らは、異なる４つの電力レベル範囲をシミュレートした。結果が、図１３に示される。図示されるとおり、電力レベルの数の影響は、本発明者らによって行われたシミュレーションにおいて５から１０までの間である或る電力レベル数を超えると、取るに足らなくなる。
【００７６】
本発明のＬＫ方法を実行する際に、コントローラが、いくつの動作を実行しなければならない可能性があるかの理解を得るのに、本発明者らは、そのような方法のシミュレーションを実行し、電力レベル調整及びユーザ関連付け変更の回数を数えた。収集された統計が、図１５に示す表ＩＩに要約されている。各テーブルエントリに関して、２つの数が与えられる。つまり、第１の数は、ＬＫ方法を呼び出したミニマックス方法に関するのに対して、第２の数は、ＬＫ（最小輻輳）方法／モデルだけに関する。一般に、ＬＫ方法は、かなり迅速に収束するのに対して、ミニマックス方法は、もう少し長くかかる。例えば、電力調整間隔が、１秒である場合、１００名のランダムなユーザのネットワークにおける負荷平衡化は、ＬＫ（最小輻輳）方法／モデルを使用して、約３３秒かかり、ＬＫ方法を呼び出すミニマックス方法を使用して、２分未満かかる。ユーザの数の増加は、収束時間を必ずしも増大させるように思われず、ホットスポットの存在も、収束時間を増大させるように思われない。実際、ＬＫ（最小輻輳）方法／モデルを使用して、収束時間は、短くなる。
【００７７】
前述した説明は、本発明のいくつかの例を示した。しかし、本発明の真の範囲は、添付の特許請求の範囲によって確定される。
【特許請求の範囲】
【請求項１】
無線ネットワーク内の負荷を平衡化するための方法であって、
該ネットワークにおける１つ又は複数のアクセス・ポイントＡＰによって伝送される１つ又は複数のビーコン・メッセージの電力レベルを変更するステップと、
該ＡＰの１つ又は複数のデータ・トラフィック・チャネルの電力レベルを維持するステップと、
各ＡＰにかかる負荷、及び各ＡＰに割り当てられた１名又は複数名のユーザに関する情報を収集するステップとを含み、
各ＡＰにかかる負荷、及び各ＡＰに割り当てられた１名又は複数名のユーザに関する該情報は、各ＡＰに関する可能な負荷、及び可能なユーザ割り当てに関する情報を含む方法。
【請求項２】
請求項１に記載の方法において、
該ネットワーク内の輻輳したＡＰにかかる負荷を多項式時間内に最小限に抑えるとともに、該ネットワーク内の輻輳していないＡＰにかかる負荷を多項式時間内に平衡化するステップをさらに含む方法。
【請求項３】
請求項１に記載の方法において、
セットの中の各ＡＰが、輻輳負荷を有する輻輳したＡＰである、又は負荷が、電力レベルの低減のために輻輳負荷まで増加する可能性があるＡＰである、該ネットワークにおけるＡＰの最小セットを繰り返し決定するステップと、
該最小セットの中の各ＡＰに関して、該ＡＰに関する最適ビーコン・メッセージ電力レベル設定以上である最大ビーコン・メッセージ電力レベルを決定するステップと、
該最小セットの中の輻輳したＡＰのビーコン・メッセージ電力レベルを、該セットの中の該ＡＰのすべてに関する最適ビーコン・メッセージ電力レベルに達するまで、１回又は複数の回の繰り返しの低減を使用して、該決定された電力レベルから低減するステップと、
ビーコン・メッセージ電力レベルの該セットを該輻輳したＡＰに適用して、輻輳を最小限に抑えるステップとをさらに含む方法。
【請求項４】
請求項２に記載の方法において、
各ＡＰに関して、該ＡＰに関する最適ビーコン・メッセージ電力レベル設定以上であるビーコン・メッセージ最大電力レベルを決定するステップと、
該決定された電力レベルから始めて、該ネットワークにおける、識別されたＡＰの格納されたセットの一部分ではない輻輳したＡＰのビーコン・メッセージ電力レベルを繰り返し低減するステップと、
各回の後、最適電力レベルが決定された１つ又は複数の輻輳したＡＰに関するビーコン・メッセージ電力レベル及びＩＤを格納するとともに、最適電力レベルがまだ決定されていないＡＰから、次の輻輳したＡＰを決定するステップと、
該ＡＰの各ＡＰの最適電力レベルが決定されるまで、次の低減された電力レベルから該繰り返しの低減ステップを繰り返すステップと、
該格納されたビーコン・メッセージ電力レベルを該ＡＰに適用して、輻輳を最小限に抑えるステップとをさらに含む方法。
【請求項５】
請求項１に記載の方法において、
ＡＰにかかる負荷が低減されると、該ＡＰにかかる新たな負荷が、セル拡大条件を満たすか否かを判定し、該条件は、近隣ＡＰのセットの中の近隣ＡＰが、最小負荷閾値より大きい負荷を有し、かつ、該新たな負荷が、該近隣ＡＰのすべてのＡＰの平均負荷に値（１−セル適応閾値）を掛けることによって計算された値より小さい値を有するか否かを判定し、該条件が満たされ、かつ、該ＡＰの電力レベルが調整されることが可能である場合、該ＡＰの該ビーコン・メッセージ電力レベルを増加させるステップ、又は
該ＡＰにかかる該負荷が増加した場合、該新たな負荷が、セル縮小条件を満たすか否かを判定し、該条件は、近隣ＡＰの該セットの中の近隣ＡＰが、該最小負荷閾値より大きく、かつ、該近隣ＡＰのすべてのＡＰの該平均負荷に値（１＋セル適応閾値）を掛けることによって計算された値より大きい負荷を有するか否かを判定し、該セル縮小閾値条件が満たされ、かつ、該ＡＰの電力レベルが調整されることが可能である場合、該ＡＰの該ビーコン・メッセージ電力レベルを低減するステップ、及び
いずれかの条件が満たされるが、該ＡＰの該ビーコン・メッセージ電力レベルが、調整されることが可能でない場合、該ＡＰのデータ・チャネル電力レベルに影響を与えることなしに、該ＷＬＡＮ内の該ＡＰの最適ビーコン・メッセージ電力レベルを決定する全体負荷平衡化最適化方法を呼び出すステップをさらに含む方法。
【請求項１】
無線ネットワーク内の負荷を平衡化するための方法であって、
該ネットワークにおける１つ又は複数のアクセス・ポイントＡＰによって伝送される１つ又は複数のビーコン・メッセージの電力レベルを変更するステップと、
該ＡＰの１つ又は複数のデータ・トラフィック・チャネルの電力レベルを維持するステップと、
各ＡＰにかかる負荷、及び各ＡＰに割り当てられた１名又は複数名のユーザに関する情報を収集するステップとを含み、
各ＡＰにかかる負荷、及び各ＡＰに割り当てられた１名又は複数名のユーザに関する該情報は、各ＡＰに関する可能な負荷、及び可能なユーザ割り当てに関する情報を含む方法。
【請求項２】
請求項１に記載の方法において、
該ネットワーク内の輻輳したＡＰにかかる負荷を多項式時間内に最小限に抑えるとともに、該ネットワーク内の輻輳していないＡＰにかかる負荷を多項式時間内に平衡化するステップをさらに含む方法。
【請求項３】
請求項１に記載の方法において、
セットの中の各ＡＰが、輻輳負荷を有する輻輳したＡＰである、又は負荷が、電力レベルの低減のために輻輳負荷まで増加する可能性があるＡＰである、該ネットワークにおけるＡＰの最小セットを繰り返し決定するステップと、
該最小セットの中の各ＡＰに関して、該ＡＰに関する最適ビーコン・メッセージ電力レベル設定以上である最大ビーコン・メッセージ電力レベルを決定するステップと、
該最小セットの中の輻輳したＡＰのビーコン・メッセージ電力レベルを、該セットの中の該ＡＰのすべてに関する最適ビーコン・メッセージ電力レベルに達するまで、１回又は複数の回の繰り返しの低減を使用して、該決定された電力レベルから低減するステップと、
ビーコン・メッセージ電力レベルの該セットを該輻輳したＡＰに適用して、輻輳を最小限に抑えるステップとをさらに含む方法。
【請求項４】
請求項２に記載の方法において、
各ＡＰに関して、該ＡＰに関する最適ビーコン・メッセージ電力レベル設定以上であるビーコン・メッセージ最大電力レベルを決定するステップと、
該決定された電力レベルから始めて、該ネットワークにおける、識別されたＡＰの格納されたセットの一部分ではない輻輳したＡＰのビーコン・メッセージ電力レベルを繰り返し低減するステップと、
各回の後、最適電力レベルが決定された１つ又は複数の輻輳したＡＰに関するビーコン・メッセージ電力レベル及びＩＤを格納するとともに、最適電力レベルがまだ決定されていないＡＰから、次の輻輳したＡＰを決定するステップと、
該ＡＰの各ＡＰの最適電力レベルが決定されるまで、次の低減された電力レベルから該繰り返しの低減ステップを繰り返すステップと、
該格納されたビーコン・メッセージ電力レベルを該ＡＰに適用して、輻輳を最小限に抑えるステップとをさらに含む方法。
【請求項５】
請求項１に記載の方法において、
ＡＰにかかる負荷が低減されると、該ＡＰにかかる新たな負荷が、セル拡大条件を満たすか否かを判定し、該条件は、近隣ＡＰのセットの中の近隣ＡＰが、最小負荷閾値より大きい負荷を有し、かつ、該新たな負荷が、該近隣ＡＰのすべてのＡＰの平均負荷に値（１−セル適応閾値）を掛けることによって計算された値より小さい値を有するか否かを判定し、該条件が満たされ、かつ、該ＡＰの電力レベルが調整されることが可能である場合、該ＡＰの該ビーコン・メッセージ電力レベルを増加させるステップ、又は
該ＡＰにかかる該負荷が増加した場合、該新たな負荷が、セル縮小条件を満たすか否かを判定し、該条件は、近隣ＡＰの該セットの中の近隣ＡＰが、該最小負荷閾値より大きく、かつ、該近隣ＡＰのすべてのＡＰの該平均負荷に値（１＋セル適応閾値）を掛けることによって計算された値より大きい負荷を有するか否かを判定し、該セル縮小閾値条件が満たされ、かつ、該ＡＰの電力レベルが調整されることが可能である場合、該ＡＰの該ビーコン・メッセージ電力レベルを低減するステップ、及び
いずれかの条件が満たされるが、該ＡＰの該ビーコン・メッセージ電力レベルが、調整されることが可能でない場合、該ＡＰのデータ・チャネル電力レベルに影響を与えることなしに、該ＷＬＡＮ内の該ＡＰの最適ビーコン・メッセージ電力レベルを決定する全体負荷平衡化最適化方法を呼び出すステップをさらに含む方法。
【図１ａ】
【図１ｂ】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図５ｄ】
【図６】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図７ｄ】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１ｂ】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図５ｄ】
【図６】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図７ｄ】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−２４９３３６（Ｐ２０１２−２４９３３６Ａ）
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願番号】特願２０１２−２０２９７５（Ｐ２０１２−２０２９７５）
【出願日】平成２４年９月１４日（２０１２．９．１４）
【分割の表示】特願２００９−５０６５７２（Ｐ２００９−５０６５７２）の分割
【原出願日】平成１９年４月１８日（２００７．４．１８）
【出願人】（５９６０９２６９８）アルカテル−ルーセント ユーエスエー インコーポレーテッド (965)
【Ｆターム（参考）】
【公開日】平成２４年１２月１３日（２０１２．１２．１３）
【国際特許分類】
【出願日】平成２４年９月１４日（２０１２．９．１４）
【分割の表示】特願２００９−５０６５７２（Ｐ２００９−５０６５７２）の分割
【原出願日】平成１９年４月１８日（２００７．４．１８）
【出願人】（５９６０９２６９８）アルカテル−ルーセント ユーエスエー インコーポレーテッド (965)
【Ｆターム（参考）】
[ Back to top ]