基于进化算法的下一代网络QoS组播路由算法

浩庆波，徐岩

（曲阜师范大学网络信息中心，山东济宁，273100）

1 网络模型

组播路由是将发送者和多个接收者之间实现点对多点的信息传输技术。组播路由技术的使用，能够降低网络出现拥塞的可能性，从而提高数据在网络中的传输效率。组播路由技术是以数据源节点为根节点，依据网络结构和数据传输约束在多个目的节点之间构建组播路由树，以完成组播数据的传输。通常我们借助于斯泰纳(Steiner)问题对组播路由问题进行研究。在Steiner问题中，求解其最小树MST(Minimum Steiner Tree,MST)的过程即是求解最小的组播树的过程。

为更为直观的描述组播路由问题，我们使用有向赋权图G = ( V,E) 描述计算机网络，其中V表示网络节点集，E表示通信链路集。在通信网络中，我们对每一条通信链路 Vi都定义三个加权值进行描述，其中均为正实数。Bij表示节点i与节点 j之间链路的带宽，Cij则表示节点i与节点 j之间链路传输数据的代价，Cij值的大小也反映出该链路资源的使用情况；Dij表示节点i与节点 j之间链路的传输延时。为简化网络模型，假设网络中每两个节点的双向链路权值相等，即。且网络中每两个节点最多存在一条连通链路。

组播问题即为花费最小代价将数据从源节点s∈V发送到一组多个目的节点 D ⊆V-{s}。组播树为,其中。可知组播路由树满足如下几个条件：

从源节点s到所有目的节点d∈D的所有路径中，最小带宽为组播树T的带宽

从源节点s到目的节点d∈D的所有路径中，最大延时为组播树T的延时

带宽和延时是网络中最为主要的评价参数。现规定B为组播树T的最小带宽约束，Δ为组播树T的最大延时，则组播树T需满足：

组播路由树的寻找方法通常是采用例如SPH算法，KPP算法等启发式的方法。启发式算法存在运算复杂度过大，收敛性能差等问题。

2 基于进化算法的组播路由算法

2.1 基于蚁群算法优化的组播路由算法

蚁群算法(Ant Colony Optimization)是基于种群的一种模拟进化算法，由Dorigo等人首先提出。借助于蚁群算法对组播路由算法进行优化，简称OQMRA算法，步骤如下：⑴首先对网络进行初始化，即对网络中的相关信息素进行赋值初始化。对每一个节点链路(Bij,Cij,Dij)，进行初始化赋值。定义每条链路边(i，j)的信息浓度，并初始化信息浓度值r。⑵根据需求从源节点释放出M只蚂蚁进行探路，蚂蚁按照规则进行路径选择，即每只蚂蚁都执行步骤(3)。⑶首先确定蚂蚁自己所节点的临近节点集合，然后从中随机选择一个节点，按照重复应用状态选择规则选取行走路径。当蚂蚁选择路径并行走成功后，依据局部更新规则对蚂蚁所选择的路径信息素进行更新。⑷对每一只蚂蚁都重复执行步骤(3)，直至M只蚂蚁都更新完路径信息素。⑸当所有蚂蚁都完成路径选择后，根据M只蚂蚁选择的路径选取全局最优路径，即代价最小的路由路径。依据全局更新规则更新全局路径信息素。⑹重复执行直到达到迭代次数的要求为止，根据结果获得最优路径。

OQMRA的算法特点：⑴在OQMRA算法中，若蚂蚁数量M值过小，则产生的信息素不能够反映出选取路由的行为；反之，若M的值过大则会加重网络负担并导致网络性能恶化。依据经验，通常定义M的值等于网络节点数N。⑵根据算法描述，不难计算出OQMRA算法的初始化复杂度为 O (N2⋅W)；每只蚂蚁的MST的复杂度为 D (X ⋅M⋅N2)，更新 r(t)的复杂度为O(X ⋅M⋅N2)，其中W为网络顶点数，N为节点数，X为循环代数；OQMRA算法的总复杂度为

2.2 基于粒子群算法优化的组播路由算法

粒子群算法，也称粒子群优化算法（Particle Swarm Optimization, PSO）是一种具有收敛快、精度高等优点的新的进化算法。粒子群算法之所以也被称为鸟群觅食算法，其算法的实质就是模拟鸟群寻找食物的迁徙过程。在粒子群算法中，使用粒子群中每个粒子的运动方向来模拟鸟群中鸟儿的飞行方向，使用粒子每次移动变换的距离来模拟鸟儿的飞行速度。粒子群算法需要依靠粒子群的群体协作进行最优化选择，其实质是一种并行化的优化算法。

影响粒子群优化算法精度的关键在于算法的适应度函数。通过适应度函数计算粒子群中每个粒子的适应度值，适应度值是评判该粒子是否为最优解的关键指标。粒子群中每个粒子都知道当前群体的最优位置（即当前群体中最优适应度值粒子的位置）和局部最优位置（即该粒子最优适应度值的位置）。粒子群中所有粒子依据群体最优位置和局部最优位置更新自己的移动方向和速度，从而确定粒子新的适应度值和位置信息。

其中1≤i≤m，1≤d≤n，k为该算法的迭代次数（k≥1）。为随机数函数，生成[0，1]之间随机数值。c1,c2为非负数。c1表示粒子自身的认知系数，c2表示粒子的社会认知系数。vmax为最大的运动速度，该值通常由用户来设置，若vmax取值较大时利于全局范围内的搜索，但其搜索步伐过大容易错过最优解。反之，若 vmax取值较小，搜索步伐较小，有利于局部范围内精细搜索，但易使算法困于局部最优解。因此vmax的值需要根据问题经验进行设定。表示粒子前次运动的速度，使得每个运动的粒子在其搜索空间中能够向各个方向进行探索。为粒子自身的运动过程，粒子自身的运动过程其实质就是该粒子认知、探索的过程。则为某粒子学习其它粒子运动经验的过程，粒子群的粒子借助该式分享运动经验。若某个粒子没有自身的运动过程，那么称该粒子群为只存在社会部分模型。粒子群算法是借助于每个粒子间的互相协作来寻求最优解的，若所有粒子缺乏自身认知过程，那么该种粒子群就无法求解出问题域的全局最优解，且容易使得算法陷于局部最优解之中。

粒子群的算法步骤：⑴随机初始化粒子群中每个粒子的相关信息，包括粒子运动速度和所处位置。⑵结合需要解决的实际问题，给出合适的适应度值函数并算出粒子的相应适应度值。⑶更新粒子的局部最优解：对比粒子此时的适应度值和历史局部最优位置的适应度值。若粒子此时的适应度值大于该粒子历史局部最优位置的适应度值，则更新该粒子的历史局部最优位置和适应度值；反之，不进行更新。⑷更新粒子群的全局最优解：将全局最优位置的适应度值与粒子群中每个粒子的局部最优位置适应度值进行比较，若某个粒子的适应度值大于全局最优适应度值，则更新全局最优位置和适应度值。⑸根据粒子运动方向和速度，重新计算每个粒子的下一个所处位置和运动速度。⑹判断是否满足终止条件：若条件满足，算法结束，否则，返回第（2）步。

粒子群算法在求解最优解过程中具有鲁棒性强、收敛速度快、求解质量高等特点。但其在迭代过程中也容易陷入到局部最优解，从而不能准确找到全局最优解[9]。