(57)【要約】【課題】本方法は、基地局（ＢＳ）のセットと、移動局（ＭＳ）のセットとを含むＯＦＤＭＡネットワークにおいて無線チャネル資源を配分する。【解決手段】ＢＳ毎に、ＭＳのセットに関するダイバーシティセットを保持する。各ＢＳは、ダイバーシティセットに基づいて、ＭＳにおける起こり得る干渉を求める。グラフが構築され、該グラフにおいて、ノードはＭＳのセットを表し、ノード対間の各エッジは、ノード対によって表されるＭＳ間のチャネル干渉を表す。各エッジに、該エッジによって接続される２つのＭＳ間の干渉を反映する重みを割り当てる。干渉グラフの構造、すなわち起こり得る干渉に基づいて、該干渉グラフを、各クラスタ間のエッジ重みの合計が最大になるように、ノードの複数の重複しないクラスタに分割する。このグラフ分割に基づいて、チャネル資源を移動局に割り当てる。【選択図】図１
2011509537.tif 000002
【特許請求の範囲】
【請求項１】
基地局のセット及び基地局毎の移動局のセットを含む直交周波数分割多元接続ネットワークにおいてチャネル資源を配分するための方法であって、
干渉グラフ内のノードが前記直交周波数分割多元接続ネットワーク内の移動局を表すとともに、ノード対間の各エッジが、ノード対によって表される移動局間の起こり得る干渉を表す、干渉グラフを構築するステップと、
前記干渉グラフを、ノードの複数の重複しないクラスタに分割するステップと、
前記分割された干渉グラフの構造、前記起こり得る干渉、及びチャネル品質に基づいて、前記移動局に前記チャネル資源を配分するステップと
を含む、直交周波数分割多元接続ネットワークにおいてチャネル資源を配分するための方法。
【請求項２】
ダイバーシティセットが、前記移動局のためのアンカー基地局及び任意の隣接する基地局を示し、前記干渉グラフの構造及び起こり得る干渉が、前記ダイバーシティセットに基づき、移動局毎にダイバーシティセットを保持するステップをさらに含む
請求項１記載の方法。
【請求項３】
重みが前記起こり得る干渉に比例し、重みを各エッジに割り当てるステップをさらに含む
請求項１記載の方法。
【請求項４】
前記直交周波数分割多元接続ネットワークの周波数再利用係数は１である
請求項１記載の方法。
【請求項５】
前記チャネル資源はセル間干渉調整に従って配分され、この配分されるチャネル資源は別個である
請求項１記載の方法。
【請求項６】
前記チャネル資源は基地局協調に従って配分され、この配分されるチャネル資源は共有される
請求項１記載の方法。
【請求項７】
前記基地局協調は空間分割多元接続を使用する
請求項６記載の方法。
【請求項８】
前記分割するステップは最大ｋ切断プロセスを使用し、各クラスタ間の前記エッジの重みの合計が最大にされる
請求項１記載の方法。
【請求項９】
特定のクラスタ内のノードによって表される前記移動局は同じチャネル資源を配分され、隣接するクラスタ内のノードによって表される前記移動局は異なるチャネル資源を配分される
請求項８記載の方法。
【請求項１０】
ノードａ及びノードｂ間のエッジに対する重みｗａｂは、起こり得る干渉を表す
請求項３記載の方法。
【請求項１１】
前記重みは、
ｗＢ，ｗＳ，ｗＮ，ｗ０，ｗ１，ｗ２，ｗＡ
から選択され、ここで、重みｗＢは基地局協調に関連付けられる重みに対応し、ｗＳは空間分割多元接続に関連付けられる重みに対応し、ｗＮは非干渉に関連付けられる重みに対応し、ｗＡはセル内干渉に関連付けられる重みに対応し、ｗ０，ｗ１，及びｗ２は、前記ノードによって表される前記移動局の地理的ロケーションに依拠する複数の干渉レベルにおけるセル間干渉重みである
請求項３記載の方法。
【請求項１２】
前記重みは、
ｗＢ≒ｗＳ＜＜ｗＮ＜ｗ０＜ｗ１＜ｗ２＜＜ｗＡ
のようにランク付けされる
請求項１１記載の方法。
【請求項１３】
前記重みは、
（ｗＢ，ｗＳ，ｗＮ，ｗ０，ｗ１，ｗ２，ｗＡ）＝（−１０３，−１０３＋５０，０，５０，１００，２００，１０５）
である
請求項１２記載の方法。
【請求項１４】
前記重みｗａｂは、
ｗＢ，ｗＳ，ｗＮ，ｗ０，ｗ１，ｗ２，ｗＡ
から選択される
請求項１０記載の方法。
【請求項１５】
前記直交周波数分割多元接続ネットワークにおいて全ての隣接する基地局間で前記ダイバーシティセットを交換するステップをさらに含む
請求項２記載の方法。
【請求項１６】
前記直交周波数分割多元接続ネットワークはＭ個の移動局を含み、
任意に選択されたＮ個のノードを、各クラスタに１つずつ、Ｎ個のクラスタに割り当てるステップと、
（Ｍ−Ｎ）個のノードを、クラスタ内重みの増加が最小になるように前記クラスタに反復的に割り当てるステップとをさらに含む
請求項９記載の方法。
【請求項１７】
前記クラスタを、クラスタサイズの昇順で配列するステップと、
前記チャネル資源を、配分されるチャネル資源の合計容量が前記クラスタに関して最大になるように、前記クラスタ内のノードによって表される移動局に昇順で配分するステップとをさらに含む
請求項１記載の方法。
【請求項１８】
各基地局において、前記ダイバーシティセットに基づいて、前記基地局によってサービス提供される移動局のセットが、空間分割多元接続を実施することができるか否かを判断するステップと、
各基地局において、前記ダイバーシティセットに基づいて、前記基地局によってサービス提供される前記移動局のセットが、基地局協調を実施することができるか否かを判断するステップと、
各基地局において、前記ダイバーシティセット情報に基づいて、前記基地局によってサービス提供される移動局のセットが、隣接する基地局によってサービス提供される前記移動局のセットにおいてセル間干渉を引き起こすか否かを判断するステップと、
各基地局において、前記基地局によってサービス提供される移動局が、前記基地局によってサービス提供される移動局のセットにおいてセル内干渉を引き起こすか否かを判断するステップとをさらに含む
請求項２記載の方法。
【請求項１９】
セル内干渉によって引き起こされる干渉に関して前記干渉グラフ内の全てのサブチャネルに関連付けられる固有のエッジ重みを割り当てるステップと、
セル間干渉によって引き起こされる干渉に関して前記干渉グラフ内の全てのサブチャネルに関連付けられる固有のエッジ重みを割り当てるステップと、
空間分割多元接続によって引き起こされる干渉に関して前記干渉グラフ内の全てのサブチャネルに関連付けられる固有のエッジ重みを割り当てるステップと、
基地局協調によって引き起こされる干渉に関して前記干渉グラフ内の全てのサブチャネルに関連付けられる固有のエッジ重みを割り当てるステップとをさらに含む
請求項１７記載の方法。
【請求項２０】
前記チャネル資源を、前記直交周波数分割多元接続ネットワークの合計容量が最大になるように各クラスタに配分するステップをさらに含む
請求項１記載の方法。
【請求項２１】
前記チャネル資源を各クラスタにランダムに配分するステップをさらに含む
請求項１記載の方法。
【請求項２２】
基地局のセットと、
基地局毎の移動局のセットと、
前記移動局のセットに関するダイバーシティセットを保持する手段と、
前記ダイバーシティセットを使用して干渉グラフを構築する手段であって、前記干渉グラフ内のノードは前記移動局を表し、ノード対間の各エッジは、起こり得る干渉と、前記ノード対によって表される移動局によって使用されるチャネルに関するチャネル品質とを表し、前記起こり得る干渉及びチャネル品質に基づいて、各エッジに重みが割り当てられる、構築する手段と、
前記干渉グラフを、ノードの複数の重複しないクラスタに分割する手段と、
分割された前記干渉グラフの構造、前記起こり得る干渉、及び前記チャネル品質に基づいて、前記移動局にチャネル資源を配分する手段と
を備える直交周波数分割多元接続ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には無線ネットワークにおける資源配分に関し、より詳細には直交周波数分割多元接続セルラネットワークにおける、グラフベースの手法を使用する資源配分に関するものである。
【背景技術】
【０００２】
ＯＦＤＭＡ
直交周波数分割多重（ＯＦＤＭ）は、多数の無線ネットワーク、たとえば既知のＩＥＥＥ８０２．１１ａ／ｇ標準規格及びＩＥＥＥ８０２．１６／１６ｅ標準規格に従って設計されたネットワークの物理層（ＰＨＹ）において使用される変調技法である。直交周波数分割多元接続（ＯＦＤＭＡ）は、ＯＦＤＭに基づく多元接続方式である。ＯＦＤＭＡでは、直交トーン（サブチャネル）の別個のセット及びタイムスロットが、複数の送受信機（ユーザ又は移動局）に配分され、それによって複数の送受信機が同時に通信することができる。ＯＦＤＭＡは、無線資源配分におけるその効率性及び柔軟性に起因して、３ＧＰＰロングタームエボリューション（ＬＴＥ）及びＩＥＥＥ８０２．１６ｍのような多数の次世代セルラネットワークにおいて広範に採用されている。
【０００３】
ＯＦＤＭＡ資源配分
無線スペクトルは、無線通信における乏しい資源であり、したがって、無線スペクトルの効率的な使用が必要とされている。無線用途及び加入者ユーザの急速な増加により、ネットワーク容量を増大させることができると共に、商業的観点からは配備コストを節約することができる良好な無線資源管理（ＲＲＭ）方式が求められている。その結果、ＯＦＤＭＡのための効果的な無線資源配分方式を開発することが産業にとって重大な関心事となっている。
【０００４】
資源配分における基本的な課題は、利用可能な乏しいスペクトルと、カバーされるべき広大なエリア及びサービス提供されるべき多数のユーザとが不均衡であることである。換言すれば、同じ周波数スペクトルが、複数の地理的エリア又はセル内で再利用されなくてはならない。これによって、隣接するセル内のユーザ又は移動局（ＭＳ）が同じスペクトルを使用するとき、不可避的にセル間干渉（ＩＣＩ）が生じる。実際、ＩＣＩは無線セルラネットワークに対する主要な性能制限要因であることがわかっている。結果として、セルラネットワークのための、ＩＣＩを意識した無線資源配分を開発することに非常に多くのの研究が充てられてきた。
【０００５】
スペクトル効率を最大にするために、ＯＦＤＭＡセル配置では、周波数再利用係数１が使用される。すなわち、同じスペクトルがあらゆるセルにおいて再利用される。不都合なことに、この高いスペクトル効率には不利な高いＩＣＩも伴う。したがって、ＯＦＤＭＡ技術を活用するために、ＯＦＤＭＡの上位における良好なＩＣＩ管理方式が必要とされる。
【０００６】
ＯＦＤＭＡ資源配分は、単一セルのケースに関して広く研究されてきた。既存の方法のほとんどは、各ＭＳがセル内干渉を回避するために異なるサブチャネル（複数可）を使用するという想定の下での電力又はスループットの最適化に焦点を当てている。単一セル資源配分における別の主要な想定は、基地局（ＢＳ）は、自身と全てのＭＳとの間のリンクのチャネル信号対雑音比（ＳＮＲ）の完全な知識を有するということである。ダウンリンク（すなわちＢＳからＭＳへの送信）において、このＳＮＲは、標準的にはＭＳによって推定され、ＢＳにフィードバックされる。アップリンク（すなわちＭＳからＢＳへの送信）において、ＢＳは、全てのＭＳから受信する信号に基づいて、ＳＮＲを直接推定することができる。しかしながら、マルチセルシナリオにおける相当物、すなわち信号対干渉雑音比（ＳＩＮＲ）は、干渉が複数のセルから到来する可能性があり、資源配分前には知られていない、干渉物の距離、ロケーション、占有チャネル状態のような様々な要因に依拠するため、取得するのがより難しい。この結果、ＩＣＩの相互依存が生じ、資源配分問題が複雑になる。このため、ＳＩＮＲの大域的で完全な知識を必要としない実用的なマルチセル資源配分方式が非常に望ましい。
【０００７】
セル間干渉調整（ＩＣＩＣ）
ＩＣＩＣは、セルエッジ領域内のＩＣＩを効率的に低減することができる技法である。ＩＣＩＣは、異なるセルに属する複数のセルエッジＭＳに、別個のチャネル資源を配分することによって達成される。セルエッジＭＳは高ＩＣＩの傾向が非常に強いため、セルエッジＭＳ間でチャネル配分を適切に調整することによって総ＩＣＩを大幅に低減することができる。より具体的には、ＩＣＩＣは、干渉物の数及び／又は各干渉物が発生させる「損害」を低減する。各干渉物が発生させる「損害」の低減は、たとえば、地理的に遠く離れたＭＳに同じ資源を配分し、経路損失に起因して干渉が緩和されるようにすることによって達成することができる。
【０００８】
しかしながら、セルエッジユーザに関する資源衝突を回避することにのみ基づくＩＣＩＣは、ダウンリンク通信において、限定的な性能利得しか提供することができない。これは、ＢＳからセル中央ＭＳへの送信によって引き起こされる干渉を見過ごしているためである。本発明の実施の形態は、セル中央もセルエッジも一様に、全てのＭＳがＩＣＩ管理の考慮に入れられる、総体的なチャネル配分方式を提案することを目的としている。
【０００９】
空間分割多元接続（ＳＤＭＡ）
ＳＤＭＡは、プレコーディング及びマルチユーザスケジューリングを用いて多入力多出力（ＭＩＭＯ）技法を使用することによって、マルチユーザチャネル接続を提供する。ＳＤＭＡはセル内のＭＳのロケーションの空間情報を利用する。ＳＤＭＡによって、信号の放射パターンは、特定の方向において最も高い利得を得るようになっている。これは、ビーム形成又はビームステアリングと呼ばれることが多い。ＳＤＭＡをサポートするＢＳは、同じ資源を使用して、複数のユーザに同時に信号を送信する。このため、ＳＤＭＡはネットワーク容量を増大させることができる。
【００１０】
基地局協調（ＢＳＣ）
基地局協調（ＢＳＣ）によって、複数のＢＳが、同じ資源（すなわち時間及び周波数）を共有して、複数のＭＳに同時に信号を送信することが可能になる。ＢＳＣは、ＢＳがＭＳに信号を協調して送信するためにＳＤＭＡ技法を利用し、特に、複数のＢＳの送信範囲内にあるセルエッジＭＳにおいて使用される。協調によって、干渉信号は有用な信号の一部となる。したがって、ＢＳＣは２つの利点、すなわち空間ダイバーシティの提供及びＩＣＩ削減を有する。
【００１１】
ダイバーシティセット
通常、各ＭＳはアンカー（又はサービング）ＢＳと呼ばれる１つのＢＳにおいて登録され、該ＢＳと通信する。しかしながら、ハンドオーバのような幾つかのシナリオにおいて、ＭＳは複数のＢＳと同時に通信することができる。ダイバーシティセットは、この目的に適うようにＩＥＥＥ８０２．１６ｅ標準規格において定義されている。ダイバーシティセットはアンカーＢＳ及びＭＳの通信範囲内にある近隣のＢＳを追跡する。ダイバーシティセット内の情報はＭＳ及びＢＳにおいて維持及び更新され、本発明のグラフベースの方法において使用される。
【００１２】
従来のチャネル配分におけるグラフベースのフレームワーク
従来の（非ＯＦＤＭＡ）セルラネットワーク及びメッシュネットワークにおけるチャネル配分問題は、グラフ彩色手法を使用して解決されてきた。従来の問題の定式化において、グラフ内の各ノードは、チャネルが配分されるネットワーク内のＢＳ又はアクセスポイント（ＡＰ）に対応する。２つのノードを接続するエッジは起こり得る同一チャネル干渉を表す。これは通常、ＢＳの地理的近接性に対応する。このため、干渉制約を守るチャネル配分問題は、ノード彩色問題となり、ここで干渉する２つのノードは同じ色を有してはならず、すなわち同じチャネルを使用してはならない。
【００１３】
従来のネットワークにおいて、２つの隣接する基地局が、同じスペクトルを使用して同じ時刻に送信する場合、それらの基地局はＭＳにおいて互いに干渉を引き起こす。このため、従来のグラフにおいて、必要とされているのは、ＢＳを表す隣接するノードが異なる色を有することのみである。
【００１４】
この解決策は、周波数再利用係数が１であり、全てのＢＳが同じスペクトルを使用するＯＦＤＭＡネットワークに適用可能である。さらに、従来のグラフは、上記で説明したようなＩＣＩＣ及びＢＳＣのような技術を考慮していない。
【発明の概要】
【００１５】
本発明の実施の形態は、グラフベースの手法を使用する、実用的で低複雑度のマルチセルＯＦＤＭＡダウンリンクチャネル配分方法を提供する。グラフベースの手法は、２つの基本的態様において従来技術と異なる。
【００１６】
第１に、従来技術は、干渉制約の下で、使用されるサブチャネル数を最小にするのに対し、本発明は、ＯＦＤＭＡネットワークにおいて自由に固定且つ所定数のサブチャネルを使用する。干渉を完全に回避することは物理的に実現可能でないため、適切で良好に管理された妥協策が検討される。
【００１７】
第２に、本発明のケースのグラフ内のノードは、ＢＳではなくＭＳを指すべきである。これは、ＯＦＤＭＡネットワークにおいてチャネルを配分されるのは、ＢＳではなくＭＳであるためである。さらに、ＭＳのロケーション及び移動によって干渉ダイナミクスが変化し、その結果グラフが変化する。従来技術のグラフでは、グラフ内のノードによって表される基地局は固定であり、このため局の移動は問題ではなく、問題を解くのが比較的簡単である。
【００１８】
本方法は２つのフェーズ、すなわち
１）スケールの粗い干渉管理方式と、
２）スケールの細かいチャネル配分方式と、
を含む。
【００１９】
第１のフェーズにおいて、干渉管理はグラフベースのフレームワークを使用して実施される。干渉情報は、ＢＳ及びＭＳにおいて保持されるダイバーシティセットに基づき、干渉グラフの形式で提示される。次に、グラフは、ＩＣＩＣ及びＢＳＣのような干渉管理基準に従って、重複しない複数のクラスタに分割される。このフェーズにおいて、ＩＣＩＣ技法、ＢＳＣ技法、及びＳＤＭＡ技法は全てフレームワーク内に組み込まれ、正確なＳＩＮＲ情報は一切必要とされない。
【００２０】
第２のフェーズにおいて、第１のフェーズにおいて取得されたクラスタに、ランダムに、又は瞬時チャネル状態を考慮してサブチャネルを配分することによって、資源配分が実施される。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態による、直交周波数分割多元接続（ＯＦＤＭＡ）ネットワークにおいてチャネル資源を配分するための方法のフローチャートである。
【図２Ａ】本発明の実施の形態による、隣接するセルにおいて実施されるＩＣＩＣスペクトル配分、並びに２つのＭＳ及び２つのＢＳを用いた例示的なＩＣＩＣシナリオの概略図である。
【図２Ｂ】本発明の実施の形態による、隣接するセルにおいて実施されるＢＳＣスペクトル配分、並びに２つのＭＳ及び２つのＢＳを用いた例示的なＢＳＣシナリオの概略図である。
【図３】本発明の実施の形態によるマルチセルネットワークの概略図である。
【図４】本発明の一実施の形態による、マルチセル、マルチ送受信機のシナリオに関して構築される干渉グラフである。
【図５】本発明の一実施の形態によるダイバーシティセットの表である。
【図６】本発明の一実施の形態による、図４における干渉に関連するエッジ重みを求める方法のフローチャートである。
【図７】図６における方法に基づいて割り当てられるエッジ重みを有する干渉グラフである。
【図８】本発明の実施の形態による、干渉管理の第１のフェーズにおいて使用される方法のフローチャートである。
【図９】本発明の実施の形態による、第２のフェーズのＳＮＲを意識したチャネル配分問題において使用される方法のフローチャートである。
【図１０】従来の配分方法と、本発明による配分方法を比較するグラフである。
【発明を実施するための形態】
【００２２】
グラフベースのＯＦＤＭＡ資源配分
図１は、本発明の実施の形態による、直交周波数分割多重（ＯＦＤＭ）ネットワークにおいて移動局に資源を配分するための方法を示している。ＯＦＤＭＡネットワークは、複数の基地局（ＢＳ）と、複数の移動局（ＭＳ）とを含む。
【００２３】
干渉グラフ１０１を構築する（１１０）。グラフにおいて、ノード１５０はＭＳを表し、ノードを接続するエッジ１５１は、エッジによって接続されるノードによって表される移動局間の起こり得る干渉、及び移動局によって使用されるチャネルの品質を表す。
【００２４】
干渉グラフは、ＯＦＤＭＡネットワーク内のＢＳ及びＭＳによって保持されるダイバーシティセット１０２を使用して構築される。各ＢＳはＭＳのセットに関するダイバーシティセットを保持することができ、ＢＳによってサービス提供される全てのダイバーシティセットの知識を有する。ＢＳは、全てのＢＳが全てのダイバーシティセットを有するように、ダイバーシティセットを交換することができ、ＭＳは自身が関連付けられる基地局に関するダイバーシティセットを保持することができる。
【００２５】
ＭＳにおける起こり得る干渉は、対応する確立されたダイバーシティセットに基づく。適切な重み割当て１０４を使用して、干渉グラフ内のエッジを構築する。エッジはＭＳ（ノード）間の干渉を表す。可能な重み１０５を、下記でより詳細に説明する。
【００２６】
干渉管理１２０は、干渉グラフ１０１を使用して実施される。発見的方法は、グラフを複数の別個のクラスタに分割するようになっている。
【００２７】
チャネル割当て１３０は、チャネル資源１３１情報を使用して、グラフのクラスタリング後に遂行される。サブチャネルがクラスタに割り当てられ、同じクラスタ内のノード（ＭＳ）は同じサブチャネルを割り当てられる。割当ては、ランダムに行ってもよく、又は割当てにおける瞬時チャネル情報を考慮してオポチュニスティックに行ってもよい。
【００２８】
スペクトル配分
図２Ａ及び図２Ｂは、本発明の実施の形態において説明される、ＯＦＤＭＡマルチセルネットワークのためのスペクトル配分を示している。７つのセルが示されている。これは、より多くのセルに容易に一般化することができる。周波数再利用係数は１である。すなわち、各セルがネットワーク帯域幅全体を使用する。各セルは、セル中央領域及びセル境界領域に地理的に分割され、境界領域は３つのセクタにさらに分けられる。
【００２９】
図２Ａ及び図２Ｂにおいて、Ａｉ、Ｂｉ、及びＣｉは、それぞれ境界領域内の３つのセクタを指し、Ｄｉはセル中央を指す。ただし、ｉ＝１，．．．，７である。図２Ａ及び図２Ｂに示すセクタ分割（sectorization）は、地理的領域の観点からの資源配分の概念を説明するための役割しかなく、限定的ではないことに留意されたい。図において、同じ網掛けを有するセクタ内のチャネルは同じ資源、たとえば周波数サブチャネルを共有し、したがって、互いに干渉する可能性があり得る。
【００３０】
セル中央は隣接するセルからより遠くにあり、したがって、ＢＳからセル中央ＭＳへの送信が、隣接するセル内のＭＳに対して引き起こすＩＣＩは、より少ないことに留意されたい。対照的に、セル境界は隣接するセルにより近く、このため、ＢＳから境界ＭＳへの送信は、通常、隣接するセル内のＭＳに対して、より強い干渉を引き起こす（と共に、より強い干渉を受ける）。換言すれば、境界領域における資源配分は、ＩＣＩを緩和することができるように、より注意深く管理されるべきである。これは、境界の計画を、ＩＣＩＣ又はＢＳＣのような干渉管理方式と組み合わせて実施することによって達成することができる。
【００３１】
ＩＣＩＣシナリオ
ＩＣＩＣは、異なるセルに属する境界ＭＳに別個のチャネル資源を配分することによって達成される。これは、図２Ａにおいて異なる複数の網掛けパターンによって示されている。ここで、隣接するＢ１セクタ及びＢ２セクタ内にそれぞれ位置するＭＳ１及びＭＳ２に、重複しないスペクトルが配分される。したがって、ダウンリンク信号によって互いに引き起こされる、起こり得る干渉を回避することができる。通常、ＩＣＩＣは、干渉を低減するために、隣接する境界領域（すなわち、Ａ１、Ａ４、及びＡ５；Ｂ１、Ｂ２、及びＢ３；Ｃ１、Ｃ６、及びＣ７）内のチャネルに別個のスペクトルを配分することを提案する。
【００３２】
ＢＳＣシナリオ
ＢＳＣは、隣接する境界領域内のＭＳに重複するスペクトルを配分することによって達成される。図２Ｂに示されているように、隣接するＢ１セクタ及びＢ２セクタ内にそれぞれ位置するＭＳ１及びＭＳ２に、重複するスペクトルが配分される。次に、ＢＳ１及びＢＳ２は、ＭＳ１及びＭＳ２の双方に、同じ周波数帯域内で共同で信号を送信する。このため、ダウンリンク信号によって互いに引き起こされる、起こり得る干渉が、有用な信号（実線によって示される）に置き換えられる。通常、ＢＳＣは、図２Ｂに示すような協調を可能にするために、隣接する境界領域（すなわち、Ａ１、Ａ４、及びＡ５；Ｂ１、Ｂ２、及びＢ３；Ｃ１、Ｃ６、及びＣ７）に、重複するスペクトルを配分することを提案する。これは従来のネットワークでは決して可能でない。
【００３３】
ＢＳＣをセル内ＳＤＭＡと統合することができ、これによって、ＢＳは、自身がサービス提供する複数のＭＳに、同じＯＦＤＭＡ資源を使用して送信することができる。たとえば、図２Ｂは、ＢＳ２がＳＤＭＡを使用してＭＳ２及びＭＳ３と通信している場合、ＭＳ１，ＭＳ２、及びＭＳ３が３−ＭＳ、２ＢＳのＢＳＣシナリオに加わることができることを示している。
【００３４】
以下において、ＯＦＤＭＡベースのマルチセルネットワークのための本発明の干渉グラフベースの資源配分方法を説明する。本方法は、ＩＣＩＣ管理方式及びＢＳＣ管理方式の双方を同時に使用することを可能にすることに留意されたい。
【００３５】
第１のフェーズ：干渉管理
図３は、ＢＳ及びＭＳの構成例を示している。本発明では、ＭＳの地理的ロケーション、及びチャネル品質を示す瞬時チャネル状態情報（ＣＳＩ）から、干渉の強度を求めることを所望する。この情報を使用して、図４においてさらに詳細に示されるような対応する干渉グラフ１０１を構築する。
【００３６】
図４において、各ノードＩ（ただし、Ｉ＝１，．．．，５）は、１つのＭＳを表す。ネットワーク内にＮ個のＯＦＤＭＡ資源、たとえばサブチャネルが存在すると想定する場合、全てのノード対はＮ個の並列のエッジによって接続される。Ｎ個の並列のエッジのそれぞれは、２つのＭＳ間の起こり得る干渉を表す、関連付けられる「コスト」又は重みｗを有する。たとえば、ノードａ及びノードｂ（ただし、ａ＜ｂ）の間の重みは、図４のｗａｂによって表される。ｗａｂの値が高いほど、ＭＳａ及びＭＳｂ間の起こり得る干渉が強くなる。
【００３７】
一般的なグラフ理論における既知の最大ｋ切断と、干渉管理を考慮に入れるＯＦＤＭＡネットワークにおけるチャネル配分問題との間の密接な関係が見て取れる。グラフ理論において、切断は、グラフの頂点を複数のセット又はクラスタに分割することである。切断のサイズは切断部を横切るエッジの総数である。本発明の重み付けグラフにおいて、切断のサイズは、切断部を横切るエッジの重みの合計である。
【００３８】
切断は、切断のサイズがいかなる他の切断のサイズよりも小さくない場合、最大限（maximal）（最大（max））である。切断をｋ個の切断に一般化することによって、最大ｋ切断プロセスは、サイズがいかなる他のｋ個の切断よりも小さくないｋ個の切断から成るセットを見つけることとなる。これは、多数のノードを有するグラフに関するＮＰ完全問題である。
【００３９】
結果として、本発明では、適切な解を効率的に生成することができる発見的方法を使用する。このため、Ｎ個のサブチャネルとＭ個のＭＳを所与とすると、チャネル配分問題に対する良好な解は、最大ｋ切断プロセスによって解かれる。
【００４０】
最大ｋ切断プロセスの目的は、図４に示す干渉グラフを、クラスタ内のエッジ重みが最大になるように複数のクラスタ４１０に分割することである。
【００４１】
各クラスタは、ＯＦＤＭＡ資源、たとえばサブチャネルに対応する。同じクラスタ内のノード（又はＭＳ）は、同じサブチャネルを配分される。クラスタ内のエッジ重みを最大にするという目的において、その結果は、強力な干渉物を異なる複数のクラスタ内に配置するか、又は換言すれば、干渉物を複数の異なるサブチャネル上に分離する傾向がある。これはＩＣＩを低減するのに役立つ。
【００４２】
干渉グラフのためのエッジ重み構築
チャネル配分の前に関連するＳＩＮＲ測定値を取得するのは、仮に実現可能であるにしても実際には困難であるため、本発明の実施の形態は、エッジ重みｗａｂを、正確なＳＩＮＲ測定値なしで構築する方法を提供する。基本的な着想は、基地局（ＢＳ）において保持されるＭＳａ及びＭＳｂに関するダイバーシティセット情報１０２に基づいて、エッジ（ａ，ｂ）に関連付けられる重みを求めることである。
【００４３】
図５は、図３に示す例に関するダイバーシティセットを示している。図５において、各行５０１は、ＢＳにおいて対応するＭＳに関して保持されるダイバーシティセットを示している。各ＭＳはアンカーＢＳ５１１を有し、ＭＳがセル境界の近くに位置する場合、幾つかの隣接するＢＳ５１２を有する可能性がある。ダイバーシティセットは、ＭＳ間の干渉に関する有用な地理的情報を含む。地理的情報は、ネットワークのトポロジ又は「構造」を表す。したがって、この構造は干渉グラフ内に反映される。
【００４４】
さらに、下記で説明するように、ダイバーシティセットからの任意の２つのＭＳ間の起こり得る干渉を求めることができる。
【００４５】
ＭＳ２及びＭＳ４は同じセル内にあり、同じアンカーＢＳを有する。したがって、ＭＳ２及びＭＳ４が同じＯＦＤＭＡ資源（たとえばサブチャネル）を配分される場合、ＭＳ２及びＭＳ４がＳＤＭＡを実施しない限り、互いにセル内干渉を引き起こす。
【００４６】
ＭＳ１のアンカーＢＳは、ＭＳ４の隣接するＢＳのセット内にある。同様に、ＭＳ４のアンカーＢＳは、ＭＳ１の隣接するＢＳのセット内にある。これは、ＭＳ１及びＭＳ４が、同じＯＦＤＭＡ資源（たとえばサブチャネル）を配分される場合、互いに干渉を引き起こす可能性があることを意味している。同じ理由で、ＭＳ１及びＭＳ４はＢＳＣを実施することができる。このため、ＭＳ１及びＭＳ４は、ＢＳＣを実施しない限り、互いにＩＣＩを有すると結論付けることができる。
【００４７】
ＭＳ４のアンカーＢＳは、ＭＳ３の隣接するＢＳのセット内にある。このため、ＭＳ４及びＭＳ３は、同じＯＦＤＭＡ資源（たとえばサブチャネル）を使用する場合、互いに干渉を引き起こす。しかしながら、ＭＳ３のアンカーＢＳは、ＭＳ４の隣接するＢＳのセット内にないため、ＭＳ３及びＭＳ４はＢＳＣを実施することができない。ＭＳ１及びＭＳ３は、いずれのＭＳのアンカーＢＳも他方のＭＳの隣接するＢＳのセット内にないため、互いに干渉しない。
【００４８】
上記の分析は、全てのノード対に関して実施され、その後に重み割当てが続く。一実施の形態では、任意の２つのノード間のエッジに関して選択することができる７つの可能な重み値１０５、
ｗＢ，ｗＳ，ｗＮ，ｗ０，ｗ１，ｗ２，ｗＡ
が存在する。ここで、重みｗＢはＢＳＣに関連付けられる重みに対応し、ｗＳはＳＤＭＡに関連付けられる重みに対応し、ｗＮは非干渉に関連付けられる重みに対応し、ｗＡはセル内干渉に関連付けられる重みに対応し、ｗ０、ｗ１、及びｗ２は、２つのＭＳの地理的ロケーションに依拠する様々な干渉レベルにおけるＩＣＩ重みである。
【００４９】
すなわち、２つの異なるセル内に位置する２つのＭＳ間の相互ＩＣＩは、各ＭＳが自身のセルの中央にある場合、最も低く（ｗ０によって表される）、一方のＭＳが一方のセルの境界にあり、他方が他方のセルの中央にある場合、中程度であり（ｗ１によって表される）、双方のＭＳが自身のセルの境界にある場合、最も強力である（ｗ２によって表される）。
【００５０】
全体的に、７つの重み値は以下のようにランク付けすることができる。
ｗＢ≒ｗＳ＜＜ｗＮ＜ｗ０＜ｗ１＜ｗ２＜＜ｗＡ
【００５１】
ｗＢ及びｗＳは、ＭＳが同じサブチャネルを使用することを必要とするため、最も小さく、ｗＡは、セル内干渉を完全に回避しようとするため、最も大きいことに留意されたい。
【００５２】
エッジ重みを求める完全な方法は、図６のフローチャートによって要約されている。
【００５３】
第１に、ＭＳａのアンカーＢＳ及びＭＳｂのアンカーＢＳをチェックする（６１０）。それらが同じである場合、重み決定を直接行うことができる。ＳＤＭＡを使用するか否かを判断し（６１１）、それに従って、ｗａｂをｗＳ６１２又はｗＡ６１３として割り当てる。
【００５４】
ＭＳａのアンカーＢＳ及びＭＳｂのアンカーＢＳが同じでない場合、さらなる手順が必要となる。具体的には、ＭＳａのアンカーＢＳが、ＭＳｂの隣接するＢＳのダイバーシティセット内にあるか否かをチェックし（６３０）、それに従って、一時的な重み（ｗ０，ｗ１，ｗ２）６３１又はｗＮ６３２を割り当てる。同様に、ＭＳｂのアンカーＢＳが、ＭＳａの隣接するＢＳのダイバーシティセット内にあるか否かをチェックし（６５０）、それに従って、一時的な重み（ｗ０，ｗ１，ｗ２）６５１又はｗＮ６５２を割り当てる。双方のアンカーＢＳが互いの隣接するＢＳのセット内にある場合、ＢＳＣを適格とし、ＢＳＣを使用するか否かを判断する（６７０）。ＢＳＣを使用する場合、ｗＢ６７１を割り当て、そうでない場合、ｍａｘ（ｗ（１），ｗ（２））６７２を割り当てる。
【００５５】
一実施の形態について、干渉関連エッジ重みは、
（ｗＢ，ｗＳ，ｗＮ，ｗ０，ｗ１，ｗ２，ｗＡ）＝（−１０３，−１０３＋５０，０，５０，１００，２００，１０５）
である。重みにおける小さな変化は結果を変化させない。上記に記載するグラフエッジ重みと異なるグラフエッジ重みも使用することができることに留意されたい。
【００５６】
図３に関して割り当てられた重みを有する、結果としての干渉グラフが図７に示されている。ここで、幾つかのエッジは、ＭＳの実際の構成に依拠して２つの可能な重みを含む。たとえば、ＭＳ１及びＭＳ４は、ＩＣＩＣ（重みｗ２）又はＢＳＣ（重みｗＢ）を実施することができる。ＭＳ２及びＭＳ４（又はＭＳ３及びＭＳ５）は、ＳＤＭＡを採用する（重みｗＳ）か又は採用しない（重みｗＡ）ことができる。ＩＣＩを有する他のノード対に関して、ＩＣＩＣを利用する。ＢＳＣ及びＳＤＭＡは、物理的に実現可能な場合に組み込むことができるオプションの機能であることに留意されたい。
【００５７】
クラスタリング
最大ｋ切断プロセスに対する従来の解は、大きなグラフ、すなわち多数のＭＳの場合に計算量が非常に多い。このため、図８に示すように、この問題を解く準最適発見的方法を説明する。
【００５８】
Ｎ個のＯＦＤＭＡ資源、たとえばサブチャネル、及びＭ個のＭＳを所与とすると、本発明の目的は、図７の干渉グラフを、クラスタ間エッジ重みが最大になるようにＮ個のクラスタ７１０に分割することである。
【００５９】
第１に、本方法は、Ｍ＞Ｎであるか否かをチェックする（８１０）。Ｍ≦Ｎのとき、クラスタリング問題は取るに足りないものとなる。これは、配分（Ｎ）に利用可能なＯＦＤＭＡ資源量が、ＭＳ（Ｍ）によって必要とされるＯＦＤＭＡ資源量以上であるためである。このケースでは、本方法は最適解で終了する（８６０）。
【００６０】
Ｍ＞Ｎの場合、本方法は、最初に、Ｎ個のクラスタに、各クラスタに１つずつ、Ｎ個の任意に選択されたノードを割り当てる（８２０）。次に、残りのＭ−Ｎ個のノードを、クラスタ内重みの増加が最小になるようにクラスタに反復的に割り当てる（８３０）。
【００６１】
割当てが完了した後、クラスタのクラスタ内重みを更新する（８４０）。
【００６２】
全てのノードをクラスタに割り当てる（８５０）と、本方法は終了する（８６０）。
【００６３】
この発見的方法の複雑度は、グラフ内のエッジ数、ノード数、クラスタ数の合計に比例する。Ｍ個のノードとＮ個のクラスタを有する、本発明の特定のケースの場合、この発見的方法は、複雑度Ｏ（Ｍ２／２＋Ｍ／２＋Ｎ）を有する。
【００６４】
第２のフェーズ：チャネル配分
第１のフェーズの配分の後、ＭＳは、サブチャネル配分のためにＮ個のクラスタ７１０にグループ化される。第２のフェーズにおいて、クラスタにサブチャネルを配分する。、第２のフェーズの配分は、（Ｎ！）個の可能なサブチャネル配分選択の中で、瞬時チャネル品質を最適化するサブチャネル配分選択を見つける。
【００６５】
第２のフェーズを解く方法
上記で述べたように、第２のフェーズの問題を解くために、全ての（Ｎ！）個の選択にわたって全数検索することも、計算的に困難である。図９に示すように、クラスタにサブチャネルを反復的に配分する発見的な準最適方法を説明する。この方法を、ＳＮＲを意識したチャネル配分と呼ぶ。
【００６６】
図９において、初期状態におけるサブチャネル資源は｛１，．．．，Ｎ｝９１０である。Ｎ個のクラスタは、クラスタ内に含まれるノード数の観点から、小さいものから大きいものへ配列され、連結（tie）は任意で外される。資源は、クラスタサイズの昇順で（９２０）クラスタに配分される。
【００６７】
クラスタ毎に、合計容量がこのクラスタに関して最大のサブチャネルを該クラスタに配分する（９３０）。それに従って、残りの資源を更新する（９４０）。全てのクラスタに資源が割り当てられている（９５０）場合、終了する（９６０）。そうでない場合、手順は次に大きなクラスタに関して継続する。
【００６８】
クラスタにサブチャネルを反復的に配分するこの発見的方法は、複雑度Ｏ（Ｎ２）である。
【００６９】
ここでも代替的なランダムチャネル配分を使用して第２のフェーズの問題を解くことができる。この方法では、（Ｎ！）個の選択から１つの配分を解としてランダムに選び取る。このランダム配分方法の複雑度はＯ（１）である。しかしながらランダムチャネル配分の性能は、上述の発見的方法の性能ほど良好でない場合がある。
【００７０】
性能評価
図１０は、従来のＩＣＩを意識しない配分を本方法と比較している。ＩＣＩＣ１及びＩＣＩＣ２は、干渉管理においてＩＣＩＣ方式を使用し、第２のフェーズにおけるチャネル割当てにおいて異なる（それぞれランダムなチャネル割当て及びＳＮＲを意識したチャネル割当て）。同様に、ＢＳＣ１及びＢＳＣ２は、干渉管理においてＢＳＣ方式を使用し、第２のフェーズにおけるチャネル割当てにおいて異なる（それぞれランダムなチャネル割当て及びＳＮＲを意識したチャネル割当て）。ＢＳＣ方式は、実現可能なときはいつでも、ＢＳＣ重みｗＢを干渉グラフ内に組み込み、一方でＩＣＩ方式は組み込まない。グラフは、５つのテスト方式に関して累積分布関数（ＣＤＦ）対ＳＩＮＲを示している。本発明による方法は、従来のＩＣＩを意識しない方法と比較して、ＳＩＮＲ性能に対する顕著な改善を有する。これによって、本発明の干渉管理及びチャネル割当て方法の効率性が実証される。
【００７１】
本発明を好ましい実施の形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１】
2011509537.tif 000003
【図２Ａ】
2011509537.tif 000004
【図２Ｂ】
2011509537.tif 000005
【図３】
2011509537.tif 000006
【図４】
2011509537.tif 000007
【図５】
2011509537.tif 000008
【図６】
2011509537.tif 000009
【図７】
2011509537.tif 000010
【図８】
2011509537.tif 000011
【図９】
2011509537.tif 000012
【図１０】
2011509537.tif 000013
【国際調査報告】
2011509537.tif 000014
2011509537.tif 000015
2011509537.tif 000016
2011509537.tif 000017
2011509537.tif 000018