光ネットワーク設計支援システム及びプログラム
【課題】
多数の加入希望者宅と複数の収容局が非一様に分布する場合に光ファイバコストを低減した設計を支援する。
【解決手段】
ＣＰＵ（１０）の光スプリッタ配置設計機能（２２）が、位置情報ＤＢ（１８）から収容局と加入希望者の位置情報を読み込む。クラスタリング処理機能（２４）が、最大ドロップケーブル長及び光スプリッタ分岐数の条件下で、加入希望者をクラスタ数（初期値）Ｎｃのクラスタに分類する。この際、各クラスタで、光スプリッタの位置を決定する。収用局決定機能（２６）が、ボロノイ領域計算機能（２８）に指示して、Ｎ個の収容局の位置を母点として、全加入希望者をボロノイ領域に分割する。ボロノイ領域内の光スプリッタを同じボロノイ領域内の収用局に接続する。収用局に空き回線が無い場合には、隣接するボロノイ領域から接続可能な収容局を探索する。
多数の加入希望者宅と複数の収容局が非一様に分布する場合に光ファイバコストを低減した設計を支援する。
【解決手段】
ＣＰＵ（１０）の光スプリッタ配置設計機能（２２）が、位置情報ＤＢ（１８）から収容局と加入希望者の位置情報を読み込む。クラスタリング処理機能（２４）が、最大ドロップケーブル長及び光スプリッタ分岐数の条件下で、加入希望者をクラスタ数（初期値）Ｎｃのクラスタに分類する。この際、各クラスタで、光スプリッタの位置を決定する。収用局決定機能（２６）が、ボロノイ領域計算機能（２８）に指示して、Ｎ個の収容局の位置を母点として、全加入希望者をボロノイ領域に分割する。ボロノイ領域内の光スプリッタを同じボロノイ領域内の収用局に接続する。収用局に空き回線が無い場合には、隣接するボロノイ領域から接続可能な収容局を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＰＤＳ（Passive Double Star）型光ネットワークの設計を支援する光ネットワーク設計支援システム及びプログラムに関する。
【背景技術】
【０００２】
ＰＤＳ型光ネットワーク、すなわち、いわゆるＰＯＮ（Passive Optical Network）ネットワークにおいて、複数の収容局に多数の加入希望者を配分する場合、従来は、熟練技術者の手作業に頼っていた。非特許文献１、２には、収容局を中心とした円形のエリア内にＰＯＮ加入希望者宅が一様に分布していることを前提とする場合で、多段分岐光アクセスネットワークの敷設コストを最小化するコンピュータ手法が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】宇田川大輔、松本隆男「多段分岐光アクセスネットワークの最小光ファイバ長に関する検討」電子情報通信学会総合大会、Ｂ−８−２９、２００３年
【非特許文献２】宇田川大輔、松本隆男「多段分岐アクセスネットワークのコスト最小化条件に関する検討」電子情報通信学会総合大会、Ｂ−８−１１、２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００４】
熟練技術者による手作業では、コスト的に最適解又は一定以上に好ましい解を得られているかどうかを確認できない。また、作成に膨大な手間と時間を要する。
【０００５】
非特許文献１および２に記載される手法は、加入希望者宅が一様に分布していない場合や、収容局ごとにカバーするエリアの形状が円形でない場合などには適用できない。しかも、このような適用的な状況が、より現実的である。
【０００６】
そこで、本発明は、多数の加入希望者宅と複数の収容局が非一様に分布する場合を前提とし、光ファイバコストに関して好ましい解を提示する光ネットワーク設計支援システム及びプログラムを提示することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る光ネットワーク設計支援システムは、収容局および加入希望者の位置情報を保存する位置情報データベースと、最大ドロップケーブル長、光スプリッタ分岐数及びクラスタ数初期値を記憶するパラメータ記憶手段と、当該加入希望者を当該クラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定する光スプリッタ位置決定手段であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定手段と、当該光スプリッタ位置決定手段により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続する光スプリッタ／収用局接続手段とを具備することを特徴とする。
【０００８】
本発明に係る光ネットワーク設計支援プログラムは、コンピュータを使い、複数の収用局及び複数の加入希望者に対して、位置情報データベースに記憶される当該収容局および当該加入希望者の位置情報を参照し、最大ドロップケーブル長及び光スプリッタ分岐数の条件の下で、光スプリッタの位置、及び当該光スプリッタを収用する収用局を決定する光ネットワーク設計支援プログラムであって、当該コンピュータに、当該複数の加入希望者をクラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定させる光スプリッタ位置決定機能であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定機能と、当該コンピュータに、当該光スプリッタ位置決定機能により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続させる光スプリッタ／収用局接続機能とを具備することを特徴とする。
【発明の効果】
【０００９】
本発明により、多数の加入希望者宅と複数の収容局が非一様に分布する場合において、加入希望者宅と収容局の位置情報をもとに、光ファイバコストを低減した設計を支援できる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施例の概略構成ブロック図である。
【図２】本実施例のネットワーク設計処理のフローチャートである。
【図３】収用局と加入希望者の分布を示す説明例でる。
【図４】図２のクラスタリング処理の詳細なフローチャートである。
【図５】図３に示す例をクラスタに分割した例である。
【図６】図５に示す分割例で１つのクラスタを更に２つに分割した例である。
【図７】図６に示すクラスタ分割例で、各光スプリッタに近くの加入希望者を接続した状態の説明図である。
【図８】図２に示すフローで、光スプリッタと収用局を接続する処理のフローチャートである。
【図９】図８に示すフローにより光スプリッタと収用局を接続した状態の説明図である。
【図１０】図２のクラスタリング処理の別のフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、本発明の実施例を詳細に説明する。
【実施例１】
【００１２】
図１は、本発明に係る設計支援システムの概略構成ブロック図を示す。コンピュータのＣＰＵ１０に、キーボード等の入力装置１２と、表示装置１４が接続する。ＣＰＵ１０上で、本実施例の設計支援プログラムが動作する。パラメータ記憶装置１６は、ＣＰＵ上の設計支援プログラムに必要な、入力装置１２により入力される各種パラメータを記憶する。パラメータ記憶装置１６は、例えば、コンピュータを構成するＲＡＭ又は二次記憶装置としてのハードディスク装置などからなる。
【００１３】
位置情報データベース（ＤＢ）１８は、ＰＯＮネットワークの設計対象地域に位置するＰＯＮ加入希望者および収容局の、２次元平面上での位置情報を保持する。収容局の位置情報をＣｉ（ｉ＝１〜Ｎ）とし、加入希望者の位置情報をＸｊ（ｊ＝１〜Ｍ）とする。この説明例では、収容局がＮ台あり、加入希望者数がＭであるとする。Ｃｉ（ｉ＝１〜Ｎ）は各収容局を示す場合と、その位置座標を示す場合とがある。同様に、Ｘｊ（ｊ＝１〜Ｍ）は、加入希望者自体を示す場合と、その一座標を示す場合とがある。
【００１４】
最大収容回線数データベース（ＤＢ）２０は、各収容局Ｃｉ（ｉ＝１〜Ｎ）の最大収容回線数Ｎｆｉ（ｉ＝１〜Ｎ）を示す。例えば、Ｃ１の最大収容回線数はＮｆ１である。
【００１５】
データベースとして、収用局の位置情報と最大収用回線数を保持する収用局データベースと、加入希望者に関する位置情報を保持する加入希望者データベースとを有する構成であってもよいことは明らかである。
【００１６】
ＣＰＵ１０は、設計支援プログラムの機能要素として、以下の機能２２〜３０を具備する。図２は、ＣＰＵ１０による設計支援プログラムのメインフローの動作フローチャートを示す。
【００１７】
光スプリッタ配置設計機能２２が、位置情報ＤＢ１８から収容局の位置情報Ｃｉ（ｉ＝１〜Ｎ）と、加入希望者の位置情報Ｘｊ（ｊ＝１〜Ｍ）を読み込む（Ｓ１）。この説明例では、収容局がＮ台あり、加入希望者がＭ人である。図３は、加入希望者と収容局の分布例を示す。図３に示す分布例では、１６人の加入希望者を３つの収用局のどれに接続すべきかを検討し、決定することになる。Ｍ＝１６、Ｎ＝３となる。各収用局には１又は複数のＰＯＮシステムを収容可能であるとする。
【００１８】
オペレータは、入力装置１２を使って、光ネットワーク設計の基本パラメータ、ここでは、最大ドロップケーブル長Ｌｍａｘ、光スプリッタ分岐数Ｎｓ及びクラスタ数（初期値）ＮｃをＣＰＵ１０に入力する（Ｓ２）。もちろん、これらのパラメータの入力（Ｓ２）を、ステップＳ１に先行して実施しておいても良い。最大ドロップケーブル長Ｌｍａｘは、光スプリッタから加入希望者宅までの、許容される最長距離である。光スプリッタ分岐数Ｎｓは１つの光スプリッタに収容できる加入希望者数である。クラスタ数Ｎｃは、ＰＯＮシステム数であり、ここでは、１つのＰＯＮシステムに１つの光スプリッタを想定しているので、光スプリッタ数でもある。クラスタ数Ｎｃは、収容局数又は加入希望者数により、計算途中で増減されることがある。図３に示す例では、収用局の数が３であることから、クラスタ数Ｎｃの初期値を３とする。
【００１９】
次に、クラスタリング処理機能２４を使って、加入希望者をクラスタ数Ｎｃの初期値以上のクラスタ数でクラスタ化し、各クラスタに光スプリッタを割り当てる（Ｓ４）。具体的には、クラスタリング処理機能２４が、ステップＳ１，Ｓ２で設定されパラメータ記憶装置１６に記憶される条件及び初期値に従い、各クラスタ内の加入希望者数がＮｓ以下となり、かつ、ドロップケーブル長が最大長Ｌｍａｘを越えないという条件の下で、全加入希望者をクラスタリングし、光スプリッタ候補の位置を決定する（Ｓ４）。
【００２０】
図４は、クラスタリング処理（Ｓ４）の詳細なフローチャートを示す。メインルーチンから引き渡された対象領域及びクラスタ数Ｎｃに従い、光スプリッタの位置候補となるＮｃ個のセントロイドＹｋ（ｋ＝１〜Ｎｃ）を対象領域内にランダムに設定する（Ｓ１１）。
【００２１】
所定のクラスタリング処理により、対象領域内に存在する全加入希望者をＮｃ個のクラスタに分割する（Ｓ１２）。これは、各クラスタ内で、セントロイドＹｋと当該クラスタに属する加入希望者との間のユークリッド距離の総和が最小となるように、各クラスタへの加入希望者の所属と各セントロイドの位置を決定する処理である。このようなクラスタリング処理法としては、データマイニングの分野において広く用いられているｋ-ｍｅａｎｓ法などがある。このクラスタリング処理で決定した各セントロイドが、光スプリッタの位置候補となる。
【００２２】
図５は、図３に示す例に対し、クラスタリング処理（Ｓ１２）により３つのクラスタに加入希望者を分割した結果を示す。破線がクラスタの境界を示す。黒丸は、セントロイドＹｋ（光スプリッタ候補）である。
【００２３】
各セントロイドＹｋについて、光スプリッタに収容可能な加入希望者数Ｎｓ、及び最大ドロップケーブル長Ｌｍａｘを満たすかどうかを調べる（Ｓ１４，Ｓ１５）。そのために、まず、条件判定対象のクラスタ／セントロイドを指定する変数ｋを１で初期化する（Ｓ１３）。そして、ｋ番目のクラスタに属する加入希望者がＮｓ以下かどうかを調べ（Ｓ１４）、ｋ番目のクラスタ内の加入希望者とセントロイドＹｋとの間の距離が全て、最大ドロップケーブル長Ｌｍａｘ以下であるかどうかを調べる（Ｓ１５）。
【００２４】
何れかの条件（Ｓ１４，Ｓ１５）が満たされない場合、クラスタリング処理機能により、ｋ番目のクラスタを２つのクラスタに分割させる（Ｓ１８）。図６は、図５に示す例で、右下のクラスタにおいて、ステップＳ１４の条件が満たされず、このクラスタを更に２分割した結果を示す。この場合、クラスタ数（又はセントロイド数）は、４になる。ソフトウエアプログラムとしては、ステップＳ１８は、ｋ番目のクラスタを対象領域とし、クラスタ数を２とする引数を、図４に示すクラスタリング処理ルーチン又は関数に渡して再帰的に実行させることで、この目的を実現している。
【００２５】
ｋ番目のクラスタに属する加入希望者がＮｓ以下であり（Ｓ１４）、かつ、ｋ番目のクラスタ内の加入希望者とセントロイドＹｋとの間のユークリッド距離が全て、最大ドロップケーブル長Ｌｍａｘ以下である場合（Ｓ１５）、ｋをインクリメントし（Ｓ１７）、次のクラスタについてステップＳ１４，Ｓ１５の条件を満たすかどうかを確認する。
【００２６】
全クラスタについて、ステップＳ１４，Ｓ１５の条件を満たすことを確認したら、図３に戻り、セントロイドを光スプリッタ位置として確定し、各クラスタ内の加入希望者を同じクラスタ内の光スプリッタに論理接続する（Ｓ５）。この時点で、光スプリッタの配置場所とドロップケーブルの設計が完了する。なお、ｋ-ｍｅａｎｓ法などのクラスタリング手法は局所最適解に収束することが知られている。従って、得られるＰＯＮネットワークの設計結果は、光ファイバ線路長に対する準最適解となる。図７は、図６に示す例における光スプリッタ候補位置（セントロイド）に光スプリッタを配置し、ステップＳ５により、加入希望者を同じクラスタ内の光スプリッタに接続した状態を示す。
【００２７】
収用局決定機能２６が、ステップＳ５で位置が確定した各光スプリッタをどの収用局に接続するかを決定する（Ｓ６）。ステップＳ６の詳細なフローチャートを図８に示す。
【００２８】
収用局決定機能２６は、ボロノイ領域計算機能２８に指示して、Ｎ個の収容局の位置を母点として、設計対象範囲をボロノイ領域に分割させる（Ｓ２１）。ボロノイ領域とは、母点からの距離が、他の母点からの距離よりも短い点の集合を表わす。領域全体を複数のボロノイ領域に区切ったものは、ボロノイ図と呼ばれる。図９は、図７に示す収用局と光スプリッタの配置に対してボロノイ領域への分割を実施した結果であって、破線がボロノイ領域の境界線を示す。ボロノイ図の作図方法としては、逐次添加法や再帰二分法などがある。
【００２９】
収用局決定機能２６は、得られたボロノイ領域の全てについて、以下の処理を実行する。まず、処理対象のボロノイ領域を指定する変数ｋを１で初期化する（Ｓ２２）。収用局決定機能２６は、最大収容回線数ＤＢ２０からｋ番目の収容局の最大収容回線数Ｎｆｋを取得する（Ｓ２３）。ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋ以下か否かを判断する（Ｓ２４）。すなわち、ｋ番目のボロノイ領域内に存在する光スプリッタ数に等しいＰＯＮシステムを、ｋ番目の収用局にまだ収容可能かどうかを調べる。
【００３０】
ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋ以下の場合（Ｓ２４）、ｋ番目のボロノイ領域内に存在する各光スプリッタをｋ番目の収容局に接続する（Ｓ２５）。ｋがＮｃに等しく無ければ（Ｓ２６）、ｋをインクリメントして（Ｓ２７）、Ｓ２３以降を繰り返す。ｋがＮｃに等しくなれば（Ｓ２６）、図８に示す処理を終了する。
【００３１】
ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋを越える場合（Ｓ２４）、もはや、ｋ番目のボロノイ領域内に存在する全光スプリッタをｋ番目の収容局に接続することができない。そこで、隣接するボロノイ領域ｊ（但し、j≠ｋ）であって、そのボロノイ領域ｊ内の全光スプリッタ数と、既に接続済みの隣接領域の光スプリッタ数を足してもまだ空きがある収用局を有するものがあるかどうかを調べる（S２８）。すなわち、隣接するボロノイ領域の収用局への接続可能性を調べる。そのような隣接ボロノイ領域ｊ（但し、j≠ｋ）が無い場合（Ｓ２８）、収用局決定機能２６は、表示装置１４に、ＰＯＮネットワークの設計不能を示すエラーメッセージを表示する（Ｓ２９）。
【００３２】
空きのある収用局を有する隣接ボロノイ領域ｊ（但し、j≠ｋ）が存在する場合（Ｓ２８）、ｋ番目のボロノイ領域内の光スプリッタの内で、当該隣接ボロノイ領域ｊ（但し、j≠ｋ）の収用局Ｃｊに最も近い光スプリッタを収用局Ｃｊに接続する（Ｓ３０）。そして、ステップＳ２４以降を繰り返す。これにより、ステップＳ２４で考慮すべき光スプリッタ数が１だけ減る。ステップＳ３０を必要回数だけ繰り返すことで、最終的にステップＳ２４の条件が満たされ、先に説明したように、次のボロノイ領域の処理に移行する（Ｓ２６，Ｓ２７）。
【００３３】
このようにして、ステップＳ５で配置された全光スプリッタを、可能な限り近い収用局に接続できる。これで、図９に示すように、ＰＯＮネットワークの設計が完了する。設計結果出力機能３０は、設計結果を表示装置１４に出力する。もちろん、設計結果を印刷出力するなり、図示しないハードディスクに保存してもよい。
【実施例２】
【００３４】
図４に示すフローでは、クラスタ内で加入希望者数の条件又はドロップケーブル長の条件が満たされないクラスタを再帰処理で２分割するようにしたが、クラスタ数Ｎｃをインクリメントして、全体でクラスタリング処理を再実行してもよい。図１０は、そのように図４を変更したフローチャートを示す。図３のステップＳ１８の代わりに、クラスタ数Ｎｃをインクリメントして（Ｓ１８ａ）、ステップＳ１１以降を再実行する。
【００３５】
この方法では、クラスタリングを仕切り直すことになり、図３に示すフローよりも時間がかかるが、全体を再考することになるので、全体的には全加入希望者の良好な配分を実現できる。
【００３６】
本発明によれば、例えば、多数のＰＯＮ加入希望者宅と複数の収容局が非一様に分布する場合において、加入希望者宅と収容局の位置情報のみをもとに、光ファイバコストに対する準最適解を与えるＰＯＮネットワークを設計できる。これにより、ＰＯＮサービスを展開する通信事業者のＰＯＮネットワーク設計負担を軽減できる。
【００３７】
特定の説明用の実施例を参照して本発明を説明したが、特許請求の範囲に規定される本発明の技術的範囲を逸脱しないで、上述の実施例に種々の変更・修整を施しうることは、本発明の属する分野の技術者にとって自明であり、このような変更・修整も本発明の技術的範囲に含まれる。
【符号の説明】
【００３８】
１０：ＣＰＵ
１２：入力装置
１４：表示装置
１６：パラメータ記憶装置
１８：位置情報データベース（ＤＢ）
２０：最大収容回線数データベース（ＤＢ）
２２：光スプリッタ配置設計機能
２４：クラスタリング処理機能
２６：収用局決定機能
２８：ボロノイ領域計算機能
３０：設計結果出力機能
【技術分野】
【０００１】
本発明は、ＰＤＳ（Passive Double Star）型光ネットワークの設計を支援する光ネットワーク設計支援システム及びプログラムに関する。
【背景技術】
【０００２】
ＰＤＳ型光ネットワーク、すなわち、いわゆるＰＯＮ（Passive Optical Network）ネットワークにおいて、複数の収容局に多数の加入希望者を配分する場合、従来は、熟練技術者の手作業に頼っていた。非特許文献１、２には、収容局を中心とした円形のエリア内にＰＯＮ加入希望者宅が一様に分布していることを前提とする場合で、多段分岐光アクセスネットワークの敷設コストを最小化するコンピュータ手法が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】宇田川大輔、松本隆男「多段分岐光アクセスネットワークの最小光ファイバ長に関する検討」電子情報通信学会総合大会、Ｂ−８−２９、２００３年
【非特許文献２】宇田川大輔、松本隆男「多段分岐アクセスネットワークのコスト最小化条件に関する検討」電子情報通信学会総合大会、Ｂ−８−１１、２００４年
【発明の概要】
【発明が解決しようとする課題】
【０００４】
熟練技術者による手作業では、コスト的に最適解又は一定以上に好ましい解を得られているかどうかを確認できない。また、作成に膨大な手間と時間を要する。
【０００５】
非特許文献１および２に記載される手法は、加入希望者宅が一様に分布していない場合や、収容局ごとにカバーするエリアの形状が円形でない場合などには適用できない。しかも、このような適用的な状況が、より現実的である。
【０００６】
そこで、本発明は、多数の加入希望者宅と複数の収容局が非一様に分布する場合を前提とし、光ファイバコストに関して好ましい解を提示する光ネットワーク設計支援システム及びプログラムを提示することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係る光ネットワーク設計支援システムは、収容局および加入希望者の位置情報を保存する位置情報データベースと、最大ドロップケーブル長、光スプリッタ分岐数及びクラスタ数初期値を記憶するパラメータ記憶手段と、当該加入希望者を当該クラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定する光スプリッタ位置決定手段であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定手段と、当該光スプリッタ位置決定手段により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続する光スプリッタ／収用局接続手段とを具備することを特徴とする。
【０００８】
本発明に係る光ネットワーク設計支援プログラムは、コンピュータを使い、複数の収用局及び複数の加入希望者に対して、位置情報データベースに記憶される当該収容局および当該加入希望者の位置情報を参照し、最大ドロップケーブル長及び光スプリッタ分岐数の条件の下で、光スプリッタの位置、及び当該光スプリッタを収用する収用局を決定する光ネットワーク設計支援プログラムであって、当該コンピュータに、当該複数の加入希望者をクラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定させる光スプリッタ位置決定機能であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定機能と、当該コンピュータに、当該光スプリッタ位置決定機能により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続させる光スプリッタ／収用局接続機能とを具備することを特徴とする。
【発明の効果】
【０００９】
本発明により、多数の加入希望者宅と複数の収容局が非一様に分布する場合において、加入希望者宅と収容局の位置情報をもとに、光ファイバコストを低減した設計を支援できる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施例の概略構成ブロック図である。
【図２】本実施例のネットワーク設計処理のフローチャートである。
【図３】収用局と加入希望者の分布を示す説明例でる。
【図４】図２のクラスタリング処理の詳細なフローチャートである。
【図５】図３に示す例をクラスタに分割した例である。
【図６】図５に示す分割例で１つのクラスタを更に２つに分割した例である。
【図７】図６に示すクラスタ分割例で、各光スプリッタに近くの加入希望者を接続した状態の説明図である。
【図８】図２に示すフローで、光スプリッタと収用局を接続する処理のフローチャートである。
【図９】図８に示すフローにより光スプリッタと収用局を接続した状態の説明図である。
【図１０】図２のクラスタリング処理の別のフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、本発明の実施例を詳細に説明する。
【実施例１】
【００１２】
図１は、本発明に係る設計支援システムの概略構成ブロック図を示す。コンピュータのＣＰＵ１０に、キーボード等の入力装置１２と、表示装置１４が接続する。ＣＰＵ１０上で、本実施例の設計支援プログラムが動作する。パラメータ記憶装置１６は、ＣＰＵ上の設計支援プログラムに必要な、入力装置１２により入力される各種パラメータを記憶する。パラメータ記憶装置１６は、例えば、コンピュータを構成するＲＡＭ又は二次記憶装置としてのハードディスク装置などからなる。
【００１３】
位置情報データベース（ＤＢ）１８は、ＰＯＮネットワークの設計対象地域に位置するＰＯＮ加入希望者および収容局の、２次元平面上での位置情報を保持する。収容局の位置情報をＣｉ（ｉ＝１〜Ｎ）とし、加入希望者の位置情報をＸｊ（ｊ＝１〜Ｍ）とする。この説明例では、収容局がＮ台あり、加入希望者数がＭであるとする。Ｃｉ（ｉ＝１〜Ｎ）は各収容局を示す場合と、その位置座標を示す場合とがある。同様に、Ｘｊ（ｊ＝１〜Ｍ）は、加入希望者自体を示す場合と、その一座標を示す場合とがある。
【００１４】
最大収容回線数データベース（ＤＢ）２０は、各収容局Ｃｉ（ｉ＝１〜Ｎ）の最大収容回線数Ｎｆｉ（ｉ＝１〜Ｎ）を示す。例えば、Ｃ１の最大収容回線数はＮｆ１である。
【００１５】
データベースとして、収用局の位置情報と最大収用回線数を保持する収用局データベースと、加入希望者に関する位置情報を保持する加入希望者データベースとを有する構成であってもよいことは明らかである。
【００１６】
ＣＰＵ１０は、設計支援プログラムの機能要素として、以下の機能２２〜３０を具備する。図２は、ＣＰＵ１０による設計支援プログラムのメインフローの動作フローチャートを示す。
【００１７】
光スプリッタ配置設計機能２２が、位置情報ＤＢ１８から収容局の位置情報Ｃｉ（ｉ＝１〜Ｎ）と、加入希望者の位置情報Ｘｊ（ｊ＝１〜Ｍ）を読み込む（Ｓ１）。この説明例では、収容局がＮ台あり、加入希望者がＭ人である。図３は、加入希望者と収容局の分布例を示す。図３に示す分布例では、１６人の加入希望者を３つの収用局のどれに接続すべきかを検討し、決定することになる。Ｍ＝１６、Ｎ＝３となる。各収用局には１又は複数のＰＯＮシステムを収容可能であるとする。
【００１８】
オペレータは、入力装置１２を使って、光ネットワーク設計の基本パラメータ、ここでは、最大ドロップケーブル長Ｌｍａｘ、光スプリッタ分岐数Ｎｓ及びクラスタ数（初期値）ＮｃをＣＰＵ１０に入力する（Ｓ２）。もちろん、これらのパラメータの入力（Ｓ２）を、ステップＳ１に先行して実施しておいても良い。最大ドロップケーブル長Ｌｍａｘは、光スプリッタから加入希望者宅までの、許容される最長距離である。光スプリッタ分岐数Ｎｓは１つの光スプリッタに収容できる加入希望者数である。クラスタ数Ｎｃは、ＰＯＮシステム数であり、ここでは、１つのＰＯＮシステムに１つの光スプリッタを想定しているので、光スプリッタ数でもある。クラスタ数Ｎｃは、収容局数又は加入希望者数により、計算途中で増減されることがある。図３に示す例では、収用局の数が３であることから、クラスタ数Ｎｃの初期値を３とする。
【００１９】
次に、クラスタリング処理機能２４を使って、加入希望者をクラスタ数Ｎｃの初期値以上のクラスタ数でクラスタ化し、各クラスタに光スプリッタを割り当てる（Ｓ４）。具体的には、クラスタリング処理機能２４が、ステップＳ１，Ｓ２で設定されパラメータ記憶装置１６に記憶される条件及び初期値に従い、各クラスタ内の加入希望者数がＮｓ以下となり、かつ、ドロップケーブル長が最大長Ｌｍａｘを越えないという条件の下で、全加入希望者をクラスタリングし、光スプリッタ候補の位置を決定する（Ｓ４）。
【００２０】
図４は、クラスタリング処理（Ｓ４）の詳細なフローチャートを示す。メインルーチンから引き渡された対象領域及びクラスタ数Ｎｃに従い、光スプリッタの位置候補となるＮｃ個のセントロイドＹｋ（ｋ＝１〜Ｎｃ）を対象領域内にランダムに設定する（Ｓ１１）。
【００２１】
所定のクラスタリング処理により、対象領域内に存在する全加入希望者をＮｃ個のクラスタに分割する（Ｓ１２）。これは、各クラスタ内で、セントロイドＹｋと当該クラスタに属する加入希望者との間のユークリッド距離の総和が最小となるように、各クラスタへの加入希望者の所属と各セントロイドの位置を決定する処理である。このようなクラスタリング処理法としては、データマイニングの分野において広く用いられているｋ-ｍｅａｎｓ法などがある。このクラスタリング処理で決定した各セントロイドが、光スプリッタの位置候補となる。
【００２２】
図５は、図３に示す例に対し、クラスタリング処理（Ｓ１２）により３つのクラスタに加入希望者を分割した結果を示す。破線がクラスタの境界を示す。黒丸は、セントロイドＹｋ（光スプリッタ候補）である。
【００２３】
各セントロイドＹｋについて、光スプリッタに収容可能な加入希望者数Ｎｓ、及び最大ドロップケーブル長Ｌｍａｘを満たすかどうかを調べる（Ｓ１４，Ｓ１５）。そのために、まず、条件判定対象のクラスタ／セントロイドを指定する変数ｋを１で初期化する（Ｓ１３）。そして、ｋ番目のクラスタに属する加入希望者がＮｓ以下かどうかを調べ（Ｓ１４）、ｋ番目のクラスタ内の加入希望者とセントロイドＹｋとの間の距離が全て、最大ドロップケーブル長Ｌｍａｘ以下であるかどうかを調べる（Ｓ１５）。
【００２４】
何れかの条件（Ｓ１４，Ｓ１５）が満たされない場合、クラスタリング処理機能により、ｋ番目のクラスタを２つのクラスタに分割させる（Ｓ１８）。図６は、図５に示す例で、右下のクラスタにおいて、ステップＳ１４の条件が満たされず、このクラスタを更に２分割した結果を示す。この場合、クラスタ数（又はセントロイド数）は、４になる。ソフトウエアプログラムとしては、ステップＳ１８は、ｋ番目のクラスタを対象領域とし、クラスタ数を２とする引数を、図４に示すクラスタリング処理ルーチン又は関数に渡して再帰的に実行させることで、この目的を実現している。
【００２５】
ｋ番目のクラスタに属する加入希望者がＮｓ以下であり（Ｓ１４）、かつ、ｋ番目のクラスタ内の加入希望者とセントロイドＹｋとの間のユークリッド距離が全て、最大ドロップケーブル長Ｌｍａｘ以下である場合（Ｓ１５）、ｋをインクリメントし（Ｓ１７）、次のクラスタについてステップＳ１４，Ｓ１５の条件を満たすかどうかを確認する。
【００２６】
全クラスタについて、ステップＳ１４，Ｓ１５の条件を満たすことを確認したら、図３に戻り、セントロイドを光スプリッタ位置として確定し、各クラスタ内の加入希望者を同じクラスタ内の光スプリッタに論理接続する（Ｓ５）。この時点で、光スプリッタの配置場所とドロップケーブルの設計が完了する。なお、ｋ-ｍｅａｎｓ法などのクラスタリング手法は局所最適解に収束することが知られている。従って、得られるＰＯＮネットワークの設計結果は、光ファイバ線路長に対する準最適解となる。図７は、図６に示す例における光スプリッタ候補位置（セントロイド）に光スプリッタを配置し、ステップＳ５により、加入希望者を同じクラスタ内の光スプリッタに接続した状態を示す。
【００２７】
収用局決定機能２６が、ステップＳ５で位置が確定した各光スプリッタをどの収用局に接続するかを決定する（Ｓ６）。ステップＳ６の詳細なフローチャートを図８に示す。
【００２８】
収用局決定機能２６は、ボロノイ領域計算機能２８に指示して、Ｎ個の収容局の位置を母点として、設計対象範囲をボロノイ領域に分割させる（Ｓ２１）。ボロノイ領域とは、母点からの距離が、他の母点からの距離よりも短い点の集合を表わす。領域全体を複数のボロノイ領域に区切ったものは、ボロノイ図と呼ばれる。図９は、図７に示す収用局と光スプリッタの配置に対してボロノイ領域への分割を実施した結果であって、破線がボロノイ領域の境界線を示す。ボロノイ図の作図方法としては、逐次添加法や再帰二分法などがある。
【００２９】
収用局決定機能２６は、得られたボロノイ領域の全てについて、以下の処理を実行する。まず、処理対象のボロノイ領域を指定する変数ｋを１で初期化する（Ｓ２２）。収用局決定機能２６は、最大収容回線数ＤＢ２０からｋ番目の収容局の最大収容回線数Ｎｆｋを取得する（Ｓ２３）。ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋ以下か否かを判断する（Ｓ２４）。すなわち、ｋ番目のボロノイ領域内に存在する光スプリッタ数に等しいＰＯＮシステムを、ｋ番目の収用局にまだ収容可能かどうかを調べる。
【００３０】
ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋ以下の場合（Ｓ２４）、ｋ番目のボロノイ領域内に存在する各光スプリッタをｋ番目の収容局に接続する（Ｓ２５）。ｋがＮｃに等しく無ければ（Ｓ２６）、ｋをインクリメントして（Ｓ２７）、Ｓ２３以降を繰り返す。ｋがＮｃに等しくなれば（Ｓ２６）、図８に示す処理を終了する。
【００３１】
ｋ番目のボロノイ領域内に存在する光スプリッタ数とｋ番目の収容局に収用済みの回線数の合計が、Ｎｆｋを越える場合（Ｓ２４）、もはや、ｋ番目のボロノイ領域内に存在する全光スプリッタをｋ番目の収容局に接続することができない。そこで、隣接するボロノイ領域ｊ（但し、j≠ｋ）であって、そのボロノイ領域ｊ内の全光スプリッタ数と、既に接続済みの隣接領域の光スプリッタ数を足してもまだ空きがある収用局を有するものがあるかどうかを調べる（S２８）。すなわち、隣接するボロノイ領域の収用局への接続可能性を調べる。そのような隣接ボロノイ領域ｊ（但し、j≠ｋ）が無い場合（Ｓ２８）、収用局決定機能２６は、表示装置１４に、ＰＯＮネットワークの設計不能を示すエラーメッセージを表示する（Ｓ２９）。
【００３２】
空きのある収用局を有する隣接ボロノイ領域ｊ（但し、j≠ｋ）が存在する場合（Ｓ２８）、ｋ番目のボロノイ領域内の光スプリッタの内で、当該隣接ボロノイ領域ｊ（但し、j≠ｋ）の収用局Ｃｊに最も近い光スプリッタを収用局Ｃｊに接続する（Ｓ３０）。そして、ステップＳ２４以降を繰り返す。これにより、ステップＳ２４で考慮すべき光スプリッタ数が１だけ減る。ステップＳ３０を必要回数だけ繰り返すことで、最終的にステップＳ２４の条件が満たされ、先に説明したように、次のボロノイ領域の処理に移行する（Ｓ２６，Ｓ２７）。
【００３３】
このようにして、ステップＳ５で配置された全光スプリッタを、可能な限り近い収用局に接続できる。これで、図９に示すように、ＰＯＮネットワークの設計が完了する。設計結果出力機能３０は、設計結果を表示装置１４に出力する。もちろん、設計結果を印刷出力するなり、図示しないハードディスクに保存してもよい。
【実施例２】
【００３４】
図４に示すフローでは、クラスタ内で加入希望者数の条件又はドロップケーブル長の条件が満たされないクラスタを再帰処理で２分割するようにしたが、クラスタ数Ｎｃをインクリメントして、全体でクラスタリング処理を再実行してもよい。図１０は、そのように図４を変更したフローチャートを示す。図３のステップＳ１８の代わりに、クラスタ数Ｎｃをインクリメントして（Ｓ１８ａ）、ステップＳ１１以降を再実行する。
【００３５】
この方法では、クラスタリングを仕切り直すことになり、図３に示すフローよりも時間がかかるが、全体を再考することになるので、全体的には全加入希望者の良好な配分を実現できる。
【００３６】
本発明によれば、例えば、多数のＰＯＮ加入希望者宅と複数の収容局が非一様に分布する場合において、加入希望者宅と収容局の位置情報のみをもとに、光ファイバコストに対する準最適解を与えるＰＯＮネットワークを設計できる。これにより、ＰＯＮサービスを展開する通信事業者のＰＯＮネットワーク設計負担を軽減できる。
【００３７】
特定の説明用の実施例を参照して本発明を説明したが、特許請求の範囲に規定される本発明の技術的範囲を逸脱しないで、上述の実施例に種々の変更・修整を施しうることは、本発明の属する分野の技術者にとって自明であり、このような変更・修整も本発明の技術的範囲に含まれる。
【符号の説明】
【００３８】
１０：ＣＰＵ
１２：入力装置
１４：表示装置
１６：パラメータ記憶装置
１８：位置情報データベース（ＤＢ）
２０：最大収容回線数データベース（ＤＢ）
２２：光スプリッタ配置設計機能
２４：クラスタリング処理機能
２６：収用局決定機能
２８：ボロノイ領域計算機能
３０：設計結果出力機能
【特許請求の範囲】
【請求項１】
収容局および加入希望者の位置情報を保存する位置情報データベースと、
最大ドロップケーブル長、光スプリッタ分岐数及びクラスタ数初期値を記憶するパラメータ記憶手段と、
当該加入希望者を当該クラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定する光スプリッタ位置決定手段であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定手段と、
当該光スプリッタ位置決定手段により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続する光スプリッタ／収用局接続手段
とを具備することを特徴とする光ネットワーク設計支援システム。
【請求項２】
当該光スプリッタ位置決定手段が、
当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化する分割手段と、
当該分割手段で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別する判別手段と、
当該第１条件及び第２条件の少なくとも一方を満たさないクラスタに対し当該分割手段及び当該判別手段を実行させる再帰手段と、
当該判別手段において、当該第１条件及び当該第２条件を満たすクラスタの当該セントロイドの位置を当該光スプリッタ位置とする手段
とを具備することを特徴とする請求項１に記載の光ネットワーク設計支援システム。
【請求項３】
当該光スプリッタ位置決定手段が、
当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化する分割手段と、
当該分割手段で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別する判別手段と、
当該第１条件及び第２条件の少なくとも一方を満たさないクラスタが存在する場合に、当該分割手段及び当該判別手段を再実行させる手段と、
全クラスタが当該第１条件及び当該第２条件を満たす場合に、各クラスタの当該セントロイドの位置を当該光スプリッタ位置とする手段
とを具備することを特徴とする請求項１に記載の光ネットワーク設計支援システム。
【請求項４】
当該光スプリッタ／収用局接続手段は、
当該収用局を母点として当該加入希望者を含む領域をボロノイ領域に分割するボロノイ領域分割手段と、
当該ボロノイ領域分割手段で分割された各ボロノイ領域において、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続可能である場合に接続し、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続する空きがない場合に隣接するボロノイ領域の収用局に対して接続可能か調べる接続手段
とを具備することを特徴とする請求項１乃至３の何れか１項に記載の光ネットワーク設計支援システム。
【請求項５】
コンピュータを使い、複数の収用局及び複数の加入希望者に対して、位置情報データベースに記憶される当該収容局および当該加入希望者の位置情報を参照し、最大ドロップケーブル長及び光スプリッタ分岐数の条件の下で、光スプリッタの位置、及び当該光スプリッタを収用する収用局を決定する光ネットワーク設計支援プログラムであって、
当該コンピュータに、当該複数の加入希望者をクラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定させる光スプリッタ位置決定機能であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定機能と、
当該コンピュータに、当該光スプリッタ位置決定機能により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続させる光スプリッタ／収用局接続機能
とを具備することを特徴とする光ネットワーク設計支援プログラム。
【請求項６】
当該光スプリッタ位置決定機能が、
当該コンピュータに、当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化させる分割機能と、
当該コンピュータに、当該分割機能で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別させる判別機能と、
当該コンピュータに、当該第１条件及び第２条件の少なくとも一方を満たさないクラスタに対し当該分割機能及び当該判別機能を実行させる再帰機能と、
当該コンピュータに、当該判別機能において、当該第１条件及び当該第２条件を満たすクラスタの当該セントロイドの位置を当該光スプリッタ位置とさせる機能
とを具備することを特徴とする請求項５に記載の光ネットワーク設計支援プログラム。
【請求項７】
当該光スプリッタ位置決定機能が、
当該コンピュータに、当該クラスタ数初期値に相当する数のセントロイドをランダムに設定させた上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割させ、当該セントロイドを最適化させる分割機能と、
当該コンピュータに、当該分割機能で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別させる判別機能と、
当該コンピュータに、当該第１条件及び第２条件の少なくとも一方を満たさないクラスタが存在する場合に、当該分割機能及び当該判別機能を再実行させる機能と、
当該コンピュータに、全クラスタが当該第１条件及び当該第２条件を満たす場合に、各クラスタの当該セントロイドの位置を当該光スプリッタ位置とさせる機能
とを具備することを特徴とする請求項５に記載の光ネットワーク設計支援プログラム。
【請求項８】
当該光スプリッタ／収用局接続機能は、
当該コンピュータに、当該収用局を母点として当該加入希望者を含む領域をボロノイ領域に分割させるボロノイ領域分割機能と、
当該コンピュータに、当該ボロノイ領域分割機能で分割された各ボロノイ領域において、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続可能である場合には接続させ、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続する空きがない場合には隣接するボロノイ領域の収用局に対して接続可能か調べさせる接続機能
とを具備することを特徴とする請求項５乃至７の何れか１項に記載の光ネットワーク設計支援プログラム。
【請求項１】
収容局および加入希望者の位置情報を保存する位置情報データベースと、
最大ドロップケーブル長、光スプリッタ分岐数及びクラスタ数初期値を記憶するパラメータ記憶手段と、
当該加入希望者を当該クラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定する光スプリッタ位置決定手段であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定手段と、
当該光スプリッタ位置決定手段により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続する光スプリッタ／収用局接続手段
とを具備することを特徴とする光ネットワーク設計支援システム。
【請求項２】
当該光スプリッタ位置決定手段が、
当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化する分割手段と、
当該分割手段で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別する判別手段と、
当該第１条件及び第２条件の少なくとも一方を満たさないクラスタに対し当該分割手段及び当該判別手段を実行させる再帰手段と、
当該判別手段において、当該第１条件及び当該第２条件を満たすクラスタの当該セントロイドの位置を当該光スプリッタ位置とする手段
とを具備することを特徴とする請求項１に記載の光ネットワーク設計支援システム。
【請求項３】
当該光スプリッタ位置決定手段が、
当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化する分割手段と、
当該分割手段で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別する判別手段と、
当該第１条件及び第２条件の少なくとも一方を満たさないクラスタが存在する場合に、当該分割手段及び当該判別手段を再実行させる手段と、
全クラスタが当該第１条件及び当該第２条件を満たす場合に、各クラスタの当該セントロイドの位置を当該光スプリッタ位置とする手段
とを具備することを特徴とする請求項１に記載の光ネットワーク設計支援システム。
【請求項４】
当該光スプリッタ／収用局接続手段は、
当該収用局を母点として当該加入希望者を含む領域をボロノイ領域に分割するボロノイ領域分割手段と、
当該ボロノイ領域分割手段で分割された各ボロノイ領域において、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続可能である場合に接続し、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続する空きがない場合に隣接するボロノイ領域の収用局に対して接続可能か調べる接続手段
とを具備することを特徴とする請求項１乃至３の何れか１項に記載の光ネットワーク設計支援システム。
【請求項５】
コンピュータを使い、複数の収用局及び複数の加入希望者に対して、位置情報データベースに記憶される当該収容局および当該加入希望者の位置情報を参照し、最大ドロップケーブル長及び光スプリッタ分岐数の条件の下で、光スプリッタの位置、及び当該光スプリッタを収用する収用局を決定する光ネットワーク設計支援プログラムであって、
当該コンピュータに、当該複数の加入希望者をクラスタ数初期値以上のクラスタに分割し、各クラスタ内での光スプリッタ位置を決定させる光スプリッタ位置決定機能であって、各クラスタ内の加入希望者数が当該光スプリッタ分岐数以下であり、各クラスタ内の光スプリッタ候補位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下であるように各クラスタ内の当該光スプリッタ位置を決定する光スプリッタ位置決定機能と、
当該コンピュータに、当該光スプリッタ位置決定機能により決定された当該各光スプリッタ位置の光スプリッタを当該収用局の何れかに接続させる光スプリッタ／収用局接続機能
とを具備することを特徴とする光ネットワーク設計支援プログラム。
【請求項６】
当該光スプリッタ位置決定機能が、
当該コンピュータに、当該クラスタ数初期値に相当する数のセントロイドをランダムに設定した上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割し、当該セントロイドを最適化させる分割機能と、
当該コンピュータに、当該分割機能で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別させる判別機能と、
当該コンピュータに、当該第１条件及び第２条件の少なくとも一方を満たさないクラスタに対し当該分割機能及び当該判別機能を実行させる再帰機能と、
当該コンピュータに、当該判別機能において、当該第１条件及び当該第２条件を満たすクラスタの当該セントロイドの位置を当該光スプリッタ位置とさせる機能
とを具備することを特徴とする請求項５に記載の光ネットワーク設計支援プログラム。
【請求項７】
当該光スプリッタ位置決定機能が、
当該コンピュータに、当該クラスタ数初期値に相当する数のセントロイドをランダムに設定させた上で、全加入希望者を当該クラスタ数初期値に相当する数のクラスタに分割させ、当該セントロイドを最適化させる分割機能と、
当該コンピュータに、当該分割機能で生成される各クラスタに対して、クラスタ内の加入希望者数が当該光スプリッタ分岐数以下である第１条件、及び各クラスタ内の当該セントロイドの位置から同じクラスタ内の加入希望者までの距離が当該最大ドロップケーブル長以下である第２条件を満たすかどうかを判別させる判別機能と、
当該コンピュータに、当該第１条件及び第２条件の少なくとも一方を満たさないクラスタが存在する場合に、当該分割機能及び当該判別機能を再実行させる機能と、
当該コンピュータに、全クラスタが当該第１条件及び当該第２条件を満たす場合に、各クラスタの当該セントロイドの位置を当該光スプリッタ位置とさせる機能
とを具備することを特徴とする請求項５に記載の光ネットワーク設計支援プログラム。
【請求項８】
当該光スプリッタ／収用局接続機能は、
当該コンピュータに、当該収用局を母点として当該加入希望者を含む領域をボロノイ領域に分割させるボロノイ領域分割機能と、
当該コンピュータに、当該ボロノイ領域分割機能で分割された各ボロノイ領域において、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続可能である場合には接続させ、当該ボロノイ領域内の収用局に同じボロノイ領域内の光スプリッタを接続する空きがない場合には隣接するボロノイ領域の収用局に対して接続可能か調べさせる接続機能
とを具備することを特徴とする請求項５乃至７の何れか１項に記載の光ネットワーク設計支援プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−２０４７８０（Ｐ２０１０−２０４７８０Ａ）
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願番号】特願２００９−４７５３１（Ｐ２００９−４７５３１）
【出願日】平成２１年３月２日（２００９．３．２）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願日】平成２１年３月２日（２００９．３．２）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]