一种面向网络编码组播树的随机拓扑生成算法

顾叶露， 刘晓红， 曲志坚， 张爱凤

(山东理工大学 计算机科学与技术学院， 山东 淄博 255049)



一种面向网络编码组播树的随机拓扑生成算法

顾叶露， 刘晓红， 曲志坚， 张爱凤

(山东理工大学 计算机科学与技术学院， 山东 淄博 255049)

摘要：为了建立满足网络编码需求的组播树，提出一种面向网络编码组播树的随机拓扑生成算法.首先依据总体布局随机网络拓扑生成算法，生成随机的雏形网络拓扑；然后结合网络编码组播树的拓扑特性，对已生成的雏形网络在孤点、连通性、度控制等方面进行修补，使最终生成的网络拓扑满足网络编码组播树的拓扑要求.

关键词：网络编码； 组播树； 随机拓扑

建立网络编码组播树是实现网络编码组播要求的重要基础，近年来研究人员在基于网络编码组播树建树和资源优化方面提出了许多重要算法.为对基于网络编码组播树建树和资源优化而提出的算法进行测试和评价，需要将所提出的算法应用于大量网络拓扑结构. 以此来测试不同网络结构下网络编码技术对网络性能的影响.其中就有基于时延、时延抖动以及网络编码资源最小化等多目标约束条件，曲志坚等人在基于遗传算法的网络编码方面做出了系列研究[1-2].

基于网络编码的组播跟传统组播对网络拓扑结构的需求有明显的区别，导致现存的各种随机拓扑生成方法无法直接使用.目前，对面向网络编码技术的随机网络拓扑生成算法大多是以经典的拓扑或在其基础上稍加修改为蓝本进行的[3].如蔡慧等人提出了一种基于K均值聚类的随机网络拓扑模型[4]，解决了在Waxman随机网络拓扑模型模拟过程中网络节点疏密不当、节点难以控制、难以生成连通图等缺点；姚文斌等人提出了一种基于总体布局的随机网络拓扑结构生成方法[5]，该方法生成的拓扑更接近真实网络，突出模拟网络的随机性.但上述随机拓扑生产算法都无法直接生成满足网络编码需要的随机网络拓扑.

为了生成符合网络编码组播树的网络拓扑，提出了一种面向网络编码组播树的随机网络拓扑生成算法，该算法基于总体布局随机网络拓扑生成算法，结合网络编码组播树在拓扑模拟建模方面的特性要求,进而生成符合网络编码组播树的拓扑结构.

1基于总体布局的随机网络拓扑生成算法

1.1算法梗概

基于总体布局的随机网络拓扑生成算法，可通过多次随机过程模拟生成随机网络，每次产生的模拟网络从顶点分布到模拟方式都不尽相同，符合真实网络多样性的特征，克服了随机网络拓扑很难贴近真实网络的缺点.基于总体布局的随机网络拓扑生成算法流程如图1所示.

图1　基于总体布局的随机网络拓扑生成算法流程图

实现随机网络雏形拓扑的过程如下.

(1)依据基于总体布局的随机网络拓扑生成算法，首先随机生成拓扑节点数目M，并依次为每个生成的随机节点从0到M-1进行标号.

(2)随机生成拓扑连接数N，表示M个随机节点中存在的连接的数目，其中N的取值范围必须控制在1

(3)随机生成N对随机数对(Ai，Bi)，表示随机生成了N条连接，其中每个随机对表示节点Ai与节点Bi之间有一条边直接关联，其中Ai∈{0,1,2…M-2}，Bi∈{0,1,2…M-1}，且Ai从闭区间[0，M-2]范围内随机产生，Bi根据Ai产生的节点序号从闭区间[Ai+1，M-1] 的范围内产生，这样做的目的是防止重边和自环问题的产生.

在图论中，所谓自环就是两个端点为同一顶点的边.在随机数对(Ai，Bi)的产生过程中，若Ai，Bi值的产生完全随机，也就是任何两个节点之间的连接是完全随机的并且均在[0，M-1]的范围内产生，有可能会在生成图中产生自环.例如，Ai和Bi的随机值为同一节点q，q∈{0,1,2…M-1}，即产生了(q，q)的连接，那么在生产的拓扑中节点q就会出现自环.

而重边则是由于随机拓扑为无向图，因此在随机数对(Ai，Bi)的产生过程中，当Ai和Bi的产生完成，在Ai+1和Bi+1的节点产生过程中，若与Ai和Bi产生的随机节点相同，即有Ai=Bi，Ai+1=Bi+1，或者Ai=Bi+1且Ai+1=Bi的情况发生，已产生的节点连接就会在后面的随机数对产生过程中重复连接，从而产生重边问题.

(4)在随机网络拓扑随机数对生成过程中，为避免重边和自环的产生，在邻接矩阵中只保留除去对角线元素外的右上三角部分，即，在产生的随机数对(Ai，Bi)中只保留Ai

