基于遗传算法的QoS多播路由策略研究

(长江大学计算机科学学院，湖北 荆州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））最小，即目标函数为：

且有如下 5 个方面约束：① 延时约束。delay（R（s，d））≤Dmax，Dmax为最大时延；② 带宽约束。bandwidth（R（s，d））≥Bmin，Bmin为瓶颈带宽；③ 延时抖动约束。delay＿j（R（s，d））≤DJmax，DJmax为最大时延抖动；④ 包丢失率约束。packet＿loss（R（s，d））≤PLmax，PLmax为最大包丢失率；⑤ 能耗约束。energyrequire（n）≤energyremain（n），energyremain（n）为节点n当前剩余能量。

2 QoS多播路由策略

1）编码机制 每个节点赋予一个物理序号(ID号）。在一条从源节点到目的节点的路径上，按序将所有节点的ID构成一个序列，称为路径序列，其编码为（v1，v2，…，vk），长度为所经过的节点数。网络中存在多条符合多约束条件的路径，根据到达目的节点的不同，构成不同的子集；则一颗满足多目标约束条件的多播路由树就是在上述不同子集中各选择一条路径编号形成的集合。所采用的遗传算法的交叉和变异算子将对编码的路径进行操作，经过修补后构成新的路径编码集合，代表新产生的多播路由树。

2）适应度函数 适应度函数是衡量目标个体优劣的尺度。适应度值越高，表明个体越优化，即多播费用越小。笔者采用的适应度函数为：

其中：

式中，A、B、C、D、E分别表示延时系数、延时抖动系数、包丢失率系数、能量剩余量系数和颈瓶带宽系数；φd（y）、φb（y）、φdj（y）、φpl（y）和φe（y）分别表示时延、带宽、时延抖动、包丢失率和剩余能量的惩罚函数，当路由满足约束条件时值为1，否则值分别为λd、λb、λdj、λpl、0，其取值范围为(0，1），它们的大小决定惩罚的程度，可以根据具体业务要求来确定其值。可见，按照此规则进行路由选择时，尽可能选择时延小、带宽大、时延抖动小、包丢失率小和能量剩余量大的比较理想的路由。

3）初始化群体 采用路径回溯方法，获取网络中符合条件的所有路径，根据X中目的节点数目，随机选择相应数量的到不同目的节点的路径，将选择的路径编号组成集合，形成多播路由树，以此来生成初始种群，种群中的每一个个体代表一颗符合约束的多播树。

4）选择操作 采用最佳保留选择机制和轮盘赌选择机制相结合的方法，即首先将当前的解群体中适应度最高的个体直接复制到下一代，然后按照轮盘赌选择机制进行选择。

5）交叉算子 采用随机选择路径和一点交叉策略。首先在群体中确定进行交叉的2个个体，再从2个个体中随机选择2条路径，进行交叉操作。路径的具体交叉操作步骤如下：①随机产生一个整数作为交叉点；②进行个体交叉操作；③修补交叉操作产生的路径。由于交叉后产生的结果不一定是一条完整的从源到某个目的节点的路径，故需要对新产生的路由进行修补。加入结果路径之一为（v1，…，vi｜vj，…，vk），则需要判断vi和vj是否为相邻节点，若不相邻，就需要在vi和vj建立部分路径，将路径（v1，…，vi｜vj，…，vk）修改为不含回路的路径（v1，…，vi，…，vj，…，vk）。

6）变异算子 采用2点交换变异算子。当前的染色体，即多播树由符合约束条件的路径编号组成，随机选择其中的2条路径，与路径池中的目的节点相同的路径按照概率进行交换，等到新的满足约束的多播路由树。为避免变异可能破坏优良个体，降低算法搜索效率，变异后的个体需重新评估其适应度，只有当适应度值高于上一代群体的平均适应度时，新产生的个体才进入到下一代，此操作同时也提高了群体的多样性。当变异产生的路径不是一条完整的路径时，则需要进行路径修补，修补方法同交叉操作；若新的个体存在回路，在满足包含所有多播目的节点的前提下，删除总费用高的部分路由。

7）终止条件 当算法趋向于搜索停止时，即后面的每次迭代所得到的费用值之差非常小的时候，可终止算法，这里用最后5次迭代值的偏差作为衡量参考，其控制参数可设置如下：

式中，xk=costk（T（s，X））为第k次迭代后得到的费用值；为后5次迭代所得费用值的期望；1≤m≤Mmax（Mmax为遗传算法的最大迭代次数），当在最大迭代次数范围内，S＜10-3时可终止。

3 仿真结果分析

设定初始种群为60，最大遗传迭代次数为300次，交叉概率pc=0．7，变异概率pm=0．02。采用Matlab平台进行仿真，并从端到端延时、分组投递率来比较QoS-GA算法和AODV算法的性能。

1）分组投递率 分组投递率反映了网络传输的可靠性，也反映路由协议的有效性和适应网络变化能力，投递率越高，网络可靠性越大。节点移动会导致Ad Hoc网络拓扑结构的变化，变化的频度导致了网络性能的下降。不同节点移动速度下QoS-GA算法和AODV算法的分组投递率变化以及不同停留时间下QoS-GA算法和AODV算法的分组投递率分别如图1和图2所示。由图1可以看出，随着节点移动速度的增加，2种算法的包投递率都在下降，AODV算法包投递率下降的很快，而QoS-GA算法分组投递率下降的比较缓慢。由图2可以看出，随着网络节点的停留时间越长，2种算法的分组投递率都在上升，AODV算法分组投递率上升的速率比较缓慢，而QoS-GA算法分组投递率上升的速率要快得多。这些都符合Ad Hoc网络的特性，运动速度越快，网络拓扑变化就越激烈，路由开销就越大，必然导致丢包率的增加；节点停留时越间长，网络拓扑结构越稳定，路由开销就越小，节点分组的投递率自然会上升。这是由于QoS-GA综合考虑了延时、延时抖动、带宽和能量等QoS约束条件，因此具有较强的负载感知能力，倾向于选择延时小、带宽大和能量高的路径进行发送数据分组，QoS-GA算法的路径相对稳定，分组投递率较高。

图1 不同节点移动速度下的分组投递率

图2 不同停留时间下分组投递率

2）端到端的延时 端到端的延时即目的节点接收分组的时间与源节点分组发送时间的差。延时越小，说明节点的响应速度越快，网络质量越好。不同停留时间和不同节点移动速度下QoS-GA算法和AODV算法的端到端的延时分别如图3和图4所示。图3表明，随着网络节点的停留时间越长，2种算法的端到端延时都在下降，AODV算法端到端延时下降的速率比较缓慢，而QoS-GA算法端到端延时下降的速率要快得多。图4表明节点移动速度的增加，2种算法的端到端延时都在上升，AODV算法端到端延时上升的很快，而QoS-GA算法端到端延时上升较缓慢。出现这些情况是由于在仿真初始时刻，即在初始路由请求之后且路由信息没有建立之前，2种算法都有明显的延迟。随着时间的推移，AODV延时仍较大，并且延时下降的速度也比较慢，相比之下QoS-GA算法的路由时延较小，下降速度也较快，这主要是利用了遗传算法的快速收敛特性，能快速找到满足需求的路由，从而提高了路由算法的性能。

图3 不同停留时间下的端到端的延时

图4 不同移动速度下端到端的延时

[1]郑少仁，王海涛，赵志峰，等．Ad Hoc网络技术 [M]．人民邮电出版社，2005．

[2]金琼，周世纪，彭燕妮．基于改进遗传算法的QoS路由选择优化 [J]．计算机应用，2005，25（2）：256-258．

[3]王小平，曹立明．遗传算法-理论、应用及软件实现 [M]．西安：西安交通大学出版社，2002：4-50．

[4]邬长安，邵罕，孙艳歌．AdHoc网络中基于遗传蚁群算的QoS多播路由算法 [J]．计算机工程与应用，2008，44（20）：107-110．

[5]尹向东．基于遗传蚁群算法的QoS路由算法研 [J]．计算机工程与应用，2009，45（17）：113-115．

[6]黄晓雯，贺细平，唐贤英．基于遗传算法的QoS路由选择与仿真 [J]．计算机仿真，2003，20（6）：43-46．