论文摘要
服务质量（Quality of Service, QoS）组播（multicast）路由是网络优化的难题之一。用启发式算法解决QoS组播路由问题，计算时间和代价会随着网络规模的扩大而急剧增大。遗传算法（GeneticAlgorithm, GA）由于具有较强的适应性、强壮性和灵活性，是求解QoS组播路由问题的重要手段。由于WANET（Wireless Ad Hoc Network, WANET）节点能量有限，与有线网络不同，无线Ad Hoc网络QoS组播路由问题需要考虑能量消耗。随着多媒体应用的飞速发展，QoS组播路由也需要考虑传输延迟和代价。本论文主要围绕华为技术有限公司研究项目“BGP路由协议硬件加速”和“IP流量探测技术”在无线Ad Hoc网络中的研究任务，从无线Ad Hoc网络的特点出发，对Ad Hoc网络QoS组播路由问题展开了深入研究，在QoS组播路由中考虑了传输延迟、路由代价、能量消耗、网络生存期和组播生存期。本文的主要创新性研究成果如下：（1）在无线Ad Hoc网络中提出了三个QoS组播路由问题，分别是：延迟抑制最小能耗组播路由（Delay-Constrained Minimum-Energy Multicast Routing, DCMEMR）问题，目的是为了保证多媒体应用的延迟约束，并同时减小组播的能量消耗；最大网络生存期最小代价组播路由（Maximum-Network-Lifetime Minimum-Cost MulticastRouting, MaxNLMCMR）问题，目的是为了减小组播传输代价的同时延长网络的生存期；延迟抑制最大组播生存期组播路由（Delay-Constrained Maximum-LifetimeMulticast Routing, DCMaxLMR）问题，目的是为了保证多媒体应用的延迟约束，并同时延长组播的工作时间。（2）提出了树结构编码法。树结构编码法用组播树本身来描述染色体，省略了遗传算法执行过程中的编码/解码操作，可以简化遗传算法，加速算法的收敛。（3）针对DCMEMR问题，提出基于遗传算法的延迟抑制最小能耗组播路由算法（GA-based Delay-Constrained Minimum-Energy Multicast Routing Algorithm,DCMEGA）。该算法的遗传算子能减小组播树的延迟和能量消耗，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且能量消耗最小，并且该算法能快速收敛。（4）针对MaxNLMCMR问题，提出基于遗传算法的最大网络生存期最小代价组播路由算法（GA-based Maximum-Network-Lifetime Minimum-Cost Multicast RoutingAlgorithm, MaxNLMCGA）。该算法的遗传算子能减小组播树的传输代价和能量消耗，变异算子能延长网络生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅传输代价最小，而且网络生存期最长，并且该算法能快速收敛。（5）针对DCMaxLMR问题，提出基于遗传算法的延迟抑制最大组播生存期组播路由算法（GA-based Delay-Constrained Maximum-Lifetime Multicast Routing Algorithm,DCMaxLGA）。该算法的遗传算子能减小组播树的延迟和能量消耗，变异算子能延长组播生存期，加速算法的收敛。实验结果证明该算法构造的组播树不仅满足延迟抑制条件，而且组播生存期最长，并且该算法能快速收敛。