基于蚁群优化的大规模自组网MPR选择算法

朱天林，王傲，杨锦彬，李大鹏

（南京邮电大学通信与信息工程学院，江苏 南京 210003）

0 引言

近些年来，在民用领域和军用领域，移动自组网的发展变得越来越引人注目，其中无人机（UAV,Unmanned Aerial Vehicle）凭借其体积小、成本低、便于部署等优势[1]在实时监控、搜寻救援、中继传输、战略打击等方面都得到了广泛的应用[2-3]。然而无人机自组织网络具有节点移动性强、网络拓扑变化快、数据交互频繁、能量消耗大等特点[4]，传统的路由算法已经无法满足其对网络传输延迟、丢包率、路由开销等方面的要求。

最优链路状态路由（OLSR,Optimized Link State Routing）协议是一种经典的链路状态协议，通过在节点间广播Hello 分组来完成链路探测、邻居发现以及多点中继（MPR,Multi-Point Relay）节点的选择[5]。利用拓扑控制（TC,Topology Control）分组在获取MPR 节点信息后建立和维护网络的整个拓扑，并最终运用Dijkrastra 算法计算路径，生成路由[6]。其中MPR 节点的选择至关重要[7]，每个节点都只会将其TC 分组发送至其对应的MPR 节点，以减少网络间的控制包数量。文献[8]提及，选择最优的MPR 集是NP 难问题。传统方式往往采用贪心算法对MPR 集进行选择，优先选取覆盖源节点二跳邻居最多的一跳节点。这样会造成很大的冗余，进而导致协议的开销增大、网络间的延迟上升。很多学者都从不同角度上对MPR 的选取算法进行了改进。文献[9-10]采用最小最大算法，以减少每个节点上的TC 分组数量。文献[11]提出一种基于集合的MPR 选择算法，通过结合循环和集合操作，可以有效地消除无效的冗余节点。在文献[12]中提出了基于扩展为三跳的相邻节点的本地数据库的MPR 选择，MPR 的选择使用OLSR 中现有的算法，结果表明，其在TC 数据包数量和能源效率方面优于标准OLSR。

蚁群算法（ACO,Ant Colony Optimization）是对现实世界中真实的蚁群觅食行为的抽象和改进，是一种智能优化的启发式算法[13]。蚂蚁通过在觅食过程移动时所留下的信息素来向其他蚂蚁传递信息，其他蚂蚁根据不同路径信息素的浓度来决定其下一步路径。该算法的优势在于其搜索具有全局性，而传统的贪心算法无法考虑到全局的情况，往往陷入局部最优[14-15]。蚁群算法利用随机概率选择下一跳路径，当信息素积累，概率增加到1 时，算法便会退化为贪心算法。单一的蚁群算法虽然在贪心算法的基础上有所改进，但仍然存在迭代时间过长而陷入局部最优的问题[16]。

本文结合蚁群算法的全局搜索能力，考虑到无人机自组网的特性，将本地节点三跳邻居数据库引入到蚁群的路径选择函数中。同时考虑节点的速度，对ACO 算法原有的路径选择以及状态更新机制进行了改进，将蚁群优化应用于求解MPR 集合问题中，达到了优化MPR 集合的目的，最后将其集成于Qualnet 网络仿真软件系统中，很好地验证了本文所提出算法的性能。

1 系统模型与问题分析

MPR 多点中继的原理是在转发广播信令包时，只有被选为MPR 的节点才具有转发的权利，其余节点对收到的消息进行处理但并不转发。每个节点都会从自己的一跳邻居中选取若干节点作为自己的MPR 节点，该节点为其转发协议的TC 分组[17]。下面是传统MPR 集合选取问题的数学描述。

贪心算法求解步骤为：

步骤1：从源节点出发，将所有一跳邻居纳入集合S1，将所有二跳邻居纳入集合S2；

