無線リソース割当装置、無線リソース割当方法及びコンピュータプログラム
【課題】無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることを図る。
【解決手段】各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップ（Ｓ１）と、該要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップ（Ｓ２）と、未割当として残っている余剰無線リソースがあるか判断するステップ（Ｓ３）と、該無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップ（Ｓ４）と、を有する。
【解決手段】各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップ（Ｓ１）と、該要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップ（Ｓ２）と、未割当として残っている余剰無線リソースがあるか判断するステップ（Ｓ３）と、該無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップ（Ｓ４）と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線リソース割当装置、無線リソース割当方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、各標準化団体（例えば、３ＧＰＰ（3rd Generation Partnership Project）、３ＧＰＰ２（3rd Generation Partnership Project 2）、ＩＥＥＥ８０２．１６標準化団体など）で新しい無線システムの標準規格が検討されている。例えば、第３世代（３Ｇ）セルラシステムの後継システムとして、ＬＴＥ（Long Term Evolution：正式名称は「Evolved Universal Terrestrial Radio Access（Ｅ−ＵＴＲＡ）」である）やＵＭＢ（Ultra Mobile Broadband）といった、次世代のセルラシステム（３．９Ｇセルラシステムとも呼ばれる）が検討されている。さらには、３．９Ｇセルラシステムの進化系である、ＩＭＴ−Ａｄｖａｎｃｅｄシステム（４Ｇセルラシステムとも呼ばれる）が検討されている。
【０００３】
それらの検討されている無線システムの中には、直交周波数分割多元接続（Orthogonal Frequency Division Multiple Access：ＯＦＤＭＡ）方式を採用するものがある。例えば、ＬＴＥ、ＵＭＢ、ＷｉＭＡＸ、さらには現在、４Ｇセルラシステム向けに検討されている、ＬＴＥ−ＡｄｖａｎｃｅｄやＩＥＥＥ８０２．１６ｍなどである。
【０００４】
ＯＦＤＭＡ方式を使用する無線システム（以下、ＯＦＤＭＡシステムと称する）では、利用可能な周波数帯域内の複数のサブキャリアを移動端末に割り当てることができる。また、その割当内容は時間とともに変更することができる。したがって、一般的に、ＯＦＤＭＡシステムでは、周波数成分と時間成分から成る二次元的な無線リソースを用いて、柔軟に、無線リソースの割当を行うことができる。
【０００５】
また、３．９Ｇセルラシステムや４Ｇセルラシステムでは、従来の３Ｇシステムに比べて利用可能な周波数帯域幅が広くなっていること、さらにＯＦＤＭＡ方式に加えてＭＩＭＯ（Multiple-Input-Multiple-Output）などの技術を用いることによって、高速データ伝送サービスを提供したり、遅延の少ないアプリケーションを運用したりすることができるようになっている。この特徴を生かすことにより、例えば３．９Ｇシステムでは、ＱｏＳ（Quality of Service）を考慮した各種サービスを展開することが可能である（例えば、非特許文献１参照）。そして、４Ｇセルラシステムでは、３．９Ｇセルラシステム以上に広帯域となるため、既存のサービスにはない新たなサービスを提供することができると期待されている。
【０００６】
特許文献１等の従来の無線リソース割当技術では、テレビ電話やＶｏＩＰ（Voice over IP）などのリアルタイム系アプリケーションで要求されるＱｏＳを満足させるために、リアルタイム系アプリケーションによって送信されるパケットの遅延時間の制限を守るようにしている。これは、一般にリアルタイム系アプリケーションでは、パケットの伝送遅延時間の制限（以下、遅延デッドラインと称する）を超えたパケットは無用となり破棄されるためである。
【０００７】
一方、非リアルタイム系アプリケーション（例えば、ファイルダウンロード、ホームページ閲覧、電子メール送受信）を対象にしたＱｏＳ制御技術として、例えば非特許文献２では、ＱＣＩ（QoS Class Identifier）と呼ばれるＱｏＳを定義するクラスを規定し、非リアルタイム系アプリケーションに対しても、物理層の無線パケットにおける遅延デッドラインを定義することが可能になっている。
【０００８】
また、既存のセルラシステムでは、非リアルタイム系アプリケーションについてはベストエフォート型サービスという位置付けであってその無線リソース割当方法は、まずリアルタイム系アプリケーションなどに優先的に割り当ててから、可能な限り割り当てるというものである。但し、ユーザ間の公平性を確保するため、既存のセルラシステムでは、非リアルタイム系アプリケーションについては、プロポーショナルフェアネス（Proportional Fairness）と呼ばれる割当アルゴリズム（例えば、非特許文献４，５参照）を適用している。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−２５２５１４号公報
【非特許文献】
【００１０】
【非特許文献１】3GPP TS 23.401，“General Packet Radio Service (GPRS) enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) access (Release 8)”
【非特許文献２】3GPP TS 36.211，“Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation (Release 8)”
【非特許文献３】3GPP TS 36.213，“Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Layer Procedures (Release 8)”
【非特許文献４】P. Bender et al.，“CDMA/HDR: A bandwidth-efficient highspeed wireless data service for nomadic users”，IEEE Communications Magazine，vol. 38，no. 7，pp. 70−77，July 2000
【非特許文献５】A. Jalali，R. Padovani，and R. Pankaj，“Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system”，Proceedings of IEEE Vehicular Technology Conference 2000 (Spring)，pp. 1854−1858，May 2000
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、上述した従来の無線リソース割当技術では、以下に示すような課題がある。
（１）無線システムが複雑化するにつれて無線リソース割当問題も複雑になるが、従来のプロポーショナルフェアネスなどによるヒューリスティック型の無線リソース割当方法では、無線リソース割当問題の最適解を求めることが困難になってきている。
（２）非リアルタイム系アプリケーションはリアルタイム系アプリケーションよりも無線リソース割当の優先度が低いため、リアルタイム系アプリケーションのトラヒックの負荷があまりに大きいと、非リアルタイム系アプリケーションに対する無線リソース割当が行われない事象が発生し、非リアルタイム系アプリケーションを使用しているユーザの満足度が下がる。
（３）従来の無線リソース割当方法で参照する情報は物理層又はデータリンク層の情報のみであり、アプリケーションの視点を考慮した無線リソース割当を行うことができない。例えば、非特許文献２におけるＱＣＩの仕組みでは、ＱＣＩはアプリケーションごとに定義できるが、ユーザの挙動や環境、また、アプリケーションの状況（たとえば、緊急の度合い）を考慮した、遅延デッドラインを扱うことはできない。このため、アプリケーションを利用するユーザの満足度を的確に上げることが難しい。
【００１２】
本発明は、このような事情を考慮してなされたもので、その目的は、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることのできる無線リソース割当装置、無線リソース割当方法及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明に係る無線リソース割当装置は、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当装置において、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得する情報取得手段と、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行う第１の無線リソース割当手段と、前記第１の無線リソース割当手段で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行う第２の無線リソース割当手段と、を備えたことを特徴とする。
【００１４】
本発明に係る無線リソース割当装置においては、前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１５】
本発明に係る無線リソース割当装置においては、前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度と微小値の和の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１６】
本発明に係る無線リソース割当装置においては、送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１７】
本発明に係る無線リソース割当装置においては、前記満足度関数演算手段は、遅延デッドラインまでの残り時間の割合をさらに加味して満足度関数の値を算出することを特徴とする。
【００１８】
本発明に係る無線リソース割当装置においては、前記情報取得手段は、各端末のサービス毎に前記要求条件を取得することを特徴とする。
【００１９】
本発明に係る無線リソース割当方法は、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当方法であって、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、未割当として残っている余剰無線リソースがあるか判断するステップと、前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、を含むことを特徴とする。
【００２０】
本発明に係るコンピュータプログラムは、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当処理を行うためのコンピュータプログラムであって、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、未割当として残っている余剰無線リソースがあるか判断するステップと、前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、をコンピュータに実行させるためのコンピュータプログラムである。
これにより、前述の無線リソース割当装置がコンピュータを利用して実現できるようになる。
【発明の効果】
【００２１】
本発明によれば、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることができるという効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施形態に係る無線スケジューラ１の構成を示すブロック図である。
【図２】同実施形態に係る無線リソースの構成を示す概念図である。
【図３】同実施形態に係る無線システムのプロトコルスタックを示す図である。
【図４】図１に示す無線リソース割当部３の処理手順を示すフローチャートである。
【図５】要求転送速度Ｒｉｊ（ｔ）を説明するための概念図である。
【図６】ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 0」を説明するための概念図である。
【図７】ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 1」を説明するための概念図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照し、本発明の実施形態について説明する。
図１は、本発明の一実施形態に係る無線スケジューラ１の構成を示すブロック図である。図２は、本実施形態に係る無線リソースの構成を示す概念図である。図３は、本実施形態に係る無線システムのプロトコルスタックを示す図である。
【００２４】
まず図２を参照して、本実施形態に係る無線リソースの構成を説明する。図２に示す無線リソースは、ＯＦＤＭＡシステムのものであり、一定の周波数帯域幅と一定の時間幅を有するリソースブロック（ＲＢ）から構成される。
【００２５】
例えば、非特許文献２では、図２に示す無線フレームのことをサブフレーム（Sub-frame）と呼び、サブフレームの長さは１ミリ秒である。また、ＲＢは、１２個のサブキャリアから構成される１８０ｋＨｚの周波数帯域幅と１個のサブフレームの時間幅を有する。セルラシステムの基地局は、サブフレーム毎に、各ＲＢに割り当てるユーザ端末（User Equipment：ＵＥ）を決定する。
【００２６】
次に図３を参照して、本実施形態に係る無線システムの構成を説明する。図３において、無線システムは、基地局と、基地局に無線接続する端末とを有する。基地局は、本実施形態に係る無線スケジューラ１を有する。端末及びサーバは、物理層からアプリケーション層までを有する。基地局は、物理層からデータリンク層までを有する。ゲートウェイは、物理層からＩＰ層までを有する。
【００２７】
端末とサーバは、アプリケーション通信を行う。アプリケーションデータが格納されたパケット（ＴＣＰ／ＩＰパケット）は、基地局（物理層、データリンク層）及びゲートウェイ（物理層、データリンク層、ＩＰ層）を介して、端末とサーバ間で送受される。
【００２８】
端末は、セッション毎に、サーバ間で送受するパケットの伝送遅延に関する要求条件を基地局へ送信する。セッションは、ＩＰアドレスとポート番号の組み合わせによって一意に特定される、サービスを指す。パケットの伝送遅延に関する要求条件としては、例えば、遅延デッドライン、スループットなどが挙げられる。本実施形態では、パケットの伝送遅延に関する要求条件として、遅延デッドラインを用いる。あるサービスにおける遅延デッドラインは、当該サービスのパケット群が送信元から宛先へ送達完了するまでの期限を表す。例えば、端末がサーバからファイルをダウンロードするサービスを行う場合、該サービスの開始時刻から所定時間以内に端末が当該ファイルを受信すること、を遅延デッドラインとして要求する。
【００２９】
遅延デッドラインは、端末からデータリンク層のデータとして基地局へ送られる。具体的には、セルラシステムのシグナリングプロトコルにおいて遅延デッドラインを伝達するための遅延デッドライン伝達メッセージを設け、物理層の無線リソースを使用して遅延デッドライン伝達メッセージを端末から基地局へ送信する。基地局では、物理層を介してデータリンク層で遅延デッドライン伝達メッセージを受信し、受信した遅延デッドライン伝達メッセージを無線スケジューラ１へ渡す。
【００３０】
また、端末は、無線チャネル品質情報（Channel Quality Indicator：ＣＱＩ）など、物理層及びデータリンク層の情報を基地局へ送信する。
【００３１】
次に図１を参照して、本実施形態に係る無線スケジューラ１の構成を説明する。図１において、無線スケジューラ１は、入力情報取得部２と無線リソース割当部３と割当結果通知部４と統計情報作成部５を有する。
【００３２】
入力情報取得部２は、無線回線品質情報と無線リソース割当における各種パラメータを取得する。無線回線品質情報としては、例えば、端末のアクティブ情報（Active／Inactive）、端末の性能情報（Capability）、ＣＱＩ、ＳＩＮＲ（Signal-to-Interference and Noise Ratio）、ＩｏＴ（Interference over Thermal）、ＭＩＭＯ用のＲＩ（Rank Indicator）やＰＭＩ（Preferred Matrix Indicator）などである。無線リソース割当における各種パラメータとしては、例えば、システム情報（周波数帯域幅、ＲＢ当たりのサブキャリア数、無線フレーム長、制御チャネルに使用する無線リソース領域など）、ＱＣＩごとの要求性能条件、ハンドオーバー閾値などである。また、入力情報取得部２は、統計情報作成部５から、過去の無線リソース割当の統計情報を取得する。入力情報取得部２は、取得した情報を無線リソース割当部３へ渡す。
【００３３】
無線リソース割当部３は、入力情報取得部２から受け取った情報を用いて、無線リソースの割当を行う。割当結果通知部４は、無線リソース割当部３による無線リソース割当結果をシステムの仕様に沿ったフォーマットの無線リソース割当データに変換し、無線リソース割当データを必要とする基地局内の各部へ出力する。統計情報作成部５は、無線リソース割当部３による無線リソース割当結果の統計情報を作成する。
【００３４】
次に、本実施形態に係る無線リソース割当部３の動作を説明する。図４は、無線リソース割当部３の処理手順を示すフローチャートである。図４において、無線リソース割当部３は、第１の無線リソース割当処理（Ｓ２）と第２の無線リソース割当処理（Ｓ４）の２段階で無線リソースの割当を行う。
【００３５】
まず、第１、第２の無線リソース割当処理で使用する変数を定義する。
ｉ：端末の識別子（ＵＥ＿ＩＤ）。端末（ｉ）は、ＵＥ＿ＩＤがｉである端末を指す。
ｊ：サービスの識別子（サービスＩＤ）。サービス（ｊ）は、サービスＩＤがｊであるサービスを指す。
ｋ：ＲＢの識別子（ＲＢ＿ＩＤ）。ＲＢ（ｋ）は、ＲＢ＿ＩＤがｋであるＲＢを指す。
ｔ：無線フレームの識別子（無線フレームＩＤ）。無線フレーム（ｔ）は、無線フレームＩＤがｔである無線フレームを指す。本実施形態では、ｔは、無線フレームが送信される時刻とする。
ＮＲＢ：無線システムで使用可能なＲＢの総数。
ｘｉｊｋ（ｔ）：無線フレーム（ｔ）において、端末（ｉ）のサービス（ｊ）にＲＢ（ｋ）を割り当てるか否かを示すフラグ（割り当てる場合は１、割り当てない場合は０）。
Ｓｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の満足度関数。
なお、満足度関数Ｓｉｊ（ｔ）は、ユーザ又はアプリケーションの視点での満足度を表すものである。満足度関数Ｓｉｊ（ｔ）の詳細は後述する。
【００３６】
以下、図４を参照して、無線リソース割当部３の動作を説明する。
ステップＳ１：入力情報取得部２から各種情報を入力する。
【００３７】
ステップＳ２：第１の無線リソース割当処理を行う。第１の無線リソース割当処理では、ユーザ間の公平性を保つため、満足度関数Ｓｉｊ（ｔ）の最小値を最大化するように、ＲＢの割当を行う。具体的には、次式（１）から（４）で表される０−１整数計画問題を解く。この計画問題の解法については、公知手法である分枝限定法を利用することができる。
【００３８】
【数１】
【００３９】
なお、式（１），（２）は、次式と等しい。
【００４０】
【数２】
【００４１】
この第１の無線リソース割当処理によって、特定の端末やサービスにＲＢの割当が集中することを避けると共に、最低限の満足度を共有化することが可能となる。
【００４２】
ステップＳ３：ステップＳ２で割り当てたＲＢの総数と、無線システムで使用可能なＲＢの総数ＮＲＢとを比較し、未割当として残っているＲＢ（余剰無線リソース）があるか判断する。余剰無線リソースがない場合は図４の処理を終了する。一方、余剰無線リソースがある場合はステップＳ４に進み、第２の無線リソース割当処理を行う。
【００４３】
ステップＳ４：第２の無線リソース割当処理を行う。第２の無線リソース割当処理では、第１の無線リソース割当処理（Ｓ２）の結果によるユーザ間の公平性を保ちながら、満足度向上のため、余剰無線リソースの割当を行ってユーザの満足度の総和を最大化する。具体的には、次式（５），（３），（４），（６）で表される０−１整数計画問題を解く。この計画問題の解法については、公知手法である分枝限定法を利用することができる。
【００４４】
【数３】
【００４５】
第２の無線リソース割当処理（Ｓ４）では、式（６）に示すように、第１の無線リソース割当処理（Ｓ２）で求められた最低の満足度ｓを保つことを条件に、全体の満足度を最大化している。
【００４６】
無線リソース割当部３は、第１の無線リソース割当処理（Ｓ２）の割当結果（ｘｉｊｋ（ｔ））と第２の無線リソース割当処理（Ｓ４）の割当結果（ｘｉｊｋ（ｔ））を出力する。
【００４７】
なお、上記式（２），（６）を次式（２’），（６’）に変更することも可能である。
【００４８】
【数４】
【００４９】
式（２），（６）を使用する場合は、各端末のサービス毎に満足度関数Ｓｉｊ（ｔ）の最小値を最大化することになる。一方、式（２’），（６’）を使用する場合は、サービスの区別なしで端末毎に満足度関数Ｓｉｊ（ｔ）の最小値を最大化することになる。
【００５０】
次に、本実施形態に係る満足度関数Ｓｉｊ（ｔ）の実施例を順次説明する。
【００５１】
まず、満足度関数Ｓｉｊ（ｔ）の実施例で使用する変数を定義する。
Ｄｉｊ：端末（ｉ）のサービス（ｊ）の遅延デッドライン。
Ａｉｊ（ｔ）：無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）に割り当てられるＲＢを用いて得られる転送速度（ビットレート）。Ａｉｊ（ｔ）は次式で算出される。Ａｉｊ（ｔ）は、ＲＢの割当状況の変化に伴って更新される。
【００５２】
【数５】
【００５３】
但し、ＷはＲＢ当たりの周波数帯域幅である。Ｅｉｊ（ｔ）は、無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）に割り当てられるＲＢ（ｋ）の集合によって決まる周波数利用効率（ビットレート／Ｈｚ）である。なお、該ＲＢ（ｋ）の集合の総数Ｚは次式で表される。
【００５４】
【数６】
【００５５】
Ｒｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の要求転送速度（要求ビットレート）。Ｒｉｊ（ｔ）は次式で算出される。Ｒｉｊ（ｔ）は、図５に示されるように、無線リソースの割当時刻の経過に伴って更新される。
【００５６】
【数７】
【００５７】
但し、Ｑｉｊ（ｔ）は無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）の未送信として残っている情報量（ビット）である。ｔ０は端末（ｉ）のサービス（ｊ）の送信すべき情報に係る転送要求開始時刻である。Ｑｉｊ（ｔ０）は、時刻ｔ０において、端末（ｉ）のサービス（ｊ）の送信すべき情報量の初期値（ビット）である。ｑｉｊ（ｔ）は無線フレーム（ｔ）までに既に送信完了した情報量（ビット）である。
【００５８】
Ｓｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の満足度関数。
【実施例１】
【００５９】
実施例１では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６０】
【数８】
【００６１】
実施例１では、上式で示されるように、送信すべき情報量を遅延デッドラインまでに送信完了するために必要な要求転送速度Ｒｉｊ（ｔ）に対する、無線リソース割当によって得られる転送速度Ａｉｊ（ｔ）の割合によって、満足度関数Ｓｉｊ（ｔ）を定義する。Ａｉｊ（ｔ）はＲＢの割当フラグｘｉｊｋ（ｔ）の関数であるので、ＲＢの割当の経過に応じて、満足度関数Ｓｉｊ（ｔ）の値が変化する。
【００６２】
実施例１で満足度関数Ｓｉｊ（ｔ）に転送速度を使用したのは、「送信すべき残りの情報量が遅延デッドラインまでに送信完了するか？」ということを主眼に置いていることに起因する。これは、「送信すべき残りの情報量が遅延デッドラインまでに送信完了するか？」ということは、つまり、「転送速度が、送信すべき残りの情報量を遅延デッドラインまでの残り時間で割って得られる要求転送速度を満足するか？」という問題に置き換えることができるからである。
【実施例２】
【００６３】
実施例２では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６４】
【数９】
【００６５】
但し、εは定数（微小値）である。
実施例２では、上式で示されるように、実施例１に改良を加えたものである。実施例１の場合、端末（ｉ）のサービス（ｊ）に割り当てられるＲＢが存在しない（つまり、割り当てられるＲＢの数が０となる）と、「Ａｉｊ（ｔ）＝０」となって「Ｓｉｊ（ｔ）＝０」となる。そのような端末（ｉ）のサービス（ｊ）の組（ｉ，ｊ）が複数存在する場合、それらの組（ｉ，ｊ）の満足度関数Ｓｉｊ（ｔ）の値は要求転送速度Ｒｉｊ（ｔ）の大小にかかわらず一律に０となるので、割り当てられるＲＢが存在しないと要求転送速度Ｒｉｊ（ｔ）の異なる組（ｉ，ｊ）であっても同等に扱われることになる。このような事象を避けるために、実施例２では、微小な値εを実施例１の満足度関数Ｓｉｊ（ｔ）の式の分子に加えている。これにより、割り当てられるＲＢが存在しないために「Ａｉｊ（ｔ）＝０」となっても、満足度関数Ｓｉｊ（ｔ）の値は要求転送速度Ｒｉｊ（ｔ）応じて異なることになる。
【実施例３】
【００６６】
実施例３では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６７】
【数１０】
【００６８】
上述の実施例１，２では、送信すべき情報量を遅延デッドラインまでに送信完了することを主眼においているが、実施例３では、さらに、遅延デッドライン以前のできる限り早い時点で送信完了することを考慮する。これは、ユーザにとっては、遅延デッドライン以前のできる限り早い時点で送信完了したほうが望ましいと思われるからである。
【実施例４】
【００６９】
実施例４では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００７０】
【数１１】
【００７１】
又は、
【００７２】
【数１２】
【００７３】
実施例４では、送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数Ｓｉｊ（ｔ）を定義する。これは、送信すべき情報量の残りが少ないほど、ユーザ満足度の向上につながることを想定している。
【００７４】
なお、上述の実施例１から４では、単純な四則演算を用いて満足度関数を定義したが、満足度の度合いを調整するために、指数関数等の高度な関数を用いて満足度関数を定義してもよい。さらに、満足度を表すそれぞれの項に対して、重み係数で重み付けするようにしてもよい。
【００７５】
上述の実施形態によれば、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることができるようになる。これにより、非リアルタイム系トラヒックについても、ユーザの満足度を考慮しながら無線リソースを割り当てることが可能となる。また、ユーザ間の公平性についても、物理層やデータリンク層での公平性ではなく、アプリケーションの観点での公平性を確保しながら、ユーザの満足度を的確に向上させることが可能となる。また、プロポーショナルフェアネス型割当手法などのヒューリスティックアルゴリズムとは異なり、最適問題定義式に従い、最適解を得ることができるようになる。
【００７６】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
例えば、本発明はパケット交換型の無線アクセスシステムに適用可能である。
【００７７】
また、上述の実施形態を非特許文献２，３で想定しているＬＴＥ方式の無線システム（以下、ＬＴＥシステムと称する）に応用することも可能である。この応用例を以下に説明する。
【００７８】
まず、ＬＴＥシステムの上りリンク（端末から基地局方向のリンク）では、ＳＣ−ＦＤＭＡ（Single Carrier FDMA）と呼ばれるシングルキャリア伝送方式を採用しており、端末が送信するときは連続するＲＢを使用することが規定されている。したがって、基地局が上りリンクの無線リソース割当を行う場合には、その規定を守る必要がある。このために、上述の図４のステップＳ２，Ｓ４において、次式（７），（８）を制約条件に追加する。
【００７９】
【数１３】
【００８０】
但し、Ｂｉｊ（ｔ）は、無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の要求転送速度Ｒｉｊ（ｔ）を達成するために必要なＲＢの数である。Ｂｉｊ（ｔ）は、次式で算出される。
【００８１】
【数１４】
【００８２】
なお、上式（７），（８）の制約条件の追加は、ＬＴＥシステムの下りリンク（基地局から端末方向のリンク）におけるＲＢ割当規則「Resource Allocation Type 2」に対しても適用可能である。
【００８３】
また、ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 0」（図６参照）では、割当単位がＲＢグループ（ＲＢＧ）であるので、割当単位をＲＢＧに変更すれば適用可能となる。
【００８４】
さらに、ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 1」（図７参照）では、「Subset」と呼ばれるＲＢの割当領域があらかじめ定められている。このため、上述の図４のステップＳ２，Ｓ４において、上述の式（７），（８）ではなく、次式（９）を制約条件に追加する。
【００８５】
【数１５】
【００８６】
これにより、ＬＴＥシステムに対して上述の実施形態を応用することができるようになるので、ＳＣ−ＦＤＭＡやＲＢ割当規則を考慮した無線リソース割当を行うことが可能になる。
【００８７】
また、図４に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、無線リソース割当処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＤＶＤ（Digital Versatile Disk）等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００８８】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００８９】
１…無線スケジューラ、２…入力情報取得部、３…無線リソース割当部、４…割当結果通知部、５…統計情報作成部
【技術分野】
【０００１】
本発明は、無線リソース割当装置、無線リソース割当方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
近年、各標準化団体（例えば、３ＧＰＰ（3rd Generation Partnership Project）、３ＧＰＰ２（3rd Generation Partnership Project 2）、ＩＥＥＥ８０２．１６標準化団体など）で新しい無線システムの標準規格が検討されている。例えば、第３世代（３Ｇ）セルラシステムの後継システムとして、ＬＴＥ（Long Term Evolution：正式名称は「Evolved Universal Terrestrial Radio Access（Ｅ−ＵＴＲＡ）」である）やＵＭＢ（Ultra Mobile Broadband）といった、次世代のセルラシステム（３．９Ｇセルラシステムとも呼ばれる）が検討されている。さらには、３．９Ｇセルラシステムの進化系である、ＩＭＴ−Ａｄｖａｎｃｅｄシステム（４Ｇセルラシステムとも呼ばれる）が検討されている。
【０００３】
それらの検討されている無線システムの中には、直交周波数分割多元接続（Orthogonal Frequency Division Multiple Access：ＯＦＤＭＡ）方式を採用するものがある。例えば、ＬＴＥ、ＵＭＢ、ＷｉＭＡＸ、さらには現在、４Ｇセルラシステム向けに検討されている、ＬＴＥ−ＡｄｖａｎｃｅｄやＩＥＥＥ８０２．１６ｍなどである。
【０００４】
ＯＦＤＭＡ方式を使用する無線システム（以下、ＯＦＤＭＡシステムと称する）では、利用可能な周波数帯域内の複数のサブキャリアを移動端末に割り当てることができる。また、その割当内容は時間とともに変更することができる。したがって、一般的に、ＯＦＤＭＡシステムでは、周波数成分と時間成分から成る二次元的な無線リソースを用いて、柔軟に、無線リソースの割当を行うことができる。
【０００５】
また、３．９Ｇセルラシステムや４Ｇセルラシステムでは、従来の３Ｇシステムに比べて利用可能な周波数帯域幅が広くなっていること、さらにＯＦＤＭＡ方式に加えてＭＩＭＯ（Multiple-Input-Multiple-Output）などの技術を用いることによって、高速データ伝送サービスを提供したり、遅延の少ないアプリケーションを運用したりすることができるようになっている。この特徴を生かすことにより、例えば３．９Ｇシステムでは、ＱｏＳ（Quality of Service）を考慮した各種サービスを展開することが可能である（例えば、非特許文献１参照）。そして、４Ｇセルラシステムでは、３．９Ｇセルラシステム以上に広帯域となるため、既存のサービスにはない新たなサービスを提供することができると期待されている。
【０００６】
特許文献１等の従来の無線リソース割当技術では、テレビ電話やＶｏＩＰ（Voice over IP）などのリアルタイム系アプリケーションで要求されるＱｏＳを満足させるために、リアルタイム系アプリケーションによって送信されるパケットの遅延時間の制限を守るようにしている。これは、一般にリアルタイム系アプリケーションでは、パケットの伝送遅延時間の制限（以下、遅延デッドラインと称する）を超えたパケットは無用となり破棄されるためである。
【０００７】
一方、非リアルタイム系アプリケーション（例えば、ファイルダウンロード、ホームページ閲覧、電子メール送受信）を対象にしたＱｏＳ制御技術として、例えば非特許文献２では、ＱＣＩ（QoS Class Identifier）と呼ばれるＱｏＳを定義するクラスを規定し、非リアルタイム系アプリケーションに対しても、物理層の無線パケットにおける遅延デッドラインを定義することが可能になっている。
【０００８】
また、既存のセルラシステムでは、非リアルタイム系アプリケーションについてはベストエフォート型サービスという位置付けであってその無線リソース割当方法は、まずリアルタイム系アプリケーションなどに優先的に割り当ててから、可能な限り割り当てるというものである。但し、ユーザ間の公平性を確保するため、既存のセルラシステムでは、非リアルタイム系アプリケーションについては、プロポーショナルフェアネス（Proportional Fairness）と呼ばれる割当アルゴリズム（例えば、非特許文献４，５参照）を適用している。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００８−２５２５１４号公報
【非特許文献】
【００１０】
【非特許文献１】3GPP TS 23.401，“General Packet Radio Service (GPRS) enhancements for Evolved Universal Terrestrial Radio Access Network (E-UTRAN) access (Release 8)”
【非特許文献２】3GPP TS 36.211，“Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation (Release 8)”
【非特許文献３】3GPP TS 36.213，“Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Layer Procedures (Release 8)”
【非特許文献４】P. Bender et al.，“CDMA/HDR: A bandwidth-efficient highspeed wireless data service for nomadic users”，IEEE Communications Magazine，vol. 38，no. 7，pp. 70−77，July 2000
【非特許文献５】A. Jalali，R. Padovani，and R. Pankaj，“Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system”，Proceedings of IEEE Vehicular Technology Conference 2000 (Spring)，pp. 1854−1858，May 2000
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかし、上述した従来の無線リソース割当技術では、以下に示すような課題がある。
（１）無線システムが複雑化するにつれて無線リソース割当問題も複雑になるが、従来のプロポーショナルフェアネスなどによるヒューリスティック型の無線リソース割当方法では、無線リソース割当問題の最適解を求めることが困難になってきている。
（２）非リアルタイム系アプリケーションはリアルタイム系アプリケーションよりも無線リソース割当の優先度が低いため、リアルタイム系アプリケーションのトラヒックの負荷があまりに大きいと、非リアルタイム系アプリケーションに対する無線リソース割当が行われない事象が発生し、非リアルタイム系アプリケーションを使用しているユーザの満足度が下がる。
（３）従来の無線リソース割当方法で参照する情報は物理層又はデータリンク層の情報のみであり、アプリケーションの視点を考慮した無線リソース割当を行うことができない。例えば、非特許文献２におけるＱＣＩの仕組みでは、ＱＣＩはアプリケーションごとに定義できるが、ユーザの挙動や環境、また、アプリケーションの状況（たとえば、緊急の度合い）を考慮した、遅延デッドラインを扱うことはできない。このため、アプリケーションを利用するユーザの満足度を的確に上げることが難しい。
【００１２】
本発明は、このような事情を考慮してなされたもので、その目的は、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることのできる無線リソース割当装置、無線リソース割当方法及びコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１３】
上記の課題を解決するために、本発明に係る無線リソース割当装置は、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当装置において、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得する情報取得手段と、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行う第１の無線リソース割当手段と、前記第１の無線リソース割当手段で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行う第２の無線リソース割当手段と、を備えたことを特徴とする。
【００１４】
本発明に係る無線リソース割当装置においては、前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１５】
本発明に係る無線リソース割当装置においては、前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度と微小値の和の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１６】
本発明に係る無線リソース割当装置においては、送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする。
【００１７】
本発明に係る無線リソース割当装置においては、前記満足度関数演算手段は、遅延デッドラインまでの残り時間の割合をさらに加味して満足度関数の値を算出することを特徴とする。
【００１８】
本発明に係る無線リソース割当装置においては、前記情報取得手段は、各端末のサービス毎に前記要求条件を取得することを特徴とする。
【００１９】
本発明に係る無線リソース割当方法は、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当方法であって、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、未割当として残っている余剰無線リソースがあるか判断するステップと、前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、を含むことを特徴とする。
【００２０】
本発明に係るコンピュータプログラムは、各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当処理を行うためのコンピュータプログラムであって、各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、未割当として残っている余剰無線リソースがあるか判断するステップと、前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、をコンピュータに実行させるためのコンピュータプログラムである。
これにより、前述の無線リソース割当装置がコンピュータを利用して実現できるようになる。
【発明の効果】
【００２１】
本発明によれば、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることができるという効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の一実施形態に係る無線スケジューラ１の構成を示すブロック図である。
【図２】同実施形態に係る無線リソースの構成を示す概念図である。
【図３】同実施形態に係る無線システムのプロトコルスタックを示す図である。
【図４】図１に示す無線リソース割当部３の処理手順を示すフローチャートである。
【図５】要求転送速度Ｒｉｊ（ｔ）を説明するための概念図である。
【図６】ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 0」を説明するための概念図である。
【図７】ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 1」を説明するための概念図である。
【発明を実施するための形態】
【００２３】
以下、図面を参照し、本発明の実施形態について説明する。
図１は、本発明の一実施形態に係る無線スケジューラ１の構成を示すブロック図である。図２は、本実施形態に係る無線リソースの構成を示す概念図である。図３は、本実施形態に係る無線システムのプロトコルスタックを示す図である。
【００２４】
まず図２を参照して、本実施形態に係る無線リソースの構成を説明する。図２に示す無線リソースは、ＯＦＤＭＡシステムのものであり、一定の周波数帯域幅と一定の時間幅を有するリソースブロック（ＲＢ）から構成される。
【００２５】
例えば、非特許文献２では、図２に示す無線フレームのことをサブフレーム（Sub-frame）と呼び、サブフレームの長さは１ミリ秒である。また、ＲＢは、１２個のサブキャリアから構成される１８０ｋＨｚの周波数帯域幅と１個のサブフレームの時間幅を有する。セルラシステムの基地局は、サブフレーム毎に、各ＲＢに割り当てるユーザ端末（User Equipment：ＵＥ）を決定する。
【００２６】
次に図３を参照して、本実施形態に係る無線システムの構成を説明する。図３において、無線システムは、基地局と、基地局に無線接続する端末とを有する。基地局は、本実施形態に係る無線スケジューラ１を有する。端末及びサーバは、物理層からアプリケーション層までを有する。基地局は、物理層からデータリンク層までを有する。ゲートウェイは、物理層からＩＰ層までを有する。
【００２７】
端末とサーバは、アプリケーション通信を行う。アプリケーションデータが格納されたパケット（ＴＣＰ／ＩＰパケット）は、基地局（物理層、データリンク層）及びゲートウェイ（物理層、データリンク層、ＩＰ層）を介して、端末とサーバ間で送受される。
【００２８】
端末は、セッション毎に、サーバ間で送受するパケットの伝送遅延に関する要求条件を基地局へ送信する。セッションは、ＩＰアドレスとポート番号の組み合わせによって一意に特定される、サービスを指す。パケットの伝送遅延に関する要求条件としては、例えば、遅延デッドライン、スループットなどが挙げられる。本実施形態では、パケットの伝送遅延に関する要求条件として、遅延デッドラインを用いる。あるサービスにおける遅延デッドラインは、当該サービスのパケット群が送信元から宛先へ送達完了するまでの期限を表す。例えば、端末がサーバからファイルをダウンロードするサービスを行う場合、該サービスの開始時刻から所定時間以内に端末が当該ファイルを受信すること、を遅延デッドラインとして要求する。
【００２９】
遅延デッドラインは、端末からデータリンク層のデータとして基地局へ送られる。具体的には、セルラシステムのシグナリングプロトコルにおいて遅延デッドラインを伝達するための遅延デッドライン伝達メッセージを設け、物理層の無線リソースを使用して遅延デッドライン伝達メッセージを端末から基地局へ送信する。基地局では、物理層を介してデータリンク層で遅延デッドライン伝達メッセージを受信し、受信した遅延デッドライン伝達メッセージを無線スケジューラ１へ渡す。
【００３０】
また、端末は、無線チャネル品質情報（Channel Quality Indicator：ＣＱＩ）など、物理層及びデータリンク層の情報を基地局へ送信する。
【００３１】
次に図１を参照して、本実施形態に係る無線スケジューラ１の構成を説明する。図１において、無線スケジューラ１は、入力情報取得部２と無線リソース割当部３と割当結果通知部４と統計情報作成部５を有する。
【００３２】
入力情報取得部２は、無線回線品質情報と無線リソース割当における各種パラメータを取得する。無線回線品質情報としては、例えば、端末のアクティブ情報（Active／Inactive）、端末の性能情報（Capability）、ＣＱＩ、ＳＩＮＲ（Signal-to-Interference and Noise Ratio）、ＩｏＴ（Interference over Thermal）、ＭＩＭＯ用のＲＩ（Rank Indicator）やＰＭＩ（Preferred Matrix Indicator）などである。無線リソース割当における各種パラメータとしては、例えば、システム情報（周波数帯域幅、ＲＢ当たりのサブキャリア数、無線フレーム長、制御チャネルに使用する無線リソース領域など）、ＱＣＩごとの要求性能条件、ハンドオーバー閾値などである。また、入力情報取得部２は、統計情報作成部５から、過去の無線リソース割当の統計情報を取得する。入力情報取得部２は、取得した情報を無線リソース割当部３へ渡す。
【００３３】
無線リソース割当部３は、入力情報取得部２から受け取った情報を用いて、無線リソースの割当を行う。割当結果通知部４は、無線リソース割当部３による無線リソース割当結果をシステムの仕様に沿ったフォーマットの無線リソース割当データに変換し、無線リソース割当データを必要とする基地局内の各部へ出力する。統計情報作成部５は、無線リソース割当部３による無線リソース割当結果の統計情報を作成する。
【００３４】
次に、本実施形態に係る無線リソース割当部３の動作を説明する。図４は、無線リソース割当部３の処理手順を示すフローチャートである。図４において、無線リソース割当部３は、第１の無線リソース割当処理（Ｓ２）と第２の無線リソース割当処理（Ｓ４）の２段階で無線リソースの割当を行う。
【００３５】
まず、第１、第２の無線リソース割当処理で使用する変数を定義する。
ｉ：端末の識別子（ＵＥ＿ＩＤ）。端末（ｉ）は、ＵＥ＿ＩＤがｉである端末を指す。
ｊ：サービスの識別子（サービスＩＤ）。サービス（ｊ）は、サービスＩＤがｊであるサービスを指す。
ｋ：ＲＢの識別子（ＲＢ＿ＩＤ）。ＲＢ（ｋ）は、ＲＢ＿ＩＤがｋであるＲＢを指す。
ｔ：無線フレームの識別子（無線フレームＩＤ）。無線フレーム（ｔ）は、無線フレームＩＤがｔである無線フレームを指す。本実施形態では、ｔは、無線フレームが送信される時刻とする。
ＮＲＢ：無線システムで使用可能なＲＢの総数。
ｘｉｊｋ（ｔ）：無線フレーム（ｔ）において、端末（ｉ）のサービス（ｊ）にＲＢ（ｋ）を割り当てるか否かを示すフラグ（割り当てる場合は１、割り当てない場合は０）。
Ｓｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の満足度関数。
なお、満足度関数Ｓｉｊ（ｔ）は、ユーザ又はアプリケーションの視点での満足度を表すものである。満足度関数Ｓｉｊ（ｔ）の詳細は後述する。
【００３６】
以下、図４を参照して、無線リソース割当部３の動作を説明する。
ステップＳ１：入力情報取得部２から各種情報を入力する。
【００３７】
ステップＳ２：第１の無線リソース割当処理を行う。第１の無線リソース割当処理では、ユーザ間の公平性を保つため、満足度関数Ｓｉｊ（ｔ）の最小値を最大化するように、ＲＢの割当を行う。具体的には、次式（１）から（４）で表される０−１整数計画問題を解く。この計画問題の解法については、公知手法である分枝限定法を利用することができる。
【００３８】
【数１】
【００３９】
なお、式（１），（２）は、次式と等しい。
【００４０】
【数２】
【００４１】
この第１の無線リソース割当処理によって、特定の端末やサービスにＲＢの割当が集中することを避けると共に、最低限の満足度を共有化することが可能となる。
【００４２】
ステップＳ３：ステップＳ２で割り当てたＲＢの総数と、無線システムで使用可能なＲＢの総数ＮＲＢとを比較し、未割当として残っているＲＢ（余剰無線リソース）があるか判断する。余剰無線リソースがない場合は図４の処理を終了する。一方、余剰無線リソースがある場合はステップＳ４に進み、第２の無線リソース割当処理を行う。
【００４３】
ステップＳ４：第２の無線リソース割当処理を行う。第２の無線リソース割当処理では、第１の無線リソース割当処理（Ｓ２）の結果によるユーザ間の公平性を保ちながら、満足度向上のため、余剰無線リソースの割当を行ってユーザの満足度の総和を最大化する。具体的には、次式（５），（３），（４），（６）で表される０−１整数計画問題を解く。この計画問題の解法については、公知手法である分枝限定法を利用することができる。
【００４４】
【数３】
【００４５】
第２の無線リソース割当処理（Ｓ４）では、式（６）に示すように、第１の無線リソース割当処理（Ｓ２）で求められた最低の満足度ｓを保つことを条件に、全体の満足度を最大化している。
【００４６】
無線リソース割当部３は、第１の無線リソース割当処理（Ｓ２）の割当結果（ｘｉｊｋ（ｔ））と第２の無線リソース割当処理（Ｓ４）の割当結果（ｘｉｊｋ（ｔ））を出力する。
【００４７】
なお、上記式（２），（６）を次式（２’），（６’）に変更することも可能である。
【００４８】
【数４】
【００４９】
式（２），（６）を使用する場合は、各端末のサービス毎に満足度関数Ｓｉｊ（ｔ）の最小値を最大化することになる。一方、式（２’），（６’）を使用する場合は、サービスの区別なしで端末毎に満足度関数Ｓｉｊ（ｔ）の最小値を最大化することになる。
【００５０】
次に、本実施形態に係る満足度関数Ｓｉｊ（ｔ）の実施例を順次説明する。
【００５１】
まず、満足度関数Ｓｉｊ（ｔ）の実施例で使用する変数を定義する。
Ｄｉｊ：端末（ｉ）のサービス（ｊ）の遅延デッドライン。
Ａｉｊ（ｔ）：無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）に割り当てられるＲＢを用いて得られる転送速度（ビットレート）。Ａｉｊ（ｔ）は次式で算出される。Ａｉｊ（ｔ）は、ＲＢの割当状況の変化に伴って更新される。
【００５２】
【数５】
【００５３】
但し、ＷはＲＢ当たりの周波数帯域幅である。Ｅｉｊ（ｔ）は、無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）に割り当てられるＲＢ（ｋ）の集合によって決まる周波数利用効率（ビットレート／Ｈｚ）である。なお、該ＲＢ（ｋ）の集合の総数Ｚは次式で表される。
【００５４】
【数６】
【００５５】
Ｒｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の要求転送速度（要求ビットレート）。Ｒｉｊ（ｔ）は次式で算出される。Ｒｉｊ（ｔ）は、図５に示されるように、無線リソースの割当時刻の経過に伴って更新される。
【００５６】
【数７】
【００５７】
但し、Ｑｉｊ（ｔ）は無線フレーム（ｔ）において端末（ｉ）のサービス（ｊ）の未送信として残っている情報量（ビット）である。ｔ０は端末（ｉ）のサービス（ｊ）の送信すべき情報に係る転送要求開始時刻である。Ｑｉｊ（ｔ０）は、時刻ｔ０において、端末（ｉ）のサービス（ｊ）の送信すべき情報量の初期値（ビット）である。ｑｉｊ（ｔ）は無線フレーム（ｔ）までに既に送信完了した情報量（ビット）である。
【００５８】
Ｓｉｊ（ｔ）：無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の満足度関数。
【実施例１】
【００５９】
実施例１では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６０】
【数８】
【００６１】
実施例１では、上式で示されるように、送信すべき情報量を遅延デッドラインまでに送信完了するために必要な要求転送速度Ｒｉｊ（ｔ）に対する、無線リソース割当によって得られる転送速度Ａｉｊ（ｔ）の割合によって、満足度関数Ｓｉｊ（ｔ）を定義する。Ａｉｊ（ｔ）はＲＢの割当フラグｘｉｊｋ（ｔ）の関数であるので、ＲＢの割当の経過に応じて、満足度関数Ｓｉｊ（ｔ）の値が変化する。
【００６２】
実施例１で満足度関数Ｓｉｊ（ｔ）に転送速度を使用したのは、「送信すべき残りの情報量が遅延デッドラインまでに送信完了するか？」ということを主眼に置いていることに起因する。これは、「送信すべき残りの情報量が遅延デッドラインまでに送信完了するか？」ということは、つまり、「転送速度が、送信すべき残りの情報量を遅延デッドラインまでの残り時間で割って得られる要求転送速度を満足するか？」という問題に置き換えることができるからである。
【実施例２】
【００６３】
実施例２では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６４】
【数９】
【００６５】
但し、εは定数（微小値）である。
実施例２では、上式で示されるように、実施例１に改良を加えたものである。実施例１の場合、端末（ｉ）のサービス（ｊ）に割り当てられるＲＢが存在しない（つまり、割り当てられるＲＢの数が０となる）と、「Ａｉｊ（ｔ）＝０」となって「Ｓｉｊ（ｔ）＝０」となる。そのような端末（ｉ）のサービス（ｊ）の組（ｉ，ｊ）が複数存在する場合、それらの組（ｉ，ｊ）の満足度関数Ｓｉｊ（ｔ）の値は要求転送速度Ｒｉｊ（ｔ）の大小にかかわらず一律に０となるので、割り当てられるＲＢが存在しないと要求転送速度Ｒｉｊ（ｔ）の異なる組（ｉ，ｊ）であっても同等に扱われることになる。このような事象を避けるために、実施例２では、微小な値εを実施例１の満足度関数Ｓｉｊ（ｔ）の式の分子に加えている。これにより、割り当てられるＲＢが存在しないために「Ａｉｊ（ｔ）＝０」となっても、満足度関数Ｓｉｊ（ｔ）の値は要求転送速度Ｒｉｊ（ｔ）応じて異なることになる。
【実施例３】
【００６６】
実施例３では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００６７】
【数１０】
【００６８】
上述の実施例１，２では、送信すべき情報量を遅延デッドラインまでに送信完了することを主眼においているが、実施例３では、さらに、遅延デッドライン以前のできる限り早い時点で送信完了することを考慮する。これは、ユーザにとっては、遅延デッドライン以前のできる限り早い時点で送信完了したほうが望ましいと思われるからである。
【実施例４】
【００６９】
実施例４では、満足度関数Ｓｉｊ（ｔ）を次式で表す。
【００７０】
【数１１】
【００７１】
又は、
【００７２】
【数１２】
【００７３】
実施例４では、送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数Ｓｉｊ（ｔ）を定義する。これは、送信すべき情報量の残りが少ないほど、ユーザ満足度の向上につながることを想定している。
【００７４】
なお、上述の実施例１から４では、単純な四則演算を用いて満足度関数を定義したが、満足度の度合いを調整するために、指数関数等の高度な関数を用いて満足度関数を定義してもよい。さらに、満足度を表すそれぞれの項に対して、重み係数で重み付けするようにしてもよい。
【００７５】
上述の実施形態によれば、無線リソース割当問題において、非リアルタイム系アプリケーション及びリアルタイム系アプリケーションの両方を扱うと共に、ユーザ又はアプリケーションの視点で満足度を最大化する最適解を求めることができるようになる。これにより、非リアルタイム系トラヒックについても、ユーザの満足度を考慮しながら無線リソースを割り当てることが可能となる。また、ユーザ間の公平性についても、物理層やデータリンク層での公平性ではなく、アプリケーションの観点での公平性を確保しながら、ユーザの満足度を的確に向上させることが可能となる。また、プロポーショナルフェアネス型割当手法などのヒューリスティックアルゴリズムとは異なり、最適問題定義式に従い、最適解を得ることができるようになる。
【００７６】
以上、本発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
例えば、本発明はパケット交換型の無線アクセスシステムに適用可能である。
【００７７】
また、上述の実施形態を非特許文献２，３で想定しているＬＴＥ方式の無線システム（以下、ＬＴＥシステムと称する）に応用することも可能である。この応用例を以下に説明する。
【００７８】
まず、ＬＴＥシステムの上りリンク（端末から基地局方向のリンク）では、ＳＣ−ＦＤＭＡ（Single Carrier FDMA）と呼ばれるシングルキャリア伝送方式を採用しており、端末が送信するときは連続するＲＢを使用することが規定されている。したがって、基地局が上りリンクの無線リソース割当を行う場合には、その規定を守る必要がある。このために、上述の図４のステップＳ２，Ｓ４において、次式（７），（８）を制約条件に追加する。
【００７９】
【数１３】
【００８０】
但し、Ｂｉｊ（ｔ）は、無線フレーム（ｔ）における端末（ｉ）のサービス（ｊ）の要求転送速度Ｒｉｊ（ｔ）を達成するために必要なＲＢの数である。Ｂｉｊ（ｔ）は、次式で算出される。
【００８１】
【数１４】
【００８２】
なお、上式（７），（８）の制約条件の追加は、ＬＴＥシステムの下りリンク（基地局から端末方向のリンク）におけるＲＢ割当規則「Resource Allocation Type 2」に対しても適用可能である。
【００８３】
また、ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 0」（図６参照）では、割当単位がＲＢグループ（ＲＢＧ）であるので、割当単位をＲＢＧに変更すれば適用可能となる。
【００８４】
さらに、ＬＴＥシステムの下りリンクにおけるＲＢ割当規則「Resource Allocation Type 1」（図７参照）では、「Subset」と呼ばれるＲＢの割当領域があらかじめ定められている。このため、上述の図４のステップＳ２，Ｓ４において、上述の式（７），（８）ではなく、次式（９）を制約条件に追加する。
【００８５】
【数１５】
【００８６】
これにより、ＬＴＥシステムに対して上述の実施形態を応用することができるようになるので、ＳＣ−ＦＤＭＡやＲＢ割当規則を考慮した無線リソース割当を行うことが可能になる。
【００８７】
また、図４に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、無線リソース割当処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＤＶＤ（Digital Versatile Disk）等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００８８】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００８９】
１…無線スケジューラ、２…入力情報取得部、３…無線リソース割当部、４…割当結果通知部、５…統計情報作成部
【特許請求の範囲】
【請求項１】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当装置において、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得する情報取得手段と、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行う第１の無線リソース割当手段と、
前記第１の無線リソース割当手段で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行う第２の無線リソース割当手段と、
を備えたことを特徴とする無線リソース割当装置。
【請求項２】
前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項３】
前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度と微小値の和の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項４】
送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項５】
前記満足度関数演算手段は、遅延デッドラインまでの残り時間の割合をさらに加味して満足度関数の値を算出することを特徴とする請求項２から４のいずれか１項に記載の無線リソース割当装置。
【請求項６】
前記情報取得手段は、各端末のサービス毎に前記要求条件を取得することを特徴とする請求項１から５のいずれか１項に記載の無線リソース割当装置。
【請求項７】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当方法であって、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、
未割当として残っている余剰無線リソースがあるか判断するステップと、
前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、
を含むことを特徴とする無線リソース割当方法。
【請求項８】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当処理を行うためのコンピュータプログラムであって、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、
未割当として残っている余剰無線リソースがあるか判断するステップと、
前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【請求項１】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当装置において、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得する情報取得手段と、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行う第１の無線リソース割当手段と、
前記第１の無線リソース割当手段で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行う第２の無線リソース割当手段と、
を備えたことを特徴とする無線リソース割当装置。
【請求項２】
前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項３】
前記要求条件に基づいた要求転送速度に対する、無線リソース割当によって得られる転送速度と微小値の和の割合によって、満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項４】
送信すべき情報量の初期値と送信すべき情報量の残りとの比率をもとにして満足度関数の値を算出する満足度関数演算手段を備えたことを特徴とする請求項１に記載の無線リソース割当装置。
【請求項５】
前記満足度関数演算手段は、遅延デッドラインまでの残り時間の割合をさらに加味して満足度関数の値を算出することを特徴とする請求項２から４のいずれか１項に記載の無線リソース割当装置。
【請求項６】
前記情報取得手段は、各端末のサービス毎に前記要求条件を取得することを特徴とする請求項１から５のいずれか１項に記載の無線リソース割当装置。
【請求項７】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当方法であって、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、
未割当として残っている余剰無線リソースがあるか判断するステップと、
前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、
を含むことを特徴とする無線リソース割当方法。
【請求項８】
各端末が自己に割り当てられた無線リソースを使用して基地局と無線通信する無線システムにおける無線リソース割当処理を行うためのコンピュータプログラムであって、
各端末から、アプリケーションデータが格納されたパケットの伝送遅延に関する要求条件を取得するステップと、
前記要求条件に関する満足度を表す満足度関数の最小値を最大化するように、無線リソースの割当を行うステップと、
未割当として残っている余剰無線リソースがあるか判断するステップと、
前記無線リソース割当で求められた最低の満足度を維持しながら、余剰無線リソースの割当を行うステップと、
をコンピュータに実行させるためのコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−２０６３１６（Ｐ２０１０−２０６３１６Ａ）
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願番号】特願２００９−４７２１９（Ｐ２００９−４７２１９）
【出願日】平成２１年２月２７日（２００９．２．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願日】平成２１年２月２７日（２００９．２．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]