(57)【要約】本発明は、通信ネットワーク中の送信機から受信機へのトラヒックのルーティングを行う方法に関わり、本方法は、送信機と受信機との間の少なくとも二つの可能なルートに対して、各ルート中の少なくとも一つのリンクにつき少なくとも一つのメトリック値を計算する工程を含み、少なくとも一つのメトリックに対するセンシティビティ・パラメータ値を計算し、ルートを選択するときに、センシティビティ・パラメータを考慮に入れる工程を含むことを特徴とする。センシティビティ・パラメータは、メトリックが依存する変数に対するメトリックの微分係数に基づくことができる。本方法は、少なくとも一つのメトリックに対する信頼性パラメータを計算し、この信頼性パラメータをルート選択時に考慮する工程をさらに含むことができる。
2008543163.tif 000002
【特許請求の範囲】
【請求項１】
送信機と受信機との間で、少なくとも二つの異なるルートを介してデータを送信でき、各ルートが少なくとも一つのリンクを有する通信ネットワーク内で使用される通信ノードであって、前記少なくとも一つのリンクに対して少なくとも一つのメトリックを計算するように構成されたリンク・マネジメント・ファンクション・ユニット（ＬＭＦ）を備える通信ノードにおいて、
前記リンク・マネジメント・ファンクション・ユニット（ＬＭＦ）が、前記少なくとも一つのメトリックに対するセンシティビティ・パラメータ値を計算するようにも構成され、
前記センシティビティ・パラメータ値が、前記ネットワーク中の所与の変化に対して前記メトリックがどのように変化するかを示すことを特徴とする通信ノード。
【請求項２】
前記リンク・マネジメント・ファンクション・ユニット（ＬＭＦ）が、前記メトリックが依存する変数に対する前記メトリックの微分係数に基づいて前記センシティビティ・パラメータ値を計算するように構成されていることを特徴とする請求項１に記載のノード。
【請求項３】
前記リンク・マネジメント・ファンクション・ユニット（ＬＭＦ）が、前記メトリックの信頼性パラメータ値を計算するように構成されていることを特徴とする請求項１または２に記載のノード。
【請求項４】
前記リンク・マネジメント・ファンクション・ユニットが、前記通信ネットワーク中の別のノードの少なくとも一つの他のリンク・マネジメント・ファンクション・ユニットに、前記メトリック、前記センシティビティ・パラメータ値、および、信頼性パラメータ値の少なくともいずれかを送信するように構成されていることを特徴とする請求項１乃至３のいずれか１項に記載のノード。
【請求項５】
前記リンク・マネジメント・ファンクション・ユニットが、前記通信ネットワーク中の別のノードの少なくとも一つの他のリンク・マネジメント・ファンクション・ユニットから、前記メトリック、前記センシティビティ・パラメータ値、及び、信頼性パラメータ値の少なくともいずれかを受信するように構成されていることを特徴とする請求項１乃至４のいずれか１項に記載のノード。
【請求項６】
前記メトリックと、少なくとも前記センシティビティ・パラメータ値および信頼性パラメータ値のいずれかとに基づいて、前記通信ネットワーク中のルートを選択する手段（ＬＭＦ）をさらに備えることを特徴とする請求項１乃至５のいずれか１項に記載のノード。
【請求項７】
通信ネットワーク内で送信機から受信機へのトラヒックをルーティングする方法であって、前記送信機と前記受信機との間の少なくとも二つの可能なルートについて、前記ネットワーク内の少なくとも第一リンクに対する少なくとも一つのメトリック値を計算する工程を含む方法において、
前記少なくとも一つのメトリックに対するセンシティビティ・パラメータ値を計算する工程であって、前記センシティビティ・パラメータ値が、前記ネットワーク中の所与の変化に対して前記メトリックがどのように変化するかを示すものである工程と、
ルートを選択する際に前記センシティビティ・パラメータを考慮する工程と
を含むことを特徴とする方法。
【請求項８】
前記前記センシティビティ・パラメータ値が、前記メトリックが依存する変数に対する前記メトリックの微分係数に基づくことを特徴とする請求項７に記載の方法。
【請求項９】
前記少なくとも一つのメトリックに対する信頼性パラメータ値を計算し、該信頼性パラメータ値をルート選択時に考慮する工程をさらに含む請求項７または８に記載の方法。
【請求項１０】
前記ネットワーク中の少なくとも第二リンクに関連したメトリックおよびセンシティビティ・パラメータ値を受信し、受信した前記メトリックおよびセンシティビティ・パラメータ値をルート選択時に考慮する工程を、さらに含むことを特徴とする請求項７乃至９いずれか１項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、請求項１のプリアンブルに記載されたトラヒックをルーティングする方法に関する。
【背景技術】
【０００２】
本発明は、多数の中間ネットワーク・ノードを介して送信機から受信機へデータが送信され得る通信ネットワークに適用される。データは、それぞれが一以上の中間ネットワーク・ノードを有する異なるルートを介して送信され得る。二つの隣接するノード間の直接パスは、リンクと呼ばれる。どの通信リンクが通信フローに使用されるかによって、送信機から受信機へのネットワークを通る送信ルート（またはパス）が区別される。
【０００３】
このような通信システムにおいては、リソースをできる限り有効に利用するために、ルート選択を最適化することが重要である。
【０００４】
現存するルーティング・ソリューションにおいては、典型的場合、ルート選択は、各通信ルートに対してコスト値すなわちメトリックを割り当てること、すなわちルート・メトリックに基づいて行われる。ルート・メトリックは、一般に、ルート中の全てのリンクすなわちホップに対するメトリック値の総和として求められる。典型的な場合（必ずしもこのようにする必要はないが）、各ノードは、それ自身のリンクに対するリンク・メトリック値を求め、それらの値は、ルーティング・プロトコルを使用して他のノードに配布される。典型的な場合、最良のルートは、最良ルート・メトリックを有するルートが選択される。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来のソリューションには、いくつかの問題がある。一つの問題は、ルートに割り当てられるメトリックが不確定ということである。メトリックは、推定エラーがあるリンク特性の推定に基づいて求められる。また、ルーティング決定を行うときメトリックが考慮される前に時間がかかる。これは、例えばリンク特性中のある変化は、推定プロセスにおいてそれらが求められる前に、終了しないという事実による。従って、これが関連メトリックに影響を与える。また、メトリックは、ルーティング決定にこのメトリックを使用するファンクションに配布されるのに時間がかかる。
【０００６】
上述した従来のソリューションは、ルート・メトリックが、例えばネットワーク中の負荷が変化するときに時間とともに変化する動的パラメータであるという事実を考慮していない。
【０００７】
本発明の目的は、ネットワークを通るルーティングを改良することにより、ネットワーク・リソースをより有効に使用できるようにすることにある。
【課題を解決するための手段】
【０００８】
本発明の目的は、送信機と受信機との間で、少なくとも二つの異なるルートを介してデータを送信でき、各ルートが少なくとも一つのリンクを有する通信ネットワーク内で使用される通信ノードであって、少なくとも一つのリンクに対して少なくとも一つのメトリックを計算するように構成されたリンク・マネジメント・ファンクション・ユニット（ＬＭＦ）を備え、リンク・マネジメント・ファンクション・ユニット（ＬＭＦ）が、少なくとも一つのメトリックに対するセンシティビティ・パラメータ値を計算するようにも構成され、センシティビティ・パラメータが、ネットワーク中の所与の変化に対してメトリックがどのように変化するかを示すことを特徴とする通信ノードによって達成される。
【０００９】
本発明の目的は、また、通信ネットワーク中の送信機から受信機へのトラヒックのルーティングを行う方法であって、送信機と受信機との間の少なくとも二つの可能なルートに対して、ネットワーク中の少なくとも第一リンクに対する少なくとも一つのメトリック値を計算する工程を含み、少なくとも一つのメトリックに対するセンシティビティ・パラメータ値を計算する工程であって、センシティビティ・パラメータ値が、ネットワーク中の所与の変化に対してメトリックがどのように変化するかを示すものである工程、およびルートを選択するときにセンシティビティ・パラメータを考慮に入れる工程を含むことを特徴とする方法によって達成される。
【００１０】
このように、本発明によるルーティング・メカニズムは、各ルートに対するメトリックに基づくとともに、例えばネットワーク中の負荷の変化のようなネットワーク中の変化に対するメトリックのセンシティビティに基づく。
【００１１】
本ルーティング・メカニズムは、また、メトリックに対する信頼性パラメータを計算し、ルーティング決定を行うときにこの信頼性パラメータを考慮することにより、メトリックの信頼性を考慮することができる。
【００１２】
本リンク・マネジメント・ファンクション・ユニットは、通信ネットワーク中の別のノードの少なくとも一つの他のリンク・マネジメント・ファンクション・ユニットに、メトリック、センシティビティパラメータ値および信頼性パラメータ値の少なくともいずれかを送信し、および／または、通信ネットワーク中の別のノードの少なくとも一つの他のリンク・マネジメント・ファンクション・ユニットから、メトリック、センシティビティパラメータ値および信頼性パラメータ値の少なくともいずれかを受信するように構成することが好ましい。
【００１３】
一つ以上のノードは、メトリックと、少なくともセンシティビティパラメータ値および信頼性パラメータ値のいずれかとに基づいて、通信ネットワーク中のルートを選択する手段を含む。
【００１４】
従来技術においては、典型的な場合、ルーティング決定は、そのルーティング決定の前のルートのメトリックに基づく。しかし、一旦、データがルートに送信されると、メトリックは一般に変化する。本発明によれば、このことは、ネットワーク中の変数に対するメトリックのセンシティビティを考慮することにより、好ましくはトラヒック負荷に関するメトリックの微分係数を考慮することにより、対処される。
【００１５】
本発明は、ルーティング決定を改良することにより、通信ネットワークの性能、サービス品質サポートおよび容量を改良する。
【００１６】
本発明は、あらゆるルーテッド通信ネットワークに適用可能であるが、特に、無線マルチホップネットワークおよびアドホック・ネットワークの少なくともいずれかに対して有効である。より具体的には、異なるリンク技術（例えば、異なる無線アクセス技術）が使用される異種マルチホップ・ネットワークに有効である。
【００１７】
頭字語
ＡＲＱ  ：Automatic Repeat Request（自動リピート要求）
ＢＬＥＲ：Block Error Rate（ブロック・エラー・レート）
ＬＭＦ  ：Link Management Function（リンク・マネジメント・ファンクション）
ＲＡＴ  ：Radio Access Technology（無線アクセス技術）
【発明を実施するための最良の形態】
【００１８】
本発明は、添付の図面を参照して、以下により詳細に説明される。
【００１９】
図１は、通信ネットワークを通る多数の可能なルートを介する送信機Ｓから受信機Ｒへのデータ送信を概略的に示す。ネットワークは、データが通る（ルートする）多数の中間ノードＩを含む。図１には、５つの異なるルート１，２，３，４，５が示されている。第一ノードから次のノードへのパスは、リンクまたはホップと呼ばれる。第一ノードは、例えば送信機Ｓまたは中間ノードＩである。次のノードは、例えば、別の中間ノードＩまたは受信機Ｒである。データをルーティングするとき、コストと呼ばれるメトリックは、伝統的に、ルート中の全リンクすなわちホップのコストの総和として求められる。
【００２０】
典型的な場合、最も低いコストのルートが選択される。少なくともいくつかのノードは、リンク・メトリック・ファンクション・ユニットＬＭＦを備え、このユニットは、そのノードから始まるリンクに対するリンク・メトリックを求めるのに必要なリンク特性を、制御、モニターする。各ノードに対するリンク・メトリックは、図１中で破線で示されているように、他のノードのリンク・メトリック・ファンクション・ユニットに伝えられる。あるノードは、他のノードに情報を与えるだけであり、あるノードは、他のノードから情報を受けるだけであり、あるノードは、両方を行う。ノードが、リンク・メトリック・ファンクション・ユニットを有していない場合、このノードのためのリンク・メトリックは、別のノードで求められる。リンク・メトリック・ファンクション・ユニットについては、以下で詳細に説明する。リンク・メトリックの例が、表１に示されている。
【００２１】
双方向トラヒックの場合、送信機は、同時に受信機でもあり得る。ルート・メトリックは、両方向でつり合っている必要はないが、典型的な場合、両方向で同じパスが選択される。送信機がある方向にルーティング決定を行うと、送信機はこの情報を受信機に配布する。受信機は、逆方向では、送信機である。この場合、受信機は、ルーティング決定に関与している。
【００２２】
ルーティング・アルゴリズム中で検討される各候補ルートｉに対して、一つまたはそれ以上のメトリックＭｉが考慮される。ルートのメトリックは、例えば、次のことに基づく。
・ルート中のホップ数
・ルート品質
・サポートされているレート
・遅延
・トラヒック負荷
・容量
・ビット・エラー・レートおよびブロック・エラー・レートの少なくともいずれか
【００２３】
このようなルート・メトリックは、ルートの各ホップに対して求められたリンク・メトリックの全てまたはいくつかから導出される。当業者は、どのようにルート・メトリックを求めるかをよく理解している。
【００２４】
ルーティング決定は、典型的な場合、そのルーティング決定の前のルートのメトリックに基づく。例えば、二つの可能なルートＡおよびＢは、非常に近似したルート・メトリックＭAおよびＭB（ここで、ＭA＜ＭB）を有しているものとする。この例では、メトリックの低い値がルートにとってより良い特性と仮定する。これらのメトリックに従って、ルーティング決定ファンクションは、データ・フローにルートＡを割り当てる。しかしながら、ルートＡ中のあるリンクが重い負荷を有していると、新たなフローがルートＡに割り当てられた後、ＭAがドラスチックに増加する。対照的に、ルートＢのリンクが軽い（低い）負荷を有していれば、新たなフローがこれに割り当てられても、ＭBはわずかに変化するだけである。このことは、以下に、詳述する。
【００２５】
本発明によれば、メトリックそれ自身に加えて、メトリックの信頼性ＲｉおよびセンシティビティＳiの少なくともいずれかを考慮する。
メトリックの信頼性は、なかんずく、次の側面に基づくことができる。
・メトリック推定の信頼性
・例えば、次のことに影響されるメトリックの変化レート
- ノードの速度
- 無線アクセス技術の種類
- 周波数帯域
- 過去のメトリックの変化レートの統計
・メトリックの推定頻度
・推定されたメトリックが配布される頻度
・メトリック値の信号遅延
【００２６】
上述の説明では、全てのルートが唯一のメトリックを有すると仮定した。しかしながら、ルートは、それに割り当てられた多くのメトリック、ならびにこれらのメトリックのいくつかを使用するルーティング・アルゴリズムを有している。本発明は、もちろん、多くのメトリックが使用されても適用でき、この場合、これらのメトリックの少なくとも一つに対して、センシティビティ値および信頼値の少なくともいずれかが考慮される。
【００２７】
メトリック・センシティビティは、メトリックが特定入力パラメータｐに依存してどのように変化するかを示す。入力パラメータは、例えば、トラヒック・レート（トラヒック負荷）の変化、サービス品質（ＱｏＳ）要求の変化、典型的パケット・サイズの変化、その他である。メトリック・センシティビティＳi（ｐ）は、従って、パラメータｐが変化したときにメトリックＭiがどのように変化するかを示す。Ｓi（ｐ）が複素関数である場合、メトリック・センシティビティを記述する簡略形が有用である。これは、例えば、複素関数のテイラー級数展開の特定数のエレメントを使用することにより、可能である。
【００２８】
メトリックのセンシティビティの一例が、図２に示されている。この図からわかるように、この例では、容量に対するメトリックが、パラメータ・トラヒック負荷とともに増加する。トラヒック負荷が小さいときには、メトリックは緩やかに増加し、Ｓiは低い。トラヒック負荷の異なる値において変化する負荷に対して容量の変化を示す直線により示されているように、トラヒック負荷が増加すると、メトリック曲線はより急勾配になる、すなわち容量のセンシティビティＳiが増加する。
【００２９】
信頼性およびセンシティビティは、ルートの異なるホップに対して変化する。ルート全体の信頼性およびセンシティビティは、信頼性およびセンシティビティを適当に組み合わせなければならない。
【００３０】
本発明によれば、実際のルーティング・アルゴリズムが、決定メトリックに基づいてルーティング決定を行う。この決定メトリックは、ルーティング・メトリックＭと、メトリック信頼性Ｒおよびメトリック・センシティビティＳの少なくともいずれかとの組み合わせである。図１を再び参照すると、このことは、ネットワークを通る各可能ルートに対するメトリックＭiに加えて、信頼性パラメータＲiおよびセンシティビティ・パラメータＳiの少なくともいずれかが、各ルートｉに対して求められることを意味する。
【００３１】
決定メトリックを求める種々のソリューションが可能である。例えば、
・ルートをフィルタリングする：Ｒが特定の閾値を超える全てのルートを可能なルートのセットから除外する。
・メトリックをスケーリングする：ルート・メトリックを、対応するメトリック信頼性Ｒおよびメトリック・センシティビティＳの少なくともいずれかによってスケーリングできる。同様に、リンク・メトリックは、それらがルート・メトリックに入れられる前に、それらの信頼性またはセンシティビティによってスケーリングできる。
・予測メトリック：入力パラメータの予期された変化に基づく。予測メトリックＰＭは、実際に求められたメトリックＭおよびパラメータｐに対するメトリック・センシティビティに依存して推定される。
【００３２】
表１は、リンク・メトリックを示し、この表には、多くのリンク・メトリックが説明されている。
[表１]
2008543163.tif 000003
2008543163.tif 000004
2008543163.tif 000005
【００３３】
次に、リンク・メトリックからどのようにしてルート・メトリックを求めるのか説明する。説明には、次の記号を使用する。
・Ｍi,j,k：リンク・メトリック、ここで、
‐ｉは、ルート番号を示す
‐ｊは、ホップ番号を示す
‐ｋは、メトリックのタイプを示す
・Ｓi,j,k:メトリック・センシティビティ、ｉ，ｊおよびｋは上記と同じ
・Ｒi,j,k：メトリック信頼性、ｉ，ｊおよびｋは上記と同じ
【００３４】
マルチホップ・ネットワーク中の、各ノードまたは少なくともいくつかのノードには、リンク・マネジメント・ファンクションＬＭＦが配置されているものと仮定する。ＬＭＦは、リンク・メトリックを求めるのに必要なリンク特性を制御、モニターする。ＬＭＦiは、ホップ番号ｉの前に配置されているＬＭＦである。ルート中にｎ個のホップがあれば、ｎ+１個までのＬＭＦが存在する。
【００３５】
異なるＬＭＦは、リンク・メトリックを制御し／測定するための情報、例えば（マルチ）無線リソース・マネジメント情報を交換する。各ノードにＬＭＦが無ければ、別のノードのＬＭＦが、いくつかのホップのメトリックを推定することができる。メトリック推定が不正確な場合、これは、メトリックの低い信頼性に反映される。
【００３６】
一つのルートの各ホップに、リンク・メトリックＭi,j,kリンク・メトリック・センシティビティＳi,j,kおよびリンク・メトリック信頼性Ｒi,j,kが存在するものとする。これらの値は、ノードのＬＭＦユニットに記憶されるか、そのノードにＬＭＦユニットが無い場合には、別のノードのＬＭＦユニットに記憶される。ノードがデータを受信機に送信しようとするとき、そのＬＭＦユニットは、異なる可能なルートに対する、ルート・メトリックと、少なくともルート・メトリック・センシティビティおよびルート・メトリック信頼性のいずれかとを計算する。ルート・メトリック、ルート・メトリック・センシティビティおよびルート・メトリック信頼性を求めるには、次の工程が必要である。
‐ 各ルートに対して、パラメータｋに係る上記ルートに属する全てのリンク・メトリックが関数（Ｆ）により組み合わされてルート・メトリック Ｍ〜j,k＝Ｆ（Ｍi,j,k；Ｓi,j,k（ｐ）；Ｒi,j,k）が求められる。ここで、該ルートに沿う全てのホップｉに対するリンク・メトリックが考慮され、また、多数の異なるパラメータｐに関するセンシティビティが考慮され得る。
- 同様に、全てのリンク・メトリック・センシティビティＳi,j,k（ｐ）が組み合わされてルート・メトリック・センシティビティＳ〜i,j,k（ｐ）＝Ｆ（Ｓi,j,k（ｐ）；Ｒi,j,k）が求められ、全てのリンク・メトリック信頼性Ｒi,j,kが組み合わされてルート・メトリック信頼性 Ｒ〜j,k＝Ｆ（Ｒi,j,k）
が求められる。
【００３７】
そして、最も適したルートを選択するために、関連ノードのＬＭＦユニット中で、ルーティング決定が行われる。この決定では、異なるメトリック・タイプの Ｍ〜j,k,Ｓ〜j,k（ｐ），Ｒ〜j,kが組み合わされ、異なる入力パラメータｐに対するセンシティビティが考慮される。
【００３８】
有効ルートの予備的選択は、次のように行われる。
- 第一の工程において、あるメトリック・タイプｋに対する最小要求を満たさない全てのルートが捨てられる（要求Ｍ〜j,k＞Ｍ〜k min）。一例として、全てのリンクが最小のセキュリティ要求をサポートするルートのみが、有効ルートとみなされる。
- 第二の工程において、あるメトリック・タイプｋに対する最小信頼性を有しない全てのルートｉが捨てられる（要求Ｒ〜j,k＞Ｒ〜k min）。一例として、サポートされたレートについてのメトリックが６０％を超える確率で有効なルートのみが、有効ルートとして許可される。
【００３９】
残った有効ルートのセットから、次の式（１）で示される決定メトリックを最大にするものが選択される。
2008543163.tif 000006
【００４０】
あるメトリック Ｍ〜j,k1は、その値がより大きい方が良く（例えば、サポートされたレート、リンク品質等）、他のメトリックＭ〜j,k2は、その値が小さい方が良い（例えば、遅延、ホップ数等）ことに留意されたい。これらの違いは、Ｍ〜jを決定するときに、正規化しなければならない。また、上記Ｍ〜jを決定する式は、線形の形であることに留意されたい。メトリックの値の範囲に応じて、 jのための式は、例えば、多項式または指数の形の他の関数を含むことができる。
【００４１】
いくつかのメトリックの間には、トレードオフが存在する。多くのメトリックを組み合わせて一つの比較可能値にするには、従来知られているユーティリティ・ファンクションを使用できる。
【００４２】
種々のノードが、それぞれ、ルート・メトリックＭ、ルート・メトリック・センシティビティＳおよびルート・メトリック信頼性Ｒを求めることができるように、リンク・メトリック、リンク・メトリック・センシティビティおよびリンク・メトリック信頼性は、ノード間で配布されなければならない。上述のように、ルート・メトリック・センシティビティＳ、ルート・メトリック信頼性Ｒ、またはこれら二つのうち一つのみ、ルート・メトリックそれ自身に加えて、使用することができる。
【００４３】
ノード間のリンク情報の配布は、信号オーバヘッドを生じさせるので、信号量を制限することが望ましい。従って、リンク情報は、それがルート決定に重要なときにのみ、配布しなければならない。
【００４４】
リンク情報の配布を制限する可能なメカニズムは、必要とみなすときのみ配布すること、およびマルチプル・リンクのために集めることである。
【００４５】
必要とみなすときにリンク情報を配布するトリガーは、例えば、次にことに基づく。
‐センシティビティＳが、特定量以上変化した場合
‐信頼性Ｒが、特定量以上変化したか、または特定の閾値を超えた場合
‐リンク・メトリックＭが特定量以上変化したか、または特定の閾値を超えた場合（例えば、リンク・ボトルネックが特定された場合）
【００４６】
マルチプル・リンクのためにリンク情報を集めることは、これらのリンクのためのルーティング決定を行うことができないか許可されていないノードにメトリックを送るときに使用できる。集めることの可能なメカニズムは、完全ルートに使用されたと同様に、サブルート・メトリックを計算することである。
【００４７】
"メトリックが１０％より多く変化したときのみ、この情報を転送"のような関連トリガーとともに転送されるべき情報が何の情報かを他のノードに通知するのに、配布サブスクリプション・アプローチを使用できる。
【００４８】
各ノードは、他のノードからのサブクリプションおよびそれ自身の必要に応じて、他のノードからの情報にサブスクライブする。配布サブクリプション・アプローチは、また、各ノードに、どのように情報を集めるかの入力を与える。ノードは、また、サブクリプションに加えて、またはこれに代えて、ルーティング決定を行うために望ましいときにはいつでも、他のノードから必要な情報を要求できる。
【００４９】
図３は、ルート・メトリックがそのルートの全てのリンクのリンク・メトリックの総和であるときにルーティング決定を改良するために、負荷に対するメトリック・センシティビティがどのように使用されるかの例を示す。
【００５０】
図３には、非常に小さな２ホップのネットワークが示されている。このネットワークは、３つのノード３１，３２，３３を有する。各ノードには、２つの利用可能な無線アクセス技術（ＲＡＴ）ＡおよびＢが存在する。各リンク／ホップｉに対するリンク・メトリックは、例えば、次の式（２）に基づく。
2008543163.tif 000007
ここで、
‐Ｌは、リンクの現在の負荷
‐Ｃは、リンクの容量
‐ΔＬは、第一ノード３１から第二ノード３２を介して第三ノード３３へルートされるべき新たなフローの増分負荷である。
【００５１】
第一ホップ、すなわち第一ノード３１と第二ノード３２との間は、１で示され、第二ホップ、すなわち第二ノード３２から第三ノード３３までは、２で示されている。無線アクセス技術は、それぞれ、ＡおよびＢで示されている。
【００５２】
表２は、従来技術によるルーティング前に計算されるメトリックを示す。表２は、異なるリンクに対するＬおよびＣの現在値、ならびに全てのリンクに対するＭの得られた値を示す。この表に示されているように、各ホップに対して、Ｍの値は、ＲＡＴ Ｂに対して、最も低い。従って、従来技術の計算によれば、両ホップに対して、ＲＡＴ Ｂが選択されなければならず、トータル・ルート・メトリックは５となる。
【００５３】
[表２]
2008543163.tif 000008
【００５４】
ΔＬ１＝１、すなわち、新たなフローの負荷が１と仮定すると、新たなフローのルーティングの後の状況が、表３に示されている。各場合、Ｌは１増加して、結果として、新たな値Ｌ’となり、Ｃは不変である。従って、新たなメトリック値Ｍ’は、式（３）によって計算でき、
2008543163.tif 000009
式(３)は、次の式(４)と同じである。
2008543163.tif 000010
表３は、ルーティングの後に計算されたメトリックを示し、各ホップに対するＭ´の新たな値が表３に示されている。
【００５５】
[表３]
2008543163.tif 000011
【００５６】
表３に示されているように、フローがルートを通った後、各ホップに対してＲＡＴ Ｂを使用するよう選択されたルート・メトリックは、８．３３である。しかしながら、第二ホップに対して、代わりにＲＡＴ Ａが使用されると、ルート・メトリックは７．０８に低減する。従って、後から見ると、この方が、より良いルーティング決定だったことになる。問題は、ほとんどの場合、最初に、全てのノードのＬＭＦからアップデートされたメトリック値を要求して、これらアップデートされたメトリックに基づいてルーティング決定を実行できないことである。
【００５７】
本発明によれば、この場合、ルーティング決定を改良するのに、負荷に対するメトリック・センシティビティを使用する。式（５）に示されているように、負荷Ｌに対するＭiの微分係数をセンシティビティＳiとして使用する。
2008543163.tif 000012
【００５８】
センシティビティは、負荷に依存する。本発明によれば、各ノードのＬＭＦユニットが、メトリックに加えて、センシティビティを計算し、必要に応じて、これら双方を、他のノードと交換する。
【００５９】
ルートおよび新たなフローのルート・メトリックを求めるとき、このフローの増分負荷ΔＬは、式（６）の有効リンク・メトリックを使用することにより考慮されている。
2008543163.tif 000013
【００６０】
表４は、本発明によるセンシティビティを含んで計算されたメトリックを示す。表４は、上記と同じ例におけるＬ，Ｃ，Ｍ，ＳおよびＭ’を示す。表４は、ＳおよびＭ’のための値を保持する新たな行が追加されたことを除いて、表１と同じである。
【００６１】
[表４]
2008543163.tif 000014
【００６２】
表４に示されているように、最少ルート・メトリックを有するルートは、事実、第一ホップに対してＲＡＴ Ｂを使用し第二ホップに対してＲＡＴ Ａを使用するルートである。センシティビティは、変化が小さいときに、アップデートされたメトリックの正確な予測を与えるだけであることに留意されたい。
【００６３】
次に、図４を参照して、本発明によりメトリック・センシティビティをどのように適用するかの第二の例を説明する。この例は、多数の異なるチャネル（リンク）を介して２つのノード４１および４２の間をデータを送信できるときに、負荷に対するメトリック・センシティビティがいかに使用されるかを示す。図４には、簡単のために、２つのチャネルのみが示されているが、この例は、容易に、任意の数のチャネルに拡張できる。このシナリオでは、ルーティング決定が、どの利用可能チャネルを送信のために選択するか決定を行う。
【００６４】
２つの異なるチャネルを有する１つのホップ接続について考える。ここでは、各チャネルのメトリックは、ある基準データｒrefに対するサポートされたデータ・レートに基づく。
Ｍ ＝ ｒref／ｒ        （７）
ルーティング決定は、ルート・メトリックを最小にするリンク（チャネル）を選択する。
【００６５】
この例では、増分負荷ΔＬ＝１を有するノード１からノード２への新たなフローが追加される。ルーティング選択が、式（７）に従ってリンク・メトリックＭのみに基づくならば、フローは、図４に示されているように、チャネルＡのルートを通る。
【００６６】
ｒref＝２Ｍｂ／ｓ、ＲＡＴ Ａに対してｒ＝５Ｍｂ／ｓ、ＲＡＴ Ｂに対してｒ＝４Ｍｂ／ｓとすると、ＲＡＴ Ａに対してＭ＝０．４、ＲＡＴ Ｂに対してＭ＝０．５である。
【００６７】
しかしながら、異なるチャネルは、極めて異なる特性を有することがあり、この場合、メトリック・センシティビティに基づくルーティング決定がより良いソリューションを提供する。例えば、異なるチャネルは、
ａ） 異なるリソース特性およびマルチプル・アクセス・スキームで使用されるＲＡＴのタイプが異なる可能性がある。
ｂ） チャネルをアクセスするユーザの数ｎが異なる可能性がある。
ｃ） 容量Ｃおよび負荷Ｌが異なる可能性がある。
【００６８】
このメトリックは、サポートされたデータ・レートｒに基づくが、この値は、例えば、Ｃ、ｎ、Ｌおよび他の値に依存するチャネル特定ファンクションに従って決定される。
【００６９】
トラヒック負荷Ｌの変化に対するｒのセンシティビティ∂r／∂Lは、例えば、実験観察から、またはｒを決定する関数から導出される。複素関数の場合、この関数のテイラー級数近似が、センシティビティ∂r／∂Lを求めるのに使用できる。この例では、トラヒック負荷Ｓ（１）に対するメトリック・センシティビティは、次の式（８）により求められる。
2008543163.tif 000015
【００７０】
この場合、図４では、メトリック・センシティビティＳ（Ｌ）ならびにトラヒック負荷増加ΔＬ＝１Ｍｂ／sに対する決定メトリックＭ〜が得られる。チャネルＡが、より低いリンク・メトリックＭおよびより高いサポートされたレートを有しているにも拘わらず、全体決定メトリックＭ〜は、チャネルＢの方が低い。これは、ｒが、異なるチャネルに対して異なるセンシティビティを有するからである。この一つの理由は、例えば、チャネルＡが、他のトラヒックによりチャネル容量に対してより高い相対負荷を有することがあげられる。他の理由は、チャネルＡが、チャネルＢ（例えば、あるリザベーション・ベース・マルチプル・アクセス・スキームであり得る）よりも、負荷増加により敏感なマルチプル・アクセス・スキーム（例えば、キャリア・センス・マルチプル・アクセス）を使用することがあげられる。あるいは、チャネルＡが、チャネルをアクセスするより多くのユーザを有していることがあげられる。
【００７１】
表５は、本発明による図４のメトリックを示す。表５は、ｒ、Ｍ、Ｓおよび式（９）により計算された全体決定メトリックＭ〜を示す。
2008543163.tif 000016
ここで、Ｓ（Ｌ）は、式（８）により計算される。
【００７２】
[表５]
2008543163.tif 000017
【００７３】
第三の例は、一つのホップが固定接続である２ホップ無線伝送である。この例は、マルチホップ伝送パラダイムを、ＲＡＮアーキテクチャ内の伝送プロトコルのファンクショナル配布に拡張したものベースにしている。例えば、マルチホップＡＲＱコンセプト（あるコンテクストでは、"マルチホップ・ゼネリック・リンク層"と呼ばれる）が使用されると仮定する。リンク層は、ベアラ・ゲートウエイ（ｂｅａｒｅｒ  ｇａｔｅｗａｙ）で終端され、アクセス・ポイントは既にリレイとみなされている。（ＷＣＤＭＡシステムでは、第一ホップが、ＲＮＣとノードＢとの間のＩｕｂインターフェースであり、第二ホップが、無線Ｕｕインターフェースである。）
この例では、マルチホップ・ルートの一部がメトリックを有していないものと（何故なら、それがボトルネックにならないというアプリオリがある（例えば、ファイバ接続））する。この例に示されているように、本発明は、ネットワーク全体の完全な知識は得られない、すなわち、あるホップが、固定接続とみなさなければならないというオペレーティング・シナリオに適用可能である。
【００７４】
第三の例に関連して、図５は、固定ネットワーク５１および無線ネットワーク５２の両方を備える電気通信マルチホップ・ネットワークを示す。Ｌ２プロトコルＲＬ２は、無線ベアラ・ゲートウェイＲＢＧから無線アクセス・ポイントＲＡＰを介してユーザ・ターミナルＵＴまでのスパンを有する。ＲＡＰからＵＴへの接続は、一つまたはそれ以上の中間リレイ・ノードＲＮを介して行うことができる。この場合、ＲＢＧとＲＡＰとの間のリンクは、固定リンクであり、Ｍ〜j,kおよびＳ〜j,kを求める役目は全然果たさない。何故なら、ルートの全体性能に与える影響はほとんど無いからである。ルート・パラメータとして、無線リンクのみ役目を果たし、固定リンクは考慮されない。
【図面の簡単な説明】
【００７５】
【図１】通信ネットワークを通る多数の可能なルートを介した送信を概略的に示す。
【図２】メトリックのセンシティビティの一例を示す。
【図３】本発明による方法がいかにして適用可能かの第一例を示す。
【図４】本発明による方法がいかにして適用可能かの第二例を示す。
【図５】固定ネットワークおよび無線ネットワーク双方を含む電気通信マルチホップ・ネットワークを示す。
【図１】
2008543163.tif 000018
【図２】
2008543163.tif 000019
【図３】
2008543163.tif 000020
【図４】
2008543163.tif 000021
【図５】
2008543163.tif 000022
【国際調査報告】
2008543163.tif 000023
2008543163.tif 000024
2008543163.tif 000025