(57)【要約】【課題】通信システムにおいて送信をスケジューリングするための適応型遅延管理を達成すること。【解決手段】    異なるサービス品質（ＱｏＳ）要求を有する資源を割り当てるための適応型遅延管理手段及び方法。順方向リンク（ＦＬ）スケジューラは、送信待ち状態のデータ待ち行列を、ベストエフォート（ＢＥ）及び優先転送（ＥＦ）等の優先度クラスに従って取り扱うことによって送信インスタンスを準備する。複数の待ち行列からのデータビットが送信インスタンス内に埋め込まれる。一組の送信候補を生成して選択するため及び前記候補の組から次の送信インスタンスを構築するために様々なメトリックが使用される。【選択図】        図１０
2007536827.tif 000002
【特許請求の範囲】
【請求項１】
無線通信システムにおいて送信インスタンスをスケジューリングする方法であって、
複数のモバイルユーザーからチャネル状態インジケータを受信することであって、前記チャネル状態インジケータは、順方向リンク通信に対応することと、
前記複数のモバイルユーザーに対して遅延基準を決定することと、
前記複数のモバイルユーザーに対して送信スケジュールを決定することであって、前記送信スケジュールは、前記遅延基準の関数であること、とを具備する方法。
【請求項２】
無線通信システムにおいて送信インスタンスをスケジューリングする方法であって、
複数の送信待ち行列を評価して各送信待ち行列に関連するアプリケーションフローの遅延影響度及びスループット影響度を識別することと、
一組の候補送信インスタンスを前記複数の送信待ち行列から生成することと、
１つの候補送信インスタンスを前記組から選択することと、
前記選択された候補送信インスタンスを送信のために準備すること、とを具備する方法。
【請求項３】
前記候補送信インスタンスの組を生成することは、
各待ち行列に関するビットメトリックを生成することと、
各待ち行列に関するビットスタッフィングメトリックを生成すること、とを具備する請求項２に記載の方法。
【請求項４】
１つの候補送信インスタンスを選択することは、
パケットメトリックを前記ビットメトリックの関数として生成することと、
前記組内の候補送信インスタンスに関する前記パケットメトリックを比較すること、とを具備する請求項３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本特許出願は、本特許出願の譲受人に対して譲渡されておりさらに本明細書において参照することによって明示で本明細書に組み入れられている、"ADAPTIVE DELAY MANAGEMENT"（適応型遅延管理）という題名の仮特許出願番号 ６０／５６８，６５０(出願日:  ２００４年５月５日) に対する優先権を主張するものである。
【０００２】
本特許出願は、本特許出願の譲受人に対して譲渡されておりさらに本明細書において参照することによって明示で本明細書に組み入れられている、"ADAPTIVE DELAY MANAGEMENT"（適応型遅延管理）という題名の仮特許出願番号 ６０／６２５，６６０(出願日:  ２００４年１１月４日) に対する優先権を主張するものである。
【０００３】
本発明は、一般的には、通信に関するものである。本発明は、より具体的には、無線通信システムにおいて適応型遅延管理を用いた送信スケジューリングに関するものである。
【背景技術】
【０００４】
無線通信システムは、回線交換型、すなわち固定資源割当型技術を用いた通信を処理するシステムと、パケット交換型、すなわち動的資源割当型技術を用いた通信を処理するシステムと、を含む。回線交換及びパケット交換は両方とも、高容量が可能なネットワークにおいて使用することができる。回線交換通信システムにおいては、送信者と受信者との間において専用通信路が確立され、送信機と受信機との間のネットワーク資源は、転送開始前は静止しているとみなされ、従って「回線」が作り出される。資源は、全転送中にわたって回線専用の状態であり、メッセージ全体が同じ経路をたどる。パケット交換ネットワークにおいては、メッセージがパケットに分割され、これらのパケットの各々は、行先まで異なる経路をたどることができる。これらのパケットは、受信された時点で、原メッセージを検索するために再コンパイルされる。パケット交換システムにおいては、メッセージ又はメッセージの一部を表すパケットが、ノード間において個々にルーティングされる。パケットは、好都合な経路を通じて行先までルーティングされる。換言すると、同じ２つのホスト間を移動するすべてのパケットが、単一のメッセージの一部であっても必ずしも同じ経路をたどるわけではない。
【０００５】
パケット交換システム、又は共有パケットデータシステムにおいては、Voice over Internet Protocol（ＶｏＩＰ）サービスを用いて回線交換音声通信をエミュレーションすることができる。ＶｏＩＰは、典型的には、遅延の影響を受けやすいアプリケーション又はサービスであり、従って、パケット引き渡しに関する遅延上の制約を満たすためにサービス品質（ＱｏＳ）機構が使用される。その他のサービス及びその他の型の送信も、ＱｏＳを保証するための様々な遅延上の要求又は目標を有する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、通信システムにおいて送信をスケジューリングするための適応型遅延管理が必要である。
【課題を解決するための手段】
【０００７】
本明細書において開示される方法及び装置の特長、性質、及び利点は、下記の詳細な説明と図面を併用することでさらに明確になる。同一のものについては図面全体に渡って同一の参照符号を付けることとする。
【発明を実施するための最良の形態】
【０００８】
異なるＱｏＳ要求を有するサービス及びアプリケーションをサポートする通信システムの動作は、最適でない場合及び非効率的な場合がある。例えば、ＶｏＩＰアプリケーションは、遅延に関する要求を有する。一方法は、負荷及びカバレッジとは無関係に複数のユーザーに関して平等な遅延上の制約を設けることによって音声をエミュレーションする。平等な遅延を保証するために資源を割り当てて最適化を避けることはシステム容量を増大させる可能性があるため、前記アプローチ法は最適でない。一実施形態においては、システム容量は、様々なユーザーに関して平等でない遅延を提供することによって増大させることができ、この場合は、負荷及びカバレッジの関数として資源が割り当てられる。  
以下の説明は、１ｘＥＶ−ＤＯの動作をサポートする、すなわちＩＳ−８５６仕様をサポートするシステムの順方向リンク（ＦＬ）に関するスケジューリングアルゴリズムに関するものである。一実施形態においては、スケジューリングアルゴリズムは、ＦＬ容量を最大化することを試みる一方で様々なアプリケーションの品質ＱｏＳ要求を満たすために、様々な多ユーザーパケット及びショートパケットを利用する。前記スケジューリングアルゴリズムは、様々なアプリケーションの優先順位を設定する機構も提供する。該優先順位設定は、アプリケーションフローの型、特定のＱｏＳ要求、又はフローのその他の特性に基づくことができる。一実施形態においては、フローは、アプリケーションの遅延による影響度に基づいてＦＬでの送信に関するスケジュールが設定される。一側面においては、フローは、スループットによる影響度と均衡化された遅延による影響度に基づいて差別化される。次の説明は、１ｘＥＶ−ＤＯ仕様の改訂Ａに基づいて実装された場合のスケジューリング手段と方法について検討する一方で、これらのスケジューリング手段および方法は、代替システムに対してもさらに適用可能である。特に、概念は、ＩＳ−８５６仕様、具体的には、"cdma2000 High Rate Packet Data Air Interface Specification"（ｃｄｍａ２０００高速パケットデータエアインタフェース仕様）3GPP2 C.S0024 Ver.4.0, October 2002において定義される所定の部分組のサブタイプとユーザーが適合可能なシステムに対して適用可能である。
【０００９】
以下の説明では、「改訂Ａユーザー」又は「改訂Ａと適合可能なユーザー」、等の表現は、ＩＳ−８５６、具体的には、"cdma2000 High Rate Packet Data Air Interface Specification"（ｃｄｍａ２０００高速パケットデータエアインタフェース仕様）3GPP2 C.S0024-A Version 1.0, March 2004において定義されるメディアアクセスチャネル（ＭＡＣ）層及び物理層プロトコルサブタイプをサポートするアクセス端末（ＡＴ）を意味するために使用される。特に、改訂Ａユーザーは、拡張型順方向トラフィックチャネルＭＡＣプロトコルをサポートする。「Ｒｅｌ−０ユーザー」等の表現は、ＩＳ−８５６において定義されているが改訂Ａにおいて定義されるより新しいサブタイプをサポートしないＡＴを意味するために使用される。
【００１０】
符号分割多重接続ＣＤＭＡ法を採用する無線通信システムにおいては、一スケジューリング方法は、加入者装置の各々に対して、すべての符号チャネルを時間多重化に基づいて指定の時間間隔で割り当てる。中央通信ノード、例えば基地局ＢＳは、加入者との排他的通信を可能にするために加入者と関連づけられた一意の搬送波周波数又はチャネル符号を実装する。物理的接点リレー交換又はパケット交換を用いる地上通信線システムにおいてＴＤＭＡ法を実装することもできる。ＣＤＭＡシステムは、（１）本明細書においてはＩＳ−９５規格と呼ばれる「デュアルモード広帯域拡散スペクトルセルラーシステムに関するＴＩＡ／ＥＩＡ／ＩＳ−９５−Ｂ移動局−基地局適合性規格」、（２）本明細書においては３ＧＰＰと呼ばれる「第三世代パートナーシッププロジェクト」という名称のコンソーシアムによって提供され、文書番号３Ｇ  ＴＳ  ２５．２１１，３Ｇ  ＴＳ  ２５．２１２，  ３Ｇ  ＴＳ  ２５．２１３，３Ｇ  ＴＳ  ２５．２１４、及び３Ｇ  ＴＳ  ２５．３０２を含む一組の文書において具体化されており、本明細書においてはＷ−ＣＤＭＡ規格と呼ばれる規格、（３）本明細書においては３ＧＰＰ２と呼ばれる「第三世代パートナーシッププロジェクト２」という名称のコンソーシアムによって提供される規格、及び前名称はＩＳ−２０００  ＭＣであって本明細書においてｃｄｍａ２０００規格と呼ばれるＴＲ−４５．５、又は（４）その他の何らかの無線規格、等の１つ以上の規格をサポートするように設計することができる。
【００１１】
ＣＤＭＡシステムは、地上リンクを通じてのユーザー間の音声通信及びデータ通信を考慮する。ＣＤＭＡシステムにおいては、ユーザー間通信は、１つ以上の基地局を通じて行われる。無線通信システムにおいては、順方向リンクは、信号が基地局から加入者局に移動時に通るチャネルを意味し、逆方向リンクは、信号が加入者局から基地局に移動時に通るチャネルを意味する。加入者局の第１のユーザーは、逆方向リンクで基地局にデータを送信することによって、第２の加入者局の第２のユーザーと通信する。基地局は、第１の加入者局からデータを受信し、第２の加入者局に対応する基地局にデータをルーティングする。これらの加入者局の所在場所に依存して、単一の基地局又は複数の基地局によって両方の加入者局に対応することができる。いずれの場合においても、第２の加入者局に対応する基地局は、順方向リンクでデータを送る。加入者局は、第２の加入者局と通信する代わりに、対応基地局との接続を通じて地上インターネットと通信することもできる。ＩＳ−９５に準拠する無線通信、等においては、順方向リンク信号及び逆方向リンク信号は、分離された周波数帯域内において送信される。
【００１２】
図１Ａは、複数のユーザーをサポートする通信システム１００の例を示した図であり、本発明の少なくとも幾つかの側面及び実施形態を実装することができる。システム１００においては、様々なアルゴリズムの及び方法のうちのいずれかを用いて送信をスケジューリングすることができる。システム１００は、幾つかのセル１０２Ａ乃至１０２Ｇに関する通信を提供し、これらのセルの各々は、対応する基地局１０４Ａ乃至１０４Ｇによって対応される。該典型的実施形態においては、基地局１０４の一部は、複数の受信アンテナを有し、その他の基地局１０４は、１本の受信アンテナのみを有する。同様に、基地局１０４の一部は、複数の送信アンテナを有し、その他の基地局１０４は、単一の送信アンテナのみを有する。送信アンテナと受信アンテナの組合せには制約はない。従って、基地局１０４が複数の送信アンテナと単一の受信アンテナを有すること、又は複数の受信アンテナと単一の送信アンテナを有すること、又は単一又は複数の送信アンテナと受信アンテナを有することが可能である。
【００１３】
無線データ送信の需要増大及び無線通信技術を通じて入手可能サービスの拡大が、特定のデータサービスの開発につながっている。１つの該サービスは、高データ速度（ＨＤＲ）と呼ばれる。「ＨＤＲ仕様」と呼ばれる"EIA/TIA-IS856 cdma2000 High Rate Packet Data Air Interface Specification"（ＥＩＡ／ＴＩＡ−ＩＳ８５６  ｃｄｍａ２０００高速パケットデータエアインタフェース仕様）において１つの典型的ＨＤＲサービスが提案されている。ＨＤＲサービスは、一般的には、無線通信システムにおいてデータパケットを送信する効率的な方法を提供する音声通信システムに対するオーバーレイである。送信データ量が増大しさらに送信数が増加するのに従い、無線送信のために利用可能な限られた帯域幅が非常に重要な資源になっている。
【００１４】
図１Ｂは、エアインタフェース１２４を介してアクセス端末ＡＴ  １２６と通信するアクセスネットワークＡＮ  １２２を有する通信システム１２０に関するアーキテクチャ基準モデルを示した図である。一実施形態においては、システム１２０は、ＨＤＲ規格において指定されるような高データ速度ＨＤＲオーバーレイシステムを有する符号分割多重接続ＣＤＭＡシステムである。ＡＮ１２２は、エアインタフェース１２４を介して、ＡＴ１２６、及びシステム１２０内のその他のあらゆるＡＴ（図示されていない）と通信する。ＡＮ１２２は、複数のセクターを含み、各セクターは、少なくとも１つのチャネルを提供する。チャネルは、所定の周波数割当て内におけるＡＮ１２２とＡＴとの間の送信に関する通信リンクの組であると定義される。チャネルは、ＡＮ１２２からＡＴ１２６に送信するための順方向リンク（ＦＬ）と、ＡＴ１２６からＡＮ１２２に送信するための逆方向リンク（ＲＬ）と、を具備する。
【００１５】
データ送信に関して、ＡＮ１２２は、ＡＴ１２６からデータ要求を受信する。該データ要求は、データを送信するデータ速度、送信されるデータパケットの長さ、及びデータを送信するセクターを指定する。ＡＴ１２６は、ＡＮ１２２とＡＴ１２６との間のチャネルの品質に基づいてデータ速度を決定する。一実施形態においては、チャネルの品質は、搬送波−干渉比Ｃ／１によって決定される。代替実施形態は、チャネルの品質に対応するその他のメトリックを使用することができる。ＡＴ１２６は、ＤＲＣチャネルと呼ばれる特定のチャネルを介してデータ速度制御ＤＲＣメッセージを送信することによってデータ送信要求を出す。ＤＲＣメッセージは、データ速度部とセクター部を含む。データ速度部は、ＡＮ１２２がデータを送信するための要求データ速度を示し、セクター部は、ＡＮ１２２がデータを送信する時の送信セクターを示す。データ速度及びセクター情報の両方とも、典型的には、データ送信を処理するために要求される。データ速度部はＤＲＣ値と呼ばれ、セクター部はＤＲＣカバーと呼ばれる。ＤＲＣ値は、エアインタフェース１２４を介してＡＮ１２２に送られるメッセージである。一実施形態においては、各ＤＲＣ値は、予め決められたＤＲＣ値割当てに従った関連パケット長を有するデータ速度キロビット／秒に対応する。該割当ては、ヌルデータ速度を指定するＤＲＣ値を含む。実際には、ヌルデータ速度は、ＡＴ１２６がデータを受信できないことをＡＮ１２２に示す。例えば一状況においては、チャネルの品質は、ＡＴ１２６がデータを正確に受信する上で不十分である。
【００１６】
動作においては、ＡＴ１２６は、ＡＴ１２６が次のデータパケット送信を受信できるデータ速度を計算するためにチャネルの品質を連続的にモニタリングする。ＡＴ１２６は、対応するＤＲＣ値を生成する。該ＤＲＣ値は、データ送信を要求するためにＡＮ１２２に送信される。典型的には、データ送信はパケットに分割されることに注目すること。１つのデータパケットを送信するのに要する時間は、用いられるデータ速度の関数である。
【００１７】
このＤＲＣ信号は、チャネルスケジューラが各待ち行列と関連づけられた各々の遠隔局に関して情報を使用する（又は送信データを受信する）瞬間速度を決定するために使用する情報も提供する。一実施形態によれば、いずれかの遠隔局から送信されたＤＲＣ信号は、該遠隔局が複数の有効データ速度のうちのいずれかのデータ速度でデータを受信できることを示す。
【００１８】
ＨＤＲ送信をサポートしさらに複数のユーザーへの送信をスケジューリングするために適合された通信システムの一例が図２に示されている。以下において図２が詳細に説明される。具体的には、基地局８２０及び基地局コントローラ８１０がパケットネットワークインタフェース８０６とインタフェースする。基地局コントローラ８１０は、システム８００における送信に関するスケジューリングアルゴリズムを実装するためのチャネルスケジューラ８１２を含む。チャネルスケジューラ８１２は、いずれかの特定の遠隔局にデータを送信時におけるサービス間隔の長さを、該遠隔局の関連づけられた瞬間的データ受信速度（直近に受信されたＤＲＣ信号において示される）に基づいて決定する。このサービス間隔は、時間的に連続することはできないが、ｎのスロットごとに１回発生することができる。一実施形態によれば、パケットの第１の部分は、最初に第１のスロット中に送信され、その後は４スロット後に送信される。さらに、パケットの後続部分は、同様の４スロットのスプレッドを有する、すなわち互いに４スロット離れた、複数のスロットで送信される。一実施形態によれば、瞬間的データ受信速度Ｒｉは、特定のデータ待ち行列と関連づけられたサービス間隔長Ｌｉを決定する。
【００１９】
さらに、チャネルスケジューラ８１２は、特定のデータ待ち行列を送信のために選択する。次に、送信すべきデータの関連づけられた量がデータ待ち行列８３０から検索され、データ待ち行列８３０と関連づけられた遠隔局に送信するためにチャネル要素８２６に提供される。後述されるように、チャネルスケジューラ８１２は、データを提供するための待ち行列を選択し、該データは、後続するサービス間隔においてデータ待ち行列の各々と関連づけられた重みを含む情報を用いて送信される。次に、送信された待ち行列と関連づけられた重みが更新される。
【００２０】
基地局コントローラ８１０は、パケットネットワークインタフェース８０６、公衆交換電話網（ＰＳＴＮ）８０８、及び通信システム内の基地局とインタフェースする（説明を単純化するため図３には１つの基地局８２０のみが示されている）。基地局コントローラ８１０は、通信システム内の遠隔局とパケットネットワークインタフェース８０６及びＰＳＴＮ８０８に接続されたその他のユーザーとの間の通信を調整する。ＰＳＴＮ８０８は、標準電話網（図３には示されていない）を通じてユーザーとインタフェースする。
【００２１】
基地局コントローラ８１０は、数多くのセレクタ要素８１６を含む。ただし、説明を単純化するため図２においては１つのセレクタ要素８１６しか示されていない。各セレクタ要素８１６は、１つ以上の基地局８２０と１つの遠隔局（図示されていない）との間の通信を制御するために割り当てられる。セレクタ要素８１６が所定の遠隔局に割り当てられていない場合は、該遠隔局をページングする必要があることが呼制御プロセッサ８１８に連絡される。連絡を受けた呼制御プロセッサ８１８は、該遠隔局をページングするように基地局８２０に指示する。
【００２２】
データ源８０２は、所定の遠隔局に送信されるある量のデータを含む。データソース８０２は、これらのデータをパケットネットワークインタフェース８０６に提供する。パケットネットワークインタフェース８０６は、前記データを受け取り、前記データをセレクタ要素８１６にルーティングする。次に、セレクタ要素８１６は、ターゲットである遠隔局と通信中の各基地局８２０に前記データを送信する。該典型的実施形態においては、各基地局８２０は、遠隔局に送信されるデータを格納するデータ待ち行列８３０を維持する。
【００２３】
データは、データパケットの形でデータ待ち行列８３０からチャネル要素８２６に送信される。該典型的実施形態では、順方向リンクにおいては、「データパケット」は、最大１０２４ビットのある量のデータ及び予め決められた「タイムスロット」（約１．６６７ミリ秒、等）内で行先である遠隔局に送信されるある量のデータを意味する。各データパケットに関して、チャネル要素８２６は、必要な制御フィールドを挿入する。該典型的実施形態においては、チャネル要素８２６は、巡回冗長検査ＣＲＣ、及びデータパケットと制御フィールドの符号化を行い、一組の符号テールビットを挿入する。データパケット、制御フィールド、ＣＲＣパリティビット、及び符号テールビットは、１つのフォーマット化されたパケットを形成する。該典型的実施形態においては、チャネル要素８２６は、フォーマット化されたパケットを符号化し、符号化されたパケット内のシンボルをインターリービング（又は順序再設定）する。該典型的実施形態においては、インターリービングされたパケットは、ウォルシュコードによってカバーされ、短いＰＮＩ符号及びＰＮＱ符号で拡散される。拡散されたデータは、ＲＦ装置８２８に提供され、ＲＦ装置８２８は、信号を直角変調、フィルタリング、及び増幅する。順方向リンク信号は、アンテナを通じて順方向リンクにオーバーエア（ｏｖｅｒ ｔｈｅ  ａｉｒ）送信される。
【００２４】
遠隔局においては、順方向リンク信号がアンテナによって受信されて受信機にルーティングされる。受信機は、該信号をフィルタリング、増幅、直角復調、及び量子化する。デジタル化された信号は、復調器（ＤＥＭＯＤ）に提供され、ＤＥＭＯＤにおいて、短いＰＮＩ符号及びＰＮＱ符号を用いて逆拡散され、ウォルシュカバーが取り除かれる。復調されたデータは復号器に提供され、復号器は、基地局８２０において行われた信号処理機能の逆の動作、具体的には、デインターリービング機能、復号機能、及びＣＲＣ検査機能を実施する。復号されたデータは、データシンクに提供される。
【００２５】
上記のハードウェアは、順方向リンクにおける可変速度でのデータ、メッセージ、音声、映像、及びその他の通信の送信をサポートする。データ待ち行列８３０から送信されるデータの速度は、信号強度及び遠隔局における雑音環境の変化に対応するために変動する。各々の遠隔局は、好ましいことに、各タイムスロットにおいてデータ速度制御ＤＲＣ信号を関連基地局８２０に送信する。ＤＲＣ信号は、遠隔局のアイデンティティ及び遠隔局が関連づけられたデータ行列からデータを受信する速度を含む情報を基地局８２０に提供する。従って、遠隔局における回路は、信号強度を測定して遠隔局における雑音環境を推定し、ＤＲＣ信号に含めて送信される速度情報を決定する。
【００２６】
各遠隔局によって送信されたＤＲＣ信号は、逆方向リンクチャネルを通じて移動し、基地局８２０においてＲＦ装置８２８に結合された受信アンテナを通じて受信される。該典型的実施形態においては、ＤＲＣ情報は、チャネル要素８２６において復調され、基地局コントローラ８１０内に配置されたチャネルスケジューラ８１２又は基地局８２０内に配置されたチャネルスケジューラ８３２に提供される。第１の典型的実施形態においては、チャネルスケジューラ８３２は、基地局８２０内に配置される。代替実施形態においては、チャネルスケジューラ８１２は、基地局コントローラ８１０内に配置され、基地局コントローラ８１０内のセレクタ要素８１６に接続する。
【００２７】
回線交換システムにおける送信スケジューリングは、各ユーザーに関する優先度関数が定義される比例的公平アルゴリズムを含むことができる。比例的公平アルゴリズムの一例が以下において示される。優先度関数は、所定のユーザーに関する要求データ速度、典型的には該ユーザーに対する順方向リンクチャネルの品質の関数、及び該ユーザーに関するスループットを考慮に入れることができる。従って、容量は、スループットと比較して高い要求データ速度を有するユーザーに最初に対応することによって均衡化される。
【００２８】
一実施形態によれば、パケット交換システムにおける送信スケジューリングは、容量とユーザー遅延を均衡化する。アプリケーションフローは、ネットワーク上を送られる独立した内蔵メッセージであるデータグラムとして送信される。データグラムの到着、到着時間、及びコンテンツは一般的には保証されない。同じアプリケーションフローと関連づけられたデータグラムは、異なるルートを通じて同じユーザーに送信することができる。これらのデータグラムは、受信機において再アセンブルされる。パケット交換システムにおけるエンド・ツー・エンド遅延は固定されておらず、従って、スケジューラは、容量を増やすためにこの遅延差を用いて様々なユーザーに関する遅延を調整する。例えば、スケジューラは、低い遅延限度及び／又は遅延変動限度を有するデータを要求しているユーザーによって経験される遅延を短くすることができる。該アプリケーションは、限定することなしに、ＶｏＩＰ、音声、等を含む。送信は、特定のサービス等級（ＧｏＳ）又はＱｏＳ要求を有することができる。ＶｏＩＰ型送信は、例えば、定義されたレーテンシーを有するパケットが到着すること、又は許容可能な遅延時間内にパケットが到着することを要求する。従って、より低いレーテンシー要求又はその他のＧｏＳ仕様を有する通信又はアプリケーションを優先させることが望ましい。マルチメディア会議、映像ストリーミング、ウェブ検索、ファイル転送プロトコルの転送は、各々が特定のＧｏＳ要求を有する。
【００２９】
優先度分類方式を実装するため、各フローに優先度関数が割り当てられる。一実施形態においては、パケット交換スケジューラに関する優先度関数（ＰＦ）は次式のように与えることができる。
【００３０】
PF=f(delay)
ここで、f( )は関数であり、ＰＦは、所定のユーザーの又はユーザーに関する所定のアプリケーションの遅延上の要求に基づいて決定される。ＰＦは、各待ち行列内の各データグラムに関して計算され、優先度がより高いフローインスタンスを識別するために様々なＰＦが比較される。パケット交換通信は、所定の通信のエンド・ツー・エンド遅延が固定されていないため、スケジューリングが適応型遅延管理を組み入れることを可能にする。この可能にすることは、エンド・ツー・エンド遅延が固定されている回線交換通信と対照的である。  
以下の説明は、ＩＳ−８５６において説明されている高速パケットデータ（ＨＲＰＤ）サービスをサポートするｃｄｍａ２０００システムに関するものであることに注意すること。このシステムは、一例として用いられている。本発明は、サービス対象ユーザーがスケジューリングアルゴリズムに従って選択されるその他のシステムに対しても適用可能である。
【００３１】
ＨＲＰＤシステムにおいては、エアインタフェースは、最高４つの並行するアプリケーションストリームをサポートすることができる。第１のストリームは、シグナリング情報を搬送し、その他の３つのストリームは、異なるＱｏＳ要求を有するアプリケーション又はその他のアプリケーションを搬送するために使用することができる。
【００３２】
以下の用語説明は、下記の一実施形態を理解する際に明確化することを目的として提供されている。以下の用語説明は、包括的であることは意図されていない。以下の用語説明は、本発明を該用語説明に限定することは意図されておらず、適応型加重スケジューリングアルゴリズムをサポートする通信システムの一実施形態に関して明確化すること及び理解することを目的として提供されている。
【００３３】
用語説明
アクセスネットワーク（ＡＮ）−セルラー方式のネットワーク、パケット交換データネットワーク（典型的にはインターネット）、及びＡＴの間においてデータ接続性を提供するネットワーク装置。ＨＲＰＤシステムにおけるＡＮは、セルラー通信システムにおける基地局に相当する。
【００３４】
アクセス端末（ＡＴ）−データ接続性をユーザーに提供するデバイス。ＨＲＰＤシステムにおけるＡＴは、セルラー通信システムにおける移動局に相当する。ＡＴは、ラップトップ型パソコン等の計算デバイスに接続することができ、又はパーソナルデジタルアシスタント（ＰＤＡ）等の内蔵型データデバイスであることができる。
【００３５】
アプリケーションフロー−所定のアプリケーションストリームに関するソースからＡＴまでの指定された送信経路。各アプリケーションフローは、ソース、行先、トラフィックプロフィール及びサービスプロフィールの品質によって識別される。
【００３６】
アプリケーションストリーム−アプリケーションに対応するデータ通信。ほとんどのアプリケーションストリームは、指定されたサービス品質要求を有する。
【００３７】
自動再送要求（ＡＲＱ）−送信機がイベントの発生又は非発生に基づいてデータの再送信を開始する機構。
【００３８】
平均データ速度−所定のアプリケーションフローに関する経時での平均入力データ速度。
【００３９】
バースト性（σ）−アプリケーションフロー内のパケットのバースト性又は密度と時間的関係を表す尺度
ベストエフォート（ＢＥ）−一般的にオーバーエアで受信するデータ量が相対的に多いが、トラフィックの性質上相対的に長い遅延を許容可能であるが、データ損失率は極端に低くすべきであるアプリケーションフロー。
【００４０】
データ速度制御（ＤＲＣ）−ＡＴが要求されたデータ速度をＡＮに送信する機構。
【００４１】
欠損ビット（ｄｅｆｂｉｔ）−欠損パケットに対応するビット数
DelayBound−ＡＮからＡＴへのデータパケット送信に関して許容される指定時間（遅延限度）
優先転送（ＥＦ）−アプリケーションフローは、典型的には、インターネットからアクセスネットワークに到着するトラフィック量は少量であるが、該トラフィックの性質上、一定の相対的に低いDelayBound内で及び合理的なデータ損失率でデータパケットをユーザーに引き渡すべきである。
【００４２】
順方向リンク（ＦＬ）−ＡＮからＡＴへの送信エアリンク。
【００４３】
ヘッド・オブ・ライン（ＨＯＬ）パケット−待ち行列内における第１のパケット。
【００４４】
高速パケットデータ（ＨＲＰＤ）−パケットデータ通信を高データ速度で送信するデータサービス。高データ速度（ＨＤＲ）とも呼ばれ、「ｃｄｍａ２０００高速パケットデータエアインタフェース仕様」という題名のＩＳ−８５６規格において規定されている。
【００４５】
ジッター−受信された連続するパケット間における時間変動
ジッター限度−所定のアプリケーションフローに関するジッター限度
モーション・ピクチャ・エキスパーツ・グループ（ＭＰＥＧ）−マルチメディア素材を送信するためのプロトコル。
【００４６】
比例的公平（ＰＦ）アルゴリズム−要求されるデータ速度とスループットの比として各ＡＴに関して計算される選択率に従ってデータ通信がスケジューリングされるスケジューリングアルゴリズム。
【００４７】
サービス品質（ＱｏＳ）−パケットデータ通信の送信に関連する要求事項であり、限定することなしに、遅延、要求速度、及びジッターを含む。
【００４８】
逆方向リンク（ＲＬ）−ＡＴからＡＮへの送信エアリンク。
【００４９】
送信待ち行列−所定のＢＴＳに関するアプリケーションフローを保存する送信待ち行列
多くの無線通信は、パケットデータの処理に関して異なるホップ単位動作（ＰＨＢ）及び異なるルーティングを利用するためにインターネットプロトコル（ＩＰ）を利用する。一般的には、インターネットは、相互運用を目的としてＩＰに依存する様々なリンク層技術によって構築された多数のネットワークを含む。ＩＰは、ネットワーク負荷とともに増大するパケット損失及び遅延が生じる可能性がある無接続ネットワーク層サービスを提供する。基本的なＩＰ引き渡しモデルは、ベストエフォート（ＢＥ）と呼ばれる。しかしながら、幾つかのアプリケーションは、単純なＢＥサービスよりも優れたサービスを要求することができる。例えば、マルチメディアアプリケーションは、帯域幅が一定であること、遅延が短いこと及びジッターがほとんどないことを指定することができる。他の優先型は、スループットレベルを保証する保証転送（ＡＦ）と呼ばれる転送動作である。
【００５０】
ＱｏＳ管理には様々な側面が存在する。ＱｏＳ管理の一部の考慮事項は、帯域幅の割当て、及びブロードキャストネットワーク、例えばイーサネット（登録商標）ネットワーク又は無線ローカルエリアネットワーク（ＬＡＮ）とも呼ばれる共有媒体における保証された帯域幅である。ラップトップ型パソコン及びその他のコンピュータに無線能力を含める要求が高くなっている一方で、無線ネットワークは帯域幅が限られており、容量の保全及び最適化が極めて重要な検討課題になっている。
【００５１】
図３は、サービス等級（ＧｏＳ）要求又はＱｏＳ要求に基づいて送信優先順位を設定するスケジューリング方法を示した図である。ＡＮにおいては、送信用データは、入アプリケーションフローに対応するデータ待ち行列を格納するように適合化されたメモリ記憶装置に格納される。待ち行列は、アプリケーションフローの各インスタンスに関して格納される。本発明によれば、アプリケーションフローはインスタンスに分割され、各インスタンスは１オクテットのデータである。従って、アプリケーションフローは、関連づけられた複数の待ち行列を有することができ、さらにしばしば有することになる。各待ち行列は、関連づけられたＱｏＳ及び／又はＧｏＳ優先型によって定義された送信要求と受信要求を有する。例えば、優先型は、エンド・ツー・エンド遅延要求またはその他の何らかの品質基準に基づくことができる。この場合、１つの所定の送信は、複数のＧｏＳ優先型の１つに分類できることに注目すること。例えば、幾つかのサービスは、データパケットを個々に送信してのちに受信機において連続性を失わずに再結合することを可能にする。すなわち、ＢＥ優先型である。対照的に、ＶｏＩＰのようにリアルタイムの経験をユーザーに提供するように設計されたアプリケーションは、これよりも優先度が高い優先型を有しており、優先転送（ＥＦ）優先型と呼ばれる。ＥＦ優先型は、遅延限度及び遅延変動が制限されるアプリケーションを含む。本例においては、スケジューラは、ＥＦ通信の優先順位を設定する。ＱｏＳ優先型又はＧｏＳ優先型は、ＱｏＳクラスと呼ぶこともできる。さらに、各待ち行列は、関連づけられた影響度を有する。例えば、ＥＦアプリケーションフローは、典型的に遅延の影響を受けやすく、ＥＦアプリケーションフローの送信は満たすべき遅延上の要求を有することを意味する。多くの場合においては、遅延上の要求が満たされない場合は、データが廃棄されて送信されない。対照的に、ＢＥアプリケーションフローは、典型的にスループットの影響を受けやすく、ＢＥアプリケーションフローの送信は目標スループット上の要求を有するが、ＥＦアプリケーションフローの厳しい遅延上の要求は必ずしも有していないことを意味する。
【００５２】
図３は、一実施形態による適応型遅延管理を実装するスケジューリング方法２００を示した図である。ＡＮ内においては、スケジューラは、スケジューリングアルゴリズムを実装し、高速パケットデータ送信を複数のユーザーに提供する。スケジューラは、データ待ち行列を検査してデータに関するＱｏＳ型を決定する。いずれかのデータが所定のＧｏＳ優先型、すなわち、ＢＥよりも特定の要求を定義する優先型である場合は、判断ボックス２０２において、プロセスはステップ２０４に進み、待ち行列内において優先度が最も高い優先型を有する最も古いデータを見つけ出す。本明細書において用いられる優先度がより高い優先型は、より厳しい仕様によって定義されたＧｏＳ優先型を指している。例えば、１つの優先型は、遅延限度を指定することができ、他の優先型は、ジッター限度を指定することができる。この場合、遅延限度を指定する優先型のほうが優先度が高いとみなされ、従って最初に考慮される。
【００５３】
本発明によれば、スケジューラは、最初に、遅延上の要求に基づいて、送信のためにパケット内にビットを入れる順序を設定する。優先度の高いデータがスケジューリングされた時点で、残りのパケットをスケジューリングするために他のアルゴリズムを使用することができる。
【００５４】
例えば、ＥＦデータが待ち行列内にあるときには、スケジューラは、該ＥＦデータを用いて送信のためのパケット形成を始める。ＥＦデータは、ステップ２０４において、待ち行列内におけるデータの待ち時間に基づいて選択される。一実施形態においては、データは、待ち行列内に入れられるときにタイムスタンプを受け取る。スケジューラは、タイムスタンプが最も早いＥＦデータを見つけ出して最初にパケット内に入れる。次に、スケジューラは、ステップ２０６において、待ち行列内における待ち時間に従ってＥＦデータをパケット内に入れる。すべてのＥＦデータが送信のためにパケット内に入れられた時点で、スケジューラは、残りのデータに関して他のアルゴリズムを適用する。本実施形態においては、スケジューラは、ステップ２０８において、ベストエフォート（ＢＥ）データである残りのデータに比例的公平アルゴリズムを適用する。これらのＢＥデータは、ステップ２１０において、比例的公平アルゴリズムに従ってパケット内に入れられる。
【００５５】
チャネル状態が向上するのに従ってユーザーがより高速のデータを要求するようになり、遅延限度を引き下げる効果を有することに注目すること。従って、スケジューラがＥＦデータを優先時においても、遅延限度はチャネル状態の関数になる可能性がある。
【００５６】
ＢＥデータを送信時には、スケジューラは、スループットが最高になるようにパケットを選択する。スループットは、一般的には次式のように計算される。
【００５７】
スループット = (パケット当たりのビット) / (パケット当たりのスロット)
一実施形態によれば、ＰＦは次式のように与えることができる。 
PF ＝ f(パケットの待ち時間)*g(チャネル状態)*h(セルの負荷)
上式は、送信をスケジューリングする際にパケットの待ち時間、チャネル状態及びセルの負荷を考慮したものである。該計算は、ＥＦデータ又はＢＥデータのスケジューリングのために使用することができる。
【００５８】
再度図２において、一実施形態においては、チャネルスケジューラ８３２は、各遠隔局に関する待ち行列内のデータ量を示す情報をデータ待ち行列８３０から受け取る。待ち行列内のデータ量は、待ち行列の規模とも呼ばれる。チャネルスケジューラ８３２は、基地局８２０によって対応される各遠隔局に関するＤＲＣ情報及び待ち行列の規模に基づいてスケジューリングを行う。代替実施形態において用いられるスケジューリングアルゴリズムに関して待ち行列の規模が要求される場合は、チャネルスケジューラ８１２は、セレクタ要素８１６から待ち行列規模情報を受け取ることができる。
【００５９】
１人以上のユーザーにパケットを送信中は、これらのユーザーは、送信されたパケットの一部分を含む応答“ＡＣＫ”信号を各タイムスロット後に送信する。各ユーザーによって送信されたＡＣＫ信号は、逆方向リンクチャネルを通って移動し、基地局８２０においてＲＦ装置８２８に結合された受信アンテナを通じて受信される。本典型的実施形態においては、ＡＣＫ情報は、チャネル要素８２６において復調され、基地局コントローラ８１０内に配置されたチャネルスケジューラ８１２に提供されるか又は基地局８２０内に配置されたチャネルスケジューラ８３２に提供される。第１の典型的実施形態においては、チャネルスケジューラ８３２は、基地局８２０内に配置される。一つの代替実施形態においては、チャネルスケジューラ８１２は、基地局コントローラ８１０内に配置され、基地局コントローラ８１０内のセレクタ要素８１６に接続する。  
本発明の実施形態は、様々な速度の送信をサポートできるその他のハードウェアアーキテクチャにも適用可能である。本発明は、逆方向リンクにおける様々な速度での送信を網羅するように容易に拡張することができる。例えば、基地局８２０におけるデータ受信速度を遠隔局からのＤＲＣ信号に基づいて決定する代わりに、基地局８２０は、遠隔局から受信された信号の強度を測定して雑音環境を推定し、遠隔局からのデータ受信速度を決定する。次に、基地局８２０は、遠隔局から逆方向リンクでデータを送信すべき速度を各関連づけられた遠隔局に送信する。これで、基地局８２０は、本明細書において順方向リンクに関して説明される方法と同様の方法で、逆方向リンクにおける異なるデータ速度に基づいて逆方向リンクでの送信をスケジューリングすることができる。
【００６０】
さらに、上記の実施形態の基地局８２０は、符号分割多重接続ＣＤＭＡ法を用いて、基地局８２０と関連づけられた遠隔局のうちの選択された１つの又は選択された複数の遠隔局に送信し、残りの基地局を除外する。いずれの特定時点においても、基地局８２０は、受信する基地局８２０に対して割り当てられた符号を用いて、選択された１つの又は選択された複数の遠隔局に送信する。しかしながら、本発明は、送信資源を最適に割り当てるため、基地局８２０を選択してその他の基地局８２０を除外するために異なるデータ提供方法である時分割多重接続ＴＤＭＡ法を採用するその他のシステムに対しても適用可能である。
【００６１】
チャネルスケジューラ８１２は、順方向リンクでの可変速度送信をスケジューリングする。チャネルスケジューラ８１２は、遠隔局に送信するデータ量を示す待ち行列の規模、及びメッセージを遠隔局から受信する。チャネルスケジューラ８１２は、好ましいことに、公平に関する制約を順守しつつデータスループットを最高にするシステム上の目標を達成させるようにデータ送信をスケジューリングする。
【００６２】
図１Ａにおいて示されるように、遠隔局は、通信システム全体にわたって分散されており、ゼロ又は１つの基地局と順方向リンクで通信状態になることができる。該典型的実施形態においては、チャネルスケジューラ８１２は、通信システム全体における順方向リンクデータ送信を調整する。
【００６３】
一実施形態によれば、図２のチャネルスケジューラ８１２は、プロセッサと、ランダムアクセスメモリＲＡＭと、前記プロセッサ（図示されていない）によって実行される命令を格納するためのプログラムメモリと、を含むコンピュータシステムに実装される。前記プロセッサ、ＲＡＭ及びプログラムメモリは、チャネルスケジューラ８１２の機能専用にすることができる。その他の実施形態においては、前記プロセッサ、ＲＡＭ及びプログラムメモリは、基地局コントローラ８１０において追加機能を実行するための共有計算資源の一部であることができる。該典型的実施形態においては、汎用スケジューラが図２のシステム８００に使用され、以下において詳細に説明される。データ送信をスケジューリングするための優先度関数を実装するために用いられるＢＳＣ８１０及びＢＳ８２０内のモジュールは、汎用スケジューラについて詳述後に説明される。
【００６４】
無線データアプリケーションの需要増大に伴い、非常に効率的な無線データ通信システム需要も大幅に増加している。ＩＳ−９５規格は、トラフィックデータ及び音声データを順方向リンク及び逆方向リンクで送信することが可能である。ＩＳ−９５規格によれば、トラフィックデータ又は音声データは、幅が２０ミリ秒、データ速度が１４．４Ｋｂｐｓの符号チャネルフレームに分割される。ＩＳ−９５システムにおいては、各加入者局は、限られた数の直交順方向リンクチャネルのうちの少なくとも１つが割り当てられる。基地局と加入者局との間において通信が進行中は、順方向リンクチャネルは加入者局に割り当てられた状態になる。ＩＳ−９５システムにおいてデータサービスを提供時には、加入者局に送信すべき順方向リンクデータが存在しない間においても順方向リンクチャネルが加入者局に割り当てられた状態になる。
【００６５】
音声サービスとデータサービスとの間の重要な相違点は、音声サービスが課す遅延上の要求が厳しくさらに固定されていることである。典型的には、音声フレームに関する１方向遅延は全体で１００ミリ秒未満にするように指定されている。対照的に、データ遅延は、データ通信システムの効率を最適化するために用いられる可変変数になることができる。
【００６６】
音声サービスとデータサービスとの間の他の重要な相違点は、音声サービスが全ユーザーに関して固定された共通のサービス等級（ＧｏＳ）を要求することである。その結果、典型的には、音声サービスを提供するデジタルシステムに関しては、全ユーザーに関して送信速度が一定の等しい送信速度になり、音声フレームの誤り率に関する許容値が最大になる。対照的に、データサービスに関しては、ＧｏＳはユーザーごとに異なることができ、さらにデータ通信システムの全体的効率を向上させるために最適化された変数であることができる。データ通信システムのＧｏＳは、典型的には、以下においてデータパケットと呼ばれる予め決められた量のデータを転送する際に被る総遅延であると定義される。
【００６７】
音声サービスとデータサービスとの間のさらに他の重要な相違点は、音声サービスは、典型的ＣＤＭＡ通信システムにおいてはソフトハンドオフによって提供される信頼性の高い通信リンクを要求することである。ソフトハンドオフは、信頼性を向上させるために２つ以上の基地局から冗長な送信が行われることになる。しかしながら、誤りがある状態で受信されたデータパケットは再送信することができるため、この追加の信頼性はデータ送信に関しては不要である。データサービスに関しては、ソフトハンドオフをサポートするために用いられる送信電力は、追加データを送信するためにより効率的に使用することができる。
【００６８】
データパケットを転送するために要求される送信遅延及び平均スループット率は、データ通信システムの品質及び有効性を定義する２つの属性である。送信遅延がデータ通信において及ぼす影響は、音声通信に関して及ぼす影響と同じではないが、送信遅延はデータ通信システムの品質を測定する１つの尺度である。平均スループット率は、通信システムのデータ送信能力の効率を示す１つの尺度である。当業においては、無線チャネルを通じて提供中のサービスの型に関して適切なＧｏＳを同時に提供する一方で向上されたデータスループットを提供する通信システムが必要である。
【００６９】
汎用スケジューラが必要であるかどうかは、無線システムにおけるデータ送信上の要求事項及び目標に基づく。データ送信の場合は、スループットは、個々のビット又はバイトに関してではなく、データパケットを送信する際に被る遅延に関して定義される。インターネットプロトコルＩＰデータグラム等のデータパケットは、ほとんどの場合、パケットの一部のみを受け取ってもユーザーがパケット全体を復号して使用する上で十分な情報を含んでいない、すなわちエンドユーザーにとっては役に立たないため、該パケットは分割不能な単位である。エンドユーザーは、データパケットを受け取り、前記データパケットに関する巡回冗長検査ＣＲＣを行い、データを処理する。従って、ユーザーは、パケットの最後のビットの到着時間に最も関心があり、データパケット内の個々のビットの遅延には最後のビットほどの関心がない。このことは、データパケットの送信時間よりも短い時間において異なるユーザーに対して非常に柔軟な速度割当てを行うことを可能にする。さらに、送信制御プロトコルＴＣＰ型接続においては、パケット遅延の変動が非常に予測不能であるためＴＣＰの再送信を不必要に生じさせることにならない限り、ある程度の変動は受入可能である。
【００７０】
無線チャネルの他の特長は、チャネル自体が可変であることである。ＨＤＲ型システムにおいては、この可変であることは、要求される速度がある一定の時間において変動することになる。チャネルを最大限に利用するため、スケジューラは、高速ユーザー、すなわち最高のデータ速度を要求するユーザーに対応するように設計されている。この設計は、自分が要求するデータ速度が低いときには該ユーザーは一定の時間だけ対応されない可能性があることを意味する。全体的スループットは、スケジューラが低速ユーザーに長時間対応しないときに最高になる。しかしながら、理想的なことに、スケジューラは、上記のように、全体的スループットを最高にすることを、パケット遅延と遅延変動が相対的に一致するようにするのが望ましいことと均衡化させる。
【００７１】
他の側面は、システム内の複数のユーザーに対する公平性を考慮する。公平なスケジューリング方法を実現させるため、スケジューラは、理想的なことに、複数の異なるユーザー間で全体的スループットを配分する。個々のシステムのニーズ及び希望に対して影響を与えるようにするために、使用される公平性の基礎（又は許容可能な不公平性）は各システムによって異なる。公平性の概念は、多くのスケジューリングアルゴリズムにおける主要な概念である。公平性は、ユーザーに対応する際の柔軟性が各ユーザーごとに異なることになり、従ってセクターの全体的スループットに対して影響を有する。
【００７２】
一実施形態によれば、複数のクラスのユーザーに対するアプリケーションを有する通信システムにおいて送信をスケジューリングする方法及び装置は、汎用スケジューラを組み入れる。汎用スケジューラは、様々なスケジューリング上の優先度に対応する。各々が特定の送信上の要求を有する異なるクラスのユーザーが汎用スケジューラによって対応され、全ユーザーに関して高いスループットが維持される。
【００７３】
一実施形態においては、汎用スケジューラの動作は、チャネル状態メトリック及び公平性基準の優先度関数を実装し、前記優先度関数は次のように定義される。
【００７４】
f(Ai(t),Ui(t))
ここで、Ai(t)は、チャネル状態メトリックと呼ばれ、Ui(t)は、ユーザー公平性メトリックと呼ばれる。関数Ai(t)は、現在のチャネル状態に基づいて時間tにおいてユーザーiに対応するのが望ましいことを指定する。関数Ui(t)は、過去の受信サービス歴に基づいて時間tにおいてユーザーｉに対応するのが望ましいことが指定される。優先度関数f(  )は、これらの２つの望ましいことに関するメトリックAi(t)及びUi(t)を組み合わせて各ユーザーに関する優先レベルを決定する。
【００７５】
一実施形態によれば、汎用スケジューラは、１つの所定のクラス又は型のユーザー内において最高の優先度関数f(Ai(t), Ui(t))を有するユーザーに対応する。該典型的実施形態においては、優先度関数f(Ai(t), Ui(t))によってとられる値は、チャネル状態関数Ai(t)が大きくなるに従って大きくなり、公平性関数Ui(t)が大きくなるに従って小さくなる。関数Ai(t)及びUi(t)は適宜決定される。さらに、優先度関数f(  )は、チャネル状態メトリック及びユーザー公平性メトリックが測定される少なくとも１つの時間の関数である。代替実施形態においては、優先度関数f(  )は、１つのユーザー関数ごとに時間に依存することができる。しかしながら、説明を単純化するため、スケジューラは、全ユーザーに共通するコンバイナ関数を使用し、ユーザー公平性メトリックを修正してユーザー要求を反映させることができる。
【００７６】
汎用クラスの多ユーザースケジューラは、ＡＮからサービスを受け取るユーザーを少なくとも２つの広範なカテゴリ、ＢＥ及びＥＦに分類する。ＡＦ等のその他のカテゴリの送信も実装することができる。ＢＥ及びＥＦは、本明細書において定義されるとおりである。具体的には、ベストエフォート（ＢＥ）アプリケーションは、一般的には、オーバーエアで受信するデータ量が相対的に多いが、トラフィックの性質上、相対的に長い遅延を許容可能である一方で、データ損失率は極端に小さくすべきである。優先転送（ＥＦ）アプリケーションフローは、典型的には、インターネットからアクセスネットワークに到着するトラフィック量は少ない。しかしながら、該トラフィックの性質上、一定の相対的に小さいDelayBound内において合理的なデータ損失率でデータパケットをユーザーに引き渡すべきである。
【００７７】
１ｘＥＶ−ＤＯ等のパケットデータシステムにおいては、スケジューラは、容量を最大化するために個々のユーザーに対して可変の遅延性能を許容する柔軟性を有する。本明細書においては、容量とは、ＢＥユーザーに関してはスループットを意味し、ＶｏＩＰ等の遅延の影響を受けやすいトラフィックの場合は受入可能な性能を有する対応されたユーザー（ＥＦユーザー）数を意味する。
【００７８】
１ｘＥＶ−ＤＯにおいては、一般的には、ユーザーのDelayBoundを上げることはＦＬの利用を増大させ、それによってシステムのＢＥ容量及びＥＦ容量を増大させる。この容量増大は、限定することなしに、パッキング効率の向上及びローカルチャネル状態と多ユーザーダイバーシティ利得の利用能力の向上を含む様々な要因によるものである。
【００７９】
ＢＥのみのトラフィックの場合は、典型的スケジューラは、比例的公平（ＰＦ）スケジューラである。このスケジューラは、個々のユーザーに提供されるスループットがユーザーと基地局との間の距離(geometry)、すなわち平均的チャネル状態にほぼ比例するという意味で比例的に公平である。比例的公平スケジューラは、スループットが有する利益と公平性の二者択一性に起因してＢＥのみのトラフィックに関して選択されるスケジューラとなっている。さらに、ＰＦアルゴリズムは、多ユーザーダイバーシティ利得を提供する一方でローカルチャネルピークを利用するように設計されている。本明細書において用いられるＰＦスケジューラは、「比例的公平スループットスケジューラ」と呼ばれる。
【００８０】
ＢＥのみのトラフィック場合は、他のクラスのスケジューラ、すなちわ「平等サービス等級」スケジューラが存在する。このスケジューラは、平等なスループットを全ユーザーに提供することを目的とするスケジューラである。この理由により、システム容量は、最も弱いユーザーによって決定される。平等サービス等級スケジューラは、幾つかのアプリケーションにおいては望ましい可能性があるが、該スケジューラは、典型的には、エアリンクを効率的に利用しない。これらのスケジューラは、本明細書においては「平等スループットスケジューラ」と呼ばれる。
【００８１】
上記のＰＦスループットスケジューラ及び平等スループットスケジューラは、ＢＥトラフィックのみの場合において有用である。遅延の影響を受けやすいＥＦトラフィックの場合は、これらのスケジューラは、遅延制御機構を有さないため十分ではない可能性がある。
【００８２】
次に、ＢＥのみのトラフィックに関する２つのアプローチ法、すなわちＰＦスループットスケジューラ及び平等スループットスケジューラと並行して動作する、遅延の影響を受けやすいスケジューリング手段および方法が説明される。遅延の影響を受けやすいトラフィックの場合は、「比例的」公平性及び「平等な」公平性は、個々のユーザーに提供されるスループットに対してだけでなく、個々のユーザーに提供される「遅延」性能に対しても当てはまる。遅延性能は、平均遅延又は遅延テールウエート、等に関して定量化することができる。代替実施形態は、スループット及び遅延の影響度に関する要求をそれぞれ満たしながらＢＥスケジューリング及びＥＦスケジューリングを１つの共通の方法の中に組み入れることができる点に注目すること。
【００８３】
一実施形態においては、ほぼ平等な遅延性能を各ユーザーに提供することができる。このアプローチ法は、平等スループットと類似しており、用語の対称性を目的として「平等遅延スケジューラ」と呼ばれる。平等スループットスケジューラは、平等なスループットを全ユーザーに提供することを試み、従って、システム容量は、最も弱いカバレッジを有するユーザーによって決定される。平等遅延スケジューラは、平等な遅延性能、例えば平等な平均遅延、又は平等なテールウエートを全ユーザーに提供することを試み、従って、システム容量は、同様に、最も弱いカバレッジを有するユーザーによって決定される。
【００８４】
他の実施形態においては、ユーザーに提供される遅延性能は、該ユーザーの平均チャネル状態に比例する。このアプローチ法は、比例的公平スループットスケジューラと類似しており、「比例的公平遅延スケジューラ」と呼ばれる。比例的公平スループットスケジューラは、個々のユーザーの平均チャネル状態に比例するスループットを該ユーザーに提供することを試み、従って平等スループットスケジューラと比較してシステム容量を大幅に増大させる。同様に、比例的公平遅延スケジューラは、ユーザーの平均チャネル状態に比例する遅延性能を個々のユーザーに提供してＥＦ容量を最大化させる。
【００８５】
４つのパケットスケジューリングカテゴリが図４に示されている。各カテゴリは、ＱｏＳに関する考慮事項が均衡している状態が示されている。具体的には、ＰＦスループットスケジューラは、スループット制御を比例的公平性と均衡させる。平等スループットスケジューラは、スループット制御を平等な公平性と均衡させる。ＰＦ遅延スケジューラは、遅延制御を比例的公平性と均衡させる。平等遅延スケジューラは、遅延制御を平等な公平性と均衡させる。
【００８６】
幾つかのスケジューリング方法は回線交換システムにおいて有用である一方で、その他のスケジューリング方法は、１ｘＥＶ−ＤＯ等のパケットデータシステムにより適している。本明細書において提供される比例的公平遅延スケジューリング手段および方法は、パケット交換システムが回線交換システムよりも有利な点を提供することができる。
【００８７】
ＰＦ遅延スケジューラは、システム容量を向上させることに加えて、ユーザーの経験を高めることもできる。例えば、ＢＳに非常に近い位置に所在するユーザーは、ＢＳから遠いユーザーよりも優れた遅延性能を受け取る可能性がより高い。この点は、ＡＮへのユーザーの近接性に依存しな遅延性能と対照的である。さらに、ＢＳに非常に近い位置に所在していてチャネル状態が良好な（ｈｉｇｈ  ｇｅｏｍｅｔｒｙ）ユーザーに関しては、高い信頼度で性能を予測可能である。他方、平等遅延スケジューラの場合は、遅延性能は、システムに対する現在の負荷に依存して予測不能である。従って、個々のユーザーが基地局に近づくのに従ってスケジューラが提供するサービスの質を高めることが望ましい。
【００８８】
ＢＥユーザー及びＥＦユーザーの両方に対応するスケジューラは、比例的公平スループットスケジューリングと遅延スケジューリングの適切な組合せを利用することができる。このようなスケジューラは、「比例的公平スループット／遅延スケジューラ」と呼ばれる。一実施形態においては、比例的公平スループット／遅延スケジューリングは、単一のセクターに関して対応されるユーザーの相対的所在位置に暗黙に基づいていることに注目すること。この公平性は、「セクター内公平性」と呼ばれる。スケジューラを設計する際に考慮すべきもう１つの課題は、「セル間の」公平性である。この「セル間の公平性」は、異なるセクターによって対応されるユーザーに対してこれらのセクターによって提供される平均サービスレベルとして表すことができ、ＢＥユーザーに対して提供されるスループットに関して及びＥＦユーザー等に対して提供される平均遅延に関して定量化することができる。
【００８９】
比例的公平スループットスケジューラと比例的公平遅延スケジューラの類似性に関する説明を続けると、比例的公平スループットスケジューラを利用するセクターによって個々のＢＥユーザーに提供されるスループットは、該セクターによって対応されるユーザー数が減少するに従って低下することに注目すること。しかしながら、セクター内公平性は維持される。同様に、比例的公平遅延スケジューラを利用するセクターによって個々のＥＦユーザーに提供される遅延性能は、該セクターによって対応されるユーザー数が増加するに従って向上するのを許容することができる。
【００９０】
比例的公平スループット／遅延スケジューラは、スケジューリング決定時に対応すべきユーザーを選択するために以下の形の決定メトリックを利用する。
【００９１】
DecisionMetric = f(PacketAge、ChannelCondition, SectorLoad)
ここで、PacketAgeは、現在の時間と基地局待ち行列内において待機中の各パケットに関して定義された該当するタイムスタンプとの間の差を示し、チャネル状態は、ＢＳとＡＴとの間の無線リンクの品質を示し、SectorLoadは、現在の時間における短い時間スパンにわたってセクターによって対応される総トラフィックの量とプロフィールを示す。関数f(  )は、スケジューラの特定の実装に依存する。さらに、DecisionMetricは、ビットメトリック、パケットメトリック、データグラムメトリック、又は送信インスタンス選択方法をスケジューラに提供するその他の手段を意味することもできる。
【００９２】
ChannelCondition情報は、様々な方法でスケジューラに組み入れることができる。例えば、比例的公平スループットスケジューラは、ローカルチャネルピーク中にピークに達する傾向があるデータ速度制御（ＤＲＣ）／AvgThroughputを使用する。他のアプローチ法は、ＤＲＣ／AvgDRCを使用可能であるが、アプリケーションにおいてはチャネル変動がより大きいユーザーのほうが適している。さらに、フィードバックループを用いてチャネルピークの一定の百分位数を示すことも可能である。１つの該ループ３００が図５において示されている。
【００９３】
図５に示される一実施形態は、しきい値に関する許容可能なチャネル品質を決定するように設計されたループ３００である。入力ＩＤＲＣは、ＤＲＣ値の関数又はインデックス、例えば、ＤＲＣに関連づけられたデータ速度の増加関数であり、要求されたデータ速度が上昇するに従ってＩＤＲＣが大きくなる。ＩＤＲＣは、比較装置３０２及び無限インパルス応答フィルタ（ＩＩＲ）３０６に提供される。一例においては、時定数が１に設定されるが、代替の時定数を実装することができる。ＩＩＲフィルタ３０６のフィルタリングされた出力が加算装置３１２に提供され、加算装置３１２は、しきい値を比較装置３０２に提供する。比較装置３０２は、ＩＤＲＣをしきい値と比較する。比較結果は、現在のチャネル品質が受入可能であるかどうかを示す。システムは、チャネル品質が受入可能であるべき時間の目標割合を決定する。本例においては、該目標は３０％に設定される。該目標は可変であり、動作中に調整することができる。代替システムは、その他の目標値又は方式を実装することができる。比較装置３０２の出力は、2進｛１，０｝であり、１は、受入可能なチャネル品質を示し、０は、受入不能、すなわちしきい値よりも小さいことを示す。
【００９４】
引き続き図５において、比較装置３０２の出力がＩＩＲフィルタ３０４に提供され、本例においては、時定数は０．５秒に設定される。代替時定数を実装可能である。ＩＩＲフィルタ３０４から、フィルタリングされた出力が、入力値と比較するために比較装置３１０に提供され、本例においては入力値は０．３である。比較結果が入力値を上回っている場合は、チャネル品質を決定するためのしきい値を引き上げるための信号がｕｐ／ｄｎアキュムレータ３０８に提供される。この動作は、比較装置３０２からのチャネル品質インジケータが３０％よりも大きいことを示している。比較結果が入力値を下回っている場合は、ｕｐ／ｄｎアキュムレータ３０８に提供される信号がしきいの引き上げを指図する。ｕｐ／ｄｎアキュムレータ３０８の出力は、加算装置３１２に提供される。加算装置３１２は、ｕｐ／ｄｎアキュムレータ３０８の出力とＩＩＲフィルタ３０６の出力を合計し、ＩＩＲフィルタ３０６からの入力は、しきい値に関する一般的バイアスを比較装置３０２に提供する。合計結果は、比較装置３０２に提供される。チャネル推定インジケータが比較装置３１２の出力から取り出される。この方法で、スケジューラは、チャネル状態が良好、すなわちチャネルピークである良好な時間の割合を特定するためにチャネル推定インジケータ又はChannelCondition情報を維持する。
【００９５】
SectorLoadは、ＢＥフロー又はＥＦフローの量を測定することによってスケジューラに組み入れることができる。最後に、スケジューラによって用いられる実際の決定メトリックは、ChannelCondition及びSectorLoadの測定値を明示で含まないことがある。ユーザー当たりの要求されるDelayBoundは、送信されたＩＰパケットの一定割合に関する遅延:限度を満たすことができないＥＦユーザーの割合を測定することによって適応的に選択することができる。
【００９６】
幾つかのスケジューラによって用いられる変数は、フローの「ＱｏＳクラスインデックス」と呼ばれ、該フローに関する相対優先度を定義する。ＱｏＳクラスの決定方法は様々である。所定のＱｏＳクラス内においては、異なるフローが非常に異なるトラフィック型を有する可能性がある。ＱｏＳクラスインデックスは、フローによって要求される優先レベルを示すものであり、トラフィックの統計学的動作を示す指標ではない。
【００９７】
一実施形態においては、ＱｏＳクラスインデックスは、スケジューラがより大きいＱｏＳクラスインデックスを有するフローにより高い優先度を提供するように選択される負でない整数値である。本例においては、ＱｏＳクラスインデックス０は、ＢＥ／ＡＦフローに対応し、ＢＥフローは、要求される最小のスループット値がゼロに設定される特殊なＡＦフロー例である。１以上のＱｏＳクラスインデックスはＥＦフローに対応する。
【００９８】
より高いＱｏＳクラスにより高い優先度が与えられることに注目すること。ただし、待ち行列内において待機中のすべてのＥＦデータが送信後にＢＥデータの送信スケジューリングが必ずしも行われるわけではない。一例として、スケジューラは、期限が近づいている幾つかのＥＦビットを送信するように多ユーザーパケットをスケジューリングすることができる。同じ送信インスタンスにおいて、スケジューラは、適合可能なＤＲＣ、すなわち送信フォーマットを有するユーザーからのＢＥデータを含めて適合不能なＤＲＣを有するユーザーからのＥＦビットを含めないようにすることもできる。
【００９９】
ＱｏＳフローは、３つの変数、すなわち（１）ＩＰデータグラムの大きさの分布、（２）ＩＰデータグラム間における到着と到着の間の時間分布、及び（３）経過するとＩＰデータグラムの内容が役に立たなくなる、ＩＰデータグラムのタイムスタンプに関する遅延限度によってほぼ表すことができる。
【０１００】
ＢＥ／ＡＦフローに関しては、遅延限度はＥＦフローよりもはるかに緩やかであり、このため、ＡＦが保証転送フローであるとみなされるＢＥ／ＡＦフローに関しては考慮されない。同じ遅延限度を有するがＩＰデータグラムの大きさと到着間の時間の分布が異なるＥＦフローに関しては、スケジューラは、ほぼ直線的に動作するように設計されている。例えば、ＶｏＩＰフローと同じ遅延限度とパケットサイズ分布を有するが到着間時間分布が１／２であるフローは、２つのＶｏＩＰフローとほぼ同じように動作する。同様に、ＶｏＩＰフローと同じ遅延限度及び到着間時間分布を有するが、データグラムの大きさ分布はＶｏＩＰフローの２倍であるフローも、スケジューラにとってはほぼ２つのＶｏＩＰとして動作する。パケットサイズ及び到着間時間の整数以外の倍数は、基本「単位」のフロー型の集合であることを容易に認識することができる。
【０１０１】
しかしながら、遅延限度は、データグラムの大きさ分布及び到着間時間分布とは大きく異なる影響をスケジューラに与える。スケジューラは、遅延限度がより低いフローをより高い優先度で取り扱う。ある意味においては、フローの遅延限度をより小さい値に設定することは、ＱｏＳクラスインデックスを大きくする１つの穏やかな方法である。
【０１０２】
前述されるように、送信のスケジューリングは、受入制御に関連しており、受入制御は、ユーザー又はフローが処理ためにどの時点で受け入れられるかを決定し、次に、スケジューリングがこれらのフローをどの時点でどのような方法で送信するかを決定する。換言すると、受入制御は、いずれのデータが送信インスタンスに含められる資格を有することになるかを決定し、次に、スケジューリングがこれらの送信インスタンスの特定のデータ、フォーマット及び順序を決定する。従って、スケジューラの動作は、所定のシステムにおいて用いられる受入制御方式に影響を与える。
【０１０３】
一実施形態によれば、システム負荷が増大するに従い、典型的には、各ＢＥ／ＡＦフローは、各々が公平に等級が下げられるようにスケジューリングされる。しかしながら、ＥＦフローに関しては、等級引き下げは典型的には不均一である。より具体的には、より高いＱｏＳクラスが適切に機能し続けるようにするためより低いＱｏＳクラスの等級が最初に下げられる。所定のＥＦ ＱｏＳクラス内において、遅延限度設定値の違いを無視した場合は、可能な限り多くのユーザーが希望される性能を受け取るようにするために基地局からより遠い（ｌｏｗｅｒ  ｇｅｏｍｅｔｒｙ）ユーザーの等級が下げられる。このアプローチ法は、サポートされるＥＦユーザー数を最大にすることを目的として講じられる。均一なＥＦフローの場合は、ＥＦユーザーは不均一に等級が下げられる。すなわち、基地局から最も遠いユーザーの等級が最初に下げられ、その後に基地局により近い（ｈｉｇｈｅｒ  ｇｅｏｍｅｔｒｙ）ユーザーに移行する。このアプローチ法は、スケジューラの外部で処理される、より具体的には受入制御処理によって処理される、幾つかの結果を有する。これらの結果の一部が以下の例において説明される。
【０１０４】
スケジューラのこの機能は図６に示されており、図６においては、基地局との距離に従って分類された順序でフローが示されており、右に進む従って基地局に近くなる。現在のシステム負荷を考慮して、スケジューラは、希望されるＱｏＳを受け取るＱｏＳフロー数を最大にするために基地局から遠いユーザーほど優先度を低くする。基地局から遠いユーザーのレベルが右に広がって混雑度が上昇する。スケジューラは、これらのユーザーの優先度を低くすることによってこれらのユーザーが受け取るサービスの質を低下させる。しかしながら、スケジューラは、１つのフローに完全に対応する責任は負っておらず、この機能は、典型的には受入制御及びその他の性能モニタリングブロックの機能になる。
【０１０５】
次に、全ユーザーが単一のフローと同じＱｏＳクラス、例えばＶｏＩＰフローを有しており、さらに基地局に最も近いユーザーが非常に高いスループットのＥＦフローを要求する状況について検討する。スケジューラは、その他のユーザーへの送信が行われなくなっても、最も近いユーザーにすべてのＦＬスロットを割り当てることができる。一般的には、フローに関する受入決定は、システムの現在の負荷を考慮した受入制御処理によって処理される。受入制御がフローを受け入れた時点では、スケジューラは、基本機能を実施してすべてのＦＬスロットを前記ユーザーに割り当てる。基地局により遠いユーザーの等級を最初に下げることは、受入可能な受信性能を有するＥＦユーザー数をスケジューラが最大にすることを必ずしも意味するわけではない。スケジューラは、全ユーザーが同じＱｏＳ変数及び同じトラフィック型（例えばＶｏＩＰ専用）を有する場合に前記ユーザー数を最大することができる。
【０１０６】
混雑度が低いことに起因して自己のサービスの等級がスケジューラによって下げられた、基地局から遠いユーザーが非常に低いスループット（例えば、毎秒１バイト）を要求している場合は、スケジューラは、ＦＬ性能に影響を及ぼさない場合であっても、要求される又は希望されるスループットを該ユーザーに提供することができない。現在のシステム負荷を考慮して前記ユーザーに関するスケジューラの動作を予想するのは受入制御の責任である。この場合は、受入制御は、スケジューラがＱｏＳクラスインデックスを大きくすることによって前記ユーザーにサービスを提供するように強制することができる。
【０１０７】
以下の説明では、ＥＦトラフィックが均質で全ユーザーが同じトラフィックモデルを有するＥＦユーザーであるシナリオについて検討する。スケジューラは、最初に、一組の単一ユーザー送信フォーマット及び多ユーザー送信フォーマットに関する候補送信インスタンスのリストを作成する。単一ユーザーフォーマットには、対応するユーザーの待ち行列からのビットがスタッフィングされる。多ユーザーフォーマットには、適合可能なＤＲＣを有するユーザーの待ち行列からのビットがスタッフィングされる。
【０１０８】
次に、スケジューラは、各々の候補インスタンスにパケットメトリックを割り当て、最大のパケットメトリックに該当する候補送信インスタンスを選択する。該パケットメトリックは、「スループット多項式」であることができ、比較動作は、適切に定義された最大化を提供する「辞書的」比較であると定義される。  
全ユーザーがＥＦユーザーであり、さらに各ユーザーが同じ型、例えばＶｏＩＰ専用システム、の１つのＥＦフロー、及び多ユーザー送信フォーマットを有する特殊事例に関するパケットメトリックについて検討する。この場合は、該フォーマットに関する多ユーザー送信インスタンスを生成するために適合可能ＤＲＣを有するユーザーの待ち行列からのビットがスタッフィングされる。これらのユーザー間において、対応するＩＰデータグラムのタイムスタンプに基づいて先入れ先出し方式でビットが選択される。本例に関しては、遅延限度は同じであると想定されている。同じタイムスタンプを有するビット間では、ＩＰパケット内での順序に従って選択が行われ、異なるユーザー間では、パケット内にデータを有するユーザー数を最小にするような形で選択が行われる。
【０１０９】
送信インスタンスのペイロード多項式は、次式のようになる。
【数１】
2007536827.tif 000003
【０１１０】
ここで、Ｂｎは、ｎのスロットの遅延を被る候補送信インスタンス内に含まれるビット数を表す。ビットが遅延限度を超える時間にわたって待ち行列内に存在しており従ってＤのスロットを超える遅延状態にあるときにはこれらのビットを待ち行列から取り出すことができるため、Ｄの値は遅延限度に等しくすることが可能である。
【０１１１】
前記スループット多項式は、ペイロード多項式をフィルタリング及びサブサンプリングすることによって得られる。一方法は、ペイロード多項式の係数ベクトルをＮのグループに分割し、次に、各グループ内の係数を合計してペイロード多項式の簡約表現を得ることである。これで、スループット多項式は、簡約されたペイロード多項式を、全対象ユーザーによって復号される候補送信インスタンスに関する予想スロット数で割ることによって得られる。該手順は図７に示されており、該図において、最上行はペイロード多項式p(x)で、最下行は、ペイロード多項式の簡約表現であるc(x)である。変数ｘは、送信インスタンスインデックスである。
【０１１２】
従って、スループット多項式は次式によって与えられる。
【数２】
2007536827.tif 000004
【０１１３】
ここで、Ｎｇは、検討中の送信フォーマットに関する「一般的」スパンであり、該スパンの計算方法が以下において説明される。得られたスループット多項式は、各々が同様の方法で得られた一組のその他の様々な代替の間で候補送信インスタンスを選択する際のパケットメトリックとして用いられる。
【０１１４】
上記のパケットメトリックは、レーテンシーの強制とスループットとの間における二者択一を示唆していることに注目すること。Ｎ−１がＤと等しくなるように選択された場合、すなわち、c(x) = p(x)である場合は、パケットメトリックは、最長の遅延状態にあるビットの送信を最初に強制する。次に、２番目に長い遅延状態にあるビットが候補送信インスタンス選択において考慮される。この手順は、パケットメトリック（すなわち、スループット多項式）を比較する際に用いられる「辞書的」比較が行われることによるものである。このように、比較は、最初に各多項式の最高次数を識別することから始まる。ある１つの多項式の次数がより高い場合は、該多項式がより大きい多項式として定義される。両方の多項式が同じ次数を有する場合は、係数の比較が行われて最初に最高次数が比較される。より大きい係数が１つの多項式において見つかった場合は、該多項式がより大きい多項式として定義される。
【０１１５】
c(x)を得るためにp(x)の係数をセグメンテーションすることは、各セグメント内のビットに対応する発生遅延の差を暗黙に無視することである。その見返りとして、現時点においてより高い柔軟性を有するスループットの最大化が行われる。最も柔軟なスループットの最大化が可能になるのは、p(x)のすべての係数が単一のセグメント（例えば、次数がゼロのc(x)）において結合された場合である。
【０１１６】
一例においては、２つのセグメント（例えば、次数が１のc(x)）は、折衷案を提供する。次数が最も大きい項が最も大きい影響を有する。様々な候補インスタンス間で同じ次数である場合は、c(x)の項が考慮される。従って、p(x)の係数を３つ以上のセグメントにセグメンテーションする必要がない場合がある。その結果、最適化する変数は単一になり、該変数はαで表され、「遅延分」と呼ばれる。要約すると、セグメントが２つの場合は、c(x) = (hi2)z−1 + (hi)であり、ここで、"hi2"及び"hi"は、各セグメントにおけるそれぞれのビット数である。より具体的には、hi2は、遅延限度のα倍よりも長い遅延状態にある候補送信インスタンスに含まれているビット数であり、"hi"は、より短い遅延状態にあるビット数である。
【０１１７】
すべてＥＦトラフィックであるがトラフィックモデルが異なる（例えば、遅延限度が異なる）ユーザーの場合は、引数が修正される。より小さい遅延限度を有するビットは、より大きい遅延限度を有するビットよりも速くhi2セグメントの一部になる。この場合における当然の方法は、候補送信インスタンス内にビットをスタッフィングする際に及びビットがhi2ギアの一部になるべき時点を決定する際に「遅延」単独ではなく遅延のβ倍を使用することである。
【０１１８】
一般的には、βは、遅延限度よりも１大きい値に比例するように設計される。その結果、より低い遅延限度を有するＥＦビットがより高い遅延限度を有するＥＦビットよりも優先される傾向があることになる。
【０１１９】
図８は、一実施形態によるスケジューラを示した図である。スケジューラ６００は、待ち行列情報を格納及び維持するために適合されたメモリ記憶装置６０４に結合された適応型遅延制御装置６０２を含む。メモリ記憶装置６０４は、遅延及び／又はスループット影響度、優先度クラス、例えばＥＦ、ＢＥ、等を含む各待ち行列関連の情報、及びスケジューラ内に組み入れることができるその他の情報、例えばその他のＱｏＳ情報も格納する。メモリ記憶装置６０４内に格納された待ち行列データ及び情報は、ビットメトリック計算装置６０８及びビットスタッフィングメトリック計算装置６０６に提供される。これらの装置は、ビットメトリック及びビットスタッフィングメトリックをそれぞれ生成する。計算されたビットメトリックは、ビットメトリック計算装置６０８、パケットメトリック計算装置６１６、及び待ち行列選択装置６１０に提供される。ビットスタッフィングメトリック及び選択された待ち行列は、候補送信インスタンス生成器６１２に提供される。パケットメトリック計算装置６１６から得られたパケットメトリックは及び生成器６１２によって生成された候補送信インスタンスの組は、送信インスタンス選択装置６１４に提供される。
【０１２０】
図９は、送信待ち状態の複数の待ち行列を格納したメモリ記憶装置６０４の詳細を示した図である。待ち行列データは、待ち行列データ６２０として１つのフローごとに格納される。各待ち行列６２０に関して、対応するＱｏＳクラス又は優先度クラス６２２と影響度指定子６２４が存在する。
【０１２１】
図１０は、一実施形態によるスケジューリング方法を示した流れ図である。方法５００は、最初に判断ボックス５０２において、ＦＬがビジーであるかどうか、すなわち新たなパケット送信のためにタイムスロットが利用可能であるかどうかを決定する。新たなパケット送信のためにタイムスロットが利用可能である場合は、スケジューラは、ステップ５０４において、部分組の定義された及び導き出された送信フォーマットに基づいて候補送信インスタンスリストを生成する。ステップ５０６において、各候補送信インスタンスに対応するパケットメトリックが計算される。ステップ５０８において、スケジューラは、パケットメトリックに関する最大値を有する送信インスタンスを選択する。ステップ５１０において、送信インスタンスが送信のためにフォーマット化される。
【０１２２】
図１１は、方法５００において一組の候補送信インスタンスを生成しさらにステップ５０４を実装する一実施形態を示した図である。ステップ５２０において、スケジューラは、待ち行列の各エントリに関するビットメトリックを計算する。ステップ５２２において、スケジューラは、各待ち行列に関するビットスタッフィングメトリックを計算する。ステップ５２４において、送信インスタンスに関する一組の待ち行列を選択するためにビットメトリック値が比較される。ステップ５２６において、ビットスタッフィングメトリックが用いられ、待ち行列の組を用いて候補送信インスタンスが生成される。前記計算及び比較に関する方法例及び手段例が以下において説明される。
【０１２３】
一実施形態においては、単一ユーザーフォーマットを有する候補送信インスタンスが送信待ち状態のデータを有する各ユーザーに関して生成されることに注目すること。送信フォーマットは、前記ユーザーのＤＲＣに対応する基準フォーマットに設定される。ＮＵＬＬ  ＤＲＣが受信されているユーザーに関しては、該ユーザーが送信待ち状態の“ＥＦ”データを有する場合のみに候補送信インスタンスが生成される。ＢＥ／ＡＦユーザーに関しては、これらのユーザーは無線層プロトコル（ＲＬＰ）層において低いドロップ率を維持することを試みるため、ＮＵＬＬ  ＤＲＣは提供されない。
【０１２４】
定義された及び導き出された各「基準」多ユーザーフォーマットに関して、多ユーザーフォーマットを有する候補送信インスタンスが生成される。導き出されたフォーマットをこの段階において許容するためにフラグを使用することができる。
【０１２５】
ステップ５０６において生成された候補送信インスタンスの組は、「基準」フォーマットに基づいたものであることに注目すること。すなわち、このステップにおいては短いパケットは含められない。この場合の目的は、基地局により近いユーザーの方にスケジューラを偏向しやすくすること及び基地局から遠いユーザーが短いパケットを乱用してＦＬスループットを低下させるのを回避することである。短いパケットは、選択された候補送信インスタンスが短いパケットに適合するペイロードを有するときにパッキング効率最大化ステップにおいて使用される（図１２において例示）。
【０１２６】
パッキング効率最大化ステップは、図１２と一致した形で実施することができる。このステップにおいては、選択された候補送信インスタンスは、下記の規則に従って送信フォーマットを変更することができる。
【０１２７】
（１）選択された候補送信インスタンスが単一ユーザーのデータを含む場合は、再選択されたフォーマットは、該ユーザーのＤＲＣと適合可能な単一ユーザーフォーマット又は多ユーザーフォーマットのいずれかになることが許容される。
【０１２８】
（２）選択された候補送信フォーマットが２つ以上のユーザーのデータを含む場合は、再選択されたフォーマットは、別の多ユーザーフォーマットにしかなることができない。いずれの場合においても、ペイロードを搬送できる最小フォーマットが選択される。この事後変換は、幾つかの多ユーザーフォーマットへの変換を回避することができるフラグによってさらに制御される。
【０１２９】
一実施形態においては、送信インスタンスをフォーマット化するステップ５１０は、スケジューラが送信インスタンスのパッキング効率を最大化するステップ５３０と、スケジューラが事前のＡＣＫ計算を行うステップ５３２と、をさらに含む。図１２参照。さらに、ステップ５３０は、図１３に示されている方法を含むことができる。最初に、判断ボックス５４０において送信インスタンスの評価が行われ、単一ユーザーフォーマットが使用されているかどうかが決定される。単一ユーザーフォーマットが使用されている場合は、各ステップが以下においてさらに詳細に説明される。
【０１３０】
一実施形態においては、スケジューラは、選択された送信インスタンスがデータビットを搬送することになるユーザーのＤＲＣに対応する最大スパンを決定する。スケジューラは、指定された数の送信スロットをカウントする。送信された情報を正確に受信したことをまだ応答してない、即ちＡＣＫメッセージを送信してないユーザーが存在する場合で、いずれかの待ち行列内に送信待ち状態のデータが存在する場合は、ＡＮは送信を終了させる。
【０１３１】
一代替実施形態は、図１０に示されている方法５００、例えば、限定することなしに、各候補送信インスタンスを生成するためのビットスタッフィング及びパケットメトリックの計算、を完了させる特定の手段および方法を含む。
【０１３２】
ビットスタッフィングはステップ５０８の送信インスタンスフォーマット化の一部である一方で、ステップ５０８においてパケットメトリック計算が行われる。一般的には、単一ユーザー送信インスタンスは、同じユーザーの１つ以上のフローからのビットをスタッフィングすることができる。「定義された」フォーマット、例えば表１において定義されているフォーマット、を有する多ユーザーインスタンスは、多ユーザーフォーマットと適合可能なＤＲＣを送信している１人以上のユーザーからのビットをスタッフィングすることができる。「導き出された」フォーマットを有する多ユーザーインスタンスは、多ユーザーフォーマットと適合可能なＤＲＣを送信しさらに「ソフトな適合性」の追加要求を満たす１人以上のユーザーからのビットをスタッフィングすることができる。ＤＲＣは、対応する「定義された」フォーマットを復号するための予想スロット数が導き出されたフォーマットのスパンよりも小さいか又は等しい場合に該導き出されたフォーマットにとってソフトな適合可能であるとみなされる。前記予想スロット数は、受信されたＤＲＣに関して要求される信号干渉雑音比（ＳＩＮＲ）を、導き出されたフォーマットを（例えば平均白色ガウス雑音（ＡＷＧＮ）状態下において）成功裡に復号するために要求されるＳＩＮＲと比較することによって得ることができる。代替として、前記予想スロット数は、要求速度を導き出されたフォーマットの有効データ速度と比較することによって決定することができる。
【０１３３】
以下の説明は、ｉ）ＢＥ／ＡＦを含むＱｏＳクラス、及び１つのクラスのＥＦを想定している。該方法は、複数のＥＦクラスへの拡張も許容する。本発明によれば、待ち行列内において送信待ち状態の各ビットは、以下の形を有する多項式として与えられるビットメトリックが割り当てられる。
【数３】
2007536827.tif 000005
【０１３４】
ここで、ｉは、ビットのインデックスであり、３つの係数（hi2、hi、1o）のうちの１つのみがゼロでないことが許容される。この説明はビットレベルに関する説明であるが、典型的にはＩＰデータグラム内の全ビットが同じメトリックを有すること及びパケットメトリック計算は必ずしもビットレベルの累積が関わらないことに注目すること。
【０１３５】
δをＥＦフローからのビットと関連づけられた現在の遅延とする。hi1及びhiに関して次のような定義を設ける。
【数４】
2007536827.tif 000006
【０１３６】
ここで、βは、ＥＦフローと関連づけられた変数であり、遅延限度に反比例する。μは大きな数字であり、αは一定のスカラー、例えば０．２５であり、ＢＥフロー型から独立している。
【０１３７】
ＢＥ／ＡＦフローに関しては、1oを次式のように設定する。
【数５】
2007536827.tif 000007
【０１３８】
ここで、AvgThroughputは、対応するユーザーの平均スループットであり、TrgtThroughputは、該ユーザーに関する最低の希望スループットである。ＢＥユーザーの場合は、TrgtThroughputはゼロに設定される。これで、パケットメトリック（例えば、スループット多項式）が次式によって得られる。
【０１３９】
PacketMetric = AccumulatedBitMetric / Ng
ここで、Ngは、対象となる定義された又は導き出された候補送信インスタンスの一般的スパンであり、累積ビットメトリック（AccumulatedBitMetric）は、候補インスタンス内に含められている（又はスタッフィングされている）全ビットに対応するビットメトリックの合計である。値Ngは、定義された又は導き出された型の公称スパンに設定することができる。代替として、該値は１に設定することができ、この場合は、パケットメトリックは、累積ビットメトリックと等しくなる。この場合は、スケジューラは、送信インスタンス当たりのスループットではなく送信インスタンス当たりのペイロードを最大化するように動作する。この動作は、ＤＲＣの影響が及ばなくなるという望ましくない影響を及ぼし、それによって性能低下を引き起こして該性能低下が図６に示されている動作に従わなくなる可能性がある。他のアプローチ法は、Ngを「疑似スパン」に設定することであり、この「疑似スパン」は、１スロット及び２スロットの高速パケットに関しては１、４スロットパケットに関しては２に設定され、以下同様であり、ペイロードに基づいて高速パケットを区別することができ、他方、低速フォーマットはNgをより大きな値に設定することによって阻止される。
【０１４０】
以下のプロパティは、基地局に近い位置に所在するユーザーの方にスケジューラを向かわせることになる。
【０１４１】
（１）ＤＲＣが多ユーザーフォーマットと適合可能である場合は、より遅い公称データ速度を有するすべての多ユーザーフォーマットとも適合可能である。
【０１４２】
（２）スケジューラは、「スループット」多項式を選択手段として使用する。
【０１４３】
一設計は、ビットメトリックに関する係数hi及びhi2を定義する際に大きな値のμ項を使用する。μは全ビットにとって共通であるため、ビットは、βδの値に従った順序で埋め込まれる。パケットメトリックは、あたかもビットメトリックの対応するエントリが１に変更されてその結果スループット多項式に比例するパケットメトリックが得られるように計算される。この計算は、パケットメトリックを計算する上でのパケットメトリック内のβδの影響を排除するものである。
【０１４４】
上記のように、スケジューラは一定のDelayBoundを全ユーザーに適用することに注目すること。典型的には、良好なカバレッジを提供されているユーザーは、DelayBoundのほんの一部分しか要求しない。ユーザー数が増加するに従い、最初に最も弱いユーザーにおいて等級引き下げが始まり、基地局に近い位置に所在するユーザーは、負荷による影響を強く受けない。
【０１４５】
一実施形態は、良好な    ＥＦユーザーの割合を測定することによって遅延限度変数と関連変数（例えばα）を適応的に設定する。スケジューラによって用いられるDelayBoundは、良好なユーザーの割合を望ましいレベルに維持するために反復的に引き上げること又は引き下げることができる。一実施形態においては、DelayBoundに関してより低い限度を有する単純な一次数ループが実装される。
【０１４６】
上述されるスケジューラ内において、ＢＥ／ＡＦユーザーに関するビットメトリックを定義する方法は次の計算を用いる。
【０１４７】
ビットメトリック =  I / [AvgThroughput − TargetThroughput]
異なるシステム、動作目標、及び設計に関してはビットメトリックに関するその他の定義を実装することができる。
【０１４８】
１ｘＥＶ−ＤＯ  Ｒｅｌ−０、及びＤＲＣインデックス０ｘ０、０ｘ１、及び０ｘ２に関する適合可能多ユーザーフォーマットを定義した改訂Ａ仕様への最近の寄稿における変更案が含まれている改訂Ａ仕様においてそれぞれ定義されている２組のプロトコルサブタイプに関して、各ＤＲＣインデックスと適合可能なＦＬ送信フォーマットが表１に記載されている。改訂Ａ仕様において示されているような送信フォーマットは、３つ組（PacketSize、Span、PreambleLength）によって表される。"PacketSize"は、送信フォーマットが搬送するビット数であり、巡回冗長符号（ＣＲＣ）及びテールを含む。"Span"は、送信インスタンスが順方向リンクにおいて占めることになる公称（例えば最大）スロット数である。"PreambleLength"は、プリアンブルチップの総数である。１ｘＥＶ−ＤＯ仕様の改訂Ａにおけるように、各ＤＲＣに関する「基準」送信フォーマットはボールド体で示されている。Ｒｅｌ−０は、単一ユーザー送信フォーマットのみを定義し、改訂Ａの幾つかのサブタイプは単一ユーザーフォーマット及び多ユーザーフォーマットの両方を定義している点に注目すること。さらに、改訂Ａでは、複数の送信フォーマットを各ＤＲＣインデックスに関して定義することができる。ＡＴは、これらのフォーマットの各々においてパケットを受け取ることを試みる。多ユーザーフォーマットは、それぞれの一意のＭＡＣインデックスによって区別される。すなわち、各多ユーザーフォーマットに関するプリアンブルは個別のウォルシュカバーを使用する。単一ユーザーフォーマットはすべて、ユーザーに割り当てられたＭＡＣインデックスを使用する。
【表１】
2007536827.tif 000008
【表２】
2007536827.tif 000009
【０１４９】
念のため繰り返すと、送信インスタンスは、転送するために選択された１つ以上の待ち行列からの特定の一組のビットを有する送信フォーマットを意味する。候補送信インスタンスは、送信可能であるかどうかの評価がスケジューラアルゴリズムによって行われる送信インスタンスを意味する。多ユーザー送信フォーマット（１０２４，４，２５６）、（２０４８，４，１２８）、（３０７２，２，６４）、（４０９６，２，６４）、及び（５１２０，２，６４）は、基準多ユーザー送信フォーマットと呼ばれる。多ユーザー送信フォーマット（１２８、４，２５６）、（２５６，４，２５６）、及び（５１２，４，２５６）は、「非基準多ユーザーフォーマット」と呼ばれる。導き出された送信フォーマットは、あたかも早期終了によって定義済みフォーマットから得られるかのように、対応する定義済みフォーマットのスパンを公称値よりも小さい値に単純に設定することによって得られる。要約すると、送信フォーマット及び送信インスタンスは、基準又は非基準、単一ユーザー又は多ユーザー、定義される又は導き出される、であることができる。「公称スロット数」という表現は、定義された送信フォーマットに関する最大スロット数及び導き出された送信フォーマットに関する再定義された最大スロット数を意味するために用いられる。
【０１５０】
スケジューリング手段および方法に関する以下の説明は、オクテットに基づくスケジューリングを考慮しており、様々な待ち行列内において送信待ち状態のオクテットをあらゆる量において（オクテット単位で）対応することができる。典型的には、各フローは、少なくとも１つのデータ待ち行列として格納される。従って、各待ち行列は、関連づけられた特定のＱｏＳ要求を有する。データは、オクテット単位で各待ち行列内に格納される。スケジューリングでは、１つのオクテット未満のデータがＦＬで送信するために送信インスタンス内又は物理層パケット内に入れられる。
【０１５１】
幾つかのアプリケーションはフレームに基づくスケジューリングを要求することがある点に注目すること。この場合は、フローの（実装された）データグラムが物理層パケット内においてフラグメンテーションなしに対応される。オクテットに基づくスケジューリング手段および方法は、フレームに基づくスケジューリングに拡張することも可能である。
【０１５２】
さらに、受入制御はスケジューリングに密接に関連している点にも注目すること。この場合は、受入制御は、現在のシステム負荷に基づいて、及び既に受け入れられているフローに関する受入不能な等級引き下げが行われずに条件を満たした形で（例えば、ＱｏＳ目標が満たされた状態で）入フローに対応できるかどうかを予測することによって、これらの入フローを受け入れる／拒否する働きをする。
【０１５３】
本明細書において用いられる「フロー」は、所定のユーザーに指向されたデータストリームを意味する。フロー源は、１つ以上のユーザーアプリケーションであることができ、限定することなしに、特にファイルダウンロード（ｆｔｐ）、ウェブサーフィン（ｈｔｔｐ）、オンラインゲーム、又はＶｏＩＰを含む。フローは、例えばシグナリングフローのように通信システム自体によって生成することができ、これらのシグナリングフローは、ユーザーセッションを適切に維持しながらシステムの稼働状態を維持する働きをする。
【０１５４】
他のフロー例は試験アプリケーションによって生成されるデータストリームであり、該データストリームは、通信システムの少なくとも一部を試験するために使用される。
【０１５５】
換言すると、フローは１つのデータストリームであり、さらに少なくとも１人のユーザーへの通信の一部である。様々なアプリケーションフローが存在しており、これらの各々のアプリケーションフローは、特定のＱｏＳ要求及び公差を有する。各フローは、目標スループット及び遅延限度、等の異なる一組のＱｏＳ要求を有することができる。以下では、これらの要求例が具体的に説明される。
【０１５６】
ユーザーは、異なるＱｏＳ要求を有する複数の同時並行フローを有することができる。各フローは、ＶｏＩＰ、ｆｔｐ、シグナリング、等に関するような単一のアプリケーションによって生成することができ、又は、基地局コントローラ（ＢＳＣ）によって単一のフローに統合される複数のアプリケーションによって生成することもできる。ＢＳＣがこのような形でフローを統合する場合は、統合されたフローは、スケジューラにとっては適切に定義されたＱｏＳ要求を有する単一のフローに見える。スケジューラは、異なるアプリケーションによって生成されたが１つの統合フロー内に含められているデータを区別することができない。スケジューラによって行うことができる他の型の統合が以下において説明される。
【０１５７】
各フローは、第１回目の送信（ＦＴｘと呼ばれる）のためのデータを保有する少なくとも１つの待ち行列を有しており、さらに、無線層プロトコル（ＲＬＰ）再送信待ち行列（フローｘのＲＴｘ待ち行列）及び／又はＭＡＣ層再送信待ち行列（遅延自動再送要求（ＡＲＱ）、又は遅延ＡＲＱ（ＤＡＲＱ）待ち行列）、等の追加の再送信待ち行列を有することができる。一実施形態においては、各待ち行列内のすべてのオクテットは、適切に定義されたタイムスタンプを有しており、スケジューラは、該タイムスタンプを用いて、オクテットの現在の遅延状態を決定することができる。これらのタイムスタンプは、（実装された）データグラム、等のデータバーストに割り当てることができ、これらのデータバーストの各オクテットが同じタイムスタンプを有することを示している。個々のデータグラムは、複数のアプリケーションレベルのフレームを搬送することができ、これらのフレームは、異なる時点においてアプリケーションによって生成しておくことができる。アプリケーションフレームタイムスタンプはスケジューラに知られていないと想定されている。この想定は適切である。その理由は、搬送されたアプリケーションフレームを受信側アプリケーションによって構文解析できるようになるためにはその前に完全なデータグラムがユーザーによって成功裡に受信されている必要があるためである。
【０１５８】
一実施形態によるスケジューラの設計においては、次の３つの主なＱｏＳクラスが考慮される。すなわち、ベストエフォート（ＢＥ）は用語説明において定義されているとおりであり、具体的には、典型的に相対的に大きいエンド・ツー・エンド遅延の余裕があるが低いビット誤り率（ＢＥＲ）を要求するフローを意味する。スループットに関する最低限の要求は存在しないが、送信されるデータのサイズを大きくすることができる。ＢＥフローであるとみなすことができるフロー例は、ファイルダウンロード（ｆｔｐ）及びウェブサーフィン（ｈｔｔｐ）を含む。保証転送（ＡＦ）は、一般的にあるレベルの遅延を許容するためＢＥフローと類似するフローを意味する。しかしながら、ＡＦフローは、典型的には最低限の平均スループットを有する点がＢＥと異なる。ＡＦフローとして分類されるアプリケーションの一例は、ビデオ会議アプリケーションによって生成される映像ストリームである。優先転送（ＥＦ）は、必ずではないが典型的にはスループットに関して緩い要求を有し、遅延に関して厳しいエンド・ツー・エンド要求を有するフローを意味する。信頼性に関する要求は、ＢＥフローに関する要求ほど厳しくなくすることができ、小さい割合のアプリケーションデータ、例えば１乃至２％を失っても許容可能である。ＥＦフローとして分類されるアプリケーション例は、限定することなしに、ＶｏＩＰ及びオンラインゲーム、等を含む。
【０１５９】
スケジューリング手段及び方法に関しては、ＢＥフローとＡＦフローとの間の違いは、スループットに関する最低限の要求の有無であり、ＢＥフローに関する最低限のスループット要求はゼロである。その他の点に関しては、これらの２つのＱｏＳクラスは類似している。次に、特定のフローをさらに区別するため、様々な異なる型のアプリケーションを含むＥＦクラスについて検討する。ＥＦクラスのフロー内には、優先度が異なるフローが存在することができる。一例として、ＶｏＩＰ及びビデオ会議アプリケーションの音声部分、等のアプリケーションは、ビデオ会議アプリケーションの映像部分よりも優先度が高いとみなすことができる。オンライゲームは、音声及び映像の両アプリケーションよりも優先度が低いとみなすことができる。
【０１６０】
ユーザーアプリケーションによって生成されるフローに加えて、ＩＳ−８５６をサポートするシステムは、システムの動作を維持するために要求されるシグナリングフロー、及びシステムの試験に用いられるテストアプリケーションによって生成されるフロー、等のフローを内部において生成している。
【０１６１】
典型的ＱｏＳ要求は、限定することなしに、遅延限度、目標スループット、信頼性、ジッター、等を含む変数によって示される様々な考慮事項に関して表すことができる。
【０１６２】
遅延限度は、"DelayBound"と呼ばれる変数によって識別される。DelayBoundは、各フローに関して指定された変数であり、データグラムを成功裡にユーザーに引き渡さなければならないときの最大遅延を意味する。DelayBoundは、データグラムのタイムスタンプに関して測定され、本実施形態においてはオクテットである。この遅延限度は、ＦＬ遅延以外の遅延収支成分を含むことになるエンド・ツー・エンド遅延限度とは異なることに注意すること。一実施形態においては、データグラムのDelayBoundに達した時点で、該データグラムが待ち行列から取り出される。換言すると、データグラムを指定された遅延限度内に送ることができない場合は、該データグラムは廃棄される。
【０１６３】
目標スループットは、別の指定されたＱｏＳ変数であって"TargetThroughput"と呼ばれる変数によって識別される。目標スループットは、フローに関して要求される最低の平均スループットを意味する。スループットの平均を求めることは、適切な時定数を有する1
次無限インパルス応答（ＩＩＲ）フィルタを通じて定義することができる。一実施形態においては、前記時定数は１ｍｓに設定される。
【０１６４】
第３のＱｏＳ要求は信頼性である。典型的には、システムの物理層は１％のパケット誤り率（ＰＥＲ）を提供し、このＰＥＲは、ファイルダウンロードのように例外的に低い誤り率を要求するアプリケーションに関しては十分でない可能性がある。従って、空中での損失をさらに低減させるために再送信機構を利用することができる。典型的再送信機構は、ＲＴｘ等のＲＬＰ再送信及びＤＡＲＱ等のＭＡＣ層再送信である。これ以外には、送信制御プロトコル（ＴＣＰ）をアプリケーションに関する転送層プロトコルとして用いて信頼性をさらに向上させることができる。
【０１６５】
一実施形態においては、スケジューラは、フロー全体において公平性を提供しさらに各フローに関する一定の優先度要求及びＱｏＳ要求を満たしつつシステム容量を最大化するように設計されている。容量及び公平性の概念は、個々のフローのＱｏＳ要求に依存する。ＢＥフローに関しては、容量は、セクターによって送信される総ＢＥスループットであると定義することができる。特定の型のＥＦフローに関しては、容量は、ＱｏＳ要求を満たしながらサポートすることができるユーザー数であると定義することができる。ＥＦフロースケジューリングの一例においては、システムは、平均してアプリケーションデータフレーム（又はオクテット）のうちの９８％を成功裡に受け取るユーザー数が９５％に達するようなＶｏＩＰユーザー数が選択されることをＶｏＩＰ容量として定義する。一例においては、指定されたDelayBound内において送信エラーなしで受け取られたフレームによって成功又は不成功が決定される。代替成功判定基準を使用することもできる。フロー全体における公平性を達成させるために、ＢＥフローのスケジューリングに関して比例的公平性（ＰＦ）基準を使用することができ、さらに優先度判定基準に従ったＥＦフローのスケジューリングを行うことができる。この方法により、システム負荷が増大するに従ってＢＥフローは平等に等級が引き下げられる。すなわち、差別なしにＢＥフローの等級が引き下げられる。
【０１６６】
ＥＦフローに関しては、システム負荷の増大及び混雑の発生に従ってユーザー間において不平等な等級の引き下げを行うことが望ましい。該等級引き下げは、最も低い優先度を有するとみなされるＥＦフローによって最初に感じられる。同様のＱｏＳ要求及び同じレベルの優先度を有するＥＦフロー間においては、等級引き下げは最初にチャネル状態が最悪であるユーザーに関するフローに対して影響を与えることになる。このアプローチ法を用いた場合は、システムの混雑が増すに従って、可能な限り数多くのＥＦフローが各々のＱｏＳ要求を満たすことができる。このアプローチ法では、通常は、ユーザーのチャネル状態とＥＦフローに関する遅延上の統計数字がほぼ反比例の関係になる。このプロパティは、「遅延公平性」と呼ばれる。
【０１６７】
「送信フォーマット」は、ＦＬパケットの幾つかの変数を記述する３つ組の形態（PacketSize、Span、PreambleLength）である。PacketSizeは、ビットを単位とする物理層ペイロードを意味し、Spanは、該フォーマットのパケットを送信することができる最大スロット数であり、PreambleLengthは、チップを単位とするプリアンブル継続時間である。
【０１６８】
ＩＳ−８５６をサポートするシステムにおいては、各ユーザーに関するＦＬ送信データ速度を決定するためにリンク適合化が使用される。各ＡＴは、該ＡＴがデータを受信できる最高データ速度を示すデータ要求を送信する。該データ要求は、データ速度制御（ＤＲＣ）メッセージと呼ばれる。ＤＲＣメッセージフォーマットは、様々なＤＲＣインデックスを使用し、各々のＤＲＣインデックスが送信フォーマットを指定する。ＡＴは、ＤＲＣメッセージをＤＲＣチャネルで送信する。ＩＳ−８５６  Ｒｅｌ−０におけるＮＵＬＬ  ＤＲＣを除く各有効ＤＲＣインデックスに関して、ユーザーに対してデータを搬送するためにＦＬで対応することができる１つ以上の単一ユーザー送信フォーマット及びゼロ以上の多ユーザー送信フォーマットが存在する。表１は、ＩＳ−８５６において定義されているＤＲＣインデックスの詳細を示した表である。さらに、表１は、各ＤＲＣインデックスに関する適合可能な送信フォーマットをさらに含む。
【０１６９】
1ｘＥＶ−ＤＯ 改訂Ａ仕様においては、各ＤＲＣインデックスに関して、適合可能な単一ユーザー送信フォーマットのうちの１つが、該ＤＲＣに関する基準フォーマットとして定義される。本明細書において用いられるＤＲＣは、ＡＴによって要求されてＤＲＣインデックスによって識別される特定のフォーマットに対応することに注目すること。一般的には、所定のＤＲＣに対応する基準フォーマットを用いて送信されたパケットをＡＴが成功裡に復号した場合は、該ＡＴは、いずれかの適合可能な非基準単一ユーザーフォーマットで又はいずれかの適合可能な多ユーザーフォーマットで送信されたパケットを成功裡に復号する可能性が高い。ただし、ＤＲＣインデックス０ｘ０、０ｘ１、及び０ｘ２は例外である。所定のＤＲＣと適合可能な幾つかの多ユーザーフォーマットは、基準フォーマットよりも大きなプリアンブル長を有することが可能であるため、これらのフォーマットの場合は必ずしもデータ処理上の利得が得られることにはならない点に注意すること。
【０１７０】
ＤＲＣインデックス０ｘ０と適合可能な全フォーマット及び０ｘ１及び０ｘ２のＤＲＣインデックスと適合可能な多ユーザーフォーマットを除くあらゆるＤＲＣに関して、非基準フォーマットのペイロードサイズは、典型的には、基準フォーマットのペイロードサイズよりも小さいか又は等しい。さらに、非基準フォーマットのスパンは、典型的には、基準フォーマットのスパンよりも大きいか又は等しい。０ｘ０のＤＲＣインデックス（例えば、ＮＵＬＬ速度要求）が受信されているユーザーが何らかのフォーマットで対応される場合は、一般的には、信頼できるパケット受信は保証されていない。さらに、０ｘ１及び０ｘ２のＤＲＣインデックスに関しても、適合可能多ユーザー送信フォーマットは、これらのフォーマットのペイロードサイズ及びスパンがこのプロパティを満たしていないため十分に信頼できる受信を保証することができない。
【０１７１】
一実施形態においては、スケジューラは、受信されたＤＲＣが０ｘ０、０ｘ１、又は０ｘ２であるユーザーに対応するために多ユーザーパケットを利用することができない。さらに、ＮＵＬＬ  ＤＲＣ（０ｘ０）が受信されたユーザーに対するサービスは、一定の条件に限定することができる。これらの条件は、設計によってシステム内に組み入れることができる。
【０１７２】
多ユーザー送信フォーマットに関して、ある所定のＤＲＣがある所定の多ユーザーフォーマットと適合可能である場合は、同じＤＲＣは、それよりもデータ速度が低いすべての多ユーザーフォーマットと適合可能である。
【０１７３】
「送信インスタンス」は、送信フォーマットと、該フォーマットのパケットによって搬送できるデータオクテットのアイデンティティとの組合せを意味する。例えば、パケットがデータオクテットを搬送する先であるユーザーに関するＭＡＣインデックスの組及びいずれのオクテットをパケットに入れて搬送すべきかを正確に示す一組の対応待ち行列ポインタが送信フォーマットを定義することができる。
【０１７４】
スケジューラは、一組の仮定の送信インスタンスを生成し、これらのインスタンスのうちの１つをＦＬで送信するために選択することができる。本明細書においてこれらの仮定の送信インスタンスを表すために用いられる表現は、「候補送信インスタンス」である。
【０１７５】
適応型遅延管理を組み入れたスケジューラの一実施形態においては、様々なメトリックが該スケジューラによって使用され、これらのメトリックは、１）ビットスタッフィングメトリックと、２）ビットメトリックと、３）パケットメトリックと、を含む。ビットメトリックは、現在の送信インスタンス内に組み入れる資格を有する待ち行列を選択するために使用される。ビットスタッフィングメトリックは、様々な待ち行列において送信待ち状態であるビット（又はオクテット）がある所定の候補送信インスタンスに含められる順序を決定する。候補送信インスタンスが生成された時点で、該候補送信インスタンスに関するパケットメトリックが計算される。次に、該パケットメトリックは、一組の同様に生成された候補送信インスタンスの中から最適の送信インスタンスを選択するために使用される。候補送信インスタンスのパケットメトリックは、候補送信インスタンス内に含められたすべてのオクテットのビットメトリックを単純に合計し、候補送信インスタンスの送信フォーマットのスパンで該合計を割ることによって決定される。
【数６】
2007536827.tif 000010
【０１７６】
ここで、ｋは、一組の代替内の特定の候補送信インスタンスを示すインデックスを表し、Span[k]は、対応する送信フォーマットに関して定義されたスパンを表し、P[k]は、候補送信インスタンス内に含められているオクテットの組を表し、BitMetric[i]は、候補インスタンス内に含められているi番目のオクテットのビットメトリックを表す。
【０１７７】
従って、パケットメトリックは、候補送信インスタンスがＦＬで実際に対応された場合における「ビットメトリックの瞬間的スループット」の推定値であると解釈することができる。
【０１７８】
一般的には、オクテットｉのビットスタッフィングメトリックが他のオクテットｊのビットスタッフィングメトリックよりも大きい場合は、オクテットｉのビットメトリックは、オクテットｊのビットメトリックよりも大きく又は該ビットメトリックと等しく設定することができる。この場合は、オクテットは、異なる待ち行列からのオクテットであることができる。同様に、オクテットｉのビットメトリックが他のオクテットｊのビットメトリックよりも大きい場合は、オクテットｉのビットスタッフィングメトリックは、オクテットｊのビットスタッフィングメトリックよりも大きく又は該メトリックと等しく設定すべきである。
【０１７９】
BitMetric[i] > BitMetric[j] => BitStuffingMetric[i] ≧ BitStuffingMetric[j]
BitStuffingMetric[i] > BitStuffingMetric[j] => BitMetric[i] ≧ BitMetric[j]
この一般的ガイドラインは、候補送信インスタンス内に埋め込まれたオクテットが、のちに埋め込まれる他のオクテットと少なくとも同じ量だけパケットメトリックに貢献することを保証する。
【０１８０】
本明細書において説明される全メトリック、及び代替メトリックは、以下のような多項式形で表すことができる。
【０１８１】
メトリック = [MC0] + [MC1] x + [MC2]x2 + [MC3]x3 + [MC4]x4 + [MC5]x5 + [MC6]x6 + [MC7]x7
ここで、メトリックは、いずれかのメトリック型であることができ、ＭＣ０，．．．，ＭＣ７は、メトリック係数を表す。２つのメトリックの加算及びスカラーによるメトリックの乗算（又は除算）は、多項式代数の場合と同じように定義され、２つのメトリックを合計時に、２つの多項式の対応係数が合計される。メトリックにスカラーを乗じる（又はメトリックをスカラーで割る）ときには、各々の係数に同じスカラーが乗じられる（又は各々の係数が同じスカラーで割られる）。この計算方法は、上記において計算されたビットメトリックを用いたパケットメトリックの計算を可能にする。
【０１８２】
比較演算子“＞、≧、＝、≦、＜”は、辞書的順序で定義される。すなわち、２つのメトリックを比較時には、最初に最高次数項の係数が比較される。等しい場合は、次に高い次数項の係数が比較され、以下同様である。２つのメトリックは、２つの多項式表現の対応係数がすべて等しい場合に等しい。比較演算は、ビットスタッフィングメトリックを比較するため及びパケットメトリックを比較するために使用される。
【０１８３】
ビットメトリック、ビットスタッフィング、及びパケットメトリック
ビットメトリック及びビットスタッフィングメトリックに関しては、対応する多項式表現の１つの項のみがいずれかの所定の時点においてゼロ以外である。ゼロでない項の次数は、ある所定のオクテットに関するビットメトリック及びビットスタッフィングメトリックに関して同じである。通常は対応する係数の名前ＭＣ０，．．．，ＭＣ７で呼ばれるこのゼロ以外の項の次数は、ビット（スタッフィング）メトリック（又は対応するオクテット）の「優先状態」と呼ばれる。比較演算の定義は、ＭＣ０項が最低優先度オクテットに対応し、ＭＣ７項が最高優先度オクテットに対応することを暗黙に示す。オクテットｉに関するビット（スタッフィング）メトリックの優先状態は、次式によって与えられる該オクテットの現在の遅延状態よって及び該オクテットが属するフローに関して定義された「優先度しきい値」と呼ばれる一組の順序が設定されたしきい値を用いて決定される。
【０１８４】
CurrentDelay[i] = CurrentTime −TimeStamp[i]
TimeStamp[i]は、オクテットｉに関する適切に定義されたタイムスタンプである。優先度しきい値によって定義された各間隔は、優先状態にマッピングされる。優先度しきい値及び定義された間隔を優先状態にマッピングすることは、各フローに関して別々にスケジューラに指定することができる。オクテットのCurrentDelay[i]は、該当する間隔を決定するためにこれらの順序が設定された組のしきい値と比較される。この比較は、ビット（スタッフィング）メトリックの優先状態を定義する。
【０１８５】
上記の動作は、Ｍ個の優先度しきい値及びＭ＋１の優先状態を各フローに関して使用する。Ｍの値は、スケジューラのソフトウェア実装である一実施形態においては２に設定される。各フローに関して、２つの優先度しきい値及び３つの優先状態が定義される。これらの優先度しきい値及び優先状態は、典型的には、フローの持続時間中は不変にすることができる。ただし、各々は、動作中に適切なＤＳＰ−ドライバコマンドを介して変更することができる。
【０１８６】
スループットの影響を受けやすいトラフィックフローに関しては、ビットメトリックは以下のように設定される。
【数７】
2007536827.tif 000011
【０１８７】
ビットスタッフィングメトリックは、次式のように設定される。
【数８】
2007536827.tif 000012
【０１８８】
ここで、
１．GoSFactorは、各フローに基づく定義済み変数であり、フロー全体において様々なレベルのサービス等級を提供するために使用される。
【０１８９】
２．AvgThroughputは、フローのフィルタリング（平均化）された総スループットであり、該フローのFTx、RTx、及びDARQ待ち行列を含む。時定数、例えば６００スロット（１秒）を有する１次無限インパルス応答（ＩＩＲ）フィルタが平均化のために使用される。
【０１９０】
３．TargetThroughputは、各フローに基づく定義済み変数である。
【０１９１】
４．Thrghpt2DelayConvFactorBMは、各フローに基づく定義済み変数である。
【０１９２】
５．Thrght2DelayConvFactorBSMは、各フローに基づく定義済み変数である。
【０１９３】
６．εは、非常に小さい正数である。
【０１９４】
遅延の影響を受けやすいフローのビットスタッフィングメトリックに関しては、優先状態に関する多項式係数は以下のように設定される。
【０１９５】
DSBSM = AccelerationFactor*CurrentDelay + AccelerationOffset
ここで、AccelerationFactorは、各フロー当たりの定義済み変数である。 AccelerationFactorは、異なるフローごとに異なる可能性があるDelayBoundを正規化する。一例として、２つの異なるオンラインゲームについて検討する。これらの２つのアプリケーションは、異なる特性を有することに起因して、異なるDelayBound設定値がスケジューラに対して指定されている可能性がある。しかしながら、一方のゲームが他方のアプリケーションよりも高い優先度を必ずしも有しているわけではない。このため、スケジューラは、両アプリケーションを等しい優先度で取り扱うことが望ましい。第１のゲームは３００ｍｓの遅延限度を有しており、第２のゲームは１５０ｍｓの遅延限度を有すると仮定する。従って、いずれの時点においても、第２のゲームに属するオクテットについては、１５０ｍｓを超えるオクテットはスケジューラが廃棄するため存在しないことになる。しかしながら、第１のゲームに属するオクテットの場合は、１５０ｍｓよりも古いオクテットが存在している可能性がある。その結果、AccelerationFactorを使用しない場合は、第１のゲームのオクテットが第２のゲームのオクテットよりも優先されることになる。各アプリケーションのAccelerationFactorを各々のDelayBound設定値に反比例させて設定することによって、スケジューラは、この望ましくない影響を正規化することができる。
【０１９６】
AccelerationOffsetは、各フローに基づく定義済み変数である。AccelerationOffset値は、AccelerationFactorがとることができる最大値の整数倍数に設定することができる。この最大値はフローとは独立しており、ソフトウェア実装によって決定することができる。一例として、AccelerationOffsetがゼロであるフローとAccelerationOffsetが正数であるフローの２つのフローにおいては、両フローが所定の候補インスタンスの送信フォーマットとＤＲＣ適合可能であると仮定して場合、前者のフローのあらゆるオクテットの前に後者のフローのオクテットが候補送信インスタンス内に含められる。
【０１９７】
ビットメトリックに関しては、優先状態に関する多項式係数は、次式のように一定値に設定される。
【０１９８】
DSBM = DSBitMetricValue
ここで、DSBitMetricValueは、ソフトな優先順位設定のために用いられる各フロー当たりの定義済み変数である。さらに、２つのアプリケーションがほぼ等しい優先度を有しているが（例えばインターネットから待ち行列への）平均入スループットが異なるときには、各フローに関するDSBitMetricValueは、より高いスループットを有するアプリケーションがＦＬパケットを効率的に満たすためにより多くのデータを単に持つことによって優先されることになるのを回避するため、該フローの典型的スループットに反比例するように設定することができる。
【０１９９】
各トラフィックフローは、FlowClass変数に基づいて、スループットの影響を受けやすいクラス又は遅延の影響を受けやすいクラスに分類される。次に、ビットメトリックＭＣＸ（Ｘは、｛０，．．．，７｝の１つの要素）は次式のように定義される。
【数９】
2007536827.tif 000013
【０２００】
同様に、ビットスタッフィングメトリックは次式のように定義される。
【数１０】
2007536827.tif 000014
【０２０１】
一実施形態においては、スケジューラは、少なくとも部分的にはソフトウェア実装として実装される。この実施形態によれば、ビットスタッフィングメトリックは、［Ｂ１５．．．Ｂ０］として示すことができる１６ビット量で表される。最上位の３つのビットは、優先状態を決定する（例えば、“０００”は、ＭＣ０にマッピングし、“１１１”はＭＣ７にマッピングする）。残りの１３の下位ビットは、計数値自体を保有する。この表現においては、ビットスタッフィングメトリック間における比較演算は、これらの１６ビット量間において直接行うことができる。
【０２０２】
ソフトウェア実装においては、ビットスタッフィングメトリックから情報を導き出すことができるため、ビットメトリックは明示で表されない。ビットメトリックの優先状態は、ビットスタッフィングメトリックの優先状態と同じである。
【０２０３】
候補送信インスタンスのパケットメトリックは、上述されている次式を当てはめることによって計算される。
【数１１】
2007536827.tif 000015
【０２０４】
オクテットのビットメトリックの１つの項しかゼロ以外にすることができないが、一般的には、結果的に得られるパケットメトリックの係数はゼロ以外にすることができる点に注目すること。
【０２０５】
多くのＤＲＣは、より小さいペイロードサイズを有する非基準単一ユーザーフォーマットと適合可能であり、従って、ＡＲＱ利得を達成させるために単一ユーザー候補を多ユーザーフォーマットに変換するのは望ましくない。
【０２０６】
スケジューラの選択ステップにおいて選択された候補送信インスタンスが多ユーザーフォーマットである場合は、本実施形態においては、（１０２４，４，２５６）を３つのフォーマット（｛１２８，２５６，５１２｝，４，２５６）のうちのいずれかに変換することのみがサポートされる（すなわち、選択されたデータオクテットを搬送できる最低速度のフォーマットが使用される）。
【０２０７】
上記のビットメトリック及びビットスタッフィングメトリックに関する説明は、各待ち行列内の各オクテットに個々のメトリックが割り当てられる一般的事例を考慮している。従って、該メトリックは、各スロットごとに再計算される。代替実施形態は、このような計算の複雑さを低減させる。待ち行列の順序がタイムスタンプによって設定されていると仮定すると、一実施形態は、該当するフローの待ち行列の待ち行列先頭オクテット間において最も古いタイムスタンプに基づいて各フローごとに１つのビット（スタッフィング）メトリックを計算する。このメトリックは、該フローの現在送信待ち中のオクテットに関して使用することができる。このような単純化は、該メトリックがオクテットのCurrentDelayの単調増加関数であると仮定している。単調増加関数でない場合は、待ち行列先頭オクテットが後続するオクテットが対応されるのを妨げる危険性がある。この単純化においては、ビットスタッフィングメトリックはフローメトリックと呼ぶこともできる。
【０２０８】
さらに、フローのＲＴｘ待ち行列内において送信待ち中の待ち行列先頭オクテットは、ＦＴｘ待ち行列及びＤＡＲＱ待ち行列において送信待ち状態になる待ち行列先頭オクテットよりも古い可能性が高い。同様に、ＤＡＲＱ待ち行列において送信待ち状態になる待ち行列先頭オクテットは、ＦＴｘ待ち行列の待ち行列先頭オクテットよりも古い可能性が高い。この理由により、一実施形態は、これらの３つの待ち行列間で最も古いタイムスタンプを見つけ出す代わりに、ＲＴｘ、ＤＡＲＱ、及びＦＴｘの固定された順序を用いて、該当するフローに関するメトリック計算の際に用いられるタイムスタンプを決定するための第１の空でない待ち行列を見つけ出す。該フローの待ち行列は、ＲＴｘ、ＤＡＲＱ、及びＦＴｘの順序で対応することもできる。
【０２０９】
一実施形態においては、新たな送信に関してＦＬが利用可能になるごとに図１０において示されているようなスケジューリングが行われる。幾つかの特定の実装は、利用不能なスロットを含むすべてのスロットに関する計算の一部又は全部を行えることに注目すること。この理由は、新たな送信のためにＦＬが利用可能であることをアクセスネットワークが決定するまでには、送信インスタンスを決定するためにスケジューリング方法に関わる計算を行うために残されている時間が通常は多くないためである。
【０２１０】
図１０に示されているスケジューラ方法は、４つの基本ステップ、すなわち、１）一組の候補送信インスタンスの生成、２）該組内における１つの候補の選択、３）パッキング効率最大化、及び４）事前計算又はＰＡＣＫ計算を含む。ＰＡＣＫ計算は、ＡＴがパケットを成功裡に復号している確率を決定する。
【０２１１】
再度図１０を参照し、ステップ５０４において、スケジューラは、候補送信インスタンスリストを生成する。各々の利用可能なユーザーに対応する単一ユーザーフォーマットを有する候補単一ユーザー送信インスタンスであり、利用可能ユーザーは、現在何らかの理由でプロトコルサブタイプによって対応が禁止されていないユーザーである。さらに、該ユーザーからの受信ＤＲＣは、ＮＵＬＬ以外になる。ＮＵＬＬである場合は、該ユーザーは、１つ以上の送信フォーマットがＮＵＬＬ  ＤＲＣに基づいて提供されることを許容するＭＡＸ層プロトコルについて交渉済みであることになる。ＮＵＬＬ  ＤＲＣが受信されているユーザーに関する候補送信インスタンスが生成される場合は、該候補インスタンスは、有限のDelayBoundを有するフローに属するデータを搬送することだけしか許容されずさらに該フローのＦＴｘ待ち行列のみからデータを搬送することが許容される。該候補インスタンスの送信フォーマットは、表１において詳述されるように、前記ユーザーのＤＲＣに対応する基準フォーマットである。
【０２１２】
５つの多ユーザー送信フォーマット（１０２４，４，２５６）、（２０４８，４，１２８）、（３０７２，２，６４）、（４０９６，２，６４）、及び（５１２０，２，６４）の各々に関して候補多ユーザー送信インスタンスが生成される。１５３．６Ｋｂｐｓ以上を要求しているユーザーは、多ユーザーフォーマットで対応される。さらに、ユーザーのＤＲＣは、候補送信インスタンスのフォーマットと適合可能でなければならない。さらに、多ユーザー候補送信インスタンスは、次の条件のうちの１つ又は両方を満たすことになる。条件を満たしていない場合は、さらなる考慮対象から外される。これらの条件は、２人以上のユーザーのデータを搬送するか、又はＤＲＣが消去された少なくとも１人のユーザーのデータを搬送することである。
【０２１３】
１つ以上のフローからのビットを埋め込むことによって、いずれかのグループ内の候補送信インスタンスが生成される。この場合、１）単一ユーザーフォーマットは、同じユーザーのフローからのビットしか生みこむことができない、２）多ユーザーフォーマットは、適合可能なＤＲＣを有するユーザーのフローからのビットが埋め込まれる。
【０２１４】
ビットスタッフィングは、ビットスタッフィングメトリックの降順で行われる。上述されるように、計算上の要求に従い、１つのフロー当たり１つのビットスタッフィングメトリックが計算され、次に、該フローの待ち行列内において現在送信待ち中のオクテットに関して使用される。この場合は、ビットスタッフィングメトリックは、最初にいずれのフローに対応するかを決定するのに役立つ。しかしながら、ある所定のフローのオクテットがどのように対応されるかは決定しない。この場合は、フローの待ち行列内において送信待ち状態であるオクテットは、タイプスタンプの順序で現れ、フローのオクテットは、待ち行列内において現れる順序で対応されると想定している。この想定は、ＦＴｘ待ち行列に関して使用され、ＲＴｘ／ＤＡＲＱ待ち行列に関しては必ずしも使用されない。
【０２１５】
上述されるように、各フローは、複数の待ち行列、すなわち、第１回目の送信データ（ＦＴｘ）に関して１つの待ち行列、及び再送信のためのその他の待ち行列（ＲＬＰ再送信に関するＲＴｘ待ち行列及び／又はＭＡＣ層再送信に関するＤＡＲＱ待ち行列）を有することができる。フローが空でないＲＴｘ及び／又はＤＡＲＱ待ち行列を有する場合は、該フローに関するビットスタッフィングメトリックは、これらの空でないＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列における待ち行列先頭タイムスタンプのうちの最も古いタイムスタンプに基づいて計算される。１つのフローの待ち行列に関して１つのビットスタッフィングメトリックのみが計算される。ある所定のフローからのビットスタッフィングは、ＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列間における待ち行列先頭タイムスタンプの昇順に基づいても行われるべきである。
【０２１６】
タイムスタンプに基づいたフローの待ち行列の順序設定は、ＲＴｘ／ＤＡＲＱ／ＦＴｘ待ち行列の固定された順序として概算することができる。
【０２１７】
候補送信インスタンスを生成する際には、非基準単一ユーザーフォーマット及び１０２４未満のビットを搬送する短い多ユーザーフォーマットは考慮されない。これらのフォーマットは、パッキング効率最大化ステップにおいて考慮される。スケジューリング方法は、複雑さを低減させること及び１つのパケット当たり可能なかぎり多くのデータをパッキングすることを追求する。
【０２１８】
短いパケットに効率的に充填することによって、弱いチャネル状態を有するが送信のためのデータを大量に有するユーザーが相対的優先度を得る状況を回避する。この段階において非基準パケット及び短いパケットを考慮しないことによる他の利益は、限定することなしに、フレームに基づくスケジューリングにおいて発生する可能性がある幾つかの量子化上の影響を回避することを含む。
【０２１９】
多ユーザー候補を生成する際には、後述される継続問題が及ぼす可能性がある悪影響を軽減するためのさらなる予防措置を講じることが可能である。１つの該方法は、第１の多ユーザーパケットの開始後の（例えば所定のインターレースにおいてカウントした）ある一定数のスロットに関して、前に開始されて終了されている多ユーザーパケットを有する同じインターレース上において多ユーザーパケットに対応するのを避けることである。このスロット数は、２つの多ユーザーパケットのスパンのうちの最小スパンに設定すること又は第１の多ユーザーパケットのスパンに設定することが可能である。このアプローチ法は、ユーザーが新たな多ユーザーパケットにおいて対応される資格を素早く得ることを可能にし、資格がない状態が長時間続くのを回避するのに役立つ。
【０２２０】
ステップ５０８に関して、単一ユーザー候補送信インスタンス及び多ユーザー候補送信インスタンスのリストを生成後、スケジューラは、（上記の生成されたリストが少なくとも１つの候補送信インスタンスを含むと想定して）これらの候補のうちの少なくとも１つを選択する。この選択は、リスト内の候補の各々に関するパケットメトリックを計算し、最大のパケットメトリックを有する候補を送信対象として選択することによって行われる。同点の場合は、多ユーザーフォーマットよりも単一ユーザーフォーマットを優先することが望ましい。さらに、低速の多ユーザーフォーマットよりも高速の多ユーザーフォーマットを優先することが望ましい。
【０２２１】
ステップ５１０において、送信対象として選択された候補送信インスタンスの送信フォーマットが再検討され、該候補送信インスタンスによって搬送するために選択されたデータオクテットの組を変更せずにパッキング効率を最大化するように変更することができる。ステップ５１０の完了は、ＡＲＱ利得を提供することができる。
【０２２２】
送信対象として選択された送信インスタンスが単一ユーザーフォーマットである場合は、該フォーマットは、選択されたデータオクテットを搬送することができる対応されたユーザーのＤＲＣと適合可能な最低速度の非基準単一ユーザーフォーマットに変換することができる。その他の実施形態は、単一ユーザー送信インスタンスのフォーマットを多ユーザーフォーマットに変換することもできる。
【０２２３】
ＡＴ内部の適応型速度制御機構は、単一ユーザーパケットをサポートするように適合される可能性が高い。多くのＤＲＣは、より小さいペイロードサイズを有する非基準単一ユーザーフォーマットと適合可能である。従って、ＡＲＱ利得を達成させるために単一ユーザー候補を多ユーザーフォーマットに変換するのは望ましくない。
【０２２４】
多ユーザーフォーマットは、（ペイロードが適合するかぎりにおいて）いずれかのより低速の多ユーザーフォーマットに変換することができるが、後述される継続問題によって悪影響を受ける可能性があるため、このような広範なフォーマット変換は回避するのが望ましい。
【０２２５】
図１２に関して、スケジューラは、選択された送信インスタンスにおいて対応されるユーザーからのＡＣＫを検出できなくても該送信インスタンスを送信する際の上限となる最大スロット数（例えば、該送信インスタンスの公称スパンよりも小さい数）を決定することができる。このステップは任意であるため、アクセスネットワークがパケット内において対応されているユーザーからＡＣＫを検出後に又はパケットの全スパンを送信後にパケット送信を終了させるようにするために実行不能にすることが可能である。
【０２２６】
このステップを実装する一方法は、送信インスタンスの最大スロット数を次式のように設定することである。
【数１２】
2007536827.tif 000016
【０２２７】
ここで、ScheduledTxFormatSpanは、スケジューリングされた送信フォーマットのスパンであり、DRCSpan[i]は、パケット内のｉ番目の対応されたユーザーからの復号されたＤＲＣに対応する基準送信フォーマットのスパンである。
【０２２８】
スケジューラによって利用される変数のうちの幾つかが上記において説明済みである。ここでは、ＤＳＰ−ドライバインタフェースにおいてスケジューラに提供される変数が示される。グローバル変数は、全フローに対して適用される変数である。フロー変数は、各フローに関して別々に指定される変数である。
【０２２９】
１．グローバル変数
ａ．FlowTPutFilterTimeConst−各フローに関して保持される平均スループットAvgThroughput変数を生成するために用いられる1次ＩＩＲフィルタの時定数を定義する。該フィルタは、スロット当たり１回繰り返される。該フィルタへの入力は、該スロットにおいて開始するパケット内の所定のフローの待ち行列から提供されるオクテット数である。該フィルタは、新たなパケット送信が開始しないスロットにおいてゼロを入力することによって更新される。
【０２３０】
ｂ．Thrghpt2DelayConvFactorBM−ビットメトリックの計算を目的として、スループットの影響を受けやすいメトリックから遅延による影響を受けやすいメトリックに変換するための変換率。
【０２３１】
ｃ．Thrghpt2DelayConvFactorBSM−ビットスタッフィングメトリックの計算を目的として、スループットの影響を受けやすいメトリックから遅延による影響を受けやすいメトリックに変換するための変換率。
【０２３２】
ｄ．FlowClass−フローがスループットの影響を受けやすい型か遅延の影響を受けやすい型かを示す。
【０２３３】
ｅ．FlowEligibleForDRCErasureMapping−ＤＲＣ消去マッピングアルゴリズムによって使用。
【０２３４】
ｆ．ErasureMapDelayThreshold−ＤＲＣ消去マッピングアルゴリズムによって使用。
【０２３５】
２．フロー変数
ａ．UserId, FlowId−各フローの所有者をインデキシング及び決定する手段を提供する。
【０２３６】
ｂ．QoSMetricState, PriorityThold[2]−ビット（スタッフィング）メトリックの優先状態を現在の遅延の関数として表す。PriorityThold[ ]アレイの要素は、変数DelayThold及びQoSMetricStateを含む構造物である。フローのCurrentDelayがPriorityThold[0].DelayTholdよりも小さい場合は、優先状態はQoSMetricStateに設定される。CurrentDelayがPriorityThold[0].DelayTholdよりも大きいが、PriorityThold[1].DelayTholdよりも小さい場合は、優先状態はPriorityThold[0].QoSMetricStateに設定される。CurrentDelayがPriorityThold[1].DelayTholdよりも大きい場合は、優先状態は、PriorityThold[1].QoSMetricStateに設定される。QoSMetricStateの変数は、｛ＭＣ０，．．．，ＭＣ７｝の優先状態に応じた値｛０，．．．，７｝をそれぞれとる。
【０２３７】
ｃ．AccelerationFactor
ｄ．AccelerationOffset
ｅ．DelayBound−0は無限を表し（すなわち、オクテットに対応する前に該オクテットを絶対に廃棄しない）、０以外の場合は、所定のオクテットのタイムスタンプに関する遅延量であって経過後に該オクテットが待ち行列から廃棄される遅延量を表す。
【０２３８】
ｆ．TargetThroughput−スループットの影響を受けやすいフローのビット（スタッフィング）メトリックにおいて用いられる変数。
【０２３９】
ｇ．FlowAggregateIndex−FlowAggregateIndexが０に設定されたフローは、スケジューラによって統合されない。FlowAggregateIndexが０に設定されていない場合は、FlowAggregateIndexの値が同じである（ゼロ以外）フローがスケジューラにおいて統合される。FlowAggregateIndexの適用範囲は１人のユーザーに限定されている。すなわち、同じインデックスを混乱なしに他のユーザーのフローに関して再使用することができる。
【０２４０】
ｈ．IntraFlowPriority−（スケジューラによって）統合されたフロー内の構成フローは、IntraFlowPriorityの順序で対応される。同じIntraFlowPriorityを有する構成フローの場合は、該構成フローのタイムスタンプによって順序が決定される。
【０２４１】
ｉ．GoSFactor−複数のレベルのサービス等級をフロー間で提供するために使用される。
【０２４２】
ｊ．DSBitMetricValue−ＭＣＸにおいて優先状態内にあるビットメトリック係数の値
ＤＳＰ−ドライバインタフェースにおいては、フローは、ＢＥ、ＡＦ、又はＥＦとして指定されず、さらにその他のいずれの高レベル記述子によっても指定されない。ＤＳＰ−ドライバインタフェースは、すべてのフローに関して一定の低レベル記述子を使用する。ＢＳＣ等のより高いレベルにおいては、ＱｏＳ要求及びＢＥ／ＥＦ／ＡＦ分類等の特定の高レベルフロー記述子が、各フローに関してＤＳＰ−ドライバインタフェース内において定義された基本変数にマッピングされる。これらのマッピングテーブルは、考えられるフロー型に関して、十分なシミュレーション及び試験によって生成される。
【０２４３】
下記は、様々な変数の使用例である。ＢＥフローに関しては以下の変数が使用される。
【数１３】
2007536827.tif 000017
【０２４４】
ＡＦフローに関しては、以下の変数を使用することができる。
【数１４】
2007536827.tif 000018
【０２４５】
ＥＦフローに関しては、以下の変数を使用することができる。
【数１５】
2007536827.tif 000019
【０２４６】
シグナリングフローは以下のように提供される。
【数１６】
2007536827.tif 000020
【０２４７】
ＢＥ／ＡＦフローは、以下の変数の適切な組合せを用いて優先順位を設定することができる。
【０２４８】
１．MC0,…,MC7状態  厳しい優先順位の設定を許容する
２．穏やかな優先順位設定に関するGoSFactor
３．典型的には、何らかの最低限のスループットを要求するＡＦフローに関するTargetThroughput
ＥＦフローは、以下の変数の適切な組合せを用いて優先順位をさらに設定することができる。
【０２４９】
１．MC0,…MC7状態  厳しい優先順位の設定を許容する
２．AccelerationOffsetは、同じ優先状態のオクテット間におけるビットスタッフィング中に優先順位設定を行うが、（最終的なパケット選択ステップは、パケットメトリックを計算するためにビットメトリックを使用し、AccelerationOffsetには依存しないため）最終的なパケット選択には直接的な影響を与えない。同じユーザー又は２人の異なるユーザーに属する２つのフローが同じ候補送信インスタンス内に含まれるために競合中である場合は、より大きいAccelerationOffsetを有するフローが優先される。
【０２５０】
３．DSBitMetricValueはビットメトリックに対して影響を与えるため、パケットメトリックに対して直接的な影響を有する。この変数は、穏やかな優先順位設定に関しても使用することができる。現在は、この変数は実装されない。
【０２５１】
ＤＳＰ−ドライバインタフェースは、スケジューラにおける柔軟なフロー統合方法を提供する。スケジューラによって行われる統合は、ＢＳＣによって行うことができる統合とは異なることに注意すること。ＢＳＣが一組のフローを統合時には、この統合フローは、スケジューラにとっては単一のフローのようにみえ、スケジューラは、該フローに関して単一の組の変数を受け取る。スケジューラは、構成フローを区別することができない。スケジューラにおいて統合が行われるときに、当然のことながらスケジューラはすべての構成フローを知ることになる。
【０２５２】
AvgThroughput変数は、統合フローの総スループットを含む。統合フローの構成フローに関して指定されたDelayBound等の一定の変数は、ＤＳＰ−ドライバインタフェースにおいて同じ値に設定される。すべての構成フローに関して等しく設定すべき変数は以下のとおりである。
【０２５３】
ａ．UserID
ｂ．AggregateIndex
ｃ．QoSMetricState
ｄ．PriorityThold[2]
ｅ．AccelerationFactor
ｆ．AcclerationOffset
ｇ．DelayBound
ｈ．TargetThroughput
ｉ．GoSFactor
ｊ．DSBitMetricValue
異なった設定が可能な変数はIntraFlowPriorityであり、異なった設定をしなければならないパラメータはFlowIDである。 
一実施形態においては、統合フローは、単一のビット（スタッフィング）メトリックが割り当てられる。このメトリックは、統合フローの構成フロー間において最も古いタイムスタンプに基づく。構成フローのタイムスタンプは、ＦＴｘ／ＲＴｘ／ＤＡＲＱ待ち行列の待ち行列先頭タイムスタンプに基づいて計算される。しかしながら、ビットスタッフィングのためにフローを選択時には、構成フローが対応される順序は、第１に、これらの構成フローの各々に対して割り当てられたIntraFlowPriority変数によって決定され、第２に、これらの構成フローのタイムスタンプによって決定される。IntraFlowPriority変数を同じ値に設定することによって、構成フローの選択順序は、厳格にこれらの構成フローのタイムスタンプに基づいて設定することができる。IntraFlowPriority変数は、ほとんどの場合はＢＥフローが対象になっている。
【０２５４】
上述されているように、各フローは、ＦＴｘ待ち行列を有しており、さらにＲＴｘ及び／又はＤＡＲＱ待ち行列を有することができる。ソフトウェア実装においては、単一のビットスタッフィングメトリックが各フローに関して計算される。このメトリックは、ＦＴｘ待ち行列内のオクテット、及びＲＴｘ待ち行列とＤＡＲＱ待ち行列内のオクテットに対して適用される。対応すべきフローが選択された場合は、個々の待ち行列も決定された順序で対応される。
【０２５５】
一ソフトウェア実施形態は、ＲＴｘ及び／又はＤＡＲＱ待ち行列が空でない場合にフローの優先度を上げる能力を提供する。この提供は、式（３．３−２）において与えられるMetricTS値を単に以下のように修正することによって達成される。
【数１７】
2007536827.tif 000021
【０２５６】
係数RetransmissionPriorityFactorは、ＲＴｘ及びＤＡＲＱの両待ち行列が空の場合は１の値をとる。該係数は、ＲＴｘ待ち行列は空であるがＤＡＲＱ待ち行列にはデータが入っている場合は他の値をとる。ＲＴｘが空でない場合はさらに他の値をとる。
【０２５７】
１ｘＥＶ−ＤＯ仕様の改訂Ａにおいては、幾つかのプロトコルサブタイプが、一組の単一ユーザー及び多ユーザー送信フォーマットと適合可能であるべきＮＵＬＬ  ＤＲＣを定義する。さらに、該仕様のＲｅｌ−０においては、ＮＵＬＬ  ＤＲＣが（１０２４，１６，１０２４）単一ユーザー送信フォーマットで受け取られたユーザーにアクセスネットワークが対応するのを可能にする一定のプロトコルサブタイプに関するコンフィギュレーション属性が定義されている。
【０２５８】
いずれの場合においても、スケジューラは、ＮＵＬＬ  ＤＲＣが受信されたユーザーに関するデータを含む候補送信インスタンスを生成することができる。この生成は、ＮＵＬＬ−速度変換と呼ばれる。スケジューラは、ＮＵＬＬ−速度変換に対して次の制限を課す。
【０２５９】
ａ．有限のDelayBoundを有するフローに対応することを許容する
ｂ．RTx/DARQ待ち行列には対応できない
上記の制限以外には、スケジューラは、ユーザーからの受信ＤＲＣが、改訂Ａ内の一定のプロトコルサブタイプ内の同じ送信フォーマットと適合可能であると定義されている０ｘ０（すなわち、ＮＵＬＬ  ＤＲＣ）、又は０ｘ１(すなわち、３８．４Ｋｂｐｓ)であったかどうか区別しない。特定のプロトコルサブタイプに関する定義については同じく表１を参照すること。
【０２６０】
ＮＵＬＬ  ＤＲＣがユーザーから受け取られたときには、提供されたパケットが該ユーザーによって成功裡に復号される保証はない。今後の改良は、ＮＵＬＬ  ＤＲＣを送っていてパケット内において対応されたユーザーが実際に合理的な範囲で成功裡に復号中であるかどうかを実際にモニタリングすることを含めることができる。成功統計数字に依存して、該当するフローに関する変換を開始／終了させることができる。一実施形態は、ＮＵＬＬ  ＤＲＣを送信したユーザーに関して生成された候補送信インスタンスの順位を、０ｘ１のＤＲＣを送信したユーザーに関して作成された候補送信インスタンスよりも低く設定する。
【０２６１】
ソフトウェア実装においては、スループットの影響を受けやすいフローに関するデータを含む候補多ユーザーインスタンスの生成を容易にするためにいくつかの合理的な概算を行うことができる。
【０２６２】
スケジューラのタイミングに関して、スロット内のタイムラインが次の２つの部分に分割される。すなわち、第１の部分は、非重要セグメントであり、第２の部分は、重要セグメントである。ユーザーのＤＲＣ値は、重要セグメント中に入手可能になる。しかしながら、重要セグメントは、最悪時負荷状態下にあるスケジューラに関わる計算を行う上で十分なプロセッササイクルを提供することができない。従って、これらの計算の一部は、非重要セグメントに移譲される。幾つかのユーザーのＤＲＣ値は、非重要セグメント中には知ることができないため、ソフトウェア実装は、前スロットのＤＲＣ値を用いて候補送信インタフェースを構築しさらに送信対象となる候補送信インスタンスを選択する。幾つかのユーザーのＤＲＣ値は変更可能であり、送信対象として選択された候補送信インスタンスは、重要セグメント中に無効になる可能性がある。この問題を克服するために、非重要セグメント中に２つ以上の強力な候補が選択される。実際のＤＲＣ値が重要セグメントにおいて受信された時点で、この縮小された組の候補の再評価が行われる。縮小された候補インスタンスの組は、下記を含むことができる。
【０２６３】
ａ．少数（例えば５つ）の単一ユーザー候補
ｂ．１つの多ユーザー候補（生成された場合）、及び、該候補内において対応されたユーザーのうちの一部が適合不能になった場合に該候補内において対応することができるいくつかの予備ユーザー
１ｘＥＶ−ＤＯ  Ｒｅｌ−０においては、ＡＮは、ＤＲＣ情報を消去時にはＡＴへのパケットのスケジューリングを行わない。ＡＮが遅延の影響を受けないアプリケーション、例えばベストエフォートトラフィック、を有する複数のＡＴに対応中であるときには、相対的に大きなＤＲＣ消去率をシステム容量を失うことなしに許容することができる（例えば、多ユーザーダイバーシティに起因するとき）。ＤＲＣ消去率が過度に高いときには、ＤＲＣロックビットがＡＮによってゼロに設定され、これで、ＡＴは、他のセクターにハンドオフすること又は固定速度モードに切り換わることを選択できる。しかしながら、ＤＲＣロックビット生成方法は、不必要なハンドオフを防止するために、少なくともフィルタリングに部分的に起因する固有の遅延を有する。従って、逆方向リンクでは相対的に長時間のＤＲＣ消去が発生する可能性がある。ＥＦトラフィック等の遅延の影響を受けやすいアプリケーションにとっては、これらの消去は、受入不能な長さのサービス停止を発生させる可能性がある。ＤＲＣ消去マッピングアルゴリズムは、ＦＬでのサービス停止を最小にすることを追求する。
【０２６４】
基準アルゴリズムは次の２つのステップで説明される。第１のステップは、ＤＲＣ消去マッピングに関する決定について説明する。第２のステップは、１ｘＥＶ−ＤＯ改訂ＡのＦＬスケジューラの変更を説明する。図１４は、可変速度モードにある各ＡＴに関するタイムスロット間隔ごとにＡＴによって実行されるＤＲＣ消去マッピングアルゴリズムを示した図である。各ＡＴに関して、該アルゴリズムは、該ユーザーに関してＢＳＣによって設定されるアクティブな待ち行列を有するセルの各セクターにおいて実行される。説明を単純化するため、該アルゴリズムは、各スロット間隔において実行されることが説明されるが、変数は、DRC_Length間隔ごとにしか更新されない。
【０２６５】
該アルゴリズムの主出力は、ＤＲＣ消去マッピングが行われること及び限定されたＦＬスケジューリングをＡＴに関して行えることをスケジューラに示すErasure_Mapped_flagである。
【０２６６】
DRC_index_storeは、最新の有効な、すなわち成功裡に復号されたＤＲＣインデックスを格納するために使用される。Eras_Countは、ＤＲＣ消去の実行長さを計算するために使用される。ＤＲＣ消去マッピングは、消去実行長さがMax_Ers_Lenよりも長い場合のみに行われる。このしきい値は、サービス停止確率が相対的に高いときのみにＤＲＣ消去マッピングが行われるようにする。しかしながら、パケットは、対応するＦＬパケット遅延が長いときにＡＴに対してスケジューリングすることができる。従って、Max_Ers_Lenは過度に大きくなることができない。ＥＦフロー、例えばＶｏＩＰに関しては、Max_Ers_Lenに関する合理的な設定値は、０乃至１６スロットの範囲内にすることができる。
【０２６７】
図１４に示されるように、方法７００は、判断ボックス７０２においてＤＲＣが消去されるかどうかを最初に確認する。ＤＲＣが消去される場合は、ステップ７０４においてEras_Cntが増加される。次に、ステップ７０６においてEras_Cntが最大値Max_Ers_Lenと比較される。Eras_CntがMax_Ers_Lenよりも大きい場合は、Erasure_Mapped_flagが１に設定される。その他の場合は、ステップ７１２においてErasure_Mapped_flagがクリアされる、すなわち０に設定される。ＤＲＣが判断ボックス７０２において消去されない場合は、ステップ７０８において、Erasure_Mapped_flagが０に設定され、Eras_Cntが０に設定され、さらにDRC_Index_StoreがDRC_Indexに設定される。処理はステップ７１２に進み、ステップ７１２においてErasure_Mapped_flagが０に設定される。
【０２６８】
上述されているＦＬスケジューラは、ＤＲＣ消去マッピングアルゴリズムとともに動作するように変更することができる。各ＡＴの各個別のデータフローに関して、フローは、下記の条件を満たしている場合に限定的ＦＬスケジューリングの資格を有する。
【０２６９】
(ErasureMappedFlag == 1 && FlowEligibleForDRCErasMapping == 1 && HeadofQueueDelay ≧ ErasureMapDelayThreshold)
ここで、FlowEligibleForDRCErasMappingは、各トラフィックフローがＤＲＣ消去マッピングに関する資格を有することを示す変数である。デフォルトとして、ＥＦフローはマッピングの資格を有ると想定され、ＢＥフロー及びＡＦフローは資格を有さない。
【０２７０】
HeadofQueueDelayは、ＦＬ待ち行列の先頭のパケット（すなわち、ＦＴｘ、ＲＴｘ又はＤＡＲＱ待ち行列内の最も古いパケット）に関する"Current_Delay"を示す。ErasureMapDelayThresholdは、消去マッピングに関する特定のフローについて要求される最低遅延である（"PriorityThold[i].DelayHold"とほぼ同じ効果を有する）。フローが限定的ＦＬスケジューリングの資格を有する場合は、下記の修正がＦＬスケジューラにおいて行われる。
【０２７１】
ａ．フローは、単一ユーザー送信インスタンスに関する候補としての資格は有さない
ｂ．フローは、要求されたＤＲＣインデックスDRC_index_mappedを有する多ユーザー送信インスタンスに関する資格を有する
DRC_index_mappedを消去長さの関数として動的に変更することが可能である。この動的変更は、DRC_index_store及びEras_Countを用いて達成させることができる。DRC_indexに関するデフォルト設定値は、０ｘ３にマッピングすることができる。ＦＬスケジューラに関しては、DRCインデックス０ｘ３は、多ユーザー送信フォーマット（１０２４，４，２５６）に対応し、該フォーマットは、フォーマット（｛１２８，２５６，５１２｝，４，２５６）に変換可能である。これらの多ユーザーフォーマットはすべて、全ＤＲＣインデックスと適合可能であり、このため、ＡＴは、（実際の要求されたＤＲＣインデックスと無関係な）十分なＳＩＮＲを有するかぎりマッピングされたＤＲＣを復号可能なはずである。代替アルゴリズムは、Eras_Countが増加するのに応じて、利用可能な多ユーザー送信フォーマットをより低いデータ速度に制限するより控え目な値を適用することができる。
【０２７２】
ＤＡＲＱオプションはＶｏＩＰに関して使用可能にできることに注目すること。従って、ＡＴが送信された多ユーザーパケットを第１の送信試みにおいて復号していない場合は、ＤＡＲＱは、第２の送信試みを可能にし、残留パケット誤り率を引き下げる。しかしながら、ＤＡＲＱ性能は、ＤＲＣが消去中であるときには信頼性がそれほど高くないＡＣＫチャネル性能と結び付けられている。ＡＣＫ／ＮＡＫ判断しきい値は、おそらくＤＲＣインデックス又はＤＲＣマッピング状態に依存してＤＡＲＱに関して最適化することができる。他の実施形態は、ＤＲＣ消去マッピングの場合はより低速の多ユーザーパケットフォーマット、例えば（５１２，４，１０２４）)、又は（２５６，４，１０２４）のみと適合能なＤＡＲＱ送信試みを行う。
【０２７３】
代替実施形態は、本明細書において示されているスケジューラに対して追加のステップ及び手段を提供することができる。例えば、ＢＥ／ＡＦフローは、典型的には、厳密により低い優先度を有する優先状態を利用する。その結果、より高い優先状態を使用する可能性が非常に高いＥＦユーザーが存在する中でＢＥ／ＡＦスループットの等級を下げることができる。ＢＥ／ＡＦスループットは、一定の条件の下でＢＥ／ＡＦフローの優先度をより高い状態に上げることによって向上させることができる。
【０２７４】
一実施形態によれば、AvgRequestedRateは、ユーザーのフィルタリングされた要求速度であり、Ｋのユーザーがシステム内におけるＢＥのユーザーとしてコンフィギュレーションされる。ＢＥフローに関するユーザーのスループットAvgThroughputが次式を満たしている場合は、
【数１８】
2007536827.tif 000022
【０２７５】
ＢＥフローに関する該ユーザーの優先状態をより高い優先状態に上昇させることができる。αの値は、システムのＥＦ負荷に依存して選択することができ、負荷が高いほどαが小さい。さらに、該上昇に関して、要求速度に関する最低要求をユーザーに対して課すことができる。その他のＢＥ／ＡＦ容量増大方法も可能である。
【０２７６】
上記の方法は、フローのビット（スタッフィング）メトリックの優先度状態は待ち行列先頭の遅延の関数であるだけでなく、該フローのスループットの関数でもあることができることを示している。
【０２７７】
遅延の影響を受けやすい状態においては、ビットスタッフィングメトリックは、厳密に遅延の関数であり、ユーザーのローカルチャネルピークを利用する機構を有さないことに注目すること。ここでは、遅延の影響を受けやすい状態にあるビットスタッフィングメトリック値は、次式のように修正することができる。
【０２７８】
MBSDS = AccelerationFactor*[CurrentDelay + kCCI] + AccelerationOffset
ここで、チャネル状態インジケータ（ＣＣＩ）は、別々に生成することができる組｛０，１｝からの値又は間隔［０，１］をとり、このため、より高い値をとるときには、ユーザーの長期的なチャネル状態と比較して相対的に良好なチャネル状態を示す。さらに、ｋは、ＣＣＩ−遅延変換率である。ｋは、ユーザーのチャネル状態が自己のチャネル統計数字に関して良好であるときにフローが遅延の点でどれだけ向上されるかを示す。
【０２７９】
2進｛０，１｝の場合に関してＣＣＩを生成する１つの単純な方法が次に示される。RateIndexを速度昇順でＤＲＣ値に割り当てられた整数とする。ここで、ＤＲＣ値は、データ速度とともに単調に増加しないため使用されない。AvgRateIndexを、ユーザーの平均（フィルタリングされた）RateIndexとする。CCIThresholdを、１．２等の変数とする。これで、RateIndex >  CCIThreshold*AvgRateIndexである場合は、ＣＣＩの値は１に設定することができる。その他の場合は、ゼロに設定される。この例においては、ＣＣＩは、受信されたＤＲＣに対応する現在のRateIndexが平均品質よりも１２０％以上高い場合は相対的に良好なチャネル状態であることを示す。
【０２８０】
プリエンプション（先取り）は、ＦＬ送信が行先ユーザーによって復号される前に打ち切ることを意味する。プリエンプションは、ＦＬにおける４つのすべてのインターレースが相対的に低速のユーザーによって占められている間に優先度が非常に高いデータが現れた場合に使用することができる。スケジューラアルゴリズムは、現在は、進行中の送信をプリエンプションする方法を提供しない。この場合の１つの理由は、制御されないプリエンプションは、慎重にモニタリングしないかぎり容量損失に至る可能性があるためである。
【０２８１】
本明細書において講じられるアプローチ法は、プリエンプションを要求する可能性がある状況を回避することである。１つの状態は、上記のように４つのすべてのインターレースが低速ユーザーによって占められている状態である。この状態を回避するために単純な方法を利用することができる。１つの該方法は、１６スロットスパン及び１８スロットスパンを有するフォーマットの同時送信が定められた数よりも行われないようにすることである。一例として、この数は、２又は３に設定することができる。
【０２８２】
一実施形態は、ＮＵＬＬ  ＤＲＣを送信しさらにパケット内において対応されるユーザーの復号性能をモニタリングする。これらのＮＵＬＬ−速度変換事例において測定されるＰＥＲに依存して、各ユーザーに関するＮＵＬＬ−速度変換を始動／停止させることが可能である。同様に、アクセス端末がこれらのパケットを十分に信頼できる形で復号中であることを収集された統計数字が示している場合は、ＲＴｘ／ＤＡＲＱ待ち行列及びＮＵＬＬ−速度インスタンス内に無限のDelayBoundを有するフローの待ち行列に対する制限を有効/無効にすることも可能である。
【０２８３】
スループットの影響を受けやすいフローに関するビット及びビットスタッフィングメトリック係数は、受信すべきデータを大量に有するユーザーが存在するＢＥ専用システムにおいて比例的公平性を提供する（例えば、全フローに関してTargetThroughput = 0及びGoSFactor = 1）。メトリック係数の形式は、同様の方法でその他のスケジューラに当てはめることができる。この場合においては、スループットの影響を受けやすいフローに関するメトリック係数は次式のように表すことができる。
【数１９】
2007536827.tif 000023
【０２８４】
ここで、f(.)及びh(.)は、総称関数であり、AvgRequestedRateは、ユーザーの平均要求速度である。f(x) = x及びh(x) = xに設定することは、ほぼ同等のＧｏＳスケジューラを提供する。
【０２８５】
１ｘＥＶ−ＤＯ仕様の改訂Ａにおいて定義される拡張型順方向トラフィックチャネルＭＡＣプロトコルは、以下において要約されるように、多ユーザーパケットに続いてユーザーに対応することに対して制約を課している。改訂Ａ仕様は、スロットｔは、下記の条件が満たされている場合は、その前のスロットｓの継続であると定義されると述べている。
【０２８６】
ｃ．アクセス端末が、スロットｓにおいて送信が開始するパケットの潜在的目標である。
【０２８７】
ｄ．スロットｔが、スロットｓと同じＦＬインターレース内にある。すなわち、t − s =  0 (mod 4)。
【０２８８】
ｅ. s < t < s + 4Nであり、Nは、スロットｓ中に有効であるＤＲＣ値に対応するＤＲＣインデックスのスパンを表す。
【０２８９】
ｆ．スロットｔの前において、アクセスネットワークが、スロットｓにおいて送信が開始したパケットに関する肯定応答を受信してない。
【０２９０】
アクセス端末が、スロットｓにおいて開始するセクターによって送信されたパケットの潜在的目標である場合は、アクセスネットワークは、スロットｓの継続であるスロットｔにおいて同じＦＬデータ源をアクセス端末に送信してはならない。
【０２９１】
上記の制限は、多ユーザーパケットに続いて対応することができるユーザーに関する制約を課すことになる。一例として、アクセスネットワークがその時点において早期に終了する一組のユーザーに多ユーザーパケットを提供する場合は、アクセスネットワークは、該提供されたパケットの継続中には、前パケットにおいて対応されなかったがそのフォーマットと適合可能であったユーザーに対してどのようなパケットも（単一ユーザーパケット及び多ユーザーパケット）提供することができない。一状況においては、アクセスネットワークが１５３．６Ｋｂｐｓの多ユーザーパケットを提供し、該パケットによって搬送されたデータを有するユーザーが４スロット未満で該パケットを復号する。アクセスネットワークが同じインターレースにおいて他の１５３．６Ｋｂｐｓ多ユーザーパケットをただちに提供する場合は、１５３．６Ｋｂｐ又は４スロットのスパンを有するＤＲＣを実際に要求したが前回のパケットにおいて対応されなかったユーザーは、新たな送信において対応することが許容されない。従って、新たな送信においては、４スロット未満のスパンを有するＤＲＣを要求したユーザー、典型的にはより良いチャネル状態にあるユーザーのみに対応することができる。しかしながら、この対応は、新たなパケットが早期に復号される可能性をさらに高くする。この連鎖は、基地局により近い位置に所在するユーザーの待ち行列が空になるまで続くことが可能である。他方、４スロットのスパンを有するＤＲＣを要求中の基地局からより遠いユーザーは対応されない。その結果、基地局からより遠いユーザーは過度の遅延状態になり、基地局により近いユーザーにとっては遅延上の小さい利得を得ることになる。
【０２９２】
上記の説明において提供される実施形態、側面及び例は、高速パケットデータプロトコルをサポートするシステムに関するものである。該システムは、提示される概念を明確化すること及び理解することを目的として示されている。代替システムは、本明細書において開示される適応型遅延管理及びスケジューリングのための方法及び手段を実装することができる。
【０２９３】
従って、通信システムにおける送信をスケジューリングするための斬新で改良された方法及び装置が説明されている。当業者は、上記の説明全体を通じて参照されることがあるデータ、命令、コマンド、情報、信号、ビット、シンボル、及びチップは、有利なことに、電圧、電流、電磁波、磁場、磁気粒子、光学場、光学粒子、又はそのあらゆる組合せによって表すことができることを理解するであろう。本明細書において開示されている実施形態に関連させて説明されている様々な例示的論理ブロック、モジュール、回路、及びアルゴリズム上のステップは、電子ハードウェアとして、コンピュータソフトウェアとして、又は両方の組合せとして実装できることを当業者はさらに理解するであろう。様々な例示的構成要素、ブロック、モジュール、回路、及びステップは、各々の機能の観点で一般的に説明されている。これらの機能がハードウェアとして又はソフトウェアとして実装されるかは、全体的システムに対する特定の用途上の及び設計上の制約事項に依存する。当業者は、これらの事情下においてハードウェアとソフトウェアを互換可能であること、及び説明されている機能を各々の特定の用途に合わせて実装する最良の方法を認識している。例として、本明細書において開示されている実施形態に関連させて説明されている様々な例示的な論理ブロック、モジュール、回路、及びアルゴリズム上のステップは、本明細書において説明されている機能を果たすように設計されたデジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、その他のプログラミング可能な論理デバイス、ディスクリートゲートロジック、ディスクリートトランジスタロジック、ディスクリートハードウェア構成品、例えばレジスタ及びＦＩＦＯ、一組のファームウェア命令を実行するプロセッサ、従来のあらゆるプログラミング可能なソフトウェアモジュール、及びプロセッサ、又はそのあらゆる組合せ、とともに実装又は実行することができる。プロセッサは、有利なことに、マイクロプロセッサであることができるが、代替として、該プロセッサは、従来のどのようなプロセッサ、コントローラ、マイクロコントローラ、プログラミング可能な論理デバイス、論理素子アレイ、又はステートマシンであってもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＲＰＯＭメモリ、ＥＥＲＰＯＭメモリ、レジスタ、ハードディスク、取り外し可能ディスク、ＣＤ−ＲＯＭ、又は当業において知られるその他のあらゆる形態の記憶媒体に常駐することが可能である。典型的プロセッサは、有利なことに、記憶媒体から情報を読み出すため及び記憶媒体に情報を書き込むために該記憶媒体に結合される。代替として、該記憶媒体は、プロセッサと一体化させることができる。該プロセッサ及び該記憶媒体は、ＡＳＩＣ内に常駐することができる。該ＡＳＩＣは、電話機又はその他のユーザー端末内に常駐することができる。代替として、該プロセッサ及び記憶媒体は、電話機又はその他のユーザー端末内に常駐することができる。該プロセッサは、ＤＳＰとマイクロプロセッサの組合せとして、又はＤＳＰコアと関係する２つのマイクロプロセッサとして実装することができ、さらにその他も可能である。
【０２９４】
本発明の好ましい実施形態が示されて説明されている。しかしながら、本発明の精神及び適用範囲を逸脱せずに数多くの変更を本明細書において開示される実施形態に対して行うことができることが当業者にとって明確になるであろう。従って、本発明は、下記の請求項による以外は限定されるものではない。
【図面の簡単な説明】
【０２９５】
【図１Ａ】無線通信システムを示した図である。
【図１Ｂ】高データ速度送信をサポートする無線通信システムを示した図である。
【図２】無線通信システムにおけるアクセスネットワーク（ＡＮ）のブロック図である。
【図３】無線通信システムにおける送信に関するスケジューリングアルゴリズムの流れ図である。
【図４】パケットデータスケジューラのカテゴリ分類を示した図である。
【図５】ユーザーからの受信データ要求に基づいてチャネル強度尺度を決定するためのフィードバックループを示した図である。
【図６】単一のトラフィック型を有する優先転送（ＥＦ）専用ユーザーが存在する状態でのスケジューラの動作を示した図である。
【図７】ペイロード多項式p(z)からの簡約ペイロード多項式c(z)の計算を示した図である。
【図８】一実施形態によるスケジューラを示した図である。
【図９】一実施形態による図８のスケジューラの一部分を示した図である。
【図１０】送信の適応型遅延管理を実装するためのスケジューリングアルゴリズムを示した図である。
【図１１】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１２】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１３】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１４】記載なし。
【図１Ａ】
2007536827.tif 000024
【図１Ｂ】
2007536827.tif 000025
【図２】
2007536827.tif 000026
【図３】
2007536827.tif 000027
【図４】
2007536827.tif 000028
【図５】
2007536827.tif 000029
【図６】
2007536827.tif 000030
【図７】
2007536827.tif 000031
【図８】
2007536827.tif 000032
【図９】
2007536827.tif 000033
【図１０】
2007536827.tif 000034
【図１１】
2007536827.tif 000035
【図１２】
2007536827.tif 000036
【図１３】
2007536827.tif 000037
【図１４】
2007536827.tif 000038
【手続補正書】
【提出日】平成19年1月30日(2007.1.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０２９５
【補正方法】変更
【補正の内容】
【０２９５】
【図１Ａ】無線通信システムを示した図である。
【図１Ｂ】高データ速度送信をサポートする無線通信システムを示した図である。
【図２】無線通信システムにおけるアクセスネットワーク（ＡＮ）のブロック図である。
【図３】無線通信システムにおける送信に関するスケジューリングアルゴリズムの流れ図である。
【図４】パケットデータスケジューラのカテゴリ分類を示した図である。
【図５】ユーザーからの受信データ要求に基づいてチャネル強度尺度を決定するためのフィードバックループを示した図である。
【図６】単一のトラフィック型を有する優先転送（ＥＦ）専用ユーザーが存在する状態でのスケジューラの動作を示した図である。
【図７】ペイロード多項式p(z)からの簡約ペイロード多項式c(z)の計算を示した図である。
【図８】一実施形態によるスケジューラを示した図である。
【図９】一実施形態による図８のスケジューラの一部分を示した図である。
【図１０】送信の適応型遅延管理を実装するためのスケジューリングアルゴリズムを示した図である。
【図１１】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１２】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１３】一実施形態による図１０のスケジューリングアルゴリズムの一部分を示した図である。
【図１４】可変速度モードにある各ＡＴに関するタイムスロット間隔ごとにＡＴによって実行されるＤＲＣ消去マッピングアルゴリズムを示す図である。
【国際調査報告】
2007536827.tif 000039
2007536827.tif 000040