(57)【特許請求の範囲】
【請求項１】
通信システム内で有限の資源を割振る方法であって、通信システムは共用ノードと、共用ノードに関係する複数の顧客ノードとを含み、各顧客ノードは要求データレートをもち、特定のサービス間隔中に、共用ノードは有限の資源を顧客ノードの１つへ割り振って、残りの顧客ノードを除外し、
各顧客ノードに対応する重みをもつ1つの重みを維持するステップと、
前記１組の重みから最小の重みＭを識別するステップと、
ＭとオフセットＫとの和に等しいか、またはそれより小さい重みをもつ前記顧客ノードのサブセットを識別するステップと、
前記サブセット内の各顧客ノードに対して望ましさの尺度値を判断するステップと、
最大の望ましさの尺度値をもつ最も望ましい顧客ノードを前記サブセットから選択するステップと、
共用ノードと前記最も望ましい顧客ノードとの間で有限の資源を介して、前記最も望ましい顧客ノードに関係するデータレートでデータを交換するステップと、
前記最も望ましい顧客ノードに基づく前記1組の重みと、前記最も望ましい顧客ノードに関係するデータレートとを変更するステップとを含む方法。
【請求項２】
前記オフセットＫが定数である請求項１記載の方法。
【請求項３】
前記オフセットＫが、顧客ノード数に基づいて変化する請求項１記載の方法。
【請求項４】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値が、前記各顧客ノードに関係する要求データレートから、前記各顧客ノードに関係する平均スループット値を減算することによって判断される請求項１記載の方法。
【請求項５】
前記オフセットＫが定数である請求項４記載の方法。
【請求項６】
前記オフセットＫが顧客ノード数に基づいて変化する請求項４記載の方法。
【請求項７】
前記平均スループット値の各々を更新するステップをさらに含む請求項４記載の方法。
【請求項８】
前記平均スループット値が、
NewAverageThroughput=｛(1-1/TC)＊OldAverageThroughput｝+(1/TC＊Requested Data Rate)、
の式（TCは時間定数, Time Constant）にしたがって更新される請求項７記載の方法。
【請求項９】
ＴＣが定数である請求項８記載の方法。
【請求項１０】
ＴＣが顧客ノード数に基づいて変化する請求項８記載の方法。
【請求項１１】
ＴＣが、前記各顧客ノードに関係する先の要求データレートに基づいて変化する請求項８記載の方法。
【請求項１２】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値が、前記サブセット内の前記各顧客ノードに対する要求データレートに等しい請求項1記載の方法。
【請求項１３】
前記オフセットＫが定数である請求項１２記載の方法。
【請求項１４】
前記オフセットＫが顧客ノード数に基づいて変化する請求項１２記載の方法。
【請求項１５】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値が、前記各顧客ノードに関係する平均スループット値によって、前記各顧客のノードに関係する要求データレートを除算することによって判断される請求項１記載の方法。
【請求項１６】
前記オフセットＫが定数である請求項１５記載の方法。
【請求項１７】
前記オフセットＫが顧客ノード数に基づいて変化する請求項１５記載の方法。
【請求項１８】
前記平均スループット値の各々を更新するステップをさらに含む請求項１５記載の方法。
【請求項１９】
前記平均スループット値が、
NewAverageThroughput=｛(1-1/TC)＊OldAverageThroughput｝+(1/TC＊Requested Data Rate)、
の式にしたがって更新される請求項１８記載の方法。
【請求項２０】
ＴＣが定数である請求項１９記載の方法。
【請求項２１】
ＴＣが顧客ノード数に基づいて変化する請求項１９記載の方法。
【請求項２２】
ＴＣが、前記顧客ノードに関係する先の要求データレートに基づいて変化する請求項１９記載の方法。
【請求項２３】
無線送信機であって、
複数の顧客ノードの各々から要求データレート信号を受信し、情報信号を前記複数の顧客ノードへ方向付ける少なくとも１つのアンテナと、
データ信号を変調して、前記少なくとも1つのアンテナを介して前記複数の顧客ノードの各々へ送るチャンネル素子と、
チャンネルスケジューラであって、各顧客ノードに対応する1組の重みを維持し、前記1組の重みから最小の重みＭを識別し、ＭとオフセットＫとの和に等しいか、またはより小さい重みをもつ前記顧客ノードのサブセットを識別し、サブセット内の各顧客ノードに対して望ましさの尺度値を判断し、最大の望ましさの尺度値をもつ最も望ましい顧客ノードをサブセットから選択し、最も望ましい顧客ノードに対応する情報を前記チャンネル素子へ供給し、前記1組の重みを更新するためのチャンネルスケジューラとを含む無線送信機。
【請求項２４】
前記チャンネル素子がＣＤＭＡのチャンネル素子である請求項２３記載の無線送信機。
【請求項２５】
前記ＣＤＭＡのチャンネル素子が、前記最も望ましい顧客ノードのＰＮ拡散を行なうための疑似雑音（pseudonoise, PN）拡散器をさらに含む請求項２４記載の無線送信機。
【請求項２６】
前記ＣＤＭＡのチャンネル素子がさらに、
同位相の疑似雑音コードと直角位相の疑似雑音コードとを生成する短い疑似雑音コード生成器と、
前記同位相の疑似雑音コードと直角位相の疑似雑音コードとによって前記最も望ましい顧客ノードに関係する信号の複素数乗算を行うための複素数乗算器とを含む請求項２４記載の無線送信機。
【請求項２７】
前記オフセットＫが定数である請求項２３記載の無線送信機。
【請求項２８】
前記オフセットＫが、顧客ノード数に基づいて変化する請求項２３記載の無線送信機。
【請求項２９】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値は、前記各顧客ノードに関係する要求データレートから前記各顧客ノードに関係する平均スループット値を減算することによって判断される請求項２３記載の無線送信機。
【請求項３０】
前記オフセットＫが定数である請求項２９記載の無線送信機。
【請求項３１】
前記オフセットＫが、顧客ノード数に基づいて変化する請求項２９記載の無線送信機。
【請求項３２】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値が、前記サブセット内の各顧客ノードに対する前記要求データレート信号内の要求データレート値に等しい請求項２３記載の無線送信機。
【請求項３３】
前記サブセット内の各顧客ノードに対する前記望ましさの尺度値が、前記各顧客ノードに関係する平均スループット値によって前記各顧客ノードに関係する要求データレートを除算することによって判断される請求項２３記載の無線送信機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信システムに関する。とくに、本発明の実施形態では、通信システムの複数の加入者間で通信資源を割り振ることについて記載している。
【０００２】
【従来の技術】
通信システム内の単一のノードによって供給される限定された通信資源を複数の加入者間で割り振る問題に対処するために、いくつかの解決案が示されてきた。このようなシステムは、ノードに十分な資源を用意して、全ての加入者の要求を満足させる一方で、コストを極小化することを目的とする。したがって、このようなシステムは、概ね、種々の加入者間で資源を効率的に割り振ることを目的として設計されている。
【０００３】
種々のシステムでは、周波数分割多重アクセス（frequency division multiple access, FDMA）方式を実行し、各加入者に資源を同時に割り振っている。このようなシステム内の通信ノードは、概ね、時間内の任意の時点において各加入者との間で情報を送受信する限定されたバンド幅をもつ。この方式には、一般的に、全バンド幅の個別の部分を個々の加入者に割り振ることを含む。このような方式は、加入者が通信ノードとの通信が中断されないことを求めるシステムにおいて効果的であるが、一定の中断されない通信が求められていないときは、全バンド幅をより適切に使用できる。
【０００４】
複数の加入者間で単一の通信ノードの通信資源を割り振る他の方式には、時分割多重アクセス（time division multiple access, TDMA）方式を含む。これらのＴＤＭＡ方式は、単一の通信ノードとの一定の中断されない通信を求めていない複数の加入者間で、単一の通信ノードの限定されたバンド幅の資源を割り振るのにとくに効率的である。ＴＤＭＡ方式では、通常は、指定された時間間隔で単一の通信ノードの全バンド幅を各加入者に専用にしている。符号分割多重アクセス（code division multiple access, CDMA）方式を採用している無線通信システムでは、これは、時間を多重化することに基づいて、指定された時間間隔で全てのコードチャンネルを各加入者に割り当てることによって達成される。通信ノードは、加入者に関係するユニークなキャリア周波数またはチャンネルコードを構成して、加入者との専用の通信を可能にしている。ＴＤＭＡ方式は、物理的な接触中継スイッチングまたはパケットスイッチングを使用して陸線システム（land line system）においても実行することができる。
【０００５】
ＴＤＭＡシステムは、一般的に、ラウンドロビン方式で均等な時間間隔を各加入者に割り振っている。これは、一定の加入者は一定の時間間隔で利用するといった条件のもとで達成される。同様に、他の加入者は、割り振られた時間間隔を越えると、サービスを受けられなくなるといった通信資源要件をもつ。したがってシステムオペレータは、ノードのバンド幅を増加するコストを負って、何れの加入者もサービスを受けられないことを保証するか、またはサービスを受けている加入者がサービスを受け続けることができるといった選択肢をもっている。
【０００６】
したがって、加入者間で通信資源を割り振るネットワークポリシーにしたがって、通信ネットワークの加入者間で通信資源を効率的で公平に割り振るシステムおよび方法を提供することが必要である。
【０００７】
【発明が解決しようとする課題】
本発明の目的は、複数の加入者間で通信システムの有限の資源を割り振るシステムおよび方法を提供することである。
【０００８】
本発明の別の目的は、データを受信する能力が異なる複数の加入者間でデータ伝送資源を割り振るためのシステムおよび方法を提供することである。
【０００９】
本発明の実施形態の別の目的は、ネットワークポリシーの公平性の基準にしたがって複数の加入者間でデータ伝送資源を最適に割り振るシステムおよび方法を提供することである。
【００１０】
本発明の実施形態の別の目的は、無線通信ネットワークにおいて複数の遠隔局間で基地局のデータ伝送資源を割り振るシステムおよび方法を提供することである。
【００１１】
本発明の実施形態のさらに別の目的は、加入者が伝送されたデータを受信できるレートに基づいて各個々の加入者へ伝送資源を割り振ることによって、可変のデータ伝送レートのネットワーク内で複数の加入者へデータを伝送する効率を向上するためのシステムおよび方法を提供することである。
【００１２】
簡潔にいうと、本発明の実施形態は、共用ノードと、共用ノードに関係する複数の顧客ノードとを含む通信システムにおける資源スケジューラに関する。共用ノードが、特定のサービス間隔において有限の資源を供給し、接続している顧客ノードがこれを占有し、残りの顧客ノードを除外することができる。資源スケジューラは、各顧客ノードに関係する重みまたはスコアを維持するための論理、残りの顧客ノードを選択して、選択された各顧客ノードに関係する重みと、他の残りの顧客ノードに関係する重みとの比較に基づいて、次のサービス間隔において有限の資源を占有する論理、顧客ノードに関係する重みを変更して、公平性の基準にしたがって有限の資源を最適に割り振る論理とを含む。資源スケジューラは、顧客ノードが共用ノードからデータを受信できる瞬間レートに基づいて、各顧客ノードに関係する重みを維持する。次に資源スケジューラは、より高いデータ受信レートをもつ顧客ノードへの伝送を優先する（favor）。各顧客ノードに関係する重みを維持し、かつ共用ノードを占有して、個々の顧客ノードを選択することによって、スケジューラは公平性の基準にしたがって顧客ノードへ資源を最適に割り振ることができる。
【００１３】
共用ノードが顧客ノードへデータ伝送資源を供給する実施形態では、例えば、スケジューラは個々の顧客ノードへ重みを適用して、より高いレートでデータを受信することができるこれらの顧客ノードを優先することができる。このような重み付けは、共用ノードの全体的なデータのスループットを向上する傾向がある。別の実施形態では、スケジューラが公平性の基準にしたがうようなやり方で、重みが適用される。
【００１４】
本発明の１つの態様では、通信システム内で有限の資源を割り振る方法であって、通信システムは共用ノードと、共用ノードに関係する複数の顧客ノードとを含み、各顧客ノードは要求データレートをもち、特定のサービス間隔の間、共用ノードは有限の資源を顧客ノードの1つへ割り振って、残りの顧客ノードを除外し、
各顧客ノードに対応する１つの重みをもつ1組の重みを維持するステップと、
前記1組の重みから最小の重みＭを識別するステップと、
ＭとオフセットＫとの和に等しいかまたはそれより小さい重みをもつ前記顧客ノードのサブセットを識別するステップと、
前記サブセット内の各顧客ノードに対する望ましさの尺度値（desirability metric value）を判断するステップと、
最大の望ましさの尺度値をもつ最も望ましい顧客ノードを前記サブセットから選択するステップと、
共用ノードと前記最も望ましい顧客ノードとの間で、有限の資源を介して、前記最も望ましい顧客ノードに関係するデータレートでデータを交換するステップと、
前記最も望ましい顧客ノードに基づく前記1組の重みと、前記最も望ましい顧客ノードに関係するデータレートとを変更するステップとを含む方法を提供する。
【００１５】
本発明の別の態様では、無線送信機であって、
複数の顧客ノードの各々から要求データレート信号を受信し、情報信号を前記複数の顧客ノードへ方向付ける少なくとも１つのアンテナと、
データ信号を変調して、前記少なくとも1つのアンテナを介して前記複数の顧客ノードの各々へ送るチャンネル素子と、
チャンネルスケジューラであって、各顧客ノードに対応する1組の重みを維持し、前記1組の重みから最小の重みＭを識別し、ＭとオフセットＫとの和に等しいか、またはより小さい重みをもつ前記顧客ノードのサブセットを識別し、サブセット内の各顧客ノードに対して望ましさの尺度値を判断し、最大の望ましさの尺度値をもつ最も望ましい顧客ノードをサブセットから選択し、最も望ましい顧客ノードに対応する情報を前記チャンネル素子へ供給し、前記1組の重みを更新するためのチャンネルスケジューラとを含む無線送信機を提供する。
【００１６】
ここに記載した実施形態は、データサービスネットワークにおいてデータ伝送資源を順方向チャンネルを介して加入者へ割振るための方法およびシステムに関し、基礎となる原理は、概ね通信システムにおける素子間の資源の割り振りに対してかなりより広範に応用される。したがって記載されている実施形態は、例示することを意図されていて、特許請求項の技術的範囲を制限しない。例えば、ここに記載した原理は、顧客ノードが制限された逆方向の伝送チャンネルを介して共用ノードへデータを送る能力について競い合う通信ネットワークに応用できる。
【００１７】
【発明の実施の形態】
本発明の実施形態は、単一の通信ノードによってサービスされる通信ネットワークの複数の加入者間で資源を割当てるシステムおよび装置に関する。個々の別個の伝送間隔、すなわち“サービス間隔（service interval）”において、個々の加入者は、通信ノードの有限の資源を占有して、他の全ての加入者を除外する。個々の加入者は、個別の加入者に関係する重みまたはスコアに基づいて有限の資源を占有するように選択される。個々の加入者に関係する重みにおける変更は、個々の加入者が有限の資源を消費できる瞬間レートに基づいていることが好ましい。
【００１８】
図面を参照すると、図1には、例示的な可変レートの通信システムが示されている。１つのこのようなシステムは、米国特許出願第08/963,386号に記載されており、これは1997年11月3日に出願され、Qualcomm, Inc.へ譲渡され、ここでは参考文献として取り上げている。可変レートの通信システムは多数のセル2aないし2gを含む。各セル２は対応する基地局４によってサービスされる。種々の遠隔局６は、通信システム全体に分散している。例示的な実施形態では、各遠隔局６は順方向リンク上を任意のデータ伝送間隔で多くとも1つの基地局４と通信している。例えば、時間スロットｎの順方向リンク上では、基地局4aは遠隔局6aのみへデータを送り、基地局4bは遠隔局6bのみへデータを送り、基地局4cは遠隔局6cのみにデータを送る。図１に示されているように、各基地局４は所与の瞬間において1つの遠隔局６へデータを送ることが好ましい。他の実施形態では、基地局４は特定の伝送間隔で２以上の遠隔局６と通信し、基地局４に関係する他の全ての遠隔局６を除外する。さらに加えて、データレートは可変であり、受信側の遠隔局６によって測定されるキャリア対干渉比（carrier-to-interference, C/I）と、要求される１ビットあたりのエネルギ対雑音比（energy-per-bit-to-noise-ratio, Ｅｂ/Ｎｏ）に依存する。遠隔局６から基地局４への逆方向リンクは、簡潔にするために図1には示されていない。実施形態にしたがって、遠隔局は、無線データサービスの加入者によって操作される無線トランシーバを備えた移動体（mobile unit）である。
【００１９】
図２および３には、例示的な可変レートの通信システムの基本的なサブシステムを表わすブロックダイヤグラムが示されている。基地局制御装置10は、パケットネットワークインターフェイス24、公衆交換電話ネットワーク（public switched telephone network, PSTN）30、および通信システム内の全ての基地局４（図２では簡潔にするために、基地局４は1つのみが示されている）とインターフェイスしている。基地局制御装置10は、通信システム内の遠隔局６と、パケットネットワークインターフェイス24およびＰＳＴＮ30に接続されている他のユーザとの間の通信を調整している。ＰＳＴＮ30は、標準のネットワーク（図２には示されていない）を介してユーザとインターフェイスしている。
【００２０】
基地局制御装置10は多くのセレクタ素子を含んでいるが、図２には、簡潔にするために、1つのみのセレクタ素子14が示されている。各セレクタ素子14は１つ以上の基地局４と１つの遠隔局６との間の通信を制御するように割り当てられている。セレクタ素子14が遠隔局６に割り当てられていないときは、呼制御プロセッサ16は遠隔局６にページする必要について知らされる。次に呼制御プロセッサ16は、基地局４に遠隔局６をページするように命令する。
【００２１】
データ源20には、遠隔局６へ送られる一定量のデータが含まれている。データ源20はパケットネットワークインターフェイス24へデータを供給する。パケットネットワークインターフェイス24はデータを受信して、そのデータをセレクタ素子14へルート設定する。セレクタ素子14は、遠隔局６と通信している各基地局4へデータを送る。例示的な実施形態では、各基地局４はデータの待ち行列40を含み、データの待ち行列40は遠隔局６へ送られるデータを記憶している。
【００２２】
データはデータパケット内でデータの待ち行列40からチャンネル素子42へ送られる。例示的な実施形態では、順方向リンク上では、“データパケット”は、最大で１０２４ビットのデータ量、および１つの“時間スロット”（例えば、略１．６６７ミリ秒）内で宛先の遠隔局６へ送られるデータ量を指す。チャンネル素子42は、各データパケットごとに必要な制御フィールドを挿入する。例示的な実施形態では、チャンネル素子42のＣＲＣでは、データパケットおよび制御フィールドをコード化し、1組のコードの末尾のビットを挿入する。データパケット、制御フィールド、ＣＲＣのパリティビット、およびコードの末尾のビットは、フォーマットされたパケットを構成している。例示的な実施形態では、チャンネル素子42はフォーマットされたパケットをコード化し、コード化されたパケット内の符号をインターリーブする（または再び順序付けする）。例示的な実施形態では、インターリーブされたパケットは、ウオルシュコード（Walsh code）でカバーされ、短いＰＮＩおよびＰＮＱコードで拡散(spread)される。拡散されたデータはＲＦユニット44へ供給され、ＲＦユニット44は信号を直交変調(quadrature modulate)し、フィルタし、増幅する。順方向リンクの信号は、順方向リンク50上でアンテナ46によって電波で送られる。
【００２３】
遠隔局６では、順方向リンク信号はアンテナ60によって受信され、フロントエンド62内で受信機へルート設定される。受信機は信号をフィルタし、増幅し、直交復調し（quadrature demodulate）、量子化する。ディジタル信号は、復調機（demodulator, DEMOD）64へ供給され、ＤＥＭＯＤ64において短いＰＮＩおよびＰＮＱのコードで逆拡散され、ウオルシュカバー(Walsh cover)でデカバー（decover）される。復調されたデータはデコーダ66へ供給され、デコーダ66は、基地局４において行われた信号処理機能の逆、とくにデインターリービング（de-interleaving）、デコーディング、およびＣＲＣ検査機能を実行する。
【００２４】
既に指摘したように、ハードウエアは、順方向リンク上での可変レートのデータ伝送、メッセージング、音声、映像、および他の通信を支援する。データの待ち行列40から送られるデータのレートは、信号強度の変化および遠隔局６におけるノイズ環境に適用するように変化する。各遠隔局６は、各時間スロットにおいてデータレート制御（data rate control, DRC）信号を関係する基地局４へ送ることが好ましい。ＤＲＣ信号は、遠隔局６の識別と、遠隔局６が関係するデータの待ち行列からデータを受信するレートとを含む情報を基地局４へ供給する。したがって、遠隔局６の回路は信号強度を測定し、遠隔局６におけるノイズ環境を推定して、ＤＲＣ信号内で送られるレート情報を判断する。
【００２５】
各遠隔局６によって送られるＤＲＣ信号は、逆方向のリンクチャンネル52を通り、アンテナ46およびＲＦユニット44を経て基地局４において受信される。例示的な実施形態では、スケジューラ12ｂは基地局４内に位置している。代わりの実施形態では、ＤＲＣ情報はチャンネル素子42において復調され、基地局制御装置10内に位置するチャンネルスケジューラ12ａか、または基地局４内に位置するチャンネルスケジューラ12ｂへ供給される。第１の例示的な実施形態では、チャンネルスケジューラ12ａは基地局制御装置10内に位置しており、基地局制御装置10内の全てのセレクタ素子14と接続している。
【００２６】
上述の第１の例示的な実施形態では、チャンネルスケジューラ12ｂは、各遠隔局の待ち行列を作るデータ量、すなわち待ち行列の長さ（queue size）を示す情報をデータの待ち行列40から受信する。次にチャンネルスケジューラ12ｂは、基地局４によってサービスされる各遠隔局ごとに、ＤＲＣ情報および待ち行列の長さに基づいてスケジューリングを行う。代わりの実施形態において使用されるスケジューリングアルゴリズムに待ち行列の長さが必要であるときは、チャンネルスケジューラ12ａはセレクタ素子14から待ち行列の長さの情報を受信する。
【００２７】
本発明の実施形態は、可変レートの伝送を支援できる他のハードウエアのアーキテクチャに適用することができる。本発明は、逆方向リンク上の可変レートの伝送を含むように容易に拡張することができる。例えば、遠隔局６からのＤＲＣ信号に基づいて基地局４においてデータを受信するレートを判断する代わりに、基地局４は、遠隔局６から受信した信号の強度を測定し、ノイズ環境を推定して、遠隔局６からデータを受信するレートを判断する。次に基地局４は、データが逆方向リンクにおいて遠隔局６から送られるレートを、各関係する遠隔局６へ送る。次に基地局４は、順方向リンクについて本明細書に記載したやり方に類似したやり方で、逆方向リンク上の異なるデータレートに基づいて、逆方向リンク上の伝送をスケジュールする。
【００２８】
さらに加えて、上述の実施形態の基地局４は、符号分割多重アクセス（code division multiple access, CDMA）方式を使用して、遠隔局６から選択した１つまたは複数の遠隔局６へ送り、基地局４に関係する残りの遠隔局は除外する。受信側の基地局４に割り当てられたコードを使用することによって、基地局４は、任意の特定の時間において、遠隔局６から選択した１つまたは複数の遠隔局６へ送る。しかしながら、本発明は、異なる時分割多重アクセス（time division multiple access, TDMA）方法を採用して、伝送資源を最適に割り振るために、基地局４を選択し、他の基地局４を除外するデータを供給する他のシステムへ適用することもできる。
【００２９】
チャンネルスケジューラ12は順方向リンク上での可変レートの伝送をスケジュールする。スケジューラ12は、遠隔局６へ送るデータ量を示す待ち行列の長さと、遠隔局６からのメッセージとを受信する。チャンネルスケジューラ12は、公平性の制約にしたがう一方で、データの最大スループットについてのシステムの目標を達成するデータ伝送をスケジュールすることが好ましい。
【００３０】
図１に示したように、遠隔局６は通信システム全体に分散しており、順方向リンク上で単一の基地局と通信できるか、または通信できない。例示的な実施形態では、チャンネルスケジューラ12は、全通信システム上で順方向リンクのデータ伝送を調節する。高速度のデータ伝送のためのスケジューリング方法および装置は、米国特許出願第08/798,951号（“Method and Apparatus for Forward Link Rate Scheduling”）に詳しく記載されており、これは1997年2月11日に出願され、本発明の譲受人に譲渡され、ここでは参考文献として取り上げている。
【００３１】
実施形態にしたがって、チャンネルスケジューラ12は、プロセッサ、ランダムアクセスメモリ（random access memory, RAM）、およびプロセッサによって実行される指令を記憶するプログラムメモリを含むコンピュータシステムにおいて実行される。プロセッサ、ＲＡＭ、およびプログラムメモリは、チャンネルスケジューリング12の機能に専用であってもよい。他の実施形態では、プロセッサ、ＲＡＭ、およびプログラムメモリは、基地局制御装置10において追加の機能を実行するための共用のコンピュータ処理資源の一部であってもよい。
【００３２】
図４は、チャンネルスケジューラ12を制御して、基地局４から遠隔局６への伝送をスケジュールするスケジューリングアルゴリズムの実施形態を示している。既に記載したように、データの待ち行列40は各遠隔局６に関係している。チャンネルスケジューラ12は各データの待ち行列40を“重み”と関係付け、“重み”は、基地局４に関係する特定の遠隔局６を選択するステップ110において推定されて、次のサービス間隔においてデータを受信する。チャンネルスケジューラ12は、個々の遠隔局６を選択して、別個のサービス間隔内でデータ伝送を受信する。ステップ102では、チャンネルスケジューラは、基地局４に関係する各待ち行列ごとに重みを初期設定する。
【００３３】
チャンネルスケジューラ12は、伝送間隔またはサービス間隔においてステップ104ないし112を繰返す。ステップ104では、チャンネルスケジューラ12は、先のサービス間隔において検出された追加の遠隔局６と基地局４との関係によって、待ち行列が追加されるか、否かを判断する。ステップ104では、チャンネルスケジューラ12はさらに、新しい待ち行列に関係する重みを初期設定する。既に記載したように、基地局４は、時間スロットのような規則的な間隔でその基地局４に関係する各遠隔局６からＤＲＣ信号を受信する。
【００３４】
ＤＲＣ信号はさらに、ステップ106においてチャンネルスケジューラが各待ち行列に関係する各遠隔局についての情報を消費する（すなわち、送られたデータを受信する）瞬間レートを判断するのに使用する情報を供給する。この実施形態にしたがって、遠隔局６から送られるＤＲＣ信号は、遠隔局６が、表１に示されている１１の実効データレートの１つにおいてデータを受信できることを示している。このような可変レートの伝送システムは、米国特許出願第08/965,705号（“Method for Assigning Optimal Packet Lengths in a Variable Rate Communication System”）に詳しく記載されており、これは1997年11月7日に出願され、本発明の譲受人に譲渡され、ここでは参考文献として取り上げている。
【００３５】
【表１】
0004559008.tif 000002
【００３６】
ステップ108においてチャンネルスケジューラ12は、（最近受信したＤＲＣ信号において示されている）遠隔局６がデータを受信することに関係する瞬間レートに基づいて、データが特定の遠隔局６へ送られる間のサービス間隔の長さを判断する。実施形態にしたがって、ステップ106ではデータＲｉを受信する瞬間レートでは、特定のデータの待ち行列に関係するサービス間隔長Ｌｉを判断する。表１には、遠隔局６においてデータを受信するための１１の可能な瞬間レートの各々に対するＬｉの値がまとめられている。
【００３７】
ステップ110においてチャンネルスケジューラ12は、特定の伝送データの待ち行列を選択する。次に、関係する伝送データの量がデータの待ち行列40から検索され、データの待ち行列40に関係する遠隔局６へ送るためにチャンネル素子42へ供給される。別途記載するように、ステップ110では、チャンネルスケジューラ12は、各待ち行列に関係する重みを含む情報を使用して、次のサービス間隔内で送られるデータを用意している待ち行列を選択する。次にステップ112では、送られる待ち行列に関係する重みは更新される。
【００３８】
図５は、サービス間隔におけるチャンネルスケジューラ12とデータ伝送とのタイミングを表わすダイヤグラムを示している。図５では、伝送中の３つの別個のサービス間隔を時間間隔Ｓ−１、Ｓ０、およびＳ１で示している。サービス間隔202の間に図４のスケジューリングアルゴリズムのステップ104ないし112が実行されているとき、間隔Ｓ０中にスケジューリングアルゴリズムを実行して、間隔Ｓ１において何れの待ち行列が送られるかを判断することが好ましい。さらに加えて、別途記載するように、ステップ104ないし112の実行は、遠隔局６から受信するＤＲＣ信号内の情報に依存する。この情報は、最近受信したＤＲＣ信号から抽出されることが好ましい。したがって、ステップ104ないし110が実行されて、サービス間隔の最後の時間スロット中に完了することが好ましい。したがって、次のサービス間隔を割り振るための決定が、最近のＤＲＣ信号（すなわち、ステップ104ないし110を実行する直前の時間スロット内のＤＲＣ信号）に基づいていることが保証される。
【００３９】
ステップ104ないし110は、チャンネルスケジューラ12が次のサービス間隔の間の伝送をスケジュールするのに十分な時間を与える一方で、１時間スロット内で完了することが好ましい。したがってチャンネルスケジューラ12が使用するプロセッサおよびＲＡＭは、図５に示した時間の制約内でステップ104ないし112を実行できることが好ましい。すなわち、プロセッサおよびＲＡＭは、ステップ104ないし110を時間スロットの最初に開始して、時間スロットの最後よりも十分に前にそれを完了するようにステップ104ないし110を実行することができ、その間にチャンネルスケジューラ12は次のサービス間隔における伝送をスケジュールすることが好ましい。
【００４０】
当業者には、本発明の技術的範囲から逸脱せずに種々のアプローチを使用して、チャンネルスケジューラ12を実行できることが分かるであろう。例えば、プロセッサ、ランダムアクセスメモリ（random access memory, RAM）および、プロセッサによって実行される指令を記憶するプログラムメモリを含むコンピュータシステム（図示されていない）を使用して、チャンネルスケジューラ12を実行してもよい。別の実施形態では、チャンネルスケジューラ12の機能は共用のコンピュータ処理資源へ組込まれて、共用のコンピュータ処理資源は基地局４または基地局制御装置10において追加の機能を実行するためにも使用されてもよい。さらに加えて、チャンネルスケジューラ機能を実行するのに使用されるプロセッサは、本発明の技術的範囲から逸脱せずに、汎用のマイクロプロセッサ、ディジタル信号プロセッサ（digital signal processor, DSP）、プログラマブルロジックデバイス、特定用途向け集積回路（application specific integrated circuit, ASIC）、または本明細書に記載したアルゴリズムを実行することができる他のデバイスであってもよい。
【００４１】
図６は、ステップ112（図４参照）において重みを更新するためのプロセスの実施形態を示している。ステップ302では、データをもつ待ち行列に関係する瞬間レートの全ての平均であるレート閾値“Ｃ”をコンピュータ処理する。データをもたない待ち行列に関係する瞬間レートは、この計算において削除されることが好ましい。ステップ304では、ステップ110において選択されたSelected Queueに関係する瞬間レートを比較する。Selected Queueに関係する瞬間レートが閾値Ｃを上回るときは、ステップ306においてこのSelected Queueに関係する重みより小さい値、すなわち次のサービス間隔の間にSelected Queueから送られるデータ量をビット、バイト、またはメガバイトのような単位で表した数だけインクリメントすることが好ましい。Selected Queueに関係する瞬間レートが、ステップ302において計算された閾値を上回らないときは、ステップ308ではSelected Queueの重みをより大きい値、すなわち次のサービス間隔の間にSelected Queueから送られるデータ量（例えば、ビット、バイト、またはメガバイト単位の量）の倍数“Ｇ”だけインクリメントすることが好ましい。
【００４２】
Ｇの選択は、より高いレートでデータを受信する容量をもつ遠隔局６へサービス間隔を割り振ることを優先する（ｓｕｐｐｏｒｔ）公平性の基準に基づいていることが好ましい。システムの設計者は、より速いレートでデータを受信する遠隔局６をより遅いレートで受信する遠隔局６よりも優先する範囲に基づいて、Ｇの大きさを選択する。Ｇの値がより大きくなると、基地局４の順方向リンクはより効率的に利用される。しかしながら、この効率は、より緩慢に受信する遠隔局６の加入者から順方向リンクの伝送資源を奪うという犠牲を払うことによって得られる。したがってシステムの設計者は、２つの競合する目的、すなわち１）順方向リンクの全体的な効率を向上することと、２）より緩慢に受信する遠隔局６から著しく奪ってしまうのを防ぐこととの間で平衡をとるようなやり方で、Ｇの値を選択することが好ましい。
【００４３】
ステップ304、306、および308は、より速い関係する瞬間データレート（すなわち、閾値Ｃを上回るレート）をもつ選択された待ち行列は、少しの量だけインクリメントされた関係する重みをもっていて、一方でより遅いデータレート（すなわち、閾値Ｃを上回らないレート）をもつ選択された待ち行列は、相当により大きな量をインクリメントされた関係する重みをもつことを示している。図４のステップ110において実行されるアルゴリズムに関連して別途記載するように、この構成は、より遅いデータレートでデータを受信する遠隔局よりも比較的により速いレートでデータを受信する遠隔局にサービスすることを優先する傾向がある。
【００４４】
この傾向により、順方向リンクにおけるデータ伝送において基地局４のスループット効率は高まる。しかしながら、より速いデータ受信レート（すなわち、閾値Ｃを上回るレート）をもつ遠隔局に関係する頻繁に選択される待ち行列に関係する重みがインクリメントされ続けるとき、これらの重みは、より遅いデータ受信レート（すなわち、閾値を上回らないレート）をもつ遠隔局に関係する比較的に選択され難い待ち行列に関係する待ち行列の重みに近付く結果になる。ステップ110における選択プロセスは、より速く受信する遠隔局の重みがより緩慢に受信する遠隔局の重みを上回り始めるとき、より緩慢に受信する遠隔局を優先し始める。これは、より速く受信する遠隔局が基地局の順方向リンクの伝送資源を占有して、より緩慢に受信する遠隔局を除外するのを防ぐことによって、ステップ110の選択プロセスに公平性の制約を課している。
【００４５】
本発明の目的は、伝送するデータをもたない待ち行列が、データをもつ待ち行列に対して、伝送について不公平な優先度（preference）を与えないことを保証することである。ステップ102および104において、全ての新しい待ち行列の重みはゼロで初期設定される。このような待ち行列は、選択されないときは、待ち行列が選択されないという条件でゼロの重みを維持し続けることになる。したがって、図６のステップ310は、全ての待ち行列の重みを、ちょうどゼロの値、すなわち（ステップ309において判断される）データをもつ待ち行列の最小の重みだけ、デクレメントする。これについては、次に表２に示した例においてより詳しく示す。
【００４６】
【表２】
0004559008.tif 000003
【００４７】
この例は３つの遠隔局をもち、各遠隔局は基地局から送られるデータの待ち行列に関係している。この例では、遠隔局１が最も速いデータレートをもち、遠隔局２が次に速いデータレートをもち、遠隔局３が最も遅いデータレートをもつと仮定する。簡潔にするために、これらのデータレートは、サービス間隔１ないし７において変化しないと仮定する。さらに加えて、ステップ304において遠隔局１および遠隔局２における各データレートは閾値Ｃを上回り、遠隔局３に関係するデータレートはこの閾値を上回らないと仮定する。さらに加えて、ステップ306において、Selected Queueが遠隔局１または遠隔局２に関係するとき、Selected Queueの重みを１だけインクリメントし、ステップ308において、Selected Queueが遠隔局３に関係するとき、Selected Queueの重みを８だけインクリメントすると仮定する。
【００４８】
サービス間隔１において、遠隔局１は遠隔局２および３と共に最も小さい重みをもつ一方で、より速いデータ受信レートをもつので、チャンネルスケジューラ12は遠隔局１を選択して、次のサービス間隔においてデータを受信する。データはサービス間隔２の間に遠隔局１へ送られ、遠隔局１に関係する重みはサービス間隔１の最後に１だけインクリメントされる。（遠隔局２は、最も小さい重みをもち、遠隔局３よりも速いデータ受信レートをもつので）チャンネルスケジューラ12は遠隔局２を選択して、サービス間隔３においてデータを受信する。表２に示したように、遠隔局２の重みはサービス間隔２の最後に１だけインクリメントされる。
【００４９】
サービス間隔３の最初に、遠隔局３は最も小さい重みをもっている。チャンネルスケジューラ12は遠隔局３を選択して、サービス間隔４においてデータを受信する。サービス間隔３の最後の状態は、遠隔局３の選択を反映するために、遠隔局３の重みがゼロから８へインクリメントされたことを反映している。遠隔局１、２、および３における重みは、表２に示されているように１だけデクレメントされ、これはステップ310（図６参照）に一致している。サービス間隔４において、遠隔局１に関係する待ち行列は最も小さい重みをもち、最も速いデータ受信レートをもつので、チャンネルスケジューラ12は遠隔局１を選択してデータを受信する。
【００５０】
チャンネルスケジューラ12はサービス間隔５において、遠隔局２を選択して、サービス間隔６の間にデータを受信する。遠隔局２に関係する重みは、最初にステップ306においてインクリメントされ、遠隔局の全ての重みは、表２に示されているように、サービス間隔５の最後に重みに反映されているように１だけデクレメントされる。次に最も小さい重みをもつ遠隔局１が、サービス間隔６において再び選択され、サービス間隔７においてデータを受信する。
【００５１】
図１の実施形態に示されているように、遠隔局６は移動性であり、異なる基地局４間の関係を変更することができる。例えば、遠隔局６ｆは最初に、基地局４ｆからデータ伝送を受信する。次に遠隔局６ｆは基地局４ｆのセルから出て、基地局４ｇのセルへ入る。次に遠隔局６ｆは、そのＤＲＣ信号の送信を開始し、基地局４ｆの代わりに基地局４ｇに警告することができる。遠隔局６ｆからＤＲＣ信号を受信しないことによって、基地局４ｆにおける論理では、遠隔局６ｆが接続を外され、データ伝送を最早受信しないと推測している。次に遠隔局６ｆに関係するデータの待ち行列は、陸線またはＲＦの通信リンクを介して基地局４ｇへ送られる。
【００５２】
本発明の実施形態にしたがって、チャンネルスケジューラ12は基地局４において、基地局４から接続を外して再び接続した遠隔局の待ち行列へ重みを割り当てる。基地局４は、再び接続した遠隔局６に単にゼロの重みを割り当てるのではなく、むしろ基地局４からデータ伝送を受信することについての不公平な特長を、再接続した遠隔局へ与えないような重みを割り当てることが好ましい。１つの実施形態では、チャンネルスケジューラ12は、チャンネルスケジューラ12が現在サービスしている待ち行列におけるゼロと最も大きい重みとの間の均一な分配にしたがって、再接続した遠隔局６の待ち行列へ重みをランダムに割り当てる。別の実施形態では、基地局４は再接続した遠隔局６の重みを、遠隔局６に関係する最後の基地局から陸線を介して受信する。
【００５３】
代わりの実施形態では、チャンネルスケジューラ12は、基地局４との過去の関係付けをもつための“部分的クレジット（partial credit）”を、再接続した遠隔局６へ与える。チャンネルスケジューラ12は、先のサービス間隔が“ｎ”にまたがっている時間スロットの数を判断し、この時間スロット数の履歴を維持する。
【００５４】
“ｍｉ”は、先のサービス間隔の間に、基地局４が遠隔局ｉからＤＲＣを受信したことを示す。遠隔局ｉに関係する待ち行列の重みは、ステップ310において次に示すようにデクレメントされる：
Ｗｉ＝Ｗｉ−ｍｉ／ｎ×Ｗｍｉｎ
なお、
Ｗｉ＝待ち行列ｉの重み
Ｗｍｉｎ＝遠隔局へ送るデータをもつ待ち行列の最小の重み
ｍｉ＝基地局が遠隔局ｉからＤＲＣを受信した先のサービス間隔中の時間スロットの数
ｎ＝先のサービス間隔がまたがっている時間スロットの数。
【００５５】
図７ないし９は、実施形態にしたがってステップ110（図４参照）において実行される論理を示すフローダイヤグラムである。ステップ402において、Selected Queueの識別を、関係する遠隔局６へ送るためのデータを含む第１のデータの待ち行列であるとして初期設定する。ステップ402ないし422では、チャンネルスケジューラ12は、最初の待ち行列または異なるデータの待ち行列が、関係する遠隔局６へ送るために選択されるデータを含むか、否かを判断する。次にステップ406においてNext Queueが検索され、ステップ408においてNext Queueがデータを含むか、否かを判断する。Next Queueがデータを含まないときは、ステップ406へ戻って、次のデータの待ち行列を選択する。さもなければ、Next Queueがデータを含むときは、Current Queueの識別はNext Queueへ割り当てられる。Current Queueの重みがSelected Queueの重みを上回るときは、ステップ412からステップ406へ戻って、次のNext Queueを検索する。さもなければ、ステップ414において、Current Queueの重みがSelected Queueの重みよりも小さいか、否かを判断する。Current Queueの重みがSelected Queueの重みよりも小さいときは、ステップ414からステップ420へ移り、Current Queueの識別をSelected Queueへ割り当てる。
【００５６】
さもなければ、ステップ412および414における論理は、ステップ416に進んだときは、Current Queueの重みとSelected Queueの重みは等しいと規定する。ステップ424では、次の条件を満たしているときは、Current QueueをSelected Queueとして割り当てる：
１）Current Queueに関係するデータを受信する瞬間レートが、Selected Queueに関係するデータを受信する瞬間レートを上回っているとき（ステップ416）；および、
２）Current Queueに割り当てられたサービス間隔が、Current Queueに割り当てられたサービス間隔中に、データの部分的な残り（fractional remainder）を残して、Current Queue内に記憶されている全てのデータを使い尽くすとき、このような部分的な残りが、Selected Queueに割当てられたサービス間隔中にSelected Queue内のデータの部分的な残りを上回らないとき（ステップ418ないし422）。
【００５７】
さもなければ、ステップ406へ戻って、Next Queueを選択する。
【００５８】
図１０ないし１３は、待ち行列を選択して、関係する遠隔局６へ送るステップ110において実行される論理の第２の実施形態を示すフローダイヤグラムを示している。この実施形態では、各基地局４は、（８ないし１６の時間スロットのような）一定の継続期間をもち、全ての関係する基地局６へ制御信号を定期的に送ると仮定する。実施形態にしたがって、基地局４はこの制御信号を４００ミリ秒ごとに送る。この制御信号の伝送中は、何れの待ち行列40（図２参照）からのデータも関係する遠隔局６へ送られない。図１０ないし１３に示した実施形態の目的は、ステップ108において判断された長さをもつサービス間隔の間において、次に制御信号を送り始める前に、伝送を完了することができるデータの待ち行列のみを選択することである。
【００５９】
ステップ499ないし507では、待ち行列の全てをフィルタして、何れの待ち行列が、次に制御信号を送り始める前に完了する候補であるかを判断する。ステップ499では、例えば、次の制御信号の伝送開始のスケジュールされた時間から、次のスケジュールされたサービス間隔の開始を減算することによって、次に制御信号を送るまでの時間“Ｔ”を判断する。ステップ501では、ステップ106において判断された待ち行列に関係する遠隔局６へ送る瞬間レートに基づいて、ステップ108において判断された各待ち行列に関係する一定長のサービス間隔が、時間Ｔ内で送られるか、否かを判断する。実施形態にしたがって、ステップ501ではサービス間隔の長さをＴと比較する。ステップ502では、Next Queueがデータを含むか、否かを判断する。Next Queueがステップ501および502において条件を満たすときは、Next Queueの識別はSelected Queueへ割り当てられる。
【００６０】
ステップ504ないし508では、残りのデータの待ち行列を調べて、次に制御信号の伝送を開始する前に伝送が完了している（ステップ108において判断された）サービス間隔に関係するデータの待ち行列を判断する。Current Queueは、ステップ507および508に記載した基準を満たすとき、Next Queueとして割り当てられる。次にステップ512ないし526では、図７ないし９のステップ412ないし426に関連して既に記載したのと類似したやり方で、待ち行列の重みにしたがって選択プロセスを実行する。しかしながら、図１０ないし１３の実施形態では、次の制御信号の伝送が開始する前に完了する割り当てられたパケット長をもつデータの待ち行列のみが、関係する待ち行列の重みに基づいて選択するための候補である。
【００６１】
図１４および１５は、伝送する待ち行列を選択するために、図４のステップ110において実行される論理の第３の実施形態を示すフローダイヤグラムを示している。この実施形態では、遠隔局６を選択する加入者は、データ伝送について最低の平均レートを保証されている。このような割り増し料金のついた遠隔ユニットの各々について、チャンネルスケジューラ12はタイマを保持しており、このタイマは、残りの待ち行列に関係する重みに関係なく、割り増し料金の付いた待ち行列への伝送をスケジュールするようにチャンネルスケジューラ12に警告する。特定のタイマについての時間間隔は、顧客に保証された平均データレート、ステップ108においてこのデータの待ち行列へ割り当てられるサービス間隔（表１の真ん中の列を参照）、およびステップ106において判断されるデータ受信についての瞬間データレートに基づいて判断される。したがって、割り増し料金の付いた待ち行列のタイマに関係する時間間隔は、これらの値に対して動的である。実施形態にしたがって、タイマがリセットされるたびに判断されるタイマの時間間隔を次に示す：
Ｔｊ＝Data Size(Lｊ)/rｊ
なお、
Ｔｉ          ＝割り増し料金の付いた待ち行列ｊに対するタイマの時間間隔
Data Size(Lｊ)＝割り増し料金の付いた待ち行列ｊに割り当てられるサービス間隔内で送られるデータ品質
rｊ            ＝割り増し料金の付いた待ち行列ｊに関係する割り増し料金付きの加入者に対して保証される平均データ伝送レート。
【００６２】
タイマは、２つのイベントの何れかにおいてリセットされる。タイマのリセットを開始する第1のイベントは、タイマの時限が切れることである。タイマのリセットを開始する第２のイベントは、図７ないし９を参照して既に記載したやり方で、関係する割り増し料金の付いたデータの待ち行列を関係する重みに基づいて選択することである。
【００６３】
ステップ606ないし610では、Next Queueが、データの受信についての最低平均レートである資格を与えられた割り増し料金の付いた待ち行列であるか、否かを判断し、そうであるときは、この割り増し料金の付いた待ち行列に関係するタイマが切れているか、否かを判断する。タイマが切れているときは、ステップ612ではNext Queueの識別をSelected Queueへ割り当てて、ステップ110を完了する。次に既に記載したようにステップ112では、選択された待ち行列の重みが更新される。ステップ614においてタイマが切れている重みの待ち行列がないときは、ステップ616では、図７ないし９を参照して既に記載したやり方で、待ち行列の重みに基づいて次のサービス間隔において送る待ち行列を選択する。ステップ618では、ステップ616において選択された待ち行列が、関係するタイマをもつ割り増し料金の付いた待ち行列であることが分かると、ステップ620では選択された待ち行列に関係するタイマのリセットを開始する。
【００６４】
既に概略的に記載したように、ステップ620では、特定の割り増し料金の付いたデータの待ち行列に関係するタイマは、関係する重みに基づいてそれを選択した後でリセットされる。関係するタイマは、データの待ち行列を選択する前に切れたときもリセットされる。したがってタイマは、重みに基づいてデータの待ち行列を選択するように指示されている論理をオーバーライドして、この加入者が割り増し料金の付いたデータの待ち行列に関係して、データ受信についての保証された最低平均レートを受信することを保証するように、チャンネルスケジューラ12に警告する。
【００６５】
図１６は、ステップ（図４参照）において重みを更新するプロセスの代わりの実施形態を示している。この代わりの実施形態では、最も小さい重みをもたない待ち行列を選択することができる。伝送レートは揮発性であり、このために最も小さい重みをもつ待ち行列をしばしば選択することが好都合である。例えば、要求されたレートが一時的に遅い時間スロット中に、待ち行列は最も小さい待ち行列をもつ。次の時間スロット中にレートが増すときは、より速いレートで伝送を行うことができる。いくつかの時間スロットを待つことにより、小さい重みの待ち行列からより速い要求レートで伝送することができる。
【００６６】
代わりの実施形態は、ステップ702において、値ＭおよびＫの和を判断することによって開始される。Ｍは全ての待ち行列の中の最小の重みであって、この全ての待ち行列には、無効のＤＲＣ値を送るか、それを含むデータをもたない待ち行列が含まれる。Ｋはオフセットであり、望ましさの尺度に基づいて待ち行列が選択される一定の範囲の重みの値を規定するのに使用されるオフセットである。
【００６７】
ＭとＫとの和を判断した後で、ステップ704では、待ち行列を選択するために望ましさの尺度を使用するか、否かに関して決定する。望ましさの尺度は、（Ｍ＋Ｋ）以上の重みと、有効なＤＲＣと送信データとをもつ待ち行列間の選択に使用される。
【００６８】
最初に、有効なＤＲＣと送信データとをもつ全ての待ち行列を評価して、（Ｍ＋Ｋ）の和よりも大きい重みをもつ待ち行列がいくつあるかを判断する。さらに、有効なＤＲＣおよび送信データをもつ全ての待ち行列が、（Ｍ＋Ｋ）の和よりも大きい重みをもつときは、ステップ706において、それらの待ち行列間で最も小さい重みの待ち行列が選択される。有効なＤＲＣおよび送信データをもつ待ち行列が、（Ｍ＋Ｃ）以下の重みをもつときは、ステップ708において望ましさの尺度にしたがって、これらの待ち行列の１つが選択される。
【００６９】
ステップ706または708において待ち行列が選択されると、（ステップ710に示されているように）待ち行列の選択は完了し、続いて図４に示したステップ110または112からプロセスが行われる。
【００７０】
図１７は、図１６に示した待ち行列選択方法の例示的な実施形態の1つを示したより詳しいフローチャートである。図１７では、ステップ702において（Ｍ＋Ｋ）を判断した後で、有効なＤＲＣおよび送信データをもつ各待ち行列が評価され、１つの待ち行列が選択されて、ステップ110へ戻る。
【００７１】
例示的な実施形態では、第1のステップ702では、（Ｍ＋Ｋ）の和を再び判断する。データおよび有効な待ち行列ＤＲＣをもつ待ち行列がないときは、待ち行列は選択されず、方法はステップ772へ進む（図４のフローへ戻る）。データおよび有効なＤＲＣをもつ待ち行列が１つだけリスト内にあるときは、この待ち行列は戻される。さもなければ、ステップ754および756において、データおよび有効なＤＲＣをもつ２以上の待ち行列からＱＳＥＬおよびＱＣＵＲが割り当てられる。ＱＳＥＬは現在選択された待ち行列を表わし、ＱＣＵＲは現在の待ち行列がＱＳＥＬと比較されいていることを表わしている。データおよび有効なＤＲＣをもつ各待ち行列はＱＳＥＬと比較され、一定の選択基準が満たされるときは、待ち行列は現在のＱＳＥＬに代わる。全ての待ち行列が評価された後で、残りのＱＳＥＬは伝送するための選択された待ち行列であり、ステップ722において戻される。
【００７２】
ステップ758では、選択された待ち行列ＱＳＥＬの重みは（Ｍ＋Ｋ）と比較される。ＱＳＥＬの重みが（Ｍ＋Ｋ）よりも大きいときは、ステップ764においてＱＳＥＬとＱＣＵＲとを置換するか、否かについてのステップ762における決定は、何れの待ち行列がより小さい重みをもつかのみに基づいている。ステップ758において、選択された待ち行列ＱＳＥＬの重みが（Ｍ＋Ｋ）以下であるときは、ステップ760において現在の待ち行列ＱＣＵＲの重みは（Ｍ＋Ｋ）と比較される。ＱＳＥＬのみが（Ｍ＋Ｋ）以下であるときは、ＱＣＵＲは選択されず、方法はステップ770へ進む。ＱＳＥＬとＱＣＵＲとの両者の重みが（Ｍ＋Ｋ）以下であるときは、ステップ766において待ち行列は望ましさの尺度にしたがって評価される。望ましさの尺度にしたがって、ＱＣＵＲがＱＳＥＬよりも望ましいと考えられるときは、ステップ764においてＱＣＵＲは新しく選択された待ち行列ＱＳＥＬになる。
【００７３】
各待ち行列が推定された後で、ステップ770では、送信データおよび有効なＤＲＣをもち、まだ評価されていない待ち行列を検査する。まだ評価されていないこのような待ち行列が増えると、ステップ768において次のＱＣＵＲとして1つの待ち行列が選択され、ステップ758の前に戻って評価される。まだ評価されていない待ち行列がなくなると、選択された待ち行列ＱＳＥＬはステップ772へ戻される。
【００７４】
本発明のいくつかの代わりの実施形態は、Ｋを判断するために使用される方法において異なる。いくつかの実施形態では、Ｋは単に定数である。他の実施形態では、Ｋは、シーケンスを選択する各ラウンドの最初に計算される。いくつかの代わりの実施形態はさらに、使用される望ましさの尺度においても異なる。Ｋまたは望ましさの尺度を判断するいくつかの方法は、本発明の技術的範囲から逸脱せずに使用することができる。
【００７５】
“変更サービス等級（Modifed Grade of Service, GOS）”のアルゴリズムを使用した特定の実施形態において、Ｋは、システム内の遠隔局の数に依存しない定数である。次の式にしたがうフィルタされた平均スループットは、各ユーザおよび関係する待ち行列に対して維持される：
Average Throughput={（11/TC）＊Old Average Throughput}+(1+TC＊Rate)  （１）
なお、Average Throughputは、待ち行列の望ましさの尺度の値を計算するのに使用される各待ち行列に対する平均スループットであり、TCは時間定数（time constant）であり、Old Average ThroughputはAverage Throughputの前の値であり、Rateは各時間スロットにおいて待ち行列から送るのに使用されるビットレートである。Average Throughputは、各伝送の時間スロットにおいて各待ち行列ごとに更新される。各時間スロットにおいて選択された待ち行列を除く全ての待ち行列において、Rateはゼロになる。ステップ706および766において評価される待ち行列の望ましさの尺度の値は、次の式にしたがって判断される：
Desirability Metric=Current Requested Rate-Average Throughput    （２）
なお、Current Requested Rateは、待ち行列のＤＲＣのレートであり、Average Throughputは式（１）において計算される。
【００７６】
当業者には、望ましさの尺度および更新された平均スループットとを判断するのに、他の式を使用できることが分かるであろう。例えば、平均スループットを更新するための式では、先の２つの要求レート値のような、現在の値よりも大きい要求レート値を考慮に入れてもよい。さらに加えて、ＴＣは、システム内の活動状態のユーザ数か、または先の要求レートの変動に基づいて、時間にしたがって変化する。望ましさの尺度を計算するのに使用できる代わりの式のいくつかについては別途記載する。
【００７７】
変更ＧＯＳのアルゴリズムは、ＤＲＣのレートが時間にしたがって変化する環境における待ち行列の選択を最適化できるので好都合である。したがって、特定の時間スロットの中で最も小さい重みをもつ待ち行列であっても、この待ち行列がＤＲＣの要求レートにおいて一時的な低下を経験するときは、これは選択されない。変更ＧＯＳのアルゴリズムは、次の時間スロットの1つにおいてレートが増加することを期待して、このような待ち行列の伝送において制限された範囲の遅延を許している。
【００７８】
“変更ＧＯＳの高ＤＲＣ（Modified GOS High DRC）”のアルゴリズムを使用する代わりの実施形態では、望ましさの尺度値は、式（１）にしたがって計算された平均スループットに等しい。このアルゴリズムでは、全体的なスループットを僅かに低減するが、コンピュータ処理における複雑さをより緩和することが必要である。変更ＧＯＳの高ＤＲＣのアルゴリズムでは、各シーケンスごとにフィルタされた平均スループットを維持する必要はない。
【００７９】
“ハイブリッド”のアルゴリズムを使用する別の代わりの実施形態では、望ましさの尺度値は、Average Throughputによって除算されるRateに等しい。ハイブリッドのアルゴリズムでは、スループットを犠牲にして、要求レートが平均レートを上回る割合に基づいて待ち行列を選択することによって、伝送する待ち行列を選択する際により高い“公平性”の度合いを実現する。例えば、このアルゴリズムでは、７６．８Ｋの要求されるRateと３０ＫのAverage Throughputとを第１のユーザがもつことを、１２２８．８Ｋの要求されるRateと９００ＫのAverage Throughputを第２のユーザがもつ代わりに選択する。第２のユーザのレートのスパイクを利用することによって、より高い全スループットを実現できるが、第１のユーザの現在のレートが平均スループットの２倍以上であるので、ハイブリッドのアルゴリズムは第１のユーザを選択する。
【００８０】
部分的に最適なアルゴリズムでは、ハイブリッドのアルゴリズムは、ユーザの数にしたがってＫを変化させて、“変更されたハイブリッドのアルゴリズム”を生成することによって変更される。変更されたハイブリッドのアルゴリズムでは、Ｋはユーザの数に逆比例し、望ましさの尺度値はAverage Throughputによって除算されるRateに等しい。ユーザ数にしたがってＫを変化させて、変更されたＧＯＳおよび変更ＧＯＳの高ＤＲＣのアルゴリズムを変更することによって、同様の代わりの部分的に最適なアルゴリズムが生成される。
【００８１】
代わりの部分的に最適な実施形態では、ハイブリッドのアルゴリズムは、ユーザ数にしたがってＫを変化させて“変更されたハイブリッド”のアルゴリズムをを生成することによって変更される。変更されたハイブリッドのアルゴリズムは、スループットを犠牲にして“公平性”の度合いを高めようとしている。
【００８２】
図１８は、本発明の例示的な実施形態にしたがって構成された順方向リンクのアーキテクチャのブロックダイヤグラムである。データはデータパケットに分割され、ＣＲＣのエンコーダ712へ供給される。各データパケットにおいて、ＣＲＣのエンコーダ712はフレーム検査ビット（例えば、ＣＲＣのパリティビット）を生成し、コードの末尾のビットを挿入する。ＣＲＣのエンコーダ712からのフォーマットされたパケットは、データ、フレーム検査およびコードの末尾のビット、並びに別途記載する他のオーバーヘッドのビットを含む。例示的な実施形態では、エンコーダ714はコード化フォーマットにしたがってフォーマットされたパケットをコード化しており、米国特許出願第08/743,688号（“SOFT DECISION OUTPUT DECODER FOR DECODING CONVOLUTIONALLY ENCODED CODEWORDS”）に記載されていて、これは1996年11月６日に出願され、本発明の譲受人に譲渡され、ここでは参考文献として取り上げている。当業者には、他の周知のコード化フォーマットも使用でき、本発明の技術的範囲内であることが分かるであろう。エンコーダ714からのコード化されたパケットはインターリーバ716へ供給され、インターリーバ716はパケット内のコード符号を記録する。インターリーブされたパケットはフレームパンクチャ素子（frame puncture element）718へ供給され、フレームパンクチャ素子718は別途記載するやり方でパケットの一部を取除く。穴を空けられたパケット（punctured packet）は乗算器720へ供給され、乗算器720はスクランブラ722からのスクランブリングシーケンスでデータをスクランブルする。パンクチャ素子718およびスクランブラ722は、上述の米国特許出願第08/963,386号に詳しく記載されている。乗算器720からの出力は、スクランブルされたパケットを含む。
【００８３】
スクランブルされたパケットは、可変レート制御装置730へ送られ、可変レート制御装置730は、パケットをＫの並列の同位相および直交チャンネルへデマルチプレックスする（なお、ここではＫはデータレートに依存する）。例示的な実施形態では、スクランブルされたパケットは最初に同位相（Ｉ）および直交（Ｑ）の流れにデマルチプレックスされる。例示的な実施形態では、Ｉの流れは偶数の指標の付いた符号を含み、Ｑの流れは奇数の指標の付いた符号を含んでいる。各流れはさらにＫの並列チャンネルへデマルチプレックスされ、各チャンネルの符号レートは全てのデータレートに対して固定される。各流れのＫチャンネルは、ウオルシュカバー素子732へ供給され、ウオルシュカバー素子732は各チャンネルをウオルシュ関数でカバーして、直交チャンネルを供給する。直交チャンネルデータは利得素子734へ供給され、利得素子734はデータを基準化（scale）して、全てのデータレートについて各チップ当りの一定の全エネルギ（constant total-energy-per-chip）（したがって、一定の出力電力）を維持する。基準化されたデータは利得素子734からマルチプレクサ（multiplexer, MUX）760へ供給され、ＭＵＸ760はデータをプリアンブルで多重化する。プリアンブルについては、上述の米国特許出願第08/963,386号に詳しく記載されている。ＭＵＸ760からの出力は、マルチプレクサ（multiplexer, MUX）762へ供給され、ＭＵＸ762はトラヒックデータ、電力制御ビット、およびパイロットデータを多重化する。ＭＵＸ762の出力は、ＩウオルシュチャンネルおよびＱウオルシュチャンネルを構成する。
【００８４】
例示的な実施形態では、順方向リンクのパイロットチャンネルはパイロット信号を供給し、遠隔局６はパイロット信号を使用して、最初の捕捉、位相の回復、タイミングの回復、および比率の結合を行う。パイロット信号は、ＩＳ−９５規格にしたがうＣＤＭＡの通信システムにおいて同様に使用されている。例示的な実施形態では、パイロット信号は、遠隔局６がＣ／Ｉ測定を行うのにも使用される。
【００８５】
図１８には、さらに、例示的な実施形態の順方向リンクのパイロットチャンネルのブロックダイヤグラムが示されている。例示的な実施形態では、パイロットデータは全てゼロ（または全て１）の数列を含み、これは乗算器756へ供給される。乗算器756はパイロットデータをウオルシュコードＷ０でカバーする。ウオルシュコードＷ０は全てゼロの数列であるので、乗算器756の出力はパイロットデータである。パイロットデータはＭＵＸ762によって多重化され、Ｉウオルシュチャンネルへ供給され、Ｉウオルシュチャンネルは複素数乗算器814（図１９参照）内で短いＰＮＩコードによって拡散される。
【００８６】
さらに加えて、図１８には電力制御チャンネルの例示的なブロックダイヤグラムが示されている。逆方向電力制御（Reverse Power Control, RPC）のビットは符号リピータ750へ供給され、符号リピータ750は、各ＲＰＣビットを所定回数だけ反復する。反復されたＲＰＣビットはウオルシュカバー素子752へ供給され、ウオルシュカバー素子752はＲＰＣの指標に対応するウオルシュカバーでビットをカバーする。カバーされたビットは利得素子754へ供給され、利得素子754は、変調する前にビットを基準化して、一定の全伝送電力を維持する。例示的な実施形態では、ＲＰＣのウオルシュチャンネルの利得は正規化され、全ＲＰＣチャンネルの電力は全可変伝送電力に等しくなる。ウオルシュチャンネルの利得は、全ての活動状態の遠隔局６への確実なＰＰＣの伝送を維持する一方で、全基地局の伝送電力の効率的な利用についての時間関数として変化することができる。例示的な実施形態では、非活動状態の遠隔局６のウオルシュチャンネルの利得はゼロにセットされる。ＲＰＣのウオルシュチャンネルは、遠隔局６からの対応するＤＲＣチャンネルからの順方向リンクの品質測定の推定値を使用して、自動的に電力を制御することができる。利得素子754からの基準化されたＲＰＣビットはＭＵＸ762へ供給される。
【００８７】
図１９には、データを変調するのに使用される例示的な変調器のブロックダイヤグラムが示されている。ＩウオルシュチャンネルおよびＱウオルシュチャンネルは、それぞれ加算器812ａおよび812ｂへ供給され、Ｋウオルシュチャンネルを加算して、それぞれ信号ＩｓｕｍおよびＱｓｕｍを供給する。ＩｓｕｍおよびＱｓｕｍの信号は複素数乗算器814へ供給される。複素数乗算器814はさらに短いコードの生成器838から短いＰＮＩおよびＰＮＱを受信し、次の式（３）にしたがって２つの複素数の入力を乗算する：
(Ｉｍｕｌｔ＋ｊＱｍｕｌｔ)
＝（Ｉｓｕｍ＋ｊＱｓｕｍ）・（ＰＮ Ｉ＋ｊＰＮ Ｑ）
＝（Ｉｓｕｍ・ＰＮ Ｉ−Ｑｓｕｍ・ＰＮ Ｑ）＋
ｊ（Ｉｓｕｍ・ＰＮ Ｑ＋Ｑｓｕｍ・ＰＮ Ｉ）
（３）
なお、ＩｍｕｌｔおよびＱｍｕｌｔは、複素数乗算器814からの出力であり、ｊは複素数を表わしている。ＩｍｕｌｔおよびＱｍｕｌｔの信号は、フィルタ816ａおよび816ｂへそれぞれ供給され、信号をフィルタする。フィルタ816ａおよび816ｂからのフィルタされた信号は、乗算器818ａおよび818ｂへそれぞれ供給され、それぞれ同位相の正弦波ＣＯＳ（ｗｃｔ）および直交の正弦波ＳＩＮ（ｗｃｔ）で信号を乗算する。Ｉの変調信号およびＱの変調信号は加算器820へ供給されて、加算器820は信号を加算して、順方向の変調された波形Ｓ（ｔ）を供給する。
【００８８】
図示されている例示的なトラヒックチャンネルのブロックダイヤグラムは、順方向リンク上でのデータのコード化および変調を支援する多数のアーキテクチャの１つである。ＩＳ−９５規格にしたがうＣＤＭＡシステム内の順方向リンクのトラヒックチャンネルのためのアーキテクチャのような他のアーキテクチャも使用可能であり、本発明の技術的範囲内である。
【００８９】
例えば、当業者には、この複素数乗算器814および短いコードの生成器838は疑似雑音（pseudonoise, PN）拡散器に置換でき、ＰＮ拡散器では、複素数乗算の代わりにＰＮの短いコードによって信号の簡単な乗算を行うことが分かるであろう。さらに加えて、エンコーダ714には、高速コーディング（turbo-coding）、たたみこみコーディング、およびソフトな決定またはブロックコーディングの他の形態を含むいくつかの順方向のエラー補正技術を使用してもよい。さらに加えて、インターリーバ716は多数のインターリービング技術を使用することができ、このインターリービング技術には、ブロックインターリービング、例えばビット反転インターリービングまたは疑似ランダムインターリービングを含む。
【００９０】
本発明の好ましい実施形態であると現在考えられているものを示し、記載してきたが、当業者には、本発明の技術的範囲から逸脱せずに、種々の他の変更を行うことができ、対応する実施形態に置換できることが分かるであろう。さらに加えて、本明細書に記載した中心的な発明の概念から逸脱せずに、本発明の教示に特定の状況を適応させて、多くの変更を行うことができる。したがって、本発明は、記載されている特定の実施形態に制限されないが、本発明の特許請求項の技術的範囲内に含まれる全ての実施形態を含むことが意図されている。
【図面の簡単な説明】
【図１】  本発明の実施形態にしたがう通信ネットワークを示す図。
【図２】  本発明の実施形態にしたがって構成されている、基地局制御装置と基地局装置とを示すブロックダイヤグラム。
【図３】  本発明の実施形態にしたがって構成されている、遠隔局装置を示すブロックダイヤグラム。
【図４】  図２に示したチャンネルスケジューラの実施形態におけるスケジューリングアルゴリズムの実行を示すフローダイヤグラム。
【図５】  図４に示したスケジューリングアルゴリズムの実施形態を実行するタイミングを示すダイヤグラム。
【図６】  図４において識別された実施形態において選択された待ち行列に対する重みを更新するためのプロセスの実施形態を示すフローダイヤグラム。
【図７】  図４において識別されたサービス間隔でデータの伝送を受信する待ち行列を選択するプロセスの第１の実施形態を示すフローダイヤグラム。
【図８】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第１の実施形態を示すフローダイヤグラム。
【図９】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第１の実施形態を示すフローダイヤグラム。
【図１０】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第２の実施形態を示すフローダイヤグラム。
【図１１】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第２の実施形態を示すフローダイヤグラム。
【図１２】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第２の実施形態を示すフローダイヤグラム。
【図１３】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第２の実施形態を示すフローダイヤグラム。
【図１４】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第３の実施形態を示すフローダイヤグラム。
【図１５】  図４において識別されたサービス間隔でデータ伝送を受信する待ち行列を選択するプロセスの第３の実施形態を示すフローダイヤグラム。
【図１６】  図４において識別された実施形態において選択された待ち行列に対する重みを更新するための代わりのプロセスを示す高レベルのフローダイヤグラム。
【図１７】  図１６に示されているプロセスの実施形態についての詳細なフローダイヤグラム。
【図１８】  本発明の例示的な順方向リンクのアーキテクチャのブロックダイヤグラム。
【図１９】  本発明の例示的な順方向リンクのアーキテクチャのブロックダイヤグラム。
【図１】
0004559008.tif 000004
【図２】
0004559008.tif 000005
【図３】
0004559008.tif 000006
【図４】
0004559008.tif 000007
【図５】
0004559008.tif 000008
【図６】
0004559008.tif 000009
【図７】
0004559008.tif 000010
【図８】
0004559008.tif 000011
【図９】
0004559008.tif 000012
【図１０】
0004559008.tif 000013
【図１１】
0004559008.tif 000014
【図１２】
0004559008.tif 000015
【図１３】
0004559008.tif 000016
【図１４】
0004559008.tif 000017
【図１５】
0004559008.tif 000018
【図１６】
0004559008.tif 000019
【図１７】
0004559008.tif 000020
【図１８】
0004559008.tif 000021
【図１９】
0004559008.tif 000022