教育资源为主的文档平台

当前位置: 查字典文档网> 所有文档分类> 工程科技> 信息与通信> 通信网络工程:通信网络拓扑可靠性层次与测度研究

通信网络工程:通信网络拓扑可靠性层次与测度研究

上传者:冯祖洪
|
上传时间:2016-09-19
|
次下载

通信网络工程:通信网络拓扑可靠性层次与测度研究

要:梳理讨论了目前通信网络可靠性研究之间的层次关系,讨论了拓扑可靠性所处的地位、任务、指标等。其次,分析了拓扑可靠性的非概率测度,指出了连通度的核心作用。再次,研究了基于边连通度与节点连通度进行可靠性评价的思想与算法。最后,通过一个算例展示了通信网络拓扑可靠性评价的具体过程。

 

关键词:通信网路 可靠性 层次 测度

 

随着通信、信息、网络技术的高速发展与广泛应用,人们对通信网络的依赖愈加明显,随之而来的可靠性问题日益成为用户关注的焦点领域。现代通信网络是一个复杂系统,融合了多学科领域,因此对其可靠性的研究是一项系统工程。

从目前的公开文献来看,通信网络可靠性研究分布于网络应用的各个层次与领域,一般可对应于OISOpen System Interconnect)系统模型的划分。同时,通信网络的复杂性、动态性、多态性等属性为可靠性评估与优化提出了新的挑战,导致了研究的视角与侧重点也不尽相同。拓扑结构是通信网络的核心特征,其依据拓扑来组织网络形态,进而体现通信网络系统的整体性。因此,对通信网络拓扑可靠性的研究处于整个通信网络可靠性研究的中心地位。

1 通信网络可靠性研究的层次体系

1.1 拓扑可靠性处于核心地位

如引言中所述,拓扑可靠性并不能完全表征整个通信网络的可靠性,其研究对象只关注于网络的拓扑结构,忽略了网络通信设备、路由策略、承载业务、管理效率等因素所带来的可靠性变化。拓扑层高于设备层,同时是路由层、业务层等高层可靠性的基础,在整个通信网络可靠性中处于承上启下的中间环节,其影响可见一斑。

通信网络可靠性可分层讨论,每层均应设计相应的指标与测度方法,以完成对通信网络可靠性的定量描述。因此,通信网络可靠性应具备一个同向、协调、完备的指标体系。在对目前文献梳理的基础之上,可得可靠性指标体系。同时,各文献对可靠性的理解与划分具有相互重叠性,而且关于同一类指标的描述也不尽相同,新的指标也不断被提出。

1.2 拓扑可靠性指标分析

在网络拓扑可靠性的指标描述上是想通的,即在抗毁性与生存性上具有广泛共识。同时可见,连通度是两者的指标与测度设计的基础因素。

1)网络拓扑抗毁性。主要用于刻画在确定的网络组织结构(即网络拓扑)、预定的破坏(攻击)方案下,通信网络依然能够保持全网或部分连通(物理可达)的能力。在对实际网络进行拓扑抽象之后,抗毁性指要破坏(中断)部分网络节点连接需要移除(破坏)的最少网络节点或链路(边)的数目,从而表征出破坏整个或部分通信网络的困难程度。可见,抗毁性完全由网络拓扑结构所决定,是可靠性的一个确定型指标。

2)网络拓扑生存性。生存性最显著的变化是引入了网络部件的失效(故障)概率,用于刻画在随机故障或蓄意破坏之下,保持通信网络整体或部分连通的概率。其建立在图论与概率论基础之上的可靠性分析,不仅受网络拓扑结构的影响,同时还依附于网络部件(设备)的故障概率与模式、网络维修与管理等因素,因此网络拓扑生存性是广义的拓扑层可靠性。

2 基于连通的通信网络拓扑可靠性测度

通信网络拓扑可靠性问题可抽象为图的可靠性问题,用图GVE)来描述拓扑结构。其中,V表示网络中节点的集合,例如用户终端、服务端、路由服务器等;E表示连接网络中节点的边(链路)集合。同时,本节主要讨论拓扑可靠性的非概率(静态)测度,即不考虑上层业务或下层设备影响,将问题视角完全限定在拓扑层面。

目前,关于拓扑可靠性的静态测度研究很多,可谓仁者见仁,测度设计的侧重点各不相同。例如:连通度(vertex connectivity)、坚韧度(toughness)、完整度(integrity)、粘连度(tenacity)、离散数(scattering number)、膨胀系数(expansion coefficient)等。其中,连通度是拓扑的基础指标,后续的测度均建立在对连通性的充分考虑的基础之上。因此,本节以连通度为重点展开讨论。

2.1 边连通度与节点连通度的定义

1)边连通度。

