基于OBDD的通信网链路重要性评估  

Importance evaluation of communication network links based on OBDD

作　　者：赵勃[1] 肖宇峰[2] 刘岩[1] 

机构地区：[1]北京邮电大学网络与交换国家重点实验室,北京100876 [2]西南科技大学信息工程学院,四川绵阳621010

出　　处：《系统工程与电子技术》2011年第10期2348-2352,共5页Systems Engineering and Electronics

摘　　要：通信网的链路重要性评估是网络设计和维护的重要依据。在链路重要性评估方法上提出了一种基于有序二叉决策图(ordered binary decision diagram,OBDD)的新方法——BO(Birnbaum OBDD,BO)方法。该方法引入了Birnbaum测度来量化链路重要性,并采用边扩张图(edge expansion diagram,EED)来创建网络的OBDD结构,在可靠度计算基础之上,通过分析链路故障时网络可靠度得到Birnbaum测度值。BO方法将高效的OBDD结构与hash表结合起来,并通过识别计算中出现的同构子网,减少冗余状态与重复计算来提高整体计算效率。引入并对比经典可靠性文献中一些规模较大网络,通过实验验证了BO方法不仅能正确地评估网络链路重要性,而且在计算效率方面优于因子分解方法。The importance evaluation of network links is important to network design and maintenance. This paper proposes a novel importance evaluation method named as Birnbaum ordered-binary-decision-diagram （BO） ,which is based on ordered binary decision diagram （OBDD）. Birnbaum measurement is introduced to qualify the link importance, and the OBDD structure of the network is constructed with an edge expansion diagram （EED）. Based on reliability calculations, the Birnbaum measurement value is gotten with the network re liability when links are fault. Furthermore, the efficient OBDD structure and hash table are used to identify those isomorphic subnetworks. As a result, some redundant states and repeated computations are decreased, and computation efficiency is enhanced. Some large networks from classic reliability literatures are introduced into experiments and are used as benchmark networks. Experiments show that the proposed method is more efficient than the factoring algorithm and can accurately evaluate the importance of network links.

关 键 词：网络可靠性 可靠度评估 有序二元决策图 链路重要性 

分 类 号：TN915[电子电信—通信与信息系统]