(57)【要約】      （修正有）【課題】マルチホップ中継ネットワークにおいて、ソースからデスティネーションへの複数の伝送ルートから最良のルートを選択する。【解決手段】ソースノードからデスティネーションノードへの送信メッセージが発生すると（Ｓ５０２）、第１中継段階のノードを経路メトリック計算ノードとして計算を開始する（Ｓ５０４）。経路メトリック計算ノードでは、ソースノードからの到来経路に関する経路メトリックを受信し（Ｓ５０６）、対象ノードへの経路に関する最大経路メトリックを決定し（Ｓ５０８）、次の中継段階の複数のノードへ経路メトリックを送信する（Ｓ５１０）。次の中継段階のノードを経路メトリック計算ノードとし（Ｓ５１２）、計算がデスティネーションノードに達するまで（Ｓ５０６）〜（Ｓ５１０）を繰り返し、最大の経路メトリックを有する経路をたどる（Ｓ５１４）。得られた経路に沿ってメッセージを送信する（Ｓ５１６）。【選択図】図５
2013219764.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも第１無線デバイス及び第２無線デバイスからの信号を受信するように構成され、前記第１無線デバイスから受信される信号から、ソースノードから前記第１無線デバイスへの経路に関する経路メトリックの表示を抽出するように構成され、前記第２無線デバイスから受信される信号から、前記ソースノードから前記第２無線デバイスへの経路に関する経路に関する経路メトリックの表示を抽出するように構成される受信機と、
抽出された前記表示を用いて、前記ソースノードから前記無線中継デバイスへの経路を選択し、選択された前記経路に関する経路メトリックを決定するように構成されるプロセッサと、
選択された前記経路に関する経路メトリックを記憶するように構成されるメモリと、
第３無線デバイスへの選択された経路に関する経路メトリックの指示を送信するように構成される送信機と、を具備する無線中継デバイス。
【請求項２】
前記プロセッサは、前記第１無線デバイスを経由して前記ソースノードから前記無線中継デバイスへの経路と、前記第２無線デバイスを経由して前記ソースノードから前記無線中継デバイスへの経路と、を具備する１セットの経路から最適経路を決定するために、抽出された前記複数の指示を使用するように構成され、前記最適経路を選択するように構成される請求項１に記載の無線デバイス。
【請求項３】
前記プロセッサは、前記ソースノードから前記無線中継デバイスへの１つの経路を選択するために、前記第１無線デバイスと前記無線中継デバイスとの間の経路と、前記第２無線デバイスと前記無線中継デバイスとの間の経路とのそれぞれに関するチャネル状態情報の複数の表示と、抽出された前記複数の表示とを用いるように構成される請求項１の無線デバイス。
【請求項４】
前記プロセッサは、前記ソースノードから前記無線中継デバイスへの１つの経路を選択するために、前記第１無線デバイスと前記無線中継デバイスとの間の経路と、前記第２無線デバイスと前記無線中継デバイスとの間の経路とのそれぞれに関する実効ゲインの複数の表示と、抽出された前記複数の表示とを用いるように構成される請求項１の無線デバイス。
【請求項５】
前記プロセッサは、前記第１無線デバイス及び前記第２無線デバイスの内の１つから前記無線中継デバイスへの経路に関する前記実効ゲインであって、前記ソースノードから前記第１無線デバイス及び前記第２無線デバイスの内の１つまでの経路に関する経路メトリックを乗じ、前記無線中継デバイス上の雑音電力に比例した量を引いた前記実効ゲインとして、選択された前記経路に関する経路メトリックを決定するように構成される請求項４の無線中継デバイス。
【請求項６】
前記プロセッサは１セットの積を計算するように構成され、前記１セットの積は、前記第１無線デバイス及び前記第２無線デバイスごとに、前記無線デバイスから前記無線中継デバイスへの経路に関する実効チャネルゲインであって、前記ソースノードから無線デバイスへの経路に関する経路メトリックを乗じる実効チャネルゲインの積を具備し、１セットの積の内の積を比較して、最も大きな積を決定し、選択された経路として最も大きな積を有する経路を選択するように構成される請求項１の無線中継デバイス。
【請求項７】
増幅及び転送（amplify-and-forward）の無線中継デバイスとして構成される請求項１の無線中継デバイス。
【請求項８】
固定ゲイン増幅及び転送（fixed-gain amplify-and-forward）の無線中継デバイスとして構成される請求項７の無線中継デバイス。
【請求項９】
ソースノードと、
デスティネーションノードと、
請求項１の複数の無線中継デバイスと、を具備し、
前記デスティネーションノードは、
前記複数の無線中継デバイスの内の、少なくとも第１無線中継デバイス及び第２無線中継デバイスから、複数の経路メトリックの各表示を受信するように構成され、
受信された前記経路メトリックを用いて、前記ソースノードから前記デスティネーションノードまでの最適経路を決定するように構成される無線ネットワーク。
【請求項１０】
前記ソースノードから前記デスティネーションノードまでの前記最適経路に沿ってメッセージを送るように構成される請求項９の無線ネットワーク。
【請求項１１】
無線中継デバイスで、少なくとも第１無線デバイス及び第２無線デバイスからの各信号を受信することと、
前記第１無線デバイスから重心される信号は、ソースノードから前記第１無線デバイスへの経路に関する経路メトリックの表示を具備し、前記第２無線デバイスから受信した信号は、前記ソースノードから前記第２無線デバイスへの経路に関する経路メトリックの表示を具備し、
前記第１無線デバイスを経由して前記ソースノードから前記無線中継デバイスへの経路と、前記第２無線デバイスを経由して前記ソースノードから前記無線中継デバイスへの経路とを具備する１セットの経路から１つの経路を選択するために、前記第１無線デバイス及び前記第２無線デバイスから受信した各表示を用いることと、
選択された前記経路について経路メトリックを決定することと、
第３無線デバイスへの選択された前記経路に関する前記経路メトリックの表示を送信することと、を具備する無線通信方法。
【請求項１２】
前記１セットの経路から最適経路を決定することと、前記最適経路を選択することと、を具備する請求項１１の無線通信方法。
【請求項１３】
選択された前記経路に関する経路メトリックを決定することは、
前記第１無線デバイス及び前記第２無線デバイスの内の１つから前記無線中継デバイスへの経路に関する実効ゲインに、前記ソースノードから前記第１無線デバイス及び前記第２無線デバイスの内の１つへの経路に関する経路メトリックを乗じることと、
前記無線中継デバイス上での雑音電力に比例する量を減じることと、を具備する請求項１１の無線通信方法。
【請求項１４】
経路を選択することは、
１セットの積を計算することと、ここで１セットの積は前記第１無線デバイス及び前記第２無線デバイスごとに、前記無線デバイスから前記無線中継デバイスへの経路に関する前記実効チャネルゲインの積は、前記ソースノードから前記無線デバイスへの前記経路に関する前記経路メトリックが乗じられていて、
最大の積を決定するために、前記１セットの積のうちの複数の積を比較することと、
前記最大の積を有する経路を選択することと、を具備する請求項１３の無線通信方法。
【請求項１５】
無線ネットワークにおいて、ソースノードからデスティネーションノードまでの１つの経路を選択する方法は、
第１中継ノードで、
前記ソースノードから前記第１中継ノードまでの複数の経路に関する最大経路メトリックを決定することと、
前記ソースノードから前記第１中継ノードまでの最適経路として前記最大経路メトリックを有する経路を選択することと、
第２中継ノードで、
前記ソースノードから前記第２中継ノードまでの複数の経路に関する最大経路メトリックを決定することと、
前記ソースノードから前記第２中継ノードへの最適経路として前記最大経路メトリックを有する経路を選択することと、
前記デスティネーションノードにおいて、前記ソースノードから前記第２中継ノードへの前記最適経路に関する前記経路メトリックの指示と、前記ソースノードから前記第１中継ノードへの前記最適経路に関する前記経路メトリックの指示と、を受信することと、
前記ソースノードから前記デスティネーションノードまでの前記経路であって、前記デスティネーションノードで、前記ソースノードから前記第２中継ノードまでの前記最適経路に関する前記経路メトリックの前記指示と、前記ソースノードから前記第１中継ノードへの前記最適経路に関する前記経路メトリックの前記指示と、を使用する前記最大経路メトリックを有する前記経路を、前記デスティネーションノードで決定することと、
前記ソースノードから前記デスティネーションノードへの前記最適経路として前記最大経路メトリックを持っている経路を選択することと、を具備する方法。
【請求項１６】
前記最適経路に沿ってメッセージを送信することをさらに具備する請求項１５の方法。
【請求項１７】
プロセッサによって実行された時、前記プロセッサに、請求項１１の方法を行なわせるコンピュータ実行可能な複数の命令を具備するコンピュータプログラム。
【発明の詳細な説明】
【関連出願】
【０００１】
この出願は、２０１２年３月２８日に出願された英国特許出願第１２０５４６５．６号からの優先権の利益に基づき、かつ利益を主張する。出願の全内容は、参照によってここに組み込まれる。
【技術分野】
【０００２】
本明細書で説明する実施形態は、無線通信ネットワークにおいて中継ノードを経由する無線通信、そのようなネットワークでのルート選択に一般的に関連する。
【背景技術】
【０００３】
マシン同士の（Ｍ２Ｍ）通信、スマートグリッドと車両通信に応用を求めった新興通信パラダイムである。
【０００４】
複数のマルチホップ中継ネットワークは、Ｍ２Ｍ通信において多数のノードに関する情報交換の絶え間なく増大する需要を提供することができるネットワークストラクチャであるとされている。マルチホップ中継ネットワークでは、１つあるいはいくつかの中間の中継ノードは、ソースノードから情報を受信し、次に他の中継ノードあるいはデスティネーションノードへそれを転送するために用いられる。
【０００５】
いくつかのマルチホップ中継ネットワークでは、複数の中継ノードは、単にソースノードからの、あるいは固定ゲインを持った他の中継ノードからの信号を増幅し、次に他の中継あるいはデスティネーションへ増幅された情報を転送する。そのような中継技術は「固定ゲイン増幅及び転送（fixed-gain amplify-and-forward）」技術と呼ばれる。各中継での各受信信号が、チャネルの瞬間電力に依存するゲインによって増幅される場合に、伝送プロトコルは「可変ゲイン増幅及び転送（variable-gain amplify-and-forward）」と呼ばれる。他の中継システムでは、各受信信号は、各中継ノードで検出され、再符号化され、次に転送される。そのような中継プロトコルは「復号及び転送（decode-and-forward）」と呼ばれる。復号及び転送は、増幅及び転送よりもよい性能をもたらすが、一方、中継ノードではより高度な複雑性の影響を受けやすいことが知られている。いくつかの応用シナリオでは、単純な中継ノードが望まれるが、増幅及び転送、特に固定ゲイン増幅及び転送技術はより魅力的である。
【０００６】
莫大な数のノードに関する情報交換の絶え間なく増大する需要では、Ｍ２Ｍ通信は、全ての可能な伝送ルートの間から、どのようにソースからデスティネーションへの信号伝送に関する最良のルートを選択するかを含む多くの挑戦に直面する。直観的に、すべての伝送リンクのチャネル状態情報（ＣＳＩ）が各ノードで知られていると仮定すると、すべての可能なルートの上の全数検索は、最適ルートを求めるために行なうことができる。しかしながら、これは、ホップの数としての中継数が増加するとともに導入される禁止的な複雑性のために実際上実現可能ではない。
【図面の簡単な説明】
【０００７】
以下、実施形態は、ほんの一例として、以下の添付図面を参照して、説明される。
【図１】図１は、実施形態にしたがうマルチホップ中継ネットワークを説明する。
【図２】図２は、複数の段階間での複数のチャネルに関する実効ゲインと、各段階でスケールされた雑音電力の表示と、を指示する複数のパラメータを示す実施形態にしたがうマルチホップ中継ネットワークを説明する。
【図３ａ】図３ａは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｂ】図３ｂは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｃ】図３ｃは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｄ】図３ｄは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｅ】図３ｅは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｆ】図３ｆは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図３ｇ】図３ｇは、実施形態にしたがうソースノードからデスティネーションノードまでの１つの経路を選択する方法におけるステップを説明する。
【図４】図４は、実施形態にしたがう無線中継ノードの概略図である。
【図５】図５は、実施形態にしたがう無線ネットワークにおける１つの経路を選択する方法のフローチャートである。
【図６】図６は、実施形態において用いられる経路選択アルゴリズム及び全数検索に関して、異なるホップ数に必要とされる比較数を示すグラフである。
【図７】図７は、実施形態において用いられる経路選択アルゴリズム及び全数検索に関して、段階当たりの異なるノード数に必要とされる比較数を説明する。
【図８】図８は、全数検索によって選択される複数の経路に関する停止確率に比較して、実施形態によって選択される複数の経路に関する停止確率を示す。
【発明を実施するための形態】
【０００８】
実施形態において、無線中継デバイスは、少なくとも第１無線デバイス及び第２無線デバイスからの信号を受信するように構成され、第１無線デバイスから受信される信号から、ソースノード（起点ノード）から第１無線デバイスへの経路に関する経路メトリックの表示を抽出するように構成され、第２無線デバイスから受信される信号から、ソースノードから第２無線デバイスへの経路に関する経路に関する経路メトリックの表示を抽出するように構成される受信機と、  
抽出された表示を用いて、ソースノードから無線中継デバイスへの経路を選択し、選択された経路に関する経路メトリックを決定するように構成されるプロセッサと、  
選択された経路に関する経路メトリックを記憶するように構成されるメモリと、  
第３無線デバイスへの選択された経路に関する経路メトリックの指示を送信するように構成される送信機と、を具備する。
【０００９】
実施形態において、プロセッサは、第１無線デバイスを経由してソースノードから無線中継デバイスへの経路と、第２無線デバイスを経由してソースノードから無線中継デバイスへの経路と、を具備する１セットの経路から最適経路を決定するために、抽出された複数の指示を使用するように構成され、最適経路を選択するように構成される。
【００１０】
実施形態において、プロセッサは、ソースノードから無線中継デバイスへの１つの経路を選択するために、第１無線デバイスと無線中継デバイスとの間の経路と、第２無線デバイスと無線中継デバイスとの間の経路とのそれぞれに関するチャネル状態情報の複数の表示と、抽出された複数の表示とを用いるように構成される。
【００１１】
実施形態において、プロセッサは、ソースノードから無線中継デバイスへの１つの経路を選択するために、第１無線デバイスと無線中継デバイスとの間の経路と、第２無線デバイスと無線中継デバイスとの間の経路とのそれぞれに関する実効ゲインの複数の表示と、抽出された複数の表示とを用いるように構成される。
【００１２】
実施形態において、プロセッサは、第１及び第２無線デバイスの内の１つから無線中継デバイスへの経路に関する実効ゲインであって、ソースノードから第１及び第２無線デバイスの内の１つまでの経路に関する経路メトリックを乗じ、無線中継デバイス上の雑音電力に比例した量を引いた実効ゲインとして、選択された経路に関する経路メトリックを決定するように構成される。
【００１３】
実施形態において、プロセッサは１セットの積を計算するように構成され、一連の積は、第１及び第２無線デバイスごとに、無線デバイスから無線中継デバイスへの経路に関する実効チャネルゲインであって、ソースノードから無線デバイスへの経路に関する経路メトリックを乗じる実効チャネルゲインの積を具備し、一連の積の内の積を比較して、最も大きな積を決定し、選択された経路として最も大きな積を有する経路を選択するように構成される。
【００１４】
実施形態において、無線中継デバイスは、増幅及び転送（amplify-and-forward）無線中継デバイスとして構成される。
【００１５】
実施形態において、無線中継デバイスは、固定ゲイン増幅及び転送（fixed-gain amplify-and-forward）無線中継デバイスとして構成される。
【００１６】
実施形態において、無線ネットワークは、ソースノード（起点ノード）と、  
デスティネーションノード（宛先ノード）と、  
実施形態にしたがう複数の無線中継デバイスと、を具備し、  
デスティネーションノードは、複数の無線中継デバイスの内の、少なくとも第１無線中継デバイス及び第２無線中継デバイスから、複数の経路メトリックの各表示を受信するように構成され、  
受信された経路メトリックを用いて、ソースノードからデスティネーションノードまでの最適経路を決定するように構成される。
【００１７】
実施形態において、無線ネットワークは、ソースノードからデスティネーションノードまでの最適経路に沿ってメッセージを送るように構成される。
【００１８】
実施形態において、無線通信方法は、無線中継デバイスで、少なくとも第１無線デバイス及び第２無線デバイスからの各信号を受信することと、  
第１無線デバイスから重心される信号は、ソースノードから第１無線デバイスへの経路に関する経路メトリックの表示を具備し、第２無線デバイスから受信した信号は、ソースノードから第２無線デバイスへの経路に関する経路メトリックの表示を具備し、  
第１無線デバイスを経由してソースノードから無線中継デバイスへの経路と、第２無線デバイスを経由してソースノードから無線中継デバイスへの経路とを具備する一連の経路から１つの経路を選択するために、第１無線デバイス及び第２無線デバイスから受信した各表示を用いることと、  
選択された経路について経路メトリックを決定することと、  
第３無線デバイスへの選択された経路に関する経路メトリックの表示を送信することと、を具備する。
【００１９】
実施形態において、無線通信方法は、１セットの経路から最適経路を決定することと、最適経路を選択することと、を具備する。
【００２０】
実施形態において、選択された経路に関する経路メトリックを決定することは、第１及び第２無線デバイスの内の１つから無線中継デバイスへの経路に関する実効ゲインに、ソースノードから第１及び第２無線デバイスの内の１つへの経路に関する経路メトリックを乗じることと、無線中継デバイス上での雑音電力に比例する量を減じることと、を具備する。
【００２１】
実施形態において、経路を選択することは、  
１セットの積を計算することと、ここで１セットの積は第１及び第２無線デバイスごとに、無線デバイスから無線中継デバイスへの経路に関する実効チャネルゲインの積は、ソースノードから無線デバイスへの経路に関する経路メトリックが乗じられていて、  
最大の積を決定するために、１セットの積のうちの複数の積を比較することと、  
最大の積を有する経路を選択することと、を具備する。
【００２２】
実施形態において、無線ネットワークにおいて、ソースノードからデスティネーションノードまでの１つの経路を選択する方法は、  
第１中継ノードで、ソースノードから第１中継ノードまでの複数の経路に関する最大経路メトリックを決定することと、ソースノードから第１中継ノードまでの最適経路として最大経路メトリックを有する経路を選択することと、  
第２中継ノードで、ソースノードから第２中継ノードまでの複数の経路に関する最大経路メトリックを決定することと、ソースノードから第２中継ノードへの最適経路として最大経路メトリックを有する経路を選択することと、  
デスティネーションノードにおいて、ソースノードから第２中継ノードへの最適経路に関する経路メトリックの指示と、ソースノードから第１中継ノードへの最適経路に関する経路メトリックの指示と、を受信することと、  
ソースノードからデスティネーションノードまでの経路であって、デスティネーションノードで、ソースノードから第２中継ノードまでの最適経路に関する経路メトリックの指示と、ソースノードから第１中継ノードへの最適経路に関する経路メトリックの指示と、を使用する最大経路メトリックを有する経路を、デスティネーションノードで決定することと、  
ソースノードからデスティネーションノードへの最適経路として最大の経路メトリックを持っている経路を選択することと、を具備する。
【００２３】
実施形態において、方法は最適経路に沿ってメッセージを送信することをさらに具備する。
【００２４】
一実施形態は、プロセッサによって実行された時、プロセッサに、上に提示されるような方法を行なわせるコンピュータ実行可能な複数の命令を具備するコンピュータプログラムを提供する。コンピュータプログラムは記憶媒体あるいは信号媒体で具体化されるかもしれない。記憶媒体は、光学的記憶手段、磁気記憶手段、あるいは電子記憶手段を含んでいるかもしれない。
【００２５】
説明される実施形態は、特定のハードウェアデバイス、適切なソフトウェアによって構成された多目的デバイスあるいは両方の組合せを組み込むことができる。態様は、完全なソフトウェア実行、あるいは（プラグインのような）既存ソフトウェアの変更あるいは拡張に関してアドオンのコンポーネントとして、ソフトウェア製品で具体化することができる。そのようなソフトウェア製品を記憶媒体（例えば光ディスクあるいはＦＬＡＳＨメモリのような大記憶メモリ）あるいは（ダウンロードのような）信号媒体で具体化することはできるかもしれない。実施形態に適している特定のハードウェアデバイスは、ＡＳＩＣ、ＦＰＧＡあるいはＤＳＰのような特定用途向けデバイス、あるいは他の専用機能ハードウェア手段を含んでいる可能性がある。読者は、ソフトウェアまたはハードウェアにおける実施形態の前述の議論のどれも、未発見のまたは未定義の実行手段での発明の将来の実行を制限することはないことを理解するだろう。
【００２６】
図１は、マルチホップ中継ネットワーク１００の実施形態を示す。ネットワーク１００は、ソースノード１０２、デスティネーションノード１０４、及び４つの中継段を有している。各中継段では、４つの中継ノード１０６がある。この実施形態では、中継プロトコルは増幅及び転送である。本発明の実施形態は、停止確率が最小化されるように、ソースノード１０２からデスティネーションノード１０４までの最適経路を求める方法に関係がある。
【００２７】
図１に示されるマルチホップネットワークは、Ｍ−１個の中継段を持ったＭ−ホップ中継システムへ一般化されてもよい。各段では、複数の（例えばＬ個の）中継ノードがある。その後、ソースからデスティネーションへの最適経路を求める問題は、Ｉ＝ＬＭ−１の中で、以下によって与えられる停止確率が最小になるような最適経路を求めることである。
【数１】
2013219764.tif 000003
【００２８】
ここで、γｅ２ｅは選択されたルートに関する端末間のＳＮＲであり、γｔｈは所定の閾値である。したがって、最小の停止確率を持ったルートを選択することは、最大の末端間ＳＮＲを持ったルートを選択することに等しい。すなわち、ｉ番目のルートが以下のように選択されることに等しい。
【数２】
2013219764.tif 000004
【００２９】
ここで、γ（ｉ）はｉ番目の経路についての末端間ＳＮＲである。
【００３０】
与えられたルートｉについては、ソースからデスティネーションへの末端間ＳＮＲは、以下で与えられる。
【数３】
2013219764.tif 000005
【００３１】
上記の式において、
【数４】
2013219764.tif 000006
【００３２】
ここで、
【数５】
2013219764.tif 000007
【００３３】
は、ｍ段でのｉ番目の経路からなるノード上での白色ガウス雑音の電力であり、
【数６】
2013219764.tif 000008
【００３４】
は、１つのホップ当たりの平均ＳＮＲである。
【００３５】
さらに、ｈ（ｉ）ｍは、（ｍ−１）番目の段とｍ番目の段との間のｉ番目の経路上でのチャネルである。ｈ（ｉ）ｍはチャネル伝達特性を定義する複素数である。送信された信号の時間分散に直面しない場合、それは平坦フェージングシステムのインパルス応答と考えられてもよい。
【００３６】
実施形態は、直交周波数分割多重（ＯＦＤＭ）のような適切なマルチキャリア方法を用いることにより、周波数選択性フェージングシステムに拡張することができる。この場合、中継を行なう場合、サブキャリアはそれぞれ独立して考慮されてもよく、あるいは、ｈ（ｉ）ｍはチャネルインパルス応答のノルムである、あるいは同等に、チャネル周波数応答のノルムであるとしてもよい。位相情報は必要ではなく、振幅情報だけ必要なので、ノルムを使用することができることに注意する。
【００３７】
Ａ（ｉ）ｍは、ｍ番目の段での対応する増幅係数である。増幅及び転送プロトコルが使用される場合、ｉ番目の経路のｍ番目の段階での無線ノードは、（ｍ＋１）番目の段階での無線ノードにメッセージを送信する前に、この係数だけでメッセージの振幅をスケールする。この増幅は、多くの方法において遂行することができ、例えば、アナログ演算増幅器回路は用いられてもよく、あるいは、信号は、ディジタルからアナログへの変換に先立ってディジタルでスケールされてもよい。増幅係数は、多くの異なる方法によって規定されてもよい。そのような方法の２つの例は、可変ゲイン増幅及び転送（variable gain amplify and forward）と、固定ゲイン増幅及び転送（fixed gain amplify and forward）である。
【００３８】
実施形態において、固定ゲイン増幅及び転送プロトコルは用いられ、また、増幅係数は次で与えられる：
【数７】
2013219764.tif 000009
【００３９】
ここでＥは期待値を表わす。
【００４０】
以下、量Ｘ（ｉ）ｍ及びσ（ｉ）ｍは、規定され、γ（ｉ）は、これらの量から決定することができる。仮に、
【数８】
2013219764.tif 000010
【００４１】
とする。Ｘ（ｉ）ｍは、以前の段で適用される増幅係数、及び増幅信号が運ばれるチャネルを考慮すると、チャネルの等価ゲインである。実施形態において、上記において述べられるように、Ｘ（ｉ）ｍは計算される。以前の段からの増幅係数の情報が未知である別の実施形態では、受信機中継ノードは、Ｘ（ｉ）ｍを推定するためにパイロット信号を用いてもよい。
【００４２】
σ（ｉ）ｍは、ｉ番目の経路上のｍ番目の中継での雑音電力のスケールされたバージョンである。これは、停止閾値γｔｈに現実の雑音分散を掛けることにより決定される。それは各ノードで独立して推定することができる。停止閾値γｔｈは設計パラメータである。上記の式（３）は、整理されて、ある経路（例えばｉ番目の経路）に関して、γ（ｉ）が所定の閾値以下である確率が、以下で与えられることを示すことができる。
【数９】
2013219764.tif 000011
【００４３】
停止確率Ｐｏｕｔは以下で与えられる。
【数１０】
2013219764.tif 000012
【００４４】
複数の経路は、複数の経路の間に複数のオーバーラップリンクがあるように、分離可能ではない。
【００４５】
以下、単純なネットワーク例が、停止確率を最小化する、増幅及び転送マルチホップ中継ネットワークの実施形態において、最適経路がどのように見つかるか示すために使用される。
【００４６】
以下に検討されるネットワークは、各段に２つの中継があり、４つのホップ及び３つの段を有している。そのようなネットワークは図２に示される。ここで各ノード／リンクの各段に関して対応するパラメータ（Ｘ（ｉ）ｍ及びσ（ｉ）ｍ）も与えられる。
【００４７】
停止確率が以下に与えられることは、上記に与えられる複数の式からわかる。
【数１１】
2013219764.tif 000013
【００４８】
いくつかの数学的な操作の後、停止確率は以下のように書き直すことができる。
【数１２】
2013219764.tif 000014
【００４９】
ここで、
【数１３】
2013219764.tif 000015
【００５０】
【数１４】
2013219764.tif 000016
【００５１】
上記の計算では、Ａ及びＢの値が何度も使用され、さらに、一旦比較が行われて最大値を決定する（例えばＡまたはＢの計算において）と、後の計算では、ちょうど最高数量が必要とされ、かつ非最高数量は棄却されることは注意する。
【００５２】
したがって、次のアルゴリズムを推定して、任意の数のホップ及び中継を有する増幅及び転送のマルチホップ中継ネットワークに関する最適経路を見つけることができる。
【００５３】
Ｍ段を持った一般的なマルチホップネットワークを考慮する。ここで、ｌｍ個の中継がｍ段目に存在する。ゼロ番目の段は、ソース（ｌ０＝１）であるとする。Ｍ番目の段はデスティネーション（ｌＭ＝１）であるとする。したがって、ｌｍ−１個の経路は、段階ｍ−１での各中継から、段階ｍでの各中継へ導く。明確にするために、そのような経路はそれぞれ１つの枝として表わされる。（ｍ−１）番目の段からｍ番目の段までｌｍ１ｌｍ個の枝が存在する。この実施形態では、複数の枝は、図２に示されるパターンに順次分類されるが、他の分類規約を使用することができる。したがって、（ｍ−１）番目の段からｍ番目の段までのｉ番目の枝ゲインは、Ｘｍ（ｉ）である。さらに、ｍ番目の段におけるｒ番目の中継は、ノイズによって影響される。それはσｍ（ｒ）によって表わされる（停止閾値γｔｈによってスケールされる）電力を有する。
【００５４】
この実施形態では、ｍ番目の中継段では、lm-1個の枝（１つの中継当たり一つ）は、ｒ番目（ｒ＝１，…，ｌｍ）の中継に（ｍ−１）番目の中継段を接続する。ｍ番目の段でのｒ番目の中継については、これらの枝がそれぞれゲインＸｍ（（ｒ−１）ｌｍ−１＋１），…，Ｘｍ（ｒｌｍ−１）を有している。
【００５５】
さらに、経路メトリックは、（ｍ−１）番目の段で各ノードと関連している。それは、ルート情報への前記ノードを選ぶ質の尺度である。Ｑ０＝１はソースでの経路メトリックを表わして、（ｍ−１）番目の段でｑ番目のノードに関連した経路メトリックをＱｍ−１（ｑ）と表わす。経路メトリックは、次の式によるｍ番目の中継段のｒ番目のノードで更新される。
【００５６】
Qm(r) = maxq{Qm-1(q) Xm((r-1)lm-1+q)} -σｍ(r)      (13)
言葉では、経路メトリックは、各経路メトリックと、対応する枝ゲインとの積を考慮し、この量を最大化し、次に、ｒ番目のノードに関するスケールされた雑音電力を減じることによって、ｍ番目の中継段のｒ番目のノードで更新される。新しいメトリックに対応する経路は、ｍ番目の中継段でメモリにおいて保存される。
【００５７】
当業者は、更新手順の結果を変更せずに、スケール化された雑音電力を減じた後に、最大化演算をも行なうことができることを認識するだろう。
【００５８】
実施形態にしたがう方法は以下のように要約される。ノードごとに各段で、第２段階からスタートして、経路ごとに対応する経路メトリックを計算し、ノードごとにＬ個の到来経路についての経路メトリックを比較し、他のものをすべて廃棄する間に最大の経路メトリックを持っている経路を予約する。したがって、ある段でのノードごとに、１つのルートだけが予約されている。デスティネーションノードに到着するまで、この処理は繰り返す。その後、アルゴリズムは、最適ルートを見つけるためにさかのぼり、生存者経路を出力する。
【００５９】
上記の方法の一例が下に図３ａから図３ｇを参照して説明される。
【００６０】
図３ａは、ソースノード３０１からデスティネーションノード３４１へネットワーク３００を介してメッセージを送信することに関する最適経路の判定において用いられる変数について実例の複数の値を示す。
【００６１】
図３ｂは、方法での第１ステップを示す。第１ステップは、第２段階で第１ノード３２１について２つの到来経路に関する経路メトリックを計算することである。第１段階での第１ノード３１１を経由する経路についての経路メトリックは、（１−０．１）＊１である。また、第１段階での第２ノード３１２を介する経路についての経路メトリックは、（４−０．２）＊３である。２つの経路メトリックは比較され、段階２での第１ノード３２１について第２の到来経路が選択され（第２ノード３１２を経由する経路）、（４−０．２）＊３＝１１．４の出力は第１ノード３２１のメモリに入れられる。第１段階における第１ノード３１１を経由する経路は、廃棄され、図３ｂにおいて破線として示される。
【００６２】
図３ｃは、方法における第２ステップを示す。第２ステップでは、第２ノード３２２についての２つの到来経路に関する経路メトリックが計算される。これらは、第１段階での第１ノード３１１を経由する経路については（１−０．１）＊２であり、第１段階での第２ノード３１２を経由する経路については（４−０．２）＊４である。その後、これらは比較され、段階２での第２ノードについての第２到来経路が選択され、それは第１段階での第２ノード３１２を経由する経路である。（４−０．２）＊４＝１５．２の出力は、第２段階で第２ノード３２２のメモリに入れられる。
【００６３】
図３ｄは、方法における第３ステップを示す。第３段階での第１ノード３３１についての２つの到来経路に関する経路メトリックが計算される。これらは、以前の段における複数のノードによって計算された経路メトリックを用いて計算される。複数の経路メトリックは、第２段階における第１ノード３２１を経由する経路について（１１．４−０．３）＊４として計算され、第２段階における第２ノード３２２を経由する経路について（１５．２−０．４）＊２として計算される。計算された複数の経路メトリックは比較され、段階３での第１ノードに関する第１到来経路（第２段階での第１ノード３２１を経由する経路）が選択され、（１１．４−０．３）＊４＝４４．４の出力は、第１ノード３３１のメモリに入れられる。
【００６４】
図３ｅは、方法における第４ステップを示す。第３段での第２ノード３３２について２つの到来経路に関する経路メトリックが計算される。これらは、第２段階における第１ノード３２１を経由する経路について（１１．４−０．３）＊３として計算され、第２段階３２２における第２ノードについて（１５．２−０．４）＊１として計算される。複数の計算された経路メトリックは比較され、段階３での第２ノード３３２について第１到来経路（すなわち、第２段階での第１ノード３２１を経由した経路）が選択され、（１１．４−０．３）＊３＝３３．３の出力は、第２ノード３３２のメモリに入れられる。
【００６５】
図３ｆは第５ステップを示す。第５ステップでは、最終段階でのデスティネーションノード３４１について２つの到来経路に関する経路メトリックが計算される。これらは、第３段での第１ノード３３１を経由する経路について（４４．４−０．５）＊１であり、第３段での第２ノード３３２を経由する経路について（３３．３−０．６）＊２である。これらの２つの経路メトリックは比較され、デスティネーションノード３４１について第２到来経路（第２ノード３３２を経由する経路）が選択される。
【００６６】
図３ｇは第６ステップを示す。第６ステップでは、生存者経路はさかのぼられ、最適ルートとして選択される。
【００６７】
複数の図において示される複数のパラメータだけが、複数のステップのそれぞれに必要とされることに注意する。したがって、各ノードは、複数の前ノードへのチャネルと、前ノードまでの経路に関する経路メトリックと、についての情報を必要とする。
【００６８】
図４は、実施形態にしたがう無線中継デバイス４００を示す。無線中継デバイス４００は、受信機４０２及び送信機４０４を有する。使用にあたり、無線中継デバイスは受信機４０２で複数の信号を受信し、送信機４０４で、複数の受信信号に基づいた複数の信号を送信する。実施形態では、無線中継デバイス４００は、増幅及び転送中継デバイスであり、信号が送信される前に、受信信号を増幅するアンプを含んでいる。
【００６９】
無線中継デバイス４００は、複数のマシンコード命令を実行するように作動するプロセッサ４０６を具備する。プロセッサ４０６は、上述した方法に従って経路メトリック計算について命令４０８を実行することを示される。無線中継デバイス４００は、上記で説明した方法に従って計算された最大の経路メトリックの表示４１２を記憶するメモリ４１０を具備する。
【００７０】
使用にあたり、無線中継デバイス４００は、他の無線デバイスからの各表示を受信する。それは他の無線中継デバイスでもよいし、ソースノードとして動作するデバイスでもよい。その表示は、無線中継デバイス４００が一部分である無線ネットワークを通して送信されるメッセージに関する経路メトリックを含んでいる。無線中継デバイスのプロセッサ４０６は、到来経路のすべてについて最大の経路メトリックを決定するために表示を用い、メモリ４１０に最大の経路メトリックの表示を記憶する。送信機４０４は、無線ネットワークの他の複数のノードに、最大の経路メトリックの表示を送信する。
【００７１】
したがって、無線中継デバイス４００は、無線ネットワークを通る経路の選択を促進する。無線中継デバイスは、一旦計算が提案されたデスティネーションノードに達したならば、最適経路のもどりを促進するために、最大の経路メトリックを持っている経路の表示を記憶してもよい。
【００７２】
経路メトリック計算の指示は、別個のソフトウェア要素として示されているが、読者は多くの異なる方法でコンピュータにソフトウェアを導入することができることを認識する。例えば、記憶媒体からなるコンピュータプログラムは、コンピュータに導入され、その結果、記憶された命令をコンピュータに転送することができる。同等に、そのような命令を有するコンピュータへ信号を送ることができる。さらに、コンピュータプログラムを導入する際に、読者は、ソフトウェアの一部が多くのコンポーネントからなり、そのいくつかは新しくてもよく、その他は既にコンピュータに提供されていると仮定されてもよいことを認識するだろう。例えば、コンピュータは、既知のタイプのオペレーティングシステムが搭載されると合理的に仮定されてもよい。また、コンピュータプログラムは、そのようなオペレーティングシステムの存在に基づいて開発されてもよい。あのように開発されるコンピュータプログラムと、オペレーティングシステムの設備との間の相互作用は、図４に示されるような通信設備エレメントの定義につながる。したがって、任意のコンピュータプログラムも、新しい、スタンドアロンの製品として、あるいは既存製品へのプラグインとして開発されてもよい。
【００７３】
図５は、実施形態にしたがい、ソースノードからデスティネーションノードへのメッセージを送信する方法を示すフローチャートである。
【００７４】
ステップＳ５０２では、ソースノードが、デスティネーションノードへ送信されるメッセージを要求する場合、方法はスタートする。
【００７５】
ステップＳ５０４では、計算は第１中継ノードに移る。ステップＳ５０６では、中継ノードは、ソースノードから対象としているノードまでの複数の経路に関する各経路メトリックの表示を受信する。
【００７６】
ステップＳ５０８では、中継ノードは、ソースノードから対象としている中継ノードまでの経路に関する最大の経路メトリックを決定する。これは上述の式（１３）を用いて決定されてもよい。
【００７７】
ステップＳ５１０では、最大の経路メトリックは次の段における複数のノードに送信される。
【００７８】
次の段がデスティネーションノードを含んでいる場合、計算はデスティネーションノードによって実行されるステップＳ５１４へ移動する。次の段がデスティネーションノードを含んでいない場合、方法は、Ｓ５１２で次の中継ノードへ移り、ステップＳ５０６−Ｓ５１０はその中継ノードで繰り返される。
【００７９】
ステップＳ５１４に到達する場合（計算がデスティネーションノードに達する場合）、最大の経路メトリックを有する経路は決定され、デスティネーションノードからソースノードまで戻る。各ノードは、最適経路の戻りを促進するために、最大の経路メトリックを持っている経路に対応する以前の段に、中継ノードの表示を記憶してもよい。
【００８０】
一旦最適経路をさかのぼったならば、メッセージは、ステップＳ５１６でソースノードからデスティネーションノードへ送信される。
【００８１】
Ｍ個のホップを有するネットワーク、及び各ホップでＬ個の中継ノードに関して、全数検索では、比較すべきＬ（Ｍ−１）個の経路がある。各経路については、末端間ＳＮＲを計算する必要がある（γ（ｉ））。また、各段の各リンクに関するチャネル状態情報のグローバルな知識は、これらのＳＮＲ値を計算し、かつ比較を行なうために必要である。
【００８２】
実施形態では、中間のＭ−２段では、Ｌ２個の比較は各段で必要であり、Ｌ個の比較はデスティネーションノードでの最後の段で必要である。したがって、比較の総数は、Ｌ２（Ｍ−２）＋Ｌであり、この数は、ＬとＭが大きい場合、特に大規模ネットワークにおけるＬ（Ｍ−１）よりはるかに小さい。
【００８３】
図６は、全数検索について異なるＭに必要な比較数、及び実施形態において用いられる経路選択アルゴリズムを示す。
【００８４】
図７は、全数検索について異なるＬに必要な比較数、及び実施形態において用いられる経路選択アルゴリズムを示す。
【００８５】
さらに、全数検索を用いることと比較して、グローバルチャネル情報は、実施形態を用いることにより最適経路を求めるために必要ではない。各ノードについては、以前の段と、このノードへのすべての到来経路の現在の段との間のチャネル状態情報だけが必要である。別の言葉では、受信機でのチャネル状態情報だけが各中継ノードで必要である。
【００８６】
本明細書で説明するアルゴリズムを用いる実施形態は、低複雑度という長所を持つ。
【００８７】
この理由のうちの１つは、実施形態では、各ノードは、次の段での複数のノードへの１つの経路に関する経路メトリックの表示を送るということである。これは、ノード数が増加しても複雑さが大幅に増加しないので、スケーラブルなアルゴリズムを用いる実施形態になる。
【００８８】
図８は、上述した方法の実施形態によって選択された経路に関する停止確率と、全数検索に関する停止確率との比較を示す。これは、全数検索としての停止確率の観点では、実施形態が同じ性能を達成することができることを示す。
【００８９】
実施形態は、各段で任意の数（必ずしも同数でなく）の中継を有し、及び任意のフェージングチャネルに関する、中継ネットワークに適用可能である。
【００９０】
さらに、実施形態は、複数のソース／デスティネーションのノードを有する複数の中継システムのための経路選択を許容する。そのような場合では、１つのソースノードは、まず経路選択を行い、次いで第２ソースノードの経路選択が続く。これらの実施形態は貪欲なアルゴリズムを実行する。遅延に強いネットワークのようないくつかの応用シナリオでは、複数のソースノードを、それらが（時間、周波数、または空間領域で）選択した複数の経路の間で、重複しないように保証する方法でスケジュールすることができる。
【００９１】
ある実施形態が説明さているが、これらの実施形態はほんの一例として提示されていて、発明の範囲を制限するようには意図されない。実際、本明細書で説明する新規な方法、システム、デバイス及びネットワークは、様々な他の形式で具体化されてもよい。さらに、様々な省略、置換及び変更は、発明の精神から外れずになされてもよい。例えば、式（４）において与えられた固定ゲイン増幅係数の代わりとなる係数が使用されてもよい。添付のクレーム及びその均等物は、発明の範囲及び精神の中にあるように、そのような形式あるいは変更を保護するように意図される。
【図１】
2013219764.tif 000017
【図２】
2013219764.tif 000018
【図３ａ】
2013219764.tif 000019
【図３ｂ】
2013219764.tif 000020
【図３ｃ】
2013219764.tif 000021
【図３ｄ】
2013219764.tif 000022
【図３ｅ】
2013219764.tif 000023
【図３ｆ】
2013219764.tif 000024
【図３ｇ】
2013219764.tif 000025
【図４】
2013219764.tif 000026
【図５】
2013219764.tif 000027
【図６】
2013219764.tif 000028
【図７】
2013219764.tif 000029
【図８】
2013219764.tif 000030
【外国語明細書】
2013219764000001.pdf