JP2005518717A - レイヤ間を統合した衝突の無い経路ルーティング - Google Patents

Abstract

本発明は概して、ネットワーク内の幾つかのプロトコルレイヤの機能を真にレイヤ間で統合することによってマルチホップネットワークにおいてＱｏＳを提供する統一手法を実現する構成について記載する。本発明による統一手法では、接続は、ネットワーク内の少なくとも３つのプロトコルレイヤの接続パラメータに関する所定の目的関数を統合する形で最適化することにより決定することが好ましい。好適には、最適化はルーティング（経路選択）、チャネルアクセスだけでなく、物理リンクパラメータの適応も含む。物理接続パラメータに正しい構成の制約を取り込むことによって、干渉問題を細心の形で考慮に入れることができる。これは、新規の接続だけでなく、既存の接続に対して実質的に干渉の無い通信を保証する接続パラメータを求めることが可能になることを意味する。

Description

発明の属する技術分野
本発明は概して、無線マルチホップネットワークのような通信ネットワークにおけるサービスの質（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ：ＱｏＳ）のサポートに関し、特にそのようなネットワークにおける接続パラメータ、接続設定、及び接続認証制御に関する。

発明の背景
ルーティングが無線ネットワークに適用されると、そのようなネットワークは多くの場合マルチホップネットワークを意味する。マルチホップネットワークでは、互いの接続範囲の外に在るノードは、これらのノードの中間に位置するノードがそれらのノードのメッセージを接続元から接続先に転送することで通信できるという利点が得られる。従来、マルチホップネットワークは、ノードがほとんど自由に移動し、そして集中制御調整型のインフラストラクチャが存在しない所謂アドホックネットワークに接続されてきた。しかしながら、マルチホップネットワーキングの考えはノードが固定される場合にも適用することができる。そのような計画の一つは郊外エリアにおけるインターネットアクセスを目標とし、家屋の屋根、街灯などの頂部に取り付けられる固定ノードを使用する。

幾つかの研究が１９７０年代前半からマルチホップ分野で進行中であるが、これらの研究成果のうち比較的少数しかマルチホップネットワークにおけるＱｏＳ提供に向けられて来なかった。この理由は、マルチホップネットワークにおけるＱｏＳサポートが非常に複雑であると考えられたからである。予測不能な移動性、ランダムに変化するように見えるトラフィックパターン、信頼度の低い無線チャネル、計算の複雑さ、及びこれ以外にも存在する不利益要素が、このような見解の原因となっている。にもかかわらず、幾人かの研究者はマルチホップネットワークにおけるＱｏＳ課題に挑もうとしてきた。この技術分野の最も興味深く有望な研究は、ＭＡＣ（メディアアクセス制御：Ｍｅｄｉｕｍ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）構造のようなある種のスロット化ＴＤＭＡ（時分割多元接続：Ｔｉｍｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）を基盤として使用することに焦点を合わせてきた。

次に、衝突の無いチャネルを実現し、接続元ノードと接続先ノードとの間のＱｏＳルートの確立を可能にする最先端のマルチホップネットワークについて以下に記載する。このような種類のプロトコルはＱｏＳルーティングプロトコルと呼ばれることが多い。普通のルーティングプロトコルとは対照的に、ＱｏＳルーティングにおいては、接続元から接続先へのルートを見つけ出す必要があるだけでなく、このルートが、帯域及び／又は遅延という観点から設定されることの多いエンドツーエンドのＱｏＳ要求を満たして、例えばリアルタイムのマルチメディア通信をサポートする必要もある。最先端のＱｏＳルーティングプロトコルは２つの異なるグループに分割することができ、以後自律分散チャネルアクセス及びルーティング方法、及び集中制御チャネルアクセス及びルーティング方法と呼ぶ。前者のグループにおいては、ルーティング及びチャネル割当てタスクを２つの異なるアルゴリズムに分割する、すなわちまず、ルートを見つけ出し、その後チャネル割当てを行なうのに対して、第２グループはチャネル割当て及びルーティングに対して事実上集中制御的な手法を実行する。

先行技術におけるＱｏＳルーティング方法に対する理解を深めるために、ネットワーキングのＯＳＩ（Ｏｐｅｎ Ｓｙｓｔｅｍｓ Ｉｎｔｅｒｃｏｎｎｅｃｔ：開放型システム間相互接続）モデルの概要から始めることが有効であろう。ＯＳＩモデルは７つの異なるプロトコルレイヤ、すなわち物理レイヤ（１）、リンクレイヤ（２）、ネットワークレイヤ（３）、トランスポートレイヤ（４）、セッションレイヤ（５）、プレゼンテーションレイヤ（６）、及びアプリケーションレイヤ（７）を含む。伝送メディア、伝送装置及びデータ信号のようなネットワーキングの物理形態に関する物理レイヤはプロトコルレイヤと見なされない場合がある。しかしながら単純化のため、全てのレイヤをプロトコルレイヤと呼ぶ。とりわけ、リンクレイヤは通信装置間のリンクを確立し、維持し、そしてネットワーク媒体へのアクセスを制御する。ネットワークレイヤの主な役割は、交換サービス、ルーティングサービス及びゲートウェイサービスを含む。トランスポートレイヤは異なる装置におけるサービスの間でフレームを配信する役割を担う。セッションレイヤはダイアログ制御及びセッション管理を処理する。プレゼンテーションレイヤはデータ表示の役割を担い、そしてアプリケーションレイヤはネットワークを通してのサービスの提供に関わり、そしてネットワークにアクセスするアプリケーションのインターフェースを提供する。

自律分散チャネルアクセス及びルーティング方法
自律分散ＱｏＳルーティングプロトコルは共通のＱｏＳ指標を使用し、そして特定のＭＡＣレイヤ、すなわちレイヤ２に合うように調整されていない。ＱｏＳ要求を満たすことを保証することができるようにするために、これらのプロトコルをＭＡＣプロトコルで機能強化してチャネルへの衝突の無いアクセスを実現する必要がある。

インシグニア
ＩＮＳＩＧＮＩＡ［１］は、アドホックネットワークにおいてＱｏＳを提供するエンドツーエンドＩＰベースの帯域内信号方式フレームワークである。帯域内信号方式とは、全てのパケットが帯域予約を行なうために必要な全ての情報を搬送することである。ＱｏＳメカニズムは、使用するアドホックルーティングプロトコル（参考文献［２］または［３］を参照のこと）及びリンクレイヤ技術の両方に依存しないが、最終的に受信するＱｏＳはこれら両方に非常に大きく依存する。フレームワークの動作を以下に記載する。接続元から接続先へのルートはレイヤ３のアドホックルーティングプロトコルによって検出される。全てのパケットは必要な帯域を予約するための必要な情報を搬送するので、データパケットはルートが確立されると直ぐにルートを通過し始めて、高速に予約を行なう。接続元から接続先へのルートに在るノードが、容量を予約していないフローからパケットを受信すると（ヘッダの１ビットにより示される）、ノードは可能であれば必要な容量を予約する。

チケットベースのプロービング
ＩＮＳＩＧＮＩＡの場合がそうであったように、チケットベースのプロービング（Ｔｉｃｋｅｔ Ｂａｓｅｄ Ｐｒｏｂｉｎｇ：ＴＢＰ）［４］は純粋なレイヤ３プロトコルであり、全てのシグナリングがこのレイヤに対して行なわれ、そしてレイヤ２（ＭＡＣ）をサポートして予約を承認する、または拒否するかどうかを決定する必要があるという点で純粋なレイヤ３プロトコルである。しかしながら、ＴＢＰは真のアドホックルーティングプロトコルである。参考文献［４］の主たる目的は、アドホックルーティングプロトコルでは普通に見られるように、全ネットワークをフラッディングさせるのではなく、接続元と接続先との間の実現可能な経路を探索する操作がネットワークの一部で自律的に行なわれるようにすることにある。特に、労力を要し、コストの高くつく探索を行なうのではなく、接続元から接続先への少数の経路のみを探索することを望ましいと考える。この操作はチケットを発行することにより実現する。チケットは一つの経路の探索を承認する許諾であり、従って探索する経路の最大数はチケットの数で制限される。接続元から接続先に至る経路上の中間ノードがチケットを受け取ると、そのノードはどのノード（群）にチケットを転送すべきかを決定する必要がある。この操作を行なうために、ノードはステート情報を使用して少数のパケットを最良の経路に沿って案内する。距離ベクタープロトコルを使用してエンドツーエンド遅延、帯域幅及びコストからなるこのステート情報を収集する。

競合の無いスケジューリングアルゴリズム例
参考文献［６］では、Ｎｅｌｓｏｎ及びＫｌｅｉｎｒｏｃｋは、タイムスロット（ＴＳ）が空間的に再利用される空間多重方式併用型ＴＤＭＡ（Ｓｐａｔｉａｌ ＴＤＭＡ：ＳＴＤＭＡ）のコンセプトを導入した。この操作は、競合の無いスケジュールを実現することを目標とする他の全てのスケジューリングアルゴリズムの土台と考えることができる。この考え方は、複数組の非干渉（または非衝突）リンクを求めることにある。この考え方は固定ネットワークを仮定し、そしてこれらの複数組のリンクは、ネットワークが大きく変化する場合に再計算する必要がある。これらの複数組のリンクが選択されて、この考え方に従った場合にネットワークの各ノードが少なくとも１回の送信が行なえるようになるのが好ましい。次にＴＤＭＡフレームの各タイムスロットに、互いに干渉を起こすことなく送信を行なえる１組のリンク（送信セット）が割り当てられる。続いて、同じスケジュールがＳＴＤＭＡフレーム毎に繰り返される。

参考文献［８］及び［９］に記載された方法（複数の方法）は、ＳＴＤＭＡから生み出される直接の成果物として見なすことができる。ＳＴＤＭＡにおける前に記載した操作では、ネットワークグラフの接続性を利用して干渉が生じるかどうかを判定する。このような手法ではネットワークの全体としての干渉を把握できない。これとは異なり、参考文献［８］及び［９］の方法（複数の方法）では、ＳＴＤＭＡスケジュールの生成は各リンクのＳＩＲ値に基づく。

ＳＴＤＭＡ及びその成果物は、送信セットに関するオフラインの、または集中制御型の計算が可能なように非常に良く設計されている。アドホックネットワークでは、これは実用的な手法ではない。

分散型の、衝突の無い動作を保証し、Ｃｏｌｌｉｓｉｏｎ−Ｆｒｅｅ Ｔｏｐｏｌｏｇｙ−Ｄｅｐｅｎｄｅｎｔ Ｃｈａｎｎｅｌ Ａｃｃｅｓｓ Ｓｃｈｅｄｕｌｉｎｇ（衝突の無い、接続形態に依存したチャネルアクセススケジューリング）または省略してＣＴＭＡと呼ばれる特定レイヤ２構成が参考文献［７］に記載されている。

「集中制御」チャネルアクセス及びルーティング方法
「集中制御」ＱｏＳルーティングアルゴリズムはアドホックネットワークがグラフとしてモデル化することができ、そしてアルゴリズムの全てがオンデマンドプロトコルである、すなわちルート探索はルートが高層のプロトコルからリクエストされた後にのみ行なわれる、という仮定に基づく。また、従来の集中制御ＱｏＳルーティングアルゴリズムは通常、ＴＤＭＡ、固定送信電力及び無指向性アンテナを仮定している。グラフにおいては、２つのノードが互いに通信可能であり、そしてこの様子をこれらの２つのノードをグラフモデルの中で一のリンクで接続して表示する場合に、これらの２つのノードを隣接体と呼ぶ。２つのノードは、これらのノード間の距離が或る所定の値を超えない場合に接続することができる、すなわちパケットを、他のノードからの外部干渉が無い状態でエラーを生じることなく受信することができる。隣接体だけが互いに干渉するという状態を仮定することもできる。グラフでモデル化したマルチホップパケット無線ネットワークにおいては、伝送を２つの態様で干渉を起こすようにモデル化することができ、この干渉を以後、主干渉及び副干渉と呼ぶ。主干渉は、ノードが単一タイムスロットで２つ以上の事象、例えば同じタイムスロットで送信及び受信を行なうと考えられるときに生じる。副干渉は、特定の送信機Ｔの周波数に合うように調整した受信機Ｒが別の送信機の接続範囲内に位置するときに生じ、この場合、受信機Ｒ向けではない別の送信機からの送信が送信機Ｔからの送信に受信機Ｒで干渉する。グラフモデルを使用すると、このモデルは、受信機Ｒの全ての隣接体が送信機Ｔと同じタイムスロットで送信を行なわないようにして副干渉を回避するために十分機能する。以下に種々の集中制御ＱｏＳルーティングプロトコルを記載するに当たって、これらのプロトコルは、どのレベルの干渉−干渉の無いチャネル、主干渉のみ、主干渉及び副干渉の両方−を考慮に入れるかによって分類されている。何故なら、この分類の仕方がプロトコルを設計する方法に大きく影響するからである。

