(57)【要約】【課題】  本発明は、空白帯域内の並列リソース管理のための方法及びシステムを提供する。【解決手段】  空白帯域内の並列リソース管理のための方法及びシステムは、送信電力制御及びチャネルセット配置を用いても良い。Ｌ個の電力レベルの各々のチャネルセット及び対応するネットワークセットは、Ｋ個のチャネルを共有するＮ個のネットワークのために配置されても良い。入力は、Ｎ個のネットワークの各々の位置情報であっても良い。出力は、Ｌ個の電力レベルの各々についての、更新されたチャネルセット及び対応するネットワークセットであっても良い。方法は、最大ネットワークをより大きな電力値を有するチャネルセットに配置しても良い。ネットワークセットは、対応するチャネルセット内のチャネル数が対応する干渉グラフの最大ノード階級より大きくなるよう、構築されても良い。方法は、さらにネットワーク間のチャネルの再利用可能性を考慮に入れても良く、相応してスペクトル利用を増大し得る。【選択図】  図２
2015056897.tif 000002
【特許請求の範囲】
【請求項１】
空白帯域における並列リソース管理のための方法であって、
Ｌ個の許容可能電力レベルを有する空白帯域内のＫ個のチャネルを共有するＮ個の無線ネットワークの位置情報を受信するステップであって、Ｎ及びＫは１以上の整数である、ステップと、
前記Ｌ個の電力レベルの各々について、前記Ｎ個の無線ネットワークの干渉グラフを生成するステップであって、前記干渉グラフは、各ノードが無線ネットワークに対応するノードと、各エッジが２つのノード間の干渉に対応するエッジと、を有し、各ノードにおけるエッジの数はノード階級を表し、Ｌは１以上の整数である、ステップと、
最大電力レベルを有するチャネルから開始して、前記Ｌ個の電力レベルに対応するチャネルセットを初期化するステップと、
前記Ｌ個の電力レベルに対応するネットワークセットを初期化するステップであって、
最大電力レベルに対応する最大電力ネットワークセット内のネットワーク数を最大化するステップ、及び
前記最大電力ネットワークセット以外のネットワークセットを空にするステップ、を含む、ステップと、
前記チャネルセット及び前記ネットワークセットを更新するステップであって、ネットワークセットに対応するチャネルセット内のチャネル数は、対応する電力レベルについての前記干渉グラフの最大ノード階級より大きい、ステップと、
を有する方法。
【請求項２】
前記チャネルセット及び前記ネットワークセットを更新するステップは、
前記Ｌ個の電力レベルの各々についての前記干渉グラフに基づき、最大電力レベルを有するチャネルセットに対応するネットワークセットの更新を開始し、及び前記ネットワークセットに、最小ノード階級変化値を有するネットワークを追加するステップ、を有する、請求項１に記載の方法。
【請求項３】
前記チャネルセット及び前記ネットワークセットを更新するステップは、
各ネットワークセットにおいて、より大きい電力レベルを有するチャネルセットに対応するネットワークの数を最大化するステップ、を有する、請求項１に記載の方法。
【請求項４】
前記チャネルセット及び前記ネットワークセットを更新するステップは、
各ネットワークセットにおいて、既に別のネットワークセットに配置されたチャネルを再利用できるようネットワークを優先順位付けするステップ、を有する、請求項１に記載の方法。
【請求項５】
前記Ｌ個の電力レベルに対応する前記チャネルセット及び前記ネットワークセットを出力するステップ、
を更に有する請求項１に記載の方法。
【請求項６】
前記Ｌ個の電力レベルの各々について、前記対応するチャネルセット内のチャネルを前記対応するネットワークセット内のネットワークに配置するステップ、
を更に有する請求項５に記載の方法。
【請求項７】
前記チャネルセット及び前記ネットワークセットを更新するステップは、
一度に１つのチャネルを、次に低い電力レベルを有するチャネルセットへ移動するステップ、を有する、請求項１に記載の方法。
【請求項８】
非一時的コンピュータ可読媒体と、
前記コンピュータ可読媒体に格納されたコンピュータ実行可能命令と、
を有する製造品であって、前記命令は、プロセッサにより可読であり、実行されると前記プロセッサに、
Ｌ個の許容可能電力レベルを有する空白帯域内のＫ個のチャネルを共有するＮ個の無線ネットワークの位置情報を受信し、Ｎ及びＫは１以上の整数であり、
前記Ｌ個の電力レベルの各々について、前記Ｎ個の無線ネットワークの干渉グラフを生成し、前記干渉グラフは、各ノードが無線ネットワークに対応するノードと、各エッジが２つのノード間の干渉に対応するエッジと、を有し、各ノードにおけるエッジの数はノード階級を表し、Ｌは１以上の整数であり、
最大電力レベルを有するチャネルから開始して、前記Ｌ個の電力レベルに対応するチャネルセットを初期化し、
前記Ｌ個の電力レベルに対応するネットワークセットを初期化し、
最大電力レベルに対応する最大電力ネットワークセット内のネットワーク数を最大化すること、及び
前記最大電力ネットワークセット以外のネットワークセットを空にすること、を含み、
前記チャネルセット及び前記ネットワークセットを更新し、ネットワークセットに対応するチャネルセット内のチャネル数は、対応する電力レベルについての前記干渉グラフの最大ノード階級より大きく、させる、製造品。
【請求項９】
前記チャネルセット及び前記ネットワークセットを更新する命令は、
前記Ｌ個の電力レベルの各々についての前記干渉グラフに基づき、最大電力レベルを有するチャネルセットに対応するネットワークセットの更新を開始し、及び前記ネットワークセットに、最小ノード階級変化値を有するネットワークを追加する命令、を有する、請求項８に記載の製造品。
【請求項１０】
前記チャネルセット及び前記ネットワークセットを更新する命令は、
各ネットワークセットにおいて、より大きい電力レベルを有するチャネルセットに対応するネットワークの数を最大化する命令、を有する、請求項８に記載の製造品。
【請求項１１】
前記チャネルセット及び前記ネットワークセットを更新する命令は、
各ネットワークセットにおいて、既に別のネットワークセットに配置されたチャネルを再利用できるようネットワークを優先順位付けする命令、を有する、請求項８に記載の製造品。
【請求項１２】
前記プロセッサに、
前記Ｌ個の電力レベルに対応する前記チャネルセット及び前記ネットワークセットを出力させる命令、を更に有する、請求項８に記載の製造品。
【請求項１３】
前記プロセッサに、
前記Ｌ個の電力レベルの各々について、前記対応するチャネルセット内のチャネルを前記対応するネットワークセット内のネットワークに配置させる命令、を更に有する、請求項１２に記載の製造品。
【請求項１４】
前記チャネルセット及び前記ネットワークセットを更新する命令は、
一度に１つのチャネルを、次に低い電力レベルを有するチャネルセットへ移動する命令、を有する、請求項８に記載の製造品。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、通信ネットワークに関し、より詳細には、送信電力制御及びチャネル割り当てを用いた空白帯域における並列リソース管理に関する。
【背景技術】
【０００２】
無線ネットワークの数及び種類が増大し、それにより伝達される通信の量が増加するにつれ、異なる無線アクセス技術、電力制限、周波数制限及び他の相違を有する無線ネットワークを含むネットワークを管理することが次第に望ましくなっている。このような異種ネットワークの管理は、空白帯域の共有特性のために次第に複雑化し得る。空白帯域での共存を管理するために幾つかの解決策が提供されているが、干渉を回避しながらスペクトル再利用及びスペクトル利用を最大化することは依然として課題である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明は、空白帯域における並列リソース管理を提供する。
【課題を解決するための手段】
【０００４】
一態様では、空白帯域内の並列リソース管理のための開示の方法は、Ｌ個の許容可能電力レベルを有する空白帯域内のＫ個のチャネルを共有するＮ個の無線ネットワークの位置情報を受信するステップであって、Ｎ、Ｋ及びＬは１より大きい整数である、ステップを有する。
【０００５】
前記方法は、前記Ｌ個の電力レベルの各々について、前記Ｎ個の無線ネットワークの干渉グラフを生成するステップであって、前記干渉グラフは、各ノードが無線ネットワークに対応するノードと、各エッジが２つのノード間の干渉に対応するエッジと、を有し、各ノードにおけるエッジの数はノード階級を表し、Ｌは１以上の整数である、ステップを有しても良い。各ノードにおけるエッジ数は、ノード階級を表しても良い。前記方法は、最大電力レベルを有するチャネルから開始して、前記Ｌ個の電力レベルに対応するチャネルセットを初期化するステップを有しても良い。
【０００６】
前記方法は、前記Ｌ個の電力レベルに対応するネットワークセットを初期化するステップであって、最大電力レベルに対応する最大電力ネットワークセット内のネットワーク数を最大化するステップ、及び前記最大電力ネットワークセット以外のネットワークセットを空にするステップ、を含む、ステップを更に有しても良い。
【０００７】
前記方法は、前記チャネルセット及び前記ネットワークセットを更新するステップを更に有しても良い。ネットワークセットに対応するチャネルセット内のチャネル数は、対応する電力レベルの前記干渉グラフの最大ノード階級より大きくても良い。
【０００８】
空白帯域内の並列リソース管理のための追加の開示の態様は、非一時的コンピュータ可読媒体を有する製造品、及び前記コンピュータ可読媒体に格納されたコンピュータ実行可能命令を有する。更なる態様は、メモリと、前記メモリに結合されるプロセッサと、ネットワークインタフェースと、前記メモリに格納されたコンピュータ実行可能命令とを有する空白帯域内の並列リソース管理のための管理システムを有する。
【０００９】
実施形態の目的及び利点が理解され、少なくとも特に特許請求の範囲で指摘された要素、特徴及び組合せを用いて達成されるだろう。
【図面の簡単な説明】
【００１０】
本発明並びに利点のより完全な理解のため、添付の図と共に以下の説明を参照する。
【図１】空白帯域内の並列リソース管理のためのネットワークの一実施形態の選択された要素のブロック図である。
【図２】空白帯域内の並列リソース管理のための管理システムの一実施形態の選択された要素のブロック図である。
【図３Ａ】干渉グラフの実施形態の選択された要素を示す。
【図３Ｂ】干渉グラフの実施形態の選択された要素を示す。
【図３Ｃ】干渉グラフの実施形態の選択された要素を示す。
【図４】空白帯域内の並列リソース管理のための方法の一実施形態の選択された要素のフローチャートである。
【図５】空白帯域内の並列リソース管理のための方法の一実施形態の選択された要素のフローチャートである。
【図６Ａ】干渉グラフの実施形態の選択された要素を示す。
【図６Ｂ】干渉グラフの実施形態の選択された要素を示す。
【発明を実施するための形態】
【００１１】
無線ネットワークは、モバイルデータトラフィックの未曾有の成長に適合するために、より多くのスペクトルを要求している。この事実にもかかわらず、多くの帯域（例えば、ＴＶ帯域又は連邦政府によって割り当てられた帯域）で割り当てられるスペクトルは、大量に活用されていないままである。世界中の規制団体は、現職者が不在のときに、帯域の不使用部分（「空白帯域」）へのアクセスを可能にする規則を策定してきた。所与の場所で、空白帯域内のチャネルは、例えば現職者の近さに依存して、異なる電力レベルを用いて未認可アクセスのために利用できる。空白帯域により提供される追加リソースを活用するために、このスペクトルを共有する複数のネットワークが展開され得る。これは、無線ネットワークプロバイダに貴重な機会を提示し得る。
【００１２】
しかしながら、空白帯域へのアクセスの調整無しでは、互いの近傍に位置するネットワークは干渉し、その結果、粗悪な性能を生じる。さらに、空白規則にり制御される場合、各ネットワークは、配置されたチャネル数にかかわらず、１つの送信電力レベルでのみ送信することを許可される。
【００１３】
本願明細書に以下に詳述するように、空白帯域における異種共存管理のために多項式時間複雑性を有する計算方法（例えば、アルゴリズム）が開発されている。本願明細書で提示される計算方法は、空白帯域内の個々のチャネルの利用が最大化されると同時に、近隣ネットワーク間の有害な干渉が回避されるようにスペクトル配置及び電力レベルを調整可能にできる。本願明細書に記載の計算方法は、スペクトル再利用及びより大きな電力レベルでのチャネル利用を増大させる目的で、ネットワーク及び利用可能な空白帯域チャネルをバラバラなセットに分割し得る。バラバラなセットは、特定の許容可能電力レベルに対応しても良い。次に、チャネル配置は、各ネットワークセットについて、その対応するチャネルセットから並列して実行される。
【００１４】
以下の説明では、開示の主題の議論を容易にするために例として詳細事項が説明される。しかしながら、当業者には、開示の実施形態が例示であること及び全ての可能な実施形態を網羅するものではないことが明らかである。
【００１５】
特定の実施形態及びそれらの利点は、図１乃至図６を参照することにより良好に理解される。図中の同様の番号は同様の及び対応する部分を示すために用いられている。
【００１６】
図を参照すると、図１は、本開示の特定の実施形態による、空白帯域内の共存管理のためのネットワーク１００の一実施形態の選択された要素を示すブロック図である。幾つかの実施形態では、ネットワーク１００は、無線ネットワーク１０２、ユーザ機器１０４、及び無線ネットワーク１０２に通信可能に結合される管理システム２００を有しても良い。図１に示すように、管理システム２００は、例えばガルバニック及び／又は光媒体（図示しない）を用いて無線ネットワーク１０２と固定通信中であっても良い。無線ネットワーク１０２は、また、ユーザ機器１０４による無線ネットワーク１０２を介した通信を可能にするため、ユーザ機器１０４によるネットワークアクセスを可能にする無線信号を提供しても良い。本願明細書に記載するように、管理システム２００は、リソース（例えば、チャネル割り当て及び／又は電力レベル）を管理し、ネットワーク１０２の各々が空白帯域を利用しながら並列動作できるよう構成されても良い。
【００１７】
幾つかの実施形態では、無線ネットワーク１０２は、通信ネットワークへのアクセスポイントであっても良い。アクセスポイントは、ユーザ機器１０４に通信ネットワークを介した通信を可能にするよう構成される。幾つかの実施形態では、各無線ネットワーク１０２は、他の無線ネットワーク１０２と実質的に同じスペクトル帯域を共有し、一方で異なる無線アクセス技術（例えば、ＩＥＥＥ８０２．１１、ＩＥＥＥ８０２．２２、ＬＴＥ、等）で動作する可能性がある。さらに、各無線ネットワーク１０２は、異なる事業者により所有され及び／又は運営されても良い。例えば、システム１００は、２つのＬＴＥ送信塔及び２つの８０２．２２無線アクセスポイントを含む４つの無線ネットワーク１０２を有しても良い。同一の又は代替の構成で、システム１００は、本開示の範囲から逸脱することなく、より多くの、より少ない、又は異なる構成の無線ネットワーク１０２を有しても良い。
【００１８】
幾つかの実施形態では、ユーザ機器１０４は、無線ネットワーク１０２のうちのいずれか又は全部を介して通信する及び／又は通信を実現するよう構成される電子装置及び／又は複数の電子装置の組合せであっても良い。例えば、ユーザ機器１０４は、セルラ電話機、タブレットコンピュータ、ラップトップコンピュータ、他のユーザ機器１０４のネットワーク、及び／又は無線ネットワーク１０２を介してデータを送信及び／又は受信するよう構成され得る他の適切な電子装置であっても良い。
【００１９】
ネットワーク１００の動作中、空白帯域は、モバイルデータトラフィックの増大する要求に適合するために、無線ネットワーク１０２に追加リソースを提供しても良い。スペクトル不足及び空白帯域を介したデータトラフィックのオフロードに対する関心の増大のために、管理システム２００は、近隣ネットワーク間の干渉を制御でき、リソース（つまり、チャネル及び／又は電力）利用を増大できるようにされても良い。空白帯域は、既存使用者の活動に依存して、幾つかのチャネルに、（例えば、ＴＶ帯域内の）異なる電力レベルを有する追加スペクトルを提供しても良い。幾つかのチャネルのスペクトルを再利用するために及び追加電力レベルを良好に利用するために、直交チャネル配置は、電力制御と共に提供され、既定面の制約を受けても良い。
【００２０】
利用可能なチャネルの数が数チャネルに制限される特定の例では、時間領域における直交共有は、効率的に解くことができる線形アルゴリズムを用いて解くことができる。時間共有が実現可能ではない状況では、対応する整数最適化問題の複雑性は、ネットワーク、利用可能チャネル及び／又は電力レベルの数と共に指数関数的に増大し、計算的に扱いにくい問題になってしまい得る。このようなソリューションは、特定電力レベルを有するチャネルをネットワークのサブセットに配置する必要がある。
【００２１】
しかしながら、現在の空白規則により与えられるように、ネットワークは、空白帯域内で動作しているとき、使用されるチャネル数にかかわらず、１つの電力レベルのみで送信できる。これは、スペクトル的に非効率であり、利用可能チャネルの粗悪な利用をもたらし得る。
【００２２】
本願明細書に開示のように、空白帯域内の並列リソース管理のためのアルゴリズムは、全体のリソース利用の増大を目的として、経験則を用いてネットワーク及びチャネルのバラバラなセットを生成する。本願明細書に開示のアルゴリズムは、多項式時間複雑性を有するので、効率的に解くことができる。許容可能電力レベルを表す各チャネルセット内のチャネルは、対応するネットワークセット内のネットワークに割り当てられても良い。
【００２３】
さらに、これらのセットは、チャネルセットの濃度が対応するネットワークセットの干渉グラフの最大ノード階級より大きくなるように、構築されても良い。次に、種々のチャネル配置アルゴリズムは、特定チャネルをネットワークに割り当てるために、各ネットワーク−チャネルセットについて並列に用いられても良い。したがって、本願明細書に開示のアルゴリズムは、多項式時間複雑性における共同電力制御及びチャネル配置ソリューションを達成できる。
【００２４】
図２を参照すると、ブロック図は、本開示による並列空白帯域リソース管理のための管理システム２００の一実施形態の選択された要素を示す。図２に示す実施形態では、管理システム２００は、共有バス２０２を介して集合的に記憶媒体２１０として識別される記憶媒体に結合されるプロセッサ２０１を有する。図２に示すように、管理システム２００は、管理システム２００を、ネットワーク１００の部分のような、無線ネットワーク１０２（図１参照）を含むネットワークに接続するネットワークアダプタ２２０を更に有する。
【００２５】
図２では、記憶媒体２１０は、永続的及び揮発性媒体、固定及び取り外し可能媒体、磁気及び半導体媒体を含み得る。記憶媒体２１０は、命令、データ、又はそれらの両方を格納するよう動作する。図示の記憶媒体２１０は、命令のセット又はシーケンス２２４、つまりオペレーティングシステム２１２及び並列リソース管理２１４を有する。
【００２６】
オペレーティングシステム２１２は、ＵＮＩＸ又はＵＮＩＸに類似するオペレーティングシステム、Ｗｉｎｄｏｗｓ（登録商標）ファミリオペレーティングシステム、又は別の適切なオペレーティングシステムであっても良い。命令２２４は、完全に又は少なくとも部分的に、その実行中にプロセッサ２０１内に存在しても良い。さらに留意すべきことに、プロセッサ２０１は、命令２２４を共有バス２０２を介して記憶媒体２１０から受信するよう構成されても良い。本願明細書に記載のように、並列リソース管理２１４は、本開示に従う種々のアルゴリズムを実施するための命令及び／又はコードを表し得る。
【００２７】
図３Ａ〜３Ｃを参照すると、Ｌ個の許容可能電力レベルについて、Ｎ個のネットワークがＫ個の空白チャネルを共有する領域のシステムモデルが、干渉グラフ３００、３０１、３０２の形式で示される。ここで、Ｎ＝４及びＬ＝３である。図３Ａ、３Ｂ、３Ｃでは、個々の干渉グラフ３００、３０１、３０２は、それぞれ異なる電力レベルにおけるネットワークトポロジを表す。干渉グラフ３００、３０１及び３０２では、ネットワークノード（円）は異なるネットワークを表し、ノード間のエッジ（線）は２つのネットワークが互いに干渉するときを表す。ある干渉グラフでは、全てのネットワークノードは実質的に同一の電力レベルで送信すると仮定される。図３Ａ〜３Ｃでは、４つのネットワークノード３１０、３１２、３１４及び３１６の例示的な実施形態が説明を明確にするために示される。異なる実施形態では、干渉グラフは、本願明細書に記載のように、異なる数のネットワークノード及びエッジを有しても良いことが理解されるだろう。
【００２８】
図３Ａの干渉グラフ３００では、ネットワークノード３１０は、ネットワークノード３１２及び３１４と干渉し得る。一方で、ネットワークノード３１２も、ネットワークノード３１６と干渉する。図３Ｂの干渉グラフ３０１では、干渉グラフ３００内の全てのエッジが存在し、ネットワークノード３１４はネットワークノード３１２と更に干渉する。図３Ｃの干渉グラフ３０２では、干渉グラフ３０１内の全てのエッジが存在し、ネットワークノード３１６はネットワークノード３１０及び３１４と更に干渉する。図３Ａ〜３Ｃに示すように、電力レベルは、干渉グラフ３００の第１の電力レベルから、干渉グラフ３０１の第２の電力レベルへ、干渉グラフ３０２の第３の電力レベルへと増大する。したがって、より大きな電力レベルでは、干渉グラフは、高密度になり、スペクトル再利用の可能性が少ないことを示し得る。
【００２９】
各干渉グラフ３００、３０１及び３０２では、「ノード階級」は、ネットワークノード当たりのエッジ数として定められる。したがって、干渉グラフ３００、３０１及び３０２のノード階級は、表１に与えられる。
［表１］それぞれ図３Ａ、３Ｂ及び３Ｃの干渉グラフ３００、３０１及び３０２のノード階級
【表１】
2015056897.tif 000003
【００３０】
次に、「ノード階級変化」は、前の電力レベルと現在の電力レベルとの間の所与のネットワークノードのノード階級の変化として定められる。ノード階級変数（前の電力レベルｌ−１に関し、電力レベルｌのＤｅｌｔａ＿ｌ）は、ネットワークがより小さい電力レベルでチャネルを再利用するより高い確率を有するか否かを反映し得る。Ｄｅｌｔａ＿ｌのより小さな値は、減少する電力レベルで再利用の可能性が小さいことを意味し、したがって、可能な場合、所与のネットワークのためにより大きな電力レベルが用いられることが望ましいことを示唆する。逆に言えば、Ｄｅｌｔａ＿ｌのより大きな値は、減少する電力レベルで希薄な干渉しかないことを意味し、したがって、より低い電力レベルでスペクトル再利用のより多くの機会があることを示唆する。したがって、干渉グラフ３００、３０１及び３０２について表２で与えられるＤｅｌｔａ＿ｌは、チャネル及びネットワークセットを構築するために用いられる。
［表２］それぞれ図３Ａ、３Ｂ及び３Ｃの干渉グラフ３０１及び３０２のノード階級変化（Ｄｅｌｔａ＿ｌ）
【表２】
2015056897.tif 000004
【００３１】
さらに、利用可能チャネルの合計数は最小電力レベル（Ｉ−１）に対応する干渉グラフの最大ノード階級より大きいとする。
【００３２】
さらに、所与の電力値（ｐ＿ｌ）で、アルゴリズムは、チャネルセット（Ｓ＿ｌ）内のチャネル数を、ネットワークセット（Ｎ＿ｌ）内のネットワークを有する干渉グラフ（Ｇ＿ｌ）の最大ノード階級より大きくする。この更新設計メトリックは、全てのチャネルに渡って１つの電力レベルのみを有する整数チャネル配置ソリューションを保証できる。
【００３３】
空白帯域内の並列リソース管理のためのアルゴリズムの一実施形態を詳細に記載する。種々の注釈及び対応する定義は、以下の表３に記載する。
【００３４】
表記：定義
ｐ＿ｌ：電力レベルｌの電力値
Ｓ＿ｌ：最大電力値ｐ＿ｌで動作し得る（利用可能チャネルからの）チャネルのセット
Ｎ＿ｌ：チャネルセットＳ＿ｌからのチャネルが配置されるネットワークのセット
【数１】
2015056897.tif 000005
：全てのネットワークのセット、ネットワークセットの構築後、
【数２】
2015056897.tif 000006
【００３５】
Ｉ＿ｌ：干渉グラフであって、ノードはネットワークを示し、エッジは２つのネットワークが干渉するか否かを反映し、全てのノードは最大電力レベルｐ＿ｌで送信する
Ｇ＿ｌ：ネットワークセットＮ＿ｌに対応する電力レベルＰ＿ｌにおける干渉グラフ
Ｄｅｌｔａ＿ｌ：前の電力レベル（Ｉ＿｛ｌ−１｝）におけるグラフに対して、電力レベル（Ｉ＿ｌ）におけるグラフのノード階級変化
＼ｄｅｌｔａ＿ｌ：グラフＧ＿ｌ内の最大ノード階級。
【００３６】
本願明細書に記載のアルゴリズムは、Ｏ（ＫＬ２Ｎ３）の多項式時間複雑性を有し得る。内側ループは、Ｄｅｌｔａ＿ｌの値に渡り、最大可能ノード階級変化Ｎ−１まで繰り返しても良く、最大Ｌ回の繰り返しを有する。チャネルセット更新は、最大（Ｌ−１）＊Ｋ（合計チャネル数）まで繰り返しても良い。再利用ペアを調べることは、Ｏ（Ｎ２）の複雑性を有し得る。得られたチャネル及びネットワークセットについて、所望のチャネル配置アルゴリズム（本願明細書には詳細に記載されない）は、各チャネルセットからのチャネルを対応するネットワークセットに分配するために並列に実行されても良い。例えば、チャネル配置アルゴリズムは、多項式時間複雑性を有する欲張りグラフ着色及び／又は別のアルゴリズムに基づいても良い。したがって、本願明細書に記載の全体の共同電力制御及びチャネル配置ソリューションの複雑性は、多項式にされる。
【００３７】
本願明細書に記載のチャネル及びネットワークを分割するためのアルゴリズムは、少なくとも、Ｎ個のネットワークの識別情報及び位置情報を入力として受信しても良い。特定の実施形態では、本願明細書に記載のアルゴリズム及び方法は、本願明細書に記載の方法の出力に対応する空白データベースが推奨電力レベルを有するチャネルのリストを各ネットワークに提案するよう、空白データベースマネジャにより実施されても良い。このようなサービスは、特定のＦＣＣ規制により明示的に許可され、ＩＥＥＥ８０２．１９．１のような標準によりサポートされ得る。さらに、ネットワーク及びチャネルを分割する中央エンティティは、さらにチャネル配置アルゴリズム（本願明細書に詳細に記載しない）を実行しても良く、生成されたネットワークセット及びチャネルセットに基づき、対応する電力レベルを有する直交チャネルを各ネットワークに配置しても良い。
【００３８】
第１のステップでは、アルゴリズムは、利用可能チャネルをバラバラなチャネルセットＳ＿ｌに分割するステップを有する。ここで、Ｓ＿ｌ内の各チャネルは、電力値ｐ＿ｌに対応する最大電力レベルで送信しても良い。図３Ａ〜３Ｃに関して上述したように、各電力レベルｌについて、干渉グラフＧ＿ｌは、最低利用可能スペクトル帯域の動作周波数が用いられるという仮定の下で構築されても良い。したがって、Ｇ＿ｌは、所与の電力レベルの帯域幅の観点で、最も保守的なグラフを表す。
【００３９】
第２のステップでは、アルゴリズムは、利用可能なネットワークをバラバラなセットに分割するステップを有しても良い。ここで、ネットワークセットＮ＿ｌ内のネットワークは、セットＳ＿ｌからチャネルを配置されても良い。留意すべきことに、ネットワークセットＮ＿ｌ内のネットワークは、異なるチャネルセット内のチャネルを集約するときこれらのチャネルからのより大きな電力レベルを低減することを要求し得る空白規則に従うために、単一のチャネルセットＳ＿ｌのみからチャネルを配置されても良い。さらに、ネットワークセットＮ＿ｌは、Ｓ＿ｌ内のチャネル数が所与のグラフＧ＿ｌの＼ｄｅｌｔａ＿１の値より大きくなるよう、構築されても良い。グラフ着色理論から、この条件は、アルゴリズムに対し整数チャネル配置ソリューションを保証する。
【００４０】
アルゴリズムの１つの目的は、先ず、可能な限り多くのネットワークでより大きな電力レベルを有するチャネルを利用すること、次にスペクトル再利用を増大することであり得る。したがって、ネットワークは、これらのネットワークに配置すべき十分なチャネルがチャネルセットＳ＿ｌ’内に存在する限り、（より大きな電力レベルｐ＿ｌ’に対応する）ネットワークセットＮ＿ｌ’に含まれる。次に、より低い電力レベルにおけるネットワークセットが更新されても良い。これらのより低い電力レベルのネットワークセットは、より低い密度の干渉グラフを有し得るので、それらは、所与のチャネルでより多くの再利用選択肢を提供し得る。
【００４１】
アルゴリズムで用いられる経験則アプローチは、以下の観察結果が動機となる。−（実質的に同じ帯域幅について）より大きな電力の使用がより大きな信号対雑音比（signal−to−noise  ratio：ＳＮＲ）をもたらし、したがって達成可能スループットを向上し得る。−より大きな帯域幅の使用（つまり、実質的に同じ電力レベルを有する１より多いチャネルの集約）が、達成可能スループットを向上し得る。
【００４２】
しかしながら、より小さな帯域幅（例えば、１つの空白チャネル）を有するより大きな電力レベルの使用は、より大きな帯域幅を有するより小さな電力レベルの使用（例えば、２つのチャネルの集約）より良好なスループットを達成できる。なぜなら、最大送信電力は、集約され得るチャネルの数に関係なく、最低使用可能電力レベルに制限されるからである。
【００４３】
したがって、特定の設計基準がアルゴリズムに適用されても良い。一例としては、チャネルセットは、最大電力レベルｐ＿ｌを有する任意のチャネルを含むチャネルセットから開始して構築されても良い。また、ネットワークセットは、より大きな電力レベル内の、特により小さなＤｅｌｔａ＿ｌ値を有するネットワークを含むネットワークから開始して構築されても良い。なぜなら、このようなネットワークは、より低い電力レベルでのチャネル再利用の可能性がより小さいからである。このように、電力リソースの利用を増大するために、これらのネットワークは、Ｓ＿ｌ内で十分なチャネルが利用可能である限り、Ｎ＿ｌ内に含まれる。さらに、チャネルセットは、Ｓ＿ｌ内で十分なチャネルが利用可能でないとき、任意の残りのネットワークに含まれるよう、更新されても良い。ここで、Ｄｅｌｔａ＿ｌは０、１、．．．、Ｎ−１の任意の値を取る。チャネルセット構築基準に従い、チャネルセットは、一度に１つのチャネルを、最大電力値ｐ＿ｋに対応するチャネルセットからｐ−｛ｋ−１｝を有するチャネルセットへ移動することにより更新されても良い。ここで、ｋはＬ，Ｌ−１，．．．，２を取り得る。
【００４４】
図４を参照すると、並列空白リソース管理のための方法４００の一実施形態の選択された要素のブロック図がフローチャート形式で示される。上述のように、方法４００は、最大Ｌ個の電力レベルまでの異なる電力レベルを有する幾つかのチャネルで、Ｎ個のネットワークがＫ個の空白チャネルを共有する場所のために用いられても良い。方法４００は、管理システム２００により実行されても良く、並列リソース管理２１４（図１及び２を参照）により実行される動作を表しても良い。留意すべきことに、方法４００に示した特定の動作は、必要に応じて再配置され又は省略されても良い。
【００４５】
方法４００は、動作４０１で開始し得る。幾つかの実施形態では、Ｎ個のネットワーク及びそれらの個々の位置は、動作４０１中に（又はその前に）識別されても良い。例えば、管理システム２００は、Ｎ個のネットワークの識別情報及び位置を受信し、次に対応するネットワークセット及びチャネルセットを出力しても良い。チャネルセットは、最大電力レベル値を有するチャネルから開始して初期化されても良い（動作４０２）。チャネルセットは、Ｓ＿ｌ＝｛最大電力レベルｐ＿ｌを有するチャネルの集合｝として初期化されても良く、ここでｌ＝１，２，．．．，Ｌである。Ｌ個の電力レベルに対応するネットワークセットは、初期化されても良く（動作４０４）、最大電力ネットワークセット内のネットワーク数を最大化するステップと、最大電力ネットワークセット以外のネットワークセットを空にするステップと、を含む。最大電力ネットワークセットは、最大電力レベルに対応する。ネットワークセットＮ＿１，．．．，Ｎ＿｛Ｌ−１｝は、先ず可能な限り多くのネットワークで最大電力レベルを有するチャネルを利用するという目的を達成するために最初に空にされても良い。したがって、可能な限り多くのネットワーク／再利用（近隣でない、したがって同じ割り当てられたチャネルを再利用し得るネットワークの対）がＮ＿Ｌに含まれても良い。したがって、対応するグラフＧ＿Ｌはノード階級＼ｄｅｌｔａ＿Ｌ＝０を有する（つまり、グラフＧ＿Ｌは不連続グラフである）。複数のネットワーク／再利用ペアから１つを選択することが要求されるとき、再利用ペアと共に最小のＤｅｌｔａ＿Ｌを有するネットワークが存在する場合、該ネットワークは、Ｎ＿Ｌに含まれても良い。
【００４６】
したがって、Ｓ＿Ｌ内に少なくとも１つのチャネルを有することにより、Ｎ＿Ｌ内のネットワークは、配置されたチャネルを得る。空のネットワークセットでは、＼ｄｅｌｔａ＿ｌ＝−１は、最初に定義されても良く、電力レベルｐ＿ｌを有する利用可能なチャネルに従って所与のネットワークセットＮ−１により多くのネットワークを追加するための条件を評価するために用いられても良い。
【００４７】
次に、方法４００で、各ネットワークがネットワークセットに含まれるか否かの決定が行われても良い（動作４０６）。動作４０６の結果がＹＥＳのとき、ネットワークセット及びチャネルセットは出力されても良く（動作４０８）、方法４００は終了しても良い（動作４１０）。動作４０６の結果がＮＯのとき、ネットワークセットは更新されても良い（動作４１２、図５も参照）。動作４１２の結果に依存して、方法４００は、動作４０６に戻るか、又は一度に１つのチャネルを次に低い電力レベルにあるチャネルセットへ移動することによるチャネルセットの更新（動作４１４）に進んでも良い。言い換えると、１つのチャネルは、動作４１４で、Ｓ＿ｋからＳ＿｛ｋ−１｝へ移動されても良い。チャネルセットは、一度に１つのチャネルを最大電力レベルに対応する空でないチャネルセットから、ｐ−｛ｋ−１｝を有するチャネルセットへと移動することにより更新されても良い。これは、より多くのネットワークがより低い電力レベルに対応するセットに含まれる可能性を増大し得る。次に、電力レベル＝２のチャネルセットが空か否かの決定が行われても良い（動作４１６）。動作４１６の結果がＮＯのとき、方法４００は、動作４０４へ戻っても良い。動作４１６の結果がＹＥＳのとき、単一のネットワークセット及びチャネルセットは出力されても良く（動作４１８）、方法４００は終了しても良い（動作４１０）。ネットワークセットＮ＿２について、（最大ｎ＿２個のネットワーク／再利用ペアが既に含まれているため）Ｎ２に含まれないＤｅｌｔａ＿２の所与の値を有する動作４１４における任意の残りのネットワークは、最小電力レベル（したがって、最大再利用可能性）を有するチャネルセットに対応するＮ＿１に含まれても良い。しかしながら、Ｎ＿１内のチャネル数が十分ではない（つまり、＼ｄｅｌｔａ＿１＋１より少ない）場合、ネットワーク分割は実現可能ではなく、現在のチャネルセットは更新されることが望ましい。ネットワーク分割が実現可能ではないとき、Ｓ＿１は、全ての利用可能チャネルのチャネルセットを表しても良く、Ｎ＿１は、全ての利用可能ネットワークのネットワークセットを表しても良く、（ｌの他の値について）全ての他のチャネルセット及びネットワークセットは空のままである。
【００４８】
図５を参照すると、並列空白リソース管理のための方法５００の一実施形態の選択された要素のブロック図がフローチャート形式で示される。
【００４９】
方法５００は、方法４００（図４を参照）に関して上述した動作４１２の一実施形態を表し得る。留意すべきことに、方法５００に示した特定の動作は、必要に応じて再配置され又は省略されても良い。方法５００は、より大きい電力レベルから、ネットワークセットを更新することで開始しても良い。特に、Ｎ＿ｌについて、（Ｄｅｌｔａ＿ｌ＝０を有するネットワークから開始して）より小さなＤｅｌｔａ＿ｌを有するネットワークは、前述のように最初に含まれても良い。Ｎ＿ｌに含まれるネットワークの数は、Ｓ＿ｌ内の利用可能チャネル数及びＧ＿ｌの現在の最大ノード階級に依存しても良い。実現可能なチャネル配置を提供するために、任意の値のＤｅｌｔａ＿ｌについて、残りのネットワークセット（つまり、
【数３】
2015056897.tif 000007
）から最大ｎ＿ｌ＝｜Ｓ＿ｌ｜−＼ｄｅｌｔａ＿ｌ−１個のネットワーク／再利用ペアが、ネットワークセットＮ＿ｌに含まれる（そして、次に＼ｄｅｌｔａ＿ｌが更新される）。Ｄｅｌｔａ＿ｌの所与の値の任意のネットワークについて、方法５００は、他の隣接しないネットワークが存在するかどうかを調べても良い。
【００５０】
次に、ネットワークは、（妥当な場合）その再利用ペアと一緒に選ばれても良い。各再利用ペアは、１つのグループとして数えられる。さらに、再利用ペアを含むために、ネットワークより高い優先度が与えられても良い。複数の（ｎ＿ｌより多い）選択肢が利用可能な場合、最小和Ｄｅｌｔａ＿ｌを有する再利用ペアがランダムに、選択され、最終的に関係を切断されても良い。
【００５１】
方法５００は、カウンタｉをインクリメントし及びｌ＝ｋを設定することにより開始しても良い（動作５０２）。
【００５２】
次に、ループを開始するために、ｌ＞１か否かの決定が行われても良い（動作５０４）。動作５０４の結果がＮＯのとき、方法５００は、ループを終了し、動作５１４（後述する）に進んでも良い。動作５０４の結果がＹＥＳのとき、方法５００は、ｎ＿ｌ＝｜Ｓ＿ｌ｜−＼ｄｅｌｔａ＿ｌ−１としても良い（動作５０６）。次に、ｎ＿ｌ＞０か否かの決定が行われても良い（動作５０８）。動作５０８の結果がＹＥＳのとき、Ｎ＿ｌ内のＤｅｌｔａ＿ｌ＝ｉを有する残りのネットワークセット（つまり、
【数４】
2015056897.tif 000008
）から最大ｎ＿ｌ個の再利用ペア及びネットワークが選択されても良い（動作５１０）。動作５１０の後、又は動作５０８の結果がＮＯのとき、ｌはデクリメントされても良く（動作５１２）、方法５００は動作５０４に戻っても良い。動作５０４の結果がＮＯのとき、方法５００は、ｎ＿１＝｜Ｓ＿１｜−＼ｄｅｌｔａ＿１−１としても良い（動作５１４）。次に、ｎ＿１＞０か否か、及び（Ｄｅｌｔａ＿２＝ｉ）を有する再利用ペア及びネットワークの数＜＝ｎ−１か否かの決定が行われても良い（動作５１６）。動作５１６の結果がＮＯのとき、方法５００は、方法４００（図４参照）の動作４１４へ戻っても良い。
【００５３】
動作５１６の結果がＹＥＳのとき、（Ｄｅｌｔａ＿２＝ｉ）を有する再利用ペア及びネットワークは、Ｎ＿１に含まれても良く（動作５１８）、その後、方法５００は、方法４００（図４参照）の動作４０６へ戻っても良い。
【００５４】
図６Ａ及び６Ｂを参照すると、例示的な並列空白リソース管理の一実施形態の選択された要素が示される。図６Ａ及び６Ｂの例では、図４及び５に関して上述したアルゴリズムは、３個の空白チャネル（ａ、ｂ及びｃ）を共有すると仮定される４個のネットワーク（Ｎ１、Ｎ２、Ｎ３及びＮ４）のトポロジに適用される。図６Ａで、干渉グラフ６００は、グラフＧ＿１内の電力レベル１についてのトポロジを示し、４０ｍＷの電力レベル１値におけるチャネルａ及びｂに対応する。図６Ｂで、干渉グラフ６０１は、グラフＧ＿２内の電力レベル２についてのトポロジを示し、１００ｍＷの電力レベル２値におけるチャネルｃに対応する。
【００５５】
一例では、電力制御が用いられないとき（つまり、全てのチャネルが４０ｍＷの電力レベルで送信する）、幾つかの場合には、ネットワークは１０ＭＨｚの帯域幅を得て、幾つかの場合には、ネットワークは５ＭＨｚの帯域幅を得る（合計３０ＭＨｚの利用を有する）。したがって、平均して、各ネットワークは、約７．５ＭＨｚの帯域幅を割り当てられ得る。本願明細書に記載のアルゴリズムを用いて、次の結果が得られる。Ｓ＿１＝｛ａ，ｂ｝、Ｓ＿２＝｛ｃ｝、Ｎ＿１＝｛１，４｝、及びＮ＿２＝｛２，３｝である。
【００５６】
留意すべきことに、このアルゴリズムは、ネットワークセット及び対応するチャネルセットを生成し、チャネルセットからのチャネルが対応するネットワークセットに配置されるようにする。次に、要求に応じて、種々の追加の方法が、チャネル配置のために用いられても良い。
【００５７】
チャネル配置の後、例えば、ネットワークＮ２及びＮ３は、１００ｍＷ電力においてチャネルｃを割り当てられても良く、一方、ネットワークＮ１及びＮ４は、４０ｍＷ電力においてチャネルａ及びｂの両方を割り当てられても良い。非協調性基準ポリシでは、Ｗｉ−Ｆｉネットワークは最小の輻輳を有するチャネルを選択し、ＬＴＥネットワークは最小干渉レベルを有するチャネルを選択する。協調直交チャネル配置と共により多くの電力レベルを利用することにより、非協調性基準ポリシに比べて及び電力制御ポリシを使用しない場合に比べてスループット性能が有意に向上され得ることが分かる。特に、（ＩＥＥＥ８０２．１１アクセス技術を用いると仮定して）ネットワークＮ２及びＮ３は、非協調性基準ポリシでもより大きな平均帯域幅を割り当てられるが、ネットワークＮ２及びＮ３のスループット性能は、より大きな電力だがより小さい帯域幅を割り当てる本願明細書に記載のアルゴリズムを用いた電力制御を有する場合より悪い。（ＬＴＥアクセス技術を用いると仮定して）ネットワークＮ１及びＮ４では、このような場合に割り当てられる帯域幅が１０ＭＨｚにおいて残っており、一方で非協調性基準ポリシを用いるとネットワークＮ１及びＮ４は幾つかの場合には５ＭＨｚ及び平均して７．５ＭＨｚしか得られないので、スループット性能は、本願明細書に記載の方法を用いると良好であることが分かる。
【００５８】
以上に開示した主題は、説明のためであり、限定ではないと考えられるべきである。また、添付の特許請求の範囲は、本開示の真の精神及び範囲に包含される全ての変更、拡張及び他の実施形態を包含することを意図している。したがって、法により認められる最大範囲まで、本開示の範囲は、特許請求の範囲及びその等価物の最も広い許容可能な解釈により決定されるべきであり、前述の詳細な説明により限定又は制限されるべきではない。
【符号の説明】
【００５９】
１００  ネットワーク
１０２  無線ネットワーク
１０４  ユーザ機器
２００  管理システム
２２０  ネットワークアダプタ
２０１  プロセッサ
２０２  共有バス
２１０  記憶媒体
２１２  ＯＳ
２１４  並列リソース管理
２２４  命令
【図１】
2015056897.tif 000009
【図２】
2015056897.tif 000010
【図３Ａ】
2015056897.tif 000011
【図３Ｂ】
2015056897.tif 000012
【図３Ｃ】
2015056897.tif 000013
【図４】
2015056897.tif 000014
【図５】
2015056897.tif 000015
【図６Ａ】
2015056897.tif 000016
【図６Ｂ】
2015056897.tif 000017