JP4024246B2 - マルチチャネル移動体アドホックネットワーク - Google Patents

Description

無線ネットワークの急速に発展している領域は、移動体アドホックネットワークである。物理的には、移動体アドホックネットワークは、複数の地理的に分散し、１つ以上の無線周波数チャネルにより無線で接続された潜在的な移動体ノードを有する。セルラネットワークや衛星ネットワークのような他の形式のネットワークと比較して、移動体アドホックネットワークの最も独特な特徴は、固定インフラが存在しないことである。ネットワークは、移動体ノードのみで構成され、ノードがその他のノードと送受信を行う進行中にネットワークが作られる。ネットワークは一般的には特定のノードに依存せず、あるノードがネットワークに加わり、また、あるノードがネットワークから去ると、ネットワークは動的に調整する。

アドホックネットワークは迅速に発展し、大量の必要な通信を提供することができる。アドホックネットワークにより、例えば単にコンピュータ又は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ルーティングはベストエフォート型ルーティングより要求されている。

また、前述のように、一般的なアドホックネットワークの帯域は限られている。従来のアドホックネットワークのルーティングプロトコルは、全てのノードが同じチャネルに不変にあることを仮定する。この単一のチャネル動作は、帯域の可用性の要因である。あるネットワークは伝送チャネルでのオーバーヘッドを低減するために別の制御チャネルを使用することがあるが、従来の移動体アドホックネットワークはパケットデータを伝送するために複数のチャネルを利用しない。

従って、前述の背景を鑑みると、複数のチャネルを効率的に利用するマルチチャネル移動体アドホックネットワークを提供することが本発明の目的である。

本発明による前記及び他の目的と特徴と利点は、複数のチャネルで移動体アドホックネットワークを動作する方法により提供される。ネットワークは、複数の無線移動体ノードと、複数のノードを複数のチャネルで相互に接続する複数の無線通信リンクを有する。この方法は、ソースノードで、複数のチャネルのそれぞれを通じてルート要求を送信し、宛先ノードへのルーティングを発見し、複数のチャネルのうちの少なくとも１つで宛先ノードへのルートを選択することを有する。ルート要求は複数のチャネルのそれぞれで連続して送信されてもよく、ルート要求はソースノードのチャネル識別子を有することが好ましい。

また、各中間ノードは、その中間ノードが要求されたルートに対応することができるか否かを決定し、そうである場合には、その他の中間ノードと宛先ノードのうちの一方にルート要求を転送してもよい。中間ノードは、複数のチャネルでルート要求を転送する。この要求を既に受信したノードは、この殺到を続けない。更に、この方法は、宛先ノードでルート要求を受信すると、発見ルート毎にソースノードへの応答を生成することを有することが好ましい。発見ルート毎にソースノードに応答を生成することは、発見ルートを通じて逆方向にソースノードに応答を返信することを有することが好ましい。ソースノードは、選択されたルートを通じて宛先ノードに伝送を送信し、その選択されたルートはいくつかのチャネルをまたがってもよい。

ルートを選択する前に、発見ルート毎に宛先ノードへの基準を計算することにより、ソースノードは発見ルートに優先順位を付けてもよい。その基準は、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づいてもよい。宛先ノードへの選択されたルートは、複数のチャネルのうちの１つより多くを有してもよい。換言すると、選択されたルートは、全体的に又は部分的にソースノードと異なるチャネルでもよい。

本発明のシステム形態は、複数の移動体ノードと、複数のチャネルで複数の移動体ノードを相互に接続する複数の無線通信リンクとを有するマルチチャネル移動体アドホックネットワークを対象とする。各移動体ノードは、無線通信リンクを介して複数のノードのうちの他のノードと無線で通信する通信装置と、通信装置を介して通信をルーティングするコントローラとを有する。コントローラは、複数のチャネルのそれぞれでルート要求を送信し、宛先ノードへのルーティングを発見するルート発見ユニットと、複数のチャネルのうちの少なくとも１つで宛先ノードへのルートを選択するルート選択ユニットとを有する。ルート発見ユニットは、複数のチャネルのそれぞれで連続してルート要求を送信してもよく、ルート要求はチャネル識別子を有してもよい。宛先ノードへの選択されたルートは、複数のチャネルのうちの１つより多くを有してもよい。

