论文部分内容阅读
本文主要研究了网络可靠性的最优化问题以及其在无线传感器网络中的应用。本文研究的内容可以分为以下四部分。第一章主要介绍了网络可靠性的一些基本知识。首先介绍了几种主要的网络结构和三种可靠性的模型,然后给出了网络可靠性的几种精确算法和近似算法,最后介绍了-致最优和最差可靠图的最新研究进展。第二章主要证明了几类一致最差可靠图。一致最差可靠图问题是网络可靠性研究中的重点问题。在边失效的可靠性模型下,通过全终端可靠性和一致最差可靠图的定义证明了当e≤n-1时,在类Ω(n,e)中的任意图G都是一致最差可靠图。当e=n时,把类Ω(,n,e)分为两个不相交的子类Ω1(n,e)和Ω2(n,e),子类Ω1(n,e)中的图中都含有长度为3的圈,子类Ω2(n,e)中的图含有长度大3的圈。通过研究这两个子类的性质,证明了子类Ω1(n,e)中的任意图G在类Ω(n,e)中都是一致最差可靠图。当e=n+1时,给出了类Ω(n,e)中的子类Ω3(n,e),子类Ω3(n,e)的图都含有一个风筝。对类Ω(n,e)中的图使用因子定理进行简化计算,可以得到一个新图M。图M只有两种拓扑结构,研究了这个两种情况下图M的可靠性系数Si(M),通过比较它与子类Ω3(n,e)中任意图G的可靠性系数Si(G),证明了在子类Ω3(n,e)中的任意图G在类Ω(n,e)中都是一致最差可靠图。当e=n+2时,给出了类Ω(n,e)中的子类Ω4(n,e),子类Ω4(n,e)的图都含有一个完全图K4。对类Ω(n,e)中的图使用因子定理进行简化计算,可以得到一个新图M。图M一共有八种不同的拓扑结构,通过计算这八种结构中的可靠性系数Si(M)的下界,证明了在子类Ω4(n,e)中的任意图G在类Ω(n,e)中都是一致最差可靠图。第三章给出了一个新的可靠性模型:剩余边连通可靠性模型。在边失效的模型下,不连通网络的全终端可靠性是0;在相同类中不同结构的树的可靠性是相同的。为了更好的研究不连通网络可靠性之间的不同以及不同树结构下可靠性的变化,本章给出了剩余边连通可靠性的概念。在此定义下我们可以计算出不连通网络和不同结构的树的剩余边连通可靠性,通过比较此可靠性的大小,可以帮助我们选择更好的通信网络结构。此外还证明了在该可靠性下,一致最优可靠图的两个必要条件以及当e≤n-1时局部星图是其所在类的一致最优可靠图。第四章介绍了无线传感器网络的发展及其应用,给出了一个用可靠性来衡量修复性的定义。在无线传感器网络中,经常会遇到不连通网络,人们在不同的节点修复网络后,得到新网络的可靠性不一定相同。基于这种情况,本章给出了用可靠性来衡量修复性的定义。通过实验模拟,我们发现边可靠性的大小对于网络的修复性有很大影响。随着边可靠性的增大,修复性也在变大,但是当边的可靠性超过某一数值时,修复性就会下降。修复性会在边可靠性的某个中间值达到其最大值。