JP2005057757A - 無線データ・ネットワークにおける伝送をスケジューリングする方法および装置 - Google Patents

Abstract

【課題】 データの伝送における遅延の変動を削減する、データの伝送をスケジューリングする方法および装置を提供する。
【解決手段】 スケジューリング評価基準を、システム内の各モバイル端末に対するＴＣＰスループット・レートに応じて計算する。あるユーザに対するこの評価基準の相対的な値が、そのユーザからのデータ伝送をスケジューリングするのに使われる。その結果、ＴＣＰのタイムアウトが削減または回避され、スループットおよびシステム性能の予測可能性が増す。
【選択図】図５

Description

本発明は、無線データ伝送システムに関し、より詳細には、このようなシステムにおけるスケジューラの性能の向上に関する。

無線通信システムは、現在の通信においてますます不可欠な側面になりつつある。サービス品質およびエンド・ユーザの満足を保証するために、効率的な資源割振りおよび管理戦略が必要である。多人数のユーザが関わる無線データ・システムにおいて、ユーザに優先権を与え、そうしたユーザとの間の伝送をスケジューリングするのに、スケジューリング・アルゴリズムが使われる。時間の経過とともにユーザのチャネル条件が変化するこのようなシステムに対して、このようなスケジューリング・アルゴリズムは、所与の時間枠においてより優れたチャネル条件を有するユーザに優先権を与えることによって、チャネルの変化を利用し、同時に、ユーザ集団における公平性を保証する。

従来の無線ネットワークでは、主に音声トラフィックを搬送していたが、現在の無線ネットワークおよび次世代無線ネットワークでは、伝送制御プロトコル（ＴＣＰ）などのプロトコルを使用するデータ・アプリケーションの人気が増しているせいで、より一層データを中心とするものになりつつある。したがって、将来の無線ネットワークは、音声トラフィックおよびデータ・トラフィック両方に、より一層資源を効率的に割り振ることができるものでなければならない。しかし、このような効率性は、達成するのが困難な場合がある。というのは、データ・アプリケーションは、トラフィック特性およびサービス品質要件両方において、従来の音声アプリケーションとは根本的に異なるものだからである。この違いは、概して、音声アプリケーションが一般に、ネットワーク負荷および無線チャネル品質に関わらず一定の伝送速度を必要とする事実から生じる。このような音声アプリケーションにおける高信頼性通信は、概して、不利なチャネル条件を緩和するための出力制御によって達成される。これに対して、データ・アプリケーションでは、エンド・ユーザが認識する性能は、ネットワーク層のスループット、接続を開始する際のトランザクション時間、およびデータを伝送する際のトランザクション時間と密接に関連する。データ伝送のためのスループットおよびトランザクション時間は、両方とも、チャネル品質、ネットワーク負荷、および資源割振り（スケジューリング）戦略に依存する。

データ・アプリケーションは一般に、音声アプリケーションよりも遅延に対する耐性があり、長期間スループットの改善、およびより高いエネルギー効率を達成するために、遅延の限界増加を容認することができる。たとえば、ｅメール通信は、音声通信よりも、伝送における遅延および中断に対してはるかに鈍感である。インターネット・アクセスおよびファイル転送も、同様に、妥当な応答時間および妥当な平均スループットが保たれる限り、集中的な通信チャネルを許容することができる。さらに、音声装置と比較して、データ装置上で一般に利用可能なバッファリングが増加しているせいで、また、通信の実質的な一方向性のせいで、ストリーミング・データ・アプリケーションでさえ、音声通信より、データの中断に対してより優れた頑強性を示す。データ・トラフィックのバースト性（すなわち、伝送中のデータ・パケットが、バースト伝送される傾向にある）に加え、データ・トラフィックのこの相対的な遅延耐性により、限られたネットワーク資源のより高い効率性を達成するために、柔軟な伝送スケジューリング戦略が可能になる。

無線データ・システムの特定の要求を満たすために、いくつかの公知のスケジューリング戦略が、様々な条件に従ってパケット・データのスループットを最大限にするのに用いられている。このような戦略の１つが、異なるユーザの相対的なチャネル品質に基づいた、データ伝送のスケジューリングである。最も単純には、このような戦略は、その瞬間に最も高いチャネル品質を有するユーザをスケジューリングし、そうすることによって、システム全体のスループットを最大限にする。しかし、このような戦略は、条件の悪いユーザが伝送のためにスケジューリングされることを阻止する影響をもち、したがって、ユーザ集団に不公平性をもたらす可能性がある。

複数ユーザにおける、システム性能と公平性の間の許容可能なバランスを達成するように資源を割り振ることが重要であることが、広く認識されている。この目的を達成する公知のアルゴリズムが、たとえば、ＣＤＭＡ １Ｘ ＥＶ−ＤＯシステムにおいて使用される、比例公平アルゴリズム（Ｐｒｏｐｏｒｔｉｏｎａｌ Ｆａｉｒ ａｌｇｏｒｉｔｈｍ）である。単に、チャネル品質が瞬間的に最も高いユーザをスケジューリングするのではなく、このアルゴリズムは、公平なやり方でユーザをスケジューリングして、チャネル条件が相対的に不利なユーザも、チャネル品質の相対強度に比例して十分なデータ・スループットを受けることを保証する。比例公平アルゴリズムは、概して、チャネル品質が相対的なピークに近づいたユーザを、伝送のためにスケジューリングすることによって、公平性を達成する。その結果、システム内のユーザが多いほど、ユーザの少なくとも１人のチャネル条件がそのピーク値に近づくことが多くなるので、システム・スループットが向上する。

