通信网络拓扑结构分析研究:关于无线移动通信网络拓扑有效性的研究初探

通信网络拓扑结构分析研究:通信网络拓扑可靠性层次与测度研究

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

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

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

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

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

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

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

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

1.2 拓扑可靠性指标分析

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

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

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

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

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

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

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

（1）边连通度。

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

（2）节点连通度。

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

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

（1）算法的基本思想。

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

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

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

第1步：对给定网络，任选一对节点和，按下面的步骤求分离和的最小链路数：

①首先将转换成有向图。方法是：将链路集中以为端点的链路转换成中以为起点的到相应节点的有向链路，将中以为端点的链路转换成中从相应节点到节点的有向链路，又将中其他链路转换成中2条有向链路和。

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

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

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

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

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

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

第2步：对所有节点，计算，即得的边连通度。

3 结论

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

通信网络拓扑结构分析研究:关于无线移动通信网络拓扑有效性的研究初探

无线移动通信网络的拓扑结构会影响到网络的性能，关系到网络是否能高效、稳定运行。发现网络拓扑结构是对其进行高效管理的重要方面，它能揭示出网络中的节点地理位置、与临接点的关系、剩余电源、数据链路等信息。本文在较为理想的层次上通过仿真分析研究无线移动通信网络拓扑结构的有效性。

【关键词】无线移动通信网 拓扑结构 节点 有效性 链路

随着网络技术的发展和人们对网络需求的增大，无线移动通信网络也将不断扩大规模，功能变得更加强大，而网络结构也变得更加复杂，这个时候，网络管理水平就关系到无线网安全稳定运行水平。拓扑发现作为一项先进技术，在网络管理中起重要作用。网络的拓扑简单来说是就是网络节点的一种地图，标记出所有节点的地理位置以及连通情况，分析网络拓扑结构可以迅速发现网络的数据传输路径、网络的承载能力等，网络拓扑是监视网络运行的重要措施。

1 节点移动模型和链路有效性

1.1 节点移动模型

分析网络节点的移动方式与性能分析有关，目前的节点移动模型多是从速度和时间角度来进行的，通过节点移动的速度和时间来判断节点移动对网络性能的影响。由于实际上的无线移动通信网络中的节点移动是非常复杂的，为简化流程，我们假定其处于较为理想的传输环境，采用简单的二维随机移动模型来进行节点的移动分析。

在一个无边界限制的二维平面上，节点处于无序移动状态，在一个基本单位时间里，节点的移动速度是相同的，在进入另一个基本时间单元时方改变速度。所以，节点在X轴和Y轴方向的方向移动中的速度和位移量都呈现出零均值正态分布，所以，节点在时间n的坐标为：

1.2 链路有效性

对于某覆盖半径为R的节点来说，其他节点与该节点存在链路都必须满足r≤R的条件，否则的话就不存在链路关系。在一个无边界限制的二维平面上，其节点的密度为ξ/，那么半径为ρ的圆周中的节点密度为：fρ（ρ）=2πξρ。在进行节点的链路有效性测试时，就可以将该节点所覆盖的范围内所有节点在某时刻链路中仍存在的平均节点数与总节点数的比值作为该节点的有效性测试结果。

2 仿真分析

无线移动通信网络拓扑中的节点移动速度是有一定的限值的，我们最大的位移定义dm为：P{│Δx│>dm}=P{│Δy│>dm}≤ε，任何一个节点密度都存在σ=Kdm，本文将节点的密度定义为0.00135/，得出的K值为1/3。

2.1 链路有效性测试

为了确保仿真结果的准确性，进行多次仿真绘制仿真曲线，对覆盖范围的所有节点移动状况进行10000次仿真，然后绘制出仿真曲线图。

分析节点初始位置对链路有效性的影响，图1中的三条仿真曲线分别是节点初始位置为4、8、10m时的仿真结果。从图中可以明显看出，随着时间的推移，节点的链路有效性逐渐降低，当n=200时，三条仿真曲线的链路有效性相差不大，接下来的递减速度也放缓。n在0-50范围内时，不同初始位置的节点链路有效性随着时间的递增而迅速降低。到n=100以后，不同初始位置的节点链路有效性随着时间的推移递减的速度放缓。这说明初始位置对链路有效性的影响在节点移动的刚开始一段时间，节点移动的时间长了之后，初始位置对链路有效性的影响逐渐变小。

2.2 拓扑结构有效性

