(57)【要約】【課題】基地局の配置場所である頂点配置場所と、セルの配置パターンである凸多角形の配置パターンを決定することを目的とする。【解決手段】配置場所および配置パターン計算装置は、被覆をおこなう対象の第１の二次元平面と、当該第１の二次元平面を内包する第２の二次元平面と、当該第２の二次元平面内に分布した、各々がコストを持つ頂点配置候補地の集合とを受け取る入力部と、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙する多角形列挙部と、凸多角形が前記第１の二次元平面上に重複および隙間がないように配置されるという条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算する配置場所および配置パターン計算部と、計算された頂点の配置場所および凸多角形の配置パターンを出力する出力部とを有する。【選択図】図１
2016091400.tif 000002
【特許請求の範囲】
【請求項１】
第１の二次元平面を凸多角形の集合によって被覆する際に、凸多角形の頂点の配置場所および凸多角形の配置パターンを出力する配置場所および配置パターン計算装置であって、
被覆をおこなう対象の第１の二次元平面と、当該第１の二次元平面を内包する第２の二次元平面と、当該第２の二次元平面内に分布した、各々がコストを持つ頂点配置候補地の集合とを受け取る入力部と、
前記頂点配置候補地の集合から、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙する多角形列挙部と、
凸多角形が前記第１の二次元平面上に重複および隙間がないように配置されるという条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算する配置場所および配置パターン計算部と、
計算された頂点の配置場所および凸多角形の配置パターンを出力する出力部と、
を有する配置場所および配置パターン計算装置。
【請求項２】
前記配置場所および配置パターン計算部における計算のための線分、頂点および凸多角形の関係を表す係数を計算する係数計算部を更に有し、
前記配置場所および配置パターン計算部は、凸多角形を配置するかしないかを表す設計変数、凸多角形の辺として配置するかしないかを表す設計変数、および頂点を配置するかしないかを表す設計変数を導入し、平面グラフにおける面、辺および頂点の関係を表すオイラーの性質を用いた制約条件、配置する凸多角形と線分の関係に基づいた制約条件、配置する凸多角形の線分と配置する頂点の関係に基づいた制約条件、凸多角形が重複しないための制約条件、隣接する凸多角形の数に基づいた制約条件、並びに、前記第１の二次元平面と凸多角形の最大面積の関係から計算される凸多角形の数の下限に基づいた制約条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算する、請求項１に記載の配置場所および配置パターン計算装置。
【請求項３】
凸多角形の一辺の長さがしきい値以下の三角形とした場合、
頂点の配置場所として、自身の頂点を配置された頂点上に持つ三角形を前記第１の二次元平面を被覆するように重複および隙間がないように配置されるという条件のもとで、頂点の配置コストに基づいて、準最適な頂点配置場所を最適化手法を用いて探索する最適化計算部と、
頂点配置場所を選択した場合に、前記第１の二次元平面を被覆するような三角形の集合が形成することができるという制約条件を満たさない場合に、前記準最適な頂点配置場所を算出するための評価値にペナルティ項を与える制約条件確認部と、
を更に有する、請求項１又は２に記載の配置場所および配置パターン計算装置。
【請求項４】
前記入力部は、前記最適化計算部において計算された前記準最適な頂点配置場所を、前記頂点配置候補地の集合として受け取る、請求項３に記載の配置場所および配置パターン計算装置。
【請求項５】
前記第１の二次元平面が、基地局のセクタアンテナを用いたマクロダイバーシティによって形成されるセルで被覆する領域であり、
前記第２の二次元平面が、基地局を配置できる候補地が分布する領域であり、
前記頂点配置候補地が、基地局の配置候補地である場合、
前記出力部は、基地局の配置場所およびセルの配置パターンを、前記計算された頂点の配置場所および凸多角形の配置パターンとして出力する、請求項１又は２に記載の配置場所および配置パターン計算装置。
【請求項６】
前記第１の二次元平面が、基地局のセクタアンテナを用いたマクロダイバーシティによって形成されるセルで被覆する領域であり、
前記第２の二次元平面が、基地局を配置できる候補地が分布する領域であり、
前記頂点配置候補地が、基地局の配置候補地である場合、
前記最適化計算部は、基地局の準最適な配置場所を、前記準最適な頂点配置場所として計算する、請求項３又は４に記載の配置場所および配置パターン計算装置。
【請求項７】
前記制約条件確認部は、前記準最適な頂点配置場所を算出するための評価値に、頂点同士の距離が均一になるような値を与える、請求項３又は４に記載の配置場所および配置パターン計算装置。
【請求項８】
第１の二次元平面を凸多角形の集合によって被覆する際に、凸多角形の頂点の配置場所および凸多角形の配置パターンを出力する配置場所および配置パターン計算装置における配置場所および配置パターン計算方法であって、
被覆をおこなう対象の第１の二次元平面と、当該第１の二次元平面を内包する第２の二次元平面と、当該第２の二次元平面内に分布した、各々がコストを持つ頂点配置候補地の集合とを受け取るステップと、
前記頂点配置候補地の集合から、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙するステップと、
凸多角形が前記第１の二次元平面上に重複および隙間がないように配置されるという条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算するステップと、
計算された頂点の配置場所および凸多角形の配置パターンを出力するステップと、
を有する配置場所および配置パターン計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配置場所および配置パターン計算装置、並びに配置場所および配置パターン計算方法に関する。より具体的には、本発明は、例えばセクタアンテナを用いた無線ネットワークにおいて、複数アンテナを協調させて1セルを構成するマクロダイバーシティ技術の元で、ネットワークによって被覆したいエリアと、基地局およびアンテナを配置できる場所の候補地が与えられた際に、最小のコストでエリアを被覆する配置パターンを計算する手法に関する。
【背景技術】
【０００２】
無線の基地局やアンテナの空間的な配置を定めるセル設計においては、できるだけ少ない基地局やアンテナの数で対象のエリアを被覆できるように設計をおこなう必要がある。従来のUniversal Mobile Telecommunications System（UMTS）でのセル設計については多くの研究が報告されており、非特許文献１では、セル設計問題を集合被覆問題へと定式化し、貪欲法によって準最適解を得る手法を提案している。また、非特許文献２および３では、通信品質を制約条件へと含んだセル最適設計問題をモデル化し、タブーサーチや焼きなまし法等のメタヒューリスティクスを用いて準最適解を得る手法を提案している。これらの文献が対象としているUMTSにおいては、一つのセルを構成するのはただ一つのアンテナのみである。
【０００３】
一方で、近年LTE-AdvancedにおいてCooperated Multipointとして採用され注目を集めているマクロダイバーシティにおいては、一つのセルを複数のアンテナで協調して構成する（非特許文献４参照）。マクロダイバーシティ環境下におけるセル設計問題については、非特許文献５では基地局およびアンテナを自由に配置できるといった条件の下で、漸近的に最適となるセル配置パターンを提案し、非特許文献６では、基地局およびアンテナの配置候補場所が与えられた下での問題を、整数計画問題へと定式化して最適解を得る手法を提案している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】K. Tutschku. Demand-based radio network planning of cellular mobile communication systems. In INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Vol. 3, pp. 1054-1061 vol.3, 1998.
【非特許文献２】E. Amaldi, A. Capone, and F. Malucelli. Planning UMTS base station location: optimization models with power control and algorithms. Wireless Communications, IEEE Transactions on, Vol. 2, No. 5, pp. 939-952, 2003.
【非特許文献３】J. Yang, M.E. Aydin, J. Zhang, and C. Maple. UMTS base station location planning: a mathematical model and heuristic optimisation algorithms. Communications, IET, Vol. 1, No. 5, pp. 1007-1014, 2007.
【非特許文献４】H. Saito, O. Kagami, M. Umehira, and Y. Kado. Wide area ubiquitous network: the network operator's view of a sensor network. Communications Magazine, IEEE, Vol. 46, No. 12, pp. 112-120, 2008.
【非特許文献５】H. Saito and D. Uchida. Asymptotic minimum coverage using macroscopic diversity. Mobile Computing, IEEE Transactions on, Vol. 12, No. 8, pp. 1518-1531, 2013.
【非特許文献６】Y. Ikeda, H. Saito, and R. Kawahara. Cell planning with macroscopic diversity: Optimal cell deployment and sinr evaluation under frequency scheduling. In Vehicular Technology Conference, 2014. VTC 2014-Spring, IEEE 79th, 2014.
【非特許文献７】Q. Wang, D. Jiang, G. Liu, and Z. Yan. Coordinated multiple points transmission for lte-advanced systems. In Wireless Communications, Networking and Mobile Computing, 2009. WiCom '09. 5th International Conference on, pp. 1-4, Sept 2009.
【非特許文献８】P. Marsch, M. Grieger, and G. Fettweis. Field trial results on different uplink coordinated multi-point (comp) concepts in cellular systems. In Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pp. 1-6, Dec 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献５および６はいずれもオムニアンテナによるマクロダイバーシティを想定している。一方、セクタアンテナを用いたマクロダイバーシティについても近年同様に研究が進んでいる（非特許文献７および８参照）。しかし、セクタアンテナを用いたマクロダイバーシティについては、最小のコストでセルを設計する手法は提案されていない。
【０００６】
セクタアンテナを用いたマクロダイバーシティにおける基地局の配置場所およびセルの配置パターンは、セルを凸多角形で表現し、凸多角形の頂点に基地局を配置すると仮定して、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを決定する問題に帰着することができる。
【０００７】
本発明は、凸多角形のセルで被覆する領域である二次元平面が与えられ、基地局の配置候補地である頂点配置候補地が与えられたときに、セクタアンテナを用いたマクロダイバーシティ環境に適用可能な、基地局の配置場所である頂点配置場所と、セルの配置パターンである凸多角形の配置パターンを決定することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一形態に係る配置場所および配置パターン計算装置は、
第１の二次元平面を凸多角形の集合によって被覆する際に、凸多角形の頂点の配置場所および凸多角形の配置パターンを出力する配置場所および配置パターン計算装置であって、
被覆をおこなう対象の第１の二次元平面と、当該第１の二次元平面を内包する第２の二次元平面と、当該第２の二次元平面内に分布した、各々がコストを持つ頂点配置候補地の集合とを受け取る入力部と、
前記頂点配置候補地の集合から、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙する多角形列挙部と、
凸多角形が前記第１の二次元平面上に重複および隙間がないように配置されるという条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算する配置場所および配置パターン計算部と、
計算された頂点の配置場所および凸多角形の配置パターンを出力する出力部と、
を有することを特徴とする。
【０００９】
また、本発明の一形態に係る配置場所および配置パターン計算方法は、
第１の二次元平面を凸多角形の集合によって被覆する際に、凸多角形の頂点の配置場所および凸多角形の配置パターンを出力する配置場所および配置パターン計算装置における配置場所および配置パターン計算方法であって、
被覆をおこなう対象の第１の二次元平面と、当該第１の二次元平面を内包する第２の二次元平面と、当該第２の二次元平面内に分布した、各々がコストを持つ頂点配置候補地の集合とを受け取るステップと、
前記頂点配置候補地の集合から、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙するステップと、
凸多角形が前記第１の二次元平面上に重複および隙間がないように配置されるという条件のもとで、頂点の配置コストが最小となる頂点の配置場所および凸多角形の配置パターンを計算するステップと、
計算された頂点の配置場所および凸多角形の配置パターンを出力するステップと、
を有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、凸多角形のセルで被覆する領域である二次元平面が与えられ、基地局の配置候補地である頂点配置候補地が与えられたときに、セクタアンテナを用いたマクロダイバーシティ環境に適用可能な、基地局の配置場所である頂点配置場所と、セルの配置パターンである凸多角形の配置パターンを決定することが可能になる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例に係る配置場所および配置パターン計算装置の構成例を示すブロック図
【図２】本発明の実施例１に係る配置場所および配置パターン計算方法のフローチャート
【図３】本発明の実施例２に係る配置場所および配置パターン計算方法のフローチャート
【図４】本発明の実施例３に係る配置場所および配置パターン計算方法のフローチャート
【図５】本発明の実施例７に係る配置場所および配置パターン計算方法のフローチャート
【図６】本発明の実施例８に係る配置場所および配置パターン計算方法にしたがってシミュレーションをおこなった際の、配置された基地局数の結果を示す図
【図７】本発明の実施例８に係る配置場所および配置パターン計算方法にしたがってシミュレーションをおこなった際の、セルの配置パターンの結果を示す図
【図８】本発明の実施例８に係る配置場所および配置パターン計算方法にしたがってシミュレーションをおこなった際の、配置されたセルの分布の結果を示す図
【発明を実施するための形態】
【００１２】
以下、図面を用いて本発明の実施例を説明する。
【００１３】
図１は本発明の実施例に係る配置場所および配置パターン計算装置の構成例を示すブロック図である。本発明の実施例は、セクタアンテナを用いたマクロダイバーシティ環境において基地局の配置候補地が与えられた下で、制約条件がホモロジーによって表現された組合せ最適化問題へとモデル化することで準最適な基地局配置場所を決定し、セル配置パターンを決定する技術に関するものである。セクタアンテナのビーム幅を任意に定められると仮定すると、セルは、協調する基地局同士を結んだ凸多角形で定義できる。基地局の配置場所およびセルの配置パターンを決定するために、凸多角形の頂点に基地局を配置するときの配置コストを最小とする問題を、0-1整数設計問題として定式化し、それを解くことによって、頂点の配置場所および凸多角形の配置パターンを計算する。
【００１４】
本発明の実施例に係る配置場所および配置パターン計算装置１００は、二次元平面を凸多角形の集合によって被覆する際に、凸多角形の頂点の配置場所および凸多角形の配置パターンを出力する装置である。配置場所および配置パターン計算装置１００は、プロセッサ等のＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）等のメモリ装置、ハードディスク等の記憶装置等から構成されたコンピュータでもよい。例えば、以下に説明する配置場所および配置パターン計算装置１００の各機能及び処理は、記憶装置又はメモリ装置に格納されているデータやプログラムをＣＰＵが実行することによって実現される。
【００１５】
配置場所および配置パターン計算装置１００は、入力部1 １０１、多角形列挙部１０３、係数計算部１０５、BIP計算部１０７および出力部1 １０９を有する。BIP計算部１０７は、頂点の配置場所および凸多角形の配置パターンを計算する配置場所および配置パターン計算部に相当する。
【００１６】
入力部1 １０１は、凸多角形の集合によって被覆をおこなう対象の二次元平面Ξと、二次元平面Ξを内包する二次元平面
【００１７】
【数１】
2016091400.tif 000003
と、二次元平面
【００１８】
【数２】
2016091400.tif 000004
内に分布した、各々がコストを持つ頂点配置候補地の集合
【００１９】
【数３】
2016091400.tif 000005
とを受け取る。
【００２０】
多角形列挙部１０３は、凸多角形を形成することができる条件を満たす凸多角形の候補および凸多角形の辺となる線分の候補を列挙する。
【００２１】
係数計算部１０５は、BIP計算部１０７における最適化計算に必要な係数の計算を行う。例えば、BIP計算部１０７における計算のための線分、頂点および凸多角形の関係を表す係数として、線分が凸多角形の辺であるか、頂点が線分の端点であるか、凸多角形同士が重なり合うか、凸多角形同士が重なり合わず且つ辺を共有するかが計算される。
【００２２】
BIP計算部１０７は、凸多角形は頂点を
【００２３】
【数４】
2016091400.tif 000006
上に持ちかつ重複および隙間が無いように配置されるとし、頂点の配置コストが最小となるように凸多角形がΞを被覆するような頂点の配置場所および凸多角形の配置パターンを、0-1整数計画問題（BIP）により計算する。
【００２４】
出力部1 １０９は、BIP計算部１０７により計算された頂点の配置場所および凸多角形の配置パターンを出力する。
【００２５】
これらの具体的な手法については、以下の実施例１で説明する。
【００２６】
また、上記（実施例１）の手法により、無線ネットワークを設計する対象の空間に、基地局を配置できる候補地が与えられた下で、セクタアンテナを用いたマクロダイバーシティによって形成されるセルで対象の空間を被覆するような場合に、最小の基地局配置コストで被覆をおこなうような基地局およびセルの配置パターンを計算することができる。セクタアンテナを用いたマクロダイバーシティ環境への適用例については、以下の実施例４で説明する。
【００２７】
また、配置場所および配置パターン計算装置１００は、入力部2 １１１、最適化計算部１１３、制約条件確認部１１５および出力部2 １１７を有してもよい。
【００２８】
入力部2 １１１は、入力部1 １０１と同様に、被覆をおこなう対象の二次元平面Ξと、二次元平面Ξを内包する二次元平面
【００２９】
【数５】
2016091400.tif 000007
と、二次元平面
【００３０】
【数６】
2016091400.tif 000008
内に分布した、各々がコストを持つ頂点配置候補地の集合
【００３１】
【数７】
2016091400.tif 000009
とを受け取る。
【００３２】
最適化計算部１１３は、凸多角形の一辺の長さがしきい値以下の三角形とした場合、頂点の配置場所として、自身の頂点を配置された頂点上に持つような三角形を、Ξを被覆するように重複および隙間なく配置することができるような、配置コストが準最適である頂点配置場所Bminを最適化手法を用いて探索する。
【００３３】
制約条件確認部１１５は、被覆対象の領域を被覆するような三角形の集合を形成することができない場合、準最適な頂点配置場所を算出するための評価値にペナルティ項を与える。
【００３４】
出力部2 １１７は、準最適な頂点配置場所Bminを出力する。
【００３５】
これらの具体的な手法については、以下の実施例２で説明する。
【００３６】
また、上記（実施例２）の手法により、無線ネットワークを設計する対象の空間に、基地局を配置できる候補地が与えられた下で、セクタアンテナを用いたマクロダイバーシティによって形成されるセルで対象の空間を被覆するような場合に、配置コストが準最適である基地局の配置場所を計算することができる。セクタアンテナを用いたマクロダイバーシティ環境への適用例については、以下の実施例５で説明する。
【００３７】
また、凸多角形の一辺の長さがしきい値以下の三角形とした場合、出力部2 １１７における準最適な頂点配置場所Bminを入力部1 １０１に入力してもよい。入力部1 １０１は、準最適な頂点配置場所Bminを
【００３８】
【数８】
2016091400.tif 000010
とみなしてもよい。
【００３９】
このときの具体的な手法については、以下の実施例３で説明する。
【００４０】
また、上記（実施例３）の手法により、無線ネットワークを設計する対象の空間に、基地局を配置できる候補地が与えられた下で、セクタアンテナを用いたマクロダイバーシティによって形成されるセルで対象の空間を被覆するような場合に、最小の基地局配置コストで被覆をおこなうような基地局およびセルの配置パターンを計算することができる。セクタアンテナを用いたマクロダイバーシティ環境への適用例については、以下の実施例６で説明する。
【００４１】
更に、制約条件確認部１１５は、準最適な頂点配置場所Bminを算出するための評価値に、頂点同士の距離が均一になるような値を与えてもよい。その結果、最適化計算部１１３は、頂点が一様に配置されるような、配置コストが準最適である頂点配置場所Bminを計算することができる。このような頂点同士の距離を考慮した具体的な手法については、以下の実施例７で説明する。
【００４２】
また、上記（実施例７）の手法により、セクタアンテナを用いたマクロダイバーシティ環境において、基地局間が一様に配置されるような基地局の配置場所を計算することができる。セクタアンテナを用いたマクロダイバーシティ環境への適用例については、以下の実施例８で説明する。
【実施例１】
【００４３】
本発明の実施例１においては、凸多角形による被覆をおこなう対象の二次元平面Ξと、Ξを内包する二次元平面
【００４４】
【数９】
2016091400.tif 000011
が与えられ、頂点配置候補地の集合
【００４５】
【数１０】
2016091400.tif 000012
が
【００４６】
【数１１】
2016091400.tif 000013
内に分布しているとする。また、各頂点については配置する際のコストが与えられているとする。被覆をおこなう凸多角形は、自身の頂点を頂点配置候補地に持つものとする。ここで、凸多角形を形成することができる条件を満たす頂点の組合せを全て列挙し、それらの凸多角形を配置するかしないかを表す設計変数zicを導入する。また、凸多角形の辺となるような線分についても全て列挙し、それらの線分を凸多角形の辺として配置するかしないかを表す設計変数zjsを導入する。また、
【００４７】
【数１２】
2016091400.tif 000014
内の頂点を配置するかしないかを表す設計変数zkbを導入する。これらを元に、平面グラフにおける面、辺および頂点の数に関する関係性を表すオイラーの性質を用いた制約条件、選択された凸多角形と線分の関係に基づいた制約条件、選択された線分と頂点の関係に基づいた制約条件、凸多角形が重複しないための制約条件、隣接する凸多角形の数に基づいた制約条件、Ξの面積と凸多角形の最大面積の関係から計算される選択される凸多角形の数の下限に基づいた制約条件の下で、頂点の配置コストを最小とする問題を、0-1整数計画問題として定式化し、それを解くことによって最小の頂点配置コストで被覆をおこなう頂点および凸多角形の配置パターンを計算する。
【００４８】
図２を参照して、実施例１について更に説明する。図２は、本発明の実施例１に係る配置場所および配置パターン計算方法のフローチャートである。ここでは、被覆をおこなう凸多角形を形成する条件として、頂点間の距離が全てL以下であり、かつ頂点の数はN以下である頂点で形成される凸多角形とする。
【００４９】
ステップＳ１０１において、入力部1 １０１より、被覆対象の二次元平面Ξと、Ξを内包する二次元平面
【００５０】
【数１３】
2016091400.tif 000015
、二次元平面
【００５１】
【数１４】
2016091400.tif 000016
内に分布した頂点集合
【００５２】
【数１５】
2016091400.tif 000017
および各頂点に応じたコスト
【００５３】
【数１６】
2016091400.tif 000018
が入力される。ここで、nbは集合内の頂点数であり、
【００５４】
【数１７】
2016091400.tif 000019
はそれぞれ、
【００５５】
【数１８】
2016091400.tif 000020
内の座標として表される。
【００５６】
ステップＳ１０３において、入力されたデータを元に多角形列挙部１０３において、被覆をおこなう凸多角形の候補および凸多角形の辺となる線分の候補が全て列挙される。列挙のアルゴリズムの疑似コードは下記のとおりである。
【００５７】
【数１９】
2016091400.tif 000021
ここで、
【００５８】
【数２０】
2016091400.tif 000022
は頂点bi1およびbi2を結ぶ線分であり、L以下の距離にある二点間を結ぶ線分を線分の候補として数え上げる事を示している。また、
【００５９】
【数２１】
2016091400.tif 000023
は
【００６０】
【数２２】
2016091400.tif 000024
のうちbj以外を頂点とする凸包であり、
【００６１】
【数２３】
2016091400.tif 000025
は
【００６２】
【数２４】
2016091400.tif 000026
を頂点とするin角形である。これは、各頂点間の距離がL以下であり、かつそれらの頂点を結んで凸in角形を形成可能である場合に、その凸in角形を凸多角形の候補として数え上げる事を示している。数え上げられた全線分候補の数をns、全凸多角形候補の数をncとする。
【００６３】
ステップＳ１０５において、数え上げられた全ての線分候補および凸多角形候補のデータをもとに、係数計算部１０５では最適化計算に必要な係数の計算をおこなう。計算されるのは下記の係数である。
ui,jcs(i=1,...,nc,j=1,...,ns)・・・線分ljが多角形Siの辺であるとき1、そうでない場合0
uj,ksb(j=1,...,ns,k=1,...,nb)・・・頂点kが線分ljの端点であるとき1、そうでない場合0
vi,i'lap(i,i'=1,...,nc)・・・i≠i'でかつ多角形Siと多角形Si'が重なり合うとき1、そうでない場合0
vi,i'adj(i,i'=1,...,nc)・・・i≠i'でかつ多角形Siと多角形Si'が重なり合わずかつ辺を共有するとき1、そうでない場合0
ei(i=1,...,nc)・・・凸多角形Siの辺のうち、被覆対象の二次元平面Ξと重複する辺の数
ステップＳ１０７において、BIP計算部１０７は以下の0-1整数計画問題（BIP）の計算により配置する頂点、線分および凸多角形を決定する。設計変数として、凸多角形Siを配置するとき1、そうでない場合0となるzic、線分ljを配置するとき1、そうでない場合0となるzjs、頂点bkを配置するとき1、そうでない場合0となるzkbの3種を導入する。この時、最小化する目的となる頂点の配置コストは
【００６４】
【数２５】
2016091400.tif 000027
として表される。ただし、配置する凸多角形、線分および頂点については、以下の制約条件を満足することが求められる。なお、Mは変数サイズに比べて十分に大きな値である。
全ての多角形が隙間かつ重複なく隣接しているとすると、オイラー標数より
【００６５】
【数２６】
2016091400.tif 000028
が成り立つ。配置する凸多角形と配置する線分の関係より
【００６６】
【数２７】
2016091400.tif 000029
が成り立つ。配置する線分と配置する頂点の関係より
【００６７】
【数２８】
2016091400.tif 000030
が成り立つ。配置された凸多角形が重複しない条件より
【００６８】
【数２９】
2016091400.tif 000031
が成り立つ。配置された凸多角形とそれに隣接する他の配置された凸多角形の数の関係より
【００６９】
【数３０】
2016091400.tif 000032
が成り立つ。凸多角形が取りうる最大の面積、すなわち一辺の長さがLの正N角形の面積Smaxと被覆対象の二次元平面||Ξ||より、被覆に必要な凸多角形の数の下限から
【００７０】
【数３１】
2016091400.tif 000033
が成り立つ。ここで、
【００７１】
【数３２】
2016091400.tif 000034
は実数xの小数点以下を切り上げた整数である。BIP計算部１０７は(2)-(7)の制約条件を満足しながら(1)を最小とする設計変数zic、zjsおよびzkbを計算する。BIPの計算アルゴリズムの例としては分枝限定法などが挙げられる。
【００７２】
ステップＳ１０９において、計算された設計変数を元に、出力部1 １０９より頂点および凸多角形の配置パターンを出力する。
【実施例２】
【００７３】
本発明の実施例２においては、凸多角形を一辺の長さがしきい値以下の三角形とした場合に、頂点の配置場所として、自身の頂点を配置された頂点上に持つ三角形を、Ξを被覆するように重複および隙間なく配置することができるような、配置コストが準最適である頂点配置場所を、最適化手法を用いて探索する。この時、最適化問題のサイズは、
【００７４】
【数３３】
2016091400.tif 000035
個の頂点配置候補地から実際に配置する場所を求める問題であるため、問題のサイズは
【００７５】
【数３４】
2016091400.tif 000036
となる。探索における解に対して求められる制約条件としては、その頂点配置場所を選択した場合に、Ξを被覆するような三角形の集合を形成することができるといった制約条件となる。この制約条件を、選択した頂点配置場所を線分で結ぶことによって得られる単体的複体を対象としたホモロジーの計算によって計算する。最適化手法の探索においては、評価値を選択されている頂点配置場所のコストの総和とし、ホモロジーの計算によって解候補が制約条件を侵害すると判断された場合には高い値を、そうでない場合は0のような十分に低い値を評価値に加えるようなペナルティ項を評価値に加える。最適化手法によってできるだけ評価値の低くなるような解を計算することで、三角形によってΞを被覆できる準最適な頂点配置場所を探索することができる。
【００７６】
図３を参照して、実施例２について更に説明する。図３は、本発明の実施例２に係る配置場所および配置パターン計算方法のフローチャートである。ここでは、被覆をおこなう三角形は、頂点を頂点配置候補地上に持ち、一辺の長さがL以下であるとする。
【００７７】
ステップＳ２０１において、入力部2 １１１より、被覆対象の二次元平面Ξと、Ξを内包する二次元平面
【００７８】
【数３５】
2016091400.tif 000037
、二次元平面
【００７９】
【数３６】
2016091400.tif 000038
内に分布した頂点集合
【００８０】
【数３７】
2016091400.tif 000039
および各頂点に応じたコスト
【００８１】
【数３８】
2016091400.tif 000040
が入力される。ここで、nbは集合内の頂点数であり、
【００８２】
【数３９】
2016091400.tif 000041
はそれぞれ、
【００８３】
【数４０】
2016091400.tif 000042
内の座標として表される。
【００８４】
ステップＳ２０３において、入力されたデータをもとに、最適化計算部１１３は、頂点の配置場所として、自身の頂点を配置された頂点上に持つ三角形を、Ξを被覆するように重複かつ隙間無く配置することができるような、配置コストが準最適である頂点配置場所を最適化アルゴリズムによって探索する。ここでは最適化アルゴリズムとして、焼きなまし法を用いる例を示す。アルゴリズムの擬似コードは下記のとおりである。
【００８５】
【数４１】
2016091400.tif 000043
ここで、Bは頂点配置場所の解候補、E(B)はBに対する評価値、Tは焼きなまし法における温度パラメータ、αは焼きなまし法における冷却の度合いを決めるパラメータ、cmaxはイテレーション回数、mmaxは冷却を実施するイテレーション数である。initial solution B0は初期解であり、
【００８６】
【数４２】
2016091400.tif 000044
からランダムに選択された頂点配置場所の集合である。また、neighbor solutionは、現状の解Bの近傍解であり、例えば選択する頂点配置場所を1、選択しない頂点配置場所を0で表すような長さnbのビット列で解を表現する場合、近傍解はビット列を十分に低い確率でランダムに反転させる事で得られる。E(B)については、解の中で選択されている頂点配置場所のコストの総和と、解が制約条件を満たす場合0、そうでない場合には頂点配置候補地の数
【００８７】
【数４３】
2016091400.tif 000045
に加えて十分に大きい値Λとなるペナルティ項の和として与えられる。制約条件は、その頂点配置場所を選択した場合に、被覆対象の領域を被覆するような三角形の集合を形成することができるといった条件となる。制約条件の確認は、ステップＳ２０５において、制約条件確認部１１５において行われる。
【００８８】
ステップＳ２０５において、制約条件確認部１１５では、入力された解Bを元に、まず初めに下記のような単体が列挙される。
・b1,b2,...,b|B|の各頂点を、自身の
【００８９】
【数４４】
2016091400.tif 000046
上への射影とみなす0単体の集合
・距離がL以下のb1,b2,...,b|B|内の2点をすべて結んだ時にできる各線分を、自身の
【００９０】
【数４５】
2016091400.tif 000047
上への射影とみなす1単体の集合
・互いの距離がL以下のb1,b2,...,b|B|内のN点をすべて結んだ時にできる各ポリトープを、自身の
【００９１】
【数４６】
2016091400.tif 000048
上への射影とみなすN-1単体の集合。ただし2<N≦|B|とする。
【００９２】
上記で列挙された単体をもとに、下記の6種類の単体的複体を計算する。
Call・・・全ての単体の集合によって形成される単体的複体
Cout・・・自身の
【００９３】
【数４７】
2016091400.tif 000049
上への射影が
【００９４】
【数４８】
2016091400.tif 000050
上に存在する0単体およびどのN単体（N＞1）の面でもなくかつ自身の
【００９５】
【数４９】
2016091400.tif 000051
上への射影がΞと交わらない1単体および自身の面である1単体の
【００９６】
【数５０】
2016091400.tif 000052
上への射影が少なくとも2つはΞと交わらないN単体（N>1）の集合によって形成される単体的複体
Cout1,Cout2・・・Coutを構成する単体のうち、Ξの中心を通る任意の直線のある一方側の半平面上にのみ自身の射影が存在する単体の集合によって形成される単体的複体と、もう一方の半平面上にのみ自身の射影が存在する単体の集合によって形成される単体的複体
Cout3,Cout4・・・Coutを構成する単体のうち、Ξの中心を通りかつCout1およびCout2を分割する直線に対して垂直な直線のある一方側の半平面上にのみ自身の射影が存在する単体の集合によって形成される単体的複体と、もう一方の半平面上にのみ自身の射影が存在する単体の集合によって形成される単体的複体
次に、6個の単体的複体の1次のベッチ数を、下記のようにして計算する。
【００９７】
単体的複体Kについて、頂点{v0,...,vn}からなるK内のn単体を、順序づけられた単体として|v0,...,vn|のように表現する。ここで、順序づけられているとは、2個の頂点の交換が符号の変換に相当すること、すなわち|v0,...,vi,...,vj,...,vn|=−|v0,...,vj,...,vi,...,vn|として表されることである。この時、単体的複体K内の、順序づけられたn単体の集合について、各要素を変数とみなし、それらを基底としたベクトル空間Cn(K)を考える。ただし、n=0,…,dimKであり、dimKとはK内の単体の最も高い次元である。このようなベクトル空間を考えると、n単体の境界を取り出すということが、Cn(K)に対するCn-1(K)への線形写像∂nとして下記のように定義できる。
【００９８】
【数５１】
2016091400.tif 000053
たとえばC2(K)上の点として表される三角形|ABC|の境界は、∂nによりC1(K)上の点|BC|−|AC|+|AB|として表現される。次に、Cn(K)上の下記の二つの部分空間を考える。一つはサイクルZn(K)であり、もう一つはバウンダリBn(K)である。サイクルは境界を持たないようなK内の単体的複体の集合によって構成されるベクトル空間であり、写像∂nの核で表される。たとえばZ1(K)は、1単体によってつながれた輪のような単体的複体で構成されるベクトル空間である。バウンダリは一次元上の単体の境界となるような単体的複体の集合によって構成されるベクトル空間であり、写像∂n+1の像として表される。この時、Kのn次のホモロジーがHn(K)=Zn(K)/Bn(K)のような商空間で定義される。ホモロジーHn(K)の階数がn次のベッチ数である。Hn(K)の階数rank(Hn(K))は、rank(Zn(K))−rank(Bn(K))として計算される。単体的複体Kの一次のベッチ数をβ1(K)とした時、各単体的複体について下記が満たされる場合に頂点集合は制約条件を満たすと判断する。
β1(Call)=0∧β1(Cout)=1∧β1(Cout1)=0∧β1(Cout2)=0∧β1(Cout3)=0∧β1(Cout4)=0
制約条件確認部１１５は、解候補Bが制約条件を満たすか満たさないかを最適化計算部１１３に出力する。
【００９９】
ステップＳ２０７およびＳ２０９において、以上のような評価値計算を最適化アルゴリズムの中で繰り返し、ステップＳ２１１において、最適化計算部１１３では制約条件を満足する頂点配置場所の準最適解Bminを計算する。
【０１００】
ステップＳ２１３において、出力部2 １１７はBminを出力する。
【実施例３】
【０１０１】
本発明の実施例３においては、実施例１において、凸多角形を一辺の長さがしきい値以下の三角形とした場合に、実施例２を用いて三角形によってΞを被覆できる準最適な頂点配置場所Bminを探索し、その頂点配置場所Bminを実施例１における頂点配置候補地の集合
【０１０２】
【数５２】
2016091400.tif 000054
とみなした上で、実施例１により被覆をおこなう頂点および三角形の配置パターンを計算する。
【０１０３】
図４を参照して、実施例３について更に説明する。図４は、本発明の実施例３に係る配置場所および配置パターン計算方法のフローチャートである。ここでは、被覆をおこなう三角形は、頂点を頂点配置候補地上に持ち、一辺の長さがL以下であるとする。
【０１０４】
ステップＳ２０１において、データは入力部2 １１１より入力され、実施例２において図３のステップＳ２０３〜Ｓ２１３を参照して説明したとおり、頂点配置場所の準最適解Bminが計算され、出力部2 １１７から出力される。
【０１０５】
ステップＳ１０１'において、出力されたデータは元の入力データと共に入力部1 １０１に送られ、Bminを実施例１における
【０１０６】
【数５３】
2016091400.tif 000055
とみなした上で実施例１において図２のステップＳ１０３〜Ｓ１０９を参照して説明したとおり、出力部1 １０９より頂点の配置場所および三角形の配置パターンが出力される。
【実施例４】
【０１０７】
本発明の実施例４においては、セクタアンテナを用いたマクロダイバーシティ環境によるセル設計を、実施例１の手法を用いておこなう。セルは、協調する基地局同士を結んだ凸多角形で定義されるとし、各基地局のセクタアンテナは、凸多角形における自身の角度に合わせたビーム幅を持つとする。
【０１０８】
この時、実施例１における
【０１０９】
【数５４】
2016091400.tif 000056
がそれぞれ、セルによって被覆をおこなう対象となる領域、基地局の配置候補地が分布する領域および基地局の配置候補地の集合に対応する。また、実施例１における凸多角形がセルに対応し、凸多角形を形成することができる条件としては、選択した基地局を協調させて一つのセルを形成できる条件とする。実施例１における頂点の配置コストは、その配置候補地に基地局を配置した際の配置コストに対応する。実施例１を用いて得られた頂点集合および凸多角形の集合をそれぞれ、配置する基地局の集合およびセルの集合とみなし、基地局の配置コストが最小となるような基地局およびセルの配置パターンを決定する。
【実施例５】
【０１１０】
本発明の実施例５では、実施例４において、セルの形状を三角形、セルの形成条件を三つの基地局間の距離がしきい値L以下であるといった条件にした場合に、セルによって被覆対象の領域を被覆できる準最適な基地局の配置場所を実施例２の手法を用いて探索する。
【０１１１】
ここでは、実施例２における
【０１１２】
【数５５】
2016091400.tif 000057
がそれぞれ、セルによって被覆をおこなう対象となる領域、基地局の配置候補地が分布する領域および基地局の配置候補地の集合に対応する。また、実施例２における一辺の長さがL以下の三角形がセルに対応する。実施例２における頂点の配置コストは、その配置候補地に基地局を配置した際の配置コストに対応する。実施例２を用いて得られた頂点集合を基地局の配置場所の集合とみなし、基地局の配置場所を決定する。
【実施例６】
【０１１３】
本発明の実施例６では、実施例４において、セルの形状を三角形、セルの形成条件を三つの基地局間の距離がしきい値L以下であるといった条件にした場合に、実施例３を用いて準最適な基地局の配置場所およびセルの配置パターンを決定する。例えば、実施例４における0-1整数計画問題のサイズは基地局の候補地数
【０１１４】
【数５６】
2016091400.tif 000058
の組合せによって増加するため、
【０１１５】
【数５７】
2016091400.tif 000059
が大きい時0-1整数計画問題はサイズが爆発し計算不可能となるが、このような場合に、実施例３の手法に従って、最初に実施例５（実施例２）の手法を用いて、サイズが
【０１１６】
【数５８】
2016091400.tif 000060
である最適化問題によって、セルによって被覆対象の領域を被覆できる準最適な基地局の集合を探索し、得られた基地局の集合が十分に小さければ、その基地局集合を実施例４（実施例１）における
【０１１７】
【数５９】
2016091400.tif 000061
と見做すことで、実施例４（実施例１）の手法によりセルの配置パターンを計算することができる。
【実施例７】
【０１１８】
本発明の実施例７では、実施例２において、単体的複体上の全線分の長さのばらつきが大きい時に、評価値も大きくなるようなペナルティ項を加えることにより、設置コストが準最適であり、かつしきい値以下の距離にある二頂点間の距離が出来る限り均一となるような、一様な頂点配置場所を探索する。
【０１１９】
図５を参照して、実施例７について更に説明する。図５は、本発明の実施例７に係る配置場所および配置パターン計算方法のフローチャートである。
【０１２０】
実施例２において図３を参照して説明したように、ステップＳ２０１において、データは入力部2 １１１より入力され、ステップＳ２０３において、最適化計算部１１３は配置コストが準最適である頂点配置場所を最適化アルゴリズムによって探索する。
【０１２１】
ステップＳ２０４において、最適化計算部１１３での評価値の計算に際し、解において選択された頂点の配置コストの総和と制約条件によって定められるペナルティ項の和に加えて、制約条件確認部１１５で列挙されたCall内の一単体の
【０１２２】
【数６０】
2016091400.tif 000062
上への射影である線分の長さの変動係数vを制約条件確認部１１５において計算し、その値に比例した値λvを、評価値に対して加える。
【０１２３】
そして、実施例２において図３のステップＳ２０５〜Ｓ２１３を参照して説明したとおり、頂点配置場所の準最適解Bminが計算され、出力部2 １１７から出力される。これにより、最適化計算部１１３では、長さL以下の距離にある頂点同士の距離ができる限り均一になるような解を選択するようになる。頂点の配置コストを削減することと、vを小さくすることは時にトレードオフの関係になるが、どちらをどの程度優先するかについてはλの値によって決定される。
【実施例８】
【０１２４】
本発明の実施例８では、実施例６において、最適化計算部１１３における準最適な基地局の集合の計算を、実施例２の手法ではなく実施例７の手法を用いて求める。これにより、しきい値L以下の距離にある基地局間の距離ができる限り均一になるような、一様な基地局の配置パターンを計算することができる。得られた基地局の集合を入力として実施例４を用いてセルの配置パターンを計算することにより、できる限りセルの大きさが均一となるようなセルの配置パターンを計算することができる。
【０１２５】
＜本発明の実施例の効果＞
本発明の実施例により、セクタアンテナを用いたマクロダイバーシティでセル設計を行う際に、最小のコストとなるセルの配置パターンを決定することができる。また、基地局の配置候補地が多く最適配置パターンの計算が困難な場合についても、セル設計問題を小さなサイズの二つの問題へと分割することにより、準最適なセル配置パターンを得ることができる。ここでは、後者のような問題に対して、実施例８をシミュレーションによって実施した結果を述べる。
【０１２６】
【数６１】
2016091400.tif 000063
をそれぞれ、25km×25kmの正方形、
【０１２７】
【数６２】
2016091400.tif 000064
の中心に各辺を
【０１２８】
【数６３】
2016091400.tif 000065
と平行にして内包されている19km×19kmの正方形および
【０１２９】
【数６４】
2016091400.tif 000066
内に強度νのポアソン点過程に従って分布した点とする。νについては、ν=0.5とν=1の2種の場合についてシミュレーションをおこなった。L=5kmとし、また、基地局の配置コストは全て1とすることで、基地局の配置数を最小化することを目的とした。最適化計算部１１３における最適化アルゴリズムについては焼きなまし法を用い、パラメータについてはT=2、α=0.9、cmax=500,000、mmax=10,000とした。制約条件に関するペナルティ項については、
【０１３０】
【数６５】
2016091400.tif 000067
とし、また、頂点の配置数を削減することの次に頂点を一様に配置することを優先するため、λvが1より小さくなるよう、λ=1とした。BIP計算部１０７での計算はCPLEX、制約条件確認部１１５でのベッチ数の計算はCHomPを用いた。
シミュレーションは10回おこない、以下の尺度で評価をおこなった。
|Bmin|best・・・各シミュレーションで得られた解（配置基地局数）の中で最も小さかったもの
|Bmin|worst・・・各シミュレーションで得られた解の中で最も大きかったもの
ave(|Bmin|)・・・各シミュレーションで得られた解の平均
var(|Bmin|)・・・各シミュレーションで得られた解の分散
また、比較手法として下記のような貪欲法を用いた。ただし、アルゴリズム内における三角形はすべて、頂点が
【０１３１】
【数６６】
2016091400.tif 000068
上の点であり、一辺の長さが5km以下である
【０１３２】
【数６７】
2016091400.tif 000069
上の三角形である。
[Step1]最も大きな三角形を配置する
[Step2]すでに配置された三角形に隣接し、かつ重複しない最も大きな三角形を配置する
[Step3]三角形の頂点として選択された頂点のうち、3点を結ぶことですでに配置された三角形と重複しない三角形を配置できる場合、その三角形を配置する
[Step4]Step2とStep3を、三角形が配置できなくなるまで繰り返し、最後にΞと重複しない三角形をすべて取り除く。残った三角形をセル、頂点を基地局とみなす。
【０１３３】
シミュレーションの数値結果を図６に示す。ここで、Proposedは実施例８による結果、Greedyは貪欲法による結果である。LBは平面グラフにおけるオイラーの公式を用いて算出された、頂点数の下限であり、timeは一回のシミュレーションに要した平均の時間である。図６より、実施例８によって配置された基地局の数は、貪欲法によって配置された基地局の数に比べて２割程度低く、また下限との差を４割程度削減できている。一方で、ホモロジーの計算を要するため計算時間は貪欲法に比べて大きくなってしまっているが、基地局設計のためのシミュレーションとしては問題の無い時間であると言える。
【０１３４】
また、シミュレーションで得られたセルの配置パターンを図７に示す。図７より、貪欲法では、極端にサイズの小さいセルが生じてしまっている。図８はセルのサイズの分布を比較した結果であり、貪欲法によって配置されたセルの約２割が、実施例８で配置されたセルの中で最もサイズの小さいセルよりもサイズが小さい事を示している。無線ネットワークにおいてはサイズの小さいセルは周波数割り当ての不公平性やハンドオーバーの増加を導くため、そのような観点においても実施例８によって望ましいセル配置ができていると言える。
【０１３５】
以上のように、本発明の実施例によれば、セクタアンテナを用いたマクロダイバーシティ環境に適用可能な、基地局の配置場所である頂点配置場所と、セルの配置パターンである凸多角形の配置パターンを決定することが可能になる。
【０１３６】
説明の便宜上、本発明の実施例に係る配置場所および配置パターン計算装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係る配置場所および配置パターン計算装置は、ハードウェア、ソフトウェアまたはそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係る配置場所および配置パターン計算装置の各機能を実現させるプログラム、コンピュータに対して本発明の実施例に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係る方法は、実施例に示す順序と異なる順序で実施されてもよい。
【０１３７】
以上、セクタアンテナを用いたマクロダイバーシティ環境に適用可能な、基地局の配置場所である頂点配置場所と、セルの配置パターンである凸多角形の配置パターンを決定するための手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【０１３８】
１００  配置場所および配置パターン計算装置
１０１  入力部1
１０３  多角形列挙部
１０５  係数計算部
１０７  BIP計算部
１０９  出力部1
１１１  入力部2
１１３  最適化計算部
１１５  制約条件確認部
１１７  出力部2
【図１】
2016091400.tif 000070
【図２】
2016091400.tif 000071
【図３】
2016091400.tif 000072
【図４】
2016091400.tif 000073
【図５】
2016091400.tif 000074
【図６】
2016091400.tif 000075
【図７】
2016091400.tif 000076
【図８】
2016091400.tif 000077