リンクに依存関係がある場合のネットワーク信頼性評価手法の提案とその高速化

吉田拓弥 (1651124)


ネットワーク信頼性評価とは,ネットワークの各リンクに静的な故障確率が設定されている場合に,2頂点間が通信可能である確率を求める問題である.
この厳密計算手法として,二分決定グラフ (BDD)による計算方法が知られている.
BDDは組合せ集合を効率よく表現できるという特徴を持つデータ構造である.

本稿では,ネットワークのリンクの故障に従属関係 (以下,依存関係と呼ぶ)がある場合の信頼性評価を行う.
本手法では,ネットワーク上のリンク間に存在する依存関係をBDDで表現し,
依存関係を考慮しない信頼性BDDとの二項演算を行うことで,依存関係を考慮した信頼性BDDを生成する.
本手法を3通りの計算方法で実装し,各方法を処理時間と生成されるBDDのノード数の観点から比較する.
提案手法によって,74頂点のネットワークに対して依存関係を考慮した信頼性BDDを生成できたが,100頂点を超えるネットワークに対してはメモリ容量の不足により,依存関係を考慮した信頼性BDDを生成できないケースが見受けられた.

そのため併せて,依存関係を考慮したネットワーク信頼性BDDを高速に構築するアルゴリズムを提案する.
BDDを効率に生成できるか否かは,ネットワークの辺を処理する順序に依存する.
本研究では,依存関係を考慮した信頼性BDDを効率よく生成するための辺の処理順序を導出するアルゴリズムを提案する.
本手法では,依存関係のある辺同士の距離を評価したアルゴリズムを用いる.
これを既存手法である幅優先探索やBeam Searchと比較し,提案手法を評価する.
実験の結果,入力する依存関係によっては,既存手法では構築できないBDDを提案手法が構築できる場合が存在した.