ほとんどの既存のアドホックルーティングプロトコルは、アドホックネットワークの２つのノード間の最短経路ルートの存在にのみ焦点を当てており、その品質を保証していない。前に記載したように、アドホックＱｏＳルーティングプロトコルの目標は、接続元ノードから接続先ノードに至る経路／チャネルを設定して、帯域及び／又は遅延に関する幾つかの要求を満たしてリアルタイムメディア通信をサポートする機能を実現することである。これを実行するために、従来の集中制御ＱｏＳルーティングプロトコルは通常、接続元から接続先に至るルートを探索するときにリンクの帯域を考慮に入れる。次に帯域要求は、経路のリンクのタイムスロットを予約することにより満たされる。本手法の主たる利点は、通常のアドホックルーティングプロトコルと比較して、ＱｏＳ要求が満たされることである。完全な自律分散ＱｏＳルーティングプロトコルに比べて、これはＱｏＳ提供がより良い形でのネットワーク利用により実現することができることを意味する。

この環境における利用可能な帯域を計算するために、有線ネットワークで行なわれるように、経路に沿ったリンクの最小帯域を単純に計算する、というのは間違いである。この理由は、利用可能な帯域は隣接ノード間で共有されるからである。この簡単な例を次に示すが、この例では主干渉のみを考慮に入れる。ノードＡがノードＣとノードＢを通して通信しようとすると仮定する。ＡがＢと通信するために利用可能な空きスロットを１，２，３及び４とし、そして同じ条件がＢからＣに至るリンクにも成立するとする。これが有線（または干渉の無いチャネル）ネットワークであるとすると、利用可能な容量は４スロットであり、これに対してこの場合では容量は２スロットである。この理由は、ＡからＢに至るリンク及びＢからＣに至るリンクを通過する共通空きスロットの共通部分は空のセットではなく、かつ一のノードが同じスロットでの送信及び受信の両方を行なえないからである。また、ＡからＢに及びＢからＣに向かう通信を行なうための利用可能な空きスロットをそれぞれ１，２，３，４及び３，４と仮定する。スロット１及び２が、ＡからＢに向かう通信を行なうために予約され、そしてスロット３及び４が、ＢからＣに向かう通信を行なうために予約されるとすると、ＡからＣに至る利用可能な帯域は２である。他方、スロット３及び４が、ＡからＢに向かう通信を行なうために予約されるとすると、ＢからＣに向かう通信は行なわれず、ＡからＣに至る利用可能な帯域はこの場合には０となってしまうことを意味する。この問題を特定してそれを解決することのできるプロトコルは、これから示す最適スケジューリングを実行することができると言えることになる。この経路帯域計算プロセスには２つの問題がある。第１の問題は、ステーションＢ（ここではＢは、ＡからＢに至るリンクの容量を予約する役割を担うと仮定する）がどのようにして２つの隣接リンクの一連の共通空きスロットを認識するかであり、そして第２の問題は、この情報をその隣接体とどのようにして共有するかである。これらの問題を解決するために、複数のステーションは幾つかのメッセージを互いに交換する必要がある。

干渉の無いチャネル
参考文献［１６］は、参考文献［４］に記載されるチケットベースの手法を基本とするマルチパスＱｏＳルーティングプロトコルについて記載している。「マルチパス」という表現は、接続元から接続先に至る予約容量を幾つかのサブパスに分割し、各サブパスが最初にリクエストされた容量の一部として機能する場合を指す。しかしながら、この操作は、リンクの帯域がその隣接リンクから独立に決定されるという点で、全く理想的なモデルを仮定としていると言える。この仮定をサポートするために、各ホストが、互いに独立して動作することのできる複数のトランシーバを有し、そして各リンクが、衝突を避けるために２ホップ離れた隣接体が使用するコードから区別できるコードを割り当てられる、と仮定する。２ホップ離れた隣接体とは隣接体の隣接体である−この例では、上記のＡ及びＣが２ホップ隣接体である。

主干渉のみを考慮に入れる
干渉の無いチャネルよりも厳しくない仮定が参考文献［１２］，［１３］及び［１５］で行なわれており、これらの文献では、ＣＤＭＡ−ｏｖｅｒ−ＴＤＭＡチャネルモデルを仮定する、すなわち一のリンクを通して一つのタイムスロットを使用する操作がその隣接リンクのステータスのみに依存するとする（すなわち、これらの文献は主干渉のみを考慮に入れる）。これらの３つの参考文献が着目する点は、接続元から接続先に至る経路で利用できる帯域の計算であるが、要求される情報を収集する方法は異なる。

次に参考文献［１２］及び［１３］の概略動作について簡単に記載する。ＲＲＥＱ（Ｒｅｓｏｕｒｃｅ ＲＥＱｕｅｓｔ）を受信すると、接続元からこのノードに至る帯域を計算する。この帯域は最適な方法で計算することができる。何故なら、利用可能な帯域計算の前に、利用可能な空きスロットについての情報をその隣接体と交換し、そしてＲＲＥＱメッセージがノードから接続元に至る経路の前のリンクで使用されるスロットを含むからである。ＲＲＥＱは、結果がＱｏＳ要求を満たさない場合には受け付けられない。予測されるように、接続先は２つ以上のＲＲＥＱを受信し、各ＲＲＥＱは接続元から接続先に至る特定の実現可能な経路を示す。接続先は経路の内の一つを選択し、そしてＲＲＥＰ（Ｒｏｕｔｅ ＲＥＰｌｙ）メッセージを発行する。ＲＲＥＰメッセージが接続元に返されると、経路に位置する各ノードは予め計算された空きスロットを予約する。

参考文献［５］には、ＩＥＥＥ８０２．１１ネットワークのＱｏＳルーティングプロトコルが記載され、このプロトコルは上述の帯域計算アルゴリズムを利用する。

参考文献［１５］においては、利用可能な帯域をホップ毎に計算するのではなく、各ＲＲＥＱパケットが接続元から接続先に至る全てのリンク状態情報を記録する。このようにして、接続先は接続元から接続先に至る最適経路を計算する機能を有し、そしてＲＲＥＰメッセージを選択経路に沿って発行する。マルチパスルーティングの選択についてもこの参考文献に記載されており、そしてこの選択は、接続先が接続元から接続先に至る全ての利用可能な経路についての全ての情報を有するので、容易に行なわれる。参考文献［１５］が提案するアルゴリズムはフローネットワークを目標とする、すなわち複数の異なるフローをサポートする。帯域要求を満たす、接続元からのフローネットワークを決定するのが接続先ノードのタスクとなる。そのような解決方法は、干渉が無視できるほぼ最適ルートを提供できる可能性があるが、この方法は接続先ノードに非常に大きな計算負荷も課してしまう。

主干渉及び副干渉の両方を考慮に入れる
クラスターベース
参考文献［１０］，［１１］，［１４］及び［１８］に記載されたクラスターベースのネットワークでは、ノードはクラスターヘッド、ゲートウェイまたは単なる普通のノードとなることができる。ノードが一旦クラスターヘッドとして選ばれると、全てのその隣接体は同じクラスターに属する。２つ以上のクラスターに属するノードはゲートウェイの役割を担う。ＣＤＭＡを使用して複数のクラスターを、異なるコードシーケンスを異なるクラスターに割り当てることにより区分し、そしてＴＤＭＡをクラスター内で使用する。このようにすることによって、これらのクラスターは、クラスター間の干渉を無視できるので、クラスター内の副干渉のみを考慮に入れればよい。利用可能なスロットについての情報をクラスター内で広めるために、全てのノードはそのノードのスロット予約ステータスを含む「空きスロット」メッセージを周期的に送信する。クラスターヘッドはクラスター内の他の全ノードと通信することができるので、クラスターヘッドはクラスター内の予約ステータスについて完全に認識している。クラスター内の全ノードとしてのクラスターヘッドは「空きスロット」メッセージを送信する義務があるので、全ノードは最終的にはクラスター全体のスロット予約を認識することになる。これによって、利用可能な帯域の計算が簡単になる。次に、利用可能帯域計算及び利用可能帯域通知を各ノードで独立してホップ毎に実行する。

参考文献［１８］が提案する方法は実際は集中制御手法ではない。それに代わって階層的方法が提案される−まず、容量割当てをノード（リンク）レベル及びフローレベルの両方で（これらの両方のステップでは固定ルーティングを仮定する）行ない、次にＢｅｌｌｍａｎ−Ｆｏｒｄアルゴリズムの分散版を最終のルート選定に使用する。全てのノードに割り当てられるスロットをタイムフレームの適切な部分に或るメカニズムによって割り当てると仮定するが、ＭＡＣレイヤは考慮に入れない。また、一の中央エンティティが全ての情報を収集し、計算を行なって、そして次に最終結果を配信することが必要である、すなわち集中制御手法である。

以下に記載する参考文献［１７］及び［１９］では、普通のＴＤＭＡ／スロット構造を仮定するので、プロトコルはネットワークの全ノードに関する主干渉及び副干渉の両方を考慮に入れる必要がある。

Ｌｉａｏ
参考文献［１７］に記載された方法では、ノードがまずそれ自体の自律性の部分グラフを認識する必要があることが要求される（これはノードが、その隣接体及び隣接体の隣接体（普通、２ホップ隣接体と呼ばれる）がどのようにして相互接続されるかを認識することを意味する）。また、ノードは隣接体が受信または送信に使用しているスロットに関して完全に認識する必要もある（ここで、ノードがビジーであるかどうかを認識するだけでは十分ではないことに留意されたい）。この条件は２ホップ隣接体にも当てはまる。これらのデータ構造を構築するために、ホストは周期的にこの情報をその隣接体にブロードキャストする必要があり、そしてこれらの隣接体はこの情報をそれらの隣接体に再ブロードキャストする必要がある。この情報により、ルーティング及びスロット割当てを実行することが可能になる。このルールは（ほとんどの他の論文に記載されているように）、スロットが、２つのノードが共にスロットが空いていることを示す場合にのみ割り当てられ、そして送信側ノードがその隣接体のいずれに対しても干渉しない、というものである。この方法では最適な経路帯域を計算できないことに注目されたい。

Ｚｈｕ
参考文献［１９］に記載された方法は、主干渉のみを考慮に入れる手法の幾つかに類似するが、この方法では利用可能な帯域を最適に計算することはできない。接続元から接続先に至る経路に無い他のノードとの副干渉の観点から、送信に使用できるのはどのスロットであるかについてノードがどのようにして認識するかについて何も触れられていない。ＭＡＣレイヤにおいて基礎をなすスロット割当てプロトコルの役割が、スロットが該当する送信機に割り当てられ、そしてこれらのスロットがノードの隣接体に受け入れられることを保証するためにノードはどのようにして互いに合意するかについて取り決めることである、と述べられているに過ぎない。

更なる最先端解決法
参考文献［２０］では、２つのノードが、これらのノード間の距離が或る所定値を超えない、すなわちパケットが他のノードによる外部干渉が無い状況でエラーを生じることなく受信される場合に接続されることを仮定することによってグラフモデルを構築している。副干渉に関する比較的実用的なモデルが使用される。全ての受信側ノードの信号対干渉比（Ｓｉｇｎａｌ−ｔｏ−Ｉｎｔｅｒｆｅｒｅｎｃｅ Ｒａｔｉｏ：ＳＩＲ）が所定のしきい値を超える場合に、２つ以上のステーションが同じタイムスロットで送信を行なうことができる。ルーティング決定は、接続元−接続先ペア間の最小ホップ接続に基づいて行なわれる。ネットワーク接続形態（グラフモデルにより示される）が与えられると、ホップ及び可能経路の数は、パケットをネットワークを通してブロードキャストし、そして通過したノードの数をカウントすることにより求めることができる。接続元と接続先との間に等しい数のホップ数を有する複数の経路が検出されると、前のスロット割当て及び相対トラフィック負荷を判定基準として使用して、ネットワークにおける負荷バランス均等化を実現する。このようにすることにより、輻輳が生じ難くなり、そしてスループットが増大する。つまり、５ステップに従うアルゴリズムは次のように記載することができる。第１ステップでは、グラフモデルを使用してネットワーク接続形態を生成する。次に、ルーティング決定を使用し、利用可能な容量を考慮に入れながらリンク間の均衡のとれたトラフィックを生成する。各リンクの容量はルーティング決定に必要であるので、等しいリンク容量をこのステップで考慮に入れる。第３ステップでは、参考文献［８］の場合のような競合の無いスケジューリングアルゴリズムのいずれかを使用してスケジュールを生成する。この後、ルーティング決定を再度行なうが（ステップ４）、今回はスケジュールにより設定される実容量に基づく。最後のステップでは、ネットワーク全体のスループットを最大にしたルーティング決定（第２または第４ステップ）を選択する。参考文献［２０］は実際は、順次ルーティング、従って自律ルーティング及びスケジューリング／予約を基本としている。この方法が集中制御型の経路及びリソース割当て決定を必要とする点も注目すべきである。

参考文献［２１〜２２］はネットワークレイヤにおけるルーティングの問題に触れるのではなく、むしろ、基地局制御装置によって物理レイヤ及びＭＡＣレイヤのパラメータを適応させる形で変更する適応無線通信に着目している。

