(57)【要約】【課題】タイミングおよび範囲が明確であり、かつ、安定したチャネル割当を行うチャネル割当装置を提供する。【解決手段】チャネル割当装置は、チャネル割当の対象となるアクセスポイント１０〜１３をグループ化する。また、チャネル割当装置は、隣接する２つのアクセスポイント間の干渉の度合を示すエッジ重みを示す基準グラフＳＴＤ１を作成する。更に、チャネル割当装置は、アクセスポイント１０〜１３およびアクセスポイント１０〜１３にアクセスする端末装置の新しいトポロジーを取得する毎に、その新しいトポロジーに基づいてエッジ重みを示す基本グラフＢＧ３を作成する。そして、チャネル割当装置は、基本グラフＢＧ３を基準グラフＳＴＤ１と比較し、エッジ重みの全ての変化量の和である変動量がしきい値よりも大きいことがｎ回連続すると、アクセスポイント１０〜１３に対してチャネル割当を行う。【選択図】図１３
2011049913.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークに接続された複数の通信装置の隣接関係を示す第１の隣接リストと、前記複数の通信装置に接続可能な複数の端末装置を示す第２の隣接リストとに基づいて、前記複数の通信装置の相互の隣接関係と前記複数の端末装置の前記通信装置への接続可能性とを示すトポロジーを作成し、その作成したトポロジーに基づいて、前記複数の通信装置をチャネル割当の対象として決定する決定装置と、
前記チャネル割当の対象として決定された前記複数の通信装置を前記決定装置から受け、その受けた複数の通信装置にチャネルを割り当てるチャネル割当ユニットとを備え、
前記チャネル割当ユニットは、
前記複数の通信装置と前記トポロジーとに基づいて、前記複数の通信装置を頂点とし、前記複数の通信装置が同じチャネルを使用した場合において隣接する２つの通信装置間の干渉の度合を示すエッジ重みによって前記複数の通信装置のうちの干渉関係にある２つの通信装置間を結んだ基本グラフを作成するグラフ生成手段と、
前記基本グラフに基づいて、前記複数の通信装置間における前記エッジ重みまたはチャネルを変更する前記複数の通信装置および前記複数の端末装置の個数が評価関数を満たすように前記複数の通信装置にチャネルを割り当てるチャネル割当処理を実行するチャネル割当手段と、
前記複数の通信装置間における前記エッジ重みの変動量を検知し、その検知した変動量が一定の条件を満たすか否かを判定する判定手段と、
前記チャネル割当処理後のチャネルをネットワークを介して前記複数の通信装置へ送信する通信手段とを含み、
前記チャネル割当手段は、前記変動量が前記一定の条件を満たす毎に、前記変動量が前記一定の条件を満たしたときの最新の前記基本グラフに基づいて前記チャネル割当処理を実行する、チャネル割当装置。
【請求項２】
前記チャネル割当手段は、前記チャネル割当処理が実行されたときの前記複数の通信装置間における前記エッジ重みを示す基準グラフの全体における前記エッジ重みの最大値が最小となる第１の評価関数、前記基準グラフの全体における前記エッジ重みの総和が最小になる第２の評価関数、および前記チャネルを変更する前記複数の通信装置および前記複数の端末装置の個数が最小になる第３の評価関数の少なくとも１つを前記評価関数として用いることにより前記チャネル割当処理を実行する、請求項１に記載のチャネル割当装置。
【請求項３】
前記判定手段は、前記グラフ生成手段によって作成された最新の基本グラフを前記チャネル割当処理が実行されたときの前記複数の通信装置に対する前記基本グラフからなる基準グラフと比較して前記最新の基本グラフにおけるエッジ重みの変化量を検出し、その検出した変化量のうち、１つのエッジにおける前記エッジ重みの変化量のしきい値である第１のしきい値よりも大きくなる変化量を検出し、その検出した変化量を前記エッジ重みの局所変動を反映するためのスケーリング関数に代入して前記変動量を演算し、その演算した変動量がネットワーク全体における前記エッジ重みの変化量のしきい値である第２のしきい値をｎ（ｎは正の整数）回連続して超えるか否かを判定し、
前記チャネル割当手段は、前記変動量が前記第２のしきい値を前記ｎ回連続して超えたと判定される毎に、前記複数の通信装置に対して前記チャネル割当処理を実行する、請求項１に記載のチャネル割当装置。
【請求項４】
前記判定手段は、前記第１のしきい値が第１の値であり、かつ、前記第２のしきい値が第２の値であるとき、前記検出した変化量を一次関数からなる前記スケーリング関数に代入して前記変動量を演算し、前記第１のしきい値が前記第１の値であり、かつ、前記第２のしきい値が前記第２の値よりも小さい第３の値であるとき、前記検出した変化量を二次関数または指数関数からなる前記スケーリング関数に代入して前記変動量を演算する、請求項３に記載のチャネル割当装置。
【請求項５】
前記エッジ重みは、隣接する２つの通信装置の両方が相互の通信範囲の重複領域以外の通信範囲に存在するとき、前記重複領域に存在する端末装置の個数を前記複数の端末装置の個数で除算した値からなり、前記２つの通信装置の両方が前記重複領域に存在するとき、前記重複領域に存在する端末装置の個数から前記複数の端末装置の個数を減算した減算結果を前記複数の端末装置の個数で除算した値からなる、請求項１から請求項４のいずれか１項に記載のチャネル割当装置。
【請求項６】
ネットワークに接続された複数の通信装置と、
各々が前記複数の通信装置のいずれかと無線通信を行う複数の端末装置と、
前記ネットワークに接続され、前記複数の通信装置に対してチャネルを割り当てるチャネル割当装置とを備え、
前記チャネル割当装置は、
ネットワークに接続された複数の通信装置の隣接関係を示す第１の隣接リストと、前記複数の通信装置に接続可能な複数の端末装置を示す第２の隣接リストとに基づいて、前記複数の通信装置の相互の隣接関係と前記複数の端末装置の前記通信装置への接続可能性とを示すトポロジーを作成し、その作成したトポロジーに基づいて、前記複数の通信装置をチャネル割当の対象として決定する決定装置と、
前記チャネル割当の対象として決定された前記複数の通信装置を前記決定装置から受け、その受けた複数の通信装置にチャネルを割り当てるチャネル割当ユニットとを含み、
前記チャネル割当ユニットは、
前記複数の通信装置と前記トポロジーとに基づいて、前記複数の通信装置を頂点とし、前記複数の通信装置が同じチャネルを使用した場合において隣接する２つの通信装置間の干渉の度合を示すエッジ重みによって前記複数の通信装置のうちの干渉関係にある２つの通信装置間を結んだ基本グラフを作成するグラフ生成手段と、
前記基本グラフに基づいて、前記複数の通信装置間における前記エッジ重みまたはチャネルを変更する前記複数の通信装置および前記複数の端末装置の個数が評価関数を満たすように前記複数の通信装置にチャネルを割り当てるチャネル割当処理を実行するチャネル割当手段と、
前記複数の通信装置間における前記エッジ重みの変動量を検知し、その検知した変動量が一定の条件を満たすか否かを判定する判定手段と、
前記チャネル割当処理後のチャネルをネットワークを介して前記複数の通信装置へ送信する通信手段とを含み、
前記チャネル割当手段は、前記変動量が前記一定の条件を満たす毎に、前記変動量が前記一定の条件を満たしたときの最新の前記基本グラフに基づいて前記チャネル割当処理を実行する、通信ネットワークシステム。
【請求項７】
前記複数の通信装置は、前記チャネル割当装置から前記チャネル割当処理後のチャネルを受信し、その受信したチャネル割当処理後のチャネルと、通信中断予定時間とを含むチャネル変更メッセージを自己に接続する第１の端末装置へ送信するとともに、自己のチャネルを前記チャネル割当処理後のチャネルに切り替え、前記通信中断予定時間の間、制御フレームの送信を停止し、
前記第１の端末装置は、前記チャネル変更メッセージを受信した後、前記チャネル変更メッセージを送信した通信装置との間のリンクの切断を検知すると、前記通信中断予定時間および前記制御フレームの送信間隔の期間内において前記チャネル割当処理後のチャネルを用いて前記通信装置を探索し、前記通信装置を検知すると、前記チャネル割当処理後のチャネルを用いて前記通信装置に接続する、請求項６に記載の通信ネットワークシステム。
【請求項８】
前記第１の端末装置は、前記通信装置を検知できない場合、全てのチャネルを用いて前記通信装置を探索する、請求項７に記載の通信ネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、チャネルを割り当てるチャネル割当装置およびそれを備えた通信ネットワークシステムに関するものである。
【背景技術】
【０００２】
ユーザの意思で任意の場所に設置される自営無線アクセスネットワーク（以下、「自営網」と言う。）と、計画的に設置される公衆無線アクセスネットワーク（以下、「公衆網」と言う。）とが混在するネットワークにおいて、自営網の各アクセスポイント（ＡＰ：Ａｃｃｅｓｓ  Ｐｏｉｎｔ）が使用する周波数チャネルを無秩序に選択すると、その配置や設置密度によりＡＰのカバレッジ間で干渉が発生し、自営網のみでなく、公衆網に対しても同じ周波数帯を利用するユーザ間で伝送効率の劣化が発生する。
【０００３】
従来、無線ネットワークの基地局の周波数チャネルを割り当てる方法として、重み付きグラフによる彩色問題を応用した集中制御によるチャネル割当方法が提案されている（非特許文献１）。
【０００４】
また、非特許文献１に開示されたチャネル割当方法を改良したチャネル割当方法も提案されている（非特許文献２，３）。
【０００５】
更に、集中制御局が無線端末のトラフィックおよびトポロジー情報に基づいて無線基地局に対するチャネル割当を行う基本的なアーキテクチャが提案されている（特許文献１）。
【０００６】
これらの方法は、チャネルを割り当てるべき対象の無線装置の隣接する干渉関係を情報として収集し、その収集した干渉関係を表す指標値を最小化するように最適チャネル割当を実施する方法である。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−１５７８３９号公報
【非特許文献】
【０００８】
【非特許文献１】A. Mishra, S. Banerjee, W. Arbaugh, “Weighted coloring based channel assignment for wlans,” SIGMOBILE Mob. Comput. Commun. Rev., 9(3):19-31, 2005.
【非特許文献２】T. Vanhatupa, M. Hannikainen, and T. D. Hamalainen, “Evaluation of throughput estimation models and algorithms for WLAN frequency planning,” The International Journal of Computer and Telecommunications Networking, Volume 51, Issue 11, pp. 3110-3124, August 2007.
【非特許文献３】Tim Dasilva, Kevin Eustice, and Peter Reiher, “Johnny Appleseed: wardriving to reduce interference in chaotic wireless deployments,” Proc. Of MSWiM '08, pp. 122-131, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、非特許文献１〜３に開示された方法は、干渉を低減するための最適チャネル割当にのみ注目しているため、どのような状況になったときに、どのくらいの規模でチャネル割当およびチャネルの変更を行えば良いか明確ではない。
【００１０】
また、特許文献１に開示された方法は、トラフィックロードに基づいたチャネル交換時期とチャネル交換の実行とを決定している。しかし、個々の基地局に対して頻繁に変動するトラフィックに基づいた判断を行うと、チャネル変更が頻繁に発生するとともに、指標とすべきトラフィック自体が不安定になるという問題がある。この問題は、トラフィックを指標とした場合に限らず、干渉量（受信電力）、端末と基地局との接続状況などに基づいたチャネル割当の場合にも生じる問題である。
【００１１】
そこで、この発明は、かかる問題を解決するためになされたものであり、その目的は、タイミングおよび範囲が明確であり、かつ、安定したチャネル割当を行うチャネル割当装置を提供することである。
【００１２】
また、この発明の別の目的は、タイミングおよび範囲が明確であり、かつ、安定したチャネル割当を行うチャネル割当装置を備えた通信ネットワークシステムを提供することである。
【課題を解決するための手段】
【００１３】
この発明によれば、チャネル割当装置は、決定装置と、チャネル割当ユニットとを備える。決定装置は、ネットワークに接続された複数の通信装置の隣接関係を示す第１の隣接リストと、複数の通信装置に接続可能な複数の端末装置を示す第２の隣接リストとに基づいて、複数の通信装置の相互の隣接関係と複数の端末装置の通信装置への接続可能性とを示すトポロジーを作成し、その作成したトポロジーに基づいて、複数の通信装置をチャネル割当の対象として決定する。チャネル割当ユニットは、チャネル割当の対象として決定された複数の通信装置を決定装置から受け、その受けた複数の通信装置にチャネルを割り当てる。チャネル割当ユニットは、グラフ生成手段と、チャネル割当手段と、判定手段と、通信手段とを含む。グラフ生成手段は、複数の通信装置とトポロジーとに基づいて、複数の通信装置を頂点とし、複数の通信装置が同じチャネルを使用した場合において隣接する２つの通信装置間の干渉の度合を示すエッジ重みによって複数の通信装置のうちの干渉関係にある２つの通信装置間を結んだ基本グラフを作成する。チャネル割当手段は、基本グラフに基づいて、複数の通信装置間におけるエッジ重みまたはチャネルを変更する複数の通信装置および複数の端末装置の個数が評価関数を満たすように複数の通信装置にチャネルを割り当てるチャネル割当処理を実行する。判定手段は、複数の通信装置間におけるエッジ重みの変動量を検知し、その検知した変動量が一定の条件を満たすか否かを判定する。通信手段は、チャネル割当処理後のチャネルをネットワークを介して複数の通信装置へ送信する。そして、チャネル割当手段は、変動量が一定の条件を満たす毎に、変動量が一定の条件を満たしたときの最新の基本グラフに基づいてチャネル割当処理を実行する。
【００１４】
好ましくは、チャネル割当手段は、チャネル割当処理が実行されたときの複数の通信装置間におけるエッジ重みを示す基準グラフの全体におけるエッジ重みの最大値が最小となる第１の評価関数、基準グラフの全体におけるエッジ重みの総和が最小になる第２の評価関数、およびチャネルを変更する複数の通信装置および複数の端末装置の個数が最小になる第３の評価関数の少なくとも１つを評価関数として用いることによりチャネル割当処理を実行する。
【００１５】
好ましくは、判定手段は、グラフ生成手段によって作成された最新の基本グラフをチャネル割当処理が実行されたときの複数の通信装置に対する基本グラフからなる基準グラフと比較して最新の基本グラフにおけるエッジ重みの変化量を検出し、その検出した変化量のうち、１つのエッジにおけるエッジ重みの変化量のしきい値である第１のしきい値よりも大きくなる変化量を検出し、その検出した変化量をエッジ重みの局所変動を反映するためのスケーリング関数に代入して変動量を演算し、その演算した変動量がネットワーク全体におけるエッジ重みの変化量のしきい値である第２のしきい値をｎ（ｎは正の整数）回連続して超えるか否かを判定する。チャネル割当手段は、変動量が第２のしきい値をｎ回連続して超えたと判定される毎に、複数の通信装置に対してチャネル割当処理を実行する。
【００１６】
好ましくは、判定手段は、第１のしきい値が第１の値であり、かつ、第２のしきい値が第２の値であるとき、検出した変化量を一次関数からなるスケーリング関数に代入して変動量を演算し、第１のしきい値が第１の値であり、かつ、第２のしきい値が第２の値よりも小さい第３の値であるとき、検出した変化量を二次関数または指数関数からなるスケーリング関数に代入して変動量を演算する。
【００１７】
好ましくは、エッジ重みは、隣接する２つの通信装置の両方が相互の通信範囲の重複領域以外の通信範囲に存在するとき、重複領域に存在する端末装置の個数を複数の端末装置の個数で除算した値からなり、２つの通信装置の両方が重複領域に存在するとき、重複領域に存在する端末装置の個数から複数の端末装置の個数を減算した減算結果を複数の端末装置の個数で除算した値からなる。
【００１８】
また、この発明によれば、通信ネットワークシステムは、複数の通信装置と、複数の端末装置と、チャネル割当装置とを備える。複数の通信装置は、ネットワークに接続される。複数の端末装置の各々は、複数の通信装置のいずれかと無線通信を行う。チャネル割当装置は、ネットワークに接続され、複数の通信装置に対してチャネルを割り当てる。チャネル割当装置は、決定装置と、チャネル割当ユニットとを備える。決定装置は、ネットワークに接続された複数の通信装置の隣接関係を示す第１の隣接リストと、複数の通信装置に接続可能な複数の端末装置を示す第２の隣接リストとに基づいて、複数の通信装置の相互の隣接関係と複数の端末装置の通信装置への接続可能性とを示すトポロジーを作成し、その作成したトポロジーに基づいて、複数の通信装置をチャネル割当の対象として決定する。チャネル割当ユニットは、チャネル割当の対象として決定された複数の通信装置を決定装置から受け、その受けた複数の通信装置にチャネルを割り当てる。チャネル割当ユニットは、グラフ生成手段と、チャネル割当手段と、判定手段と、通信手段とを含む。グラフ生成手段は、複数の通信装置とトポロジーとに基づいて、複数の通信装置を頂点とし、複数の通信装置が同じチャネルを使用した場合において隣接する２つの通信装置間の干渉の度合を示すエッジ重みによって複数の通信装置のうちの干渉関係にある２つの通信装置間を結んだ基本グラフを作成する。チャネル割当手段は、基本グラフに基づいて、複数の通信装置間におけるエッジ重みまたはチャネルを変更する複数の通信装置および複数の端末装置の個数が評価関数を満たすように複数の通信装置にチャネルを割り当てるチャネル割当処理を実行する。判定手段は、複数の通信装置間におけるエッジ重みの変動量を検知し、その検知した変動量が一定の条件を満たすか否かを判定する。通信手段は、チャネル割当処理後のチャネルをネットワークを介して複数の通信装置へ送信する。そして、チャネル割当手段は、変動量が一定の条件を満たす毎に、変動量が一定の条件を満たしたときの最新の基本グラフに基づいてチャネル割当処理を実行する。
【００１９】
好ましくは、複数の通信装置は、チャネル割当装置からチャネル割当処理後のチャネルを受信し、その受信したチャネル割当処理後のチャネルと、通信中断予定時間とを含むチャネル変更メッセージを自己に接続する第１の端末装置へ送信するとともに、自己のチャネルをチャネル割当処理後のチャネルに切り替え、通信中断予定時間の間、制御フレームの送信を停止する。第１の端末装置は、チャネル変更メッセージを受信した後、チャネル変更メッセージを送信した通信装置との間のリンクの切断を検知すると、通信中断予定時間および制御フレームの送信間隔の期間内においてチャネル割当処理後のチャネルを用いて通信装置を探索し、通信装置を検知すると、チャネル割当処理後のチャネルを用いて通信装置に接続する。
【００２０】
好ましくは、第１の端末装置は、通信装置を検知できない場合、全てのチャネルを用いて通信装置を探索す。
【発明の効果】
【００２１】
この発明によれば、決定装置は、第１および第２の隣接リストに基づいて、複数の通信装置の相互の隣接関係と複数の端末装置の通信装置への接続可能性とを示すトポロジーを作成し、その作成したトポロジーに基づいて、複数の通信装置をチャネル割当の対象として決定し、チャネル割当ユニットは、判定手段によってエッジ重みの変動量が一定の条件を満たすと判定される毎に、決定装置によって決定された複数の通信装置に対してチャネルを割り当てる。その結果、チャネル割当の対象が複数の通信装置に限定される。また、隣接する通信装置間の干渉の度合を示すエッジ重みの変動量が一定の条件を満たした時にチャネル割当が行われる。
【００２２】
従って、チャネル割当のタイミングおよび範囲を明確でき、安定したチャネル割当を行うことができる。
【図面の簡単な説明】
【００２３】
【図１】この発明の実施の形態による通信ネットワークシステムの構成を示す概略図である。
【図２】図１に示す端末装置１の構成図である。
【図３】図１に示すアクセスポイントの構成図である。
【図４】図１に示すチャネル割当装置の構成図である。
【図５】エッジ重みを演算する方法を説明するための第１の概念図である。
【図６】エッジ重みを演算する方法を説明するための第２の概念図である。
【図７】基本グラフの作成方法を説明するためのトポロジーの具体例を示す図である。
【図８】基本グラフの具体例を示す図である。
【図９】チャネル割当前の干渉グラフを示す図である。
【図１０】チャネル割当後の干渉グラフを示す図である。
【図１１】チャネル割当後のトポロジーを示す図である。
【図１２】変動後のトポロジーを示す図である。
【図１３】基本グラフの他の具体例を示す図である。
【図１４】変動量の判定動作と、チャネル割当のタイミングとの関係を示す概念図である。
【図１５】ＣＡドメインの分割方法を説明するための図である。
【図１６】分割後のＣＡドメインの概念図である。
【図１７】図１に示すチャネル割当装置における動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００２４】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。
【００２５】
図１は、この発明の実施の形態による通信ネットワークシステムの構成を示す概略図である。図１を参照して、この発明の実施の形態による通信ネットワークシステム１００は、端末装置１〜９と、アクセスポイント１０〜２０と、ルータ２１〜２４と、ネットワーク４０と、監視サーバ５０と、チャネル割当装置６０とを備える。
【００２６】
端末装置１〜９は、無線通信空間に配置される。そして、端末装置１〜９の各々は、例えば、ＷｉＦｉの無線インターフェースを備え、その備えた無線インターフェースによってインフラストラクチャモードでアクセスポイント１０〜２０のいずれかに接続する。
【００２７】
そして、端末装置１〜９の各々は、接続したアクセスポイントから受信したチャネルを用いて無線通信を行う。
【００２８】
また、端末装置１〜９の各々は、周辺に存在するアクセスポイントからビーコンフレームを受信し、その受信したビーコンフレームに基づいて、自己が接続可能なアクセスポイントを示す接続可能アクセスポイントリスト（以下、「接続可能ＡＰリスト」と言う。）を定期的に作成する。そして、端末装置１〜９の各々は、その作成した接続可能ＡＰリストをネットワーク４０を介して監視サーバ５０へ定期的に送信する。
【００２９】
アクセスポイント１０〜１３は、ルータ２１に接続され、アクセスポイント１４〜１６は、ルータ２２に接続され、アクセスポイント１７，１８は、ルータ２３に接続され、アクセスポイント１９，２０は、ルータ２４に接続される。ルータ２１〜２４は、ネットワーク４０に接続される。
【００３０】
アクセスポイント１０〜２０の各々は、ＷｉＦｉの無線インターフェースを備え、その備えた無線インターフェースを用いて端末装置１〜９と無線通信を行うとともに、ルータ（ルータ２１〜２４のいずれか）およびネットワーク４０を介して監視サーバ５０およびチャネル割当装置６０と通信を行う。
【００３１】
また、アクセスポイント１０〜２０の各々は、無線通信によってビーコンフレームを定期的に送信する。そして、アクセスポイント１０〜２０の各々は、他のアクセスポイントから送信されたビーコンフレームを受信することによって自己に隣接するアクセスポイントを定期的に検出し、その検出したアクセスポイントのリストである隣接アクセスポイントリスト（以下、「隣接ＡＰリスト」と言う。）を作成する。そして、アクセスポイント１０〜２０の各々は、その作成した隣接ＡＰリストをルータ（ルータ２１〜２４のいずれか）およびネットワーク４０を介して監視サーバ５０へ定期的に送信する。
【００３２】
ルータ２１〜２４の各々は、ネットワーク４０からパケットを受信し、その受信したパケットを自己に接続されたアクセスポイント（アクセスポイント１０〜２０の少なくとも１つ）に送信する。
【００３３】
また、ルータ２１〜２４の各々は、自己に接続されたアクセスポイント（アクセスポイント１０〜２０の少なくとも１つ）からパケットを受信し、その受信したパケットをネットワーク４０を介して送信する。
【００３４】
ネットワーク４０は、例えば、インターネットからなる。
【００３５】
監視サーバ５０は、ネットワーク４０に接続される。そして、監視サーバ５０は、アクセスポイント１０〜２０の各々から隣接ＡＰリストをネットワーク４０を介して定期的に受信し、その受信した隣接ＡＰリストを管理する。
【００３６】
また、監視サーバ５０は、端末装置１〜９の各々から接続可能ＡＰリストをネットワーク４０を介して定期的に受信し、その受信した接続可能ＡＰリストを管理する。
【００３７】
チャネル割当装置６０は、ネットワーク４０に接続される。そして、チャネル割当装置６０は、ネットワーク４０を介して監視サーバ５０から隣接ＡＰリストおよび接続可能ＡＰリストを定期的に取得する。その後、チャネル割当装置６０は、その取得した隣接ＡＰリストおよび接続可能ＡＰリストに基づいて、アクセスポイント１０〜２０の相互の隣接関係と、端末装置１〜９とアクセスポイント１０〜２０との接続可能性とを示すトポロジーを作成する。そうすると、チャネル割当装置６０は、その作成したトポロジーに基づいて、後述する方法によって、チャネル割当を行う。そして、チャネル割当装置６０は、その割り当てたチャネルをアクセスポイント１０〜２０へ送信する。
【００３８】
図２は、図１に示す端末装置１の構成図である。図２を参照して、端末装置１は、アンテナ１０１と、無線インターフェース１０２と、通信手段１０３と、アプリケーションモジュール１０４とを含む。
【００３９】
無線インターフェース１０２は、ＷｉＦｉの無線通信方式によって無線通信を行う。そして、無線インターフェース１０２は、インフラストラクチャモードでアクセスポイント（アクセスポイント１０〜２０のいずれか）にアクセスし、アクセスポイント（アクセスポイント１０〜２０のいずれか）との間でパケットを送受信する。
【００４０】
即ち、無線インターフェース１０２は、通信手段１０３から受けたパケットをアンテナ１０１を介してアクセスポイント（アクセスポイント１０〜２０のいずれか）へ送信する。また、無線インターフェース１０２は、アンテナ１０１を介してパケットをアクセスポイント（アクセスポイント１０〜２０のいずれか）から受信し、その受信したパケットを通信手段１０３へ出力する。
【００４１】
通信手段１０３は、アプリケーションモジュール１０４からパケットを受け、その受けたパケットを無線インターフェース１０２を用いて送信する。
【００４２】
また、通信手段１０３は、無線インターフェース１０２からパケットを受け、その受けたパケットをアプリケーションモジュール１０４へ出力する。
【００４３】
更に、通信手段１０３は、端末装置１の周辺に存在するアクセスポイントから無線インターフェース１０２を介してビーコンフレームを定期的に受信し、その受信したビーコンフレームに基づいて、端末装置１が接続可能なアクセスポイントを示す接続可能ＡＰリストを定期的に作成する。そして、通信手段１０３は、その作成した接続可能ＡＰリストを無線インターフェース１０２を介して監視サーバ５０へ定期的に送信する。
【００４４】
更に、通信手段１０３は、チャネル割当装置６０によってチャネルが割り当てられたとき、後述する方法によってチャネルの変更を行う。
【００４５】
アプリケーションモジュール１０４は、パケットを生成して通信手段１０３へ出力するとともに、通信手段１０３からパケットを受ける。
【００４６】
なお、図１に示す端末装置２〜９の各々も、図２に示す端末装置１と同じ構成からなる。
【００４７】
図３は、図１に示すアクセスポイント１０の構成図である。図３を参照して、アクセスポイント１０は、アンテナ１１１と、無線インターフェース１１２と、通信手段１１３と、有線インターフェース１１４とを含む。
【００４８】
無線インターフェース１１２は、ＷｉＦｉの無線通信方式によって無線通信を行う。そして、無線インターフェース１１２は、通信手段１１３からパケットを受け、その受けたパケットをアンテナ１１１を介して送信する。また、無線インターフェース１１２は、アンテナ１１１を介してパケットを受信し、その受信したパケットを通信手段１１３へ出力する。
【００４９】
通信手段１１３は、無線インターフェース１１２からパケットを受け、その受けたパケットを有線インターフェース１１４へ出力する。また、通信手段１１３は、有線インターフェース１１４からパケットを受け、その受けたパケットを無線インターフェース１１２へ出力する。
【００５０】
更に、通信手段１１３は、アクセスポイント１０の周囲に存在するアクセスポイントから無線インターフェース１１２を介してビーコンフレームを定期的に受信し、その受信したビーコンフレームに基づいて、アクセスポイント１０に隣接するアクセスポイントを示す隣接ＡＰリストを定期的に作成する。そして、通信手段１１３は、その作成した隣接ＡＰリストを有線インターフェース１１４を介して監視サーバ５０へ定期的に送信する。
【００５１】
更に、通信手段１１３は、有線インターフェース１１４を介してチャネル割当装置６０からチャネル割当後のチャネルを受信すると、後述する方法によって、チャネルの変更を行う。
【００５２】
有線インターフェース１１４は、通信手段１１３からパケットを受け、その受けたパケットをネットワーク４０を介して監視サーバ５０へ送信する。
【００５３】
また、有線インターフェース１１４は、ネットワーク４０を介してチャネル割当装置６０からチャネルを受信し、その受信したチャネルを通信手段１１３へ出力する。
【００５４】
なお、図１に示すアクセスポイント１１〜２０の各々も、図３に示すアクセスポイント１０と同じ構成からなる。
【００５５】
図４は、図１に示すチャネル割当装置６０の構成図である。図４を参照して、チャネル割当装置６０は、チャネル割当ユニット６１，６２，６３，・・・と、ドメイン決定装置６００と、有線インターフェース６１０と、通信手段６２０とを含む。
【００５６】
チャネル割当ユニット６１，６２，６３，・・・は、チャネル割当の対象となるアクセスポイントの集合を示すＣＡドメインの個数に対応して設けられる。即ち、ＣＡドメインの個数が１個である場合、１個のチャネル割当ユニット６１のみが存在し、ＣＡドメインの個数が２個である場合、２個のチャネル割当ユニット６１，６２が存在し、ＣＡドメインの個数が３個である場合、３個のチャネル割当ユニット６１〜６３が存在し、以下、同様にして、ＣＡドメインの個数と同じ個数のチャネル割当ユニットが存在する。
【００５７】
チャネル割当ユニット６１，６２，６３，・・・の各々は、チャネル割当の対象となるＣＡドメインをドメイン決定装置６００から受ける。そして、チャネル割当ユニット６１，６２，６３，・・・の各々は、その受けたＣＡドメインに含まれるアクセスポイントに対して、後述する方法によってチャネルを割り当てる。
【００５８】
また、チャネル割当ユニット６１，６２，６３，・・・の各々は、一旦、チャネル割当を行うと、その後、隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から定期的に取得し、その取得した隣接ＡＰリストおよび接続可能ＡＰリストに基づいて、チャネル割当の対象とするＣＡドメイン内のトポロジーの変化を監視する。そして、チャネル割当ユニット６１，６２，６３，・・・の各々は、トポロジーの変化が一定条件を満たす毎にチャネル割当を行う。
【００５９】
ドメイン決定装置６００は、隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から取得し、その取得した隣接ＡＰリストおよび接続可能ＡＰリストに基づいて、チャネル割当の対象となるＣＡドメインを決定する。その後、ドメイン決定装置６００は、後述する方法によってＣＡドメインを分割可能であるか否かを判定し、分割可能である場合、ＣＡドメインを２個のＣＡドメインに分割する。
【００６０】
そして、ドメイン決定装置６００は、ＣＡドメインが１個増える毎に、１個のチャネル割当ユニットを生成する。また、ドメイン決定装置６００は、チャネル割当ユニットを生成すると、その生成したチャネル割当ユニットに関する情報を通信手段６２０へ出力する。
【００６１】
ＣＡドメインは、最初、１個であり、チャネル割当ユニット６１のみが存在する。そして、ドメイン決定装置６００は、１個のＣＡドメインをチャネル割当ユニット６１のみへ出力する。
【００６２】
その後、ドメイン決定装置６００は、１個のＣＡドメインを２個のＣＡドメインＣＡ１，ＣＡ２に分割すると、チャネル割当ユニット６２を新たに生成し、一方のＣＡドメインＣＡ１をチャネル割当ユニット６１へ出力し、他方のＣＡドメインＣＡ２をチャネル割当ユニット６２へ出力する。そして、ドメイン決定装置６００は、チャネル割当ユニット６２が新たに生成されたことを示す情報を通信手段６２０へ出力する。
【００６３】
更に、ドメイン決定装置６００は、分割によってＣＡドメインが３個になると、チャネル割当ユニット６３を新たに生成し、ＣＡドメインＣＡ１をチャネル割当ユニット６１へ出力し、ＣＡドメインＣＡ２をチャネル割当ユニット６２へ出力し、ＣＡドメインＣＡ３をチャネル割当ユニット６３へ出力する。そして、ドメイン決定装置６００は、チャネル割当ユニット６３が新たに生成されたことを示す情報を通信手段６２０へ出力する。以下、同様にして、ドメイン決定装置６００は、分割によってＣＡドメインが増える毎に、１個のチャネル割当ユニットを新たに生成し、ＣＡドメインをそれぞれのチャネル割当ユニットへ出力する。そして、ドメイン決定装置６００は、１個のチャネル割当ユニットが新たに生成される毎に、新たに生成されたチャネル割当ユニットを示す情報を通信手段６２０へ出力する。
【００６４】
有線インターフェース６１０は、ネットワーク４０を介してパケットを受信し、その受信したパケットを通信手段６２０へ出力する。
【００６５】
また、有線インターフェース６１０は、通信手段６２０からパケットを受け、その受けたパケットを送信する。
【００６６】
通信手段６２０は、有線インターフェース６１０を介して監視サーバ５０から隣接ＡＰリストおよび接続可能ＡＰリストを定期的に取得する。そして、通信手段６２０は、その取得した隣接ＡＰリストおよび接続可能ＡＰリストをチャネル割当ユニット６１，６２，６３，・・・およびドメイン決定装置６００へ出力する。
【００６７】
この場合、通信手段６２０は、チャネル割当ユニット６１のみが存在するときは、その取得した隣接ＡＰリストおよび接続可能ＡＰリストをチャネル割当ユニット６１のみへ出力する。そして、通信手段６２０は、ドメイン決定装置６００から新たに生成されたチャネル割当ユニット６２を示す情報を受けると、その取得した隣接ＡＰリストおよび接続可能ＡＰリストをチャネル割当ユニット６１，６２へ出力する。更に、通信手段６２０は、ドメイン決定装置６００から新たに生成されたチャネル割当ユニット６３を示す情報を受けると、その取得した隣接ＡＰリストおよび接続可能ＡＰリストをチャネル割当ユニット６１〜６３へ出力する。このように、通信手段６２０は、新たに生成されたチャネル割当ユニットを示す情報をドメイン決定装置６００から受ける毎に、ＡＰリストおよび接続可能ＡＰリストの出力先であるチャネル割当ユニットを増やす、その時点で存在する全てのチャネル割当ユニットへＡＰリストおよび接続可能ＡＰリストを出力する。
【００６８】
また、通信手段６２０は、チャネル割当後のチャネルをチャネル割当ユニット６１，６２，６３，・・・から受け、その受けたチャネルを有線インターフェース６１０を介してチャネル割当の対象であるアクセスポイントへ送信する。
【００６９】
チャネル割当ユニット６１は、グラフ生成手段６１１と、判定手段６１２と、チャネル割当手段６１３とを含む。
【００７０】
グラフ生成手段６１１は、隣接ＡＰリストおよび接続可能ＡＰリストを通信手段６２０から定期的に受け、チャネル割当の対象となるアクセスポイントを示すＣＡドメインをドメイン決定装置６００から受ける。
【００７１】
そして、グラフ生成手段６１１は、その受けたＣＡドメイン、隣接ＡＰリストおよび接続可能ＡＰリトに基づいて、ＣＡドメイン内における端末装置１〜９およびアクセスポイント１０〜２０に関するトポロジーを作成する。そして、グラフ生成手段６１１は、その作成したトポロジーに基づいて、後述する方法によって、隣接する２つのアクセスポイント間の干渉の度合を示すエッジ重みを隣接する２つのアクセスポイント間の全てについて演算する。そうすると、グラフ生成手段６１１は、トポロジーおよびエッジ重みに基づいて、後述する方法によって、ＣＡドメインに含まれる全てのアクセスポイントが同じチャネルを割り当てられたと想定した場合におけるアクセスポイント間のエッジ重みを示す基本グラフを作成する。
【００７２】
そして、グラフ生成手段６１１は、基本グラフを最初に作成した場合、その作成した基本グラフをチャネル割当手段６１３へ出力し、２回目以降に基本グラフを作成した場合、その作成した基本グラフを判定手段６１２およびチャネル割当手段６１３へ出力する。
【００７３】
判定手段６１２は、基本グラフをグラフ生成手段６１１から受け、チャネル割当後の基本グラフである基準グラフをチャネル割当手段６１３から受ける。そして、判定手段６１２は、基本グラフおよび基準グラフに基づいて、後述する方法によって、チャネル割当処理を行うか否かを判定し、チャネル割当処理を行うと判定したとき、チャネル割当処理を行うための信号ＡＳＧＮをチャネル割当手段６１３へ出力する。一方、判定手段６１２は、チャネル割当処理を行わないと判定したとき、チャネル割当手段６１３へ何も出力しない。
【００７４】
チャネル割当手段６１３は、基本グラフをグラフ生成手段６１１から受け、信号ＡＳＧＮを判定手段６１２から受ける。
【００７５】
チャネル割当手段６１３は、基本グラフをグラフ生成手段６１１から最初に受けたとき、信号ＡＳＧＮの有無に拘わらず、後述する方法によってチャネル割当処理を行う。そして、チャネル割当手段６１３は、チャネル割当処理の後、基準グラフを判定手段６１２へ出力するとともに、チャネル割当後のチャネルを通信手段６２０へ出力する。
【００７６】
また、チャネル割当手段６１３は、１回目のチャネル割当処理が終わった後、信号ＡＳＧＮを判定手段６１２から受ける毎に、後述する方法によってチャネル割当処理を行う。そして、チャネル割当手段６１３は、チャネル割当処理後の基本グラフである基準グラフを判定手段６１２へ出力するとともに、チャネル割当後のチャネルを通信手段６２０へ出力する。
【００７７】
なお、チャネル割当ユニット６２，６３，・・・の各々は、チャネル割当ユニット６１と同じ構成からなる。
【００７８】
この発明の実施の形態における端末装置１〜９、アクセスポイント１０〜２０、監視サーバ５０およびチャネル割当装置６０の定義および処理概要等を表１に示す。
【００７９】
【表１】
2011049913.tif 000003
【００８０】
なお、チャネル割当装置６０は、論理的なものであり、単一のサーバ内に複数存在してもよいし、複数のサーバに分散配置されてもよいし、複数のチャネル割当装置を管理する管理装置が存在するようにしてもよい。
【００８１】
また、監視サーバ５０は、論理的なものであり、チャネル割当装置６０と同一のサーバ内に存在してもよいし、独立したサーバに存在してもよい。
【００８２】
図５および図６は、それぞれ、エッジ重みを演算する方法を説明するための第１および第２の概念図である。なお、図５および図６において、通信範囲ＲＥＧ１，ＲＥＧ２は、それぞれ、アクセスポイント１０，１１からのビーコンフレームが到達する範囲を示す。
【００８３】
図５を参照して、アクセスポイント１０の通信手段１１３は、アクセスポイント１１からのビーコンフレームを受信できない。また、アクセスポイント１１の通信手段１１３は、アクセスポイント１０からのビーコンフレームを受信できない。
【００８４】
従って、アクセスポイント１０の通信手段１１３は、アクセスポイント１０のアドレスＭＡＣａｄｄ１０と、アクセスポイント１０に隣接するアクセスポイントが存在しないことを示す隣接ＡＰリストＡＤＪ１＝［ＭＡＣａｄｄ１０／ＮＯ（＝隣接アクセスポイント無し）］を生成し、その生成した隣接ＡＰリストＡＤＪ１＝［ＭＡＣａｄｄ１０／ＮＯ（＝隣接アクセスポイント無し）］を有線インターフェース１１４を介して監視サーバ５０へ送信する。
【００８５】
また、アクセスポイント１１の通信装置１１３も、同様にして、隣接ＡＰリストＡＤＪ２＝［ＭＡＣａｄｄ１１／ＮＯ（＝隣接アクセスポイント無し）］を生成し、その生成した隣接ＡＰリストＡＤＪ２＝［ＭＡＣａｄｄ１１／ＮＯ（＝隣接アクセスポイント無し）］を有線インターフェース１１４を介して監視サーバ５０へ送信する。
【００８６】
更に、端末装置１の通信手段１０３は、アクセスポイント１０からのビーコンフレームを定期的に受信し、端末装置１がアクセスポイント１０に接続可能であることを検知する。そして、端末装置１の通信手段１０３は、端末装置１のアドレスＭＡＣａｄｄ１と、端末装置１が接続可能なアクセスポイント１０のアドレスＭＡＣａｄｄ１０とを含む接続可能ＡＰリストＣＡＰＬ１＝［ＭＡＣａｄｄ１／ＭＡＣａｄｄ１０］を生成し、その生成した接続可能ＡＰリストＣＡＰＬ１＝［ＭＡＣａｄｄ１／ＭＡＣａｄｄ１０］をアクセスポイント１０およびネットワーク４０を介して監視サーバ５０へ送信する。端末装置２，３の通信手段１０３は、同様にして、それぞれ、接続可能ＡＰリストＣＡＰＬ２＝［ＭＡＣａｄｄ２／ＭＡＣａｄｄ１０］および接続可能ＡＰリストＣＡＰＬ３＝［ＭＡＣａｄｄ３／ＭＡＣａｄｄ１０］を生成して監視サーバ５０へ送信する。
【００８７】
更に、端末装置４の通信手段１０３は、アクセスポイント１０からのビーコンフレームと、アクセスポイント１１からのビーコンフレームとを定期的に受信し、端末装置４がアクセスポイント１０，１１の両方に接続可能であることを検知する。そして、端末装置４の通信手段１０３は、端末装置４のアドレスＭＡＣａｄｄ４と、端末装置４が接続可能なアクセスポイント１０，１１のアドレスＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１とを含む接続可能ＡＰリストＣＡＰＬ４＝［ＭＡＣａｄｄ４／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］を生成し、その生成した接続可能ＡＰリストＣＡＰＬ４＝［ＭＡＣａｄｄ４／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］をアクセスポイント１０（または１１）およびネットワーク４０を介して監視サーバ５０へ送信する。端末装置５の通信手段１０３は、同様にして、接続可能ＡＰリストＣＡＰＬ５＝［ＭＡＣａｄｄ５／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］を生成し、その生成した接続可能ＡＰリストＣＡＰＬ５＝［ＭＡＣａｄｄ４／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］をアクセスポイント１０（または１１）およびネットワーク４０を介して監視サーバ５０へ送信する。
【００８８】
更に、端末装置６の通信手段１０３は、アクセスポイント１１からのビーコンフレームを定期的に受信し、端末装置６がアクセスポイント１１に接続可能であることを検知する。そして、端末装置６の通信手段１０３は、端末装置６のアドレスＭＡＣａｄｄ６と、端末装置６が接続可能なアクセスポイント１１のアドレスＭＡＣａｄｄ１１とを含む接続可能ＡＰリストＣＡＰＬ６＝［ＭＡＣａｄｄ６／ＭＡＣａｄｄ１１］を生成し、その生成した接続可能ＡＰリストＣＡＰＬ６＝［ＭＡＣａｄｄ６／ＭＡＣａｄｄ１１］をアクセスポイント１１およびネットワーク４０を介して監視サーバ５０へ送信する。端末装置７〜９の通信手段１０３は、同様にして、それぞれ、接続可能ＡＰリストＣＡＰＬ７＝［ＭＡＣａｄｄ７／ＭＡＣａｄｄ１１］、接続可能ＡＰリストＣＡＰＬ８＝［ＭＡＣａｄｄ８／ＭＡＣａｄｄ１１］、および接続可能ＡＰリストＣＡＰＬ９＝［ＭＡＣａｄｄ９／ＭＡＣａｄｄ１１］を生成して監視サーバ５０へ送信する。
【００８９】
そうすると、通信手段６２０は、監視サーバ５０から隣接ＡＰリストＡＤＪ１，ＡＤＪ２および接続可能ＡＰリストＣＡＰＬ１〜ＣＡＰＬ９を監視サーバ５０から取得してチャネル割当ユニット６１のグラフ生成手段６１１へ出力する。
【００９０】
チャネル割当ユニット６１のグラフ生成手段６１１は、隣接ＡＰリストＡＤＪ１，ＡＤＪ２に基づいて、アクセスポイント１０，１１が相互に相手の通信範囲内に存在しないこと（即ち、アクセスポイント１０，１１がアクセスポイント１０，１１の通信範囲ＲＥＧ１，ＲＥＧ２の重複領域ＲＥＧ３内に存在しないこと）を検知する。
【００９１】
また、チャネル割当ユニット６１のグラフ生成手段６１１は、接続可能ＡＰリストＣＡＰＬ１〜ＣＡＰＬ９に基づいて、端末装置１〜３がアクセスポイント１０の通信範囲ＲＥＧ１内のみに存在することを検知し、端末装置４，５がアクセスポイント１０，１１の通信範囲ＲＥＧ１，ＲＥＧ２の重複領域ＲＥＧ３内に存在することを検知し、端末装置６〜９がアクセスポイント１１の通信範囲ＲＥＧ２内のみに存在することを検知する。
【００９２】
そうすると、チャネル割当ユニット６１のグラフ生成手段６１１は、端末装置１〜９のアクセスポイント１０，１１への接続可能性と、アクセスポイント１０，１１の相互の接続関係とを示すトポロジー（図５参照）を作成する。
【００９３】
図６を参照して、アクセスポイント１０の通信手段１１３は、上述した方法によって、隣接ＡＰリストＡＤＪ１’＝［ＭＡＣａｄｄ１０／ＭＡＣａｄｄ１１］を監視サーバ５０へ送信し、アクセスポイント１１は、上述した方法によって、隣接ＡＰリストＡＤＪ２’＝［ＭＡＣａｄｄ１１／ＭＡＣａｄｄ１０］を監視サーバ５０へ送信する。
【００９４】
また、端末装置１の通信手段１０３は、上述した方法によって、接続可能ＡＰリストＣＡＰＬ１’＝［ＭＡＣａｄｄ１／ＭＡＣａｄｄ１０］を監視サーバ５０へ送信し、端末装置２の通信手段１０３は、上述した方法によって、接続可能ＡＰリストＣＡＰＬ２’＝［ＭＡＣａｄｄ２／ＭＡＣａｄｄ１０］を監視サーバ５０へ送信する。
更に、端末装置３〜６の通信手段１０３は、上述した方法によって、それぞれ、接続可能ＡＰリストＣＡＰＬ３’＝［ＭＡＣａｄｄ３／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］、接続可能ＡＰリストＣＡＰＬ４’＝［ＭＡＣａｄｄ４／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］、接続可能ＡＰリストＣＡＰＬ５’＝［ＭＡＣａｄｄ５／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］、および接続可能ＡＰリストＣＡＰＬ６’＝［ＭＡＣａｄｄ６／ＭＡＣａｄｄ１０，ＭＡＣａｄｄ１１］を監視サーバ５０へ送信する。
【００９５】
更に、端末装置７〜９の通信手段１０３は、上述した方法によって、それぞれ、接続可能ＡＰリストＣＡＰＬ７’＝［ＭＡＣａｄｄ７／ＭＡＣａｄｄ１１］、接続可能ＡＰリストＣＡＰＬ８’＝［ＭＡＣａｄｄ８／ＭＡＣａｄｄ１１］、および接続可能ＡＰリストＣＡＰＬ９’＝［ＭＡＣａｄｄ９／ＭＡＣａｄｄ１１］を監視サーバ５０へ送信する。
【００９６】
そうすると、通信手段６２０は、監視サーバ５０から隣接ＡＰリストＡＤＪ１’，ＡＤＪ２’および接続可能ＡＰリストＣＡＰＬ１’〜ＣＡＰＬ９’を監視サーバ５０から取得してチャネル割当ユニット６１のグラフ生成手段６１１へ出力する。
【００９７】
チャネル割当ユニット６１のグラフ生成手段６１１は、隣接ＡＰリストＡＤＪ１’，ＡＤＪ２’に基づいて、アクセスポイント１０，１１が相互に相手の通信範囲内に存在すること（即ち、アクセスポイント１０，１１がアクセスポイント１０，１１の通信範囲ＲＥＧ１，ＲＥＧ２の重複領域ＲＥＧ４内に存在すること）を検知する。
【００９８】
また、チャネル割当ユニット６１のグラフ生成手段６１１は、接続可能ＡＰリストＣＡＰＬ１’〜ＣＡＰＬ９’に基づいて、端末装置１，２がアクセスポイント１０の通信範囲ＲＥＧ１内のみに存在することを検知し、端末装置３〜６がアクセスポイント１０，１１の通信範囲ＲＥＧ１，ＲＥＧ２の重複領域ＲＥＧ４内に存在することを検知し、端末装置７〜９がアクセスポイント１１の通信範囲ＲＥＧ２内のみに存在することを検知する。
【００９９】
そうすると、チャネル割当ユニット６１のグラフ生成手段６１１は、端末装置１〜９のアクセスポイント１０，１１への接続可能性と、アクセスポイント１０，１１の相互の接続関係とを示すトポロジー（図６参照）を作成する。
【０１００】
隣接する２つのアクセスポイント間の干渉の度合を示すエッジ重みは、次の方法によって演算される。エッジ重みをＷとし、重複領域ＲＥＧ３またはＲＥＧ４に存在する端末装置の個数をＮｏｖｅｒｌａｐとし、通信範囲ＲＥＧ１および通信範囲ＲＥＧ２の全体に含まれる端末装置の全数をＮａｌlとすると、エッジ重みＷは、次の式によって演算される。
【０１０１】
【数１】
2011049913.tif 000004
【０１０２】
式（１）の上側の式は、隣接する２個のアクセスポイントが相互に相手の通信範囲外に存在する場合におけるエッジ重みＷを表し、式（１）の下側の式は、隣接する２個のアクセスポイントが相互に相手の通信範囲内に存在する場合におけるエッジ重みＷを表す。
【０１０３】
図５に示すトポロジーにおいては、隣接する２つのアクセスポイント１０，１１が相互に相手の通信範囲外に存在するので、アクセスポイント１０，１１間のエッジ重みＷ１は、式（１）の上側の式によって演算される。この場合、Ｎａｌｌは、９個であり、Ｎｏｖｅｒｌａｐは、２個であるので、エッジ重みＷ１は、Ｗ１＝２／９となる。
【０１０４】
また、図６に示すトポロジーにおいては、隣接する２つのアクセスポイント１０，１１が相互に相手の通信範囲内に存在するので、アクセスポイント１０，１１間のエッジ重みＷ２は、式（１）の下側の式によって演算される。この場合、Ｎａｌｌは、９個であり、Ｎｏｖｅｒｌａｐは、４個であるので、エッジ重みＷ２は、Ｗ２＝（９−４）／９＝５／９となる。
【０１０５】
図５および図６において、斜線の領域は、隠れ端末の影響を受ける領域である。そうすると、エッジ重みＷ１は、２つのアクセスポイント１０，１１のいずれかに接続可能な端末装置１〜９の全数Ｎａｌｌに対する隠れ端末の影響を受ける領域に存在する端末装置の個数Ｎｏｖｅｒｌａｐを表す。また、エッジ重みＷ２は、２つのアクセスポイント１０，１１のいずれかに接続可能な端末装置１〜９の全数Ｎａｌｌに対する隠れ端末の影響を受ける領域に存在する端末装置の個数（Ｎａｌｌ−Ｎｏｖｅｒｌａｐ）を表す。
【０１０６】
従って、式（１）によって演算されるエッジ重みＷは、隣接する２つのアクセスポイントの通信範囲内に存在する端末装置の全数に対する隠れ端末の影響を受ける領域に存在する端末装置の個数を表す。
【０１０７】
チャネル割当装置６０のドメイン決定装置６００は、端末装置１〜９からの接続可能ＡＰリストと、アクセスポイント１０〜２０からの隣接ＡＰリストとを監視サーバ５０から取得し、その取得した接続可能ＡＰリストおよび隣接ＡＰリストに基づいて、上述した方法によって、端末装置１〜９とアクセスポイント１０〜２０との接続可能性と、アクセスポイント１０〜２０の相互の接続関係とを示すトポロジー（図１参照）を作成する。
【０１０８】
そして、チャネル割当装置６０のドメイン決定装置６００は、アクセスポイント１０〜２０からなる集合をチャネル割当の対象となるＣＡドメインＣＡ０として決定する。
【０１０９】
そうすると、チャネル割当装置６０のドメイン決定装置６００は、ＣＡドメインＣＡ０をチャネル割当ユニット６１のグラフ生成手段６１１へ出力する。これによって、チャネル割当の対象となるＣＡドメインＣＡ０がチャネル割当ユニット６１に与えられる。なお、この場合、ＣＡドメインは、１個のみであるので、チャネル割当ユニット６１のみが存在する。
【０１１０】
そして、チャネル割当ユニット６１のグラフ生成手段６１１は、ドメイン決定装置６００からＣＡドメインＣＡ０を受け、ＣＡドメインＣＡ０に含まれるアクセスポイント１０〜２０をチャネル割当の対象であるアクセスポイントとして検知する。
【０１１１】
その後、チャネル割当ユニット６１のグラフ生成手段６１１は、ＣＡドメインＣＡ０に含まれるアクセスポイント１０〜２０間のエッジ重みを上述した方法によって演算して基本グラフを作成する。
【０１１２】
［基本グラフの作成］
図７は、基本グラフの作成方法を説明するためのトポロジーの具体例を示す図である。また、図８は、基本グラフの具体例を示す図である。
【０１１３】
図７を参照して、３個のアクセスポイント１０，１１，１３が１つのＣＡドメインに属する。そして、アクセスポイント１０の通信範囲ＲＥＧ１は、アクセスポイント１１の通信範囲ＲＥＧ２およびアクセスポイント１３の通信範囲ＲＥＧ６と重複する。また、アクセスポイント１１の通信範囲ＲＥＧ２は、アクセスポイント１０の通信範囲ＲＥＧ１、アクセスポイント１２の通信範囲ＲＥＧ５およびアクセスポイント１３の通信範囲ＲＥＧ６と重複する。更に、アクセスポイント１２の通信範囲ＲＥＧ５は、アクセスポイント１１の通信範囲ＲＥＧ２とアクセスポイント１３の通信範囲ＲＥＧ６と重複する。
【０１１４】
また、端末装置２，３は、アクセスポイント１０の通信範囲ＲＥＧ１とアクセスポイント１１の通信範囲ＲＥＧ２との重複領域に存在する。端末装置５，６は、３個のアクセスポイント１０，１１，１３の通信範囲ＲＥＧ１，ＲＥＧ２，ＲＥＧ６の重複領域に存在する。端末装置７は、３個のアクセスポイント１１，１２，１３の通信範囲ＲＥＧ２，ＲＥＧ５，ＲＥＧ６の重複領域に存在する。端末装置８は、アクセスポイント１１の通信範囲ＲＥＧ２とアクセスポイント１２の通信範囲ＲＥＧ５との重複領域に存在する。
【０１１５】
チャネル割当ユニット６１のグラフ生成手段６１１は、図７に示すトポロジーに基づいて、アクセスポイント１０〜１３が相互に同じチャネルを使用したと仮定した場合のアクセスポイント１０−アクセスポイント１１間のエッジ重み、アクセスポイント１０−アクセスポイント１２間のエッジ重み、アクセスポイント１０−アクセスポイント１３間のエッジ重み、アクセスポイント１１−アクセスポイント１２間のエッジ重み、およびアクセスポイント１１−アクセスポイント１３間のエッジ重みを上述した方法によって演算する。つまり、チャネル割当ユニット６１のグラフ生成手段６１１は、干渉関係が生じる２つのアクセスポイント間について、その干渉の度合いを示すエッジ重みを演算する。
そして、チャネル割当ユニット６１のグラフ生成手段６１１は、ＣＡドメインに含まれるアクセスポイント１０，１１，１３と、ＣＡドメインに含まれるアクセスポイント１１と干渉関係を生じるアクセスポイント１２とを頂点（Ｖｅｒｔｅｘ）とし、隣接干渉関係にある頂点（Ｖｅｒｔｅｘ）間を枝（エッジ重み）で結んだ基本グラフＢＧ１を作成する（図８参照）。
【０１１６】
この場合、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１０の通信範囲ＲＥＧ１とアクセスポイント１２の通信範囲ＲＥＧ５との重複領域が存在しないので、アクセスポイント１０−アクセスポイント１２間のエッジ重みを“０”と演算するが、その演算したエッジ重み（＝０）をアクセスポイント１０−１２間の枝として表示しない。
【０１１７】
また、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１２がＣＡドメイン外（チャネル割当の対象外）であり、アクセスポイント１３がチャネル割当を禁止されたアクセスポイントであるので、アクセスポイント１２−アクセスポイント１３間のエッジ重みを演算しない。
【０１１８】
但し、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１１がチャネル割当の対象であるので、アクセスポイント１１のチャネルを変更することにより、アクセスポイント１１−アクセスポイント１２間の干渉度合いを表すエッジ重みを低減し得る。従って、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１２を頂点（Ｖｅｒｔｅｘ）として取り扱い、アクセスポイント１１−アクセスポイント１２間のエッジ重みを演算する。
【０１１９】
また、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１０，１１がチャネル割当の対象であるので、アクセスポイント１０，１１のチャネルを変更することにより、アクセスポイント１０−アクセスポイント１３間およびアクセスポイント１１−アクセスポイント１３間の干渉度合いを表すエッジ重みを低減し得る。従って、チャネル割当ユニット６１のグラフ生成手段６１１は、アクセスポイント１３を頂点（Ｖｅｒｔｅｘ）として取り扱い、アクセスポイント１０−アクセスポイント１３間のエッジ重みおよびアクセスポイント１１−アクセスポイント１３間のエッジ重みを演算する。
【０１２０】
なお、基本グラフは、チャネル割当の対象となるアクセスポイントが同じチャネルを使用することを想定した場合の隣接するアクセスポイント間のエッジ重みを示すグラフである。
【０１２１】
このように、チャネル割当ユニット６１のグラフ生成手段６１１は、チャネル割当の対象となるアクセスポイント１０，１１，１３と、図７に示すトポロジーとに基づいて、アクセスポイント１０，１１，１３を頂点とするとともに、干渉関係にあるアクセスポイント間の干渉の度合を示すエッジ重みを演算し、その演算したエッジ重みによってアクセスポイント１０〜１４のうちの干渉関係にある２つのアクセスポイント間を結んだ基本グラフＢＧ１を生成する。
【０１２２】
チャネル割当ユニット６１のグラフ生成手段６１１は、上述した方法によって、基本グラフを定期的に生成し、その生成した基本グラフを判定手段６１２およびチャネル割当手段６１３へ出力する。
【０１２３】
［チャネル割当］
チャネル割当ユニット６１のチャネル割当手段６１３は、基本グラフをグラフ生成手段６１１から受けると、その受けた基本グラフから同一チャネルを有するアクセスポイント間のエッジ重みのみを取り出し、その取り出したエッジ重みを表示した干渉グラフを作成する。そして、チャネル割当ユニット６１のチャネル割当手段６１３は、次の評価関数を満たすようにアクセスポイントにチャネルを割り当てる。
【０１２４】
（評価関数１）干渉グラフ全体でのエッジ重みの最大値が最小
（評価関数２）干渉グラフ全体のエッジ重みの総和が最小
（評価関数３）チャネルを変更するアクセスポイントまたは端末装置の個数が最小
評価関数１は、サービス範囲を最大化するときに用いられ、評価関数２は、ネットワーク全体のパフォーマンスを向上させるときに用いられ、評価関数３は、チャネル切替に伴う影響を抑制する場合に用いられる。
【０１２５】
なお、チャネル割当ユニット６１のチャネル割当手段６１３は、評価関数１〜評価関数３の各々を独立に適用してもよく、評価関数１〜評価関数３のうちの２個以上の評価関数を優先度に応じて順番に適用してもよい。
【０１２６】
チャネル割当ユニット６１のチャネル割当手段６１３は、対象となる規模（アクセスポイントの個数および割り当て可能なチャネル数）、適用可能な計算機資源、および評価関数の精度によって、一般的な近似解法またはヒューリスティックアルゴリズムを適用してチャネル割当を行う。
【０１２７】
図９は、チャネル割当前の干渉グラフを示す図である。図１０は、チャネル割当後の干渉グラフを示す図である。図１１は、チャネル割当後のトポロジーを示す図である。
【０１２８】
図９を参照して、図８に示す基本グラフＢＧ１において、アクセスポイント１２，１３がＣＡドメインに含まれ、アクセスポイント１３がチャネル変更を可能とした場合、基本グラフＢＧ２が得られる。
【０１２９】
以下のチャネル割当においては、使用可能なチャネルを２個のチャネルＣＨ１，ＣＨ６とし、評価関数は、評価関数２からなるものとする。
【０１３０】
チャネル割当ユニット６１のチャネル割当手段６１３は、基本グラフＢＧ２をグラフ生成手段６１１から受け、その受けた基本グラフＢＧ２から干渉グラフＩＦＲ１を作成する。この場合、基本グラフＢＧ２は、アクセスポインと１０〜１３が同一チャネルを有することを想定して作成されているので、干渉グラフＩＦＲ１は、基本グラフＢＧ２と同じである。
【０１３１】
その後、チャネル割当ユニット６１のチャネル割当手段６１３は、干渉グラフＩＦＲ１（＝基本グラフＢＧ２）全体のエッジ重み（４／６，３／６，２／６，２／５，１／４）の総和（＝４／６＋３／６＋２／６＋２／５＋１／４＝２．１５）が最小になるようにアクセスポイント１０〜１３に割り当てるチャネルを探索する。
【０１３２】
その結果、チャネルＣＨ１がアクセスポイント１０，１２に割り当てられ、チャネルＣＨ６がアクセスポイント１１，１３に割り当てられる。
【０１３３】
この場合、干渉グラフＩＦＲ２全体のエッジ重みの総和は、３／６＝０．５になる。
【０１３４】
チャネル割当ユニット６１のチャネル割当手段６１３は、チャネル割当が終了すると、干渉グラフＩＦＲ２を保持するとともに、干渉グラフＩＦＲ２を判定手段６１２へ出力する。
【０１３５】
また、チャネル割当ユニット６１のチャネル割当手段６１３は、チャネル割当が終了すると、割り当てたチャネルを通信手段６２０へ出力する。この場合、チャネル割当ユニット６１のチャネル割当手段６１３は、アクセスポイント１０〜１３のアドレスＭＡＣａｄｄ１０〜ＭＡＣａｄｄ１３とチャネルＣＨ１，ＣＨ６とを対応付けた［ＭＡＣａｄｄ１０：ＣＨ１／ＭＡＣａｄｄ１１：ＣＨ６／ＭＡＣａｄｄ１２：ＣＨ１／ＭＡＣａｄｄ１３：ＣＨ６］をチャネル割当後のチャネルとして通信手段６２０へ出力する。
【０１３６】
そして、チャネル割当ユニット６１の通信手段６２０は、［ＭＡＣａｄｄ１０：ＣＨ１／ＭＡＣａｄｄ１１：ＣＨ６／ＭＡＣａｄｄ１２：ＣＨ１／ＭＡＣａｄｄ１３：ＣＨ６］を含むパケットＰＫＴ１＝［ＭＡＣａｄｄ１０：ＣＨ１／ＭＡＣａｄｄ１１：ＣＨ６／ＭＡＣａｄｄ１２：ＣＨ１／ＭＡＣａｄｄ１３：ＣＨ６］を生成し、その生成したパケットＰＫＴ１＝［ＭＡＣａｄｄ１０：ＣＨ１／ＭＡＣａｄｄ１１：ＣＨ６／ＭＡＣａｄｄ１２：ＣＨ１／ＭＡＣａｄｄ１３：ＣＨ６］を有線インターフェース６１を介してアクセスポイント１０〜１３へ送信する。
【０１３７】
［グラフ変動の監視］
チャネル割当ユニット６１の判定手段６１２は、チャネル割当が終了した後、ＣＡドメイン内のトポロジーの変動を基本グラフの変動として監視する。
【０１３８】
チャネル割当ユニット６１の判定手段６１２は、チャネル割当後の干渉グラフをチャネル割当手段６１３から受け、その受けた干渉グラフにおいて、全てのアクセスポイントが同じチャネルを用いたことを想定した基本グラフを基準グラフとして作成する。
【０１３９】
また、チャネル割当ユニット６１の判定手段６１２は、グラフ生成手段６１１から基本グラフを定期的に受ける。そして、チャネル割当ユニット６１の判定手段６１２は、最新の基本グラフを基準グラフと比較し、最新の基本グラフにおける全てのエッジ重みの変動量Ｗｃｈｇを検出する。
【０１４０】
この変動量Ｗｃｈｇは、１つのエッジ重みの変化量ΔＷを全てのエッジについて加算したものによって表わされる。
【０１４１】
そして、チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇを検出すると、その検出した変動量Ｗｃｈｇがしきい値βよりも大きいことをｎ（ｎは正の整数）回連続して満たすか否かを判定する。即ち、チャネル割当ユニット６１の判定手段６１２は、次式が成立するか否かを判定する。
【０１４２】
【数２】
2011049913.tif 000005
【０１４３】
なお、式（２）の右辺は、変動量Ｗｃｈｇを表す。また、αは、エッジ当たりの重み変動のしきい値であり、βは、グラフ全体の重み変動のしきい値であり、関数ｆ（ｘ）は、エッジ重みの局所変動を反映するためのスケーリング関数である。
【０１４４】
このように、この発明の実施の形態においては、判定手段６１２は、２つのしきい値α，βを用いてチャネル割当処理を行なう必要があるエッジ重みの変動量Ｗｃｈｇが生じたか否かを判定する。これによって、エッジ重みの局所的変動および大局的変動を反映してチャネル割当を行なうかどうかを判定できる。また、頻繁なチャネル割当を抑制して、端末装置１〜９およびアクセスポイント１０〜２０の頻繁なチャネル切替を抑制できる。
【０１４５】
チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇがしきい値βよりも大きいことをｎ回連続して満たしたと判定したとき、信号ＡＳＧＮを生成し、その生成した信号ＡＳＧＮをチャネル割当手段６１３へ出力する。
【０１４６】
しきい値α，βおよびスケーリング関数ｆ（ｘ）の具体例について説明する。この場合、干渉グラフにおけるエッジの総数を“２０”とする。
【０１４７】
（ａ）局所変動に鈍感な例
スケーリング関数ｆ（ｘ）を局所変動に鈍感なｆ（ｘ）＝ｘ＝｜ΔＷ｜−αとする。｜ΔＷ｜は、［０，１］の範囲であり、しきい値αをα＝０．３とし、例えば、エッジ当たりの平均の変動量｜ΔＷ｜ａｖｇが｜ΔＷ｜ａｖｇ＝０．４である場合、グラフ全体の重み変動のしきい値βを全体の変動見積値の半分として次式によって設定する。
【０１４８】
【数３】
2011049913.tif 000006
【０１４９】
（ｂ）局所変動に敏感な例
スケーリング関数ｆ（ｘ）を局所変動に敏感なｆ（ｘ）＝ｘ２＝（ΔＷ｜−α）２とする。しきい値αをα＝０．３とし、エッジの総数（＝２０）のうち、１つのエッジのみが最大局所変動｜ΔＷ｜ｍａｘ＝１．０を起こし、他のエッジの変動が“０”である場合、グラフ全体の重み変動のしきい値βを次式を満たすうように設定する。
【０１５０】
【数４】
2011049913.tif 000007
【０１５１】
例えば、β＝０．４と設定した場合、エッジ当たりの平均の重み変動量に置き換えると、｜ΔＷ｜ａｖｇ＞０．５が必要である。
【０１５２】
なお、この場合、スケーリング関数ｆ（ｘ）をｆ（ｘ）＝ｅｘ＝ｅ（ΔＷ｜−α）としてもよい。
【０１５３】
変動量Ｗｃｈｇを検出する具体例について説明する。以下においては、しきい値αを０．１とし、しきい値βを０．０１とし、スケーリング関数をｆ（ｘ）＝ｘとする。
【０１５４】
図１２は、変動後のトポロジーを示す図である。また、図１３は、基本グラフの他の具体例を示す図である。
【０１５５】
図１２を参照して、図１１に示すトポロジーにおいて、２台の端末装置１，９が追加された場合を想定する。
【０１５６】
その結果、チャネル割当ユニット６１のグラフ生成手段６１１は、上述した方法によって基本グラフＢＧ３（図１３の（ａ）参照）を作成し、その作成した基本グラフＢＧ３を判定手段６１２へ出力する。
【０１５７】
チャネル割当ユニット６１の判定手段６１２は、基本グラフＢＧ３を受けると、図１０に示す干渉グラフＩＦＲ２においてアクセスポイント１０〜１３のチャネルを同一のチャネルにしたグラフを基準グラフＳＴＤ１（図１３の（ｂ）参照）とする。
【０１５８】
そして、チャネル割当ユニット６１の判定手段６１２は、基本グラフＢＧ３を基準グラフＳＴＤ１と比較し、基本グラフＢＧ３における全てのエッジにおけるエッジ重みの変化量｜ΔＷ｜を検出する。即ち、チャネル割当ユニット６１の判定手段６１２は、アクセスポイント１０−アクセスポイント１１間におけるエッジ重みの変化量＝１／６（＝４／８−４／６）と、アクセスポイント１０−アクセスポイント１３間におけるエッジ重みの変化量＝４／３５（＝２／７−２／５）と、アクセスポイント１１−アクセスポイント１３間におけるエッジ重みの変化量＝１／８（＝５／８−３／６）と、アクセスポイント１１−アクセスポイント１２間におけるエッジ重みの変化量＝１／２４（＝３／８−２／６）と、アクセスポイント１２−アクセスポイント１３間におけるエッジ重みの変化量＝１／１２（＝２／６−１／４）とを検出する。
【０１５９】
その後、チャネル割当ユニット６１の判定手段６１２は、その検出した変化量の総和（＝（１／６−０．１）＋（４／３５−０．１）＋（１／８−０．１）＋（１／２４−０．１）＋（１／１２−０．１）＝０．０３１）を変動量Ｗｃｈｇとして演算する。
【０１６０】
そうすると、チャネル割当ユニット６１の判定手段６１２は、その演算した変動量Ｗｃｈｇ（＝０．０３１）をしきい値β（＝０．０１）と比較し、変動量Ｗｃｈｇ（＝０．０３１）がしきい値β（＝０．０１）よりも大きいことがｎ回連続して満たされたと判定する。
【０１６１】
そして、チャネル割当ユニット６１の判定手段６１２は、信号ＡＳＧＮを生成し、その生成した信号ＡＳＧＮをチャネル割当手段６１３へ出力する。
【０１６２】
チャネル割当ユニット６１のチャネル割当手段６１３は、１回目のチャネル割当を行った後は、判定手段６１２から信号ＡＳＧＮを受ける毎に、上述した方法によってチャネル割当を行う。そして、チャネル割当ユニット６１のチャネル割当手段６１３は、その割り当てたチャネルを通信手段６２０へ出力する。
【０１６３】
図１４は、変動量の判定動作と、チャネル割当のタイミングとの関係を示す概念図である。
【０１６４】
図１４を参照して、チャネル割当ユニット６１のチャネル割当手段６１３は、タイミングｔ１において、上述した方法によってチャネル割当を行い、判定手段６１２は、チャネル割当後の基本グラフである基準グラフを保持する。
【０１６５】
その後、チャネル割当ユニット６１のグラフ生成手段６１１は、監視情報取得間隔が経過したタイミングｔ２において、監視サーバ５０から新しい隣接ＡＰリストＡＤＪおよび接続可能ＡＰリストを取得する。そして、チャネル割当ユニット６１のグラフ生成手段６１１は、タイミングｔ２において、上述した方法によって、新しい基本グラフＢＧを作成し、その作成した新しい基本グラフを判定手段６１２へ出力する。
【０１６６】
そうすると、チャネル割当ユニット６１の判定手段６１２は、新しい基本グラフＢＧを基準グラフと比較し、上述した方法によって変動量Ｗｃｈｇ１を演算する。そして、チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇ１がしきい値βよりも大きいことがｎ回連続して満たされたか否かを判定する。変動量Ｗｃｈｇ１がしきい値βよりも小さいので、上記の条件が満たされず、チャネル割当ユニット６１の判定手段６１２は、信号ＡＳＧＮを生成しない。
【０１６７】
その後、チャネル割当ユニット６１のグラフ生成手段６１１は、タイミングｔ３，ｔ４，ｔ５において、上述した方法によって、新しい基本グラフＢＧを作成し、その作成した新しい基本グラフを判定手段６１２へ出力し、判定手段６１２は、新しい基本グラフを基準グラフと比較し、それぞれ、変動量Ｗｃｈｇ２，Ｗｃｈｇ３，Ｗｃｈｇ４を演算する。
【０１６８】
そして、チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇ２をしきい値βと比較して、変動量Ｗｃｈｇがしきい値βよりも大きいことが１回満たされたと判定する。
【０１６９】
その後、チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇ３をしきい値βと比較して、変動量Ｗｃｈｇがしきい値βよりも大きいことが２回連続して満たされたと判定する。
【０１７０】
更に、チャネル割当ユニット６１の判定手段６１２は、変動量Ｗｃｈｇ４をしきい値βと比較して、変動量Ｗｃｈｇがしきい値βよりも大きいことが３回連続して満たされたと判定する。
【０１７１】
そうすると、チャネル割当ユニット６１の判定手段６１２は、信号ＡＳＧＮを生成してチャネル割当手段６１３へ出力し、チャネル割当手段６１３は、タイミングｔ６において、信号ＡＳＧＮに応じて、上述した方法によってチャネル割当を行う。そして、チャネル割当ユニット６１の判定手段６１２は、基準グラフを保持する。
【０１７２】
以降、上述した動作が繰り返し実行され、ＣＡドメインにおけるエッジ重みの変動量Ｗｃｈｇが一定の条件を満たす毎にＣＡドメインに含まれるアクセスポイントに対するチャネル割当が行われる。
【０１７３】
上述したように、チャネル割当を行うための条件を変動量Ｗｃｈｇがしきい値βよりも大きいことがｎ回連続して満たされたことに設定することにより、アクセスポイントおよび端末装置におけるチャネルの頻繁な変更を抑制できる。
【０１７４】
［ＣＡドメインの分割］
図１５は、ＣＡドメインの分割方法を説明するための図である。図１５を参照して、アクセスポイント１０〜１７は、１個のＣＡドメインＣＡ１を形成している。そして、アクセスポイント１１は、アクセスポイント１４と干渉関係にあり、アクセスポイント１２は、アクセスポイント１４，１５と干渉関係にあり、アクセスポイント１３は、アクセスポイント１６と干渉関係にある。
【０１７５】
チャネル割当装置６０のドメイン決定装置６００は、隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から定期的に取得する。そして、チャネル割当装置６０のドメイン決定装置６００は、その取得した隣接ＡＰリストおよび接続可能ＡＰリストに基づいて、アクセスポイント１０〜１７のトポロジーを把握し、干渉関係にあるアクセスポイント間について、上述した方法によってエッジ重みを演算する。
【０１７６】
この場合、アクセスポイント１１−１４間のエッジ重みＷ１は、“３”であり、アクセスポイント１２−１４間のエッジ重みＷ２は、“１”であり、アクセスポイント１２−１５間のエッジ重みＷ３は、“２”であり、アクセスポイント１３−１６間のエッジ重みＷ４は、“５”である。
【０１７７】
そうすると、チャネル割当装置６０のドメイン決定装置６００は、エッジ重みＷ１〜Ｗ４の総和Ｗｔｏｔａｌ（＝１１）を演算し、その演算した総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さいか否かを判定する。
【０１７８】
総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さいと判定されたとき、チャネル割当装置６０のドメイン決定装置６００は、アクセスポイント１０〜１７からなるＣＡドメインＣＡ１をアクセスポイント１０〜１３からなるＣＡドメインＣＡ２と、アクセスポイント１４〜１７からなるＣＡドメインＣＡ３とに分割する。
【０１７９】
そして、チャネル割当装置６０のドメイン決定装置６００は、チャネル割当の対象であるＣＡドメインＣＡ１が２個のＣＡドメインＣＡ２，ＣＡ３に増加したので、チャネル割当ユニット６２を新たに生成し、ＣＡドメインＣＡ２をチャネル割当ユニット６１のグラフ生成手段６１１へ出力し、ＣＡドメインＣＡ３をチャネル割当ユニット６２のグラフ生成手段６１１へ出力する。
【０１８０】
一方、総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さくないと判定されたとき、チャネル割当装置６０のドメイン決定装置６００は、ＣＡドメインＣＡ１を分割せずに、ＣＡドメインＣＡ１をチャネル割当の対象としてチャネル割当ユニット６１のグラフ生成手段６１１へ出力する。この場合、チャネル割当装置６０のドメイン決定装置６００は、チャネル割当ユニット６２を新たに生成しない。
【０１８１】
チャネル割当装置６０のドメイン決定装置６００は、元のＣＡドメインＣＡ１において、干渉関係にある２つのアクセスポイント間のエッジ重みＷを全て演算し、その演算したエッジ重みＷに基づいて、総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さくなるアクセスポイント間（図１５においては、アクセスポイント１１〜１３とアクセスポイント１４〜１６との間）を探索する。
【０１８２】
そして、チャネル割当装置６０のドメイン決定装置６００は、総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さくなるアクセスポイント間を探索できれば、その探索したアクセスポイント間で元のＣＡドメインを２個以上のＣＡドメインに分割し、その分割した２個以上のＣＡドメインをチャネル割当の新たな対象として決定する。一方、チャネル割当装置６０のドメイン決定装置６００は、総和Ｗｔｏｔａｌがしきい値Ｗｔｏｔａｌ＿ｔｈよりも小さくなるアクセスポイント間を探索できなければ、元のＣＡドメインを維持して元のＣＡドメインをチャネル割当の対象として決定する。
【０１８３】
そして、チャネル割当装置６０のドメイン決定装置６００は、その決定したＣＡドメインをＣＡドメインの個数に応じて存在するチャネル割当ユニット６１等へ出力する。
【０１８４】
チャネル割当装置６０のドメイン決定装置６００は、上述したＣＡドメインの分割が可能であるか否かの判定を隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から新たに取得する毎に実行する。従って、ＣＡドメインの分割は、ドメイン決定装置６００が隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から取得する毎に行なわれる場合もあれば、ドメイン決定装置６００が隣接ＡＰリストおよび接続可能ＡＰリストを監視サーバ５０から取得する周期と無関係に行なわれることもある。
【０１８５】
図１６は、分割後のＣＡドメインの概念図である。図１６を参照して、チャネル割当装置６０のドメイン決定装置６００は、上述した方法によって、図１に示すＣＡドメインＣＡ０をＣＡドメインＣＡ１〜ＣＡ３に分割し、３個のＣＡドメインＣＡ１〜ＣＡ３をチャネル割当の対象として決定する。
【０１８６】
そして、チャネル割当装置６０のドメイン決定装置６００は、１個のＣＡドメインＣＡ０が３個のＣＡドメインＣＡ１〜ＣＡ３に分割され、チャネル割当の対象となるＣＡドメインが２個増えたので、チャネル割当ユニット６２，６３を新たに生成する。
【０１８７】
そうすると、チャネル割当装置６０のドメイン決定装置６００は、ＣＡドメインＣＡ１をチャネル割当ユニット６１のグラフ生成手段６１１へ出力し、ＣＡドメインＣＡ２をチャネル割当ユニット６２のグラフ生成手段６１１へ出力し、ＣＡドメインＣＡ３をチャネル割当ユニット６３のグラフ生成手段６１１へ出力する。
【０１８８】
チャネル割当ユニット６１〜６３は、それぞれ、ＣＡドメインＣＡ１〜ＣＡ３をドメイン決定装置６００から受ける。そして、チャネル割当ユニット６１は、上述した方法によって、ＣＡドメインＣＡ１に含まれるアクセスポイント１０〜１６に対してチャネルを割り当て、その割り当てたチャネルをアクセスポイント１０〜１６へ送信する。また、チャネル割当ユニット６２は、上述した方法によって、ＣＡドメインＣＡ２に含まれるアクセスポイント１９，２０に対してチャネルを割り当て、その割り当てたチャネルをアクセスポイント１９，２０へ送信する。更に、チャネル割当ユニット６３は、上述した方法によって、ＣＡドメインＣＡ３に含まれるアクセスポイント１７，１８に対してチャネルを割り当て、その割り当てたチャネルをアクセスポイント１７，１８へ送信する。
【０１８９】
図１７は、図１に示すチャネル割当装置６０における動作を説明するためのフローチャートである。
【０１９０】
図１７を参照して、一連の動作が開始されると、チャネル割当装置６０のドメイン決定装置６００は、新しい隣接ＡＰリストおよび新しい接続可能ＡＰリストを監視サーバ５０から取得する毎に、上述した方法によってＣＡドメインを決定し（ステップＳ１）、その決定したＣＡドメインをチャネル割当ユニット６１，６２，６３，・・・へ出力する。この場合、チャネル割当ユニット６１等へ出力されるＣＡドメインは、ドメイン決定装置６００によって分割されたＣＡドメインも含む。
【０１９１】
そして、チャネル割当ユニット６１，６２，６３，・・・の各々は、上述した方法によってチャネル割当を行い（ステップＳ２）、その後、グラフの変動を監視する（ステップＳ３）。
【０１９２】
チャネル割当ユニット６１，６２，６３，・・・の各々は、グラフを監視した結果、エッジ重みの変動量Ｗｃｈｇを演算する。そして、チャネル割当ユニット６１，６２，６３，・・・の各々は、その演算した変動量Ｗｃｈｇが一定の条件を満たすか否かを判定する。即ち、チャネル割当装置６０は、チャネル変更条件を満たすか否かを判定する（ステップＳ４）。
【０１９３】
ステップＳ４において、チャネル変更条件を満たすと判定されたとき、一連の動作は、ステップＳ２へ戻る。
【０１９４】
一方、ステップＳ４において、チャネル変更条件を満たさないと判定されたとき、一連の動作は、ステップＳ３へ戻る。
【０１９５】
チャネル割当装置６０は、起動中、図１５に示すフローチャートを繰り返し実行し、チャネル割当を行う。
【０１９６】
［チャネル変更］
アクセスポイントおよび端末装置におけるチャネルをチャネル割当装置６０によって割り当てられたチャネルに変更する方法について説明する。
【０１９７】
チャネル割当装置６０によってアクセスポイント１０，１２にチャネルＣＨ１が割り当てられ、アクセスポイント１１，１３にチャネルＣＨ６が割り当てられると、アクセスポイント１０の通信手段１１３は、チャネル割当装置６０からパケットＰＫＴ１＝［ＭＡＣａｄｄ１０：ＣＨ１／ＭＡＣａｄｄ１１：ＣＨ６／ＭＡＣａｄｄ１２：ＣＨ１／ＭＡＣａｄｄ１３：ＣＨ６］を有線インターフェース１１４を介して受信する。
【０１９８】
そして、アクセスポイント１０の通信手段１１３は、パケットＰＫＴ１を参照して、チャネルＣＨ１がアクセスポイント１０に割り当てられていることを検知する。
【０１９９】
そうすると、アクセスポイント１０の通信手段１１３は、チャネルＣＨ１と、通信中断予定時間とを含むチャネル変更メッセージ＝［チャネルＣＨ１／通信中断予定時間］を作成し、その作成したチャネル変更メッセージ＝［チャネルＣＨ１／通信中断予定時間］を無線インターフェース１１２を介して端末装置２，３，５，６へ送信する。
【０２００】
そして、アクセスポイント１０の通信手段１１３は、無線インターフェース１１２のチャネルをチャネルＣＨ１に切り替える。また、アクセスポイント１０の通信手段１１３は、チャネルを切り替えると、通信中断予定時間の間、ビーコンフレームの送信を停止する。
【０２０１】
一方、端末装置２，３，５，６の各々において、通信手段１０３は、チャネル変更メッセージ＝［チャネルＣＨ１／通信中断予定時間］を無線インターフェース１０２を介して受信する。そして、端末装置２，３，５，６の各々の通信手段１０３は、チャネル変更メッセージの受信後、アクセスポイント１０とのリンクの切断を検知した場合、通信中断予定時間およびビーコンフレームの送信間隔の期間内において、指定された切り替え後のチャネルＣＨ１でアクセスポイント１０を探索する。
【０２０２】
その後、端末装置２，３，５，６の各々の通信手段１０３は、切り替え後のチャネルＣＨ１でアクセスポイント１０を発見できた場合、再度、アソシエーションし、アクセスポイント１０に接続する。
【０２０３】
一方、端末装置２，３，５，６の各々の通信手段１０３は、切り替え後のチャネルＣＨ１でアクセスポイント１０を発見できなかった場合、通常のチャネルサーチから開始する。
【０２０４】
アクセスポイント１１〜１３およびその配下の端末装置も、アクセスポイント１０および端末装置２，３，５，６と同じ動作に従ってチャネルを切り替える。
【０２０５】
なお、チャネル変更メッセージは、アクセスポイントに接続している端末装置のみへ送信されるので、複数のアクセスポイントの複数の通信範囲の重複領域に存在する端末装置に対しても、チャネル割当後の１個のチャネルが通知される。
【０２０６】
このように、この発明の実施の形態においては、アクセスポイントおよび端末装置におけるチャネルを切り替える場合、通信中断予定時間を設け、その期間内は、無線通信を中止してチャネルの切替を行うようにしている。
【０２０７】
従って、アクセスポイントと端末装置との間の無線通信の切断を防止してチャネルの切替から早期に復帰できるとともに、チャネルの切替によってアクセスポイントが変更するのを抑制できる。
【０２０８】
この発明の実施の形態によれば、チャネル割当ユニット６１，６２，６３，・・・の各々は、チャネル割当の対象として決定されたＣＡドメインをドメイン決定装置６００から受け、その受けたＣＡドメインに含まれるアクセスポイントに対してチャネル割当を行う。
【０２０９】
また、この発明の実施の形態によれば、アクセスポイント間の干渉の度合を示すエッジ重みの変動量Ｗｃｈｇがしきい値βよりも大きいことがｎ回連続して満たされた時にチャネル割当が行われ、アクセスポイント１０〜２０および端末装置１〜９におけるチャネルの変更が行われる。
【０２１０】
従って、チャネル割当のタイミングおよび範囲を明確にでき、安定したチャネル割当を行うことができる。
【０２１１】
上記においては、通信ネットワークシステム１００において、使用可能なチャネル数が２個である場合についてアクセスポイント１０〜２０へのチャネル割当について説明したが、この発明の実施の形態においては、これに限らず、通信ネットワークシステム１００において使用可能なチャネル数は、３個以上であってもよく、一般的には、２個以上であればよい。
【０２１２】
また、上記においては、端末装置１〜９およびアクセスポイント１０〜２０が使用する無線通信方式は、ＷｉＦｉの無線通信方式であると説明したが、この発明の実施の形態においては、これに限らず、端末装置１〜９およびアクセスポイント１０〜２０が使用する無線通信方式は、ＷｉＭＡＸの無線通信方式であってもよく、一般的には、どのような無線通信方式であってもよい。
【０２１３】
更に、この発明の実施の形態においては、チャネル割当装置６０の機能は、ソフトウェアによって実現されてもよい。
【０２１４】
なお、この発明の実施の形態においては、しきい値αは、「第１のしきい値」を構成し、しきい値βは、「第２のしきい値」を構成する。
【０２１５】
また、この発明の実施の形態においては、ビーコンフレームは、「制御フレーム」を構成する。
【０２１６】
更に、この発明の実施の形態においては、隣接ＡＰリストは、「第１の隣接リスト」を構成し、接続可能ＡＰリストは、「第２の隣接リスト」を構成する。
【０２１７】
更に、この発明の実施の形態においては、アクセスポイント１０〜２０は、ネットワークに接続された「複数の通信装置」を構成し、端末装置１〜９は、「複数の端末装置」を構成する。
【０２１８】
更に、この発明の実施の形態においては、ドメイン決定装置６００は、「決定装置」を構成する。
【０２１９】
更に、この発明の実施の形態においては、各ＣＡドメインに含まれるアクセスポイントは、「制御対象の通信装置」を構成する。
【０２２０】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０２２１】
この発明は、タイミングおよび範囲が明確であり、かつ、安定したチャネル割当を行うチャネル割当装置に適用される。また、この発明は、タイミングおよび範囲が明確であり、かつ、安定したチャネル割当を行うチャネル割当装置を備えた通信ネットワークシステムに適用される。
【符号の説明】
【０２２２】
１〜９  端末装置、１０〜２０  アクセスポイント、２１〜２４  ルータ、４０  ネットワーク、５０  監視サーバ、６０  チャネル割当装置、６１〜６３  チャネル割当ユニット、１００  通信ネットワークシステム、１０１，１１１  アンテナ、１０２，１１２  無線インターフェース、１０４  アプリケーションモジュール、１０３，１１３，６２０  通信手段、１１４，６１０  有線インターフェース、６００  ドメイン決定装置、６１１  グラフ生成手段、６１２  判定手段、６１３  チャネル割当手段。
【図１】
2011049913.tif 000008
【図２】
2011049913.tif 000009
【図３】
2011049913.tif 000010
【図４】
2011049913.tif 000011
【図５】
2011049913.tif 000012
【図６】
2011049913.tif 000013
【図７】
2011049913.tif 000014
【図８】
2011049913.tif 000015
【図９】
2011049913.tif 000016
【図１０】
2011049913.tif 000017
【図１１】
2011049913.tif 000018
【図１２】
2011049913.tif 000019
【図１３】
2011049913.tif 000020
【図１４】
2011049913.tif 000021
【図１５】
2011049913.tif 000022
【図１６】
2011049913.tif 000023
【図１７】
2011049913.tif 000024