(57)【特許請求の範囲】
【請求項１】
ある時間間隔の間のモバイル・ノードに対して、それより前の以前時間間隔の間の前記モバイル・ノードに関連する以前の第１の重みと、第１のビット・レートと前記モバイル・ノードのスループットの指標との差の一次関数である修正率との合計に等しい第１の重みを、アクセス・ノードが動作することによって、設定するステップと、
前記第１の重みに基づいて前記モバイル・ノードとの通信を、スケジューラが動作することによって、スケジューリングするステップと
を含む方法。
【請求項２】
前記モバイル・ノードとの前記通信を、前記スケジューラが動作することによって、スケジューリングするステップは、前記第１の重みとベストエフォート型スケジューリングに関連する重みとの大きい方を前記スケジューラが使用して、前記モバイル・ノードとの前記通信を、前記スケジューラが動作することによって、スケジューリングするステップを含む請求項１に記載の方法。
【請求項３】
前記モバイル・ノードの保証されたビット・レートと前記時間間隔の間の前記モバイル・ノードのスループットとの差の関数として前記修正率を前記スケジューラが決定するステップを含む請求項１に記載の方法。
【請求項４】
前記モバイル・ノードとの前記通信を前記スケジューラがスケジューリングするステップは、前記第１の重みと前記少なくとも１つのチャネルの品質の指標との両方に基づいて前記スケジューラが決定した優先度を前記スケジューラが使用して、少なくとも１つのチャネルを通じて前記モバイル・ノードとの通信を前記スケジューラがスケジューリングするステップを含む請求項１に記載の方法。
【請求項５】
前記第１のモバイル・ノードに対して前記第１の重みを前記アクセス・ノードが設定するステップは、複数のモバイル・ノードに対して複数の第１の重みを前記アクセス・ノードが設定するステップを含み、前記複数の第１の重みのそれぞれは、前記以前時間間隔の間の対応する以前の第１の重みと、第１のビット・レートと前記対応するモバイル・ノードのスループットの指標との差の一次関数である修正率との合計に等しい請求項１に記載の方法。
【請求項６】
前記モバイル・ノードの第１の部分に対して保証されたビット・レートを達成するために最小の帯域幅を前記スケジューラが割り当て、前記モバイル・ノードの第２の部分に残りの帯域幅を前記スケジューラが公平に割り当てる反復手順を前記スケジューラが使用して、前記複数のモバイル・ノードに対して前記複数の第１の重みを前記スケジューラが初期化するステップを含み、前記複数の第１の重みのそれぞれは、前記対応する割り当てられた帯域幅の関数である請求項５に記載の方法。
【請求項７】
前記第１の重みを設定するステップは、以前の第１の重みと、保証されたビット・レートと前記モバイル・ノードの前記スループットの前記指標との差の一次関数である修正率との合計に等しい前記第１の重みを前記アクセス・ノードが設定するステップを含み、
前記時間間隔の間に前記モバイル・ノードに対して、前記以前時間間隔の間に前記モバイル・ノードに関連する以前の第２の重みと、最大ビット・レートと前記モバイル・ノードの前記スループットの前記指標との差の一次関数である修正率との合計に等しい第２の重みを前記アクセス・ノードが設定するステップと、
前記第２の重みと、前記第１の重みと前記ベストエフォート型スケジューリングに関連する前記重みとの大きい方との小さい方に等しい最終的な重みに基づいて前記モバイル・ノードとの通信を前記スケジューラがスケジューリングするステップと、
前記モバイル・ノードのそれぞれに対して、保証されたビット・レートまたは最大ビット・レートの少なくとも１つによって課せられる制約を受ける前記モバイル・ノードのそれぞれに帯域幅を前記スケジューラが割り当てる反復手順を前記スケジューラが使用して、複数のモバイル・ノードに対して複数の最終的な重みを前記スケジューラが初期化するステップであって、前記複数の最終的な重みのそれぞれは、前記対応する割り当てられた帯域幅の関数であるステップと
をさらに含む請求項５に記載の方法。
【請求項８】
第１の重みの以前の値と、第１のビット・レートとモバイル・ノードのスループットの指標との差の一次関数を前記アクセス・ノードが使用して、前記モバイル・ノードに関連する前記第１の重みを前記アクセス・ノードが再帰的に規定するステップと、
前記第１の重みに基づいて前記モバイル・ノードとの通信を前記スケジューラがスケジューリングするステップと
を含む方法。
【請求項９】
前記モバイル・ノードとの前記通信を前記スケジューラがスケジューリングするステップは、少なくとも１つチャネルの品質の指標および前記第１の重みとベストエフォート型スケジューリングに関連する重みとの大きい方に基づいて前記スケジューラが決定した優先度を使用して、前記少なくとも１つのチャネルを通じて前記モバイル・ノードとの通信を前記スケジューラがスケジューリングするステップを含む請求項８に記載の方法。
【請求項１０】
前記重みを前記スケジューラが再帰的に規定するステップは、前記モバイル・ノードの保証されたビット・レートと、前記時間間隔の間の前記モバイル・ノードのスループットとの差の関数として修正率を前記スケジューラが決定するステップを含む請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に通信システムに関し、より詳細には、ワイヤレス通信システムに関する。
【背景技術】
【０００２】
従来のワイヤレス通信システムは、アクセス・ポイント、基地局、基地局ルータなど、アクセス・ノードのネットワークを使用してワイヤレス接続を提供する。各アクセス・ノードは、移動ユニット、携帯電話、スマート・フォン、ネットワーク・インターフェース・カード、ノートブック・デバイス、ラップトップ、デスクトップなど、１つまたは複数のアクセス端末を用いてエア・インターフェースを通じてワイヤレス通信をサポートするためにリソースを割り当てる。エア・インターフェースのリソースは、通常、利用可能なタイム・スロット、チャネル・コード、周波数、帯域幅、伝送電力などに関して規定される。アクセス・ノードまたは他のネットワーク・エンティティは、ワイヤレス通信のためにアクセス端末にリソースを割り当てるスケジューラを含む。
【０００３】
アクセス端末は、典型的には、優先度に基づいて利用可能なリソースの一部を割り当てられる。たとえば、アクセス端末には、エア・インターフェースを通じた通信に関するサービス品質（ＱｏＳ）レベルおよび／またはチャネル状態に基づいて、スケジューリングの優先度を割り当てることができる。ＱｏＳレベルは、関連するアクセス端末に約束された保証されたビット・レート（ＧＢＲ）に関連づけることができる。あるいは、一部のユーザまたはサービスは、リソースのベスト・エフォート型の割り当てを選ぶことができ、これでは特定のビット・レートは保証されず、その代わりに、ベストエフォート型のユーザ間で利用可能なリソースを公平に分散することを試みる。場合によっては、また、エア・インターフェースを通じてユーザ・トラフィックに最大ビット・レートを与えることもできる。スケジューリング・アルゴリズムおよび／または承認制御アルゴリズムは、様々なＱｏＳユーザおよび／またはベストエフォート型ユーザの競合する需要の平衡を保つことを試みる。
【０００４】
あるアルゴリズムは、ユーザのＱｏＳレベルによって決定された重みおよび長期的な平均スループットまたはビット・レートに対する現在のチャネル・レートの比率の結果として各ユーザの優先度を規定する。重みは、ユーザの保証されたビット・レートと時間窓を通じた平均ビット・レートとの間で正規化された差の指数関数である。結果として、ユーザのスループットが保証されたビット・レートを下回り（または上回る）場合、重みは指数関数的に増加（または減少）する。重みは、また、保証されたビット・レートと平均ビット・レートまたはスループットとの間のエラーの期間の関数であるため、それが長期にわたって持続する場合、重みの増加または減少がさらに増幅される。この積極的な指数関数的な重み係数の正味の影響として、保証されたビット・レートに向けて平均ビット・レートが急速に促され、同時に、Ｗ＝１というベストエフォート型の重みに向けて重みが促される。
【０００５】
指数関数的な重み付け方式は保証されたビット・レートを効果的に維持することができるが代償を伴う。たとえば、本出願の発明者らは、積極的な指数関数的な重み付け方式は、最適でないチャネルを割り当てることをスケジューラに強いるため、結果的にシステムの全体的な効率を下げる可能性があることを示した。たとえば、最適でない状態のＱｏＳユーザのＧＢＲ要件を満たすために、余計なリソースが必要な可能性があり、このためにＢＥユーザが利用できるリソースが減る可能性がある。さらに、スケジューラが指数関数的な重み付け技術を用いる場合、スケジューリング・アルゴリズムは、セル・エッジの近くに位置するユーザの保証されたビット・レートを維持しようと努力する。正味の影響として、最適な割り当てと比較して全体的なスループットが低下する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】欧州特許公開第ＥＰ１６４３６９５号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
開示された主題は、上記の１つまたは複数の問題による影響に対処することを対象とするものである。以下は、開示された主題の一部の態様について基本的な理解を得るために、開示された主題を単純化して概要を提示するものである。この概要は、開示された主題の完全な概要ではない。これは、開示された主題の重要または不可欠な要素を特定したり、または開示された主題の範囲を描写することを意図するものではない。その唯一の目的は、後で記述するより詳細な記述の準備として、単純化した形で一部の概念を提示することである。
【課題を解決するための手段】
【０００８】
一実施形態では、方法は、保証されたビット・レートおよび／または最大ビット・レートの適用をスケジューリングするために提供される。方法の実施形態は、時間間隔の間にモバイル・ノードに対して、以前の時間間隔の間にモバイル・ノードに関連する以前の第１の重みと、第１のビット・レートとモバイル・ノードのスループットの指標との差の一次関数である修正率との合計に等しい第１の重みを設定するステップを含むことができる。方法の実施形態は、また、第１の重みに基づいてモバイル・ノードとの通信をスケジューリングするステップを含むことができる。
【０００９】
他の実施形態では、方法は、保証されたビット・レートおよび／または最大ビット・レートの適用をスケジューリングするために提供される。方法の実施形態は、重みの以前の値の一次関数および第１のビット・レートと、モバイル・ノードのスループットの指標との差を使用してモバイル・ノードに関連する重みを再帰的に規定するステップを含むことができる。方法の実施形態は、また、第１の重みに基づいてモバイル・ノードとの通信をスケジューリングするステップを含むことができる。
【００１０】
開示された主題は、同じ参照番号は同じ要素を示している添付の図面とともに以下の記述を参照することによって理解されるだろう。
【図面の簡単な説明】
【００１１】
【図１】ワイヤレス通信システムの代表的な一実施形態を概念的に示す図である。
【図２】スケジューリングの優先度を決定するために指数関数的な重み付け方式を使用するスケジューラの変化のシミュレーションのために発明者らによって取得されたデータを示す図である。
【図３】スケジューリングの優先度を決定するために線形の重み付け方式を使用するスケジューラの変化のシミュレーションのために発明者らによって取得されたデータを示す図である。
【図４】異なるスケジューリング・アルゴリズムを使用してスループットの比較を示す図である。
【図５】異なるスケジューリング・アルゴリズムを使用して想定されたユーザ分布の累積分布関数の比較を示す図である。
【図６】モバイル・ノードに帯域幅を割り当てるための方法の代表的な一実施形態を概念的に示す図である。
【図７】４人のユーザの分布のために代表的な帯域幅割り当てを示す図である。
【図８】保証されたビット・レートおよび最大ビット・レートの両方の要件について、線形の再帰関係を使用してモバイル・ノードに割り当てられる重みを概念的に示す図である。
【図９Ａ】保証されたビット・レートおよび最大ビット・レートの要件に基づいて、ユーザに帯域幅を割り当て、かつ／または初期化するための方法の代表的な一実施形態を概念的に示す図である。
【図９Ｂ】保証されたビット・レートおよび最大ビット・レートの要件に基づいて、ユーザに帯域幅を割り当て、かつ／または初期化するための方法の代表的な一実施形態を概念的に示す図である。
【発明を実施するための形態】
【００１２】
開示された主題は、様々な変更および代替形式の余地があるが、その特定の実施形態について、図面の例として示し、本明細書に詳細に記述している。しかし、本明細書に記述した特定の実施形態の記述は、開示された特定の形式に開示された主題を限定することを意図するものではなく、それとは反対に、添付された特許請求の範囲に該当するすべての変更、等価物、および代替案を包含することを意図することを理解されるだろう。
【００１３】
例示的実施形態について以下に記述する。明快さのために、実際の実装のすべての機能を、本明細書に記述しているとは限らない。もちろん、そのような任意の実際の実施形態を開発する際に、実装によって異なる、システム関連およびビジネス関連の制約への遵守など、開発者の特定の目標を達成するために多数の実装固有の決定が下されるべきであることを理解されるだろう。さらに、そのような開発努力は、複雑かつ時間がかかる可能性があるが、本開示の利益を受ける当業者にとっては日常的な仕事であろうことを理解されるだろう。
【００１４】
ここで、開示された主題について、添付の図面に関して記述する。様々な構造、システム、およびデバイスは、説明のみを目的として、かつ当業者によく知られている詳細によって本発明を不明瞭にしないように、図面に概略的に描写している。しかし、添付の図は、開示された主題の実例となる例を記述し説明するために含まれている。本明細書に使用される単語および句は、当業者によるそれらの単語および句の理解に一致する意味を持つものと理解および解釈するべきである。本明細書において用語または句を一貫して使用することによって、用語または句の特別な定義、つまり、当業者によって理解されている通常および慣習的な意味とは異なる定義を意味することを意図するものではない。用語または句が特別な意味、つまり当業者によって理解されるものと異なる意味を持つことを意図する場合は、そのような特別な定義は、用語または句の特別な定義を直接的かつ明白に提供する定義方法で明細書に特に記述することになる。
【００１５】
一般的に、本出願は、ワイヤレス通信システムにおいて保証されたビット・レートおよび／または最大ビット・レートの適用のためにリソースをスケジューリングし、かつ／または割り当てるための技術の実施形態について記述する。ある従来のスケジューリング・アルゴリズムは、ＱｏＳユーザのスケジューリングの優先度を決定するために指数関数的な重み係数を使用する。一般通念は、積極的な指数関数的な重み係数によって、通信チャネルも安定している場合、平均ビット・レートは保証されたビット・レートに等しく、ユーザの重みは１に等しい安定した状態に収束するということである。しかし、本出願の発明者らは、実際に達成されたとしても、安定した状態がめったにないことを実証した。さらに、積極的な指数関数的な重み付け技術の目標とする解決策（ＡＢＲ＝ＧＢＲ、Ｗ＝１）は、安定したチャネル状態でも持続可能ではない。たとえば、スケジューラが、保証されたビット・レートを持つＱｏＳユーザおよび保証されたビット・レートを受け取らないベストエフォート型（ＢＥ）のユーザにリソースを割り当てている場合、保証されたビット・レートに等しい平均ビット・レートをＱｏＳユーザが受け取っているときに、安定した状態の解決策は、両方のユーザにＷ＝１を割り当てる。しかし、両方のユーザにベストエフォート型の重みが割り当てられたら、スケジューラは「動作を抑えて（ｒｅｌａｘ）」、ＱｏＳユーザに比較的より高い優先度を割り当てない。したがって、ＱｏＳユーザによって達成される実際のビット・レートは、ＧＢＲに等しくない値に傾く可能性があり、このため平均ビット・レートを急速にＧＢＲに戻すために、重みに対して指数関数的な修正がトリガーされる。したがって、重みに積極的な指数関数的な修正を加えると、重みの値には、大きく振動する変動が生じる可能性がある。
【００１６】
重みの変動の結果は、チャネル・フェージングがない状態では穏やかな場合がある。しかし、チャネル・フェージングは、実質的には、エア・インターフェースを通じてワイヤレス通信に使用されるすべてのチャネルに存在する。スケジューラは、スケジュールされた時間に最も高いチャネル品質を持つユーザにチャネルを割り当てることによって、リソースの使用状況を最適化することを試みる「ピーク・ピッキング」技術を使用して、チャネル・リソースを割り当てる。積極的な指数関数的な重み付け技術は、重みを急速に押し上げることによって、ピーク・ピッキング技術の目標を台無しにする可能性があるため、スケジューラは、これらのユーザがフェージングのためにチャネル品質の劣化を経験している可能性があるにもかかわらず、チャネルをＱｏＳユーザ（複数可）に割り当てるように強いられる。最適でないチャネルを割り当てるようにスケジューラに強いることで、システムの全体的な効率が下がる可能性がある。たとえば、最適でない状態および／またはセル・エッジの位置でＱｏＳユーザのＧＢＲ要件を満たすために余計なリソースが必要な可能性があり、このためにＢＥユーザが利用できるリソースが減る可能性がある。結果的に、最適な割り当てと比較して、全体的なスループットが低下する可能性がある。
【００１７】
本出願では、理論上の理想的なスループットにほぼ一致する個別および全体的なユーザ・スループットを達成することができる代替スケジューリング技術の実施形態について記述している。一実施形態では、スケジューリングは、重みの以前の値の一次関数、およびモバイル・ノードの保証されたビット・レートと測定されたスループットとの差を使用して、各モバイル・ノードに対して再帰的に規定される重みを基準にして実行される。たとえば、第１の重みは、第２の（以前の）時間間隔の間にモバイル・ノードに関連する第２の重みに、モバイル・ノードの保証されたビット・レートとモバイル・ノードの測定されたスループットとの差の一次関数である修正率を加えたものに等しい第１の重みを設定することによって、第１の時間間隔の間にモバイル・ノードに対して規定することができる。次に、モバイル・ノードとの通信は、第１の重みに基づいて、たとえば、第１の重みの関数であるスケジューリングの優先度を使用して、スケジューリングすることができる。
【００１８】
図１は、ワイヤレス通信システム１００の代表的な一実施形態を概念的に示している。図示する実施形態では、ワイヤレス通信システム１００は、エア・インターフェース１１５を通じて１つまたは複数のモバイル・ノード１１０にワイヤレス接続を提供するように構成されたアクセス・ノード１０５を含む。アクセス・ノード１０５は、基地局、アクセス・ポイント、基地局ルータ、家庭内基地局ルータ、フェムトセルなどでもよい。モバイル・ノード１１０は、携帯電話、スマート・フォン、ラップトップ、デスクトップ・コンピュータ、および／または他のワイヤレス対応デバイスでもよい。ワイヤレス通信は、第三世代パートナーシップ・プロジェクト（３ＧＰＰ、３ＧＰＰ２）、米電気電子学会（ＩＥＥＥ）などの規格団体によって規定された規格および／またはプロトコルの第２世代（２Ｇ）、第３世代（３Ｇ）、第４世代（４Ｇ）、および次の世代を含む規格および／またはプロトコルに従ってエア・インターフェース１１５を通じて実行することができる。エア・インターフェースを通じて通信するための技術は当技術分野で知られており、明瞭さのために、特許請求される主題に関連するこれらの通信技術の態様のみについて、本明細書に記述する。
【００１９】
アクセス・ノード１０５の図示する実施形態は、エア・インターフェース１１５を通じてワイヤレス通信をスケジューリングするように構成されたスケジューラ１２０を含む。スケジューラ１２０は、通信のためにエア・インターフェース１１５のリソースをモバイル・ノード１１０に割り当てる。スケジューラ１２０によってスケジューリングし、かつ／または割り当てることができる代表的なリソースは、タイム・スロットまたは他の間隔、周波数／帯域幅、チャネル、チャネル・コードなどを含む。スケジューラ１２０の他の実施形態は、また、エア・インターフェース１１５を通じて伝送するために、パケット・サイズ、変調および符号化の体系、伝送電力などを決定するように構成することができる。スケジューラ１２０は、単一の機能エンティティ、または複数のエンティティに実装することができる。本開示の恩恵を受ける当業者は、スケジューラ１２０は、あるいは、アクセス・ノード１０５の外部の場所に展開または実装できることを理解されるだろう。
【００２０】
一実施形態では、スケジューラ１２０は、積極的な指数関数的に重み付けされた優先度技術を使用して通信をスケジューリングするように構成することができる。たとえば、一般的な重み付けされたプロポーショナル・フェア型スケジューリング・アルゴリズムは、次のようにスケジューリング・ランクまたは優先度Ｐを規定することができる：
Ｐ（ｉ，ｎ）＝Ｗ（ｉ，ｎ）ρ（ｉ，ｎ）／Ｔα（ｉ，ｎ）
ここで、（ｉ，ｎ）は、それぞれユーザおよびサブフレームのインデックスであり、Ｗは、示されたサブフレームの間にユーザに割り当てられたサービスの品質の重みであり（ベストエフォート型のトラフィックに対してＷ＝１）、ρは、（信号対干渉雑音比（ＳＩＮＲ）の関数として）周波数領域リソースの単位ごとのチャネル・レートであり、Ｔは、ユーザの中期的または長期的な平均スループットであり、指数αは、厳密なプロポーショナル・フェア・スケジューリングでは１、最大ＳＩＮＲスケジューリングでは０、または等しいスループット・スケジューリングでは非常に大きな値に設定することができる公平性要素である。積極的な指数関数的な重み付き優先度技術に対する重み要素Ｗは、次のように規定することができる：
Ｗ（ｉ，ｎ）＝ｅｘｐ（γ・ＴＣ（ｉ，ｎ）／ＧＢＲ（ｉ））
ここで、トークン・カウンターＴＣは、次のように規定することができる：
ＴＣ（ｉ，ｎ）＝ｍｉｎ（ｃｌｉｐｐｉｎｇ＿ｆａｃｔｏｒ・ＧＢＲ（ｉ），ＴＣ（ｉ，ｎ−１）＋ＧＢＲ（ｉ）・ＴＴＩ−ＴＢＳ（ｉ，ｎ））
いくつかの実施形態では、トークン・カウンターおよび重みは、あるいは、次のように表現することができる：
ＴＣ（ｉ，ｎ）＝ｍｉｎ（ｃｌｉｐｐｉｎｇ＿ｆａｃｔｏｒ・ＧＢＲ（ｉ），ｎ・ＧＢＲ（ｉ）−Ｒａｖｇ（ｉ，ｎ））・ＴＴＩ
Ｗ（ｉ，ｎ）＝ｍｉｎ（ｍａｘ＿ｗｅｉｇｈｔ，ｅｘｐ（γ・ｎ・ｐｅｒｃｅｎｔ＿ｒａｔｅ＿ｅｒｒｏｒ）
ここで、
ｐｅｒｃｅｎｔ＿ｒａｔｅ＿ｅｒｒｏｒ＝（ＧＢＲ（ｉ）−Ｒａｖｇ（ｉ，ｎ））／ＧＢＲ（ｉ）
トークン・カウンターはゼロで初期化され、保証されたビット・レート（ＧＢＲ（ｉ））はユーザに割り当てられた値、たとえば、ユーザのサービスの品質を示す契約情報によって示される値に等しい。送信時間間隔（ＴＴＩ）は、サブフレームに対して規定され、ＴＢＳは無線経由のトランスポート・ブロック・サイズを示し、これは、ハイブリッド自動再送要求システムの再伝送されたサブフレームでは０と考えられる場合がある。増加または減衰の要素γが関数に対して規定され、クリッピング要素は、重みＷに対する上限を決定する最大重みを設定するために使用することができる。エア・インターフェースのレート平均は、Ｒａｖｇで表される。
【００２１】
スループットがＧＢＲ（保証されたビット・レート）より低かったり、ＭＢＲ（最大ビット・レート）を超えたりしている場合、積極的な指数関数的な重み関数により規定された重みの指数関数的な立ち上がり時間によって、時間および／または周波数リソースに対するスケジューリング決定を行うように、スケジューラ１２０に強いることができる。したがって、たとえば、チャネル強度がエア・インターフェース１１５を通じた伝送に必ずしも必要ない場合など、スケジューリング決定は、場合によっては不適当な時期に行うことができる。結果として、スケジューラ１２０が、たとえば、チャネル品質がより良好な場合など、より最適な時間にリソースをスケジューリングすることを許可された場合、スケジューラ１２０は、必要より多くのリソースを割り当てることを強いられる場合がある。たとえばスケジューラ１２０は、求められる範囲でスループットを制御するために、チャネル品質が改善される場合に必要になるより、より多くの時間／周波数／電力のリソースを割り当てることを強いられる場合がある。このように割り当てを強いることで容量が減り、ベストエフォート型（ＢＥ）サービスに対して、より少ないリソースを残す場合があるため、それによって、ワイヤレス通信システム１００の全体的なスループットが減る場合がある。特許請求される主題の発明者は、スケジューリングのシミュレーションを実行し、積極的な指数関数的な重み付け方式は、多くの実施形態において、ベストエフォート型のスループットにおいて最大２２％の損失につながる可能性があることを示した。さらに、シミュレーションは、また、スループットの低下は、本明細書に記述した代替技術と比較して、多くの場合、２桁である場合があることを示している。テストした他のシナリオでは、また、指数関数的な重み付けアルゴリズムを実装するスケジューラ１２０は、セル・エッジでのユーザのＧＢＲ目標を維持しようと努力するが、本明細書に記述した代替アルゴリズムは、セル・エッジ・ユーザのＧＢＲ目標を容易に維持することができることを示している。
【００２２】
図２は、スケジューリングの優先度を決定するために指数関数的な重み付け方式を使用するスケジューラの変化のシミュレーションのために発明者らによって取得されたデータを示している。図示する実施形態では、水平軸は、シミュレーションの時間間隔を示し、これは図２において約５秒である。左手の垂直軸は、ユーザ装置に割り当てられた重みを示し、右手の垂直軸は、ユーザ装置のスループットをＭｂｐｓで示している。ユーザ装置の保証されたビット・レートは４．２Ｍｂｐｓであり、図示する実施形態では、望ましいサービスの品質を達成するための理想的な重みは、重み２である。本明細書で使用する場合、「理想的な重み」という用語は、たとえば、これらのシミュレーションにおいてアクセス・ノードに関するリングで分散されるＱｏＳおよびＢＥのユーザの特定の混合体に対してシミュレーションされるシステムにおいてユーザに対して保証されたビット・レートをもたらすことが知られている重みの値を指すものである。
【００２３】
シミュレーションでは、スケジューラは、４．２ＭＢｐｓという保証されたビット・レートでユーザ装置のためのスループット２００を非常に効果的に維持する。しかし、シミュレーションはまた、ユーザ装置に割り当てられた重み２０５は、広く急速に振れて変動することも示している。たとえば、ユーザ装置に割り当てられた重み２０５は、１つの送信時間間隔から次の送信時間間隔へと、２倍以上増加または減少する場合がある。したがって、指数関数的に重み付けされたスケジューリング・アルゴリズムは、２方向音声／ビデオ（たとえば電話またはテレビ会議）などの用途に役立つ場合がある。その理由は、このタイプの用途は、典型的に、保証されたビット・レートの制約に伴う厳格な遅延制約を受けやすいからである。少なくとも部分的に、厳格な遅延制約のために、スケジューリングのために最適なチャネルの瞬間（ピーク）を選ぶのが難しい場合があるため、スケジューリング決定においてチャネル意識を強調することはより重要度が低い場合がある。しかし、典型的には、受信機で複数秒のバッファリングが実装されるため、一方向のビデオおよび／またはオーディオ・ストリーミングなどの用途については、遅延制約は緩和される。ストリーミング用途をサポートするために、すべての瞬間に保証されたビット・レートを維持する必要はない。したがって、スケジューラは、遅延制約が存在しないと想定することができ、より長い時間尺度を通じて平均的に保証されたビット・レートを維持するように構成することができる。その結果、スケジューラは、本明細書に記述するように、適切なスケジューラの重み設計でスケジューリングするために、最適または最適に近いチャネルの瞬間（ピーク）を選ぶことができる。本明細書に記述したように、重み付きプロポーショナル・フェア（または他のタイプの重み付きフェア）を実装することで、また、ＧＢＲおよびＭＢＲの制約を受けやすいリソースの公平な分割を保証することができる。
【００２４】
図１を再び参照すると、スケジューラ１２０は、ビット・レート・エラーの一次関数を使用して、スケジューリングの重みを決定する代替スケジューリング・アルゴリズムを実装することができる。たとえば、スケジューリング・アルゴリズムは、ユーザの保証されたビット・レート（および／または最大ビット・レート）と、各ユーザに割り当てられた保証されたビット・レート（および／または最大ビット・レート）に対するユーザの測定されたスループットとの差の比率の一次関数を使用して、スケジューリングの重みを決定することができる。線形の重み付けアルゴリズムは、目標レートと実際のレートとの間の誤差に比例する更新またはインクリメントを使用して、重みの反復を生じさせることができる。発明者らは、線形の重みシーケンスの実施形態は、スループットがＧＢＲに収束するにつれて、基礎をなす理想的な（理論上は最適な）静的な重みへと漸近的に収束させることを示した。線形のアルゴリズムは、ユーザの重みの値に指数関数的な揺れを生じさせず、結果的に、長期的なリソース利用部分のニーズが満たされる限り、瞬間的な割り当て決定に干渉しない。
【００２５】
本明細書に記述したように、スケジューリングの優先度は、スケジューリングの重みおよびチャネル品質の測定を表す要素の結果として規定することができる。重みの振幅の変動を減らすこと（および重みの変化の時間的尺度を増やすこと）で、スケジューリングの重みに対するスケジューリングの優先度の感度を下げることができ、チャネル品質に対するスケジューリングの優先度の感度を上げることができる。したがって、ピーク・ピッキングなどの技術を使用して、チャネル品質が良好な場合、スケジューラ１２０は、ユーザを優先的にスケジューリングするために、チャネルを意識した日和見的な（ｏｐｐｏｒｔｕｎｉｓｔｉｃ）スケジューリングを実行することができる。したがって、たとえば、最小限の時間、周波数、およびエネルギー・リソースを使用して、スケジューラ１２０は、ビット・レート要件を容易かつ効率的に満たすことができる。これは、（ＧＢＲおよびＭＢＲタイプのＱｏＳユーザの）容量の増加、および／または（ＢＥトラフィックの）スループットの増加につながる。
【００２６】
一実施形態では、スケジューラ１２０は、各時間間隔の間に各ユーザの重みを再帰的に規定する。たとえば、重みは、次により規定することができる：
【００２７】
【数１】
0005852227.tif 000002
ここで、ＧＢＲは、ユーザｉに保証されたビット・レートであり、Ｔｉは、ユーザの現在の測定されたスループットであり、ｋは、０．１などステップサイズまたはノイズの平均算出要素である。重みは、あるいは、次の式を使用して、トークン・カウンターの現在値に関して規定することができる：
【００２８】
【数２】
0005852227.tif 000003
重みは、１というベストエフォート値に初期化することができる。または、本明細書に記述するように、モバイル・ノードのそれぞれについて、保証されたビット・レートおよび／または最大ビット・レートによって課される制約を受けるモバイル・ノードに帯域幅を割り当てる反復手順を使用して割り当てられた帯域幅の関数として初期化することができる。
【００２９】
図３は、スケジューリングの優先度を決定するために線形の重み付け方式を使用するスケジューラの変化のシミュレーションのために発明者らによって取得されたデータを示している。図示する実施形態では、水平軸は、シミュレーションの時間間隔を示し、これは図３では約１０秒である。左手の垂直軸は、ユーザ装置に割り当てられた重みを示し、右手の垂直軸は、ユーザ装置のスループットを示している。ユーザ装置の保証されたビット・レートは３２４５ｋｂｐｓであり、図示する実施形態では、破線３００によって示すように、望ましいサービスの品質を達成するための理想的な重みは、８という重みである。本明細書で使用する場合、「理想的な重み」という用語は、たとえば、これらのシミュレーションにおいてアクセス・ノードに関するリングで分散されるＱｏＳおよびＢＥのユーザの特定の構成に対してシミュレーションされるシステムにおいてユーザに対して保証されたビット・レートをもたらすことが知られている重みの値を指すものである。
【００３０】
図示する実施形態では、ユーザに割り当てられる重み３１０は、１．０というベストエフォート型の重みで初期化され、８という理想的な重みにほぼ等しい重み３１０に徐々に収束する前に、最初に約１２という重み３１０に上昇する。ユーザのスループット３０５は、３２４５ｋｂｐｓという目標スループットに近い値に徐々に安定する前に約３０００ｋｂｐｓで始まる。図２に示す指数関数的な重み付け技術のシミュレーションと比較すると、スループット３０５が保証されたビット・レートに近づくのにいくぶん長くかかるが、線形の重み付けアルゴリズムは、目標スループットを正しく達成する。スループット３０５が保証されたビット・レートに到達すると、図２に見られる変動よりわずかに大きくこの値の近くを変動する。しかし、図２〜図３に示すシミュレーションの比較は、また、線形の重み付けアルゴリズムの顕著な利点を示している。たとえば、重み３１０は、８という理想的な重みに収束し、比較的小さな変動でこの値を維持する。他の例では、シミュレーションの最も早い段階においても、重み３１０の変動の時間的尺度は送信時間間隔よりはるかに長く、送信時間間隔の間の重み３１０の変動の振幅は、重み３１０の値のごくわずかである。
【００３１】
図２および図３に示すシミュレーションの比較は、指数関数的な重み付けアルゴリズムによって生じるスケジューラの変化は、所与のレートを達成するためにリソースのより大きな部分を必要とすることをさらに示している（帯域幅かける時間）。結果的に、他のＧＢＲおよび／またはＢＥのユーザについて、より少ないリソースを利用できる状態となり、このため、ＧＢＲ容量および／またはＢＥスループットの低下につながる可能性がある。指数関数的に重み付けされたアルゴリズムのために、スケジューラはＰＤＢ制約されたスケジューラのように振る舞う。これは、バッファされるストリーミングによるＱｏＳ用途、ＢＥ用途のサービス程度（ＧｏＳ）ユーザ・レート層などに必要ではない。他方では、線形の重み付けアルゴリズムを使用してスループットおよび対応するリソースの一部を漸近的に保証するスケジューラがより効率的な場合がある。たとえば、本明細書に記述した線形の重み付けアルゴリズムは、安定した重みをサポートすることによって、長期的なスループットを保証することができる（これは、バッファされたストリーミングなどの用途にとって必須のＱｏＥ測定基準である）。線形の重み付けアルゴリズムは実装が簡単であり、明らかにより効率的である。
【００３２】
図４は、異なるスケジューリング・アルゴリズムを使用するスループットの比較４００を示している。図示する実施形態では、比較４００は、想定される「理想的な」プロポーショナル・フェア・スケジューラに関連する第１の列４０５、積極的な指数関数的に重み付けされた技術を使用するトークン・アルゴリズムに関連する第２の列４１０、および本明細書に記述した線形の重み付け技術の実施形態を使用するアルゴリズムに関連する第３の列４１５を含む。図４に示す結果を出すために使用されるシミュレーションは、８人のユーザがいて、ユーザはアクセス・ノードの周りに環状に分散していることを想定している。これらのユーザの１人は保証されたビット・レートを持ち、他のユーザはベストエフォート型のユーザである。行は、アクセス・ノードからのユーザの距離（１７ｄＢ、６ｄＢ、および０ｄＢ）およびＱｏＳユーザに割り当てられた保証されたビット・レート（１５２２８．７８ｋｂｐｓ、６６３７．２６ｋｂｐｓ、および３２４５．５１ｋｂｐｓ）によって区別される。第１の列４０５は、アクセス・ノードからのユーザの距離およびＧＢＲ／ＱｏＳユーザの理想的なスループット、ベストエフォート・ユーザのそれぞれの理想的なスループット、ならびにすべてのユーザの理想的な全体的なスループットを示している。第２および第３の列４１０、４１５は、シミュレーションされたスループットおよびシミュレーションされたスループットと理想的なスループットの比率を示している。
【００３３】
セル（１７ｄＢ）の中心に近いユーザに対して、指数関数的な重み付けアルゴリズムおよび線形の重み付けアルゴリズムの両方は、ＱｏＳユーザ、ベストエフォート・ユーザ、およびすべてのユーザの全体に対して理想的なスループットに非常に近い（たとえば１％または２％以内）スループットを作り出す。しかし、セルの中心からのユーザの距離が大きくなるとともに（１７ｄＢから６ｄＢ、０ｄＢ）、指数関数的な重み付けアルゴリズムは、理想的なスループットから著しく外れ始める。たとえば、エッジ・ユーザ（０ｄＢ）について、ＱｏＳユーザのスループットは理想のわずか９６％であり、ベストエフォート・ユーザのスループットは理想の７９％であり、全体的なスループットは理想のわずか８７％である。これとは対照的に、線形の重み付けアルゴリズムは、理想値に実質的に等しいスループットをエッジ・ユーザに対して作り出す（たとえば１％以内）。図４は、また、図示するシミュレーションの線形の重み付けアルゴリズムによって出されたスループットが、ユーザの位置の影響をあまり受けず、すべての距離で理想値に実質的に等しいことを示している。本出願の発明者らは、また、重み収束が堅牢であり（たとえば、重み収束は、様々なシナリオで図４に示した振る舞いに似た方法で振る舞う）、システムの統計において変化（たとえば、移動性による平均チャネル品質の変動、ユーザの到着／出発または集中的なトラフィックによる負荷の変化）を追跡できることを実証した。さらに、代替実施形態では、平均パラメータを適切に選択することによって、オーバーシュート減衰を得るために収束の速度がトレードオフにされる場合がある。
【００３４】
図５は、異なるスケジューリング・アルゴリズムを使用する想定されるユーザ分布について発明者らによって決定された累積分布関数の比較５００を示している。累積分布関数（ＣＤＦ）は、ユーザごとのスループット（水平軸）を達成しているユーザの一部を（垂直軸に）示している。したがって、ユーザごとのスループットが少なくとも１人のユーザによって達成される最小値に到達するまで、累積分布関数はゼロである。任意のユーザによって達成される最大スループットで１の値に到達するまで、累積分布関数は単調増加する。図示する実施形態では、比較５００は、「理想的な」プロポーショナル・フェア・スケジューラに関連する第１のＣＤＦ５０５、積極的な指数関数的に重み付けされた技術を使用するトークン・アルゴリズムに関連する第２のＣＤＦ５１０、および本明細書に記述した線形の重み付き技術の実施形態を使用するアルゴリズムに関連する第３のＣＤＦ５１５を含む。図５に示す結果を出すために使用されるシミュレーションでは、１０人のユーザが、アクセス・ノードに関して異なる位置に分散され、高速フェージングによりチャネル品質の変動が生じることを想定している。ユーザは、３５０ｋｂｐｓという保証されたビット・レートを持っている。
【００３５】
ユーザの一部は少なくともこの保証されたビット・レートを受けているため、第１のＣＤＦ５０５は、３５０ｋｂｐｓという保証されたビット・レートで始まる。第１のＣＤＦ５０５は、約３９００ｋｂｐｓというユーザごとの最大スループットで１という値に単調増加する。第２のＣＤＦ５１０は、２９０ｋｂｐｓだけというユーザごとのスループットで始まり、これは保証されたビット・レート未満であり、指数関数的な重み付けアルゴリズムは、一部のユーザ、たとえばエッジ・ユーザおよび／または比較的大きなフェージングを経験しているユーザ対して保証されたビット・レートを達成できないことを示している。さらに、第２のＣＤＦ５１０は、「理想的な」第１のＣＤＦ５０５のパフォーマンスより大きく劣っている。その理由は、ユーザごとのスループットの各値の第２のＣＤＦ５１０の値は、第１のＣＤＦ５０５の値よりはるかに大きいためである。これは、指数関数的な重み付けアルゴリズムは、スケジューラに、「理想的な」第１のＣＤＦ５０５と比較してより低いビット・レートでより多くのユーザをスケジューリングさせることを示している。これとは対照的に、第３のＣＤＦ５１５は、第１のＣＤＦ５０５をほぼ完璧に追跡し、第１のＣＤＦ５０５の「理想的な」値から小さなずれしか示していない。
【００３６】
表１は、図５に示す累積分布関数を得るために使用されるシミュレーションのセル・スループットに関して異なるアルゴリズムの相対的なパフォーマンスを示している。表１に示す結果は、線形の重み付けアルゴリズムの相対的なパフォーマンスは、理想的なプロポーショナル・フェア・スケジューリング・アルゴリズムのパフォーマンスの数パーセント内にあることを示している。他方、指数関数的な重み付けアルゴリズムは、相対的なパフォーマンスが理想的なパフォーマンスよりほぼ１７％低い。これは、スケジューリング・アルゴリズムによって達成される効率の大幅な低下である。
【００３７】
【表１】
0005852227.tif 000004
【００３８】
図１を参照すると、スケジューラ１２０は、様々な異なる技術を使用して、モバイル・ノード１１０の優先度および／または重みを初期化することができる。一実施形態では、スケジューラ１２０は、Ｗ＝１というベストエフォート型の値へとモバイル・ノード１１０の重みを初期化することができる。あるいは、初期化アルゴリズムは、重みを生成する再帰型フィルターの初期化またはリセットの始点を生成するために、各ＧＢＲ／ＭＢＲユーザのリソースおよび重みの計算を実行するために使用することができる。このアルゴリズムの実施形態は、スケジューラ１２０、またはワイヤレス通信システム１００の他の場所においてオフライン・プロセッサ（たとえばバッチ・プロセッサ）に実装することができる。アルゴリズムの実施形態は、また、任意のＧＢＲおよび／またはＭＢＲ制約を持つ新しいユーザ（複数可）を許可するために必要なリソース割り当てを測定または決定することによって、（たとえば、より長期的な平均チャネル測定に基づいて）呼承認制御を実行するために用いることができる。アルゴリズムの実施形態は、また、平均チャネル品質測定およびＧＢＲ／ＭＢＲ目標に基づいて、既存の許可されたユーザのリソース割り当ての一部分を予測するか、またはアルゴリズムは、あるいは、スケジューラ１２０からのチャネル品質／ターゲットの測定を使用することができる。
【００３９】
図６は、モバイル・ノードに帯域幅を割り当てるための方法６００の代表的な一実施形態を概念的に示している。図示する実施形態では、（図１に示すスケジューラ１２０など）方法６００を実装する機能エンティティは、要求された割り当てが実現可能かどうかを（６０５で）決定する。たとえば、スケジューラは、モバイル・ノードの保証されたビット・レートに必要な帯域幅リソースをすべて合計し（たとえば、リソースを割り当てられるユーザのプールにあるすべてのユーザ）、少なくともこれらの最低要件を満たすために十分な帯域幅が利用可能かどうかを決定することができる。ベストエフォート・ユーザは、要求された割り当てが実現可能かどうかを（６０５で）決定する目的のために帯域幅を保証されないと想定することができる。提案された割り当てが実現可能でない場合、方法６００を（６１０で）終了することができる。あるいは、代替リソース割り当てを提案することができ、システムは、新しい割り当てが実現可能かどうかを（６０５で）決定することができる。たとえば、保証されたビット・レートを持つユーザのプールは、一部のユーザをドロップすることによって減らすことができる。方法６００が承認制御に使用される場合、この手法は特に役に立つ場合がある。
【００４０】
割り当てが実現可能な場合、ユーザのプールにある各ユーザに等しい帯域幅を（６１５で）割り当てることができるため、全体的な利用可能な帯域幅は、プールにあるユーザのすべてに均等に分配される。次に、スケジューラは、ユーザのすべての目標帯域幅が満たされたかどうかを（６２０で）決定することができる。たとえば、スケジューラは、等しい帯域幅割り当てがＱｏＳユーザのすべての保証されたビット・レート要件を満たすかどうかを（６２０で）決定することができる。目標帯域幅がすべて満たされる場合、リソースの割り当ては（６１０で）終了することができる。しかし、保証されたビット・レート要件を満たすために、ユーザの一部がより多くの帯域幅を必要とする場合、スケジューラは、保証されたビット・レート要件を満たすために、これらのユーザに十分なリソースを（６２５で）割り当てることができる。一実施形態では、スケジューラは、保証されたビット・レート要件を満たすために十分なリソースだけを割り当て、実質的に超過リソースを（６２５で）割り当てないように試みる。本明細書で使用する場合、「本質的に超過リソースを割り当てない」という語句は、指定された許容範囲内の保証されたビット・レート要件を満たすのに十分なリソースだけを割り当てたこと、および、ユーザは、割り当てられたリソースを使用して保証されたビット・レートの許容レベルを超えてビット・レートを達成することができないと、スケジューラが決定することを示すために使用される。リソース／帯域幅割り当てを受け取ったユーザは、ユーザのプールから（６３０で）削除される。次に、スケジューラは、プールに残るユーザに残りの帯域幅を（６１５で）等しく割り当てることによって、残りのユーザに残りの割り当てられていないリソース／帯域幅を公平に割り当てる。
【００４１】
この手順は、帯域幅要件がすべて満たされ、帯域幅がすべて割り当てられるまで繰り返される。割り当てが実現可能であると（６０５で）決定されたため、これらの要件をすべて満たす割り当ては存在する。重みおよび／または優先度は、割り当てられたリソース／帯域幅の関数として重みおよび／または優先度を決定することによって初期化することができる。たとえば、ベストエフォート・ユーザ、およびベストエフォート・ユーザと同じ帯域幅割り当てを受け取る任意のＱｏＳユーザには、Ｗ＝１という初期重みを割り当てることができる。保証されたビット・レート要件を満たすために、より大きな帯域幅を割り当てられるユーザには、より大きな重みを割り当てることができるため、最大帯域幅要件を持つユーザは、最大の重みに初期化され、比較的より小さい帯域幅要件を持つユーザは、比較的より小さい重みに初期化される。
【００４２】
図７は、４人のユーザの分布のために代表的な帯域幅割り当てを示している。図示する実施形態では、ユーザの３人は、保証されたビット・レート要件７００を持つＱｏＳユーザであり、ユーザの１人はベストエフォート・ユーザである。最初の２人のユーザは、比較的大きな保証されたビット・レート要件７００（１〜２）を持っているため、それに応じて大きな帯域幅を割り当てられる。しかし、帯域幅がこれらのユーザに割り当てられた後、第３のＱｏＳユーザの保証されたビット・レート要件を満たしながら、残り２人のユーザで残りの帯域幅７０５を公平に分配するのに十分な帯域幅が維持される。
【００４３】
図１を参照すると、線形のスケジューリング・アルゴリズムは、複数のビット・レート要件に対応するために一般化することができる。たとえば、スケジューラ１２０は、保証されたビット・レート（たとえば最小ビット・レート）および各ユーザまたはモバイル・ノードに許可された最大ビット・レート（ＭＢＲ）の関数である線形の帰納式を使用してユーザの重みを決定することができる。一実施形態では、スケジューラ１２０は、各時間間隔の間に各ユーザの重みを再帰的に規定する。たとえば、保証されたビット・レートおよび最大ビット・レートに関連する重みは、次により規定することができる：
【００４４】
【数３】
0005852227.tif 000005
ここで、ＧＢＲｉは、ユーザｉの保証されたビット・レートであり、ＭＢＲｉは、ユーザｉの最大ビット・レートであり、Ｔｉは、ユーザの現在の測定されたスループットであり、かつｋは、０．１などステップサイズまたはノイズの平均算出要素である。重みは、あるいは、次の式を使用して、トークン・カウンターの現在値に関して規定することができる：
【００４５】
【数４】
0005852227.tif 000006
図示する実施形態では、トークン・カウンターは、それぞれＧＢＲおよびＭＢＲのエラー・トークン・カウンターの現在値である。次に、特定のユーザまたはモバイル・ノードに割り当てられた重みは、最大ビット・レートを超えないながら、保証されたビット・レート（または１というベストエフォート型の重み）と少なくとも同じ大きさになるように設定することができる。たとえば、重みは次のように規定することができる：
Ｗｉ（ｎ）＝ｍｉｎ（Ｙｉ（ｎ），ｍａｘ（Ｘｉ（ｎ），１．０））
重みは、１というベストエフォート値に初期化することができる。または、本明細書に記述するように、モバイル・ノードのそれぞれについて、保証されたビット・レートおよび／または最大ビット・レートによって課される制約を受けるモバイル・ノードに帯域幅を割り当てる反復手順を使用して割り当てられた帯域幅の関数として初期化することができる。
【００４６】
図８（Ａ）〜（Ｃ）は、保証されたビット・レートおよび最大ビット・レートの両方の要件について、線形の再帰関係を使用して、モバイル・ノードに割り当てられる重みを概念的に示す図である。図示する実施形態では、重みは垂直軸に示され、一時的なインデックス（ｎ）は水平軸に示されるため、左から右に時間は増加する。図８（Ａ）は、ＱｏＳユーザおよびベストエフォート・ユーザへのリソースの比例的に公平な割り当てが、保証されたビット・レートおよび最大ビット・レートの要件の両方を満たすときに割り当てられる重みを示している。これらは、それぞれ「ＧＢＲスラック」および「ＭＢＲスラック」ケースと呼ぶことができる。この場合、すべてのユーザの重みは、Ｗ＝１というベストエフォート型の値に設定することができる。
【００４７】
図８（Ｂ）は、比例的に公平な量のリソースより多くを割り当てることによって保証されたビット・レート要件が満たされるため、保証されたビット・レート要件を満たすために十分な量のリソース／帯域幅が割り当てられるシナリオを示している。このケースは「ＧＢＲタイト」と呼ぶことができる。この場合、保証されたビット・レート要件を満たすのに必要な以上には追加的なリソースが割り当てられないため、最大ビット・レート要件が満たされる。次に、重みは、保証されたビット・レートに基づいて決定されたレートを追跡する。全体的な重みは、大きく一時的なインデックスで比較的平坦な線によって示すように、値Ｗ＞１で集中して安定している。
【００４８】
図８（Ｃ）は、比例的に公平な量のリソースより少なく割り当てることによって最大ビット・レート要件を満たすため、ユーザまたはモバイル・ノードに割り当てられるリソース／帯域幅の量は、ユーザまたはモバイル・ノードが最大ビット・レート要件を超えることを可能にしないシナリオを示している。このケースは「ＭＢＲタイト」と呼ぶことができる。この場合、最大ビット・レートは、保証されたビット・レートより大きく規定されため、最大ビット・レート要件が満たされる場合に、定義により、保証されたビット・レート要件を満たすために十分なリソースが割り当てられるため、保証されたビット・レート要件が満たされる。次に、重みは、最大ビット・レートに基づいて決定されたレートを追跡する。全体的な重みは、大きい一時的なインデックスで比較的平坦な線によって示すように、値Ｗ＜１で収束して安定している。
【００４９】
図９Ａ〜図９Ｂは、保証されたビット・レートおよび最大ビット・レートの要件に基づいて、ユーザに帯域幅を割り当て、かつ／または初期化するための方法９００の代表的な一実施形態を概念的に示す図である。図示する実施形態では、方法９００（図１に示すスケジューラ１２０など）を実装する機能エンティティは、要求された割り当てが実現可能かどうかを（９０５で）決定する。たとえば、スケジューラは、モバイル・ノードの必要な保証されたビット・レートをすべて合計し（たとえば、リソースを割り当てられるユーザのプールにあるすべてのユーザ）、少なくともこれらの最低要件を満たすために十分な帯域幅が利用可能かどうかを決定することができる。スケジュールは、また、保証されたビット・レートおよび最大ビット・レートが一貫していることを確認することができる。たとえば、各ユーザの保証されたビット・レートは、対応するユーザの最大ビット・レート未満である。ベストエフォート・ユーザは、要求された割り当てが実現可能かどうかを（９０５で）決定する目的のために帯域幅を保証しない（かつ最大帯域幅を持たない）と想定することができる。提案された割り当てが実現可能でない場合、方法９００は終了することができる。あるいは、代替リソース割り当てを提案することができ、システムは、新しい割り当てが実現可能かどうかを（９０５で）決定することができる。方法９００が承認制御に使用される場合、この手法は特に役に立つ場合がある。
【００５０】
割り当てが実現可能な場合、ユーザのプールの各ユーザに等しい帯域幅を（９１０で）割り当てることができるため、全体的な利用可能な帯域幅は、プールのユーザのすべてに均等に分配される。次に、スケジューラは、ユーザのすべての目標帯域幅が満たされたかどうかを（９１５で）決定することができる。たとえば、スケジューラは、等しい帯域幅割り当てが、ユーザのすべての保証されたビット・レート要件および最大ビット・レート要件を満たすかどうかを（９１５で）決定することができる。提案された割り当てが帯域幅要件をすべて満たす場合、方法９００を（９２０で）終了することができる。提案された割り当てが帯域幅要件のすべてを満たさない場合、スケジューラは、ユーザのサブセットが保証されたビット・レート要件を満たすために、リソースの公平な割り当てを超えて必要とするかどうかを（９２５で）決定する。
【００５１】
リソースの公平な割り当てを超えて必要とするサブセットのユーザは、保証されたビット・レート要件を満たすために十分なリソース／帯域幅を（９３０で）割り当てられる。たとえば、スケジューラは、引き続き保証されたビット・レート要件を満たすことが期待できる最小帯域幅である最小の必要な帯域幅（ＭＲＢ）を（９３０で）割り当てることができる。次に、サブセットのユーザは、第１のサブセットに（９３５で）追加される。これはＧＢＲタイト・サブセットと呼ぶことができる。フラグは、第１のサブセットが最大ではないことを示すために「ＦＡＬＳＥ」に（９４０で）設定される。たとえば、残りの帯域幅の公平な割り当てが、現在、第１のサブセットにないユーザの保証されたビット・レート要件を満たしていない場合、追加的なモバイル・ノードを第１のサブセットに追加することが可能である。次に、方法は（９４５で）フラグ試験に進むことができる。フラグが真ではないと試験で（９４５で）決定された場合、つまり、フラグがＦＡＬＳＥに設定されている場合、第１の組のユーザは残りのユーザのプールから（９４６で）削除され、第１の組のユーザに割り当てられた帯域幅は、プールの残りのユーザへの割り当てに利用できる帯域幅から（９４６で）削除される。任意のユーザがプールに残るとスケジューラによって（９４７で）決定された場合、スケジューラは、方法９００の別の反復を始めるためにステップ９１０に戻る。この分岐のために、ＧＢＲタイト・ユーザの単調増加候補（必ずしも最終ではない）の組が増えるため、公平な割り当ての単調減少シーケンスが生じる場合がある。方法９００のこの分岐は、一部のケースでは、残りのユーザが、残りの帯域幅の公平な割り当てを超えて必要としないとスケジューラが（９２５で）決定するまで反復し続け、方法９００は（９４８で）終了する。
【００５２】
この時点で、解決策が存在することが知られているため、すべてのユーザは、ＧＢＲ制約の観点から実現可能な初期割り当てを持っている。下に記述するように、一部のユーザは、また、ＭＢＲ制約の観点から実現可能な場合があり、次の分岐ステップの反復により、１組のＭＢＲタイト・ユーザだけでなく、公平な割り当ての単調増加シーケンスも生じる場合がある。このプロセスでは、一部のＧＢＲタイトの組のユーザは、ＧＢＲおよびＭＢＲスラップの組に移動することができ、ユーザは、また、ＧＢＲおよびＭＢＲスラックの組からＭＢＲタイトの組に移動することができる。ＭＢＲの観点からも実現可能なものを増加させながら、（ＧＢＲの観点から）実現可能性は、すべてのユーザに対して維持される。
【００５３】
割り当ての実現可能性は、残りのユーザが公平な帯域幅割り当てを超えて必要としない場合、残りのユーザの一部は、公平な割り当て未満を要求する必要があることを意味する。たとえば、ユーザの一部は、リソース／帯域幅の公平な割り当てを受け取った場合に超える可能性がある最大ビット・レートを持っていなければならない。別の言い方をすると、この場合、ユーザの一部は、公平に割り当てられた帯域幅より低い最大許容帯域幅（ＭＡＢ）を持っている。したがって、スケジューラは、最大許容帯域幅の最低値を持つユーザに最大許容帯域幅（ＭＡＢ）を（９５０で）割り当てる。これらのユーザは、また、第２の組に（９５５で）追加される。これはＭＢＲタイトの組と呼ぶことができる。第２の組のメンバーシップは最終であり、方法９００のさらなる反復によって変更されない。第２の組に（９５５で）追加されなかった残りのユーザは、第３の組に（９６０で）追加される。これはＧＢＲ／ＭＢＲスラックの組と呼ぶことができる。第２の組のユーザにＭＡＢを（９５０で）割り当てた後に利用できる過剰な帯域幅は（９６５で）計算され、第１のサブセットが最大であることを示すためにフラグがＴＲＵＥに（９７０で）設定される。たとえば、追加的なモバイル・ノードは、方法９００のさらなる反復の間に第１のサブセットに追加されなくてもよい。しかし、下に記述するように、モバイル・ノードは、さらなる反復の間に第１のサブセットから削除することができる。
【００５４】
次に、方法はフラグ試験に（９４５で）進むことができる。フラグが真であると試験で（９４５で）決定された場合、つまり、フラグがＴＲＵＥに設定されている場合、残りのユーザのプールは、ユーザの第３の組に等しく（９７５で）設定される。次に、利用可能な帯域幅は、第３の組とのユーザにも割り当てられた帯域幅に、ユーザにまだ割り当てられていない任意の過剰な帯域幅を加えたものに等しく（９８０で）設定される。次に、スケジューラは、残りのユーザのプール全体で公平に（均等に）利用可能な帯域幅を分割または共有することによって、試験割り当てを（９８３で）決定する。スケジューラは、プールの残りのユーザへの利用可能な帯域幅の公平な試験割り当てが、第１の組の任意のユーザの最も小さい最小必要帯域幅より大きいユーザごとの割り当てにつながるかどうかを（９８５で）決定する。該当しない場合、本明細書に記述するように、方法は、いずれかのユーザがプールに残っているかどうかを（９４７で）チェックし、次に進む。しかし、公平な試験割り当てが、第１の組の任意のユーザの最も小さい最小必要帯域幅より大きい場合、公平な割り当てより低いＭＲＢを持つ第１の組からのユーザは、第３の組に（９９０で）追加され、残りのユーザのプールは、変更されたユーザの第３の組に等しく（９７５で）設定される。たとえば、これらのユーザは第１の組から削除され、第３の組に追加される。（９７５、９８０、９８５、９９０での）ループは、プールの残りのユーザへの利用可能な帯域幅の公平な割り当てが、第１の組の任意のユーザの最も小さいＭＲＢより大きいユーザごとの割り当てへとつながらないとスケジューラが（９８５で）決定するまで反復する。
【００５５】
一代替実施形態では、それらにＭＲＢを最初に割り当てることによって、すべてのユーザの最も大きい最大ＧＢＲタイトの組を構成することができる。次に、残りのリソースを計算することができ、リソース割り当てを実行するために、ステップ９５０、９５５、９６０、９６５、９７５、９８０、９８５、および９９０において記述したように、注水アルゴリズム（water pouring algorithm）を使用することができる。一部の実施形態では、方法９００によって決定されたＧＢＲタイトの組が最大（フラグ＝ＴＲＵＥ）で、割り当てが不完全であるため、残りのユーザのプールは少なくとも１人のユーザを含む場合、方法９００は、ステップ９３０、９３５、９４０を省略し（かつ、これらのステップに戻らない）、方法９００は、初めてステップ９５０に進む。
【００５６】
この手順は、帯域幅要件がすべて満たされ、帯域幅がすべて割り当てられるまで繰り返される。割り当てが実現可能であると（９０５で）決定されたため、これらの要件をすべて満たす割り当ては存在する。重み（Ｗ、Ｘ、および／またはＹ）および／または優先度は、割り当てられたリソース／帯域幅の関数として重みおよび／または優先度を決定することによって初期化することができる。たとえば、ベストエフォート・ユーザ、およびベストエフォート・ユーザと同じ帯域幅割り当てを受け取る任意のＱｏＳユーザには、Ｗ＝１という初期重みを割り当てることができる。保証されたビット・レート要件を満たすために、より大きな帯域幅を割り当てられるユーザには、より大きな重みを割り当てることができるため、最大帯域幅要件を持つユーザは、最大の重みに初期化され、比較的より小さい帯域幅要件を持つユーザは、比較的より小さい重みに初期化される。
【００５７】
方法９００の実施形態は、各ユーザのＧＢＲおよびＭＢＲ制約の両方を満たす実現可能な割り当てを生じさせることができるため、個々の割り当ておよび最終的な公平な割り当てはＫＫＴ状態を満たす：ユーザは、ＭＲＢ＞最終的な公平な割り当てであるときかつそのときに限り、ＧＢＲタイト・サブセットにあり、ユーザは、ＭＡＢ＜最終的な公平な割り当てであるときかつそのときに限り、ＭＢＲタイト・サブセットにあり、節約するべきリソースがない、または最小であり、厳密に最終的な公平な割り当てであるときかつそのときに限り、他のすべてのユーザは、ＧＢＲおよびＭＢＲスラック・サブセットにある。したがって、方法９００の実施形態は、最適な解決策をもたらすことができる。
【００５８】
最大ＧＢＲタイトの組＝ＦＡＬＳＥ段階（９３０、９３５）において、方法９００がこの段階を終了するまで、各反復の後に残りのユーザの数は厳密に減少しており、これは、この段階において最大でもＮステップを意味する。補足的な最大ＧＢＲタイトの組＝ＴＲＵＥの段階（９５０、９５５、９６０、９６５）において、それがアルゴリズムを終了するまで、各反復の後にＭＢＲタイトの組のユーザの数は、厳密に増加している。ここでも、これはこの段階において最大でもＮステップを意味する。一実施形態では、ユーザは、２つのリストで順位付けすることができる。１つは、ＦＡＬＳＥ段階を支援するためにＭＲＢの降順で、他方は、ＴＲＵＥ段階を支援するためにＭＡＢの昇順である。ソート動作＋２Ｎ（２段階）を実行するための（ＧＢＲ、ＭＢＲ）の最悪計算量は、２ＮｌｏｇＮステップでもよく、これは、Ｏ（ＮｌｏｇＮ）ステップを持つプロセスにつながる。これはユーザの明示的な順序に依存しておらず、上記の「外部」アルゴリズムは、Ｏ（２Ｎ）時間に実行するように見えるが、「内部」ステップは、最悪の場合には、それぞれ累積的なＮ（Ｎ−１）／２操作のそれぞれ、つまりＯ（Ｎ２）の複雑性を意味するＧＢＲ／ＭＢＲタイトであるものを決定するために、すべての残りのユーザの組を通じて実行（比較）することができる。しかし、事前ソートされた２つのリスト（９５０、９５５、９６０、９６５の昇順のＭＡＢおよび９３０、９３５の降順のＭＲＢ）は、毎回、各リストの上部のユーザをチェックすること、またはアルゴリズムの過程の間に各リストですべてのユーザを一度だけチェックすることのみを必要とする場合がある。
【００５９】
本明細書に記述した技術の実施形態は、従来の積極的な指数関数的な重み付け技術より多くの長所を持つことができる。従来製品の基地局スケジューラの既存の解決策と比較して、重み付きスケジューリングのための提案された線形の重み付け技術の実施形態は、ＧＢＲ目標をより良好に達成する。たとえば、目標を満たす解決策を見つける可能性が高い。線形の技術の実施形態は、また、リソースをより効率的に使うことができる。その理由は、指数関数的な重み付け技術で行われることが示されたのと同じ方法で、それらはチャネル・ピーク・ピッキングまたは日和見主義のスケジューリング（ｏｐｐｏｒｔｕｎｉｓｔｉｃ  ｓｃｈｅｄｕｌｉｎｇ）を妨げないからである。効率が上がると、より高いＧＢＲユーザ容量および／またはより高いベストエフォート型および他のサービス・スループットにつながる。たとえば、特許請求された技術の実施形態は、発明者らがテストしたシナリオにおいてベストエフォート型のスループットを最大２２％改善することを示した。さらに、発明者らは、指数関数的な重み付け技術と比較して、線形の重み付け技術について２桁の割合の改善（平均１５％）を示した。ＧＢＲユーザ容量に対して、同様の改善を予想することができる。提案された解決策は、複雑性が非常に低く、実際に、従来の指数関数的な重み付けアルゴリズムよりシンプルである。
【００６０】
１０ＭＨｚのＦＤＤ  ＬＴＥキャリア（ダウンリンク）における容量／スループットが１０〜２０％増加すると、約１．２〜２．４Ｍｂｐｓの向上につながる。金銭的には、独立分析によって、（１つのまたは別の方式を介して）基地局ごとに１Ｍｂｐｓの容量を追加するには約２０００ドルかかることが示唆されている。したがって、本明細書に記述した技術の実施形態を実装するシステムは、（無視できるコストについて）基地局ごとに正味約４０００ドルの節約を得ることができ、展開されている基地局が何万もあることを考慮すると、これは数億ドルにつながる。最後に、提案された変更は実装するのが簡単であり、実際に、中核となる等式は、現在の等式と比較して、少なくはないにせよ同様の計算量を含む。
【００６１】
開示された主題および対応する詳細な説明の部分は、ソフトウェア、またはコンピュータ・メモリ内のデータ・ビットに対する操作を表すアルゴリズムおよび記号に関して提示されている。これらの記述および表現は、当業者が他の当業者に仕事の本質を効果的に伝達するものである。本明細書で使用し、一般的に使用されるアルゴリズムという用語は、望ましい結果につながる首尾一貫した連続したステップであると考えられる。ステップは、物理量の物理的な操作を必要とするものである。通常、必須ではないが、これらの量は、格納、転送、組み合わせ、比較、または操作可能な光学的、電気的、または磁気的な信号の形をとる。これらの信号は、主に一般的に使用する理由から、時には、ビット、値、要素、記号、文字、用語、数値などと呼ぶことが便利であると分かっている。
【００６２】
しかし、これらおよび同様の用語はすべて、適切な物理量に関連しており、これらの量に適用される便利なラベルにすぎないことを覚えておくべきである。特に別記しない限り、または記述から明白でない限り、「処理」または「コンピューティング」または「計算」または「決定」または「表示」などの用語は、コンピュータ・システムのレジスタおよびメモリ内の物理的な電子量として表されたデータを操作し、コンピュータ・システムのメモリもしくはレジスタ、または他のそのような情報記憶装置、伝送デバイスもしくは表示デバイス内の物理量として同様に表される他のデータへと変形するコンピュータ・システム、または同様の電子計算デバイスの活動およびプロセスを指すものである。
【００６３】
また、開示された主題のソフトウェアに実装された態様は、典型的に、プログラム記憶媒体の何らかの形式で符号化されるか、または何らかのタイプの伝送媒体を通じて実装されることに注意されたい。プログラム記憶媒体は、磁気的（たとえば、フロッピー・ディスクまたはハードドライブ）、または光学的（たとえば、コンパクト・ディスクを使った読み出し専用メモリ、すなわち「ＣＤ  ＲＯＭ」）でもよく、読み出し専用またはランダム・アクセスでもよい。同様に、伝送媒体は、ツイストペア線、同軸ケーブル、光ファイバ、または当技術分野で既知の他の何らかの適切な伝送媒体でもよい。開示された主題は、特定の実装のこれらの態様によって限定されるものではない。
【００６４】
上に開示した特定の実施形態は例を示しているにすぎず、開示した主題は、本明細書の教示の利益を受ける当業者に明白な、異なるが同等の方法で変更および実施することができる。さらに、以下の特許請求の範囲に記述した以外、本明細書に示した構造または設計の詳細に限定することを意図するものではない。したがって、上に開示した特定の実施形態は変更または修正することができ、そのような変形形態はすべて、開示された主題の範囲内にあると考えられることは明白である。したがって、本明細書に求められる保護は、以下の特許請求の範囲に記述する通りである。
【図１】
0005852227.tif 000007
【図２】
0005852227.tif 000008
【図３】
0005852227.tif 000009
【図４】
0005852227.tif 000010
【図５】
0005852227.tif 000011
【図６】
0005852227.tif 000012
【図７】
0005852227.tif 000013
【図８】
0005852227.tif 000014
【図９Ａ】
0005852227.tif 000015
【図９Ｂ】
0005852227.tif 000016