(57)【要約】  ネットワーク内にメッセージを行き渡らせる際に、片方向リンクも利用して、効率的なメッセージ転送を実現することができる通信装置を提供する。リンク検出手段７２は、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出する。第２メッセージ送信手段７３は、片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する。転送ノード選択手段７４は、双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する。
2011118133.tif 000002
【特許請求の範囲】
【請求項１】
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信手段と、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出手段と、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信手段と、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択手段とを備える
ことを特徴とする通信装置。
【請求項２】
リンク検出手段は、自ノードが隣接ノードとして記述されていない第１のメッセージの受信回数に基づいて、第１のメッセージを送信してくる他のノードと自ノードとの間のリンクが片方向リンクであると判定する
請求項１に記載の通信装置。
【請求項３】
第２メッセージ送信手段は、片方向隣接ノードまでのホップ数に応じて、第２のメッセージの送信を抑制する
請求項１または請求項２に記載の通信装置。
【請求項４】
第２メッセージ送信手段は、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制する
請求項１から請求項３のうちのいずれか１項に記載の通信装置。
【請求項５】
片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在する場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める自律的転送ノード判定手段を備える
請求項１から請求項４のうちのいずれか１項に記載の通信装置。
【請求項６】
自律的転送ノード判定手段は、
共通の片方向隣接ノードに関して、前記片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在するという条件を満たす複数の通信装置が存在する場合、自ノードの識別情報が、前記複数の通信装置の識別情報の中で所定の条件を満たしている場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める
請求項５に記載の通信装置。
【請求項７】
メッセージを無線で送受信する通信装置を複数備え、
各通信装置は、
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信手段と、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出手段と、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信手段と、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択手段とを含む
ことを特徴とする通信システム。
【請求項８】
メッセージを無線で送受信する通信装置を複数備える通信システムに適用される通信方法であって、
各通信装置が、自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信し、
各通信装置が、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出し、
各通信装置が、片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信し、
各通信装置が、双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する
ことを特徴とする通信方法。
【請求項９】
コンピュータに、
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信処理、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出処理、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信処理、および、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択処理
を実行させるための通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置、通信システム、通信方法および通信プログラムに関し、特に、無線マルチホップネットワークに適用される通信装置、通信システム、通信方法、通信プログラムに関する。
【背景技術】
【０００２】
無線マルチホップネットワークにおけるユニキャスト経路制御の例が、非特許文献１に記載されている。具体的には、非特許文献１には、ＯＬＳＲ（Optimized Link State Routing）について記載されている。ＯＬＳＲが適用される通信システムは、制御メッセージやデータパケットを送受信する複数の無線通信装置を備える。以下、この無線通信装置をノードと記す。ＯＬＳＲでは、各ノードは、起動後に、予め定められた送信間隔でHello メッセージを送信する。そして、Hello メッセージの送信元のノードからの無線到達範囲内に存在するノードのみが、そのHello メッセージを受信する。Hello メッセージを受信したノードは、Hello メッセージの転送を行わない。【０００３】
また、各ノードは、自ノードの隣接ノードの情報（ＩＰアドレス等）を記録する隣接ノードテーブルを保持し、Hello メッセージ送信時には、隣接ノードテーブルに記録されている全ての隣接ノードのＩＰアドレス等をHello メッセージに含めて、Hello メッセージを送信する。また、他のノードからHello メッセージを受信したノードは、そのHello メッセージの送信元のノードの情報（ＩＰアドレス等）を隣接ノードテーブルに記憶する。ただし、個々のHello メッセージに関する情報を隣接ノードテーブルに記憶しておく期間（有効期間）は予め定められており、自ノードの隣接ノードの情報は、その有効期間が経過するまでの間、隣接ノードテーブルに記憶される。【０００４】
そして、各ノードは、隣接ノードから受信したHello メッセージに、自ノードのＩＰアドレスが含まれている場合、その隣接ノードとの間で双方向で通信可能であると判断する。さらに、隣接ノードからHello メッセージを受信したノードは、双方向で通信可能な隣接ノードの中からＭＰＲ（Multipoint Reply）ノードを選択する。ＭＰＲノードは、ノード毎に定められる。あるノードＮに関するＭＰＲノードは、ネットワーク内の全ノードに通知すべき制御メッセージをノードＮが送信した場合に、その制御メッセージをネットワーク内の全ノードが受信できるように転送するノードである。換言すれば、ＭＰＲノードは、ノードＮが送信した制御メッセージを、ネットワークにブロードキャスト（またはマルチキャスト）するための転送ノードである。なお、ネットワーク内の全ノードに通知すべき制御メッセージの例としては、ＴＣ（Topology Control）メッセージ等の経路制御メッセージが挙げられる。ＴＣメッセージは、自ノードの持つリンク（通常は、自ノードをＭＰＲノードに選択した隣接ノードとのリンク）の情報を、ネットワーク内の全ノードに通知するための制御メッセージである。以下、ＴＣメッセージを例にして説明する。【０００５】
あるノードに着目した場合に、そのノードのＭＰＲノードを具体的に定義すると、ＭＰＲノードとは、着目しているノード（以下、着目ノードと記す）の２ホップ先の全てのノードに対して制御メッセージ（ネットワーク内の全ノードに通知すべき制御メッセージ）を転送することができる着目ノードの隣接ノードの集合に属するノードである。図１３は、ＭＰＲノードの例を示す説明図である。ここでは、図１３に示すノード１００に着目し、ノード１００のＭＰＲノードを例にして説明する。図１３において、ノード１１１〜１１４は、ノード１００の１ホップ先のノードである。また、ノード１２１〜１２６は、ノード１００の２ホップ先のノードである。本例では、ノード１１１は、ノード１００が送信したＴＣメッセージをノード１２１，１２２に転送することができ、ノード１１３は、ノード１００が送信したＴＣメッセージをノード１２３〜１２６に転送することができる。従って、ノード１００が送信したＴＣメッセージを、ノード１００の２ホップ先の全てのノード１２１〜１２６に転送することができる、ノード１００の隣接ノードの集合は、ノード１１１，１１３である。よって、ノード１１１，１１３が、ノード１００のＭＰＲノードとなる。【０００６】
各ノードは、自ノードのＭＰＲノードを選択した場合、ＭＰＲノードとして選択したノードの情報をHello メッセージに含める。このHello メッセージを受信することにより、ＭＰＲノードに選択されたノードは、自ノードが他のノードによってＭＰＲノードとして選択されたことを判断し、そのノードからＴＣメッセージを受信した場合、そのＴＣメッセージをブロードキャスト（またはマルチキャスト）によって転送する。【０００７】
各ノードは、予め設定された間隔で定期的にＴＣメッセージを送信し、ＭＰＲノードとして選択されたノードは、自ノードをＭＰＲノードと定めたノードからＴＣメッセージを受信するとそのＴＣメッセージを転送する。この結果、あるノードから送信されたＴＣメッセージは、ネットワーク内の全ノードに通知される。【０００８】
また、各ノードは、他のノードから送信されたＴＣメッセージを受信する毎に、そのＴＣメッセージに含まれるリンクの情報をトポロジーテーブルに記録する。そして、各ノードは、それぞれ自ノードのトポロジーテーブルに記録したリンク情報から、ネットワークトポロジー（ネットワークのノード接続構成）のグラフを作成し、ネットワーク内の各ノードまでの最短経路を計算する。そして、その計算結果に従って、ユニキャスト通信の転送経路を設定する。この結果、各ノードが、それぞれ他のノードへのユニキャスト通信の転送経路を設定することができる。【０００９】
非特許文献２では、制御メッセージだけではなくデータパケットのブロードキャストにもＭＰＲを利用することを提案している。有線ネットワークでは、同一ローカルネットワーク（ＬＡＮ）に接続する端末へのブロードキャストパケットは、スイッチングハブ等が転送を行い、ＬＡＮ内全体に届けられる。しかし、無線マルチホップネットワークにおいては、スイッチングハブのような機器が存在しないため、ネットワークが単一のネットワークアドレス（例えば、abc.def.0.0/24）を持ち、ネットワーク内の全端末がそのネットワークアドレスに属するホストアドレス（abc.def.0.1〜254）を持っていたとしても、ネットワークへのブロードキャストパケットはネットワーク内の全端末に届かない。非特許文献２では、前述のＭＰＲを利用することで、無線マルチホップネットワークにおいてもブロードキャストデータパケットをネットワーク全体に届けることを目的としている。非特許文献２に記載された技術における基本的な仕組みは、非特許文献１に記載された技術と同様である。異なる点は、ネットワークに流すメッセージがユーザデータである点である。【００１０】
非特許文献１，２に開示されている技術では、あるノードＮがＭＰＲノードとして選択するノードは、ノードＮと双方向通信可能なノードＮの隣接ノードに限定されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】T.Clausen他、“Optimized Link State Routing Protocol (OLSR)”，Internet Engineering Task Force (IETF) Request for Comments(RFC) 3626，２００３年１０月
【非特許文献２】J.Macker他、“Simplified Multicast Forwarding for MANET draft-ietf-manet-smf-01”，Internet Engineering Task Force (IETF)  Internet-Draft，２００５年６月
【発明の概要】
【発明が解決しようとする課題】
【００１２】
実際の通信の状況では、ノード毎の送信電力の違い、受信設定の違い、障害物や無線干渉による影響等により、２つのノード間で片方向でしか通信できない状況が多く発生する。このような２つのノード間のリンクを片方向リンクと称する。すなわち、２つのノード間のリンクであって、一方から他方へは通信可能であるが、その逆方向の通信を行えないリンクを片方向リンクと称する。片方向リンクは、ＡＲＰ（Address Resolution Protocol ）や、ＭＡＣ（Media Access Control）のＡｃｋ（ACKnowledgement）が必要なユニキャスト通信にはそのまま利用できない。しかし、ＡＰＲやＡｃｋを必要としないブロードキャスト通信やマルチキャスト通信には、メッセージの転送負荷を減らすために有効である。【００１３】
以下、図１４を参照して具体例を示す。図１４は、片方向リンクを含むネットワークの一例を示している。図１４では、４つのノードＡ〜Ｄを示し、各ノードを中心とする円は、ノードからの無線到達範囲を示している。本例では、ノードＡ，Ｂ間、ノードＢ，Ｃ間、および、ノードＣ，Ｄ間のリンクは双方向リンクである。一方、ノードＡ，Ｃ間のリンクは、ノードＡからノードＣへの通信のみが可能な片方向リンクである。【００１４】
仮に、ノードＡが片方向リンクを考慮してノードＣをＭＰＲノードとして選択できるものとすると、ノードＡがノードＢ，ＣにＴＣメッセージを送信し、ノードＣが、ノードＤにそのＴＣメッセージを送信すれば、ＴＣメッセージは行き渡る。一方、ノードＡが片方向リンクを考慮せず、ノードＢをＭＰＲノードに定めると、ノードＡがノードＢにＴＣメッセージを送信し、ノードＢがノードＣにＴＣメッセージを転送し、さらに、ノードＣがノードＤにＴＣメッセージを転送しなければならない。従って、図１４に示す例において、ノードＡは、ノードＣをＭＰＲノードとして選択した方が転送負荷の観点から好ましい。【００１５】
しかし、非特許文献１，２に記載された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 メッセージは、ブロードキャスト送信され、送信元からの無線到達範囲内に存在するノードに受信される。ただし、Hello メッセージは、受信されたノードによって転送されない。
【００３７】
また、隣接ノードに関するステータスは、例えば、隣接ノード自体のステータスと、隣接ノードとの間に介在するリンクのステータスとを含む。図３は、隣接ノードに関するステータスの例を示す説明図である。図３（ａ）は、隣接ノード自体のステータスを示し、図３（ｂ）は、隣接ノードとの間に介在するリンクのステータスを示す。
【００３８】
図３（ａ）に示すように、隣接ノード自体のステータスとして、「双方向隣接ノード」、「片方向隣接ノード」、「逆片方向隣接ノード」、「ＭＰＲノード」等がある。なお、各ステータスの表記の仕方は特に限定されず、図３（ａ）において括弧書きで示したように、“SYM_NEIGH ”，“ASYM_NEIGH”，“REV_ASYM_NEIGH”，“MPR_NEIGH”等のように表してもよい。
【００３９】
図３（ｂ）に示すように、隣接ノードとの間に介在するリンクのステータスとして「双方向リンク」、「相手側が片方向隣接ノードとなる片方向リンク」、「相手側が逆片方向隣接ノードとなる片方向リンク」、「切断」、「未定」等がある。図３（ｂ）に示すように、隣接ノードが片方向隣接ノードであるか逆片方向隣接ノードであるかによって、片方向リンクを区別している。なお、各ステータスの表記の仕方は特に限定されず、図３（ｂ）において括弧書きで示したように、“SYM_LINK”，“ASYM_LINK ”，“REV_ASYM_LINK ”，“LOST_LINK”，“UNSPEC_LINK”等のように表記してもよい。
【００４０】
また、図３（ａ），（ｂ）に示した以外のステータスが定められていてもよい。
【００４１】
次に、本発明の通信装置（ノード）の構成について説明する。図４は、本発明の通信装置の構成例を示すブロック図である。図４では、図２に示す各ノードのうちノード１１を例にして説明するが、図２に示す他のノード１２〜１４の構成も同様である。
【００４２】
ノード１１は、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 メッセージを送信する。
【００４５】
片方向リンク判定部２３は、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 メッセージの送信元のノードのＩＰアドレスを、隣接ノードのＩＰアドレスとして隣接ノードテーブルに登録する。さらに、その隣接ノード自体のステータスを「逆片方向隣接ノード（REV_ASYM_NEIGH）」とし、その隣接ノードとの間のリンクのステータスを「相手側が逆片方向隣接ノードとなる片方向リンク（REV_ASYM_LINK ）」として、隣接ノードテーブルに登録する。
【００５１】
２ホップ先ノードテーブル記憶部３２は、２ホップ先ノードテーブルを記憶する記憶装置である。図６は、２ホップ先ノードテーブルに登録される情報の例を示す説明図である。２ホップ先ノードテーブルは、例えば、自ノードの隣接ノードのＩＰアドレスと、自ノードから２ホップ先のノードのＩＰアドレスとを登録する。ここで、２ホップ先のノードは、「自ノードの隣接ノード」の隣接ノードに該当する。２ホップ先ノードテーブルは、さらに、例えば、「自ノードの隣接ノード」に着目した場合における、２ホップ先のノード自体のステータスと、自ノードの隣接ノードと２ホップ先のノードとの間のリンクのステータスも登録する。
【００５２】
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 送信処理部２２は、それぞれHello メッセージを送信する（ステップＳ１）。各Hello メッセージは、送信元からの無線到達範囲内に存在する全ノードに受信される。このHello メッセージは、転送されない。ステップＳ１におけるHello メッセージ送信により、各ノードは、自ノードの情報を広告し、また、隣接ノードの情報を収集する。
【００６６】
そして、各ノードにおいて、ＭＰＲ選択部２６は、自ノードのＭＰＲノードを決定する（ステップＳ２）。ＭＰＲノード決定後、各ノードは、次回のHello メッセージ時に、自ノードのＭＰＲノードの情報も含めて送信する（ステップＳ３）。
【００６７】
次に、各ノードの制御メッセージ送受信部５１は、自ノードをＭＰＲノードとして選択したノードとのリンクの情報を含むＴＣメッセージを送信する（ステップＳ３）。ただし、このとき、ＴＣメッセージには、双方向リンクの情報のみを含める。また、自ノードをＭＰＲノードとして選択したノードから、ＴＣメッセージを受信した場合、そのＴＣメッセージを転送する。この結果、各ノードは、他の各ノードが送信したＴＣメッセージを受信することになる。
【００６８】
各ノードのトポロジー情報作成部５２は、他のノードから受信したＴＣメッセージを用いてネットワークのトポロジー情報を作成し、トポロジー情報記憶部５３に記憶させる（ステップＳ５）。このトポロジー情報を用いることで、自身からネットワーク内の各ノードまでの最短経路を計算することができる。各ノードは、自身から各ノードまでの最短経路を計算し、計算した最短経路に基づき、宛先と転送ノード、宛先までのホップ数を記録したユニキャスト経路表（不図示）を保持する。
【００６９】
以降、ステップＳ１からの動作を繰り返す。この結果、ノードの移動、追加、離脱等の変化が合っても、ネットワークに応じたトポロジー情報がステップＳ５で作成される。なお、ステップＳ１の時点において、既にＭＰＲノードが定まっているならば、その情報もHello メッセージに含める。
【００７０】
また、各ノードがステップＳ５の処理を行い、トポロジー情報を作成することによって、各ノードは、他のノードまでの最短経路を導出したり、他のノードまでのホップ数をカウントしたりすることができる。
【００７１】
次に、各ノードが、ＭＰＲノードを決定し、そのＭＰＲノードを介してＴＣメッセージ等をネットワーク内の各ノードに通知する際の動作について説明する。図８は、ＭＰＲノードを介してメッセージを送信する際の処理経過の例を示すフローチャートである。また、以下の説明では、ノード１１，１３が、それぞれノード１２をＭＰＲノードとして選択しているものとする。そして、各ノード１１〜１４は、図２に示す状態になったとする。
【００７２】
［片方向リンクの判定］
まず、片方向リンクの判定処理について説明する。各ノードのHello 送信処理部２２は、隣接ノードテーブル、２ホップ先ノードテーブル、およびＭＰＲノードテーブルに基づいて、Hello メッセージを作成し、送信する。既に説明したように、このHello メッセージは、無線到達範囲内に存在するノードに受信されるが、転送はされない。各ノードのHello 送信処理部２２は、Hello メッセージに、自ノードのＩＰアドレス、（既にHello メッセージを受信して存在を認識している）自ノードの隣接ノードのＩＰアドレス、およびその隣接ノードに関するステータスを含める。また、自ノードのＭＰＲノードを選択している場合には、そのＭＰＲノードを示す情報も含める。
【００７３】
各ノードのHello メッセージ受信処理部２１は、Hello メッセージを受信すると、Hello メッセージの内容に応じて、隣接ノードテーブル、２ホップ先ノードテーブルを更新する。すなわち、Hello メッセージ受信処理部２１は、Hello メッセージの送信元のＩＰアドレスを、自ノードの隣接ノードのＩＰアドレスとして、隣接ノードテーブルに登録する。
【００７４】
また、Hello メッセージ受信処理部２１は、Hello メッセージにおいて、Hello メッセージ送信元ノードの隣接ノードとして自ノードが記述されていた場合、そのHello メッセージ送信元ノードのステータスを「双方向隣接ノード」とし、その双方向隣接ノードとの間のリンクのステータスを“SYM_LINK （図３参照）”として、隣接ノードテーブルに登録する。
【００７５】
また、Hello メッセージ受信処理部２１は、Hello メッセージにおいて、Hello メッセージ送信元ノードの隣接ノードとして自ノードが記述されていない場合、そのHello メッセージ送信元ノードのステータスを「片方向隣接ノード」として、隣接ノードテーブルに登録する。また、そのHello メッセージ送信元ノード（片方向隣接ノード）との間のリンクのステータスを“ASYM_LINK （図３参照）”として、隣接ノードテーブルに登録する。また、Hello メッセージ受信処理部２１からHello メッセージの受信通知を受けた片方向リンク判定部２３は、Hello メッセージの受信回数を隣接ノードテーブルに記録する。さらに、片方向リンク判定部２３は、受信回数が３回以上で、かつ、隣接ノードのステータスが「片方向隣接ノード」である隣接ノードを、ユニキャストHello 送信処理部２５へ通知する。
【００７６】
なお、ここでは、各ノードにおけるHello メッセージ送信間隔が等しいものとしている。この場合、通常、１回半のHello メッセージの往復で、双方向隣接ノードとして認識できることに基づいて、上記の３回という回数を定めた。ただし、上記の所定回数は３回でなくてもよい。また、各ノードにおけるHello メッセージ送信間隔が異なっている場合、その態様に応じて、上記の所定回数を決定しておけばよい。
【００７７】
図８に示す例では、ノード１１は、ノード１２が双方向通信ノードであり、ノード１２をＭＰＲノードとしているという情報を含むHello メッセージを送信する。このHello メッセージを受信したノード１３は、ノード１１が片方向隣接ノードであると判定する。そして、ノード１１が片方向隣接ノードであり、ノード１２，１４が双方向通信ノードであり、ノード１２をＭＰＲノードとしているという情報を含むHello メッセージを送信する。ただし、このHello メッセージは、ノード１１に到達しないものとする。
【００７８】
この結果、ノード１１は、ノード１３を隣接ノードとして定めていないHello メッセージを繰り返し送信し、ノード１３は、このHello メッセージを３回受信した時点で、ノード１１との間のリンクが片方向リンクであり、そのステータスが“ASYM_LINK”であると判断する（ステップＳ１１、図８参照）。
【００７９】
また、Hello メッセージ受信処理部２１は、Hello メッセージ送信元のノードから、Hello メッセージを受信しなくなり、そのノードから受信していたHello メッセージの有効期間が経過した場合、そのノードに関しては切断（LOST）と判断し、隣接ノードテーブルおよび２ホップ先ノードテーブルから、そのノードに関する情報を削除する。
【００８０】
また、Hello メッセージ受信処理部２１は、Hello メッセージ送信元ノードの隣接ノードとしてHello メッセージ内に記述されているノードのうち、自ノードの隣接ノードテーブルに登録されていないノードがあれば、そのノードを２ホップ先ノードと判断する。そして、Hello 受信処理部２１は、そのHello メッセージの送信元のノードのＩＰアドレスを、隣接ノードのＩＰアドレスとして２ホップ先ノードテーブルに登録する。さらに、２ホップ先ノードのＩＰアドレス、および、自ノードの隣接ノードに着目した場合の２ホップ先ノードに関するステータスをHello メッセージから読み込み、２ホップ先ノードテーブルに登録する。
【００８１】
また、Hello メッセージ受信処理部２１は、自ノードがHello メッセージの送信元ノードによってＭＰＲノードに選択されていることをHello メッセージによって認識すると、そのHello メッセージの送信元ノードによってＭＰＲノードに選択されている旨をブロードキャスト転送テーブルに登録する。
【００８２】
［片方向リンクの通知］
ノード１３の片方向リンク判定部２３が、Hello メッセージの送信元ノードと自ノードとの間のリンクが片方向リンク（ASYM_LINK）であると判定した場合、ノード１３のユニキャストHello 送信処理部２５は、そのHello メッセージの送信元ノードに対して、ユニキャストHello メッセージを送信するか否かを判定する。送信すると判定した場合、ノード１３のユニキャストHello 送信処理部２５は、ノード１１が自ノードにとって片方向隣接ノードであり、ノード１１と自ノードとのリンクステータスが“ASYM_LINK”であるという情報を含むユニキャストHello メッセージを作成する。なお、ユニキャストHello メッセージには、ユニキャストHello メッセージであることを示す片方向リンクフラグを含める。ノード１３のユニキャストHello 送信処理部２５は、作成したユニキャストHello メッセージをHello 送信処理部２２に渡し、Hello 送信処理部２２は、そのユニキャストHello メッセージを送信する。なお、Hello 送信処理部２２は、Hello メッセージの送信間隔毎に、そのユニキャストHello メッセージを送信する。
【００８３】
片方向リンク判定部２３が、Hello メッセージの送信元ノードと自ノードとの間のリンクが片方向リンク（ASYM_LINK）であると判定した場合、ユニキャストHello 送信処理部２５が、そのHello メッセージの送信元ノードに対して、ユニキャストHello メッセージを送信するか否かを判定する処理について説明する。ここでは、図９に示す各ノードを例にして説明する。図９において、実線の矢印は、双方向リンクを表している。破線の矢印は、片方向リンクを表している。例えば、図９において、ノード１１，１７間のリンクは片方向リンクであり、ノード１１からノード１７への通信のみが可能である。また、点線の矢印は、矢印の始点のノードが選択しているＭＰＲノードを表している。例えば、図９において、ノード１１は、ノード１２，１３，１４をＭＰＲノードとして選択していることを表している。
【００８４】
ここでは、ノード１７が、ノード１１との間のリンクが片方向リンク（ASYM_LINK）であると判定した場合に、ノード１７がノード１１にユニキャストHello メッセージを送信するか否かを判定する場合を例にして説明する。
【００８５】
ノード１７のユニキャストHello 送信処理部２５は、以下の（１）〜（６）の手順により、ノード１１にユニキャストHello メッセージを送信するか否かを判定する
【００８６】
（１）ノード１７のユニキャストHello 送信処理部２５は、ノード１１へのユニキャスト経路のホップ数をトポロジー情報に基づいてカウントし、そのホップ数が３以上であるならば、ユニキャストHello メッセージを送信しないと決定する。そのホップ数が“２”であるならば、以下の計算を行う。
【００８７】
（２）ノード１７のユニキャストHello 送信処理部２５は、ノード１１の隣接ノード（ノード１２，１３，１４）のうち、ノード１１がＭＰＲノードに選択していて、かつ、ノード１７自身がHello メッセージを受信しているノードを選択する。なお、これまでの説明において、「双方向隣接ノード」、「片方向隣接ノード」および「逆片方向隣接ノード」をそれぞれ隣接ノードと称していたが、この（２）の処理において、ユニキャストHello メッセージを送信するか否かの判定対象となるノードの隣接ノードは、「双方向隣接ノード」および「逆片方向隣接ノード」であるものとする。すなわち、ここでは、ノード１１の隣接ノードとは、ノード１１の双方向隣接ノードおよびノード１１の逆片方向隣接ノードである。図９に示す例では、ノード１１の隣接ノードのうち、ノード１１がＭＰＲノードに選択していて、かつ、ノード１７自身がHello メッセージを受信しているノードは、ノード１３，１４である。よって、ノード１７のユニキャストHello 送信処理部２５は、ノード１３，１４を選択する。
【００８８】
また、図９では、ノード１１の隣接ノード１２，１３，１４が全て双方向隣接ノードとなっているが、上述のように、ノード１１の隣接ノードは、逆片方向隣接ノード（ノード１１にとって、REV_ASYM_LINK で結ばれるノード）も含む。例えば、仮に、図９に示す例において、ノード１６が、ノード１１の逆片方向隣接ノードであり、ノード１１がノード１６もＭＰＲノードとしているとする。この場合、ノード１７は、ノード１６からHello メッセージを受信しているので、ノード１６も選択することとなる。
【００８９】
（３）ノード１７のユニキャストHello 送信処理部２５は、ノード１１から見て、上記（２）で選択したノードを経由した２ホップ先のノードを特定し、その集合を第１の集合Ｘとする。ただし、自ノード（本例ではノード１７）は、除外する。本例では、ノード１１からノード１３を経由した２ホップ先のノード、および、ノード１１からノード１４を経由した２ホップ先のノードのうち、ノード１７以外のノードは、ノード１６，１８である。よって、ノード１６，１８を第１の集合Ｘとする。
【００９０】
なお、ノード１１から見て２ホップ先のノードまでの経路において、ノード１１や、上記（２）で選択したノードに着目した場合、双方向リンクだけでなく、“REV_ASYM_LINK （図３（ｂ）参照）”が含まれていてもよい。例えば、図９に示す例において、ノード１３にとってノード１６が逆片方向隣接ノードであったとする。この場合であっても、ノード１１からノード１３を経由した２ホップ先のノードとしてノード１６を特定する。
【００９１】
（４）次に、ノード１７のユニキャストHello 送信処理部２５は、自ノード（ノード１７）を経由したノード１１から２ホップ先のノードを特定し、その集合を第２の集合Ｙとする。本例では、ノード１６，１９を特定し、第２の集合Ｙとする。
【００９２】
上記の（４）においても、ノード１１から２ホップ先のノードまでの経路で、ノード１１や自ノード（ノード１７）に着目した場合、双方向リンクだけでなく、“REV_ASYM_LINK （図３（ｂ）参照）”が含まれていてもよい。例えば仮に、ノード１７にとって、ノード１９との間のリンクが“REV_ASYM_LINK”であったとしても、ノード１９を第２の集合Ｙに含めてよい。
【００９３】
（５）次に、ノード１７のユニキャストHello 送信処理部２５は、第１の集合Ｘおよび第２の集合Ｙに属するノードを、“Covered ”，“Uncovered ”，“Extra Covered ”の３種類に分類する。
【００９４】
“Covered ”とは、第１の集合Ｘおよび第２の集合Ｙの両方に属している、ノード１１から２ホップ先のノードである。本例では、ノード１６が“Covered ”に該当する。
【００９５】
“Uncovered ”とは、第１の集合Ｘに属しているが第２の集合Ｙに属していない、ノード１１から２ホップ先のノードである。本例では、ノード１８が“Uncovered ”に該当する。
【００９６】
“Extra Covered ”とは、第１の集合Ｘに属していないが第２の集合Ｙに属している、ノード１１から２ホップ先のノードである。本例では、ノード１９が“Extra Covered ”に該当する。
【００９７】
（６）次に、ノード１７のユニキャストHello 送信処理部２５は、“Extra Covered ”に該当するノードが１つ以上ある場合には、ノード１１に対してユニキャストHello メッセージを送信しないと決定する。その他の場合（すなわち、“Extra Covered ”に該当するノードが０個である場合）には、ノード１１に対してユニキャストHello メッセージを送信すると決定する。
【００９８】
ここで、“Extra Covered ”に該当するノードが１つ以上ある場合に、ノード１１にユニキャストHello メッセージを送信しないと決定するのは、自ノード（ノード１７）がノード１１によって既存のＭＰＲノードとともにＭＰＲノードとして選択され、ＭＰＲノードが増加してしまう可能性があるからである。
【００９９】
“Extra Covered ”に該当するノードが１つ以上あるということは、自ノードが片方向隣接ノードによってＭＰＲノードとして選択された場合に、その片方向隣接ノードを起点とし、自ノードを経由してＴＣメッセージが転送されることになる新たな２ホップ先ノードが発生することを意味する。
【０１００】
ユニキャストHello 送信処理部２５は、ユニキャストHello メッセージを送信すると決定した場合、Hello 送信処理部２２にそのユニキャストHello メッセージの送信を依頼する。Hello 送信処理部２２は、元のHello メッセージの送信元ノードに対して、他のノードを経由してユニキャストHello メッセージを送信する。図２に示す例では、ノード１３が送信したユニキャストHello メッセージは、ノード１２を経由して、ノード１１に受信される（ステップＳ１２、図８参照）。なお、（１）の処理によって、ユニキャストHello メッセージの宛先までのホップ数が“２”であると判定した場合にのみ、（２）以降の処理を行う。よって、ユニキャストHello メッセージの宛先ノードまでに経由する他のノードは１つである。
【０１０１】
なお、ユニキャストHello 送信処理部２５は、どのノードを経由してユニキャストHello メッセージを送信するのかを、トポロジー情報に基づいて判断すればよい。すなわち、ステップＳ５（図７参照）で作成されているトポロジー情報に基づいて、ユニキャストHello メッセージの宛先までの最新経路を決定し、その経路で、ユニキャストHello メッセージを送信するように、Hello 送信処理部２２に要求すればよい。
【０１０２】
図８に示すステップＳ１２で、ノード１３が送信したユニキャストHello メッセージには、ノード１１が片方向隣接ノードであり、ノード１２，１４が双方向隣接リンクであり、ノード１２をＭＰＲノードに定めている旨の情報が含まれている。
【０１０３】
［片方向リンクを考慮したＭＰＲノードの計算］
ユニキャストHello メッセージを受信したノードのHello 受信処理部２１は、そのユニキャストHello メッセージをユニキャストHello 受信処理部２４に渡す。すると、ユニキャストHello 受信処理部２４は、そのユニキャストHello メッセージの送信元ノードのＩＰアドレスを、隣接ノードテーブルに登録する。さらに、ユニキャストHello 受信処理部２４は、その送信元ノードのステータスを「逆方向隣接ノード（REV_ASYM_NEIGH）」とし、その送信元ノードとの間のリンクのステータスを「REV_ASYM_LINK」とし、隣接ノードテーブルに登録する。
【０１０４】
すなわち、ユニキャストHello メッセージを受信したノードは、自ノードが片方向リンクにおける送信側ノードに該当していることを、ユニキャストHello メッセージによって認識することができる。
【０１０５】
また、ユニキャストHello 受信処理部２４は、そのユニキャストHello メッセージの送信元ノードの隣接ノード（ここでは、双方向隣接ノードまたは逆片方向隣接ノード）のうち、自身の隣接ノードでないノードの情報を、２ホップ先ノードテーブルに登録する。
【０１０６】
そして、ＭＰＲ選択部２６は、隣接ノードテーブルおよび２ホップ先ノードテーブルの変化を契機として、隣接ノードテーブルおよび２ホップ先ノードテーブルを参照して、ＭＰＲノードを特定する。ＭＰＲ選択部２６は、隣接ノードテーブルにおいて、「双方向隣接ノード」および「逆片方向隣接ノード」として登録されているノードの中から、自ノードから２ホップ先の全てのノードに対して制御メッセージ（ネットワーク内の全ノードに通知すべき制御メッセージ）を転送することができるノード群を、できるだけノードの数が少なくなるように選択する。ＭＰＲ選択部２６は、選択した各ノードをＭＰＲノードとして決定する（ステップＳ１３、図８参照）。図８に示す例では、ノード１１（図２参照）のＭＰＲ選択部２６は、双方向隣接ノード１２と逆片方向隣接ノード１３の中から、逆片方向隣接ノード１３をＭＰＲノードとして決定する。
【０１０７】
ＭＰＲ選択部２６は、新たに決定したＭＰＲノードのＩＰアドレスを、ＭＰＲノードテーブルに登録する。また、ＭＰＲノードに該当しなくなったノードの情報がＭＰＲノードテーブルに記憶されている場合、そのノードの情報をＭＰＲノードテーブルから削除する。
【０１０８】
また、ＭＰＲ選択部２６は、隣接ノードテーブルにおいて、隣接ノードのうちＭＰＲノードとしたノードのステータスを「ＭＰＲノード（MPR_NEIGH）」として更新してもよい。例えば、双方向隣接ノードや逆片方向隣接ノードがＭＰＲノードにも該当する場合には、それらのノードのステータスを上記のように「ＭＰＲノード（MPR_NEIGH）」としてもよい。
【０１０９】
その後、Hello 受信処理部２１がHello メッセージを作成・送信する場合には、新たに定めたＭＰＲノードの情報をそのHello メッセージに含める。図８に示す例では、ステップＳ１３の後、ノード１１は、ノード１２が双方向隣接リンクであり、ノード１３が逆片方向隣接ノードかつＭＰＲノードであるという情報を含んだHello メッセージを送信する。
【０１１０】
［ＭＰＲノードとして選択された旨のブロードキャスト転送テーブルへの登録］
Hello メッセージを受信したノードのHello 受信処理部２１は、自ノードがそのHello メッセージにおいてＭＰＲノードに定められているならば、そのHello メッセージの送信元ノードにとって自ノードがＭＰＲノードである旨をブロードキャスト転送テーブルに登録する（ステップＳ１４、図８参照）。例えば、受信したHello メッセージにおいて、そのHello メッセージの送信元ノードと自ノードとのリンクが“REV_ASYM_LINK”あるいは“SYM_LINK”であり、自ノードがＭＰＲノードとして定められている場合、その送信元のノードにとって自ノードがＭＰＲノードであることを登録する。図８に示す例では、ノード１３は、ノード１３自身がノード１１のＭＰＲノードである旨をブロードキャスト転送テーブルに登録する。
【０１１１】
その後、ノード１３の制御メッセージ送受信部５１は、自ノードをＭＰＲノードとして定めたノードからＴＣメッセージを受信した場合、そのＴＣメッセージを転送する。すなわち、制御メッセージ送受信部５１は、ＴＣメッセージを受信したならば、ＴＣメッセージの送信・転送元が自ノードをＭＰＲノードとして定めたノードであるか否かを、ブロードキャスト転送テーブルを参照して判定すればよい。そして、ＴＣメッセージの送信・転送元が自ノードをＭＰＲノードとして定めたノードであるならば、そのＴＣメッセージを転送すればよい。
【０１１２】
また、ノード１３のデータパケット送受信部６１は、自ノードをＭＰＲノードとして定めたノードから、ネットワーク全体へのブロードキャストパケットを受信した場合、そのパケットを転送する。すなわち、データパケット送受信部６１は、ネットワーク全体へのブロードキャストパケットを受信したならば、そのパケットの送信・転送元が自ノードをＭＰＲノードとして定めたノードであるか否かを、ブロードキャスト転送テーブルを参照して判定すればよい。そして、そのパケットの送信・転送元が自ノードをＭＰＲノードとして定めたノードであるならば、そのパケットを転送すればよい。
【０１１３】
図８では、ノード１１，１３を例に説明したが、各ノードが、それぞれ上記と同様の動作を繰り返せばよい。
【０１１４】
以上の説明では、あるノードが片方向隣接ノードに対してユニキャストHello メッセージを送信する場合、その片方向隣接ノードまでの通信経路が存在し、その片方向隣接ノードにユニキャストHello メッセージを送信できる場合を示した。ネットワークの状態によっては、片方向隣接ノードまでの通信経路しない場合もある。例えば、図１０に示す例において、ノード１３に着目した場合、ノード１３から片方向隣接ノード１１へのユニキャストHello メッセージの送信経路は存在しない。この結果、ノード１１は、ノード１３を逆片方向隣接ノードとして認識できない。このような場合、定められた条件を満たしている場合に、ノード１３が、自ノードが片方向隣接ノード１１のＭＰＲノードに該当すると自律的に判断し、片方向隣接ノード１１からのＴＣメッセージや、ネットワーク全体へのブロードキャストパケットを転送送信してもよい。この結果、ノード１４は、ノード１１に対してユニキャスト送信できないが、ノード１１からのＴＣメッセージや、ネットワーク全体へのブロードキャストパケットは受信することができる。
【０１１５】
このような自律的判断について説明する。ユニキャストHello 受信処理部２５は、自ノードから片方向隣接ノード（すなわち、ユニキャストHello メッセージの宛先）までの通信経路がないことを、ユニキャスト経路表に基づいて判断したとする。この場合、ユニキャストHello 受信処理部２５は、自ノードの隣接ノードのうち、その片方向隣接ノードとの間に双方向リンクと片方向リンクのいずれのリンクも存在しないノードがあるかどうかを判断する。そのようなノードがあれば、ユニキャストHello 受信処理部２５は、自ノードがその片方向隣接ノードのＭＰＲノードであると判定し、その旨をブロードキャスト転送テーブルに登録する。ただし、共通のノードを片方向隣接ノードとして認識している同じ条件のノードが複数存在する場合には、その複数のノードのうち、識別情報の値が最小のノードが、ブロードキャスト転送テーブルへの登録を行い、ＭＰＲノードとして動作する。ここでは、識別情報の値が最小となっているノードがＭＰＲノードとして動作する場合を例にしたが、「識別情報の値が最小」という条件とは異なる条件により、ＭＰＲノードとして動作するノードを定めてもよい。
【０１１６】
より具体的に説明する。片方向リンク判定部２３が、Hello メッセージの送信元ノードと自ノードとの間のリンクが片方向リンク（ASYM_LINK）であると判定した場合、ユニキャストHello 受信処理部２５は、そのHello メッセージの送信元ノードの情報を片方向リンク判定部２３から受け取る。そのHello メッセージの送信元ノード（Ｘとする。）は、自ノードにとって片方向隣接ノードである。ユニキャストHello 受信処理部２５は、その片方向隣接ノードＸへのユニキャスト経路があるかどうかを、ユニキャスト経路表から判断する。片方向隣接ノードＸへの経路がない場合、ユニキャストHello 受信処理部２５は、自ノードの双方向隣接ノードのうち、ノードＸとの間に片方向リンクを有し、ノードＸを片方向隣接ノードと認識しているノードが存在しているか否かを判定する。そのようなノードが存在しているならば、ユニキャストHello 受信処理部２５は、それらのノードの中で自ノードの識別情報が最小であるか否かを判定する。自ノードの双方向隣接ノードのうち、ノードＸとの間に片方向リンクを有し、ノードＸを片方向隣接ノードと認識しているノードが存在していない場合、または、それらのノードの中で自ノードの識別情報が最小である場合、ユニキャストHello 受信処理部２５は、以下に示す処理を行う。なお、いずれの場合でもなければ、処理を終了する。
【０１１７】
ユニキャストHello 受信処理部２５は、自ノードの双方向隣接ノードのうち、上記のノードＸとの間に双方向リンクと片方向リンクのいずれのリンクも存在しないノードがあるかどうかを判断する。そのようなノードがなければ処理を終了する。そのようなノードがあれば、ユニキャストHello 受信処理部２５は、自ノードがノードＸのＭＰＲノードであると判断し、その旨をブロードキャスト転送テーブルに登録する。その後、そのノードは、ノードＸからＴＣメッセージや、ネットワーク全体へのブロードキャストパケットを受信した場合、そのＴＣメッセージやブロードキャストパケットを転送する。
【０１１８】
本実施形態によれば、自ノードにHello メッセージを送信してくるノードと自ノードとの間のリンクが片方向リンクであり、自ノードにとってそのノードが片方向隣接ノードである場合、その片方向隣接ノードに対して、ユニキャストHello メッセージを送信する。従って、片方向リンクにおける送信側のノードは、逆片方向隣接ノードの存在を認識することができ、逆片方向隣接ノードおよび双方向隣接ノードの中からＭＰＲノードを決定することができる。その結果、片方向リンクも利用して、効率的なメッセージ転送を実現することができる。
【０１１９】
また、各ノードは、所定の条件（“Extra Covered ”に該当するノードが０個であるという条件）を満たす場合にユニキャストHello メッセージを送信し、その所定の条件が満たされていなければユニキャストHello メッセージを送信しない。このことにより、ＭＰＲノードの数の増加を抑えることができ、効率的なメッセージ転送を実現することができる。
【０１２０】
また、ユニキャストHello メッセージを宛先（片方向隣接ノード）まで送ることができる経路が存在しない場合、自ノードをその片方向隣接ノードのＭＰＲノードとして自律的に判断することにより、その片方向隣接ノードからのメッセージをネットワーク内に転送することができる。
【０１２１】
次に、本発明の最小構成について説明する。図１１は、本発明の通信装置の最小構成の例を示すブロック図である。図１２は、本発明の通信システムの最小構成の例を示すブロック図である。
【０１２２】
本発明の通信システムは、メッセージを無線で送受信する通信装置８１を複数備える（図１２参照。）。
【０１２３】
そして、各通信装置８１は、第１メッセージ送信手段７１と、リンク検出手段７２と、第２メッセージ送信手段７３と、転送ノード選択手段７４とを備える（図１１、図１２参照）。
【０１２４】
第１メッセージ送信手段７１（例えば、Hello 送信処理部２２）は、ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージ（例えば、Hello メッセージ（第１のHello メッセージ））を送信する。
【０１２５】
リンク検出手段７２（例えば、Hello 受信処理部２２および片方向リンク判定部２３によって実現される。）は、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出する。
【０１２６】
第２メッセージ送信手段７３（例えば、ユニキャストHello 送信処理部２５およびHello 送信処理部２２によって実現される。）は、片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に片方向リンクがあることを通知するための第２のメッセージ（例えば、ユニキャストHello メッセージ（第２のHello メッセージ））を作成し、ユニキャスト送信する。
【０１２７】
転送ノード選択手段７４（例えば、ＭＰＲ選択部２６）は、双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノード（例えば、ＭＰＲノード）を選択する。
【０１２８】
そのような構成によれば、転送ノード選択手段７４が、双方向隣接ノードおよび逆片方向隣接ノードの中から転送ノードを選択することができるので、片方向リンクも利用して、効率的なメッセージ転送を実現することができる
【０１２９】
また、リンク検出手段７２が、自ノードが隣接ノードとして記述されていない第１のメッセージの受信回数に基づいて、第１のメッセージを送信してくる他のノードと自ノードとの間のリンクが片方向リンクであると判定する構成であってもよい。
【０１３０】
また、第２メッセージ送信手段７３が、片方向隣接ノードまでのホップ数に応じて、第２のメッセージの送信を抑制する（例えば、片方向隣接ノードまでのホップ数が３以上のときにユニキャストHello メッセージを送信しない）構成であってもよい。
【０１３１】
また、第２メッセージ送信手段７３が、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、新たなノードが発生する場合に、その片方向隣接ノードに対する第２のメッセージの送信を抑制する（例えば、“Extra Covered ”に該当するノードが１つ以上ある場合にユニキャストHello メッセージを送信しない）構成であってもよい。
【０１３２】
また、片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中にその片方向隣接ノードからの第１のメッセージを受信していないノードが存在する場合に、自ノードをその片方向隣接ノードの転送ノードとして定める自律的転送ノード判定手段（例えば、ユニキャストHello 送信処理部２５によって実現される。）を備える構成であってもよい。
【０１３３】
また、自律的転送ノード判定手段が、共通の片方向隣接ノードに関して、その片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中にその片方向隣接ノードからの第１のメッセージを受信していないノードが存在するという条件を満たす複数の通信装置が存在する場合、自ノードの識別情報が、その複数の通信装置の識別情報の中で所定の条件（例えば、識別情報が複数の通信装置の中で最小であるという条件）を満たしている場合に、自ノードを片方向隣接ノードの転送ノードとして定める構成であってもよい。
【０１３４】
また、本発明による通信装置は、自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信部と、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出部と、前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信部と、前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択部とを備えることを特徴とする通信装置であってもよい。
【０１３５】
リンク検出部が、自ノードが隣接ノードとして記述されていない第１のメッセージの受信回数に基づいて、第１のメッセージを送信してくる他のノードと自ノードとの間のリンクが片方向リンクであると判定する構成であってもよい。
【０１３６】
第２メッセージ送信部が、片方向隣接ノードまでのホップ数に応じて、第２のメッセージの送信を抑制する構成であってもよい。
【０１３７】
第２メッセージ送信部が、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制する構成であってもよい。
【０１３８】
片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在する場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める自律的転送ノード判定部を備える構成であってもよい。
【０１３９】
自律的転送ノード判定部が、共通の片方向隣接ノードに関して、前記片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在するという条件を満たす複数の通信装置が存在する場合、自ノードの識別情報が、前記複数の通信装置の識別情報の中で所定の条件を満たしている場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める構成であってもよい。
【０１４０】
また、本発明による通信システムは、メッセージを無線で送受信する通信装置を複数備え、各通信装置が、自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信部と、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出部と、前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信部と、前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択部とを含むことを特徴とする通信システムであってもよい。
【０１４１】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１４２】
この出願は、２０１０年３月２４日に出願された日本特許出願２０１０−０６８５４０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用の可能性】
【０１４３】
本発明は、無線マルチホップネットワークに適用される通信システムとして好適に利用される。
【符号の説明】
【０１４４】
１１〜１４  ノード（通信装置）
２１  Hello 受信処理部
２２  Hello 送信処理部
２３  片方向リンク判定部
２４  ユニキャストHello 受信処理部
２５  ユニキャストHello 送信処理部
２６  ＭＰＲ選択部
３１  隣接ノードテーブル記憶部
３２  ２ホップ先ノードテーブル記憶部
３３  ＭＰＲノードテーブル記憶部
３４  ブロードキャスト転送テーブル記憶部
【図１】
2011118133.tif 000003
【図２】
2011118133.tif 000004
【図３】
2011118133.tif 000005
【図４】
2011118133.tif 000006
【図５】
2011118133.tif 000007
【図６】
2011118133.tif 000008
【図７】
2011118133.tif 000009
【図８】
2011118133.tif 000010
【図９】
2011118133.tif 000011
【図１０】
2011118133.tif 000012
【図１１】
2011118133.tif 000013
【図１２】
2011118133.tif 000014
【図１３】
2011118133.tif 000015
【図１４】
2011118133.tif 000016
【手続補正書】
【提出日】平成24年9月26日(2012.9.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信手段と、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出手段と、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信手段と、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択手段とを備え、
第２メッセージ送信手段は、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制する
ことを特徴とする通信装置。
【請求項２】
リンク検出手段は、自ノードが隣接ノードとして記述されていない第１のメッセージの受信回数に基づいて、第１のメッセージを送信してくる他のノードと自ノードとの間のリンクが片方向リンクであると判定する
請求項１に記載の通信装置。
【請求項３】
第２メッセージ送信手段は、片方向隣接ノードまでのホップ数に応じて、第２のメッセージの送信を抑制する
請求項１または請求項２に記載の通信装置。
【請求項４】
片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在する場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める自律的転送ノード判定手段を備える
請求項１から請求項３のうちのいずれか１項に記載の通信装置。
【請求項５】
自律的転送ノード判定手段は、
共通の片方向隣接ノードに関して、前記片方向隣接ノードに対して第２のメッセージをユニキャスト送信可能な通信経路が存在せず、自ノードの隣接ノードの中に前記片方向隣接ノードからの第１のメッセージを受信していないノードが存在するという条件を満たす複数の通信装置が存在する場合、自ノードの識別情報が、前記複数の通信装置の識別情報の中で所定の条件を満たしている場合に、自ノードを前記片方向隣接ノードの転送ノードとして定める
請求項４に記載の通信装置。
【請求項６】
メッセージを無線で送受信する通信装置を複数備え、
各通信装置は、
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信手段と、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出手段と、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信手段と、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択手段とを含み、
第２メッセージ送信手段は、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制する
ことを特徴とする通信システム。
【請求項７】
メッセージを無線で送受信する通信装置を複数備える通信システムに適用される通信方法であって、
各通信装置が、自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信し、
各通信装置が、第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出し、
各通信装置が、片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信し、
各通信装置が、双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択し、
片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定し、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制する
ことを特徴とする通信方法。
【請求項８】
コンピュータに、
自ノードの隣接ノードとなる通信装置の情報を含む第１のメッセージを送信する第１メッセージ送信処理、
第１のメッセージを受信できるが自ノードからの第１のメッセージを到達させることができない片方向リンク、および、双方向で第１のメッセージを到達させることができる双方向リンクを検出するリンク検出処理、
前記片方向リンクを介して第１のメッセージを送信してくる通信装置である片方向隣接ノードに対して、当該片方向隣接ノードと自ノードとの間に前記片方向リンクがあることを通知するための第２のメッセージを作成し、ユニキャスト送信する第２メッセージ送信処理、および、
前記双方向リンクを介して第１のメッセージを送信してくる通信装置である双方向隣接ノードと、第２のメッセージの送信元に該当する通信装置である逆片方向隣接ノードの中から、自ノードが送信したメッセージを転送すべき転送ノードを選択する転送ノード選択処理を実行させ、
第２メッセージ送信処理で、片方向隣接ノードを起点として当該片方向隣接ノードが選択した転送ノードを経由する２ホップ先のノードと、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとに基づいて、自ノードが転送ノードに選択された場合に、片方向隣接ノードを起点として自ノードを経由する２ホップ先のノードとして新たなノードが発生するか否かを判定させ、前記新たなノードが発生する場合に、前記片方向隣接ノードに対する第２のメッセージの送信を抑制させる
ための通信プログラム。
【国際調査報告】
2011118133.tif 000017
2011118133.tif 000018
2011118133.tif 000019