记为,其大小等于使网络成为不连通图所需去掉链路(边)的最少条数。它反映网络节点间的内聚程度,是网络可靠性的一个基本度量指标。例如:通过分析可知,所示的网络分割至少需要移除3条边,即边连通度。

2)节点连通度。

也成为点连通度,记为,其大小等于使网络成为不连通图所需去掉的节点的最少个数。同理,网络的连通度。从某种意义上讲,点连通度是比边连通度更重要的网络可靠性度量指标,这是因为在网络中去掉某个节点就意味着与之关联的所有链路将失去意义。

2.2 边连通度与节点连通度的算法

1)算法的基本思想。

通常,要求给定网络的边连通度,需要首先确定任意不同两点的链路割集。设和是的两个不同节点,所谓的一个链路割集是指这样的链路集合:若去掉其中所有链路,网络将被分割成两个分支,一个包含节点;另一个包含节点。假设是中所有链路割集中链路的最小数,则就是切断和之间所有路由所需从中删去的最小链路数,故网络的边连通度可按(1)式计算:

2)网络边连通度计算步骤。

由前所述,计算网络边连通度的算法思路是:先按标号算法求分离任两点的最小链路数,然后,再求所有这些数的最小数即可。但是,上述求的算法是针对有向图给出的,而网络边连通度是针对无向图的,因此,算法需首先将原无向网络转换成等效的有向网络。具体计算步骤如下:

1步:对给定网络,任选一对节点和,按下面的步骤求分离和的最小链路数: ①首先将转换成有向图。方法是:将链路集中以为端点的链路转换成中以为起点的到相应节点的有向链路,将中以为端点的链路转换成中从相应节点到节点的有向链路,又将中其他链路转换成中2条有向链路和。

②用标号算法,求中分离与的最小链路数。

2步:对所有节点对,,重复上述步骤计算,最后计算:,即网络的边连通度。需要注意的是:由于,对于含有个节点的图,第2步中需要计算的共有个。

3)网络节点连通度计算步骤。

算法的思路是:将割点问题转换成割边问题,从而使求网络节点连通度的问题转换成求网络的边连通度问题。转换的方法是:在网络中任选一对节点和,首先,类似于边连通度算法一样,将转换成有向网络,然后,再将构造另一个有向图,构图规则是:将中除和外的每个节点拆成2个新的中的节点和,并用中的有向链路将它们连接起来。将中每一链路换成中的链路,并把标为,标为。

由构图规则可知,在新的网络中,从发点到收点的包含节点的一条路由,必定包含一个顶点拆成的两部分之间的那条弧。并且原图的一对相邻点及其间的边被转换成等效的由4个节点组成的“8”字形有向回路。因此,一个链路割集在切断中到的所有有向路由方面,与在原始无向图中去掉节点割集有相同作用,即中等于中。综上,可得网络节点连通度算法计算步骤如下。

1步:对原网络的任一节点对和,按上述规则构造新的有向网络,并用标号法求中分离和的最小链路数,即中分离和的最小割点集点数。

2步:对所有节点,计算,即得的边连通度。

3 结论

本文讨论了通信网络可靠性的层次划分与影响因素,针对性的分析了拓扑层可靠性的指标与测度,指出了“连通度”作为拓扑层可靠性基础测度,以及其对其它测度设计的重要性。同时,详细分析了节点连通度与边连通度的计算思想与算法步骤。最后,通过一个相对简单的算例演示了通过边与节点连通度计算来评价某一通信网络拓扑可靠性的主要流程。

参考文献

[1]罗鹏程,金光,周经伦.通信网可靠性研究综述[J].小型微型计算机系统,20002110):1073-1077.

[2]陈建国.通信网络拓扑抗毁性评估算法研究[J].通信系统与网络技术,2006321):6-7.

[3]饶育萍,林竞羽,周东方.网络抗毁度和节点重要性评价方法[J].计算机工程,2009356):14-16.

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注视频

冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》
【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,辽宁省
【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
冀教版英语三年级下册第二课
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
沪教版八年级下册数学练习册一次函数复习题B组(P11)
冀教版小学英语四年级下册Lesson2授课视频
化学九年级下册全册同步 人教版 第22集 酸和碱的中和反应(一)
【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,辽宁省
苏科版数学 八年级下册 第八章第二节 可能性的大小
北师大版小学数学四年级下册第15课小数乘小数一
沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
二年级下册数学第三课 搭一搭⚖⚖
沪教版牛津小学英语(深圳用) 五年级下册 Unit 7
3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436
七年级英语下册 上海牛津版 Unit3
冀教版英语五年级下册第二课课程解读
二年级下册数学第一课
30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》
沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs
第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
冀教版小学数学二年级下册1
沪教版八年级下次数学练习册21.4(2)无理方程P19