遗传算法在宽带通信网设计中的应用

南京邮电学院 王国华 张顺颐

　　摘要：本文讨论了使用遗传算法来进行宽带通信网络设计的研究方法,使用遗传算法对网络设计中的拓扑、路由和容量分配等方面的优化问题进行了详细的描述,并简要举例说明遗传算法的使用。

关键词：遗传算法,网络设计,通信网络,网络时延

　　一、引言

　　ITU-T对宽带业务定义为支持速率高于1.5 M bit/s（或者在ISDN、T1、DS1中数字术语的基本速率的传输通道能力）的业务。宽带网络主要是作为骨干传输网络使用,要求提供较高的带宽满足数据流量的突发性,可按需分配带宽,传输延迟小,节点多且连接关系复杂,节点发送数据类型多,流量差别大,并覆盖比较大的区域。随着网络的迅速发展,网络业务量成倍增加,以及网络应用日益增多,网络需要越来越高的带宽传输数据、声音、图像等大量信息；光纤的铺设解决了传输介质的带宽,网络瓶颈已经转化为带宽使用效率、交换能力、最佳或最短路由的选择等问题。使用遗传算法（Genetic Algorithm,GA）可以为这些问题提供快速简便的解决方案,但原有解决方案通常都是基于窄带网络的研究方法,当遇到宽带网络问题时这些方法并不完全适用。本文着重于研究使用遗传算法作为优化和研究工具为宽带网络设计提供一个比较标准的解决方案,并着重于网络路由的优化方法。

　　二、宽带通信网络设计相关参数

　　宽带网具有很大的传输带宽,主要研究的是网络的交换能力、路由选择、网络延迟和组织结构等方面。宽带网传输延迟主要是受交换能力和路由选择等影响形成的延迟。网络采用不同的交换技术对网络设计和业务具有一定的影响,主要体现在网络规模、费用成本、交换速率、QoS、多播支持和灵活性等方面。当前宽带网络的主要发展方向是宽带IP网络。

　　为了在通信网中将遗传算法用公式化的方法描述出来,下面给出通信网相关的研究设计参数定义。

　　● 链路设计：链路的设计包括链路的传输能力、带宽、容量、传输延迟等方面的因素。宽带网络的主干带宽非常大,链路的传输延迟、带宽和容量的限制一般情况下可以不考虑,设计中主要考虑的是租用链路带宽的费用以及带宽分配和利用率等。若一条连接共租用了b条链路,每条链路i上租用的Ci容量的费用用di（Ci）表示,那么这条连接的总租用费用D就是：

　　● 交换节点设计

　　交换节点设计包括交换能力、接口能力、延迟、封装延迟、路由等。

　　交换节点的交换能力对宽带网络有较大的影响,造成延迟的主要部分来自于此,因此交换能力往往会成为网络交换的瓶颈。节点交换能力包括交换速率、交换接口的吞吐量等,交换速率主要受到硬件性能、数据包分析和封装效率、路由选择算法和选择速率等影响,采用快速有效的路由选择算法可以极大的提高交换速率,交换接口吞吐量和吞吐能力的大小直接制约着链路带宽的使用率和传输时延,如果链路的流量大于接口的吞吐量会在节点缓冲中排队等候造成时延。如果交换节点的交换能力强则数据包的延迟小,交换能力弱则延迟增大,甚至会发生拥塞导致丢包的情况。

　　● 包延迟

　　宽带网络的平均包延迟主要由两方面构成：队列延迟和交换延迟。在宽带网络中链路传输延迟非常小,可以不予考虑。网络中到达节点的业务量是随机的,数据队列被存储在交换节点的交换缓冲区中,如果缓冲区溢出会导致数据包丢失。假设在一个设计比较好的网络中很少发生阻塞或者数据包很少丢失,那么这个网络就可以近似地认为具有无限大缓冲队列或者延迟系统。因此,队列延迟和交换延迟都可以用M/M/1队列来模拟。根据参考[3]中的平均等待时间计算公式可以计算延迟时间,平均等待时间计算公式为：

　　其中ρ=λ/μ,λ为到达率,μ为服务率。

　　以代表网络中链路的数目,和分别代表链路m上的容量和总流量,以bit/s为单位。是网络中交换的个数,和分别代表交换n的交换能力和总流量,也以bit/s为单位。σ是网络中的平均流量。则队列延迟和交换延迟计算如下：

　　队列延迟主要是由于主干接口吞吐能力的限制引起的,当链路上需要传输的总流量小于该链路的接口吞吐能力时该流量可以顺利传输,当总流量大于接口吞吐能力时则需要在缓冲中排队等候发送。在这个M/M/1队列中,到达率,服务率,由于传输延迟（即服务时间）小到可以不予考虑,主干队列延迟时间就是等待时间,带入公式1,得到平均队列延迟时间T1为：

