信頼度最大ネットワーク構成を用いた効率的ネットワーク設計

榎本 大地  肖 霄  高橋 奈津美  山本 久志  

誌名
電子情報通信学会論文誌 A   Vol.J101-A   No.7   pp.178-188
発行日: 2018/07/01
Online ISSN: 1881-0195
DOI: 
論文種別: 論文
専門分野: 信頼性,保全性,安全性
キーワード: 
ネットワーク信頼性,  最大全点間信頼度,  条件付きコスト最小問題,  アルゴリズム改善,  

本文: PDF(616.8KB)
>>論文を購入


あらまし: 
本論文はネットワーク設計に関する古典的な問題の一つである,全点間信頼度制約下での構築コスト最小化を目指す問題に対し,解法アルゴリズムの計算負荷の削減を目的とする.全点間信頼度と構築コストの二つの評価尺度を考慮した問題においては,先行研究によって厳密解を得るためのアルゴリズムが提案されており,解探索開始時にあらかじめ与えられたノード数とエッジの信頼度から,制約条件を満たす探索開始エッジ数を決定することで,制約を満足しないエッジ数での探索を回避している.探索開始エッジ数の決定にはノード数とエッジ数の関係から得られる最大全点間信頼度が参照されるため,全点間信頼度を最大化するネットワーク構成を求める研究はこれまでにもなされているが,最大全点間信頼度の多項式を効率的に導出する方法は確立されていない.本論文では,このようなノード数とエッジ数の関係に応じた最大全点間信頼度を取りうるネットワーク構成に対し,その多項式を導出する方法を提案する.また,提案手法を用いて導出した式を利用し,先行研究のアルゴリズムの改善を行い,その効果を確認する.