(57)【要約】      （修正有）【課題】Ｂ３Ｇ／４Ｇセルラー網内で異種のトラフィックをスケジューリングする方法及び装置の提供。【解決手段】サービスされているユーザごと、平均ユーザスループット等を追跡し、データフローの最低速度保証と音声フローの最大遅延及びジッタ保証に対するユーザ要求に対応する、可能性のあるスケジュール群を決定することと、各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して、各ユーザに対する競合フローを最初に決定することと、対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得ることと、最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定することと、決定するステップからのパラメータに固有のスケジュールの中で、最大の増分効用または限界効用を与える、チャネル上のユーザの最終的なスケジュールを算出することと、を有する。【選択図】図１Ａ
2008289127.tif 000002
【特許請求の範囲】
【請求項１】
ＯＦＤＭセルラーシステムにおいてサービスを受けているユーザごとに、平均ユーザスループット、パケット遅延及びジッタを追跡するステップと、
フィードバックを用いて、データフローの最低速度保証と音声フローの許容可能な最大遅延及びジッタ保証と対応したデータ及び音声トラフィックに対するユーザ要求に対応する、可能性のあるスケジュール群を決定するステップと、
各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して、各ユーザに対する競合フローを最初に決定するステップと、
対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得るステップと、
最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定するステップと、
前記決定するステップからのパラメータに固有のスケジュールの中で、最大の増分効用または限界効用を与える、チャネル上のユーザの最終的なスケジュールを算出するステップと、
を含む方法。
【請求項２】
前記追跡するステップは、各ユーザの回線パケットの現在のヘッドの瞬間的な速度、遅延及びジッタに対応している、請求項１に記載の方法。
【請求項３】
速度情報について、すべての移動局ＭＳは、(i)すべての利用可能なＯＦＤＭチャネル上の最高速度、(ii)前記最高速度に対応するチャネルインデックス、及び(iii)すべての利用可能なＯＦＤＭチャネル上での総合速度を収集して基地局へフィードバックする、請求項２に記載の方法。
【請求項４】
現在のパケットの遅延及びジッタ情報は、前のパケットから保持されている情報とフィードバックされたパケット速度情報とを用いて得られる、請求項１に記載の方法。
【請求項５】
前記各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して各ユーザに対する競合フローを最初に決定することは、遅延及びジッタのトラフィックパラメータに関する限界効用の中で最も高い総和を与える音声ユーザに属するすべての音声フローの中から特定の音声フローを決定することを含む、請求項１に記載の方法。
【請求項６】
前記各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して各ユーザに対する競合フローを最初に決定することは、遅延及びジッタのトラフィックパラメータに関する限界効用の中で最も高い総和を与える音声ユーザに属するすべての音声フローの中から特定の音声フローを決定することを含み、前記パラメータは、ｋ∈Ｋｖに対して次の関係
【数１】
2008289127.tif 000013
に係る右辺の括弧内の項となり、ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、ｐはパラメータ（速度／遅延／ジッタ）、そしてＰはパラメータ数である、請求項１に記載の方法。
【請求項７】
前記各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して各ユーザに対する競合フローを最初に決定することは、速度トラフィックパラメータに関して最も高い限界効用を与えるデータユーザに属するすべてのデータフローの中から特定のデータフローを決定することを含む、請求項１に記載の方法。
【請求項８】
前記各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して各ユーザに対する競合フローを最初に決定することは、速度トラフィックパラメータに関して最も高い限界効用を提供するデータユーザに属するすべてのデータフローの中から特定のデータフローを決定することを含み、前記速度トラフィックパラメータは、ｋ∈Ｋｄに対して次の関係
【数２】
2008289127.tif 000014
に係る右辺の括弧内の項となり、ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、ｐはパラメータ（速度／遅延／ジッタ）、そしてＰはパラメータ数である、請求項１に記載の方法。
【請求項９】
各ユーザの複数のフローにおいて、Ｋ人のユーザからなる前記群は、Ｋｖ人の音声ユーザ及びＫｄ人のデータユーザからそれぞれ構成されるとして、次の関係が成立することを有し、
【数３】
2008289127.tif 000015
ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、ｐはパラメータ（速度／遅延／ジッタ）、そしてＰはパラメータ数である、請求項１に記載の方法。
【請求項１０】
前記最大の増分効用または限界効用を与える個別の速度、遅延、及びジッタを決定する前記ステップは、次式の関係を含み、
【数４】
2008289127.tif 000016
ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、βはユーザＱｏＳクラス優先度、ｐはパラメータ（速度／遅延／ジッタ）、ｒは瞬時の速度、Ｌはパケットサイズ、Ｐはパラメータ数、Ｓは可能性のあるスケジュールの探索空間であり、ｖkは長さＮのサブチャネル割り当てベクトルを表す、請求項１に記載の方法。
【請求項１１】
前記最大の増分効用または限界効用を与える個別の速度、遅延、及びジッタを決定する前記ステップは、前記速度トラフィックパラメータに関して最も高い限界効用を与えるスケジュールを決定することを含み、その結果決定されたスケジュールは、データユーザの群及び選ばれたデータユーザへのサブチャネルの割り当てであり、前記スケジュールは、速度スケジュール探索（ＲＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１２】
前記最大の増分効用または限界効用を与える個別の速度、遅延、及びジッタを決定する前記ステップは、次式の関係
【数５】
2008289127.tif 000017
を含み、ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、βはユーザＱｏＳクラス優先度、ｐはパラメータ（速度／遅延／ジッタ）、ｒは瞬時の速度、Ｌはパケットサイズ、Ｐはパラメータ数、Ｓは可能性のあるスケジュールの探索空間であり、ｖkは長さＮのサブチャネル割り当てベクトルを表し、前記関係は、前記速度トラフィックパラメータに関して前記最も高い限界効用、すなわち右辺の括弧内の項を与えるスケジュールを決定し、その結果決定されたスケジュールは、データユーザの群及び選ばれたデータユーザへのサブチャネルの割り当てであり、前記スケジュールは、速度スケジュール探索（ＲＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１３】
前記最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタを決定する前記ステップは、遅延及びジッタのトラフィックパラメータに関して限界効用の中で最も高い総和を与えるスケジュールを決定することを含み、前記得られたスケジュールは、音声ユーザの群及び選ばれた音声ユーザへのサブチャネルの割り当てであり、前記スケジュールは、遅延スケジュール探索（ＤＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１４】
前記最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタを決定する前記ステップは、次式の関係
【数６】
2008289127.tif 000018
を含み、ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、βはユーザＱｏＳクラス優先度、ｐはパラメータ（速度／遅延／ジッタ）、ｒは瞬時の速度、Ｌはパケットサイズ、Ｐはパラメータ数、Ｓは可能性のあるスケジュールの探索空間であり、ｖkは長さＮのサブチャネル割り当てベクトルを表し、前記関係は、遅延及びジッタのトラフィックパラメータに関して、限界効用の最も高い総和、すなわち右辺の括弧内の項を与えるスケジュールを決定し、前記得られたスケジュールは、音声ユーザの群及び選ばれた音声ユーザへのサブチャネルの割り当てであり、前記スケジュールは、前記遅延スケジュール探索（ＤＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１５】
前記最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタを決定する前記ステップは、遅延及びジッタのトラフィックパラメータに関して、限界効用の中で最も高い総和（右辺の括弧内の項）を提供するスケジュールを決定することを含み、その結果決定されたスケジュールは、音声ユーザの群及び選ばれた音声ユーザへのサブチャネルの割り当てであり、前記スケジュールは、パラグラフ３０で定義されているように、前記ジッタスケジュール探索（ＪＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１６】
前記最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタを決定する前記ステップは、次式の関係
【数７】
2008289127.tif 000019
を含み、ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、βはユーザＱｏＳクラス優先度、ｐはパラメータ（速度／遅延／ジッタ）、ｒは瞬時の速度、Ｌはパケットサイズ、Ｐはパラメータ数、Ｓは可能性のあるスケジュールの探索空間であり、ｖkは長さＮのサブチャネル割り当てベクトルを表し、前記関係は、遅延及びジッタのトラフィックパラメータに関して、限界効用の最も高い総和、すなわち右辺の括弧内の項を提供するスケジュールを決定し、前記得られたスケジュールは、音声ユーザの群及び選ばれた音声ユーザへのサブチャネルの割り当てであり、前記スケジュールは、前記ジッタスケジュール探索（ＪＳＳ）空間内であらゆる可能なスケジュールを探索することにより得られる、請求項１に記載の方法。
【請求項１７】
前記決定ステップから、パラメータに固有のスケジュールの中で最大の増分効用または限界効用を提供するチャネル上のユーザの最終スケジュールを算出する前記ステップは、関係
【数８】
2008289127.tif 000020
にしたがって実行される、請求項１０に記載の方法。
【請求項１８】
前記決定ステップから、パラメータに固有のスケジュールの中で最大の増分効用または限界効用を提供するチャネル上のユーザの最終スケジュールを算出する前記ステップは、関係
【数９】
2008289127.tif 000021
にしたがって実行され、前記関係は、速度、遅延及びジッタのパラメータに関して最も高い限界効用を与える前記速度、遅延及びジッタに固有のスケジュールをそれぞれとって、前記３つのスケジュールの中で最も高い限界効用を与えるスケジュールを見つけ、該スケジュールは、前記選ばれたユーザへの対応するチャネルの割り当てとともに、ユーザの最終スケジュールとして戻される、請求項１０に記載の方法。
【請求項１９】
対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得る前記ステップは、速度スケジュール探索空間（ＲＳＳ）：
【数１０】
2008289127.tif 000022
と、遅延スケジュール探索空間（ＤＳＳ）：
【数１１】
2008289127.tif 000023
と、ジッタスケジュール探索空間（ＪＳＳ）：
【数１２】
2008289127.tif 000024
とによる関係を含む、請求項１に記載の方法。
【請求項２０】
ＯＦＤＭセルラーシステムにおいてサービスを受けているユーザごとに、平均ユーザスループット、パケット遅延及びジッタを追跡する手段と、
フィードバックを用いて、データフローの最低速度保証と音声フローの許容可能な最大遅延及びジッタ保証と対応したデータ及び音声トラフィックに対するユーザ要求に対応する、可能性のあるスケジュール群を決定する手段と、
各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して、各ユーザに対する競合フローを最初に決定する手段と、
対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得る手段と、
最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定する手段と、
前記決定する手段からのパラメータに固有のスケジュールの中で、最大の増分効用または限界効用を与える、チャネル上のユーザの最終スケジュールを算出する手段と、
を有する装置。
【請求項２１】
総合速度のフィードバックに応答して各ユーザに対する競合フローを最初に決定する前記手段は、Ｋ人のユーザからなる前記群は、Ｋｖ人の音声ユーザ及びＫｄ人のデータユーザからそれぞれ構成されるとして、次の関係が成立することを有し、
【数１３】
2008289127.tif 000025
ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、ｐはパラメータ（速度／遅延／ジッタ）、及びＰはパラメータ数である、請求項２０に記載の装置。
【請求項２２】
最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定する前記手段は、次式の関係を有し、
【数１４】
2008289127.tif 000026
ここで、Ｕは効用関数、ｆはフローインデックス、ｋはユーザインデックス、αはトラフィックタイプ優先度、βはユーザＱｏＳクラス優先度、ｐはパラメータ（速度／遅延／ジッタ）、ｒは瞬時の速度、Ｌはパケットサイズ、Ｐはパラメータ数、Ｓは可能性のあるスケジュールの探索空間であり、ｖkは長さＮのサブチャネル割り当てベクトルを表す、請求項２０に記載の装置。
【請求項２３】
前記決定するステップからのパラメータに固有のスケジュールの中で最大の増分効用または限界効用を与えるチャネル上のユーザの最終スケジュールを算出する前記ステップは、関係
【数１５】
2008289127.tif 000027
にしたがって実行される、請求項２２に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、無線通信に関し、特に、複数チャネルを備えるＢ３Ｇ／４Ｇセルラーネットワークにおける異種(heterogeneous)のトラフィックのスケジューリングに関する。
【背景技術】
【０００２】
メディアアプリケーションの人気及び導入を考えると、セルラーネットワークは、高データレート及びこのような多数のアプリケーションを支援する能力を提供することを前提に、Ｂ３Ｇ／４Ｇネットワークに向かって進んでいる。さらに、このようなセルラーシステムのＬＴＥ（長期発展；long-term evolution）プロジェクトの主な目標の１つは、オールＩＰネットワークへの収束であり、そこではすべてのアプリケーションがＩＰ上で運ばれることが想定されている。このような目的を考えると、セルターネットワークは、単にデータトラフィックのみならず、データ、ＶｏＩＰ、ストリーミングアプリケーション等のような多種多様の異種のトラフィックをも効率的に搬送するように構成される必要がある。そのような試みにおける重要な設計要素の１つが基地局トラフィックスケジューラである。
【０００３】
個別のトラフィックタイプ及びトラフィックパラメータに向けたスケジューラを設計したいくつかの研究があるが、それらを使用して複数のトラフィックタイプを並行して最適化することはできない。ひとつに対して他よりも厳密な優先度を与えることによる、データ及び音声アプリケーション用のスケジューラを設計する研究もある。よって、これらの研究は、異なるトラフィックタイプ間でリソースを柔軟に交換する能力を持たない。その能力は、サービスＱｏＳを分類する場合、異なる品質に属するトラフィックフローにとって極めて重要である。したがって、それらの間でリソースを柔軟に割り当てる能力とともに、複数の異種のトラフィックタイプを同時に処理する効率的なスケジューラの構築は大きな注目に値する。
【０００４】
直交周波数分割多重（ＯＦＤＭ；orthogonal frequency deivision multiplexing）は、Ｂ３Ｇ／４Ｇセルラーシステム用の望ましい無線インタフェース技術である。複数のＯＦＤＭサブチャネルに対してユーザ及びデータを割り当てるリソース割り当て戦略を提案している研究が複数ある。しかしながら、これらの研究は速度にのみ注目し、速度、遅延、ジッタ等のような異種のトラフィックパラメータを考慮していない。さらに、これらの研究は、機構の複雑さまたは通信オーバーヘッドにも注目していない。したがって、ＯＦＤＭセルラーシステムにおける異種（データ及び音声）トラフィックを処理可能な、複雑でなく、オーバーヘッドが小さくかつ高い性能を持つスケジューラの構築が本発明の主題を形成している。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
それゆえ、ＯＦＤＭセルラーシステムにおける異種（データ及び音声）トラフィックを処理可能な、複雑でなく、オーバーヘッドが小さく、かつ高い性能を持つスケジューラが必要とされている。
【課題を解決するための手段】
【０００６】
本発明によれば、方法は、ＯＦＤＭセルラーシステムにおいてサービスを受けているユーザごとに、平均ユーザスループット、パケット遅延及びジッタを追跡することと、フィードバックを用いて、データフローの最低速度保証と音声フローの許容可能な最大遅延及びジッタ保証と対応したデータ及び音声トラフィックに対するユーザ要求に対応する、可能性のあるスケジュール群を決定することと、各ユーザに対する複数のフローを用いて、総合速度(aggregate rate)のフィードバックに応答して、各ユーザに対する競合フロー(contending flow)を最初に決定することと、対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得ることと、最大の増分効用(incremental utility)または限界効用(marginal utility)を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定することと、決定するステップからのパラメータに固有のスケジュールの中で、最大の増分効用または限界効用を与える、チャネル上のユーザの最終的なスケジュールを算出することと、を含む。
【０００７】
本発明の他の様相によれば、装置は、ＯＦＤＭセルラーシステムにおいてサービスを受けているユーザごとに、平均ユーザスループット、パケット遅延及びジッタを追跡する手段と、フィードバックを用いて、データフローの最低速度保証と音声フローの許容可能な最大遅延及びジッタ保証と対応したデータ及び音声トラフィックに対するユーザ要求に対応する、可能性のあるスケジュール群を決定する手段と、各ユーザに対する複数のフローを用いて、総合速度のフィードバックに応答して、各ユーザに対する競合フローを最初に決定する手段と、対応する最適化戦略に応答して、速度、遅延及びジッタに関するユーザ要求の探索空間を得る手段と、最大の増分効用または限界効用を提供する個別の速度、遅延及びジッタに関連するスケジュールを決定する手段と、決定する手段からのパラメータに固有のスケジュールの中で、最大の増分効用または限界効用を与える、チャネル上のユーザの最終スケジュールを算出する手段と、を含む。
【０００８】
発明のこれら及び他の利点は、以下の詳細な説明及び添付図面を参照して、当業者には明白になるであろう。
【発明を実施するための最良の形態】
【０００９】
本発明に基づく統一(unified)スケジューリングプロセスは、基地局で実行され、ユーザに対応するリソース割り当てを決定するとともに、任意の与えられたタイムスロットで送信するユーザの群を決定するタスクを行なう。このプロセスは、多くの特別な利点及び機能性を備えている。
【００１０】
本発明に基づくスケジューリングプロセスは、異種のトラフィックタイプ及びパラメータを最適に処理する統一フレームワークを提供する。統一スケジューリングプロセスは、速度、パケット遅延及びパケットジッタの複数のトラフィックパラメータを同時に最適化する。これは、データ、音声及びストリーミングアプリケーションとともに使用でき、速度、遅延、及び／またはジッタのパラメータの最適化を必要とする他のアプリケーションとともにも使用することができる。
【００１１】
スケジューリングプロセスは、異なるトラフィックタイプ間でリソースを割り当てる柔軟性を提供する。このことは、このプロセスをインターネットの差別化されたサービス（ＱｏＳ）機構に適用することを可能にし、それによって、異なるＱｏＳクラスに属する異なるトラフィックタイプをリソースに対して適切かつ動的に割り当てることができる。
【００１２】
統一スケジューリングプロセスは、最適な性能を提供する。しかしながら、最適な性能を達成する複雑さが、複数の直交周波数分割多重ＯＦＤＭサブチャネルという状況下で、指数関数的に増加する。この解決のために、新しいパラメータベースの最適化方法を用いて、ＯＦＤＭ方式のスケジューリングプロセスの、複雑さがより小さく、オーバーヘッドがより低い（ＬＣＯ）バージョンを提案している。
【００１３】
スケジューリングプロセスのＬＣＯバージョンは、最適なスキームの場合のオーダーより小さい、ＮNのオーダーの複雑さを生じ、ここでＮは、基地局と移動局の両方でのアンテナの数である。複雑さにおけるこの低減は、フレームごとにプロセスを実行することを可能にし、そして、それは基地局でのスケジューリング決定の細かさとなる。
【００１４】
最適なスキームと比較した場合、通信オーバーヘッドも、移動局からのフィードバックの形態で、ほぼＮのオーダーだけ低減される。これは、アップリンク上で有用な通信に対する付加的な帯域幅リソースを解放することになる。
【００１５】
複雑さ及びオーバーヘッドの低減に対し払うべき代償は、最適な統一スケジューリングプロセスと比べて、準最適性能であることである。しかしながら、この構成は、最適プロセスからたった約２０％の偏差しか有していないので、非常に優れた性能を与える。
【００１６】
この解決法は、アップリンクとダウンリンクの両方に適用可能である。提案している解決法のこれらの特定の属性は、この解決法を、Ｂ３Ｇ／４ＧセルラーシステムにおいてＯＦＤＭ上の異種のトラフィックを搬送する、効率的であり、低複雑性／オーバーヘッド（複雑性及びオーバーヘッドが低いこと）、高性能なスケジューリングプロセスの優れた候補にしている。
【００１７】
図１Ａのシステムブロック図を参照して、本発明に係る低複雑性／オーバーヘッドのスケジューラを用いたブロック図の一例を示している。複数のユーザ、すなわちユーザ１，ユーザ２，…，ユーザＫからのデータ及び音声情報は、フローキューを通って低複雑性／オーバーヘッドＬＣＯモジュールへ入る。データ及び音声情報は、ユーザごとの低複雑性／オーバーヘッドＬＣＯユーザ内(intra user)スケジューラと、低複雑性／オーバーヘッドのリソースアロケータ(resource allocator)とへ入力される。速度、遅延及びジッタのようなＫ個のユーザの要求は、ＬＣＯモジュールへ渡され、ＬＣＯユーザ内スケジューラと、ＬＣＯユーザ間(inter-user)スケジューラ及びＬＣＯリソースアロケータとの両方にその要求を与える共同(joint)スケジューリングリソース割り当てアルゴリズムへ入力される。ＬＣＯユーザ間スケジューラ及びＬＣＯリソースアロケータからの出力は、スケジューリング決定に基づいた単一ユーザＳＵまたは複数ユーザＭＵの戦略のための変調及び符号化プロセスへ入力される。無線ユーザからのフィードバックは、Ｋ個のユーザのチャネル及びパラメータ情報として処理され、それは、ＬＣＯモジュールの共同スケジューリング及びリソース割り当てアルゴリズムへフィードバックされる。
【００１８】
図１Ｂのダイアグラムを参照して、ＬＣＯスケジューリングモジュールの機能を詳述する。異種の音声及びデータトラフィックは、異種のトラフィックパラメータ最適化、柔軟なＱｏＳ差別化、ユーザ内及びユーザ間のスケジューリング、低複雑性、低オーバーヘッド、及び高性能な能力を提供するＬＣＯスケジューリングモジュールへ入力される。
【００１９】
ＬＣＯ（低複雑性／オーバーヘッド）スケジューラは基地局に常駐し、２つのコンポーネント、すなわちユーザ内及びユーザ間スケジューリングコンポーネントを含んでいる。ユーザ内及びユーザ間コンポーネントは、低複雑性／オーバーヘッドＬＣＯの共同スケジューリング及びリソース割り当てプロセスによってデータを供給される。
【００２０】
ＬＣＯスケジューリングプロセスの原理は、本発明に基づく統一された最適なスケジューリングプロセスであり、それは、次の２ステップのスケジューリング規則により与えられる。
【００２１】
ステップ１：ユーザ内スケジューリング規則
【００２２】
【数１】
2008289127.tif 000003
【００２３】
ステップ２：ユーザ間スケジューリング規則
【００２４】
【数２】
2008289127.tif 000004
【００２５】
基地局はユーザ当たり１つのキューを備えるだけなので、最初のスケジューリング規則は、タイムスロットを求めて競合するであろう各ユーザからの特定のフローを識別する。これはネットワーク層で起こる。２番目のスケジューリング規則は、その後、利用可能なリソースに基づいて、所与のスロットの中で実際に送信するであろうユーザの群（最初のステップからのフロー）を識別する。これらの規則は、異なるパラメータ（速度／遅延／ジッタ）値をもたらす所与のリソース割り当てのために得られたアプリケーション（エンドユーザ）ユーティリィティを表す共通の手段として、凹(concave)効用関数（Ｕ）をフローに使用している。
【００２６】
注釈：Ｕ−効用関数(utility function)、ｆ−フローインデックス、ｋ−ユーザインデックス、α−トラフィックタイプ優先度、β−ユーザＱｏＳクラス優先度、ｐ−パラメータ（速度／遅延／ジッタ）、ｒ−瞬時の速度、Ｌ−パケットサイズ、Ｐ−パラメータ数、Ｓ−可能性のあるスケジュールの探索空間。
【００２７】
直交周波数分割多重ＯＦＤＭの場合には、スケジュール探索空間Ｓは、指数関数的になる。最適なスキームに近い性能を保持しつつ複雑さ及びオーバーヘッドを低減するために、ＬＣＯは、次のアプローチを用いる。
【００２８】
ａ）ＬＣＯは、必ずしもすべてのパラメータを並行して最適化するわけではない。ＬＣＯは、最大の正味（ネット）での増分効用をもたらし、各スロットにおいてその特定のパラメータを最適化する単一のパラメータを識別する。
【００２９】
ｂ）ＬＣＯは、どのパラメータが最大の正味での増分効用をもたらすかに基づいて、１つのスロットから別のスロットへとパラメータ間を移動する。
【００３０】
ｃ）単一のパラメータが最適化されるので、それは、性能に関して準最適である。一方、これは複雑さ及びオーバーヘッドを低減するために利用される。
【００３１】
ｄ）個別のパラメータを最適化する特定の通信戦略は、識別されて通信に使用される。パラメータに固有の最適化は性能であるので、これらの識別された戦略は、通信オーバーヘッドの低減だけでなく、可能性のあるスケジュールに対する探索空間の著しい低減にも寄与する。
【００３２】
ｅ）具体的には、（Ｎ個のサブチャネルをすべて使用する）単一ユーザ（ＳＵ；single-user）送信戦略は、パケット遅延に対する最適化戦略であると識別されるが、一方、（Ｋ人のうちの）スロットで送信しているＮ人の異なったユーザを有する複数ユーザ（ＭＵ；multi-user）戦略は、速度及びジッタの最適化戦略であると識別される。
【００３３】
ｆ）ユーザ当たり１つのチャネルだけ複数ユーザ戦略の中で使用されるので、移動局（ＭＳ）にそれらの最良のサブチャネルインデックス及び関連付けられた速度を識別してフィードバックすることを可能にさせることにより、複雑さ及びオーバーヘッドはさらに単純化される。
【００３４】
ｇ）さらに、パラメータ最適化通信戦略が各スロットで使用されているので、複雑さとフィードバックのオーバーヘッドとを低減しつつ、最適からの偏差は小さいままに保たれた。
【００３５】
ここで、図２のフロー図を参照して、本発明に基づくＬＣＯスケジューリングプロセスの方法を示す。本発明に基づくスケジューラの方法は、データに対して関心あるパラメータである速度、及び音声に対して関心あるパラメータであるパケット遅延及びパケットジッタを用いて、データ及び音声トラフィックを処理する。
【００３６】
ステップ１：基地局（ＢＳ）は、データフローの最低速度保証、及び音声フローの許容可能な最大遅延保証及びジッタ保証に関して、データ及び音声トラフィックに対するユーザ要求を収集する（２１）。
【００３７】
ステップ２：ＢＳは、そのＢＳがサービスするユーザごとに、平均ユーザスループット／速度、パケット遅延、及びパケットジッタを追跡する（２２）。しかし、ＢＳは、各ユーザの回線パケットの現在のヘッドの瞬時の速度、遅延及びジッタに関する情報を必要とする。速度情報については、各ＭＳは、(i)すべての利用可能なＯＦＤＭチャネル上の最高速度(Rmu)、(ii)最高速度に対応するチャネルインデックス(lmu)、及び(iii)すべての利用可能なＯＦＤＭチャネル上の総合速度(Rsu)を収集し（２４）、ＢＳへフィードバックする（２３）。現在のパケットの遅延及びジッタ情報は、前のパケットから保持されている情報とともに、フィードバックされたパケットの速度情報を用いて得られる。
【００３８】
ステップ３：ＢＳは、フィードバックを用いて、考慮されるパラメータに基づいて可能性のあるスケジュール群を決定し、次に、最良のスケジュールを決定する（２５）。
【００３９】
ステップ４：各ユーザに対して複数のフローがある場合、ＢＳは、総合速度のフィードバック(Rsu)に基づいて、各ユーザｋの競合フローを先ず次のように決定する。説明を簡単にするために、Ｋ人のユーザの群が、Ｋｖ人の音声ユーザとＫｄ人のデータユーザからそれぞれ構成されると仮定する。
【００４０】
【数３】
2008289127.tif 000005
【００４１】
ステップ５：ＢＳは、識別された最適化戦略に基づいて、個別のパラメータ（速度、遅延及びジッタ）の各々に対する探索空間を次のように取得する。
【００４２】
・速度スケジュール探索空間（ＲＳＳ；Rate schedule search space）：
【００４３】
【数４】
2008289127.tif 000006
【００４４】
・遅延スケジュール探索空間（ＤＳＳ；Delay schedule search space）：
【００４５】
【数５】
2008289127.tif 000007
【００４６】
・ジッタスケジュール探索空間（ＪＳＳ；Jitter schedule search space）：
【００４７】
【数６】
2008289127.tif 000008
【００４８】
ステップ６：ＢＳは、最大の増分／限界効用を与える個別のパラメータ（速度、遅延及びジッタ）に固有のスケジュールを次式のように算出する（２９）。
【００４９】
【数７】
2008289127.tif 000009
【００５０】
ここで、ｖkは長さＮのサブチャネル割り当てベクトルを表す。
【００５１】
ステップ７：ＢＳは、ステップ６で既に決定されているパラメータに固有のスケジュールのうち最大の増分／限界効用を与えるものとして、チャネル上のユーザの最終スケジュールを次式のように算出する（２０１）。
【００５２】
【数８】
2008289127.tif 000010
【００５３】
性能：
ＬＣＯスケジューリングプロセスは、最適なスキーム、すなわち
【００５４】
【数９】
2008289127.tif 000011
【００５５】
で生じたオーダーより小さいＮNのオーダーである
【００５６】
【数１０】
2008289127.tif 000012
【００５７】
の探索空間に比例する複雑さを生じる。Ｂｒ及びＢｎが速度及びアンテナのインデックスのフィードバックにそれぞれ割り当てられたビット数を表す場合、ＬＣＯのフィードバックのオーバーヘッドは、Ｋ（２Ｂｒ＋Ｂｎ）となり、それはほぼ、最適なスキームで生じたオーダーよりも小さいＮのオーダー、すなわちＫＮ（Ｂｒ＋Ｂｎ）となる。さらに、ＬＣＯスキームの性能は、最適時の約２０％以内にあるので、著しい性能利得をも与える。複数の異種のトラフィックパラメータを同時に処理する能力が従来の方法にないために、従来の同種(homogeneous)のスケジューリングアプローチに対する性能利得は、けた違いに良い（２倍から３倍）。
【００５８】
次のリストは、任意の効率的で実用的なスケジューラ設計における不可欠の特徴群を示している、すなわち、（ａ）異種のトラフィックタイプ／パラメータ、（ｂ）ユーザ内及びユーザ間スケジューリング、（ｃ）異なるトラフィックタイプ間での柔軟なリソース割り当て、（ｄ）共同のスケジューリング及びリソース割り当て、及び（ｅ）低複雑性／オーバーヘッドである。しかしながら、ほとんどの先行技術の研究では、それらのスケジューラ設計において、上記のリスト中の１つの様相のみ、または多くても２つの様相しか考慮していない。
【００５９】
図３Ａの従来システムのダイアグラム、及び図３Ｂに詳述した従来のスケジューリングモジュールの機能に示すように、ほとんどすべての先行技術研究に欠けている主要なコンポーネントは、(i)ユーザ内及びユーザ間スケジューリングの両方における異種のトラフィックタイプ／パラメータの調整、(ii)異なるトラフィックタイプ間での柔軟なリソース割り当てと複数のトラフィックＱｏＳクラスの調整、及び(iii)低複雑性と低オーバーヘッドとを備えた効率的なスケジューリングであり、これらは、基地局でのスケジューリング機構のリアルタイム実行にとって重要である。
【００６０】
同種のトラフィックタイプ、主としてデータフローの速度に重点を置いたスケジューラは、複数の異種のトラフィックタイプ／パラメータを同時に調整する能力及びそれらの間でリソースを柔軟に割り当てる能力がないので、ＬＣＯアプローチと比較した場合、性能利得が数倍（２倍から３倍）劣っている。これらは、チャネル依存性スケジューリング及びＯＦＤＭリソース割り当てスキームを活用するパケットスケジューラを含んでいる。ＬＣＯスキームと比較した場合、最適なＯＦＤＭリソース割り当てでさえ、最適な性能を得るのに必要な桁違い（ＮN）の複雑さは言うまでもなく、７５％の性能ロスとなる。
【００６１】
異種のトラフィックタイプすなわちデータ及び音声に重点を置いたスケジューラは、異なるトラフィックタイプ間でリソースを柔軟に割り当てることができないので、インターネットにおいて不可欠なトラフィックのサービス品質ＱｏＳクラスがある状況では、使用することができない。さらに、このようなスケジューラは、効率的な物理層リソース割り当て部、及びそれらに関連付けられた複雑さ及びオーバーヘッドにも重点を置いていない。
【００６２】
本発明を最も実用的で好ましい実施形態であると考えられるものについて図示し、説明してきた。しかしながら、新しい試みがそこからなされてもよく、明白な修正が当業者によってなされることは予想される。当業者はここに明確に図示または説明していない多くの配置及び変形を考案できるであろうが、それらは本発明の原理を具体化するものであり本発明の精神及び範囲に包含されることが十分に理解されるであろう。
【００６３】
本出願は、２００７年３月８日に出願された、"Scheduler Design for Heterogenous Traffic in B3G/4G Cellular Networks with Multiple Channels"と題する、米国仮出願番号第60/893,719号の利益を主張し、その内容は参照によりここに組み込まれている。
【図面の簡単な説明】
【００６４】
【図１Ａ】本発明による複雑性オーバーヘッドの低いＬＣＯスケジューラを採用したシステムブロック図の一例である。
【図１Ｂ】本発明による複雑性オーバーヘッドの低いＬＣＯスケジューリング機能を詳細に示したものである。
【図２】データに対して関心あるパラメータである速度、及び音声に対して関心あるパラメータであるパケット遅延及びパケットジッタを用いて、データ及び音声トラフィックを処理するＬＣＯスケジューリングプロセスのフロー図である。
【図３Ａ】先行技術による従来のスケジューリングを備えたシステムブロック図である。
【図３Ｂ】従来のスケジューリングモジュールの機能を示すブロック図である。
【図１Ａ】
2008289127.tif 000028
【図１Ｂ】
2008289127.tif 000029
【図２】
2008289127.tif 000030
【図３Ａ】
2008289127.tif 000031
【図３Ｂ】
2008289127.tif 000032
【外国語明細書】
2008289127.tif 000033
2008289127.tif 000034
2008289127.tif 000035
2008289127.tif 000036
2008289127.tif 000037
2008289127.tif 000038
2008289127.tif 000039
2008289127.tif 000040
2008289127.tif 000041
2008289127.tif 000042
2008289127.tif 000043
2008289127.tif 000044
2008289127.tif 000045
2008289127.tif 000046
2008289127.tif 000047
2008289127.tif 000048
2008289127.tif 000049
2008289127.tif 000050
2008289127.tif 000051
2008289127.tif 000052
2008289127.tif 000053
2008289127.tif 000054
2008289127.tif 000055
2008289127.tif 000056
2008289127.tif 000057
2008289127.tif 000058