最先端解決法に関する問題
自律分散チャネルアクセス及びルーティング方法は概して、最適とはとても言えない。その理由は単に、ルート及びチャネルリソースの割当て問題が２つのより簡単な問題に細分されただけであるからである。また、自律分散方法は多くの場合、経路及びリソース割当てのオフラインかつ集中制御型の決定を仮定している。これは、情報を収集し、処理し、そしてその結果を関連ノードに通知する必要があることからすると、これらの自律分散方法が「処理を移動できる」という点でかなり貧弱であることを意味する。

或る形の「集中制御」チャネルアクセス及びルーティングに関する幾つかの良いアイデアを示してきたが、重要な無線形態が全く無視されている。従って、果たしてアルゴリズムの有用性についてはどうだろうかと懸念される。例えば、送信側ノードが他の受信側ノードに決して干渉しないようにノードが直交コードを使用するという極端に単純化された仮定が論文の幾つかで使用されている。実際にはコードは、例えば遅延拡散によって完全には直交せず、従って有害な干渉を生じさせるのでこの仮定が単に間違っているだけでなく、この仮定では貴重なリソースが非効率的に使用されてしまう。信号の直交性は帯域（ＢＷ）拡大の結果であり、また帯域は、データをより高いレートで送信することにより有効に使用できる可能性がある。従来の「集中制御」チャネルアクセス及びルーティング方法において提案される経路及びリソース割当て手順は非常に簡素化されてもいるが、実際には利用できないルートを推奨してしまうことがある。

課題を解決するための手段
本発明は、先行技術の構成におけるこれらの不具合及び他の不具合を解決する。
本発明の全体としての目的は通信ネットワークにおける利用可能なリソースの利用効率を改善することにある。
本発明の目的はまた、無線マルチホップネットワークのような通信ネットワークにおいてＱｏＳをサポートするための強固で効率的なメカニズムを実現することにある。この点に関して、サービス品質を保証しながらネットワークの全ての機能を生かすことが望ましい。
本発明の別の目的は、各個々の接続に対して実質的に干渉の無い、または衝突の無い通信を少なくとも所与の小集団ネットワークにおいて実現することにある。
本発明のさらに別の目的は、無線マルチホップネットワークのような通信ネットワークにおいて接続設定を行なうための改良された方法及び該当する制御システムを実現することにある。
本発明のさらに別の目的は、無線マルチホップネットワークのような通信ネットワークにおいて接続を決定するための改良された方法及び該当する制御システムを実現することにある。
本発明の目的はまた、無線マルチホップネットワークのような通信ネットワークにおいて接続認証制御を行なうための改良された方法及び該当する制御システムを実現することにある。
本発明の別の目的は、複数のネットワークノードを有し、これらのノードの内の少なくとも一つが、改良された形で接続決定を行う手段を含む通信ネットワークを実現することにある。
本発明の目的はまた、正しい接続パラメータを求める際の計算の複雑さを制御する方法を見出すことにある。

本発明は基本的に、ネットワークの幾つかのプロトコルレイヤの機能を、少なくとも３つのプロトコルレイヤの接続パラメータに関する単一の目的関数を統合する形で最適化することによって単一の統一メカニズムにレイヤ間で統合することを目的とする。

好適には、関連するプロトコルレイヤはネットワークレイヤ、リンクレイヤ及び物理レイヤを含む。しかしながら、他のプロトコルレイヤを統合最適化に使用することができることを理解されたい。３つよりも多くのプロトコルレイヤを、例えば３つの最低位レベルをアプリケーションレイヤのアプリケーションへの適応操作と一緒に考慮に入れることにより最適化に使用することも可能である。実際、本発明の統一手法によって、レイヤ表示の必要が一部、または全く必要が無くなる。幾つかの個別の最適化アルゴリズムを異なるプロトコルレイヤにおいて程度の差はあれ個々に実行するのではなく、単一の統一最適化を行なう。

本発明の好適な実施形態では、ルーティング、チャネルアクセス、物理レイヤ機能、及び任意選択の認証制御も、経路、チャネル、及び一つ以上の物理レイヤ／リンクパラメータを含む接続パラメータを統合最適化に使用することにより単一の、統一メカニズムに統合する。この場合、各接続は結果的に少なくとも三つ組によって定義され、この場合三つ組は選択経路、選択チャネル及び一つ以上の物理レイヤ／リンクパラメータを含む。

衝突の無い、または干渉の無い通信を実現するために、最適化は一つ以上の制約に従い、この制約はリクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成される。

物理レイヤ接続パラメータを統合最適化に取り入れ、そして最適化を一つ以上の干渉関連の制約の下に実行することによって、干渉問題を、無線マルチホップネットワークのようなネットワークにおいてＱｏＳを提供するための統一手法にも細心の形で考慮に入れることができる。これは、リクエストされる接続のリンクも含む実質的に干渉の無いリンクを保証する接続パラメータを求めることが可能であることを意味する。

実際、目的関数はリンク送信電力、遅延、ローカル負荷、電池残量、及びリンクマージンのような項目を含むことができる。物理レイヤパラメータは通常、リンク動作を定義し、そして送信電力、変調パラメータ、帯域幅、データレート、誤り訂正パラメータなどのような一つ以上の物理リンクパラメータを含む。他の物理リンクパラメータは、多入力多出力（Ｍｕｌｔｉｐｌｅ−Ｉｎｐｕｔ−Ｍｕｌｔｉｐｌｅ−Ｏｕｔｐｕｔ：ＭＩＭＯ）パラメータ、アダプティブアンテナ（Ａｄａｐｔｉｖｅ Ａｎｔｅｎｎａ：ＡＡ）パラメータ及び他のアンテナ構成パラメータを送信側、受信側、または双方で含む。

利点を生じる形で、統合最適化は発見的アルゴリズムを通じて行なわれる。接続パラメータは、例えば自律探索手順において求めることができる。この点に関して、統合最適化は、各ネスティングレベルがネットワークプロトコルレイヤを表わすネスト化されたアルゴリズムと一緒に機能させれば有用であることも判明している。

本発明の特定の実施形態では、どこまで遠くこのアルゴリズムが動作するかを示す地平線（ｈｏｒｉｚｏｎ）が、演算の複雑さの所定の許容レベルに対応する最適な性能を実現できるように選択可能である。

固有の予め定義されたユニットがリクエストに応じて接続を決定する構成の集中制御型の実施形態に加えて、要求される情報の転送のためにＲＲＥＱ（Ｒｅｓｏｕｒｃｅ ＲＥＱｕｅｓｔ）及びＲＲＥＰ（Ｒｏｕｔｅ ＲＥＰｌｙ）シグナリングを使用して最適化アルゴリズムをネットワークの複数のネットワークノードに分散することも可能である。この分散型のシナリオでは、所定の接続リクエストに対して、最適化アルゴリズムを関連するネットワークノードでノード毎に実行する、またはネットワークを通して転送されたＲＲＥＱにおいて照合される情報を使用して接続先ノードで全てを実行することができる。

最適化の考慮されたネットワークは主としてワイヤレス（無線、光など）マルチホップネットワークであるが、本発明は無線及び有線技術を組み合わせて構成する多重接続ネットワークのような他のネットワークにも適用することができる。

ここで、「チャネル」という用語は、タイムスロット、周波数帯域、直交符号、または他の全ての直交チャネル、或いはこれらの組合せ、スロット化されていないチャネルさえも含むことを理解されたい。

要約すると、本発明は、無線マルチホップネットワークのような通信ネットワークにおけるＱｏＳの提供に重点を置くだけでなく、複雑性の低い経路検出アルゴリズムの利用を保証しつつ無線媒体の効率的な利用を目標とする。提案するアルゴリズムは固定ノードシナリオという固定構成に限定されるのではなく、或る環境下で低い、または中位の移動性に対応することができる。

本発明は次の利点を提供する。
・高いネットワーク利用効率
・保証された遅延及び保証されたスループットを含む効率的なＱｏＳサポート及び提供
・実質的に衝突の無い通信
・性能ゲイン、及び最適解の組み合わせの複雑度に対する演算の低複雑性
・演算の複雑性に対する柔軟な制御
・送信電力を目的関数に使用する際の低消費電力
・遅延を目的関数に使用する際の短いエンドツーエンド遅延
・分散型制御及び集中型制御の両方が利用可能
・ほぼ真の最短経路、または非常に低い負荷での真の最短経路の選択が可能
本発明が提供する他の利点は以下に示す本発明の実施形態に関する記載を一読することにより理解されると考えられる。

本発明はその更なる目的及び利点と共に、次に示す記載を添付の図面と共に参照することにより最も深く理解されるであろう。

本発明の理解を深めるために、ルーティング及びチャネルアクセス方式に関する先行技術について図１を参照しながら要約する。従来のルーティング及びチャネルアクセス方式において、各プロトコルレイヤは通常、その固有の独立アルゴリズムＡ１，Ａ２，Ａ３に関連付けられる。時々、抽出データを低位レイヤから高位レイヤに転送して或る形で「ソフトに」レイヤ間を統合する、または順次レイヤ間を統合する。低位レイヤからの抽出データは単純に高位レイヤに転送されて高位レイヤアルゴリズムが使用し、この場合適応化のための低位レイヤに対するフィードバックは行なわれない。例えば、リンク帯域に関する抽出データをリンクレイヤＬ２からネットワークレイヤＬ３のルーティングアルゴリズムＡ３に送信する。次に帯域情報をルーティングアルゴリズムが使用し、このルーティングアルゴリズムは、帯域が非常に狭い場合に、例えば経路割当てを変更する。各々がその固有の目的関数に関連付けられる幾つかの独立アルゴリズムを使用するこの手法は比較的単純な形のレイヤ間統合であるが、このレイヤ間統合は、仮に実現可能な経路が生成され得るとしても次善の結果しかもたらさない。従来の集中制御チャネルアクセス及びルーティング方法を注意深く解析すると、これらは全て２つのプロトコルレイヤでしか動作せず、そして多くの場合、干渉問題を完全に無視しているので、次善のルートしか提供せず、そしてネットワークの全ての可能性を活用するわけではない、ということも判明した。

参考文献［２３〜２５］は全て、本特許出願が基本とする米国仮特許出願番号６０／３５８，３７０の出願日後に発行された米国特許出願公報である。

参考文献［２３］はリンクレイヤから転送されるリンク品質指標に基づくアドホックインターネットワーキングのルーティングについて記載している。

参考文献［２４］は、時間と共に変化する無線伝送特性を考慮に入れ、最小歪基準または最小電力基準に基づいたチャネル適応リソース割当てを行なうセルラーネットワークについて記載している。

参考文献［２５］は、リンクレイヤ管理をネットワークレイヤ管理に統合したメディア抽出ユニットの使用について記載している。種々の伝送パラメータを環境因子の変化に応じて変更し、そしてこの変更により利用可能なリンク帯域を変更し、今度はこの変更後のリンク帯域をネットワークレイヤトラフィック管理の段階で使用する。

参考文献［２３〜２５］は単に、「ソフトに」レイヤ間を統合する操作の種々の変形を記載しているに過ぎず、これらの変形は、一度にせいぜい２つのプロトコルレイヤを含むだけであり、この場合抽出データは低位レイヤから高位レイヤに転送される。

図２に模式的に示すように、本発明は、好適にはレイヤＬ１，Ｌ２，Ｌ３を含む少なくとも３つのプロトコルレイヤの接続パラメータに関して単一の目的関数を統合する形で最適化する統一アルゴリズムを提案することにより、ルーティング、チャネル割当て、及び物理リンクパラメータ適応を行なうための真の統合及び統一手法を提供する。程度の差はあれ個々に自律分散最適化アルゴリズムを有するのではなく、単一の統一最適化を本発明に従って行なう。図２の破線枠で示す他の任意関数が依然としてネットワークレイヤＬ３、リンクレイヤＬ２、及び物理レイヤＬ１に存在することを妨げるものは何も無いが、前に述べたように本発明の統一手法は実際に、階層化表現の必要を無くすことができる。これらの関数は本発明による統一アルゴリズムと連携する、または連携しないことができる。

次に本発明について特定の通信ネットワーク、すなわちワイヤレス（無線、光など）マルチホップネットワークを参照しながら記載する。しかしながら、本発明はこの特定の通信ネットワークに限定されるのではなく、無線技術及び有線技術の融合技術としてのマルチアクセスネットワークのような他のネットワークに適用することもできることを理解されたい。

基本原理及びネットワーク概要
上述のように、本発明は概して、ネットワークの幾つかのプロトコルレイヤの機能を真にレイヤ間統合した形で表現することにより、マルチホップネットワークでＱｏＳを提供する統一手法を実現する。本発明による統一手法では、接続を、ネットワーク内の少なくとも３つのプロトコルレイヤの接続パラメータに関する所定の目的関数を統合する形で最適化することにより決定するのが好ましい。

