(57)【要約】  無線マルチキャストシステムで使用する装置は、複数の受信機から受信したチャネル状態及び／又は速度情報を記憶するためのストレージと、元のマルチキャスト／同報通信コンテンツから符号化ブロックを生成するためのエンコーダと、送信タイムスロット毎に、複数の受信機のうちのいくつかの受信機に同報通信チャネルを介して情報を同報通信するための送信機と、送信機に異なる送信タイムスロットごとに異なる速度で送信させるよう送信機の送信速度を適合させるコントローラであって、符号化された情報を同報通信する送信機の送信速度を、同報通信チャネルに関連付けられ複数の受信機から受信したチャネル状態情報と、複数の受信機のうち、各送信タイムスロットの間に同報通信チャネルを介して同報送信を確実に受信するターゲットにされた受信機部分集合とに基づいて決定するコントローラと、を備える。【選択図】図３
2010523011.tif 000002
【特許請求の範囲】
【請求項１】
複数の受信機を有する無線マルチキャストシステムにおいて使用するための装置であって、
前記複数の受信機から受信したチャネル状態及び速度情報のうち少なくとも１つを記憶するためのストレージと、
送信タイムスロット毎に前記複数の受信機のうちのいくつかの受信機に同報通信チャネルを介して情報を同報通信するための送信機と、
前記送信機に異なる送信タイムスロットごとに異なる速度で送信させるように前記送信機の送信速度を適合させる、前記ストレージ及び前記送信機に接続されたコントローラであって、前記情報を同報通信する前記送信機の送信速度を、前記同報通信チャネルに関連付けられ前記複数の受信機から受信したチャネル状態情報と、前記複数の受信機のうち、前記各送信タイムスロットの間に前記同報通信チャネルを介して同報通信送信を確実に受信するターゲットにされた受信機の部分集合とに基づいて決定するコントローラと、
を備える装置。
【請求項２】
同報通信チャネルを介して同報通信情報を送る送信機と、
前記同報通信チャネルを介して送信を受信する複数のノードと、
前記送信機に、前記受信機から受け取ったチャネル状態と、存在する、ターゲットにする信頼性とに応じて異なる速度で送信させるように、速度適合化を実施するコントローラと、
を備える無線マルチキャストシステム。
【請求項３】
無線マルチキャストシステムにおける複数の受信機のチャネル状態情報を受信するステップと、
前記送信機に異なる送信タイムスロットごとに異なる速度で送信させるように前記送信機の送信速度を適合させるステップであって、送信タイムスロット毎に前記複数の受信機に同報通信チャネルを介して情報を同報通信する前記送信機の送信速度を、前記同報通信チャネルに関連付けられ前記複数の受信機から受信したチャネル状態情報と、前記複数の受信機のうち、前記各送信タイムスロットの間に前記同報通信チャネルを介して同報通信送信を確実に受信するターゲットにされた受信機部分集合とに基づいて決定するステップを含む、ステップと、
を含む方法。
【発明の詳細な説明】
【優先権】
【０００１】
[0001]本特許出願は、２００６年１２月２２日に提出した、「AMethod and Apparatus for Opportunistic Multicasting with Coded Scheduling inWireless Networks」という名称の、対応する仮出願第６０／８７６９０３号の優先権を主張し、また、参照のために本明細書に完全に組み込むものである。
【関連出願】
【０００２】
[0002]本出願は、２００６年１１月２７日に提出された「AMethod and Apparatus for Layered Rateless Coding」という名称の米国特許出願番号第１１／６０５８１２号と、２００７年５月４日に提出された「Hybridand Improved Approaches to Layered Rateless Coding」という名称の米国特許出願番号第６０／９２７８１４号と、２００７年１０月１６日に提出された「Information Delivery Over Time-Varying Network Topologies」という名称の米国特許出願番号第１１／８７３２４８号と、２００７年３月１３日に提出された「A Method and Apparatus for Prioritized Information Delivery withNetwork Coding Over Time Varying Network Topologies」という名称の米国特許出願番号第６０／９０６９９９号とに関連するものであり、それら全てが、本発明の法人譲受人に譲渡されたものである。
【発明の分野】
【０００３】
[0003]本発明はマルチキャスト同報通信の分野に関し、より詳細には、無線ネットワークにおける臨機応変型スケジューリング及び送信速度適合化によるネットワークマルチキャスティングに関する。
【発明の背景】
【０００４】
[0004]Ｍ個の受信機の集合ＲＸ＝｛ＲＸ１，ＲＸ２，…，ＲＸＭ｝について考察する。ときには、この集合内の各受信機が完全な情報を再生し同時に高いスループットを達成できるように、その各受信機に同じ情報を送ることが望ましいことがある。一般性を失うことなく、時間をスロットに分割し、そのスロット内で各受信機ＲＸｊ∈ＲＸが、ｋ番目のスロットにおける平均受信信号対雑音比ＳＮＲｊ（ｋ）で表される定常チャネル品質を観測するものと仮定する。タイムスロットの開始時点で、送信機が（ある程度の正確さをもって）各受信機のチャネル状態を（例えばフィードバックチャネルを介して）知っているものとする。チャネル状態情報（ＣＳＩ）は、所与の信頼性又は達成可能性をもって、そのチャネルを介して１秒当たり何ビット（又は、１送信当たり何ビット）を送ることができるかを指示する。例えば、情報理論によれば、受信機ｘにおいて、加算性ホワイトガウスノイズ（ＡＷＧＮ）チャネルを介してＣｘ（ｋ）＝０．５ｌｏｇ２（１＋ＳＮＲｘ（ｋ））という送信速度が達成可能である。送信機がｋ番目のタイムスロットの間にＲ＞Ｃｘ（ｋ）という速度で情報を送った場合、受信機ｘはそのスロットの間に送られた情報を再生することができない。一方、Ｒ＜Ｃｘ（ｋ）という速度で送信された情報はどれも、ｋ番目のタイムスロットの間にｘによって無事に再生することができる。
【０００５】
[0005]各タイムスロットの開始時点で、受信機がチャネルの品質について降順、すなわち、ＳＮＲ１（ｋ）≧ＳＮＲ２（ｋ）≧・・・≧ＳＮＲＭ（ｋ）の順に並べられると仮定する。その場合、タイムスロットの始まりにおいて送信機によって設定された速度は、そのタイムスロットの間に送られた情報をどの受信機部分集合が再生することができるかを指示する。この速度ＲＬ（ｋ）は、高い方からＬ個のチャネル品質を有する受信機が、残りの（Ｍ−Ｌ）台の受信機にはできないが、スロットｋの間に同報通信情報を本当に再生することができる速度として定義される。例えば、理想的な想定のもとでＡＷＧＮチャネルを介した場合、ＲＬ（ｋ）は０．５ｌｏｇ２（１＋ＳＮＲＬ（ｋ））に等しくなる。集合ＲＸＬ（ｋ）はｋ番目のスロットの間に、高い方からＬ個の品質値、例えばＳＮＲを有する受信機部分集合として定義される。言い換えれば、ＲＸＬ（ｋ）は、速度ＲＬ（ｋ）で送信された情報を無事に再生することができる受信機の集合を現す。ここでは、指標関数Ｉ（ｘ）を、ｘが真である場合には１に等しく、そうでない場合には０に等しいと定義する。例えば、ｘ∈ＲＸＬ（ｋ）の場合にはＩ（ｘ∈ＲＸＬ（ｋ））＝１であり、
【数１】
2010523011.tif 000003
の場合には、Ｉ（ｘ∈ＲＸＬ（ｋ））＝０である。これらの定義を心に留めておくと、Ｔ個のスロットのフレームにおいて、受信機ｘで観察される平均速度を次のように書くことができる。
【数２】
2010523011.tif 000004
【０００６】
[0006]ここではＬ及びＴをシステムパラメータとして使用していることに注意されたい。Ｒｘ（Ｌ，Ｔ）はランダムな変数であるので、これらのパラメータを、Ｒｘ（Ｌ，Ｔ）の期待値、すなわちＥ［Ｒｘ（Ｌ，Ｔ）］が最大になるように選択することができる。ＲＬ（ｋ）×Ｉ（ｘ∈ＲＸＬ（ｋ））が完全に同じように配布されると、Ｅ［Ｒｘ（Ｌ，Ｔ）］はＴとは無関係になり、最大化はＬについてのみ実行される。一般的に、最大値はＬ＝１又はＬ＝Ｍである端点に一致することはなく、むしろ中間点で一致する。最大点の位置はチャネル統計に左右される。
【０００７】
[0007]異なるユーザが異なるチャネル統計を観測する場合（例えば、あるユーザが他のユーザよりも送信機に近い場合や、ユーザによっては送信機からみて直線上にあり他のユーザにとってはそうではない場合など）、ユーザによっては異なるＬの値おいてより多くの恩恵を得ることがある。
【０００８】
[0008]臨機応変型マルチキャスティングは当技術分野においてはよく知られている。チャネルの品質についてユーザをソートし、中間のユーザを、ターゲットとするチャネル品質レベルとして選定し、無線チャネルを介した送信速度を設定するという戦略を提案している者がいる。この場合、濃度Ｎ／２（Ｎは偶数とする）の考えられるあらゆる受信機部分集合について別個の送信待ち行列が使用される。例えば、ユーザに１から６までの番号が振られている、６ユーザのシステムの場合、Ｃ（６，２）＝６！／２！／（６−２）！＝１５の、濃度２の異なる部分集合を定義することができる。あらゆる部分集合Ａについて、補部分集合ＡＣ＝｛１，２，３，４，５，６｝／Ａが得られ、例えば、｛１，４，５｝の補部分集合は｛２，３，６｝である。新しい情報パケットが受信されたときはいつでも、そのパケットは２つの待ち行列、すなわち、高い方からＮ／２個のチャネル品質値（すなわちＳＮＲ）を有する受信機の部分集合及びその補集合の上にコピーされる。各受信機がＩＩＤチャネル品質メトリクスを備えると仮定すると、各部分集合は、現在のチャネル状態情報によって指示されているように送信機によりスケジュールされる機会を同等に有することになる。各パケットは全ての受信機によって受信され得るため、パケットがコピーされる各待ち行列は、少なくとも一度はスケジュールされる必要がある。このシステムは主として３つの問題を抱えている。まず、このシステムは最適なものではなく、中間ユーザについてのみ速度適合化を考慮している。第２に、送信機がＮ／２以上の受信機をターゲットとした場合に帯域の無駄が生じる。このような状況では、相互に排他的な、同じサイズの受信機部分集合を見つけることはできず、提案されているスケジューリングは、受信機のいくつかに対する再送信という結果になる。例えば、最適な戦略が、時刻ごとに、中間ユーザではなく、６台のうち最良の４台の受信機をターゲットにすることであると仮定する。最適な部分集合が｛２，３，５，６｝（例えば、これらは、現在、高い方から４つの平均ＳＮＲ値を有する受信機）であるとすると、その補部分集合は｛１，４｝であり、濃度は４よりも少ない。であるから、部分集合｛２，３，５，６｝についてパケットをスケジュールすると、そのパケットは、濃度４の部分集合に対応し、かつ｛１，４｝も含む待ち行列にコピーされる。しかし、その待ち行列がスケジュールされたとき、少なくとも２台の受信機は新しい情報を得られないことが約束され、その観点からすると、送信が無駄にされることになる。第３に、指数関数的数の待ち行列を維持する必要があるため、この解決策はユーザ数により指数関数的に複雑さが増す。
【０００９】
[0009]符号化されたビットストリームを送る、その他の臨機応変型マルチキャスティング戦略も知られている。しかしそれらは、後に再生サイクルが続く送信を伴うか、あるいは作業節約型ではない（すなわち、送信機は十分に良い送信機会が発生するまでアイドル状態であり得る）。
【００１０】
[0010]臨機応変型スケジューリングに関する文献が存在するが、この文献はそれを、各受信機がフェーディング同報通信チャネルを介して独立した情報ストリームを要求する、ユニキャストフローのために使用することを提案している。
【００１１】
[0011]抹消符号、レートレス符号、及びそれらの応用も当技術分野においてよく知られていることにも注意されたい。
【発明の概要】
【００１２】
[0012]臨機応変型マルチキャスティングのための方法、装置、及びシステムを説明する。一実施形態では、無線マルチキャストシステムにおいて使用するための装置は、前記複数の受信機から受信したチャネル状態及び／又は速度情報を記憶するためのストレージと、元のマルチキャスト／同報通信コンテンツから符号化ブロックを生成するためのオプションのエンコーダと、送信タイムスロットごとに、複数の受信機のうちのいくつかの受信機に同報通信チャネルを介して符号化された情報を同報通信するための送信機と、前記送信機に異なる送信タイムスロットごとに異なる速度で送信させるよう前記送信機の送信速度を適合化するために、前記ストレージ及び前記送信機に接続されたコントローラであって、前記符号化された情報を同報通信する前記送信機の送信速度を、前記同報通信チャネルに関連付けられ前記複数の受信機から受信したチャネル状態情報と、前記複数の受信機のうち、前記各送信タイムスロットの間に前記同報通信チャネルを介して同報通信送信を確実に受信するターゲットにされた受信機部分集合とに基づいて決定するコントローラと、を備える。
【００１３】
[0013]本発明は、以下に記載の詳細な説明から、また、本発明の様々な実施形態の添付の図面から、より完全に理解することができるであろう。しかしそれらは、本発明を特定の実施形態に限定するものとしてとるべきものではなく、説明及び理解のためのものでしかない。
【本発明の詳細な説明】
【００１４】
[0020]無線ネットワークにおけるマルチキャスティングのための方法及び装置について説明する。一実施形態では、マルチキャスティングは、符号化されたスケジューリングを含む。本発明の実施形態は、同じ情報が同じ受信機にマルチキャストされる無線ネットワークに著しい容量ゲインを提供する。無線ネットワークでは、媒体は本来的に同報通信のためのものであるため、送信機で送られる情報は多くのユーザによって同時に受信される。しかし各受信機は、異なる、且つ一般に時間的に変化する、チャネル品質を観測する。このようなチャネル品質は、所与の時刻における各受信機に配信可能な最大速度を決定する。これらの条件のもとで、異なる１ユーザ当たりの短期的及び長期的なマルチキャストスループットを達成するために、異なる送信戦略が使用される。極端な場合、各送信において送られた情報を誰もが無事に再生できることを保証するために、最悪のケースのユーザについて送信が行われることがある。最悪のケースのユーザのチャネル品質はシステム内の多くのその他のユーザよりも著しく低い可能性があるため、この戦略は、誰にとっても非常に低い速度の送信という結果を招くことがあり、それによって、はるかに良いサポート可能なチャネル速度を有するユーザが不利な立場に置かれることになる。反対に極端な場合には、送信機は各送信機会において最良のチャネル品質を有するユーザのみを臨機応変にターゲットにすることがあり、それによって時刻ごとの送信速度を最大にする。このような戦略の欠点は、送信機会ごとにベストケースのユーザのみが無事に情報を再生することができ、ユーザはチャネル条件が自分に有利になるまで待たなければならない。この待機期間はユーザ１人当たりのマルチキャストスループットを著しく下げる可能性がある。したがって、しばしば、ここで「臨機応変型マルチキャスティング」と呼ぶ、より良い戦略が、より大きいユーザ集合に焦点を合わせ、しかし非常にチャネル品質が低いユーザを取り除くことによって、スケジューラにおける瞬間送信速度及びユーザ１人当たりの待機時間のバランスを注意深くとる。
【００１５】
[0021]臨機応変型マルチキャスティングは、時空間を越えたチャネル品質の広がりを利用することによって（すなわち、マルチユーザダイバーシチ）実質的にスループットを増加させるが、送信機におけるスケジューラは、各受信機において同じ同報通信情報が受信されることを保証しなければならない。一実施形態では、これは、注意深く送信を調整することによって成し遂げられる。一実施形態では、システムは、どの時点においても、何の情報がどのユーザ集合によって受信されたかを追跡する。この情報と現在のチャネル状態とが与えられると、スケジューラは、どの受信機（ユーザ）部分集合がいまだにそのデータを受信することを必要としているかに応じて、どの情報を送るべきかを決定する。
【００１６】
[0022]一実施形態では、受信機が十分な数の送信された符号化ブロックを成功裏に再生することができる限り、受信機が完全な同報通信情報を再生することを可能にする、固定速度又はレートレス抹消符号が使用される。このような場合、システムが追跡しなければならない情報は少なくてよく、システムはまた、当然、送信エラーからの立ち直りも早い。本発明の一実施形態はこれらの符号の特定の実装に依存するものではなく、また、新しい符号化技術を提供することを主張するものでもない。本発明の一実施形態は、これらの符号のいずれかを最適な臨機応変型マルチキャスティングと一緒に使って、単純でスケーラブル（例えばユーザ数について）、かつ最適な（例えば、再送信や無駄なスケジュールによって送信機会を無駄にすることが全くない）マルチキャスティング装置を提供することができる。
【００１７】
[0023]以下の説明では、本発明をより完全に説明するために、多数の詳細を記載している。しかし、当業者には、これらの具体的な詳細なしでも本発明を実施できることが明らかであろう。他の場合には、本発明を不明瞭なものにすることを避けるために、よく知られている構造やデバイスを、詳細にではなくブロック図という形態で示している。
【００１８】
[0024]以下に続く詳細な説明の一部は、コンピュータメモリ内のデータビット上のオペレーションのアルゴリズムや記号表現によって提示される。これらのアルゴリズムの記載及び表現は、データ処理技術分野における熟練者が、自分の作業の内容を他のその分野の技術者に最も有効に伝えるするための手段である。ここでは、また一般に、アルゴリズムとは、所望の結果を導く、自己矛盾のない一連のステップとして考えられる。それらのステップは、物理量の物理的操作を必要とするものである。通常、必ずというわけではないが、これらの量は、保存、転送、接続、比較、そうでなければ操作を行うことが可能な、電気又は磁気信号の形態をとる。時々、主として一般的な使用法であるという理由から、これらの信号をビット、値、エレメント、記号、文字、用語、又は数などと呼ぶことが便利であることがわかっている。
【００１９】
[0025]しかしながら、これら及び同様の用語は全て、適切な物理量に関連付けられるべきものであり、また、それらの量に貼られる便利なラベルにすぎないことを心に留めておくべきである。別途明確に述べていない限り、以下のディスカッションから明らかなように、この説明を通して、「処理」又は「コンピューティング」又は「算出」又は「決定」又は「表示」などの用語を使ったディスカッションは、コンピュータシステムのレジスタやメモリ内の物理（電子）量として表されたデータを操作及び変形して、そのコンピュータシステムのレジスタやメモリ内、又はその他のそのような情報記憶デバイス、送信デバイス又はディスプレイデバイス内の同じく物理量として表された他のデータにする、コンピュータシステム、又は同様の電子コンピューティングデバイスのアクション及びプロセスについてのものであることを理解されたい。
【００２０】
[0026]本発明はまた、本明細書におけるオペレーションを実施するための装置に関する。この装置は、要求される目的のために特別に組み立てられたものであってもよいし、あるいは、内部に保存されたコンピュータプログラムによって選択的に起動又は再構成される汎用コンピュータから成るものであってもよい。そのようなコンピュータプログラムを、コンピュータ読み取り可能記憶媒体に記憶することができる。コンピュータ読み取り可能記憶媒体は、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む任意の種類のディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気又は光カード、あるいは電子命令を記憶するのに適した任意の種類の媒体などで、それぞれがコンピュータシステムバスに連結されるものであるが、それらに限定されるものではない。
【００２１】
[0027]ここで提示されるアルゴリズム及び表示は、本来的にいずれかの特定のコンピュータ又はその他の装置に関連するものではない。本明細書における教示に従って、様々な汎用システムをプログラムと共に使用することができる。あるいは、必要とされる方法ステップを実施するためには、より特殊化された装置を組み立てるのが便利であることがわかる場合もあろう。様々なこれらのシステムに必要な構造が、以下の説明から明らかになろう。さらに、本発明は、いずれかの特定のプログラミング言語に関して記載したものではない。本明細書に記載されているように、本発明の教示を実装するために様々なプログラミング言語を使用できることを理解されたい。
【００２２】
[0028]マシン読み取り可能媒体には、マシン（例えば、コンピュータ）が読み取り可能な形態で情報を記憶又は送信するための任意のメカニズムが含まれる。例えば、マシン読み取り可能媒体には、読み取り専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、電気、光、音響、又はその他の形態の伝達信号（例えば、搬送波、赤外線信号、ディジタル信号など）などが含まれる。
【００２３】
概略
[0029]図１は、無線マルチキャストシステムの一実施形態のブロック図である。図１を見ると、無線マルチキャストシステムは同報通信チャネルを介して同報通信情報を送る１台の送信機１０１を有し、複数の受信機（ノード）１０２〜１０４はこの同報通信チャネルを介して受信することができる。したがって、同じ情報が全ての受信機から要求され、それらの受信機は、同報通信された情報を聴いたり再生することを試みる。一実施形態では、同報通信チャネルは、タイムスロット、周波数帯域、ＯＦＤＭサブバンド、拡散符号、又は論理チャネル（例えば、一連の周波数帯域又は一組のタイムスロット）を含む。各受信機は、そのチャネル上で聴いたり受信したりすることができる。３台の受信機を示してあるが、本発明は、３台の受信機を有するシステムに限定されるものではなく、このようなシステムは、いくつでも受信機を備えることができる（例えば、４、５、・・・１０、・・・１００、・・・）。
【００２４】
[0030]受信機１０２〜１０４のそれぞれは、時間によって変化するチャネル条件を経験する。一実施形態では、チャネル条件は準定常であり、次のスロットが開始する前に、受信機と送信機１０１の両方において知ることができる。一実施形態では、フィードバックメカニズムは、チャネル条件を表す、受信機１０２〜１０４のチャネル状態を送信機１０１に返す。フィードバックメカニズムは、受信機１０２〜１０４と送信機１０１の間に無線チャネル又は有線チャネルを含むことができる。フィードバックは、受信したチャネル品質を送り主に返すという明示的通信の形態で行い得る一方、別の実施形態では、フィードバックは、逆方向チャネルの品質を観察し、前方向及び反対方向のチャネル対称性を使うことにより送り主側で暗黙的に行われる。
【００２５】
[0031]送信機１０１は、送信機１０１を制御するコントローラ１１０を含む。一実施形態では、コントローラ１１０は、送信機１０１が同報通信チャネルを介して同報通信情報を送信する異なるチャネル速度又は送信速度を選択する速度アダプタとして動作する。このような場合、送信速度の選択は送信が行われる時期（例えば、タイムスロット）ごとに行われる。一実施形態では、コントローラ１１０は、速度適合化機能を提供する。これは、送信機１０１が、チャネル状態と、存在する、ターゲットとする信頼性とに応じて、異なる速度で送信することができるようにする機能である。一実施形態では、この速度適合化は、送信機会ごとに受信機１０２〜１０４の部分集合をターゲットとすることにより臨機応変なやり方で行われ、この場合、ターゲットとする部分集合の受信機の間で最悪のチャネル条件を満足するように速度が設定される。この場合、設定された送信速度は、どの受信機部分集合が同報通信された情報を実際に再生できるかを指示する。場合によっては、ターゲットの集合に入らない１つ又は複数の受信機が、設定された送信速度でマルチキャストデータを再生するのに十分な良いチャネル品質を観測できる。これらの受信機は、その場合、送信された情報を再生することができるので、実際にマルチキャストされたデータを所与のスロットで再生できる受信機部分集合は、ターゲットにされた部分集合よりも大きくなり得る。もともとターゲットにされた部分集合に含まれていた受信機が、見積りよりも悪いチャネル条件になり、そのため、実際のオペレーションではデータを再生できないという場合もあり得る。
【００２６】
[0032]図２は、送信機１０１などの送信デバイスの一実施形態のブロック図である。図２を見ると、送信デバイスは、フィードバックチャネル入力２１１を介して、無線マルチキャストシステム内の複数の受信機から受信されるチャネル状態情報２１１を記憶するための、ストレージ又はその他のメモリ２１２を含む。無線送信機／受信機２０２は、同報通信情報２０１を受信し、それを、送信タイムスロットごとに、同報通信チャネル及びアンテナ２０４を介して、マルチキャストシステムの複数の受信機のうちのいくつかの受信機に同報通信するために接続されている。
【００２７】
[0033]コントローラ２０２は、送信機の送信速度を適合化して、送信機に異なる送信タイムスロットごとに異なる速度で送信させるようにするために、ストレージ２１２及び送信機／受信機２０３に接続されている。一実施形態では、コントローラ２０２は、複数の受信機から受信されてストレージ２１２に記憶された、同報通信チャネルに関連したチャネル状態情報２１０と、タイムスロットの間に同報通信チャネルを介して同報通信送信を確実に受信するようターゲットにされた複数の受信機のうちの受信機部分集合とに基づいて、情報を同報通信する送信機２０３の送信速度を決定する。
【００２８】
[0034]一実施形態では、コントローラ２０２は、受信機部分集合（図１の受信機１０２〜１０４）のうちで最悪のチャネル条件を満足するよう送信機２０３の送信速度を設定することにより、送信機２０３の送信速度を適合させる。別の実施形態では、コントローラ２０２は、１タイムスロットの間に少なくとも１回のマルチキャスト送信が行われるようにすることを含む、マルチキャスト送信のための速度適合化を行い、送信機２０３のその送信速度を設定することによって、送信機２０３の送信速度を適合させる。この場合、その送信速度は、そのタイムスロットでベストＬ人のユーザに役立つ送信速度である。送信機２０３はそのタイムスロットの間ずっとその送信速度で送信することに注意されたい。
【００２９】
[0035]一実施形態では、コントローラ２０２は、個々のチャネル状態情報に基づいてマルチキャストシステム内の複数の受信機をソートしてソートリストを作成し、最適順序情報に基づいてそのソートリスト内の値を決定し、そして、少なくとも１つの過去のチャネル状態情報履歴と複数の受信機の全ての受信機に関連した送信スケジュールとが与えられると、ソートリスト内の値以上の達成可能送信速度を有する全ての受信機を含むように受信機部分集合を決定することによって、受信機部分集合を識別する。
【００３０】
[0036]別の実施形態では、コントローラ２０２が、マルチキャストシステム中の複数の受信機の各受信機の達成可能な速度を、次のタイムスロットでの順番でソートしてリストにすることによって、受信機部分集合を選択し、次いで、リスト中の１台の受信機の１つの達成可能速度に等しい送信速度を設定する。この場合、その１つの達成可能速度とは、所定数の受信機に関連付けられ、リスト中の最高の達成可能速度を含むグループにおける最低達成可能速度である。このような場合、コントローラ２０２は、設定された送信速度以上の信頼できる送信速度を有する受信機に対しての、次のタイムスロットでのデータの送信をスケジュールする。
【００３１】
[0037]一実施形態では、コントローラ２０２は、各受信機について１チャネル当たりの容量を計算し、マルチキャストシステム内の受信機グループについて１チャネル当たりの容量を正規化したものをソートし、そのソートした受信機グループから所定数の受信機を選択する。この場合、送信速度は、その所定数の受信機の中のいくつかの受信機の送信速度のうち最低の送信速度に応じて設定する。ユーザのチャネル速度の正規化は、各受信機に送られる平均スループット、各受信機のスケジューリング間の時間、各受信機の平均チャネル品質、各受信機によって受信される実際のスループット（この場合、この受信されたスループットは、その後、フィードバックチャネルを介して送信機に伝達され、返される）、受信機において観測されるアプリケーションの品質（例えば、速度ひずみの測定）などを考慮することができる。
【００３２】
[0038]一実施形態では、コントローラ２０２は各受信機のチャネル状態情報に基づいて関数を計算し、その関数の計算結果について複数の受信機のうちのいくつかの受信機をソートする。一実施形態では、この関数は、チャネル状態情報と過去の受信機への送信のスケジューリングに関連する情報（例えば、受信機それぞれの平均スループット）とに基づく。別の実施形態では、この関数は現時点におけるマルチキャストシステムの各受信機の容量に対応する。さらに別の実施形態では、この関数は、現時点における各受信機の、拡張容量（例えば全ての受信機の平均）と比較した容量に対応する。さらに別の実施形態では、この関数は、現時点における各受信機の、その受信機へのスループットと比較した容量に対応する。
【００３３】
[0039]一実施形態では、送信デバイスは、同報通信／マルチキャスト情報２０１から符号化されたブロックを生成するためのエンコーダ２２０を含む。一実施形態では、エンコーダ２２０は固定速度抹消符号を使用する。一実施形態では、固定速度抹消符号はチャネル状態情報及びスケジュール履歴を使って符号化されたブロックを生成する。一実施形態では、エンコーダ２２０はレートレス符号を使用する。いずれのケースも、送信機２０３は、マルチキャストシステム中の全ての受信機のうち受信機部分集合に、符号化されたブロックを送信する。一実施形態では、レートレス符号はチャネル状態情報及びスケジュール履歴を使って符号化されたブロックを生成する。一実施形態では、エンコーダ２２０はまたバッファリング機能を実行して、十分な同報通信／マルチキャストブロックを抹消符号エンコーダに蓄積する。エンコーダ２２０は、一般的に、別のノードにおいてまだ同報通信／マルチキャスト情報が符号化されていない場合に使用される。一実施形態では、システムは、図２の全てのブロックを１つのノードにおいて実装する。別の実施形態では、ブロック及び機能が多くのノード間に配布される。この場合、スケジューラが符号化された情報を送信することを保証するために、適切な制御シグナリングメカニズムが使用される。一実施形態では、マルチキャスト／同報通信情報が常駐している起点ノードはエンコーダ２２０の符号化機能を実行し、送信デバイス自体は符号化オペレーションを何も行わない。一実施形態では、起点ノードは、どの送信デバイスがエンコーダ２２０を通じて情報を渡すかに応じて、同報通信／マルチキャスト情報がすでに符号化されたかどうかをその送信デバイスに知らせる。別の実施形態では、無線送信デバイスはエンコーダ２２０を完全に使用不能にし、起点又は何らかのその他のノードがすでに抹消符号化された（例えばＦＥＣ保護された）同報通信／マルチキャストメッセージを送ったことを確信する。
【００３４】
部分集合及び送信速度の選択
[0040]受信機（ノード）の部分集合の選択を公式化し送信速度を選択するために、チャネルをモデル化する。このモデルを正式に述べるために、無線ユーザｉについて時間ｔの受信信号ｙｉ（ｔ）を次のように書き表すことができる。
ｙｉ（ｔ）＝ｈｉ（ｔ）・ｓ（ｔ）＋ｎｉ（ｔ）
ここでは、ｓ（ｔ）は、平均電力制限Ｅ［‖ｓ（ｔ）‖２］≦Ｐで送信機によって送られたマルチキャストメッセージを表す。ユーザｉのチャネルフェーディング係数ｈｉは、一般に、回転対称な複素ガウスランダム変数としてモデル化されるが、ここでは、そのような前提を必要とはしない。同様に、加算性ノイズｎｉは、一般に、ゼロ平均及び単位分散を有する回転対称な複素ホワイトガウスノイズとしてモデル化される。１タイムスロットの間、チャネルフェーディング係数ｈｉは同じままであり、それは受信機と送信機の両方において知られるものとする。ｈｉは、ｉ．ｉ．ｄ．で、又は相関関係で、スロットごとに変化し得る。二人の異なるユーザｉ及びｊについて、ｈｉ及びｈｊは一般的に独立したプロセスとしてみなされる。一方、加算性ノイズｎｉは常にユーザ間でｉ．ｉ．ｄ．であるものとする。
【００３５】
[0041]このモデルを使って、スロットｋにおける１チャネル当たりの容量を次のように表現することができる。
Ｃｉ［ｋ］＝Ｂ１ｌｏｇ２（１＋Ｂ２・ＳＮＲｉ［ｋ］）
この場合、ＳＮＲｉ［ｋ］＝‖ｈｉ［ｋ］‖２Ｐであり、それは、ｋ番目のタイムスロットの間のユーザｉについての平均信号対雑音比を表す。ここで、Ｂ１及びＢ２は、チャネル帯域、干渉、受信機の不備などを表す係数である。送信機が速度Ｒ［ｋ］＞Ｃｉ［ｋ］で送信する場合にはいつでも、ノードｉは、スロットｋの間に、送信された情報のどれも再生できないことに注意されたい。対照的に、送信機がその速度をＲ［ｋ］≦Ｃｉ［ｋ］の任意の値に設定した場合には、ノードｉは、スロットｋの間に送られた情報の全てを再生することができる。
【００３６】
[0042]一実施形態では、送信機はマルチキャスト送信のための速度適合化を次のように行う。各タイムスロットの始めに、送信機はその送信速度Ｒ［ｋ］を設定し、そのタイムスロットの間、同じ速度で送信を続ける。したがって、ｎ番目のタイムスロットの終わりまでのユーザｉのスループット容量を、次のように表現することができる。
【数３】
2010523011.tif 000005
ここでは、Ｉｉ［ｊ］は、ユーザｉがｊ番目のスロットで無事に受信した場合には１に等しく、そうでなければゼロである、指標関数である。
【００３７】
[0043]一実施形態では、ＩＩＤの場合については、ユーザ間でチャネル条件がｉ．ｉ．ｄ．であるとき、送信機は、各スロットでベストＬ人のユーザに役立つよう送信速度を選択するよう抑制されている。Ｌは１からＮまでの任意の値であってよいが、その値は、いったん固定されると、システム中のユーザの数が変わるか、チャネル統計が変わるか、あるいはマルチキャストセッションが終わるまで同じままである。これを実装するために、次のスロット（ｎ＋１）の始めに、ユーザの容量がＣ（１）≧Ｃ（２）≧・・・≧Ｃ（Ｎ）などの順に並べられる。ここで、本発明を不明瞭なものにすることを避けるために、スロットのインデックスは省略した。送信機は、次のタイムスロットのチャネル速度を、ベストＬ人のユーザのグループ内の最悪のユーザの速度Ｒ［ｎ＋１］＝Ｃ（Ｌ）として設定する。Ｒ［ｎ］がｉ．ｉ．ｄ．のランダムプロセスになることに注意されたい。さらに、Ｉｉ［ｎ］もまたｉ．ｉ．ｄ．のランダムプロセスになり、これはＲ［ｎ］とは無関係なものでもある。これは、ｉ．ｉ．ｄ．のチャネル統計が与えられると、どの受信機も、ベストＬ人のユーザに入る可能性が等しくあるという事実によるものである。したがって、確率ｐ＝Ｌ／ＮでＩｉ［ｎ］＝１であり、確率（１−ｐ）＝（１−Ｌ／Ｎ）でＩｉ［ｎ］＝０である。
【００３８】
[0044]このような場合、送信機は、次の等式を使って、長期的スループット容量を最適化するＬ＊を選択する。
【数４】
2010523011.tif 000006
【００３９】
[0045]一実施形態では、送信機のコントローラは、次のタイムスロットについて、各ユーザの達成可能速度を降順にソートする。コントローラは、システム中のベストからＬ番目の達成可能速度ＣＬをターゲットにして、送信速度Ｒ＝ＣＬを設定する。この速度適合化は、全タイムスロットにわたるスケジューリングの決定を暗黙的に行うものであり、Ｃ≧Ｒの達成可能な容量を有するユーザは誰でも、次のタイムスロットで送信されるブロックを無事に再生する。そうでない場合、ユーザは、供給停止状態になり、そのタイムスロットにおいて損失／抹消を観測することになる。また、一実施形態では、コントローラは、最低限のユーザスループットを長期的に最大限にするような最適なＬ＊を見つける。これは、上記の式を計算で解くことによって、あるいは、異なるチャネル統計についてシステムをシミュレートし、Ｌ＊を選ぶための最適なプロファイルを作成することによって行うことができる。ｉ．ｉ．ｄ．の場合には、全てのユーザが、同一の長期的なスループット容量を観測する。
【００４０】
[0046]非ｉ．ｉ．ｄ．の場合については、ユーザ間でチャネル条件が独立して、しかし完全に同じようにではなく変化するときには、公平さが考慮される。この状況は、一般的に、ユーザが地理的に散在していることから生じる。基地局により近いユーザは一般的に信号の減衰が少なく、したがって、遠く離れているユーザよりも高い平均信号電力が得られる。一実施形態では、M. Sharif and B. Hassibi著の「A Delay Analysis for Opportunistic Transmission in Fading BroadcastChannels」（Proceedingsof Infocom '05, Miami, FL, 2005）に記載されているプロポーショナルフェアシェアリング（Proportional-Fair Sharing）を使用することができる。ＰＦＳでは、送信機は、次のスロットにおける各ユーザの達成可能容量をそのユーザの平均容量によって正規化する。したがって各ユーザは、他のユーザではなく自分自身の平均と競うことになる。一実施形態では、ＰＦＳメトリクスの修正版が使用される。以下にこれについて要約する。
【００４１】
[0047]非ｉ．ｉ．ｄ．の場合については、次のスロット（ｎ＋１）におけるマルチキャストチャネルの速度を設定するために、コントローラは、まず、各受信機ｉについて
【数５】
2010523011.tif 000007
を計算する。式中、Γｉは正規化係数である。Γｉは、一般的に、ユーザｉの過去のスケジューリング履歴及びチャネル品質の関数である。それをΓｉ＝Ｅ［Ｃｉ］、すなわち、ユーザｉが観測する平均チャネル品質として設定することができる。また、それをΓｉ＝Ψｉ［ｎ］、すなわち、ユーザｉが観測する平均スループットとして設定することもできる。別の一般的な方法として
【数６】
2010523011.tif 000008
がある。この場合、ｗ［ｊ］は、一般的に
【数７】
2010523011.tif 000009
である重み付け係数である。元のＰＦＳアルゴリズムは、例えばｗ［ｎ］＝α及びｗ［ｊ］＝α（１−α）（ｎ−ｊ）を設定する。この場合、０＜α＜１、１＜ｊ＜（ｎ−１）である。次いで、コントローラは正規化された容量を
【数８】
2010523011.tif 000010
としてソートする。コントローラは、ソートリスト中の高い方からＬ個の値を選択し、ｍ＝１，・・・，Ｌについて
【数９】
2010523011.tif 000011
が満たされるよう集合｛１，・・・，Ｎ｝中の一意のｊを見つけることによって、受信機インデックス集合ＪＬ［ｎ＋１］＝｛ｊ１，・・・ｊＬ｝を構築する。したがって、タイムスロット（ｎ＋１）におけるマルチキャストチャネル速度は次のように計算される。
【数１０】
2010523011.tif 000012
【００４２】
[0048]常にＲ［ｎ＋１］＜Ｃ（Ｌ）であり、一般的にＲ［ｎ＋１］＜Ｃ（Ｌ）であることに注意されたい。言い換えれば、一般的に、所与のタイムスロットにおいてＬ人以上のユーザがスケジュールされるということである。
【００４３】
[0049]したがって、非ｉ．ｉ．ｄ．の場合、一実施形態では、以下に従ってベストのＬ＊が見つけられる。
【数１１】
2010523011.tif 000013
【００４４】
[0050]チャネル統計が推測的にわかる場合、Ｌ＊を計算で求めることができる。チャネル統計がわからない場合は、まずシステムをシミュレートし、Ｌ＊を動的な方法でオンラインで決定することができる。
【００４５】
性能曲線
[0051]図３は、平均ＳＮＲが１０ｄＢでユーザが１００人のシステムにおけるＩＩＤレイリーチャネルの場合に対応する性能曲線の例である。図３に示すように、ユーザは、長期的に同じ平均チャネル統計を見る。図３から、チャネルに十分な変動があるならば、ベストケース及びワーストケースのユーザについて役立つことは次善であると容易に結論付けることができよう。実際に、所与のチャネル条件のもとでは、常にユーザの上位６３％に対して役立つべきである（すなわち、最も最近の測定値から６３番目に高いＳＮＲ値を選択し、それに応じて送信速度を設定する）。明らかに、ユーザのチャネル条件が変化するのにつれて、ユーザの上位６３％も時間とともに変わる。図４は、Ｔ個の全スロットについて、新しい測定値に基づいてそのモデルが修正されるまで（それまでに）識別されたチャネルモデルが用いられたことで、チャネルモデルが更新されＬが最適化される（例えば図４ではＬ＝３）状況を描いたものである。時間とともにＬ自体が変化し得るケースも考えることができる。これは、（平均）チャネル統計が情報の同報通信を介して変化したり、あるいはタイムスロットからタイムスロットに移るときにある特定の状況で変化したりする場合にあり得る。その他のシナリオにおいては、Ｌが固定される場合がある。
【００４６】
抹消符号の使用法
[0052]各受信機が同報通信情報全体を再生することが望ましいことに注意されたい。スケジューラが、所与のタイムスロットｋでＬ台の最強の受信機を臨機応変にターゲットとし、例えば、情報Ｘを対応する速度Ｒｋ（Ｌ，Ｍ）で送信した場合、残りの（Ｍ−Ｌ）台の受信機はそれを復号化することができない。従来のスケジューラであれば、これらの（Ｍ−Ｌ）台の受信機のうちのいずれかが、チャネル条件がよくなり最終的にスケジュールできるようになったときに、その後の送信機会においてＸを再送信するであろう。しかし、これは、臨機応変型マルチキャストによって達成されるスループットゲインを著しく減じる可能性がある。一実施形態では、抹消符号を使ってこの問題に対処する。
【００４７】
[0053]上記のように、マルチキャストスケジューリングにおける１つのコンポーネントは、全てのマルチキャストユーザが、通常のオペレーションのもとで、マルチキャストコンテンツのあらゆるそれぞれのブロックを確実に受信するようにするものである。無線マルチキャストシステムの一実施形態では、スケジューラはシステム内のＮ人のユーザの適切な部分集合のために機能することを決定する。このスケジューリング決定の結果、Ｋ人のユーザが現在のタイムスロットで送信されたブロックを無事に再生することができる。残りの（Ｎ−Ｋ）人のユーザの観点からすれば、ブロックの抹消が爆発的に生じ、この場合、この爆発の長さはスロットの長さと同じである。一実施形態では、ここで説明している臨機応変型マルチキャスト技術が人工的な抹消チャネルを作成する。すなわち、本発明の一実施形態では、送信機は、その他の情報ブロックとともに、Ｘの関数である元の情報とは別個の符号化されたものを送る。これは、符号化されていない元の同報通信情報のみがスケジュールされて送られる従来のアプローチとは対照的な点である。符号化された情報を使うことによって、あらゆる新たな送信が各受信機にとって新しい情報を含むことを、高い確率で確実にすることができる。このように、受信された各パケットが、元のコンテンツから新しい情報セグメントを再生するための助けとなる。
【００４８】
[0054]したがって、元のメッセージブロックを送る代わりに、固定速度又はレートレス抹消符号を通してメッセージブロックが渡され、代わりに、抹消符号による符号化ブロックの出力がスケジュールされる。一実施形態では、スケジューリング層全体にわたって、固定速度及び／又はレートレス抹消符号が使用される。一実施形態では、ｎ番目の時間間隔の間、Ｃ＜Ｒ（ｎ）のユーザは受信できない（すなわち、これらのユーザはスケジュールされていない）。所定のユーザがスケジュールされていない間隔は、ブロック抹消として扱われる（すなわち、スケジューリング層が「制御可能な」仮想抹消チャネルのように動作する）。実装戦略及びターゲットの復号化遅延に応じて、既存の抹消符号化技術を使用することができる。ここでは、このようなスキームのうち２つ、すなわち、固定速度抹消符号（例えばリードソロモン符号などの最大距離分離可能（ＭＤＳ）符号）、及びレートレス符号（例えばラプタ符号）を説明する。
【００４９】
[0055]固定速度抹消符号は、無線チャネル及びスケジューリング決定の注意深い評価を必要とする。これらの条件のいずれかが変化した場合、それらは、悲観的な観点から設計されていない限り、その変化に容易に適応することはできない。したがって、オペレーションの最適点にはしっかりした制御が必要であり、少数のブロックに対して抹消符号化がパケットスケジューラの次又は上の基地局で適用されるならば、それがベストである。
【００５０】
[0056]一方、レートレス符号はきわめて柔軟性があり、スループットの変動に対して盲目的に適応することができる。異なる受信機が異なる短期的又は長期的スループットを観測するならば、各受信機はそれ自身のスループットを達成し、他のユーザにとってのボトルネックをつくることはない。それらは、コンテンツ全体が利用可能なリモートサーバ側のアプリケーション層において適用することができる。あるいは、サーバがアプリケーション層ＦＥＣをサポートしていない場合には、十分なバッファリングの後、基地局でそれを適用することができる。速度制限を強化することによって、レートレス符号を非効率的な固定速度符号として使用することもできる。
【００５１】
コントローラの例
[0057]図５は、臨機応変型マルチキャスティングのための送信機を固定速度又はレートレス抹消符号を使って制御するためのコントローラの一実施形態のデータフロー図である。処理ブロックのそれぞれは、ハードウェア（回路、専用ロジックなど）、ソフトウェア（汎用コンピュータシステム又は専用マシン上で走るものなど）、又はその両方の組み合わせを含むことができる処理を含むことができる。これらの処理ブロックは、１つのデバイスに物理的に配置することができ、あるいは、２つ以上のデバイスに物理的に配布することができる。
【００５２】
[0058]図５を見ると、フィードバックメカニズムは受信機からチャネル状態情報（ＣＳＩ）（例えば、ＳＮＲ又はＳＩＮＲ測定値や、達成可能チャネル速度など）を収集し、それを送信機に送り返す（処理ブロック５０１）。ＣＳＩは処理ブロック５０２でソートされ、処理ブロック５０５でスケジュール履歴の一部として記憶される。一実施形態では、スケジューラ履歴は、少なくとも、それまでに（すなわち、最後のＴ秒間、時期、など）どの受信機がスケジュールされたかについての情報と、各受信機の平均スループット（ウィンドウ表示の／フィルタ処理したスループットであり得る）が何だったかについての情報とを含む。一実施形態では、コントローラは、システム中の受信機の数、それらの移動性、ロケーションなどに依存するネットワーク構成の現在のスナップショットについてチャネルモデルの構築及び更新を行うために、ＣＳＩ測定値の履歴を記憶する（処理ブロック５０４）。一実施形態では、コントローラは各ユーザの達成可能チャネル速度の統計を記憶する。これは少なくとも２つの方法で行うことができる。１つの方法では、送信機は、干渉及びノイズに対する受信信号の比という観点からＣＳＩ情報及び履歴を得て、各受信機の達成可能チャネル速度を決定する。もう１つの方法では、送信機は、受信機において達成可能な速度という観点から、受信機から直接フィードバックを受信する。
【００５３】
[0059]モデル、及び現在のチャネル状態情報を降順に並べたソート配列を与えられると、コントローラは最適な受信機数Ｌ（５０３）を決定し、その最適な受信機数Ｌに基づいて、送信速度を設定するためのターゲットＣＳＩを選択する（処理ブロック５２０）。チャネルモデルは時間とともに著しく変化するため、一般に、最適なＬの値も時間とともに変化する。一実施形態では、この最適な「Ｌ」も評価の信頼性又は過去の情報の正確さを考慮し、この場合、ターゲットとされる受信機数も、それ自体が評価又は何らかの確率的な目標になる。
【００５４】
[0060]一実施形態では、全ての受信機からＣＳＩのソート配列中のターゲットＣＳＩを選択することによって、どの受信機部分集合を次の一連の送信において受信すべきターゲットとするかを決定する。これらの受信機がそれらのチャネル状態において高い変動を経験することはないと想定して、次の一連の送信のターゲットとするユーザ部分集合は、送信を受けるよう暗黙的にスケジュールされる。
【００５５】
[0061]別の実施形態では、コントローラは、現在のＣＳＩ自体ではなく、現在のＣＳＩ及び過去のＳＣＩ履歴の汎関数を使って、受信機をソートし、ターゲットとする受信機部分集合を決定する。例えば、一実施形態では、各ユーザの最も最近のＳＮＲ測定値を、それまでに観測されたそのユーザの平均ＳＮＲについて正規化し、次いで、送信機が正規化されたＳＮＲを使って受信機をソートする。別の実施形態では、現在のＣＳＩ及び過去のＳＣＩ履歴が、現在のタイムスロット及び過去のタイムスロットの達成可能送信速度にマップされる。別のケースでは、一実施形態において、ユーザの現在の達成可能速度（又は、正規化された速度）についてユーザを直接ソートする。この場合、速度は一般にチャネル状態情報の非自明な関数である。そして、送信速度の順番付けを使ってターゲットとする受信機部分集合を決定する。同様に、別の実施形態では、いったん現在の達成可能速度及び速度履歴が計算されると、各ユーザのピーク送信速度に近いという観点からユーザの測定がなされ、次いで、それに応じてコントローラがユーザに優先順位を付ける。一実施形態では、この測定は、ユーザの現在のチャネル速度をその平均チャネル速度について正規化することによってなされる。別の実施形態では、ユーザの現在のチャネル速度がその平均スループットについて正規化される。平均スループットは、長時間にわたる、重み付けされた平均値として計算することができる。この場合、より最近のタイムスロットの間に達成されたスループットの値には、平均値の計算においてより高い重みが付けられる。この例を、ＣＳＩのその他の関数及び達成可能速度に拡張することができる。ユーザ１人当たりのスケジューリング間の時間、送信機及び受信機におけるユーザ１人当たりのバッファバックログを明示的に使って、現在のチャネル品質のトップにいるユーザをソートすることもできる。
【００５６】
[0062]一実施形態では、コントローラは長時間にわたってこれらの部分集合を追跡し続け、それまでにすでに送信済みの情報を使ってスケジュール履歴５０５が形成される。別の実施形態では、コントローラは、スケジュール履歴５０５を修正するためにどの情報を受信するか受け取らないかについて、受信機から直接フィードバックを受信する。
【００５７】
[0063]一実施形態では、最適なＬを選択するための決定において、過去のスケジュール（例えば、過去のＬの値とＣＳＩ履歴とを一緒に）を使うことができる。この情報はスケジュール履歴５０５によって提供される。
【００５８】
[0064]一実施形態では、固定速度又はレートレス抹消符号を通じて元のコンテンツ（５１０）が渡されて、抹消又はレートレスエンコーダ（５１１）を使って符号化ブロック５１２（例えば、ビット、記号、パケットなど）を生成する。この場合、ＣＳＩ履歴を使って抹消符号の速度を選択することができる。次いで、符号化ブロック（５１２）は、次のチャネル（５３０）を介して、無線トランシーバのためにターゲットにされたＣＳＩ（すなわち受信機部分集合）によってすでに決定された送信速度で、送信機の物理層に渡される。別の実施形態では、符号化ブロック５０２が、無事に再生された符号化ブロックのそれぞれが任意の受信機に新しい情報を運ぶ、レートレスコードによって生成される。ここで、その新しい情報は、それが冗長ではない（すなわち、それまでに受信した情報ビットからは再生できない）という意味できわめて新しい、いずれかの受信情報である。
【００５９】
[0065]一実施形態では、スケジュール履歴５０５が、元のコンテンツ５１０及びＣＳＩ履歴５０４とともに、抹消符号／レートレス符号エンコーダ５１１への入力として使用される。より具体的には、各受信機によってまだ再生されていないマルチキャストコンテンツの符号化されていないブロックを記憶しておくために、各受信機のための待ち行列を維持することができる（スケジューリング履歴及び過去に符号化されたものから、どのブロックがまだ再生されていないかがすぐわかり、あるいは、受信機がこの情報を明示的にフィードバックすることができる）。次いで、エンコーダは、現在スケジュールされている受信機のこれらの待ち行列のうちで、符号化されたもののどれが最も多くの情報を送達できるかをたずねる。例えば、最初のタイムスロットで送信機がｘ（符号化されていない情報）をスケジュールし受信機Ａ、Ｂがそれを再生したが、受信機Ｃは再生しなかったとする。２番目のスロットで、受信機Ｂ、Ｃのためにｙ（これも符号化されていない）をスケジュールしたと仮定する。現在のスロットで受信機Ａ、Ｃがスケジュールされているならば、符号化されたものｘ＋ｙは、受信機Ａがｙを再生し受信機Ｃがｘを再生することを保証する。このように、現在のスロットにおいてどの受信機がスケジュールされているかとともに、現在のスロットにおけるスケジューリング履歴が使用される。
【００６０】
[0066]他の実施形態では、スケジュール履歴５０５は使用されない。この場合、レートレス符号を使用することにより、スケジュール履歴５０５とは関係なく、高確率できわめて新しい情報が送られる。
【００６１】
[0067]様々な実施形態では、各チャネルが、タイムスロット、周波数サブバンド、拡散符号、又は、これらのチャネライゼーション技術の１つ又は複数の組み合わせに対応し得る。所与の受信機、又は多くの受信機のチャネル品質の変動は、時間の領域、周波数の領域（例えば、ＯＦＤＭサブバンド）、符号の領域（例えば、ＣＤＭＡ拡散符号）、又はこれらの領域のいずれかの部分集合において生じ得る。
【００６２】
[0068]本発明の１つ又は複数の実施形態に関連する多くの利点がある。例えば、本発明の実施形態は、臨機応変型マルチキャスティングと符号化を結びつけることによって、１台の送信機から多くの受信機に情報を同報通信するために、ユーザ及びシステムスループットを支援する。従来のシステムは、一般に、最悪のケースのユーザをターゲットにして送信速度を適合化する。臨機応変型マルチキャスティング機能は、その代わりに、より小さいユーザ部分集合に焦点を合わせて、はるかに高速の瞬間送信速度を達成できるようにする。文献に記載の、臨機応変型マルチキャスティングのための提案解決策は、これまでにどの受信機が特定のパケットをまだ受け取っていないかを暗黙的又は明示的に追跡することで、パケットスケジューリングの問題を別個に解決し、その後の送信機会においてそのパケットを再送信するので、資源を無駄使いすることになる。それらの解決策はまた、中間ユーザに焦点を合わせることによって、臨機応変型マルチキャスティングの１つのケースにのみ焦点を当てている。一方、本発明の一実施形態は、パケットを符号化しスケジューリングオペレーションを単純化する追加のメカニズムを使用している。
【００６３】
[0069]さらに、本発明の一実施形態は、さらに速度適合化のための最適なターゲットＣＳＩを計算することによって、臨機応変型マルチキャスティングの性能を最適化する。また、符号化段階で、固定速度抹消符号ではなくレートレス符号を使用することによって、スループットが短期的により高い受信機がその利点を利用できるようになる。本発明の一実施形態はまた、文献に記載の臨機応変型マルチキャスティングのための従来のスケジューラの指数時間とは反対に、スケジューリングという点に関して複雑さがはるかに少ない（抹消／レートレス符号エンコーダによる多項式時間）。
【００６４】
コンピュータシステムの例
[0070]図６は、本明細書に記載のオペレーションの１つ又は複数を実行することができる、例示的コンピュータシステムのブロック図である。図６を見ると、コンピュータシステム６００は、例示的クライアント又はサーバコンピュータシステムを含むことができる。コンピュータシステム６００は、情報を伝達するための通信メカニズム又はバス６１１、及びバス６１１に接続された、情報を処理するためのプロセッサ６１２を含む。プロセッサ６１２はマイクロプロセッサを含むが、例えば、ペンティアム（商標）、ＰｏｗｅｒＰＣ（商標）、Ａｌｐｈａ（商標）などのマイクロプロセッサに限定されるものではない。
【００６５】
[0071]システム６００はさらに、ランダムアクセスメモリ（ＲＡＭ）、又はバス６１１に接続された、情報及びプロセッサ６１２が実行する命令を記憶するためのその他の動的記憶デバイス６０４（メインメモリと呼ぶ）を含む。メインメモリ６０４はまた、プロセッサ６１２による命令の実行の間に一時的変数又はその他の中間情報を記憶するために使用することができる。
【００６６】
[0072]コンピュータシステム６００はまた、バス６１１に接続された、静的情報及びプロセッサ６１２のための命令を記憶するための読み取り専用メモリ（ＲＯＭ）及び／又はその他の静的記憶デバイス６０６、及び、磁気ディスクや光ディスク及びそれに対応するディスクドライブなどのデータ記憶デバイス６０７も含む。データ記憶デバイス６０７は、情報及び命令を記憶するためにバス６１１に接続されている。
【００６７】
[0073]コンピュータシステム６００はさらに、コンピュータユーザに情報を表示するためにバス６１１に接続された、陰極線管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）などのディスプレイデバイス６２１に接続することもできる。英数字及びその他のキーを含む英数字入力デバイス６２２も、情報及びコマンドの選択をプロセッサ６１２に伝達するためにバス６１１に接続することができる。さらなるユーザ入力デバイスは、マウス、トラックボール、トラックパッド、タッチペン、又はカーソル方向キーなどのカーソル制御装置６２３であり、これは、方向情報及びコマンドの選択をプロセッサ６１２に伝達するために、また、ディスプレイ６２１上のカーソルの動きを制御するためにバス６１１に接続されている。
【００６８】
[0074]バス６１１に接続することができる別のデバイスとしてハードコピーデバイス６２４がある。これは、紙、フィルム、又は同様のタイプの媒体など、媒体の上に情報を示すために使用することができる。バス６１１に接続することができる別のデバイスとして、電話やハンドヘルドパームデバイスと通信するための有線／無線通信機能６２５がある。
【００６９】
[0075]システム６００のいずれか又は全てのコンポーネント、及び関連するハードウェアを本発明において使用できることに注意されたい。しかし、コンピュータシステムのその他の構成は、それらのデバイスのいくつか又は全てを含むことができることを理解されたい。
【００７０】
[0076]当業者には、前述の説明を読めば、本発明の多くの変更及び修正が疑いもなく明らかになろう。しかし、例示によって示し、説明したいずれの特定の実施形態も、制限するものとしてみなされることを意図したものでは決してない。したがって、様々な実施形態の詳細についての言及は、特許請求の範囲を限定することを意図したものではない。特許請求の範囲自体には、本発明に必須とみなされる特徴のみを列挙してある。
【図面の簡単な説明】
【００７１】
【図１】無線マルチキャストシステムの一実施形態のブロック図である。
【図２】送信デバイスの一実施形態のブロック図である。
【図３】１０ｄＢの平均ＳＮＲのスロットにわたる、独立同一分布に従う（ｉｎｄｅｐｅｎｄｅｎｔ  ａｎｄ  ｉｄｅｎｔｉｃａｌｌｙ  ｄｉｓｔｒｉｂｕｔｅｄ）（ＩＩＤ）レイリーチャネルを示す図である。
【図４】Ｔ個の全スロットそれぞれの間に、Ｌについてチャネルモデルが更新され最適化される状況を示す図である。
【図５】送信機の一実施形態のデータフロー図である。
【図６】例示的コンピュータシステムのブロック図である。
【図１】
2010523011.tif 000014
【図２】
2010523011.tif 000015
【図３】
2010523011.tif 000016
【図４】
2010523011.tif 000017
【図５】
2010523011.tif 000018
【図６】
2010523011.tif 000019
【手続補正書】
【提出日】平成21年6月23日(2009.6.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の受信機を有する無線マルチキャストシステムにおいて使用するための装置であって、
前記複数の受信機から受信したチャネル状態及び速度情報のうち少なくとも１つを記憶するためのストレージと、
送信タイムスロット毎に前記複数の受信機のうちのいくつかの受信機に同報通信チャネルを介して情報を同報通信するための送信機と、
前記送信機に異なる送信タイムスロットごとに異なる速度で送信させるように前記送信機の送信速度を適合させる、前記ストレージ及び前記送信機に接続されたコントローラであって、前記情報を同報通信する前記送信機の送信速度を、前記同報通信チャネルに関連付けられ前記複数の受信機から受信したチャネル状態情報と、前記複数の受信機のうち、前記各送信タイムスロットの間に前記同報通信チャネルを介して同報通信送信を確実に受信するターゲットにされた受信機の部分集合とに基づいて決定するコントローラと、
を備える装置。
【請求項２】
前記コントローラが、前記送信機の送信速度を、前記コントローラによって選択された前記受信機部分集合のうちの最悪のチャネル条件を満足するように前記送信機の送信速度を設定することによって適合させる、請求項１に記載の装置。
【請求項３】
前記コントローラが、固定速度抹消符号及びレートレス符号からなる群のうちの一つを使って、前記同報通信情報から符号化されたブロックを生成するエンコーダを備え、
前記送信機が前記符号化されたブロックを送信する、
請求項２に記載の装置。
【請求項４】
前記コントローラが、
前記複数の受信機を個々のチャネル状態情報に基づいてソートしてソートリストを作成し、
最適な順序情報に基づいて前記ソートリスト中の値を決定し、
過去のチャネル状態情報履歴、及び前記複数の受信機のうちの全ての受信機に関連付けられた送信スケジュールのうち少なくとも１つが与えられると、前記ソートリスト中の前記値以上の達成可能送信速度を有する全ての受信機を含むように前記受信機部分集合を決定する
ことによって前記受信機部分集合を識別する、請求項１に記載の装置。
【請求項５】
前記コントローラが、各受信機の前記チャネル状態情報に基づいて関数を計算し、前記複数の受信機のうちの受信機を前記関数の計算結果についてソートする、請求項４に記載の装置。
【請求項６】
前記関数は、チャネル状態情報、及び過去の前記複数の受信機のうちのいくつかの受信機への送信のスケジューリングに関連する情報に基づくものである、請求項５に記載の装置。
【請求項７】
前記過去のスケジューリングに関連する情報が、前記受信機それぞれへの平均スループットを含む、請求項６に記載の装置。
【請求項８】
前記関数が、現時点における前記複数の受信機の各受信機の容量に対応する、請求項６に記載の装置。
【請求項９】
前記関数が、拡張容量と比較した、現時点における各受信機の容量に対応する、請求項６に記載の装置。
【請求項１０】
前記関数が、前記受信機のスループットと比較した、現時点における各受信機の容量に対応する、請求項６に記載の装置。
【請求項１１】
前記コントローラが、
前記複数の受信機の各受信機の達成可能速度を次のタイムスロットのための順番でソートしてリストにし、
前記リスト中の１台の受信機の１つの達成可能速度に等しい送信速度であって、前記１つの達成可能速度が、前記リスト中の、所定数の受信機に関連付けられた最高の達成可能速度を含むグループ内において最低の達成可能速度である送信速度を設定する
ことで前記受信機部分集合を選択し、
前記設定された送信速度以上の信頼できる送信速度を有する受信機への次のタイムスロットでのデータの送信をスケジュールすることをさらに含む、
請求項１に記載の装置。
【請求項１２】
前記コントローラが、１タイムスロットの間に少なくとも１回のマルチキャスト送信が行われるようにすることを含む、マルチキャスト送信のための速度適合化を行い、且つ前記送信機の送信速度を設定することによって、前記送信機の送信速度を適合させ、
該送信速度は、前記タイムスロットにおいてベストＬ人のユーザに役立つ送信速度であり、
前記送信機が、前記タイムスロットの間ずっと前記送信速度で送信する、
請求項１に記載の装置。
【請求項１３】
前記コントローラが、
各受信機について１チャネル当たりの容量を計算し、
前記受信機グループについて１チャネル当たりの容量を正規化したものをソートし、
前記ソートされた受信機グループから、前記ソーティングに基づいて所定数の受信機を選択し、
前記送信速度は、前記所定数の受信機のうちの受信機の送信速度のうち最低の送信速度にしたがって設定される、
請求項１２に記載の装置。
【請求項１４】
固定速度抹消符号を使って、前記同報通信情報から符号化されたブロックを生成するエンコーダをさらに備え、
前記送信機が前記符号化されたブロックを送信する、
請求項１に記載の装置。
【請求項１５】
前記固定速度抹消符号が、前記チャネル状態情報及び前記スケジュール履歴を使って前記符号化されたブロックを生成する、請求項１４に記載の装置。
【請求項１６】
レートレス符号を使って、前記同報通信情報から符号化されたブロックを生成するエンコーダをさらに備え、
前記送信機が前記符号化されたブロックを送信する、
請求項１に記載の装置。
【請求項１７】
前記レートレス符号が、前記チャネル状態情報及び前記スケジュール履歴を使って前記符号化されたブロックを生成する、請求項１６に記載の装置。
【請求項１８】
同報通信チャネルを介して同報通信情報を送る送信機と、
前記同報通信チャネルを介して送信を受信する複数のノードと、
前記送信機に、前記受信機から受け取ったチャネル状態と、存在する、ターゲットにする信頼性とに応じて異なる速度で送信させるように、速度適合化を実施するコントローラと、を備える無線マルチキャストシステム。
【請求項１９】
前記コントローラが、前記ターゲット部分集合の受信機の間で最悪のチャネル条件を満足するように送信速度が設定される送信機会ごとに、受信機部分集合をターゲットにすることによって速度適合化を行う、請求項１８に記載のシステム。
【請求項２０】
無線マルチキャストシステムにおける複数の受信機のチャネル状態情報を受信するステップと、
前記送信機に異なる送信タイムスロットごとに異なる速度で送信させるように前記送信機の送信速度を適合させるステップであって、送信タイムスロット毎に前記複数の受信機に同報通信チャネルを介して情報を同報通信する前記送信機の送信速度を、前記同報通信チャネルに関連付けられ前記複数の受信機から受信したチャネル状態情報と、前記複数の受信機のうち、前記各送信タイムスロットの間に前記同報通信チャネルを介して同報通信送信を確実に受信するターゲットにされた受信機部分集合とに基づいて決定するステップを含む、ステップと、
を含む方法。
【請求項２１】
前記送信機の送信速度を適合させるステップが、前記受信機部分集合のうちの最悪のチャネル条件を満足するように前記送信機の送信速度を設定するステップを含む、請求項２０に記載の方法。
【請求項２２】
固定速度抹消符号及びレートレス符号からなる群のうちの一つを使って、前記同報通信情報から符号化されたブロックを生成するステップと、
前記符号化されたブロックを送信するステップと、
をさらに含む請求項２１に記載の方法。
【請求項２３】
前記複数の受信機を個々のチャネル状態情報に基づいてソートしてソートリストを作成し、
最適な順序情報に基づいて前記ソートリスト中の値を決定し、
過去のチャネル状態情報履歴、及び前記複数の受信機のうちの全ての受信機に関連付けられた送信スケジュールのうち少なくとも１つが与えられると、前記ソートリスト中の前記値以上の達成可能送信速度を有する全ての受信機を含むように前記受信機部分集合を決定する
ことによって前記受信機部分集合を識別するステップをさらに含む、請求項２０に記載の方法。
【請求項２４】
前記複数の受信機の各受信機の達成可能速度を次のタイムスロットのための順番でソートしてリストにし、
前記リスト中の１台の受信機の１つの達成可能速度に等しい送信速度であって、前記１つの達成可能速度が、前記リスト中の、所定数の受信機に関連付けられた最高の達成可能速度を含むグループ内において最低の達成可能速度である送信速度を設定する
ことによって前記受信機部分集合を選択するステップをさらに含み、
前記設定された送信速度以上の信頼できる送信速度を有する受信機への次のタイムスロットでのデータの送信をスケジューリングするステップをさらに含む、
請求項２０に記載の方法。
【請求項２５】
前記送信機の送信速度を適合させるステップが、
１タイムスロットの間に少なくとも１回のマルチキャスト送信が行われるようにすることを含む、マルチキャスト送信のための速度適合化を行うステップと、
前記送信機の送信速度を設定するステップであって、前記送信速度は前記タイムスロットにおいてベストＬ人のユーザに役立つ送信速度である、ステップと、
前記タイムスロットの間ずっと前記送信速度で送信するステップと、を含む、
請求項２０に記載の方法。
【請求項２６】
各受信機について１チャネル当たりの容量を計算するステップと、
前記受信機グループについて１チャネル当たりの容量の正規化したものをソートするステップと、
前記ソートされた受信機グループから、該受信機のソーティングに基づいて所定数の受信機を選択するステップであって、前記送信速度は前記所定数の受信機の中の受信機の送信速度のうち最低の送信速度にしたがって設定される、ステップと、
をさらに含む請求項２５に記載の方法。
【請求項２７】
固定速度抹消符号を使って、前記同報通信情報から符号化されたブロックを生成するステップと、
前記符号化されたブロックを送信するステップと、
をさらに含む請求項２０に記載の方法。
【請求項２８】
前記固定速度抹消符号が、前記チャネル状態情報及び前記スケジュール履歴を使って前記符号化されたブロックを生成する、請求項２７に記載の方法。
【請求項２９】
レートレス符号を使って、前記同報通信情報から符号化されたブロックを生成するステップと、
前記符号化されたブロックを送信するステップと、
をさらに含む請求項２０に記載の方法。
【請求項３０】
前記レートレス符号が、前記チャネル状態情報及び前記スケジュール履歴を使って前記符号化されたブロックを生成する、請求項２９に記載の方法。
【国際調査報告】
2010523011.tif 000020
2010523011.tif 000021
2010523011.tif 000022