(57)【要約】【課題】無線基地局数が多い場合でも最適解を短時間で求めることができ、かつ現状からの変更費用を低く抑えられる無線基地局の収容設計方法、装置およびプログラムを提供する。【解決手段】収容設計システム１において、ハンドオーバ監視部１０１は、無線端末MNの無線基地局eNB間でのハンドオーバを監視し、基地局ペアごとにハンドオーバ数Nを集計する。集計結果はデータベース１０２に蓄積される。収容設計部１０３は、基地局ペアごとに求められたハンドオーバ数Nに基づいて、収容先の移動管理装置が異なる基地局ペア間のハンドオーバ数Nが最少化されるように各移動管理装置に収容する無線基地局の割り当てを設計する。収容設計部１０３において、ゼロベース設計部１０３ａは、収容割当の現状に拘束されずに一から収容設計を行う。現状ベース設計部１０３ｂは、収容割当の現状を一部変更して評価することを繰り返すことで漸進的な改善を図る。【選択図】図１
2019180029.tif 000002
【特許請求の範囲】
【請求項１】
複数の無線端末を収容する各基地局の各移動管理装置への収容を設計する無線基地局の収容設計装置において、
基地局ペアごとに無線端末のハンドオーバ数を判別する手段と、
ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように各移動管理装置への各基地局の収容割当を設計する手段とを具備したことを特徴とする無線基地局の収容設計装置。
【請求項２】
前記収容割当を設計する手段は、収容先の異なる基地局ペア間でのハンドオーバ数を最小化する収容割当を設計することを特徴とする請求項１に記載の無線基地局の収容設計装置。
【請求項３】
前記収容割当を設計する手段がゼロベース設計手段を具備し、
前記ゼロベース設計手段は、各基地局ペアのハンドオーバ数の逆数を当該基地局ペア間の距離としたクラスタリングを実行し、同一グループに分類された基地局を同一の移動管理装置に収容することを特徴とする請求項１または２に記載の無線基地局の収容設計装置。
【請求項４】
前記収容割当を設計する手段が現状ベース設計手段を具備し、
前記現状ベース設計手段は、現状で異なる移動管理装置に収容されている基地局の一部をランダムに入れ替えて評価することを繰り返す乱択アルゴリズムを実行することを特徴とする請求項１ないし３のいずれかに記載の無線基地局の収容設計装置。
【請求項５】
前記乱択アルゴリズムは、フリンジ基地局をフリンジ基地局以外に較べてより高い頻度で入れ替えることを特徴とする特徴とする請求項４に記載の無線基地局の収容設計装置。
【請求項６】
前記乱択アルゴリズムは、現状からの基地局の入れ替え数がより少ない収容割当をより高く評価することを特徴とする請求項４または５に記載の無線基地局の収容設計装置。
【請求項７】
前記各移動管理装置の容量が異なり、前記乱択アルゴリズムは、容量のより多い移動管理装置により多くの無線基地局が収容される収容割当をより高く評価することを特徴とする請求項４または５に記載の無線基地局の収容設計装置。
【請求項８】
前記乱択アルゴリズムは、各移動管理装置の負荷がより平準化される収容割当をより高く評価することを特徴とする請求項４または５に記載の無線基地局の収容設計装置。
【請求項９】
前記乱択アルゴリズムは、容量超過となる移動管理装置の数がより少ない収容割当をより高く評価することを特徴とする請求項４または５に記載の無線基地局の収容設計装置。
【請求項１０】
複数の無線端末を収容する各基地局の各移動管理装置への収容を設計する無線基地局の収容設計方法において、
コンピュータが、
基地局ペアごとに無線端末のハンドオーバ数を判別し、
ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように各移動管理装置への各基地局の収容割当を設計することを特徴とする無線基地局の収容設計方法。
【請求項１１】
複数の無線端末を収容する各基地局の各移動管理装置への収容を設計する無線基地局の収容設計プログラムにおいて、
基地局ペアごとに無線端末のハンドオーバ数を判別し、
ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように各移動管理装置への各基地局の収容割当を設計する、ことをコンピュータに実行させる無線基地局の収容設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線基地局の収容設計方法、装置およびプログラムに係り、特に、各無線基地局が収容する無線端末のハンドオーバ数を指標として、各無線基地局を収容する移動管理装置の負荷が分散されるように、各移動管理装置への各無線基地局の収容を設計する方法、装置およびプログラムに関する。
【背景技術】
【０００２】
LTEに代表される無線ネットワークは、図５に模式的に表したように、多数の無線端末MNを動的に収容する複数の無線基地局eNB（eNodeB）と、これら複数の無線基地局eNBを固定的に収容し、無線端末MNの移動管理を行う複数の移動管理装置と、その上位ネットワーク（図示省略）とから構成される。前記移動管理装置の例としては、コア設備MME（Mobility Management Entity）がある。
【０００３】
各移動管理装置に収容する無線基地局eNBの割り当てや移動管理装置の増設／削減は収容設計と呼ばれる。従来の収容設計は、移動管理装置の容量、利用者端末の移動経路等を考慮し、人手による設計の他、非特許文献１，２に開示されるように、組み合わせ最適化問題・集合分割問題・集合被覆問題に制約条件を追加して整数計画法に落とし込み、ソルバにより解決することが行われていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】藤江哲也, "整数計画法による定式化入門,"オペレーションズ・リサーチ，57-4 (2012), pp.190-197.
【非特許文献２】S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi,"Optimization by Simulated Annealing," Science 220 (4598), pp.671-680.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
収容設計はNP困難であり、問題の規模が大きくなる、すなわち無線基地局数が多くなると最適解を求めることが非常に困難であり、解の収束に時間がかかる。また最適解や準最適解が求められた場合でも、現状からの変更費用が膨大となるおそれがある。
【０００６】
本発明の目的は、上記の従来技術を解決し、無線基地局数が多い場合でも最適解や準最適解を短時間で求めることができ、かつ現状からの変更費用を低く抑えられる無線基地局の収容設計方法、装置およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記の目的を達成するために、本発明は、複数の無線端末を収容する各基地局の各移動管理装置への収容を設計する無線基地局の収容設計装置において、以下の構成を具備した点に特徴がある。
【０００８】
(1) 基地局ペアごとに無線端末のハンドオーバ数を判別する手段と、ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように各移動管理装置への各基地局の収容割当を設計する手段とを具備した。
【０００９】
(2) 前記収容割当を設計する手段は、収容先の異なる基地局ペア間でのハンドオーバ数を最小化する収容割当を設計するようにした。
【００１０】
(3) 前記収容割当を設計する手段がゼロベース設計手段を具備し、ゼロベース設計手段は、各基地局ペアのハンドオーバ数の逆数を当該基地局ペア間の距離としたクラスタリングを実行し、同一グループに分類された基地局を同一の移動管理装置に収容するようにした。
【００１１】
(4) 前記収容割当を設計する手段が現状ベース設計手段を具備し、現状ベース設計手段は、異なる移動管理装置に収容されている基地局の一部をランダムに入れ替えて評価することを繰り返す乱択アルゴリズムを実行するようにした。
【００１２】
(5) 乱択アルゴリズムは、フリンジ基地局をフリンジ基地局以外に較べてより高い頻度で入れ替えるようにした。
【発明の効果】
【００１３】
本発明によれば、以下のような効果が達成される。
【００１４】
(1) 基地局ペアごとに無線端末のハンドオーバ数を判別し、ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように各移動管理装置への各基地局の収容割当を設計するので、移動管理装置を跨ぐような処理負荷の高いハンドオーバ数を最小化することができ、各移動管理装置の負荷を軽減できるようになる。
【００１５】
(2) ゼロベース設計手段を設け、各基地局ペアのハンドオーバ数の逆数を当該基地局ペア間の距離としたクラスタリングを実行し、同一グループに分類された基地局を同一の移動管理装置に収容するので、比較的局所最適に陥りにくく、現在の収容設計に囚われない革新的な収容設計を実現し易くなる。また、移動管理装置を追加する場合の再設計などにも対応し易いのみならず、シンプルな制約条件ならば準最適解に比較的高速に収束させることが可能になる。
【００１６】
(3) 現状ベース設計手段を設け、異なる移動管理装置に収容されている基地局の一部同士をランダムに入れ替えて評価することを繰り返すようにしたので、漸進的な改善に留まるものの変更費用を低く抑えられる収容設計が可能になる。
【００１７】
(4) 現状ベース設計手段による基地局のランダムな入れ替えが、フリンジ基地局ではフリンジ基地局以外に較べてより高い頻度で試行されるので、少ない入れ替え回数で評価の高い収容設計を導き出せるようになる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態に係る収容設計システムのブロック図である。
【図２】ゼロベース設計部による第１の収容設計方法を模式的に示した図である。
【図３】現状ベース設計部による第２の収容設計方法を模式的に示した図である。
【図４】フリンジ基地局の識別方法を示した図である。
【図５】本発明が適用されるLTEネットワークの構成を示した図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の一実施形態に係る収容設計装置／システム１の主要部の構成を示したブロック図であり、前記図５を参照して説明したLTEネットワークにおいて、各移動管理装置に収容する無線基地局eNBの割り当てを設計する。
【００２０】
本発明の収容設計システム１は、汎用のコンピュータに後述する各機能を実現するアプリケーション（プログラム）を実装して構成しても良いし、あるいはアプリケーションの一部がハードウェア化またはROM化された専用機や単能機として構成しても良い。
【００２１】
ハンドオーバ監視部１０１は、無線端末MNが移動しながら通信する際に生じる無線基地局eNBのハンドオーバを監視し、基地局ペアごとにハンドオーバ数Nを集計する。集計結果はハンドオーバ履歴としてデータベース１０２に蓄積される。収容設計部１０３は、基地局ペアごとに求められたハンドオーバ数Nに基づいて、原則として、収容先の移動管理装置が異なる基地局ペア間のハンドオーバ数Nが最少化されるように各移動管理装置に収容する無線基地局の割り当てを設計する。
【００２２】
本実施形態では、収容設計部１０３がゼロベース設計部１０３ａおよび現状ベース設計部１０３ｂを含む。ゼロベース設計部１０３ａは、収容割当の現状に拘束されることなく、一から収容設計を行うことで準最適な収容設計を行う。現状ベース設計部１０３ｂは、収容割当の現状を一部変更して評価することを繰り返し、所定の制約、条件下で評価が最良の収容割当を採用することで漸進的な改善を図る。
【００２３】
図２は、前記ゼロベース設計部１０３ａによる第１の収容設計方法を模式的に示した図である。第１の収容設計方法は、現在の移動管理装置収容設計を利用しない教師なし学習によるクラスタリングを基本とする。
【００２４】
本実施形態では、基地局ペア間のハンドオーバ数Nの逆数（または反数）nを当該基地局ペア間の論理的な距離として、物理的な距離とは無関係に各無線基地局eNBを２次元マップ上に配置し［同図(a)］、これにk-means等の適宜のクラスタリング手法を適用することで、ハンドオーバ数のより多い基地局ペア、すなわち論理的な距離のより近い基地局ペアが同一のグループに分類されるクラスタリングを実現し［同図(b)］、グループごとに同一の移動管理装置に収容する。
【００２５】
このようなゼロベース設計部１０３ａによる第１の収容設計方法によれば、比較的局所最適に陥りにくく、現在の移動管理装置収容設計に拘束されない革新的な収容設計が実現されやすい。また、移動管理装置を追加する場合の再設計などにも対応しやすい。さらに、シンプルな制約条件ならば準最適解に比較的高速に収束させることができる。
【００２６】
なお、各移動管理装置の容量、例えば収容可能な移動端末数が異なる場合には、分類された無線端末MNの数がより多いグループを容量のより大きい移動管理装置に割り当てることが望ましい。
【００２７】
図３は、前記現状ベース設計部１０３ｂによる第２の収容設計方法を模式的に示した図である。第２の収容設計方法は、現状の収容環境を出発点として、その一部の無線基地局eNBの収容先を現在の移動管理装置から他の移動管理装置に入れ替えて評価することを繰り返すことで漸進的な改善を図る。
【００２８】
本実施形態では、Simulated Annealing法等の局所探索用の乱択アルゴリズムを用い、現在の移動管理装置収容状態から一ないし複数の無線基地局eNBの収容先を入れ替え、入れ替えの前後におけるハンドオーバ数Nの増減を指標として当該入れ替えを評価することを繰り返す。
【００２９】
なお、現状からの変更費用を低く抑えるために、入れ替え数を評価関数として追加し、現状からの無線基地局eNBの入れ替え数がより少ない収容割当をより高く評価するようにしても良い。あるいは、各移動管理装置の容量が異なる場合には、容量のより多い移動管理装置により多くの無線基地局が収容される収容割当をより高く評価しても良い。
【００３０】
さらに、容量超過となる移動管理装置の数がより少ない収容割当をより高く評価したり、各移動管理装置のシグナリング負荷（ハンドオーバ数）がより平準化される収容割当をより高く評価するようにしても良い。
【００３１】
さらに、ハンドオーバが生じるシグナリングに着目し、シグナリング種別で各ハンドオーバに重み付けを行うようにしても良い。本実施形態では、接続、切断、ベアラ設定、ベアラ解放、移動管理装置内ハンドオーバ、移動管理装置間ハンドオーバに基づいて各ハンドオーバに重み付けが行われる。
【００３２】
また、本実施形態では乱択アルゴリズムの適用に際して、各無線基地局eNBに優先度を設定し、優先度のより高い無線基地局eNBほど、より高い頻度で入り替えが試行されるようにしている。
【００３３】
本実施形態では、各移動管理装置に収容されている無線基地局eNBの物理的な位置に着目し、物理的に収容範囲の境界近傍に位置する無線基地局eNB（フリンジ基地局）については、隣接する他の移動管理装置に収容されている他の無線基地局eNBとの間で無線端末MNのハンドオーバの発生する確率が高いという経験則に基づいて、当該フリンジ基地局に対してより高い優先度を設定している。
【００３４】
フリンジ基地局の識別においては、図４に示したように、各無線基地局eNBの物理的な配置［同図(a)］を点の集合として三角形およびその外接円を作成し、どの三角形の外接円にも点が包括されないように再分割を繰り返す［同図(b)］ことでドロネー分割を完了する［同図(c)］。次いで、各三角形の外接円の中心を結ぶことでボロノイ図を作図し［同図(d)］、三角形の頂点となる基地局が異なるTAC（Tracking Area Code）であればフリンジ基地局として識別できる。
【００３５】
このように、本実施形態によれば、基地局ペアごとに無線端末MNのハンドオーバ数を判別し、ハンドオーバ数のより多い基地局ペアがより優先的に同一の移動管理装置に収容されるように収容割当を設計するので、移動管理装置を跨ぐような処理負荷の高いハンドオーバ数を最小化することができ、各移動管理装置の負荷を軽減できるようになる。
【００３６】
また、本実施形態のシステムはゼロベース設計部１０３ａを備え、各基地局ペアのハンドオーバ数の逆数を当該基地局ペア間の距離としたクラスタリングを実行し、同一グループに分類された基地局を同一の移動管理装置に収容するので、比較的局所最適に陥りにくく、現在の収容設計に囚われない革新的な収容設計を実現し易くなる。また、移動管理装置を追加する場合の再設計などにも対応し易いのみならず、シンプルな制約条件ならば準最適解に比較的高速に収束させることが可能になる。
【００３７】
さらに、本実施形態のシステムは現状ベース設計部１０３ｂを備え、異なる移動管理装置に収容されている基地局の一部同士をランダムに入れ替えて評価することを繰り返すので、漸進的な改善に留まるものの変更費用を低く抑えられる収容設計が可能になる。
【００３８】
さらに、現状ベース設計部１０３ｂによる基地局のランダムな入れ替えが、フリンジ基地局ではフリンジ基地局以外に較べてより高い頻度で試行されるので、少ない入れ替え回数で評価の高い収容設計を導き出せるようになる。
【符号の説明】
【００３９】
eNB（eNodeB）…無線基地局，MN…無線端末，１０１…ハンドオーバ監視部，１０２…データベース，１０３…収容設計部，１０３ａ…ゼロベース設計部，１０３ｂ…現状ベース設計部
【図１】
2019180029.tif 000003
【図２】
2019180029.tif 000004
【図３】
2019180029.tif 000005
【図４】
2019180029.tif 000006
【図５】
2019180029.tif 000007