本発明の理解を深めるために、例示としての無線マルチホップネットワークを簡単に概括することから始めるのが有用であると考える。図３は例示としての無線マルチホップネットワークの模式図であり、幾つかの重要なコンセプトを示している。我々は複数のノードを含むネットワークを有していると仮定する。ネットワークは無線媒体の中で動作し、この無線媒体では、送信が互いに干渉する可能性がある。ネットワークの２つのノード間で送信されるトラフィックをフローと呼ぶ。そのようなフローのデータの送信者を接続元ノードと呼び、そして受信者を接続先ノードと呼ぶ。各時点で、ネットワークはゼロの、一つの、または多数のトラフィックフローを搬送する。各フローは接続（旧来のネットワーキングの回路としても知られている）を通して搬送される。簡単のため、図３には一の接続のみを示している。勿論、実際は幾つかの接続が同時に存在する。

接続元ノードから接続先ノードに至る接続は、経路を含む多数の接続パラメータだけでなく、経路に沿ったチャネルパラメータ及び物理レイヤパラメータにより定義することができる。接続元から接続先に至るには幾つかの異なる経路が存在し得る。各経路は一組のリンクにより形成され、そして２つの隣接ノードｉとｊとの間の各リンクは幾つかの異なる通信チャネル及び物理リンクパラメータ設定を使用することができる。経路は複数のノードの識別情報により特徴付けることができる。

物理リンクパラメータとも呼ばれる物理レイヤパラメータは、経路に沿った各ノードの送信側及び／又は受信側に関連付けることができる。送信側物理リンクパラメータは、例えば送信電力、送信変調などとすることができる。受信側リンクパラメータはアンテナアレイの調整を含むことができる。個別チャネルを通しての通信は完全直交と考えられるので、互いに干渉しない。中継ノードでの一のチャネルから別のチャネルへの変更はチャネル切換えと呼ぶ。接続は通常、上限データレートを有し、フローは利用可能なデータレートまたは全帯域の一部を使用することができる。互いの接続範囲内のノードは通常、隣接体と呼ばれる。明らかなことであるが、「接続範囲内（ｗｉｔｈｉｎ ｒｅａｃｈ）」という用語に関して幾つかの定義が可能である。好適には、ノードの接続範囲内に在るという状態は、受信側での平均信号対ノイズ比（ＳＮＲ）が、最大許容送信電力を送信側ステーションで使用し、かつ干渉するステーションが存在しない場合に所定レベルを超える事象を指す。

幾つかの点で最適となる接続パラメータを求めることが望ましい。明確に定義された形での最適性についての説明を可能にするために、目的関数ｆを導入する。一般的に、目的関数ｆは細心の注意をもって選定し、そして経路、チャネル及び物理レイヤパラメータのような接続パラメータに依存する形で構成する。物理レイヤ／リンクパラメータが普通、目的関数の一部を構成するが、ローカル負荷または電池残量のような他の非物理レイヤ／リンク要素を目的関数に組み入れることができる。次に目的関数を関連する接続パラメータに関して最適化することにより、接続に関する最適接続パラメータも同時に求める。パラメータという用語は、当業者には容易に理解できるように、可変パラメータ自体、及び該当するパラメータ値の両方を表わすために使用される。

最適化を公式化する際には次のような表記を使用する。
Ω ネットワークの全ノード（またはネットワークの着目部分）を表わす。
Ｍ 全直交チャネルの集合を表わす。
ψ 一の、または多数の物理レイヤパラメータを表わし、従って物理レイヤパラメータに関して多次元であり、各可変パラメータ自体は定義空間を有し、その空間では可変パラメータは連続値または離散値を採ると仮定する。

目的関数ｆを最適化する際に、上述の集合Ω、Ｍ、ψから選ばれる入力パラメータを使用して、経路、チャネル及び物理レイヤパラメータを含む接続を定義する実際の接続パラメータが得られる。
Ｒ 接続元と接続先との間の実ノードを定義する。

Ｓ_ｕ ノードｕが送信に利用するチャネルの集合を定義する。

ここで、Ｍ（ｕ）はノードｕの最適チャネルの集合であり、そしてノードｕは接続先ノードを除く経路Ｒに属する。
Ｔ_ｕ，ｖ チャネルｖのノードｕに対応するパラメータ値の集合を定義し、送信及び／又は受信パラメータを含むことができるが、接続元ノード（送信パラメータのみ）及び接続先ノード（受信パラメータのみ）に関するパラメータは除く。

ここで、ψ（ｕ，ｖ）はチャネルｖのノードｕにおけるパラメータの最適集合であり、ｖはＭ（ｕ）に属し、そしてｕは経路Ｒに属する。

単一の目的関数が経路、チャネル及び物理レイヤパラメータに関して最適化されることにより、実際上、ネットワークレイヤを通してのルーティング、リンクレイヤを通してのチャネル割当てだけでなく、物理レイヤ機能に対して真のレイヤ間統合を行なって単一の統一メカニズムとすることができる。

正しく構成された制約に従うとき、本発明が提案するレイヤ間の関連付けの最適化によって、一の、または多数の接続を有するネットワークを実現することができ、この場合これらの接続は、実質的に衝突の無い通信が各個々のフローに対して保証されるように割り当てられる。実際には、完全に衝突の無い通信は可能ではない。しかしながら、衝突の無い度合いは実際には、パケット誤り率（Ｐａｃｋｅｔ Ｅｒｒｏｒ Ｒａｔｉｏ：ＰＥＲ），搬送波対干渉比（Ｃａｒｒｉｅｒ−ｔｏ−Ｉｎｔｅｒｆｅｒｅｎｃｅ Ｒａｔｉｏ：ＣＩＲ，ノイズも含むとする）、信号対ノイズ比（Ｓｉｇｎａｌ−ｔｏ−Ｎｏｉｓｅ Ｒａｔｉｏ：ＳＮＲ）などの関連性能指標の全てを所定の目標値未満または所定の目標範囲に維持する度合いとして定義することができる。例えば、衝突の無い通信は、干渉及び他の有害な無線の影響により生じるパケット損失が任意の低いレベルに維持される限り満たされる通信であると定義することが出来る。

このようなレイヤ間統合に関する最適解は非常に複雑な計算を必要とする。例えば、ＴＤＭＡまたはＦＤＭＡのような多重接続方式における経路及びチャネルを選択するだけでも、良く知られたいわゆるＮＰ完全問題（実行時間が入力サイズに関して非多項式関数、すなわち多くの場合に指数関数的に定義される）が生じる。物理リンクパラメータの最適化のような追加の機能を組み込む場合には、問題をさらに悪い方に複雑にしてしまう。

全体としての方策は、ｐｃｒ（ｐｅａｋ ｃｅｌｌ ｒａｔｅ：ピークセルレート）フローベースでのＱｏＳ提供及び認証制御を管理することであり、これは従来の集中制御ルーティング及びチャネルアクセス方式に関して記載したものと同様である。しかしながらここでは、さらに幾つかの新たな状況も考慮に入れる。

次に全体としての方策について図４のフロー図を参照しながら記載する。設定リクエストが行なわれて第１フローがネットワークに確立されると（Ｓ１）、幾つかの点で最適な接続が選択される必要がある。好適には、この操作において、経路、チャネル及び一連の物理リンクパラメータを選択することにより、接続が衝突の無い状態になり（すなわち、それ自体の送信の影響を受けない）、そしてこの接続により所定のメトリックが最適化される（Ｓ２）ようにする。接続認証制御は、実現可能な経路が検出されるかどうかについての情報を使用することにより行なわれる（Ｓ３）。実現可能な経路が検出されると、接続が確立され（Ｓ４）、そしてデータが送信される（Ｓ５）。確立される追加の各フローに対してこの手順が繰り返されるが、新規の接続が既存の接続との衝突を起こさない、または既存の接続からの衝突を受けないことも高い確率で保証される。リクエストされる接続が最適化を行なう際に遵守すべき制約のために設定できない場合、フローのネットワークへの参加が認証されないことになる（Ｓ６）。そのような場合にユーザが採る措置は本発明の主要な関心事ではないが、通常、低いＱｏＳ要求で（例えば、サポートされている場合の低データレート）接続設定を再度開始する、または設定をネットワーク負荷が小さくなるまで先に延ばす。さらなる代替手段としては、接続先が設定段階で最大レベルの利用可能なＱｏＳに関する情報を取り出す機能を有するようにすることである。この場合には、この情報を接続元に転送して接続元に新規に設定を行なわせる。接続元が承認すると、接続先は最適ＱｏＳ要求に完全には合致しない経路を予約することもできる。

フロー解除リクエストが行なわれると（Ｓ７）データの送信が終了する（Ｓ８）。フローが終了すると、該当するネットワークリソース及び無線媒体が解除される（Ｓ９）ので、媒体に空きができ、必要なときには新規接続がいつでも確立できる可能性が高くなる。

従って、接続を決定するプロセスでは、既存の接続だけでなく新規接続の基本部分が干渉を受けない状態を保証しつつ、信頼度の高い動作を行なうための十分なレベルのマージンを維持できるように物理レイヤパラメータを選択するのが好ましい。好適には、物理レイヤパラメータは、各リンクに対して適切な送信及び／又は受信パラメータを選択する物理リンクパラメータである。従って、送信及び／又は受信パラメータの適応化は選択する経路に影響を与える。逆に、選択する経路も送信及び受信パラメータの適応化に影響を与える。

従って接続は、要求があればいつでも要求に応じて設定することが好ましく、この場合{経路、チャネル、及び物理リンクパラメータ}のような接続パラメータの全ては基本接続固有のリンクチェーンを含む、干渉の無い、または衝突の無いリンクを保証するように最良の形で選択される。換言すれば、本発明の本実施形態では、我々は、経路、チャネル及びリンクパラメータ選択によるイベント駆動型の接続設定を扱う。

ネットワークでは種々のデータレートだけでなく、データレートの上げ下げを可能にするメカニズムもサポートすることができる。重要な利点となり得るのは効率的なリソース利用であり、これはいかなる負荷状況においてもシステム停止確率が低いことと解釈できる。

選択する目的関数に応じて、最適化は最小化または最大化になる。本発明の好適な実施形態では、最適化の全体としての目的は目的コスト関数を最小化することである。

利点として挙げることができる点であるが、最適化は、発見的アルゴリズムを使用することにより、例えば自律探索手順において接続パラメータを求めることにより行なわれる。特に、目的関数の問題はノード固有の目的関数の集まりとして公式化することができる。最適化はネスト化されたアルゴリズムと一緒に機能させれば有用であることも判明している。

次に本発明について、コストの最小化を目標とするネスト化された最適化アルゴリズムの特定例を参照しながら記載する。

経路、チャネル及びリンクパラメータ決定アルゴリズム例
本考案は、ディレクテッドスパニングツリーを予備経路で形成して接続元ノードを根とする未使用の接続を決定することである。一旦アルゴリズムが安定すると、接続元ノードと接続先ノードとを接続するルートを選択する。従ってアルゴリズムは、一括してＣＦＰＲ（衝突の無い経路ルーティング：Ｃｏｌｌｉｓｉｏｎ Ｆｒｅｅ Ｐａｔｈ Ｒｏｕｔｉｎｇ）アルゴリズムとして示す次のアルゴリズムに従って、指定された接続元ノードから所与の集合内の各ノードｉに至るための最小コストＫ_ｉを見つけ出すための探索手順を含む。

ここで、ｉ≠Ｓｏｕｒｃｅ ＩＤ，Ｎ（ｉ）はノードｉの現時点における隣接体の集合であり、この集合が今度はネットワークの全ノードΩの集合となり、ｊはＮ（ｉ）に属する隣接ノード、ｍは合計でＭ個の直交チャネルの集合の中の一つ以上のチャネルの集合、ψは一の、または多数の物理レイヤパラメータ、ｋ_ｉ（ｊ，ｍ，ψ）はノードｊからノードｉに至るまでのコスト、そして項Ｋ（ｊ）は接続元ノードからノードｊに至るまでの累積コストである。コストｋ_ｉ（ｊ，ｍ，ψ）は各チャネル及び幾つかの物理リンクパラメータ（群）に対応する値とする。Ｋ_{Ｓｏｕｒｃｅ ＩＤ}は接続元ノードでの初期コストであり、通常ゼロに設定される一定値とする。集合Ｎ（ｉ）は隣接ノードｉの現時点での隣接体の選択可能な集合であり、必ずしも全ての隣接体を含む必要はない。

チャネルの集合ｍはリクエストされる帯域に応じて一つ以上のチャネルを含むことができる。狭帯域接続の場合、単一のチャネルで十分である。広帯域接続の場合、数チャネルが必要になる。

一般的にサブインデックスとしてｉ及びｊのようなノードインデックスを書き込むことが許されるので、我々は単純にｋ_ｉ（ｊ，ｍ，ψ）をｋ_ｊｉ（ｍ，ψ）と、Ｋ（ｊ）をＫｊと示す。このような表記法により、接続元ノードからの最小コストＫ
_iを求めることを目標とするＣＦＰＲアルゴリズムを要約すると次のようになる。

