(57)【要約】      （修正有）【課題】ノード間通信の中継数を少なくしてスループットを大きくすることができ、パケット転送遅延を可能な限り小さくすることができるアドホックネットワーク構成方法及びノード装置を提供すること。【解決手段】互いに近傍に配置された複数のノード装置の中からクラスタヘッドを選択する際において、より多くの隣接ノードを持つノード装置がより高い確率でクラスタヘッドに選択されるようにすると同時に、既に選択されたクラスタヘッドの隣接ノード装置の中から、当該クラスタヘッドと共通する隣接ノードをより少なく持つノード装置がより高い確率でクラスタヘッドに選択されるようにする。また、あるノードから直接通信できない２ホップ先の近傍に既に存在するクラスタヘッドを含む２つのクラスタヘッドの共通隣接ノードと共通する隣接ノードをより少なく持つノード装置がより高い確率でクラスタヘッドに選択するようにする。【選択図】図１
2008312059.tif 000002
【特許請求の範囲】
【請求項１】
無線通信を行うノード装置が、他のノード装置の送信パケットを中継転送しあうことによって、互いに直接無線通信することができない離れたノード装置間の通信を可能とするアドホックネットワーク構成方法であって、
互いに直接無線通信が可能な範囲内に存在するノード装置によってクラスタを構成し、１つのノード装置は、１つのクラスタに属するようにし、１つのクラスタに属するノード装置の中から１つのクラスタヘッドを選択し、同じクラスタに属するそれ以外のノード装置をクラスタメンバーノードとし、
前記クラスタヘッドは、近傍の他クラスタヘッドとの直接通信によるアドホック通信によって相互の送信パケットを中継転送し、
前記クラスタメンバーノードは、他のノード装置との通信に際して、自身の属するクラスタのクラスタヘッドを介して送受信を行うアドホックネットワーク構成方法。
【請求項２】
無線通信を行うノード装置が、他のノード装置の送信パケットを中継転送しあうことによって、互いに直接無線通信することができない離れたノード装置間の通信を可能とするアドホックネットワーク構成方法であって、
互いに直接無線通信が可能な範囲内に存在するノード装置によってクラスタを構成し、１つのノード装置は、１つのクラスタに属するようにし、１つのクラスタに属するノード装置の中から１つのクラスタヘッドを選択し、同じクラスタに属するそれ以外のノード装置をクラスタメンバーノードとし、
前記クラスタヘッドは、近傍の他クラスタヘッドとのアドホック通信によって相互の送信パケットを中継転送し、
前記クラスタメンバーノードは、自身と同一のクラスタに属するノード装置以外のノード装置との通信に際して、自身の属するクラスタのクラスタヘッドを介して送受信を行い、自身と同一のクラスタに属するノード装置との通信に際しては、該当ノード装置と直接通信するアドホックネットワーク構成方法。
【請求項３】
前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内にクラスタヘッドが存在しない場合には、自身の無線通信可能エリア内に存在する隣接ノードの数がより多いノード装置がより高い確率でクラスタヘッドとなるようにした請求項１又は請求項２に記載のアドホックネットワーク構成方法。
【請求項４】
前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に１つ以上のクラスタヘッドが存在する場合には、無線通信可能エリア内の自身以外のクラスタヘッドについて各クラスタヘッドの隣接ノード集合と自身の隣接ノードとの積集合を取ったものの和集合がより少ないノード装置が、より高い確率でクラスタヘッドとなるようにした請求項１又は請求項２に記載のアドホックネットワーク構成方法。
【請求項５】
前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に１つ以上のクラスタヘッドが存在する場合には、無線通信可能エリア内の自身以外のクラスタヘッドのそれぞれについて該当クラスタヘッドの隣接ノード集合と該当クラスタヘッドの無線通信可能エリア内にありかつ自分の無線通信可能エリア内に無いクラスタヘッドの隣接ノード集合との積集合と、自身の隣接ノードとの積集合を取ったものの和集合がより少ないノード装置が、より高い確率でクラスタヘッドとなるようにした請求項１又は請求項４に記載のアドホックネットワーク構成方法。
【請求項６】
前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に予め定めた個数以上のクラスタヘッドが存在する場合には、前記ノード装置が前記クラスタヘッドに選択されず、クラスタメンバーノードとして機能し、無線通信可能エリア内に存在するクラスタヘッドのいずれか１つのクラスタに属するようにした請求項１乃至請求項５のいずれかに記載のアドホックネットワーク構成方法。
【請求項７】
前記クラスタメンバーノードが属するクラスタを選択する際に、各クラスタメンバーノードは、自身の無線通信可能エリア内において最初にクラスタヘッドとなったノード装置のクラスタに属するようにした請求項１乃至請求項６のいずれかに記載のアドホックネットワーク構成方法。
【請求項８】
前記請求項１乃至請求項７のいずれかに記載のアドホックネットワーク構成方法が適用されるノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックネットワーク構成方法及びノード装置に関し、詳細には、無線通信を行うノード装置が、他のノード装置の送信パケットを中継転送しあうことによって、互いに直接無線通信することができない離れたノード装置間の通信を可能とするアドホックネットワーク構成方法及びノード装置に関する。
【背景技術】
【０００２】
無線通信を利用してノード間でパケットの交換を行うネットワークにおいて、ノード間の接続形態が固定されておらず、伝播環境その他の条件によって適応的にネットワーク構成の変化するネットワークはアドホックネットワークと呼ばれる。
【０００３】
図７は、従来のアドホックネットワーク構成方法によるネットワーク構成例を示す図である。図７において、無線アドホックネットワークは、クラスタヘッド１１、ゲートウェイノード１２、クラスタメンバノード１３を有し、ノード間の接続形態は固定されていない。
【０００４】
図７に示すように、アドホックネットワーク構成方法では、無線通信リンクを介して互いに通信可能なノード装置のグループ１４の中から、１つのクラスタヘッド１１を選択するように構成されており、隣接するクラスタのクラスタヘッド同士が直接通信することができないため、他のクラスタと隣接するクラスタエッジ部分にゲートウェイノード１２を設けて、クラスタ間をまたがる通信はゲートウェイノード１２を介して行う必要がある（例えば、非特許文献１参照）。
【非特許文献１】Tzu-Chiang Chiang, Po-Yi Wu, Yueh-Min Huang 「A limited Flooding Scheme for Mobile Ad Hoc Networks」IEEE Transactions on Applied Super connectivity, Volume 11, Issue 1, Part 3, page 3788 - 3791, March 2001
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、このような従来のアドホックネットワーク構成方法にあっては、以下に述べる中継動作を中継クラスタの数分繰り返す必要があり、これら中継動作によるスループットの低下やパケット転送遅延の増加が発生するという問題があった。上記中継動作は、（１）異なるクラスタに属するノード装置間での通信に際して、送信元ノード〜送信元ノードが属するクラスタヘッド間の中継動作、（２）宛先ノードが属するクラスタのゲートウェイノード〜宛先ノードが属するクラスタのクラスタヘッド〜宛先ノードという中継動作、及び（３）送信元ノードが属するクラスタと宛先ノードが属するクラスタの間に位置する中継クラスタにおけるゲートウェイノード及びクラスタヘッドによる中継動作である。
【０００６】
本発明は、上記に鑑みてなされたものであり、ノード間通信の中継数を少なくしてスループットを大きくすることができ、パケット転送遅延を可能な限り小さくすることができるアドホックネットワーク構成方法及びノード装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明のアドホックネットワーク構成方法は、無線通信を行うノード装置が、他のノード装置の送信パケットを中継転送しあうことによって、互いに直接無線通信することができない離れたノード装置間の通信を可能とするアドホックネットワーク構成方法であって、互いに直接無線通信が可能な範囲内に存在するノード装置によってクラスタを構成し、１つのノード装置は、１つのクラスタに属するようにし、１つのクラスタに属するノード装置の中から１つのクラスタヘッドを選択し、同じクラスタに属するそれ以外のノード装置をクラスタメンバーノードとし、前記クラスタヘッドは、近傍の他クラスタヘッドとの直接通信によるアドホック通信によって相互の送信パケットを中継転送し、前記クラスタメンバーノードは、他のノード装置との通信に際して、自身の属するクラスタのクラスタヘッドを介して送受信を行う。
【０００８】
この方法により、互いに隣接するクラスタ間をまたがる通信において、当該クラスタのクラスタヘッド同士が直接通信することが可能となり、異なるクラスタに属するノード間の通信に際してクラスタ間でのゲートウェイノードを介した通信を不要とし、中継転送数の増加によるスループットの低下やパケット転送遅延の増加を抑制することができる。
【０００９】
本発明のアドホックネットワーク構成方法は、無線通信を行うノード装置が、他のノード装置の送信パケットを中継転送しあうことによって、互いに直接無線通信することができない離れたノード装置間の通信を可能とするアドホックネットワーク構成方法であって、互いに直接無線通信が可能な範囲内に存在するノード装置によってクラスタを構成し、１つのノード装置は、１つのクラスタに属するようにし、１つのクラスタに属するノード装置の中から１つのクラスタヘッドを選択し、同じクラスタに属するそれ以外のノード装置をクラスタメンバーノードとし、前記クラスタヘッドは、近傍の他クラスタヘッドとのアドホック通信によって相互の送信パケットを中継転送し、前記クラスタメンバーノードは、自身と同一のクラスタに属するノード装置以外のノード装置との通信に際して、自身の属するクラスタのクラスタヘッドを介して送受信を行い、自身と同一のクラスタに属するノード装置との通信に際しては、該当ノード装置と直接通信する。
【００１０】
この方法により、前項に示した作用に加えてさらに同一のクラスタに属するノード装置間の通信に際しては、当該ノード装置同士がクラスタヘッドを介することなく直接通信することが可能となり中継転送数の増加によるスループットの低下やパケット転送遅延の増加を抑制することができる。
【００１１】
本発明のアドホックネットワーク構成方法は、前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内にクラスタヘッドが存在しない場合には、自身の無線通信可能エリア内に存在する隣接ノードの数がより多いノード装置がより高い確率でクラスタヘッドとなるようにした。
【００１２】
この方法により、複数のノード装置の中からクラスタヘッドを選択する際に、より隣接ノードが多いノード装置をクラスタヘッドとして選択することにより、できるだけ少ない数のクラスタヘッドによってノード装置が配置されたエリア全体をカバーすることが可能となる。これによりノード装置間通信における中継転送数を少なくすることが可能となりスループットの低下やパケット転送遅延の増加を抑制することができる。
【００１３】
本発明のアドホックネットワーク構成方法は、前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に１つ以上のクラスタヘッドが存在する場合には、無線通信可能エリア内の自身以外のクラスタヘッドについて各クラスタヘッドの隣接ノード集合と自身の隣接ノードとの積集合を取ったものの和集合がより少ないノード装置が、より高い確率でクラスタヘッドとなるようにした。
【００１４】
この方法により、既にクラスタヘッドとして選択されたノード装置の周辺に位置する複数のノード装置の中から前記クラスタヘッドに隣接するクラスタヘッドを選択する際において、周辺のクラスタヘッドと直接通信可能でありながら、かつ周辺のクラスタヘッドからできるだけ遠くに位置するノード装置をクラスタヘッドとして選択することができる。これによりできるだけ少ない数のクラスタヘッドによってノード装置が配置されたエリア全体をカバーすることが可能となる。これによりノード装置間通信における中継転送数を少なくすることが可能となりスループットの低下やパケット転送遅延の増加を抑制することができる。
【００１５】
本発明のアドホックネットワーク構成方法は、前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に１つ以上のクラスタヘッドが存在する場合には、無線通信可能エリア内の自身以外のクラスタヘッドのそれぞれについて該当クラスタヘッドの隣接ノード集合と該当クラスタヘッドの無線通信可能エリア内にありかつ自分の無線通信可能エリア内に無いクラスタヘッドの隣接ノード集合との積集合と、自身の隣接ノードとの積集合を取ったものの和集合がより少ないノード装置が、より高い確率でクラスタヘッドとなるようにした。
【００１６】
この方法により、既にクラスタヘッドとして選択されたノード装置の周辺に位置する複数のノード装置の中から前記クラスタヘッドに隣接するクラスタヘッドを選択する際において、周辺のクラスタヘッドと直接通信可能でありながら、かつ周辺のクラスタヘッドからできるだけ遠くに位置するノード装置をクラスタヘッドとして選択することができる。これによりできるだけ少ない数のクラスタヘッドによってノード装置が配置されたエリア全体をカバーすることが可能となる。これによりノード装置間通信における中継転送数を少なくすることが可能となりスループットの低下やパケット転送遅延の増加を抑制することができる。
【００１７】
本発明のアドホックネットワーク構成方法は、前記クラスタヘッドの選択では、ノード装置の無線通信可能エリア内に予め定めた個数以上のクラスタヘッドが存在する場合には、前記ノード装置が前記クラスタヘッドに選択されず、クラスタメンバーノードとして機能し、無線通信可能エリア内に存在するクラスタヘッドのいずれか１つのクラスタに属するようにした。
【００１８】
この方法により、任意のノード装置が周辺のいずれかのクラスタヘッドと直接通信可能であり、またクラスタヘッド同士をできるだけ少ない中継転送回数で互いに通信可能とするために必要充分なクラスタヘッドが選択された場合には、それ以上のノード装置をクラスタヘッドとして選択しないようにすることができる。これによりできるだけ少ない数のクラスタヘッドによってノード装置が配置されたエリア全体をカバーすることが可能となり、ノード装置間通信における中継転送数を少なくすることが可能となりスループットの低下やパケット転送遅延の増加を抑制することができる。
【００１９】
本発明のアドホックネットワーク構成方法は、前記クラスタメンバーノードが属するクラスタを選択する際に、各クラスタメンバーノードは、自身の無線通信可能エリア内において最初にクラスタヘッドとなったノード装置のクラスタに属するようにした。
【００２０】
この方法により、クラスタヘッドに選択されないノード装置は無線通信可能エリア内のクラスタヘッドのいずれか一つのクラスタに属するようしたシンプルなクラスタ構成を実現することができる。
【００２１】
本発明のノード装置は、上記アドホックネットワーク構成方法が適用されるノード装置である。
【発明の効果】
【００２２】
本発明によれば、互いに隣接するクラスタ間をまたがる通信において、当該クラスタのクラスタヘッド同士が直接通信することが可能となり、異なるクラスタに属するノード間の通信に際してクラスタ間でのゲートウェイノードを介した通信を不要とし、中継転送数の増加によるスループットの低下やパケット転送遅延の増加を抑制することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２４】
（実施の形態）
図１は、本発明の一実施の形態に係るアドホックネットワーク構成方法におけるノード装置の動作を示すフローチャートであり、「Hello」メッセージの交換による隣接ノード情報取得に関する動作を示す。図中、Ｓはフローの各ステップを示す。
【００２５】
本実施の形態のアドホックネットワーク構成方法では、各ノード装置は、まずノード間で「Hello」メッセージを交換することによって、各ノード装置の無線通信可能エリア内に配置された他ノード装置（隣接ノード）を把握し、その一覧を作成する。
【００２６】
隣接ノード情報収集処理を開始すると（ステップＳ１００）、ステップＳ１０１では、各ノード装置は、まずタイマＴ０を設定しタイマＴ０を起動する。このタイマＴ０の値は、予めシステムパラメータとして各ノード装置に共通に設定された固定値である。
【００２７】
タイマＴ０の設定・起動の後、ステップＳ１０２で各ノード装置は自分の無線通信可能エリア内の他ノード装置に向けて「Hello」メッセージをブロードキャストにより送信する。
【００２８】
図２は、「Hello」メッセージのプロトコルメッセージ構成を示す図である。図２において、「Hello」メッセージ１００は、メッセージが「Hello」メッセージであることを示すメッセージタイプ値１０１と、メッセージを送信するノード装置を識別する固有の識別番号である送信元ノード装置ＩＤ１０２とからなる。
【００２９】
図１のフローに戻って、上記「Hello」メッセージ１００の送信の後、ステップＳ１０３で各ノード装置は他ノード装置からの「Hello」メッセージ受信を待つ。
【００３０】
他ノード装置からの「Hello」メッセージを受信すると、ステップＳ１０４で「Hello」メッセージ１００中に記述された送信元ノード装置ＩＤ１０２によってそのメッセージを送信したノード装置のＩＤを取得し、それを隣接ノードリスト（図示せず）に保持（追記）する。
【００３１】
上記ステップＳ１０３で他ノード装置からの「Hello」メッセージ受信がない場合、あるいは上記ステップＳ１０４で送信元ノード装置ＩＤ１０２を隣接ノードリスト追記した場合は、ステップＳ１０５に進む。
【００３２】
ステップＳ１０５では、タイマＴ０が満了か否かを判別し、タイマＴ０が満了でなければ上記ステップＳ１０３に戻ってタイマＴ０が満了するまでの一定時間上記の受信動作を行う。タイマＴ０が満了した場合は、本「隣接ノード情報収集処理」フローを終了する（ステップＳ１０６）。
【００３３】
上記「隣接ノード情報収集処理」フローにより、各ノード装置は自身の無線通信可能エリア内にある他のノード装置（隣接ノード）の一覧を保持することができる。
【００３４】
続いて、各ノード装置は互いに隣接するノード同士の中から、クラスタヘッドとして動作するノードを選択する動作を行う。
【００３５】
図３は、本実施の形態に係るアドホックネットワーク構成方法におけるノード装置の動作を示すフローチャートであり、クラスタヘッドの選択に関する動作を示す。
【００３６】
クラスタヘッド選択処理を開始すると（ステップＳ２００）、ステップＳ２０１では、各ノードはまずタイマＴ１を設定しタイマＴ１を起動する。タイマＴ１の値は、先の手順によって作成した隣接ノードリストのエントリ数に応じて決定される値である。タイマＴ１の値は、隣接ノードリストのエントリ数が多い、すなわち多くのノード装置を隣接ノードとして持つノードほど小さい値が設定されるように、予め定められた関数Ｆ（ｎ）（ｎは隣接ノードリストのエントリ数）によって決定される。関数Ｆ（ｎ）は、ｎの値に反比例する値を返す関数である。
【００３７】
ステップＳ２０２では、他ノードからクラスタヘッド宣言メッセージを受信したか否かを判別する。他ノードからクラスタヘッド宣言メッセージを受信した場合は、ステップＳ２０３に進み、他ノードからクラスタヘッド宣言メッセージを受信していない場合は、ステップＳ２０７に進む。
【００３８】
各ノード装置は、隣接ノードから後述する「クラスタヘッド宣言」メッセージを受信するか、自身がクラスタヘッドに選択されるまで以下の動作（ステップＳ２０３〜ステップＳ２０５）を繰り返す。
【００３９】
すなわち、ステップＳ２０３でタイマＴ１が満了したか否かを判別し、タイマＴ１が満了していなければ上記ステップＳ２０２に戻る。タイマＴ１満了すると、ステップＳ２０４で各ノード装置は乱数を発生させて関数ｆ（ｎ，ｒａｎ（ｉ））の値を求める。ｎは隣接ノードリストのエントリ数、ｒａｎ（ｉ）は[０，１]の範囲でランダムに値が選ばれる乱数である。関数ｆは、例えばｎ／ｋ×ｒａｎ（ｉ）  （ｋは予めシステムパラメータとして設定された固定値）のように、乱数の値に応じて値が変化し、ｎの値が大きいほどより高い確率で１以上の値を返すような関数である。
【００４０】
関数ｆ（ｎ，ｒａｎ（ｉ））の値が１以上の場合には、ステップＳ２０５で該当ノード装置がクラスタヘッドとして選択され、自身の無線通信可能エリア内の他ノード装置に「クラスタヘッド宣言」メッセージをブロードキャスト送信する。これにより該当ノード装置が他ノード装置にクラスタヘッドとして選択されたことを通知する。該当ノード装置は、その後クラスタヘッド選択処理を終了し（ステップＳ２０６）、これ以降クラスタヘッドとして動作する。
【００４１】
関数ｆ（ｎ，ｒａｎ（ｉ））の値が１より小さい場合には、上記ステップＳ２０１に戻って該当ノード装置は再びタイマＴ０を設定、起動して上記の動作を繰り返す。
【００４２】
図４は、「クラスタヘッド宣言」メッセージのプロトコルメッセージ構成を示す図である。図４において、「クラスタヘッド宣言」メッセージ２００は、「クラスタヘッド宣言」メッセージであることを示すメッセージタイプ値２０１と、そのメッセージを送信するノード装置を識別する固有の識別番号である送信元ノード装置ＩＤ２０２と、本メッセージを送信するノード装置の隣接ノードの隣接ノード装置ＩＤ２０３（隣接ノード装置ＩＤ−ｉ）とからなる。
【００４３】
一方、上記動作を繰り返すうちに、他のノード装置からの「クラスタヘッド宣言」メッセージを受信することによって、自身の無線通信可能エリア内にクラスタヘッドとして選択されたノード装置があることを知ったノード装置は、以下の動作（１）〜（７）を行う。
【００４４】
（１）「クラスタヘッド宣言」メッセージを受信したノード装置は、まず隣接クラスタヘッドカウンタ値を１増加させる（ステップＳ２０７）。この隣接クラスタヘッドカウンタ値は、自身の無線通信可能エリア内のクラスタヘッドの数を係数するカウンタであり、初期値は０に設定されている。ステップＳ２０８では、隣接クラスタヘッドカウンタ値がシステムパラメータとして予め定められた値Ｄ以上か否かを判別する。隣接クラスタヘッドカウンタ値がシステムパラメータとして予め定められた値Ｄ以上になった場合には、該当ノード装置はすでに自身のまわりに充分な数のクラスタヘッドが存在するものと判断してクラスタヘッド選択処理を終了し（ステップＳ２０６）、以降自身はクラスタメンバーノードとして動作する。この際、最初に受信した「クラスタヘッド宣言」メッセージの送信元ノード装置（クラスタヘッド）のクラスタに属することを決定する。隣接クラスタヘッドカウンタ値がＤより小さい場合には、ノード装置は以下の動作（２）を行う。
【００４５】
（２）受信した「クラスタヘッド宣言」メッセージ２００中に含まれる隣接ノード装置ＩＤ２０３一覧と、自身の共通隣接ノードリストを比較し、両者に共通に含まれるノードＩＤを共通隣接ノードリストから削除する（ステップＳ２０９）。この共通隣接ノードリストは、初期値としてそのノードの隣接ノードリストと同一の内容を保持しているものである。
【００４６】
（３）その後当該ノード装置はタイマＴ２を設定しタイマＴ２を起動する（ステップＳ２１０）。タイマＴ２の値は上記共通隣接ノードリストのエントリ数に応じて決定される値であり、隣接ノードリストのエントリ数が少ないほど小さい値が設定されるように、予め定められた関数Ｇ（ｃ）（ｃは共通隣接ノードリストのエントリ数）によって決定される。関数Ｇ（ｃ）はｃの値に比例する値を返す関数である。
【００４７】
（４）他のノード装置から「クラスタヘッド宣言」メッセージ２００を受信したか否かを判別する（ステップＳ２１１）。他のノード装置から「クラスタヘッド宣言」メッセージ２００を受信した場合には、上記（１）に戻って動作を繰り返す。他のノード装置から「クラスタヘッド宣言」メッセージ２００を受信しない場合には、ステップＳ２１２に進む。
【００４８】
（５）隣接するクラスタヘッドから、後述する「共通隣接ノード情報」メッセージ３００を受信したか否かを判別する（ステップＳ２１２）。自身の無線通信可能エリア内にあるクラスタヘッドから、後述する「共通隣接ノード情報」メッセージ３００を受信した場合には、受信した「共通隣接ノード情報」メッセージ３００中に含まれる共通隣接ノード装置ＩＤ３０３一覧と、自身の共通隣接ノードリストを比較し、両者に共通に含まれるノードＩＤを共通隣接ノードリストから削除する（ステップＳ２１３）。その上でタイマＴ２を再設定しタイマＴ２を起動する（ステップＳ２１４）。
【００４９】
（６）上記（４），（５）の動作を、タイマＴ２が満了するまで繰り返す（ステップＳ２１５）。
【００５０】
（７）タイマＴ２が満了した場合には、各ノード装置は乱数を発生させて関数ｇ（ｃ，ｒａｎ（ｉ））の値を求める（ステップＳ２１６）。ｃは共通隣接ノードリストのエントリ数、ｒａｎ（ｉ）は[０，１]の範囲でランダムに値が選ばれる乱数である。関数ｇは、例えばｎ／ｑ×ｒａｎ（ｉ）  （ｑは予めシステムパラメータとして設定された固定値）のように、乱数の値に応じて値が変化し、ｃの値が大きいほどより高い確率で１以上の値を返すような関数である。関数ｇ（ｃ，ｒａｎ（ｉ））の値が１以下の場合には、該当ノード装置はクラスタヘッドとして選択され、自身の無線通信可能エリア内の他ノード装置に「クラスタヘッド宣言」メッセージ２００をブロードキャスト送信する（ステップＳ２１７）。これにより該当ノード装置が他ノード装置にクラスタヘッドとして選択されたことを通知する。該当ノード装置はその後クラスタヘッド選択処理を終了し（ステップＳ２０６）、これ以降クラスタヘッドとして動作する。関数ｇ（ｃ，ｒａｎ（ｉ））の値が１より大きい場合には、該当ノード装置は上記（３）に戻り動作を繰り返す。
【００５１】
上述した動作によってクラスタヘッドとして選択されたノード装置は、加えて以下のクラスタヘッド後処理動作を行う。
【００５２】
図５は、本実施の形態に係るアドホックネットワーク構成方法におけるノード装置の動作を示すフローチャートであり、クラスタヘッド後処理に関する動作を示す。
【００５３】
クラスタヘッド後処理を開始すると（ステップＳ３００）、ステップＳ３０１では、クラスタヘッドはタイマＴ３を設定しタイマＴ３を起動する。タイマＴ３の値は、予めシステムパラメータとして各ノード装置に共通に設定された固定値である。タイマＴ３の設定、起動の後、タイマＴ３の満了までの間以下の動作（ステップＳ３０２〜ステップＳ３０４）を繰り返す。
【００５４】
すなわち、ステップＳ３０２で自身の無線通信可能エリア内にある他ノードから「クラスタヘッド宣言」メッセージ２００を受信したか否かを判別する。他ノードから「クラスタヘッド宣言」メッセージ２００を受信した場合は、ステップＳ３０３に進み、他ノードから「クラスタヘッド宣言」メッセージ２００を受信しない場合は、ステップＳ３０５に進む。
【００５５】
ステップＳ３０３では、自身の無線通信可能エリア内にある他ノードから「クラスタヘッド宣言」メッセージ２００を受信するたびに、受信した「クラスタヘッド宣言」メッセージ２００中に含まれる隣接ノードＩＤ一覧と自身の隣接ノードリストのエントリを比較し、共通するエントリを抽出する。
【００５６】
ステップＳ３０４では、共通するエントリのノードＩＤを含む「共通隣接ノード情報」メッセージ３００をブロードキャストにより送信する。
【００５７】
図６は、「共通隣接ノード情報」メッセージのプロトコルメッセージ構成を示す図である。図６において、「共通隣接ノード情報」メッセージ３００は、「共通隣接ノード情報」メッセージであることを示すメッセージタイプ値３０１と、そのメッセージを送信するノード装置を識別する固有の識別番号である送信元ノード装置ＩＤ３０２と、受信した「クラスタヘッド宣言」メッセージ２００中に含まれる隣接ノード装置ＩＤ２０３と自身の隣接ノードリストに共通する共通隣接ノード装置ＩＤ３０３（共通隣接ノード装置ＩＤ−ｉ）とからなる。
【００５８】
ステップＳ３０５では、タイマＴ３が満了か否かを判別し、タイマＴ３が満了でなければ上記ステップＳ３０２に戻ってタイマＴ３が満了するまでの上記動作を繰り返す。タイマＴ３が満了した場合は、本「クラスタヘッド後処理」フローを終了する（ステップＳ３０６）。
【００５９】
以上詳細に説明したように、本実施の形態によれば、互いに近傍に配置された複数のノード装置の中からクラスタヘッドを選択する際において、より多くの隣接ノードを持つノード装置がより高い確率でクラスタヘッドに選択されるようにすると同時に、既に選択されたクラスタヘッドの隣接ノード装置の中から、当該クラスタヘッドと共通する隣接ノードをより少なく持つノード装置がより高い確率でクラスタヘッドに選択されるようにする。また、あるノードから直接通信できない２ホップ先の近傍に既に存在するクラスタヘッドを含む２つのクラスタヘッドの共通隣接ノードと共通する隣接ノードをより少なく持つノード装置がより高い確率でクラスタヘッドに選択するようにする。これにより、近傍のクラスタヘッド同士が互いに通信可能である条件を保ちながら、できるだけ離れたノード装置をクラスタヘッドに選択することが可能となる。その結果、ノード間通信の中継数を少なくしスループットを可能な限り大きくするともに、中継転送によるパケット転送遅延を可能な限り小さくすることのできるアドホックネットワーク構成を実現することができる。
【００６０】
ここで、従来技術では、互いに無線通信可能なノードグループの中から１つのクラスタヘッドを選択するため、隣接するクラスタのクラスタヘッド同士は、互いの無線通信可能エリア内に無い場合があり、この場合は直接通信できない欠点があった。これに対して、本実施の形態では、互いに無線通信可能なノード同士の中から複数のクラスタヘッドを選択するようにしているので、隣接するクラスタヘッド同士が互いに直接通信できるという特有の効果がある。
【００６１】
以上の説明は本発明の好適な実施の形態の例証であり、本発明の範囲はこれに限定されることはない。
【００６２】
すなわち、本発明にかかるアドホックネットワーク構成方法及びノード装置は、アドホックノードの中で動くアルゴリズムの発明であり、本発明の技術的思想を逸脱しない範囲で様々な態様を採ることができる。
【００６３】
また、上記実施の形態は、無線アドホックネットワークにおいて、互いの無線通信可能領域内に配置された近傍のノード装置同士によりクラスタを構成し、クラスタの代表ノードがアドホックルーチングを行うようにすることにより、多数のノード装置が配置された場合においてノード装置間でのルーチング制御パケットのやりとりを削減するようにしたアドホックネットワーク構成方法に適用した例であるが、ノード間通信を行うノード装置であればどのような装置への実装も可能である。
【００６４】
また、上記各実施の形態では、アドホックネットワーク構成方法及びノード装置という名称を用いたが、これは説明の便宜上であり、無線アドホックネットワーク構成方法及ノードのクラスタ構成方法等であってもよいことは勿論である。
【産業上の利用可能性】
【００６５】
以上のように、本発明にかかるアドホックネットワーク構成方法及びノード装置は、互いに隣接するクラスタ間をまたがる通信において、該当クラスタのクラスタヘッド同士が直接通信することが可能となり、異なるクラスタに属するノード間の通信に際してクラスタ間でのゲートウェイノードを介した通信を不要とし、中継転送数の増加によるスループットの低下やパケット転送遅延の増加を抑制することができるという効果を有する。また、無線アドホックネットワークにおいて、互いの無線通信可能領域内に配置された近傍のノード装置同士によりクラスタを構成し、クラスタの代表ノードがアドホックルーチングを行うようにすることにより、多数のノード装置が配置された場合においてノード装置間でのルーチング制御パケットのやりとりを削減するようにしたアドホックネットワーク構成方法等として有用である。
【図面の簡単な説明】
【００６６】
【図１】本発明の実施の形態に係るアドホックネットワーク構成方法におけるノード装置の隣接ノード情報取得に関する動作を示すフロー図
【図２】本実施の形態に係るアドホックネットワーク構成方法におけるノード装置の「Hello」メッセージのプロトコルメッセージ構成を示す図
【図３】本発明の実施の形態に係るアドホックネットワーク構成方法におけるノード装置のクラスタヘッドの選択に関する動作を示すフロー図
【図４】本実施の形態に係るアドホックネットワーク構成方法におけるノード装置の「クラスタヘッド宣言」メッセージのプロトコルメッセージ構成を示す図
【図５】本発明の実施の形態に係るアドホックネットワーク構成方法におけるノード装置のクラスタヘッド後処理に関する動作を示すフロー図
【図６】本実施の形態に係るアドホックネットワーク構成方法におけるノード装置の「共通隣接ノード情報」メッセージのプロトコルメッセージ構成を示す図
【図７】従来のアドホックネットワーク構成方法によるネットワーク構成例を示す図
【符号の説明】
【００６７】
１１  クラスタヘッド
１２  ゲートウェイノード
１３  クラスタメンバノード
１４  互いに通信可能なノード装置のグループ
【図１】
2008312059.tif 000003
【図２】
2008312059.tif 000004
【図３】
2008312059.tif 000005
【図４】
2008312059.tif 000006
【図５】
2008312059.tif 000007
【図６】
2008312059.tif 000008
【図７】
2008312059.tif 000009