(57)【要約】【課題】アドホックネットワークにおいて障害が発生したときに、エンドツーエンドの通信を切断することなく、経路を再確立する。【解決手段】記憶手段１０１は、複数のノードから構成されるアドホックネットワークの経路情報を記憶する。リクエスト送信手段１０２は、発信元ノードから宛先ノードまでの経路を探すとき、発信元ノードから宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信する。リプライ送信手段１０３は、宛先ノードから発信元ノードへリプライを返送するとき、宛先ノードから発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信する。制御手段１０４は、隣接ノードからリクエストまたはリプライを受信したとき、その隣接ノードを含む経路の情報を記憶手段１０１に登録する。【選択図】図１
2008193543.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークを構成する複数のノードのうちの１つに設けられた経路制御装置であって、
前記アドホックネットワークの経路情報を記憶する記憶手段と、
前記複数のノードのうち発信元ノードから宛先ノードまでの経路を探すとき、該発信元ノードから該宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信するリクエスト送信手段と、
前記宛先ノードから前記発信元ノードへリプライを返送するとき、該宛先ノードから該発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信するリプライ送信手段と、
隣接ノードから前記リクエストまたは前記リプライを受信したとき、該隣接ノードを含む経路の情報を前記記憶手段に登録する制御手段と
を備えることを特徴とする経路制御装置。
【請求項２】
前記記憶手段は、前記発信元ノードから前記宛先ノードまでの複数の経路を示す経路情報を記憶し、前記制御手段は、該複数の経路のうちの第１の経路を用いた通信が開始された後通信状態が悪化すると、該経路情報を参照して、該第１の経路から該複数の経路のうちの第２の経路へ切り替える切り替え処理を開始することを特徴とする請求項１記載の経路制御装置。
【請求項３】
前記制御手段は、前記第２の経路に含まれる隣接ノードに対して、該隣接ノードの次段のノードを示すノード識別情報を含み前記切り替え処理を指示する代替経路形成指示を送信することを特徴とする請求項２記載の経路制御装置。
【請求項４】
前記制御手段は、前記第２の経路に含まれる隣接ノードが前記次段のノードへの経路を示す経路情報を記憶していないとき、前記第１の経路から前記複数の経路のうちの第３の経路へ切り替える切り替え処理を開始することを特徴とする請求項３記載の経路制御装置。
【請求項５】
前記記憶手段は、前記複数の経路のそれぞれに対応する複数のノード列を示すノード列情報をさらに記憶することを特徴とする請求項２、３、または４記載の経路制御装置。
【請求項６】
複数のノードから構成されるアドホックネットワークにおける経路制御方法であって、
前記複数のノードのうち発信元ノードから宛先ノードまでの経路を探すとき、該発信元ノードから該宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信する処理を繰り返し、
隣接ノードから前記リクエストを受信したノードに、該隣接ノードを含む経路の情報を登録し、
前記宛先ノードから前記発信元ノードへリプライを返送するとき、該宛先ノードから該発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信する処理を繰り返し、
隣接ノードから前記リプライを受信したノードに、該隣接ノードを含む経路の情報を登録する
ことを特徴とする経路制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線で接続できる端末等のノード装置から構成されたアドホックネットワークの経路（route ）を制御する装置および方法に関する。
【背景技術】
【０００２】
アドホックネットワークの経路制御プロトコルは、用途別にいくつかの種類が存在する。このうち、ＡＯＤＶ（Adhoc On-Demand Distance Vector）プロトコルは、リアクティブ系に属し、オンデマンドで通信経路を確立するプロトコルである（例えば、下記の非特許文献１を参照）。リアクティブ系では、各ノードに通信要求があったときに、周囲に存在するノードを確認してルーティングテーブルが作成される。
【０００３】
従来のＡＯＤＶプロトコルでは、発信元（source）から宛先（destination ）までの経路を探すときに、フラッディング（flooding）処理により、ルートリクエストが通信可能なすべてのパスを通っていく。そして、ルートリクエストが宛先に到達すると、最善の一本の経路のみを通ってリプライが返送される。
【０００４】
アドホックネットワークを構成する各ノードは、従来の有線系で用いられているルーティングテーブルと同様のフォーマットで、宛先アドレス、次ホップアドレス、ホップカウント等の情報を保持する。そして、パケットを回送（forward ）するとき、ルーティングテーブルを検索し、パケットの宛先と一致するエントリがあれば、そのエントリの次ホップへ向けてパケットを回送する。以下では簡単のため、ルーティングテーブルに記録される各ノードのアドレスを、ノード識別子（ノード番号）に置き換えて説明する。
【０００５】
図１９から図２１までは、従来のアドホックネットワークにおけるフラッディング処理の例を示している。図１９に示すアドホックネットワークは、ノード０〜７の８個のノードから構成され、ノード０およびノード７がそれぞれ発信元および宛先となる。各ノードは、パーソナルコンピュータ、ＰＤＡ（Personal Digital Assistants ）、携帯電話機等の端末、またはその他の通信装置に相当する。
【０００６】
まず、図１９に示すように、発信元ノード０は、ノード７を宛先として、隣接ノード１〜３に対してルートリクエストパケットを送信する。ノード１〜３は、宛先（Ｄｅｓｔ）、次ホップ（Ｎｅｘｔ  ｈｏｐ）、およびホップカウント（Ｎｕｍ  ｈｏｐｓ）を含むエントリからなる、ルーティングテーブル５１〜５３をそれぞれ作成する。このとき、ルーティングテーブルの宛先には、ルートリクエストパケットの発信元を示すノード識別子が記録され、次ホップには、宛先に至る経路上の次段のノードを示すノード識別子が記録され、ホップカウントには、宛先までのホップ数が記録される。
【０００７】
次に、図２０に示すように、ノード１は、ルートリクエストパケットを隣接ノード０、２、４、および５に送信する。同様に、ノード２は、ルートリクエストパケットを隣接ノード０、４、５、および６に送信し、ノード３は、ルートリクエストパケットを隣接ノード０、２、５、および６に送信する。これにより、ルートリクエストパケットが次段のノード４〜６に到達する。このとき、ノード０、４、５、および６は、ルーティングテーブル５４〜５７をそれぞれ作成し、ノード２は、ルーティングテーブル５２に２つのエントリを追加する。
【０００８】
次に、図２１に示すように、ノード４は、ルートリクエストパケットを隣接ノード５および７に送信し、ノード５は、ルートリクエストパケットを隣接ノード７に送信し、ノー
ド６は、ルートリクエストパケットを隣接ノード５および７に送信する。これにより、ルートリクエストパケットが宛先ノード７に到達する。このとき、ノード７は、ルーティングテーブル５８を作成し、ノード５は、ルーティングテーブル５６に２つのエントリを追加する。
【０００９】
図２２から図２５までは、宛先ノード７からのリプライ処理の例を示している。まず、図２２に示すように、宛先ノード７は、ノード５に対してルートリプライパケットを送信し、ノード５は、ルーティングテーブル５６にエントリを追加する。このとき、追加されるエントリの宛先には、ルートリプライパケットの発信元を示すノード識別子が記録される。
【００１０】
次に、図２３に示すように、ノード５は、ノード２および７に対してルートリプライパケットを送信する。このとき、ノード２および７は、ルーティングテーブル５２および５８にそれぞれエントリを追加する。
【００１１】
次に、図２４に示すように、ノード２は、ノード０に対してルートリプライパケットを送信する。このとき、ノード０は、ルーティングテーブル５４にエントリを追加する。こうして、図２５に示すように、ノード０からノード２および５を経由してノード７に至る経路が確立され、各ノードは、ルーティングテーブル中の二重丸の記号が示すエントリを参照しながら、パケットを回送する。
【００１２】
ノードの移動やバッテリの消耗等のトラブルが発生しなければ、この経路を使用して通信が行われる。しかし、トラブル発生により通信が遮断されると、通信コネクションは一旦切断され、再度、フラッディングからリプライまでの手続きが実行されて、経路が再確立される。
【００１３】
現状のＡＯＤＶの仕様では、あるノードが通信不可となった場合に、ローカルルートリペア（local route repair）を行うことになっている。ＭＡＣ（Media Access Control）レイヤでのリトライ回数に基づいてリトライアウトが発生した場合、通信不可のノードから下流の部分に限定して、局所的にＡＯＤＶリクエストを実施し、経路の再確立を行う。
【００１４】
ＡＯＤＶリクエストのフラッディングを行うとき、中間に存在する通信可能なノードを経由するすべてのパスを、各ルーティングテーブル中に格納しておく。そして、通信中に、あるノードが遠方への移動やバッテリの不備により通信不可となった場合、エンドツーエンドに知らせることなく、局所的にルーティングテーブルのエントリを変更することで、そのノードを回避する経路を確立する。
【００１５】
つまり、経路切断に至る以前の段階において、事前にルーティングテーブルのエントリ
を変更し、上位プロトコルにリトライを実施させずに、通信を継続させる。
図２６は、このようなローカルルートリペアを行うアドホックネットワークの例を示している。このアドホックネットワークはノードＡ〜Ｆから構成され、ノードＡ、Ｂ、Ｄ、およびＦは、ルーティングテーブル６１〜６４をそれぞれ保持する。
【００１６】
ここで、図２７に示すように、ノードＦが移動することによりノードＤとノードＦの間のリンクが切れると、リンク故障を検出したノードＤは、ルートリクエストパケット（ＲＲＥＱ）を隣接ノードＢ、Ｃ、およびＥに送信する。次に、ノードＥは、ルートリクエストパケットを移動先のノードＦに送信する。そして、ノードＦからノードＥにルートリプライパケット（ＲＲＥＰ）が送信され、ノードＥからノードＤにルートリプライパケットが送信される。
【００１７】
下記の特許文献１は、無線アドホック通信システムにおける経路切替に関し、特許文献２は、マルチホップ無線ネットワークにおける経路更新に関する。
【特許文献１】特開２００４−２８２２７０号公報
【特許文献２】特開２００５−２２３６９７号公報
【非特許文献１】“RFC3561: Ad hoc On-Demand Distance Vector (AODV) Routing”、［online］、［平成１９年１月９日検索］、インターネット＜ＵＲＬ：http://www.ietf.org/rfc/rfc3561.txt ＞
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上述した従来のＡＯＤＶプロトコルにおいて、経路を探すときにはフラッディング処理によりすべてのパスを辿り、リプライ処理では一本の経路のみを辿る方法は、アーキテクチャを簡便化する意味において１つの有効な解となる。しかし、経路の途中に何らかの障害が発生し、ローカルルートリペア処理を行う場合、エンドツーエンドの通信が一旦切断されてしまうという問題がある。
【００１９】
本発明の課題は、アドホックネットワークにおいて障害が発生したときに、エンドツーエンドの通信を切断することなく、経路を再確立することである。
【課題を解決するための手段】
【００２０】
図１は、本発明の経路制御装置の原理図である。図１の経路制御装置は、アドホックネットワークを構成する複数のノードのうちの１つに設けられ、記憶手段１０１、リクエスト送信手段１０２、リプライ送信手段１０３、および制御手段１０４を備える。
【００２１】
記憶手段１０１は、アドホックネットワークの経路情報を記憶する。リクエスト送信手段１０２は、複数のノードのうち発信元ノードから宛先ノードまでの経路を探すとき、発信元ノードから宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信する。
【００２２】
リプライ送信手段１０３は、宛先ノードから発信元ノードへリプライを返送するとき、宛先ノードから発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信する。制御手段１０４は、隣接ノードからリクエストまたはリプライを受信したとき、その隣接ノードを含む経路の情報を記憶手段１０１に登録する。
【００２３】
このような経路制御装置を各ノードに設ければ、通信開始以前の段階において、発信元ノードから宛先ノードまでの複数の経路を示す双方向の経路情報を、各ノードに登録することができる。これにより、メインルートだけでなく、１つ以上の代替経路も自動的にアドホックネットワークに設定され、メインルートの通信状態が悪化したとき、直ちに代替経路へ切り替えることが可能になる。
【００２４】
図１の経路制御装置は、例えば、後述する図２のノード０〜７、図１３の端末１３０１〜１３０５、および図１５の基地局１５０１、移動中継装置１５１１、１５１２、端末１５２１〜１５２３の１つに対応する。また、記憶手段１０１が記憶する経路情報は、例えば、図２のルーティングテーブル５１〜５８の１つに対応する。
【発明の効果】
【００２５】
本発明によれば、例えば、障害が発生したノードの上流に位置するノードが、ＭＡＣレイヤのリトライアウトに至る以前の段階において、自身の判断にて代替経路を確立することができる。これにより、通信コネクションの切断が回避され、最小限の通信パケット数と消費電力にて、最大限の通信経路使用効率を達成することができる。
【発明を実施するための最良の形態】
【００２６】
以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。
本実施形態では、アドホックネットワークにおいて発信元から宛先までの経路を探すときに、ルートリクエストの順方向フラッディングに加えて、ルートリプライの逆方向フラッディングも実施する。これにより、通信開始以前の段階において、双方向の通信可能なパスをすべてルーティングテーブルに格納することが可能になる。
【００２７】
例えば、図１９に示したネットワークの場合、ルートリクエストパケットの順方向フラッディングは、図１９〜図２１と同様の手順で行われる。そして、ルートリクエストパケットが宛先ノード７に到達した後、順方向フラッディングと同様に、ルートリプライパケットの逆方向フラッディングが行われる。
【００２８】
図２から図５までは、このようなリプライ処理の例を示している。まず、図２に示すように、宛先ノード７は、発信元ノード０を宛先として、隣接ノード４〜５に対してルートリプライパケットを送信する。このとき、ノード４〜５は、ルーティングテーブル５５〜５７にそれぞれエントリを追加する。
【００２９】
次に、図３に示すように、ノード４は、ルートリプライパケットを隣接ノード１、２、５、および７に送信する。同様に、ノード５は、ルートリプライパケットを隣接ノード１、２、３、６、および７に送信し、ノード６は、ルートリプライパケットを隣接ノード２、３、および７に送信する。これにより、ルートリプライパケットが次段のノード１〜３に到達する。
【００３０】
このとき、ノード１および３は、ルーティングテーブル５１および５３にそれぞれ２つのエントリを追加し、ノード５および６は、ルーティングテーブル５６および５７にそれぞれ１つのエントリを追加し、ノード７は、ルーティングテーブル５８に３つのエントリを追加する。
【００３１】
次に、図４に示すように、ノード１は、ルートリプライパケットを隣接ノード０および２に送信する。同様に、ノード２は、ルートリプライパケットを隣接ノード０および３に送信し、ノード３は、ルートリプライパケットを隣接ノード０に送信する。これにより、ルートリプライパケットが宛先ノード０に到達する。このとき、ノード２および３は、ルーティングテーブル５２および５３にそれぞれ１つのエントリを追加し、ノード０は、ルーティングテーブル５４に３つのエントリを追加する。
【００３２】
そして、図５に示すように、ルーティングテーブルに記録されたすべての経路のうち、最善の経路がメインルートに決定される。この例では、ノード０からノード２および５を経由してノード７に至る経路がメインルートに決定され、各ノードは、ルーティングテーブル中の二重丸の記号が示すエントリを参照しながら、パケットを回送する。
【００３３】
図６は、このようなリプライ処理のフローチャートである。まず、宛先ノードが送信ノードとなり（ステップ６０１）、送信ノードは、複数の隣接ノードへルートリプライパケットを送信する（ステップ６０２）。そして、隣接する送信ノードからルートリプライパケットを受信した各ノードは、ルーティングテーブルにエントリを追加する（ステップ６０３）。
【００３４】
このとき、追加されるエントリの宛先には、ルートリプライパケットの発信元を示すノード識別子が記録され、次ホップには、送信ノードを示すノード識別子が記録され、ホップカウントには、宛先までのホップ数が記録される。
【００３５】
次に、ルートリプライパケットを受信したノードがルートリクエストパケットの発信元であるか否かがチェックされる（ステップ６０４）。受信ノードが発信元でなければ、その受信ノードが新たな送信ノードとなり（ステップ６０５）、ステップ６０２以降の処理を繰り返す。そして、発信元ノードがルートリプライパケットを受信すると、処理を終了する。こうして、双方向の代替経路を含む、通信可能なすべてのパスが、それぞれのノードのルーティングテーブルに格納される。
【００３６】
リプライ処理の終了後、シーケンス番号等を考慮しながら、最善の経路であるメインルートが決定される。シーケンス番号はタイムスタンプの役割を果たし、各ノードは、シーケンス番号を参照することで、ルーティングテーブルの情報が最新のものであるか否かを判定する。各ノードは、メッセージを送信する度に、そのノードのシーケンス番号を増加させ、メッセージを受信すると、他のノードのシーケンス番号を記録する。より大きなシーケンス番号は、より新しい経路を意味する。これにより、どのノードがより正確な情報を保持しているかが分かる。
【００３７】
例えば、図７に示すアドホックネットワークにおいて、ノード１がノード３からのルートリプライパケットをノード４に回送する場合、ルートリプライパケット７０１のシーケンス番号と、ルーティングテーブル７０２に記録されたシーケンス番号を比較する。
【００３８】
この場合、ルートリプライパケット７０１のシーケンス番号は“１３６”であり、ルーティングテーブル７０２の宛先ノード３のエントリのシーケンス番号は“１２８”である。したがって、ルートリプライパケット７０１の方がそのエントリより新しい経路を示していることが分かり、ノード１は、ルートリプライパケット７０１が持つ情報をルーティングテーブル７０２に登録する。
【００３９】
図５に示したルーティングテーブル５１〜５８にシーケンス番号を付加すると、図８のようになる。シーケンス番号“１３６”は、シーケンス番号“１２８”より新しい情報を示しており、シーケンス番号“１６４”は、シーケンス番号“１３６”より新しい情報を示している。
【００４０】
図９は、このようなシーケンス番号を用いたメインルート決定処理のフローチャートである。まず、宛先ノードが対象ノードとなり（ステップ９０１）、対象ノードは、ルーティングテーブルに登録された同一の宛先を持つエントリ中で、最も新しいシーケンス番号を持つエントリを選択する（ステップ９０２）。そして、そのエントリをメインルートで使用する参照エントリ（二重丸の記号が示すエントリ）に指定する。
【００４１】
次に、対象ノードがルートリクエストパケットの発信元であるか否かがチェックされる（ステップ９０３）。対象ノードが発信元でなければ、次段のノードが新たな対象ノードとなり（ステップ９０４）、ステップ９０２以降の処理を繰り返す。そして、発信元ノードが対象ノードになると、処理を終了する。
【００４２】
メインルートを使用した通信が開始された後、通信状態が悪化してＭＡＣレイヤにおいてリトライを実行する場合、従来の方法であれば、例えば、８回リトライして不成功に終わるとリトライアウトとして扱われる。
【００４３】
これに対して、本実施形態では、リトライアウトのカウントより少ない回数（例えば、４回）リトライして不成功となった時点で、あらかじめルーティングテーブルに記録されている代替経路への切り替え処理を開始する。この処理では、受信電力のような物理レイヤの情報は参照せずに、プロトコルレベルの再送により経路の切り替えを行う。
【００４４】
例えば、図８のメインルート上のノード５で障害が発生した場合、ノード７は、ノード５に対するＭＡＣレイヤでのリトライを、所定回数まで実行する。それでもパケットが不達であれば、ノード７は、ノード４に対して、ノード２へ向かう経路を確保するように指示する。
【００４５】
具体的には、図１０に示すように、ノード４内のルーティングテーブルから、宛先が０で次ホップが２となっているエントリを選択するように指示する。これにより、ノード２−ノード５−ノード７の代替経路として、ノード２−ノード４−ノード７が確立される。
【００４６】
図１１は、このような経路切り替え処理のフローチャートである。メインルートが決定された後、そのメインルートを形成するノードの並び“０，２，５，７”を含むパケットが、発信元ノード０から宛先ノード７に向けて送信される（ステップ１１０１）。
【００４７】
このパケットを受信したノード７は、メインルート上の次のノードがノード５であり、その次のノードがノード２であることを記憶する（ステップ１１０２）。そして、ノード７は、ノード０とノード７間の通信において必要なすべてのＴＣＰ（Transmission Control Protocol ）パケットをノード５に送信したか否かをチェックする（ステップ１１０３）。
【００４８】
未送信のＴＣＰパケットがあれば、ノード７はノード５に次のＴＣＰパケットを送信し（ステップ１１０４）、ノード５から受信確認（ＡＣＫ）が返信された否かをチェックする（ステップ１１０５）。ノード５からＡＣＫを受信すれば、ＴＣＰパケットへのポインタをインクリメントして、ステップ１１０３以降の処理を繰り返し、すべてのＴＣＰパケットを送信すると、処理を終了する。
【００４９】
ステップ１１０５においてノード５からＡＣＫを受信しなければ、リトライ回数のカウンタに１を設定して（ステップ１１０７）、カウンタを閾値と比較する（ステップ１１０８）。この閾値としては、リトライアウトの閾値より小さい値（例えば４）が設定される。
【００５０】
カウンタが閾値以下であれば、ステップ１１０４以降の処理を繰り返し、再びＡＣＫを受信しなければ、カウンタをインクリメントする（ステップ１１０７）。そして、ステップ１１０８においてカウンタが閾値を超えると、ノード７は、ルーティングテーブル５８から代替経路の第１候補を選択する（ステップ１１０９）。このとき、ルーティングテーブル５８中でノード０を宛先として有するエントリのうち、２番目に新しいシーケンス番号を持つエントリが、第１候補（ノード２−ノード４−ノード７）として選択される。
【００５１】
次に、選択した代替経路の入り口となるノード４に対して、代替経路形成を指示する（ステップ１１１０）。このとき、図１２に示すように、ノード７は、障害が発生したノード５の次段のノード２へ到達可能な代替ノード４に対して、代替経路形成を指示するパケット１２０１を送信し、ノード４からＡＣＫ１２０２を受信する。パケット１２０１の宛先１２１１にはノード７の識別子が記述され、発信元１２１２にはノード０の識別子が記述される。また、ファンクション１２１３にはパスの切り替えが記述され、次々段のノード識別子１２１４にはノード２の識別子が記述される。
【００５２】
次に、ノード４は、発信元１２１２および次々段のノード識別子１２１４をキーとしてルーティングテーブル５５を検索し（ステップ１１１１）、該当するエントリの有無をチェックする（ステップ１１１２）。ルーティングテーブル５５に該当するエントリがあれば、ノード２、４、および７は、第１候補の代替経路を確立し（ステップ１１１３）、処
理を終了する。これにより、ルーティングテーブル５２、５５、および５８における参照エントリが変更される。
【００５３】
ステップ１１１２において該当するエントリがなければ、ノード７は、代替経路の他の候補の有無をチェックし（ステップ１１１４）、他の候補があれば、第２候補を選択して（ステップ１１１５）、ステップ１１１０以降の処理を繰り返す。このとき、ルーティングテーブル５８中でノード０を宛先として有するエントリのうち、３番目に新しいシーケンス番号を持つエントリが、第２候補（ノード２−ノード６−ノード７）として選択される。
【００５４】
ステップ１１１４において他の候補がなければ、経路切り替えは失敗と判断し（ステップ１１１６）、処理を終了する。
このように、本実施形態では、通信開始前に逆方向フラッディングを行ってあらかじめ代替経路情報を収集しておくことで、経路切り替えをタイムリに実施することが可能になる。これに対して、通信開始後に代替経路情報を取得する従来の方法では、パケット再送を検出してから代替経路の検索を開始するため、ＴＣＰコネクション切断に至る可能性がある。
【００５５】
代替経路確立回数をｎとして、図１０のアドホックネットワークにおける経路再構築時に消費するパケット数を見積もると、従来の方法では２３×ｎパケットであるのに対して、本実施形態ではｎパケットのみである。本実施形態では、逆方向フラッディングのためにさらに２０パケットを消費するが、これを合わせても２０＋ｎパケットである。したがって、従来の方法より少ないパケット数で、代替経路を確立することができる。
【００５６】
なお、メインルート上のノード５以外のノードで障害が発生した場合も、障害ノードに隣接するノードが同様の経路切り替え処理を行うことで、代替経路が確立される。
次に、図１３から図１６までを参照しながら、上述した経路切り替え制御の適用例を説明する。
【００５７】
図１３は、災害発生の緊急連絡時等に、インフラを必要とせず、ライフラインとなる情報をやりとりするアドホックネットワークシステムの例を示している。このシステムは端末１３０１〜１３０５からなり、各端末のモビリティは低く、ノマディックな動作を行うものとする。
【００５８】
端末１３０１から端末１３０２を経由して端末１３０３に至るメインルートが形成され、端末１３０１と端末１３０３の間で通信が行われているときに、図１４に示すように、遮蔽物１４０１が出現したとする。この場合、端末１３０１と端末１３０２の間でＴＣＰコネクションのリトライアウトが発生しやすくなるが、その前に端末１３０５を経由する代替経路に切り替えることにより、災害復旧に要する時間を短縮することができる。
【００５９】
図１５は、携帯電話のデータ通信を行うアドホックネットワークシステムの例を示している。このシステムは基地局１５０１、移動中継装置１５１１、１５１２、およびノマディックな動作を行う端末１５２１〜１５２３からなる。移動中継装置１５１２は、基地局１５０１が担当するセル１５３１の端部において、端末１５２１および１５２２と基地局１５０１の間の通信を中継している。
【００６０】
端末１５２１から移動中継装置１５１２を経由して基地局１５０１に至るメインルートが形成され、端末１５２１と基地局１５０１の間で通信が行われているときに、図１６に示すように、端末１５２１が移動したとする。この場合、移動中継装置１５１１を経由する代替経路に切り替えることにより、データ通信を継続することができる。
【００６１】
ところで、図５に示したアドホックネットワークにおいて順方向と逆方向のフラッディングを行った後、メインルートおよび代替経路を形成するノード列のすべてのノード識別子を、各ノードが記憶しておいてもよい。これにより、隣接ノードに障害が発生したときに、速やかに代替ノードへ代替経路形成を指示することが可能になる。
【００６２】
例えば、図１７に示すように、メインルート（ノード０−ノード２−ノード５−ノード７）、第１の代替経路（ノード０−ノード１−ノード４−ノード７）、および第２の代替経路（ノード０−ノード３−ノード６−ノード７）の３種類のノード列情報を、ルーティングテーブルとは別に作成しておく。
【００６３】
各ノード列情報は、例えば、図１８に示すようなデータ構造を有し、発信元ノード識別子１８０１、複数の中継ノード識別子１８０２〜１８０４、および宛先ノード識別子１８０５からなる。ポインタ１８１１は、ノード列情報を格納しているノードの位置を指している。複数の経路についてこのようなノード列情報を作成しておくことで、障害発生時に、ノード単位ではなく、発信元から宛先に至る経路全体を代替系に切り替えることができる。
なお、ネットワークを構成するすべてのノードがノード列情報を記憶する代わりに、発信元ノードと宛先ノードのみがノード列情報を記憶するようにしてもよい。
【００６４】
（付記１）アドホックネットワークを構成する複数のノードのうちの１つに設けられた経路制御装置であって、
前記アドホックネットワークの経路情報を記憶する記憶手段と、
前記複数のノードのうち発信元ノードから宛先ノードまでの経路を探すとき、該発信元ノードから該宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信するリクエスト送信手段と、
前記宛先ノードから前記発信元ノードへリプライを返送するとき、該宛先ノードから該発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信するリプライ送信手段と、
隣接ノードから前記リクエストまたは前記リプライを受信したとき、該隣接ノードを含む経路の情報を前記記憶手段に登録する制御手段と
を備えることを特徴とする経路制御装置。
（付記２）前記記憶手段は、前記発信元ノードから前記宛先ノードまでの複数の経路を示す経路情報を記憶し、前記制御手段は、該複数の経路のうちの第１の経路を用いた通信が開始された後通信状態が悪化すると、該経路情報を参照して、該第１の経路から該複数の経路のうちの第２の経路へ切り替える切り替え処理を開始することを特徴とする付記１記載の経路制御装置。
（付記３）前記制御手段は、前記第２の経路に含まれる隣接ノードに対して、該隣接ノードの次段のノードを示すノード識別情報を含み前記切り替え処理を指示する代替経路形成指示を送信することを特徴とする付記２記載の経路制御装置。
（付記４）前記制御手段は、前記第２の経路に含まれる隣接ノードが前記次段のノードへの経路を示す経路情報を記憶していないとき、前記第１の経路から前記複数の経路のうちの第３の経路へ切り替える切り替え処理を開始することを特徴とする付記３記載の経路制御装置。
（付記５）前記記憶手段は、前記複数の経路のそれぞれに対応する複数のノード列を示すノード列情報をさらに記憶することを特徴とする付記２、３、または４記載の経路制御装置。
（付記６）複数のノードから構成されるアドホックネットワークにおける経路制御方法であって、
前記複数のノードのうち発信元ノードから宛先ノードまでの経路を探すとき、該発信元
ノードから該宛先ノードに向かう方向の順方向フラッディング処理により、リクエストを複数の隣接ノードに送信する処理を繰り返し、
隣接ノードから前記リクエストを受信したノードに、該隣接ノードを含む経路の情報を登録し、
前記宛先ノードから前記発信元ノードへリプライを返送するとき、該宛先ノードから該発信元ノードに向かう方向の逆方向フラッディング処理により、リプライを複数の隣接ノードに送信する処理を繰り返し、
隣接ノードから前記リプライを受信したノードに、該隣接ノードを含む経路の情報を登録する
ことを特徴とする経路制御方法。
（付記７）各ノードは、前記発信元ノードから前記宛先ノードまでの複数の経路を示す経路情報を記憶し、該複数の経路のうちの第１の経路に属する各ノードは、該第１の経路を用いた通信が開始された後通信状態が悪化すると、該経路情報を参照して、該第１の経路から該複数の経路のうちの第２の経路へ切り替える切り替え処理を開始することを特徴とする付記６記載の経路制御方法。
【図面の簡単な説明】
【００６５】
【図１】本発明の経路制御装置の原理図である。
【図２】本発明のリプライ処理を示す図（その１）である。
【図３】本発明のリプライ処理を示す図（その２）である。
【図４】本発明のリプライ処理を示す図（その３）である。
【図５】本発明のリプライ処理を示す図（その４）である。
【図６】リプライ処理のフローチャートである。
【図７】シーケンス番号を示す図である。
【図８】リプライ処理後のシーケンス番号を示す図である。
【図９】メインルート決定処理のフローチャートである。
【図１０】代替経路を示す図である。
【図１１】経路切り替え処理のフローチャートである。
【図１２】代替経路形成指示を示す図である。
【図１３】第１のアドホックネットワークシステムを示す図である。
【図１４】遮蔽物出現後の代替経路を示す図である。
【図１５】第２のアドホックネットワークシステムを示す図である。
【図１６】端末移動後の代替経路を示す図である。
【図１７】メインルートと代替経路を示す図である。
【図１８】ノード列情報を示す図である。
【図１９】従来のフラッディング処理を示す図（その１）である。
【図２０】従来のフラッディング処理を示す図（その２）である。
【図２１】従来のフラッディング処理を示す図（その３）である。
【図２２】従来のリプライ処理を示す図（その１）である。
【図２３】従来のリプライ処理を示す図（その２）である。
【図２４】従来のリプライ処理を示す図（その３）である。
【図２５】従来のリプライ処理を示す図（その４）である。
【図２６】従来のアドホックネットワークを示す図である。
【図２７】従来のローカルルートリペアを示す図である。
【符号の説明】
【００６６】
５１、５２、５３、５４、５５、５６、５７、５８、６１、６２、６３、６４、７０２
ルーティングテーブル
１０１  記憶手段
１０２  リクエスト送信手段
１０３  リプライ送信手段
１０４  制御手段
７０１  ルートリプライパケット
１２０１  パケット
１２０２  ＡＣＫ
１２１１  宛先
１２１２  発信元
１２１３  ファンクション
１２１４  次々段のノード識別子
１３０１、１３０２、１３０３、１３０４、１３０５、１５２１、１５２２、１５２３
端末
１４０１  遮蔽物
１５０１  基地局
１５１１、１５１２  移動中継装置
１８０１  発信元ノード識別子
１８０２、１８０３、１８０４  発信元ノード識別子
１８０５  宛先ノード識別子
１８１１  ポインタ
【図１】
2008193543.tif 000003
【図２】
2008193543.tif 000004
【図３】
2008193543.tif 000005
【図４】
2008193543.tif 000006
【図５】
2008193543.tif 000007
【図６】
2008193543.tif 000008
【図８】
2008193543.tif 000009
【図９】
2008193543.tif 000010
【図１０】
2008193543.tif 000011
【図１１】
2008193543.tif 000012
【図１２】
2008193543.tif 000013
【図１３】
2008193543.tif 000014
【図１４】
2008193543.tif 000015
【図１５】
2008193543.tif 000016
【図１６】
2008193543.tif 000017
【図１７】
2008193543.tif 000018
【図１８】
2008193543.tif 000019
【図１９】
2008193543.tif 000020
【図２０】
2008193543.tif 000021
【図２１】
2008193543.tif 000022
【図２２】
2008193543.tif 000023
【図２３】
2008193543.tif 000024
【図２４】
2008193543.tif 000025
【図２５】
2008193543.tif 000026
【図７】
2008193543.tif 000027
【図２６】
2008193543.tif 000028
【図２７】
2008193543.tif 000029