资源描述：
《基于遗传蚁群算法的 QoS多播路由算法在Ad Hoc网络中运用方法的研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于遗传蚁群算法的QoS多播路由算法在AdHoc网络中运用方法的研究随着网络信息的推广和普及，用户在网络时延、带宽等方面要求提供的保障越来越多，随之在AdHoc网络中提供QoS支持也就显得越来越重要。但是考虑到AdHoc网络节点并非是固定不动的，网络拓扑结构也是不断发生变化的，而且它们的存储容量和计算能力较低，并且能量也受到一定的限制，那么如何设计出满足多个QoS约束条件的多播路由算法便成为重要的研究课题。【关键词】网络节拓扑结构遗传算法蚁群算法传统的路由算法难以有效解决满足多约束的问题,但启发式算法可以解决这一
2、难题。它具有本质上的并行性和全局优化能力，已被用于解决QoS路由问题。蚁群算法的信息素积累到一定的强度之后向最优解收敛的速度迅速提高。本文对GAAC(GeneticAlgorithmandAntColonyAlgorithm)方法进行研究，目的是为了更好地解决AdHoc网络中的QoS多播路由问题。GAAC方法是利用具有快速全局搜索能力的遗传算法具和有正反馈收敛机制的蚂蚁算法，初期采用遗传算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解，从而获得时间性能和优化性能的双赢。lQoS多播路由问题是寻找一棵多播树Q
3、(a,A)满足以下约束(1)延迟约束：delay(p(a,d))WY,Y为最大时延。(2)带宽约束：bandwidth(p(5,d))2C,C为瓶颈带宽。(3)延迟抖动约束:delayjiter(p(a,d))WYL,YL为最大时延抖动。(4)包丢失率约束：packetloss(P(5,d))WF,F为最大包丢失率。使得多播树(S,M)的总费用cost(Q(a,A))最小。2基于遗传蚁群算法的QoS多播路由算法分析GAAC算法的基本指导思想是:先由遗传算法产生较优解，较优的路径留下信息素，其它路径不改变;然后在有
4、一定初始信息素分布的情况下再按照蚁群算法，充分利用蚁群算法正反馈性、并行性求精解。既能发挥遗传算法与蚁群算法在寻优搜索中各自的优势,又能克服遗传算法在搜索到一定阶段时最优解搜索效率低以及蚁群算法初始信息素匮乏的问题。但这种算法虽然能够有效地选择一条最优路径，但却忽视了一个问题，即实际网络的最优路径一经形成，那么所有的数据就将会选择最优路径传输。这就使得当负载较大时发生拥塞的可能性就比较大，并且一旦发生拥塞,要消除它将需花较长时间。这时如果采用拥塞回避的策略将可以获得较好的效果，从而实现网络负载均衡。3GAAC中的
5、遗传算法规则3.1遗传编码通用的遗传算法编码模式使得算法编码、解码过程都很复杂，并且算法的搜索空间会随网络规模增加而急剧增加，这就使得算法效率大大降低。本文根据网络路由的特点和遗传算法的编码原则，采用节点序列编码，对给定的路径的物理节点标识序列作为该路径的编码值，并保持不变，这种编码方式自然而且直观。3.2初始群体的生成采用随机方法从中选择若干个体组成初始种群，其具体做法是：首先精简网络，删除不满足QoS约束条件的节点及与之相连的链路，再删除不满足带宽要求的链路，得到一个新的网络拓扑。基于此拓扑图进行搜索，从源节
6、点开始，随机地选择一个与之相关联的节点，将两点相连；然后从选择的节点继续随机地选择与其关联的下一个节点，在连接时要判断是否有回路，如有就重新选择节点，一直循环至搜索到目的节点。3.3选择算子本遗传算法米用最佳保留选择机制，先将当前的解群体中适应度最高的个体结构完整地复制到下一代群体中，然后按照轮盘赌选择机制执行选择功能。4GAAC中的蚁群算法规则（1）路径选择规则。该策略增强了搜索的多样性,以避免过早陷于搜索停滞。（2）信息素初值设置规则。通过遗传算法得到了一定的路径信息素，因此把信息素的进行初值设置。（3）信息
7、素更新规则。即采用局部更新和全局更新相结合的策略，既可避免蚂蚁在上次最好的路径有限相邻区域内搜索又对历史最优解的路径上的信息素进行了更新。（4）拥塞回避规则。通过节点的平均队列长度来衡量网络拥塞状态，以便向网络层实时提供传输信道的拥塞信息。5算法的实现过程（1）精简网络拓扑，删除不满足QoS约束条件的节点和与之相连的链路，再删除不满足带宽要求的链路，得到一个新的网络拓扑，基于此拓扑图进行搜索；（2）随机产生一组实数编码；（3）根据遗传算法进行若干次迭代，依据目标函数，生成网络初始信息素分布；（4）在源节点放置多只
8、蚂蚁，每个蚂蚁依据状态转移概率选择下一跳节点；（5）蚂蚁完成一步后，进行局部信息素更新，同时按照拥塞回避规则回避拥塞节点；（6）所有的蚂蚁完成一次循环后，进行全局信息素更新；（7）若满足结束条件及输出最优解；否则跳转到步骤4o6小结本文针对AdHoc网络QoS多播路由问题进行分析,对基于遗传蚁群算法的QoS多播路有时产生的拥塞问题进行了分析，采取拥塞回避策略，从而实现了业