　　交换延迟主要是由于节点的交换能力的限制引起的,当到达节点的总流量小于该节点的交换能力时该流量可以顺利进行交换,当总流量大于交换能力时就需要在缓冲中排队等待交换。在这个M/M/1队列中,到达率,服务率,由于宽带网中交换速率普遍提高,线速交换的大量应用,交换处理时间（即服务时间）可以忽略不计,交换延迟就是等待时间,带入公式1,平均交换延迟时间T2就是：

　　这样整个网络中（不包含传播延迟）平包延迟T就是：

　　需要指出的是,用遗传算法的解决方案不依赖于单一的延迟或者费用等结构的模型。对于不同的网络或者同一网络的不同需求可以具有不同的结构模型。

　　三、遗传算法简述

　　遗传算法是根据生物学上的染色体基因因子构成机制而产生的一种计算工程学。通过遗传算法可以找出最优解决方案。它是一种快捷、简便、容错性强的算法,可以直接对结构对象进行操作,易于优化和并行化,适应范围广。

　　遗传算法是具有“生产+检测”的迭代过程的搜索算法。它是一种群体型操作,该操作以群体中的所有个体为对象。选择、交叉、变异和重排序是遗传算法的主要操作算子。遗传算法的运算过程为：选择编码方式→产生初始群体→计算初始群体适应度→如果不满足终止条件则循环以下过程直到满足为止：选择→交叉→变异→（重排序）→计算新群体适应度。

　　四、使用遗传算法建立网络优化模型

　　网络的总体优化过程可分为拓扑优化、路由优化和容量优化等多种优化处理过程。下面对优化过程

进行具体描述,并建立相应的的网络模型。

　　4.1 基因因子表示方法

　　网络拓扑可以用节点间连接边的集合来定义,更直接的就是用邻接矩阵表示。一个n×n的布尔值矩阵中,如果节点x到节点y之间有边连接则a[x][y]值为1,否则为0。这是在假定链路是双连接的情况下,也就是说这是一个对称矩阵。这样只需要n（n-1）/2个二进制值就可以表示这个矩阵。为方便起见,二维矩阵可以通过如下公式转变为一维矩阵A：

a [k]=a [i] [j] [1]

　　这里,j > i,并且k =(2n - i)(i - 1)/2 + j - i容量、费用等参数也可以使用二维邻接矩阵表示,在这个矩阵中的因子值就是连接之间的相应参数值。一个n×n的矩阵中,如果节点x到节点y之间有边连接则a[x][y]对应参数值为C,否则为0,其中C就是这个相应的参数值。这是在假定链路是双连接的情况下,这个矩阵也是一个对称矩阵,只需要n（n-1）/2个二进制值就可以表示这个矩阵。为了方便起见,二维矩阵可以通过如下公式转变为一维矩阵B：

b [k] = a [i] [j] [2]

　　这里,j > i,并且k= （2n - i）（i - 1）/2 + j - i这样,代表网络的拓扑、容量或者费用等参数的染色体基因就可以用一个长度为n（n - 1）/ 2位的二进制串来表示,它等同于式[1]和[2]的矩阵A和B。这样选择、交叉、突变以及其他的遗传算法常规分析动作就可以分别运用到运算中来。并且在运算中,往往需要把A和B两个矩阵结合起来进行分析和研究。比如已知网络中两节点间的路由矩阵A和网络的费用矩阵B,就可以得出两节点之间的路由总费用D：

　　其中N为网络中的节点数量。通过遗传算法的运算改变节点的路由矩阵A就可以通过上式得到相应路由的总费用。

　　在实际的网络优化设计中,染色体的编码还往往采取域的概念,就是将某些相关的节点或者链路等基因因子结合在一起作为一个整体参加运算,并在运算中采取一定的运算规则,使得这个域中的基因因子同时发生符合某种规则的变化,这样可以大大简化和方便遗传算法的运算。

　　4.2 宽带网络优化中遗传算法的应用

　　首先讨论宽带网络优化中遗传算法的终止条件：网络设计中遗传算法的终止条件可以结合宽带网络设计的相关参数条件来采用某种判定准则,当判定出染色体集群已经进化成熟且不再有进化趋势时就可以终止算法的运行,常用判定准则有：连续几代个体平均适应度的差异小于某一个极小的阈值；或者群体中所有个体适应度的方差小于某一个极小的阈值。当优化过程中连续几代子染色体集群中的最优子染色体始终相同,或者总费用、总延迟等参数指标已经达到设计要求的标准,那么也可以判定已经到达优化的终止条件。也可以通过预先设定遗传运算发生的次数来终止遗传算法的运算。

