(57)【要約】【課題】パケットを無線ネットワークの中継ノードを介して発信元ノードから宛先ノードに送信する方法およびシステムを得ることを目的とする。【解決手段】パケットは、無線ネットワークの発信元ノードから中継ノードルートに沿って宛先ノードに送信される。パケットのエネルギーは、パケットの複数のバージョンを記憶することによって、宛先ノードでのみ蓄積される。パケットは、蓄積されたエネルギーを使用して、宛先ノードで複号化される。【選択図】図１
2008042911.tif 000002
【特許請求の範囲】
【請求項１】
パケットを無線ネットワークの中継ノードを介して発信元ノードから宛先ノードに送信する方法であって、
パケットを、無線ネットワークの発信元ノードから中継ノードのルートに沿って宛先ノードに送信するステップと、
前記宛先ノードで、前記パケットの複数のバージョンを受信するステップと、
前記宛先ノードでのみ、前記パケットの前記複数のバージョンを記憶するステップと、
前記宛先ノードにおいて、受信された前記パケットの前記複数のバージョンを使用して該パケットを復号化するステップと
を含むパケットを無線ネットワークの中継ノードを介して発信元ノードから宛先ノードに送信する方法。
【請求項２】
前記宛先ノードは、複数のノードから前記パケットの前記複数のバージョンを受信する請求項１に記載の方法。
【請求項３】
前記パケットの前記複数のバージョンは、該パケットのコピーである請求項１に記載の方法。
【請求項４】
前記ノードは、少なくとも１つのアンテナを使用する請求項１に記載の方法。
【請求項５】
前記発信元ノードから前記宛先ノードへのエネルギー効率的なルートを漸進的に求めることをさらに含む請求項１に記載の方法。
【請求項６】
前記エネルギー効率的なルートは、各ノードで利用可能なローカルチャネル状態情報のみに基づく請求項５に記載の方法。
【請求項７】
前記ノードに送信電力を設定することをさらに含む請求項５に記載の方法。
【請求項８】
前記設定することは分散的および漸進的に行われる請求項７に記載の方法。
【請求項９】
前記パケットの前記複数のバージョンのエネルギーは、前記宛先ノードにより蓄積される請求項１に記載の方法。
【請求項１０】
前記パケットの復号化は、受信された前記パケットの前記複数のバージョンの蓄積エネルギーを使用する請求項１に記載の方法。
【請求項１１】
前記パケットは、前記パケットの前記複数のバージョンの前記蓄積エネルギーが所定の閾値以上になった後に復号化される請求項１０に記載の方法。
【請求項１２】
前記所定の閾値は、前記パケットの送信に使用される変調および符号化によって決まる請求項１１に記載の方法。
【請求項１３】
巡回冗長検査が前記パケットに挿入されて、該パケットが正しく符号化されているか否かが判断される請求項１に記載の方法。
【請求項１４】
前記ルートに沿って総消費電力を低減するように中継ノードを前記ルートに追加することをさらに含む請求項１に記載の方法。
【請求項１５】
追加される前記中継ノードは、前記ルートに沿ってノード間に直列に挿入される請求項１に記載の方法。
【請求項１６】
前記パケットは、潜在的な中継ノードにより受信される請求項１に記載の方法。
【請求項１７】
前記潜在的な中継ノードが前記ルートに沿った中継ノードとして機能できることを示す協働要求パケットが、前記潜在的な中継ノードにより送信される請求項１６に記載の方法。
【請求項１８】
前記協働要求パケットを受信する特定のノードが、前記潜在的な中継ノードを使用するか否かを判断する請求項１６に記載の方法。
【請求項１９】
前記発信元ノードから前記宛先ノードへの前記ルートを求めることと、
前記パケットを前記ルートに沿って送信する間の消費エネルギーを低減するように、該ルートに中継ノードを漸進的に追加することと
をさらに含む請求項１に記載の方法。
【請求項２０】
前記消費エネルギーを低減するように、前記発信元ノードから前記宛先ノードへの前記ルートを漸進的に更新することをさらに含む請求項１に記載の方法。
【請求項２１】
特定の中継ノードは、特定のパケットを前記宛先ノードに送信することにより前記宛先ノードに蓄積されるエネルギーの割合を記録する請求項１に記載の方法。
【請求項２２】
前記記録されたエネルギーの割合を前記ルートに沿って次のノードに転送することをさらに含む請求項２１に記載の方法。
【請求項２３】
特定の中継ノードは、該特定の中継ノードから前記宛先ノードへの前記ルートに沿ったノードにより特定のパケットを該宛先ノードに送信することにより該宛先ノードに蓄積されるエネルギーの割合を記録する請求項１に記載の方法。
【請求項２４】
パケットを無線ネットワークの中継ノードを介して発信元ノードから宛先ノードに送信するシステムであって、
パケットを送信するように構成される発信元ノードと、
ただ前記パケットを受信して再送信するように構成される複数の中継ノードと、
前記パケットの複数のバージョンを受信するように構成される宛先ノードと
を備え、
前記宛先ノードは、該宛先ノードのみが、受信された前記パケットの前記複数のバージョンを記憶するように構成され、受信された該パケットの該複数のバージョンを使用して該パケットを復号化する手段を含む
パケットを無線ネットワークの中継ノードを介して発信元ノードから宛先ノードに送信するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはパケットのマルチホップ伝送を用いる無線中継ネットワークに関し、特に、このような無線中継ネットワークでのエネルギー蓄積に関する。
【背景技術】
【０００２】
無線中継ネットワーク
無線中継ネットワークでは、発信元ノードが、複数のホップ、すなわち、ルートを使用して中継ノードを介してパケットを宛先ノードに送信する。このような多くのネットワークでは、ノードは、小型で複雑性の低いセンサノードである。このようなノードの計算資源、メモリ資源、および電力資源は、大幅に制限されている。したがって、このような資源を可能な限り節減することが重要である。
【０００３】
マルチホップルーティング
マルチホップルーティングが、多くの場合、ユニキャストパケットの送出に必要な総エネルギーを低減するために、従来の無線中継ネットワークに使用される（J. Li, D. Cordes、およびJ. Zhang著「Power-aware routing protocols in ad hoc wireless networks」（IEEE Wireless Commun. Magazine, pp. 69-81, Dec. 2005）並びにA. MichailおよびA. Ephremides著「Energy efficient routing for connection-oriented traffic in ad hoc wireless networks」（Proc. IEEE Int. Symp. Personal, Indoor, Mobile Radio Commun., pp. 762-66, Sept. 2000））。
【０００４】
こういったネットワークでは、発信元は、所定のエネルギー効率的なルートに沿って１つまたは複数の中間中継を通して宛先にパケットを送信する。パケットを中継または宛先で首尾よく復号化することができない場合、パケットは、破棄され、再送信が必要になる（J. E. Wieselthier、G. D. Nguyen, およびA. Ephremides著「On the construction of energy efficient broadcast and multicast trees in wireless networks」（Proc. IEEE INFOCOM, Mar. 2000）、A. E. Khandani、J. Abounadi、E. Modiano、およびL. Zheng著「Cooperative routing in wireless networks」（Proc. Allerton Conf. on Commun., Contr. and Computing, May 2003）、A. S. AhluwaliaおよびE. H. Modiano著「On the complexity and distributed construction of energy efficient broadcast trees in wireless ad hoc networks」（IEEE Trans. Wireless Commun., vol. 4, no.5, 2005）、並びにJ. Cartigny、D. Simplot、およびI. Stojmenovi'c著「Localized minimum-energy broadcasting in ad-hoc networks」（Proc, IEEE INFOCOM, Apr. 2003））。これらの手法は、破損したパケットが完全に破棄され、それから先は、使用されないため、エネルギー効率的ではない。
【０００５】
エネルギー蓄積
エネルギー蓄積ルーティングは、無線中継ネットワークのエネルギー効率を向上させる（I. MaricおよびR. D. Yates著「Efficient multihop broadcast for wideband systems」（DIMACS Workshop on Signal Processing for Wireless Transmission, Oct. 2002）、M. Agarwal、J. H. Cho、L. Gao、およびJ. Wu著「Energy efficient broadcast in wireless ad hoc networks with hitch-hiking」（Proc. IEEE INFOCOM, March 2004）（両方とも参照により本明細書に援用される））。エネルギー蓄積ルーティングでは、中継は、復号化するには微弱すぎるパケットの受信信号を記憶し、記憶されている信号を、後に受信した同じパケットの他の信号と組み合わせる。パケットを首尾よく復号化した後、中継は、そのパケットを宛先に向けてブロードキャストする。しかし、こういった方法は、ユニキャストパケットではなく、ブロードキャストパケットに対して設計されている。
【０００６】
現世代および次世代の無線ネットワークは、エネルギー蓄積を実施するメカニズムを整えているが、エネルギー蓄積をあらゆるノードのそれぞれで実施するには、資源が消費される。既知のエネルギー蓄積技法は、あらゆるノードが、パケットを首尾よく復号化できるようになるまで、ネットワーク内の複数のノードから送信される受信パケットのあらゆるコピーのそれぞれの信号を記憶するという理想的な前提の下で機能する。通常、発信元は、次々と複数のパケットを送信する。この場合、中継は、パケットをすでに復号化している可能性のあるすべてのノードにより送信される１つではなく多くのパケットの複数の「ソフト」コピーを記憶する必要がある。
【０００７】
事態をさらに悪化させることとして、中継は、異なる発信元の中継として機能することができるため、中継の記録作業量は、ネットワーク内の「伝送中」の別個のパケットの総数に比例する。中継は、パケットを発信元から宛先に送信することにより生じる恩恵を直接は受けないため、相当量の資源をエネルギー蓄積に費やすことの正当化は、難しい。さらに、多くの中継ノードを有する無線ネットワークで最適なエネルギー蓄積を見つけ、それと併せてルートに沿ったノードの送信電力レベルを判断することは、非常に難しい。
【０００８】
ユニキャスト伝送のための最小エネルギー蓄積ルーティング（ＭＥＡＲ）が、ＮＰ完全な問題であることが分かっている（J. Chen、L. Jia、X. Liu, G. Noubir、およびR. Sundaram著「Minimum energy accumulative routing in wireless networks」（Proc. IEEE INFOCOM, 2005））。したがって、スケーラブルな最適メカニズムは、不可能である。Chen他のＭＥＡＲは、全エネルギー蓄積を意図しており、完全に中央化される。すなわち、あらゆるノードがネットワーク内のすべてのノード間のすべてのリンクの状態を認識する必要がある。
【０００９】
別の技法は、マルチキャストパケットにエネルギー蓄積ルーティングを実施する（I. MaricおよびR. D. Yates著「Cooperative multicast for maximum network lifetime」（IEEE J. Select. Areas Commun., vol. 23, pp. 127-135, Jan. 2005））。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の実施の形態は、中継ノードが協働して、ユニキャストパケットを発信元ノードから宛先ノードに送信する際に消費される総エネルギーを最小に抑える無線ネットワークを提供する。
【課題を解決するための手段】
【００１１】
この実施の形態は、漸進蓄積ルーティング（progressive accumulative routing：ＰＡＲ）プロセスを使用し、漸進蓄積ルーティングプロセスは、各中継ノードに必要なものがローカル情報のみであるように、分散様式で中継の発見、中継の順序付け、および電力割り振りを漸進的に実行する。
【００１２】
本発明の実施の形態は、また、宛先エネルギー蓄積（destination energy accumulation：ＤＥＡ）プロセスも使用し、宛先エネルギー蓄積プロセスでは、複雑性の低い中継ノードがdecode-and-forward方式を使用している場合に、個々のパケットが弱すぎて確実に復号化できない場合があるため、宛先ノードのみがパケットの複数の受信コピーを記憶する。
【００１３】
ＰＡＲプロセスおよびＤＥＡプロセスは、ネットワークでの総エネルギー消費量をかなり低減し、効率的に実施することができる。さらに、これらのプロセスは、最適なルーティングを高い確率で提供する。
【発明の効果】
【００１４】
本発明の実施の形態による無線中継ネットワークでは、宛先のみがエネルギーを蓄積し、中継ノードは、エネルギーを蓄積しない。はるかに単純な中継を有するこのような中継は、エネルギーがあらゆるノードに蓄積される従来のネットワークに匹敵するエネルギー効率を有する。宛先エネルギー蓄積ネットワークは、また、エネルギーを蓄積しない従来のマルチホップネットワークよりもエネルギー効率的である。
【００１５】
ＰＡＲプロセスは、分散様式でＤＥＡルートを発見し、中継送信電力を判断する。このプロセスは、チャネル利得についてのローカル情報を利用するとともに、ルートに中継として追加することができるノードからの非常に限られたフィードバックを使用する。ＰＡＲでのルート発見は、非常に低い複雑性を有し、これは、全エネルギー蓄積ネットワークでのルート発見プロセスのＮＰ完全性とは対照的である。
【００１６】
ＰＡＲを使用して、ノードは、ＤＥＡルートで現在送信中のパケットを受信し、復号化することができ、ノードが中継として機能してルートの総消費電力を低減できるか否かを判断することができる。
【００１７】
ＰＡＲを使用したルートセットアップの待ち時間は、短く、これは、発信元と宛先との間の基本接続性が最初から確立され、時間の経過に伴ってより多くの中継を漸進的に追加することでルートが改良されるためである。ＰＡＲは、複雑性の低いノードを有する実際のセンサネットワークでの消費エネルギーの低減に、非常に適している。
【発明を実施するための最良の形態】
【００１８】
無線中継ネットワーク
図１は、本発明の1つの実施の形態による無線中継ネットワーク１００を示す。ネットワークは、発信元ノードｓ１１１、宛先ノードｔ１３１、および１つまたは複数の中間のdecode-and-forward方式の中継ノードｒ１２１〜１２４を含む。すべてのノードは、送受信に単一の全方向性アンテナを介するユニキャスト伝送を使用し、半二重モードで動作する。すなわち、ノードは、送信または受信のいずれか一方を行うことはできるが、両方を同時には行わない。ネットワーク１００は、準静的であり、不定期のリンク更新により、ネットワークのチャネルのチャネル状態情報のあり得る変更を反映させる。発信元は、宛先に直接送信するか、または１つ若しくは複数の中継ノードを介して間接的に送信することができる。中継ノードは、パケットを宛先に直列または並列に転送することができる。
【００１９】
宛先エネルギー蓄積
本発明の実施の形態は、宛先エネルギー蓄積（ＤＥＡ）を利用する。ＤＥＡは、２つの既知の両極端のネットワーク、すなわち（ｉ）エネルギー蓄積の恩恵を受けない単純なdecode-and-forward方式の中継が必要な従来のネットワークと（ｉｉ）エネルギーを最大限蓄積するかなり複雑なdecode-and-forward方式の中継が必要な、完全なエネルギー蓄積ネットワークとの間のギャップを埋める。
【００２０】
本実施の形態では、宛先ノードのみがパケットの復号化にパケットの記憶されている複数のバージョンを使用し、中間中継は、パケットの複数のバージョンを記憶しない。すなわち、中継ノードは、パケット転送後にそのパケットを破棄する。実施の形態の１つにおいて、パケットのバージョンとはパケットのコピーのことである。
【００２１】
巡回冗長検査をパケットに挿入して、パケットが正しく復号化されているか否かを判断することができる。宛先のみにエネルギーを蓄積することは、以下の理由により正当化することができる。本明細書では、エネルギー蓄積により、宛先ノードのみに同じパケットの複数のバージョンを記憶することを特に意味する。多くのセンサネットワークでは、すべてのセンサノードからセンサデータを収集する宛先ノードは、通常、大きな計算資源、メモリ資源、および電力資源を有する。さらに、蓄積作業は、蓄積から恩恵を受けるノードで行われる。蓄積し記憶する必要のあるパケットの数は、限られる。さらに、エネルギー蓄積を宛先でのみ行うことにより、ネットワーク全体を通しての消費エネルギーが低減する。別の利点として、エネルギー蓄積を宛先でのみ行うことにより、ルート発見が大幅に簡易化され、実用的な実施が実現可能になる。
【００２２】
漸進蓄積ルーティング
漸進蓄積ルーティング（ＰＡＲ）プロセスも使用され、これは、エネルギー効率的なＤＥＡルートを判断し、ノード送信電力を分散的かつ漸進的に設定する。分散プロセスとして、ＰＡＲは、各ノードで入手可能なローカルチャネル状態情報のみに基づいてエネルギー効率的な蓄積ルートを確立する。このプロセスの漸進性により、確立されたＤＥＡルートに新しいノードを増分的に追加することができ、さらなるエネルギー低減が実現される。
【００２３】
伝搬環境の変化により、またはノードの可動性により、各種ノード間のチャネルは、経時変化する。ＰＡＲを使用して、すでに確立されたルートを更新することができる。
【００２４】
ＰＡＲプロセスは、従来の非蓄積ネットワークと比較して総エネルギー効率を大幅に向上させる。すなわち、パケットをルートに沿って送信する間に消費されるエネルギー量が低減される。高い確率で、ＰＡＲプロセスは、すべてのノードで最適で完全なエネルギー蓄積を行う。
【００２５】
ネットワークモデル
Ｖをネットワーク１００内のノードの集合とする。ノードｕについて、ｈｕｖをノードｕとノードｖとの間のチャネル利得の絶対値とする（ｖ∈Ｖ）。ノードは、隣接ノードに対するチャネル利得のみを求めることができる。ノードは、あらゆるチャネル利得の位相を求める必要がなく、また、他のノード間のリンクの他のいかなる利得も求めることはできない。
【００２６】
ノードは、パケットを確実に復号化した後でのみ、そのパケットを転送することができる。本発明の実施の形態によれば、宛先ノードのみが、パケットの複数のバージョンを記憶することによってエネルギーを蓄積し、中継ノードは、エネルギーを蓄積しない。宛先ノードは、複数のノードからの同じパケットの複数の「ソフト」コピーを受信して記憶することができる。
【００２７】
宛先ノードは、受信したパケットの複数のバージョンから蓄積された総エネルギーが所定の閾値を超えた後（所定の閾値は、送信に使用される変調および符号化によって決まる）、そのパケットを首尾よく復号化することができる（上記のMaric他およびAgarwal他参照（参照により本明細書に援用される））。巡回冗長検査（ＣＲＣ）をパケットに含めて、受信側が、パケットが正しく復号化されたか否かを判断できるようにすることができる。
【００２８】
宛先は、各ノードｕ１，ｕ２，・・・，ｕｎからパケットの１つのバージョンを受信したとき、下式の総蓄積電力が閾値γ（￣）以上の場合に、パケットを首尾よく復号化することができる（なお、表記（￣）は、かっこの前の記号の上部に￣が付くことを意味する）。
【００２９】
【数１】
2008042911.tif 000003
【００３０】
ここで、ｐｋは、ノードｕｋの送信電力である。中継ノードｖは、ノードｕから送信された電力ｐを有するパケットを、ｐｈｕｖ＝γ（￣）である場合、かつその場合に限り首尾よく復号化することができ、その他の場合、中継は、復号化不可能なパケットを破棄する。一般性を失うことなく、パケットの持続時間は、１に正規化される。したがって、エネルギーなる用語と電力なる用語とは同じ意味で使用される。
【００３１】
漸進蓄積ルーティング
単一の発信元ｓおよび単一の宛先ｔを考える。まず、（ｉ）単一の中継がノードｓとノードｔとの間に追加された場合、および（ｉｉ）第２の中継が、１つの中継をすでに含んでいるエネルギー蓄積ルートに導入される場合の電力低減の一般的な状況を導出する。後述するように、多くの場合、最適中継の判断に必要な情報は、非常に限られる。このため、その結果を、任意の数の中継を含む一般エネルギー蓄積ルートに拡張する。また、後述するように、中継でのローカルチャネル状態情報および限られた追加情報を使用して、さらなるエネルギー低減を実現することができる。
【００３２】
第１の中継を発信元と宛先との間に追加するステップ
補題１
中継ノードｒを通る発信元ノードｓから宛先ノードｔへの蓄積ルートは、下式（１）のようなノードｒが存在する場合、かつそのような場合に限り総消費電力を低減することができる。
【００３３】
【数２】
2008042911.tif 000004
【００３４】
ノードｒを中継として機能させることによる最大総電力低減Ｐｓｒｅｄ（ｒ）は、下式（２）により与えられる。
【００３５】
【数３】
2008042911.tif 000005
【００３６】
そして、ノードｓおよびノードｒが、それぞれの送信電力ＰｓおよびＰｒをそれぞれ下式（３）に設定した場合に実現される。
【００３７】
【数４】
2008042911.tif 000006
【００３８】
証明
まず、式（１）を満たすノードがないものと仮定する。これは、すべての中継ｒ∈Ｖ−｛ｓ,ｔ｝について、ｈｓｔ＝ｈｓｒであり、かつ／またはｈｓｔ＝ｈｒｔであることを暗に意味する。あらゆるノードｒについて、ｈｓｔ＝ｈｓｒである場合、パケットをノードに送信するよりも、宛先に首尾よく送信するほうが、必要な電力が小さい。ｈｓｔ＝ｈｒｔである場合、送信電力が同じとき、パケットが中継ではなく発信元から送信された場合に、宛先は、より高い信号電力を受信する。したがって、中継を使用することにより、総消費電力を低減することはできない。
【００３９】
ｈｓｔ＜ｍｉｎ｛ｈｓｒ，ｈｒｔ｝であるような少なくとも１つのノードｒが存在するものとする。ＤＥＡでは、ｒが中継である場合、発信元は、まず、ノードｒがパケットを首尾よく復号化できるように、電力Ｐｓを有するパケットを送信する。次いで、ノードｒは、パケットを、電力Ｐｒで宛先ノードｔに送信する。宛先は、両方のノードｓおよびｒの送信から蓄積されたエネルギーを使用してパケットを復号化する。したがって、最適電力割り振り問題は、下式（４）の通りである。
【００４０】
【数５】
2008042911.tif 000007
【００４１】
式（４）での制約の最初の不等式により、ノードｒがノードｓにより送信されるパケットを復号化することが保証される。ノードｒがパケットを復号化した後、ｈｒｔ＞ｈｓｔであるため、パケット復号化のために、ノードｒにより、残余エネルギーをノードｔに送らせるほうがよりエネルギー効率的である。これは、式（４）の制約を等式で満たす式（３）の電力割り振りに繋がる。次いで、ノードｓからノードｔへの直接送信に必要な最小電力γ（￣）／ｈｓｔと比較した式（３）の電力設定での総電力低減が、式（２）によって与えられる。この電力低減は、式（１）が満たされる場合に正である。
【００４２】
補題１は、式（１）を満たすノードのみが、総消費エネルギーの低減に適格な候補であることを示す。発信元が、どのノードが最良の中継であるかを判断するために、ノードがすでに有する任意のローカル情報の他に、利得ｈｒｔを知る必要があるだけであることに留意願いたい。また、ノードｓがパケットをノードｔに直接送信している場合、ｈｓｒ＞ｈｓｔであるため、適格なすべての候補は、すでにパケットを復号化できる。
【００４３】
第２の中継をソースと宛先との間に追加するステップ
ノードｒを、図２Ａに示すＤＥＡルートにすでに存在する最適な第１の中継を示すものとする。図２Ｂ〜図２Ｄに示すように、第２の中継ｑを３つのリンクｓ−ｔ、ｓ−ｒ、およびｒ−ｔのうちの１つに追加することができる。補題２で、最初の可能性は、常に最適未満のものであり、考慮する必要がないことを述べる。
【００４４】
補題２
中継ｒを、ノードｓからノードｔへの送信に際して協働する最適な単一の中継とする場合、図２Ｂに示すように追加ノードｑをノードｓとノードｔとの間に並列に追加しても、ＤＥＡでの総送信電力を低減することはできない。
【００４５】
証明
両方の中継ｑおよびｒがノードｓからのパケットを首尾よく復号化するためには、ノードｓは最小電力Ｐｓ＝γ（￣）／ｍａｘ｛ｈｓｑ、ｈｓｒ｝で送信しなければならない。ノードｑおよびｒがパケットを首尾よく復号化した後、電力をノードｔへの最良チャネルを有するノードへのみ送ることが最適である。したがって、並列している２つの中継は、ｈｑｔ＝ｈｒｔの場合にのみ有用である。
【００４６】
ここで、ｈｑｔ＝ｈｒｔと仮定する。ｈｓｑ＞ｈｓｒの場合、これは、Ｐｓｒｅｄ（ｑ）＞Ｐｓｒｅｄ（ｒ）であることを暗に意味し、これは、中継ｒが最適な単一の中継であるという仮定に反する。ｈｓｑ＜ｈｓｒの場合、ノードｒのみが中継として使用されるべきである。ｈｓｑ＝ｈｓｒの場合、総消費電力は、単一の中継の場合と同じである。
【００４７】
補題２に基づき、図２Ｃおよび図２Ｄに示すように、考慮する必要があるのは、確立されたＤＥＡルート内のｓ−ｒリンクおよびｒ−ｔリンク間での新中継の追加についてのみである。
【００４８】
補題３
ｒを、確立されたＤＥＡルートでの最適な単一の中継であるとする。ｈｓｑ＞ｈｓｒ，ｈｑｔ＜ｍｉｎ｛ｈｑｒ,ｈｒｔ｝であり、かつ下式（５）であるようなノードｑ∈Ｖ−｛ｓ，ｒ，ｔ｝が存在する場合にのみ、図２Ｃに示すように、ノードｑをノードｓとノードｒとの間に追加することで総消費エネルギーが低減する。
【００４９】
【数６】
2008042911.tif 000008
【００５０】
最適な消費電力Ｐｓｒｅｄ（ｑ）は、下式（６）である。
【００５１】
【数７】
2008042911.tif 000009
【００５２】
これは、発信元および中継が、それぞれの送信電力Ｐｓ、Ｐｑ、およびＰｒを、下式（７）に設定した場合である。
【００５３】
【数８】
2008042911.tif 000010
【００５４】
証明
エネルギー効率的なＤＥＡルートでは、各中継は、次の中継に到達するのに必要な最小電力でパケットを送信し、最後の中継が、宛先がそれまでの中継による送信から蓄積されたエネルギーを使用してパケットを復号化するのにただ十分な電力でパケットを宛先に送信する。これは、ＤＥＡルートｓ−ｑ−ｒ−ｔについて、式（７）での電力割り振りに繋がることを示すことができる。式（６）での電力低減は、ルートｓ−ｑ−ｒ−ｔとルートｓ−ｒ−ｔとの総送信電力差である。
【００５５】
ＤＥＡルートｓ−ｑ−ｒ−ｔは、ｈｓｑ＞ｈｓｒの場合に電力を低減することができず、その他の場合、ノードｒそれ自体でノードｓにより送信されるパケットを首尾よく復号化することができるため、ノードｑをルートから外すことができる。同様に、ｈｑｔ＞ｍｉｎ｛ｈｑｒ，ｈｒｔ｝の場合に、ノードｒをルートから外すことができる。しかし、これは、ノードｒが最適な単一の中継であるという仮定に反する。式（６）での総電力低減は、式（５）での条件が満たされる場合かつそのような場合に限り正である。
【００５６】
補題４
ノードｒを確立されたＤＥＡルートでの最適な単一の中継とする。下式（８）のようなノードｑ∈Ｖ−｛ｓ，ｒ，ｔ｝が存在するとする。
【００５７】
【数９】
2008042911.tif 000011
【００５８】
このような場合にのみ、図２Ｄに示すように、ノードｑを、ノードｒとノードｔとの間に追加することで、下式（９）に示すような最適な電力低減Ｐｒｒｅｄ（ｑ）に繋がる。
【００５９】
【数１０】
2008042911.tif 000012
【００６０】
これは、発信元および中継がそれらの送信電力Ｐｓ、Ｐｑ、およびＰｒをそれぞれ下式（１０）に設定した場合である。
【００６１】
【数１１】
2008042911.tif 000013
【００６２】
証明
式（１０）での電力割り振りは、補題３での場合と同様の論拠に従う。また、ｈｑｔ＝ｈｒｔの場合、ノードｑをＤＥＡルートｓ−ｒ−ｑ−ｔから外すことができる。式（９）での総電力低減は、ルートｓ−ｒ−ｑ−ｔおよびルートｓ−ｒ−ｔにより消費される総電力の差である。これは、式（８）が満たされる場合、かつそのような場合に限り正である。
【００６３】
第２の中継が追加される前、第１の中継ｒは、パケットを電力１／ｈｒｔ（１−ｈｓｔ／ｈｓｒ）γ（￣）で送信することに注意願いたい。式（８）での必要十分条件から、総電力を低減できる適格なすべてのノードが、ノードｒにより送信されるパケットを首尾よく復号化できることが分かる。中継を漸進的に追加して総消費電力を低減する場合に、このことを利用する。
【００６４】
複数の中継
上述したように、並列している２つの中継は、最適な単一の中継のＤＥＡルートで総消費電力を低減することはできない。この結果は、複数の中継が存在する場合に一般化することができる。したがって、考慮する必要があるのは、図２Ｃおよび図２Ｄにおいて行ったように、新しいノードが２つの隣接中継間または中継と宛先との間に挿入される場合だけである。本明細書では、このようなルートを直列ＤＥＡルートと呼ぶ。
【００６５】
複数の中継をすでに含む直列ＤＥＡルートへのノードｗの追加を考えるには、まず、以下の用語を定義する。ノードｕおよびノードｖが直列ＤＥＡルート内の２つの中継であり、ノードｕが中継ｖよりも前にパケットを首尾よく復号化する場合、ノードｕがノードｖの前にあり、ノードｖがノードｕの後にあると言う。ノードｖがノードｕの後にあり、ノードｕの後かつノードｖの前に中継がない場合、ノードｖがノードｕの直後または次にあると言う。直列ＤＥＡルートでのノードｕの直後の中継をＮ（ｕ）で示す。Ｎ（ｕ）＝ｔの場合、中継ｕを直列ＤＥＡルートの最後の中継と呼ぶ。
【００６６】
中継の集合Ｒは、直列ＤＥＡルートにある、宛先を除くすべての中継の集合である。逆方向中継集合Ｂ（ｕ）は、ルートでのノードｕの前にある中継の順序付き集合である。Ａ（ｕ）＝Ｐｒ∈Ｂ（ｕ）ｈｒｔ／ｈｒＮ（ｒ）が、宛先においてパケットを首尾よく復号化するために必要な、総エネルギーの割合を示す。エネルギーは、集合Ｂ（ｕ）内の中継からの送信により宛先に蓄積する。
【００６７】
定理１
ｕを直列ＤＥＡルート内の中継とし、ｖ＝Ｎ（ｕ）を中継ｕの直後の中継とする。ｕがルートの最後の中継ｌではない場合、ノードｗをノードｕの直後の中継として追加すると、ｗが下式（１１）の２つの十分条件を満たす場合に総消費電力が低減される。
【００６８】
【数１２】
2008042911.tif 000014
【００６９】
下式（１２）の総電力低減は、ｕおよびｌのノード送信電力が下式（１３）に変更される場合に実現される。
【００７０】
【数１３】
2008042911.tif 000015
【００７１】
新しい中継ｗの送信電力は、Ｐｗ＝γ（￣）／ｈｗｖである。ルートの他のすべての中継の送信電力は、変更されない。
【００７２】
証明
補題３と同様の論拠を用いると、ノードｗが中継として追加された後の電力割り振りは、式（１３）の電力割り振りに対応することとなる。式（１１）の電力低減の条件は、式（５）と同様にして導出することができる。電力低減を実現するために、式（１１）の条件では、直列ＤＥＡルート内のあらゆる中継が、利得ｈｌｔを求める必要がある。これは、分散実施では伝達されない。以下の系が、あらゆる中継が利得ｈｌｔを求める必要なしに電力低減を保証する十分条件を提供する。
【００７３】
系１
ノードｕが直列ＤＥＡルートの最後の中継でない場合、ノードｗをノードｕの直後に追下することで、下式（１４）の条件である場合に電力を低減することができる。
【００７４】
【数１４】
2008042911.tif 000016
【００７５】
定理２
ノードｕが直列ＤＥＡルートの最後の中継である場合、ノードｗをノードｕの直後に追加することで、ｗが下式（１５）の２つの条件を満たす場合に消費電力を低減することができる。
【００７６】
【数１５】
2008042911.tif 000017
【００７７】
下式（１６）の総電力低減は、ノードｕの送信電力がＰｕ＝γ（￣）／ｈｕｗに変更され、かつ新しいノードｗの送信電力が下式（１７）に変更された場合に実現される。
【００７８】
【数１６】
2008042911.tif 000018
【００７９】
ルートの他のすべての中継の送信電力は、変更されない。
【００８０】
証明
補題４と同様の論拠を用いると、ノードｗが追加された後の電力割り振りは、式（１０）の電力割り振りに対応することとなる。式（１５）での電力低減の条件は、式（８）と同様にして導出することができる。定理２および系１の両方が、すべての可能性のある中継、すなわち電力低減に繋がるノードが、直前の中継からの送信をすでに首尾よく復号化できることを示す。そのため、可能性のある中継からのローカルチャネル状態情報および最小フィードバックを使用して、直列ＤＥＡルートを漸進的に増分して総電力を低減することができる。
【００８１】
漸進蓄積ルート（ＰＡＲ）
まず、基本ルートが発信元と宛先との間に確立される。ノードｓからノードｔに直接リンクが存在しない場合、従来のルート発見プロセスを使用して、ネットワーク内のノードｓとノードｔとの間にルートを発見することができる。
【００８２】
次いで、ＰＡＲプロセスが、直列ＤＥＡルートのエネルギー効率を向上させるように漸進的かつ分散的に中継を追加する。すなわち、パケットをルートに沿って送信する間に消費エネルギーが低減される。この中継発見プロセスは、２種類のパケットを介して行われる。すなわち、ノードｓからノードｔに送信されるデータを含むデータパケットおよびルートを変更するために必要な限られた追加情報をフィードバックするための協働要求（ＲＴＣ）パケットである。
【００８３】
発信元は、すでに確立されている直列ＤＥＡルートを通してデータを宛先に送信する。発信元は、新しいパケットを次の中継Ｎ（ｓ）に電力γ（￣）／ｈｓＮ（ｓ）で送信する。確立されている直列ＤＥＡルートの現在送信中の中継から送信を受信した隣接ノードは、利用できるローカル情報およびデータパケット内の情報のみを使用して、中継として参加することで、さらなる電力低減に繋げることができるか否かを調べる。できる場合、ノードは、ＲＴＣパケットを、そのノードが受信したパケットを送信した中継にフィードバックする。
【００８４】
図３は、データパケットおよびＲＴＣパケットの構造を示す。パケット内の各フィールドの意味を図４に示す。
【００８５】
ＰＡＲプロセスの擬似コードを図５に示す。発信元ではない中継ｕがデータパケットｐを首尾よく復号化する場合、その中継は、ｐ．ＲＤｅｓｔ＝ｕの場合にのみパケットに対して機能する。次いで、中継は、最終宛先がｐ．ＭＤｅｓｔであり、ｐが送信された後に宛先に蓄積される総電力がｐ．ＦｒａｃＤｅｌｉｖｅｒｅｄ＋ｐ．ＧａｉｎＤ／ｐ．ＧａｉｎＲであることを知る。すなわち、中継は、特定のパケットを宛先に送信することにより、宛先に蓄積されるエネルギーの割合を記録する。この記録情報もルートに沿って他のノードに転送されるため、ノードは、エネルギーを最小に抑えるルートの設計に参加することができる。
【００８６】
ｕは、最後の中継ではない場合、パケットを次の中継に電力γ（￣）／ｈｕＮ（ｕ）で送信する。ノードは、最後の中継である場合、パケットを電力（１−Ａ（ｕ））／ｈｕｔで送信する。
【００８７】
中継ｕは、ルートを最後に更新してから十分な時間ｍｉｎＴｉｍｅが経過した後に、ルートを更新する。時間ｍｉｎＴｉｍｅは、マルチアクセスプロトコルによって決まり、ノードが追加中継を決定する前に、中継がＲＴＣフィードバックパケットを受信するのに十分な時間を有することを保証するために使用される。ノードは、次の中継をｂｅｓｔＣａｎｄｉｄａｔｅで示される次のノードに更新する。これにより、最大の電力低減に繋がる。ＲＴＣパケットは、ノードｕがノードｂｅｓｔＣａｎｄｉｄａｔｅを見つけられるようにする。ノードｕがＲＴＣパケットをノードｗから受信すると、そのパケットのフィールドにより、ノードｕは、ノードｗが次の中継になった場合の電力低減を、以下のように求めることができる。
【００８８】
ｕが最後の中継でない場合、下式（１８）であり、ｕが最後の中継である場合、下式（１９）である。
【００８９】
【数１７】
2008042911.tif 000019
【００９０】
式中、ｖは、ｕの直後の中継である（ｖ＝Ｎ（ｕ））。Ｐｕｒｅｄ（ｗ）が現在の最良の候補により実現可能な電力低減を超える場合、ｂｅｓｔＣａｎｄｉｄａｔｅをノードｗに更新する。
【００９１】
ノードｗがデータパケットｐを中継ｕから受信すると、データパケットのフィールドにより、ノードｗは、式（１４）または式（１５）を使用して、中継になることにより総電力を低減することができるか否かを調べることができる。できる場合、ノードｗは、Ｎ（ｗ）＝ｐ．ＲＤｅｓｔをメモリに記憶し、可能な場合にはマルチアクセスプロトコルに従ってＲＴＣパケットを生成して送信する。ノードの擬似コードを図６に提供する。
【図面の簡単な説明】
【００９２】
【図１】本発明の1つの実施の形態による無線中継ネットワークのブロック図である。
【図２Ａ】追加の中継ノードを有するネットワークのブロック図である。
【図２Ｂ】追加の中継ノードを有するネットワークのブロック図である。
【図２Ｃ】追加の中継ノードを有するネットワークのブロック図である。
【図２Ｄ】追加の中継ノードを有するネットワークのブロック図である。
【図３】本発明の１つの実施の形態によるデータパケットおよび協働要求パケット（ＲＴＣ）のブロック図である。
【図４】本発明の１つの実施の形態による図３のＲＴＣパケットのフィールドの説明のブロック図である。
【図５】本発明の１つの実施の形態による図１のネットワークの中継ノードによって実行される擬似コードのブロック図である。
【図６】本発明の１つの実施の形態によるパケットを受信する他のノードによって実行される擬似コードのブロック図である。
【図１】
2008042911.tif 000020
【図２Ａ】
2008042911.tif 000021
【図２Ｂ】
2008042911.tif 000022
【図２Ｃ】
2008042911.tif 000023
【図２Ｄ】
2008042911.tif 000024
【図３】
2008042911.tif 000025
【図４】
2008042911.tif 000026
【図５】
2008042911.tif 000027
【図６】
2008042911.tif 000028
【外国語明細書】
2008042911.tif 000029
2008042911.tif 000030
2008042911.tif 000031
2008042911.tif 000032
2008042911.tif 000033
2008042911.tif 000034
2008042911.tif 000035
2008042911.tif 000036
2008042911.tif 000037
2008042911.tif 000038
2008042911.tif 000039
2008042911.tif 000040
2008042911.tif 000041
2008042911.tif 000042
2008042911.tif 000043
2008042911.tif 000044
2008042911.tif 000045
2008042911.tif 000046
2008042911.tif 000047
2008042911.tif 000048
2008042911.tif 000049
2008042911.tif 000050
2008042911.tif 000051
2008042911.tif 000052
2008042911.tif 000053
2008042911.tif 000054
2008042911.tif 000055
2008042911.tif 000056
2008042911.tif 000057
2008042911.tif 000058
2008042911.tif 000059
2008042911.tif 000060