(57)【要約】【課題】共用ダウンリンク上でリアルタイムサービスを提供する無線システムに非常に適したな呼承認制御方法、装置を実現する。【解決手段】呼承認制御技術は多重化およびマルチユーザダイバーシティ利得の両方を考慮する。ユーザごとの資源割り当ての測定により正確にマルチユーザダイバーシティ利得を決定し、好都合に、位置依存の資源利用性制約だけでなくサービス品質（ＱｏＳ）の下でユーザ収用能力を最大限にする。さらなる態様において、呼承認制御技術は、システム効率（チャネル使用率）とユーザ期待値（例えばサービス品質）の間のバランスを有効に保つ、遅延ベースのスケジューリングと組み合わされる。説明した呼承認制御およびスケジューリング技術を具体化するシステムは、好都合に効率的なリアルタイムサービスを実現でき、システムダイナミクスおよび／またはユーザ移動性によって変化する異なった負荷に対する堅牢性を保つ。【選択図】図１
2007159131.tif 000002
【特許請求の範囲】
【請求項１】
通信資源のスケジューリング決定を受け取ること、
前記スケジューリング決定に基づいて通信資源の既存の負荷を測定すること、
付加された新規ユーザの負荷を推定すること、
前記既存の負荷の測定と前記付加された負荷の推定を組み合わせて組み合わせ負荷を決定すること、
前記組み合わせ負荷をシステム容量と比較すること、
前記組み合わせ負荷が前記システム容量を上回らない場合、前記新規ユーザを承認すること、
を含む承認制御方法。
【請求項２】
前記スケジューリング決定はほぼ瞬間的である請求項１に記載の方法。
【請求項３】
前記既存の負荷の測定は前記スケジューリング決定に従って割り当てられた無線資源を測定することを含む、請求項１に記載の方法。
【請求項４】
前記通信資源は共用ダウンリンク無線チャネルである請求項１に記載の方法。
【請求項５】
下記条件が満たされる場合、前記新規ユーザが承認される
【数１】
2007159131.tif 000039
ここで、Ｋは承認されたユーザｋの数、ｍｋは承認されたユーザｋのプロフィール率、ｍｉは新規ユーザのプロフィール率、Ｅ［ｒｉ（ｔ）］は時間ｔでの前記新規ユーザの推定チャネル速度、Ｂｋ（ｔ）は、時間ｔで前記承認されたユーザｋに割り当てられた通信資源の平均測定値である、請求項１に記載の方法。
【請求項６】
【数２】
2007159131.tif 000040
が満足される、ここで、ｒｋ（ｔ）は時間ｔでの承認されたユーザｋのチャネル速度、Ｉｋ（ｔ）は時間ｔでの前記承認されたユーザｋに対する前記スケジューリング決定である、請求項５に記載の方法。
【請求項７】
前記組み合わせ前記負荷がシステム容量を越える場合、前記新規ユーザを拒絶することを含む、請求項１に記載の方法。
【請求項８】
前記方法はセルラー基地局で実行される請求項１に記載の方法。
【請求項９】
前記スケジューリング決定を生成することを含む、請求項１に記載の方法。
【請求項１０】
前記スケジューリング決定は最大コスト控除（ＭＣＤ）アルゴリズムに従って生成される、請求項９に記載の方法。
【請求項１１】
前記ＭＣＤアルゴリズムは遅延ベースの重み関数を持つリアルタイムＭＣＤアルゴリズムである、請求項１０に記載の方法。
【請求項１２】
前記遅延ベースの重み関数は線形関数である請求項１１に記載の方法。
【請求項１３】
前記遅延ベースの重み関数は指数関数である請求項１１に記載の方法。
【請求項１４】
前記ＭＣＤアルゴリズムはレートベースの重み関数を持つ非リアルタイムＭＣＤアルゴリズムである、請求項１０に記載の方法。
【請求項１５】
前記レートベースの重み関数は線形関数である請求項１４に記載の方法。
【請求項１６】
前記スケジューリング決定はセルラー基地局で生成される、請求項９に記載の方法。
【請求項１７】
前記方法は無線ネットワーク制御装置で実行される請求項１に記載の方法。
【請求項１８】
前記スケジューリング決定を生成することを含み、前記スケジューリング決定はセルラー基地局で生成される、請求項１７に記載の方法。
【請求項１９】
通信資源のスケジューリング決定を受け取り、前記スケジューリング決定に基づいて通信資源の既存の負荷を測定し、付加された新規ユーザの負荷を推定し、前記既存の負荷の測定と前記付加された負荷の推定を組み合わせて組み合わせ負荷を決定する負荷推定器と、
前記組み合わせ負荷をシステム容量と比較し、前記組み合わせ負荷が前記システム容量を上回らない場合、前記新規ユーザを承認する判定部と、
を含む承認制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に承認制御技術に関し、特に、無線パケットデータシステムのユーザの承認制御方法および装置に関する。
【背景技術】
【０００２】
次世代無線システムは、リアルタイムサービスのようなオンデマンド用途を支援すると予想されている。共用ダウンリンクチャネル上のリアルタイムサービスは、リアルタイムスケジューラだけでなく、一般に呼承認制御（ＣＡＣ：call admission control）と呼ばれる効率的な承認制御も必要である（なお、ここに使用している、用語「呼（call）」は電話呼またはいかなる特定のメディアタイプにも限定されないことに留意されたい）。
【０００３】
承認制御は、システムが既存のユーザのサービス品質（ＱｏＳ：quality of service）を犠牲にすることなく、新着のユーザ、またはストリーミングビデオまたはＶｏｌＰリクエストのような呼を収容する資源を持っているかどうかを判断するものである。該ＣＡＣ機能は、各ユーザに対する保証されたサービスの要件を満たしながら、ユーザがセル領域への出入りを継続的に行っているセルラー無線システムのようなシステムにとって特に重要である。
【０００４】
承認制御はシステムの必須部分であり、そのようなシステムにおいてＱｏＳを促進する重要な要素の１つである。承認制御は、システムがどれくらい効率的になりえるか、すなわち無線システムがどれだけのリアルタイムユーザを支援できるかを直接的に判断する。そのため、承認制御は、ユーザの満足度、ひいてはシステムの収入に大きな影響を及ぼすことになる。
【０００５】
Proportional Fairness（ＰＦ）法、Modified largest weighted delay first（ＭＬＷＤＦ）法、およびExponential rule（Ｅｘｐ−Ｒｕｌｅ）アルゴリズムを含む、根本的なパケットレベルのスケジューリング手法に関する多くの選択肢がある。
【０００６】
ところが、リアルタイムスケジューリングアルゴリズム、特に、共有チャネルセルラーシステム用のリアルタイムスケジューリングアルゴリズムはＭＬＷＤＦ法およびＥｘｐ−Ｒｕｌｅアルゴリズム以外にはわずかしかない（非特許文献１および２を参照されたい）。
【０００７】
ＭＬＷＤＦ法およびＥｘｐ−Ｒｕｌｅアルゴリズムは、共に、ユーザごとの荷重が行頭（ＨＯＬ：head-of line）パケット遅延に等しくなる、ＰＦ法の荷重版である。上記方法は「スループット最適」を示しているが、それらは必ずしも遅延最適ではない。
【０００８】
有線ネットワークシステムでは、最早納期（ＥＤＤ：earliest due date）および最短消去（ＳＴＥ：shortest time extinction）アルゴリズムが、それぞれ平均キューイング遅延および最終期限違反パケットロスを最小化するのに最適であることが示されている。
【０００９】
一方、最も単純なスケジューリングアルゴリズムとしては、ＦＩＦＯキューイングが最大キューイング遅延を最小化するものとして知られている。着信したパケットがすべて同一の終了時間Ｄsを持つという単純な事例では、ＥＤＤアルゴリズムとＦＩＦＯキューイングの結果は等しくなる。しかしながら、これらの手法はチャネルに対する認識が不足していることからセルラー環境での効率は低い。
【００１０】
承認制御については、各ユーザが出力制御専用チャネルを持つ、レガシー回路切替えセルラーシステムに適用可能な承認制御技術が多数存在するのとは対照的に、セルラーダウンリンク共有チャネルシステムにおけるフローまたはユーザレベル承認制御を処理する技術はわずかであった。フローレベルでは、ほんの少数の承認制御技術がそのようなシステムに対して提案されている（非特許文献３および４を参照されたい）。
【００１１】
しかし、上記手法は、スケジューラ（またはパケット）レベルでのマルチユーザダイバーシティ利得の無視に起因する効率の悪さに苦慮している。マルチユーザダイバーシティ利得を活用するためには、発信者がシステムのスペクトル効率を最大にするように最良チャネル品質を持つ受信機を選ぶ必要がある。
【００１２】
一方、遅延認識により、または、そのような利得を活用する、いくつかのチャネル依存の便宜主義的スケジューリングアルゴリズムがある。しかしながら、これらのスケジューリング手法は、固定数のユーザまたは静的なトラヒック負荷のシステムを想定しているものである。
【００１３】
特にセルラーシステムでは、各ユーザの負荷と、位置依存性およびユーザ固有のチャネル品質が与えられたシステム全体の負荷とを正確に捕らえる点において、および、ユーザごとのＱｏＳと便宜主義的スケジューラとが与えられた無線資源を特徴づける点において大きな課題がある。
【非特許文献１】M. Andrews et al., ”Providing Quality of Service over a Shared Wireless Link, ”IEEE Commun. Mag.,pp.15054(Feb.2001)
【非特許文献２】S. Shakkottai and A. Stolyar, ”Scheduling Algorithms for Mixture of Real-time and NonReal-time Data in HDR, ”in Proceedings 17th Int. TeletrafficCongress(ITC17)(Sept.2001)
【非特許文献３】T. Bonald and A. Proutiere, ”Wireless Downlink Data Channels: User Performance and Cell Dimensioning, ”Proceedings of ACM MOBICOM,pp.33952(Sept.2003)
【非特許文献４】S.Das, H. Viswanathan, G. Rittenhouse, ”Dynamic Load Balancing Through Coordinated Scheduling in Packet Data Systems, ”IEEE Proceedings of INFOCOM,pp.78696(April 2003)
【発明の開示】
【発明が解決しようとする課題】
【００１４】
共有チャネルセルラーシステム用のリアルタイムスケジューリングアルゴリズムはＭＬＷＤＦ法およびＥｘｐ−Ｒｕｌｅアルゴリズム以外にはわずかしかなく、ＭＬＷＤＦ法およびＥｘｐ−Ｒｕｌｅアルゴリズムは、「スループット最適」となるものの、それらは必ずしも遅延最適ではない。
【００１５】
最も単純なスケジューリングアルゴリズムとしては、ＦＩＦＯキューイングが最大キューイング遅延を最小化するものとして知られ、着信したパケットがすべて同一の終了時間Ｄsを持つという単純な事例では、ＥＤＤアルゴリズムとＦＩＦＯキューイングの結果は等しくなるが、これらの手法はチャネルに対する認識が不足していることからセルラー環境での効率は低い。
【００１６】
承認制御については、セルラーダウンリンク共有チャネルシステムにおけるフローまたはユーザレベル承認制御を処理する技術はわずかであった。フローレベルでは、非特許文献３および４に開示されるようなほんの少数の承認制御技術が提案されているが、これらはスケジューラ（またはパケット）レベルでのマルチユーザダイバーシティ利得の無視に起因する効率の悪さに苦慮している。マルチユーザダイバーシティ利得を活用するためには、発信者がシステムのスペクトル効率を最大にするように最良チャネル品質を持つ受信機を選ぶ必要がある。
【００１７】
遅延認識、または、そのような利得を活用する、いくつかのチャネル依存の便宜主義的スケジューリングアルゴリズムでのスケジューリング手法は、固定数のユーザまたは静的なトラヒック負荷のシステムを想定しているものであり、セルラーシステムに用いる場合には、各ユーザの負荷と、位置依存性およびユーザ固有のチャネル品質が与えられたシステム全体の負荷とを正確に捕らえる点において、および、ユーザごとのＱｏＳと便宜主義的スケジューラとが与えられた無線資源を特徴づける点において大きな課題がある。
【００１８】
本発明は上述したような従来の技術が有する課題に鑑みてなされたものであって、共用ダウンリンク上でリアルタイムサービスを提供する無線システムに非常に適したな呼承認制御方法、装置を実現することを目的とする。
【課題を解決するための手段】
【００１９】
本発明の承認制御方法は、
通信資源のスケジューリング決定を受け取ること、
前記スケジューリング決定に基づいて通信資源の既存の負荷を測定すること、
付加された新規ユーザの負荷を推定すること、
前記既存の負荷の測定と前記付加された負荷の推定を組み合わせて組み合わせ負荷を決定すること、
前記組み合わせ負荷をシステム容量と比較すること、
前記組み合わせ負荷が前記システム容量を上回らない場合、前記新規ユーザを承認すること、
を含む。
【００２０】
また、本発明の承認制御装置は、通信資源のスケジューリング決定を受け取り、前記スケジューリング決定に基づいて通信資源の既存の負荷を測定し、付加された新規ユーザの負荷を推定し、前記既存の負荷の測定と前記付加された負荷の推定を組み合わせて組み合わせ負荷を決定する負荷推定器と、
前記組み合わせ負荷をシステム容量と比較し、前記組み合わせ負荷が前記システム容量を上回らない場合、前記新規ユーザを承認する判定部と、
を含む。
【発明の効果】
【００２１】
第１の態様において、本発明は共用ダウンリンクチャネルを持つ無線システムに呼承認制御技術を提供する。本発明の呼承認制御技術の典型的な実施形態は、多重化と、ユーザごとの資源割り当てのオンライン測定またはリアルタイム測定によって正確に捕らえられるマルチユーザダイバーシティ利得との両方を考慮している。本発明の承認制御技術は、ＱｏＳにおける制約（例えばユーザごとのプロフィール率の期待値）、および位置に依存する資源利用性の制約の下で、ユーザ収容能力を最大限にする。
【００２２】
さらなる本発明の態様として、前述の呼承認制御を、ここで最大のコスト控除（ＭＣＤ）スケジューリングと呼ばれる遅延ベースのスケジューリングと組み合わせる。システム効率（チャネル使用率）とユーザ期待値（例えばＱｏＳ）の間で効果的にバランスを保つ、スケジューラのいくつかの典型的な実施形態が挙げられる。リアルタイムＭＣＤ（ｒｔ−ＭＣＤ）と呼ばれる第１のスケジューラにより、未処理パケットの遅延派生のコスト関数を最も小さな時間的尺度（例えばスロットレベル）に最小化する。非リアルタイムＭＣＤ（ｎｒｔ−ＭＣＤ）と呼ばれる第２のスケジューラインプリメンテーションがリアルタイム遅延低減と非リアルタイム（すなわち大きな時間的尺度）のユーザごとの公平さの間でバランスを保つ。
【００２３】
本発明の呼承認制御およびスケジューリング技術は、各ユーザに割り当てられた無線資源の正確な測定によりマルチユーザダイバーシティ利得を効果的に活用する。それらは、共に、高いシステム効率、およびフローレベルのＱｏＳ（例えば、総計の「グッドプット」、新規に着信したユーザのブロッキング率）とパケットレベルのＱｏＳ（例えばパケットキューイング遅延または損失）の間のバランスを保つ。
【００２４】
本発明による呼承認制御およびスケジューリングを具体化するシステムは、効率的なリアルタイムサービスを実現し、システムダイナミクスおよび／またはユーザの移動によって変化する、異なる負荷シナリオに対する堅牢性を維持できるので好都合である。
【００２５】
本発明の前述のおよび他の側面および利点は、以下の詳細な説明および添付の図面を参照することにより通常の当業者には明白になるであろう。
【発明を実施するための最良の形態】
【００２６】
いくつかの性能メトリックが、本発明を説明する際にここで引用される。「ユーザごとのグッドプット（ｇｏｏｄｐｕｔ）」とは、パケットが最終期限前に成功裡に配信されたリアルタイムパケットの転送率を意味している。逆に、リアルタイムパケットの損失率とは、最終期限切れまたは遅延違反により、基地局で落ちたパケットの割合を意味している。成功裡に配信されたリアルタイムパケットの平均遅延およびジッタも、関連するメトリックである。ユーザごとのグッドプット、および平均遅延およびジッタメトリックも、システム全体の性能を反映した経路の集約において、すべてのユーザに対して測定することができる。
【００２７】
他のメトリックは、セル内の無作為に分散された位置に動的に到達するユーザに対する呼ブロッキング率である。システムの観点からすると、このメトリックも、システムのパケットレベルのサービス品質（ＱｏＳ）制約の下で承認可能なユーザの最大数を反映している。複合のリアルタイムユーザの性能公平性、すなわちシステムに承認されたユーザのグッドプットがプロファイル率のそれらの期待値とどのように異なるかが、システムの堅牢性を示している。このメトリックはそれほど遅延敏感でないので非リアルタイムメトリックと呼ばれている。
【００２８】
各リアルタイムユーザは、パケットレベルでの厳格なＱｏＳ要件およびフローレベルでの名目上のプロファイル率を指定すると推測される。パケット遅延および損失のような厳格なＱｏＳメトリックが各タイムスロットでモニターされている間、プロファイル率は、比較的長期間にわたり最小または平均ストリーミングレートに一致する。セルラー環境における高いユーザ移動性によってだけでなく揮発性のチャネルフェージングおよび集中的なトラヒック／ユーザ到着のため、厳格なＱｏＳを保証することは、それが少しでも実現可能とすれば、難しい課題である。したがって、実用的なシステムは、システム効率、パケットレベルＱｏＳ、およびフローレベル性能の間のバランスを維持しようと試みている。
【００２９】
他の考察としては、例えば安定または区分上静止している期間に承認されたユーザのパケットレベルＱｏＳが、異常時にもまだ許容できるかどうかといった、異常な状態に対するシステムの堅牢性については、システムは、異なった負荷をかけるシナリオの下で堅牢であり、ユーザ移動性またはシステム（負荷）ダイナミクスの場合には予測可能な方法で低下するのが好ましい。
【００３０】
ここに使用されるシステムの概要およびＱｏＳパラメータをここで提供する。
Ｑk，s（ｔ）＝｛０，．．．，ｉ，．．．，ｎk，s（ｔ）｝：
これは、セルラー基地局のＦＩＦＯキューでの未処理パケット群である。各パケットは、ｐik，s（ｔ）によって識別される、ここで、時間ｔでの、ｉはパケット指数、ｓはクラスＩＤ、ｋは対象とする受信者のユーザＩＤである。インデックスｉ＝０は空キュー、ｉ＝１は行頭（ＨＯＬ）パケット、およびｉ＝ｎk，s（ｔ）はＦＩＦＯキューの最終パケットを指す。
Ｑk，s（ｔ）：
Ｑk，s（ｔ）のサブセットが、時間ｔでの基地局のＦＩＦＯキューから送信用に選ばれたパケットを表わす。
ｌik，s（ｔ）：
パケットｐik，s（ｔ）の長さ（例えばビット長）
Δｌik，s（ｔ）：
既に送信されたパケットｐik，s（ｔ）のそのセグメントの長さ（例えばビット長）。
ｍk，sおよびｍk：
それぞれ、ユーザｋの単一のクラスｓまたはすべてのクラスに対するリアルタイムフローの平均プロファイル率すなわち最低レート期待値（例えばｋｂｐｓで）。ｍkは、ユーザｋへのすべてのアクティブフロー中のｍk，sの合計である。
Ｄs：
セルラー基地局に着信したクラスｓからの各パケットの遅延量。
ｄik，s（ｔ）：
基地局へのその最初の着信からのパケットｐik，s（ｔ）のキューイング遅延。このパラメータは再送信遅延を含む。パケット再送信は最初の送信より優先度が高い。
βs：
これは、最終期限違反によるパケット損失（完全に着信したパケットの部分として）の上界であり、次式のように定義される。
【００３１】
【数１】
2007159131.tif 000003
【００３２】
条件ｄik，s（ｔ）?Ｄs違反の各リアルタイムパケットは、バッファから直ちに取り除かれるので紛失パケットとして数えられる。
Ｔk，s（ｔ）およびＴk（ｔ）：
Ｔk，s（ｔ）は、ユーザｋのクラスｓに対するｋｂｐｓ単位のオンライン測定平均グッドプットである。
【００３３】
【数２】
2007159131.tif 000004
【００３４】
はユーザごとのグッドプットを示している。
Ｉk（ｔ）：
時間ｔでのユーザｋに対するスケジューリングを決定する２値の指標。
Ｉk（ｔ）＝１は、ユーザｋが時間ｔでスケジュールされていることを示し、Ｉk（ｔ）＝０はスケジュールされていない場合である。
Ｂk（ｔ）：
このパラメータは、時間ｔでユーザｋに割り当てられた平均無線資源（例えば帯域幅）を表し、ここで、典型的な実施形態においては、
【００３５】
【数３】
2007159131.tif 000005
【００３６】
ｒk（ｔ）はユーザｋの瞬間チャネル速度であり、ｔlは大きな時間的尺度での平滑化窓（smoothing window）の幅である、例えばｔl＝１，０００タイムスロットである。
【００３７】
背景として上記の枠組みを用いて、本発明のいくつかの典型的な実施形態をここで詳細に説明する。
【００３８】
図１は、本発明による呼承認制御装置およびスケジューラを有する、共有チャネルダウンリンク無線通信システムの一実施例の構成を示すブロック図である。
【００３９】
図１に示すシステムは、呼承認制御（ＣＡＣ）部１１０とスケジューリング部１２０とを有する、典型的な共有チャネルダウンリンクセルラーシステム１００を概略的に示している。
【００４０】
ＣＡＣ部１１０およびスケジューリング部１２０は、例えばセルラーシステムの基地局１５０に配置されていてもよいが、例えば、特に無線ネットワーク制御装置（ＲＮＣ:Radio Network Controller）を含む移動体通信システムの他のコンポーネントと共に配置することもできる。さらに、ＣＡＣ部１１０およびスケジューリング部１２０は一緒に配置される必要はない。例えば、ＣＡＣ部１１０はＲＮＣに配置され、複数の基地局にある複数のスケジューラと共に動作してもよい。
【００４１】
ＣＡＣ部１１０およびスケジューリング部１２０の典型的な動作を以下に詳細に説明する。
【００４２】
新規ユーザ１３５（「新規ユーザｉ」として示されている）が承認を要求するときには、基地局１５０は、いつでも、承認されたユーザ｛１，…，ｋ，…，Ｋ｝群１２５にサービスを提供しているであろう。ＣＡＣ部１１０は、本発明に従って、各新規に着信したユーザ１３５を承認するかまたは拒絶するかの判断を行う。無線移動体通信の状況では、各「ユーザ」は「移動局」を介してシステム１００と交信する、また当然そのようなものとして、当該用語は交換可能に使用されることを意味している。
【００４３】
ＣＡＣブロック１１０は測定ベースの負荷推定器１１２と判定部１１４を含んでいる。スケジューリングブロック１２０は、パケット分類器１２２と、パケットバッファ１２４と、最大コスト控除（ＭＣＤ）スケジューラ１２６と、処理部１２８および１２９とを含んでいる。
【００４４】
動作中、着信パケット（すなわち承認されたユーザ１…Ｋへの伝達のためにシステムにより受け取られたダウンストリームパケットｐik，s（ｔ））は、基地局１５０で受け取られ、分類器１２２に提供される。分類器１２２は、各パケットが属するクラスｓを決定する。各ユーザｋは、１からＳまでのクラスを持つことができる。さらに、分類器１２２は、クラス特有のパラメータすなわちプロファイル率ｍs、遅延量Ｄs、およびパケット損失上限βsに着信パケットのクラス識別子をマップする。下記により詳細に説明するように、これらのクラス特有のパラメータは処理部１２８に与えられる。
【００４５】
各クラスｓからのパケットは各ユーザｋに対するパケットバッファ１２４の待ち行列に入れられる。クラスは、遅延許容範囲の大きい順にソートされるのが好ましい。典型的な実施形態において、バッファ１２４は、十分な空間を持つ先入れ先出し（ＦＩＦＯ）バッファであり、バッファオーバフローが頻繁となることを回避している。
【００４６】
バッファ１２４は、バッファされているパケットおよびスループット履歴からキューイング遅延ｄik，s（ｔ）を決定し、それらを処理部１２８に与える。処理部１２８は、分類器１２２およびバッファ１２４から得られた情報を用いて、下でより詳細に説明するように、スケジューラのインプリメンテーションに応じて、リアルタイム遅延ベースの重み関数Ｗs（ｄlx，s（ｔ））、または非リアルタイムレートベースの重み関数
【００４７】
【数４】
2007159131.tif 000006
【００４８】
／Ｗk（ｔ）
を計算する。
【００４９】
各リアルタイムフローはそのプロファイル率ｍk，sによってそのネットワーク入口で監視され、各到着パケットは、例えば、S. Blake et al., ”An Architecture for Differentiated Services, ”Internet Engineering Task Force(IETF),Request for Comments 2475(Dec.1998)に記載されているように、差別化サービス（DiflServ）コードポイントで適切にラベル付けされているものと推測される。リアルタイムフロー、例えばビデオまたはオーディオストリームは、通常ＩＰ／ＵＤＰ／ＲＴＰプロトコルにより運ばれる。例えば、ＩＴＵ  Ｇ．７２９の符号化ボイスオーバーＩＰ（ＶｏＩＰ）ソースは、概略２４ｋｂｐｓまたは１２ｋｂｐｓの生のまたは圧縮されたプロファイル率で毎秒５０パケットを生成する。
【００５０】
一方、ＩＴＵ  Ｈ．２６３の符号化ビデオソースは、概略６４ｋｂｐｓのプロファイル率で、それほど時間クリティカルでないトラヒックを毎秒２５フレーム生成する。各ＲＴパケットのエンドツーエンド遅延許容範囲は約１５０ミリセカンドから２００ミリセカンドの範囲である。最終的に、セルラーアクセスには、例えば概略４０から８０ミリセカンドの固定遅延量（Ｄs）が割り当てられてもよい。
【００５１】
各タイムスロットｔで、ＭＣＤスケジューラ１２６は、下でより詳細に説明するように、未処理のパケットのＱｏＳおよびキューイング情報、すべてのユーザのプロファイル率｛ｍk｝および瞬間チャネル速度｛ｒk（ｔ）｝、およびパケット当たりの「コスト」、
【００５２】
【数５】
2007159131.tif 000007
【００５３】
Ｃlk，s（ｔ）／Ｗk（ｔ）
またはＣlk，s（ｔ）に基づいて、承認されたユーザ｛１，．．．，Ｋ｝群１２５からパケット伝送のための「最良の」ユーザｋ*を選択する。図１に示すように、これらのパラメータは処理部１２９からＭＣＤスケジューラ１２６に提供される。共有チャネルダウンリンクは、タイムスロットｔの間最良のユーザｋ*（ｔ）に専用となる、すなわち、それは、バッファ１２４における待機パケットがそのタイムスロット中に送信されるそのユーザである。
【００５４】
単なる例証として、時分割多重（ＴＤＭ）チャネルアクセスを想定したが、本発明はいかなる特別のアクセススキームまたは特定のシステムアーキテクチャにも限定されるものではない。
【００５５】
図１に示すように、ＣＡＣブロック１１０の負荷推定器１１２は、スケジューラ１２６から瞬間的スケジューリング決定群（Ｉk（ｔ））を受け取って、それと各ユーザの瞬間チャネル速度ｒk（ｔ）とを使用し、上記式（２）に従って、パラメータＢk（ｔ）、各承認されたユーザに対するユーザ当たりの平均無線資源割り当てを決定する。負荷推定器１１２は、群｛Ｂk（ｔ）｝、承認されたユーザ（ｍk）のおよび新規ユーザ１３５（ｍi）のプロファイル率、各ユーザの瞬間チャネル速度｛ｒk（ｔ）｝、および新規ユーザの推定瞬間チャネル速度Ｅ［ｒi（ｔ）］を使用して、正規化されたシステム負荷推定を生成する。判定部１１４で正規化された負荷推定が１未満と判定されると、新規ユーザは承認され、ユーザ当たりのキューがバッファ１２４の新規ユーザに対して形成される。いったん承認されると、上述のように、新規ユーザのダウンストリームパケットはバッファ１２４の待ち行列に入れられる。判定部１１４で新規ユーザの正規化された負荷推定が１以上であると判定されると、新規ユーザは承認を拒否される。ＣＡＣブロック１１０およびそれらの動作のいくつかの典型的な実施形態を、以下に、より詳細に説明する。
【００５６】
本発明は、ＣＤＭＡ２０００高データレート（ＨＤＲ：High Data Rate）システムおよびＷＣＤＭＡ高速データパケットアクセス（ＨＳＤＰＡ：High Speed Data Packet Access）システムのような第３世代（３Ｇ）セルラーシステムを含む多くのシステムで、制限なく容易に実施することができる。
【００５７】
本発明は、例えば、移動体のセルラーユーザに対するＭＰＥＧ４またはＨ．２６３符号化ビデオストリームを含むリアルタイムサービスに特に有利であろうが、本発明はいかなる特定サービスの提供にも限定されるものではない。両システムは共用ダウンリンクチャネルを採用して、リアルタイムのサービス品質（ＱｏＳ）の異種の期待値について複数のユーザを支援している。本発明は、好都合に、異種のＱｏＳ期待値および複数のユーザの位置依存のチャネル状態の認識を用いて、そのようなチャネルにアクセスするモバイルユーザの堅牢で効率的な制御に備えている。
【００５８】
動作中の呼承認制御装置は、ほぼ瞬間的なスケジューリング決定を提供するあらゆるスケジューラと共に動作することができる。上記システムで使用される呼承認制御装置およびスケジューラのいくつかの典型的な実施形態をここで詳細に説明する。
【００５９】
チャネル依存の、測定ベースＣＡＣ
図１に示されるＫの既存のリアルタイムユーザおよび新規に着信したユーザｉを持つシステムでは、いくつかの呼承認制御アルゴリズムを導き出すために次式を使用することができる。
【００６０】
【数６】
2007159131.tif 000008
【００６１】
数式（３）において、数値「１」は正規化された全チャネル容量を表している。Ｇ（Ｋ＋１）は、下でさらに詳細に説明するような便宜主義的スケジューラで達成することができるマルチユーザダイバーシティ利得である。Ｅ［ｒk（ｔ）］およびＥ［ｒi（ｔ）］は、それぞれ、既存のユーザｋおよび新規ユーザｉに対するユーザ当たりの平均チャネル速度である。これらのパラメータはチャネルフィードバックに基づいて容易に測定することができる。
【００６２】
【数７】
2007159131.tif 000009
【００６３】
および
【００６４】
【数８】
2007159131.tif 000010
【００６５】
は、それぞれ既存のユーザｋおよび新規ユーザｉにより共有チャネルに作用されるユーザ当たりの負荷である。負荷のこのメトリックは、ＱｏＳ期待値（例えばプロファイル率）およびユーザ特定のチャネル品質（無線資源有効性）の両方を考慮している。
【００６６】
様々なＣＡＣアルゴリズムを数式（３）から導き出すことができる。例えば、上式で総合システム負荷が項Ｌ2（ｔ）、システム容量が１として定義された場合、次のＣＡＣアルゴリズムが導き出され、ここで、次式が満足されるとユーザｉは承認される。
【００６７】
【数９】
2007159131.tif 000011
【００６８】
しかしながら、このアルゴリズムは、システム負荷がユーザ当たりの負荷を「最悪」の場合として決定されるので、いくつかの応用例では慎重なものかもしれない。
【００６９】
上式（３）で総合システム負荷を項Ｌ1（ｔ）、システム容量を１と定義することにより、ここでＣＡＣ０として表わされるさらなるＣＡＣアルゴリズムが与えられる、ここで、次式が満足されるとユーザｉは承認される。
【００７０】
【数１０】
2007159131.tif 000012
【００７１】
ＣＡＣ０アルゴリズムは、マルチユーザダイバーシティ利得ではなく複数のリアルタイムユーザの多重化利得を活用するものである。
【００７２】
数式（３）から導き出すことができる他の典型的なＣＡＣアルゴリズムが次式で表される。
【００７３】
【数１１】
2007159131.tif 000013
【００７４】
ＣＡＣ１としてここに示されたこのアルゴリズムは、マルチユーザダイバーシティおよび多重化利得の両方を考慮している。しかしながら、項Ｇ（Ｋ＋１）は、ある特別な場合を除き実際に解析的に扱いにくい。例えば、Proportional Fairness（ＰＦ）スケジューリングアルゴリズムが使用された場合、およびすべてのユーザの正規化されたチャネル速度
【００７５】
【数１２】
2007159131.tif 000014
【００７６】
がＳＮＲの線形関数であり、かつ同一で、独立して分散（ＩＩＤ：Identical and Independently Distributed）している場合、
【００７７】
【数１３】
2007159131.tif 000015
【００７８】
であることが示されている。
【００７９】
【数１４】
2007159131.tif 000016
【００８０】
とセットされた場合にCAC1アルゴリズムが積極的に利用可能となる。
【００８１】
さらに典型的なＣＡＣアルゴリズムは、次のように表わすことができ、次式が満足されるとユーザｉが承認される。
【００８２】
【数１５】
2007159131.tif 000017
【００８３】
数式（７）で表わされるアルゴリズムはここではＣＡＣ２と示される。理解できるように、ＣＡＣ２は、測定されたユーザ当たりの負荷、
【００８４】
【数１６】
2007159131.tif 000018
【００８５】
のすべての既存のユーザ｛１，．．．，Ｋ｝についての合計、および新規ユーザｉに対する推定負荷、
【００８６】
【数１７】
2007159131.tif 000019
【００８７】
に基づいて合否判定を行う。
【００８８】
上述のように、Ｂk（ｔ）は、時間ｔでユーザｋに割り当てられた平均無線資源（例えば帯域幅）を表し、ここで、
【００８９】
【数１８】
2007159131.tif 000020
【００９０】
ｔlは大きな時間的尺度での平滑窓（smoothing window）の幅である、例えばｔl＝１，０００タイムスロットである。
【００９１】
Ｂk（ｔ）を測定することにより、呼承認制御装置をＣＡＣ２アルゴリズムに従って実行させることができ、スケジューラにより（無線）帯域幅資源に本来組み込まれているマルチユーザダイバーシティ利得を、もしあれば、正確に得ることができる。特に、この測定はチャネル分配に無関係で、いかなる特定のスケジューリングアルゴリズムにも限定されるものではない。対照的に、ユーザごとのグッドプットＴk（ｔ）は、軽負荷のシステムでは限定されたトラヒックの到着により束縛されるので、帯域幅資源の特徴を正確に表さない。なお、制限されたパケット到着のリアルタイムフローでは、Ｂk（ｔ）?Ｔk（ｔ）であり、ここで、等号は長期間未処理にされたままのユーザにのみ当てはまる。
【００９２】
さらに、ＣＡＣ２は、説明したように、解析的に扱いにくいであろうＧ（Ｋ）を使用しないので推定が不正確になる。
【００９３】
下に述べる試験結果は、ＣＡＣ２が、控えめな傾向があるＣＡＣ０と積極的な傾向があるＣＡＣ１の間のよい妥協点を表わすことを示している。
【００９４】
遅延ベースのスケジューリング
本発明によるシステムは、リアルタイムおよび非リアルタイム両方の様々なスケジューラで実施することができる。本発明の典型的な実施形態において使用することができるいくつかのスケジューラは、２００６年２月２７日に出願され、参照によりその全体がここに組み込まれている米国特許出願番号第１１／２７６，３８１号に記載されている。
【００９５】
非リアルタイム（ＮＲＴ）データサービスのスケジューリングでは、資源公平性および総計のシステムスループットが通常第一の関心事である。ｍａｘＣ／ＩおよびProportional Fairness（ＰＦ）のような既存のＮＲＴスケジューリングアルゴリズムは、未処理データが無限という仮定の下でのチャネル状態開発という点に焦点を当てている。しかしながら、それらのアルゴリズムは、リアルタイムパケット遅延または損失を保証することができないので、結果的にグッドプットが悪くなる。これは、該アルゴリズムが未処理データについての動的なトラヒックを無視していること、および該アルゴリズムが未処理データの中のリアルタイムパケット遅延について十分な考慮を払っていないことによるものである。資源公平性はリアルタイムサービスでは二次的な問題になる。
【００９６】
modified largest-weighted delay first（ＭＬＷＤＦ）および指数関数的規則（Ｅｘｐ−Ｒｕｌｅ）スケジューラのような第３世代（およびそれ以降の）セルラーシステム用の既存のリアルタイムスケジューラは、リアルタイムパケット遅延保証をマルチユーザダイバーシティ利得と有効に統合している。パケット損失低減に該スケジューラの性能が与えられると、それらのグッドプットおよび堅牢性は、資源公平性に対する該スケジューラの根本的な機構により制限される。ここに説明しているスケジューラは、従来と同等の、または、より優れたリアルタイムサービスを提供し、システム負荷シナリオの広範囲において堅牢である。
【００９７】
リアルタイムフローのパケット到着は規則性がなく、突発的で、集中的である。優れたリアルタイムスケジューラというのは、未処理のパケットに規則的で適時のサービスを提供するはずである、なぜなら、それらのパケットの過度の遅延が最終期限違反を引き起こすのでパケットが失われ、不十分な未処理データおよび低いグッドプットをもたらす結果になるからである。
【００９８】
ダウンリンクスケジューラは、マルチユーザダイバーシティ利得の有効活用により高いシステム効率を達成することができる。あいにく、いかなるユーザに対しても、チャネル品質のピークは、未処理またはキューイング遅延のピークとほとんど一致しない。したがって、リアルタイムスケジューラは、良好な受信を持つそれらのユーザと時間クリティカルなフローを持つユーザ間のバランスを検討するのが好ましい。各タイムスロットで、スケジューラは、最も期限切れが迫っているパケットを最大のチャネル容量に送信すべきであり、それにより、システムから最大コスト控除（ＭＣＤ）を生み出すことができる。言いかえれば、ＭＣＤスケジューラは各タイムスロットで下記の目標を追求する。
【００９９】
最大｛発送パケットの遅延派生のコスト｝・・・（８）
システムコスト関数は、すべての未処理のパケットの総コストとして定義することができ、次のように表わすことができる。
【０１００】
【数１９】
2007159131.tif 000021
【０１０１】
ここで、Ｃik、s（ｔ）は、時間ｔでの各キューパケットｐk、s（ｔ）のパケット当たりのコストを示している。
【０１０２】
成功裡に配信されたリアルタイムパケットとは、パケットの最終期限が終了する前に、パケットが対象とする受信者に送信されるその全内容を持っているパケットである。より大きなパケットまたは部分的に配信されたパケットを遅らせるコストは、より小さなパケットまたはまだ送信されていないパケットを遅らせるコストよりも大きい。したがって、パケット当たりのコスト関数Ｃik，s（ｔ）は、全体のパケットの大きさｌik，s（ｔ）、任意の送信されたパケットのセグメントの大きさΔｌik，s（ｔ）、およびキューイング遅延ｄik、s（ｔ）の関数であるはずである。パケット当たりのコスト関数Ｃik、s（ｔ）は、ｌik，s（ｔ）およびΔｌik，s（ｔ）と共に単調に増加するはずである。Ｃik，s（ｔ）は、また、ｄik，s（ｔ）と共に単調に増加するはずであり、ｄik，s（ｔ）が遅延量Ｄsに近づくにつれて、すなわち、パケットが遅延違反によりキューから落とされるとき、その最大に近づく。さらに、Ｃik，s（ｔ）は、それらの遅延に従って同一クラスｓのパケットを差別化するはずであり、クラスに応じてもパケットを差別化するはずである。
【０１０３】
前述の特徴を考慮に入れると、パケット当たりの適切なコスト関数は、次のように定義することができる。
【０１０４】
【数２０】
2007159131.tif 000022
【０１０５】
ここで、γ?０は、既に送信されたセグメントΔｌik，s（ｔ）のパケットセグメントの長さをパケット当たりのコストに重み付けする係数であり、Ｗs（ｄik，s（ｔ））はビット当たりの単位コストである。ビット当たりの単位コスト、Ｗs（ｄik，s（ｔ））は、遅延の非減少重み関数ｄik，s（ｔ）で、各クラスｓに特有である。このパラメータについて下でより詳細に説明する。
【０１０６】
説明しているように、本発明は様々なスケジューラを考慮している。第１のそのようなスケジューラは、リアルタイムの、遅延ベースの重み関数を持つ最大コスト控除（ｒｔ−ＭＣＤ）スケジューラである。第２のスケジューラは、レートベースの重み関数を持つ非リアルタイムＭＣＤ（ｎｒｔ−ＭＣＤ）スケジューラである。これらの各々についてここでより詳細に説明する。
【０１０７】
ｒｔ−ＭＣＤスケジューラは、タイムスロットｔで、まず承認されたユーザ｛１，．．．，ｋ，．．．，Ｋ｝群を走査し、｛１，．．．，ｘ，．．．Ｘ｝とて示される未処理のリアルタイムユーザ群を捜し出す。未処理のユーザがいない、例えば、未処理データが空であるまたはシステムが軽負荷であるときのような場合、スケジューラは、あたかもユーザがみな無限の未処理データを持ち、パケットがすべて等しい重みを持つかのように動作する。
【０１０８】
しかし、未処理のユーザがいる場合、スケジューラは、コスト削減へのそれらの貢献により以下のようにしてユーザｘ*（ｔ）を見つける。
【０１０９】
【数２１】
2007159131.tif 000023
【０１１０】
次の条件、
【０１１１】
【数２２】
2007159131.tif 000024
【０１１２】
および
【０１１３】
【数２３】
2007159131.tif 000025
【０１１４】
を仮定している、ここで、Ｑx，s（ｔ）は、未処理のパケットのキュー（「（ｘ，ｓ）キュー」とも呼ばれる）から送信のために選ばれたパケットＱx，s（ｔ）のサブセットである。
【０１１５】
数式（１１）に従ってｘ*（ｔ）を決定するための典型的な手順は、２つの最適化ステップを必要とする。各ユーザｘに対して、スケジューラは、まず未処理パケット群Ｑx，s（ｔ）、各ユーザｘのＱx，s（ｔ），（∀s）を走査することにより、ユーザ内またはクラス間コスト控除を推進し、瞬間チャネル速度ｒx（ｔ）により送信可能な、最も「時間クリティカルな」サブセットＱx，s（ｔ）を決定する、すなわち、スケジューラは混合クラスから次式のようにパケットを選ぶ。
【０１１６】
【数２４】
2007159131.tif 000026
【０１１７】
パケットのセグメント化が可能でない、すなわちΔｌix，s（ｔ）＝０、Ｃix，s（ｔ）＝Ｗs（ｄix，s（ｔ））ｌix，s（ｔ）の場合には、数式（１２）のパケット選択の問題は、難しいＮＰナップサック問題（NP-hard Knapsack problem）になる。この問題は近似法で解を得ることができ、スケジューラは、ユーザｘのすべてのクラス／キューからのパケットがＷs（ｄix，s（ｔ））の減少値に従って並べられている、ソート済みのリストの先頭から始まるパケットを選択する。該選択は、リストが空になるか、または容量が選択されたパケットで満たされるまで続く。近似法の複雑さはＯ(ＮlogＮ）となり、ここで、Ｎはユーザｘの待ちパケットの合計数である。
【０１１８】
ただし、パケットのセグメント化が可能な場合、スケジューラは、まず、減少
【０１１９】
【数２５】
2007159131.tif 000027
【０１２０】
の単一のリスト中のすべてのリアルタイムクラスからパケットを分類する。スケジューラは、リストの先頭から開始して、キューが空になるか、またはチャネル容量が満たされる（ｒx（ｔ）Δｔビットで）まで、パケットまたはセグメントを選択する。なお、最後に選択された「パケット」は単にセグメントかもしれない、すなわち、パケットは部分的に送信されることになっていることに留意されたい。
【０１２１】
各ユーザｘの選択されたパケット｛Ｑx，s（ｔ），（∀s）｝が与えらると、スケジューラは次に進み、前のユーザ内パケット選択に基づいて、最大のコスト控除を提供する可能性のある最適なユーザｘ*（ｔ）を見つけることによりユーザ間コスト控除を最大にする。
【０１２２】
【数２６】
2007159131.tif 000028
【０１２３】
スケジューリング決定は、他のすべてのｘに対してＩx*（ｔ）＝１、Ｉx（ｔ）＝０である。
【０１２４】
説明したようなｒｔ−ＭＣＤスケジューラで、線形のまたは指数関数的な遅延ベースの重み関数Ｗs（ｄix，s（ｔ））を使用して、優れたＱｏＳ性能を実現することができる。線形の重み関数、すなわち、
【０１２５】
【数２７】
2007159131.tif 000029
【０１２６】
は、線形のパケット当たりのコスト関数を生み出す。なお、遅延は、比較目的用のクラス無関係な重みを得るためにクラス特有の遅延量Ｄsで正規化される。
【０１２７】
【数２８】
2007159131.tif 000030
【０１２８】
線形の遅延ベースの重み関数を持ったｒｔ−ＭＣＤスケジューラが、ｒｔ−ＭＣＤ線形スケジューラとしてここに示される。
【０１２９】
指数関数的な重み関数、すなわちＷs（ｄ）＝ａｅbd/Dsは、ここで、ａおよびｂは一定でもまたは時間に変化してもよいが、パケットがますます「時間クリティカルである」、すなわちｄ→Ｄsの場合には、単位遅延コストのいつまでも成長していくわずかな増加を反映している。典型的な実施形態では、ａ＝ｂ＝１である。
【０１３０】
指数関数的な遅延ベースの重み関数を持ったｒｔ−ＭＣＤスケジューラが、ｒｔ−ＭＣＤ−ｅｘｐスケジューラとしてここに示される。
【０１３１】
特別な事例として、
【０１３２】
【数２９】
2007159131.tif 000031
【０１３３】
、および
【０１３４】
【数３０】
2007159131.tif 000032
【０１３５】
の場合、ｒｔ−ＭＣＤ−ｅｘｐスケジューラはＥｘｐ−Ｒｕｌｅスケジューラになる。S. Shakkottai and A. Stolyar, ”Scheduling Algorithms for Mixture of Real-time and NonReal-time Data in HDR”,in Proceedings 17th Int. Teletraffic Congress（ＩＴＣ１７）（Ｓｅｐｔ．２００１）を参照されたい。なお、ＥＸＰ−Ｒｕｌｅにおいて、ｄは行頭の（ＨＯＬ）パケット遅延を指す、すなわち、１つのキュー内のパケットはすべて同一の遅延であると推測され、各ユーザｋは正確に１つのクラスのトラヒックを持っている。
【０１３６】
説明したように、本発明で熟考した第２の形態のスケジューラは、レートベースの重み関数を持つ非リアルタイムＭＣＤ（ｎｒｔ−ＭＣＤ）スケジューラである。リアルタイムユーザは、
【０１３７】
【数３１】
2007159131.tif 000033
【０１３８】
で表わされるそれらのプロファイル率期待値と比較された、それらの長期的な資源割り当てにも関心を持つかもしれない、ここでＢk（ｔ）は上述のように数式（２）に従って決定される。システムの観点からすると、このメトリックは性能公平性、非リアルタイムメトリックを反映している。リアルタイムスケジューラは、きめ細かい、短時間の遅延を確保するために長期的なシステム効率を犠牲にすることで、より長期間にわたる不十分な公平性を提供することができる。時間クリティカルでないリアルタイムユーザ（すなわち、それらの未処理のパケットおよび現在の遅延が遅延限界からはるかに遠い）を過度の未処理のパケットおよび効率損失から保護するために、レートベースの重み関数／Ｗk（ｔ）を持つＭＣＤスケジューラが、本発明のシステムにおいて使用できる。そのようなｎｒｔ−ＭＣＤスケジューラは以下のように実施することができる。
【０１３９】
【数３２】
2007159131.tif 000034
【０１４０】
【数３３】
2007159131.tif 000035
【０１４１】
、および
【０１４２】
【数３４】
2007159131.tif 000036
【０１４３】
という条件を仮定している。
【０１４４】
ｎｒｔ−ＭＣＤスケジューラは上述のｒｔ−ＭＣＤの場合と同様の手順で行うことができる。各ユーザｘに対するユーザ内またはクラス間コスト控除が、以前のように、最も「時間クリティカルな」パケットサブセットＱx，s（ｔ）を見つける一方、ユーザ間コスト控除は、次式のように最適なユーザｋ*（ｔ）を捜し出す。
【０１４５】
【数３５】
2007159131.tif 000037
【０１４６】
なお、このｎｒｔ−ＭＣＤスケジューラでは、Ｗs（ｄ）に対する単純で線形な関数がパケット当たりのコスト関数Ｃik，s（ｔ）の中で仮定されていたことに留意されたい。
【０１４７】
優れたＱｏＳ性能が、線形関数
【０１４８】
【数３６】
2007159131.tif 000038
【０１４９】
のようないくつかの異なった重み関数で実現することができる。そのような重み関数を持ったｎｒｔ−ＭＣＤスケジューラが、ｎｒｔ−ＭＣＤ線形スケジューラとしてここに示される。無限の未処理データが与えられると、そのようなスケジューラは、重みがリアルタイムパケット遅延を掛けたユーザ特定のプロファイル率となる、ＰＦアルゴリズムの重み付けされたバージョンと等価になる。
【０１５０】
性能評価
従来方式を超える、本発明により提供された改良を十分に理解するために、フローおよびパケットレベルの両方で本発明のＣＡＣとスケジューリングアルゴリズムを結合させた性能、例えばユーザ収容能力およびダウンリンクスループットに対して達成されたシステム容量、および承認されたユーザに対するパケット遅延／損失メトリックを評価することは有用である。
【０１５１】
本発明の典型的な実施性能の例証的評価として、Δｔ＝１．６６７ミリセカンドのスロットサイズ、すなわち６００Ｈｚのスケジューリング周波数、および１．２５ＭＨｚのチャネル帯域幅を持つ、ＣＤＭＡ／ＨＤＲダウンリンクチャネル構造がモデル化された。平均チャネル分配は、各チャネルが４ｄＢの標準偏差を持つ高速レイリーフェージングおよび対数正規のシャドーフェージングを持ちながら、平均の支援可能レートが１５３ｋｂｐｓから３．７６７ｍｂｐｓの範囲に広がる、ＣＤＭＡ／ＨＤＲのＣＤＦ関数に従うと仮定された。普遍性を失うことなく説明を簡単にするために、モデルは、基地局でＨ．２６３のリアルタイムビデオストリーミング（Ｓ＝１）ユーザのみを仮定し、各ユーザがたった１つのフローを持つと仮定している。各リアルタイムフローは、ｍk＝６４ｋｂｐｓのプロファイル率のベルヌーイ（Ｂｅｒｎｏｕｌｌｉ）プロセスとしてモデル化された。ＨＤＲシステムで１２８バイトのパケット長が与えられると、平均パケット到着間時間は約１６ミリセカンドになる。
【０１５２】
さらに、８０ミリセカンドの遅延量（Ｄs）を仮定し、同一ユーザｋのすべての未処理のパケットに対するコスト定義である数式（１０）において、ＨＯＬパケット遅延ｄik，sを使用した。この単純化は、実際には性能が大きく異なることなく、キュー管理経費を低減する。
【０１５３】
該モデルは、動的なユーザ集団を持ち、ユーザが一定の割合で到着、出発し、かつ各ユーザが４０秒の制限された寿命を持つ単一のセルで、ＣＡＣが行われると仮定している。さらに、平均チャネルまたは帯域幅割り当ては、１，０００タイムスロットの時間窓ｔlで測定される。
【０１５４】
比較のために、ＣＡＣ０、ＣＡＣ１、およびＣＡＣ２呼承認制御装置と、Ｅｘｐ−Ｒｕｌｅ、ｒｔ−ＭＣＤ、およびｎｒｔ−ＭＣＤ線形スケジューラの様々なシステム組み合わせがモデル化された。ｒｔ−ＭＣＤスケジューラを持つシステム組み合わせがｎｒｔ−ＭＣＤ線形スケジューラを持つ組み合わせと類似した動作をすることが分かった。
【０１５５】
図２は、ＣＡＣ０、ＣＡＣ１、またはＣＡＣ２呼承認制御装置と、Ｅｘｐ−Ｒｕｌｅまたはｎｒｔ−ＭＣＤ線形スケジューラとのすべての組み合わせに対する総計のパケット損失率を示している。総計のパケット損失率はグッドプットを反映している。図２に示すように、ＣＡＣ０呼承認との２つの組み合わせには０または０に近いパケット損失が得られる。しかし、そのようなシステムは、該システムがユーザをほとんど受け付けないので、グッドプットが低い。したがって、ＣＡＣ０の使用は、完全または完全に近いパケットレベルＱｏＳを提供するが一方、それは、システム効率または資源活用の低下を引き起こす。さらに、図２に示されるＣＡＣ０／Ｅｘｐ−ＲｕｌｅとＣＡＣ０／ｎｒｔ−ＭＣＤ線形の２つの曲線の密接な重複は、そのような性能がスケジューラに無関係であることを示している。これにより、上に説明した期待値は、説明した３つのＣＡＣアルゴリズムの中でＣＡＣ０が最も控えめであることが確認できる。
【０１５６】
図２から、ＣＡＣ１／Ｅｘｐ−ＲｕｌｅおよびＣＡＣ１／ｎｒｔ−ＭＣＤ線形の２つの曲線の高いパケット損失率で示されるように、ＣＡＣ１が３つのＣＡＣアルゴリズムの中で最も積極的であることも確認される。３つのＣＡＣアルゴリズムのうち、ＣＡＣ１が最も高い総計のグッドプット（図示されない）を提供するが、しかしそれは、図２で示されるようにＱｏＳを犠牲にしたものである。
【０１５７】
ＣＡＣ２は、高いグッドプットと低パケット損失の間の優れた妥協案を提供する。さらに、図２に示すように、ＣＡＣ２を実施するシステムのパケット損失率は、Ｅｘｐ−Ｒｕｌｅスケジューラとｎｒｔ−ＭＣＤ線形スケジューラによる２つのインプリメンテーション間で大きく変わらない。
【０１５８】
図３は、各々が様々なシステム構成に対して８０ミリセカンドの遅延量を持つ、成功裡に送信されたパケットの平均遅延を示している。概して言えば、スケジューラにかかわらず、ＣＡＣ０およびＣＡＣ１は、それぞれ、それらが余りにも控えめおよび積極的なために最低および最高の平均パケット遅延を生み出している。上で説明したように、ＣＡＣ２はその中間のある点の動作を行う。図３は、ＣＡＣアルゴリズムに関係なく、ｎｒｔ−ＭＣＤ線形スケジューラを持つシステムが、一般に、Ｅｘｐ−Ｒｕｌｅスケジューラを持つシステムよりも小さい遅延を提供することも示している。これは上に説明した期待値と一致している。
【０１５９】
図４は、ＣＡＣおよびスケジューリングアルゴリズムの異なった組み合わせの下で承認された平均ユーザ数を示している。承認されたユーザ数は、一般にユーザブロッキング率の逆となるシステム容量を示す。
【０１６０】
図４に示すように、３つのＣＡＣアルゴリズム中で、ＣＡＣ１が最多のユーザ数を承認し（しかしより高いパケット遅延と損失を持つ）、ＣＡＣ０が最小のユーザ数を承認する（したがって、優れたＱｏＳだが不十分なグッドプットを享受する）。対照的に、ＣＡＣ２は、パケットレベルＱｏＳ（例えば遅延および損失）およびシステム効率（例えばグッドプット）の両方の点から、本質的にシステムで支援可能なユーザの「正しい」数を承認する。
【０１６１】
図４に示すように、ＣＡＣ０またはＣＡＣ１呼承認を持ったシステムに対する承認されたユーザの平均数は、実際上スケジューラに依存しない。ＣＡＣ２／Ｅｘｐ−ＲｕｌｅシステムはＣＡＣ２／ｎｒｔ−ＭＣＤ線形システムよりさらに数人のユーザを収容することができる。
【０１６２】
本発明の代表的な図面および特定の実施形態を説明し例示してきたが、本発明の範囲は、説明した特定の実施形態に限定されないことを理解されたい。したがって、実施形態は限定的ではなく例示的なものであると見なすべきであり、当業者であれば、以下の請求の範囲に記載される本発明の範囲、ならびにその構造的および機能的同等物から逸脱することなく、これら実施形態の変形例を作成できることを理解されるべきであろう。
【図面の簡単な説明】
【０１６３】
【図１】本発明による呼承認制御装置およびスケジューラを有する、共有チャネルダウンリンク無線通信システムの典型的な実施形態を概略的に示している。
【図２】本発明によるシステムの様々な実施形態のパケット損失性能を示すグラフである。
【図３】本発明によるシステムの様々な実施形態のパケット遅延性能を示すグラフである。
【図４】本発明によるシステムの様々な実施形態の承認ユーザ数の性能を示すグラフである。
【符号の説明】
【０１６４】
１００    システム
１１２    負荷推定器
１１４    判定部
１２２    分類器
１２６    ＭＣＤスケジューラ
１２５    ユーザ
１２８    処理部
１２９    処理部
１３５    新規ユーザ
１５０    基地局
【図１】
2007159131.tif 000041
【図２】
2007159131.tif 000042
【図３】
2007159131.tif 000043
【図４】
2007159131.tif 000044