(57)【要約】【課題】基地局と、基地局から発生する移動トラヒックを処理する移動トラヒック処理機能とを備える移動通信システムにおいて、移動トラヒック処理機能に係るコストが小さくなるように、基地局に移動トラヒック処理機能を割り当てる。【解決手段】割当装置において、移動トラヒック処理機能に関するコスト情報、及び、基地局毎の時系列の移動トラヒック情報を入力する入力手段と、各移動トラヒック処理機能における割当可能な移動トラヒック量、及び割当可能な基地局数に関する制約条件の下で、構築される移動トラヒック処理機能に関するコストを最小にする最適化問題を解くことにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する計算手段とを備える。【選択図】図６
2018207364.tif 000002
【特許請求の範囲】
【請求項１】
複数の基地局と、当該複数の基地局から発生する移動トラヒックを処理する複数の移動トラヒック処理機能を備える移動通信システムにおいて、各基地局を１つの移動トラヒック処理機能に割り当てる割当装置であって、
移動トラヒック処理機能に関するコスト情報、及び、基地局毎の時系列の移動トラヒック情報を入力する入力手段と、
各移動トラヒック処理機能における割当可能な移動トラヒック量、及び割当可能な基地局数に関する制約条件の下で、構築される移動トラヒック処理機能に関するコストを最小にする最適化問題を解くことにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する計算手段と
を備えることを特徴とする割当装置。
【請求項２】
前記計算手段は、各基地局に対する移動トラヒック処理機能の割り当てが所定の時間長の中で可変であるという条件の下で前記最適化問題を解くことにより、当該所定の時間長の中の単位時間毎に基地局に対する移動トラヒック処理機能の割り当てを算出する
ことを特徴とする請求項１に記載の割当装置。
【請求項３】
前記計算手段は、前記最適化問題において、移動トラヒック処理機能の割り当ての変更回数に関するペナルティを更に使用することで、各基地局に対する移動トラヒック処理機能の割り当てを算出する
ことを特徴とする請求項２に記載の割当装置。
【請求項４】
前記計算手段は、ランダムに基地局を移動トラヒック処理機能に割り当てることで得られた解によるコストを上界値の初期値とし、基地局の移動トラヒックを分割して複数の移動トラヒック処理機能への割当を許容することを前提として計算される最適化問題の解によるコストを下界値の初期値としながら、当該初期値から始め、制約充足問題を解くことで下界値を実現する実行可能解が存在するかを調べ、存在する場合は下界値を実現する割り当てを算出し、存在しない場合は、その時点での上界値と下界値の間の値の実行可能解の存在を制約充足問題を解くことで確認し、上界値と下界値の間隔を狭めていく
ことを特徴とする請求項１ないし３のうちいずれか１項に記載の割当装置。
【請求項５】
複数の基地局と、当該複数の基地局から発生する移動トラヒックを処理する複数の移動トラヒック処理機能を備える移動通信システムにおいて、各基地局を１つの移動トラヒック処理機能に割り当てる割当装置が実行する割当方法であって、
移動トラヒック処理機能に関するコスト情報、及び、基地局毎の時系列の移動トラヒック情報を入力する入力ステップと、
各移動トラヒック処理機能における割当可能な移動トラヒック量、及び割当可能な基地局数に関する制約条件の下で、構築される移動トラヒック処理機能に関するコストを最小にする最適化問題を解くことにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する計算ステップと
を備えることを特徴とする割当方法。
【請求項６】
前記計算ステップにおいて、前記割当装置は、各基地局に対する移動トラヒック処理機能の割り当てが所定の時間長の中で可変であるという条件の下で前記最適化問題を解くことにより、当該所定の時間長の中の単位時間毎に基地局に対する移動トラヒック処理機能の割り当てを算出する
ことを特徴とする請求項５に記載の割当方法。
【請求項７】
前記計算ステップにおいて、前記割当装置は、前記最適化問題において、移動トラヒック処理機能の割り当ての変更回数に関するペナルティを更に使用することにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する
ことを特徴とする請求項６に記載の割当方法。
【請求項８】
コンピュータを、請求項１ないし４のうちいずれか１項に記載の割当装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の基地局と、当該複数の基地局から発生する移動トラヒックを処理する複数の移動トラヒック処理機能を備える移動通信システムにおいて、各基地局を１つの移動トラヒック処理機能に割り当てる技術に関連するものである。
【背景技術】
【０００２】
移動通信システムにおいて、端末が、基地局を経由して通信を行うことにより発生する移動トラヒックは、人間の生活状況に依存して基地局毎での特徴を有している。このため、特定のエリアにおいては、多量のトラヒックが発生することで帯域が逼迫していても周辺のエリアではトラヒックが少なく帯域に余裕があるという状況が起こり得る。
【０００３】
基地局毎に発生した移動トラヒックを分割して処理するのでなく、それらの統計多重効果を得るために柔軟に移動ネットワークの機能を割り付けるための各種方式が次世代移動通信システムとして検討されている。例えば、アクセスネットワーク装置が提供する機能を部品化し、それらを柔軟な組合せで提供するアーキテクチャＦＡＳＡ（Flexible Access System Architecture）が提唱されている。
【０００４】
また、トラヒックの多重化領域を拡大する技術として、現在は固定帯域（ＣＰＲＩ規格）で構築されているＭＦＨ（Mobile Front Hall）を、パケット化により可変帯域とすることで、ＰＯＮシステムでの多重収容を行うことが検討されている（例えば非特許文献１）。
【０００５】
図１は、Ｃ−ＲＡＮ（Centralized/Cloud Radio Access Network）アーキテクチャによるＭＦＨの例を示す図である。図１に示すように、当該ＭＦＨでは、小さなカバーエリアを持つ基地局（ＲＲＨ１とＯＮＵ２を備える）を複数配置し、ＢＢＵ４でそれらを制御する。ＢＢＵ４は、光終端機能であるＯＬＴ３により光ファイバで基地局のＯＮＵ２と接続される。ＯＬＴ３とＢＢＵ４は、移動トラヒックを処理する移動トラヒック処理機能（ネットワーク機能と称してもよい）の例である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】小林孝行、王寛、久野大介、島田達也、寺田純、大高明浩、「モバイルフロントホールへの適用に向けたトラヒックの統計多重情報に基づくＴＤＭ−ＰＯＮの上り帯域割当手法」、信学総大２０１６．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した状況を踏まえ、移動ネットワークでのトラヒックの統計多重を効果的なものとするため、基地局でのトラヒックの時系列変化に基づき、基地局とそこで発生した移動トラヒックを処理する移動ネットワーク処理機能との対応を決定することが想定される。
【０００８】
すなわち、図２に示すように、例えば割当処理機能７が、移動トラヒック処理機能側５の機能部品６に移動トラヒックを割り当てる。なお、図２における機能部品６は、例えば、図１に示した光終端機能（ＰＯＮ利用を想定）、ＢＢＵ機能（Ｃ−ＲＡＮアーキテクチャを想定）等である。
【０００９】
サービス提供者にとっては、サービス提供に係るコストが小さいことが望ましいことから、上記の割り当てを行う際には、基地局からネットワーク（移動トラヒック処理機能）側への移動トラヒックの基地局毎の時系列変化に基づき、構築することが必要な機能部品が少なくなるように割り当てを行うことが必要である。なお、本明細書での「コスト」には、設備構築費、割当変更回数に関するペナルティ等が含まれる。
【００１０】
ここで、非特許文献１には、ＭＦＨへの帯域割当について、ＰＯＮによる基地局の収容を前提に、基地局からの移動トラヒックをパケット化して可変帯域による統計多重効果を実現する帯域割当技術が提案されている。この技術は、従来の固定帯域での割当を実際に発生する移動トラヒック量に応じた可変帯域にすることで、過剰な割当帯域を削減することを目指す技術であり、割当帯域を最大限に削減するような基地局の収容法を決定する技術ではない。
【００１１】
また、Ｃ−ＲＡＮにより分離された、ＢＢＵの機能をＮＦＶにより仮想化基盤上で提供し、ＢＢＵ機能を統合化・プール化することが検討されているが、当該技術はＢＢＵ機能を提供する機能部品の容量を出来るだけ少なくするように基地局の収容法を決定する技術ではない。
【００１２】
本発明は上記の点に鑑みてなされたものであり、基地局と、基地局から発生する移動トラヒックを処理する移動トラヒック処理機能とを備える移動通信システムにおいて、移動トラヒック処理機能に係るコストが小さくなるように、基地局に移動トラヒック処理機能を割り当てる技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
開示の技術によれば、複数の基地局と、当該複数の基地局から発生する移動トラヒックを処理する複数の移動トラヒック処理機能を備える移動通信システムにおいて、各基地局を１つの移動トラヒック処理機能に割り当てる割当装置であって、
移動トラヒック処理機能に関するコスト情報、及び、基地局毎の時系列の移動トラヒック情報を入力する入力手段と、
各移動トラヒック処理機能における割当可能な移動トラヒック量、及び割当可能な基地局数に関する制約条件の下で、構築される移動トラヒック処理機能に関するコストを最小にする最適化問題を解くことにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する計算手段と
を備えることを特徴とする割当装置が提供される。
【発明の効果】
【００１４】
開示の技術によれば、基地局と、基地局から発生する移動トラヒックを処理する移動トラヒック処理機能とを備える移動通信システムにおいて、移動トラヒック処理機能に係るコストが小さくなるように、基地局に移動トラヒック処理機能を割り当てる技術が提供される。
【図面の簡単な説明】
【００１５】
【図１】Ｃ−ＲＡＮアーキテクチャによるＭＦＨ（Ｍｏｂｉｌｅ  Ｆｒｏｎｔ  Ｈａｌｌ）の例を示す図である。
【図２】課題を説明するための図である。
【図３】本発明の実施の形態におけるシステム構成図である。
【図４】本発明の実施の形態における最適割当装置１００の構成例を示す図である。
【図５】本発明の実施の形態における最適割当装置１００のハードウェア構成例を示す図である。
【図６】実施例１の処理を説明するための図である。
【図７】実施例１の最適化モデルを示す図である。
【図８】実施例２の処理を説明するための図である。
【図９】実施例２の最適化モデルを示す図である。
【図１０】実施例３の処理を説明するための図である。
【図１１】実施例３の最適化モデルを示す図である。
【図１２】実施例４における処理のフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態（本実施の形態）を説明する。以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１７】
（システム構成）
図３に、本実施の形態におけるシステム構成図を示す。図３に示すように、本実施の形態におけるシステムは、最適割当装置１００、及び移動通信システム２００を有する。移動通信システム２００は、基地局２０１、転送機能２０２、光終端機能２０３を含む。図３には、基地局２０１、転送機能２０２が１つずつ示されているが、これは図示の便宜にためであり、実際にはそれぞれ複数備えられる。また、移動トラヒック処理機能として、光終端機能２０３を示しているが、これは例であり、移動トラヒック処理機能が、光終端機能２０３以外の機能であってもよい。
【００１８】
本実施の形態では、移動通信システム２００として、図１に示したような、ＰＯＮシステムを適用したＭＦＨを使用することを想定している。すなわち、図３の基地局２０１は、ＲＲＨとＯＬＴを含む装置であり、転送機能２０２は、ＭＦＨ区間（ＢＢＵ−ＲＲＨ）の機能であり、光終端装置は、ＯＮＵである。
【００１９】
ＭＦＨ区間（ＢＢＵ−ＲＲＨ）にＰＯＮシステムを適用することで、心線共用による設備共用効果により、効率的に基地局から発生する移動トラヒックを収容することができる。
【００２０】
また、本実施の形態では、従来、Ｃ−ＲＡＮアーキテクチャに基づきＢＢＵで実施してきたパケット化機能を基地局２０１に配備することで、ＰＯＮ区間による統計多重効果により移動トラヒックの収容率向上を図ることとしている。
【００２１】
図３に示す最適割当装置１００は、基地局毎の移動トラヒック情報（時系列）、ネットワーク構成情報、設備構築費を入力とし、基地局から発生した移動トラヒックを処理する局側（例：中央集約局側）での光終端機能の割り当てを決定する。割り当ての情報は、例えば、最適割当装置１００から転送機能２０２に送られる。転送機能２０２は、当該割り当てに従って、移動トラヒックの転送を行う。また、割り当ての情報は、運用者に送られ、運用者により設備構築が行われる。
【００２２】
最適割当装置１００は、移動通信システム外のネットワーク、例えばインターネットに接続される装置であってもよいし、移動通信システム内の装置であってもよいし、スタンドアロンの装置であってもよい。
【００２３】
図４は、最適割当装置１００の機能構成図である。図４に示すように、最適割当装置１００は、基地局毎の移動トラヒック情報（時系列）、ネットワーク構成情報、設備構築費を入力する入力部１０１と、最適化問題を解くことにより、基地局に対する光終端機能の割り当てを決定する最適化計算部１０２と、計算結果を出力する出力部１０３と、入力データ、計算に必要なデータ、計算過程データ、計算結果等を格納するデータ格納部１０４を有する。最適化計算部１０２における処理内容については、最適割当装置１００が実行する処理内容として後述する。
【００２４】
本実施の形態における最適割当装置１００は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。図５は、本実施の形態における最適割当装置１００のハードウェア構成例を示す図である。図５の最適割当装置１００は、それぞれバスＢで相互に接続されているドライブ装置３００、補助記憶装置３０２、メモリ装置３０３、ＣＰＵ３０４、インタフェース装置３０５、表示装置３０６、及び入力装置３０７等を有する。
【００２５】
最適割当装置１００での処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ又はメモリカード等の記録媒体３０１によって提供される。プログラムを記憶した記録媒体３０１がドライブ装置３００にセットされると、プログラムが記録媒体３０１からドライブ装置３００を介して補助記憶装置３０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体３０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置３０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２６】
メモリ装置３０３は、プログラムの起動指示があった場合に、補助記憶装置３０２からプログラムを読み出して格納する。ＣＰＵ３０４は、メモリ装置３０３に格納されたプログラムに従って最適割当装置１００に係る機能を実現する。インタフェース装置３０５は、ネットワークに接続するためのインタフェースとして用いられる。表示装置３０６はプログラムによるＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）等を表示する。入力装置３０７はキーボード及びマウス、ボタン、又はタッチパネル等で構成され、様々な操作指示を入力させるために用いられる。
【００２７】
（最適割当装置１００が実行する処理内容）
以下、最適割当装置１００が実行する処理内容の例として、実施例１〜実施例４を説明する。なお、以下の各実施例の説明において、最適化モデルでのインデックスとの紛らわしさを生じさせないために、「基地局２０１」、「光終端機能２０３」については参照符号２０１、２０３を使用していない。
【００２８】
（実施例１）
実施例１では、考慮対象の全時間帯にわたり基地局とそこから発生する移動トラヒックを処理する機能（移動トラヒック処理機能（本実施の形態では光終端機能））との対応が固定であることを前提とする。
【００２９】
最適割当装置１００は、基地局毎の移動トラヒックの時系列変化の情報に基づいて、必要とする移動トラヒック処理機能の容量を少なくするように、基地局に対する移動トラヒック処理機能の割り当てを（準）最適化処理により決定する。ここで、「基地局」対「移動トラヒック処理機能」は、Ｎ対１（Ｎは１以上の整数）である。つまり、各基地局に対し、１つの移動トラヒック処理機能が割り当てられる。
【００３０】
実施例１では、（準）最適化処理は、（準）最適化プログラムにより、最適化計算部１０２において実行される。この点は、実施例２〜４でも同様である。なお、"（準）"と記載しているのは、後述する実施例４のように、厳密な最適解を導くことが保証されている方法ではなく、発見的手法で代表されるような良い解（厳密な最適解とは限らない）を導く手法であることを意図している。
【００３１】
実施例１における処理を図６を参照して説明する。まず、入力部１０１により、最適割当装置１００に、ネットワーク構成情報（設備容量、設備構成の制約情報等）、設備構築費ｃｊ、及び基地局毎の移動トラヒック情報（時系列）ｄｉｔが入力される。図６には、例として、基地局＃０００１〜＃０００３に関する移動トラヒック情報（時系列）が示されている。
【００３２】
次に、最適化計算部１０２は、入力された情報を用いて、制約を考慮し、設備構築費が（準）最小となるような割り当てを計算する。実施例１では、当該割り当ては、考慮する全時間に固定的に適用されるものである。考慮する全時間とは、例えば、２４時間、１週間、１ヶ月等の、予め定めた時間長である。
【００３３】
最適化計算部１０２による割り当ての計算結果は、データ格納部１０４に格納され、出力部１０３により出力される。図６の例では、基地局＃０００１から発生する移動トラヒックと基地局＃０００３から発生する移動トラヒックが移動トラヒック処理機能＃Ａに割り当てられ、基地局＃０００２から発生する移動トラヒックが移動トラヒック処理機能＃Ｂに割り当てられ、基地局＃０００４から発生する移動トラヒックが移動トラヒック処理機能＃Ｃに割り当てられている。
【００３４】
以下、最適化計算部１０２による処理内容をより具体的に説明する。実施例１における最適化計算部１０２は、最適化問題を解くことにより、基地局に対する移動トラヒック処理機能の割り当てを計算する。その最適化モデル（問題定義）は以下のとおりである。
【００３５】
＜表記＞
最適化モデルで使用される表記は以下のとおりである。
【００３６】
・ｉ：基地局のＩｎｄｅｘ
・ｊ：基地局からの移動トラヒックに対する局側の光終端機能に対するＩｎｄｅｘ
・ｔ：時間のＩｎｄｅｘ
・Ｉ：基地局の集合
・Ｊ：（局側の）光終端機能の集合
・Ｔ：時間の数、ｔ∈［１，Ｔ］
＜パラメータ＞
最適化モデルで使用されるパラメータは以下のとおりである。
【００３７】
・ｃｊ：光終端機能ｊの設備構築費
・Ｕｊ：光終端機能ｊに割当可能な移動トラヒックの容量
・Ｍｊ：光終端機能ｊに割当可能な基地局の最大数
・ｄｉｔ：時間ｔにて基地局ｉから発生するトラヒック量
＜変数＞
最適化モデルで使用される変数は以下のとおりである。
【００３８】
・ｙｊ：光終端機能ｊの設備構築を規定するバイナリ変数（設備を構築する場合は１、そうでない場合は０）
・ｘｉ，ｊ：基地局ｉの光終端機能ｊへの割り当てを規定するバイナリ変数（割当てる場合は１。そうでない場合は０）
＜最適化モデル＞
実施例１の最適化モデルを図７に示す。
【００３９】
図７に示すように、最適化計算部１０２は、式（２）、式（３）で示す制約条件の下、式（１）に示すΣｊ∈Ｊｃｊ・ｙｊを最小化する基地局ｉの光終端機能ｊへの割り当てを計算する。具体的には、各ｉ、各ｊにおけるｘｉ，ｊが割り当ての計算結果として得られる。
【００４０】
式（１）は、構築する光終端機能全体の設備構築費を最小にすることを示している。式（２）は、考慮する全時間Ｔの中の各時間ｔ、及び、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局のトラヒック量の合計が、当該光終端機能ｊに割当可能な移動トラヒックの容量以下であるという制約条件を示す。式（３）は、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局の数が、当該光終端機能ｊに割当可能な基地局の最大数以下であるという制約条件を示す。
【００４１】
（実施例２）
実施例２では、基地局と移動トラヒック機能の対応が可変であることを前提とする。ただし、移動トラヒック機能は、考慮する時間で増減設されることなく、考慮する全時間において、その設備容量は一定である。つまり、例えば、考慮する全期間を１日とし、基地局と移動トラヒック機能の対応を変え得る単位時間を１時間とすると、１日の中で、基地局と移動トラヒック機能の対応関係は１時間単位で変化し得るが、移動トラヒック機能の設備は１日にわたって固定である。
【００４２】
最適割当装置１００は、基地局毎の移動トラヒックの時系列変化の情報に基づいて、必要とする移動トラヒック処理機能の容量を少なくするように、基地局に対する移動トラヒック処理機能の割り当て（「基地局」対「移動トラヒック処理機能」は、Ｎ対１（Ｎは１以上の整数））を（準）最適化処理により決定する。
【００４３】
実施例２における処理を図８を参照して説明する。まず、実施例１と同様にして、入力部１０１により、最適割当装置１００に、ネットワーク構成情報（設備容量、設備構成の制約情報等）、設備構築費ｃｊ、及び基地局毎の移動トラヒック情報（時系列）ｄｉｔが入力される。
【００４４】
次に、最適化計算部１０２は、入力された情報を用いて、制約を考慮し、設備構築費が（準）最小となるような割り当てを計算する。実施例２では、当該割り当ては、時間により変更されるものである。
【００４５】
最適化計算部１０２による割り当ての計算結果は、データ格納部１０４に格納され、出力部１０３により出力される。図８の例では、時間１、時間２、...時間ｔ、...のそれぞれの時間の割当結果が出力されている。例として、時間ｔにおいて、基地局＃０００１から発生する移動トラヒックと基地局＃０００３から発生する移動トラヒックが移動トラヒック処理機能＃Ａに割り当てられ、基地局＃０００２から発生する移動トラヒックと基地局＃０００４から発生する移動トラヒックが移動トラヒック処理機能＃Ｂに割り当てられている。
【００４６】
以下、最適化計算部１０２による処理内容をより具体的に説明する。実施例１と同様、実施例２における最適化計算部１０２は、最適化問題を解くことにより基地局に対する移動トラヒック処理機能の割り当てを計算する。その最適化モデル（問題定義）は以下のとおりである。
【００４７】
＜表記＞
最適化モデルで使用される表記は以下のとおりである。
【００４８】
・ｉ：基地局のＩｎｄｅｘ
・ｊ：基地局からの移動トラヒックに対する局側の光終端機能に対するＩｎｄｅｘ
・ｔ：時間のＩｎｄｅｘ
・Ｉ：基地局の集合
・Ｊ：（局側の）光終端機能の集合
・Ｔ：時間の数、ｔ∈［１，Ｔ］
＜パラメータ＞
最適化モデルで使用されるパラメータは以下のとおりである。
【００４９】
・ｃｊ：光終端機能ｊの設備構築費
・Ｕｊ：光終端機能ｊに割当可能な移動トラヒックの容量
・Ｍｊ：光終端機能ｊに割当可能な基地局の最大数
・ｄｉｔ：時間ｔにて基地局ｉから発生するトラヒック量
＜変数＞
最適化モデルで使用される変数は以下のとおりである。
【００５０】
・ｙｊ：光終端機能ｊの設備構築を規定するバイナリ変数（設備を構築する場合は１、そうでない場合は０）
・ｘｉ，ｊ，ｔ：基地局ｉの光終端機能ｊへの割り当てを規定するバイナリ変数（割当てる場合は１。そうでない場合は０）
＜最適化モデル＞
実施例２の最適化モデルを図９に示す。
【００５１】
図９に示すように、最適化計算部１０２は、式（５）、式（６）で示す制約条件の下、式（４）に示すΣｊ∈Ｊｃｊ・ｙｊを最小化する基地局ｉの光終端機能ｊへの割り当てを計算する。具体的には、各ｉ、各ｊ、各ｔにおけるｘｉ，ｊ，ｔが割り当ての計算結果として得られる。
【００５２】
式（４）は、構築する光終端機能全体の設備構築費を最小にすることを示している。式（５）は、考慮する全時間Ｔの中の各時間ｔ、及び、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局のトラヒック量の合計が、当該光終端機能ｊに割当可能な移動トラヒックの容量以下であるという制約条件を示す。式（６）は、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局の数が、当該光終端機能ｊに割当可能な基地局の最大数以下であるという制約条件を示す。
【００５３】
（実施例３）
実施例３では、実施例２と同じく基地局と移動トラヒック機能の対応が可変であるが、対応関係の変更回数を最小限にすべく、基地局毎の変更、あるいは全基地局についての変更に対するペナルティを最適化の目的に加えて、基地局と移動トラヒック機能の対応を計算する。なお、実施例２と同様に、移動トラヒック機能の設備構築については、考慮する全時間において固定である。
【００５４】
実施例３における処理を図１０を参照して説明する。まず、入力部１０１により、最適割当装置１００に、ネットワーク構成情報（設備容量、設備構成の制約情報等）、設備構築費ｃｊ、基地局毎の移動トラヒック情報（時系列）ｄｉｔ、及び、基地局の割当変更に関するペナルティの情報が入力される。、基地局の割当変更に関するペナルティの情報とは、例えば、後述するペナルティ関数である。図１０の例では、ペナルティの情報として（ａ）と（ｂ）の２種類が示されている。（ａ）に示す場合では、基地局毎の割当変更回数に関するペナルティを使用し、（ｂ）に示す場合には、全体の割当変更回数に関するペナルティを使用する。
【００５５】
次に、最適化計算部１０２は、入力された情報を用いて、制約を考慮し、設備構築費及びペナルティの合計が（準）最小となるような割り当てを計算する。実施例３でも、当該割り当ては、時間により変更されるものである。
【００５６】
最適化計算部１０２による割り当ての計算結果は、データ格納部１０４に格納され、出力部１０３により、出力される。図１０の例では、時間１、時間２、...時間ｔ、...のそれぞれの時間の割当結果が出力されている。例として、時間ｔにおいて、基地局＃０００１から発生する移動トラヒックと基地局＃０００３から発生する移動トラヒックが移動トラヒック処理機能＃Ａに割り当てられ、基地局＃０００２から発生する移動トラヒックと基地局＃０００４から発生する移動トラヒックが移動トラヒック処理機能＃Ｂに割り当てられている。
【００５７】
以下、最適化計算部１０２による処理内容をより具体的に説明する。実施例１、２と同様、実施例３における最適化計算部１０２は、最適化問題を解くことにより基地局に対する移動トラヒック処理機能の割り当てを計算する。その最適化モデル（問題定義）は以下のとおりである。なお、ここでは、一例として、ペナルティを、全体の基地局‐移動トラヒック処理機能の割当変更回数に対して適用するケースについて説明している。
【００５８】
＜表記＞
最適化モデルで使用される表記は以下のとおりである。
【００５９】
・ｉ：基地局のＩｎｄｅｘ
・ｊ：基地局からの移動トラヒックに対する局側の光終端機能に対するＩｎｄｅｘ
・ｔ：時間のＩｎｄｅｘ
・Ｉ：基地局の集合
・Ｊ：（局側の）光終端機能の集合
・Ｔ：時間の数、ｔ∈［１，Ｔ］
＜パラメータ＞
最適化モデルで使用されるパラメータは以下のとおりである。
【００６０】
・ｃｊ：光終端機能ｊの設備構築費
・Ｕｊ：光終端機能ｊに割当可能な移動トラヒックの容量
・Ｍｊ：光終端機能ｊに割当可能な基地局の最大数
・ｄｉｔ：時間ｔにて基地局ｉから発生するトラヒック量
＜変数＞
最適化モデルで使用される変数は以下のとおりである。
【００６１】
・ｙｊ：光終端機能ｊの設備構築を規定するバイナリ変数（設備を構築する場合は１、そうでない場合は０）
・ｘｉ，ｊ，ｔ：基地局ｉの光終端機能ｊへの割り当てを規定するバイナリ変数（割当てる場合は１。そうでない場合は０）
・ｚ：光終端機能の割当変更回数の全基地局合計
＜ペナルティ関数＞
最適化モデルで使用されるペナルティ関数は以下のとおりである。
【００６２】
・λ（ｚ）：全体での割当変更回数に伴い課するペナルティ
＜最適化モデル＞
実施例３の最適化モデルを図１１に示す。
【００６３】
図１１に示すように、最適化計算部１０２は、式（８）、式（９）、式（１０）で示す制約条件の下、式（７）に示すΣｊ∈Ｊｃｊ・ｙｊ＋λ（ｚ）を最小化する基地局ｉの光終端機能ｊへの割り当てを計算する。具体的には、各ｉ、各ｊ、各ｔにおけるｘｉ，ｊ，ｔが割り当ての計算結果として得られる。
【００６４】
式（７）は、構築する光終端機能全体の設備構築費とペナルティとの和を最小にすることを示している。式（８）は、考慮する全時間Ｔの中の各時間ｔ、及び、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局のトラヒック量の合計が、当該光終端機能ｊに割当可能な移動トラヒックの容量以下であるという制約条件を示す。式（９）は、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局の数が、当該光終端機能ｊに割当可能な基地局の最大数以下であるという制約条件を示す。式（１０）は、考慮する全時間Ｔにおける全体での割当変更回数を示す。
【００６５】
なお、上記の例では、ペナルティをコストの一部として目的関数に使用しているが、ペナルティを、ある値以下に抑えるという制約条件として使用してもよい。
【００６６】
（実施例４）
実施例４では、上記実施例１〜３の割当において、最適化計算部１０２での（準）最適化処理による計算時間の削減のため、ランダムに実施する割り当てを上界、基地局の移動トラヒックを分割して複数の移動トラヒック処理機能への割当を許容することで得られる下界の情報を利用して、下界での実行可能解が得られたときには、それを解に、得られないときには上界と下界の中点にて実行可能解が得られるか否かを評価し、得られるときにはその中点を新たな上界に、得られないときにはその中点を新たな下界として、解の範囲を狭めていき、最終的に許容される（準）最適解を導く。
【００６７】
図１２のフローチャートを参照して、実施例４における最適化計算部１０２の処理手順を説明する。以下の処理において、ＵＢは処理の実施時点で得られている上界値を示し、ＬＢは処理の実施時点で得られている下界値を示す。
【００６８】
ステップＳ１０１において、設備構成上の制約条件を満たしながら、ランダムに基地局を移動トラヒック処理機能に割当てることで得られた解の設備構築費ＵＢ＿０を初期の上界値として設定する（ＵＢ：＝ＵＢ＿０）。例えば、実施例１に準じる手法を用いる場合、ステップＳ１０１では、各時間ｔ、及び、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局のトラヒック量の合計が、当該光終端機能ｊに割当可能な移動トラヒックの容量以下であるという制約条件と、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局の数が、当該光終端機能ｊに割当可能な基地局の最大数以下であるという制約条件とを満たす割り当てをランダムに生成し、当該割り当ての設備構築費をＵＢ＿０とする。ここでは、実施例１に準じる手法を用いる場合を示したが、実施例２〜３に準じる手法を使用してもよい。
【００６９】
ステップＳ１０２において、基地局の移動トラヒックを分割して複数の移動トラヒック処理機能への割当を許容することを前提として、制約条件を満足しつつ最適な割当解を算出し、得られた解の設備構築費ＬＢ＿０を初期の下界値として設定する（ＬＢ：＝ＬＢ＿０）。例えば、実施例１に準じる手法を用いる場合、ステップＳ１０２では、単一の基地局から発生する移動トラヒックを分割して複数の移動トラヒック処理機能への割当を許容することを前提として、各時間ｔ、及び、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局のトラヒック量の合計が、当該光終端機能ｊに割当可能な移動トラヒックの容量以下であるという制約条件と、各光終端機能ｊにおいて、光終端機能ｊに割り当てられた全基地局の数が、当該光終端機能ｊに割当可能な基地局の最大数以下であるという制約条件とを満たす割り当ての中で設備構築費が最小となる割り当てを最小化アルゴリズムで特定し、当該割り当ての当該設備構築費をＬＢ＿０とする。ここでは、実施例１に準じる手法を用いる場合を示したが、実施例２〜３に準じる手法を使用してもよい。
【００７０】
ステップＳ１０３において、得られている下界値（ＬＢ）を実現する解が実行可能解であるか否かを制約充足問題としてチェックする。実行可能解は、基地局の移動トラヒックを分割しないで移動トラヒック処理機能への割当が行われる解である。また、ＬＢを実現する実行可能解とは、設備構築費がＬＢ以下になる実行可能解である。同様に、ＵＢを実現する実行可能解とは、設備構築費がＵＢ以下になる実行可能解である。このような実行可能解は、例えば、上述した割当可能な移動トラヒックの容量の制約条件と、割当可能な基地局の最大数の制約条件と、設備構築費（ＬＢ又はＵＢ又はＶ）の制約条件を満たす制約充足問題の解として求めることができる。
【００７１】
実行可能解が存在する場合（Ｓ１０４のＹｅｓ）にはステップＳ１０５に進み、ＬＢを実現する実行可能解を最適解とし、処理を終了する。実行可能解が存在しない場合（Ｓ１０４のＮｏ）にはステップＳ１０６に進む。
【００７２】
ステップＳ１０６において、「ＵＢ−ＬＢ＜目標値」（目標値は予め設定しておく値）を満たすかどうかをチェックし、満たす場合（Ｓ１０６のＹｅｓ）にはステップＳ１０７に進み、ＵＢを実現する実行可能解を準最適解とし、処理を終了する。
【００７３】
「ＵＢ−ＬＢ＜目標値」を満たさない場合（Ｓ１０６のＮｏ）にはステップＳ１０８に進む。
【００７４】
ステップＳ１０８において、Ｖを（ＵＢ＋ＬＢ）／２とし、Ｖを実現する解が実行可能解であるか否かを制約充足問題としてチェックする。実行可能解が存在する場合（Ｓ１０９のＹｅｓ）にはステップＳ１１１に進み、ＵＢをＶとしてステップＳ１０８に進む。実行可能解が存在しない場合（Ｓ１０９のＮｏ）にはステップＳ１１０に進み、ＬＢをＶとしてステップＳ１０３に進む。
【００７５】
（各実施例の効果について）
実施例１、２によれば、移動トラヒック処理機能の容量が少なくなるような、基地局に対する移動トラヒック処理機能の割り当てを実施することができる。
【００７６】
実施例３によれば、基地局と移動トラヒック処理機能の割当関係の変更を、その設備構築費削減への効果を踏まえて、最小限にすることができる。
【００７７】
実施例４によれば、上記の実施例１〜３により望ましい割り当てを実施する（準）最適化プログラムは、計算負荷が大きく、問題の規模が大きくなるにつれ、計算に莫大な時間を要する場合がある。実施例４では、実施例１〜３の手法にて、最適化アルゴリズムを直接適用するのでなく、容易に計算可能な制約充足問題のアルゴリズムを適用することで、短時間で望ましい割り当てを決定することができる。
【００７８】
（実施の形態のまとめ）
本実施の形態によれば、複数の基地局と、当該複数の基地局から発生する移動トラヒックを処理する複数の移動トラヒック処理機能を備える移動通信システムにおいて、各基地局を１つの移動トラヒック処理機能に割り当てる割当装置であって、移動トラヒック処理機能に関するコスト情報、及び、基地局毎の時系列の移動トラヒック情報を入力する入力手段と、各移動トラヒック処理機能における割当可能な移動トラヒック量、及び割当可能な基地局数に関する制約条件の下で、構築される移動トラヒック処理機能に関するコストを最小にする最適化問題を解くことにより、各基地局に対する移動トラヒック処理機能の割り当てを算出する計算手段とを備えることを特徴とする割当装置が提供される。
【００７９】
最適割当装置１００、入力部１０１、最適化計算部１０２はそれぞれ、割当装置、入力手段、計算手段の例である。また、設備構築費、割当変更回数に係るペナルティはいずれもコストの例である。
【００８０】
前記計算手段は、各基地局に対する移動トラヒック処理機能の割り当てが所定の時間長の中で可変であるという条件の下で前記最適化問題を解くことにより、当該所定の時間長の中の単位時間毎に基地局に対する移動トラヒック処理機能の割り当てを算出することとしてもよい。
【００８１】
前記計算手段は、前記最適化問題において、移動トラヒック処理機能の割り当ての変更回数に関するペナルティを更に使用することで、各基地局に対する移動トラヒック処理機能の割り当てを算出することとしてもよい。
【００８２】
前記計算手段は、ランダムに基地局を移動トラヒック処理機能に割り当てることで得られた解によるコストを上界値の初期値とし、基地局の移動トラヒックを分割して複数の移動トラヒック処理機能への割当を許容することを前提として計算される最適化問題の解によるコストを下界値の初期値としながら、当該初期値から始め、制約充足問題を解くことで下界値を実現する実行可能解が存在するかを調べ、存在する場合は下界値を実現する割り当てを算出し、存在しない場合は、その時点での上界値と下界値の間の値の実行可能解の存在を制約充足問題を解くことで確認し、上界値と下界値の間隔を狭めていくこととしてもよい。
【００８３】
以上、本実施の形態について説明したが、本発明はかかる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００８４】
１００  最適割当装置
１０１  入力部
１０２  最適化計算部
１０３  出力部
１０４  データ格納部
２００  移動通信システム
２０１  基地局
２０２  転送機能
２０３  光終端機能
３００  ドライブ装置
３０１  記録媒体
３０２  補助記憶装置
３０３  メモリ装置
３０４  ＣＰＵ
３０５  インタフェース装置
３０６  表示装置
３０７  出力装置
【図１】
2018207364.tif 000003
【図２】
2018207364.tif 000004
【図３】
2018207364.tif 000005
【図４】
2018207364.tif 000006
【図５】
2018207364.tif 000007
【図６】
2018207364.tif 000008
【図７】
2018207364.tif 000009
【図８】
2018207364.tif 000010
【図９】
2018207364.tif 000011
【図１０】
2018207364.tif 000012
【図１１】
2018207364.tif 000013
【図１２】
2018207364.tif 000014