ＴＣＰを使用する無線ネットワークにおける従来の比例公平アルゴリズムの性能は、多くの点で有利であるが、このようなアルゴリズムはある欠点を有することを本発明者は理解している。具体的には、比例公平アルゴリズムは、公知であるように、ネットワーク内の他の層、たとえば、ユーザが認識する性能を非常に多くの場合定義するＴＣＰ層での公平性または効率を考慮するように設計されていない。ＴＣＰの主要な目的は、ネットワーク内の使用可能な帯域幅の効率的な使用を保証し、（データ・パケットの紛失を生じさせる）ネットワークの過負荷を防止することである。ＴＣＰネットワークは、パケット紛失が検出されると、ユーザの伝送速度を減少させてユーザの伝送を抑制することによって、こうした目標を達成する。このことは、概して、有線ＴＣＰネットワークにおいて容認可能である。というのは、パケットの紛失は、概してネットワークの輻輳を示し、したがって、このような抑制が適切だからである。しかし、無線ネットワークでは、パケット紛失または疑わしいパケット紛失（たとえば、ある特定の時間が経過した後、パケットが確認されない）は、必ずしもこのような輻輳の結果ではない。たとえば、パケットは、たとえば基地局内のスケジューラに送信されると、比例公平アルゴリズムなどのスケジューリング・アルゴリズムによって決定される、エンド・ユーザへの無線伝送を待つ間、キューの中で遅延を経験する場合がある。その後に続く、ある特定のモバイル端末に対するスケジューリング時間の間の遅延（スケジューリング間遅延）は、そのアルゴリズムが使う評価基準(metric)に従って変わる。この遅延の変動は、（たとえば、再伝送されるパケットをデータ・ストリームにインターリーブすることによって、伝送の遅延をさらに増加させ得る）ＨＡＲＱ（ハイブリッド自動再送要求）技術などの再伝送技術に依拠する無線ネットワークにおける、固有の遅延変動性によって悪化する。その結果生じる、累積的な遅延変動によって、データ伝送の中断を生じさせる疑わしいパケット紛失による、ＴＣＰのタイムアウトが起こり得る。

したがって、本発明者は、ネットワークのＴＣＰ層において比例的に公平であるとともに、データの伝送における遅延の変動を削減する、データの伝送をスケジューリングする方法および装置を発明した。この方法および装置は、システム内の各モバイル端末に対するＴＣＰスループットの関数である評価基準を計算する。あるユーザに対する、この評価基準の相対的な値は、そのユーザからのデータ伝送をスケジューリングするのに使われる。その結果、ＴＣＰのタイムアウトが削減または回避され、スループットおよびシステム性能の予測可能性が増す。

図１は、本発明を実装することができる無線通信システムの実施形態を示し、例示的には、データ・メッセージが、モバイル端末１０１へ、かつそこから伝送される。モバイル端末１０１は、アンテナ１０２に信号を送信することによって、他の通信ノード（たとえば、他のモバイル端末や従来の電話）と通信する。アンテナ１０２は、エア・インターフェース１０９に沿ってネットワーク１１５からモバイル端末１０１にデータを送信し、かつ、エア・インターフェース１０８に沿ってモバイル端末１０１からデータを受信し、そのデータをネットワーク１１５に送信するのにも用いられる。アンテナ１０２は、接続１１６を介して例示的な基地局１０３に接続され、基地局１０３は、接続１１７を介して例示的な基地局コントローラ（ＢＳＣ）１０４に接続される。無線システムは、例示的なＢＳＣ１０４などのＢＳＣを使っても使わなくてもよいことが、当業者には理解されよう。ＢＳＣ１０４は、接続１１８を介して移動交換局（ＭＳＣ）１０５に接続される。ＭＳＣ１０５は、一般に複数の基地局または基地局コントローラを制御し、他の構成要素の中でも、制御モジュール１１０および交換ネットワーク１１１を備え、こうした構成要素は、ともに、ネットワークの他の部分に制御信号を発行し、着信および発信音声メッセージ、ならびに着信および発信データ・メッセージが正しい宛先に届くように、そうしたメッセージを切り換えるように機能する。ＭＳＣ１０５は、たとえば、無線端末１０１と他の通信ノード、たとえばコンピュータ１２０との間のインターネット１１９を介したデータ通信を実現するために、通信経路１１２および１１３を介して、ＰＤＳＮ（パケット・データ・サービング・ノード）／ＩＷＦ（ネットワーク間接続機能）１０６に接続される。

モバイル端末１０１の１つが、別の通信ノードへの呼の接続を確立しようと試みると、ＭＳＣ１０５は、このような試みが行われていることを示すデータ・メッセージを、基地局１０３およびＢＳＣ１０４を介して受信する。データ・メッセージを受信すると、ＭＳＣ１０５は、モバイル端末の識別を調べ、被呼番号を調べ、ＰＤＳＮ／ＩＷＦ１０６への出トランクを選択する。ＭＳＣ１０５はまた、モバイル端末用の無線チャネルを選択し、選択した無線チャネルに同調するようモバイル端末に命令するために、セル・サイトにデータ・メッセージを送信する。モバイル端末からではなく、モバイル端末への呼の場合、ＭＳＣ１０５は、モバイル端末にページング・メッセージをブロードキャストするために、ＭＳＣ１０５によってサービスされるセル・サイトにデータ・メッセージを送信する。ＭＳＣ１０５はまた、あるセル・サイトから別のセル・サイトへのハンドオフを調整し、切断された呼に関連づけられた信号送信機能を制御する。

