(57)【要約】      （修正有）【課題】無線通信システム内でのリソース配分及びスケジューリングのための方法及び装置の提供。【解決手段】リソース配分の間に、システム全体の伝送電力の最大値（Ｐ）と、利用可能な符号数の最大値（Ｎ）と、システムの各ユーザに対する符号数の最大値（Ｎ※＝（Ｎ1，．．．，Ｎd））と、システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※＝（Ｓ1，．．．，Ｓd））と、システムの各ユーザに対する伝送電力の単位ワットあたりのＳＩＮＲ（ｅ※＝（ｅ1，．．．，ｅd））とがスケジューラによって受信される（２０１）。次いで、スケジューラは、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を出力する（２１５）。【選択図】図２
2005176344.tif 000002
【特許請求の範囲】
【請求項１】
リソース配分のための方法において、その方法は、
システム全体の伝送電力（Ｐ）の最大値を受信するステップと、
利用可能なシステムの符号数の最大値（Ｎ）を受信するステップと、
システムの各ユーザに対する符号数の最大値（Ｎ※）を受信するステップと、
システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※）を受信するステップと、
システムの各ユーザに対する伝送電力値の単位ワットあたりのＳＩＮＲ（ｅ※）を受信するステップと、
Ｐ、Ｎ、Ｎ※、Ｓ※及びｅ※に基づき、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を決定するステップと、
ｎ※及びｐ※に基づいた動作パラメータにより、ユーザのスケジュールを組むステップとからなるリソース配分のための方法。
【請求項２】
ｎ※及びｐ※に基づいて、各ユーザに対する最適なレート（ｒ※）を決定するステップをさらに含む請求項１に記載の方法。
【請求項３】
前記ｎ※及びｐ※を決定するステップは、
スループット／キュー長の関数としての重みベクトルｗ※t＝（ｗ1（Ｗ※1,t，Ｑ※1,t），．．．，ｗd（Ｗ※d,t，Ｑ※d,t））とスケジューリング時刻ｔにおいて選択されるレートベクトルｒ※tとの内積を最大化するステップを含み、ここで、
ｗ※t＝（ｗ1,t，．．．，ｗd,t）は重みベクトルであり、
Ｗ※t＝（Ｗ1,t，．．．，Ｗd,t）はユーザのスループットの推定値のベクトルであり、
Ｑ※t＝（Ｑ1,t，．．．，Ｑd,t）はユーザのキュー長又は遅延時間のベクトルであり、
ｒ※t＝（ｒ1,t，．．．，ｒd,t）は選択されたレートベクトルであり、かつ
ｄはユーザの数である請求項１に記載の方法。
【請求項４】
前記ｎ※及びｐ※を決定するステップは、
【数１】
2005176344.tif 000084
を、条件
【数２】
2005176344.tif 000085
の下、決定するステップを含み、ここで、
【数３】
2005176344.tif 000086
であり、
ｗ※は重みｗiのベクトルであり、
ｅ※は伝送電力の単位ワットあたりのＳＩＮＲｅiのベクトルであり、
Ｓ※はＳＩＮＲの最大値Ｓiのベクトルであり、
ｗi＝ｆi（Ｗ※i，Ｑ※i）であり、ここで、
Ｗ※＝（Ｗ1，．．．，Ｗd）は全てのユーザに対する推定スループットのベクトルであり、
Ｑ※＝（Ｑ1，．．．，Ｑd）は全てのユーザに対するキュー長又は遅延時間のベクトルであり、ｆiはユーザｉに対するスループット及び／又はキュー長の特定の関数であり、かつユーザｉに対するＱｏＳクラス及びパラメータにも依存し得る請求項１に記載の方法。
【請求項５】
リソース配分のための方法において、その方法は、
通信システム内のユーザ一人あたりの最適符号数（ｎ※）の値を決定するステップと、
ｎ※に基づいて、ユーザ一人あたりの最適レート（ｒ※）及びユーザ一人あたりの最適電力（ｐ※）を決定するステップとを含むリソース配分のための方法。
【請求項６】
前記ユーザ一人あたりの符号数（ｎ※）を決定するステップは、
ｎ※＝ｎ※*（λ*，μ*（λ*））を計算するステップを含み、ここで、
λ*は、電力制約に対するラグランジジュの未定乗数の最適値であり、
μ*（λ）は、（電力制約に対するラグランジュの未定乗数λの関数としての）符号制約に対するラグランジュの未定乗数μの最適値であり、
ｎ※*（λ，μ）は、λ及びμの関数としての符号配分の最適値である請求項５に記載の方法。
【請求項７】
前記ｎ※に基づいて、ユーザ一人あたりの最適レート（ｒ※）及びユーザ一人あたりの最適電力（ｐ※）を決定するステップは、
ｎ※＝ｐ※*（ｎ※）＝ｐ※*（ｎ※，λ*（ｎ※））を計算するステップを含み、ここで、
λ*（ｎ※）は、電力制約に対するラグランジジュの未定乗数の最適値であり、
ｐ※*（ｎ※，λ）は、ｎ※及びλの関数としての電力配分の最適値である請求項５に記載の方法。
【請求項８】
前記ｎ※の値を決定するステップは、
ｗi及びｅiの関数である尺度（ｍｅｔｒｉｃ）に基づき降順にユーザをソートするステップであって、ｅiは伝送電力値の単位ワットあたりのＳＩＮＲであり、ｗiはシステムにおける各ユーザｉに対する勾配／重みであるステップと、
【数４】
2005176344.tif 000087
を満たす最小のｊ*を決定するステップと、
【数５】
2005176344.tif 000088
を満たすｎ※を決定するステップとを含む請求項５に記載の方法。
【請求項９】
システム全体の伝送電力の最大値（Ｐ）と、利用可能なシステムの符号数の最大値（Ｎ）と、システムの各ユーザに対する符号数の最大値（Ｎ※）と、システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※）と、システムの各ユーザに対する伝送電力値の単位ワットあたりのＳＩＮＲ（ｅ※）とを受信するスケジューラであって、そのスケジューラはＰ、Ｎ、Ｎ※、Ｓ※及びｅ※に基づき、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を出力するスケジューラを備える装置。
【請求項１０】
ｎ※及びｐ※に基づく物理層動作点により、ユーザへの伝送のスケジュールを組むコントローラをさらに備える請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の参照）
本願は、２００３年１１月２１日に出願された出願番号６０／５２３９７１号、タイトル“リソース配分及びスケジューリングのための方法及び装置”の仮出願の優先権を主張するものであり、その出願の内容は全て、本明細書に参照として共有かつ組み入れられる。
【０００２】
本発明は、一般にはリソース配分及びスケジューリングに関するものであり、詳細には無線通信システムにおけるリソース配分及びスケジューリングに関するものである。
【背景技術】
【０００３】
通信システム内でのリソース配分及びスケジューリングは、当該技術分野において一般的に周知である。リソース配分及びスケジューリングの間、システムコントローラは、データ伝送のスケジュールと共に、各ユーザに対するチャンネルパラメータを決定する。例えば、通信システム内の各ユーザには、符号化方式、電力、使用される符号数及びデータレートが割り当てられよう。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
周知なように、通信システムには、一般的に、それぞれに固有の伝送パラメータを有する複数のユーザが含まれている。課題は、各ユーザのスケジュールを適切に組み、かつ各ユーザに対して適切なシステムパラメータを選択することにより、その通信システムを最適化することにある。それゆえ、一般にシステム性能を最適化するような通信システム内のスケジューリング及びリソース配分のための方法及び装置についての必要性は存在する。
【課題を解決するための手段】
【０００５】
リソース配分及びスケジューリングについての必要性に対処するため、本明細書において、無線通信システム内でのリソース配分及びスケジューリングのための方法及び装置が提供される。リソース配分の間に、システム全体の伝送電力の最大値（Ｐ）と、利用可能な符号数の最大値（Ｎ）と、システムの各ユーザに対する符号数の最大値（Ｎ※＝（Ｎ1，．．．，Ｎd））と、システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※＝（Ｓ1，．．．，Ｓd））と、システムの各ユーザに対する伝送電力の単位ワットあたりのＳＩＮＲ（ｅ※＝（ｅ1，．．．，ｅd））とがスケジューラによって受信される。次いで、スケジューラは、Ｐ、Ｎ、Ｎ※及びＳ※に基づき、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を出力する。
【０００６】
本発明は、リソース配分のための方法を含んでいる。本方法は、システム全体の伝送電力の最大値（Ｐ）を受信するステップと、利用可能なシステムの符号数の最大値（Ｎ）を受信するステップと、システムの各ユーザに対する符号数の最大値（Ｎ※）を受信するステップと、システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※）を受信するステップと、システムの各ユーザに対する伝送電力値の単位ワットあたりのＳＩＮＲ（ｅ※）を受信するステップと、Ｐ、Ｎ、Ｎ※、Ｓ※及びｅ※に基づき、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を決定するステップと、ｎ※及びｐ※に基づいた動作パラメータにより、ユーザのスケジュールを組むステップとからなる。
【０００７】
本発明はさらに、リソース配分のための方法を含んでいる。本方法は、通信システム内でユーザ一人あたりの最適符号数（ｎ※）の値を決定するステップと、ｎ※に基づき、ユーザ一人あたりの最適レート（ｒ※）及びユーザ一人あたりの最適電力（ｐ※）を決定するステップとからなる。
【０００８】
本発明はさらに、システム全体の伝送電力の最大値（Ｐ）と、利用可能なシステムの符号数の最大値（Ｎ）と、システムの各ユーザに対する符号数の最大値（Ｎ※）と、システムの各ユーザに対するＳＩＮＲ値の最大値（Ｓ※）と、システムの各ユーザに対する伝送電力値の単位ワットあたりのＳＩＮＲ（ｅ※）とを受信するスケジューラであって、そのスケジューラはＰ、Ｎ、Ｎ※、Ｓ※及びｅ※に基づき、ユーザ一人あたりの最適符号数（ｎ※）及びユーザ一人あたりの最適電力レベル（ｐ※）を出力するスケジューラを備える装置を含んでいる。
【発明を実施するための最良の形態】
【０００９】
以下に、図面を参照する。図面では同一の数字は同一の部品を指定する。図１は伝送回路１００のブロック図である。図示するように、伝送回路１００は、スケジューラ／オプティマイザ１０１、コントローラ１０３及び複数の伝送器１０５を備えている。動作の間、スケジューラ１０１に、システムパラメータが入力される。次いで、スケジューラ１０１は、各伝送器１０５に対する伝送パラメータの最適な集合を計算し、その情報をコントローラ１０３に移す。データ伝送の間、コントローラ１０３は、各ユーザに伝送されるべきデータを受信し、最適な伝送パラメータの集合を利用して、伝送器１０５を適切に制御する。データが伝送器１０５に移された時、伝送器１０５はその伝送パラメータを利用して、各ユーザにデータを適切に伝送する。
【００１０】
一例として、スケジューラ／オプティマイザ１０１はコントローラ１０３からユーザの集合を受信し、伝送するユーザを選択する。選択された各ユーザに対し、スケジューラ／オプティマイザ１０１は、特定の変調及び符号化方式（ＭＣＳ）、特定の伝送電力、特定の符号数及び特定の情報レートを含む物理層動作点（ＰＬＯＰ）を選択する。各ＰＬＯＰは、符号及び電力リソース全体のうちの異なった量を消費する。スケジューラ／オプティマイザ１０１は、システム全体が最適化されるように、各ユーザに対して“最適な”ＰＬＯＰを選択する。特に、各ユーザに対して最適なＰＬＯＰは、ユーザに割り当てられるレートの重みづけられた組み合せの和が最大化されるように選択される。重みベクトルの好ましい値は、その瞬間のスループットの推定値における効用関数の勾配である。
【００１１】
上述したように、スケジューラ／オプティマイザ１０１は所定の入力パラメータの集合に基づき、システム全体の性能を最適化するタスクを有している。本発明の好ましい実施形態において、これは、スケジューリング及びリソース配分アルゴリズムを最適化することにより達成される。以下の文章は、１）リソース配分アルゴリズムの生成、２）リソース配分アルゴリズムの最適化を説明している。
【００１２】
１  リソース配分アルゴリズムの生成
簡潔に記載すれば、スケジューリングアルゴリズムの最適化には、∇Ｕ（Ｗ※t，Ｑ※t）：＝φ∇W※Ｕ（Ｗ※t，Ｑ※t）−∇Q※Ｕ（Ｗ※t，Ｑ※t）により定義される（スループット及びキュー長の関数としての）“効用の勾配”と、各スケジューリング時刻ｔにおいて選択されるレートベクトルｒ※tとの内積を最大化することが含まれる。ここで、
Ｕは効用関数であり、
Ｗ※t＝（Ｗ1,t，．．．，Ｗd,t）はユーザのスループットの推定値であり、
Ｑ※t＝（Ｑ1,t，．．．，Ｑd,t）はユーザのキュー長又は遅延時間であり、
∇W※Ｕ（Ｗ※t，Ｑ※t）はＷ※に関するＵの偏微分ベクトルであり、
∇Q※Ｕ（Ｗ※t，Ｑ※t）はＱ※に関するＵの偏微分ベクトルであり、
ｒ※t＝（ｒ1,t，．．．，ｒd,t）は選択されたレートベクトルであり、かつ
ｄはユーザの数である。
【００１３】
つまり、状態に依存したレート範囲Ｒ（ｅ※t）から、効用の勾配による射影が最大となるレートベクトルを選択する。そのレート範囲はチャンネルの状態に依存する。そのチャンネルの状態が完全に既知でない間は、品質（例えば、ＣＱＩ）のフィードバック等により利用可能な幾らかの推定値の存在を仮定する。特に、各ユーザｉに対する伝送電力の単位ワットあたりの予想ＳＩＮＲｅi,tは既知であること、かつｅ※t＝（ｅ1,t，．．．，ｅd,t）はチャンネルの状態を反映していることを仮定する。
【００１４】
【数６】
2005176344.tif 000003
効用関数の特定のクラスに対して、
【００１５】
【数７】
2005176344.tif 000004
を得る。ここで、
ｃiはユーザｉに対するスループットに付随したＱｏＳの重みであり、
ｄiはユーザｉに対するキュー長に付随したＱｏＳの重みであり、
φはスループットに付随したフィルタ係数であり、
αはスループットに付随した公平さのパラメータであり、
ｐはキュー長に付随した公平さのパラメータである。
このように、本最適化問題は、
【００１６】
【数８】
2005176344.tif 000005
に帰着した。ここで、ｗiは上式（１）により与えられ、便宜上、時刻ｔの依存性は省いた。レートｒiの選択には、符号数ｎi及び電力ｐiを含む物理層動作点（ＰＬＯＰ）の選択が関連していることに注意されたい。これらのＰＬＯＰ変数は、
【００１７】
【数９】
2005176344.tif 000006
のようなシステムの制約及びユーザ一人あたりの制約を満たす必要があり、これらは、状態に依存したレート範囲Ｒ（ｅ※）の説明の一部である。アグラワルらによる米国特許出願公開第２００２／０１４７０２２号“無線通信システムにおけるパケットスケジューリング及び無線リソース配分のための方法”（以後、“アグラワルの公開特許”と称する）に記載されているように、単位符号あたりのレートは、単位符号あたりの信号対雑音比（ＳＩＮＲ）の関数として、
【００１８】
【数１０】
2005176344.tif 000007
のように記述され得る。ここで、その単位符号あたりのＳＩＮＲは、
【００１９】
【数１１】
2005176344.tif 000008
により与えられ、Γは適当な関数である。関数Γの妥当な選択は、周知の情報理論によるチャンネル容量の公式Γ（ｘ）＝Ｂｌｏｇ（１＋ｘ）である。Ｂをシンボルレート（チップレート／拡散率）に等しくおけば、このようなレートとＳＩＮＲとの間の関数関係はまた、高速ダウンリンクパケット接続（ＨＳＤＰＡ）ＭＣＳの表と一致する望ましい曲線を提供する。ここで、ＨＳＤＰＡに対しては、Ｂ＝３８４００００／１６＝２４００００シンボル／秒である。最適な曲線に一致させるためには、係数Ａ＝１．７だけ減少させたＳＩＮＲ、つまり、Γ（ｘ）〜Ｂｌｏｇ（１＋ｘ／Ａ）が使用されることにも注意されたい。この公式に代入することにより、ｅi，ｎi，ｐiの関数としてのレートｒiについての以下の式に帰着する。
【００２０】
【数１２】
2005176344.tif 000009
ＨＳ−ＰＤＳＣＨ符号に関する伝送電力の単位ワットあたりのＳＩＮＲは、
【００２１】
【数１３】
2005176344.tif 000010
により与えられることに注意されたい。表記の便宜上、ｅiをｅi／Ａにより再定義し、ＨＳ−ＰＤＳＣＨ符号に関する伝送電力の単位ワットあたりの“有効な”ＳＩＮＲは、つまり、
【００２２】
【数１４】
2005176344.tif 000011
である。その場合、レート範囲は、
【００２３】
【数１５】
2005176344.tif 000012
により与えられる。ｗiを以下のように再定義する。
【００２４】
【数１６】
2005176344.tif 000013
ここで、
ｗ※＝（ｗ1，．．．，ｗd）は勾配ベクトルであり、
Ｗ※＝（Ｗ1，．．．，Ｗd）は全てのユーザに対するスループットベクトルの推定値であり、
Ｑ※＝（Ｑ1，．．．，Ｑd）は全てのユーザ対するスループットベクトルの推定値であり、
ｃiはユーザｉに対するスループットに付随したＱｏＳの重み（場合によっては０）であり、
ｄiはユーザｉに対するキュー長に付随したＱｏＳの重み（場合によっては０）であり、
φはスループットに付随したフィルタ係数であり、
αはスループットに付随した公平さのパラメータであり、
ｐはキュー長に付随した公平さのパラメータであり、
Ｂは公式をビットに合わせるためのスケーリング定数である。
これは、重みベクトルｗ※＝（ｗ1，．．．，ｗd）の特定の例である。しかしながら、一般に，ｗiは、スループットＷiについては非増加型、かつキュー長Ｑiについては非減少型であるような、スループット及びキュー長の任意関数であっても構わない。その関数は、遅延時間の要求、ＱｏＳクラス、帯域幅の要求等のような情報に関連した様々なＱｏＳをパラメータとして含んでいても構わない。
【００２５】
本最適化問題は以下のように書き換えられる。
【００２６】
【数１７】
2005176344.tif 000014
条件、
【００２７】
【数１８】
2005176344.tif 000015
ここで、
【００２８】
【数１９】
2005176344.tif 000016
ｎ※は符号配分のベクトル、つまりユーザ一人あたりの符号を含んでいるベクトルであり、
ｐ※は電力配分のベクトル、つまりユーザ一人あたりの電力レベルを含んでいるベクトルであり、
ｗ※はｗiのベクトルであり、かつ
ｅ※はｅiのベクトルである。
制約集合χは凸であることに注意されたい。Ｖが（ｎ※，ｐ※）について凹であることを証明することもまた可能である。ユーザｉについて再伝送する場合は、そのユーザの単位符号、単位ワットあたりの“有効な”ＳＩＮＲｅiは、適切な係数だけ増加され得る。
【００２９】
上記制約に加えて、以下のユーザ一人あたりの電力制約も考慮されるが、それらの制約のいずれも、パラメータの適切な設定により重複するものとなり得る。
・ピーク電力制約
【００３０】
【数２０】
2005176344.tif 000017
・ＳＩＮＲ制約
【００３１】
【数２１】
2005176344.tif 000018
・単位符号あたりのレート（固定された変調の次数を仮定したエンコーダのレートは、この量の定数倍であることに注意されたい。すなわち、そのエンコーダのレートは、単位符号あたりのレートを符号化された出力レートにより割った量であり、その符号化された出力レート自体は、変調の次数（２又は４）とシンボルレート（ＨＳＤＰＡに対しては、２４００００シンボル／秒）との積である）
【００３２】
【数２２】
2005176344.tif 000019
・レート
【００３３】
【数２３】
2005176344.tif 000020
上記のユーザ一人あたりの電力制約は全て、
【００３４】
【数２４】
2005176344.tif 000021
の特別な場合である。ここで、関数ｓiは、（本最適化問題において）固定されたパラメータＰi，ｅi，Ｓi，（Ｒ／Ｎ）iにも依存している。実際に、上記制約の全ては、
【００３５】
【数２５】
2005176344.tif 000022
を伴う上記の単一の制約（６）に統合可能である。このうち関心があるのは、以下の特別な二つの場合である。
１．ｓi（ｎi）≡ｓiは、ｎiに依存しない。
２．ｓi（ｎi）≡ｓi＝∞．
ユーザ一人あたりの電力制約に伴い、制約集合χはさらに以下のように制限される。
【００３６】
【数２６】
2005176344.tif 000023
仮にｓi（ｎi）ｎiがｎiについて凹関数であるならば、その制約集合は凸であり続ける。上記の二つの特別な場合１、２に対しては、ｓi（ｎi）ｎiは、実際にｎiについて凹関数であることに注意されたい。しかしながら、レート制約の場合（式（１８））、ｓi（ｎi）ｎiはｎiについて凸関数である。
【００３７】
１．１  再伝送の取扱い
前述したように、再伝送のユーザは、二点について異なった取扱いをされる必要がある。
１．そのユーザの単位符号、単位ワットあたりの有効なＳＩＮＲは増加される必要がある。
２．そのユーザは、レートに関する等式の制約ｒi＝Ｒiを有する。
【００３８】
前者は、そのユーザのｅiを適切に調整することにより容易に取り扱うことが出来る。後者の制約を取り扱うために、レート制約が、
【００３９】
【数２７】
2005176344.tif 000024
と等価であることに注意しておく。
【００４０】
２．  スケジューラ／オプティマイザの動作
スケジューラ／オプティマイザ１０１は、パラメータの集合を受信し、式（３）のリソース配分アルゴリズムを最適化することによりＶ*を解く。より詳細には、スケジューラ／オプティマイザ１０１は、
Ｐ＝システム全体の伝送電力の最大値と、
Ｎ＝システムに対して利用可能な合計符号の最大値と、
Ｎ※＝システムの各ユーザに対する符号（例えば、拡散符号）数の最大値を含むベクトルと、
Ｒ※＝システムの各ユーザに対するデータレートの最大値を含むベクトルと、
Ｒ※／Ｎ※＝システムの各ユーザに対する単位符号あたりのデータレートの最大値を含むベクトルと、
Ｐ※＝システムの各ユーザに対する伝送電力の最大値を含むベクトルと、
Ｓ※＝システムの各ユーザに対する雑音（例えば、ＳＩＮＲ）の最大値を含むベクトルと、
ｅ※＝システムの各ユーザに対する単位電力（例えば、単位ワット）あたりの雑音（例えば、ＳＩＮＲ）を含むベクトルと、
Ｗ※＝システムの各ユーザに対する推定スループットベクトルを含むベクトルと、
Ｑ※＝システムの各ユーザに対するキュー長ベクトルを含むベクトルと、
ｃ※＝システムの各ユーザに対するスループットに付随したＱｏＳ重みを含むベクトルと、
ｂ※＝システムの各ユーザに対するキュー長に付随したＱｏＳ重みを含むベクトルとを受信する。
【００４１】
本発明の好ましい実施形態において、スケジューラ／オプティマイザ１０１は各ユーザｉに対するｒi、ｎi及びｐiの最適値を決定し、通信システム１００に対してベクトルｒ※、ｎ※及びｐ※を出力する。上述したように、通信システム１００におけるベクトルｒ※、ｎ※及びｐ※は、上述の入力パラメータの集合を与え、式（３）におけるＶ*を解くことにより決定される。スケジューラ／オプティマイザ１０１は、式（７）において上述した追加の制約条件の下、Ｖ*を解く。
【００４２】
２．１  第一の実施形態
【００４３】
【数２８】
2005176344.tif 000025
の場合、ｎi＝Ｎiが最適な符号配分であり、単に電力の最適化問題のみが残されるが、後に示すように、その問題を解くことは極めて容易である。以後、そのような場合ではない場合、すなわち、
【００４４】
【数２９】
2005176344.tif 000026
の場合を取り扱う。また、整数最適化問題を緩和して、ｎiは非整数値も取り得るとするが、殆どの場合、結果的には、その最適解のｎiには整数値が割り当てられることを見出す。
【００４５】
本最適化問題は、その双対定式化を見出すことにより解かれる。ラグランジアン
【００４６】
【数３０】
2005176344.tif 000027
を定義する。このラグランジアンに基づき、双対関数を定義できる。
【００４７】
【数３１】
2005176344.tif 000028
ここで、
χは制約集合（７）により与えられる（ｎ，ｐ）に対する妥当な選択の集合であり、
λは電力制約に対するラグランジュの未定乗数であり、
μは符号制約に対するラグランジュの未定乗数である。
その双対問題は、
【００４８】
【数３２】
2005176344.tif 000029
を見出すことにある。また、
【００４９】
【数３３】
2005176344.tif 000030
を定義する。
【００５０】
この部分的な解においては、レート制約（５）（再伝送に対しては、式（８））は無視をされるか、さもなくば、以下の“レート制約の取扱い”において説明するように、線形の制約により置き換えられる。
【００５１】
（注）  レート制約の取扱い
レート制約（５）又は（８）を含む制約集合は凸ではない。その結果、極めて容易にｎiに関する最適化を行うことは出来ないだろう。問題を簡単にするため、右辺の第二項においてｎi＝Ｎiと仮定する。このように、式（５）は、
【００５２】
【数３４】
2005176344.tif 000031
により置き換えられると仮定する。制約（８）の場合は、
【００５３】
【数３５】
2005176344.tif 000032
により置き換えられる。
【００５４】
この置き換えは、二、三の異なる理由により正当化され得る。第一に、多くの場合、ｎi＝Ｎiが最適であることを見出した。第二に、ｎi＝Ｎiの代入により、このユーザの状況は幾分悪化するが、（再伝送の場合における）ｅiの増加により、このユーザのｗiｅiは増加し、この増加は恐らくはこのユーザの選択をまだ促進する。上記制約に対して、異なる線形近似を試みることもまた可能であろう。この制約は符号配分の部分においてのみ必要であることに注意されたい。幾らかの他の経験側もまた可能である。例えば、レート制約を上記のものに置き換えることは可能であり、仮にこのユーザがまだ選択され、ｎi＝Ｎiを得られるならば、その場合、殆どいかなる犠牲も払っていないことになる。同様に、第二項において、ｎi＝１を試みることも出来よう、その場合は、そのユーザはより選択され易いだろう。仮にまだ選択されないならば、またしても、この近似により、恐らくはいかなる犠牲も払っていないことになる。しかしながら、（恐らくは稀であろう）中間の場合は、このユーザに対するｎiを明白に変化させ、最適化を行うことが望ましい。ひとたび符号配分が成されたならば、電力に関する最適化においては、その本来のレート制約が使用可能であることに注意されたい。
【００５５】
目的関数は凹であり、制約集合は凸であるため、双対ギャップは存在せず、主問題の解を計算するのに、その双対問題の解を使用することが可能となる。
これに基づき、スケジューラ／オプティマイザ１０１は、以下の（図２においても示す）ステップにより、ｒ※、ｎ※及びｐ※の適切な値を決定する。
１．全ての入力パラメータＰ、Ｎ、Ｎ※、Ｒ※、Ｒ※／Ｎ※、Ｐ※、Ｓ※、ｅ※、Ｗ※、Ｑ※、ｃ※、ｂ※を収集する（ステップ２０１）。
２．固定されたλ及びμに対して、最適な（ｎ※，ｐ※）を解析的に求める（ステップ２０３）。
３．次いで、λの固定は保ち、最適なμ*（λ）を求める（ステップ２０５）。
４．また、λの固定は保ち、式（１１）において定義されたＬ（λ）を計算する（ステップ２０７）。
５．最適なλ＝λ*を数値的に求める。言い換えれば、Ｌ*を得るためにＬ（λ）を最小にするλの値を求める（ステップ２０９）。
６．ｎ※＝ｎ※*（λ*，μ*（λ*））を計算する（ステップ２１１）。
７．ｎ※の固定を保ち、最適なｐ※及びｒ※を計算する（ステップ２１３）。
【００５６】
図２はスケジューラ／オプティマイザ１０１の動作を示すフローチャートである。その論理フローはステップ２０１により開始され、そこではオプティマイザ１０１により、ｅ※、Ｐ、Ｎ、Ｎ※及びＳ※が収集される。ステップ２０３において、λ及びμの固定を保つことにより、ｎ※及びｐ※が解析的に計算される。特に、λ及びμは固定されるが任意であり、ラグランジアンを最適化するｎ※及びｐ※はλ及びμの関数として計算され、式（９）に示す双対関数を得る。
【００５７】
ステップ２０５において、λは固定されているが任意であり、Ｌ（λ）を得るための最適なμ*（λ）は双対関数Ｌ（λ，μ）を最小化するように決定される。ステップ２０７において、Ｌ（λ）は式（２３）により計算され、ステップ２０９において、最適なλ＝λ*の数値的なサーチが行われる。言い換えれば、ステップ２０９において、λ＝λ*は、Ｌ*＝Ｌ（λ*）＝ｍｉｎλ≧0Ｌ（λ）となるように決定される。ステップ２１１において、ｎ※＝ｎ※*（λ*，μ*（λ*））が、式（１４）により計算される。ベクトルＲ※が収集され、ｎ※の固定を保ちながら、ｒ※及びｐ※が計算される（ステップ２１３）。特に、ｎ※はステップ５において得られた値に固定され、ｐ※及びｒ※は、実際のレート制約Ｒ※を考慮して、式（２１）及び（２）により計算される。最後に、ステップ２１５において、ｎ※、ｐ※及びｒ※の値がコントローラ１０３に出力され、伝送器１０５を介して、データのスケジュールを組み、かつ伝送するのに使用される。
【００５８】
以下の議論は、図２における上記ステップをさらに詳述する。
２．１．１  λ及びμは固定し、最適な（ｎ※，ｐ※）を解析的に計算するステップ２０３
固定されたλ、μ及びｎ※に対し、（双対な）ラグランジアンを最適化すると（これには、固定され、かつ実現可能なｎ※を仮定した電力に関する最適化が含まれる）、
【００５９】
【数３６】
2005176344.tif 000033
又は、等価な式として、
【００６０】
【数３７】
2005176344.tif 000034
を得る。結果として、単位符号あたりのＳＩＮＲは、
【００６１】
【数３８】
2005176344.tif 000035
により与えられる。
【００６２】
電力に関するいかなるユーザ一人あたりの制約も存在しない時、つまりｓi（ｎi）＝∞の時は、上式の最後の場合は不要である。ｓi（ｎi）≡ｓiがｎiに依存しない場合、その結果として得られる単位符号あたりのＳＩＮＲもやはり符号数ｎiに依存せず、その電力要求は符号数に関して線形にスケールすることに注意されたい。
【００６３】
【数３９】
2005176344.tif 000036
を定義する。次いで、場合１においては、ｓi（ｎi）≡ｓiはｎiに依存しない。加えて、
【００６４】
【数４０】
2005176344.tif 000037
もまたｎiに依存しない。この場合は、双対関数を計算するために、ラグランジアンをさらにｎiに関して最適化することは容易である。具体的には、
【００６５】
【数４１】
2005176344.tif 000038
を得る。μ＝ｗiｈ（ｗiｅi，ｓi，λ）の場合、任意の０≦ｎi≦Ｎiが最適であることに注意されたい。その時、双対関数は、
【００６６】
【数４２】
2005176344.tif 000039
により与えられる。ここで、
【００６７】
【数４３】
2005176344.tif 000040
である。
【００６８】
２．１．２  λを固定して、μを最適化するステップ２０５
双対関数（１５）をμに関して最適化するために、μi（λ）が降順になるようにユーザをソートする。ｊ*を、
【００６９】
【数４４】
2005176344.tif 000041
を満たす最小の整数とすると、
【００７０】
【数４５】
2005176344.tif 000042
であり、その最小化するμは、
【００７１】
【数４６】
2005176344.tif 000043
により与えられる。
【００７２】
上記順序により、μj（λ）≧μj+1（λ）であることに注意されたい。このように、μ*（λ）は閾値である。μi（λ）＞μ*（λ）を満たすユーザｉは、その符号の性能を完全に取得するが、μi（λ）＜μ*（λ）を満たすユーザｉは全く取得しない。また、ｗi≧ｗjかつｅi＞ｅjである場合、μi（λ）≧μj（λ）であることに注意されたい、ユーザｉには、ユーザｊにいかなる符号が配分されるよりも前に、完全な符号配分が与えられるだろう。これにより、公平さのパラメータα＝１（“最大Ｃ／Ｉスケジューラ”）であり、かつ全てのユーザが同一のＱｏＳ重みを有している場合、ｗiは定数であり、ユーザ全員に渡って同一であるため、ユーザのｅiの順で符号の割当量にユーザが詰められていくのが最適である。これは、本発明の別の実施形態の説明に関連して、以下に示される。
【００７３】
【数４７】
2005176344.tif 000044
の場合、符号和の制約を等式で満たし、かつμ＝μ*（λ）においてラグランジアンを最適化する一意的な実現可能なｎ※*が存在する。それは、
【００７４】
【数４８】
2005176344.tif 000045
により与えられる。しかしながら、仮に上記場合ではない場合は、同順位（ｔｉｅ）が存在し、ラグランジアンを最適化するｎ※*は複数個存在する。しかしながら、式（１８）及び（１２）により与えられる、ｎ※*、及びその結果として得られるｐ※*の選択の全てが実現可能という訳ではない。実現可能性を達成するためには、追加の符号及び電力制約をまた満たさなければならない。ｎ※*（λ）は上記で構成された最大化するｎ※のいずれかを意味するものとする。
【００７５】
最適な符号配分は以下の性質を有していることが正に示された。
１．Ｎi＝Ｎの場合、最大でも二人のユーザにスケジュールが組まれるのみである。
２．仮に全てのＮiが等しい場合、最大でも（［Ｎ／Ｎi］＋１）人のユーザにスケジュールが組まれるのみである。殆ど二人のユーザが完全な符号配分を得る。
３．一般に、殆ど二人のユーザが完全な符号配分を得る。
【００７６】
２．１．３  ｎ※の固定は保ちながら、ｒ※及びｐ※を計算するステップ２１３
ステップ２１３において、所定の符号配分ｎ※における電力最適化問題を解く。ｎ※は、ステップ２０３及び２０５を参照して上述したように導出されているか、或いは、予め定められており、本電力最適化アルゴリズムに入力として提供されていることに注意するべきである。その電力最適化アルゴリズムを
【００７７】
【数４９】
2005176344.tif 000046
条件
【００７８】
【数５０】
2005176344.tif 000047
により表す。
【００７９】
この問題は、その双対定式化を使用して、λ*（ｎ※）を求め、次いで、前述したように最適なｐ※*（ｎ※）を計算することにより解かれる。ｎ※は固定されているため、関数ｎiｓi（ｎi）には、それが非負でなければならないことを除いて、いかなる制限も課されない。このように、このステップにおいて実行される計算では、レート制約を組み入れることも可能である。
【００８０】
一般性を損なうことなく、符号配分がゼロのユーザを取り除く。正の符号配分のユーザの数をＭとする。第一に、電力和の制約が不使用か否か、つまり、
【００８１】
【数５１】
2005176344.tif 000048
か否かをチェックする必要がある。仮に不使用の場合は、最適な電力配分は正に個々の電力制約ｐi*＝ｎiｓi（ｎi）／ｅiそのものであり、この問題は完了である。
【００８２】
以下、この制約が使用される場合を取り扱う。この場合、最適電力が電力和の制約を等式により満たさなければならないことを示すことは可能である（さもなくば、ユーザの電力のうちの少なくとも一つが増加可能であり、その結果より大きな主問題の関数値をもたらすからである）。以下のように、電力和の制約のみにおけるラグランジアンを構成することが出来る。
【００８３】
【数５２】
2005176344.tif 000049
【００８４】
【数５３】
2005176344.tif 000050
の場合、二つのラグランジアンは等価である。その双対関数は、
【００８５】
【数５４】
2005176344.tif 000051
により与えられる。
【００８６】
電力に関して最適化するため、その制約集合は、関数ｓi（ｎi）ｎiに拘わらず、常に凸であることに注意されたい。ｐ※に関してＬp（ｐ※，λ）を最大化することは、前節で対象としたＬ（ｐ※，ｎ※，λ，μ）における問題と本質的に同一である。その最適なｐ※は以前と同様に式（１２）、つまり、
【００８７】
【数５５】
2005176344.tif 000052
により与えられる。
【００８８】
アグラワルの公開特許において、対応するｐ※*（ｎ※，λ）が
【００８９】
【数５６】
2005176344.tif 000053
を満たす場合に限り、λ*（ｎ※）はＬp（λ）を最適化することが示された。式（１９）を代入すると、λ*（ｎ※）は以下の方程式の解のいずれかにより与えられるということが分かる。
【００９０】
【数５７】
2005176344.tif 000054
その時、最適な電力配分ベクトルｐ※*（ｎ※）は、
【００９１】
【数５８】
2005176344.tif 000055
により与えられる。λは式（２０）の両辺において現れるため、λ*（ｎ※）について解くことは困難に思われる。この問題に対する解のアルゴリズムを以下のように提供する。
【００９２】
ユーザｉ＝１，．．．，Ｍに対して、
【００９３】
【数５９】
2005176344.tif 000056
を定義する。ａi＜ｂiに注意されたい。集合｛ａi，ｂi；ｉ＝１，．．．，２Ｍ｝を降順の数の集合｛ｘ［ｌ］；ｌ＝１，．．．，２Ｍ｝にソートする。また、各ｌ＝１，．．．，２Ｍに対し、仮にｘ［ｌ］＝ｂi又はｘ［ｌ］＝ａiの場合、ｙ［ｌ］：＝ｉ、かつ
【００９４】
【数６０】
2005176344.tif 000057
とする。同順位がある場合は任意の方法で解消される。次いで、
【００９５】
【数６１】
2005176344.tif 000058
を満たす最大のλ∈｛ｘ［ｌ］；ｌ＝１，．．．，２Ｍ｝、つまり
【００９６】
【数６２】
2005176344.tif 000059
を満たす最小のｌを求める。イギリスのケンブリッジにおいて、２００４年３月に開催されたＷｉＯｐｔ０４会議において発表された、Ｒ．アグラワル、Ｖ．スブラマニアン及びＲ．ベリーによるタイトル“ＣＤＭＡシステムにおけるジョイントスケジューリング及びリソース配分”の論文（以後、“アグラワルの論文”と称する）において、
【００９７】
【数６３】
2005176344.tif 000060
が示され、式（２０）の解が与えられた。さらに、上記範囲のλに対して、式（２０）における指標はλの特定の値に依存せず、それゆえに直ちにλの計算可能な表現を得る。
【００９８】
以下に、上式（２０）の解を求めるアルゴリズムについての擬似コードを提供する。そのアルゴリズムの計算量はソートのためにＯ（ＭｌｏｇＭ）である。
解λ*（ｎ※）の好ましい実施形態のための擬似コード
【００９９】
【数６４】
2005176344.tif 000061
ここで、ｓ*（ｗiｅi／λ，ｓi（ｎi））は、式（１３）により定義されている。
【０１００】
２．１．３．１  ユーザ一人あたりの等式の制約の場合
仮に一部のユーザｉについて、レートが固定される再伝送の場合に発生し得るように、不等式ｐi≦ｅiｓi（ｎi）ｎiが等式の制約ｐi＝ｅiｓi（ｎi）ｎiに置き換えられている場合は、単に、このユーザを問題から取り除き、Ｐからｐiを差し引いた後、前述のように取り扱えばよい。
【０１０１】
２．１．３．２  ユーザ一人あたりの電力制約が無い場合
ｓi（ｎi）＝∞の場合は、以下のより簡単なアルゴリズムにより、λ*（ｎ※）は求められる。第一に、一般性を損なうことなく、ｗiｅiが降順になるようにユーザは番号付けられていると仮定する。以下を計算する。
【０１０２】
【数６５】
2005176344.tif 000062
以下のようにλ*（ｎ※）を決定する。
【０１０３】
【数６６】
2005176344.tif 000063
２．１．４  Ｌ*を取得するステップ２０９
λに関してＬ（λ）を最小化する、若しくは最小化を試みる任意のアルゴリズムが、以下に考察される。好ましい実施形態において、繰り返してアルゴリズムを実行する。その場合、繰り返しの各ステップｋにおける最適なλ*の範囲［λkLB，λkUB］は、ｋ＝０において、０≦λ0LB≦λ0UB＜∞により開始され、特定のｄ≧１かつ０≦ρ＜１に対し、
【０１０４】
【数６７】
2005176344.tif 000064
を満たすように狭くなる。
【０１０５】
複数のそのようなスキームが設計され得るが、それらの全てが等比級数的に早く最適なλ*に収束することを保証する。二つのそのような実施形態を以下に記載する。
２．１．４．１  λ*を求めるための第一の実施形態
本アルゴリズムは、先に定義した関数Ｌ（λ）（１１）、ｎ※*（λ）（１８）及びその同順位の解消、λ*（ｎ※）（２０）、ｐ※*（ｎ※）（２１）並びにＶ（ｐ※，ｎ※）（４）を使用する。関数ｒ※（ｐ※，ｎ※）は式（２）により与えられ、単に、電力及び符号により決定されるレートである。λ*（ｎ※）を計算するための擬似コードはまた、ステップ２１３において与えられている。
【０１０６】
アグラワルの論文において、Ｌ（λ）は凸であり、最適なλ*＝ａｒｇｍｉｎλ≧0Ｌ（λ）∈［λmin，λmax］、ここでλmin＝０及びλmax＝ｍａｘiｗiｅiであることが示されている。
【０１０７】
ｋ回目の繰り返しにおいて、λ*の推定値をλk*により与え、λ*は範囲［λkLB，λkUB］内にあると同定する。ｋ回目である時はいつでも、アルゴリズムの状態は、仮定Ｌk*＝Ｌ（λk*）≦ｍｉｎ（ＬkUB＝Ｌ（λkUB），ＬkLB＝Ｌ（λkLB））を伴う、
【０１０８】
【数６８】
2005176344.tif 000065
により与えられる。
【０１０９】
ステップ０は、本アルゴリズムの状態を初期化し、幸運にも最適配分に的中した場合における終了検査を提供する。
ステップ１は、上記アルゴリズムの状態の繰り返しを実行し、また終了検査を使用する。
【０１１０】
ステップ２は、追加の制約を考慮し、電力を再最適化し、かつレート／ＴＢＳ等を計算することにより結果を洗練する。
本アルゴリズムは以下のように動作する。
【０１１１】
ステップ０：初期化
（ａ）λ0LB＝０
（ｂ）少なくとも一人のユーザにおいて、そのユーザ一人あたりの電力制約が存在しない場合、Ｌ（λ0LB）＝＋∞
（ｃ）さもなくば、Ｌ（λ0LB）を計算する
（ｄ）ｗiｅiが降順になるようにユーザをソートする
（ｅ）
【０１１２】
【数６９】
2005176344.tif 000066
を満たす最小のｊ*を求める
（ｆ）ｎ※0*を定義する
【０１１３】
【数７０】
2005176344.tif 000067
（ｇ）ｊ*について同順位が存在する場合、より大きなｗiを有するユーザを選択し、仮にｗiも等しい場合は、どちらかを選択する
（ｈ）仮に
【０１１４】
【数７１】
2005176344.tif 000068
ならば、その場合、
【０１１５】
【数７２】
2005176344.tif 000069
（ｉ）さもなくば、
【０１１６】
【数７３】
2005176344.tif 000070
（ｊ）仮にＰreq≧Ｐならば、その場合、ステップ２へ移行
（ｋ）仮に
【０１１７】
【数７４】
2005176344.tif 000071
ならば、その場合、
【０１１８】
【数７５】
2005176344.tif 000072
さもなくば、
【０１１９】
【数７６】
2005176344.tif 000073
（ｌ）Ｌ0UB＝Ｌ（λ0UB）を計算する
（ｍ）仮にＬ0LB≦Ｌ0UBならば、その場合、λ0*＝λ0LB；Ｌ0*＝Ｌ0LB
（ｎ）さもなくば、λ0*＝λ0UB；Ｌ0*＝Ｌ0UB
ステップ１：繰り返し  Ｆｏｒ（ｋ＝０，ｋ＜繰り返しの制限，ｋ＋＋）
（ａ）仮にＬk*＞ｍｉｎ（ＬkLB，ＬkUB）ならば、その場合、エラー！
（ｂ）λk+1CAND＝λ*（ｎ※k*）を計算する
（ｃ）Ｌk+1CAND＝Ｌ（λk+1CAND）、ｎ※k+1CAND＝ｎ※*（λk+1CAND）を計算する
（ｄ）λ*（ｎ※k+1CAND）、ｐ※k+1CAND＝ｐ※*（ｎ※k+1CAND）を計算する
（ｅ）Ｖ（ｎ※k+1CAND）を計算する
（ｆ）仮にＶ（ｎ※k+1CAND）＞（１−［ｅｐｓｉｌｏｎ］）ｍｉｎ｛Ｌk+1CAND，Ｌk*｝ならば、その場合、ステップ２へ移行
（ｇ）仮にＬk+1CAND＜Ｌk*、λk+1CAND＞λkLB＋［ｅｐｓｉｌｏｎ］（λkUB−λkLB）、λk+1CAND＜λk+1UB−［ｅｐｓｉｌｏｎ］（λkUB−λkLB）、かつλk+1CAND≠λk*ならば、
より早いトラックを試みる
ｉ．仮にλk+1CAND＜λk*ならば、
【０１２０】
【数７７】
2005176344.tif 000074
ｉｉ．さもなくば、
【０１２１】
【数７８】
2005176344.tif 000075
（ｈ）さもなくば、
二分法を実行する
ｉ．仮にλk*−λkLB≧λkUB−λk*ならば、その場合、
Ａ．λk+1CAND＝（λkLB＋λk*）／２を与える
Ｂ．Ｌk+1CAND＝Ｌ（λk+1CAND）、ｎ※k+1CAND＝ｎ※*（λk+1CAND）を計算する
Ｃ．λ*（ｎ※k+1CAND）、ｐ※k+1CAND＝ｐ※*（ｎ※k+1CAND）を計算する
Ｄ．Ｖ（ｎ※k+1CAND）を計算する
Ｅ．仮にＶ（ｎ※k+1CAND）＞（１−［ｅｐｓｉｌｏｎ］）ｍｉｎ｛Ｌk+1CAND，Ｌk*｝ならば、その場合、ステップ２へ移行
Ｆ．仮にＬk+1CAND≦Ｌk*ならば、その場合、アルゴリズムの状態を以下のように変化させる
【０１２２】
【数７９】
2005176344.tif 000076
Ｇ．さもなくば、以下のように変化させる
【０１２３】
【数８０】
2005176344.tif 000077
ｉｉ．さもなくば、
Ａ．λk+1CAND＝（λkUB＋λk*）／２を与える
Ｂ．Ｌk+1CAND＝Ｌ（λk+1CAND）、ｎ※k+1CAND＝ｎ※*（λk+1CAND）を計算する
Ｃ．λ*（ｎ※k+1CAND）、ｐ※k+1CAND＝ｐ※*（ｎ※k+1CAND）を計算する
Ｄ．Ｖ（ｎ※k+1CAND）を計算する
Ｅ．仮にＶ（ｎ※k+1CAND）＞（１−［ｅｐｓｉｌｏｎ］）ｍｉｎ｛Ｌk+1CAND，Ｌk*｝ならば、その場合、ステップ２へ移行
Ｆ．仮にＬk+1CAND≦Ｌk*ならば、その場合、アルゴリズムの状態を以下のように変化させる
【０１２４】
【数８１】
2005176344.tif 000078
Ｇ．さもなくば、以下のように変化させる
【０１２５】
【数８２】
2005176344.tif 000079
ステップ２：
（ａ）ｎ※＊の整数化−同順位の場合、二人のユーザが非整数の配分を得る可能性があることに注意されたい。その場合、単位符号あたりの電力要求がより大きい一方の配分の小数点以下は繰り下げ、他方の配分の小数点以下は繰り上げる。
（ｂ）レート制約を含む全ての制約を考慮して、ｐ※*（ｎ※*）を再計算する。
（ｃ）ｒi*＝（２４００００／ｌｎ２）・ｎi*ｌｎ（１＋ｐi*ｅi／ｎi*）により与えられるレートｒ※*＝ｒ※（ｐ※*，ｎ※*）及びＴＢＳ＝ｒi×０．００２を計算する。最も近いバイト、又は尚粗い量子化にまで繰り下げる。
完全な二分法に基づいたサーチアルゴリズムを得るために、ステップ１におけるステップ（ｂ）−（ｇ）を省略することも可能である。
【０１２６】
２．１．４．２  λ*を求めるための第二の実施形態
最適なλ*を求めるための第二の実施形態では、その最小化を補助するためにＬ（λ）の劣勾配が使用される。任意に定められたλに対して、劣勾配は以下のように容易に求められる。
１．第一に、式（１８）におけるｎ※*（λ）を求める。“同順位”の場合は、（式（１８）以下で説明したように）電力和の制約を等式で満たし、かつラグランジアンを最適化する全ての実現可能な符号配分が考慮される。
２．次いで、ｎ※*（λ）を使用して、式（１２）により与えられるような対応するｐ※*を求める。
３．その時、
【０１２７】
【数８３】
2005176344.tif 000080
がλにおけるＬ（λ）の劣勾配である。
４．Ｌ（λ）は凸であるので、Ｌ（λ*）の劣勾配がゼロである場合にのみ、λ*は最適となる。
５．このように、劣勾配がゼロであるλを数値的にサーチすることにより、Ｌ（λ）を最小化する最適なλ*を求めることが可能である。
【０１２８】
２．２  他の実施形態
上記の結果に基づき、スケジューラ／オプティマイザ１０１は、以下のように、ｒ※、ｎ※及びｐ※の適切な値を決定する。
１．全ての入力パラメータＰ、Ｎ、Ｎ※、Ｒ※、Ｒ※／Ｎ※、Ｐ※、Ｓ※、ｅ※、Ｗ※、Ｑ※、ｃ※、ｂ※を収集する（ステップ３０１）。
２．ｎ※を計算する（ステップ３０３）。
３．ｎ※の固定を保ち、最適なｐ※及びｒ※を計算する（ステップ３０５）。
【０１２９】
これは図３に示されている。図３は、本発明の別の実施形態によるスケジューラ／オプティマイザ１０１の動作を示すフローチャートである。その論理フローはステップ３０１により開始され、そこではオプティマイザ１０１により、Ｐ、Ｎ、Ｎ※、Ｒ※、Ｒ※／Ｎ※、Ｐ※、Ｓ※、ｅ※、Ｗ※、Ｑ※、ｃ※及びｂ※が収集される。第一の実施形態のステップ２−５は、実際には、最適なｎ※を計算するための補助ステップであったことに注意されたい。入力パラメータＰ、Ｎ、Ｎ※、Ｒ※、Ｒ※／Ｎ※、Ｐ※、Ｓ※、ｅ※、Ｗ※、Ｗ※、Ｑ※、ｃ※及びｂ※に基づき、ｎ※を計算するための任意の他の方法も考慮される（ステップ３０３）。次いで、ｎ※の固定を保ち、ｒ※及びｐ※が計算される（ステップ３０５）。特に、ｎ※は、ステップ３０３において取得した値に固定され、ｐ※及びｒ※は、実際のレート制約Ｒ※を考慮して、式（２１）及び（２）により計算される。最後に、ステップ３０７において、ｎ※、ｐ※及びｒ※の値がコントローラ１０３に出力され、伝送器１０５を介して、データのスケジュールを組み、かつ伝送するのに使用される。
【０１３０】
入力パラメータｅ※、Ｐ、Ｎ、Ｎ※及びＳ※に基づき、ｎ※を計算する別の方法を以下に提示する。
１．ｗi及びｅiを含む入力パラメータの関数である任意の尺度に基づいて、ユーザをソートする。
２．
【０１３１】
【数８４】
2005176344.tif 000081
を満たす最小のｊ*を求める。
３．ｎ※0*を定義する。
【０１３２】
【数８５】
2005176344.tif 000082
４．ｊ*について同順位の場合、より大きなｗiを有するユーザを選択し、仮にｗiも等しい場合は、どちらかを選択する。
５．状況に応じて、前節において説明したアルゴリズムの繰り返しを複数回実行することも可能である。
【０１３３】
本発明を、特定の実施形態を参照して、詳細に示し、かつ説明したが、形態及び詳細の様々な変更が本発明の技術思想及び範囲から逸脱することなくなされることを、当業者は理解されよう。例えば、上記例はＨＳＤＰＡシステム内での実施に関するものであるが、上記実施形態を、符号及び／又は電力が配分される必要性がある任意の通信システムに移植することが可能であることは当業者にとっては当然のことであろう。そのような変更は、以下の請求項の範囲内にあると意図されている。
【０１３４】
尚、外国書面出願の英文明細書中にＪＩＳコードで表記できない箇所があったため、この翻訳文では代替表記を使用した、具体的には、ベクトルＮ※、Ｒ※、Ｒ※／Ｎ※、Ｐ※、Ｓ※、ｅ※、Ｗ※、Ｑ※、ｃ※、ｂ※、ｎ※、ｐ※及びｒ※は、
【０１３５】
【数８６】
2005176344.tif 000083
のように、外国語書面出願の明細書ではボールド体により表現されていたが、便宜上、翻訳文では※を付けて表現した。但し、数１から数８６の部分の数式については、外国語書面の明細書と同一のボールド体により、ベクトルは表現されている。
【図面の簡単な説明】
【０１３６】
【図１】本発明の一実施形態による伝送回路のブロック図。
【図２】本発明の一実施形態による図１の回路の動作を示すフローチャート。
【図３】本発明の別の実施形態による図１の回路の動作を示すフローチャート。
【図１】
2005176344.tif 000089
【図２】
2005176344.tif 000090
【図３】
2005176344.tif 000091
【外国語明細書】
2005176344.tif 000092
2005176344.tif 000093
2005176344.tif 000094
2005176344.tif 000095
2005176344.tif 000096
2005176344.tif 000097
2005176344.tif 000098
2005176344.tif 000099
2005176344.tif 000100
2005176344.tif 000101
2005176344.tif 000102
2005176344.tif 000103
2005176344.tif 000104
2005176344.tif 000105
2005176344.tif 000106
2005176344.tif 000107
2005176344.tif 000108
2005176344.tif 000109
2005176344.tif 000110
2005176344.tif 000111
2005176344.tif 000112
2005176344.tif 000113
2005176344.tif 000114
2005176344.tif 000115
2005176344.tif 000116
2005176344.tif 000117
2005176344.tif 000118
2005176344.tif 000119
2005176344.tif 000120
2005176344.tif 000121
2005176344.tif 000122
2005176344.tif 000123
2005176344.tif 000124
2005176344.tif 000125
2005176344.tif 000126
2005176344.tif 000127
2005176344.tif 000128
2005176344.tif 000129