(57)【要約】通信システム100 、120 で送信をスケジュールするための一般化されたスケジューラ400 の方法および装置である。スケジューラはチャンネル状態と公正基準の優先順位関数により規定される。一般化されたスケジューラはチャンネル状態メトリックとユーザ公正メトリックの種々の組合わせを適用するように構成されている。スケジューラはユーザのクラスを弁別し、クラス毎の個々の処理を可能にする。１実施形態では、システム制御装置は複数のユーザ1202のそれぞれに対する転送優先順位パラメータＤＰＰを受信し、各ＤＰＰを対応する共通のマップされた優先順位パラメータＭＰＰ1206へマップする。動作点は1208で決定され、各ユーザに対する対応するＭＰＰ値は送信をスケジュールするために1210で適用される。【選択図】図７
2004533750.tif 000002
【特許請求の範囲】
【請求項１】
無線通信システムにおけるスケジュール方法において、
複数の移動体ユーザから順方向リンク通信に対応するチャンネル状態インジケータを受信し、
複数の移動体ユーザに対するスループットの関数として公正インジケータを決定し、
チャンネル状態インジケータと公正インジケータの関数である複数の移動体ユーザに対する送信スケジュールを決定するステップを含んでいるスケジュール方法。
【請求項２】
送信スケジュールの決定はさらに、
チャンネル状態インジケータと公正インジケータの関数として複数の移動局に対するスケジュールインジケータを計算し、
スケジュールインジケータに基づいて次に送信するための複数の移動局の少なくとも１つを選択するステップを含んでいる請求項１記載の方法。
【請求項３】
送信スケジュールの決定はさらに、
ｉ＝１，…Ｎとして、Ａi （ｔ）＝Ｂ（ｔ）／Ｂ ＡＶＥi （ｔ）としてチャンネル状態インジケータの関数を計算し、
ここでＡi （ｔ）はｉ番目の移動局に対するチャンネル状態インジケータの関数であり、Ｂi （ｔ）は時間ｔにおけるｉ番目の移動局からのチャンネル状態インジケータであり、Ｂ ＡＶＥi （ｔ）は最近ｉ番目の移動局から受信されたチャンネル状態インジケータの平均値であり、Ｎは複数の移動局の移動局の総数である請求項２記載の方法。
【請求項４】
チャンネル状態インジケータはデータレート制御リクエストであり、チャンネル状態インジケータの平均値はｉ番目の移動局からの濾波されたデータレート制御リクエストである請求項３記載の方法。
【請求項５】
チャンネル状態インジケータの関数の計算は、
Ｂ ＡＶＥi （ｔ＋１）＝Ｂ ＡＶＥi （ｔ）［１−（１／Ｔc ）］＋Ｂi （ｔ）［１／Ｔc ］として時間ｔにおけるｉ番目の移動局からの濾波されたデータレート制御リクエストを計算し、
ここでＴc は公正時間期間である請求項４記載の方法。
【請求項６】
チャンネル状態インジケータの関数の計算はさらに、
それぞれ最近受信されたデータレート制御リクエストに加重を割当てるステップを含んでいる請求項５記載の方法。
【請求項７】
スケジュールインジケータの計算は、
複数の移動局のそれぞれに対して、対応するチャンネル状態インジケータと対応する公正インジケータとの比の決定を含んでいる請求項２記載の方法。
【請求項８】
各移動局で、公正インジケータは移動局が公正時間期間中にサービスされた時間の割合である請求項１記載の方法。
【請求項９】
コンピュータの実行可能な命令を含んでいるコンピュータの読取り可能な媒体で実行されるプログラムにおいて、
複数の移動体ユーザから受信されたチャンネル状態インジケータを処理するための第１の命令のセットと、
複数の移動体ユーザに対するスループットの関数として公正インジケータを決定する第２の命令のセットと、
チャンネル状態インジケータと公正インジケータの関数として複数のユーザに対する送信スケジュールを決定する第３の命令のセットとを含んでいるプログラム。
【請求項１０】
チャンネル状態インジケータと公正インジケータの関数は公正インジケータによりチャンネル状態インジケータを平衡する請求項９記載のプログラム。
【請求項１１】
無線通信システムにおけるアクセスネットワークにおいて、
複数の移動体ユーザから順方向リンク通信に対応するチャンネル状態インジケータを受信する受信手段と、
複数の移動体ユーザに対するスループットの関数として公正インジケータを決定する手段と、
チャンネル状態インジケータと公正インジケータの関数である複数の移動体ユーザに対する送信スケジュールを決定する手段を具備しているアクセスネットワーク。
【請求項１２】
無線通信システムにおけるデータ送信をスケジュールする方法において、
それぞれの複数の移動体ユーザから転送優先順位のパラメータ値を受信し、
任意の転送優先順位のパラメータが異なるタイプであるならば、各転送優先順位のパラメータをマップされた優先順位のパラメータへマップし、
複数の移動体ユーザのマップされた優先順位パラメータに基づいて動作点を決定するスケジュール方法。
【請求項１３】
さらに、各複数の移動体ユーザのそれぞれに対して、動作点に対応するマップされた優先順位パラメータ値を適用し、
マップされた優先順位パラメータ値に対応する転送優先順位パラメータを決定する請求項１２記載の方法。
【請求項１４】
第１の転送優先順位パラメータは所望の時間割当てである請求項１３記載の方法。
【請求項１５】
第２の転送優先順位パラメータは所望のスループットである請求項１３記載の方法。
【請求項１６】
第３の転送優先順位パラメータは所望の遅延である請求項１３記載の方法。
【請求項１７】
無線通信システムのシステム制御装置において、
複数の移動体ユーザのそれぞれから転送優先順位パラメータを受信する手段と、
各転送優先順位パラメータをマップされた優先順位パラメータへマップする手段と、
複数の移動体ユーザのマップされた優先順位パラメータに基づいて動作点を決定する手段とを具備しているシステム制御装置。
【請求項１８】
無線通信システムにおける装置において、
処理素子と、
処理素子に結合されているメモリ記憶装置とを具備し、メモリ記憶装置はコンピュータの読取り可能な命令を記憶するように構成され、、コンピュータの読取り可能な命令は、
複数の移動体ユーザのそれぞれから転送優先順位パラメータを受信し、
各転送優先順位パラメータをマップされた優先順位パラメータへマップし、
複数の移動体ユーザのそれぞれのマップされた優先順位パラメータに基づいて動作点を決定することを実行するように構成されている装置。
【請求項１９】
コンピュータの読取り可能な命令はさらに、
動作点を各複数の移動体ユーザに適用するように構成され、
ここで動作点は複数の移動体ユーザのそれぞれに対応するマップされた優先順位パラメータ値を決定する請求項１８記載の装置。
【請求項２０】
コンピュータの読取り可能な命令はさらに、
マップされた優先順位パラメータ値を使用して、動作点にしたがって複数の移動体ユーザをスケジュールするように構成されている請求項１９記載の装置。
【請求項２１】
複数の受信機への送信をスケジュールするように構成されているチャンネルスケジュール装置と、
複数の受信機からの複数の受信された転送優先順位パラメータを適用するように構成されている公正セレクタとを具備している無線インフラストラクチャ装置。
【請求項２２】
チャンネルスケジュール装置は複数の受信機から受信された複数の転送優先順位パラメータとチャンネル状態インジケータに基づいて送信をスケジュールする請求項２１記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的に通信に関し、特に通信システムで送信をスケジュールする方法および装置に関する。
【背景技術】
【０００２】
本発明は本発明の出願人に譲渡され、ここで参考文献としている2001年４月12日出願の米国特許出願第60/283,885号明細書の優先権を主張している。
【０００３】
本発明は2001年２月27日出願の米国特許出願第09/796,583号明細書（発明の名称“SYSTEM FOR ALLOCATING RESOURCES IN A COMMUNICATION SYSTEM ”）に関する。
【０００４】
通信システム、特に無線システムは種々のユーザ間でのリソースの効率的な割当てを目的に設計されている。無線システムは特に価格を最小にしながら全ての加入者の要求を満たすのに十分なリソースを提供することを目的としている。種々のスケジュールアルゴリズムが開発され、それぞれ予め定められたシステム基準に基づいている。
【０００５】
コード分割多元アクセス、ＣＤＭＡ方式を使用する無線通信システムでは、１つのスケジュール方法は時間多重化を基礎として指定された時間間隔で各加入者装置を全てのコードチャンネルに割当てる。基地局ＢＳ等の中央通信ノードは加入者との専門の通信を可能にするために加入者に関連する特別な搬送波周波数またはチャンネルコードを構成する。ＴＤＭＡ方式は物理的な接触リレイ交換またはパケット交換を使用して陸線システムで構成されてもよい。ＣＤＭＡシステムは（１）ここではＩＳ−９５標準と呼ばれる“TIA/EIA/IS-95-B Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System ”、（２）ここでは３ＧＰＰと呼ぶ“3rd Generation Partnership Project”という名称の組合により提出され、ここではＷ−ＣＤＭＡ標準と呼ばれる文書番号3G TS 25.211、3G TS 25.212、3G TS 25.213、3G TS 25.214、3G TS 25.302を含む１組の文書で実施されている標準、（３）ここでは３ＧＰＰ２と呼ばれる“3rd Generation Partnership Project2 ”という名称の組合により提出される標準と、公式にＩＳ−２０００ＭＣと呼ばれるｃｄｍａ２０００とここで呼ばれているＴＲ−４５．５、または（４）幾つかの他の無線標準等の１以上の標準をサポートするように設計されている。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
通信システム、特に無線システムでは、ユーザは典型的にクラスに割当てられ、各クラスは関連するシステム性能基準を有する。例えば各クラスは公正基準に関して異なって扱われ、１クラスの各ユーザは同様に扱われる。クラスは各クラスの優先順位にしたがって扱われる。１システムでは、ユーザはサービスプランのように、システムで使用されるサービスにしたがって分類される。幾つかのクラスが１つの通信システム内に存在する。
【０００７】
したがって、アプリケーションにより多数のクラスのユーザに対する通信システムの送信をスケジュールする方法および装置が必要とされている。さらに、種々の異なるスケジュール優先順位を適合するスケジュール方法および装置が必要とされている。
【課題を解決するための手段】
【０００８】
ここで開示されている実施形態は無線通信システムにおけるデータ送信をスケジュールする手段を提供することにより前述の要求を解決する。一般化されたスケジューラは多数の移動局のスケジュールを可能にし、各移動局は異なる転送優先順位パラメータを有する。転送の優先順位パラメータは所望のデータ送信転送速度に影響を与えるために使用されるパラメータを規定する。例えば転送優先順位パラメータは所望のスループット、所望の時間割当て、所望の時間遅延等である。転送優先順位パラメータ値はそれぞれマップされた優先順位パラメータと呼ばれる共通のスケールへマップされる。動作点がその後選択され、各移動体ユーザに対する対応するマップされた優先順位パラメータ値が抽出される。一般化されたスケジューラはその後、共通のマップされた優先順位パラメータ値を使用して移動体ユーザをスケジュールする。換言すると、各ユーザは対応する転送優先順位パラメータ範囲内で同一の割合を実現するようにスケジュールされる。
【０００９】
１特徴によると、無線通信システムにおけるスケジュール方法は複数の移動体ユーザから順方向リンク通信に対応するチャンネル状態インジケータを受信し、複数の移動体ユーザに対するスループットの関数として公正インジケータを決定し、チャンネル状態インジケータと公正インジケータの関数である複数の移動体ユーザに対する送信スケジュールを決定するステップを含んでいる。
【００１０】
別の特徴では、コンピュータの実行可能な命令を含んでいるコンピュータの読取り可能な媒体で実行されるプログラムは複数の移動体ユーザから受信されたチャンネル状態インジケータを処理するための第１の命令のセットと、複数の移動体ユーザに対するスループットの関数として公正インジケータを決定する第２の命令のセットと、チャンネル状態インジケータと公正インジケータの関数として複数のユーザの送信スケジュールを決定する第３の命令のセットとを含んでいる。
【００１１】
さらに別の特徴では、複数の遠隔局の１つの遠隔局と、無線通信システムの基地局との間でデータを送信する方法は、基地局で１つの遠隔局により送信される情報を受信し、その情報に基づいて１つの遠隔局に特別な少なくとも１つのサービスパラメータのグレードを調節するステップを含んでいる。
【００１２】
さらに別の特徴では、無線通信システムにおけるデータ送信をスケジュールする方法は、複数の移動体ユーザのそれぞれから転送優先順位のパラメータ値を受信し、任意の転送優先順位のパラメータ値が異なるタイプであるならば、各転送優先順位のパラメータをマップされた優先順位のパラメータへマップし、複数の移動体ユーザのマップされた優先順位パラメータに基づいて動作点を決定するステップを含んでいる。
【００１３】
別の特徴によると、無線通信システムにおける装置は、処理素子と、処理素子に結合されているメモリ記憶装置とを具備し、メモリ記憶装置はコンピュータの読取り可能な命令を記憶するように構成され、コンピュータの読取り可能な命令は各複数の移動体ユーザから転送優先順位パラメータを受信し、各転送優先順位パラメータをマップされた優先順位パラメータへマップし、各複数の移動体ユーザのマップされた優先順位パラメータに基づいて動作点を決定することを実行する。
【発明を実施するための最良の形態】
【００１４】
ここで説明した特徴と利点は添付図面を伴った以下の詳細な説明からさらに明白になるであろう。同一の参照符号は全体を通して対応して同一である。
現在、通信システムは種々の応用をサポートするために必要とされている。１つのこのような通信システムは以後ＩＳ−９５と呼ぶ“TIA/EIA-95 Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System”とその後継に準じた符号分割多重化アクセス（ＣＤＭＡ）システムである。ＣＤＭＡシステムは地上リンクによってユーザ間の音声およびデータ通信を可能にする。多数のアクセス通信システムにおけるＣＤＭＡ技術の使用は米国特許第4,901,307 号明細書（発明の名称“SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS ”）と、米国特許第5,103,459 号明細書（発明の名称“SYSTEM AND METHOD FOR GENERATING WAVEFORMS IN A CDMA CELLULAR TELEPHONE SYSTEM”）に開示されており、この両者は本発明の出願人に譲渡され、ここで参考文献とされている。
【００１５】
ＣＤＭＡシステムでは、ユーザ間の通信は１以上の基地局を介して行われる。無線通信システムでは順方向リンクは信号が基地局から加入者局へ伝播するチャンネルを意味し、逆方向リンクは信号が加入者局から基地局へ伝播するチャンネルを意味する。逆方向リンクで基地局へデータを送信することにより、１つの加入者局の第１のユーザは第２の加入者局の第２のユーザと通信する。基地局は第１の加入車局からデータを受信し、そのデータを第２の加入者局をサービスする基地局へ伝送する。加入者局の位置に応じて、両者は単一の基地局または多数の基地局によりサービスされる。任意の場合において、第２の加入者局をサービスする基地局は順方向リンクでデータを送信する。第２の加入者局と通信する代わりに、加入者局はまたサービスする基地局との接続により地上インターネットと通信してもよい。ＩＳ−９５に準じるような無線通信では、順方向リンクおよび逆方向リンク信号は別々の周波数帯域内で送信される。
【００１６】
図１のＡは複数のユーザをサポートし、本発明の少なくとも幾つかの特徴と実施形態を実施することのできる通信システム100 の１例を与える。任意の種々のアルゴリズムと方法はシステム100 における送信のスケジュールに使用されてもよい。システム100 はそれぞれ対応する基地局104A乃至104Gによりサービスされている102A乃至102Gの複数のセルで通信を行う。例示的な実施形態では、幾つかの基地局104 は多数の受信アンテナを有し、別のものはただ１つの受信アンテナを有する。同様に、幾つかの基地局104 は多数の送信アンテナを有し、別のものはただ１つの送信アンテナを有する。送信アンテナと受信アンテナの組合わせには制限はない。それ故、基地局104 が多数の送信アンテナと単一の受信アンテナを有するか、多数の受信アンテナと単一の送信アンテナ、或いは両者共に単一または多数の送信アンテナと受信アンテナを有することが可能である。
【００１７】
カバー区域の端末106 は固定（即ち静止）または移動体のいずれでもよい。図１のＡに示されているように、種々の端末106 はシステム全体に分散されている。各端末106 は例えばソフトハンドオフが使用されるか否かまたは端末が（同時または逐次的に）多数の送信を多数の基地局から受信するように設計され、動作されるか否かに応じて、少なくとも１、恐らくそれ以上の基地局104 と任意の所定の瞬間にダウンリンクおよびアップリンクで通信する。ＣＤＭＡ通信システムのソフトハンドオフは技術でよく知られており、米国特許第5,101,501 号明細書（発明の名称“Method and system for providing a Soft Handoff in a CDMA Cellular Telephone System”）に詳細に説明されており、これは本発明の出願人に譲渡されている。
【００１８】
ダウンリンクは基地局から端末への送信を意味し、アップリンクは端末から基地局への送信を意味している。例示的な実施形態では、幾つかの端末196 は多数の受信アンテナを有し、別のものはただ１つの受信アンテナを有する。図１のＡでは、基地局104Aはデータを端末106Aと106Jへダウンリンクで送信し、基地局104Bはデータを端末106Bと106Jへで送信し、基地局104Cはデータを端末106Cへ送信する。
【００１９】
無線データ送信の需要の増加と無線通信技術により利用可能なサービスの拡大により特別なデータサービスが開発されている。１つのこのようなサービスは高データレート（ＨＤＲ）と呼ばれる。例示的なＨＤＲサービスは“ＨＤＲ仕様”と呼ばれ、“EIA/TIA-IS856 CDMA2000 High Rate Packet Data Air Interface Specification”で提案されている。ＨＤＲサービスは通常、無線通信システムでデータのパケットを送信する効率的な方法を提供する音声通信システムへのオーバーレイである。送信されるデータ量と送信数が増加すると、無線送信に利用可能な限定された帯域幅は臨界的なリソースになる。それ故、利用可能な帯域幅の使用を最適化する通信システムで送信をスケジュールする効率的で公正な方法が必要とされている。例示的な実施形態では、図１のＡに示されているシステム100 はＨＤＲサービスを有するＣＤＭＡタイプのシステムと適応している。
【００２０】
図１のＢは、無線インターフェース124 によりアクセス端末ＡＴ 126と通信しているアクセスネットワークＡＮ 122を有する通信システム120 のアーキテクチャ基準モデルを示している。１実施形態ではシステム10は特定されたＨＤＲ標準方式等の高データレートＨＤＲ、オーバーレイシステムを有する符号分割多元アクセスＣＤＭＡシステムである。ＡＮ 122はＡＴ 126およびシステム120 内の任意の他のＡＴ（図示せず）と無線インターフェース124 により通信する。ＡＮ 122は多数のセクタを含み、各セクタは少なくとも１つのチャンネルを提供する。チャンネルは所定の周波数割当て内でＡＮ 122とＡＴ間で送信するための通信リンクのセットとして規定される。チャンネルはＡＮ 122からＡＴ126 への送信の順方向リンク（ＦＬ）とＡＴ126 からＡＮ 122への送信の逆方向リンク（ＲＬ）からなる。
【００２１】
データ送信では、ＡＮ 122はＡＴ126 からデータリクエストを受信する。データリクエストはデータが送信されるデータレートと、送信されるデータパケットの長さと、データが送信されるセクタとを特定する。ＡＴ126 はＡＮ 122とＡＴ126 間のチャンネル品質に基づいてデータレートを決定する。１実施形態ではチャンネル品質は搬送波対干渉比Ｃ／Ｉにより決定される。別の実施形態はチャンネル品質に対応する他のメトリックを使用する。ＡＴ126 はＤＲＣチャンネルと呼ばれる特別なチャンネルによってデータレート制御ＤＲＣメッセージを送信することによってデータ送信をリクエストする。ＤＲＣメッセージはデータレート部分とセクタ部分を含んでいる。データレート部分はデータを送信するためのＡＮ 122のリクエストされたデータレートを示し、セクタはＡＮ 122がデータを送信するセクタを示している。データレートとセクタ情報は典型的にデータ送信のプロセスに必要とされる、データレート部分はＤＲＣ値と呼ばれ、セクタ部分はＤＲＣカバーと呼ばれる。ＤＲＣ値は無線インターフェース124 によりＡＮ 122へ送信されるメッセージである。１実施形態では、各ＤＲＣ値は予め定められたＤＲＣ値割当てにしたがって関連するパケット長を有するキロビット／秒のデータレートに対応する。割当てはゼロのデータレートを特定するＤＲＶ値を含んでいる。実際に、ゼロのデータレートはＡＴ 126がデータを受信できないことをＡＮ 122に示す。１つの状態では、例えばチャンネルの品質はＡＴ 126が正確にデータを受信するのは不十分である。
【００２２】
動作において、ＡＴ 126はそれが次のデータパケット送信を受信できるデータレートを計算するためにチャンネル品質を連続して観察する。ＡＴ 126はその後、対応するＤＲＣ値を発生し、そのＤＲＣ値はデータ送信をリクエストするためにＡＮ 122に送信される。典型的にデータ送信はパケットに区分されることに注意する。データのパケットの送信に必要な時間は与えられたデータレートの関数である。
【００２３】
このＤＲＣ信号はまた情報を提供し、これはチャンネルスケジューラが各待ち行列に関連する各遠隔局の消費情報（または受信する送信されたデータ）の瞬間レートを決定するために使用する。１実施形態にしたがって、任意の遠隔局から送信されたＤＲＣ信号は遠隔局が多数の効率的なデータレートの任意の１つでデータを受信できることを示している。このような可変レート送信システムは2000年５月16日出願の米国特許第6,064,678 号明細書（発明の名称“Method for Assigning Optimal packet Lengths in a Variable Rate Communication System ”）に詳細に説明されており、本発明の出願人に譲渡され、ここで参考文献とされている。
【００２４】
ＨＤＲ送信をサポートし、多数のユーザへの送信をスケジュールするように構成された通信システムの１例が図７に示されている。図７を以下詳細に説明し、ここで特に基地局820 と基地局制御装置810 はパケットネットワークインターフェース806 にインターフェースする。基地局制御装置810 はシステム800 での送信のためのスケジュールアルゴリズムを実行するためのチャンネルスケジューラ812 を含んでいる。チャンネルスケジューラ812 は（最も最近受信されたＤＲＣ信号で示されているような）データを受信するための遠隔局の関連する瞬間レートに基づいて、データが任意の特定の遠隔局へ送信されるサービスインターバルの長さを決定する。サービスインターバルは時間的に連続しないでｎスロット毎に一度生じる。１実施形態にしたがって、パケットの第１の部分は第１の時間の第１のスロット期間に送信され、パケットの第２の部分は後続する時間の４スロット後に送信される。また、パケットの後続部分は類似の４スロット分散、即ち相互に４スロット離れている多数のスロットで送信される。１実施形態にしたがって、受信データＲi の瞬間レートは特定のデータ待ち行列に関連するサービスインターバルの長さＬi を決定する。
【００２５】
さらに、チャンネルスケジューラ812 は送信のための特別なデータ待ち行列を選択する。送信されるデータの関連する品質はその後、データ待ち行列830 から検索され、データ待ち行列830 に関連する遠隔局へ送信するためにチャンネル素子826 へ与えられる。以下説明するように、チャンネルスケジューラ812 はデータを提供するための待ち行列を選択し、これは各待ち行列に関連する加重を含んだ情報を使用して後続するサービスインターバルで送信される。送信される待ち行列に関連する加重はその後更新される。
【００２６】
パケットの一部のみが送信されてもユーザは正確にパケットを受信することが可能であることに注意する。これはチャンネル状態がユーザにより予測されるよりも良好であるときに生じる。その場合にはユーザはパケットが既に正確に受信されており、パケットの残りの部分は送信される必要がないことを示す“ＡＣＫ”信号を基地局へ送信する。これが行われるとき、データパケット全体はさらに短いサービスインターバルでユーザへ効率よく送信され、それによってパケットが送信される効率的なデータレートを増加する。基地局はその後、別のパケットを同じユーザまたは異なるユーザへ送信するためにそのパケットの残りの部分を送信するようにもともとスケジュールされているタイムスロットを再割当する。このプロセスは通常自動反復リクエスト（ＡＲＱ）と呼ばれる。
【００２７】
ＡＲＱをサポートするシステムでは、データパケットは予め定められた数の送信を行うようにスケジュールされており、ここで各送信は異なる情報を含んでもよい。多数の送信は他のパケットを逐次的に挿入されている。受信機がパケットを復号し処理するのに十分な情報を受信するとき、受信機はこれ以上の情報が現在のパケットに必要とされないことの指示を送信機へ送信する。送信機はその後、現在のパケットにもともとスケジュールされているスロットを自由に別のパケットへスケジュールする。この方法で、システムリソースが保存され、受信機への送信時間は減少される。
【００２８】
例示的な可変レートの通信システムの基本サブシステムを示しているブロック図が図７で示されている。基地局制御装置810 はパケットネットワークインターフェース806 、公共交換電話網ＰＳＴＮ 808および通信システムの全ての基地局（簡単にするため１つの基地局820 だけが図７に示されている）とインターフェースする。基地局制御装置810 は通信システムの遠隔局と、パケットネットワークインターフェース806 とＰＳＴＮ808 とに接続されている他のユーザとの間の通信を調整する。ＰＳＴＮ808 は標準的な電話機ネットワーク（図７では図示せず）によりユーザとインターフェースする。
【００２９】
基地局制御装置810 は多数のセレクタ素子816 を含んでいるが、簡単にするため１つだけが図７に示されている。各セレクタ素子816 は１以上の基地局820 と１つの遠隔局（図示せず）との間の通信を制御するように割当てられる。セレクタ素子816 が所定の遠隔局に割当てられていないならば、呼制御プロセッサ818 は遠隔局をページする必要性を通知される。呼制御プロセッサ818 はその後、遠隔局をページするように基地局820 に命令する。
【００３０】
データソース802 は所定の遠隔局へ送信されるデータ量を含んでいる。データソース802 はデータをパケットネットワークインターフェース806 へ提供する。パケットネットワークインターフェース806 はデータを受信し、そのデータをセレクタ素子816 へ転送する。セレクタ素子816 はその後、ターゲット遠隔局と通信中の各基地局820 へそのデータを送信する。例示的な実施形態では、各基地局820 はデータの待ち行列830 を維持し、待ち行列830 は遠隔局へ送信されるデータを記憶する。
【００３１】
データはデータ待ち行列830 からチャンネル素子826 へデータパケットで送信される。例示的な実施形態では、順方向リンクで、“データパケット”は最大１０２４ビットのデータ量と、予め定められた“タイムスロット”（約１．６６７ミリ秒）内で目的地の遠隔局へ送信されるデータ量を意味する。各データパケットに対しては、チャンネル素子826 は必要な制御フィールドを挿入する。例示的な実施形態では、チャンネル素子826 は巡回冗長チェックＣＲＣのデータパケットおよび制御フィールドの符号化を行い、コードテールビットのセットを挿入する。データパケット、制御フィールド、ＣＲＣパリティビット、コードテールビットはフォーマットされたパケットを構成している。例示的な実施形態では、チャンネルエレメント826 はその後フォーマットされたパケットを符号化し、符号化されたパケット内のシンボルをインターリーブ（または再度順序付け）する。例示的な実施形態ではインターリーブされたパケットはウォルシュコードでカバーされ、短いＰＮＩとＰＮＱコードで拡散される。拡散データはＲＦ装置828 へ与えられ、そこで信号を直角位相変調、濾波、増幅する。順方向リンク信号は無線でアンテナを通って順方向リンクへ送信される。
【００３２】
遠隔局では、順方向リンク信号はアンテナにより受信され、受信機へ転送される。受信機は信号を濾波し、増幅し、直角位相復調し、量子化する。デジタル化された信号は復調器（ＤＥＭＯＤ）へ与えられ、ここで短いＰＮＩとＰＮＱコードでデスプレッドされ、ウォルシュカバーがデカバーされる。復調されたデータ信号は復号器へ与えられ、ここで基地局820 で行われた信号処理機能の逆、特に、デインターリーブ、復号、ＣＲＣチェック機能を行う。復号されたデータはデータシンクへ与えられる。
【００３３】
先に指摘したように、ハードウェアは順方向リンクでデータ、メッセージング、音声、ビデオ、およびその他の通信の可変レート送信をサポートする。データ待ち行列830 から送信されたデータのレートは遠隔局における信号強度と雑音環境の変化に適合するように変化する。各遠隔局は好ましくはデータレート制御ＤＲＣ信号を、各タイムスロットで関連する基地局820 へ送信する。ＤＲＣ信号は情報を基地局820 へ提供し、基地局820 は遠隔局の識別子と、遠隔局が関連するデータ待ち行列からデータをを受信するレートを含んでいる。したがって遠隔局の回路は信号強度を測定し、ＤＲＣ信号で送信されるレート情報を決定するために遠隔局の雑音環境を評価する。
【００３４】
各遠隔局により送信されるＤＲＣ信号は逆方向リンクチャンネルを通って伝送され、ＲＦ装置828 へ結合された受信アンテナを通して基地局820 で受信される。例示的な実施形態では、ＤＲＣ情報はチャンネル素子826 で復調され、基地局制御装置810 中に位置されているチャンネルスケジューラ812 または基地局820 に位置されたチャンネルスケジューラ832 へ提供される。第１の例示的な実施形態では、チャンネルスケジューラ832 は基地局820 中に位置される。別の実施形態では、チャンネルスケジューラ812 は基地局制御装置810 中に位置され、基地局制御装置810 内の全てのセレクタ素子816 に接続される。
【００３５】
最初に説明した例示的な実施形態では、チャンネルスケジューラ832 は待ち行列サイズとも呼ばれる各遠隔局で待ち行列されるデータ量を示している情報をデータ待ち行列830 から受信する。チャンネルスケジューラ832 ははその後、基地局820 によりサービスされる各遠隔局のＤＲＣ情報と待ち行列サイズに基づいてスケジュールを行う。待ち行列サイズが別の実施形態で使用されるスケジュールアルゴリズムで必要とされるならば、チャンネルスケジューラ812 はセレクタ素子816 から待ち行列サイズの情報を受信する。
【００３６】
１以上のユーザへのパケットの送信中、ユーザは送信されたパケット部分を含んだ各タイムスロットの後に“ＡＣＫ”信号を送信する。各ユーザにより送信されたＡＣＫ信号は逆方向リンクチャンネルを伝播し、ＲＦ装置828 に結合された受信アンテナを経て基地局820 で受信される。例示的な実施形態では、ＡＣＫ情報はチャンネル素子826 で復調され、基地局制御装置810 中に位置されているチャンネルスケジューラ812 または基地局820 に位置されているチャンネルスケジューラ832 へ与えられる。第１の例示的な実施形態では、チャンネルスケジューラ832 は基地局820 に位置されている。別の実施形態では、チャンネルスケジューラ812 は基地局制御装置810 に位置され、基地局制御装置810 内の全てのセレクタ素子816 に接続している。
【００３７】
本発明の実施形態は可変レートの送信をサポートできる他のハードウェアアーキテクチャにも応用可能である。本発明は逆方向リンクで可変レートの送信をカバーするように容易に拡張されることができる。例えば遠隔局からのＤＲＣ信号に基づいて基地局820 における受信データのレートを決定する代わりに、基地局820 は遠隔局から受信された信号の強度を測定し、遠隔局からの受信データのレートを決定するための雑音環境を評価する。基地局820 はその後、遠隔局から逆方向リンクでデータが送信されるレートを、各関連する遠隔局へ送信する。基地局820 は順方向リンクについてここで説明した方法と類似した方法で逆方向リンクの異なるデータレートに基づいて逆方向リンクにおける送信をスケジュールしてもよい。
【００３８】
また、前述の実施形態の基地局820 は符号分割多元アクセスＣＤＭＡ方式を使用して、基地局820 に関連する残りの遠隔局を除く遠隔局の選択された１以上のものへ送信する。任意の特定の時間に、基地局820 は受信基地局820 へ割当てられたコードを使用して遠隔局の選択された１つまたは選択された１以上のものへ送信する。しかしながら本発明はまた送信リソースを最適に割当てるために、データを他の基地局820 を除く選択された基地局820 へ提供する異なる時間分割多重アクセスＴＤＭＡ方法を使用している他のシステムにも応用可能である。
【００３９】
チャンネルスケジューラ812 は順方向リンクの可変レート送信をスケジュールする。チャンネルスケジューラ812 は待ち行列サイズを受信し、これは遠隔局へ送信するデータの量、遠隔局からのメッセージの量を示している。チャンネルスケジューラ812 は好ましくは公正制約に適合しながら最大のデータスループットのシステムの目的を実現するためにデータ送信をスケジュールする。
【００４０】
図１で示されているように、遠隔局は通信システム全体に分散されており、ゼロまたは１つの基地局と順方向リンクで通信中である。例示的な実施形態ではチャンネルスケジューラ812 は順方向リンクデータ送信を通信システム全体にわたって調整する。高速度データ送信のためにスケジュール方法および装置は1997年２月11日出願の米国特許出願第08/798,951号明細書（発明の名称“Method and Apparatus for Forward Link Rate Scheduling ”）に詳細に説明されており、これは本発明の出願人に譲渡され、ここで参考文献とされている。
【００４１】
１実施形態によれば、チャンネルスケジューラ812 はコンピュータシステム中に構成され、プロセッサ、ランダムアクセスメモリ、ＲＡＭおよびプロセッサ（図示せず）により実行される命令を記憶するためのプログラムメモリを含んでいる。プロセッサ、ＲＡＭ、プログラムメモリはチャンネルスケジューラ812 の機能に専用とされていてもよい。他の実施形態では、プロセッサ、ＲＡＭ、プログラムメモリは基地局制御装置810 における付加的な機能を行うための共有されたコンピュータ処理リソースの一部であってもよい。例示的な実施形態では、一般化されたスケジューラは図７に示されているシステム800 に適用され、以下詳細に説明する。データ送信のスケジュールのための優先順位機能を実行するのに使用されるＢＳＣ 810とＢＳ 820内のこれらのモジュールについて一般化されたスケジューラの特定を行った後に説明する。
【００４２】
無線データ応用での需要が増加すると、非常に効率的な無線データ通信システムの需要は著しく増加する。ＩＳ−９５標準方式はトラフィックデータおよび音声データを順方向および逆方向リンクによって送信できる。ＩＳ−９５標準方式にしたがって、トラフィックデータまたは音声データは１４．４Ｋｂｐｓ程度のデータレートで２０ミリ秒の幅のコードチャンネルフレームに区画される。ＩＳ−９５システムでは、各加入者局は限定された数の直交順方向リンクチャンネルの少なくとも１つを割当てられる。基地局と加入者局との通信が進行中である一方で、順方向リンクチャンネルは加入者局に割当てられたままの状態である。データサービスがＩＳ−９５システムで行われるとき、順方向リンクチャンネルは加入者局へ送信される順方向リンクデータが存在しないときでも加入者局へ割当てられた状態である。
【００４３】
音声サービスとデータサービスの大きな差は前者が厳格で固定した遅延要求を有することである。典型的に、スピーチフレームの１方向遅延全体は１００ミリ秒よりも小さいように特定される。それと対照的に、データ遅延はデータ通信システムの効率を最適にするために使用される可変パラメータになることができる。
【００４４】
音声サービスとデータサービスの別の大きな差は前者が全てのユーザに対して固定し共通したグレードのサービス（ＧＯＳ）を必要とすることである。典型的に音声サービスを提供するデジタルシステムでは、これは全てのユーザに対して固定された等しい送信レートと、スピーチフレームのエラー率に対する最大の許容値に変換される。対照的に、データサービスでは、ＧＯＳはユーザにより異なり、データ通信システムの全体効率を増加するように最適化されたパラメータである。データ通信システムのＧＯＳは典型的にここではデータパケットと呼ぶ予め定められたデータ量の転送で被る総遅延として規定される。
【００４５】
音声サービスとデータサービスのさらに別の大きな差は前者が確実な通信リンクを必要とすることであり、これは例示的なＣＤＭＡ通信システムではソフトハンドオフにより行われる。ソフトハンドオフは信頼性を改良するために２以上の基地局から冗長送信を行う。しかしながら、この付加的な信頼性はエラーを有して受信されたデータパケットが再送信されるのでデータ送信に必要とされない。データサービスでは、ソフトハンドオフのサポートに使用される送信パワーは付加的なデータの送信にさらに効率的に使用されることができる。
【００４６】
データパケットと平均スループットレートに必要な送信遅延はデータ通信システムの品質と効率性を規定するのに使用される２つの属性である。送信遅延は音声通信で行うのと同じ影響をデータ通信ではもたないが、データ通信システムの品質を測定するには重要なメトリックである。平均スループットレートは通信システムのデータ送信能力の効率の尺度である。無線チャンネルで提供されるタイプのサービスに適切なＧＯＳを同時に提供しながら改良されたデータスループットを与える通信システムが技術で必要とされている。
【００４７】
一般化されたスケジューラの必要性は無線システムのデータ送信の要求およびターゲットに基づいている。データ送信では、スループットは個々のビットまたはバイトに関するよりもデータのパケットの送信で被る遅延に関して規定される。インターネットプロトコルＩＰデータグラム等のデータパケットは、多くの場合、パケットの一部のみの受信はユーザがパケット全体を復号し使用するのに十分な情報を含まないので、即ちパケットはエンドユーザに対して無用なので、分割できない装置である。エンドユーザはデータパケットを受信し、データパケットで巡回冗長チェックＣＲＣを実行し、データを処理する。それ故、ユーザはパケットの最後のビットの到着時間に最も関心をもち、データパケットの個々おビットの遅延には関心をもたない。これはデータパケットの送信時間よりも小さい時間スケールにわたって異なるユーザへのレート割当てにかなりのフレキシブル性を可能にする。さらに、送信制御プロトコルＴＣＰでは、タイプ接続、パケット遅延の幾つかの変化はＴＣＰの再送信を不必要に起こす変化がそれ程予測不可能ではない限り、許容可能である。
【００４８】
無線チャンネルの別の特徴はチャンネル自体の可変性である。ＨＤＲタイプのシステムでは、この可変性は時間にわたるリクエストされたレートの変化を生じる。チャンネルの使用を最大にするために、スケジューラは高いレートのユーザ、即ち最高のデータレートをリクエストするユーザにサービスするように設計されている。このことは時には、ユーザが彼等のリクエストされたレートが低い時間期間にサービスされない可能性があることを意味している。スループット全体はスケジューラが長時間、低いレートのユーザにサービスしないときに最大にされる。しかしながら、理想的にはスケジューラは前述したようにパケット遅延と遅延変化が比較的一貫性を有する要望に対してこれを平衡する。
【００４９】
別の特徴はシステム中の多数のユーザに対する公正さを考慮する。公正スケジュール方法を実現するために、スケジューラは理想的には異なるユーザ間に総合的なスループットを分配する。異なるベースの公正さ（または許容可能な非公正さ）は異なるシステムによって、個々のシステムの要求と要望に作用するように使用される。公正さの概念は多くのスケジュールアルゴリズムで重要な概念である。公正さはサービスする異なるユーザに対して異なる量のフレキシブル性を与え、セクタの全体的なスループットに影響を有する。
【００５０】
１実施形態によると、多数のクラスのユーザへの応用を有する通信システムでの送信のスケジュール方法および装置は一般化されたスケジューラを構成する。一般化されたスケジューラは種々の異なるスケジュール優先順位を適合する。それぞれ特別な送信要求を有する異なるクラスのユーザは全てのユーザで高いスループットを維持している一般化されたスケジューラによりサービスされる。
【００５１】
例示的な実施形態では、一般化されたスケジューラの動作はチャンネル状態メトリックと公正さ基準の優先順位関数を実行し、ここで優先順位関数は次式で規定される。
ｆ（Ａi （ｔ），Ｕi （ｔ））                  （１）
ここでＡi （ｔ）はチャンネル状態メトリックを指し、Ｕi （ｔ）はユーザ公正さメトリックを指している。関数Ａi （ｔ）は現在のチャンネル状態に基づいて時間ｔにおいてユーザｉをサービスする要望を特定する。関数Ｕi （ｔ）は受信されたサービスの過去の経歴に基づいて時間ｔでユーザｉをサービスする要望を特定する。優先順位関数ｆ( ) は２つの要望メトリックＡi （ｔ）とＵi （ｔ）を結合して、各ユーザに対する優先順位レベルを決定する。
【００５２】
図９Ａを参照すると、例示的な実施形態では、多数のユーザはそれぞれ同一の基地局から送信を受信するための所望の基準を有する。基準を測定するのに使用されるスケールはここでは転送優先順位パラメータ（ＤＰＰ）と呼ばれ、ＤＰＰは各ユーザの所望の優先順位を反映している。例えば第１のユーザは特定の時間割当てで送信を受信することを望み、第２のユーザは特定のスループットの送信を受信することを望んでいる。さらに第３のユーザは特定された遅延を有する送信を受信することを望んでいる。第１のユーザのＤＰＰは時間スケールを反映し、第２のユーザのＤＰＰは秒当たりのビット（ｂｐｓ）スケールを反映し、第３のユーザのＤＰＰは時間遅延スケールを示す。各ユーザのＤＰＰは送信を受信するための所望の基準の特定値を識別する。
【００５３】
多数のユーザのＤＰＰは共通のスケールにマップされる。共通のスケールはＤＰＰ内の値範囲のユニットレス（unitless）の比例表示である。図９Ａで示されているように、各ＤＰＰは異なる値の範囲を有し、各異なるＤＰＰ範囲は共通のスケールにマップされる。ＤＰＰ範囲内の特定のユーザの実際値のマッピングはここではマップされた優先順位パラメータ（ＭＰＰ）と呼ぶ。
【００５４】
図９Ｂは第１のＤＰＰをＭＰＰへマッピングするシナリオを示しており、３つの異なるＤＰＰタイプはＡ、Ｂ、Ｃとラベル付けされている。水平軸は各３つのタイプのＤＰＰ範囲を表している。垂直軸は値のＭＰＰ範囲を表している。理解を明白にするために、図９ＢではＤＰＰタイプＡは秒当りのビットで測定されたスループットパラメータを表し、ＤＰＰタイプＢは全てのユーザに割当てられた総時間に比例する１人のユーザに割当てられた時間のユニットレス比として測定された時間比例パラメータを表し、ＤＰＰタイプＣはユニットレス比として測定された時間遅延比例を表している。別の実施形態は所定のシステムに特別な任意のタイプのＤＰＰを構成し、さらに、別の実施形態はここでの例で説明されている比例値ではなく実際の時間単位を含んでいる。所定のＤＰＰに対する値の範囲は予め定められた範囲にわたって与えられている。例えば、ＤＰＰタイプＡの値の範囲は０ｂｐｓからシステムによりサポートされる最大値までである。同様に、ＤＰＰタイプＢの値範囲はユーザが送信を受信しない０からユーザが全ての送信時間を受信する予め定められた最大値までである。ＤＰＰタイプＣの値範囲は遅延なしから最大遅延までである。
【００５５】
タイプＡは増加する関数であり、ＭＰＰ＝１は最大値に対応し、ＭＰＰ＝０は最小値に対応する。タイプＢも増加する関数であり、ＭＰＰ＝１は最大値に対応し、ＭＰＰ＝０は最小値に対応する。タイプＣは減少する関数であり、ＭＰＰ＝１は遅延なしに対応し、ＭＰＰ＝０は最大遅延に対応することに注意する。ＭＰＰ範囲はＤＰＰの最小から最大値を示している。換言すると、ＭＰＰ範囲はＤＰＰ範囲を使用する。代わりのマッピングは種々のＤＰＰの共通の評価ベースを与えるように実行される。図９Ｂについて説明を継続すると、動作点はＭＰＰ範囲１から０内で選択される。動作点はＤＰＰ範囲で示されるように各ユーザを満足するための利用可能なリソースを示している。動作点は与えられた範囲内の各ＤＰＰの正確な値を規定する。例えば、動作点はタイプＡの値ｄ３、タイプＢの値ｄ２、タイプＣの値ｄ１を規定する。これらのＤＰＰを有する個々のユーザには動作点が存在する。値ｄ１、ｄ２、ｄ３は対応するＤＰＰの単位を考慮して解釈された各範囲内の特別な値である。値ｄ１はｂｐｓで解釈され、値ｄ２は時間の割合として解釈され、値ｄ３は遅延の割合として解釈される。
【００５６】
図９Ｃは同じＤＰＰからＭＰＰのマッピングを示しており、ここでは異なる動作点が選択される。タイプＢとタイプＣのＤＰＰは結果的に共通の値ｄ４となり、タイプＡは異なる値ｄ５を結果とする。図９Ｄは別のＤＰＰからＭＰＰのマッピングを示している。ここで結果的な関数は減少する関数であるが、関数は線形ではない。動作点はＤＰＰ値ｄ６を規定する。
【００５７】
図１０は１実施形態による一般化されたスケジューラ方法1200のフロー図を示している。ステップ1202で、一般化されたスケジューラはＮのユーザのそれぞれからＤＰＰタイプの情報を受信する。ＤＰＰタイプの情報は一般化されたスケジューラにＮのユーザ間の動作点を決定する情報を提供する。決定の菱形ブロック1204では、一般化されたスケジューラは全てのＤＰＰ値が全ての対のユーザで等しいか否か、即ちユニットを考慮せずに絶対値を決定する。全てのＤＰＰ対が等しい値を有するならば処理はステップ1212へ進み、前述の式（１）により規定された一般化されたスケジューラを適用する。ＤＰＰ値が全て等しくないならば、処理はステップ1206へ続き、図９Ａ−９Ｄで示されているように、各ＤＰＰ範囲を対応するＭＰＰ範囲へマップする。ステップ1208で、一般化されたスケジューラは各ユーザの利用可能なリソースによりサポートされた動作点を決定する。ステップ1210で、プロセスは動作点を各ユーザへ適用し、動作の継続のため正確なＤＰＰ値を決定する。処理はその後、前述の式（１）により規定された一般化されたスケジュールアルゴリズムを適用するためにステップ1212へ続く。このようにして、一般化されたスケジューラは個々のＤＰＰを考慮せずに共通のＭＰＰ動作点を各ユーザへ適用する。ＭＰＰ動作点が一度選択されると、一般化されたスケジューラは各ＤＰＰ範囲内の正確なＤＰＰ値へ外挿する。ユーザはそれ故、異なる優先順位のパラメータをそれぞれリクエストし、ここで一般化されたスケジューラは共通のスケールをスケジュールに適用する。
【００５８】
例示的な実施形態にしたがって、一般化されたスケジューラは所定のクラスまたはユーザタイプ内で最高の優先順位関数ｆ（Ａi （ｔ），Ｕi （ｔ））をユーザにサービスする。例示的な実施形態では、優先順位関数ｆ（Ａi （ｔ），Ｕi （ｔ））により取られる値はチャンネル状態関数Ａi （ｔ）が増加するときに増加し、公正関数Ｕi （ｔ）が増加するときに減少する。関数Ａi （ｔ）とＵi （ｔ）はしたがって決定される。さらに、優先順位関数ｆ( ) はチャンネル状態メトリックとユーザ公正メトリックが測定される少なくとも１つの時間期間の関数である。別の実施形態では、優先順位関数ｆ( ) はユーザ機能当たり時間依存性である。しかしながら、簡単にするために、全てのユーザに共通である結合器関数に固着し、ユーザの要求を反映するためにユーザ公正メトリックを変更することが最良である。また説明を明瞭にするため、分割演算として優先順位関数を考慮する。
【００５９】
チャンネル状態メトリックはチャンネル状態の変化の効率を利用する。以下説明するように、メトリックはＤＲＣ、ＤＲＣ／ＤＲＣａｖｅ、ＤＲＣ−ＤＲＣａｖｅまたは定数値として規定される。多数のユーザダイバーシティからの利得を最大にするために、選択されたチャンネル品質メトリックはチャンネル状態がそのユーザの平均状態に関して良好であるときに高い値を有するべきである。説明を明白にするために、例示的な実施形態はチャンネル状態メトリックとしてＤＲＣ／ＤＲＣａｖｅを考慮する。特に重要なのはＤＲＣａｖｅの定義である。平均化はチャンネル状態の時定数Ｔｃにわたって行われなければならない。このように、チャンネル状態メトリックはＴｃよりも小さい時間スケールにわたってＤＲＣにより変化することが予測される。Ｔｃよりも大きい時間スケールにわたって生じるＤＲＣ値の変化は長期で考慮され、チャンネル状態メトリックの分子と分母の両者に等しく影響し、したがって相互に消去する。Ｔｃの値はチャンネルダイナミックを観察することにより選択される。チャンネルダイナミックがＤＲＣ値が例えばＴ１の長さの時間スケールにわたって顕著に変化するようなものであるならば、時定数ＴｃはＴ１よりも大きくなければならない。チャンネル状態メトリックはユーザの要求により可能にされる最大の時定数を使用しなければならないことに注意する。
【００６０】
例示的な実施形態によると、公正メトリックはユーザのクラス毎に実効的に一定にされている。選択されたチャンネル状態メトリック、および約１で振動する傾向がチャンネル状態メトリックにあるならば、スケジューラは低いユーザ公正メトリック値を有するユーザにサービスし、高いユーザ公正メトリック値を有するユーザにサービスしない傾向がある。このように、一般化されたスケジューラは多数のユーザダイバーシティを利用しながらユーザ公正メトリックを一定に維持するアルゴリズムに類似している。各ユーザが最も所望する状態がユーザ公正メトリックの同じ数値になるようにユーザ公正メトリックを決定するため、システムが多数の異なるタイプの要求を有するユーザにサービスすることを可能にする。また、所望の動作点周辺の勾配はどれ程の過剰な容量または容量の欠損が異なるユーザ間で分配されているかを決定する。異なるユーザに対するスケジュールの重要な洞察は多数のユーザのダイバーシティを利用しながら一定値でユーザ公正メトリックを維持することである。
【００６１】
サービスにしたがってユーザを区分するシステムでは、異なるクラスのユーザはラウンドロビン方法等の優先順位またはその他の方式にしたがってサービスされる。最初に単一のクラスまたはユーザタイプを考える。例示的な実施形態は最高のｆ（Ａi （ｔ），Ｕi （ｔ））を使用するが、別の実施形態は最低値および／または別のタイプの関数を使用してもよい。ｆ( ) 、Ａi （ｔ）、Ｕi （ｔ）の適切な定義の決定はスケジュールの有効性を決定する。
【００６２】
本発明は種々のスケジュールアルゴリズムと優先順位化に適用可能であり、ここで説明したものに限定されない。明白にするため、幾つかのスケジュールアルゴリズムを一般化されたスケジューラと種々の構造の例を与えるために説明した。
【００６３】
本発明の実施形態は単一の通信ノードによってサービスされる通信ネットワークへ複数の加入者間のリソースを割当てるシステムおよび装置に関する。個々のディスクリートな送信インターバルまたは“サービスインターバル”で、個々の加入者は全ての他の加入者を除く通信ノードの有限リソースを使用する。個々の加入者は彼等に関連する加重またはスコアに基づいて有限リソースを使用するように選択される。個々の加入者に関連する加重の変化は個々の加入者が有限リソースを消費できる瞬間レートに基づくことが好ましい。
【００６４】
１実施形態では、ＡＴ 126はＤＲＣカバーによりＤＲＣ値をカバーする。ＤＲＣカバーはデータが送信されるセクタを識別するために適用するコーディングである。１実施形態では、ＤＲＣカバーはＤＲＣ値に適用されるウォルシュコードであり、特有のコードはＡＴ 126のアクチブセットの各セクタに対応する。アクチブセットＡＳはこれらのセクタからなり、これらのセクタと共にＡＴ 126は現在情報を送信し受信している。ＤＲＣ値とＤＲＣカバーはＤＲＣ値がデータレートを特定し、ＤＲＣカバーが送信セクタを識別するとき完全なデータリクエストを提供する。別の実施形態は送信セクタを識別する別のカバーまたは方法を使用してもよい。さらに別の実施形態はＤＲＣ値のセクタ識別子を含んでもよい。
【００６５】
一般化されたスケジューラフレームワークを使用して構成されることのできるスケジューラの１例は、多数のユーザダイバーシティの利用によりシステムのスループットを改良する均等時間スケジューラである。このスケジューラのチャンネル状態メトリックは前述のＤＲＣ／ＤＲＣａｖｅである。特に任意の時間ｔにおいて、スケジューラは各ユーザｉについてチャンネル状態メトリックＡｉ（ｔ）を計算する。Ａｉ（ｔ）＝ＤＲＣｉ（ｔ）／ＤＲＣａｖｅｉ（ｔ）であり、ここでＤＲＣｉ（ｔ）は時間ｔでユーザｉからのチャンネル状態を示す受信されたＤＲＣ信号であり、ＤＲＣａｖｅｉ（ｔ）は次式により与えられる。
ＤＲＣａｖｅｉ（ｔ）＝
ＤＲＣａｖｅｉ (ｔ−１)(１−１／ｔａ) ＋ＤＲＣｉ (ｔ−１)(１／ｔａ)
（２）
ここでｔａは平均化のための時定数である。
【００６６】
ユーザの要求メトリック（Ｕｉ（ｔ））がｆｒａｃｉ（ｔ）として与えられ、ここでｆｒａｃｉ（ｔ）は次式を使用して規定される。
ｆｒａｃｉ（ｔ）＝
ｆｒａｃｉ (ｔ−１)(１−１／ｔｕ) ＋Ｓｅｒｖｅｄｉ (ｔ−１)(１／ｔｕ)
（３）
Ｓｅｒｖｅｄｉ (ｔ−１) はユーザｉがスロットｔ−１中にサービスされるならば１であり、ユーザがスロットｔ−１中にサービスされないならば０である。ｆｒａｃｉ（ｔ）はユーザｉのサービスに費やす時間の平均的な割合であり、平均化は式（２）に基づいて行われることに注意すべきである。
【００６７】
スケジューラはその後各時間スロットｔにおける各ユーザおよび送信するデータを有するユーザ間でＡｉ（ｔ）／Ｕｉ（ｔ）を計算し、最高のＡｉ（ｔ）／Ｕｉ（ｔ）を有するユーザにサービスする。
【００６８】
一般化されたスケジューラフレームワークを使用して構成されることのできるスケジューラの別の例は多数のユーザダイバーシティの利用によりシステムのスループットを改良するだけでなく２つの異なる品質のサービスを２つの異なるクラスのユーザに提供する均等時間スケジューラである。ユーザの１つのクラス、例えばクラスＡはパケット遅延に敏感であり、スケジューラはそれらに別のクラス、例えばクラスＢよりも小さいジッタをサービスする。このスケジューラのチャンネル状態メトリックは前述したＤＲＣ／ＤＲＣａｖｅである。特に、任意の時間ｔにおいて、スケジューラは以下のように各ユーザｉのチャンネル状態メトリックＡｉ（ｔ）を計算する。
Ａｉ（ｔ）＝ＤＲＣｉ（ｔ）／ＤＲＣａｖｅｉ（ｔ）                  （４）
ここで、ＤＲＣｉ（ｔ）は時間ｔにおいてユーザｉからのチャンネル状態を示す受信されたＤＲＣ信号であり、ＤＲＣａｖｅｉ（ｔ）は次式により与えられる。
ＤＲＣａｖｅｉ（ｔ）＝
ＤＲＣａｖｅｉ (ｔ−１)(１−１／ａ) ＋ＤＲＣ (ｔ−１)(１／ｔａ)     （５）
ここでｔａは平均化のための時定数である。
【００６９】
クラスＡのユーザに対するユーザ要求メトリック（Ｕｉ（ｔ））はｆｒａｃｉａ（ｔ）であり、ここでｆｒａｃｉａ（ｔ）は次式を使用して規定される。
ｆｒａｃｉａ（ｔ）＝
ｆｒａｃｉａ (ｔ−１)(１−１／ｔｕａ) ＋
Ｓｅｒｖｅｄｉａ (ｔ−１)(１／ｔｕａ)                         （６）
Ｓｅｒｖｅｄｉａ (ｔ−１) はクラスＡのユーザｉがスロットｔ−１中にサービスされるならば１であり、ユーザがスロットｔ−１中にサービスされないならば０である。ｆｒａｃｉａ（ｔ）はユーザｉのサービスに費やす時間の平均的な割合であり、平均化は式（５）に基づいて行われることに注意する。
【００７０】
クラスＢのユーザのユーザ要求メトリック（Ｕｉ（ｔ））はｆｒａｃｉｂ（ｔ）であり、ここでｆｒａｃｉｂ（ｔ）は次式を使用して規定される。
ｆｒａｃｉｂ（ｔ）＝
ｆｒａｃｉｂ (ｔ−１)(１−１／ｔｕｂ) ＋
Ｓｅｒｖｅｄｉｂ (ｔ−１)(１／ｔｕｂ)                         （７）
Ｓｅｒｖｅｄｉｂ (ｔ−１) はクラスＢのユーザｉがスロットｔ−１中にサービスされるならば１であり、ユーザがスロットｔ−１中にサービスされないならば０である。ｆｒａｃｉｂ（ｔ）はユーザｉのサービスに費やす時間の平均的な割合であり、平均化は式（５）に基づいて行われることに注意すべきである。スケジューラは各時間スロットｔにおける各ユーザおよび送信するデータを有するユーザ間でＡｉ（ｔ）／Ｕｉ（ｔ）を計算し、最高のＡｉ（ｔ）／Ｕｉ（ｔ）を有するユーザにサービスする。
【００７１】
この場合、ｔｕａ＜ｔｕｂであり、クラスＡのユーザのＵｉ（ｔ）がクラスＢのユーザのＵｉ（ｔ）よりも速く減衰することを示している。結果として、クラスＡのユーザはクラスＢのユーザよりも頻繁にサービスを獲得するが、クラスＡのユーザがサービスを獲得する度に、これはさらに小さい時間量である。全体として、スケジューラは各ユーザにサービスするのに等しい時間量を費やす。
【００７２】
一般化されたスケジューラフレームワークを使用して構成されることのできる別の例のスケジューラは多数のユーザのダイバーシティの利用によりシステムのスループットを改良する比例公正スケジューラである。このスケジューラに対するチャンネル状態メトリックは前述したＤＲＣ／ＤＲＣａｖｅである。特に、任意の時間ｔではスケジューラは各ユーザｉについてチャンネル状態メトリックＡｉ（ｔ）を計算する。
Ａｉ（ｔ）＝ＤＲＣｉ（ｔ）／ＤＲＣａｖｅｉ（ｔ）                （８）
ここで、ＤＲＣｉ（ｔ）は時間ｔにおけるチャンネル状態を示しているユーザｉから受信されたＤＲＣ信号であり、ＤＲＣａｖｅｉ（ｔ）は次式により与えられる。
ＤＲＣａｖｅｉ（ｔ）＝ＤＲＣａｖｅｉ (ｔ)(ｔ−１)(１−ｔ／ｔａ) ＋
ＤＲＣｉ (ｔ−１)(１／ｔａ)                                   （９）
ここでｔａは平均化のための時定数である。ユーザ要求メトリック（Ｕｉ（ｔ））はＳｅｒｖｅｄＲａｔｅａｖｅｉ（ｔ）／ＤＲＣａｖｅｉ（ｔ）として与えられ、ここでＳｅｒｖｅｄＲａｔｅａｖｅｉ（ｔ）は次式を使用して規定される。
ＳｅｒｖｅｄＲａｔｅａｖｅｉ（ｔ）＝
ＳｅｒｖｅｄＲａｔｅａｖｅｉ (ｔ−１)(１−１／ｔａ) ＋
Ｓｅｒｖｅｄ Ｒａｔｅ (ｔ−１)(１／ｔａ)                     （１０）
ここでＳｅｒｖｅｄ Ｒａｔｅｉ (ｔ−１) はユーザｉがスロットｔ−１中にサービスされるレートであり、ユーザがスロットｔ−１中にサービスされないならば０である。Ｓｅｒｖｅｄ Ｒａｔｅｉ（ｔ）は平均化が式（９）に基づいて行われる場合にユーザｉにサービスするために使用される平均データレートであることに注意すべきである。
【００７３】
スケジューラは各時間スロットｔにおける各ユーザのＡｉ（ｔ）／Ｕｉ（ｔ）を計算して、データの送信を保留中のユーザ間で最高のＡｉ（ｔ）／Ｕｉ（ｔ）を有するユーザにサービスする。
【００７４】
さらに、一般化されたスケジューラ方法を使用して構成されることのできる別の例のスケジューラはサービスグレードスケージューラである。サービスグレードスケージューラの原理は任意の２人のユーザ間のビットレート比を予め定められた値Ｇ内に維持することである。サービスグレードスケージューラは所定の時間インターバルにわたってビットレート比の要求を維持する。このスケジューラは短い時間インターバルにわたって多数のユーザのダイバーシティの利用によりシステムスループットを改良する。このスケジューラのチャンネル状態メトリックは前述のＤＲＣ／ＤＲＣａｖｅである。特に任意の時間ｔにおいてスケジューラは各チャンネルユーザｉに対するチャンネル状態メトリックＡｉ（ｔ）を計算する。Ａｉ（ｔ）＝ＤＲＣｉ（ｔ）／ＤＲＣａｖｅｉ（ｔ）であり、ここでＤＲＣｉ（ｔ）は時間ｔにおけるユーザｉから受信されたチャンネル状態を示すＤＲＣ信号であり、ＤＲＣａｖｅｉ（ｔ）は次式により与えられる。
ＤＲＣａｖｅｉ（ｔ）＝ＤＲＣａｖｅｉ (ｔ−１)(１−１／ｔａ) ＋
ＤＲＣｉ (ｔ−１)(１／ｔａ)                                   （１１）
ここでｔａは平均化のための時定数である。
【００７５】
ユーザ要求メトリック（Ｕｉ（ｔ））は以下の方法で計算される。各タイムスロットで、全体的なシステムのスループットの尺度、即ち基地局によりサービスされる全てのユーザのスループットの合計は記憶され、Ｒｔｏｔａｌと呼ばれる。Ｒｔｏｔａｌの追跡を維持する１つの可能な方法は各タイムスロットｔで以下の計算を行うことにより行われる。
Ｒｔｏｔａｌ（ｔ）＝Ｒｔｏｔａｌ (ｔ−１)(１−１／ｔｔｏｔａｌ) ＋
ＳｙｓｔｅｍＳｅｒｖｅｄＲａｔｅ (ｔ−１)(１／ｔｔｏｔａｌ)     （１２）
ここでＳｙｓｔｅｍＳｅｒｖｅｄＲａｔｅ (ｔ−１) はシステムが時間ｔ−１で任意のユーザにサービスしているレートであり、ユーザが時間ｔ−１中にサービスされないならば０であり、ｔｔｏｔａｌは適切に選択された時定数である。
【００７６】
また、加重Ｗは各ユーザに対して維持される。長さＢバイトを有するデータパケットがユーザに送信され、ユーザのデータレートがパケットが送信されたときのＲｔｏｔａｌよりも小さいとき、加重ＷはＢ* Ｇだけ増加される。Ｂバイトパケットがユーザに送信された後、加重ＷはＢだけ増加され、ユーザのデータレートはパケットが送信されたときのＲｔｏｔａｌ以上である。加重Ｗは時間により変化するので、これはＷ（ｔ）として表される。また各ユーザは異なる加重を有するので、それに属するユーザを識別するための添字を使用する。それ故、時間ｔにおけるユーザｊの加重はＷｉ（ｔ）により示される。
【００７７】
さらに、カラーと呼ばれるパラメータが存在する。カラーはスケジューラパラメータとして特定化され時間の経過に対して変化しない数である。Ｗｍｉｎ（ｔ）が時間ｔにおける全てのユーザ間で最小の加重であることを想定する。ユーザ要求メトリックＵｉ（ｔ）はＷｍｉｎ（ｔ）とＷｍｉｎ（ｔ）＋カラーとの間の加重を有する全てのユーザで１に規定される。１つのケースでは、Ｕｉ（ｔ）は全ての他のユーザに対して、例えば１０００の大きい定数であるように規定される。
【００７８】
次にスケジューラは各時間スロットｔにおける各ユーザに対してＡｉ（ｔ）／Ｕｉ（ｔ）を計算し、データの送信を保留中のユーザ間で、最高のＡｉ（ｔ）／Ｕｉ（ｔ）を有するユーザにサービスする。
【００７９】
前述したように、ＨＤＲシステム等の種々のスケジュールアルゴリズムがデータ送信をサポートするシステムで送信をスケジュールするために使用される。１つの方法はサービスグレ−ドＧＯＳスケジュールアルゴリズムと呼ばれる。図２は図１のシステム100 に適用可能なＧＯＳスケジューラを示しており、ここで各アクチブユーザまたは移動局ＭＳはデータレートリクエストを基地局ＢＳへ送信する。ＧＯＳスケジューラは任意の２つのユーザ対の間のレート比を維持するデータ送信のためにユーザを選択する方法を提供し、したがって対応する公正基準を満たす。換言すると、ＧＯＳスケジューラに対する公正基準は各ユーザのスループットが他のそれぞれのユーザに比例することを確実にする。
【００８０】
スケジューラ方法200 はＢＳで実行され、アクチブセットのユーザを考慮し、ユーザはそのユーザとＢＳとの間で通信するために保留されたデータが存在するときのアクチブセットのメンバである。アクチブユーザの総数はＮで与えられ、インデックスｉはアクチブセットの個々のメンバを識別する。データ送信では、アクチブセットの各Ｎ数のユーザはＢＳにユーザが所望しているデータレートでデータを送信するように命令する。データレート情報はデータレートリクエストメッセージとして与えられる。１実施形態では、データレートリクエストはデータレート制御ＤＲＣメッセージである。データレートリクエストメッセージは順方向リンクＦＬの品質を示す。
【００８１】
図２を続いて参照すると、ステップ202 で各ＮのユーザはＤＲＣ値を送信する。ステップ204 で、ＢＳは送信されるビット数に基づいてＮのユーザのそれぞれのスループットを決定する。ＢＳは各Ｎ数のユーザに送信し、それ故所定の時間中に各ユーザに送信される送信ビット数を知っている。ユーザｉのスループットはＴｉとして与えられる。第２のインデックスｊはユーザｉとの比較のためにユーザを識別するのに使用される。決定の菱形ブロック206 で、ＢＳはユーザｉと、アクチブセットの全てのユーザのユーザｊとのスループット比を決定する。比はその後値Ｇに比例する公正基準と比較される。
全てのｉおよびｊに対して、Ｔｉ／Ｔｊ≦Ｇ                           （１３）
式（１３）で与えられるように、スループットはＧの増加と共に増加することに注意すべきである。スループットの増加は公正さを犠牲にし、Ｇ値が高い程、異なるユーザのスループットの差は大きくなる。この意味で公正さは所定のユーザに送信される実際のビット数を指している。式（１３）の比がユーザｉとｊの任意の組合わせの式を満たさないならば、ステップ210 でＢＳは式（１３）の関係を実現またはほぼ実現するようにスケジュールを決定する。この場合、ＢＳは典型的に低いスループット値を有するユーザへの送信を増加する。このようにして、最低のスループットを有するユーザと最高のスループットを有するユーザとの比は減少される。式（１３）が決定菱形ブロック206 で満足されたならば、ＢＳはステップ208 でほぼＧ以下のスループット比を維持するようにスケジュールを決定する。スケジュールはステップ212 で適用され、処理はステップ202 へ戻り、例えばＤＲＣの次データレートリクエストメッセージのセットを受信する。
【００８２】
システム100 に適用可能な別のスケジュールアルゴリズムが図３に示されている。スケジュール方法250 はステップ252 で各ユーザの加重を初期化する。加重は優先順位インジケータであり、加重が大きい程、ユーザの送信の重要性を意味する。別の実施形態は加重の異なる重要性を構成する。加重はユーザにより選択されるサービスプランを含むがそれに限定されない種々ファクタにより決定されることができる。ステップ254 で、ＢＳは最小の加重を有するユーザを選択する。ＢＳはステップ256 でレートしきい値のＲthの値を計算し。決定菱形ブロック258 でＲthの値を選択されたユーザのレートと比較する。ＢＳはレートしきい値をデータを有するユーザに関連する瞬間レートの全ての平均としてレートしきい値を計算する。データを含まないユーザに関連する全ての瞬間レートは好ましくはこの計算で除去される。ＢＳはレートしきい値のＲthの値を選択されたユーザのレートと比較し、ユーザレートがしきい値Ｒthの値を超えるならば、ステップ260 でＢＳはこのユーザに関連される加重を、好ましくはビット、バイトまたはメガバイト等の単位で次のサービスインターバル中に送信されるデータの量を表す数である低い値だけ増加する。ユーザレートがしきい値Ｒthの値を超えないならば、ステップ262 で好ましくはビット、バイトまたはメガバイト量のような次のサービスインターバル中に送信されるデータの量の倍数“Ｋ”である高い値だけユーザの加重を増加する。
【００８３】
Ｋの選択は高いレートでデータを受信する能力を有する遠隔局またはユーザへのサービスインターバルの割当を好む公正基準に基づくことが好ましい。システム設計者は高いレートでデータを受信する遠隔局がより低速度で受信する遠隔局よりも好まれる程度に基づいてＫのサイズを選択する。Ｋ値が大きい程、使用されるＢＳの順方向リンクの効率は大きくなる。しかしながら、この効率は加入者から順方向リンクの送信リソースの低速度で受信するユーザを奪うことになる。それ故、システム設計者は好ましくは２つの競合する目的１）順方向リンクの全体効率の強化と、２）低速度で受信するユーザを奪うことの防止とを平衡する方法でＫの値を選択する。高速度の関連する瞬間データレート（即ちしきい値Ｒthの値を超過する）を有している選択されたユーザは少量だけ増加された関連する加重を有する傾向が高く、低いデータレート（即ちしきい値のＲthの値を超過しない）を有する選択されたユーザは非常に多量に増加された関連する加重を有する。図３の方法250 は低いデータレートでデータを受信する遠隔局よりも比較的高いレートでデータを受信するユーザをサービスすることを好む傾向が高い。この傾向は順方向リンクでのデータ送信でＢＳのスループットの効率を強化するが、高いレート（即ちしきい値Ｒthの値を超過する）のデータ受信を有するユーザに関連するしばしば選択された待ち行列に関する加重が増加され続けると、これらの加重は低いレート（即ちしきい値を超過しない）のデータ受信を有するユーザに関連する頻繁には選択されない待ち行列に関する加重に徐々に接近する。選択プロセスは高速度で受信するユーザの加重が低速度で受信するユーザの加重を超え始めたとき低速度で受信するユーザを好み始める。これは高速度で受信するユーザが低速度で受信するユーザを除外して基地局の順方向リンク送信リソースを占有することを防ぐことによって選択プロセスに公正制限を与える。
【００８４】
さらに別のスケジュール方法はアクチブセットの全てのユーザにわたって送信時間を等しくしようとする公正基準を有する比例公正スケジューラと呼ばれる。比例公正スケジュール方法にしたがって、ＢＳはデータレートＲi （ｔ）等の時間の関数として各ユーザｉに関連するパラメータを追跡する。ＢＳはアクチブセットの各ユーザからＤＲＣ情報を受信し、アクチブセットの各ユーザの以下の比を計算する。
ＤＲＣｉ／Ｒｉ                                                  （１４）
この比は効率的に現在のチャンネル状態を最近の過去と比較する。所定のユーザに対しては、ＤＲＣが高くパラメータＲが低いならば、ユーザは送信の良好な候補と考慮される。
【００８５】
減少されたＲ値はユーザが最近の過去の基地局からのデータ送信の受信者ではないことを示している。高いＤＲＣはユーザが良好なチャンネル状態を検出していることを示している。１実施形態によれば、ユーザパラメータＲの計算は次式により与えられる。
Ｒi （ｔ＋１）＝Ｒi （ｔ１）＊（１−１／Ｔc ）＋Ｄ＊（１／Ｔc ）
（１５）
ここでＤは予め定められた時間インターバルｔ中に受信されたデータレートを表し、Ｔc は考慮される最近のインターバルを表している。最近のデータレートは各ユーザの実際の状態を反映するためにさらに重く加重される。
【００８６】
図４Ａは前述の方法の組合わせを示しており、データレートしきい値は予め定められた時間期間内の瞬間値に適用され、ＧＯＳ基準は予め定められた時間期間により規定されたインターバルにわたって適用される。方法400 は最初にステップ402 でＧＯＳ時間期間を追跡するためにタイマを初期化する。タイマがステップ404 で期間を満了しないならば、即ち依然としてＧＯＳ時間期間内であるならば、処理は各ユーザの優先順位関数を決定するために図４Ｂのステップ420 へ継続する。例示的な実施形態では、優先順位関数はユーザのデータレートＲi （ｔ１）である。ステップ422 で、ＢＳは優先順位関数にしたがって勝者を選択し、データをステップ424 で送信する。データがステップ426 で依然として保留であるならば、処理はステップ420 へ戻り、そうでない場合には処理はこの時間期間で終了する。
【００８７】
図４Ａを続けて参照すると、タイマがステップ404 で満了したならば、即ちＧＯＳ時間期間が完了したならば、処理は他のユーザからＤＲＣを受信するためにステップ406 へ続く。ステップ408 でＢＳは送信されたビット数に基づいて各ユーザのスループットを決定する。比はその後、前述の式（１５）で示したように公正基準比例値Ｇと比較される。式（１３）の比がユーザｉとｊの任意の組合わせに対して式を満足しないならば、ステップ414 でＢＳは式（１３）の関係を実現またはほぼ実現するためにスケジュールを決定する。この場合、ＢＳは低いスループット値を有するユーザへの送信を典型的に増加する。このようにして、低いスループットを有するユーザと、高いスループットを有するユーザとの比は減少される。式（１３）が決定菱形ブロック410 で満足されるならば、ＢＳはステップ414 でほぼＧ以下のスループット比を維持するようにスケジュールを決定する。スケジュールはステップ416 で適用され、処理はステップ402 へ戻り、例えばＤＲＣのデータレートリクエストメッセージの次のセットを受信する。
【００８８】
図４Ａと４Ｂで示されている方法400 の特別な例が図５に与えられている。方法600 は最初にステップ602 で数Ｍのユーザ間の最小の加重を決定する。方法600 はさらにステップ604 で選択されたユーザのカラーＫを決定し、ステップ606 で（Ｍ＋Ｋ）を計算する。有効なＤＲＣを送信し、保留データを有するユーザでは、ユーザの加重が（Ｍ＋Ｋ）の計算された値よりも非常に小さいならば、処理はチャンネル状態に基づいてユーザを選択するようにステップ612 へ継続する。そうでなければ処理は最小の加重を有するユーザを選択するためにステップ610 へ継続する。選択されたユーザの加重はステップ614 で更新され、処理はステップ602 へ戻る。
【００８９】
もともとＨＤＲシステムの順方向リンク用に提案された１つのスケジュールアルゴリズムはＨＤＲエンコーダパケットの細分性により可能にされるような小さい時間期間にわたってサービスグレードの公正さを与える。サービスグレ−ドの公正さは幾らかの時間期間にわたって２人のユーザにより観察されたスループットがＧ：１の比だけ相互から異なることを意味するように規定されており、ここでＧ≧１である。同じことを説明する別の方法は長さｔの任意の時間期間にわたるそれを示すことである。
ｂA （ｔ）≦Ｇ* ｂB （ｔ）∀Ａ，Ｂ                            （１６）
ここでｂA （ｔ）とｂB （ｔ）はそれぞれ長さｔの時間期間にわたってユーザＡとＢにより受信されたビット数である。ＧＯＳスケジュールアルゴリズムは最初に待ち行列に関連する全ての加重をゼロの公称上の加重値に初期化する。アルゴリズムはその後、送信の待ち行列を選択し、選択された待ち行列からパケットを送信する。全ての加重はその後全ての待ち行列で更新される。アルゴリズムは送信のための次の待ち行列を選択する。
【００９０】
選択された待ち行列はエントリなしに初期化され、負の無限大の加重を与えられる。プロセスはその後次の待ち行列を考慮し、次の待ち行列が制御チャンネル送信が開始をスケジュールされる前にデータパケットの送信を完了するのに十分な時間があるか否かをチェックする。十分な時間があるならば、プロセスは別の待ち行列をチェックする。このプロセスは待ち行列が利用可能な時間で送信が完了できることを発見するまで継続する。アルゴリズムは現在の待ち行列の加重を選択された待ち行列の加重と比較する。現在の待ち行列の加重が選択された待ち行列の加重よりも小さいならば、アルゴリズムは現在の待ち行列を選択し、メモリにその加重を記憶する。そうでなければ、現在の待ち行列の加重が選択された待ち行列の加重と等しいならば、アルゴリズムは以下のチェック、即ち（ａ）現在の待ち行列は選択された待ち行列と少なくとも同程度の現在のスロットを使用することができるか？、（ｂ）現在の待ち行列の遠隔局は選択された待ち行列のレートよりも高いレートで受信することができるかのチェックを行う。両者の回答がイエスならば、アルゴリズムは現在の待ち行列を選択し、関連する加重をメモリに記憶する。プロセスは全ての待ち行列で反復される。データが保留中であるならば、この点では選択された待ち行列は存在しない。
【００９１】
比例公正アルゴリズムはセクタのスループットをアクチブユーザの数の増加と共に増加させる。ＧｏＳアルゴリズムはこの特性をもたない。この差は公正さが維持される時間スケールにより生じる。比例公正方式は平均スループット計算器の時定数よりも短い時間スケールでは公正さを保証しない。その結果として、チャンネル状態の変化を使用するため短い時間期間にわたって異なるユーザへ送信を再度アレンジするためのフレキシブル性を有する。せいぜいこれらの時間期間はパケット遅延が顕著な影響を受けないような十分な短さである。
【００９２】
しかしながら、比例公正アルゴリズムはまたサービスグレードスケジューラから公正さの概念を変更する。即ち最悪の場合、個人のユーザに対するビットレートの比はリクエストされたレートの最大の比（ＨＤＲシステムの１実施形態では６４：１）と同じ大きさである。これは望ましくない。スループットを増加するために短期間にわたってチャンネル変化を利用するが長い時間にわたってサービスグレードの公正さを維持することが望ましい。
【００９３】
前述したように、公正さのＧｏＳ概念に基づくスケジューラは通常、式（１６）が全ての時間インターバルで満足されることを確実にする。定数値Ｃを含むための式（１６）の変形は次式を生む。
ｂA （ｔ）≦Ｇ* ｂB （ｔ）＋Ｃ∀Ａ，Ｂ                        （１７）
延長された時間インターバルにわたって、即ち大きなｔ値で、インターバルｂA （ｔ）とｂB 中に送信されたビット数はＣと比較して非常に大きい。ｔが無限大になる限界では、新しいルールは古いルールに減少される。これは長期間にわたってサービスグレードの公正さを与える。しかしながら短時間の期間ではユーザＡおよびＢに送信されるビット数は任意の比を有する。したがってＣを慎重に選択することによって、システムはどの時間期間が短く、どの時間期間が長いかを決定するように設計されることができる。これは短時間の期間においてはＧｏＳ公正度基準を犯す自由を許容し、それ故システムはスループットを最大にするために自由に任意の方式を使用する。ここで説明された修正されたアルゴリズムは、それぞれ１つ１つがこの自由を使用することによって性能を最適化し、さらにそれぞれがどのように値Ｃを決定するかについて相互に異なっている。
【００９４】
しかしながら、ここで説明したＧｏＳアルゴリズムと類似した方法で行われる代わりのスケジュールアルゴリズムは、パラメータまたは定数値Ｃを選択手順に導入することによってユーザ選択プロセスの実行に応じて異なる可能性がある。前述したように、１実施形態ではＧｏＳアルゴリズムは有効なＤＲＣメッセージを有するユーザ間で、変数Ｍにより識別される最小の加重を有するユーザを選択する。別の実施形態では、スケジュールアルゴリズムは最小の加重のユーザの周辺で定数値Ｃにより規定される範囲内、即ちＭ＋Ｃとして規定される範囲内の加重を有するユーザを選択する。換言すると、アルゴリズムは最小の加重に関するマージンを構成する。規定の範囲内、即ち（Ｍ＋Ｃ）により規定される加重の範囲内の加重を有するユーザのセットが決定される。この範囲内の選択プロセスはＤＲＣ値またはその関数等のリクエストされたデータレートを含むがそれに限定されない別の基準に基づいていてもよい。種々の実施形態は類似のスケジュール方法を実行することが可能であり、個々のスケジュール方式はこのセットからのユーザの選択に使用される方法に関して異なっていてもよい。最小の加重のユーザは保留中のデータのないアクチブユーザおよび無効のＤＲＣメッセージを有するアクチブユーザを含む全てのアクチブユーザのセットで最小の加重を有するユーザである。したがってこのユーザセットには保留中のデータおよび有効なＤＲＣを有するユーザはいない可能性があり、残りのユーザの中で最小の加重を有するユーザ、即ち（Ｍ＋Ｃ）よりも大きい加重を有するアクチブセットのユーザは送信のために選ばれる。
【００９５】
図８は１実施形態にしたがったスケジュールアルゴリズム900 を示しており、この方法はステップ902 で最小の加重Ｍのユーザまたは待ち行列を決定する。範囲値Ｃはステップ904 で決定され、その値は別の選択基準が使用されてもよい加重の範囲を規定するために使用される。ステップ906 で、方法はＭ＋Ｃ等の範囲を計算し、ステップ908 でその範囲のユーザのグループを決定する。グループ中の少なくとも１人のユーザが保留中のデータと有効なＤＲＣメッセージを有するならば、処理はグループから次のユーザを選択するためにステップ914 へ進行する。グループに保留中のデータと有効なＤＲＣメッセージを有するユーザがいないならば、グループはＭ＋Ｃの範囲により規定されたグループに含まれないユーザとして規定される。換言すると、グループはステップ912 でＭ＋Ｃよりも大きい加重を有するユーザセットとして再度規定され、処理は908 へ戻る。グループの少なくとも１人のユーザが保留中のデータと有効なＤＲＣメッセージを有するならば、処理はグループから次のユーザを選択するためにステップ914 へ移行する。アクチブセット中に保留中のデータと有効なＤＲＣを有するユーザがいないならば、送信は処理されないことに注意する。ユーザまたは待ち行列をグループから選択するために使用される基準は所望性メトリックと呼ばれる。
【００９６】
１実施形態では値Ｃはユーザの数にかかわりなく定数である。比例公正タイプのアルゴリズムに類似して、各ユーザへの平均スループットの濾波されたバージョンは所望性メトリックとして実行される。例えば１実施形態にしたがって、所望性メトリック現在のリクエストされたデータレートから所定のユーザの平均スループット値を引いた数として規定される。
【００９７】
別の実施形態によれば、Ｃは定数であり、所望性メトリックは現在のリクエストされたデータレートに等しい。この方法は高いＤＲＣ値を適用する変形されたＧｏＳアルゴリズムと呼ばれる。
【００９８】
別の実施形態によれば、Ｃは定数であり、各ユーザへの平均スループットの濾波されたバージョンは比例公正タイプアルゴリズムのように維持される。この実施形態では、所望性メトリックは平均スループットにより割算された現在のリクエストされたデータレートに等しく設定される。
【００９９】
さらに別の実施形態によれば、Ｃの値は（１／アクチブユーザ数）に比例する。各ユーザへの平均スループットの濾波されたバージョンは比例公正方式に同一の方法で維持され、所望性メトリックは平均スループットにより割算された現在のリクエストされたデータレートに等しく設定される。
【０１００】
１実施形態では、スケジュールアルゴリズムは基地局820 から遠隔局までの送信をスケジュールするために図７のチャンネルスケジューラ812 を制御する。前述したように、データの待ち行列830 は各遠隔局に関連される。チャンネルスケジューラ812 は各データ待ち行列830 に、次のサービスインターバルでデータを受信するために基地局820 に関連する特定の遠隔局を選択するように評価される“加重”を割当てる。チャンネルスケジューラ812 はディスクリートなサービスインターバルでデータ送信を受信するための個々の遠隔局を選択する。チャンネルスケジューラ812 は最初に基地局820 に関連する各待ち行列の加重を初期化する。
【０１０１】
チャンネルスケジューラ812 は一連の送信インターバルまたはサービスインターバルを循環する。チャンネルスケジューラ812 は、付加的な遠隔局６と先のサービスインターバル中に検出された基地局820 との関連により付加される任意の付加的な待ち行列が存在するか否かを決定する。チャンネルスケジューラ812 はまた新しい待ち行列に関連する加重を初期化する。前述したように、基地局820 はタイムスロット等の規則的なインターバルでそれに関連する各遠隔局からＤＲＣ信号を受信する。
【０１０２】
本発明の例示的な実施形態は種々のスケジュールアルゴリズムに応用可能であり、種々の公正度の基準を実現するのに有効である。図６はチャンネル状態を最初に評価し、ステップ702 でチャンネル状態インジケータを準備する例示的な実施形態のスケジュール方法700 を示している。公正インジケータがステップ704 で選択される。公正インジケータは実行されるスケジュール方法の公正さを評価するために使用されるメトリックである。保留中のデータまたは不適切なチャンネル状態をほとんどもたないユーザに対して遅延を生じさせずにスループットを最大にすることによってシステムリソースを最適にすることが望ましい。さらに、方法は各ユーザのクラスにしたがってサービスを提供する。公正度基準は以下のタイプ、即ち：１）チャンネル状態およびスループットの関数としての比例公正方法、２）スループットおよびユーザの優先順位の関数としてのパケットごとの一般化されたプロセサ共有（ＰＧＰＳ）方法、３）サービス時間の関数としての均一時間方法、４）スループットの関数としてのＧＯＳ方法、５）待ち時間および完了までのデッドラインの関数としてのサービス時間方法を含んでいるが、これらに限定されない。
【０１０３】
続いて図６を参照すると、ステップ706 で、方法700 はスループットの関数として公正度インジケータ値を決定する。ステップ708 で、各ユーザはチャンネル状態インジケータと公正度インジケータの関数として評価される。スケジュールはステップ708 の評価に基づいて決定され、スケジュールはステップ710 において適用される。例示的な実施形態にしたがって、種々の方法はチャンネル状態評価に利用可能であり、それ故、チャンネル状態インジケータと公正度インジケータの多数の組合わせがスケジュールで使用するのに有効である。
【０１０４】
図７は基地局制御装置ＢＳＣの部分810 と、ネットワークと通信中のＢＳ部分820 とを含んでいるシステム800 を示している。ネットワークはそれぞれネットワークパケットインターフェース806 と通信しているデータソース802 とデータシンク804 を含んでいる。さらに、ネットワークは公共交換電話網ＰＳＴＮ 808を含んでいてもよい。ＢＳＣ 810はチャンネルスケジューラ812 、公正セレクタ814 、セレクタ素子816 、呼制御プロセッサ818 を含んでいる。パケットネットワークインターフェース806 はセレクタ素子816 と呼制御プロセッサ818 へ結合されている。呼制御プロセッサ818 はシステム800 内のユーザのアクチブセットの変化に作用する。セレクタ素子816 は通信に対するターゲットの関係者を決定し、適切な接続を行う。セレクタ素子816 はＢＳ 820へも結合されている。公正セレクタ814 はＢＳＣ 810が所望の公正基準を実行し、情報をチャンネルスケジューラ812 へ提供することを可能にする。公正セレクタ814 はまたＢＳ 820から公正度インジケータ目的地を受信する。
【０１０５】
ＢＳ 820はチャンネルスケジューラ832 を含んでおり、これは次のデータ送信のための選択されたユーザについての情報をチャンネル素子826 に提供する。ＢＳ 820はさらにデータ待ち行列830 、ＲＦ装置828 、公正セレクタ824 、マイクロプロセッサ822 を含んでいる。公正セレクタ824 は図６に示されている方法700 を実行する。
【０１０６】
前述したように、例示的な実施形態は多数のユーザが優先順位方式または他の方式にしたがって区分されることを可能にする。２つのユーザセットをサポートするシステムを考慮する。第１のセットは遅延要求を有し、第２のセットは単に最善の努力のサービスを必要とする。第１のセットの遅延要求は予め定められた遅延量よりも少ない遅延量で送信が行われることを示し、それ故第２のセットよりも高い優先順位のセットである。例示的な実施形態ではユーザｉは第１のセットのメンバである。ユーザｉは順方向リンクまたはダウンリンクでの送信の予め定められた遅延ｄi よりも少ないパケット遅延を特定し、ユーザｉは予め定められたレベルのフレキシブル性ｆi で遅延を実行する。第２のユーザセットには等しい時間方法でスロットへのアクセスが行われる。第１および第２のユーザセットをスケジュールするために、所望のスケジューラが多数のユーザダイバーシティを行い、異なる方法で各異なるユーザの要求を満足する。例を明白にするために、チャンネル状態メトリックは変更されない。
【０１０７】
第１のステップは適切なユーザ公正さメトリックを決定することであり、ユーザの公正さメトリックは２つのクラスのユーザで異なる関数により記述される。さらに制約は第１および第２のセットの両者が所望の動作点で同一の数値を生じることである。例えば次式のユーザ公正さメトリックを考慮する。
Ｕi （ｔ）＝（ｄi ＋ｆi −Ｗi （ｔ））／ｆi                    （１８）
ここでＷi （ｔ）は保留中のデータのユーザｉの待ち行列の時間ｔにおいて最長の時間待機しているデータパケットが受けた遅延である。この関数はパケットの遅延がｄi であるときに値１を取り、遅延がｄi ＋ｆi 、即ち所望の遅延範囲内にあるときにゼロになる特性を有する。目標は遅延をｄi を維持するが、これがｄi ＋ｆi 程度の高さになる、即ち所望の遅延範囲内にあることを可能にすることである。
【０１０８】
第２のユーザセットでは、例示的な実施形態は等しい時間のスケジュールを全てのユーザに提供することによってデータパケットの遅延に関して最善の努力を与える。等しい時間スケジュールを実現するために、方法は次式のようなユーザ公正さメトリックを使用する。
Ｕi （ｔ）＝ｎ* ｆｒａｎｃi （ｔ）                              （１９）
ここでｎは（両セットの）セクタのユーザの総数であり、ｆｒａｎｃi （ｔ）はこのユーザにサービスするために使用されるスロットの割合である。ｆｒａｎｃi （ｔ）の値は適切な時定数のＩＩＲフィルタを通過することにより計算される。このメトリックの公称値は各ユーザに対して１であるが、実現される実際の値は最近のチャンネル状態と、ユーザの他のセットの存在に基づいている。ユーザがサービスされていないとき、このメトリックは第１のユーザセットに対して規定されているメトリックよりも時間の経過と共に非常に低速度に落ちることに注意する必要がある。
【０１０９】
ユーザのこのメトリックの低い値はそのユーザに高い優先順位を与える。このことは各セットから１人づつの２人のユーザがユーザ公正さメトリックの公称値にある（即ちユーザの公正さが１に等しい）ことを示唆するが、スケジューラが別のカスタマをサービス中であるので彼等はサービスを受けられず、第１のセットからのユーザに対するユーザ公正さメトリックスは急速に低下し、第２のセットからのユーザよりも早期にスケジューラからサービスを受ける。第１のユーザセットが満たすのが厳しいデッドラインを有しながら第２のユーザセットは最善の努力のサービスだけを必要とするので、この行為は正しい。
【０１１０】
先に詳細に説明した例を考慮すると、適切なユーザ公正さメトリックの決定を容易にする幾つかの差を識別することが可能である。時定数Ｔｃは短く維持されなければならず、Ｔｃよりも大きい時間スケールのユーザの要求を処理および考察することを可能にする。
【０１１１】
各スケジュールは公称動作点を有していてもよく、スケジューラは各ユーザに対してユーザ公正さメトリックの同じ公称値を実現するようにサービスするようにユーザをスケジュールする。メトリックは異なるユーザの要求の差を考慮するように規定される。別の考察は公称上の動作点周辺の勾配に受信されたサービスの関数として公正さの増加を示させることである。公正さは低い優先順位のサービスを有するユーザを犠牲にして高い優先順位のサービスを有するユーザを好む傾向が高い。１実施形態によれば、受信されるサービスの関数としてのユーザ公正さメトリックの勾配はサービスの優先順位の減少と共に常に負である。１／（ユーザ公正さメトリック）の感度は各ユーザの要求により可能にされるフレキシブル性を考慮する。
【０１１２】
図７で示されているように無線通信システムへ一般化されたスケジューラを構成するために、公正基準およびチャンネル状態基準をチャンネルスケジュール関数に適用する。例えばチャンネル状態メトリックを実行するためにはチャンネルフィードバック機構を設けることが含まれている。フィードバック機構はユーザにより与えられるＤＲＣ等の明白なインジケータでもよく、またＣ／Ｉ尺度等の盲目的なインジケータであってもよい。チャンネル状態インジケータと評価およびスケジュールに使用される方法はシステムに特有である。チャンネル状態インジケータは先の説明のインジケータに限定されるものではなく、ここで詳細に説明されたチャンネル状態インジケータは理解を明白にするために例として与えられたものである。チャンネル品質の確実な尺度を有することが望ましい。
【０１１３】
同様に、ユーザ公正さメトリックの信頼できる尺度を有することが望ましい。ＢＳがユーザへの送信を開始し処理するとき、ＢＳは所定の時間期間に所定のユーザに送信されるビットまたはパケット数の十分な知識を有している。ＢＳはこの情報をスループット、正確性、公正さを評価するのに使用する。公正さメトリックはそれが適用するシステムの関数であり、それ故、前述の公正さメトリックに限定されない。
【０１１４】
明白には前述していないが、同時の多数のユーザのサービスを阻止する有効な制限は存在しない。一般化されたスケジューラはｆ（Ａi （ｔ），Ｕi （ｔ））の減少する順序でユーザをランクすることができ、サービスされるリスト中の第１のユーザが残りの容量をサービスに残しておくならば、これは同時に次のユーザをサービスできる。１よりも多数のユーザの並列処理は帯域幅の使用を最大にし、全体としてシステムのスループットを最適化する。
【０１１５】
図４Ａは前述の方法の組合せを示しており、データレートのしきい値は予め定められた時間期間内の瞬間値に適用され、ＧＯＳ基準は予め定められた時間期間により規定されるインターバルにわたって適用される。方法400 は最初にＧＯＳ時間期間を追跡するためにステップ402 でタイマを初期化する。タイマがステップ404 で満了していないならば、即ち依然としてＧＯＳ時間期間内であるならば、処理は図４Ｂのステップ420 へ進み、各ユーザの優先順位関数を決定する。例示的な実施形態では、優先順位関数はユーザのデータレートＲｉ（ｔ）である。ステップ422 で、ＢＳは優先順位関数にしたがって勝者を選択しステップ424 でデータを送信する。データがステップ426 で依然として保留中であるならば、処理はステップ420 へ戻り、そうでなければこの時間期間で処理は終了する。
【０１１６】
図４Ａを続いて参照すると、タイマがステップ404 で満了したならば、即ちＧＯＳ時間期間が完了したならば、処理は他のユーザからＤＲＣを受信するためにステップ406 へ進む。ステップ408 でＢＳは送信されたビット数に基づいて各ユーザのスループットを決定する。比はその後前述の式（１３）で与えられているように公正さ規準比例値Ｇに比較される。式（１３）の比がユーザｉとｊの任意の組合わせに対して式を満足しないならば、ステップ414 で、ＢＳは式（１３）の関係を実現またはほぼ実現するようにスケジュールを決定する。この場合ＢＳは典型的に低いスループット値を有するユーザへの送信を増加する。このようにして、最低のスループットを有するユーザと最高のスループットを有するユーザとの比は減少される。式（１３）が決定菱形ブロック410 で満足されるならば、ＢＳはステップ414 でほぼＧ以下のスループット比を維持するようにスケジュールを決定する。スケジュールはステップ416 で適用され、処理は例えばＤＲＣ等のデータレートリクエストメッセージの次のセットを受信するためにステップ402 へ戻る。
【０１１７】
図４Ａと４Ｂで示されている方法400 の特別な例は図５で与えられている。その方法600 は最初にステップ602 で数Ｍのユーザ間の最小の加重を決定する。方法600 はさらにステップ604 で選択されたユーザのカラーＫを決定し、ステップ606 で（Ｍ＋Ｋ）を計算する。有効なＤＲＣを送信し、保留中のデータを有するユーザに対しては、ユーザの加重が（Ｍ＋Ｋ）の計算された値よりも非常に小さいならば、処理はチャンネル状態に基づいてユーザを選択するためステップ612 に継続する。そうでなければ、処理は最小の加重を有するユーザを選択するためにステップ610 に継続する。選択されたユーザの加重はステップ614 で更新され、処理はステップ602 に戻る。
【０１１８】
もともとＨＤＲシステムの順方向リンクに対して提案されていた１つのスケジュールアルゴリズムはＨＤＲエンコーダパケット細分性により可能にされる程度の小さい時間期間にわたってサービスグレ−ドの公正さを提供する。サービスグレードの公正さは幾らかの時間期間にわたって２人のユーザにより観察されるスループットがＧ：１の比だけ相互から異なることを意味するように規定されており、ここでＧ≧１である。同じことを説明する別の方法は長さｔの任意の時間期間の長さｔにわたってそれを示すことである。
ｂA （ｔ）≦Ｇ* ｂB （ｔ）∀Ａ，Ｂ                            （２０）
ここでｂA （ｔ）とｂB （ｔ）はそれぞれ長さｔの時間期間にわたってユーザＡとＢにより受信されたビット数である。ＧＯＳスケジュールアルゴリズムは最初に待ち行列に関連する全ての加重をゼロの公称上の加重値に初期化する。アルゴリズムはその後、送信の待ち行列を選択し、選択された待ち行列からパケットを送信する。全ての加重はその後全ての待ち行列で更新される。アルゴリズムは送信のための次の待ち行列を選択する。
【０１１９】
前述したように、例示的な実施形態はチャンネル状態インジケータと公正度インジケータを適用することにより多数のユーザ間で送信をスケジュールする方法を提供する。１例として、例示的な実施形態にしたがって一般化されたスケジューラのフレームワークの比例公正スケジューラを考慮する。式（１）の関数ｆ( ) は簡単な割算演算子として規定される。チャンネル状態メトリックＲｉ（ｔ）は次式で与えられている。
Ｒｉ（ｔ）＝ＤＲＣi （ｔ）／ａｖｅｒａｇｅ ＤＲＣi （ｔ）      （２１）
ユーザ公正メトリックは次式のように与えられる。
Ｕｉ（ｔ）＝ａｖｅｒａｇｅ ｔｈｒｏｕｇｈｐｕｔi （ｔ）
／ａｖｅｒａｇｅ ＤＲＣi （ｔ）                    （２２）
式（１）を考慮すると、結果的な方法は最高のＤＲＣi （ｔ）／ａｖｅｒａｇｅ ｔｈｒｏｕｇｈｐｕｔi （ｔ）を有するユーザにサービスし、これは比例公正スケジューラである。この場合、全ての平均化は予め定められた時定数を有する無限インパルス応答ＩＩＲフィルタを使用して行われる。先に与えられた式の検査により、多数のユーザダイバーシティ利得がチャンネル状態メトリックの関数であり、即ちチャンネル状態メトリックにより導入されることが明らかになった。ＤＲＣが各ユーザに対して平均化される時間期間はチャンネル状態メトリックの分母の計算に使用される。ユーザ公正メトリックはアルゴリズムの実際の公正さを与える。各ユーザのチャンネル状態メトリックは約１の値を与えられる。長期間にわたって異なるユーザにより受信されるスループットの相対値はチャンネル状態メトリックではなく主としてユーザ公正メトリックにより影響される。特に、ユーザにより実現される相対的なスループットは各ユーザの公正メトリックが同一値を実現するようにされている。
【０１２０】
さらに、所定のユーザに対するユーザ公正メトリックは次式のように書換えられる。
Ｕｉ（ｔ）＝（fraction of slots served）* 
（ＤＲＣａｖｅ while served ／ＤＲＣａｖｅ）          （２３）
（ｄＢによる）全てのユーザのＤＲＣがほぼ中間値の同一の統計値で変化する場合には、ＤＲＣａｖｅ ｗｈｉｌｅ ｓｅｒｖｅｄとＤＲＣａｖｅの比は全てのユーザに対して同一であり、アルゴリズムの等時間特性を与える。
【０１２１】
比例公正スケジューラ式を書換える利点は均一時間スケジューラを得ることである。この均一時間スケジューラは多数のユーザダイバーシティにより利得を有する。チャンネル状態メトリックは比例公正アルゴリズムにしたがったのと同一であるが、ｆｒａｃｔｉｏｎ ｏｆ ｓｌｏｔｓ ｓｅｒｖｅｄにより規定されたユーザ公正メトリックの適用により各ユーザへ等しい時間を保証する。１実施形態では、この割合は比例公正アルゴリズムで現在使用するのと同一の時定数を有するＩＩＲフィルタを使用して平均される。
【０１２２】
さらに、前述したように、例示的な実施形態は区分方式にしたがって個々のユーザまたはユーザのグループにおける処理の区分化を可能にする。このようにして異なるユーザは異なるユーザ公正メトリック値を割当てられる。ユーザクラスｊに対するユーザ公正メトリックが次式のように規定されるならば、即ち、
Ｕｉ（ｔ）＝ａj * ａｖｅｒａｇｅ ｔｈｒｏｕｇｈｐｕｔi （ｔ）
／ａｖｅｒａｇｅ ＤＲＣ（ｔ）                        （２４）
ここでユーザクラスｊは他のユーザクラスと比較して（１／ａj ）に比例する相対的な優先順位を受ける。例えばＧＯＳアルゴリズムの一般化されたスケジューラへの適用を考慮すると、チャンネル状態メトリックはいつでも全てのユーザに対して１であり（即ちアルゴリズムは多数のユーザダイバーシティを使用しない）ユーザ公正メトリックはユーザに割当てられた加重である。セクタのスループットを最大にしながらＧＯＳ公正さを実現する方法で加重が割当てられたことを思い出されたい。結合関数は式（１０）で与えられた割算演算子である。この例はｆ、Ａi （ｔ）、Ｕi （ｔ）の異なる選択が同一のアルゴリズムに作用することを示している。換言すると、優先順位関数が評価されるとき、結果的なアルゴリズムはｆ、Ａi （ｔ）、Ｕi （ｔ）の異なる組合わせに対して同一である。例えばｆ( ) が異なる演算子であり、即ちｆ（ａ，ｂ）＝ａ−ｂであることを考慮し、チャンネル状態メトリックをゼロとしてユーザ公正メトリックを加重とする。結果は現在サービスされているユーザが最低の加重を有するユーザであるときＧＯＳアルゴリズムに接近する。
【０１２３】
変形されたサービスグレードアルゴリズムでは、カラーと呼ばれるパラメータが使用され、マージンまたは最小の加重値の範囲内、即ちｍｉｎ ｗｅｉｇｈｔ  ｔｏ（ｍｉｎ  ｗｅｉｇｈｔ＋ｃｏｌｌａｒ）の加重を有する全てのユーザはチャンネル状態に基づいてサービスされる。その範囲内に送信を保留中のデータを有するか有効なＤＲＣを送信するユーザが発見されないならば、方法はユーザ間で最小の加重を有するユーザを選択する。ユーザ公正メトリックはその後、範囲内、即ちｍｉｎ ｗｅｉｇｈｔとｍｉｎ ｗｅｉｇｈｔ＋ｃｏｌｌａｒとの間および全ての他のユーザで無限の範囲内で加重を有する全てのユーザのうち１人に規定される。種々のチャンネル状態メトリックは１）ＤＲＣと２）ＤＲＣ／ＤＲＣａｖｅを含むがそれに限定されない例示的な実施形態への適用に使用されてもよい。
【０１２４】
強化された均一時間スケジューラは均一時間スケジューラに基づいて開発される。１実施形態にしたがって、時定数Ｔｃは強化された均一時間スケジューラ方法でユーザ公正メトリックに関連される。時定数Ｔｃを予め定められた数のスロットに等しく規定することは送信制御プロトコルＴＣＰタイプのシミュレーションの経験に基づいており、ここでのＴｃよりも小さい時間スケールにわたるスループット変化は重要ではない。しかしながら異なるユーザは現在行っているアプリケーションに基づいて適用された時間スケールに異なるフレキシブル性を有することが可能である。１実施形態ではユーザ公正メトリックは１人のユーザ当りまたはユーザのグループ当りの平均スループットを計算し続け、ユーザ公正メトリックの計算はユーザ当りの平均を計算するのに個々の、即ち異なる時定数を使用する。ユーザ当り異なる時定数を使用することによってユーザ当りのスロットのほぼ平均的な割合で異なる変化が生じる。小さい変化は小さい時定数の適用により経験される。ユーザ当りのスロットの割合はほぼ等しく維持される。類似の強化は他のユーザ公正メトリック、例えば比例公正スケジューラ（ａｖｅｒａｇｅ ｔｈｒｏｕｇｈｐｕｔ／ａｖｅｒａｇｅ ＤＲＣ）により使用されるメトリックで可能である。優先順位関数ｆ( ) の適用は各個々のユーザのスループットに関して異なった変動性を与える。
【０１２５】
システム120 のＨＤＲ動作では、ＡＮ 122とＡＴ 126はそれぞれ信号処理モジュールに加えてプロセッサと少なくとも１つのメモリ記憶装置を含んでいる。プロセッサは中央処理装置または専用の制御装置である。メモリ記憶装置はコンピュータ読取り可能な命令および／または無線システム120 内で通信を制御するためのルーチンを記憶する。ＡＮ 122内で、メモリ記憶装置はデータ送信を制御するための命令を記憶する。ＡＴ 126内で、メモリ記憶装置はデータリクエストを含むデータ送信を制御する命令を記憶する。
【０１２６】
１実施形態では、無線通信システムはリクエストされたデータレートよりも高い実際の受信されたデータレートを生じる送信プロトコルをサポートする。１つのこのようなシステムはＡＲＱ方式を実行するＨＤＲシステムである。このようなシステムでは、ユーザはＤＲＣメッセージのようなデータレートリクエストメッセージを基地局またはアクセス端末のような送信機に送信する。ＤＲＣメッセージはリクエストされたデータの送信に必要なスロットの総数を示している。送信機はＤＲＣメッセージで示されているスロットの総数よりも少ないスロットでデータを送信する。受信機がスロットの総数よりも少ないスロットで情報を復号できるならば、受信機は応答メッセージを送信機へ送信し、送信機は送信を終了する。そうでなければ、送信機は応答を受信していないならば、送信は継続し、応答が受信されないならば識別された総数のスロットで送信するように進行する。
【０１２７】
受信データレートがリクエストされたデータレートと異なるとき、システム設計者は目的をスケジュールするために実際の受信されたデータレートを使用することを望む。このレートが送信機によって演繹的に知られていないときに受信されたデータレートの決定に問題が存在するが、むしろ送信プロセス中のもとの場所で決定される。換言すると、送信機はＤＲＣ等のリクエストされたデータレートを知っており、送信がＤＲＣにより識別される全てのスロットを必要とすることを理解して受信機へ送信を開始する。送信機は受信機が応答メッセージを送信するとき、さらに少数のスロットで受信機が送信を受取ることができることを発見する。これは典型的にスケジュールアルゴリズムが選択を決定した後である。結果的に、ＡＲＱタイプの方式で物理層をサポートする無線通信システムはＤＲＣによりリクエストされるレートと実際の受信されたレートとを分断する。スケジュールの公正さはＤＲＣが送信ターゲットの選択に使用されるときに影響を受ける。
【０１２８】
１例として、２つのアクセス端末ＡＴ１とＡＴ２を有するシステムを考える。ＡＴ１は３０７．２ｋｂｐｓのレートで全体で２のスロットによってデータをリクエストし、ＡＴ２は６１４．４ｋｂｐｓのレートで全体で１のスロットによってデータをリクエストする。比例公正タイプのスケジュールアルゴリズムを適用すると、ＡＴ１とＡＴ２は等しい時間に対してスケジュールされ、ＡＴ１のスループットはＡＴ２のスループットの半分であり、即ちＡＴ１のスループットは１５３．６ｋｂｐｓであり、ＡＴ２のスループットは３０７．２ｋｂｐｓである。ＡＴ１が１つのスロット送信がいつでも受信されるようになった後応答メッセージを送信するならば、ＡＴ１の受信されたレートは６１４．４ｋｂｐｓである。それ故、ＡＴ１のスループットは２０４．８ｋｂｐｓ即ち６１４．４ｋｂｐｓの３分の１であり、ＡＴ２のスループットは４０９．６ｋｂｐｓ即ち６１４．４ｋｂｐｓの３分の２である。公正さ基準は違反される。ユーザはリクエストされたレートではなく実際の受信されたレートに比例するスループットを得ることが所望される。ＡＲＱタイプの方式が低いデータレートを有するユーザのデータレートに恩恵を与える可能性が高いので、典型的な比例公正タイプのアルゴリズムは全てのユーザへシステムリソースを再分配することによりその恩恵を打消す。
【０１２９】
前述の１実施形態は公正比例タイプのアルゴリズムをＧｏＳタイプのスケジューラと結合することによりこの問題を解決する。短い時間インターバルに対して、組合わせプロセスは公比例タイプのアルゴリズムを使用し、長い時間インターバルにわたってＧｏＳ制約を適用する。ＧｏＳ公正規準は予め定められた期間にわたって送信されるビットまたはバイトの総数を評価するので、実際にリクエストされたデータレートは選択プロセスへ直接的に入らない。
【０１３０】
等しくないＧｏＳアルゴリズムでは、高および低の２つのグレードが与えられる。各ユーザは前述したように加重を割当てられる。高いグレードのユーザがサービスされるとき、即ちデータ送信の受信者であるとき、ユーザの加重は１のような予め決められた値だけ増加される。低いグレードのユーザがサービスされるとき、ユーザの加重は調節された量だけ増加され、この調節された量は利得係数Ｇにより調節された予め定められた値である。所定のユーザはリクエストされたデータレートと平均スループットに応じてグレードを変化する。しきい値のスループット値を超えるユーザは高いグレードを割当てられ、平均スループット値を上げることを意図される。しきい値を下回るユーザはスループットへの影響を最小にするために低いグレードを割当てられる。しきい値はＧｏＳタイプのスケジューラを使用して実現可能な論理的平均スループットを決定するためにＤＲＣを使用してスロット当りで計算される。計算はチャンネル変化を無視する。
【０１３１】
比例公正アルゴリズムに対して前述したように、ＤＲＣが実際の受信されたデータレートと異なるときにＧｏＳアルゴリズムに問題が存在する。１実施形態ではＩＩＲフィルタを使用してセクタ当りの実際の平均スループットを追跡することによりその問題を解決する。フィルタの時定数はシミュレーションによりまたは動作により決定される値に固定される。この実施形態にしたがって、所定のセクタまたはセルのスループットは次式により規定される。
Ｔ［ｎ＋１］＝Ｔ［ｎ］* （１−α）＋α* Ｒ［ｎ］                （２５）
ここでＴはしきい値であり、Ｒは時間インスタンスｎにおけるサービスレートであり、またαは予め定められた値である。スループットはその後、高および低グレードのユーザを割当てるためのしきい値として使用される。
【０１３２】
変更された前述したＧｏＳタイプのスケジュールアルゴリズムを適用しながら多数ユーザダイバーシティをさらに利用するために、１実施形態は予め定められた時間期間を適用する。この時間期間内で、プロセスは多数ユーザダイバーシティを使用し、時間期間にわたってＧｏＳタイプのスケジュールアルゴリズムが適用される。この方法は対応するＤＲＣをＩＩＲフィルタを通過させることにより各ユーザのリクエストされたデータレートの最近の平均を追跡する。各ユーザに対しては、比は最近の平均的なリクエストされたデータレートに対する現在のＤＲＣとして計算される。最高の比を有するユーザがサービスを受ける。別の実施形態では、全ての加重が予め定められた範囲内の値であるならば、最高の比を有するユーザがサービスを受ける。ＤＲＣ値が比の分子と分母の部分であるとき、選択プロセスはリクエストされたレートではなく実際の受信されたデータレートを反映していると予測される。
【０１３３】
さらに別の実施形態は比例公正タイプのスケジュールアルゴリズムの修正によって、リクエストされたデータレートと受信されたデータレートとの間の不一致を解決しようとする。比例公正タイプのアルゴリズムはリクエストされたデータレートと、ユーザ当りの平均スループットの比に基づいており、最高の比を有するユーザがサービスを受けるように選択される。平均スループットは以下のように計算される。
Ｔave ［ｎ＋１］＝Ｔave ［ｎ］* （１−α）＋α* Ｒ［ｎ］        （２６）
ここで、Ｔave は平均しきい値であり、Ｒは時間インスタンスｎにおけるサービスレートであり、αは予め定められた値である。以下に規定されているように修正によってスループットの値が変更される。
【０１３４】
Ｔave ［ｎ＋１］＝Ｔave ［ｎ］* （１−α）＋α* ＤＲＣ［ｎ］      （２７）
平均しきい値を計算するためのＤＲＣの適用は実際の受信されたスループットよりも潜在的に低い平均しきい値を生成する。リクエストされたデータレートと平均スループットの比の分母を減少することにより、比の値は増加され、したがって所望の効果が得られる。
【０１３５】
以上、通信システムで送信をスケジュールする優秀で改良された方法および装置を説明した。当業者は先の説明を通じて参照されたデータ、命令、コマンド、情報、信号、ビット、シンボル、チップが電圧、電流、電磁波、磁界または粒子、光フィールドまたは粒子或いは任意のその組合わせにより有効に表されることを理解するであろう。当業者はさらにここで示した実施形態を伴って説明した種々の例示された論理ブロック、モジュール、回路、アルゴリズムステップが電子ハードウェア、コンピュータソフトウェア、またはその両者の組合わせとして構成されることを認識するであろう。種々の例示されたコンポーネント、ブロック、モジュール、回路、ステップをそれらの機能に関して一般的に説明した。機能がハードウェアとして実行されるか、またはソフトウェアとして実行されるかはシステム全体に課された特定の応用および設計の制約に基づいている。当業者はこれらの状態下におけるハードウェアとソフトウェアの交換性、各特定の応用での説明した機能を実行するのに最良の方法を認識するであろう。例として、種々の例示的な論理ブロック、モジュール、回路、アルゴリズムステップはデジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラム可能なゲートアレイ（ＦＰＧＡ）、その他のプログラム可能な論理装置、ディスクリートなゲートまたはトランジスタ論理装置、レジスタおよびＦＩＦＯ等のディスクリートなハードウェアコンポーネント、１セットのファームウェア命令を実行するプロセッサ、任意の通常のプログラム可能なソフトウェアモジュール、プロセッサ、またはその任意の組合わせがここで説明した機能を行うように設計され、構成され、実行される。プロセッサはマイクロプロセッサであると有効であるが、その代りとして、プロセッサは任意の通常のプロセッサ、制御装置、マイクロプロセッサ、プログラム可能な論理装置、論理素子のアレイ、または状態マシンであってもよい。ソフトウェアモジュールはＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取出し可能なディスク、ＣＤ−ＲＯＭ、または技術で知られている任意の他の形態の記憶媒体に存在する。例示的なプロセッサは記憶媒体から情報を読出し、そこへ情報を書込むように記憶媒体に有効に結合される。別のものでは、記憶媒体はプロセッサに不可欠である。プロセッサおよび記憶媒体はＡＳＩＣに存在する。ＡＳＩＣは電話機または他のユーザ端末に存在してもよい。別のものとしては、プロセッサおよび記憶媒体が電話機または他のユーザ端末に存在してもよい。プロセッサはＤＳＰとマイクロプロセッサの組合わせとして、またはＤＳＰコア等を伴った２つのマイクロプロセッサとして構成されてもよい。
【０１３６】
以上、本発明の好ましい実施形態を示し説明した。しかしながら本発明の技術的範囲を逸脱せずに、多数の変形をここで説明した実施形態に対して行ってもよいことが当業者に明白であろう。それ故、本発明は特許請求の範囲の記載を除いては限定されない。
【図面の簡単な説明】
【０１３７】
【図１】無線通信システムおよび高いデータレートの送信をサポートする無線通信システムの概略図。
【図２】無線通信システムでデータ送信をスケジュールするサービスグレード、ＧＯＳおよびアルゴリズムのフロー図。
【図３】無線通信システムのデータ送信のスケジュールアルゴリズムのフロー図。
【図４Ａ】無線通信システムにおけるデータ送信をスケジュールするための割合−公正アルゴリズムのフロー図。
【図４Ｂ】無線通信システムにおけるデータ送信をスケジュールするための割合−公正アルゴリズムのフロー図。
【図５】無線通信システムにおける割合−公正アルゴリズムとＧＯＳアルゴリズムを実行する組合わせスケジュールアルゴリズムのフロー図。
【図６】無線通信システムの一般化されたスケジューラのフロー図。
【図７】図５および図６に示されているような組合わせスケジュールアルゴリズムをサポートする無線通信システムのブロック図。
【図８】無線通信システムのスケジュールアルゴリズムのフロー図。
【図９Ａ】共通のマップされた優先順位パラメータ範囲への種々の転送優先順位パラメータ範囲のマッピング図。
【図９Ｂ】多数のマップされた優先順位パラメータにわたる種々の動作点の決定を示した図。
【図９Ｃ】多数のマップされた優先順位パラメータにわたる種々の動作点の決定を示した図。
【図９Ｄ】多数のマップされた優先順位パラメータにわたる種々の動作点の決定を示した図。
【図１０】一般化されたスケジューラのフロー図。
【図１】
2004533750.tif 000003
【図２】
2004533750.tif 000004
【図３】
2004533750.tif 000005
【図４Ａ】
2004533750.tif 000006
【図４Ｂ】
2004533750.tif 000007
【図５】
2004533750.tif 000008
【図６】
2004533750.tif 000009
【図７】
2004533750.tif 000010
【図８】
2004533750.tif 000011
【図９Ａ】
2004533750.tif 000012
【図９Ｂ】
2004533750.tif 000013
【図９Ｃ】
2004533750.tif 000014
【図９Ｄ】
2004533750.tif 000015
【図１０】
2004533750.tif 000016
【国際公開パンフレット】
2004533750.tif 000017
2004533750.tif 000018
2004533750.tif 000019
2004533750.tif 000020
2004533750.tif 000021
2004533750.tif 000022
2004533750.tif 000023
2004533750.tif 000024
2004533750.tif 000025
2004533750.tif 000026
2004533750.tif 000027
2004533750.tif 000028
2004533750.tif 000029
2004533750.tif 000030
2004533750.tif 000031
2004533750.tif 000032
2004533750.tif 000033
2004533750.tif 000034
2004533750.tif 000035
2004533750.tif 000036
2004533750.tif 000037
2004533750.tif 000038
2004533750.tif 000039
2004533750.tif 000040
2004533750.tif 000041
2004533750.tif 000042
2004533750.tif 000043
2004533750.tif 000044
2004533750.tif 000045
2004533750.tif 000046
2004533750.tif 000047
2004533750.tif 000048
2004533750.tif 000049
2004533750.tif 000050
2004533750.tif 000051
2004533750.tif 000052
2004533750.tif 000053
2004533750.tif 000054
2004533750.tif 000055
2004533750.tif 000056
2004533750.tif 000057
2004533750.tif 000058
2004533750.tif 000059
2004533750.tif 000060
2004533750.tif 000061
2004533750.tif 000062
2004533750.tif 000063
2004533750.tif 000064
2004533750.tif 000065
2004533750.tif 000066
2004533750.tif 000067
2004533750.tif 000068
2004533750.tif 000069
2004533750.tif 000070
2004533750.tif 000071
2004533750.tif 000072
2004533750.tif 000073
2004533750.tif 000074
2004533750.tif 000075
2004533750.tif 000076
2004533750.tif 000077
2004533750.tif 000078
2004533750.tif 000079
2004533750.tif 000080
2004533750.tif 000081
2004533750.tif 000082
2004533750.tif 000083
【国際調査報告】
2004533750.tif 000084
2004533750.tif 000085
2004533750.tif 000086