(57)【要約】【課題】ノードのグループの形成や変更が任意に生じる場合に、少ない制御負荷で移動グループを特定することができる通信装置を提供する。【解決手段】探索用制御メッセージ送信手段７１は、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する。情報抽出手段７２は、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する。移動ノード特定手段７４は、情報抽出手段によって抽出された情報に基づいて、移動グループに属するノードを特定する。【選択図】図１０
2011217012.tif 000002
【特許請求の範囲】
【請求項１】
自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、前記切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信手段と、
他の通信装置から探索用制御メッセージを受信したときに、前記探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する情報抽出手段と、
受信した探索用制御メッセージから抽出された、移動グループに属するノードを特定するための情報を記憶する情報記憶手段と、
受信した各探索用制御メッセージから情報抽出手段によって抽出され、情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定手段とを備える
ことを特徴とする通信装置。
【請求項２】
探索用制御メッセージ送信手段は、移動グループに属するノードを特定するための情報として、自ノードとのリンクが切断された隣接ノードである切断ノードの識別情報と、前記切断ノードを経路上のノードとしていた宛先ノードの識別情報と、前記宛先ノードの隣接ノードリストとを含めた探索用制御メッセージを送信し、
情報抽出手段は、他の通信装置から探索用制御メッセージを受信したときに、前記探索用制御メッセージから、切断ノードの識別情報と、宛先ノードの識別情報と、前記宛先ノードの隣接ノードリストとを抽出し、前記探索用制御メッセージの受信時刻と対応づけて情報記憶手段に記憶させ、
移動ノード特定手段は、受信した探索用制御メッセージ毎に情報記憶手段に記憶された探索用制御メッセージの受信時刻、切断ノードの識別情報、宛先ノードの識別情報、および前記宛先ノードの隣接ノードリストに基づいて、移動グループに属するノードを特定する
請求項１に記載の通信装置。
【請求項３】
移動ノード特定手段は、少なくとも、予め定められた時間幅内に受信時刻が収まっている探索用制御メッセージ群で宛先ノードとされているという条件を満たすノード群を、移動グループに属するノードとして特定する
請求項２に記載の通信装置。
【請求項４】
移動ノード特定手段は、ノード群内のノードのみを経由して、ノード郡内の任意の２つのノードがトポロジーグラフ上で互いに到達可能であるという条件を満たすノード群を、移動グループに属するノードとして特定する
請求項３に記載の通信装置。
【請求項５】
宛先と、前記宛先へのメッセージを受信したときに前記メッセージを次に転送すべき転送先ノードとを対応付けたルーティングテーブルを記憶するルーティングテーブル記憶手段と、
探索用制御メッセージ、および、前記探索用制御メッセージを受信した宛先ノードが送信した応答メッセージに基づいて、ルーティングテーブルにエントリを登録するエントリ登録手段と、
移動ノード特定手段が移動グループに属するノードを特定した場合に、ルーティングテーブル内で、特定された各ノードが宛先となっているエントリの転送先ノードを共通化するルーティングテーブル修正手段とを備える
請求項１から請求項４のうちのいずれか１項に記載の通信装置。
【請求項６】
モバイルアドホックネットワークにおけるノードである請求項１から請求項５のうちのいずれか１項に記載の通信装置。
【請求項７】
メッセージを送受信する通信装置を複数備え、
各通信装置は、
自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、前記切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信手段と、
他の通信装置から探索用制御メッセージを受信したときに、前記探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する情報抽出手段と、
受信した探索用制御メッセージから抽出された、移動グループに属するノードを特定するための情報を記憶する情報記憶手段と、
受信した各探索用制御メッセージから情報抽出手段によって抽出され、情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定手段とを含む
ことを特徴とする通信システム。
【請求項８】
メッセージを送受信する通信装置を複数備える通信システムに適用される通信方法であって、
各通信装置が、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、前記切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信し、
各通信装置が、他の通信装置から探索用制御メッセージを受信したときに、前記探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出し、自ノードの情報記憶手段に記憶させ、
各通信装置が、自ノードの情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する
ことを特徴とする通信方法。
【請求項９】
情報記憶手段を備えるコンピュータに、
自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、前記切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信処理、
他の通信装置から探索用制御メッセージを受信したときに、前記探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出し、前記情報記憶手段に記憶させる情報抽出処理、および、
前記情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定処理
を実行させるための通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置、通信システム、通信方法および通信プログラムに関し、特に、通信経路の変更頻度が多い通信ネットワークに適した通信装置、通信システム、通信方法および通信プログラムに関する。
【背景技術】
【０００２】
近年、３Ｇネットワークや無線ＬＡＮの普及に伴い、エリア拡大等を目的とした無線マルチホップネットワークへの要求が増加している。また、無線ネットワーク特性に応じたルーティング技術が通信品質確保に重要な役割を担っている。
【０００３】
無線ネットワークの特徴として挙げられるのが、通信装置（以下、ノードと記す。）の移動である。ノードの移動態様として様々な態様があるが、一例としてノードのグループ移動が挙げられる。ノードのグループ移動は、一般的なノードの移動態様であり、例えば、人間の集団移動や、軍隊における集団移動等により生じる。
【０００４】
通信機能を持つノードがグループで移動し、複数のノードを介したパケット転送により通信を行う場合において、経路変更に伴う制御負荷が大きくなることが問題になる。特に、アドホックネットワークのルーティングプロトコルとして、制御負荷の軽いリアクティブ型のルーティングプロトコルを用いた場合にその問題が顕著に現れる。
【０００５】
一般的に使われるリアクティブ型のルーティングプロトコルとしてＡＯＤＶ（Ad hoc On-Demand Distance Vector）がある。ＡＯＤＶについは、例えば、非特許文献１に記載されている。このＡＯＤＶを用いた場合の問題点について述べる。なお、以下の説明で、「送信ノード」とは、宛先ノードを定めて、その宛先ノードに対してパケットを送信するノードである。宛先ノードも、「送信ノード」に対する応答としてパケットを送信することがあるが、「宛先ノード」と記し「送信ノード」と区別する。「送信ノード」は、宛先ノードまでの経路が定まっていない場合に、ＲＲＥＱ（Ｒｏｕｔｅ Ｒｅｑｕｅｓｔ）を送信するノードであるということができる。
【０００６】
ＡＯＤＶでは、通信の開始時に送信ノードがＲＲＥＱ（Ｒｏｕｔｅ Ｒｅｑｕｅｓｔ）メッセージを付加した制御パケットをブロードキャスト送信し、宛先ノードへの経路を探索する。ＲＲＥＱメッセージを受信した宛先ノードは、ＲＲＥＰ（Ｒｏｕｔｅ Ｒｅｐｌｙ）メッセージを送信ノードに向けてユニキャスト送信する。そのＲＲＥＰメッセージの転送ノードが、送信ノードと宛先ノードとの間の通信経路として確定される。
【０００７】
ノードの移動や無線リンクロス等に伴って経路が変更される場合にも、ＲＲＥＱメッセージがフラッディングされる。経路切断を検出した途中経路のノードがＲＲＥＱをフラッディングすることにより、経路修復が行われる。また、ある２つのノード間で経路切断が起こり、その２つのノード間のリンクを複数の経路が共有している場合には、その経路の数だけＲＲＥＱメッセージがフラッディングされる。従って、ノードのグループが移動する場合には、グループに属する全ノードの経路が切断され、グループに属する各ノード宛の経路探索のために、ノード数と同じ数だけＲＲＥＱメッセージがフラッディングされる。フラッディングとは、ネットワークを形成するノード全てにパケットを転送することである。ＲＲＥＱメッセージをフラッディングするということは、ＲＲＥＱメッセージが無線帯域を圧迫することを意味する。一般に、無線帯域は有線と比較して、帯域が狭いため制御負荷の増加は深刻な問題となる。
【０００８】
この問題点を解決するために提案されているのが、移動ノードを階層化したルーティングである。非特許文献２には、ＬＡＮＭＡＲと呼ばれる階層化ルーティングが提案されている。これは移動ノードグループに属するノードが代表ノードを介して、グループ外のノードと通信を行うものである。従って、グループ内の全ノードに対する経路探索や修正を行なう必要はなく、グループの代表ノードの探索のみでグループ内の全ノードとの経路確立が可能である。従って、経路変更に伴う制御負荷の減少の効果は、ノード数の増加に伴い顕著になる。また、ＩＥＴＦ（Internet Engineering Task Force ）にて規定されるＮＥＭＯ（Network Mobility）では、モバイルルータを介してグループノードが通信を行う方式が規定されており、そのベース技術は非特許文献３に記載されている。ＮＥＭＯではモバイルルータが代表ノードの役割を行い、ＮＥＭＯ外のノードとモバイルルータ配下のモバイルノードとは、ルータを介して通信を行う。ネットワークの移動に伴う経路変更のメッセージの送受信はモバイルルータのみが行なう。そのため、経路変更時の制御は階層化ルーティングと同様である。従って、各モバイルルータが経路変更手続きを行なう必要がなく、経路変更に伴う制御負荷は削減される。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】C. Perkins, E. Belding-Royer, and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing,” IETF RFC 3562, 2003.
【非特許文献２】G. Pei, M. Gerla and X. Hong, “LANMAR: Landmark Routing for Large Scale Wireless Ad Hoc Networks with Group Mobility”, Proceedings of IEEE/ACM MobiHOC 2000, Boston, MA, Aug. 2000.
【非特許文献３】NEMO IETF RFC 3963，“Network Mobility(NEMO) Basic Support Protocol”，［online］，インターネット＜http://tools.ietf.org/html/rfc3963＞
【発明の概要】
【発明が解決しようとする課題】
【００１０】
前述の階層化ルーティングは、移動ノードグループの構成を事前に把握していることを前提とする。すなわち、人為的な設定により、グループの構成および変更が行なわれることを前提とする。階層化を行なうためにはノードがどのグループに属するかに関する情報を代表ノードやモバイルルータが把握している必要がある。しかし、ノードのグループ構成を事前に知ることが不可能な場合が多い。例えば、人の集団移動や車のグループ移動等の場合、どのノードがグループ移動するかは状況によって変わるため、事前には把握できない。また、事前にグループ構成が把握できたとしても、グループが再構成された場合には対応できない。例えば、同じグループであっても、グループの分割、結合、メンバノードの入れ替わり、新規ノードの参加、離脱が行なわれる場合もあるが、事前に代表ノードを決める方式(LANDMARKルーティングやNEMO)では柔軟に対応することが困難である。
【００１１】
また、階層化ルーティングは経路変更頻度が高いときのみに有効であるが、変更頻度が低いときには、通常のフラットルーティングと比較して制御負荷が高くなる。すなわち、階層化ルーティングでは、階層を維持するための制御メッセージが必要となるため、経路変更頻度が低い場合にはかえって負荷が高くなる。
【００１２】
そこで、本発明は、ノードのグループの形成や変更が任意に生じる場合に、少ない制御負荷で移動グループを特定することができる通信装置、通信システム、通信方法および通信プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明による通信装置は、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信手段と、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する情報抽出手段と、受信した探索用制御メッセージから抽出された、移動グループに属するノードを特定するための情報を記憶する情報記憶手段と、受信した各探索用制御メッセージから情報抽出手段によって抽出され、情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定手段とを備えることを特徴とする。
【００１４】
また、本発明による通信システムは、メッセージを送受信する通信装置を複数備え、各通信装置が、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信手段と、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する情報抽出手段と、受信した探索用制御メッセージから抽出された、移動グループに属するノードを特定するための情報を記憶する情報記憶手段と、受信した各探索用制御メッセージから情報抽出手段によって抽出され、情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定手段とを含むことを特徴とする。
【００１５】
また、本発明による通信方法は、メッセージを送受信する通信装置を複数備える通信システムに適用される通信方法であって、各通信装置が、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信し、各通信装置が、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出し、自ノードの情報記憶手段に記憶させ、各通信装置が、自ノードの情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定することを特徴とする。
【００１６】
また、本発明による通信プログラムは、情報記憶手段を備えるコンピュータに、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報を含む探索用制御メッセージを送信する探索用制御メッセージ送信処理、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出し、情報記憶手段に記憶させる情報抽出処理、および、情報記憶手段に記憶された情報に基づいて、移動グループに属するノードを特定する移動ノード特定処理を実行させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、ノードのグループの形成や変更が任意に生じる場合に、少ない制御負荷で移動グループを特定することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の通信システムの例を示す説明図である。
【図２】本発明の通信装置の構成例を示す説明図である。
【図３】ルーティングテーブルの例を示す説明図である。
【図４】ルーティングテーブルに作成されるエントリの例を示す説明図である。
【図５】情報管理テーブルの例を示す説明図である。
【図６】個々のノードにおける制御メッセージ受信時の処理経過の例を示すフローチャートである。
【図７】個々のノードにおける制御メッセージ受信時の処理経過の例を示すフローチャートである。
【図８】隣接ノードとの経路切断時の処理経過の例を示す説明図である。
【図９】移動グループを形成する移動ノード群を特定する処理経過の例を示すフローチャートである。
【図１０】本発明の通信装置の最小構成の例を示すブロック図である。
【図１１】本発明の通信システムの最小構成の例を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面を参照して説明する。
本発明の通信システムは、パケット転送機能を持つ複数の通信装置（ノード）を含み、グループで移動するノード群（すなわち、ノードのグループ）を特定する。以下の説明では、無線マルチホップネットワークに適用される通信装置を例にして説明するが、他の態様のネットワークに適用されるものであってもよい。例えば、移動するノードが有線で接続された有線ネットワークに本発明が適用されてもよい。
【００２０】
図１は、本発明の通信システムの例を示す説明図である。また、図１では、通信システムに属するノードがグループで移動する状況の一例を示している。図１に示す通信システムは、ノード１〜３、ノードＡ〜Ｉ，およびノードＳを含む。各ノードの構成は同様である。図１に示す例では、ノードＡ〜Ｉ，ノードＳは静止しており、ノード１〜３が、図１における右方向に移動する状況を表している。移動しているノードを移動ノードと記す場合がある。ここでは、ノード１〜３が同じ速度で同じ方向に移動しているものとする。また、ノード１，２，３において、ノード間の距離は一定であるものとする。さらに、各ノードは、どのノードが移動ノードであるかを把握しておらず、移動ノード自身も、自ノードが移動していることを把握していないものとする。
【００２１】
また、本例では、ノード１〜３、ノードＡ〜Ｉ，およびノードＳは、モバイルアドホックネットワークにおけるノードであるものとする。
【００２２】
図１に示すｔは、時刻を示している。時刻ｔ０〜ｔ１の間に、ノード１とノードＡとの距離が増加し、ノード１とノードＢとの距離が短くなっていく。このように、図１では、時間経過に伴うノード１，２，３の移動を表している。また、時刻ｔ０は、ノード１〜３をそれぞれ宛先ノードとしたノードＳが、各ノード１〜３との間で通信経路を確立した時刻である。同様に、時刻ｔ１は、ノード１〜３の移動後に、ノードＳとノード１〜３との間の通信経路が確立した時刻である。
【００２３】
ここでは、ノードＳが、ノード１〜３を宛先とする送信ノードであり、ノード１〜３が宛先ノードである場合を例にして説明する。すなわち、ノードＳが送信ノードとなり、ノード１〜３を宛先ノードとして、経路確立が行われるものとする。そして、確立された経路上のノードを介してパケットが転送される。また、本実施形態では、ルーティングプロトコルとして、ＡＯＤＶを用いる場合を例にして説明する。
【００２４】
移動ノードのグループ外のノードは、自ノード以外の各ノードから受信したＲＲＥＱメッセージから情報を抽出し、抽出した情報に基づいて、以下の３つの条件を満たす２つ以上のノードを、移動グループに属するノードであると判定する。なお、移動グループとは、グループで移動しているノードのグループである。
【００２５】
第１の条件は、経路変更が近接した時刻で発生するノード群であることである。以下、第１の条件を具体的に説明する。各ノードは、Hello メッセージを定期的に送信し、Hello メッセージ送信を継続していたノードからのHello メッセージが途切れると、経路が切断したと判定し、宛先ノードとの経路修復のためのＲＲＥＱメッセージを送信する。グループ移動の場合には、複数のノードが同時に移動するため、それらのノードを宛先とする経路の変更も近いタイミングで生じる。従って、移動グループに属するノードを宛先ノードとして、その宛先ノードとの経路探索のために送信されるＲＲＥＱメッセージも近接した時刻に送信される。従って、第１の条件は、近接した時刻に受信した各ＲＲＥＱメッセージにおいて宛先ノードとされているノード群であるということができる。
【００２６】
第２の条件は、上記のノード群のノードのみを使って接続性を保証できるということである。すなわち、第１の条件を満たすノード群を、移動グループに属するノードの候補とすると、その候補となるノードのみで、接続性を保証できることである。ここで、例えば、ノードＰ，Ｑ，Ｒというノード群があるとする。そのノード群のみで、ノードＰ，Ｑ，Ｒ相互の通信が可能であれば、第２の条件を満たすことになる。第２の条件を満たすか否かは、第２の条件の判定対象となる各ノードの隣接ノードリストに基づいて判定できる。隣接ノードとは、１ホップでパケットを転送できるノードである。
【００２７】
第３の条件は、前述の第１の条件および第２の条件が、一定期間以上継続して満たされていることである。グループ移動は、一時的なものではない。そのため、同じような移動状況が継続していることを確認する必要がある。第３の条件は、この確認のための条件であり、経路変更の時刻相関を有するノード群において、ノード群における通信の接続性を保証できる状態が一定期間継続していることを確認するための条件である。
【００２８】
上記の第１から第３までの各条件を満たすノード群が、移動グループを形成するノード群として判定される。すなわち、第１から第３までの各条件を満たすノード群が移動グループである。
【００２９】
次に、各ノード１〜３、ノードＡ〜Ｉ、及びノードＳの構成（すなわち、本発明の通信装置の構成）について説明する。ここでは、ノードＡを例に説明するが、他の各ノード１〜３，Ｂ〜Ｉ，Ｓに関しても同様である。図２は、ノード（通信装置）Ａの構成例を示すブロック図である。
【００３０】
ノードＡは、通信機能部２０２と、ルーティング機能部２０１とを備える。通信機能部２０２は、全パケットの送受信を行う。ルーティング機能部２０１は、ルーティングテーブルの管理や、移動グループに属する移動ノードの判定等の種々の処理を行う。
【００３１】
ルーティング機能部２０１は、ルーティングテーブル記憶部２０３と、制御メッセージ受信・生成部２０４と、接続状況確認部２０５と、経路変更情報検出部２０６と、グループ判定部２０７とを備える。また、グループ判定部２０７は、経路変更情報記憶部２０９と、判定部２０８とを備え、移動グループに属する移動ノードを判定する。
【００３２】
ルーティングテーブル記憶部２０３は、ルーティングテーブルを記憶する記憶装置である。ルーティングテーブルは、各宛先ノードへの経路上における自ノードの次のホップノードのアドレス等の情報を格納するテーブルである。図３は、ルーティングテーブルの例を示す説明図である。例えば、ルーティングテーブルには、宛先ノードのアドレスと、自ノードの次のホップノードのアドレス（自ノードが次に転送すべきノードのアドレス）とが対応付けて記憶される。このルーティングテーブルにより、宛先ノードが指定されたパケットを受信した場合、通信機能部２０２は、そのパケットを、次に転送すべきノードに転送することができる。
【００３３】
制御メッセージ受信・生成部２０４は、通信機能部２０２が受信したパケットのうち、ルーティングに関わる制御パケットを受け取り、その制御パケットに基づいて、ルーティングテーブルを作成したり、更新したりする。制御メッセージ受信・生成部２０４は、経路確立のために送信ノードから転送されてくるＲＲＥＱメッセージと、そのＲＲＥＱメッセージに対する応答として宛先ノードから転送されてくるＲＲＥＰメッセージとに基づいて、ルーティングテーブルにエントリを作成する。制御メッセージ受信・生成部２０４は、ＲＲＥＰメッセージ受信時に２つのエントリを作成する。
【００３４】
図４は、ルーティングテーブルに作成されるエントリの例を示す説明図である。制御メッセージ受信・生成部２０４は、ＲＲＥＰメッセージ受信時に、そのＲＲＥＰメッセージの送信元アドレスを「宛先ノードのアドレス」とし、そのＲＲＥＰメッセージを転送してきたノードのアドレスを「次のホップノードのアドレス」として、ルーティングテーブルに格納する。なお、ＲＲＥＰメッセージの送信元アドレスの代わりに、ＲＲＥＱメッセージの宛先アドレスを用いてもよい。さらに、制御メッセージ受信・生成部２０４は、ＲＲＥＱメッセージの送信元アドレスを「宛先ノードのアドレス」とし、そのＲＲＥＱメッセージを転送してきたノードのアドレスを「次のホップノードのアドレス」として、ルーティングテーブルに格納する。ＲＲＥＱメッセージの送信元アドレスの代わりに、ＲＲＥＰメッセージの宛先アドレスを用いてもよい。
【００３５】
送信ノードと宛先ノードとの間の各ノードにおいて、このようなエントリが作成されることで、送信ノードと宛先ノードとの間の経路が確立される。
【００３６】
また、制御メッセージ受信・生成部２０４は、Hello メッセージを定期的（例えば、１秒毎）に作成し、通信機能部２０２に送信させる。Hello メッセージは、自ノードとのリンク接続状況を定期的に隣接ノードに確認させるための制御メッセージである。
【００３７】
また、制御メッセージ受信・生成部２０４は、通信機能部２０２が他のノードからHello メッセージを受信した場合、そのHello メッセージを受け取り、どのノードからHello メッセージを受信したのかを、接続状況確認部２０５に通知する。
【００３８】
さらに、制御メッセージ受信・生成部２０４は、接続状況確認部２０５が隣接ノードとのリンクの切断を検出した場合、接続状況確認部２０５からの要求に応じてＲＲＥＱメッセージを作成し、通信機能部２０２に送信せる。このＲＲＥＱメッセージのフラッディングにより、切断した経路における宛先ノードまでの経路検索を開始する。
【００３９】
接続状況確認部２０５は、どのノードからHello メッセージを受信したのかを制御メッセージ受信・生成部２０４から通知されると、そのノードを自ノードの隣接ノードとして認識する。そして、隣接ノードからのHello メッセージの受信が一定期間ない場合（例えば、Hello メッセージを３秒間受信していない場合）には、その隣接ノードとのリンクが切断されたと判定する。この場合、接続状況確認部２０５は、その隣接ノードを次のホップノードとする経路における宛先ノードを指定して、その宛先ノードまでの経路検索のためのＲＲＥＱメッセージを制御メッセージ受信・生成部２０４に作成するように要求する。
【００４０】
経路変更情報検出部２０６は、自ノードがＲＲＥＱメッセージを受信したときに、そのＲＲＥＱメッセージから、移動グループに属するノードを特定するための情報を抽出し、経路変更情報記憶部２０９に記憶させる。
【００４１】
経路変更情報記憶部２０９は、移動グループに属するノードを特定するための情報を記憶する記憶装置である。経路変更情報記憶部２０９は、例えば、後述の情報管理テーブル（図５参照）を記憶する。
【００４２】
判定部２０８は、経路変更情報記憶部２０９に記憶された情報に基づいて、移動グループに属するノード群を特定する。
【００４３】
通信機能部２０２は、ＲＲＥＱメッセージやＲＲＥＰメッセージを受信した場合、制御メッセージ受信・生成部２０４にそのメッセージを渡すとともに、ＲＲＥＱメッセージ、ＲＲＥＰメッセージを他のノードに転送する。また、ＲＲＥＱメッセージおよびＲＲＥＰメッセージは、転送されるごとに１インクリメントされる「ホップカウント」という情報を含む。通信機能部２０２は、ＲＲＥＱメッセージやＲＲＥＰメッセージを転送させる際に、このホップカウントの値を１インクリメントする。また、通信機能部２０２は、Hello メッセージを受信した場合には、制御メッセージ受信・生成部２０４にそのメッセージを渡し、Hello メッセージの転送は行わない。また、通信機能部２０２は、宛先ノードのアドレスが指定されたパケットを受信した場合には、その宛先ノードのアドレスに対応する次ホップノードのアドレスをルーティングテーブルから読み込み、その次ホップノードにパケットを転送する。
【００４４】
通信機能部２０２、制御メッセージ受信・生成部２０４、接続状況確認部２０５、経路変更情報検出部２０６、およびグループ判定部２０７（判定部２０８、経路変更情報記憶部２０９）は、例えば、メモリ等を有するコンピュータのＣＰＵによって実現される。この場合、コンピュータのプログラム記憶装置（図示略）が通信プログラムを記憶し、ＣＰＵがそのプログラムに従って、通信機能部２０２、制御メッセージ受信・生成部２０４、接続状況確認部２０５、経路変更情報検出部２０６、およびグループ判定部２０７として動作すればよい。あるいは、これらの各要素が、それぞれ別々のユニットで実現されていてもよい。
【００４５】
次に、動作について説明する。まず、移動グループに属しているノードが特定されていない状況での動作の概要について、図１を参照して説明する。
【００４６】
図１において、時刻ｔ０より前には、ノードＳ（送信ノード）とノード１〜３（宛先ノード）との間で、経路は確立されていないとする。として、時刻ｔ０の直前に、ノードＳは、ノード１〜３それぞれに対してＲＲＥＱメッセージを作成し、フラッディングすることにより、ノード１〜３毎に宛先ノードを探索する。このように、送信ノードがＲＲＥＱメッセージを送信して経路確立を行うことを経路探索と呼ぶ。経路確立のタイミングは、送信ノードであるノードＳにＲＲＥＰメッセージが届き、送信ノードと宛先ノードとの間で通信可能となった時である。
【００４７】
また、送信ノードは、宛先ノード毎にＲＲＥＱメッセージを送信する。従って、送信ノードから送信されるＲＲＥＱメッセージの数は、宛先ノードの数と同数である。本例では、ノードＳは、ノード１〜３それぞれを宛先とする３つのＲＲＥＱメッセージを送信する。
【００４８】
ＲＲＥＱメッセージは、宛先ノードを指定しているが、ユニキャスト通信とは異なり、経路上のノードのみに受信されるのではなく、無線通信範囲内の各ノードに受信される。そして、転送を繰り返され、宛先ノードに到達する。
【００４９】
また、ＲＲＥＱメッセージを転送する各ノードは、ＲＲＥＱメッセージに含まれるホップカウントの値を１増加させて、転送する。そして、各ノードは、そのホップカウントをＲＲＥＱメッセージの送信元のノードの識別情報とともに記憶する。このホップカウントは、ＲＲＥＱメッセージの送信元のノードから自ノードまでのホップ数を表す。
【００５０】
なお、ＡＯＤＶでは、ホップ数の上限を設定することにより、パケットが転送される範囲を限定することができる。本発明においても、各ノードは、ＲＲＥＱメッセージのホップ数の上限をＲＲＥＱメッセージに定めておき、ＲＲＥＱメッセージの転送範囲を限定してもよい。
【００５１】
宛先ノードの制御メッセージ受信・生成部２０４は、自ノードを宛先とするＲＲＥＱメッセージを受信すると、送信ノードとの間で経路を確立できると判断し、送信ノードにＲＲＥＰメッセージを送信する。例えば、ノード１の制御メッセージ受信・生成部２０４は、自ノード（ノード１）を宛先とするＲＲＥＱメッセージを受信すると、ノードＳとの間で経路を確立できると判断し、ノードＳにＲＲＥＰメッセージを送信する。ノード２，３に関しても同様である。
【００５２】
各宛先ノードから送信されたＲＲＥＰメッセージは、ＲＲＥＱメッセージの転送経路を逆方向に転送され、送信ノードＳに返信される。経路上の各ノードは、ＲＲＥＰメッセージ受信時に、図４に例示するルーティングテーブルのエントリを作成し、そのエントリに従ってＲＲＥＰメッセージを転送していけばよい。また、送信ノードと宛先ノードとの間の経路上の各ノードが、ＲＲＥＰメッセージ受信時に図４に例示する２つのエントリを作成することにより、その送信ノードと宛先ノードとの間で送受信されるパケットを、確立した経路に沿って転送していくことができる。
【００５３】
また、ＲＲＥＰメッセージを転送する各ノードは、ＲＲＥＰメッセージに含まれるホップカウントの値を１増加させて、転送する。そして、各ノードは、そのホップカウントをＲＲＥＰメッセージの送信元のノードの識別情報とともに記憶する。このホップカウントは、ＲＲＥＰメッセージの送信元のノード（すなわち、宛先ノード）から自ノードまでのホップ数を表す。
【００５４】
図１に示す例において、送信ノードＳがノード１〜３からそれぞれＲＲＥＰメッセージを受信した時刻をｔ０とする。
【００５５】
また、送信ノードＳにとって宛先ノードとなるノード１〜３は、ＲＲＥＰメッセージに、自ノードにとって１ホップで接続可能なノードである隣接ノードのリストを追加する。各ノードは、ＲＲＥＰメッセージを受信したときに、そのＲＲＥＰメッセージから、ＲＲＥＰメッセージを送信した宛先ノードの隣接ノードのリストを抽出し、記憶する。また、各ノードは、自ノードから見て、その宛先ノードへの経路上における次のノードとのリンクが切断された場合、その宛先ノードの隣接ノードのリストをＲＲＥＱメッセージに含める。そして、このリストは、前述の第２の条件が満足されているか否かの判定に用いられる。なお、通常、リンクの切断は、前述のように、Hello メッセージの受信が一定期間ないことにより判断される。
【００５６】
ノード１〜３は、同時に同じ速度で図１における右方向に移動する。時刻ｔ０の後、ノード１〜３の移動に伴い、ノード１とノードＡとの距離が次第に大きくなり、その２つのノード間のリンクが切断される。
【００５７】
隣接ノードとのリンクが切断されたことを検知したノードの接続情報確認部２０５は、リンクが切断された隣接ノードが宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードを判定する。接続情報確認部２０５は、リンクが切断された隣接ノードのアドレスが、ルーティングテーブル（図４参照）において、「次のホップノードアドレス」として格納されていたならば、そのアドレスに対応する宛先アドレスを特定すればよい。そして、接続情報確認部２０５は、自ノードからその宛先アドレスまでのホップ数が、予め定められている閾値よりも小さい場合に、その宛先ノードを探索するためのＲＲＥＱメッセージを制御メッセージ受信・生成部２０４に作成させる。制御メッセージ受信・生成部２０４は、接続情報確認部２０５に従いＲＲＥＱメッセージを作成し、通信機能部２０２に送信させる。
【００５８】
各ノードは、リンクが切断された隣接ノードが宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードであって、自ノードからその宛先アドレスまでのホップ数が閾値より小さいという条件を満たす全ての宛先ノードに関して、経路修復を行う。すなわち、そのような条件を満たす全ての宛先ノードに関してＲＲＥＱメッセージを送信する。
【００５９】
図１に示す例では、ノードＡに着目すると、リンクが切断されたノード１が宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードは、ノード１〜３である。また、ノードＡから、ノード１，２，３までホップ数は、いずれも閾値より小さいものとする。この場合、ノードＡは、宛先ノード１，２，３をそれぞれ探索するために、ノード１，２，３毎にＲＲＥＱメッセージを送信する。
【００６０】
ここで、ノードＡは、ＲＲＥＱメッセージに、次の３つの情報を含める。第１の情報は、ノードＡとのリンクが切断された相手側のノード（本例ではノード１）の識別情報である。以下、自ノードとのリンクが切断された相手側のノードを切断ノードと記す。第２の情報は、探索対象となる宛先ノードの識別情報である。第３の情報は、その宛先ノードの各隣接ノードのリストである。この宛先ノードの隣接ノードリストは、その宛先ノードからのＲＲＥＰメッセージに含まれていたリストである。例えば、ノードＡは、ノード３の探索のためのＲＲＥＱメッセージには、「“切断ノード：１”，“宛先ノード：３”、“宛先ノードの隣接ノードリスト：１，２”」という情報を含める。また、例えば、ノードＡは、ノード１の探索のためのＲＲＥＱメッセージには、「“切断ノード：１”，“宛先ノード：１”、“宛先ノードの隣接ノードリスト：２，３”」という情報を含める。
【００６１】
ノードＡが作成した各ＲＲＥＱメッセージは、宛先ノードまで順次転送されていく。このとき、ＲＲＥＱメッセージを転送する各ノードの経路変更情報検出部２０６は、ＲＲＥＱメッセージ受信時に、ＲＲＥＱメッセージから上記の第１から第３までの各情報（すなわち、切断ノードの識別情報、宛先ノードの識別情報、宛先ノードの隣接ノードリスト）を抽出し、ＲＲＥＱメッセージの受信時刻とともに、経路変更情報記憶部２０９に記憶させる。この「ＲＲＥＱメッセージの受信時刻」、「切断ノードの識別情報」、「宛先ノードの識別情報」、「宛先ノードの隣接ノードリスト」は、移動グループに属するノードを特定するための情報である。
【００６２】
図５は、経路変更情報記憶部２０９に記憶される情報（情報管理テーブル）の例を示す説明図である。経路変更情報検出部２０６は、ＲＲＥＱメッセージを受信する毎に、「ＲＲＥＱメッセージの受信時刻」、「切断ノードの識別情報」、「宛先ノードの識別情報」、「宛先ノードの隣接ノードリスト」を対応付けて、図５に例示するように経路変更情報記憶部２０９に記憶させる。この「ＲＲＥＱメッセージの受信時刻」、「切断ノードの識別情報」、「宛先ノードの識別情報」、「宛先ノードの隣接ノードリスト」を含むエントリの集合を、以下、情報管理テーブルと記す。
【００６３】
経路変更情報検出部２０６は、一定の計測時間分の履歴として経路変更情報記憶部２０９に記憶させる。これは、前述の第１の条件および第２の条件が、一定期間以上継続して満たされているという第３の条件に関する判断を行えるようにするためである。
【００６４】
ここでは、切断ノードが宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードであって、自ノードからその宛先アドレスまでのホップ数が閾値より小さいという条件を満たす宛先ノードを探索するためのＲＲＥＱメッセージの送信および転送に関して説明した。また、リンクの切断を検出したノードは、切断ノードが宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードであって、自ノードからその宛先アドレスまでのホップ数が閾値以上となっている宛先ノードに関しては、その宛先ノードまでの経路を無効にするためのエラーメッセージを経路上の全ノードに送信する。このエラーメッセージをＲＥＲＲ（Ｒｏｕｔｅ  Ｅｒｒｏｒ）と記す。ＲＥＲＲを送信したノードや、ＲＥＲＲメッセージを受信したノードは、ルーティングテーブルにおいて、その宛先ノードに関するエントリを無効にする。そして、その後、送信ノードＳが、その宛先ノードを探索するためのＲＲＥＱメッセージを送信する。
【００６５】
また、ノードＡが経路修復のために送信したＲＲＥＱメッセージは、ノードＢを介して、各宛先ノード１，２，３に到達する。このＲＲＥＱメッセージを受信したノード１，２，３は、経路修復を開始したノードＡ（ＲＲＥＱメッセージの送信元）に対して、ＲＲＥＰメッセージを送信する。このとき、各ノード１，２，３は、経路探索の時と同様に、自ノードの隣接ノードリストをＲＲＥＰメッセージに含める。ノード１，２，３は、ＲＲＥＱを自ノードに送ってきたノードに、ＲＲＥＰメッセージを送信し、ＲＲＥＰメッセージを受信した各ノードは、ルーティングテーブルにエントリを作成し、ＲＲＥＰメッセージを転送する。本例では、ノード１が送信したＲＲＥＰメッセージは、ノードＢを介してノードＡに到達する。ノード２，３が送信したＲＲＥＰメッセージは、ノード１，ノードＢを介してノードＡに到達する。そして、この過程で、ＲＲＥＰメッセージを送信した宛先ノード、ＲＲＥＰメッセージを転送したノード、最終的にＲＲＥＰメッセージを受信したノード（ノードＡ）において、それぞれ、宛先ノードに関する新たなエントリがルーティングテーブルに追加される。この結果、経路修復が完了する。
【００６６】
なお、ＲＲＥＱノードを送信したノードまたは転送したノードは、ＲＲＥＱノードを送信・転送後、一定期間内にＲＲＥＰメッセージを受信しなければ、そのＲＲＥＱノードの宛先とした宛先ノードに関する経路上の全ノードに対して、ＲＥＲＲメッセージを送信することによって、経路を無効化する。
【００６７】
以上の動作により、リンクに切断が生じても、経路を修復することができる。また、経路修復の過程で、経路変更情報記憶部２０９には情報管理テーブルが作成される。各ノードは、自ノードの情報管理テーブルを参照して、移動グループに属する移動ノードを特定する。
【００６８】
以下、移動グループに属する移動ノードを特定する動作も含めて、ノードの内部処理の観点から、本発明の動作を詳細に説明する。既に説明したように、各ノードの構成は、共通であり、例えば、図２に示す構成となっている。
【００６９】
図６および図７は、個々のノードにおける制御メッセージ受信時の処理経過の例を示すフローチャートである。個々のノードは、制御メッセージの受信をトリガとして、ステップＦ３０１（図６参照）以降の処理を開始する。あるノードにおいて、通信機能部２０２が、他のノードからの制御メッセージを受信すると（ステップＦ３０１）、通信機能部２０２は、その制御メッセージがＲＲＥＱメッセージであるか否かを判定する（ステップＦ３０２）。そして、受信したメッセージがＲＲＥＱメッセージである場合（ステップＦ３０２におけるＹｅｓ）、通信機能部２０２は、そのＲＲＥＱメッセージを制御メッセージ受信・生成部２０４に渡し、制御メッセージ受信・生成部２０４は、そのＲＲＥＱメッセージが自ノードを宛先ノードとして経路探索するためのＲＲＥＱメッセージであるか否かを判定する（ステップＦ３０３）。
【００７０】
ＲＲＥＱメッセージが自ノードを宛先ノードとして経路探索するためのＲＲＥＱメッセージでないならば（ステップＦ３０３におけるＮｏ）、制御メッセージ受信・生成部２０４は、そのＲＲＥＱメッセージを経路変更情報検出部２０６に渡す。
【００７１】
経路変更情報検出部２０６は、受信したＲＲＥＱメッセージから、切断ノードの識別情報を取得する（ステップＦ３０４）。さらに、経路変更情報検出部２０６は、そのＲＲＥＱメッセージから、宛先ノードの識別情報（すなわち、宛先ノードとして探索の対象としているノードの識別情報）を取得する（ステップＦ３０５）。経路変更情報検出部２０６は、そのＲＲＥＱメッセージの受信時刻に対応付けて、ステップＦ３０４，Ｆ３０５で取得した切断ノードの識別情報および宛先ノードの識別情報を、経路変更情報記憶部２０９における情報管理テーブルに格納する。
【００７２】
さらに、経路変更情報検出部２０６は、受信したＲＲＥＱメッセージから、宛先ノードの隣接ノードリストを取得し（ステップＳ３０７）、ステップＦ３０６で格納したＲＲＥＱメッセージ受信時刻、切断ノードの識別情報および宛先ノードの識別情報に対応付けて、その宛先ノードの隣接ノードリストも情報管理テーブルに格納する（ステップＦ３０８）。この結果、１エントリ分（図５における１行分）のデータが、情報管理テーブル（図５参照）に格納される。
【００７３】
ただし、経路切断後の経路修復のためでなく、あるノードが宛先ノードとの通信を最初に確立するために送信したＲＲＥＱメッセージには、切断ノードの識別情報や、宛先ノードの隣接ノードリストの情報は含まれない。よって、このようなＲＲＥＱメッセージを受信してステップＦ３０４以降の処理を行う場合には、例えば、切断ノードの識別情報や、宛先ノードの隣接ノードリストの情報を「なし」として、情報管理テーブルに格納すればよい。
【００７４】
ステップＦ３０８の後、通信機能部２０２は、受信したＲＲＥＱメッセージのホップカウントの値を１増加させ、ＲＲＥＱメッセージを転送する（ステップＦ３０８ａ）。また、通信機能部２０２は、そのホップカウントの値を、ＲＲＥＱメッセージ送信元から自ノードまでのホップ数として記憶する。
【００７５】
リンク切断に伴って送信されたＲＲＥＱメッセージを受信した場合を例にして、ステップＦ３０４以降の処理の具体例を示す。例えば、図１における時刻ｔ０後に、ノードＡとノード１とのリンク切断が生じたとする。この場合、ノードＡは、切断ノード１が宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノードとして、ノード１，２，３があるということをルーティングテーブルから判定する。そして、ノードＡが、ノード１，２，３を探索するためのＲＲＥＱメッセージをそれぞれ送信する。ノードＡは、ノード１を探索するためのＲＲＥＱメッセージとして、「“切断ノード：１”，“宛先ノード：１”，“宛先ノードの隣接ノードリスト：２，３”」という情報を含むＲＲＥＱメッセージを送信する。このＲＲＥＱメッセージを受信したノード（ノードＢ〜Ｉ）は、ステップＦ３０４〜Ｆ３０８の処理によって、例えば、図５に示すエントリ４１を情報管理テーブルに格納する。同様に、ノード２を探索するためのＲＲＥＱメッセージや、ノード３を探索するためのＲＲＥＱメッセージを受信したときにも、各ノードは、ステップＦ３０４〜Ｆ３０８の処理によって、例えば、図５に示すエントリ４２やエントリ４３を記憶する。また、ノードＡは、３種類のＲＲＥＱメッセージを近接したタイミングで送信するので、各ノードにおけるこれら３種類のＲＲＥＱメッセージの受信時刻も近接している。
【００７６】
また、例えば、図１における時刻ｔ１後に、ノードＢとノード１とのリンク切断が生じた場合にも、ノードＢは、上記のノードＡと同様に、ノード１，２，３を探索するための３種類のＲＲＥＱメッセージをそれぞれ送信する。各ノードは、これらのＲＲＥＱメッセージを受信する毎に、ステップＦ３０４〜Ｆ３０８の処理によって、例えば、図５に示すエントリ４４，４５，４６をそれぞれ情報管理テーブルに格納する。
【００７７】
情報管理テーブルには、「ＲＲＥＱメッセージの受信時刻」、「切断ノードの識別情報」、「宛先ノードの識別情報」および「宛先ノードの隣接ノードリスト」を含むエントリ（図５に示す１行分のデータ）が、ＲＲＥＱメッセージ受信毎に、履歴として格納されていく。切断ノードは、ＲＲＥＱメッセージの送信元ノードの隣接ノードであって、そのＲＲＥＱメッセージの送信元ノードとのリンクが切断されたノードである。宛先ノードは、ＲＲＥＱメッセージの送信元ノードから見て、切断ノードを経路としていた宛先ノードである。
【００７８】
なお、経路変更情報検出部２０６は、情報管理テーブルに格納した情報を、予め定められた期間以上、情報管理テーブル内で保持する。既に説明したように、これは、第３の条件に関する判断を行えるようにするためである。
【００７９】
次に、受信したＲＲＥＱメッセージが自ノードを宛先ノードとして経路探索するためのＲＲＥＱメッセージであった場合（ステップＳ３０３におけるＹｅｓ）の動作について説明する。この場合、制御メッセージ受信・生成部２０４は、ＲＲＥＱメッセージの送信元宛のＲＲＥＰメッセージを作成し、そのＲＲＥＰメッセージに、自ノードの隣接ノードリストを含める（ステップＦ３０９）。なお、自ノードが他のノードからHello メッセージを受信したときに、接続状況確認部２０５が、そのHello メッセージの送信元ノードを、自ノードの隣接ノードとして認識する（後述のステップＦ３１８，Ｆ３１９参照）。制御メッセージ受信・生成部２０４は、このようにしてHello メッセージの受信により認識した隣接ノードのリストをＲＲＥＰメッセージに含める。
【００８０】
次に、制御メッセージ受信・生成部２０４は、ステップＦ３０９で作成したＲＲＥＰメッセージを、通信機能部２０２に送信させる（ステップＦ３１０）。
【００８１】
このとき、ＲＲＥＰメッセージは、ＲＲＥＱメッセージが宛先ノードまで転送された経路とは逆の経路を辿り、ＲＲＥＱメッセージの送信元ノードまでユニキャスト送信される。例えば、図１に示す例において、送信ノードＳがノード３宛に送信したＲＲＥＱメッセージに対する応答として、ノード３が送信するＲＲＥＰメッセージは、ノード１，Ａ，Ｄ，Ｈ，Ｓの順に転送され、ノードＳに到達し、それら以外のノードには到達しない。また、例えば、ノードＡがノード１とのリンク切断後に、ノード１を探索するために送信したＲＲＥＱメッセージは、ノードＢ〜Ｉに送信されるが、ノード１へは、ノードＢ，１という順に転送される。従って、ノード１がノードＡ宛に送信したＲＲＥＰメッセージは、ノードＢ，Ａの順に転送され、ノードＡに到達する。
【００８２】
次に、受信した制御メッセージがＲＲＥＱメッセージ以外のメッセージであった場合の動作について説明する。通信機能部２０２は、受信した制御メッセージがＲＲＥＱメッセージでないと判定した場合（ステップＦ３０２におけるＮｏ）、その制御メッセージがＲＲＥＰメッセージであるか否かを判定する（ステップＦ３１１）。受信した制御メッセージがＲＲＥＰメッセージである場合（ステップＦ３１１におけるＹｅｓ）、通信機能部２０２は、そのＲＲＥＰメッセージを制御メッセージ受信・生成部２０４に渡す。そして、制御メッセージ受信・生成部２０４は、そのＲＲＥＰメッセージから隣接ノードリストを取り出し、自ノード内に保持しておく（ステップＦ３１２）。例えば、ＲＲＥＰメッセージから隣接ノードリストを取り出し、自ノード内の記憶装置（図示せず。）に記憶させておけばよい。また、この隣接ノードリストは、ＲＲＥＰメッセージの送信元のノードの隣接ノードのリストであり、ＲＲＥＰメッセージの送信元のノードにおけるステップＦ３０９の処理で、ＲＲＥＰメッセージに追加されたものである。
【００８３】
なお、制御メッセージ受信・生成部２０４は、ＲＲＥＰメッセージを受け取ると、そのＲＲＥＰメッセージと、そのＲＲＥＰメッセージに対応するＲＲＥＱメッセージに基づいて、ルーティングテーブルのエントリ（図４参照）を作成し、ルーティングテーブルに格納する。
【００８４】
続いて、通信機能部２０２は、受信したＲＲＥＰメッセージのホップカウントの値を１増加させ、ＲＲＥＰメッセージを転送する（ステップＦ３１３）。また、通信機能部２０２は、そのホップカウントの値を、ＲＲＥＰメッセージ送信元（すなわち宛先ノード）から自ノードまでのホップ数として記憶する。
【００８５】
ただし、自ノードが、ＲＲＥＰメッセージの宛先に該当する場合、ＲＲＥＰメッセージの転送は行わない。
【００８６】
例えば、送信ノードＳからのＲＲＥＱメッセージに対して、ノード１がＲＲＥＰメッセージを返した場合、その経路上のノードＡ，Ｄ，Ｈ，Ｓが上記のステップＦ３１２の処理を行い、ノード１の隣接ノードリストを保持する。
【００８７】
通信機能部２０２は、受信した制御メッセージがＲＲＥＰメッセージでないと判定した場合（ステップＦ３１１におけるＮｏ）、その制御メッセージがHello メッセージであるか否かを判定する（ステップＦ３１８）。受信した制御メッセージがHello メッセージである場合（ステップＦ３１８におけるＹｅｓ）、通信機能部２０２は、そのHello メッセージを制御メッセージ受信・生成部２０４に渡す。制御メッセージ受信・生成部２０４は、そのHello メッセージに基づいて、どのノードからHello メッセージを受信したのかを、接続状況確認部２０５を通知し、接続状況確認部２０５は、Hello メッセージの送信元のノードの識別情報を、自ノードの隣接ノードの識別情報として、隣接ノードリストに追加する（ステップＦ３１９）。新たに隣接ノードが出現し、その隣接ノードからのHello メッセージを受信したときには、このステップＦ３１９の処理によって、その新たな隣接ノードが隣接ノードリストに追加される。
【００８８】
このように作成された隣接ノードリストは、自ノードがＲＲＥＰメッセージを送信する際に、ステップＦ３０９の処理でＲＲＥＰメッセージに含められる。
【００８９】
また、受信した制御メッセージがHello メッセージでないと判定した場合（ステップＦ３１８におけるＮｏ）、通信機能部２０２は、その制御メッセージがＲＥＲＲメッセージであるか否かを判定する（ステップＦ３２０）。受信した制御メッセージがＲＥＲＲメッセージである場合（ステップＦ３２０におけるＹｅｓ）、通信機能部２０２は、そのＲＥＲＲメッセージを制御メッセージ受信・生成部２０４に渡す。制御メッセージ受信・生成部２０４は、ルーティングテーブルにおいて、そのＲＥＲＲメッセージで指定されている宛先ノードに関するエントリを無効にする（ステップＦ３２１）。例えば、ルーティングテーブルからそのエントリを削除する。また、受信した制御メッセージがＲＥＲＲメッセージでない場合（ステップＦ３２０におけるＮｏ）、通信機能部２０２は、受信した制御メッセージに関する処理を終了する。
【００９０】
次に、隣接ノードとの経路切断時の処理について説明する。図８は、隣接ノードとの経路切断時の処理経過の例を示す説明図である。接続状況確認部２０５は、隣接ノードリストに含めた各隣接ノードからのHello メッセージの受信状況を監視する。すなわち、隣接ノードリストに含めた各隣接ノードに関して、Hello メッセージを受信したという通知を定期的に制御メッセージ受信・生成部２０４から受けているか否かを判定する。そして、接続状況確認部２０５は、その判定結果に基づいて、隣接ノードのリンクが切断されたか否かを判定する（ステップＦ３５１）。リンクの切断を検出しなければ、同様の監視（ステップＦ３５１）を継続する。
【００９１】
また、隣接ノードからのHello メッセージが一定期間以上受信していないことに基づいて、接続状況確認部２０５が隣接ノードとのリンクが切断されたと判定した場合（ステップＳ３５１におけるＹｅｓ）、接続状況確認部２０５は、その隣接ノードを次のホップノードとする経路における各宛先ノードをルーティングテーブルに基づいて判定し、その宛先ノードを指定して、その宛先ノードまでの経路検索のためのＲＲＥＱメッセージを制御メッセージ受信・生成部２０４に作成するように要求する。
【００９２】
すると、メッセージ受信・生成部２０４は、接続状況確認部２０５に指定された宛先ノードを探索するためのＲＲＥＱメッセージを作成し、そのＲＲＥＱメッセージに、その宛先ノードの隣接ノードリストを含める（ステップＦ３５２）。宛先ノードの隣接ノードリストは、その宛先ノードからのＲＲＥＰメッセージ受信時にステップＦ３１２で保持しておいたリストである。
【００９３】
次に、メッセージ受信・生成部２０４は、そのＲＲＥＱメッセージに、切断ノードリストの識別情報を含める（ステップＦ３５３）。この切断ノードリストは、リンクが切断されたと接続状況確認部２０５に判定された隣接ノードである。
【００９４】
次に、メッセージ受信・生成部２０４は、そのＲＲＥＱメッセージに、宛先ノードの識別情報を含める（ステップＦ３５４）。
【００９５】
そして、通信機能部２０２は、そのＲＲＥＱメッセージを周辺のノードにフラッディングする（ステップＦ３５５）。
【００９６】
なお、このＲＲＥＱメッセージを受信した各ノードは、前述のステップＦ３０４〜Ｆ３０８の処理を行い、情報管理テーブル（図５参照）を更新する。
【００９７】
次に、各ノードが、移動グループを形成する移動ノード群を特定する処理について説明する。図９は、移動グループを形成する移動ノード群を特定する処理経過の例を示すフローチャートである。
【００９８】
各ノードの判定部２０８は、移動グループを形成する移動ノード群を測定（特定）する周期が経過したか否かを判定する（ステップＦ４０１）。このように、測定周期の経過を待つのは、前述の第３の条件を満たしているかを確認することに対応しており、グループの状態が一定期間継続していることを確認するためである。
【００９９】
判定部２０８は、測定周期が経過していなければ、測定周期が経過するまで待機する。
【０１００】
測定周期が経過したならば（ステップＦ４０１におけるＹｅｓ）、判定部２０８は、経路変更情報記憶部２０９に記憶された情報管理テーブルを参照して、経路変動タイミングが近接したノードを抽出する（ステップＦ４０２）。具体的には、図５に例示する情報管理テーブルにおいて、ＲＲＥＱメッセージ受信時刻が、予め定められた時間幅内に収まっているＲＲＥＱメッセージにおいて、宛先ノードとされたノード群を抽出する。例えば、予め定められた時間幅が０．１秒であるとする。すると、図５に示す例では、エントリ４１〜４３における受信時刻は、０．１秒の時間幅に収まっている。よって、判定部２０８は、エントリ４１〜４３の受信時刻に受信されたＲＲＥＱメッセージにおいて宛先ノードとなっていた宛先ノード１，２，３を抽出する。判定部２０８は、エントリ４４，４５，４６からも同様に宛先ノード１，２，３を抽出する。
【０１０１】
判定部２０８は、ステップＦ４０２においてノード群を抽出できなかった場合（ステップＦ４０２におけるＮｏ）、処理を終了する。また、ステップＦ４０２においてノード群を抽出できた場合にはステップＦ４０４に移行する。
【０１０２】
ステップＦ４０４において、判定部２０８は、ステップＦ４０２で抽出したノード群のみで、そのノード群の各ノード同士の接続性を保証できるか否かを判定する（ステップＦ４０４）。具体的には、判定部２０８は、ステップＦ４０２で抽出した各宛先ノードの隣接ノードリストを情報管理テーブルから抽出し、各宛先ノードと、その隣接ノードリストとに基づいて、ステップＦ４０２で抽出したノードの接続トポロジー（グラフ）を作成する。そして、ステップＦ４０２で抽出したノード群におけるいかなる任意の２ノードにおいても、その抽出したノード群のみを経由して互いに到達可能であるならば、ステップＦ４０２で抽出したノード群のみで、そのノード群の各ノード同士の接続性を保証できると判定する。一方、接続トポロジーにおいて、互いに到達可能とならないノードの組が存在するならば、接続性を保証できないと判定する。
【０１０３】
判定部２０８は、ステップＦ４０４で、ノード群内のみにおけるノード間の接続性を保証できないと判定した場合（ステップＦ４０５におけるＮｏ）、処理を終了する。また、ステップＦ４０２で抽出したノード群内のみにおけるノード間の接続性を保証できると判定した場合、そのステップＦ４０２で抽出したノード群を、移動グループを形成する移動ノード群として定める（ステップＦ４０６）。
【０１０４】
なお、ステップＦ４０２で、情報管理テーブルから、ＲＲＥＱメッセージの受信時刻の時間帯がずれたエントリ群から、それぞれ同じ宛先ノード群が複数回抽出され、その同じノード群に関して、それぞれ、ノード群内のみにおけるノード間の接続性を保証されると判定された場合には、第１の条件および第２の条件が継続していると判定し（すなわち、第３の条件が満たされていると判定し）、その宛先ノード群を、移動グループを形成する移動ノード群として決定してもよい。
【０１０５】
測定周期毎に、ステップＦ４０１移行の処理を行い、所定回数以上の測定（ステップＦ４０１〜Ｆ４０６）において、ステップＦ４０６で同一のノード群が連続して特定された場合に、そのノード群を、移動グループを形成する移動ノード群として決定してもよい。
【０１０６】
次に、グループ決定後の経路修復の動作について説明する。各ノードは、隣接ノードとのリンクが切断され、その隣接ノードが宛先ノードまでの経路における次のノードとなっているという条件を満たす宛先ノード群が、グループを形成するノード群であると判定した場合、以下のように動作すればよい。
【０１０７】
例えば、接続状況確認部２０５は、そのグループを形成するノード群の中から、そのノード群のいずれのノードへの経路においても存在するノードを特定する。例えば、図１に示す例では、ノード１，２，３のノード群のうち、ノード１は、ノード２への経路上にも、ノード３への経路上にも存在する。接続状況確認部２０５は、このようなノードを特定すればよい。また、接続状況確認部２０５は、情報管理テーブルにおいて、移動グループを形成する各宛先ノードに共通の切断ノードとして格納されているノードを、上記のようなノード（ノード群のいずれのノードへの経路においても存在するノード）として特定すればよい。
【０１０８】
そして、接続状況確認部２０５は、その特定したノードを探索するためのＲＲＥＱメッセージを制御メッセージ受信・生成部２０４に作成させ、通信機能部２０２から送信させる。グループ内の他のノードに関しては、ＲＲＥＱメッセージを作成させなくてもよい。
【０１０９】
このＲＲＥＱメッセージを宛先ノードに転送する動作は、既に説明した動作と同様である。また、ＲＲＥＱメッセージの宛先ノードは、ＲＲＥＱメッセージを受信するとＲＲＥＰメッセージを返す。この動作も、既に説明した動作と同様である。
【０１１０】
ＲＲＥＰメッセージを転送・受信する各ノードの制御メッセージ受信・生成部２０４は、ＲＲＥＰメッセージの受信に合わせて、ルーティングテーブルを更新する。このとき、制御メッセージ受信・生成部２０４は、ＲＲＥＰメッセージの送信元に関するエントリは、既に説明した動作と同様に、更新する。ただし、ＲＲＥＰメッセージの送信元のノードと同じ移動グループに属する各ノードに関して、それらの各ノードを「宛先ノード」とし、その「宛先ノード」に対応する「次のホップノードのアドレス（図４参照）」を、ＲＲＥＰメッセージの送信元に対応する「次のホップノードのアドレス」と共通化する。
【０１１１】
例えば、図１に示す例において、移動グループを特定したことにより、ノードＣにとって、ノード１とのリンクがノード２，３宛の経路上のリンクであること、および、ノード１〜３が移動グループを形成していることが既知となったとする。この場合、ノードＣは、ノード１との経路が修復できれば、ノード１がノード２，３にパケットを転送可能で、ノードＣとノード２，３との接続性も確保できる。この場合、ノードＣは、ノード１との経路修復を開始し、宛先をノード１としたＲＲＥＱメッセージをフラッディングする。また、ノード１からＲＲＥＰメッセージを受信したノードＣは、ノード１のアドレスを「宛先ノードのアドレス」とし、そのＲＲＥＰメッセージを転送してきたノードのアドレスを「次のホップノードのアドレス」としてルーティングテーブルに登録する。また、ノード２，３に関しても、ルーティングテーブルにおける「次のホップノードのアドレス」を、ノード１と共通化する。
【０１１２】
本発明によれば、隣接ノードとのリンク切断を検知したノードが、その隣接ノードを経路としていた宛先ノードの探索を、ＲＲＥＱメッセージを送信することによって行う。その際、経路切断を検知したノードは、切断ノード、宛先ノード、およびその宛先ノードの隣接ノードをＲＲＥＱメッセージに含める。また、リンク切断を検知したノードは、その隣接ノードを経路としていた宛先ノード毎に、近接したタイミングで各ＲＲＥＱメッセージを送信する。その結果、リンク切断を検知したノードと、宛先ノードとの間で、ＲＲＥＱメッセージおよびＲＲＥＰメッセージの授受が行われ、新たな経路確立が可能となる。このとき、ＲＲＥＱを受信した各ノードは、ＲＲＥＱの受信時刻や、宛先ノード毎に送信したＲＲＥＱに含まれている各情報に基づいて、移動グループを特定することができる。また、このように、自動的に移動グループを特定することができるので、移動グループに属するノードが変更（例えば、新たなノードの参加、あるいは、ノードの離脱）したとしても、移動グループを特定することができる。
【０１１３】
また、グループ特定に要する制御メッセージとしては、ＡＯＤＶにおけるＲＲＥＱメッセージやＲＲＥＰメッセージ（あるいはそれらに相当するメッセージ）を用いればよく、新たな種類の制御メッセージを用意する必要がない。そのため、少ない制御負荷で移動グループを特定することができる。
【０１１４】
また、移動グループを特定した後においては、移動グループに属する各ノードへの経路上のリンクを検出したノードは、その移動グループに属する１つのノードに関してＲＲＥＱメッセージを送信して経路修復、経路探索を行うことで、その移動グループ内の全ノードとの経路確立が可能となる。従って、この場合、ＲＲＥＱメッセージのフラッディングは１回で済む。よって、制御負荷を大幅に削減することができる。移動グループに属するノード数が多いほど、この効果は大きくなる。
【０１１５】
なお、以上の説明では、移動グループに属する各ノード（図１におけるノード１〜３）のグループ内での位置関係が変わらない場合を例にして説明したが、移動グループに属する各ノードのグループ内での位置関係が変化する場合であっても、本発明に適用可能である。
【０１１６】
また、上記の説明では、無線アドホックネットワークのdistance vector 型のＡＯＤＶをベースにしたルーティングプロトコルを用いる場合を例にして説明したが、ルーティング態様は、上記の例に限定されない。例えば、link state型のＯＬＳＲ（Optimized Link State Routing）、有線ネットワークで用いられるルーティングなど、各ノードを対等として扱うフラットルーティングであれば、本発明に適用可能である。
【０１１７】
また、上記の説明では、移動の例として、グループ移動を例に説明したが、時間に相関のある障害で経路変更が発生するノード群で、各ノードのみで接続性が確保される場合であれば、グループ移動に限らない。例えば、局所領域内のランダム移動ノードの場合等である。
【０１１８】
次に、本発明の最小構成について説明する。図１０は、本発明の通信装置の最小構成の例を示すブロック図である。図１１は、本発明の通信システムの最小構成の例を示すブロック図である。
【０１１９】
本発明の通信システムは、メッセージを送受信する通信装置８１を複数備える（図１１参照）。
【０１２０】
そして、各通信装置８１は、探索用制御メッセージ送信手段７１と、情報抽出手段７２と、情報記憶手段７３と、移動ノード特定手段７４とを備える（図１０、図１１参照）。
【０１２１】
探索用制御メッセージ送信手段７１（例えば、接続状況確認部２０５、制御メッセージ受信・生成部２０４および通信機能部２０２によって実現される。）は、自ノードとのリンクが切断された隣接ノードである切断ノードを検出したときに、その切断ノードを経路上のノードとしていた宛先ノード毎に、宛先ノードを探索する探索用制御メッセージであって、移動グループに属するノードを特定するための情報（例えば、切断ノードの識別情報、宛先ノードの識別情報および宛先ノードの隣接ノードリスト）を含む探索用制御メッセージ（例えば、ＲＲＥＱメッセージ）を送信する。
【０１２２】
情報抽出手段７２（例えば、経路変更情報検出部２０６によって実現される。）は、他の通信装置から探索用制御メッセージを受信したときに、その探索用制御メッセージから、移動グループに属するノードを特定するための情報を抽出する。
【０１２３】
情報記憶手段７３（例えば、経路変更情報記憶部２０９によって実現される。）は、受信した探索用制御メッセージから抽出された、移動グループに属するノードを特定するための情報を記憶する。
【０１２４】
移動ノード特定手段７４（例えば、判定部２０８によって実現される。）は、受信した各探索用制御メッセージから情報抽出手段によって抽出され、情報記憶手段７３に記憶された情報に基づいて、移動グループに属するノードを特定する。
【０１２５】
そのような構成によれば、宛先ノードを探索する探索用制御メッセージとは別に制御メッセージを用いることなく、移動グループに属するノードを特定することができるので、少ない制御負荷で移動グループを特定することができる。
【０１２６】
また、探索用制御メッセージ送信手段７１が、移動グループに属するノードを特定するための情報として、自ノードとのリンクが切断された隣接ノードである切断ノードの識別情報と、その切断ノードを経路上のノードとしていた宛先ノードの識別情報と、宛先ノードの隣接ノードリストとを含めた探索用制御メッセージを送信し、情報抽出手段７２が、他の通信装置から探索用制御メッセージを受信したときに、探索用制御メッセージから、切断ノードの識別情報と、宛先ノードの識別情報と、宛先ノードの隣接ノードリストとを抽出し、その探索用制御メッセージの受信時刻と対応づけて情報記憶手段７３に記憶させ、移動ノード特定手段７４が、受信した探索用制御メッセージ毎に情報記憶手段７３に記憶された探索用制御メッセージの受信時刻、切断ノードの識別情報、宛先ノードの識別情報、および宛先ノードの隣接ノードリストに基づいて、移動グループに属するノードを特定する構成であってもよい。
【０１２７】
また、移動ノード特定手段７４が、少なくとも、予め定められた時間幅内に受信時刻が収まっている探索用制御メッセージ群で宛先ノードとされているという条件を満たすノード群を、移動グループに属するノードとして特定する構成であってもよい。
【０１２８】
また、移動ノード特定手段７４が、ノード群内のノードのみを経由して、ノード郡内の任意の２ノードがトポロジーグラフ上で互いに到達可能であるという条件を満たすノード群を、移動グループに属するノードとして特定する構成であってもよい。
【０１２９】
また、宛先と、その宛先へのメッセージを受信したときにそのメッセージを次に転送すべき転送先ノードとを対応付けたルーティングテーブルを記憶するルーティングテーブル記憶手段（例えば、ルーティングテーブル記憶部２０３）と、探索用制御メッセージ、および、探索用制御メッセージを受信した宛先ノードが送信した応答メッセージ（例えば、ＲＲＥＰメッセージ）に基づいて、ルーティングテーブルにエントリを登録するエントリ登録手段（例えば、制御メッセージ受信・生成部２０４）と、移動ノード特定手段７４が移動グループに属するノードを特定した場合に、ルーティングテーブル内で、特定された各ノードが宛先となっているエントリの転送先ノードを共通化するルーティングテーブル修正手段（例えば、制御メッセージ受信・生成部２０４）とを備える構成であってもよい。
【０１３０】
また、通信装置は、モバイルアドホックネットワークにおけるノードであってもよい。
【産業上の利用可能性】
【０１３１】
本発明は、通信経路の変更頻度が多い通信ネットワークに適用される通信システムに好適に利用される。
【符号の説明】
【０１３２】
１〜３，Ａ〜Ｉ，Ｓ  ノード（通信装置）
２０１  ルーティング機能部
２０２  通信機能部
２０３  ルーティングテーブル記憶部
２０４  制御メッセージ受信・生成部
２０５  接続状況確認部
２０６  経路変更情報検出部
２０７  グループ判定部
２０８  判定部
２０９  経路変更情報記憶部
【図１】
2011217012.tif 000003
【図２】
2011217012.tif 000004
【図３】
2011217012.tif 000005
【図４】
2011217012.tif 000006
【図５】
2011217012.tif 000007
【図６】
2011217012.tif 000008
【図７】
2011217012.tif 000009
【図８】
2011217012.tif 000010
【図９】
2011217012.tif 000011
【図１０】
2011217012.tif 000012
【図１１】
2011217012.tif 000013