(57)【要約】【課題】送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法を説明する。【解決手段】一組のリレーノードは、無線リンクによって接続されたノード及び次のノードを含む。次のノードは、メッセージの１つ又は複数の前の伝送からの累積ナットを受信することを保証される。ノードから次のノードへのメッセージの伝送は、次のノードによって受信されることを保証された累積ナットを求めること、ノードから次のノードへ伝送されるメッセージの最小ナットと累積ナットとの合計が送信元エントロピーよりも小さくならないような最小ナットを計算すること、及び最小ナットを有するメッセージをノードから次のノードへの伝送することを含む。【選択図】図１
2010233209.tif 000002
【特許請求の範囲】
【請求項１】
送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法であって、前記メッセージの送信元エントロピーはＸナットであり、前記一組のリレーノードは、ノードｉ及び前記ノードｉに後続するノードｊを含み、前記一組のリレーノードは無線リンクによって接続され、各リンクはチャネル電力利得γｉｊを有し、前記伝送は時間制約Ｔを有し、前記方法は、
前記ノードｉから前記次のノードｊへ伝送される前記メッセージにおけるナット数ｘｉを最小にするステップであって、前記次のノードｊは、前記ナット数ｘｉと１つ又は複数の前の伝送からの累積ナット数ｘａｃとの合計が、送信元エントロピーＸよりも小さくならないような前記累積ナット数ｘａｃを受信することを保証される、最小にするステップと、
前記ノードｉから前記次のノードｊへ前記メッセージを伝送するための一組の資源を割り当てるステップと、
前記一組の資源を使用して前記ノードｉから前記次のノードｊへ前記メッセージを伝送するステップと、
を含む送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項２】
前記一組の資源は、前記ナット数ｘｉを伝送するのに必要とされる伝送時間ｔｉ、前記伝送時間ｔｉ内で前記ナット数ｘｉを伝送するのに必要とされるエネルギーｅｉ、前記伝送時間ｔｉ内で前記ナット数ｘｉを伝送するのに必要とされる伝送電力ｐｉ、及びそれらの組み合わせを含む群から選択される請求項１に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項３】
前記最小にするステップは、
ナット割り当て線形計画法（ＬＰ）
【数１】
2010233209.tif 000028
を構成するステップであって、ｂは、ｂ＝１・Ｘであるようなナット割り当てベクトルであり、Ａは、Ａｉ≧ｊ＝ｒｉｊであるような三角行列であり、ｊは、ｊ＞ｉであるような次のノードのインデックスであり、前記次のノードｊは、チャネル電力利得γｉを有する無線リンクによって前記ノードｉに接続され、ｃｉは、ｃｉ＝１／γｉであるようなコストパラメータベクトルであり、ｒｉｊは、前記ノードｉから前記次のノードへの前記ナット数ｘｉの前記伝送を前記後続のノードｊにおいてオーバーヒアすることを記述する係数であり、ｍｉｎは最小値を返す関数であり、Ｔは転置演算子である、ナット割り当て線形計画法（ＬＰ）を構成するステップと、
前記三角行列Ａがカスケードしている場合には、前記ＬＰを算術的に解くことによって前記ナット数ｘｉを求めるステップと、
そうでない場合には、汎用線形計画法ソルバを使用して前記ＬＰを解くことにより、前記ナット数ｘｉを求めるステップと、
をさらに含む請求項１に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項４】
前記割り当てるステップは、
エネルギー曲線
【数２】
2010233209.tif 000029
を構成するステップと、
前記エネルギー曲線の双曲線上限を求めるステップと、
【数３】
2010233209.tif 000030
を満たす双曲線上限の合計に関する最小点について閉形式で解くことにより、エネルギーｅｉ及び伝送時間ｔｉを求めるステップと、
をさらに含む請求項２に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項５】
前記割り当てるステップは、
前記エネルギーｅｉ及び前記伝送時間ｔｉに基づいて前記双曲線上限をタイト化するステップと、
前記割り当てるステップを繰り返すステップと、
をさらに含む請求項４に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項６】
前記割り当てるステップは、
前記エネルギーｅｉ及び前記伝送時間ｔｉに基づいてｐｉ＝ｅｉ／ｔｉに従い前記伝送電力ｐｉを求めるステップをさらに含む請求項４に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項７】
前記後続のノードｊは、前記宛先ノードである請求項１に記載の送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法。
【請求項８】
送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法であって、前記一組のリレーノードは、無線リンクによって接続されたノード及び次のノードを含み、前記次のノードは、前記メッセージの１つ又は複数の前の伝送からの累積ナットを受信することを保証され、前記ノードから前記次のノードへの前記メッセージの伝送は、
前記次のノードによって受信されることを保証された前記累積ナットを求めるステップと、
前記ノードから前記次のノードへ伝送される前記メッセージの最小ナットと前記累積ナットとの合計が前記送信元エントロピーよりも小さくならないような前記最小ナットを計算するステップと、
前記最小ナットを有する前記メッセージを前記ノードから前記次のノードへ伝送するステップと、
を含む送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項９】
前記メッセージの前記伝送のための一組の資源を割り当てるステップをさらに含む請求項８に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１０】
前記求めるステップ及び前記計算するステップは、
ナット割り当て線形計画法（ＬＰ）を構成するステップと、
前記最小ナットを求めるようにＬＰを解くステップと、
をさらに含む請求項８に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１１】
前記解くステップは、三角行列を使用し、
前記三角行列がカスケードしている場合に、前記ＬＰを算術的に解くステップをさらに含む請求項１０に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１２】
前記解くステップは、三角行列を使用し、
前記三角行列がカスケードしていない場合に、汎用線形計画法ソルバを使用して前記ＬＰを解くステップをさらに含む請求項１０に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１３】
前記一組の資源は、伝送時間、エネルギー、伝送電力、及びそれらの組み合わせを含む群から選択される請求項９に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１４】
前記最小ナット、前記ノードと前記次のノードとの間のチャネルの電力利得、及び前記送信元ノードから前記ノードのリレーを介して前記宛先ノードへの前記伝送の時間制約に基づいて前記エネルギー及び前記伝送時間を求めるステップをさらに含む請求項１３に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１５】
前記エネルギー及び前記伝送時間に基づいて前記伝送電力を求めるステップをさらに含む請求項１４に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１６】
前記伝送は、レートレス消去符号伝送である請求項８に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１７】
前記伝送は、ファウンテン符号化伝送である請求項８に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【請求項１８】
送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送するシステムであって、前記一組のリレーノードは、無線リンクによって接続されたノード及び次のノードを含み、前記次のノードは、前記メッセージの１つ又は複数の前の伝送からの累積ナットを受信することを保証され、前記システムは、
前記次のノードによって受信されることを保証された前記累積ナットを求める手段と、
前記ノードから前記次のノードへ伝送される前記メッセージの最小ナットと前記累積ナットとの合計が前記送信元エントロピーよりも小さくならないような前記最小ナットを計算する手段と、
前記最小ナットを有する前記メッセージを前記ノードから前記次のノードへ伝送する手段と、
を含む送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送するシステム。
【請求項１９】
前記メッセージの前記伝送のための一組の資源を割り当てる手段をさらに含む請求項１８に記載の送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、無線アドホックネットワークに関し、より詳細には、レートレス伝送のための資源割り当てに関する。
【背景技術】
【０００２】
セルラーネットワーク等の従来の無線ネットワークと異なり、アドホックネットワークは、インフラストラクチャを有しない。通常、アドホックネットワークは、複雑度の低い多数の送受信機（ノード）を使用して情報を通信する。これによって、コスト及び単一のリンクの障害に対する感度が低減される。そのため、アドホックネットワークは、極めて信頼性のある通信リンクを必要とする用途の候補とされる。
【０００３】
非常に信頼性のあるアドホック無線ネットワークは、２つの競合する制約を有する。ノードは、通常、バッテリーで動作し、バッテリーを使い果たすことは、障害につながる可能性があるので、エネルギー消費は低くなければならず、また、データの伝送が成功する確率は高くあるべきである。すなわち、メッセージは、所定の遅延制約内で送信元ノードから宛先ノードへ伝送されなければならない。受信の信頼性を増大させるためには、電力を高くすることが必要となる場合があるので、遅延を小さくするには、より多くのエネルギーを必要とする。
【０００４】
アドホックネットワークでは、遅延制約内で宛先へメッセージを渡す一方、エネルギー消費を最小にするルート、すなわちノードのシーケンスを選択することが望まれる。単純な解決法は、各リンクが一定の時間間隔内でのメッセージの伝送を単純に試みるように選択された一定のメッセージサイズ及び一定の符号化レートを有する物理レイヤ伝送を使用する。その場合、遅延制約を満たすことは、ホップ数を制限することと等価である。
【０００５】
しかしながら、この単純な手法は、一定のリンク上でエネルギーを多く使用し、場合によっては他のリンク上でエネルギーの使用量を少なくすることによって、全体の遅延を減少させる可能性を無視している。単一のリンクの場合、伝送時間とエネルギーとの間のトレードオフは直接的である。シャノンの容量方程式によれば、可能なデータレートは、伝送電力と共に対数的に増加する。しかしながら、複数のホップを有するネットワークの場合、トレードオフははるかに複雑になる。トレードオフは、ルートを選択し、次いで、そのルートに沿った各ホップに関してエネルギーレベルを選択することを伴う。
【０００６】
ファウンテン符号
ファウンテン符号（レートレス消去符号（ｒａｔｅｌｅｓｓ  ｅｒａｓｕｒｅ  ｃｏｄｅ）としても知られている）は、ソースシンボル数と等しいサイズ又はソースシンボル数よりも僅かにだけ大きいサイズの符号化シンボルの任意の部分集合から元のソースシンボルを回復できるような所与のソースシンボルの集合から、符号化シンボルの潜在的に無限のシーケンスを生成できるという特性を有する消去符号のクラスである。
【０００７】
ファウンテン符号は、元のｋ個のソースシンボルを任意のｋ個の符号化シンボルから回復できるときに最適である。ファウンテン符号は、高い確率を有する符号化シンボルの任意のｋ’個からの元のｋ個のソースシンボルの回復を可能にする効率的な符号化アルゴリズム及び復号アルゴリズムを有する。ここで、ｋ’は、ｋよりも僅かに大きい。
【０００８】
マルチホップファウンテン符号化伝送の資源割り当ての従来の方法は、反復的であり、各ステップは、高い多項式計算複雑度を有する。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
後続のノードが前のファウンテン符号化伝送のフラグメントを受信していることを考慮して、一定の時間制約内に無線リンクのパスに沿ってメッセージを伝搬するのに必要とされる総エネルギーを最小にすることが望まれている。
【００１０】
本発明の目的は、後続のノードが前のレートレス伝送からのメッセージのフラグメントを累積することを考慮して、一定の時間制約内に無線リンクのパスに沿ってメッセージを伝送するのに必要とされる総エネルギーを最小にする方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明の１つの実施の形態は、送信元ノードから一組のリレーノードを介して宛先ノードへメッセージを伝送する方法であって、メッセージの送信元エントロピーはＸナットであり、一組のリレーノードは、ノードｉ及びノードｉに後続するノードｊを含み、一組のリレーノードは無線リンクによって接続され、各リンクはチャネル電力利得γｉｊを有し、伝送は時間制約Ｔを有し、この方法は、ノードｉから次のノードｊへ伝送されるメッセージにおけるナット数ｘｉを最小にするステップであって、次のノードｊは、ナット数ｘｉと１つ又は複数の前の伝送からの累積ナット数ｘａｃとの合計が、送信元エントロピーＸよりも小さくならないような累積ナット数ｘａｃを受信することを保証される、最小にするステップと、ノードｉから次のノードｊへメッセージを伝送するための一組の資源を割り当てるステップと、一組の資源を使用してノードｉから次のノードｊへメッセージを伝送するステップとを含むものである。
【００１２】
別の実施の形態は、送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送する方法であって、一組のリレーノードは、無線リンクによって接続されたノード及び次のノードを含み、次のノードは、メッセージの１つ又は複数の前の伝送からの累積ナットを受信することを保証され、ノードから次のノードへのメッセージの伝送は、次のノードによって受信されることを保証された累積ナットを求めるステップと、ノードから次のノードへ伝送されるメッセージの最小ナットと累積ナットとの合計が送信元エントロピーよりも小さくならないような最小ナットを計算するステップと、最小ナットを有するメッセージをノードから次のノードへ伝送するステップとを含むものである。
【００１３】
さらに別の実施の形態は、送信元ノードから一組のリレーノードを介して宛先ノードへ送信元エントロピーのメッセージを伝送するシステムであって、一組のリレーノードは、無線リンクによって接続されたノード及び次のノードを含み、次のノードは、メッセージの１つ又は複数の前の伝送からの累積ナットを受信することを保証され、システムは、次のノードによって受信されることを保証された累積ナットを求める手段と、ノードから次のノードへ伝送されるメッセージの最小ナットと累積ナットとの合計が送信元エントロピーよりも小さくならないような最小ナットを計算する手段と、最小ナットを有するメッセージをノードから次のノードへ伝送する手段とを含むものである。
【発明の効果】
【００１４】
この発明によれば、後続のノードが前のレートレス伝送からのメッセージのフラグメントを累積することを考慮して、一定の時間制約内に無線リンクのパスに沿ってメッセージを伝送するのに必要とされる総エネルギーを最小にする方法を実現することができる。
【図面の簡単な説明】
【００１５】
【図１】最適な送信元／宛先ルートが強調された本発明の実施の形態によるリレーネットワークの概略図である。
【図２】本発明の実施の形態によるメッセージのマルチホップファウンテン符号化伝送のための資源割り当て方法のブロック図である。
【図３】本発明の実施の形態によるナット（ｎａｔ）割り当て線形計画法（ＬＰ：ｌｉｎｅａｒ  ｐｒｏｇｒａｍ）の一例である。
【発明を実施するための形態】
【００１６】
図１は、最適な送信元／宛先ルートが強調された本発明の実施の形態によるリレーネットワーク１００を示している。本発明の実施の形態は、ノード１０２のリレーを介して、送信元ノード１０１から宛先ノード１０３へＸナットのサイズを有するメッセージを伝送するためのネットワーク１００を使用する。メッセージ伝送のための時間は制約される。すなわち、送信元ノードからノードのリレーを介した宛先ノードへの伝送は、所定のＴよりも大きくなるべきではない。
【００１７】
リレーノード１０２は、ノードｉ １０６及びノードｊ １０７を含む。ここで、ノードｉはノードｊよりも先行する。ノードｉ １０６とノードｊ １０７との間のチャネル１１０に関する電力利得はγｉｊである。ノードｉ １０６は、送信元ノード１０１でも宛先ノード１０３でもないことに留意されたい。これに対して、ノードｊは、宛先ノード１０３を含めて、ネットワーク１００においてノードｉに後続する任意のノードとすることができる。
【００１８】
本発明の実施の形態は、ネットワーク１００を通じたメッセージのマルチホップファウンテン符号化伝送を使用する。ファウンテン符号化システムは、後続の受信機により受信されるビットを利用することによって、マルチホップ伝送を最適化することができる。例えば、ノードｉ １０６が次のノード１０８へメッセージを伝送するとき、「後続」のノードｊは、チャネル１１０を介してこのメッセージの少なくとも一部を受信する。ノードｊによって受信される部分のサイズは、チャネル１１０の電力利得γｉｊに依存する。
【００１９】
したがって、ノードｊは、すべての前の伝送からの累積ナット数ｘａｃを累積する。例えば、ノードｊ １０７は、ノードｉ １０６からノードｉ＋１ １０８への伝送から受信されたナットだけでなく、送信元ノード１０１からノードｉ １０６への伝送から受信されたナットも累積する。
【００２０】
ファウンテン符号化伝送のエネルギー最小化
本発明の実施の形態は、時間制約を条件として全体のエネルギーを最小にする。エネルギーｅｉ、伝送時間ｔｉ、伝送電力ｐｉ、及び伝送される最小ナットｘｉ→ｊ（ビット＝ナット×ｌｏｇ２）の間の関係は、式（１）に開示される。式（１）において、ｍｉｎ関数は最小値を返す。
【００２１】
【数１】
2010233209.tif 000003
【００２２】
この等式は、（ａ）エネルギー＝時間×電力、（ｂ）ｔ個の時間ユニットでｘナットを伝送するのに必要な電力（シャノン−ハートレーの容量法則による）、及び（ｃ）ナットについて解かれるシャノン−ハートレー法則から得られる。
【００２３】
式（１）の第３行は、ファウンテン符号化の独特の特徴を記述している。すなわち、各ノードｊは、先行ノードｉ＜ｊから伝送されたナットを累積する。明瞭にするために、ｘｉは、ｘｉ→ｉ＋１の代わりに使用され、γｉは、γｉ→ｉ＋１の代わりに使用されている。
【００２４】
ノードｉから次のノードへ時間ｔｉ内でｘｉナットを伝送するには、次式で表される電力ｐｉを必要とする。
【００２５】
【数２】
2010233209.tif 000004
【００２６】
この電力をシャノン−ハートレー方程式に代入すると、後続のノードｊ（ｊ＞ｉ）において受信されるナットが得られる。その結果の曲線は、時間ｔｉ→∞において最小ナット伝送が達成されるような、時間ｔｉにおいて減少する凹型である。したがって、ノードｉ １０６がｘｉナットを伝送する場合、後続のノードｊ（ｊ＞ｉ）は、少なくとも、次式（２）を受信する。
【００２７】
【数３】
2010233209.tif 000005
【００２８】
この実施の形態は、∞を最大総時間Ｔに変更することによって、式（２）の境界を際立たせるように、伝送されるナットｌｉ≦ｘｉに対する下限を使用する。これによって、次式（３）が得られる。ここで、式（３）の２番目の不等式は、ｌｉ→０のときタイトである。
【００２９】
【数４】
2010233209.tif 000006
【００３０】
式（３）の最初の不等式は、構成によって作成される。２番目の不等式は、ｌｉ＝０を中心とする級数展開による線形化であり、γｉ→ｊ／γｉ≦１についてこの公式が凸型であるので、下限である。
【００３１】
どちらの境界も時間又は電力割り当てを考慮しておらず、したがって、パスに沿ったナット割り当てを独立して決定することができる。例えば、最初の２つのリンクでは、ｘ１＝Ｘ及びｘ１→３≧ｘ１・γｉ→３／γ１である。各ノードが、伝送するナット数を最小にする場合、すなわち、次のノードがフルメッセージを受信することを確かめるのに、最小ナットが十分なナットである場合、上限は、次式で表される。
【００３２】
【数５】
2010233209.tif 000007
【００３３】
本明細書で定義するように、ｒｉｊは、ノードｉから次のノードへのナット数ｘｉの伝送の、後続のノードｊにおける受信を記述する係数であり、例えば、ｒｉｊは、式（２）又は式（３）のｘｉに対する係数である。
【００３４】
次に、オリジナルの問題（１）（式（１））における制約の最後の行を次式（４）のようにタイト化することができる。
【００３５】
【数６】
2010233209.tif 000008
【００３６】
式（４）において、∀ｉｊｒｉｊ≧０なので、変更された制約は凸錐である。変更された制約は、伝送する必要があるナット数の上限を示すので、変更された問題の実現可能な領域は、オリジナルの実現可能な領域の厳密に内部にあり、したがって、その解は上界である。したがって、式（４）は凸型であり、その解は、式（１）のオリジナルの問題の解の上限を示す。
【００３７】
任意の特定の電力割り当てｅｉについて、ナットｘｉとエネルギーｅｉとの関係は線形である。したがって、式（４）は、ナット割り当て線形計画法（ＬＰ）の制約である。
【００３８】
さらに、式（４）の解をオリジナルの式（１）に代入し、次式（５）で表される可分凸計画法（ｓｅｐａｒａｂｌｅ  ｃｏｎｖｅｘ  ｐｒｏｇｒａｍ）が得られる。
【００３９】
【数７】
2010233209.tif 000009
【００４０】
式（５）は、参照により本明細書に援用される関連米国特許出願第１２／２７１，２００号に記載された閉形式の解を有する双曲線上限（ｈｙｐｅｒｂｏｌｉｃ  ｕｐｐｅｒ−ｂｏｕｎｄ）を使用して解くことができる。
【００４１】
資源割り当て
図２は、本発明の実施の形態によるメッセージのマルチホップファウンテン符号化伝送のための資源を割り当てる方法２００を示す。方法２００のステップは、プロセッサ２９５を使用して実行される。
【００４２】
次のノードが前の伝送からの累積ナット数ｘａｃを既に受信して累積していることを考慮して、ノードｉから次のノードへ伝送されるメッセージの最小ナットｘｉを求める（２２０）。
【００４３】
例えば、ファウンテン符号化伝送といったレートレス伝送によれば、各ノードは、少なくともフルメッセージを受信すべきであり、したがって、最小ナットｘｌと累積ナットｘａｃとの合計は、Ｘナットよりも小さくなるべきではない。ここで、Ｘナットは、メッセージの送信元エントロピーである。送信元ノードから宛先ノードへのメッセージの伝送の時間Ｔ２１０、及びネットワーク１００のリンクのチャネル電力利得γｉｊ２１５が方法２００に入力される。
【００４４】
最小ナットｘｉを求める（２２０）ために、各ノード１０２が次式（６）に従ってサイズＸのフルメッセージを受信するという制約を条件として、ノード１０２のリレーを介して伝送されたすべてのナットの加重和を最小にする。
【００４５】
【数８】
2010233209.tif 000010
【００４６】
式（６）において、ｍｉｎは、最小化関数であり、ｃｉはコストパラメータであり、ｒｉｊは、ノードｉから次のノードへの伝送の結果としてノードｊにより受信されたナット数ｘｉである。
【００４７】
式（６）は、ナット割り当てＬＰであり、このナット割り当てＬＰは、図３に示された次式（７）で表される正準形３５０に書き換えることができる。
【００４８】
【数９】
2010233209.tif 000011
【００４９】
式（７）において、ｂは、ｂ＝１・Ｘであるようなナット割り当てベクトル３１０であり、Ａは、Ａｉ≧ｊ＝ｒｉｊであるような三角行列３３０であり、ｉ及びｊは、リレーノードのインデックスであり、ｃは、ｃｉ＝１／γｉであるようなコストパラメータｃｉのベクトル３４０である。三角行列Ａ ３００は、チャネル電力利得γｉｊ又はコストパラメータｃｉｊについて書き換えることができる。ベクトルｘｉ ２２５は、ノードｉから次のノードへ伝送される最小ナットを記述する。
【００５０】
ＬＰの閉形式の解
三角行列Ａ ３３０がカスケードしている場合、ＬＰを算術的に解くことによって、すなわち、ｉ番目の制約を満たすように最小のｘｉを順次選ぶことによって、ナット数ｘｉ ２２５を求める（２２０）。三角行列Ａ ３３０がカスケードしていない場合、従来の線形計画法ソルバを使用してＬＰを解くことにより、ナット数ｘｉ ２２５を求める（２２０）。
【００５１】
三角行列Ａ ３３０は、各対角が次の対角を決定付けている場合、すなわち、Ａｉｊ＞Ａｉｊ−１且つＡｉｊ＞Ａｉ＋１ｊである場合、カスケードしている。これは、チャネル利得比ｒｉｊがパスのホップ距離｜ｉ−ｊ｜と共に減少する場合に対応する。
【００５２】
行列Ａ ３３０がカスケードしており且つｃｉ≧ｃｉ＋１である場合、行列Ａ ３３０の各行は、左から右へ増加する。任意のｉ＜ｊについて、ｘｊを増加させることによるよりもｘｉを増加させることによってｊ番目の制約を満たすことの方が多くのコストを要する。その結果、最適なｘｊは、ｉ番目の制約を満たすのに必要な最小値を取り、その後の制約は無視することができる。Ｃ≡ｄｉａｇ（ｃ）であり且つｙ≡Ｃｘである場合、ＬＰは、（ＡＣ−１）（Ｃｘ）＝ＡＣ−１ｙ≧ｂであるようなｍｉｎ（ｃＴＣ−１）（Ｃｘ）＝１Ｔｙとして書き換えることができる。これは、逐次解が可能であることを示す。
【００５３】
問題がたとえカスケードしていなくても、逐次算術解ｘ（ハット）は、ＬＰ最適解と一致することができる。実際に、式の三角線形システムを解くことによって最適性をチェックすることができる。
【００５４】
解ｘ（ハット）が最適且つ正である場合、ＬＰのスラック変数及び双対変数はゼロでなければならない。ＬＰにおいて、スラック変数は、不等式を等式に変えるために制約に追加される変数である。双対定理は、相補スラック性として知られている主変数と双対変数との間の関係を含蓄している。
【００５５】
相補スラック性によれば、双対変数ｙは、一意の最適解については厳密に正でなければならず、それ以外については非負でなければならない。ゼロスラック変数は、ＡＴｙ＝ｃを含蓄している。行列Ａはフルランクであるので、解ｘ（ハット）及びｙ（ハット）は一意である。ＬＰは厳密に正であるので、ＬＰは、主双対制限（ｐｒｉｍａｌ  ａｎｄ  ｄｕａｌ  ｂｏｕｎｄｅｄ）され、したがって、強い双対性ｂＴｙ（ハット）＝ＣＴｘ（ハット）によって主双対制限される。したがって、ｘ（ハット）＞０であり、且つＡＴｙ＝ｃが、ｙ（ハット）≧０及びＣＴｘ（ハット）＝ｂＴｙ（ハット）を満たす解ｙ（ハット）を有する場合、ｘ（ハット）は、ＬＰを最適化し、解ｙ（ハット）＞０である場合、解ｘ（ハット）は一意である。
【００５６】
ＬＰにおける省エネルギー
一定の電力では、各リンクによる伝送時間は、伝送されたナット数に比例する。すなわち、以下で求める或る係数ｋｉについてｔｉ＝ｋｉｘｉである。さらに、ｘｉナットを時間ｔｉ＝ｋｉｘｉで伝送するのに必要な最小エネルギーは、ｅｉ＝ｘｉ・ｋｉ／γｉ（ｅｘｐ１／ｋｉ−１）である。したがって、エネルギーｅｉは、ナットｘｉにおいて線形であり、ナット割り当て線形計画法（式（７））は、ｃｉ＝ｋｉ／γｉ（ｅｘｐ１／ｋｉ−１）を設定することによってエネルギーを考慮する。
【００５７】
次数ｎの双曲線限界（ｈｙｐｅｒｂｏｌｉｃ  ｂｏｕｎｄ）を使用したエネルギー最小化について、最適な時間割り当ては、減衰の（ｎ＋１）乗根と共に増加する。これについては、参照により本明細書に援用される関連米国特許出願第１２／２７１，２００号を参照されたい。或るラムダについて、次式が使用される。
【００５８】
【数１０】
2010233209.tif 000012
【００５９】
これは、時間割り当て問題のラグランジュ乗数に比例する。その結果、線形計画法のコスト効率は、次式（８）のようになる。
【００６０】
【数１１】
2010233209.tif 000013
【００６１】
ＬＰ解は、比ｃｉ／ｃｊにのみ依存するので、最初のラムダを式（８）から除去することができる。同様に、一般的なａ、ｂについて比
【数１２】
2010233209.tif 000014
を保存する必要があるので、したがって、ラグランジュ乗数が大きいときは、部分式
【数１３】
2010233209.tif 000015
を
【数１４】
2010233209.tif 000016
と置き換えることができる。したがって、大きな利得λについて、式（８）のコスト効率は、次式（９）のように簡略化される。
【００６２】
【数１５】
2010233209.tif 000017
【００６３】
小さな利得λについては、式（９）のコスト構造が近似される。比ｃｉ／ｃｊの誤差限界は、式（８）の代わりに式（９）を使用して作成される。
【００６４】
ｂ≧ａ＞０で且つ任意の誤差フラクションδ＞０について、次式が成立する。
【００６５】
【数１６】
2010233209.tif 000018
【００６６】
この式において、最初の不等式は常に成立し、２番目の不等式は、利得λが次式のいずれかを満たすか又は超えるときに成立する。
【００６７】
【数１７】
2010233209.tif 000019
【００６８】
この式において、最初の不等式は、次式から取得される。
【００６９】
【数１８】
2010233209.tif 000020
【００７０】
これについては、以下で説明する。２番目の不等式については、
【数１９】
2010233209.tif 000021
であるので、
【数２０】
2010233209.tif 000022
を解いて、
【数２１】
2010233209.tif 000023
における保証が取得される。第２の形態は、δ∈［０，ｚ］において凸状分母（ｃｏｎｖｅｘ  ｄｅｎｏｍｉｎａｔｏｒ）の内側に弦を配置し、第３の形態は、弦の傾斜を緩和し、第４の形態は、その切片を緩和する。
【００７１】
【数２２】
2010233209.tif 000024
を設定し、
【数２３】
2010233209.tif 000025
を保証に乗算すると、次式（１０）で表されるＬＰコスト係数の任意の誤差の限界が得られる。
【００７２】
【数２４】
2010233209.tif 000026
【００７３】
コスト構造ｃｉ∝γｉ−１が与えられると、Ａｄｉａｇ（ｃ）−１は、チャネル利得の下三角行列となる。チャネル利得γｉ→ｊは、通例、パスのホップ距離｜ｉ―ｊ｜と共に減少するので、この行列はカスケードすると予測される。例えば、多くの場合において、実際に成立する十分条件ではあるが必要条件ではない条件は、すべてのｋについて、ｋホップにわたるリンク上のすべての利得が、ｋ＋１ホップにわたるリンク上のすべての利得よりも大きいということである。
【００７４】
資源の割り当て
各ノードが伝送する（２４０）最小ナットｘｉ ２２５を使用して、伝送２４０に必要な資源を割り当てる（２３０）。割り当てステップ２３０中、次式で表されるエネルギー曲線について閉形式の解を有する双曲線上限を見つけることによって、伝送時間ｔｉ内でナットｘｉのメッセージ２４５を伝送する（２４０）のに必要とされるエネルギーｅｉが求められる。
【００７５】
【数２５】
2010233209.tif 000027
【００７６】
同様に、エネルギーｅｉに基づいて伝送時間ｔｉが求められる。双曲線上限を見つけることに関する詳細は、関連米国特許出願第１２／２７１，２００号に開示されている。最後に、エネルギーｅｉ及び伝送時間ｔｉに基づいてｐｉ＝ｅｉ／ｔｉに従い、伝送時間ｔｉ内でナット数ｘｉを伝送するのに必要とされる伝送電力ｐｉが求められる。
【図１】
2010233209.tif 000031
【図２】
2010233209.tif 000032
【図３】
2010233209.tif 000033
【外国語明細書】
2010233209.tif 000034
2010233209.tif 000035
2010233209.tif 000036
2010233209.tif 000037
2010233209.tif 000038
2010233209.tif 000039
2010233209.tif 000040
2010233209.tif 000041
2010233209.tif 000042
2010233209.tif 000043
2010233209.tif 000044
2010233209.tif 000045
2010233209.tif 000046
2010233209.tif 000047
2010233209.tif 000048
2010233209.tif 000049
2010233209.tif 000050
2010233209.tif 000051
2010233209.tif 000052
2010233209.tif 000053
2010233209.tif 000054
2010233209.tif 000055
2010233209.tif 000056
2010233209.tif 000057
2010233209.tif 000058