(57)【要約】【課題】近似法を使用して妥当な時間内に無線ローカル・エリア・ネットワーク（ＷＬＡＮ）内のアクセス・ポイント（ＡＰ）にチャネルを割り当てるための方法および装置を提供すること。【解決手段】ある近似法は、所与のＷＬＡＮ内のＡＰに関連する干渉パターンが単位円グラフの干渉パターンに一致するならば、チャネル割当て方式が最適なチャネル割当て方式の１／６以上であることを保証する。【選択図】図１
2006109442.tif 000002
【特許請求の範囲】
【請求項１】
無線ローカル・エリア・ネットワーク（ＷＬＡＮ）内でチャネルを割り当てるための方法であって、
実質上互いに干渉する次の順のＡＰと前の順のＡＰに同じチャネルが割り当てられ得ないという条件で、干渉グラフに関連する、順序付けられた１つまたは複数のアクセス・ポイント（ＡＰ）に、使用可能なチャネルの集合のうちからチャネルを割り当てる工程と、
チャネルを割り当てられたすべてのＡＰの重みの和を計算する工程であって、前記計算された和が、最適なチャネル割当てに関連する最大和の近似である工程とを含む方法。
【請求項２】
前記干渉グラフが単位円グラフであるならば、前記計算された和が、前記最大和の１／６以上である請求項１に記載の方法。
【請求項３】
前記ＡＰに割り当てられる重みに基づいて順序付けられたＡＰの代表リストを生成する工程をさらに含み、
より大きい重みをもつＡＰが、より小さい重みに関連するＡＰよりも前記リスト内の高い順序に置かれる請求項１に記載の方法。
【請求項４】
それぞれのＡＰに割り当てられる重みが、
Ｗｎ＝μｎＱｎ（ｔ）によって定義され、
ただし、Ｗｎは各ＡＰに割り当てられる前記重みであり、μｎはアクティブＡＰに一定の伝送速度であり、Ｑｎ（ｔ）は、時間フレームｔの間のアクティブＡＰのキュー・サイズである請求項３に記載の方法。
【請求項５】
無線ローカル・エリア・ネットワーク（ＷＬＡＮ）内でチャネルを割り当てるための装置であって、
実質上互いに干渉する次の順のＡＰと前の順のＡＰに同じチャネルが割り当てられ得ないという条件で、干渉グラフに関連する、順序付けられた１つまたは複数のアクセス・ポイントに、使用可能なチャネルの集合のうちからチャネルを割り当てる工程と、
チャネルを割り当てられたすべてのＡＰの重みの和を計算する工程であって、前記計算された和が、最適なチャネル割当てに関連する最大和の近似である工程とを行うように動作可能である装置。
【請求項６】
前記ＡＰに割り当てられる重みに基づいて順序付けられたＡＰの代表リストを生成する工程をさらに含み、
より大きい重みをもつＡＰが、より小さい重みに関連するＡＰより前記リスト内の高い順序に置かれる請求項５に記載の装置。
【請求項７】
それぞれのＡＰに割り当てられる重みが、
Ｗｎ＝μｎＱｎ（ｔ）によって定義され、
ただし、Ｗｎは各ＡＰに割り当てられる前記重みであり、μｎはアクティブＡＰに一定の伝送速度であり、Ｑｎ（ｔ）は、時間フレームｔの間のアクティブＡＰのキュー・サイズである請求項６に記載の装置。
【請求項８】
Ｖが複数のＡＰを表し、Ｅが、実質上互いに干渉するＡＰによって形成された複数のエッジを表すものとする、干渉グラフＧ（Ｖ，Ｅ）内で表されたいくつかのＡＰにチャネルを割り当てるための装置であって、
使用可能なチャネルの集合を識別する工程と、
２つの異なるチャネルが、前記干渉グラフ内のエッジによって接続されたＡＰのいずれの対にも割り当てられるという条件で、１つまたは複数のＡＰにチャネルを割り当てる工程とを行うように動作可能である装置。
【請求項９】
チャネルを割り当てられたＡＰを識別する工程であって、識別された各ＡＰが重みＷｎに関連付けられる工程と、
前記識別されたＡＰから重みの和を計算する工程とを行うようにさらに動作可能である請求項８に記載の装置。
【請求項１０】
それぞれのＡＰの前記重みＷｎが、
Ｗｎ＝μｎＱｎ（ｔ）によって定義され、
ただし、Ｗｎは各ＡＰに割り当てられる前記重みであり、μｎはアクティブＡＰに一定の伝送速度であり、Ｑｎ（ｔ）は、時間フレームｔの間のアクティブＡＰのキュー・サイズである請求項９に記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
本明細書中で完全に記載されるかのようにその開示が本明細書に組み込まれている米国特許出願第１０／９５３３５５号は、無線ローカル・エリア・ネットワーク（ＷＬＡＮ：wireless local area network）内のアクセス・ポイント（「ＡＰ」：access point）（基地局など）にチャネルを割り当てるための新規な技術を取り入れている。こうした技術は、とりわけ干渉に関する問題を克服している。
【０００２】
しかし、米国特許出願第１０／９５３３５５号で開示された技術を使用して、所与のＡＰに割り当てる特定のチャネルを判断するのに必要な時間は、ＷＡＮがかなりの数のＡＰを含む場合には、指数関数的に増加する（すなわち時間がかかりすぎる）。
【０００３】
【特許文献１】米国特許出願第１０／９５３３５５号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
したがって、妥当な時間内にＷＬＡＮ内のＡＰにチャネルを割り当てるための方法および装置を提供することが望ましい。
【課題を解決するための手段】
【０００５】
チャネル割当てプロセスが、以下でより詳細に論じるあるガイドラインに従うならば、チャネルを割り当てられたＡＰに関連する重みの和を計算することによって、チャネルが妥当な時間内にＷＡＮ内のＡＰに割り当てられ得ることが理解されている。計算される和は、最適なチャネル割当て方式に関連する最大和の近似になる。さらに、所与のＷＡＬＮのＡＰが、単位円グラフ（すなわち特殊なタイプの干渉グラフ）によって表され得る干渉パターンに一致することが証明され得る場合、計算される和は、最適なチャネル割当て方式の予測可能な範囲内（最適なチャネル割当て方式の１／６以上など）にあると言うことができる。
【発明を実施するための最良の形態】
【０００６】
次に図１を参照すると、複数のＡＰ１，２，…Ｎで構成されたＷＬＡＮ１００が示されており、ただし、Ｎは、最後のＡＰであり、ＷＬＡＮ１００内のＡＰの総数を表している。それぞれのＡＰ１，２，…Ｎ間の干渉関係は、図２で示すような干渉グラフによって表され得る。図２で、矢印はＡＰ１，２，…Ｎ間の干渉関係を表しており、だたし、干渉関係は、矢印で接続されたＡＰの対によって同じチャネルを使用する並列伝送を意味することが理解されよう。図１のＷＬＡＮ１００は、ＡＰ１，２，…Ｎ間で割り当てるための所与の３つのチャネルであると仮定する。３つのチャネルだけが与えられると、接続された（したがって干渉する）ＡＰの少なくとも１つの対に同じチャネルを割り当てずに、各ＡＰ１，２，…Ｎにチャネルを割り当てるやり方は存在しないことが当業者には理解されよう。
【０００７】
上記で言及した米国特許出願第１０／９５３３５５号は、チャネルを割り当てるために、干渉（および限られた数のチャネル）に関する問題を克服するための技術を提供している。簡潔に述べると、米国特許出願第１０／９５３３５５号で開示された技術は、時間フレームベースのチャネル割当てアーキテクチャの採用を伴い、このアーキテクチャでは、割当てベクトルを使用して、アクティブＷＡＬＮ  ＡＰの集合を識別する。その後に、それぞれのフレーム内で、１つまたは複数のチャネルが、各アクティブＡＰに割り当てられる。
【０００８】
本発明は、所与のフレーム内でアクティブなＷＬＡＮ  ＡＰだけにチャネルが割り当てられるものとする、類似のフレームベースのチャネル割当てアーキテクチャを採用する。
【０００９】
したがって、本発明の目標は、ネットワーク・オペレータなどが、どのチャネルがどのＡＰに割り当てられるべきかを妥当な間隔内に判断することを可能にする技術を提供することである。次にこの課題に移る。
【００１０】
図１で示したＷＬＡＮ１００のＡＰ１，２，…Ｎは、Ｇ＝（Ｖ，Ｅ）で定義された干渉グラフによって表され得ることを理解することから開始する。だたし、Ｇは干渉グラフを表し、Ｖは、それぞれが頂点と称されるＡＰの集合を表し、Ｅは、頂点の対の間のエッジの集合を表す。エッジは、対の両方の頂点が同じチャネルを使用して送信を試みるときに干渉が引き起こされると判断される場合に、頂点（ＡＰ）の対の間に存在していると言われる。
【００１１】
ほとんどの部分について、本発明は、干渉グラフが他のネットワーク装置、またはネットワーク・オペレータなどによって作成されると仮定する。したがって、特定の干渉グラフＧが与えられると、課題は、各ＡＰ間の干渉関係、限られた数の使用可能なチャネル、およびＡＰの潜在的に大きい数、Ｎを考慮して、妥当な時間内に、こうしたグラフ内に表されるＡＰにチャネルを割り当てることになる。これは、些細なことではなく、困難な課題であることが当業者には理解されよう。
【００１２】
チャネル割当ての問題は、以下の関係によって表され得る。
【数１】
2006109442.tif 000003
【００１３】
ただし、数式（１）で判断されるように、Ｃ＊（ｔ）は時間フレームｔについての最適なチャネル割当てベクトルであり、ｃは任意のチャネル割当てベクトルであり、Ｃはチャネルの実行可能集合であり、Ｕはチャネル割当てベクトルに従ってアクティブ化されるＡＰの集合であり、ｃおよびＷｎは、所与のＡＰ、ｎに割り当てられる重みを表す。数式（１）で参照されるチャネル割当てベクトルｃ、および実行可能集合Ｃについては、以前に出願された、上記で言及した米国特許出願第１０／９５３３５５号でより詳細に定義され、論じられていることに留意されたい。
【００１４】
本発明によれば、Ｗｎは、以下のように定義され得る。
【数２】
2006109442.tif 000004
ただし、μｎは所与のＡＰ、ｎの一定の伝送速度であり、Ｑｎ（ｔ）は、時間フレームｔの間のＡＰ、ｎのパケット・キューのサイズである。
【００１５】
本発明によれば、課題は、ＡＰ干渉の結果、および割当てに使用可能な限られた数のチャネルとして課されたある制約に従いながら、アクティブなＡＰの集合を判断し、妥当な時間内にすべてのアクティブＡＰにチャネルを割り当てるために、数式（１）を解くことになる。
【００１６】
続ける前に、発明人は、数式（１）および（２）を立証するために証明を策定したことに留意されたい。当業者はこうした証明なしに本発明を理解し実施することができるので、それは省略してある。また省略することによって、本明細書での議論を集中し、議論を追い、理解することがより容易になることが望まれる。
【００１７】
本発明によれば、本発明人は、数式（１）および（２）において、最大和ΣＷｎを近似するための技術を発見した。
【００１８】
以下でより詳細に論じるように、本発明人は、すべてのアクティブＡＰ（チャネルを割り当てられたＡＰ）の計算された重みの和が最大和ΣＷｎの近似となる、近似法（approximation technique）を発見した。さらに、本発明人は、ＷＬＡＮを構成する所与のＡＰの集合が、単位円グラフとして知られる特殊な干渉パターンに一致するならば、そのようにして計算された和は、最大和（ΣＷｎ）の１／６以上であるものとして信頼され得ることを発見した。すなわち、後者の場合では、本発明人によって発見された技術は、ＡＰにチャネルを割り当てるために使用される場合に、割当て方式が最適なチャネル割当てのある範囲内にあることをネットワーク・オペレータに対して保証する和を計算する。ネットワーク・オペレータによっては、これをある種の保証と見なすことができ、すなわち本発明の技術は、特殊なＡＰ干渉パターンが単位円グラフに一致するならば、最適な割当て方式のある範囲内にあるチャネル割当てを作成することが保証され得る。
【００１９】
最大和ΣＷｎを近似するために、本発明人は、各ＡＰに重みが割り当てられ、干渉ＡＰがエッジＥによって接続されるものとする、ＡＰ（すなわち頂点）Ｖを含む干渉グラフＧ（Ｖ，Ｅ）が、その近似を得るのに重要であることを発見した。
【００２０】
本発明によれば、割り当てられる任意のチャネルは、使用可能なチャネル１，２，…Ｆの限られた集合のうちから選択されると仮定する。
【００２１】
この近似法がＡＰ間の干渉を確実に考慮するように、本発明は、エッジの一部である２つのＡＰに同じチャネルが割り当てられ得ないことをも必須とする。別の言い方をすると、本発明は、同じチャネルが、実質上干渉している２つのＡＰに割り当てられることを認めない。
【００２２】
これら２つのガイドラインに留意して、本発明人は、妥当な時間内にＷＬＡＮのチャネルを割り当てるために、「欲張りヒューリスティック（Greedy Heuristic）」近似法として知られるものを導出した。
【００２３】
本発明の一実施形態では、所与の干渉グラフ内のアクティブＡＰすなわち頂点は、アクティブ化集合Ｕを形成する。一般に、このアクティブ化集合は、上述のガイドラインを使用することによってチャネルが割り当てられ得るすべてのＡＰの集合を表す。
【００２４】
より具体的には、本発明の最初のステップとして、ＡＰに割り当てられる重みに基づいて、順序付けられたＡＰの代表リストが生成される。概念的には、本発明は、最大の重みをもつＡＰから最小の重みをもつＡＰへと進む代表リスト内の各ＡＰにチャネルを割り当てる試みを伴う。たとえば、図２に戻って参照すると、ＡＰ１に１０の重みが割り当てられ、ＡＰ２に２０の重みが割り当てられ、ＡＰ３に３０の重みが割り当てられ…ＡＰ  Ｎに１０Ｎの重みが割り当てられるならば、順序付けられたＡＰの代表リストは、割り当てられるその重みに基づく順序で置かれたＡＰ１，２…Ｎを含む。たとえば、１０Ｎが最大の重みであり、１０が最小の重みであるので、代表リストは、最大の重み（すなわち１０Ｎ）をもつＡＰ  Ｎを第１のエントリ（最高順位）に置き、その後に、次に最も大きい重みに関連するノードが続くなどとなる。このプロセスは、最小の重みをもつＡＰ、ＡＰ１が順位の最後に置かれるまで続く。要するに、代表リストは、減少する重みの順序で配列された、順序付けられたＡＰの集合で構成される。
【００２５】
こうした順序リストを生成した後に、本発明は、そのように順序付けられた１つまたは複数のＡＰに、使用可能なチャネルの集合のうちから１つのチャネルを割り当てようと試みるが、しかし、その次の順のＡＰと前の順のＡＰが互いに干渉する場合、同じチャネルが次の順のＡＰに割り当てられ得ないことに留意する。たとえば、チャネル番号１が図２のＡＰ  Ｎに割り当てられる場合、ＡＰ  Ｎおよび５は接続されて、それらが実質上互いに干渉することを示すエッジを形成しているので、次に最も高いＡＰ、ＡＰ５には、別のチャネルが割り当てられなければならない。したがって、本発明によれば、別のチャネルが、ＡＰ５に割り当てられなければならない。これは、別のチャネルを割当てに使用できると仮定している。割当てに使用できるチャネルがない場合は、チャネルは、ＡＰ５に割り当てられない。
【００２６】
要するに、チャネルは、２つの異なるチャネルが、干渉グラフ内のエッジによって接続されたＡＰのいずれの対（ＡＰ  ＮおよびＡＰ５など）にも割り当てられるように、順序リスト内のＡＰに割り当てられる。
【００２７】
チャネル割当ての試みが行われるたびに、上記で論じたエッジまたは干渉のガイドラインが適用されなければならない。
【００２８】
ある時点で、すべてのＡＰへのチャネル割当てを試みるプロセスが完了する。その後、本発明は、次いで、そのようにチャネルが割り当てられたＡＰを識別する。こうしたＡＰは、アクティブ集合Ｕを構成する。アクティブ集合Ｕが識別されると、次いで、本発明は、アクティブ集合（すなわちチャネルが割り当てられたＡＰ）の一部と識別されたＡＰに関連するすべての重みの和を計算する。
【００２９】
結果としてもたらされる、アクティブ集合ＵをもつＡＰのすべての重みの和は、数式（１）によって与えられる、最適なチャネル割当てに関連する最大和ΣＷｎの近似を表す。
【００３０】
ここで論じた技術によって、チャネル割当てに到達するために使用され得る最大和の近似がもたらされるが、本発明人は、こうした近似によってもたらされるチャネル割当てが最適なチャネル割当てのある範囲内にあることのある種の保証をネットワーク・オペレータなどに提供することが非常に望ましいと認識した。
【００３１】
このために、本発明人は、所与のＷＬＡＮのＡＰが、単位円グラフとして知られる特殊化された干渉グラフに一致する場合、上記で論じた計算値は、最大和ΣＷｎの１／６以上であることが保証され得ることを発見した。
【００３２】
用語単位円グラフは当業者には周知であり得るが、読者の利益のため、単位円グラフを、頂点およびエッジからなる干渉グラフとして定義し、ただし、（ａ）単位距離内に置かれたいずれの２つの頂点もがエッジによって接続されなければならず、（ｂ）単位距離より大きい距離によって分離された頂点のいずれの対もがそのように接続されるべきでない。完全にするために、頂点がエッジによって接続されるべきかどうか判断する際に用いられる「単位距離」は、定義の問題であることを理解されたい。すなわち、単位距離は、（ＡＰの集合に有効な干渉範囲によって決定され得る）任意の所望の距離であると定義され得る。
【００３３】
要するに、特定のＷＬＡＮを表す干渉グラフが単位円グラフに一致する場合、上記で論じた計算された和は、ある範囲内、この場合は最適チャネル割当て方式の１／６以上であることが保証されたチャネル割当て方式の提供のために信頼され得る。
【００３４】
上記議論は、数式（１）によって提供される、チャネル割当て問題の解を近似するための方法およびプロセスに焦点を当てた。こうした方法およびプロセスは、図１に示したコントローラ１０１などの１つまたは複数の装置で実施され得ることを理解されたい。すなわち、コントローラ１０１は、最適なチャネル割当て方式を近似するチャネル割当て方式、または最適なチャネル割当て方式の１／６以上であることが保証された近似方式を保証するチャネル割当て方式を作成するために、上記で論じた諸ステップのそれぞれを実施するように動作可能であり得る。コントローラ１０１はＡＰ１，２…Ｎとは別個のものとして示されているが、本発明の代替実施形態では、このコントローラは、ＡＰのうちの１つまたは複数のうちに含まれ、またはＡＰ１，２…Ｎのうちの１つまたは複数のＡＰの隣に一緒に置かれ得る。ＡＰ１，２…Ｎが基地局を含む場合、コントローラ１０１は、基地局コントローラを含み得る。
【００３５】
上記議論では、本発明のいくつかの例を示すことを試みている。しかし、本発明の真の範囲は、特許請求の範囲によって提供される。
【図面の簡単な説明】
【００３６】
【図１】ＷＡＮを構成する複数のＡＰを示す図である。
【図２】図１のＡＰに関連する干渉グラフの一例を示す図である。
【図１】
2006109442.tif 000005
【図２】
2006109442.tif 000006