上述したように、スケジューリング・アルゴリズムは、エア・インターフェース１０９を介した、図１のコンピュータ１２０などの送信側から、図１のネットワーク内のモバイル・ユーザへの送信をスケジューリングするのに用いられる。このようなアルゴリズムは、たとえば、データが一時的に格納される、基地局におけるキューから各モバイル・ユーザへのデータ伝送用のタイム・スロットを割り当てる。再度図１を参照すると、このスケジューリング機能は一般に、例示的には、ＢＳ１０３またはＢＳＣ１０４内でコードを実行するコンピュータ・プロセッサ内の回路によって、ネットワーク１１５内で実装される。このようなスケジューリングは、ネットワーク１１５内のどの構成要素としても実装できることが、当業者には理解されよう。さらに、このようなスケジューリング・アルゴリズムにおいて必要な様々な計算は、１つの回路でも、別個の回路によって実施される別々の計算でも行うことができることも、当業者には理解されよう。

上述した、かつ当該分野において公知である、１つの例示的なスケジューリング・アルゴリズムが、比例公平アルゴリズムである。このアルゴリズムは、ユーザ特有のチャネル品質の相対ピークに近づいたときにそのユーザの伝送が起こるようなやり方で、ユーザをスケジューリングする。その結果、システム内のユーザが多いほど、ユーザの少なくとも１人のチャネル条件がそのピーク値に近づくことが多くなるので、システム・スループットが向上する。比例公平アルゴリズムに従ってユーザｉをスケジューリングするのに用いられるスケジューリング評価基準Ｍ_ｉ ^{（ＭＡＣ−ＰＦ）}［ｎ］は、以下の式（１）のように表すことができる。

上式で、ｎは、ユーザ伝送がスケジューリングされるタイム・スロットであり、Ｒ_ｉ［ｎ］は、測定されたタイム・スロットｎにおける、ユーザｉ向けの最大可能伝送速度、たとえば、ビット／秒であり、Ａ_ｉ［ｎ−１］は、最大でタイム・スロットｎ−１まで受信された伝送に基づいて計算された、ユーザｉの推定平滑平均スループット（繰り返しになるが、例示的にはビット／秒）である。ユーザｉに対する平均スループットＡ_ｉ［ｎ］は、たとえば以下の式（２）で計算される。

上式で、ωは、式２の別々の項に与えられる重みを調節するための、調整可能なパラメータであり、例示的には、ω＝１／１０００である。ユーザｉがスロットｎにおける伝送のためにスケジューリングされる場合、関数δ_ｉ［ｎ］＝１であり、ユーザｉがスロットｎにおける伝送のためにスケジューリングされない場合、δ_ｉ［ｎ］＝０である。比例公平スケジューリング・アルゴリズムは次いで、タイム・スロットｎにおける最大スケジューリング評価基準を有するユーザｉを、そのタイム・スロットにおける伝送のために選択する。選択されたユーザの伝送速度は、そのタイム・スロットにおいて選択されたユーザに対する、最大可能伝送速度とみなされる。

したがって、比例公平アルゴリズムは、式１で表されるようなスケジューリング評価基準を使用して、過去の伝送速度に部分的に基づいた、現在の推定スループットに対する現在の可能伝送速度の比率に基づいて、ユーザをスケジューリングする。したがって、この評価基準は、図１のユーザ１０１の１人など、そのユーザ自身の過去の伝送速度／チャネル条件と比較して、現在の伝送速度／チャネル条件が優れているユーザへの伝送に有利に働く。この評価基準は、しばらくの間スケジューリングされておらず、したがって平均スループットが他のユーザと比べて大幅に低下しているユーザにも有利に働く。したがって、比例公平アルゴリズムのこの実装では、各ユーザ１０１は、そのユーザのチャネル条件がその最高の状態に近づいたとき、またはユーザが、長い期間スケジューリングされておらず、データ伝送を受けていない場合、伝送用のタイム・スロットをようやく受け取る。ただし、各ユーザは伝送用のスロットを受け取るが、ある特定のユーザからの、その後に続く伝送の間の遅延は、他の要因の中でも、そのユーザのチャネル条件の変動に応じて大きく変わり得る。伝送遅延におけるこのような変動を、これ以降、スケジューリング間（ｉｎｔｅｒ−ｓｃｈｅｄｕｌｉｎｇ）遅延変動と呼ぶ。

上述したような比例公平アルゴリズムは、多くの点で望ましく、無線伝送のスケジューリングにおける重大な問題を解決するが、データを伝送するのに伝送制御プロトコル（ＴＣＰ）も使っているネットワークにおいて比例公平スケジューリング・アルゴリズムが使われると、重大な問題が起こることを本発明者は理解している。こうした問題は、一部には、無線スケジューリング・アルゴリズムと、ＴＣＰプロトコルの一部として用いられる、パケット紛失の検出および補償機構との相互依存のせいで起こる。

ＴＣＰプロトコルは、送信側からデータ・パケットを送信し、宛先から、そうしたデータ・パケットの受信の確認応答を受信するのに使われる上位層プロトコルである。図１を参照すると、ＴＣＰプロトコルは、パケットが、たとえば、コンピュータ１２０からユーザ１０１の１人に受け渡されることを保証する。この受渡しを確認するために、各パケットの受信の確認応答が、宛先ユーザ１０１からコンピュータ１２０に返送される。図２は、送信側とユーザの間のデータの流れを示し、ここで、ＴＣＰは、データ・パケットの受渡し、およびその受信の確認のために使われる。この図では、例示的に、インターネット２０２に接続されたコンピュータ・サーバである送信側２０１が、経路２１０に沿って、関連づけられたアンテナ２０７を有する基地局２０６に、データ・パケットを送信する。無線データ・ネットワークでは、たとえば、経路２１０は、ルータ２０３、ＩＷＦ２０４およびＭＳＣ２０５を超えるまたは通過する経路でよい。データ・パケットは、基地局２０６に届くと、例示的には基地局２０６に置かれたスケジューラが、モバイル端末２０８へのデータの伝送をスケジューリングするまで、着信データを一時的に保持するように設計されたキューに入る。伝送がスケジューリングされると、データは、経路２１２に沿って、無線でモバイル端末２０８およびエンド・ユーザ２０９（ここでは例示的に、ラップトップ・コンピュータ）に送信される。パケットの受信が成功すると、エンド・ユーザ２０９は、経路２１３に沿って送信側２０１に確認応答（ＡＣＫ）通知を送信することによって、応答する。

