(57)【特許請求の範囲】
【請求項１】
無線によって通信可能に接続される複数のノードを備えた無線マルチホップネットワークの形成方法であって、
前記ノード毎に、１ホップで通信可能な近傍のノードをそれぞれ検出する第１のステップと、
前記近傍のノードどうしをポーリング方式による通信を可能に接続し、マスターとして動作する１つのノードとスレーブとして動作する少なくとも１つのノードとから成る複数のポーリングクラスタを形成する第２のステップと、
前記ポーリングクラスタ毎に、隣接する近傍のポーリングクラスタをそれぞれ検出する第３のステップと、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定する第４のステップと、
ポーリングクラスタ内ではポーリング方式でパケット転送を行い、ポーリングクラスタ間ではキャリアセンス方式でパケット転送を行う第５のステップと、
を有する無線マルチホップネットワークの形成方法。
【請求項２】
前記第２のステップは、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合は、前記近傍のノードからの受信電界強度が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大で、かつ前記近傍のノードからの受信電界強度が最大のノードが複数存在する場合は、前記ノードにそれぞれ付与されたアドレスの値が最小または最大のノードを前記マスターとして選択する請求項１記載の無線マルチホップネットワークの形成方法。
【請求項３】
前記第２のステップは、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合、該ノードに対するアソシエーションを要求したノード数が最も少ないノードを前記マスターとして選択する請求項１記載の無線マルチホップネットワークの形成方法。
【請求項４】
前記第４のステップは、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートが複数存在する場合、前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートを選択する請求項１記載の無線マルチホップネットワークの形成方法。
【請求項５】
前記第４のステップは、
前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートが複数存在する場合、前記前記近傍のポーリングクラスタからの受信電界強度が最大の通信ルートを選択する請求項４記載の無線マルチホップネットワークの形成方法。
【請求項６】
前記第２のステップは、
前記近傍のポーリングクラスタから、それぞれが使用する無線周波数の情報を送信させ、他のポーリングクラスタで未使用の無線周波数を選択する処理をさらに有する請求項１から請求項５のいずれか１項記載の無線マルチホップネットワークの形成方法。
【請求項７】
無線によってパケットを転送する無線マルチホップネットワークを構成するための無線通信装置であって、
１ホップで通信可能な近傍のノードを検出する近傍ノード発見部と、
自無線通信装置を、無線通信装置の集合体であるポーリングクラスタのマスターまたはスレープのいずれか一方に選択し、前記近傍のノードとポーリング方式による通信が可能に接続するアソシエーション実行部と、
前記ポーリングクラスタ毎に隣接する近傍のポーリングクラスタを検出する近傍クラスタ発見部と、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定するクラスタ間接続部と、
ポーリングクラスタ内でポーリング方式によるパケットを送受信する第１の無線インタフェースと、
ポーリングクラスタ間でキャリアセンス方式によるパケットを送受信する第２の無線インタフェースと、
を有する無線通信装置。
【請求項８】
前記アソシエーション実行部は、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合は、前記近傍のノードからの受信電界強度が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大で、かつ前記近傍のノードからの受信電界強度が最大のノードが複数存在する場合は、前記ノードにそれぞれ付与されたアドレスの値が最小または最大のノードを前記マスターとして選択する請求項７記載の無線通信装置。
【請求項９】
前記アソシエーション実行部は、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合、該ノードに対するアソシエーションを要求したノード数が最も少ないノードを前記マスターとして選択する請求項７記載の無線通信装置。
【請求項１０】
前記クラスタ間接続部は、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートが複数存在する場合、前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートを選択する請求項７記載の無線通信装置。
【請求項１１】
前記クラスタ間接続部は、
前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートが複数存在する場合、前記前記近傍のポーリングクラスタからの受信電界強度が最大の通信ルートを選択する請求項１０記載の無線通信装置。
【請求項１２】
前記近傍のポーリングクラスタから、それぞれが使用する無線周波数の情報を送信させ、他のポーリングクラスタで未使用の無線周波数を選択する無線周波数調査部をさらに有する請求項７から請求項１１のいずれか１項記載の無線通信装置。
【請求項１３】
無線によってパケットを転送する無線マルチホップネットワークを構成するコンピュータに実行させるためのプログラムであって、
１ホップで通信可能な近傍のノードを検出する第１のステップと、
自無線通信装置を、無線通信装置の集合体であるポーリングクラスタのマスターまたはスレープのいずれか一方に選択し、前記近傍のノードとポーリング方式による通信が可能に接続する第２のステップと、
前記ポーリングクラスタ毎に隣接する近傍のポーリングクラスタを検出するための処理を実行する第３のステップと、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定するための処理を実行する第４のステップと、
ポーリングクラスタ内ではポーリング方式でパケット転送を行い、ポーリングクラスタ間ではキャリアセンス方式でパケット転送を行う第５のステップと、
をコンピュータに実行させるためのプログラム。
【請求項１４】
前記第２のステップは、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合は、前記近傍のノードからの受信電界強度が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大で、かつ前記近傍のノードからの受信電界強度が最大のノードが複数存在する場合は、前記ノードにそれぞれ付与されたアドレスの値が最小または最大のノードを前記マスターとして選択する請求項１３記載のプログラム。
【請求項１５】
前記第２のステップは、
前記近傍のノード数が最大のノードを前記マスターとして選択し、
前記近傍のノード数が最大のノードが複数存在する場合、該ノードに対するアソシエーションを要求したノード数が最も少ないノードを前記マスターとして選択する請求項１３記載のプログラム。
【請求項１６】
前記第４のステップは、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートが複数存在する場合、前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートを選択する請求項１３記載のプログラム。
【請求項１７】
前記第４のステップは、
前記近傍のポーリングクラスタに対するホップ数が最小となる通信ルートが複数存在する場合、前記前記近傍のポーリングクラスタからの受信電界強度が最大の通信ルートを選択する請求項１６記載のプログラム。
【請求項１８】
前記第２のステップは、
前記近傍のポーリングクラスタから、それぞれが使用する無線周波数の情報を送信させ、他のポーリングクラスタで未使用の無線周波数を選択する処理をさらに有する請求項１３から請求項１７のいずれか１項記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はホットゾーンシステムに適用して好適な無線マルチホップネットワークの形成方法及び該無線マルチホップネットワークを構成する無線通信装置に関する。
【背景技術】
【０００２】
ホットゾーンシステムとは、複数のアクセスポイント（以下、ＡＰ）に対して無線ＬＡＮスイッチを１台ずつ接続し、無線ＬＡＮスイッチどうしを無線により接続することで広範囲な無線ＬＡＮサービスエリアを提供するシステムである。ホットゾーンシステムは、有線ではなく無線によりＡＰどうしを接続するため、ケーブル敷設の手間がかからずコストを削減できる利点を持つ。このホットゾーンシステムでは、指定されたサービスエリアをカバーするためにＡＰがきめ細かく配置され、またサービスの利用人数が多い場所ではＡＰが高密度に配置される。
【０００３】
ホットゾーンシステムのように、複数の無線通信装置（例えば、無線ＬＡＮスイッチ）を相互接続することで構築されるネットワークは、任意のＡＰから入力されたパケットを複数の無線通信装置を経由して所望のＡＰまで伝送するために、無線マルチホップネットワークと呼ばれる。
【０００４】
このような無線マルチホップネットワークに対するアクセス方式として、従来、ＣＳＭＡ/ＣＡ（Carrier Sense Multiple Access with Collision Avoidance）等を使用するキャリアセンス方式が知られている。
【０００５】
このキャリアセンス方式を無線マルチホップネットワークにおける無線通信装置間の通信に適用すれば、各無線通信装置の送信間隔がそれぞれランダムに変化するため、複数の無線通信装置が一斉に送信することによるパケットの衝突を回避できる。
【０００６】
しかしながら、キャリアセンス方式だけを適用した無線マルチホップネットワークでは、無線通信装置の配置密度が高くなると、コンテンション数が多くなるためにパケットの衝突を回避できなくなる問題がある。パケットの衝突が発生すると、その度にパケットの送信待ち時間がおよそ２倍に増加するため、パケットの転送遅延の増大を招いてしまう。そのため、無線マルチホップネットワークを音声通信のようなリアルタイム性が要求されるアプリケーションで利用する場合に音声品質の劣化を招くおそれがある。
【０００７】
また、無線マルチホップネットワークにおける無線通信装置間の通信に適用可能な他の方式として、非特許文献１に記載されたポーリング方式がある。
【０００８】
ポーリング方式を適用した無線マルチホップネットワークでは、各無線通信装置がＭａｓｔｅｒあるいはＳｌａｖｅのいずれか一方の役割を担当する。本明細書では１つのＭａｓｔｅｒとなる無線通信装置と少なくとも１つのＳｌａｖｅとなる無線通信装置から構成される集合体をポーリングクラスタ（以下、ＰＣＦクラスタと略す）と呼ぶ。ポーリング方式を適用した無線マルチホップネットワークでは、Ｍａｓｔｅｒとなる無線通信装置（以下、Ｍａｓｔｅｒノードと称す）がＳｌａｖｅとなる複数の無線通信装置（以下、Ｓｌａｖｅノードと称す）を予め決められたスケジュールにしたがって順次ポーリングすることでパケットの送受信を行う。
【０００９】
ＭａｓｔｅｒノードからＳｌａｖｅノードへパケットを送信する場合、Ｍａｓｔｅｒノードは送信先のＳｌａｖｅノードに対してポーリングするタイミングでパケットを送信する。逆に、ＳｌａｖｅノードからＭａｓｔｅｒノードへパケットを送信する場合、ＳｌａｖｅノードはＭａｓｔｅｒノードからのポーリングを受けたタイミングでパケットを送信する。このような方式では、ＭａｓｔｅｒノードがＳｌａｖｅノードの送信タイミングを制御することになるため、Ｓｌａｖｅノード間やＭａｓｔｅｒノードとＳｌａｖｅノード間の通信におけるパケットの衝突を回避でき、結果としてパケットの転送時間を低減できる。
【００１０】
しかしながら、ポーリング方式を適用した無線マルチホップネットワークでは、ＰＣＦクラスタを形成するＳｌａｖｅノード数に比例してポーリングによる待ち時間が増大し、かつパケットが複数のＰＣＦクラスタを経由することにより各ＰＣＦクラスタにおけるポーリング待ち時間が累積されるという問題がある。
【００１１】
図１５は、１８台の無線ＬＡＮスイッチ（ＷＳ：Wireless Switch）ＷＳ１〜ＷＳ１８を備えた、ポーリング方式だけを適用した無線マルチホップネットワークの一構成例を示している。また、図１６は図１５に示したＷＳ２からＷＳ１５へパケットを転送する際に発生するポーリング待ち時間を示している。
【００１２】
図１５に示す無線マルチホップネットワークは、ＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６がそれぞれＭａｓｔｅｒノードとして動作し、ＷＳ２〜４、ＷＳ５、ＷＳ６、ＷＳ８〜１１、ＷＳ１３〜１５、ＷＳ１７及びＷＳ１８がそれぞれＳｌａｖｅノードとして動作する例である。
【００１３】
図１５に示すように、ＷＳ１をＭａｓｔｅｒノードとする第１のＰＣＦクラスタは、Ｓｌａｖｅノードとして、ＷＳ２、ＷＳ３、ＷＳ４、ＷＳ５及びＷＳ６を備えている。ＷＳ７をＭａｓｔｅｒノードとする第２のＰＣＦクラスタは、Ｓｌａｖｅノードとして、ＷＳ６、ＷＳ８、ＷＳ９、ＷＳ１０及びＷＳ１１を備えている。また、ＷＳ１２をＭａｓｔｅｒノードとする第３のＰＣＦクラスタは、Ｓｌａｖｅノードとして、ＷＳ１０、ＷＳ１３、ＷＳ１４及びＷＳ１５を備えている。さらに、ＷＳ１６をＭａｓｔｅｒノードとする第４のＰＣＦクラスタは、Ｓｌａｖｅノードとして、ＷＳ１３、ＷＳ１７及びＷＳ１８を備えている。
【００１４】
第１のＰＣＦクラスタ〜第４のＰＣＦクラスタでそれぞれ利用する無線周波数は、各ＰＣＦクラスタ間で干渉しないように設定する。図１５では、第１のＰＣＦクラスタが無線周波数ｆ１を使用し、第２のＰＣＦクラスタが無線周波数ｆ２を使用し、第３のＰＣＦクラスタが無線周波数ｆ３を使用し、第４のＰＣＦクラスタが無線周波数ｆ４を使用する例を示している。
【００１５】
このような構成において、例えば図１５に示したＷＳ２からＷＳ１５へパケットを転送する場合、第１のＰＣＦクラスタでは、ＷＳ２からＷＳ１、ＷＳ１からＷＳ６の順にパケットが転送される。このとき、第１のＰＣＦクラスタでは、ＭａｓｔｅｒノードであるＷＳ１によってパケットの送信タイミングが制御されるため、図１６に示すようにＷＳ２からＷＳ１に対するパケット転送が終了後、次にＷＳ１からＷＳ６に対するパケット転送が始まるまでにポーリング待ち時間（待ち時間１）が生じる。
【００１６】
また、第２のＰＣＦクラスタでは、ＷＳ６からＷＳ７、ＷＳ７からＷＳ１０の順にパケットが転送され、ＷＳ１からＷＳ６に対するパケット転送が終了後、次にＷＳ６からＷＳ７に対するパケット転送が始まるまでにポーリング待ち時間（待ち時間２）が生じ、さらにＷＳ６からＷＳ７に対するパケット転送が終了後、次にＷＳ７からＷＳ１０に対するパケット転送が始まるまでにポーリング待ち時間（待ち時間３）が生じる。
【００１７】
同様に、第３のＰＣＦクラスタでは、ＷＳ１０からＷＳ１２、ＷＳ１２からＷＳ１５の順にパケットが転送され、先のパケット転送が終了してから次にこれらのパケット転送が始まるまでにポーリング待ち時間（待ち時間４、待ち時間５）が生じる。
【００１８】
したがって、図１５に示した無線ネットワークにおいて、ＷＳ２からＷＳ１５へパケットを転送する場合、第１のＰＣＦクラスタ、第２のＰＣＦクラスタ及び第３のＰＣＦクラスタにおけるそれぞれポーリング待ち時間を累積した遅延（待ち時間１〜５の合計）が生じることになる。
【非特許文献１】K. Mizuno, M. Katayama, H. Suda, "A New QoS-guaranteed Multichannel MAC Protocol for Multihop Wireless Networks," Vehicular Technology Conference 2002, VTC Spring 2002, IEEE 55th, Volume 2, 6-9 May 2002, pp.967-971, vol.2
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述したように、従来の無線マルチホップネットワークのうち、キャリアセンス方式だけを適用した構成では、無線通信装置が高密度に配置されていると、コンテンション数が多くなるためにパケットの衝突に起因して転送遅延が大きくなる問題がある。
【００２０】
また、ポーリング方式だけを適用した構成では、複数のＰＣＦクラスタを通過する際に、各ＰＣＦクラスタにおけるポーリング待ち時間が累積されるため、パケットの転送遅延が増大する問題がある。
【００２１】
本発明は上記したような従来の技術が有する問題点を解決するためになされたものであり、パケットの転送時間を短縮することが可能な無線マルチホップネットワークの形成方法及び無線通信装置を提供することを目的とする。
【課題を解決するための手段】
【００２２】
上記目的を達成するため本発明の無線マルチホップネットワークの形成方法は、無線によって通信可能に接続される複数のノードを備えた無線マルチホップネットワークの形成方法であって、
前記ノード毎に、１ホップで通信可能な近傍のノードをそれぞれ検出する第１  のステップと、
前記近傍のノードどうしをポーリング方式による通信を可能に接続し、マスターとして動作する１つのノードとスレーブとして動作する少なくとも１つのノードとから成る複数のポーリングクラスタを形成する第２のステップと、
前記ポーリングクラスタ毎に、隣接する近傍のポーリングクラスタをそれぞれ検出する第３のステップと、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定する第４のステップと、
ポーリングクラスタ内ではポーリング方式でパケット転送を行い、ポーリングクラスタ間ではキャリアセンス方式でパケット転送を行う第５のステップと、
を有する方法である。
【００２３】
一方、本発明の無線通信装置は、無線によってパケットを転送する無線マルチホップネットワークを構成するための無線通信装置であって、
１ホップで通信可能な近傍のノードを検出する近傍ノード発見部と、
自無線通信装置を、無線通信装置の集合体であるポーリングクラスタのマスターまたはスレープのいずれか一方に選択し、前記近傍のノードとポーリング方式による通信が可能に接続するアソシエーション実行部と、
前記ポーリングクラスタ毎に隣接する近傍のポーリングクラスタを検出する近傍クラスタ発見部と、
前記近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定するクラスタ間接続部と、
ポーリングクラスタ内でポーリング方式によるパケットを送受信する第１の無線インタフェースと、
ポーリングクラスタ間でキャリアセンス方式によるパケットを送受信する第２の無線インタフェースと、
を有する構成である。
【００２４】
上記のような無線マルチホップネットワークの形成方法及び無線通信装置では、近傍のノードどうしをポーリング方式による通信を可能に接続し、マスターとして動作する１つのノードとスレーブとして動作する少なくとも１つのノードとから成る複数のポーリングクラスタを形成し、近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定することで、キャリアセンス方式のみを用いた構成と比べて近傍のノード間のパケット衝突に起因する遅延時間が低減し、ポーリング方式のみを用いた構成と比べてポーリングクラスタ間でのポーリング待ち時間に起因する遅延時間が低減する。
【発明の効果】
【００２５】
本発明によれば、近傍のノードどうしをポーリング方式による通信を可能に接続し、マスターとして動作する１つのノードとスレーブとして動作する少なくとも１つのノードとから成る複数のポーリングクラスタを形成し、近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定することで、キャリアセンス方式のみを用いた構成と比べて近傍のノード間のパケット衝突に起因する遅延時間が低減し、ポーリング方式のみを用いた構成と比べてポーリングクラスタ間でのポーリング待ち時間に起因する遅延時間が低減する。したがって、無線マルチホップネットワークにおけるパケットの転送遅延が低減する。
【発明を実施するための最良の形態】
【００２６】
次に本発明について図面を参照して説明する。
【００２７】
図１は本発明の無線マルチホップネットワークの形成方法の手順を示すフローチャートである。
【００２８】
図１に示すように、本発明では以下に示す４つのステップＳ１〜Ｓ４によって無線マルチホップネットワークを形成する。
【００２９】
ステップＳ１は、無線通信装置（以下、ノードと称す）毎にそれぞれ近接ノードを検出する工程である（Neighbor Discovery）。ステップＳ１では、ノード毎にそれぞれ１ホップで到達可能な近傍ノードを検出し、無線インターフェースで接続可能な近傍ノード数をそれぞれ算出する。
【００３０】
ステップＳ２は、ＰＣＦクラスタを形成する工程である。ステップＳ２では、ステップＳ１の処理で検出した近傍ノード数の情報を１ホップで到達可能な近傍ノード間でそれぞれ交換する。そして、近傍ノード数が最大のノードをＰＣＦクラスタにおけるＭａｓｔｅｒノードとして選択し、選択したノードにそれぞれアソシエーションを要求する。このとき、近傍ノード数が最大のノードが複数存在する場合は、それらのノードから送信された無線信号の受信電界強度が最大のノードをＭａｓｔｅｒノードとして選択する。さらに、近傍ノード数が最大であり、かつ受信電界強度が最大のノードが複数存在する場合は、各ノードに付与されたＭＡＣアドレス等の値が最小（または最大）のノードをＭａｓｔｅｒノードとして選択する。近傍ノード数、受信電界強度及びＭＡＣアドレスの各情報は、キャリアセンス方式によりパケットを送受信することで近傍ノードどうしが互いに通知する。
【００３１】
なお、自ノードの近傍ノード数が最大の場合は、自ノードをＭａｓｔｅｒノードに選択して他ノードからのアソシエーション要求を待ち受ける。但し、近傍ノード数が最大のノードが自ノードの他にも存在する場合は、上記と同様に受信電界強度が最大のときに自ノードをＭａｓｔｅｒノードとして選択する。さらに、近傍ノード数が最大であり、かつ受信電界強度が最大のノードが自ノードの他にも存在する場合は、ＭＡＣアドレスが最小（または最大）のときに自ノードをＭａｓｔｅｒノードに選択する。
【００３２】
アソシエーション要求を受信したＭａｓｔｅｒノードは、その送信元のノードへ応答メッセージを返信する。アソシエーション要求に対する応答メッセージを受け取ったノードは全てＳｌａｖｅノードとして動作する。本発明では、ステップＢの処理で選択されたＭａｓｔｅｒノードとＳｌａｖｅノードとにより構成されるＰＣＦクラスタ内の通信にポーリング方式を利用する。
【００３３】
ステップＳ２の処理で選択された各ＰＣＦクラスタのＭａｓｔｅｒノードは、他のＰＣＦクラスタと無線周波数が干渉しないように自ＰＣＦクラスタで使用する無線周波数を決定する。
【００３４】
ステップＳ３は、ＰＣＦクラスタ単位で近傍のＰＣＦクラスタを検出する工程である。ステップＳ３では、自ＰＣＦクラスタと接続可能な近傍ＰＣＦクラスタのリストを生成する。
【００３５】
ステップＳ４は、ＰＣＦクラスタ間を接続する工程である。ステップＳ４では、隣接する各ＰＣＦクラスタ間でパケットを送受信するための通信ルートを決定する。本発明では、ＰＣＦクラスタ間の通信にキャリアセンス方式を利用する。
【００３６】
次に、本発明の無線マルチホップネットワークの形成方法について図面を用いて具体的に説明する。
【００３７】
図２は本発明の無線マルチホップネットワークを形成方法で用いるパケットの一構成例を示す模式図であり、図３は本発明の無線マルチホップネットワークを構成するノードの一構成例を示すブロック図である。
【００３８】
図２に示すように、本発明ではノード間で送受信するパケットが、送信局アドレス、受信局アドレス、送信先アドレス及び送信元アドレスの各フィールドを備えた構成である。図２に示す各フィールドを備えたパケットは、例えばＩＥＥＥ８０２．１１で規定されている。送信局アドレスはパケットの転送元ノードのアドレスが格納されるフィールドであり、受信局アドレスはパケットの転送先ノードのアドレスが格納されるフィールドである。また、送信先アドレス及び送信元アドレスは、ＡＰを経由してパケットを送受信する端末等のend to endのアドレスがそれぞれ格納されるフィールドである。なお、図２はパケットの送受信に必要な最低限の情報のみを示している。実際のパケットは、上記アドレスフィールドに続いてパケットの種類を識別するための情報が搭載されるフィールドや送受信対象のデータが搭載されるデータフィールド等を備えている。後述する、無線マルチホップネットワークを構成するために各ノード間で送受信する種々のパケットは、これらのフィールドを備えた構成である。
【００３９】
図３に示すように、ノード１００は、２つの無線インターフェースを備え、一方の無線インターフェースがポーリング方式の通信で使用され、他方の無線インターフェースがキャリアセンス方式の通信で使用される構成である。各ノード１００が備える無線インターフェースは、パケットの転送に用いる有限数の無線チャネルから任意の無線チャネルを選択可能とする。なお、各ノード１００には、ＰＣＦクラスタ内の通信用及びＰＣＦクラスタ間の通信用として、それぞれ２つ以上の無線インターフェースを備えていてもよい。その場合、無線チャネルを使い分けることで干渉による実効データレートの低下を防止できるため、無線帯域を有効に利用できる。
【００４０】
図３に示すように、ノード１００は、第１の無線インターフェース１０１、第２の無線インターフェース１０２、有線インターフェース１０３、Master/Slave動作部１０４、近傍ノード発見部１０５、アソシエーション実行部１０６、無線周波数調査部１０７、近傍クラスタ発見部１０８及びクラスタ間接続部１０９を有する構成である。
【００４１】
第１の無線インターフェース１０１、第２の無線インターフェース１０２、有線インターフェース１０３、Master/Slave動作部１０４、近傍ノード発見部１０５、アソシエーション実行部１０６、無線周波数調査部１０７、近傍クラスタ発見部１０８及びクラスタ間接続部１０９は、例えば論理回路やメモリ等を用いてそれぞれ構成してもよく、これらを集積したＬＳＩ等によりその機能を実現してもよい。また、ノード１００は、上記第１の無線インターフェース１０１、第２の無線インターフェース１０２及び有線インターフェース１０３に加えて、ＣＰＵ（またはＤＳＰ）やメモリを備え、該メモリに格納されたプログラムにしたがってＣＰＵ（またはＤＳＰ）により以下に記載するMaster/Slave動作部１０４、近傍ノード発見部１０５、アソシエーション実行部１０６、無線周波数調査部１０７、近傍クラスタ発見部１０８及びクラスタ間接続部１０９の処理をそれぞれ実行する、例えばコンピュータで実現することも可能である。
【００４２】
第１の無線インターフェース１０１は、主としてＰＣＦクラスタ内の通信で使用される、ポーリング方式によりパケットを送受信するための無線インターフェースである。ＰＣＦクラスタの各ノード間では、無線マルチホップネットワークを形成するために、後述する近傍ノード発見パケット、近傍ノード応答パケット、近傍ノード数通知パケット、アソシエーション要求パケット、アソシエーション応答パケット、無線周波数調査指示パケット、無線周波数調査結果パケット、クラスタ内無線周波数通知パケット、近傍クラスタ発見指示パケット、近傍クラスタ応答通知パケット、クラスタ接続要求送信指示パケット、クラスタ接続応答結果パケット等が送受信される。
【００４３】
第２の無線インターフェース１０２は、主としてＰＣＦクラスタ間の通信で使用される、キャリアセンス方式によりパケットを送受信するための無線インターフェースである。異なるＰＣＦクラスタのノード間では、無線マルチホップネットワークを形成するために、後述する無線周波数調査パケット、無線周波数ビジーパケット、近傍クラスタ発見パケット、近傍クラスタ応答パケット、クラスタ接続要求パケット、クラスタ接続応答パケット等が送受信される。
【００４４】
有線インターフェース１０３は、有線による伝送路を介してＡＰとパケット通信を行うためのインターフェースである。
【００４５】
Master/Slave動作部１０４は、自ノードをＰＣＦクラスタのＭａｓｔｅｒノードまたはＳｌａｖｅノードとして動作させるための処理を行う。
【００４６】
近傍ノード発見部１０５は、第１の無線インターフェース１０１または第２の無線インターフェース１０２で接続可能な近傍ノードを検出する。近傍ノード発見部１０５は、近接ノードの検出時、最初に第１の無線インターフェース１０１を用いて近傍ノード発見パケットを他ノード間で送受信する。近傍ノード発見パケットは１ホップで到達可能な隣接するノードにのみ送信される。近傍ノード発見パケットを他ノードから受信した場合、近傍ノード発見部１０５は、近傍ノード応答パケットによりその送信元のノードへ応答メッセージを返信する。近傍ノード発見パケットを送信した近傍ノード発見部１０５は、他ノードから返信される近傍ノード応答パケットの受信数をカウントすることで近傍ノード数を算出する。そして、算出した自ノードの近傍ノード数を、近傍ノード数通知パケットを用いて各近傍ノードへそれぞれ通知する。
【００４７】
アソシエーション実行部１０６は、近傍ノード発見部１０５で検出した情報を用いてＰＣＦクラスタを形成する。アソシエーション実行部１０６は、最初に各近傍ノードから受信した近傍ノード数と自ノードの近傍ノード数とを比較する。そして、近傍にＭａｓｔｅｒノードが無く、かつ自ノードの近傍ノード数が最大の場合は、自ノードをＭａｓｔｅｒノードに選択して他ノードからのアソシエーション要求パケットを待ち受ける。但し、近傍ノード数が最大のノードが複数存在する場合は、受信電界強度が最大のときに自ノードをＭａｓｔｅｒノードに選択する。さらに、近傍ノード数が最大であり、かつ受信電界強度が最大のノードが複数存在する場合は、ＭＡＣアドレス等の値が最小（または最大）のときに自ノードをＭａｓｔｅｒノードに選択する。
【００４８】
Ｍａｓｔｅｒノードから近傍ノード数通知パケットを受信した場合、あるいは自ノードの近傍ノード数が他ノードの近傍ノード数よりも小さい場合は、近傍ノード数が最大のノードを選択してアソシエーション要求パケットを送信する。近傍ノード数が最大のノードが複数存在する場合は、受信電界強度が最大のノードを選択する。さらに、近傍ノード数が最大であり、かつ受信電界強度が最大のノードが複数存在する場合は、ＭＡＣアドレス等の値が最小（または最大）のノードを選択する。
【００４９】
アソシエーション応答パケットを受信したノードは、アソシエーション応答パケットの送信元を自ＰＣＦクラスタにおけるＭａｓｔｅｒノードとみなし、自らはＳｌａｖｅノードとして動作する。ＭａｓｔｅｒノードまたはＳｌａｖｅノードとしての動作はMaster/Slave動作部１０４の制御による。
【００５０】
アソシエーション実行部１０６は、自ノードがＭａｓｔｅｒのとき、近傍ノードからアソシエーション要求パケットを受信すると、その送信元の近傍ノードに対してアソシエーション応答パケットをそれぞれ返信する。但し、アソシエーション数が予め決められたしきい値を越える場合は、しきい値を越えた時点でアソシエーション要求パケットを送信した近傍ノードに対するアソシエーション応答パケットの返信を停止する。このような処理を行うことでＰＣＦクラスタのＳｌａｖｅノード数を制限する。
【００５１】
無線周波数調査部１０７は、自ノードがＭａｓｔｅｒのとき、自ＰＣＦクラスタ内で使用する無線周波数を決定する。無線周波数調査部１０７は、他のＰＣＦクラスタ内で使用する無線周波数を知るために、自ＰＣＦクラスタ内で使用する（あるいは使用したい）無線周波数の情報（使用無線周波数）を載せた無線周波数調査パケットを各ＰＣＦクラスタ間で交換する。無線周波数調査パケットの送受信には第１の無線インターフェース１０１が使用される。
【００５２】
無線周波数調査パケットを交換する場合、Ｍａｓｔｅｒノードから無線周波数調査パケットを送信する場合と、Ｓｌａｖｅノードを介して隣接するＰＣＦクラスタへ無線周波数調査パケットを送信する場合とがある。Ｓｌａｖｅノードを介して隣接するＰＣＦクラスタへ無線周波数調査パケットを送信する場合、Ｍａｓｔｅｒノードの無線周波数調査部１０７はＳｌａｖｅノードへ無線周波数調査指示パケットを送信する。無線周波数調査指示パケットには自ＰＣＦクラスタ内で使用する無線周波数の情報をＭａｓｔｅｒノードが搭載する。無線周波数調査指示パケットを受信したＳｌａｖｅノードの無線周波数調査部１０７は各々の近傍ノードへ無線周波数調査パケットを送信する。
【００５３】
無線周波数調査パケットを受信したノードの無線周波数調査部１０７は、その送信局アドレスを参照し、自ＰＣＦクラスタに所属するノードのアドレスと異なる場合は、無線周波数調査パケット内の使用無線周波数の情報を取得する。そして、自ＰＣＦクラスタ内で使用する無線周波数の情報（使用無線周波数）を無線周波数ビジーパケットに搭載して送信元ノードへ返信する。また、送信局アドレスが自ＰＣＦクラスタに所属するノードのアドレスと一致する場合は送信元ノードへ応答を返信しない。無線周波数ビジーパケットを受信したノードがＳｌａｖｅノードの場合、その無線周波数調査部１０７は無線周波数ビジーパケットの情報を無線周波数調査結果パケットへ搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ送信する。
【００５４】
近傍クラスタ発見部１０８は、無線により接続可能な近傍クラスタを検出する。自ノードがＭａｓｔｅｒのとき、近傍クラスタ発見部１０８は、自身で近傍クラスタ発見パケットを送信する。または、自ＰＣＦクラスタ内の各Ｓｌａｖｅノードに近傍クラスタ発見指示パケットを送信する。その場合、Ｓｌａｖｅノードの近傍クラスタ発見部１０８は、近傍クラスタ発見パケットを各々の近傍ノードへ送信する。
【００５５】
近傍クラスタ発見部１０８は、近傍クラスタ発見パケットを受信すると、その送信局アドレスを参照し、自ノードのＰＣＦクラスタに所属するノードのアドレスと異なる場合は、近傍クラスタ応答パケットを送信元ノードへ返信する。また、送信局アドレスが自ＰＣＦクラスタに所属するノードのアドレスと一致する場合は送信元ノードへ応答を返信しない。近傍クラスタ応答パケットを受信したノードがＳｌａｖｅノードの場合、その近傍クラスタ発見部１０８は近傍クラスタ応答パケットの情報及び近傍クラスタ応答パケットに含まれる受信電界強度の情報を近傍クラスタ応答通知パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ送信する。
【００５６】
クラスタ間接続部１０９は、自ノードがＭａｓｔｅｒのとき、近傍クラスタ発見部１０８で収集した近傍クラスタ応答パケット及び近傍クラスタ応答通知パケット内の情報に基づき自ＰＣＦクラスタと近傍ＰＣＦクラスタとを接続する通信ルートを決定する。このとき、同一の近傍ＰＣＦクラスタに対して複数の通信ルートが存在する場合は受信電界強度がより強い接続ルートを選択する。
【００５７】
クラスタ間接続部１０９は、自ノードがＭａｓｔｅｒのとき、他ＰＣＦクラスタのノードへ直接接続を要求する場合は、クラスタ接続要求パケットを送信する。また、自ＰＣＦクラスタ内のＳｌａｖｅノードを経由して他ＰＣＦクラスタのノードへ接続を要求する場合は、該Ｓｌａｖｅノードへクラスタ接続要求送信指示パケットを送信する。クラスタ接続要求送信指示パケットを受信したＳｌａｖｅノードのクラスタ間接続部１０９は、クラスタ接続要求パケットを近傍ノードへ送信する。
【００５８】
クラスタ接続要求パケットを受信したＭａｓｔｅｒノードのクラスタ間接続部１０９は、クラスタ接続を要求したＰＣＦクラスタのノードへクラスタ接続応答パケットを送信する。クラスタ接続応答パケットをＳｌａｖｅノードで受信した場合、そのクラスタ間接続部１０９は受信したクラスタ接続応答パケットの情報をクラスタ接続応答通知パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ送信する。その結果、他ＰＣＦクラスタとの接続が確立する。
【００５９】
次に、本発明の無線マルチホップネットワークの形成方法について図４〜図１１を用いて説明する。
【００６０】
図４は図３に示した近接ノード発見部の処理手順を示すフローチャートであり、図５は図３に示したアソシエーション実行部の処理を示す状態遷移図である。図６及び図７は図３に示した無線周波数調査部の処理手順を示すフローチャートであり、図８及び図９は図３に示した近傍クラスタ発見部１０８の処理手順を示すフローチャートである。また、図１０及び図１１は図３に示したクラスタ間接続部の処理手順を示すフローチャートである。
【００６１】
図４に示すように、各ノードの近接ノード発見部１０５は、まず近傍ノード発見パケットをそれぞれ送信する（ステップＡ１）。近傍ノード発見パケットを送信したノードの近接ノード発見部１０５は近傍ノード応答パケットの受信待ち状態となる（ステップＡ２）。
【００６２】
次に、近接ノード発見部１０５は、近傍ノード応答パケットを受信したか否かを判定し（ステップＡ３）、近傍ノード応答パケットを受信した場合は、自ノードの近傍ノード数をカウントアップする（ステップＡ４）。
【００６３】
続いて、近接ノード発見部１０５は、近傍ノード発見パケットを受信したか否かを判定し（ステップＡ５）、近傍ノード発見パケットを受信した場合は、その送信元ノードへ近傍ノード応答パケットを返信する（ステップＡ６）。
【００６４】
ステップＡ５の処理で近傍ノード発見パケットを受信しない場合、近接ノード発見部１０５は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＡ７）、タイムオーバーでない場合は、ステップＡ３の処理に戻ってステップＡ３〜Ａ７の処理を繰り返す。また、ステップＡ７の処理でタイムオーバーを検出した場合は、自ノードの近傍ノード数を近傍ノード数通知パケットに搭載して各近傍ノードへそれぞれ送信する（ステップＡ８）。近傍ノード数通知パケットを送信したノードは、近傍ノードからの近傍ノード数通知パケットの受信待ち状態となる（ステップＡ９）。
【００６５】
次に、近接ノード発見部１０５は、近傍ノード数通知パケットを受信したか否かを判定し（ステップＡ１０）、近傍ノード数通知パケットを受信した場合は、その情報（近傍ノード数）を送信元ノードに関連付けてそれぞれ保存する。
【００６６】
近傍ノード数通知パケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＡ１１）、タイムオーバーでない場合は、ステップＡ１０に戻ってステップＡ１からステップＡ１１の処理を繰り返す。タイムオーバーとなった場合は近接ノード発見部１０５による処理を終了する。
【００６７】
図５に示すように、アソシエーション実行部１０６は、まず近接ノード発見部１０５で検出した自ノードの近接ノード数と他ノードから通知された近傍ノード数とを比較する。そして、Ｍａｓｔｅｒノードが近傍に無く、かつ自ノードの近傍ノード数が最大の場合は、自ノードをＭａｓｔｅｒノードに選択して近傍ノードからのアソシエーション要求パケットの受信を待ち受ける。ここで、近傍ノード数が最大のノードが複数存在する場合は受信電界強度が最大の場合に自ノードをＭａｓｔｅｒノードに選択する。また、近傍ノード数が最大で、かつ受信電界強度が最大のノードが複数存在する場合はＭＡＣアドレスの値が最小（または最大）の場合に自ノードをＭａｓｔｅｒノードに選択する。
【００６８】
一方、自ノードよりも多くの近傍ノード数を持つノードが存在する場合は、近傍ノード数が最大のノードを選択し、そのノードにアソシエーション要求パケットを送信する。近傍ノード数が最大のノードが複数存在する場合は受信電界強度が最大のノードを選択する。また、近傍ノード数が最大で、かつ受信電界強度が最大のノードが複数存在する場合は、ＭＡＣアドレスの値が最小（または最大）のノードを選択し、そのノードへアソシエーション要求パケットを送信する。
【００６９】
Ｍａｓｔｅｒに選択されたノードのアソシエーション実行部１０６は、アソシエーション要求パケットを受信すると、その送信元ノードへアソシエーション応答パケットを返信する。
【００７０】
アソシエーション要求パケットを送信したノードは、アソシエーション応答パケットの受信待ちとなる。アソシエーション応答パケットを受信した場合、そのノードはＳｌａｖｅノードとなる。アソシエーション応答パケットを受信できなかったノードは、図４に示した近接ノード発見部１０５による近傍ノードの検出処理を再び実行する（クラスタリセット）。
【００７１】
Ｍａｓｔｅｒに選択されたノードでは、無線周波数調査部１０７により自ＰＣＦクラスタで使用する無線周波数を決定する。
【００７２】
図６に示すように、無線周波数調査部１０７は、まず無線周波数調査パケットを近傍ＰＣＦクラスタのノードへ送信する（ステップＣ１）。無線周波数調査パケットを送信した無線周波数調査部１０７は、近傍のＰＣＦクラスタから返送される、そのＰＣＦクラスタで使用する無線周波数の情報（使用無線周波数）を含む無線周波数ビジーパケットの受信待ち状態となる（ステップＣ２）。
【００７３】
次に、無線周波数調査部１０７は、無線周波数ビジーパケットを受信したか否かを判定し（ステップＣ３）、無線周波数ビジーパケットを受信した場合は、それに含まれる使用無線周波数の情報を抽出し、ＰＣＦクラスタ毎の使用無線周波数を保存する（ステップＣ４）。無線周波数ビジーパケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＣ５）、タイムオーバーでない場合は、ステップＣ３に戻ってステップＣ３からステップＣ５の処理を繰り返す。タイムオーバーとなった場合は、全てのＳｌａｖｅノードへ無線周波数調査指示パケットを送信し、Ｓｌａｖｅノードを介して近傍ＰＣＦクラスタで使用する無線周波数を調査する（ステップＣ６）。無線周波数調査指示パケットを受信したＳｌａｖｅノードの無線周波数調査部１０７は、図７に示すフローチャートにしたがって処理を実行する。
【００７４】
Ｍａｓｔｅｒノードの無線周波数調査部１０７は、無線周波数調査指示パケットを送信すると、Ｓｌａｖｅノードから無線周波数調査結果パケットを受信したか否かを判定する（ステップＣ７）。そして、Ｓｌａｖｅノードから無線周波数調査結果パケットを受信すると、そのパケットに含まれるＰＣＦクラスタ毎の使用無線周波数の情報を保存する（ステップＣ８）。
【００７５】
無線周波数調査結果パケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＣ９）、タイムオーバーでない場合は、ステップＣ７に戻ってステップＣ７からステップＣ９の処理を繰り返す。タイムオーバーとなった場合は、保存した近傍ＰＣＦクラスタの使用無線周波数を参照して未使用の無線周波数を自ＰＣＦクラスタの使用無線周波数に決定し（ステップＣ１０）、決定した使用無線周波数の情報をクラスタ内無線周波数通知パケットに搭載して自ＰＣＦクラスタ内の各Ｓｌａｖｅノードへ通知する（ステップＣ１１）。
【００７６】
図７に示すように、Ｓｌａｖｅノードの無線周波数調査部１０７は無線周波数調査指示パケットの受信待ち状態にある（ステップＤ１）。無線周波数調査部１０７は、Ｍａｓｔｅｒノードから無線周波数調査指示パケットを受信したか否かを判定し（ステップＤ２）、無線周波数調査指示パケットを受信しない場合はＭａｓｔｅｒノードからの無線周波数調査指示パケットを待ち受ける。また、Ｍａｓｔｅｒノードから無線周波数調査指示パケットを受信すると、無線周波数調査パケットを近傍ノード（他ＰＣＦクラスタ）へ送信する（ステップＤ３）。そして、無線周波数調査部１０７は、近傍ノードから無線周波数ビジーパケットを受信したか否かを判定し（ステップＤ４）、無線周波数ビジーパケットを受信した場合は、それに含まれる他ＰＣＦクラスタの使用無線周波数の情報を無線周波数調査結果パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ返信する。また、無線周波数ビジーパケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＤ５）、タイムオーバーでない場合は、ステップＤ３に戻ってステップＤ３からステップＤ５の処理を繰り返す。タイムオーバーとなった場合は、“応答なし”を示す情報を無線周波数調査結果パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ返信し処理を終了する。
【００７７】
Ｍａｓｔｅｒノードは、自ＰＣＦクラスタの使用無線周波数を決定すると、近傍クラスタ発見部１０８により接続可能な近傍ＰＣＦクラスタを検出する。
【００７８】
図８に示すように、Ｍａｓｔｅｒノードの近傍クラスタ発見部１０８は、まず近傍ノードに近傍クラスタ発見パケットを送信する（ステップＥ１）。近傍クラスタ発見パケットを送信した近傍クラスタ発見部１０８は、近傍クラスタ応答パケットの受信待ち状態となる（ステップＥ２）。
【００７９】
次に、近傍クラスタ発見部１０８は近傍クラスタ応答パケットを受信したか否かを判定し（ステップＥ３）、近傍クラスタ応答パケットを受信した場合は、そのパケットに含まれる近傍クラスタ情報を保存する（ステップＥ４）。近傍クラスタ情報は、自ＰＣＦクラスタの近傍に存在する他のＰＣＦクラスタを識別するための情報である。近傍クラスタ応答パケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＥ５）、タイムオーバーでない場合は、ステップＥ３に戻ってステップＥ３からステップＥ５の処理を繰り返す。タイムオーバーとなった場合は、Ｓｌａｖｅノードへ近傍クラスタ発見指示パケットを送信する（ステップＥ６）。近傍クラスタ発見指示パケットを受信したＳｌａｖｅノードの近傍クラスタ発見部１０８は、図９に示すフローチャートにしたがって処理を実行する。
【００８０】
近傍クラスタ発見指示パケットを送信したＭａｓｔｅｒノードの近傍クラスタ発見部１０８は、Ｓｌａｖｅノードからの近傍クラスタ応答通知パケットの受信待ち状態となる（ステップＥ７）。
【００８１】
続いて、近傍クラスタ発見部１０８は、Ｓｌａｖｅノードから近傍クラスタ応答通知パケットを受信したか否かを判定し（ステップＥ８）、近傍クラスタ応答通知パケットを受信した場合は、そのパケットに含まれる近傍クラスタ情報を保存する（ステップＥ９）。近傍クラスタ応答通知パケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＥ１０）、タイムオーバーでない場合は、ステップＥ８に戻ってステップＥ８からステップＥ１０の処理を繰り返す。タイムオーバーとなった場合は、近傍クラスタ発見部１０８による処理を終了する。
【００８２】
図９に示すように、Ｓｌａｖｅノードの近傍クラスタ発見部１０８は、Ｍａｓｔｅｒノードからの近傍クラスタ発見指示パケットの受信待ち状態にある（ステップＦ１）。近傍クラスタ発見部１０８は、まずＭａｓｔｅｒノードから近傍クラスタ発見指示パケットを受信したか否かを判定し（ステップＦ２）、近傍クラスタ発見指示パケットを受信しない場合はＭａｓｔｅｒノードからの近傍クラスタ発見指示パケットを待ち受ける。Ｍａｓｔｅｒノードから近傍クラスタ発見指示パケットを受信した場合は、近傍クラスタ発見パケットを近傍ノード（他ＰＣＦクラスタ）へ送信する（ステップＦ３）。そして、近傍ノードから近傍クラスタ応答パケットを受信したか否かを判定し（ステップＦ４）、近傍クラスタ応答パケットを受信した場合は、それに含まれる近傍クラスタ情報を保存する（ステップＦ５）。また、近傍クラスタ応答パケットを受信しない場合は、予め決められた所定時間が過ぎたか（タイムオーバー）否かを判定し（ステップＦ６）、タイムオーバーでない場合は、ステップＦ４に戻ってステップＦ４からステップＦ６の処理を繰り返す。タイムオーバーとなった場合は、保存した近傍クラスタ情報を近傍クラスタ応答通知パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ返信し処理を終了する。
【００８３】
Ｍａｓｔｅｒノードは、近傍クラスタ発見部１０８により近傍クラスタ情報を収集すると、クラスタ間接続部１０９により近傍ＰＣＦクラスタとの通信ルートを決定する。
【００８４】
図１０に示すように、Ｍａｓｔｅｒノードのクラスタ間接続部１０９は、まず収集した近傍クラスタ情報を参照し（ステップＧ１）、各近傍ＰＣＦクラスタとの通信ルートが１つであるか否かを判定する（ステップＧ２）。近傍ＰＣＦクラスタとの通信ルートが１つである場合、ＭａｓｔｅｒノードがそのＰＣＦクラスタと直接接続するときは、Ｍａｓｔｅｒノードからクラスタ接続要求パケットを送信する。また、Ｓｌａｖｅノードを介してそのＰＣＦクラスタと接続する場合は、該Ｓｌａｖｅノードにクラスタ接続要求送信指示パケットを送信する（ステップＧ６）。
【００８５】
一方、近傍ＰＣＦクラスタとの通信ルートが複数存在する場合、クラスタ間接続部１０９は、ホップ数が最小となる通信ルートを選択する（ステップＧ３）。そして、近傍ＰＣＦクラスタとのホップ数が最小となる通信ルートが１つであるか否かを判定し（ステップＧ３）、ホップ数が最小となる通信ルートが１つである場合は上記ステップＧ６の処理へ移行してクラスタ接続要求パケットまたはクラスタ接続要求送信指示パケットを送信する。ホップ数が最小となる通信ルートが複数存在する場合は、近傍クラスタ応答パケットの受信電界強度が最大の通信ルートを選択し（ステップＧ５）、上記ステップＧ６の処理へ移行してクラスタ接続要求パケットまたはクラスタ接続要求送信指示パケットを送信する。クラスタ接続要求送信指示パケットを受信したＳｌａｖｅノードのクラスタ間接続部１０９は、図１１に示すフローチャートにしたがって処理を実行する。
【００８６】
クラスタ接続要求パケットまたはクラスタ接続要求送信指示パケットを送信したＭａｓｔｅｒノードは、他ＰＣＦクラスタからのクラスタ接続応答パケットまたはＳｌａｖｅノードからのクラスタ接続応答結果パケットの受信待ち状態となる（ステップＧ７）。
【００８７】
クラスタ間接続部１０９は、クラスタ接続要求パケットを送信した全てのＰＣＦクラスタからのクラスタ接続応答パケットまたはＳｌａｖｅノードからのクラスタ接続応答結果パケットを受信したか否かを判定し（ステップＧ８）、クラスタ接続応答パケットまたはクラスタ接続応答結果パケットを受信していない場合はこれらのパケットの受信を待ち受ける。クラスタ接続応答パケットまたはクラスタ接続応答結果パケットを受信した場合は処理を終了する。
【００８８】
図１１に示すように、Ｓｌａｖｅノードのクラスタ間接続部１０９は、Ｍａｓｔｅｒノードからのクラスタ接続要求送信指示パケットの受信待ち状態にある（ステップＨ１）。クラスタ間接続１０９は、Ｍａｓｔｅｒノードからクラスタ接続要求送信指示パケットを受信すると、指定された近傍ＰＣＦクラスタへクラスタ接続要求パケットを送信する（ステップＨ２）。そして、近傍ＰＣＦクラスタからクラスタ接続応答パケットを受信したか否かを判定し（ステップＨ３）、クラスタ接続応答パケットを受信しない場合はクラスタ接続応答パケットの受信を待ち受ける。また、クラスタ接続応答パケットを受信した場合は、そのパケットに含まれる情報をクラスタ接続応答結果パケットに搭載して自ＰＣＦクラスタのＭａｓｔｅｒノードへ送信し（ステップＨ４）、該近傍ＰＣＦクラスタとの接続を確立して処理を終了する。
【００８９】
本発明によれば、近傍のノードどうしをポーリング方式による通信を可能に接続し、マスターとして動作する１つのノードとスレーブとして動作する少なくとも１つのノードとから成る複数のポーリングクラスタを形成し、近傍のポーリングクラスタ間にキャリアセンス方式による通信を可能にする通信ルートを設定することで、キャリアセンス方式のみを用いた構成と比べて近傍のノード間のパケット衝突に起因する遅延時間が低減し、ポーリング方式のみを用いた構成と比べてポーリングクラスタ間でのポーリング待ち時間に起因する遅延時間が低減する。したがって、無線マルチホップネットワークにおけるパケットの転送遅延が低減する。
【００９０】
（実施例）
次に本発明の無線マルチホップネットワークの形成方法の実施例について説明する。
【００９１】
本実施例では、図１２に示すように１８台の無線ＬＡＮスイッチＷＳ１〜ＷＳ１８が配置された状態から無線マルチホップネットワークを形成する場合を例にして説明する。
【００９２】
図１２に示すように配置された各無線ＬＡＮスイッチ（ノード）ＷＳ１〜ＷＳ１８は、まず図４に示した手順にしたがって自ノードの近傍ノード数をそれぞれ算出する。その算出結果を表１に示す。
【００９３】
【表１】
0004737396.tif 000002
ＷＳ１〜ＷＳ１８は、自ノードの近傍ノード数を、近傍ノード数通知パケットを用いてそれぞれ近傍ノードへ通知する。
【００９４】
表１に示したように、ＷＳ１〜ＷＳ１８は全てＭａｓｔｅｒノードではなく、かつＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６が最大の近傍ノード数を持っている。したがって、これらのノードが他のノードからのアソシエーション要求パケットを待つことになる。ＷＳ２、ＷＳ３、ＷＳ４、ＷＳ５、ＷＳ６、ＷＳ８、ＷＳ９、ＷＳ１０、ＷＳ１１、ＷＳ１３、ＷＳ１４、ＷＳ１５及びＷＳ１７は、近傍ノードの中で近傍ノード数が最大のノードへアソシエーション要求パケットを送信する。
【００９５】
具体的には、ＷＳ２、ＷＳ３、ＷＳ４及びＷＳ５は、最大の近傍ノード数を持つＷＳ１へアソシエーション要求パケットを送信する。
【００９６】
また、ＷＳ８、ＷＳ９、ＷＳ１０及びＷＳ１１は、ＷＳ７へアソシエーション要求パケットを送信する。ここで、表１に示すように、ＷＳ６では、近傍ノードであるＷＳ１とＷＳ７とがそれぞれ最大（５個）の近傍ノード数を持っている。そのため、ＷＳ６は、近傍ノード応答パケットの受信電界強度がより大きいノードへアソシエーション要求パケットを送信する。ここでは、ＷＳ１よりもＷＳ７から強い受信電界強度で近傍ノード応答パケットを受信したと仮定する。したがって、ＷＳ６はＷＳ７へアソシエーション要求パケットを送信する。
【００９７】
ＷＳ１４及びＷＳ１５は、ＷＳ１２へアソシエーション要求パケットを送信する。また、ＷＳ１３、ＷＳ１７及びＷＳ１８は、ＷＳ１６へアソシエーション要求パケットを送信する。
【００９８】
アソシエーション要求パケットを受信したＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６はアソシエーション応答パケットを送信元ノードへそれぞれ返信する。アソシエーション要求パケットを受信したＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６は、ＰＣＦクラスタのＭａｓｔｅｒノードとなる。一方、アソシエーション応答パケットを受信した他のノードは、ＰＣＦクラスタのＳｌａｖｅノードとなる。
【００９９】
次に、Ｍａｓｔｅｒに選択されたＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６は、それぞれ自ＰＣＦクラスタ内で使用する無線周波数を決定する。各ＰＣＦクラスタ内で使用する無線周波数は、図６及び図７に示した手順にしたがって決定する。ここでは、第１のＰＣＦクラスタが無線周波数ｆ１を使用し、第２のＰＣＦクラスタが無線周波数ｆ２を使用し、第３のＰＣＦクラスタが無線周波数ｆ３を使用し、第４のＰＣＦクラスタが無線周波数ｆ４を使用する。
【０１００】
続いて、Ｍａｓｔｅｒに選択されたＷＳ１、ＷＳ７、ＷＳ１２及びＷＳ１６は、図８及び図９に示した手順に従い、近傍クラスタ発見パケット及び近傍クラスタ発見指示パケットを用いて近傍ＰＣＦクラスタを検出する。近傍ＰＣＦクラスタの検出結果を表２に示す。
【０１０１】
【表２】
0004737396.tif 000003
表２に示す例では、ＷＳ１をＭａｓｔｅｒノードとする第１のＰＣＦクラスタでは第２のＰＣＦクラスタに対する通信ルートを２つ発見する。また、ＷＳ７をＭａｓｔｅｒノードとする第２のＰＣＦクラスタでは、第１のＰＣＦクラスタに対する２つの通信ルートと、第３のＰＣＦクラスタ及び第４のＰＣＦクラスタに対する通信ルートをそれぞれ１つずつ発見する。また、ＷＳ１２をＭａｓｔｅｒノードとする第３のＰＣＦクラスタでは、第２のＰＣＦクラスタ及び第４のＰＣＦクラスタに対する通信ルートをそれぞれ１つずつ発見する。また、ＷＳ１６をＭａｓｔｅｒノードとする第４のＰＣＦクラスタでは、第２のＰＣＦクラスタ及び第３のＰＣＦクラスタに対する通信ルートをそれぞれ１つずつ発見する。
【０１０２】
ここで、第１のＰＣＦクラスタと第２のＰＣＦクラスタ間の通信ルートが複数存在する。この場合、第１のＰＣＦクラスタ及び第２のＰＣＦクラスタのＭａｓｔｅｒノードは、ホップ数が最小の通信ルートを選択する。表２に示す例では、第１のＰＣＦクラスタから第２のＰＣＦクラスタへ送信する場合、ＷＳ１からＷＳ６を通る通信ルートが最短である。また、第２のＰＣＦクラスタから第１のＰＣＦクラスタへ送信する場合は、ＷＳ６からＷＳ１を通る通信ルートが最短である。
【０１０３】
各ＰＣＦクラスタのＭａｓｔｅｒノードは、近傍ＰＣＦクラスタに対する最小の通信ルートを選択し、クラスタ接続要求パケットまたはクラスタ接続要求送信指示パケットを送信し、クラスタ接続応答パケットまたはクラスタ接続応答結果パケットを受信することで、近傍ＰＣＦクラスタとの接続を確立する。
【０１０４】
図１３は以上の手順によって形成された無線マルチホップネットワークの一例を示している。この図１３に示した無線マルチホップネットワークのＷＳ２からＷＳ１５へパケットが転送される様子を図１４に示す。
【０１０５】
図１４に示すように、図１３に示した無線マルチホップネットワークにおいて、ＷＳ２からＷＳ１５へパケットを転送する場合、第１のＰＣＦクラスタでは、ＷＳ２からＷＳ１、ＷＳ１からＷＳ６の順にパケットが転送される。図１４に示すように、第１のＰＣＦクラスタでは、ＭａｓｔｅｒノードであるＷＳ１によってＷＳ２からＷＳ１に対するパケット転送が制御されるが、ＷＳ１からＷＳ６へはキャリアセンス方式でパケットが転送されるためにポーリング待ち時間が発生しない。
【０１０６】
また、第２のＰＣＦクラスタでは、ＷＳ６からＷＳ７、ＷＳ７からＷＳ１０の順にパケットが転送されるが、いずれもキャリアセンス方式でパケットが転送されるためにポーリング待ち時間が発生しない。
【０１０７】
さらに、第３のＰＣＦクラスタでは、ＷＳ１０からＷＳ１２、ＷＳ１２からＷＳ１５の順にパケットが転送されるが、ＷＳ１０からＷＳ１２へはキャリアセンス方式でパケットが転送されるためにポーリング待ち時間が発生しない。但し、ＷＳ１０からＷＳ１２に対するパケット転送が終了してからＷＳ１２からＷＳ１５に対するパケット転送が始まるまでにポーリング待ち時間が生じる。しかしながら、図１５に示した従来の無線マルチホップネットワークに比べてポーリング待ち時間が大幅に低減しているため、本発明の形成方法によって構成された無線マルチホップネットワークでは、パケットの転送遅延を大幅に低減できる。
【０１０８】
なお、上記説明では、ＰＣＦクラスタを形成する際に、Ｍａｓｔｅｒノードが所定のアソシエーション数を超える場合にアソシエーション応答パケットを返信しないことでＰＣＦクラスタを構成するＳｌａｖｅノード数を制限する方法を示した。
【０１０９】
しかしながら、Ｍａｓｔｅｒノードとなり得る複数のノードが存在する場合、すなわち近傍ノード数が最大のノードが複数存在する場合、Ｓｌａｖｅノードは、アソシエーション要求パケットを送信する前に、それらのノードに対して現在のアソシエーション数を問い合わせ、その問い合わせ結果から、最もアソシエーション数の少ないノードへアソシエーション要求パケットを送信してもよい。その場合、各ＰＣＦクラスタに所属するＳｌａｖｅノード数が均一になるため、各Ｍａｓｔｅｒノードの処理負荷が平滑化されるという効果がある。
【図面の簡単な説明】
【０１１０】
【図１】本発明の無線マルチホップネットワークの形成方法の手順を示すフローチャートである。
【図２】本発明の無線マルチホップネットワークを形成方法で用いるパケットの一構成例を示す模式図である。
【図３】本発明の無線マルチホップネットワークを構成するノードの一構成例を示すブロック図である。
【図４】図３に示した近接ノード発見部の処理手順を示すフローチャートである。
【図５】図３に示したアソシエーション実行部の処理を示す状態遷移図である。
【図６】図３に示した無線周波数調査部の処理手順を示すフローチャートである。
【図７】図３に示した無線周波数調査部の処理手順を示すフローチャートである。
【図８】図３に示した近傍クラスタ発見部１０８の処理手順を示すフローチャートである。
【図９】図３に示した近傍クラスタ発見部１０８の処理手順を示すフローチャートである。
【図１０】図３に示したクラスタ間接続部の処理手順を示すフローチャートである。
【図１１】図３に示したクラスタ間接続部の処理手順を示すフローチャートである。
【図１２】本発明の無線マルチホップネットワークを構成するノードの配置例を示すブロック図である。
【図１３】図１２に示すノードの配置例から形成した本発明の無線マルチホップネットワークを一構成例を示すブロック図である。
【図１４】図１３に示した無線マルチホップネットワークのパケット転送時における遅延時間の発生例を示す模式図である。
【図１５】従来の無線マルチホップネットワークの一構成例を示すブロック図である。
【図１６】図１５に示した無線マルチホップネットワークのパケット転送時における遅延時間の発生例を示す模式図である。
【符号の説明】
【０１１１】
１００    ノード
１０１    第１の無線インターフェース
１０２    第２の無線インターフェース
１０３    有線インターフェース
１０４    Master/Slave動作部
１０５    近傍ノード発見部
１０６    アソシエーション実行部
１０７    無線周波数調査部
１０８    近傍クラスタ発見部
１０９    クラスタ間接続部
ＷＳ１〜ＷＳ１８    無線ＬＡＮスイッチ
【図１】
0004737396.tif 000004
【図２】
0004737396.tif 000005
【図３】
0004737396.tif 000006
【図４】
0004737396.tif 000007
【図５】
0004737396.tif 000008
【図６】
0004737396.tif 000009
【図７】
0004737396.tif 000010
【図８】
0004737396.tif 000011
【図９】
0004737396.tif 000012
【図１０】
0004737396.tif 000013
【図１１】
0004737396.tif 000014
【図１２】
0004737396.tif 000015
【図１３】
0004737396.tif 000016
【図１４】
0004737396.tif 000017
【図１５】
0004737396.tif 000018
【図１６】
0004737396.tif 000019