(57)【要約】【課題】  アドホックネットワークにおいて、比較的長時間に渡って中継ノードが安定して存在するような経路構築をする移動ノードの経路構築方法及びプログラムを提供する。【解決手段】  直前中継ノード状態情報を含むＲＲＥＱを受信するステップと、直前中継ノード状態情報と自ノード状態情報とから差分状態情報を導出するステップと、差分状態情報を、直前中継ノードと自ノードとに対応付けて経路状態テーブルに記録するステップと、自ノード宛でない場合、ＲＲＥＱに自ノード状態情報及び経路状態テーブルを含めて放送的に送信するステップと、自ノード宛である場合、経路状態テーブルを用いて複数の戻り経路を導出し、各戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出し、該戻り経路リストを含むＲＲＥＰを送信するステップとを有する。【選択図】  図１
2005269042.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークにおける移動ノードの経路構築方法であって、
宛先アドレス、送信元アドレス及び直前中継ノード状態情報を含む経路要求メッセージを受信する第１のステップと、
前記直前中継ノード状態情報と自ノード状態情報とから差分状態情報を導出する第２のステップと、
前記差分状態情報を、前記直前中継ノードと前記自ノードとに対応付けて経路状態テーブルに記録する第３のステップと、
前記宛先アドレスが自ノードアドレスでない場合、前記経路要求メッセージに前記自ノード状態情報及び前記経路状態テーブルを含めて放送的に送信する第４のステップと、
前記宛先アドレスが自ノードアドレスである場合、前記経路状態テーブルを用いて前記送信元アドレスまでの複数の戻り経路を導出し、各戻り経路全体の前記差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出し、該戻り経路リストを含む経路応答メッセージを送信する第５のステップと
を有することを特徴とする経路構築方法。
【請求項２】
前記直前中継ノード状態情報は、直前中継ノードの位置情報であり、
前記自ノード状態情報は、自ノードの位置情報であり、
前記差分状態情報は、差分位置情報である
ことを特徴とする請求項１に記載の経路構築方法。
【請求項３】
前記直前中継ノード状態情報は、直前中継ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、
前記自ノード状態情報は、自ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、
前記差分状態情報は、走行速度情報、走行方向情報及び／又は通信品質情報の差分情報を更に含むことを特徴とする請求項２に記載の経路構築方法。
【請求項４】
前記第５のステップは、前記戻り経路リストの最上位の戻り経路における当該自ノードから次の直前中継ノードへ前記経路応答メッセージを送信することを特徴とする請求項１から３のいずれか１項に記載の経路構築方法。
【請求項５】
宛先アドレス、送信元アドレス及び前記戻り経路リストを含む前記経路応答メッセージを受信する第６のステップと、
前記経路応答メッセージの前記宛先アドレスが自ノードアドレスでない場合、前記経路状態テーブルに基づいて当該自ノードからの戻り経路全体の前記差分状態情報が相対的に小さく且つ変化の少ない戻り経路を導出する第７のステップと、
前記導出された戻り経路を前記戻り経路リストに含む前記経路応答メッセージを放送的に送信する第８のステップと
を更に有することを特徴とする請求項１から４のいずれか１項に記載の経路構築方法。
【請求項６】
前記第７のステップは、前記戻り経路リストに含まれていない経路についてのみ、前記戻り経路を導出することを特徴とする請求項５に記載の経路構築方法。
【請求項７】
前記経路要求メッセージを受信する毎に前記第１のステップから前記第３のステップまでを実行し、所定時間経過後に前記第４のステップ又は前記第５のステップを実行することを特徴とする請求項１から６のいずれか１項に記載の経路構築方法。
【請求項８】
アドホックネットワークにおける移動ノードの経路構築プログラムであって、
宛先アドレス、送信元アドレス及び直前中継ノード状態情報を含む経路要求メッセージを受信する第１のステップと、
前記直前中継ノード状態情報と自ノード状態情報とから差分状態情報を導出する第２のステップと、
前記差分状態情報を、前記直前中継ノードと前記自ノードとに対応付けて経路状態テーブルに記録する第３のステップと、
前記宛先アドレスが自ノードアドレスでない場合、前記経路要求メッセージに前記自ノード状態情報及び前記経路状態テーブルを含めて放送的に送信する第４のステップと、
前記宛先アドレスが自ノードアドレスである場合、前記経路状態テーブルを用いて前記送信元アドレスまでの複数の戻り経路を導出し、各戻り経路全体の前記差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出し、該戻り経路リストを含む経路応答メッセージを送信する第５のステップと
して実行させることを特徴とする経路構築プログラム。
【請求項９】
前記直前中継ノード状態情報は、直前中継ノードの位置情報であり、
前記自ノード状態情報は、自ノードの位置情報であり、
前記差分状態情報は、差分位置情報である
ことを特徴とする請求項８に記載の経路構築プログラム。
【請求項１０】
前記直前中継ノード状態情報は、直前中継ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、
前記自ノード状態情報は、自ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、
前記差分状態情報は、走行速度情報、走行方向情報及び／又は通信品質情報の差分情報を更に含むことを特徴とする請求項９に記載の経路構築プログラム。
【請求項１１】
前記第５のステップは、前記戻り経路リストの最上位の戻り経路における当該自ノードから次の直前中継ノードへ前記経路応答メッセージを送信することを特徴とする請求項８から１０のいずれか１項に記載の経路構築プログラム。
【請求項１２】
宛先アドレス、送信元アドレス及び前記戻り経路リストを含む前記経路応答メッセージを受信する第６のステップと、
前記経路応答メッセージの前記宛先アドレスが自ノードアドレスでない場合、前記戻り経路リストに含まれていない経路であって、前記経路状態テーブルに基づいて当該自ノードからの戻り経路全体の前記差分状態情報が相対的に小さく且つ変化の少ない戻り経路を導出する第７のステップと、
前記導出された戻り経路を前記戻り経路リストに含む前記経路応答メッセージを放送的に送信する第８のステップと
を更に有することを特徴とする請求項８から１１のいずれか１項に記載の経路構築プログラム。
【請求項１３】
前記第７のステップは、前記戻り経路リストに含まれていない経路についてのみ、前記戻り経路を導出することを特徴とする請求項１２に記載の経路構築プログラム。
【請求項１４】
前記経路要求メッセージを受信する毎に前記第１のステップから前記第３のステップまでを実行し、所定時間経過後に前記第４のステップ又は前記第５のステップを実行することを特徴とする請求項８から１３のいずれか１項に記載の経路構築プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックネットワークにおける移動通信装置（以下「移動ノード」という）の経路構築方法及びプログラムに関する。
【背景技術】
【０００２】
従来、アドホックネットワークにおける移動ノードの経路構築プロトコルとして、ＤＳＲ（Dynamic Source Routing）がある（例えば非特許文献１参照）。このプロトコルは、パケット自体に、送信元ノードから宛先ノードまでの経路情報を含むものである。
【０００３】
最初に、通信開始ノードは、経路キャッシュに経路情報を問い合わせ、宛先ノードに対する経路情報の有無を確認する。宛先ノードへの経路情報が存在しない場合、通信開始ノードは、経路要求メッセージＲＲＥＱ(Route Request)を放送的に送信し（ブロードキャスト）する。次に、ＲＲＥＱを受信したノードは、自ノードアドレスをＲＲＥＱの経路情報に追加して更に転送する。尚、その経路情報に、既に自ノードのアドレスが含まれている場合には、ＲＲＥＱを破棄する。ＲＲＥＱを受信した宛先ノードは、経路応答メッセージＲＲＥＰ(Route Reply)を当該経路情報に沿って返信する。
【０００４】
また、他の経路構築プロトコルとして、ＡＯＤＶ（Ad hoc On-Demand Distance Vector）がある（例えば非特許文献２参照）。このプロトコルは、パケット自体に経路情報を含まず、中継ノードが宛先ノードへの経路表を有するものである。
【０００５】
更に、当該ノードの地理的な位置情報に基づいて、他のノードへメッセージを送信するか否かを決定するものもある（例えば特許文献１参照）。
【０００６】
【非特許文献１】IETF MANET Working Group INTERNET-DRAFT "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)"、［online］、[平成１６年３月５日検索]、インターネット＜ＵＲＬ：http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-09.txt＞
【非特許文献２】IETF RFC 3561 "Ad hoc On-Demand Distance Vector (AODV) Routing"、［online］、[平成１６年３月５日検索]、インターネット＜ＵＲＬ：http://www.faqs.org/rfcs/rfc3561.html＞
【特許文献１】特開２００２−３６８７８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述した技術によれば、経路構築時における中継ノードの位置情報（ノード間の離隔距離又は相対速度）が全く考慮されていない。従って、その時点においては、最適な経路を構築できたとしても、その経路に位置情報等が直ぐに変化する中継ノードが介在していた場合、再び経路構築をやり直さなければならない。従って、経路再構築が頻繁に行われる場合も想定され、その経路再構築のためのＲＲＥＱ及びＲＲＥＰによって電波リソースが逼迫し、他ユーザへの通信に影響を及ぼす可能性もある。
【０００８】
そこで、本発明は、アドホックネットワークにおいて、比較的長時間に渡って中継ノードが安定して存在するような経路構築をすることができる移動ノードの経路構築方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明における移動ノードの経路構築方法によれば、
宛先アドレス、送信元アドレス及び直前中継ノード状態情報を含む経路要求メッセージを受信する第１のステップと、
直前中継ノード状態情報と自ノード状態情報とから差分状態情報を導出する第２のステップと、
差分状態情報を、直前中継ノードと自ノードとに対応付けて経路状態テーブルに記録する第３のステップと、
宛先アドレスが自ノードアドレスでない場合、経路要求メッセージに自ノード状態情報及び経路状態テーブルを含めて放送的に送信する第４のステップと、
宛先アドレスが自ノードアドレスである場合、経路状態テーブルを用いて送信元アドレスまでの複数の戻り経路を導出し、各戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出し、該戻り経路リストを含む経路応答メッセージを送信する第５のステップと
を有することを特徴とする。
【００１０】
尚、直前中継ノード状態情報とは、経路要求メッセージを送信した直前のノード（自ノードから１ホップ先）を意味する。従って、送信元アドレスに対応する送信元ノードが最初に送信した経路要求メッセージには、送信元ノードのノード状態情報が含まれることとなる。
【００１１】
本発明の経路構築方法における他の実施形態によれば、直前中継ノード状態情報は、直前中継ノードの位置情報であり、自ノード状態情報は、自ノードの位置情報であり、差分状態情報は、差分位置情報であることも好ましい。また、直前中継ノード状態情報は、直前中継ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、自ノード状態情報は、自ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、差分状態情報は、走行速度情報、走行方向情報及び／又は通信品質情報を更に含むものであってもよい。
【００１２】
また、本発明の経路構築方法における他の実施形態によれば、第５のステップは、戻り経路リストの最上位の戻り経路における当該自ノードから次の直前中継ノードへ経路応答メッセージを送信することも好ましい。
【００１３】
更に、本発明の経路構築方法における他の実施形態によれば、
宛先アドレス、送信元アドレス及び戻り経路リストを含む経路応答メッセージを受信する第６のステップと、
経路応答メッセージの宛先アドレスが自ノードアドレスでない場合、経路状態テーブルに基づいて当該自ノードからの戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ない戻り経路を導出する第７のステップと、
導出された戻り経路を戻り経路リストに含む経路応答メッセージを放送的に送信する第８のステップとを更に有することも好ましい。
【００１４】
更に、本発明の経路構築方法における他の実施形態によれば、第７のステップは、戻り経路リストに含まれていない経路についてのみ、戻り経路を導出することも好ましい。
【００１５】
更に、本発明の経路構築方法における他の実施形態によれば、前記経路要求メッセージを受信する毎に前記第１のステップから前記第３のステップまでを実行し、所定時間経過後に前記第４のステップ又は前記第５のステップを実行することも好ましい。
【００１６】
本発明における移動ノードの経路構築プログラムによれば、
宛先アドレス、送信元アドレス及び直前中継ノード状態情報を含む経路要求メッセージを受信する第１のステップと、
直前中継ノード状態情報と自ノード状態情報とから差分状態情報を導出する第２のステップと、
差分状態情報を、直前中継ノードと自ノードとに対応付けて経路状態テーブルに記録する第３のステップと、
宛先アドレスが自ノードアドレスでない場合、経路要求メッセージに自ノード状態情報及び経路状態テーブルを含めて放送的に送信する第４のステップと、
宛先アドレスが自ノードアドレスである場合、経路状態テーブルを用いて送信元アドレスまでの複数の戻り経路を導出し、各戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出し、該戻り経路リストを含む経路応答メッセージを送信する第５のステップと
して実行させることを特徴とする。
【００１７】
本発明の経路構築プログラムにおける他の実施形態によれば、直前中継ノード状態情報は、直前中継ノード状態情報は、直前中継ノードの位置情報であり、自ノード状態情報は、自ノードの位置情報であり、差分状態情報は、差分位置情報であることも好ましい。また、直前中継ノード状態情報は、直前中継ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、自ノード状態情報は、自ノードの走行速度情報、走行方向情報及び／又は通信品質情報を更に含み、差分状態情報は、走行速度情報、走行方向情報及び／又は通信品質情報の差分情報を更に含むものであってもよい。
【００１８】
また、本発明の経路構築プログラムにおける他の実施形態によれば、第５のステップは、戻り経路リストの最上位の戻り経路における当該自ノードから次の直前中継ノードへ経路応答メッセージを送信することも好ましい。
【００１９】
更に、本発明の経路構築プログラムにおける他の実施形態によれば、
経路応答メッセージの宛先アドレスが自ノードアドレスでない場合、戻り経路リストに含まれていない経路であって、経路状態テーブルに基づいて当該自ノードからの戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ない戻り経路を導出する第７のステップと、
導出された戻り経路を戻り経路リストに含む経路応答メッセージを放送的に送信する第８のステップと
を更に有することも好ましい。
【発明の効果】
【００２０】
本発明によれば、差分状態情報が相対的に小さく且つ変化の少ない経路を選択することができるので、アドホックネットワークにおいて、比較的長時間に渡って中継ノードが安定して存在するような経路構築をすることができる。従って、経路再構築が頻繁に行われることもなく、電波リソースにおけるＲＲＥＱ及びＲＲＥＰの割合も比較的低減し、他ユーザの通信に及ぼす影響も小さくなる。特に、大量の移動ノードが存在し且つ他のノードを中継してデータを送受信する環境に適用するＩＴＳ(Intelligent Transport Systems)においては、極めて有効である。
【００２１】
また、差分状態情報に基づいて、離隔距離が比較的短距離の中継ノードが選択されるので、ノード間の電波強度を比較的高く維持できる。また、相対速度が比較的小さい中継ノードが選択されるので、自ノードの走行速度に対して極端に高速又は低速な中継ノードが選択されない。更に、相対角度が比較的小さい中継ノードが選択されるので、自ノードの走行方向に対して極端に異なる方向へ進む中継ノードは選択されない。更に、ノード間の通信品質情報も考慮するので、経路中に極端に通信品質の悪いノード間が存在しても、その経路は選択されない。
【００２２】
更に、ＲＲＥＰの送信元ノードが、戻り経路リストを含むＲＲＥＰを送信しても、時間変化によって既にその最上位の戻り経路が最適でないと中継ノードが判断した場合、中継ノード自身が戻り経路リストの優先順位を変更することができるので、ＲＲＥＱの送信元ノードは、最適の戻り経路リストを取得することができる。
【００２３】
更に、宛先アドレスに対応する宛先ノードが、戻り経路リストを含むＲＲＥＰを送信しても、その後、ノード間の差分情報に基づいて最適経路が異なると中継ノードが判断した場合、その戻り経路リストを中継ノードが変更することができるので、ＲＲＥＱの送信元ノードは、より新しい最適な戻り経路リストを取得することができる。
【００２４】
更に、第３のステップと第４又は第５のステップとの間に所定の待ち時間を設けることにより、中継ノードは、より多くの経路を中継したＲＲＥＱを受信することができるので、より多くの差分状態情報をＲＲＥＱに含めて転送することができる。
【発明を実施するための最良の形態】
【００２５】
以下では、図面を用いて、本発明における最良の実施形態について詳細に説明する。
【００２６】
図１は、本発明における具体的なシーケンス図である。
【００２７】
図１によれば、各車両は、移動ノードを搭載して移動している。各移動ノードは、ＧＰＳ(Global Positioning System)によって位置情報（経度及び緯度）を取得でき、速度計測器から走行速度を取得でき、ＧＰＳによって又は位置情報の時間変化から走行方向を取得できる。本発明によれば、送信元ノードＡは、宛先ノードＥへＲＲＥＱを送信し、そのＲＲＥＰを宛先ノードＥから受信することによって、最適な経路シーケンスを取得することができる。尚、図１は、アドホック通信における信号到達距離が２ホップであるとして説明している。
【００２８】
ここで、ＲＲＥＱは、各ノードでフラッディングされて転送される。フラッディングとは、送信元ノードの無線信号到達範囲内に存在する全てのノードにブロードキャストでメッセージを転送し、受信したノードも同様に繰り返すことによって、ネットワーク全体にメッセージを伝播する技術のことである。既存のＡＯＤＶは基本的に１対１の経路探索プロトコルであるので、ＲＲＥＱの宛先ノードはフラッディングの機能を備えているものではない。従って、ＲＲＥＱヘッダにホップカウントが含まれる。
【００２９】
表１は、本発明におけるＲＲＥＱメッセージフォーマットである。
【表１】
2005269042.tif 000003
【００３０】
表１によれば、先の送信元となる直前中継ノードにおける位置情報、走行速度及び走行方向が、ＲＲＥＱに含まれていることに特徴がある。直前中継ノードの位置情報等と、自ノードの位置情報等とを比較することで、ノード間差分情報を導出することができ、導出されたノード間差分情報は、更にＲＲＥＱに含まれて転送される。
【００３１】
表２は、本発明におけるＲＲＥＰメッセージフォーマットである。
【表２】
2005269042.tif 000004
【００３２】
表２によれば、戻り経路リストが、ＲＲＥＰに含まれていることに特徴がある。戻り経路リストは、最適経路からの順位付けがされている。
【００３３】
以下では、図１のシーケンスに基づいて順次説明する。
【００３４】
（Ｓ１０１）ノードＡが、ノードＥとの間で最適経路を構築しようとしている。このとき、ノードＡは、以下のメッセージフォーマットのＲＲＥＱをブロードキャストで送信する。宛先アドレスはノードＥのアドレスを示し、送信元アドレスはノードＡのアドレスを示す。ＲＲＥＱには、更に、ノードＡの位置情報、走行速度及び走行方向が含まれている。尚、信号到達距離は２ホップであるので、ノードＡから送信されたＲＲＥＱは、ノードＢ及びＣによって受信される。
【００３５】
【表３】
2005269042.tif 000005
【００３６】
（Ｓ１０２）ノードＢは、ノードＡからＲＲＥＱを受信する。このとき、ノードＢは、ノードＡの位置情報、走行速度及び走行方向と、ノードＢの位置情報、走行速度及び走行方向との差分情報(N1)を導出する。更に、ＲＲＥＱの受信品質情報も含む。ノードＢは、差分情報(N1)を、ノードＢの経路状態テーブルに記録する。
差分情報(N1)：ノードＢの緯度−ノードＡの緯度        ＝緯度差分
ノードＢの経度−ノードＡの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｂ−Ａ間の離隔距離
ノードＢの走行速度−ノードＡの走行速度＝Ｂ−Ａ間の相対速度
ノードＢの走行方向−ノードＡの走行方向＝Ｂ−Ａ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｂ−Ａ間の通信品質
【００３７】
（Ｓ１０３）ノードＣは、ノードＡからＲＲＥＱを受信する。このとき、ノードＣは、ノードＡの位置情報、走行速度及び走行方向と、ノードＣの位置情報、走行速度及び走行方向との差分情報(N2)を導出する。更に、ＲＲＥＱの受信品質情報も含む。ノードＣは、差分情報(N2)を、ノードＣの経路状態テーブルに記録する。
差分情報(N2)：ノードＣの緯度−ノードＡの緯度        ＝緯度差分
ノードＣの経度−ノードＡの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｃ−Ａ間の離隔距離
ノードＣの走行速度−ノードＡの走行速度＝Ｃ−Ａ間の相対速度
ノードＣの走行方向−ノードＡの走行方向＝Ｃ−Ａ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｃ−Ａ間の通信品質
【００３８】
（Ｓ１０４）ノードＢは、ノードＡから受信したＲＲＥＱの宛先アドレスが自ノードアドレスではないために、更にＲＲＥＱを転送する。このとき、ノードＢは、以下のメッセージフォーマットのＲＲＥＱをブロードキャストで送信する。ＲＲＥＱには、ノードＢの位置情報、走行速度及び走行方向と、差分情報（N1)とが含まれる。尚、信号到達距離は２ホップであるので、ノードＢから送信されたＲＲＥＱは、ノードＡと、ノードＣ及びＤとによって受信される。
【００３９】
【表４】
2005269042.tif 000006
【００４０】
（Ｓ１０５）ノードＣは、ノードＢからＲＲＥＱを受信する。そのＲＲＥＱには、ノードＢの位置情報等と、Ｂ−Ａ差分情報(N1)とを含む。このとき、ノードＣは、ノードＢの位置情報、走行速度及び走行方向と、ノードＣの位置情報、走行速度及び走行方向との差分情報(N3)を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＣは、差分情報(N3)と、受信したＢ−Ａ差分情報(N1)とを、ノードＣの経路状態テーブルに記録する。
差分情報(N3)：ノードＣの緯度−ノードＢの緯度        ＝緯度差分
ノードＣの経度−ノードＢの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｃ−Ｂ間の離隔距離
ノードＣの走行速度−ノードＢの走行速度＝Ｃ−Ｂ間の相対速度
ノードＣの走行方向−ノードＢの走行方向＝Ｃ−Ｂ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｃ−Ｂ間の通信品質
【００４１】
（Ｓ１０６）ノードＤは、ノードＢからＲＲＥＱを受信する。そのＲＲＥＱには、ノードＢの位置情報等と、Ｂ−Ａ差分情報(N1)とを含む。このとき、ノードＤは、ノードＢの位置情報、走行速度及び走行方向と、ノードＤの位置情報、走行速度及び走行方向との差分情報(N4)を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＤは、差分情報(N4)と、受信したＢ−Ａ差分情報(N1)とを、ノードＤの経路状態テーブルに記録する。
差分情報(N4)：ノードＤの緯度−ノードＢの緯度        ＝緯度差分
ノードＤの経度−ノードＢの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｄ−Ｂ間の離隔距離
ノードＤの走行速度−ノードＢの走行速度＝Ｄ−Ｂ間の相対速度
ノードＤの走行方向−ノードＢの走行方向＝Ｄ−Ｂ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｄ−Ｂ間の通信品質
【００４２】
（Ｓ１０７）ノードＡは、ノードＢからＲＲＥＱを受信する。そのＲＲＥＱには、ノードＢの位置情報等と、Ｂ−Ａ差分情報(N1)とを含む。このとき、ノードＡは、ノードＢの位置情報、走行速度及び走行方向と、ノードＡの位置情報、走行速度及び走行方向との差分情報(N3')を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＡは、差分情報(N3')と、受信したＢ−Ａ差分情報(N1)とを、ノードＡの経路状態テーブルに記録する。
差分情報(N3')：ノードＡの緯度−ノードＢの緯度        ＝緯度差分
ノードＡの経度−ノードＢの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ａ−Ｂ間の離隔距離
ノードＡの走行速度−ノードＢの走行速度＝Ａ−Ｂ間の相対速度
ノードＡの走行方向−ノードＢの走行方向＝Ａ−Ｂ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ａ−Ｂ間の通信品質
【００４３】
（Ｓ１０８）ノードＣは、ノードＡから受信したＲＲＥＱの宛先アドレスが自ノードアドレスではないため、更にＲＲＥＱを転送する。このとき、ノードＣは、以下のメッセージフォーマットのＲＲＥＱをブロードキャストで送信する。ＲＲＥＱには、ノードＣの位置情報、走行速度及び走行方向と、差分情報（N2)とが含まれている。尚、信号到達距離は２ホップであるので、ノードＣから送信されたＲＲＥＱは、ノードＡ及びＢと、ノードＤ及びＥとによって受信される。
【００４４】
【表５】
2005269042.tif 000007
【００４５】
（Ｓ１０９）ノードＤは、ノードＣからＲＲＥＱを受信する。このとき、ノードＤは、ノードＣの位置情報、走行速度及び走行方向と、ノードＤの位置情報、走行速度及び走行方向との差分情報(N5)を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＤは、差分情報(N5)と、受信したＣ−Ａ差分情報(N2)とを、ノードＤの経路状態テーブルに記録する。
差分情報(N5)：ノードＤの緯度−ノードＣの緯度        ＝緯度差分
ノードＤの経度−ノードＣの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｄ−Ｃ間の離隔距離
ノードＤの走行速度−ノードＣの走行速度＝Ｄ−Ｃ間の相対速度
ノードＤの走行方向−ノードＣの走行方向＝Ｄ−Ｃ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｄ−Ｃ間の通信品質
【００４６】
（Ｓ１１０）ノードＥは、ノードＣからＲＲＥＱを受信する。このとき、ノードＥは、ノードＣの位置情報、走行速度及び走行方向と、ノードＥの位置情報、走行速度及び走行方向との差分情報(N6)を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＥは、差分情報(N6)と、受信したＣ−Ａ差分情報(N2)とを、ノードＥの経路状態テーブルに記録する。
差分情報(N6)：ノードＥの緯度−ノードＣの緯度        ＝緯度差分
ノードＥの経度−ノードＣの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｅ−Ｃ間の離隔距離
ノードＥの走行速度−ノードＣの走行速度＝Ｅ−Ｃ間の相対速度
ノードＥの走行方向−ノードＣの走行方向＝Ｅ−Ｃ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｅ−Ｃ間の通信品質
【００４７】
（Ｓ１１１）ノードＢは、ノードＣからＲＲＥＱを受信する。このとき、ノードＢは、ノードＣの位置情報、走行速度及び走行方向と、ノードＢの位置情報、走行速度及び走行方向との差分情報(N5')を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＢは、差分情報(N5')と、受信したＣ−Ａ差分情報(N2)とを、ノードＢの経路状態テーブルに記録する。
差分情報(N5')：ノードＢの緯度−ノードＣの緯度        ＝緯度差分
ノードＢの経度−ノードＣの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｂ−Ｃ間の離隔距離
ノードＢの走行速度−ノードＣの走行速度＝Ｂ−Ｃ間の相対速度
ノードＢの走行方向−ノードＣの走行方向＝Ｂ−Ｃ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｂ−Ｃ間の通信品質
【００４８】
（Ｓ１１２）ノードＡは、ノードＣからＲＲＥＱを受信する。このとき、ノードＡは、ノードＣの位置情報、走行速度及び走行方向と、ノードＡの位置情報、走行速度及び走行方向との差分情報(N6')を導出する。更に、ＲＲＥＱの受信品質情報を含む。ノードＡは、差分情報(N6')と、受信したＣ−Ａ差分情報(N2)とを、ノードＡの経路状態テーブルに記録する。
差分情報(N6')：ノードＡの緯度−ノードＣの緯度        ＝緯度差分
ノードＡの経度−ノードＣの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ａ−Ｃ間の離隔距離
ノードＡの走行速度−ノードＣの走行速度＝Ａ−Ｃ間の相対速度
ノードＡの走行方向−ノードＣの走行方向＝Ａ−Ｃ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ａ−Ｃ間の通信品質
【００４９】
（Ｓ１１３）ノードＤは、ノードＣから受信したＲＲＥＱの宛先アドレスが自ノードアドレスでないため、更にＲＲＥＱを転送する。このとき、ノードＤは、以下のメッセージフォーマットのＲＲＥＱをブロードキャストで送信する。ＲＲＥＱには、ノードＤの位置情報、走行速度及び走行方向と、差分情報（N1)（N2)（N4)（N5)とが含まれる。更に、ＲＲＥＱの受信品質情報を含む。尚、信号到達距離は２ホップであるので、ノードＤから送信されたＲＲＥＱは、ノードＢ及びＣとノードＥとによって受信される。
【００５０】
【表６】
2005269042.tif 000008
【００５１】
（Ｓ１１４）ノードＥは、ノードＤからＲＲＥＱを受信する。このとき、ノードＥは、ノードＤの位置情報、走行速度及び走行方向と、ノードＥの位置情報、走行速度及び走行方向との差分情報(N7)を導出する。更に、ＲＲＥＱの受信品質情報を含む。
差分情報(N7)：ノードＥの緯度−ノードＤの緯度        ＝緯度差分
ノードＥの経度−ノードＤの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｅ−Ｄ間の離隔距離
ノードＥの走行速度−ノードＤの走行速度＝Ｅ−Ｄ間の相対速度
ノードＥの走行方向−ノードＤの走行方向＝Ｅ−Ｄ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｅ−Ｄ間の通信品質
【００５２】
ノードＥは、差分情報(N7)と、受信したＢ−Ａ差分情報(N1)、Ｃ−Ａ分情報(N2)、Ｄ−Ｂ差分情報(N4)及びＤ−Ｃ差分情報(N5)とを、ノードＥの経路状態テーブルに記録する。
【００５３】
ノードＥの経路状態テーブルは、以下のようになる。
【表７】
2005269042.tif 000009
【００５４】
（Ｓ１１５）ノードＣは、ノードＤからＲＲＥＱを受信する。このとき、ノードＣは、ノードＤの位置情報、走行速度及び走行方向と、ノードＣの位置情報、走行速度及び走行方向との差分情報(N7')を導出する。更に、ＲＲＥＱの受信品質情報を含む。
差分情報(N7')：ノードＣの緯度−ノードＤの緯度        ＝緯度差分
ノードＣの経度−ノードＤの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｃ−Ｄ間の離隔距離
ノードＣの走行速度−ノードＤの走行速度＝Ｃ−Ｄ間の相対速度
ノードＣの走行方向−ノードＤの走行方向＝Ｃ−Ｄ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｃ−Ｄ間の通信品質
ノードＣは、差分情報(N7')と、受信したＢ−Ａ差分情報(N1)、Ｃ−Ａ分情報(N2)、Ｄ−Ｂ差分情報(N4)及びＤ−Ｃ差分情報(N5)とを、ノードＣの経路状態テーブルに記録する。
【００５５】
（Ｓ１１６）ノードＢは、ノードＤからＲＲＥＱを受信する。このとき、ノードＢは、ノードＤの位置情報、走行速度及び走行方向と、ノードＢの位置情報、走行速度及び走行方向との差分情報(N8')を導出する。更に、ＲＲＥＱの受信品質情報を含む。
差分情報(N8')：ノードＢの緯度−ノードＤの緯度        ＝緯度差分
ノードＢの経度−ノードＤの経度        ＝経度差分
√（緯度差分２＋経度差分２）            ＝Ｂ−Ｄ間の離隔距離
ノードＢの走行速度−ノードＤの走行速度＝Ｂ−Ｄ間の相対速度
ノードＢの走行方向−ノードＤの走行方向＝Ｂ−Ｄ間の相対角度
ＲＲＥＱの受信品質情報                ＝Ｂ−Ｄ間の通信品質
ノードＢは、差分情報(N8')と、受信したＢ−Ａ差分情報(N1)、Ｃ−Ａ分情報(N2)、Ｄ−Ｂ差分情報(N4)及びＤ−Ｃ差分情報(N5)とを、ノードＢの経路状態テーブルに記録する。
【００５６】
（Ｓ１１７）ノードＥは、経路状態テーブルに基づいて、ノードＡまでの複数の戻り経路を導出する。これは、ノードＥからノードＡまでの組み合わせに基づく。
【００５７】
図２は、図１に基づいて導出された戻り経路の木構造図である。
【００５８】
図２によれば、３つの戻り経路が導出される。
（戻り経路１）ノードＥ->ノードＤ->ノードＢ->ノードＡ
（戻り経路２）ノードＥ->ノードＤ->ノードＣ->ノードＡ
（戻り経路３）ノードＥ->ノードＣ->ノードＡ
【００５９】
各戻り経路の全てのノード間差分情報に基づいて、最適な戻り経路を選択する。その選択方法としては、差分評価値による方法がある。これは、ノード間の差分情報に基づいて各要素を評価する。ここでは、例として、差分評価値が低いほど経路選択に有効であると考える。
離隔距離：ｘ１ｍ以下      ＝差分評価値０
ｘ１〜ｘ２      ＝差分評価値１
ｘ２以上        ＝差分評価値２
相対速度：ｙ１ｋｍ／ｈ以下＝差分評価値０
ｙ１〜ｙ２      ＝差分評価値１
ｙ２以上        ＝差分評価値２
相対角度：ｚ１°以下      ＝差分評価値０
ｚ１°〜ｚ２°  ＝差分評価値１
ｚ２°以上      ＝差分評価値２
通信品質：ｗ１Ｓ／Ｎ以下  ＝差分評価値０
ｗ１〜ｗ２以下  ＝差分評価値１
ｗ３以上        ＝差分評価値２
【００６０】
例えば、経路状態デーブルの差分情報に、以下のような差分評価値を与えたとする。
Ｅ−Ｄ間差分情報(N7)：差分評価値３
Ｅ−Ｃ間差分情報(N6)：差分評価値４
Ｄ−Ｃ間差分情報(N5)：差分評価値２
Ｄ−Ｂ間差分情報(N4)：差分評価値５
Ｃ−Ａ間差分情報(N2)：差分評価値３
Ｂ−Ａ間差分情報(N1)：差分評価値４
【００６１】
３つの戻り経路は、以下のような差分評価値となる。
（戻り経路１）ノードＥ（３）ノードＤ（５）ノードＢ（４）ノードＡ
（戻り経路２）ノードＥ（３）ノードＤ（２）ノードＣ（３）ノードＡ
（戻り経路３）ノードＥ（４）ノードＣ（３）ノードＡ
【００６２】
そうすると、差分評価値４及び５を含まない戻り経路２が最も良いことが理解できる。本発明は、単に、ノードＥから見てノードＣ又はノードＤのいずれの差分情報が少ないかだけで判断するものではない。戻り経路全体に渡って、長時間に渡って安定した経路を選択するためのものである。
【００６３】
ノードＥは、戻り経路が優先順に並べられた戻り経路リストを含むＲＲＥＰを送信する。このとき、戻り経路リストの最上位について次ノードがノードＤであるので、ＲＲＥＰはノードＤへ送信される。表８は、ノードＥが送信するＲＲＥＰのメッセージフォーマットである。
【００６４】
【表８】
2005269042.tif 000010
【００６５】
（Ｓ１１８）ノードＤは、ＲＲＥＰを受信した場合、Ｆ１に基づいて、ＲＲＥＰをノードＣへ送信する。
【００６６】
（Ｓ１１９）ノードＥは、戻り経路が優先順に並べられた戻り経路リストを含むＲＲＥＰを送信する。例えば、戻り経路リストの最上位について次ノードがノードＣである場合、ＲＲＥＰはノードＣへ送信される。表９は、ノードＥが送信するＲＲＥＰのメッセージフォーマットである。
【００６７】
【表９】
2005269042.tif 000011
【００６８】
（Ｓ１２０）受信したＲＲＥＰの戻り経路リストにはノードＣ->ノードＡの経路のみが含まれている。しかしながら、ノードＣの経路状態テーブルを参照すると、ノードＣ->ノードＢ->ノードＡの経路の方が差分評価値としては良い場合もある。
Ｃ−Ａ間差分情報(N2)：差分評価値３
Ｂ−Ａ間差分情報(N1)：差分評価値４
Ｃ−Ｂ間差分情報(N3)：差分評価値２
そうすると、ノードＣは、ノードＣ->ノードＢ->ノードＡの経路をＲＲＥＰの戻り経路リストに含めて、ノードＢへ送信する。
【００６９】
【表１０】
2005269042.tif 000012
【００７０】
（Ｓ１２１）ノードＣは、前述Ｓ１２０と同様に判断して、ノードＣ->ノードＡの経路が有効である場合、ノードＣは、ＲＲＥＰそのままをノードＡへ送信する。
【００７１】
【表１１】
2005269042.tif 000013
【００７２】
（Ｓ１２２）ノードＤは、戻り経路リストで(F2)Ｅ->Ｄ->Ｂ->Ａが最上位にリストされていれば、ノードＢへＲＲＥＰを送信する。
【００７３】
（Ｓ１２３）ノードＢは、戻り経路リストに従って、ノードＡへＲＲＥＰを送信する。
【００７４】
前述したＳ１０１〜Ｓ１２３のシーケンスによって、ノードＡは、ノード間差分情報を考慮した最適経路を構築することができる。
【００７５】
図３は、ＲＲＥＱを受信した際のフローチャートである。
【００７６】
自ノードは、ＧＰＳ等によって取得された現在の位置情報と、速度計測器によって取得された現在の走行速度と、その位置情報の時間的変化から得られた走行方向とを、自ノード情報として常に保持する。
（Ｓ２１）ＲＲＥＱを受信する。ＲＲＥＱには、宛先アドレスと、送信元アドレスと、直前中継ノード情報（直前中継ノードの位置情報、走行速度及び走行方向）と、直前中継ノードで取得されたノード間差分情報とが含まれている。
（Ｓ２２）直前中継ノード情報と、自ノード情報との差分情報を導出する。
（Ｓ２３）その差分情報と、ＲＲＥＱに含まれるノード間差分情報とを、経路状態テーブルに記録する。
（Ｓ２４）ＲＲＥＱの宛先アドレスが、自ノードアドレスか否かを判定する。
（Ｓ２５）ＲＲＥＱの宛先アドレスが自ノードアドレスでないならば、更にＲＲＥＱを転送する。このとき、ＲＲＥＱには、経路状態テーブルのノード間差分情報と、直前中継ノードとしての自ノード情報とを含める。
（Ｓ２６）ＲＲＥＱの宛先アドレスが自ノードアドレスであるならば、経路状態テーブルを用いて複数の戻り経路を導出する。このとき、ノード間差分情報の評価に基づいて評価値を定め、各戻り経路全体の差分評価値が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを生成する。
（Ｓ２７）自ノード情報（自ノードの位置情報、走行速度及び走行方向）と、ノード間差分情報とを含むＲＲＥＰを送信する。
【００７７】
図４は、ＲＲＥＰを受信した際のフローチャートである。
【００７８】
（Ｓ４１）ＲＲＥＰを受信する。ＲＲＥＰには、宛先アドレスと、送信元アドレスと、戻り経路リストとが含まれている。
（Ｓ４２）ＲＲＥＰの宛先アドレスが、自ノードアドレスか否かを判定する。
（Ｓ４３）ＲＲＥＰの宛先アドレスが自ノードアドレスでないならば、ＲＲＥＰの戻り経路リストにおける次ノードを確認する。このとき、経路状態テーブルを参照して、自ノードから次ノードに対する経路として他の最適経路が存在するならば、その経路を戻り経路リストに含める。
（Ｓ４４）次ノードへＲＲＥＰを送信する。
（Ｓ４５）ＲＲＥＰの宛先アドレスが自ノードアドレスであるならば、ＲＲＥＰの戻り経路リストに含まれる経路を最適経路として保持する。
【００７９】
図５は、本発明における移動ノードの機能構成図である。
【００８０】
図５によれば、移動ノード１は、無線通信インタフェース部１０と、位置情報測定部１１と、走行速度計測部１２と、メッセージ判定部１３と、差分情報導出部１４と、経路状態テーブル記録部１５と、ＲＲＥＱ送信部１６と、ＲＲＥＰ送信部１７と、戻り経路導出部１８とを有する。
【００８１】
無線通信インタフェース１０は、無線ＬＡＮ等を介して、他の移動ノードとパケットを送受信する。位置情報測定部１１は、ＧＰＳ等によって常に自ノードの現在位置（緯度経度）を測定する。走行速度計測部１２は、自ノードの走行速度を速度メータ等から取得する。
【００８２】
メッセージ判定部１３は、受信されたメッセージがＲＲＥＱか又はＲＲＥＰかを判定する。
【００８３】
差分情報導出部１４は、位置情報測定部１１及び走行速度計測部１２から自ノードの位置情報及び走行速度を取得する。また、位置情報の時間変化から走行方向を取得する。これら自ノードの位置情報、走行速度及び走行方向を自ノード情報として、ＲＲＥＱに含まれる直前中継ノード情報（直前中継ノードの位置情報、走行速度及び走行方向）との差分情報を導出する。
【００８４】
経路状態テーブル記録部１５は、差分情報導出部１４によって導出された差分情報を、自ノード及び直前中継ノードに対応付けて記憶する。
【００８５】
ＲＲＥＱ送信部１６は、自ノード情報（自ノードの位置情報、走行速度及び走行方向）と、経路状態テーブルの情報とを含めたＲＲＥＱを、無線通信インタフェース１０へ送信する。
【００８６】
戻り経路導出部１８は、ＲＲＥＱに対しては、経路状態テーブルを用いて送信元アドレスまでの複数の戻り経路を導出する。そして、各戻り経路全体の差分状態情報が相対的に小さく且つ変化の少ないものから順に並べた戻り経路リストを導出する。また、ＲＲＥＰに対しては、戻り経路リストに含まれない経路があって、その経路が差分評価値として有効であれば、その経路を戻り経路リストに含める。
【００８７】
ＲＲＥＰ送信部１７は、戻り経路リストを含む経路応答メッセージを送信する。
【００８８】
本発明によれば、移動ノードに本発明の経路構築方法を実行させる実施形態や、移動ノードに記録させた経路構築プログラムを実行させる実施形態もある。
【００８９】
前述した本発明の種々の実施形態において、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００９０】
【図１】本発明における具体的なシーケンス図である。
【図２】図１に基づいて導出された戻り経路の木構造図である。
【図３】本発明における経路要求メッセージを受信した際のフローチャートである。
【図４】本発明における経路応答メッセージを受信した際のフローチャートである。
【図５】本発明における移動ノードの機能構成図である。
【符号の説明】
【００９１】
１  移動ノード、移動通信装置、
１０  無線通信インタフェース
１１  位置情報測定部
１２  走行速度計測部
１３  メッセージ判定部
１４  差分情報導出部
１５  経路状態テーブル記録部
１６  ＲＲＥＱ送信部
１７  ＲＲＥＰ送信部
１８  戻り経路導出部
【図１】
2005269042.tif 000014
【図２】
2005269042.tif 000015
【図３】
2005269042.tif 000016
【図４】
2005269042.tif 000017
【図５】
2005269042.tif 000018