步骤2：计算S1 集合中每一个节点的一跳节点的邻居个数n（不包含源节点及S1 集合中的点）；

步骤3：选取n数目最大的一跳邻居，添入MPR 集合，从源节点一跳邻居集合S1 中移除，并将其对应源节点的二跳邻居从S2 中移除；

步骤4：重复S2～S3 直到S2 集合为空，所选的MPR集合即为所求。

贪心算法的优点在于计算与实现简单，但是其结果往往会产生冗余。当考虑图1 的拓扑时，针对源节点1，其S1 集合={2,3,4,5,6}，其S2 集合为{A,B,C,D,E,F,G}。经由贪心算法所得的MPR 集为{2,3,4,6}，而实际最优的MPR 集为{3,4,5}，这就导致了选取节点的冗余。

图1 贪心算法计算冗余的示例

此外贪心算法求解的MPR 集合仅仅考虑源节点一跳邻居对二跳邻居的覆盖度，对节点的移动性、链路的状态质量等都没有考虑，已经无法适应越来越多变的自组网环境。鉴于上述所提出的传统贪心算法的各种不足，本文采取了蚁群优化算法对MPR 问题进行建模并求解。

2 基于节点状态的动态更新蚁群算法

2.1 目标函数

在当前的MPR 选取问题中，假设共有m个节点，其中源节点为A，定义源节点的一跳集合S1，且|S1|=n，源节点的严格二跳邻居集合S2，源节点的严格三跳邻居集合S3，其中|S1|+|S2|+|S3|+1=m。假设共有k只蚂蚁，resk代表第k只蚂蚁在当前迭代中所得到的MPR 解集合中的元素个数。targetj∈{0,1}(j=1,2,...,n)代表对当前蚂蚁是否将S1j选入MPR 集合。对于每只蚂蚁，其最优解。对于该问题，全局的最优解bestSolu=min|resk|。本算法的目标是在考虑无人机网络节点移动性的同时，不断优化resk的取值，使得最后所得的bestSolu取得理想的最小值，以适应当前复杂的无人机自组网的需要。

2.2 节点路径选择

蚁群算法的全局搜索能力就在于其下一跳路径的选择不是绝对的，蚂蚁在移动过程中，会动态更新信息素、权值等关键信息，并依据这些因素选取最符合的路径。令表示蚂蚁k选择节点i(i=1,2,...,n)作为下一个选入MPR 集合的节点的概率，可得：

其中，α表示信息素的启发式因子，β表示两跳权重的启发因子，γ表示三跳权重的启发因子，ε表示节点相对速度的启发因子，且α∈(0,1),β∈(0,1)，γ∈(0,1)，ε∈(0,1)。α的值越大，当前蚂蚁收到其他蚂蚁遗留信息素的影响就越大，β、γ、ε代表了对应启发因子的重要程度。当α为1，β、γ、ε为0 时，蚁群算法就退化成了传统的贪心算法。

τ(i)表示节点i上持有的信息素的浓度，μ(i)表示节点i所覆盖源节点二跳邻居的权重，η(i)表示节点i所覆盖源节点三跳邻居的权重，υ(i)表示目标节点i移动速度对概率选择的影响公式，allowed(S1)k表示蚂蚁k允许加入其MPR 集的节点集合。

对于η(i)，引入三跳邻居的本地数据库加入MPR 的附加决策函数中，可以达到进一步优化MPR 的目的[10]。

2.3 信息素的更新

蚁群算法中，路径上的信息素会随着所经过蚂蚁的增加而不断累积，往往大量已走过的非最优路径上的信息素浓度不断累积，而未被选择过的路径上信息素浓度不断降低，真正可能的最优路径或许就存在于未被选择过的路径中，这时算法就陷入了局部最优解中。

