(57)【要約】    【課題】      迅速な経路修復と最適な経路による通信の継続を同時に実現すること。    【解決手段】  無線受信部１０３は、サーキュレータ１０２を介して送受信アンテナ１０１で受信されたパケットデータを含む無線信号を受信する。また、無線受信部１０３は、通信相手からの信号の電界強度の低下からアドホックネットワークが切断を検出する。無線送信部１０４は、経路検索パケット、経路応答パケット等を含む無線信号を、サーキュレータ１０２を介して送受信アンテナ１０１から送信する。制御部１０５は、アドホックネットワークが切断された場合、宛先の無線アドホック端末に経路検索パケットを送信する経路修復の処理とともに、送信元の無線アドホック端末に経路断を通知する経路再構築処理を行う。  【選択図】      図１
2005269623.tif 000002
【特許請求の範囲】
【請求項１】
パケットを含む無線信号を受信する受信手段と、
パケット転送の経路が切れたことを検出する検出手段と、
パケット転送の経路が切れた場合、前記パケットの宛先への経路探索要求をブロードキャスト送信すると共に、前記パケットの送信元に前記パケット転送の経路が切れたことを通知する送信手段と、
を具備することを特徴とするパケットルーティング装置。
【請求項２】
受信した信号の内容を判断する制御手段と、
パケットの転送経路を探索する経路探索パケット処理手段と、
前記受信手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求、またはパケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求を含む無線信号を受信し、
前記制御手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求と、パケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求と区別し、
経路探索パケット処理手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求を受信した場合に、パケットの転送経路を探索し、
パケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求を受信した場合に、再構築するパケットの経路を探索することを特徴とする請求項１に記載のパケットルーティング装置。
【請求項３】
パケットを含む無線信号を受信する受信手段と、
パケット転送の経路が切れたことを検出する検出手段と、
パケット転送の経路が切れた場合、前記パケットの宛先への経路探索要求を前記パケットの送信元が行ったように前記検索要求の内容を調整してブロードキャスト送信する送信手段と、
を具備することを特徴とするパケットルーティング装置。
【請求項４】
複数の無線端末装置を経由して宛先の無線端末装置にパケットを送信するシステムにおいて、パケットを中継する無線端末装置が経路断を監視し、経路断を検出した無線端末装置が、パケットの宛先の無線端末装置に経路検索パケットを送信すると共に、送信元の無線端末装置に経路断を通知し、中継する無線端末装置は、経路検索パケットに従ってパケット転送の経路を再構築し、送信元の無線端末装置は、経路断の情報を受け取った場合に経路再構築を行うことを特徴とするパケットルーティング方法。
【請求項５】
複数の無線端末装置を経由して宛先の無線端末装置にパケットを送信するシステムにおいて、パケットを中継する無線端末装置が経路断を監視し、経路断を検出した無線端末装置が、パケットの宛先の無線端末装置にパケットの宛先への経路探索要求をパケットの送信元が行ったように前記検索要求の内容を調整して経路検索パケットを送信し、経路検索パケットを受信した宛先の無線端末装置が経路断を検出した無線端末装置への応答を送信することにより、パケット転送の経路を修復することを特徴とするパケットルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線端末が自在に移動可能な無線アドホックネットワークにおけるパケットルーティング方法及びパケットルーティング装置に関し、特に、経路を修復するパケットルーティング方法及びパケットルーティング装置に関する。
【背景技術】
【０００２】
自由に動き回る複数の無線端末同士が互いに通信を行うアドホックネットワーク上で無線パケット通信を行う技術として、ＩＥＴＦ（Internet Engineering Task Force）のＭＡＮＥＴ（Mobile Adhoc NETworks）ワーキンググループで標準化中のＡＯＤＶ（Adhoc On-demand Distance Vector）ルーティングプロトコルがある。
【０００３】
ＭＡＮＥＴでは、データパケットの発信元である送信元端末と、当該データパケットの送信先である宛先端末とが、距離の関係などにより直接通信できない場合であっても、送信元端末と宛先端末との間に存在する１又は複数の無線端末にデータパケットを中継させる。これにより、発信端末と宛先端末とが直接通信できなくても、送信元端末から宛先端末へのデータ転送を行うことができる。
【０００４】
この送信元端末から宛先端末までの通信経路の構築を行うにあたり、ＭＡＮＥＴには大きく分けて２つの方法がある。１つは、アプリケーション等から通信要求が発生した場合にのみ通信経路を構築するＡＯＤＶなどのオンデマンド型のルーティングプロトコルによる方法である。もう１つは、有線ネットワークにおけるルーティングプロトコルと同様に、定期的に経路構築のためのパケットを送出して、全ての端末への経路構築（更新）を行うＯＬＳＲ（Optimized Link State Routing）などのテーブル駆動型のルーティングプロトコルである。
【０００５】
オンデマンド型ルーティングプロトコルは、データ送信のたびに経路探索を行うため、個々の送信コストが高くなるものの、定期的に消費する通信帯域は発生しないので、他の端末に及ぼす影響や消費電力が小さく済む。一方、テーブル駆動型ルーティングプロトコルは、予め経路を構築しておくため、各端末がデータを送る頻度が高い場合には有利であるが、その経路構築（更新）のために定期的に通信帯域を消費してしまうので、無線媒体を共有するような場合、他のデータ送信中の端末に影響を及ぼす可能性が高くなる。
【０００６】
このようなことから、バッテリーで駆動するような端末を用いてアドホックネットワークを構築する場合、オンデマンド型ルーティングプロトコルが一般的に用いられている。
【０００７】
ところが、オンデマンド型のルーティングプロトコルを用いた無線アドホックネットワークにおいて、データパケットの中継中に、特定された通信経路上の無線端末が移動または電源を切るなどすると、データパケットを中継できなくなってしまう。このため、こうした場合には新たな通信経路を確保する必要がある。
【０００８】
一般に、通信経路を確保する方法としては、通信経路構築のためのパケットをブロードキャスト送信し、その結果を各無線端末が受け取ることで通信経路を構築する方法が用いられる。上記のＡＯＤＶプロトコルにおいては、図１７〜図２２に示すように、通信経路の再構築が行われる。
【０００９】
ここでは、図１７に示すように、送信元端末２０→中継端末１３→中継端末１６→中継端末１８→宛先端末２１という送信経路でデータパケットを送信していたとする。ここで、宛先端末２１が移動するなどしてデータパケットを中継できなくなった場合に、それを認識した中継端末１８は、経路の更新が必要であると判断する。
【００１０】
すなわち、中継端末１８は、例えば電波受信レベルを監視し、それがある一定のレベルを下回ると、宛先端末２１との間における通信状態の悪化、すなわち、経路の切断を検出する。この宛先端末２１への経路として中継端末１８を使用している直前の端末（ここでは、中継端末１６）を検索し、この経路が使用できなくなったことを通知する経路エラーパケットを直前の端末に対して送信する。
【００１１】
この経路エラーパケットを受信した端末は、さらに自端末を経路上に指定している直前の端末を検索し、該当する端末が存在すれば、その端末に対して経路エラーパケットを送信する。これを繰り返すことにより、送信元端末２０まで経路エラーパケットが転送される。送信元端末２０は、図１８に示すように、もう一度、宛先端末２１への経路探索パケットをフラッディングする。そして、図１９に示すように、宛先端末２１が経路応答パケットを送信元端末２０に送信することにより、経路を再構築する。
【００１２】
ところで、経路断を検出した中継端末１８が、宛先端末２１にある程度近い場合には、その経路の修復を中継端末１８で行うことができる。この場合、図２０に示すように、中継端末１８は宛先端末２１への経路を検索する経路検索パケットをフラッディングする。
【００１３】
ただし、この経路検索パケットの広がる範囲は、パケットの送信元端末２０まで届かないように計算されて調整される。この経路検索パケットを受信した各中継端末は、転送が許される限りフラッディングを繰り返し、最終的に宛先端末２１に転送される。経路検索パケットを受信した宛先端末２１は、図２１に示すように、経路検索パケットを送信した中継端末１９に対して経路応答パケットを送信し、中継端末１９は受信した経路応答パケットを中継端末１８に転送することにより、中継端末１８から宛先端末２１への経路が構築される。
【００１４】
これにより、もともとは送信元端末２０→中継端末１３→中継端末１６→中継端末１８→宛先端末２１であった経路が、送信元端末２０→中継端末１３→中継端末１６→中継端末１８→中継端末１９→宛先端末２１と修復され、送信元−宛先間の通信が継続される。
【００１５】
また、この場合、経路修復後の中継回数が経路修復前よりも増加しているため、図２２に示すように、経路断を検出した場合の経路エラーパケットの送出と同様に、中継端末１８は、送信元端末２０に対して、修復した経路が修復前の経路よりも中継回数が増加したことを示す情報を経路エラーパケットに含めてフラッディングする。
【００１６】
この経路エラーパケットを受信した送信元端末２０は、修復された経路を継続して使用してもよいし、図１８及び図１９に示した経路検索パケットと経路応答パケットのやり取りで新たな経路を再構築してもよい。
【非特許文献１】ＲＦＣ３５６１
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかしながら、上記のＡＯＤＶプロトコルによる中継端末での経路修復の際、中継端末から宛先端末への経路検索パケットの送信後、ある一定時間、宛先端末からの経路応答パケットの到着を待つ。その時間内に経路応答パケットが到着しなかった場合、経路修復不可能と判断して、送信元端末に対して経路エラーパケットを送信するため、送信元端末への経路エラー通知が遅れ、送信元端末による宛先端末への経路再構築が行われるまでの時間が増加してしまう。
【００１８】
また、一定時間内に、宛先端末から経路応答パケットを受信した場合でも、送信元端末から宛先端末への経路として、通信断を検出した中継端末を経由しないものが最適な経路であることも考えられる（図２２の通信経路よりも図１９の通信経路のほうが、中継回数が少ない）。さらに、修復された経路で送信元端末に対して経路エラーパケットを送信すると、修復された経路は修復前より中継回数が増加しているので、送信元端末への経路修復の通知が遅れ、送信元端末による宛先端末への最適な経路構築が行われるまでの時間が増加する。
【００１９】
このように、上述した方法では、迅速な経路修復と最適な経路による通信の継続を同時に実現することが難しいという問題がある。
【００２０】
本発明はかかる点に鑑みてなされたものであり、ネットワーク上で経路再構築を行うにあたって、中継断を検出した中継端末による宛先端末への経路修復と並行して送信元端末による宛先端末への経路再構築を行うことにより、迅速な経路修復と最適な経路による通信の継続を同時に実現するパケットルーティング方法及びパケットルーティング装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明のパケットルーティング装置は、パケットを含む無線信号を受信する受信手段と、パケット転送の経路が切れたことを検出する検出手段と、パケット転送の経路が切れた場合、前記パケットの宛先への経路探索要求をブロードキャスト送信し、また前記パケットの送信元に前記パケット転送の経路が切れたことを通知する送信手段と、を具備する構成を採る。
【００２２】
この構成によれば、経路断を検出した中継端末が、宛先端末へ経路検索パケットを送信するとともに、送信元端末へ経路断を通知することにより、中継端末による迅速な宛先端末への経路修復ができるとともに、送信元端末による最適な経路の検索を開始するまでの時間を短縮できる。また、中継端末による宛先端末への経路修復が失敗した場合でも、送信元端末による宛先端末への経路検索を開始するまでの時間を短縮できる。
【００２３】
本発明のパケットルーティング装置は、受信した信号の内容を判断する制御手段と、パケットの転送経路を探索する経路探索パケット処理手段と、前記受信手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求、またはパケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求を含む無線信号を受信し、前記制御手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求と、パケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求と区別し、経路探索パケット処理手段は、パケットを中継する装置より中継された前記パケットの宛先への経路探索要求を受信した場合に、パケットの転送経路を探索し、パケット転送の経路が切れたことにより前記パケットの送信元から送信された経路再構築の要求を受信した場合に、再構築するパケットの経路を探索する構成を採る。
【００２４】
この構成によれば、経路破損箇所の下流側端末において、経路修復のためのルートと経路再構築のためのルートを識別して経路応答することにより、同一の送信元端末からの異なる経路要求を同時に受信しても、複数の経路を同時に構築することができる。
【００２５】
本発明のパケットルーティング装置は、パケットを含む無線信号を受信する受信手段と、パケット転送の経路が切れたことを検出する検出手段と、パケット転送の経路が切れた場合、前記パケットの宛先への経路探索要求を前記パケットの送信元が行ったように前記検索要求の内容を調整してブロードキャスト送信する送信手段と、を具備する構成を採る。
【００２６】
この構成によれば、宛先の無線端末装置は、受信した経路検索要求に基づいて、経路検索要求を送信した無線端末装置を経由すれば送信元の無線端末装置にパケットが届くことになるので、宛先の無線端末装置から送信元の無線端末装置への経路を迅速に修復することができる。
【００２７】
本発明のパケットルーティング方法は、複数の無線端末装置を経由して宛先の無線端末装置にパケットを送信するシステムにおいて、パケットを中継する無線端末装置が経路断を監視し、経路断を検出した無線端末装置が、パケットの宛先の無線端末装置に経路検索パケットを送信するとともに、送信元の無線端末装置に経路断を通知し、中継する無線端末装置は、経路検索パケットに従ってパケット伝送の経路を再構築し、送信元の無線端末装置は、経路断の情報を受け取った場合に経路再構築を行うようにした。
【００２８】
この方法によれば、経路断を検出した中継端末が、宛先端末へ経路検索パケットを送信するとともに、送信元端末へ経路断を通知することにより、中継端末による迅速な宛先端末への経路修復ができるとともに、送信元端末による最適な経路の検索を開始するまでの時間を短縮できる。また、中継端末による宛先端末への経路修復が失敗した場合でも、送信元端末による宛先端末への経路検索を開始するまでの時間を短縮できる。
【００２９】
本発明のパケットルーティング方法は、複数の無線端末装置を経由して宛先の無線端末装置にパケットを送信するシステムにおいて、パケットを中継する無線端末装置が経路断を監視し、経路断を検出した無線端末装置が、パケットの宛先の無線端末装置にパケットの宛先への経路探索要求をパケットの送信元が行ったように前記検索要求の内容を調整して経路検索パケットを送信し、経路検索パケットを受信した宛先の無線端末装置が経路断を検出した無線端末装置への応答を送信することにより、パケット転送の経路を修復するようにした。
【００３０】
この方法によれば、宛先の無線端末装置は、受信した経路検索パケットに基づいて、経路検索パケットを送信した無線端末装置を経由すれば送信元の無線端末装置にパケットを送信可能であると認識することになるので、宛先の無線端末装置から送信元の無線端末装置への経路を迅速に修復することができる。
【発明の効果】
【００３１】
本発明によれば、経路断を検出した中継端末が、宛先端末へ経路検索パケットを送信するとともに、送信元端末へ経路断を通知することにより、中継端末による迅速な宛先端末への経路を修復することができると共に、送信元端末による最適な経路の検索を開始するまでの時間を短縮することができる。また、中継端末による宛先端末への経路修復が失敗した場合でも、送信元端末による宛先端末への経路検索を開始するまでの時間を短縮することができる。これにより、迅速な経路修復と最適な経路による通信の継続を同時に実現することができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００３３】
（一実施の形態）
図１は、本発明の一実施の形態に係る無線アドホック端末１００の構成を示すブロック図である。この図において、送受信アンテナ１０１で受信されたパケットデータを含む無線信号は、サーキュレータ１０２を介して無線受信部１０３に入力される。また、無線送信部１０４から出力された信号は、サーキュレータ１０２を介して送受信アンテナ１０１から放射される。
【００３４】
無線受信部１０３は、サーキュレータ１０２から入力された無線信号を復調処理し、復調処理した信号を制御部１０５に出力する。また、入力された無線信号の電界強度などを監視し、電界強度の低下を検出すると、パケットを直接伝送している端末との通信が切断されたと判断する。通信断の検出は制御部１０５に通知される。
【００３５】
無線送信部１０４は、制御部１０５から出力された信号を変調処理し、変調処理した信号をサーキュレータ１０２に出力する。
【００３６】
制御部１０５は、アドホックネットワークが切断された場合、宛先端末に経路検索パケットを送信する経路修復の処理とともに、送信元端末に経路断を通知する経路再構築処理を行う。
【００３７】
経路エラーパケット処理部１１１は、経路が切断された場合に、経路エラーパケットを送信する制御を行う。データ発信パケット処理部１１２は、制御部１０５を介してルーティング上位部１１７から受信したデータ発信パケットの受信処理を行う。
【００３８】
経路応答パケット処理部１１３は、経路応答パケットを中継するか否かを判定して経路応答の処理を行う。データ中継パケット処理部１１４は、経路修復キャッシュ１１６を参照し、既に記憶されている中継端末が存在するかどうか確認し、パケットを伝送する中継端末の数が所定の数以上か未満かを判断し、経路設定の処理を行う。
【００３９】
経路検索パケット処理部１１５は、経路検索パケットの処理を行う。経路修復キャッシュ１１６は、中継端末から送信された経路修復のための経路検索パケットの内容を記憶する。ルーティング上位部１１７は、上位プロトコルでの処理を行う。
【００４０】
次に、上述した構成を有する無線アドホック端末の制御処理について図２を用いて説明する。図２において、ステップ（以下、「ＳＴ」と省略する）５０１では、制御部１０５において無線受信部１０３から通信断の通知を受けたか否かを判定し、通信断の通知を受けた（Ｙｅｓ）と判定された場合、ＳＴ５０２に移行し、通信断の通知を受けていない（Ｎｏ）と判定された場合、ＳＴ５０４に移行する。
【００４１】
ＳＴ５０２では、通信断となった相手側端末とパケットを直接伝送する宛先端末の識別情報が経路キャッシュ１１６に存在するか否か検索し、宛先端末の識別情報が存在すれば（Ｙｅｓ）、ＳＴ５０３に移行し、宛先端末の識別情報が存在しなければ（Ｎｏ）、制御処理を終了する。
【００４２】
ＳＴ５０３では、ＳＴ５０２において経路キャッシュ１１６に存在するとして検索された宛先端末に対応するエントリを全て削除し、制御処理を終了する。
【００４３】
ＳＴ５０４では、制御部１０５が無線受信部１０３からパケットを受信したか否かを判定し、パケットを受信したら（Ｙｅｓ）、ＳＴ５０５に移行し、パケットを受信しなければ（Ｎｏ）、ＳＴ５１４に移行する。
【００４４】
ＳＴ５０５では、制御部１０５において、受信したパケットが経路エラーパケットであるか否かが判定され、経路エラーパケットであれば（Ｙｅｓ）、ＳＴ５０９に移行し、経路エラーパケットでなければ（Ｎｏ）、ＳＴ５０６に移行する。
【００４５】
ＳＴ５０６では、制御部１０５において、受信したパケットが経路検索パケットであるか否かが判定され、経路検索パケットであれば（Ｙｅｓ）、ＳＴ５１０に移行し、経路検索パケットでなければ（Ｎｏ）、ＳＴ５０７に移行する。
【００４６】
ＳＴ５０７では、制御部１０５において、受信したパケットが経路応答パケットであるか否かが判定され、経路応答パケットであれば（Ｙｅｓ）、ＳＴ５１１に移行し、経路応答パケットでなければ（Ｎｏ）、ＳＴ５０８に移行する。
【００４７】
ＳＴ５０８では、制御部１０５において、受信したパケットがデータ発信パケットであるか否かが判定され、データ発信パケットであれば（Ｙｅｓ）、ＳＴ５１２に移行し、データ発信パケットでなければ（Ｎｏ）、ＳＴ５１３に移行する。
【００４８】
ＳＴ５０９では、経路エラーパケット処理部１１１において、経路エラーパケットの受信処理が行われ、制御処理を終了する。
【００４９】
ＳＴ５１０では、経路検索パケット処理部１１５において、経路検索パケットの受信処理が行われ、制御処理を終了する。
【００５０】
ＳＴ５１１では、経路応答パケット処理部１１３において、経路応答パケットの受信処理が行われ、制御処理を終了する。
【００５１】
ＳＴ５１２では、データ発信パケット処理部１１２において、データ発信パケットの受信処理が行われ、制御処理を終了する。
【００５２】
ＳＴ５１３では、データ中継パケット処理部１１４において、データ中継パケットの受信処理が行われ、制御処理を終了する。
【００５３】
なお、ＳＴ５０９の経路エラーパケット受信処理、ＳＴ５１０の経路検索パケット受信処理、ＳＴ５１１の経路応答パケット受信処理、ＳＴ５１２のデータ発信パケット受信処理、及び、ＳＴ５１３のデータ中継パケット受信処理の詳細については後述する。
【００５４】
ＳＴ５１４では、制御部１０５が経路キャッシュ１１６内に期限が満了したエントリがあるか否かを検索し、期限が満了したエントリがある場合（Ｙｅｓ）、ＳＴ５１５において、該当するエントリを経路キャッシュ１１６から削除し、制御処理を終了する。また、期限が満了したエントリがない場合（Ｎｏ）、制御処理を終了する。
【００５５】
ここで、上述した無線アドホック端末を利用したネットワークを図３に示し、送信元端末２１０から宛先端末２１１まで中継端末２０３、２０６、２０８を中継してデータパケットが送信されている場合を考える。
【００５６】
この場合、それぞれの端末が保持する情報として、送信元端末２１０は宛先端末２１１側の直接伝送を行う端末を識別する識別情報（ここでは、中継端末２０３の識別情報）を保持し、各中継端末２０３、２０６、２０８は、宛先端末２１１側及び送信元端末２１０側の直接伝送を行う識別情報を保持する。具体的には、中継端末２０３は中継端末２０６及び送信元端末２１０の識別情報を、中継端末２０６は中継端末２０８及び２０３の識別情報を、中継端末２０８は宛先端末２１１及び中継端末２０６の識別情報をそれぞれ保持する。また、宛先端末２１１は送信元端末２１０側の直接伝送を行う端末の識別情報（ここでは、中継端末２０８の識別情報）を保持する。
【００５７】
次に、データパケット送信中において、図４に示すように、宛先端末２１１の移動などにより、中継端末２０８の無線受信部１０３が宛先端末２１１の電界強度の低下を検出し、制御部１０５に対して宛先端末２１１との経路断を通知する。
【００５８】
経路断の通知を受けた制御部１０５では（図２のＳＴ５０１）、通知された端末を次の中継端末として利用する宛先端末が自端末の経路キャッシュ１１６内に存在するかどうか検索し（ＳＴ５０２）、存在するならば、該当する宛先端末に対応するエントリを全て削除する（ＳＴ５０３）。
【００５９】
また、中継端末２０８は、図４に示すように、中継端末２０６に経路エラーパケットを送信し、経路エラーパケットを受信した中継端末２０６では、パケット種別判定において、受信したパケットが経路エラーパケットであることを判定し（ＳＴ５０５）、経路エラーパケット処理部１１１が経路エラーパケット受信処理を行う（ＳＴ５０９）。
【００６０】
一方で、中継端末２０８は、図４に示すように、宛先端末２１１への経路検索パケットを送信し、中継端末２０８の近隣端末である中継端末２０５、２０６、２０９に経路検索パケットが伝播していく。そのうち、宛先端末２１１の近隣端末である中継端末２０９において、受信パケットがパケット種別判定により経路検索パケットであると判定され（ＳＴ５０６）、経路検索パケット処理部１１５が経路検索パケット受信処理を行う（ＳＴ５１０）。
【００６１】
宛先端末２０８から送信された経路検索パケットを受信した宛先端末２１１は、図５に示すように、経路検索パケットを直接伝送した中継端末２０９に経路応答パケットを送信する。経路応答パケットを受信した中継端末２０９は、受信パケットのパケット種別判定において、経路応答パケットであることを判定し（ＳＴ５０７）、経路応答パケット処理部１１３が経路応答パケット受信処理を行う（ＳＴ５１１）。
【００６２】
また、図５に示すように、経路検索パケット処理により経路検索パケットがネットワークを伝播する過程で、送信元端末２１０では、受信した経路エラーパケットのエラー種別が修復中であった場合には、送信元端末２１０から経路修復中の中継端末２０８までの経路は削除されてはいないので、データ発信パケットをルーティング上位部１１７から取得すると（ＳＴ５０８）、データ発信パケット処理部１１２がデータ発信パケット受信処理を行う（ＳＴ５１２）。
【００６３】
次に、図２のＳＴ５０９で示した経路エラーパケット受信処理の詳細な手順について図６を用いて説明する。図６において、ＳＴ８０１では、中継端末２０６は、中継端末２０８から経路エラーパケットを通知されると、送信元端末２１０側の直接伝送を行う端末（ここでは、中継端末２０３）が存在するか経路キャッシュ１１６を検索する。存在すれば（Ｙｅｓ）ＳＴ８０２に移行し、存在しなければ（Ｎｏ）ＳＴ８０３に移行する。
【００６４】
ＳＴ８０２では、ＳＴ８０１において検索された端末に対して、経路エラーパケットをユニキャストで送信することにより、経路がエラーになったことを通知する。ここでは、中継端末２０６が中継端末２０３に経路エラーパケットを送信することになるが、経路エラーパケットに含まれる経路エラー種別（経路修復中又は経路断）は、中継端末２０８から送信された経路エラーパケットに含まれる種別と同じである。
【００６５】
ＳＴ８０３では、中継端末２０３から経路エラーパケットを受信した送信元端末２１０が、受信した経路エラーパケットのエラー種別を判定し、エラー種別が経路修復中（Ｙｅｓ）であればＳＴ８０４に移行し、エラー種別が経路断（Ｎｏ）であればＳＴ８０７に移行する。
【００６６】
ＳＴ８０４では、送信元端末２１０が自端末内に宛先端末２１１へのデータ発信パケット（自端末のルーティング上位部１１７から取得したデータパケット）が存在するか否かを判定し、存在すれば（Ｙｅｓ）ＳＴ８０５に移行し、存在しなければ（Ｎｏ）経路エラーパケット受信処理を終了する。
【００６７】
ＳＴ８０５では、経路検索パケットの中継回数を１にセットし、ＳＴ８０６では、図５の細い実線で示すように、宛先端末２１１への経路検索パケットをブロードキャストで送信する。
【００６８】
ＳＴ８０７では、ＳＴ８０３において経路エラーパケットの種別が経路断と判定されたので、送信元端末２１０は自端末内の経路キャッシュ１１６に格納された宛先端末２１１への経路を削除し、経路エラーパケット受信処理を終了する。
【００６９】
次に、図２のＳＴ５１０で示した経路検索パケット受信処理の詳細な手順について図７を用いて説明する。図７において、ＳＴ９０１では、受信した経路検索パケットが既に受信済みのパケットと同一のもの（重複パケット）かを判断し、重複パケットである（Ｙｅｓ）と判断したら経路検索パケット受信処理を終了し、重複パケットではない（Ｎｏ）と判断したらＳＴ９０２に移行する。
【００７０】
経路検索パケットはブロードキャストで伝播していくため、例えば、中継端末２０８が送信した経路検索パケットを中継端末２０６が受信し、それを更にブロードキャストで転送すると中継端末２０９にも、その経路検索パケットが到着する。しかし、既に中継端末２０９は、中継端末２０８から同一の経路検索パケットを既に受信しているため、ＳＴ９０１では、この重複したパケットの処理を防ぐことになる。
【００７１】
ＳＴ９０２では、受信した経路検索パケットが経路修復のためのものであるかどうかを判定し、経路修復のための経路検索パケットである（Ｙｅｓ）と判定したらＳＴ９０３に移行し、経路修復のための経路検索パケットではない（Ｎｏ）と判定したらＳＴ９０４に移行する。
【００７２】
ＳＴ９０３では、経路修復を行っている端末への経路を構築するため、自端末の経路修復キャッシュに経路検索パケットを送信した端末を経路修復用として記憶（エントリの見かけ上は送信元端末であるが、実際は経路修復を行っている端末への経路構築に利用される）する。
【００７３】
ＳＴ９０４では、この経路検索パケットの送信元端末への経路を構築するため、送信元端末２１０（実際に経路検索パケットを送信したのは中継端末２０８であるが、そのパケットの中身は送信元端末２１０が送信したように装われている）側の直接伝送を行う中継端末を経路構築用として記憶する。例えば、中継端末２０９は中継端末２０８を経路キャッシュ１１６に記憶する。
【００７４】
ＳＴ９０５では、経路検索パケットの宛先が自端末であるかを判定し、自端末宛である（Ｙｅｓ）と判定したらＳＴ９０６に移行し、自端末宛ではない（Ｎｏ）と判定したらＳＴ９０７に移行する。
【００７５】
ＳＴ９０６では、ＳＴ９０５において経路検索パケットの宛先が自端末であると判定した宛先端末２１１が、図５に示すように、送信元端末２１０側の直接伝送を行う端末（経路検索パケットを自端末に送信した中継端末）、すなわち中継端末２０９に対して経路応答パケットをユニキャストで送信する。
【００７６】
ＳＴ９０７では、経路検索パケットが既に中継された回数と、経路検索パケットが無限に中継されることを防止するため、経路検索パケットに定められた中継を許容する回数（中継限界数）とを比較する。既に中継された回数が中継限界数よりも小さければ（Ｙｅｓ）ＳＴ９０８に移行し、既に中継された回数が中継限界数以上であれば（Ｎｏ）、経路検索パケットを伝播させることはできないので、中継せずに経路検索パケット受信処理を終了する。
【００７７】
ＳＴ９０８では、中継回数をインクリメントし、ＳＴ９０９では、再び経路検索パケットを近隣端末へとブロードキャストで送信し、経路検索パケット受信処理を終了する。
【００７８】
次に、図２のＳＴ５１１で示した経路応答パケット受信処理の詳細な手順について図８を用いて説明する。図８において、ＳＴ１００１では、経路応答パケットを受信した中継端末２０９が宛先端末２１１側の直接伝送を行う端末（経路応答パケットを自端末に対して送信した端末）、すなわち宛先端末２１１を自端末の経路キャッシュ１１６に記憶する。
【００７９】
ＳＴ１００２では、経路応答パケットの目的地となる端末、すなわち、経路検索パケットの送信元端末（実際に経路検索パケットを送信したのは中継端末２０８であるが、見かけ上は送信元端末２１０）が自端末であるか判定することにより、この経路応答パケットを中継するか否かを判定する。経路応答パケットの目的地が自端末である場合（Ｙｅｓ）、一連の経路確立動作を終了し、経路応答パケットの目的地が自端末ではない場合（Ｎｏ）、ＳＴ１００３に移行する。
【００８０】
ＳＴ１００３では、中継端末２０９が自端末から宛先端末２１１への経路修復を行ったか否かを判定し、経路修復を行っていれば（Ｙｅｓ）、一連の経路修復動作を終了し、経路修復を行っていなければ（Ｎｏ）、ＳＴ１００４に移行する。
【００８１】
ＳＴ１００４では、ＳＴ１００３において経路修復を行っていないと判定された中継端末２０９は、受信した経路応答パケットの宛先となる送信元端末へのエントリが経路修復キャッシュ１１６に存在するか否かを判定し、存在すれば（Ｙｅｓ）ＳＴ１００５に移行し、存在しなければ（Ｎｏ）ＳＴ１００７に移行する。
【００８２】
ＳＴ１００５では、宛先端末２１１が送信元端末（実際には、経路を修復する端末であり、ここでは中継端末２０８）側の直接伝送を行う中継端末２０９に経路応答パケットをユニキャストで送信し、ＳＴ１００６では、経路修復キャッシュ１１６の送信元端末へのエントリを削除する。そして、ＳＴ１００７では、送信元端末２１０側の直接伝送を行う中継端末２０８に、経路応答パケットをユニキャストで送信し、経路応答パケット受信処理を終了する。
【００８３】
なお、中継端末２０８は、中継端末２０９を介して宛先端末２１１からの経路応答パケットを受信し、ＳＴ１００３において自端末が宛先端末２１１への経路を修復したことを判定し、一連の経路修復動作を終了する。これにより、図５の太線で示した経路が中継端末２０８の経路修復動作により構築されたことになる。
【００８４】
次に、図２のＳＴ５１２で示したデータ発信パケット受信処理の詳細な手順について図９を用いて説明する。図９において、ＳＴ６０１では、データパケットの中継回数を１にセットし、再送回数を０にクリアする。
【００８５】
ＳＴ６０２では、宛先端末２１１側の直接伝送を行う中継端末（ここでは、中継端末２０３）が自端末の経路キャッシュ１１６内に存在するか否かを判定し、経路キャッシュ１１６内に存在する場合（Ｙｅｓ）、ＳＴ６０３に移行し、経路キャッシュ１１６内に存在しない場合（Ｎｏ）、ＳＴ６０５に移行する。
【００８６】
ＳＴ６０３では、ＳＴ６０２において経路キャッシュ１１６内に存在すると判定された中継端末（中継端末２０３）にデータ発信パケットをユニキャストで送信し、ＳＴ６０４では、ＳＴ６０２において経路キャッシュ１１６内に存在すると判定されたエントリの満了時間をリセットし、データ発信パケット受信処理を終了する。
【００８７】
一方、送信元端末２１０が受信した経路エラーパケットのエラー種別が経路断であった場合には、ＳＴ６０２において宛先端末２１１側の直接伝送を行う中継端末が自端末の経路キャッシュ１１６内に存在しないと判定され、ＳＴ６０５以降の経路再構築動作を行う。
【００８８】
ＳＴ６０５では、再送回数Ｎが予め定められた回数（閾値Ｎｔｈ）以下であるかを判定し、閾値Ｎｔｈ以下であれば（Ｙｅｓ）ＳＴ６０７に移行し、閾値Ｎｔｈを越えていれば（Ｎｏ）ＳＴ６０６に移行する。
【００８９】
ＳＴ６０６では、ＳＴ６０５において再送回数Ｎが閾値Ｎｔｈを越えたと判定されたので、受信したデータ発信パケットのルーティングができなかったことを示すエラーをルーティング上位部１１７に通知し、データ発信パケット受信処理を終了する。
【００９０】
ＳＴ６０７では、再送回数Ｎをインクリメントし、ＳＴ６０８では、宛先端末２１１への経路検索パケットをブロードキャストで送信する。
【００９１】
ＳＴ６０９では、経路検索パケットと経路応答パケットのやり取りが完了するまでに充分な予め定められた時間をウェイトし、ＳＴ６０２に戻る。
【００９２】
次に、図２のＳＴ５１３で示したデータ中継パケット受信処理の詳細な手順について図１０を用いて説明する。図１０において、ＳＴ７０１では、宛先端末２１１側の直接伝送を行う中継端末が経路修復キャッシュ１１６内に存在するか中継端末２０８が検索し、経路キャッシュ１１６内に存在する場合（Ｙｅｓ）、ＳＴ７０２に移行し、経路キャッシュ１１６内に存在しない場合（Ｎｏ）、ＳＴ７０５に移行する。この場合、宛先端末２１１への経路は既に削除されて存在しないので、中継端末２０６から受信した宛先端末２１１へのデータパケットは送信バッファに格納しておく。
【００９３】
経路修復を終了させた中継端末２０８では、ＳＴ７０１において、宛先端末２１１側の直接伝送を行う中継端末が中継端末２０９であるということが分かるので、ＳＴ７０２では、それまでの中継回数をインクリメントし、ＳＴ７０３では、バッファに格納していた宛先端末２１１へのデータパケットを次の中継端末である中継端末２０９にユニキャストで送信する。
【００９４】
ＳＴ７０４では、例えば、レイヤ２におけるデータ転送確認応答などを利用して、中継端末２０９へのデータ転送が完了したことを確認すると、自端末の経路キャッシュ１１６に記憶された該当するエントリの満了時間をリセットし、データ中継パケット受信処理を終了する。
【００９５】
ＳＴ７０５では、ＳＴ７０１において宛先端末２１１側の直接伝送を行う中継端末が存在しないと判定された中継端末２０８は、経路断前の自端末から宛先端末２１１までの中継回数に予め定められた値（ここではα）を加算したものと、送信元端末２１０までの中継回数を比較する。前者の方が小さければ（Ｙｅｓ）ＳＴ７０６に移行し、前者が後者以上に大きければ（Ｎｏ）ＳＴ７０９に移行する。
【００９６】
ＳＴ７０６では、中継端末２０８による宛先端末２１１への経路修復が許容されるものとして、経路断前の中継端末２０８からの宛先端末２１１までの中継回数に予め定められた値（ここではα：任意に設定が可能）を加算したものを中継限界数として設定する。
【００９７】
ＳＴ７０７では、中継端末２０８によって経路検索パケットの内容をあたかも送信元端末２１０から宛先端末２１１へのパケットであるかのように装い、経路修復のための経路検索パケットであることを明示して、宛先端末２１１への経路検索パケットをブロードキャストで送信する。
【００９８】
ＳＴ７０８では、更に、送信元端末２１０に経路を修復していることを通知するため、送信元端末２１０側の直接伝送を行う中継端末である中継端末２０６に宛先端末２１１への経路を修復中であることを示す経路エラーパケットをユニキャストで送信し、データ中継パケット受信処理を終了する。
【００９９】
ＳＴ７０９では、Ｓ７０５において前者が後者以上に大きいと判定された中継端末は、自端末による宛先端末への経路修復を許容できないとして、経路断を通知する経路エラーパケットを送信元端末２１０側の直接伝送を行う中継端末にユニキャストで送信し、データ中継パケット受信処理を終了する。
【０１００】
ここで、経路を再構築する場合について説明する。まず、経路エラーパケットを受信した送信元端末２１０は、自端末から宛先端末２１１への経路検索パケットを送信することにより、経路検索パケットが各端末において上述した経路検索パケット受信処理を施され、目的地となる宛先端末２１１へと伝播されていく。宛先端末２１１宛ての経路検索パケットを受信した宛先端末２１１では、送信元端末２１０に経路応答パケットを送信する。
【０１０１】
図１１に示すように、経路応答パケットを受信した中継端末２０６では、今まで宛先端末２１１側の直接伝送を行う中継端末は中継端末２０８であったが、中継端末２０９に切り替える。
【０１０２】
これにより、送信元端末２１０による宛先端末２１１への経路検索により、通信経路が送信元端末２１０→中継端末２０３→中継端末２０６→中継端末２０９→宛先端末２１１の合計４回の中継回数になり、上述した修復経路が送信元端末２１０→中継端末２０３→中継端末２０６→中継端末２０８→中継端末２０９→宛先端末２１１の合計５回の中継回数より減らすことができ、以降の通信はこの中継回数の少ない経路を使用して行われる。
【０１０３】
このように、中継端末２０８による宛先端末２１１への経路修復と送信元端末２１０への経路エラー通知とを同時に並行して行うことで、中継端末２０８に蓄積された宛先端末２１１へのデータパケット転送の再開から、送信元端末２１０による宛先端末２１１への最適経路の構築を行うまでの時間を短縮することができる。
【０１０４】
これまで説明してきた内容は、送信元端末２１０から宛先端末２１１への経路（以下、「第１の通信経路」という）を修復又は構築することを中心に想定したが、逆に、宛先端末２１１から送信元端末２１０への経路（以下、「第２の通信経路」という）を中心に考えることも可能であり、以下、この場合について説明する。なお、第１の通信経路では、送信元端末２１０を上流、宛先端末２１１を下流とし、第２の通信経路では、送信元端末２１０を下流、宛先端末２１１を上流として扱う。
【０１０５】
いま、図１２に示すように、送信元端末２１０と宛先端末２１１との間に中継端末２０３、２０６、２０８、２０９を経由する経路が確立しているものとする。ここで、この経路を用いてデータパケットを送信中に、中継端末２０８と２０９との間で経路断が発生した場合を考える。第２の通信経路に着目すると、中継端末２０９が経路断を検出し、送信元端末２１０までの中継回数及び宛先端末２１１までの中継回数と所定の閾値とをそれぞれ比較する。閾値以下となる場合には、経路断を検出した中継端末は該当する経路を修復するための経路検索パケットを送信することなく、経路断を示す経路エラー通知を端末に送信することがプロトコル上規定されている。ここでは、中継端末２０９は宛先端末２１１までの中継回数が閾値以下であることを認識し、図１３に示すように、第２の経路検索パケットを送信することなく、経路エラー通知を宛先端末２１１に送信する。
【０１０６】
一方、第１の通信経路に着目すると、中継端末２０８も経路断を検出し、既に説明しているように、経路検索パケットの内容をあたかも送信元端末２１０から宛先端末２１１へのパケットであるかのように装い、経路修復のための経路検索パケットであることを明示して、宛先端末２１１への経路検索パケットをブロードキャストで送信する。
【０１０７】
経路検索パケットのフォーマットは、図１４に示すように、各フィールドが定められており、このフィールドのうち、経路断を検出した端末から送信元端末までの中継回数を示す「Hop Count」、送信元端末のＩＰアドレスを示す「Originator IP Address」、送信元端末の最新のシーケンス番号を示す「Originator Sequence Number」を調整することにより、中継端末２０８から送信する経路検索パケットの内容を送信元端末２１０が送信したかのように装うことができる。
【０１０８】
中継端末２０８から経路検索パケットを受信した宛先端末２１１は、図１５に示すように、例えば、レイヤ２におけるデータ転送確認応答などを利用して、送信元端末２１０側の直接伝送を行う中継端末を２０９から２０８に更新する。すなわち、宛先端末２１１は中継端末２０８を経由すれば送信元端末２１０にデータパケットを送信可能であると認識することができる。これにより、図１６に示すように、第２の通信経路を迅速に修復することができる。
【０１０９】
このように本実施の形態によれば、経路断を検出した中継端末が、宛先端末へ経路検索パケットを送信するとともに、送信元端末へ経路断を通知することにより、中継端末による迅速な宛先端末への経路修復ができるとともに、送信元端末による最適な経路の検索を開始するまでの時間を短縮できる。また、中継端末による宛先端末への経路修復が失敗した場合でも、送信元端末による宛先端末への経路検索を開始するまでの時間を短縮できる。
【０１１０】
また、経路断箇所より宛先端末側において、経路修復のためのルートと経路再構築のためのルートを識別して経路応答することにより、同一の送信元端末からの異なる経路要求を同時に受信しても、複数の経路を同時に構築することができる。
【０１１１】
なお、本発明は上記実施の形態に限定されず、種々変更して実施することが可能である。例えば、上記実施の形態では、パケットルーティング装置として行う場合について説明しているが、これに限られるものではなく、このパケットルーティング方法をソフトウェアとして行うことも可能である。
【０１１２】
例えば、上記パケットルーティング方法を実行するプログラムを予めＲＯＭ（Read Only Memory）に格納しておき、そのプログラムをＣＰＵ（Central Processor Unit）によって動作させるようにしてもよい。
【０１１３】
また、上記パケットルーティング方法を実行するプログラムをコンピュータで読み取り可能な記憶媒体に格納し、記憶媒体に格納されたプログラムをコンピュータのＲＡＭ（Random Access Memory）に記録して、コンピュータをそのプログラムにしたがって動作させるようにしてもよい。
【産業上の利用可能性】
【０１１４】
本発明にかかるパケットルーティング方法及びパケットルーティング装置は、無線通信装置及び無線ＬＡＮ装置に用いて好適である。
【図面の簡単な説明】
【０１１５】
【図１】本発明の一実施の形態に係る無線アドホック端末の構成を示すブロック図
【図２】図１に示した無線アドホック端末の制御処理を示すフロー図
【図３】図１に示した無線アドホック端末を利用したネットワークの図
【図４】図１に示した無線アドホック端末を利用したネットワークの図
【図５】図１に示した無線アドホック端末を利用したネットワークの図
【図６】図２に示した経路エラーパケット受信処理を示すフロー図
【図７】図２に示した経路検索パケット受信処理を示すフロー図
【図８】図２に示した経路応答パケット受信処理を示すフロー図
【図９】図２に示したデータ発信パケット受信処理を示すフロー図
【図１０】図２に示したデータ中継パケット受信処理を示すフロー図
【図１１】図１に示した無線アドホック端末を利用したネットワークの図
【図１２】図１に示した無線アドホック端末を利用したネットワークの図
【図１３】図１に示した無線アドホック端末を利用したネットワークの図
【図１４】経路検索パケットのフォーマットを示す図
【図１５】図１に示した無線アドホック端末を利用したネットワークの図
【図１６】図１に示した無線アドホック端末を利用したネットワークの図
【図１７】従来の無線アドホック端末を利用したネットワークの図
【図１８】従来の無線アドホック端末を利用したネットワークの図
【図１９】従来の無線アドホック端末を利用したネットワークの図
【図２０】従来の無線アドホック端末を利用したネットワークの図
【図２１】従来の無線アドホック端末を利用したネットワークの図
【図２２】従来の無線アドホック端末を利用したネットワークの図
【符号の説明】
【０１１６】
１０１  送受信アンテナ
１０２  サーキュレータ
１０３  無線受信部
１０４  無線送信部
１０５  制御部
１１１  経路エラーパケット処理部
１１２  データ発信パケット処理部
１１３  経路応答パケット処理部
１１４  データ中継パケット処理部
１１５  経路検索パケット処理部
１１６  経路修復キャッシュ
１１７  ルーティング上位部
【図１】
2005269623.tif 000003
【図２】
2005269623.tif 000004
【図３】
2005269623.tif 000005
【図４】
2005269623.tif 000006
【図５】
2005269623.tif 000007
【図６】
2005269623.tif 000008
【図７】
2005269623.tif 000009
【図８】
2005269623.tif 000010
【図９】
2005269623.tif 000011
【図１０】
2005269623.tif 000012
【図１１】
2005269623.tif 000013
【図１２】
2005269623.tif 000014
【図１３】
2005269623.tif 000015
【図１４】
2005269623.tif 000016
【図１５】
2005269623.tif 000017
【図１６】
2005269623.tif 000018
【図１７】
2005269623.tif 000019
【図１８】
2005269623.tif 000020
【図１９】
2005269623.tif 000021
【図２０】
2005269623.tif 000022
【図２１】
2005269623.tif 000023
【図２２】
2005269623.tif 000024