(57)【要約】  ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）フレームをパックするための方法であって、ＷｉＭＡＸフレームとほぼ同じ数の行および列のマトリクスを生成するステップと、第１の制御メッセージをマトリクスの第１の隅内のある位置にマッピングするステップと、第１のデータ・メッセージをマトリクスの第２の隅内のある位置にマッピングするステップであって、第２の隅が第１の隅の方を向いている所定の方向で対向するステップと、他のデータ・メッセージのうちの１つ以上が、他の制御メッセージのうちの１つ以上と一致するまで、複数の他の制御メッセージをマトリクスの中心の方向に第１の隅から移動する第１の方向に、マトリクスにマッピングするステップと、複数の他のデータ・メッセージを、マトリクスの中心の方向に、マトリクスの第２の隅から第１の方向とは異なる第２の方向にマトリクスにマッピングするステップと、マトリクスからの制御メッセージをＷｉＭＡＸフレームの第１の領域にコピーするステップと、第１の制御メッセージがフレームの開始のところに位置するように、ＷｉＭＡＸフレーム内に制御メッセージを配置するステップと、第１のデータ・メッセージが制御メッセージの直後に位置するように、マトリクスからのデータ・メッセージをＷｉＭＡＸフレームの第２の領域にコピーするステップとを含むことを特徴とする方法。
2010524321.tif 000002
【特許請求の範囲】
【請求項１】
ＯＦＤＭシンボルを含むサブチャネルおよびタイムスロット内にグループ分けしたサブキャリアを含むＯＦＤＭＡ／ＴＤＭＡフレームをパックするための方法であって、前記ＯＦＤＭＡ／ＴＤＭＡフレームが、前記サブチャネルに対応する行および前記ＯＦＤＭシンボル（６２）に対応する列を含むマトリクスとしてモデル化され、前記方法が、
同じ数の行および列を有するマトリクス（６０）を前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）として生成するステップと、
第１の制御メッセージを前記マトリクス（６０）の第１の隅（７０）内のある位置にマッピングするステップと、
第１のデータ・メッセージを、前記マトリクス（６０）の第２の隅（７２）内のある位置にマッピングするステップであって、前記第２の隅（７２）が前記第１の隅（７０）への所定の方向において対向するステップと、
前記他のデータ・メッセージのうちの１つ以上が、前記他の制御メッセージのうちの１つ以上と一致するまで、前記マトリクス（６０）の中心に向かって、前記第１の隅（７０）から移動する第１の方向へ、前記マトリクス（６０）に複数の他の制御メッセージをマッピングし、前記マトリクス（６０）の中心に向かって、前記マトリクス（６０）の前記第２の隅（７２）から前記第１の方向とは異なる第２の方向へ、前記マトリクス（６０）に複数の他のデータ・メッセージをマッピングするステップと、
前記制御メッセージを、前記マトリクス（６０）から前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）の第１の領域にコピーするステップと、
前記第１の制御メッセージが、前記フレーム（６２）の開始のところに位置するように、前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）内に前記制御メッセージを配置するステップと、
前記第１のデータ・メッセージが、前記制御メッセージの直後に位置するように、前記データ・メッセージを前記マトリクス（６０）から前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）の第２の領域にコピーするステップと、
を含む方法。
【請求項２】
前記方法が、
所与のデータ・メッセージを収容できる十分な大きさの区画が存在するか否かを判別するために、前記マトリクス内の区画をチェックするステップ（８２）と、
前記区画が前記データ・メッセージを収容できる大きさのものである場合に、前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージをある区画にマッピングするステップと、
前記データ・メッセージを収容できる大きさの区画を発見できなかった場合に、前記マトリクス内の空き領域内に、前記データ・メッセージを十分収容できる大きさの新しい区画を生成するステップと、
前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージを前記新しい区画にマッピングするステップと、
前記マッピング・プロセスの結果に関するメッセージを返送するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記方法が、
所与のデータ・メッセージを十分収容することができる大きさの区画が存在するか否かを判別するために、前記マトリクス内の区画をチェックするステップ（６６）と、
前記区画が前記データ・メッセージを十分収容することができる大きさのものである場合に、前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージをある区画にマッピングするステップ（６８）と、
前記データ・メッセージ全体を収容することができる十分な大きさの区画を発見できなかった場合に、データ・メッセージのどの部分を最大の区画内に収容することができるかを判別するステップと、
前記一部のための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージの前記一部を前記最大の区画にマッピングするステップ（６８）と、
前記マトリクスの空き領域内に、前記データ・メッセージの残りの部分を収容するのに十分な大きさの新しい区画を生成するステップ（７０）と、
前記データ・メッセージの前記残りの部分のための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージの前記残りの部分を前記新しい区画にマッピングするステップと、
前記マッピング・プロセスの結果に関するメッセージを返送するステップ（７２）と、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記方法の後に、前記ＯＦＤＭＡ／ＴＤＭＡフレーム内で前記区画のさらなる最適化が行われる、前記請求項のいずれか１項に記載の方法。
【請求項５】
前記最適化が、データ・メッセージの少なくともいくつかを、前記ＯＦＤＭＡ／ＴＤＭＡフレームの前記第１の領域の少なくとも一部内に移動し、前記ＯＦＤＭＡ／ＴＤＭＡフレームの前記第２の領域内の空きスペースに移動するステップを含む、請求項４に記載の方法。
【請求項６】
前記最適化が、前記ＯＦＤＭＡ／ＴＤＭＡフレーム内の空き領域に隣接するデータ・メッセージを延長するステップを含む、請求項４に記載の方法。
【請求項７】
前記データ・メッセージが、前記ＯＦＤＭＡ／ＴＤＭＡフレームのＭＡＣ層からのサービス・データ・ユニット（ＳＤＵ）を含み、前記マトリクスに前記データ・メッセージをマッピングする前記ステップの前に、前記ＳＤＵがプロトコル・データ・ユニット（ＰＤＵ）内にカプセル化される、前記請求項のいずれか１項に記載の方法。
【請求項８】
前記方法が、前記データ・メッセージを前記マトリクスにマッピングする前に、同じ機能を共有するデータ・メッセージをグループ分けするステップを含む、前記請求項のいずれか１項に記載の方法。
【請求項９】
ＯＦＤＭシンボルを含むサブキャリアおよびタイムスロットにグループ分けされているサブキャリアを含むＯＦＤＭＡ／ＴＤＭＡフレームをパックするための方法で使用するためのデータ構造であって、前記ＯＦＤＭＡ／ＴＤＭＡフレームが、前記サブチャネルに対応する行および前記ＯＦＤＭシンボル・フレーム（６２）に対応する列を含むマトリクスとしてモデル化され、前記データ構造が、
・前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）と同じ数の行と列とを有するマトリクス（６０）内の多数のスロットのインジケータと、
・前記マトリクス（６０）のダウンリンク・データ領域の幅のインジケータと、
・制御メッセージまたはデータ・メッセージを収容するための前記マトリクス（６０）内の第１の使用可能な区画のインジケータと、
前記マトリクス（６０）内のもっとも最近生成された区画のインジケータと、
前記マトリクス（６０）内のある区画の幅のインジケータと、
前記マトリクス（６０）内のある区画の位置のインジケータと、
を備え、使用中、前記インジケータが、
第２の隅（７２）が前記第１の隅（７０）に向かって所定の方向に対向している場合に、前記マトリクス（６０）の前記第１の隅（７０）内のある位置に第１の制御メッセージのマッピング、および前記マトリクス（６０）の前記第２の隅（７２）内のある位置に第１のデータ・メッセージのマッピング、
前記他のデータ・メッセージのうちの１つ以上が、前記他の制御メッセージのうちの１つ以上と一致するまで、前記マトリクス（６０）の中心に向かって前記第１の隅（７０）から移動する第１の方向に前記マトリクス（６０）に複数の他の制御メッセージのマッピング、および前記マトリクス（６０）の中心に向かって、前記マトリクス（６０）の前記第２の隅（７２）から前記第１の方向とは異なる前記第２の方向に、複数の他のデータ・メッセージの前記マトリクス（６０）へのマッピング、前記制御メッセージの前記マトリクス（６０）から前記ＯＦＤＭＡ／ＴＤＭＡフレームの第１の領域へのコピー、前記第１の制御メッセージが前記フレーム（６２）の開始のところに位置するように、前記制御メッセージのその内部での配置、および
前記第１のデータ・メッセージが前記制御メッセージの直後に位置するように、前記データ・メッセージの前記マトリクス（６０）から前記ＯＦＤＭＡ／ＴＤＭＡフレーム（６２）の第２の領域へのコピー
を調整するために使用されるデータ構造。
【請求項１０】
前記データ構造が、前記マトリクス内のデータ・メッセージの位置のインジケータのリストをさらに含む、請求項９に記載のデータ構造。
【請求項１１】
前記コンピュータ・システムが、請求項１〜８のいずれか１項に記載の前記方法の前記ステップを実行する手段を含むことを特徴とするコンピュータ・システム。
【請求項１２】
前記処理回路モジュールが、前記モジュールのところに到着するデータのデータ・レートとは無関係に、少なくとも１つのデータ・メッセージおよび少なくとも１つの制御メッセージを含むＯＦＤＭＡ／ＴＤＭＡフレームをパックするために、前記ＯＦＤＭＡ／ＴＤＭＡフレームを処理する、請求項９〜１０のいずれか１項に記載の手段を含むことを特徴とする無線基地局で使用するための処理回路モジュール。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）をパックするための方法、データ構造およびコンピュータ・システムに関する。
【背景技術】
【０００２】
図１を参照すると、典型的な無線通信システムは、地理的領域を、それぞれが１つ以上の基地局（ノードＢ）を含む複数のセル１０に分割する。この場合、セル１０内に位置するモバイル・ユーザ装置（ＵＥ１，ＵＥ２，ＵＥ３）は、そのセル１０の基地局（ノードＢ）と通信する。より詳細には、基地局（ノードＢ）は、無線チャネル（Ｒ１，Ｒ２，Ｒ３）を介してモバイル・ユーザ装置（ＵＥ１、ＵＥ２、ＵＥ３）との間の無線送信および受信を処理し、コアネットワーク（２０）と接続している無線ネットワーク・コントローラ（ＲＮＣ）により制御される。基地局（ノードＢ）からモバイル・ユーザ装置（ＵＥ１、ＵＥ２、ＵＥ３）への送信は、ダウンリンク送信と呼ばれる。同様に、モバイル・ユーザ装置（ＵＥ１、ＵＥ２、ＵＥ３）から基地局（ノードＢ）への送信は、アップリンク送信と呼ばれる。
【０００３】
ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）プロトコル（ＩＥＥＥ８０２．１６規格）は、時分割多元接続（ＴＤＭＡ）との組合せで直交周波数分割多元接続（ＯＦＤＭＡ）を使用する無線通信プロトコルである。直交周波数分割多重化（ＯＦＤＭ）は、高データ・レート入力データ・ストリームを、遅いデータ・レートの多数の並列サブストリームに分割する。この場合、各サブストリームは変調され、別々の直交サブキャリアにより同時に送信される。直交周波数分割多元接続（ＯＦＤＭＡ）の場合には、サブキャリアはサブチャネルにグループ分けされる。この場合、周波数選択性フェー_ジングの影響を軽減するために、所与のサブチャネル内のキャリアはチャネル・スペクトルに沿って拡散される。ハイブリッドＯＦＤＭＡ／ＴＤＭＡアプローチの場合には、送信チャネルは、周波数領域において複数のサブキャリアに分割され、時間領域において持続時間が一定のまたは可変のタイムスロットに分割される。すなわち、各タイムスロットは、（そのサイズが、送信チャネルの選択した変調／符号化方法に依存する）一定のまたは可変サイズの（ＯＦＤＭシンボルの）データ・セグメントを含む。この場合、これらのデータ・セグメント（またはスロット）は、ＭＡＣプロトコルにより管理されるＯＦＤＭＡ／ＴＤＭＡアプローチが提供するネットワーク・リソースの最小のアクセス可能な部分である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】１９７９年、Ｗ．Ｈ．Ｆｒｅｅｍａｎ  ＆  Ｃｏｍｐａｎｙ発行のＭ．ＧａｒｅｙおよびＤ．Ｊｏｈｎｓｏｎの「Ｃｏｍｐｕｔｅｒｓ  ａｎｄ  Ｉｎｔｒａｃｔａｂｉｌｉｔｙ：Ａ  Ｇｕｉｄｅ  ｔｏ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  ＮＰ−Ｃｏｍｐｌｅｔｅｎｅｓｓ」、Ｅｕｒ．Ｊ．Ｏｐｅｒ．Ｒｅｓ．、１４１（２００２）２４１−２５２掲載のＡ．Ｌｏｄｉ、Ｓ．Ｍａｒｔｅｌｌｏ、Ｍ．Ｍｏｎａｃｉ。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
図２を参照すると、ＷｉＭＡＸフレームは、ｍ個の（サブチャネルの）行およびｎ個の（シンボルの）列を含むマトリクスＭ∈Ｒｍ×ｎとしてモデル化することができる。この場合、マトリクスＭの個々の素子は、スロットｓ（ｉ，ｊ）、ｉ＝０．．．ｍ−１、およびｊ＝０．．．ｎ−１であり、この場合、ＷｉＭＡＸの物理層は、ｍおよびｎを、フレーム・マトリクスの特性の一部として提供する。実際には、各セルは波形を含んでいるのではなく、各セルはこの波形を表す係数を含み、この場合、この係数は高速フーリエ変換（ＦＦＴ）によるものである。所与の波形により符号化されたビットの数は、各波形が使用する変調符号化スキーム（ＭＣＳ）により異なる。
【課題を解決するための手段】
【０００６】
本発明は、ＷｉＭＡＸ（Ｗｏｒｌｄｗｉｄｅ  Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ  ｆｏｒ  Ｍｉｃｒｏｗａｖｅ  Ａｃｃｅｓｓ）をパックするための方法、データ構造およびコンピュータ・システムを提供する。
【０００７】
添付の図面を参照しながら、以下に本発明のいくつかの実施形態について説明するが、これは単に例示としてのものに過ぎない。
【図面の簡単な説明】
【０００８】
【図１】典型的な従来技術の無線通信システムのブロック図である。
【図２】典型的な従来技術のＯＦＤＭＡ／ＴＤＭＡフレームのブロック図である。
【図３】従来技術のＷｉＭＡＸフレームのブロック図である。
【図４】典型的な従来技術のＷｉＭＡＸプロトコル・データ・ユニット上で動作している、典型的な従来技術のスケジューラおよびフレーム・マッパのブロック図である。
【図５】図３のＷｉＭＡＸフレーム内のプロトコル・データ・ユニット（ＰＤＵ）の典型的な従来技術の粗いマッピングのブロック図である。
【図６】図３のＷｉＭＡＸフレーム内のＰＤＵの従来技術の不正確なマッピングのブロック図である。
【図７】図３のＷｉＭＡＸフレーム内のＰＤＵの従来技術の正確なマッピングのブロック図である。
【図８】図３のＷｉＭＡＸフレームをパックするための従来技術のシーケンシャルな敷設マッピング（ｓｅｑｕｅｎｔｉａｌ  ｌａｙｉｎｇ  ｍａｐｐｉｎｇ）アプローチのブロック図である。
【図９】図３のＷｉＭＡＸフレームをパックするための最後のビン・チェック・マッピング・アプローチによる従来技術のシーケンシャルな敷設のブロック図である。
【図１０】例示としての本発明のある実施形態による、実ＷｉＭＡＸフレームと仮想フレーム間のマッピングを示すブロック図である。
【図１１】図１０のマッピングの際に使用する、例示としての本発明のある実施形態による、データ構造のブロック図である。
【図１２】図１０のマッピングを行う、例示としての本発明のある実施形態による、ＦＦＲ、すなわちフレーム・マッピングＳＤＵ（）アルゴリズムのフローチャートである。
【図１３】図１２のＦＦＲアルゴリズムの数字による例で使用するフレームのブロック図である。
【図１４】図１０のマッピングを行う、例示としての本発明のある実施形態による、ＦＥＤ、すなわちフレーム・マッピングＳｅｇ（）アルゴリズムのフローチャートである。
【図１５】図１４のＦＥＤアルゴリズムの数字による例で使用するフレームのブロック図である。
【図１６】フレーム内の制御領域に隣接するビンが１つのスロットの幅を有する、例示としての本発明のある実施形態による仮想フレームのブロック図である。
【図１７】パケットをフレームの最後のビンにパックすることができない、例示としての本発明のある実施形態による仮想フレームのブロック図である。
【図１８】図３の実ＷｉＭＡＸフレームの制御領域上で帯域幅を最適化するための、例示としての本発明のある実施形態による機構のブロック図である。
【図１９】その仮想フレームの制御領域が満杯になっている、例示としての本発明のある実施形態による実ＷｉＭＡＸフレームのブロック図である。
【図２０】図３の実ＷｉＭＡＸフレームのデータ領域上で帯域幅を最適化するための、例示としての本発明のある実施形態による機構のブロック図である。
【発明を実施するための形態】
【０００９】
１．潜在的なフレーム・パッキング問題の概要
ＷｉＭＡＸ  ＭＡＣプロトコルは、ポイント・ツー・マルチポイント・ネットワーク環境の要件を処理するように設計されている。この場合、中央基地局は、複数の同時送信要求を処理する。何故なら、エア・インタフェースが基地局に送信したがっているモバイルユーザ装置（ＵＥ）間で共有されているからである。アップリンク通信はＴＤＭＡにより行われる。この場合基地局はその帯域幅要件に従って所与のＵＥに可変数のタイムスロットを割り当てる。
【００１０】
ＷｉＭＡＸは、ＷｉＭＡＸネットワーク（例えば、音声トラフィックおよびインターネット・プロトコル（ＩＰ）データ）上で送信される異なるタイプのトラフィックの要求を満たすために、２つの二重化スキーム、すなわち時分割二重（ＴＤＤ）および周波数分割二重（ＦＤＤ）を使用する。ＴＤＤの場合には、基地局は周期的にＵＥにフレームを送信する。図３を参照すると、ＷｉＭＡＸフレーム３０は、本質的には、図２のＯＦＤＭＡ／ＴＤＭＡフレーム上の延長部であることが分かる。より詳細には、ＷｉＭＡＸフレームは、ダウンリンクおよびアップリンク送信の衝突を防止するために、（ダウンリンク・トラフィックのために使用するスロットを含む）ダウンリンク・サブフレーム３２およびその後に位置するガード３４を含む。ガード３４の後には（アップリンク・トラフィック用のスロットを含む）アップリンク・サブフレーム３６が位置する。
【００１１】
ダウンリンク・サブフレーム３２は、プリアンブル３８およびフレーム制御ヘッダ（ＦＣＨ）４０からできている。ＦＣＨ４０は、ＦＣＨ４０直後の１つ以上のＤＬバースト４２のバースト・プロファイルおよび長さを指定する。ＦＣＨ４０の後においては、ダウンリンク・サブフレーム３２が、ＤＬ−ＭＡＰ４４およびＵＬ−ＭＡＰ４６を含む。ＤＬ−ＭＡＰ４４およびＵＬ−ＭＡＰ４６は、サブチャネル割当て、およびＤＬおよびＵＬサブフレーム３２、３６（例えば、基地局により所与のＵＥに割り当てられたアップリンク・タイムスロット）に対する他の制御情報をそれぞれ提供する。ＤＬ−ＭＡＰ４４およびＵＬ−ＭＡＰ４６は、また各バースト内で受信および／または送信するＵＥを指定し、各バースト内および各サブチャネルで使用する符号化および変調を指定する。アップリンク・サブフレーム３６は、範囲および帯域幅割当てのための競合区間および異なるＵＥからのデータ・バーストを含む。
【００１２】
各データ・バーストは、整数のＯＦＤＭシンボルからなっていて、バースト内で送信されるこれらデータのために使用する符号化アルゴリズム（ｃｏｄｅ  ａｌｇｏｒｉｔｈｍ）、符号化率（ｃｏｄｅ  ｒａｔｅ）および変調レベルを指定するバースト・プロファイルが割り当てられる。より詳細には、各バーストは、複数のＭＡＣ層プロトコル・データ・ユニット（ＰＤＵ）を含む。ＰＤＵは、一定の長さのヘッダ、可変長のペイロードおよび巡回冗長検査（ＣＲＣ）のためのオプションとしてのフィールドを含む。２つのタイプのＭＡＣヘッダ、すなわち、（データまたはＭＡＣメッセージを送信するために使用する）一般的なヘッダ、および広いアップリンク帯域幅を要求するために（ＵＥが使用する）帯域幅要求ヘッダが存在する。
【００１３】
要するに、サービス・データ・ユニット（ＳＤＵ）は、ＷｉＭＡＸネットワーク・モデルのもっと上のレベル（例えば、ネットワーク層）からＭＡＣレベルに到着するエンティティ（例えば、ＩＰパケット）である。ＳＤＵは、ＵＥへまたはＵＥから送信する前に、ＰＤＵ内にカプセル化しなければならない。ＰＤＵは、データ・バースト内で送信される。この場合、データ・バーストは、ＷｉＭＡＸフレーム内に１つ以上のスロットを含む。
【００１４】
図４を参照すると、ＰＤＵは、スケジューラ５０が選択したフローからのサービス・データ・ユニット（ＳＤＵ）をカプセル化する。概念的には、スケジューラ５０は、最初に、どのフローを提供すべきか、およびフローがスケジュール・アウトするバイトの数を決定する。このフローからのバイトは、トランスポートするＳＤＵを形成する。次に、フレーム・マッピング手順（すなわち、フレーム・マッパ５２）はＳＤＵを入手し、カプセル化ＰＤＵを生成し（５４）、物理層が予め定義した変調／符号化方法でＰＤＵをトランスポートすることができるようにするために、バーストにＰＤＵを格納する（５６）。
【００１５】
バースト内のバイトの数は、選択したフローに関連する変調／符号化方法に関連する。それ故、バーストの容量は、バースト毎に非常に大きく変化する場合がある。それ故、一例を挙げて説明すると、スロットが８の第１のバーストは、ＱＡＭ６４＿３４フローからのＰＤＵを含み、スロットが１２の第２のバーストは、ＱＰＳＫ＿１２フローからのＰＤＵを含んでいる。この場合、第１のバースト１は、２７ｘ８＝２１６のバイトを含み、一方、第２のバーストは、６×１２＝７２のバイトを含む。
【００１６】
フレーム・マッパ５２とスケジューラ５０との間のインタフェースは、スケジューラ５０が選択したフロー番号（またはフローを識別する待ち行列ＩＤ）、トランスポートしたいＳＤＵバイトの数、および／または上限としてトランスポートすることができるＳＤＵバイトの数を含む一組のパラメータである。スケジューラ５０からこれらのパラメータを受信すると、フレーム・マッパ５２は、要求を満たすためにその最善を尽くそうとし、実際にトランスポートするバイト数を報告する。マッピング手順中、１つ以上のバーストが選択したフローのＳＤＵに対して生成される場合がある。この場合、各バーストは、ＰＤＵ生成手順により生成したＰＤＵを運ぶ。
【００１７】
この手順は下記のように要約することができる。
１．スケジューラ５０は、フロー（例えば、フローＡ）を選択し、サービスの品質（ＱｏＳ）要件に適合するように、トランスポートするＳＤＵバイト（例えば、ｒＡバイト）の数を決定する。
【００１８】
２．スケジューラ５０は、フレーム・マッパ５２にフローＡのためにｒＡバイトを送信するように要求し、十分広い帯域幅を使用することができる場合には、フレーム・マッパ５２が、最大ＵＬＩＭのバイトをトランスポートすることができるようにする。
【００１９】
３．フレーム・マッパ５２は、使用できる帯域幅、フレームのスペースをチェックし、スケジューラの要求を満たすために最善を尽くそうとする。
４．マッピング中、使用することができる帯域幅、フレーム内のスペース、および分割／セグメント分割要件に従って、１つ以上のバーストを生成することができる。
【００２０】
５．ＰＤＵ生成手順５４は、ＳＤＵをそのＰＤＵと関連付けるために、フレーム・マッパ５２により呼び出される。
６．ＰＤＵ格納手順５６は、ＷｉＭＡＸフレーム内のＳＤＵに関連するＰＤＵバーストを格納するために、フレーム・マッパ５２により呼び出される。
【００２１】
受信者が、バーストを復号することができるようにするために、各バーストを、そのＷｉＭＡＸフレームの頭のところの短い記述オーバーヘッドと関連付けなければならない。記述オーバーヘッド（または情報素子ＩＥ）は、その対応するバーストのための復号／復調情報およびＷｉＭＡＸフレーム内のバーストの開始座標を提供する。下記の制限は、フレーム・マッパ５２の設計に重大な影響を有する。
【００２２】
（ａ）第１のバーストのＩＥは、ＦＣＨの直後のＷｉＭＡＸマトリクスの頂部の左隅に位置していなければならないし、以降のＩＥは、ＤＬ−ＭＡＰ領域を形成するために、その後で上から下に連続的に位置していなければならない。一方、ＩＥに関連するバーストは、ＷｉＭＡＸマトリクスで使用することができる任意のスペース内に設置することができる。
【００２３】
（ｂ）（以後アップリンク制御と呼ぶ）第１のバーストは、アップリンク・マップを運び、ＤＬ＿ＭＡＰ領域の直後に配置しなければならない。
（ｃ）ＰＤＵを２つのバーストに分割しなければならない場合には、第１のバーストは時間的に第２のバーストの前に置かなければならない。（例えば、第１のバーストが、ＷｉＭＡＸマトリクスの列ｎ内に位置している場合には、第２のバーストは、任意の列ｍ内に位置していなければならない。この場合、ｍ＞ｎである。
【００２４】
説明を簡単にするために、ＤＬ＿ＭＡＰ領域を以後制御領域と呼ぶことにする。説明中、ＦＣＨは除外する。何故なら、ＦＣＨは、ＷｉＭＡＸフレーム内の予め指定した一定の領域内に位置しているからである。それ故、アップリンクまたはダウンリンク・サブフレームは、効果的に制御領域とデータ領域に分割され、この場合、制御領域は、ＩＥ（または記述オーバーヘッド）を含み、データ領域は、ＩＥに関連するバーストを含んでいる。バースト・オーバーヘッド（ＩＥ）のサイズは小さいが、ＩＥ毎に異なるものであってもよい。同様に、バーストのサイズは、対応するＰＤＵのサイズにより異なる。図５を参照すると、アップリンク・マップ・バースト（ＰＤＵ１）が９のスロットを含み、ＱＡＭ６４＿３４フローからのものである場合には、バーストＰＤＵ１は、９×２７＝２４３バイトを占める。同様に、第２のバーストＰＤＵ２が１２のスロットを含み、ＱＰＳＫ＿１２フローからのものである場合には、バーストＰＤＵ２は、１２×６＝７２バイトを占める。
【００２５】
ＷｉＭＡＸフレームを効率的に使用するためには、マッパは、データ領域を制御領域から離れた場所に維持しなければならない。そうでない場合には、フレーム内に十分な帯域幅を含んでいても、ＷｉＭＡＸフレーム内の任意の他のバーストをマッピングできない場合がある。例えば、図６に示すように、バーストが制御領域内にマッピングされる場合には、フレーム内に多くの空のスロット（使用できる帯域幅）が存在していても、それ以上ＰＤＵをフレームにマッピングすることはできない。図７に、ＷｉＭＡＸフレームを充填するためのもっと感覚的に理解できる方法を示す。この場合、ＰＤＵ２は、ＰＤＵ３のＩＥおよびバーストのための余地を含んでいる位置のところのフレーム内に位置している。この配置を使用すれば、フレーム内にもっと多くのＰＤＵを置くことができる。ＩＥは若干異なるサイズを有することができることを思い出されたい。上記図の場合には、説明を簡単にするために、ＩＥは「平均的な」サイズを有している。
【００２６】
ＷｉＭＡＸフレーム・マッピングの目標は下記のように要約することができる。
１．使用できる空気帯域幅を最善の方法で使用すること。何故なら、この帯域幅は無線システムで最も貴重なリソースであるからである。
【００２７】
２．所与の時間内にフレーム・マッピング・プロセスを終了すること。
３．手順の性能プロファイルを入手するために、あるレベルの分析を達成すること。
それ故、ＷｉＭＡＸフレーム・マッピング・プロセスは、制限付きの最適化問題であると見なすことができる。制限されるのは、フレームが満杯になるまで、フレームの制御領域がどこで終わるのか（およびデータ領域がどこで開始するのか）を知ることができないからである。しかし、依然として、制御領域直後のアップリンク制御の位置を知る必要があるし、次に、残りのバーストを残りのスペース内に入れるようにしなければならない。
【００２８】
一見したところ、ＷｉＭＡＸフレーム・マッピング問題は、一次元または二次元「ビン・パッキング」問題であると見なすことができる。しかし、従来のビン・パッキング問題とＷｉＭＡＸフレーム・マッピングの間には有意の違いがある。ビン・パッキング問題の場合には、所与の品目を小片に分割することはできないが、ＷｉＭＡＸフレーム・マッピングの場合には、パケットを小片にセグメント分割することができる。これらの違いはあるが、ビン・パッキングの類推は、ＷｉＭＡＸフレーム・マッピングへの種々のアプローチを分析するために使用することができる。この類推を使用して、ビン（または分割）をＷｉＭＡＸフレームの１つ以上の連続している列であると定義することができる。この場合、マッピング・プロセスは、フレーム内にビンをパックする。パケットのセグメント分割の可能性の見地から見て、３つのＷｉＭＡＸフレーム・マッピング方法が識別されている。
（ａ）シーケンシャルな敷設
図８を参照すると、シーケンシャルな敷設プロセスは、制御領域を上から下にＩＥでマッピングし、類似の方法でデータ領域をＰＤＵバースト（ＰＤＵ）で充填する簡単な方法である。このプロセスは、アップリンク制御（ＰＤＵ１）の位置がすでに確立されているという仮定の下で行われる。ＰＤＵが、ビン内の使用できるスペースを超えた場合には、ＰＤＵがセグメント分割され、ＰＤＵの超過部分が新しいビンにマッピングされる。図８（ａ）の例の場合には、ＰＤＵ１が第１のビンにマッピングされると、ＰＤＵ２は大きすぎてビン内の残りのスペース内に入らない。それ故、図８（ｂ）を参照すると、ＰＤＵ２は、Ｐ２’およびＰ２”にセグメント分割され、２つの対応するＩＥ（すなわち、ＩＥ２’およびＩＥ２”）がセグメントのために提供される。ＰＤＵ２の第１のセグメント（すなわち、Ｐ２’）は、第１のビン内の残りのスペースにマッピングされ、ＰＤＵ２の第２のセグメント（すなわち、Ｐ２”）は、次のビン内にマッピングされる。２つの対応するＩＥ（すなわち、ＩＥ２’およびＩＥ２”）は、制御領域内のＩＥ１の後ろに位置する。図８（ｃ）を参照すると、次に、次のＰＤＵ（すなわち、ＰＤＵ３）が、第２のビンの残りのスペース内に入れられる（もし可能な場合）。
【００２９】
シーケンシャルな敷設アプローチは、制御領域およびデータ領域を容易に管理することができるという利点を有する。さらに、帯域幅効率の見地から見た場合、最悪の場合（例えば、各ＰＤＵが使用することができるビンより１バイト大きい場合）でも、ＰＤＵは、ビン内の１つの行を無駄にし、非常に短い（１バイトの）バーストに対して余分なＩＥを生成する場合がある。
【００３０】
しかし、シーケンシャルな敷設アプローチの１つの問題点は、セグメント分割動作が非常に多いことである。簡単なセグメント毎のチェックを行っても、確率論的なプロセスの全体像は分からない。何故なら、到着するパケットは異なる長さを有し、ビンのサイズもフレーム毎に異なるからである。それ故、確率論的プロセスを分析する１つの方法は、すべてのものを予測した数値に「平均」することである。より詳細には、各ビンが平均Ｂ個のスロットを含み、各パケットが平均Ｐ個のスロットを占有するとしよう。実際には、Ｐ≦Ｂである。それ故、データ領域内の第１のビンは、
【００３１】
【数１】
2010524321.tif 000003
個のセグメント分割されていないパケットを保持することができ、平均（Ｂ  ｍｏｄ  Ｐ）個のマッピングされていないスロットが残る。ＢをＰで割ることができる場合には、セグメント分割する必要はない。最悪の場合でも、ＰおよびＢは、互いに素である。この場合、
【００３２】
【数２】
2010524321.tif 000004
パケットそれぞれは、セグメント分割動作を必要とする。２つのランダムな整数の場合には、これらの整数が互いに素になる確率は、
【００３３】
【数３】
2010524321.tif 000005
であることが分かっている。いくつかのＢおよびＰの場合、ｇｃｄ（Ｂ，Ｐ）≠１であることを考慮に入れると、ＰおよびＢが互いに素になる確率は、６／π２未満である。そのため、最悪の場合でも、パケットがセグメント分割される確率は約Ｐ／Ｂであり、この最悪の場合のシナリオは、百に対して約６１発生するだけである。すなわち、パケットが小さく、ビンが大きい場合には、セグメント分割の割合は非常に低い。
（ｂ）最後のビン・チェックを含むシーケンシャルな敷設
最後のビン・チェックを含むシーケンシャルな敷設アプローチは、最初に、前のシーケンシャルな敷設アプローチを試行する。しかし、ＰＤＵがビン内の使用することができるスペースを超えた場合には、ＰＤＵをセグメント分割する代わりに、最後のビン・チェックを含むシーケンシャルな敷設アプローチは、新しいビン内にＰＤＵのその全体を入れようとする。図９を参照しながら、図８で使用したものと同じ例を使用して説明すると、ＰＤＵ２をセグメント分割する代わりに、最後のビン・チェックを含むシーケンシャルな敷設アプローチは、ＢＩＮ２をＰＤＵ２で直ちに充填する（図９（ｂ））。次に、最後のビン・チェックを含むシーケンシャルな敷設アプローチは、次のＰＤＵ（すなわち、ＰＤＵ３）をＰ３’およびＰ３”にセグメント分割する。最後のビン・チェックを含むシーケンシャルな敷設アプローチは、また、ＰＤＵ３のセグメントに対応する２つのＩＥ（すなわち、ＩＥ３’およびＩＥ３”）を生成し、フレームの制御領域内の２つのＩＥの位置を発見する。次に、最後のビン・チェックを含むシーケンシャルな敷設アプローチは、ＢＩＮ２およびＢＩＮ３の空のスペースをセグメントＰ３’およびＰ３”で充填する。空のスペースは２つのセグメントを収容できるだけの大きさを有しているので、ＰＤＵ３のための新しいビンは生成されない。
【００３４】
上記のシーケンシャルな敷設アプローチの際のように、同じ仮定を最後のビン・チェックを含むシーケンシャルな敷設アプローチに適用する。この場合、第１のビンの空のスペースは、約（１／２）×Ｐのスロットを含む。平均して、セグメント分割動作は、
【００３５】
【数４】
2010524321.tif 000006
パケットの後で行われ、この動作はＰＤＵを２つの存在するビンの空のスペース内にマッピングする。それ故、最後のビン・チェックを含むシーケンシャルな敷設が必要とするセグメント分割動作の平均回数は、シーケンシャルな敷設アプローチの平均回数より少ないように思われる。しかし、シーケンシャルな敷設に対する
【００３６】
【数５】
2010524321.tif 000007
個のパケット毎の１回のセグメント分割の数字は、６０％の確率で起こる最悪の場合のシナリオを表していることに留意されたい。
（ｃ）セグメント分割を行わないシーケンシャルな敷設
セグメント分割を行わないシーケンシャルな敷設は、
使用することができるビンを発見し、選択したＰＤＵをビン内に入れるステップと、
どのビンのスペースもＰＤＵを収容するのに十分なものでない場合に、最大の使用することができるスペースを含むビンを発見するステップと、
ビン内にＰＤＵの一部を充填するステップと、
を含む。
【００３７】
セグメント分割を行わないシーケンシャルな敷設アプローチは、セグメント分割は行わなくてすむが、いくつかの新しい問題が生じる。より詳細には、新しいビンを生成するのかしないのかを決定しなければならない。同様に、トランスポートするデータが少なすぎるという問題も起こる。さらに、もっと低いレベルで不必要なセグメント分割動作が必要になるという問題も起こる。最後に、最大または最も適しているビンを取り出すためにビンの順序を維持しなければならない。この問題のためにアルゴリズムが不必要に複雑なものになる。
（ｄ）制御されたセグメント分割を含むシーケンシャルな敷設
制御されたセグメント分割を含むシーケンシャルな敷設アプローチは、
フレーム内にＰＤＵをシーケンシャルに入れるステップと、
セグメント分割を行った場合に、分割したＰＤＵ（例えば、図８のＰＤＵ２”）の後部のサイズをチェックするステップと、
後部が大きすぎる場合に、新しいＩＥを生成するステップ、または
ＰＤＵの前部だけをフレームにマッピングするステップと、
を含む。
２．ＷｉＭＡＸフレームをパッキングするための方法の概要
下記の実施形態のすべてのアルゴリズムおよび手順は、少なくとも１つの無線ユーザ装置と通信している基地局内で実施される。より詳細には、この手順は、基地局内の処理回路モジュール内で実施可能である。この場合、この処理回路モジュールは、モジュールに到着するデータのデータ・レートとは無関係に、ＷｉＭＡＸフレームを効果的に処理する。
【００３８】
元のシーケンシャルな敷設アプローチは、第１の実施形態のパッキング方法にとって実行可能な開始点である。何故なら、その少なくとも一部が、他のアプローチにより再使用されるからである。より詳細には、実施の見地からいうと、このシーケンシャルな敷設アプローチは、制御されたセグメント分割を含むシーケンシャルな敷設が後に続く、他のもっと高度のアプローチに対するベースラインとして使用することができる。
【００３９】
第１の可能性は、フローティング・ヒル探索タイプのアプローチを使用することである。この場合、フレーム内で制御領域およびデータ領域を最初に予め定義し、進行的に制御領域およびデータ領域にＰＤＵを配置することにより、空のマトリクスが配置される。使用することができる制御領域が満たされると、（効果的に、フレーム内の制御領域とデータ領域間の分割ラインを前方に移動させ、それに従ってデータ領域内のＰＤＵバーストを移動させることにより）制御領域が増大する。しかし、このアプローチは、確実に制御領域が溢れないようにするために、制御領域およびデータ領域を常に監視しなければならない。
【００４０】
思い出していただけると思うが、アップリンク制御（すなわち、第１のＰＤＵバースト）を制御領域の直後に置かなければならないために、もう１つの問題が起こる。しかし、他のバーストをデータ領域にマッピングする方法を決定する前に、フレーム内のアップリンク制御の位置を決定するのは非常に困難である。この問題を解決する自明の方法は、アップリンク制御の位置を予め定義する方法である。しかし、そうすると、制御領域内に予備の帯域幅があるのにフレームのデータ領域が満杯になる場合がでてくるし、またその逆も起こり得る。制御領域またはデータ領域内の未使用の帯域幅を使用するために、バーストを移動する特別の方法が必要になる。しかし、フレーム・マッピングの厳密なモデルがないと、多くの他の問題（例えば、帯域幅の効率、アルゴリズムの複雑さ、完全さ、丈夫さおよびスケーラビリティ）が生じる。
【００４１】
図１０を参照すると、好ましい実施形態のフレーム・マッピング方法は、実ＷｉＭＡＸフレーム６２と同じ数の行と列を有する仮想または想像上のフレーム６０を供給することによりこの問題を解決している。仮想フレーム６０は、制御領域６４およびデータ領域６６に分割される。この場合、制御領域６４は仮想フレーム６０の右端に位置し、データ領域６６は、仮想フレーム６０の左端に位置する。それ故、すでに説明したように、ＩＥを実ＷｉＭＡＸフレーム６２の左頂部の隅からおよびフレーム６２の右に下方にマッピングするのではなく、（およびバーストを下方におよび実ＷｉＭＡＸフレーム６２の右方向にマッピングするのではなく）、第１のＩＥは、仮想フレーム６０の右頂部の隅７０方向にマッピングされ、使用することができる仮想フレーム６０本体内に左方向に進行的に延びる制御領域６４に延びる、下方に制御領域６４を配置する。同様に、ＰＤＵバーストは、データ領域６６を配置し、そのためＰＤＵバーストは、仮想フレーム６０内の最も遠い左側のセル７２内に位置していて、データ領域６６は、仮想フレーム６０のコア内を右方向に効果的に延びる。それ故、実際には、制御領域６４およびデータ領域データ６６は、仮想フレーム６０内に延びていて、そのため、制御領域６４およびデータ領域データ６６の間の分割は、最初から確実に確立されない。
【００４２】
ある時点において、制御領域６４およびデータ領域データ６６は、仮想フレーム６０内で相互に接するのに十分なだけ効果的に延びている。この場合には、仮想フレーム６０は満杯である。仮想フレーム６０が満杯になると、仮想マトリクス６０のデータ領域６６を、実ＷｉＭＡＸフレーム６２の右端に移動し、仮想フレーム６０の制御領域６４を実ＷｉＭＡＸフレーム６２の左端に移動し、制御領域６４内のＩＥの順序を裏返すことにより、実ＷｉＭＡＸフレーム６２が仮想フレーム６０から生成され、そのため、第１のＩＥは、実ＷｉＭＡＸフレーム６２内の一番遠い左の位置に位置する。それ故、例えば、座標が（０，０）であるバーストＰ１およびＬ個の列を含む制御領域６４の場合には、並進プロセス（ｔｒａｎｓｌａｔｉｏｎ  ｐｒｏｃｅｓｓ）によりＰ１バーストは座標（０＋Ｌ，０）に移動する。
【００４３】
仮想フレーム６０を使用すると、「中央で合流」アプローチは、空気帯域幅を使用することができる。仮想フレーム６０内である解決方法を発見した場合には、その解決方法を、実ＷｉＭＡＸフレーム６２に直ちに適用することができる。この仮想フレーム６０内においては、もはやＷｉＭＡＸフレーム６２の制御領域６４およびデータ領域６６の状態を常に監視する必要はない。代わりに、仮想フレーム６０内で制御領域６４およびデータ領域６６がいつ接するのかを判別するだけでよい。
【００４４】
この機構は、ＷｉＭＡＸフレームを効率的に使用しているので、実際には、平均して、ほとんどの場合、空のままでいるフレームのスロットの百分率は１％未満である。これらの空のスロットは、他の最適化手順によって使用することができる。この方法は、帯域幅の効率およびアルゴリズムの複雑さ分析するために使用することができる。さらに、この方法はスケーラブルなものである。
３．ＷｉＭＡＸフレームをパックするための方法で使用するデータ構造
上記アルゴリズムがＷｉＭＡＸ  ＭＡＣ層内ですでに実施されているので、ＷｉＭＡ物理層が物理情報を供給するまでは、そこからのＷｉＭＡＸフレームを適切に配置することができない。それ故、仮想フレーム６０を生成しても、基地局またはその任意の受信側携帯電話のメモリ・デマンドは増大しない。何故なら、実ＷｉＭＡＸフレーム６２もその仮想の相手側もまだ物理エンティティではないからである。さらに、実ＷｉＭＡＸ６２および仮想フレーム６０を表すためには、特定のマトリクスが必要なのではなく、使用できる座標のベクトルが必要だからである。さらに、仮想フレーム６０内の制御領域６４およびデータ領域６６の状態を監視するのにデバッグ・スタックが役に立つ。これらのことを考慮して、データ構造を図１１に示すように設計した。データ構造は、下記の構成要素を含む。
【００４５】
（ａ）ｇＢＷａ  −  仮想フレーム６０で使用することができるスロットの数を示すグローバル変数。この場合、この変数はＷｉＭＡＸ物理層により初期化される。
（ｂ）ｇＤＬＢｚｏｎｅＷｉｄｔｈ  −  仮想フレーム６０のダウンリンク・データ領域のスロット内の幅。
【００４６】
（ｃ）ｇＢｉｎＳｔａｒｔ  −  仮想フレーム６０内の有用なスロットを含む最初のビン。
（ｄ）仮想フレーム６０内の最も右に位置する／生成されたビン。このビンを超えた先においては、仮想フレーム６０は、新しいビンを生成することができる空白領域を含む。
【００４７】
（ｅ）ｇＢｉｎＷｉｄｔｈ  −  スロット内の仮想フレーム６０内の所与のビンの幅を示す。
（ｆ）ｇＢｉｎＴｏｐ  −  仮想フレーム６０内のビンのＹ座標を示す（ｂｉｎ＝ｉ）。
【００４８】
（ｇ）ｇＢｉｎＸ  −  仮想フレーム６０内のビンのＸ座標を示す（ｂｉｎ＝ｉ）。
（ｈ）ｇＰｄｕＳｔａｃｋ  −  仮想フレーム６０内のすべてのＰＤＵバーストを記録するスタック。その「ＰＤＵバースト位置」フィールドは、ＰＤＵの位置を示す４つ組＜ｘ，ｙ，ｗ，ｄ＞を格納する。この場合、ｘおよびｙは、バーストの左頂部隅を示し、一方ｗおよびｄは、バーストの幅および深さを示す。その「他の情報」フィールドは、ＱＩＤおよびＰＤＵバーストのデータへのポインタを含む。
【００４９】
（ｉ）ｇＰｄｕＳｔａｃｋＴｏｐ  −  スタックの頂部を示す。
ｇＰｄｕＳｔａｃｋおよびｇＰｄｕＳｔａｃｋＴｏｐ変数の両方は、独立コード・デバッグのためのオプションである。
４．ＷｉＭＡＸフレームをパックするための方法を実施するために使用するアルゴリズム
すでに説明したように、フレーム・マッパは、サービス・データ・ユニット（ＳＤＵ）（例えば、ＩＰパケット）を選び、それをプロトコル・データ・ユニット（ＰＤＵ）内にカプセル化する。ＰＤＵは、ＷｉＭＡＸフレームのデータ領域を配置するために使用される。個々のＰＤＵバーストが大きすぎてＷｉＭＡＸフレームの使用できる列内に入れることができない場合には、１つの問題が起こる。この問題を解決する１つの方法は、ＳＤＵを分割することである。それ故、ビン・パッキング問題からの２つのアルゴリズムがすでに開発されている。両方のアルゴリズムは、仮想フレーム６０上で実施される。（ＦＥＤアルゴリズムまたはｆｒａｍｅＭａｐｐｉｎｇＳｅｇ（））と呼ばれる）第１のアルゴリズムにおいては、所与のＳＤＵが、１つ以上のＰＤＵバースト内にマッピングされる。この場合、それを列の使用できるスペース内に入れることができない場合には、ＳＤＵのセグメント分割は自動的に行われる。（ＦＦＲまたはｆｒａｍｅＭａｐｐｉｎｇＳＤＵ（）と呼ばれる）第２のアルゴリズムにおいては、ＳＤＵは、セグメント分割しないで、ＰＤＵバースト内にマッピングされる。このアルゴリズムは、主として、ＭＮＧフロー（管理フロー）およびアップリンク制御をマッピングするために使用される。２つのアルゴリズムは、可変サイズのビンをパックし、生成することができ、その前には（図１１に示す）データ構造のための初期化手順を行うことができる。
（ａ）データ構造の初期化
データ構造のキー・パラメータは、下記のように初期化される。
【００５０】
・ｇＢＷａが、仮想フレーム６０のスロットの数内の使用できる全帯域幅として初期化される。（通常、これは仮想フレーム６０内の行の数に、仮想フレーム６０内の列の数からいくつかの予約しているスロットを引いたものを掛けたものである。）
・ｇＢｉｎＳｔａｒｔは、０として初期化される。
【００５１】
・ｇＢｉｎＲｍｏｓｔは、−１として初期化される。
／ｇＤｍａｐＢｙｔｅｓは、ＩＥＥＥ規格８０２．１６ｅ（商標）（２００５）の図２１８に定義されているように、ＦＣＨ＿ＳＬＯＴＳ＊ＢＹＴＥＳ＿ＰＥＲ＿ＳＬＯＴ＿ＤＬＭＡＰとして初期化される。
【００５２】
・ｇＤＬＢｚｏｎｅＷｉｄｔｈは、０として初期化される。
・ｇＤＬＢｓｔａｃｋＴｏｐは、スタックが始めのところで空である−１として初期化される。
（ｂ）ＦＦＲアルゴリズム（ｆｒａｍｅＭａｐｐｉｎｇＳＤＵ（））
図１２を参照すると、ＦＦＲアルゴリズムは、最初に（８０）、ＩＥを制御領域内にマッピングし、ｇＢｉｎＳｔａｒｔを調整し、次に、所与のＳＤＵを（仮想フレーム６０内に）十分収容できる大きさの既存のビンが存在するか否かを判別するために、ｇＢｉｎＳｔａｒｔとｇＢＩｎＲｍｏｓｔとの間のビンをチェックす（８２）。十分なスペースを含むビンを発見した場合には、所与のＳＤＵに対する１つのＰＤＵバーストの輪郭が描かれる。しかし、適当なビンを発見することができなかったか場合には、ＦＦＲアルゴリズムは、仮想フレーム６０の空白領域内に、新しい十分な大きさを有するビンを生成しようとする（８４）。十分な帯域幅を使用できる場合には、ビンが成功裏に生成され、そこへＳＤＵがマッピングされる。そうでない場合には、所与のＳＤＵに対して１つのバーストを生成するために十分なスペースが存在しない。それ故、ＦＦＲアルゴリズムは、０（ＳＤＵのマッピングに失敗した場合）、またはバイト単位のＳＤＵの長さに戻る（仮想フレーム６０へのＳＤＵのマッピングで成功した場合）。
ＦＦＲアルゴリズムの数字による例
仮想フレームを１２×１５のマトリクスとして表すこととしよう。さらに、スロットが３バイトを含み、平均したＩＥバーストが、６バイトを含んでいるものとしよう。同様に、サービス・フローが、５つのパケット（ＰＤＵ１−ＰＤＵ５）を含んでいるものとしよう。この場合、ＰＤＵ１、ＰＤＵ２、ＰＤＵ３、ＰＤＵ４およびＰＤＵ５は、それぞれ、サイズが６、３３、１２、６および１４のスロットである。ＦＦＲアルゴリズムは、マトリクス内に十分なスペースがある限りは、２つのスロット幅のビンを生成する。最初は、ｇＳｔａｒｔ＝０、ｇＲｍｏｓｔ＝−１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝０、およびｇＤｍａｐＢｙｔｅｓ＝０である。ｇＢｉｎＷｉｄｔｈ［］、ｇＢｉｎＴｏｐ［］およびｇＢｉｎＸ［］は指定されない。
【００５３】
ＰＤＵ１を選択した場合には、ＩＥ１バーストは、仮想フレーム６０の制御領域にマッピングされる（８０）。次に、ＦＦＲアルゴリズムは、（仮想フレーム６０内に）ＰＤＵ１を収容することができるだけの十分な大きさを有する既存のビンが存在するか否かを判別するために、ｇＢｉｎＳｔａｒｔとｇＢｉｎＲｍｏｓｔとの間のビンをチェックする（８２）。この場合、ＦＦＲアルゴリズムは、ＰＤＵ１を収容することができるだけの十分な大きさのビンを発見しない。（何故なら、ｇＢｉｎＲｍｏｓｔ＝−１は、ｇＢｉｎＳｔａｒｔ＝０より小さいからである。）それ故、ＦＦＲアルゴリズムは、フレームのデータ・スペース内にビン＃０を生成し、ＰＤＵ１をその中にマッピングする。この時点で、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝０、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝２、ｇＤｍａｐＢｙｔｅｓ＝６、ｇＢｗａ＝１６２、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝２、ｇＢｉｎＸ［０］＝０である。
【００５４】
ＰＤＵ２を選択した場合には、ＩＥ２バーストは、仮想フレーム６０の制御領域にマッピングされる（８０）。次に、ＦＦＲアルゴリズムは、（仮想フレーム６０内に）ＰＤＵ２を収容することができるだけの十分な大きさを有する既存のビンが存在するか否かを判別するために、ｇＢｉｎＳｔａｒｔとｇＢｉｎＲｍｏｓｔとの間のビンをチェックする（８２）。ビン＃０は存在するが、その容量はＰＤＵ２を収容するのに十分なものではない。それ故、仮想フレーム６０のデータ領域内に（幅＝３スロットの）ビン＃１が生成され（８４）、ＰＤＵ２がその中にマッピングされる。この時点で、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝５、ｇＤｍａｐＢｙｔｅｓ＝１２、ｇＢｗａ＝１２９、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝２、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝３、ｇＢｉｎＴｏｐ［１］＝１０、ｇＢｉｎＸ［１］＝２である。
【００５５】
ＰＤＵ３をマッピングした後では、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝５、ｇＤｍａｐＢｙｔｅｓ＝１８、ｇＢｗａ＝１１７、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝８、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝３、ｇＢｉｎＴｏｐ［１］＝１０、ｇＢｉｎＸ［１］＝２になる。ＰＤＵ４をマッピングした後では、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝５、ｇＤｍａｐＢｙｔｅｓ＝２４、ｇＢｗａ＝１１１、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝３、ｇＢｉｎＴｏｐ［１］＝１０、ｇＢｉｎＸ［１］＝２になる。
【００５６】
同様に、ＰＤＵ５に対するビン＃２を生成した後では、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝７、ｇＤｍａｐＢｙｔｅｓ＝２４、ｇＢｗａ＝９７、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝３、ｇＢｉｎＴｏｐ［１］＝１０、ｇＢｉｎＸ［１］＝２、ｇＢｉｎＷｉｄｔｈ［２］＝２、ｇＢｉｎＴｏｐ［２］＝６、ｇＢｉｎＸ［１］＝５になる。特に、図１３は今までの結果を示す。
（ｃ）ＦＥＤアルゴリズム（ｆｒａｍｅＭａｐｐｉｎｇＳｅｇ（））
ＦＥＤアルゴリズムは、使用することができる帯域幅がある限りは、所与のＳＤＵ全体またはその一部が確実にマッピングされるようなシーケンシャルな敷設方法を実施する。より詳細には、図１４を参照すると、ＦＥＤアルゴリズムは、最初に、ＩＥを仮想フレーム６０の制御領域内にマッピングし、次に（仮想フレーム６０内の）所与のＳＤＵを収容できるだけの十分な大きさの既存のビンビンが存在するか否かを判別するために、ｇＢｉｎＳｔａｒｔとｇＢｉｎＲｍｏｓｔとの間のビンをチェックする（８６）。有用なスペースを含むビンを発見した場合には、このアルゴリズムは、ＳＤＵ全体またはその一部をその中にマッピングする（８８）。有用なスペースを含むビンを発見できなかった場合には、ＦＥＤアルゴリズムは、仮想フレーム６０の空白領域内に（使用することができる帯域幅ｇＢＷａの制限を含む）十分な大きさのビンを生成し（９０）、ＳＤＵがマッピングされるまで、または帯域幅が無くなるまで、その内部にＳＤＵを引き続きマッピングする（８８）。アルゴリズムは、ＳＤＵ内にマッピングされているバイトの数を返送する（９２）。それ故、スケジューラは、ＱｏＳ情報を更新するためにこのバイト数を使用することができる。セグメント分割を行うと追加のＩＥバーストが生成されることを理解することができるだろう。
ｆｒａｍｅＭａｐｐｉｎｇＳｅｇ（）アルゴリズムの数字による例
上記のように、仮想フレームを１２×１５マトリクスで表すとしよう。さらに、スロットが３バイトを含み、平均したＩＥバーストが６バイトを含んでいるとしよう。同様に、サービス・フローが、５つのパケット（ＰＤＵ１−ＰＤＵ５）を含んでいるとしよう。この場合、ＰＤＵ１、ＰＤＵ２、ＰＤＵ３、ＰＤＵ４およびＰＤＵ５は、それぞれ、サイズが６、３３、１２、６および１４のスロットである。ＦＥＤアルゴリズムは、仮想フレーム６０内に十分なスペースがある限りは、２つのスロット幅のビンを生成する。最初は、ｇＳｔａｒｔ＝０、ｇＲｍｏｓｔ＝−１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝０、およびｇＤｍａｐＢｙｔｅｓ＝０である。ｇＢｉｎＷｉｄｔｈ［］、ｇＢｉｎｔｏｐ［］およびｇＢｉｎＸ［］は指定されない。
【００５７】
ＰＤＵ１を選択した場合には、ＩＥ１バーストは仮想フレーム６０の制御領域にマッピングされる。ＰＤＵ１を収容することができるだけの十分な大きさを有する既存のビンが存在するか否かを判別するために、ｇＢｉｎＳｔａｒｔとｇＢｉｎＲｍｏｓｔとの間のビンをチェックした場合には、既存のビンは発見されない。何故なら、ｇＢｉｎＲｍｏｓｔ＝−１は、ｇＢｉｎＳｔａｒｔ＝０より小さいからである。それ故、ビン＃０が生成され（７０）、ＰＤＵ１がその中にマッピングされる（６８）。この時点で、ｇＢｉｎＳｔａｒｔ＝０、ｇＢｉｎＲｍｏｓｔ＝０、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝２、ｇＤｍａｐＢｙｔｅｓ＝６、ｇＢｗａ＝１６２、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝２、ｇＢｉｎＸ［０］＝０である。
【００５８】
ＰＤＵ２を選択した場合には、現在のビン、ビン＃０が発見されるが、パケット（１８スロット）の一部だけしかそこにマッピングされない。この場合、バーストＩＥ２’が生成され、ＰＤＵの一部（ＰＤＵ２’）がそれにより充填されるビン＃０にマッピングされる。この時点で、ｇＢｉｎＳｔａｒｔ＝１、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝２、ｇＤｍａｐＢｙｔｅｓ＝１２、ｇＢｗａ＝１４４、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０である。ＰＤＵ２の一部しか仮想フレーム６０にマッピングされないので、ｒｅｍＢｙｔｅｓ（＝１５スロット×３バイト／スロット）＝７５バイト＞０となり、ループが継続する。ｇＢｉｎＲｍｏｓｔ＝０である場合には、ｇＢｉｎＳｔａｒｔ＝１であるので、このことは（仮想フレーム６０内で）現在のビンが使用できないことを意味する。それ故、ＰＤＵ２（すなわち、ＰＤＵ”）の残りの部分を収容することができる十分な大きさの新しいビン（すなわち、ビン＃１）が生成される。ＰＤＵ２”は、新しいビンにマッピングされ、追加のＩＥバースト、ＩＥ２”が制御領域にマッピングされる。この時点で、ｇＢｉｎＳｔａｒｔ＝１、ｇＢｉｎＲｍｏｓｔ＝１、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝４、ｇＤｍａｐＢｙｔｅｓ＝１８、ｇＢｗａ＝１２８、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝２、ｇＢｉｎＴｏｐ［１］＝７、ｇＢｉｎＸ［１］＝２である。
【００５９】
ＰＤＵ３をＰＤＵ３’およびＰＤＵ３”としてマッピングした後では、ｇＢｉｎＳｔａｒｔ＝２、ｇＢｉｎＲｍｏｓｔ＝２、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝６、ｇＤｍａｐＢｙｔｅｓ＝３０、ｇＢｗａ＝１０４、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝２、ｇＢｉｎＴｏｐ［１］＝１１、ｇＢｉｎＸ［１］＝２、ｇＢｉｎＷｉｄｔｈ［２］＝２、ｇＢｉｎＴｏｐ［２］＝１、ｇＢｉｎＸ［２］＝４になる。同様に、ＰＤＵ４をマッピングした後では、ｇＢｉｎＳｔａｒｔ＝２、ｇＢｉｎＲｍｏｓｔ＝２、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝６、ｇＤｍａｐＢｙｔｅｓ＝３６、ｇＢｗａ＝９８、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝２、ｇＢｉｎＴｏｐ［１］＝１１、ｇＢｉｎＸ［１］＝２、ｇＢｉｎＷｉｄｔｈ［２］＝２、ｇＢｉｎＴｏｐ［２］＝４、ｇＢｉｎＸ［２］＝４になる。
【００６０】
ＰＤＵ５をマッピングする場合には、データ領域内に新しい列が必要になる。この時点で、ｇＢｉｎＳｔａｒｔ＝３、ｇＢｉｎＲｍｏｓｔ＝２、ｇＤＬＢｚｏｎｅＷｉｄｔｈ＝６、ｇＤｍａｐＢｙｔｅｓ＝４２、ｇＢｗａ＝７２、ｇＢｉｎＷｉｄｔｈ［０］＝２、ｇＢｉｎＴｏｐ［０］＝１１、ｇＢｉｎＸ［０］＝０、ｇＢｉｎＷｉｄｔｈ［１］＝２、ｇＢｉｎＴｏｐ［１］＝１１、ｇＢｉｎＸ［１］＝２、ｇＢｉｎＷｉｄｔｈ［２］＝２、ｇＢｉｎＴｏｐ［２］＝１１、ｇＢｉｎＸ［２］＝４になる（図１５の場合と同様である。）
４．帯域幅の効率を最適化するための方法
最後のビン（すなわち、制御領域の隣のビン）に１つのスロットの幅を強制的に持たせることにより、ビンの平均的な空の大きさは列の半分になる。（すなわち、平均して、ビンの半分が空になる）。しかし、図１６に示すように、この状態の場合には２つのシナリオを使用することができることに留意されたい。（図１６ａに示す）一方のシナリオの場合には、仮想フレーム６０のデータ領域６６が満杯である。（図１６ｂに示す）他方のシナリオの場合には、仮想フレーム６０の制御領域６４が満杯である。すべてのビン全体をマッピングする可能性はあるし、空き領域が残っていない場合もあるが、図１７に示す最後のビン内にパケットをパックすることができない可能性もある。この場合、ＩＥバーストをマッピングすると、ＰＤＵバーストのためのスペースがない。実ＷｉＭＡＸ用途の場合には、空き領域の百分率は非常に小さい（最悪の場合には、平均３％未満、平均的なほとんどの場合には、１％未満）である（２００６年７月のＷｉＭＡＸフォーラム、「ＷｉＭＡＸフォーラム（商標）モバイル・システム・プロファイル」の表１０参照）。しかし、依然として、仮想フレーム６０内にもっと多くのパケットをさらにマッピングすることができる。
【００６１】
図１６ａおよび図１７の場合には、１つの潜在的なアプローチは、最初に、仮想フレーム６０を実ＷｉＭＡＸフレーム（図１０参照）に変換し、次に、図１８に示すように、データ領域内であるスペースを開放するためにビン＃０を操作する方法である。そうすることにより、もっと多くのＰＤＵを入手することができる。
【００６２】
図１６（ｂ）の場合の最適化は、図１８の場合のように簡単にはいかない。何故なら、空のスロットを含む列が、図１９に示すように遥か右側１００に位置しているからである。新しいＩＥバーストのための空きスペースに周囲のバーストを移動させるための明らかな試行錯誤的方法はないように思われる。実行可能な方法は、図２０に示すように、空き領域に隣接するバースト１０２を延長する方法である。つまり、フレーム内の空の小さな百分率をさらに低減するためにフレーム−マッピング・アルゴリズムを適用した後でさらなる最適化を行うことができる。
５．「グループ分け」問題へのアルゴリズムの適用
ある実施態様の場合には、制御領域内の帯域幅を節約するために、同じＭＳまたは同じＤＵＩＣを有するバーストを併合することが望ましい。この要件は、小さなパケット（すなわち、ＷｉＭＡＸ内のｒｔＰＳまたはＥｒｔＰＳ）を含むトラフィックの場合に特にうまくいく。何故なら、グループ分けしたパケットは、同じＩＥバーストを共有していて、そのため帯域幅全体を節約することができるからである。同じ機能を有するパケットを一緒にグループ分けするのに、スケジューラによりフローが向けられる所望のビン番号に索引を付けるために逆の表（ＭＳｉｄ／ＤＵＩＣｉｄ−＞ビン＃）が必要である。マッピングの後でビンが満杯の場合には、このエントリ内のビン番号は削除される。新しいビンが生成された場合には、そのビン番号が、ＭＳｉｄ／ＤＵＩＣｉｄにより索引が付けられたエントリ内に挿入される。
【００６３】
より詳細には、同じ機能を含むパケットを一緒にグループ分けするための手順は、下記のステップを含む。
（１）ＭＳ／ＤＩＵＣ−＞ビン番号マッピングのための逆の表を作成するステップ
（ａ）ＭＳのための索引づけ
（ｂ）ＤＩＵＣのための索引づけ
（２）ＭＳまたはＤＩＵＣからビン番号を発見するための逆の表を参照するステップ
（３）（第１の）同じＭＳ／ＤＩＵＣビンからｆｒａｍｅＭａｐｐｉｎｇＳｅｇ（）／ｆｒａｍｅＭａｐｐｉｎｇＦＦ（）を行うステップ
（４）新しいビンが生成された場合に、逆の表にそのビン番号を追加するステップ
（５）マッピング後でビンが満杯の場合に、逆の表内のＭＳ／ＤＵＩＣエントリからそのビン番号を削除するステップ
（６）ビンを生成することができない場合に、使用できる帯域幅が存在する限り、ｇＢｉｎＳｔａｒｔからｆｒａｍｅＭａｐｐｉｎｇＳｅｇ（）／ｆｒａｍｅＭａｐｐｉｎｇＦＦ（）を行い、ビンが満杯でない場合には、逆の表内に最後のビン番号を追加するステップ。
【００６４】
割合簡単に、上記手順を現在のフレーム・マッピング手順に組み込むことができる。
本発明の範囲から逸脱することなしに、本発明を種々に変更および修正することができる。
【図１】
2010524321.tif 000008
【図２】
2010524321.tif 000009
【図３】
2010524321.tif 000010
【図４】
2010524321.tif 000011
【図５】
2010524321.tif 000012
【図６】
2010524321.tif 000013
【図７】
2010524321.tif 000014
【図８】
2010524321.tif 000015
【図９ａ】
2010524321.tif 000016
【図９ｂ】
2010524321.tif 000017
【図９ｃ】
2010524321.tif 000018
【図１０】
2010524321.tif 000019
【図１１】
2010524321.tif 000020
【図１２】
2010524321.tif 000021
【図１３】
2010524321.tif 000022
【図１４】
2010524321.tif 000023
【図１５】
2010524321.tif 000024
【図１６】
2010524321.tif 000025
【図１７】
2010524321.tif 000026
【図１８ａ−１８ｂ】
2010524321.tif 000027
【図１９】
2010524321.tif 000028
【図２０】
2010524321.tif 000029
【手続補正書】
【提出日】平成22年4月6日(2010.4.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＯＦＤＭシンボルを含むサブチャネルおよびタイムスロットにグループ分けされたサブキャリアからなるＯＦＤＭＡ／ＴＤＭＡフレームをパックするための方法であって、前記ＯＦＤＭＡ／ＴＤＭＡフレームが、前記サブチャネルに対応する行および前記ＯＦＤＭシンボルに対応する列を含むマトリクスとしてモデル化され、前記方法が、
同じ数の行および列を有するマトリクスを前記ＯＦＤＭＡ／ＴＤＭＡフレームとして生成する工程と、
第１の制御メッセージを前記マトリクスの第１のコーナー内のある位置にマッピングする工程と、
第１のデータ・メッセージを、前記マトリクスの第２のコーナー内のある位置にマッピングする工程であって、前記第２のコーナーが前記第１のコーナーへの所定の方向において対向している工程と、
更なるデータ・メッセージのうちの１つ以上が、更なる制御メッセージのうちの１つ以上と対応するまで、前記第１のコーナーから前記マトリクスの中心に向かって第１の方向へ移動し、前記マトリクスに複数の更なる制御メッセージをマッピングし、前記マトリクスの中心に向かって、前記マトリクスの前記第２のコーナーから前記第１の方向とは異なる第２の方向へ、前記マトリクスに複数の他のデータ・メッセージをマッピングする工程と、
前記制御メッセージを、前記マトリクスから前記ＯＦＤＭＡ／ＴＤＭＡフレームの第１の領域にコピーする工程と、
前記第１の制御メッセージが、前記フレームの開始のところに位置するように、前記ＯＦＤＭＡ／ＴＤＭＡフレーム内に前記制御メッセージを配置する工程と、
前記第１のデータ・メッセージが、前記制御メッセージの直後に位置するように、前記データ・メッセージを前記マトリクスから前記ＯＦＤＭＡ／ＴＤＭＡフレームの第２の領域にコピーする工程と、
からなる方法。
【請求項２】
前記方法が、
所与のデータ・メッセージを収容できる十分な大きさの区画が存在するか否かを判別するために、前記マトリクス内の区画をチェックする工程と、
前記区画が前記データ・メッセージを収容できる大きさのものである場合に、前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージをある区画にマッピングする工程と、
前記データ・メッセージを収容できる大きさの区画を発見できなかった場合に、前記マトリクス内の空き領域内に、前記データ・メッセージを十分収容できる大きさの新しい区画を生成する工程と、
前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージを前記新しい区画にマッピングする工程と、
前記マッピング・プロセスの結果に関するメッセージを返送する工程と、
から更になる請求項１に記載の方法。
【請求項３】
前記方法が、
所与のデータ・メッセージを十分収容することができる大きさの区画が存在するか否かを判別するために、前記マトリクス内の区画をチェックする工程と、
前記区画が前記データ・メッセージを十分収容することができる大きさのものである場合に、前記データ・メッセージのための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージをある区画にマッピングする工程と、
前記データ・メッセージ全体を収容することができる十分な大きさの区画を発見できなかった場合に、データ・メッセージのどの部分を最大の区画内に収容することができるかを判別する工程と、
前記一部のための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージの前記一部を前記最大の区画にマッピングする工程と、
前記マトリクスの空き領域内に、前記データ・メッセージの残りの部分を収容するのに十分な大きさの新しい区画を生成する工程と、
前記データ・メッセージの前記残りの部分のための制御メッセージを生成し、前記制御メッセージを前記マトリクスにマッピングし、前記データ・メッセージの前記残りの部分を前記新しい区画にマッピングする工程と、
前記マッピング・プロセスの結果に関するメッセージを返送する工程と、
から更になる請求項１に記載の方法。
【請求項４】
前記方法の後に、前記ＯＦＤＭＡ／ＴＤＭＡフレーム内で前記区画のさらなる最適化が行われる前記請求項１に記載の方法。
【請求項５】
前記最適化が、データ・メッセージの少なくともいくつかを、前記ＯＦＤＭＡ／ＴＤＭＡフレームの前記第１の領域の少なくとも一部内に移動し、前記ＯＦＤＭＡ／ＴＤＭＡフレームの前記第２の領域内の空きスペースに移動するステップを含む、請求項４に記載の方法。
【請求項６】
ＯＦＤＭシンボルを含むサブキャリアおよびタイムスロットにグループ分けされているサブキャリアからなるＯＦＤＭＡ／ＴＤＭＡフレームをパックするための方法を実行すべく作成された無線通信装置であって、        
前記ＯＦＤＭＡ／ＴＤＭＡフレームが、前記サブチャネルに対応する行および前記ＯＦＤＭシンボルに対応する列を含むマトリクスとしてモデル化され、前記方法が、
前記ＯＦＤＭＡ／ＴＤＭＡフレームと同じ数の行と列とを有するマトリクスを生成する工程と、
前記マトリクスの第１のコーナーの位置に第１の制御メッセージをマッピングする工程と、
前記マトリクスの、前記第１のコーナーに対して所定の方向に対向している第２のコーナーの位置に、第１のデータ・メッセージをマッピングする工程と、
前記マトリクスの中心に向かって、前記第１のコーナーから移動する第１の方向に前記マトリクスに複数の更なる制御メッセージをマッピングし、前記マトリクスの中心に向かって、前記マトリクスの第２のコーナーから、前記第１の方向とは異なる前記第２の方向に、１つ以上の更なるデータ・メッセージが１つ以上の更なる制御メッセージに対応するまで、更なる複数のデータ・メッセージを前記マトリクスにマッピングする工程と、
前記マトリクスから前記ＯＦＤＭＡ／ＴＤＭＡフレームの第１の領域へ、制御メッセージをコピーする工程と、
前記第１の制御メッセージが前記フレームの開始のところに位置するように、前記ＯＦＤＭＡ／ＴＤＭＡフレームの制御メッセージを配置する工程と、
前記第１のデータ・メッセージが前記制御メッセージの直後に位置するように、前記マトリクスから前記ＯＦＤＭＡ／ＴＤＭＡフレームの第２の領域へ前記データ・メッセージをコピーする工程と、
からなる装置。
【国際調査報告】
2010524321.tif 000030
2010524321.tif 000031
2010524321.tif 000032