(57)【要約】【課題】優良な網区分図を生成することによってネットワーク負荷を低減する移動通信網の区分方法を提供する。【解決手段】  複数の網区分アルゴリズムの中の一つを実行し、後続区分図を生成するステップと、目標関数に基づき、初期および後続の区分図の対応する関数値をそれぞれ生成するステップと、初期および後続の区分図の対応する関数値に基づき、初期および後続の区分図の中の優れたものを選出するステップとを初期区分図を有する移動通信網に実行し、システム的に優良な網区分図を生成することによってネットワーク負荷を低減する。【選択図】  図６
2007006426.tif 000002
【特許請求の範囲】
【請求項１】
目標関数に基づき、移動通信網の初期区分図の初期関数値を生成するステップと、
複数の網区分アルゴリズムの中から一つを選出するステップと、
前記選出した網区分アルゴリズムを実行し、前記移動通信網の後続区分図を生成するステップと、
前記目標関数に基づき、前記後続区分図の後続関数値を生成するステップと、
前記初期および後続の関数値に基づき、前記初期および後続の区分図内の中の優良なものを決定するステップとを含むことを特徴とする移動通信網の区分方法。
【請求項２】
前記初期および後続の関数値は、別々に初期および後続の区分図のそれぞれのネットワーク負荷に対応していることを特徴とする請求項１記載の移動通信網の区分方法。
【請求項３】
前記選出するステップと、前記実行するステップと、前記後続区分図を生成するステップとを繰り返し実行して区分図の序列を生成し、前記区分図の序列において、後続区分図は前の区分図よりも優れていることを特徴とする請求項１記載の移動通信網の区分方法。
【請求項４】
前記初期および後続の区分図は多層区分図であり、
前記実行するステップは、
複数の区分層の中から一つを選出するステップと、
前記選出した区分層において、前記選出した網区分アルゴリズムを実行して前記後続区分図を生成するステップとを含むことを特徴とする請求項１記載の移動通信網の区分方法。
【請求項５】
前記区分層は、繰り返して選出されることによって、前記選出された網区分アルゴリズムをそれぞれの区分層にバランス良く実行できることを特徴とする請求項４記載の移動通信網の区分方法。
【請求項６】
前記移動通信網は、複数のネットワークエレメントを含み、前記目標関数はそれぞれのネットワークエレメントの対応コスト関数に基づいて生成され、前記対応コスト関数は前記ネットワークエレメントの負荷推定に使用されることを特徴とする請求項１記載の移動通信網の区分方法。
【請求項７】
前記後続区分図は一組の区分制限を満たし、前記区分制限は一組の区分エリア制限および一組の区分層制限を含むことを特徴とする請求項１記載の移動通信網の区分方法。
【請求項８】
仮に前記初期および後続の区分図が多層区分図の場合、前記区分制限はさらに一組の多層制限を含むことを特徴とする請求項７記載の移動通信網の区分方法。
【請求項９】
移動通信網は、初期区分図を有し、
複数の網区分アルゴリズムの中から少なくとも一つを実行して前記移動通信網の後続区分図を生成するステップと、
目標関数に基づき、前記初期および後続の区分図の対応関数値を別々に生成するステップと、
前記初期および後続の区分図の対応関数値に基づき、前記初期および後続の区分図の中の優良なものを選出するステップとを含むことを特徴とする移動通信網の区分方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は移動通信網のネットワークプランニング（network planning）方法に関し、特にリファインされた区分図を生成することによってネットワーク負荷を低減できる網区分方法に関する。
【背景技術】
【０００２】
移動通信網は通常、移動管理（mobility management）に都合がいいように、複数の区分エリア（partition area）に区分される。これらの区分エリアは単層区分図（single-layer partition plan）を形成する。ある移動通信網においては多層（multi-layer）の区分構造が採用される。多層区分構造において、多くの区分層が階層体系を形成し、それぞれの区分層は一つまたは多くの対応する区分エリアから構成される。
【０００３】
例えば、ＧＳＭ（Global System for Mobile communication）ネットワークでは、図１、２、３、４に示すような多層区分構造を採用できる。図１は最低部の区分層が基地局（base transceiver station:ＢＴＳ）によって構成されることを示す。図２、３、４は下から上に向かって、基地局制御装置（base station controller:ＢＳＣ）、位置エリア（location area）および移動通信交換局（mobile switching center:ＭＳＣ）から構成される区分層を示す。図から分かるように、それぞれのＢＴＳエリアはＢＳＣエリア内に含まれ、それぞれのＢＳＣエリアは位置エリア内に含まれ、それぞれの位置エリアはＭＳＣエリア内に含まれる。図１、２、３、４が結合して図５に示すような多層区分図（multi-layer partition plan）が形成される。注意すべき点は、その他の種類の多層区分構造においては、低い区分層の区分エリアは高い区分層の二つまたはさらに多くの区分エリアを跨ることができる点である。
【０００４】
リファインまたは最適化された区分図を採用することによって、単層であっても多層であっても移動通信網の負荷を低減でき、ネットワーク効率も上昇する。しかし、従来技術においてはシステム的、客観的な解決方法を提供しておらず、ネットワーク管理者はリファインまたは最適化された区分図を探し出すために、試行錯誤または主観的な経験に頼るしかない。通常この種のやり方は効率が悪く、判断を誤りやすい。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、システム的に優良な網区分図を生成することによってネットワーク負荷を低減する移動通信網の区分方法を提供することにある。
【課題を解決するための手段】
【０００６】
本発明の一実施例において、移動通信網の区分方法は、目標関数に基づき、初期多層区分図の初期関数値を生成するステップと、複数の網区分アルゴリズムの中から一つを選出するステップと、選出した網区分アルゴリズム（network partitioning algorithm）を実行し、後続区分図を生成するステップと、前述の目標関数に基づき、後続多層区分図の後続関数値を生成するステップと、初期および後続の関数値に基づき、初期および後続の多層区分図の中から優良なものを決定するステップとを含む。
【０００７】
本発明のもう一つの実施例において、移動通信網の区分方法は、目標関数に基づき、
初期単層区分図の初期関数値を生成するステップと、複数の網区分アルゴリズムの中から一つを選出するステップと、選出した網区分アルゴリズムを網に応用し、後続単層区分図を生成するステップと、前述の目標関数に基づき、後続単層区分図の後続関数値を生成するステップと、初期および後続の関数値に基づき、初期および後続の単層区分図内の優良なものを選出するステップとを含む。
【発明の効果】
【０００８】
目標関数に基づき、初期多層区分図の初期関数値を生成するステップと、複数の網区分アルゴリズムの中から一つを選出するステップと、選出した網区分アルゴリズムを実行し、後続区分図を生成するステップと、前述の目標関数に基づき、後続多層区分図の後続関数値を生成するステップと、初期および後続の関数値に基づき、初期および後続の多層区分図の中から優良なものを決定するステップとを初期区分図を有する移動通信網に実行することによってネットワーク負荷を低減する。
【発明を実施するための最良の形態】
【０００９】
以下に示す実施例においてはＧＳＭネットワークを例としているが、当該技術に熟知する者なら本発明の技術特徴をその他の移動通信網に応用できる。従って本発明はＧＳＭネットワークだけへの応用に限らない。
【００１０】
図６は本発明の一実施例による多層区分構造を有する移動通信網の区分方法を示す流れ図である。本実施例において、移動通信網は多層区分構造（複数の区分層）を採用しており、初期多層区分図を含む。図６に示すように下記のステップを含む。
【００１１】
ステップ２１：目標関数に基づき、初期多層区分図の初期関数値を生成するステップ。
ステップ２２：複数の網区分アルゴリズムの中から一つを選出するステップ。
ステップ２３：前述の区分層の中から一つを選出するステップ。
ステップ２４：選出した区分層において、選出した網区分アルゴリズムを実行し、後続区分図を生成するステップ。
ステップ２５：前述の目標関数に基づき、後続多層区分図の後続関数値を生成するステップ。
ステップ２６：初期および後続の関数値に基づき、初期および後続の多層区分図の中から優良なものを決定するステップ。
【００１２】
本実施例において、目標関数は多層区分図がもたらすネットワーク負荷の推定に使用される。ネットワーク負荷の少ない区分図はネットワーク負荷の大きい区分図よりも優れているので、ステップ２６において、後続区分図が初期区分図よりも優れているかどうかは、初期関数値と後続関数値との比較によって判定できる。仮に後続区分図が優れている場合、ネットワーク内で応用でき、ネットワーク負荷を低減する。優れていない場合、後続区分図は破棄される。移動通信網は複数のネットワークエレメントを含み、目標関数はそれぞれのネットワークエレメントの対応コスト関数（cost function）に基づいて生成される。ここでのネットワークエレメントとはネットワーク内でネットワーク負荷をもたらすエレメントであり、対応コスト関数はそれぞれのネットワークエレメントの負荷の推定に使用される。本実施例において、目標関数はこれらのネットワークエレメントの対応コスト関数の線形結合である。即ち、
（数１）ｆ(P)=α１・ｆ１(P)+α2・ｆ2(P)+…+αn・ｆn(P)
となる。
【００１３】
（数式１）において、Pは区分図を表し、αiはｆiの重み付け係数であり、ｆiはネットワークエレメントiのコスト関数であり、ｆは網全体の目標関数である。重み付け係数は調整でき、対応ネットワークエレメントの網全体の負荷に対する重要性を反映する。注意すべきことは、（数式１）の右側のそれぞれの項は異なる目的に対応して決定することができる。例えばＧＳＭネットワークにおける目標関数は、
（数２）ｆ(P)=αBTS,1・ｆBTS,1(P)+αBTS,2・ｆBTS,2(P)+…+αBTS,n・ｆBTS,n(P)
と定義できる
【００１４】
ｆBTS,i(P)はＢＴＳiの位置更新（location update）量を表す。従って、上述の目標関数は区分図への反映をPとするとき、網内のすべてのｎ個のＢＴＳの総位置更新量となる。従って、目標関数は網内において考慮されるある特定部分の負荷を反映させて設計できる。もう一つの例において、考慮されるのはＧＳＭネットワーク内のＭＳＣとＢＳＣのＣＰＵ負荷である。従って、目標関数は
（数３）ｆ(P)=αMSC,1・ｆMSC,1(P)+…+αMSC,n・ｆMSC,n(P)
+αBSC,1・ｆBSC,1(P)+…+αBSC,p・ｆBSC,p(P)
と定義できる。
【００１５】
ｆMSC,i(P)はＭＳＣiのＣＰＵ負荷であり、ｆBSC,j(P)はＢＳＣjのＣＰＵ負荷である。大部分のＣＰＵ負荷は主要な演算が寄与し、例えば、位置更新、ＭＳＣまたはＢＳＣ間のハンドオーバー（handover）、ＢＳＣ内のハンドオーバー、受話（mobile terminating call:ＭＴＣ）、発話（mobile originating call:ＭＯＣ）、ページング（paging）、ショートメッセージサービス（short message service:ＳＭＳ）などである。これらの主要な演算は当該技術に熟知する者は熟知するものであるので、説明は行わない。従ってＭＳＣiとＢＳＣjのＣＰＵ負荷はそれぞれ、
（数４）ｆMSC,i(P)=αMTC,I×#(MTC)+αMOC,I×#(MOC)+αSMS,i×#(SMS)+αHO×#(inter-MSC handover)+αLU×#(location update)+αPG×#(paging) 
（数５）ｆBSC,j(P)=βMTC,j×#(MTC)+βMOC,j×#(MOC)+βSMS,j×#(SMS)+βHO×[#(inter-BSC handover) + #(intra-BSC handover)]+βLU×#(location update)+βPG×#(paging) 
と表すことができる。
【００１６】
αとβは重み付け係数をあらわし、#（特定演算）は特定演算が一定時間内に発生する回数を表す。これらのαとβは例えば回帰モデル（regression model）のような実行可能なすべての統計方法によって推定できる。
【００１７】
仮に網内のすべての主要なエレメントの負荷を考慮した場合、目標関数は網の全体のコスト関数と定義できる。例えば、ＧＳＭネットワークにおいて、主要エレメントは、移動通信交換局（mobile switching center:ＭＳＣ）、基地局制御装置（base station controller:ＢＳＣ）、基地局（base transceiver station:ＢＴＳ）、Ａインターフェース（A-interface:ＭＳＣとＢＳＣとの間の接続）およびＡ−ｂｉｓインターフェース（A-bis interface:ＢＳＣとＢＴＳとの間の接続）を含む。従って、目標関数は下記のように定義でき、網の全体の負荷を反映する。
（数６）ｆ(P)=αMSC,1・ｆMSC,1(P)+…+αMSC,n・ｆMSC,n(P)
+αA,1・ｆA,1(P)+…+αA,n*p・ｆA,n*p(P)
+αBSC,1・ｆBSC,1(P)+…+αBSC,p・ｆBSC,p(P)
+αAbis,1・ｆAbis,1(P)+…+αAbis,p*q・ｆAbis,p*q(P)
+αBTS,1・ｆBTS,1(P)+…+αBTS,q・ｆBTS,q(P)
【００１８】
ｆMSC,i(P)はＭＳＣiの負荷を表し、ｆA,j(P)はAインターフェースjの負荷であり、ｆBSC,k(P)はＢＳＣkの負荷であり、ｆAbis,l(P)はＡ−ｂｉｓインターフェースlの負荷であり、ｆBTS,ｍ(P)はＢＴＳmの負荷である。ＧＳＭネットワークの一実施例において、（数式６）は目標関数とし、ＭＳＣiとＢＳＣkのＣＰＵ負荷と定義し、ＢＴＳmの負荷をＢＴＳmの位置更新量と定義し、Aインターフェースjの負荷をAインターフェースjの現在のトラフィック量（current traffic quantity）とトラフィック容量（traffic capacity）との比率と定義し、Ａ−ｂｉｓインターフェースlの負荷をＡ−ｂｉｓインターフェースlの現在のトラフィック量とトラフィック容量との比率と定義する。
【００１９】
ステップ２２において、選出される網区分アルゴリズムは初期区分図に基づいて後続区分図を生成できるすべてのアルゴリズムである。注意すべき点は、初期区分図は網の最初の区分状態であり、即ち最低部の区分層のそれぞれの区分エリアであり、同時にその他の高い区分層の区分エリアであり、あるアルゴリズムの運転要求に符号する。選出可能な網区分アルゴリズムは、Ｋ‐Ｌ（Kernighan-Lin）アルゴリズム、欲張りアルゴリズム（greedy algorithm）、Ｆ‐Ｍ（Fiduccia-Mattheyses）アルゴリズム、遺伝的アルゴリズム（genetic algorithm）、シュミレーティッド・アニーリングアルゴリズム（simulated annealing algorithm）、動的区分ユニット（dynamic partition unit:ＤＰＵ）などであるが、これらに限らない。Ｋ‐Ｌアルゴリズムに関しては、“An Efficient Heuristic Procedure for Partitioning Graphs”（The Bell system technical journal,49(1):291-307,1970）を参照。欲張りアルゴリズムに関しては、“Introduction to Algorithms: A Creative Approach, chapter 7”（pp.210.about.pp.211,Addison-Wesley Publishing Company,1989）を参照。Ｆ‐Ｍアルゴリズムに関しては、“A Linear-Time Heuristic for Improving Network Partitions”（Proc.of DAC,1982）を参照。遺伝的アルゴリズムに関しては、“A Genetic Algorithm For Optimizing Multiple Part Placement To Reduce Build Time”（Proceedings of the Fifth International Conference on Rapid Prototyping,Dayton,Ohio,June 1994）を参照。シュミレーティッド・アニーリングアルゴリズムに関しては、“Location Area Planning in Cellular Networks Using Simulated Annealing”（Proceedings of IEEE Infocom,The Conference on Computer Communications 2001,Anchorage,Ak.,Apr.22-26,2001）を参照。動的区分ユニットアルゴリズムに関しては、米国特許第１０／７６０，３００号明細書を参照。本明細書の申請日は２００４年１月２１日であり、本発明と同一の発明者および申請人である。上述の文献は本明細書の参考文献とする。
【００２０】
ステップ２２および２３において、網区分アルゴリズムおよび区分層は網の需要および実際の状況に基づいて選出される。
【００２１】
ステップ２４は選出された区分層に対して選出されたアルゴリズムを実行し、プログラムを進行させて生成された多層区分図は一組の区分制限（partitioning constraint）を満たさなければならない。区分制限はアルゴリズムの運転を制約し、一組の区分エリア制限および一組の区分層制限を含む。区分エリア制限とそれぞれの区分エリア自身とは関係があり、区分層制限と全ての区分層とは関係がある。例えば、ＧＳＭネットワークにおいて、それぞれの区分エリアの中の一区分エリアはページング率（paging rate）が上限を超えないように制限し、ＭＳＣエリアの区分層の中の一区分層はＭＳＣエリアの数量を固定値に制限する。一実施例において、前述の区分制限はさらに一組の多層制限（multi-layer constraint）を含み、全ての多層区分図と関係がある。多層制限の一例として、低区分層のそれぞれの区分エリアは高区分層に含まれる単一区分エリアが必要である。例えば、ＧＳＭネットワークにおいて、それぞれのＢＴＳエリアは一ＢＳＣエリア内に含まれ、それぞれのＢＳＣエリアは一位置エリア内に含まれ、それぞれの位置エリアは一ＭＳＣエリア内に含まれる。
【００２２】
図６のもう一つの実施例において、ステップ２２から２５を繰り返し実行し、区分図の序列を生成する。この序列において、後続区分図は前の区分図よりも優れている。ステップ２２から２５を繰り返し実行し、もし後続区分図が前の区分図よりも優れていない場合、図６の工程は停止され、最後に生成された区分図が最適化された区分図とされる。本実施例において、ステップ２３は選出された順序に基づいて区分層を選出し、選出された網区分アルゴリズムをそれぞれの区分層にバランス良く実行できる。このようにして、特定の区分層を過度にプログラムするのを避けることができ、その他の区分層のプログラムの柔軟性を制限する可能性を有する。
【００２３】
本発明の区分方法は単層区分構造を有する移動通信網にも応用できる。図７は本発明
の一実施例による単層区分構造を有する移動通信網の区分方法を示す流れ図である。こ
の網は初期単層区分図を有する。図７に示すように、本方法は下記のステップを含む。
【００２４】
ステップ３１：目標関数に基づき、初期単層区分図の初期関数値を生成するステップ。
ステップ３２：複数の網区分アルゴリズムの中から一つを選出するステップ。
ステップ３３：選出した網区分アルゴリズムを網に応用し、後続単層区分図を生成す
るステップ。
ステップ３４：前述の目標関数に基づき、後続単層区分図の後続関数値を生成するス
テップ。
ステップ３５：初期および後続の関数値に基づき、初期および後続の単層区分図内の優良なものを選出するステップ。
【００２５】
目標関数の生成および網区分アルゴリズムの選出は図６の実施例と類似するので、こ
こでは説明をしない。また、ステップ３３で生成された後続単層区分図は一組の区分制
限を満たさなければならず、一組の区分エリア制限および一組の区分層制限を含み、図
６の実施例と類似するので、ここでは説明をしない。
【００２６】
図３の実施例において、ステップ３２からステップ３４を繰り返し実行し、区分図の
序列を生成する。この序列において、後続区分図は前の区分図よりも優れている。ステップ３２からステップ３４を繰り返し実行し、もし後続の区分図がもとの区分図よりも優れていない場合、図７の工程は停止され、最後に生成された区分図が最適化された区分図とされる。
【００２７】
以上の内容は実施例を利用して本発明を詳細に説明したものであり、本発明の範囲を制限するものではない。当該技術に熟知する者による本発明の主旨を逸脱しない範囲における変更、調整は全て本発明に含まれる。
【図面の簡単な説明】
【００２８】
【図１】ＧＳＭネットワークの多層区分構造を示す模式図である。
【図２】ＧＳＭネットワークの多層区分構造を示す模式図である。
【図３】ＧＳＭネットワークの多層区分構造を示す模式図である。
【図４】ＧＳＭネットワークの多層区分構造を示す模式図である。
【図５】ＧＳＭネットワークの多層区分構造を示す模式図である。
【図６】本発明の一実施例による多層区分構造を有する移動通信網の区分方法を示す流れ図である。
【図７】本発明の一実施例による単層区分構造を有する移動通信網の区分方法を示す流れ図である。
【符号の説明】
【００２９】
２１：目標関数に基づき、初期多層区分図の初期関数値を生成する。
２２：複数の網区分アルゴリズムの中から一つを選出する。
２３：区分層の中から一つを選出する。
２４：選出した区分層において、選出した網区分アルゴリズムを実行し、後続区分図を生成する。
２５：前述の目標関数に基づき、後続多層区分図の後続関数値を生成する。
２６：初期および後続の関数値に基づき、初期および後続の多層区分図の中から優良なものを決定する。
３１：目標関数に基づき、初期単層区分図の初期関数値を生成する。
３２：複数の網区分アルゴリズムの中から一つを選出する。
３３：選出した網区分アルゴリズムを網に応用し、後続単層区分図を生成する。
３４：前述の目標関数に基づき、後続単層区分図の後続関数値を生成する。
３５：初期および後続の関数値に基づき、初期および後続の単層区分図の中から優良なものを選出する。
【図１】
2007006426.tif 000003
【図２】
2007006426.tif 000004
【図３】
2007006426.tif 000005
【図４】
2007006426.tif 000006
【図５】
2007006426.tif 000007
【図６】
2007006426.tif 000008
【図７】
2007006426.tif 000009
【外国語明細書】
2007006426.tif 000010
2007006426.tif 000011
2007006426.tif 000012
2007006426.tif 000013
2007006426.tif 000014
2007006426.tif 000015
2007006426.tif 000016
2007006426.tif 000017
2007006426.tif 000018
2007006426.tif 000019
2007006426.tif 000020
2007006426.tif 000021
2007006426.tif 000022
2007006426.tif 000023
2007006426.tif 000024
2007006426.tif 000025
2007006426.tif 000026