(57)【特許請求の範囲】
【請求項１】
パケット交換式のローカルエリアネットワークの単一の無線チャネルにおいて複数の端末間で伝送するための複数の一連のパケットをスケジューリングする方法であって、
複数の端末それぞれに伝送速度を割り当てること、
および
各端末が秒単位あるいは分単位にわたって等しい量の伝送時間を受け取るように、前記端末間で伝送するための前記一連のパケットをスケジューリングすることを含み、
各パケットに開始タグＳｋｆ＝ｍａｘ｛Ｖ（Ａ（ｔｋｆ）），Ｆｋ−１ｆ｝および終了タグＦｋｆ＝Ｓｋｆ＋Ｌｐ／（ｒｆ・Ｃｆ（ｔ））を割り当てることをさらに含み、
ただし、ｋは、ある特定の一連のパケットｆにおける前記パケットのシーケンス番号であり、
Ａ（ｔｋｆ）は、前記パケットの到達時刻であり、
Ｌｐは、前記パケットのビットサイズであり、
Ｖ（．）は、前記開始タグのための仮想時刻であり、
ｒｆは、基本伝送速度であり、
Ｃｆ（ｔ）は、現在の伝送速度である、
パケット交換式のローカルエリアネットワークの単一の無線チャネルにおいて複数の端末間で伝送するための複数の一連のパケットをスケジューリングする方法。
【請求項２】
前記ローカルエリアネットワークは、アドホック方式において動作する
請求項１記載の方法。
【請求項３】
前記ローカルエリアネットワークは、インフラストラクチャ方式において動作する
請求項１記載の方法。
【請求項４】
少なくとも１つの端末が全ての他の端末と異なる速度で送信しているように、前記複数の端末に異なる伝送速度を割り当てることをさらに含む
請求項１記載の方法。
【請求項５】
前記複数の端末のうちのいくつかは、移動端末である
請求項１記載の方法。
【請求項６】
前記割り当てられる伝送速度は、チャネルの品質による
請求項１記載の方法。
【請求項７】
誤りのないチャネルを介して送信している特定の端末が、誤りを起こしやすいチャネルを介して送信している別の端末よりも高い伝送速度を割り当てられる
請求項６記載の方法。
【請求項８】
前記基本伝送速度に対して前記現在の伝送速度を正規化することをさらに含む
請求項１記載の方法。
【請求項９】
最も小さな開始タグを有する特定のパケットを最初に送信するようにスケジューリングすることをさらに含む
請求項１記載の方法。
【請求項１０】
Ｅｆ（ｔ）＞０であるときに、前記一連のパケットが進んでおり、Ｅｆ（ｔ）＜０であるときに、前記一連のパケットが遅れているように、クレジットカウンタを一連のパケットそれぞれに関連付けることをさらに含み、ただし、ｔはタイムユニットである
請求項１記載の方法。
【請求項１１】
特定の遅れている一連のパケットによって放棄されたタイムユニットの数だけ特定の進んでいる一連のパケットのための前記クレジットカウンタをインクリメントし、一方、前記タイムユニットの数だけ前記特定の遅れている一連のパケットの前記クレジットカウンタをデクリメントすることをさらに含む
請求項１０記載の方法。
【請求項１２】
前記タイムユニットは、前記伝送速度に対して正規化された、送信されたバイトに関して表される
請求項１１記載の方法。
【請求項１３】
最大のクレジットカウンタを有する、選択された、進んでいる一連のパケットからのタイムユニットを、遅れている一連のパケットに譲ることをさらに含む
請求項１１記載の方法。
【請求項１４】
前記タイムユニットは、前記遅れている一連のパケットの正規化されたクレジットカウンタに比例して前記遅れている一連のパケットに譲られる
請求項１３記載の方法。
【請求項１５】
各端末内のチャネルの状態を推定し、前記端末が送信するためのパケットをスケジューリングするか否かを判定することをさらに含む
請求項１記載の方法。
【請求項１６】
スケジューリング機構は、ＩＥＥＥ８０２．１１ｅ標準規格に準拠したハイブリッドコーディネータで実装される
請求項１記載の方法。
【請求項１７】
パケット交換式のローカルエリアネットワークの単一の無線チャネルにおいて複数の端末間で伝送するための複数の一連のパケットをスケジューリングするシステムであって、
誤りのないチャネル上で、種々の速度で伝送する理想的なパケットフローを規定するように構成されるエラーフリーサービスモデルと、
進んでいるパケットフローおよび遅れているパケットフローを判定し、前記進んでいるパケットフローおよび前記遅れているパケットフローのための、それぞれ進みの量および遅れの量を判定するように構成される進みおよび遅れモデルと、
前記進んでいるパケットフローを犠牲にして前記遅れているパケットフローを補償するように構成される補償モデルと、
各端末が秒単位あるいは分単位にわたって等しい量の伝送時間を受け取るように、前記端末間で伝送するための一連のパケットをスケジューリングするための手段と
を備える、パケット交換式のローカルエリアネットワークの単一の無線チャネルにおいて複数の端末間で伝送するための複数の一連のパケットをスケジューリングするシステム。
【請求項１８】
チャネル推定モジュールと、
チャネルアクセスモジュールとをさらに備える
請求項１７記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は包括的には無線ローカルエリアネットワークに関し、より詳細には、そのようなネットワークにおいて送信するための一連のデータパケットをスケジューリングすることに関する。
【背景技術】
【０００２】
ローカルエリアネットワーク（ＬＡＮ）は比較的小さなエリアにわたる通信ネットワークである。大部分のＬＡＮは１つの建物あるいは一群の建物に限定される。しかしながら、ＬＡＮは、通信チャネルを用いて、インターネットのような他のネットワークに接続されることができる。ＬＡＮは、ワークステーション、パーソナルコンピュータ、プリンタ、娯楽装置、センサおよび電話のような端末装置を、あるエリアに限定して接続することができる。多数の異なるタイプのＬＡＮがあるが、イーサネット（登録商標）が最も一般的である。
【０００３】
無線ローカルエリアネットワーク（ＷＬＡＮ）は、無線伝送範囲内にある端末間において、無線チャネル上で情報を伝送する、媒体を共有する通信ネットワークである。ＩＥＥＥ８０２．１１はＷＬＡＮのための１つの通信標準規格である。O’Hara等による「IEEE 802.11 Handbook, A Designer's Companion」（IEEE Press, 1999）および「IEEE 802.11e/D5.0, Draft Supplement to Part 11: Wireless Medium Access Control(MAC) and Physical Layer(PHY) Specifications: Medium Access Control(MAC) Enhancements for Quality of Service(QoS)」を参照されたい。ＩＥＥＥ８０２．１１の媒体アクセス方法（ＭＡＣ）は自律分散的なアクセス制御（distributed coordination function：ＤＣＦ）と呼ばれ、搬送波感知多重アクセス／衝突回避（ＣＳＭＡ／ＣＡ）プロトコルを基にする。
【０００４】
ＩＥＥＥ８０２．１１無線ネットワークは２つの異なる方式：アドホック方式およびインフラストラクチャ方式で構成されることができる。アドホック方式では、通信範囲内の全ての無線端末が互いに直に通信することができる。本発明は、インフラストラクチャ方式およびアドホック方式の両方で動作する無線ＬＡＮに適用されることができる。ＩＥＥＥ８０２．１１ａ標準規格は、６、９、１２、１８、２４、３６、４８および５４Ｍｂｐｓの８つの伝送ビット速度を規定し、ＩＥＥＥ８０２．１１ｂ標準規格は１、２、５．５および１１Ｍｂｐｓの４つの速度を規定する。そのように物理層の伝送速度を高めることができる場合、端末は、信号対雑音比（ＳＮＲ）あるいはパケット誤り率によって測定される無線チャネルの品質に応じて、最も良い伝送速度を選択することができる。適切に用いられるとき、マルチレートＷＬＡＮは、スループットを大幅に改善し、通信を集中的に利用するマルチメディアアプリケーションを効率的に支援する。
【０００５】
端末間の一連のパケット、すなわち「パケットフロー」をスケジューリングすることに関連して、マルチレートＷＬＡＮは、ネットワークプロトコルを設計するための新たな難問を提起する。パケットスケジューリング、特にフェアキューイングは、スループットおよび遅延に関して、パケットレベルのサービス品質（ＱｏＳ）を提供し、遅延の影響を受けやすい応用形態およびスループットの影響を受けやすい応用形態の両方を可能にする。無線パケットスケジューリングは、無線ネットワーク内の場所による（location-dependent）チャネル誤りにも対処し、パケットフローを短時間の誤りバーストから保護する。場所による誤りは、端末が移動端末である場合に特に懸念される。
【０００６】
しかしながら、従来技術の無線フェアパケットスケジューリングは通常、全ての端末が単一の固定された伝送速度を有する場合を想定し、種々の端末が多数の速度を有する場合、すなわち少なくとも１つの端末が全ての他の端末とは異なる速度で送信している場合を考慮しない。結果として、シングルレートネットワーク用に設計されたフェアキューイング法は、８０２．１１ａ／ｂ／ｇ標準規格に基づくＷＬＡＮでは大幅なスループットの低下を被る。実際には、従来技術の公平性の考えでさえ正当であると評価することはできない。
【０００７】
無線フェアスケジューリングでは、パケットフローは、チャネル誤りがある場合に、理想的で、誤りのないチャネル状態と同等のＱｏＳに近づこうとする。この目的を果たすために、誤りを起こしやすいパケットフローの送信は時間的に延期され、一方、誤りのないフローは進む。これは、誤りのないチャネルを認識するフローのみが常時パケットを送信するので、実効的なチャネルスループットを大幅に改善する。
【０００８】
全てのフローが常時、誤りのないチャネルを認識するエラーフリーサービスと比べて、誤りを起こしやすいフローは時間的に遅れる可能性があり、誤りのないフローは短時間に進む。しかしながら、遅れているフローが延期された時間を補償するために、遅れているフローが誤りのないチャネルを認識するとき、これらの進んでいるフローはその将来の送信を遅らせる。
【０００９】
このように、進んでいるフローおよび遅れているフローはいずれも長時間にわたってその約定された速度、すなわちスループットで受信し、スループット、遅延および公平性に関する性能限界が、誤りを起こしやすいチャネルが存在する場合でも、長時間にわたって保持される。従来技術による設計では、競合するフロー間のフェアシェアリングのモデルおよび誤りを起こしやすいフローの補償のモデルは、スループットに関して規定される。すなわち、「公平性」は、長時間にわたって、全てのフローが概ね等しいスループットを経験することを意味する。
【００１０】
大まかに言うと、未処理のまま残されたフローは、ｆバイト／秒と定義される、「公平な」スループットのシェアを受ける。チャネル誤りが存在する場合の補償もスループットに基づく。
【００１１】
あるパケットフローｆの割り当てられた伝送速度がｒｆである場合には、フローｆは、以下の式によって与えられるように、速度ｒｆに比例した時間［ｔ，ｔ＋ΔＴ］中にサービスを受ける。
【００１２】
【数１】
0004667899.tif 000002
【００１３】
ただし、Ｃは全てのフローによって認識されるチャネル容量であり、Ｂは誤りを起こしやすいチャネルを経験することによって未処理のまま残された１組のフローを示し、ΔＴはある所定の時間増分である。
【００１４】
そのようなモデルはシングルレートＷＬＡＮの場合には適しているが、マルチレートＷＬＡＮの場合、フローが種々の速度を有し、単一のチャネル容量Ｃが存在しないので、そのモデルはうまく機能しない。代わりに、チャネル容量は、種々の端末に割り当てられる速度に応じて、時間とともに変化する。さらに、誤りを起こしやすいフローは不釣合いな量の時間およびチャネルリソースを消費するので、マルチレートネットワークにおいてフロースループットを規格化する結果として、著しく非効率的になり、マルチレートの物理層によって提供される利得が減少する。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
ＷＬＡＮ内の各端末が種々の時刻に種々の伝送速度を割り当てられる可能性がある、すなわち少なくとも１つの端末が全ての他の端末とは異なる速度で送信している場合には、その根本的な問題は、その補償モデルを改変して、無線ネットワークにおいてそのようなマルチレートオプションに対応することである。
【課題を解決するための手段】
【００１６】
本発明は、無線ローカルエリアネットワークにおけるデータパケットのためのマルチレート無線フェアスケジューリング（ＭＷＦＳ）法を提供する。本発明によるパケットスケジューラはマルチレート能力を利用して、最適な伝送速度を自動的に選択することにより、認識されたチャネル品質と一致させる。
【００１７】
ＭＷＦＳ法の重要な概念は、時間的なシェアに関して公平性および補償を定義し、未処理のまま残されたパケットフローが、長時間、たとえば秒単位あるいは分単位にわたって、伝送時間に関して公平なシェアを受けることを確実にすることである。既に述べたように、用語「公平性」は概ね等しいことを意味するが、この場合には公平性は、従来技術の場合のようなスループットの代わりに、時間に当てはまる。ＭＷＦＳ法は、パケットフローに対して、チャネル条件によって支配されるような劇的に異なるスループットを与えることにより、大きなスループット利得を達成する。
【００１８】
ＷＭＦＳ法は、従来技術のフェアスループットスケジューリング法と比べて、約１５９％の大きなスループット利得を達成することができる。
【００１９】
詳細には、システムおよび方法が、パケット交換式のローカルエリアネットワークの単一の無線チャネルにおいて、端末間で伝送するための一連のパケットをスケジューリングする。
【００２０】
そのローカルエリアネットワークは、アドホック方式あるいはインフラストラクチャ方式で動作することができる。１つの伝送速度が各端末に割り当てられる。その端末には移動端末を用いることができる。
【００２１】
種々の端末が、チャネルの品質に応じて、種々の伝送速度を割り当てられることができる。すなわち、誤りのないチャネルを介して送信している端末は、誤りを起こしやすいチャネルを介して伝送している端末よりも高い伝送速度を割り当てられる。
【００２２】
その際、各端末が、長時間にわたって概ね等しい量の伝送時間を受け取るように、端末間で伝送するための一連のパケットがスケジューリングされる。
【発明の効果】
【００２３】
本発明は、ＩＥＥＥ８０２．１１標準規格に基づくＷＬＡＮのために物理層マルチレート能力を利用するパケットスケジューリング方法を提供する。本方法によって用いられるモデルは、長時間にわたって、全ての端末に対して公平な時間シェアを確保する。誤りのないチャネルをうまく利用することにより、その方法は、従来技術のスケジューラと比べて、著しいスループット利得を達成する。その方法は、インフラストラクチャ方式において動作するＩＥＥＥ８０２．１１ｂ／ａ／ｇネットワークに基づくパケット交換式のＷＬＡＮのために設計されているが、スケジューラを、通常はＡＰに一緒に配置されるハイブリッドコーディネータに統合することにより、ＩＥＥＥ８０２，１１ｅフレームワークにおいて用いられることもできる。その方法は、チャネル推定値および伝送速度を推定するために用いられる過程とは無関係である。
【発明を実施するための最良の形態】
【００２４】
図１Ａに示されるように、本発明は、アクセスポイント１１０を介して、パケット交換式の無線ローカルエリアネットワーク（ＷＬＡＮ）１００内の一連のデータパケット１０１〜１０２、すなわち「パケットフロー」をスケジューリングするためのシステムおよび方法２００を提供する。詳細には、種々の端末１１１〜１１２が、割り当てられた異なる伝送速度で、１つの物理伝送チャネル１０５上でパケットを通信することができる。すなわち、少なくとも１つの端末が、全ての他の端末とは異なる伝送速度でパケットを送信している。
【００２５】
本発明人は、本発明のスケジューリング方法２００を、マルチレート無線フェアスケジューリング（ＭＷＦＳ）と呼ぶ。本発明による方法は、ＩＥＥＥ８０２．１１ａ／ｂ／ｇ／ｅ標準規格に基づくＷＬＡＮで用いられることができる。本質的に、その方法は、場所によるチャネル誤りが存在する場合に時間的な公平性を達成する。場所による誤りは、端末が移動端末である場合に特に問題である。
【００２６】
図１Ｂに示されるように、スケジューラ２００は３つのモデル、すなわちエラーフリーサービスモデル２１０と、補償モデル２２０と、進みおよび遅れモデル２３０とを用いる。またスケジューラは、チャネル推定モジュール２５０およびチャネルアクセスモジュール２６０も用いる。
【００２７】
エラーフリーサービスモデル２１０は、誤りのないチャネル上で、種々の速度で伝送する理想的なパケットフローを定義する。補償モデル２２０は、進んでいるフローを犠牲にして、遅れているパケットフローを補償する。進みおよび遅れモデル２３０は、そのエラーフリーサービスにおいて、どのパケットフローが、どの程度だけ進んでいるか、あるいは遅れているかを判定する。これは、短時間の誤りバースト、移動端末に起因する場所によるチャネル誤りおよびＷＬＡＮ内のチャネル競合の問題に対処する。
【００２８】
スケジューラ２００のための擬似コードが付録に与えられる。
【００２９】
チャネル推定モデル２５０はチャネルの品質を判定する。チャネルアクセスモジュール２６０は物理チャネル１０５へのアクセスを可能にする。
【００３０】
本発明による方法は、シングルレートネットワークのための従来技術の無線フェアスケジューリング（ＷＦＳ）と後方互換性がある。たとえば、Lu等による「Fair scheduling in wireless packet networks」（IEEE/ACM Transactions on Networking, August, 1999）を参照されたい。全てのパケットフローが同じ伝送速度を認識する場合には、全ての端末が同じスループットを有することになるので、本発明のＭＷＦＳ法は機能を落として、従来技術のＷＦＳに適合する。
【００３１】
本発明人は、本発明のＭＷＦＳ法を、ＩＥＥＥ８０２．１１ｂ／ａ／ｇ／ｅ標準規格に基づくＷＬＡＮに適用する。そこでは、誤りのないチャネルを介して送信している端末は、誤りを起こしやすいチャネルを用いる端末よりも高い伝送速度を割り当てられて、用いることができる。
【００３２】
時間的なシェアに基づく公平性とスループットシェアに基づく公平性との区別はマルチレートＷＬＡＮにおいて重要である。本発明のＭＷＦＳ法は、パケットフローに対して、チャネル条件によって支配されるような劇的に異なるスループットを与えることができる。しかしながら、全てのパケットフローが、長時間、たとえば秒単位あるいは分単位にわたって概ね同じ時間のシェアを受け取る。
【００３３】
ネットワークモデル
ＩＥＥＥ８０２．１１ｂ／ａ／ｇ／ｅ標準規格に基づくＷＬＡＮのインフラストラクチャ方式では、アクセスポイント（ＡＰ）１１０は、ＡＰ１１０の伝送範囲内に位置する端末１１１〜１１２のためのデータパケット１０１〜１０２の伝送を調整する。単一の無線チャネル１０５が、端末とＡＰとの間のアップリンクおよびダウンリンク両方の通信のために共有される。端末はＡＰを介して互いに通信する。３つ一組の表現｛端末、アップリンク／ダウンリンクフラグ、識別情報｝が各パケットのフローを指定する。
【００３４】
全ての端末およびＡＰが同じチャネルを共有する場合であっても、誤り率は、ＡＰに対する端末の場所に応じて変化する可能性がある。場所による誤りは、特に移動端末の場合に、フェージング、干渉、障害物などに起因する。
【００３５】
パケットの伝送に成功するとき、パケットのフローが誤りのないチャネルを認識すると言われる。そうではなく、パケットの伝送に失敗するとき、フローが誤りを起こしやすいチャネルを認識すると言われる。無線チャネル内の誤りは通常、短いバーストにおいて生じ、少数のパケット、たとえば１２個のパケットを送信するのにかかる短い時間、たとえば１秒よりもはるかに短い時間では大きな相関があるが、１秒間に何千ものパケットを伝送することができるときに、長時間にわたると無相関である。
【００３６】
厳密な誤りモデルについて何も仮定しないが、所与の時間Ｔｉの誤りの数が限られていること、すなわち１つのパケットフローｉが、所与の時間Ｔｉ内にｅｉ個以下のパケット誤りしか受けないものと仮定する。
【００３７】
本発明の根底をなすＭＡＣプロトコルは８０２．１１標準規格に準拠する。自律分散的なアクセス制御（ＤＣＦ）方式では、各データパケット伝送の前に、ＲＴＳ／ＣＴＳハンドシェークが行われ、その後、ＡＣＫパケットが返送される。ＰＣＦ方式では、各データパケット伝送の前に、ＡＰと端末との間でポーリングによる交換が実施される。
【００３８】
マルチレート無線フェアスケジューリング
本発明のＭＷＦＳ法は、シングルレートネットワークのために利用することができる従来技術のスループットを対象にした（throughput-oriented）公平性および補償モデルから逸脱する。ＭＷＦＳは時間的なシェアが等しいという概念を用いる。それゆえ、ＭＷＦＳ法は全スループットを大幅に改善することができる。
【００３９】
さらに別の利点として、ＭＷＦＳ法はシングルレートネットワークのための従来技術のＷＦＳと後方互換性がある。全てのフローが同じ伝送速度を認識する場合には、ＭＷＦＳ法は機能を落として、ＷＦＳ法に適合する。
【００４０】
エラーフリーサービスモデル
この節では、本発明によるマルチレート無線フェアスケジューリング方法のための基本的なスケジューリングモデルを説明する。簡単にするために、最初に、エラーフリーサービス、すなわち全ての端末が誤りのないチャネルを認識するサービスについて考えてみる。後の節では、誤りを起こしやすいチャネルのためのサービスについて説明する。
【００４１】
本発明によるモデルは既知の開始時フェアキューイング（ＳＦＱ）スケジューリング方法を改変したものである。Goyal等による「Start-time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks」（IEEE/ACM Transactions on Networking, Vol. 5, No. 5, pp.690-704, October 1997）を参照されたい。ＳＦＱでは、到達する各パケットは２つのタグ、すなわち開始タグおよび終了タグを割り当てられる。
【００４２】
具体的には、時刻Ａ（ｔｋｆ）に到達する、シーケンス番号ｋのパケットフローｆを有するパケットは、以下のように定義される２つのタグ、すなわち開始タグＳｋｆおよび終了タグＦｋｆを割り当てられる。
【００４３】
【数２】
0004667899.tif 000003
【００４４】
ただし、Ｌｐはそのパケットのビットサイズを示し、Ｖ（．）は、スケジューラにおいて現時点でサービスされているパケットの開始タグのための仮想時刻であり、フローｆの基本伝送速度はｒｆである。その際、ＳＦＱは最小開始タグを有するパケットフローを選択し、そのヘッド・オブ・ライン（ＨｏＬ）パケット、すなわち、直後に送信されることになるパケットを送信する。
【００４５】
本発明はＳＦＱをマルチレートＷＬＡＮに適合させる。パケットフローｆの場合、時刻ｔにおける現在の伝送速度はＣｆ（ｔ）である。この現在の速度は、基本伝送速度ｒｆに対して正規化されることができる。それゆえ、そのタグは本発明によって以下のように変更される。
【００４６】
【数３】
0004667899.tif 000004
【００４７】
ただし、Ｃｆは現在の伝送速度であり、他の変数は式（１）の場合に定義されたのと同じである。
【００４８】
それゆえ、開始タグおよび終了タグはいずれも現時点で割り当てられている伝送速度に対して正規化される。これにより、誤りのないチャネルを認識する、高い速度のパケットフローが、より高い伝送速度で送信できるようになる。
【００４９】
さらに、その方法は、遅れている各フローに対して時間的な公平性を提供する。各パケットにタグが割り当てられた後に、スケジューリングによって、最も小さな開始タグを有するフローｆｍｉｎが最初に送信できるようになる。上記のＭＷＦＳタギングの擬似コードは付録の関数ｅｎｑｕｅｕｅ（）において与えられる。
【００５０】
進み／遅れモデル
進みおよび遅れモデルは、進んでいるフローを犠牲にして遅れているパケットフローに対してどの程度の補償が必要とされるかを規定する。本発明によるＭＷＦＳ法では、本発明による公平な時間補償を確実にするために、その補償はタイムユニットに関して定義される。各フローｆは、現在のフローのステータスを指示するための関連するクレジットカウンタＥｆ（ｔ）を有し、たとえば、Ｅｆ（ｔ）＞０は、そのフローｆが進んでいることを指示し、クレジットカウンタＥｆ（ｔ）＜０は、そのフローが遅れていることを指示する。Ｅｆ（ｔ）＝０の場合には、そのフローは「スケジュールどおり」である。
【００５１】
あるフローが誤りを起こしやすいチャネルを経験しているとき、そのフローは他のフローに対してタイムユニットを譲り、結果として、そのフローは遅れているフローになり、他のフローが進んでいるフローになる。後に、遅れているフローが再び誤りのないチャネルを経験するとき、進んでいるフローはタイムユニットを遅れているフローに返し、遅れているフローはスケジュールを取り戻す。
【００５２】
本発明による設計は２つの原理を基にする。第１に、遅れているフローｇによって放棄されたタイムユニットが進んでいるフローｌによって用いられるときにのみ、進んでいるフローのためのクレジットカウンタがインクリメントされる。それと同時に、遅れているフローのクレジットカウンタが同じ量だけデクリメントされる。第２に、クレジットカウンタのタイムユニットは、パケットフローの伝送速度に対して正規化された、送信済みのバイトに関して表現される。すなわち、そのインクリメントは、Ｅｌ（ｔ）＝Ｅｌ（ｔ）＋Ｌｇ／Ｃｌ（ｔ）によって表されることができる。ただし、Ｌｐは進んでいるパケットフローによって送信されたパケットのサイズであり、Ｃｌ（ｔ）は進んでいるフローの送信の現在の伝送速度である。
【００５３】
本質的に、進みおよび遅れモデルは時間シェア、すなわち、延期されたものを補償する際に、進んでいるフローが将来にいくつのタイムユニットを放棄し、遅れているフローがいくつのタイムユニットを受け取るかを規定する。
【００５４】
補償モデル
２つのさらに別の問題に対処する必要がある。第１に、スケジューラは、進んでいるフローがデータパケットを送信するのを許されるか否か、あるいは延期された、遅れているフローを補償するために、現在のスケジューリングの機会が放棄されるべきであるか否かを判定する必要がある。第２に、スケジューラは、進んでいるフローによって現在のスケジューリングの機会が放棄されたが、多数の遅れているフローが存在する場合に、どの遅れているフローが送信するのを許されるかを判定する必要がある。
【００５５】
本発明は、遅れているフローを補償するためにグレースフルなサービス放棄モデルを用いる。ｒｆの基本伝送速度、クレジットカウンタＥ（ｉ）およびＥｍａｘ（ｉ）の最大の進みを有する、進んでいるパケットフローｉについて考えてみる。言い換えると、最大の進みを有するフローが、タイムユニットを遅れているフローに譲るために選択される。このフローｉは、それぞれｒｉ．Ｅ（ｉ）／Ｅｍａｘ（ｉ）およびｒｉ．（１−Ｅ（ｉ）／Ｅｍａｘ（ｉ））の伝送速度を有する、補償フローｉｃおよび伝送フローｉｔに階層的に分割される。
【００５６】
パケットフローｉが送信機会を割り当てられるとき、フローｉは、補償フローｉｃおよび伝送フローｉｔの間で機会を階層的にスケジューリングする。補償フローｉｃに属する全てのタイムユニットが、以下に説明されるように選択される、遅れているフローに譲られる。進みが減少するとき、補償フローｉｃのための伝送速度は線形に減少することに留意されたい。これは、進んでいるフローのためのサービスをグレースフルに低下させるという性質を持っている。
【００５７】
進んでいるフローが、そのヘッド・オブ・ラインパケットのための送信機会を放棄した後に、所与のタイムユニットにおいて送信するための遅れているフローを選択する必要がある。パケットサイズがＬｌであり、進んでいるフローの伝送速度がＣｌ（ｔ）である場合には、補償のために利用可能な時間は以下の式で表される。
ΔＴｌ＝Ｌｌ／Ｃｌ（ｔ）
【００５８】
マルチレートネットワークでは、タイムユニットΔＴｌを満たすために、遅れているフローが選択される態様が新たな問題を提起する。シングルレートネットワークのためのＷＦＳ法では、全てのフローに対して、固定されたタイムユニットおよび同じパケットサイズが想定される。それゆえ、進んでいるフローによって放棄されたユニットにおいて送信するために、任意の遅れているフローを選択することができる。
【００５９】
マルチレートの場合、これはもはや当てはまらない。実際には、選択された、遅れているフローからのヘッド・オブ・ラインパケットの送信は、利用可能なタイムユニットΔＴｌの一部のみになる可能性があるか、あるいはタイムユニットΔＴｌの長さよりもはるかに長くなる可能性がある。さらに、ＷＦＳ法によって用いられる、簡単な重み付けされたラウンドロビン（ＷＲＲ）を基にする補償は、マルチレートネットワークでは重みが整数ではない場合もあるので、適用することができない。
【００６０】
本発明による補償モデルは、伝送速度が異なり、パケットが任意のサイズであっても、遅れているフローの間のグレースフルな補償の特徴を維持する。
【００６１】
遅れているフローｉのクレジットカウンタがＥｉ（ｔ）である場合には、ｇｉ（ｔ）＝Ｅｉ（ｔ）／Σｊ∈Ｆ（ｔ）Ｅｊ（ｔ）に従って、全ての遅れているフローのためのクレジットカウンタが正規化される。ただし、Ｆ（ｔ）は時刻ｔにおける全ての遅れているフローを示す。
【００６２】
遅れているフローはそれぞれ、ｇｉ（ｔ）に比例して、タイムユニットに関して補償を受ける。これは、以下の動作で実施されることができる。
【００６３】
Ｌｇがヘッド・オブ・ラインパケットのサイズであり、Ｃｇ（ｔ）が現在の伝送速度であると仮定すると、遅れているフローｇからのヘッド・オブ・ラインパケットは、補償タグＬｇ／Ｃｇ（ｔ）・ｇｇ（ｔ）を割り当てられる。
【００６４】
その際、最も小さな補償タグを有する、遅れているフローが選択され、放棄された補償タイムユニットを受け取る。すなわち、本発明による補償モデルは、全ての遅れているフローの中で、公平に、すなわち概ね等しく補償タイムユニットを割り当てる。
【００６５】
実施態様
ＩＥＥＥ８０２．１１  ＭＡＣネットワークの場合に、本発明のＭＷＦＳ法は実施する上で多数の問題がある。
【００６６】
チャネル状態の推定および伝搬
受信している端末はパケット誤り率に関して最も正確な情報を有するので、本発明では、受信している端末において、チャネル状態、すなわち誤りがないか、あるいは誤りを起こしやすいかが推定される（２５０）。所与の瞬間に受信対象でない端末の場合、本発明は、ＤＣＦ方式ではＲＴＳ／ＣＴＳハンドシェークを、ＰＤＦ方式ではポーリングメッセージを用いて、チャネル状態を推定することができる。Bianchiによる「Performance analysis of the IEEE 802.11 media access protocol for wireless LANs」（Proceedings of ACM SIGCOMM'94, 1994）を参照されたい。チャネル状態を推定した後に、その端末はチャネル状態を、ポーリングパケットの一部としてＡＰに送出することができる。その際、ＡＰはそのポーリング状態を用いて、パケットを適切にスケジューリングすることができる。
【００６７】
アップリンクフローの処理
本発明によるＭＷＦＳ法は、ダウンリンクおよびアップリンク両方のフローに対してうまく機能する。アップリンクフローの場合、ＡＰは各端末を周期的にポーリングし、以下の情報：ＨｏＬパケットのサイズ、およびアイドル時間後にパケットフローが再び遅れる場合には、ＨｏＬパケットの到達時刻を収集する。
【００６８】
ＡＰは、各端末から伝送速度を入手することができる。これを果たすための詳細は、ＡＲＦの場合にはKamerman等による「WaveLAN II: A high-performance wireless LAN for the unlicensed band」（Bell Labs Technical Journal, pp. 118-133, Summer 1997）に記載されるのと同じようにすることができ、あるいは改良ＲＢＡＲの場合にはHolland等による「A rate-adaptive MAC protocol for multi-hop wireless networks」（Proceedings of ACM MOBICOM'01, 2001）を参照し、あるいはＯＡＲの場合にはSadeghi等による「OAR: A multi-rate Media Access Protocol for Wireless Ad Hoc Networks」（ACM Mobile Networking and Applications, 2003）を参照されたい。
【００６９】
評価
この節では、種々の条件下でＭＷＦＳ法の性能を評価するためのシミュレーション結果を説明する。基準となる従来技術のＷＦＳ法は、Holland等によって説明される方法である。その方法は、誤りのないチャネルおよび誤りを起こしやすいチャネルの両方の場合のパケットフローに対してスループット公平性およびスループット遅延限界を与える修正流体フェア（modified fluid fair）アルゴリズムを利用する。
【００７０】
そのシミュレーション設定は以下の通りである。図２〜図６に示されるシミュレーションでは、４つのタイプのトラフィック、すなわちＦＴＰソース、ＣＢＲソース、ポアソンソースおよびマルコフ変調ポアソン過程（ＭＭＰＰ）ソースが検討される。
【００７１】
伝送速度はＩＥＥＥ８０２．１１ｂ標準規格に従って２Ｍｂｐｓ、５．５Ｍｂｐｓおよび１１Ｍｂｐｓである。各フローのパケットサイズは変化することができる。本発明はよく知られている２状態離散マルコフ連鎖を用いてチャネル誤りをシミュレートし、パラメータｐｇおよびｐｅはそれぞれ、次のタイムユニットが誤りのないチャネルあるいは誤りを起こしやすいチャネルを経験することになる確率を表す。
【００７２】
それゆえ、誤りのないチャネルおよび誤りを起こしやすいチャネルの定常状態確率ＰＧおよびＰＥはそれぞれ、ＰＧ＝ｐｇ／（ｐｇ＋ｐｅ）およびＰＥ＝ｐｅ／（ｐｇ＋ｐｅ）によって与えられる。本発明は１ステップの予測を用いて、チャネルの現在の状態に基づいて近い将来のチャネル状態を推定する。これは、チャネル誤りが短い時間、たとえば数分の一秒にわたって相関が大きいという実態を利用する。他に明確に述べられない限り、各シミュレーションの実行は１００，０００タイムユニットにわたって続き、その結果は５０シミュレーション実行にわたって平均される。
【００７３】
誤りのないチャネルのスループット
この組のシミュレーションでは、本発明のＭＷＦＳ法の従来技術のＷＦＳ方法よりも優れたスループット改善を実証するために、誤りのないチャネルの６つのＦＴＰフローについて考える。各フローは比較のベースとして２Ｍｂｐｓの伝送速度を用いる。その際、そのシミュレーションをマルチレートネットワークに適合させて、フローＦＴＰ−１およびＦＴＰ−２は１１Ｍｂｐｓで送信し、フローＦＴＰ−３およびＦＴＰ−４は５．５Ｍｂｐｓを使用し、フローＦＴＰ−５およびＦＴＰ−６は２Ｍｂｐｓを使用する。また、種々のシミュレーションの場合に、フロー毎にパケットサイズのセットを変更する。
【００７４】
図２は、フロー当たりのスループットおよび全スループットを示す。それは、本発明によるＭＷＦＳ法が、マルチレート無線ネットワークにおいて、従来技術のＷＦＳ方法と比べて、１５９％の総スループットを達成することを示す。そのスループットは、全てのパケットフローが同じ伝送速度を用いるときには、ＷＦＳと同様である。フロー当たりでも、特に高い伝送速度を用いるフローでは著しいスループット改善が達成される。たとえば、各フローが２Ｍｂｐｓの基本伝送速度を用いる場合と比べて、フローＦＴＰ−１およびＦＴＰＯ−２の場合には５５０％、フローＦＴＯ−３およびＦＴＰ−４の場合には２７０％だけスループットが増加する。
【００７５】
本発明によるＭＷＦＳは、高い速度のパケットフローが低い速度のパケットフローの存在時に不利にされることのないように、全てのパケットフロー間で「公平に」時間を割り当てる。従来技術は、等しいスループットを達成するために、低い速度のフローに長い時間を与えなければならないので、高い速度のパケットフローの動作が激しく劣化する。本発明によるＭＷＦＳ法は、全パケットフローおよびフロー当たりの両方の場合に、大幅に高いスループットを達成する。
【００７６】
誤りのないチャネルの遅延
ここで、誤りのないチャネル条件下のＭＷＦＳ法のパケット遅延動作がさらに説明される。６つのフローあるいは「ソース」の到達過程は以下の通りである。２つのＭＭＰＰフローにおいて、変調過程は２つの状態オンおよびオフを有する連続マルコフ連鎖である。オンからオフへの遷移確率は０．９であり、状態オフからオンへの遷移確率は０．１である。パケットは、３．０の速度でポアソン過程にしたがって到達する。２．０のパケット到達速度を有する２つのポアソンフローも存在する。残りの２つのフローは、１ｍｓ毎にパケットを生成されるＣＢＲソースである。種々のフローに対するＭＷＦＳ法の遅延性能を測定するために、フローＭＭＰＰ−１、ポアソン−１、ＣＢＲ−１に基本伝送速度２Ｍｂｐｓで送信させ、他のフローに１１Ｍｂｐｓで送信させる。評価において用いられる判定基準は、フロー毎に、送信に成功したパケットの平均遅延Ｄｅｌａｙａｖｇと、最大遅延Ｄｅｌａｙｍａｘと、標準遅延偏差Ｄｅｌａｙｄｅｖと、平均バッファサイズＢｕｆｆｅｒａｖｇとを含む。
【００７７】
図３は、このシミュレーション結果を示す。１１Ｍｂｐｓフローによって経験される遅延は、いずれの方法の場合でも２Ｍｂｐｓよりも小さい。しかしながら、本発明のＭＷＦＳ法は、従来技術のＷＦＳ法と比べて、高い速度のフローの場合にかなり小さな遅延時間および小さなバッファサイズを達成する。ＭＷＦＳ法の場合、高い速度のフローによって経験される遅延は、低い速度のフローには影響を及ぼさない。これは、ＭＷＦＳ法が高い速度および低い速度のフローの場合に差別化されたサービスを提供する能力を実証する。
【００７８】
誤りを起こしやすいチャネルのスループット
このシミュレーションでは、誤りを起こしやすいチャネルの場合のＭＷＦＳ法の補償モデルの有効性が説明される。理想的には、ＭＷＦＳ法は、より高いスループットを達成するために時間的な公平性を保持し、遅れているフローに対してグレースフルな補償を確保する。提示を簡単にするために、４つのＦＴＰフローを有するシナリオについて考える。２つのＦＴＰフロー（ＦＴＰ−３、４）は２．０Ｍｂｐｓの基本伝送速度を使用し、他の２つのフロー（ＦＴＰ−１、２）は１１Ｍｂｐｓのより高い速度で送信する。これらのフローのチャネル誤りパターンは場所に依存し、２状態離散マルコフ連鎖によってモデル化される。ｐｅ＋ｐｇ＝０．１を設定することにより、フロー毎に、相関が大きなチャネル条件がエミュレートされる。
【００７９】
図４は、従来技術のＷＦＳ法および本発明によるＭＷＦＳ法の場合のスループットの結果を示す。ただしパケット誤り率は０％から３０％まで変化する。パケット誤り率が２０％に増加すると、全てのフローが同時に誤りを起こしやすくなる確率が増加するので、両方のスケジューリング方法の場合のスループットが減少する。しかしながら、ＭＷＦＳ法の全スループットはＷＦＳ法よりもかなり良好である。
【００８０】
図５は、時間的な公平性および本発明の補償モデルの有効性を示す。そこでは、フロー毎に獲得された、正規化された時間が測定される。チャネルに誤りがないとき、各フローは概ね等しい時間量１．０を獲得する。パケット誤り率が増加すると、フローによって獲得される時間の長さが減少し、それは、図４に示されるように、後に全スループットの減少に繋がる。しかしながら、全てのフローの長期的な時間シェアは依然として保持され、全てのパケットフローの場合に概ね等しい。これは、本発明による補償方法が有効であることを示す。パケット誤り率が２０％に増加する場合であっても、各フローによって獲得されるスループットおよび時間シェアはわずかしか減少しない。これは、ＭＷＦＳ法が依然として、フローを誤りから保護し、良好な全スループットを保持することができることを実証する。
【００８１】
誤りを起こしやすいチャネルのパケット遅延
さらに、パケット遅延への誤りを起こしやすいチャネルの影響を説明する。このシミュレーション設定では、フロー１および２は、速度１．０でパケットが到達するＭＭＰＰソースであり、フロー３および４は、０．５のパケット到達速度のポアソンソースである。速度１．０の２つのＣＢＲフローも、バックグラウンドトラフィックをエミュレートするために用いられる。ＭＭＰＰ−１、ポアソン−１およびＣＢＲ−１の場合の伝送速度は２Ｍｂｐｓに設定され、他の３つのフローは１１Ｍｂｐｓの伝送速度を用いる。
【００８２】
図５および図６はそれぞれＭＭＰＰフローおよびポアソンフローの場合のパケット遅延を示す。これらの図は、各フローによって経験される遅延が、チャネル誤り率が増加するとともに増加することを示す。ＷＦＳ法はスループット公平性を保持するので、高い速度のフローおよび低い速度のフローによって経験される遅延は概ね同じである。しかしながら、ＭＷＦＳでは公平な時間的なシェアが用いられるので、遅延性能は、低い速度のフローと高い速度のフローとで異なる。具体的には、高い速度のフロー、ＭＭＰＰ−２およびポアソン−２は、それに相当する低い速度のフローよりも際立って低い遅延しか経験しない。しかしながら、低い速度のフローはＷＦＳに匹敵する遅延性能を有する。これは、ＭＷＦＳ法が、高い速度のパケットフローが低い速度のパケットフローによって不利にされないように、あるいはさらに悪くなり、停滞することのないように、高い速度のフローおよび低い速度のフロー間に、ある一定の度合いのフロー分離を与えることができることを示す。
【００８３】
本発明が、例示として好ましい実施形態において説明されてきたが、本発明の精神および範囲内において、種々の他の改変あるいは変更がなされることができることは理解されたい。それゆえ、添付の特許請求の範囲の目的は、本発明の真の精神および範囲内に入るような全てのそのような変形および変更を網羅することである。
【００８４】
【数４】
0004667899.tif 000005
【数５】
0004667899.tif 000006
【図面の簡単な説明】
【００８５】
【図１Ａ】本発明によるマルチレート無線フェアスケジューラを含む通信システムのブロック図である。
【図１Ｂ】図１Ａのマルチレート無線フェアスケジューラのブロック図である。
【図２】従来技術のシングルレートフェアスケジューリングおよび本発明によるマルチレート無線フェアスケジューリングの場合の誤りのないチャネルのスループットを比較するグラフである。
【図３】本発明によるマルチレート無線フェアスケジューリングを用いる種々のパケットソースの場合の誤りのないチャネルのパケット遅延統計データの表である。
【図４】従来技術のシングルレートフェアスケジューリングおよび本発明によるマルチレート無線フェアスケジューリングの場合の誤りを起こしやすいチャネルのスループットを比較するグラフである。
【図５】従来技術のシングルレートフェアスケジューリングおよび本発明によるマルチレート無線フェアスケジューリングの場合のＭＭＰＰソースのためのパケット遅延を比較するグラフである。
【図６】従来技術のシングルレートフェアスケジューリングおよび本発明によるマルチレート無線フェアスケジューリングの場合のポアソンソースのためのパケット遅延を比較するグラフである。
【図１Ａ】
0004667899.tif 000007
【図１Ｂ】
0004667899.tif 000008
【図２】
0004667899.tif 000009
【図３】
0004667899.tif 000010
【図４】
0004667899.tif 000011
【図５】
0004667899.tif 000012
【図６】
0004667899.tif 000013