为防止算法收敛于局部最优解或者收敛过慢，本文采取了全局信息素更新规则对路径上的信息素进行更新。相较于传统ACO 算法对所有到达目的节点的蚂蚁所经过的路径上的信息素进行更新，本文对当前迭代过程中的最优路径进行进一步的信息素积累，对最差路径进行进一步地挥发来予以惩罚。这样有利于更快地排除相对较差的路径，同时突出较好的路径，从而加快算法的收敛，减少算法陷入局部最优的概率。

信息素的更新公式如下：

其中ρ为阶段性的信息素的挥发率，τi(t)为更新前节点i上的信息素增量，τ(t+i)为更新后节点i上的信息素增量，具体定义如下：

其中itecur代表当前的迭代次数，itemax代表设置的最大迭代次数。

其次，由于每轮迭代的结果可能不同，这使得更多路径上的信息素将会得到积累，并且就阶段性的信息素挥发系数来说，挥发率的初值较高，有利于蚂蚁对所有路径进行更加全面的搜索，避免陷入局部最优。随着迭代次数的增多，挥发率不断降低，可以让蚂蚁逐渐汇集到最优路径上。

当信息素更新时，为防止某个最优节点被选取自身时，因为信息素过小而难以被选取，或者某个节点上的信息素浓度过大，导致路径搜索过程过早停滞从而错过更优的路径，为每个节点的信息素设置上限phemax，同时设置下限phemin，使得节点的信息素恒在[phemin,phemax]之内。

2.4 DNACO算法流程

整个算法的框架如下：蚂蚁的数目num_Ants、当前迭代次数ite、总的迭代次数total_iteration、每只蚂蚁访问过的节点数组visit、当前未被覆盖的二跳邻居节点个数Uncover_S2、当前蚂蚁选择MPR 集合大小cur_Solu和历史最优的MPR 集大小best_Solu，算法流程如下：

3 仿真结果与分析

为验证本文算法的可行性，实验使用qualnet 网络仿真平台进行仿真。该仿真平台基于PASREC 并行仿真内核，对于大规模自组网络，其仿真速度是其他仿真器的几十倍，并且包含的协议栈完备，能适应不同场景下的网络仿真[19-20]。

实验采用了qualnet 中的OLSR 协议，并将动态更新蚁群优化（DNACO,Dynamic Updating Ant Colony Optimization）算法加入到MPR 选择的过程中。在不同的网络拓扑和网络密集度下比较了采用贪心策略的MPR算法、ACO 算法以及DNACO 的性能，每个节点都采用qualnet 自带的Random Waypoint 移动模型，整个场景规模为1 500 m×1 500 m。整体实验的参数如表1 所示。

表2 给出了在不同数目节点下，三种算法求取MPR节点后对于网络性能的改善。

从图2 可以看出，当节点数目比较少的时候，三种算法选择出的MPR 集合近似相同，算法的性能差异不大。此时ACO 和DNACO 使用较大的权值启发因子，算法趋近于传统的贪心算法以加快迭代速度。随着节点数目的增加，DNACO 及ACO 较传统的贪心算法有了明显的改进。可以看出，DNACO 算法相较于ACO 算法时延降低了8.7%、网络丢包率降低了7.9%、吞吐量提高了5.7%。

表1 三种算法的仿真参数

表2 三种算法的性能对比

图2 三种算法时延、丢包率对比情况

4 结束语

传统OLSR 协议采用贪心算法求解MPR 从而造成冗余，无法适应现今大规模自组网络场景，针对这个问题，本文将蚁群优化算法应用于MPR 选择机制中，并且在蚁群算法的基础上，将节点的三跳邻居信息及移动信息添加进节点选择考量中，将动态更新添加入信息素更新机制中，提出了DNACO 算法。实验结果表明，当网络中节点数较多时，DNACO 选取的MPR 集合可能不是最小的MPR 集，但是其在降低网络延时和提高网络吞吐量时较传统的算法有明显的提高。因此，采用本文提出的DNACO 算法可以有效提高无人机自组网络的网络性能，降低开销。