送信側２０１とエンド・ユーザ２０９の間の最も信頼性の高い伝送方法では、新しいデータ・パケットを送信する前に、各データ・パケットに対するＡＣＫパケットの受信を必要とするが、このことは、データのスループットを大幅に制限することになる。したがって、データの受信が成功している（すなわち、パケットの紛失がない）限り、ＴＣＰは次第に、エンド・ユーザからＡＣＫを受信する前に、送信「ウィンドウ」において送信することが可能なパケット数（送信側が送信を許可されるパケット数）を増やす。たとえば、最初に、ＴＣＰは、ウィンドウにおいてただ１つのパケットが送信されるようにすることができる。そのパケットに対するＡＣＫが受信されると、ＴＣＰは、２つのパケットに対してウィンドウの大きさを倍にすることができる。次いで、連続して受信される各ＡＣＫごとに、ＴＣＰはさらに、送信ウィンドウにおいて送ることが可能なパケット数を、送信側のスループットの制限まで、倍にすることができる。ＴＣＰプロトコルは、パケットが紛失したと判定されると、他の手順に従う。たとえば、パケットの受信の確認応答が、図２の宛先ユーザ２０９から特定の時間閾値までに受信されない場合、パケットは紛失したと判定される。この時間閾値は、概して、送信側２０１によってパケットが送信された時から、そのパケットに対するＡＣＫが送信側２０１によって受信される時間までの、予測される最大ラウンド・トリップ時間（ＲＴＴ）に基づく。このＲＴＴ閾値は、異なるシステム条件を可能にするように、また、確認応答を受信するのにかかる時間の変動の制限を許可するように、調節可能である。調節されると、（可能などの変動も考慮する）その時間閾値までに確認応答が受信されないどのパケットも、紛失したと判定される。

１つまたは複数のパケットが紛失したという判定が行われると、ＴＣＰは、この紛失を２通りの方法で補償する。第１に、このプロトコルは、送信側２０１に対して紛失したパケット（群）の再送信を要求し、第２に、プロトコルは、輻輳制御を開始する。従来の有線ネットワークにおいて、ほとんどのパケット紛失が、ネットワークの輻輳または過負荷の直接的な結果なので、ＴＣＰ輻輳制御が用いられる。したがって、一般に、ＴＣＰ輻輳制御は、送信側２０１からの送信を制限または抑制して、システム内のデータ・トラフィックを制限し、ネットワークにおける輻輳を削減することからなる。この抑制は、送信側２０１が所与の送信ウィンドウ中で送信することができるパケット数を削減することによって達成され、その結果、システムにおける全体のデータ・スループットを低下させる。公知のＴＣＰプロトコルの動作は、一般に、上記の説明で述べたよりもはるかに詳細であり、このような細部は、使用されるＴＣＰの特定のバージョンに応じて変わり得ることが、当業者には理解されよう。

したがって、ＴＣＰは、検出されたパケット紛失がネットワークの輻輳を示すものであると推測する。しかし、比例公平スケジューラを有する無線データ・ネットワークでは、ＴＣＰによって検出されるパケット紛失が、実際にはこのような輻輳の結果でない場合がある。実際には、検出された紛失は、現実のパケット紛失でさえない場合もある。そうではなく、検出されたこのような紛失は、あるパケットの受渡しにおける超過遅延によるものである場合がある。こうした遅延に寄与する主な要因の１つは、比例公平スケジューリング・アルゴリズムを使用した結果生じる、上述したスケジューリング間遅延の変動である。ＴＣＰ動作の上記の説明は、例示に過ぎない。上述したように、比例公平アルゴリズムは、他の要因の中でも、ユーザのチャネル条件に基づいて、ユーザへの伝送をスケジューリングする。チャネル条件は、（たとえば、ユーザの動きまたは環境上の影響のせいで）大幅に変わり得るので、その後のユーザへの伝送におけるスケジューリング間遅延も、大幅に変わり得る。したがって、パケットまたはパケットの部分は、比較的長い時間、ユーザへの伝送を、キューの中で待つ場合がある。したがって、パケットが送信側からユーザに届き、ユーザが送信側に確認応答を返送するのにかかる総ＲＴＴは、部分的には、このスケジューリング間遅延に基づいて、ただちに変化する。このＲＴＴが、確認応答を受信するためのＴＣＰのＲＴＴ閾値を超えると、ＴＣＰは、タイムアウトし、上述した再送信および輻輳制御手順を開始する。図３は、パケットが、実際には紛失していないのに、どのようにして、スケジューリング・アルゴリズムとＴＣＰプロトコルの間の対話が、紛失したパケットの検出を引き起こし得るかという例示的なフローを示す。この図では、ステップ３０１で、図２の送信側２０１がパケット１−１を送出する。１−１という表記は、第１のパケットの最初の送信であることを示す。例示の目的でのみ、表記１−２は、パケット１の２度目の送信（再送信）であることを示す。ステップ３０２で、パケット１−１は、たとえば、図２の基地局２０６にあるキューに入る。したがって、ボックス３０２ａに示すように、パケット１−１は、この時点で、キューの中にある唯一のパケットである。次に、ステップ３０３で、パケット１−１は、図２の基地局２０６によって、スケジューリングされ、図２のモバイル端末２０８に送信される。エンド・ユーザ２０９は、受信すると、パケット２の送信を要求するＡＣＫを用いて応答する。ステップ３０５で、パケット１−１に対するＡＣＫが送信側によって受信され、そうすることによって、パケット１の送信が成功したことが示されるので、ＴＣＰプロトコルは、送信側２０１用の送信ウィンドウを、例示的に２つのパケットに対して拡大する。このようにして、送信側２０１は、パケット２−１および３−１を送出する。ステップ３０７で、こうしたパケットは、基地局２０６にあるキューに入る。パケット１−１は、モバイル端末に既に送信されているので、ブロック３０７ａで示すように、パケット２−１および３−１だけが、この時点でのキューの内容である。

