基于遗传算法的路由选择问题的研究

《基于遗传算法的路由选择问题的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7卷第4期华北科技学院学报2010年10月基于遗传算法的路由选择问题的研究①申彦春②(唐山学院信息工程系，河北唐山063000)摘要：针对多目标优化问题，应用免疫遗传算法的基本思想，提出了一种求解满足带宽一时延约束多组播路径问题的两层遗传算法。在算法中设计了一种基于节点连接路径的具有树状结构的染色体表示方法及可以实现树状染色体交叉和变异的算子。数值实验结果表明，文中提出的算法可以有效找到多组播路由问题的优化解。关键词：多组播路由1'4题；免疫理论；遗传算法；QoS路由中图分类号：TP183文献标识码：A文章编号：1672—7169(2010)04—0081—03以抽象为一个赋权图(

2、G=V，E)，其中：O引言遗传算法是模拟自然界生物优胜劣汰、适者生存的法则进行科学研究的一种手段。在遗传算法中，个体的适应度是判断个体生存能力的唯一标准。通过对群体中的个体进行遗传操作，实现群体内部结构的重组，进而使群体的性能逐渐得到优化，最终接近最优解。然而遗传算法又是一种新型的优化技术，它今后的发展图1QoS路由选择问题的网络拓扑图还有许多工作需要去不断充实和提高。因此以图的顶点表示网络节点，图的边表示网络链遗传算法为主要研究对象，来求解实际问题是路，V=(V，V：，⋯，V)是代表路由器的所有交很有意义的⋯。换节点的集合，E=(E，E：，⋯E)是所有连接路1QoS路由问题由器的链

3、路的集合。QoS路由选择就是在图1中目前，在Internet中大部分是“尽力而为”查找满足网络QoS要求的路由，而QoS路由涉及(best—efort)的路由协议，并且采用“最短路径”的的度量参数一般包括：带宽、时延和代价等。寻径策略，因而无法满足多媒体信息传输的要求。2基于免疫遗传算法的QoS路由选择问题从网络用户的角度来看，基于QoS(Qualityof2．1QoS路由选择问题的数学：漠型Service，服务质量)的路由算法首先应保证满足用为了更好地分析问题和解决问题，为QoS路户的QoS请求，即寻找一条满足各种条件限制的由选择问题建立一个数学模型。在图1中，A、B、从源节点到目

4、的节点的传输路径。从服务提供商C、D、E表示路由，路由之间的连线表示相连的两的角度来看，基于QoS的路由算法应能最优化地个路由之间是通路，每条链路用(cost，width，de—使用网络资源J。lay)表示，分别代表这条通路的费用、带宽和时延。网络提供给用户的QoS是由网络的各种参根据上面论述的QoS路由选择问题应考虑数决定的。因此，RFC2216将QoS定义为：由可的因素和影响，可以认为带宽、时延和费用问题是用带宽、延时、延时抖动和包丢失率等参数描述的影响有关QoS路由选择问题的关键因素，但是如分组传输特性。网络要满足用户的服务质量要果在设计具体的路由算法时考虑所有因素，算法求，就

5、必须满足用户要求的QoS参数。势必太复杂而不能实际应用，所以应该针对不同一般地，网络的拓扑结构和链路状态信息可的实际需要设计相应的算法，处理不同的约束条①收稿日期．2010—08—29②作者简介：申彦春(1980一)，男，河北唐山人，唐山学院讲师，主要研究方向为：信号处理，控制工程。81第7卷第4期华北科技学院学报2010年l0月件。通过进一步的分析，可以知道通常在QoS组下面对流程图中的每一个步骤进行详细播路由选择时，由于延时和带宽是作为实时多媒介绍。体传输必须保证的基本条件，而费用作为评价网2．3生成初始种群络使用效率的重要因素，所以可以得到以上条件生成初始种群这一步需要通过三个

6、小的步骤下的约束条件：来完成，分别是对链路的编码、种群的初始化和链对任意一条链路来说(a，b)，D(a，b)表示通路的预处理。过该链路产生的延时，B(a，b)表示该链路的可用1)编码带宽，C(a，b)表示该通信过程中所需的费用。设由于遗传算法不能直接处理解空间的解数，之间的路径的延时为据，因此必须通过编码将它们表示成遗传空间的delay(¨，)=>D(0，b)(1)基因型串结构数据。遗传算法将求解目标问题编(口，b)一EP(口，6)码表示为“染色体”，在编码过程中，首先根据具P(“，)的可用带宽为体的路由拓扑图确定“染色体”的长度和各位所width(M，))(。，6)(2)tⅡ．DJ

7、∈，Iu．J代表的含义，再通过二进制表示出来，即将原问题P(M，)在通信过程中所需的费用为的解映射到位串空间，位串的每一位为0或1，以cost(，)=>C(口，b)(3)便在位串空间上进行遗传操作。(。，6)(o，6)从上述QoS路由选择问题的约束条件可以2)种群的初始化得到QoS路由选择问题的数学模型，为：由于遗传算法的群体型操作需要，必须为遗cost(T)=min(>c(Ⅱ，b))传操作准备一个由若干“染色体”组成的初始群、(n，_EEr体。初始群体的