コントローラは、ノードが要求されたルートに対応できるか否かを決定し、そうである場合には、その他の中間ノードと宛先ノードのうちの一方にルート要求を転送するルート要求処理ユニットをさらに有してもよい。また、コントローラは、発見ルート毎にソースノードへのルート応答を生成する応答生成器を有してもよい。また、発見ルート毎にソースノードへの応答を生成することは、発見ルートを通じて逆方向にソースノードに応答を返信することを有することが好ましい。

コントローラはまた、選択ルートを通じて宛先ノードに伝送を送信するデータ伝送ユニットと、発見ルートに優先順位を付けるルート優先順位付けユニットとを有してもよい。また、優先順位付けは、発見ルート毎に宛先ノードへの基準を計算することを有してもよい。その基準は、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づいてもよい。

本発明について、添付図面を参照して以下に十分に説明する。図面には本発明の好ましい実施例を示している。しかし、本発明は多数の異なる形式で具体化されてもよく、ここに示された実施例に限定して解釈されるべきではない。むしろ、これらの実施例は、この開示が十分且つ完全であるように提供されたものであり、当業者に本発明の範囲を十分に伝えるものである。全体を渡って同様の数字は同様の要素を示し、代替の実施例で類似の要素を示すためにプライム表記法が使用されている。

当業者に明らかなように、本発明の部分は、方法、データ処理システム又はコンピュータプログラム製品として具体化されてもよい。従って、本発明のこの部分は、完全にハードウェアの実施例の形式を取ってもよく、完全にソフトウェアの実施例の形式を取ってもよく、また、ソフトウェアとハードウェア形式を組み合わせた実施例を取ってもよい。更に、本発明の部分は、媒体にコンピュータ読取可能プログラムコードを有するコンピュータ使用可能記憶媒体上のコンピュータプログラム製品でもよい。静的及び動的記憶装置、ハードディスク、光記憶装置並びに磁気記憶装置に限定されず、これらを含む如何なる適切なコンピュータ読取可能媒体も利用され得る。

本発明は、本発明の実施例による方法とシステムとコンピュータプログラム製品のフローチャート表示を参照して、以下に説明される。その表示のブロック及びその表示のブロックの組み合わせは、コンピュータプログラム命令により実装され得る。これらのコンピュータプログラム命令は、多目的コンピュータ、専用目的コンピュータ又は機械を製造するその他のプログラム可能データ処理装置のプロセッサに提供されてもよく、それにより、コンピュータ又はその他のプログラム可能データ処理装置のプロセッサを介して実行する命令は、ブロックに指定された機能を実装する。

このコンピュータプログラム命令はまた、コンピュータ又はその他のプログラム可能データ処理装置が特定の方法で機能するように指示し得るコンピュータ読取可能メモリに格納されてもよく、それにより、コンピュータ読取可能メモリに格納されたメモリは、フローチャートのブロックに指定された機能を実装する命令を有する製品を生じる。コンピュータプログラム命令はまた、コンピュータ又はその他のプログラム可能装置で一連の動作ステップを実行させ、コンピュータに実装された処理を作るように、コンピュータ又はその他のプログラム可能データ処理装置にロードされてもよく、それにより、コンピュータ又はその他のプログラム可能装置で実行する命令は、フローチャートのブロックに指定された機能を実装するステップを提供する。

まず、図１−５と図８を参照して、移動体アドホックネットワーク20でソースノードから宛先ノードへのルートを決定する方法について説明する。ネットワーク20は、中間に中間ノードA-C及びE-Nを備えてソースノードSと宛先ノードDを有する複数の移動体ノード30を有する。また、この例では、ノードYとZはその他の図示のノード30の通信範囲にない。ラップトップコンピュータや個人情報端末(PDA)や携帯電話のようなノード30は、当業者にわかるように、無線通信リンク32により接続されている。従来の移動体アドホックネットワークとは異なり、通信リンク32は、複数のチャネル(例えば３〜１０チャネルの間)で存在する。