次に、ステップ３０８で、上述したスケジューリング間遅延によって引き起こされた遅延に直面し、この遅延は、パケット２−１の受信を遅らせ、その結果、送信側へのＡＣＫの返送も遅れる。この場合、例示的には、スケジューリング間遅延は、ＴＣＰのラウンド・トリップ時間閾値を超える十分な長さであり、したがって、ステップ３０９で、ＴＣＰがタイムアウトする。このタイムアウト条件の結果、ステップ３１０で、ＴＣＰは、パケット２および３がネットワーク輻輳のせいで紛失したと判定し、したがって、図２の送信側２０１用の送信ウィンドウを縮小することによって輻輳制御を行う。ステップ３１１で、送信側２０１は、ＴＣＰからの要求に応答してパケット２を再送信する。パケット２が送信されるのが２度目なので、このパケットを、パケット２−２と示す。ステップ３１２で、パケット２−２は、基地局２０６にあるキューに入り、したがって、この時点で、ボックス３１２ａに示すように、キューは、パケット２−１（パケット２の１度目の送信）、パケット３−１、および誤りのある冗長なパケット２−２を含む。このような冗長性は、さらなる輻輳制御につながり、したがって、システム・スループットの低下につながり得る。

当業者には明らかであるように、どのパケットがキューの中にあるかについての情報をＴＣＰが入手可能である場合、ＴＣＰのタイムアウトは防止することができる。しかし、基地局にあるキューおよびスケジューラは、ＴＣＰと、ネットワーク内の同じ層にない。図４は、図２の例示的なネットワーク、および、ネットワークの構成要素２０１〜２０９の間で使用される様々な例示的なプロトコル４０１〜４０５を示す。図４では、上述したように、ＴＣＰプロトコルは、送信側２０１からモバイル端末２０８およびエンド・ユーザ２０９にデータを送信するのに用いられる。このプロトコルを、線４０１で表す。ただし、他の公知のプロトコルが、ネットワークの異なる層において、ネットワーク内の他の構成要素間でのデータ転送を実現するのに用いられる。たとえば、ルータ２０３は、エンド・ユーザとの間の伝送用に、線４０２で表す公知のインターネット・プロトコル（ＩＰ）を使用する。同様に、ネットワーク間接続機能（ＩＷＦ）は、エンド・ユーザとの間の伝送用に、例示的には、線４０３で表すポイントツーポイント・プロトコル（ＰＰＰ）を使用する。無線ネットワーク自体の内部では、ＭＳＣとモバイル端末が、線４０４で表す無線リンク・プロトコル（ＲＬＰ）を用いて、制御信号およびデータを伝達する。最後に、基地局２０６とモバイル端末２０８は、メディア・アクセス制御（ＭＡＣ）層として知られる層を介して、たとえば、線４０５で表す公知のＩＳ２０００（ＵＭＴＳ）プロトコルを用いてデータを伝達する。このＭＡＣ層は、基地局キューおよびスケジューラ両方が置かれている層である。したがって、当業者には明らかであるように、ＭＡＣ層とＴＣＰ層の間のデータ転送は、すぐには利用可能でない。

ＴＣＰプロトコルを用いる無線データ・ネットワークにおいて起こる上記のスループットの問題は、比例公平アルゴリズムが、ＭＡＣ層のみでの公平性および効率を保証するために最適化されるせいで起こることを、本発明者は理解している。比例公平アルゴリズムは、公知のように、ユーザが認識する性能を非常に多くの場合定義するＴＣＰ層など、ネットワーク内の他の層での公平性または効率を考慮するように設計されていない。したがって、ＭＡＣ層以外の層での公平性に部分的に基づくスケジューリング・アルゴリズムを使うことが望ましいことを、本発明者は発見した。具体的には、本発明者は、ＴＣＰスループットに基づくスケジューリング・アルゴリズムを発明した。このようなアルゴリズムは、依然として比例的に公平であるとみなすことができるが、ＭＡＣ層スループットではなくＴＣＰスループットに基づいて、また、ＴＣＰ層での公平性の保証に基づいて、比例的に公平である。本発明の、ＴＣＰスループットに基づく比例的に公平なアルゴリズムを、これ以降、ＴＣＰ比例公平（ＴＣＰ−ＰＦ）アルゴリズムと呼ぶ。

