(57)【要約】      （修正有）【課題】複数の送信リソースを共有するマルチアクセス通信システムにおいて、緊急性があるパケットを優先してスケジューリングする。【解決手段】さまざまなアクセスに関連するパケットを、緊急パケット（Ｑｕ）の第１のカテゴリと、非緊急パケットの第２のカテゴリ（Ｑｎ＿ｕ）とに分類する（１１０）。第１のスケジューリングに従って、第１のカテゴリのパケットをスケジューリング（１２０）し、これらのパケットに送信リソースを割り当て（１２５）、次いで、第２のスケジューリングに従って、第２のカテゴリのパケットをスケジューリングし（１３０）、これらのパケットに送信リソースを割り当てる（１３５）。【選択図】図１
2010050961.tif 000002
【特許請求の範囲】
【請求項１】
複数の送信リソースを共有するマルチアクセス通信システムにおいて、パケットをスケジューリングする方法において、
さまざまなアクセスに関連する前記パケットが、緊急パケット（Ｑｕ）の第１のカテゴリと、非緊急パケットの第２のカテゴリ（Ｑｎ＿ｕ）とに分類され（１１０）、
第１のスケジューリングに従って、第１のカテゴリのパケットをスケジューリング（１２０）し、これらのパケットに送信リソースを割り当て（１２５）、次いで、第２のスケジューリングに従って、第２のカテゴリのパケットをスケジューリングし（１３０）、これらのパケットに送信リソースを割り当てる（１３５）ことを特徴とする、方法。
【請求項２】
緊急特性または非緊急特性が、さまざまなユーザのサービスクラスに割り当てられており、パケットが属している前記クラスが緊急特性である場合、当該パケットが前記第１のカテゴリに分類され、そうでない場合、前記パケットが前記第２のカテゴリに分類されることを特徴とする、請求項１に記載のスケジューリング方法。
【請求項３】
パケットの有効期間（ＴＴＬ）が所定のしきい値（Ｔｈ）よりも短い場合、前記当該パケットが前記第１のカテゴリに分類されることを特徴とする、請求項１に記載のスケジューリング方法。
【請求項４】
前記システムの前記ユーザのさまざまなサービスクラスに対して、複数の異なるしきい値（Ｔｈ１，．．．，ＴｈＮ）が提供されており、あるサービスクラス（Ｃｎ）に属しているパケットが、当該パケットの有効期間（ＴＴＬ）が前記クラスに関連付けられている前記しきい値よりも短い場合、前記第１のカテゴリに分類されることを特徴とする、請求項３に記載のスケジューリング方法。
【請求項５】
パケットが、時間ウィンドウ全体について計算される平均スループットが所定のしきい値（ＲＴｈ）よりも大きいストリーム、に属している場合、当該パケットが前記第１のカテゴリに分類されることを特徴とする、請求項１に記載のスケジューリング方法。
【請求項６】
前記第１のスケジューリングおよび前記第２のスケジューリングが、同じパケットスケジューリング方法に従って実行されることを特徴とする、請求項１から請求項５のいずれかに記載のスケジューリング方法。
【請求項７】
前記同じスケジューリング方法が、「最大搬送波対干渉波比」タイプまたは「プロポーショナルフェアネス」タイプであることを特徴とする、請求項６に記載のスケジューリング方法。
【請求項８】
前記第１のスケジューリングおよび前記第２のスケジューリングが、個別のパケットスケジューリング方法に従って実行されることを特徴とする、請求項１から請求項５のいずれかに記載のスケジューリング方法。
【請求項９】
前記第１のスケジューリングが、「最早デッドライン優先」タイプのスケジューリング方法に従って実行され、前記第２のスケジューリングが、前記「最大搬送波対干渉波比」タイプのスケジューリング方法に従って実行されることを特徴とする、請求項８に記載のスケジューリング方法。
【請求項１０】
前記第１のスケジューリングが、「最早デッドライン優先」タイプのスケジューリング方法に従って実行され、前記第２のスケジューリングが、前記「プロポーショナルフェアネス」タイプのスケジューリング方法に従って実行されることを特徴とする、請求項８に記載のスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットをスケジューリングする方法に関し、より詳細には、マルチアクセス無線通信システムに関する。
【背景技術】
【０００２】
マルチアクセス通信システムでは、さまざまなユーザのそれぞれに個別の送信チャネルを提供することができるように、さまざまなユーザの間で送信リソースを共有することが可能である。
【０００３】
特に公知の手法は、ＴＤＭＡ（時分割多元接続）、ＦＤＭＡ（周波数分割多元接続）、およびＣＤＭＡ（符号分割多元接続）であり、これらの手法では、それぞれ、さまざまなユーザに時間間隔、周波数間隔、およびアクセス符号が割り当てられる。また、これらのアクセス制御手法を組み合わせる方法も知られている。例えば、ＯＦＤＭＡシステム（直交周波数分割多元接続）では、周波数分割に基づくアクセス（ＦＤＭＡ）と時間分割に基づくアクセス（ＴＤＭＡ）とを組み合わせている。このようなシステムにおいては、各ユーザには、各時間間隔に対して、自身のデータを送信することのできるＯＦＤＭ多重化方式の一連のサブキャリア（チャンク）が動的に割り当てられる。
【０００４】
特定の場合には、これら通信システムは、複数のサービス、例えば、ボイスオーバーＩＰ（ＶｏＩＰ）などのリアルタイムサービス、もしくは、異なるサービス品質（ＱｏＳ）プロファイルを示すデータを伝送するサービス、またはその両方を提供する。この場合、アクセス制御システムは、ユーザのさまざまなサービスから送信リソースへのアクセスを許可することもできる。
【０００５】
アクセス制御は、各ユーザに専用リソースを割り当てることによって実行することができる。あるいは、さまざまなユーザもしくはさまざまなサービス、またはその両方のデータパケットが、共通の送信リソースにアクセスするために競合する。例えば、セルラー通信システムにおいては、基地局は、データパケットをさまざまなユーザまたはＵＥ（ユーザ機器）、または実際にはさまざまなサービスに送信するための時間間隔（タイムスロット）、周波数、またはスペクトラム拡散シーケンス（spread spectrum sequence）のうちの１つ以上を共有することができる。
【０００６】
さまざまなユーザまたはサービスがリソースにアクセスする順序は、パケットスケジューラによって決定される。
【０００７】
パケットをスケジューリングするいくつかの方法は、従来技術において公知である。例えば、ＭＣＩ（最大搬送波対干渉波比またはＭａｘ  Ｃ／Ｉ）（Maximum Channel to Interference ratioまたはMax C/I）と称される方法、あるいはＰＦ（プロポーショナルフェアネス）（Proportional Fairness）と称される方法は、いずれも、チャネルの状態を監視すること（チャネル状態監視）が要求される。前者の方法では、最大の瞬間総スループットが得られるように、各送信間隔において、最良のチャネル状態を有する１人または複数のユーザにリソースを割り当てる。後者の方法では、最大のスループットという基準と、さまざまなユーザ間の公平性という基準との間でバランスを確保することが可能である。この方法では、平均して他のユーザよりも良好なチャネル状態を有するユーザは、長期的には高い平均スループットを達成することが保証される。
【０００８】
しかしながら、前述した２つのスケジューリング方法（ＭＣＩ、ＰＦ）は、さまざまなユーザのサービス品質（ＱｏＳ）の制約を考慮していない。本文書において、サービス品質という用語は、一般的に、データストリームの特定のパフォーマンスレベルの特性、例えば、バイナリスループット（binary throughput）、バイナリ誤り率またはパケット誤り率、最大レイテンシ、あるいはジッタ時間を意味するものと理解される。ＭＣＩスケジューリング方法では、さらに、特定の時間期間においてチャネル状態が良好ではないユーザが、その期間全体にわたりリソースへのアクセスを拒否される（ユーザリソース窮乏）（user starvation）ことが起こり得る。
【０００９】
パケットをスケジューリングする特定の方法は、特定のサービス品質制約に適合する試みにおいて提案されている。例えば、ＥＤＦ（最早デッドライン優先）（Earliest Deadline First）と称されるスケジューリング方法では、送信期限に近いパケットほど高い優先度を割り当てることによって、特定のアプリケーション（例えば、ＶｏＩＰ、ビデオストリーミング）によって要求されるリアルタイム制約を考慮する。ＥＤＦタイプのパケットスケジューリングアルゴリズムは、特許文献１に記載されている。
【００１０】
しかしながら、ＥＤＦスケジューリング方法には、瞬間的な総スループットが最大化されないという欠点があり、なぜなら、この方法の決定基準において、チャネルの状態に関する情報が考慮されず、さらに、システムの過負荷の場合に、満足のいく妥協的解決策が何ら提供されないためである。
【００１１】
ストリームのリアルタイム制約と、ユーザの瞬間的な総スループットの最大化とを同時に考慮するパケットスケジューリング方法は、非特許文献１に提案されている。頭字語ＭＬＷＤＦ（Modified Largest Weighted Deadline First）として公知のこのスケジューリング方法では、パケット送信遅延が、ある程度の確率のしきい値よりも小さいことが保証される。
【００１２】
ＭＬＷＤＦ方法では、リアルタイム制約を受けるストリーム（ＲＴ（リアルタイム）ストリームと称される）と、そのような制約を受けないストリーム（ＮＲＴ（非リアルタイム）ストリームと称される）とを同じシステムにおいて処理することが可能である。しかしながら、ＭＬＷＤＦ方法を実際に実施することは簡単ではないことが判明しており、なぜなら、パラメータ（遅延しきい値、スループットしきい値）の選択がシステムのパフォーマンスに相当に影響しうるためである。
【００１３】
ＲＴストリームとＮＲＴストリームを同時に扱うことのできる別のスケジューリング方法は、非特許文献２に記載されている。頭字語ＵＥＰＳ（Urgency and Efficiency based Packet Scheduling）として公知であるこの方法は、ＯＦＤＭＡシステムの枠組みの中で提案されている。この方法では、トラフィックの特性と、ネットワークにおいて特定の瞬間にアクティブである一連のユーザの特性とに依存する効用関数に基づいてパケットスケジューリング規則を実施する。この方法の場合にも、効用関数の選択によってシステムの有効性が大きく影響される。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許第２３０９２３号明細書
【非特許文献】
【００１５】
【非特許文献１】M. Andrews et al. entitled "Providing quality of service over a shared wireless link" published in IEEE Communications Magazine, vol. 39, No. 2, February 2001, pp 150-154
【非特許文献２】S. Ryu et al. entitled "Urgency and efficiency based packet scheduling algorithm" published in Proceedings of the Int'l Conf. On Communications, 2005, vol. 4, pp. 2279-2785
【発明の概要】
【発明が解決しようとする課題】
【００１６】
本発明の目的は、マルチアクセス通信システムのための、パケットをスケジューリングする方法であって、ユーザのＲＴストリームおよびＮＲＴストリームを同時に処理することができ、従来の方法よりも、トラフィック負荷特性を満足させることに関して良好なパフォーマンスを提供する一方で、パラメータの選択による影響が小さい方法、を提案することである。
【課題を解決するための手段】
【００１７】
本発明は、複数の送信リソースを共有するマルチアクセス通信システムにおいて、パケットをスケジューリングする方法によって定義される。さまざまなアクセスに関連するパケットは、緊急パケット（Ｑｕ）の第１のカテゴリと、非緊急パケットの第２のカテゴリ（Ｑｎ＿ｕ）とに分類され、第１のカテゴリのパケットは、第１のスケジューリングの処理、および、この第１のスケジューリングに従っての送信リソースの割当ての処理、の対象となり、次いで、第２のカテゴリのパケットは、第２のスケジューリングの処理、および、この第２のスケジューリングに従っての残りの送信リソースの割当ての処理、の対象となる。
【００１８】
第１の変形形態によると、さまざまなユーザのサービスクラスに緊急特性または非緊急特性が割り当てられており、パケットが属しているクラスが緊急特性である場合、そのパケットは第１のカテゴリに分類され、そうでない場合、そのパケットは第２のカテゴリに分類される。
【００１９】
第２の変形形態によると、パケットの有効期間（ＴＴＬ）が所定のしきい値（Ｔｈ）よりも短い場合、そのパケットは第１のカテゴリに分類される。システムのユーザのさまざまなサービスクラスに対して、複数の異なるしきい値（Ｔｈ１，．．．，ＴｈＮ）が提供されていることが有利であり、あるサービスクラス（Ｃｎ）に属しているパケットは、そのパケットの有効期間（ＴＴＬ）がそのクラスに関連付けられているしきい値よりも短い場合、第１のカテゴリに分類される。
【００２０】
第３の変形形態によると、パケットが、時間ウィンドウ全体について計算される平均スループットが所定のしきい値（ＲＴｈ）よりも大きいストリームに属している場合、そのパケットは第１のカテゴリに分類される。
【００２１】
第１の実施形態によると、第１および第２のスケジューリングは、同じパケットスケジューリング方法に従って実行される。
【００２２】
この場合、このスケジューリング方法は、「最大搬送波対干渉波比」タイプまたは「プロポーショナルフェアネス」タイプとすることができる。
【００２３】
第２の実施形態によると、第１および第２のスケジューリングは、個別のパケットスケジューリング方法に従って実行される。
【００２４】
この場合、第１のスケジューリングを、「最早デッドライン優先」タイプのスケジューリング方法に従って実行することができ、第２のスケジューリングを、「最大搬送波対干渉波比」タイプのスケジューリング方法に従って実行することができる。
【００２５】
あるいは、第１のスケジューリングを、「最早デッドライン優先」タイプのスケジューリング方法に従って実行することができ、第２のスケジューリングを、「プロポーショナルフェアネス」タイプのスケジューリング方法に従って実行することができる。
【００２６】
本発明のその他の特徴および利点は、本発明の好ましい実施形態を、添付の図面を参照しながら読み進めることによって明らかになるであろう。
【図面の簡単な説明】
【００２７】
【図１】本発明による、パケットをスケジューリングする方法を概略的に表している。
【図２Ａ】第１のタイプのシナリオにおける、公知のスケジューリング方法の各パフォーマンスと、本発明によるスケジューリング方法のパフォーマンスを示している。
【図２Ｂ】第２のタイプのシナリオにおける、公知のスケジューリング方法の各パフォーマンスと、本発明によるスケジューリング方法のパフォーマンスを示している。
【発明を実施するための形態】
【００２８】
本発明においても、複数のユーザ、もしくは複数のアプリケーション、またはその両方が共通の送信リソースにアクセスする、マルチアクセス通信システムの枠組み内での方式を採用する。本発明の代表的な例示的使用は、各送信間隔（ＴＴＩ）において、リソースがサブキャリアの間隔（周波数チャンク）によって構成されるＯＦＤＭＡシステムにおける使用である。しかしながら、本発明は、一般的には、さまざまなアクセスの間で送信リソースが共有され、各アクセスにおいてデータがパケットの形式において送信される、任意のマルチアクセス通信システムに適用することができる。
【００２９】
本発明の基礎をなす発想は、さまざまなパケットを、緊急パケットに対応する第１のカテゴリと、非緊急パケットに対応する第２のカテゴリとに分類することであり、第１のカテゴリのパケットは第２のカテゴリのパケットよりも高い優先度を有する。第１のカテゴリに属しているパケットは、第１のスケジューリング処理の対象であり、これらがスケジューリングされる順序において送信リソースが割り当てられる。その後、第２のカテゴリに属しているパケットが、第２のスケジューリングの主題を形成し、これらがスケジューリングされる順序において、まだ割り当てられていないリソースが割り当てられる。
【００３０】
図１は、本発明による、パケットをスケジューリングする方法を概略的に表している。
【００３１】
ステップ１１０において、さまざまなアクセスに関連するパケット、すなわち、さまざまなユーザのパケットもしくはさまざまなユーザを宛先とするパケット、または、さまざまなサービスに関連するパケット、またはその両方を、第１のカテゴリ（Ωｕによって表す）および第２のカテゴリ（Ωｎ＿ｕによって表す）に分類する。
【００３２】
上述した２つのカテゴリへのパケットの分類は、さまざまな方法において実行することができる。例えば、システムは、特定のサービスクラスに「緊急」特性をつねに割り当てることができる。その後、このようなサービスに属しているすべてのパケットは、「緊急」特性を継承し、第１のカテゴリに分類される。同様に、特定のサービスクラスを、最初から緊急特性を持たないものとみなすことができる。この場合、このようなサービスに属しているすべてのパケットは、つねに第２のカテゴリに分類される。
【００３３】
別のタイプの分類は、パケットに対して直接的に行われる。例えば、パケットを、それぞれの有効期間またはＴＴＬ（Time To Live）の関数として分類することができる。より詳細には、あるパケットの有効期間が所定のしきい値Ｔｈよりも短い場合、そのパケットは第１のカテゴリに属し、そうでない場合、そのパケットは第２のカテゴリに属する。より一般的な方式においては、さまざまなサービスクラスＣ１，．．．，ＣＮに対してさまざまなしきい値Ｔｈ１，．．，ＴｈＮを提供することが可能であり、この場合、クラスＣｎのパケットの有効期間がＴＴＬ≦Ｔｈｎである場合、そのパケットは第１のカテゴリに属し、そうでない場合、そのパケットは第２のカテゴリに属す。
【００３４】
しきい値Ｔｈ、またはさまざまなしきい値Ｔｈ１，．．，ＴｈＮを、最大ＴＴＬ値の割合に関連して表すことが可能である。さらに、しきい値Ｔｈは、適応的に決定する、または、さまざまなパケットのＴＴＬ値のヒストグラムに基づいて決定することも可能である。さまざまなサービスクラスに対していくつかのしきい値Ｔｈ１，．．，ＴｈＮが提供される場合、これらのしきい値は、これらのさまざまなクラスにおけるＴＴＬ値のヒストグラムを通じて同様に得ることができる。
【００３５】
別のタイプの分類では、パケットが属しているストリームの平均スループットが要求される。より詳細には、あるストリームが、所定のしきい値ＲＴｈよりも大きい平均スループット（時間ウィンドウ全体について計算される）を示す場合、そのストリームに属しているパケットは第１のカテゴリに分類される。
【００３６】
ステップ１２０において、Ωｕのパケットをスケジューリングし、ステップ１２５において、このスケジューリングに従ってこれらのパケットに送信リソースを割り当てる。ステップ１３０において、Ωｎ＿ｕのパケットをスケジューリングし、ステップ１３５において、まだ割り当てられていない送信リソースをこれらのパケットに割り当てる。
【００３７】
第１のカテゴリのパケットのスケジューリングと、第２のカテゴリのパケットのスケジューリングは、同じスケジューリング方法または個別のスケジューリング方法に従って実行することができる。
【００３８】
第１の実施形態によると、パケットの２つのカテゴリに対する２つのスケジューリング方法が同じである。例えば、サービス品質を考慮しないスケジューリング方法（例えば、ＭＣＩ方法またはＰＦ方法）を使用する。
【００３９】
第２の実施形態によると、２つのスケジューリング方法を、異なる方法として選択する。第１のカテゴリのパケットには、リアルタイム制約のみを考慮するスケジューリング方法（例えば、ＥＤＦ方法）を選択するのが有利である。したがって、このスケジューリングにおいては、緊急であるとみなされるパケットの間で、緊急性の階層を考慮する。逆に、第２のカテゴリのパケットについては、サービス品質制約とは無関係にシステムの総スループット（最大スループット）の最大化を目的とするスケジューリング方法（例えば、ＭＣＩ方法またはＰＦ方法）を有利に選択することが可能である。
【００４０】
図２Ａおよび図２Ｂでは、２つの異なるシナリオの場合における、ＰＦ方法、ＭＣＩ方法、ＭＬＷＤＦ方法、ＥＤＦ方法と、本発明によるスケジューリング方法（頭字語ＨＹＧＩＥＮＥとして表してある）の各パフォーマンスを比較することができる。図示した場合においては、本発明のスケジューリング方法は第２の実施形態に対応しており、第１のカテゴリのパケットに対してＥＤＦ方法を使用し、第２のカテゴリのパケットに対してＭＣＩ方法を使用する。しきい値Ｔｈは、４０ｍｓに固定されている。
【００４１】
本文書において想定されるマルチアクセス通信システムは、基地局と複数のユーザ機器（ＵＥ）とを備えているセルラーシステムであり、ユーザ機器はセル内にランダムかつ均一に分散している。各ユーザにおいて、データストリームは、リアルタイム（ＲＴ）タイプまたは非リアルタイム（ＮＲＴ）タイプである。
【００４２】
第１のシナリオにおいては、セルのユーザのデータストリームが単一のリアルタイムタイプのみであり、すなわち、図示した場合には、ボイスオーバーＩＰ（ＶｏＩＰ）、またはほぼリアルタイムのビデオ（ＮＲＴＶ）のいずれかであるものと想定されている。
【００４３】
第２のシナリオにおいては、セル内に、異なるタイプのリアルタイムデータストリームが共存することがあり、すなわち、図示した場合には、ＶｏＩＰストリームおよびＮＲＴＶストリームであるものと想定されている。特に明記しない限り、セル内のリアルタイムトラフィックは混合されている（ＶｏＩＰまたはＮＲＴＶ）。
【００４４】
図２Ａおよび図２Ｂは、ＰＦ、ＭＣＩ、ＭＬＷＤＦ、ＥＤＦの各スケジューリング方法と、本発明によるスケジューリング方法（ＨＹＧＩＥＮＥ）における、セルの最大トラフィック負荷（ユーザの数によって表してある）を示している。より詳細には、セルの最大負荷は、ユーザの９５％が満足しているときの最大ユーザ数として定義され、この場合、ＶｏＩＰサービスまたはＮＲＴＶサービスのユーザは、パケット誤り率が２％未満であり、スケジューラにおける伝送時間がそれぞれ５０ｍｓおよび１００ｍｓ未満である場合に満足するものとみなす。結果は、１００回以上の独立したシミュレーションを平均したものであり、各シミュレーションにおいて、機器の位置をランダムに選択した後、ネットワークの１００秒のアクティビティを実行する。新しい送信間隔（ＴＴＩ）それぞれにおいて、さまざまなユーザの送信チャネルの特性を新たに選択する。
【００４５】
図２Ａは、ＶｏＩＰサービスのユーザについては、ＥＤＦ方法と、本発明による方法によって、セル内で最大トラフィック負荷が得られることを示している。これに対して、ＮＲＴＶサービスのユーザについては、さまざまなスケジューリング方法の間のパフォーマンスの差は比較的小さく、最低の結果はＥＤＦ方法において得られている。
【００４６】
図２Ｂは、セル内にＮＲＴＶサービスユーザ（この場合には１００に固定されている）とＶｏＩＰサービスユーザとが同時に存在する場合、セル内の最大トラフィック負荷が、本発明による方法によって得られていることを示している。これに対して、最低の結果は、ＭＣＩスケジューリング方法において得られている。
【図１】
2010050961.tif 000003
【図２Ａ】
2010050961.tif 000004
【図２Ｂ】
2010050961.tif 000005
【外国語明細書】
2010050961000001.pdf