假定场景的节点密度为1/，dm为4，改变覆盖半径R的大小进行仿真分析。如图3所示为覆盖半径为4、8、16、32、64m时的仿真曲线图，随着节点移动时间的推移，拓扑结构的有效性也在降低。覆盖半径越大，拓扑结构的有效性越高，递减的幅度也越小。覆盖半径为4、8m时，拓扑结构有效性在节点刚开始移动是呈现急剧降低现象，到n=50后，拓扑结构的有效性降低速度放缓。

3 结束语

无线移动通信网络作为当前以及未来的主要网络形式，其拓扑的有效性关系到网络运行的稳定和安全。拓扑图中节点的无序移动会影响到网络的有效性，本文以理想状态下的网络运行环境为背景建立了二维平面节点移动模型，经过仿真分析，研究节点初始位置、节点覆盖半径大小、节点密度等对拓扑的有效性的影响，而现实环境中的网络拓扑受到的外界干扰更多，其拓扑有效性还有待进一步研究。

通信网络拓扑结构分析研究:基于遗传算法的通信网络拓扑优化研究

摘要:该文通过分析通信网络中的拓扑优化问题,抽象出数学模型,并利用遗传算法对该模型进行求解。最后通过实例验证用遗传算法求解该问题明显优于一些传统的算法,文中所建立的数学模型和算法能够正确地解决通信网络拓扑优化问题。

关键词:遗传算法;通信网络;拓扑;优化

随着信息化的发展,通信网络不断扩充新功能,发展新业务。这必然导致网络规模日益庞大,节点众多,并且网络拓扑的结构也越来越复杂。从而造成了数据信息的转接次数增多,迟延增加,维护难度增大,这就给现代通信网络的建设和管理提出了新的挑战。

对通信网络进行优化能够使其更加快速有效可靠地传递信息,避免和最大限度减少因网络中断或延迟带来的损失。遗传算法(GA)模拟自然进化过程,是一种具有并行特征的搜索算法,它能对解空间进行搜索,加快对解的搜索速度,便于推广到多结点的网络优化设计中,是解决大规模网络优化问题的有效工具。

1 遗传算法求解过程

遗传算法(GA)的主要特点是直接对结构对象进行操作,具有内在的隐含并行性和更好的全局寻优能力,自动获取和指导优化的搜索空间,自适应调整搜索方向,不需要确定的规则。

使用遗传算法求解通信网络的拓扑优化一般采用如图1的过程。

2 算法设计

2.1 编码和初始化种群

对于一个n结点的网络,其G图最多有n(n-1)/2条边,所以染色体的长度可定长为n(n-1)/2的二进制串。由于邻接矩阵具有对称性,因此只需使用该矩阵的上三角表示,这样可以使个体的长度为n(n-1)/2,压缩比为2。 所求问题可用图2的下(上)三角矩阵表示,称其为G的邻接矩阵T。如图2。

图2 G的邻接矩阵T

在上述编码方式中,则基因型可设为A[1,…,n(n-1)/2],由此可以生成W个基因个体,每个基因个体都是此通信网络的一种拓扑。

2.2 根据个体适应度进行选择

求解网络优化的数学模型属于求解目标函数最小值问题,适应度函数可设为

随着进化代数的增加,个体适应度之间的差别越来越小,可以对适应度函数增加一个比例系数a将其放大,f’(x)=af(x),a>1。

2.3 算法终止条件

当种群满足以下三个条件之一时算法终止并输出最优解。

1) 个体的最大适应度超过预先设定参数。

2) 个体的平均适应度超过预先设定参数。

3) 种群代数超过预先设定参数。

3 实验及结果分析

某通信主干网络节点数为9,经过多次实验后,选取POP=60,Pc=0.65,Pm=0.01, 并以最大代数max gen=3000做为程序的终止条件。其各节点间线路代价如表1所示。

经过该算法可得到计算结果如图3。

若采用枚举法,则时间复杂度为O(2N),此算法时间复杂度为O(N2),所以在对通信网络优化的同时,大大降低了时间复杂度。

4 结论与总结

通信网络的优化是一个复杂且涉及范围广泛的课题,是通信网络技术中不可缺少的部分。与遗传算法相比,传统算法比较复杂,局限性很大且计算时间较长。本文使用遗传算法较好地解决了通信网络优化问题。本文提出的算法对小规模通信网络的拓扑优化问题能够较好的求解,对大规模网络拓扑进行优化还存在不足。改进方法可以在遗传算法中融合其它优化算法,构成一种混合遗传算法。本文中对遗传算法在网络优化中的研究只进行了初步的探讨,要将这种方法完善还需要做进一步探讨和研究。