式（１）を再度参照すると、式１は、無線伝送をスケジューリングするのに用いられる、従来の比例公平アルゴリズムにおけるスケジューリング評価基準を表し、項Ａ_ｉ［ｎ］は、最大でタイム・スロットｎまで、ユーザｉによって受信される平均スループットを表す。ただし、このスループットは、ＴＣＰ層でのスループットではなく、ＭＡＣ層でのスループットである。ＴＣＰ−ＰＦアルゴリズムに従って、ユーザｉをスケジューリングするのに用いられるスケジューリング評価基準Ｍ_ｉ ^{（ＴＣＰ−ＰＦ）}［ｎ］は、ＭＡＣ層のみでなくＴＣＰ層のスループットも考慮し、以下の式（３）のように表すことができる。

上式で、ｎは、ユーザ伝送がスケジューリングされるタイム・スロットであり、Ｒ_ｉ［ｎ］は、所望の伝送速度、たとえば、本明細書で説明する実施形態では、測定されたタイム・スロットｎにおける、ユーザｉに対する最大可能伝送速度、たとえば、ビット／秒である。適切などの伝送速度も、スケジューリング動作での使用に等しく有効であり得ることが、当業者には理解されよう。式３のΓ_ｉ［ｎ−１］は、最大でタイム・スロットｎ−１までスケジューリングされた伝送に基づいて、タイム・スロットｎのときに推定される、ユーザｉの平滑平均ＴＣＰスループットである。ＴＣＰスループットが、いくつかの変数、たとえば輻輳制御機構のダイナミクス、ラウンド・トリップ時間（ＲＴＴ）、ならびに、ＩＰ、ＰＰＰ、および上述した他のプロトコルなど、下位層プロトコルとの対話に依存するので、ＴＣＰスループット（Γ_ｉ［ｎ−１］）の式は、入手するのが困難である。ただし、ＴＣＰデータ伝送の期間が比較的長い場合、ＴＣＰスループットは、ａ）（上述した）輻輳制御送信ウィンドウの大きさの、ｂ）平均ＲＴＴ（すなわち、パケットの平均システム時間）に対する比率として厳密に近似される。パケットのシステム時間は、図２の送信側２０１などの送信側によってパケットが送信されたときから、そのパケットが、図２のユーザ２０９などのユーザによって受信されるまでにかかる時間である。輻輳制御送信ウィンドウは、式２のＭＡＣ層のスループットＡ_ｉに比例するとみなすことができる。というのは、より大きいＭＡＣスループットが、送信される多数のパケット、および送信側によって受信される確認応答へ変換され、その結果、ＴＣＰ輻輳ウィンドウがより一層増大するからである。したがって、ＴＣＰスループットは、以下の式（４）のように表すことができる。

上式で、Ａ_ｉ［ｎ−１］は、タイム・スロットｎ−１の間の、ユーザｉに対するＭＡＣ層スループットであり、Ｔ_ｉ［ｎ］は、ユーザｉの、時間ｎのときに推定される、パケットの平均システム時間である。したがって、式３のスケジューリング評価基準は、以下の式（５）のように書き表すことができる。

したがって、ユーザｉに対して、最大可能伝送速度Ｒ_ｉ［ｎ］、ＭＡＣ層スループットＡ_ｉ［ｎ−１］、およびユーザに対するパケットのシステム時間Ｔ_ｉ［ｎ］が既知であり、または厳密に推定される場合、ＴＣＰ−ＰＦアルゴリズムで使用する評価基準を推定することができる。ＭＡＣ層スループットは、式２によってすぐに利用可能であるが、パケットの全体の平均システム時間は、推定するのが困難である。というのは、システム時間は、エア・インターフェースを介したパケットの待機、スケジューリングおよび伝送時間、迂回中継ネットワーク内およびＴＣＰの送信側での処理の遅延およびバッファリングの遅延、ならびに有線ネットワーク内の伝送遅延を含むいくつかの要素の合計だからである。ただし、迂回中継ネットワークに関連するシステム時間の要素は、スケジューリング用キューにおけるキュー作成時間およびスケジューリング時間と比べて、比較的小さいと仮定することができ、したがって、こうした迂回中継ネットワークの要素は、無視することができる。パケットは、伝送用セグメントに分割されるので、パケットのシステム時間は、したがって、パケットの第１のセグメントがシステムに入ったときから、パケットの最後のセグメントがエンド・ユーザに送信されるまでにかかるシステム時間として近似することができる。したがって、パケットの全体の平均システム時間Ｔ_ｐは、以下の式（６）のように近似することができる。

上式で、Ｎ_Ｓは、キュー中で待機しているセグメントの数であり、Ｓは、現在サービスを受けているセグメントの、残っているサービス時間（すなわち、現在サービスを受けているパケットのセグメントのサービスを終わらせるために、サーバによって必要とされる時間）であり、

（以下、必要に応じて「Ｘ￣」と表記する場合がある。他の記号についても同様）は、パケット・セグメントの平均サービス時間であり、Ｖ￣は、あるセグメントへのサービス終了と、次の連続するセグメントのサービス開始との間の、サーバによって必要とされる平均時間であり、Ｋ￣は、パケット中の平均セグメント数であり、

は、キュー中のセグメントすべてを送信するのに必要な全体の平均時間である。項

は、

と表すことができ、この式において、ＭＡＣ層での平均キュー・サイズＱ_ｉは、平均ＭＡＣスループットＡ_ｉによって除算される。項

は、通常の場合のように、バッファ中のセグメントの平均数がＴＣＰパケットごとのセグメント数より大きい場合、無視することができる。さらに、最後の項Ｘ￣も、やはり通常の場合のように、システム内に多くのユーザがいる限り、他の項と比べて比較的小さいものとして無視することができる。