この等式の各ネスティングレベルはほぼプロトコルレイヤを表わしている。最も内側の引数が送信電力のような物理レイヤパラメータの調整に使用される。従って、ｋ_ｉｊは通常、物理レイヤパラメータ（ψ）が採る値に依存するコストであるが、他の非物理レイヤ要素を組み込むこともできる。このような要素は、例えばローカル負荷、または残っている電池容量とすることもできる。次の選択レベルは個々の隣接体に対応するチャネル（群）の最良の集合（ｍ）の選択である。これはチャネルアクセスまたはＭＡＣレベルを表わす。第３のレベルは隣接体の中からの選択であり、これによりルーティングレイヤの経路を選択する。

一般的に、要求される情報を実行中のユニットが認識している、または収集できるとすると、最適化は固有の予め決められたユニットに完全に集中させることができる。しかしながら、アルゴリズムを複数のネットワークノード、好適にはマルチホップネットワーク内の全ノードに分散することも可能である。分散型のシナリオでは、詳細な実施形態は全情報が利用可能である、またはローカル情報しか利用可能できない、という状況に応じて変わる。後者の場合、アルゴリズムはノード毎ベースで関連するネットワークノードにおいて実行され、この場合後で詳細に記載するようにＲＲＥＱおよびＲＲＥＰシグナリングを使用して要求される情報を交換するのが好ましい。他方、要求される情報が接続先ノードに到達する途中で照合される場合、ＣＦＰＲアルゴリズムは該当する認証制御手順とともに接続先ノードにおいて照合情報に基づいて完全に実行することができる。

上に定義されるＣＦＰＲアルゴリズムは、特に分散型実施形態に適しており、この実施形態では最適化アルゴリズムが複数のネットワークノードに分散され、そして続いてノード毎ベースで関連するネットワークノードで実行される。これは通常、自律探索手順が各ノードｉで行なわれて、隣接体の選択された集合Ｎ（ｉ）における全ノードｊに対してノードｊからノードｉに至るまでの最小コストｋ_ｉｊ（ｍ，ψ）が見積もられ、そして接続元ノードから各ノードｉに至るまでの最小コストＫ_ｉが、この見積もりを各隣接ノードｊから受信するＫ_ｊに関する情報と一緒に併せたものに基づいて求められる。探索手順は、関連するノードからなるツリー全体がスパニングツリーを構成するまで各ノードにおいて継続して行なわれる。

ここで、ＣＦＰＲアルゴリズムがＢｅｌｌｍａｎ Ｆｏｒｄの最短経路アルゴリズムと幾つかの点で同じことを示していることに注目されたい。しかしながら、いくつかの相違点が在る。ＣＦＰＲアルゴリズムは多次元（チャネル）に渡って法則化されており、物理リンクパラメータ、チャネル及び経路を統合する形で最適化し、衝突が無いことを保証し、そして最短経路に近い経路を提供する。低負荷状態では、選定する経路は通常、実際の最短経路となる。図５は、ＣＦＰＲアルゴリズムに関連して使用する専門用語及び表記の可視化を試みたものである。

次に、新規の経路を設定する場合、既存接続のリンクを考慮に入れ、そしてこれらとの干渉を回避することが望ましい。同様に、既存接続のリンクが新規接続のリンクと干渉しないことを確認することも望ましい。従って、この場合２つのノード、すなわちノードｉ及びｊのみに着目しながらノード群を４集合に分割することが有用である。最初の２集合は単に、受信を行なうと考えられるノード、すなわちノードｉ、及び送信を行なうと考えられるノード、すなわちノードｊである。第３集合は、ノードｉを除いたノードｊの隣接体集合Ｎ（ｊ）である。この集合内のノードはｕとして示す。第４集合は、ノードｊを除いたノードｉの隣接体を含む集合Ｎ（ｉ）である。この集合内のノードはｖとして示す。通常、隣接体集合はほぼノード群の集合と同じである。

上に示したように、いずれかの適切なコスト関数を最適化に使用し、そして選択する物理接続パラメータ（群）のタイプは最適化の細部の目的に応じて変わる。しかしながら、理解し易くするために、次に、物理リンクパラメータを含む最適化の例示としての実施例について記載する。

送信電力のような物理リンクパラメータを含む最適化の実施例
本発明の好適な実施形態によれば、衝突の無い状況は、十分なレベルの受信マージンγを関連ノードに付与できるようにノードｊの送信電力を選択することにより保証される。ノードｉで受信を行なう場合、ノードｊは送信電力Ｐ_ｊ（ｍ）を使用して、結果としての受信電力Ｃ_ｉ（ｍ）が、集合Ｎ（ｉ）＼｛ｊ｝内のノードｖ（別の構成として、Ω内の他のノードも計算に使用することができる）が引き起こし、緩和係数γ_Ｍを有するノードｉで観察される干渉レベルを超えるようになることが必要である。同様に、ノードｊは送信電力Ｐ_ｊ（ｍ）を使用して、送信電力Ｐ_ｊ（ｍ）が少なくとも集合Ｎ（ｊ）＼｛ｉ｝内のノードｕのいずれかでの受信電力Ｃ_ｕ（ｍ）よりも受信係数γ_Ｒだけ小さくなるようにすることが必要である。ここで、チャネルゲインマトリクスＧ（ｍ）は既知であると仮定し、そしてそれによって受信電力及び送信電力を互いに関連付けることが可能となる。また、ノイズレベルＷは係数γ_Ｗを使用してノイズレベルがノイズで制限されるのではなく、概して干渉で制限されるようになることを保証する。

満されるべき更なる重要な条件は、ノードｊが決して、接続元ノードに向かうその固有の基本ルートに沿ったリンクに干渉しないことである。Ｒはノードｊに接続される基本ルートに沿ったノードの集合を表わし、ｒはＲ内のノードに付すインデックスである。最後に、受信機ノイズレベルをＷとする。

ノードｊからの最大限に許容され、最小限に要求される送信電力は次のように定義することができる。

ここで、Ｐ＾ｒ（ｍ）及びＣ＾ｒ（ｍ）はそれぞれ、集合Ｒ内の一のノードの推定（または基本）送信電力及び受信電力を示す。他方、Ｐｖ（ｍ）及びＣｕ（ｍ）はそれぞれ、確立されたトラフィックを有するノードの送信電力及び受信電力を示す。その後アルゴリズムが収束すると、接続元と接続先とを接続する予備経路が選択され、そして予備経路の有効期間が終了するまで活性経路として確立される。全ての送信電力だけでなく受信電力レベルも更新して新規に確立した接続を反映させる。

ここで、Ｐ＾ｍａｘ_ｊ（ｍ）の公式は、既存のリンク受信ノードでの結果として得られるＣＩＲが所定のＣＩＲレベルを下回る形で劣化することがないことを保証するものではないことに注目されたい。その代わり、この公式は単純化されていて、この公式によれば、緩和マージンγ_Ｍ＞受信マージンγ_Ｒが成り立つ場合に、ＣＩＲがγ_Ｒを下回る形で大きく劣化する状態が起こり難くなる。Ｐ＾ｍａｘ_ｊ（ｍ）が、ＣＩＲが所望のＣＩＲレベルを下回る形で劣化しないように保証できるように選択される場合の状況について後で記載することとする。

幾つかのチャネルが送信用または受信用に使用されない場合、アルゴリズムの構築には、送信電力をゼロに設定し、そして受信電力を∞に設定することが必要である。実際、コスト計算を行なうときにはそのようなチャネルを考慮に入れる必要が無く、従ってそのようなチャネルを省略することができる。

ｋ_ｊｉに関する合理的なコストメトリックはリンク送信電力である。このようなメトリックは全体の経路に渡って使用される累積送信電力を最小化するように作用する。これは電池消費電力の削減に適する上に、システムにおける干渉レベルも低くするので新規接続を組み入れるための空間を残すことになる。従って、システムは大きなネットワーク負荷で動作することができる。メトリックは次式に従って選択される。

ここで、Ｃは０と１との間の定数に選択される。これは、ｋ_ｊｉがＰ＾ｍｉｎ_ｊ（ｍ）及びＰ＾ｍａｘ_ｊ（ｍ）により制限されることを意味する。Ｃ＝０の場合、ｋ_ｊｉはＰ＾ｍｉｎ_ｊ（ｍ）に等しい。Ｃ＝１の場合、ｋ_ｊｉはＰ＾ｍａｘ_ｊ（ｍ）に等しい。コストを∞に設定する理由は、コストｋ_ｊｉ（ｍ）が、それが実現可能なときにのみ有用な値を採り得るからである。

正しく、高速に収束させるために、Ｋ_ｉ＝∞が成り立つときは必ず、ノードｉは接続元から導出される予備経路を廃棄し、そして関連する送信電力を０に、関連する受信電力を∞に設定する。予備経路にノードｉを有するノードは必ずこの手順を繰り返すものとする。

図６は、ノード３（接続元ノード）から発し、ノード３のｃｈ２からノード６に、ノード６のチャネルをｃｈ２からｃｈ３に切り換え、ノード６のｃｈ３からノードｊに至る予備経路を示している。図示の状況は、ノードｉ及びノードｊがｃｈ１で通信可能かどうかのテストの様子を示している。これには、ノードｊのチャネルをｃｈ３からｃｈ１に切り換える必要があるだけでなく、ノードｊが、例えばｃｈ１のノード１及び２に干渉しないことを保証する必要がある。同様に、ノードｊが十分なレベルの電力で送信を行なってこの送信がｃｈ１のノード４及び５からの干渉を受けているノードｉに到達することを保証する必要がある。

上の手順は経路及びチャネルが変化しない間、続行する。次に、新規の接続が確立されると、データが流れ始める。或る時間が経過した後、接続の必要が無くなると新規の接続は取り除かれる。接続の寿命がノードの移動性及び／又はチャネル変動に対して比較的短いとすると、低い移動性はサポートされる。

アルゴリズムは動的電力調整が不可能な場合でも機能する。この場合、物理リンク適応操作は、固定のリンク送信電力Ｐ_ｆｉｘ（ＯＮ）で送信を行なう操作と全く送信を行なわない（ＯＦＦ）操作との間での選択となる。好適にはリンク送信電力は、Ｐ_ｆｉｘがＰ＾ｍｉｎ_ｊ（ｍ）とＰ＾ｍａｘ_ｊ（ｍ）との間にある限りＰ_ｆｉｘとなるように選択され、そうでない場合にはリンク送信電力はゼロに設定される。

読者に本発明の基本コンセプトだけでなくＣＦＰＲアルゴリズムを理解して頂くために、次にＣＦＰＲアルゴリズム動作の一例を図７〜１３を参照しながら記載するが、これらの図は、方形エリアに分散し、そして１４のタイムスロット（ＴＳ）を使用する３６のノードを有するネットワークを描いている。各ノードは中抜きの円として描いている。接続元ノードは円内の黒星印で示し、接続先ノードは灰色の星印で示している。各ノードはノードの直ぐ右側に記したＩＤを有する。ノード間の接続は異なる諧調のリンクで示し、この場合中間調はＴＳ番号を表わす。ＴＳ番号はリンクと一緒に、リンクが相互接続するノード間の途中の括弧内にも示している。

図７はＩＤ５が付された接続元がツリーのルート（根）であることを示している。これはＣＦＰＲアルゴリズムが経路、チャネル、及び適応リンクパラメータからなる予備接続を生成したときの第１フローの接続設定局面を表わしている。ＣＦＰＲアルゴリズムのこの特定の実施形態では、最小ＴＳ番号は常に、等しく良好なタイムスロットが存在する場合に選択される。これが、スロット番号が接続元ノードから番号順に割り当てられる理由である。

図８はＩＤ３１が付された接続先ノードへの選択経路を示している。従って、接続元／接続先ペアの間のＣＦＰＲ最適経路を除く他の全ての予備経路が消されている。

第２フロー及び接続が確立されようとするときには、リンクが既存の接続及びその周辺の他の通路に有害な形で干渉することがないように選択されることが直感的に理解できる。図９において、ノードＩＤ７は接続元であり、ノードＩＤ３０は接続先である。

第２接続が確立されてしまうと、ＴＳ１，１３，１２，２及び３が再使用されたことがわかる。また、２つのスロットがノード２２と２３との間で同時に使用される。図１０は第１及び第２フローに対応する、結果として得られる経路及びチャネルを示している。

最後に、第３フロー及び関連する接続を確立する様子を図１１及び１２に示す。

ここで、図７〜１２は確立の様子のみを示していて、接続の解除は示していない。しかしながら後者は瑣末な事項であるので省略する。

上述の例では、γ_Ｍ＝８ｄＢ，γ_Ｒ＝５ｄＢ及びγ_Ｗ＝８ｄＢである。全ての活性状態の受信機の結果として得られるＣＩＲ ＣＤＦを図１３に示す。

接続元から接続先に至る衝突の無いリソースまたはトンネルを見れば回路交換接続を自然と思い浮かべることができるが、実質的な回路もこれらの衝突の無いリソースを利用していることが理解されるであろう。この場合、リンクの容量は通常、複数の接続間で共有される。これにより普通、各ノードでスケジューラを使用して各接続にその合意された容量を供給することが必要となる。

