(57)【要約】  マルチホップ・ルート全体に沿った全てのリンクに共通の新しいパラメータを導入することにより、数多くのそのリンクの各々に対して、ａ）リンク送信エネルギー、ｂ）リンク送信時間或いはリンク送信帯域幅或いはリンク符号語消費量、及びｃ）リンク送信電力を表わす３つの相互に依存するリンク送信パラメータのセットをより柔軟に配分することができる。基本的に、その共通パラメータは、マルチホップ・ルート全体に対して与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決定される（Ｓ１）。その思想は、それから、各々の検討中のリンクに対して、共通パラメータとローカルリンク特性に基づいた３つの相互依存するリンク送信パラメータを割り当てるか、或いは配分することである（Ｓ２）。このようにして、全ての３つのリンク送信パラメータは、各々のリンク送信パラメータが、そのローカルリンク特性にも依存すると想定して、そのリンクが異なるリンク特性を有する場合、そのルート上の少なくとも２つのリンク相互間で異なる場合がある（一般にはそうであろう）。その共通パラメータは、与えられた対象ＥＴＥ関数を最適化する処理において決められることが好ましい。
2009500901.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップ・ネットワークにおける少なくとも２つのリンクに関与するマルチホップ・ルートに関するリンクパラメータを制御する方法であって、
マルチホップ・ルート全体に沿った全てのリンクに共通な新しいパラメータを、前記マルチホップ・ルート全体に関する与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決定する工程と、
前記リンクの各々に関して、夫々がローカルリンク特性にも依存して、次の３つの相互に依存するリンク送信パラメータのセット、即ち、
ａ）リンク送信エネルギーを表わすリンク送信パラメータ、
ｂ）リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
ｃ）リンク送信電力を表わすリンク送信パラメータ
を前記共通のパラメータと前記ローカルリンク特性とに基づいて割当てる工程とを有することを特徴とする方法。
【請求項２】
前記ＥＴＥ制約の下で、前記リンクの各々に関して、前記相互に依存するリンク送信パラメータのセットが、前記リンクが異なるリンク特性を有する場合、３つ全ての相互に依存するリンク送信パラメータが一般に前記ルート上の少なくとも２つのリンク間で異なるように割当てられることを特徴とする請求項１に記載の方法。
【請求項３】
前記共通のパラメータは、前記ＥＴＥ制約の下で、与えられた対象ＥＴＥ関数を最適化する過程において決定されることを特徴とする請求項１に記載の方法。
【請求項４】
前記リンクの各々に関して、前記相互に依存するリンク送信パラメータのセットを割当てる工程は、前記夫々のリンクにより情報を送信する際に、使用する前記３つの相互に依存するリンク送信パラメータの２つを明瞭に決定する工程を有し、
これにより、残りのリンク送信パラメータは、前記３つのリンク送信パラメータの相互依存性により与えられることを特徴とする請求項１に記載の方法。
【請求項５】
前記共通のパラメータは、夫々の考慮されているリンクに関して、前記ＥＴＥ制約の下で、第１のリンク送信パラメータに関する与えられた対象ＥＴＥ関数を最適化する過程において決定され、
前記３つの相互に依存するリンク送信パラメータの２つを明瞭に決定する工程は、
前記共通のパラメータと前記ローカルリンク特性とに基づいて、前記第１のリンク送信パラメータを決定する工程と、
前記第１のリンク送信パラメータと前記ローカルリンク特性の関数として、前記第１のリンク送信パラメータによりパラメータライズされる第２のリンク送信パラメータを決定する工程とを有することを特徴とする請求項４に記載の方法。
【請求項６】
前記対象ＥＴＥ関数は、前記エンド・ツー・エンド（ＥＴＥ）送信パラメータである、
ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータ、
ＥＴＥ送信時間、又は、ＥＴＥ送信帯域幅、又は、ＥＴＥ送信符号語消費量
を表わすＥＴＥ送信パラメータ、
ＥＴＥ送信電力を表わすＥＴＥ送信パラメータ
の内の１つを含み、
前記エンド・ツー・エンド（ＥＴＥ）送信パラメータの別のパラメータは前記ＥＴＥ制約として作用することを特徴とする請求項３又は５に記載の方法。
【請求項７】
ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータは、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥの送信符号語消費量を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化されることを特徴とする請求項６に記載の方法。
【請求項８】
ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータに関する制約のもとで、最適化されることを特徴とする請求項６に記載の方法。
【請求項９】
ＥＴＥ送信電力を表わすＥＴＥ送信パラメータは、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥの送信符号語消費量を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化されることを特徴とする請求項６に記載の方法。
【請求項１０】
ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、ＥＴＥ送信電力を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化されることを特徴とする請求項６に記載の方法。
【請求項１１】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、ＥＴＥスループットを含むことを特徴とする請求項８又は１０に記載の方法。
【請求項１２】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、前記ルート全体にわたって用いられる副搬送波の総数により表現されるＥＴＥ送信帯域幅を含むことを特徴とする請求項８又は１０に記載の方法。
【請求項１３】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、前記ルート全体にわたって用いられる符号語の総数により表現されるＥＴＥ符号語消費量を含むことを特徴とする請求項８又は１０に記載の方法。
【請求項１４】
前記与えられた対象ＥＴＥ関数を最適化する過程は、ラグランジュ乗数法により実行され、前記共通パラメータは前記ラグランジュ乗数を表わしていることを特徴とする請求項３又は５に記載の方法。
【請求項１５】
前記第１のリンク送信パラメータはリンク送信電力であり、
前記第２のリンク送信パラメータはリンク送信速度であり、
統合リンク速度適合とリンク電力制御とは、前記決定された第１と第２のリンク送信パラメータに基づいて実行されることを特徴とする請求項４又は５に記載の方法。
【請求項１６】
前記ＥＴＥ制約の下で、前記マルチホップ・ルートの個々のリンクに関して、前記相互に依存するリンク送信パラメータのセットが、３つ全てのリンク送信パラメータが前記ルート上のいずれか２つのリンク間で異なるように割当てられることを特徴とする請求項１に記載の方法。
【請求項１７】
前記ルートに沿って前記ＥＴＥ制約送信パラメータに関連したリンク送信パラメータ情報を収集する工程と、
前記収集されたリンク情報から総ＥＴＥ送信パラメータ値を形成する工程と、
前記与えられたＥＴＥ送信パラメータ制約に関連して前記総ＥＴＥ送信パラメータ値を比較する工程をさらに有し、
前記共通パラメータを決定する工程は、前記比較の結果に基づいて制御されることを特徴とする請求項１に記載の方法。
【請求項１８】
前記収集する工程と、前記形成する工程と、前記比較する工程と、前記共通パラメータを決定する工程とは、反復的に実行されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記共通パラメータを前記マルチホップ・ルートに沿って多くのノードに分配し、前記ノード夫々が、前記共通パラメータと前記ローカルリンクパラメータとに基づいて、前記相互依存するリンク送信パラメータのセットを割当てることを可能にする工程をさらに有することを特徴とする請求項１７又は１８に記載の方法。
【請求項２０】
前記リンク送信パラメータ各々は、前記ローカルリンク特性に、非線形的に依存しており、
前記共通パラメータを決定する工程は、非線形処理に基づいていることを特徴とする請求項１に記載の方法。
【請求項２１】
マルチホップ・ネットワークにおけるルーティングの方法であって、
多数の可能なルートの各々に対して、全てのルートに共通な与えられたＥＴＥ送信パラメータ制約に従い、各ルートにおける各リンクに関して、次の３つの相互依存のリンク送信パラメータである
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
の内の１つに関して、与えられた対象エンド・ツー・エンド（ＥＴＥ）関数を
夫々がローカルリンク特性にも依存した３つの相互依存のリンク送信パラメータ全てが、前記リンクが異なるリンク特性をもつときに、一般には前記ルート上での少なくとも２つのリンクの間で異なるように前記考慮しているルートに沿った全てのリンクに共通のパラメータにより最適化するという手順を実行することを特徴とする方法。
【請求項２２】
マルチホップ・ネットワークにおける少なくとも２つのリンクに関与するマルチホップ・ルートに関するリンクパラメータを制御する装置であって、
前記マルチホップ・ルートの全体に沿った全てのリンクに共通なパラメータを、前記マルチホップ・ルート全体に関する与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決定する手段と、
前記マルチホップ・ルートにおける前記リンクの各々に関して、夫々がローカルリンク特性にも依存して、次の３つの相互依存するリンク送信パラメータのセット、即ち、
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
を前記共通のパラメータと前記ローカルリンク特性とに基づいて割当てる手段とを有することを特徴とする装置。
【請求項２３】
前記割当てる手段は、前記リンクの各々に関して、前記相互に依存するリンク送信パラメータのセットを、前記リンクが異なるリンク特性を有する場合、３つ全ての相互依存するリンク送信パラメータが一般に前記ルート上の少なくとも２つのリンク間で異なるように割当てるように動作することを特徴とする請求項２２に記載の装置。
【請求項２４】
前記共通のパラメータを決定する手段は、前記ＥＴＥ制約の下で、与えられた対象ＥＴＥ関数を最適化する手段を有することを特徴とする請求項２２に記載の装置。
【請求項２５】
前記リンクの各々に関して、前記相互依存するリンク送信パラメータのセットを割当てる手段は、前記夫々のリンクにより情報を送信する際に、使用する前記３つの相互依存するリンク送信パラメータの２つを明瞭に決定する手段を有し、
これにより、残りのリンク送信パラメータは、前記３つのリンク送信パラメータの相互依存性により与えられることを特徴とする請求項２２に記載の装置。
【請求項２６】
前記共通のパラメータを決定する手段は、夫々の考慮されているリンクに関して、前記ＥＴＥ制約の下で、第１のリンク送信パラメータに関する与えられた対象ＥＴＥ関数を最適化する手段を有し、
前記３つの相互依存するリンク送信パラメータの２つを明瞭に決定する手段は、
前記共通のパラメータと前記ローカルリンク特性とに基づいて、前記第１のリンク送信パラメータを決定する手段と、
前記第１のリンク送信パラメータと前記ローカルリンク特性の関数として、前記第１のリンク送信パラメータによりパラメータライズされる第２のリンク送信パラメータを決定する手段とを有することを特徴とする請求項２５に記載の装置。
【請求項２７】
前記対象ＥＴＥ関数は、前記エンド・ツー・エンド（ＥＴＥ）送信パラメータである、
ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータ、
ＥＴＥ送信時間、又は、ＥＴＥ送信帯域幅、又は、ＥＴＥ送信符号語消費量
を表わすＥＴＥ送信パラメータ、
ＥＴＥ送信電力を表わすＥＴＥ送信パラメータ
の内の１つを含み、
前記エンド・ツー・エンド（ＥＴＥ）送信パラメータの別のパラメータは前記ＥＴＥ制約として作用することを特徴とする請求項２４又は２６に記載の装置。
【請求項２８】
前記最適化する手段は、ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータを、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥの送信符号語消費量を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化するよう動作することを特徴とする請求項２７に記載の装置。
【請求項２９】
前記最適化する手段は、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータを、ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータに関する制約のもとで、最適化するよう動作することを特徴とする請求項２７に記載の装置。
【請求項３０】
前記最適化する手段は、ＥＴＥ送信電力を表わすＥＴＥ送信パラメータを、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥの送信符号語消費量を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化するよう動作することを特徴とする請求項２７に記載の装置。
【請求項３１】
前記最適化する手段は、ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータを、ＥＴＥ送信電力を表わすＥＴＥ送信パラメータに関する制約のもとで、最適化するよう動作することを特徴とする請求項２７に記載の装置。
【請求項３２】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、ＥＴＥスループットを含むことを特徴とする請求項２９又は３１に記載の装置。
【請求項３３】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、前記ルート全体にわたって用いられる副搬送波の総数により表現されるＥＴＥ送信帯域幅を含むことを特徴とする請求項２９又は３１に記載の装置。
【請求項３４】
前記ＥＴＥ送信時間又はＥＴＥ送信帯域幅又はＥＴＥ送信符号語消費量を表わすＥＴＥ送信パラメータは、前記ルート全体にわたって用いられる符号語の総数により表現されるＥＴＥ符号語消費量を含むことを特徴とする請求項２９又は３１に記載の装置。
【請求項３５】
前記与えられた対象ＥＴＥ関数を最適化する手段は、ラグランジュ乗数法に従って動作するように構成され、前記共通パラメータは前記ラグランジュ乗数を表わしていることを特徴とする請求項２４又は２６に記載の装置。
【請求項３６】
前記第１のリンク送信パラメータはリンク送信電力であり、
前記第２のリンク送信パラメータはリンク送信速度であり、
前記装置はさらに、統合リンク速度適合とリンク電力制御とを、前記決定された第１と第２のリンク送信パラメータに基づいて実行する手段を有することを特徴とする請求項２５又は２６に記載の装置。
【請求項３７】
前記割当てる手段は、前記ＥＴＥ制約の下で、前記マルチホップルートの個々のリンクに関して、前記相互依存するリンク送信パラメータのセットを、３つ全てのリンク送信パラメータが前記ルート上のいずれか２つのリンク間で異なるように割当てるよう動作することを特徴とする請求項２２に記載の装置。
【請求項３８】
前記ルートに沿って前記ＥＴＥ制約送信パラメータに関連したリンク送信パラメータ情報を収集する手段と、
前記収集されたリンク情報から総ＥＴＥ送信パラメータ値を形成する手段と、
前記与えられたＥＴＥ送信パラメータ制約に関連して前記総ＥＴＥ送信パラメータ値を比較する手段とをさらに有し、
前記共通パラメータを決定する手段は、前記比較する手段の比較結果に基づいて制御されることを特徴とする請求項２２に記載の装置。
【請求項３９】
前記収集する手段と、前記形成する手段と、前記比較する手段と、前記共通パラメータを決定する手段とは、反復的に実行するよう構成されていることを特徴とする請求項３８に記載の装置。
【請求項４０】
前記共通パラメータを前記マルチホップ・ルートに沿って多くのノードに分配する手段をさらに有し、
前記ノード夫々が、前記共通パラメータと前記ローカルリンクパラメータとに基づいて、前記相互依存するリンク送信パラメータのセットを割当てるよう動作可能であることを特徴とする請求項３８又は３９に記載の装置。
【請求項４１】
前記装置は前記マルチホップ・ルートに沿った複数のノードの１つ以上に組み込まれることを特徴とする請求項２２乃至４０のいずれか１項に記載の装置。
【請求項４２】
前記装置は専用制御システムで実現されることを特徴とする請求項２２乃至４０のいずれか１項に記載の装置。
【請求項４３】
前記リンク送信パラメータ各々は、前記ローカルリンク特性に、非線形的に依存しており、
前記共通パラメータを決定する手段は、非線形処理のために構成されていることを特徴とする請求項２２に記載の装置。
【請求項４４】
マルチホップ・ネットワークにおけるルーティングの装置であって、
多数の可能なルートの各々に対して、全てのルートに共通な与えられたＥＴＥ送信パラメータ制約に従い、各ルートにおける各リンクに関して、次の３つの相互依存のリンク送信パラメータである
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
の内の１つに関して、与えられた対象エンド・ツー・エンド（ＥＴＥ）関数を夫々がローカルリンク特性にも依存した３つの相互依存のリンク送信パラメータ全てが、前記リンクが異なるリンク特性をもつときに、一般には前記ルート上での少なくとも２つのリンクの間で異なるように前記考慮しているルートに沿った全てのリンクに共通のパラメータにより最適化する手段と、
前記対象ＥＴＥ関数の最適化値をもつルートを前記ルートの中から選択する手段とを有することを特徴とする装置。
【請求項４５】
マルチホップ・ネットワークにおける少なくとも２つのリンクに関与するマルチホップ・ルートに関するリンクパラメータを制御する装置であって、
前記マルチホップ・ルートの全体に沿った全てのリンクに共通なパラメータを、前記マルチホップ・ルート全体に関する与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決定するよう構成された資源コントローラと、
前記マルチホップ・ルートにおける前記リンクの各々に、夫々がローカルリンク特性にも依存した、次の３つの相互依存するリンク送信パラメータのセット、即ち、
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
を前記共通のパラメータと前記ローカルリンク特性とに基づいて割当てるよう構成されたリンク送信パラメータ割当器とを有することを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にマルチホップ・ネットワークに関し、特に、マルチホップ・ネットワークにおけるルーティングばかりでなく、選択されたマルチホップ・ルートに対するリンクパラメータの制御に関する。
【背景技術】
【０００２】
マルチホップ・ネットワークは、固有の電力／エネルギー効率、および実現可能な電力／エネルギーのレベルで中間の中継ノードを介して受信範囲外のノードを接続する能力故に、将来の無線通信技術に対する鍵となる技術として論じられている。マルチホップ・ネットワークでは、お互いからの圏外にあるノードが、それらのメッセージをその発信元からその宛先に転送できる中間に位置するノードから恩恵を受けることができる。伝統的に、マルチホップ・ネットワークは、ノードが大抵は移動体機器で、中心となる調整インフラストラクチュアが存在しない、いわゆるアドホック・ネットワークと多くの場合関連していた。しかしながら、マルチホップ・ネットワーキングの思想は、ノードが固定されている場合もまた適用することができる。さらに、ノードが固定され、そしてチャネルに耐性がある場合に、特に、集中的な調整をまた思い描くことができる。マルチホップ・ネットワークでは、無線リンクに加えて有線リンクを含む複合型のネットワークを思い描ける場合もある。
【０００３】
ルーティングは、一般に適切なルーティング経路を決め、そしてそのネットワークを経由して情報を転送する基本的なタスクが関係する。これらのタスクの前者は通常ルート決定と呼ばれ、そして後者は多くの場合パケット転送と呼ばれる。
【０００４】
発信元ルーティングでは、通常はその発信元のノードが全体のルートを決めるものと想定される。その中間ノードは、それで単に蓄積および転送ノードとして動作し、その宛先ノードへの経路上にあるその次のノードにそのパケットをひたすら転送するに過ぎない。
【０００５】
ホップ・バイ・ホップ・ルーティングでは、各々のノードは、基本的に、数多くの宛先の各々に対して、好ましい次のホップ・ノードの情報を有するルーティング表を決定し、そして維持する。あるノードがパケットを受信すると、そのパケットの宛先に関する情報に基づいて、そのパケットをその次のノードに転送する。その転送処理は、そのパケットがその宛先に達するまでノードからノードへと継続する。
【０００６】
そのネットワーク・ノードはルーティング情報を渡し、そして様々なルーティング情報メッセージを転送することによりそれらのルーティング表を維持する。そのルーティング情報は、使われるその特定のルーティング方式に依存して必然的に変化する。
【０００７】
ホップ・バイ・ホップ・ルーティング方式は、通常、２つの主なクラス、すなわち、リンク状態および距離ベクトル・アルゴリズムに分類される。リンク状態アルゴリズムは、一般にルーティング情報を全てのノードに送りつける（しかしながらそのネットワークのごく一部に送りつける解もまたある）が、各々のノードは、そのとき、それ自身のリンクの状態を記述した情報を送信するだけである。これに対して、距離ベクトル・アルゴリズムは、隣接ノード間でのみルーティング・コスト情報を交換することに基づいている。
【０００８】
伝統的なやり方は、いわゆる経路ツリーを展開することである。図１Ａは、そのような経路ツリーの例を説明しており、ここでは所定の宛先ノードにルーツ（root）が置かれる。マルチホップ・ネットワークでは、最短経路アルゴリズムに基づいてその経路ツリーを計算することがよく知られており、そのツリーの中の様々なノードからその宛先ノードへの決められた最短経路が、いわゆる“最小コスト経路”であることを暗示している。各々のリンクは、それで通常差分コストにより特徴付けられ、そして各々のノードには、決められた最短経路に沿ってその宛先に達する累積コストが割り当てられる。実際には、そのツリーは、移動度および変化するリンク状態を管理するために絶えず更新される。
【０００９】
ベルマン−フォード最短経路アルゴリズムは、最短経路アルゴリズムのよく知られた例である（ダイクストラ・アルゴリズムは、伝統的なルーティング・アルゴリズムの別の例である）。ベルマン−フォード・アルゴリズムは、インターネットのような有線ネットワークでは中心的な役割を果たしてきているが、しかしまた、無線マルチホップ・ネットワークでも重要な機能を有している。ベルマン−フォード・アルゴリズムの長所は、分散型でそして“非協調的な”やり方で、最短経路決定を提供できることである。ベルマン−フォード・アルゴリズムはまた、隣接ノード間でのルーティング・コスト情報の交換に基づいて、有限期間内での収束を保証する。
【００１０】
ベルマン−フォード・アルゴリズムに対しては、与えられた宛先のセットのうち各々の宛先ｄに対するあるノードνiのコストＣiは、分散ベルマン−フォード方程式を介して次のように決められることができる。
【００１１】
2009500901.tif 000003
【００１２】
ここで、νj∈Ｎjは、ノードνiに属する隣接ノードの隣接インデクスであり、Ｃj(d)は隣接ノードνiの宛先ノードｄに至るコスト、そしてΔＣijはノードνiからνjに進むコスト（即ち、ホップあたりのコスト、またはそのリンク・コスト）である。
【００１３】
反復回数は、整数、したがって上限がホップ数、例えば最大２ホップに限定されると良い。
【００１４】
とにかく、そのツリーの中の特定のノードがその次のパケット転送処理でパケットを送信しようとする場合、そのノードは発信元ノードと見なされ、そしてそのパケットは、図１Ｂで説明されているように、その発信元からその宛先への決められたルーティング経路に従う。異なるノードは、時間とともにその同じ宛先にパケットを送信する場合がある。それ故、異なるノードが、発信元ノードとして振る舞い、そしてそれらそれぞれの最短経路に沿って送信する。さらに、複数の宛先が存在しうるので、複数のツリーが、各々は対応する宛先をルーツ（root）として生成される場合がある。その転送処理の中でパケットを送信する場合、そのノードは、効率的な送信を提供するために、リンク適応と電力制御との内、少なくともいずれかのようなリンク制御を用いる。
【００１５】
前述のとおり、ルーティング方式の共通の目的は、通常、ある意味で最適である経路を見出すことである。例えば、“最短経路”という表現は、通常、最小コスト経路に対応し、その経路或いはルート(route)は、ある特定のコストメトリックに関してその最小コストを提示する経路であるということを暗示している。
【００１６】
例えば、スロットになっていないチャネル・アクセスにおける共通のルーティング方式は、全てのホップに対して送信電力を一定に保つことであり、全てのホップが異なる経路損失に遭遇することを想定していて、最小の累積送信時間（或いは遅延）を提示する経路を選択する。
【００１７】
この文脈では、適切なリンク距離関数（メトリック：metric）の例は、その推定平均リンク速度を用いることであり、速度適応能力を想定してリンク・コストをその平均リンク速度の逆数、即ち、
【００１８】
2009500901.tif 000004
【００１９】
として定義することである。このメトリックは、二通りに理解されることができる。第一に、固定長のパケットに対して、最小の送信時間経路を提示することを目指すことである（そのネットワークにおける待ち行列遅延が無視できるものと想定している）。しかしながら、固定長のデータ位相（そのデータ位相におけるパケット数は速度適応に依存して可変である）を有するマルチホップ方式の環境では、それはある経路に沿っての最小時間資源利用を提示する。平均速度に基づくリンクメトリックには、伝統的なシャノン容量により見積もられる。
【００２０】
2009500901.tif 000005
【００２１】
ここで、Ｂはその帯域幅（システム全体で唯一の共通の帯域幅が使用される場合は無視しうる）、Ｅ｛．．．｝はその期待値、Ｐiはノードνiの送信電力（固定されても良いし、あるいは何か他のメカニズムにより決定されても良い）であり、σN2は、（ノードνjにおける）雑音レベルである。その項、σN2は、潜在的に平均の干渉を含むこともでき、それで受信器雑音とは別に複素ガウス雑音としてモデル化される。
【００２２】
同じ方策が、スロット化されたチャネル・アクセス方式に対して使用されても良いが、しかしこの場合、遅延の代わりに、１つのメッセージに対するエンド・ツー・エンド時間利用が最小化されるであろう。たとえ、これがその物理層遅延を最小化しなくても、その遅延はその継続時間のホップ数倍となるものであるので、ある程度ヒューリスティックに、マルチホップ・ネットワークにおけるユーザ送信をできるだけ多く詰め込むことができるようにしようとする。
【００２３】
スロット化されたチャネル・アクセスにおける別の一般的な方式は、ホップあたりの速度が全てのホップに対して（そしてそれ故、パケット当たり、ビット当たりの送信時間が）同じであり、そしてそれからそのエンド・ツー・エンド（総）電力が、関連ノードにわたる電力割り当てにより最小化されると想定している。あるいは、全てのホップにわたる同一の速度に対して、総経路損失を最小化するのに十分であるかもしれない。
【００２４】
この環境での可能なメトリックの例は、その平均リンク利得Ｇijを使用し、リンク・コストを平均リンク利得の逆数（非特許文献１）、即ち、ΔＣij＝Ｇij-1として定義することである。このメトリックは、（電力固定で）大きな受信器ＳＮＲ（信号対雑音比）値と、（電力制御のもとで）最小電力ルートを与える。
【００２５】
所望の目標リンク速度
【００２６】
2009500901.tif 000006
【００２７】
に対してシャノン容量を用いて、その最小電力ルートを決めると
【００２８】
2009500901.tif 000007
【００２９】
となる。
【００３０】
これは、全てのリンクにわたって単一の共通目標リンク速度を想定する場合、一般に上述した逆パス利得メトリックのケースに相当する。
【００３１】
特許文献１は、パス全体にわたって使用される累積送信電力を最小化するための合理的なコストメトリックとしてリンク送信電力の使用について記載している。これは電池消費に役立ち、そしてまたそのシステムにおける干渉レベルを減らし、新しい接続の余地を残して、それ故により高いネットワーク負荷での稼動を可能にする。
【００３２】
そのメトリックに干渉を含めることが可能である。干渉ベース型のメトリックは、その思想は最小の相殺的干渉をもたらすルートを使用することである最小干渉ルーティング（ＬＩＲ）（非特許文献２）と、その思想は最小の干渉に遭遇するルートを使用することである最小妨害ルーティング（ＬＲＲ）（非特許文献３）とを含む。
【特許文献１】米国特許出願公開第２００３／０１６１２６８号明細書
【非特許文献１】リンク利得メトリック、ミルズ（Mills）、ローエル（Lauer）、９５
【非特許文献２】ＬＩＲ（最小干渉ルーティング）、スティーブンス（Stevens）、８８
【非特許文献３】ＬＲＲ（最小阻害ルーティング）、パースレイ等（Pursley et al.）、９３
【発明の開示】
【発明が解決しようとする課題】
【００３３】
そのメトリックにトラフィック負荷を含めることもまた可能である。しかしながら、そのメトリックにそのようなトラフィックの側面を含める（例えば、トラフィック負荷の側面と媒体アクセス規則とを組み込む）ことは、安定性の問題を考慮することも必要とするので、単純ではない。
【００３４】
指摘したように、従来のルーティング方式は、通常、その取られた経路が累積送信時間（或いは遅延）のような累積リンク・コスト、累積或いは総送信電力、或いはホップ数を最小化することを保証し、全てのリンクにわたって、あるリンクパラメータ（例えば、リンク送信電力或いはリンク速度）が、少なくとも１つの他のリンクパラメータ（例えば、リンク速度或いは送信電力）を一定に保ちながら、変化するのを許している。
【課題を解決するための手段】
【００３５】
本発明は先行技術による装置のこれらおよび他の欠点を克服する。
【００３６】
本発明の目的の概略は、マルチホップ・ネットワークにおいてリンク送信パラメータをより効率的に割り当てあるいは配分することである。
【００３７】
マルチホップ・ルートのリンクにわたって情報を送信するために、利用できるネットワーク資源をより最適に利用することが、具体的な目的である。特に、そのルートに対する一定の品質を保証し、そして同時に送信エネルギー或いは電力のような高価な資源の使用を最適化（最小化）することが望ましい。
【００３８】
マルチホップ・ネットワークにおいて、あるルートに対するリンク送信パラメータを制御するための改良された方法と装置を提供することが、具体的な目的である。
【００３９】
マルチホップ・ネットワークにおいて、ルーティングをより効率的に実行することも、本発明の具体的な目的である。
【００４０】
これらおよび他の目的が、添付の請求の範囲により定義されるように、本発明によって達成される。
【００４１】
前述のように、従来のルーティング方式は、その取られた経路が累積送信時間（或いは遅延）のような累積リンク・コスト、総送信電力あるいはホップ数を最小化することを保証し、全てのリンクにわたって、あるリンク送信パラメータが、他のリンクパラメータのうちの少なくとも１つを一定に保ちながら、変化するのを許す。しかしながら、本発明による徹底的な解析は、このことが、リンク適応および電力制御のような課題を含むそのリンク・レベルでの送信パラメータの制御と適応に悪影響を及ぼす全く重大な制約であることを明らかにする。
【００４２】
発明者らは、マルチホップ・ルート全体に沿った全てのリンクに共通な新しいパラメータを導入することにより、多数のリンクの各々に対して、ａ）リンク送信エネルギー、ｂ）リンク送信時間或いはリンク送信帯域幅あるいはリンク送信符号語数（リンク符号語消費量）、及び、ｃ）リンク送信電力を表わす３つの相互に依存するリンク送信パラメータのセットをより柔軟に配分することができるということを認識した。基本的に、その共通パラメータは、マルチホップ・ルート全体に対する与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決められる。その思想は、それから、各々の検討中のリンクに対して、その共通パラメータおよびローカルリンク特性に基づいて、３つの相互依存するリンク送信パラメータを割り当てあるいは配分することである。このようにして、全ての３つのリンク送信パラメータは、各々のリンク送信パラメータがそのローカルリンク特性にも依存していると想定すると、そのリンクが異なるリンク特性を有する場合、一般にそのルート上の少なくとも２つのリンク間で異なる。
【００４３】
３つの相互依存するリンク送信パラメータのうちの２つが、それぞれのリンクにわたって情報を送信する場合に使用するために明示的に決められ、そしてその残りのリンク送信パラメータは、その３つのリンク送信パラメータの相互依存性により、“単に”与えられることが好ましい。
【００４４】
本発明のリンク送信パラメータを柔軟に割り当て／配分するために使用される共通パラメータは、ヒューリスティックな手法で、例えば、比較的単純な経験則を使用して、決められるかもしれない。
【００４５】
あるいは、より体系的な手法で、その共通パラメータは、各々の検討中のリンクに対して、所定のＥＴＥ制約を考慮してそのリンク送信パラメータのうちの１つについて、与えられた対象エンド・ツー・エンド（ＥＴＥ）関数を最適化する処理においてで決められる。
【００４６】
それから第１のリンク送信パラメータが、その共通パラメータおよびローカルリンク特性に基づいて決められ、そして、第２のリンク送信パラメータが、第１のリンク送信パラメータによりパラメータ化され、第１のリンク送信パラメータとそのローカルリンク特性の関数として決められる。その決められたパラメータは、統合リンク速度適応やリンク電力制御のような課題を含む高度なリンク制御に使用されると良い。
【００４７】
都合よく、その３つの基本的な物理パラメータ、電力、時間／帯域幅／符号語およびエネルギーが考えられ、与えられたマルチホップ・ルートに対して、エンド・ツー・エンドの最適化のためのパラメータのうちの１つを、それらパラメータの内のもう１つの制約のもとで選ぶ。より一般的には、その対象ＥＴＥ関数は、以下のＥＴＥ（エンド・ツー・エンド）送信パラメータのうちの１つを含むように選ばれる。即ち、
ａ）ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータと、
ｂ）ＥＴＥ送信時間或いはＥＴＥ送信帯域幅或いはＥＴＥの送信符号語数（ＥＴＥ符号語消費量）を表わすＥＴＥ送信パラメータと、
ｃ）ＥＴＥ送信電力を表わすＥＴＥ送信パラメータと
である。一方、エンド・ツー・エンド（ＥＴＥ）送信パラメータのうちのもう１つは、ETE制約として作用する。
【００４８】
対象ＥＴＥ関数とＥＴＥ制約の実際の選択は、全体的な設計最終目標および性能目標に依存する。例えば、ＥＴＥ送信エネルギーを表わすＥＴＥ送信パラメータは、ＥＴＥ送信時間或いはＥＴＥ送信帯域幅或いはＥＴＥの送信符号語数に関する制約のもとで、最適化される。あるいは、ＥＴＥ送信時間／帯域幅／符号語数を表わすＥＴＥ送信パラメータは、ＥＴＥエネルギー制約のもとで最適化される。さらに別の例は、ＥＴＥ送信電力を表わすＥＴＥ送信パラメータを、ＥＴＥ送信時間或いはＥＴＥ送信帯域幅或いはＥＴＥの送信符号語数を表わすＥＴＥ送信パラメータに関する制約のもとで最適化することに関係し、逆もまた同様である。
【００４９】
ＥＴＥ送信時間／帯域幅／符号語数を表わすＥＴＥ送信パラメータが最適化される場合、実際の対象ＥＴＥ関数は、ＥＴＥスループットとルート全体にわたって使用される副搬送波の総数との内の少なくともいずれかを含むことができる。
【００５０】
適切な最適化手法の１つの例は、ラグランジュ乗数法であり、ここではその共通パラメータがそのラグランジュ乗数を表わしている。
【００５１】
代表的は実用化では、その共通パラメータは、そのノードの各々がその一連の相互に依存するリンク送信パラメータを決めることができるように、そのマルチホップ・ルートに沿った多くのノードに分配される。適応を可能にするために、その選ばれたＥＴＥ制約送信パラメータに関連したリンク送信パラメータ情報は、そのルートに沿って収集されることが好ましく、総ＥＴＥ送信パラメータ値が、収集されたリンク情報に基づいて形成される。総ＥＴＥ送信パラメータ値は、それから、そのＥＴＥ性能が許容できるか、或いはその共通パラメータが再計算され、その関連ノードに再分配される必要があるかどうかを決めるために、与えられたＥＴＥ送信パラメータ制約と比較されると良い。
【００５２】
普通、それらリンク送信パラメータ各々は、その経路利得対雑音比のようなローカルリンク特性に非線形的に依存しており、その共通パラメータは、非線形処理に基づいて、例えば、対応する連立（結合）非線形方程式を解くことにより決められる。
【００５３】
本発明はまた、マルチホップ・ネットワークにおけるルート選択を可能にするために上記の思想の拡張を提案する。基本的に、その拡張された思想は、多数の可能なルートの各々に対して与えられたＥＴＥ制約に従う選択された対象ＥＴＥ関数を最適化することであり、そしてそれらのルートの中から、その対象ＥＴＥ関数の一番最適な値を有するルートを選ぶことである。このようにして、最適ルートとリンクパラメータとを併せて選ぶことができ、もう１つのＥＴＥ送信パラメータを最適化しながら、任意の所望のＥＴＥ制約パラメータを達成する。
【発明の効果】
【００５４】
本発明には、次のような利点がある。即ち、
＞マルチホップ・ネットワークにおけるリンク送信パラメータの効率的な割り当て／配分と、
＞所定の品質要件を満たしながら、利用できるネットワーク資源の最適化使用と、
＞マルチホップ・ルートに対する最適なＥＴＥ性能と、
＞効率的なマルチホップ・ルーティングと、
＞ルーティングとＥＴＥの状態に適応したリンク制御とを統合することと、
＞リンク適応と電力制御方策の改良と、
＞干渉の減少と、
＞ＳＡＲ（比吸収率）の減少と、
＞電池寿命の増大とである。
【００５５】
本発明で提供される他の利点は、本発明の実施例に関する以下の記載を読むときに認識される。
【００５６】
本発明は、その更なる目的およびその利点とともに、次の説明と添付図面とを合わせて参照することにより、最善の理解が得られるであろう。
【発明を実施するための最良の形態】
【００５７】
図面全体を通じて、同じ参照文字が対応するまたは同様の要素に対して使用される。
【００５８】
本発明をよりよく理解するために、ルーティングとリンク制御に対する従来技術の手法の簡単な解析から始めるのが有用であろう。
【００５９】
簡潔に言えば、従来技術によるマルチホップ・システムでは、あるルートは、累積リンク・コストを最小化することから決められる。このような状況で関連のある側面は、そのリンク・コストが、３つの基本的な（古典物理学から）相互に関連のある送信パラメータ：電力、時間、或いは、エネルギーのうちの少なくとも１つが、全てのリンクについて同じで、経路利得が可変として想定されるとの仮定のもとで決められるということである。特に、従来技術では、一般に、与えられた選択された基本的な送信パラメータを有するＥＴＥ（エンド・ツー・エンド）経路についての最適性を想定している。その従来技術の少なくとも２つの主な側面が改良される。
【００６０】
そのエンド・ツー・エンドのマルチホップ・ルートだけでなく、１つのリンク上のパケット送信をも特徴付けることのできる３つの基本的な物理尺度があるということが認識されている。それらは、電力Ｐ、時間Ｔ、及び、エネルギーＥである。それら３つは独立ではないが、その電力がそのパケット送信時間Ｔにわたって一定である場合、その関係は、Ｅ＝∫T0Ｐ（ｔ）ｄｔ、或いは、もっと簡単には、Ｅ＝Ｐ・Ｔに従う。なお、Ｅ＝Ｐ・Ｔは１つのリンクに対して直接成り立つが、そのＥＴＥマルチホップ・ルートに対しては、Ｅが関連のあるエネルギーの和であるので直接には成り立たない。
【００６１】
第一に、伝統的な従来技術の方法は、別の固定で与えられたリンクパラメータという仮定のもとで、リンク経路利得に基づいて各々のリンク・コストを決める。この例は、各々のリンクについては柔軟な電力設定と異なる経路損失を、しかし全てのリンク上では唯一の共通の送信継続時間を想定する最小電力ルーティングである。１つの基本的な物理リンクパラメータを固定することは、従来技術で行われているように、不必要に制限されたものであるということが認識されてきた。このことのために、先行技術の方式は、基本的な物理リンクパラメータのＥＴＥ（エンド・ツー・エンド）特性間の最適なトレードオフに達することができない。本発明の代表的な実施例として提案されるように、１つの例には、ＥＴＥエネルギー（或いは電力）とＥＴＥ送信継続時間との間のトレードオフがある。
【００６２】
ルーティングがマルチホップ・ネットワークにおいて従来行われている方法のために、１つの基本的な物理リンクパラメータを固定することにより、リンク速度適応と電力制御のような柔軟な（そして発明者らが最適と見なすような）リンク制御を実行する能力が不必要に制限されている。
【００６３】
第二に、あるルートに対する一定の品質、例えば、任意長Ｌのパケットに対する最大許容累積送信時間（または等価的に遅延）を保証し、そして同時にエネルギー（或いは電力）のような高価な資源の使用を最小化することが望ましい場合がある。さらに、実際に必要とされるよりも小さい遅延をもたらすためにより多くの資源（例えば、エネルギー或いは電力）を浪費するのは殆んど意味がない。従来技術は、あるＥＴＥ（エンド・ツー・エンド）の基本的な物理リンクパラメータ（例えば、エネルギー或いは電力）を、あるＥＴＥ制約（例えば、累積送信時間）のもとでの最小化することを扱っていない。それ故に、従来技術の方法は、必要とされるよりもより厳格な要件を満たすことにより高価な資源を不必要に浪費している。
【００６４】
上記の問題分析は、従来技術のルーティングでは、その３つの基本的で、そして相互に依存するリンク送信パラメータ（送信電力、送信時間および送信エネルギー）のうちの少なくとも１つが、全てのリンクにわたって一定であるということを明らかにしている。本発明に従う基本的な思想は、上記の基本的なリンク送信パラメータのいずれでもない、新しいパラメータを導入することであり、それはマルチホップ・ルートの全体に沿った全てのリンクに共通であって、リンク送信パラメータのより柔軟な割り当てまたは配分を可能にすることである。
【００６５】
図２は、本発明の好適な実施例に従うマルチホップ・ルートに対するリンク送信パラメータを制御するための基本的な方法を示すフローチャートである。ステップＳ１では、その共通パラメータが、好ましくはマルチホップ・ルート全体に対する与えられたエンド・ツー・エンド（ＥＴＥ）送信パラメータ制約に基づいて決められる。ステップＳ２では、それら３つの相互依存するリンク送信パラメータのセット、あるいはそれに代わるものが、各々の検討中のリンクに対して、その共通パラメータとローカルリンク特性に基づいて併せて配分される。このようにして、全ての３つのリンク送信パラメータは、各々のリンク送信パラメータがそのローカルリンク特性にも依存していると想定して、前記リンクが異なるリンク特性を有する場合、一般にそのルート上の少なくとも２つのリンク間で異なる。必要なら、その選択されたＥＴＥ制約に関連する適切なリンク情報が、そのルートに沿って収集され、その共通パラメータが、図２の破線で示されるように、調整される必要があるかどうかを決めるために用いられる。
【００６６】
結果的に、そのリンク送信パラメータは、そのリンク送信パラメータのうちの１つが全てのリンクにわたって一定でなければならないという制限を除去してきたので、より柔軟に割り当てられる。このようにして、従来技術とは対照的に、その基本的な物理リンク送信パラメータのいずれかと経路利得対雑音比との間で非線形関係を許容する。本発明はまた、ローカルリンクの最適化を取り扱うのではなく、むしろＥＴＥの状態に適応したリンク最適化を取り扱うので、より最適なリンク制御方策を提供する。また、その改良されたリンク制御方策の好都合な効果には、総干渉の減少、ＳＡＲの減少、及び電池寿命の増大がある。
【００６７】
より一般的に、その割り当てられた相互依存するリンク送信パラメータのセットには、次のものがある。即ち、
ａ）リンク送信エネルギー（Ｅi）を表わすパラメータと、
ｂ）リンク送信時間（Ｔi）、或いは、リンク送信帯域幅（Ｂi或いはＦi）、或いは、リンク送信符号語数（Ｃi）を表わすパラメータと、
ｃ）リンク送信電力（Ｐi）を表わすパラメータである。
【００６８】
Ｅ＝∫T0Ｐ（ｔ）ｄｔという関係、或いは、もっと簡単には簡単にＥ＝Ｐ・Ｔという関係から理解されるように、３つの相互依存するリンク送信パラメータのうちの２つが決められると、残りのリンク送信パラメータは、その３つのリンク送信パラメータの相互依存性により与えられる。実際に、その３つのリンク送信パラメータのうちの２つが、それぞれのリンクにわたって情報を送信する場合に使用するために明示的に決められる一方、第３のパラメータはその他の２つのパラメータにより与えられる。１つの例は、リンク送信電力および送信時間を明示的に決めることであり、ここで、その送信時間が、変調及び符号化方式（ＭＳＣ）に効率的に写像される送信速度というパラメータにより表わされる。
【００６９】
本発明のリンク送信パラメータの柔軟な割り当て／配分のために使用される共通パラメータは、例えば、ヒューリスティックな手法で、或いは、より体系的な手法を用いて決められることができる。
【００７０】
後者の場合、所定の対象エンド・ツー・エンド（ＥＴＥ）関数が、各々の検討中のリンクに対して、与えられたＥＴＥ制約を考慮して第１のリンク送信パラメータについて最適化されることが好ましい。ラグランジュ乗数法は、適切な最適化手法の１つの例であり、ここではその共通パラメータは、ラグランジュ乗数λを表わす。
【００７１】
都合よく、例えば、その３つの基本的な物理パラメータ、電力、時間／帯域幅／符号語数、及びエネルギーが考慮され、与えられたマルチホップ・ルートに対して、エンド・ツー・エンドの最適化のためのパラメータの１つを、それらパラメータのうちのもう１つの制約のもとで選択する。例えば、その対象ＥＴＥ関数は、次のＥＴＥ（エンド・ツー・エンド）送信パラメータのうちの１つを含むように選択される。即ち、
ａ）ＥＴＥ送信エネルギー（Ｅ）を表わすＥＴＥ送信パラメータと、
ｂ）ＥＴＥ送信時間（Ｔ）或いはＥＴＥ送信帯域幅（Ｂ或いはＦ）或いはＥＴＥ符号語数（Ｃ）を表わすＥＴＥ送信パラメータと、
ｃ）ＥＴＥ送信電力（Ｐ）を表わすＥＴＥ送信パラメータと
である。一方、そのエンド・ツー・エンド（ＥＴＥ）送信パラメータのうちのもう１つが、そのＥＴＥ制約として作用する。
【００７２】
対象ＥＴＥ関数とＥＴＥ制約の実際の選択は、全体の設計最終目標と性能目標に必然的に依存する。
【００７３】
リンクｉとｊについて、ｉ≠ｊでＧi≠Ｇj（或いは、現実にはその利得対雑音比が異なる）であって、そのルートに沿った全てのリンクに適用されると、この手法は、従来技術とは対照的に、全ての基本的なパラメータが異なるリンクについて異なる（そして実際そうであろう）という結果、即ち、Ｐi≠Ｐj、Ｔi≠Ｔj、及び、Ｅi≠Ｅjとなる。なお、時間Ｔ及びＴiが、Ｆ及びＦi（副搬送波の数）のような別の動的な資源パラメータに置換することができる。この代表的な方式のいくつかの特性は以下の通りである。
【００７４】
＞先の最適化がなされると、パラメータは、そのルートに沿った全てのリンクに共通なラグランジュ乗数λのようなパラメータの関数として導出される。
【００７５】
＞全てのパラメータ｛Ｐi、Ｅi、Ｔi｝は、Ｇiでは通常非線形である。
【００７６】
＞その最終結果は、与えられた経路に対する最適なＥＴＥ性能である。
【００７７】
言い換えると、代表的で好適な実施例では、本発明は１つの基本的な物理ＥＴＥ送信パラメータが最小化される一方、もう１つの基本的な物理ＥＴＥ送信パラメータが制約として作用するように、（電力、エネルギー、及び時間を表わす）基本的な物理リンク送信パラメータを併せて決める。
【００７８】
リンク当たり使用される符号語数は、総称として、リンク符号語消費量或いはリンク符号語使用量と呼ばれ、エンド・ツー・エンド（ＥＴＥ）の観点で使用される符号語数は、総称として、ＥＴＥ符号語消費量或いはＥＴＥ符号語使用量と呼ばれる。
【００７９】
次に、リンク送信パラメータの局所的な割当てのために関与するノードに分配される共通パラメータを集中的に決めることに基づく本発明の代表的な具現化に関して、本発明を説明する。しかし、共通パラメータの決定が分散化され、その結果、各々のノードで計算されることを妨げるものではないことを理解されたい。他方、全面的に集中化した手法が望まれるなら、リンク送信パラメータのセットだけでなくその共通パラメータが双方とも集中して計算されても良い。この場合、特定のノードに対して決められたリンク送信パラメータはそれから、実施のためにそのノードに転送される。
【００８０】
実際に、本発明では、集中度、非集中度、或いは分散運用の程度が異なって、実施されて良い。いずれの手法が好ましいかは、シナリオ、アーキテクチュアに関する好み、どの程度の速さでそのチャネルが変化するか、最適化の最終目標は何か（平均的なあるいは瞬間的な最適化）などに依存する。
【００８１】
図３は、本発明の好適な実施例に従うリンク送信パラメータを制御するための構成の代表的な具現化を示すブロック図である。基本的にその構成は、その共通パラメータを決める中央のいわゆる資源制御装置１０を備え、それはある意味で、そのマルチホップ・ネットワーク内のあるルート上でデータの送信に利用可能な資源の実際の配分と利用を制御する。その共通パラメータは、異なるリンクに対するリンク最適化に影響を与え、異なるリンクに対するリンク最適化を統合する。資源制御装置１０は、例えば、専用の制御ノードにおいて、あるいはそのルートに沿ったノードのうちの指定されたノードにおいて実装されると良い。この特定の例では、制御装置１０は、そのマルチホップ・ルートに沿った関連ノードにその共通パラメータを分配する。各ノード２０は、ローカル割当器２２とオプションとしてはローカル情報管理装置２４を備える。各ローカル割当器２２はその共通パラメータを受信し、基本的には、その共通パラメータとローカルリンク特性に基づいて、対応する相互依存するリンク送信パラメータのセットを配分する。情報管理装置２４は、適切な測定によりローカルリンク特性を決め、この情報を割当器２２に転送する。あるいは、ローカル割当器２２は、それ自身によりそのローカルリンク特性を決定するように構成されている。そのローカルリンク特性に加えて、情報管理装置２４はまた、制御装置１０において共通パラメータを適応できるようにするために、その選択されたＥＴＥ制約送信パラメータに関連したローカルリンク送信情報を決めることができる。各ノードで収集された情報はそれから、制御装置１０に転送され、その収集された情報に基づいて総ＥＴＥ送信パラメータ値を形成することが望ましい。オプションとして、割当器２２はまた、情報管理装置２４にその配分されたリンク送信パラメータを通知し、それからその収集された情報の一部を形成することが望ましい。総ＥＴＥ送信パラメータ値はそれから、そのＥＴＥ性能が受容できるかどうか、或いはその共通パラメータが再計算され、そのノードに再分配される必要があるかどうかを決めるために、与えられたＥＴＥ送信パラメータ制約と比較されると良い。
【００８２】
そのローカルリンク特性は、例えば、経路利得或いは経路利得対受信器雑音比を表わすかもしれず、その雑音項は他の送信からの干渉だけでなく受信器の内部および外部雑音からなるかもしれないということに留意しておく。
【００８３】
図４は、本発明の特に代表的な実施例に従うマルチホップ・ネットワークを示すブロック図である。ノード２０は、通常１つ以上のアンテナ要素を使用する送信モジュール（ＴＸ）と受信モジュール（ＲＸ）に分けられる。データパケットの送受信に関連して、そのパケットは通常、バッファで編成される。その送信モジュールは、割当器２２、変調及び符号化ユニットに基づく送信チェイン２５、電力増幅器２６、そしてスケジューラ２８を含むことが好ましい。その受信モジュールは、情報管理装置２４、復調及び復号化ユニット２７を基本的に含む。割当器２２は、その共通パラメータ、例えば、λに関する情報やローカルリンク情報Γiを受信し、そのリンク送信パラメータを、例えば、変調／符号化方式（ＭＣＳ）及び電力設定を制御することにより割当てる。必要であれば、割当器２２はまた、適切なリンク送信パラメータを配分する処理においてそのスケジューラ２８からの追加情報を用いても良い。その受信モジュールでは、情報管理装置２４は通常、そのローカルリンク特性を評価するための基礎に従来のチャネル評価を実行する。この情報、あるいはむしろそのリンク利得対雑音比は、チャネルの相互依存が想定されることができる場合、自身のノード内で使用されても良く、あるいはその代わりにその経路利得が測定されるノードに通信されても良い。
【００８４】
次に、最適化シナリオの特定の例に関して本発明をより詳細に説明する。基本的に、ここでの発明の代表的な進歩性のアプローチは、その基本的な物理パラメータである電力、エネルギー、及び時間のうちの１つで表現される制約として、ＥＴＥパラメータを最小化するためにＥＴＥパラメータを選択することである。その３つのパラメータである電力、時間（或いは、帯域幅或いは符号語数）、及びエネルギーのいずれかを、その他の２つの非選択のパラメータのうちのいずれか１つの制約のもとで最小化することが可能であるが、その主な焦点は、２、３の特に興味のあるケースに当てられるであろう。１つの興味のある例は、送信時間制約での最小エネルギーである。他の例には、エネルギー制約のもとでの最小送信時間と、送信時間制約のもとでの最小送信電力とを含む。送信継続時間が固定で、しかし、副搬送波／コード符号語使用量が柔軟なマルチキャリア／拡散設定では、別の最適化シナリオは、そのＥＴＥエネルギーを固定に保って、使用される副搬送波／符号語の総（ＥＴＥ）数を最小化することである（あるいは逆もまた同様）。
【００８５】
本発明は、特に、（８０２．１１のような）スロット化されていない速度制御のシステムに適用可能であるが、本発明はまた、（時間がスロット化されたシステムのような）資源の大きさが固定されたシステムに対する近似解を提供することもできる。加えて、述べてきたように、本発明は、電力、エネルギー、及び、送信周波数帯域／符号語使用量に基づいて基本的なリンク送信パラメータを有した、柔軟な帯域／符号語割り当てを可能とする時間が固定のシステムに使用できる。
【００８６】
第１の例として、送信時間制約のもとで推定最適ルートに対する総エネルギーを最小化するための定式化が導出される1。この最小化ではまた、その逆の状況、即ち、エネルギー制約のもとでルートに対する総送信時間を最小化する状況に対しても有効であることも示される。この解析は、基礎の役割を担うリンク／ノードの既知のルート（及び、それ故また既知の経路損失としても知られる）から始めて、そして続いてその拡張で、そのルーティング問題を解くのにも用いられる。その導出は、最初に今日の前方誤り訂正符号（ＦＥＣ）の性能として、シャノン容量限界2を用い、この限界に非常に近くなり、そして将来さらに改良されるであろう。その導出は、実際の変調／符号化方式に対するスループット対ＳＮＲ近似のための最適解の提示で補われる。
【００８７】
１  付属資料では、この導出手法は、エネルギー、メトリックよりはむしろ、総ＥＴＥ電力を最小化するために使用されることが示されている。
【００８８】
２  ターボ符号及び低密度パリティ検査符号（ＬＤＰＣ）がそのシャノン限界に近づいている。このことはシャノン限界の仮説の正当性を立証している。また、実際に、速度の限界となるセットが存在することがあり、その利用可能な速度内の全数検索が、ここで導出されたパラメータからの指針により実行される。
【００８９】
例−ＥＴＥ送信時間制約のもとでの最小ＥＴＥエネルギー（或いは、その逆）
ルートが一連のＮノードからなり、各々のリンクがｉで索引されるものと想定する。ここで使用されるモデルは、任意に電力と速度（その速度はその送信継続時間に影響する）が選択されるものである。その図解モデルが図５3に示されており、そのモデルは（８０２．１１などの）速度制御を備えたスロット化されていないシステムに適用可能であるが、本発明はこれに限定されるものではない。本発明は、例えば、スロット化されたチャネル・アクセスを用いる通信システムに対する近似最適解を見出すために使用される。それから、ノードの送信継続時間は、スロット数に最も近い数に丸められる。それ故、複数のスロットが潜在的に、各パケット送信に使用される。
【００９０】
３  １つのパケットを複数のセグメントに分割することもでき、それらを同じ経路に沿って同時に送ることができよう。このことは、遅延をさらにもっと低減することができるが、このことはマルチホップ・ネットワークで使用される標準的な手法ではない。さらに本発明により提案されている手法がこのために使用されると良い。
【００９１】
そのエンド・ツー・エンド送信時間は、次のようにシャノン速度の逆数の和として表記される。
【００９２】
2009500901.tif 000008
【００９３】
ここで、Ｌはそのパケットにおけるビット数、Γiはリンクｉの経路利得（Ｇi）対雑音電力（Ｗi＝ｋＴAmbＢi）比（ｋはボルツマン定数、ＴAmbはその周囲温度である）であり（なお、その雑音項に、干渉も追加される）、Ｐiは送信電力、Ｎはホップ数、そして、Ｂiはリンク帯域幅である。
【００９４】
通常、全てのＢiは同一であるが、例えば、異なるアクセス技術と、周波数帯域と、端末帯域幅能力との内、少なくともいずれかが考えられるなら、異なる帯域幅を許す。送信時間（或いは遅延）と同等に、体験された実効速度についてまた論じることができるかもしれない。さて、そのエンド・ツー・エンドのエネルギーは、ホップ当たりのそのエネルギー寄与、即ち、各ホップに対する送信継続時間の電力倍の和として表記され、それは以下の通りである。
【００９５】
2009500901.tif 000009
【００９６】
以下、最適化に十分であるビット当たりの送信時間とエネルギーを考え、即ち、そのパケット長パラメータＬを省略する。
【００９７】
ラグランジュ乗数法が、送信時間制約を用いながらそのエネルギーを最小化する問題に適用される。これは次のように表記される。
【００９８】
2009500901.tif 000010
【００９９】
ここで、Ｔ0は所望のエンド・ツー・エンド送信時間制約である。この式は、その偏微分を取って、そのＢiを除き、それからＰi値（異なるリンク）はラグランジュ乗数からの暗示的なもの以外は、直接互いには依存しないことに留意することにより整理される。その最適性条件は、以下の通りである。
【０１００】
2009500901.tif 000011
【０１０１】
ここで、左辺はｘi＝ΓiＰiについて事前に計算可能であり、右辺は定数で既知である。
【０１０２】
一旦Γiが分かると、λが選ばれ、所望のエンド・ツー・エンド送信時間制約が満たされるように、最適なリンク送信電力Ｐiを与える。そのリンク送信時間Ｔiは、Ｐiによりパラメータ化され、その結果、次のように計算される。
【０１０３】
2009500901.tif 000012
【０１０４】
一方、そのリンク送信エネルギーは、次により与えられる。
【０１０５】
2009500901.tif 000013
【０１０６】
その逆の問題、即ち、エネルギー制約を用いながら、その送信時間を最小化することは、実際に式（６）と式（７）に等価な定式化をもたらす。即ち、式（７）におけるλがその逆数で置換されるだけが必要であり、しかしλはちょうど任意の“定数”である。またなお、式（７）は送信されるビット数Ｌだけでなく、それ自身の（または他の）リンク帯域幅Ｂiにも依存しない。
【０１０７】
式（７）を解くいくつかの方法は、付属資料で説明されている。例えば、自明の代入とともにテーブル参照法が使用される。λの小さい値に対するいくつかの近似解がまたその付属資料で提示されている。
【０１０８】
ノードのルート性能
２０ノードのルート（直線に沿って一様に分布された）についての性能例が図６に与えられており、そして他のメトリクスと比較される。図６は、べき乗則伝搬損失モデルＧ∝Ｄ−αのもとで、ＥＴＥエネルギー対ＥＴＥ送信時間（遅延或いは継続時間）を示している。ここで、Ｇはチャネル利得、Ｄは距離、そして、αは伝搬定数(ここではα＝３．５）である。
【０１０９】
１．最適電力設定曲線には式（７）を用い、ここでλは可変である。
【０１１０】
２．電力曲線が固定されているケースでは、ＥＴＥ電力の総計は可変であるが、全てのリンクについて等しく分布しており、それ故にその継続時間のみが（異なる速度のため）全てのリンク間で異なる。なお、この電力設定方式は、電力が設定できない場合に、多くの想定されるマルチホップ・ネットワークでよく生じることである。
【０１１１】
３．継続時間曲線が固定されているケースでは、ＥＴＥ電力の総計は可変であるが、各リンクが同じＳＮＲを有するように分布しており、即ち、Ｐi∝Γi-βにおいてβ＝１である。それ故、その電力は全てのリンク間で異なるが、その継続時間は同一である。この電力設定方式は、マルチホップ・ネットワークでは非常にありふれた仮定を表現している。
【０１１２】
４．第１のヒューリスティック曲線のケースでは、ＥＴＥ電力の総計は可変であるが、各リンクがＰi∝Γi-β（ここで、β＝１／２）を有するように分布している。
【０１１３】
５．第２のヒューリスティック曲線のケースでは、ＥＴＥ電力の総計は可変であるが、各リンクがＰi∝Γi-β（ここで、β＝１／４）を有するように分布している。
【０１１４】
上記において、ケース１、４、及び５は、異なるリンクに対して電力も継続時間も何らかの特定の値に制約するものではない。
【０１１５】
いくつかの結論を図６から引き出すことができる。
【０１１６】
＞継続時間固定の送信は、拙い方策である。
【０１１７】
＞電力固定であるが柔軟な継続時間は、次善の方策であるが、少なくとも所定のルートに対してはそんなに悪くないように思われる。
【０１１８】
＞ケース４、β＝１／２の場合は、非常に低いＳＮＲでその最適電力設定に対する近似として良好である。さらに、β＝１／４のケース５は、ＳＮＲｓの広範囲にわたって良好である。
【０１１９】
更なる説明のために、その送信時間制約の最小エネルギー問題は、Γiのランダムな値が区間［０，１］に一様に分布しており、所望の送信時間が１０ｓ・Ｈｚ／ビットである４ホップのネットワークに対して解かれる。式（７）と式（４）とを用いて、以下のパラメータが決められる。
【０１２０】
【表１】
2009500901.tif 000014
【０１２１】
上の結果は、λ＝０．１６６０に対して得られたもので、ここでその全体のエネルギーは、１３．９８１５［Ｊ・Ｈｚ／ビット］である。
【０１２２】
上記の最適化に加えて、ＯＦＤＭのようなマルチキャリア伝送における注水定理を実行し、それからそのチャネルにおける周波数の選択性を説明しても良い。
【０１２３】
離散化
送信継続時間がタイムスロットの整数で現われるシナリオでは、任意の継続時間の送信が想定される状況とは反対に、その送信継続時間は丸められる必要がある。
【０１２４】
１つの可能性は、連続するケースで決められる送信継続時間をサポートするタイムスロット数に最も近くて最も大きい数に丸めることである。それを行うなかで、それに応じて、送信電力はエネルギー消費を最小にするように調整される。これを行うために、パケット長Ｌとスロット継続時間ＴSが知られる必要がある。それで、固定パケット長が仮定されるか、継続時間が各パケット長に依存してスロットの整数に動的に適合されるかのどちらかである。後者のケースに対して、その所要のスロット数は、Ｎi(Slots)＝［Ｌ（ＴSＢｌｏｇ2（１＋ΓiＰi））-1］として、計算される。このことから修正された電力は、
【０１２５】
2009500901.tif 000015
【０１２６】
ということになる。
【０１２７】
なお、電力もまた離散値を許容しうるだけなので、実際にはタイムスロット数と電力レベルが離散空間で探索されるかもしれない。
【０１２８】
シャノン限界が上記のように用いられているが、実際には別個のセットの変調／符号化方式が使用されると良い。これはまた、丸め処理が考慮されても良い。
【０１２９】
現実的な変調／符号化方式を用いる最適化の例
実際的な速度が、シャノン速度より小さい一定の要因としてモデル化されることができない場合には、異なる変調／符号化方式（ＭＣＳｓ）に対する逆スループット性能曲線（おそらくは再送効果さえも考慮に入れて）が、シャノン速度の代わりに活用される。全ての性能曲線に対する最大スループットの逆数を、関数ｆ（ΓiＰi）として表わすものと仮定する。それから、これをラグランジュ乗数法で使用することができる。
【０１３０】
2009500901.tif 000016
【０１３１】
これは、次のようになる。
【０１３２】
2009500901.tif 000017
【０１３３】
上式の左辺は、そのシステムで使用されるＭＣＳ方式に対して、事前に計算され、それから、式（１１）の解をテーブル参照とともに使用される。
【０１３４】
実際のＭＣＳｓに対して、その導関数は、ｆ（ΓiＰi）＝ｆ（ＳＮＲ）を示している図７から気付くように解決が難しく、図７はいくつかのＭＣＳｓ（４ＱＡＭから６４ＱＡＭを用いたターボ符号化で、そして再送を説明している）の最大スループットである。しかしながら、（点線の曲線で示されている）近似が、ＳＮＲ区間［ＳＮＲlow，ＳＮＲhigh］にわたって定義される非ゼロ（non-zero）で、連続的な“導関数”を持つという条件で使用される。ＳＮＲlow以下で、その経路は、送信時間が無限大になるので実行不可能である。ＳＮＲhighを超えると、その送信時間は上限があり、ＳＮＲhighより高いＳＮＲｓは考慮される必要がない。それ故に、
【０１３５】
2009500901.tif 000018
【０１３６】
2009500901.tif 000019
【０１３７】
2009500901.tif 000020
【０１３８】
例−ＥＴＥ送信時間制約のもとでの最小ＥＴＥ電力（或いは、その逆）
エンド・ツー・エンド送信時間は、式（４）にあるようにシャノン速度の逆数の和として表記される。エンド・ツー・エンド電力は、ホップ当たりの電力寄与の和として表記される。
【０１３９】
2009500901.tif 000021
【０１４０】
ラグランジュ乗数法が、送信時間制約を用いながら、その電力を最小化する問題に適用される。これは次のように表記される。
【０１４１】
2009500901.tif 000022
【０１４２】
これは若干整理でき、その結果は以下のようになる。
【０１４３】
2009500901.tif 000023
【０１４４】
この方程式は未知の電力Ｐiについて解かれる。それから、上記の方程式は、電力と速度設定に関するエネルギー最小化に対するものと同じように用いられる（あとで明らかになるようにルーティングも同様である）。
【０１４５】
例−ＥＴＥ周波数／符号語資源制約のもとでの最小ＥＴＥエネルギー（或いは、その逆）
この節では、同じリンク最適化方策が、その送信時間（ＢＷ固定で）を使用帯域幅／符号語資源量（送信時間固定で）で置換した場合にも適用可能であることを示す。このことに対する動機は、そのモデルがマルチキャリア／拡散スペクトラム通信（例えば、ＯＦＤＭ／ＣＤＭＡ）に対しても有用であること、即ち、ＯＦＤＭ／ＣＤＭＡ符号に対する時間が固定される一方、ＯＦＤＭ／ＣＤＭＡにおける帯域幅／符号語資源の量を適応的に選択できることを示すことである。次に、その品質がホップｉで全てのＯＦＤＭ副搬送波に対して（少なくとも近似的に）等しいことを仮定する。使用される副搬送波の量は、以下のように表記される。
【０１４６】
2009500901.tif 000024
【０１４７】
ここで、Ｌはそのパケット内のビット数、Γi(sc)はリンクｉに対する経路利得Ｇi対雑音電力Ｗi＝ｋＴAmbＢi(sc)の比（ｋはボルツマン定数、ＴAmbはその周囲温度）であり（なお、干渉もその雑音項に追加される）、Ｐi(Sc)は副搬送波当たりの送信電力、Ｎはホップ数、Ｂi(Sc)はリンクの副搬送波の帯域幅（通常、全てのＢi(Sc)は異なるｉに対して同一であるが、例えば、異なるアクセス技術、周波数帯域、及び端末の帯域幅能力が考慮さえされるなら、異なる帯域幅を許容する）であり、Ｔ(Symb)は１つの（ＯＦＤＭ）シンボルの継続時間である。そのＥＴＥエネルギーは以下の通りである。
【０１４８】
2009500901.tif 000025
【０１４９】
前と同じように、ラグランジュ乗数法が適用され、最適性基準の形式は、いくつかのささいな定数を除けば式（７）と同一である。
【０１５０】
式（１８）と式（１９）とはＯＦＤＭに対して導出されるが、同じ方程式が、直交語を用いたＣＤＭＡに対して、そして、高次の変調（例えば、４，１６，６４．．．ＱＡＭ）及び可変前方誤り訂正符号速度が、各シンボルを１つの符号語で拡散するときに使用されるなら成り立つ。もっと正確には、リンク当たり要求される符号語数は、Ｃi＝Ｌ／（Ｂ(C)ｌｏｇ2（１＋Γi(C)Ｐi(C)））であり、ここで（Ｃ）は、符号語に関心があることを示している。同様のやり方で、リンク当たりのエネルギー項は、Ｅi＝Ｐi(C)Ｌ／（Ｂ(C)ｌｏｇ2（１＋Γi(C)Ｐi(C)））である。前と同様に、ラグランジュ乗数法が適用され、最適性基準の形式は、いくつかのささいな定数を除けば式（７）と同一である。
【０１５１】
例−プロトコルを備えたＥＴＥの状態に適応したリンク制御
この節では、ノード／リンクについての所定の経路に対するリンク最適性条件式（７）がどのように代表的な実施例で使用されるのかが検討される。
【０１５２】
まず、経路がどのように与えられることができるかについて手短にコメントする。経路を見つける合理的でヒューリスティックな手法は、最短経路ルーティングを使用することができるし、あるいはその代わりに、いくつかの選ばれたメトリクス、例えば、エネルギー、電力、或いは送信継続時間で、後で説明されるように、統合的なルート選択を用いる提案方法を使用することもできる。最短経路ルーティングがエネルギーというメトリクスで使用されるなら、その問題はリンク当たりの雑音対利得比の最小和を提示する経路を見出すことへと悪化することである。
【０１５３】
その思想は、程度は異なるが集中化された、非集中化された、或いは、分散された運用で実施できよう。いずれの手法が好ましいかは、シナリオ、アーキテクチュアに関する好み、どの程度の速さでそのチャネルが変化するか（静止、緩やかに変化する、移動度による見通しチャネル、高速フェージング）、最適化の最終目標は何か（平均的な、或いは瞬間的な最適化）などに依存する。
【０１５４】
図８では、代表的なフローチャートがその基本的な動作を示している。ルートが存在すると仮定する（Ｓ１１）と、他のルートが使用にはより最適かどうかが調べられ、そうであれば新しいルートが選ばれる。それら２つのステップ（Ｓ１２、Ｓ１３）はオプション（点線で示されている）であるが、ノードが移動体であるか、あるいはノード間のチャネルが他の理由のために変化する場合には含まれることが好ましい。ＥＴＥ性能が受け入れ可能なものか、あるいは再調整される必要があるかどうかのチェックがなされる（Ｓ１４）。それがＯＫ（Ｙ）であれば、その処理は、データが転送されるＳ１８で継続することが好ましい。ステップＳ１９では、そのＥＴＥ性能が特徴付けられ、λnの新しい値をその後に処理するために収集される。次に、そのルートが更新される必要があるかどうかがもう一度調べられると良い。しかしながら、そのＥＴＥ性能がステップＳ１４でＯＫでない（Ｎ）場合、全てのリンクに対する共通パラメータλnが再計算され（Ｓ１５）、目標のＥＴＥ基準をよりよく満たすように更新される。その新しいλnがそのルートに沿ったそのノードに分配され（Ｓ１６）、それから最適化された送信パラメータを設定する場合、各ノードにより使用される（Ｓ１７）。それらのパラメータはそれから、パケット送信のための粗い初期設定として少なくとも使用される。そのチャネル利得対雑音比が緩やかに変化する場合、λnの正確な最適値がその経路全体に対して使用されるであろう。しかしながら、そのチャネルが、新しい値が分配されることができるよりも急速に変化する場合、λnは、平均ＥＴＥ性能が所望の目標を満たすように決められることが好ましい。この“平均”型の最適化は、ＥＴＥ性能パラメータ（例えば、送信時間とエネルギー）の変動性をもたらす結果になる一方、最小化されるパラメータとその“制約”パラメータとの間の最適なトレードオフ曲線に依然として追随する。もしデータがあれば、その新しいパラメータとともに、ここで（あるいは後で）転送される（Ｓ１８）。最後のステップ（Ｓ１９）として、ＥＴＥ性能が特徴付けられ、λnの新しい値を処理するために収集される。
【０１５５】
ＥＴＥの状態に適応したリンク制御方式（例えば、リンク適応と電力制御の統合）のあり得る代表的な実施例を説明するだけのために、図９におけるルートを考える。ここで、ＥＴＥ性能情報は、そのルートに沿って収集される。例えば、λn-1の値が与えられると、総ＥＴＥ制約パラメータ（そして、潜在的には、新しい改善されたλnを容易に決めやすくする他の情報）が収集され、意思決定ノードに転送される。例えば、そのノードを図９のνNとする。そのノードνNは報告されたＥＴＥ性能を評価し、それを所望の目標基準と比較する。これに基づいて、新しい値λnが決められ、そのルートに沿ったノードに分配される。ＥＴＥ性能情報は、データパケットの送信とは独立に収集されても良いし、あるいはデータパケットに便乗させることもできる。（例えば、ＥＴＥ送信時間のような）主なＥＴＥ制約パラメータを報告することに加えて、（例えば、ＥＴＥエネルギーのような）最小化パラメータに関するＥＴＥ性能を特徴付けることが望ましい場合がある。
【０１５６】
最小化パラメータとしてＥＴＥエネルギーを用いると、別の実施例は累積リンク雑音対利得比（それは、最小の達成可能なＥＴＥエネルギーの尺度）を報告することに関係する。この別の実施例では、そのＥＴＥエネルギーが最小の達成可能なＥＴＥエネルギーより少量高めるようにすることができるλの値を選ぶように目指すと良い。このようにして、過度の遅延が避けられることを保証しながら、最小エネルギーに近い動作でのよい均衡をとる。
【０１５７】
その制御ループも、図９に示されている。ＥＴＥ情報がそのルートに沿って収集され、ノードで処理され、それからλの値が、その経路に沿った、関連のある、通常は全ての、ノードに配信されることが示されている。各ノードはその利得対雑音比Γiを決めることも理解される。各ノードはそれから、これら２つの入力、λとΓiを用いてその送信パラメータを調整する。ある意味では、Γiを見つけることは開ループ動作である。それ故、各リンクが潜在的には閉ループ型の動作で補われることもできると想像できるかもしれない。
【０１５８】
例−ルーティングへの拡張
上記のリンク制御メカニズム、即ち、与えられた経路に対するＥＴＥ制約のもとでのＥＴＥの最適化に基づいて、経路の全セットが選ばれ、最適化され、評価される。ＥＴＥ制約の各値に対して、ＥＴＥ最適化パラメータの最小のものを提示する経路が選ばれる。
【０１５９】
リンク制御のみに対しては、１つの経路が与えられるものと仮定されていた。ルーティングとリンク制御とを統合する拡張では、しかしながら、ＥＴＥ性能を異なるパラメータ範囲内で最適化する経路のセットを探索することが提案されていて、例えば、第１の経路は最小のＥＴＥエネルギーをある送信継続時間範囲で提示することができる一方、第２の経路は最小のＥＴＥエネルギーを別の送信継続時間範囲で提示しており、図１０で模式的に図示されているように、図１０ではＥＴＥエネルギー対ＥＴＥ遅延の代表的なケースを示している。図１０に関して、経路１は、ＥＴＥ制約がＴ１として選ばれると、最小のＥＴＥエネルギーを提供すると理解される。しかしながら、そのＥＴＥ制約がＴ２であるなら、経路２が最小のＥＴＥエネルギーを提供する。
【０１６０】
限られた数のノードと固定ノードとの内の少なくともいずれかに対しては、その可能な経路内の全数検索が実現できる場合がある。各々の経路に対して、パラメータλが性能曲線、例えば、ＥＴＥエネルギー対ＥＴＥ遅延が生成されるように走査される。その最小エネルギー対遅延がそのとき、全ての曲線に対して取られる。これにより、別のパラメータを最小化しながら、何らかの所望なＥＴＥ制約パラメータを達成する最適ルートとリンクパラメータを併せて選択することが可能になる。理想的には、これはその前提条件のもとで、見出され得る一番最適な解である。
【０１６１】
例−２ホップ中継
２ホップ中継は、次世代セルラシステムに対して、特に、高速データ通信向けのサービスエリア拡大を促進するものとして、興味深い解である。
【０１６２】
なお、その中継は、移動局からばかりでなく基地局からの利得にも（単に、送信、ビーコン、或いは、プローブ信号が偶然聞こえることにより）注意が払われる。それ故、その中継をその送信パラメータ設定を決めるノードとして使用するのは、道理に適っている。これまでに導出されてきた方程式、例えば、式（４）、（５）、及び（７）のバージョンが使用されると良い。その制御ループはここでも関心もあることであり、その中継ノード内にルーツ(root)が置かれることが好ましい。
【０１６３】
上記の実施例は例として単に与えられたものであり、本発明はそれによって限定されるものではないことを理解されたい。ここで開示され、ここで特許請求された基幹を構成する原理を保持する更なる修正、変更、及び改良は、本発明の範囲内にある。
【０１６４】
付属資料
この付属資料では、方程式（７）に対する様々な代表的な解について詳述する。
【０１６５】
ＳＮＲ範囲全体にわたる厳密解
ここでは、式（７）、（５）、及び（４）の解法／計算法に関する短い節が続く。式（７）の形式の方程式が、各々のリンク／ホップｉに対して１つで、Ｎ個ある。その課題は、式（４）の送信時間制約が満たされるように、電力Ｐiを与えるλを選ぶことである。これは、連立非線形方程式を解くことに関係する。非線形連立方程式を解く既存の方法が、この目的のために使用されても良く、例えば、二分法、ニュートン・ラプソン法等がある。関係している関数は、式（４）の送信時間Ｔ、式（５）のエネルギーＥ、及び電力Ｐiが完全に単調にλの増加関数であるという意味において、（周到な吟味では）、その挙動が良好であると見られる。
【０１６６】
式(７)をオフラインで解き、そしてテーブル参照法を使用することも可能で、たぶんそれが好ましい。２つのダミーパラメータ、ｘi、ｙiが与えられると、（１＋ｘi）ｌｎ（１＋ｘi）−ｘi＝ｙiをｘiについて解くことにより、テーブルが生成される。各ノードは、Γiとλを知り、それから、ｘi＝ΓiＰi、ｙi＝Γiλ、及び事前に計算されたテーブルからＰiを決めることができる。グラフを使って、リンク当たりの電力、エネルギー、及び送信時間が、例えば、図１１に示されている曲線から導出される。図１１では、ｆ（ｘ）＝（１＋ｘ）ｌｎ（１＋ｘ）−ｘ、Ｅ（ｘ）＝ｘ／ｌｏｇ2（１＋ｘ）、及びＴ（ｘ）＝１／ｌｏｇ2（１＋ｘ）が示されており、ここで、ｘi＝ΓiＰi、ｙi＝Γiλ、及びＥi＝Ｅ（ｘi(opt)）Γi-1Ｂi-1、Ｔi＝Ｔ（ｘi(opt)）Ｂi-1、Ｐi＝ｘi(opt)Γi-1である。それらの曲線は、そのテーブルの基礎として使用される。そのテーブルにおける各点間の補間は、その曲線の形が滑らかなので容易だろう。
【０１６７】
低ＳＮＲ範囲における近似解
式（７）は最適な電力設定をもたらす一方、その低ＳＮＲ範囲内、即ち、ΓiＰiが小さい場合、近似最適化を検討することは有益である。このことは、式（７）の対数部を、ΓiＰiを変数として、次の式に従ってテイラー展開することにより達成される。
【０１６８】
2009500901.tif 000026
【０１６９】
その結果は、電力がそのチャネル利得に逆平方根として関連していることを示す。
【０１７０】
2009500901.tif 000027
【０１７１】
これは、電力の指数が式（７）のヒューリスティックな解として調べるには興味深いことを示唆している。Ｐi∝Γi-βでβ＝｛１／２，．．．，１／４｝であることは非常に良い結果をもたらすことが実験的に検証されている。図６を参照をされたい。特に、β＝１／２は、低いＳＮＲｓで、漸近的に最適なものであるが、β＝｛１／３，．．．，１/４｝は、式(７)の非線形性が効いている場合、高ＳＮＲｓで良好である。
【０１７２】
低ＳＮＲで、式（２１）が妥当であるところでは、その継続時間とエネルギーは、以下で近似される。
【０１７３】
2009500901.tif 000028
【０１７４】
2009500901.tif 000029
【図面の簡単な説明】
【０１７５】
【図１Ａ】ルート決定中に生成される伝統的な経路ツリーの例を説明した図である。
【図１Ｂ】発信元ノードと宛先ノード間でのパケット転送を説明する図である。
【図２】本発明の好適な実施例に従うマルチホップ・ルートに対するリンク送信パラメータを制御するための基本的な方法を示すフローチャートである。
【図３】本発明の好適な実施例に従うリンク送信パラメータを制御するための装置の典型的な具現化のブロック図である。
【図４】本発明の特に代表的な実施例に従うマルチホップ・ネットワークノードの概略ブロック図である。
【図５】予め決められたルートに対するシステムモデルを説明する図である。
【図６】ＥＴＥエネルギー対ＥＴＥ送信時間の性能の例を説明する図である。
【図７】最大スループット対ＳＮＲを説明する図である。
【図８】本発明の特に代表的な実施例に従う基本的な動作を説明するフローチャートである。
【図９】本発明の代表的な具現化に従うマルチホップ・ルートと関連する制御ループを説明する図である。
【図１０】２つの異なる経路（ルート）に対するＥＴＥエネルギー対ＥＴＥ送信時間の性能曲線を説明する図である。
【図１１】共通パラメータとローカルリンク特性を考慮したリンクあたりの電力、エネルギー、及び送信時間の解のグラフ表示である。
【図１Ａ】
2009500901.tif 000030
【図１Ｂ】
2009500901.tif 000031
【図２】
2009500901.tif 000032
【図３】
2009500901.tif 000033
【図４】
2009500901.tif 000034
【図５】
2009500901.tif 000035
【図６】
2009500901.tif 000036
【図７】
2009500901.tif 000037
【図８】
2009500901.tif 000038
【図９】
2009500901.tif 000039
【図１０】
2009500901.tif 000040
【図１１】
2009500901.tif 000041
【手続補正書】
【提出日】平成20年6月16日(2008.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１５
【補正方法】変更
【補正の内容】
【請求項１５】
前記第１のリンク送信パラメータはリンク送信電力であり、
前記第２のリンク送信パラメータはリンク送信速度であり、
統合リンク速度適合とリンク電力制御とは、前記決定された第１と第２のリンク送信パラメータに基づいて実行されることを特徴とする請求項５に記載の方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２１
【補正方法】変更
【補正の内容】
【請求項２１】
マルチホップ・ネットワークにおけるルーティングの方法であって、
多数の可能なルートの各々に対して、全てのルートに共通な与えられたＥＴＥ送信パラメータ制約に従い、各ルートにおける各リンクに関して、次の３つの相互依存のリンク送信パラメータである
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
の内の１つに関して、与えられた対象エンド・ツー・エンド（ＥＴＥ）関数を
夫々がローカルリンク特性にも依存した３つの相互依存のリンク送信パラメータ全てが、前記リンクが異なるリンク特性をもつときに、一般には前記ルート上での少なくとも２つのリンクの間で異なるように考慮しているルートに沿った全てのリンクに共通のパラメータにより最適化するという手順を実行することを特徴とする方法。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項３６
【補正方法】変更
【補正の内容】
【請求項３６】
前記第１のリンク送信パラメータはリンク送信電力であり、
前記第２のリンク送信パラメータはリンク送信速度であり、
前記装置はさらに、統合リンク速度適合とリンク電力制御とを、前記決定された第１と第２のリンク送信パラメータに基づいて実行する手段を有することを特徴とする請求項２６に記載の装置。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項４４
【補正方法】変更
【補正の内容】
【請求項４４】
マルチホップ・ネットワークにおけるルーティングの装置であって、
多数の可能なルートの各々に対して、全てのルートに共通な与えられたＥＴＥ送信パラメータ制約に従い、各ルートにおける各リンクに関して、次の３つの相互依存のリンク送信パラメータである
リンク送信エネルギーを表わすリンク送信パラメータ、
リンク送信時間、又は、リンク送信帯域幅、又は、リンク送信符号語
を表わすリンク送信パラメータ、
リンク送信電力を表わすリンク送信パラメータ
の内の１つに関して、与えられた対象エンド・ツー・エンド（ＥＴＥ）関数を夫々がローカルリンク特性にも依存した３つの相互依存のリンク送信パラメータ全てが、前記リンクが異なるリンク特性をもつときに、一般には前記ルート上での少なくとも２つのリンクの間で異なるように考慮しているルートに沿った全てのリンクに共通のパラメータにより最適化する手段と、
前記対象ＥＴＥ関数の最適化値をもつルートを前記ルートの中から選択する手段とを有することを特徴とする装置。
【国際調査報告】
2009500901.tif 000042
2009500901.tif 000043
2009500901.tif 000044