(57)【要約】【課題】  メッシュネットワークのスループットを増大させ効率を高めることのできるチャネル割り当て方法を提供することを目的とする。【解決手段】  メッシュネットワークを構成する個々のアクセスポイント内で複数のインタフェースのチャネルをトラフィック状況に合わせて動的に割り当てる方法であって、自アクセスポイントのノード内情報を取得する工程と、取得した情報に基づき通信量が多いアクセスポイント同士を同じチャネルセットを持つクラスタに含める工程とを備える。【選択図】  図４
2006050549.tif 000002
【特許請求の範囲】
【請求項１】
メッシュネットワークを構成する個々のアクセスポイント内で複数のインタフェースのチャネルをトラフィック状況に合わせて動的に割り当てる方法であって、
自アクセスポイントのノード内情報を取得する工程と、
取得した情報に基づき通信量が多いアクセスポイント同士を同じチャネルセットを持つクラスタに含める工程とを備えたことを特徴とするチャネル割り当て方法。
【請求項２】
上記ノード内情報は、
各チャネルの使用状況および品質を示すチャネル情報と、
各アクセスポイント間の通信セッションを示す通信相手情報と、
自アクセスポイントの通信する相手アクセスポイントとの通信量もしくはチャネルの混雑度を表すトラフィック情報と、
他システムによる干渉の存在の有無もしくは程度の情報との、すべてまたは一部を含むことを特徴とする請求項１に記載のチャネル割り当て方法。
【請求項３】
上記トラフィック情報は、
送受信したパケット数、パケットサイズ、送受信変調方式から算出したチャネル占有時間割合を含むことを特徴とする請求項２に記載のチャネル割り当て方法。
【請求項４】
上記トラフィック情報にＱｏＳの重み付けをすることを特徴とする請求項２に記載のチャネル割り当て方法。
【請求項５】
上記トラフィック情報測定時に、他システムから受信したパケットもしくは他システムによるチャネル占有時間を観測し、他システムの干渉を判定することを特徴とする請求項２乃至４のいずれか一項に記載のチャネル割り当て方法。
【請求項６】
他のアクセスポイントとの間で統計情報を交換する工程を備えたことを特徴とする請求項１乃至５のいずれか一項に記載のチャネル割り当て方法。
【請求項７】
上記メッシュネットワーク内の全てのアクセスポイントとの間で統計情報を交換することを特徴とする請求項６に記載のチャネル割り当て方法。
【請求項８】
近隣のアクセスポイントとのみ統計情報を交換することを特徴とする請求項６に記載のチャネル割り当て方法。
【請求項９】
上記統計情報は、各チャネルの使用状況および品質を示すチャネル情報と、
各アクセスポイント間の通信セッションを示す通信相手情報と、
自アクセスポイントの通信する相手アクセスポイントとの通信量もしくはチャネルの混雑度を表すトラフィック情報とを含むことを特徴とする請求項６乃至８のいずれか一項に記載のチャネル割り当て方法。
【請求項１０】
上記クラスタは、上記チャネルセット内に少なくとも一つの共通のチャネルを持つことを特徴とする請求項１乃至９のいずれか一項に記載のチャネル割り当て方法。
【請求項１１】
上記クラスタは、上記チャネルセット内に全体としての共通のチャネルを持たず、他の少なくとも一つのクラスタとの間の共通のチャネルを持つことを特徴とする請求項１乃至９のいずれか一項に記載のチャネル割り当て方法。
【請求項１２】
自己のノード内情報を取得するノード内情報取得部と、
上記ノード内情報に基づいてクラスタ化するノードを判断するクラスタ化判断部と、
上記クラスタ化判断部の判断結果に基づいてインタフェースのチャネルを変更するチャネル変更部とを備えたことを特徴とするアクセスポイント。
【請求項１３】
他のアクセスポイントとの間で統計情報を交換する統計情報交換部を備え、
上記クラスタ化判断部は上記ノード内情報および上記統計情報に基づいてクラスタ化するノードを判断することを特徴とする請求項１２に記載のアクセスポイント。
【請求項１４】
経路制御プロトコルへチャネル変更の通知を行う制御線を備え、
チャネル変更前に一時的に上記経路制御プロトコルにチャネル変更の通知を行うことで、上記経路制御プロトコルがチャネル変更の対象となるインタフェースと別のインタフェースを通信に使用することを特徴とする請求項１２または１３のいずれか一項に記載のアクセスポイント。
【請求項１５】
経路制御プロトコルへチャネル変更の通知を行う制御線を備え、
チャネル変更前から所定の時間にわたり、チャネル変更の対象となるインタフェースによる経路制御信号のやりとりを停止することを特徴とする請求項１２または１３のいずれか一項に記載のアクセスポイント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信機能を有する複数のアクセスポイントにより構成されるメッシュネットワーク（アドホックネットワーク、自律分散ネットワーク）におけるアクセスポイントのチャネル割り当て方法に関する。
【背景技術】
【０００２】
メッシュネットワークの広範な応用が考えられており、例えば、家庭内のテレビ、ＤＶＤプレイヤ等にアクセスポイントの機能を設け、ケーブル等による接続を行うことなく、テレビからの要求に応じてＤＶＤプレイヤからテレビに動画・音声データ等を送信するような用途が想定されている。このような用途に使用可能とするためには、アクセスポイント間のデータ伝送速度を高速化させる必要がある。
【０００３】
図１はアクセスポイントのインタフェース数と同数のチャネルを設けた従来のメッシュネットワークの例を示す図であり、アクセスポイントＡＰ１〜ＡＰ４はそれぞれ２つのインタフェースを有しており、同じ周波数ｆ１、ｆ２のチャネルに設定されている。なお、チャネル数は図示の２つに限られず、インタフェース数が多い場合にはそれに応じて増やすことができる。
【０００４】
このように、各アクセスポイントに複数のチャネルを割り当てることで、別のチャネルを使用して他のアクセスポイントと同時に通信することが可能となり、各アクセスポイント間の伝送速度を高速化することができる。なお、この場合、インタフェース数とチャネル数が同数なので、アクセスポイント毎に個別に異なるチャネルを割り当てる必要はない。
【０００５】
図２はアクセスポイントのインタフェース数よりも多いチャネルを設けた従来のメッシュネットワークの例を示す図である。チャネルを増やすことでメッシュネットワークの効率は一般的に上がるが、全てのチャネルを各アクセスポイントのインタフェースで同時に使用することはできないため、例えば図２では、アクセスポイントＡＰ１、ＡＰ４を周波数ｆ１、ｆ３のチャネルセットを使うクラスタに入れ、アクセスポイントＡＰ３、ＡＰ２を周波数ｆ１、ｆ２のチャネルセットを使うクラスタに入れるようにしている。ここで、クラスタとは、同じチャネルセットを使うノードの論理的な集まり（グループ）である。
【０００６】
この場合、同じクラスタ内のアクセスポイントＡＰ１、ＡＰ４間またはアクセスポイントＡＰ３、ＡＰ２間では、２つのチャネルを同時に使用できるため高速に通信が行える。なお、異なるクラスタに属するアクセスポイント間の通信は共通の周波数ｆ１のチャネルしか使えないので転送速度は低下する。
【０００７】
図３は従来のトポロジに基づくクラスタリングの例を示す図であり、メッシュネットワーク上の至近距離にあるアクセスポイントを同じクラスタに入れるようにしたものである。すなわち、アクセスポイントＡＰ１〜ＡＰ３を第１のクラスタに入れ、アクセスポイントＡＰ４〜ＡＰ７を第２のクラスタに入れ、アクセスポイントＡＰ８〜ＡＰ１０を第３のクラスタに入れるようにしている。どの範囲のアクセスポイントを同じクラスタにするかといった基準や制御シーケンスについては各社によって差があるが（非特許文献１、２を参照。）、このようなトポロジによるチャネルの割り当て（クラスタリング）は一般に制御が簡単であるという利点がある。
【非特許文献１】「マルチホップ無線ネットワークにおける自律的ネットワーク構築法の特性評価」水野晃平  片山譲  中山正芳  清水雅史、電子情報通信学会  信学技報Vol.102 No.281 ISSN 0913-5685  RCS2002-137(2002-08)
【非特許文献２】”Maximizing Aggregate Throughput in 802.11 Mesh Networks with Physical Carrier Sensing and Two-Radio Multi-Channel Clustering”, Jing Zhu, S. Roy, Xingang Guo, and W. Steven Conner, To appear in Proceedings of NSF-RPI Workshop on Pervasive Computing and Networking, April 29-30, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述したように、従来はメッシュネットワーク上のアクセスポイントに対してトポロジに基づいてチャネルの割り当てを行うようにしており、同じクラスタ内のアクセスポイント間の通信は使えるチャネルが多いため高速に行えるものであったが、クラスタをまたがったアクセスポイント間の通信は使えるチャネルが少ないため高速に行えないものであった。
【０００９】
この点、メッシュネットワークにおける通信の状況は固定的ではなく、その時々の状況によって変化するものであるため、大容量の通信がクラスタをまたがって発生する場合も多く、その際のスループットの低下が問題となり、メッシュネットワークの効率を悪化させる原因となっていた。
【００１０】
本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、メッシュネットワークのスループットを増大させ効率を高めることのできるチャネル割り当て方法を提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するため、本発明にあっては、請求項１に記載されるように、メッシュネットワークを構成する個々のアクセスポイント内で複数のインタフェースのチャネルをトラフィック状況に合わせて動的に割り当てる方法であって、自アクセスポイントのノード内情報を取得する工程と、取得した情報に基づき通信量が多いアクセスポイント同士を同じチャネルセットを持つクラスタに含める工程とを備えるようにしている。
【００１２】
また、請求項２に記載されるように、上記ノード内情報は、各チャネルの使用状況および品質を示すチャネル情報と、各アクセスポイント間の通信セッションを示す通信相手情報と、自アクセスポイントの通信する相手アクセスポイントとの通信量もしくはチャネルの混雑度を表すトラフィック情報と、他システムによる干渉の存在の有無もしくは程度の情報との、すべてまたは一部を含むようにすることができる。
【００１３】
また、請求項３に記載されるように、上記トラフィック情報は、送受信したパケット数、パケットサイズ、送受信変調方式から算出したチャネル占有時間割合を含むようにすることができる。
【００１４】
また、請求項４に記載されるように、上記トラフィック情報にＱｏＳの重み付けをするようにすることができる。
【００１５】
また、請求項５に記載されるように、上記トラフィック情報測定時に、他システムから受信したパケットもしくは他システムによるチャネル占有時間を観測し、他システムの干渉を判定するようにすることができる。
【００１６】
また、請求項６に記載されるように、他のアクセスポイントとの間で統計情報を交換する工程を備えるようにすることができる。
【００１７】
また、請求項７に記載されるように、上記メッシュネットワーク内の全てのアクセスポイントとの間で統計情報を交換するようにすることができる。
【００１８】
また、請求項８に記載されるように、近隣のアクセスポイントとのみ統計情報を交換するようにすることができる。
【００１９】
また、請求項９に記載されるように、上記統計情報は、各チャネルの使用状況および品質を示すチャネル情報と、各アクセスポイント間の通信セッションを示す通信相手情報と、自アクセスポイントの通信する相手アクセスポイントとの通信量もしくはチャネルの混雑度を表すトラフィック情報とを含むようにすることができる。
【００２０】
また、請求項１０に記載されるように、上記クラスタは、上記チャネルセット内に少なくとも一つの共通のチャネルを持つようにすることができる。
【００２１】
また、請求項１１に記載されるように、上記クラスタは、上記チャネルセット内に全体としての共通のチャネルを持たず、他の少なくとも一つのクラスタとの間の共通のチャネルを持つようにすることができる。
【００２２】
また、請求項１２に記載されるように、自己のノード内情報を取得するノード内情報取得部と、上記ノード内情報に基づいてクラスタ化するノードを判断するクラスタ化判断部と、上記クラスタ化判断部の判断結果に基づいてインタフェースのチャネルを変更するチャネル変更部とを備えるアクセスポイントとして構成することができる。
【００２３】
また、請求項１３に記載されるように、他のアクセスポイントとの間で統計情報を交換する統計情報交換部を備え、上記クラスタ化判断部は上記ノード内情報および上記統計情報に基づいてクラスタ化するノードを判断するようにすることができる。
【００２４】
また、請求項１４に記載されるように、経路制御プロトコルへチャネル変更の通知を行う制御線を備え、チャネル変更前に一時的に上記経路制御プロトコルにチャネル変更の通知を行うことで、上記経路制御プロトコルがチャネル変更の対象となるインタフェースと別のインタフェースを通信に使用するようにすることができる。
【００２５】
また、請求項１５に記載されるように、経路制御プロトコルへチャネル変更の通知を行う制御線を備え、チャネル変更前から所定の時間にわたり、チャネル変更の対象となるインタフェースによる経路制御信号のやりとりを停止するようにすることができる。
【発明の効果】
【００２６】
本発明にあっては、各ノードの物理的な位置関係によるトポロジ情報を元にクラスタリングするのではなく、通信量が多いアクセスポイント同士を同じクラスタにするという動的かつ論理的なクラスタリングを行うことで、メッシュネットワークのスループットを増大させ効率を高めることができる。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の好適な実施形態につき図面を参照して説明する。なお、実施形態として、本発明をＩＥＥＥ８０２．１１（Institute of Electrical and Electronics Engineers 802.11）規格の無線ＬＡＮに適用した場合を例にとって説明する。
【００２８】
図４は本発明のチャネル割り当て方法を適用したアクセスポイントの構成例を示す図であり、クラスタリングに関する機能部のみを示しており、その他の機能部は省略してある。
【００２９】
図４において、アクセスポイントＡＰ１は、自己のノード内情報を取得するノード内情報取得部１と、他のアクセスポイントＡＰ２等との間で統計情報を交換する統計情報交換部２と、ノード内情報および統計情報に基づいてクラスタ化するノード（アクセスポイント）を判断し、必要に応じて他のノードにクラスタ化を要求して承認を得るクラスタ化判断部３と、クラスタ化判断部３の判断結果に基づいてインタフェースのチャネルを変更するチャネル変更部４とを備えている。また、チャネル変更部４は、他アクセスポイントからの信号を中継する際の経路制御を行う経路制御モジュール５に対してチャネル通知信号を与える制御線を備えている。なお、他のアクセスポイントＡＰ２等との間で統計情報を交換せずにクラスタリングを実行する場合には統計情報交換部２はなくてもよい。
【００３０】
ここで、ノード内情報取得部１によって取得するノード内情報としては次の情報が含まれる。
【００３１】
・チャネル情報・・・各チャネルの使用状況および品質を示す情報。具体的には、そのチャネルを使用しているアクセスポイントの送信するビーコンの数や平均電力強度、各アクセスポイントや各アクセスポイントに所属する各端末（ステーション）がそのチャネルを使用して送信するデータフレームの数やデータフレームの平均電力強度、他のシステムの使用や白色雑音などによって発生する干渉やノイズの量などが挙げられる。
【００３２】
・通信相手情報・・・各アクセスポイント間の通信セッションを示す情報。具体的には、通信相手を示すＩＤ情報（ＩＰアドレスやＭＡＣアドレスなど）、通信時に使用する無線変調方式や使用する通信速度（ビットレート）、通信に使用するチャネル情報などが挙げられる。
【００３３】
・トラフィック情報・・・自アクセスポイントの通信する相手アクセスポイントとの通信量もしくはチャネルの混雑度を表す情報。具体的には、各アクセスポイントや各アクセスポイントに所属する各端末の送受信したデータフレームのフレーム数やフレームサイズ、フレームを送信するのに使用した変調方式、データフレームの送受信のためにチャネルを占有した時間やその単位時間当たりの割合などが挙げられる。
【００３４】
なお、通信量が多いことがあらかじめ分かっている場合や高品質の通信が必要で高いＱｏＳ（Quality of Service）を実現したい場合、優先度付けされたノード情報を上の層からもらうようにすることもできる。このノード情報もクラスタリングするノードの判断に使用可能である。
【００３５】
また、高品質の通信が必要な場合に、例えばＩＥＥＥ８０２．１１ｅ規格やＩＥＴＦ  ＤｉｆｆＳｅｒｖｅ規格などを適用することでＱｏＳを実現することが考えられるが、この場合にフレーム毎にＱｏＳ値を記入するフィールドがあるため、フレーム毎にＱｏＳ値を判別し、高ＱｏＳに設定されているデータフレームのサイズを過大に計測することで、高ＱｏＳの通信路のトラフィックを過大に見せ、チャネル割り当てされやすくすることも可能である。具体的には、高いＱｏＳ値の設定されたデータフレームは、データフレームのサイズを例えば３倍多く数えることによって実現することが可能である。この処理を行うことによって、高品質な通信が必要なビデオ会議などの動画像通信やＶｏＩＰ（Voice over Internet Protocol）を使用した通話などの通信が存在する場合はチャネルが割り当てられやすくなることになり、高品質な通信を実現することが可能となる。また、高ＱｏＳの通信がない場合は、一般的な通信のトラフィック量でチャネルが割り当てられるため、普段から高ＱｏＳが流れる経路にチャネルを割り当てておく必要がなく、柔軟にＱｏＳを考慮したチャネル割り当てが可能になるという利点がある。
【００３６】
図５はＩＥＥＥ８０２．１１ｅ規格のＱｏＳに対応した場合のトラフィック情報の値の計算方法の例を示す図である。図５に示す式は、アクセスポイントＡ、Ｂ間のＩＥＥＥ８０２．１１ａのインタフェースによるリンクのトラフィック情報ＴＩを表しており、音声、動画等に対応するアクセスカテゴリＡＣ０、ＡＣ１、ＡＣ２、ＡＣ３の各トラフィック量に重み付けのための係数ａ、ｂ、ｃ、ｄをかけて合計し、ＡＢ間の通信速度で割って求めるようにしている。なお、係数ａ〜ｄは、例えば、ａ＝１、ｂ＝２、ｃ＝６、ｄ＝１０といった値となる。
【００３７】
また、計測するトラフィック情報であるが、例えばＩＥＥＥ８０２．１１システムでは、通信路の伝搬状況によって適応的に変調方式を変更する適応変調を行っており、通信品質がよいときは高速通信が可能な変調方式を使用し、伝搬状況が悪化した場合は、通信速度は低いがエラー耐性が強い変調方式を使用することで、環境に適応した通信を実現している。
【００３８】
ここで、伝搬路状況がよく高速な通信をしているリンクと、伝搬状況が悪く通信速度を下げているリンクとで、同じ量のデータを通信した場合を考えると、送受信したデータ量だけを見た場合には、どちらのリンクも同量のトラフィックが流れている。しかし、実際の無線状況では、両方のリンクによって無線チャネルにかかる負荷は異なる。伝搬状況が悪く通信速度を下げているリンクでは、より多くの無線チャネルリソースを使用してデータ通信をしている。
【００３９】
実際の通信では、ネットワーク内の複数のリンクで通信することが考えられるので、上記の点を考えるとより効率的な無線チャネル割り当てを行うためには、トラフィック情報には、送受信したデータ量だけではなく、実際に無線チャネルを占有した時間割合も計測する必要がある。
【００４０】
実際に無線チャネルを占有した時間割合を計測するためには、次の２つの方法が挙げられる。
【００４１】
一つは、実際に直接自ノードの送信および受信している時間を計測し、それを元に単位時間当たりどの程度の無線チャネルを占有したかを計測する方法である。
【００４２】
もう一つは、統計的に送受信したデータのサイズとパケット数および送信に使用したビットレートから、チャネル占有時間割合を計算する方法である。
【００４３】
送信および受信した情報量の総量を使用したビットレートで割ることで、その情報量を送信するのに消費した無線チャネルの時間を算出することが可能である。送受信した情報量の総量は、パケット数およびパケットのサイズから計測することが可能である。パケット毎に送信バイト数とビットレートから送受信時間を計算し、足し合わせていく方法と、平均的な送受信パケットサイズと送信パケット数、使用ビットレートから定期的に計算する方法の二つの方法がある。前者は細かい変化を計算することが可能であるという特徴があり、後者は定期的に計算するだけでよいので処理負荷が低いという特徴がある。
【００４４】
トラフィック情報の測定と同時に、受信したパケットの送信元アドレスやフレーム内のＳＳＩＤ（Service Set Identifier）フィールドやグループを判別することが可能なメッシュネットワークを表すＩＤ情報から他システムからのパケットを判別することが可能である。また、他システムによるチャネル占有時間を観測することで、他システムによる無線帯域占有割合を知ることが可能である。この情報を利用し、高干渉時にはチャネル変更を行うことで、他システムの干渉を回避することができる。また、高干渉時にトラフィック情報の中に干渉の通知の情報を含ませることで、他ノードにも干渉の存在を知らせ、チャネル変更を促すことが可能である。これは、伝搬状況や無線状況が異なるメッシュネットワークで、干渉の存在の情報をネットワーク内で共有できるという利点がある。
【００４５】
また、統計情報交換部２で交換する統計情報には、各ノード内で取得したノード内情報や情報の履歴を統計的に処理した情報、例えば、移動平均値やデジタルフィルタを通した後の情報や、他ノードと情報交換することによって得られた、自ノードだけでは取得できないネットワーク全体のトラフィックやチャネル混雑度の分布を取得することが可能となる情報が含まれる。
【００４６】
クラスタ化（クラスタリング）に際して他のノードとの間での統計情報の交換の仕方は大別して次の３方式に分かれる。
【００４７】
（１）全てのノードと統計情報を交換
（２）近隣のノードとのみ統計情報を交換
（３）他のノードと統計情報を交換しない（ノード内情報のみで判断）
図６はアクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その１）であり、上記の（１）（２）に対応する全てもしくは近隣のノードと統計情報を交換する場合の処理を示している。
【００４８】
図６において、先ずクラスタリングの開始条件が満たされるのを待つ（ステップＳ１）。クラスタリングの開始条件としては、一定時間毎に周期的にクラスタリング処理を開始する場合には一定時間の経過となり、ネットワークトポロジやルーティングの変更した際にクラスタリング処理を開始する場合にはルーティング層などの他の層から指示があった場合となり、通信断や通信開始によるトラフィック量が変動した際にクラスタリング処理を開始する場合には、交換する統計情報の受信・計測時や統計情報の値や変化量がある閾値を超えた場合となる。ここで、複数のノードが同時にクラスタリング処理を開始すると同じチャネルを選択してしまう可能性があるため、クラスタリング開始条件クリア後ランダム時間後にクラスタリング処理を開始する。
【００４９】
開始条件が満たされてクラスタリング処理が開始すると、ノード内情報取得部１（図４）によりノード内情報を取得する（ステップＳ２）。
【００５０】
次いで、統計情報交換部２（図４）により他のアクセスポイントと統計情報を交換し、通信相手情報については通信量でランキング化する（ステップＳ３）。
【００５１】
次いで、取得したノード内情報および統計情報に基づき、クラスタ化判断部３（図４）により、同じクラスタになるノードを選定する（ステップＳ４）。この際、ルーティングのパス（path）を増やすこと、混んでいるパスを分散してスループットを上げること、通信の多いノードと同じ周波数を割り当ててスループットを上げること、特定のノードが隠れ端末やさらし端末の配置になっているために干渉が起こり、スループットが低下することを回避すること、通信の多いノード間（リンク）で使用している周波数と別の周波数を使用することで、衝突確立や送信待ちによって発生するスループット低下を回避すること等をクラスタリングないしはチャネル割り当ての目標とする。
【００５２】
そして、新しいクラスタ化が必要であるか否かを判断し（ステップＳ５）、必要ない場合（現状のままで変更がない場合）はクラスタリング開始条件待ち（ステップＳ１）に戻る。
【００５３】
また、新しいクラスタ化が必要である場合には、チャネル変更部４（図４）によりインタフェースのチャネルを変更し、クラスタ化を実行する（ステップＳ６）。この際、電波干渉を避けるために近くのクラスタとかぶらないチャネルを選択するとともに、チャネル品質に応じてより適切なチャネルを選択することができる。なお、クラスタは同じチャネルセットを使うことが条件であるが、クラスタ内の全てのノードが同じチャネルを使う必要はない。例えば、インタフェースが２つである場合であっても、３つ以上の周波数のチャネルセットを用いることができる。この場合は、そのチャネルセットの中から実際に割り当てるチャネルをノード毎に決定する。インタフェース数がノード毎に異なる場合も同様である。
【００５４】
そして、チャネルの変更後、再びクラスタリング開始条件待ち（ステップＳ１）に戻る。
【００５５】
なお、チャネルの変更はクラスタ化に際してだけではなく、クラスタ化を行った後においてもチャネルの品質等に応じて適宜に変更することができる。
【００５６】
図７はアクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その２）であり、他のノードと統計情報を交換せずにノード内情報のみで判断する場合の処理を示している。
【００５７】
図７において、先ずクラスタリングの開始条件が満たされるのを待つ（ステップＳ１１）。クラスタリングの開始条件としては、一定時間毎に周期的にクラスタリング処理を開始する場合には一定時間の経過となり、ネットワークトポロジやルーティングの変更した際にクラスタリング処理を開始する場合にはルーティング層などの他の層から指示があった場合となり、通信断や通信開始によるトラフィック量が変動した際にクラスタリング処理を開始する場合には、交換する統計情報の受信・計測時や統計情報の値や変化量がある閾値を超えた場合となる。ここで、複数のノードが同時にクラスタリング処理を開始すると同じチャネルを選択してしまう可能性があるため、クラスタリング開始条件クリア後ランダム時間後にクラスタリング処理を開始する。
【００５８】
開始条件が満たされてクラスタリング処理が開始すると、ノード内情報取得部１（図４）によりノード内情報を取得する（ステップＳ１２）。
【００５９】
次いで、取得したノード内情報に基づき、クラスタ化判断部３（図４）により、同じクラスタにしたいノードを選定する（ステップＳ１３）。この際、ルーティングのパス（path）を増やすこと、混んでいるパスを分散してスループットを上げること、通信の多いノードと同じ周波数を割り当ててスループットを上げること、特定のノードが隠れ端末やさらし端末の配置になっているために干渉が起こり、スループットが低下することを回避すること、通信の多いノード間（リンク）で使用している周波数と別の周波数を使用することで、衝突確立や送信待ちによって発生するスループット低下を回避すること等をクラスタリングないしはチャネル割り当ての目標とする。
【００６０】
そして、新しいクラスタ化が必要であるか否かを判断し（ステップＳ１４）、必要ない場合（現状のままで変更がない場合）はクラスタリング開始条件待ち（ステップＳ１１）に戻る。
【００６１】
また、新しいクラスタ化が必要である場合には、クラスタ化判断部３（図４）により同じクラスタにしたい他のノードにクラスタ化を要求する（ステップＳ１５）。
【００６２】
クラスタ化の要求が他のノードにより承認されなかった場合はクラスタリング開始条件待ち（ステップＳ１１）に戻る。
【００６３】
また、クラスタ化の要求が他のノードにより承認された場合は、チャネル変更部４（図４）によりインタフェースのチャネルを変更し、クラスタ化を実行する（ステップＳ１７）。そして、再びクラスタリング開始条件待ち（ステップＳ１１）に戻る。
【００６４】
なお、チャネルの変更はクラスタ化に際してだけではなく、クラスタ化を行った後においてもチャネルの品質等に応じて適宜に変更することができる。
【００６５】
図８はアクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その３）である。
【００６６】
図８において、ネットワーク内の各ノードは、立ち上げ後随時統計情報を取得し（ステップＳ２１）、イベントが発生する毎に他のノードと統計情報を交換する（ステップＳ２２）。ここで、イベントとは、具体的には、一定時間毎に周期的に統計情報を交換するために統計情報を送信する場合には一定時間の経過となり、トラフィックの変動を条件として統計情報を交換するために統計情報を送信する場合には、取得しているノード内情報の変化量や絶対値が閾値を超えた場合などがイベントとして挙げられる。
【００６７】
これと並行して、クラスタリングの開始条件が満たされるのを待つ（ステップＳ２３）。クラスタリングの開始条件としては、一定時間毎に周期的にクラスタリング処理を開始する場合には一定時間の経過となり、ネットワークトポロジやルーティングの変更した際にクラスタリング処理を開始する場合にはルーティング層などの他の層から指示があった場合となり、通信断や通信開始によるトラフィック量が変動した際にクラスタリング処理を開始する場合には、交換する統計情報の受信・計測時や統計情報の値や変化量がある閾値を超えた場合となる。ここで、複数のノードが同時にクラスタリング処理を開始すると同じチャネルを選択してしまう可能性があるため、クラスタリング開始条件クリア後ランダム時間後にクラスタリング処理を開始する。
【００６８】
次いで、取得したノード内情報および統計情報に基づき、クラスタ化判断部３（図４）により、同じクラスタになるノードを選定する（ステップＳ２４）。この際、ルーティングのパス（path）を増やすこと、混んでいるパスを分散してスループットを上げること、通信の多いノードと同じ周波数を割り当ててスループットを上げること、特定のノードが隠れ端末やさらし端末の配置になっているために干渉が起こり、スループットが低下することを回避すること、通信の多いノード間（リンク）で使用している周波数と別の周波数を使用することで、衝突確立や送信待ちによって発生するスループット低下を回避すること等をクラスタリングないしはチャネル割り当ての目標とする。
【００６９】
そして、新しいクラスタ化が必要であるか否かを判断し（ステップＳ２５）、必要ない場合（現状のままで変更がない場合）はクラスタリング開始条件待ち（ステップＳ２３）に戻る。
【００７０】
また、新しいクラスタ化が必要である場合には、チャネル変更部４（図４）によりインタフェースのチャネルを変更し、同じクラスタにすべきノードに対してクラスタ化を要求し（ステップＳ２６）、肯定的な応答があった場合にはチャネル変更を実行する（ステップＳ２７）。なお、クラスタ化の要求（ステップＳ２６）については、統計情報交換により全ノードが同じ情報を持っている場合に、特にノード間でシーケンスをやり取りせずにチャネルを変更する場合には省略することも可能である。また、チャネル変更にあっては、電波干渉を避けるために近くのクラスタとかぶらないチャネルを選択するとともに、チャネル品質に応じてより適切なチャネルを選択することができる。なお、クラスタは同じチャネルセットを使うことが条件であるが、クラスタ内の全てのノードが同じチャネルを使う必要はない。例えば、インタフェースが２つである場合であっても、３つ以上の周波数のチャネルセットを用いることができる。この場合は、そのチャネルセットの中から実際に割り当てるチャネルをノード毎に決定する。インタフェース数がノード毎に異なる場合も同様である。
【００７１】
そして、チャネルの変更後、再びクラスタリング開始条件待ち（ステップＳ２３）に戻る。
【００７２】
なお、チャネルの変更はクラスタ化に際してだけではなく、クラスタ化を行った後においてもチャネルの品質等に応じて適宜に変更することができる。もしここで、統計情報の交換により、トラフィックの状況が変わり、クラスタリングすることによりシステムスループットが低下することが判明したら、チャネルを元に戻すことや、チャネル変更をさらに行うことも可能である。
【００７３】
次に、図９はアクセスポイントの配置の例を示す図であり、アクセスポイントＡ、Ｂ、Ｃ、Ｄ、Ｅはそれぞれ２つのインタフェース１１ａ（ＩＥＥＥ８０２．１１ａインタフェース）、１１ｇ（ＩＥＥＥ８０２．１１ｇインタフェース）を有しており、図示のような配置にあるものとする。
【００７４】
図１０は図９の配置にあるアクセスポイント間の信号伝達の例を示すシーケンス図であり、各アクセスポイントＡ〜Ｅを基点とした統計情報交換が行われ（ステップＳ３１、Ｓ３２）、その後、例えば、アクセスポイントＡからアクセスポイントＤに対してクラスタ化要求および肯定的な応答が行われると（ステップＳ３３）、アクセスポイントＡはチャネルスキャンを実行し（ステップＳ３４）、アクセスポイントＤに対してチャネル指定を行い（ステップＳ３５）、チャネル変更が実施される。
【００７５】
図１１はクラスタリングの例を示す図であり、新しいクラスタ化が必要であるか否かを判断するアルゴリズムの一例を示している。図１１において、各アクセスポイントＡ〜Ｅのノード間のリンクが２本存在しているものは、２つのインタフェースにより通信可能であることを示し、リンクに書かれている数字はリンクの混み具合（例えばチャネルの時間的占有割合［％］）を示している。ここで、統計情報の情報交換により各アクセスポイントＡ〜Ｅは他ノードの混雑具合を知ることができるため、チャネル自体の混み具合、ネットワーク全体での自ノードの混み具合、特定のノードがチャネル変更した場合のスループット改善度等を推定することが可能である。例えば、図１１では、統計情報の交換によりＡ−Ｂ−Ｃに高負荷のリンクがあり、Ｄ−Ｅに高負荷のリンクがあることがわかる。
【００７６】
ここで、各アクセスポイントＡ〜Ｅは同時に２つのチャネルしか扱えないため、Ａ−Ｂ−ＣとＤ−Ｅのクラスタにし、別々のチャネルを片方のインタフェースで使用するのが最もよいことがわかり、自ノードおよび他ノードのクラスタ化が必要であると判定できる。
【００７７】
図１１（ａ）はクラスタ化する前の状態を示しているが、アクセスポイントＣでは混み具合「５０」のリンクが閾値Ｔ１を超え、そのリンクの占有割合（５０／７０）が閾値Ｔ２を超えたものとすると、アクセスポイントＣはアクセスポイントＢに対して同じクラスタとなるためにチャネル変更を要求する。同じように、アクセスポイントＥでは混み具合「５０」のリンクが閾値Ｔ１を超え、そのリンクの占有割合（５０／７０）が閾値Ｔ２を超えたものとすると、アクセスポイントＥはアクセスポイントＤに対して同じクラスタとなるためにチャネル変更を要求する。図１１（ｂ）における矢印はチャネル変更の要求を示している。
【００７８】
ここで、これらのチャネル変更の要求に対し、アクセスポイントＢはリンクＡ−Ｂが高負荷であるためチャネル変更を拒否し、アクセスポイントＤは許諾したものとすると、図１１（ｃ）に示すように、アクセスポイントＤ、Ｅはチャネル変更を行い、アクセスポイントＡ、Ｂ、Ｃとの間は１つのインタフェースによる共通チャネルのみで結び、アクセスポイントＤ、Ｅ間は２つのインタフェースで高負荷に耐えうる状態にする。
【００７９】
なお、新しいクラスタ化が必要であると判定した場合、チャネル割り当てを実行するが、チャネル割り当ての方法として以下の３つが挙げられる。
【００８０】
（１）統計情報の情報交換により、全ノードが同じ情報を持っている場合に、特にノード間でシーケンスをやり取りせずにチャネルを変更する方法。この方法はメッセージの送受信を必要としないので、チャネルに負荷をかけないという利点がある。
【００８１】
（２）チャネルを変更したいノードが、一緒にチャネルを変更したいノード（クラスタメンバ）にチャネル変更指示メッセージを送信し、チャネル変更指示を受信したノードはチャネル変更指示メッセージに記入されたチャネルに変更する方法。この方法はチャネル変更に際し、上記の（１）よりもチャネル変更指示メッセージによるチャネル負荷増大という欠点はあるが、チャネルを指定することでより確実によりよいチャネルに変更できるという利点がある。
【００８２】
（３）クラスタ化の意思をメッセージのやり取りにより確認し、確認が取れた上でチャネル変更指示のメッセージをやり取りし、クラスタ化およびチャネル変更を行う方法。この方法は、処理負荷はかかるが、各ノードの状況に応じて確実にチャネルを変更できるという利点がある。図１１に示した例はこの方法を採用している。
【００８３】
図１２は本発明のチャネル割り当て方法によるクラスタリングの例を示す図であり、共通（Common）のチャネルを設けた例である。すなわち、（ａ）に示すように、各アクセスポイントのインタフェースを２つとした場合、共通チャネルを「１ｃｈ」とし、「１ｃｈ」「３ｃｈ」のチャネルセットのクラスタＣ１と、「１ｃｈ」「２ｃｈ」のチャネルセットのクラスタＣ２とのいずれかを各アクセスポイントに割り当てるようにしている。なお、各アクセスポイントのインタフェース数が２より多い場合についても同様に本方式を適用することができる。
【００８４】
（ｂ）はクラスタリングが行われたメッシュネットワークの例を示しており、各アクセスポイントの位置（トポロジ）とは関係なく、通信量が多いアクセスポイント同士を同じクラスタにするという動的かつ論理的なクラスタリングを行ったものである。すなわち、アクセスポイントＡＰ１、ＡＰ４、ＡＰ５、ＡＰ６、ＡＰ７を同じクラスタにし、アクセスポイントＡＰ２、ＡＰ３、ＡＰ８、ＡＰ９を同じクラスタにしている。なお、同じクラスタに属していても位置的に遠いアクセスポイント間では電波が届かないために通信が行えない部分がある。
【００８５】
この場合、同じクラスタ内のアクセスポイント同士では使えるチャネルが２つであるため高速に通信が行え、通信量の多い現時点の通信状況に即応した環境が構築される。また、クラスタをまたがる通信は、共通のチャネルにより、クラスタ内ほどではないが現時点の通信状況に即応した十分な通信を行うことができる。
【００８６】
図１３は本発明のチャネル割り当て方法によるクラスタリングの他の例を示す図であり、メッシュネットワーク全体としての共通のチャネルを設けない例である。すなわち、（ａ）に示すように、各アクセスポイントのインタフェースを２つとした場合、「１ｃｈ」「２ｃｈ」のチャネルセットのクラスタＣ１と、「２ｃｈ」「３ｃｈ」のチャネルセットのクラスタＣ２と、「１ｃｈ」「３ｃｈ」のチャネルセットのクラスタＣ３とに分け、クラスタＣ１とクラスタＣ２の間では「２ｃｈ」のチャネルを共通とし、クラスタＣ２とクラスタＣ３の間では「３ｃｈ」のチャネルを共通とし、クラスタＣ３とクラスタＣ１の間では「１ｃｈ」のチャネルを共通としている。なお、各アクセスポイントのインタフェース数が２より多い場合についても同様に本方式を適用することができる。
【００８７】
（ｂ）はクラスタリングが行われたメッシュネットワークの例を示しており、アクセスポイントＡＰ１、ＡＰ７、ＡＰ９を同じクラスタにし、アクセスポイントＡＰ２、ＡＰ３、ＡＰ８を同じクラスタにし、アクセスポイントＡＰ４、ＡＰ５、ＡＰ６を同じクラスタにしている。なお、同じクラスタに属していても位置的に遠いアクセスポイント間では電波が届かないために通信が行えない部分がある。
【００８８】
この場合も、同じクラスタ内のアクセスポイント同士では使えるチャネルが２つであるため高速に通信が行え、通信量の多い現時点の通信状況に即応した環境が構築される。また、クラスタをまたがる通信は、メッシュネットワーク全体に共通のものではないがクラスタ間の共通のチャネルにより、クラスタ内ほどではないが現時点の通信状況に即応した十分な通信を行うことができる。更に、図１２に示した共通チャネルの場合と比べ、電波干渉が起きにくいことから、より高速なクラスタ間の通信を行うことができる。
【００８９】
ところで、一般的に、チャネル変更時には制御により遅延時間がかかり、またノード内の経路制御モジュール５（図４）が経路の切り替えなどを行うために一時的に通信が切れたり、パケット喪失の原因となる。そのため、チャネル変更時に各ノードは自ノード内の経路制御モジュール５へチャネル変更する自ノードのインタフェース情報を含んだチャネル通知信号を送り、この信号を受けた経路制御モジュール５の経路制御プロトコルは、チャネルが変更するまでの間、他の経路で通信し、チャネル変更を行うインタフェースでの経路制御の信号のやり取りを停止することで、パケット喪失を防ぐことが可能となる。
【００９０】
図１４はチャネル変更時の経路制御モジュールの動作制御の例を示す図であり、（ａ）に示すようにアクセスポイントＡからアクセスポイントＢに対してインタフェース１１ｇ、１１ａの両方からルートリクエストを出したとすると、インタフェース１１ａのチャネル変更時にアクセスポイントＢ、Ｃは自ノード内の経路制御モジュールへチャネル変更する自ノードのインタフェース情報を含んだチャネル通知信号を送り、信号を受けた経路制御モジュールは、経路更新間隔より長い期間、チャネル変更を行うインタフェース１１ａでの経路制御の信号のやり取りを停止し、（ｂ）に示すようにインタフェース１１ａを通したルートリクエストを遮断することで、インタフェース１１ａの使用を止める。そして、チャネル変更後にインタフェース１１ａで経路制御の信号のやり取りを再開することで、チャネル変更中のパケット喪失を防ぐことが可能となる。
【００９１】
このようにすることで、経路制御プロトコルそのものの状態遷移やフローチャートには変更を加えることなく、チャネル変更に経路制御を対応させることが可能となる。
【００９２】
本発明の応用例として、例えば、家庭内のテレビ、ＤＶＤプレイヤ等がアクセスポイントの機能を有し、メッシュネットワークを構成している場合、テレビからＤＶＤプレイヤに対して動画・音声の送信を要求することでテレビとＤＶＤプレイヤとの間に大量のデータ通信が発生すると、従来のトポロジに基づいて複数のインタフェースのチャネル割り当てがなされている場合はテレビとＤＶＤプレイヤとの間のチャネル数が少ないために円滑なデータ通信が行なえなかったり、同じメッシュネットワークに含まれる他のアクセスポイント（例えば、パーソナルコンピュータ等）の利用に悪影響を与える可能性がある。この点、本発明のチャネル割り当てによれば、大量のデータ通信が行われるテレビとＤＶＤプレイヤとを同じクラスタに入れ、両者間に複数のチャネルを優先的にかつ動的に割り当てることになるため、テレビとＤＶＤプレイヤとの間のデータ通信が円滑に行われるとともに、他のアクセスポイントの利用に悪影響を与えることがなくなるものである。
【００９３】
以上、本発明の好適な実施の形態により本発明を説明した。ここではＩＥＥＥ８０２．１１規格の無線ＬＡＮを例にとって説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、ＩＥＥＥ８０２．１５規格、ＩＥＥＥ８０２．１６規格、ＩＥＥＥ８０２．２０規格やセルラー方式の基地局間通信などに、本実施形態で挙げた具体例に様々な修正および変更を加えることで適用ができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【図面の簡単な説明】
【００９４】
【図１】インタフェース数と同数のチャネルを設けた従来のメッシュネットワークの例を示す図である。
【図２】インタフェース数よりも多いチャネルを設けた従来のメッシュネットワークの例を示す図である。
【図３】従来のトポロジに基づくクラスタリングの例を示す図である。
【図４】本発明のチャネル割り当て方法を適用したアクセスポイントの構成例を示す図である。
【図５】トラフィック情報の値の計算方法の例を示す図である。
【図６】アクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その１）である。
【図７】アクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その２）である。
【図８】アクセスポイントにおけるクラスタリング処理の例を示すフローチャート（その３）である。
【図９】アクセスポイントの配置の例を示す図である。
【図１０】アクセスポイント間の信号伝達の例を示すシーケンス図である。
【図１１】クラスタリングの例を示す図である。
【図１２】本発明のチャネル割り当て方法によるクラスタリングの例を示す図である。
【図１３】本発明のチャネル割り当て方法によるクラスタリングの他の例を示す図である。
【図１４】チャネル変更時の経路制御モジュールの動作制御の例を示す図である。
【符号の説明】
【００９５】
１                ノード内情報取得部
２                統計情報交換部
３                クラスタ化判断部
４                チャネル変更部
５                経路制御モジュール
ＡＰ１〜ＡＰ９    アクセスポイント
Ｃ１〜Ｃ３        クラスタ
【図１】
2006050549.tif 000003
【図２】
2006050549.tif 000004
【図３】
2006050549.tif 000005
【図４】
2006050549.tif 000006
【図５】
2006050549.tif 000007
【図６】
2006050549.tif 000008
【図７】
2006050549.tif 000009
【図８】
2006050549.tif 000010
【図９】
2006050549.tif 000011
【図１０】
2006050549.tif 000012
【図１１】
2006050549.tif 000013
【図１２】
2006050549.tif 000014
【図１３】
2006050549.tif 000015
【図１４】
2006050549.tif 000016