　　选择运算：选择运算按照一定的比例在当前父染色体集群中选择一些优良的染色体复制到下一代子染色体集群中,继续进行遗传运算。在选择运算中为了防止出现局部最优化（早熟）的情况,可以采用加长编码长度或者结合模拟退火算法等其他算法的方法进行运算,降低出现局部最优的可能。交叉运算：以路由优化为例,可以将路由方案看作是染色体,路由染色体可以用下面的路径列表来表示：

P = {p1,p2,……,p n（n-1）/2}

这里,p k = Path（i,j）=[i,x1,x2,……,xe,j]是代表从节点i到节点j的路由路径的基因因子,i=1,……, n；k=g（i,j）

　　对于一个特定的路由方案P,链路的流量可以根据业务量需求来分配。这样,路由方案的适合程度可以用从容量分配优化中得到的最佳解决方案中得出。

　　对于父染色体P1和P2交叉运算得到子染色体P的运算中,

P1 = {p1,p2, ……, pn（n-1）/2}

P2 = {p’1 , p’2, ……,p’n（n-1）/2}

P= P1?P2 ={s（p1,p’1）,s（p2,p’2）,……,s（pn（n-1）/2,p’n(n-1)/2）}

这里,如果pi路径比pj短,否则一般交叉发生的概率为0.4--0.99。

　　突变运算：突变运算一般在交叉运算之后进行。为了使突变在二进制以外的实际应用中得以进行,可以采用随机突变,概率函数为：g = g + Ψ(μ,σ),其中g是真实值基因因子,Ψ是随机函数,一般是高斯随机函数,μ,σ分别是和随机函数有关的平均值和变量。

　　在通信网络优化设计的具体应用中,路由优化的突变运算就是将路由路径p重新随机选择一条可行路由；容量优化则是将链路L上的容量重新取值；突变发生的概率为0.0001--0.1。

　　重排序运算：染色体中基因因子的排列顺序对于染色体特性的决定是至关重要的。重排序的目的就是查找更具有进化潜力的基因因子序列。在路由优化中,如果进行重排序运算,有可能会发现一条新的更为优化的路由方案。重排序运算发生的几率非常小。

　　宽带IP网络路由是现代宽带通信网中的一项关键技术,现已有许多关于宽带IP网路由的协议和产品,但是几乎所有的路由协议都是以Dijkstra于五十年代提出的最短路径模型（Dijkstra算法）为基础的。当最短路径被阻塞时,数据包就被缓存以等待最短路径修复,这种路由策略并不高效,不能很好的反映网络的动态性,也难以有效的实现网络负载的分担,从而使得数据包在网络中的实际传输时间与期望值差别很大,网络带宽利用率低、传输延迟大和传输总费用高。宽带网络中数据传输的路由优化问题是宽带网络设计的重点之一,未来的智能路由器应该能够适应动态变化的网络,使数据包得以避免拥塞从而获取各方面的优势。遗传算法可以很方便的和现存路由协议结合起来,对通信网中的路由算法进行优化,以获得通信网的最佳路由。比如OSPF(开放式最短路径优先协议)中每个参与路由器都有网络的完全拓扑信息,可以用遗传算法与OSPF路由算法相结合进行路由优化和选择；另外BGP(边界网关协议)、RIP（路由信息协议）等路由协议的路由算法也可以很方便的和遗传算法融合。

　　五、应用举例以及分析

　　建立遗传算法的例程如下：

Chromosome GAs_Optimize(Chromosome Parent)

double xRate=0.5;//交叉概率

double mRate=0.05;//突变概率

double tRate=0.005//重排序概率

int Population_size=20;//父集群大小

int Sub_Population_size=20;//子集群大小

Population Pop(Population_size, Parent);//设置父集群

Population SubPop(Sub_Population_size);//设置子集群

GAs Optimize(Pop, xRate, mRate, tRate);//设置运算参数

Optimize.Evaluate(Pop);//计算群体适合度

While (Optimize.Terminate=FALSE) {//判断是否符合终止条件

Optimize.Select_Parent(Pop, SubPop);//选择操作

Optimize.Recombine(SubPop);//临时保存子集群

Optimize.Cross(SubPop);//交叉操作

Optimize.Mutate(SubPop);//突变操作

Optimize.Taxis(SubPop);//重排序操作

Optimize.Reinsert(Pop, SubPop);//将子集群重新插入父集群

Optimize.Evaluate(SubPop);}return Optimize.getbest();//返回最优化结果}

