(57)【要約】      （修正有）【課題】アドホックネットワークにおいて最適なルート選択を可能とする。【解決手段】方法は、ノード、すなわち送信元、一組のリレー、及び宛先を含むノードから成るワイヤレス協調リレーネットワークにおいてルートを選択する。コードワードが、データストリームとして符号化される。このデータストリームは、送信元から宛先へ一組のリレーを介して送信される。相互情報量が、特定のノードにおいて積算されて、データストリームが復号され、コードワードが復元される。次に、送信及び積算を行っている間、送信元から宛先へのルートが、ノード間のチャネル状態情報に基づいて選択される。【選択図】図１
2008148299.tif 000002
【特許請求の範囲】
【請求項１】
ノードから成るワイヤレス協調リレーネットワークにおけるルート選択方法であって、前記ノードは、送信元、一組のリレー、及び、宛先を含み、該方法は、
コードワードをデータストリームとして符号化するステップと、
前記送信元から前記宛先へ前記一組のリレーを介して前記データストリームを送信するステップと、
特定のノードにおいて相互情報量を積算して、前記データストリームを復号し、前記コードワードを復元するステップと、
送信及び積算を行っている間、前記ノード間のチャネル状態情報に基づいて、前記送信元から前記宛先へのルートを選択するステップと
を備えたことを特徴とするノードから成るワイヤレス協調リレーネットワークにおけるルート選択方法。
【請求項２】
前記符号は、ブロックエラー訂正符号であることを特徴とする請求項１に記載の方法。
【請求項３】
前記符号は、レートレス符号であることを特徴とする請求項１に記載の方法。
【請求項４】
拡散符号を使用して前記コードワードを符号化するステップをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項５】
前記コードワードは、ビットを任意に積算したものであることを特徴とする請求項１に記載の方法。
【請求項６】
前記データストリームは、パケットとしてブロードキャストされることを特徴とする請求項１に記載の方法。
【請求項７】
前記ルートは、該ルートにおけるノードを識別し、識別された該ノードのそれぞれによって使用される電力、送信時間、及び、拡散符号を指定することを特徴とする請求項１に記載の方法。
【請求項８】
前記指定することは、前記ノード間の前記チャネル状態情報に基づくことを特徴とする請求項７に記載の方法。
【請求項９】
前記チャネル状態情報は、中央ロケーションにおいて知られており、前記ルートは、該中央ロケーションにおいて選択されることを特徴とする請求項１に記載の方法。
【請求項１０】
前記ルートは、該ルートにおけるノードを識別し、前記方法は、
前記ネットワークにおけるすべてのノードへ前記ルートをブロードキャストするステップ
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項１１】
前記チャネル状態情報は、前記ノードのすべてのサブセットにおいて知られており、該チャネル状態情報は、分散形式で求められることを特徴とする請求項１に記載の方法。
【請求項１２】
前記選択するステップは、最適化プロセス及び最適化基準を使用することを特徴とする請求項１に記載の方法。
【請求項１３】
前記最適化基準は、前記データストリームの送信時間が所定のしきい値を超える確率を最小にすることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記最適化基準は、前記ネットワークにおけるエネルギー消費を最小にすることを特徴とする請求項１２に記載の方法。
【請求項１５】
前記最適化基準は、前記ノードのすべてにおける最大エネルギー消費を最小にすることを特徴とする請求項１２に記載の方法。
【請求項１６】
前記最適化基準は、前記ネットワークにおけるデータスループットを最大にすることを特徴とする請求項１２に記載の方法。
【請求項１７】
前記最適化基準は、前記ネットワークの寿命を最大にすることを特徴とする請求項１２に記載の方法。
【請求項１８】
前記最適化基準は、送信時間、エネルギー消費、スループット、及び、前記ネットワークの寿命の線形結合であることを特徴とする請求項１２に記載の方法。
【請求項１９】
前記最適化基準は、送信時間、エネルギー消費、スループット、及び、前記ネットワークの寿命の非線形結合であることを特徴とする請求項１２に記載の方法。
【請求項２０】
前記最適化プロセスは、ペナルティ関数を最小にすることを特徴とする請求項１２に記載の方法。
【請求項２１】
前記最適化プロセスは、近似であり、数値最適化方法を使用することを特徴とする請求項１２に記載の方法。
【請求項２２】
前記最適化プロセスは、焼きなまし法を使用することを特徴とする請求項１２に記載の方法。
【請求項２３】
前記最適化プロセスは、遺伝的アルゴリズムを使用することを特徴とする請求項１２に記載の方法。
【請求項２４】
前記最適化プロセスは、ノードを繰り返し追加して、前記ペナルティ関数の最大の改善につながる準最適なルートを選択することを特徴とする請求項２０に記載の方法。
【請求項２５】
前記最適化プロセスは、前記ペナルティ関数の最大の改善につながる準最適なルートからノードを繰り返し控除することを特徴とする請求項２０に記載の方法。
【請求項２６】
前記最適化プロセスは、所定のルートから、前記積算された相互情報量の量を実質的に増加させないノードを繰り返し控除することであることを特徴とする請求項２５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、ワイヤレスネットワークに関し、より詳細には、協調ネットワークにおける情報の送信に関する。
【背景技術】
【０００２】
アドホックネットワーク
アドホックワイヤレスリレーネットワークは、セルラーネットワーク等の従来の構造化ネットワークを上回る多くの利点を有する。アドホックワイヤレスネットワークは、固定されているインフラストラクチャを必要としない。これは、コストを削減することができる。信号は、異なるルートを介して送信することができるので、信頼性は増加する。中間リレーノードがより短いホップを介して信号を受信して再送信できるので、エネルギー消費を削減することができる。全送信エネルギーが減少するので、ネットワークの寿命が長くなり、また、干渉が少なくなり、スペクトル効率が改善される。
【０００３】
アドホックリレーネットワークの不利な点として、送信元ノードから宛先ノードへのルートを指定する必要がある。このルートは、情報のリレーに関与するノード列、送信プロトコル、ノードにおけるエネルギー割り当て、及び送信スケジュールを指定する。
【０００４】
従来のアドホックリレーネットワークでは、送信元ノードは、通常、エラー訂正符号で情報を符号化し、この情報は、ルートのノード列を介して送信される。符号化された情報は、コードワード（codeword）と呼ばれる。本明細書で使用されるように、コードワードは、データバイトのファイル又はブロックとすることができる。
【０００５】
レートレス符号
チャネル状態情報（ＣＳＩ）が知られていない状況では、弱いブロックエラー訂正符号は、雑音によって通信を信頼できないものとする可能性がある一方、強いブロックエラー訂正符号は、エネルギーを浪費する。レートレス符号はこの問題を解決する。ブロックエラー訂正符号を使用して情報を所定のビット数として符号化する代わりに、情報は、潜在的に無限のビットストリームに符号化される。そして、受信機は、情報が復元されるまでフローのビットを復号するだけである。
【０００６】
レートレス符号には、ファウンテン符号、パンクチャード低レートブロック符号、リードソロモン符号、畳み込み符号、及びターボ符号が含まれる。レートレス符号は、最初は、消失チャネル用に設計された。しかしながら、レートレス符号は、加法性白色ガウス雑音（ＡＷＧＮ）チャネルにも良好に機能する。また、レートレス符号は、イーサネット（登録商標）アプリケーション、ポイントツーポイントアプリケーション、ブロードキャストアプリケーション、及びマルチキャストアプリケーションにも使用されてきた。
【０００７】
ルーティングプロトコル
リレーノードは、前のノードから信号を受信する。ノードは、増幅転送プロトコル（amplify-and-forward protocol）で信号を増幅することもできるし、ノードは、復号転送プロトコル（decode-and-forward protocol）で信号の情報を復号し、その情報を再符号化し、次に、信号を次のノードへ再送信することもできる。このプロセスは、信号が宛先ノードによって受信されるまで続く。このようなリレー方式は、マルチホップルーティングとして知られている。従来は、どの時点においても、１つのノードしか、送信元ノードから宛先ノードへの連続した複数のホップを有する単一のルートを使用して次のノードへ信号を転送していない。
【０００８】
マルチホップアドホックリレーネットワークにおいて最適なルートを選択するための多数の方法が知られている。「フラッディング（flooding）」と呼ばれる１つの方法では、各ノードは、そのノードのアドレス及び送信に使用されるエネルギー（又は電力）と共に情報をブロードキャストする。宛先ノードは、その後、自身が受信する積算された情報量から最適なルートを選択することができる。ルートに参加しているノードは、その後、フィードバック情報を使用してそのルートの通知を受けることができる。
【０００９】
すべてのチャネル状態情報が単一のロケーションで入手可能である場合、最適なルートは、ネットワークにおける全エネルギー消費を最小にする最適化技法又は他の最適化基準を使用して決定することができる。最適なルートの決定の分散型方法も知られている。
【００１０】
アドホックネットワークのもう１つの課題は、フロー制御である。フロー制御では、送信元ノードは、連続したビットストリーム（フロー）を送信し、リレーノードは、宛先ノードへのいくつかの並列リンク上に同時にフローを方向付ける。リレーノードは、このような複数のフローを受信することができ、フローが宛先ノードに到達するまで、ネットワークの後続のリレーへフローを再配信することができる。
【００１１】
協調リレーネットワーク
協調リレーネットワークは、単一ルートマルチホッピングの代わりとなるものを提供する。協調リレーネットワークでは、複数のノードが同時に情報を送信することができる。従来（最新式）の協調リレーネットワークでは、複数のノードは、同じ情報を送信し、受信ノードは、情報を復号する前に、信号のすべてからエネルギーを積算する。これは、受信ノードにおけるダイバーシティ次数（diversity order）を増加させることができる。加えて、ルートダイバーシティ（route diversity）を得るために情報をいくつかの並列ルート上に同時に送信することができる。したがって、フェードが深くなる確率が減少する。さらに、エネルギーの積算によって、送信のエネルギー効率が増加する。
【００１２】
協調通信を使用するネットワークは、並列ルート選択及び特定のリンクの符号選択等の異なる一組の問題を有する。協調という仮定の下での予想エネルギーコスト及びネットワークトポロジーも課題である。
【００１３】
従来技術のルート選択技法及び最適化技法は、一般に、ルートに沿ったノードがエネルギー積算を行うものと仮定している。しかしながら、その方法で選択されたルートは、ノードが相互情報量を積算するネットワークで使用されるとき、準最適（sub-optimal）となる。したがって、従来技術のルーティング方法は、本発明によるネットワークに適用可能ではない。
【００１４】
２００６年３月１６日にMolisch他によって出願された、本願の同一譲受人に譲渡された特許出願第１１／３７７，７１１号の「Cooperative Relay Networks using Rateless Codes」に記載されているルーティングプロトコルは、十分な相互情報量を有するどのノードも送信に参加するものと仮定する。準同期プロトコルでは、特定のスケジューリング方式が仮定され、送信元と宛先との間には、２つのホップしか許可されない。２ホップネットワークは、相対的に制限的であることは明らかである。
【００１５】
非同期方式は、ノードの送信の開始時刻及び継続時間について特別な仮定を行い、送信電力を等しく割り当てる。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
サイズに制約のないネットワークにおいてより一般的な方法でルート選択を改善することが望まれている。
【課題を解決するための手段】
【００１７】
本発明の実施の形態は、受信ノードが２つ以上の送信ノードからの相互情報量を積算できるワイヤレス協調リレーネットワークにおいて、情報を通信するための方法を提供する。より詳細には、複数のリレーノードが、情報の異なって符号化されたバージョンを送信する。受信機は、復号中に、その異なるバージョンの相互情報量を結合することができる。本発明は、このようなノードを有するネットワークにおいてルート、送信電力、及び送信時間を選択するための方法を提供する。
【００１８】
本発明の実施の形態は、送信時間、ネットワーク寿命、エネルギー消費、スループット（throughput）、信号対干渉比、若しくは他の適した基準、又はこれらの組み合わせの点から性能を最適化することができる。実施の形態は、ネットワークトポロジー及びノード間の送信チャネルの状態に従って、ルーティング、送信電力、スケジューリング、送信時間、及び使用される符号を動的に調整することによってこの最適化を達成する。
【００１９】
この最適化は、最適な組み合わせルートの総当り数値探索（brute-force numerical search）、集中化準最適繰り返し探索（centralized suboptimal iterative search)、又は非集中化準最適繰り返し探索（decentralized suboptimal iterative search）を使用することができる。
【発明を実施するための最良の形態】
【００２０】
図１及び図２は、本発明の実施の形態による協調リレーネットワーク１００及び２００を示している。協調リレーネットワーク１００は、送信元ノード１１１、一組のＮ個のリレーノード１２１〜１２４、及び、宛先ノード１３１を、すなわち、送信元、リレー、及び、宛先を、含む。また、本発明のこの実施の形態は、図２に示すような複数のリレー「ホップ」と共に使用できることも理解されるべきである。この場合、リレー１２５は、「中間」リレー１２６にとって「送信元」としても動作する。この方式は、追加のホップに拡張することができる。
【００２１】
場合によっては、通信遮断（outage）等の制約条件に従って、送信時間、ネットワーク寿命、エネルギー消費、スループット、信号対雑音比、若しくは他の適した基準、又はこれらの組み合わせの点からネットワークの性能を最適化することが望まれている。ここで、通信遮断は、所定の時間内又は所定のエネルギー内で送信が成功していないものと定義される。
【００２２】
送信元ノードは、一組のＮ個のリレーノードを介して宛先ノードへコードワードを送信する。これらのノードは、単一のルートを形成することもできるし、複数の並列ルートを形成することもできる。コードワードは、たとえば、データバイト（情報）のファイルとすることができる。リレーノードは、復号転送技法を使用する。コードワードは、スケーリングされたナット／Ｈｚ（nats/Hz）で与えられる、サイズＨｔａｒｇｅｔの帯域幅正規化エントロピー（bandwidth-normalized entropy）を有する。ここで、１ナットは、自然単位の情報量であり、オイラーの定数２．７１８…である。
【００２３】
送信元、さらにリレーは、レートレス符号を使用して、コードワードを符号化する。すべてのノードは、半２重モードで動作する。すなわち、ノードは、送信又は受信のいずれかを行うことができるが、双方を同時に行うことはできない。しかしながら、他の（ブロック）エラー訂正符号も符号化に使用できることに留意すべきである。一般化されたブロック符号の場合、積算された情報量は、それらの符号内に構築された冗長性を含む。
【００２４】
以下では、ダイレクトシーケンススペクトル拡散技法による送信が可能であるものとする。拡散は、柔軟且つ非集中的な方法で異なるデータストリームの送信を可能にし、それらのデータストリームは受信機において区別可能であるので、このような手法は、リレーネットワークに役立つ。ノードｎｉの送信電力はＰｉである。ノード間の伝播チャネルは、周波数フラットブロックフェージングチャネルとしてモデル化される。チャネル利得は、振幅のレイリーフェージングに対応して、独立した指数分布である。この場合もまた、これらの仮定は、一例を提供するためにのみ置かれていること、及び、場合によっては残りのバッテリー寿命、平均チャネル状態、又は瞬時チャネル状態によって変化する、異なる複数のアクセス方式、さらには、異なるノードの異なる送信電力を本方法と共に使用できることに留意されたい。
【００２５】
本受信機は、相互情報量を積算する受信機である。これらの受信機は、同時に到達する場合がある異なるリレーからのさまざまな情報ストリームを区別することができる。たとえば、受信機は、マルチユーザ検出を使用して、異なるレートレス符号を区別することができる。ＣＤＭＡシステムでは、データストリームがチップ継続時間よりも長い相対遅延で到達したときに、受信機は、異なるリレーノードからの受信データストリームを処理することができる。
【００２６】
受信機は、レートレス符号復号器を含み、その結果、異なるリレーノードからのデータストリームを区別することができ、リレーノードによって送信された信号の相互情報量を積算することができる。この場合もまた、従来のブロックエラー訂正符号も使用できることが強調される。
【００２７】
ＣＤＭＡシステムについての本発明の一実施形態では、宛先が、異なるデータストリームを分離して、それらのデータストリームに含まれる情報を抽出するために、異なるノードは異なる拡散符号を使用する。しかしながら、異なる拡散符号は、常に必要とは限らない。たとえば、すべてのリレーが同じ符号、すなわちレートレス符号又はブロック符号を使用して、自身の信号を宛先へ同期して送信するとき、同じ拡散符号を使用することができる。
【００２８】
擬似同期送信
図３に示すように、コードワード３０１は、レートレス符号３１１及び任意選択で拡散符号３１２を使用して符号化され（３１０）、データストリーム３２０が生成される。コードワード３０１は、ビットのあらゆる任意の集まり、すなわち「情報」とすることができる。送信元（Ｓ）３２５は、宛先（Ｄ）３２７によって受信されるデータストリームを一組のリレーノード（Ｒ）３２６へブロードキャストする（３３０）。データストリームのブロードキャストは、パケットの形にすることができる。
【００２９】
図４に示すように、リレーノードが、データストリームを復号してコードワードを復元するのに十分な相互情報量を積算するとすぐに、そのリレーは、受信が成功したことの確認応答（ＡＣＫ）４００を送信元へ返信する。
【００３０】
送信元は、所定の個数の確認応答４００を受信した後、場合によっては、送信元からのブロードキャストの終了をリレーノードに通知した後に、ブロードキャストを終了する。
【００３１】
同時に、リレーノードは、復元されたコードワードをデータストリームに再符号化し、受信から送信に切り換わる。
【００３２】
この第２のフェーズの間、２つの場合を考えることができる。第１は、すべてのリレーノードが同じレートレス符号で符号化されたデータストリーム４１０を送信する場合である。レートレス符号は、送信元によって使用されたものと同じものとすることができる。ランダムに配置されたリレーノードからの送信に固有の遅延差のために、データストリームは、わずかに異なる遅延で宛先に到達する。以下では、それらの遅延はチップ継続時間よりも長いが、シンボル継続時間よりもはるかに短いものと仮定する。この仮定は、大きな拡散率を有するダイレクトシーケンスＣＤＭＡシステムで達成することができる。宛先は、リレーノードから受信されたデータストリームの相互情報量を積算することができる。
【００３３】
第２は、各リレーノードが、データストリーム４１０の送信に異なるレートレス符号及び異なる拡散符号を使用する場合である。この場合、宛先は、異なるリレーノードからの信号を、それらの異なるリレーノードの異なる拡散符号を通じて区別することができ、相互情報量を積算する。宛先は、送信元によってブロードキャストされたデータストリーム３０９も使用できることに留意すべきである。
【００３４】
いずれの場合も、図５に示すように、宛先は、リレー及び場合によっては送信元によって送信されたデータストリームの復号に成功してコードワード３０１を復元するとすぐに、信号５００をリレーノードへ及び場合によっては送信元へもブロードキャストして、送信を終了する。
【００３５】
直観的には、単一のレートレス符号の使用と複数のレートレス符号の使用との間の相違は、消失確率ｐｅを有する消失チャネル（erasure channel）上で２つのリレーを使用するバイナリシグナリングの簡単な例について最も容易に理解することができる。それらのリレーが同じレートレス符号を使用する場合、各ビットは、確率ｐｅ２で消失することになり、その結果、１−ｐｅ２ビットが、リレー送信ごとに有効に受信される。
【００３６】
他方、２つの異なるレートレス符号が使用される場合、送信は独立しており、リレー送信ごとに２（１−ｐｅ）ビットが受信される。２つのプロトコルに必要とされる受信機の複雑さは、大きくは異ならないことに留意されたい。受信機のアナログ／デジタル変換器（ＡＤＣ）のサンプリングレートが、シンボルレートと同一である場合、双方の受信機は、Ｌ個の相関器を必要とする。第１の場合では、すべての相関器は、同じ拡散シーケンスとの相関を形成し、最大比合成に従って結果を加える。
【００３７】
或いは、受信機は、単一の相関器のみを使用することもできる。この相関器の出力は、各シンボル継続時間中にＬ回サンプリングされる。これによって、或るハードウェアの複雑さが省かれる。しかしながら、信号は、異なるリレーノードから不規則な間隔で到達する可能性があり、したがって、ＡＤＣがチップレートでサンプリングする能力を必要とする可能性がある。ＡＤＣのこの高速サンプリングは、電力（したがって、エネルギー）消費を大幅に増加させ、したがって、バッテリー電源のセンサネットワークアプリケーションにとって望ましくない場合がある。
【００３８】
第２の場合では、各相関器は、異なるリレーノードからの信号の検出に使用される。主要な相違は復号器にある。復号器は、複数のレートレス符号が使用される場合に、より複雑となる。第２の方法は、１つのコードワードの送信に複数の拡散符号を使い果たすので、改善された符号化利得がこの影響を部分的に相殺するものの、第２の方法のスペクトル効率はより悪くなる。
【００３９】
また、第１の場合及び第２の場合の組み合わせも使用できることに留意されたい。
【００４０】
非同期送信
上述したような擬似同期送信では、リレーノードは、送信元ノードによってブロードキャストされたデータストリームしか受信しない。しかしながら、レートレス符号を使用するとき、リレーノードは、他のリレーがデータストリームをより高速に復号するのを「援助する」こともでき、したがって、送信プロセスを加速することができ、したがって、エネルギー消費を削減することができる。このアイデアは、リレーがコードワードを復号するのに十分な情報量を受信するとすぐに、そのリレーノードが、再符号化されたデータストリームを宛先へ送信することを開始するということである。この送信は、まだ受信モードにある他のリレーノードによっても受信可能である。したがって、送信モードにあるリレーノードは、まだ受信しているリレーノードが、データストリームをより高速に復号するのを援助する。すなわち、他のリレーは、ブロードキャストデータストリーム及び再符号化されたデータストリームの双方を復号する。
【００４１】
図３に示すように、送信元ノードは、割り当てられた拡散符号及びレートレス符号を使用して、リレーノードのすべてへデータストリームをブロードキャストすることにより始動する。
【００４２】
すべてのリレーノードは、相互情報量を絶えず積算する。送信元は、所与の拡散符号による送信が開始すると、受信機による雑音の不要な受信を回避するように信号で伝える。送信元は、図４について説明したように送信を停止する。
【００４３】
図６に示すように、リレーノードは、コードワードを復号するのに十分な情報を有するとすぐに、受信モードから送信モードに切り換わる。リレーは、自身に割り当てられた拡散符号及びレートレス符号を使用して、コードワードをデータストリーム６０１として再送信する。受信モードにあるリレーノードは、すべての拡散符号を同時に観測するので、送信元ノードからのデータストリーム３３０及び宛先へ送信中のリレーノードからのデータストリーム６０２を受信することができ、それらのすべてのノードからの相互情報量を積算して、データストリームをより高速に復号する。
【００４４】
宛先ノードは、異なるリレーのすべてのデータストリームを連続的に受信し、したがって、さまざまなリレーノードからの情報量を積算する。上述したように、宛先は、送信元から直接受信されたコントリビューション３０９も使用することができる。
【００４５】
宛先は、送信元データストリームを復号してコードワードを復元することに成功するとすぐに、図５に示すように、信号５００をリレーノードへ及びおそらく送信元へもブロードキャストして、送信を終了する。
【００４６】
宛先がコードワードの復元に成功するまで送信は続くものと仮定する。送信元がリレーノードを監視し、すべてのリレーノードが送信モードにあるとすぐに送信を停止する場合に、いくらかのエネルギーを節減することができる。
【００４７】
ルート検出
上記プロトコルは、どのノードが送信に参加するのか、それらのノードの電力及び送信時間を暗に決定することによって機能する。しかしながら、それらのパラメータを明示的に最適化すること、すなわち最適なルート（ルート上のノードのパラメータを含む）を見つけることに相当するプロセスが、好都合となり得る。以下では、そのサイズ又はホップ数において制限のないネットワークにおいて、この最適なルートを見つける方法を説明する。
【００４８】
仮定
協調ネットワークにおけるルートの最適化は、より多くの自由パラメータを最適化する必要があるので、特に困難である。したがって、一定の量のオーバーヘッド送信がネットワークで避けられないことを認識しつつ、いくつかの単純化する仮定を行う。
【００４９】
（ｉ）ネットワークのノードは、地理的にランダムに分布している。一部のノード又は全部のノードのロケーションが、ＧＰＳ又は超広帯域測位を通じて判明していることは可能ではあるが、必要ではない。このようなサイド情報は、情報を転送すべき方向の情報を提供するのに役立つので、ルーティングプロセスによって使用することができる。以下では、このようなサイド情報を考慮しない。しかしながら、このようなサイド情報を、情報量を積算する協調ネットワークにおけるルーティングに使用することは、本特許の一部である。
【００５０】
（ｉｉ）単純化するために、ルート選択は集中化される。しかしながら、特に大きなネットワークでは、分散型ルーティングも使用することができる。
【００５１】
（ｉｉｉ）瞬時ＣＳＩ又は平均ＣＳＩも中央で知られている。チャネル状態情報の量は変化し得る。通常、瞬時ＣＳＩ又は平均ＣＳＩのいずれかが知られている状況を考える。ＣＳＩは、観測中の雑音及び干渉、並びに／又は、ＣＳＩがネットワークを通じて送信される時の量子化、並びに／又は、ＣＳＩの測定とルーティングプロセスでのその使用との間の遅延によるチャネルの変化によって、雑音を有する可能性がある。以下の説明では、完全な瞬時ＣＳＩ又は完全な平均ＣＳＩのみを考える。しかしながら、ＣＳＩの他の形も、この説明の一部として含まれる。ＣＳＩを獲得して配信するコストを全エネルギーコストに組み入れることができる。
【００５２】
（ｉｖ）各ノードは、異なる送信機からの相互情報量を完全に積算するものと仮定する。この仮定を近似したものは、レートレス符号が使用されるときに実現することができ、異なるレートレス符号は、異なる時間−周波数拡散符号を使用し、その結果、受信機は符号を区別することができる。また、有限サイズの送信元ワードのレートレス符号は、理想的な特性を有しないものと仮定する。たとえば、オーバーヘッドが、シャノンの限界よりも大きい可能性がある。以下では、レートレス符号の非理想性は無視する。また、１つのノードが、複数の拡散符号及び／又はファウンテン符号を使用して、トランスポートブロックサイズの限界を迂回することも可能である。
【００５３】
（ｖ）明示的な別段の言及がない限り、ネットワークにおけるすべての拡散符号は、完全に直交し、その結果、或るレートレス符号を使用するビットストリーム又はフローの送信は、他のレート符号で符号化されたビットストリームの送信とは干渉しないものと仮定する。
【００５４】
（ｖｉ）また、各ノードは、任意に低い信号対雑音比の信号を受信できるものと仮定し、受信機における同期及びチャネル推定にオーバーヘッドは必要とされないものと仮定する。これは、一定の同期及びチャネル推定のオーバーヘッドが存在する下で理想化された仮定である。
【００５５】
（ｖｉｉ）ノードが情報を復号することに成功したという情報のフィードバック４００は瞬時であるものと仮定され、いかなるオーバーヘッドをも要しない。しかしながら、本明細書で説明する技法は、このフィードバック情報の有限のオーバーヘッド及び遅延した送信が使用されるときにも適用可能である。
【００５６】
（ｖｉｉｉ）送信は、単一のノードが単一の受信ノードへ情報を送信する場合にユニキャストとすることができる。送信は、複数の、場合によっては相関されるノード（複数のフロー）及び／又は複数の宛先ノード（マルチキャスト）を含むように一般化することもできる。
【００５７】
（ｉｘ）チャネルは、遅延分散を示さず、どの時点においても、単一スカラーの複素減衰係数（complex attenuation coefficient）によって特徴付けることができるものと仮定する。しかしながら、この減衰のフェージング（時間変動）の可能性も考慮に入れる。遅延分散が存在する場合、拡散符号が、その影響を減らすのに使用される。
【００５８】
（ｘ）送信元ノードは、宛先ノードが前のコードワードの復号に成功した後にしか、新たなコードワードの送信を開始しないものと仮定する。このように、どの時点においても、送信元ノードからの１つのメッセージしかネットワークには存在しない。
【００５９】
最適化モデル
従来のアドホックルーティングは、以下の自由パラメータ、すなわち、協調するノード、各ノードにおける送信電力、及びノードが送信を行う順序を使用する。
【００６０】
協調リレーネットワークは、ネットワークの各ノードｉについて以下のパラメータ、すなわち、レートレス符号Ｃｉ（ｔ）、拡散符号、送信の開始時刻ｔｉ、及び送信の継続時間τも決定する。
【００６１】
目標は、以下の基準、すなわち、ネットワークの全エネルギー消費、送信元ノードから宛先ノードへの全送信時間、送信のスペクトル効率、及びネットワークの寿命のいずれかの組み合わせを最適化することである。
【００６２】
スペクトル効率の１つの有用な尺度として、送信ノードの周りの「ブロッキングエリア」を定義する（ただし、スペクトル効率の他の尺度も、同様に、本方法で使用することができる）。ブロッキングエリアでは、ノードからの放射が非常に強いので、他の通信を受信することができない。厳密に言えば、ブロッキングエリアのサイズは、受信機の検出しきい値と、環境における伝播状態とに依存する。「ブロッキング時間」は、ノードが送信を行っている時である。ブロッキングエリアとブロッキング時間との積をスペクトル効率の尺度とすることができる。コードワードを送信するのに必要とされる拡散符号の総数は、スペクトル効率を特徴付けるさらに別のパラメータである。
【００６３】
ノードが利用できるエネルギーの量は有限であるものと仮定する。すなわち、ノードはバッテリー動作しているものと仮定する。ネットワークの寿命は、最初のノードが自身の利用可能な全エネルギーを使用した時に「満了し」、動作を停止する。ネットワークの寿命の他の定義は、「その時刻後に、送信元から宛先への可能なルートが存在しなくなるという時刻」、又は「ネットワークが分割するのに要する時間」等である。ネットワーク分割（network partitioning）は、ネットワークを完全に切断された部分に分離する広範囲のトポロジー変更である。これは、進行中のネットワークルーティング及び上位レイヤアプリケーションに対して、突然の重大な混乱を引き起こす可能性がある。
【００６４】
最適化基準は、線形関数又は非線形関数の形にすることもできるし、厳密制約条件の形にすることもできる。最適化基準の例としては、たとえば、コードワードの送信時間と送信エネルギーとの加重和を使用するペナルティ関数、又は、送信時間τに対する厳密制約条件がある。
【００６５】
積算された相互情報量
上記仮定では、積算された相互情報量は以下のように述べることができる。送信元ノードｎ０は、Ｎ個のリレーノードｎｉを介して宛先ノードｎＮ＋１へコードワードを送信する。各ノードは、時刻ｔｉにおいて、継続時間τｉの間、電力Ｐｉ及び拡散符号Ｃｉで送信を開始する。拡散符号Ｃｉは拡散利得ＳＦを有する。指示関数Ｉｉ（ｔ）は、ｔｉ＜ｔ＜ｔｉ＋τｉの場合は１であり、それ以外の場合は０である。受信信号の電力は、最小しきい値電力εよりも大きくなければならない。さらに、伝達関数ｈｉｊは、ノードｉからノードｊへの複素（complex）振幅ベースバンドチャネル利得である。さらに、コードワードは、単位帯域幅に正規化されたエントロピーＨｔａｒｇｅｔを有する。その場合、時刻ｔにおいてノードｉに積算された相互情報量は、
【００６６】
【数１】
2008148299.tif 000003
【００６７】
となる。ここで、Ｎ０は雑音の電力である。この定式化は、残留干渉が雑音のように働き、受信機の結合検出等、どの干渉抑圧メカニズムによっても抑圧されないことを暗に仮定している。
【００６８】
干渉抑圧が使用される場合、上記式の分母は、結合検出受信機の出力における干渉プラス雑音電力に置き換えられる。問題の複雑さを低減するために、ノードの送信電力が一定であるものと仮定する。また、ｔｍｉｎ，０＝０と定義し、且つ、０＜ｉ≦Ｎ＋１の場合はＨｉ（ｔｍｉｎ，ｉ）＝Ｈｔａｒｇｅｔによって暗にｔｍｉｎ，ｉを定義する。
【００６９】
ｔ≧ｔｍｉｎ，ｉという制約条件を課す。換言すれば、どのノードも、そのノードがコードワードを復号した後にしか、送信を開始することができない。さらに、送信時間をｔｉ＋τｉ≦ｔｍｉｎ，Ｎ＋１となるように制約することは理に適っており、その結果、コードワードが復号された後、ノードは送信を行わない。
【００７０】
信号獲得の実際的な要件を考慮したい場合、制約条件Ｐｉ≧εｉを設ける。また、各ノードは、ハードウェア制限による最大電力制約条件Ｐｉ≦Ｐｍａｘも有する。ノードｎｉによって消費される全エネルギーは、
【００７１】
【数２】
2008148299.tif 000004
【００７２】
であり、ネットワークにおける全エネルギーは、
【００７３】
【数３】
2008148299.tif 000005
【００７４】
である。Ｅｉには、受信に必要とされるエネルギー、さらには、チャネル状態情報を取得してそのチャネル状態情報を中央ノードのような適切な受信者へ転送するのに必要とされるエネルギーも含めることができることに留意されたい。
【００７５】
所与の拡散符号Ｃｍのブロッキングエリアは、Ａｍ（ｔ）によって示される。このＡｍ（ｔ）から、スペクトル効率Ｓの尺度を導出することができる。
【００７６】
ペナルティ関数Ｄ（Ｅ０，…，ＥＮ＋１，ｔｍｉｎ，Ｎ＋１，Ｓ）を最小にするものとする。ここで、関数Ｄは、パラメータの線形関数若しくは非線形関数とすることができ、且つ／又は、厳密制約条件を有することができる。たとえば、サービス品質制約条件は、Ｐｒ（ｔｍｉｎ，Ｎ＋１＞ｔａｄｍｉｓｓｉｂｌｅ）＜ｏｕｔａｇｅとすることができる。ここで、ｔａｄｍｉｓｓｉｂｌｅは、メッセージが送信元ノードから宛先ノードへ進むのに許容できる時間であり、ｏｕｔａｇｅは、許容できる通信遮断確率である。
【００７７】
一般的な最適化手順
上記説明は、最適化問題の理論的な定式化を提供する。未知のパラメータの解は、焼きなまし法（simulated annealing）、遺伝的アルゴリズム（genetic algorithms）、モンテカルロシミュレーション（Monte-Carlo simulations）等の従来のあらゆる標準的な最適化方法によって得ることができる。この最適化は、中央ロケーションで行うこともできるし、又は分散形式で行うこともできる。
【００７８】
図７は、送信に消費される全エネルギーの制約条件に従って、コードワードの送信時間を最小にする最適化の一例を示している。
【００７９】
ノード７０１、送信元ノード７０２、及び、宛先ノード７０３のネットワークが与えられた場合、最適化プロセスは、最適な非協調ルート７１１を選択する（７１０）ことによって開始する。ここで、各ノードは、そのノードが十分な相互情報量を積算するとすぐにコードワードを復号する。最適な非協調ルートは、従来の技法に従って選択することができる。
【００８０】
最適なルートの探索を単純化するために、最初に、許容できる全エネルギーの１／Ｎを各ノードに割り当てる（７２０）。これは、全エネルギーの制約条件を自動的に満たす。
【００８１】
エネルギーを割り当てられた最適な非協調ルートから開始し、焼きなまし法を使用して、全送信時間を減少させるノード及び電力設定を見つけることができる。ルートに沿った次のノードがコードワードをまだ復号できるように電力設定及び送信時間を調整する。
【００８２】
焼きなまし法プロセスは、以下のように動作することができる。ノード７３１の複数の対をランダムに選択する（７３０）。選択されたこれらの対のエネルギーを以下のように調整する（７４０）。ノードの一方に割り当てられたエネルギーを小さな量Δだけ増加させ、他方のノードのエネルギーを同じ量だけ減少させる。
【００８３】
エネルギーが調整された一対のノード７４１について、電力設定及び送信時間設定、すなわち上述した制約条件を満たす設定の実現可能性を判断する（７５０）。次に、電力設定を選択して更新する（７６０）。この設定は、ランダムに選択することもできるし、又は代替的に、送信元ノードから宛先ノードへのコードワードの全送信時間が最小となる実現可能な設定を選択することもできる。その結果の送信時間が、前の電力割り当ての送信時間よりも小さい場合には、電力設定を適切に更新する。この結果、送信時間が長くなる場合には、送信時間ペナルティと共に減少する或る確率ｐで更新を行い、たとえそれが性能の減少につながり、最適化中にいずれかの極小値を避けることになっても、電力を更新する。
【００８４】
最適化プロセスは、収束するまで、又は、一定の最大数の繰り返しステップが実行されるまで繰り返す（７７０）。
【００８５】
特定の最適化手順
多数の特別な場合を説明する。これらは、本発明の実施形態の例として機能するが、本発明の一般的な適用範囲を限定するものと解釈されるべきではない。
【００８６】
フラッディング（Flooding）
フラッディング技法の期間中、各ノードは、そのノードがコードワードを復号するとすぐに、時刻ｔ＝ｔｍｉｎ，ｉにおいて最大許容可能電力Ｐｍａｘにて情報の送信を開始する。ノードは、宛先ノードがコードワードを復号するまで送信を続ける。これによって、全送信時間が最小にされる。リレーノードによるどの送信も、たとえ、そのリレーから宛先までの距離が送信元から宛先までの距離よりも長くても、他のノードにおけるこの送信からの干渉の抑圧が完全であるとの仮定の下で、全送信時間の削減につながることは注目すべきである。直観的には、このようなリレーノードによる送信は、宛先により近いノードによる送信を高速化するのに役立ち、したがって、それらの送信の受信機がより早く送信を開始することを可能にし、これによって、全送信時間が減少する。しかしながら、これは、エネルギー、さらにスペクトル資源を浪費する。
【００８７】
スペクトル効率を改善する１つの方法は、互いから十分に分離されたノードの拡散符号を再利用することである。２つのノードｉ及びｊを考え、ノードｋからノードｉへの伝達関数ｈｉｋが、所定のしきい値を超えるか、すなわち、ノードｉが、ノードｋによって受信される相互情報量に「大きく」貢献するか否かを判定する。すべてのノードｋについて、ノードｊからノードｋへの伝達関数ｈｊｋが、必要とされる信号対干渉比であるファクタＺよりも小さい場合、ノードｉ及びｊは、同じ拡散符号を使用することができる。
【００８８】
減分ノード控除
この手法では、最初に、ネットワークのフラッディングを使用して、ルートと電力の割り当てとを選択する。次に、各ノードについて、そのノードがネットワークから控除された場合に、電力消費の減少及び送信時間の増加を決定する。送信時間の増加がしきい値よりも小さい場合、そのノードは控除される。同様に、控除による全送信時間の増加が小さい場合に、ノードのブロッキングエリア及びブロッキング時間による干渉を増加させるノードも控除することができる。
【００８９】
増分ノード追加
この手法では、上述したような最良の非協調ルートにおけるノードから開始する。ネットワークにおける可能性のある各ノードについて、そのノードが協調形式でもルートに含まれる場合に、所与のエネルギー消費及び所与の送信時間についての全送信時間の減少を別個に求める。減少が最大であるノードがルートに追加される。この手順は、さらに別のノードの追加が性能の小さな改善しか与えなくなるまで、又は、参加するノードの個数が所定のしきい値に達するまで繰り返される。
【００９０】
非集中化終了
非集中化手法では、各ノードは、そのノードがコードワードを復号した後に送信を開始する。送信は、宛先ノードに「より近い」ｋ個のノードがコードワードを復号した後に停止される。
【００９１】
好ましい実施形態の例として本発明を説明してきたが、本発明の精神及び範囲内において、他のさまざまな適応及び変更を行えることが理解されるべきである。したがって、本発明の真の精神及び範囲内に入るこのようなすべての変形及び変更をカバーすることが添付の特許請求の範囲の目的である。
【図面の簡単な説明】
【００９２】
【図１】本発明の一実施形態による協調リレーネットワークの図である。
【図２】本発明の一実施形態による協調リレーネットワークの図である。
【図３】本発明の一実施形態によるプロトコルのブロードキャストステップを示す図である。
【図４】本発明の一実施形態によるプロトコルの確認応答ステップを示す図である。
【図５】本発明の一実施形態によるプロトコルの終了ステップを示す図である。
【図６】本発明の一実施形態による同期プロトコルの送信ステップを示す図である。
【図７】本発明の一実施形態による送信時間最適化のブロック図である。
【図１】
2008148299.tif 000006
【図２】
2008148299.tif 000007
【図３】
2008148299.tif 000008
【図４】
2008148299.tif 000009
【図５】
2008148299.tif 000010
【図６】
2008148299.tif 000011
【図７】
2008148299.tif 000012
【外国語明細書】
2008148299.tif 000013
2008148299.tif 000014
2008148299.tif 000015
2008148299.tif 000016
2008148299.tif 000017
2008148299.tif 000018
2008148299.tif 000019
2008148299.tif 000020
2008148299.tif 000021
2008148299.tif 000022
2008148299.tif 000023
2008148299.tif 000024
2008148299.tif 000025
2008148299.tif 000026
2008148299.tif 000027
2008148299.tif 000028
2008148299.tif 000029
2008148299.tif 000030
2008148299.tif 000031
2008148299.tif 000032
2008148299.tif 000033
2008148299.tif 000034
2008148299.tif 000035
2008148299.tif 000036
2008148299.tif 000037
2008148299.tif 000038
2008148299.tif 000039
2008148299.tif 000040
2008148299.tif 000041
2008148299.tif 000042
2008148299.tif 000043
2008148299.tif 000044
2008148299.tif 000045
2008148299.tif 000046
2008148299.tif 000047
2008148299.tif 000048
2008148299.tif 000049
2008148299.tif 000050
2008148299.tif 000051