最適解検出装置及び最適解検出プログラム
【課題】実行可能解の最適解を短時間で検出することができる最適解検出装置及び最適解検出プログラムを提供する。
【解決手段】最適解検出装置１００は、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部１４０を備える。
【解決手段】最適解検出装置１００は、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部１４０を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適解検出装置及び最適解検出プログラムに関する。
【背景技術】
【０００２】
無線通信システム、特に携帯電話に代表される移動体通信システムでは、通信エリアを実際に構築する前に、基地局を設置する位置を設計者が事前に検討する置局設計が行われる。置局設計では、通信エリアを構築する対象とされた範囲を含む地図が、予め定められたサイズの領域（以下、「ＢＩＮ」という）により複数に分割される。基地局を設置する位置は、これらＢＩＮ毎の受信電力等に基づいて、制約条件（例えば、トラヒック需要）を満たすよう検討される。
【０００３】
このような置局設計において、トラヒック需要を満たすマクロ基地局の配置と、そのパラメータの設定とを行うことを目的とした置局設計方法が、特許文献１に開示されている。
【０００４】
また、近年、スマートフォンなどの登場により、移動体通信システムのトラヒック需要は、急激な増加傾向にある。そこで、マクロ基地局のカバレッジエリア内のＢＩＮに、送信電力が小さい小型基地局をさらに設置することによって、マクロ基地局の負荷を分散することができる「ヘテロジニアスネットワーク（Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｎｅｔｗｏｒｋ：ＨｅｔＮｅｔ）」が注目されている。
【０００５】
さらに、ヘテロジニアスネットワークにおいて、より高い負荷分散効果を得るための技術として、Ｃｅｌｌ Ｒａｎｇｅ Ｅｘｐａｎｓｉｏｎ（ＣＲＥ）が検討されている。ＣＲＥのパラメータの一つである、受信電力に対するバイアス（以下、「ＣＲＥバイアス」という）に応じて、小型基地局がカバレッジエリアを拡大することにより、ヘテロジニアスネットワークは、より高い負荷分散効果を得る。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２０１２６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に開示された置局設計方法では、ヘテロジニアスネットワークに特有であるＣＲＥのパラメータは、まったく考慮されていない。このため、特許文献１に開示された様な置局設計方法により定められるパラメータに、例えば、ＣＲＥのパラメータ等が追加された場合、トラヒック需要を収容し且つ費用が最小となる実行可能解の最適解を検出するための処理時間は、指数関数的に増加してしまうという問題がある。
【０００８】
本発明は、前記の点に鑑みてなされたものであり、実行可能解の最適解を短時間で検出することができる最適解検出装置及び最適解検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、上記の課題を解決するためになされたものであり、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部、を備えることを特徴とする最適解検出装置である。
【００１０】
また、本発明は、前記最適化部が、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群を費用が増加する方向に変更することにより、実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１１】
また、本発明は、前記最適化部が、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用が最小となる最適解を検出することを特徴とする最適解検出装置である。
【００１２】
また、本発明は、前記最適化部が、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１３】
また、本発明は、前記最適化部が、ヘテロジニアスネットワークを構成する第１無線基地局における受信電力に対するバイアス値、前記ヘテロジニアスネットワークを構成する第２無線基地局が送信するサブフレームがミュートされる率、及び、前記第２無線基地局の送信電力のうち少なくとも一つを、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１４】
また、本発明は、前記最適化部が、ヘテロジニアスネットワークを構成する第１無線基地局の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群として変更することを特徴とする最適解検出装置である。
【００１５】
また、本発明は、前記最適化部が、タブーサーチ又は局所探索を実行することを特徴とする最適解検出装置である。
【００１６】
また、本発明は、コンピュータに、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する手順、を実行させるための最適解検出プログラムである。
【発明の効果】
【００１７】
本発明によれば、最適化部は、解が遷移した場合の直近の実行不可能解に対してのみ、前記第１パラメータ群を変更する。これにより、最適解検出装置は、実行可能解の最適解を短時間で検出することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態における、最適解検出装置の構成を示すブロック図である。
【図２】本発明の一実施形態における、ヘテロジニアスネットワークの構成例を示す図である。
【図３】本発明の一実施形態における、ＣＲＥを適用していない場合のカバレッジエリアの例を示す図である。
【図４】本発明の一実施形態における、ＣＲＥを適用した場合のカバレッジエリアの例を示す図である。
【図５】本発明の一実施形態における、最適化処理を行う対象エリアを示す地図の情報の例を示す図である。
【図６】本発明の一実施形態における、ＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルの例を示す表である。
【図７】本発明の一実施形態における、周波数帯域幅と、サブキャリア数と、ＲＢ数との関係の例を示す表である。
【図８】本発明の一実施形態における、ミューティング・サブフレームの例を示す図である。
【図９】本発明の一実施形態における、ミューティング・サブフレームの送信タイミングと、小型基地局の通信タイミングとの例を示す図である。
【図１０】本発明の一実施形態における、解が実行可能解から実行不可能解に遷移した場合の最適化処理の例を示す図である。
【図１１】本発明の一実施形態における、解が実行不可能解から実行可能解に遷移した場合の最適化処理の例を示す図である。
【図１２】本発明の一実施形態における、直近で得られた解が実行可能解である場合の近傍操作の例を示す図である。
【図１３】本発明の一実施形態における、費用に影響しないパラメータについての近傍操作の例を示す図である。
【図１４】本発明の一実施形態における、最適化処理の手順を表すフローチャートである。
【発明を実施するための形態】
【００１９】
本発明の一実施形態について図面を参照して詳細に説明する。図１には、最適解検出装置の構成がブロック図により示されている。また、図２には、ヘテロジニアスネットワークの構成例が示されている。
【００２０】
以下では、ヘテロジニアスネットワークの通信システムにＯＦＤＭＡ（Ｏｒｔｈｏｇｏｎａｌ Ｆｒｅｑｕｅｎｃｙ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）が用いられているものとして説明を続けるが、通信システムは、ＯＦＤＭＡに限らなくてよい。例えば、通信システムは、ＣＤＭＡ（Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）システムでもよい。
【００２１】
ヘテロジニアスネットワークは、無線基地局であるマクロ基地局４００及び小型基地局５００−ｐ（ｐは、１以上の整数）を含んで構成される。ここで、カバレッジエリア８００は、マクロ基地局４００によって既に構築されているものとする。また、マクロ基地局４００のカバレッジエリア８００には、複数の無線端末６００−ｍ（ｍは、１以上の整数）が存在可能であるものとする。
【００２２】
図３には、ＣＲＥを適用していない場合のカバレッジエリアの例が示されている。また、図４には、ＣＲＥを適用した場合のカバレッジエリアの例が示されている。ＣＲＥを適用した場合、無線端末６００−ｍは、カバレッジエリア８００に設置された小型基地局５００−ｐのうちから、通信接続する小型基地局を選択するため、小型基地局５００−ｐからの受信電力５１０に、予め定められたＣＲＥバイアス値を加算することで、ＣＲＥバイアス値が加算された受信電力５２０を算出する。
【００２３】
無線端末６００−ｍは、マクロ基地局４００からの受信電力４１０と、ＣＲＥバイアス値が加算された受信電力５２０とを比較し、最も受信電力が高い小型基地局５００−ｐに通信接続する。このようにして、例えば、小型基地局５００−１のカバレッジエリア９００−１は、予め定められたＣＲＥバイアス値に応じて、カバレッジエリア９１０−１に拡張される（カバレッジ拡張）。
【００２４】
したがって、小型基地局５００−１からの受信電力５１０が、マクロ基地局４００からの受信電力４１０よりも実際には小さいエリアに在る無線端末６００−ｍでも、その小型基地局は、ＣＲＥバイアス値に応じて、小型基地局５００−１に通信接続することとなる。このため、その小型基地局は、信号対干渉比（Ｓｉｇｎａｌ ｔｏ Ｉｎｔｅｒｆｅｒｅｎｃｅ Ｒａｔｉｏ：ＳＩＲ）が悪く、十分な通信速度を確保することが出来ない場合がある。そこで、信号対干渉比を改善するため、マクロ基地局４００は、通信を制限（ミューティング）する領域（サブフレーム）を、無線リソースの周波数方向又は時間方向に設ける。
【００２５】
以下、ミューティングするサブフレームを、「ミューティング・サブフレーム」という。また、ミューティングしないサブフレームを、「ノーマル・サブフレーム」という。また、予め定められたノーマル・サブフレーム数とミューティング・サブフレーム数との比率を、「ミューティング比率」という。
【００２６】
小型基地局５００−１は、ＣＲＥにより通信接続している無線端末６００−ｍと、マクロ基地局４００が通信を制限（ミューティング）しているタイミングに通信する。このため、ヘテロジニアスネットワークにおける置局設計では、トラヒック需要を収容し、且つ、費用（費用合計）が最小となる小型基地局５００−ｐの設置台数及び設置位置（最適解）を検出するだけでなく、ＣＲＥバイアス値及びミューティング比率が、最適に定められる必要がある。
【００２７】
図１に戻り、最適解検出装置の構成の説明を続ける。入力装置３００は、ヘテロジニアスネットワークの置局設計における条件を示す情報として、最適化処理を行う対象エリアにおいて収容すべきトラヒック需要を示す情報（トラヒック需要情報）を、最適解検出装置１００に入力する。以下では、最適化処理を行う対象エリアに１台のマクロ基地局４００による一つのカバレッジエリア８００があるものとして説明を続けるが、最適化処理を行う対象エリアには、複数のマクロ基地局４００のそれぞれによる、複数のカバレッジエリア８００が含まれていてもよい。
【００２８】
入力装置３００は、マクロ基地局４００の送信電力を示す情報、マクロ基地局４００のアンテナ高を示す情報、マクロ基地局４００のアンテナパターンを示す情報、小型基地局５００−ｐの装置費用及び設置費用を示す情報、マクロ基地局４００の周波数帯を示す情報、カバレッジエリア８００の範囲を示す情報、ＢＩＮのサイズを示す情報、伝搬ロスのモデル式を示す情報、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータを、最適解検出装置１００に入力してもよい。ＭＣＳテーブルデータの詳細については、図６を用いて後述する。
【００２９】
また、入力装置３００は、小型基地局５００−ｐの最適な設置台数及び設置位置（実行可能解）を検出する最適化処理におけるパラメータ及び終了条件（閾値）を、最適解検出装置１００に入力してもよい。また、入力装置３００は、カバレッジエリア８００を含む地図の情報、ＢＩＮ毎の土地区分情報、及び、カバレッジエリア８００に対するトラヒック需要情報又はその予測情報を、最適解検出装置１００に入力する。また、入力装置３００は、地図の情報に含まれる範囲における、建物高データ、及び土地の標高データを、最適解検出装置１００に入力してもよい。
【００３０】
次に、最適解検出装置１００の概要について説明する。
最適解検出装置１００は、ヘテロジニアスネットワークを構成する小型基地局５００−ｐの最適な設置台数及び設置位置、並びに、最適なＣＲＥバイアス値及びミューティング比率を定める。ここで、最適な設置台数及び設置位置とは、ヘテロジニアスネットワークがトラヒック需要を収容し、且つ、小型基地局５００−ｐを設置するために必要な費用合計が最小となる、設置台数及び設置位置である。なお、最適解検出装置１００は、小型基地局５００−ｐの送信電力及びアンテナチルト角等を定めてもよい。
【００３１】
最適解検出装置１００は、領域設定部１１０と、特性算出部１２０と、記憶部１３０と、最適化部１４０と、出力部１５０とを備える。領域設定部１１０には、地図の情報と、ＢＩＮのサイズを示す情報とが、入力装置２００から入力される。領域設定部１１０は、ＢＩＮのサイズで地図をメッシュ状に分割することにより、複数のＢＩＮを地図に定める。図５には、最適化処理を行う対象エリアを示す地図の情報の例が表されている。図５では、一例として、１５×１５個の矩形状のＢＩＮにより、地図が分割されている。
【００３２】
領域設定部１１０には、トラヒック需要情報又はトラヒック需要予測情報が、入力装置３００から入力される。領域設定部１１０は、地図に定めたＢＩＮに基づいて、トラヒック需要（積算値）をＢＩＮ毎に算出する。領域設定部１１０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報とを、記憶部１３０に記憶させる。
【００３３】
また、領域設定部１１０には、ＢＩＮ毎の土地区分情報が、入力装置３００から入力される。ここで、土地区分情報とは、例えば、住宅地、森林などの区分情報であり、ＢＩＮにおいて最も面積率が高い土地区分が、そのＢＩＮの土地区分情報と定められる。領域設定部１１０は、ＢＩＮ毎の土地区分情報に基づいて、小型基地局５００−ｐの設置費用をＢＩＮ毎に定め、小型基地局５００−ｐのＢＩＮ毎の設置費用を記憶部１３０に記憶させる。
【００３４】
特性算出部１２０には、伝搬ロスのモデル式を示す情報が、入力装置２００から入力される。また、特性算出部１２０は、カバレッジエリア８００を含む地図の情報を、記憶部１３０から読み出す。特性算出部１２０は、伝搬ロスのモデル式を示す情報と、カバレッジエリア８００を含む地図の情報とに基づいて、マクロ基地局４００から送出された電波の伝搬ロスを、ＢＩＮ毎に算出する。また、特性算出部１２０は、算出した伝搬ロスを示す情報をマクロ基地局４００及びＢＩＮに対応付けて、記憶部１３０に記憶させる。
【００３５】
記憶部１３０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報と、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報と、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータと、ＭＣＳテーブルデータと、小型基地局５００−ｐのＢＩＮ毎の設置費用と、小型基地局５００−ｐの装置費用とを記憶する。
【００３６】
最適化部１４０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報と、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報と、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータと、ＭＣＳテーブルデータと、小型基地局５００−ｐのＢＩＮ毎の設置費用と、小型基地局５００−ｐの装置費用とを記憶部１３０から読み出す。
【００３７】
最適化部１４０は、カバレッジエリア８００（図２を参照）のトラヒック需要を収容可能であり、且つ、小型基地局５００−ｐの費用合計が最小となる、小型基地局５００−ｐの最適な設置台数及び設置位置と、最適なＣＲＥバイアス値及びミューティング比率とを検出する。また、最適化部１４０は、小型基地局５００−ｐの最適な送信電力及びチルト角を検出してもよい。最適化部１４０は、例えば、タブーサーチ（タブー探索）又は局所探索といったヒューリスティック（試行錯誤）な最適化手法により、これらを検出する。
【００３８】
以下では、ｉは、ＢＩＮの識別子を表す。また、その集合は、Ｉと表記される。また、ｊは、マクロ基地局４００の設置位置の識別子を表す。また、その集合は、Ｊと表記される。また、Ｉｊは、位置ｊに設置されたマクロ基地局４００にカバーされるＢＩＮｉの集合を表す。また、Ｔｘは、マクロ基地局４００の送信電力を表す。また、ｃは、小型基地局５００毎の装置費用（機器費用）を表す。また、ｃｊは、位置ｊに小型基地局５００を設置した場合における小型基地局５００毎の設置費用を表す。また、ｗｉは、ＢＩＮｉにおけるトラヒック需要値を表す。また、ηは、ノイズを表す。また、ｇｉｊは、ｊに設置されたマクロ基地局４００からＢＩＮｉまでの伝搬ロスを表す。また、ｄｉｊは、ＢＩＮｉに在る無線端末が、位置ｊに設置されたマクロ基地局４００に接続した場合に、無線リソースが全て割当てられたと仮定された場合のスループット値を表す。また、ｘｊの値が１である場合、ｘｊは、ｊに基地局が配置されていることを表す。一方、ｘｊの値が０である場合、ｘｊは、ｊに基地局が配置されていないことを表す。
【００３９】
最適化部１４０は、小型基地局５００−ｐの設置に関する費用合計を算出する。ここで、費用合計とは、小型基地局５００−ｐの装置費用と、小型基地局５００−ｐの設置費用との合計である。費用合計には、土地区分毎の設置費用の違いを反映させることができる。費用合計は、式（１）により示される。
【００４０】
【数１】
【００４１】
最適化部１４０は、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報とに基づいて、マクロ基地局４００から送出された電波の受信電力をＢＩＮ毎に算出する。
【００４２】
最適化部１４０は、地図の情報に示された範囲にマクロ基地局４００が複数在る場合、受信電力が最も高いマクロ基地局４００を、そのＢＩＮをカバーするマクロ基地局４００であると定める。
【００４３】
また、最適化部１４０は、地図の情報に示された範囲に含まれるマクロ基地局４００に対するトラヒック需要の負荷量を、マクロ基地局４００毎に算出する。ここで、最適化部１４０は、ＣＲＥバイアス値、ミューティング比率、及びＢＩＮ毎に算出したスループット値に基づいて、マクロ基地局４００に対するトラヒック需要の負荷量を算出する。
【００４４】
比較のため、まず、ＣＲＥバイアス値及びミューティング比率を考慮しない場合のトラヒック需要の負荷量の算出方法について説明する。
【００４５】
マクロ基地局４００に対する（収容される）トラヒック需要の負荷量は、ＢＩＮ毎に算出したスループット値に基づいて算出される。位置ｊに設置されたマクロ基地局４００にカバーされるＢＩＮｉの信号対干渉雑音比ＳＩＮＲｉｊは、式（２）により表される。
【００４６】
【数２】
【００４７】
ここで、式（２）の分母の第1項は、他の基地局からの干渉を表す。また、式（２）の分母の第２項は、雑音成分を表す。
【００４８】
また、マクロ基地局４００のカバレッジエリア８００に含まれるＢＩＮ毎のスループット値は、ＢＩＮ毎の信号対干渉雑音比（ＳＩＮＲ）に基づいて算出される。より具体的には、ＢＩＮ毎のスループット値は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータに基づいて算出される。
【００４９】
信号対干渉雑音比−パケットエラーレート変換テーブルには、信号対干渉雑音比と、パケットエラーレートとが対応付けられて登録されている。また、ＭＣＳテーブルには、変調方式と、符号化率と、ＳＩＮＲ閾値とが対応付けられて登録されている。図６には、ＭＣＳテーブルの例が示されている。変調方式には、例えば、ＱＰＳＫ (２)、１６ＱＡＭ (４)及び６４ＱＡＭ (６)がある。
【００５０】
以下、下り方向の通信にＯＦＤＭＡを採用するＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）を例に、スループット値の算出方法を説明する。ＬＴＥでは、時間×周波数の無線リソースは、リソースブロック（Ｒｅｓｏｕｒｃｅ Ｂｌｏｃｋ，ＲＢ）単位で構成されている。また、リソースブロックは、７ＯＦＤＭシンボル（０．５［ｍｓ］）×１２サブキャリアで構成されている。１リソースブロックにより送信可能であるビット数は、式（３）により表わされる。
【００５１】
【数３】
【００５２】
式（３）において、[ＭＩＭＯ ｅｆｆｉｃｉｅｎｃｙ] は、そのＢＩＮにおけるＭＩＭＯの効率を表す。また、[Ｍｏｄｕｌａｔｉｏｎ]は、変調方式（図６を参照）を表す。また、 [Ｃｏｄｉｎｇ ｒａｔｅ]は、符号化率を表す。また、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]は、１リソースブロックあたりのサブキャリア数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝１２とする。また、[＃ ｏｆ ＯＦＤＭ ｓｙｍｂｏｌ／ＲＢ]は、１リソースブロックあたりのＯＦＤＭシンボル数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝７とする。また、ＰＥＲは、パケットエラーレートを表す。ＰＥＲは、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルにより、ＳＩＮＲ値を用いて算出される。
【００５３】
１リソースブロックは０．５［ｍｓ］であることから、対象とするシステムの周波数方向のリソースブロック数を＃ＲＢとして、位置ｊに設置されたマクロ基地局４００がカバーするＢＩＮｉに、リソースブロックが全て割り当てられた場合、スループットｄｉｊは、式（４）により表される。
【００５４】
【数４】
【００５５】
なお、割り当てられるリソースブロックは、その個数（リソース量）が制限されてもよい。例えば、フェージング等の変動要因に対するマージンとして、全無線リソースの８０［％］まで無線リソースが割り当てられるようにする場合、式（４）の＃ＲＢは、例えば、０．８×＃ＲＢに置き換えられてもよい。
【００５６】
図７には、周波数帯域幅と、サブキャリア数と、ＲＢ数との関係の例が示されている。 周波数方向のリソースブロック数は、対象とするシステムの周波数帯域幅に依存する。例えば、ＬＴＥでは、周波数帯域幅１．４［ＭＨｚ］に対応するサブキャリア数は、７６であり、対応するリソースブロック数は、６である。
【００５７】
位置ｊに設置されたマクロ基地局４００がカバーするＢＩＮｉに対して必要な無線リソース量の割合は、式（５）により表される。
【００５８】
【数５】
【００５９】
また、以下に示す式（６）の値が1以下である場合、そのことは、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全て収容することができることを表す。
【００６０】
【数６】
【００６１】
一方、式（６）の値が1を超えている場合、そのことは、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全ては収容することができないことを表す。したがって、マクロ基地局４００に対するトラヒック需要の負荷量の条件式は、式（７）により表される。
【００６２】
【数７】
【００６３】
ここで、ξは、カバレッジエリア８００の各ＢＩＮにおいて収容されるべきトラヒック需要の比率（０＜ξ≦１）を表す係数である。なお、ξの値は、パラメータとして予め定められているものとする。
【００６４】
式（６）の値が1以下である場合、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００は全て収容することができる、と判定される。
【００６５】
一方、式（６）の値が1を超えている場合、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全ては収容することができない、と判定される。
【００６６】
以上に説明した、ＣＲＥバイアス値及びミューティング比率を考慮しない場合に対し、最適化部１４０は、ＣＲＥバイアス値、ミューティング比率、及びＢＩＮ毎に算出したスループット値に基づいて、マクロ基地局４００に対するトラヒック需要の負荷量を、以下のように算出する。ここで、ＣＲＥバイアス値は、小型基地局５００−ｐに対して定められるパラメータである。また、時間方向の干渉を回避するためのミューティング比率は、マクロ基地局４００に対して定められるパラメータである。
【００６７】
図８には、ミューティング・サブフレームの例が示されている。ミューティング・サブフレームによるミューティング比率は、全てのマクロ基地局４００で共通であるものとする。つまり、ノーマル・サブフレームの送信タイミング、及び、ミューティング・サブフレームの送信タイミングは、全てのマクロ基地局４００で同期しているものとする。
【００６８】
ＣＲＥバイアス値及びミューティング比率を考慮した場合の信号対干渉雑音比（ＳＩＮＲ）は、各マクロ基地局４００に対する干渉源が小型基地局５００及び他のマクロ基地局４００であるため、ＣＲＥバイアス値及びミューティング比率を考慮しない場合の信号対干渉雑音比（ＳＩＮＲ）と同じである。したがって、ＣＲＥバイアス値及びミューティング比率を考慮した場合の信号対干渉雑音比（ＳＩＮＲ）は、上記の式（２）により表される。
【００６９】
マクロ基地局４００は、ミューティング・サブフレーム（＝オールモスト・ブランク・サブフレーム（Ａｌｍｏｓｔ Ｂｌａｎｋ Ｓｕｂｆｒａｍｅｓ））に、所定データを含めて送信しないよう通信を制限する。したがって、位置ｊに設置されたマクロ基地局４００によりカバーされるＢＩＮｉに対する全てのリソースブロック（ＲＢ）に、ノーマル・サブフレームを割り当てた場合、ＢＩＮ毎のスループット値は、式（８）により表される。
【００７０】
【数８】
【００７１】
以上より、ミューティング比率を考慮した場合における、マクロ基地局４００の負荷量は、式（９）により表される。
【００７２】
【数９】
【００７３】
一方、小型基地局５００−ｐは、ノーマル・サブフレームの送信タイミングと、ミューティング・サブフレームの送信タイミングとの両方で、無線端末６００−ｍと通信する。図９には、ミューティング・サブフレームの送信タイミングと、小型基地局の通信タイミングとの例が示されている。図９では、一例として、マクロ基地局４００のトラヒックと、小型基地局５００−１のトラヒックとが示されている。
【００７４】
小型基地局５００−１は、ＣＲＥによらずに通信接続している無線端末６００−ｍと、ノーマル・サブフレームの送信タイミング及びミューティング・サブフレームの送信タイミングで通信する。また、小型基地局５００−１は、ＣＲＥにより通信接続している無線端末６００−ｍとも、ノーマル・サブフレームの送信タイミング及びミューティング・サブフレームの送信タイミングで通信する。
【００７５】
また、小型基地局５００にカバーされたＢＩＮにおける信号対干渉雑音比（ＳＩＮＲ）は、ノーマル・サブフレームに対する干渉源と、ミューティング・サブフレームに対する干渉源とが異なるため、サブフレームの種別毎に算出される。
【００７６】
具体的には、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局のみを干渉源として算出される。一方、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局５００−ｐ及びマクロ基地局４００を干渉源として算出される。
【００７７】
位置ｊに設置された小型基地局５００（ピコ基地局）にカバーされるＢＩＮｉに対して、ミューティング・サブフレームの全てのリソースブロック（ＲＢ）を割り当てた場合のスループット値ｄｉｊｐｉｃｏ（ｍｕｔｅ）、及びノーマル・サブフレームの全てのリソースブロック（ＲＢ）を割り当てた場合のスループット値ｄｉｊｐｉｃｏ（ｎｏｒｍａｌ）は、それぞれ式（１０）により表される。
【００７８】
【数１０】
【００７９】
以上より、ＢＩＮｉのスループット値ｄｉｊｐｉｃｏは、式（１１）により表される。
【００８０】
【数１１】
【００８１】
よって、ミューティング比率を考慮した場合の小型基地局５００のトラヒック需要の負荷量は、式（１２）により表される。
【００８２】
【数１２】
【００８３】
また、小型基地局５００−１が、ＣＲＥによらずに通信接続している無線端末６００−ｍとはノーマル・サブフレームの送信タイミングで通信し、且つ、ＣＲＥにより通信接続している無線端末６００−ｍとはミューティング・サブフレームの送信タイミングで通信する、と仮定することにより（図９を参照）、小型基地局５００のトラヒック需要の負荷量は、以下のように算出されてもよい。
【００８４】
小型基地局５００にカバーされたＢＩＮにおける信号対干渉雑音比（ＳＩＮＲ）は、ノーマル・サブフレームに対する干渉源と、ミューティング・サブフレームに対する干渉源とが異なるため、サブフレームの種別毎に算出される。
【００８５】
具体的には、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局のみを干渉源として算出される。ここで、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、小型基地局５００がＣＲＥによりカバーするＢＩＮのみを対象に算出される。一方、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局５００及びマクロ基地局４００を干渉源として算出される。ここで、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、小型基地局５００がＣＲＥによらずにカバーするＢＩＮを対象に算出される。
【００８６】
したがって、スループット値、及びトラヒック需要の負荷量は、小型基地局５００がＣＲＥによりカバーするＢＩＮと、小型基地局５００がＣＲＥによらずにカバーするＢＩＮとに分けて、それぞれ算出される。
【００８７】
以下、位置ｊに設置された小型基地局５００がカバーするＢＩＮｉのうち、小型基地局５００がＣＲＥによりカバーするＢＩＮの集合を、Ｉｊ，ＣＲＥＢＩＮと表記する。また、小型基地局５００がＣＲＥによらずにカバーするＢＩＮの集合を、Ｉｊ，ｎｏｒｍａｌＢＩＮと表記する。
【００８８】
ＢＩＮの集合Ｉｊ，ＣＲＥＢＩＮを構成するＢＩＮｉに対して、ミューティング・サブフレームの全てのリソースブロックを割り当てた場合、スループット値ｄｉｊｐｉｃｏ（ｍｕｔｅ）は、式（１３）により表される。
【００８９】
【数１３】
【００９０】
一方、ＢＩＮの集合Ｉｊ，ｎｏｒｍａｌＢＩＮを構成するＢＩＮｉに対して、ノーマル・サブフレームの全てのリソースブロックを割り当てた場合、スループット値ｄｉｊｐｉｃｏ（ｎｏｒｍａｌ）は、式（１４）により表される。
【００９１】
【数１４】
【００９２】
以上より、ＣＲＥバイアス値及びミューティング比率を考慮した場合の小型基地局５００に対するトラヒック需要の負荷量は、式（１５）により表される。
【００９３】
【数１５】
【００９４】
式（１５）に表された二つの式のうち、いずれか一方の式でも値が１以上である場合、最適化部１４０は、その小型基地局５００がオーバロードしている、すなわち、その小型基地局５００のトラヒック需要を、その小型基地局５００が全ては収容することができない、と判定する。
【００９５】
タブーサーチ又は局所探索による最適化処理によって最適化される予め定められたパラメータ群には、費用に影響するパラメータ群と、費用に影響しないパラメータ群（トラヒック需要に影響するパラメータ群）とがある。費用に影響するパラメータには、例えば、小型基地局５００の設置台数、及び小型基地局５００の設置位置がある。一方、費用に影響しないパラメータ群（トラヒック需要に影響するパラメータ群）には、例えば、ＣＲＥバイアス値、ミューティング比率、小型基地局５００の送信電力、及び小型基地局５００のチルト角がある。
【００９６】
費用に影響するパラメータを変更する段階と、費用に影響しないパラメータのみを変更する段階との２段階に分けて、タブーサーチ又は局所探索による最適化処理を実行する。
【００９７】
以下、最適化処理における予め定められた制約条件を満たす、費用に影響するパラメータ値と、費用に影響しないパラメータ値との組を、「実行可能解」という。また、最適化処理における予め定められた制約条件を満たさない、費用に影響するパラメータ値と、費用に影響しないパラメータ値との組を、「実行不可能解」という。ここで、予め定められた制約条件とは、例えば、所要の受信電力、所要の信号対干渉雑音比（所要ＳＩＮＲ）、及び、収容すべきトラヒック需要（トラヒック量）を満たすという条件である。
【００９８】
最適化部１４０は、直近で得られた解（現在の解）が実行可能解であるか又は実行不可能解であるかに応じて、費用に影響するパラメータを変更する最適化処理を主に実行する。
【００９９】
図１０には、解が実行可能解から実行不可能解に遷移した場合の最適化処理の例が示されている。直近で得られた解が実行可能解である場合、最適化部１４０は、費用に影響するパラメータを変更することにより、小型基地局５００の設置費用が少なくなる方向に、探索を進める。ここで、小型基地局５００の設置費用が少なくなる方向に探索を進めることにより、直近で得られた解が実行不可能解（図１０では、１と表記されている解）になったとする。最適化部１４０は、この実行不可能解に対して、費用に影響するパラメータを固定し、且つ、費用に影響しないパラメータを変更することにより、直近で得られた解が実行可能解（図１０では、２と表記されている解）となるか否かを判定する。
【０１００】
一方、図１１には、解が実行不可能解から実行可能解に遷移した場合の最適化処理の例が示されている。直近で得られた解が実行不可能解である場合、最適化部１４０は、費用に影響するパラメータである「小型基地局５００の設置台数」を追加又は削除することにより、実行可能解を探索する。ここで、小型基地局５００の設置台数を追加したことにより、直近で得られた解が実行不可能解から実行可能解（図１１では、１と表記されている解）に遷移したとする。最適化部１４０は、小型基地局５００の設置台数を追加する前の直近の実行不可能解（図１１では、０と表記されている解）に対して、費用に影響しないパラメータを変更することにより、実行可能解（図１１では、２と表記されている解）となるか否かを判定する。
【０１０１】
このようにして、最適化部１４０は、直近で得られた解が実行可能解である場合と、直近で得られた解が実行不可能解である場合とに応じて、上記の最適化処理（操作）を繰り返すことにより、実行可能解の最適解を検出する。
【０１０２】
次に、費用に影響するパラメータを変更する最適化処理の例を説明する。
最適化部１４０は、費用に影響するパラメータを変更する最適化処理として、例えば、タブーサーチを実行する。
【０１０３】
ここで、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第１指標は、収容すべきトラヒック需要（所要収容トラヒック量）から、直近で得られた解により収容可能であるトラヒック需要（現在の収容トラヒック量）を減算した値である。但し、この減算結果が負値である場合、第１指標は値０とされる。また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第２指標は、小型基地局５００−ｐの設置費用である。また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第３指標は、カバレッジエリア８００（図２を参照）における、全ての基地局（マクロ基地局４００及び小型基地局５００−ｐ）に対するトラヒック需要の負荷量の総和である。
【０１０４】
また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第１〜第３指標は、辞書式順序（例えば、昇順、五十音順、アルファベット順）により、それぞれ予め配列されているものとする。
【０１０５】
最適化部１４０は、実行可能解の空間内だけでなく、実行不可能解の空間内に対しても、トラヒック需要の最適解の探索を実行する。このため、カバレッジエリア８００において収容すべきトラヒック需要を満たすことは、本実施形態における制約条件でないものとする。その代わり、本実施形態では、該制約条件は、上記の第１指標のように定められている。この場合、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たしている解が、元の最適化問題の実行可能解である。一方、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たさない解が、元の最適化問題の実行不可能解である。
【０１０６】
したがって、第１指標が値０となる本実施形態における実行可能解は、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たす解である。つまり、第１指標が値０となる本実施形態における実行可能解が得られなかった場合、このことは、カバレッジエリア８００（図２を参照）において収容すべきトラヒック需要を満たす解を得ることができなかったことを示す。ただし、この場合でも、最適化部１４０は、収容すべきトラヒック需要に可能な限りに近いトラヒック需要を満たす、小型基地局５００の設置台数及び設置位置、並びに、小型基地局５００毎のパラメータ（例えば、チルト角）を検出することができる。
【０１０７】
また、最適化部１４０は、第１指標の値が最も小さくなる解に対して小型基地局５００の費用合計が最小となる解を、さらに第２指標を探索することにより検出する。ここで、小型基地局５００の費用合計が最小となる解が複数ある場合、最適化部１４０は、収容すべきトラヒック需要を最も少ない負荷量で収容することができる解を、さらに第３指標を探索することにより検出する。これは、第１指標及び第２指標により定まった解の条件下において、ヘテロジニアスネットワーク（システム）が収容可能であるトラヒック需要が、最も大きくなる解を検出（選択）することを意味する。
【０１０８】
最適化部１４０は、直近で得られた解が実行可能解である場合と、直近で得られた解が実行不可能解である場合とで、異なる近傍操作を実行する。ここで、近傍操作には、タブーサーチにおける１回の探索に対し、実行可能な操作の上限数が定められる。例えば、近傍値＝１と定められた場合、最適化部１４０は、小型基地局５００の設置台数を新たに1台追加する操作、又は、小型基地局５００の設置台数を新たに1台削除する操作のどちらかを、1回だけ実行する。
【０１０９】
図１２には、直近で得られた解が実行可能解である場合の近傍操作の例が示されている。直近で得られた解（図１２では、ｎ−１（ｎは、１以上の整数）と表記されている解）が実行可能解であり、且つ、実行不可能解から実行可能解（図１２では、０と表記されている解）に遷移した以降に探索した回数が、予め定められた回数ｎ未満である場合、最適化部１４０は、小型基地局５００の設置台数を新たに追加する近傍操作のみを実行する。これにより、最適化部１４０は、局所的な解から脱し、探索する範囲を広げることができる。
【０１１０】
また、直近で得られた解（図１２では、ｎと表記されている解）が実行可能解であり、且つ、実行不可能解から実行可能解（図１２では、０と表記されている解）に遷移した以降に探索した回数が、予め定められた回数ｎ以上である場合、最適化部１４０は、小型基地局５００を新たに削除する近傍操作のみを実行する。これにより、最適化部１４０は、費用合計が最小となる解を探索することができる。
【０１１１】
一方、直近で得られた解が実行不可能解である場合、最適化部１４０は、直近で得られた解が実行可能解となるよう、小型基地局５００の設置台数を新たに追加する近傍操作、及び、小型基地局５００の設置台数を新たに削除する近傍操作のうち、少なくとも一方を実行する。
【０１１２】
次に、費用に影響しないパラメータを変更する最適化処理の例を説明する。
最適化部１４０は、費用に影響しないパラメータを変更する最適化処理として、例えば、局所探索法を実行する。
【０１１３】
ここで、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第１指標は、収容すべきトラヒック需要（所要収容トラヒック量）から、直近で得られた解により収容可能であるトラヒック需要（現在の収容トラヒック量）を減算した値である。ただし、この減算結果が負値である場合、第１指標は値０とされる。また、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第２指標は、カバレッジエリア８００（図２を参照）における、全ての基地局（マクロ基地局４００及び小型基地局５００−ｐ）に対するトラヒック需要の負荷量の総和である。
【０１１４】
また、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第１及び第２指標は、辞書式順序（例えば、昇順、五十音順、アルファベット順）により、それぞれ予め配列されているものとする。
【０１１５】
図１３には、費用に影響しないパラメータについての近傍操作の例が示されている。最適化部１４０は、直近で得られた解（図１３では、値Ｃ）を基準とする、目的関数の指標要素（離散値）に予め定められた範囲（図１３では、ｎ＝±２の場合、値Ａ〜値Ｅ）に対して、近傍操作を実行する。
【０１１６】
図１に戻り、最適解検出装置１００の構成の説明を続ける。出力部１５０は、記憶部１３０に記憶されている各種データに基づいて、小型基地局５００−ｐの最適な設置台数及び設置位置を示す情報を、地図（図５を参照）と共に画面に表示する。また、出力部１５０は、カバレッジエリア８００に含まれる各ＢＩＮ（メッシュ）を示す情報を、地図と共に画面に表示してもよい。
【０１１７】
次に、最適化処理の手順を説明する。
図１４は、最適化処理の手順を表すフローチャートである。最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか（収容すべきトラヒック需要を収容可能か）否かを判定する（ステップＳ１）。
【０１１８】
直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１−Ｙｅｓ）、最適化部１４０は、タブーサーチにおいて、予め定められた回数まで小型基地局５００の設置台数を追加したか否かを判定する（ステップＳ２）。
【０１１９】
予め定められた回数までは小型基地局５００を追加していない場合（ステップＳ２−Ｎｏ）、最適化部１４０は、小型基地局５００の設置台数を追加する近傍操作（局所的な解から脱し、探索する範囲を広げる操作）を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ３）。
【０１２０】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか（収容すべきトラヒック需要を収容可能か）否かを判定する（ステップＳ４）。直近で得られた解が、収容すべきトラヒック需要を満たさない場合（ステップＳ４−Ｎｏ）、最適化部１４０は、小型基地局５００の設置台数を追加した回数をカウントするための回数カウンタをリセットする（ステップＳ５）。
【０１２１】
最適化部１４０は、直近で得られた解に対して、費用に影響するパラメータを固定し、費用に影響しないパラメータを変更することにより、最適化処理を実行する（ステップＳ６）。最適化部１４０は、最適化処理により得られた解で、直近で得られた解を示す変数を更新する。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ７）。
【０１２２】
そして、最適化部１４０は、最適化処理について予め定められた終了条件を満たすか否かを判定する（ステップＳ８）。最適化処理について予め定められた終了条件を満たす場合（ステップＳ８−Ｙｅｓ）、最適化部１４０は、最適化処理を終了する。
【０１２３】
一方、ステップＳ１において、直近で得られた解が、収容すべきトラヒック需要を満たしていない場合（ステップＳ１−Ｎｏ）、最適化部１４０は、直近で得られた解を変数ＴＭＰに格納し、変数ＴＭＰを記憶部１３０に記憶させる（ステップＳ９）。
【０１２４】
最適化部１４０は、小型基地局５００の設置台数を追加及び削除する近傍操作を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１０）。
【０１２５】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか否かを判定する（ステップＳ１１）。直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１１−Ｙｅｓ）、最適化部１４０は、直近で得られた解が、小型基地局５００の設置台数を追加する近傍操作により得られた解であるか否かを判定する（ステップＳ１２）。
【０１２６】
直近で得られた解が、小型基地局５００の設置台数を追加する近傍操作により得られた解である場合（ステップＳ１２−Ｙｅｓ）、最適化部１４０は、変数ＴＭＰに対して、費用に影響するパラメータを固定し、費用に影響しないパラメータを変更することにより、最適化処理を実行する（ステップＳ１３）。
【０１２７】
最適化部１４０は、直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値以下であるか否かを判定する（ステップＳ１４）。直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値よりも大きい場合（ステップＳ１４−Ｎｏ）、最適化部１４０は、ステップＳ１３における最適化処理により得られた解で、直近で得られた解を示す変数を更新する。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１５）。そして、最適化部１４０は、ステップＳ８に処理を進める。
【０１２８】
また、ステップＳ２において、予め定められた回数まで小型基地局５００を追加している場合（ステップＳ２−Ｙｅｓ）、最適化部１４０は、小型基地局５００の設置台数を削除する近傍操作（費用合計が最小となる解を探索する操作）を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１６）。
【０１２９】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか否かを判定する（ステップＳ１７）。直近で得られた解が、収容すべきトラヒック需要を満たさない場合（ステップＳ１７−Ｎｏ）、最適化部１４０は、ステップＳ５に処理を進める。一方、直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１７−Ｙｅｓ）、最適化部１４０は、ステップＳ１６に処理を戻す。
【０１３０】
また、ステップＳ４において、直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ４−Ｙｅｓ）、最適化部１４０は、小型基地局５００の設置台数を追加した回数をカウントするための回数カウンタをリセットする（ステップＳ１８）。そして、最適化部１４０は、ステップＳ２に処理を戻す。
【０１３１】
また、ステップＳ１２において、直近で得られた解が、小型基地局５００の設置台数を追加する以外の近傍操作により得られた解である場合（ステップＳ１２−Ｙｅｓ）、最適化部１４０は、ステップＳ２に処理を戻す。また、ステップＳ１４において、直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値以下である場合（ステップＳ１４−Ｙｅｓ）、最適化部１４０は、ステップＳ８に処理を進める。また、ステップＳ８において、最適化処理について予め定められた終了条件を満たさない場合（ステップＳ８−Ｎｏ）、最適化部１４０は、ステップＳ１に処理を戻す。
【０１３２】
以上のように、最適解検出装置１００は、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する（費用に影響しない）第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより（図１０及び図１１を参照）、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部１４０を備える。
この構成により、最適化部１４０は、第１パラメータ群（費用に影響しないパラメータ群）と、第２パラメータ群（費用に影響するパラメータ群）とに分けられたパラメータに基づいて、解が遷移した場合の直近の実行不可能解に対してのみ、前記第１パラメータ群を変更する。これにより、最適解検出装置１００は、第１パラメータ群（費用に影響しないパラメータ群）を変更する最適化処理を必要最小限に抑え、実行可能解の最適解を短時間で検出することができる。また、最適解検出装置１００は、ヘテロジニアスネットワークに特有のパラメータであるＣＲＥバイアス値及びミューティング比率の最適値を得ることができる。
【０１３３】
また、最適化部１４０は、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群（費用に影響するパラメータ）を費用が増加する方向に変更（近傍操作）することにより、実行可能解の最適解を検出する（図１２を参照）。
この構成により、最適化部１４０は、近傍操作を実行する。これにより、最適解検出装置１００は、局所的な解から脱し、探索する範囲を広げることができ、実行可能解の最適解を短時間で検出することができる。
【０１３４】
また、最適化部１４０は、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用（費用合計）が最小となる最適解を検出する。
これにより、最適解検出装置１００は、トラヒック需要を収容し且つ費用（費用合計）が最小となる最適解を短時間で検出することができる。
【０１３５】
また、最適化部１４０は、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群（例えば、ＣＲＥバイアス値、ミューティング比率、小型基地局５００の送信電力、及び小型基地局５００のチルト角）を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３６】
また、最適化部１４０は、ヘテロジニアスネットワークを構成する第１無線基地局（小型基地局５００）における受信電力に対するバイアス値（ＣＲＥバイアス値）、前記ヘテロジニアスネットワークを構成する第２無線基地局（マクロ基地局４００）が送信するサブフレームがミュートされる率（ミューティング比率）、及び、前記第２無線基地局（マクロ基地局４００）の送信電力のうち少なくとも一つを、前記第１パラメータ群（例えば、費用に影響しないパラメータ群）として変更することにより、前記実行可能解の最適解を検出する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３７】
また、最適化部１４０は、ヘテロジニアスネットワークを構成する第１無線基地局（小型基地局５００）の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群（例えば、費用に影響するパラメータ）として変更する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３８】
また、最適化部１４０は、タブーサーチ（タブー探索）又は局所探索を実行する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３９】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【０１４０】
例えば、各ＢＩＮにおける受信信号強度及び干渉量、アンテナのチルト角などの基地局のパラメータ、並びに、所要の受信信号強度及びキャリア信号電力対干渉電力比（Ｃ／Ｉ）等を入力データとして、通信エリアを構築する対象とされた範囲に対し、例えば、所要の受信信号強度以上となるＢＩＮの個数を最大化（カバレッジ最大化）する等の置局設計における条件が満たされるように、最適解検出装置１００は、最適化処理を実行してもよい
【０１４１】
また、例えば、最適解検出装置１００は、入力装置３００から各種データを取得する代わりに、それら各種データを予め記憶するデータベース部を備えていてもよい。
【０１４２】
なお、以上に説明した最適解検出装置を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録し、そのプログラムをコンピュータシステムに読み込ませて実行するようにしてもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【０１４３】
１００…最適解検出装置、１１０…領域設定部、１２０…特性算出部、１３０…記憶部、１４０…最適化部、１５０…出力部、３００…入力装置、４００…マクロ基地局、４１０…受信電力曲線、５００…小型基地局、５１０…受信電力曲線、５２０…受信電力曲線、６００…無線端末、８００…カバレッジエリア、９００…小型基地局セル、９１０…小型基地局セル
【技術分野】
【０００１】
本発明は、最適解検出装置及び最適解検出プログラムに関する。
【背景技術】
【０００２】
無線通信システム、特に携帯電話に代表される移動体通信システムでは、通信エリアを実際に構築する前に、基地局を設置する位置を設計者が事前に検討する置局設計が行われる。置局設計では、通信エリアを構築する対象とされた範囲を含む地図が、予め定められたサイズの領域（以下、「ＢＩＮ」という）により複数に分割される。基地局を設置する位置は、これらＢＩＮ毎の受信電力等に基づいて、制約条件（例えば、トラヒック需要）を満たすよう検討される。
【０００３】
このような置局設計において、トラヒック需要を満たすマクロ基地局の配置と、そのパラメータの設定とを行うことを目的とした置局設計方法が、特許文献１に開示されている。
【０００４】
また、近年、スマートフォンなどの登場により、移動体通信システムのトラヒック需要は、急激な増加傾向にある。そこで、マクロ基地局のカバレッジエリア内のＢＩＮに、送信電力が小さい小型基地局をさらに設置することによって、マクロ基地局の負荷を分散することができる「ヘテロジニアスネットワーク（Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｎｅｔｗｏｒｋ：ＨｅｔＮｅｔ）」が注目されている。
【０００５】
さらに、ヘテロジニアスネットワークにおいて、より高い負荷分散効果を得るための技術として、Ｃｅｌｌ Ｒａｎｇｅ Ｅｘｐａｎｓｉｏｎ（ＣＲＥ）が検討されている。ＣＲＥのパラメータの一つである、受信電力に対するバイアス（以下、「ＣＲＥバイアス」という）に応じて、小型基地局がカバレッジエリアを拡大することにより、ヘテロジニアスネットワークは、より高い負荷分散効果を得る。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２０１２６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に開示された置局設計方法では、ヘテロジニアスネットワークに特有であるＣＲＥのパラメータは、まったく考慮されていない。このため、特許文献１に開示された様な置局設計方法により定められるパラメータに、例えば、ＣＲＥのパラメータ等が追加された場合、トラヒック需要を収容し且つ費用が最小となる実行可能解の最適解を検出するための処理時間は、指数関数的に増加してしまうという問題がある。
【０００８】
本発明は、前記の点に鑑みてなされたものであり、実行可能解の最適解を短時間で検出することができる最適解検出装置及び最適解検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、上記の課題を解決するためになされたものであり、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部、を備えることを特徴とする最適解検出装置である。
【００１０】
また、本発明は、前記最適化部が、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群を費用が増加する方向に変更することにより、実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１１】
また、本発明は、前記最適化部が、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用が最小となる最適解を検出することを特徴とする最適解検出装置である。
【００１２】
また、本発明は、前記最適化部が、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１３】
また、本発明は、前記最適化部が、ヘテロジニアスネットワークを構成する第１無線基地局における受信電力に対するバイアス値、前記ヘテロジニアスネットワークを構成する第２無線基地局が送信するサブフレームがミュートされる率、及び、前記第２無線基地局の送信電力のうち少なくとも一つを、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする最適解検出装置である。
【００１４】
また、本発明は、前記最適化部が、ヘテロジニアスネットワークを構成する第１無線基地局の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群として変更することを特徴とする最適解検出装置である。
【００１５】
また、本発明は、前記最適化部が、タブーサーチ又は局所探索を実行することを特徴とする最適解検出装置である。
【００１６】
また、本発明は、コンピュータに、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する手順、を実行させるための最適解検出プログラムである。
【発明の効果】
【００１７】
本発明によれば、最適化部は、解が遷移した場合の直近の実行不可能解に対してのみ、前記第１パラメータ群を変更する。これにより、最適解検出装置は、実行可能解の最適解を短時間で検出することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態における、最適解検出装置の構成を示すブロック図である。
【図２】本発明の一実施形態における、ヘテロジニアスネットワークの構成例を示す図である。
【図３】本発明の一実施形態における、ＣＲＥを適用していない場合のカバレッジエリアの例を示す図である。
【図４】本発明の一実施形態における、ＣＲＥを適用した場合のカバレッジエリアの例を示す図である。
【図５】本発明の一実施形態における、最適化処理を行う対象エリアを示す地図の情報の例を示す図である。
【図６】本発明の一実施形態における、ＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルの例を示す表である。
【図７】本発明の一実施形態における、周波数帯域幅と、サブキャリア数と、ＲＢ数との関係の例を示す表である。
【図８】本発明の一実施形態における、ミューティング・サブフレームの例を示す図である。
【図９】本発明の一実施形態における、ミューティング・サブフレームの送信タイミングと、小型基地局の通信タイミングとの例を示す図である。
【図１０】本発明の一実施形態における、解が実行可能解から実行不可能解に遷移した場合の最適化処理の例を示す図である。
【図１１】本発明の一実施形態における、解が実行不可能解から実行可能解に遷移した場合の最適化処理の例を示す図である。
【図１２】本発明の一実施形態における、直近で得られた解が実行可能解である場合の近傍操作の例を示す図である。
【図１３】本発明の一実施形態における、費用に影響しないパラメータについての近傍操作の例を示す図である。
【図１４】本発明の一実施形態における、最適化処理の手順を表すフローチャートである。
【発明を実施するための形態】
【００１９】
本発明の一実施形態について図面を参照して詳細に説明する。図１には、最適解検出装置の構成がブロック図により示されている。また、図２には、ヘテロジニアスネットワークの構成例が示されている。
【００２０】
以下では、ヘテロジニアスネットワークの通信システムにＯＦＤＭＡ（Ｏｒｔｈｏｇｏｎａｌ Ｆｒｅｑｕｅｎｃｙ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）が用いられているものとして説明を続けるが、通信システムは、ＯＦＤＭＡに限らなくてよい。例えば、通信システムは、ＣＤＭＡ（Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）システムでもよい。
【００２１】
ヘテロジニアスネットワークは、無線基地局であるマクロ基地局４００及び小型基地局５００−ｐ（ｐは、１以上の整数）を含んで構成される。ここで、カバレッジエリア８００は、マクロ基地局４００によって既に構築されているものとする。また、マクロ基地局４００のカバレッジエリア８００には、複数の無線端末６００−ｍ（ｍは、１以上の整数）が存在可能であるものとする。
【００２２】
図３には、ＣＲＥを適用していない場合のカバレッジエリアの例が示されている。また、図４には、ＣＲＥを適用した場合のカバレッジエリアの例が示されている。ＣＲＥを適用した場合、無線端末６００−ｍは、カバレッジエリア８００に設置された小型基地局５００−ｐのうちから、通信接続する小型基地局を選択するため、小型基地局５００−ｐからの受信電力５１０に、予め定められたＣＲＥバイアス値を加算することで、ＣＲＥバイアス値が加算された受信電力５２０を算出する。
【００２３】
無線端末６００−ｍは、マクロ基地局４００からの受信電力４１０と、ＣＲＥバイアス値が加算された受信電力５２０とを比較し、最も受信電力が高い小型基地局５００−ｐに通信接続する。このようにして、例えば、小型基地局５００−１のカバレッジエリア９００−１は、予め定められたＣＲＥバイアス値に応じて、カバレッジエリア９１０−１に拡張される（カバレッジ拡張）。
【００２４】
したがって、小型基地局５００−１からの受信電力５１０が、マクロ基地局４００からの受信電力４１０よりも実際には小さいエリアに在る無線端末６００−ｍでも、その小型基地局は、ＣＲＥバイアス値に応じて、小型基地局５００−１に通信接続することとなる。このため、その小型基地局は、信号対干渉比（Ｓｉｇｎａｌ ｔｏ Ｉｎｔｅｒｆｅｒｅｎｃｅ Ｒａｔｉｏ：ＳＩＲ）が悪く、十分な通信速度を確保することが出来ない場合がある。そこで、信号対干渉比を改善するため、マクロ基地局４００は、通信を制限（ミューティング）する領域（サブフレーム）を、無線リソースの周波数方向又は時間方向に設ける。
【００２５】
以下、ミューティングするサブフレームを、「ミューティング・サブフレーム」という。また、ミューティングしないサブフレームを、「ノーマル・サブフレーム」という。また、予め定められたノーマル・サブフレーム数とミューティング・サブフレーム数との比率を、「ミューティング比率」という。
【００２６】
小型基地局５００−１は、ＣＲＥにより通信接続している無線端末６００−ｍと、マクロ基地局４００が通信を制限（ミューティング）しているタイミングに通信する。このため、ヘテロジニアスネットワークにおける置局設計では、トラヒック需要を収容し、且つ、費用（費用合計）が最小となる小型基地局５００−ｐの設置台数及び設置位置（最適解）を検出するだけでなく、ＣＲＥバイアス値及びミューティング比率が、最適に定められる必要がある。
【００２７】
図１に戻り、最適解検出装置の構成の説明を続ける。入力装置３００は、ヘテロジニアスネットワークの置局設計における条件を示す情報として、最適化処理を行う対象エリアにおいて収容すべきトラヒック需要を示す情報（トラヒック需要情報）を、最適解検出装置１００に入力する。以下では、最適化処理を行う対象エリアに１台のマクロ基地局４００による一つのカバレッジエリア８００があるものとして説明を続けるが、最適化処理を行う対象エリアには、複数のマクロ基地局４００のそれぞれによる、複数のカバレッジエリア８００が含まれていてもよい。
【００２８】
入力装置３００は、マクロ基地局４００の送信電力を示す情報、マクロ基地局４００のアンテナ高を示す情報、マクロ基地局４００のアンテナパターンを示す情報、小型基地局５００−ｐの装置費用及び設置費用を示す情報、マクロ基地局４００の周波数帯を示す情報、カバレッジエリア８００の範囲を示す情報、ＢＩＮのサイズを示す情報、伝搬ロスのモデル式を示す情報、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータを、最適解検出装置１００に入力してもよい。ＭＣＳテーブルデータの詳細については、図６を用いて後述する。
【００２９】
また、入力装置３００は、小型基地局５００−ｐの最適な設置台数及び設置位置（実行可能解）を検出する最適化処理におけるパラメータ及び終了条件（閾値）を、最適解検出装置１００に入力してもよい。また、入力装置３００は、カバレッジエリア８００を含む地図の情報、ＢＩＮ毎の土地区分情報、及び、カバレッジエリア８００に対するトラヒック需要情報又はその予測情報を、最適解検出装置１００に入力する。また、入力装置３００は、地図の情報に含まれる範囲における、建物高データ、及び土地の標高データを、最適解検出装置１００に入力してもよい。
【００３０】
次に、最適解検出装置１００の概要について説明する。
最適解検出装置１００は、ヘテロジニアスネットワークを構成する小型基地局５００−ｐの最適な設置台数及び設置位置、並びに、最適なＣＲＥバイアス値及びミューティング比率を定める。ここで、最適な設置台数及び設置位置とは、ヘテロジニアスネットワークがトラヒック需要を収容し、且つ、小型基地局５００−ｐを設置するために必要な費用合計が最小となる、設置台数及び設置位置である。なお、最適解検出装置１００は、小型基地局５００−ｐの送信電力及びアンテナチルト角等を定めてもよい。
【００３１】
最適解検出装置１００は、領域設定部１１０と、特性算出部１２０と、記憶部１３０と、最適化部１４０と、出力部１５０とを備える。領域設定部１１０には、地図の情報と、ＢＩＮのサイズを示す情報とが、入力装置２００から入力される。領域設定部１１０は、ＢＩＮのサイズで地図をメッシュ状に分割することにより、複数のＢＩＮを地図に定める。図５には、最適化処理を行う対象エリアを示す地図の情報の例が表されている。図５では、一例として、１５×１５個の矩形状のＢＩＮにより、地図が分割されている。
【００３２】
領域設定部１１０には、トラヒック需要情報又はトラヒック需要予測情報が、入力装置３００から入力される。領域設定部１１０は、地図に定めたＢＩＮに基づいて、トラヒック需要（積算値）をＢＩＮ毎に算出する。領域設定部１１０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報とを、記憶部１３０に記憶させる。
【００３３】
また、領域設定部１１０には、ＢＩＮ毎の土地区分情報が、入力装置３００から入力される。ここで、土地区分情報とは、例えば、住宅地、森林などの区分情報であり、ＢＩＮにおいて最も面積率が高い土地区分が、そのＢＩＮの土地区分情報と定められる。領域設定部１１０は、ＢＩＮ毎の土地区分情報に基づいて、小型基地局５００−ｐの設置費用をＢＩＮ毎に定め、小型基地局５００−ｐのＢＩＮ毎の設置費用を記憶部１３０に記憶させる。
【００３４】
特性算出部１２０には、伝搬ロスのモデル式を示す情報が、入力装置２００から入力される。また、特性算出部１２０は、カバレッジエリア８００を含む地図の情報を、記憶部１３０から読み出す。特性算出部１２０は、伝搬ロスのモデル式を示す情報と、カバレッジエリア８００を含む地図の情報とに基づいて、マクロ基地局４００から送出された電波の伝搬ロスを、ＢＩＮ毎に算出する。また、特性算出部１２０は、算出した伝搬ロスを示す情報をマクロ基地局４００及びＢＩＮに対応付けて、記憶部１３０に記憶させる。
【００３５】
記憶部１３０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報と、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報と、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータと、ＭＣＳテーブルデータと、小型基地局５００−ｐのＢＩＮ毎の設置費用と、小型基地局５００−ｐの装置費用とを記憶する。
【００３６】
最適化部１４０は、ＢＩＮ毎のトラヒック需要値を示す情報と、カバレッジエリア８００を含む地図の情報と、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報と、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータと、ＭＣＳテーブルデータと、小型基地局５００−ｐのＢＩＮ毎の設置費用と、小型基地局５００−ｐの装置費用とを記憶部１３０から読み出す。
【００３７】
最適化部１４０は、カバレッジエリア８００（図２を参照）のトラヒック需要を収容可能であり、且つ、小型基地局５００−ｐの費用合計が最小となる、小型基地局５００−ｐの最適な設置台数及び設置位置と、最適なＣＲＥバイアス値及びミューティング比率とを検出する。また、最適化部１４０は、小型基地局５００−ｐの最適な送信電力及びチルト角を検出してもよい。最適化部１４０は、例えば、タブーサーチ（タブー探索）又は局所探索といったヒューリスティック（試行錯誤）な最適化手法により、これらを検出する。
【００３８】
以下では、ｉは、ＢＩＮの識別子を表す。また、その集合は、Ｉと表記される。また、ｊは、マクロ基地局４００の設置位置の識別子を表す。また、その集合は、Ｊと表記される。また、Ｉｊは、位置ｊに設置されたマクロ基地局４００にカバーされるＢＩＮｉの集合を表す。また、Ｔｘは、マクロ基地局４００の送信電力を表す。また、ｃは、小型基地局５００毎の装置費用（機器費用）を表す。また、ｃｊは、位置ｊに小型基地局５００を設置した場合における小型基地局５００毎の設置費用を表す。また、ｗｉは、ＢＩＮｉにおけるトラヒック需要値を表す。また、ηは、ノイズを表す。また、ｇｉｊは、ｊに設置されたマクロ基地局４００からＢＩＮｉまでの伝搬ロスを表す。また、ｄｉｊは、ＢＩＮｉに在る無線端末が、位置ｊに設置されたマクロ基地局４００に接続した場合に、無線リソースが全て割当てられたと仮定された場合のスループット値を表す。また、ｘｊの値が１である場合、ｘｊは、ｊに基地局が配置されていることを表す。一方、ｘｊの値が０である場合、ｘｊは、ｊに基地局が配置されていないことを表す。
【００３９】
最適化部１４０は、小型基地局５００−ｐの設置に関する費用合計を算出する。ここで、費用合計とは、小型基地局５００−ｐの装置費用と、小型基地局５００−ｐの設置費用との合計である。費用合計には、土地区分毎の設置費用の違いを反映させることができる。費用合計は、式（１）により示される。
【００４０】
【数１】
【００４１】
最適化部１４０は、ＢＩＮ毎の伝搬ロスを示す情報と、マクロ基地局４００の送信電力を示す情報と、マクロ基地局４００のアンテナパターンを示す情報とに基づいて、マクロ基地局４００から送出された電波の受信電力をＢＩＮ毎に算出する。
【００４２】
最適化部１４０は、地図の情報に示された範囲にマクロ基地局４００が複数在る場合、受信電力が最も高いマクロ基地局４００を、そのＢＩＮをカバーするマクロ基地局４００であると定める。
【００４３】
また、最適化部１４０は、地図の情報に示された範囲に含まれるマクロ基地局４００に対するトラヒック需要の負荷量を、マクロ基地局４００毎に算出する。ここで、最適化部１４０は、ＣＲＥバイアス値、ミューティング比率、及びＢＩＮ毎に算出したスループット値に基づいて、マクロ基地局４００に対するトラヒック需要の負荷量を算出する。
【００４４】
比較のため、まず、ＣＲＥバイアス値及びミューティング比率を考慮しない場合のトラヒック需要の負荷量の算出方法について説明する。
【００４５】
マクロ基地局４００に対する（収容される）トラヒック需要の負荷量は、ＢＩＮ毎に算出したスループット値に基づいて算出される。位置ｊに設置されたマクロ基地局４００にカバーされるＢＩＮｉの信号対干渉雑音比ＳＩＮＲｉｊは、式（２）により表される。
【００４６】
【数２】
【００４７】
ここで、式（２）の分母の第1項は、他の基地局からの干渉を表す。また、式（２）の分母の第２項は、雑音成分を表す。
【００４８】
また、マクロ基地局４００のカバレッジエリア８００に含まれるＢＩＮ毎のスループット値は、ＢＩＮ毎の信号対干渉雑音比（ＳＩＮＲ）に基づいて算出される。より具体的には、ＢＩＮ毎のスループット値は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータに基づいて算出される。
【００４９】
信号対干渉雑音比−パケットエラーレート変換テーブルには、信号対干渉雑音比と、パケットエラーレートとが対応付けられて登録されている。また、ＭＣＳテーブルには、変調方式と、符号化率と、ＳＩＮＲ閾値とが対応付けられて登録されている。図６には、ＭＣＳテーブルの例が示されている。変調方式には、例えば、ＱＰＳＫ (２)、１６ＱＡＭ (４)及び６４ＱＡＭ (６)がある。
【００５０】
以下、下り方向の通信にＯＦＤＭＡを採用するＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）を例に、スループット値の算出方法を説明する。ＬＴＥでは、時間×周波数の無線リソースは、リソースブロック（Ｒｅｓｏｕｒｃｅ Ｂｌｏｃｋ，ＲＢ）単位で構成されている。また、リソースブロックは、７ＯＦＤＭシンボル（０．５［ｍｓ］）×１２サブキャリアで構成されている。１リソースブロックにより送信可能であるビット数は、式（３）により表わされる。
【００５１】
【数３】
【００５２】
式（３）において、[ＭＩＭＯ ｅｆｆｉｃｉｅｎｃｙ] は、そのＢＩＮにおけるＭＩＭＯの効率を表す。また、[Ｍｏｄｕｌａｔｉｏｎ]は、変調方式（図６を参照）を表す。また、 [Ｃｏｄｉｎｇ ｒａｔｅ]は、符号化率を表す。また、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]は、１リソースブロックあたりのサブキャリア数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝１２とする。また、[＃ ｏｆ ＯＦＤＭ ｓｙｍｂｏｌ／ＲＢ]は、１リソースブロックあたりのＯＦＤＭシンボル数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝７とする。また、ＰＥＲは、パケットエラーレートを表す。ＰＥＲは、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルにより、ＳＩＮＲ値を用いて算出される。
【００５３】
１リソースブロックは０．５［ｍｓ］であることから、対象とするシステムの周波数方向のリソースブロック数を＃ＲＢとして、位置ｊに設置されたマクロ基地局４００がカバーするＢＩＮｉに、リソースブロックが全て割り当てられた場合、スループットｄｉｊは、式（４）により表される。
【００５４】
【数４】
【００５５】
なお、割り当てられるリソースブロックは、その個数（リソース量）が制限されてもよい。例えば、フェージング等の変動要因に対するマージンとして、全無線リソースの８０［％］まで無線リソースが割り当てられるようにする場合、式（４）の＃ＲＢは、例えば、０．８×＃ＲＢに置き換えられてもよい。
【００５６】
図７には、周波数帯域幅と、サブキャリア数と、ＲＢ数との関係の例が示されている。 周波数方向のリソースブロック数は、対象とするシステムの周波数帯域幅に依存する。例えば、ＬＴＥでは、周波数帯域幅１．４［ＭＨｚ］に対応するサブキャリア数は、７６であり、対応するリソースブロック数は、６である。
【００５７】
位置ｊに設置されたマクロ基地局４００がカバーするＢＩＮｉに対して必要な無線リソース量の割合は、式（５）により表される。
【００５８】
【数５】
【００５９】
また、以下に示す式（６）の値が1以下である場合、そのことは、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全て収容することができることを表す。
【００６０】
【数６】
【００６１】
一方、式（６）の値が1を超えている場合、そのことは、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全ては収容することができないことを表す。したがって、マクロ基地局４００に対するトラヒック需要の負荷量の条件式は、式（７）により表される。
【００６２】
【数７】
【００６３】
ここで、ξは、カバレッジエリア８００の各ＢＩＮにおいて収容されるべきトラヒック需要の比率（０＜ξ≦１）を表す係数である。なお、ξの値は、パラメータとして予め定められているものとする。
【００６４】
式（６）の値が1以下である場合、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００は全て収容することができる、と判定される。
【００６５】
一方、式（６）の値が1を超えている場合、位置ｊに設置されたマクロ基地局４００がカバーする全てのＢＩＮにおけるトラヒック需要を、マクロ基地局４００が全ては収容することができない、と判定される。
【００６６】
以上に説明した、ＣＲＥバイアス値及びミューティング比率を考慮しない場合に対し、最適化部１４０は、ＣＲＥバイアス値、ミューティング比率、及びＢＩＮ毎に算出したスループット値に基づいて、マクロ基地局４００に対するトラヒック需要の負荷量を、以下のように算出する。ここで、ＣＲＥバイアス値は、小型基地局５００−ｐに対して定められるパラメータである。また、時間方向の干渉を回避するためのミューティング比率は、マクロ基地局４００に対して定められるパラメータである。
【００６７】
図８には、ミューティング・サブフレームの例が示されている。ミューティング・サブフレームによるミューティング比率は、全てのマクロ基地局４００で共通であるものとする。つまり、ノーマル・サブフレームの送信タイミング、及び、ミューティング・サブフレームの送信タイミングは、全てのマクロ基地局４００で同期しているものとする。
【００６８】
ＣＲＥバイアス値及びミューティング比率を考慮した場合の信号対干渉雑音比（ＳＩＮＲ）は、各マクロ基地局４００に対する干渉源が小型基地局５００及び他のマクロ基地局４００であるため、ＣＲＥバイアス値及びミューティング比率を考慮しない場合の信号対干渉雑音比（ＳＩＮＲ）と同じである。したがって、ＣＲＥバイアス値及びミューティング比率を考慮した場合の信号対干渉雑音比（ＳＩＮＲ）は、上記の式（２）により表される。
【００６９】
マクロ基地局４００は、ミューティング・サブフレーム（＝オールモスト・ブランク・サブフレーム（Ａｌｍｏｓｔ Ｂｌａｎｋ Ｓｕｂｆｒａｍｅｓ））に、所定データを含めて送信しないよう通信を制限する。したがって、位置ｊに設置されたマクロ基地局４００によりカバーされるＢＩＮｉに対する全てのリソースブロック（ＲＢ）に、ノーマル・サブフレームを割り当てた場合、ＢＩＮ毎のスループット値は、式（８）により表される。
【００７０】
【数８】
【００７１】
以上より、ミューティング比率を考慮した場合における、マクロ基地局４００の負荷量は、式（９）により表される。
【００７２】
【数９】
【００７３】
一方、小型基地局５００−ｐは、ノーマル・サブフレームの送信タイミングと、ミューティング・サブフレームの送信タイミングとの両方で、無線端末６００−ｍと通信する。図９には、ミューティング・サブフレームの送信タイミングと、小型基地局の通信タイミングとの例が示されている。図９では、一例として、マクロ基地局４００のトラヒックと、小型基地局５００−１のトラヒックとが示されている。
【００７４】
小型基地局５００−１は、ＣＲＥによらずに通信接続している無線端末６００−ｍと、ノーマル・サブフレームの送信タイミング及びミューティング・サブフレームの送信タイミングで通信する。また、小型基地局５００−１は、ＣＲＥにより通信接続している無線端末６００−ｍとも、ノーマル・サブフレームの送信タイミング及びミューティング・サブフレームの送信タイミングで通信する。
【００７５】
また、小型基地局５００にカバーされたＢＩＮにおける信号対干渉雑音比（ＳＩＮＲ）は、ノーマル・サブフレームに対する干渉源と、ミューティング・サブフレームに対する干渉源とが異なるため、サブフレームの種別毎に算出される。
【００７６】
具体的には、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局のみを干渉源として算出される。一方、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局５００−ｐ及びマクロ基地局４００を干渉源として算出される。
【００７７】
位置ｊに設置された小型基地局５００（ピコ基地局）にカバーされるＢＩＮｉに対して、ミューティング・サブフレームの全てのリソースブロック（ＲＢ）を割り当てた場合のスループット値ｄｉｊｐｉｃｏ（ｍｕｔｅ）、及びノーマル・サブフレームの全てのリソースブロック（ＲＢ）を割り当てた場合のスループット値ｄｉｊｐｉｃｏ（ｎｏｒｍａｌ）は、それぞれ式（１０）により表される。
【００７８】
【数１０】
【００７９】
以上より、ＢＩＮｉのスループット値ｄｉｊｐｉｃｏは、式（１１）により表される。
【００８０】
【数１１】
【００８１】
よって、ミューティング比率を考慮した場合の小型基地局５００のトラヒック需要の負荷量は、式（１２）により表される。
【００８２】
【数１２】
【００８３】
また、小型基地局５００−１が、ＣＲＥによらずに通信接続している無線端末６００−ｍとはノーマル・サブフレームの送信タイミングで通信し、且つ、ＣＲＥにより通信接続している無線端末６００−ｍとはミューティング・サブフレームの送信タイミングで通信する、と仮定することにより（図９を参照）、小型基地局５００のトラヒック需要の負荷量は、以下のように算出されてもよい。
【００８４】
小型基地局５００にカバーされたＢＩＮにおける信号対干渉雑音比（ＳＩＮＲ）は、ノーマル・サブフレームに対する干渉源と、ミューティング・サブフレームに対する干渉源とが異なるため、サブフレームの種別毎に算出される。
【００８５】
具体的には、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局のみを干渉源として算出される。ここで、ミューティング・サブフレームの送信タイミングにおける信号対干渉雑音比は、小型基地局５００がＣＲＥによりカバーするＢＩＮのみを対象に算出される。一方、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、他の小型基地局５００及びマクロ基地局４００を干渉源として算出される。ここで、ノーマル・サブフレームの送信タイミングにおける信号対干渉雑音比は、小型基地局５００がＣＲＥによらずにカバーするＢＩＮを対象に算出される。
【００８６】
したがって、スループット値、及びトラヒック需要の負荷量は、小型基地局５００がＣＲＥによりカバーするＢＩＮと、小型基地局５００がＣＲＥによらずにカバーするＢＩＮとに分けて、それぞれ算出される。
【００８７】
以下、位置ｊに設置された小型基地局５００がカバーするＢＩＮｉのうち、小型基地局５００がＣＲＥによりカバーするＢＩＮの集合を、Ｉｊ，ＣＲＥＢＩＮと表記する。また、小型基地局５００がＣＲＥによらずにカバーするＢＩＮの集合を、Ｉｊ，ｎｏｒｍａｌＢＩＮと表記する。
【００８８】
ＢＩＮの集合Ｉｊ，ＣＲＥＢＩＮを構成するＢＩＮｉに対して、ミューティング・サブフレームの全てのリソースブロックを割り当てた場合、スループット値ｄｉｊｐｉｃｏ（ｍｕｔｅ）は、式（１３）により表される。
【００８９】
【数１３】
【００９０】
一方、ＢＩＮの集合Ｉｊ，ｎｏｒｍａｌＢＩＮを構成するＢＩＮｉに対して、ノーマル・サブフレームの全てのリソースブロックを割り当てた場合、スループット値ｄｉｊｐｉｃｏ（ｎｏｒｍａｌ）は、式（１４）により表される。
【００９１】
【数１４】
【００９２】
以上より、ＣＲＥバイアス値及びミューティング比率を考慮した場合の小型基地局５００に対するトラヒック需要の負荷量は、式（１５）により表される。
【００９３】
【数１５】
【００９４】
式（１５）に表された二つの式のうち、いずれか一方の式でも値が１以上である場合、最適化部１４０は、その小型基地局５００がオーバロードしている、すなわち、その小型基地局５００のトラヒック需要を、その小型基地局５００が全ては収容することができない、と判定する。
【００９５】
タブーサーチ又は局所探索による最適化処理によって最適化される予め定められたパラメータ群には、費用に影響するパラメータ群と、費用に影響しないパラメータ群（トラヒック需要に影響するパラメータ群）とがある。費用に影響するパラメータには、例えば、小型基地局５００の設置台数、及び小型基地局５００の設置位置がある。一方、費用に影響しないパラメータ群（トラヒック需要に影響するパラメータ群）には、例えば、ＣＲＥバイアス値、ミューティング比率、小型基地局５００の送信電力、及び小型基地局５００のチルト角がある。
【００９６】
費用に影響するパラメータを変更する段階と、費用に影響しないパラメータのみを変更する段階との２段階に分けて、タブーサーチ又は局所探索による最適化処理を実行する。
【００９７】
以下、最適化処理における予め定められた制約条件を満たす、費用に影響するパラメータ値と、費用に影響しないパラメータ値との組を、「実行可能解」という。また、最適化処理における予め定められた制約条件を満たさない、費用に影響するパラメータ値と、費用に影響しないパラメータ値との組を、「実行不可能解」という。ここで、予め定められた制約条件とは、例えば、所要の受信電力、所要の信号対干渉雑音比（所要ＳＩＮＲ）、及び、収容すべきトラヒック需要（トラヒック量）を満たすという条件である。
【００９８】
最適化部１４０は、直近で得られた解（現在の解）が実行可能解であるか又は実行不可能解であるかに応じて、費用に影響するパラメータを変更する最適化処理を主に実行する。
【００９９】
図１０には、解が実行可能解から実行不可能解に遷移した場合の最適化処理の例が示されている。直近で得られた解が実行可能解である場合、最適化部１４０は、費用に影響するパラメータを変更することにより、小型基地局５００の設置費用が少なくなる方向に、探索を進める。ここで、小型基地局５００の設置費用が少なくなる方向に探索を進めることにより、直近で得られた解が実行不可能解（図１０では、１と表記されている解）になったとする。最適化部１４０は、この実行不可能解に対して、費用に影響するパラメータを固定し、且つ、費用に影響しないパラメータを変更することにより、直近で得られた解が実行可能解（図１０では、２と表記されている解）となるか否かを判定する。
【０１００】
一方、図１１には、解が実行不可能解から実行可能解に遷移した場合の最適化処理の例が示されている。直近で得られた解が実行不可能解である場合、最適化部１４０は、費用に影響するパラメータである「小型基地局５００の設置台数」を追加又は削除することにより、実行可能解を探索する。ここで、小型基地局５００の設置台数を追加したことにより、直近で得られた解が実行不可能解から実行可能解（図１１では、１と表記されている解）に遷移したとする。最適化部１４０は、小型基地局５００の設置台数を追加する前の直近の実行不可能解（図１１では、０と表記されている解）に対して、費用に影響しないパラメータを変更することにより、実行可能解（図１１では、２と表記されている解）となるか否かを判定する。
【０１０１】
このようにして、最適化部１４０は、直近で得られた解が実行可能解である場合と、直近で得られた解が実行不可能解である場合とに応じて、上記の最適化処理（操作）を繰り返すことにより、実行可能解の最適解を検出する。
【０１０２】
次に、費用に影響するパラメータを変更する最適化処理の例を説明する。
最適化部１４０は、費用に影響するパラメータを変更する最適化処理として、例えば、タブーサーチを実行する。
【０１０３】
ここで、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第１指標は、収容すべきトラヒック需要（所要収容トラヒック量）から、直近で得られた解により収容可能であるトラヒック需要（現在の収容トラヒック量）を減算した値である。但し、この減算結果が負値である場合、第１指標は値０とされる。また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第２指標は、小型基地局５００−ｐの設置費用である。また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第３指標は、カバレッジエリア８００（図２を参照）における、全ての基地局（マクロ基地局４００及び小型基地局５００−ｐ）に対するトラヒック需要の負荷量の総和である。
【０１０４】
また、費用に影響するパラメータを変更する最適化処理の目的関数を構成する第１〜第３指標は、辞書式順序（例えば、昇順、五十音順、アルファベット順）により、それぞれ予め配列されているものとする。
【０１０５】
最適化部１４０は、実行可能解の空間内だけでなく、実行不可能解の空間内に対しても、トラヒック需要の最適解の探索を実行する。このため、カバレッジエリア８００において収容すべきトラヒック需要を満たすことは、本実施形態における制約条件でないものとする。その代わり、本実施形態では、該制約条件は、上記の第１指標のように定められている。この場合、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たしている解が、元の最適化問題の実行可能解である。一方、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たさない解が、元の最適化問題の実行不可能解である。
【０１０６】
したがって、第１指標が値０となる本実施形態における実行可能解は、直近の解により収容可能であるトラヒック需要が、収容すべきトラヒック需要を満たす解である。つまり、第１指標が値０となる本実施形態における実行可能解が得られなかった場合、このことは、カバレッジエリア８００（図２を参照）において収容すべきトラヒック需要を満たす解を得ることができなかったことを示す。ただし、この場合でも、最適化部１４０は、収容すべきトラヒック需要に可能な限りに近いトラヒック需要を満たす、小型基地局５００の設置台数及び設置位置、並びに、小型基地局５００毎のパラメータ（例えば、チルト角）を検出することができる。
【０１０７】
また、最適化部１４０は、第１指標の値が最も小さくなる解に対して小型基地局５００の費用合計が最小となる解を、さらに第２指標を探索することにより検出する。ここで、小型基地局５００の費用合計が最小となる解が複数ある場合、最適化部１４０は、収容すべきトラヒック需要を最も少ない負荷量で収容することができる解を、さらに第３指標を探索することにより検出する。これは、第１指標及び第２指標により定まった解の条件下において、ヘテロジニアスネットワーク（システム）が収容可能であるトラヒック需要が、最も大きくなる解を検出（選択）することを意味する。
【０１０８】
最適化部１４０は、直近で得られた解が実行可能解である場合と、直近で得られた解が実行不可能解である場合とで、異なる近傍操作を実行する。ここで、近傍操作には、タブーサーチにおける１回の探索に対し、実行可能な操作の上限数が定められる。例えば、近傍値＝１と定められた場合、最適化部１４０は、小型基地局５００の設置台数を新たに1台追加する操作、又は、小型基地局５００の設置台数を新たに1台削除する操作のどちらかを、1回だけ実行する。
【０１０９】
図１２には、直近で得られた解が実行可能解である場合の近傍操作の例が示されている。直近で得られた解（図１２では、ｎ−１（ｎは、１以上の整数）と表記されている解）が実行可能解であり、且つ、実行不可能解から実行可能解（図１２では、０と表記されている解）に遷移した以降に探索した回数が、予め定められた回数ｎ未満である場合、最適化部１４０は、小型基地局５００の設置台数を新たに追加する近傍操作のみを実行する。これにより、最適化部１４０は、局所的な解から脱し、探索する範囲を広げることができる。
【０１１０】
また、直近で得られた解（図１２では、ｎと表記されている解）が実行可能解であり、且つ、実行不可能解から実行可能解（図１２では、０と表記されている解）に遷移した以降に探索した回数が、予め定められた回数ｎ以上である場合、最適化部１４０は、小型基地局５００を新たに削除する近傍操作のみを実行する。これにより、最適化部１４０は、費用合計が最小となる解を探索することができる。
【０１１１】
一方、直近で得られた解が実行不可能解である場合、最適化部１４０は、直近で得られた解が実行可能解となるよう、小型基地局５００の設置台数を新たに追加する近傍操作、及び、小型基地局５００の設置台数を新たに削除する近傍操作のうち、少なくとも一方を実行する。
【０１１２】
次に、費用に影響しないパラメータを変更する最適化処理の例を説明する。
最適化部１４０は、費用に影響しないパラメータを変更する最適化処理として、例えば、局所探索法を実行する。
【０１１３】
ここで、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第１指標は、収容すべきトラヒック需要（所要収容トラヒック量）から、直近で得られた解により収容可能であるトラヒック需要（現在の収容トラヒック量）を減算した値である。ただし、この減算結果が負値である場合、第１指標は値０とされる。また、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第２指標は、カバレッジエリア８００（図２を参照）における、全ての基地局（マクロ基地局４００及び小型基地局５００−ｐ）に対するトラヒック需要の負荷量の総和である。
【０１１４】
また、費用に影響しないパラメータを変更する最適化処理の目的関数を構成する第１及び第２指標は、辞書式順序（例えば、昇順、五十音順、アルファベット順）により、それぞれ予め配列されているものとする。
【０１１５】
図１３には、費用に影響しないパラメータについての近傍操作の例が示されている。最適化部１４０は、直近で得られた解（図１３では、値Ｃ）を基準とする、目的関数の指標要素（離散値）に予め定められた範囲（図１３では、ｎ＝±２の場合、値Ａ〜値Ｅ）に対して、近傍操作を実行する。
【０１１６】
図１に戻り、最適解検出装置１００の構成の説明を続ける。出力部１５０は、記憶部１３０に記憶されている各種データに基づいて、小型基地局５００−ｐの最適な設置台数及び設置位置を示す情報を、地図（図５を参照）と共に画面に表示する。また、出力部１５０は、カバレッジエリア８００に含まれる各ＢＩＮ（メッシュ）を示す情報を、地図と共に画面に表示してもよい。
【０１１７】
次に、最適化処理の手順を説明する。
図１４は、最適化処理の手順を表すフローチャートである。最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか（収容すべきトラヒック需要を収容可能か）否かを判定する（ステップＳ１）。
【０１１８】
直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１−Ｙｅｓ）、最適化部１４０は、タブーサーチにおいて、予め定められた回数まで小型基地局５００の設置台数を追加したか否かを判定する（ステップＳ２）。
【０１１９】
予め定められた回数までは小型基地局５００を追加していない場合（ステップＳ２−Ｎｏ）、最適化部１４０は、小型基地局５００の設置台数を追加する近傍操作（局所的な解から脱し、探索する範囲を広げる操作）を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ３）。
【０１２０】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか（収容すべきトラヒック需要を収容可能か）否かを判定する（ステップＳ４）。直近で得られた解が、収容すべきトラヒック需要を満たさない場合（ステップＳ４−Ｎｏ）、最適化部１４０は、小型基地局５００の設置台数を追加した回数をカウントするための回数カウンタをリセットする（ステップＳ５）。
【０１２１】
最適化部１４０は、直近で得られた解に対して、費用に影響するパラメータを固定し、費用に影響しないパラメータを変更することにより、最適化処理を実行する（ステップＳ６）。最適化部１４０は、最適化処理により得られた解で、直近で得られた解を示す変数を更新する。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ７）。
【０１２２】
そして、最適化部１４０は、最適化処理について予め定められた終了条件を満たすか否かを判定する（ステップＳ８）。最適化処理について予め定められた終了条件を満たす場合（ステップＳ８−Ｙｅｓ）、最適化部１４０は、最適化処理を終了する。
【０１２３】
一方、ステップＳ１において、直近で得られた解が、収容すべきトラヒック需要を満たしていない場合（ステップＳ１−Ｎｏ）、最適化部１４０は、直近で得られた解を変数ＴＭＰに格納し、変数ＴＭＰを記憶部１３０に記憶させる（ステップＳ９）。
【０１２４】
最適化部１４０は、小型基地局５００の設置台数を追加及び削除する近傍操作を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１０）。
【０１２５】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか否かを判定する（ステップＳ１１）。直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１１−Ｙｅｓ）、最適化部１４０は、直近で得られた解が、小型基地局５００の設置台数を追加する近傍操作により得られた解であるか否かを判定する（ステップＳ１２）。
【０１２６】
直近で得られた解が、小型基地局５００の設置台数を追加する近傍操作により得られた解である場合（ステップＳ１２−Ｙｅｓ）、最適化部１４０は、変数ＴＭＰに対して、費用に影響するパラメータを固定し、費用に影響しないパラメータを変更することにより、最適化処理を実行する（ステップＳ１３）。
【０１２７】
最適化部１４０は、直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値以下であるか否かを判定する（ステップＳ１４）。直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値よりも大きい場合（ステップＳ１４−Ｎｏ）、最適化部１４０は、ステップＳ１３における最適化処理により得られた解で、直近で得られた解を示す変数を更新する。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１５）。そして、最適化部１４０は、ステップＳ８に処理を進める。
【０１２８】
また、ステップＳ２において、予め定められた回数まで小型基地局５００を追加している場合（ステップＳ２−Ｙｅｓ）、最適化部１４０は、小型基地局５００の設置台数を削除する近傍操作（費用合計が最小となる解を探索する操作）を実行し、直近で得られた解を示す変数を、記憶部１３０に記憶させる。また、直近で得られた解が、これまでに得られた解のなかで、目的関数値を最も小さくさせる解である場合、最適化部１４０は、直近で得られた解を変数Ｂｅｓｔに格納し、変数Ｂｅｓｔを記憶部１３０に記憶させる（ステップＳ１６）。
【０１２９】
最適化部１４０は、直近で得られた解が、収容すべきトラヒック需要を満たすか否かを判定する（ステップＳ１７）。直近で得られた解が、収容すべきトラヒック需要を満たさない場合（ステップＳ１７−Ｎｏ）、最適化部１４０は、ステップＳ５に処理を進める。一方、直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ１７−Ｙｅｓ）、最適化部１４０は、ステップＳ１６に処理を戻す。
【０１３０】
また、ステップＳ４において、直近で得られた解が、収容すべきトラヒック需要を満たす場合（ステップＳ４−Ｙｅｓ）、最適化部１４０は、小型基地局５００の設置台数を追加した回数をカウントするための回数カウンタをリセットする（ステップＳ１８）。そして、最適化部１４０は、ステップＳ２に処理を戻す。
【０１３１】
また、ステップＳ１２において、直近で得られた解が、小型基地局５００の設置台数を追加する以外の近傍操作により得られた解である場合（ステップＳ１２−Ｙｅｓ）、最適化部１４０は、ステップＳ２に処理を戻す。また、ステップＳ１４において、直近で得られた解による目的関数値が、ステップＳ１３における最適化処理により得られた解による目的関数値以下である場合（ステップＳ１４−Ｙｅｓ）、最適化部１４０は、ステップＳ８に処理を進める。また、ステップＳ８において、最適化処理について予め定められた終了条件を満たさない場合（ステップＳ８−Ｎｏ）、最適化部１４０は、ステップＳ１に処理を戻す。
【０１３２】
以上のように、最適解検出装置１００は、置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する（費用に影響しない）第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより（図１０及び図１１を参照）、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部１４０を備える。
この構成により、最適化部１４０は、第１パラメータ群（費用に影響しないパラメータ群）と、第２パラメータ群（費用に影響するパラメータ群）とに分けられたパラメータに基づいて、解が遷移した場合の直近の実行不可能解に対してのみ、前記第１パラメータ群を変更する。これにより、最適解検出装置１００は、第１パラメータ群（費用に影響しないパラメータ群）を変更する最適化処理を必要最小限に抑え、実行可能解の最適解を短時間で検出することができる。また、最適解検出装置１００は、ヘテロジニアスネットワークに特有のパラメータであるＣＲＥバイアス値及びミューティング比率の最適値を得ることができる。
【０１３３】
また、最適化部１４０は、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群（費用に影響するパラメータ）を費用が増加する方向に変更（近傍操作）することにより、実行可能解の最適解を検出する（図１２を参照）。
この構成により、最適化部１４０は、近傍操作を実行する。これにより、最適解検出装置１００は、局所的な解から脱し、探索する範囲を広げることができ、実行可能解の最適解を短時間で検出することができる。
【０１３４】
また、最適化部１４０は、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用（費用合計）が最小となる最適解を検出する。
これにより、最適解検出装置１００は、トラヒック需要を収容し且つ費用（費用合計）が最小となる最適解を短時間で検出することができる。
【０１３５】
また、最適化部１４０は、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群（例えば、ＣＲＥバイアス値、ミューティング比率、小型基地局５００の送信電力、及び小型基地局５００のチルト角）を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３６】
また、最適化部１４０は、ヘテロジニアスネットワークを構成する第１無線基地局（小型基地局５００）における受信電力に対するバイアス値（ＣＲＥバイアス値）、前記ヘテロジニアスネットワークを構成する第２無線基地局（マクロ基地局４００）が送信するサブフレームがミュートされる率（ミューティング比率）、及び、前記第２無線基地局（マクロ基地局４００）の送信電力のうち少なくとも一つを、前記第１パラメータ群（例えば、費用に影響しないパラメータ群）として変更することにより、前記実行可能解の最適解を検出する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３７】
また、最適化部１４０は、ヘテロジニアスネットワークを構成する第１無線基地局（小型基地局５００）の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群（例えば、費用に影響するパラメータ）として変更する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３８】
また、最適化部１４０は、タブーサーチ（タブー探索）又は局所探索を実行する。
これにより、最適解検出装置１００は、実行可能解の最適解を短時間で検出することができる。
【０１３９】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【０１４０】
例えば、各ＢＩＮにおける受信信号強度及び干渉量、アンテナのチルト角などの基地局のパラメータ、並びに、所要の受信信号強度及びキャリア信号電力対干渉電力比（Ｃ／Ｉ）等を入力データとして、通信エリアを構築する対象とされた範囲に対し、例えば、所要の受信信号強度以上となるＢＩＮの個数を最大化（カバレッジ最大化）する等の置局設計における条件が満たされるように、最適解検出装置１００は、最適化処理を実行してもよい
【０１４１】
また、例えば、最適解検出装置１００は、入力装置３００から各種データを取得する代わりに、それら各種データを予め記憶するデータベース部を備えていてもよい。
【０１４２】
なお、以上に説明した最適解検出装置を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録し、そのプログラムをコンピュータシステムに読み込ませて実行するようにしてもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【０１４３】
１００…最適解検出装置、１１０…領域設定部、１２０…特性算出部、１３０…記憶部、１４０…最適化部、１５０…出力部、３００…入力装置、４００…マクロ基地局、４１０…受信電力曲線、５００…小型基地局、５１０…受信電力曲線、５２０…受信電力曲線、６００…無線端末、８００…カバレッジエリア、９００…小型基地局セル、９１０…小型基地局セル
【特許請求の範囲】
【請求項１】
置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部、
を備えることを特徴とする最適解検出装置。
【請求項２】
前記最適化部は、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群を費用が増加する方向に変更することにより、実行可能解の最適解を検出することを特徴とする請求項１に記載の最適解検出装置。
【請求項３】
前記最適化部は、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用が最小となる最適解を検出することを特徴とする請求項１又は請求項２に記載の最適解検出装置。
【請求項４】
前記最適化部は、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする請求項１から請求項３のいずれか一項に記載の最適解検出装置。
【請求項５】
前記最適化部は、ヘテロジニアスネットワークを構成する第１無線基地局における受信電力に対するバイアス値、前記ヘテロジニアスネットワークを構成する第２無線基地局が送信するサブフレームがミュートされる率、及び、前記第２無線基地局の送信電力のうち少なくとも一つを、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする請求項１から請求項４のいずれか一項に記載の最適解検出装置。
【請求項６】
前記最適化部は、ヘテロジニアスネットワークを構成する第１無線基地局の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群として変更することを特徴とする請求項１から請求項５のいずれか一項に記載の最適解検出装置。
【請求項７】
前記最適化部は、タブーサーチ又は局所探索を実行することを特徴とする請求項１から請求項６のいずれか一項に記載の最適解検出装置。
【請求項８】
コンピュータに、
置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する手順、
を実行させるための最適解検出プログラム。
【請求項１】
置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する最適化部、
を備えることを特徴とする最適解検出装置。
【請求項２】
前記最適化部は、直近で得られている解が実行可能解である場合、予め定められた回数だけ前記第２パラメータ群を費用が増加する方向に変更することにより、実行可能解の最適解を検出することを特徴とする請求項１に記載の最適解検出装置。
【請求項３】
前記最適化部は、前記実行可能解の最適解として、トラヒック需要を収容し且つ費用が最小となる最適解を検出することを特徴とする請求項１又は請求項２に記載の最適解検出装置。
【請求項４】
前記最適化部は、トラヒック需要に影響し且つ費用に影響しない予め定められたパラメータ群を、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする請求項１から請求項３のいずれか一項に記載の最適解検出装置。
【請求項５】
前記最適化部は、ヘテロジニアスネットワークを構成する第１無線基地局における受信電力に対するバイアス値、前記ヘテロジニアスネットワークを構成する第２無線基地局が送信するサブフレームがミュートされる率、及び、前記第２無線基地局の送信電力のうち少なくとも一つを、前記第１パラメータ群として変更することにより、前記実行可能解の最適解を検出することを特徴とする請求項１から請求項４のいずれか一項に記載の最適解検出装置。
【請求項６】
前記最適化部は、ヘテロジニアスネットワークを構成する第１無線基地局の設置台数及び設置位置のうち少なくとも一つを、前記第２パラメータ群として変更することを特徴とする請求項１から請求項５のいずれか一項に記載の最適解検出装置。
【請求項７】
前記最適化部は、タブーサーチ又は局所探索を実行することを特徴とする請求項１から請求項６のいずれか一項に記載の最適解検出装置。
【請求項８】
コンピュータに、
置局設計により収容すべきトラヒック需要を満たす解である実行可能解と、前記収容すべきトラヒック需要を満たさない解である実行不可能解との間を、トラヒック需要に影響する第１パラメータ群、及び費用に影響する第２パラメータ群を変更することにより、解が遷移した場合、直近の実行不可能解に対してのみ、前記第１パラメータ群を変更することにより、実行可能解の最適解を検出する手順、
を実行させるための最適解検出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１３−４２２０２（Ｐ２０１３−４２２０２Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１１−１７５８８０（Ｐ２０１１−１７５８８０）
【出願日】平成２３年８月１１日（２０１１．８．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２３年８月１１日（２０１１．８．１１）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]