別の／任意の問題
チャネル動作及びマージンに関するコメント
視線上（Ｌｉｎｅ Ｏｆ Ｓｉｇｈｔ：ＬＯＳ）にある場合、ルーフトップネットワークによく見られるように、チャネルは比較的に安定である。従って、種々のマージンγは比較的小さくすることができる。しかしながら、チャネル強度がパケット期間またはインターリーブ長よりも長い時間に渡って変動するとき、マージンγを十分なレベルのマージンを有するように選択して既存または固有の接続に対する干渉によって大きな問題が生じないことを保証する必要がある。

コストの方向性
所定の等式中のｋ_ｉｊのインデックスｉ及びｊの順番を変えて、経路を逆さまに辿る代わりに、ノードｉからノードｊに至るコストを考察することができることに注目されたい。従って、接続元ノードからのコストを求めるのではなく、接続元ノードに向かうコストを求める。この場合、接続元ノードを接続先ノードとして、より適切な形で指定できる。

好適なアルゴリズムは試行錯誤により得られるものであるので、アルゴリズムによって常に経路が最小の達成可能なコストメトリックを保持できるわけではない。これを処理する方法の一つは、経路を２回求めることである。すなわち、１回目に、接続元をルート（根）として、２回目に接続先をルート（根）とする。次に、フローが接続元から接続先に向けられることを考慮に入れたメトリックを使用する必要がある。

複雑さ
複雑さを減らすために、多くの指標を採用する。まず、合理的な数の隣接体Ｎ（ｉ）を選択して合理的な程度のネットワーク接続性を確保する必要がある。６〜１０の隣接体を十分な数と考える。接続を行なうための適切な経路の探索領域は制限される。これを達成するための一の方法は、接続元ノードと接続先ノードとの間の最短経路近傍の或る距離範囲または幾つかのホップを探索することである。これには探索の前に最短経路を確立する必要があり、そして経路近傍のこれらのノードに、それらが探索領域に属することを認識させる。ここで、探索領域の他の選択も可能であることに留意されたい。探索領域に対する実用的な制約の一つに、接続元に向かって一層近接する隣接体を考慮に入れることが挙げられる。ノードが接続元に一層近接していると判断する一の方法は、ＣＦＰＲアルゴリズムを適用する前に普通の最短経路アルゴリズムを第１ステップとして実行することである。ＣＦＰＲアルゴリズムが送信電力をメトリックとして使用する場合、接続元からの累積経路損失のようなメトリックを使用してみる価値がある。前に示したように、多くの項目が０または∞のような値を採る場合には、上の計算から多くの項目を除外することができる。

実用的なルートの生成
経験的なアルゴリズムにより生成されるルートの全てが実用的であると見なされる必要は無い。例えば、高負荷状態でのチャネル不足に陥ると、広い領域に亘るジグザグラインを通る経路が生成されてしまう。これが大きな問題と考えられる場合、これを部分的に処理する少なくとも３つのアルゴリズムが在る。第１として、負荷制御を有効に使用することにより、チャネル不足の生じる確率を減らす。これを行なうと今度は、同じメトリックをＣＦＰＲアルゴリズムの場合のように使用すると仮定すると、最短経路に一層近接するルートが生成される。第２の方法は、上の「複雑さ」の章で記載したルート探索の範囲を制限することである。これを実現する一つの方法は、接続元に向かう方向に、より小さいＢｅｌｌｍａｎ−Ｆｏｒｄコストを有する隣接体を使用することである。

ＣＩＲ制限ベースの最大許容送信電力
送信電力を既存リンクの全ての受信機部分の受信電力よりもマージンγだけ小さい電力に制限するのではなく、替わりの条件として、既存リンクの全ての受信機部分のＣＩＲがＣＩＲしきい値Γ_Ｍ以上になるように送信電力を制限する。最大許容送信電力は次式で与えられる。

ここで、既存リンクまたは予備経路の各受信機部分が受ける干渉の大きさは干渉レベルＩ（ｍ）であり、そしてＩ＾_ｘ（ｍ）は予備経路に沿ったノードからのノードｘにおける干渉予測値である。これは受信ＣＩＲレベルの下限を規定する。結果として、トラフィックが既存リンクのＣＩＲレベルがＣＩＲしきい値Γ_Ｍを下回るように作用するのではなく、拒否されることになる。

ＣＩＲバランシング
送信電力レベルが最適化の操作期間中に決定されると、実際には実際のＣＩＲレベルがいずれにしても所望のＣＩＲレベルから外れてしまう、という現象が生じ得る。この現象は、ネットワークの送信電力レベルに対する従来のＣＩＲバランシングを自律分散または集中制御の形で行なうことにより補償することができる。換言すれば、一旦新規の接続が設定されると、送信電力レベルをバランスさせてネットワークにおいて所望のＣＩＲレベル（または他のＱｏＳ指標）が得られるようにする。

別の構成として、特にＣＩＲバランス均等化が集中制御の形で行なわれる場合に、ＣＩＲバランス均等化を接続認証制御（ＣＡＣ）局面の特別ステップとして使用する。ＣＩＲバランス均等化に失敗した場合、接続は拒否される。この場合に図１３のＣＩＲ ＣＤＦが階段関数となることに留意されたい。この特殊な手法の利点は全体としての性能が改善されることである。

アルゴリズムのより広い地平線への拡張
ＣＦＰＲの基本動作によってチャネルが今後さらに不適切となると判断されることがあり得るので、基本的なＣＦＰＲアルゴリズムの拡張についてここに記載する。一例として、チャネル１＋２，１＋２，１をそれぞれノードｋ，ｊ及びｉが使用でき、ｋ及びｉが隣接体ではなく、ｊがｋ及びｉの両方の隣接体であると仮定する。ノードｊが、チャネル１がチャネル２よりも低いコストを有するのでノードｋからのチャネル１を使用するように選択すると、ノードｊ及びｉがリンクを生成できないことになる。明らかに、ｊからｉに向かうチャネル１を使用するのではなくｋとｊとの間のチャネル２を割り当てるのがより賢明である。

ここでこれを処理する方法は、ｊからｉに向かうリンクの生成が可能でなければならないという制約の下で、ノードｉにｋからｊに向かうリンクのプロパティ（例えば、チャネル及びリンクパラメータ）を決定させることである。従って、ノードｉは２つのリンクに対する最小コストの組合せを同時に探索する。しかしながら、２つの同レベルのリンクが求まったとしても、接続元に最も近接するリンクのみが維持される。後続のステップでは、別のノードが最も有望なリンク組合せを探索する際にノードｊとｉとの間のリンクを使用するように判断するが、ｉからそのノード自体に向かうリンクは廃棄する。接続元ノードから最も遠く離れたリンクを無視するこのルールが適用される例外は接続先ステーションであり、このステーションは２つの最後のリンクを決定するが２つのリンクのいずれも廃棄しない。

基本のＣＦＰＲアルゴリズムでは、一度に一つのリンクを考慮に入れるだけである。ＣＦＰＲアルゴリズムのこのバージョンでは、一度に２つの連続するリンクを考慮に入れる。ここで、どこまで遠くこのアルゴリズムが動作するかを示すために地平線（ｈｏｒｉｚｏｎ）のコンセプトを導入する。基本ＣＦＰＲがｈｏｒｉｚｏｎ＝１を有するのに対して、この章のＣＦＰＲバージョンはｈｏｒｉｚｏｎ＝２を有する。地平線はどのような大きな値にも拡大することができるが、多くのノード及びチャネルを含む場合には複雑さが途方もなく大きくなる可能性がある。

高データレートのサポート
異なるアプリケーションはデータレートに関して異なる要求を有するので、異なるデータレートに対して一定のサポートを提供することは重要である。エンドツーエンドのスループットを変えるために２つの方法を利用する。第１の方法では、マージンγ_Ｒをγ_Ｍ及びγ_Ｗと一緒に選択して符号化率及び信号群からなるリンクモードをサポートする。簡易化した、異なるレートは、異なるＣＩＲ要求を指定する（或るデータレートに対応するＣＩＲをリクエストする）ことにより処理することができる。通常、信号群は２−ＢＰＳＫから６４−ＱＡＭに変わる。これも、Ｐ_ｍｉｎ及びＰ_ｍａｘに対応する送信電力の調整設定段階で考慮に入れることが好ましい。第２の方法では、マルチパスを確立し、そしてこれらを同時に使用して所望のデータレートを提供する。これらの２つの方法を組み合わせた形でも使用できる。

アプリケーションレイヤの統合
前に述べたように、最適化には他のプロトコルレイヤだけでなく３つを超えるプロトコルレイヤを使用することができる。例えば、アプリケーションレイヤを最適化に使用することができ、この場合３つの最低位プロトコルレイヤと組み合わせることが好ましい。例えば、アプリケーションレイヤはアダプティブアプリケーションを取り入れることができ、これにより、使用するデータレートに関連し、適合するアプリケーション品質でもって、異なるデータレートで動作することができる。多くの映像及び音声ベースのアプリケーションは、マルチデータレートを可能にするアダプティブアプリケーションの良好な例である。特に、新規の接続の設定を試みる場合、目的関数（またはアルゴリズム）の最適化をマルチデータレート要求（アプリケーションレイヤが必要とする）に関して行なう。前に示したように、種々のデータレートは、例えばノード間のマルチチャネル（例えばマルチタイムスロット）の組合せを使用し、リンク適応操作（信号群及び転送エラー符号化率の種々の組合せ）を行なうことによって、または両方を組合せることによりサポートすることができる。前記４つのレイヤ機能を統合する形で最適化する操作において、許容レート範囲の実現可能性は所定の制約の下に評価される。本発明の例示としての実施形態では、各最適化ステップで、所望であるが実現不可能なデータレートを後続の最適化ステップから外す。

アプリケーションレイヤは別の構成として、３つの最低位のプロトコルレイヤ内の２つのレイヤのみと一緒に統合最適化に使用することができる。

アルゴリズムのアダプティブアンテナ及びＭＩＭＯへの拡張
アルゴリズムを拡張してアダプティブアンテナ及びＭＩＭＯ通信の両方を取り込むことができる。アダプティブアンテナの場合、受信アンテナ及び送信アンテナのアンテナ重量のような物理レイヤパラメータを、送信電力を最小化するという条件の下で選択する。この選択は、進行中のトラフィックを妨害せず、そして所望の受信機が十分なレベルの品質（信号対干渉及びノイズ比）を有することを保証する、という制約を受ける。

十分に多くのアンテナ（アダプティブアンテナアレイの）を展開し、そして高い指向性を実現できる場合、干渉はネットワークの制限要素ではなくなる。それに代わって、ネットワークが対応できる負荷を制限することになるのはチャネルリソースである。極端な場合、すなわち干渉を完全に無視できる場合、別の最適化基準を採用してホップ数の最小化を試みる。各ノードでの空きリソースをバランスさせるという制約も加えて各時点における空き経路を検出できる確率を高くする。

ＭＩＭＯは、送信機ＭＩＭＯ重量及び受信機ＭＩＭＯ重量を含むリンクパラメータを選択することにより同様な態様で可能になる。パラメータ選択はリンク送信電力を最小化するとともに所望のＭＩＭＯリンクスループットも満たす、という制約を受ける。

実施局面
一般的に、最適化アルゴリズムは該当する接続認証制御（Ｃｏｎｎｅｃｔｉｏｎ Ａｄｍｉｓｓｉｏｎ Ｃｏｎｔｒｏｌ：ＣＡＣ）手順と共に、例えばマイクロプロセッサ技術、デジタル信号処理またはＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）技術を使用してハードウェア、ソフトウェア、ファームウェアまたはこれらのあらゆる組合せとして実施する。例えば、アルゴリズムはコンピュータシステムが実行するソフトウェアとして実施することができる。ソフトウェアは、Ｃ，Ｃ＋＋，Ｊａｖａ(登録商標)または特殊な固有言語をも含むようなほとんどどのタイプのコンピュータ言語でも記述することができる。実際、ソフトウェアベースの実施形態では、アルゴリズムをソフトウェアプログラムにマッピングし、このソフトウェアプログラムはコンピュータシステムが実行する際には接続を決定し、そして認証制御を処理する。しかしながら好適には、ＣＦＰＲアルゴリズム及び該当するＣＡＣ手順を、ＡＳＩＣまたは他のサブミクロン回路技術を使用して、程度の差はあるにしてもハードウェアで実施する。

