(57)【要約】【課題】情報量を削減することができる、アドホック・ネットワークを構成するノードを得る。【解決手段】ノード１０１−ｓは、管理可能な数を超えて隣接ノードが存在する状態の場合、ノード１０１−ａから隣接ノードの情報を含むハローメッセージを受信すると、隣接ノードの集合中の最小のリンク品質Ｌｍｉｎよりも、前記ハローメッセージのリンク品質Ｌａが小さいか等しい場合には、ノード１０１−ａからのハローメッセージを廃棄し、ノード１０１−ｂから隣接ノードの情報を含む同報メッセージを受信すると、最小のリンク品質Ｌｍｉｎよりも、前記ハローメッセージのリンク品質Ｌｂが大きい場合には、隣接ノードの集合から最小のリンク品質Ｌｍｉｎを持つノードを削除し、隣接ノードの集合にノード１０１−ｂを登録する。【選択図】図３
2008042647.tif 000002
【特許請求の範囲】
【請求項１】
自ノードの隣に位置する隣接ノードの集合、隣接ノードを介して到達可能な２ホップ隣接ノードの集合、及び全ての２ホップ先の隣接ノードに対して同報メッセージを転送可能な必要最小限の隣接ノードの組を保持するメモリ手段と、
受信した隣接ノードの情報を含む隣接ノード向け同報メッセージに基づいて前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合を前記メモリ手段に作成し、前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合に基づいて前記隣接ノードの組を前記メモリ手段に作成する管理手段と、
隣接ノードから通知された前記隣接ノードの組に基づいて同報メッセージを再転送する再転送手段とを備え、
自ノードの隣接ノードの情報を含む隣接ノード向け同報メッセージを周期的に送信する、アドホック・ネットワークを構成するノードであって、
前記管理手段は、
前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第１のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、前記隣接ノードの集合中の最小のリンク品質と前記第１のノードからの隣接ノード向け同報メッセージのリンク品質とを比較し、前記最小のリンク品質よりも、前記第１のノードからの隣接ノード向け同報メッセージのリンク品質が小さいか等しい場合には、前記第１のノードからの隣接ノード向け同報メッセージを廃棄し、
前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第２のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、前記隣接ノードの集合中の最小のリンク品質と前記第２のノードからの隣接ノード向け同報メッセージのリンク品質とを比較し、前記最小のリンク品質よりも、前記第２のノードからの隣接ノード向け同報メッセージのリンク品質が大きい場合には、前記隣接ノードの集合から前記最小のリンク品質を持つ第３のノードを削除し、前記隣接ノードの集合に前記第２のノードを登録する
ことを特徴とするアドホック・ネットワークを構成するノード。
【請求項２】
自ノードの隣に位置する隣接ノードの集合、隣接ノードを介して到達可能な２ホップ隣接ノードの集合、及び全ての２ホップ先の隣接ノードに対して同報メッセージを転送可能な必要最小限の隣接ノードの組を保持するメモリ手段と、
受信した隣接ノードの情報を含む隣接ノード向け同報メッセージに基づいて前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合を前記メモリ手段に作成し、前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合に基づいて前記隣接ノードの組を前記メモリ手段に作成する管理手段と、
隣接ノードから通知された前記隣接ノードの組に基づいて同報メッセージを再転送する再転送手段とを備え、
自ノードの隣接ノードの情報を含む隣接ノード向け同報メッセージを周期的に送信する、アドホック・ネットワークを構成するノードであって、
前記管理手段は、
前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第１のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、予め保持する最小の新規ノード数と前記第１のノードの隣接ノードに基づく新規ノード数とを比較し、前記最小の新規ノード数よりも、前記第１のノードの隣接ノードに基づく新規ノード数が小さいか等しい場合には、前記第１のノードからの隣接ノード向け同報メッセージを廃棄し、
前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第２のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、予め保持する最小の新規ノード数と前記第２のノードの隣接ノードに基づく新規ノード数とを比較し、前記最小の新規ノード数よりも、前記第２のノードの隣接ノードに基づく新規ノード数が大きい場合には、前記隣接ノードの集合から前記最小の新規ノード数を持つ第３のノードを削除し、前記隣接ノードの集合に前記第２のノードを登録する
ことを特徴とするアドホック・ネットワークを構成するノード。
【請求項３】
自ノードの無線伝播の到達範囲よりも大きな無線伝播の到達範囲を持つと推定した、あるいは前記管理手段により双方向での隣接ノードとしての認識がなされていないと想定した第４のノードに対して、応答を要求する到達性確認メッセージを通知し、前記第４のノードから到達性確認応答メッセージを受信した後、前記第４のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、前記隣接ノードの集合に前記第４のノードを登録する双方向性確認手段をさらに備えた
ことを特徴とする請求項１又は２記載のアドホック・ネットワークを構成するノード。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数のノードが自律的にネットワークを構成し、ノード間でダイレクトに通信ができない際には、任意のノードを中継ノードとして通信を行うアドホック・ネットワーク（或いはマルチホップ・ネットワーク）・システムにおいて、ネットワーク内のノードに向けてメッセージを同報する際に、自ノードの周辺に位置するノードの持つ情報より、必要最小限の同報メッセージを再転送するノードを求めることにより、効率的に同報メッセージを転送する、アドホック・ネットワークを構成するノードに関するものである。
【背景技術】
【０００２】
近年の無線通信技術の進展と電子機器の小型化及び高度化に伴い、従来のインフラストラクチャ型の通信形態に対して、既存ネットワーク・インフラを利用することなく通信機器間での通信を可能とするアドホック・ネットワークへの関心が高まっている。このアドホック・ネットワークは、従来の固定的なインフラストラクチャ型のネットワークとは異なり、（１）物やデバイス間の通信、（２）膨大な物やデバイスによる自律的なネットワークの構築、（３）既存の通信インフラに依存しないネットワーク構築、（３）手軽な、及び一時的に利用するネットワークの構築といった特徴を持っており、トポロジーの変化に対しても自律的に対応することが可能である。現在、上記の特徴を満たすため、アドホック・ネットワークを形成するための多くのルーティング・プロトコル（アドホック・ルーティング・プロトコル）が提案されている。例えば、ＤＳＲ（Ｄｙｎａｍｉｃ  Ｓｏｕｒｃｅ  Ｒｏｕｔｉｎｇ）（ｄｒａｆｔ−ｉｅｔｆ−ｍａｎｅｔ−ｄｓｒ−１０．ｔｘｔ）、ＡＯＤＶ（Ａｄ  Ｈｏｃ  Ｏｎ  Ｄｅｍａｎｄ  Ｄｉｓｔａｎｃｅ  Ｖｅｃｔｏｒ  Ｒｏｕｔｉｎｇ）（ＲＦＣ３５６１）、ＯＬＳＲ（Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ）  （ＲＦＣ３６２６）等がある。
【０００３】
ＤＳＲやＡＯＤＶは、Ｏｎ−Ｄｅｍａｎｄ型のルーティング・プロトコルであり、通信の要求が生じた際に送信元から送信先までの経路を求め、通信を行うものである。一方、ＯＬＳＲは、Ｐｒｏａｃｔｉｖｅ型のルーティング・プロトコルであり、常時経路情報を交換することによりトポロジー情報を管理し、通信の要求が生じた際に保持する経路情報をもとに通信の開始が可能となっている。
【０００４】
また、近年では、低コストにより構築可能なワイヤレス・センサ・ネットワークに対する関心が高まっている。このワイヤレス・センサ・ネットワークは、センシングやコンピューティング、無線通信の機能を持つセンサ・ノードより成るネットワークであり、モニタリング等を必要とするエリアに任意に配置されるノードにより構成されるアドホック・ネットワークである。なお、ワイヤレス・センサ・ネットワークを構成するセンサ・ノードは、一般にＣＰＵ処理能力やメモリ・リソース、バッテリ容量などに制約を持っており、各種制約の考慮が必要である。
【０００５】
ＤＳＲやＡＯＤＶでは、通信の要求が生じた際に送信元ノードから送信先ノードまでの経路を求めるため、送信先ノードに向けて経路探索要求メッセージをネットワーク内に同報する。この同報メッセージを受信する各ノードは、自ノードが該当メッセージに含まれる送信先ノードでない時には、受信した同報メッセージの持つシーケンス番号と送信元アドレス及び送信先アドレスなどの対をもとに、既に受信した同報メッセージであるかどうかを判断し、最初に受信する同報メッセージについては、全ての受信ノードが再転送を行う。すなわち、全ての受信ノードが再転送を行うため、ノード数の増大やノードが密に存在する場合には、数多くの冗長な同報メッセージがネットワーク内で転送され、無線帯域を浪費するといった問題点があった。
【０００６】
上記問題に対応するため、確率型方法（Ｐｒｏｂａｂｉｌｉｔｙ  Ｂａｓｅｄ  Ｍｅｔｈｏｄｓ）や範囲型方法（Ａｒｅａ  Ｂａｓｅｄ  Ｍｅｔｈｏｄｓ）と呼ばれる効率的な同報メッセージのネットワーク内の転送を実現する手段が提案されている（例えば、非特許文献１参照）。しかし、確率型方法では、各ノードが最初に受信する同報メッセージについて確率的に受信した同報メッセージを再転送する手段であり、ネットワーク内の全てのノードに対して同報メッセージの転送を実現するためには、受信した同報メッセージを再転送するための確率値を、周辺に位置するノード数に応じて最適な値に設定するなどの手段が必要となり、上記確率値の設定如何によっては、同報メッセージがネットワーク内の全てのノードに転送される確率（到達率）の低下が発生するといった問題点があった。
【０００７】
また、範囲型方法では、隣接ノードとの位置関係により同報メッセージを再転送することにより新たに増える無線通信範囲を評価し、受信した同報メッセージの再転送を行う。ここで、新たに増える無線通信範囲の評価に際し、各ノードの持つ無線特性は同一であるという仮定が必要であり、様々なノードが存在する実環境との不一致による到達率の低下が発生するといった問題点があった。
【０００８】
【非特許文献１】Ｓ．Ｎｉ，Ｙ．Ｔｓｅｎｇ，Ｙ．Ｃｈｅｎ，ａｎｄ  Ｊ．Ｓｈｅｕ，“Ｔｈｅ  ｂｒｏａｄｃａｓｔ  ｓｔｏｒｍ  ｐｒｏｂｌｅｍ  ｉｎ  ａ  ｍｏｂｉｌｅ  ａｄ  ｈｏｃ  ｎｅｔｗｏｒｋ，”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ／ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｏｂｉｌｅ  Ｃｏｍｐｕｔｉｎｇ，ｐｐ．１５１−１６２，１９９９
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ＯＬＳＲにおいては、ＭＰＲ（Ｍｕｌｔｉ−Ｐｏｉｎｔ  Ｒｅｌａｙｉｎｇ）として、ハロー（Ｈｅｌｌｏ）メッセージと呼ぶ隣接ノード向け同報メッセージを隣接ノード間でやり取りすることにより得られる隣接ノードの情報、すなわち、隣接ノードや２ホップ隣接ノード（隣接ノードを介して到達可能なノード）より、自ノードが転送する同報メッセージを再転送するノードの組であるＭＰＲ集合を求めることにより、効率的な同報メッセージの転送を実現する手段を規定している。しかし、ＭＰＲ集合を求めるための計算において、隣接ノードや２ホップ隣接ノードに対する情報（隣接ノードの情報）が必要であり、特に各ノードが密に存在するネットワークにおいては、必要となるメモリ量が大きくなるという問題点があった。
【００１０】
また、自ノードで管理していない隣接ノードからのハローメッセージの受信により、新規ノードの参入を検出し、ＭＰＲ集合の再計算を行うため、十分なメモリ容量がなく、自ノードの隣接に位置する全てのノードを管理できない際には、ハローメッセージの受信により頻繁に新規ノードの参入を検出、及びＭＰＲ集合の再計算によるＣＰＵ処理負荷の増大やＭＰＲ集合の再通知による無線帯域の浪費につながるという問題点があった。
【００１１】
さらに、一般に、全てのノードが同じ無線伝播特性を持つとは限らず、無線伝播の到達範囲が小さいノードの存在も考えられ、無線伝播の到達範囲の小さいノードにおいては、隣接ノードがメモリ量等の制約により全ての隣接ノードに対する情報を保持できない際に、該当隣接ノードとの間で双方向リンクを確立できず、十分な数の隣接ノードの情報を確保できないこともあるという問題点があった。
【００１２】
この発明は、上述のような課題を解決するためになされたもので、その目的は、複数のノードが自律的にネットワークを構成するアドホック・ネットワーク（或いはマルチホップ・ネットワーク）・システムにおいて、周期的に通知される隣接ノードの情報をもとに自ノードの周辺に位置する隣接ノードや２ホップ隣接ノードの情報を保持し、保持する情報より同報メッセージを再転送する隣接ノードの組を決定する際に、計算に必要となる情報量を削減することができる、アドホック・ネットワークを構成するノードを得るものである。
【００１３】
また、この発明は、上述のような課題を解決するためになされたもので、その目的は、自ノードで管理可能なノード数を超えて隣接ノードが存在する際に、自ノードで管理していないノードからの同報メッセージ受信による新規ノードの検出による各種処理の頻度を削減することができる、アドホック・ネットワークを構成するノードを得るものである。
【００１４】
さらに、この発明は、上述のような課題を解決するためになされたもので、その目的は、ノード間の無線伝播特性に大きな差がある際に、無線伝播の到達範囲の小さなノードにおいても十分な数の隣接ノードと双方向リンクを確立することができる、アドホック・ネットワークを構成するノードを得るものである。
【課題を解決するための手段】
【００１５】
この発明に係るアドホック・ネットワークを構成するノードは、自ノードの隣に位置する隣接ノードの集合、隣接ノードを介して到達可能な２ホップ隣接ノードの集合、及び全ての２ホップ先の隣接ノードに対して同報メッセージを転送可能な必要最小限の隣接ノードの組を保持するメモリ手段と、受信した隣接ノードの情報を含む隣接ノード向け同報メッセージに基づいて前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合を前記メモリ手段に作成し、前記隣接ノードの集合、及び前記２ホップ隣接ノードの集合に基づいて前記隣接ノードの組を前記メモリ手段に作成する管理手段と、隣接ノードから通知された前記隣接ノードの組に基づいて同報メッセージを再転送する再転送手段とを設け、自ノードの隣接ノードの情報を含む隣接ノード向け同報メッセージを周期的に送信する、アドホック・ネットワークを構成するノードであって、前記管理手段は、前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第１のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、前記隣接ノードの集合中の最小のリンク品質と前記第１のノードからの隣接ノード向け同報メッセージのリンク品質とを比較し、前記最小のリンク品質よりも、前記第１のノードからの同報メッセージのリンク品質が小さいか等しい場合には、前記第１のノードからの隣接ノード向け同報メッセージを廃棄し、前記隣接ノードの集合の予め定められた管理可能なノード数を超えて隣接ノードが存在する状態の場合、隣接する第２のノードから隣接ノードの情報を含む隣接ノード向け同報メッセージを受信すると、前記隣接ノードの集合中の最小のリンク品質と前記第２のノードからの隣接ノード向け同報メッセージのリンク品質とを比較し、前記最小のリンク品質よりも、前記第２のノードからの同報メッセージのリンク品質が大きい場合には、前記隣接ノードの集合から前記最小のリンク品質を持つ第３のノードを削除し、前記隣接ノードの集合に前記第２のノードを登録するものである。
【発明の効果】
【００１６】
この発明に係るアドホック・ネットワークを構成するノードは、周期的に通知される隣接ノードの情報をもとに自ノードの周辺に位置する隣接ノードや２ホップ隣接ノードの情報を保持し、保持する情報より同報メッセージを再転送する隣接ノードの組を決定する際に、計算に必要となる情報量を削減することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
実施の形態１．
この発明の実施の形態１に係るアドホック・ネットワークを構成するノードについて図１から図７までを参照しながら説明する。なお、以降では、各図中、同一符号は同一又は相当部分を示す。
【００１８】
図１は、この発明の実施の形態１に係るアドホック・ネットワークのシステム構成を示す図である。図１において、アドホック・ネットワーク１００は、複数のノード（△印）１０１が無線リンクで接続され、自律的にネットワークを構成している。各ノード１０１は、それぞれ、ハローメッセージを送受信する送受信手段、隣接ノードの情報を管理する管理手段、隣接ノードの情報を記憶するメモリ手段、同報メッセージを再転送する再転送手段、アンテナなどが設けられている。
【００１９】
アドホック・ネットワーク１００を構成するノード１０１は、自ノードのローカルリンク情報として、自ノードの隣接ノードの識別子などをハローメッセージにより周期的に広告している。また、隣接ノードからのハローメッセージの受信により、隣接ノードの情報（隣接ノードの集合ＡＡ、２ホップ隣接ノードの集合ＢＢ、隣接ノードの組ＣＣ）を管理手段により管理している。
【００２０】
最初に、アドホック・ネットワーク１００を構成するノード１０１において、隣接ノードの情報を管理する管理手段と、隣接ノードの組ＣＣに基づきネットワーク内に同報メッセージを効率的に再転送する再転送手段の基本的な動作について説明する。
【００２１】
図２は、この発明の実施の形態１に係るアドホック・ネットワークを構成するノードの同報メッセージの転送例を示す図である。
【００２２】
図２において、ノード１０１−ｓは、送受信手段により、自ノードのローカルリンク情報として、隣接ノードの識別子などを含むハローメッセージと呼ぶ同報メッセージを周期的に送信している。また、隣接ノードからのハローメッセージを受信することにより、自ノードのローカルリンク情報を更新し、管理手段により、自ノードの隣に位置する隣接ノードの集合ＡＡや隣接ノードを介して到達可能な２ホップ隣接ノードの集合ＢＢをメモリ手段に作成する。そして、管理手段により、隣接ノードの集合ＡＡや２ホップ隣接ノードの集合ＢＢをもとに、全ての２ホップ先の隣接ノードに対してハローメッセージを転送可能な必要最小限の隣接ノードの組ＣＣ（ＭＰＲ集合）をメモリ手段に作成する。この隣接ノードの組ＣＣをハローメッセージにより隣接ノードに通知することにより、隣接ノードの組ＣＣに含まれる隣接ノードのみが、ノード１０１−ｓより転送される同報メッセージを再転送手段により再転送する。
【００２３】
図３は、図１のアドホック・ネットワークの一部を取り出したシステム構成を示す図である。また、図４は、図３のアドホック・ネットワークを構成するノードの隣接ノードの集合及び２ホップ隣接ノードの集合の構成を示す図である。
【００２４】
図３において、ノード１０１−ｓは、隣接ノードであるノード１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄよりハローメッセージを受信すると、管理手段により、隣接ノードの集合ＡＡ｛１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄ｝及び２ホップ隣接ノードの集合ＢＢ｛１０１−ｅ、１０１−ｆ、１０１−ｇ、１０１−ｈ、１０１−ｉ｝をメモリ手段に作成する。そして、管理手段によって、隣接ノードの集合ＡＡ及び２ホップ隣接ノードの集合ＢＢから、隣接ノードの組ＣＣ｛１０１−ａ、１０１−ｃ｝を求め、ハローメッセージによりこの隣接ノードの組ＣＣを隣接ノード１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄに通知する。
【００２５】
ここで、ノード１０１−ｓの管理手段は、隣接ノードの組ＣＣ（ＭＰＲ集合）の計算のため、図４に示すように、隣接ノード１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄのローカルリンク情報である、各隣接ノードが持つ隣接ノードの情報である隣接ノードのリストも併せて管理する必要がある。
【００２６】
図４（ａ）に示すように、ノード１０１−ｓの隣接ノードの集合ＡＡを構成する隣接ノード毎に、図３の例では、隣接ノード１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄ毎に、それぞれ、「ノードの識別子」と、片方向通信可や、双方向通信可などの「状態」と、「優先度」と、「その他」と、「隣接ノードの情報」が格納される。また、「隣接ノードの情報」には、隣接ノードの「ノードの識別子」が格納される。なお、「その他」欄には、後述するように、計算された当該隣接ノードのリンク品質が格納される。
【００２７】
図４（ｂ）に示すように、ノード１０１−ｓの２ホップ隣接ノードの集合ＢＢを構成する隣接ノード毎に、図３の例では、隣接ノード１０１−ｅ、１０１−ｆ、１０１−ｇ、１０１−ｈ、１０１−ｉ毎に、それぞれ、「ノードの識別子」と、「余命時間」と、「その他」と、「隣接ノードの情報」が格納される。また、「隣接ノードの情報」には、当該隣接ノードへ到達可能な隣接ノードの「ノードの識別子」が格納される。
【００２８】
次に、この発明の実施の形態１に係るアドホック・ネットワークを構成するノードにおいて隣接ノードの情報を効率的に管理する管理手段について説明する。図５は、この発明の実施の形態１に係るアドホック・ネットワークを構成するノードの管理手段の動作を示すフローチャートである。
【００２９】
例えば、ノード１０１−ｓの管理手段は、予め設定した隣接ノードの集合ＡＡの管理可能なノード数に余裕がある場合に、隣接ノード或いは２ホップ隣接ノードが存在するときには、隣接するノードからハローメッセージを受信する際に、ＬＱＩ（Ｌｉｎｋ  Ｑｕａｌｉｔｙ  Ｉｎｄｉｃａｔｉｏｎ）や、ＲＳＳＩ（Ｒｅｃｅｉｖｅｄ  Ｓｉｇｎａｌ  Ｓｔｒｅｎｇｔｈ  Ｉｎｄｉｃａｔｏｒ）と呼ばれる値である、リンク品質を計算して当該隣接ノードの隣接ノードの集合ＡＡの「その他」欄に格納し、このリンク品質が規定の範囲内にある隣接ノードに対して、リンク品質の大きい順に順次、隣接ノードの集合ＡＡに登録することにより、管理可能な最大限の隣接ノードを保持する。
【００３０】
また、ノード１０１−ｓの管理手段は、管理可能なノード数を超えて隣接ノードが存在する状態時には、受信したハローメッセージに対するリンク品質を計算し、このリンク品質が、隣接ノードの集合ＡＡで保持する隣接ノードのリンク品質の中で最小のリンク品質よりも小さいか等しい場合には、受信したハローメッセージを廃棄することにより、頻繁な隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を回避する。
【００３１】
なお、従来のＭＰＲでは、隣接ノードの集合に登録されていないノードからハローメッセージを受信する際には、新規ノードがアドホック・ネットワークに参入したとしてＭＰＲ集合の再計算を行う。
【００３２】
図５のステップ１０、１２、１４、１６において、ノード１０１−ｓの管理手段は、隣接するノード１０１−ａからハローメッセージ（リンク品質：Ｌａ）を受信すると、新規の隣接ノードの追加管理が可能な状態の場合、隣接ノードの集合ＡＡや２ホップ隣接ノードの集合ＢＢを更新する。このとき、隣接ノードの集合ＡＡに登録した隣接ノード１０１−ａの「その他」欄には、計算したリンク品質Ｌａを格納する。また、隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を行う。
【００３３】
ステップ１８において、隣接ノードの集合ＡＡの管理可能なノード数を超えて隣接ノードが存在する状態となり、ノード１０１−ｓの管理手段は、隣接ノードの集合ＡＡ｛１０１−ａ、１０１−ｃ、・・・｝を管理している。ここで、管理している隣接ノードの集合ＡＡの隣接ノードのリンク品質Ｌａ、Ｌｃ、・・・の中で最小のリンク品質がＬｍｉｎであるとする。
【００３４】
ステップ２０、２２、２４、２６において、ノード１０１−ｓの管理手段は、隣接するノード１０１−ｄからハローメッセージ（リンク品質：Ｌｄ）を受信すると、管理可能なノード数を超えて隣接ノードが存在する状態の場合、最小のリンク品質Ｌｍｉｎと、ノード１０１−ｄからのハローメッセージの計算したリンク品質Ｌｄを比較する。最小のリンク品質Ｌｍｉｎよりも、今回のハローメッセージのリンク品質Ｌｄが小さいか等しい場合（Ｌｍｉｎ≧Ｌｄ）には、ノード１０１−ｄからの受信ハローメッセージを廃棄する。
【００３５】
ステップ３０、３２、３４、３６において、ノード１０１−ｓの管理手段は、隣接するノード１０１−ｂからハローメッセージ（リンク品質：Ｌｂ）を受信すると、管理可能なノード数を超えて隣接ノードが存在する状態の場合、最小のリンク品質Ｌｍｉｎと、ノード１０１−ｂからのハローメッセージの計算したリンク品質Ｌｂを比較する。最小のリンク品質Ｌｍｉｎよりも、今回のハローメッセージのリンク品質Ｌｂが大きい場合（Ｌｍｉｎ＜Ｌｂ）には、ノード１０１−ｂからの受信ハローメッセージを処理する。隣接ノードの集合ＡＡや２ホップ隣接ノードの集合ＢＢを更新する。また、隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を行う。例えば、リンク品質Ｌｃが最小のリンク品質Ｌｍｉｎであった場合、リンク品質Ｌｂ＞リンク品質Ｌｃより、隣接ノードの集合ＡＡから隣接ノード１０１−ｃを削除し、隣接ノード１０１−ｂを隣接ノードの集合ＡＡに追加登録する。
【００３６】
また、ＬＱＩやＲＳＳＩと呼ばれるリンク品質ではなく、自ノードが持つ隣接ノードに対して、任意の隣接ノードが持つ隣接ノードのうち重複しない隣接ノードの数である新規ノード数をもとに、隣接ノードの集合ＡＡに登録する隣接ノードを選択することも可能である。
【００３７】
図６は、図１のアドホック・ネットワークの一部を取り出したシステム構成を示す図である。また、図７は、図６のアドホック・ネットワークを構成するノードの隣接ノードの集合及び２ホップ隣接ノードの集合の構成を示す図である。
【００３８】
図６において、ノード１０１−ｘは、隣接ノードとして｛１０１−ｘ＿１、・・・、１０１−ｘ＿ｉ｝を保持し、ノード１０１−ｙは、隣接ノードとして｛１０１−ｙ＿１、・・・、１０１−ｙ＿ｊ｝を保持し、ノード１０１−ｚは、隣接ノードとして｛１０１−ｚ＿１、・・・、１０１−ｚ＿ｋ｝を保持している。
【００３９】
図７（ａ）に示すように、ノード１０１−ｘの隣接ノードの集合ＡＡを構成する隣接ノード毎に、図６の例では、隣接ノード１０１−ｚ、・・・毎に、それぞれ、「ノードの識別子」と、片方向通信可や、双方向通信可などの「状態」と、「優先度」と、「その他」と、「隣接ノードの情報」が格納される。また、「隣接ノードの情報」には、隣接ノードの「ノードの識別子」が格納される。なお、「その他」欄には、後述するように、計算された当該隣接ノードの新規ノード数が格納される。
【００４０】
図７（ｂ）に示すように、ノード１０１−ｘの２ホップ隣接ノードの集合ＢＢを構成する隣接ノード毎に、図６の例では、隣接ノード１０１−ｚ＿１、・・・毎に、それぞれ、「ノードの識別子」と、「余命時間」と、「その他」と、「隣接ノードの情報」が格納される。また、「隣接ノードの情報」には、当該隣接ノードへ到達可能な隣接ノードの「ノードの識別子」が格納される。
【００４１】
図７（ｃ）に示すように、ノード１０１−ｘの隣接ノードの集合ＡＡに登録されない隣接ノードのリストが別途格納される。
【００４２】
ノード１０１−ｘの隣接ノード｛１０１−ｘ＿１、・・・、１０１−ｘ＿ｉ｝に対して、ノード１０１−ｘの隣接ノード１０１−ｙの隣接ノード｛１０１−ｙ＿１、・・・、１０１−ｙ＿ｊ｝は、重複しないＭ個の異なるノード、すなわち新規ノードがＭ個存在しているとする。また、ノード１０１−ｘの隣接ノード｛１０１−ｘ＿１、・・・、１０１−ｘ＿ｉ｝に対して、ノード１０１−ｘの隣接ノード１０１−ｚの隣接ノード｛１０１−ｚ＿１、・・・、１０１−ｚ＿ｋ｝は、重複しないＮ個（Ｍ＜Ｎ）の異なるノード、すなわち新規ノードがＮ個存在しているとする。
【００４３】
この時、ノード１０１−ｘにおいて、管理可能なノード数を超えて隣接ノードが存在する際には、図７（ａ）及び（ｂ）に示すように、管理手段は、該当ノード１０１−ｘに対して新規ノード数が大きい隣接ノード１０１−ｚ（新規ノード数＝Ｎ個）の情報を優先して隣接ノードの集合ＡＡ、２ホップ隣接ノードの集合ＢＢに登録する。このとき、隣接ノードの集合ＡＡに登録した隣接ノード１０１−ｚの「その他」欄には、計算した新規ノード数を格納する。また、登録できない隣接ノード１０１−ｙ（新規ノード数＝Ｍ個）については、図７（ｃ）に示すように、隣接ノード１０１−ｙの識別子のみを隣接ノードのリストとしてメモリ手段に保持する。
【００４４】
ここで、図６の例を、図３の例に置き換えて説明する。図６のノード１０１−ｘ、１０１−ｙ、１０１−ｚは、図３のノード１０１−ｓ、１０１−ａ、１０１−ｂにそれぞれ相当するとする。従って、ノード１０１−ｘの隣接ノード｛１０１−ｘ＿１、・・・、１０１−ｘ＿ｉ｝には、ノード１０１−ｓの隣接ノード｛１０１−ａ、１０１−ｂ、１０１−ｃ、１０１−ｄ｝が対応する。ノード１０１−ｙの隣接ノード｛１０１−ｙ＿１、・・・、１０１−ｙ＿ｊ｝には、ノード１０１−ａの隣接ノード｛１０１−ｓ、１０１−ｂ、１０１−ｅ、１０１−ｆ｝が対応する。ノード１０１−ｚの隣接ノード｛１０１−ｚ＿１、・・・、１０１−ｚ＿ｋ｝には、ノード１０１−ｂの隣接ノード｛１０１−ｓ、１０１−ａ、１０１−ｃ、１０１−ｆ、１０１−ｇ、１０１−ｈ｝が対応する。
【００４５】
説明を簡単にするために、この段落では１０１−を省略する。ノードｓの隣接ノード｛ａ、ｂ、ｃ、ｄ｝に対して、ノードｓの隣接ノードａの隣接ノード｛ｓ、ｂ、ｅ、ｆ｝は、ノードｂが重複し、ノードｅ、ｆが重複しない異なるノード、すなわち新規ノードが２個存在していることになる。また、ノードｓの隣接ノード｛ａ、ｂ、ｃ、ｄ｝に対して、ノードｓの隣接ノードｂの隣接ノード｛ｓ、ａ、ｃ、ｆ、ｇ、ｈ｝は、ノードａ、ｃが重複し、ノードｆ、ｇ、ｈが重複しない異なるノード、すなわち新規ノードが３個存在していることになる。この時、ノードｓにおいて、管理可能なノード数を超えて隣接ノードが存在する際には、管理手段は、該当ノードｓに対して新規ノード数が大きい隣接ノードｂ（新規ノード数＝３個）の情報を優先して隣接ノードの集合ＡＡ、２ホップ隣接ノードの集合ＢＢに登録し、登録できない隣接ノードａ（新規ノード数＝３個）については、隣接ノードａの識別子のみを隣接ノードのリストとしてメモリ手段に保持する。なお、新規ノードの計算において、自ノード(ノードｓ)は含まない。
【００４６】
さらに、ノード１０１−ｘの管理手段は、管理する隣接ノードの持つ情報の中で、最小の新規ノード数（Ｍｉｎｉｍｕｎ＿ＮｅｗＮｏｄｅＮｕｍｂｅｒ）を別途、メモリ手段に保持する。
【００４７】
ノード１０１−ｘの管理手段は、管理可能なノード数を超えて隣接ノードが存在する状態時に、受信したハローメッセージの送信元の隣接ノードによる新規ノード数を計算し、この新規ノード数が、保持する最小の新規ノード数よりも小さいか等しい場合には、受信したハローメッセージを廃棄することにより、頻繁な隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を回避する。
【００４８】
また、ノード１０１−ｘの管理手段は、管理可能なノード数を超えて隣接ノードが存在する状態時に、受信したハローメッセージの送信元の隣接ノードに基づく新規ノード数を計算し、この新規ノード数が、保持する最小の新規ノード数よりも大きい場合には、隣接ノードの集合ＡＡから最小の新規ノード数を持つ隣接ノードを削除し、今回のハローメッセージの送信元である隣接ノードを隣接ノードの集合ＡＡに追加登録する。また、最小の新規ノード数（Ｍｉｎｉｍｕｎ＿ＮｅｗＮｏｄｅＮｕｍｂｅｒ）を更新する。
【００４９】
以上のように、アドホック・ネットワークを構成するノードが、周期的に通知される隣接ノードからのハローメッセージをもとに、隣接ノードに関する情報を保持し、同報メッセージの再転送を期待する隣接ノードを求める際に、ＬＱＩやＲＳＳＩと呼ばれるリンク品質や、ハローメッセージの送信元の隣接ノードに基づく新規ノード数をもとに、保持する隣接ノードの情報を制限することにより、各ノードで保持する情報量の削減を図ることが可能となる。
【００５０】
また、管理可能なノード数を超えて隣接ノードが存在する状態時に、受信したハローメッセージのＬＱＩやＲＳＳＩと呼ばれるリンク品質や、ハローメッセージの送信元の隣接ノードに基づく新規ノード数をチェックし、必要に応じて受信したハローメッセージを廃棄することにより、頻繁な隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を回避することができ、ＣＰＵ処理負荷の増大や再計算の結果として生じる隣接ノードの組ＣＣ（ＭＰＲ集合）の再通知による無線帯域の浪費の削減を図ることが可能となる。なお、ここでは、ＭＰＲに基づいて説明したが、他のメカニズムについても可能である。
【００５１】
以上のように、この発明の実施の形態１に係るアドホック・ネットワークにおける同報メッセージの転送手法によれば、複数のノードが自律的にネットワークを構成するアドホック・ネットワーク（或いはマルチホップ・ネットワーク）・システムにおいて、ネットワークを構成するノードが、周期的に通知される隣接ノードの情報をもとに自ノードの周辺に位置する隣接ノードや２ホップ隣接ノードの情報を保持し、保持する情報より同報メッセージを再転送する隣接ノードの組を決定する際に、リンク品質や新規ノード数をもとに該当ノードにおいて保持する隣接ノードの情報を選択することにより、計算に必要となる情報量の削減が可能となり、効率的なシステム構築が図れるという効果がある。
【００５２】
また、アドホック・ネットワーク、或いはマルチホップ・ネットワークを構成するノードが、自ノードで管理可能なノード数を超えて隣接ノードが存在する際に、リンク品質や新規ノード数を保持することにより、自ノードで管理していないノードからのハローメッセージ受信時に保持する該当情報との比較により、新規ノードの検出による各種処理の頻度の削減が可能となり、効率的なシステム構築が図れるという効果がある。
【００５３】
実施の形態２．
この発明の実施の形態２に係るアドホック・ネットワークを構成するノードについて図８を参照しながら説明する。
【００５４】
上記の実施の形態１では、管理可能なノード数を超えて隣接ノードが存在する状態時において、各ノードで保持する情報量の削減や頻繁な隣接ノードの組ＣＣ（ＭＰＲ集合）の再計算を回避する手法について説明したが、この実施の形態２では、隣接ノードにおいて管理する情報を制限することにより、双方向リンクを確立できないノードが、任意の隣接ノードとの接続性を確認し、必要十分な隣接ノードの情報を保持することができるものである。
【００５５】
図８は、この発明の実施の形態２に係るアドホック・ネットワークのシステム構成を示す図である。図８において、アドホック・ネットワーク１００は、複数のノード（△印）１０２が無線リンクで接続され、自律的にネットワークを構成している。各ノード１０２は、それぞれ、ハローメッセージを送受信する送受信手段、隣接ノードの情報を管理する管理手段、隣接ノードの情報を記憶するメモリ手段、同報メッセージを再転送する再転送手段、アンテナ、さらに、隣接ノードとのリンクの双方向性を確認する双方向性確認手段などが設けられている。
【００５６】
上記の実施の形態１では、無線伝播の到達範囲が同じノード１０１により構成されるアドホック・ネットワーク１００について説明したが、この図８は、無線伝播の到達範囲が大きく異なるノード１０２により構成されるアドホック・ネットワーク１００を示す図である。図８において、ノード１０２−ａは、無線伝播の到達範囲が大きなノードであり、ノード１０２−ｂ及び１０２−ｃは、無線伝播の到達範囲が小さなノードである。特に、ノード１０２−ｂは、ノード１０２−ａの無線伝播の到達範囲に完全に含まれている例である。
【００５７】
ノード１０２−ａは、周辺に多数のノードが存在しており、すなわち、ノード１０２−ａで管理可能なノード数を超えて、ノードが存在しており、上記の実施の形態１で説明した、リンク品質や新規ノード数をもとに、例えば、隣接ノードの集合ＡＡを｛１０２−ｃ、１０２−ｘ、１０２−ｙ｝として、隣接ノードの情報を保持している。
【００５８】
一方、ノード１０２−ｂは、ノード１０２−ａからのハローメッセージに自ノード、すなわちノード１０２−ｂの情報が含まれていないため、ノード１０２−ａとの間で双方向リンクを確立できず、ノード１０２−ａを除く他のノードより隣接ノードの集合ＡＡ、例えば、｛１０２−ｊ、１０２−ｋ｝を保持する。
【００５９】
ここで、ノード１０２−ｂの双方向性確認手段は、自ノードの隣に位置するノード数よりも明らかに多くの隣接ノードを保持するノードについては、自ノードの無線伝播の到達範囲よりも大きな到達範囲を持つと推定し、該当ノードに対して応答を要求する到達性確認メッセージを通知する。例えば、ノード１０２−ａからのハローメッセージに自ノード（ノード１０２−ａ）の送信電力が含まれており、ノード１０２−ｂは、自ノード（ノード１０２−ｂ）の送信電力と比較する。ノード１０２−ａの送信電力＞ノード１０２−ｂの送信電力の場合には、ノード１０２−ｂは、自ノードの無線伝播の到達範囲よりも大きな無線伝播の到達範囲をノード１０２−ａが持つと推定する。
【００６０】
すなわち、ノード１０２−ｂの双方向性確認手段は、ノード１０２−ａに対して到達性確認メッセージを通知する。そして、応答を要求する到達性確認メッセージを受信するノード１０２−ａは、到達性確認応答メッセージで応答し、当該到達性確認応答メッセージを受信するノード１０２−ｂは、以降に受信するノード１０２−ａからのハローメッセージをもとに、ノード１０２−ａを隣接ノードの集合ＡＡに登録する。
【００６１】
なお、ノード１０２−ｃについては、ノード１０２−ｃの無線伝播の到達範囲内にノード１０２−ａが存在しないため、ノード１０２−ｃは、ノード１０２−ａに対する到達性確認メッセージの応答を受信することがないため、ノード１０２−ａをノード１０２−ｃの隣接ノードの集合ＡＡに保持することはない。
【００６２】
以上のように、アドホック・ネットワーク１００を構成するノード１０２が、周期的に通知される隣接ノードからのハローメッセージをもとに、隣接ノードに関する情報を保持し、ハローメッセージの再転送を期待する隣接ノードを求める際に、任意のノードが特定のノードに対して到達性確認を行い、双方向リンクの存在を確認することにより、無線伝播の到達範囲の小さなノード１０２においても十分な数の隣接ノードと双方向リンクを確立することが可能となる。
【００６３】
なお、無線伝播の到達範囲が大きく異なるノードに対する双方向性確認手段の例を示したが、管理可能なノード数を超えてノードが存在しており、上記の実施の形態１で説明した手法により、各ノードが隣接ノードの情報を保持することにより、隣接ノード間で十分な双方向通信可能な隣接ノードを認識できないときも同様である。
【００６４】
複数のノード１０２が自律的にネットワークを構成するアドホック・ネットワーク（或いはマルチホップ・ネットワーク）・システムにおいて、ネットワークを構成するノード間の無線伝播特性に大きな差がある際に、無線伝播の到達範囲の小さなノードにおいても十分な数の隣接ノードと双方向リンクを確立することが可能となり、効率的なシステム構築が図れるという効果がある。
【図面の簡単な説明】
【００６５】
【図１】この発明の実施の形態１に係るアドホック・ネットワークのシステム構成を示す図である。
【図２】この発明の実施の形態１に係るアドホック・ネットワークを構成するノードのハローメッセージの転送例を示す図である。
【図３】図１のアドホック・ネットワークの一部を取り出したシステム構成を示す図である。
【図４】図３のアドホック・ネットワークを構成するノードの隣接ノードの集合及び２ホップ隣接ノードの集合の構成を示す図である。
【図５】この発明の実施の形態１に係るアドホック・ネットワークを構成するノードの管理手段の動作を示すフローチャートである。
【図６】図１のアドホック・ネットワークの一部を取り出したシステム構成を示す図である。
【図７】図６のアドホック・ネットワークを構成するノードの隣接ノードの集合及び２ホップ隣接ノードの集合の構成を示す図である。
【図８】この発明の実施の形態２に係るアドホック・ネットワークのシステム構成を示す図である。
【符号の説明】
【００６６】
１００  アドホック・ネットワーク、１０１  ノード、１０２  ノード。
【図１】
2008042647.tif 000003
【図２】
2008042647.tif 000004
【図３】
2008042647.tif 000005
【図４】
2008042647.tif 000006
【図５】
2008042647.tif 000007
【図６】
2008042647.tif 000008
【図７】
2008042647.tif 000009
【図８】
2008042647.tif 000010