(57)【要約】  無線ネットワークをデータが横断するための終端間経路を確立する方法およびシステムであって、リンク・コスト関数を計算すること、計算したリンク・コスト関数を使用して、量子化リンク・コスト関数を計算すること、およびデータが無線ネットワークを横断するための複数の終端間経路のそれぞれの量子化コストを計算することを含み、上記複数の終端間経路が、無線ネットワーク中の同じノード・セット内のノード間の経路を含み、データが無線ネットワークを横断するための上記複数の終端間経路のそれぞれの量子化コストが、量子化リンク・コスト関数を使用して計算され、さらに、上記複数の終端間経路のそれぞれの量子化コストに基づいて、データが無線ネットワークを横断するための上記複数の終端間経路の１つを選択することを含む、方法およびシステムについて記載する。また、データが無線ネットワークを横断するための双方向終端間経路の確立に参加するように構成された無線ネットワーク中のノードについても記載する。
2010518745.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークをデータが横断するための終端間経路を確立する方法であって、
リンク・コスト関数を計算するステップと、
前記計算したリンク・コスト関数を使用して、量子化リンク・コスト関数を計算するステップと、
前記無線ネットワークをデータが横断するための複数の終端間経路のそれぞれの量子化コストを計算するステップであって、前記複数の終端間経路が、前記無線ネットワーク中の同じノード・セット内のノード間の経路を含み、前記無線ネットワークをデータが横断するための前記複数の終端間経路のそれぞれの前記量子化コストを前記量子化リンク・コスト関数を使用して計算するステップと、
前記複数の終端間経路のそれぞれの前記量子化コストに基づいて、前記無線ネットワークをデータが横断するための前記複数の終端間経路の１つを選択するステップと、
を含む、前記方法。
【請求項２】
前記無線ネットワークが、無線メッシュ・ネットワークである、請求項１に記載の方法。
【請求項３】
前記無線ネットワーク中の同じノード・セット内のノード間の、異なるチャネルを利用する前記複数の終端間経路が、複数の無線インタフェースを含み、さらに前記複数の終端間経路がそれぞれ双方向性である、請求項１に記載の方法。
【請求項４】
媒体アクセス制御レイヤおよび物理レイヤのプロトコル・オーバヘッドを決定するステップと、
データ・サイズを決定するステップと、
リンク・データ・レートを定期的に決定するステップと、
パケット・エラー率を定期的に測定するステップと、
チャネル利用率の重み関数を測定するステップと、
前記パケット・エラー率の重み関数を決定するステップと、
をさらに含む、請求項１に記載の方法。
【請求項５】
チャネル利用率を定期的に推定するステップをさらに含む、請求項４に記載の方法。
【請求項６】
チャネル測定期間を決定するステップと、
チャネル・ビジー・タイムを定期的に測定するステップと、
をさらに含む、請求項５に記載の方法。
【請求項７】
量子化レベルの数を決定するステップと、
量子化因子を決定するステップと、
をさらに含む、請求項１に記載の方法。
【請求項８】
第１のチャネル変更重み関数を決定するステップと、
第２のチャネル変更重み関数を決定するステップと、
をさらに含む、請求項１に記載の方法。
【請求項９】
前記無線メッシュ・ネットワークが、プロアクティブ・ネットワークである、請求項２に記載の方法。
【請求項１０】
前記計算したリンク・コスト関数の結果を、制御メッセージの状態情報として通知するステップと、
前記計算したリンク・コスト関数を使用して、ルーティング・テーブルを生成し、維持するステップと、
をさらに含む、請求項９に記載の方法。
【請求項１１】
前記計算したリンク・コスト関数の結果が所定のしきい値よりも大きい場合に、前記結果を制御メッセージの状態情報として直ちに通知するステップをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記無線メッシュ・ネットワークが、オンデマンド・ネットワークである、請求項２に記載の方法。
【請求項１３】
経路発見を初期化するステップと、
前記計算したリンク・コスト関数を使用して、ルーティング・テーブルを生成し、維持するステップと、
をさらに含む、請求項１２に記載の方法。
【請求項１４】
前記無線メッシュ・ネットワークが、ハイブリッド・メッシュ・ネットワークである、請求項２に記載の方法。
【請求項１５】
前記無線メッシュ・ネットワークが、ツリー・トポロジに基づく、請求項２に記載の方法。
【請求項１６】
初期化されたメトリック・フィールドおよびシーケンス番号フィールドを含めた、ルート通知の伝送および経路発見の初期化の一方を実行するステップと、
前記メトリック・フィールドを更新するステップと、
前記シーケンス番号フィールドを更新するステップと、
ルーティング・テーブルを更新するステップと、
前記双方向終端間経路を確立するステップと、
をさらに含む、請求項１５に記載の方法。
【請求項１７】
無線ネットワークをデータが横断するための終端間経路を確立するシステムであって、
リンク・コスト関数を計算する手段と、
前記計算したリンク・コスト関数を使用して、量子化リンク・コスト関数を計算する手段と、
前記無線ネットワークをデータが横断するための複数の経路のそれぞれの量子化コストを計算する手段であって、前記複数の経路が、前記無線ネットワーク中の同じノード・セット内のノード間の経路を含み、前記無線ネットワークをデータが横断するための前記複数の終端間経路のそれぞれの前記量子化コストを前記量子化リンク・コスト関数を使用して計算する手段と、
前記複数の経路のそれぞれの前記量子化コストに基づいて、前記無線ネットワークをデータが横断するための前記複数の終端間経路の１つを選択する手段と、
を備える、前記システム。
【請求項１８】
前記無線ネットワークが、無線メッシュ・ネットワークである、請求項１７に記載のシステム。
【請求項１９】
前記無線ネットワーク中の同じノード・セット内のノード間の、異なるチャネルを利用する前記複数の終端間経路が、複数の無線インタフェースを含み、さらに前記複数の終端間経路がそれぞれ双方向性である、請求項１７に記載のシステム。
【請求項２０】
媒体アクセス制御レイヤおよび物理レイヤのプロトコル・オーバヘッドを決定する手段と、
データ・サイズを決定する手段と、
リンク・データ・レートを定期的に測定する手段と、
パケット・エラー率を定期的に測定する手段と、
チャネル利用率の重み関数を決定する手段と、
前記パケット・エラー率の重み関数を決定する手段と、
をさらに備える、請求項１７に記載のシステム。
【請求項２１】
チャネル利用率を定期的に推定する手段をさらに含む、請求項２０に記載のシステム。
【請求項２２】
チャネル測定期間を決定する手段と、
チャネル・ビジー・タイムを定期的に測定する手段と、
をさらに備える、請求項２１に記載のシステム。
【請求項２３】
量子化レベルの数を決定する手段と、
量子化因子を決定する手段と、
をさらに備える、請求項１７に記載のシステム。
【請求項２４】
第１のチャネル変更重み関数を決定する手段と、
第２のチャネル変更重み関数を決定する手段と、
をさらに備える、請求項１７に記載のシステム。
【請求項２５】
前記無線メッシュ・ネットワークが、プロアクティブ・ネットワークである、請求項１８に記載のシステム。
【請求項２６】
前記計算したリンク・コスト関数の結果を、制御メッセージの状態情報として通知する手段と、
前記計算したリンク・コスト関数を使用して、ルーティング・テーブルを生成し、維持する手段と、
をさらに備える、請求項２５に記載のシステム。
【請求項２７】
前記計算したリンク・コスト関数の結果が所定のしきい値よりも大きい場合に、前記結果を制御メッセージの状態情報として直ちに通知する手段をさらに備える、請求項２６に記載のシステム。
【請求項２８】
前記無線メッシュ・ネットワークが、オンデマンド・ネットワークである、請求項１８に記載のシステム。
【請求項２９】
経路発見を初期化する手段と、
前記計算したリンク・コスト関数を使用して、ルーティング・テーブルを生成し、維持する手段と、
をさらに備える、請求項２８に記載のシステム。
【請求項３０】
前記無線メッシュ・ネットワークが、ハイブリッド・メッシュ・ネットワークである、請求項１８に記載のシステム。
【請求項３１】
前記無線メッシュ・ネットワークが、ツリー・トポロジに基づく、請求項１８に記載のシステム。
【請求項３２】
初期化されたメトリック・フィールドおよびシーケンス番号フィールドを含めた、ルート通知の伝送および経路発見の初期化の一方を実行する手段と、
前記メトリック・フィールドを更新する手段と、
前記シーケンス番号フィールドを更新する手段と、
ルーティング・テーブルを更新する手段と、
をさらに備える、請求項３１に記載のシステム。
【請求項３３】
無線ネットワークをデータが横断するための双方向終端間経路の確立に参加するように構成された前記無線ネットワーク中のノードであって、
複数のチャネルをそれぞれ有する前記ノードの各チャネルの品質および利用率を定期的に測定する手段と、
前記各チャネルの前記測定した品質および利用率を使用して、ルーティング・メトリックを定期的に計算する手段と、
前記計算したルーティング・メトリックを用いてルーティング・テーブルを定期的に更新する手段と、
前記ルーティング・テーブルに基づいて、データが前記無線ネットワークを横断するための前記双方向終端間経路を選択する手段と、
を備える、前記ノード。
【請求項３４】
少なくとも１つの無線インタフェースを有する、請求項３３に記載のノード。
【請求項３５】
無線ネットワークをデータが横断するための終端間経路を確立する方法であって、
リンク・コスト関数を計算するステップと、
前記無線ネットワークをデータが横断するための複数の終端間経路のそれぞれのコストを計算するステップであって、前記複数の終端間経路が、前記無線ネットワーク中の同じノード・セット内のノード間の異なるチャネルを利用する経路を含み、データが前記無線ネットワークを横断するための前記複数の終端間経路のそれぞれの前記コストを前記リンク・コスト関数を使用して計算する、前記ステップと、
前記複数の終端間経路のそれぞれの前記コストに基づいて、データが前記無線ネットワークを横断するための前記複数の終端間経路の１つを選択するステップと、
を含む、前記方法。
【請求項３６】
無線ネットワークをデータが横断するための終端間経路を確立するシステムであって、
リンク・コスト関数を計算する手段と、
前記無線ネットワークをデータが横断するための複数の終端間経路のそれぞれのコストを計算する手段であって、前記複数の終端間経路が、前記無線ネットワーク中の同じノード・セット内のノード間の異なるチャネルを利用する経路を含み、データが前記無線ネットワークを横断するための前記複数の終端間経路のそれぞれの前記コストを前記リンク・コスト関数を使用して計算する、前記手段と、
前記複数の終端間経路のそれぞれの前記コストに基づいて、データが前記無線ネットワークを横断するための前記複数の終端間経路の１つを選択する手段と、
を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークのための無線・トラフィック認識型ルーティング・メトリック（ｒａｄｉｏ  ａｎｄ  ｔｒａｆｆｉｃ  ａｗａｒｅ  ｒｏｕｔｉｎｇ  ｍｅｔｒｉｃ）に関し、さらに詳細には、１つまたは複数のノードが１つまたは複数の異なるチャネルでそれぞれ動作する複数の無線装置（ｒａｄｉｏ）を有する、あるいは１つまたは複数のノードが１つまたは複数のチャネルで動作する単一の無線装置を有する無線メッシュ・ネットワークをデータが横断するための経路またはパスを選択する方法および装置に関する。
【背景技術】
【０００２】
現在のメッシュ・ルーティング・プロトコルの多くは、パス／経路選択決定を行うためのメトリックとして最小ホップ数を使用している。本明細書で使用する記号「／」は、同一または同様の構成要素の代替の名称を示す。この方法では、無線リンクの品質、トラフィック負荷、およびリンクの利用可能帯域幅は考慮しない。パケットまたはフレームの形態のデータの転送のために、ホップ数が最小となる経路を選択する。しかし、ホップ数が最小の経路は、離れたノード間に無線リンクを含む傾向があり、当該経路のリンクの品質が良好でない可能性もあるので、性能が低い可能性がある。物理的距離の長い無線リンクは、損失が大きくなり、何度も再送することになり、物理レイヤのデータ・レートが低くなる可能性がある。例えばＩＥＥＥ８０２．１１やＩＥＥＥ８０２．１６の無線装置など多くの無線伝送システムでは、リンクの品質に応じた物理レイヤのデータ・レートを採用している。実は、これにより、ホップ数は多いがリンク品質は高いパスを選択した場合よりもスループットが低下し、ネットワーク利用効率も低下している。
【０００３】
従来技術では、「予想伝送カウント（ｅｘｐｅｃｔｅｄ  ｔｒａｎｓｍｉｓｓｉｏｎ  ｃｏｕｎｔ）（ＥＴＸ）」と呼ばれるメトリックがルーティング・メトリックとして使用されている。ＥＴＸは、無線リンクを介したパケットの転送を成功させるのに必要なＭＡＣレイヤの予想伝送回数を推定したものである。パス（ＥＴＸコストが最低となるパス）上の全てのリンクのＥＴＸの合計が最小となる経路が選択される。ＥＴＸは、リンクのパケット損失率の影響は捕らえているが、異なる伝送レートおよびリンクの利用可能帯域幅は考慮していない。
【０００４】
報告されている別の従来技術の方法では、リンクの伝送レートの差を考慮することによってＥＴＸを改善するために、「予想伝送時間（ＥＴＴ）」と呼ばれるメトリックを提案している。リンクのＥＴＴは、そのリンクを介したパケットの伝送が成功した場合のＭＡＣレイヤ上の予想持続時間として定義される。経路のコストは、その経路上の全てのリンクのＥＴＴの合計である。ＥＴＴは、異なるリンク伝送レートの影響を考慮に入れている。しかし、リンクのトラフィック負荷および利用可能帯域幅ならびに媒体を共用することによるネットワーク内の干渉の影響は、完全には捕らえきれていない。重い負荷のかかったリンクを選択して経路に含めて、リンクの負荷がさらに大きくなり、輻輳が生じることになる恐れがある。
【０００５】
従来の関連出願には、重み付き無線・トラフィック負荷認識型（ＷＲＡＬＡ）ルーティング・メトリックについて記載したものもある。そこに記載されているメトリックは、無線伝送レート、損失率、リンクのトラフィック負荷および利用可能帯域幅、ならびにネットワーク内で媒体を共用することによる干渉など、メッシュ・ネットワーク内の無線リンクの様々な特徴の影響を捕らえている。
【０００６】
しかし、上記のルーティング・メトリックは何れも、マルチラジオ（複数の無線装置）、マルチチャネルがルーティングの性能に及ぼす影響を考慮していない。メッシュ・ネットワークでは、ノード／メッシュ・ポイントは、複数の無線装置を備えることができ、それらの無線装置のそれぞれが、ネットワーク容量を増大させるために異なるチャネル／周波数で動作することができる。単一の無線装置しか備えないノードとは異なり、マルチラジオ・マルチチャネル・ノードは、１つのチャネルでデータ・パケットを受信し、同時に別のチャネルでデータ・パケットを送信することができる。従って、それぞれ異なるチャネルで動作する複数の無線装置を備えた中継ノードを選択することが好ましい。さらに、単一の無線装置しか備えていなくても、複数のチャネルで動作することができる無線装置を有するノードは、１つのチャネルでデータを受信し、次いで別のチャネルに切り替えてそのデータを転送／中継／伝送することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
トラフィックおよび帯域幅を認識するだけでなく、それぞれ異なるチャネルで動作する複数の無線装置を有する１つまたは複数のノードを有する、あるいは複数のチャネルで動作する単一の無線装置を有する１つまたは複数のノードを有することの影響も捕らえるメトリックを使用する、データがメッシュ・ネットワークを横断するための経路を選択するシステムがあると有利である。
【課題を解決するための手段】
【０００８】
マルチラジオ・マルチチャネル無線メッシュ・ネットワークでは、ソース・ノード／メッシュ・ポイントから宛先ノード・メッシュ・ポイントにパケットまたはフレームの形態のデータを転送するために、単一ホップまたはマルチホップのパスを選択する必要がある。パス／経路選択は、メトリックに基づいて行われる。このようなルーティング・メトリックは、メッシュ・ネットワークにおけるルーティングおよび転送機構の設計の最適化のために重要である。本発明は、マルチラジオ（複数の無線装置）およびマルチチャネルがルーティング性能に及ぼす影響を捕らえる無線・帯域幅認識型メトリック、ならびにそのメトリックを使用して、データがメッシュ・ネットワークを横断するための経路を選択する装置および方法について記載する。本発明を説明するために無線メッシュ・ネットワークを一例として用いるが、本発明のメトリックは、無線メッシュ・ネットワークに限定されないことに留意されたい。本発明は、例えばツリー型のマルチホップ無線ネットワーク等、その他のネットワーク・トポロジに使用して、ノードとツリー・ノードとの間の経路を選択することもできる。
【０００９】
ルーティング・メトリックの値は、リンク品質およびトラフィック負荷のダイナミクスによって頻繁に変化する可能性があり、それにより経路が不安定になる可能性がある。急速なリンク品質および負荷の変動に直面しても、高いルーティング性能を維持したまま経路の安定性を確保することが重要である。従って、本発明では、ルーティング・メトリックを量子化することによって、経路の安定性を維持しながら、リンク状態およびネットワーク・トポロジの変化に対する迅速な応答を実現する方法も記載する。
【００１０】
データが無線ネットワークを横断するための終端間経路を確立する方法およびシステムであって、リンク・コスト関数を計算すること、計算したリンク・コスト関数を使用して、量子化リンク・コスト関数を計算すること、およびデータが無線ネットワークを横断するための複数の終端間経路のそれぞれの量子化コストを計算することを含み、上記複数の終端間経路が、無線ネットワーク中の同じノード・セット内のノード間の異なるチャネルを利用する経路を含み、データが無線ネットワークを横断するための上記複数の終端間経路のそれぞれの量子化コストが、量子化リンク・コスト関数を使用して計算され、さらに、上記複数の終端間経路のそれぞれの量子化コストに基づいて、データが無線ネットワークを横断するための上記複数の終端間経路の１つを選択することを含む、方法およびシステムについて記載する。また、データが無線ネットワークを横断するための双方向終端間経路の確立に参加するように構成された無線ネットワーク中のノードであって、複数のチャネルをそれぞれ有する上記ノードの各チャネルの品質および利用率を測定する手段と、各チャネルの測定した品質および利用率を使用して、ルーティング・メトリックを計算する手段と、計算したルーティング・メトリックを用いてルーティング・テーブルを更新する手段と、ルーティング・テーブルに基づいて、データが無線ネットワークを横断するための双方向終端間経路を選択する手段とを備えたノードについても記載する。また、データが無線ネットワークを横断するための終端間経路を確立する方法およびシステムであって、リンク・コスト関数を計算すること、およびデータが無線ネットワークを横断するための複数の終端間経路のそれぞれのコストを計算することを含み、上記複数の終端間経路が、無線ネットワーク中の同じノード・セット内のノード間の異なるチャネルを利用する経路を含み、データが無線ネットワークを横断するための上記複数の終端間経路のそれぞれのコストが、リンク・コスト関数を使用して計算され、さらに、上記複数の終端間経路のそれぞれのコストに基づいて、データが無線ネットワークを横断するための上記複数の終端間経路の１つを選択することを含む、方法およびシステムについても記載する。
【００１１】
本発明は、以下の詳細な説明を添付の図面と関連づけて読むことにより最も良く理解される。添付の図面には、以下に簡単に説明する図面が含まれる。
【図面の簡単な説明】
【００１２】
【図１】本発明の原理による、双方向終端間経路を確立する方法を示す流れ図である。
【図２】本発明のリンク・コスト関数の計算を示す流れ図である。
【図３】本発明のチャネル利用率の重み関数の決定を示す流れ図である。
【図４】本発明のチャネル推定を示す流れ図である。
【図５】本発明の量子化リンク・コスト関数の計算を示す流れ図である。
【図６】本発明の経路の量子化コストの計算を示す流れ図である。
【図７】無線メッシュ・ネットワークを示す概略図である。
【図８】本発明の原理に従って動作するモジュールを有する無線メッシュ・ネットワークのノードを示すブロック図である。
【発明を実施するための形態】
【００１３】
Ｔｏｈは、媒体アクセス制御（ＭＡＣ）レイヤおよび物理レイヤのプロトコル・オーバヘッドを表すパラメータである。Ｓは、テスト・フレーム／パケット・サイズである。例えばＩＥＥＥ８０２．１１ａの無線伝送システムでは、Ｔｏｈは１８５μｓになることがある。簡潔にするために、Ｔｏｈは０に設定することもできる。テスト・パケットのサイズＳは、予め設定された所定の定数、例えば８２２４ビットとすることができる。また、ノードから伝送されるパケットの平均サイズまたは最大サイズをテスト・フレーム／パケット・サイズとして選択することもできる。さらに、Ｒは、ノードが現在のチャネル条件の下で標準サイズＳのパケットまたはフレームの形態でデータを伝送するリンク・データ・レートである。リンク・データ・レートは、リンク・レート適応のローカルな実施態様によって決まる。Ｅｒは、ノードが標準サイズＳのパケット／フレーム（データ）を伝送レートＲで伝送する場合のパケット／フレーム・エラー率である。データは、複数ビットの情報で構成される。データは、伝送しやすいようにパケットまたはフレームの形態にされる。Ｅｒは、メッシュ・ネットワーク中のノードがローカルに測定および／または推定することができる。ρは、チャネルの利用可能帯域幅と関係する、リンクのチャネルの負荷／利用率である。本発明のルーティング・メトリックは、重み付き無線・帯域幅認識型（ＲＡＢＡ）リンク・コスト関数である。無線リンクＬのＲＡＢＡコスト関数は、以下のように計算することができる。
【００１４】
【数１】
2010518745.tif 000003
ここで、Ｗ１（ρ）およびＷ２（Ｅｒ）はそれぞれ、チャネル利用率ρおよびパケット／フレーム・エラー率Ｅｒの２つの重み関数である。Ｗ１（ρ）は、以下のようないくつかの形態をとることができる。
【００１５】
【数２】
2010518745.tif 000004
この場合は、チャネル利用率について全てのリンクが等しく重み付けされる。
【００１６】
【数３】
2010518745.tif 000005
この場合は、リンクには、チャネル負荷／利用率に応じて増大する重みが与えられる。
【００１７】
【数４】
2010518745.tif 000006
この場合は、チャネル負荷／利用率がρ０以下であるリンクが等しく重み付けされる。チャネル負荷／利用率がρ０からρｍａｘの間であるリンクは、チャネル負荷／利用率に応じて増大する重みが与えられる。チャネル利用率がρｍａｘを超えるリンクは、コストが無限であるのでパス選択において考慮されない。一般に、システム設計者は、ネットワークの収益および適用に関するいくつかの目標とする要件に応じて、ρｍａｘおよびρ０の適当な値を選択することができる。
【００１８】
同様に、Ｗ２（Ｅｒ）も、以下のようないくつかの形態を取ることができる。
【００１９】
【数５】
2010518745.tif 000007
この場合は、パケット・エラー率について全てのリンクが等しく重み付けされる。
【００２０】
【数６】
2010518745.tif 000008
この場合は、リンクには、パケット・エラー率に応じて増大する重みが与えられる。
【００２１】
【数７】
2010518745.tif 000009
この場合は、パケット／フレーム・エラー率がＥ０以下であるリンクが等しく重み付けされる。パケット・エラー率がＥ０からＥｍａｘの間であるリンクは、パケット・エラー率に応じて増大する重みが与えられる。パケット・エラー率がＥｍａｘを超えるリンクは、コストが無限であるのでパス選択において考慮されない。一般に、システム設計者は、ネットワークの収益および適用に関するいくつかの目標とする要件に応じて、Ｅ０およびＥｍａｘの適当な値を選択することができる。
【００２２】
重み関数Ｗ１（ρ）およびＷ２（Ｅｒ）は、上記の形態に限定されないことに留意されたい。これらの関数は、その他の形態をとることも可能である。
【００２３】
ＲＡＢＡリンク・コスト関数は、特定のリンクを介してデータ・パケット／フレームを送信することによって消費される無線リソースの量、ならびに当該リンクにかかる負荷および当該リンクの利用可能帯域幅を捕らえる複合ルーティング・メトリックを表す。ＲＡＢＡリンク・コスト関数は、共有される無線媒体におけるフロー間干渉を考慮している。パス／経路選択では、パス／経路のリンク・データ・レートが高くなるほど、大きな利用可能帯域幅、および低いパケット・エラー率が優先される。
【００２４】
リンク／チャネルの品質および負荷はともに変動するので、ＲＡＢＡの値も頻繁に変化する。ＲＡＢＡをそのままルーティング・メトリックとして使用する場合には、パスが頻繁に変更され、経路が不安定になる可能性がある。本発明は、リンクの状態およびネットワーク・トポロジの変化に対する迅速な応答を実現するだけでなく、経路の安定性の維持も行う方法も含む。経路安定性を向上させるために、量子化ＲＡＢＡをリンク・コスト関数として使用する。リンクＬの量子化ＲＡＢＡ（ＱＲＡＢＡ）は、以下のような数式で表すことができる。
【００２５】
【数８】
2010518745.tif 000010
または
【００２６】
【数９】
2010518745.tif 000011
または
【００２７】
【数１０】
2010518745.tif 000012
ここで、Ｍは量子化レベルの数、Ｑは量子化因子である。一般に、システム設計者は、経路安定性とリンク状態およびトポロジの変化に対するネットワーク応答時間との間のいくつかの目標とする兼ね合いに応じて、ＭおよびＱの適当な値を選択することができる。例えば、所望の量子化レベルＭを１６とし、Ｑを最大値またはＲＡＢＡ（Ｌ）の範囲とすることができる。限られたビット数（一定サイズのフィールド）を使用してＱＲＡＢＡの値を表すために、ＱＲＡＢＡの値がＭ＋１を超える場合には、その値を切り捨ててＭ＋１にしてもよい。
【００２８】
ノードは、隣接するノードまでのリンクで使用されるチャネルの負荷／利用率を推定することができる。チャネル負荷／利用率を推定する１つの可能な方法は、チャネル・ビジー・タイムを使用するものである。共用されるという無線チャネルの性質から、チャネルは、干渉範囲内の任意のノードが伝送を実行するときにビジーになる。あるノードが、あるチャネルを使用してフレームまたはパケットの形態のデータを伝送するとき、このチャネルはビジーである。干渉範囲内のその他のノードは、同じ周波数を用いて同時に伝送することはできない。伝送を行えば、衝突が発生し、伝送されたフレーム／パケット（データ）がエラーとなる。さらに、ノードは別のノードから制御メッセージを受信することもできるが、この際、このノードはチャネルを一定期間確保（ｒｅｓｅｒｖｅ）する。ノードが以下に挙げる状態の１つである場合には、チャネルはビジーである。第１に、ノードがこのチャネル／周波数を用いてデータを伝送または受信している状態。第２に、ノードが、一定期間チャネルを確保する別のノードから制御／管理メッセージを受信する状態。第３に、ノードが、このチャネル／周波数上でしきい値を超える信号強度を有するビジー・キャリアを検知した状態。推定チャネル・ビジー・タイムが測定期間Ｔｐに対してＴｂｕｓｙであれば、チャネル負荷はρ＝Ｔｂｕｓｙ／Ｔｐである。
【００２９】
ソース・ノードから宛先ノードまでのパスは、複数のリンクＬｉと中間ノードＮｉとを含む。Ｌｉは、パス／経路上のノードＮｉとその前のホップＮｉ−１との間のリンクを表す。パスＰのＲＡＢＡコストは、以下のように計算される。
【００３０】
【数１１】
2010518745.tif 000013
経路安定性を改善するために量子化を用いる場合には、パスＰのＱＲＡＢＡコストを、以下のように計算する。
【００３１】
【数１２】
2010518745.tif 000014
ここで、リンクＬｉ＋１は、パスＰ上でリンクＬｉに続く次のリンクであり、ｆＬｉおよびｆＬｉ＋１はそれぞれ、リンクＬｉおよびＬｉ＋１に割り当てられたチャネル／周波数を表す。α１（ｆＬｉ、ｆＬｉ＋１）およびα２（ｆＬｉ、ｆＬｉ＋１）は、パス上の連続する２つのリンクに割り当てられたチャネル／周波数によって決まる、２つのチャネル変更重み（ｃｈａｎｎｅｌ  ｃｈａｎｇｅ  ｗｅｉｇｈｔ）（ＣＣＷ）関数である。α１（ｆＬｉ、ｆＬｉ＋１）は、以下のようないくつかの形態をとることができる。
【００３２】
【数１３】
2010518745.tif 000015
この場合は、伝送に割り当てられたチャネルについて全てのリンクが等しく重み付けされる。
【００３３】
【数１４】
2010518745.tif 000016
この場合は、パス上のＬａｓｔＬｉｎｋ、すなわち宛先ノードがパケット／フレーム（データ）を受信するリンクについては、ＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）はａ１に等しい。宛先ノードは、それ以上データを転送しないことに留意されたい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が同じチャネル／周波数を使用する場合、すなわち、その中間のノードＮｉが、チャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、チャネル／周波数ｆＬｉ＋１＝ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）は、ｂ１に等しい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が異なるチャネル／周波数を使用するが、使用する無線装置は同じである場合、すなわち、その中間のノードＮｉが、ある無線インタフェースを用いてチャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、同じ無線インタフェースを用いてチャネル／周波数ｆＬｉ＋１≠ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）は、ｃ１に等しい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が異なるチャネル／周波数を使用し、且つ使用する無線装置も異なる場合、すなわち、その中間のノードＮｉが、ある無線インタフェースを用いてチャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、それとは異なる無線インタフェースを用いてチャネル／周波数ｆＬｉ＋１≠ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）は、ｄ１に等しい。ａ１、ｂ１、ｃ１およびｄ１は、システム設計者が予め決定することができる設計パラメータである。例えば、ａ１＝１、ｂ１＝２、ｃ１＝１．５およびｄ１＝１である。連続する複数のリンクで同じチャネル／周波数および同じ無線装置を使用するパスには、連続する複数のリンクで異なるチャネル／周波数および異なる無線装置を使用するパスよりも高い重み／コストが与えられる。
【００３４】
同様に、α２（ｆＬｉ、ｆＬｉ＋１）も、以下のようないくつかの形態をとることができる。
【００３５】
【数１５】
2010518745.tif 000017
これは、伝送に割り当てられたチャネルについて全てのリンクが等しく重み付けされている場合である。
【００３６】
【数１６】
2010518745.tif 000018
この場合は、パス上のＬａｓｔＬｉｎｋ、すなわち宛先がデータを受信するリンクについては、ＣＣＷ関数α２（ｆＬｉ、ｆＬｉ＋１）はａ２に等しい。宛先ノードは、それ以上データを転送しないことに留意されたい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が同じチャネル／周波数を使用する場合、すなわち、その中間のノードＮｉが、チャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、チャネル／周波数ｆＬｉ＋１＝ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α２（ｆＬｉ、ｆＬｉ＋１）は、ｂ２に等しい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が異なるチャネル／周波数を使用するが、使用する無線装置は同じである場合、すなわち、その中間のノードＮｉが、ある無線インタフェースを用いてチャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、同じ無線インタフェースを用いてチャネル／周波数ｆＬｉ＋１≠ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α２（ｆＬｉ、ｆＬｉ＋１）は、ｃ２に等しい。パス上の連続する２つのリンクＬｉおよびＬｉ＋１が異なるチャネル／周波数を使用し、且つ使用する無線装置も異なる場合、すなわち、その中間のノードＮｉが、ある無線インタフェースを用いてチャネル／周波数ｆＬｉを有するリンクＬｉからデータを受信し、それとは異なる無線インタフェースを用いてチャネル／周波数ｆＬｉ＋１≠ｆＬｉを有するリンクＬｉ＋１によってデータを転送／伝送する場合には、ＣＣＷ関数α２（ｆＬｉ、ｆＬｉ＋１）は、ｄ２に等しい。ａ２、ｂ２、ｃ１およびｄ１は、システム設計者が予め決定することができる設計パラメータである。例えば、ａ２＝０、ｂ２＝５、ｃ２＝３、およびｄ２＝０である。連続する複数のリンクで同じチャネル／周波数および同じ無線装置を使用するパス／経路には、連続する複数のリンクで異なるチャネル／周波数および異なる無線装置を使用するパス／経路よりも高い重み／コストが与えられる。
【００３７】
ＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）およびα２（ｆＬｉ、ｆＬｉ＋１）は、上記の形態に限定されないことに留意されたい。これらの関数は、その他の形態をとることもできる。
【００３８】
パス／経路メトリックのＣＣＷ関数α１（ｆＬｉ、ｆＬｉ＋１）およびα２（ｆＬｉ、ｆＬｉ＋１）は、マルチラジオ、マルチチャネルがネットワークの容量、フロー間干渉およびフロー内干渉に与える影響を捕らえる。本発明のパス／経路選択方法では、異なるチャネルを使用し、且つ複数の無線装置を使用するパス／経路が優先される。単一の無線装置および単一のチャネルというケースは、本発明のマルチラジオおよびマルチチャネルの特殊なケースである。
【００３９】
図１は、本発明の原理による双方向終端間経路を確立する方法を示す流れ図である。１０５で、上述のリンク・コスト関数を計算する。１１０で、この計算の結果を使用して、量子化リンク・コスト関数を計算する。１１５で、これら複数の量子化リンク・コストを使用して、経路の量子化コストを計算する。１２０で、これら複数の経路の計算したコストに基づいて、データが無線ネットワークを横断するための最良の双方向終端間経路を選択する。
【００４０】
図２は、本発明のリンク・コスト関数の計算を示す流れ図である。２０５で、媒体アクセス制御レイヤおよび物理レイヤのプロトコル・オーバヘッドを決定する。２１０で、パケット／フレーム（データ）のサイズを決定する。２１５で、リンク・データ・レートを定期的に測定する。２２０で、パケット／フレーム・エラー率を定期的に測定する。２２５で、チャネル利用率の重み関数を決定する。すなわち、重み関数は、複数の利用可能な重み関数から選択することができ、特定のリンクのリンク・コスト関数の計算に適用される重みを決定する。次いで、２３０で、パケット／フレーム・エラー率の重み関数を決定する。ここでも、重み関数は、複数の利用可能な重み関数から選択することができ、特定のリンクのリンク・コスト関数の計算に適用される重みを決定する。
【００４１】
図３は、本発明のチャネル利用率の重み関数の決定を示す流れ図である。３０５で、チャネル利用率を定期的に推定する。
【００４２】
図４は、本発明のチャネル推定を示す流れ図である。４０５で、チャネル測定期間を決定し、次いで、４１０で、チャネル・ビジー・タイムを定期的に測定する。これらの決定および測定の結果を使用して、チャネル利用率を定期的に推定する。
【００４３】
図５は、本発明の量子化リンク・コスト関数の計算を示す流れ図である。５０５で、量子化レベルの数を決定し、５１０で、量子化因子を決定する。５１５で、これら両方の値を使用して、量子化リンク・コスト関数を計算する。
【００４４】
図６は、本発明の経路のコストの計算を示す流れ図である。６０５で、第１のチャネル変更重み関数を決定し、６１０で、第２のチャネル変更重み関数を決定する。経路のコストの計算では、これら両方の値を使用する。
【００４５】
本発明のＱＲＡＢＡパス／ルーティング・メトリックは、無線メッシュ・ネットワークのパス／経路の選択に適用することができる。ＱＲＡＢＡルーティング・メトリックは、経路／パスを選択するためのオンデマンド・ルーティング・プロトコルやプロアクティブ・ルーティング・プロトコル、ハイブリッド・ルーティング・プロトコルなどのルーティング・プロトコル／アルゴリズムの設計に組み込むことができる。ソース・ノード／メッシュ・ポイントと宛先ノード／メッシュ・ポイントの間で、複数のパスのなかから、ＱＲＡＢＡの値が最小となるパス／経路を選択する。ＱＲＡＢＡの値が同じ最小値となるパス／経路が複数存在する場合には、ホップ数が最小となるパスを選択する。
【００４６】
図７を参照すると、本発明の理解を助ける例示的なメッシュ・ネットワークが示してある。例えば、ノードＡからノードＣまでのパスは、リンクＡＢ、ＢＣ、および中間ノードＢから構成される。
【００４７】
例えば、ＱＲＡＢＡパス・メトリックが、最適化リンク状態ルーティング（ＯＬＳＲ）プロトコルやオープン最短パス・ファースト（ＯＳＰＦ）プロトコルなどのプロアクティブ・リンク状態ルーティング・プロトコルに組み込まれる場合には、メッシュ・ネットワーク内の各リンクのＱＲＡＢＡリンク・コストを推定する必要がある。メッシュ・ネットワーク内のノードは、それが隣接する各ノードのＱＲＡＢＡリンク・コストをローカルに推定し、そのＱＲＡＢＡコストと、隣接する各ノードまでのリンクのチャネル／周波数とを、ルーティング制御メッセージのリンク状態情報の一部としてネットワーク内のその他のノードに通知する。各ノードは、ルーティング／転送テーブルを保持しており、この表によって、ネットワーク中のその他のノードに宛てられたパケットまたはフレームの形態のデータを転送することができる。ルーティング／転送テーブルは、各ノードが生成してキャッシュしているリンク状態情報に基づいて生成され、更新される。本発明のＱＲＡＢＡをパス・メトリックとして使用して、ノードは、上記式（６）によって宛先までの経路／パスを計算する。図７に示す例では、ノードＡは、宛先Ｃまで２本のパスＡ−Ｂ−ＣおよびＡ−Ｄ−Ｅ−Ｆ−Ｃを有する。リンクＢＣの品質が極めて低く、且つ／またはリンクＢＣの負荷が極めて高く、且つ／またはリンクＢＣの利用可能帯域幅が極めて小さく、且つ／またはリンクＡＢおよび  リンクＢＣに同じチャネル／周波数が割り当てられていると、パスＡ−Ｂ−ＣのＱＲＡＢＡコストは、パスＡ−Ｄ−Ｅ−Ｆ−ＣのＱＲＡＢＡコストより大きくなる。パスＡ−Ｂ−Ｃの方がパスＡ−Ｄ−Ｅ−Ｆ−Ｃよりホップ数が少なくても、ノードＡは、ノードＣ宛てのパケットまたはフレームの形態のデータを転送するのにパスＡ−Ｄ−Ｅ−Ｆ−Ｃを選択することになる。ノードＡのルーティング・テーブルでは、宛先Ｃに向かうための次のホップはノードＢではなくノードＤとなる。
【００４８】
別の例では、ＱＲＡＢＡパス・メトリックが、アドホック・オンデマンド距離ベクトル（ＡＯＤＶ）プロトコルなどのオンデマンド・ルーティング・プロトコルに組み込まれる。ソース・ノードが何らかの宛先ノードに対してパケットまたはフレームの形態のデータを送信したいと思ったときに、ＱＲＡＢＡパス・コストが最小値となるパスが発見され、作成され、維持される。各ノードは、それが隣接する各ノードまでのＱＲＡＢＡリンク・コストを決定する機構を有しており、各リンクに使用されるチャネル／周波数を動的または静的に知っている。ソース・ノードは、何らかの宛先ノードに対してデータを送信したいが、その宛先までの有効な経路を有していないときには、ネットワーク内の全てのノードに対する経路要求（ＲＲＥＱ）メッセージによるネットワークのフラッディングを行うことにより、経路発見処理を開始する。特に、宛先アドレス、ルーティング・メトリック・フィールド、およびホップ数フィールドがＲＲＥＱメッセージには含まれる。各ノードが、ソース・ノードから送出された同じＲＲＥＱメッセージを複数回受信してもよいことに留意されたい。これらのＲＲＥＱはそれぞれ、ソース・ノードから受信側ノードまで一意的なパスを通る。受信側ノードは、宛先ノードであることもあるし、中間ノードであることもある。中間ノードＮｉがＲＲＥＱを受信した場合には、中間ノードＮｉは、上記式（６）に基づいてメトリック・フィールドを更新する。具体的には、この中間ノードＮｉは、ＲＲＥＱメッセージの受信元のノードとそのノード自体との間の重み付きリンク・コストα１（ｆＬｉ、ｆＬｉ＋１）×ＱＲＡＢＡ（Ｌｉ）＋α２（ｆＬｉ、ｆＬｉ＋１）を、ＲＲＥＱメトリック・フィールドの値に加算する。チャネル変更重み関数α１（ｆＬｉ、ｆＬｉ＋１）およびα２（ｆＬｉ、ｆＬｉ＋１）は、ＲＲＥＱを受信したリンクおよび無線インタフェースのチャネル／周波数、ならびにネットワークにＲＲＥＱを転送（再フラッディング）するリンクおよび無線インタフェースのチャネル／周波数によって決まる。中間ノードは、ソース・ノードまでの逆経路を有していない場合には逆経路を確立し、あるいは、このＲＲＥＱがソース・ノードまでの現行の経路より良好な新経路を表している場合には、ソース・ノードまでの逆経路を更新する。中間ノードは、更新済みのＲＲＥＱを転送（再フラッディング）する。再フラッディングされたＲＲＥＱのメトリック・フィールドは更新済みのメトリックであり、これは、ＲＲＥＱソース・ノードと転送側ノードとの間の経路の累積メトリックを反映している。
【００４９】
宛先ノードは、ＲＲＥＱを受信すると、上記式（６）に基づいてメトリック・フィールドを更新する。宛先ノードは、そのルーティング・テーブル内にソース・ノードまでの経路がない場合には、そのルーティング・テーブル内にソース・ノードまでの逆経路を作成する。宛先ノードは、ＲＲＥＱがソース・ノードまでの現行の逆経路より良好な新経路を提供する場合には、ソース・ノードまでの現行の逆経路を更新する。ソース・ノードまでの逆経路を作成または更新した後で、宛先ノードは、ユニキャスト経路リプライ（ＲＲＥＰ）メッセージをソース・ノードに向かって送信する。特に、ＲＲＥＰメッセージには、メトリック情報を記載するメトリック・フィールドが含まれる。ＲＲＥＰは、中間ノードにおいて、また最終的にはソース・ノードにおいて、宛先ノードまでの転送経路を確立する。ノード（ソース・ノードおよび／または中間ノード）は、同一の宛先ノードについて複数のＲＲＥＰを受信してもよいことに留意されたい。中間ノードは、ＲＲＥＰメッセージを受信すると、上記式（６）に従ってそのルーティング・テーブル中のメトリック情報を更新する。次いで、中間ノードは、宛先ノードまでの経路を有していない場合には、宛先ノードまでの経路を確立し、あるいは、新しいＲＲＥＰが宛先ノードまでの現行の経路より良好な経路を提供する場合には宛先ノードまでの現行の経路を更新する。経路が作成または修正された場合は、中間ノードは、確立された逆経路に沿って、次の上流側ノード（ソースノード側のノード）に対してユニキャストにＲＲＥＰを転送する。ＲＲＥＰのメトリック・フィールドは、更新済みのメトリックであり、これは、転送側ノードから宛先ノードまでの経路の累積メトリックを反映している。ＲＲＥＰが送信された後で、宛先ノードがさらに良好なメトリックを有する別のＲＲＥＱを受信した場合には、宛先は、ソース・ノードまでの経路を更新し、更新した経路に沿ってソース・ノードまでの新しいＲＲＥＰを送信する。このようにして、ソース・ノードと宛先ノードとの間に、最適なＱＲＡＢＡパス・メトリックの値を有する最適な終端間メトリック経路が確立される。代替の実施例では、宛先ノードまでの有効な経路を有する中間ノードは、ユニキャストＲＲＥＰメッセージをソース・ノードに返送することもできる。
【００５０】
本発明のＱＲＡＢＡパス・メトリックは、ツリー・トポロジに基づくマルチホップ無線ネットワークにおけるパスの選択に適用することができる。ＱＲＡＢＡ経路メトリックを、ツリー型ルーティング・プロトコル／アルゴリズムの設計に組み込んで、ルート・ノードをルートとするトポロジ・ツリーを構築し、親およびパスを選択することができる。ノードは、ルートとそのノード自体との間でＱＲＡＢＡの値が最小となる親を選択する。
【００５１】
ルート・ノードは、宛先ノード・アドレス付きのルート通知（ＲＡＮＮ）メッセージまたは特殊な経路要求（ＲＲＥＱ）メッセージを、ネットワーク中の全てのノードに定期的に送信する。特に、ＲＡＮＮおよびＲＲＥＱは、メトリック・フィールドおよびシーケンス番号フィールドを含む。ルートが新しいＲＡＮＮまたはＲＲＥＱを送信すると、メトリック・フィールドは初期化され、シーケンス番号は増大する。ネットワーク中のいかなるノードも、全てのノードに向けた宛先ノード・アドレスを有するＲＡＮＮまたはＲＲＥＱを受信すると、上記式（６）に基づいてメトリック・フィールドを更新する。このノードは、ルート・ノードへのルーティングに関する情報を有していない場合には、ルートへのルーティング／転送情報を作成する。ＲＡＮＮまたはＲＲＥＱの受信元であるノードが、そのルート・ノードの親である。各ノードは、ＲＡＮＮまたはＲＲＥＱメッセージを複数回受信してもよいことに留意されたい。ノードは、ＲＡＮＮまたはＲＲＥＱがルート・ノードまでの現行の経路より良好な新経路を表している場合には、その親と、ルートへのルーティング／転送情報とを更新する。例えば、ノードは、ＲＡＮＮまたはＲＲＥＱがより大きなシーケンス番号を含む場合、あるいはシーケンス番号は現行の経路と同じであるが、ＲＡＮＮまたはＲＲＥＱメッセージがルート・ノードまでの現行の経路より良好なメトリックを提供する場合には、その現行の親と、ルート・ノードへのルーティング／転送情報とを更新する。その親とソース・ノードへのルーティング／転送情報とを作成または更新した後で、ノードは、更新済みのＲＡＮＮまたはＲＲＥＱメッセージをネットワークを介して転送（再フラッディング）する。（１つまたは複数の）ルートおよびの存在および（１つまたは複数の）利用可能なルートへのメトリックについての情報は、ネットワーク中の全てのノードに配布される。ノードは、全てのノードに対する宛先ノード・アドレス付きのＲＡＮＮまたはＲＲＥＱメッセージを受信した後で、あるいはルート・ノードに送信すべきデータを有しており、ルート・ノードまでの双方向パスを必要としているときに、登録（ＲＥＧＳ）または経路リプライ（ＲＲＥＰ）メッセージあるいは経路要求（ＲＲＥＱ）をルート・ノードに送信することができる。ＲＥＧＳ、ＲＲＥＰまたはＲＲＥＱメッセージは、ルート・ノードからこのノードまでの経路を確立／更新する。
【００５２】
図８は、本発明のルーティング・メトリックを使用したノードの詳細を示すブロック図である。このノードは、特に、経路選択モジュール８１５と、リンク品質およびチャネル負荷／利用率測定モジュール８０５と、ルーティング・メトリック計算モジュール８１０と、１つまたは複数の無線通信インタフェース・モジュール８２０ａ、…８２０ｎとから構成される。リンク品質およびチャネル負荷／利用率測定モジュール８０５は、無線通信インタフェース・モジュール８２０ａ、…８２０ｎを介して、隣接する各ノードへのリンク／チャネルの品質および負荷／利用率を定期的に測定する。リンク品質およびチャネル負荷／利用率測定モジュール８０５は、測定結果をルーティング・メトリック計算モジュールに提供し、ルーティング・メトリック計算モジュールは、ルーティング・メトリックを定期的に計算する。ルーティング・メトリックには、リンク・コスト関数、量子化リンク・コスト関数、および量子化経路コスト関数などがある。ノードは複数の隣接ノード、複数の無線インタフェース、ならびに複数の物理／論理チャネルおよびリンクを有することができることに留意されたい。これらのリンク全ての品質および負荷を、測定モジュールによって定期的に測定する必要がある。経路選択モジュールは、ルーティング・プロトコル／アルゴリズムを実行し、データを転送するための経路および無線インタフェースを決定する。また、経路選択モジュールは、無線通信インタフェース・モジュール８２０ａ、…８２０ｎを介してネットワーク中のその他のノードとルーティング制御メッセージを交換する。ノードは、１つまたは複数の無線通信インタフェース、およびその他の通信インタフェースを有することができることに留意されたい。
【００５３】
プロアクティブ・ルーティング・プロトコルでは、リンク状態およびトポロジの変化に対する適度に迅速な応答を実現しながら経路安定性を維持するために、ノードは、最後の通知の値と比較したときのこのリンクのＲＡＢＡメトリックの変化がしきい値を超える場合に限り、ルーティング制御メッセージのフラッディングを行うことによって、リンクの状態の変化を隣接するノードの１つに直ちに通知することができる。すなわち、（ＲＡＢＡ（ｃｕｒｒｅｎｔ）−ＲＡＢＡ（ｌａｓｔ））／ＲＡＢＡ（ｌａｓｔ）×１００％＞Ｔ％である場合に限り、ノードは、直ちにルーティング制御メッセージのフラッディングを行って、リンク状態の変化を通知する。そうでない場合には、経路メトリックの変化は、次の定期通知で通知される。
【００５４】
本発明は、様々な形態のハードウェア、ソフトウェア、ファームウェア、特殊目的プロセッサ、またはそれらの組合せで実施することができることを理解されたい。好ましくは、本発明は、ハードウェアとソフトウェアの組合せで実施される。さらに、ソフトウェアは、プログラム記憶装置に実装されたアプリケーション・プログラムとして実施されることが好ましい。アプリケーション・プログラムは、任意の適当なアーキテクチャを備えるマシンにアップロードし、実行することができる。このマシンは、１つまたは複数の中央処理装置（ＣＰＵ）、ランダム・アクセス・メモリ（ＲＡＭ）および（１つまたは複数の）入出力（Ｉ／Ｏ）インタフェースなどのハードウェアを有するコンピュータ・プラットフォーム上に実装されることが好ましい。コンピュータ・プラットフォームは、オペレーティング・システムおよびマイクロ命令コードも含む。本明細書に記載した様々なプロセスおよび機能は、オペレーティング・システムによって実行されるマイクロ命令コードの一部またはアプリケーション・プログラムの一部（あるいはそれらの組合せ）とすることができる。さらに、追加のデータ記憶装置や印刷装置など、その他の様々な周辺機器をコンピュータ・プラットフォームに接続することもできる。
【００５５】
さらに、添付の図面に示したシステムの構成要素および方法のステップの一部はソフトウェアで実施することが好ましいので、システムの構成要素（またはプロセス・ステップ）の間の実際の接続は、本発明のプログラムの仕方によって様々であってもよいことも理解されたい。本明細書の教示により、当業者なら、上記の、またそれと同様の本発明の実施態様または構成を企図することができるであろう。
【図１】
2010518745.tif 000019
【図２】
2010518745.tif 000020
【図３】
2010518745.tif 000021
【図４】
2010518745.tif 000022
【図５】
2010518745.tif 000023
【図６】
2010518745.tif 000024
【図７】
2010518745.tif 000025
【図８】
2010518745.tif 000026
【手続補正書】
【提出日】平成22年2月5日(2010.2.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データが無線ネットワークを横断するための双方向の終端間経路を確立する方法であって、
リンク・メトリック関数を計算するステップと、
前記リンク・メトリック関数を量子化リンク・メトリック関数に量子化するステップと、
第１のチャネル変更重み関数を決定するステップと、
第２のチャネル変更重み関数を決定するステップと、
前記第１のチャネル変更重み関数および第２のチャネル変更重み関数を使用して、データが前記無線ネットワークを横断するための複数の経路のそれぞれの量子化メトリックを計算するステップと、
前記複数の経路のそれぞれの前記量子化メトリックに基づいて、データが前記無線ネットワークを横断するための前記双方向の終端間経路を選択するステップと、
を含む、前記方法。
【請求項２】
前記無線ネットワークが、プロアクティブ・ネットワーク、オンデマンド・ネットワーク、およびツリー・トポロジに基づくネットワークを含む無線メッシュ・ネットワークである、請求項１に記載の方法。
【請求項３】
前記複数の経路は、異なるチャネルに亘る前記無線ネットワーク中の同じノード・セット内のノード間であり、複数の無線インタフェースを含む、請求項１に記載の方法。
【請求項４】
媒体アクセス制御レイヤおよび物理レイヤのプロトコル・オーバヘッドを決定するステップと、
データ・サイズを決定するステップと、
リンク・データ・レートを定期的に決定するステップと、
パケット・エラー率を定期的に決定するステップと、
チャネル利用率の重み関数を決定するステップと、
前記パケット・エラー率の重み関数を決定するステップと、
をさらに含み、
前記データ・サイズが、所定の定数のデータ・サイズ、平均データ・サイズ、および最大データ・サイズのうちの一つである、請求項１に記載の方法。
【請求項５】
チャネル利用率を定期的に推定するステップと、
チャネル測定期間を決定するステップと、
チャネル・ビジー・タイムを定期的に決定するステップと、
をさらに含む、請求項４に記載の方法。
【請求項６】
量子化レベルの数を決定するステップと、
量子化因子を決定するステップと、
をさらに含む、請求項１に記載の方法。
【請求項７】
前記無線メッシュ・ネットワークが、プロアクティブ・ネットワークである場合、当該プロアクティブ・ネットワークが、
前記計算したリンク・メトリック関数の結果を、制御メッセージの状態情報として通知するステップと、
前記計算したリンク・メトリック関数を使用して、ルーティング・テーブルを生成し、維持するステップと
前記計算したリンク・メトリック関数の結果が所定のしきい値より大きい場合に、前記結果を制御メッセージの状態情報として直ちに通知するステップと、
をさらに行う、請求項２に記載の方法。
【請求項８】
前記無線メッシュ・ネットワークが、オンデマンド・ネットワークである場合、当該オンデマンド・ネットワークが、
経路発見を初期化するステップと、
前記計算したリンク・メトリック関数を使用して、ルーティング・テーブルを生成し、維持するステップと、
をさらに行う、請求項２に記載の方法。
【請求項９】
前記無線メッシュ・ネットワークが、ツリー・トポロジに基づく場合、当該ツリー・トポロジに基づく前記ネットワークが、
初期化されたメトリック・フィールドおよびシーケンス番号フィールドを含めた、ルート通知の伝送および経路発見の初期化の一方を実行するステップと、
前記メトリック・フィールドを更新するステップと、
前記シーケンス番号フィールドを更新するステップと、
ルーティング・テーブルを更新するステップと、
前記双方向終端間経路を確立するステップと、
をさらに行う、請求項２に記載の方法。
【請求項１０】
データが無線ネットワークを横断するための双方向の終端間経路を確立するシステムであって、
リンク・メトリック関数を計算する手段と、
前記リンク・メトリック関数を量子化する手段と、
第１のチャネル変更重み関数を決定する手段と、
第２のチャネル変更重み関数を決定する手段と、
前記第１のチャネル変更重み関数および第２のチャネル変更重み関数を使用して、データが前記無線ネットワークを横断するための複数の経路のそれぞれの量子化メトリックを計算する手段と、
前記複数の経路のそれぞれの前記量子化メトリックに基づいて、データが前記無線ネットワークを横断するための前記双方向の終端間経路を選択する手段と、
を備える、前記システム。
【請求項１１】
前記無線ネットワークが、プロアクティブ・ネットワーク、オンデマンド・ネットワーク、およびツリー・トポロジに基づくネットワークを含む無線メッシュ・ネットワークである、請求項１０に記載のシステム。
【請求項１２】
前記複数の経路は、異なるチャネルに亘る前記無線ネットワーク中の同じノード・セット内のノード間であり、複数の無線インタフェースを含む、請求項１０に記載のシステム。
【請求項１３】
媒体アクセス制御レイヤおよび物理レイヤのプロトコル・オーバヘッドを決定する手段と、
データ・サイズを決定する手段と、
リンク・データ・レートを定期的に決定する手段と、
パケット・エラー率を定期的に決定する手段と、
チャネル利用率の重み関数を決定する手段と、
前記パケット・エラー率の重み関数を決定する手段と、
をさらに備え、
前記データ・サイズが、所定の定数のデータ・サイズ、平均データ・サイズ、および最大データ・サイズのうちの一つである、請求項１０に記載のシステム。
【請求項１４】
チャネル利用率を定期的に推定する手段と、
チャネル測定期間を決定する手段と、
チャネル・ビジー・タイムを定期的に決定する手段と、
をさらに備える、請求項１３に記載のシステム。
【請求項１５】
量子化レベルの数を決定する手段と、
量子化因子を決定する手段と、
をさらに備える、請求項１０に記載のシステム。
【請求項１６】
前記無線メッシュ・ネットワークが、プロアクティブ・ネットワークである場合、当該プロアクティブ・ネットワークが、
前記計算したリンク・メトリック関数の結果を、制御メッセージの状態情報として通知する手段と、
前記計算したリンク・メトリック関数を使用して、ルーティング・テーブルを生成し、維持する手段と
前記計算したリンク・メトリック関数の結果が所定のしきい値より大きい場合に、前記結果を制御メッセージの状態情報として直ちに通知する手段と、
をさらに備える、請求項１１に記載のシステム。
【請求項１７】
前記無線メッシュ・ネットワークが、オンデマンド・ネットワークである場合、当該オンデマンド・ネットワークが、
経路発見を初期化する手段と、
前記計算したリンク・メトリック関数を使用して、ルーティング・テーブルを生成し、維持する手段と、
をさらに備える、請求項１１に記載のシステム。
【請求項１８】
前記無線メッシュ・ネットワークが、ツリー・トポロジに基づく場合、当該ツリー・トポロジに基づく前記ネットワークが、
初期化されたメトリック・フィールドおよびシーケンス番号フィールドを含めた、ルート通知の伝送および経路発見の初期化の一方を実行する手段と、
前記メトリック・フィールドを更新する手段と、
前記シーケンス番号フィールドを更新する手段と、
ルーティング・テーブルを更新する手段と、
前記双方向終端間経路を確立する手段と、
をさらに備える、請求項１１に記載のシステム。
【請求項１９】
データが無線ネットワークを横断するための双方向の終端間経路の確立に参加するように構成された前記無線ネットワーク中のノードであって、
複数のチャネルをそれぞれ有する前記ノードの各チャネルの品質および利用率を定期的に測定する手段と、
前記各チャネルの前記測定した品質および利用率を使用して、ルーティング・メトリックを定期的に計算する手段と、
前記計算したルーティング・メトリックを用いてルーティング・テーブルを定期的に更新する手段と、
前記ルーティング・テーブルに基づいて、データが前記無線ネットワークを横断するための前記双方向終端間経路を選択する手段と、
を備え、
当該ノードが少なくとも一つの無線ネットワークを有する、前記ノード。
【国際調査報告】
2010518745.tif 000027
2010518745.tif 000028
2010518745.tif 000029
2010518745.tif 000030