図１４は、本発明によるＣＦＰＲアルゴリズムを実施するネットワークノードの模式図である。本発明に関連するこれらのネットワークノードコンポーネントのみを図１４に示す。ネットワークノード１００は制御システム１１０、及びベースバンド処理モジュール１２１だけでなく無線周波数（ＲＦ）モジュール１２２を有する一般的な無線送信／受信ユニット１２０を備える。制御システム１１０は、接続認証制御（ＣＡＣ）ユニット１１２及びルーティングユニット１１４だけでなく、ネットワーク情報を保存するデータベース１１６を備えることが好ましい。ルーティングユニット１１４はトラフィックをルーティングテーブル１１５を使用してルーティングする機能を含む。この特定の実施形態では、ＣＦＰＲユニット１１３をＣＡＣユニット１１２に設けて可能ならば一連の接続パラメータを求める。ＣＦＰＲユニット１１３は既存の接続に関する関連情報だけでなく、予備接続固有のリンクチェーンをデータベース１１６から、及び／又はノード間制御シグナリングから直接取り出し、そして適切な目的関数を有するＣＦＰＲアルゴリズムを実行する。ＣＡＣユニット１１２は、ＣＡＣ判定をＣＦＰＲアルゴリズムの実行結果に基づいて行なうように構成される。実現可能な一連の接続パラメータがＣＦＰＲユニット１１３によって所定のＱｏＳ要求の観点から求まらない場合、ＣＡＣユニット１１２は接続設定リクエストを拒否する。他方、ＣＦＰＲアルゴリズムが一連の実現可能な接続パラメータを生成する場合、リクエストされた接続が確立される。この動作は普通、ルーティングユニット１１６のルーティングテーブル１１５を新規の接続パラメータで更新し、そして接続パラメータを関連するネットワークノードに「フラッディング」、スパニングツリー転送、ソースルーティングまたは他の従来のメカニズムのいずれかを使用して転送することにより行なわれる。これは主として集中制御型の実施形態について記載したものである。しかしながら以下の記載においては、自律分散型実施形態に関する実施可能な形態について議論する。

ＣＦＰＲのオンデマンド実行
ＣＦＰＲは自律分散型で実施することができる。これは、前に述べたようにオンデマンドルーティングのコンセプトを利用することにより行なうことができる。オンデマンドルーティングは最先端の方式の幾つかに触れることにより知ることができるが、従来のオンデマンドルーティング手法には幾つかの修正がなされる。

第１の点は、ネットワークの各（Ｒｅｓｏｕｒｃｅ Ｒｅｑｕｅｓｔ）ＲＲＥＱによって単に予備ルートに沿ったノードのリストが生成されるだけではなく、リソース割当てに関する特定の詳細も生成されることである。例えば、予備接続の各受信スロットは受信電力レベルに関連付けることができる。ＣＩＲ制限ベースの最大許容送信電力が使用される場合には、ノイズ及び干渉レベルを含ませることもできる。

この情報を送信する理由は、スロット及び送信電力割当てが予備接続に沿って割り当てられるリソースに対する障害とならないことを保証するためである。従って、予備接続におけるリソースの送信電力レベルもＲＲＥＱによって配信される。これは、ノードｉが、予備接続に沿ったどのノードがノードｉの受信動作中に干渉するかを判断する機能を有する必要があるからである。

予備接続（ノードＩＤ）、及び使用チャネル、使用する可能性のある送信電力、受信する可能性のある受信電力（及び受信する可能性のある干渉）のような関連情報のリストは或る固定長に制限することができる。次に、リストが一杯になるとリストは先入れ先出し（ＦＩＦＯ）法で動作する。これは、無駄な情報を送信することでリソースを無駄にしたくないという思考が働くからである。明らかなことであるが、予備リストのノードは、そのノードがノードｉから十分に離れていて、ノードｉから、または干渉ノードｉからの干渉によって悪影響を受けることがない場合に重要度の低いノードになる。

単なるホップメトリックではないコストメトリックのフィールドもＲＲＥＱによって搬送される。前に議論した一の特定のメトリックは送信電力を基本にしていて、ルートに沿った累積送信電力レベルを示唆していた。

接続先ノードがＲＲＥＱを受信すると、ノードはＣＦＰＲアルゴリズムを分散制御型の態様に従って実行することにより最小コスト経路を選択し、そしてＲＲＥＰで応答するが、この応答は選択経路に沿って中継されて接続元ノードに戻される。ＲＲＥＰは、隣接ノードがＲＲＥＰ情報を受信できるように広いエリアに渡って基本的に衝突の無いチャネルを通して十分に大きい電力で送信されることが好ましい。ＲＲＥＰ情報を受信するこれらのノードは続いて、そのリソース割当てデータベースを更新する。ＲＲＥＱ及びＲＲＥＰに対応するプロトコルの詳細は先行技術から知ることができるのでこれ以上議論しない。

ＲＲＥＱ及びＲＲＥＰのような各制御メッセージは使用送信電力を取り込むこともでき、これにより受信ノードが経路損失を求めることができる。これは、チャネルが程度の差はあれ、平均経路利得との関係において相互に関係する場合に、実現可能になる。相互に関係しない場合、経路利得を推定する他の公知の方法を利用することができる。

複雑さを減らす上述の方式をオンデマンドルート決定と連携させて使用することができる。

最後に、ＲＲＥＱは帯域要求に応じて、所望のマージンγ_Ｒをγ_Ｍ及びγ_Ｗと一緒に通知する、または所望のリンクモードを通知する、或いは両方を通知することができる。同様に、ＲＲＥＰは送信電力、受信電力、所望マージン、関連タイムスロット（チャネル）などのような関連する接続パラメータを明示する。

オンデマンド動作の複雑さの緩和
複数の予備経路を含む完全なツリー構造を構築する操作は、最後には単に一つだけの経路を使用することになるので不必要な処理を生じてしまう。この章では、冗長経路に関する不必要な処理を減らすのに適した別のバージョンのオンデマンド動作を提案する。

接続元ノードが接続先ノードをどこに検出することができるかについての大まかなアイデアを有すると仮定する。これは、例えば基本的にゆっくりとした速度で更新されて、アプリオリ（理論的）に認識される（すなわち固定ノード）またはオンデマンドで認識されるＤＳＤＶのような革新的な最短経路プロトコルによって実現することができる。これによって、ＲＲＥＱを接続先に最短経路または最短経路に続く領域に沿って送信することができる。これを行なうに当たって、ＲＲＥＱには最短経路に沿った既存の接続に関するリンク情報が収集されている。この情報はＣＦＰＲアルゴリズムが必要とする同じ情報を含み、この情報によって使用チャネル、使用送信電力、受信する受信電力などの接続を後で計算する。接続先ノードがＲＲＥＱを受信すると、そのノードはＲＲＥＱによって収集される情報をＣＦＰＲアルゴリズム及びその派生物を通して処理する。ここで、ＲＲＥＱは単一の接続がサポートすることができない帯域を要求するリクエストを含むことができることに注目されたい。このような場合、接続先ノードは一のフローに対して複数の接続を決定することができる。続いて、一の（それより多くの）ＲＲＥＰを返送してリソースを予約する。このようにしてＲＲＥＰはノードＩＤ、使用予定のチャネル及びリンクパラメータ（例えば送信電力）を含むことができる。

この手法の利点は、計算が接続先ノードにおいてのみ行なわれ、ＲＲＥＱのフラッディングが制限されることである。ＲＲＥＱの転送中には計算が行なわれないので、ＲＲＥＱはネットワークを高速に送信される。別の利点は、接続先ノードがループの自由度を保証し、ＣＦＰＲアルゴリズムを前方及び後方の両方に走らせ（コスト方向性に関連して示したように）、そして任意の（ベンダー固有の）アルゴリズムを実行することができることである。

不利な点は、ＲＲＥＱに含まれる情報が非常に長いルートに対して非常に大きくなることである。この問題を解決する方法の一つとして、接続元と接続先との間の中間終了ポイント、例えば２０番目のノードなどを取り入れることである。

勿論、前に記載したツリーベースの手法をノードの小さな集合を含む小さな領域に使用することもできる。

アルゴリズムの非スロット化チャネルアクセスへの拡張
ＣＦＰＲアルゴリズムを拡張して、等サイズチャネルの媒体を予測可能なチャネル境界により分割する操作に依存しないチャネルアクセス技術を取り込むことができる。このようなチャネルアクセス方式の例として、８０２．１１ ＤＣＦプロトコルが挙げられる。ＤＣＦの現在の動作では、将来時点でリソースを繰返し割り当てることができないことに留意されたい。

この場合、コストｋ_ｉｊは遅延を、恐らくは送信電力と組み合わせた形で含む。各ノードは進行中の送信の間に、または後に所定サイズのパケットの送信ウィンドウを検出しようとする。リンクレートは、データパケット送信の圧縮処理が予定通りに行なわれるように適応させることができる。可能であれば必ず最大リンクレートを使用すると仮定すると、受信が干渉とノイズとを合わせた値よりも係数γだけ大きくなることを保証しつつ送信電力を適応させる（最小化させる）ことができる。図１５は、どのようにして種々のリンクレートが異なるリンクで使用されるかを示している。この図によれば、パケット送信が異なる期間に、いわゆる送信期間遅延によって行なわれることになる。効率的なことに、ルート、媒体アクセス遅延及びリンクレイヤパラメータ（リンクレート及び／又は送信電力のような）が、既存の接続だけでなく予備接続固有のリンクチェーンに対して実質的に干渉の無い通信が確保されるように設定される。

各ノードの送信時間遅延及びリンクレート（伝送遅延に影響する）を正しく選択することにより、接続元から接続先に至る全体のエンドツーエンド伝送遅延を最小化することができる。一旦、最高速リンクモードを使用すると、リンクモードに関するＣＩＲ要求を満たしつつリンク送信電力を最大限に小さくできる。これは実際に、遅延及び送信電力の両方を目的関数に、好適には重み付けした形で組み入れることができることを意味する。ネットワークにおいて遅延（または送信電力）を最小化することがより重要である場合には、該当する重み付け係数を単純に大きくする。

上述の実施形態は単に例として示すものであり、本発明はこれらの実施形態に限定されるものではないことを理解されたい。さらに、本明細書において開示し、主張するところの基本的な重要原理を含む変形、変更及び改良は本発明の技術範囲及び技術思想に含まれる。

参考文献
[1] S. Lee and A. T. Campbell, "INSIGNIA: In-band signaling support for QoS in mobile ad hoc networks", in Proc. Of the 5^th Intl. Workshop on
Mobile Multimedia Communication, 1999.
[2] C. Perkins, E. M. Royer and S. R. Das, "Ad hoc on-demand distance vector routing", in Internet-Draft, draft-ietf-manet-aodv-06.txt, July 2000.
[3] D. Johnson and D. Maltz, "Dynamic source routing in ad hoc wireless
networks", in Mobile Computing, Kluwer Academic Publ., 1996.
[4] S. Chen and K. Nahrstedt, "Distributed Quality-of-Service in ad hoc
networks", IEEE JSAC, SAC-17(8), 1999.
[5] C. R. Lin, "Multimedia transport in multihop wireless networsks", in
IEEE Proc.-Commun., vol. 145, No. 5, October 1998.
[6] R. Nelson and L. Kleinrock, "Spatial TDMA: A collision free multihop
channel access protocol," IEEE Trans. Commun., vol.COM-33, no.9,
pp.934--944, Sept. 1985.
[7] Lichun Bao and J.J. Garcia-Luna-Aceves, "Collision-Free Topology-Dependent
Channel Access Scheduling",
[8] Gronkvist, J., "Traffic Controlled Spatial TDMA in multihop radio networks", PIMRC 98, October 1998.
[9] Gronkvist, J., "Assignment Methods for Spatial Reuse TDMA" MobiCom OO,
Boston, MA, August 2000.
[10] Y.-C. Hsu and T.-C. Tsai, "Bandwidth Routing in Multihop Packet Radio
Environment", in Proceedings of the 3rdInternational Mobile Computing
Workshop, March 1997.
[11] Y.-C. Hsu, T.-C. Tsai and Y.-D. Lin, "QoS Routing in Multihop Packet Radio
Environment", in IEEE International Symposium on Computer Communications,
Athens, Greece, June 1998.
[12] C.-R. Lin and J.-S. Liu, "QoS Rounting in Ad hoc Wireless Networks",
in IEEE JSAC, SAC-17(8), 1999.
[13] C.-R. Lin. "On-Demand QoS Routing in Multihop Mobile Networks,". In
Proc. of IEEE INFOCOM, 2001.
[14] T.-W. Chen, J.-T. Tsai and M. Gerla, "QoS Routing Performance in Multihop,
Multimedia, Wireless Networks", in Proc. of IEEE ICUPC, 1997.
[15] Y.-S. Chen et al., "On-Demand, Link-State, Multi-Path QoS Routing in a
Wireless Mobile Ad-Hoc Network", To appear at IEEE European Wireless 2002:
February 26-28, Florence, Italy (previously available at the Internet).
[16] W.-H Liao, et al., "A Multi-Path QoS Routing Protocol in a Wireless Mobile
Ad Hoc Network", EEE Int’l Conf. On Networking (ICN), Vol. 2, pp. 158-167,
2001.
[17] W.-H Liao, Y.-C. Tseng and K.-P. Shih, "A TDMA Based Bandwidth Reservation
Protocol for QoS Routing in a Wireless Mobile Ad Hoc Network", to appear
in ICC, 2002 (previously available at the Internet).
[18] A. Michail, "Routing and Scheduling Algorithms in Resource-limited
Wireless Multi-hop Networks", PhD thesis, University of Maryland, College
Park, 2000.
[19] C. Zhu, "Medium Access Control and Quality-of-Service Routing for Mobile
Ad Hoc Networks", PhD thesis, University of Maryland, College Park, 2001.
[20] M. Sandchez, J. Zander, "Reuse Adaptive Routing for Multihop Packet Radio
Networks", distributed through the Industrial Partnership Program hosted
by the Radio Communication Systems group of KTH Royal Institute of Technology,
Stockholm.
[21] International Patent Application with International Publication No.WO 02/05493
A2, January 17, 2002.
[22] International Patent Application with International Publication No.WO
01/50669 A1, July 12, 2001.
[23] U.S. Patent Application Publication No. US 2002/0049561 A1, April 25,
2002.
[24] U.S. Patent Application Publication No. US 2002/0054578 A1, May 9, 2002.
[25] U.S. Patent Application Publication No. US 2002/0075869 A1, June 20, 2002.

