(57)【特許請求の範囲】
【請求項１】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、
前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行する第２転送ステップと、
を有することを特徴とするパケットスケジューリング方法。
【請求項２】
前記判定ステップでは下りサービス品質の判定を行い、前記第１および第２転送ステップでは下り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項１記載のパケットスケジューリング方法。
【請求項３】
前記判定ステップでは上りサービス品質の判定を行い、前記第１および第２転送ステップでは上り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項１記載のパケットスケジューリング方法。
【請求項４】
前記第２転送ステップは、
パケットの消失を検出した移動局が存在する場合には、当該移動局に関して優先してパケットの再送を実行するステップと、
パケットの消失を検出していない移動局に関しては、前記無線回線の物理的な品質の良い順にパケット転送を実行するステップと、
を有することを特徴とする請求項１〜３のいずれかに記載のパケットスケジューリング方法。
【請求項５】
前記第１転送ステップにおいて、前記サービス品質が満たされていない移動局に関しては、当該移動局が使用している無線回線の物理的な品質に基づいて、前記サービス品質が満たされている移動局の場合よりも雑音耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号化方式の少なくとも一方を使用してパケット転送を実行する、ことを特徴とする請求項１〜３のいずれかに記載のパケットスケジューリング方法。
【請求項６】
前記複数の移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップを更に有することを特徴とする請求項１記載のパケットスケジューリング方法。
【請求項７】
前記設定されたパケット転送レートの大きいフローから順にパケット転送を実行する転送ステップを更に有し、前記転送ステップでは、下り帯域を割り当て移動局へのパケット転送を実行する、ことを特徴とする請求項６記載のパケットスケジューリング方法。
【請求項８】
前記設定されたパケット転送レートの大きいフローから順にパケット転送を実行する転送ステップを更に有し、前記転送ステップでは、各フローの宛先移動局に対して上り帯域を割り当て、設定されたパケット転送レートでパケット転送を実行する、ことを特徴とする請求項６記載のパケットスケジューリング方法。
【請求項９】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、
前記サービス品質が満たされている移動局に関しては、当該移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップと、
前記設定されたパケット転送レートの大きいフローから順に、各フローの宛先移動局に関して、設定されたパケット転送レートでパケット転送を実行する転送ステップと、
を有することを特徴とするパケットスケジューリング方法。
【請求項１０】
前記判定ステップでは下りサービス品質の判定を行い、前記転送ステップでは下り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項９記載のパケットスケジューリング方法。
【請求項１１】
前記判定ステップでは上りサービス品質の判定を行い、前記転送ステップでは上り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項９記載のパケットスケジューリング方法。
【請求項１２】
前記下りサービス品質が満たされている移動局に関しては、
当該移動局が利用するサービスごとに吸収可能なパケット転送遅延の揺らぎ量を当該移動局から前記無線基地局に対して通知し、
前記無線基地局において当該移動局の利用するサービスごとにパケットの転送間隔を測定し、
前記吸収可能なパケット転送遅延の揺らぎ量と前記パケット転送間隔との差分を計算し、
前記差分が小さい移動局から順番に下り帯域を割り当ててパケット転送を実行する、
ことを特徴とする請求項２記載のパケットスケジューリング方法。
【請求項１３】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケット転送装置において、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定手段と、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定手段と、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行し、前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行するスケジューリング手段と、
を有することを特徴とするパケット転送装置。
【請求項１４】
前記判定手段は下りサービス品質の判定を行い、前記スケジューリング手段は下り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項１３記載のパケット転送装置。
【請求項１５】
前記判定手段は上りサービス品質の判定を行い、前記スケジューリング手段は上り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項１３記載のパケット転送装置。
【請求項１６】
前記スケジューリング手段は、前記サービス品質が満たされている移動局のうちパケットの消失を検出した移動局が存在する場合には、当該移動局に関して優先してパケットの再送を実行し、パケットの消失を検出していない移動局に関しては、前記無線回線の物理的な品質の良い順にパケット転送を実行することを特徴とする請求項１３〜１５のいずれかに記載のパケット転送装置。
【請求項１７】
前記スケジューリング手段は、前記サービス品質が満たされていない移動局に関しては、当該移動局が使用している無線回線の物理的な品質に基づいて、前記サービス品質が満たされている移動局の場合よりも雑音耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号化方式の少なくとも一方を使用してパケット転送を実行する、ことを特徴とする請求項１３〜１５のいずれかに記載のパケット転送装置。
【請求項１８】
前記複数の移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定手段を更に有することを特徴とする請求項１３記載のパケット転送装置。
【請求項１９】
前記スケジューリング手段は、下り帯域を割り当て、前記設定されたパケット転送レートの大きいフローから順に移動局へのパケット転送を実行する、ことを特徴とする請求項１８記載のパケット転送装置。
【請求項２０】
前記スケジューリング手段は、各フローの宛先移動局に対して上り帯域を割り当て、前記設定されたパケット転送レートの大きいフローから順にパケット転送を実行する、ことを特徴とする請求項１８記載のパケット転送装置。
【請求項２１】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケット転送装置において、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定手段と、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定手段と、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行し、前記サービス品質が満たされている移動局に関しては、当該移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定するレート設定手段と、
前記設定されたパケット転送レートの大きいフローから順に、各フローの宛先移動局に関して、設定されたパケット転送レートでパケット転送を実行するスケジューリング手段と、
を有することを特徴とするパケット転送装置。
【請求項２２】
前記判定手段は下りサービス品質の判定を行い、前記スケジューリング手段は下り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項２１記載のパケット転送装置。
【請求項２３】
前記判定手段は上りサービス品質の判定を行い、前記スケジューリング手段は上り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項２１記載のパケット転送装置。
【請求項２４】
前記下りサービス品質が満たされている移動局に関しては、  当該移動局が利用するサービスごとに吸収可能なパケット転送遅延の揺らぎ量を当該移動局から受信する受信手段と、
当該移動局の利用するサービスごとにパケットの転送間隔を測定する転送間隔測定手段と、
をさらに有し、
前記スケジューリング手段は、前記吸収可能なパケット転送遅延の揺らぎ量と前記パケット転送間隔との差分を計算し、前記差分が小さい移動局から順番に下り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項１４記載のパケット転送装置。
【請求項２５】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリングをコンピュータに実行させるためのプログラムにおいて、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、
前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行する第２転送ステップと、
を有することを特徴とするパケットスケジューリングプログラム。
【請求項２６】
前記判定ステップでは下りサービス品質の判定を行い、前記第１および第２転送ステップでは下り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項２５記載のパケットスケジューリングプログラム。
【請求項２７】
前記判定ステップでは上りサービス品質の判定を行い、前記第１および第２転送ステップでは上り帯域を割り当ててパケット転送を実行する、ことを特徴とする請求項２５記載のパケットスケジューリングプログラム。
【請求項２８】
前記第２転送ステップは、
パケットの消失を検出した移動局が存在する場合には、当該移動局に関して優先してパケットの再送を実行するステップと、
パケットの消失を検出していない移動局に関しては、前記無線回線の物理的な品質の良い順にパケット転送を実行するステップと、
を有することを特徴とする請求項２５〜２７のいずれかに記載のパケットスケジューリングプログラム。
【請求項２９】
前記第１転送ステップにおいて、前記サービス品質が満たされていない移動局に関しては、当該移動局が使用している無線回線の物理的な品質に基づいて、前記サービス品質が満たされている移動局の場合よりも雑音耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号化方式の少なくとも一方を使用してパケット転送を実行する、ことを特徴とする請求項２５〜２７のいずれかに記載のパケットスケジューリングプログラム。
【請求項３０】
前記複数の移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップを更に有することを特徴とする請求項２５記載のパケットスケジューリングプログラム。
【請求項３１】
前記設定されたパケット転送レートの大きいフローから順にパケット転送を実行する転送ステップを更に有し、前記転送ステップでは、下り帯域を割り当て移動局へのパケット転送を実行する、ことを特徴とする請求項３０記載のパケットスケジューリングプログラム。
【請求項３２】
前記設定されたパケット転送レートの大きいフローから順にパケット転送を実行する転送ステップを更に有し、前記転送ステップでは、各フローの宛先移動局に対して上り帯域を割り当て、設定されたパケット転送レートでパケット転送を実行する、ことを特徴とする請求項３０記載のパケットスケジューリングプログラム。
【請求項３３】
共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリングをコンピュータに実行させるためのプログラムにおいて、
前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、
前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、
前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、
前記サービス品質が満たされている移動局に関しては、当該移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップと、
前記設定されたパケット転送レートの大きいフローから順に、各フローの宛先移動局に関して、設定されたパケット転送レートでパケット転送を実行する転送ステップと、
を有することを特徴とするパケットスケジューリングプログラム。
【請求項３４】
前記判定ステップでは下りサービス品質の判定を行い、前記転送ステップでは下り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項３３記載のパケットスケジューリングプログラム。
【請求項３５】
前記判定ステップでは上りサービス品質の判定を行い、前記転送ステップでは上り帯域を割り当てパケット転送を実行する、ことを特徴とする請求項３３記載のパケットスケジューリングプログラム。
【請求項３６】
前記下りサービス品質が満たされている移動局に関しては、
当該移動局が利用するサービスごとに吸収可能なパケット転送遅延の揺らぎ量を当該移動局から受信するステップと、
当該移動局の利用するサービスごとにパケットの転送間隔を測定するステップと、
前記吸収可能なパケット転送遅延の揺らぎ量と前記パケット転送間隔との差分を計算し、前記差分が小さい移動局から順番に下り帯域を割り当ててパケット転送を実行するステップと、
を有することを特徴とする請求項２６記載のパケットスケジューリングプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は無線リンクを介してパケット通信を行う移動通信システムに係り、特に移動通信システムにおける無線基地局のパケットスケジューリング方法、パケット転送装置およびパケットスケジューリングプログラムに関する。
【０００２】
【従来の技術】
無線基地局が複数の移動局に対して時間スロットをそれぞれ選択し、共用の下りリンクを用いてパケットを送信する無線通信システムでは、移動局への時間スロットの割当方法として次のような方式が知られている。
【０００３】
１）3GPP（3rd Generation Partnership Project）のHSDPA（High Speed Downlink Speed Access）システムにおいて適用が検討されているラウンドロビン方式（"Physical Layer Aspects for High Speed Downlink Packet Access", 3GPP TR25.848. 2000）。この方式は全ての移動局に対して任意の順番で公平に時間スロットを割り当てるため、公平なスループットが実現できる。
【０００４】
２）同じくHSDPＡで検討されているMax C/I方式として知られるもの（"Physical Layer Aspects for High Speed Downlink Packet Access", 3GPP TR 25.848. 2000）。この方式では、無線基地局が何らかの手段によって各移動局との間の無線リンクのキャリア対干渉雑音電力比（ＣＩＲ：Carrier to Interference Ratio）を測定し、最もＣＩＲの良い移動局から順番にパケットを転送する。これにより無線基地局のセル全体のスループットを最大にすることができる。
【０００５】
３）ユーザがサービス品質を要求した場合を考慮したCBQ with CSDPS方式（Fragouliほか, "Controlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queuing with Channel-State-Dependent Packet Scheduling", INFOCOM '98.）。以下、この方式について、図１４を参照しながら簡単に説明する。
【０００６】
図１４（Ａ）は一般的な移動通信システムの概略的構成図であり、（Ｂ）は従来のパケット転送装置の一例を示すブロック図である。
【０００７】
図１４（Ａ）に示すように、移動局である通信装置０１は、無線基地局０３のセル内において無線リンク０２を介して通信可能であり、無線基地局０３は、優先リンク０４、パケットネットワーク０５および優先リンク０６を介して通信装置０７と接続されている。これによって、通信装置０１と通信装置０７との間でパケット通信が行われているものとする。なお、無線リンク０２は、無線基地局０３から通信装置０１へパケットを転送するための下りリンク１１と、逆に通信装置０１から無線基地局０３へパケットを転送する上りリンク１２からなる。
【０００８】
無線基地局０３にはパケット転送装置が設けられており、パケット転送装置は下りリンク１１へのパケット転送の順序を制御する。以下、ｎ個の移動局１〜ｎとの間でパケットをスケジューリングしながら転送する従来のパケット転送装置について説明する。
【０００９】
図１４（Ｂ）において、有線リンク０４側から受信したパケットは入力端子００１を通ってパケット分類部００３に入力する。パケット分類部００３は、フロー情報記憶部００２の情報を参照しながら、パケットの宛先である移動局を識別し、さらにパケットのヘッダ情報からパケットが属するサービスのフローを識別する。識別結果に従って、入力パケットは複数のキュー０２１〜０２６のいずれかに格納される。
【００１０】
キュー０２１〜０２６は移動局ごとにグループ化されている。たとえば、複数のキュー０２１〜０２２は移動局１のキューグループ０１１であり、複数のキュー０２３〜０２４は移動局２のキューグループ０１２であり、複数のキュー０２５〜０２６は移動局ｎのキューグループ０１３である。さらに、各グループ内のキューはサービスの優先度によって分けられている。例えば、入力されたパケットが移動局１宛で優先度が最も高いサービスのフローに属する場合には、キュー０２１に格納される。
【００１１】
スケジューラ００４には、移動局ごとの出力キューセレクタ０３１〜０３３と、これらキューセレクタ０３１〜０３３を選択する移動局間の出力キューセレクタ０３４とが設けられ、キュー０２１〜０２６のうちどのキューからパケットを取り出すかを決定する。こうして取り出されたパケットは出力端子００５から無線リンクを通して宛先移動局へ送出される。
【００１２】
スケジューラ００４において、まず、移動局間の出力キューセレクタ０３４は移動局毎の出力キューセレクタ０３１〜０３３を順次選択し、選択された移動局との間の無線リンクの品質が良いかどうかを判定する。無線リンク品質は、移動局へのパケット送信の際に行うRTS/CTS（Request to Send/Clear to Send）手順の成功/失敗によって評価することができる。成功すれば次の最大再送回数を１だけ増加させ無線リンク品質は良いと記憶し、失敗すれば次の最大再送回数を１だけ減少させて無線リンク品質は悪いと記憶する。
【００１３】
選択された移動局との無線リンク品質が良好であれば、当該移動局毎の出力キューセレクタはフロー情報記憶部００２の情報を参照して、該当する移動局内でパケット転送レートを満たさないキューがあるかどうかを判定する。もし満足しないキューが存在すれば、そのキューの先頭パケットを送信する。
【００１４】
当該移動局の全てのキューが転送レートを満足しているならば、全てのキューが適切な余剰帯域を配分されているかチェックする。一つでも適切な余剰帯域を配分されていないキューがあるならば、そのキューの先頭パケットを送信する。適切な余剰帯域を配分されている場合には、他の移動局にパケット転送レートを満たさないキューが存在するかをチェックし、存在しなければ以前送信したキューの次のキューの先頭パケットを送信する。他に所要のパケット転送レートを満たしていないキューが存在すれば、そちらを優先して処理することになる。
【００１５】
次に、パケット転送レートを満たさないキューの内、移動局の無線リンク品質が良いものがあるかをチェックし、全ての移動局の無線リンク品質が悪い場合には、以前送信したキューの次のキューの先頭パケットを送信する。転送レートを満たしておらずリンク状態の良い移動局が存在する場合には、その移動局における転送レートを満たしていないキューの先頭パケットを送信する。
【００１６】
いずれかのキューからパケットを送信した後、パケット送信によって変化したキュー長、スループット、全てのキューについて全体のスループットに対するサービス割合などを再計算し、フロー情報記憶部００２の情報を更新する。パケット送信によって全てのキューが空になったかどうかをチェックし、全て空になるまで上記動作を繰り返す。
【００１７】
このようにして、無線リンク品質の悪い移動局への送信を抑え、無線基地局がカバーするエリア全体のスループットの向上を図りつつ、利用するサービスに関して契約したパケット転送レートを保証し、さらに適切な余剰帯域を割り当てることが可能となる。
【発明が解決しようとする課題】
上記Max C/I方式のスケジューリングは、セル全体のスループットを最大化することができるが、無線リンク品質のみを考慮してパケット転送を行うために、サービス品質を要求するフローに対して所望の品質を達成できないという問題がある。
【００１８】
一方、CBQ with CSDPS方式のスケジューリングは、上述したように、利用するサービスに応じたパケット転送レートを保証しつつ、移動局間でなるべく公平に余剰帯域を割り当てようとする。
【００１９】
しかしながら、無線基地局と移動局の間の無線リンク品質がある基準値を超えてさえいればパケット転送を行うために、無線基地局の提供するセル全体のパケット転送レートが低く抑えられてしまう難点がある。
【００２０】
そこで、本発明の目的は、サービス品質を要求するフローに対しては所望の品質を満たしつつ、無線セル全体のスループットを最大化するパケットのスケジューリング方法、パケット転送装置およびパケットスケジューリングプログラムを提供することにある。
【００２１】
【課題を解決するための手段】
本発明によれば、移動局に対して所要のサービス品質を保証すべく、無線基地局は所要のサービス品質を満足しないフロー群に関しては、サービス品質を満足するフロー群よりも優先してパケット転送を行い、サービス品質を満足するフロー群に関しては無線リンク品質の良い移動局から順番にパケット転送を行う。
【００２２】
本発明の一実施態様によれば、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行する第２転送ステップと、を有することを特徴とする。
【００２３】
前記第２転送ステップは、パケットの消失を検出した移動局が存在する場合には、当該移動局に関して優先してパケットの再送を実行するステップと、パケットの消失を検出していない移動局に関しては、前記無線回線の物理的な品質の良い順にパケット転送を実行するステップと、を有することが望ましい。
【００２４】
さらに望ましくは、前記第１転送ステップにおいて、前記サービス品質が満たされていない移動局に関しては、当該移動局が使用している無線回線の物理的な品質に基づいて、前記サービス品質が満たされている移動局の場合よりも雑音耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号化方式の少なくとも一方を使用してパケット転送を実行する。
【００２５】
本発明の他の観点によれば、前記複数の移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップを更に有することを特徴とする。
【００２６】
本発明の別の観点によれば、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、前記サービス品質が満たされている移動局に関しては、当該移動局の各々が利用するサービスのフローごとに設定されるサービス品質と、宛先移動局と前記無線基地局との間の無線回線の物理的な品質と、に基づいて、各フローに対してパケット転送レートを設定する転送レート設定ステップと、前記設定されたパケット転送レートの大きいフローから順に、各フローの宛先移動局に関して、設定されたパケット転送レートでパケット転送を実行する転送ステップと、を有することを特徴とする。
【００２７】
本発明の一実施態様によれば、前記下りサービス品質が満たされている移動局に関しては、当該移動局が利用するサービスごとに吸収可能なパケット転送遅延の揺らぎ量を当該移動局から前記無線基地局に対して通知し、前記無線基地局において当該移動局の利用するサービスごとにパケットの転送間隔を測定し、前記吸収可能なパケット転送遅延の揺らぎ量と前記パケット転送間隔との差分を計算し、前記差分が小さい移動局から順番に下り帯域を割り当ててパケット転送を実行する、ことを特徴とする。
【００２８】
なお、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、他の無線基地局から前記無線基地局への移動局の移動を検出する検出ステップと、他の無線基地局から前記無線基地局へ移動した前記移動局に関して、移動後一定期間、優先的にパケット転送を実行する転送ステップと、を有することもできる。
【００２９】
また、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、ある移動局が無線基地局間を移動する際、少なくともパケットのヘッダ情報に基づいて当該移動局宛の移動制御パケットであることを検出するステップと、前記移動制御パケットに対しては優先してパケット転送を実行するステップと、を有することもできる。
【００３０】
また、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリング方法において、前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、ある移動局が無線基地局間を移動する際、少なくともパケットのヘッダ情報に基づいて当該移動局宛の移動制御パケットであることを検出するステップと、前記移動制御パケットに対しては、当該移動局が使用している無線回線の物理的な品質に基づいて、その他の移動局の場合よりも雑音耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号化方式の少なくとも一方を使用してパケット転送を実行するステップと、を有することもできる。
【００３１】
本発明によるパケット転送装置は、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケット転送装置において、前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定手段と、前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定手段と、前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行し、前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行するスケジューリング手段と、を有することを特徴とする。
【００３２】
本発明によるパケットスケジューリングプログラムは、共用下り無線回線を通して複数の移動局へパケットを送信し、マルチアクセス型の上り無線回線を通して前記複数の移動局からのパケットを受信する無線基地局におけるパケットスケジューリングをコンピュータに実行させるためのプログラムにおいて、前記複数の移動局の各々が利用するサービスごとに、対応するサービス品質が満たされているか否かを判定する判定ステップと、前記複数の移動局の各々について、前記無線基地局との間の無線回線の物理的な品質を測定する測定ステップと、前記サービス品質が満たされていない移動局が存在する場合には、当該移動局に関して優先してパケット転送を実行する第１転送ステップと、前記サービス品質が満たされている移動局に関しては、前記無線回線の物理的な品質の良い移動局から順番にパケット転送を実行する第２転送ステップと、を有することを特徴とする。
【００３３】
【発明の実施の形態】
以下、図１４（Ａ）に示す無線基地局０３におけるパケット転送装置を例にとって、本発明によるスケジューリング方法および装置について詳細に説明する。
【００３４】
（第１実施形態）
図１は、本発明の第１実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。本実施形態によるパケット転送装置は、有線リンク側の入力端子１０１と、無線リンク側の上り信号入力端子１０９および下り信号出力端子１１０とを有する。さらに、パケット転送装置は、パケット上り信号解析部１０２、フロー情報記憶部１０３、パケット分類部１０４、キューマネージャ１０５、送信済みバッファ１０６、再送用バッファ１０７、変調部１０８、複数のキュー１２１〜１２８、およびスケジューラ１３０を備える。
【００３５】
本実施形態では、複数のキュー１２１〜１２８を２つのグループに分ける。ここでは、複数のキュー１２１〜１２８は、サービス品質を満たしていないキューグループ１２０と、サービス品質を満たしているキューグループ１２５とに分けられ、所要サービス品質を満たしていないグループ１２０は複数のキュー１２１、１２２を含み、所要サービス品質を満たしているグループ１２５は複数のキュー１２６、１２７、１２８を含むものとする。後述するように、他のセルから移行してきた移動局ごとに、ハンドオーバ後の経過時間が所定時間を経過したか否かによって、２つのグループ１２０および１２５に分けることもできる。言い換えれば、複数のキュー１２１〜１２８の各々が複数のフローにそれぞれ対応する場合と、複数の移動局にそれぞれ対応する場合とがある。ここでは、それぞれが複数のフローに対応する場合を説明する。
【００３６】
サービス品質に関して２つのグループ１２０および１２５に分ける場合、スケジューラ１３０は、サービス品質を満たしていないキューグループ１２０から１つの出力キューを選択する出力キューセレクタ１３１と、サービス品質を満たしているキューグループ１２５から１つの出力キューを選択する出力キューセレクタ１３２と、出力キューセレクタ１３１および１３２のいずれかの出力を選択する出力キューセレクタ１３３とを含む。
【００３７】
入力端子１０１で有線ネットワークから入力された受信パケットは、パケット分類部１０４に入力する。上り信号解析部１０２は、入力端子１０９から入力した移動局からの上り信号を解析し、各移動局との間の無線リンクの品質情報に基づいてフロー情報記憶部１０３の情報を更新する。また、移動局へ送信したパケットの到達確認信号を移動局側から受信した場合には、送信済みバッファ１０６の該当パケットを削除する。
【００３８】
フロー情報記憶部１０３は、複数の移動局ごとに、利用するサービスの各フロークラスに関する情報を格納する。パケット分類部１０４は、入力されたパケットのヘッダを解析してフローを識別し、フロー情報記憶部１０３を参照して、対応するキューのキュー識別子とともにキューマネージャ１０５にパケットを渡す。
【００３９】
キューマネージャ１０５は、パケット分類部１０４から受け取ったパケットをキュー識別子に従い該当するキューに格納する。入力されたパケットは、フロークラスに設定されたサービス品質を満たしていないグループ１２０とサービス品質を満たしているグループ１２５とに属するクラス毎のキュー１２１〜１２８のいずれかに格納される。
【００４０】
スケジューラ１３０の出力キューセレクタ１３１、１３２はそれぞれの管理するグループから出力すべきキューを選択し、出力キューセレクタ１３３は出力キューセレクタ１３１および１３２のいずれかを選択する。
【００４１】
送信済みバッファ１０６は、スケジューラ１３０により選択されたキューからパケットが送信される時に当該パケットを一時的に格納する。当該パケットは、移動局から到達確認があれば上り信号解析部１０２によって削除される。再送用バッファ１０７は、移動局に到達できなかったパケットを一時的に格納しておく。
【００４２】
変調部１０８は、スケジューラ１３０で選択されたキューの先頭パケットを、後述するように無線リンク品質に応じて変調および誤り訂正符号化し、出力端子１１０から無線リンクに向けて出力する。
【００４３】
図２はフロー情報記憶部１０３の保持する情報の一例を示す模式図である。ここでは、各移動端末において、サービスクラスごとに、キュー識別子、パケット転送レート、サービス品質を満たしているどうかのフラグ(satisfied?)および再送フラグを保持し、かつ、端末ごとに無線リンク品質の情報としてのＣＩＲ(Carrier to Interference Ratio)を保持している。ここで、必ずしも移動局から無線基地局に対して明示的にＣＩＲのような下り回線のリンク品質を通知しなくても良く、移動局から所望の変調方式、誤り訂正符号、基地局からの送信パワーレベルを通知するようにしても良い。無線リンク品質の情報は、上り信号解析部１０２が無線リンク品質の変化を検知する毎に更新される。
【００４４】
このような構成を有するパケット転送装置は次のように動作する。有線ネットワーク側からパケット転送装置に入力されたパケットは、入力端子１０１を経て、パケット分類部１０４でヘッダ解析が行われる。ヘッダ解析の結果、パケットの宛先移動局とパケットの属するクラスが判明すると、パケット分類部１０４は、フロー情報記憶部１０３に問合せ、該当するクラスのキュー識別子とともにキューマネージャ１０５にパケットを渡す。
【００４５】
キューマネージャ１０５は、パケット分類部１０４からキュー識別子と共にパケットを受け取ると、キュー識別子に従い該当するキューにパケットを格納する。また、キューマネージャ１０５は、任意のアルゴリズムで適当にパケットを廃棄してもよい。例えば、特定のサービス品質の保証を要求しないフローに属するパケットは廃棄確率を高くするようにしてもよい。以上のような処理を経て、入力パケットはキュー１２１〜１２８のいずれかに格納される。
【００４６】
スケジューラ１３０は、キュー１２１〜１２８の中から送信するキューを選択し、その先頭パケットを変調部１０８に渡す。スケジューラ１３０は、パケットを変調部１０８に渡すと、フロー情報記憶部１０３の情報を更新し、再びキューを選択する。この処理を全てのキューが空になるまで繰り返す。スケジューラ１３０は、パケットを送信した後、当該パケットを送信済みバッファ１０６に格納する。入力端子１０９から入力された信号の内、上り信号解析部１０２でパケットの到達確認信号が検出された時に、送信済みバッファ１０６に格納された該当するパケットは削除される。不到達信号が検出されると、該当パケットは送信済みバッファ１０６から再送用バッファ１０７へ転送される。再送用バッファ１０７に格納されたパケットは、スケジューラ１３０によって任意のタイミングで再送される。
【００４７】
変調部１０８は、変調方式や誤り訂正符号化の強度を無線リンク品質に応じて決定し、誤り訂正符号化され変調された送信信号が出力端子１１０から無線リンクを通して宛先の移動局へ送信される。なお、変調方式・誤り訂正符号化の決定方法は任意で構わない。
【００４８】
次に、スケジューラ１３０で実行されるパケットスケジューリングの動作例を詳細に説明する。
【００４９】
（動作例１−１）
図３は、スケジューラ１３０のスケジューリング動作例１−１を示すフローチャートである。まず、出力キューセレクタ１３３は、サービス品質を満たしていないグループ１２０に属しているキューがあるかどうかをチェックする（ステップＢ０１）。もしあれば（ステップＢ０１のＹＥＳ）、出力キューセレクタ１３１は、サービス品質を満たしていないグループ１２０内の任意のキューを選択する（ステップＢ０６）。ここでのキュー選択方法は任意で構わない。そして選択したキューの先頭パケットを送信する（ステップＢ０７）。
【００５０】
サービス品質を満たしていないグループ１２０にキューがなければ（ステップＢ０１のＮＯ）、出力キューセレクタ１３２は、サービス品質を満たしているグループ１２５内のキューをＣＩＲが良い順に並べ替える（ステップＢ０２）。ただし、ここではＣＩＲを基準として並べ替えを行っているが、無線リンク品質の良さを表す指標であれば任意の基準で構わない。そして、最もＣＩＲが良い移動局へのパケットが格納されているキューの先頭パケットを送信する（ステップＢ０３）。
【００５１】
スケジューラ１３０は、パケットを送信した後、フロー情報記憶部１０３のパケット転送レートなどの全てのキュー情報を更新し、キュー情報の変化によってグループ変更されるべきキューについては、satisfiedフラグを書き換えてグループを変更する（ステップＢ０４）。全てのキューが空であるかをチェックし（ステップＢ０５）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＢ０１に戻る。
【００５２】
（動作例１−２）
図４は、スケジューラ１３０のスケジューリング動作例１−２を示すフローチャートである。まず、出力キューセレクタ１３３は、サービス品質を満たしていないグループ１２０に属しているキューがあるかどうかをチェックする（ステップＣ０１）。もしあれば（ステップＣ０１のＹＥＳ）、出力キューセレクタ１３１は、サービス品質を満たしていないグループ１２０内の任意のキューを選択する（ステップＣ０８）。ここでのキュー選択方法は任意で構わない。そして選択したキューの先頭パケットを送信する（ステップＣ０９）。
【００５３】
もしサービス品質を満たしていないグループ１２０にキューがなければ（ステップＣ０１のＮＯ）、出力キューセレクタ１３３は、再送用バッファ１０７に再送パケットが存在するかチェックする（ステップＣ０２）。もし存在するならば（ステップＣ０２のＹＥＳ）、再送パケットが存在するフローを持つ移動局をＣＩＲが良い順に並べ替え（ステップＣ０６）、最もＣＩＲの良い移動局宛に再送パケットを送信する（ステップＣ０７）。
【００５４】
もし、再送パケットが存在しなければ（ステップＣ０２のＮＯ）、出力キューセレクタ１３２は、サービス品質を満たしているグループ１２５内のキューをＣＩＲが良い順に並べ替える（ステップＣ０３）。なお、ここではＣＩＲを基準として並べ替えを行っているが、無線リンク品質の良さを表す指標であれば任意の基準で構わない。そして最もＣＩＲが良い移動局へのパケットが格納されているキューの先頭パケットを送信する（ステップＣ０４）。
【００５５】
スケジューラ１３０は、パケットを送信した後、パケット転送レートなどに関し全てのキュー情報を更新し、キュー情報の変化によってグループ変更されるべきキューについてはグループを変更する（ステップＣ１０）。全てのキューが空であるかをチェックし（ステップＣ１１）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＣ０１に戻る。
【００５６】
（動作例１−３）
図５は、スケジューラ１３０のスケジューリング動作例１−３を示すフローチャートである。まず、出力キューセレクタ１３３は、サービス品質を満たしていないグループ１２０に属しているキューがあるかどうかをチェックする（ステップＤ０１）。もしあれば（ステップＤ０１のＹＥＳ）、出力キューセレクタ１３１は、サービス品質を満たしていないグループ１２０内の任意のキューを選択する（ステップＤ１０）。ここでのキュー選択方法は任意で構わない。そして選択したキューの先頭パケットを送信する（ステップＤ１１）。
【００５７】
もしサービス品質を満たしていないグループにキューがなければ（ステップＤ０１のＮＯ）、サービス品質を満たしているグループのキュー処理が一巡したかチェックする（ステップＤ０２）。一巡した場合（ステップＤ０２のＹＥＳ）、移動局毎の出力キューセレクタ１３２は、サービス品質を満たしているグループ内のｎ個のキューをＣＩＲが良い順に並べ替える（ステップＤ０３）。ただし、ここではＣＩＲを基準として並べ替えを行っているが、無線リンク品質の良さを表す指標であれば任意の基準で構わない。また、それぞれのキューに対して、単位時間当たりパケット送信するデータ量をＣＩＲに従って重みをつけて設定する（ステップＤ０４）。例えば、ＣＩＲが最も良いものを１０ｋバイト／ｓと設定し、その他のキューは
１０ｋバイト／ｓ  ×（そのキューのＣＩＲ）/（最も良いキューのＣＩＲ）と設定することができる。次に、カウンタの値を１にリセットし（ステップＤ０５）、ステップＤ０６を実行する。ステップＤ０６では、その時のカウンタ値の順番のキューに設定されたデータ量分のパケットを送信する。ここではカウンタ値が１にリセットされているので、１番目のキューに設定されたデータ量だけパケット送信して（ステップＤ０６）、カウンタを１だけ加算する（ステップＤ０７）。
【００５８】
サービス品質を満たしたグループ内のキュー処理が一巡していない場合は（ステップＤ０２のＮＯ）、その時のカウンタ値の順番のキューに設定されたデータ量分のパケットを送信し（ステップＤ０６）、カウンタを１だけ加算する（Ｄ０７）。
【００５９】
スケジューラ１３０は、パケットを送信した後、パケット転送レートなどに関し全てのキュー情報を更新し、キュー情報の変化によってグループ変更されるべきキューについてはグループを変更する（ステップＤ０８）。全てのキューが空であるかをチェックし（ステップＤ０９）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＤ０１に戻る。
【００６０】
（動作例１−４）
スケジューラ１３０の動作例１−４では、移動局が利用するサービスに対して、パケットの転送遅延揺らぎの許容量の閾値が設定される。移動局から入力端子１０９を通して伝えられた信号が、上り信号解析部１０２の解析の結果、パケット転送間隔閾値を設定する信号であると識別された場合、上り信号解析部１０２がパケット転送遅延揺らぎの許容量の閾値をフロー情報記憶部１０３に記録しておく。
【００６１】
図６は、スケジューラ１３０のスケジューリング動作例１−４を示すフローチャートである。まず、出力キューセレクタ１３３は、サービス品質を満たしていないグループ１２０に属しているキューがあるかどうかをチェックする（ステップＥ０１）。もしあれば（ステップＥ０１のＹＥＳ）、出力キューセレクタ１３１は、サービス品質を満たしていないグループ１２０内の任意のキューを選択する（ステップＥ０８）。ここでのキュー選択方法は任意で構わない。そして選択したキューの先頭パケットを送信する（ステップＥ０９）。
【００６２】
もしサービス品質を満たしていないグループにキューがなければ（ステップＥ０１のＮＯ）、出力キューセレクタ１３３は、前パケット送信後の経過時間がフローに設定された閾値を超えているキューが存在するか否かをチェックする（ステップＥ０２）。もし存在するならば（ステップＥ０２のＹＥＳ）、該当キューを移動局のＣＩＲが良い順に並べ替え（ステップＥ０６）、最もＣＩＲの良い移動局宛に再送パケットを送信する（ステップＥ０７）。
【００６３】
もし、該当するキューが存在しなければ（ステップＥ０２のＮＯ）、出力キューセレクタ１３２は、サービス品質を満たしているグループ１２５内のキューをＣＩＲが良い順に並べ替える（ステップＥ０３）。ただし、ここではＣＩＲを基準として並べ替えを行っているが、無線リンク品質の良さを表す指標であれば任意の基準で構わない。そして最もＣＩＲが良い移動局へのパケットが格納されているキューの先頭パケットを送信する（ステップＥ０４）。
【００６４】
スケジューラ１３０は、パケットを送信した後、パケット転送レート、全パケット送信後の経過時間などに関し全てのキュー情報を更新し、キュー情報の変化によってグループ変更されるべきキューについてはグループを変更する（ステップＥ１０）。全てのキューが空であるかをチェックし（ステップＥ１１）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＥ０１に戻る。
【００６５】
なお、上述した動作例１−１〜１−４において、スケジューラ１３０が選択したパケットがサービス品質を満たしていないグループ１２０に属しているキューのパケットである場合、パケット誤り可能性を低下させるために、適切な変調方式や誤り訂正符号化方式を設定することもできる。すなわち、スケジューラ１３０が変調部１０８にパケットを渡す際、同時に、サービス品質を満たしていないグループ１２０に属しているキューのパケットである旨を通知する。これによって、変調部１０８は、その宛先移動局の無線リンク品質に基づいて、通常使用される変調方式よりも、熱雑音や干渉成分などの背景雑音に対する耐性の高い変調方式を用いるようにする。たとえば、通常であれば１６ＱＡＭ(Quadrature Amplitude Modulation)方式を選択する場合には、無線リンク品質に基づいてＱＰＳＫ(Quadrature Phase Shift Keying)方式を選択するなどである。あるいは、通常の誤り訂正符号方式よりも誤り訂正能力の高い誤り訂正符号を用いても構わない。たとえば、通常であれば符号化率１／２の符号化を行う場合には、無線リンク品質に基づいて符号化率１／４の符号化を行うなどである。このような背景雑音に対する耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号の両方を用いるようにしても良い。
【００６６】
（動作例１−５）
上述した動作例１−１〜１−４では、複数のキューがサービス品質を満足するグループ１２０と満足しないグループ１２５とに分けられた。
【００６７】
そのほかに、他の無線基地局から自無線基地局へ移動局が移行するハンドオーバＨＯ（Hand Over）後の経過時間が閾値を超えるか否かでグループ分けすることもできる。すなわち、複数のキュー１２１〜１２８は、それぞれ複数の移動局に対応しており、この場合、フロー情報記憶部１０３には各移動局のＨＯ後の経過時間がそれぞれ保持される。
【００６８】
図７は、スケジューラ１３０のスケジューリング動作例１−５を示すフローチャートである。スケジューラ１３０は、ＨＯ後５ｓｅｃ以内の移動局のキューにパケットが存在するか否かチェックする（ステップＧ０１）。ただし、ＨＯ後の経過時間の閾値は５ｓｅｃに限定されるものではなく、任意の値で構わない。もし無ければ（ステップＧ０１のＮＯ）、任意のキューを選択し（ステップＧ０６）、選択したキューの先頭パケットを送信する（ステップＧ０７）。ただし、ここでのキューの選択方法は任意の方法で構わない。
【００６９】
ＨＯ後５ｓｅｃ以内の移動局のキューにパケットが存在する場合（ステップＧ０１のＹＥＳ）、ＨＯ後５ｓｅｃ以内のグループ内のキューをＣＩＲが良い順に並べ替え（ステップＧ０２）、その中で最もＣＩＲの良いキューの先頭パケットを送信する（ステップＧ０３）。
【００７０】
スケジューラ１３０は、パケットを送信した後、パケット転送レートなどに関し全てのキュー情報を更新し、キュー情報の変化によってグループ変更されるべきキューについてはグループを変更する（ステップＧ０４）。全てのキューが空であるかをチェックし（ステップＧ０５）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＧ０１に戻る。
【００７１】
（第２実施形態）
図８は、本発明の第２実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。本実施形態によるパケット転送装置は、有線リンク側の入力端子２０１と、無線リンク側の上り信号入力端子２０９および下り信号出力端子２１０とを有する。さらに、パケット転送装置は、パケット上り信号解析部２０２、フロー情報記憶部２０３、パケット分類部２０４、キューマネージャ２０５、送信済みバッファ２０６、再送用バッファ２０７、変調部２０８、複数のキュー２２１〜２２３、およびスケジューラ２３０を備える。本実施形態では、複数のキュー２２１〜２２３が１つのキューグループ２２０を形成する。
【００７２】
入力端子２０１で有線ネットワークから入力された受信パケットは、パケット分類部２０４に入力する。上り信号解析部２０２は、入力端子２０９から入力した移動局からの上り信号を解析し、各移動局との間の無線リンクの品質情報に基づいてフロー情報記憶部２０３の情報を更新する。また、移動局へ送信したパケットの到達確認信号を移動局側から受信した場合には、送信済みバッファ２０６の該当パケットを削除する。
【００７３】
フロー情報記憶部２０３は、各移動局が利用するサービスのフロー毎にフローに関する情報を格納する。パケット分類部２０４は、入力されたパケットのヘッダを解析してフローを識別し、フロー情報記憶部２０３を参照して、対応するキューのキュー識別子とともにキューマネージャ２０５にパケットを渡す。
【００７４】
キューマネージャ２０５は、パケット分類部２０４から受け取ったパケットをキュー識別子に従い該当するキューに格納する。入力されたパケットは、複数のキュー２２１〜２２３のいずれかに格納される。スケジューラ２３０は、キュー２２１〜２２３のいずれかを選択し、選択したキューの先頭パケットを変調部２０８へ出力する。
【００７５】
次に、スケジューラ２３０で実行されるパケットスケジューリングの動作例を詳細に説明する。
【００７６】
（動作例２−１）
図９は、スケジューラ２３０のスケジューリング動作例２−１を示すフローチャートである。まず、スケジューラ２３０は、キュー処理が一巡したかチェックする（ステップＦ０１）。一巡した場合（ステップＦ０１のＹＥＳ）、スケジューラ２３０は、グループ２２０内のｎ個のキューをＣＩＲが良い順に並べ替える（ステップＦ０２）。ただし、ここではＣＩＲを基準として並べ替えを行っているが、無線リンク品質の良さを表す指標であれば任意の基準で構わない。また、それぞれのキューに対して、ＣＩＲに従って単位時間当たり送信するデータ量を重みをつけて設定する（ステップＦ０３）。例えば、ＣＩＲが最も良いものを１０ｋバイト／ｓと設定し、その他のキューは
１０ｋバイト／ｓ  ×（そのキューのＣＩＲ）/（最も良いキューのＣＩＲ）
と設定することができる。次に、カウンタの値を１にリセットし（ステップＦ０４）、１番目のキューを設定されたデータ量だけパケット送信し（ステップＦ０５）、カウンタを１だけ加算する（ステップＦ０６）。
【００７７】
キュー処理が一巡していない場合は（ステップＦ０１のＮＯ）、その時のカウンタの値の順番のキューに設定されたデータ量分のパケットを送信し（ステップＦ０５）、カウンタを１だけ加算する（ステップＦ０６）。
【００７８】
スケジューラ２３０は、パケットを送信した後、パケット転送レートなどに関し全てのキュー情報を更新する（ステップＦ０７）。全てのキューが空であるかをチェックし（ステップＦ０８）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＦ０１に戻る。
【００７９】
このように、無線リンクの品質に応じて、単位時間あたり転送可能なパケット量の重み付けをおこなうことにより、無線リンク品質の劣る移動局に対して継続的に帯域の割り当てが行われないという事態を防止することができる。
【００８０】
（動作例２−２）
動作例２−２では、図８に示す複数のキュー２２１〜２２３の１つを移動制御パケット用キューとして設定しておく。パケット分類部２０４は、パケットの送信元アドレスが局所的な位置登録局である場合あるいはパケットのヘッダに移動制御パケットであることを示す識別子がある場合には、その情報に基づいて入力パケットを移動局宛の移動制御パケットであると識別する。移動制御パケットである場合には移動制御パケット用キューに格納され、それ以外のパケットである場合には、移動局とフローとの組合せに従って、その他いずれかのキューに格納される。
【００８１】
図１０は、スケジューラ２３０のスケジューリング動作例２−２を示すフローチャートである。まず、スケジューラ２３０は、移動制御パケット用キューが空であるかどうかをチェックする（ステップＨ０１）。もし空でなければ（ステップＨ０１のＹＥＳ）、移動制御パケット用キューの先頭のパケットを送信する（ステップＨ０５）。空の場合には（ステップＨ０１のＮＯ）、その他のキューをＣＩＲが良い順に並べ替える（ステップＨ０２）。ただし、ここで並べ替えの方法は任意で構わない。次に、最もＣＩＲの良いキューの先頭パケットを送信する（ステップＨ０３）。全てのキューが空であるかをチェックし（ステップＨ０４）、もし全て空であるならば終了し、空でないキューが存在するならば再びステップＨ０１に戻る。
【００８２】
なお、スケジューラ２３０が選択したパケットが移動制御パケット用キューのパケットである場合、パケット誤り可能性を低下させるために、スケジューラ２３０が変調部２０８にパケットを渡す際、同時にその旨を通知することによって、通常その移動局の無線リンク品質を基に適用される変調方式よりも熱雑音や干渉成分などの背景雑音に対する耐性の高い変調方式を用いる。たとえば、通常であれば１６ＱＡＭ(Quadrature Amplitude Modulation)方式を選択する場合には、無線リンク品質に基づいてＱＰＳＫ(Quadrature Phase Shift Keying)方式を選択するなどである。あるいは、通常の誤り訂正符号方式よりも誤り訂正能力の高い誤り訂正符号を用いても構わない。たとえば、通常であれば符号化率１／２の符号化を行う場合には、無線リンク品質に基づいて符号化率１／４の符号化を行うなどである。このような背景雑音に対する耐性の高い変調方式および誤り訂正能力の高い誤り訂正符号の両方を用いるようにしても良い。
【００８３】
（第３実施形態）
図１１は、本発明の第３実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。本実施形態によるパケット転送装置は、有線リンク側の出力端子３０１と、無線リンク側の入力端子３０７および出力端子３０８とを有する。さらに、パケット転送装置は、パケット識別部３０３、フロー情報記憶部３０４、上り信号解析部３０５、帯域割当装置３０６、およびフロー毎のキュー３１１〜３１３を備える。
【００８４】
出力端子３０１からは有線ネットワークへ向けてパケットが送出される。スケジューラ３０２は、フロー毎のキュー３１１〜３１３のいずれかの先頭のパケットを取り出して出力端子３０１に渡し、またフロー情報記憶部３０４におけるフローのパケット転送レートを更新する。パケット分類部３０３は、入力端子３０７から入力された信号が移動局からの帯域割り当て要求であるか否かを判定し、帯域割当要求であれば、フロー情報記憶部３０４の該当移動局のフローに帯域割り当て要求があったことを記録する。通信パケットの場合には、フロー情報記憶部３０４を参照し、フロー毎に分類してキュー３１１〜３１３のいずれかに格納する。
【００８５】
フロー情報記憶部３０４は、移動局とフローの組合せ毎にパケット転送レート、移動局と無線基地局の間の無線リンク品質などの情報を保持している。上り信号解析部３０５は、入力端子３０７から入力した信号から各移動局と無線基地局との間の無線リンク品質情報を取り出し、フロー情報記憶部３０４に記録する。帯域割当部３０６は、フロー情報記憶部３０４を参照しつつ、各移動局に対して上り方向の帯域の割当を決定し、各移動局へ出力端子３０８を通して帯域割り当て命令を送出する。
【００８６】
図１２は、フロー情報記憶部３０４の保持する情報の一例を示す模式図である。ここでは、移動端末とフローとの組合せごとに、サービスクラス、キュー識別子、パケット転送レート、サービス品質を満たしているどうかのフラグ(satisfied?)、帯域要求の有無を示す要求フラグ（および要求サイズ）、再送フラグ、および移動制御フラグを保持し、かつ、端末ごとに無線リンク品質の情報としてのＣＩＲ(Carrier to Interference Ratio)を保持している。
【００８７】
このような第３実施形態において、移動局から上り無線リンクを通って到達したパケットは、入力端子３０７を通してパケット分類部３０３に入力する。パケット分類部３０３は、まず信号がパケットであるかどうか識別する。パケットでなく帯域割当要求ならば、フロー情報記憶部３０４の該当するフローの要求フラグを１とし、要求されたサイズを記録する。パケットの場合は、移動局とフローを識別し、フロー情報記憶部３０４に問い合わせてキュー識別子を得て、移動局とフローとの組合せに従ってキュー３１１〜３１３のいずれかに格納する。
【００８８】
上り信号解析部３０５は、入力端子３０７から入力する信号から各移動局と無線基地局の間の無線リンク品質についての情報が得られるたびに、フロー情報記憶部３０４の該当する移動局に対する情報を更新する。スケジューラ３０２はキュー３１１〜３１３から空でないキューを順次選択し、先頭のパケットを出力端子３０１へ出力する。ただし、キューの選択方法は任意の方法で構わない。また同時に、キューのパケット転送レート情報の更新をフロー情報記憶部３０４に対して行う。その後、パケットは出力端子３０１から有線ネットワークに送出される。
【００８９】
帯域割当部３０６は、フロー情報記憶部３０４の情報に基づいて、移動局の上りリンクの割り当て帯域を決定し、出力端子３０８を通して該当する移動局に通知する。割り当てた帯域で、要求されたサイズのデータを送信し終えるときには、同時に該当移動局フローの要求フラグを０にしておく。通知を受けた移動局はパケットを上りリンクに出力する。
【００９０】
（動作例３−１）
図１３は、帯域割当部３０６の動作例３−１を示すフローチャートである。帯域割当部３０６は、フロー情報記憶部３０４の移動局とフローの組合せごとの情報を参照し、サービス品質を満たしていないフローがあるかどうかをチェックする（ステップＩ０１）。もし存在するならば（ステップＩ０１のＹＥＳ）、サービス品質を満たしていない任意のフローを選択し（ステップＩ０７）、選択したフローに上り帯域を割り当て移動局に通知する（ステップＩ０８）。ただし、割り当てる帯域は、フローが要求する全データ分でも良いし任意の基準で決定した帯域で構わない。
【００９１】
サービス品質を満たしていないフローがない場合には（ステップＩ０１のＮＯ）、サービス品質を満たしているフローの中で無線リンク品質ＣＩＲが良い順に並べ替え（ステップＩ０２）、最も無線リンク品質が良いフローに上り帯域を割り当て移動局に通知する（ステップＩ０３）。ただし、割り当てる帯域は、フローが要求する全データ分でも良いし任意の基準で決定した帯域で構わない。
【００９２】
次に、移動局に帯域を割り当てたことによって変化したフローの情報を更新する。まず、割り当てた帯域でフローの全要求データを送信することが可能であるか判断する（ステップＩ０４）。もし可能であれば、フローの要求フラグを０とする（ステップＩ０５）。送信しきれない場合には（ステップＩ０４のＮＯ）、割り当てた帯域で送信可能なデータサイズ分減算して更新する（ステップＩ０９）。以上で帯域割当処理が終わり、他に要求フラグが１のフローがあるかチェックする（ステップＩ０６）。もしあれば、再びステップI０１に戻り、なければ終了する。
【００９３】
なお、上記第１〜第３実施形態において説明された動作を実行するパケット転送装置は、プログラム制御のコンピュータにより実現することができる。
【００９４】
図１５は、本発明によるプログラムにより各種処理を実行するコンピュータを用いたパケット転送装置の概略的構成を示すブロック図である。入出力インタフェース部４０１は、パケットの入力端子１０１や出力端子１１０を通して外部とのパケットのやりとりを可能にする。演算処理部４０２は、ＣＰＵなどのマイクロプロセッサおよびその周辺回路からなり、所定のプログラムを読み込んで実行することにより上記ハードウエアとプログラムからなるソフトウエアとを協働させ、パケット分類部１０４、キューマネージャ１０５およびスケジューラ１３０の各種機能を実現する。記憶部４０３は、演算処理部４０２での処理に用いる各種情報やパケットスケジューリングプログラムを記憶するメモリである。キューバッファ４０４は、各キュー１２１、１２２、１２６〜１２８を実現するバッファメモリである。これら入出力インタフェース部４０１、演算処理部４０２、記憶部４０３およびキューバッファ４０４は、バス４０５を介して相互に接続されており、必要に応じて各種情報をやりとりする。
【００９５】
【発明の効果】
以上のように、本発明によれば、移動局に対して所要のサービス品質を保証すべく、無線基地局は所要のサービス品質を満足しないフロー群に関しては、サービス品質を満足するフロー群よりも優先してパケット転送を行い、サービス品質を満足するフロー群に関しては無線リンク品質の良い移動局から順番にパケット転送を行う。本発明によるスケジューラを無線基地局に適用することにより、移動通信ネットワークにおける無線基地局−移動局間の通信に関し、所要のサービス品質を満たしつつ、セル全体のスループットを最大化することが可能となる。
【図面の簡単な説明】
【図１】本発明の第１実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。
【図２】フロー情報記憶部１０３の保持する情報の一例を示す模式図である。
【図３】スケジューラ１３０のスケジューリング動作例１−１を示すフローチャートである。
【図４】スケジューラ１３０のスケジューリング動作例１−２を示すフローチャートである。
【図５】スケジューラ１３０のスケジューリング動作例１−３を示すフローチャートである。
【図６】スケジューラ１３０のスケジューリング動作例１−４を示すフローチャートである。
【図７】スケジューラ１３０のスケジューリング動作例１−５を示すフローチャートである。
【図８】本発明の第２実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。
【図９】スケジューラ２３０のスケジューリング動作例２−１を示すフローチャートである。
【図１０】スケジューラ２３０のスケジューリング動作例２−２を示すフローチャートである。
【図１１】本発明の第３実施形態によるスケジューリング装置を適用したパケット転送装置の構成を示すブロック図である。
【図１２】フロー情報記憶部３０４の保持する情報の一例を示す模式図である。
【図１３】帯域割当部３０６の動作例３−１を示すフローチャートである。
【図１４】（Ａ）は一般的な移動通信システムの概略的構成図であり、（Ｂ）は従来のパケット転送装置の一例を示すブロック図である。
【図１５】本発明によるプログラムにより各種処理を実行するコンピュータを用いたパケット転送装置の概略的構成を示すブロック図である。
【符号の説明】
０１、０７ 通信装置
０２ 無線リンク
０３ パケット転送装置
０４、０６ 有線リンク
０５ パケットネットワーク
１１ 下りリンク
１２ 上りリンク
００１ 入力端子
００２ フロー情報記憶部
００３ パケット分類部
００４ スケジューラ
００５ 出力端子
０１１、０１２、０１３ 移動局ごとのキューグループ
０２１、０２２ 移動局１のキュー群
０２３、０２４ 移動局２のキュー群
０２５、０２６ 移動局３のキュー群
０３１、０３２、０３３ 移動局毎の出力キューセレクタ
０３４ 移動局間の出力キューセレクタ
１０１、１０９ 入力端子
１０２ 上り信号解析部
１０３ フロー情報記憶部
１０４ パケット分類部
１０５ キューマネージャ
１０６ 送信済みバッファ
１０７ 再送用バッファ
１０８ 変調部
１１０ 出力端子
１２０、１２５ キューグループ
１２１、１２２ キュー
１２６、１２７、１２８ キュー
１３０ スケジューラ
１３１、１３２、１３３ 移動局毎の出力キューセレクタ
１３４ 移動局間の出力キューセレクタ
２０１、２０９ 入力端子
２０２ 上り信号解析部
２０３ フロー情報記憶部
２０４ パケット分類部
２０５ キューマネージャ
２０６ 送信済みバッファ
２０７ 再送用バッファ
２０８ 変調部
２１０ 出力端子
２２０ キューグループ
２２１、２２２、２２３ キュー
２３０ スケジューラ
３０１、３０８ 出力端子
３０２ スケジューラ
３０３ パケット分類
３０４ フロー情報記憶部
３０５ 上り信号解析部
３０６ 帯域割当部
３０７ 入力端子
３０２ キューグループ
３１１、３１２、３１３ キュー
【図１】
0004168633.tif 000002
【図２】
0004168633.tif 000003
【図３】
0004168633.tif 000004
【図４】
0004168633.tif 000005
【図５】
0004168633.tif 000006
【図６】
0004168633.tif 000007
【図７】
0004168633.tif 000008
【図８】
0004168633.tif 000009
【図９】
0004168633.tif 000010
【図１０】
0004168633.tif 000011
【図１１】
0004168633.tif 000012
【図１２】
0004168633.tif 000013
【図１３】
0004168633.tif 000014
【図１４】
0004168633.tif 000015
【図１５】
0004168633.tif 000016