(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf_第1页
(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf_第2页
(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf_第3页
(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf_第4页
(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf_第5页
已阅读5页,还剩63页未读, 继续免费阅读

(通信与信息系统专业论文)基于结构分解的网络可靠性分析研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

西南科技大学硕士研究生学位论文第1 页 摘要 随着网络不断发展,网络科学与技术已渗透到社会各个领域,人们的生 活也越来越依赖于网络。作为网络性能的一项关键指标,可靠性关乎到网络 数据能否正常传输,网络服务能否满足用户需求。在网络结构空前膨胀的今 天,网络故障可能导致网络瘫痪,带来巨大的经济损失。传统的网络可靠性 评估方法很难应用于规模较大的网络结构,需要对网络可靠性的有效计算算 法进行深入研究。 论文首先讨论了网络可靠性的国内外研究现状,对现阶段其研究领域的 主要问题进行了阐述,并重点分析了该领域中的连通可靠性。其次,介绍了 网络可靠性的相关理论知识及一些传统的计算方法。在查阅大量国内外相关 的文献基础上,针对链路或节点失效的连通网络可靠性展开了进一步地研究。 通过对链路失效的因子分解精确算法改进提出了因子分解近似算 法,该近似算法在给定精度要求的情况下能够快速有效地计算网络可靠度的 边界值,尤其是对于较大规模的网络,其计算开销要明显低于精确算法。 研究节点失效的因子分解算法,给出相应的计算公式,并通过实验 验证该算法对于计算中、小规模的结点不可靠网络的连通可靠性是一种非常 有效的方法。 研究采用i t e ( i f - t h e n e l s e ) 表达式来构建b d d ( b i n a r yd e c i s i o n d i a g r a m s ) 高效的存储结构,提出按广度优先搜索方式改进的边扩张( e d g e e x p a n s i o n ) 、点扩张( n o d ee x p a n s i o n ) 算法。这两种算法都采用了哈希表 来存储网络的同构子网,从而能够很好地减少网络的冗余,提高网络的计算 效率。同时利用该改进的算法,也可以对网络中的链路或节点进行重要性评 价。这样当网络中多条链路或多个节点同时发生故障时,就可以确定它们维 修的先后顺序以及对重要链路或节点进行重点维护,提高整个网络的可靠性。 通过研究无线传感器网络的拓扑结构,建立无线传感器网络的终端 对等效图模型。将上述算法应用于等效图中,就可以计算出无线传感器网络 的连通可靠度及确定网络中的重要链路或节点。 关键词:二端网络,链路重要性,结点重要性,网络可靠性,二元决策 图,网络可靠性模型 a b s t r a c t w i t ht h ec o n t i n u o u s d e v e l o p m e n to fn e t w o r k s ,n e t w o r k s c i e n c ea n d t e c h n o l o g yh a sp e n e t r a t e di n t oa l la s p e c t so fs o c i a ln e e d s p e o p l e sl i v e sb e c o m e i n c r e a s i n g l yd e p e n d e n t o nt h en e t w o r k a sa k e y i n d i c a t o ro fn e t w o r k p e r f o r m a n c e ,r e l i a b i l i t yr e l a t e st ow h e t h e rt h en o r m a lt r a n s m i s s i o no fn e t w o r k d a t a ,n e t w o r ks e r v i c ec a ns a t i s f yt h en e e d so fo u rc l i e n t s i na nu n p r e c e d e n t e d e x p a n s i o no ft h en e t w o r ks t r u c t u r et o d a y ,n e t w o r kf a i l u r em a yc a u s et h ee n t i r e n e t w o r ki n t oc o l l a p s ea n db r i n gh u g ee c o n o m i cl o s s e s t h et r a d i t i o n a ln e t w o r k r e l i a b i l i t ye v a l u a t i o nm e t h o d sd i f f i c u l tu s ei nt h el a r g e rn e t w o r ks t r u c t u r ea n d n e e du st o d e p t h r e s e a r c he f f e c t i v ec o m p u t a t i o n a la l g o r i t h m sf o rn e t w o r k r e l i a b i l i t y t h ep a p e rf i r s td i s c u s s e so v e r s e a sr e g a r d i n gt h ec o m p u t e rn e t w o r kr e l i a b l e r e s e a r c hp r e s e n ts i t u a t i o n ,t h e ne l a b o r a t e st h em a i nc o n t e n to ft h ec u r r e n ta b o u t t h ef i e l do fn e t w o r kr e l i a b i l i t y ,a n da n a l y s e st h ec o n n e c t e dr e l i a b i l i t yo ft h i sf i e l d s e c o n d l y ,i ti n t r o d u c e san u m b e ro fr e l e v a n tt h e o r e t i c a lk n o w l e d g eo fn e t w o r k r e l i a b i l i t ya n ds o m et r a d i t i o n a lm e t h o d so fc o m p u t i n gn e t w o r kr e l i a b i l i t y b a s e d o nc o n s u l t i n gal a r g en u m b e ro fd o m e s t i c a n df o r e i g nr e l e v a n tl i t e r a t u r e , a c c o r d i n gt ot h er e l i a b i l i t yo ft h ec o n n e c t i v i t yn e t w o r kf o rl i n ko r n o d ef a i l u r e h a sl a u n c h e daf u r t h e rs t u d y t h r o u g ht h ef a c t o rd e c o m p o s i t i o na c c u r a t ea l g o r i t h m i m p r o v e m e n to f t h el i n kf a i l u r et op r o p o s et h ef a c t o rd e c o m p o s i t i o na p p r o x i m a t i o na l g o r i t h m ,t h e a p p r o x i m a t i o na l g o r i t h m i s g i v e ni np r e c i s i o nr e q u i r e m e n t s c a nq u i c k l ya n d e 筒c i e n t l yc a l c u l a t et h eb o u n d a r yv a l u e so f t h en e t w o r kr e l i a b i l i t y ,e s p e c i a l l yf o r al a r g e s c a l en e t w o r k ,i t sc o m p u t a t i o n a lo v e r h e a di so b v i o u s l yl o w e rt h a nt h e a c c u r a t ea l g o r i t h m a f t e rs t u d i e st h ef a i l u r eo fn o d ef a c t o rd e c o m p o s i t i o na l g o r i t h m ,t h e c o r r e s d o n d i n gc a l c u l a t i o nf o r m u l a i s g i v e n ,b ye x p e r i m e n t t o v e r i f y t h e a l g o r i t h mf o rc a l c u l a t i n gc o n n e c t i v i t yr e l i a b i l i t yo fs m a l l s c a l en o d eu n r e l i a b l e n e t w o r ki sav e r ye f f e c t i v em e t h o d s t u d yu s i n gt h ei t e ( i f - t h e n e l s e ) e x p r e s s i o n t oc o n s t r u c tt h eb d d e f f i c i e n ts t o r a g es t r u c t u r e ,a n dp r o p o s eab r e a d t h f i r s ts e a r c ho fw a y st oi m p r o v e t h ee d g ee x p i n s i o n 、t h en o d ee x p a n s i o na l g o r i t h m t h et w oa l g o r i t h m su s ea _ 一 西南科技大学硕士研究生学位论文第1 i i 页 h a s ht a b l et os t o r e i s o m o r p h i s ms u b n e to fn e t w o r k ,w h i c hc a nr e d u c et h e r e d u n d a n c yo ft h en e t w o r ka n di m p r o v et h ec o m p u t a t i o n a le f f i c i e n c yo ft h e n e t w o r k a tt h es a m et i m et a k i n ga d v a n t a g eo ft h ei m p r o v e da l g o r i t h m ,a n da l s o c a r r yo u tt h ei m p o r t a n c ee v a l u a t i o nf o rl i n k o rn o d e o fn e t w o r k s ow h e n m u l t i p l el i n k so rm u l t i p l en o d e ss i m u l t a n e o u sf a i l u r ei n t h en e t w o r k ,w ec a n d e t e r m i n et h eo r d e ro ft h e i rm a i n t e n a n c ea sw e l la se m p h a s i so nt om a i n t a i na n i m p o r t a n tl i n ko rn o d e ,i no r d e rt or e d u c et h e i rf a u l ta n di m p r o v et h er e l i a b i l i t y o ft h ee n t i r en e t w o r k b ys t u d y i n gt h ep h y s i c a lt o p o l o g yf o rt h ew i r e l e s ss e n s o rn e t w o r k s ,w e h a v ee s t a b l i s h e de n d t o e n d e q u i v a l e n tg r a p hm o d e lo ft h e w i r e l e s ss e n s o r n e t w o r k s t h ea b o v em e n t i o n e da l g o r i t h mi sa p p l i e dt ot h ee q u i v a l e n tg r a p h ,w e c a nc a l c u l a t et h er e l i a b i l i t yo fw i r e l e s s s e n s o rc o n n e c t i v i t yn e t w o r k a n d d e t e r m i n et h ei m p o r t a n tl i n ko rn o d ei nt h en e t w o r k k e yw o r d s :2 - t e r m i n a ln e t w o r k s ;l i n ki m p o r t a n c e ;n o d e i m p o r t a n c e ; n e t w o r kr e l i a b i l i t y ;o r d e r e db i n a r yd e c i s i o nd i a g r a m ;n e t w o r kr e l i a b i l i t ym o d e l _ 一 西南科技大学硕士研究生学位论文第1 页 1 绪论 1 1课题研究的背景与意义 可靠性学科最早产生于航空与军事领域,是在第二次世界大战期间为解 决武器装备的不可靠问题而提出的。它的产生及发展与电子技术的发展密切 相关,它也是社会发展的必然产物。到目前为止,它已发展成为一门涉及面 十分广泛的综合性应用学科。 作为一门涉及面很广的综合性新兴交叉学科,世界各发达国家均给予了 高度重视。尤其是日本,把可靠性的应用放到质量管理上,其产品的质量有 了大幅度的提高,产品的高可靠性也得到国际市场的高度好评,为此,大大 推动了日本的经济发展,也使其成为了经济强国。美国国防部与l9 5 7 年起 就对可靠性给予了极大重视。此后不久,与1 9 6 5 年国际电子技术委员会就成 立了可靠性专业委员会,这也表明了可靠性工程已成为一门国际性技术。在 我国最早开展可靠性的工作与国际上基本一致,也是通过对电子产品的研究, 在2 0 世纪6 0 年代初,还成立了专门研究机构进行可靠性评估的开拓性工作。 到了7 0 年代,在发达国家关于可靠性的研究工作变得更加的专业和深入,尤 其是航天方面,对可靠性的要求基本上要达到9 9 9 ,这样对系统的设计就 提出了极高要求,在电子产品的设计方面,关于可靠性的要求也是越来越高, 从它的应用和给国民经济及企业所带来的巨大效益方面来看,人们已经深刻 的意识到提高产品可靠性的重要性。 与此同时,伴随着通信技术和计算机网络技术的发展,为可靠性的研究 提供了更加广阔的领域,尤其是在美国诞生的世界上第一个计算机网络 a r p a n e t 以后,科研人员就开始了很多关于网络可靠性的研究“,到了9 0 年代,高新的技术使得网络变得更加密集化,这也加剧了单个部件故障对网 络的影响程度,因此关于网络可靠性在网络部件故障情况下的研究很快就成 为了热点t “,另一方面网络传输容量的密集化也会导致整个网络更加的稀疏 化,在这种情况下,需要我们重点考虑网络的连通性,它是网络能够进行正 常工作的重要保障,也是在网络的设计时进行可靠性分析的重要因素。网络 可靠性的计算问题同样适用于优化设计s d h 网络、计算机网络、电信网络、 a t m 网络以及无线传感器网络h ,这些方面也都将成为网络可靠性研究的 重要领域。现如今伴随着社会信息化进一步加强,人们对网络的依赖性也变 得越来越强,尤其是在信息产业高速发展的今天,网络的规模仍在不断地扩 西南科技大学硕士研究生学位论文第2 页 大,其用户数量也在迅速增长,网络的结构也变的越发复杂,一旦网络发生 故障,将会给社会、政治、经济、环境、文化等带来巨大破坏,因此在设计 网络时需要我们重点分析网络的可靠性,不断地评估网络可靠性优化网络结 构也是网络设计者最关心的重大课题1 。同时网络可靠性也是我们进行网络 管理、运行和维护的依据指标,通过对网络可靠性的分析,就可以发现网络 中比较脆弱的节点和链路,并采取相应的措施进行重点保护也可降低故障时 带来的风险旧,减少损失。设计较高可靠性的网络对准确无误地评价网络可 靠性的性能具有重要的理论和现实意义。 目前关于网络可靠性的研究主要还是针对网络链路和节点发生故障时的 分析no | n “。比如对通信网络、交通网络、传感器网络等,从建立模型开始, 对其可靠性如何要求? 如何分析不同设计方案的优劣? 以及如何确定网络在 遭受破坏后的维修顺序? 由于这些新的特点,对网络可靠性的要求也变得更 加严格。近年来,由于嵌入式技术、通信技术和传感器技术的不断成熟,使 得无线传感器网络迅速发展成为了一门新兴技术“,从2 l 世纪开始,欧美就 启动了无线传感器网络的研究,先后提出了“灵巧传感器网络通信”、“基于 微型传感器网络的新型计算规划”。然而,由于传感器能源的有限性和环境的 恶劣性等缺陷,容易造成无线传感器网络出现能源耗尽或受到自然界破坏而 出现通信中断的情况n3 ,这些因素对无线传感器网络的性能都有严重的影响。 因此对无线传感器网络的可靠性研究是十分必要的,建立适应无线传感器网 络自身特点的可靠性理论对网络的优化设计也具有重要的理论指导和实际价 值。 1 2国内外研究现状 1 2 1国外研究现状 国外早期关于网络可靠性的研究主要集中在通信| ) ( = 习络领域,最早是由 m rl e e 对电信交换网络进行的研究,网络部件的故障会导致整个网络的传 输容量下降,可能引起呼叫拥塞,从而致使网络瘫痪,m rl e e 将上述故障称 为链路故障,并提出将连通性作为网络可靠性的指标。之后伴随着计算机网 络的迅速发展,尤其是世界上第一个计算机网络a r p a n e t 诞生并投入使用以 后,网络可靠性的研究才真正得到关注。这个阶段主要是针对网络的连通性 指标来考察网络的可靠性。例如b a r b e r i s 等人给出了一种加权的端到端连 通概率完成性指标l ;p a r k 等人采用了一种基于网络传输时延的完成性指 西南科技大学硕士研究生学位论文第3 页 标”“。 到八十年代,由于网络规模的迅速扩张,由b o e s c h 首次提出网络可靠性 的优化与设计方案,并涉及到如何优化网络的可靠性及如何完善网络拓扑 结构设计等的问题。这一阶段研究的主要是对网络可靠性性能的分析。例如 b o n a v e n t u r a 对报文和线路交换网提出了基于时延的有效性指标”“, d e u e r m e y e r 以网络吞吐量为切入点提出一种分析网络完成性的方法”。 进入九十年代后,社会网络化进程进一步加快,这一阶段对网络系统的 可靠性研究越来越多,其研究范围也从通信网拓展到电路、电力、交通网等 生活中的各个领域,此后,网络可靠性的研究工作大部分都集中在网络部件 故障时对网络可靠度的计算和性能分析的研究n ,如a b o e l f o t o h 通过对二 端网络可靠性分析提出了因子分解方法他,e l m a l l a n ,a y o u b 等人通过对k 端 网络可靠性的分析提出了一些新的算法恤”,s m i t hae 等人将遗传算法、启发 式算法等应用到求解全终端网络可靠性的问题上,且获得了较为满意的结果 。 现阶段,随着低功耗嵌入式技术和传感器技术的迅速发展,出现了很多 具有监测、计算和通信功能的无线传感器网络,且已经深度延伸到军事、商 业以及空间探索和自然灾难等特殊领域,其结构、布局、规模也更加复杂化, 这对网络可靠性又提出了更高的要求。目前主要是从下述几个方面来研究无 线传感器网络可靠性:路由协议可靠性、连通可靠性、二终端可靠性、节点 可靠性和结构可靠性。研究成果有:t h a imt 等人利用节点的多重连通和多重 覆盖来提高网络的抗毁性”,l u oj , j i a n glg 等人在未考虑路由算法对网络 性能的影响下研究了能耗与时延的折中问题n “,f l o r e n sc ,s h a r i fm 等人在考 虑无线传感器网络对数据传输时延的情况下提出了高效的m a c 协议和路由 算法提高端到端能量的使用效率“,h a r d yg l u c e tc ,l i m n i o sn 提出了k 终 端网络可靠性的b d d 评估算法心。 1 2 2国内研究现状 在国内,对网络可靠性的研究较晚,最早是由钱学森与2 0 世纪6 0 年代 提出的,主要应用于航天和军事领域。到了七十年代,随着计算机网络技术 的发展,出现了很多关于计算机网络理论方面的可靠性算法,如张公绪提出 的通信网络割集算法。这一时期主要是针对网络可靠性的凝聚度和连通度指 标来研究的。 到了九十年代以后,随着计算机网络容量进一步加聚,实现了软硬件和 西南科技大学硕士研究生学位论文第4 页 数据资源的共享,然而一旦网络故障,将会给人们带来无法弥补的损失,因 此网络的规划、设计、建设者开始重视了网络的可靠性问题,尤其是网络的 可靠性优化与设计。这一时期关于网络的优化与设计方法成为了人们研究的 热点。许多研究机构与大学在这方面都取得了不错的成果。诸如许多学者针 对二终端网络可靠度、k 一终端可靠度和全终端可靠度提出了一系列新的计算 算法“,还有些学者通过对y u n g r u e ic h a n g 等人算法的改进提出了k 终端 可靠度的计算算法,伴随智能算法等的出现,网络可靠性的优化研究又前 进一步,郭伟等学者提出了一种近似评估网络可靠性的方法,并深入研究了 网络可靠性的优化设计问题,另外,有些学者将蚁群算法、遗传算法等进 化算法应用到解决网络可靠性的优化问题上n “。上述介绍的研究成果大多是 针对网络节点的连通性或二终端网络的可靠性等研究的。 现阶段,由于无线传感器网络的出现引起了人们广泛的关注,我国也开 展了对无线传感器网络的研究,与2 0 0 6 年初发布的国家中长期科学与技术 发展规划纲要中确定了3 个前沿的研究方向,其中跟无线传感器网络直接 相关的就有两个,同时国家自然科学基金委员会在该领域也设立了多个重点 研究项目,例如张强等人对无线传感器网络k 终端可靠性的研究”“1 ,然而在 二终端连通网络可靠性的优化设计方面取得的成果并不多,所谓的二终端连 通网络可靠性是指网络的源端与终端之问至少存在一条通路通信的概率”1 , 因此,它也是进行网络可靠性研究的重点,本文也是基于此丌展研究的。 1 3 论文研究内容 1 3 1论文研究的主要内容 论文研究的课题是“基于结构分解的网络可靠性分析研究”,是在总结了 国内外关于网络可靠性研究现状的基础上,针对二终端网络的连通可靠性作 为主要的研究目标,并将其应用到对无线传感器网络可靠性的优化设计中。 具体的研究内容主要包括以下几个方面: ( 1 ) 研究二端网络因子分解算法,并对该算法进行改进,提出一种近似 评估通信网可靠度的算法。 通过对几种精确算法的研究,得知因子分解算法是计算网络可靠度精确 值的一种非常普遍f i j 有效的方法。但是,如果利用该算法计算较大规模网络 的精确度时,计算量将会快速膨胀,算法的计算效率也会变得低下。考虑到 网络从根节点因子分解到叶子节点的完整支路的可靠度的总体趋势是减小 西南科技大学硕士研究生学位论文第5 页 的,因此在给出一定精度的条件下,通过收缩和截取子网不再让其继续因子 分解,这样就可以分别确定二端网络的上下界值。该算法的时问复杂由最坏 时问复杂度研2 ”) 变为0 ( 2 ”) 一0 ( 2 ”) ,( 其中m 、n 分别为网络和子网的边数) , 提高了网络的计算效率。最终的实验结果也表明该方法可快速有效的计算网 络可靠度的边界值。 ( 2 ) 研究b d d 的基本理论,并将b d d 结构分别应用到边、点的扩张算 法中。 通过对b d d 基本理论的研究,得知b d d 的表示形式是一种高效的存储 结构,能够以较小的空问存储较大规模的网络图,而b d d 结构的大小跟构 造过程中变量的顺序直接相关,目前产生较好的变量顺序是运用b f s 方式。 在此基础上,研究采用( i f - t h e n e l s e ) 连接词将网络的分解过程转换为b d d 结构,并将该b d d 结构分别应用到边和点的扩张算法中,能很好减少网络 的冗余状态,提高网络的计算效率。 ( 3 ) 研究网络可靠性分析系统模块的设计与实现。 网络可靠度分析仿真软件包括:网络的表示与存储:网络的存储结构 采用邻接表而不是邻接矩阵,这样可减少了网络的存储空间。网络结构的 功能模块化:悬挂边简化模块、自环简化模块、删除点( 边) 模块、收缩点( 边) 模块、点( 边) 扩张模块。遍历计算网络的可靠度:采用广度优先搜索( b f s ) 方式来遍历计算网络的可靠度。 ( 4 ) 研究无线传感器网络中二终端网络连通可靠性的优化模型。 应用上述介绍的算法来评估无线传感器网络中s i n k ( 数据被传往的端点) 结点与传感器结点之f b j 的连通概率,并通过可靠性计算来确定无线传感器网 络中的重要节点,对最重要结点进行改善,就可提高无线传感器网络的可靠 性。 1 3 2创新点 文章主要是在以下几个方面进行了创新研究: ( 1 ) 通过对二端网络因子分解精确算法的研究,可知对于较大规模网络, 网络精确值的计算非常困难。基于效率和精度的考虑,本文在此精确算法的 基础上通过改进得出一种近似评估网络可靠性的算法,并通过仿真验证了该 近似算法的计算时问要低于精确算法。 ( 2 ) 通过对b d d 基本理论的研究,采用( i f - t h e n e l s e ) 连接词将网络的 分解过程转换为b d d 结构的布尔表达式,并运用b f s 遍历方式将该b d d 结 西南科技大学硕士研究生学位论文第6 页 构的布尔表达式分别应用到边和点的扩张算法中,能够很好减少网络的冗余 状态,提高网络的计算效率,且通过仿真对网络可靠性的计算进行了更加深 入的分析。 ( 3 ) 结合提出的算法来评估无线传感器网络的可靠性,并对网络可靠性 分析系统模块的设计进行优化,确定网络中的最重要节点且进行重点维护可 提高无线传感器网络的可靠性。 1 4 论文的组织结构与安排 论文共分为五章,内容介绍如下: 第一章是绪论,首先介绍了课题研究的背景与意义;接着介绍了关于网 络可靠性的国内外研究现状,且对网络可靠性研究领域的主要研究内容进行 了阐述;最后介绍了论文的主要研究内容及创新点。 第二章是网络可靠性的相关理论,首先介绍了关于网络可靠性的基本概 念,接着对其网络的结构模型进行描述,最后重点讨论了关于网络可靠性的 一些计算方法。 第三章是链路失效网络可靠性分析算法,本章首先介绍了二元决策图 b d d 的基本知识,研究了网络可靠性分析系统的模块化设计,接着重点研究 了计算网络链路的连通可靠性算法,提出了基于因子分解的近似算法和采用 b f s 遍历的边扩张算法,最后对以上算法进行了仿真分析。 第四章是节点失效网络可靠性分析算法,本章重点研究了计算网络节点 的连通可靠性算法,应用结点的因子分解算法或结点的扩张算法来递归计算 网络的可靠度,最后通过上述的可靠度计算来确定网络中的至关重要节点, 并对其进行优化来提高网络可靠度性能,经过仿真分析,验证了上述方法的 有效性。 第五章是结构分解算法在无线传感器网络中的应用,首先介绍了无线传 感器的网络的拓扑结构并建立了可靠性模型,然后针对其网络模型从网络的 链路或节点失效方面进行了可靠性评估。 西南科技大学硕士研究生学位论文第7 页 2 网络可靠性相关理论 2 1 网络可靠性基本概念 2 1 1 网络可靠性的定义 现阶段国内外学者从不同的角度定义了网络可靠性,但其本质都是在以 下概念上得出的1 1 ( 1 ) 网络可靠性是指网络在特定的时间和条件下,完成所规定正常通信 功能的能力。 ( 2 ) 网络可靠性是指网络在特定的时间和条件下,完成所规定正常通信 功能的概率。 这里“特定时间”是执行任务的时间,由于网络中的元器件随时间的延 长,可能会出现老化、功能降低等现象,不同的时间段,损耗情况也会不同, 因此只有在特定时间内讨论网络可靠性才有实际意义。“特定条件”主要指的 是维修条件、环境条件与使用条件,这些条件对于网络可靠性有着重大影响。 即便是对于同一个网络,所处的条件不同,其可靠性也可能会相差很大,因 此,对网络可靠性的研究必须是在特定的条件下才具有实际意义。“规定的功 能”是网络的战术性能指标,对网络功能的要求越多,其可靠性设计也就越 难。通常来说,在网络保持其连通的情况下,尽量实现所规定的f 常通信功 能。其研究成果大致又可分为抗毁性、生存性和有效性三个方面。 1 ) 网络的抗毁性:是指网络遭到攻击后无法保持正常通信需要删除的最 小链路或节点数。其测度指标包括:聚合度和连通度川。聚合度是指使网络 中断需要删除的最小链路数,即网络最少割边的边数;连通度是指使网络中 断需要删除的最小节点数,即网络最少割端的端点数。 2 ) 网络的生存性:是指某种结构的网络,在自身可靠性因素( 如设备老 化等) 、及环境因素( o n 人为破坏、自然灾害等) 的影响下,使得网络部件( 节点、 链路) 以某种概率失效时网络仍保存连通的概率。生存性又称为概率型可靠性 网络,它是网络部件故障率的可靠性指标,也是进行网络可靠性研究的重要 领域。 3 1 网络的有效性:是指网络性能的可靠性指标,通常又称为网络的完成 性,其指标主要包括:业务性能( 吞吐量、时延、呼损等) 、有效度和完成度。 有效度是指网络部件在失效时某种性能指标的期望值。完成度指网络中所有 有效态( 网络的可靠性的性能优于设定值) 的概率累加和。网络的有效性能够 西南科技大学硕士研究生学位论文第8 页 更好的反映出网络的服务质量,因此,网络的性能也是进行网络可靠性分析 的一个研究热点。 综上说述,这三个方面都与网络的连通性指标密不可分,网络的抗毁性 能够很好地反映网络的拓扑结构,是网络进行分析与设计的基础,网络的生 存性考虑的是网络部件失效时对网络连通性的影响情况。因此,网络的连通 性通常可通过网络可靠性来衡量的旧“。本文主要研究的就是关于网络的生存 性问题。 2 1 2 网络可靠性分类 网络可靠性通常是指网络的概率连通性,是在网络设计和运行中必不可 少的一个重要参数,按完成规定功能的不同,网络可靠性可分为全终端可靠 性、二终端可靠性和尽终端可靠性三类。 1 ) 全终端网络可靠性 全终端网络可靠性是指在一个概率图中,整个网络中所有端点之间均保 持正常连通的概率,。全终端网络可靠性更能体现整个网络的性能,但是全 终端网络可靠性的计算问题是n p h a r d ,这方面的研究也相对较少。 2 1 二终端网络可靠性 二端网络可靠度性指网络中指定的两点之问存在一条连通路径的概率 m ,;也就是说网络中在源端点s 和目的端点t 之间至少存在一条路径使之通 信。任何一个完整的网络,都不希望出现孤立节点或出现分离的子网,随着 高科技的迅速发展,网络也变得越来越复杂,若出现上述情况,网络的执行 效率就会大大降低,也可能导致通信网络的中断,这非常危险,此外,二端 网络可靠性的计算也是人们进行网络可靠性分析与设计的基础,因此,对二 端网络可靠性的研究非常重要。本文关于网络可靠性问题就是针对二端网络 展开研究的。 3 1k 一终端网络可靠性 k 终端网络可靠性”是指在一个概率图中,指定的k 个端点之间均保持 相互连通的概率,当顶点集合k 中只包含一个非源端结点时,即k = 2 ,该问题 就转化为二终端可靠性问题;当k 中包含网络中除源端结点外所有结点时, 即k = ,z ,称为全终端可靠性问题,因此,二终端和全终端网络可靠性可视为 尽终端网络可靠性的一个特例。 西南科技大学硕士研究生学位论文第9 页 2 1 3 网络可靠性评价 确定网络可靠性指标是进行网络可靠性分析与评价的前提,建立完整的 可靠性评价体系,能够更准确地评价网络的可靠性,提高网络可靠性的性能, 因此对网络进行可靠性评价,是研究网络可靠性的一个重要方向。”,。 网络可靠性评价主要是对网络链路和网络节点的重要性进行评价,它也 是进行网络分析的一项重要指标,由于人为或自然的原因,网络的节点或链 路容易发牛故障,所以在进行网络设计时,需要重点维护网络中的重要节点 或重要链路,这样当网络出现故障时,先对重要节点或链路进行维修,就可 降低故障的损失。因此,对网络的节点或链路进行重要性评价是非常有必要 的。 网络节点或链路的重要性取决于它们对网络可靠性的影响程度。针对不 同的测度,其评价方法也不相同。归纳起来主要有:最小割集、最小路集、 最短路径、可靠性多项式、最小生成树、最大流、关键重要度等。本文主要 是把关键重要度作为评价准则,并提出了链路或节点收缩的评价方法,当删 除网络图中的某条边或某个节点时,对应的网络可靠度值最小,则表明该边 或节点就最重要。 2 2网络模型 2 2 1图论基础 图论是离散数学的一个重要分支学科,应用极为广泛,特别是近几年的 迅速发展,应用范围已经渗入到逻辑学、语言学、物理、化学、计算机科学 等领域,它在通信、运输网络中的应用更为深入,尤其是通信网络的问题主 要是运用图论的知识来分析网络的可靠性和连通性。 本文所涉及到图论的一些基本内容如下n ”: 对于一个图g = r 形剧是由两个集合组成,其中吖q 表示g 的顶点集,e 倒 表示g 的边集,对每条边都有e = 似,w ,也就是说e 和两个顶点“,v 相关联, 点h i , v 被称为e 的两个端点,且“,v 相邻或邻接。这里跟顶点v 相关联的边的 个数就称为点v 的度,记为d e g ( v ) 。 若有两条或两条以上的边同与一对端点相关,则称为平行边。p = 似,砂称 为自环。如果e 有方向,则称为有向边,反之则称为无向边。如果每条边都 有方向,则图称为有向图,反之若图都有似,砂= 化砂,则图称为无向图。不存 在白环且没有平行边的无向图称为简单图。 西南科技大学硕士研究生学位论文第1o 页 对于图g 中各个顶点问恰有一条边连接的简单图就称此图为完全图。任 意图g 和h ,都满足吖矽= 吖q ,e 倒c e ( g ) ,称图h 为图g 的生成子图。 如果图g 的一个顶点和边序列= v o e l ,l e 2 ,v m _ l e 。y 。,使得l f m ,其中 边e ,的两个端点分别是一,和v ,则称该序列就为g 的一条路径,和分 别称为该路径的起点和终点,又如果边q ,e 2 ,e m 书互不相同,则称该路径 就为g 的条链,对于顶点又互不相同的链,则称该链为g 路,路中边的个 数称为该路的长度。如果无向图g 的任意两顶点问都至少有一条路连接,那 么就称该无向图为连通图。 对于无向图g ,其中v = v l ,v 2 ,匕) ,e = e 。,e :,p 。,) ,y 和e 分别 为图g 的顶点集和边集,顶点集v 中的所有顶点可用一个一维数组表示,边 集e 可用一个二维数组表示,则此二维数组就称为邻接矩阵。图g 的邻接矩 阵可以通过,2 木甩的矩阵来描述: f l 若f v v 、e、 4 f 卅刊u ,f 】i 2 1 0 若x ( w - t 7 j 肛i - - e 1 2 2 2网络可靠性模型 网络可靠性主要研究的是网络元件出现故障时,网络仍然能够保持连通 的概率,在实际生活中,通常网络如计算机网络、能源网络、无线通信网络、 交通运输网络、无线传感器网络等的可靠性问题模型都可以转化为关于图的 可靠性模型。 网络可靠性模型通常采用概率图g r k 剧的方式来表示,图中点的集合矿 表示网络的通信中心、终端或路由器等:图中边的集合e 表示网络节点间的 通信链路。这样就把一个实际的网络抽象为了一个图,概率图g f ,k 习就是对 图中的边和点以1 定的概率值正常工作所得到的图,图中边与点都有两个状 态:即工作与失效。这罩的工作是说概率值为1 ,失效是说以一定的概率值 工作。为了更好的研究图的结构,我们进行了如下三方面的假设川: 1 ) 图中每个顶点与边有且只有正常工作或失效两种状态; 2 1 图中的顶点与边失效的概率己知: 3 ) 图中顶点与边的失效状态在概率统计上是相互独立的。 网络可靠性理论又可分为两种i :网络可靠性分析与网络可靠性综合。 网络可靠性分析研究的是用给出的概率图来计算网络的可靠性;网络可靠性 综合研究的是通过给出的网络构成元件来设计一个可靠性最大的网络。本文 西南科技大学硕士研究生学位论文第1l 页 研究的主要内容是针对网络可靠性分析问题。 网络可靠性根据限制条件的不同,其可靠性模型可划分为以下三种模型: 1 ) 边失效模型:图中所有的边不可靠,所有的点则完全可靠且不会失效。 2 ) 点失效模型:图中所有的点不可靠,所有的边则完全可靠且不会失效。 3 ) 点、边混合失效模型:图中所有的点与所有的边都不可靠。 本文主要研究的是前两种网络模型,边失效模型是边不可靠点可靠网络, 即在指定的图中,点出现故障的概率为0 ,而边出现故障的概率为一尸且相 互独立。点失效模型是点不可靠边可靠网络,即在指定的图中,边出现故障 的概率为0 ,而点出现故障的概率为j p 且相互独立。在现实生活中,这两 种模型都有广泛的应用。例如,在通信网络中,点可以代表通信网中的路由 器,边可以代表通信网中连接路由器的链路,实际通信网络中的路由器发生 故障的概率很低,可认为为0 ,网络的故障主要由通信链路故障引起的。而 对另一种情况,如无线通信网络,点可以代表移动终端如手机等,边可以代 表无线电波等,通常可认为无线电波等出现故障的概率为0 ,网络故障主要 由移动终端引起。 2 3网络可靠性的计算方法 网络可靠性算法根据计算结果的精确度通常可分为两大类m 1 :网络可靠 性的精确算法与网络可靠性的近似算法。 2 3 1网络可靠性精确算法 网络可靠性精确算法是运用树、图论等相关知识先将网络的拓扑结构等 效为相关图模型,接着再结合数学中的数值分析、概率统计等分析方法来求 解网络图的可靠性。相关的研究方法一般可分为:完全状态枚举法、容斥原 理法、不交积和法和因子分解法等。 1 1 完全状态枚举法 完全状态枚举法是进行网络可靠性计算的最基本的方法n ,其原理是把 网络中节点和链路的所有状态全部列举出来并进行核对,以便于确定网络f 常工作的情况,再将这些事件进行累加就可以得到网络的可靠度。具体的实 现过程:将网络g 中所有成功事件的集合记为s ,其互斥的事件相应的表示 为4 ( i = 1 ,2 ,刀) ,则有: 西南科技大学硕士研究生学位论文第1 2 页 s = :a i ( 2 2 ) 一 i = 1 即网络的可靠度可表示为: j l r e ( g ) = p r s ) = 艺p r a j ) ( 2 - 3 ) i = 1 对每个概率图g ( k e ) ,其中的结点或链路都具有f 常工作或失效两个状 态。假设网络中有n 个结点和m 条链路,则将有2 ”2 ”= 2 ”种状态,随着 结点或链路个数的增加,网络的状态数将以几何倍数增长,其计算复杂度也 将成倍增加为0 ( 2 ”) ,因此,对于较大规模网络来说,利用完全状态枚举法 来求解网络的可靠度是很难的,该方法只适合于小规模网络的可靠度计算。 2 ) 容斥原理法 容斥原理法是运用数学中的概率容斥原理公式来计算网络的可靠性,。 其最典型的计算方法是最小路集、最小割集算法。路集和割集分别对应网络 的工作与失效状态,要使网络正常运行,则该网络中至少存在一个最小路集 或除最小割集外至少有一条边4 i 发生故障。路集是保持网络连通的边的集合, 最小路集是删除网络中的任一条边后网络就断开的边的集合。割集是使网络 断丌所需要删除的边的集合。最小割集是任意增加一条边后网络就保持连通 的边的集合。 对网络g 中的m 个最小路集,分别用4 ,a :,a m 来表示,要使网络f 常 工作则网络巾至少存在这样一条最小路,用事件s 可表示如下: m s = 比 ( 2 4 ) 则网络的可靠度的计算公式为: r 1 r e l ( g ) = p r s = p r li = 1j = p r ( 4 ) 一p r ( 4 a j ) + p r ( 4 4 4 ) + 一1 ) “p r ( 4 4 4 ,) ( 2 5 ) l 鱼s 肌 l g j ,1 9 ,诎蔓脚 因此,对特定网络来说,找出它所有包含的最小路集或最小割集代人公 式( 2 5 ) 就可以计算出网络的可靠度。对于上式共有2 项,当网络规模增 大时,m 值也会增大时,其计算量也会迅速膨胀

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论