(57)【要約】予測機構及び可変重み付けフィルタを用いてノード間のリンク信頼度を推定するリンク信頼度アルゴリズムを用いることにより、通信ネットワーク、特に無線アドホック通信ネットワークにおいて、発信元ノードと宛先ノードとの間の最適経路を特定するためのシステム及び方法に関する。この予測は、信号強度若しくは信号対雑音比、又はリンク品質を表すと見なされる、物理層にて収集される任意の統計量に基づくことが可能である。重み付けフィルタは、リンク品質が推定されるノードにより経験されているトラフィック状況（例えば、アイドル、軽度トラフィック、中程度トラフィック又は重度トラフィック）に基づき、予測される値を調整する。
2006527525.tif 000002
【特許請求の範囲】
【請求項１】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を特定するための方法であって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別する信頼度推定工程と、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィック状況に基づき、予測される値を調整することと、
信頼度推定工程において決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択する経路選択工程とからなる方法。
【請求項２】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項１に記載の方法。
【請求項３】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項３に記載の方法。
【請求項４】
発信元ノード及び宛先ノードは移動体ノードである請求項１に記載の方法。
【請求項５】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項１に記載の方法。
【請求項６】
信頼度推定工程は以下の方程式に基づきリンク信頼度を推定する請求項１に記載の方法。
【数１】
2006527525.tif 000008
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項７】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項１に記載の方法。
【請求項８】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を発信元ノードが特定するように制御するための命令を含むコンピュータ可読媒体であって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別する命令の第１の組と、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィック状況に基づき、予測される値を調整することと、
命令の第１の組において決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択する命令の第２の組とを含むコンピュータ可読媒体。
【請求項９】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項７に記載のコンピュータ可読媒体。
【請求項１０】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項８に記載のコンピュータ可読媒体。
【請求項１１】
発信元ノード及び宛先ノードは移動体ノードである請求項７に記載のコンピュータ可読媒体。
【請求項１２】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項７に記載のコンピュータ可読媒体。
【請求項１３】
命令の第１の組は以下の方程式に基づきリンク信頼度を推定する請求項７に記載のコンピュータ可読媒体。
【数２】
2006527525.tif 000009
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項１４】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項１に記載のコンピュータ可読媒体。
【請求項１５】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて自身と宛先ノードとの間の最適経路を特定するノードであって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別することと、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィック状況に基づき、予測される値を調整することと、
信頼度を推定することにより決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択することとを含むコントローラを含むノード。
【請求項１６】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項１３に記載のノード。
【請求項１７】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項１４に記載のノード。
【請求項１８】
発信元ノード及び宛先ノードは移動体ノードである請求項１３に記載のノード。
【請求項１９】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項１３に記載のノード。
【請求項２０】
コントローラは以下の方程式に基づきリンク信頼度を推定する請求項１に記載のノード。
【数３】
2006527525.tif 000010
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項２１】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項１に記載のノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク、特に無線アドホック通信ネットワークにおいて、発信元ノードと宛先ノードとの間の最適経路を特定するためのシステム及び方法に関する。より詳細には、本発明は、帰納的にパケット完了率を推定することにより、通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を識別するためのシステム及び方法に関する。
【背景技術】
【０００２】
移動体無線電話ネットワーク等の無線通信ネットワークは、この十年を通じて次第に普及つつある。それらの無線通信ネットワークにおいては、「セル」と呼ばれる複数の領域にサービス域を分割するようにネットワークのインフラ（ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）が構成されているため、それらの無線通信ネットワークは一般に「セルラー・ネットワーク」と称される。地上セルラー・ネットワークには、複数の相互接続された基地局、即ち基地ノードが含まれる。基地ノードは、サービス域全体を通じて所定の位置に地理的に分配されている。各基地ノードは、カバレッジ域内に位置する無線電話機等の移動体ユーザ・ノードに対し無線周波数（ＲＦ）通信信号等の電磁信号の受発信を行うことが可能な、１つ以上のトランシーバを備える。通信信号には、例えば、所望の変調手法に従って変調されデータパケットとして発信される、音声データが含まれる。当業者には認められ得るように、時分割多元接続（ＴＤＭＡ）形式、符号分割多元接続（ＣＤＭＡ）形式又は周波数分割多元接続（ＦＤＭＡ）形式等の多重化形式にてネットワーク・ノードがデータパケット通信の受発信を行うことにより、第１のノードの１つのトランシーバが、カバレッジ域の幾つかの他のノードと同時に通信することが可能である。
【０００３】
近年では、「アドホック（ａｄ−ｈｏｃ）」ネットワークとして周知の種類の移動体通信ネットワークが開発されている。この種類のネットワークにおいては、各移動体ノードは他の移動体ノードに対する基地局又はルータ（ｒｏｕｔｅｒ）として動作することが可能であるため、固定インフラの基地局の必要が除かれる。アドホック・ネットワークに関する詳細は、メイヤー（Ｍａｙｏｒ）による特許文献１に述べられている。その全内容を引用により本明細書に援用する。
【０００４】
より洗練されたアドホック・ネットワークも開発されている。このアドホック・ネットワークでは、従来のアドホック・ネットワークにおけるように移動体ノードの相互通信が可能であることに加え、移動体ノードが固定ネットワークへアクセスすることも可能であるため、公衆交換電話網（ＰＳＴＮ）上、及びインターネット等、他のネットワーク上の他の移動体ノードと通信することが可能となる。それらの高度な種類のアドホック・ネットワークに関する詳細は、「ＰＳＴＮ及びセルラー・ネットワークとインタフェースするアドホック・ピアツーピア移動体無線接続システム（Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks ）」と題された２００１年６月２９日出願の特許文献２、「別個の予約チャネルを備えた共有パラレル・データ・チャネルへの協調チャネル接続を有するアドホック・ピアツーピア無線ネットワークにおける時分割プロトコル（Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel）」と題された２００１年３月２２日出願の特許文献３、及び「アドホック・ピアツーピア移動体無線接続システムにおける優先付け経路制御（Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System ）」と題された２００１年３月２２日出願の特許文献４に記載されている。それらの各々の全内容を引用により本明細書に援用する。
【０００５】
当業者には認められ得るように、アドホック・ネットワークのうちの一部のノードは移動体であるため、ネットワークにおいてそれらのノードとの接続性が保持される必要がある。発信されたデータパケットは、通常、最終の宛先に到達するまで移動体デバイスから移動体デバイスへと「ホップ（ｈｏｐ）」し、伝送のパス（ｐａｔｈ）、すなわち経路を生成する。しかしながら、多くの場合、移動体デバイス間の伝送パスはデバイスの移動に従って変化し易いため、アドホック・ネットワーク通信は、個々の移動体デバイスの限定された能力及び容量に対処しつつ最適性能を達成することが可能である必要がある。
【０００６】
通常の無線通信ネットワークにおいては、発信元と宛先との間のホップ数が経路制御メトリックとして用いられ、通常、より小さいホップ数の経路が、より好適な経路である。しかしながら、より大きいホップ数を有するものの、より良好なリンク品質又はデータレートを有する、より良好な経路が存在し得るので、このことにより、非最適経路を選択することが起こり得る。
【０００７】
経路制御プロトコルの種類の例は、特許文献５及び米国特許仮出願第６０／４７６，２３７号明細書に記載されている。それらの全内容を引用により本明細書に援用する。それらの手法では、各ノードは宛先ノードへの経路メトリックを計算し、存在する場合には代替の経路を用いる。その目的は、最小のメトリックを有する経路を選択することにより最も良好な経路を選択することである。
【０００８】
特許文献５の記載においては、メトリックは単純にホップ数である。しかしながら、米国特許仮出願第６０／４７６，２３７号明細書の記載においては、メトリックは、信号強度に基づく「リンク信頼度（ｌｉｎｋ  ｒｅｌｉａｂｉｌｉｔｙ）」計算に依存する、より複雑な値である。このアルゴリズムでは、各ホップ毎に「１」を加算するのではなく、リンクが最大限の性能のまで用いられない場合、より大きい整数値（例えば、２０）を加算するため、「リンク信頼度」はより洗練された経路制御メトリックの構成要素である。したがって、各ノードは最も良好な無線リンクに対して最小の整数値（例えば、１）を割り当て、例えば、マルチパス、フェージング、輻輳、距離、シャドーイング、干渉等のために無線リンクの品質が低下している場合、より大きい整数値（例えば、２０）を割り当てる。リンク品質を決定するための手法の他の例は、特許文献６及び特許文献７に述べられている。それらの全内容を引用により本明細書に援用する。
【０００９】
上述の米国特許仮出願明細書に記載の手法は、無線アドホック・ピアツーピア・ネットワークを含む多くの無線ネットワークに対し適切であるが、主として低コスト広帯域無線からなるネットワークにおいて用いられる時、それらの手法の一定の欠点が明らかとなる場合がある。例えば、通常の無線チャネルにおいて発生するような散発性のトラフィック・エラー（静的マルチパス等）においては、信号強度及び信号対雑音比は影響を受けないため、通常、リンク信頼度が調整されることはない。また、フェージング・チャネルに関する特定の事例においては、受信機側で発生する信号強度の変動を低コスト広帯域無線が適切に追跡することは不可能である。このことは、部分的には、この測定が無線の感度に依存することにより、また部分的には、受信機が散発性の測定（パケットが受信される時における１つの特定の時点等）を行うことのみが可能であり、実際の信号強度の変動に関して部分的な情報しか得られないことによる。
【特許文献１】米国特許第５，９４３，３２２号明細書。
【特許文献２】米国特許出願第０９／８９７，７９０号明細書。
【特許文献３】米国特許出願第０９／８１５，１５７号明細書。
【特許文献４】米国特許出願第０９／８１５，１６４号明細書。
【特許文献５】米国特許第５，４１２，６５４号明細書。
【特許文献６】米国特許出願公開第２００４／００２２２２３号明細書。
【特許文献７】米国特許第６，５２２，８８１号明細書。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
したがって、ホップ数又は受信した信号の強度以外の係数を唯一のメトリックとして用いる効率的な手法により、通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を発見するためのシステム及び方法の必要が存在する。
【００１１】
本発明の１つの目的は、通信ネットワーク、特に無線アドホック通信ネットワークにおいて、発信元ノードと宛先ノードとの間の最適経路を特定するためのシステム及び方法を提供することである。
【００１２】
本発明の別の目的は、ノード間のホップ数又は出力制御以外の係数を唯一のメトリックとして用い、そのメトリックに基づく最適経路選択により、通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を識別するためのシステム及び方法を提供することである。
【課題を解決するための手段】
【００１３】
それらの目的及び他の目的は、予測機構及び可変重み付けフィルタを用いてノード間のリンク信頼度を推定するリンク信頼度アルゴリズムを用いて、通信ネットワーク、特に無線アドホック通信ネットワークにおいて、発信元ノードと宛先ノードとの間の最適経路を特定するためのシステム及び方法により、実質的に達成される。この予測は、信号強度若しくは信号対雑音比、又はリンク品質を表すと見なされる物理層にて収集される任意の統計量に基づくことが可能である。重み付けフィルタは、リンク品質が推定されるノードにより経験されているトラフィック状況（例えば、アイドル、軽度トラフィック、中程度トラフィック又は重度トラフィック）に基づき、予測される値を調整する。
【発明を実施するための最良の形態】
【００１４】
図１は、本発明の一実施形態を用いるアドホック・パケット交換無線通信ネットワーク１００の一例を示すブロック図である。詳細には、ネットワーク１００は複数の移動体無線ユーザ端末１０２−１〜１０２−ｎ（一般に、ノード１０２又は移動体ノード１０２と称する）を含み、必須ではないが、ノード１０２を固定ネットワーク１０４へ接続するための複数のアクセス・ポイント１０６−１，１０６−２，．．．１０６−ｎ（一般に、ノード１０６又はアクセス・ポイント１０６と称する）を有する固定ネットワーク１０４を含み得る。固定ネットワーク１０４は、例えば、中核ローカル・エリア・ネットワーク（ＬＡＮ）と、他のアドホック・ネットワーク、公衆交換電話網（ＰＳＴＮ）及びインターネット等、ネットワーク・ノードを他のネットワークへ接続するための複数のサーバ及びゲートウェイ・ルータとを含み得る。ネットワーク１００はさらに、他のノード１０２，１０６又は１０７の間においてデータ・パケットを経路制御するための複数の固定ルータ１０７−１〜１０７−ｎ（一般に、ノード１０７又は固定ルータ１０７と称する）を含み得る。なお、説明のため、上述のノードを集合的に「ノード１０２，１０６，１０７」又は単に「ノード」と称する場合がある。
【００１５】
当業者には、上述のメイヤーによる特許文献１、並びに特許文献２、特許文献３及び特許文献４の記載のように、ノード１０２，１０６，１０７は直接的に相互に通信可能であるか、又は、ノード間にて送信されるパケットに対するルータとして動作する１つ以上の他のノード１０２，１０６又は１０７を介して、相互に通信可能であることが認められ得る。
【００１６】
図２に示すように、各ノード１０２，１０６，１０７はトランシーバ、即ちモデム１０８を備える。このトランシーバはアンテナ１１０に接続されており、コントローラ１１２の制御の下で、ノード１０２，１０６又は１０７に対し、パケット化された信号等の信号の受発信を行うことが可能である。パケット化されたデータ信号は、例えば、音声データ又はマルチメディア情報と、ノード更新情報を含むパケット化された制御信号とを含む。
【００１７】
各ノード１０２，１０６，１０７はさらに、特に、自身及びネットワーク１００における他のノードに関する経路制御情報等を記憶することが可能である、ランダム・アクセス・メモリ（ＲＡＭ）等のメモリ１１４を備える。さらに図２に示すように、一部のノード、特に移動体ノード１０２は、ノートブック・コンピュータ端末、移動体電話装置、移動体データ装置又は任意の他の適切なデバイス等、任意数のデバイスからなってよいホスト１１６を備えることが可能である。当業者には容易に認められ得る目的により、各ノード１０２，１０６，１０７は、インターネット・プロトコル（ＩＰ）及びアドレス解決プロトコル（ＡＲＰ）を実行するための適切なハードウェア及びソフトウェアも備える。伝送制御プロトコル（ＴＣＰ）及びユーザ・データグラム・プロトコル（ＵＤＰ）を実行するための適切なハードウェア及びソフトウェアを備えてもよい。
【００１８】
上述の背景技術において説明したように、ネットワーク性能を最適化するために、相互間のデータ・パケットの送信に介する最適リンクをノードが選択することを可能とする手法を開発した。そのような手法においては、信号強度に基づきリンク信頼度が推定される。残念なことに、信号強度により必ずしもリンク信頼度の正確な尺度が与えられる訳ではないのは上述の通りである。以下で述べる本発明の一実施形態による手法は従来の手法よりも汎用的であり、実質的に任意の無線技術に対し適用可能である（即ち、「無線に依存しない（ｒａｄｉｏ  ａｇｎｏｓｔｉｃ）」）。リンク信頼度により、複数の無線技術にて、且つ場合によっては同時に動作することが必要とされ得る経路制御プロトコルにおいて用いられる最も良好なメトリックが決定されるので、この性能は有利且つ重要である。
【００１９】
当業者には認められ得るように、隣接するノードに対するリンク信頼度は、隣接するノードによりパケットが成功裏に受信される確率の尺度である。リンク信頼度は、例えば、受信した信号の強度又は受信したデータ・パケットの信号対雑音比を用いることにより予測され得る。このことは、隣接するノードに対し有効な通信が存在しない場合、特に有用である。ＭＡＣ情報を用いることによりリンク信頼度を測定することも可能であるが、適切な精度で達成され得るのは、通常、隣接するノードに対し有効な通信リンクが存在する場合のみである。
【００２０】
本発明の一実施形態によるリンク信頼度推定アルゴリズムの構成要素は、予測機構及び可変重み付けフィルタを含む。この予測は、信号強度若しくは信号対雑音比、又はリンク品質を表すと見なされる、物理層にて収集される任意の統計量に基づくことが可能である。特定のノードに対し確立されたリンクが存在しない時、及びそのノードに関する情報を受信することが可能である時、この予測が実行される必要がある。このことは、他のノードへ宛てられたパケットの受動的リスニング（ｐａｓｓｉｖｅ  ｌｉｓｔｅｎｉｎｇ）により、又は上述の米国特許仮出願第６０／４７６，２３７号明細書に記載の予約チャネル上で送信される「ハロー（ｈｅｌｌｏ）」メッセージ等の特別な広告／認知パケットの能動的受信（ａｃｔｉｖｅ  ｒｅｃｅｐｔｉｏｎ）により、達成され得る。
【００２１】
この発明の目的は、可変重み付けフィルタを用いることにより、帰納的にパケット完了率（ｐａｃｋｅｔ  ｃｏｍｐｌｅｔｉｏｎ  ｒａｔｅ）を測定することである。パケットは不規則な間隔にて受発信されるので、適切なフィルタリングを実行するには、実際の時間の刻み（ｓｔｅｐ）に対し忘却係数を調整することが必要である（固定重み付けフィルタの実装においては時間刻みが不変であることが仮定される）。さもなければ、高トラフィック状況においてはシステムの収束が早過ぎ、中程度トラフィック状況においては遅過ぎることになる。この新規なアプローチにおいては、リンク信頼度計算機構の収束率は時間に対して標準化される、即ち、本来的に予測不能、且つカオス的である、トランシーバが送信するトラフィックの種類及び量から独立である（トランシーバはトランシーバに用いられているアプリケーションに関する認識を有しない）。特に、パケット完了率の決定は、一定の程度まで時間間隔から独立である。過去のパケット量「ｘ」のパケットを調査し、成功数及び失敗数を計数し、それらの数からパケット完了率を導出することはより容易であり得るが、過去のトランザクション数「ｘ」のトランザクションの全てからなるメモリが必要であるため、その方法は非効率的である。また、その方法は、過去のトランザクション数「ｘ」のトランザクションが最後の１時間に発生したのか、又は最後の１ミリ秒間に発生したのかを認識しないため、時間の観点から不正確である。したがって本発明は、それらの２つの問題、即ち、計算効率及び時間に対する疑似独立性に対処する。
【００２２】
リンク信頼度計算は、以下の方程式１に従って実行される。ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である。
【００２３】
【数１】
2006527525.tif 000003
方程式１に記載のフィルタの出力は、入力（Ｘ（ｔ０））の平均へと収束する。したがって、各失敗伝送に対するフィルタの入力は０、且つ各成功伝送に対しては１の場合、一定数の反復の後、フィルタの出力は成功裏に発信されたパケットの数と、発信されたパケットの数との比へと収束する。定義により、この比がパケット完了率である。
【００２４】
プログラムの簡便さのため、以下で述べる図５ａ，５ｂに示す値等、有限個の値に忘却係数を量子化することにより、マイクロプロセッサにおける固定小数点の実装を可能とする。なお、Ｘ（ｔ０）は予測であり、ＬＲ（ｔ０）は、時間ｔ０において経路制御アルゴリズムがリンク信頼度を照合するために用いる値である。状況の変化に従って特定のリンクに対するパケット完了率が変化する場合、それに従い、その特定のリンクに関する経路制御アルゴリズムの情報が調整される。「前のリンク信頼度（ｐｒｅｖｉｏｕｓ  ｌｉｎｋ  ｒｅｌｉａｂｉｌｉｔｙ）」の値は、アルゴリズムの前の繰り返しにおいて計算された値である。開始時（即ち、新たなリンクが確立される時）には、アルゴリズムに対して初期値を導入することが必要である。控えめな（ｃｏｎｓｅｒｖａｔｉｖｅ）推定においては、この初期値は０（即ち、パケット完了率０％）であり得る。よりプロアクティブ（ｐｒｏａｃｔｉｖｅ）な結果においては、この初期値は５０％に設定され得る。初期値はアルゴリズムの収束には全く影響を与えない。初期値は、経路制御アルゴリズムがリンク信頼度を解釈する手法に基づき選択される必要がある。初期化された新たなリンクに関する充分な情報を別の確立されたリンクが集積しているため、別の確立されたリンクを経路制御アルゴリズムに破棄させないような初期値を選択することが賢明である。初期化に続く各繰り返しにおいては、「前のリンク信頼度」が前の繰り返しにおける出力（「現在のリンク信頼度（ｃｕｒｒｅｎｔ  ｌｉｎｋ  ｒｅｌｉａｂｉｌｉｔｙ）」）である。
【００２５】
なお、ネットワーク構築者は、種々のデータレートにおける感度、移動体性能等、一定の無線特性値に基づき、「予測される値（ｐｒｅｄｉｃｔｅｄ  ｖａｌｕｅ）」に対する方程式を決定する必要がある。メッシュネットワークス社（ＭｅｓｈＮｅｔｗｏｒｋｓ）のｍｅａ（商標）システムの予測において用いられる方程式は、２つの要素を有する。即ち、アイドル動作における控えめな予測と、有効通信リンクにおけるプロアクティブな予測とである。発信出力の観点からリンクは対称であると仮定すると、いずれの予測もパケットに関して受信した信号の強度に基づく。発信出力の観点からリンクが非対称である場合、用いられる「受信した信号の強度（ｒｅｃｅｉｖｅｄ  ｓｉｇｎａｌ  ｓｔｒｅｎｇｔｈ）」が受信機により測定されたものであることを保証することが重要である。
【００２６】
以下の方程式は、予測の値に対する方程式の例を表す。
【００２７】
【数２】
2006527525.tif 000004
図３は、方程式２，３のグラフ表現である。なお、「プロアクティブな予測」機構は、完全に随意である。送信されているトラフィックが存在すると、各リンクの信頼度に基づきアルゴリズムは接続性を保持する。信号強度をプロアクティブな予測の値に変換することのさらなる利点は、より長範囲にあるリンクに対し、アルゴリズムがより小さいペナルティを適用することである。そのようなペナルティを適用する機構が常に存在する場合（エネルギー認知経路制御アルゴリズム等）、方程式１のリンク信頼度予測は全てのデータ・パケットに対してＬＲ＝１００に設定される（ハロー・メッセージに対する予測は影響を受けないままである）。
【００２８】
可変の忘却係数は、以下の３つの動作状況等、種々の動作状況を含むように選択される。
アイドル動作：装置は「広告／認知（ａｄｖｅｒｔｉｓｍｅｎｔ／ａｗａｒｅｎｅｓｓ）」メッセージのみを受信する。平均到達時間間隔は、通常、５００ｍｓより大きい。
軽トラフィック：装置は小量のデータを発信する。平均到達時間間隔は、通常、２００ｍｓ〜５００ｍｓである。
中程度トラフィック：装置は中程度の量のデータを発信する。平均到達時間間隔は、通常、１００ｍｓ〜２００ｍｓである。
重度トラフィック：装置は大量のデータを発信する。平均到達時間間隔は、通常、１００ｍｓ未満である。
【００２９】
各伝送間の時間を計算することにより、それに従ってノード１０２，１０６又は１０７のトランシーバ１０８が忘却係数を選択し、方程式１に従って新たなリンク信頼度を計算することが可能である。このことを図４のブロック図に示す。詳細には、Ｘ（ｔ０）はフィルタへの入力である。トランシーバ１０８は、各失敗伝送においてはＸ（ｔ０）に対し０を割り当て、各成功伝送、又は広告／認知パケットの受信成功においてはＸ（ｔ０）に対し予測値を割り当てることにより、別のノードに対するリンク信頼度推定を更新する。この予測値はプラットフォームに依存しており、任意の物理層の実装に対し一般化することは不可能である。この予測値は、無線の性能が部分的に依存する信号強度、ＳＮＲ又は利用可能な任意の他の関連統計量等、物理層のパラメータに依存する。したがって、成功裏に動作しないことをシステム設計者が認識している無線に対する弱い信号強度又はＳＮＲにおいては、予測値は一様に小さい（０に近い）。同様に、成功裏に動作することをシステム設計者が認識している無線に対する強い信号強度又はＳＮＲにおいては、予測値はリンク信頼度に対し割り当てられた範囲における最大値（例えば、１００％を表す１００）に設定される。続いて、割り当てられた範囲、例えば０〜１００のリンク信頼度の値へ信号強度又はＳＮＲを変換する、値の参照用テーブルが、システム設計者により確立され得る。この参照用テーブルは物理層の情報のみを用いるので、実際のリンクの成功の程度を示すことはないが、無線アドホック・ネットワークにおける移動体ノードの適切な動作に不可欠な予測を実行する。
【００３０】
図５ａには、量子化されたλ（Δｔ／ΔＴ）の組を示し（ここで、λ＝（２６−１）／２６であり、Δｔは８５ｍｓに等しい）、図５ｂには、先述の４つの動作状況（即ち、アイドル動作（制御チャネル）、低トラフィック、中程度トラフィック、重度トラフィック）に対する可変重み付けフィルタの応答を示す。これらの図から認められ得るように、「制御チャネル（Ｃｏｎｔｒｏｌ  Ｃｈａｎｎｅｌ）」トラフィックのシナリオ等、より遅いトラフィック負荷においては、収束率が他よりも小さい（例えば、初期状態「１」に対し入力として５つの「０」を用いた後に値が「０．５」に到達する）。アルゴリズムは、各繰り返しにおいて収束率を調整することにより、収束時間を不変に保持することを試みる。実際、パケット間の到達時間間隔が大きい場合には、パケット当たりの収束率は速くなる必要がある。同様に、パケット間の到達時間間隔が小さい場合、パケット当たりの収束率は遅くなる必要がある。
【００３１】
λ（Δｔ／ΔＴ）に対する値は、プログラムの簡便さのために量子化される。到達時間間隔が決定されると、前のリンク信頼度の値ＬＲ（ｔ−１）に対し、値が加算又は減算される。ＬＲ（ｔ−１）の値は、λ（Δｔ／ΔＴ）・Ｘ（ｔ０）である。当業者には認められ得るように、特に、λ（Δｔ／ΔＴ）が０より大きく且つ１未満の実数であるため、そのような乗算を固定小数点プロセッサにおいて達成することは困難であり得る。λ（Δｔ／ΔＴ）が２の累乗の逆数として表現され得る場合、この乗算は単純な右ビット・シフト演算となる。特定のλ（Δｔ／ΔＴ）に相当する２の累乗の指数がＮの場合、以下となる。
【００３２】
【数３】
2006527525.tif 000005
この例を用いて量子化したλ（Δｔ／ΔＴ）の値を以下の表に示す。
【００３３】
【表１】
2006527525.tif 000006
したがって、リンク信頼度計算は、アイドル動作（５００ｍｓより大きいΔｔに相当）においてはＮ＝３、軽度トラフィック（２００ｍｓ〜５００ｍｓのΔｔに相当）においてはＮ＝４、中程度トラフィック（１００ｍｓ〜２００ｍｓのΔｔに相当）においてはＮ＝５、重度トラフィック（１００ｍｓ未満のΔｔに相当）においてはＮ＝６を用いて実行される。
【００３４】
以下は、予測モデルと可変重み付けフィルタとの組み合わせにより、無線アドホック・ネットワーク１００において移動体ノード（例えば、ノード１０２）が最適経路を確立する手法に関する説明である。
【００３５】
以下のシナリオにおけるリンク信頼度推定は臨界的である。第１はリンクが確立される時、第２はリンクが切断される時である。それらの事象は以下の状況において発生し得る。即ち、第１は特定の隣接ノード内に存在中、第２は隣接ノードの離脱中である。起こり得る事例を以下のテーブル１に要約する。
【００３６】
【表２】
2006527525.tif 000007
各事例のシナリオを、以下でより詳細に説明する。
【００３７】
「隣接ノード進入」
説明：トランシーバが別の装置の範囲内に進入する。即ち、移動体ノード１０２が、例えば、別のノード１０２，１０６又は１０７の範囲へ進入する時。
目的：リンク信頼度推定アルゴリズムは、いずれのリンクが現在用いられているリンクより好適であるかを迅速に示すことが可能である必要がある。
機構：広告／認知パケットを処理する時、リンク信頼度推定アルゴリズムは、受信したパケットの信号強度又はＳＮＲのみを用いて予測を行う。
【００３８】
「隣接ノード退出」
説明：トランシーバが範囲外となる。
目的：リンク信頼度推定アルゴリズムは、リンクの品質が低下することを故障が起きる以前に予測することが可能である必要がある。この機能は、「メイク・ビフォア・ブレーク（ｍａｋｅ−ｂｅｆｏｒｅ−ｂｒｅａｋ）」と称される、より一般的な機構の一部である。
機構：リンク信頼度推定アルゴリズムはパケットの信号強度を用いて予測を行い、それに従ってリンク信頼度の値を低下させる。この低下は、失敗したパケット伝送により生じる低下に加えて行われる。したがって、より好適な予測を有する他の利用可能なリンクを優先させるため、自発的にこのリンクの信頼度が過小推定される。
【００３９】
「リンク調整」
説明：宛先ノードは充分に範囲内に存在するが、パケット完了率は低下する。このことはフェージング、即ち、監視の一時的な実行不能、又は干渉の存在により引き起こされる場合がある。
目的：リンク信頼度推定アルゴリズムは、干渉及びシャドーイング等、実際のチャネル状況に対し迅速に調整することが可能である必要がある。この機構によりリンク信頼度推定アルゴリズムは経路制御プロトコルに故障を示す。
機構：リンク信頼度推定アルゴリズムはリンク信頼度を調整し、実時間において各宛先ノードに対するパケット完了率を一致させる。
【００４０】
「リンク故障メモリ」
説明：リンクが切断されているが、依然としてノードは範囲内に存在する。
目的：リンク信頼度推定アルゴリズムは、経路制御の不安定性を回避するため、リンク故障のメモリを保持する。
機構：広告／認知パケットを処理する時、リンク信頼度推定アルゴリズムがパケットの信号強度又はＳＮＲを用いて予測を行うことにより、リンク信頼度の値を増加させる。信頼度に関して故障から経路の再確立までに要する時間（メモリ故障時間）は、このノードまでの経路を最初に確立するために要する時間（メモリなし故障時間）より、有意に大きい必要がある。
【００４１】
上述から認められ得るように、本明細書にて提示のシステム及び方法は、宛先までの最も良好な経路を経路制御プロトコルに選択させるために、整数値（「リンク信頼度」）を計算する。データレート選択、チャネル選択、又はパケット分割／連結等、より高度な機能においても、この手法は用いられ得る。さらに、先述のシステム及び方法を用いて、システムが動作する各キャリア周波数、各パケット・サイズ間隔、各データレート若しくは各変調方式、又はそれらの任意の組合せに対し、独立にリンク信頼度が決定され得る。したがって、このシステム及び方法は、所与の時間において用いることが必要である最適なチャネル、分割／連結方法、データレート又は変調方式を、最も良好なリンク信頼度を与えるチャネル、分割／連結方法、データレート又は変調方式を選択することにより、決定することが可能である。
【００４２】
さらに、上述から認められ得るように、幾つかの理由から、本発明の実施形態による手法は背景技術に記載の手法より有利である。第１に、本手法は装置試験可能（ｕｎｉｔ−ｔｅｓｔａｂｌｅ）であるため、アルゴリズムが適切に実装されていることを照合することが容易である。ＳＮＲ及び信号強度に基づく方法においては信頼度を推定することのみが可能であり、どの程度リンクが信頼可能であるかを正確に示すことは期待できない。また本手法はプログラム可能であるのでマイクロプロセッサに実装可能であり、論理合成可能（ｓｙｎｔｈｅｓｉｚａｂｌｅ）であるのでＡＳＩＣ又はＦＰＧＡに実装可能である。また本手法は、パケット無線が動作する帯域幅又は帯域のフェージング特性に関わらず、任意の種類のパケット無線において用いられることが可能である点で可搬である。アルゴリズムの特徴のうちの１つは、トラフィックが不変である又は規制されている必要がないことである。さらに、本手法は適応型であるので任意の程度のトラフィック負荷又は収束時間に対して調整可能であり、フィルタ・パラメータ及び到達時間間隔境界を外部的に調整することが可能である。これに加えて、本手法は実装が簡単であり、開発コストは極めて小さい。
【００４３】
上述においては本発明の幾つかの模範的な実施形態のみを説明したが、本発明の新規な教示及び利点から実質的に逸脱することなく模範的な実施形態において多数の変更が可能であることが、当業者には容易に認められるであろう。したがって、添付の特許請求の範囲において規定される本発明の範囲の内に、そのような変更の全てが包含されることを意図するものである。
【図面の簡単な説明】
【００４４】
【図１】本発明の一実施形態によるシステム及び方法を用いる複数のノードを含む一例のアドホック無線通信ネットワークのブロック図。
【図２】図１に示すネットワークに用いられる移動体ノードの一例を示すブロック図。
【図３】データ・パケット及びハロー・メッセージに対して予測されるリンク信頼度対信号強度を表すグラフ。
【図４】本発明の一実施形態によるリンク信頼度を計算するための方程式を表すブロック図。
【図５ａ】種々の到達時間間隔Δｔに対して量子化されたλの組を示すグラフ。
【図５ｂ】図１に示すシステムにおけるノードの制御チャネル（アイドル）、軽度トラフィック、中程度トラフィック及び重度トラフィックの動作状況に対する可変重み付けフィルタの応答を示すグラフ。
【図１】
2006527525.tif 000011
【図２】
2006527525.tif 000012
【図３】
2006527525.tif 000013
【図４】
2006527525.tif 000014
【図５ａ】
2006527525.tif 000015
【図５ｂ】
2006527525.tif 000016
【手続補正書】
【提出日】平成18年2月10日(2006.2.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を特定するための方法であって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別する信頼度推定工程と、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィック状況に基づき、予測される値を調整することと、
信頼度推定工程において決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択する経路選択工程とからなる方法。
【請求項２】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項１に記載の方法。
【請求項３】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項１に記載の方法。
【請求項４】
発信元ノード及び宛先ノードは移動体ノードである請求項１に記載の方法。
【請求項５】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項１に記載の方法。
【請求項６】
信頼度推定工程は以下の方程式に基づきリンク信頼度を推定する請求項１に記載の方法。
【数１】
2006527525.tif 000017
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λ
Δｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項７】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項１に記載の方法。
【請求項８】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて発信元ノードと宛先ノードとの間の最適経路を発信元ノードが特定するように制御するための命令を含むコンピュータ可読媒体であって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別する命令の第１の組と、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィック状況に基づき、予測される値を調整することと、
命令の第１の組において決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択する命令の第２の組とを含むコンピュータ可読媒体。
【請求項９】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項８に記載のコンピュータ可読媒体。
【請求項１０】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項８に記載のコンピュータ可読媒体。
【請求項１１】
発信元ノード及び宛先ノードは移動体ノードである請求項８に記載のコンピュータ可読媒体。
【請求項１２】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項８に記載のコンピュータ可読媒体。
【請求項１３】
命令の第１の組は以下の方程式に基づきリンク信頼度を推定する請求項８に記載のコンピュータ可読媒体。
【数２】
2006527525.tif 000018
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項１４】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項８に記載のコンピュータ可読媒体。
【請求項１５】
アドホック・マルチホッピング・ピアツーピア無線通信ネットワークにおいて自身と宛先ノードとの間の最適経路を特定するノードであって、
予測機構及び可変重み付けフィルタを用いてネットワークにおいてノード間のリンク信頼度を推定することにより、発信元ノードと宛先ノードとの間の幾つかのノードを含む最適経路を識別することと、
可変重み付けフィルタはリンク品質が推定されるノードにより経験されているトラフィ
ック状況に基づき、予測される値を調整することと、
信頼度を推定することにより決定された最も好適なリンク品質を有するノードからなる発信元ノードと宛先ノードとの間の経路を選択することとを含むコントローラを含むノード。
【請求項１６】
予測される値は信号強度及び信号対雑音比のうちの少なくとも一方に基づく請求項１５に記載のノード。
【請求項１７】
トラフィック状況はアイドル、軽度トラフィック、中程度トラフィック又は重度トラフィックを含む請求項１５に記載のノード。
【請求項１８】
発信元ノード及び宛先ノードは移動体ノードである請求項１５に記載のノード。
【請求項１９】
最も好適なリンク品質は宛先ノードによりパケットが成功裏に受信される確率の尺度を含む請求項１５に記載のノード。
【請求項２０】
コントローラは以下の方程式に基づきリンク信頼度を推定する請求項１５に記載のノード。
【数３】
2006527525.tif 000019
［ここで、ＬＲ（ｔ０）は現在のリンク信頼度、ＬＲ（ｔ−１）は前のリンク信頼度、λΔｔ／ΔＴは現在の忘却係数、Δｔ＝ｔ０−ｔ−１は現在の到達時間間隔、ΔＴは基準時間単位、Ｘ（ｔ０）は現在のフィルタ入力（予測に基づく）である］
【請求項２１】
経験されているトラフィック状況は各パケット伝送間の到達時間間隔を計算することにより決定される請求項１５に記載のノード。
【国際調査報告】
2006527525.tif 000020