(57)【要約】移動体アドホックネットワークは、ソースノード(1)と宛先ノード(4)の間の複数の中間移動体ノード(2,3,5)と、ノードを接続する複数の無線通信リンクとを有する。ソースノードは宛先ノードへのルーティングを発見し、少なくとも１つのリンク基準に従って発見ルートをランク付けし、ランクに基づいて宛先ノードにメッセージデータを配信する。リンク基準は、リンク遅延、リンク容量、リンク使用可能容量、及び／又はリンク信頼性の測定を有してもよい。
2005535256.tif 000002
【特許請求の範囲】
【請求項１】
ソースノードと宛先ノードとの間の複数の中間ノードと、前記ノードを相互に接続する無線通信リンクとを有する移動体アドホックネットワークにおいて、ソースノードから宛先ノードにメッセージデータをルーティングする方法であって、
前記ソースノードで、前記宛先ノードへのルーティングを発見し、
前記ソースノードで、少なくとも１つのリンク基準に従って発見ルートをランク付け、
前記ソースノードで、ランクに基づいて複数の発見ルートを通じて前記宛先ノードに前記メッセージデータを配信することを有する方法。
【請求項２】
請求項１に記載の方法であって、
前記発見ルートをランク付けることは、ルートキャッシュにルートエントリーを格納することを有し、
各ルートエントリーは、前記発見ルートの１つに対応する方法。
【請求項３】
請求項２に記載の方法であって、
各ルートエントリーは、
前記リンク基準の基準値と、
前記メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と
を有する方法。
【請求項４】
請求項３に記載の方法であって、
各ルートエントリーは、前記発見ルートを終了するタイマー値を更に有する方法。
【請求項５】
請求項１に記載の方法であって、
前記ソースノードで、故障のルートを検出し、前記発見ルートから故障のルートを取り除くことを更に有する方法。
【請求項６】
複数の移動体ノードと、前記複数の移動体ノードを相互に接続する複数の無線通信リンクとを有する移動体アドホックネットワークであって、
各移動体ノードは、
前記無線通信リンクを介して前記複数のノードのその他のノードと無線で通信する通信装置と、
前記通信装置を介して通信をルーティングし、
宛先ノードへのルーティングを発見するルート発見ユニットと、
少なくとも１つのリンク基準に従って発見ルートをランク付けるルートランク付けユニットと、
ランクに基づいて複数の発見ルートを通じて前記宛先ノードに前記メッセージデータを配信するメッセージデータ配信ユニットと
を有するコントローラと
を有する移動体アドホックネットワーク。
【請求項７】
請求項６に記載のネットワークであって、
前記ルートランク付けユニットは、前記発見ルートの１つにそれぞれ対応するルートエントリーを格納するルートキャッシュを有するネットワーク。
【請求項８】
請求項７に記載のネットワークであって、
各ルートエントリーは、
前記リンク基準の基準値と、
前記メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と
を有するネットワーク。
【請求項９】
請求項８に記載のネットワークであって、
各ルートエントリーは、前記発見ルートを終了するタイマー値更に有するネットワーク。
【請求項１０】
請求項６に記載のネットワークであって、
前記リンク基準は、リンク遅延、リンク容量、リンク使用可能容量及びリンク信頼性のうちの少なくとも１つの測定を有するネットワーク。
【請求項１１】
請求項６に記載のネットワークであって、
前記コントローラは、前記ノードが前記ルート要求に対応し続けることができるか否かを決定し、そうでない場合には、故障のルートに対してエラー通知を生成するルート要求処理ユニットを更に有するネットワーク。
【発明の詳細な説明】
【背景技術】
【０００１】
無線ネットワークの急速に発展している領域は、移動体アドホックネットワークである。物理的には、移動体アドホックネットワークは、複数の地理的に分散し、１つ以上の無線周波数チャネルにより無線で接続された潜在的な移動体ノードを有する。セルラネットワークや衛星ネットワークのような他の形式のネットワークと比較して、移動体アドホックネットワークの最も独特な特徴は、固定インフラが存在しないことである。ネットワークは、移動体ノードのみで構成され、ノードがその他のノードと送受信を行う進行中にネットワークが作られる。ネットワークは一般的には特定のノードに依存せず、あるノードがネットワークに加わり、また、あるノードがネットワークから去ると、ネットワークは動的に調整する。
【０００２】
アドホックネットワークは迅速に発展し、大量の必要な通信を提供することができる。アドホックネットワークにより、例えば単にコンピュータ又はPDAのスイッチを入れることにより作るネットワーク構造以外のネットワーク構造を使用せずに、フィールドやクラスルームでデータを交換することが可能になる。
【０００３】
移動体アドホックネットワークの新しいアプリケーションが出現し続け、通信構造の重要な部分になるであろう。固定インフラがないため、ノードは自己組織化し、ネットワークを移動し、加わり又は去ると共に、再構成しなければならない。潜在的には、全てのノードは機能的に同一であり、ネットワークに自然の階層又は中央コントローラは存在する必要がない。多数のネットワーク制御機能はノード間に分散されている。ノードは、しばしばバッテリにより電力供給され、限られた通信機能及び計算機能を有する。システムの帯域は通常は限られている。２つのノード間の距離は、しばしば無線伝送範囲を超過し、宛先に到達する前に他のノードにより伝送が中継されなければならない。従って、ネットワークはマルチホップトポロジを有し、ノードが移動すると、このトポロジが変化する。
【０００４】
インターネット特別技術調査委員会(IETF:  Internet  Engineering  Task  Force)の移動体アドホックネットワーク(MANET:  Mobile  Ad-Hoc  Network)ワーキンググループは、マルチキャストを含むルーティングプロトコルについて積極的に評価し、標準化している。ノードが移動すると任意にネットワークトポロジが変化するため、情報は陳腐化の対象になり、異なるノードは、時間的にも(あるノードでは情報が時代遅れになるが、あるノードでは現在のものになる)、空間的にも(ノードは自ノードから一般的に遠くない周辺のネットワークトポロジのみを認識することがある)、しばしばネットワークの異なる視野を有している。
【０００５】
ルーティングプロトコルは、あまり正確でない情報で、頻繁なトポロジの変化に適応する必要がある。この独特の要件のため、このネットワークにおけるルーティングは、その他のものと非常に異なる。全体ネットワークについて新しい情報を収集することは、しばしば高コスト且つ非現実的である。多くのルーティングプロトコルはリアクティブ(オンデマンド)型プロトコルである。そのようなプロトコルは、必要な時にルーティングする必要のある宛先に対してのみルーティング情報を収集し、一般的にある一定期間後に未使用のルートを保持しない。このように、ルーティングのオーバーヘッドは、全ての時間での全ての宛先へのルートを維持するプロアクティブ型プロトコルに比較して非常に低減される。プロトコルが適応的であることは重要である。Ad  Hoc  on  Demand  Distance  Vector(AODV)と、Dynamic  Source  Routing(DSR)と、Temporally  Ordered  Routing  Algorithm(TORA)は、MANETワーキンググループで提示されているオンデマンド型ルーティングプロトコルの代表である。
【０００６】
他の多様なルーティングプロトコルの例には、Perkinsの米国特許第5,412,654号に開示されているDestination-Sequenced  Distance  Vector(DSDV)ルーティングと、Haasの米国特許第6,304,556号に開示されているZone  Routing  Protocol(ZRP)が含まれる。ZRPは、ソースノードからの距離に基づいて、プロアクティブ型手法とリアクティブ型手法の双方を使用したハイブリッド型プロトコルである。
【０００７】
この従来のルーティングプロトコルは、ソースノードから宛先ノードへのルートを選択する際にベストエフォート型手法を使用する。一般的に、このようなベストエフォート型手法では、ホップ数が主要な基準(測定基準)である。換言すると、最小ホップ数を有するルートが伝送ルートとして選択される。
【０００８】
移動体アドホックネットワークにおけるサービス品質(QoS)ルーティングが関心を得ている。サービス品質を提供するために、プロトコルはルートを発見するだけではなく、ルートを通じたリソースを保証する必要がある。ネットワークの限られた共有帯域のため、また、この限られたリソースに責任を持って管理することができる中央コントローラがないため、ノードは相互に交渉してQoSルートに必要なリソースを管理しなければならない。このことは、頻繁なトポロジ変化により更に複雑になる。このような制約のため、QoSルーティングはベストエフォート型ルーティングより要求されている。
【０００９】
QoSルーティング手法のいくつかの例は、Chenxi  Zhuによる2001年の“Medium  Access  Control  and  Quality-of-Service  Routing  for  Mobile  Ad  Hoc  Networks”という題の刊行物と、Mirhakkak他による2000年のMITRE  Corp.の“Dynamic  Quality-of-Service  for  Mobile  Ad  Hoc  Networks”という題の刊行物に示されている。Zhuはトポロジが小〜中の変化率で変化する小規模ネットワークにおいて帯域保証のQoSルートを確立することについて説明している。Mirhakkak他は、ネットワークがその範囲内でサービスを提供する義務を行う一方で、QoS値の範囲を特定するリソース予約要求を主題としている。
【００１０】
DSRやAODVのようなリアクティブ型ルーティングプロトコルの性能と信頼性は、移動体アドホックネットワークの分野で重要である。従来のDSRは複数のパスを検出するが、メッセージデータ／ミッショントラヒックの伝送には単一のパスのみを使用する。残りのパスはバックアップになり得るが、必要な時にはしばしば陳腐化する。従来では、AODVは単一のパスを検出する。主要パスの故障により、ミッショントラヒックが新たなルート発見処理の完了を待機しなければならないため、しばしばかなりの遅延を生じる。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従って、前述の背景を鑑みると、移動体アドホックネットワークにおいて小さいトラヒック負荷の集中で、より信頼性のあるタイムリーなルートを提供することが、本発明の目的である。
【課題を解決するための手段】
【００１２】
本発明による前記及び他の目的と特徴と利点は、移動体アドホックネットワークにおいてソースノードから宛先ノードにメッセージデータをルーティングする方法により提供される。移動体アドホックネットワークは、ソースノードと宛先ノードとの間に複数の中間ノードを有し、複数の無線通信リンクがノードを相互に接続する。その方法は、ソースノードで、宛先ノードへのルーティングを発見し、少なくとも１つのリンク基準に従って発見ルートをランク付け、ランクに基づいて複数の発見ルートを通じて宛先ノードにメッセージデータを配信することを有する。リンク基準は、リンク遅延、リンク容量、リンク使用可能容量及び／又はリンク信頼性の測定を有してもよい。
【００１３】
メッセージデータを配信することは、複数の発見ルートを通じて複製のメッセージデータを配信し、及び／又は複数の発見ルートのそれぞれを通じてメッセージデータの異なる部分を配信することを有してもよい。また、発見ルートをランク付けることは、発見ルートの１つに対応する各ルートエントリーを備えたルートキャッシュにルートエントリーを格納することを有することが好ましい。各ルートエントリーは、基準値と、メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と、発見ルートを終了するタイマー値とを有してもよい。ルートエントリーは、遅延に敏感なメッセージデータや大量のメッセージデータのように、異なるクラスのメッセージデータについてルートキャッシュで繰り返されてもよい。
【００１４】
その方法はまた、ソースノード、中間ノード及び／又は宛先ノードで、ノードがルート要求に対応し続けることができるか否かを検出し、そうでない場合には、故障のルートに対してエラー通知を生成することを有してもよい。エラー通知を受信すると、ソースノードは、発見ルートから故障のルートを取り除き、残りの発見ルートの中でメッセージデータを配信することが好ましい。更に、ソースノードは、発見ルートの数が閾値より小さくなると、宛先ノードへの新しいルーティングを発見する第２のルート要求を送信してもよい。
【００１５】
本発明による目的と特徴と利点はまた、複数の移動体ノードと、複数の移動体ノードを相互に接続する複数の無線通信リンクとを有する移動体アドホックネットワークによっても提供される。各移動体ノードは、無線通信リンクを介して複数のノードのその他のノードと無線で通信する通信装置と、通信装置を介して通信をルーティングするコントローラとを有する。コントローラは、宛先ノードへのルーティングを発見するルート発見ユニットと、少なくとも１つのリンク基準に従って発見ルートをランク付けるルートランク付けユニットと、ランクに基づいて複数の発見ルートを通じて宛先ノードにメッセージデータを配信するメッセージデータ配信ユニットとを有する。リンク基準は、リンク遅延、リンク容量、リンク使用可能容量及び／又はリンク信頼性の測定であることが好ましい。
【００１６】
メッセージデータ配信ユニットは、複数の発見ルートを通じて複製のメッセージデータを配信し、及び／又は複数の発見ルートのそれぞれを通じてメッセージデータの異なる部分を配信してもよい。ルートランク付けユニットは、発見ルートの１つにそれぞれ対応するルートエントリーを格納するルートキャッシュを有する。また、各ルートエントリーは、基準値と、メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と、発見ルートを終了するタイマー値とを有してもよい。また、ランク付けユニットは、遅延に敏感なメッセージデータや大量のメッセージデータのように、異なるクラスのメッセージデータについてルートキャッシュでルートエントリーを繰り返してもよい。
【００１７】
また、コントローラは、ノードがルート要求に対応し続けることができるか否かを検出し、そうでない場合には、故障のルートに対してエラー通知を生成するルート要求処理ユニットを有してもよい。ルートランク付けユニットは、発見ルートから故障のルートを取り除き、ルート発見ユニットは、発見ルートの数が閾値より小さくなると、宛先ノードへの新しいルーティングを発見する。
【発明を実施するための最良の形態】
【００１８】
本発明について、添付図面を参照して以下に十分に説明する。図面には本発明の好ましい実施例を示している。しかし、本発明は多数の異なる形式で具体化されてもよく、ここに示された実施例に限定して解釈されるべきではない。むしろ、これらの実施例は、この開示が十分且つ完全であるように提供されたものであり、当業者に本発明の範囲を十分に伝えるものである。全体を渡って同様の数字は同様の要素を示し、代替の実施例で類似の要素を示すためにプライム表記法が使用されている。
【００１９】
当業者に明らかなように、本発明の部分は、方法、データ処理システム又はコンピュータプログラム製品として具体化されてもよい。従って、本発明のこの部分は、完全にハードウェアの実施例の形式を取ってもよく、完全にソフトウェアの実施例の形式を取ってもよく、また、ソフトウェアとハードウェア形式を組み合わせた実施例を取ってもよい。更に、本発明の部分は、媒体にコンピュータ読取可能プログラムコードを有するコンピュータ使用可能記憶媒体上のコンピュータプログラム製品でもよい。静的及び動的記憶装置、ハードディスク、光記憶装置並びに磁気記憶装置に限定されず、これらを含む如何なる適切なコンピュータ読取可能媒体も利用され得る。
【００２０】
本発明は、本発明の実施例による方法とシステムとコンピュータプログラム製品のフローチャート表示を参照して、以下に説明される。その表示のブロック及びその表示のブロックの組み合わせは、コンピュータプログラム命令により実装され得る。これらのコンピュータプログラム命令は、多目的コンピュータ、専用目的コンピュータ又は機械を製造するその他のプログラム可能データ処理装置のプロセッサに提供されてもよく、それにより、コンピュータ又はその他のプログラム可能データ処理装置のプロセッサを介して実行する命令は、ブロックに指定された機能を実装する。
【００２１】
このコンピュータプログラム命令はまた、コンピュータ又はその他のプログラム可能データ処理装置が特定の方法で機能するように指示し得るコンピュータ読取可能メモリに格納されてもよく、それにより、コンピュータ読取可能メモリに格納されたメモリは、フローチャートのブロックに指定された機能を実装する命令を有する製品を生じる。コンピュータプログラム命令はまた、コンピュータ又はその他のプログラム可能装置で一連の動作ステップを実行させ、コンピュータに実装された処理を作るように、コンピュータ又はその他のプログラム可能データ処理装置にロードされてもよく、それにより、コンピュータ又はその他のプログラム可能装置で実行する命令は、フローチャートのブロックに指定された機能を実装するステップを提供する。
【００２２】
まず、図１から５を参照して、移動体アドホックネットワーク20における方法について説明する。ネットワーク20は、中間に中間ノード2と3と5を備えてソースノード1と宛先ノード4を有する複数の移動体ノード30を有する。当業者にわかるように、ラップトップコンピュータや個人情報端末(PDA)や携帯電話のようなノード30は、無線通信リンク32により接続されている。方法が開始し(ブロック100)、図５のブロック102に示すように、ソースノード1からルート要求RREQを送信し、宛先ノード4へのルーティングを発見することを有する。具体的には、所定の宛先ノード4に対して新しいルートが必要になると、ソースノード1はRREQパケットを宛先ノードにブロードキャストする。このRREQパケットは、DSR又はAODVのようなプロトコルで使用される従来のRREQパケットと類似するが、以下に詳細に説明するように、リンク／ルート基準を有してもよい。従来のRREQブロードキャストは“ベストエフォート型”サービスに使用される。本発明の方法は、ベストエフォート型サービスのプロトコルにより確立された従来の手順に依然として従ってもよい。
【００２３】
更に、ブロック104において、その方法は、各中間ノード2と3と5が、ノードがルート要求RREQに対応できるか否かを決定することを有する。ノードが特定の要求RREQに対応できない場合には、要求は拒否されるか、又は単にノードにより転送されない(ブロック106)。ノード(例えばノード3)が特定の要求RREQに対応できる場合には、ノードはルート要求をその他の中間ノード2と5に転送し(ブロック108)、そのルート要求について一時的にノードのリソースを予約してもよい。中間ノード2と5もまた、ノード3から転送されたルート要求RREQに対応できるか否かを決定しなければならない。そうである場合には、ルート要求RREQが宛先ノード4に転送される。
【００２４】
宛先ノード4は、ルート要求RREQを受信すると、発見ルート毎にソースノード1に応答RREPを生成する(ブロック110)。換言すると、宛先ノード4は、例えば1-2-4又は1-3-5-4を含む多様な可能なルートのうちのいずれかから、転送されたルート要求RREQを受信していることがある。それぞれの場合について応答RREPが生成される。ブロック112において、ソースノード1は１つ以上のリンク基準に従って発見ルートをランク付ける。以下に説明するように、リンク基準は、リンク遅延、リンク容量、リンク使用可能容量及び／又はリンク信頼性の測定であることが好ましい。
【００２５】
発見ルートをランク付けることは、ルートキャッシュ又はテーブルにルートエントリーを格納することを有することが好ましい。各ルートエントリーは、発見ルートの１つに対応する。また、各ルートエントリーは、基準値と、メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と、発見ルートを終了するタイマーとを有してもよい。ルートエントリーの一部又は全部は、遅延に敏感なメッセージデータ及び／又は大量のメッセージデータのように、異なるクラスのメッセージデータ／トラヒックについて繰り返されてもよい。
【００２６】
ブロック114において、ソースノード1は宛先ノード4への複数のルートを選択し、ブロック116において、ソースノードは選択されたルートで中間ノードにルート確認CONFを送信してもよい。これは、サービス品質ルーティングのように、ベストエフォート型手法以外のルーティング手法を使用するシステムにおいて、選択されたルートでリソースの使用を確認するためのものである。
【００２７】
また、ブロック118において、ソースノード1は、複数の発見ルート(例えば1-2-4や1-3-5-4等)を通じて宛先ノード4にメッセージデータを配信する。メッセージデータを配信することは、改善した信頼性のため、複数の発見ルートを通じて複製のメッセージデータを配信し、及び／又は改善した適時性のため、複数の発見ルートのそれぞれを通じてメッセージデータの異なる部分を配信することを有してもよい。ここで使用される“メッセージデータ”は、当業者にわかるように、映像データ、音声データ、英数字データ等を含み(これらに限定されない)、移動体アドホックネットワークのノード間で送信され得る如何なるデータをも有することを意図している。
【００２８】
ブロック120において、中間ノード2と3と5及び／又は宛先ノード4は、ノードがルート要求RREQに対応し続けることができるか否かを常に検出してもよい。ノードが要求RREQに対応し続けることができない場合、ノードはソースノード1に対してエラー通知RERRを生成する。ここで(ブロック112)、ソースノード1は、エラー通知RERRを受信すると、その他の発見ルートの使用を維持する一方で、故障のルートを取り除いてもよい。しかし、発見ルートの数が特定の閾値より下になると、ソースノード1はルート要求RREQを再送信し、宛先ノード4への新しいルートを発見してもよい(ブロック124)。
【００２９】
説明した方法は、当業者にわかるように、Dynamic  Source  Routing(DSR)若しくはAd-Hoc  On-Demand  Distance  Vector(AODV)のような如何なる種類のオンデマンド型又はリアクティブ型ルーティングプロトコル、又はZone  Routing  Protocol(ZRP)のような如何なるハイブリッド型プロアクティブ型／リアクティブ型プロトコルにも適用可能である。説明した手順は、DSRプロトコルに容易に適用される。従来のDSRメッセージ形式RREQ、RREP、RRERは、任意選択のパケット形式として規定されており、下位互換性モードでの“ベストエフォート型”トラヒックに対応するプロトコルの従来の動作用に規定されたものとして使用され得る。新しい任意選択のパケット形式は、特定のリンク基準の測定に対応するために規定されてもよい。この形式の所要のヘッダフィールドの定義は、前述の機能に基づくと簡単である。
【００３０】
前述のように、DSRやAODVのようなリアクティブ型アドホックルーティングプロトコルの性能は、小さいトラヒック負荷の集中で、より信頼性のあるタイムリーなルートを提供するように改善される。ルートはルート要求及びルート応答機構を介して発見される。従来のDSRは複数のパスを検出するが、メッセージデータ送信に単一のパスのみを使用し、残りのパスはバックアップになり得るが、必要な時にはしばしば陳腐化することに留意すべきである。従来では、AODVは単一のパスを検出する。主要パスの故障により、ミッショントラヒックが新たなルート発見処理の完了を待機しなければならないため、しばしばかなりの遅延を生じる。
【００３１】
前述のように、本発明は、宛先へのそれぞれに対して適切な基準で複数のルートの発見及び使用を提供する。発見されたパスは、基準及び／又はトラヒッククラスに従ってランク付けされる。ルーティングキャッシュ／テーブルは、宛先毎に同時にnルートまで利用できるように調整される(負荷の分配又は信頼性のために使用されてもよい)。トラヒックは、ランク及びパス基準により示された値に従って、複数のルートを通じて配信される。nのパスの使用により、単一のパスの故障でもn-1のパスが依然として動作中のままにできるため、nのパスの同時の管理が可能になる。
【００３２】
ルートキャッシュ／テーブルは、ルートのグループ(DSRのソースルート又はAODVの次のホップのルート)内に宛先のインデックスを有する。各ルートエントリーは、基準値と、トラヒック負荷のどの部分がそのルートを使用すべきかを示す使用因子(例えば0と1の間)と、ルートを終了するタイマーとを有する。使用中に、nまでのルートのうちの１つは、負荷が共有されることを可能にする何らかの手法(ランダム選択又は使用因子によるラウンドロビンサービス)に従って選択される。ルートエントリーはまた、トラヒックのクラス(例えば、異なる基準の使用及びクラス毎のランク付け)毎に繰り返されてもよい。
【００３３】
ルートの故障に関しては、ルートの故障を発見したノードは、ルートエラーパケット(RERR)を生成し、トラヒックのソースに返信する。トラヒックのソースは、キャッシュ／テーブルから故障のルートを取り除く。トラヒックのソースは、n-1の“良好な”ルートを使用し続ける。他のルートが(十分な基準で)利用可能である場合には、テーブルに追加され、nのルートを取得する。使用因子は再計算される。故障により、使用中のルートの数が所定の閾値より小さくなった場合、更なるルートを検出するために新しいルート発見処理が起動される。
【００３４】
基準の使用に関しては、ルート要求とルート応答は、改善した基準に対応するように変更される。DSRとAODVは、現在は所望のときに依然として使用され得るホップ数のみを使用する。改善した基準は、リンク遅延やリンク容量やリンク使用可能容量やリンク信頼性のような多様な測定を有することができる。より重要な基準はトラヒッククラスに依存してもよい。例えば、遅延に敏感なトラヒックは、ルートが遅延の基準に基づいてランク順位付けされることを必要としてもよい。大量のトラヒックは、ルートが容量の基準に基づいてランク順位付けされることを必要としてもよい。
【００３５】
ルート毎の使用因子は、使用因子(Rtek)=F(基準k,f(使用中の全パスの基準))として計算されてもよい。大量のトラヒックの場合、ボトルネック容量がルートを評価する差異の基準として使用されてもよい。すなわち、使用因子(Rtek)=ボトルネック容量k/((ルート毎のボトルネック容量)の全ルートの合計)である。
【００３６】
特にDSRに適用される本発明について説明する。DSRは、複数のルートを自然に収集するが、１つのみが使用される。ソースルートが全体パスを指示する(ループが容易に検出される)ため、複数のルートでループ無し(loop  freedom)が維持される。DSRは、ソースルートのリンク毎に適切な基準を収集するように変更される。DSRルートキャッシュは、ルート使用因子を使用して複数のクラスのトラヒックについて同時に複数のルートの使用を反映するように変更される。トラヒッククラス毎にルートをランク付けることは、ルートキャッシュで実装され、トラヒッククラス毎に上位のnルートが選択される。ソースルートが収集されているため、ランク付け処理は、どのnのパスが最も望ましいかを決定すると、パスの解体のような要素を有してもよい(解体のパスは、リンク／ノードの故障及び移動により同時に中断しそうにない一式のパスを提供する)。トラヒッククラス毎に上位のnルートの使用因子は、前記のように適切なパス基準に基づいて計算される。いくつかのパスの間でのトラヒック分配は、ソースノードのみで行われる。陳腐化したルーティングのキャッシュエントリーに対するタイマーが使用されてもよい(すなわち、任意選択である)。より高い信頼性のため、複数のルートで複製のトラヒックを送信する高い信頼性のトラヒッククラスが実装されてもよい。前述のように、ルート故障回復が実装される。これは、動作中の使用されている上位のnルートにおける何らかの陳腐化したルートを自然に発見する。
【００３７】
特にAODVに適用される本発明について説明する。現在の規定では、AODVは基準としてのパスホップ数で単一のルートのみを収集する。このように、AODVは適切な基準で複数のルートを収集するように変更されるべきである。AODVは次のホップのルーティングテーブルを構築するため、ループ無し(loop-free)のルートを確保するためにAODVでは注意が必要である。例えば、以下の保守的な手法が使える。複数のルートの使用と、上位のnルートのランク付けと、適切なパス基準に基づく上位のnルートの使用因子を反映するようにAODVルートテーブルを変更する。上位のnルートのうちの１つを“最善のルート”として選択し、ループ無しを維持する。それは、AODVでは最も新しい最小ホップ数のルートとして選択される(上位のnに含まれる小さいルートは、1より大きいホップ数まで有することができる)。中間ノードは、“最善のルート”の選択のみを示すRREPを返信し、宛先は異なる周辺のものを通じたパスの複数のRREPを返信することができる。nの可能なパスのうちの１つの選択はソースノードでのみ生じる。各中間転送ノードは、“最善のルート”を通じてパケットを常に転送する。ノードが既に使用中のその他のルートより新しいルートを発見したとき、故障の場合又はホップ数が大きすぎる場合を除いて、他のルートを破棄する必要はない。より高い信頼性のため、複数のルートで複製のトラヒックを送信する高い信頼性のトラヒッククラスが実装されてもよい。ルートの故障は、RERRの生成を生じ、前記のように故障回復処理を起動することを生じる。このように、本発明は、DSRやAODVのような従来のアドホックルーティングプロトコルに対応するが、性能をかなり改善する。負荷バランシングのため、又はデータトラヒック配信の更なる可能性のため、複数のルートが使用され得る。複数のルートの使用は、パスの故障が生じたときにタイムリーなバックアップルートを提供することができる。多くの場合、故障は、故障のリンクで一時的に失われたトラヒック以外のデータトラヒックを中断しない。全ルートが全くルートのない可能性を低減できない前に、ルート発見は起動され得る。すなわち、全ルートが失われた後に起動されるルート発見は稀である。
【００３８】
更に図６と７を参照して、本発明のシステム形態について説明する。移動体アドホックネットワーク20は、複数の移動体ノード30と、複数の移動体ノードを相互に接続する複数の無線通信リンク32とを有する。各移動体ノードは、無線通信リンク32を介して他のノードと無線で一方向又は双方向に通信する通信装置42と、通信装置を介して通信をルーティングするコントローラ44とを有するルータ40(図６)を有する。また、コントローラ44の一部として、又はコントローラに接続して、メモリ46が含まれてもよい。
【００３９】
図７に示すように、コントローラ44は、他のノードにルート要求を送信し、宛先ノードへのルーティングを発見するルート発見ユニット50を有する。また、ルート要求処理ユニット52は、ノードがルート要求に対応し続けることができるか否かを決定する。更に、ルート要求処理ユニット52は、ノードがルート要求に対応し続けることができるか否かを検出し、そうでない場合には、エラー通知RERRを生成する。ルートランク付けユニット54は、１つ以上のリンク基準に従って発見ルートをランク付け、メッセージデータ配信ユニット58は、ランクに基づいて複数の発見ルートを通じて宛先ノードにメッセージデータを配信する。また、リンク基準は、リンク遅延、リンク容量、リンク使用可能容量及び／又はリンク信頼性の測定であることが好ましい。
【００４０】
メッセージデータ配信ユニット58は、複数の発見ルートを通じて複製のメッセージデータを配信し、及び／又は複数の発見ルートのそれぞれを通じてメッセージデータの異なる部分を配信してもよい。ルートランク付けユニット54は、発見ルートの１つにそれぞれ対応するルートエントリーを格納するルートキャッシュ56を有する。また、各ルートエントリーは、基準値と、メッセージデータのうちのどのくらいが対応するルートに配信されるべきかを示す使用因子と、発見ルートを終了するタイマー値とを有してもよい。また、ランク付けユニット54は、遅延に敏感なメッセージデータや大量のメッセージデータのように、異なるクラスのメッセージデータについてルートキャッシュでルートエントリーを繰り返してもよい。ルートランク付けユニット54は、発見ルートから故障のルートを取り除き、ルート発見ユニット50は、発見ルートの数が閾値より小さくなると、宛先ノードへの新しいルーティングを発見する。
【図面の簡単な説明】
【００４１】
【図１】本発明による移動体アドホックネットワークの概略図である。
【図２】本発明による移動体アドホックネットワークの概略図である。
【図３】本発明による移動体アドホックネットワークの概略図である。
【図４】本発明による移動体アドホックネットワークの概略図である。
【図５】本発明による移動体アドホックネットワークにおける方法のステップを示したフローチャートである。
【図６】本発明のネットワークによるノードのルータを示した概略図である。
【図７】図６のルータのコントローラの詳細を示した概略図である。
【図１】
2005535256.tif 000003
【図２】
2005535256.tif 000004
【図３】
2005535256.tif 000005
【図４】
2005535256.tif 000006
【図５】
2005535256.tif 000007
【図６】
2005535256.tif 000008
【図７】
2005535256.tif 000009
【国際調査報告】
2005535256.tif 000010
2005535256.tif 000011