(5)根据生成的N对随机数对，填充M*M阶随机拓扑的邻接矩阵GMM，在矩阵中元素1代表相应的两个节点有连接，元素0则表示两个节点间无连接.

1.2面向网络编码组播树的网络拓扑特性探究

网络编码组播树中从源节点到目的节点必须具有多条分离路径.因此要求给定的网络拓扑结构为连通图且每个节点的度必须大于等于2.上述算法能够生成较为随机的网络拓扑结构，但是生成的随机网络拓扑还存在一些无法满足网络编码组播树拓扑特性的问题.产生这些问题的主要原因是算法中的随机生成数对(Ai，Bi)的随机性，导致拓扑生成的过程中对于边和点的约束不充分.

下面对存在的孤点问题、不连通问题、度不可控问题进行探讨，其中描述的随机网络拓扑结构均以无向图来表示.

(1)孤点问题.孤点是无向图中度为0的节点，在无向图中孤点不与其他任何节点相邻接.上述算法容易产生孤点，对于基于网络编码的组播中仿真中，通常不希望孤点的存在.导致孤点存在的主要原因是在随机数对产生过程中若不对Ai和Bi进行限制，Ai和Bi可能只在一个小范围内产生，如果节点j(其中j∈{0,1,2……M-1})不在Ai和Bi产生的范围内，将会导致结点j不与任何其他结点有连接成为孤点.

(2)不连通问题.在无向图中，如果存在两个节点没有通路，则该图为不连通图.组播网络仿真过程中希望所有的生产图均为连通图.但是，上述算法在拓扑生成过程中，因有连接的两个节点(Ai，Bi)都是随机产生的，因此在节点连接问题上很有可能产生多个小范围的节点相互连接的问题，而在图的总体上没有联通的情况，也就是生产的随机拓扑可能存在不连通的问题.

(3)度不可控问题.为了满足网络编码需求，组播树中从源节点到目的节点必须具有多条分离路径.这就要求给定的网络拓扑结构是个连通图且每个节点的度必须大于等于2.由于上述算法在产生随机拓扑的过程中节点之间的相互连接是完全随机的，有些节点可能只与剩余节点中的一个节点相连接或者不与其他任何节点相连(即上述孤点)，就会使拓扑中产生度为1或者0的节点，不符合网络编码组播树对于节点度的要求.

总的来说，基于总体布局的随机网络拓扑生成算法，在雏形拓扑生成过程中，从顶点分布到连接方式都是随机产生，符合真实网络中拓扑结构多样化的特性，更加贴近真实的网络拓扑结构.也正由于拓扑生成方式的完全随机，生成过程中必然会产生以上描述的各个问题，从而使得生成的网络拓扑结构无法满足网络编码组播树的要求.因此，需要对上述算法进行改进，以生成满足网络编码组播树特定需求的随机网络.

2面向网络编码组播树的随机拓扑生成算法

在基于总体布局随机网络拓扑生成算法的要求下生成的雏形网络，存在一些不符合基于网络编码组播树对随机拓扑特征需求的问题，因此本部分在总体布局随机拓扑算法产生的雏形网络的基础上，针对存在的问题进行改进，使得算法生产的随机网络拓扑结构满足基于网络编码组播对随机网络的结构要求，面向网络编码组播树的随机拓扑生成算法流程图如图2所示.

对于孤点问题、不连通问题、度不可控问题的解决方案为：

(1)解决孤点问题.对于孤点问题的解决，通过遍历邻接矩阵GMM，找到第i行和第i列均为0 的节点i，i即为孤点，然后将孤点i与除该节点以外的，度数最小的节点相连，也就是遵循度数最小节点优先选择的原则，将有问题的节点与优先于度数最小的节点相连接，这样就将孤点重新融入到已生成的随机网络拓扑图当中.这样做的同时也改变了某些节点的度数，为后续度不可控问题减少了工作量.

(2)解决不连通的问题.首先深度优先遍历生成的整个雏形网络拓扑图，查找全局网络拓扑的连通分量数目，如果连通分支数量大于1，则说明该拓扑图为非连通图.对于该问题，根据连通分量的数目将每个连通分量看作一个单独节点，重复全局随机生成连接的方式，生成各个连通分量间的拓扑连接，在两个有连接的连通分量中，随机产生连通分量内部具体节点对方的节点相连.

图2　面向网络编码组播树的随机拓扑生成算法流程图

(3) 解决度不可控问题.对产生的雏形随机网络拓扑图中的每个节点的度数实时更新，记录每个节点度数，若有节点不符合网络编码组播树对于节点度数的要求，依据度数小节点优先选择的原则，将不符合要求的节点，在本课题中即为节点度数不足2的节点，与除该节点外剩余节点中度数最小的节点相连，使得在改变自身节点度的同时，也在改变其他的节点的度数，为后续的重复操作减少了工作量.更新各节点度数，重复操作，直至每个节点的度数符合网络编码组播树对节点度的要求，实现节点度的控制.

