(57)【要約】【課題】複数の無線端末が存在する無線ネットワークにおいて、最小の基地局数をより高精度に算出可能とする。【解決手段】実施形態の位置算出方法は、無線ネットワークに配置する複数の基地局の位置をそれぞれ表す複数の候補位置を取得し、無線ネットワークに含まれる複数の端末と、取得した候補位置にある基地局とが接続可能な接続確率を用い、候補位置から基地局を配置する配置位置を決定するための最適化問題の条件を算出する。位置算出方法は、算出された条件の下で最適化問題を解いて、配置位置を算出する。【選択図】図３
2015109514.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークに配置する複数の基地局の位置をそれぞれ表す複数の候補位置を取得する取得ステップと、
前記無線ネットワークに含まれる複数の端末と、前記候補位置に存在する前記基地局の間の接続確率を用い、前記候補位置から基地局を配置する配置位置を決定するための最適化問題の条件を算出する条件算出ステップと、
前記条件の下で最適化問題を解いて前記配置位置を算出する位置算出ステップと
を有する
ことを特徴とする位置算出方法。
【請求項２】
前記条件は、
前記複数の端末それぞれの前記接続確率が閾値以上であって、且つ、前記無線ネットワークに含まれる前記基地局の数を最小にする条件である
ことを特徴とする請求項１に記載の位置算出方法。
【請求項３】
前記条件は、
基地局と端末とが接続できない確率を、前記複数の端末と、前記基地局から１以上の基地局が選択される全ての組み合わせとについてそれぞれ閾値と比較し、該確率が該閾値以下になる該組み合わせのうち含まれる基地局の数が最小の組み合わせを求める条件である
ことを特徴とする請求項２に記載の位置算出方法。
【請求項４】
前記条件は、
前記無線ネットワークに含まれる前記基地局の数が与えられた場合に、前記複数の端末それぞれの前記接続確率の最小値を最大にする条件である
ことを特徴とする請求項１に記載の位置算出方法。
【請求項５】
前記条件は、
基地局と端末とが接続できない確率を、前記複数の端末と、前記基地局のうち与えられた数の基地局が選択される全ての組み合わせとについてそれぞれ求め、求められた全ての該確率のうち最大の確率を最小にする該組み合わせを求める条件である
ことを特徴とする請求項４に記載の位置算出方法。
【請求項６】
前記取得ステップは、
前記複数の端末が配置されるエリアをグリッドに分割した各グリッドから前記基地局の前記候補位置を取得する
ことを特徴とする請求項１乃至請求項５の何れか１項に記載の位置算出方法。
【請求項７】
前記取得ステップは、
前記グリッドそれぞれの中央位置を前記候補位置として取得する
ことを特徴とする請求項６に記載の位置算出方法。
【請求項８】
前記取得ステップは、
前記複数の端末をグループに分けたグループ毎に前記基地局の前記候補位置を取得する
ことを特徴とする請求項１乃至請求項５の何れか１項に記載の位置算出方法。
【請求項９】
前記取得ステップは、
前記グループ毎に、グループに含まれる端末の位置の重心位置を前記候補位置として取得する
ことを特徴とする請求項８に記載の位置算出方法。
【請求項１０】
無線ネットワークに配置する複数の基地局の位置をそれぞれ表す複数の候補位置を取得する取得ステップと、
前記無線ネットワークに含まれる複数の端末と、前記候補位置に存在する前記基地局の間の接続確率を用い、前記候補位置から基地局を配置する配置位置を決定するための最適化問題の条件を算出する条件算出ステップと、
前記条件の下で最適化問題を解いて前記配置位置を算出する位置算出ステップと
をコンピュータに実行させるための位置算出プログラム。
【請求項１１】
無線ネットワークに配置する複数の基地局の位置をそれぞれ表す複数の候補位置を取得する取得部と、
前記無線ネットワークに含まれる複数の端末と、前記候補位置に存在する前記基地局の間の接続確率を用い、前記候補位置から基地局を配置する配置位置を決定するための最適化問題の条件を算出する条件算出部と、
前記条件の下で最適化問題を解いて前記配置位置を算出する位置算出部と
を有する
ことを特徴とする位置算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置算出方法、位置算出プログラムおよび位置算出装置に関する。
【背景技術】
【０００２】
複数の無線端末が存在する無線ネットワークにおいて、全ての無線端末と無線で通信可能なように基地局を配置する際に基地局の数を最小とするための方法が知られている。この方法によれば、複数の無線端末の位置と、基地局の配置が可能な候補位置とが与えられた場合に、候補位置の全てに基地局を配置しなくても、最小の個数の基地局で複数の無線端末の全てが何れかの基地局と通信可能とすることができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】A.  Molina,  G.E.  Athanasiadou,  A.R.  Nix.  "The  automatic  location  of  base-stations  for  optimized  cellular  coverage:  A  new  combinatorial  approach".  Vehicular  Technology  Conference,  1999  IEEE  49th.
【非特許文献２】J  Van  Roy,  LA  Wolsey  ,  “Solving  mixed  integer  programming  problems  using  automatic  reformulation,”  Operations  Research,  January/February  1987,  vol.  35,  no.  1,  45-57.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、実際の無線通信では、無線伝送路上のフェージングや信号の衝突などにより、基地局と無線端末との間の接続確率は、０〜１の範囲の値で表される。しかしながら、従来では、基地局と無線端末との間の接続確率が０および１の何れかであるとして、基地局数の最小値を求めていた。そのため、従来の方法では、求められる最小の基地局数が、実際の無線通信における最小の基地局数よりも多く算出されてしまうおそれがあった。
【０００５】
したがって、本発明の目的は、複数の無線端末が存在する無線ネットワークにおいて、最小の基地局数をより高精度に算出可能な位置算出方法、位置算出プログラムおよび位置算出装置を提供することにある。
【課題を解決するための手段】
【０００６】
実施形態の位置算出方法は、無線ネットワークに配置する複数の基地局の位置をそれぞれ表す複数の候補位置を取得し、無線ネットワークに含まれる複数の端末と、取得した候補位置にある基地局とが接続可能な接続確率を用い、候補位置から基地局を配置する配置位置を決定するための最適化問題の条件を算出する。位置算出方法は、算出された条件の下で最適化問題を解いて、配置位置を算出する。
【図面の簡単な説明】
【０００７】
【図１】図１は、各実施形態に適用可能なネットワークシステムを説明するための図である。
【図２】図２は、第１の実施形態に適用可能な位置計算装置の機能を示す機能ブロック図である。
【図３】図３は、第１の実施形態に係る位置計算処理を示す一例のフローチャートである。
【図４】図４は、第１の実施形態に係る、エリアを分割した各グリッドの中央位置を基地局の候補位置Ｂiとした例を示す図である。
【図５】図５は、第１の実施形態に係る、グループ化した各無線端末Ｓjの位置に基づき基地局の候補位置Ｂiを決定する例を示す図である。
【図６】図６は、各実施形態に係る位置算出装置を実現可能な構成の例を示すブロック図である。
【図７】図７は、各実施形態に適用可能な位置計算システムの別の例の構成を示すブロック図である。
【発明を実施するための形態】
【０００８】
以下、各実施形態に係る位置計算方法、位置計算プログラムおよび位置計算装置について説明する。先ず、各実施形態の説明に先んじて、各実施形態に適用可能なネットワーク構成について、図１を用いて概略的に説明する。
【０００９】
図１において、各実施形態に適用可能なネットワークシステムは、黒丸で示される１以上の無線端末Ｓ1、Ｓ2、…、Ｓj、…、Ｓn-1、Ｓnと、黒四角で示される候補位置Ｂ1、Ｂ2、…、Ｂi、…、Ｂmのうち選択された候補位置に配置される基地局とを含む。
【００１０】
以下では、特に記載のない限り、各無線端末Ｓ1、Ｓ2、…、Ｓj、…、Ｓn-1、Ｓnを無線端末Ｓjで代表して記述する。同様に、基地局の各候補位置Ｂ1、Ｂ2、…、Ｂi、…、Ｂmを、これらを代表させて候補位置Ｂiとして記述する。
【００１１】
なお、無線端末Ｓjは、例えば、無線機、無線センサノード、無線を利用するユーザの無線端末である。無線端末Ｓjは、他の無線端末を介して基地局と通信可能とされている。また、基地局は、例えば、無線アクセスポイント、コンセントレータである。
【００１２】
各実施形態では、各候補位置Ｂ1、Ｂ2、…、Ｂi、…、Ｂmの何れに基地局を配置するかを、各無線端末Ｓjと各候補位置Ｂiに配置する基地局との間の接続確率に基づき求める。ここで、接続確率は、０から１の範囲の値であり、接続確率が０に近付くほど接続困難となり、１に近付くほど接続容易となることを示す。
【００１３】
なお、以下では、「各無線端末Ｓjと各候補位置Ｂiに配置する基地局との間の接続確率」を、適宜、「各無線端末Ｓjと各基地局との間の接続確率」のように、候補位置Ｂiに配置された基地局を仮定して記述する。
【００１４】
（第１の実施形態）
第１の実施形態に係る基地局の位置算出方法について説明する。第１の実施形態では、ネットワークシステムにおいて、各無線端末Ｓjと基地局との間の接続確率を一定以上とする、各基地局の配置位置を算出する。図２は、第１の実施形態に適用可能な位置計算装置１の機能を示す機能ブロック図である。図２において、位置計算装置１は、計算部２と、取得部１０と、出力部１３とを有する。
【００１５】
取得部１０は、計算部２において基地局の位置計算に必要となる各種のデータを取得する。計算部２は、条件算出部１１と位置算出部１２とを有し、取得部１０で取得された各種データに基づき、予め設定された基地局の各候補位置Ｂiのうち何れに基地局を配置するかを示す位置情報を算出する。出力部１３は、計算部２で算出された位置情報を出力する。
【００１６】
位置計算装置１において、計算部２および取得部１０は、ＣＰＵ(Central  Processing  Unit)上で動作する位置計算プログラムにより実現される。これに限らず、計算部２および取得部１０は、それぞれ専用のハードウェアによって構成してもよい。また、計算部２および取得部１０を実現する位置計算プログラムに対し、出力部１３の少なくとも一部の機能を含めることもできる。
【００１７】
図３は、第１の実施形態に係る位置計算処理を示す一例のフローチャートである。位置計算装置１は、この図３のフローチャートによる処理を実行することで、ネットワークシステムにおける基地局の配置位置などを算出する。位置計算装置１において、取得部１０は、ステップＳ１０で、基地局の各候補位置Ｂiを取得する。次のステップＳ１１で、取得部１０は、各無線端末Ｓjと、ステップＳ１０で取得した各候補位置Ｂiの基地局との接続確率を取得する。
【００１８】
次のステップＳ１２で、条件算出部１１は、各候補位置Ｂiから基地局を配置する位置を決定するための最適化問題の条件を算出する。第１の実施形態では、条件算出部１１は、ステップＳ１１で取得された各無線端末Ｓjと各候補位置Ｂiの基地局との接続確率を一定以上とする最適化問題の条件を算出する。換言すれば、ステップＳ１２で、条件算出部１１は、各無線端末Ｓjと各候補位置Ｂiの基地局との接続確率を一定以上とする条件で、各候補位置Ｂiから基地局を配置する位置を決定する方法を最適化問題に変換する。
【００１９】
そして、次のステップＳ１３で、位置算出部１２は、ステップＳ１２で得られた条件の下に最適化問題を解いて、各候補位置Ｂiのうち基地局を配置する位置を算出する。
【００２０】
以下、図３のフローチャートの各ステップの処理について、より詳細に説明する。最初のステップＳ１０で、取得部１０は、基地局Ｂiを配置する候補位置を取得する。基地局Ｂiの候補位置の決定方法は、従来、様々な方法が提案されている。
【００２１】
図４は、第１の実施形態に係る、エリアを予め定めれられたグリッドに分割し、各グリッドの中央位置を基地局の候補位置Ｂiとした例を示す。例えば、ユーザは、各無線端末Ｓjを配置するエリア２０の情報と、エリア２０を分割するグリッド数とを取得部１０に入力する。取得部１０は、入力された各情報に基づき、エリア２０を予め定められたグリッドにより小エリア３０1、３０2、…、３０gに分割する。取得部１０は、これら各小エリア３０1、３０2、…、３０gの中央位置を求め、求められた各中央位置を、基地局の候補位置Ｂiとして取得する。
【００２２】
図５は、第１の実施形態に係る、配置される各無線端末Ｓjをグループ化し、各グループに含まれる各無線端末Ｓjの位置に基づき基地局の候補位置Ｂiを決定する例を示す。例えば、ユーザは、各無線端末Ｓjの位置情報を取得部１０に入力する。取得部１０は、入力された各位置情報に基づき、各無線端末Ｓjが属するグループ３１1、３１2、…、３１hを求める。これに限らず、各無線端末Ｓjが属するグループ３１1、３１2、…、３１hを、ユーザが取得部１０に対して指定してもよい。
【００２３】
取得部１０は、各グループ３１1、３１2、…、３１hに属する無線端末Ｓjの配置位置に基づき、各グループ３１1、３１2、…、３１hそれぞれについて、基地局の候補位置Ｂiを求める。例えば、取得部１０は、各グループ３１1、３１2、…、３１hそれぞれについて、属する無線端末Ｓjの位置の重心を求め、各重心を各グループ３１1、３１2、…、３１hの基地局の候補位置Ｂiとして取得する。
【００２４】
なお、各基地局の候補位置Ｂiの取得方法は、上述に限定されず、取得部１０は、他の方法で候補位置Ｂiを取得してもよい。例えば、各基地局の候補位置Ｂiは、無線端末Ｓjが配置されるエリアの状況などに応じて、ユーザが任意に選択してもよい。ユーザは、例えば、決定された各候補位置Ｂiに対して識別情報ｉを関連付けて、位置計算装置１に入力する。位置計算装置１において、取得部１０は、入力された各候補位置Ｂiについて、それぞれ識別情報ｉを取得する。
【００２５】
次のステップＳ１１で、取得部１０は、ステップＳ１０で取得した各候補位置Ｂiにおける基地局と、各無線端末Ｓjとが接続可能な確率を示す接続確率を取得する。ここでは、取得部１０は、各基地局が各候補位置Ｂiに配置されているものと見做して、各接続確率を取得する。
【００２６】
なお、各実施形態では、基地局の設置候補位置Ｂiの数＝ｍ、無線端末Ｓjの数＝ｎ（ｍ、ｎはそれぞれ１以上の整数）とし、ｉ番目の基地局の設置候補位置を設置候補位置Ｂi（１≦ｉ≦ｍ）、ｊ番目の無線端末を無線端末Ｓj（１≦ｊ≦ｎ）と定義する。また、候補位置Ｂiに配置される基地局と、無線端末Ｓjとの間の通信が接続可能な確率を接続確率Ｐijと定義する。
【００２７】
また、以下では、「各無線端末Ｓjと各候補位置Ｂiに配置する基地局との間の接続確率Ｐij」を、適宜、「各無線端末Ｓjと各基地局との間の接続確率Ｐij」のように、候補位置Ｂiに配置された基地局を仮定して記述する。
【００２８】
基地局および無線端末Ｓjの位置が与えられた場合に、各無線端末Ｓjと各基地局との接続確率Ｐijを計算できる。接続確率Ｐijは、既知の方法を適用して算出することができる。例えば、無線端末Ｓjと基地局の位置（候補位置Ｂｉ）との間の距離に応じて接続確率Ｐijを算出することができる。この場合、無線端末Ｓjと基地局との間の距離が所定範囲内であれば、接続確率Ｐijを１とすることも考えられる。
【００２９】
また、無線端末Ｓjと基地局との間の通信におけるＳＮＲ(Signal  to  Noise  Ratio)が計測可能であれば、このＳＮＲに基づき接続確率Ｐijを算出してもよい。さらに、フェージングの環境において、無線端末Ｓjと基地局との間の通信における相互情報量の時刻変化を計測可能である場合に、所定時間内の相互情報量が閾値以上になる確率を接続確率Ｐijとして用いてもよい。
【００３０】
取得部１０は、例えば、ユーザにより入力された、外部で算出された各接続確率Ｐijを取得する。これに限らず、取得部１０は、ユーザにより入力された各情報に基づき各接続確率Ｐijを算出して取得してもよい。取得部１０は、ステップＳ１１で取得した各無線端末Ｓjと各候補位置Ｂiにおける基地局との間の通信における接続確率Ｐijを条件算出部１１に渡す。
【００３１】
条件算出部１１は、ステップＳ１２で、取得部１０から渡された各接続確率Ｐijを閾値以上とする、各候補位置Ｂiから基地局を配置する配置位置を決定するための最適化問題の条件を算出する。先ず、条件算出部１１は、接続確率Ｐijを用いて、対数値Ｑijを下記の式（１）により定義する。なお、式（１）は、指数関数exp()を用いて下記の式（２）のように表すことができる。式（１）で求められる対数値Ｑijは、１の無線端末Ｓjが１の候補位置Ｂiの基地局に接続できない確率の対数値である。
Ｑij＝log(１−Ｐij)    …（１）
１−Ｐij＝exp(Ｑij)    …（２）
【００３２】
ステップＳ１２における最適化問題の条件算出方法について、より詳細に説明する。第１の実施形態では、ネットワークの接続性を保証するために、各無線端末Ｓjと各候補位置Ｂiにおける基地局との接続確率Ｐijが閾値Ｐth（０＜Ｐth≦１）以上の条件で基地局の数を最小にする、基地局の配置位置を決定する。
【００３３】
ここで、閾値Ｐthは、例えば、ネットワークシステム内で所定時間内に１回の通信が成功する確率に基づき決定することができる。また例えば、閾値Ｐthは、予め定められた通信周期において、所定周期のうち１回の通信が成功する確率に基づき決定することもできる。なお、閾値Ｐthの決定方法は、これらの例に限定されるものではない。
【００３４】
また、基地局の候補位置Ｂiが基地局の配置位置として選択される場合に１、選択されない場合に０となる値ｂiを定義する。配置する基地局数は、この値ｂiを用いて、下記の式（３）で表すことができる。
【数１】
2015109514.tif 000003
【００３５】
先ず、１の無線端末Ｓjが少なくとも１の候補位置Ｂiの基地局に接続可能な確率の計算方法について説明する。無線端末Ｓｊが各候補位置Ｂｉの何れの基地局にも接続できない確率は、下記の式（４）で表される。
【数２】
2015109514.tif 000004
【００３６】
したがって、１の無線端末Ｓｊが少なくとも１の候補位置Ｂｉの基地局に接続可能な確率Ｐjは、上述した式（１）と式（４）とを用いて、下記の式（５）で表される。
【数３】
2015109514.tif 000005
【００３７】
ここで、無線端末Ｓjと１の候補位置Ｂiの基地局との接続確率Ｐijが閾値Ｐth以上である条件から、下記の式（６）が導出できる。
【数４】
2015109514.tif 000006
【００３８】
また、上述した式（１）から、閾値Ｐthに関し、下記の式（７）が成り立つ。
Ｑth＝log(１−Ｐth)    …（７）
【００３９】
この式（７）と上述した式（６）とから、下記の式（８）を満足する値ｂiを求めることで、基地局の最小個数、すなわち、全ての候補位置Ｂiのうち選択される候補位置の最小の個数を求めることができる。
【数５】
2015109514.tif 000007
【００４０】
この式（８）は、無線端末Ｓjと候補位置Ｂiの基地局とが接続できない確率を、ネットワークシステムに含まれる全ての無線端末Ｓ1、Ｓ2、…、Ｓj、…、Ｓnと、全ての候補位置Ｂ1、Ｂ2、…、Ｂi、…、Ｂmに配置される各基地局から１以上の基地局が選択される全ての組み合わせとについて、それぞれ閾値Ｑthと比較する。そして、この確率が閾値Ｑth以下になる組み合わせのうち含まれる基地局の数（候補位置Ｂiの数）が最小の組み合わせを求める最適化問題の条件を定める。
【００４１】
ステップＳ１３における基地局配置位置の算出方法について説明する。ステップＳ１３で、位置算出部１２は、ステップＳ１２で求めた式（８）から、基地局の位置を算出する。すなわち、位置算出部１２は、ステップＳ１３で、式（８）において値ｂi＝１となる各候補位置Ｂiを算出する。
【００４２】
このステップＳ１３での各候補位置Ｂiを算出する問題は、混合整数計画法の問題であって、混合整数計画法の既知の方法を用いることで解が得られる。例えば、ステップＳ１３の問題は、非特許文献２に記載の解法を適用することができる。勿論、第１の実施形態によるステップＳ１３の解法は、非特許文献２の方法に限られず、混合整数計画法に係る他の解法を適用してもよい。
【００４３】
このように、位置算出部１２は、ステップＳ１３で、必要な基地局数を式（３）で表現される値として出力する。また、位置算出部１２は、値ｂi＝１に対応する各候補位置Ｂiを、各基地局の配置位置として出力する。
【００４４】
位置算出部１２から出力された基地局数および基地局の配置位置を示す情報は、出力部１３に渡され、例えば図示されない表示部に表示される。これに限らず、出力部１３は、基地局数および基地局の配置位置を示す情報を、位置計算装置１の外部に出力してもよい。
【００４５】
以上説明したように、第１の実施形態では、各無線端末の位置と、基地局の各候補位置と、各無線端末と各候補位置の基地局との接続確率とが与えられた条件下で、無線端末と基地局との通信の接続確率が閾値以上となる条件を満足する基地局の個数および配置位置を求めることが可能となる。
【００４６】
（第２の実施形態）
次に、第２の実施形態について説明する。第２の実施形態では、配置する基地局の数ＢＳｎｕｍが与えられた場合に、各無線端末Ｓjが少なくとも１の基地局に接続可能な接続確率Ｐjの最小値を最大化するように、各基地局の配置位置を求める。なお、第２の実施形態では、上述の第１の実施形態で図２を用いて説明した位置計算装置１の構成をそのまま適用できるので、ここでの構成の説明を省略する。
【００４７】
第２の実施形態による処理について、上述した図３のフローチャートを参照しながら説明する。なお、フローチャートの実行に先立って、取得部１０は、配置する基地局の数ＢＳｎｕｍを、ユーザ入力などにより予め取得しているものとする。
【００４８】
ステップＳ１０およびステップＳ１１の処理は、上述した第１の実施形態と共通である。すなわち、ステップＳ１０で、位置計算装置１において取得部１０は、基地局の各候補位置Ｂiを取得する。そして、次のステップＳ１１で、取得部１０は、各無線端末Ｓjと、ステップＳ１０で取得した各候補位置Ｂiの基地局との接続確率Ｐijを取得する。
【００４９】
次のステップＳ１２で、条件算出部１１は、上述したように、与えられた基地局数ＢＳｎｕｍの条件下で、各候補位置Ｂiから基地局を配置する配置位置を決定するための最適化問題の条件を算出する。この第２の実施形態では、条件算出部１１は、各無線端末Ｓjが少なくとも１の基地局に接続可能な接続確率Ｐjの最小値を最大化する。この接続確率Ｐjの最小値の最大化は、上述した式（６）の左辺の式である下記の式（９）の最小化と同義である。
【数６】
2015109514.tif 000008
【００５０】
したがって、接続確率Ｐjの最小値の最大化は、下記の式（１０）により表すことができる。
【数７】
2015109514.tif 000009
【００５１】
これにより、条件算出部１１は、基地局の数ＢＳｎｕｍという条件下で、下記の式（１１）に示す、各無線端末Ｓjと基地局との接続確率Ｐjの最小値を最大化する最適化問題の条件を算出する。
【数８】
2015109514.tif 000010
【００５２】
この式（１１）は、無線端末Ｓｊと候補位置Ｂiの基地局とが接続できない確率を、ネットワークシステムに含まれる全ての無線端末Ｓ1、Ｓ2、…、Ｓj、…、Ｓnと、全ての候補位置Ｂ1、Ｂ2、…、Ｂi、…、Ｂmに配置される各基地局のうち与えられた数ＢＳｎｕｍの基地局が選択される全ての組み合わせとについてそれぞれ求める。そして、求められた全ての確率のうち最大の確率を最小にする組み合わせを求める最適化問題の条件である。
【００５３】
式（１１）は、下記の式（１２）に示すように変形できる。
【数９】
2015109514.tif 000011
【００５４】
位置算出部１２は、次のステップＳ１３で、この式（１２）を解いて、基地局の位置を算出する。すなわち、位置算出部１２は、ステップＳ１３で、式（１１）において値ｂi＝１となる各候補位置Ｂiを算出する。これは、混合整数計画法の問題であって、混合整数計画法の既知の方法、例えば上述の非特許文献２に記載の解法を用いて解くことが可能である。勿論、この第２の実施形態によるステップＳ１３の解法も、非特許文献２の方法に限られず、混合整数計画法に係る他の解法を適用してもよい。
【００５５】
このように、位置算出部１２は、ステップＳ１３で、必要な基地局数を上述した式（３）で表現される値として出力する。また、位置算出部１２は、値ｂi＝１に対応する各候補位置Ｂiを、各基地局の配置位置として出力する。
【００５６】
位置算出部１２から出力された基地局数および基地局の配置位置を示す情報は、出力部１３に渡され、例えば図示されない表示部に表示される。これに限らず、出力部１３は、基地局数および基地局の配置位置を示す情報を、位置計算装置１の外部に出力してもよい。
【００５７】
以上説明したように、第２の実施形態によれば、基地局数が与えられた場合に、各無線端末と各基地局との接続確率の最小値が最大になる、すなわち、接続が困難である無線端末と基地局との間の接続確率を最大化する基地局の配置位置を求めることが可能となる。
【００５８】
（各実施形態に適用可能なハードウェア構成）
次に、各実施形態に係る位置計算装置１を実現可能な構成について、図６を用いて説明する。図６に例示されるように、位置計算装置１は、例えば一般的なコンピュータ装置１００により実現可能である。
【００５９】
図６において、バス１２０に対してＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、表示制御部１０４および通信Ｉ／Ｆ（インターフェイス）１０５が接続される。また、バス１２０に対して、ストレージ１０６、ドライブ装置１０７および入力Ｉ／Ｆ１０８が接続される。
【００６０】
ＣＰＵ１０１は、ＲＯＭ１０３やストレージ１０６に記憶されるプログラムに従い、ＲＡＭ１０２をワークメモリとして用いて、このコンピュータ装置１００の全体を制御する。表示制御部１０４は、ＣＰＵ１０１により生成された表示制御信号を、表示装置１１０が表示可能な信号に変換して出力する。
【００６１】
ストレージ１０６は、例えば不揮発性の半導体メモリやハードディスクドライブであり、上述のＣＰＵ１０１が実行するためのプログラムや、プログラムによって用いられるデータなどが格納される。ドライブ装置１０７は、脱着可能な記録媒体１１１が装填可能とされ、少なくとも当該記録媒体１１１からのデータの読み出しを行うことができる。ドライブ装置１０７が対応可能な記録媒体１１１としては、ＣＤ(Compact  Disk)、ＤＶＤ(Digital  Versatile  Disk)、フレキシブルディスクといったディスク記録媒体や、読み書き可能で不揮発性の半導体メモリが考えられる。
【００６２】
入力Ｉ／Ｆ１０８は、外部からのデータの入力を行う。入力Ｉ／Ｆ１０８は、例えば、ＵＳＢ(Universal  Serial  Bus)やＩＥＥＥ１３９４(Institute  of  Electrical  and  Electronics  Engineers  1394)といった所定のインターフェイスを有し、このインターフェイスにより外部の機器からのデータ入力を行う。また、入力Ｉ／Ｆ１０８に対して、キーボード１１２やマウス１１３といった入力デバイスが接続される。ユーザは、例えば表示装置１１０に対する表示に応じてこれら入力デバイスを操作することで、このコンピュータ装置１００に対して指示を出すことができる。
【００６３】
通信Ｉ／Ｆ１０５は、所定のプロトコルを用いて外部の通信ネットワークと通信を行う。
【００６４】
上述した位置計算装置１における取得部１０、条件算出部１１および位置算出部１２は、ＣＰＵ１０１上で動作する位置算出プログラムによって実現される。位置算出プログラムに、出力部１３を含めてもよい。取得部１０が取得する各種情報は、例えば他のコンピュータで作成されファイルに格納され、記録媒体１１１に記録されてこのコンピュータ装置１００に供給される。これに限らず、取得部１０は、外部からネットワークを介してこのコンピュータ装置１００に供給された当該各情報を取得するようにしてもよい。
【００６５】
例えば各実施形態に係る位置計算装置１の動作を実行するための位置算出プログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ、フレキシブルディスク、ＤＶＤなどのコンピュータで読み取り可能な記録媒体１１１に記録して提供される。これに限らず、当該位置算出プログラムを、ＲＯＭ１０３に予め記憶させて、コンピュータ装置１００に提供してもよい。
【００６６】
さらに、当該位置算出プログラムを、インターネットやＬＡＮ(Local  Area  Network)などのネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより、コンピュータ装置１００に提供するように構成してもよい。また、当該位置算出プログラムを、インターネットなどのネットワーク経由で提供または配布するように構成してもよい。
【００６７】
例えば各実施形態に係る位置算出プログラムは、上述した取得部１０、条件算出部１１および位置算出部１２を含むモジュール構成となっており、実際のハードウェアとしては、ＣＰＵ１０１が例えばストレージ１０６から当該位置算出プログラムを読み出して実行することにより上述の各部がＲＡＭ１０３上にロードされ、取得部１０、条件算出部１１および位置算出部１２がＲＡＭ１０３上に生成されるようになっている。
【００６８】
（各実施形態に適用可能なハードウェア構成の別の例）
次に、各実施形態に適用可能なハードウェア構成の別の例について説明する。図７は、各実施形態に適用可能な位置計算システムの別の例の構成を示す。この別の例では、各実施形態による計算部２（条件算出部１１および位置算出部１２）をネットワーク・クラウド上に構成する。なお、図７において、上述の図２と共通する部分には同一の符号を付して、詳細な説明を省略する。
【００６９】
図７において、位置計算システムは、計算部２がネットワーク・クラウド２００上に構成される。ネットワーク・クラウド２００は、互いにネットワークで接続される複数のコンピュータを含み、外部からは、その内部が隠蔽されたブラックボックスとして入出力のみが示されるネットワーク・グループである。ネットワーク・クラウド２００は、例えば通信プロトコルとしてＴＣＰ／ＩＰ(Transmission  Control  Protocol/Internet  Protocol)を用いるものとする。
【００７０】
計算端末装置２０１は、ネットワーク・クラウド２００と通信するための通信Ｉ／Ｆを備え、取得部１０および出力部１３を含む。取得部１０をネットワーク・クラウド２００上に構成し、計算端末装置２０１には情報を入力する入力部を含めてもよい。計算端末装置２０１は、例えば一般的なコンピュータ装置を適用してもよいし、計算部２に専用の装置としてもよい。取得部１０は、上述したように、基地局の各候補位置Ｂiや各無線端末Ｓjと各候補位置Ｂiの基地局との接続確率Ｐijなどを取得する。出力部１３は、ネットワーク・クラウド２００から送信された各基地局の配置位置を示す情報や基地局数などの出力を行う。
【００７１】
計算端末装置２０１は、取得部１０により取得した各情報を、ネットワーク・クラウド２００に送信する。この計算端末装置２０１から送信された各情報は、ネットワーク・クラウド２００において、計算部２（条件算出部１１）に渡される。ネットワーク・クラウド２００上の計算部２は、渡された各情報に基づき、各候補位置Ｂiから基地局を配置する配置位置を決定する最適化問題の条件を算出する。そして、計算部２は、算出した条件に従いこの最適化問題を混合整数計画法などを用いて解いて、基地局の配置位置や基地局数を算出する。算出された基地局の配置位置や基地局数などの情報は、ネットワーク・クラウド２００から計算端末装置２０１に送信される。計算端末装置２０１は、ネットワーク・クラウド２００から受信した基地局の配置位置や基地局数の情報を出力する。
【００７２】
なお、本実施形態は、上述したそのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上述の実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００７３】
１  位置計算装置
２  計算部
１０  取得部
１１  条件算出部
１２  位置算出部
１３  出力部
【図１】
2015109514.tif 000012
【図２】
2015109514.tif 000013
【図３】
2015109514.tif 000014
【図４】
2015109514.tif 000015
【図５】
2015109514.tif 000016
【図６】
2015109514.tif 000017
【図７】
2015109514.tif 000018