(57)【要約】送信元ノードと宛先ノードの間の所望のスループット課題を達成するためにマルチキャリア・マルチホップネットワークにおけるリンクのトーン、電力、スケジューリング及びルーティングを共同して決定するための方法が提供される。方法は、メッシュネットワーク内の複数のノードの各々の間の各リンクに適用する電力、スケジューリング及びフロー制限のようなノードトラフィック制限の下で、各宛先ルータによって受信されるスループットを効果的に向上又は最適化する。
2010530177.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにおいて複数のノード間でデータを送信するための方法であって、該複数のノードが複数の無線リンクを介して相互接続され、該方法が、
該複数のノードから選択された各送信元−宛先ペアについての少なくとも１つの所望のデータスループット特性及び該複数のノードに対応付けられたリンクルーティング制限のセットに基づいて、該複数のノードのうちの少なくとも２つの間でデータを送信するための少なくとも１つのリンクルーティング特性を決定するステップ、及び
該少なくとも１つのリンクルーティング特性に従って該複数のノード間でデータを送信するステップ
からなる方法。
【請求項２】
請求項１の方法において、前記少なくとも１つのリンクルーティング特性が、前記複数の無線リンクに割り当てられたトーン数、該トーンの各々に対応付けられた送信電力、各送信元／宛先ペアについてのルーティング経路及び各ルーティング経路を介して送信される送信元／宛先トラフィック量のうちの少なくとも１つを含む、方法。
【請求項３】
請求項２の方法において、前記決定するステップがさらに、
前記複数の無線リンクに対応付けられた信号対干渉プラスノイズ比に基づいて該複数の無線リンクの各々に少なくとも1つのトーンを割り当てるステップ、及び
前記少なくとも１つのデータスループット特性及び前記複数のノードの各々に対応付けられた電力制限に基づいて、割り当てられた該トーンの各々に送信電力を割り当てるステップ
を備える方法。
【請求項４】
請求項１の方法において、前記リンクルーティング制限のセットがルーティングの制限、メディアアクセスの制限及び物理層の制限の少なくとも１つを含む、方法。
【請求項５】
請求項１の方法において、前記決定するステップがさらに、
前記所望のデータスループット特性を達成するために、決定された前記少なくとも１つのリンクルーティング特性に対応するリンクスケジュールのセットを選択するステップを備え、前記送信するステップが、選択された該リンクスケジュールに基づいて該データを送信するものである、方法。
【請求項６】
請求項１の方法において、前記少なくとも１つのリンクルーティング制限が、前記複数のノードにおける１つのノードが前記複数の無線リンクのうちの１つで、かつ、複数のトーンのうちの１つで送信する時間の長さを示すノード毎の平均合計電力制限である、方法。
【請求項７】
請求項１の方法において、前記決定するステップがさらに、
前記少なくとも1つのリンクルーティング制限及び前記所望のデータスループット特性に基づいて前記データを送信するための集合フローのセットを決定するステップを備え、該所望のデータスループット特性が各宛先ノードへの所望の入来トラフィックフローであり、
前記送信するステップが該集合フローのセットに従って該データを送信するものである、方法。
【請求項８】
請求項１の方法であって、さらに、
割当て送信電力のセットに基づいて前記複数の無線リンクの各々にリンク容量を割り当てるステップを備え、該送信電力が前記少なくとも１つの所望のスループット特性に基づいて割り当てられるものであり、
前記決定するステップが、割り当てられた該リンク容量に基づいて該少なくとも１つのリンクルーティング特性を決定するものである、方法。
【請求項９】
請求項１の方法において、前記決定するステップがさらに、
各宛先ノードに対応付けられた合計レートメトリックに基づいて前記データを送信するための集合フローのセットを決定するステップを備え、該合計レートメトリックが、対応付けられた該宛先ノードへの合計トラフィックフローを示すものであり、
前記送信するステップが、該集合フローのセットに従って該データを送信するものである、方法。
【請求項１０】
請求項１の方法であって、さらに、
前記所望のデータスループット特性を達成するために、決定された前記少なくとも１つのリンクルーティング特性に対応するリンクスケジュールのセットを選択するステップ、
選択された該リンクスケジュール及び少なくとも１つのリンクルーティング制限に基づいて前記送信されるデータをルーティングするためのルーティング経路を特定するステップ
を備え、前記送信するステップが、決定された該ルーティング経路を介して前記複数のノード間でデータを送信するものである、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
実施例は通信システムに関し、例えば、マルチホップ無線通信システムにおいてリソースを共同して割り当てる方法に関する。
【背景技術】
【０００２】
直交周波数分割多重アクセス（ＯＦＤＭＡ）は、電気電子学会（ＩＥＥＥ）８０２．１６ｅ標準（ＷｉＭＡＸとしても知られる）、現在第３世代パートナーシッププロジェクト（３ＧＰＰ）で標準化されているユニバーサル移動体通信システムロングタームエボリューション（ＵＭＴＳ−ＬＴＥ）、及び現在第３世代パートナーシップ２（３ＧＰＰ２）で標準化されている高速パケットデータ改正Ｃに従って動作するシステムを含む多くの無線通信システムのための複数アクセス技術として適用されてきた。
【０００３】
従来のＯＦＤＭＡシステムでは、利用可能な帯域幅が複数のサブキャリア周波数（一般に、帯域、トーン又はサブキャリアといわれ、ここではこのように言い換え可能に使用される）に分割され、時間がシンボルにセグメント化される。周波数帯域上で隣接又は分散される１以上のサブキャリアはサブチャネルにグループ化される。さらに、１以上のシンボルはタイムスロットにグループ化され、タイムスロットはフレームにグループ化される。通常は、基地局は、基地局と加入者局の間、基地局と中継局の間、又は基地局と基地局の間の全てのシングルホップ通信リンクに対してリソース単位を時間及び周波数にわたって割り当てる責任を担っている。シングルホップとは、通信を補助する中間ノードがない２つのネットワークノード間の直接通信リンクを意味し、マルチホップとは、送信されるデータが中間ノードを介してルーティングされる２つのネットワークノード間の通信を意味する。このようなリンクは単方向又は双方向的な性質となる。より高いシステムスループットを達成するために、リソースは、時間、周波数及び／又は空間にわたって変化するチャネル品質情報に基づいて割り当てられる。より良いチャネル品質は通常より高いスループットをもたらす。
【０００４】
従来の無線通信ネットワークでは、基地局はリソースをローカル的に割り当てる。即ち、例えば、基地局はその基地局で発信又は終端するリンクのためだけにリソースを割り当てる。リソース割当て決定はこれらのローカルリンクについてのチャネル品質情報に基づく。さらに、電力、トーン割当て、スケジューリング及びルーティングに及ぶリソース決定は複雑さを減らすために従来的には独立して実行される（例えば、レイヤー化する）。しかし、そのようにすることはシステム性能を大幅に低下させてしまう。
【発明の概要】
【課題を解決するための手段】
【０００５】
実施例はマルチキャリア、マルチホップネットワークにおける全てのリンクのトーン／サブチャネル、電力、スケジューリング及び／又はルーティングを共同して決定して送信元ノードと宛先ノードの間の所望のスループットの課題を達成するための方法を提供する。実施例は、メッシュネットワーク内の複数のノード各々の間の各リンクに適用される電力制限、スケジューリング制限及びフロー制限のようなリンクルーティング制限の下で、各宛先ルータで受信されるスループットを向上又は最適化する。
【０００６】
少なくとも１つの実施例は無線ネットワークにおける複数のノード間のデータを送信するための方法を提供する。複数のノードは複数の無線リンクを介して相互接続されている。この方法において、複数のノードの少なくとも２つの間でデータを送信するための少なくとも１つのリンクルーティング特性は、複数のノードから選択された送信元／宛先ペア及び複数のノードに対応付けられた１セットのリンクルーティング制限についての少なくとも１つの所望データスループットに基づいて決定される。データは少なくとも１つのリンクルーティング特性に従って複数のノード間で伝送される。
【０００７】
少なくとも幾つかの実施例によると、複数のノードに対応付けられたリンクルーティング制限のセットは少なくとも１つのデータスループット特性に基づいて確立される。少なくとも１つのリンクルーティング特性は複数の無線リンクに割り当てられた多数のトーン、トーンの各々に対応付けられる送信電力、各送信元／宛先ペアに対するルーティング経路及び各ルーティング経路を介して送信される送信元／宛先トラフィック量の少なくとも１つを含むことができる。
【０００８】
少なくとも幾つかの実施例によると、複数の無線リンクの各々に対する複数のトーンの少なくとも１つは少なくとも１つのデータスループット特性に基づいて特定される。少なくとも１つのトーンは、複数の無線リンクに対応付けられた信号対干渉＋ノイズ比に基づいて複数の無線リンクの各々に割り当てられる。送信電力は、少なくとも１つのデータスループット特性及び複数のノードの各々に対応付けられた電力制限に基づいて割当てトーンの各々に割り当てられる。リンクルーティング制限のセットはルーティングの制限、メディアアクセスの制限及び物理層の制限の少なくとも１つを含む。
【０００９】
少なくとも幾つかの実施例によると、特定された少なくとも１つのリンクルーティング特性に対応するリンクスケジュールのセットが、所望のデータスループット特性を達成するように選択される。データは選択されたリンクスケジュールに基づいて送信される。所望のデータスループット特性は複数のノードの各々における総トラフィックフローであればよい。送信データをルーティングするためのルーティング経路は、選択されたリンクスケジュール及び少なくとも１つのリンクルーティング制限に基づいて決定される。少なくとも１つのリンクルーティング制限は、複数のノードにおける１つのノードが複数の無線リンクの１つにおいて複数のトーンの１つで送信するための時間長を示すノード毎平均合計電力制限であればよい。
【００１０】
少なくとも幾つかの実施例によると、データを送信するための集合フローのセットが少なくとも１つのリンクルーティング制限及び所望のデータスループット特性に基づいて決定される。所望のデータスループット特性は各宛先ノードへの所望の入来トラフィックフローであればよい。データは集合フローのセットに従って送信される。集合フローのセットは、複数のノードにおける各送信元ノードで生成されるトラフィックが複数のノードにおける各宛先ノードに配信される総スループット以上となるように、決定される。
【００１１】
少なくとも幾つかの実施例によると、リンク容量は割当て送信電力のセットに基づいて複数の無線リンクの各々に割り当てられる。送信電力は少なくとも１つの所望のスループット特性に基づいて割り当てられる。少なくとも１つのリンクルーティング特性は割当てリンク容量に基づいて決定される。
【００１２】
少なくとも幾つかの実施例によると、データを送信するための集合フローのセットは各宛先ノードに対応付けられた合計レートメトリックに基づいて決定される。合計レートメトリックは対応付けられた宛先ノードへの合計トラフィックフローを表す。データは集合フローのセットに従って送信される。
【００１３】
本発明はここに与えられる詳細な説明及び添付図面からより完全に理解され、図面では同様の要素は同様の参照符号で表され、これらは例示のためだけに与えられたものであって本発明を限定するものではない。
【図面の簡単な説明】
【００１４】
【図１】図１は実施例が実装されるネットワークアーキテクチャ例を示す。
【図２】図２は図１に示すネットワークアーキテクチャ例に対応するグラフに向けられる。
【図３】図３は実施例による方法を示すフローチャートである。
【図４】図４は実施例が実装されるサンプルネットワークトポロジを示す。
【図５】図５は実施例が実装される他のネットワーク例を示す。
【図６】図６は実行可能なリンクスケジュールが選択される集合フロー例を示す。
【図７】図７は実施例による実行可能モード選択スケジュールを示す。
【図８】図８は実施例による他の実行可能モード選択スケジュールを示す。
【図９】図９は図５に示す宛先へのルーティング経路例を示す。
【図１０】図１０は他の実施例による方法を示すフローチャートである。
【図１１】図１１は他の実施例による具体例を示すフローチャートである。
【図１２】図１２は他の実施例による方法を示すフローチャートである。
【図１３】図１３は他の実施例による方法を示すフローチャートである。
【発明を実施するための形態】
【００１５】
実施例の原理は８０２.１６ｅ、８０２.１６ｍ、ＷｉＭａｘ、及びＥＶ−ＤＯ改正Ｃのような第４世代（４Ｇ）無線通信システムに基づく無線通信システムに特に適しており、その例の文脈で説明されるが、これらの実施例は例示に過ぎず、どのようにも限定されない。実施例は他の無線ネットワークにも適用可能である。このように、他の無線通信システムへの応用のための種々の変形例が当業者には明らかであり、ここでの教示によって熟慮される。
【００１６】
以下で使用される用語「ゲートウェイアクセスポイント」とは、他のネットワークノードにマルチキャリア又は直交周波数分割マルチアクセス（ＯＦＤＭＡ）ベースの無線リンクを介して相互接続され、「高い帯域幅」の有線又はバックホールネットワークに接続されたネットワークノードを意味する。ゲートウェイアクセスポイントは、ゲートウェイ、ゲートウェイ機能を有する基地局又は送信元ノードと同義とみなされ、そのように称されることもある。
【００１７】
以下で使用される用語「メッシュルータ」とは、マルチキャリア又は直交周波数分割マルチアクセス（ＯＦＤＭＡ）ベースの無線リンクを用いて相互接続され、トラフィックルーティング機能を有するネットワークノードを意味する。メッシュルータは、アクセスポイント又はシンクノードと同義とみなされ、そのように称されることもある。
【００１８】
実施例によると、ゲートウェイアクセスポイントはトラフィックソース（ダウンリンク）として機能し、メッシュルータはゲートウェイアクセスポイントから、例えば、マルチホップルーティングを介して、例えば、他のメッシュルータ等の中間ノードを介してトラフィックを受信する。
【００１９】
ここで使用される用語「移動体端末」は移動局、移動体、移動体ユーザ、ユーザ機器（ＵＥ）、加入者、ユーザ、リモート局、アクセス端末、受信機、メッシュクライアント等と同義とみなされ、そのように称されることもあり、無線通信ネットワークにおける無線リソースのリモートユーザを記述することもある。
【００２０】
ここに記載されるように、ネットワーク要素又はノードはゲートウェイアクセスポイント、メッシュルータ及び移動体端末のいずれか又は全てを意味し、用語「基地局ルータ」はゲートウェイアクセスポイント及びメッシュルータの１以上を意味する。幾つかの実施例では、ゲートウェイアクセスポイント及びメッシュルータは固定又は静止基地局に位置する。
【００２１】
この説明の目的のために、用語「ネットワーク」は１以上の基地局ルータ及び移動体端末を意味する。即ち、例えば、ここで説明される「ネットワーク」は単一の基地局ルータ及び移動体端末、何百もの基地局ルータ及び移動体端末、何千もの基地局ルータ及び移動体端末等を意味するものとする。
【００２２】
概略として、実施例はマルチキャリア、マルチホップ無線通信システムにおいてリソースを共同して割り当てる方法に向けられる。実施例は、電力制御、周波数選択可能ＯＦＤＭＡスケジューリング及びマルチホップルーティングを共同して決定することができる上述の無線メッシュのためのクロスレイヤ最適化フレームワークを提供して所定のレート最大化の課題を達成する。
【００２３】
少なくとも幾つかの実施例による方法は中央リソース割当て装置といわれる装置によって実行される。中央リソース割当て装置は基地局、メッシュルータ、ゲートウェイアクセスポイントと機能的に共存していてもよいし、又は複数の基地局、メッシュルータ及び／又はゲートウェイアクセスポイントへのシグナリング情報を通信するネットワーク内の個別のエンティティであってもよい。ここに記載されるように、クロスレイヤ最適化が実行されるリンクは、ゲートウェイアクセスポイントリンクへのゲートウェイアクセスポイント、メッシュルータリンクへのゲートウェイアクセスポイント、移動体端末リンクへのゲートウェイアクセスポイント、メッシュルータリンクへのメッシュルータ、移動体端末リンクへのメッシュルータ等のうちの１以上を含む。
【００２４】
図１は有線ネットワークに接続されたゲートウェイアクセスポイントのセットを含む無線メッシュネットワークを示す。図１について、メッシュネットワークはインターネット１００への有線接続（実線で示す）を有するゲートウェイアクセスポイント１０２及び１０４、並びにゲートウェイアクセスポイント１０２及び１０４、移動体端末１１８−１２４及び他のメッシュルータへの無線リンク（破線で示す）を有するメッシュルータ１０６、１０８、１１０、１１４及び１１６を含む。
【００２５】
図１に示すメッシュネットワークは図２に示す方向付けグラフＧ＝（Ｍ，Ａ）上にマッピングされ、ノードＭのセット並びにリンク及び／又は送信元／宛先ペアＡのセットを含む。ノードＭのセットは、Ｍ＝｛１，２，３，４，５，６，７｝で与えられ、リンクのセットはＡ＝｛（１，２），（１，４），（１，５），（２，５），（２，６），（３，２），（３，５），（３，６），（３，７），（４，５），（５，２），（５，４），（５，６），（６，２），（６，５），（６，７），（７，６）｝で与えられる。ノードＭのセット及び／又はリンクＡのセットは入来データの宛先、入来トラフィックの量等のようなトラフィック特性に基づいてネットワーク内の複数のノードから選択される。図１及び２について、図１のメッシュルータ１０６、１０８、１１０、１１４及び１１６はノード４、２、５、６及び７にそれぞれ対応し、ゲートウェイアクセスポイント１０２及び１０４はノード１及び３にそれぞれ対応する。
【００２６】
図２について、Ｃij（例えば、Ｃ54及びＣ45）はネットワーク内のｉ番目及びｊ番目のノード間のリンク（ｉ，ｊ）で達成可能なレートを表し、ｘijはｉ番目及びｊ番目のノード間のリンク（ｉ，ｊ）のフローの量、即ち、例えば、ｉ番目及びｊ番目のノード間のリンクで所与の時間に搬送されるデータトラフィックの量を表す。少なくとも幾つかの実施例によると、ｘijf＝ａijfであり、ここでａijfは複数の宛先ノード（例えば、メッシュルータ、移動体端末等）についてのトラフィックを含み、ａijfの少なくとも一部分は宛先ノードｄに属する。リンク上で達成可能なレートは「リンク容量」ともいわれる。
【００２７】
ゲートウェイアクセスポイントはトラフィックソースとみなされるため、図２におけるノード１及び３の各々はＴiビット／秒の供給を有する送信元ノードといわれ、ここでＴiは、メッシルータ（又はシンクノード）のサービスエリアに位置するメッシュクライアント（例えば、図２には不図示の移動体端末）に分散される送信元ノードｉ（なお、図２においてｉ＝１及び３である）を介してネットワークに入来するトラフィックの合計量を表す。上述のように、シンクノードは他のノードへ宛てられたトラフィックをルーティングすることができる。各シンクノードについて、総入来フローをＴビット／秒とする。より概略的には、ｊ番目のシンクノードに宛てられた総入来フローはＴｊによって表される。各ノードｊについてＴｊ＝Ｔとなる特別の場合は共通レート解に対応し、達成可能レートは最悪の「ボトルネック」ノードによって制限される。
【００２８】
Ｎ個のノードを有するネットワークについて、方向付けグラフ表示におけるリンクの最大数は|Ｄ|＝Ｎ＊(Ｎ−１)−Ｎs＊(Ｎ−１)＝(Ｎ−Ｎs)＊(Ｎ−１)であり、ここでＮｓは送信元ノード数を示し、Ｎ＊(Ｎ−１)はノードペア間の可能な２方向リンク数であり、Ｎｓ＊(Ｎ−１)の項は送信元への入来リンクを削除する（例えば、後方トラフィックなし）。図２において、方向付けグラフ表示におけるリンクの最大数は|Ｄ|＝７＊(６)−２＊(６)＝(５)＊(６)＝３０である。
【００２９】
説明の目的のため、セットＭは２つのサブセットＭ＝Ｍｓｏ∪Ｍｓｉに分割されるものとし、ここで、Ｍｓｏは送信元ノードのセットであり、Ｍｓｉはシンクノードのセットである。上記のように、図２において、Ｍｓｏ＝｛１，３｝及びＭｓｉ＝｛２，４，５，６，７｝である。
【００３０】
セットＭｓｉにおける各シンクノードは帯域幅各ＷＨｚのＬ個のチャネルにアクセスできる。複数の直交チャネルの存在は、ノードペア間にＬ個の個別のリンクがあるものとして考慮される。言い換えると、１番目、２番目、Ｌ番目のチャネルの各々がＷ１、Ｗ２・・・ＷＬＨｚの帯域幅をそれぞれ有し、単一のリンクを構成するものとする。説明の目的のため、上付き文字ｆはそれらのチャネルの各々を示す。即ち、例えば、ｘijfはノードｉとノードｊの間のｆ番目のチャネル上のフローを示す。
【００３１】
ｆ番目チャネル上の達成可能なレート即ちリンク容量Ｃijfは、例えば、チャネル帯域幅、ｆ番目のチャネルについての送信電力、及びｆ番目のチャネルについてのチャネル条件等のｆ番目のチャネルについてのチャネル特性に基づいて決定される。即ち、例えば、ｆ番目のチャネル上の達成可能レートＣijfは、以下の式（１）を用いて計算できる。
【数１】
2010530177.tif 000003
【００３２】
式（１）において、ｆ番目のチャネル上のρijfは受信信号対干渉プラスノイズ比（ＳＩＮＲ）を表し、ρijf＝ｐijf＊ｈijfに等しくなる。この例では、ｐijfはｆ番目のチャネルで送信される電力を表し、ｈijfはチャネル条件（例えば、経路損失、フェーディングによるチャネル減衰、干渉、温度ノイズ等）を表す。説明の簡明化のためにここでは述べないが、ｆ番目のチャネルでの達成可能レートＣijfはｐijf及びｈijfに基づいて（変調及びコード化スキーム・ルックアップテーブルのような）他の方法に従って決定されてもよく、ｈijfは基地局によって推定され、及び／又は移動体端末によって計算されて任意の周知の態様で基地局にシグナリングされる。
【００３３】
図３は実施例による方法を示すフローチャートである。説明の明瞭化のため、図３に示す方法のステップＳ１０１及びＳ１０２は図２に示す方向付けグラフに関して記載される。しかし、図３の方法は他のあらゆるネットワークに適用可能である。
【００３４】
図３の方法は、複数のノードから選択された各送信元−宛先ペアについての少なくとも１つの所望のデータスループット特性及び複数のノードに対応付けられたリンクルーティング制限（例えば、以下に示す式（２）−（７））のセットに基づいて複数のノードのうちの少なくとも２つの間でデータを送信するために、少なくとも１つのリンクルーティング特性（例えば、リンク容量、集合フロー、リンクスケジュール及び／又はルーティング経路）を決定するのに使用される。
【００３５】
図３を参照すると、ステップＳ１０１において、送信電力ｐijfはｆ個のチャネルの各々及びセットＡ内の全てのリンクに割り当てられる（例えば、これはリンク容量割当てステップといわれる）。即ち、例えば、ステップＳ１０１において、セットＡ＝｛（１，２），（１，４），（１，５），（２，５），（２，６），（３，２），（３，５），（３，６），（３，７），（４，５），（５，２），（５，４），（５，６），（６，２），（６，５），（６，７），（７，６）｝内のリンクのｆ個のチャネルの各々について送信電力ｐijfが決定される。ｆ個のチャネルの各々についての送信電力ｐijfはセットＡ内のリンク上で決定され、達成可能レートＣijfはネットワークにおける複数のノード各々間のリンクにおけるｆ個のチャネルの各々について決定される。これはまとめて割当てリンク容量ともいわれる。
【００３６】
一例では、リンク容量は均等な電力割当てを用いて割り当てられる。即ち、例えば、送信電力は均等な電力割当てを用いて割り当てられる。当技術では周知のように、この例ではｐijfは、所与のネットワークパラメータである最大電力制限Ｐに従って均等に設定される。均等電力割り当ては当分野では周知なので、詳細な説明は説明の簡明化のために省略する。
【００３７】
他の例では、リンク容量は空間的な注水（water-filling）を用いて割り当てられる。この例は図４に示す例示のネットワークトポロジに関してより詳細に記載される。
【００３８】
図４を参照すると、ノードｉからの送出リンクのセットをＡｏｕｔ(ｉ)とする。図４を参照すると、Ａｏｕｔ(１０)＝｛（１０；２０）；（１０；３０）；（１０；４０）；（１０；５０）｝である。セットＡｏｕｔ(ｉ)におけるノードペアの各々について、Ｌ個の利用可能チャネル（サブキャリア又はトーンともいわれる）がある。この実施例では、空間注水は全Ｌ個のトーンに対するＡｏｕｔ(ｉ)におけるペアにわたってｉ番目のノードについて利用可能送信電力を分散する。少なくとも下記の（例えば、適用可能な）スケジューリング制限に従って、各トーンは同時に単一のリンク上でアクティブとなるだけであり、従って、各トーンについて単一のリンクが選択される。特定ノードの合計レートを向上又は最大化するために、各トーンは、そのトーンについて最も高い信号対干渉プラスノイズ比（ＳＩＮＲ）を有する対応リンクに割り当てられる。
【００３９】
さらに他の例では、リンク容量は注水によるランダムリンク割当てを用いて割り当てられる。ｉ番目のノードから送出するリンクのセットがＡｏｕｔ(ｉ)であるとすると、セットＡｏｕｔ(ｉ)からランダムに選択されるリンクに各トーンが割り当てられ、これらのランダムに選択されたリンク／トーンペアにわたって合計ノード送信電力が注水によって割り当てられる。ランダムリンク割当ては空間注水と比べてネットワーク接続性を改善することができるが、スペクトル効率を向上及び／又は最大化することはできない。
【００４０】
リンク容量はまた、リンクベースの注水を用いて割り当てることもできる。この例では、リンクベースの注水は２つの上述の注水アプローチ間の妥協点を与える。リンクベースの注水では、各送信元／宛先ペアは個別に検討され、各ペアは非ゼロの容量を有して空間注水と比べてより良いネットワーク接続性を保障することを助ける。さらに、注水に基づく電力割当てはトーンについて十分な又は良いチャネル条件でより高いレートをもたらすことができ、結果として最適化によって生成されたレートを向上することができる。注水が各ペアで実行されるとき、電力レベルがノード送信電力制限Ｐであるとする。Ｎ個の隣接のものへの全ての送出リンク／トーンが同時にアクティブである場合、これは合計ノード送信電力ＮＰに帰着することになる。各トーンはＮ個のリンクのうちの１つのみでアクティブとなるようにスケジュールされるため、ＮＰのおよそ１／Ｎが実際に使用され、平均ノード送信電力は約Ｐとなる。さらに、これらはリンク容量を生成するための予備的発見的な電力割当てに過ぎず、後の最適化のステップで使用される平均ノード電力の制限によって、平均電力の制限が満足されることを保障することができる。
【００４１】
ステップＳ１０１でリンク容量が割り当てられた後に、ステップＳ１０２において、線形プログラムが使用されて、下記の式（２）−（７）に示すリンクルーティング制限の少なくとも１つを用いてネットワーク内のリンクのｆ個のチャネルについて集合フローｘijfを決定する。
【数２】
2010530177.tif 000004
【００４２】
式（２）では、Ａout(i)及びＡin(i)はｉ番目のノードについてのそれぞれ送出及び入来リンクのセットであり、Ｃijfはｉ番目とｊ番目のノード間のリンクのｆ番目のチャネル上の達成可能レートである。式（２）で与えられるリンクルーティング制限はメディアアクセス（例えば、ＭＡＣ）制限の例である。式（２）における制限が満足される場合、ネットワーク内のノードが半二重で動作し（例えば、同じチャネルｆで同時に受信及び送信できない）、複数のノードが同じノードに同じチャネルｆで同時に送信していないときに、ｘijfの総フローをサポートする実行可能リンクスケジューリングポリシーが存在する。定数β＝２／３及びβ＝１は、実行可能リンクスケジューリングポリシーを達成するための十分条件及び必要条件をそれぞれ表す。
【００４３】
他のリンクルーティング制限は下記の式（３）によって与えられる。式（３）に示す制限はノード毎の平均合計電力制限を施行する。ここで、ｘijf／Ｃijfはｉ番目のノードがチャネルｆで送信する時間部分を示し、残りの項はレートＣijfを達成するのに必要な電力を表す。
【数３】
2010530177.tif 000005
【００４４】
式（３）の第２項は上記式（１）で与えられたｐijfと等価である。ｐijfの関数としてＣijfの異なる偏差が採用される場合、積の第２項はそれに従って修正される。式（３）によって与えられるリンクルーティング制限は物理層制限の一例である。
【００４５】
式（４）−（７）で下記に示すリンクルーティング制限は、送信元ノードによるトラフィック分散量を決定し（式（４））、送信元ノードへの後方トラフィックを抑制及び／又は防止し（式（５））、シンクノードで受信されるトラフィック量を決定し（式（６））、並びに送信元ノードからの合計トラフィックが宛先シンクノードによって受信されるトラフィックの合計に一致することを保障する（式（７））ためのトラフィックフロー制限である。
【数４】
2010530177.tif 000006
【数５】
2010530177.tif 000007
【数６】
2010530177.tif 000008
【数７】
2010530177.tif 000009
【００４６】
式（４）−（７）によって与えられるリンクルーティング制限は総フロールーティング又はルーティングの制限の例である。
【００４７】
実施例によると、式（２）−（７）のリンクルーティング制限に支配されるＴを最大化する集合フローｘijfのセットによって、各宛先シンクノードへの入来トラフィックＴを改善、向上及び／又は最大化することができる。ステップＳ１０１で決定される各Ｃijfによって、式（２）−（７）はｘijfに関して線形となり、集合フローｘijfのセットは線形プログラムを用いて決定できる。
【００４８】
図３に戻ると、ステップＳ１０２で集合フローｘijfを決定した後に、ステップＳ１０３において、集合フローｘijfに対応するとともに少なくとも１つの所望データスループット特性（例えば、各シンクノードへの所望トラフィックフロー）を達成するリンクスケジュールのセットが複数の候補リンクスケジュールから選択される。上述したように、式（２）はスケジューリングの実行可能性を保障する。
【００４９】
少なくとも幾つかの実施例によると、リンクスケジュールのセットは割当てリンク容量及び集合フローに基づいて選択される。図３のステップＳ１０３を、例示として図５及び６に示すネットワーク例に関して説明する。図５及び６では、ノード５１は送信元ノードであり、ノード５２−５４はシンクノードである。
【００５０】
上述したように、Ｎ個のノードのネットワークについて、方向付けグラフ表示において可能な最大リンク数は|Ｄ|＝Ｎ＊(Ｎ−１)−Ｎs＊(Ｎ−１)＝(Ｎ−Ｎs)＊(Ｎ−１)であり、ここでＮsは送信元ノード数を示し、Ｎ＊(Ｎ−１)はノードペア間の可能な２方向リンク数であり、Ｎs＊(Ｎ−１)の項は送信元への入来リンクを削除する（例えば、後方トラフィックなし）。図５及び６に示すサンプルネットワークについて、リンク数は、|Ｄ|＝４＊(４−１)−１＊(４−１)＝９である。
【００５１】
これらの|Ｄ|個のリンクの中で、式（２）で与えられるリンクルーティング制限に抵触しないリンクのみが選択される（例えば、各ノードが１つの送出又は入来リンクに接続される）。同時にアクティブとなることが許されるリンクのセットは「モード」といわれる。リンクスケジュールのセットは１以上のモードを含むことができる。
【００５２】
実施例によると、アクティブなモード及び各モードがアクティブである継続時間が用いられて所望のデータスループット特性又は所望のフロー要件を達成する。ネットワーク内の|Ｄ|個のリンクでは、２|Ｄ|個のサブセットのリンクが可能であるが、式（２）によって与えられるリンクルーティング制限を満足するもののみが候補モードとみなされる。無線バックホールアプリケーションについて、ネットワークトポロジは比較的固定的であるので、利用可能なモードは、例えば、合理的なネットワークサイズについての網羅的検索法によってオフラインで決定できる。代替的に、多項式時間における実行可能なモードを生成する発見的なグラフ・カラーリング・アルゴリズムが任意のネットワークサイズに対して使用できる。渇望的なグラフ・カラーリング・アルゴリズムのようなこれらの幾つかのアルゴリズムは当技術で周知であるので、説明の簡明化のために詳細な説明を省略した。本説明の目的のために、実行可能なモードは網羅的検索によって或いは任意の周知の発見的アルゴリズムを用いることによって生成されるものとする。
【００５３】
図５及び６におけるサンプルネットワークについて、チャネル１及び２（それぞれ図７及び８に示す）の各々についての候補モードは網羅的検索によって決定される。この例では、チャネル１及びチャネル２の各々について１５個の候補モードがある。各モードがアクティブとなるべき時間の割合は以下のように計算される。
【００５４】
αｋはモードｋがアクティブである時間の割合を示し、
【数８】
2010530177.tif 000010
がモードｋについての容量ベクトルを示し、ここで、ノードｉとノードｊの間のリンクがモードｋに含まれるときはｃijk＝ｃijであり、そうでないときはｃijk＝０である。フロー要件を満足するために、
【数９】
2010530177.tif 000011
が満たされなければならない。この例では、各モードがアクティブな必要時間部分について以降の線形プログラム（ＬＰ−１）を解く。
【数１０】
2010530177.tif 000012
【００５５】
図６におけるノード間の所望データスループット特性を提供する（例えば、レート要件を満足する）ために、モードのセットがチャネル１及び２の各々に対して選択される。表１及び２に、チャネル１及び２の各々について問題となる（ＬＰ−１）を解く時間部分の例を示す。この例では、図６に示すレート要件例をサポートするために、例えば、モード(MODE)１、モード２、モード４及びモード１０が図７に示すチャネル１に対する候補モードから選択され、モード１２が図８に示すチャネル２に対する候補モードから選択される。各リンクの集合フローは図６に示す要求レートを達成し、モード選択は式（２）で与えられるリンクルーティング制限（例えば、ノード内外のチャネルの合計利用率は２／３になるべき等）を満足し、平均ノード電力制限は結果として得られるフローによって満足される。
【表１】
2010530177.tif 000013
【表２】
2010530177.tif 000014
【００５６】
ステップＳ１０３でリンクスケジュールを決定した後、各宛先ノードについてのルーティング経路がステップＳ１０４で決定される。上述のように、リンク（ｉ，ｊ）におけるｆ番目チャネルについてのフロー割当てはｘijf＝ａijfで与えられる。少なくとも幾つかの実施例によると、ａijfは複数の宛先ノードについてのトラフィックを含み、ａijfの少なくとも一部は宛先ｄに属する。この部分はａijf(ｄ)で示されるので、ａijfは下記の式（Ｃ１）で与えられる。
【数１１】
2010530177.tif 000015
【００５７】
さらに上述したように、各宛先ノードに配信される総スループットはＴbpsによって示され、各送信元ノードはＴibpsを注入し、送信元及びシンクノードインデックスのセットはそれぞれＭso及びＭsiで示され、ノードｉに対応付けられる送出及び入来リンクのセットはそれぞれＡout(ｉ)及びＡin(ｉ)で示される。この例では、式（Ｃ２）に示す等式が送信元トラフィックに当てはまる。
【数１２】
2010530177.tif 000016
【００５８】
シンクノードについて、下記の式（Ｃ３）に示すルーティング経路制限はシンクノードがそれら自身のトラフィックをルーティングしないことを意味している。
【数１３】
2010530177.tif 000017
【００５９】
シンクノードが他の各トラフィックをルーティングし得るということが、下記の式（Ｃ４）に示すルーティング経路制限で表現される。
【００６０】
【数１４】
2010530177.tif 000018
【００６１】
式（Ｃ４）において、左辺は宛先ｄに属するノードｉによってルーティングされるトラフィックを示す。右辺はルーティングされたトラフィックを示す。個々のルーティング経路は式（Ｃ１）−（Ｃ４）で与えられるルーティング経路制限に支配される線形実行可能問題を解くことによって特定される。即ち、例えば、個々のルーティング経路を特定するために、以下の線形プログラムが解かれる。
【数１５】
2010530177.tif 000019
【００６２】
図５を再度参照すると、このサンプルネットワークについて、図９に示す３個の宛先の各々に対するルーティング経路は制限（Ｃ１）−（Ｃ４）を満足するので、上記の線形プログラムを解決する。図９に示す例では、Ｔi＝９９６６ｋbpsであり、Ｔ＝３３２２ｋbpsである。
【００６３】
図１０は他の実施例による方法を示すフローチャートである。図３に関する場合でそうであったように、図１０に示す方法は図１及び２に記載するネットワークに適用可能である。
【００６４】
図１０を参照すると、ステップＳ２０１において、集合フローは、式（３）の代わりに式（８）が使用されることを除いて、図３に関して上述した態様と同様の態様で決定される。即ち、例えば、線形プログラムが使用されて、上記式（４）−（７）及び下記式（８）によって表されるリンクルーティング制限に支配されるＴを最大化する集合フローを決定する。この実施例では、式（８）はｌｏｇ(１＋ｘ)〜ｘを用いて式（３）を近似する。
【数１６】
2010530177.tif 000020
【００６５】
ステップＳ２０２において、リンク容量が各リンクに割り当てられる。例えば、実行可能リンクスケジュールを達成するのに十分な最小リンク電力が式（９）を用いて決定される。
【数１７】
2010530177.tif 000021
【００６６】
式（９）は、変数の対数化の後に単純な凸最適化問題に変換される幾何学的最適化問題である。
【００６７】
ステップＳ２０３及びＳ２０４において、スケジューリング及びルーティングが、それぞれステップＳ１０３及びＳ１０４に関して上述したのと同じ態様で決定される。
【００６８】
図１１は他の実施例による方法を示すフローチャートである。この実施例では、ステップＳ３０１及びＳ３０２は図５に関して上述したステップＳ２０１及びＳ２０２と同一又は実質的に同一である。
【００６９】
ステップＳ３０３において、ステップＳ３０２で決定された送信電力ｐijfのセットが使用されて達成可能レートＣijfのセットを決定する。達成可能レートＣijfのセットは図３におけるステップＳ１０２に関して記載した線形プログラムを解くために使用される。即ち、例えば、これらの達成可能レートＣijfは、式（２）−（７）によって与えられるリンクルーティング制限に支配されるＴを最大化する線形プログラムを解くために使用される。ステップＳ３０４及びＳ３０５において、図３のステップＳ１０３及びＳ１０４に関して説明したのと同一又は実質的に同一の態様で決定される。
【００７０】
図１２は他の実施例による方法を示すフローチャートである。図１２を参照すると、ステップＳ４０１、Ｓ４０３及びＳ４０４はそれぞれステップＳ１０１、Ｓ１０３及びＳ１０４と同一又は実質的に同一である。一方、ステップＳ４０２では、線形プログラムは、式（２）、（３）、（４）及び（５）によって与えられるリンクルーティング制限並びに下記の式（１０）及び（１１）によって与えられるリンクルーティング制限についての合計レートメトリックΣＴｉを最大化する集合フローｘijfを決定するために使用され、ここで、Ｔｉは宛先ノードｉについてのトラフィックを表す。
【数１８】
2010530177.tif 000022
【数１９】
2010530177.tif 000023
【００７１】
図１３は他の実施例による方法を示すフローチャートである。図１３を参照すると、ステップＳ５０１において、集合フローｘijf及び共通達成レートＴは図３に関して上述したのと同じ態様で決定することができる。ステップＳ５０２において、線形プログラムが使用されて、合計レートメトリックΣＴｉのような課題の機能に従うが、式（２）、（３）、（４）、（５）、（１０）及び（１１）によって与えられる制限並びに下記の式（１２）によって与えられる制限に支配される集合フローｘijfを決定する。
【数２０】
2010530177.tif 000024
【００７２】
ステップＳ５０３及びＳ５０４はそれぞれステップＳ１０３及びＳ１０４と同一又は実質的に同一であればよい。
【００７３】
ここに記載した実施例によると、図３及び１０−１４に示す方法を用いて、複数のノードから選択された各送信元−宛先ペアについての少なくとも１つの所望のデータスループット特性及び複数のノードに対応付けられたリンクルーティング制限（例えば、式（２）−（７））のセットに基づいて複数のノードのうちの少なくとも２つの間でデータを送信するための少なくとも１つのリンクルーティング特性（例えば、リンク容量、集合フロー、リンクスケジュール及び／又はルーティング経路）を決定し、決定されたリンクルーティング特性の１以上を用いてデータが複数のノード間で送信される。データは、例えば、上述のＯＦＤＭＡリンクを介してデータを送信するための周知の方法を用いて送信される。
【００７４】
線形プログラムに関してここに記載したが、幾何学的プログラムも使用できる。さらに、線形及び幾何学的プログラム並びにそのようなプログラムを用いる式を解くための方法は、例えば、Stephen Boyd他による「Convex Optimization」、ケンブリッジ大学プレス、ニューヨーク、ＮＹ、２００４に記載されるように当技術では周知である。
【００７５】
以上のように発明が記載されたが、同じことが多数の態様で変形され得ることは自明である。そのような変形例は本発明から離れたものとしてみなされてはならず、全てのそのような修正例は本発明の範囲内に含まれることが意図されている。
【図１】
2010530177.tif 000025
【図２】
2010530177.tif 000026
【図３】
2010530177.tif 000027
【図４】
2010530177.tif 000028
【図５】
2010530177.tif 000029
【図６】
2010530177.tif 000030
【図７】
2010530177.tif 000031
【図８】
2010530177.tif 000032
【図９】
2010530177.tif 000033
【図１０】
2010530177.tif 000034
【図１１】
2010530177.tif 000035
【図１２】
2010530177.tif 000036
【図１３】
2010530177.tif 000037
【国際調査報告】
2010530177.tif 000038
2010530177.tif 000039
2010530177.tif 000040