(57)【特許請求の範囲】
【請求項１】
複数の基地局の各々に対して移動局との間の通信用の周波数チャネルを割り当てる制御局装置において、
前記移動局毎に受信電波に基づいて作成された基地局のリストに基づき、各基地局のセル間の重複の有無を判断する重複判断手段と、
前記判断結果に基づき、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する判定手段と、
前記判定結果に応じて、基地局の組合せ毎の干渉回避の優先順位を決定する優先順位決定手段と、
前記優先順位に従って、各基地局に割り当てる周波数チャネルを決定する周波数チャネル決定手段と、
基地局を表すノードと、セル間の干渉のあり得る基地局間に対応するノード間を接続する枝と、から構成される無線基地局グラフを作成する無線基地局グラフ作成手段と、
前記無線基地局グラフに応じた彩色多項式を生成する彩色多項式生成手段と、
を備え、
前記判定手段は、
前記無線基地局グラフが前記所定数で彩色可能ならば、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能であると判定し、
前記優先順位決定手段は、前記無線基地局グラフにおいて、セル間の干渉の影響が小さいノード間の枝を前記優先順位が低いノードとして切断する際に、前記移動局毎に受信電波に基づいて算出された基地局の組み合わせ毎の搬送波対干渉波電力比に基づき、基地局の組み合わせ毎の搬送波対干渉波電力比の逆数の総和を求め、前記無線基地局グラフにおいて、前記総和がより小さい値となるノード間の枝を切断し、
前記周波数チャネル決定手段は、
枝で接続された２つのノードに対応する各基地局に対し、異なる周波数チャネルを割り当てるよう周波数チャネルを決定する
ことを特徴とすることを特徴とする制御局装置。
【請求項２】
前記干渉の判断結果に応じて、基地局の送信電力を制御する送信電力制御手段を備えたことを特徴とする請求項１に記載の制御局装置。
【請求項３】
前記干渉の判断結果に応じて、基地局の適応変調を制御する適応変調制御手段を備えたことを特徴とする請求項１に記載の制御局装置。
【請求項４】
複数の基地局の各々に対して移動局との間の通信用の周波数チャネルを割り当てる制御局の無線通信制御方法であって、
前記移動局毎に受信電波に基づいて作成された基地局のリストに基づき、各基地局のセル間の重複の有無を判断する過程と、
前記判断結果に基づき、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する過程と、
前記判定結果に応じて、基地局の組合せ毎の干渉回避の優先順位を決定する過程と、
前記優先順位に従って、各基地局に割り当てる周波数チャネルを決定する過程と、
基地局を表すノードと、セル間の干渉のあり得る基地局間に対応するノード間を接続する枝と、から構成される無線基地局グラフを作成する過程と、
前記無線基地局グラフに応じた彩色多項式を生成する過程と、
を備え、
前記周波数チャネルの割当てが可能か判定する過程は、
前記無線基地局グラフが前記所定数で彩色可能ならば、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能であると判定し、
前記優先順位を決定する過程は、前記無線基地局グラフにおいて、セル間の干渉の影響が小さいノード間の枝を前記優先順位が低いノードとして切断する際に、前記移動局毎に受信電波に基づいて算出された基地局の組み合わせ毎の搬送波対干渉波電力比に基づき、基地局の組み合わせ毎の搬送波対干渉波電力比の逆数の総和を求め、前記無線基地局グラフにおいて、前記総和がより小さい値となるノード間の枝を切断し、
前記周波数チャネルを決定する過程は、
枝で接続された２つのノードに対応する各基地局に対し、異なる周波数チャネルを割り当てるよう周波数チャネルを決定する
ことを特徴とすることを特徴とする無線通信制御方法。
【請求項５】
前記干渉の判断結果に応じて、基地局の送信電力を制御する過程を備えたことを特徴とする請求項４に記載の無線通信制御方法。
【請求項６】
前記干渉の判断結果に応じて、基地局の適応変調を制御する過程を備えたことを特徴とする請求項４に記載の無線通信制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、制御局装置及び無線通信制御方法に関する。
【背景技術】
【０００２】
従来より、無線接続サービスにおいて広域をカバーする広域セル方式の無線通信システムが知られている。広域セル方式の無線通信システムでは、少数の基地局で広域の通信エリアを実現できる反面、局所的な電波の不感地帯が散在する可能性がある、又、１基地局当たりで収容するユーザ数が多く、基地局の処理能力がボトルネックとなる可能性がある、などの問題がある。これらの問題に対処するために基地局数を増加させることが考えられるが、広域セル方式の基地局装置は高コストである点、又、基地局の新規設置時において干渉増大の抑制のための綿密な置局設計が必要とされる点、などから柔軟な対応が困難である。
【０００３】
そのような状況下において、広域セルに比べてセルサイズが極小であるピコセルを用いた無線通信システムが検討されている。ピコセル方式の無線通信システムでは、基地局装置が広域セル方式に比べて安価であるので、基地局装置の増加にも比較的対応がしやすい。また、ピコセル方式によれば、適切に基地局の配置を行えば、周波数利用効率の向上が望めるという利点もある。但し、広域セル方式と同様に、干渉増大の抑制のための綿密な置局設計を行わなければ、周波数チャネルが基地局間で互いに干渉し、所望の伝送性能が得られない事態が発生し得る。しかし、ピコセル方式の基地局は簡易に設置することができることから、基地局の設置自由度が大きいことがピコセル方式の利点でもあり、綿密な置局設計を行って設置者の意向に反して指定の場所に基地局を設置するよう強制することは本望ではない。このため、できるだけ任意の場所に基地局を設置できるように置局設計は簡易化し、その分、置局後の基地局間で生じる周波数チャネルの干渉を回避もしくは軽減する方が好ましい。
【０００４】
セルラシステムにおける従来のセル設計技術では、例えば非特許文献１に記載されるように、セル形状を三角形、四角形、六角形などの多角形で近似することを想定している。そのように想定した環境下における従来の周波数チャネル割当て方法としては、例えば特許文献１に記載の方法が知られている。特許文献１記載の方法では、多角形の形状を想定したセルを間断なく配置した環境において、セル間の干渉をトラヒック量等から推定し、複数のセル間における干渉が大きい場合には同一周波数帯域が割り当てられるセルの距離間隔を大きくし、逆に干渉が小さい場合には同一周波数帯域が割り当てられるセルの距離間隔を小さくしている。
【非特許文献１】奥村・進士監修、「移動通信の基礎」、第8章、（社）電子情報通信学会
【特許文献１】特開２００５−２７１８９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、上述した従来の周波数チャネル割当て方法では、多角形のセルが規則的に間断なく配置された環境を想定しており、例えばピコセル方式において基地局が任意の場所に設置されることにより、セルが複雑に重複配置されるような環境に対しては、適用することが難しい。
【０００６】
本発明は、このような事情を考慮してなされたもので、その目的は、基地局が任意の場所に、かつ、不規則に設置及び廃止されることを許容しつつ、各基地局のセル間で生じる周波数チャネルの干渉を回避もしくは軽減することのできる無線通信システム、制御局装置、移動局装置及び無線通信制御方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記した課題を解決するために、本発明の一態様に係る制御局装置は、複数の基地局の各々に対して移動局との間の通信用の周波数チャネルを割り当てる制御局装置において、  前記移動局毎に受信電波に基づいて作成された基地局のリストに基づき、各基地局のセル間の重複の有無を判断する重複判断手段と、前記判断結果に基づき、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する判定手段と、前記判定結果に応じて、基地局の組合せ毎の干渉回避の優先順位を決定する優先順位決定手段と、前記優先順位に従って、各基地局に割り当てる周波数チャネルを決定する周波数チャネル決定手段と、基地局を表すノードと、セル間の干渉のあり得る基地局間に対応するノード間を接続する枝と、から構成される無線基地局グラフを作成する無線基地局グラフ作成手段と、前記無線基地局グラフに応じた彩色多項式を生成する彩色多項式生成手段と、を備え、前記判定手段は、前記無線基地局グラフが前記所定数で彩色可能ならば、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能であると判定し、前記優先順位決定手段は、前記無線基地局グラフにおいて、セル間の干渉の影響が小さいノード間の枝を前記優先順位が低いノードとして切断する際に、前記移動局毎に受信電波に基づいて算出された基地局の組み合わせ毎の搬送波対干渉波電力比に基づき、基地局の組み合わせ毎の搬送波対干渉波電力比の逆数の総和を求め、前記無線基地局グラフにおいて、前記総和がより小さい値となるノード間の枝を切断し、前記周波数チャネル決定手段は、枝で接続された２つのノードに対応する各基地局に対し、異なる周波数チャネルを割り当てるよう周波数チャネルを決定することを特徴とする。
【０００９】
上記制御局装置において、前記干渉の判断結果に応じて、基地局の送信電力を制御する送信電力制御手段を備えてもよい。
【００１０】
上記制御局装置において、前記干渉の判断結果に応じて、基地局の適応変調を制御する適応変調制御手段を備えてもよい。
【００１７】
本発明の他の態様に係る無線通信制御方法は、複数の基地局の各々に対して移動局との間の通信用の周波数チャネルを割り当てる制御局の無線通信制御方法であって、前記移動局毎に受信電波に基づいて作成された基地局のリストに基づき、各基地局のセル間の重複の有無を判断する過程と、前記判断結果に基づき、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する過程と、前記判定結果に応じて、基地局の組合せ毎の干渉回避の優先順位を決定する過程と、前記優先順位に従って、各基地局に割り当てる周波数チャネルを決定する過程と、基地局を表すノードと、セル間の干渉のあり得る基地局間に対応するノード間を接続する枝と、から構成される無線基地局グラフを作成する過程と、前記無線基地局グラフに応じた彩色多項式を生成する過程と、を備え、前記周波数チャネルの割当てが可能か判定する過程は、前記無線基地局グラフが前記所定数で彩色可能ならば、所定数の周波数チャネルで、各基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能であると判定し、前記優先順位を決定する過程は、前記無線基地局グラフにおいて、セル間の干渉の影響が小さいノード間の枝を前記優先順位が低いノードとして切断する際に、前記移動局毎に受信電波に基づいて算出された基地局の組み合わせ毎の搬送波対干渉波電力比に基づき、基地局の組み合わせ毎の搬送波対干渉波電力比の逆数の総和を求め、前記無線基地局グラフにおいて、前記総和がより小さい値となるノード間の枝を切断し、前記周波数チャネルを決定する過程は、枝で接続された２つのノードに対応する各基地局に対し、異なる周波数チャネルを割り当てるよう周波数チャネルを決定することを特徴とする。
【００１８】
上記無線通信制御方法において、前記干渉の判断結果に応じて、基地局の送信電力を制御する過程を備えてもよい。
【００１９】
上記無線通信制御方法において、前記干渉の判断結果に応じて、基地局の適応変調を制御する過程を備えてもよい。
【発明の効果】
【００２０】
本発明によれば、基地局が任意の場所に、かつ、不規則に設置及び廃止されることを許容しつつ、各基地局のセル間で生じる周波数チャネルの干渉を回避もしくは軽減することができる。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照し、本発明の一実施形態について説明する。
図１は、本発明の一実施形態に係る無線通信システムの構成を示すブロック図である。図１において、集中制御局１は、各無線基地局２に通信回線を介して接続されている。各無線基地局２は、それぞれの無線接続サービスエリアであるセル１００を形成している。移動局３は、在圏しているセル１００の無線基地局２と無線接続することができる。
【００２２】
図１の例では３つのセル１００は互いに重複して配置されている。このため、各無線基地局２のセル間で周波数チャネルの干渉が生じる可能性があり、干渉対策を講じることが望ましい。そこで、本実施形態では、集中制御局１が周波数チャネルの割当を調整し、各無線基地局２のセル間で生じ得る周波数チャネルの干渉を回避もしくは軽減することを図る。
【００２３】
以下、本実施形態に係る周波数チャネル割当て方法について詳細に説明する。
【００２４】
ピコセル方式の無線通信システムのように基地局が任意に設置及び廃止される場合には、全ての基地局間の位置関係を正確に把握することができないので、セル同士が重複して配置されていたとしても、その重複しているセル間の位置関係を基地局間の位置関係から知ることは難しい。そのため、本実施形態では、移動局３がアクセス可能な無線基地局２をアクセス可能局リストとしてリスト化し、集中制御局１はそのアクセス可能局リストを取得して参照することにより、各無線基地局２のセル間のエリアの重複関係を推定し、同一周波数チャネルを用いた場合に周波数チャネル干渉が発生し得るか判定する。
【００２５】
図２は、図１に示す集中制御局１の構成を示すブロック図である。
図２において、集中制御局１は、制御開始通知部１１と干渉報告受信部１２と周波数チャネル割当て制御部１３と使用周波数チャネル通知部１４とを有する。
【００２６】
集中制御局１において制御開始通知部１１は、自集中制御局１の配下の無線基地局２に対して周波数チャネル割当て動作の開始を通知する。この通知によって、無線基地局２は接続中の移動局３に対してアクセス可能局リストを要求する。この要求によって、移動局３は、受信電波に基づき、無線基地局２のリストを作成する。そのリスト作成処理では、現時点で通信可能である無線基地局２を記載したアクセス可能局リストを作成する。移動局３は、アクセス可能局リストを接続中の無線基地局２に送信する。無線基地局２は、移動局３からのアクセス可能局リストを集中制御局１に送信する。
【００２７】
図３には、アクセス可能局リストの例が示されている。図３に示される無線通信システムの例（図３には集中制御局１は図示していない）では、４つの無線基地局２Ａ、２Ｂ、２Ｃ、２Ｄが存在し、それぞれ対応するセル１００Ａ、１００Ｂ、１００Ｃ、１００Ｄが形成されている。それらセル１００Ａ、１００Ｂ、１００Ｃ、１００Ｄは重複して配置されている。具体的には、セル１００Ａ、１００Ｂ、１００Ｃは互いに重複して配置されている。また、セル１００Ｂ、１００Ｃ、１００Ｄは互いに重複して配置されている。セル１００Ａと１００Ｄは重複していない。また、図３の例では、３台の移動局３ａ、３ｂ、３ｃが存在している。移動局３ａはセル１００Ａと１００Ｂの重複エリアに在圏している。移動局３ｂはセル１００Ａと１００Ｂと１００Ｃの重複エリアに在圏している。移動局３ｃはセル１００Ｃと１００Ｄの重複エリアに在圏している。
【００２８】
図３においては、移動局３ａは無線基地局２Ａと２Ｂとに通信可能であるので、無線基地局２Ａと２Ｂを記載したアクセス可能局リスト２００ａを作成する。移動局３ｂは無線基地局２Ａと２Ｂと２Ｃとに通信可能であるので、無線基地局２Ａと２Ｂと２Ｃを記載したアクセス可能局リスト２００ｂを作成する。移動局３ｃは無線基地局２Ｃと２Ｄとに通信可能であるので、無線基地局２Ｃと２Ｄを記載したアクセス可能局リスト２００ｃを作成する。各アクセス可能局リスト２００ａ、２００ｂ、２００ｃは、それぞれの移動局が接続中の無線基地局を介して集中制御局１に送られる。
【００２９】
集中制御局１において干渉報告受信部１２は、アクセス可能局リストを受信する。干渉報告受信部１２は、アクセス可能局リストに基づき、各無線基地局２のセル間の重複の有無を判断する。また、干渉報告受信部１２は、各無線基地局２のセル間において干渉が発生する可能性の有無を表す無線基地局グラフを作成する。図４には、図３に例示される３つのアクセス可能局リスト２００ａ、２００ｂ、２００ｃに基づいて作成された無線基地局グラフ３００が示されている。無線基地局グラフ３００において、ノードＡ、Ｂ、Ｃ、Ｄは、それぞれ無線基地局２Ａ、２Ｂ、２Ｃ、２Ｄを表す。ノード間を接続する枝は、接続している２つのノードに対応する各無線基地局２のセル間で干渉が発生し得ることを表し、当該２つの無線基地局２のセルの重複エリアに対応している。
【００３０】
干渉報告受信部１２は、同一アクセス可能局リスト中に記載された各無線基地局２のセル間には干渉が発生し得るものとして、当該ノード間を枝で接続する。これにより、図４の無線基地局グラフ３００では、アクセス可能局リスト２００ａ中に記載された無線基地局２Ａと２Ｂ間、アクセス可能局リスト２００ｂ中に記載された無線基地局２Ａと２Ｂと２Ｃの各間、アクセス可能局リスト２００ｃ中に記載された無線基地局２Ｃと２Ｄ間のそれぞれ対応するノード間が枝で接続される。
【００３１】
なお、無線基地局グラフは、実質的に図４に例示されるようにノードと枝とから構成されればよく、その表現方法には限定されない。例えば、図５に例示されるように、行列形式で無線基地局グラフを構成してもよい。図５には、図４に示される無線基地局グラフ３００が行列形式で構成されている。図５において、各行及び各列はノードＡ、Ｂ、Ｃ、Ｄに対応している。そして、ノードの組み合わせに対応する行列要素は当該ノード間の枝の有無を表し、行列要素“１”は枝有りを表し、行列要素“０”は枝無しを表す。例えば、ノードＡとノードＢの組み合わせに対応する１行２列の行列要素は“１”であり、当該ノードＡ、Ｂ間には枝が有ることを表す。一方、ノードＡとノードＤの組み合わせに対応する１行４列の行列要素は“０”であり、当該ノードＡ、Ｄ間には枝が無いことを表す。
【００３２】
干渉報告受信部１２が作成した無線基地局グラフにおいては、枝の両端の各ノードに対応する各無線基地局２のセル間で干渉発生の可能性ありが示されると共に、その干渉によって通信に悪影響の及ぶ移動局３が存在することが示されている。従って、その干渉を回避もしくは軽減するためには、無線基地局グラフ中の枝で接続された２つのノードに対応する各無線基地局２に対しては異なる周波数チャネルを割り当てればよい。
【００３３】
集中制御局１において周波数チャネル割当て制御部１３は、セル間の重複の有無の判断結果に基づき、所定数の周波数チャネルで、各無線基地局２に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する。この判定処理では、干渉報告受信部１２が作成した無線基地局グラフを使用する。周波数チャネル割当て制御部１３は、その判定結果に応じて、無線基地局２の組合せ毎の干渉回避の優先順位を決定する。この優先順位決定処理では、現在の無線基地局グラフの状況では周波数チャネルの割り当てが成功しない場合に、セル間の干渉の影響が小さいノード間の枝を切断する。
【００３４】
周波数チャネル割当て制御部１３は、その優先順位に従って、各無線基地局に割り当てる周波数チャネルを決定する。この周波数チャネル決定処理では、優先順位が反映された無線基地局グラフ（つまり、枝切断後の無線基地局グラフ）において、枝で接続された２つのノードに対応する各無線基地局２に対しては異なる周波数チャネルを割り当てる。例えば、図４の無線基地局グラフ３００では、枝の両端の２つのノードの組として、ノードＡとＢ、ノードＡとＣ、ノードＢとＣ、ノードＣとＤの４つの組がある。これら４つの組の全てにおいて、組中の２つのノードに対応する各無線基地局２に対しては異なる周波数チャネルを割り当てるようにする。
【００３５】
使用周波数チャネル通知部１４は、その割当て結果の各無線基地局２の使用周波数チャネルの情報を各無線基地局２に通知する。
【００３６】
次に、上記した集中制御局１の周波数チャネル割当て制御部１３が行う周波数チャネルの割当てに係る動作を詳細に説明する。
【００３７】
始めに、図６を参照して、周波数チャネルの割当てに係る全体動作を説明する。
図６は、本実施形態に係る周波数チャネル割当て処理の手順を示すフローチャートである。図６において、ステップＳ１では、集中制御局１は、各移動局３が作成したアクセス可能局リストを収集し、各無線基地局２のセル間の重複を把握する。ステップＳ２では、その収集したアクセス可能局リストに基づき、無線基地局グラフを作成する。
【００３８】
ステップＳ３〜Ｓ６では、周波数チャネル割当て制御部１３が、無線基地局グラフに基づき、無線基地局２に対する周波数チャネルの割当てを行う。ここで、上記したように、所定数の周波数チャネルで、各無線基地局２に対してセル間干渉を回避できる周波数チャネルの割当てが可能か判定する。本実施形態では、この問題をグラフ理論における彩色問題として扱う。つまり、無線基地局グラフ中の枝の両端の各ノードを異なる色で彩色する問題として扱う。彩色に使用可能な色の数は、利用可能な周波数チャネルの数である。利用可能な周波数チャネルの数は予め定められている。
【００３９】
先ず、ステップＳ３では、無線基地局グラフに応じた彩色多項式P(k)を生成する。kは彩色に使用可能な色の数である。彩色多項式P(k)は、任意のグラフをk色で彩色する場合に、その塗り方の数を与える関数（彩色関数）である。与えられたグラフが単純グラフ（各ノード間を接続する枝が必ず１本のみであるグラフ）であれば、彩色関数は必ずkの多項式となる。また、彩色多項式P(k)の値が「k＝R」の条件で必ず１以上であることが保証されるのであれば、与えられたグラフはR色で彩色可能である。
【００４０】
本実施形態の無線基地局グラフは単純グラフであるので、必ず彩色多項式P(k)が生成可能である。従って、利用可能な周波数チャネルの数がRであるとき、「k＝R」の条件で彩色多項式P(k)の値が１以上になれば、少なくとも１つの塗り方が存在するので、無線基地局グラフはR色で彩色可能である。そして、無線基地局グラフがR色で彩色可能ならば、所定数Rの周波数チャネルで、各無線基地局２への周波数チャネルの割り当てを成功させることができると判定することができる。
【００４１】
ステップＳ４では、「k＝R」の条件での彩色多項式P(k)の値P(R)が１以上であるか判断する。この結果、値P(R)が１未満ならば、無線基地局グラフの枝を切断する（ステップＳ５）。このとき、切断する枝は、セル間の干渉の影響が小さいノード間の枝である。その枝切断後にステップＳ３に戻り、彩色多項式P(k)を生成し直す。
【００４２】
ステップＳ４の判断の結果、値P(R)が１以上ならば、無線基地局グラフはR色で彩色可能であるので、当該無線基地局グラフに基づき、各無線基地局２への周波数チャネルの割り当てを行う（ステップＳ６）。このとき、無線基地局グラフ中の枝で接続された２つのノードに対応する各無線基地局２に対しては、異なる周波数チャネルを割り当てる。
【００４３】
ステップＳ７では、各無線基地局２に対して、割り当てられた周波数チャネルを通知する。
【００４４】
次に、彩色多項式P(k)の生成方法を説明する。
【００４５】
図７には、グラフの例として、簡単なグラフＧ１、Ｇ２が示されている。図７（１）のグラフＧ１をk色で彩色する場合の彩色多項式PＧ１(k)は、（１）式となる。
PＧ１(k)＝k(k-1)2      ・・・（１）
また、図７（２）のグラフＧ２をk色で彩色する場合の彩色多項式PＧ２(k)は、（２）式となる。
PＧ２(k)＝k(k-1)(k-2)      ・・・（２）
従って、例えばグラフＧ１の場合、kが２以上ならば、（１）式の値は必ず１以上になることが保証される。これにより、グラフＧ１は２色で彩色可能であることが分かる。同様にグラフＧ２の場合、kが３以上ならば、（２）式の値は必ず１以上になるので、グラフＧ２は３色で彩色可能であることが分かる。このように、ある無線基地局グラフに対して、その彩色多項式を生成することにより、何色で彩色可能であるかを判定することが可能になる。
【００４６】
以下、任意の無線基地局グラフに対して彩色多項式を生成する方法を説明する。なお、ここで挙げる方法は一般に知られているものである。
本生成方法では、次の定理を用いる。
［定理］
単純グラフＧから枝ｅを除去して得られるグラフ「Ｇ−ｅ」と、単純グラフＧから枝ｅを縮約して得られるグラフ「Ｇ＼ｅ」との間には、（３）式の関係が成立する。
PＧ(k)＝PＧ−ｅ(k)−PＧ＼ｅ(k)      ・・・（３）
但し、PＧ(k)は単純グラフＧの彩色多項式、PＧ−ｅ(k)はグラフ「Ｇ−ｅ」の彩色多項式、PＧ＼ｅ(k)はグラフ「Ｇ＼ｅ」の彩色多項式である。
また、枝の除去とは、枝を取り除くことを指す。
また、枝の縮約とは、枝を取り除き、その両端のノードを一つのノードに合成することを指す。このとき、重複する枝が発生する場合には一本の枝として再記述する。
【００４７】
この定理を用いて、任意のグラフの彩色多項式を次のアルゴリズムにより生成することができる。
ステップＳ１１；任意の枝を選択し、その選択した枝を除去したグラフと、その選択した枝を縮約したグラフとを生成する。そして、上述の定理を適用する。
ステップＳ１２；ステップＳ１１で生成した二つのグラフにおいてさらに任意の枝を選択し、それぞれのグラフにおいて、その選択した枝を除去したグラフと、その選択した枝を縮約したグラフとを生成する。そして、上述の定理を適用する。
ステップＳ１３；上記の工程を、当初のグラフが空グラフ（枝が０本のグラフ）または所定の形のグラフ（例えば図７のグラフＧ１、Ｇ２など）のみで表されるまで繰り返す。
ステップＳ１４；最終的に得られたグラフ群に含まれる各グラフを、空グラフの彩色多項式または所定の形のグラフの彩色多項式に置換し、当初のグラフの彩色多項式を得る。
【００４８】
具体的に、図８を参照して、上述のアルゴリズムを説明する。
図８において、（Ａ）式の左辺のグラフが当初のグラフＧである。
先ず、当初グラフＧから、枝ｅを除去したグラフ（（Ａ）式の右辺第一項のグラフ）と、枝eを縮約したグラフ（（Ａ）式の右辺第二項のグラフ）とを生成する。ここで、上述の定理により、左辺のグラフの彩色多項式は右辺に示す二つのグラフの彩色多項式の差となる。これにより、（Ａ）式が得られる（ステップＳ１１）。
【００４９】
次いで、（Ａ）式の右辺第一項のグラフの枝eを、除去したグラフと縮約したグラフとを生成する。また、（Ａ）式の右辺第二項のグラフの枝eを、除去したグラフと縮約したグラフとを生成する。そして、上述の定理を適用する。これにより、（Ｂ）式の右辺が得られる（ステップＳ１２）。
【００５０】
次いで、そのステップＳ１２の処理を（Ｂ）式の右辺に対してもう一度繰り返すことによって、（Ｃ）式の右辺が得られる（ステップＳ１２）。
【００５１】
次いで、（Ｃ）式の右辺に含まれる各グラフを彩色多項式に置換する。（Ｃ）式の右辺には５つのグラフが含まれており、その種類は４種類である。（Ｃ）式の右辺において、左から順番に各グラフの彩色多項式を示すと、
k(k-1)4、
k(k-1)3、
k(k-1)3、
k(k-1)2、
k(k-1)(k-2)、
となる。なお、空グラフの彩色多項式は、図９に示される（４）式である。
【００５２】
（Ｃ）式の右辺の各グラフを、それぞれ対応する彩色多項式に置換する。これにより、図８の当初グラフＧの彩色多項式PＧ(k)は、（５）式として得られる。
PＧ(k)＝k(k-1)4−k(k-1)3−２（k(k-1)3−k(k-1)2）＋k(k-1)(k-2)
＝k(k-1)4−３k(k-1)3＋２k(k-1)2＋k(k-1)(k-2)
＝k(k-1)(k-2)3      ・・・（５）
【００５３】
（５）式から、kが3以上の場合に彩色多項式PＧ(k)の値は１以上になることが保証される。これにより、３色あれば、図８の当初グラフＧは彩色可能であることが分かる。
【００５４】
次に、無線基地局グラフの枝の切断方法を説明する。
【００５５】
利用可能な周波数チャネルの数がRであるとき、「k＝R」の条件で彩色多項式P(k)の値が１未満でありR色で彩色不可能であった場合には、無線基地局グラフの枝を一本選択して切断し、無線基地局グラフの近似を行う。図１０に枝切断の例を示す。
【００５６】
図１０の例では、使用可能な色の数（利用可能な周波数チャネルの数）は３である。先ず、図１０（Ａ）に示される最初の無線基地局グラフＧａが生成される。図１０（Ａ）の無線基地局グラフＧａの彩色多項式PＧａ(k)は、（６）式である。
PＧａ(k)＝k(k-1)(k-2)(k-3)(k-4)      ・・・（６）
【００５７】
（６）式から、値PＧａ(3)は１未満であるので、無線基地局グラフＧａは３色では彩色することができない。このため、枝を一本切断し、図１０（Ｂ）の無線基地局グラフＧｂに変形する。なお、ここでは、切断する枝は説明の便宜上の枝である。
【００５８】
図１０（Ｂ）の無線基地局グラフＧｂの彩色多項式PＧｂ(k)は、（７）式である。
PＧａ(k)＝k(k-1)(k-2)(k-3)2      ・・・（７）
（７）式から、値PＧｂ(3)は１未満であるので、無線基地局グラフＧｂでも３色では彩色することができない。このため、さらに枝を一本切断し、図１０（Ｃ）の無線基地局グラフＧｃに変形する。
【００５９】
図１０（Ｃ）の無線基地局グラフＧｃの彩色多項式PＧｃ(k)は、（８）式である。
PＧａ(k)＝k(k-1)2(k-2)2      ・・・（８）
（８）式から、値PＧｃ(3)は１以上であるので、無線基地局グラフＧｃならば３色で彩色することができる。これにより、無線基地局グラフＧｃに基づき、各無線基地局２への周波数チャネルの割り当てを行う。このとき、無線基地局グラフＧｃ中の枝で接続された２つのノードに対応する各無線基地局２に対しては、異なる周波数チャネルを割り当てる。
【００６０】
無線基地局グラフ中の枝を切断することは、セルが重複している複数の無線基地局２に、同一の周波数チャネルを割り当てることを許容することに相当する。セルが重複している複数の無線基地局２に同一の周波数チャネルが割り当てられると、その重複しているセル間で干渉が発生し得る。従って、そのセル間の干渉の影響が小さい無線基地局２間（ノード間）の枝を切断することが好ましい。以下、セル間の干渉の影響が小さい無線基地局２間（ノード間）の枝を選択する方法を説明する。
【００６１】
［第１の枝選択方法］
第１の枝選択方法では、移動局３毎に受信電波に基づいて算出された無線基地局２の組み合わせ毎の搬送波対干渉波電力比（Carrier to Interference Ratio：ＣＩＲ）に基づき、無線基地局２の組み合わせ毎のＣＩＲの最低値を求め、無線基地局グラフにおいて、該最低値がより高い値となるノード間の枝を切断する。
【００６２】
移動局３は、受信電波に基づき、無線基地局２の組み合わせ毎のＣＩＲを求める計測手段を備える。移動局３は、通信可能な全ての無線基地局２を一つずつ所望局にして、それぞれのＣＩＲを測定する。なお、そのＣＩＲ測定において、ＣＩＲの測定対象となる無線基地局２間が同一の周波数チャネルを使用していない場合には、それぞれの無線基地局２からの受信信号強度（Received Signal Strength Indicator：ＲＳＳＩ）を測定し、該ＲＳＳＩ測定値を同一の周波数チャネルの値として想定のＣＩＲを算出する。本実施形態では、この想定のＣＩＲも含めてＣＩＲとする。
【００６３】
移動局３で測定された無線基地局２の組み合わせ毎のＣＩＲは、集中制御局１に送られる。例えば、アクセス可能局リストと同時に集中制御局１に送られる。
【００６４】
集中制御局１において周波数チャネル割当て制御部１３は、各移動局３から報告されたＣＩＲに基づき、無線基地局２の組み合わせ毎のスコアを決定し記録する。具体的には、無線基地局２の同一組み合わせに関するＣＩＲの中で最低値を当該無線基地局２の組み合わせの、つまり該当する枝のスコアに決定する。
【００６５】
ここで、スコアの高い枝に対応する干渉エリアの方が、他のスコアの低い枝に対応する干渉エリアよりも、高いＣＩＲを提供可能である。このことから、スコアの高い枝に対応する干渉エリアの方が、他のスコアの低い枝に対応する干渉エリアよりも、干渉の影響が少ないと考えられる。従って、スコアの最も高い枝を切断対象とする。
【００６６】
［第２の枝選択方法］
第２の枝選択方法では、アクセス可能局リストにより報告された無線基地局２の組み合わせ毎の報告数を求め、無線基地局グラフにおいて、該報告数が最も少ない値となるノード間の枝を切断する。
【００６７】
集中制御局１において周波数チャネル割当て制御部１３は、アクセス可能局リストにより報告された無線基地局２の組み合わせ毎の報告数を算出する。ある２つの無線基地局２の組がｎ個のアクセス可能局リスト中に記載されていた場合は、当該２つの無線基地局２の組の報告数はｎとなる。例えば、ある２つの無線基地局２の組が３つのアクセス可能局リスト中にのみ記載されていた場合は、当該２つの無線基地局２の組の報告数は３である。各無線基地局２の組のスコアは、無線基地局グラフ中の対応する枝のスコアとして記録する。
【００６８】
本報告数が少ない方が干渉の影響を与えている移動局３の数が少ない。従って、スコアの最も低い枝を切断対象とする。
【００６９】
［第３の枝選択方法］
第３の枝選択方法では、移動局３毎に受信電波に基づいて算出された無線基地局２の組み合わせ毎のＣＩＲに基づき、無線基地局２の組み合わせ毎のＣＩＲの逆数の総和を求め、無線基地局グラフにおいて、該総和がより小さい値となるノード間の枝を切断する。
【００７０】
上述の第１の枝選択方法と同様に、移動局３で測定された無線基地局２の組み合わせ毎のＣＩＲは、集中制御局１に送られる。
【００７１】
集中制御局１において周波数チャネル割当て制御部１３は、各移動局３から報告されたＣＩＲに基づき、無線基地局２の組み合わせ毎のスコアを決定し記録する。具体的には、無線基地局２の同一組み合わせに関するＣＩＲの逆数の総和を算出し、該総和を当該無線基地局２の組み合わせの、つまり該当する枝のスコアに決定する。
【００７２】
ここで、スコアの低い枝に対応する干渉エリアの方が、他のスコアの高い枝に対応する干渉エリアよりも、高いＣＩＲを提供可能である。このことから、スコアの低い枝に対応する干渉エリアの方が、他のスコアの高い枝に対応する干渉エリアよりも、干渉の影響が少ないと考えられる。従って、スコアの最も低い枝を切断対象とする。
【００７３】
なお、一般にＣＩＲにはデシベル単位が使用されるが、「ＣＩＲの逆数」の算出には、デシベル単位に換算しない、次式で表されるＣＩＲを用いることが好ましい。
ＣＩＲ＝搬送波の受信電力／干渉波の受信電力
【００７４】
上述したように本実施形態によれば、移動局毎に受信電波に基づいて作成された無線基地局のリスト（アクセス可能局リスト）から、セル間の重複の有無が判断される。その結果から、所定数の周波数チャネルで、各無線基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能かが判定され、不可能である場合には無線基地局の組合せ毎の干渉回避の優先順位を決定し、その優先順位に従って、各無線基地局に割り当てる周波数チャネルが決定される。これにより、例えばピコセル方式において無線基地局が任意の場所に、かつ、不規則に設置及び廃止されることにより、セルが複雑に重複配置されるような環境であっても、各無線基地局のセル間で生じる周波数チャネルの干渉を回避もしくは軽減することができる。
【００７５】
また、各無線基地局のセル間の干渉の判断結果として、各無線基地局のセル間において干渉が発生する可能性の有無を表す無線基地局グラフを作成するので、所定数の周波数チャネルで、各無線基地局への周波数チャネルの割り当てを行う処理が簡単になる。
【００７６】
さらに、無線基地局グラフに応じた彩色多項式を生成するので、グラフ理論における彩色問題として、所定数の周波数チャネルで、各無線基地局に対してセル間干渉を回避できる周波数チャネルの割当てが可能かの判定を行うことができる。これにより、周波数チャネル割当て処理がさらに簡単になる。
【００７７】
以上、本発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
例えば、各無線基地局のセル間の重複の有無の判断結果に応じて、無線基地局の送信電力を制御するようにしてもよい。その重複の有無の判断結果としては、無線基地局グラフが利用可能である。
【００７８】
また、各無線基地局のセル間の重複の有無の判断結果に応じて、無線基地局の適応変調を制御するようにしてもよい。その重複の有無の判断結果としては、無線基地局グラフが利用可能である。
【００７９】
なお、本発明は、ピコセル方式など、各種セル方式の無線通信システムに適用可能である。
【図面の簡単な説明】
【００８０】
【図１】本発明の一実施形態に係る無線通信システムの構成を示すブロック図である。
【図２】図１に示す集中制御局１の構成を示すブロック図である。
【図３】本発明の一実施形態に係るアクセス可能局リストの例を示す図である。
【図４】本発明の一実施形態に係る無線基地局グラフの例を示す図である。
【図５】本発明の一実施形態に係る無線基地局グラフの他の例を示す図である。
【図６】本発明の一実施形態に係る周波数チャネル割当て処理の手順を示すフローチャートである。
【図７】本発明の一実施形態に係る彩色多項式の生成方法を説明するためのグラフの例を示す図である。
【図８】本発明の一実施形態に係る彩色多項式の生成方法を説明するための説明図である。
【図９】本発明の一実施形態に係る彩色多項式の生成方法を説明するためのグラフ及び彩色多項式の例を示す図である。
【図１０】本発明の一実施形態に係る無線基地局グラフの枝の切断方法を説明するための説明図である。
【符号の説明】
【００８１】
１…集中制御局、２…無線基地局、３…移動局、１１…制御開始通知部、１２…干渉報告受信部、１３…周波数チャネル割当て制御部、１４…使用周波数チャネル通知部、１００…セル、３００…無線基地局グラフ
【図１】
0004786413.tif 000002
【図２】
0004786413.tif 000003
【図３】
0004786413.tif 000004
【図４】
0004786413.tif 000005
【図５】
0004786413.tif 000006
【図６】
0004786413.tif 000007
【図７】
0004786413.tif 000008
【図８】
0004786413.tif 000009
【図９】
0004786413.tif 000010
【図１０】
0004786413.tif 000011