(57)【特許請求の範囲】
【請求項１】
直交周波数分割多元接続（ＯＦＤＭＡ）方式の通信システムでフレームを組み立てる方法において、
ブロードキャスト局から受信機へ送信されるべきデータパケットには、ＯＦＤＭＡフレームの２つの次元すなわち時間および周波数に関して矩形の形状が与えられ、
単一のデータパケットのみを含むか、または、複数の連接されたデータパケットを含むかのいずれかであるバーストが生成され、該バーストがフレーム組み立てスケジューラによってＯＦＤＭＡフレームに順次はめ込まれ、
前記ＯＦＤＭＡフレームの充填プロセスが、前記ＯＦＤＭＡフレーム内の現在の空きスペースを表す矩形データ構造体の順序リストに基づき、
ＯＦＤＭＡのスロットおよびサブチャネルに関する前記バーストの矩形整形または寸法調整が、最大の残り空き矩形のサイズが最大化されるように実行される
ことを特徴とする、直交周波数分割多元接続（ＯＦＤＭＡ）方式の通信システムでフレームを組み立てる方法。
【請求項２】
送信されるべきデータパケットが、前記ＯＦＤＭＡフレームに割り当てられる前に、緊急データパケットと非緊急データパケットに分割されることを特徴とする請求項１に記載の方法。
【請求項３】
緊急データパケットが最初に割り当てられ、前記ＯＦＤＭＡフレームの残りスペースが、非緊急データパケットを割り当てるために使用されることを特徴とする請求項２に記載の方法。
【請求項４】
データパケットが、前記ＯＦＤＭＡフレームに割り当てられる前に、連接されてバーストにされることを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
相異なるコネクションからのデータパケットの連接が、それらの変調符号化方式に従って実行されることを特徴とする請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
データパケットの連接が、緊急データパケットと非緊急データパケットとで別個に実行されることを特徴とする請求項２ないし５のいずれか１項に記載の方法。
【請求項７】
バーストの最大許容サイズを指定するしきい値が適用されることを特徴とする請求項４ないし６のいずれか１項に記載の方法。
【請求項８】
データパケット／バーストが、最大のデータパケット／バーストから開始してそれらのサイズによる降順で前記ＯＦＤＭＡフレーム内に充填されることを特徴とする請求項１ないし７のいずれか１項に記載の方法。
【請求項９】
あるデータパケット／バーストを配置した後の前記ＯＦＤＭＡフレームの残りの空きスペースが、空き矩形のセットへと断片化解消されることを特徴とする請求項１ないし８のいずれか１項に記載の方法。
【請求項１０】
前記ＯＦＤＭＡフレーム内の現在の空きスペースを表すデータ構造体の前記リストが、サイズの昇順で空き矩形の前記セットを含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記ＯＦＤＭＡフレームに配置されるべき次のデータパケット／バーストの充填領域が、該データパケット／バーストを入れることができる最小の空き矩形として、前記リストから選択されることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記データパケット／バーストが、前記選択された充填領域の右上隅に配置されることを特徴とする請求項１１に記載の方法。
【請求項１３】
データパケット／バーストを縦または横のどちら向きに配置するかの決定は、結果として生じる断片化解消された空き矩形ができるだけ大きいサイズの矩形を含むように行われることを特徴とする請求項９ないし１２のいずれか１項に記載の方法。
【請求項１４】
最大の残り空き矩形のサイズが最大化されるように、データパケット／バーストの矩形整形が実行されることを特徴とする請求項９ないし１３のいずれか１項に記載の方法。
【請求項１５】
データパケット／バーストの前記矩形整形は、パディングが所定しきい値以下に抑えられるように実行されることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記ＯＦＤＭＡフレーム内へのデータパケット／バーストの割当てを開始する前に、ＦＣＨ、ＵＬ−ＭＡＰ、およびＤＬ−ＭＡＰが、前記ＯＦＤＭＡフレームの左上隅に配置されることを特徴とする請求項１ないし１５のいずれか１項に記載の方法。
【請求項１７】
前記ＯＦＤＭＡフレーム内へのデータパケット／バーストの割当てを開始する前に、ＤＬ−ＭＡＰの初期サイズのヒューリスティック値の計算のために、仮想的充填が実行されることを特徴とする請求項１ないし１６のいずれか１項に記載の方法。
【請求項１８】
ＤＬ−ＭＡＰを増大させるのに十分なスペースが存在しない場合に、前記ＯＦＤＭＡフレーム充填プロセスを終了することを特徴とする請求項１ないし１７のいずれか１項に記載の方法。
【請求項１９】
残りのデータパケット／バーストのいずれを割り当てるのに要するユニット数も、最大の空き矩形のサイズより大きい場合に、前記ＯＦＤＭＡフレーム充填プロセスを終了することを特徴とする請求項１ないし１８のいずれか１項に記載の方法。
【請求項２０】
前記ＯＦＤＭＡフレーム充填プロセスの終了後、充填されたデータパケット／バーストの配列および未充填のデータパケット／バーストの配列が生成されることを特徴とする請求項１ないし２０のいずれか１項に記載の方法。
【請求項２１】
通信システム、特に請求項１ないし２０のいずれか１項に記載の方法を実行する通信システムにおいて、
データパケットを直交周波数分割多元接続（ＯＦＤＭＡ）方式で受信機へ送信するブロードキャスト局と、
送信されるべきデータパケットにＯＦＤＭＡフレームの２つの次元すなわち時間および周波数に関して矩形の形状を与えるデータパケット整形部と、
送信されるべきデータパケットをＯＦＤＭＡフレームに順次はめ込むフレーム組み立てスケジューラと
を備え、
単一のデータパケットのみを含むか、または、複数の連接されたデータパケットを含むかのいずれかであるバーストが生成され、該バーストがフレーム組み立てスケジューラによってＯＦＤＭＡフレームに順次はめ込まれ、
前記フレーム組み立てスケジューラは、前記ＯＦＤＭＡフレーム内の現在の空きスペースを表す矩形データ構造体の順序リストに基づいて前記ＯＦＤＭＡフレームの充填プロセスを実行するように構成され、
ＯＦＤＭＡのスロットおよびサブチャネルに関する前記バーストの矩形整形または寸法調整が、最大の残り空き矩形のサイズが最大化されるように実行される
ことを特徴とする通信システム。
【請求項２２】
前記フレーム組み立てスケジューラが、相異なるコネクションからのデータパケットを単一のバーストへと連接することができるように構成されることを特徴とする請求項２１に記載の通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、直交周波数分割多元接続（ＯＦＤＭＡ）方式の通信システムでフレームを組み立てる方法に関する。ブロードキャスト局から受信機へ送信されるべきデータパケットには、ＯＦＤＭＡフレームの２つの次元すなわち時間および周波数に関して矩形の形状が与えられ、データパケットはフレーム組み立てスケジューラによってＯＦＤＭＡフレームに順次はめ込まれる。
【０００２】
また、本発明は、通信システムに関する。該通信システムは、データパケットを直交周波数分割多元接続（ＯＦＤＭＡ）方式で受信機へ送信するブロードキャスト局と、送信されるべきデータパケットにＯＦＤＭＡフレームの２つの次元すなわち時間および周波数に関して矩形の形状を与えるデータパケット整形部と、送信されるべきデータパケットをＯＦＤＭＡフレームに順次はめ込むフレーム組み立てスケジューラとを備える。
【背景技術】
【０００３】
ＯＦＤＭＡ（直交周波数分割多元接続）は、多数の密集した直交サブキャリアの使用に基づくデータ伝送のための、現在広く知られている技術である。特に、無線通信システムにおいて、ＯＦＤＭＡはますます普及しており、今後の４Ｇ標準の候補と目されている。
【０００４】
無線通信システムにおけるＯＦＤＭＡの応用の一例として、ＷｉＭＡＸが挙げられる。ＷｉＭＡＸは World Wide Interoperability for Microwave Access の略で、ＩＥＥＥ８０２．１６の標準ファミリに基づいている。ＷｉＦｉアライアンスがＩＥＥＥ８０２．１１無線ＬＡＮ標準の相互運用可能な実装を認証しているのと同様に、ＷｉＭＡＸフォーラムが、ＩＥＥＥ８０２．１６無線標準の相互運用可能な実装を認証している。
【０００５】
ＷｉＭＡＸにおいて、ダウンリンク方向でのフレーム充填プロセスは、フレーム組み立てスケジューラ（以下、ダウンリンクＭＡＰ（ＤＬ−ＭＡＰ）スケジューラと称する）によって実行される。ＤＬ−ＭＡＰスケジューラの仕事は、与えられたビットサイズのダウンリンクデータパケット、いわゆるＭＰＤＵ（MAC Protocol Data Unit）を、ＷｉＭＡＸフレームのダウンリンク部分に割り当てることである。現行の２つのＷｉＭＡＸ標準であるＩＥＥＥ８０２．１６−２００４および８０２．１６ｅ−２００５によれば、ＷｉＭＡＸフレームは特定の２次元領域からなり、ＷｉＭＡＸフレームの２つの次元は、スロット（時間）およびサブチャネル（周波数）の形で与えられる。
【０００６】
ＤＬ−ＭＡＰスケジューラのタスクは、２つの基本的なサブタスクに分解することができる。第１に、前述のＭＰＤＵを矩形形状（ＷｉＭＡＸ標準においてバーストとして規定される）にはめ込まなければならない。この際、特定のＭＣＳ（変調符号化方式）が適用されることになる。単一のバースト内で相異なるコネクション識別子（connection identifier, ＣＩＤ）に属するＭＰＤＵを連接することにより、ＤＬ−ＭＡＰサイズによるシグナリングオーバーヘッドを低減することができる。第２に、これらのバーストを矩形のＷｉＭＡＸダウンリンクフレーム内に充填することで、未使用スペースを最小化する。これにより、無線リソースがより良好に活用される。
【０００７】
前述した現行の２つのＷｉＭＡＸ標準は、基地局（およびそれぞれのＤＬ−ＭＡＰスケジューラ）が上記のタスクをどのように実現すべきかについて、何ら指針を提供していない。システムのパフォーマンスは、ＤＬ−ＭＡＰスケジューラアルゴリズムに強く依存する。というのは、それは無線リソースがどのくらい効率的に使用されるかを決定するからである。フレーム組み立てスケジューラの効率は、フレーム組み立ての終了時に残される空きスペースのサイズと、対象領域に矩形をはめ込むために必要とされるパディングの量とによって決定される。空きスペースおよびパディングは、無駄な無線リソース（すなわち帯域幅）である。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
したがって、本発明の目的は、頭書のような方法および通信システムにおいて、ＯＦＤＭＡフレーム内の空きスペースおよびパディングに関して無線リソース使用効率を向上させるとともに、フレーム組み立てスケジューラに要求される複雑さを最小化するような改良およびさらなる展開を行うことである。
【課題を解決するための手段】
【０００９】
本発明によれば、上記の目的は、請求項１の構成を有する方法によって達成される。この請求項に記載の通り、本方法は、ＯＦＤＭＡフレームの充填プロセスが、ＯＦＤＭＡフレーム内の現在の空きスペースを表すデータ構造体の順序リストに基づくことを特徴とする。
【００１０】
また、上記の目的は、請求項２１の構成を有する通信システムによって達成される。この請求項に記載の通り、本通信システムは、フレーム組み立てスケジューラが、ＯＦＤＭＡフレーム内の現在の空きスペースを表すデータ構造体の順序リストに基づいて、ＯＦＤＭＡフレームの充填プロセス実行するように構成されることを特徴とする。
【００１１】
本発明によって認識されたこととして、フレーム組み立てスケジューラに要求される複雑さは、２次元充填問題を探索問題に変換することによって低減することができる。ＤＬ−ＭＡＰスケジューラが準拠しなければならない厳格な時間的限界のため、全数探索は実行可能でない。実際、フレーム組み立て手続きは、ＷｉＭＡＸフレーム期間内に実行する必要がある。これを考慮して、ヒューリスティックメトリックを用いた欲張り探索が最適解であることが認識された。この目的のため、本発明は、ＯＦＤＭＡフレームの割当てプロセスが、データ構造体の順序リストに基づくようにすることを提案する。このデータ構造体は、ＯＦＤＭＡフレーム内の現在の空きスペースを表す。認識されたこととして、上記リストを用いることにより、ＯＦＤＭＡフレームに矩形データパケットを割り当てる問題が高効率で解決できる。上記リストの使用により、各データパケットについて、すべての実行可能な寸法置換を考慮することが可能となり、すべての可能な矩形形状を活用することにつながる。
【００１２】
有利な実施形態によれば、ＯＦＤＭＡフレームにおけるデータパケットの割当てを開始する前に、送信されるべきデータパケットが緊急データパケットと非緊急データパケットに分割される。結果として、ＯＦＤＭＡフレームに十分な空きスペースが存在する確率を増加させるために最初に緊急データパケットが割り当てられるので、例えば時間重視のアプリケーションに関して、サービス品質（ＱｏＳ）要求を満たすことができる。他方、すべての緊急データパケットを配置した後に、非緊急データパケットのすべてを割り当てるためには十分なスペースが残っていないことが起こり得る。しかし、非緊急データパケットは時間重視のアプリケーションには関係していないので、後続のＯＦＤＭＡフレームで送信しても問題がない。
【００１３】
一般に、好ましい実施形態によれば、データパケットは、ＯＦＤＭＡフレームに割り当てられる前に、連接されてバーストにされる。ここで連接とは、相異なるデータパケットを単一のバーストにまとめることを意味する。ＷｉＭＡＸの場合、相異なるコネクション識別子（ＣＩＤ）に属するデータパケットを連接して単一のバーストにすることは、それらの変調符号化方式ＭＣＳに従って実行することができる。以下では、簡単のため、連接されたデータパケットも、（連接を受けていない）個々のデータパケットも、同様にバーストと称することにする。
【００１４】
連接メカニズムを適用することにより、ＤＬ−ＭＡＰサイズによるシグナリングオーバーヘッドを低減することができる。緊急データパケット／バーストおよび非緊急データバーストが混在しないことを保証するためには、緊急データパケットに対する連接と非緊急データパケットに対する連接とを別個に実行すると有利であることがわかる。さらに、バーストの最大許容サイズを指定するしきい値を適用してもよい。これにより、極端に大きいサイズのバーストが回避される。そのような大きいバーストは割り当てるのが困難な場合があるので、これが有益であることがわかる。
【００１５】
別の有利な態様として、緊急バーストは、バーストのサイズに基づく一定の順序に従ってＯＦＤＭＡフレーム内に割り当ててもよい。好ましくは、アルゴリズムは最大のバーストから開始される。というのは、ＯＦＤＭＡフレーム内の残りの空きスペースが小さくなるほど、より大きいバーストを配置するための十分大きいスペースを見出すことはますます困難になるからである。すべての緊急バーストを割り当てた後、非緊急とみなされたバーストを、緊急バーストに関して前述したのと同じ一定の時間順序を適用して、割り当てることができる。
【００１６】
好ましい実施形態によれば、あるバーストを配置した後のＯＦＤＭＡフレームの残りの空きスペースが、空き矩形のセットへと断片化解消される。有利な態様として、ＯＦＤＭＡフレーム内の現在の空きスペースを表すデータ構造体の上記リストは、サイズの昇順で空き矩形の上記セットを含む。このような場合、ＯＦＤＭＡフレーム内に割り当てられるべき次のバーストの充填領域は、当該バーストを入れることができる最小の空き矩形として、上記リストから選択することができる。このような実施形態の利点として、大きい残り空き矩形がなるべく影響を受けないようにされることにより、ＯＦＤＭＡフレーム内に割当て可能なバーストの数が増加することがある。
【００１７】
割当てプロセスの具体的構成に関して、バーストは常に、それぞれの選択された充填領域の右上隅に配置されるとよい。断片化解消された空き矩形のリストからある矩形を充填領域として選択し、選択された充填領域内のどこにバーストを置くべきかがわかった後に、バーストを縦横どちら向きに置くかという問題が残る。効率を高めるためには、結果として生じる断片化解消された空き矩形のサイズが最大化されるような決定を行う。基本的に、ＯＦＤＭＡフレームを受信してフレームからバーストを抽出しなければならない端末での電力を節減するためには、時間方向に薄い矩形を用いた配置が好ましい。
【００１８】
なお、一般に、事前に既知であるのは、割り当てられるべきバーストのサイズ、すなわちＯＦＤＭＡフレーム内のバーストに必要とされるユニット数のみである。これに対して、バーストの実際の（ＯＦＤＭＡフレームのスロットおよびサブチャネルに関する）形状あるいは寸法は、いかなる形でも事前に決定されず、自由に選択され得る。その限りにおいて、各バーストごとに特定の形状を決定する必要があるので、バーストを縦横どちら向きに割り当てるべきかという上記の問題はより複雑になることがわかる。この問題に対処し、割当てプロセスの効率をさらに向上させるためには、最大の残り空き矩形のサイズが最大化されるように、バーストの矩形整形を実行する。これは、割り当てられるべきバーストのすべての可能な矩形形状に対して、断片化解消された空き矩形のセットを計算することを意味する。断片化解消された最大の残り空き矩形を結果として生じる形状が、当該バーストに対する充填領域として選択される。好ましい実施形態では、パディングも整形プロセスにおいて考慮される。
【００１９】
整形プロセスの一例を挙げるため、２６ユニットのバーストを考える。パディングを含む実際のバーストの（スロットおよびサブチャネルに関する）寸法あるいは形状に対する選択肢は以下の通りである。１（スロット）×２６（サブチャネル）でパディングなし、２×１３でパディングなし、３×１０でパディングが４ユニット、４×７でパディングが２ユニット、５×６でパディングが４ユニット。もちろん、さらに多くの選択肢が存在するが、それらはすべて、より多くのユニットのパディングを含む。ＯＦＤＭＡスペース内で不必要にスペースを浪費することになる余計なパディングを回避するため、許容されるパディングの最大ユニット数に関する所定しきい値を指定してもよい。その場合、そのしきい値によって指定されるより多くのパディングを必要とする実際のバーストの形状／寸法に対する選択肢は無視してよい。
【００２０】
ＯＦＤＭＡフレーム内でのバーストの割当てを開始する前に、ＯＦＤＭＡフレームの固定オーバーヘッドを割り当ててもよい。このオーバーヘッドは、ＦＣＨ（フレーム制御ヘッダ）、ＵＬ−ＭＡＰ（アップリンクＭＡＰ）、およびＤＬ−ＭＡＰ（ダウンリンクＭＡＰ）を含む。オーバーヘッドは、全ユーザによって復号されるブロードキャスト情報を含むので、常に最初に配置される。ＦＣＨは、与えられたＯＦＤＭＡシステムに対して固定長であるが、ＵＬ−ＭＡＰおよびＤＬ−ＭＡＰのサイズは必ずしもあらかじめ既知ではない。というのは、例えばＤＬ−ＭＡＰの場合、それは連接プロセスと、ＯＦＤＭＡフレーム内に割り当てられるバーストの数とに依存するからである。
【００２１】
このため、現実の割当てプロセスを開始する前に、バーストの仮想的充填を実行すると有利であることがわかる。仮想的充填により、ＤＬ−ＭＡＰの初期サイズに対するヒューリスティック値を計算することができる。この値に基づいて、現実の割当てプロセスを開始すればよい。すなわち、仮想的充填において、２次元充填問題が、より単純な１次元充填に帰着される。仮想的充填は、ＯＦＤＭＡフレームに十分なスペースが存在する限りパケットを充填し、与えられたバーストのサイズがフレーム内の残りのスペースよりも大きい場合（ＦＣＨ  ＋  ＵＬ−ＭＡＰ  ＋  ＤＬ−ＭＡＰ  ＋  Σｂｕｒｓｔｉ  ＜  Ｃｆｒａｍｅ）に停止する。こうして決定されたバーストに対して、要求されるＤＬ−ＭＡＰのサイズが計算され、現実の２ｄ充填に対する初期概算値として使用される。
【００２２】
割当てプロセス全体を通じて、ＤＬ−ＭＡＰの初期サイズが不十分であり、より多くのスペースがＤＬ−ＭＡＰに必要とされることがわかった場合、可能であればこれを増大させてもよい。ＤＬ−ＭＡＰを十分に増大させるだけのスペースが存在しないことは、割当てプロセスを終了する２つの場合のうちの１つである。割当てプロセスを終了しなければならない第２の場合は、残りのどのデータパケットあるいはバーストを割り当てるのに要するユニット数も、最大空き矩形のサイズよりも大きいときである。
【００２３】
割当てプロセスを終了後、充填されたデータパケット／バーストの配列および未充填のデータパケット／バーストの配列を生成してもよい。充填されたデータパケット／バーストの場合、フレーム内でのバーストの位置を返してもよい。
【００２４】
不必要な繰り返しを避けるため、本発明による通信システムの有利な実施形態に関しては、上記の本発明による方法の有利な実施形態を参照されたい。
【００２５】
本発明を有利な態様で実施するにはいくつもの可能性がある。このためには、請求項１および２１に従属する諸請求項を参照しつつ、図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００２６】
【図１】ＯＦＤＭＡフレームの一例の模式図であり、データパケット連接メカニズムを例示する図である。
【図２ａ】本発明の一実施形態による例示的な割当てプロセスを示す。
【図２ｂ】本発明の一実施形態による例示的な割当てプロセスを示す。
【図２ｃ】本発明の一実施形態による例示的な割当てプロセスを示す。
【発明を実施するための形態】
【００２７】
図１に、時間（スロット）および周波数（サブチャネル）をその２つの次元とする代表的なＯＦＤＭＡフレームを示す。また、図１は一般的に、本発明に関して適用可能な連接メカニズムを例示している。原理的には、各データパケットは、個別にＯＦＤＭＡフレーム内に割り当てられる。しかし、連接メカニズムを適用することにより、相異なるコネクションからの２個以上のデータパケットを連接してバーストとすることが可能であり、そしてこれをまるごとＯＦＤＭＡフレーム内に割り当てることができる。例えば、図１に示す実施形態によれば、バーストＢ１は２個の連接されたデータパケットを含む。一方のデータパケットはコネクション識別子ＣＩＤ１のコネクションから、もう一方のデータパケットはＣＩＤ３のコネクションからのものである。以下の説明では、簡単のため、「バースト」という場合には、上記のような連接されたデータパケットとしてのバーストに加えて、連接されていない個々のデータパケットをも指すものとする。
【００２８】
図２を参照して、ＯＦＤＭＡフレーム割当てのプロセスを説明する。与えられている例では、ＯＦＤＭＡフレーム内に割り当てられるべきバーストは全体として３個のバースト、すなわちバーストＢ１、Ｂ２およびＢ３のみからなる。しかし、現実の状況では通常、より多くのバーストが１つのＯＦＤＭＡフレーム内に割り当てられるであろう。
【００２９】
図２の例で考察されるＯＦＤＭＡフレームは、（周波数軸上に）３０個のサブチャネルおよび（時間軸上に）６０個のスロットを含む。したがって、充填スペース全体で３０×６０＝１８００ユニットの面積を有する。
【００３０】
図２ａは、最初のバーストの割当てを例示している。バーストはそのサイズに関して降順で充填されるので、割り当てられるべき最初のバーストは、２４０ユニットを有する最大のバーストＢ３である。バーストは常に、選択された充填領域の右上隅に充填される。この充填領域は、最初のバーストの場合、固定オーバーヘッドに必要とされるスペースを除いて、ＯＦＤＭＡフレーム全体である。固定オーバーヘッドは、ＦＣＨ、ＵＬ−ＭＡＰおよびＤＬ−ＭＡＰを含むが、分かりやすくするために、図２では省略している。上記のオーバーヘッド部分は、フレームの最初に配置されるので、ＯＦＤＭＡフレームの左上隅から開始される。
【００３１】
なお、事前には、バーストのサイズ、すなわち割当てに必要なユニット数のみが既知である。しかし、バーストの最適な形状／寸法、すなわち、ＯＦＤＭＡフレームのスロットとサブチャネルの間でユニットがどのように分配されるか、を評価しなければならない。本発明の好ましい実施形態によれば、この評価は、バーストの配置後に最も大きい空き矩形が最大化するように実行される。
【００３２】
図２ａに示す具体例では、バーストＢ３の最適寸法は３０サブチャネル×８スロットである。このような分配により、結果として生じたＯＦＤＭＡフレームの空きスペースを完全にカバーするただ１つの空き矩形が得られる。図２ａでは、この矩形は破線のフレームで示され、Ｒ１ａとして表されている。バーストＢ３をこのように配置した後、残り空き矩形のリストをサイズの昇順に並べる。残り空き矩形として存在するのは１つの矩形Ｒ１ａだけであるので、上記リストは、サイズが３０×５２＝１５６０ユニットのＲ１ａのみを含むことになる。
【００３３】
図２ｂを参照すると、次のバースト、すなわちバーストＢ１が、ＯＦＤＭＡフレーム内に割り当てられる。上記のように、残り空き矩形のリストは、エントリＲ１ａのみを含む。図２ｂは、全面積が１２０ユニットのバーストＢ２をどのように割り当てるべきかについて、２つの異なる可能性を例示している。図２ｂの上側には、１５×８の分配が示されている。バーストＢ２のこのような割当ての結果として、２個の空き矩形Ｒ２ａおよびＲ２ｂ（今度も破線フレームで示す）が得られる。これらの矩形は、残り空きスペース全体を断片化解消することによって得られる。空き矩形Ｒ２ａおよびＲ２ｂのそれぞれの面積を計算することにより、矩形Ｒ２ａは面積が３０×４４＝１３２０ユニットであり、矩形Ｒ２ｂは面積が１５×５２＝７８０ユニットであることがわかる。図２ｂの下側の割当てでは、２個の断片化解消された矩形Ｒ２ｃおよびＲ２ｄが得られ、その面積は、Ｒ２ｃが３０×３７＝１１１０ユニット、Ｒ２ｄが２２×５２＝１１４４ユニットとなる。
【００３４】
このプロセスを、すべての寸法置換、すなわち１×１２０、２×６０、３×４０、４×３０等々に対して実行する。なお、パディングを必要とする置換も考慮に入れる。本具体例では、例えば、７×１７でパディングが１ユニットという組合せや、９×１３でパディングが３ユニットという組合せが該当する。それぞれの場合について、断片化解消された残り空き矩形のサイズを計算する。結果として最大の空き矩形を生じる組合せを選択する。与えられた例では、図２ｂの上側に例示した組合せの結果として最大の空き矩形が得られる。これは、サイズが３０×４４＝１３２０ユニットの矩形Ｒ２ａである。その結果、ＯＦＤＭＡフレーム内の現在の空きスペースを表すデータ構造体の更新されたリスト（これは、断片化解消された空き矩形をサイズの昇順に並べたセットを含む）は、１番目の位置に矩形Ｒ２ｂ、２番目の位置に矩形Ｒ２ａを含むことになる。
【００３５】
図２ｃには、次のバーストであるバーストＢ２の割当てを例示している。実際の空き矩形（いまの場合、上記で説明したように、矩形Ｒ２ｂおよびＲ２ａを含む）のセットから、割り当てられるべきバーストを入れることができる最小の矩形を、当該バーストに対する充填領域として選択する。バーストＢ２は３０ユニットしか有していないので、サイズが１１１０ユニットの矩形Ｒ２ｂが、空き矩形の現在のセットのうちでバーストＢ２を入れるのに十分に大きい最小の矩形である。したがって、バーストＢ２は、矩形Ｒ２ｂの右上隅に充填される。今度も、バーストＢ２の実際の寸法は、上記のように決定される。例示のため、２つの可能な寸法置換を図２ｃに示している。図２ｃの上側に示す（充填領域の断片化解消後の）組合せの結果として、最大の空き矩形が得られる。これを点線フレームで示し、Ｒ３ａで表している。矩形Ｒ３ａはサイズが１５×４７＝７０５ユニットである。その結果、バーストＢ３を割り当てた後、空き矩形のセットは、矩形Ｒ３ｂ（サイズ：４６８ユニット）、Ｒ３ａ（サイズ：７０５ユニット）、およびＲ２ａ（サイズ：１３２０ユニット）を含むように更新される。
【００３６】
現実の応用場面では、より多くのバーストがＯＦＤＭＡフレーム内に割り当てられるであろう。各バーストごとに、割当てプロセスは、バーストＢ１、Ｂ２、およびＢ３の割当てに関して上記で説明したのと同じ規則に従うことになる。いずれの残りのバーストに要求されるユニット数も最大の空き矩形のサイズより大きい場合、割当てプロセスは終了する。
【００３７】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと理解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
0005405479.tif 000002
【図２ａ】
0005405479.tif 000003
【図２ｂ】
0005405479.tif 000004
【図２ｃ】
0005405479.tif 000005