(57)【要約】      （修正有）【課題】無線ネットワークにおいて用いられる、ネットワーク干渉を評価する方法、動的チャネル割り当て方法および装置を提供する。【解決手段】受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算し、視覚的遅延時間に基づいて現在のチャネル割付けの下での総合的ネットワーク干渉を評価し、現在のチャネル割付けの下での評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分を所定の閾値と比較し、差分が所定の閾値より大きければ、新たなチャネル割付け手法に従ってベーシックサービスセットのチャネル割付けを変更する。【選択図】図３Ａ
2010119087.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにおいて用いられる動的チャネル割り当て方法であって、
受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算し、計算された視覚的遅延時間に基づいて現在のチャネル割付けの下での総合的ネットワーク干渉を評価するステップと、
前記各ベーシックサービスセットが頂点に位置し、各組のベーシックサービスセット間の接続ラインが、ベーシックサービスセットの各組の視覚的遅延時間の各組から取得した重みを有するように無向グラフを作成するステップと、
新たなチャネル割付け手法と当該新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るために無向グラフに着色するステップと、
現在のチャネル割付けの下での評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分を所定の閾値と比較するステップと、
前記差分が前記所定の閾値より大きければ、新たなチャネル割付け手法に従ってベーシックサービスセットのチャネル割付けを変更するステップと
を含むことを特徴とする動的チャネル割り当て方法。
【請求項２】
前記着色を半正定値計画法で行うことを特徴とする請求項１に記載の動的チャネル割り当て方法。
【請求項３】
前記重みは、アクセスポイントの組についての視覚的遅延時間の組の合計に等しいことを特徴とする請求項１に記載の動的チャネル割り当て方法。
【請求項４】
前記計算ステップが、
第１のベーシックサービスセットを形成する第１のノードのグループ、および他のベーシックサービスセットを形成する第２のノードのグループに関して、
前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するステップと、
前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計するステップとを含むことを特徴とする請求項１に記載の動的チャネル割り当て方法。
【請求項５】
前記計算ステップが、さらに、
トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算するステップと、
ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングするステップと、
トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算するステップとを含むことを特徴とする請求項４に記載の動的チャネル割り当て方法。
【請求項６】
前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含むことを特徴とする請求項５に記載の動的チャネル割り当て方法。
【請求項７】
現在のチャネル割付けの下での総合的ネットワーク干渉は、現在のチャネル割付けの下でのベーシックサービスセットの各組の間の全ての干渉の総計として評価され、
ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉が、０に等しいことを特徴とする請求項１に記載の動的チャネル割り当て方法。
【請求項８】
受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算するステップと、
現在のチャネル割付けに基づいて前記ベーシックサービスセットの各組の間の干渉を全て合計し、前記合計結果を、総合的ネットワーク干渉の評価として用いるステップとを有し、
１組の前記ベーシックサービスセット間の干渉は、前記ベーシックサービスセットの組について計算された視覚的遅延時間の組から推定されることを特徴とする総合的ネットワーク干渉評価方法。
【請求項９】
前記計算ステップが、
第１のベーシックサービスセットを形成する第１のノードのグループ、および他のベーシックサービスセットを形成する第２のノードのグループに関して、
前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するステップと、
前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計するステップとを含むことを特徴とする請求項８に記載の総合的ネットワーク干渉評価方法。
【請求項１０】
前記計算ステップが、さらに、
トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算するステップと、
ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングするステップと、
トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算するステップとを含むことを特徴とする請求項９に記載の総合的ネットワーク干渉評価方法。
【請求項１１】
前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含むことを特徴とする請求項１０に記載の総合的ネットワーク干渉評価方法。
【請求項１２】
前記第１のノードの前記標準伝送時間Timex(Normal)が、以下の式によって計算され、
【数１８】
2010119087.tif 000022
Ratex は、干渉のない第１の端末あるいはアクセスポイントの標準伝送レートを表わし、Rｘは、第１の端末あるいはアクセスポイントの正規化された受信トラヒック負荷を表わす
ことを特徴とする請求項１１に記載の総合的ネットワーク干渉評価方法。
【請求項１３】
前記第１の端末について、Ｒｘは、前記第１の端末の標準伝送レートRatexによって前記第１の端末の受信トラヒック負荷throughputｘ（受信）を正規化することにより、
Rｘ=
thoughputx(receiving)/ Ratex
として取得することを特徴とする請求項１２に記載の総合的ネットワーク干渉を評価する方法。
【請求項１４】
最初のアクセスについて、Ｒｘは、前記第１の端末のグループの正規化された送信トラヒック負荷ＬＷを合計することにより、
【数１９】
2010119087.tif 000023
として取得し、
Ｗは、前記第１の端末のグループを表し、ＬＷは、前記第１の端末の標準伝送レートRatewによって前記第１の端末の送信トラヒック負荷throughputW（送信）を正規化することにより、
Lw=
thoughputw(sending)/ Ratew. 
として取得することを特徴とする請求項１２に記載の総合的ネットワーク干渉を評価する方法。
【請求項１５】
前記第１の端末の低下伝送レートRatexyは、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、
Ratexy
=Map(RSSIxz-RSSIxy) 
としてマッピングされ、
ここで、RSSIxz-RSSIxyから得られた値は、ＳＩＮＲ−ＲＡＴＥテーブルのＳＩＮＲ欄に対応し、Ratexyの値はＳＩＮＲ−ＲＡＴＥテーブルのレート欄に対応し、RSSIxzは、第１のアクセスポイントと第１の端末の間の受信信号強度を表わし、また、RSSIxyは、１つの第２のノードと第１端末の間の受信信号強度を表わすことを特徴とする請求項１１に記載の総合的ネットワーク干渉を評価する方法。
【請求項１６】
前記第１の端末の低下伝送レートRatexyは、ＳＩＮＲ−ＲＡＴＥテーブルを用いることにより、
Ratexy
=Map(RSSIx-RSSIxy) 
としてマッピングされ、
ここで、RSSIx-RSSIxyから得られた値は、ＳＩＮＲ−ＲＡＴＥテーブルのＳＩＮＲ欄に対応し、Ratexyの値はＳＩＮＲ−ＲＡＴＥテーブルのレート欄に対応し、RSSIxは、第１のアクセスポイントの受信信号強度を表わし、また、RSSIxyは、１つの第２のノードと第１端末の間の受信信号強度を表わすことを特徴とする請求項１１に記載の総合的ネットワーク干渉を評価する方法。
【請求項１７】
前記第１のアクセスポイントの受信信号強度RSSIxは、正規化された送信トラヒック負荷ＬＷによって重みが加えられた第１の端末のグループと第１の端末のグループと前記第１のアクセスポイントの間の受信信号強度RSSIxＷを合計することにより、
【数２０】
2010119087.tif 000024
として取得することを特徴とする請求項１６に記載の総合的ネットワーク干渉を評価する方法。
【請求項１８】
前記第２のノードのグループからの干渉の下での前記第１のノードの遅延伝送時間Timex,Y(Interferece)は、
【数２１】
2010119087.tif 000025
として計算され、
Ｙは、第２のノードのグループを表わし、Ｌｙは、１つの第２のノードの正規化された送信トラヒック負荷を表わし、前記第２ノードの標準伝送レートRateｙによって第２のノードの送信トラヒック負荷throughputｙ（送信）を正規化することにより、
Ly=
thoughputy(sending)/ Ratey 
として取得されることを特徴とする請求項１１に記載の総合的ネットワーク干渉を評価する方法。
【請求項１９】
第２のノードのグループからの干渉の下での第１のノードの視覚的遅延時間ＶＤＴ（x,Y）は、
VDT(x,Y)=Timex,y(Interferece)-
Timex(Normal)
として計算されることを特徴とする請求項９に記載の総合的ネットワーク干渉を評価する方法。
【請求項２０】
ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉は、０に等しいことを特徴とする請求項８に記載の総合的ネットワーク干渉評価方法。
【請求項２１】
無線ネットワークにおいて用いられる動的チャネル割り当て装置であって、
受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算する視覚的遅延時間計算器と、
前記視覚的遅延時間計算器によって計算された視覚的遅延時間に基づいて現在のチャネル割付けの下での総合的ネットワーク干渉を評価する総合的ネットワーク干渉計算器と、
前記各ベーシックサービスセットが頂点に位置し、各組のベーシックサービスセット間の接続ラインが、ベーシックサービスセットの各組の視覚的遅延時間の各組から取得した重みを有するように無向グラフを作成するグラフ生成器と、
新たなチャネル割付け手法と当該新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るためにグラフ生成器によって生成された無向グラフに着色するグラフ着色ユニットと、
現在のチャネル割付けの下での評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分を所定の閾値と比較する比較器と、
前記差分が前記所定の閾値より大きければ、新たなチャネル割付け手法に従ってベーシックサービスセットのチャネル割付けを変更するコントローラと
を備えることを特徴とする動的チャネル割り当て装置。
【請求項２２】
前記グラフ着色ユニットは、半正定値計画法で前記着色を行うことを特徴とする請求項２１に記載の動的チャネル割り当て装置。
【請求項２３】
前記重みは、アクセスポイントの組についての視覚的遅延時間の組の合計に等しいことを特徴とする請求項２１に記載の動的チャネル割り当て装置。
【請求項２４】
第１のノードのグループが第１のベーシックサービスセットを形成し、第２のノードのグループが第２のベーシックサービスセットを形成し、
前記視覚的遅延時間計算器が、
前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するノード視覚的遅延時間計算器と、
前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計する加算器を含むことを特徴とする請求項２１に記載の動的チャネル割り当て装置。
【請求項２５】
前記視覚的遅延時間計算器が、さらに、
トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算する標準伝送時間計算器と、
ＳＩＮＲ−ＲＡＴＥテーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングする低下伝送レートマッピングユニットと、
トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算する遅延伝送時間計算器とを含むことを特徴とする請求項２４に記載の動的チャネル割り当て装置。
【請求項２６】
前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含むことを特徴とする請求項２５に記載の動的チャネル割り当て装置。
【請求項２７】
前記総合的ネットワーク干渉計算器は、現在のチャネル割付けの下での総合的ネットワーク干渉は、現在のチャネル割付けの下でのベーシックサービスセットの各組の間の全ての干渉の総計として評価し、
ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉が、０に等しいことを特徴とする請求項２１に記載の動的チャネル割り当て装置。
【請求項２８】
受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算する視覚的遅延時間計算器と、
現在のチャネル割付けに基づいて前記ベーシックサービスセットの各組の間の干渉を全て合計し、前記合計結果を、総合的ネットワーク干渉の評価として用いる総合的ネットワーク干渉評価器とを備え、
１組の前記ベーシックサービスセット間の干渉は、前記ベーシックサービスセットの組について計算された視覚的遅延時間の組から推定することを特徴とする総合的ネットワーク干渉評価装置。
【請求項２９】
第１のノードのグループが第１のベーシックサービスセットを形成し、第２のノードのグループが第２のベーシックサービスセットを形成し、
前記視覚的遅延時間計算器が、
前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するノード視覚的遅延時間計算器と、
前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計する加算器を含むことを特徴とする請求項２８に記載の総合的ネットワーク干渉評価装置。
【請求項３０】
前記視覚的遅延時間計算器が、さらに、
トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算する標準伝送時間計算器と、
ＳＩＮＲ−ＲＡＴＥテーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングする低下伝送レートマッピングユニットと、
トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算する遅延伝送時間計算器とを含むことを特徴とする請求項２９に記載の総合的ネットワーク干渉評価装置。
【請求項３１】
前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含むことを特徴とする請求項３０に記載の総合的ネットワーク干渉評価装置。
【請求項３２】
ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉は、０に等しいことを特徴とする請求項２８に記載の総合的ネットワーク干渉評価装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、８０２．１１のＷＬＡＮのような無線ネットワークに関し、特に、無線ネットワークにおいて利用されるネットワーク干渉評価方法、動的チャネル割り当て方法および装置に関する。
【背景技術】
【０００２】
８０２．１１ＷＬＡＮなどの無線ネットワークは、近年未曾有の普及率をもたらした。一般に、ネットワークはいくつかのセルを含んでいる。また、セルはそれぞれ１つの基地局（ＢＳ）とその基地局に関連付けた多くの移動局（ＳＴＡ）を含んでいる。ＳＴＡの通信は、ＢＳによって中継される。ここでは、問題点を詳細に説明するために一例として８０２．１１ＷＬＡＮを取り扱う。しかし、本発明が８０２．１１ＷＬＡＮに限定されることを意味するものでないことは言うまでもない。８０２．１１ＷＬＡＮにおいて、セルはＢＳＳ（ベーシックサービスセット：Basic Service Set）と呼ばれ、ＢＳはアクセスポイント（ＡＰ：Access Point）と呼ばれる。また、チャネルは、ＷＬＡＮに割り当てられた無線周波数スペクトルを表す。８０２．１１仕様書は、使用するチャネルの固定数を定義している。例えば、８０２．１１ｂ（２．４１２−２．４６２ＧＨｚ）は１１のチャンネルを規定する。
【０００３】
これらのネットワークにおける重要な問題は干渉である。
無線媒体のブロードキャスト性のために、送信機と受信機組の１組からの送信は、他の組みの送信に対して影響を与える。ミクロの観点から、干渉量は信号強度と関連する。
パケットがノードｖからノードｕへ送られる場合、そのパケットが確実に受信されるかどうかは、受信機ｕのインターフェースと送信機ｖの伝送レートに関するＳＩＮＲ（Signal to Interference-Noise Ratio：信号対干渉雑音比）に依存する。
【０００４】
【数１】
2010119087.tif 000003
式（１）において、Nu[CH(u)]はチャネルCH(u)の暗騒音である。ａは異なるＢＳＳ内の他の送信機であり、Pv と Paは送信機のネットワークインターフェイスからの最初のパワーレベルである。
Gv,u と Ga,uは伝播減衰定数であり、経路環境と関係づけられ、数学モデルで計算することは非常に困難である。
ＳＩＮＲがより低くなると、送信ノードはパケット破損を防ぐためにより低いＰＨＹ（物理的）レートにする必要がある。
８０２．１１ＷＬＡＮについて、ＰＨＹレートとＳＩＮＲの関係はテーブル１において示される。
【０００５】
【表１】
2010119087.tif 000004
【０００６】
マクロの観点から、より多いトラフィックが信号干渉のより長い継続時間を引き起こすので、干渉は干渉源のトラフィックに比例する。
無線ネットワーク最適化において、我々は、異なるネットワーク・パラメータの下で干渉を予報する必要がある。
例えば、ネットワークの最良のチャネル割当てを見つけ出したければ、我々は異なるチャネル割付けの下で干渉度を予報し、最小の大域的な干渉を持った一つを選択する必要がある。
干渉予測の正確さは直接最適化性能を影響を与える。
同様の要求は、電力制御とネットワーク診断などのような他の最適化に必要である。同様の要求は、電力制御および網状の分析などのような他の最適化に必要である。
【０００７】
干渉の現在の推定は非常に不正確である。
非特許文献１などのような大部分の既存の研究は、干渉範囲が通信距離の２倍である、電波の伝播の簡単な抽象モデルに基づいて干渉を規定する。受信機が干渉源の干渉範囲の中にある場合、それらの間の干渉は「１」である。干渉範囲内でなければ、干渉は「０」に設定される。
【０００８】
特許文献１は、アクセスポイントについて自動チャネル決定の方法および自動チャネル割当システムを提案している。特許文献１の解決法においては、アクセスポイント間の信号強度が干渉量として利用され、非特許文献１よりさらに高性能である。
【０００９】
特許文献２は、干渉信号強度に加えて、干渉源のトラヒック負荷を考慮に入れている。特許文献２の解決法においては、ＡＰは、周期的にチャネルｊへ切り替えて、Ｔミリセカンドの間チャネルｊを確認する。それから、ＡＰは、Ｔ＿負荷とＴ＿干渉を判定し、チャネルｊにおいてモニターした負荷と干渉エネルギーである、ＣＳ（ｊ）およびＣＩ（ｊ）を計算する。最後に、ＡＰは、最小の（ＣＳ（ｊ）＋ＣＩ（ｊ））を有する最適なチャネルｊを判定する。
【００１０】
非特許文献２は、局認識干渉メトリックを提案する。
【００１１】
【数２】
2010119087.tif 000005
ここで、Numap1は、ＡＰｉのＢＳＳにおけるＳＴＡ数であり、Numap1(apj)は、ＡＰｉに関連付けられているが、ＡＰｊからビーコンを確認することができるＳＴＡの数である。また、Numap1は、ＡＰｊのＢＳＳにおけるＳＴＡ数であり、Numap1(apj)は、ＡＰｊに関連付けられているが、ＡＰｉからビーコンを確認することができるＳＴＡの数である。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００６−０５４８４９号公報
【特許文献２】米国特許公報７１１０３７４Ｂ２
【非特許文献】
【００１３】
【非特許文献１】コリン・マクダーミド、ブルース・リード等による“加重着色とチャネル割当て”、２０００年（ColinMcDiarmid and Bruce Reed, “Channel Assignment And Weighted Coloring”, 2000.）
【非特許文献２】アルネッシュ・ミッシュラ、スーマン・バネルジー、ウィリアム・アルボー等による“ワイヤレスローカルエリアネットワークのための加重着色ベースのチャネル割当て”、モバイルコンピューターコミュニケーションレビュー、第３号、２００５年（Arunesh Mishra, Suman Banerjee, and William Arbaugh, “WeightedColoring Based Channel Assignment For WLANs”, Mobile Computer CommunicationsReview (MC2R), vol. 9, no. 3, 2005.）
【非特許文献３】アラン・フリーズ、マーク・ジェラム等による“マックスＫカットとマックス二分法のための改良近似アルゴリズム”、アルゴリズミカ、１８、１９９７年（A. Frieze and M. Jerrum. Improved approximation algorithms for MAX k-CUTand MAX BISECTION. Algoritmica, 18, 1997.）
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明の目的は、無線周波数特性を捕捉し、異なるセッティングの元で動作する時にどのように動作するかを正確に予測し、最適なシステム総合的性能を達成する種々のＡＰにチャネルリソースを動的に割り当てるために、無線ネットワーク上のリアルタイム測定を利用することにある。
【課題を解決するための手段】
【００１５】
結果として、既存の方法は、単に以下の２つの要因を考慮する。干渉源と受信機の間の信号のパワー（以下、「干渉信号」と称する）と、干渉源のトラフィック量（以下、「干渉トラフィック」と称する）である。
しかしながら、干渉の性能に直接影響を与える他のファクターは、既存の方法においては十分に検討されていない。それらは、
１．送信機と受信機の間の信号パワー（以下、「有効な信号」と称する）
２．受信機のトラフィック量。
３．ＳＩＮＲ−ＲＡＴＥ（レート）テーブル
【００１６】
これらの情報がないと、干渉予測はいくつかの状況において正確さを損なう。
例えば
１．  ２つの受信機ＡおよびＢについて、それらの干渉信号の強さが同じであるが、受信機Ａは受信機Ｂよりその送信機に接近している場合。この場合、受信機Ａのパケット損失は、受信機Ｂよりはるかに少ない。それは、受信機Ａが受ける干渉度が受信機Ｂより小さいことを意味している。しかしながら、有効な信号に相当する情報を有しないので、既存の方法ではこのような状況を把握できない。
２．  受信機Ｂが強い干渉信号を受けていても、受信機Ｂがその時に通信するトラフィックを有しなければ、受信機Ｂに実際の干渉影響はない。干渉がパケット伝送衝突によって引き起こされるからである。
３．  受信機Ｂについて干渉を軽減したい場合、送信機の送信パワーをどれだけ増大しなければならないか。
【００１７】
本発明は、より正確にネットワークパフォーマンスを予測するために干渉度予測メトリックを提案する。そのメトリックは視覚的遅延時間であり、干渉による視覚的な増加伝送時間を意味する。それは、１つの式に以下の４つの重要な干渉関連要因を適切に組み込む。
１．送信機と受信機の間の信号強度。
２．干渉源と受信機の間の信号強度。
３．各ノードのトラフィック要求。
４．ＳＩＮＲ−ＲＡＴＥ（レート）テーブル。
【００１８】
本発明の第１の形態によれば、無線ネットワークにおいて用いられる動的チャネル割り当て方法であって、受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算し、計算された視覚的遅延時間に基づいて現在のチャネル割付けの下での総合的ネットワーク干渉を評価するステップと、前記各ベーシックサービスセットが頂点に位置し、各組のベーシックサービスセット間の接続ラインが、ベーシックサービスセットの各組の視覚的遅延時間の各組から取得した重みを有するように無向グラフを作成するステップと、新たなチャネル割付け手法と当該新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るために無向グラフに着色するステップと、現在のチャネル割付けの下での評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分を所定の閾値と比較するステップと、前記差分が前記所定の閾値より大きければ、新たなチャネル割付け手法に従ってベーシックサービスセットのチャネル割付けを変更するステップとを含む動的チャネル割り当て方法を提供する。
【００１９】
好ましくは、着色を半正定値計画法で行う。
【００２０】
好ましくは、前記重みは、アクセスポイントの組についての視覚的遅延時間の組の合計に等しい。
【００２１】
好ましくは、前記計算ステップが、第１のベーシックサービスセットを形成する第１のノードのグループ、および他のベーシックサービスセットを形成する第２のノードのグループに関して、前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するステップと、前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計するステップとを含む。
【００２２】
好ましくは、前記計算ステップが、さらに、トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算するステップと、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングするステップと、トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算するステップとを含む。
【００２３】
好ましくは、前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含む。
【００２４】
好ましくは、現在のチャネル割付けの下での総合的ネットワーク干渉は、現在のチャネル割付けの下でのベーシックサービスセットの各組の間の全ての干渉の総計として評価され、ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉が、０に等しい。
【００２５】
本発明の第２の形態によれば、受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算するステップと、現在のチャネル割付けに基づいて前記ベーシックサービスセットの各組の間の干渉を全て合計し、前記合計結果を、総合的ネットワーク干渉の評価として用いるステップとを有し、１組の前記ベーシックサービスセット間の干渉は、前記ベーシックサービスセットの組について計算された視覚的遅延時間の組から推定されることを特徴とする総合的ネットワーク干渉評価方法を提供する。
【００２６】
好ましくは、前記計算ステップが、第１のベーシックサービスセットを形成する第１のノードのグループ、および他のベーシックサービスセットを形成する第２のノードのグループに関して、前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するステップと、前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計するステップとを含む。
【００２７】
好ましくは、前記計算ステップが、さらに、トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算するステップと、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングするステップと、トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算するステップとを含む。
【００２８】
好ましくは、前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含む。
【００２９】
好ましくは、前記第１のノードの前記標準伝送時間Timex(Normal)が、以下の式によって計算され、
【００３０】
【数３】
2010119087.tif 000006
Ratex は、干渉のない第１の端末あるいはアクセスポイントの標準伝送レートを表わし、Rｘは、第１の端末あるいはアクセスポイントの正規化された受信トラヒック負荷を表わす。
【００３１】
好ましくは、前記第１の端末について、Ｒｘは、前記第１の端末の標準伝送レートRatexによって前記第１の端末の受信トラヒック負荷throughputｘ（受信）を正規化することにより、
Rｘ=
thoughputx(receiving)/ Ratex
として取得する。
【００３２】
好ましくは、最初のアクセスについて、Ｒｘは、前記第１の端末のグループの正規化された送信トラヒック負荷ＬＷを合計することにより、
【００３３】
【数４】
2010119087.tif 000007
として取得し、
Ｗは、前記第１の端末のグループを表し、ＬＷは、前記第１の端末の標準伝送レートRatexによって前記第１の端末の送信トラヒック負荷throughputW（送信）を正規化することにより、
Lw=
thoughputw(sending)/ Ratew. 
として取得する。
【００３４】
好ましくは、前記第１の端末の低下伝送レートRatexyは、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、
Ratexy
=Map(RSSIxz-RSSIxy) 
としてマッピングされ、
ここで、RSSIxz-RSSIxyから得られた値は、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルのＳＩＮＲ欄に対応し、Ratexyの値はＳＩＮＲ−ＲＡＴＥ（レート）テーブルのレート欄に対応し、RSSIxzは、第１のアクセスポイントと第１の端末の間の受信信号強度を表わし、また、RSSIxyは、１つの第２のノードと第１端末の間の受信信号強度を表わす。
【００３５】
好ましくは、前記第１の端末の低下伝送レートRatexyは、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルを用いることにより、
Ratexy
=Map(RSSIx-RSSIxy) 
としてマッピングされ、
ここで、RSSIx-RSSIxyから得られた値は、ＳＩＮＲ−ＲＡＴＥ（レート）テーブルのＳＩＮＲ欄に対応し、Ratexyの値はＳＩＮＲ−ＲＡＴＥ（レート）テーブルのレート欄に対応し、RSSIxは、第１のアクセスポイントの受信信号強度を表わし、また、RSSIxyは、１つの第２のノードと第１端末の間の受信信号強度を表わす。
【００３６】
好ましくは、前記第１のアクセスポイントの受信信号強度RSSIxは、正規化された送信トラヒック負荷ＬＷによって重みが加えられた第１の端末のグループと第１の端末のグループと前記第１のアクセスポイントの間の受信信号強度RSSIxＷを合計することにより、
【００３７】
【数５】
2010119087.tif 000008
として取得する。
【００３８】
好ましくは、前記第２のノードのグループからの干渉の下での前記第１のノードの遅延伝送時間Timex,Y(Interferece)は、
【００３９】
【数６】
2010119087.tif 000009
として計算され、
Ｙは、第２のノードのグループを表わし、Ｌｙは、１つの第２のノードの正規化された送信トラヒック負荷を表わし、前記第２ノードの標準伝送レートRateｙによって第２のノードの送信トラヒック負荷throughputｙ（送信）を正規化することにより、
Ly=
thoughputy(sending)/ Ratey 
として取得される。
【００４０】
好ましくは、第２のノードのグループからの干渉の下での第１のノードの視覚的遅延時間ＶＤＴ（x,Y）は、
VDT(x,Y)=Timex,y(Interferece)-
Timex(Normal)
として計算される。
【００４１】
好ましくは、ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉は、０に等しい。
【００４２】
本発明の第３の形態によれば、無線ネットワークにおいて用いられる動的チャネル割り当て装置であって、受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算する視覚的遅延時間計算器と、前記視覚的遅延時間計算器によって計算された視覚的遅延時間に基づいて現在のチャネル割付けの下での総合的ネットワーク干渉を評価する総合的ネットワーク干渉計算器と、前記各ベーシックサービスセットが頂点に位置し、各組のベーシックサービスセット間の接続ラインが、ベーシックサービスセットの各組の視覚的遅延時間の各組から取得した重みを有するように無向グラフを作成するグラフ生成器と、新たなチャネル割付け手法と当該新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るためにグラフ生成器によって生成された無向グラフに着色するグラフ着色ユニットと、現在のチャネル割付けの下での評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分を所定の閾値と比較する比較器と、前記差分が前記所定の閾値より大きければ、新たなチャネル割付け手法に従ってベーシックサービスセットのチャネル割付けを変更するコントローラとを備えることを特徴とする動的チャネル割り当て装置を提供する。
【００４３】
好ましくは、前記グラフ着色ユニットは、半正定値計画法で前記着色を行う。
【００４４】
好ましくは、前記重みは、アクセスポイントの組についての視覚的遅延時間の組の合計に等しい。
【００４５】
好ましくは、第１のノードのグループが第１のベーシックサービスセットを形成し、第２のノードのグループが第２のベーシックサービスセットを形成し、前記視覚的遅延時間計算器が、前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するノード視覚的遅延時間計算器と、前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計する加算器を含む。
【００４６】
好ましくは、前記視覚的遅延時間計算器が、さらに、トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算する標準伝送時間計算器と、ＳＩＮＲ−ＲＡＴＥテーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングする低下伝送レートマッピングユニットと、トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算する遅延伝送時間計算器とを含む。
【００４７】
好ましくは、前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含。
【００４８】
好ましくは、前記総合的ネットワーク干渉計算器は、現在のチャネル割付けの下での総合的ネットワーク干渉は、現在のチャネル割付けの下でのベーシックサービスセットの各組の間の全ての干渉の総計として評価し、ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉が、０に等しい。
【００４９】
本発明の第４の形態によれば、受信した信号強度、トラフィック情報およびレート情報に基づいてベーシックサービスセットの各組について視覚的遅延時間の各組を計算する視覚的遅延時間計算器と、現在のチャネル割付けに基づいて前記ベーシックサービスセットの各組の間の干渉を全て合計し、前記合計結果を、総合的ネットワーク干渉の評価として用いる総合的ネットワーク干渉評価器とを備え、１組の前記ベーシックサービスセット間の干渉は、前記ベーシックサービスセットの組について計算された視覚的遅延時間の組から推定することを特徴とする総合的ネットワーク干渉評価装置を提供する。
【００５０】
好ましくは、第１のノードのグループが第１のベーシックサービスセットを形成し、第２のノードのグループが第２のベーシックサービスセットを形成し、前記視覚的遅延時間計算器が、前記第１のノードの計算した標準伝送時間および前記第１のノードの計算した遅延伝送時間を用いることにより、前記第２のノードのグループからの干渉の下での各前記第１のノードの視覚的遅延時間を計算するノード視覚的遅延時間計算器と、前記第２のベーシックサービスセットからの干渉の下での前記第１のベーシックサービスセットの視覚的遅延時間を取得するために、前記第１のノードのグループの視覚的遅延時間を全て合計する加算器を含む。
【００５１】
好ましくは、前記視覚的遅延時間計算器が、さらに、トラフィック情報とレート情報を用いることにより各第１のノードの標準伝送時間を計算する標準伝送時間計算器と、ＳＩＮＲ−ＲＡＴＥテーブルを用いることにより、かつ受信した信号強度指標に基づいて、第１のノードの低下伝送レートをマッピングする低下伝送レートマッピングユニットと、トラフィック情報、レート情報および第１のノードのマッピングした低下伝送レートを用いることにより、第２のノードのグループからの干渉の下での第１のノードの遅延伝送時間を計算する遅延伝送時間計算器とを含む。
【００５２】
好ましくは、前記第１のノードのグループが、第１のアクセスポイント、および第１のアクセスポイントによって無線ネットワークにアクセスする第１の端末のグループを含み、前記第２のノードのグループが、他のアクセスポイント、および第２のアクセスポイントによって無線ネットワークにアクセスする第２の端末のグループを含む。
【００５３】
好ましくは、ベーシックサービスセットの組が現在のチャネル割付けの下で同一のチャネルを利用していれば、１組のベーシックサービスセット間の干渉は、１組のベーシックサービスセットについて計算された１組の視覚的遅延時間の合計と等しく、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、当該組のベーシックサービスセットの間の干渉は、０に等しい。
【００５４】
概略として、本発明は以下のように機能する。
１．ＳＩＮＲ−ＲＡＴＥテーブルを既知の知識として用意する。このテーブルは、ＷｉＦｉ（Ｗｉｍａｘなど）などのような無線ネットワークのタイプに依存する。例えば、実装例においてＷｉＦｉネットワークを用い、テーブルは上記のテーブル１として示される。
２．無線ネットワークにおけるノードはそれぞれ測定処理を周期的に実行する。この処理において、ノードは以下の情報を測定する。
そのノードに関連付けられているアクセスポイント（あるいは、他の種類の無線ネットワークにおける基地局）からの信号強度。
その隣接のセルにおける他のノードからの信号強度。
その隣接のセルにおける他のノードのトラフィック量。
そのノード自身のトラフィック量。
３．情報と共に、ノードは、それが受けている干渉度（視覚的な遅延時間）を計算する。
４．各ノードの情報はアクセスポイント（あるいは基地局）によって収集され、アクセスポイント（あるいは基地局）はセルが受けている干渉度を計算することができる。
【発明の効果】
【００５５】
本発明は以下に述べるような効果を提供する。
１．干渉度予測は、無線信号の伝播の性質に関する仮定を単純化しないように、実際の測定によって実行される。
２．様々なセッティングの元で動作するネットワークパフォーマンスをより正確に把握することが可能となる。
３．本発明はＭＡＣ層での変更を必要とせず、簡単なソフトウェア改良によって実現することが可能である。この提案は、８０２．１１のような既存のネットワーク規格と上位互換性をもつ。
【図面の簡単な説明】
【００５６】
本発明の前述した目的、特徴及び効果と他の目的、特徴及び効果は、添附の図面を参照した本発明の限定されない実施の形態に関する以下の説明からより明らかになるであろう。
【図１】本発明を適用した簡単な実施例を示す図である。
【図２】複数の干渉者が存在する他の実施例を示す図である。
【図３Ａ】本発明による動的チャネル割り当て方法を説明するフローチャートである。
【図３Ｂ】図３ＡにおけるＶＤＴ計算ステップの詳細を示す図である。
【図４Ａ】本発明による動的チャネル割り当て装置の構成例を示すブロック図である。
【図４Ｂ】図４ＡにおけるＶＤＴ計算機の詳細を示すブロック図である。
【発明を実施するための最良の形態】
【００５７】
以下、本発明について図面を参照して説明する。以下の説明において、ある特定の実施の形態は説明のみの目的で利用される。それは、あくまで一例であり、本発明の制限として理解されてはならない。本発明の理解を不鮮明にするかもしれないので、従来の構成あるいは構造については省略する。
【００５８】
本発明を適用した簡単な事例を図１に示す。
ＡＰ１のセルにおいて、ＡＰ１は、ノードＡに対してトラフィックを送信している。ＡＰ２のセルにおいて、同時に、ノードＢがＡＰ２に対してトラフィックを送信している。２つのセルが同じチャンネルを利用する場合、ノードＢは受信機（ノードＡ）に対して干渉源となる。
【００５９】
ノードＢからノードＡに対する干渉度を評価するために、ノードＡが収集する必要のあるパラメータを、テーブル２にリストされている。
【００６０】
【表２】
2010119087.tif 000010
【００６１】
テーブル２において、ＲＳＳＩは受信信号強度（全ての汎用無線カードによって伝えられる）を表わしている。このＲＳＳＩは、信号強度を推定するために使用される。
例えば、Ａｔｈｅｒｏｓ社製カードにおいて、ＲＳＳＩは、
【００６２】
【数７】
2010119087.tif 000011
と報告されている。
ここで、Ｓは入力信号の強さを表わし、Ｉは同じチャンネルにおける干渉エネルギーを表わし、また、ｎは「暗騒音（noise floor）」（一般的に、約-95dbm）を表わす。
【００６３】
干渉度を示すために、干渉メトリックの選択が重要なポイントである。その干渉メトリックは、複数のパラメータをどのように一緒に取り入れるかを決定する。例えば、既存の方法においては、干渉信号強度あるいは干渉信号強度と干渉トラフィックの合計が、干渉メトリックとしての利用される。本発明においては、新たなメトリックとして、視覚的遅延時間（Visual Delayed Time：ＶＤＴ）を提案する。この新たなメトリックは、以下の事実に基づいて提案されている。
送信機は、パケット・ロスを防ぐためにその伝送レートを下げることが可能であり、また、コストとしての、同じパケットに対する伝送時間は、干渉のない場合より長いはずである。
従って、以下のように、余分な時間コストは、干渉度を評価するために利用することができる。
VDT(x,Y)=Timex,y(Interferece)- Timex(Normal)          (2)
【００６４】
式（２）において、Timex(Normal)は、干渉のないノードｘの正常な伝送時間である。また、Timex,y(Interferece)は、ノードｙからの干渉を受けて遅れたノードｘの伝送時間である。それらは両方ともテーブル２においてリストされたパラメータで計算される。
【００６５】
１つの受信機と１つの干渉源（図１）が存在する簡単なケースの場合、それらの転送時間は、
【００６６】
【数８】
2010119087.tif 000012
【００６７】
【数９】
2010119087.tif 000013
として表される。
ここで、Ratexyはノードｙの干渉を受けて低下したノードｘの伝送レートであり、以下のように計算される。
Ratexy
=Map(RSSIxz-RSSIxy)             (5)
ここで、関数Map(.)は、ＳＩＮＲ−ＲＡＴＥ（レート）テーブル（例えば、８０２．１１のネットワークに関するのテーブル１）に従うＳＩＮＲから伝送レートに対するマッピング関数である。ノードｚはノードｘの送信機である。また、ノードｙはノードｘの干渉源である。
RSSIxz-RSSIxyから得られた値は、テーブル１のＳＩＮＲの欄に対応し、Ratexyの値は、テーブル１のＰＨＹレートの欄に対応する。
【００６８】
以下に、VDT(A, B)をどのように計算するかに関する例について、図１を参照して説明する。
ノードＡが受信機、また、ノードＢが干渉源であり、RateA＝２４Ｍｂｐｓ、RateB＝３６Ｍｂｐｓ、throughputA（受信）＝１２Ｍｂｐｓ、throughputB（送信）＝  ９  Ｍｂｐｓ、RSSIAAP1＝２４ｄｂｍ、RSSIAB＝１０ｄｂｍであると仮定する。従って、テーブル２内のそれらの定義によれば、LB
= 0.25、RA = 0.5である。
式（３）に従って、
【００６９】
【数１０】
2010119087.tif 000014
を求める。
式（５）およびテーブル１によれば、１４ｄｂｍが６．９９ｄｂｍより大きく、２３ｄｂｍより小さいので、RateAB
=Map(14dbm)=11Mbpsとなる。従って、式（４）を参照すると、
【００７０】
【数１１】
2010119087.tif 000015
となる。
結果として、
VDT(x,y)=24.10ns-20.83ns=3.27ns
が得られる。
図２に示すように複数の干渉源が存在する場合に関しては、Timex(Normal)が、式（３）で今までどおり計算される。
Timex,y(Interferece)は、以下の式（６）で計算される。
Yは、干渉源(Y = {B,C, ..N})の集合とする。
【００７１】
【数１２】
2010119087.tif 000016
ここで、Ratexyは、式（５）によって得られる。
【００７２】
従って、複数の干渉源がある場合には、式（２）で示される視覚的遅延時間（ＶＤＴ）は、次のように書き換えられる。
VDT(x,Y)=Timex,y(Interferece)- Timex(Normal)          (2’)
【００７３】
ＡＰが受信機である場合、ＡＰの受信トラフィックが複数の送信機から到来するので、式（５）におけるＡＰの良好な信号は、局のそれとは異なる。
ＸがＡＰに関連付けられた全ての局に対する集合であると想定すると、以下の式が成り立つ。
【００７４】
【数１３】
2010119087.tif 000017
本発明において、ＡＰの良好な信号は以下の式（７）によって推定される。
【００７５】
【数１４】
2010119087.tif 000018
【００７６】
全てのＢＳＳ  Ｘの干渉を計算したい場合、それは、単にＢＳＳにおける各ノードのＶＤＴの合計に等しくなる。
すなわち、
【００７７】
【数１５】
2010119087.tif 000019
となる。
ＶＤＴ（ｘ、Ｙ）は、式（２）〜（６）及び式（２’）で計算することができる。
【００７８】
ここで、ＷＬＡＮにおける動的チャネル割当問題を解決するためにＶＤＴを利用する方法を説明する。
無線通信ネットワークを、ネットワークにおいてｎ個のＢＳＳを表わす頂点の集合V={1,2,L,n}を有する一般的な無向グラフとしてモデル化する。ネットワークにおける利用可能なＫ個の直交チャネルがあり、k={1,2,L,K}をセットする。
チャネル割当ては総合的ネットワーク干渉
【００７９】
【数１６】
2010119087.tif 000020
を最小限にする関数F:V→ｋを計算するための問題として表わすことができる。
ここで、ＢＳＳ  ＸとＢＳＳ  Ｙの間の干渉I(X,Y)は、次のように定義される。
【００８０】
【数１７】
2010119087.tif 000021
ここで、F(X)=F(Y)は、ＢＳＳ  ＸとＢＳＳ  Ｙが１つでかつ同じチャネルを利用していることを意味するのに対し、F(X)≠F(Y)は、ＢＳＳ  Ｙが異なるチャネルを利用していることを意味する。
【００８１】
その問題の最適化はＮＰ困難（NP-hard）として知られている。
本発明においては、この問題を解決するために集中化された方法を利用する。
小規模(n≦12 and K≦3)のケースでは、最良の割り当てを実現するために網羅的探索（brute-force
search）を利用することが可能である。大規模のケースでは、近似の結果を得るために半正定値計画法（semi-definite programming
technology：ＳＤＰ）を利用する。
ＳＤＰは、最小ｋ−分割（ＭｋＰ）問題（Minimum
k-Partition (MkP) problem）として一般に知られている。それはチャネル割当てと等価な問題として見ることが可能である。
ＭｋＰ手法の詳細については、非特許文献３を参照することが可能である。ここでは、本発明の特徴の不要に不明瞭にする説明を回避するために、その詳細については省略する。
【００８２】
図３Ａは、本発明の動的チャネル割り当て方法のフローチャートを示す。
【００８３】
上述した原理の説明に基づいて、本発明による動的チャネル割り当て方法について図３Ａを参照して説明する。
ステップＳ３０５において、ＲＳＳＩ、トラフィック情報および割合情報がＡＰと端末から取得される。
ステップＳ３１０において、ベーシックサービスセット（ＡＰ）の各組について視覚的遅延時間の各組が、ＲＳＳＩ、トラフィック情報およびレート情報について基づいて計算される。
特に、視覚的遅延時間が、式（２）〜（８）と（２’）及びＳＩＮＲ−ＲＡＴＥ（レート）テーブル（例えば、テーブル１）を参照することにより計算される。
ステップＳ３１２において、現在のチャネル割付けの下での総合的ネットワーク干渉が、ステップＳ３１０において得られた視覚的遅延時間に基づいて評価される。
特に、現在のチャネル割付けの下での総合的ネットワーク干渉は、現在のチャネル割付けの下でのベーシックサービスセットの各組みの間の全ての干渉の総計として評価することが可能である、
ここで、ベーシックサービスセットの一組の間の干渉は、ベーシックサービスセットの組が現在のチャネル割付けの下で全く同一のチャネルを利用していれば、ステップＳ３１０において得られたベーシックサービスセットの組についての視覚的遅延時間の組の合計と等しくなる。これに対して、ベーシックサービスセットの組が現在のチャネル割付けの下で異なるチャネルを利用していれば、ベーシックサービスセットの組の間の干渉は０に等しくなる。
ステップＳ３１５において、ベーシックサービスセット（ＡＰ）がそれぞれ頂点に位置するように、無向グラフが作成される。また、ベーシックサービスセット（ＡＰ）の各組の間の接続ラインは、それぞれ、ステップＳ３１０において取得されたベーシックサービスセット（ＡＰ）の各組についての視覚的遅延時間の組の合計と等しい重みを有するように作成される。
ステップＳ３２０において、新たなチャネル割付け手法およびこの新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るために、特に半正定値計画（ＳＤＰ）法で、無向グラフに着色する。
ステップＳ３２５において、ステップＳ３１２およびＳ３２０においてそれぞれ取得された、評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分（干渉改善量）を、所定の閾値と比較する。
差分が、総合的システム性能が非常に改善されることを意味する閾値より大きければ（ステップＳ３２５において「ＹＥＳ」）、ステップＳ３３０において、ベーシックサービスセット（ＡＰ）のチャネル割付けが、新たなチャネル割付け手法に従って変更される。
逆に、差分が閾値（ステップＳ３２５において「ＮＯ」）ほど大きくなければ、総合的システム性能が非常に改善されないことを意味しており、ベーシックサービスセット（ＡＰ）のチャネル割付けをそのまま維持する。
本発明の動的チャネル割り当て方法は、システムをモニターし続ける（定期的にあるいは所定のトリガ機構で）。
【００８４】
図３Ｂは、ＶＤＴ計算ステップＳ３１０の詳細を示している。
ステップＳ３１００において、ノードｘ（１つのＢＳＳ集合Ｘに属する）の標準伝送時間Timex(Normal)は、トラフィック情報とレート情報を使用することにより式（３）に従って計算される。
ステップＳ３１０２において、ノードｘの低下伝送レートRatexyが、ＳＩＮＲ−ＲＡＴＥ（レート）テーブル（例えば、テーブル１）の利用することにより、かつ各ノードとノードｘのＲＳＳＩ情報に基づいてマッピングされる。
ステップＳ３１０４において、干渉源集合Ｙ（他のＢＳＳ）からの干渉の下におけるノードｘの遅延伝送時間Timex,y(Interferece)が、トラフィック情報、レート情報、およびステップＳ３１０２で得られたノードｘのマッピングされた低下伝送レートRatexyを利用することにより、式（６）に従って計算される。
ステップＳ３１０６において、干渉源集合Ｙからの干渉の下におけるノードｘの視覚的遅延時間VDT(x,Y)が、ステップＳ３１００およびＳ３１０４においてそれぞれ取得されたノードｘの計算された標準伝送時間Timex(Normal)およびノードｘの計算された遅延伝送時間Timex,y(Interferece)を利用することにより、式（２’）に従って計算される。
ステップＳ３１０８において、集合Ｘに属する全てのノードｘについて視覚的遅延時間VDT(x,Y)が取得されたかどうか、つまり、集合Ｘに属する全てのノードｘが処理されたかどうかを判定する。
そうであれば（ステップＳ３１０８で「ＹＥＳ」）、ステップＳ３１１０に進み、他のＢＳＳ集合Ｙからの干渉の下における１つのＢＳＳの視覚的遅延時間VDTXYが、式（８）に従ってセットＸに属する全てのノードｘについての視覚的遅延時間VDT(x,Y)の合計として計算される。
集合Ｘに属する全てのノードｘについての視覚的遅延時間VDTXYが、まだ取得されていなければ（ステップＳ３１０８において「ＮＯ」）、集合Ｘに属する他のノードｘが選択され、処理はステップＳ３１００とＳ３１０２まで戻る。
【００８５】
同様に、他のＢＳＳ集合Ｙに属する各ノードｙと干渉源集合Ｘについて、上記のステップＳ３１００〜Ｓ３１１０を、１つのＢＳＳ集合Ｘからの干渉の下での他のＢＳＳ集合Ｙの視覚的遅延伝送時間VDTYXを取得するために実行する。
【００８６】
その結果、各組のＢＳＳセットＸおよびＹについて、１組の視覚的遅延時間VDTXYおよびVDTYXが取得される。
【００８７】
図４Ａは、本発明による動的チャネル割り当て装置の概略構成を示すブロック図である。
【００８８】
図４Ａに示すように、本発明の動的チャネル割り当て装置４００は、ＡＰと端末からＲＳＳＩ、トラフィック情報およびレート情報を検出するための検知器４１０と、検知器４１０によって検出されたＲＳＳＩ、トラフィック情報およびレート情報に基づいて各組のベーシックサービスセット（ＡＰ）について各組の視覚的遅延時間を計算する視覚的遅延時間（ＶＤＴ）計算器４２０（視覚的遅延時間は、式（２）〜（８）と式（２’）及びＳＩＮＲ−ＲＡＴＥ（レート）テーブル（例えば、テーブル１）を参照して計算される。）と、ＶＤＴ計算器４２０によって計算された視覚的遅延時間について基づいた現在のチャネル割付けの下で総合的ネットワーク干渉を評価するための総合的ネットワーク干渉計算器４２５（現在のチャネル割付けの下で総合的ネットワーク干渉は、現在のチャネル割付けの下でそれぞれの組のベーシックサービスセット間のすべての干渉の総計として評価することが可能であり、そこでは、１組のベーシックサービスセット間の干渉は、組のベーシックサービスセットが現在のチャネル割付けの下で全く同一のチャネルを利用していれば、ＶＤＴ計算器４２０によって計算された組のベーシックサービスセットについて組の視覚的遅延時間の合計と等しい、組のベーシックサービスセットが現在のチャネル割付けの下で異なるチャネルを利用していれば、１組のベーシックサービスセット間の干渉は０に等しい）と、ベーシックサービスセット（ＡＰ）がそれぞれ頂点に位置し、各組のベーシックサービスセット（ＡＰ）間の接続ラインはそれぞれ、ＶＤＴ計算器４２０によって計算されたこの組のベーシックサービスセット（ＡＰ）について組の視覚的遅延時間の合計と等しい重みを有するように、無向グラフを作成するためのグラフ生成器４３０と、新たなチャネル割付け手法およびこの新たなチャネル割付け手法の下で最適化された最小の総合的ネットワーク干渉を得るために、特に半正定値計画（ＳＤＰ）法で、グラフ生成器４３０によって作成された無向グラフに着色するグラフ着色ユニット４４０と、総合的ネットワーク干渉計算器４２５およびグラフ着色ユニット４４０によってそれぞれ取得された、評価された総合的ネットワーク干渉と最適化された最小の総合的ネットワーク干渉の間の差分（干渉改善量）を所定の閾値と比較する比較器４５０と、比較器４５０の比較結果が、差分が閾値より大きく、総合的システム性能が非常に改善されることを示している場合、新たなチャネル割付け手法に従ってベーシックサービスセット（ＡＰ）のチャネル割付けを変更するコントローラ４６０とを含んでいる。
他方、比較器の比較結果が、差分が閾値より大きくなく、総合的システム性能が非常に改善されないことを示していれば、コントローラ４６０は、ベーシックサービスセット（ＡＰ）のチャネル割付けをそのまま維持する。本発明の動的チャネル割り当て方法は、システムをモニターし続ける（定期的にあるいは所定のトリガ機構で）。
【００８９】
図４Ｂは、ＶＤＴ計算器４２０の詳細を示している。
ＶＤＴ計算器４２０は、標準伝送時間計算器４２１０、低下伝送レートマッピングユニット４２２０、遅延伝送時間計算器４２３０、ノードＶＤＴ計算器４２４０、コントローラ４２５０および加算器４２６０を含んでいる。
【００９０】
標準伝送時間計算器４２１０は、トラフィック情報とレート情報を利用することにより式（３）に従ってノードｘ（１つのＢＳＳ集合Ｘに属する）の標準伝送時間Timex(Normal)を計算する。
【００９１】
低下伝送レートマッピングユニット４２２０は、ＳＩＮＲ−ＲＡＴＥ（レート）テーブル（例えば、テーブル１）の利用することにより、かつ各ノードとノードｘのＲＳＳＩ情報に基づいてノードｘの低下伝送レートRatexyをマッピングする。
【００９２】
遅延伝送時間計算器４２３０は、トラフィック情報、レート情報、および低下伝送レートマッピングユニット４２２０によってマッピングされたノードｘの低下伝送レートRatexyを利用することにより、式（６）に従って干渉源集合Ｙ（他のＢＳＳ）からの干渉の下におけるノードｘの遅延伝送時間Timex,y(Interferece)を計算する。
【００９３】
ノードＶＤＴ計算器４２４０は、標準伝送時間計算器４２１０および遅延伝送時間計算器４２３０によってそれぞれ計算されたノードｘの計算された標準伝送時間Timex(Normal)およびノードｘの計算された遅延伝送時間Timex,y(Interferece)を利用することにより、式（２’）に従って、干渉源集合Ｙからの干渉の下におけるノードｘの視覚的遅延時間VDT(x,Y)を計算する。
【００９４】
コントローラ４２５０は、集合Ｘに属する全てのノードｘについて視覚的遅延時間VDT(x,Y)が取得されたかどうか、つまり、集合Ｘに属する全てのノードｘが処理されたかどうかを判定する。
【００９５】
集合Ｘに属する全てのノードｘについて視覚的遅延時間VDT(x,Y)が取得されているとコントローラ４２５０が判定すると、コントローラ４２５０は、ノードＶＤＴ計算器加算器４２６０によって計算された集合Ｘに属する全てのノードｘについて視覚的遅延時間VDT(x,Y)を加算器４２６０に転送する。
加算器４２６０は、他のＢＳＳ集合Ｙからの干渉の下における１つのＢＳＳの視覚的遅延時間VDTXYを、式（８）に従ってセットＸに属する全てのノードｘについての視覚的遅延時間VDT(x,Y)の合計として計算する。
【００９６】
集合Ｘに属する全てのノードｘについての視覚的遅延時間VDT(x,Y)がまだ取得されていないとコントローラ４２５０が判定すると、コントローラ４２５０は、集合Ｘに属する他のノードｘを選択し、干渉源集合Ｙからの干渉の下における集合セットＸに属する新たに選択したノードｘの視覚的遅延時間VDT(x,Y)を計算するために、標準伝送時間計算器４２１０、低下伝送レートマッピングユニット４２２０、遅延伝送時間計算器４２３０およびノードＶＤＴ計算器４２４０を呼び出す。
【００９７】
同様に、他のＢＳＳ集合Ｙに属する各ノードｙと干渉源集合Ｘについて、低下伝送レートマッピングユニット４２２０、遅延伝送時間計算器４２３０、ノードＶＤＴ計算器４２４０、コントローラ４２５０および加算器４２６０は、１つのＢＳＳ集合Ｘからの干渉の下での他のＢＳＳ集合Ｙの視覚的遅延伝送時間VDTYXを取得するために同様の処理を実行する。
【００９８】
その結果、各組のＢＳＳセットＸおよびＹについて、１組の視覚的遅延時間VDTXYおよびVDTYXが取得される。
【００９９】
以上の説明は、本発明の好ましい実施の形態のみを提示するものであり、本発明に対していかなる限定も加えるものではない。従って、本発明の精神及び原則内においてなされた任意の変形、置き換え、改良などは本発明の範囲に含まれるものである。
【符号の説明】
【０１００】
４００：動的チャネル割り当て装置
４１０：検知器
４２０：視覚的遅延時間（ＶＤＴ）計算器
４２５：総合的ネットワーク干渉計算器
４３０：グラフ生成器
４４０：グラフ着色ユニット
４５０：比較器
４６０：コントローラ
４２１０：標準伝送時間計算器
４２２０：低下伝送レートマッピングユニット４２２０
４２３０：遅延伝送時間計算器４２３０
４２４０：ノードＶＤＴ計算器４２４０
４２５０：コントローラ４
４２６０：加算器
【図１】
2010119087.tif 000026
【図２】
2010119087.tif 000027
【図３Ａ】
2010119087.tif 000028
【図３Ｂ】
2010119087.tif 000029
【図４Ａ】
2010119087.tif 000030
【図４Ｂ】
2010119087.tif 000031
【外国語明細書】
2010119087000001.pdf