(57)【要約】【課題】方法は、パケットを送信元ノードから中継ノードを介して宛先ノードへルーティングする。【解決手段】ノードは無線リンクｘによって接続される。各リンクｘに関してチャネル電力利得γを測定する。チャネル電力利得γから、各リンクｘに関して資源トレードオフ曲線ｙ＝ｆ（ｘ）を構築する。式中、ｙは資源の集合を表す。各資源曲線に対し、ｈ／ｘ＋ｃ≧ｆ（ｘ）となるように双曲上界ｈ／ｘ＋ｃをあてはめる。式中、ｈはスケール係数であり、ｃはオフセットである。双曲上界に従って最適資源配分を有するルートを選択する。次に、当該ルートを使用して、パケットを送信元ノードから宛先ノードへ伝送する。【選択図】図１
2010119086.tif 000002
【特許請求の範囲】
【請求項１】
パケットを送信元ノードから中継ノードを介して宛先ノードへルーティングする方法であって、前記ノードは無線リンクｘによって接続され、
各リンクｘに関してチャネル電力利得γを測定すること、
前記チャネル電力利得γから、各リンクｘに関して資源トレードオフ曲線ｙ＝ｆ（ｘ）（ｙは資源の集合を表す）を構築すること、
各資源曲線に対し、ｈ／ｘ＋ｃ≧ｆ（ｘ）（ｈはスケール係数であり、ｃはオフセットである）となるように双曲上界ｈ／ｘ＋ｃをあてはめること、
前記資源トレードオフ曲線に対する前記双曲上界に従って最適資源配分を有するルートを選択すること、及び
前記ルートを使用して、前記パケットを前記送信元ノードから前記中継ノードを介して前記宛先ノードへ伝送すること
を含む、パケットを送信元ノードから中継ノードを介して宛先ノードへルーティングする方法。
【請求項２】
前記資源の集合は、時間、電力、及びエネルギーを含み、前記資源トレードオフ曲線は、時間対電力、時間対エネルギー、電力対時間、及びエネルギー対時間を含む
請求項１記載の方法。
【請求項３】
前記集合内の前記資源のうちの１つは、前記集合内の他の２つの資源に対する制約に従って最小化される
請求項２記載の方法。
【請求項４】
各資源トレードオフ曲線は、確率関数によって表される
請求項１記載の方法。
【請求項５】
前記チャネル電力利得は経時的平均である
請求項１記載の方法。
【請求項６】
Ｂが資源バジェットであり、
【数１】
2010119086.tif 000062
（such that:となるような）
となるように、前記資源の集合の総使用を最小にすることをさらに含む
請求項１記載の方法。
【請求項７】
前記資源の集合は、前記パケットが前記送信元ノードから前記宛先ノードへ伝送される間、動的に配分される
請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には無線アドホックネットワークに関し、より詳細にはメッセージをルーティングしている間に資源を配分することに関する。
【背景技術】
【０００２】
セルラネットワークのような従来の無線ネットワークとは異なり、アドホックネットワークはインフラストラクチャを有しない。通常、アドホックネットワークは多数の低複雑度の送受信機（ノード）を使用して互いの間で情報を通信する。この手法はコストを減少させるのみでなく、単一リンクの失敗に対する過敏性も減少させる。これによって、アドホックネットワークは、超高信頼性通信リンクを必要とする用途において、非常に有望なものになっている。
【０００３】
高信頼性アドホック無線ネットワークは、２つの相反する制約を有する。ノードは電池式であるため、エネルギー消費量は低くなくてはならず、電池が消耗すると故障につながる可能性がある。他方で、データ送信が成功する確率は非常に高くなくてはならない。すなわち、データのパケットを、送信元ノードから宛先ノードへ所定の遅延の範囲内で送信しなくてはならない。
【０００４】
アドホックネットワークにおいて、エネルギーを最小にしながら、パケットを遅延制約の範囲内で宛先へ渡すルート、すなわち一連のノードを選択することが所望されている。単純な解決策は、各リンクが単純にパケットを固定期間内に伝送することを試みるように選択される、固定のパケットサイズ及び符号化速度を用いる物理層伝送を使用する。その場合、遅延制約を満たすことは、ホップ数を制限することと同義である。
【０００５】
しかしながら、この単純な手法は、特定のリンクに対しより多くのエネルギーを使用し、且つ、場合によっては他のリンクに対しより少ないエネルギーを使用することによって全体の遅延を減少させることができる可能性を無視している。単一リンクの場合、伝送時間とエネルギーとの間のトレードオフは単純である。シャノンの容量式によると、可能なデータレートは伝送電力と共に対数的に増加する。しかしながら、複数のホップを有するネットワークの場合、トレードオフははるかに複雑になる。トレードオフは、ルートを選択し、次に当該ルートに沿った各ホップに関してエネルギーレベルを選択することを含む。
【０００６】
Ｎ個のノードから成るユニキャストネットワークでは、各ノードは、適応変調・符号化（ＡＭＣ）を使用して伝送電力と伝送時間とのトレードオフを行うことができる。伝送は、パケットが遅延制約の範囲内に宛先に到着する場合にしか成功したと見なされない。送信が成功する確率ｑを同時に可能にしながら、全体のエネルギー消費を最小にするルート及びホップあたりのエネルギー割当てを選択することが所望されている。ここで、ｑは９０〜９９．９９９％の範囲である。
【０００７】
一般的には、チャネル状態情報（ＣＳＩ）はアドホックネットワークにおいて動的であるため、ルーティングにはＣＳＩの統計しか利用可能でない。無線伝搬チャネルのコヒーレンス時間、すなわち要求される更新間隔は、約数ミリ秒である。ネットワーク全体にわたってＣＳＩを頻繁に更新することによって、許容不可能なオーバヘッドがもたらされる。大規模ネットワークにおいて、すべての可能性のあるリンクに関するルーティング情報を通信することのオーバヘッドトラフィックによって、スペクトル効率及び電池寿命が減少する。他方で、オンデマンドのルート発見も、ルート発見プロセスが多くの場合、遅延制約よりも長い時間を要するため、実現可能ではない。
【０００８】
このように、問題は明確であり、実際に関連しているが、解決するのが過度に難しい。Ｎ個のノードから成るネットワークにおいて、約Ｎ！個の可能なルートが存在し、各ルートに関して、ノードの伝送エネルギーが確率的制約の下で最適化されなくてはならない。
【０００９】
１つの方法は、遅延制約を考慮するが、単一リンクにおけるスケジューリングに関してのみ考慮する（非特許文献１）。他の方法は、エネルギー／遅延トレードオフを考慮するが、ここでもまた単一リンクに関してのみ考慮する（非特許文献２及び非特許文献３）。
【００１０】
複数の方法が同時のルーティング及び電力制御を考慮するが、瞬時ＣＳＩの想定の下で、遅延制約なしで考慮する（非特許文献４）。別の方法は、確率的遅延制約を有するルーティングを考慮するが、各ノードに関して固定の伝送電力、及び凸界を想定する（Brand他によって出願された米国特許出願）。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Berry他著「Communication over fading channels with delay constraints」(IEEE Transactions on Information Theory, vol.48, pp.1135-1149, 2002)
【非特許文献２】Zhong他著「Delay-constrained energy-efficient wireless packet scheduling with QoS guarantees」（IEEE Trans. Wireless Communications, vol.5, 2006）
【非特許文献３】Yang他著「Energy minimization for real-time data gathering in wireless sensor networks」（IEEE Trans. Wireless Communications, vol.5, 2006）
【非特許文献４】Cruz他著「Optimal link scheduling and power control in CDMA multihop wireless networks」（IEEE Globecom, 2002）
【発明の概要】
【課題を解決するための手段】
【００１２】
本発明の実施の形態は、無線アドホックネットワークにおいて、遅延制約下でエネルギーを最小にしながら、又はエネルギー制約下で遅延を最小にしながら、パケットを送信元ノードから宛先ノードへルーティングする方法を提供する。チャネル状態情報（ＣＳＩ）を与えられると、本方法は対象となる資源に対する厳密な双曲界（hyperbolic bound）を提供すると共に、関連する最適化を解く。
【００１３】
平均ＣＳＩのみが利用可能である場合、確率的（probabilistical）性能を達成することができる。界の別の集合が、保証された成功率を有する資源最適ルーティングをサポートする。
【発明の効果】
【００１４】
無線ネットワークにおいて、時間資源、電力資源、及びエネルギー資源は、チャネル容量制約に従って、伝送時間とのトレードオフとなる可能性があり、互いに対するサービス品質を保証しながら１つの資源を最適化することが望ましい。
【００１５】
本発明では、組み合わせ設定及び確率論的設定において、そのような資源トレードオフを最適化する方法を提供する。本発明では、３％未満の予測される準最適性を有する厳密な双曲上界及び閉形式の資源配分と、動的再配分と、近最適資源トレードオフを有するルートを発見する低複雑度の組み合わせ解決策と、当該ルートの準最適性に対する界とを達成すると共に、これらの方法のすべてを、資源トレードオフ曲線が確率的にのみ知られている確率論的設定に対し拡張する。
【００１６】
適切に一般化すると、本方法は、確率論的資源トレードオフ及びバジェット制約に従う組み合わせ最適化が存在する任意のネットワークにおいて有用である。
【図面の簡単な説明】
【００１７】
【図１】送信元から宛先へのルートが強調された、本発明の実施の形態による中継ネットワークの概略図である。
【図２Ａ】双曲上界を有する資源の４つのタイプのうちの１つのタイプ、時間対電力のグラフである。
【図２Ｂ】双曲上界を有する資源の４つのタイプのうちの１つのタイプ、時間対エネルギーのグラフである。
【図２Ｃ】双曲上界を有する資源の４つのタイプのうちの１つのタイプ、電力対時間のグラフである。
【図２Ｄ】双曲上界を有する資源の４つのタイプのうちの１つのタイプ、エネルギー対時間のグラフである。
【図３】図１のルートを表すコスト線及び当該ルートに関連付けれるコストを表す縦座標のグラフである。
【図４】すべてのコストに対する下界である区分的に滑らかな曲線のグラフである。
【図５】本発明の実施の形態による最適資源配分を用いるルーティング方法のフロー図である。
【発明を実施するための形態】
【００１８】
図１は本発明の実施の形態による中継ネットワークを示す。ネットワークは、送信元ノード１０１と、中継ノード１０２と、宛先ノード１０３とを備える。ノードは送受信機とすることができる。ノード間の辺はチャネル１１０を表す。最適ルート１２０は破線によって指示される。
【００１９】
本発明では、チャネルおける遅延１１５に注目する。遅延は、ノードを接続するチャネルの信頼度に起因し得る。信頼度は、部分的に、チャネル利得又は伝送電力に起因する。瞬時チャネル利得の測定は時間を要する可能性があるため、本発明では平均利得の測定を使用する。この利得はチャネル状態情報（ＣＳＩ）から求められる。
【００２０】
ＣＳＩはパケットを配信するのに使用することができるデータレートに直接影響を及ぼす。雑音が多いか又は信頼できないチャネルにおいて、パケットを、より低いデータレートで、さらに非常に長い誤り訂正符号を用いて、反復して再送する必要がある場合がある。これは待ち時間（遅延）を増大させる。本発明の通信ネットワークにおいて、ノードにおけるキューイング遅延は無視される。
【００２１】
ネットワークモデル
シャノンの容量式から、１Ｈｚ帯域の加法性白色ガウス雑音（ＡＷＧＮ）チャネル及びリンク容量における伝送時間（遅延）は、ナット（情報又はエントロピーの対数単位）あたりの秒で表すと、
【００２２】
【数１】
2010119086.tif 000003
【００２３】
である。式中、ｐは電力（雑音電力によって正規化される）であり、γはチャネル電力利得又は逆減衰である。本明細書において使用される場合、電力は、エネルギーが伝送される速度、又は所与の時間単位の間に消費されるエネルギー量である。
【００２４】
伝送時間はナット／帯域幅に線形に比例するため、本明細書におけるすべての数式はナット／Ｈｚ単位である。逆数
【００２５】
【数２】
2010119086.tif 000004
【００２６】
は、所望の伝送時間のために必要とされる電力を与え、エネルギー消費
【００２７】
【数３】
2010119086.tif 000005
【００２８】
は、ｌｉｍｔ→∞ｅ＝１／γであるため、１／γ以上（no less than 1/γ）である。
【００２９】
逆に、ｅ≧１／γのエネルギー単位を費やすことによって、
【００３０】
【数４】
2010119086.tif 000006
【００３１】
秒の伝送時間がもたらされる。式中、Ｗ−１（・）は[−ｅｘｐ−１，０）→[−１，−∞）をマッピングする多値ランバートＷ関数の分枝である。この不等式はγｅ＝１において正確であり、γｅ＞１の場合に良好な近似である。
【００３２】
これらの関数は正の線上で減少する凸形であり、無線ノードの実際の動作範囲にわたって深く「湾曲した」資源トレードオフを明確にする。たとえば、式（１）は、冪級数近似
【００３３】
【数５】
2010119086.tif 000007
【００３４】
を有する。
【００３５】
厳密に湾曲部の両側に位置する部分範囲（典型的には高帯域幅又は低ＳＮＲ）内で演算する場合、線形近似が有用である。本発明では、構築した資源トレードオフ曲線全体に対する、最適又は限定的に（boundedly）準最適の非線形解決策を提供する。
【００３６】
それぞれが一意のチャネル利得γｉ及び凸形の資源トレードオフ減少曲線ｙｉ＝ｆｉ（ｘｉ）を有する無線チャネル又はリンクｘｉが与えられると、以下の問題を解くことができる。
【００３７】
配分：一連のＮ個のリンク（ホップ）ｘｉ、及び資源ｙに対する（ナット／Ｈｚあたりの）総バジェットＢが与えられると、資源の総使用量を最小にする配分が求められる。
【００３８】
【数６】
2010119086.tif 000008
（such that:となるような）
【００３９】
ルーティング：ネットワークを通じた、最適資源配分を提供するルートを選択する。
【００４０】
再配分：部分情報又は他の情報が与えられると、最適な配分を動的に求める。
【００４１】
これらの決定論的最適化は、チャネル状態情報（ＣＳ）が、当該チャネル状態情報に従って動作するのに十分長く有効である、すなわちチャネルが低速に変化している場合に有用である。
【００４２】
確率論的設定
多くのネットワークにおいて、瞬時（ＣＳＩ）は測定可能とすることができないか、又は対象となる時間尺度にわたって一定ではない。したがって、本発明ではＣＳＩにわたる確率分布を対象とする。
【００４３】
別の資源に対する或る制約（電力／遅延又は遅延／電力）に従う１つの資源の使用を最適化するのではなく、本発明では、その他の資源に対する制約を満たすことに成功する確率に対する界に従う１つの資源の使用を最小化する。すなわち、式（５）は以下に置き換えられる。
【００４４】
【数７】
2010119086.tif 000009
（s.t.:となるように）
【００４５】
ここで、ｙｉはｉ番目のリンクに配分される資源であり、Ｘｉは、その確率分布関数（ＰＤＦ）が資源ｙｉによってパラメータ化される確率変数であり、Ｂはバジェットであり、ｑは最小の受け入れ可能な成功率である。
【００４６】
経時的分布及び電力コスト
チャネル利得は平均利得を有して指数関数的に分布する確率変数であるため、実際のネットワークにおいて偶発性が生じる。利得γについて式（２）を解くことによって、（−１＋ｅｘｐ  １／ｔ）／ｐは、パラメータ
【００４７】
【数８】
2010119086.tif 000010
【００４８】
を有して指数関数的に分布することが明らかになり、一方、ｐ／（−１＋ｅｘｐ  １／ｔ）は、パラメータ
【００４９】
【数９】
2010119086.tif 000011
【００５０】
を有して逆γ分布する。
【００５１】
条件付き時間及び電力の累積分布関数（ＣＤＦ）について解くことによって、
【００５２】
【数１０】
2010119086.tif 000012
【００５３】
がもたらされる。式中、
【００５４】
【数１１】
2010119086.tif 000013
は不完全なγ関数である。これらのＣＤＦは、電力（又は時間）の消費が与えられる場合の時間（又は電力）制約を満たす確率を与える。同様に、エネルギー及び時間は以下の確率論的トレードオフを有する。
【００５５】
【数１２】
2010119086.tif 000014
【００５６】
これらの準指数分布は幾つかの好ましくない特性を有する。これらの準指数分布は、指数分布族におけるいかなる分布よりも裾が重い。これらの準指数分布は、畳み込みの下で閉じておらず、式（６）内の確率変数の和を評価することができない。これらの準指数分布は無限のモーメントを有するため、期待値を推論することができない。
【００５７】
これらの分布の結合を分析的に比較することは、不可能でないとしても困難である。決定論的設定すら厄介である。一方で、配分問題は凸関数の凸結合であり、したがって、原則として、様々な凸最適化技法を通じて問題を数値的に解くことができる。
【００５８】
しかしながら、数値的作業量はかなりのものであり、確保されているよりも多くの時間及びエネルギーを必要とする場合がある。有用であるためには、解は計算的に単純であると共に、資源の制限されたネットワークにおいて信頼がおけるように十分正確であるべきである。
【００５９】
この目的のために、本発明では、決定論的トレードオフに対し、厳密な上側資源トレードオフの集合を提供する。次に、資源トレードオフ配分問題を閉形式で解く。これによって次に、Ｍ個のリンクから成るネットワークに関して、Ｏ（Ｍ  ｌｏｇ２Ｍ）時間において近最適ルーティング解をサポートするリンク特性決定がもたらされる。本発明ではまた、確率論的問題を決定論的問題に変換し、それを解く。
【００６０】
双曲資源トレードオフ
本発明では、或る大域指数ｎ＞０であり、且つ各リンクに関して各リンクの一意のスケール係数ｈｉ及びオフセットｃｉである場合に、ｈｉ／ｘｎｉ＋ｃｉの形の双曲線を有する或る有限の実用範囲にわたって各リンク（チャネル）ｘについて構築した、資源トレードオフ曲線ｙ＝ｆ（ｘ）を有界化する上側資源によって決定論的設定を開始する。スケーリング及びオフセットは曲線あてはめを可能にする。
【００６１】
図２Ａ〜図２Ｄは、決定論的資源トレードオフに対する近似として、これらが大きな動作範囲にわたって極めて良好であることを示す。図２Ａ〜図２Ｄは、双曲上界を有する４つのタイプの資源トレードオフ、すなわち時間対電力、時間対エネルギー、電力対時間、及びエネルギー対時間を示す。ｎを適切に選択することによって、予測される近似誤差を常に数パーセントに低減することができる。実際、多くのケースにおいて、最大値及び予測誤差を分析的に制限することができる。
【００６２】
通常、最大誤差も同様に制限することができる。正式には、本発明では、以下の４つの方策のうちの１つを使用して、双曲線ｈ／ｘｎ＋ｃを有する凸形の減少曲線ｙ＝ｆ（ｘ）に、或る間隔
【００６３】
【数１３】
2010119086.tif 000015
【００６４】
で上界を設ける：
【００６５】
（Ａ）上界を保証するのに十分小さいｎを選択し、
【００６６】
【数１４】
2010119086.tif 000016
【００６７】
である端点ｘ０、ｘ１において交わる２つの曲線を設定する。
【００６８】
（Ｂ）上界を保証するのに十分大きいｎ、及び予測されるギャップ又は最大ギャップを最小にするμを選択し、
【００６９】
【数１５】
2010119086.tif 000017
【００７０】
である或る点ｘ＝μ∈２[ｘ０，ｘ１]において上記曲線を接線にする。
【００７１】
(Ｃ)ｈ、ｃ、ｎを、資源トレードオフ関数ｆ（ｘ）の良好な近似を与えるようにあてはめると共に、オフセットｃを上界を作るように調節する。
【００７２】
（Ｄ）１つの資源トレードオフに対する上界を反転して、逆資源トレードオフに対し、シフトされた双曲上界をもたらす。
【００７３】
【数１６】
2010119086.tif 000018
【００７４】
一例として、式（１）のように、電力ｐの関数としての時間ｔに関して、双曲界ｔ≦ｈ／ｐｎ＋ｃを、式（８）に示すように或るμ＞０において曲線を接線にすることによって、あてはめることができる。
【００７５】
【数１７】
2010119086.tif 000019
【００７６】
すべての正のｐ、μ、及びｎ＜１の場合に、この双曲線はｐ＝μにおいて等値である上界である。
【００７７】
この近似は、０＜ｎ＜１を選択することによって改善することができる。しかしながら、結果としての双曲線は、μの周りの或る有限の間隔においてしか上界とならない場合がある。本発明では、接点μを選択して、電力コストにおける或る分布に関して予測される近似誤差を最小にすることができる。
【００７８】
たとえば、予測される付加誤差
【００７９】
【数１８】
2010119086.tif 000020
【００８０】
を考慮する。式中、ｈ、ｃは上記のように定義され、Ｐｒ（ｐ）は平均λを有する指数密度関数である。この積分は収束しないが、μに関するその導関数は、或る有限の動作範囲ｐ∈［ｐ０，ｐ１］を想定すると、μ＝
【００８１】
【数１９】
2010119086.tif 000021
【００８２】
において、０＜μ＜∞において単一ゼロを有する。一般的な動作方針（regime）では、（γｐ∈［４，１００］ＳＮＲであり、平均λ＝１０を有して指数的に分布する。付加誤差はｎ＝１におけるμ≒０．９５λ、及びｎ＝３／４におけるμ≒０．９９λにおいて最小になる。
【００８３】
最大の予測される誤差に対する界は代数的に続く。あまり正式ではないが、単純にμ＝λを設定すると共に予測される乗法誤差を数値的に計算することによって、双曲界はｎ＝１において平均＜２．４％、及びｎ＝３／４において＜１．０％だけ電力コストを過大評価していることが分かる。
【００８４】
最適な決定論的配分
双曲上界ｈｉ／ｘｎｉ＋ｃｉ≧ｆｉ（ｘｉ）の場合、式（５）の配分問題は以下の形態をとる。
【００８５】
【数２０】
2010119086.tif 000022
（s.t.:となるような）
【００８６】
一般性を損なうことなく、本発明では固定Σｉｃｉを取り去り、単体制限をアップグレードしてΣｉｘｉ＝Ｂにおいて等値になるようにする。これを閉形式で以下のように解く。
【００８７】
双曲プログラム
問題
【００８８】
【数２１】
2010119086.tif 000023
（s.t.:となるような）
【００８９】
は、
【００９０】
【数２２】
2010119086.tif 000024
【００９１】
の場合に一意の解
【００９２】
【数２３】
2010119086.tif 000025
【００９３】
を有し、これは値
【００９４】
【数２４】
2010119086.tif 000026
【００９５】
を有し、式中、||・||はＬｐ準ノルムである。
【００９６】
式（１０）のような全配分問題の場合、コストは
【００９７】
【数２５】
2010119086.tif 000027
【００９８】
によって上界を設けられる。
【００９９】
ｍ＝１であると想定する。最適なｎ＝１配分は、バジェットが設けられた資源の
【０１００】
【数２６】
2010119086.tif 000028
【０１０１】
及び最小にされた資源の
【０１０２】
【数２７】
2010119086.tif 000029
【０１０３】
をｉ番目のリンクに割り当てる。
【０１０４】
決定論的資源のトレードオフに対するｎ＝１の双曲界の場合、スケール係数は、或る定数ｚに関してチャネル減衰：ｈｉ≒ｚ／γｉを伴って変化することを示すことができる。したがって、たとえば電力及び他のノードとの干渉を最小にすると共に配信期限を保証するために、チャネル減衰の平方根に従って電力及び時間を分配するべきである。この配分は双曲界からの準最適界を有する。このケースでは、予測される準最適性は＜２．４％である。
【０１０５】
本発明では、水平方向にシフトされた双曲線
【０１０６】
【数２８】
2010119086.tif 000030
（s.t.:となるような）
【０１０７】
に関して
【０１０８】
【数２９】
2010119086.tif 000031
【０１０９】
において解かれる閉形式の配分を提供する。
【０１１０】
シフト（ｖｉ）によって、凸形の資源トレードオフ曲線へのより柔軟なあてはめが可能になるが、シフトされていない双曲線はルーティング問題においてはるかに多用途である。
【０１１１】
動的分散型配分
配分を決定し、ルートに沿って伝送した後、パケットはｉ番目のリンクに達し、自身のチャネル利得がずれていることを発見する場合がある。したがって、本発明では、最適資源配分を動的に修正する。そのために、部分和
【０１１２】
【数３０】
2010119086.tif 000032
【０１１３】
及び期限Ｂｉまでの残り時間を伝搬及び更新することが有用である。ｎ＝１について、リンクｉの双曲スケール係数がｈｉからｈ'ｉへ変化する場合、リンクｉにおける最小配分は
【０１１４】
【数３１】
2010119086.tif 000033
【０１１５】
から
【０１１６】
【数３２】
2010119086.tif 000034
【０１１７】
へ変化する。
【０１１８】
これは、分散式の方法の範囲を示唆する。ここで、瞬時測定から各ｈｉを求めるのではなく、履歴統計に基づいて各ｈｉについて値を想定する。次に、上述したように配分を動的に更新する。この概念は、下記の確率論的設定においてより詳細に説明される。
【０１１９】
近最適ルーティング
本発明の双曲上界に関して近最適ルートを求めることが可能である。そのために、本発明では、線形多基準組合わせ最適化の概念を導入する。ここで、目的関数は複数の基準の重み付けされた平均である。一般的には、重み付けを知る前に最適値を想定する。重み付けパラメータによって指数付けされた、可能な解の集合全体を考慮する。ここで、二基準経路コスト
【０１２０】
【数３３】
2010119086.tif 000035
【０１２１】
を考慮する。式中、Ｐは経路（ルート）であり、λは、各辺の長さ
【０１２２】
【数３４】
2010119086.tif 000036
【０１２３】
を求めるために２つの基準の平衡をとる重み付けパラメータである。
【０１２４】
これは、ネットワーク内の各送信元−宛先経路Ｐｉを、傾斜
【０１２５】
【数３５】
2010119086.tif 000037
【０１２６】
及び切片
【０１２７】
【数３６】
2010119086.tif 000038
【０１２８】
を有する正象限（λ≧０）内の直線にマッピングする、二基準最短経路（ＢＳＰ）問題を定義する。
【０１２９】
主要な特性は、各直線ａｉλ＋ｂｉ上に、λ＝ａｎ／ｍｉにおいて、最適配分の下の対応する経路の非線形コストを指数付けする点が存在する、すなわち、
【０１３０】
【数３７】
2010119086.tif 000039
【０１３１】
であることである。
【０１３２】
本発明では、このジオメトリを使用して最小双曲コストルートを得る。
【０１３３】
図３は、可能なルートに対応する線３０１の「束」を示す。各ルートは、式（１４）に示すように関連付けられるコスト点３０２を有する。本発明の解決策は、この直線の束の最大下界の周りを（文字通り）回転することであって、この回転は束境界と呼ばれる区分線形凹曲線である（図４を参照のこと）。
【０１３４】
最大下界を形成する複数の直線はＢＳＰ解の集合である。各直線は、或るλ間隔における最短ルートを表し、Ｏ（Ｍ  ｌｏｇＭ）時間において、λの適切な値によって生成されるスカラー辺重みｗｉ（λ）に対するダイクストラの最短経路アルゴリズムによって求めることができる。
【０１３５】
図４は、二次のケースにおける、非線形コスト包絡線を構成するためのコストを示す。各指数は、正象限内の、ｌｉ（λ）＝ａｉλ＋ｂｉの形の直線に関連付けられる。この図は、区分線形束境界を形成する直線の部分集合を示す。各経路のコストは座標
【０１３６】
【数３８】
2010119086.tif 000040
【０１３７】
における自身の直線上の点である。
【０１３８】
コスト包絡線は、境界上の各交差点を中心として直線を旋回させると共に、直線の傾斜ａが、旋回点４０２において交わるこれらの２本の包絡線間で変化するときに
【０１３９】
【数３９】
2010119086.tif 000041
【０１４０】
を満たす点の位置を追跡することによって形成される、区分的放物曲線である。コスト包絡線及び境界コスト点は、グラフ内の任意の経路によって達成可能な、最小の可能なｍｉｎｉ  ａ２ｉ＋ｂｉに対し下界及び上界を与える。対象となる曲線は、直線ａλ＋ｂ  ４０１を境界の上端を中心として回転させ、当該境界の頂点を中心として旋回させ（４０２）、λ＝ａｎ／ｍにおいて点の旋回を追跡することによって形成される。
【０１４１】
正のｍ，ｎの場合、この曲線は、凸であり、区分的に滑らかであり、且つ同じＢＳＰ境界４０３を有する任意のネットワークに関するすべての可能な最適コスト点に対する下側包絡線である。図４はこの包絡線が境界経路のコスト点を接続することを示す。したがって、これらの経路のうちの１つは以下の準最適界を有する最適又は近最適のいずれかである。
【０１４２】
双曲最小コストルーティング
Ｐｉ，Ｐｊを、それらの直線が束境界４０３上で、λｉｊ＝（ｂｊ−ｂｉ）／（ａｊ−ａｉ）において交差する、２つの経路（ルート）とする。ここで、ａｊ＜ａｉである。境界は、ｎ＝ｍ＝１の場合にｍｉｎｉｊ（ａｉ−１／２λｉｊ）２、また一般的なｍ、ｎの場合にインタフェースｍｉｎｉｊａｉ（ａｎ／ｍｉ−λｉｊ）＋（ｎ／ｍ）（（ｍλｉｊ）／（ｍ＋ｎ））（ｍ＋ｎ）／ｎによって、付加準最適上界を設けられた最適ルート又は近最適ルートのいずれかを含むような１つの対を有する。より緩い界（（ａｎ／ｍｉ−ａｎ／ｍｊ）／２）（ｍ＋ｎ）／ｎはｎ＝ｍ＝１の準最適比
【０１４３】
【数４０】
2010119086.tif 000042
【０１４４】
をもたらす。
【０１４５】
境界線の母集団は、辺の数と共に少なくとも多項式的に増大することに留意されたい。したがって、準最適性はグラフサイズと共に斬新的に消滅する。ＢＳＰ解集合を、簡略化された多項式平滑化時間計算量で、最良経路のために明示的に列挙及び走査することができる。しかしながら、包絡線をパラメータ的に特徴付けて、差別化することができるため、正確な二分間隔を決定するために包絡線導関数を使用して、境界線の傾斜に対し二分探索を実施して最低非線形コストを有する境界経路及び指数を求めることができる。
【０１４６】
確率論的方法
ここで、確率的資源トレードオフを説明する。上述したように、最適化変数の分布の準最適性は、分析的手法の妨げとなる。本発明では、より扱いやすい線形加法的位相型分布の集合を用いて成功率に下界を設ける方が好ましい。幾つかの可能性が存在する。本発明では、共通拡散パラメータβ及び変化する位置パラメータαｉを有するγ分布を使用する。たとえば、Ｘ１〜γ（α１β）、且つＸ２〜γ（α２β）の場合、Ｘ１＋Ｘ２〜γ（αｉ＋α２，β）である。
【０１４７】
各リンクについて、有限の動作範囲を想定し、その間隔における真の分布によって占められるパラメータ化された有界化分布、たとえば
【０１４８】
【数４１】
2010119086.tif 000043
【０１４９】
を選択する。
【０１５０】
そのため、有界化分布に関して行われるいかなる想定も、成功の真の確率を過小評価する。たとえば、時間制約に従う電力を最小化するとき、ｔｍａｘを、全時間バジェットになるように、且つ、ｔｍｉｎを、最大電力において達成可能な最短単一リンク伝送時間になるように、慎重に選択することができる。これによって、成功する事象の集合は、界が有効である事象の集合の部分集合になる。
【０１５１】
真の分布は準指数的に裾が重いため、その下を真の分布が占める或る交点ｔｃ＞０が存在する。２つのＣＤＦをｔｃ＝ｔｍａｘにおいて等値に設定することによって、資源使用ｙｉと有界化ＣＤＦのパラメータαｉとの間の凸関数関係αｉ＝ｇｉ（ｙｉ）を求める間の、動作範囲にわたる界の有効性が保証される。
【０１５２】
通常、資源使用ｙｉが増加することによってパラメータαｉが減少し、パラメータαｉが減少することによって確率Ｐｒ（Ｘｉ≦ｔ）が増加する。任意の固定資源配分ｙ１，ｙ２，ｙ３，．．．がネットワーク全体及び線形加法的有界化分布にわたって与えられると、辺コストαｉ＝ｇｉ（ｙｉ）上の最小コストルートは成功率の下界を最大にする。
【０１５３】
固定ルートに対する資源配分
確率論的資源トレードオフを有するルートに対する配分問題を考慮する。リンクの任意のルートに関して、分布
【０１５４】
【数４２】
2010119086.tif 000044
【０１５５】
が存在するように、リンク状の有界化分布が構築される。これは、Ａ≧Σｉαｉの場合にそのルートに対する成功率に下界を設ける。すなわち、
【０１５６】
【数４３】
2010119086.tif 000045
（at least:少なくとも）
【０１５７】
の場合に
【０１５８】
【数４４】
2010119086.tif 000046
【０１５９】
である。
【０１６０】
特定の成功率ｑを得るために、
【０１６１】
【数４５】
2010119086.tif 000047
【０１６２】
を設定し、その第１のパラメータにおけるＧβを反転させて、新規制約
【０１６３】
【数４６】
2010119086.tif 000048
【０１６４】
を得る。資源使用は、αｉに関してｙｉ＝ｇ−１（αｉ）として表すこともできるため、式（６）を以下のように書き換えることができる。
【０１６５】
【数４７】
2010119086.tif 000049
（s.t.:となるような）
【０１６６】
本発明では、最適αｉについて解くための決定論的設定において開発された同じ双曲有界化方式及び最適化方法を利用し、次に資源配分ｙｉ＝ｇｉ（αｉ）を計算する。
【０１６７】
本発明では、時間制約に従う最小電力使用のケースを解明する。成功率に対する下界を保証するために、各リンクにおいて、ｔ＝ｔｍａｘにおいて等値であるγＣＤＦ及び時間ＣＤＦを設定すると共に必要とされる電力ｐｉについて解き、以下をもたらす。
【０１６８】
【数４８】
2010119086.tif 000050
【０１６９】
αｉ＝０を中心とする、冪級数展開によって、双曲近似
【０１７０】
【数４９】
2010119086.tif 000051
（for:但し）
【０１７１】
が明らかになる。これはｃｉを適切に選択することによって上界となる。
【０１７２】
これを用いて、式（１２）を式（１５）に直接適用して、双曲界に関する最適αｉを求めることができる。最適αｉは双曲界及びγ界の両方に関する最適配分ｙｉを与える。同じ構造を使用して、電力制約を与えられた時間を最小にする。ただし、以下を除く。
【０１７３】
【数５０】
2010119086.tif 000052
（for:但し）
【０１７４】
時間を与えられたエネルギーの場合、ｇ−１（α）及びｈｉは、ｔｍａｘによって乗算されることを除いて、時間を与えられた電力のｇ−１（α）及びｈｉと同じである。エネルギーを与えられた時間の場合、以下を仮定する。
【０１７５】
【数５１】
2010119086.tif 000053
【０１７６】
それゆえ、以下のようになる。
【０１７７】
【数５２】
2010119086.tif 000054
（for:但し）
【０１７８】
ｎ＝１の双曲界の下のすべてのケースにおいて、
【０１７９】
【数５３】
2010119086.tif 000055
【０１８０】
を有する対称性が存在する。したがって、γ位置パラメータの最適設定は以下の通りである。
【０１８１】
【数５４】
2010119086.tif 000056
【０１８２】
しかしながら、実際の実施の態様において、非対称性が存在する。電力を最小にするとき、配分された電力で伝送する。時間を最小にするとき、送信機及び受信機は電流チャネル利得を交換し、配分された時間制約を満たすのに必要なだけの電力を使用して伝送する。要求される成功率が高すぎる場合、最適配分は１つ又は複数のリンクを当該リンクの動作範囲の外側に出す。これらのリンクにおける資源使用を当該リンクの最大に固定し、残りのリンクにおいて配分問題を再度解くことができる。これよって実行可能な配分をもたらすことができない場合、選択された界に関して所望の成功率が実現可能でないと報告する。
【０１８３】
ルーティング
式（１５）における最適化問題が双曲に有界化された後、γ界及び双曲界に対して近最適経路を求めるために、ルーティングを変更せずに適用することができる。
【０１８４】
動的配分
マルチホップ中継が進行すると、不確定性が低減される。確率分布は狭まり、リンクｉに到達した後、バジェットが設けられた資源のうちのＢｉのみが残る。リンクｉにおいて式（１５）を再度解くことによって、
【０１８５】
【数５５】
2010119086.tif 000057
【０１８６】
の修正されたｎ＝ｍ＝１上界が与えられる。
【０１８７】
リンクｉの確率分布が、たとえば当該リンクの瞬時チャネル利得を測定することによって、伝送前に損なわれる場合、決定論的資源トレードオフｙｉ＝ｆｉ（ｘｉ）を求める。この情報に対して成功率を調整することによって、以下の、式（１５）の最適問題の変更がもたらされる。
【０１８８】
【数５６】
2010119086.tif 000058
（s.t.:となるような）
【０１８９】
ｘｉに対する成功率の非線形依存性は難題を呈する。ｎ＝１界を用いて解くために、アフィン関数
【０１９０】
【数５７】
2010119086.tif 000059
【０１９１】
を用いて成功率に下界を設け、上記のように確率論的リンクコストｇ−１ｊ（αｊ）に上界を設け、ｈ'ｉ／ｘｉ＋ｃ'ｉを用いて決定論的コストｆｉ（ｘｉ）に上界を設け、次に双曲プログラム
【０１９２】
【数５８】
2010119086.tif 000060
（s.t.:となるように）
【０１９３】
を解いて、上述した動的配分に対する変形である
【０１９４】
【数５９】
2010119086.tif 000061
【０１９５】
のリンクｉにおいて最小安全消費を得る。
【０１９６】
方法
図５は、本発明に従って決定論的にルーティングする全般的な方法を示す。ネットワーク１００におけるノード間のリンクｘのチャネル利得γ５１５を測定する（５１０）。上述したように、利得は経時的平均とすることができる。利得から、資源トレードオフ曲線ｙ＝ｆ（ｘ）を構築する（５２０）。式中、ｙは資源であり、ｘはリンクである。双曲上界（ｈ／ｘ＋ｃ）５３５を曲線にあてはめる（５３０）。式中、ｈはスケール係数であり、ｃは各リンクのオフセットである。最適資源配分ｙｉを有するルートｘｉを選択し（５４０）、それに従ってパケット５５５を伝送する（５５０）。
【０１９７】
本発明を特定の好ましい実施の形態を参照して説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１】
2010119086.tif 000063
【図２Ａ】
2010119086.tif 000064
【図２Ｂ】
2010119086.tif 000065
【図２Ｃ】
2010119086.tif 000066
【図２Ｄ】
2010119086.tif 000067
【図３】
2010119086.tif 000068
【図４】
2010119086.tif 000069
【図５】
2010119086.tif 000070
【外国語明細書】
2010119086.tif 000071
2010119086.tif 000072
2010119086.tif 000073
2010119086.tif 000074
2010119086.tif 000075
2010119086.tif 000076
2010119086.tif 000077
2010119086.tif 000078
2010119086.tif 000079
2010119086.tif 000080
2010119086.tif 000081
2010119086.tif 000082
2010119086.tif 000083
2010119086.tif 000084
2010119086.tif 000085
2010119086.tif 000086
2010119086.tif 000087
2010119086.tif 000088
2010119086.tif 000089
2010119086.tif 000090
2010119086.tif 000091
2010119086.tif 000092
2010119086.tif 000093
2010119086.tif 000094
2010119086.tif 000095
2010119086.tif 000096
2010119086.tif 000097
2010119086.tif 000098
2010119086.tif 000099
2010119086.tif 000100
2010119086.tif 000101
2010119086.tif 000102
2010119086.tif 000103