したがって、パケットの総システム時間は、ネットワークの無線部分における、パケットの全体のシステム時間によって厳密に近似することができ、以下の式（７）のように表すことができる。

上式で、Ａ_ｉは、（式（２）で計算される）平均ＭＡＣスループットであり、Ｑ_ｉは、ユーザｉに対する平均キュー・サイズである。システム内のユーザの人数Ｍが十分に多い場合、式７の、残りのサービス時間Ｓは、以下の式（８）ように推定することができる。

上式で、ρは、

で計算される利用率であり、λ_ｐは、１秒ごとのパケット数を測定単位とする、キューへのパケットの到着率であり、他の項は、上述した通りである。項Ｖ^２￣は、スケジューリング間隔の二乗の平均であり、これ以降、スケジューリング間隔の二次モーメントと呼ぶ。

したがって、ＴＣＰ−ＰＦアルゴリズム用の式５のスケジューリング評価基準は、以下のように書き表すことができる。

オンライン動作中にユーザ伝送をスケジューリングするために用いられる場合、平均ＭＡＣスループットは、Ａ_ｉ［ｎ−１］によって推定され、ＭＡＣの平均キュー・サイズＱ_ｉは、タイム・スロットｎにおける、平滑平均キュー・サイズＱ_ｉ［ｎ］によって、以下の式（１０）のように推定される。

上式で、ｑ_ｉ［ｎ］は、タイム・スロットｎのときの、ユーザｉに対する瞬間的なキュー・サイズであり、ωは、前述した因子と類似した、指数的な重みづけ因子であり、Ｑ_ｉ［ｎ−１］は、タイム・スロットｎ−１のときに計算される、ユーザｉに対する、平滑平均キュー・サイズである。さらに、オンライン動作用に用いられる場合、式９の平均スケジューリング間隔Ｖ_ｉ￣は、以下の式（１１）のように書き表すことができる。

上式で、αは、平均スケジューリング間隔が推定されるタイム・スケールを制御するのに使われる、０と１の間の調整可能なパラメータであり、

は、ユーザｉが最後にスケジューリングされてからの、タイム・スロットｎのときに測定される経過時間であり、Φ_ｉ ^ｊは、ｊ番目の伝送における、ユーザｉに対する過去のスケジューリング間隔の平滑平均である。

式（９）で使われる、スケジューリング間隔の二次モーメントＶ_ｉ ^２￣は、以下のように書き表すことができる。

上式で、βは、式（１１）の変数αと同様、スケジューリング間隔の二次モーメントが平均されるタイム・スケールを制御するのに用いられる、０と１の間の調整可能なパラメータであり、Σ_ｉ ^ｊは、過去のスケジューリング間隔の二次モーメントの平滑値である。式（１１）および（１２）で、αおよびβは、大きいスケジューリング間隔の瞬間的な変化とバランスの取れた、平均スケジューリング間隔の長期的な影響に適切な重みを与えるように調整することができる。このような調整の目標の１つは、長い待機時間を経験したパケットをもつユーザに優先権を与え、したがって、ＴＣＰのタイムアウトを回避するのを助けることである。好ましくは、αは、β（たとえば、β＝０．５）と比べて、比較的大きい（たとえば、α＝０．９）とすべきである。システムのダイナミクスに応じて等しく好ましい結果を提供するように、αおよびβに対して他の値を選択することもできることが、当業者には理解されよう。

式（１１）および（１２）においても、平均値Φ_ｉ ^ｊの、平滑化された過去の値、およびスケジューリング間隔の二次モーメントΣ_ｉ ^ｊは、スケジューリング判断が行われた後で更新され、それぞれ以下の式（１３）および式（１４）

および

のように表すことができる。上式で、φ_ｉ ^ｊは、伝送ｊにおける、ユーザｉに対するスケジューリング間隔（すなわち、そのユーザの伝送ｊ−１と伝送ｊの間に経過した時間）であり、Φ_ｉ ^ｊ−１およびΣ_ｉ ^ｊ−１は、それぞれ、スケジューリング間隔の平均値および二次モーメントの、ユーザｉに対するｊ−１伝送における、平滑化された過去の値である。

したがって、ＴＣＰ−ＰＦアルゴリズム用の、式９のスケジューリング評価基準は、以下の式（１５）のように書き表すことができる。

上式の項は、上述した通りである。式１５は、式３のＴＣＰスループットΓ_ｉに部分的に基づくが、式１５の全項は、ＭＡＣ層において既知であり、または、ＭＡＣ層で利用可能な情報に基づいて計算できることが、当業者には理解されよう。したがって、式１５のスケジューリング評価基準によって、ＴＣＰ層でのみ利用可能などの情報も必要とすることなく、ＴＣＰ比例公平によるやり方で、ユーザ向けの伝送をスケジューリングすることが可能になる。したがって、ＴＣＰスループットが向上し、スケジューリングの遅延およびＴＣＰのタイムアウトに関連する上述した問題が、実質的に排除される。

