(57)【特許請求の範囲】
【請求項１】
リング網の各ノードに複数の無線基地局がX台所属しており、端末が該リング網に接続されたインターネット接続サーバにアクセスする通信サービスにおいて、無線基地局を経由したトラヒックが、該リング網上のノードを経由して、ゲートウェイノードを通過して該インターネット接続サーバにアクセスする状況において、トラヒックを他の設備に分散させるリング網分割最適化装置であって、
前記リング網上のノード間のリンクを流れるトラヒック情報及び前記無線基地局がどのノードに接続されているかを示す基地局情報を取得して、記憶手段に格納するデータ収集手段と、
前記記憶手段の前記トラヒック情報及び前記基地局情報を用いて、前記ゲートウェイノードの１単位の設備では容量が不足し、２単位に増設するために、無線基地局集合M、時間区間の集合T、及び該無線基地局集合Mに含まれるある無線基地局発のトラヒックで前記ゲートウェイノードを時間区間t∈Tに疎通するトラヒックd(i,t)を求め、無線基地局の集合M1，M2を求める集合分割問題を、２つの設備へのトラヒック負荷がほぼ均等にするという条件を満たす局所最適化アルゴリズムを解くことにより、前記無線基地局からのトラヒックを振り分けるトラヒック振り分け手段と、
を有することを特徴とするリング網分割最適化装置。
【請求項２】
前記トラヒック振り分け手段は、
前記条件の下、前記リング網のノード内の基地局集合Mに閉じた形で前記局所最適化アルゴリズムを解く手段を含む
請求項１記載のリング網分割最適化装置。
【請求項３】
前記トラヒック振り分け手段は、
前記局所最適化アルゴリズムとして、
前記無線基地局の集合M1の元と前記無線基地局の集合M2の元を一つずつ置換する局所最適化に基づく近似算法を用いる
請求項１または２記載のリング網分割最適化装置。
【請求項４】
リング網の各ノードに複数の無線基地局がX台所属しており、端末が該リング網に接続されたインターネット接続サーバにアクセスする通信サービスにおいて、無線基地局を経由したトラヒックが、該リング網上のノードを経由して、ゲートウェイノードを通過して該インターネット接続サーバにアクセスする状況において、トラヒックを他の設備に分散させるリング網分割最適化装置におけるリング網分割最適化方法であって、
前記リング網上のノード間のリンクを流れるトラヒック情報及び前記無線基地局がどのノードに接続されているかを示す基地局情報を取得して、記憶手段に格納するデータ収集ステップと、
前記記憶手段の前記トラヒック情報及び前記基地局情報を用いて、前記ゲートウェイノードの１単位の設備では容量が不足し、２単位に増設するために、無線基地局集合M、時間区間の集合T、及び該無線基地局集合Mに含まれるある無線基地局発のトラヒックで前記ゲートウェイノードを時間区間t∈Tに疎通するトラヒックd(i,t)を求め、無線基地局の集合M1，M2を求める集合分割問題を、２つの設備へのトラヒック負荷がほぼ均等にするという条件を満たす局所最適化アルゴリズムを解くことにより、前記無線基地局からのトラヒックを振り分けるトラヒック振り分けステップと、
を行うことを特徴とするリング網分割最適化方法。
【請求項５】
前記トラヒック振り分けステップにおいて、
前記条件の下、前記リング網のノード内の基地局集合Mに閉じた形で前記局所最適化アルゴリズムを解く
請求項４記載のリング網分割最適化方法。
【請求項６】
前記トラヒック振り分けステップにおいて、
前記局所最適化アルゴリズムとして、
前記無線基地局の集合M1の元と前記無線基地局の集合M2の元を一つずつ置換する局所最適化に基づく近似算法を用いる
請求項４または５記載のリング網分割最適化方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載のリング網分割最適化装置の各手段として機能させるためのリング網分割最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リング網分割最適化装置及び方法及びプログラムに係り、特に、移動体通信を対象とする設備を有効利用するために、トラヒックを対象としたクラスタの最適な設計を行うためのリング網分割最適化装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
リング網内の容量が不足して２単位となった設備（L2(レイヤ２)スイッチ、回線など）への無線基地局の割り振りは、両グループのそれぞれのトラヒック量の合計が、可能な限り等しくなることが理想的となるが、全ての解をしらみつぶしに探索する解法を用いるときには、非常に時間がかかるため、現実的には最適解を求めることが困難であることが知られている。
【０００３】
現実的に許容できる時間内に出来るだけ良い解を見つけるために、全ての解をしらみつぶしに探索することではなく、探索可能な解の中から出来るだけ良い解を見つける、発見的アルゴリズムは、局所最適化技術（例えば、非特許文献１参照）と呼ばれて、広く研究がなされている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】久保幹雄，田村明久，松井知己，"応用数理計画ハンドブック"pp594-595, 2002.
【非特許文献２】久保幹雄，田村明久，松井知己，"応用数理計画ハンドブック"p91, 2002Recognizing and using goals in event management (2009. D. Smith., et al(MIT))
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の局所最適化技術は、携帯電話からのアクセストラヒックを集約した無線基地局と、無線基地局からのトラヒックの収容先となるリング内の設備を振り分けることに局所最適化技術を応用した具体的なアルゴリズムの検討はまだなされていない。
【０００６】
そのため、リング網内の無線基地局からのトラヒック振り分けの最適化は、局所最適化技術による検索の高速化が実現されないと計算量が膨大となり、現実的な時間内における計算は困難である。
【０００７】
本発明は、上記の点に鑑みなされたもので、リング網内の無線基地局からのトラヒックの振り分けを均等に分散させ、現実のリング網設計を最適化できるリング網分割最適化装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
一態様によれば、リング網の各ノードに複数の無線基地局がX台所属しており、端末が該リング網に接続されたインターネット接続サーバにアクセスする通信サービスにおいて、無線基地局を経由したトラヒックが、該リング網上のノードを経由して、ゲートウェイノードを通過して該インターネット接続サーバにアクセスする状況において、トラヒックを他の設備に分岐させるリング網分割最適化装置であって、
前記リング網上のノード間のリンクを流れるトラヒック情報及び前記無線基地局がどのノードに接続されているかを示す基地局情報を取得して、記憶手段に格納するデータ収集手段と、
前記記憶手段の前記トラヒック情報及び前記基地局情報を用いて、前記ゲートウェイノードの１単位の設備では容量が不足し、２単位に増設するために、無線基地局の集合M、時間区間の集合T、及び該無線基地局集合Mに含まれるある無線基地局発のトラヒックで前記ゲートウェイノードを時間区間t∈Tに疎通するトラヒックd(i,t)を求め、無線基地局の集合M1,M2を求める集合分割問題を、２つの設備へのトラヒック負荷がほぼ均等にするという条件を満たす局所最適化アルゴリズムを解くことにより、前記無線基地局からのトラヒックを振り分けるトラヒック振り分け手段と、を有するリング網分割最適化装置が提供される。
【発明の効果】
【０００９】
一態様によれば、リング網内の基地局からのトラヒックの振り分けの最適化は、従来は局所最適化技術による検索の高速化がないと計算量が膨大となり現実的な時間内における計算は困難となっていたが、局所最適化技術の適用により高速な検索が可能になることにより、現実的な時間内での最適化が可能になる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施の形態におけるシステム構成例である。
【図２】本発明の一実施の形態におけるオペレーションシステム及びリング網分割最適化装置の構成例である。
【図３】本発明の一実施の形態におけるリング網の一例である。
【発明を実施するための形態】
【００１１】
以下、図面と共に本発明の実施の形態を説明する。
【００１２】
本発明は、移動体通信を対象とする設備の有効利用に関するものである。網構成は、リング網の各ノードに複数の無線基地局がX台所属しているものとする。リング網は多段になっていても良い。携帯電話がリング網に接続されたインターネット接続サーバにアクセスする通信サービスを提供する際には、無線基地局を経由したトラヒックは、さらに，リング網上のノードを経由して、ゲートウェイノードを通過してインターネット接続サーバにアクセスする。この状況において、無線基地局を経由してリングに多重されるトラヒックが次第に増加し、ゲートウェイノード内の１単位の設備では容量が不足する見通しになり、設備を２単位に増設する場合を考える。不足する設備は、Ｌ２スイッチであっても、回線であってもよい。このとき、X台の無線基地局と2単位の設備の間の関係が固定的であるとき、X台の無線基地局を２つのグループに分類することが必要になる。しかも、今後の無線基地局の収容数増加や、無線基地局それぞれが経由するトラヒック量の増加によって、再び設備の容量不足が懸念される条件では、無線基地局のトラヒック量を、２つのグループ間で均等化にする、つまり、トラヒック量を２つのグループ間で可能な限り等しくなるようなグルーピングを行うことが最も経済的となる。無線基地局のトラヒック量が時間によって変動し、それぞれ無線基地局毎にトラヒック量のピーク時間の異なる条件では、時間変動を伴うトラヒック量をもつ無線基地局を、２つのグループに属するトラヒック量の合計が、可能な限り等しくなるように、２つのグループに振り分ける。
【００１３】
図１は、本発明の一実施の形態におけるシステム構成例である。
【００１４】
同図に示すシステムは、複数のノード（ノード１０Ａ，１０Ｂ，１０Ｃ）、ゲートウェイ装置であるノード１０Ｃに接続されるインターネット接続サーバ２０、各ノード１０間の通信リンク３０１，３０２，３０３を有する通信網（リング網）１と、ノード１０Ａ、ノード１０Ｂに接続される複数の無線基地局２、各無線基地局２に接続される複数の携帯電話３、各ノード１０Ａ，１０Ｂ，１０Ｃと接続されるオぺレーションシステム２００、リング網分割最適化装置１００、帯域表示装置３００から構成される。
【００１５】
リング網分割最適化装置１００は、通信網１上のノード１０、通信網１を管理運用するオペレーションシステム２００に接続し、必要なデータの取得と取得したデータを用いたトラヒックの振り分けを実施する。リング網分割最適化装置１００は通信網１の運用者、または設計者が直接操作する帯域表示装置３００からの要求を受け、算出したトラヒック振り分けに関する情報を帯域表示装置３００に送信する。
【００１６】
図２は、本発明の一実施の形態におけるオペレーションシステム及びリング網分割最適化装置の構成例である。
【００１７】
同図に示すオペレーションシステム２００は、ネットワークデータ収集部２１０とネットワーク情報データベース２２０を有する。ネットワークデータ収集部２１０は、当該オペレーションシステム２００が管理する通信網１上のノード１０に接続する通信リンク３０上を流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース２２０に蓄積する。また、無線基地局２がどの通信網のノードに接続されているかは基地局情報としてネットワーク情報データベース２２０に蓄積する。
【００１８】
リング網分割最適化装置１００は、データ取得部１１０、トラヒック振り分け部１２０、基地局情報データベース１３０、トラヒック情報データベース１４０を有する。
【００１９】
データ取得部１１０は、オペレーションシステム２００がネットワーク情報データベース２２０で管理する情報のうち、トラヒック振り分けに必要な情報として、トラヒック情報及び基地局情報を取得し、それぞれ、トラヒック情報データベース１４０、基地局情報データベース１３０に蓄積する。
【００２０】
トラヒック振り分け部１２０は、トラヒック情報データベース１４０、基地局情報データベース１３０に蓄積されたトラヒック情報と基地局情報を用いて、次に示すような計算を実施することでトラヒック振り分けを計算する。
【００２１】
以下では、リング網１の各ノード１０に複数の無線基地局２が所属し、無線基地局２には、携帯電話３からのアクセストラヒックがあるものとする。携帯電話３から無線基地局２に到達したトラヒックは上位ノードを経由してリング網１のゲートウェイノード１０Ｃを通過しインターネット接続サーバ２０にアクセスするものとする。この前提の下、携帯電話３からのトラヒックが時を経て増加し、ゲートウェイノード１０Ｃ内の１単位の設備では容量が不足し、２単位に増設することを考える。そのため無線基地局２からのトラヒックの収容先をどちらの設備にするかが問題となる。無線基地局２からのトラヒックはピーク時が異なっている場合があり、うまく設備への収容先を決めないと設備への負荷の分散が不均衡になってしまう。このとき、２つの設備へのトラヒックの負荷がほぼ均等になるように局所最適化の手順に従って無線基地局（以下、単に「基地局」と記す）２からのトラヒックを振り分ける。
【００２２】
リング網１配下の基地局２の集合をM、24時間をいくつかの区間に分けてその区間の集合をTとする。基地局i∈M発のトラヒックでゲートウェイを時間区間t∈Tに疎通するトラヒックをd(i,t)と置く。
【００２３】
基地局集合の分割問題は次の条件を満たす集合M1,M2を求める集合分割問題として定式化できる。
【００２４】
＜集合分割問題１＞
【００２５】
【数１】
0006035264.tif 000002
これによって、リング網１配下の基地局２を２つに分割してほぼ均等にゲートウェイ内の２つのL2スイッチにトラヒックを振り分けることができる。M1の個数k1とM2の個数k2は最初に固定しておく。
【００２６】
この問題は、変数x(i)∈{0,1}を、次のように定義することで、0−1整数計画問題に変換することができる。基地局iを集合M1(L2スイッチ1にトラヒックを収容)に含める場合にはx(i)=1と置き、基地局iを集合M2(L2スイッチ2にトラヒックを収容)に含める場合にはx(i)=0と置く。このとき、元の問題は次のように変換される。
【００２７】
【数２】
0006035264.tif 000003
(6)式は次式に直すことができる。
【００２８】
【数３】
0006035264.tif 000004
上記の問題(5),(7),(8),(9)は、0−1整数計画問題（非特許文献２参照）と呼ばれ、計算量はNP困難（非特許文献２参照）と呼ばれるクラスに属する。このクラスの問題は、規模が大きくなったとき、計算時間が膨大になるのでM1の元とM2の元をひとつずつ置換するという局所最適化に基づく近似算法を提案する。
【００２９】
＜局所最適化アルゴリズム1＞
１）上記の式(2),(3),(4)を満たす基地局集合M1,M2を初期解として選ぶ。候補集合O=M1とする。
【００３０】
２）基地局
【００３１】
【数４】
0006035264.tif 000005
と任意の
【００３２】
【数５】
0006035264.tif 000006
を、Dの値を評価するために一旦メモリに置換したものとして格納して
【００３３】
【数６】
0006035264.tif 000007
の値が小さくなるかどうか調べる。小さくならない場合はメモリ上における置換は行わない。小さくなる場合にはi1をすべてのi2と置換したときのメモリ上に一旦格納されたDの値と比較して、最もDの値が小さくなる
【００３４】
【数７】
0006035264.tif 000008
と置換した結果をメモリに書き込む。
【００３５】
M1←M1-{i1}+{i2'}, M2←M2-{i2'}+{i1}
最後に処理の終わった基地局i1を候補集合Oから除く。
【００３６】
O←O-{i1}
３）O=φとなるまで２）を繰り返す。この結果得られたM1,M2が局所最適解である。
初期解のときに、M1,M2の個数が決まってしまうので、個数を変えたいときは初期解のM1の個数k1を変えて計算を実施する。
【００３７】
基地局集合の分割は、リング網１のノード１０配下で行われるのが現実的である。そこで、基地局集合の分割を細分化して以下のような集合分割問題の定式化ができる。
【００３８】
リング網のノード数をNとし，ノードj(1≦j≦N)配下の基地局集合をMjとする。MjをMj1(L2スイッチ1にトラヒックを収容)とMj2(L2スイッチ2にトラヒックを収容)に分割する問題を次のように定式化する（M1=∪Mj1, M2=∪Mj2とする。集合の個数
【００３９】
【数８】
0006035264.tif 000009
(1≦j≦N)は固定する）。
【００４０】
＜集合分割問題２＞
【００４１】
【数９】
0006035264.tif 000010
対応する局所最適化アルゴリズムは次のようになる。
【００４２】
＜局所最適化アルゴリズム2＞
１）式(10),(11),(12)を満たす基地局集合Mj1,Mj2 (1≦j≦N)を初期解として選ぶ。候補集合Oj=Mj1(1≦j≦N)とする。
【００４３】
２）ノードj(1≦j≦N)を固定する。
【００４４】
３）基地局
【００４５】
【数１０】
0006035264.tif 000011
と任意の
【００４６】
【数１１】
0006035264.tif 000012
を仮にメモリ上に置換して
【００４７】
【数１２】
0006035264.tif 000013
の値が小さくなるかどうか調べる。小さくならない場合はメモリ上における置換は行わない。小さくなる場合にはDの値が最も小さくなる
【００４８】
【数１３】
0006035264.tif 000014
とメモリ上に置換結果を書き込む。
【００４９】
Mj1←Mj1-{ij1}+{ij2'}, Mj2←Mj2-{ij2'}+{ij1}
最後に、処理の終わった基地局ij1を候補集合Ojから除く。
【００５０】
Oj←Oj-{ij1}
４）Oj=φとなるまで２）、３）の処理を繰り返す。この結果得られたMj1,Mj2がノードjについての局所最適解である。
【００５１】
５）ノードj(1≦j≦N)を変化させて３）、４）の処理を繰り返す。
【００５２】
［計算例］
次に、上記の局所最適化アルゴリズムを適用した計算例を示す。
【００５３】
図３に示すように４つの基地局からなるリング網を考える。24時間は昼夜に２分し、「1」を昼、「2」を夜とする。トラヒック量dは以下の通りとする。 
d(1,1)=4                                  (10)
d(1,2)=1                                  (11)
d(2,1)=4                                  (12)
d(2,2)=2                                  (13)
d(3,1)=1                                  (14)
d(3,2)=4                                  (15)
d(4,1)=1                                  (16)
d(4,2)=5                                  (17)
この問題設定に対して、局所最適化アルゴリズム１を適用する。
【００５４】
初期解をM1={1,2},M2={3,4}とする。候補集合をO={1,2}とする。このとき、
D=max{max{4+4,1+2}, max{1+1, 4+5}}=9
とし、「基地局1」と「基地局3」を置換すると、
D=max{max{1+4,4+2}, max{4+1, 1+5}=6
となり、「基地局1」と「基地局4」を置換すると、
D=max{max{1+4,5+2}, max{1+4, 4+1}}=7
となる。そこで「基地局1」と「基地局3」の置換を実施して、
M1={3,2},M2={1,4}, O={2}
とする。
【００５５】
次に、「基地局2」と「基地局1」を置換すると、
D=max{max{4+1,1+4}, max{2+1, 1+5}=6
となる。「基地局2」と「基地局4」を置換すると、
D=max{max{1+1,4+5}, max{4+4, 1+2}=9
となる。Dの値が小さくならないのでここで探索を終了する。その結果
M1={3,2},M2={1,4}
が局所最適解となり、ゲートウェイ内設備双方に最大6トラヒックの負荷がかかる。初期解はゲートウェイ内設備それぞれに最大8,9トラヒックの負荷がかかる。局所最適化によって昼夜のピークが相殺されて、ゲートウェイ内設備にかかる負荷が軽減されることがわかる。目的関数の定義の仕方から「基地局2」と「基地局1」の置換を実施しなかったが、もし実施していたらゲートウェイ内設備の一方のトラヒックを最大5にまで減らせるので最も良い解が得られていた。そのため本手法は最善の解を選ぶとはいえないがほとんどそれに近い解を見つけ出すことができた。このアルゴリズムが効果的になるのは基地局数
【００５６】
【数１４】
0006035264.tif 000015
が大きくなって場合の数が増えたときである。
【００５７】
次に、トラヒック振り分け表示装置３００について説明する。
【００５８】
トラヒック振り分け表示装置３００は、トラヒック振り分け表示部３１０を有する。
【００５９】
トラヒック振り分け表示部３１０は、通信網１の運用者、または、設計者による操作に基づき、リング網分割最適化装置１００に対して、設計、運用、管理の対象である基地局集合の分割の取得要求を実施し、リング網分割最適化装置１００から受信した値を表示する。
【００６０】
なお、上記のリング網分割最適化装置１００の各構成要素の動作をプログラムとして構築し、リング網分割最適化装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６２】
１  通信網（リング網）
２  無線基地局
３  携帯電話
１０  ノード
２０  インターネット接続サーバ
１００  リング網分割最適化装置
１１０  データ取得部
１２０  トラヒック振り分け部
１３０  基地局情報データベース
１４０  トラヒック情報データベース
２００  オペレーションシステム
２１０  ネットワークデータ収集部
２２０  ネットワーク情報データベース
３００  帯域表示装置
３１０  トラヒック振り分け表示部
【図１】
0006035264.tif 000016
【図２】
0006035264.tif 000017
【図３】
0006035264.tif 000018