(57)【要約】複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックの多重化されたスケジューリングを行うための方法。それぞれの情報源からの情報ブロックは、繰り返し周期を有し、複数のセグメントに分割される。この方法は、チャネル上のスケジューリングされる位置の総数を決定すること（１０１）、バイナリツリー上のノードに対応する不連続な順序で位置をマッピングし（１０３）、それによりこのバイナリツリーの各レイヤは繰り返し周期に対応すること、最小繰り返し周期から始めてブロックを繰り返し周期の順序で並べること、各ブロックの情報セグメントを未割当ての位置に割り当てること（１０６）、および繰り返し周期に対応するレイヤ上の割当て済み位置ノードのすべての子ノードを、割当て済みとしてマークすること（１０７）を含む。
2004530392.tif 000002
【特許請求の範囲】
【請求項１】
複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックの多重化されたスケジューリングを行うための方法であって、それぞれの情報源からの前記情報ブロックは、繰り返し周期およびセグメント数を有し、
前記チャネル上のスケジューリングされる位置の総数を決定するステップと、
バイナリツリーに対応する不連続な順序で、チャネル位置をマッピングするステップと、
前記ブロックの前記繰り返し周期に関連する、前記バイナリツリーのレイヤ上のバイナリツリーノードに対応する未割当てのチャネル位置に、各ブロックの情報セグメントを割り当て、また前記関連する割当て済みのレイヤノードの対応するすべての子ノードを、割当て済みとしてマークするステップとを備えることを特徴とする方法。
【請求項２】
前記決定するステップは、前記情報の繰り返し周期の関数であることを特徴とする請求項１に記載の方法。
【請求項３】
前記バイナリツリーのレイヤ数は、前記情報ブロックの最大繰り返し周期の関数であることを特徴とする請求項１に記載の方法。
【請求項４】
位置の割当ては、前記繰り返し周期に基づいて前記チャネル上の位置を割り当てるための情報ブロックの優先順位を決定すること、および
前記優先順位に従って、各情報源の情報セグメントをチャネル位置に割り当て、それぞれの情報源が完全に割り当てられてから、その次の情報ブロックの情報セグメントが割り当てられることを有することを特徴とする請求項１に記載の方法。
【請求項５】
前記情報ブロックは、前記優先順位の１番目であるヘッダ情報ブロックを含み、前記ヘッダ情報ブロックのセグメントは、数値的に連続した最初のチャネル位置に割り当てられることを特徴とする請求項４に記載の方法。
【請求項６】
その後の情報ブロックのセグメントは、最小数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項５に記載の方法。
【請求項７】
その後の情報ブロックのセグメントは、最大数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項５に記載の方法。
【請求項８】
複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックをスケジューリングするための方法であって、それぞれの情報源からの前記情報ブロックは、繰り返し周期およびセグメント数を有し、
前記チャネル上のスケジューリングされる位置の総数を決定するステップと
最小繰り返し周期を有するブロックから始めて、前記ブロックを繰り返し周期の順序で割り当てるステップであって、各ブロックの前記セグメントは、バイナリツリー上のノードにマッピングされた未割当ての位置に割り当てられるステップとを備えることを特徴とする方法。
【請求項９】
前記情報ブロックは、前記優先順位の１番目であるヘッダ情報ブロックを含み、前記ヘッダ情報ブロックのセグメントは、数値的に連続する最初のチャネル位置に割り当てられることを特徴とする請求項８に記載の方法。
【請求項１０】
その後の情報ブロックのセグメントは、最小数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項９に記載の方法。
【請求項１１】
その後の情報ブロックのセグメントは、最大数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項９に記載の方法。
【請求項１２】
複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックをスケジューリングするための方法であって、それぞれの情報源からの前記情報ブロックは、繰り返し周期およびセグメント数を有し、
前記チャネル上のスケジューリングされる位置の総数を決定するステップと、
バイナリツリー上のノードに対応する不連続な順序で位置をマッピングするステップであって、前記バイナリツリーの各レイヤは繰り返し周期に対応するステップと、
前記ブロックを、最小繰り返し周期から始めて、繰り返し周期の順序で並べるステップと、
前記順序付けに基づいて、各ブロックの情報セグメントを未割当ての位置に割り当てるステップと、
前記繰り返し周期に対応する前記レイヤ上の前記ノードのすべての子ノードを識別し、割当て済みとしてマークするステップとを備えることを特徴とする方法。
【請求項１３】
前記情報ブロックは、前記優先順位の１番目であるヘッダ情報ブロックを含み、前記ヘッダ情報ブロックのセグメントは、数値的に連続した最初のチャネル位置に割り当てられることを特徴とする請求項１２に記載の方法。
【請求項１４】
その後の情報ブロックのセグメントは、最小数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項１３に記載の方法。
【請求項１５】
その後の情報ブロックのセグメントは、最大数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項１３に記載の方法。
【請求項１６】
複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックをスケジューリングするための方法であって、それぞれの情報源からの前記情報ブロックは、繰り返し周期およびセグメント数を有し、
前記チャネル上のスケジューリングされる位置の総数を決定するステップと、
バイナリツリー上のノードに対応する不連続な順序で位置をマッピングするステップであって、前記バイナリツリーは複数のレイヤを有し、それぞれのレイヤは繰り返し周期に対応し、最下位のレイヤは前記必要とされる位置の数を有するステップと、
各ブロックの情報セグメントを、前記ブロックの前記繰り返し周期に対応する前記レイヤ上の未割当ての位置、および前記バイナリツリーの前記最下位レイヤまでの対応するすべての子ノードに割り当てるステップとを備えることを特徴とする方法。
【請求項１７】
前記情報ブロックは、前記優先順位の１番目であるヘッダ情報ブロックを含み、前記ヘッダ情報ブロックのセグメントは、数値的に連続した最初のチャネル位置に割り当てられることを特徴とする請求項１６に記載の方法。
【請求項１８】
その後の情報ブロックのセグメントは、最小数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項１７に記載の方法。
【請求項１９】
その後の情報ブロックのセグメントは、最大数値を有する未割当ての位置にできるだけ連続して割り当てられることを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、周期的にスケジューリングされる複数の情報ブロックが単一チャネルの物理レイヤにアクセスするための要件に関する。詳細には、本発明は、単一チャネルの物理レイヤの効率的な使用、および単一のチャネルへのアクセススケジューリングの最適化を実現することに関する。
【背景技術】
【０００２】
無線通信システムでは、複数の情報源からの複数の情報ブロックが、単一チャネルに周期的にアクセスするためにスケジューリングを要することがある。限られた伝送速度やパワーレベルなど、チャネルの物理レイヤの制約によって、それぞれの情報ブロックを複数のセグメントに分割し、それぞれのセグメントを、チャネルにアクセスするための位置にスケジューリングすることが必要となり得る。
【０００３】
異なる情報源をスケジューリングする際に、複数の要件を考慮しなければならない。単一のチャネルが複数のアドレスすなわち位置に分割され、それに対して情報セグメントの割当てすなわちスケジューリングが行われる。複数の情報源には、それに付随する情報ブロックセグメントがあり、これらのセグメントはチャネル位置に沿ってスケジューリングされるので、スケジューリングされた情報はチャネル上に多重化されていると見なされる。したがって、異なる情報セグメント間の位置の競合を回避しなければならない。すなわち、チャネル位置を２つの異なる情報ブロックのセグメントで共有することはできない。したがって、第１の要件は、それぞれの位置が１つの情報セグメントにしか割当てできないことである。
【０００４】
第２に、それぞれの情報源が必要とする繰り返し周期は、情報に関連する機能に基づいているので、単一のチャネルにアクセスするために異なる情報源が異なる周期を必要とする。たとえば、３Ｇ  ＵＭＴＳにおいて、ＢＣＣＨ（Ｂｒｏａｄｃａｓｔ  Ｃｈａｎｎｅｌ：同報チャネル）のシステム情報ブロック（ＳＩＢ）の周期が異なるということは、パワー制御やセル選択などのシステム機能の待ち時間が様々であることを意味する。ユーザ装置（ＵＥ）はシステム機能を実施するために必要とされるよりも速くシステム情報を受信することができるので、繰り返し周期が短くなれば、待ち時間が短くなる。しかし、この要件によって、チャネルの限られた帯域幅の効率的な使用が損なわれることになる。繰り返し周期が短いということは、単一のチャネルへの負荷が重くなることも意味しており、他の用途に帯域幅を割り当てる可能性が限られることになる。
【０００５】
第３に、チャネル効率を最大にするには、チャネル利用率が最大になるように、チャネル上の未割当ての位置を最小限に抑えなければならない。
【０００６】
第４に、情報はしばしば、同じ情報源のセグメントすべてが受信側に届くまで、読み取ることができないので、同じ情報ブロックのセグメントは、できるだけ連続してスケジューリングしなければならない。
【０００７】
この問題に対する１つの解決策は、先着順（ＦＣＦＳ：ｆｉｒｓｔ  ｃｏｍｅ  ｆｉｒｓｔ  ｓｅｒｖｉｃｅ）割当て方法を使用することであった。この方法では、スケジューラは最初に第１情報源の情報ブロックをスケジューリングする。第１情報源をスケジューリングした後、次いでスケジューラは、第２情報源の情報ブロックに、単一のチャネル上の位置を割り当てる。第２情報源をスケジューリングする際に、スケジューラは、第１情報源の情報ブロックに既に割り当てたチャネル位置を割り当てないようにする必要がある。したがって、その後にスケジューリングされる情報ブロックをスケジューリングする間、スケジューラは、以前にスケジューリングされた情報ブロックに既に割当て済みのすべての位置を把握している必要がある。
【０００８】
図１Ａおよび図１Ｂに、単一のチャネル、すなわちチャネルＡにアクセスするように３つの情報源をスケジューリングする例を示す。図では、３つの情報ブロック、情報源１、情報源２および情報源３は、様々なセグメント数および繰り返し周期を有する。図１Ｂに、情報源１、情報源２および情報源３のセグメント数および必要とされる繰り返し周期に基づいて行われる、チャネルＡ上の位置に対する赤、青および緑の情報セグメントのスケジューリングを示す。図１Ｂに示すチャネルＡから明らかなように、情報源１、情報源２および情報源３の情報ブロックのスケジューリング後に、未割当ての位置（８、９、１８、１９、２０．．．）が残っている。チャネルＡ上にスケジューリングすべき、異なるセグメント数および繰り返し周期の制約を伴う情報ブロックがさらに追加されると、１つまたは複数の上記要件を損なわないスケジューリング方法を実現することが難しくなる。
【０００９】
ＦＣＦＳ手法を用いると、同じ情報源の情報ブロックに属するセグメントを連続してスケジューリングすることができないなど、いくつかの不備（ｃｏｍｐｒｏｍｉｓｅ）が生じる。この解決策では、セグメント数の大きい情報に対応できるのに十分な連続する使用可能位置が確保されないからである。図１Ｂに、情報源３についてこうした不備が示されている。緑の情報セグメントはチャネルＡ上で連続してスケジューリングされていない。これによって、受信側は情報ブロックのすべてのセグメントが届くのを待つので、情報源３の情報ブロックの読取りが遅くなる。またこうしたスケジューリングは周期的な性質のものなので、２つの情報源が将来、どこかの位置で互いに競合することがあり、したがって、起こり得る競合を回避するために、情報セグメントを位置に割り当てる度に、グローバルサーチを実施する必要が生じる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記の要件を満たすように最適化を図りながら、所与の情報ブロックセットに必要な帯域幅を決定し、情報を効率的にスケジューリングする方法およびシステムが求められている。
【課題を解決するための手段】
【００１１】
本発明は、複数のアドレス位置に分割される単一の通信チャネル上に、複数の情報源からの情報ブロックの多重化されたスケジューリングを行うための方法を含む。それぞれの情報源の情報ブロックは、繰り返し周期を有し、複数のセグメントに分割される。チャネル上のスケジューリングされる位置の総数を決定した後、バイナリツリー（ｂｉｎａｒｙ  ｔｒｅｅ）上のノードに対応する不連続な順序で位置をマッピングし、それによって、バイナリツリーの各レイヤは特定の繰り返し周期に対応する。情報ブロックを繰り返し周期の昇順で割り当てる。それぞれのブロックの情報セグメントを、関連するバイナリツリーレイヤ上の未割当ての位置、およびそれに対応するすべての子ノードにスケジューリングする。
【発明を実施するための最良の形態】
【００１２】
本発明を図面を参照して説明する。これらの図面を通して、同じ番号は同様の要素を示す。
【００１３】
本発明によれば、ＩＮＦＯ1、ＩＮＦＯ2、．．．、ＩＮＦＯRで表されるＲ個の情報ブロックがあり、そのそれぞれが情報源に関連付けられている。情報ブロックＩＮＦＯはそれぞれ、その情報がどのくらいの頻度で単一のチャネルにアクセスしなければならないかを示す独自の繰り返し周期ＲＰを有し、セグメント数ＳＣ個のセグメントＳＥＧに分割される。このセグメント数は、１個の情報ブロックに対するセグメントＳＥＧの数である。単一のチャネルが複数のアドレス位置Ｐに分割され、これらのアドレス位置Ｐに対して、情報セグメントＳＥＧがスケジューリングすなわち割当てされる。
【００１４】
次式によって、単一のチャネルによってアクセスされる所与の情報源セットのために十分な帯域幅があるかどうかを判定する。
【００１５】
【数１】
2004530392.tif 000003
【００１６】
式１が真の場合、十分な帯域幅があることになる。
【００１７】
図２に、Ｎ個のレイヤを有し、最下位レイヤに２N個の位置を含むバイナリツリーの例を示す。Ｎは、２Nがすべての情報ブロックＩＮＦＯのうちで最大の繰り返し周期ＲＰになるように選択される。繰り返し周期ＲＰは通常、全体的なシステム要件によって決まり、Ｎを自然数として、２Nに相当することが好ましい。これによって、個々のいずれの位置においても、異なる情報ブロックＩＮＦＯの競合が回避される。
【００１８】
図２に戻ると、レイヤｎ（ただし、ｎ Ｎ）の各ノードは、引数０または１のＮ次元ベクトル（ａn，ａn-1，．．．，ａ1）として表すことができる。バイナリツリーは、それぞれのレイヤにおいて、引数ａnが左から右に交互に０か１になるように定義される。レイヤｎの各ノードはベクトルのバイナリ表現に等しい値に関連付けられる。たとえば、レイヤ値ｎ＝４、ベクトル（ａ4，ａ3，ａ2，ａ1）を有するノードＡのバイナリ表現は、（１０１１）であり、この値は１１に相当する。４つのレイヤ（Ｎ＝４）を有する図２のバイナリツリーでは、一番下の行に示すように、０、８、４、１２、２、．．．７、１５の順で１６（２4）個の位置がある。それぞれのノードは関連する親ノードと２つの子ノードを有する。
【００１９】
図３は、複数の情報ブロックを単一の通信チャネル上にスケジューリングするための、本発明による方法１５０を示すフロー図である。まず、式１を用いて、所与の情報ブロックセットのために十分な帯域幅があることを確認する（ステップ１００）。次いで、スケジューラは、すべての情報セグメントをスケジューリングできるようにするのに必要な位置の数を決定しなければならない（ステップ１０１）。ＰMAXは、すべてのセグメントをスケジューリングできるようにするのに必要な位置の最大数であり、以下のように表される。
【００２０】
ＰMAX＝２N−１                                                    （式２）
ただし、Ｎ＝ｌｏｇ2（ｍａｘＩＮＦＯr（ＲＰ））                      （式３）
【００２１】
それぞれの情報ブロックＩＮＦＯについて、Ｐ＝０からＰ＝２N−１の位置のうちから、ｉ＝（０，１，．．．，ＳＣ）として、位置Ｐ（ｉ）を選択する。
【００２２】
次いで、ステップ１０２で、すべての情報ブロックＩＮＦＯについて、その繰り返し周期ＲＰの昇順でソートされた情報リスト、リストＡを生成する。システムによっては、ある種の情報用に特定の位置を必要とすることがある。たとえば、情報ブロックＩＮＦＯが管理情報ベース（ＭＩＢ）などの制御情報である場合、その情報ブロックはヘッダＩＮＦＯと見なされて、リストＡの一番上に置かれる。リストＡ上で情報ブロックＩＮＦＯをソートする場合、非ヘッダＩＮＦＯはＲＰの昇順でソートされて、リストＡのヘッダＩＮＦＯのすぐ下に置かれる。スケジューラは、情報セグメントを単一のチャネル上に割り当てるための順序についてリストＡを参照する。図２に示すフォーマットを用いて、Ｎ個のレイヤおよび０から２N−１個の位置を有するバイナリツリーを生成する（ステップ１０３）。次いで、ステップ１０４で、位置割当てリストであるリストＢを生成し、このリスト上で、それぞれの情報ブロックＩＮＦＯについて、各情報セグメントＳＥＧを単一の位置Ｐに割り当てる。スケジューリングのための次のステップ、ステップ１０５では、バイナリツリーのどのレイヤを第１情報ブロックＩＮＦＯ1用に使用するかを決定する。レイヤｍについて、ｍは式４で定義される。
【００２３】
ｍ＝ｌｏｇ2（ＩＮＦＯ1（ＲＰ））．Ｎ                              （式４）
【００２４】
ステップ１０６で、Ｐ＝０からＰ＝（ＳＣ−１）の連続した数を用いて、第１情報ブロックＩＮＦＯ1のための位置を選択する。ステップ１０７で、第１情報ブロックＩＮＦＯ1用に割り当てられた位置に相当するｍレイヤ上のノードを、バイナリツリー上で仮想的にマークする。ｍレイヤ上の仮想的にマークされたノードより下のすべての子ノードも同様に、割当て済みとしてマークして、残りの情報ブロックＩＮＦＯのいずれかのセグメントに位置を割り当てる対象から除外する。ステップ１０８で、その次のＩＮＦＯをリストＡから取り出す。レイヤｋは以後にスケジューリングされるいずれかの情報ブロックＩＮＦＯrのためのレイヤを表し、式５で定義される。
【００２５】
ｋ＝ｌｏｇ2（ＩＮＦＯr（ＲＰ））．Ｎ                              （式５）
【００２６】
ステップ１０９で、位置ＰにＩＮＦＯの情報セグメントＳＥＧを割り当てるとき、２つの条件、すなわち１）ＩＮＦＯはヘッダＩＮＦＯのすぐ後のＩＮＦＯである（つまりＩＮＦＯがリストＡ上の第１非ヘッダＩＮＦＯである）かどうか、および２）ｋ＜ｍであるかどうか調べる。ステップ１０９の両方の条件を満たす場合、ステップ１１１で、Ｐ（０）からＰ（ＳＣ−１）までＩＮＦＯ  ＳＥＧを、空き位置Ｐのうちで最大数値かつ最小可能範囲となるｋレイヤ上の空き位置Ｐに割り当てる。そうではなく、ステップ１０９の条件を満たさない場合は、使用可能位置Ｐのうちで最小数値かつ最小可能範囲となるｋレイヤ上の位置Ｐに、ＩＮＦＯ  ＳＥＧを割り当てる（ステップ１１０）。
【００２７】
ステップ１１２で、割当て済みのすべてのＰノードを仮想的にマークし、ステップ１０７で、ｋレイヤ上のマークされたＰノードより下のすべてのノードを割当て済みとしてマークし、残りのＩＮＦＯに関する対象から除外する。最後に、すべての情報ブロックＩＮＦＯがスケジューリングされるまで、ステップ１０８から１１２を繰り返す（ステップ１１３）。
【００２８】
図４に、１１個の情報ブロック（ＭＩＢ、ＩＮＦＯ１〜ＩＮＦＯ１０）があり、そのそれぞれが独自のセグメント数ＳＣおよび繰り返し周期ＲＰを有する例を示す。ステップ１００で、式１を用いて、十分な帯域幅があるかどうかのチェックを以下のとおり行う。
【００２９】
【数２】
2004530392.tif 000004
【００３０】
したがって、十分な帯域幅があり、放送チャネルの利用率は９３．７５％となる。
【００３１】
１１個の情報ブロックのうちで最大の繰り返し周期ＲＰは、図４のＩＮＦＯ５およびＩＮＦＯ６に対応する１２８である。式３を用いると、Ｎ＝７になる。したがって、式２によって、放送チャネル上のスケジューリングすべき位置Ｐは０および１２７の間の範囲になる（ステップ１０１）。次いで、表１に示すように、非ヘッダブロックであるＩＮＦＯ１〜ＩＮＦＯ１０情報を、ＲＰの昇順で並び換える（ステップ１０２）。管理情報ベースＭＩＢはヘッダＩＮＦＯであり、情報ブロックを受信する通信システム用の制御情報を含むので、受信側が最初にこの情報を読むように、ＭＩＢの第１セグメントをＰ＝０に割り当てる。したがって、ＭＩＢのＲＰは情報ブロックのうちで最小のＲＰではないが、ＭＩＢが表１のリストＡの第１行目にくる。
【００３２】
【表１】
2004530392.tif 000005
【００３３】
レイヤ数がＮ＝７に確定されたので、図５Ａに示すように、７個のレイヤおよびＰ＝０からＰ＝１２７の位置を有するバイナリツリーを生成する（ステップ１０３）。それぞれの情報ブロックについて、割当て済みの位置Ｐ（ｉ）を追跡するために、位置割当てリストとしてリストＢを生成する（ステップ１０４）。式４を用いて、情報ブロックＭＩＢについてレイヤ値を計算する（ステップ１０５）。
【００３４】
ｍ＝ｌｏｇ2（ＩＮＦＯ1（ＲＰ））
＝ｌｏｇ2（１６）
＝４
【００３５】
次いで、表２に示すように、位置Ｐ（０）からＰ（４）について、ＭＩＢの５個のセグメントを連続する位置Ｐ＝０，１，２，３，４に割り当てる（ステップ１０６）。情報ブロックＩＮＦＯについて、それぞれの情報セグメントをスケジューリングし、それに対応する位置ＰをリストＢに記録する。
【００３６】
【表２】
2004530392.tif 000006
【００３７】
図５Ｂのバイナリツリーを参照すると、Ｐ＝０，１，２，３，４について、レイヤ４より下のすべてのノードは、残りの情報セグメント用の潜在的に割当て可能な位置として除外される（ステップ１０７）。たとえば、Ｐ＝０であるレイヤ４のノードＢでは、以下のノードは除外され、情報セグメントを含まなくなる。レイヤ５の２つのノード（Ｐ＝０，１６）、レイヤ６の４つのノード（Ｐ＝０，３２，１６，４８）およびレイヤ７の８つのノード（Ｐ＝０，６４，３２，９６，１６，８０，４８，１１２）。図５ＢのノードＢより下の網掛け部分は、こうした子ノードを除外することを示している。同様に、図５Ｂのレイヤ４より下の網掛け部分が示すように、Ｐ＝１，２，３，４に関連する子ノードも割当て済みとしてマークされる。
【００３８】
ＩＮＦＯ１０は、リストＡ上でＭＩＢのすぐ下にあるので、スケジューリングするべき次の情報ブロックである（ステップ１０８）。式５に基づいて、ＩＮＦＯ１０についてレイヤｋの値はｋ＝３になる。図５Ｂのバイナリツリー上でレイヤｋ＝３を見ると、Ｐ＝０からＰ＝４はＭＩＢに割当て済みなので、可能な選択の候補はＰ＝５，６または７になる。ｋ＜ｍかつＩＮＦＯ１０はリストＡの最初の非ヘッダＩＮＦＯであるので、ステップ１０９および１１１に従って、図５ＣにノードＣとして示す、これらのうちで最大の位置Ｐ＝７を選択する。ノードＣより下の網掛け部分は、レイヤｋ＝３のＰ＝７について、すべての子ノードを除外することを示している（ステップ１１２）。
【００３９】
ＩＮＦＯ１０がスケジューリングされたので、スケジューリングすべき次の情報についてリストＡを照会する。表１に示すように、ＩＮＦＯ１は、スケジューリングする次の順序にある。式５によって、ＩＮＦＯ１に関連するレイヤ値ｋ＝５を計算する（ステップ１０８）。図５Ｃを参照すると、レイヤ５上の使用可能ノードは、ＩＮＦＯブロックＭＩＢおよびＩＮＦＯ１０のスケジューリングによって除外されなかったものである。最初の非ヘッダＩＮＦＯがスケジューリングされたので、ステップ１０９および１１０に従って、最小値の数値を有し、互いにできるだけ連続する位置に、残りのすべてのＩＮＦＯをスケジューリングする。したがって、図５Ｄに示すように、ＩＮＦＯ１の２つのセグメントを位置Ｐ＝５，６に割り当てる。
【００４０】
ステップ１０８、１０９、１１０および１１２を繰り返して、次に、リストＡに示される順序に従って情報ブロックＩＮＦＯ４およびＩＮＦＯ７をスケジューリングする。ＩＮＦＯ１と同様に、情報ブロックＩＮＦＯ４およびＩＮＦＯ７のレイヤ値はｋ＝５であり、したがって、次の連続する使用可能位置Ｐ＝８およびＰ＝９をＩＮＦＯ４およびＩＮＦＯ７にそれぞれ割り当てる。図５Ｅにこれらの位置のマーキングを示す。
【００４１】
情報ブロックＩＮＦＯ２およびＩＮＦＯ３は、同じ繰り返し周期ＲＰ３２、従ってレイヤ値ｋ＝５を有する。図５Ｅを照会すると、レイヤ５では、位置Ｐ＝１０，１１が使用可能であり、図５Ｆに示すようにこれらの位置を選択する。
【００４２】
リストＡに示されるスケジューリングすべき次の情報ブロックは、レイヤ値ｋ＝６を有するＩＮＦＯ９である。レイヤ６上で最小の数値をもつ５つの連続する使用可能位置、すなわちＰ＝２４，２５，２６，２７，２８に、ＩＮＦＯ９の５つの情報セグメントをスケジューリングする。これらの位置をリストＢ上に記録し、図５Ｇに示すように、これらのノードより下にあるレイヤ７上の位置を以後の対象から除外する。同様に、情報ブロックＩＮＦＯ８は、５つの情報セグメントを有し、レイヤ６に関連する。５つの連続する位置を求めてレイヤ６上の残っている使用可能位置を探すと、Ｐ＝５６，５７，５８，５９，６０が得られる。前の情報ブロックと同様に、これらの位置をリストＢ上に記録し、対応するレイヤ７上の子位置を対象から除外する（図５Ｇ）。残りの情報ブロック、ＩＮＦＯ５およびＩＮＦＯ６は、レイヤ値ｋ＝７および１０個の情報セグメントを有する。図５Ｈに移ると、ＩＮＦＯ５のセグメントについて、レイヤ７上の残りの使用可能位置から、最小可能範囲となる１０個の位置、Ｐ＝１２，１３，１４，２１，２２，２９，３０，４４，４５，４６が選択される。同様に、ＩＮＦＯ６のセグメントをレイヤ７上の使用可能位置にスケジューリングし、表３に示すように、リストＢに記録する。この表がシステム１０についての完成したリストＢを示している。
【００４３】
【表３】
2004530392.tif 000007
【００４４】
表３の最終列は、それぞれの情報ブロックのＰ範囲を示している。それぞれ１０個の情報セグメントを有する情報ブロックＩＮＦＯ５およびＩＮＦＯ６では、位置の範囲値は３４である。この値は、セグメントが単一のチャネルに従って比較的コンパクトな位置群に割り当てられているので、１２８個の位置のうちから、ＩＮＦＯ５およびＩＮＦＯ６について完全な情報セグメントセットが最適化されて受信されることを示している。したがって、受信側は、情報セグメントが１２８個の使用可能位置に沿ってより広い範囲に広がっている場合よりも、高速かつ効率的にＩＮＦＯ５およびＩＮＦＯ６を読み取ることができる。他のすべての情報ブロックＩＮＦＯは、セグメント数ＳＣにまったく等しいＰ範囲、すなわち最大可能効率を有する。
【００４５】
本発明の方法は、メモリを備えたマイクロプロセッサによって実装できることが当業者には明らかであろう。バイナリツリーマッピング（ｂｉｎａｒｙ  ｔｒｅｅ  ｍａｐｐｉｎｇ）はメモリに常駐することができる。情報セグメントがスケジューリングされるとき、マイクロプロセッサは、情報セグメントが対応するバイナリツリーレイヤ上のそれぞれの位置、および対応するすべての子ノードの位置に割り当てられていることを反映するようにマッピングを更新する。
【００４６】
当業者には、本発明に従ってＢツリーまたはスプレイ木（ｓｐｌａｙ  ｔｒｅｅ）を同様にマッピングすることができることも理解されたい。
【図面の簡単な説明】
【００４７】
【図１Ａ】３つの異なる情報ブロックを単一チャネル上に多重化する従来技術を示す図である。
【図１Ｂ】３つの異なる情報ブロックを単一チャネル上に多重化する従来技術を示す図である。
【図２】４つのレイヤを有するバイナリツリーを示す図である。
【図３Ａ】バイナリツリーを使用して、多重化された単一チャネル上に複数の情報源をスケジューリングするための方法フロー図である。
【図３Ｂ】バイナリツリーを使用して、多重化された単一チャネル上に複数の情報源をスケジューリングするための方法フロー図である。
【図４】多重化された単一チャネル上にスケジューリングされる情報源からの複数情報ブロックのサンプルを示す図である。
【図５Ａ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｂ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｃ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｄ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｅ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｆ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｇ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図５Ｈ】バイナリツリー上の割り当てられた位置に図４の情報ブロックをマッピングする進行経過を示す図である。
【図１Ａ】
2004530392.tif 000008
【図１Ｂ】
2004530392.tif 000009
【図２】
2004530392.tif 000010
【図３Ａ】
2004530392.tif 000011
【図３Ｂ】
2004530392.tif 000012
【図４】
2004530392.tif 000013
【図５Ａ】
2004530392.tif 000014
【図５Ｂ】
2004530392.tif 000015
【図５Ｃ】
2004530392.tif 000016
【図５Ｄ】
2004530392.tif 000017
【図５Ｅ】
2004530392.tif 000018
【図５Ｆ】
2004530392.tif 000019
【図５Ｇ】
2004530392.tif 000020
【図５Ｈ】
2004530392.tif 000021
【国際公開パンフレット】
2004530392.tif 000022
2004530392.tif 000023
2004530392.tif 000024
2004530392.tif 000025
2004530392.tif 000026
2004530392.tif 000027
2004530392.tif 000028
2004530392.tif 000029
2004530392.tif 000030
2004530392.tif 000031
2004530392.tif 000032
2004530392.tif 000033
2004530392.tif 000034
2004530392.tif 000035
2004530392.tif 000036
2004530392.tif 000037
2004530392.tif 000038
2004530392.tif 000039
2004530392.tif 000040
2004530392.tif 000041
2004530392.tif 000042
2004530392.tif 000043
2004530392.tif 000044
2004530392.tif 000045
2004530392.tif 000046
2004530392.tif 000047
2004530392.tif 000048
2004530392.tif 000049
2004530392.tif 000050
2004530392.tif 000051
2004530392.tif 000052
【国際調査報告】
2004530392.tif 000053
2004530392.tif 000054