方法が開始し(ブロック100)、図８のブロック102に示すように、ソースノードSからルート要求RREQを送信し、複数のチャネルで宛先ノードDへのルーティングを発見することを有する。ソースノードSは、宛先ノードDが通常に何のチャネルにあるかを現時点で認識していない。図１に示す例において、ソースノードは中間ノードA-Cにルート要求RREQを送信する。例えば、ソースノードSとノードCは、通常は第１のチャネルにあり、ノードBは通常は第２のチャネルにあり、ノードAは通常は更に第３のチャネルにある。従って、ソースノードSは、ネットワークが現在動作しており、１ホップ内の全てのノード30に到達する全ての既存のチャネルで、ルート要求RREQを送信する。ルート要求RREQは、ソースノードSが何のチャネルにあるかを示すソースノードのチャネル識別子を有することが好ましい。

別々に、各チャネルでルート発見が通常通り処理される(図２)。各中間ノードAとBとCは、ノードがルート要求RREQに対応できるか否かを決定する。ノードが特定の要求RREQに対応できない場合、要求は拒否されるか、又はノードにより単に転送されない。ノード(例えばノードA)が特定の要求RREQに対応することができる場合、ノードは、全チャネルでルート要求RREQを他の中間ノード(例えばノードH)に転送し、要求がベストエフォート型以外のトラヒックである場合には、そのルート要求に対するノードのリソースを一時的に予約する。ベストエフォート型の場合には、必ずしもリソースが予約される必要はない。ルート要求RREQは最終的には宛先ノードDに転送される。

図３に示すように、宛先ノードDは、ルート要求RREQを受信すると、ソースノードSへの応答RREPを生成する(ブロック104)。しかし、図４に示すように、宛先ノードDは、多様な可能なルートのうちのいずれか(例えばS-A-H-J-D又はS-B-G-K-D)から転送されたルート要求RREQを受信している可能性がある。それぞれの場合について応答RREPQが生成される。応答RREPはSからDへの発見ルートを有し、宛先ノードDにより受信されたルート要求RREQに追加されたルートを逆にすることにより得られたルートを通じて、ソースノードSに返信される。図３と図４に示す例では、ノードDとJとHとAがソースノードSと異なるチャネルにある場合、最後のホップAは、ソースノードSと同じチャネルに移動しなければならず、その通常のチャネルの表示を有する応答RREPを送信する。RREPは、ルートを通じたノードのリストを有するだけでなく、各ノードがどのチャネルにあるかを有する。

ソースノードSは、最初のホップノードへのチャネルを有する各発見ルートをキャッシュする。ブロック106において、ソースノードSは、発見ルート毎に宛先ノードDへの基準を計算することにより、発見ルートを優先順位付けてもよい。基準は、例えば、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づいてもよい。宛先ノードへの選択されたルートは、複数のチャネルのうちの１つより多くを有してもよい。換言すると、選択されたルートは、全体的に又は部分的にソースノードと異なるチャネルでもよい。

また、ブロック108において、ソースノードSはルート基準に基づいて宛先ノードDへのルートを選択し、選択されたルートの中間ノードにルート確認CONFQを送信することが好ましい。これは、一時的に予約されている選択されたルートでリソースの使用を確認するためのものである。発見ルートであるが選択されていないルートにおける他の一時的に予約されたリソースは、このルートにCONFQを送信しないことにより、タイムアウトになってもよい。CONFQの使用は、ベストエフォート型以外のQoSを必要とするトラヒックに対して、リソースの使用を確認することに関連する。ベストエフォート型のルート発見は、各中間ノードでリソースを予約することを有する必要はない。ルートが選択されると、ブロック110において、選択されたルートを介して適切なチャネルでソースノードSから宛先ノードDにメッセージ／パケットデータが送信されてもよい。その結果、方法が終了する(ステップ112)。ここで使用される“メッセージデータ”は、当業者にわかるように、追加のルート要求／応答、映像データ、音声データ、英数字データ等を含み(これらに限定されない)、移動体アドホックネットワークのノード間で送信され得る如何なるデータをも有することを意図している。

