位置検出装置及び位置検出プログラム
【課題】基地局を設置する自由度が高い位置を検出することができる位置検出装置及び位置検出プログラムを提供する。
【解決手段】位置検出装置１００は、所定範囲を含む地図データと、サイズと最適化条件と制約条件とを取得し、地図にＢＩＮを定める領域設定部１１０と、伝搬ロスを算出する特性算出部１２０と、制約条件と最適化条件とに基づいて、基地局の台数と、基地局が設置される第１及び第２候補位置とを算出し、第１及び第２候補位置の近傍からＢＩＮを選択する領域選択部１４２と、選択したＢＩＮにより定まる第３及び第４候補位置をノードとするグラフから、前記範囲で制約条件を満たし、且つ、最適化条件により最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部１４３と、選択した完全部分グラフにより定まる領域を出力する出力部１５０とを備える。
【解決手段】位置検出装置１００は、所定範囲を含む地図データと、サイズと最適化条件と制約条件とを取得し、地図にＢＩＮを定める領域設定部１１０と、伝搬ロスを算出する特性算出部１２０と、制約条件と最適化条件とに基づいて、基地局の台数と、基地局が設置される第１及び第２候補位置とを算出し、第１及び第２候補位置の近傍からＢＩＮを選択する領域選択部１４２と、選択したＢＩＮにより定まる第３及び第４候補位置をノードとするグラフから、前記範囲で制約条件を満たし、且つ、最適化条件により最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部１４３と、選択した完全部分グラフにより定まる領域を出力する出力部１５０とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、置局設計における、位置検出装置及び位置検出プログラムに関する。
【背景技術】
【０００２】
無線通信システム、特に携帯電話に代表される移動体通信システムでは、通信エリアを実際に構築する前に、基地局を設置する位置を設計者が事前に検討する置局設計が行われる。置局設計では、通信エリアを構築する対象とされた範囲の地図データが、予め定められた大きさの複数の領域に分割される。基地局を設置する位置は、これら領域毎の受信信号強度等に基づいて、制約条件（例えば、トラヒックの需要の条件）を満たすよう検討される。
【０００３】
このような置局設計において、基地局の配置パターンの作成等の手間を省くとともに、最適な配置パターンを得ることを目的とした基地局配置パターン決定方法が、特許文献１に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−２８５９２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、実際の設置では地理的な制約があるため、置局設計によって事前に定められた位置に基地局を設置できるとは限らない。そこで、置局設計によって事前に定められた位置の代わりに、その位置から離れた位置に、基地局を実際に設置することとなった場合、置局設計では満たされていた制約条件、及び最適化条件（例えば、設置費用等を最小にするという条件）が、実際の設置では必ずしも満たされるとは限らない。このように、特許文献１に開示された方法により検出された位置は、基地局を設置する位置としては、自由度が低いという問題がある。
【０００６】
本発明は、前記の点に鑑みてなされたものであり、基地局を設置する自由度が高い位置を検出する位置検出装置及び位置検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記の課題を解決するためになされたものであり、予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する領域設定部と、基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する特性算出部と、前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する領域選択部と、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、前記選択した完全部分グラフのノードの位置により定まる領域を出力する出力部と、を備えることを特徴とする位置検出装置である。
【０００８】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、前記領域選択部が、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記領域毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【０００９】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータと、を取得することにより、前記領域毎の受信電力及び信号対干渉雑音比を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、前記領域選択部が、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力及び前記所要信号対干渉雑音比を満たす前記領域群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【００１０】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記領域毎の前記トラヒックの収容量を算出し、前記予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記領域選択部が、基地局の価格及び前記台数により定まる値と、基地局が設置される前記領域毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記領域毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【００１１】
また、本発明は、コンピュータに、予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する手順と、基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する手順と、前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する手順と、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、前記選択した完全部分グラフのノードの位置により定まる領域を出力する手順と、を実行させるための位置検出プログラムである。
【発明の効果】
【００１２】
本発明によれば、制約条件及び最適化条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態における、位置検出装置の構成を表すブロック図である。
【図２】本発明の一実施形態における、地図データの例を表す図である。
【図３】本発明の一実施形態における、基地局を設置する位置を含む地図の所定範囲を表す図である。
【図４】本発明の一実施形態における、ＭＣＳテーブルの例を示す表である。
【図５】本発明の一実施形態における、周波数帯域幅と、サブキャリア数と、リソースブロック（ＲＢ）数の関係例を示す表である。
【図６】本発明の一実施形態における、第３候補位置と第４候補位置との組み合わせの一例を表す図である。
【図７】本発明の一実施形態における、制約条件を満たす第３候補位置及び第４候補位置の組み合わせの一例を表す図である。
【図８】本発明の一実施形態における、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置の全ての組合せが実行可能解である完全部分グラフの一例を表す図である。
【図９】本発明の一実施形態における、制約条件及び最適化条件を満たす第３候補位置により定まる領域の例を表す図である。
【図１０】本発明の一実施形態における、出力された領域の例を表す図である。
【図１１】本発明の一実施形態における、位置検出装置の動作手順を表すフローチャートである。
【図１２】本発明の一実施形態における、最適化部の動作手順を表すフローチャートである。
【発明を実施するための形態】
【００１４】
［第１実施形態］
本発明の第１実施形態について図面を参照して詳細に説明する。第１実施形態では、置局設計における最適化条件の一例として、基地局の価格及び設置台数により定まる金額と、各基地局の設置費用とを合計した金額を最小にするという条件を設定する。また、置局設計における制約条件の一例として、通信エリアにおけるトラヒックの需要を全て収容する（トラヒックの需要を満たす収容量を通信エリアで確保する）という条件を設定する。
【００１５】
図１には、位置検出装置の構成がブロック図により表されている。位置検出装置１００は、入力装置２００から取得した各種データに基づいて、トラヒックの需要を全て収容するという条件（制約条件）と、基地局の設置費用等を最小にするという条件（最適化条件）とを満たす基地局の設置位置を、基地局を設置する候補位置をノードとするグラフ（図７及び図８を用いて後述する）に基づいて検出し、検出した設置位置により定まる設置領域を出力する。これにより、位置検出装置１００は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００１６】
まず、位置検出装置の構成、及び入力装置について説明する。
入力装置２００は、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとを、位置検出装置１００に入力する。
【００１７】
また、地図データは、所定範囲（通信エリア）を表す地図データである。また、予め定められたサイズを表すデータとは、地図がメッシュ状に分割された各領域（以下、「ＢＩＮ」という）のサイズを表すデータである。また、予め定められた最適化条件を表すデータとは、本実施形態では、基地局の設置費用を表すデータである。なお、最適化条件を表すデータには、最適化処理における終了条件（閾値など）を表すデータが含まれていてもよい。
【００１８】
また、予め定められた制約条件を表すデータとは、本実施形態では、トラヒックの需要（要求される収容量）を表すデータである。なお、トラヒックの需要を表すデータは、将来のトラヒックの需要が予測されたデータ（以下、「トラヒック需要予測データ」という）でもよい。
【００１９】
また、予め定められた土地区分データとは、基地局を設置する位置が住宅地であるか又は森林地帯であるか等を、ＢＩＮ毎に表すデータである。この土地区分データは、例えば、基地局の設置費用がＢＩＮ毎に算出される際に参照される。なお、土地区分が考慮されなくてもよい場合、土地区分データは、位置検出装置１００に入力されなくてもよい。
【００２０】
入力装置２００は、基地局の周波数帯を表すデータと、基地局の送信電力を表すデータと、伝搬ロスのモデル式を表すデータとを、位置検出装置１００に入力する。ここで、伝搬ロスのモデル式は、伝搬ロスを算出する手順を表す式であり、例えば、レイ・トレース、Ｗａｌｆｉｓｃｈ−池上モデル等の伝搬ロスのモデル式である。
【００２１】
なお、伝搬ロスのモデル式のパラメータには、土地区分データを表すパラメータが含まれていてもよい。伝搬ロスのモデル式にこのパラメータが含まれることで、位置検出装置１００は、土地区分毎に伝搬ロスを精度よく算出することができる。なお、入力装置２００は、伝搬ロスのモデル式を表すデータの代わりに、伝搬ロスを直接表すデータを位置検出装置１００に入力してもよい。
【００２２】
入力装置２００は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータ（図４を用いて後述する）を、位置検出装置１００に入力する。
【００２３】
位置検出装置１００は、領域設定部１１０と、特性算出部１２０と、記憶部１３０と、最適化部１４０と、出力部１５０とを備える。
【００２４】
領域設定部１１０には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００から入力される。
【００２５】
領域設定部１１０は、入力されたサイズでメッシュ状に地図を分割することにより、入力されたサイズのＢＩＮを地図に複数定める。図２には、地図データの例が表されている。各ＢＩＮの形状は、例えば、矩形状である。
【００２６】
領域設定部１１０は、地図に定めたＢＩＮと、予め定められた制約条件（トラヒックの需要を表すデータ）とに基づいて、トラヒックの需要（要求される収容量）をＢＩＮ毎に算出する。また、領域設定部１１０は、地図に定めたＢＩＮと、予め定められた最適化条件を表すデータ（基地局の設置費用を表すデータ）とに基づいて、基地局の設置費用をＢＩＮ毎に算出する。ここで、領域設定部１１０は、ＢＩＮ毎の土地区分データに基づいて、基地局の設置費用をＢＩＮ毎に算出してもよい。ここで、領域設定部１１０は、１つのＢＩＮに含まれる複数の土地区分のうち、最も面積率が高い土地区分（代表）を、そのＢＩＮの土地区分としてもよい。
【００２７】
領域設定部１１０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データとを、記憶部１３０に記憶させる。
【００２８】
特性算出部１２０には、基地局の送信電力を表すデータと、基地局の周波数帯を表すデータと、伝搬ロスのモデル式を表すデータとが、入力装置２００から入力される。
【００２９】
特性算出部１２０は、基地局の送信電力を表すデータと、その周波数帯を表すデータと、伝搬ロスのモデル式を表すデータとに基づいて、ＢＩＮ毎の伝搬ロスを算出し、算出したＢＩＮ毎の伝搬ロスを表すデータを、記憶部１３０に記憶させる。
【００３０】
記憶部１３０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データと、ＢＩＮ毎の伝搬ロスを表すデータとを記憶する。
【００３１】
また、記憶部１３０には、基地局の価格を表すデータが、入力装置２００から入力される。また、記憶部１３０には、トラヒックの収容量（収容トラヒック量）を算出するためのモデル式（収容量計算式）を表すデータ、又は、トラヒックの収容量を基地局毎に表すデータが、入力装置２００から入力される。記憶部１３０は、これらのデータも記憶する。ここで、記憶部１３０は、トラヒックの収容量を算出するためのモデル式を表すデータを記憶する代わりに、トラヒックの収容量を直接表すデータを記憶してもよい。なお、トラヒックの収容量を算出するためのモデル式のパラメータには、地図の所定範囲（通信エリア）に存在する建物毎の建物高を表すパラメータが含まれていてもよい。
【００３２】
最適化部１４０は、トラヒックの需要を満たす収容量を地図の所定範囲（通信エリア）で確保するという制約条件を満たし、且つ、基地局の価格及び設置台数により定まる金額と各基地局の設置費用とを合計した金額を最小にするという最適化条件を満たす完全部分グラフ（図８を用いて後述する）を選択する（最適化処理）。
【００３３】
最適化部１４０は、取得部１４１と、領域選択部１４２と、グラフ選択部１４３とを有する。取得部１４１は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータとを、記憶部１３０から取得する。また、取得部１４１は、トラヒックの収容量を算出するためのモデル式を表すデータと、トラヒックの収容量を基地局毎に表すデータとのうち、記憶部１３０に記憶されているほうのデータを、記憶部１３０から取得する。
【００３４】
領域選択部１４２は、取得部１４１が記憶部１３０から取得したこれらのデータを、取得部１４１から受信する（初期設定）。領域選択部１４２は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、目的関数（後述）の値が最小となるように、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局が設置される第１候補位置及び第２候補位置と、基地局の台数とを算出する。
【００３５】
ここで、第１候補位置とは、置局設計の際に１つの組とされる基地局同士の一方を構成する１台以上の基地局をそれぞれ設置する１箇所以上の候補位置である。また、第２候補位置とは、置局設計の際に１つの組とされる基地局同士の他方を構成する１台以上の基地局をそれぞれ設置する１箇所以上の候補位置である。
【００３６】
以下では、一例として、領域選択部１４２が算出した基地局の台数は２台であるとして説明を続ける。なお、算出した基地局の台数が３台以上である場合でも、最適化部１４０は、各基地局の設置位置を１つの組として扱えばよい。
【００３７】
領域選択部１４２は、算出した２台の基地局が設置される第１候補位置及び第２候補位置の近傍から、それぞれＢＩＮを選択する。図３には、基地局を設置する位置を含む地図の所定範囲（通信エリア）が表されている。図３では、第１候補位置４００を中心とする近傍範囲４１０に含まれるＢＩＮ４２０−１〜４２０−４が、複数のＢＩＮから領域選択部１４２により選択されたとする。同様に、第２候補位置５００を中心とする近傍範囲５１０に含まれるＢＩＮ５２０−１〜５２０−４が、複数のＢＩＮから領域選択部１４２により選択されたとする。
【００３８】
また、ＢＩＮ４２０−１〜４２０−４には、複数の第３候補位置が、領域選択部１４２により定められたとする。同様に、ＢＩＮ５２０−１〜５２０−４には、複数の第４候補位置が、領域選択部１４２により定められたとする。なお、これら候補位置の配置は、一例である。
【００３９】
次に、基地局の設置費用等を算出する方法の一例、及び基地局のトラヒック収容量を算出する方法の一例を説明する。ここで、通信システムにＯＦＤＭＡ（Ｏｒｔｈｏｇｏｎａｌ Ｆｒｅｑｕｅｎｃｙ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）が用いられているものとして説明するが、通信システムは、ＯＦＤＭＡに限らなくてよい。例えば、通信システムは、ＣＤＭＡ（Ｗｉｄｅｂａｎｄ Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）システムでもよい。
【００４０】
以下では、ｉは、ＢＩＮの識別子を表す。また、その集合は、Ｉと表記される。また、ｊは、基地局の設置位置の識別子を表す。また、その集合は、Ｊと表記される。また、Ｉｊは、位置ｊに設置された基地局にカバーされるＢＩＮｉの集合を表す。また、Ｔｘは、基地局の送信電力を表す。また、ｃは、基地局の価格を表す。また、ｃｊは、位置ｊに基地局を設置する場合の設置費用を表す。また、ｗｉは、ＢＩＮｉにおけるトラヒックの需要を表す。また、ηは、ノイズを表す。また、ｇｉｊは、ｊに設置された基地局からＢＩＮｉまでの伝搬ロスを表す。また、ｄｉｊは、ＢＩＮｉに在る無線局が、位置ｊに設置された基地局に接続した場合に、無線リソースが全て割当てられたと仮定された場合のスループット値を表す。また、ｘｊの値が１である場合、ｘｊは、ｊに基地局が配置されていることを表す。一方、ｘｊの値が０である場合、ｘｊは、ｊに基地局が配置されていないことを表す。
【００４１】
まず、基地局の設置費用等を算出する方法の一例について説明する。領域選択部１４２は、式（１）により、基地局の設置費用を算出する。
【００４２】
【数１】
【００４３】
次に、基地局のトラヒック収容量を算出する方法の一例について説明する。領域選択部１４２は、基地局がカバーするＢＩＮに対する信号対干渉雑音比（ＳＩＮＲ）に基づいて、そのＢＩＮに対するスループット値を算出する。また、領域選択部１４２は、算出したスループット値を用いて、その基地局が収容するトラヒックの収容量を算出する。また、領域選択部１４２は、位置ｊに設置された基地局がカバーするＢＩＮｉに対するＳＩＮＲｉｊを、式（２）により算出する。
【００４４】
【数２】
【００４５】
ここで、式（２）の分母の第1項は、他の基地局からの干渉を表す。また、式（２）の分母の第２項は、雑音成分を表す。
【００４６】
また、領域選択部１４２は、ＢＩＮ毎にスループット値を算出する。ここで、領域選択部１４２は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータを参照する。
【００４７】
信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルには、信号対干渉雑音比（ＳＩＮＲ）と、パケットエラーレート（ＰＥＲ）とが対応付けられて登録されている。また、ＭＣＳテーブルには、変調方式と、符号化率と、ＳＩＮＲ閾値とが対応付けられて登録されている。図４には、ＭＣＳテーブルの例が示されている。変調方式には、例えば、ＱＰＳＫ (２)、１６ＱＡＭ (４)及び６４ＱＡＭ (６)がある。
【００４８】
ここで、下り方向の通信にＯＦＤＭＡを採用するＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）を例に、スループット値の算出を説明する。ＬＴＥでは、時間×周波数の無線リソースは、リソースブロック（Ｒｅｓｏｕｒｃｅ Ｂｌｏｃｋ，ＲＢ）単位で構成されている。また、リソースブロックは、７ＯＦＤＭシンボル（０．５［ｍｓ］）×１２サブキャリアで構成されている。１リソースブロックにより送信可能であるビット数は、式（３）により表わされる。
【００４９】
【数３】
【００５０】
式（３）において、[ＭＩＭＯ ｅｆｆｉｃｉｅｎｃｙ] は、そのＢＩＮにおけるＭＩＭＯの効率を表す。また、[Ｍｏｄｕｌａｔｉｏｎ]は、変調方式を表す（図４を参照）。また、 [Ｃｏｄｉｎｇ ｒａｔｅ]は、符号化率を表す（図４を参照）。また、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]は、１リソースブロックあたりのサブキャリア数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝１２とする。また、[＃ ｏｆ ＯＦＤＭ ｓｙｍｂｏｌ／ＲＢ]は、１リソースブロックあたりのＯＦＤＭシンボル数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝７とする。また、ＰＥＲは、パケットエラーレートを表す。ＰＥＲは、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルにより、ＳＩＮＲ値を用いて算出される。
【００５１】
１リソースブロックは０．５［ｍｓ］であることから、対象とするシステムの周波数方向のリソースブロック数を＃ＲＢとして、位置ｊに設置された基地局がカバーするＢＩＮｉに、リソースブロックが全て割り当てられた場合、スループットｄｉｊは、式（４）により表される。
【００５２】
【数４】
【００５３】
なお、割り当てられる無線リソースは、そのリソース量が制限されてもよい。例えば、フェージング等の変動要因に対するマージンとして、全無線リソースの８０［％］まで無線リソースが割り当てられるようにする場合、式（４）の＃ＲＢを、０．８×＃ＲＢに置き換えることにより、領域選択部１４２は、このような場合にも対応可能である。
【００５４】
また、周波数方向のリソースブロック数は、対象とするシステムの周波数帯域幅に依存する。図５には、周波数帯域幅と、サブキャリア数と、リソースブロック（ＲＢ）数との関係例が、表により示されている。例えば、周波数帯域幅１．４［ＭＨｚ］に対応するサブキャリア数は、７６である。また、周波数帯域幅１．４［ＭＨｚ］に対応するリソースブロック数は、６である。
【００５５】
位置ｊに設置された基地局がカバーするＢＩＮｉに対して必要な無線リソース量の割合は、式（５）により表される。
【００５６】
【数５】
【００５７】
また、式（６）の値が1以下である場合、式（６）は、位置ｊに設置された基地局が、自局がカバーする全てのＢＩＮにおけるトラヒックの需要を、全て収容することができることを表す。
【００５８】
【数６】
【００５９】
一方、式（６）の値が1を超えている場合、式（６）は、位置ｊに設置された基地局が、自局がカバーする全てのＢＩＮにおけるトラヒックの需要を、全ては収容することができないことを表す。したがって、トラヒックの収容量（収容トラヒック量）の条件式は、式（７）により表される。
【００６０】
【数７】
【００６１】
ここで、ξは、通信エリアの各ＢＩＮにおいて収容されるべきトラヒック量の比率（０＜ξ≦１）を表す係数である。なお、ξの値は、パラメータとして予め定められているものとする。本実施形態では、ξ＝１とする。
【００６２】
図１に戻り、位置検出装置の構成の説明を続ける。グラフ選択部１４３は、複数の第３候補位置及び複数の第４候補位置（図３を参照）をノード（節点）とするグラフを構成する部分グラフを検出する。
【００６３】
候補位置をノードとするグラフについて説明する。図６には、第３候補位置と第４候補位置との組み合わせの一例が、鎖線等により表されている。以下では、第１候補位置４００を、第３候補位置４３０−１と表記する。また、第２候補位置５００を、第４候補位置５３０−１と表記する。また、グラフ選択部１４３は、図６では、第３候補位置４３０−１〜４３０−１３と、第４候補位置５３０−１〜５３０−１３との全ての組み合わせについて、トラヒックの需要を収容することが可能であるか否かを、組み合わせ毎に判定する（式（７）を参照）。
【００６４】
また、グラフ選択部１４３は、検出したグラフから、地図の所定範囲（通信エリア）でトラヒックの需要（式（７）を参照）を満たし、且つ、基地局の価格及びその台数により定まる値と基地局が設置されるＢＩＮ毎の設置費用との合計（式（１）を参照）が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
【００６５】
グラフ選択部１４３は、トラヒックの需要が全て収容されるか否かを、第３候補位置と第４候補位置との組み合わせ毎に判定する。図７には、制約条件（通信エリアにおけるトラヒックの需要を全て収容するという条件）を満たす第３候補位置及び第４候補位置の組み合わせの一例が表されている。図７では、各組み合わせのうち、第３候補位置４３０−１及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−２と、第３候補位置４３０−３及び第４候補位置５３０−１と、第３候補位置４３０−３及び第４候補位置５３０−２とで、制約条件が満たされているとする。
【００６６】
ここで、グラフ選択部１４３は、基地局を設置する候補位置を、グラフ理論におけるノード（節点）として扱う。
【００６７】
基地局が設置される位置は、他の基地局の位置に依存しない位置である実行可能解である必要がある。グラフ選択部１４３は、実行可能解を構成する各基地局の候補位置をノードとするグラフから、実行可能解である各基地局の候補位置の組合せを維持する完全部分グラフを選択する。
【００６８】
以下、最適化条件（基地局の価格及び設置台数により定まる金額と、各基地局の設置費用とを合計した金額を最小にするという条件）を満たす候補位置を検出する処理（最適化処理）を説明する。最適化処理では、最大の完全部分グラフを選択するよう、すなわち、評価関数の値が最大となるよう、基地局の台数及び設置領域が検出される。
【００６９】
なお、最適化条件を満たす候補位置を検出するアルゴリズムは、以下に例として示すアルゴリズムに限定されるものではなく、グラフから完全部分グラフを求めるアルゴリズムであれば、他のアルゴリズムでもよい。
【００７０】
まず、グラフ選択部１４３は、実行可能解である各基地局の候補位置をノードとする複数のグラフのうちから、初期値とする部分グラフＧを選択する。グラフ選択部１４３は、例えば、候補位置同士の組み合わせの中からランダムに、複数個の組み合わせを選択し、選択した組み合わせを構成する設置位置をノードとする部分グラフＧを初期値とする。なお、初期値とした部分グラフＧは、完全部分グラフである必要はない。
【００７１】
また、グラフ選択部１４３は、評価関数の値が最大となる完全部分グラフであり、且つ、基地局の候補位置の全ての組合せが実行可能解である場合に、当該完全グラフを格納するための変数「Ｂｅｓｔ」を用意する。
【００７２】
グラフ選択部１４３は、終了条件が満たされるまで、部分グラフＧの初期値に対して以下の操作を実行する。ここで、終了条件とは、例えば、部分グラフＧに候補位置ｐを追加又は除外した回数（反復回数）、又は、評価関数の値（評価値）が更新されないことが連続した回数である。なお、終了条件は、これら２つの終了条件のうち１つでもよいし、これら２つの終了条件の組み合わせ、すなわち、「反復回数∧評価値が更新されないことが連続した回数」、又は、「反復回数∨評価値が更新されないことが連続した回数」）でもよい。
【００７３】
また、評価関数の値（評価値）は、グラフ選択部１４３が現在選択している部分グラフＧに含まれている枝の数とする。また、タブーリストには、部分グラフＧ（部分集合）に追加された候補位置ｐ、及び部分グラフＧから除外された候補位置ｐを表すデータが追加される。タブーリストに追加された候補位置ｐは、タブーリストに追加されている期間において、部分グラフＧに対する追加又は除外の操作が禁止される。なお、タブー長は、パラメータとして予め定められるとする。
【００７４】
グラフ選択部１４３は、現在選択している部分グラフＧが完全部分グラフであり、且つ、基地局の候補位置の全ての組合せが実行可能解である場合、その完全部分グラフの評価値が、変数「Ｂｅｓｔ」にすでに格納されている完全部分グラフの評価値よりも高いか否かを判定する。すでに変数「Ｂｅｓｔ」に格納されている完全部分グラフの評価値よりも評価値が高い場合、グラフ選択部１４３は、変数「Ｂｅｓｔ」に格納する完全部分グラフを、新たに評価した完全部分グラフに更新する。
【００７５】
さらに、グラフ選択部１４３は、部分グラフＧに含まれていない候補位置ｐのうち、評価関数（Ｇ∪｛ｐ｝）が最大となった候補位置ｐを部分グラフＧに追加し、新たな部分グラフＧを作成する。また、グラフ選択部１４３は、部分グラフＧに追加した候補位置ｐをタブーリストに追加する。グラフ選択部１４３は、候補位置ｐがタブーリストに追加されている期間、その候補位置ｐを部分グラフＧから除外しないようにする。
【００７６】
一方、グラフ選択部１４３は、現在選択している部分グラフＧが完全部分グラフでない場合、部分グラフＧに含まれている候補位置ｐのうち、評価関数（Ｇ‐｛ｐ｝）の値が最小となった候補位置ｐを部分グラフＧから除外し、新たな部分グラフＧを作成する。また、グラフ選択部１４３は、部分グラフＧから除外した候補位置ｐをタブーリストに追加する。グラフ選択部１４３は、候補位置ｐがタブーリストに追加されている期間、その候補位置ｐを部分グラフＧに追加しないようにする。
【００７７】
また、図７に一例として表されたグラフから、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置（ノード）の全ての組合せが実行可能解である完全部分グラフが、グラフ選択部１４３により選択される（設置位置列挙処理）。
【００７８】
図８には、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置の全ての組合せが実行可能解である完全部分グラフの一例が表されている。図８では、一例として、第３候補位置４３０−２及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−２と、第３候補位置４３０−３及び第４候補位置５３０−１と、第３候補位置４３０−３及び第４候補位置５３０−２との全ての各組合せが、実行可能解であるとする。
【００７９】
グラフ選択部１４３は、選択した完全部分グラフのノードである候補位置により定まる領域を検出する（領域検出処理）。図９には、制約条件及び最適化条件を満たす第３候補位置により定まる領域の例が表されている。図９では、第３候補位置４３０−２を代表点とする領域４４０−２が表されている。また、第３候補位置４３０−３を代表点とする領域４４０−３が表されている。このように、制約条件及び最適化条件が満たされる領域は、候補位置が代表点となるように定められる。また、制約条件及び最適化条件が満たされる領域を表すデータは、グラフ選択部１４３により記憶部１３０に記憶される。
【００８０】
出力部１５０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０から取得して出力する（出力処理）。図１０には、出力された領域の例が表されている。例えば、出力部１５０は、制約条件及び最適化条件が満たされる領域４４０及び５４０を表すデータと、予め定められた範囲（通信エリア）を含む地図データとを取得し、領域４４０及び５４０をその地図に重畳させて画面に表示する。また、出力部１５０は、ＢＩＮを表す図形を、地図に重畳させて画面に表示してもよい。
【００８１】
次に、位置検出装置の動作手順を説明する。
図１１は、位置検出装置の動作手順を表すフローチャートである。最適化部１４０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータと、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータとを、初期設定として、記憶部１３０から取得する（ステップＳ１）。
【００８２】
最適化部１４０は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、基地局が設置される第１候補位置及び第２候補位置とを算出する。
【００８３】
最適化部１４０は、通信エリアにおいてトラヒックの需要を全て収容するという制約条件を満たし、且つ、基地局の価格及び設置台数により定まる金額と各基地局の設置費用とを合計した金額を最小にするという最適化条件を満たす完全部分グラフを選択する。最適化部１４０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０に記憶させる（ステップＳ２）。
【００８４】
出力部１５０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０から取得して出力する。例えば、出力部１５０は、制約条件及び最適化条件が満たされる領域４４０及び５４０を表すデータと、予め定められた範囲（通信エリア）を含む地図データとを取得し、領域４４０及び５４０をその地図に重畳させて画面に表示する（ステップＳ３）。
【００８５】
図１２は、最適化部の動作手順を表すフローチャートである。領域選択部１４２（図１を参照）は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータと、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータとを、初期設定として、取得部１４１から受信する（ステップＳａ１）。
【００８６】
領域選択部１４２は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、基地局が設置される第１候補位置及び第２候補位置とを算出する。
【００８７】
グラフ選択部１４３は、複数の第３候補位置及び複数の第４候補位置（図３を参照）をノードとするグラフを構成する部分グラフを検出する。また、グラフ選択部１４３は、検出した部分グラフのうちから、地図の所定範囲（通信エリア）でトラヒックの需要（式（７）を参照）を満たし、且つ、基地局の価格及びその台数により定まる値と基地局が設置されるＢＩＮ毎の設置費用との合計（式（１）を参照）が最小である実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する（ステップＳａ２）。
グラフ選択部１４３は、選択した完全部分グラフのノードである候補位置により定まる領域を検出する（ステップＳａ３）。
【００８８】
以上のように、位置検出装置１００は、予め定められた範囲（通信エリア）を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件（基地局の設置費用等）を表すデータと、予め定められた制約条件（トラヒックの需要）を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズのＢＩＮを複数定め、前記ＢＩＮ毎の前記制約条件（トラヒックの需要）と、前記ＢＩＮ毎の前記最適化条件（基地局の設置費用等）と、を算出する領域設定部１１０と、基地局の送信電力及び周波数帯に基づいて、前記ＢＩＮ毎の伝搬ロスを算出する特性算出部１２０と、前記ＢＩＮ毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件（トラヒックの需要）を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択する領域選択部１４２と、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件（トラヒックの需要）を満たし、且つ、前記ＢＩＮ毎の最適化条件（基地局の設置費用等）により定まる値（設置費用等の合計）が最適（最小）となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部１４３と、前記選択した完全部分グラフのノードの位置により定まる領域４４０及び領域５４０を出力する出力部１５０と、を備える。
この構成により、制約条件及び最適化条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００８９】
また、領域設定部１１０は、予め定められた最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記ＢＩＮ毎の前記設置費用を算出し、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記ＢＩＮ毎の前記トラヒックの需要を算出し、領域選択部１４２は、前記ＢＩＮ毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、第１候補位置４００及び第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記ＢＩＮ毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、トラヒックの需要の条件、及び基地局の設置費用等最小化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００９０】
＜制約条件について＞
制約条件を満たす候補位置の組み合わせは、制約条件を満たすか否かの判定において参照されるデータに応じて変化する。
制約条件に収容トラヒック量が用いられる場合、通信エリア（サービスエリア）におけるトラヒックの需要を表すデータ、トラヒック需要予測データ、トラヒックの収容量を表すデータ、及び収容量計算式を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【００９１】
ここで、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上は、制約条件を満たすか否かの判定において参照されるとしてもよい。
【００９２】
また、制約条件に所要受信電力が用いられる場合、所要受信電力を表すデータは、制約条件を満たすか否かの判定において参照される。また、制約条件に所要ＳＩＮＲが用いられる場合、所要ＳＩＮＲを表すデータは、制約条件を満たすか否かの判定において参照される。
【００９３】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【００９４】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【００９５】
［第２実施形態］
本発明の第２実施形態について図面を参照して詳細に説明する。第２実施形態では、置局設計における最適化条件の一例として、所要受信電力を満たすカバレッジ範囲を最大化するという条件を設定する。また、置局設計における制約条件の一例として、トラヒックの需要（収容量）を満たすという条件を設定する。以下では、第１実施形態との相違点についてのみ説明する。
【００９６】
領域設定部１１０（図１を参照）には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００（図１を参照）から入力される。ここで、領域設定部１１０には、最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータとが、入力装置２００から入力される。
【００９７】
領域設定部１１０は、受信電力及び信号対干渉雑音比をＢＩＮ毎に算出する。また、領域設定部１１０は、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、ＢＩＮ毎のトラヒックの需要を算出する。
【００９８】
領域選択部１４２（図１を参照）は、ＢＩＮ毎のトラヒックの需要と、トラヒックの収容量を基地局毎に表すデータとに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００とを算出する。以下では、一例として、算出された基地局の台数は２台であるとして説明を続ける。領域選択部１４２は、算出した２台の基地局が設置される第１候補位置及び第２候補位置の近傍から、ＢＩＮをそれぞれ選択する。
【００９９】
グラフ選択部１４３は、第１候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第３候補位置と、第２候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第４候補位置とをノードとするグラフを構成する部分グラフのうちから、地図の所定範囲（通信エリア）でトラヒックの需要を満たし、且つ、所要受信電力を満たすＢＩＮ群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフ（図８を参照）を選択する。
【０１００】
以上のように、領域設定部１１０は、予め定められた最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、設置高を表すデータと、を取得することにより、前記ＢＩＮ毎の受信電力及び信号対干渉雑音比を算出し、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記ＢＩＮ毎の前記トラヒックの需要を算出し、領域選択部１４２は、前記ＢＩＮ毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、第１候補位置４００及び第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力を満たす前記ＢＩＮ群（カバレッジ）が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、トラヒックの需要の条件、及びカバレッジ最大化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【０１０１】
＜制約条件について＞
制約条件に設置費用等が用いられる場合、基地局の価格を表すデータ、基地局の設置費用を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【０１０２】
また、制約条件に収容トラヒック量が用いられる場合、通信エリア（サービスエリア）におけるトラヒックの需要を表すデータ、トラヒック需要予測データ、トラヒックの収容量を表すデータ、及び収容量計算式を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【０１０３】
ここで、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上は、制約条件を満たすか否かの判定において参照されるとしてもよい。
【０１０４】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【０１０５】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【０１０６】
［第３実施形態］
本発明の第３実施形態について図面を参照して詳細に説明する。第３実施形態では、置局設計における最適化条件の一例として、トラヒックの収容量を最大化するという条件を設定する。また、置局設計における制約条件の一例として、基地局の設置費用等の合計を所定閾値以下にするという条件を設定する。以下では、第１実施形態及び第２実施形態との相違点についてのみ説明する。
【０１０７】
領域設定部１１０（図１を参照）には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００（図１を参照）から入力される。ここで、領域設定部１１０には、最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータとが、入力装置２００から入力される。
【０１０８】
領域設定部１１０は、トラヒックの収容量をＢＩＮ毎に算出する。また、領域設定部１１０は、予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、ＢＩＮ毎の基地局の設置費用を算出する。
【０１０９】
領域選択部１４２（図１を参照）は、基地局の価格及び台数により定まる値と、基地局が設置されるＢＩＮ毎の基地局の設置費用との合計が所定閾値以下となる基地局の台数の最大値と、１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００とを算出する。領域選択部１４２は、合わせてこの台数の最大値以下となる基地局が設置される第１候補位置及び第２候補位置の近傍から、ＢＩＮをそれぞれ選択する。
【０１１０】
グラフ選択部１４３は、第１候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第３候補位置と、第２候補位置の近傍から選択したＢＩＮに定められた複数の第４候補位置（図３を参照）と、をノードとするグラフを構成する部分グラフのうちから、基地局の価格及び台数により定まる値と、基地局が設置されるＢＩＮ毎の基地局の設置費用との合計が所定閾値以下であり、且つ、基地局が設置されるＢＩＮ毎のトラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフ（図８を参照）を選択する。
【０１１１】
また、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上が、制約条件を満たすか否かの判定において参照されるとしてもよい。
【０１１２】
以上のように、領域設定部１１０は、予め定められた最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記ＢＩＮ毎の前記トラヒックの収容量を算出し、予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記ＢＩＮ毎の前記設置費用を算出し、領域選択部１４２は、基地局の価格及び前記台数により定まる値と、基地局が設置される前記ＢＩＮ毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記ＢＩＮ毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、設置費用等の条件、及びトラヒックの収容量最大化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【０１１３】
＜制約条件について＞
制約条件に費用が用いられる場合、基地局の価格を表すデータ、基地局の設置費用を表すデータのうち１つ以上が、制約条件を満たすか否かの判定において参照される。
また、制約条件に所要受信電力が用いられる場合、所要受信電力を表すデータは、制約条件を満たすか否かの判定において参照される。また、制約条件に所要ＳＩＮＲが用いられる場合、所要ＳＩＮＲを表すデータは、制約条件を満たすか否かの判定において参照される。
【０１１４】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【０１１５】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【０１１６】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【０１１７】
例えば、位置検出装置は、入力装置から入力される各種データを予め記憶しているデータベースを備えてもよい。位置検出装置の各部は、入力装置から入力された各種データの代わりに、データベースに記憶されている各種データを取得して、上記に説明した動作を実行してもよい。
【０１１８】
また、例えば、上記の実施形態では、基地局が展開されていない通信エリアに新規に基地局を設置する場合について説明したが、位置検出装置は、基地局が既に展開されている通信エリアに基地局を増設する場合にも適用可能である。この場合、領域設定部は、既設の基地局が設置されている位置を表すデータを、入力装置又はデータベースから取得する。
【０１１９】
また、例えば、上記の実施形態では、置局設計における置局配置について説明したが、置局配置のみならず、位置検出装置は、基地局の送信電力、及び基地局のパラメータ（例えば、アンテナチルト角）を、置局配置と併せて最適化してもよい。
【０１２０】
また、例えば、設置される基地局は、1種類に限定されず、例えば、マクロ基地局、ピコ基地局といった複数種類でもよい。この場合、各基地局の種類毎に、伝搬ロスのモデル式が定められてもよい。
【０１２１】
また、例えば、候補位置を表すデータは、候補位置の各座標（例えば、緯度及び経度）を表すデータの集合により表現されてもよいし、各候補位置を含む領域（範囲）を表すデータにより表現されてもよい。領域を表すデータにより候補位置が表現されている場合、候補位置を含む領域を表すデータに加えて、候補位置の総数を表すデータ、又はＢＩＮ毎の候補位置数を表すデータが、位置検出装置に入力されてもよい。
【０１２２】
なお、以上に説明した位置検出装置を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録し、そのプログラムをコンピュータシステムに読み込ませて実行するようにしてもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【０１２３】
１００…位置検出装置、１１０…領域設定部、１２０…特性算出部、１３０…記憶部、１４０…最適化部、１４１…取得部、１４２…領域選択部、１４３…グラフ選択部と、１５０…出力部、２００…入力装置、４００…第１候補位置、４１０…近傍範囲、４２０−１〜４２０−４…ＢＩＮ、４３０−１〜４３０−１３…第３候補位置、４４０，４４０−２，４４０−３…領域、５００…第２候補位置、５１０…近傍範囲、５２０−１〜５２０−４…ＢＩＮ、５３０−１〜５３０−１３…第４候補位置、５４０，５４０−２，５４０−３…領域
【技術分野】
【０００１】
本発明は、置局設計における、位置検出装置及び位置検出プログラムに関する。
【背景技術】
【０００２】
無線通信システム、特に携帯電話に代表される移動体通信システムでは、通信エリアを実際に構築する前に、基地局を設置する位置を設計者が事前に検討する置局設計が行われる。置局設計では、通信エリアを構築する対象とされた範囲の地図データが、予め定められた大きさの複数の領域に分割される。基地局を設置する位置は、これら領域毎の受信信号強度等に基づいて、制約条件（例えば、トラヒックの需要の条件）を満たすよう検討される。
【０００３】
このような置局設計において、基地局の配置パターンの作成等の手間を省くとともに、最適な配置パターンを得ることを目的とした基地局配置パターン決定方法が、特許文献１に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００１−２８５９２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、実際の設置では地理的な制約があるため、置局設計によって事前に定められた位置に基地局を設置できるとは限らない。そこで、置局設計によって事前に定められた位置の代わりに、その位置から離れた位置に、基地局を実際に設置することとなった場合、置局設計では満たされていた制約条件、及び最適化条件（例えば、設置費用等を最小にするという条件）が、実際の設置では必ずしも満たされるとは限らない。このように、特許文献１に開示された方法により検出された位置は、基地局を設置する位置としては、自由度が低いという問題がある。
【０００６】
本発明は、前記の点に鑑みてなされたものであり、基地局を設置する自由度が高い位置を検出する位置検出装置及び位置検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記の課題を解決するためになされたものであり、予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する領域設定部と、基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する特性算出部と、前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する領域選択部と、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、前記選択した完全部分グラフのノードの位置により定まる領域を出力する出力部と、を備えることを特徴とする位置検出装置である。
【０００８】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、前記領域選択部が、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記領域毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【０００９】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータと、を取得することにより、前記領域毎の受信電力及び信号対干渉雑音比を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、前記領域選択部が、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力及び前記所要信号対干渉雑音比を満たす前記領域群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【００１０】
また、本発明は、前記領域設定部が、前記最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記領域毎の前記トラヒックの収容量を算出し、前記予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記領域選択部が、基地局の価格及び前記台数により定まる値と、基地局が設置される前記領域毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、前記グラフ選択部が、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記領域毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択することを特徴とする位置検出装置である。
【００１１】
また、本発明は、コンピュータに、予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する手順と、基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する手順と、前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する手順と、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、前記選択した完全部分グラフのノードの位置により定まる領域を出力する手順と、を実行させるための位置検出プログラムである。
【発明の効果】
【００１２】
本発明によれば、制約条件及び最適化条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態における、位置検出装置の構成を表すブロック図である。
【図２】本発明の一実施形態における、地図データの例を表す図である。
【図３】本発明の一実施形態における、基地局を設置する位置を含む地図の所定範囲を表す図である。
【図４】本発明の一実施形態における、ＭＣＳテーブルの例を示す表である。
【図５】本発明の一実施形態における、周波数帯域幅と、サブキャリア数と、リソースブロック（ＲＢ）数の関係例を示す表である。
【図６】本発明の一実施形態における、第３候補位置と第４候補位置との組み合わせの一例を表す図である。
【図７】本発明の一実施形態における、制約条件を満たす第３候補位置及び第４候補位置の組み合わせの一例を表す図である。
【図８】本発明の一実施形態における、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置の全ての組合せが実行可能解である完全部分グラフの一例を表す図である。
【図９】本発明の一実施形態における、制約条件及び最適化条件を満たす第３候補位置により定まる領域の例を表す図である。
【図１０】本発明の一実施形態における、出力された領域の例を表す図である。
【図１１】本発明の一実施形態における、位置検出装置の動作手順を表すフローチャートである。
【図１２】本発明の一実施形態における、最適化部の動作手順を表すフローチャートである。
【発明を実施するための形態】
【００１４】
［第１実施形態］
本発明の第１実施形態について図面を参照して詳細に説明する。第１実施形態では、置局設計における最適化条件の一例として、基地局の価格及び設置台数により定まる金額と、各基地局の設置費用とを合計した金額を最小にするという条件を設定する。また、置局設計における制約条件の一例として、通信エリアにおけるトラヒックの需要を全て収容する（トラヒックの需要を満たす収容量を通信エリアで確保する）という条件を設定する。
【００１５】
図１には、位置検出装置の構成がブロック図により表されている。位置検出装置１００は、入力装置２００から取得した各種データに基づいて、トラヒックの需要を全て収容するという条件（制約条件）と、基地局の設置費用等を最小にするという条件（最適化条件）とを満たす基地局の設置位置を、基地局を設置する候補位置をノードとするグラフ（図７及び図８を用いて後述する）に基づいて検出し、検出した設置位置により定まる設置領域を出力する。これにより、位置検出装置１００は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００１６】
まず、位置検出装置の構成、及び入力装置について説明する。
入力装置２００は、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとを、位置検出装置１００に入力する。
【００１７】
また、地図データは、所定範囲（通信エリア）を表す地図データである。また、予め定められたサイズを表すデータとは、地図がメッシュ状に分割された各領域（以下、「ＢＩＮ」という）のサイズを表すデータである。また、予め定められた最適化条件を表すデータとは、本実施形態では、基地局の設置費用を表すデータである。なお、最適化条件を表すデータには、最適化処理における終了条件（閾値など）を表すデータが含まれていてもよい。
【００１８】
また、予め定められた制約条件を表すデータとは、本実施形態では、トラヒックの需要（要求される収容量）を表すデータである。なお、トラヒックの需要を表すデータは、将来のトラヒックの需要が予測されたデータ（以下、「トラヒック需要予測データ」という）でもよい。
【００１９】
また、予め定められた土地区分データとは、基地局を設置する位置が住宅地であるか又は森林地帯であるか等を、ＢＩＮ毎に表すデータである。この土地区分データは、例えば、基地局の設置費用がＢＩＮ毎に算出される際に参照される。なお、土地区分が考慮されなくてもよい場合、土地区分データは、位置検出装置１００に入力されなくてもよい。
【００２０】
入力装置２００は、基地局の周波数帯を表すデータと、基地局の送信電力を表すデータと、伝搬ロスのモデル式を表すデータとを、位置検出装置１００に入力する。ここで、伝搬ロスのモデル式は、伝搬ロスを算出する手順を表す式であり、例えば、レイ・トレース、Ｗａｌｆｉｓｃｈ−池上モデル等の伝搬ロスのモデル式である。
【００２１】
なお、伝搬ロスのモデル式のパラメータには、土地区分データを表すパラメータが含まれていてもよい。伝搬ロスのモデル式にこのパラメータが含まれることで、位置検出装置１００は、土地区分毎に伝搬ロスを精度よく算出することができる。なお、入力装置２００は、伝搬ロスのモデル式を表すデータの代わりに、伝搬ロスを直接表すデータを位置検出装置１００に入力してもよい。
【００２２】
入力装置２００は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータ（図４を用いて後述する）を、位置検出装置１００に入力する。
【００２３】
位置検出装置１００は、領域設定部１１０と、特性算出部１２０と、記憶部１３０と、最適化部１４０と、出力部１５０とを備える。
【００２４】
領域設定部１１０には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００から入力される。
【００２５】
領域設定部１１０は、入力されたサイズでメッシュ状に地図を分割することにより、入力されたサイズのＢＩＮを地図に複数定める。図２には、地図データの例が表されている。各ＢＩＮの形状は、例えば、矩形状である。
【００２６】
領域設定部１１０は、地図に定めたＢＩＮと、予め定められた制約条件（トラヒックの需要を表すデータ）とに基づいて、トラヒックの需要（要求される収容量）をＢＩＮ毎に算出する。また、領域設定部１１０は、地図に定めたＢＩＮと、予め定められた最適化条件を表すデータ（基地局の設置費用を表すデータ）とに基づいて、基地局の設置費用をＢＩＮ毎に算出する。ここで、領域設定部１１０は、ＢＩＮ毎の土地区分データに基づいて、基地局の設置費用をＢＩＮ毎に算出してもよい。ここで、領域設定部１１０は、１つのＢＩＮに含まれる複数の土地区分のうち、最も面積率が高い土地区分（代表）を、そのＢＩＮの土地区分としてもよい。
【００２７】
領域設定部１１０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データとを、記憶部１３０に記憶させる。
【００２８】
特性算出部１２０には、基地局の送信電力を表すデータと、基地局の周波数帯を表すデータと、伝搬ロスのモデル式を表すデータとが、入力装置２００から入力される。
【００２９】
特性算出部１２０は、基地局の送信電力を表すデータと、その周波数帯を表すデータと、伝搬ロスのモデル式を表すデータとに基づいて、ＢＩＮ毎の伝搬ロスを算出し、算出したＢＩＮ毎の伝搬ロスを表すデータを、記憶部１３０に記憶させる。
【００３０】
記憶部１３０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データと、ＢＩＮ毎の伝搬ロスを表すデータとを記憶する。
【００３１】
また、記憶部１３０には、基地局の価格を表すデータが、入力装置２００から入力される。また、記憶部１３０には、トラヒックの収容量（収容トラヒック量）を算出するためのモデル式（収容量計算式）を表すデータ、又は、トラヒックの収容量を基地局毎に表すデータが、入力装置２００から入力される。記憶部１３０は、これらのデータも記憶する。ここで、記憶部１３０は、トラヒックの収容量を算出するためのモデル式を表すデータを記憶する代わりに、トラヒックの収容量を直接表すデータを記憶してもよい。なお、トラヒックの収容量を算出するためのモデル式のパラメータには、地図の所定範囲（通信エリア）に存在する建物毎の建物高を表すパラメータが含まれていてもよい。
【００３２】
最適化部１４０は、トラヒックの需要を満たす収容量を地図の所定範囲（通信エリア）で確保するという制約条件を満たし、且つ、基地局の価格及び設置台数により定まる金額と各基地局の設置費用とを合計した金額を最小にするという最適化条件を満たす完全部分グラフ（図８を用いて後述する）を選択する（最適化処理）。
【００３３】
最適化部１４０は、取得部１４１と、領域選択部１４２と、グラフ選択部１４３とを有する。取得部１４１は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲（通信エリア）の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータとを、記憶部１３０から取得する。また、取得部１４１は、トラヒックの収容量を算出するためのモデル式を表すデータと、トラヒックの収容量を基地局毎に表すデータとのうち、記憶部１３０に記憶されているほうのデータを、記憶部１３０から取得する。
【００３４】
領域選択部１４２は、取得部１４１が記憶部１３０から取得したこれらのデータを、取得部１４１から受信する（初期設定）。領域選択部１４２は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、目的関数（後述）の値が最小となるように、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局が設置される第１候補位置及び第２候補位置と、基地局の台数とを算出する。
【００３５】
ここで、第１候補位置とは、置局設計の際に１つの組とされる基地局同士の一方を構成する１台以上の基地局をそれぞれ設置する１箇所以上の候補位置である。また、第２候補位置とは、置局設計の際に１つの組とされる基地局同士の他方を構成する１台以上の基地局をそれぞれ設置する１箇所以上の候補位置である。
【００３６】
以下では、一例として、領域選択部１４２が算出した基地局の台数は２台であるとして説明を続ける。なお、算出した基地局の台数が３台以上である場合でも、最適化部１４０は、各基地局の設置位置を１つの組として扱えばよい。
【００３７】
領域選択部１４２は、算出した２台の基地局が設置される第１候補位置及び第２候補位置の近傍から、それぞれＢＩＮを選択する。図３には、基地局を設置する位置を含む地図の所定範囲（通信エリア）が表されている。図３では、第１候補位置４００を中心とする近傍範囲４１０に含まれるＢＩＮ４２０−１〜４２０−４が、複数のＢＩＮから領域選択部１４２により選択されたとする。同様に、第２候補位置５００を中心とする近傍範囲５１０に含まれるＢＩＮ５２０−１〜５２０−４が、複数のＢＩＮから領域選択部１４２により選択されたとする。
【００３８】
また、ＢＩＮ４２０−１〜４２０−４には、複数の第３候補位置が、領域選択部１４２により定められたとする。同様に、ＢＩＮ５２０−１〜５２０−４には、複数の第４候補位置が、領域選択部１４２により定められたとする。なお、これら候補位置の配置は、一例である。
【００３９】
次に、基地局の設置費用等を算出する方法の一例、及び基地局のトラヒック収容量を算出する方法の一例を説明する。ここで、通信システムにＯＦＤＭＡ（Ｏｒｔｈｏｇｏｎａｌ Ｆｒｅｑｕｅｎｃｙ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）が用いられているものとして説明するが、通信システムは、ＯＦＤＭＡに限らなくてよい。例えば、通信システムは、ＣＤＭＡ（Ｗｉｄｅｂａｎｄ Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）システムでもよい。
【００４０】
以下では、ｉは、ＢＩＮの識別子を表す。また、その集合は、Ｉと表記される。また、ｊは、基地局の設置位置の識別子を表す。また、その集合は、Ｊと表記される。また、Ｉｊは、位置ｊに設置された基地局にカバーされるＢＩＮｉの集合を表す。また、Ｔｘは、基地局の送信電力を表す。また、ｃは、基地局の価格を表す。また、ｃｊは、位置ｊに基地局を設置する場合の設置費用を表す。また、ｗｉは、ＢＩＮｉにおけるトラヒックの需要を表す。また、ηは、ノイズを表す。また、ｇｉｊは、ｊに設置された基地局からＢＩＮｉまでの伝搬ロスを表す。また、ｄｉｊは、ＢＩＮｉに在る無線局が、位置ｊに設置された基地局に接続した場合に、無線リソースが全て割当てられたと仮定された場合のスループット値を表す。また、ｘｊの値が１である場合、ｘｊは、ｊに基地局が配置されていることを表す。一方、ｘｊの値が０である場合、ｘｊは、ｊに基地局が配置されていないことを表す。
【００４１】
まず、基地局の設置費用等を算出する方法の一例について説明する。領域選択部１４２は、式（１）により、基地局の設置費用を算出する。
【００４２】
【数１】
【００４３】
次に、基地局のトラヒック収容量を算出する方法の一例について説明する。領域選択部１４２は、基地局がカバーするＢＩＮに対する信号対干渉雑音比（ＳＩＮＲ）に基づいて、そのＢＩＮに対するスループット値を算出する。また、領域選択部１４２は、算出したスループット値を用いて、その基地局が収容するトラヒックの収容量を算出する。また、領域選択部１４２は、位置ｊに設置された基地局がカバーするＢＩＮｉに対するＳＩＮＲｉｊを、式（２）により算出する。
【００４４】
【数２】
【００４５】
ここで、式（２）の分母の第1項は、他の基地局からの干渉を表す。また、式（２）の分母の第２項は、雑音成分を表す。
【００４６】
また、領域選択部１４２は、ＢＩＮ毎にスループット値を算出する。ここで、領域選択部１４２は、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及びＭＣＳ（Ｍｏｄｕｌａｔｉｏｎ ａｎｄ Ｃｏｄｉｎｇ Ｓｃｈｅｍｅ）テーブルデータを参照する。
【００４７】
信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルには、信号対干渉雑音比（ＳＩＮＲ）と、パケットエラーレート（ＰＥＲ）とが対応付けられて登録されている。また、ＭＣＳテーブルには、変調方式と、符号化率と、ＳＩＮＲ閾値とが対応付けられて登録されている。図４には、ＭＣＳテーブルの例が示されている。変調方式には、例えば、ＱＰＳＫ (２)、１６ＱＡＭ (４)及び６４ＱＡＭ (６)がある。
【００４８】
ここで、下り方向の通信にＯＦＤＭＡを採用するＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）を例に、スループット値の算出を説明する。ＬＴＥでは、時間×周波数の無線リソースは、リソースブロック（Ｒｅｓｏｕｒｃｅ Ｂｌｏｃｋ，ＲＢ）単位で構成されている。また、リソースブロックは、７ＯＦＤＭシンボル（０．５［ｍｓ］）×１２サブキャリアで構成されている。１リソースブロックにより送信可能であるビット数は、式（３）により表わされる。
【００４９】
【数３】
【００５０】
式（３）において、[ＭＩＭＯ ｅｆｆｉｃｉｅｎｃｙ] は、そのＢＩＮにおけるＭＩＭＯの効率を表す。また、[Ｍｏｄｕｌａｔｉｏｎ]は、変調方式を表す（図４を参照）。また、 [Ｃｏｄｉｎｇ ｒａｔｅ]は、符号化率を表す（図４を参照）。また、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]は、１リソースブロックあたりのサブキャリア数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝１２とする。また、[＃ ｏｆ ＯＦＤＭ ｓｙｍｂｏｌ／ＲＢ]は、１リソースブロックあたりのＯＦＤＭシンボル数を表す。この例では、[＃ ｏｆ ｓｕｂｃａｒｒｉｅｒ／ＲＢ]＝７とする。また、ＰＥＲは、パケットエラーレートを表す。ＰＥＲは、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルにより、ＳＩＮＲ値を用いて算出される。
【００５１】
１リソースブロックは０．５［ｍｓ］であることから、対象とするシステムの周波数方向のリソースブロック数を＃ＲＢとして、位置ｊに設置された基地局がカバーするＢＩＮｉに、リソースブロックが全て割り当てられた場合、スループットｄｉｊは、式（４）により表される。
【００５２】
【数４】
【００５３】
なお、割り当てられる無線リソースは、そのリソース量が制限されてもよい。例えば、フェージング等の変動要因に対するマージンとして、全無線リソースの８０［％］まで無線リソースが割り当てられるようにする場合、式（４）の＃ＲＢを、０．８×＃ＲＢに置き換えることにより、領域選択部１４２は、このような場合にも対応可能である。
【００５４】
また、周波数方向のリソースブロック数は、対象とするシステムの周波数帯域幅に依存する。図５には、周波数帯域幅と、サブキャリア数と、リソースブロック（ＲＢ）数との関係例が、表により示されている。例えば、周波数帯域幅１．４［ＭＨｚ］に対応するサブキャリア数は、７６である。また、周波数帯域幅１．４［ＭＨｚ］に対応するリソースブロック数は、６である。
【００５５】
位置ｊに設置された基地局がカバーするＢＩＮｉに対して必要な無線リソース量の割合は、式（５）により表される。
【００５６】
【数５】
【００５７】
また、式（６）の値が1以下である場合、式（６）は、位置ｊに設置された基地局が、自局がカバーする全てのＢＩＮにおけるトラヒックの需要を、全て収容することができることを表す。
【００５８】
【数６】
【００５９】
一方、式（６）の値が1を超えている場合、式（６）は、位置ｊに設置された基地局が、自局がカバーする全てのＢＩＮにおけるトラヒックの需要を、全ては収容することができないことを表す。したがって、トラヒックの収容量（収容トラヒック量）の条件式は、式（７）により表される。
【００６０】
【数７】
【００６１】
ここで、ξは、通信エリアの各ＢＩＮにおいて収容されるべきトラヒック量の比率（０＜ξ≦１）を表す係数である。なお、ξの値は、パラメータとして予め定められているものとする。本実施形態では、ξ＝１とする。
【００６２】
図１に戻り、位置検出装置の構成の説明を続ける。グラフ選択部１４３は、複数の第３候補位置及び複数の第４候補位置（図３を参照）をノード（節点）とするグラフを構成する部分グラフを検出する。
【００６３】
候補位置をノードとするグラフについて説明する。図６には、第３候補位置と第４候補位置との組み合わせの一例が、鎖線等により表されている。以下では、第１候補位置４００を、第３候補位置４３０−１と表記する。また、第２候補位置５００を、第４候補位置５３０−１と表記する。また、グラフ選択部１４３は、図６では、第３候補位置４３０−１〜４３０−１３と、第４候補位置５３０−１〜５３０−１３との全ての組み合わせについて、トラヒックの需要を収容することが可能であるか否かを、組み合わせ毎に判定する（式（７）を参照）。
【００６４】
また、グラフ選択部１４３は、検出したグラフから、地図の所定範囲（通信エリア）でトラヒックの需要（式（７）を参照）を満たし、且つ、基地局の価格及びその台数により定まる値と基地局が設置されるＢＩＮ毎の設置費用との合計（式（１）を参照）が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
【００６５】
グラフ選択部１４３は、トラヒックの需要が全て収容されるか否かを、第３候補位置と第４候補位置との組み合わせ毎に判定する。図７には、制約条件（通信エリアにおけるトラヒックの需要を全て収容するという条件）を満たす第３候補位置及び第４候補位置の組み合わせの一例が表されている。図７では、各組み合わせのうち、第３候補位置４３０−１及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−２と、第３候補位置４３０−３及び第４候補位置５３０−１と、第３候補位置４３０−３及び第４候補位置５３０−２とで、制約条件が満たされているとする。
【００６６】
ここで、グラフ選択部１４３は、基地局を設置する候補位置を、グラフ理論におけるノード（節点）として扱う。
【００６７】
基地局が設置される位置は、他の基地局の位置に依存しない位置である実行可能解である必要がある。グラフ選択部１４３は、実行可能解を構成する各基地局の候補位置をノードとするグラフから、実行可能解である各基地局の候補位置の組合せを維持する完全部分グラフを選択する。
【００６８】
以下、最適化条件（基地局の価格及び設置台数により定まる金額と、各基地局の設置費用とを合計した金額を最小にするという条件）を満たす候補位置を検出する処理（最適化処理）を説明する。最適化処理では、最大の完全部分グラフを選択するよう、すなわち、評価関数の値が最大となるよう、基地局の台数及び設置領域が検出される。
【００６９】
なお、最適化条件を満たす候補位置を検出するアルゴリズムは、以下に例として示すアルゴリズムに限定されるものではなく、グラフから完全部分グラフを求めるアルゴリズムであれば、他のアルゴリズムでもよい。
【００７０】
まず、グラフ選択部１４３は、実行可能解である各基地局の候補位置をノードとする複数のグラフのうちから、初期値とする部分グラフＧを選択する。グラフ選択部１４３は、例えば、候補位置同士の組み合わせの中からランダムに、複数個の組み合わせを選択し、選択した組み合わせを構成する設置位置をノードとする部分グラフＧを初期値とする。なお、初期値とした部分グラフＧは、完全部分グラフである必要はない。
【００７１】
また、グラフ選択部１４３は、評価関数の値が最大となる完全部分グラフであり、且つ、基地局の候補位置の全ての組合せが実行可能解である場合に、当該完全グラフを格納するための変数「Ｂｅｓｔ」を用意する。
【００７２】
グラフ選択部１４３は、終了条件が満たされるまで、部分グラフＧの初期値に対して以下の操作を実行する。ここで、終了条件とは、例えば、部分グラフＧに候補位置ｐを追加又は除外した回数（反復回数）、又は、評価関数の値（評価値）が更新されないことが連続した回数である。なお、終了条件は、これら２つの終了条件のうち１つでもよいし、これら２つの終了条件の組み合わせ、すなわち、「反復回数∧評価値が更新されないことが連続した回数」、又は、「反復回数∨評価値が更新されないことが連続した回数」）でもよい。
【００７３】
また、評価関数の値（評価値）は、グラフ選択部１４３が現在選択している部分グラフＧに含まれている枝の数とする。また、タブーリストには、部分グラフＧ（部分集合）に追加された候補位置ｐ、及び部分グラフＧから除外された候補位置ｐを表すデータが追加される。タブーリストに追加された候補位置ｐは、タブーリストに追加されている期間において、部分グラフＧに対する追加又は除外の操作が禁止される。なお、タブー長は、パラメータとして予め定められるとする。
【００７４】
グラフ選択部１４３は、現在選択している部分グラフＧが完全部分グラフであり、且つ、基地局の候補位置の全ての組合せが実行可能解である場合、その完全部分グラフの評価値が、変数「Ｂｅｓｔ」にすでに格納されている完全部分グラフの評価値よりも高いか否かを判定する。すでに変数「Ｂｅｓｔ」に格納されている完全部分グラフの評価値よりも評価値が高い場合、グラフ選択部１４３は、変数「Ｂｅｓｔ」に格納する完全部分グラフを、新たに評価した完全部分グラフに更新する。
【００７５】
さらに、グラフ選択部１４３は、部分グラフＧに含まれていない候補位置ｐのうち、評価関数（Ｇ∪｛ｐ｝）が最大となった候補位置ｐを部分グラフＧに追加し、新たな部分グラフＧを作成する。また、グラフ選択部１４３は、部分グラフＧに追加した候補位置ｐをタブーリストに追加する。グラフ選択部１４３は、候補位置ｐがタブーリストに追加されている期間、その候補位置ｐを部分グラフＧから除外しないようにする。
【００７６】
一方、グラフ選択部１４３は、現在選択している部分グラフＧが完全部分グラフでない場合、部分グラフＧに含まれている候補位置ｐのうち、評価関数（Ｇ‐｛ｐ｝）の値が最小となった候補位置ｐを部分グラフＧから除外し、新たな部分グラフＧを作成する。また、グラフ選択部１４３は、部分グラフＧから除外した候補位置ｐをタブーリストに追加する。グラフ選択部１４３は、候補位置ｐがタブーリストに追加されている期間、その候補位置ｐを部分グラフＧに追加しないようにする。
【００７７】
また、図７に一例として表されたグラフから、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置（ノード）の全ての組合せが実行可能解である完全部分グラフが、グラフ選択部１４３により選択される（設置位置列挙処理）。
【００７８】
図８には、制約条件及び最適化条件を満たす候補位置をノードとし、基地局の候補位置の全ての組合せが実行可能解である完全部分グラフの一例が表されている。図８では、一例として、第３候補位置４３０−２及び第４候補位置５３０−１と、第３候補位置４３０−２及び第４候補位置５３０−２と、第３候補位置４３０−３及び第４候補位置５３０−１と、第３候補位置４３０−３及び第４候補位置５３０−２との全ての各組合せが、実行可能解であるとする。
【００７９】
グラフ選択部１４３は、選択した完全部分グラフのノードである候補位置により定まる領域を検出する（領域検出処理）。図９には、制約条件及び最適化条件を満たす第３候補位置により定まる領域の例が表されている。図９では、第３候補位置４３０−２を代表点とする領域４４０−２が表されている。また、第３候補位置４３０−３を代表点とする領域４４０−３が表されている。このように、制約条件及び最適化条件が満たされる領域は、候補位置が代表点となるように定められる。また、制約条件及び最適化条件が満たされる領域を表すデータは、グラフ選択部１４３により記憶部１３０に記憶される。
【００８０】
出力部１５０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０から取得して出力する（出力処理）。図１０には、出力された領域の例が表されている。例えば、出力部１５０は、制約条件及び最適化条件が満たされる領域４４０及び５４０を表すデータと、予め定められた範囲（通信エリア）を含む地図データとを取得し、領域４４０及び５４０をその地図に重畳させて画面に表示する。また、出力部１５０は、ＢＩＮを表す図形を、地図に重畳させて画面に表示してもよい。
【００８１】
次に、位置検出装置の動作手順を説明する。
図１１は、位置検出装置の動作手順を表すフローチャートである。最適化部１４０は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータと、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータとを、初期設定として、記憶部１３０から取得する（ステップＳ１）。
【００８２】
最適化部１４０は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、基地局が設置される第１候補位置及び第２候補位置とを算出する。
【００８３】
最適化部１４０は、通信エリアにおいてトラヒックの需要を全て収容するという制約条件を満たし、且つ、基地局の価格及び設置台数により定まる金額と各基地局の設置費用とを合計した金額を最小にするという最適化条件を満たす完全部分グラフを選択する。最適化部１４０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０に記憶させる（ステップＳ２）。
【００８４】
出力部１５０は、制約条件及び最適化条件が満たされる領域を表すデータを、記憶部１３０から取得して出力する。例えば、出力部１５０は、制約条件及び最適化条件が満たされる領域４４０及び５４０を表すデータと、予め定められた範囲（通信エリア）を含む地図データとを取得し、領域４４０及び５４０をその地図に重畳させて画面に表示する（ステップＳ３）。
【００８５】
図１２は、最適化部の動作手順を表すフローチャートである。領域選択部１４２（図１を参照）は、ＢＩＮ毎の基地局の設置費用を表すデータと、ＢＩＮ毎のトラヒックの需要を表すデータと、所定範囲の地図データと、ＢＩＮ毎の伝搬ロスを表すデータと、基地局の価格を表すデータと、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータとを、初期設定として、取得部１４１から受信する（ステップＳａ１）。
【００８６】
領域選択部１４２は、トラヒックの収容量を算出するためのモデル式を表すデータ、又はトラヒックの収容量を基地局毎に表すデータと、ＢＩＮ毎のトラヒックの需要とに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、基地局が設置される第１候補位置及び第２候補位置とを算出する。
【００８７】
グラフ選択部１４３は、複数の第３候補位置及び複数の第４候補位置（図３を参照）をノードとするグラフを構成する部分グラフを検出する。また、グラフ選択部１４３は、検出した部分グラフのうちから、地図の所定範囲（通信エリア）でトラヒックの需要（式（７）を参照）を満たし、且つ、基地局の価格及びその台数により定まる値と基地局が設置されるＢＩＮ毎の設置費用との合計（式（１）を参照）が最小である実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する（ステップＳａ２）。
グラフ選択部１４３は、選択した完全部分グラフのノードである候補位置により定まる領域を検出する（ステップＳａ３）。
【００８８】
以上のように、位置検出装置１００は、予め定められた範囲（通信エリア）を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件（基地局の設置費用等）を表すデータと、予め定められた制約条件（トラヒックの需要）を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズのＢＩＮを複数定め、前記ＢＩＮ毎の前記制約条件（トラヒックの需要）と、前記ＢＩＮ毎の前記最適化条件（基地局の設置費用等）と、を算出する領域設定部１１０と、基地局の送信電力及び周波数帯に基づいて、前記ＢＩＮ毎の伝搬ロスを算出する特性算出部１２０と、前記ＢＩＮ毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件（トラヒックの需要）を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択する領域選択部１４２と、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件（トラヒックの需要）を満たし、且つ、前記ＢＩＮ毎の最適化条件（基地局の設置費用等）により定まる値（設置費用等の合計）が最適（最小）となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部１４３と、前記選択した完全部分グラフのノードの位置により定まる領域４４０及び領域５４０を出力する出力部１５０と、を備える。
この構成により、制約条件及び最適化条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００８９】
また、領域設定部１１０は、予め定められた最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記ＢＩＮ毎の前記設置費用を算出し、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記ＢＩＮ毎の前記トラヒックの需要を算出し、領域選択部１４２は、前記ＢＩＮ毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、第１候補位置４００及び第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記ＢＩＮ毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、トラヒックの需要の条件、及び基地局の設置費用等最小化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【００９０】
＜制約条件について＞
制約条件を満たす候補位置の組み合わせは、制約条件を満たすか否かの判定において参照されるデータに応じて変化する。
制約条件に収容トラヒック量が用いられる場合、通信エリア（サービスエリア）におけるトラヒックの需要を表すデータ、トラヒック需要予測データ、トラヒックの収容量を表すデータ、及び収容量計算式を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【００９１】
ここで、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上は、制約条件を満たすか否かの判定において参照されるとしてもよい。
【００９２】
また、制約条件に所要受信電力が用いられる場合、所要受信電力を表すデータは、制約条件を満たすか否かの判定において参照される。また、制約条件に所要ＳＩＮＲが用いられる場合、所要ＳＩＮＲを表すデータは、制約条件を満たすか否かの判定において参照される。
【００９３】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【００９４】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【００９５】
［第２実施形態］
本発明の第２実施形態について図面を参照して詳細に説明する。第２実施形態では、置局設計における最適化条件の一例として、所要受信電力を満たすカバレッジ範囲を最大化するという条件を設定する。また、置局設計における制約条件の一例として、トラヒックの需要（収容量）を満たすという条件を設定する。以下では、第１実施形態との相違点についてのみ説明する。
【００９６】
領域設定部１１０（図１を参照）には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００（図１を参照）から入力される。ここで、領域設定部１１０には、最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータとが、入力装置２００から入力される。
【００９７】
領域設定部１１０は、受信電力及び信号対干渉雑音比をＢＩＮ毎に算出する。また、領域設定部１１０は、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、ＢＩＮ毎のトラヒックの需要を算出する。
【００９８】
領域選択部１４２（図１を参照）は、ＢＩＮ毎のトラヒックの需要と、トラヒックの収容量を基地局毎に表すデータとに基づいて、地図の所定範囲（通信エリア）でトラヒックの需要を満たす収容量を確保するために必要とされる基地局の台数と、１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００とを算出する。以下では、一例として、算出された基地局の台数は２台であるとして説明を続ける。領域選択部１４２は、算出した２台の基地局が設置される第１候補位置及び第２候補位置の近傍から、ＢＩＮをそれぞれ選択する。
【００９９】
グラフ選択部１４３は、第１候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第３候補位置と、第２候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第４候補位置とをノードとするグラフを構成する部分グラフのうちから、地図の所定範囲（通信エリア）でトラヒックの需要を満たし、且つ、所要受信電力を満たすＢＩＮ群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフ（図８を参照）を選択する。
【０１００】
以上のように、領域設定部１１０は、予め定められた最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、設置高を表すデータと、を取得することにより、前記ＢＩＮ毎の受信電力及び信号対干渉雑音比を算出し、予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記ＢＩＮ毎の前記トラヒックの需要を算出し、領域選択部１４２は、前記ＢＩＮ毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、第１候補位置４００及び第２候補位置５００と、を算出し、合わせて前記台数となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力を満たす前記ＢＩＮ群（カバレッジ）が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、トラヒックの需要の条件、及びカバレッジ最大化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【０１０１】
＜制約条件について＞
制約条件に設置費用等が用いられる場合、基地局の価格を表すデータ、基地局の設置費用を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【０１０２】
また、制約条件に収容トラヒック量が用いられる場合、通信エリア（サービスエリア）におけるトラヒックの需要を表すデータ、トラヒック需要予測データ、トラヒックの収容量を表すデータ、及び収容量計算式を表すデータのうち１つ以上は、制約条件を満たすか否かの判定において参照される。
【０１０３】
ここで、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上は、制約条件を満たすか否かの判定において参照されるとしてもよい。
【０１０４】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【０１０５】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【０１０６】
［第３実施形態］
本発明の第３実施形態について図面を参照して詳細に説明する。第３実施形態では、置局設計における最適化条件の一例として、トラヒックの収容量を最大化するという条件を設定する。また、置局設計における制約条件の一例として、基地局の設置費用等の合計を所定閾値以下にするという条件を設定する。以下では、第１実施形態及び第２実施形態との相違点についてのみ説明する。
【０１０７】
領域設定部１１０（図１を参照）には、地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、予め定められた土地区分データとが、入力装置２００（図１を参照）から入力される。ここで、領域設定部１１０には、最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータとが、入力装置２００から入力される。
【０１０８】
領域設定部１１０は、トラヒックの収容量をＢＩＮ毎に算出する。また、領域設定部１１０は、予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、ＢＩＮ毎の基地局の設置費用を算出する。
【０１０９】
領域選択部１４２（図１を参照）は、基地局の価格及び台数により定まる値と、基地局が設置されるＢＩＮ毎の基地局の設置費用との合計が所定閾値以下となる基地局の台数の最大値と、１箇所以上の第１候補位置４００及び１箇所以上の第２候補位置５００とを算出する。領域選択部１４２は、合わせてこの台数の最大値以下となる基地局が設置される第１候補位置及び第２候補位置の近傍から、ＢＩＮをそれぞれ選択する。
【０１１０】
グラフ選択部１４３は、第１候補位置の近傍から選択したＢＩＮ（図３を参照）に定められた複数の第３候補位置と、第２候補位置の近傍から選択したＢＩＮに定められた複数の第４候補位置（図３を参照）と、をノードとするグラフを構成する部分グラフのうちから、基地局の価格及び台数により定まる値と、基地局が設置されるＢＩＮ毎の基地局の設置費用との合計が所定閾値以下であり、且つ、基地局が設置されるＢＩＮ毎のトラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフ（図８を参照）を選択する。
【０１１１】
また、収容量計算式を表すデータに応じて、信号対干渉雑音比（ＳＩＮＲ）−パケットエラーレート（ＰＥＲ）変換テーブルデータ、及び、ＳＩＮＲ−ＭＣＳ変換テーブルデータのうち１つ以上が、制約条件を満たすか否かの判定において参照されるとしてもよい。
【０１１２】
以上のように、領域設定部１１０は、予め定められた最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記ＢＩＮ毎の前記トラヒックの収容量を算出し、予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記ＢＩＮ毎の前記設置費用を算出し、領域選択部１４２は、基地局の価格及び前記台数により定まる値と、基地局が設置される前記ＢＩＮ毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される第１候補位置４００及び第２候補位置５００の近傍から、ＢＩＮ４２０−１〜４２０−４、ＢＩＮ５２０−１〜５２０−４をそれぞれ選択し、グラフ選択部１４３は、第１候補位置４００の近傍から選択したＢＩＮ４２０−１〜４２０−４に定められた第３候補位置４３０−１〜４３０−１３と、第２候補位置５００の近傍から選択したＢＩＮ５２０−１〜５２０−４に定められた第４候補位置５３０−１〜５３０−１３と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記ＢＩＮ毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する。
この構成により、設置費用等の条件、及びトラヒックの収容量最大化の条件を満たす位置を、基地局を設置する候補位置をノードとするグラフにより検出し、検出した位置により定まる領域を出力するので、これにより、位置検出装置は、基地局を設置する自由度が高い位置を検出し、検出した位置により定まる領域を出力することができる。
【０１１３】
＜制約条件について＞
制約条件に費用が用いられる場合、基地局の価格を表すデータ、基地局の設置費用を表すデータのうち１つ以上が、制約条件を満たすか否かの判定において参照される。
また、制約条件に所要受信電力が用いられる場合、所要受信電力を表すデータは、制約条件を満たすか否かの判定において参照される。また、制約条件に所要ＳＩＮＲが用いられる場合、所要ＳＩＮＲを表すデータは、制約条件を満たすか否かの判定において参照される。
【０１１４】
＜伝搬ロスについて＞
伝搬ロスのモデル式を表すデータに応じて、建物高を表すデータ、建物形状を表すデータ、標高を表すデータ、アンテナ高を表すデータ、アンテナ利得を表すデータ、アンテナパターンを表すデータ、アンテナチルト角を表すデータ、及び基地局の設置高を表すデータのうち１つ以上は、伝搬ロスが算出される際に参照されてもよい。
【０１１５】
ここで、伝搬ロスのモデル式を土地区分毎に変更する場合、土地区分データは、伝搬ロスが算出される際に参照されてもよい。これにより、位置検出装置は、伝搬ロスを精度よく算出することができる。
【０１１６】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【０１１７】
例えば、位置検出装置は、入力装置から入力される各種データを予め記憶しているデータベースを備えてもよい。位置検出装置の各部は、入力装置から入力された各種データの代わりに、データベースに記憶されている各種データを取得して、上記に説明した動作を実行してもよい。
【０１１８】
また、例えば、上記の実施形態では、基地局が展開されていない通信エリアに新規に基地局を設置する場合について説明したが、位置検出装置は、基地局が既に展開されている通信エリアに基地局を増設する場合にも適用可能である。この場合、領域設定部は、既設の基地局が設置されている位置を表すデータを、入力装置又はデータベースから取得する。
【０１１９】
また、例えば、上記の実施形態では、置局設計における置局配置について説明したが、置局配置のみならず、位置検出装置は、基地局の送信電力、及び基地局のパラメータ（例えば、アンテナチルト角）を、置局配置と併せて最適化してもよい。
【０１２０】
また、例えば、設置される基地局は、1種類に限定されず、例えば、マクロ基地局、ピコ基地局といった複数種類でもよい。この場合、各基地局の種類毎に、伝搬ロスのモデル式が定められてもよい。
【０１２１】
また、例えば、候補位置を表すデータは、候補位置の各座標（例えば、緯度及び経度）を表すデータの集合により表現されてもよいし、各候補位置を含む領域（範囲）を表すデータにより表現されてもよい。領域を表すデータにより候補位置が表現されている場合、候補位置を含む領域を表すデータに加えて、候補位置の総数を表すデータ、又はＢＩＮ毎の候補位置数を表すデータが、位置検出装置に入力されてもよい。
【０１２２】
なお、以上に説明した位置検出装置を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録し、そのプログラムをコンピュータシステムに読み込ませて実行するようにしてもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【符号の説明】
【０１２３】
１００…位置検出装置、１１０…領域設定部、１２０…特性算出部、１３０…記憶部、１４０…最適化部、１４１…取得部、１４２…領域選択部、１４３…グラフ選択部と、１５０…出力部、２００…入力装置、４００…第１候補位置、４１０…近傍範囲、４２０−１〜４２０−４…ＢＩＮ、４３０−１〜４３０−１３…第３候補位置、４４０，４４０−２，４４０−３…領域、５００…第２候補位置、５１０…近傍範囲、５２０−１〜５２０−４…ＢＩＮ、５３０−１〜５３０−１３…第４候補位置、５４０，５４０−２，５４０−３…領域
【特許請求の範囲】
【請求項１】
予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する領域設定部と、
基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する特性算出部と、
前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する領域選択部と、
前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、
前記選択した完全部分グラフのノードの位置により定まる領域を出力する出力部と、
を備えることを特徴とする位置検出装置。
【請求項２】
前記領域設定部は、前記最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、
前記領域選択部は、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記領域毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項３】
前記領域設定部は、前記最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータと、を取得することにより、前記領域毎の受信電力及び信号対干渉雑音比を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、
前記領域選択部は、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力及び前記所要信号対干渉雑音比を満たす前記領域群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項４】
前記領域設定部は、前記最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記領域毎の前記トラヒックの収容量を算出し、前記予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、
前記領域選択部は、基地局の価格及び前記台数により定まる値と、基地局が設置される前記領域毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記領域毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項５】
コンピュータに、
予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する手順と、
基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する手順と、
前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する手順と、
前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、
前記選択した完全部分グラフのノードの位置により定まる領域を出力する手順と、
を実行させるための位置検出プログラム。
【請求項１】
予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する領域設定部と、
基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する特性算出部と、
前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する領域選択部と、
前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、
前記選択した完全部分グラフのノードの位置により定まる領域を出力する出力部と、
を備えることを特徴とする位置検出装置。
【請求項２】
前記領域設定部は、前記最適化条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、
前記領域選択部は、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、基地局の価格及び前記台数により定まる値と基地局が設置される前記領域毎の前記設置費用との合計が最小となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項３】
前記領域設定部は、前記最適化条件を表すデータとして、所要受信電力を表すデータと、所要信号対干渉雑音比を表すデータと、基地局の設置高を表すデータと、を取得することにより、前記領域毎の受信電力及び信号対干渉雑音比を算出し、前記予め定められた制約条件を表すデータとして、トラヒックの需要を表すデータを取得することにより、前記領域毎の前記トラヒックの需要を算出し、
前記領域選択部は、前記領域毎の前記トラヒックの需要と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記トラヒックの需要を満たす前記収容量を確保するために必要とされる基地局の台数と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記トラヒックの需要を満たし、且つ、前記所要受信電力及び前記所要信号対干渉雑音比を満たす前記領域群が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項４】
前記領域設定部は、前記最適化条件を表すデータとして、アンテナパターンを表すデータと、トラヒックの需要を表すデータと、トラヒックの収容量を基地局毎に算出するための手順を表すデータと、を取得することにより、前記領域毎の前記トラヒックの収容量を算出し、前記予め定められた制約条件を表すデータとして、基地局の設置費用を表すデータを取得することにより、前記領域毎の前記設置費用を算出し、
前記領域選択部は、基地局の価格及び前記台数により定まる値と、基地局が設置される前記領域毎の前記設置費用との合計が所定閾値以下となる前記台数の最大値と、前記第１候補位置及び前記第２候補位置と、を算出し、合わせて前記最大値以下となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択し、
前記グラフ選択部は、前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記合計が前記所定閾値以下であり、且つ、基地局が設置される前記領域毎の前記トラヒックの収容量の合計が最大となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択する
ことを特徴とする請求項１に記載の位置検出装置。
【請求項５】
コンピュータに、
予め定められた範囲を含む地図データと、予め定められたサイズを表すデータと、予め定められた最適化条件を表すデータと、予め定められた制約条件を表すデータと、を取得し、前記地図を前記サイズで分割することにより前記地図に前記サイズの領域を複数定め、前記領域毎の前記制約条件と、前記領域毎の前記最適化条件と、を算出する手順と、
基地局の送信電力及び周波数帯に基づいて、前記領域毎の伝搬ロスを算出する手順と、
前記領域毎の前記制約条件と、トラヒックの収容量を基地局毎に表すデータと、に基づいて、前記範囲で前記制約条件を満たす前記収容量を確保するために必要とされる基地局の台数と、１台以上の基地局をそれぞれ設置する１箇所以上の第１候補位置及び１箇所以上の第２候補位置と、を算出し、合わせて前記台数となる前記基地局が設置される前記第１候補位置及び前記第２候補位置の近傍から、前記領域をそれぞれ選択する手順と、
前記第１候補位置の近傍から選択した前記領域に定められた複数の第３候補位置と、前記第２候補位置の近傍から選択した前記領域に定められた複数の第４候補位置と、をノードとするグラフを構成する部分グラフのうちから、前記範囲で前記制約条件を満たし、且つ、前記領域毎の前記最適化条件により定まる値が最適となる実行可能解からなる完全部分グラフのうち最大の完全部分グラフを選択するグラフ選択部と、
前記選択した完全部分グラフのノードの位置により定まる領域を出力する手順と、
を実行させるための位置検出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−２０９７２３（Ｐ２０１２−２０９７２３Ａ）
【公開日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【出願番号】特願２０１１−７３２５７（Ｐ２０１１−７３２５７）
【出願日】平成２３年３月２９日（２０１１．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【出願日】平成２３年３月２９日（２０１１．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]