先行技術によるルーティング及びチャネルアクセス方法を示す模式図である。 本発明による統一手法を示す模式図である。 例示としての無線マルチホップネットワークの模式図である。 接続設定、接続拒否、及び接続切断のフローチャートある。 例示としての無線マルチホップネットワークにおける予備接続経路設定に使用する表記を示す。 特定ノードペア及びチャネルに対応する例示としての無線マルチホップネットワークにおける予備接続経路設定を示す。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 所定のネットワークにおいてＱｏＳを提供するための本発明の統一メカニズムの動作例を示す模式図である。 図１２の例に対応する全ての通信状態の受信機に対応する、結果として得られるＣＩＲ ＣＤＦのグラフを示す模式図である。 本発明によるＣＦＰＲアルゴリズムが実行されるネットワークノードの模式図である。 スロット化されていないチャネルを予約する例を示す模式図である。

Claims (34)

1. 通信ネットワークにおける接続設定方法であって、
   リクエストされる接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータを前記接続パラメータの全てに関する単一の目的関数の統合最適化によって求める工程と、そして
   前記リクエストされる接続を前記求めた一連の接続パラメータに基づいて確立する工程と、
   を備える方法。
2. 前記通信ネットワークは無線マルチホップネットワークである請求項１記載の方法。
3. 前記最適化は少なくとも一つの制約に従い、この制約は前記リクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成される請求項１記載の方法。
4. 前記接続パラメータは少なくとも一つの干渉関連の制約の下に同時に求められ、この制約は、リクエストされる接続のリンクを含む干渉の無いリンクを実質的に保証するように構成される請求項３記載の方法。
5. 前記少なくとも一つの物理リンクパラメータは次のグループから選択される請求項１記載の方法。
   ・送信電力
   ・アダプティブアンテナ（Ａｄａｐｔｉｖｅ Ａｎｔｅｎｎａ：ＡＡ）パラメータ
   ・多入力−多出力（Ｍｕｌｔｉｐｌｅ−Ｉｎｐｕｔ−Ｍｕｌｔｉｐｌｅ−Ｏｕｔｐｕｔ：ＭＩＭＯ）パラメータ
   ・変調パラメータ
   ・帯域幅
   ・データレート
   ・誤り訂正パラメータ
6. 前記統合最適化は発見的アルゴリズムにより行なわれる請求項１記載の方法。
7. 前記アルゴリズムがどこまで遠く動作するかを示す地平線（ｈｏｒｉｚｏｎ）は、演算の複雑さの所定の許容レベルに対応する最適な性能を実現できるように選択可能である請求項６記載の方法。
8. 前記統合最適化はネスト化アルゴリズムを使用して行なわれ、このネスト化アルゴリズムは、それぞれ経路割当て、チャネル割当て、及び物理リンクパラメータ適応を表わすネスティングレベルを有する請求項１記載の方法。
9. 前記最適化は前記接続パラメータの全てに関する目的コスト関数の最小化を含む請求項１記載の方法。
10. 前記最適化は、接続元ノードから所定の集合の各ノードｉに至る最小コストＫ_ｉを求める探索手順を含み、この探索手順は次の最適化アルゴリズムに従う請求項１記載の方法。
    

    

    ここで、ｉ≠Ｓｏｕｒｃｅ（接続元） ＩＤ，Ｎ（ｉ）はノードｉの現在の隣接体の集合であり、この集合が今度はネットワークの全ノードΩの集合となり、ｊはＮ（ｉ）に属する隣接ノード、ｍは合計でＭ個の直交チャネルの集合の中の少なくとも一つのチャネルの集合、ψは一の、または多数の物理レイヤパラメータ、ｋ_ｉｊ（ｍ，ψ）とも記載するｋ_ｉ（ｊ，ｍ，ψ）はノードｊからノードｉに至るコスト、そしてＫ_ｊとも記載する項Ｋ（ｊ）は接続元ノードからノードｊに至るまでの累積コストであり、Ｋ_{Ｓｏｕｒｃｅ ＩＤ}は接続元ノードでの初期コストである。
11. 自律探索手順を各ノードｉで実行して、前記隣接体集合Ｎ（ｉ）の全ノードｊに関してノードｊからノードｉに至るコストｋ_ｉｊ（ｍ，ψ）を見積もり、そして接続元ノードから各ノードｉに至る最小コストＫ_ｊを、前記見積もりに各ノードｊから受信するＫ_ｊに関する情報を併せたものに基づいて求める請求項１０記載の方法。
12. 前記コストｋ_ｉｊ（ｍ，ψ）はチャネルに依存する物理リンクパラメータψ（ｍ）を含む請求項１０記載の方法。
13. 前記コストｋ_ｉｊ（ｍ，ψ）はノードｊに対応するリンク送信電力Ｐ_ｊ（ｍ）を含む請求項１０記載の方法。
14. 前記リンク送信電力Ｐ_ｊ（ｍ）はリンク送信電力を所定の範囲に制限する制約に従う請求項１３記載の方法。
15. ノードｊからの最大許容リンク送信電力及び最小限必要なリンク送信電力が次式で定義される請求項１４記載の方法。
    

    

    ここで、Ｐ＾_ｒ（ｍ）及びＣ＾_ｒ（ｍ）は、ノードｊに接続される予備経路に沿ったノードを示す集合Ｒ内のノードｒに対応するそれぞれ予備送信電力及び予備受信電力を示し、他方、Ｐ_ｖ（ｍ）及びＣ_ｕ（ｍ）は、確立されたトラフィックを有するノードに対応するそれぞれ送信電力及び受信電力を示し、γ_Ｍは緩和係数であり、Ｇ（ｍ）はそれぞれのチャネルゲインマトリクスであり、γ_Ｒは受信係数であり、そしてＷはノイズレベルであり、このノイズレベルは係数γ_Ｗを使用してノイズレベルがノイズに制限されるのではなく全体的に干渉に制限されることを保証する。
16. ノードｊからの最大許容リンク送信電力及び最小限必要なリンク送信電力が次式で定義される請求項１４記載の方法。
    

    

    ここで、Ｐ＾_ｒ（ｍ）及びＣ＾_ｒ（ｍ）は、ノードｊに接続される予備経路に沿ったノードを示す集合Ｒ内のノードｒに対応するそれぞれ推定（または予備）送信電力及び推定（または予備）受信電力を示し、他方、Ｐ_ｖ（ｍ）及びＣ_ｕ（ｍ）は、確立されたトラフィックを有するノードに対応するそれぞれ送信電力及び受信電力を示し、Ｇ（ｍ）はそれぞれのチャネルゲインマトリクスであり、Γ_ＭはＣＩＲ（搬送波干渉比：Ｃａｒｒｉｅｒ Ｉｎｔｅｒｆｅｒｅｎｃｅ Ｒａｔｉｏ）しきい値であり、このしきい値は既存リンクまたは予備経路の各受信機部分が干渉レベルＩ（ｍ）を受けると仮定し、Ｉ＾_ｘ（ｍ）は予備経路に沿ったノードからのノードｘでの予測される干渉であり、γ_Ｒは受信係数であり、そしてＷはノイズレベルであり、このノイズレベルは係数γ_Ｗを使用してノイズレベルがノイズに制限されるのではなく、全体として干渉に制限されることを保証する。
17. さらに、前記統合最適化の前に予備最短経路を求め、そしてノード隣接体Ｎ（ｉ）の前記探索領域を前記予備最短経路を認識することによって選択する工程を備える請求項１０記載の方法。
18. オンデマンドルーティングを展開して、リソースリクエスト（Ｒｅｓｏｕｒｃｅ ＲＥＱｕｅｓｔ：ＲＲＥＱ）によって、リクエストされる予備接続に対応する経路、チャネル及び物理リンクパラメータを搬送し、そしてルート応答（Ｒｏｕｔｅ ＲＥＰｌｙ：ＲＲＥＰ）によって該当する経路に沿った選択接続を確認する請求項１記載の方法。
19. オンデマンドルーティングを展開して、リソースリクエスト（Ｒｅｓｏｕｒｃｅ ＲＥＱｕｅｓｔ：ＲＲＥＱ）によって、前記ＲＲＥＱが前記ネットワークを通して転送されるときに既存の接続に関する情報を照合し、そして前記照合情報に基づいて前記ＲＲＥＱに含まれるサービス品質（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ：ＱｏＳ）を満たす新規接続を接続先ノードにて決定する請求項１記載の方法。
20. 通信ネットワークにおいて接続を決定する方法であって、
    前記接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータを、前記接続パラメータの全てに関する単一の目的関数の統合最適化を行なうことによって求める工程を備える、方法。
21. 前記最適化は少なくとも一つの制約に従い、この制約は前記リクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成される請求項２０記載の方法。
22. 通信ネットワークにおける接続認証制御方法であって、
    リクエストされる接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータに関する単一の目的関数の統合最適化を行なう工程であって、前記最適化は少なくとも一つの制約に従い、この制約は前記リクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成される工程と、
    一連の接続パラメータを求めるには必ず前記制約に違反しなければならない場合に前記リクエストされる接続を拒否する工程と、
    一連の接続パラメータを求めるために前記制約に違反する必要がない場合に前記リクエストされる接続を認証する工程と、を備える方法。
23. 前記少なくとも一つの制約は干渉関連の制約を含み、この制約は前記リクエストされる接続のリンクを含む実質的に干渉の無いリンクを保証するように構成される請求項２２記載の方法。
24. 通信ネットワークにおける接続を決定する方法であって、
    前記接続を、前記ネットワーク内の少なくとも３つのプロトコルレイヤの接続パラメータに関する単一の目的関数の最適化を行なうことによって決定する工程を備える方法。
25. 前記通信ネットワークは無線マルチホップネットワークを含み、そして前記接続パラメータは前記無線マルチホップネットワーク内の少なくとも３つのプロトコルレイヤのパラメータを含む、請求項２４記載の方法。
26. 前記少なくとも３つのプロトコルレイヤはネットワークレイヤ、リンクレイヤ及び物理レイヤを含む、請求項２４記載の方法。
27. 前記少なくとも３つのプロトコルレイヤはさらにアプリケーションレイヤを含む請求項２６記載の方法。
28. 前記最適化は少なくとも一つの制約に従い、この制約は前記リクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成される請求項２４記載の方法。
29. 前記接続は少なくとも一つの三つ組によって定義され、この三つ組は選択経路、チャネルのような選択直交伝送リソース、及び一つ以上の選択物理リンクパラメータを含む、請求項２４記載の方法。
30. 前記アルゴリズムは、各ネスティングレベルがネットワークプロトコルレイヤを表わすネスト化されたアルゴリズムである、請求項２４記載の方法。
31. 通信ネットワークにおいて接続を決定する制御システムであって、
    前記接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータを、前記接続パラメータの全てに関する単一の目的関数の統合最適化を行なうことによって求める手段を備える、制御システム。
32. 通信ネットワークにおける接続設定を行なう制御システムであって、
    リクエストされる接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータを、前記接続パラメータの全てに関する単一の目的関数の統合最適化を行なうことによって求める手段と、そして
    前記リクエストされる接続を求めた前記一連の接続パラメータに基づいて確立する手段と、を備える制御システム。
33. 通信ネットワークにおける接続認証制御を行なう制御システムであって、
    リクエストされる接続に対して、経路、チャネル及び少なくとも一つの物理リンクパラメータを含む一連の接続パラメータに関する単一の目的関数の統合最適化を行なう手段を備え、前記最適化は少なくとも一つの制約に従い、この制約は前記リクエストされる接続だけでなく既存の接続に対して実質的に衝突の無い通信を保証するように構成され、
    一連の接続パラメータを求めるには必ず前記制約に違反しなければならない場合に前記リクエストされる接続を拒否する手段と、
    一連の接続パラメータを求めるに前記制約に違反する必要がない場合に前記リクエストされる接続を認証する手段と、を備える制御システム。
34. 通信ネットワークにおける接続を決定する制御システムであって、
    前記接続を、前記ネットワーク内の少なくとも３つのプロトコルレイヤの接続パラメータに関する単一の目的関数の統合最適化を行なうことによって決定する手段を備える制御システム。

Images