反復リソース重みの更新を用いて通信システムにおいてノードにリソースを配分する装置及び方法
【課題】通信システムにおいてノードにリソースを配分する装置が提供される。
【解決手段】反復処理を実行する反復コントローラ１０を備え、該反復コントローラ１０は、反復リソース重みを用いて（１１）反復ステップのリソース配分結果を得るように、かつ反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて、反復リソース重みを更新して（１２）、更なる反復ステップの更新された反復リソース重みを得るように構成される。
【解決手段】反復処理を実行する反復コントローラ１０を備え、該反復コントローラ１０は、反復リソース重みを用いて（１１）反復ステップのリソース配分結果を得るように、かつ反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて、反復リソース重みを更新して（１２）、更なる反復ステップの更新された反復リソース重みを得るように構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は無線通信に関し、特に、無線ネットワークにおける送信機／受信機ノードのためのリソース配分のタスクに関する。
【背景技術】
【０００２】
ネットワークのカバレッジエリア内のユーザの集合Ｋについて、伝送レートのベクトル
【数１】
によって表される効率的な比例公平レート割当てを見つける問題について述べる。
【数２】
【０００３】
ネットワーク内のユーザのためのレート割当てが図２に示されている。ユーザレートの相互依存性が、達成可能なレート領域Ｒによって表されている。これは凸集合となることが仮定される。レート領域Ｒは、物理層技法、例えばＭＩＭＯ伝送、及びチャネル実現によって構成される。この問題は双対分解によって解くことができることがよく知られている（非特許文献１）。双対問題は、図５に示すアルゴリズムによって説明されているように、主双対アルゴリズムによって解くことができる。
【０００４】
アルゴリズムのリアルタイムの実施を可能にするために、該アルゴリズムの収束速度及び複雑度が主な課題である。アルゴリズムの計算複雑度は、各反復において実行される重み付け合計レート最適化
【数３】
を解く複雑度に支配される。加えて、２つ以上の基地局を有するネットワークにおいてユーザが協調しているとき、各反復によって基地局間にシグナリングオーバーヘッドが生じる。重み付け合計レート最適化を解く複雑度は各反復について一定であるので、主な課題は、解、又は解の係数ε内で証明可能なレート構成を見つけるのに必要な反復数を低減することである。必要な反復数は、双対変数の更新方法に依拠し、双対係数の更新に最も頻繁に用いられる方法は以下である。
・劣勾配法。例えば、更新のための簡単な閉形式の式を有することに着目すると、最も一般的な更新規則である。
【数４】
しかしながら、劣勾配法の欠点は、特に高い確度が必要とされているときに収束が不良であることである。
・切断平面法。双対関数が凸型であり、したがって超平面によって下界を定めることができることに基づいて、切断平面法は構築される。解が見つかるまで、超平面を反復的に用いて、候補点から点の半空間を切り離す。
−楕円法（非特許文献２）は、候補点を含む楕円を用いる。楕円は２つの半楕円になるように反復的に切断され、一方が廃棄される。残りの半楕円を含む新たな楕円の中心が更新値として用いられる。新たな中心λｉ＋１は以下によって計算される。
【数５】
−Kellyの切断平面法（非特許文献３）は、双対関数を超平面によって近似し、線形近似を最小にするものを更新値として用いる。新たな双対変数は、以下の最適化問題の解である。
【数６】
【０００５】
線形近似に超平面を加える様々な変形形態が存在する。加えて、マルチカットと呼ばれる方法が検討される。マルチカット法では、各反復においてユーザあたり１つの超平面が加えられる。マルチカット法は収束速度を劇的に改善するが、双対更新のコストが各反復において大きく増大する。
・Aitkenの方法（非特許文献４）は、劣勾配法に加速モードを加え、結果として、より高速な収束がもたらされるが、アルゴリズムの安定性が問題となる。更新規則は１つの劣勾配ステップを計算し、それによって中間双対ベクトルを見つける。
【数７】
中間双対ベクトルを用いて、
【数８】
及び
【数９】
を計算し、更なる劣勾配ステップを求めることができる。
【数１０】
最後に、
【数１１】
及び
【数１２】
を用いて
【数１３】
を計算する。
【０００６】
双対更新に対し、より多くの計算複雑度が費やされると、収束速度を改善することができることを観測することができる。更新のための閉形式の式を有する方法もあれば、最適化問題を解くことを必要とする方法もある。複雑度及び収束速度は図８に要約されている。
【０００７】
理解されるように、最新技術の方法は、双対更新を計算するのに高い複雑度を有するか、又は収束不良を被るかのいずれかである。収束不良もまた、解く必要がある多数の重み付け合計レート問題に起因して計算的に複雑である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Mung Chiang、S.H. Low、 A.R. Calderbank、及び、J.C. Doyle、「Layering as optimization decomposition: A mathematical theory of network architectures」、Proceedings of the IEEE, 95(1):255-312, Jan. 2007
【非特許文献２】N. Z. Shor、「Convergence rate of the gradient descent method with dilatation of the space」、Cybernetics and Systems Analysis, 6(2):102-108, 1970
【非特許文献３】J.E. Jr. Kelley、「The Cutting-Plane method for solving convex programs」、Journal of the Society for Industrial and Applied Mathematics, 8(4):703-712, December 1960
【非特許文献４】J. Hodgskiss、A. Dekorsy、及び、J. Fliege、「Accelerating a dual algorithm for the simultaneous routing and power control problem」、Proc. IEEE 18thInternational Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC ´07, pages 1-5, 2007
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、通信システムにおいてノードにリソースを配分するための改善された概念を提供することである。
【００１０】
この目的は、請求項１に記載のリソースを配分する装置、請求項１４に記載のリソースを配分する方法、又は請求項１５に記載のコンピュータプログラムに従って達成される。
【課題を解決するための手段】
【００１１】
本発明は、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて反復リソース重みの更新ステップを実行するとき、反復プロセスのはるかに高速な収束速度が得られることの発見に基づく。好ましくは、全ての以前のリソース配分結果が、主双対アルゴリズムにおいて必要な更新された反復リソース重みを計算するために組み合わせられる。
【００１２】
特に、双対変数λｋの更新は、以前のリソース配分結果-の重み付け結合として実行され、ここで、以前の配分結果の各々は関連付けられた重み付け係数を有する。重み付け係数は、好ましくは、以前の反復結果を重み付けするための重みの合計が１に等しいという点で、更なる最適化問題の解となる。
【００１３】
好ましくは、反復ステップのリソース配分結果は、個々のリソースの重み付け合計の最適化に基づいて求められ、ここで反復リソース重みλは個々のリソースの重みであり、最適化は最適化目標及びリソース領域を用いて実行される。リソース領域は、通信システム又はノードの条件によって画定される。一実施の形態では、通信システム又はノードの条件は、ノードと受信機との間の伝送チャネル若しくはノードの内部特性、ノードの伝送電力制約、ノード間の相互干渉、物理層制約、又は伝送プロトコルを含む。好ましくは、ノードを通じて配分されるリソースは、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルである。
【００１４】
好ましくは、前記反復コントローラは、反復ステップにおいて、以前の反復ステップの前記リソース配分結果を該以前の反復ステップの結合重みと乗算したものの重み付け合計の最適化に基づいて新たな結合重みαを計算し、該新たな結合重みと、少なくとも１つの以前の反復ステップの結合重みとの結合が所定の制約値に等しいという条件下で、現在の反復ステップの前記リソース配分結果を前記新たな結合重みと乗算したものを計算するように構成される。
【００１５】
好ましくは、前記装置は、以前の反復ステップから現在の反復ステップまでに得られた前記リソース配分結果を格納し、以前の反復ステップから現在の反復ステップまでの前記重み付け結合の結合重みを格納するメモリを更に備える。
【００１６】
前記装置は、前記通信システム又は前記ノードの条件によって画定されるリソース領域に関する情報を受信する入力インターフェースと、前記反復コントローラによって実行される最終反復ステップの前記リソース配分結果を出力し該最終反復ステップの該リソース配分結果を用いて前記ノードが構成可能になるようにする出力インターフェースと、を更に備えることが好ましい。
【００１７】
好ましくは、前記ノードは移動端末であり、前記システムは基地局を含み、前記配分する装置は、最終反復ステップの前記リソース配分結果を前記基地局に提供するように構成される。
【００１８】
本発明の実施の形態は、マルチユーザシステムのための効率的な比例公平レート割当てを構成する。本発明は、好ましくはマルチユーザシステムのための効率的な比例公平レート割当てを計算するのに用いられる双対分解に基づくアルゴリズムのための新規の双対更新方法及び双対更新装置を提供する。新たな概念は、既存の方法と比較して優れた収束速度をもたらす。既存の方法と対照的に、本発明の実施の形態は、各反復において性能を厳密に改善する。本発明の概念は、軽微な追加コストを生じさせることによって、必要な反復数を劇的に低減し、したがって複雑度の全体的な低減を可能にする。
【発明の効果】
【００１９】
本発明は、無線通信の分野、送信技術の分野、協調マルチポイント（ＣｏＭＰ）送信の分野において、比例公平レート割当てが必要とされているときに有用である。
【００２０】
次に、本発明の好ましい実施形態を添付の図面に関して説明する。
【図面の簡単な説明】
【００２１】
【図１】通信システムにおいてノードにリソースを配分する方法のための装置を示す図である。
【図２】マルチユーザマルチセル／ＣｏＭＰ ＭＩＭＯシステムのための、ダウンリンク送信におけるユーザへのレート割当てを示す図である。
【図３】複数の反復にわたる、従来技術の方法と比較した本発明の性能を示す図である。
【図４ａ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｂ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｃ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｄ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｅ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｆ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｇ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｈ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｉ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図５】単純な主双対アルゴリズムを示す図である。
【図６】特定の更新規則を用いた本発明の主双対アルゴリズムを示す図である。
【図７】従来技術の方法に対する本発明の性能を示す図である。
【図８】本発明の概念と比較した従来技術の方法の様々な特性を要約した表である。
【発明を実施するための形態】
【００２２】
図２は、本発明を適用することができる問題を示している。問題のシナリオは、幾つかのセル２０１、２０２、２０３、２０４を含み、各セルは基地局２１０及びいくつかの移動端末２１１を含む。ここで、解くべき問題は、各移動端末２１１が、伝送レート、複数の周波数チャネル、複数の或るサイズのタイムスロット、周波数スロット、コードスロット、又は空間チャネル等の或る送信リソースを受けるべきであることである。特に、無線状況は、全ての移動端末２１１が或る意味互いに影響するようになっており、この互いに対する相互依存性は、通常達成可能なレート領域Ｒによって表される。達成可能なレート領域Ｒは、例えば凸集合であると仮定されるが、本発明では必ずしも必要とされない。レート領域Ｒは、物理層技法、例えばＭＩＭＯ送信、及びチャネル実現によって構成される。非特許文献１に示されているように、この問題は双対分解によって解くことができ、双対問題は、図５に示すような主双対アルゴリズムによって解かれる。特に、公平レート配分が必要とされ、これは、ゼロリソースを受け取るユーザが存在せず、全体としてリソースが最大にされることを確保すべきであることを意味する。言い換えれば、或るセル内のユーザ２１１が最大レートを受けるとき、これは、この強力な送信機の近傍の他の送信機が小さなレートしか有することができない可能性があることを意味するが、双方の送信機が非常に類似したレートを取得すれば、総全体レートがより高くなる可能性がある。しかしながら、これは最終的に異なる伝送チャネル、物理層等に依拠する。一方、ユーザのレートは、セルエッジのユーザに対しても高スループットを達成し、これによって全てのユーザに対し高いユーザ満足度を達成するには、比例公平配分されなくてはならない。通常、レート領域Ｒの明確な記述は利用可能でないため、図５に示すように、反復アルゴリズムが用いられる。このプロセスでは反復が実行され、該反復において、現在の双対変数（重み）に従って重み付け合計レートの解が計算され、解が最適でない限り双対変数が更新される。
【００２３】
従来技術の方法における双対変数更新の計算複雑度は過度に高く、多くの反復が必要とされ、高い総計算複雑度がもたらされることがわかっている。ここで、主な複雑度は重み付け合計レート問題を解くことにあり、セル間連携の場合、高いシグナリングオーバーヘッドが必要となる。
【００２４】
本発明によれば、双対変数の更新規則は、反復リソース重みλを更新するために、反復リソース重みλｉ＋１が、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて更新されるという点で強化されている。好ましくは、レート領域の近似が反復的に改善され、双対変数（ユーザ間のレート分布の重み）を更新するために用いられる。新たな更新規則は小さな計算複雑度を有し、高い収束速度をもたらす。したがって、新たな概念は低減された全体複雑度を有する。これは図８の最終行に要約されている。
【００２５】
図７及び図８のシミュレーションのために、六角形グリッド内に配置された１９個のサイト、サイトあたり３つのセクター、サイト間距離５００メートル、ラップアラウンド構成、３ＧＰＰ ＴＲ３６０．８１４に従ったチャネルモデル、都市型マクロセル、４×４ＭＩＭＯ構成、及び均一に分配されたセクターあたり平均５人のユーザでの、マルチセル／ＣｏＭＰシミュレーションセットアップが用いられる。
【００２６】
図１は、図２に示す通信システム２００においてノード２１１にリソースを配分する装置を示している。装置は、反復処理を実行する反復コントローラ１０を備え、該反復コントローラは、１１及び１２で示すように構成される。参照符号１１は反復コントローラの構成を指し、該構成において、反復コントローラは、反復リソース重みλを用いて反復ステップのリソース配分結果ｒ＊を得るように構成されている。参照符号１２は、反復コントローラが、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて、反復リソース重みλを更新して、更なる反復ステップの更新された反復リソース重みλｉ＋１を得るように更に構成されていることを示す。また、装置は、例えば、物理層技法、例えばＭＩＭＯ伝送、及びチャネル実現によって構成することができる達成可能なレート領域に関する情報を受信する入力インターフェース１３を備える。また、装置は、反復プロセスの終了後、すなわち終了判断基準が満たされたとき、最終配分結果を提供する出力インターフェース１４を備える。
【００２７】
最終配分結果は、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルを含むことができる。例えば、或るビットレートに或る最小ビット誤り率が必要とされるとき、伝送電力は或る値に設定されなくてはならない。一方、伝送電力が同じままであるとき、例えば、より高いか又はより低い信号点配置図を有する様々な緩和方法（moderation method）によって制御することができる、より高いか又はより低い最小信号対雑音比を割り当てて、レート割当ても実行することができる。したがって、リソース配分は、送信機内で、或る伝送電力設定及び／又はマッピング規則（信号点配置図）の或る選択において、或る量の転送誤り訂正コーディングにおいて現れ、すなわち、より高い冗長性は、より低い伝送レートを意味するが、高められた信号対雑音比を意味する。或る利用可能な再送信規則等のより複雑な課題をレート割当てに含めることができる。
【００２８】
このため、最終的な配分結果は出力インターフェースを介して送信ネットワーク内の個々の送信機に通信されるか、又はまず図２の基地局２１０に送信され、次に、基地局からこの基地局に関連する送信機２１１に送信される。
【００２９】
双対変数の更新のために、以下が提案される。
【数１４】
ここで、α＊は以下の最適化問題の解である。
【数１５】
【００３０】
問題は、単純な制約集合にわたって２回微分可能な凹関数を最大化することであって、このために非常に高速で効率的なアルゴリズムが存在する。新たな更新メカニズムを有する主双対アルゴリズムが図６に要約されている。ここで、いくつかのステップが省かれていることに気付くことができる。
【００３１】
新規の双対更新方法の主な寄与は、
・優れた収束速度、
・各反復の効用の改善が保証され、ステップサイズ制御が必要とされないこと、
・複雑度の全体的な低減、
である。
【００３２】
実施形態は、複数ユーザを有する通信システムにおいて或る効用関数を最大化することを目的とし、レート領域の区分線形近似を仮定した効用最大化問題の解を含み、結果のユーザレートの要素単位の反転を更に含むアルゴリズムにおいて双対変数を更新する概念を含むことが好ましい。
【００３３】
好ましくは、本発明は、レート領域の区分線形近似の品質を改善する双対変動更新規則の反復的な実行を含む。効用関数は、比例公平レート配分に従って実行されることが好ましい。また、本発明は、基地局が連携し、基地局及び移動ノードが複数のアンテナを有する通信システムに適用されることが好ましい。
【００３４】
マルチユーザシステムのための効率的な比例公平レート割当てを見つけることは、効用最大化問題によって計算される。
【数１６】
【００３５】
この問題は双対分解によって解かれ、ここで双対関数ｄ（λ）は以下である。
【数１７】
【００３６】
Ｕｐは自身の最大値を達成する凸最適化問題であるので、双対問題は同じ最適値
【数１８】
を有する。双対問題ＵＤは、
【数１９】
であり、
【数２０】
に等しい。これは、閉じた凸集合は、閉じた半空間の交差として特徴付けることができるためである。通常、Ｒを完全に記述するのに必要な半空間の数は無限であり、これによってＵＤを直接解くことができない。したがって、アルゴリズム１を採用することができ、各反復において、代替問題を定式化することができる。
【数２１】
この代替問題は、各反復において解かれる重み付け合計レート最適化問題
【数２２】
から得られる有限の点集合
【数２３】
を用いて機能する。明らかに、ＡＰの最適値は問題ＵＤの最適値の下限であり、自由度がより低い。以下で、双対変数の更新値としてＡＰを最適化したものを反復的に用いることによって、最終的にε最適解である
【数２４】
又は
【数２５】
となるまで界が狭まることが数学的に証明されている。
【００３７】
近似問題に対する解決策
このセクションでは、凸最適化問題である
【数２６】
の解を計算する方法を検討する。ラグランジュ関数は以下の通りである。
【数２７】
【００３８】
定理１：所与の双対変数αのラグランジュ関数の最小値である双対関数θ（α）が以下によって与えられる
【数２８】
【００３９】
説明：ｚは制約されていないので、ｚを任意に小さくすることができ、したがって
【数２９】
でない限りθ（α）＝−∞である。この場合、
【数３０】
であり、
【数３１】
から、
【数３２】
となる。
【００４０】
これを式（１）に代入すると、
【数３３】
の場合に以下となることを結論付けることができる。
【数３４】
【００４１】
定理１から、双対問題ＡＤ（ｉ）、すなわち
【数３５】
は以下の問題に等しいことを結論付けることができる。
【数３６】
【００４２】
この問題は、比例公平性効用を最大にするレート点ｃ１，．．．，ｃｉの凸結合を見つけることを意味する。ＡＤ（ｉ）の解ａ＊を式（２）に代入することによって、提案された更新規則がもたらされる。最終的に、アルゴリズムによって、効用が解に収束するまで、各反復において効用が厳密に改善されることを証明することが可能である。
【００４３】
シミュレーション結果
図３は、１つのチャネル実現のための複数の反復にわたる効用を示している。ここで、収束性能を検証することができる。Aitkenのプロセスは、安定性を確保するための慎重なステップサイズ制御を必要とし、これは本発明者らの実験において達成することができなかった。提案された方法によって、最良の収束速度が提供されることを理解することができる。切断平面法は、更新値を計算するのに比較可能な複雑度を有するが、本方法による目覚しい利得を見て取ることができる。マルチカット方法は良好な性能をもたらすが、本発明の一実施形態による方法よりも高い複雑度を有する。
【００４４】
アルゴリズムは、部分的再利用方式を用いた、より大規模なネットワークにおいても研究されている。反復数が過度に高い（１，０００〜１，０００，０００）ので、劣勾配アルゴリズム、楕円アルゴリズム、及び切断平面アルゴリズムはこのシナリオには適用可能でない。図７は、本方法がマルチカット法をはるかに凌ぐ一方で、より低い複雑度を有することを示している。マルチカット法のｉ番目の反復において解かれなくてはならない線形問題の制約数は（Ｋ＋１）ｉ個の制約を有し、これは最後の反復では７０００個を超える。一方、新規の手法は、単純な制約を有する凸問題において、ｉ番目の反復においてｉ個の変数を有する。数ステップのうちに最適条件に近い（９０％〜９５％）構成に到達することができ、これによって新規の方法が実際の実施に対して現実的となることに注目されたい。
【００４５】
続いて、図６に示すアルゴリズムを、図４ａ〜図４ｉを参照して詳細に論じる。図４ａ〜図４ｉを検討するとき、完全な一貫性を有するために、図ａ〜図ｉにおいてパラメータｃがパラメータｒに置き換えられることに留意されたい。しかしながら、ｃ及びｒはともに同じもの、すなわちリソース配分結果を意味する。特に、ｒｍ又はｃｍは、検討中のユーザグループの特定のユーザｍのリソース配分結果を示している。このため、ｒｍ又はｃｍは、ユーザｍの伝送レート、ユーザｍの周波数チャネル、ユーザｍのタイムスロット、ユーザｍのコードスロット、又はユーザｍの空間チャネルとすることができる。加えて、各ユーザリソース配分結果ｒｍが関連付けられたλｍを有するように、反復リソース重みλが各ユーザに関連付けられる。また、一方、ｍ＊は、反復ステップのリソース配分結果と少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合において用いられる或るユーザｍの重み付け係数である。
【００４６】
図４ａは、Ｒの境界上の点を見つけるのに用いることができる重み付け合計レート最大化（ＷＳＲＭａｘ）を示している。ここで、Ｒは、全ての物理パラメータ及び伝送チャネル等の表現である、いわゆる達成可能なレート領域Ｒである。λをｒと乗算した積が、レートが許容レート領域内にあることを条件として最大化されることになる。図４において見て取ることができるように、直線４０が存在し、ここで、特定の直線４１は、或る点においてレート領域に接し、反復リソース重みλによって規定されたベクトルは線４１に直交する。図４ｂは、図６と比較してわずかに異なる表現で反復アルゴリズムを示している。特に、更新ステップ２が示され、該ステップは、λを引数とした重み付け合計レート最大化の後に実行される。特に、図４ｂはレート領域の反復的探査を示しており、反復当たりのコストが、最適化問題、ＷＳＲＭａｘ、及びλを更新するときに全ての送信機間で必要とされるシグナリングによって与えられる。主な目標は、反復数を劇的に低減することである。
【００４７】
図４ｃは、レート領域の別の反復的探査を示しており、ここで、異なる線４２は図４ａに対し異なる勾配を有し、線４３はリソース配分結果ｒにおいてレート領域境界に接し、ここでもλは線４３に直交している。
【００４８】
図４ｄは、重み付け合計レート最適化を用いた最初の反復ステップを示している。ここで、レート領域が再び示され、関連付けられた更新重みλ１を有する第１の反復結果がｒ１において見つかる。次に、図４ｅに示すように、レート領域の内部近似が実行される。更新ステップが図４ｅに示されている。次に、図４ｆにおいて、反復２が実行されるが、今度は図４ｅにおいて計算された異なるλを用いて実行され、これは、線５０がレート領域Ｒに接する点が求められることを意味し、この点はｒ２に対応する。次に、図４ｇに示すように、レート領域の内部近似が再び実行され、反復２において、ｒ２が、２つの以前の反復ステップにおいて求められたｒ１及びｒ２の重み付け結合として計算され、次にこのｒ２を用いて、λ更新値が、反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合に基づくように新たなλ３を最終的に計算する。
【００４９】
次に、図４ｈに示すように、反復３によって結果としてｒ３がもたらされる。言い換えると、図４ｇにおいてλ３が計算され、図４ｈにおいて、λ３によって求められた勾配を有する直線がレート領域に接する点が求められる。このため、第３の反復の結果はｒ３となる。図４ｉに示すように、これより改善された結果を得ることができないので、ここで反復が終了する。
【００５０】
装置との関係でいくつかの態様が説明されたが、これらの態様は対応する方法の記述も表し、ここでブロック又はデバイスは方法ステップ又は方法ステップの特徴に対応することが明らかである。それに類似して、方法ステップに関連して説明された態様も、対応する装置の対応するブロック又はアイテム又は特徴の記述を表す。
【００５１】
或る特定の実施態様要件に依拠して、本発明の実施形態はハードウェア又はソフトウェアにおいて実施することができる。実施態様は、電子的に読取り可能な制御信号が格納されたデジタルストレージ媒体若しくは非一時的ストレージ媒体、例えばフロッピー（登録商標）ディスク、ＤＶＤ、ＣＤ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、又はフラッシュメモリを用いて実行することができ、それらは、それぞれの方法が実行されるようにプログラム可能なコンピュータシステムと連携する（又は連携可能である）。
【００５２】
本発明によるいくつかの実施形態は、本明細書に記載される方法のうちの１つが実行されるようにプログラム可能なコンピュータシステムと連携することができる電子的に読取り可能な制御信号を有する非一時的データ担体を含む。
【００５３】
概して、本発明の実施形態は、プログラムコードを有するコンピュータプログラム製品として実装することができる。該プログラムコードは、コンピュータプログラム製品がコンピュータ上で実行されると、方法のうちの１つを実行するように動作可能である。プログラムコードは、例えば機械可読担体上に格納することができる。
【００５４】
他の実施形態は、機械可読担体上に格納された、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを含む。
【００５５】
したがって、換言すれば、本発明の方法の一実施形態は、コンピュータプログラムがコンピュータ上で実行されるときに本明細書に記載された方法のうちの１つを実行するプログラムコードを有するコンピュータプログラムである。
【００５６】
したがって、本発明の方法の更なる実施形態は、データ担体（又はデジタルストレージ媒体若しくはコンピュータ可読媒体）であって、該データ担体上に記録された、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを含む、データ担体である。
【００５７】
したがって、本発明の方法のまた更なる実施形態は、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを表すデータストリーム又は信号シーケンスである。例えば、データストリーム又は信号シーケンスは、データ通信接続を介して、例えばインターネットを介して転送されるように、構成することができる。
【００５８】
更なる実施形態は、本明細書に記載された方法のうちの１つを実行するように構成又は適合された処理手段、例えばコンピュータ又はプログラム可能な論理デバイスを含む。
【００５９】
更なる実施形態は、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムがインストールされたコンピュータを含む。
【００６０】
いくつかの実施形態では、プログラム可能な論理デバイス（例えばフィールドプログラマブルゲートアレイ）を用いて、本明細書に記載された方法の機能のうちのいくつか又は全てを実行することができる。いくつかの実施形態では、フィールドプログラマブルゲートアレイは、本明細書に記載された方法のうちの１つを実行するためにマイクロプロセッサと連携することができる。概して、本方法は好ましくは任意のハードウェア装置によって実行される。
【００６１】
上述した実施形態は、単に本発明の原理を説明するものである。本明細書において記載される構成並びに詳細の変更及び変形は当業者には明らかであることが理解される。したがって、同封の特許請求の範囲の範囲によってのみ制限され、本明細書における実施形態の記述及び説明のために提示された特定の詳細によって制限されるものではないことが意図される。
【符号の説明】
【００６２】
１０ 反復コントローラ
１３ 入力インターフェース
１４ 出力インターフェース
１５ メモリ
２００ 通信システム
２０１、２０２、２０３、２０４ セル
２１０ 基地局
２１１ 移動端末
【技術分野】
【０００１】
本発明は無線通信に関し、特に、無線ネットワークにおける送信機／受信機ノードのためのリソース配分のタスクに関する。
【背景技術】
【０００２】
ネットワークのカバレッジエリア内のユーザの集合Ｋについて、伝送レートのベクトル
【数１】
によって表される効率的な比例公平レート割当てを見つける問題について述べる。
【数２】
【０００３】
ネットワーク内のユーザのためのレート割当てが図２に示されている。ユーザレートの相互依存性が、達成可能なレート領域Ｒによって表されている。これは凸集合となることが仮定される。レート領域Ｒは、物理層技法、例えばＭＩＭＯ伝送、及びチャネル実現によって構成される。この問題は双対分解によって解くことができることがよく知られている（非特許文献１）。双対問題は、図５に示すアルゴリズムによって説明されているように、主双対アルゴリズムによって解くことができる。
【０００４】
アルゴリズムのリアルタイムの実施を可能にするために、該アルゴリズムの収束速度及び複雑度が主な課題である。アルゴリズムの計算複雑度は、各反復において実行される重み付け合計レート最適化
【数３】
を解く複雑度に支配される。加えて、２つ以上の基地局を有するネットワークにおいてユーザが協調しているとき、各反復によって基地局間にシグナリングオーバーヘッドが生じる。重み付け合計レート最適化を解く複雑度は各反復について一定であるので、主な課題は、解、又は解の係数ε内で証明可能なレート構成を見つけるのに必要な反復数を低減することである。必要な反復数は、双対変数の更新方法に依拠し、双対係数の更新に最も頻繁に用いられる方法は以下である。
・劣勾配法。例えば、更新のための簡単な閉形式の式を有することに着目すると、最も一般的な更新規則である。
【数４】
しかしながら、劣勾配法の欠点は、特に高い確度が必要とされているときに収束が不良であることである。
・切断平面法。双対関数が凸型であり、したがって超平面によって下界を定めることができることに基づいて、切断平面法は構築される。解が見つかるまで、超平面を反復的に用いて、候補点から点の半空間を切り離す。
−楕円法（非特許文献２）は、候補点を含む楕円を用いる。楕円は２つの半楕円になるように反復的に切断され、一方が廃棄される。残りの半楕円を含む新たな楕円の中心が更新値として用いられる。新たな中心λｉ＋１は以下によって計算される。
【数５】
−Kellyの切断平面法（非特許文献３）は、双対関数を超平面によって近似し、線形近似を最小にするものを更新値として用いる。新たな双対変数は、以下の最適化問題の解である。
【数６】
【０００５】
線形近似に超平面を加える様々な変形形態が存在する。加えて、マルチカットと呼ばれる方法が検討される。マルチカット法では、各反復においてユーザあたり１つの超平面が加えられる。マルチカット法は収束速度を劇的に改善するが、双対更新のコストが各反復において大きく増大する。
・Aitkenの方法（非特許文献４）は、劣勾配法に加速モードを加え、結果として、より高速な収束がもたらされるが、アルゴリズムの安定性が問題となる。更新規則は１つの劣勾配ステップを計算し、それによって中間双対ベクトルを見つける。
【数７】
中間双対ベクトルを用いて、
【数８】
及び
【数９】
を計算し、更なる劣勾配ステップを求めることができる。
【数１０】
最後に、
【数１１】
及び
【数１２】
を用いて
【数１３】
を計算する。
【０００６】
双対更新に対し、より多くの計算複雑度が費やされると、収束速度を改善することができることを観測することができる。更新のための閉形式の式を有する方法もあれば、最適化問題を解くことを必要とする方法もある。複雑度及び収束速度は図８に要約されている。
【０００７】
理解されるように、最新技術の方法は、双対更新を計算するのに高い複雑度を有するか、又は収束不良を被るかのいずれかである。収束不良もまた、解く必要がある多数の重み付け合計レート問題に起因して計算的に複雑である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Mung Chiang、S.H. Low、 A.R. Calderbank、及び、J.C. Doyle、「Layering as optimization decomposition: A mathematical theory of network architectures」、Proceedings of the IEEE, 95(1):255-312, Jan. 2007
【非特許文献２】N. Z. Shor、「Convergence rate of the gradient descent method with dilatation of the space」、Cybernetics and Systems Analysis, 6(2):102-108, 1970
【非特許文献３】J.E. Jr. Kelley、「The Cutting-Plane method for solving convex programs」、Journal of the Society for Industrial and Applied Mathematics, 8(4):703-712, December 1960
【非特許文献４】J. Hodgskiss、A. Dekorsy、及び、J. Fliege、「Accelerating a dual algorithm for the simultaneous routing and power control problem」、Proc. IEEE 18thInternational Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC ´07, pages 1-5, 2007
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、通信システムにおいてノードにリソースを配分するための改善された概念を提供することである。
【００１０】
この目的は、請求項１に記載のリソースを配分する装置、請求項１４に記載のリソースを配分する方法、又は請求項１５に記載のコンピュータプログラムに従って達成される。
【課題を解決するための手段】
【００１１】
本発明は、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて反復リソース重みの更新ステップを実行するとき、反復プロセスのはるかに高速な収束速度が得られることの発見に基づく。好ましくは、全ての以前のリソース配分結果が、主双対アルゴリズムにおいて必要な更新された反復リソース重みを計算するために組み合わせられる。
【００１２】
特に、双対変数λｋの更新は、以前のリソース配分結果-の重み付け結合として実行され、ここで、以前の配分結果の各々は関連付けられた重み付け係数を有する。重み付け係数は、好ましくは、以前の反復結果を重み付けするための重みの合計が１に等しいという点で、更なる最適化問題の解となる。
【００１３】
好ましくは、反復ステップのリソース配分結果は、個々のリソースの重み付け合計の最適化に基づいて求められ、ここで反復リソース重みλは個々のリソースの重みであり、最適化は最適化目標及びリソース領域を用いて実行される。リソース領域は、通信システム又はノードの条件によって画定される。一実施の形態では、通信システム又はノードの条件は、ノードと受信機との間の伝送チャネル若しくはノードの内部特性、ノードの伝送電力制約、ノード間の相互干渉、物理層制約、又は伝送プロトコルを含む。好ましくは、ノードを通じて配分されるリソースは、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルである。
【００１４】
好ましくは、前記反復コントローラは、反復ステップにおいて、以前の反復ステップの前記リソース配分結果を該以前の反復ステップの結合重みと乗算したものの重み付け合計の最適化に基づいて新たな結合重みαを計算し、該新たな結合重みと、少なくとも１つの以前の反復ステップの結合重みとの結合が所定の制約値に等しいという条件下で、現在の反復ステップの前記リソース配分結果を前記新たな結合重みと乗算したものを計算するように構成される。
【００１５】
好ましくは、前記装置は、以前の反復ステップから現在の反復ステップまでに得られた前記リソース配分結果を格納し、以前の反復ステップから現在の反復ステップまでの前記重み付け結合の結合重みを格納するメモリを更に備える。
【００１６】
前記装置は、前記通信システム又は前記ノードの条件によって画定されるリソース領域に関する情報を受信する入力インターフェースと、前記反復コントローラによって実行される最終反復ステップの前記リソース配分結果を出力し該最終反復ステップの該リソース配分結果を用いて前記ノードが構成可能になるようにする出力インターフェースと、を更に備えることが好ましい。
【００１７】
好ましくは、前記ノードは移動端末であり、前記システムは基地局を含み、前記配分する装置は、最終反復ステップの前記リソース配分結果を前記基地局に提供するように構成される。
【００１８】
本発明の実施の形態は、マルチユーザシステムのための効率的な比例公平レート割当てを構成する。本発明は、好ましくはマルチユーザシステムのための効率的な比例公平レート割当てを計算するのに用いられる双対分解に基づくアルゴリズムのための新規の双対更新方法及び双対更新装置を提供する。新たな概念は、既存の方法と比較して優れた収束速度をもたらす。既存の方法と対照的に、本発明の実施の形態は、各反復において性能を厳密に改善する。本発明の概念は、軽微な追加コストを生じさせることによって、必要な反復数を劇的に低減し、したがって複雑度の全体的な低減を可能にする。
【発明の効果】
【００１９】
本発明は、無線通信の分野、送信技術の分野、協調マルチポイント（ＣｏＭＰ）送信の分野において、比例公平レート割当てが必要とされているときに有用である。
【００２０】
次に、本発明の好ましい実施形態を添付の図面に関して説明する。
【図面の簡単な説明】
【００２１】
【図１】通信システムにおいてノードにリソースを配分する方法のための装置を示す図である。
【図２】マルチユーザマルチセル／ＣｏＭＰ ＭＩＭＯシステムのための、ダウンリンク送信におけるユーザへのレート割当てを示す図である。
【図３】複数の反復にわたる、従来技術の方法と比較した本発明の性能を示す図である。
【図４ａ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｂ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｃ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｄ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｅ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｆ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｇ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｈ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図４ｉ】リソースを配分する好ましい反復アルゴリズムをグラフ表現で示す図である。
【図５】単純な主双対アルゴリズムを示す図である。
【図６】特定の更新規則を用いた本発明の主双対アルゴリズムを示す図である。
【図７】従来技術の方法に対する本発明の性能を示す図である。
【図８】本発明の概念と比較した従来技術の方法の様々な特性を要約した表である。
【発明を実施するための形態】
【００２２】
図２は、本発明を適用することができる問題を示している。問題のシナリオは、幾つかのセル２０１、２０２、２０３、２０４を含み、各セルは基地局２１０及びいくつかの移動端末２１１を含む。ここで、解くべき問題は、各移動端末２１１が、伝送レート、複数の周波数チャネル、複数の或るサイズのタイムスロット、周波数スロット、コードスロット、又は空間チャネル等の或る送信リソースを受けるべきであることである。特に、無線状況は、全ての移動端末２１１が或る意味互いに影響するようになっており、この互いに対する相互依存性は、通常達成可能なレート領域Ｒによって表される。達成可能なレート領域Ｒは、例えば凸集合であると仮定されるが、本発明では必ずしも必要とされない。レート領域Ｒは、物理層技法、例えばＭＩＭＯ送信、及びチャネル実現によって構成される。非特許文献１に示されているように、この問題は双対分解によって解くことができ、双対問題は、図５に示すような主双対アルゴリズムによって解かれる。特に、公平レート配分が必要とされ、これは、ゼロリソースを受け取るユーザが存在せず、全体としてリソースが最大にされることを確保すべきであることを意味する。言い換えれば、或るセル内のユーザ２１１が最大レートを受けるとき、これは、この強力な送信機の近傍の他の送信機が小さなレートしか有することができない可能性があることを意味するが、双方の送信機が非常に類似したレートを取得すれば、総全体レートがより高くなる可能性がある。しかしながら、これは最終的に異なる伝送チャネル、物理層等に依拠する。一方、ユーザのレートは、セルエッジのユーザに対しても高スループットを達成し、これによって全てのユーザに対し高いユーザ満足度を達成するには、比例公平配分されなくてはならない。通常、レート領域Ｒの明確な記述は利用可能でないため、図５に示すように、反復アルゴリズムが用いられる。このプロセスでは反復が実行され、該反復において、現在の双対変数（重み）に従って重み付け合計レートの解が計算され、解が最適でない限り双対変数が更新される。
【００２３】
従来技術の方法における双対変数更新の計算複雑度は過度に高く、多くの反復が必要とされ、高い総計算複雑度がもたらされることがわかっている。ここで、主な複雑度は重み付け合計レート問題を解くことにあり、セル間連携の場合、高いシグナリングオーバーヘッドが必要となる。
【００２４】
本発明によれば、双対変数の更新規則は、反復リソース重みλを更新するために、反復リソース重みλｉ＋１が、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて更新されるという点で強化されている。好ましくは、レート領域の近似が反復的に改善され、双対変数（ユーザ間のレート分布の重み）を更新するために用いられる。新たな更新規則は小さな計算複雑度を有し、高い収束速度をもたらす。したがって、新たな概念は低減された全体複雑度を有する。これは図８の最終行に要約されている。
【００２５】
図７及び図８のシミュレーションのために、六角形グリッド内に配置された１９個のサイト、サイトあたり３つのセクター、サイト間距離５００メートル、ラップアラウンド構成、３ＧＰＰ ＴＲ３６０．８１４に従ったチャネルモデル、都市型マクロセル、４×４ＭＩＭＯ構成、及び均一に分配されたセクターあたり平均５人のユーザでの、マルチセル／ＣｏＭＰシミュレーションセットアップが用いられる。
【００２６】
図１は、図２に示す通信システム２００においてノード２１１にリソースを配分する装置を示している。装置は、反復処理を実行する反復コントローラ１０を備え、該反復コントローラは、１１及び１２で示すように構成される。参照符号１１は反復コントローラの構成を指し、該構成において、反復コントローラは、反復リソース重みλを用いて反復ステップのリソース配分結果ｒ＊を得るように構成されている。参照符号１２は、反復コントローラが、現在の反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合を用いて、反復リソース重みλを更新して、更なる反復ステップの更新された反復リソース重みλｉ＋１を得るように更に構成されていることを示す。また、装置は、例えば、物理層技法、例えばＭＩＭＯ伝送、及びチャネル実現によって構成することができる達成可能なレート領域に関する情報を受信する入力インターフェース１３を備える。また、装置は、反復プロセスの終了後、すなわち終了判断基準が満たされたとき、最終配分結果を提供する出力インターフェース１４を備える。
【００２７】
最終配分結果は、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルを含むことができる。例えば、或るビットレートに或る最小ビット誤り率が必要とされるとき、伝送電力は或る値に設定されなくてはならない。一方、伝送電力が同じままであるとき、例えば、より高いか又はより低い信号点配置図を有する様々な緩和方法（moderation method）によって制御することができる、より高いか又はより低い最小信号対雑音比を割り当てて、レート割当ても実行することができる。したがって、リソース配分は、送信機内で、或る伝送電力設定及び／又はマッピング規則（信号点配置図）の或る選択において、或る量の転送誤り訂正コーディングにおいて現れ、すなわち、より高い冗長性は、より低い伝送レートを意味するが、高められた信号対雑音比を意味する。或る利用可能な再送信規則等のより複雑な課題をレート割当てに含めることができる。
【００２８】
このため、最終的な配分結果は出力インターフェースを介して送信ネットワーク内の個々の送信機に通信されるか、又はまず図２の基地局２１０に送信され、次に、基地局からこの基地局に関連する送信機２１１に送信される。
【００２９】
双対変数の更新のために、以下が提案される。
【数１４】
ここで、α＊は以下の最適化問題の解である。
【数１５】
【００３０】
問題は、単純な制約集合にわたって２回微分可能な凹関数を最大化することであって、このために非常に高速で効率的なアルゴリズムが存在する。新たな更新メカニズムを有する主双対アルゴリズムが図６に要約されている。ここで、いくつかのステップが省かれていることに気付くことができる。
【００３１】
新規の双対更新方法の主な寄与は、
・優れた収束速度、
・各反復の効用の改善が保証され、ステップサイズ制御が必要とされないこと、
・複雑度の全体的な低減、
である。
【００３２】
実施形態は、複数ユーザを有する通信システムにおいて或る効用関数を最大化することを目的とし、レート領域の区分線形近似を仮定した効用最大化問題の解を含み、結果のユーザレートの要素単位の反転を更に含むアルゴリズムにおいて双対変数を更新する概念を含むことが好ましい。
【００３３】
好ましくは、本発明は、レート領域の区分線形近似の品質を改善する双対変動更新規則の反復的な実行を含む。効用関数は、比例公平レート配分に従って実行されることが好ましい。また、本発明は、基地局が連携し、基地局及び移動ノードが複数のアンテナを有する通信システムに適用されることが好ましい。
【００３４】
マルチユーザシステムのための効率的な比例公平レート割当てを見つけることは、効用最大化問題によって計算される。
【数１６】
【００３５】
この問題は双対分解によって解かれ、ここで双対関数ｄ（λ）は以下である。
【数１７】
【００３６】
Ｕｐは自身の最大値を達成する凸最適化問題であるので、双対問題は同じ最適値
【数１８】
を有する。双対問題ＵＤは、
【数１９】
であり、
【数２０】
に等しい。これは、閉じた凸集合は、閉じた半空間の交差として特徴付けることができるためである。通常、Ｒを完全に記述するのに必要な半空間の数は無限であり、これによってＵＤを直接解くことができない。したがって、アルゴリズム１を採用することができ、各反復において、代替問題を定式化することができる。
【数２１】
この代替問題は、各反復において解かれる重み付け合計レート最適化問題
【数２２】
から得られる有限の点集合
【数２３】
を用いて機能する。明らかに、ＡＰの最適値は問題ＵＤの最適値の下限であり、自由度がより低い。以下で、双対変数の更新値としてＡＰを最適化したものを反復的に用いることによって、最終的にε最適解である
【数２４】
又は
【数２５】
となるまで界が狭まることが数学的に証明されている。
【００３７】
近似問題に対する解決策
このセクションでは、凸最適化問題である
【数２６】
の解を計算する方法を検討する。ラグランジュ関数は以下の通りである。
【数２７】
【００３８】
定理１：所与の双対変数αのラグランジュ関数の最小値である双対関数θ（α）が以下によって与えられる
【数２８】
【００３９】
説明：ｚは制約されていないので、ｚを任意に小さくすることができ、したがって
【数２９】
でない限りθ（α）＝−∞である。この場合、
【数３０】
であり、
【数３１】
から、
【数３２】
となる。
【００４０】
これを式（１）に代入すると、
【数３３】
の場合に以下となることを結論付けることができる。
【数３４】
【００４１】
定理１から、双対問題ＡＤ（ｉ）、すなわち
【数３５】
は以下の問題に等しいことを結論付けることができる。
【数３６】
【００４２】
この問題は、比例公平性効用を最大にするレート点ｃ１，．．．，ｃｉの凸結合を見つけることを意味する。ＡＤ（ｉ）の解ａ＊を式（２）に代入することによって、提案された更新規則がもたらされる。最終的に、アルゴリズムによって、効用が解に収束するまで、各反復において効用が厳密に改善されることを証明することが可能である。
【００４３】
シミュレーション結果
図３は、１つのチャネル実現のための複数の反復にわたる効用を示している。ここで、収束性能を検証することができる。Aitkenのプロセスは、安定性を確保するための慎重なステップサイズ制御を必要とし、これは本発明者らの実験において達成することができなかった。提案された方法によって、最良の収束速度が提供されることを理解することができる。切断平面法は、更新値を計算するのに比較可能な複雑度を有するが、本方法による目覚しい利得を見て取ることができる。マルチカット方法は良好な性能をもたらすが、本発明の一実施形態による方法よりも高い複雑度を有する。
【００４４】
アルゴリズムは、部分的再利用方式を用いた、より大規模なネットワークにおいても研究されている。反復数が過度に高い（１，０００〜１，０００，０００）ので、劣勾配アルゴリズム、楕円アルゴリズム、及び切断平面アルゴリズムはこのシナリオには適用可能でない。図７は、本方法がマルチカット法をはるかに凌ぐ一方で、より低い複雑度を有することを示している。マルチカット法のｉ番目の反復において解かれなくてはならない線形問題の制約数は（Ｋ＋１）ｉ個の制約を有し、これは最後の反復では７０００個を超える。一方、新規の手法は、単純な制約を有する凸問題において、ｉ番目の反復においてｉ個の変数を有する。数ステップのうちに最適条件に近い（９０％〜９５％）構成に到達することができ、これによって新規の方法が実際の実施に対して現実的となることに注目されたい。
【００４５】
続いて、図６に示すアルゴリズムを、図４ａ〜図４ｉを参照して詳細に論じる。図４ａ〜図４ｉを検討するとき、完全な一貫性を有するために、図ａ〜図ｉにおいてパラメータｃがパラメータｒに置き換えられることに留意されたい。しかしながら、ｃ及びｒはともに同じもの、すなわちリソース配分結果を意味する。特に、ｒｍ又はｃｍは、検討中のユーザグループの特定のユーザｍのリソース配分結果を示している。このため、ｒｍ又はｃｍは、ユーザｍの伝送レート、ユーザｍの周波数チャネル、ユーザｍのタイムスロット、ユーザｍのコードスロット、又はユーザｍの空間チャネルとすることができる。加えて、各ユーザリソース配分結果ｒｍが関連付けられたλｍを有するように、反復リソース重みλが各ユーザに関連付けられる。また、一方、ｍ＊は、反復ステップのリソース配分結果と少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合において用いられる或るユーザｍの重み付け係数である。
【００４６】
図４ａは、Ｒの境界上の点を見つけるのに用いることができる重み付け合計レート最大化（ＷＳＲＭａｘ）を示している。ここで、Ｒは、全ての物理パラメータ及び伝送チャネル等の表現である、いわゆる達成可能なレート領域Ｒである。λをｒと乗算した積が、レートが許容レート領域内にあることを条件として最大化されることになる。図４において見て取ることができるように、直線４０が存在し、ここで、特定の直線４１は、或る点においてレート領域に接し、反復リソース重みλによって規定されたベクトルは線４１に直交する。図４ｂは、図６と比較してわずかに異なる表現で反復アルゴリズムを示している。特に、更新ステップ２が示され、該ステップは、λを引数とした重み付け合計レート最大化の後に実行される。特に、図４ｂはレート領域の反復的探査を示しており、反復当たりのコストが、最適化問題、ＷＳＲＭａｘ、及びλを更新するときに全ての送信機間で必要とされるシグナリングによって与えられる。主な目標は、反復数を劇的に低減することである。
【００４７】
図４ｃは、レート領域の別の反復的探査を示しており、ここで、異なる線４２は図４ａに対し異なる勾配を有し、線４３はリソース配分結果ｒにおいてレート領域境界に接し、ここでもλは線４３に直交している。
【００４８】
図４ｄは、重み付け合計レート最適化を用いた最初の反復ステップを示している。ここで、レート領域が再び示され、関連付けられた更新重みλ１を有する第１の反復結果がｒ１において見つかる。次に、図４ｅに示すように、レート領域の内部近似が実行される。更新ステップが図４ｅに示されている。次に、図４ｆにおいて、反復２が実行されるが、今度は図４ｅにおいて計算された異なるλを用いて実行され、これは、線５０がレート領域Ｒに接する点が求められることを意味し、この点はｒ２に対応する。次に、図４ｇに示すように、レート領域の内部近似が再び実行され、反復２において、ｒ２が、２つの以前の反復ステップにおいて求められたｒ１及びｒ２の重み付け結合として計算され、次にこのｒ２を用いて、λ更新値が、反復ステップのリソース配分結果と、少なくとも１つの以前の反復ステップのリソース配分結果との重み付け結合に基づくように新たなλ３を最終的に計算する。
【００４９】
次に、図４ｈに示すように、反復３によって結果としてｒ３がもたらされる。言い換えると、図４ｇにおいてλ３が計算され、図４ｈにおいて、λ３によって求められた勾配を有する直線がレート領域に接する点が求められる。このため、第３の反復の結果はｒ３となる。図４ｉに示すように、これより改善された結果を得ることができないので、ここで反復が終了する。
【００５０】
装置との関係でいくつかの態様が説明されたが、これらの態様は対応する方法の記述も表し、ここでブロック又はデバイスは方法ステップ又は方法ステップの特徴に対応することが明らかである。それに類似して、方法ステップに関連して説明された態様も、対応する装置の対応するブロック又はアイテム又は特徴の記述を表す。
【００５１】
或る特定の実施態様要件に依拠して、本発明の実施形態はハードウェア又はソフトウェアにおいて実施することができる。実施態様は、電子的に読取り可能な制御信号が格納されたデジタルストレージ媒体若しくは非一時的ストレージ媒体、例えばフロッピー（登録商標）ディスク、ＤＶＤ、ＣＤ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、又はフラッシュメモリを用いて実行することができ、それらは、それぞれの方法が実行されるようにプログラム可能なコンピュータシステムと連携する（又は連携可能である）。
【００５２】
本発明によるいくつかの実施形態は、本明細書に記載される方法のうちの１つが実行されるようにプログラム可能なコンピュータシステムと連携することができる電子的に読取り可能な制御信号を有する非一時的データ担体を含む。
【００５３】
概して、本発明の実施形態は、プログラムコードを有するコンピュータプログラム製品として実装することができる。該プログラムコードは、コンピュータプログラム製品がコンピュータ上で実行されると、方法のうちの１つを実行するように動作可能である。プログラムコードは、例えば機械可読担体上に格納することができる。
【００５４】
他の実施形態は、機械可読担体上に格納された、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを含む。
【００５５】
したがって、換言すれば、本発明の方法の一実施形態は、コンピュータプログラムがコンピュータ上で実行されるときに本明細書に記載された方法のうちの１つを実行するプログラムコードを有するコンピュータプログラムである。
【００５６】
したがって、本発明の方法の更なる実施形態は、データ担体（又はデジタルストレージ媒体若しくはコンピュータ可読媒体）であって、該データ担体上に記録された、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを含む、データ担体である。
【００５７】
したがって、本発明の方法のまた更なる実施形態は、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムを表すデータストリーム又は信号シーケンスである。例えば、データストリーム又は信号シーケンスは、データ通信接続を介して、例えばインターネットを介して転送されるように、構成することができる。
【００５８】
更なる実施形態は、本明細書に記載された方法のうちの１つを実行するように構成又は適合された処理手段、例えばコンピュータ又はプログラム可能な論理デバイスを含む。
【００５９】
更なる実施形態は、本明細書に記載された方法のうちの１つを実行するコンピュータプログラムがインストールされたコンピュータを含む。
【００６０】
いくつかの実施形態では、プログラム可能な論理デバイス（例えばフィールドプログラマブルゲートアレイ）を用いて、本明細書に記載された方法の機能のうちのいくつか又は全てを実行することができる。いくつかの実施形態では、フィールドプログラマブルゲートアレイは、本明細書に記載された方法のうちの１つを実行するためにマイクロプロセッサと連携することができる。概して、本方法は好ましくは任意のハードウェア装置によって実行される。
【００６１】
上述した実施形態は、単に本発明の原理を説明するものである。本明細書において記載される構成並びに詳細の変更及び変形は当業者には明らかであることが理解される。したがって、同封の特許請求の範囲の範囲によってのみ制限され、本明細書における実施形態の記述及び説明のために提示された特定の詳細によって制限されるものではないことが意図される。
【符号の説明】
【００６２】
１０ 反復コントローラ
１３ 入力インターフェース
１４ 出力インターフェース
１５ メモリ
２００ 通信システム
２０１、２０２、２０３、２０４ セル
２１０ 基地局
２１１ 移動端末
【特許請求の範囲】
【請求項１】
通信システムにおいてノードにリソースを配分する装置であって、
反復処理を実行する反復コントローラ（１０）であって、前記反復コントローラが、
反復リソース重み（λ）を用いて（１１）反復ステップのリソース配分結果（ｒ＊）を得、かつ
前記反復ステップの前記リソース配分結果と、少なくとも１つの以前の反復ステップの前記リソース配分結果との重み付け結合を用いて、前記反復リソース重み（λ）を更新して、更なる反復ステップの更新された反復リソース重み（λｉ＋１）を得る、
ように構成された、反復コントローラを備える、装置。
【請求項２】
前記反復コントローラ（１０）は、前記個々のリソースの前記重み付け合計の最適化に基づいて、前記反復ステップの前記リソース配分結果（ｒ＊）を求めるように構成され、ここで、前記反復リソース重み（λ）は前記個々のリソースの重みであり、前記最適化は、最適化目標、及び前記通信システム又は前記ノードの条件によって画定されたリソース領域を用いて実行される、請求項１に記載の装置。
【請求項３】
前記通信システム又は前記ノードの前記条件は、ノードと受信機との間の伝送チャネルと、前記ノードの内部特性、又は前記ノードの伝送電力制約、又は前記ノード間の相互干渉、又は物理層制約、又は伝送プロトコルとを含む、請求項２に記載の装置。
【請求項４】
前記リソースは、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルである、請求項１〜３のいずれか１項に記載の装置。
【請求項５】
前記反復コントローラ（１０）は、反復ステップにおいて、以前の反復ステップの前記リソース配分結果を該以前の反復ステップの結合重みと乗算したものの重み付け合計の最適化に基づいて新たな結合重み（α）を計算し、該新たな結合重みと、少なくとも１つの以前の反復ステップの結合重みとの結合が所定の制約値に等しいという条件下で、現在の反復ステップの前記リソース配分結果を前記新たな結合重みと乗算したものを計算するように構成される、請求項１〜４のいずれか１項に記載の装置。
【請求項６】
以前の反復ステップから現在の反復ステップまでに得られた前記リソース配分結果を格納し、以前の反復ステップから前記現在の反復ステップまでの前記重み付け結合の結合重みを格納するメモリ（１５）を更に備える、請求項１〜５のいずれか１項に記載の装置。
【請求項７】
前記通信システム又は前記ノードの条件によって画定されるリソース領域に関する情報を受信する入力インターフェース（１３）と、
前記反復コントローラによって実行される最終反復ステップの前記リソース配分結果を出力し、該最終反復ステップの該リソース配分結果を用いて前記ノードが構成可能になるようにする、出力インターフェース（１４）と、
を更に備える、請求項１〜６のいずれか１項に記載の装置。
【請求項８】
前記反復コントローラ（１０）は、各反復ステップにおいてリソース領域の新たな線形化を実行し、前記リソース配分結果を得るように構成される、請求項１〜７のいずれか１項に記載の装置。
【請求項９】
前記反復コントローラ（１０）は、ｒが前記リソース領域内にあるという制約下で、関数（λＴｒ）を最大化し、前記リソース配分結果を得るように構成され、λは前記ノードの前記反復リソース重みからなるベクトルであり、ｒは前記ノードの前記リソース配分結果を含むベクトルである、請求項１〜８のいずれか１項に記載の装置。
【請求項１０】
前記反復コントローラ（１０）は、以下の制約
【数１】
の下で、関数
【数２】
を最大化することによって、前記重み付け結合の新たな結合重みαを計算するように構成され、ここで、αｉは反復ステップｉにおけるノードｍの前記重み付け結合の重みであり、ｒｉは反復ステップｉにおける前記リソース配分結果であり、ｅはユーザの集合Ｋ内のユーザｋのリソース配分結果の成分を選択する単位ベクトルであり、ｍは総和パラメータである、請求項１〜９のいずれか１項に記載の装置。
【請求項１１】
前記反復コントローラ（１０）は、以下の式
【数３】
に基づいて前記反復リソース重みを更新するように構成され、ここで、αｉは反復ステップｉにおけるノードｍの前記重み付け結合の重みであり、ｒｉは反復ステップｉにおける前記リソース配分結果であり、ｅはユーザの集合Ｋ内のユーザｋのリソース配分結果の成分を選択する単位ベクトルであり、ｍは総和パラメータである、請求項１〜１０のいずれか１項に記載の装置。
【請求項１２】
前記ノードは移動端末（２１１）であり、前記システムは基地局（２１０）を含み、前記配分する装置は、最終反復ステップの前記リソース配分結果を前記基地局（２１０）に提供するように構成される、請求項１〜１１のいずれか１項に記載の装置。
【請求項１３】
通信システム（２００）であって、
請求項１〜１２のいずれか１項に記載のリソースを配分する装置（１０）と、
移動端末（２１１）であるノードと、
基地局（２１０）と、
を備え、
前記移動端末（２１１）又は前記基地局（２１０）は空間チャネルを実装する複数のアンテナを有する、通信システム。
【請求項１４】
通信システムにおいてノードにリソースを配分する方法であって、
複数の連続した反復ステップを用いて反復処理を実行するステップと、
反復ステップ内で、反復リソース重み（λ）を用いること（１１）であって、該反復ステップのリソース配分結果（ｒ＊）を得る、用いるステップと、
前記反復ステップ内で、前記反復リソース重み（λ）を更新するステップ（１２）であって、該反復ステップの前記リソース配分結果と、少なくとも１つの以前の反復ステップの前記リソース配分結果との重み付け結合を用いて、前記複数の連続した反復ステップにおける更なる反復ステップの更新された反復リソース重み（λｉ＋１）を得る、更新するステップと
を含む、方法。
【請求項１５】
コンピュータ又はプロセッサ上で実行されたときに、請求項１４に記載のリソースを配分する方法を実行するためのコンピュータプログラム。
【請求項１】
通信システムにおいてノードにリソースを配分する装置であって、
反復処理を実行する反復コントローラ（１０）であって、前記反復コントローラが、
反復リソース重み（λ）を用いて（１１）反復ステップのリソース配分結果（ｒ＊）を得、かつ
前記反復ステップの前記リソース配分結果と、少なくとも１つの以前の反復ステップの前記リソース配分結果との重み付け結合を用いて、前記反復リソース重み（λ）を更新して、更なる反復ステップの更新された反復リソース重み（λｉ＋１）を得る、
ように構成された、反復コントローラを備える、装置。
【請求項２】
前記反復コントローラ（１０）は、前記個々のリソースの前記重み付け合計の最適化に基づいて、前記反復ステップの前記リソース配分結果（ｒ＊）を求めるように構成され、ここで、前記反復リソース重み（λ）は前記個々のリソースの重みであり、前記最適化は、最適化目標、及び前記通信システム又は前記ノードの条件によって画定されたリソース領域を用いて実行される、請求項１に記載の装置。
【請求項３】
前記通信システム又は前記ノードの前記条件は、ノードと受信機との間の伝送チャネルと、前記ノードの内部特性、又は前記ノードの伝送電力制約、又は前記ノード間の相互干渉、又は物理層制約、又は伝送プロトコルとを含む、請求項２に記載の装置。
【請求項４】
前記リソースは、伝送レート、周波数チャネル、タイムスロット、コードスロット、又は空間チャネルである、請求項１〜３のいずれか１項に記載の装置。
【請求項５】
前記反復コントローラ（１０）は、反復ステップにおいて、以前の反復ステップの前記リソース配分結果を該以前の反復ステップの結合重みと乗算したものの重み付け合計の最適化に基づいて新たな結合重み（α）を計算し、該新たな結合重みと、少なくとも１つの以前の反復ステップの結合重みとの結合が所定の制約値に等しいという条件下で、現在の反復ステップの前記リソース配分結果を前記新たな結合重みと乗算したものを計算するように構成される、請求項１〜４のいずれか１項に記載の装置。
【請求項６】
以前の反復ステップから現在の反復ステップまでに得られた前記リソース配分結果を格納し、以前の反復ステップから前記現在の反復ステップまでの前記重み付け結合の結合重みを格納するメモリ（１５）を更に備える、請求項１〜５のいずれか１項に記載の装置。
【請求項７】
前記通信システム又は前記ノードの条件によって画定されるリソース領域に関する情報を受信する入力インターフェース（１３）と、
前記反復コントローラによって実行される最終反復ステップの前記リソース配分結果を出力し、該最終反復ステップの該リソース配分結果を用いて前記ノードが構成可能になるようにする、出力インターフェース（１４）と、
を更に備える、請求項１〜６のいずれか１項に記載の装置。
【請求項８】
前記反復コントローラ（１０）は、各反復ステップにおいてリソース領域の新たな線形化を実行し、前記リソース配分結果を得るように構成される、請求項１〜７のいずれか１項に記載の装置。
【請求項９】
前記反復コントローラ（１０）は、ｒが前記リソース領域内にあるという制約下で、関数（λＴｒ）を最大化し、前記リソース配分結果を得るように構成され、λは前記ノードの前記反復リソース重みからなるベクトルであり、ｒは前記ノードの前記リソース配分結果を含むベクトルである、請求項１〜８のいずれか１項に記載の装置。
【請求項１０】
前記反復コントローラ（１０）は、以下の制約
【数１】
の下で、関数
【数２】
を最大化することによって、前記重み付け結合の新たな結合重みαを計算するように構成され、ここで、αｉは反復ステップｉにおけるノードｍの前記重み付け結合の重みであり、ｒｉは反復ステップｉにおける前記リソース配分結果であり、ｅはユーザの集合Ｋ内のユーザｋのリソース配分結果の成分を選択する単位ベクトルであり、ｍは総和パラメータである、請求項１〜９のいずれか１項に記載の装置。
【請求項１１】
前記反復コントローラ（１０）は、以下の式
【数３】
に基づいて前記反復リソース重みを更新するように構成され、ここで、αｉは反復ステップｉにおけるノードｍの前記重み付け結合の重みであり、ｒｉは反復ステップｉにおける前記リソース配分結果であり、ｅはユーザの集合Ｋ内のユーザｋのリソース配分結果の成分を選択する単位ベクトルであり、ｍは総和パラメータである、請求項１〜１０のいずれか１項に記載の装置。
【請求項１２】
前記ノードは移動端末（２１１）であり、前記システムは基地局（２１０）を含み、前記配分する装置は、最終反復ステップの前記リソース配分結果を前記基地局（２１０）に提供するように構成される、請求項１〜１１のいずれか１項に記載の装置。
【請求項１３】
通信システム（２００）であって、
請求項１〜１２のいずれか１項に記載のリソースを配分する装置（１０）と、
移動端末（２１１）であるノードと、
基地局（２１０）と、
を備え、
前記移動端末（２１１）又は前記基地局（２１０）は空間チャネルを実装する複数のアンテナを有する、通信システム。
【請求項１４】
通信システムにおいてノードにリソースを配分する方法であって、
複数の連続した反復ステップを用いて反復処理を実行するステップと、
反復ステップ内で、反復リソース重み（λ）を用いること（１１）であって、該反復ステップのリソース配分結果（ｒ＊）を得る、用いるステップと、
前記反復ステップ内で、前記反復リソース重み（λ）を更新するステップ（１２）であって、該反復ステップの前記リソース配分結果と、少なくとも１つの以前の反復ステップの前記リソース配分結果との重み付け結合を用いて、前記複数の連続した反復ステップにおける更なる反復ステップの更新された反復リソース重み（λｉ＋１）を得る、更新するステップと
を含む、方法。
【請求項１５】
コンピュータ又はプロセッサ上で実行されたときに、請求項１４に記載のリソースを配分する方法を実行するためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図４ｅ】
【図４ｆ】
【図４ｇ】
【図４ｈ】
【図４ｉ】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図４ｅ】
【図４ｆ】
【図４ｇ】
【図４ｈ】
【図４ｉ】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１３４９５２（Ｐ２０１２−１３４９５２Ａ）
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２５０７２３（Ｐ２０１１−２５０７２３）
【出願日】平成２３年１１月１６日（２０１１．１１．１６）
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願番号】特願２０１１−２５０７２３（Ｐ２０１１−２５０７２３）
【出願日】平成２３年１１月１６日（２０１１．１１．１６）
【出願人】（３９２０２６６９３）株式会社エヌ・ティ・ティ・ドコモ (5,876)
【Ｆターム（参考）】
[ Back to top ]