一种计算Ad hoc网络K-终端可靠性的线性时间算法  

A Linear-time Algorithm for Computing Ad hoc Network K-terminal Reliability of MANET

作　　者：毛鸿林[1] 沈元隆[1] 

机构地区：[1]南京邮电大学光电工程学院,江苏省南京市210003

出　　处：《电子工程师》2008年第2期54-56,共3页Electronic Engineer

摘　　要：研究计算Ad hoc网络K-终端可靠性的线性时间算法,可以快速计算Ad hoc网络K-终端可靠性。为了计算Ad hoc网络分级结构K-终端可靠性,可以采用无向概率图表示Ad hoc网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算K-终端可靠性的一种线性时间算法。本算法可用来计算Ad hoc网络的K-终端可靠性。其时间复杂度为O(|V|+|E|)。This paper studies linear-time algorithm for computing K-terminal reliability of MANET, may quickly compute K-terminal reliability of MANET. In order to computing K-terminal reliability of MANET hier-achical structure, MANET hierachical structure can be modeled using an undirected probabilistic graph, in which each cluster header is represented by a vertex with known probability of failure, and edge exists between the vertices iff the related clusters are adjacent. Consider a probabilistic graph in which the edges are perfectly reliable, but vertices can fail with some known probabilities. The K-terminal reliability of this graphs is the probability that a given set of vertices K is connected. This paper presents a linear-time algorithm for computing K-terminal reliability on proper interval graphs. This algorithm can be used for computing K-terminal reliability of MANET. This algorithm can be implemented in O（｜V｜ ＋ ｜E｜ ） time.

关 键 词：算法 区间图 网络可靠性 合适区间图 AD hoe网络 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]