図５は、本発明の原理による、複数のモバイル・ユーザに対して伝送をスケジューリングする、例示的な方法のステップを示す。たとえば、図５のフロー図によって表されるステップは、例示的には、プロセッサ上で実行されるソフトウェアによって実施できることが、当業者には理解されよう。このようなプロセッサは、例示的には、ＭＳＣ、ＢＳまたは図１のネットワーク１１５の他のどの構成要素にも置くことができる。図５において、ステップ５０１で、スケジューリング判断が必要か、判定が行われる。判断が必要ない場合、スケジューリング用システムは、このような判断が必要になるまで待機する。判断が必要ある場合、次いでステップ５０２で、ユーザｉに対する最大可能伝送速度が決定される。次に、ステップ５０３で、式４〜１５に関連して上述したように、各ユーザｉに対するＴＣＰスループットが近似される。ＴＣＰスループットの個別の値を取得することは、実際には必要ないことが、当業者には理解されよう。そうではなく、式１５に示すように、近似されたＴＣＰスループットを構成する個々の変数を、計算し、スケジューリング評価基準で直接使うことができる。次に、ステップ５０４で、（ステップ５０２で決定された）各ユーザに対する最大可能伝送速度を、（ステップ５０３で近似された）各ユーザに対するＴＣＰスループットで割ることによって、各ユーザに対するスケジューリング評価基準が計算される。ステップ５０５で、全ユーザに対して計算された評価基準が比較され、計算された評価基準が最も高いユーザが、伝送のためにスケジューリングされる。最後に、ステップ５０６で、システム動作が継続しているかに関して判定が行われる。継続している場合、方法はステップ５０１に戻って、スケジューリング判断が必要か、判定する。必要ない場合、処理は、システム動作が再開するまで終了する。

上述した内容は、本発明の原理の例示に過ぎない。したがって、本明細書では明示的に説明もせず、示してもいないが、本発明の原理を実施するとともに本発明の精神および範囲内である様々な構成を当業者が考案できることが理解されよう。たとえば、本明細書において説明した実施形態では、無線ネットワークに言及したが、そうした実施形態における原理は、スケジューリングを用いて、ユーザとの間の伝送に優先順位をつける、有線ネットワークなどの他のどのネットワークにも等しく適用できることが、当業者には理解されよう。さらに、本明細書において使用したすべての例および条件に関する用語は、読者が本発明の原理を理解するのを助ける、教育的な目的のみを特に意図しており、このような具体的に説明した例および条件への限定ではないと解釈されたい。さらに、本発明の態様および実施形態ならびにその具体的な例を説明したすべての文章は、機能的な等価物を包含することを意図している。

無線通信システムの、従来技術の例を示す図である。 例示的な無線通信システムにおける、伝送制御プロトコル（ＴＣＰ）のデータ・パケットの、従来技術による移動を示す図である。 図２の無線通信システム内の基地局キューへの、かつそこからのパケットの例示的な流れを示す図である。 図２の無線通信システムにおいて使われる、一般的なプロトコルを示す図である。 本発明の原理による、例示的なスケジューリング処理を示すフロー図である。

Claims (10)

1. 基地局と複数のモバイル端末の間の、無線通信システムにおけるデータ伝送をスケジューリングする方法であって、
   前記複数のモバイル端末の各モバイル端末に対するスケジューリング評価基準の値を計算する工程であって、前記スケジューリング評価基準が、前記モバイル端末のそれぞれに対する伝送制御プロトコル（ＴＣＰ）スループットを表す工程と、
   前記スケジューリング評価基準の前記計算された値に応じて、前記基地局と前記モバイル端末の間の伝送をスケジューリングする工程とを特徴とする方法。
2. 前記スケジューリングする工程が、
   各モバイル端末ごとに、前記スケジューリング評価基準の前記計算された値を比較すること、および
   前記スケジューリング評価基準の値が最も高いモバイル端末をスケジューリングすることを特徴とする請求項１に記載の方法。
3. 前記スケジューリング評価基準が、前記無線通信ネットワーク内のメディア・アクセス制御層で利用可能な情報のみを用いて、各モバイル端末ごとに計算されることを特徴とする請求項１に記載の方法。
4. 前記スケジューリング評価基準が、
   前記ネットワーク内のキューにサービスを行う際の、スケジューリング間遅延と、
   前記スケジューリング間遅延の二次モーメントとの少なくとも一方の関数であることを特徴とする請求項１に記載の方法。
5. 前記スケジューリング評価基準が、
   前記ネットワーク内のキューの大きさと、
   前記ネットワーク内のユーザに関連する所望の伝送速度と、
   前記ネットワーク内のネットワーク・プロトコル層でのデータ・スループットとの少なくとも１つの関数であることを特徴とする請求項４に記載の方法。
6. 基地局と複数のモバイル端末の間の、無線通信システムにおけるデータ伝送のスケジューリングにおいて使うための装置であって、
   前記複数のモバイル端末の各モバイル端末に対するスケジューリング評価基準の値を計算する第１の回路を含み、前記スケジューリング評価基準が、前記モバイル端末のそれぞれに対する伝送制御プロトコル（ＴＣＰ）スループットを表し、さらに、
   前記スケジューリング評価基準の前記計算された値に応じて、前記基地局と前記モバイル端末の間の伝送をスケジューリングする第２の回路とを含むことを特徴とする装置。
7. 前記第１の回路および前記第２の回路が、同じ回路を備えることを特徴とする請求項６に記載の装置。
8. 各モバイル端末ごとに、前記スケジューリング評価基準の前記計算された値を比較する第３の回路をさらに含み、
   前記第２の回路が、前記スケジューリング評価基準の値が最も高いモバイル端末を伝送のためにスケジューリングする請求項６に記載の装置。
9. 前記スケジューリング評価基準が、
   前記ネットワーク内のキューにサービスを行う際の、スケジューリング間遅延と、
   前記スケジューリング間遅延の二次モーメントとの少なくとも一方の関数であることを特徴とする請求項６に記載の装置。
10. 前記スケジューリング評価基準が、
    前記ネットワーク内のキューの大きさと、
    前記ネットワーク内のユーザに関連する所望の伝送速度と、
    前記ネットワーク内のネットワーク・プロトコル層でのデータ・スループットとの少なくとも１つの関数であることを特徴とする請求項９に記載の装置。
    

Images