説明した方法は、当業者にわかるように、Dynamic Source Routing(DSR)若しくはAd-Hoc On-Demand Distance Vector(AODV)のような如何なる種類のオンデマンド型又はリアクティブ型ルーティングプロトコル、又はZone Routing Protocol(ZRP)のような如何なるハイブリッド型プロアクティブ型／リアクティブ型プロトコルにも適用可能である。異なるチャネルにあることがある最善のルート範囲のノードを発見するために、プロアクティブ型ルーティングプロトコルで同様の手法が使用されてもよい。

説明した手順は、DSRプロトコルに容易に適用される。従来のDSRメッセージ形式RREQ、RREP、RRERは、任意選択のパケット形式として規定されており、下位互換性モードでの“ベストエフォート型”トラヒックに対応するプロトコルの従来の動作用に規定されたものとして使用され得る。変更された任意選択のパケット形式は、マルチチャネルのルーティングに対応するために規定されてもよい。この形式の所要のヘッダフィールドの定義は、前述の機能に基づくと簡単である。特別の種類のミッションデータについてのソースのルーティングパケットもまた含まれてもよい。

図６と図７を更に参照すると、本発明のシステム形態が記載されている。前述のように、移動体アドホックネットワーク20は、複数の移動体ノード30と、複数の移動体ノードを相互に接続する複数の無線通信リンク32とを有する。各移動体ノード30は、複数のチャネルで複数の通信リンク32を介して他のノードと無線で一方向又は双方向に通信する通信装置42を有するルータ40(図６)と、通信装置42を介して通信をルーティングするコントローラ44とを有する。また、メモリ46もコントローラ44の一部として、又はコントローラと接続して含まれてもよい。

図７に示すように、コントローラ44は、複数のチャネルのそれぞれでルート要求RREQを送信し、宛先ノードDへのルーティングを発見するルート発見ユニット50と、複数のチャネルのうちの少なくとも１つで宛先ノードへのルートを選択するルート選択ユニット52とを有する。ルート発見ユニット50は、複数のチャネルのそれぞれで連続してルート要求を送信してもよく、ルート要求はチャネル識別子を有してもよい。宛先ノードへの選択されたルートは、複数のチャネルのうちの１つより多くを有してもよい。

コントローラ44は、ノード30が要求されたルートに対応することができるか否かを決定し、そうである場合には、その他の中間ノードと宛先ノードDのうちの一方にルート要求RREQを転送するルート要求処理ユニット54を更に有してもよい。また、コントローラ44は、発見ルート毎にソースノードSへのルート応答RREPを生成する応答生成器46を有してもよい。また、発見ルート毎にソースノードSへの応答RREPを生成することは、発見ルートを通じて逆方向にソースノードに応答を返信することを有することが好ましい。

コントローラ44はまた、選択されたルートを通じて宛先ノードDにメッセージ／伝送を送信するデータ送信ユニット58と、発見ルートに優先順位を付けるルート優先順位付けユニット60とを有してもよい。また、優先順位付けは、発見ルート毎に宛先ノードへの基準を計算することを有してもよい。その基準は、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づいてもよい。

本発明は、同じ出願人により2002年4月29日に出願された同時係属出願第10/134,862号(代理人管理番号51261号)に記載されているように、移動体アドホックネットワークにおける動的チャネル割り当てを利用し、複数のチャネルを効率的に利用することができる。その全てが参照として取り込まれる。IEEE802.11は、5GHz帯域でISMスペクトルを利用する802.11aのように、スピンオフを行っている。この帯域では、多数のチャネルに対応するように利用可能な帯域が多く存在する。結果として、802.11ノードにチャネルを自動的に割り当てる処理が重要になる。このようなチャネルの決定は、現在のチャネル利用とその他のチャネルのサンプリングに基づく。動的チャネル選択の使用は、スペクトルが均等に使用されるため、より良い性能を提供する。更に、チャネルを使用する現在の局でサービス品質(QoS)が維持されるように、チャネルが調整されてもよい。

