(57)【要約】【課題】コスト制約を満たしつつ、通信の信頼度を最大化するネットワークを設計することができる。【解決手段】最適化計算部が、構築された二分決定グラフと、追加に必要な各辺の各々のコストと、各辺の各々の動作確率と、コストの上限Ｃとに基づいて、二分決定グラフのノードｂｉとコストｓの組み合わせの各々に対し、ノードｂｉに対応し、かつ、コストの合計がコストｓ以下となるように追加する辺の組み合わせを選択したときの信頼度の上限を表す値を格納したインデックスを計算し、コストに関する予め定められた制約を満たすようにネットワークに追加する辺の組み合わせを選択する。【選択図】図２
2019114877.tif 000002
【特許請求の範囲】
【請求項１】
複数の機器を通信リンクで接続する通信ネットワークを設計するネットワーク設計装置であって、
複数の機器の各々を頂点とし、前記通信ネットワークに追加可能な通信リンクの各々を辺として前記通信ネットワークをグラフで表現するものとして、
前記頂点の集合と、前記辺の集合と、頂点集合の部分集合である端点の集合とに基づいて、前記通信ネットワークがとりうる故障パターンの集合を表現した二分決定グラフを構築するＢＤＤ構築部と、
前記二分決定グラフの終端ノードのうち、一部の辺が故障しても前記端点に対応する機器の各々が通信ネットワークにより通信可能であるようなネットワーク構造に対応する経路の終端ノードを第１終端ノードとして、
前記二分決定グラフと、予め定められた前記辺の集合に含まれる各辺のコストと、予め定められた前記辺の集合に含まれる各辺の動作確率とに基づいて、前記二分決定グラフのノードｂｉ（ｉ＝１，・・・，Ｂ、ただしＢは前記二分決定グラフのノードの総数）と取りうるコストｓ（ｓ＝０,１，・・・，Ｃ、ただしＣはコストの上限）の組み合わせの各々に対し、前記二分決定グラフの第一終端ノードからノードｂｉに至る経路のうち、当該経路に対応する通信ネットワークのコストの合計がコストｓ以下となるように経路を選択したときの当該経路に対応する通信ネットワークの信頼度の上限を表す値を当該ｂｉとｓの組に対応するインデックスとして計算するインデックス計算部と、
前記インデックスと、前記各辺のコストと、前記各辺の動作確率と、コストの上限Ｃとに基づいて、前記選択する前記辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たす辺の組み合わせのうち、前記信頼度が最大となる辺の組み合わせを探索する最適化計算部と、
を含むネットワーク設計装置。
【請求項２】
前記最適化計算部は、前記辺の集合に含まれる先頭の辺から順に、各辺を追加するか否かを決定することにより前記辺の組み合わせを求める探索手段を含み、
前記辺の組み合わせの候補毎に、当該組み合わせに対応する通信ネットワークの信頼度を対応付けて記憶した記憶部をさらに備える
ことを特徴とする請求項１に記載のネットワーク設計装置。
【請求項３】
複数の機器を通信リンクで接続する通信ネットワークを設計するネットワーク設計装置におけるネットワーク設計方法であって、
ＢＤＤ構築部が、複数の機器の各々を頂点とし、前記通信ネットワークに追加可能な通信リンクの各々を辺として前記通信ネットワークをグラフで表現するものとして、前記頂点の集合と、前記辺の集合と、頂点集合の部分集合である端点の集合とに基づいて、前記通信ネットワークがとりうる故障パターンの集合を表現した二分決定グラフを構築するステップと、
インデックス計算部が、前記二分決定グラフの終端ノードのうち、一部の辺が故障しても前記端点に対応する機器の各々が通信ネットワークにより通信可能であるようなネットワーク構造に対応する経路の終端ノードを第１終端ノードとして、前記二分決定グラフと、予め定められた前記辺の集合に含まれる各辺のコストと、予め定められた前記辺の集合に含まれる各辺の動作確率とに基づいて、前記二分決定グラフのノードｂｉ（ｉ＝１，・・・，Ｂ、ただしＢは前記二分決定グラフのノードの総数）とコストｓ（ｓ＝０,１，・・・，Ｃ、ただしＣはコストの上限）の組み合わせの各々に対し、前記二分決定グラフの第一終端ノードからノードｂｉに至る経路のうち、当該経路に対応する通信ネットワークのコストの合計がコストｓ以下となるように経路を選択したときの当該経路に対応する通信ネットワークの信頼度の上限を表す値を当該ｂｉとｓの組に対応するインデックスとして計算するステップと、
最適化計算部が、前記インデックスと、前記各辺のコストと、前記各辺の動作確率と、コストの上限Ｃとに基づいて、前記選択する前記辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たす辺の組み合わせのうち、前記信頼度が最大となる辺の組み合わせを探索するステップと、
を含むネットワーク設計方法。
【請求項４】
コンピュータを、請求項１又は請求項２に記載のネットワーク設計装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク設計装置、方法、及びプログラムに係り、特に、コスト制約を満たしつつ通信ネットワーク信頼性を最大とするネットワークを設計するネットワーク設計装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
通信ネットワークの信頼性とは、通信ネットワーク（以下、単にネットワークと記載する場合もある）を構成する構成要素の故障に対して、どれだけネットワークが頑健であるかを示す指標である。より具体的には、ネットワークの構成要素がある確率分布に従って故障するとしたときに、ネットワークを用いた通信が行える確率として定義される。信頼性が高いネットワークを設計することは重要である。複数の機器を通信リンクで接続するネットワークにおいて、複数の機器の各々を頂点とし、ネットワークに追加可能な通信リンクの各々を辺としてネットワークをグラフで表現するものとして、グラフを構築し、グラフに対する操作を行って信頼性の高い通信ネットワークを設計する技術がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Li, X. Sun, and K. McKinnon, "An exact solution method for reliability optimization in complex systems", Annals of Operations Research,vol.133, no. 1, pp.129-148, 2005
【非特許文献２】G. Hardy, C. Lucet, and N. Limnios "K-terminal network reliability measures with binary decision diagrams", IEEE Trans. reliability, Vol.56, No.3,p.506-515, 2007
【発明の概要】
【発明が解決しようとする課題】
【０００４】
各通信リンクに対応する辺を、ネットワークに対応するグラフに追加するために必要なコストが与えられている場合に、構築コストがある基準値を下回るという制約のもとで、構築されるネットワークの信頼性が最大となるようなネットワークを設計する問題は、組合せ最適化問題として定式化して解くことができることが知られている（非特許文献１）。しかしながら、解を求めるのが非常に難しい組合せ最適化問題となるため、既存手法では非常に小規模なネットワークの設計においてしか最適解を求めることができなかった。そのため、最適解を求めることができない規模のネットワークの設計においては性能についての保証のない近似解法に頼らざるを得なかった。
【０００５】
本発明は、上記問題点を解決するために成されたものであり、コスト制約を満たしつつ、通信の信頼度を最大化するネットワークを設計することができるネットワーク設計装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明に係るネットワーク設計装置は、複数の機器を通信リンクで接続する通信ネットワークを設計するネットワーク設計装置であって、複数の機器の各々を頂点とし、前記通信ネットワークに追加可能な通信リンクの各々を辺として前記通信ネットワークをグラフで表現するものとして、前記頂点の集合と、前記辺の集合と、頂点集合の部分集合である端点の集合とに基づいて、前記通信ネットワークがとりうる故障パターンの集合を表現した二分決定グラフを構築するＢＤＤ構築部と、前記二分決定グラフの終端ノードのうち、一部の辺が故障しても前記端点に対応する機器の各々が通信ネットワークにより通信可能であるようなネットワーク構造に対応する経路の終端ノードを第１終端ノードとして、前記二分決定グラフと、予め定められた前記辺の集合に含まれる各辺のコストと、予め定められた前記辺の集合に含まれる各辺の動作確率とに基づいて、前記二分決定グラフのノードｂｉ（ｉ＝１，・・・，Ｂ、ただしＢは前記二分決定グラフのノードの総数）と取りうるコストｓ（ｓ＝０,１，・・・，Ｃ、ただしＣはコストの上限）の組み合わせの各々に対し、前記二分決定グラフの第一終端ノードからノードｂｉに至る経路のうち、当該経路に対応する通信ネットワークのコストの合計がコストｓ以下となるように経路を選択したときの当該経路に対応する通信ネットワークの信頼度の上限を表す値を当該ｂｉとｓの組に対応するインデックスとして計算するインデックス計算部と、前記インデックスと、前記各辺のコストと、前記各辺の動作確率と、コストの上限Ｃとに基づいて、前記選択する前記辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たす辺の組み合わせのうち、前記信頼度が最大となる辺の組み合わせを探索する最適化計算部と、を含んで構成されている。
【０００７】
本発明に係るネットワーク設計方法は、複数の機器を通信リンクで接続する通信ネットワークを設計するネットワーク設計装置におけるネットワーク設計方法であって、ＢＤＤ構築部が、複数の機器の各々を頂点とし、前記通信ネットワークに追加可能な通信リンクの各々を辺として前記通信ネットワークをグラフで表現するものとして、前記頂点の集合と、前記辺の集合と、頂点集合の部分集合である端点の集合とに基づいて、前記通信ネットワークがとりうる故障パターンの集合を表現した二分決定グラフを構築するステップと、インデックス計算部が、前記二分決定グラフの終端ノードのうち、一部の辺が故障しても前記端点に対応する機器の各々が通信ネットワークにより通信可能であるようなネットワーク構造に対応する経路の終端ノードを第１終端ノードとして、前記二分決定グラフと、予め定められた前記辺の集合に含まれる各辺のコストと、予め定められた前記辺の集合に含まれる各辺の動作確率とに基づいて、前記二分決定グラフのノードｂｉ（ｉ＝１，・・・，Ｂ、ただしＢは前記二分決定グラフのノードの総数）とコストｓ（ｓ＝０,１，・・・，Ｃ、ただしＣはコストの上限）の組み合わせの各々に対し、前記二分決定グラフの第一終端ノードからノードｂｉに至る経路のうち、当該経路に対応する通信ネットワークのコストの合計がコストｓ以下となるように経路を選択したときの当該経路に対応する通信ネットワークの信頼度の上限を表す値を当該ｂｉとｓの組に対応するインデックスとして計算するステップと、最適化計算部が、前記インデックスと、前記各辺のコストと、前記各辺の動作確率と、コストの上限Ｃとに基づいて、前記選択する前記辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たす辺の組み合わせのうち、前記信頼度が最大となる辺の組み合わせを探索するステップと、を含んで実行することを特徴とする。
【０００８】
本発明に係るプログラムは、コンピュータを、上記ネットワーク設計装置の各部として機能させるためのプログラムである。
【発明の効果】
【０００９】
本発明のネットワーク設計装置、方法、及びプログラムによれば、コスト制約を満たしつつ、通信の信頼度を最大化するすネットワークを設計することができる、という効果が得られる。
【図面の簡単な説明】
【００１０】
【図１】ＢＤＤの一例を示す図である。
【図２】本発明の実施の形態に係るネットワーク設計装置の構成を示すブロック図である。
【図３】インデックス構築処理の詳細を示す図である。
【図４】最適化処理の詳細を示す図である。
【図５】関数評価処理フローを示す図である。
【図６】前向き計算フローを示す図である。
【図７】本発明の実施の形態に係るネットワーク設計装置におけるネットワーク設計処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１２】
＜本発明の実施の形態に係る概要＞
【００１３】
二分決定グラフ(Binary Decision Diagram, ＢＤＤ)とよばれるデータ構造を用いて、ネットワークが動作可能な全ての故障パターンの集合を表現する。さらに、そのＢＤＤ上でＡ＊探索アルゴリズムを実行することで、規模の大きなネットワークの設計においても効率的に最適解を発見することを可能とする。
【００１４】
＜本発明の実施の形態に係る原理＞
【００１５】
ここで、本発明の実施の形態における原理を説明する。
【００１６】
まず以下で用いる記号を導入する。通信ネットワークはグラフＧ＝（Ｖ；Ｅ）で与えられるとする。ここでＶは頂点の集合、Ｅは辺の集合である。辺の総数をＭとする。Ｅの部分集合Ｆが与えられたとき、Ｅによって導出される誘導部分グラフをＧ［Ｆ］とあらわす。Ｖの部分集合Ｔ⊆Ｖを端点とよぶ。各辺をｅ１,...,ｅＭとする。辺ｅｉは確率ｐｉで動作し、確率１−ｐｉで故障するとする（以下、ｐｉを辺ｅｉの動作確率という）。二値変数ｙｉ∈｛０,１｝を用いて、辺ｅｉが動作しているかどうかを表す。すなわち、ｙｉ＝１ならばｅｉは動作しているとし、ｙｉ＝０ならば故障しているとする。ネットワークの信頼度は以下（１）式として計算できる。
【００１７】
【数１】
2019114877.tif 000003
・・・（１）
【００１８】
ここで、ｙは各要素が０または１の何れかの値をとるＭ次元ベクトルであり、｛０，１｝Ｍは、各要素が０または１の何れかの値をとるＭ次元ベクトルの集合である。ここでＩ（ｙ）は、ｙによって表現される故障していない辺の集合（ｙi＝１であるｙiに対応する辺ｅiの集合）によって、端点Ｔに含まれるすべての頂点が接続されているならば１、そうでないならば０を返す関数である。
【００１９】
ネットワークの設計問題は以下のように定義される。
【００２０】
【数２】
2019114877.tif 000004
・・・（２）
2019114877.tif 000005
・・・（３）
【００２１】
ここでｃｉは辺ｅｉを通信ネットワークに追加するためにかかるコスト、Ｃはコストの上限である。すなわち、信頼性を最大化する問題とは、ネットワークに追加できる辺の候補の集合Ｅから、コストの総和が上限値Ｃを超えない範囲で辺を選択して追加することで、得られたネットワークＧ［Ｅ′］の信頼性を最大化する問題である。ここで、ｅｉ∈Ｅ′ならばｘｉ＝１、
【００２２】
【数３】
2019114877.tif 000006
ならばｘｉ＝０であるような二値変数ｘ１,...,ｘＭを導入すると、上記の最適化問題は以下（４）式のように書くことができる。
【００２３】
【数４】
2019114877.tif 000007
・・・（４）
【００２４】
ここでｘ＝（ｘ１,...,ｘＭ）である。つまり、ｘiは辺ｅｉを通信ネットワークに追加するか否かを示す変数である。Ｒ（ｘ）は信頼度をｘの関数として定義したものであり、以下（５）式のように定義される。
【００２５】
【数５】
2019114877.tif 000008
・・・（５）
【００２６】
ＢＤＤは論理関数を有向非巡回グラフとして表現するデータ構造である。論理関数（ｘ１∧ｘ２）∨（ｘ１∧ｘ３）∨（ｘ２∧ｘ３）を表現するＢＤＤの例を図１に示す。ＢＤＤは終端ノードと分岐ノードの２種類のノードをもつ。ＢＤＤにおいて、ノードとノードとを繋ぐ線を「アーク」または「枝」と呼ぶ。終端ノードはそのノードを始点とするアークを持たないノードであり、図１中では四角で表現される。
【００２７】
【数６】
2019114877.tif 000009
終端ノード（以下「第２終端ノード」という）と
【数７】
2019114877.tif 000010
終端ノード（以下「第１終端ノード」という）の２種類の終端ノードがあり、一つのＢＤＤには各終端ノードは高々一つずつ存在する。分岐ノードは終端ノードではないノードのことである。各分岐ノードには、そのノードを始点とするアークが必ず２つ存在し、それぞれｌｏ枝、ｈｉ枝とよばれる。また、各分岐ノードには論理関数の引数が１つラベルとして対応付けられる。図１中では各分岐ノードは円として表現され、ｈｉ枝は実線、ｌｏ枝は点線によって表現される。図１中のノードｂ１は分岐ノードであり、要素ｘ１がラベルとして付与され、ｌｏ枝はｂ２を、ｈｉ枝はｂ３を指している。ＢＤＤ中では親をもたないノードが必ず１つのみ存在し、根ノードとよばれる。
【００２８】
根ノードから第１終端ノードまでの各経路が、ＢＤＤが表現する論理関数を真とするような変数の割り当てに対応している。
【００２９】
図１のＢＤＤでは根ノードｂ１から第１終端ノードに至る３種類の経路が存在する。図１のＢＤＤが３引数の論理関数を表しているため３つの変数で経路が表現できるものとしている。もしＢＤＤが表す関数の引数がＮ個であれば、Ｎ個の変数の０,１で経路が表現される。
【００３０】
経路を３つの変数（ｘ１,ｘ２,ｘ３）で表すものとし、ｘｉをノードラベルｉのノードにおいて枝ｌｏ枝とｈｉ枝のどちらを辿るかを示す変数とすると、根ノードｂ１から第１終端ノードに至る３種類の経路は（１,１,＊）,（１,０,１）,（０,１,１）と表現できる。なお＊はｘ３に対応するノードが経路中に出現しないことを示す。各経路がそれぞれ真となる変数の割当に対応する。なお、経路中に対応するノードが出現しなかった変数については、その変数に０もしくは１のどちらを割り当てても真となる。図１のＢＤＤの例では、経路（１,１,＊）は、(１,１,０),(１,１,１)の二種類の変数に対する値の割当を示している。したがって、（１,１,０）,(１,１,１),（１,０,１）,（０,１,１）が、ＢＤＤが表現する論理関数を真とするような変数の割り当てである。
【００３１】
なお、以下ではＢＤＤのノードはＢ個存在するとし、各ノードをｂ１,...,ｂＢとあらわす。なお、ｂ１は根ノードに対応し、ｂｊ,ｂｋについてｊ＜ｋならばｂｊはｂｋの子になりえないとする。なお、ｂＢは第１終端ノード、ｂＢ-1は第２終端ノードであるとする。また、Ｄｉを高さｉでのカットノードの添字の集合とし、ＢＤＤノードのうち、ラベルが１,...,ｉ−１のいずれかではなく、かつ１,...,ｉ−１のいずれかをラベルとするような親ノードをもつものの添字の集合とする。
【００３２】
ＢＤＤは、各ノードについて、（ノードのＩＤ、ラベル、ｈｉ枝の指すノード、ｌｏ枝の指すノード）の４つ組を用意することで表現できる。例のＢＤＤは６つのノードをもつため、［（ｂ１,１,ｂ３,ｂ２）,（ｂ２,２,ｂ４,ｂ５）,（ｂ３,２,ｂ６,ｂ４）,（ｂ４,３,ｂ６,ｂ５）,（ｂ５,
【数９】
2019114877.tif 000011
,−,−）,（ｂ６,
【数１０】
2019114877.tif 000012
,−,−）］というテーブルを用意することで表現することができる。
【００３３】
本発明では、通信ネットワークに対応するグラフ（以下「入力グラフ」と呼ぶ）からＢＤＤを構築する。
【００３４】
入力グラフでは、通信ネットワークを構成する通信機器が各頂点に対応し、各通信機器間の通信リンクが辺に対応する。
【００３５】
構築されるＢＤＤは、各ノードが入力グラフの各辺に対応するラベルを持つ。そして、入力グラフのある部分構造（部分グラフ）が辺ｅi（ｉ＝１,・・・,Ｍ）を含む場合には当該ｉをラベルとするノードからｈｉ枝を辿り、辺ｅiを含まない場合には当該ｉをラベルとするノードからｌｏ枝を辿る。よって、根ノードから終端ノードまでの各経路は、それぞれ入力グラフの部分構造に対応する。
【００３６】
「ＢＤＤが表現する論理関数を真とするような変数の割り当て」の各々は、入力グラフの部分構造に対応する。この部分構造は、通信ネットワークにおいて故障したリンクを取り除いて得られるネットワークに対応したグラフを表現している。故障しているリンクを取り除いて得られた通信ネットワークにおいて全ての端点間において通信が可能となったときに、論理関数が真となる。
【００３７】
＜本発明の実施の形態に係るネットワーク設計装置の構成＞
【００３８】
次に、本発明の実施の形態に係るネットワーク設計装置の構成について説明する。図２に示すように、本発明の実施の形態に係るネットワーク設計装置１００は、ＣＰＵと、ＲＡＭと、後述するネットワーク設計処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このネットワーク設計装置１００は、機能的には図２に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００３９】
入力部１０は、入力として、通信ネットワークに対応するグラフの頂点集合Ｖ＝｛ｖ１，ｖ２，・・・，ｖＮ｝（Ｎは頂点の総数）、端点の集合Ｔ⊆Ｖ、通信ネットワークに追加できる辺の集合Ｅ＝｛ｅ１，ｅ２，・・・，ｅＭ｝（Ｍは辺の総数）、各辺のコストｃ１,...,ｃＭ（ｃｉは辺ｅiのコスト）、各辺の動作確率ｐ１,...,ｐＭ（ｐiは辺ｅiの動作確率）、コスト上限Ｃを入力として受け取る。ここで、辺ｅiのコストとは、通信ネットワークに辺ｅiに対応する通信リンクを追加するのに要するコストを表す。
【００４０】
演算部２０は、ＢＤＤ構築部３０と、インデックス計算部３２と、最適化計算部３４と、記憶部４０とを含んで構成されている。
【００４１】
ＢＤＤ構築部３０は、入力部１０で受け付けた、ネットワークの頂点集合Ｖと、ネットワークに追加できる辺の集合Ｅと、頂点集合Ｖのうちの端点の集合Ｔとに基づいて、グラフＧ＝（Ｖ,Ｅ）において、全ての端点が接続される辺の組み合わせである故障パターンの集合を表現した二分決定グラフ(ＢＤＤ)を構築する。
【００４２】
結果としてＢＤＤの各経路は、集合Ｖに含まれる頂点からなるグラフであって、当該経路により特定される辺で頂点を接続したグラフである。つまり、ＢＤＤの各経路は、Ｇ＝（Ｖ；Ｅ）に対応するグラフのうち、一部または全部の辺が欠けているグラフに対応する。欠けている辺は、通信ネットワークにおいて故障している通信リンクを表すので、例えば、辺ｅｉが欠けているグラフは、辺ｅｉに対応する通信リンクが故障しているような故障パターンに対応する。すなわち、ＢＤＤの経路の集合は、グラフＧに対応する通信ネットワークにおいて取りうるすべての故障パターンの集合を表すものとなる。
【００４３】
そして、根ノードから第１終端ノードに至る各経路が、一部の辺が欠けた（通信リンクが故障した）としても、全ての端点がネットワークによる通信が可能である故障パターンに対応する。根ノードから第１終端ノードに至る経路の集合は、全ての端点がネットワークによる通信が可能であるようなすべての故障パターンの集合をあらわす。
【００４４】
なお、ＢＤＤの構築は、上記非特許文献２に記載されている方法を用いることにより行う。
【００４５】
インデックス計算部３２は、ＢＤＤ構築部３０にて構築されたＢＤＤと、追加に必要な各辺の各々のコストｃ１,...,ｃＭと、各辺の各々の動作確率ｐ１,...,ｐＭとに基づいて、ＢＤＤのノードｂｉと終端ノードからノードｂｉまでの部分構造に対応する通信ネットワークにおけるコスト（ｓ＝０，１，２，・・・，Ｃ）の組み合わせの各々に対し、インデックスを計算する。ここで、ｂｉとｓの組に対応するインデックスは、終端ノードからノードｂｉに至る経路の各々に対応するグラフのうち、コストがｓ以下となるような辺の組み合わせを選択したときの、当該辺の組み合わせに対応する通信ネットワークの信頼度の上限値である。インデックス計算部３２の処理の詳細については後述する。
【００４６】
最適化計算部３４は、インデックス計算部３２で計算されたインデックスと、各辺のコストｃ１,...,ｃＭと、各辺の各々の動作確率ｐ１,...,ｐＭと、コストの上限Ｃとに基づいて、上記（４）式で表されるコストに関する所定の制約を満たすような辺の組み合わせを選択することにより、ネットワークを設計する。具体的には、最適化計算部３４は、選択する辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たし、かつ、信頼度が最大となるように、辺の組み合わせを選択し、その組み合わせの信頼度を最大化するようなネットワークの構成を特定する情報として出力部５０により出力する。
【００４７】
記憶部４０には、最適化計算部３４において辺の組み合わせの候補毎に計算される、当該組み合わせに対応する通信ネットワークの最大の信頼度（信頼度の上限）の推定値が対応付けられて記憶される。
【００４８】
次に、インデックス計算部３２のインデックス構築処理の詳細について、図３を用いて説明する。インデックス計算部３２では、入力として、ＢＤＤ構築部３０で構築されたＢＤＤ、コストの最大値Ｃ、辺の動作確率ｐ１,...,ｐＭ、辺のコストｃ１,...,ｃＭを受け取り、インデックスＡを計算する。インデックスＡはＢ×（Ｃ＋１）個の要素からなるテーブルであり、テーブルのｊ行ｓ列目の要素をＡ［ｉ］［ｓ］とする。Ａ［ｉ］［ｓ］は、ＢＤＤの終端ノードからノードｂｉまでの経路の各々に対応するグラフのうち、コストがｓ以下となるように辺を選択したときの、信頼度の推定値（上限値）を保持している。なお、ＢＤＤのｉ番目のノードにラベルとして対応づけられているネットワークの辺をｅｋとする。
【００４９】
図３の処理では、まず各ｉ＝１,...,Ｂ、ｓ＝０,１，...,Ｃに対して、Ａ［ｉ］［ｓ］に値０を設定してインデックスを初期化する。次にすべてのｓ＝０,１，...,ＣについてＡ［Ｂ］［ｓ］←１.０に設定する。以降では、全てのｉ,ｓの組合せについてＡ［ｉ］［ｓ］の値を再帰的に計算する。
【００５０】
次に最適化計算部３４の最適化処理の詳細について、図４を用いて説明する。なお、以下ではｘのｉ番目以下（つまり、ｘ１，ｘ２，・・・，ｘi）の要素にのみ値を割り当てた部分ベクトルをｘ≦ｉとして表現する。また、ｘ≦iにおける各要素の取りうる値の組み合わせの各々を「状態」と呼ぶ。例えば、ｘ≦２であれば、（０，０），（０，１），（１，０），（１，１）の各々が「状態」である。
【００５１】
最適化計算部３４は、図４のステップ１で状態の集合を格納するリストＯｐｅｎを初期化する。ステップ２で初期状態をＯｐｅｎに追加する。次に、Ｏｐｅｎが空でない限り、スコアを最大とする状態ｘ≦ｊを一つ選択する（ステップ３，４）。ここで、各状態におけるスコアとは、部分ベクトルｘ≦ｊの各要素の値が当該状態であるとしたときの通信ネットワークの信頼度の推定値である。詳しくは後述する。もしその状態ｘ≦ｊに対応する部分ベクトルの大きさがＭであったならば、それを解として出力して処理を終了する（ステップ６）。ここで、部分ベクトルの大きさとは、部分ベクトルの要素数であり、ｘ≦ｊの大きさはｊである。そうでないならば、ｘ≦ｊのｊ＋１番目の要素を１に設定した新しいベクトルｘ≦ｊ＋１（１）と、ｊ＋１番目の要素を０に設定した新しいベクトルｘ≦ｊ＋１（０）を作成する。それぞれについてスコアを計算してＯｐｅｎに追加する（ステップ８〜１３）。
【００５２】
上記の手順を繰り返し、ステップ３,４でOpenから取り出したスコア最大の部分ベクトルｘ≦ｊの大きさがＭであったときに処理を終了する。各ｘｊは０または１の何れかの値をとり、ｘｊ＝１であれば通信ネットワークに辺ｅｊを追加することを意味する。よって、ｘ≦Ｍのうちｘｊ＝１となる辺ｅｊが、通信ネットワークに追加する辺となる。
【００５３】
すなわち、最適化計算部３４は、辺の組み合わせ方の候補（ｘ≦ｊのうちｘi＝１となる辺ｅiの組み合わせ）を、その組合せ方に対する最大信頼度の推定値とともにOpenに格納し、信頼度の推定値が大きいものから順番に展開・伸張させていく最良優先探索を実行することにより、通信ネットワークに追加する辺の組み合わせを選択する。このように、最良優先探索を実行し、通信ネットワークに追加する辺の組み合わせを選択する処理が、探索手段による処理（辺の集合に含まれる先頭の辺から順に、各辺を追加するか否かを決定することにより辺の組み合わせを求める処理）の一例である。また、Openへの格納が、記憶部４０に、辺の組み合わせの候補毎に、当該組み合わせに対応する通信ネットワークの信頼度が対応付けて記憶されることの一例である。
【００５４】
図４ステップ１０、１３のスコアの計算について、図５の関数評価処理フローを用いて説明する。
【００５５】
まず図５のステップ１、２で部分ベクトルｘ≦ｊに対応するコストの和ｓを計算し、辺動作確率ｐ′jを設定する。次に、ステップ３で、図６の前向き計算フローの処理を用いて、カットノード集合Ｄｊに相当する配列Ｆｊ［ｉ］の値を求める。その後、ステップ４で、インデックスＡの値とＦｊ［ｉ］の値を用いて信頼度のスコアを算出する。
【００５６】
＜本発明の実施の形態に係るネットワーク設計装置の作用＞
【００５７】
次に、本発明の実施の形態に係るネットワーク設計装置１００の作用について説明する。入力部１０において通信ネットワークの頂点集合Ｖ、端点の集合Ｔ⊆Ｖ、ネットワークに追加できる辺の集合Ｅ、各辺を追加するのに必要なコストｃ１,...,ｃＭ、各辺の動作確率ｐ１,...,ｐＭ、コスト合計の上限値Ｃを受け付けると、ネットワーク設計装置１００は、図７に示すネットワーク設計処理ルーチンを実行する。
【００５８】
まず、ステップＳ１００では、入力部１０で受け付けた、ネットワークの頂点集合Ｖと、ネットワークに追加できる辺の集合Ｅと、頂点集合Ｖのうちの端点の集合Ｔとに基づいて、グラフＧ＝（Ｖ,Ｅ）において、全ての端点が接続される辺の組み合わせである故障パターンの集合を表現したＢＤＤを構築する。
【００５９】
次に、ステップＳ１０２では、ステップＳ１００で構築されたＢＤＤと、グラフＧに各辺を追加する際に必要なコストｃ１,...,ｃＭと、各辺の各々の動作確率ｐ１,...,ｐＭとに基づいて、上記図３に示すアルゴリズムに従って、ＢＤＤのノードｂｉとコストｓの組み合わせの各々に対し、ノードｂｉに対応し、かつ、コストの合計がコストｓ以下となるように追加する辺の組み合わせを選択したときの信頼度の上限を表す値を格納したインデックスを計算する。
【００６０】
ステップＳ１０４では、ステップＳ１０２で計算されたインデックスと、各辺の追加に必要なコストｃ１,...,ｃＭと、各辺の各々の動作確率ｐ１,...,ｐＭと、コストの上限Ｃとに基づいて、選択する辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たし、かつ、信頼度が最大となるように、ネットワークに追加する辺の組み合わせを選択する。ここでは、上記図４に示すアルゴリズムに従って最良優先探索を行い、ネットワークに追加する辺の組み合わせを選択することにより、ネットワークを設計する。
【００６１】
ステップＳ１０６では、ステップＳ１０４で設計された信頼度を最大化するようなネットワークの構成を出力部５０により出力し、処理を終了する。
【００６２】
以上説明したように、本発明の実施の形態に係るネットワーク設計装置によれば、構築されたＢＤＤと、各辺の追加に必要なコストと、各辺の各々の動作確率とに基づいて、ＢＤＤのノードｂｉとコストｓの組み合わせの各々に対し、ノードｂｉに対応し、かつ、コストの合計がコストｓ以下となるように追加する辺の組み合わせを選択したときの信頼度の上限を表す値を格納したインデックスを計算するインデックス計算部と、計算されたインデックスと、追加に必要な各辺の各々のコストと、各辺の各々の動作確率と、コストの上限Ｃとに基づいて、選択する辺の組み合わせのコストがコスト上限Ｃ以下となる制約を満たすようにネットワークに追加する辺の組み合わせを選択することにより、コスト制約を満たしつつ、通信の信頼度を最大化するネットワークを設計することができる。これにより、より耐障害性能の高いネットワークの設計に寄与することができる。
【００６３】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００６４】
２０   演算部
３０   ＢＤＤ構築部
３２   インデックス計算部
３４   最適化計算部
５０   出力部
１００ ネットワーク設計装置
【図１】
2019114877.tif 000013
【図２】
2019114877.tif 000014
【図３】
2019114877.tif 000015
【図４】
2019114877.tif 000016
【図５】
2019114877.tif 000017
【図６】
2019114877.tif 000018
【図７】
2019114877.tif 000019