(长江大学计算机科学学院，湖北 荆州434023）

Ad Hoc网络是一种自创造、自组织和自管理的无线移动网络[1]，具有不需要固定基础设施、节点高移动性和动态变化的拓扑结构等特点，被广泛应用于军事信息通信、临时紧急网络会议、自然灾害的灾后恢复等领域。随着人们对无线网络通信的依赖度越来越高，在网络使用过程中，对网络的带宽、时延、时延抖动、丢失率等性能提出了更高的要求，这就要求Ad Hoc网络能够提供更好的服务质量（Quality of Service，QoS）保障，满足实际应用的需求。

基于Ad Hoc网络的QoS多播路由问题是一个多约束的NP问题[2]，传统路由算法很难适应Ad Hoc网络环境。遗传算法是模拟生物界自然进化优胜劣汰的过程，具有快速全局搜索的能力[3]。对此，笔者在分析Ad Hoc网络的QoS多播路由问题的基础上基于遗传算法设计了有效的QoS多播路由协议(QoS Routing Protocol based on Genetic Algorithm，QoS-GA），并通过 Matlab仿真验证了 QoSGA算法的性能。

1 QoS多播路由模型

Ad Hoc网络QoS多播路由问题可抽象定义如下：

定义1[4]网络拓扑可表示为加权图G=（V，E），其中，V为网络移动节点的集合；E为链路边集合。对于任意链路e∈E，有e=(vi，vj），vi∈V，vj∈V，i≠j，vi、vj为相邻节点。

定义2对任意链路e∈E，可用四元组（dalay（e），band＿width（e），delay＿j（e），cost（e））表示其QoS属性值，分别为链路的延时、带宽、延时抖动和费用。对于任意节点v∈V，用五元组（delay（v），packet＿loss（v），delay＿j（v），energyrequire（v），cost（v））表示其 QoS属性值，分别为节点的延时、包丢失率、延时抖动、所需剩余量和费用。用R（s，d）表示从源节点s到目标节点d的一条路径，T（s，X）表示多播树，s∈V为源节点，X⊆｛V-｛s｝｝为该多播树的端点或叶节点集[5-6]。则有：

QoS多播路由问题的目标就是寻找一颗能满足约束条件的多播树T（s，X），使其总费用cost（T（s，X））最小，即目标函数为：