(57)【要約】  本発明は、複数のネットワーク・ノードから成る複数ホップの無線通信ネットワークにおいて、効率的なルーティングを行うシステムに関するものである。システムは、該インフラ・ノード間のリンク状態を示す品質情報を取得する手段(3001)、予測手順を用いるインフラ・ノード内の経路決定プロセスにおいて該リンク品質情報を用いる手段(3002)、そして、決定された経路に従ってデータパケットを送るルーティング手段(101)から成り、該リンク品質情報は、該リンク状態の時間的に変化する情報についての情報を含んでおり、該予測手順は、予測手順の中でリンク状態の該時間的に変化する情報を使用する。
2007529135.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワーク・ノードから成る複数ホップの無線通信ネットワークにおいて、効率的なルーティングを行うシステムであって、
前記インフラ・ノード間のリンク状態を示す品質情報を取得する手段（３００１）と、
予測手順を用いるインフラ・ノード内の経路決定プロセスにおいて、前記リンク品質情報を用いる手段（３００２）と、
決定された経路に従ってデータパケットをルーティングするルーティング手段（１０１）とを有し、
前記リンク品質情報は、前記リンク状態の時間変化情報についての情報を含んでおり、前記予測手順は、リンク状態の前記時間変化情報を用いることを特徴とするシステム。
【請求項２】
前記無線通信が１００ｋＨｚから１００ＰＨｚの範囲の周波数による電磁放射に基づく伝送システムであることを特徴とする請求項１記載のシステム。
【請求項３】
前記伝送システムが、ＩＥＥＥ ８０２．１１、ＩＥＥＥ ８０２．１５、ＩＥＥＥ ８０２．１６、ＨｉｐｅｒＬＡＮ、ＨｏｍｅＲＦ、Ｂｌｕｅｔｏｏｔｈ、赤外線、ＵＷＢ、ＪＴＲＳ、３Ｇ、ＧＰＲＳ、またはＥＤＧＥの一つ以上であることを特徴とする請求項２記載のシステム。
【請求項４】
反応型アドホックルーティングプロトコルを用いることを特徴とする請求項１記載のシステム。
【請求項５】
先行型アドホックルーティングプロトコルを用いることを特徴とする請求項１記載のシステム。
【請求項６】
反応型アドホックルーティングプロトコルと先行型アドホックルーティングプロトコルの組み合わせを用いることを特徴とする請求項１記載のシステム。
【請求項７】
前記リンク状態情報がドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つを測定して得られる無線チャネル状態情報であることを特徴とする請求項１記載のシステム。
【請求項８】
アドホックルーティングプロトコルのための前記予測手順が、取得したリンク状態情報および無線チャネル情報を、予め定められたルーティング予測基準と比較して利用することを特徴とする請求項１記載のシステム。
【請求項９】
前記反応型アドホックルーティングプロトコルのための前記予測モデルが、リンク状態および無線チャネル状態についての情報を、修正された経路応答（ＲＲＥＰ）、ハローメッセージ、確認応答、または経路エラー（ＲＥＲＲ）メッセージから取得することを特徴とする請求項４記載のシステム。
【請求項１０】
前記先行型アドホックルーティングプロトコルの前記予測モデルが、リンク状態についての情報によって修正される、経路状態フィールドを含んだルーティングテーブルを備えることを特徴とする請求項５記載のシステム。
【請求項１１】
前記リンク状態情報が、前記ネットワーク内のノードのエネルギ状態を含むことを特徴とする請求項１記載のシステム。
【請求項１２】
前記リンク状態情報が、前記ネットワーク内のノード間のＮＡＣＫ（確認否定）信号またはＡＣＫ（確認）信号の数を含むことを特徴とする請求項１記載のシステム。
【請求項１３】
前記リンク状態情報が、前記ネットワーク内のノード間での通信のビット・エラー数を含むことを特徴とする請求項１記載のシステム。
【請求項１４】
前記リンク状態情報が、前記ネットワーク内のノードの所有権についての情報を含むことを特徴とする請求項１記載のシステム。
【請求項１５】
請求項１記載のシステムの中で使われるルーティングプロトコル。
【請求項１６】
先行型アドホックルーティングプロトコル、反応型アドホックルーティングプロトコル、あるいは先行型アドホックルーティングプロトコルと反応型アドホックルーティングプロトコルの組み合わせのうちの一つであることを特徴とする請求項１５記載のルーティングプロトコル。
【請求項１７】
複数のノードを有する無線通信ネットワークにおける効率的なルーティングのための方法であって、
ノード間のリンク状態を取得するステップと、
リンク状態情報を用いてルーティング要素を更新するステップと、
前記リンク状態情報を用いる予測手順に従って、効率的な経路を決定するステップと、
前記決定された経路に従ってトラヒックをルーティングするステップとを有することを特徴とする方法。
【請求項１８】
前記経路決定ステップが、反応型アドホックルーティングプロトコルを用いるステップを有することを特徴とする請求項１７記載の方法。
【請求項１９】
前記経路決定ステップが、先行型アドホックルーティングプロトコルを用いるステップを有することを特徴とする請求項１７記載の方法。
【請求項２０】
前記経路決定ステップが、反応型アドホックルーティングプロトコルと先行型アドホックルーティングプロトコルの組み合わせを用いるステップを有することを特徴とする請求項１７記載の方法。
【請求項２１】
前記取得するステップが、ドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つの測定から無線リンク状態情報を取得することを特徴とする請求項１７記載の方法。
【請求項２２】
アドホックルーティングプロトコルのための前記予測手順が、取得したリンク状態情報を、予め定められたルーティング予測基準と比較して利用するステップを有することを特徴とする請求項１７記載の方法。
【請求項２３】
前記反応型アドホックルーティングプロトコルのための前記予測手順が、リンク状態についての情報を、修正された経路応答（ＲＲＥＰ）、ハローメッセージ、確認応答、または経路エラー（ＲＥＲＲ）メッセージから取得するステップを有することを特徴とする請求項１８記載の方法。
【請求項２４】
前記先行型アドホックルーティングプロトコルのための前記予測手順が、経路状態フィールドを含むルーティングテーブルを、リンク状態についての情報を使って修正するステップを有することを特徴とする請求項１９記載の方法。
【請求項２５】
前記リンク状態情報が、前記ネットワーク内のノードのエネルギ状態を含むことを特徴とする請求項１７記載の方法。
【請求項２６】
前記リンク状態情報が、前記ネットワーク内のノード間のＮＡＣＫ（確認否定）信号またはＡＣＫ（確認）信号の数を含むことを特徴とする請求項１７記載の方法。
【請求項２７】
前記リンク状態情報が、前記ネットワーク内のノード間の通信のビット・エラー数を含むことを特徴とする請求項１７記載の方法。
【請求項２８】
前記リンク状態情報が、前記ネットワーク内のノードの所有権についての情報を含むことを特徴とする請求項１７記載の方法。
【請求項２９】
前記無線通信が１００ｋＨｚから１００ＰＨｚの範囲の周波数による電磁放射に基づく伝送システムであることを特徴とする請求項１７記載の方法。
【請求項３０】
前記伝送システムが、ＩＥＥＥ ８０２．１１、ＩＥＥＥ ８０２．１５、ＩＥＥＥ ８０２．１６、ＨｉｐｅｒＬＡＮ、ＨｏｍｅＲＦ、Ｂｌｕｅｔｏｏｔｈ、赤外線、ＵＷＢ、ＪＴＲＳ、３Ｇ、ＧＰＲＳ、またはＥＤＧＥの一つ以上であることを特徴とする請求項２９記載のノード（８００）。
【請求項３１】
複数ホップ無線通信ネットワークにおける効率的ルーティングのためのノード（８００）であって、
リンク品質取得手段（３００１）と、
リンク状態情報をルーティング手段（１０１）に提供するリンク状態監視手段（１０２）と、
予測手順を使って、前記リンク品質情報に従って適切な経路を決定する前記ルーティング手段（１０１）とを有することを特徴とするノード。
【請求項３２】
前記無線通信が１００ｋＨｚから１００ＰＨｚの範囲の周波数による電磁放射に基づく伝送システムであることを特徴とする請求項３１記載のノード（８００）であって、
【請求項３３】
前記伝送システムが、ＩＥＥＥ ８０２．１１、ＩＥＥＥ ８０２．１５、ＩＥＥＥ ８０２．１６、ＨｉｐｅｒＬＡＮ、ＨｏｍｅＲＦ、Ｂｌｕｅｔｏｏｔｈ、赤外線、ＵＷＢ、ＪＴＲＳ、３Ｇ、ＧＰＲＳ、またはＥＤＧＥの一つ以上であることを特徴とする請求項３２記載のノード（８００）。
【請求項３４】
反応型アドホックルーティングプロトコルを用いることを特徴とする請求項３１記載のノード（８００）。
【請求項３５】
先行型アドホックルーティングプロトコルを用いることを特徴とする請求項３１記載のノード（８００）。
【請求項３６】
反応型アドホックルーティングプロトコルと先行型アドホックルーティングプロトコルの組み合わせを用いることを特徴とする請求項３１記載のノード（８００）。
【請求項３７】
前記リンク状態情報がドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つを測定して得られる無線チャネル状態情報であることを特徴とする請求項３２記載のノード（８００）。
【請求項３８】
アドホックルーティングプロトコルのための前記予測手順が、取得したリンク状態情報および無線チャネル情報を、予め定められたルーティング予測基準と比較して利用することを特徴とする請求項３７記載のノード（８００）。
【請求項３９】
前記反応型アドホックルーティングプロトコルのための前記予測モデルが、リンク状態および無線チャネル状態についての情報を、修正された経路応答（ＲＲＥＰ）、ハローメッセージ、確認応答、または経路エラー（ＲＥＲＲ）メッセージから取得することを特徴とする請求項３４または請求項３７記載のノード（８００）。
【請求項４０】
前記先行型アドホックルーティングプロトコルの前記予測モデルが、リンク状態についての情報によって修正される、経路状態フィールドを含んだルーティングテーブルを備えることを特徴とする、請求項３５または請求項３７記載のノード（８００）。
【請求項４１】
前記リンク状態情報が、前記ネットワーク内のノードのエネルギ状態を含むことを特徴とする請求項３１記載のノード（８００）。
【請求項４２】
前記リンク状態情報が、前記ネットワーク内のノード間のＮＡＣＫ（確認否定）信号またはＡＣＫ（確認）信号の数を含むことを特徴とする請求項３１記載のノード（８００）。
【請求項４３】
前記リンク状態情報が、前記ネットワーク内のノード間での通信のビット・エラー数を含むことを特徴とする請求項３１記載のノード（８００）。
【請求項４４】
前記リンク状態情報が、前記ネットワーク内のノードの所有権についての情報を含むことを特徴とする請求項３１記載のノード（８００）。
【請求項４５】
無線通信ネットワーク内で用いるための層構成であって、
無線チャネル情報取得手段（３００１）を有する第１層と、
リンク状態情報取得手段（１１５）を有する第２層と、
前記第１層および前記第２層から無線チャネル情報およびリンク状態情報を取得するリンク状態監視手段（１０２）及び予測手順において前記リンク状態情報を用いる経路決定手段（３００２）と、決定された経路を経由してデータをルーティングするためのルーティング手段（１０１）とを有する第３層、とを有することを特徴とする層構成。
【請求項４６】
複数ホップ無線通信ネットワークにおけるルーティングを制御するコンピュータ・プログラムであって、
インフラ・ノード間のリンク状態情報を取得するための第１の命令セットと、
前記取得したリンク状態情報を予測手順において使用し、効率的な経路を決定するための第２の命令セットと、
前記決定された経路に従ってトラヒックをルーティングする第３の命令セットとを有することを特徴とするプログラム。
【請求項４７】
複数ホップ無線通信ネットワークにおけるルーティングを制御するコンピュータ・プログラムを含んだ製品であって、
インフラ・ノード間のリンク状態情報を取得するための第１の命令セットと、
前記取得したリンク状態情報を予測手順において使用し、効率的な経路を決定するための第２の命令セットと、
前記決定された経路に従ってトラヒックをルーティングする第３の命令セットとを有することを特徴とする製品。
【請求項４８】
無線ネットワークにおける効率的なルーティングの方法であって、データ・パケットが、
前記ネットワーク内のインフラ・ノード間のリンク状態品質を測定することによってリンク状態情報を提供するステップと、
前記リンク状態情報を使ってルーティング要素を更新するステップと、
前記リンク状態情報を使って経路を決定するステップと、
データ・パケットのルーティング失敗を検出したときには、前記無線ネットワーク内のインフラ・ノードのリンク状態情報を用いる予測手順を用いて決定された、異なる経路を経由して、前記データパケットを再送信するステップ、
とを用いてルーティングされることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングシステム、方法および装置に関するものであり、特に、予測ルーティングを用いた、モバイル環境または静的環境におけるアドホック・ネットワークのためのものである。
【背景技術】
【０００２】
モバイル・ユーザ間の無線通信は、装置や技術の進歩に伴って、ますます普及している。インフラの展開は、通信システムにおいてもデータ・ネットワーク・システムにおいても拡大を続けている。今日、通信システムもパケット交換網の利用が増加しており、パケットに基づくルーティングという枠組みへの流れは明らかである。このシステムはデータネットワークをベースにしたシステムにおいて長年利用されており、従ってこの目的で標準化されたルーティングプロトコルが多数存在する。しかし、それらは、例えばいわゆるアドホック・ネットワークのような、急速に変化するネットワークトポグラフィへの対応が考慮されたものではない、。
【０００３】
無線アドホック・ネットワークの特徴は、通常の有線ネットワークインフラのような静的な性質を持たないこと、一元制御を行なう手段がないこと、自然発生的に形成されることが多いという点にある。制御は分散化のコンセプトによって維持される。ノードの接続や切断は、標準的な固定ネットワーク・アーキテクチャと比べて無統制な方法で行われることがある。ノードが急にやってきたり、出て行ったりすると、それによりネットワークトポロジは動的に変化する。ときには、そのようなアドホック・ネットワークは、ユーザまたはクライアント装置そのものがインフラの構成装置となって形成される。これらの構成装置は、ユーザがネットワークのセルを出入りしながら動きまわるという意味で、まさしく移動性であり、それゆえインフラもそれに従って移動する。これは面白いインフラ構築法であるが、ルーティングプロトコルに非常に厳しい要求を行うことでもある。
【０００４】
無線環境におけるその他の問題は、ネットワーク・フローの性能と効率を劣化させる無線特有の問題によるものである。無線環境におけるインフラ・ノードの移動や対象(objects)の移動によるフェーディングの問題もあるし、通信範囲内にある他の電波源からの干渉による問題もあるだろう。
【０００５】
このようなネットワークトポグラフィは軍事環境において使われてきたが、現在では民生分野でも使われ始めている。今、無線システムは、例えば住宅地や商業地域に無線ブロードバンドアクセス用のインフラ急速に構築するのに使われている。例えば、緊急事態、災害地域、戦闘地域での軍事目的等で、一時的にインフラを構築するのに使ってもよい。例えば、コンサート、会議、会合、季節的な観光地のようなイベントの期間中に一時的な通信サービスエリアを構築するのに使うこともできる。これらの地域では、一年中通信サービスエリアを提供する必要はなく、特定の期間内だけで良い。
【０００６】
現在では、インターネット・サービス・プロバイダ(ISP)数社が、空港、レストラン、珈琲店、ホテルのような公共または半公共的な区域で、固定無線インフラシステムを使って無線アクセスを提供している。このようなシステムは、しばしばホットスポットと呼ばれる。
【０００７】
通信サービスエリアの大きさと帯域の点でアクセスに対するユーザの需要が高まると、無線による通信サービスエリアや帯域を拡大する方法の一つはインフラの構成装置をより多く設置することである。しかしこれを通常の固定ワイヤレス構成装置で行うのは費用がかさむ。従って、無線ルータを使ってネットワークを構築するというアイデアが浮上してきた。この場合、設置手順を簡素化するためにアドホックルーティングプロトコルを使ってもよい。
【０００８】
アドホック・ネットワークを論じる際、基本的に2種類のネットワーク利用法がある。第一の方法は、外部ネットワーク（たとえばインターネット）へのアクセスを提供する外部ゲートウェイなしのLANを構築することである。この手法は災害地域に関する設置や戦闘地域での軍事用の設置に見ることができる。もう一方の利用法は、多分もっと普通の方法であるが、一つ以上のゲートウェイを設けてネットワークに外部接続機能、例えばIPネットワーク（専用網でも良いし、公共網、例えばインターネットでも良い）への接続機能を持たせることである。そのようなネットワーク構成においては、データパケットは、例えばデータトラヒックの種類、輻輳、経路コストによって異なる経路を選択したり異なるゲートウェイを利用したりする可能性がある。
【０００９】
パケットに基づくルーティング手法では、階層化モデル、例えばOSI参照モデルを元に通信ネットワークシステムを構築することが多い。通信ソフトウェアやハードウェアはいくつかのより小さいサブユニットや階層に分かれており、階層的に機能している。情報・通信制御パラメータが、局所的に上層及び下層間でやりとりされたり、送信端及び受信端における同じ階層間でやりとりされる。当該階層の各々は、通信命令の中の異なるタスクについて責任を負う。ルーティングに関しては、OSI参照モデルの最初の3つの階層がもっとも重要である。
【００１０】
第1層は、データビットの物理的伝送に責任を持つ。物理的手段の例としては、例えば、イーサネット（登録商標）をベースにしたネットワークにおける有線リンク、または無線LANにおける無線リンク等でもよい。
【００１１】
第2レイヤは、リンクレイヤ層又はMAC層と呼ばれ、データチャンクの伝送、エラー検出、ネットワーク・リソース調整等に責任を持つ。
【００１２】
第3層はネットワーク層と呼ばれることが多い。ネットワーク内の任意のノード対間の通信を可能にする責任を持つ。この層は、例えば、ルーティング計算や輻輳制御を担当する。この目的で、ネットワークの種類によって異なるルーティングプロトコルが開発されてきた。
【００１３】
IPネットワークにおけるパケットルーティングプロトコルは、一般に、距離ベクトルまたはリンク状態情報を用い、ネットワーク内のソースノードと宛先ノードのペアの各々についての経路を見つけて維持するルーティングアルゴリズムに基づいている。原則として、距離ベクトルルーティングアルゴリズムにおいては、各ルータは全ホストとの距離を隣接ルータにブロードキャストし、情報を受信した各ルータがネットワーク内の各ホストへの最短経路を計算する。リンク状態ルーティングアルゴリズムにおいては、各ルータは各隣接ネットワークリンクの状態情報を隣接ルータにブロードキャストし、情報を受信した各ルータがリンク状態情報からネットワークの全体像のデータベースを維持し、データベース内のリンクコストに基づいて各ホストへの最短距離を計算する。これらのルーティングアルゴリズムは比較的スタティックなネットワーク向けに設計されており、そのため、トポロジが頻繁に変化するアドホック・ネットワーク向けには、新たなルーティングアルゴリズムを設計する必要がある。
【００１４】
基本的に、アドホック・ネットワーク向けの既存のルーティングプロトコルには二つのカテゴリがある。すなわち、「先行型（テーブルによる動作）」と「反応型（オンデマンド）」ルーティングプロトコルである。これらのプロトコルを組み合わせたプロトコルも可能である。
【００１５】
先行型ルーティングプロトコルは定常的かつ周期的に、アドホック・ネットワーク内の全ホストへの経路を計算する。従って、パケットを特定の宛先ホストに送信する必要が生じたとき、利用可能な経路が常にある。結果はすべてのノードのルーティングテーブルに維持される。
【００１６】
各ホストへの経路を維持するため、ルータ間で制御メッセージを交換し、ネットワーク構成やリンク状態の変化を通知する。距離ベクトルとリンク状態ルーティングプロトコルはどちらも先行型プロトコルに属する。制御メッセージはオーバヘッドに直結するため、結果としてネットワーク効率が低下することに注意が必要である。また、先行型プロトコルは、ネットワークトポロジが頻繁に変化するときには有効な経路の維持が困難な可能性がある。
【００１７】
DSDV (Destination-Sequenced Distance Vector Routing（宛先順序距離ベクトルルーティング）)は、距離ベクトルアルゴリズムに基づく先行型ルーティングプロトコルであり、ルーティング情報プロトコル（Routing Information Protocol (RIP)）をアドホック・ネットワークに適合したものである。各ノードはルーティングテーブルを維持しており、その中には到達可能な全宛先ホストの各々に対する次のホップ・ノードとホップ・カウントが保存されている。DSDVにおいては、各ノードが定期的またはネットワークトポロジの変更を検出したときに、ルーティングの更新についてブロードキャストまたはマルチキャストする。制御トラヒックを減らすため、前回の更新からの変更についての情報のみを更新する増分更新を行うこともある。
【００１８】
反応型プロトコルは、送信するデータパケットがあるときだけ、経路の発見・更新のために制御メッセージの交換を行う。あるソース・ノードがデータ・パケットを送信しようとするとき、ソース・ノードは制御プロトコルを開始し、隣接ノードに経路要求メッセージを送信することによって経路を発見する。この原理によって、転送すべきパケットがないときにはネットワーク資源を浪費しないという点で、反応型の方法はすぐれている。しかし、最初に経路を形成するときにはパケットの送信に要する時間が長くなる。AODVおよびDSRは代表的な反応型プロトコルである。
【００１９】
AODV (Ad hoc On-Demand Distance Vector Routing)プロトコルは、DSDVアルゴリズムを用いており、オン・デマンドで、すなわちソース・ノードがデータパケットを送信するときだけ経路を作成し更新する。これにより、経路を発見・更新するのに必要なブロードキャストの数が少なくて済む。
【００２０】
AODVでは、各ノードは検出した隣接ノードのリストを維持する。隣接ノードリストは以下の三通りの方法のうちのいずれかによって更新される。a) パケットを隣接ノードから受信したとき、b)隣接ノードからローカルな宣伝(advertisement)、すなわちハロー・メッセージを受信することにより、 あるいは、c) リンク層からのフィードバックを通じて。ハロー・メッセージは、各ノードが隣接ノードに自己の存在を知らせるために隣接ノードに対して定期的にブロードキャストされる。
【００２１】
AODVでは、各ノードはすべての宛先のルーティングテーブルを維持している。宛先の各々は、ノードが交信しているか、または他のノードの代理でデータパケットを送信しているかのどちらかである。各宛先について、ルーティングテーブルにエントリがある。各エントリは、宛先に関する情報、例えばIPアドレス、宛先ノードのシーケンス番号、宛先へのホップ・カウント、宛先への次のホップ・ノード、経路の存続期間(lifetime)を含む。
【００２２】
あるノードが宛先ノードと交信しようとするとき、すなわち、データパケットを宛先に送信しようとするとき、ソース・ノードは経路発見メカニズムを起動する。ここでソース・ノードは、検出したすべての隣接ノードに対して経路要求(RREQ)をブロードキャストする。隣接ノードが経路要求メッセージを受信して、その宛先に対する新たな経路エントリがルーティングテーブルにあるとき、隣接ノードはソース・ノードに経路応答(RREP)メッセージを返す。隣接ノードがその宛先についての経路エントリを見つけられないとき、隣接ノードは経路要求メッセージを自分自身が見つけた隣接ノードに転送する。宛先ノードが経路要求(RREQ)を受信すると、宛先ノードは経路応答(RREP)メッセージをソースノードに返す。
【００２３】
経路要求(RREQ)パケットを転送するプロセスにおいて、各中間ノードは、隣接ノードからRREQの最初のコピーを受信すると、その隣接ノードのIPアドレスを記録することにより、逆ルートを確立する。その後受信した同一の経路要求(RREQ)メッセージのコピーはすべて廃棄する。中間ノードは宛先に対する自分のルーティングテーブルにエントリを追加する。ここでは、経路応答(RREP)の送信元である隣接ノードを、その宛先への次のホップ・ノードとして記録する。宛先順序番号とその経路の存続期間を経路応答(RREP)からコピーし、エントリに記録する。最後にソース・ノードから経路応答(RREP)メッセージが返ってきたとき、ソースから宛先までの転送経路が形成されたことになる。
【００２４】
経路上のリンクの障害である経路が利用できなくなったことを検出したとき、ノードはその経路を利用するすべての隣接ノードに対して経路エラー(RERR)メッセージを送信する。経路エラー(RERR)メッセージは隣接ノードのさらに隣接ノードへ送信され、ソース・ノードに届くまで送信が続けられる。そうするとソース・ノードが、データ・パケットの送信を停止するか、新たな経路発見を開始するかという決定を行うことができる。
【００２５】
DSR (Dynamic Source Routing) プロトコルで用いるソースルーティングメカニズムでは、経路に沿ったノードの全順序をオン・デマンドでソース・ノードが決定する。そしてパケットのヘッダに中間ノードのリストを設定して、経路上のノードの順序を示す。このように、各パケットはパケットのルーティングのためのオーバヘッドを伝送する必要がある。しかし、中間ノードは経路に関する情報を一切維持する必要なく、データ・パケットを配信するときに経路を知ることができる。
【００２６】
DSRにおいては、各ノードは自分が知った経路を保存（キャッシュ）する。ソース・ノードがデータ・パケットを宛先ノードに送信したいが、キャッシュにその宛先についてのエントリがない場合、ソース・ノードは自分のリンク層上で経路要求(RREQ)メッセージをブロードキャストすることによって経路発見メカニズムを起動する。経路要求(RREQ)メッセージを受け取った各ノードは、自分のIPアドレスを経路要求(RREQ)メッセージに追加し、それをさらに転送する。宛先への経路が見つかるまで、あるいは別のノードが宛先ノードへの経路を提供できるまで、このプロセスは続く。その後、宛先ノードへの一連のネットワーク・ホップを含む経路応答(RREP)メッセージがソース・ノードに返信される。
【００２７】
DSRでは、あるノードでリンク障害を検出すると（すなわち、パッケージが最大回数再送信されたとき）、そのノードは自分の経路キャッシュからそのリンクを削除して、確認応答を前回受信して以来そのリンクを使った各ノードに対して、経路エラー(RERR)メッセージを送信する。これらのノードはそのリンクを含む経路を削除する必要がある。ソース・ノードからのデータ・パケットの再送信は、その後、送信制御プロトコル（Transmission Control Protocol (TCP)）のような上位層によって処理される。
【００２８】
リンクの有効期限およびノードのトラヒック負荷を用いるアドホックルーティングプロトコルにおいて、リンク有効期限は、二つの特定のノードの距離が無線有効距離以下に維持される時間間隔である、と定義される。このルーティングプロトコルでは、各リンクのコストとしてメトリックを用いる。ノードは、経路の存続時間がより長く、経路更新頻度とトラヒック制御用のオーバヘッドが少なく、データ・パケット転送の全体的な処理量が増加するであろうという予想の元に、最小コストの経路を探そうとする。
【００２９】
このプロトコルでは、ノードのトラヒック負荷を、所与の時間における使用率（busy rate）で表す。経路選択アルゴリズムでは、ノードのトラヒック負荷が最も少ない経路を選択する。このアルゴリズムにより、ネットワーク内での良好な負荷バランスの実現、すなわち、ネットワーク内の特定ノードへのトラヒック集中を回避しうるであろうことが期待されている。
【００３０】
移動無線通信ネットワークにおいて従来のアドホックネットワークルーティング方法を用いるとき、いくつか問題が起きる可能性がある。その一つは、移動が可能であるためユーザが動き回り、フェーディング、伝搬損失、シャドーイングなどによってシステムの無線品質が変化することである。これは、インフラシステムが可動性要素で構成されている場合、例えば、クライアント装置がインフラの一部である場合にも当てはまる。固定式無線インフラ構成要素を備えたシステムであっても、そのような問題は起こる。例えば、二つのインフラ構成要素間の信号経路を車両や他の物体が一時的に遮断することによって無線リンク品質が変化する場合などがそうである。この種の問題が特に心配なのは、その変化がルーティングテーブルや経路変更の更新頻度より速いときである。
【００３１】
もし経路情報の更新頻度を増すことによって上記の問題を解決しようとすれば、ある時点で伝送効率の低下が始まる。経路情報の更新は、伝送媒体のデータ伝送可能量の相当な部分を占めることになるためである。
【００３２】
特許文献１では、使用する周波数帯、この場合は2. 4 GHz ISM帯において、認証されていない信号を聞くことにより、ネットワーク内の干渉源を検出するシステムについて説明している。この文書では、無線層よりもネットワーク層上で発生する問題に焦点を当てている。文書は現状への適合についてのみ開示しており、将来的に起こりうるリンク状態に関連する記述はない。このシステムはパケット経路を適合させて干渉の影響を減らすことを試みている。解決案は干渉の検出にのみ注目しており、アンテナの位置とノードの方向を干渉物に近づくように調節して干渉源に対する無線通信範囲を狭めることによって問題を解決している。
【００３３】
特許文献２では、固定網での解決策として状態予測機能を導入している。この解決策の中では、状態監視機能からの情報の大規模で統計的な計算を含んでいる。統計的計算は、ネットワークシステム全体のもたらす影響を解釈するために行われるものであり、アドホック・ネットワーク、特に無線アドホック・ネットワークにすぐに適合させることはできない。
【００３４】
【特許文献１】米国特許公開第2003/0120809号公報
【特許文献２】米国特許第5,537, 394号公報
【発明の開示】
【００３５】
本発明の目的は、インフラ・ノード間のリンク状態情報を用いた予測的なルーティング制御を導入することによって、上述の問題を軽減するアドホックルーティングの方法を提供することである。
【００３６】
無線チャネル属性、リンクの品質、あるいは他のリンクの重要なパラメータを定期的に測定することによって、ネットワーク・状態やリンク状態を分析することができる。この情報がルーティング処理要素に伝えられ、ルーティング処理要素はこの情報を用いて信号品質の種類を決定し、適切な時期にリンク状態の変化を監視する。処理要素は、測定した傾向を推定して信号品質の変化を予測し、それに従って適切な方法で対応して利用可能なネットワーク資源を効率的に使用することができる。
【００３７】
OSIネットワーク参照モデルの第1層から取得したチャネル属性情報を、第2層から取得したリンク品質情報と共に、ルーティング制御およびトラヒック・スケジューリングが位置する第3層へと転送する。測定して取得した情報は保存し、利用可能な隣接ノードおよび現在のノードのルーティング手法一部であるネットワーク区域内にあるノードとの間のリンク品質または状態の傾向を分析する。これによって、アドホックルーティングプロトコルはデータ・パケットを送る適切な経路を決定する。
【００３８】
チャネル属性およびリンク品質についての情報は、いくつかの異なるパラメータの測定によって得られる。このようなパラメータの例としては、無線信号フェーディングに因る無線信号のドップラー・スプレッドがある。別の方法としては、無線信号のコヒーレンス・タイム、受信信号の変化速度、または信号対干渉雑音比を減らすことがある。
【００３９】
この種の予測行動の利用は、使用するアドホックルーティングプロトコルの種類には依存しない。
【００４０】
ある実施例では、複数のネットワークノードから成る複数ホップ無線通信ネットワークにおける効率的ルーティングシステムは以下の特徴を持つ。すなわち、システムは、インフラ・ノード間のリンク状態を示す品質情報を取得するための手段、予測手順を用いてインフラ・ノード内の経路決定プロセスにおいてリンク品質情報を用いるための手段、そして、決定された経路に従ってデータパケットを送るルーティング手段から成る。リンク品質情報は、リンク状態の時間的に変化する情報についての情報を含んでおり、予測モデルは、予測手順においてリンク状態の時間的に変化する情報を使用する。
【００４１】
システムはさらに、無線リンクが100 kHz から100 PHzまでの範囲の周波数による電磁放射に基づく伝送システムであるという特徴を持つ。システムはさらに、伝送システムがIEEE 802.11、 IEEE 802.15、 IEEE 802.16、HiperLAN、 HomeRF、Bluetooth、 赤外線、 UWB、 JTRS、 3G、 GPRS、またはEDGEの内の一つ以上であるという特徴を持つ。
【００４２】
本発明の別の形態においては、システムは、反応型アドホックルーティングプロトコル、先行型アドホックルーティングプロトコル、あるいは反応型と先行型の組み合わせから成る。
【００４３】
本発明のさらに別の形態によれば、システムは、リンク状態情報がドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つを測定して得られる無線チャネル・状態情報であるという特徴を持つ。
【００４４】
システムは、アドホックルーティングプロトコルの予測手順が、取得したリンク状態情報および無線チャネル情報を、決定されたルーティング予期基準と比較して利用するという特徴を持つ。
【００４５】
システムは、反応型アドホックルーティングプロトコルの予測モデルが、リンク状態および無線チャネル・状態についての情報を、修正された経路応答（RREP）、ハローメッセージ、確認応答、または経路エラー（RERR）メッセージから取得するという特徴を持つ。
【００４６】
システムはさらに、先行型アドホックルーティングプロトコルの予測モデルが、リンク状態についての情報を備えた経路状態フィールドを含む、修正されたルーティングテーブルから成るという特徴を持つ。
【００４７】
システムはさらに、リンク状態情報がネットワーク内のノードのエネルギ・状態から成る、という特徴を持つ。
【００４８】
システムはさらに、リンク状態情報がネットワーク内のノード間のNACK （確認否定）信号またはACK(確認)信号の数から成る、という特徴を持つ。
【００４９】
別の形態によるシステムは、リンク状態情報がネットワーク内のノード間の通信のビット・エラー数から成る、という特徴を持つ。
【００５０】
システムはさらに、リンク状態情報がネットワーク内のノードの所有権についての情報から成る、という特徴を持つ。
【００５１】
別の実施例において、上記記述によるシステムで用いられるルーティングプロトコル。
【００５２】
ルーティングプロトコルはさらに、先行型アドホックルーティングプロトコル、反応型アドホックルーティングプロトコル、あるいは先行型と反応型の組み合わせのうちの一つである。
【００５３】
別の実施例において、複数のノードから成る無線通信ネットワークにおける効率的なルーティングのための以下のステップから成る方法。すなわち、ノード間のリンク状態を取得すること、リンク状態情報を使ってルーティング要素を更新すること、リンク状態情報を用いた予測モデルに従って効率的な経路を決定すること、そして決定した経路に従ってトラヒックを送ること。
【００５４】
経路決定ステップは、反応型アドホックルーティングプロトコル、先行型アドホックルーティングプロトコル、あるいは反応型と先行型の組み合わせから成る。
【００５５】
本発明の別の形態によれば、方法は、ドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つの測定によって、無線リンク状態情報を取得する。
【００５６】
アドホックルーティングプロトコルの予測手順は、取得したリンク状態情報を、決定されたルーティング予期基準と比較して利用するステップから成る。
【００５７】
反応型アドホックルーティングプロトコルの予測手順は、リンク状態についての情報を、修正された経路応答（RREP）、ハローメッセージ、確認応答、または経路エラー（RERR）メッセージから取得するステップから成る。
【００５８】
先行型アドホックルーティングプロトコルの予測手順は、経路状態フィールドを含むルーティングテーブルをリンク状態についての情報を使って修正するステップから成る。
【００５９】
リンク状態情報は、ネットワーク内のノードのエネルギ・状態、ネットワーク内のノード間のACK(確認)信号、ネットワーク内のノード間の通信のビット・エラー数、またはネットワーク内のノードの所有権についての情報であっても良い。
【００６０】
方法はさらに、無線通信が100 kHz から100 PHzまでの範囲の周波数による電磁放射に基づく伝送システムであるという特徴を持つ。ノードはさらに、伝送システムがIEEE 802.11、 IEEE 802.15、 IEEE 802.16、HiperLAN、 HomeRF、Bluetooth、 赤外線、 UWB、 JTRS、 3G、 GPRS、またはEDGEの内の一つ以上であるという特徴を持つ。
【００６１】
別の実施例においては、複数ホップ無線通信ネットワークにおける効率的ルーティングのためのノードは、その装置が、リンク品質取得手段、リンク状態情報をルーティング手段に提供するリンク状態監視手段、予測手順を使ってリンク品質情報に従って適切な経路を決定するルーティング手段から成るという特徴を持つ。
【００６２】
ノードはさらに、無線リンクが100 kHz から100 PHzまでの範囲の周波数による電磁放射に基づく伝送システムであるという特徴を持つ。ノードはさらに、伝送システムがIEEE 802.11、 IEEE 802.15、 IEEE 802.16、HiperLAN、 HomeRF、Bluetooth、 赤外線、 UWB、 JTRS、 3G、 GPRS、またはEDGEの内の一つ以上であるという特徴を持つ。
【００６３】
ノードは反応型アドホックルーティングプロトコル、先行型アドホックルーティングプロトコル、あるいは先行型と反応型の組み合わせから成る。
【００６４】
本発明の別の形態において、ノードは、リンク状態情報がドップラー・スプレッド、コヒーレンス・タイム、平均フェーディング時間、信号強度または信号対干渉雑音比の内の少なくとも一つを測定して得られる無線チャネル・状態情報であるという特徴を持つ。
【００６５】
ノードはさらに、アドホックルーティングプロトコルの予測モデルが、取得したリンク状態情報および無線チャネル情報を、決定されたルーティング予期基準と比較して利用するという特徴を持つ。
【００６６】
ノードはさらに、反応型アドホックルーティングプロトコルの予測モデルが、リンク状態および無線チャネル・状態についての情報を、修正された経路応答（RREP）、ハローメッセージ、確認応答、または経路エラー（RERR）メッセージから取得するという特徴を持つ。
【００６７】
ノードはさらに、先行型アドホックルーティングプロトコルの予測モデルが、無線リンク状態についての情報を備えた経路状態フィールドを含む、修正されたルーティングテーブルを持つ、という特徴を持つ
【００６８】
ノードはさらに、リンク状態情報がネットワーク内のノードのエネルギ・状態、ネットワーク内のノード間のNACK （確認否定）信号またはACK(確認)信号の数、ネットワーク内のノード間のビット・エラー数、またはネットワーク内のノードの所有権についての情報から成る、という特徴を持つ。
本発明の別の実施例において、無線通信ネットワーク内で使用するための各層の間の連携が以下から成る。無線チャネル情報取得手段から成る第1層、リンク状態情報取得手段から成る第2層、そして、第1層および第2層から無線チャネル情報およびリンク状態情報を取得するリンク状態監視手段(102) 、リンク状態情報を使用する経路決定手段(3002)、そして決定された経路を経由してデータを送信するためのルーティング手段(101)から成る第3層。
【００６９】
別の実施例において、複数ホップ無線通信ネットワークにおけるルーティングを制御するコンピュータ・プログラムが以下から成る。インフラ・ノード間のリンク状態情報を取得するための第1の指示セット、取得したリンク状態情報を予測手順において使用して効率的な経路を決定するための第2の指示セット、そして、決定された経路に従ってトラヒックを送信する第3の指示セット。
【００７０】
別の実施例において、複数ホップ無線通信ネットワークにおけるルーティングを制御するコンピュータ・プログラムから成る製品が以下から成る。インフラ・ノード間のリンク状態情報を取得するための第1の指示セット、取得したリンク状態情報を予測手順において使用して効率的な経路を決定するための第2の指示セット、そして、決定された経路に従ってトラヒックを送信する第3の指示セット。
【００７１】
無線ネットワークにおける効率的なルーティングの方法が、データ・パケットを下記のステップを用いて送信する、という特徴を持つ。ネットワーク内のインフラ・ノード間のリンク状態品質を測定することによってリンク状態情報を提供すること、リンク状態情報によってルーティング要素を更新すること、リンク状態情報を使って経路を決定すること、そして、データ・パケットのルーティングの失敗を検出したときには、無線ネットワーク内のインフラ・ノードのリンク状態情報を用いた予測手順を用いて決定した異なる経路を経由してデータパケットを再送信すること。
【００７２】
本発明のこの目的およびその他の目的、特徴、機能は、以下の詳細説明を参照すれば明らかになるであろう。
【発明を実施するための最良の形態】
【００７３】
図6に、本発明のモバイルマルチホップ無線アドホック・ネットワークの基本概念を示す。複数のノードまたはインフラ要素601、 602、603、604... 60nが相互に通信してデータトラヒックを転送することによって共同でアドホック・ネットワーク610を構築しており、相互にトラヒックを制御して、通信端ノードと中間ノード間のネットワーク・トラヒックを維持している。アドホック・ネットワーク610には一つ以上のゲートウェイ601が存在するときもある。このゲートウェイ601は、例えば無線アドホック・ネットワーク610と標準的な固定IPネットワーク620（例えばインターネット）間のリンクとして機能する。標準的なIPネットワークへの接続600は、例えばイーサネット（登録商標）・ネットワークを利用した固定回線でも良いし、例えばLMDSや「ミニリンク」システムあるいは同様の技術を使った固定無線接続でも良い。
【００７４】
これらのインフラ・ノード601、 602、603、604... 60nを経由して通信するクライアントまたはエンドユーザ端末は図6に明示していないが、インフラは実際にはクライアントまたはエンドユーザ端末自身を利用することによって構築されることがある。専用ルータによって構築することもあるし、これら二つの要素を組み合わせてネットワークを構築することもある。今日ではクライアントまたはエンドユーザ端末はアドホック環境においてさえネットワークアプリケーションを処理する計算能力を備えている。クライアント端末は、デスクトップコンピュータ、ワークステーション、ノートパソコン、PDA（携帯情報端末）、携帯電話、その他の通信またはネットワーク利用手段を備えたデータ処理装置を含んでも良い。
【００７５】
インフラ要素またはノード601、 602、603、604... 60n、800は、少なくとも、処理手段(801)、保存手段(802)、通信手段805およびルーティング手段101, 803から成る。通信手段805は無線806でも良いし、有線接続806を使っても良いが、好適な実施形態では、通信手段805は無線である。ルーティング手段101, 803は、多くの場合ソフトウェア・プログラムを利用してルーティングアルゴリズムに実装されており、通常はルーティング手段101, 803および通信手段805はどちらもインフラ要素800に組み込まれていることが多い。しかし、コネクタ804によってインフラ要素601、 602、603、604... 60n、800に接続される外部装置に位置する場合もある。この配置の一例として、接続された外部装置を持つPDAが挙げられる。この外部装置がルーティングおよび/または通信手段を担当することで、PDAはアドホック・ネットワーク610あるいは一般の無線ネットワークの一部となることができる。
【００７６】
図1に、ルーティング要素800の主要構成およびその各々の役割を示す。階層ネットワークの参照モデル、例えばOSIモデル内のデータおよび制御トラヒック・フロー・パターンも一緒に示している。第1層104（L1）はデータ・ビットの物理的伝送に責任を持つ。この層に、物理的な伝送媒体の属性の状態と品質、例えば無線チャネル・状態を測定して取得する機能性があってもよい。この情報を第3層106 (L3)、さらにリンク状態モニタ102へと渡す。
【００７７】
インフラ・ノード間の無線リンクの状態を取得する目的で測定するパラメータがいくつかある。その一つがドップラー・スプレッドである。ドップラー・スプレッド、平均フェーディング時間、コヒーレンス・タイム（平均フェーディング時間に比例する）はどちらも無線チャネルが時間と共に変化する性質を説明するパラメータである。移動局とインフラ・ノード間に相対的な動きがあれば、それに関連したフェーディングの問題が発生する。二つのインフラ・ノード間、あるいはインフラ・ノードと移動局間の無線パスの中を移動する物体があれば、同じことが言える。各ノードが定期的に無線ビーコン信号、例えば「ハローメッセージ」を送受信するとき、あるいは他のなんらかの形で隣接ノードからの無線信号を監視するとき、無線チャネル品質の指標となる、いわゆるドップラー・シフトfDの測定が可能である。ドップラー・シフトは、ドップラー・スプレッドの幅の大きさである。この大きさをドップラー・シフトｆDULの最大限度と比較する。これは、アドホックルーティングアルゴリズムがまだ伝送効率を劣化させることなく適用できる限界を設定するものである。信号の帯域幅がドップラー・スプレッドの決定閾値よりもかなり大きい場合、その効果は無視できるものであり、この状況を低速フェーディングと定義し、アドホックルーティングアルゴリズムにとって、更新頻度を増やして対応しなければならないような問題ではない。しかし、ドップラー・スプレッドが決定閾値レベルよりも高い場合、フェーディングはいわゆる高速領域に入っており、そのためルーティングアルゴリズムが経路更新頻度を増やす場合、利用可能な伝送能力の中で制御トラヒックが占める割合が次第に大きくなるため、ある時点でトラヒック・フロー効率の劣化が始まることになる。注意すべき点は、ドップラー・スプレッドがさらに拡大すると、前進型誤信号訂正（FEC (Forward Error Correction)）の影響も同様に拡大し、その結果、第2層のリンク品質の安定性が向上することである。
【００７８】
平均フェーディング時間τDはレイリーのフェーディング・モデルから計算する。これらの計算から、平均フェーディング時間を推定し、これを限界値τDULと比較することができる。これをその相手方であるｆDULと比較しても良い。は下記の等式から計算しても良い。
【００７９】
【数１】
2007529135.tif 000003
【００８０】
ここで、Mは監視されたフェード存続期間、τmはｍ番目のフェード存続期間、N(Rs)はレベルRsを交差したフェードレベルの1秒当たりの数、Tは測定時間である。
【００８１】
無線リンクの品質を説明するもう一つのパラメータは、図2に示すいわゆる変化速度VS201である。これは受信信号強度202または信号対干渉雑音比202がどのくらい早く変化しているかを示す尺度である。VS 201は瞬間的なチャネル強度202を微分することによって計算できる。VS 201が閾値レベルＶSUL203よりも低いとき、アドホックルーティングアルゴリズムはまだネットワーク効率を劣化させることなく対応できる。しかし、VS 201がＶSUL203よりも高いとき、上述のドップラー・スプレッドと同じ問題が起こる。ルーティングテーブルの更新頻度204によって、制御トラヒックが利用可能な伝送能力に占める部分が大きくなるため、伝送効率が劣化する。
【００８２】
第2層105(L2)は、情報のより大きな部分の伝送制御を担当し、エラー処理、検出、エラーへの対応を行う。また、エラー検出を処理することから、第3層106へのリンク品質情報提供も行う。例えば、NACK （確認否定）信号またはACK(確認)信号408、409、410の数をリンク状態モニタ102に渡しても良い。 これらのパラメータの解釈は、NACK信号数の増加はリンクの品質が低下していることを意味し、他方、ACK信号の増加は無線チャネルの品質が向上していることを意味する、ということであろう。
【００８３】
また、L2 105に位置する前進型誤信号訂正（FEC (Forward Error Correction)）要素が検出し訂正したビットエラー数は、リンク状態モニタ102に報告しても良い。このパラメータは上述のACK/NACK信号からは明示的に現れないリンク品質を反映することがある。
【００８４】
リンク状態モニタ102は第一のネットワーク層104 LIおよび第二のネットワーク層105 L2から取得したチャネル属性およびリンク品質情報を監視する。リンク状態モニタ102は無線チャネルの品質を所定の基準に関して決定し、それをフェーディングの二つの異なるカテゴリに分類する。すなわち、ドップラー・スプレッドを測定するのなら低速または高速フェーディング、VSを測定するのなら低速または高速VSカテゴリに分類する。
【００８５】
リンク状態モニタ102はまた、経路決定プロセスに関連するノードのハードウェアまたはアプリケーション層から情報を受け取ることがある。情報とは、例えば、ルーティングパスにおいて当該ノードを除外するか、少なくとも当該ノードの使用量を減らすため、ネットワーク内のノードのバッテリ・レベルあるいはエネルギ状態であっても良い。このように除外するのは、これらのノードのバッテリ・レベルを維持するためである。それは、それらがクライアント端末かもしれないことと、クライアントまたはエンドユーザはいくつかの理由で自分の装置が電池切れになることを望まないことに因る。また、バッテリ・レベルの低いノードはそのうち作動を停止するリスクが高いこともある。それ以外に関連のあるルーティングパラメータとしては、マルチ所有者ネットワークにおいて少なくとも低コストのルーティング方法が実装できるよう、インフラ・ノードの所有者情報をあげてもよいだろう。その場合、クライアントのオペレータが所有するインフラ要素またはクライアントのオペレータが所有者と契約しているインフラ要素を経由してパケットを転送してもよい。ルーティングの金銭コストが各インフラ・ノードに提供してあれば、そして金銭的コストをできるだけ低く押さえることに関心があるのであれば、この方法は有益である。この方法は、無線アドホック・ネットワークに限定されない。IPパケットを送信する通信ネットワークならどんなものにも実装できる。
【００８６】
リンク状態モニタ102は、取得し分析した状態情報をルーティング要素101に転送する。この要素101はルーティング計算を実行して、送信するこのデータパケットの経路を決定し、ルーティングテーブルをいつどのように更新すべきかについても決定する。ルーティング要素101はデータ・トラヒックと制御トラヒックの両方の送受信を扱う。ルーティングの更新処理を行い、所定のスケジュールに従って、またはリンク状態モニタ102から取得した状態情報によって、ルーティングの更新を開始する。
【００８７】
無線および/またはリンク品質の測定からリンク状態情報を取得することから成る予測モデルまたは手順を用いたルーティング決定方法または手順は、リンクの変化を監視し、ルーティングテーブルに格納した各リンクの近い将来の状態を予想または推定する。従って、ルーティング要素101はリンクが機能しなくなる前にルーティング構成を更新することがある。これは、パッケージの紛失による不要なトラヒック・フローを減らすメリットがある。
【００８８】
経路決定方法または手順は、インフラ・ノードに存在するソフトウェア・プログラムによって解決してもよい。
【００８９】
リンク品質の動向や変化を知るため、以前の測定についての情報を一定時間L3 106 に保存する。これはインフラ・ノード内で使用しているハードウェアに応じた標準的な技術で保存する。
【００９０】
表１は、信号強度をフェーディング・パラメータまたは変化速度VSパラメータと合わせて考察した場合のシナリオとその解釈を示す。
【００９１】
【表１】
2007529135.tif 000004
【００９２】
表1から、下記の予期基準および下記に列挙した信号強度傾向についての推定が得られる。
1. 低fDまたは低VSの場合
信号強度が低から高へと移行するとき、新規経路が発生する。
信号強度が高から低へと移行するとき、現在の経路は消滅する。
2. 高fDまたは高VSの場合
信号強度が低から高へと移行するとき、新規の安定した経路がゆっくりとできあがる。
信号強度が高から低へと移行するとき、現在の安定した経路がゆっくり消滅する。
【００９３】
表１の信号強度またはL2品質は平均レベルを言及している。すなわち、比較的長い時間範囲の間のチャネル品質を表している。他方、fDまたはVSは短い時間範囲で定義されている。この点で、長短の定義は本発明を実装するシステムに依存する。長い時間範囲は、いくつかのトラヒック・フレームの範囲をカバーしていると定義できる。他方、短い時間範囲は、いくつかの送信シンボルまたはビットの範囲をカバーしていると定義できる。従って、短時間での速いチャネル変化は、ランダム・ビット・エラーの原因となることがある。これはFEC技術（前進型誤信号訂正）によって回復できる。FECは、情報部分（システマチック・ビットと呼ぶことがある）とそのパリティ部分を異なる時刻に運ぶからである。時刻が十分離れていれば、二つの時刻間には時間チャネル相関はないので、FECは時間ダイバーシチ効果をもたらす。そうなれば情報部分もパリティ部分もフェーディングを免れて生き延びる。その後、FEC機能が正しい情報を修復する。
【００９４】
これらのケースから、特に経路更新に関してアドホックルーティングプロトコルを予測的に修正できることが明らかである。
【００９５】
反応型と先行型の両方のアドホックルーティングプロトコルについて、この方法を使った例をいくつかあげよう。
【００９６】
ルーティングが先行型プロトコルに基づいているのなら、ルーティングテーブルは使用するプロトコルに応じて通常の手順で定期的に更新される。該プロトコルの一つがDSDVである。DSDVはネットワーク内のノードのルーティングテーブルを維持する。ルーティングプロトコルを状態測定に従って修正し、それに従ってルーティングテーブルに追加のリストを加えて、リンク状態を表示する。選択したルーティングプロトコルに応じた通常の技術を用いて、例えば「ハロー・メッセージ」やトポロジ・メッセージを用いて、リンク状態情報を配布する。
【００９７】
例えば、図5Aに示すように、データパケットをノードA 501からノードC 503へ送信する場合、データパケットはノードB 502を通って伝送される。しかし、ノードB 502とノードC 503間の現在のリンク状態は、この例では終わりつつある（すなわち、信号強度が低下しつつある）ことがわかり、動作的にはバーストで（すなわち、フェーディングまたはVSパラメータが閾値より低いと測定された）、しかもシステムは測定の結果から、ノードD504を通る経路の方が品質が良いことも知っているので、ルーティング要素101は、次のパケットは、ノードB 502を経由する古い経路505、506ではなく、ノードD504を経由して送信すべきだと決定する。この経路の変更を図5Bに示す。
【００９８】
先行型ルーティングプロトコルに従ったルーティング方法は以下に説明したアルゴリズムで例示されても良い。（図７Bも参照のこと）。
1. 無線アドホック・ネットワーク内のすべてのノードは、隣接ノードに対する各自のリンク品質を定期的に測定する。
2. すべてのリンク品質情報を、無線アドホック・ネットワークのすべてのノードに配布し、決定されたルーティング更新頻度で、各自のルーティングテーブルを更新並びに保存する。
3. データパケットの発生元であるソース・ノードが、リンク品質情報と予測モデルを使って適切な経路を決定する。
4. データパケットを、決定した経路に従って、宛先ノードへ送信する。
【００９９】
ルーティングが反応型ルーティングプロトコルに基づいている場合は、少し違う方法を用いる。経路の決定は先行型プロトコルと同じように定期的に更新するのではなく、オン・デマンドで更新する。パケット送信要求と、パケット送信経路の少なくとも一部を知る必要とに応じて、ルーティングプロトコルが反応する。
【０１００】
図3は反応型ルーティングプロトコルにおける修正された経路発見の一例を示している。図3に示すように、リンク状態情報304、305、306が、ソース・ノード300に返信された経路発見情報を定義する通常の経路応答(RREP)メッセージに含まれている。この情報を使ってルーティング要素101は、現在アクティブな経路について取得した情報に応じてデータ・パケットの経路を変更しても良い。経路応答(RREP)メッセージに含まれる状態情報は、修正された経路応答(RREP)メッセージ313、314、315を生じさせ、それがルーティング要素101に情報を提供し、現在のリンク状態の取得と、ソース300と宛先ノード303間のチェーンに含まれる全リンクについて近い将来のリンク状態の予測とが行われる。ルーティングチェーン中の各ノードについてのリンク状態情報を、修正された経路応答(RREP)メッセージに追加する。
【０１０１】
図3では、典型的な4つのノードがパケット・トランザクションに関与している。1個のパケットが、ソース・ノード300から宛先ノード303まで2個の中間ノード301、302を経由して送信される。パケットが宛先ノード303まで送信されたとき、最後の中間ノード302は、修正された経路応答(RREP)メッセージ313を返信する。この修正された経路応答(RREP)メッセージ313は、最後の中間ノード302と宛先ノード303の間のリンク情報304についての情報を含んでいる。経路応答(RREP)メッセージはチェーンの中を前の中間ノード301まで返送され（図3の例では、これは中間ノード1の301である）、このノード301が、自分自身とチェーンの中の次のノード302（中間ノード2  302）の間のリンク間のリンク状態についての情報を追加する。経路応答(RREP)メッセージ315が最後にソース・ノード300に戻ったとき、メッセージはソース・ノード300と宛先ノード303間のネットワークルーティングチェーンの中の全リンクについての情報を含むことになる。この種の手法はネットワーク内のノード数にかかわらず用いることができる。図3に描いているのは4個のノードだけであるが、これは数を限定するものではないことを理解すべきである。ノードの数はもっと少なくても多くても良い。図3では経路応答(RREP)の中のL1情報のみを示しているが、各ノードに関連するL2情報および/またはルーティングに関連してインフラ・ノードのその他の部分からのその他の情報を含めても良い。この方法はアドホックをベースにした反応型ルーティングプロトコル、例えばAODVやDSRが使っても良い。
【０１０２】
反応型ルーティングプロトコルに従ったルーティング方法は、以下に説明したアルゴリズムで例示されても良い。（図７Aも参照のこと）。
1. 無線アドホック・ネットワーク内のすべてのノードは、隣接ノードに対する各自のリンク品質を定期的に測定する。
2. すべてのリンク品質情報を、無線アドホック・ネットワーク内の経路に参加しているすべてのノードに配布し、経路要求が発行された際に各自のルーティングテーブルを更新及びソートする。
3. ソース・ノードが、リンク品質情報と予測モデルを使って適切な経路を決定する。
4. 当該データパケットを、決定した経路に従って、送信する。
【０１０３】
アドホックをベースにした反応型ルーティングプロトコルで送信される標準的な経路エラー(RERR)信号を修正することも可能であり、これを図4に示す。この修正は、次のホップ406に関する障害の可能性を検出したノード402、修正された経路エラー(RERR)メッセージを送信することによって行われる。この修正されたRERRは、当該リンク406のリンク状態404についての情報を含んでおり、それをソース・ノード400に返信する。ネットワークチェーン401においてより手前にある複数の中間ノードがこの情報404をソース・ノード400へと中継する。ソース・ノード400の中のルーティング要素101がこの情報404を使い、それに従って経路を変更することがある。
【０１０４】
この修正された経路エラー(RERR)404の方法を使って、ネットワークチェーンでその後発生するリンク障害に因るパケット再送信を劇的に減らすことができる。通常は、ルーティングプロトコルがリンク障害を検出するまでにかなりの時間がかかるため、ルーティング要素101がリンク障害が発生したと判定してルーティング構成を変更するまでデータパケットの再送信を何度も試みる。この方法を使えば、リンク消滅前の経路変更が可能であるため、リンク障害に因る再送信の回数は減る、もしくはなくなることもある。
【０１０５】
ノード間のリンク状態についての情報があれば、予測モデルを使って、リンク障害の検出と同時に、同じ経路でデータを再送信する前に経路を変更することができる。それは標準的なルーティングプロトコルの通常手順と同じである。ルーティング要素101は、リンク状態取得方法、具体的には修正された経路エラー(RERR)メッセージを通じてリンク障害のことを知っているため、失敗した送信パケットは新規経路を使って再送信する。図5Aおよび5Bを使ってこのルーティングダイバーシチの一例を示す。ここでパケットはノードA 501からノードC 503まで、まずノードB 502を経由して送信され、リンク障害が発生した時点で、代わりにノードD 504を経由して同じパケットを再送信する。
【０１０６】
予測的な方法を使ったインテリジェントなルーティングモデルは、さまざまな分野に応用できる。例えば、一般的なまたは特別なイベントの際の警察による使用、災害や事故の際の救助隊による使用、戦場や訓練での軍隊による使用、住宅用および商業用通信ネットワークの無線アクセス・エリアの構築に使用することなどである。例えば、これらのアドホック・ネットワークを使って、他のブロードバンド・アクセス技術が少ないか接続費用が高い住宅地に、短距離で低コストの無線装置によるブロードバンドアクセスを構築することができる。商業地区においても、大企業や小企業へのブロードバンド・アクセスやいわゆるホットスポットでの無線接続の提供に使用しても良い。ホットスポットは、一定の区域、例えば空港のラウンジやホテルにおいて、ビジネスモデルによって有料または無料で通信アクセスを提供するという性質のものである。
【０１０７】
好適な実施例ではリンク状態モニタ102を使っているが、この機能はルーティング要素101に組み込んでも良いことに注意する必要がある。
【０１０８】
ルーティングプロトコルは使用する無線コード体系には依存しないので、いかなる無線タイプでも使用可能である。例えば、IEEEE802.11シリーズ （例えば IEEEE 802. 11a、IEEEE 802.11b、 IEEEE 802.11g等）、IEEE 802.15、IEEE 802.16、 HiperLAN、HomeRF、Bluetooth、IR （赤外線）、UWB （Ultra WideBand）、JTRS （Joint Tactical Radio System）、 3G （第3世代移動通信）, GPRS （General Packet Radio Service）, or EDGE （Enhanced Data rate for Global Evolution）の中の無線標準に話が及んでもよい。しかし、利用可能な無線標準は上記に限定されない。100 kHz から100 PHzまでの周波数帯の範囲内で機能する電磁放射に基づく伝送システムであればいかなるものにも適合することがある。それには、無線周波数、マイクロ波周波数、および、赤外、可視、紫外の周波数も含む。
【０１０９】
トラヒック・スケジューリングおよびアドホック経路ダイバーシチについて同じ著者らからこれと似た出願が同時に申請されており、引用することによって本文中に組み込まれる。
1.「アドホック経路ダイバーシチ（Ad hoc route diversity）」
2.「アドホック・トラヒック・スケジューリング（Ad hoc traffic scheduling）」
【０１１０】
好適な実施例では無線アドホック・ネットワークについて説明してきたが、同じ概念が優先ネットワークや固定無線ネットワークに適用できることにも注意を払うべきである。
【０１１１】
例示する目的で本発明について詳細に説明してきたが、そのような詳細説明の目的はあくまで例示であり、当業者であれば、請求項によって限定される場合を除いて、発明の範囲と精神から逸脱することなくそのバリエーションを実施できるということを理解する必要がある。
【図面の簡単な説明】
【０１１２】
【図１】本発明の好適実施例の層間概念における、一部の成分およびその各々の役割の概略を示すブロック図である。
【図２】時間に対する信号強度および変化速度パラメータの図解であり、低速または高速カテゴリの決定を支配する閾値を示している。
【図３】反応型ルーティングプロトコルについて、チャネル・状態情報とリンク品質情報がシステム内にどのように戻されるかを示す略図である。
【図４】反応型プロトコルについて、チャネル・状態予測がシステム内にどのように戻されるかを示す略図である。
【図５】小規模なアドホック・ネットワークと、このネットワーク内の二つのノード間で可能な経路の略図である。
【図６】無線アドホック・ネットワーク・トポロジの略図である。
【図７】反応型ルーティングアドホック・プロトコル（図７Ａ）および先行型アドホックルーティングプロトコル（図７Ｂ）のルーティングと経路決定プロセスの一部を示す概略ブロック図である。
【図８】ネットワーク内のノードを示す概略ブロック図である。
【図１】
2007529135.tif 000005
【図２】
2007529135.tif 000006
【図３】
2007529135.tif 000007
【図４】
2007529135.tif 000008
【図５】
2007529135.tif 000009
【図６】
2007529135.tif 000010
【図７】
2007529135.tif 000011
【図８】
2007529135.tif 000012
【国際調査報告】
2007529135.tif 000013
2007529135.tif 000014
2007529135.tif 000015