3仿真结果分析

为了验证改进后算法的有效性，对算法进行了仿真实验分析.本实验使用C#语言在Visual Studio 2012开发环境下，基于面向网络编码组播树的随机拓扑生成算法设计实现了随机网络生成系统.为保证实验结果的可视性和可参考性，本课题将M的随机范围限制在[5，40].

随机生成的雏形随机网络中，随机节点数M=15，随机连接数N=29，雏形网络拓扑如图3(a)所示，在拓扑图中可以看出，生成的随机网络拓扑图中节点0、节点2、节点7度数不可控制，不符合网络编码组播树对于网络节点度数至少为2的要求.修补过程中，首先记录度数不可控的节点，然后将除节点0以外的所有节点排序，找到度数最小的节点，将节点0与度数最小节点相连接，保证了节点0的度数至少为2，以此类推可使得节点2与节点7度数完全符合网络编码组播树的需求，最终成形扑如图3(b)所示.

(a) 雏形网络拓扑　　　 (b)成形络拓扑图3　M=15，N=29的随机网络拓扑图

如图4(a)所示的雏形网络拓扑中，随机节点数M=14，随机连接数N=18，存在孤点9，同时生成的拓扑图因孤点9的存在,形成了具有两个连通分量的非连通图.对于孤点的处理，采取的措施是：将孤点9重新融入到由剩余节点形成的连通分量当中，在该连通分量当中寻找节点度数最小的节点，将其与孤点9相连.这样操作不仅解决了孤点的问题同时也解决了非连通图的问题.孤点问题解决之后，图中还存在度数不可控的节点，操作过程与图3的处理过程类似，在此不做赘述.最终成形拓扑如图4(b)所示.

(a) 雏形网络拓扑　　　　　　　 (b)成形络拓扑图4　M=14,N=18的随机网络拓扑图

4结束语

面向网络编码组播树的随机拓扑生成算法在总体布局随机网络拓扑生成算法的基础上，结合网络编码组播树对于网络拓扑的特殊要求改进基于总体布局随机网络拓扑生产算法.根据随机网络算法生成的雏形网络，在满足网络编码组播树拓扑要求的条件下，对得到的雏形网络进行修补，主要针对雏形网络中的孤立点、不连通以及节点度不可控制等不满足网络编码组播树需求的特征进行修整，使得生成的随机网络更加符合网络编码组播树的拓扑仿真需求.

参考文献:

[1]Qu Z J, Liu X H, Huang J J, et al. Genetic local search algorithm for network coding resources minimization [C]// 2012 IEEE International Conference on Computer Science and Automation Engineering, 2012: 782-786.

[2]Qu Z J, Liu X H, Fu J. Genetic algorithm-based network coding resources optimization in multimedia network [C]//2012 International Conference on Systems and Informatics, 2012: 1 547-1 550.

[3] 张宇,张宏莉,方滨兴.Internet拓扑建模综述[J].软件学报,2004,15(8):1220-1226.

[4]蔡慧,刘洪波,韩国栋.基于K均值聚类的随机网络拓扑模型[J].计算机工程与设计,2009,30(5):1 089-1 091.

[5]姚文斌,韩司,姚翔.一种基于总体布局的随机网络拓扑结构生成:中国,103457860 A[P].2013-09-03.

(编辑：刘宝江)

Research on network coding based multicast-oriented random topology generation algorithm

GU Ye-lu, LIU Xiao-hong, QU Zhi-jian, ZHANG Ai-feng

(School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China)

Abstract:A novel random topology network algorithm was presented to meet the requirements for establishing the network coding based multicast tree. Firstly, a primitive random topology was generated according to the overall layout random topology network. Secondly, the obtained primitive random topology was repaired in terms of solitary point, network connectivity, degrees of each node to remove the negative effects of unsuitable for establishing network coding based multicast tree. Finally, the proposed algorithm was tested, and the results indicated that the generated random topology meet the requirements of establishing the network coding based multicast tree. The proposed algorithm can provide plenty of simulation resources for the network coding based multicast research.

Key words:network coding； multicast tree； random topology

中图分类号：TP393.0

文献标志码：A

文章编号：1672-6197(2016)02-0001-04

作者简介：顾叶露，女，jiangmi22@163.com； 通信作者： 刘晓红,女，Liuxh88@tom.com

基金项目：国家自然科学基金项目(61473179);山东省自然科学基金项目(ZR2014FM007);山东省优秀中青年科学家科研奖励基金项目(BS2013DX032);山东理工大学青年教师发展计划项目

收稿日期：2015-03-19