本発明によるマルチチャネル移動体アドホックネットワークの概略図である。 本発明によるマルチチャネル移動体アドホックネットワークの概略図である。 本発明によるマルチチャネル移動体アドホックネットワークの概略図である。 本発明によるマルチチャネル移動体アドホックネットワークの概略図である。 本発明によるマルチチャネル移動体アドホックネットワークの概略図である。 本発明のネットワークによるノードのルータを示した概略図である。 図６のルータのコントローラの詳細を示した概略図である。 本発明による移動体アドホックネットワークのマルチチャネルルーティングの方法のステップを示したフローチャートである。

Claims (8)

1. 複数の無線移動体ノードと、前記複数のノードを複数の電気的に別の無線チャネルで相互に接続する複数の無線通信リンクとを有する移動体アドホックネットワークを動作する方法であって、
   ソースノードで、前記複数の電気的に別のチャネルのそれぞれでルート要求を送信し、宛先ノードへのルーティングを発見し、
   各中間ノードで、前記中間ノードが要求されたルートに対応することができるか否かを決定し、そうである場合には、前記複数の電気的に別のチャネルのそれぞれで他の中間ノードと前記宛先ノードに前記ルート要求を転送し、
   前記宛先ノードで、前記ルート要求を受信すると、発見ルート毎に前記ソースノードへの応答を生成し、
   前記ソースノードで、前記複数の電気的に別のチャネルのうちの少なくとも１つで前記宛先ノードへのルートを選択し、
   前記選択されたルートを通じて前記宛先ノードに伝送を送信することを有する方法。
2. 請求項１に記載の方法であって、
   前記ソースノードは、前記複数のチャネルのそれぞれで連続して前記ルート要求を送信する方法。
3. 請求項１に記載の方法であって、
   前記ソースノードで、発見ルートに優先順位を付けることを更に有する方法。
4. 請求項３に記載の方法であって、
   優先順位付けは、前記宛先ノードへの発見ルート毎に基準を計算することを有し、
   前記基準は、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づく方法。
5. 複数の移動体ノードと、複数の電気的に別の無線チャネルで前記複数の移動体ノードを相互に接続する複数の無線通信リンクとを有する移動体アドホックネットワークであって、
   各移動体ノードは、
   前記無線通信リンクを介して前記複数のノードのうちの他のノードと無線で通信する通信装置と、
   前記通信装置を介して通信をルーティングするコントローラであり、
   前記複数の電気的に別のチャネルのそれぞれでルート要求を送信し、宛先ノードへのルーティングを発見するルート発見ユニットと、
   前記複数の電気的に別のチャネルのうちの少なくとも１つで前記宛先ノードへのルートを選択するルート選択ユニットと
   を有するコントローラと
   を有する移動体アドホックネットワーク。
6. 請求項５に記載の移動体アドホックネットワークであって、
   前記コントローラは、ノードが要求されたルートに対応できるか否かを決定し、そうである場合には、他の中間ノードと前記宛先ノードのうちの一方に前記ルート要求を転送するルート要求処理ユニットを更に有する移動体アドホックネットワーク。
7. 請求項５に記載の移動体アドホックネットワークであって、
   前記コントローラは、発見ルートに優先順位を付けるルート優先順位付けユニットを更に有する移動体アドホックネットワーク。
8. 請求項７に記載の移動体アドホックネットワークであって、
   前記優先順位付けユニットは、発見ルート毎に前記宛先ノードへの基準を計算し、
   前記基準は、利用可能な帯域、誤り率、エンドツーエンドの遅延、エンドツーエンドの遅延の変化、ホップ数、期待パス耐久性及び優先度のうちの少なくとも１つに基づく移動体アドホックネットワーク。

Images