　　使用了遗传算法使得网络设计的限制问题变得简单化了。如图2所示的网络,该网络是一个双向传输网络,每条主干线上的数字代表该主干线的使用费用,现在要选择一条从节点A到节点F的最小费用的路由,而其他的因素暂时不予考虑。则该问题就是一个路由优化问题。

　　在这个通信网络中二维延迟矩阵为：

　　转换成一维延迟矩阵D为：

　　D = {AB,AC,BC,BD,CD,CE,CG,DE,DF,EF,GF}

　　　= {4,3,2,5,2,3,2,1,3,4,4}

　　要使用遗传算法进行分析,首先要正确选择遗传染色体基因的表示法,以及遗传算法的交叉、突变等运算的基本规则。针对该网络的优化问题我们制定规则如下：

　　1、染色体基因用位串编码表示,每一条主干传输线作为染色体基因的一个因子,一条主干传输线被选中则将对应因子标示为1,未选中则标示为0；

　　2、染色体基因分块表示,同一起点的链路的染色体基因因子放入同一个块中,从某一节点出发没有分支路由的链路因子也放入同一块中。

　　3、交叉运算中,块与块之间可以进行交叉运算,但块内的因子不能进行交叉运算；

　　4、突变运算中,以块为单位进行突变；无效主干传输线因子可自动优化并恢复为0。

　　根据以上规则,进行图2的网络路由优化。染色体的基因因子分块分为以下几块：AB、AC块,BC、BD块,CD、CE、CG、GF块,DE、DF块和EF块。随机选择两条染色体基因作为初始运算染色体集群：使用R1、R2作为父染色体集群进行遗传算法运算,得到的第一代子染色体集群为：继续进行遗传算法得到第二代子染色体集群为：

　　继续进行遗传算法运算得到的子染色体集群和第二代子染色体集群相比,最优子染色体基因仍然是R5,那么遗传算法到此终止。从子染色体集群中我们可以很清楚的得出结论,延迟最短的路由就是A郈郉郌, 次短路由是A郈郍郌。

　　如果网络链路发生了阻塞或者故障导致CG链路不能使用,那么就需要重新计算次短路由,染色体基因因子重新分块为：AB、AC块,BC、BD块,CD、CE块,DE、DF块和EF块。再次使用遗传算法进行计算,初始运算染色体集群为：运算得到第一代子染色体集群为继续进行遗传算法得到第二代子染色体集群为：

　　这里终止条件和上一次运算的终止条件相同。最短路由仍然是A郈郉郌,次短路由是A郈郋郌。在这个例子中,遗传算法的计算过程大概仅需要3个运算循环15 ~ 18次运算就可以完成,如果使用Dijkstra算法进行运算,那么所用的时间复杂性为n(n—1) 3/2,即n2量级,在这个例子中就需要7个运算循环72次运算。随着网络结构的复杂情况和节点链路数量的增加,与使用Dijkstra算法相比,遗传算法的运算速度更快,其优越性更加显著。

六、结论

　　宽带通信网络的优化是一个复杂且涉及范围广泛的课题,是宽带通信网络技术中不可缺少的部分。网络优化的传统方法有很多,比如梯度法、爬山法、模拟退火算法、列表寻优法等,但是他们的局限性也非常大,算法也比较复杂,在许多限制条件下不能有效的发挥作用。遗传算法由于其高效、快速等优点成为众多方法中比较好的一种。可以在遗传算法中融合其它优化方法的思想,构成一种混合遗传算法。基于遗传算法的网络优化方法是网络优化发展的主要方向之一。本文对遗传算法在网络优化中的应用只进行了初步的探讨,要将这种方法完善还需要做进一步探讨和研究。

七、参考文献

[1]Holland, J. H: Adaption in natural and artifical systems. MIT Press , 1975

[2]Thomas Back: Evolutionary Algorithms in Theory and Practice. Oxford University Press , 1996

[3]周炯磐：《通信网理论基础》,人民邮电出版社,1992

[4]盛友招：《排队论及其在计算机通信中的应用》,北京邮电大学出版社,1998

[5]周明、孙树栋：《遗传算法原理及应用》,国防工业出版社,1999

[6]叶敏：《程控数字交换与现代通信网》,北京邮电大学出版社,1998

[7]赵慧玲等：《宽带Internet网络技术》,电子工业出版社,1999

[8]William Stallings：《局域网与城域网（第五版）》,电子工业出版社,1998

[9]赵慧玲等：《ATM、帧中继、IP技术与应用》,电子工业出版社,1998

[10]陈国良等：《遗传算法及其应用》,人民邮电出版社,1996

[11]顾冠群等：《计算机网络》,江苏省科学技术出版社,1989

摘自《网络通信世界》