基于改进粒子群的农田WSN 路由优化方法

缪祎晟，赵春江，吴华瑞

（1.北京工业大学 信息学部，北京 100124；2.国家农业信息化工程技术研究中心，北京 100097；3.农业农村部农业信息技术重点实验室，北京 100097）

0 概述

以无线传感器网络（Wireless Sensor Network，WSN）为代表的物联网技术，是实现农业生产中环境、土壤、动植物生理等实时监测以及温度、水肥在线调控的重要技术手段。通过对环境、水肥等进行精确感知与精准调控，可以减少不必要的水肥药消耗，提高农产品的产量与品质，实现绿色高效生产。WSN 本身具有能量敏感、成本低等特点，而大规模农田监测网络还存在覆盖区域广、种植周期长、能量供给不便、环境复杂多变等现实情况，如何实现稳定可靠的数据传输汇集是实际应用中的难点所在［1］。

在农田WSN 监测应用中，节点异构、环境动态变化等原因进一步提高了优化网络能耗和负载均衡的难度［2］。为提高农田环境下网络的使用寿命与长周期工作时的稳定性，本文从动态环境适配角度开展农田WSN路由优化研究，并提出一种基于改进粒子群（Particle Swarm Optimization，PSO）的路由优化算法RD-PSO。将农田WSN 路由路径作为粒子进行寻优，以链路质量、节点剩余能量等作为粒子参数并量化，优先选择链路质量好、剩余能量高的路径进行数据传输，以延长无线监测网络在农田WSN 复杂动态环境中的使用寿命。

1 农业WSN 路由研究现状

WSN 具有资源受限的特点，其网络能耗优化一直以来都是研究人员关注的焦点，而路由是实现低能耗传输的重要环节。孙想等［3］针对频繁簇首选举产生过多能耗的问题，提出一种能量逼近式的簇首选择方法，该方法连续任命某一节点担任簇首直至逼近簇内平均剩余能量，有效减少了簇首选举产生的开销，延长了网络寿命。李华等［4］提出一种基于近源数据聚合的低能耗路由协议，其根据WSN 中数据分布密度的不同来选择数据融合的节点组合与转发路径，实现了网络能耗下降与拥塞控制。黄博文等［5］提出一种K 中心的近似算法来挑选簇首，使簇内节点到簇首的距离最优，进而降低与均衡能耗。上述方法在优化WSN 网络能耗时均针对静态的网络条件，而农田WSN 监测应用中的环境是动态变化的，从而对网络路由优化算法提出了新的挑战。

群体智能算法［6］是求解复杂动态问题的有效手段，国内外学者在基于群体智能算法的WSN 路由算法优化方面开展了诸多研究。牛祺君等［7］设计一种基于节点剩余能量的簇首轮换机制，并通过蜂群算法优化簇首节点路由选择，减少了节点能量消耗，延长了网络寿命。谢英辉等［8］采用遗传算法缩短了sink 节点的移动距离，在简化网络拓扑结构的同时也得出了近似最优的能耗优化方案。ARJUNAN等［9］首先采用聚类算法进行节点分簇，再通过蚁群算法优化簇首节点间路由，提高了路由算法在宽矩形区域中的适应度。FU等［10］基于人工势场法，结合节点采集的数据判断节点所处环境的状况，进而使得优化后的路由尽可能地避开了一些不期望到达的节点。

利用群体智能算法可以在迭代次数较少的情况下求得动态条件下近似的全局最优解，算法效率高，适合于资源受限的农田WSN。针对农田应用场景下环境、作物生长等对无线网络传输的影响，本文提出一种基于改进PSO 的路由优化算法，通过引入网络链路质量因子提高PSO 算法的环境适配性，同时综合考虑节点剩余能量、路径转发跳数等因素，以期实现农田复杂动态环境下的能耗性能最优。

2 网络模型与定义

2.1 网络模型

本文讨论的大规模农田WSN 场景假定有N个传感节点随机地被部署在一个二维矩形区域内，同时假定该WSN 具有如下性质［2，11］：

1）网络属于密度较高的静态网络，即传感节点部署后位置保持不变，节点密度足以保证网络连通性以及对监测区域的覆盖度。

2）sink 节点位置固定且唯一，其无线发射功率可控且能量不受限制。

3）传感节点类型同构，初始能量均相同，为E0，且不能补充。

4）传感节点每轮消耗的能量不一定相同，即能量异构。

5）节点具有自我能量感知的能力，可获得剩余能量数据。

2.2 能耗模型

基于文献［12］的无线通信能耗模型，可以认为节点发送lbit 数据需要消耗的能量Etx为：

其中：Eelec代表发射电路或接收电路传输1 bit 数据消耗的能量；d为发射节点与接收节点之间的距离；d0=为模型的距离阈值；εf和εm为2 种模式下的功率放大系数。

3 基于反向探测的改进PSO 算法

农田WSN 中的路由选择是典型的组合优化问题，而群体智能算法具有自关联和自组织的特点［13］，适用于解决农田WSN 路由寻优问题。灰狼算法［14］、蚁群算法［15］等新兴智能方法具有参数少、结构简单、易于实现的特点，在WSN 路由协议优化方面已被广泛应用，但对于动态环境仍存在精度低、优化维数低、收敛速度慢等不足。在求解规模较大的优化问题时，PSO 算法能够在更短时间内获得优化解［16］，有利于农田感知数据的迅速传输。本文提出一种基于反向探测的改进PSO（Reverse Detection based PSO，RD-PSO）算法，通过改进算法的适应度函数与初始化方法减少网络传输能耗，进一步提高PSO 算法对路由路径的搜索迭代效率。

3.1 适应度函数构建与粒子更新

农田WSN 路由优化问题示意图如图1 所示，从初化化路径s1开始，通过算法迭代向最优路径s2逼近。优化过程中首先需要考虑的是降低节点能耗以及提高节点间的能量均衡性，因此，考虑从节点剩余能量和路径转发能耗2 个方面进行加权，优化算法适应度函数，即最优路径应满足路径能耗尽可能小、路径上节点平均剩余能量以及最低剩余能量尽可能高。同时，考虑到跳数对路由算法的效率以及网络能耗性能有显著影响，因此，在求解最优路径时需要使得跳数尽可能少。此外，由于农田环境具有动态多径衰落特性，因此本文将链路质量也作为适应度函数的权重因子之一。

图1 基于PSO 的WSN 路径选择示意图Fig.1 Schematic diagram of WSN path selection based on PSO

从图1 可以看出，当前路径和最优路径存在多个交点cross1，cross2，…，crossn，这些交点可以理解为路径选择中的关键点，也是WSN 常见的能耗节点，对于网络能耗优化有着重要影响。对于一次数据传输路径选择过程，记源节点到sink 节点的一条多跳路径为Pi，其对应PSO 算法中的一个粒子i，定义适应度函数f如式（2）所示［12，17］：

RD-PSO 算法根据初始化位置与速度计算个体最优和全局最优位置，并开始迭代寻优。粒子速度更新方法如式（3）所示［19］：

其中：ω是惯性因子；c1、c2是学习因子；r1、r2为0～1 之间的随机数，它们可使粒子变异时具有一定的随机性，避免落入局部最优。

粒子位置的更新方法如式（4）所示：

3.2 基于反向探测的粒子初始化

在基于PSO 的WSN 路由优化问题中，一个粒子初始化就是随机生成一条从源节点到sink 节点的路径。传统方法以sink 节点向网络发送探测包的方式，确定各个节点到sink 节点的跳数值［20］。在生成初始化拓扑时，当前节点始终选择跳数值小于自身跳数值的节点作为下一跳节点，并保留跳数小于所设定最大跳数的路径，从而保证路径方向总体趋向于sink 节点。传统探测包方法适用于管道、深井等带状空间，但由于缺少在横向空间上的约束，使得其在宽矩形区域中易出现迭代效率低等问题［21］。为此，本文提出一种针对宽矩形农田WSN 的反向探测粒子初始化方法。

在本文方法中，由sink 节点向其一跳范围内的传感节点广播发送探测包信息，传感节点接收到探测包后保存其距sink 节点的跳数值，并将值加1 后转发至其他节点，若某节点接收到多个值，则以收到的最小值作为其自身的值。由此近似地形成以sink 节点为圆心、半径不同的多个圆环，各圆环区域内的值相同。同时，为了建立横向维度上的重复路径约束，选择一条区域边界，如图2 中右侧边界所示，以最靠近边界的传感器（图2中的节点1）发送反向探测包，记节点1的值为1，其他转发节点的值增加方法与相同。

图2 基于反向探测的初始化过程Fig.2 Initialization process based on reverse detection

其中：eva（i）为根据Ni节点

值计算的节点得分，其值为i节点

差值的倒数，如式（6）所示：

3.3 RD-PSO 算法步骤

RD-PSO 算法在农田WSN 节点初始化完成后，按照3.2 节所述内容进行反向探测，完成粒子位置和速度的初始化，并依据节点能耗、剩余能量、距离sink 的最小跳数以及链路质量等构造适应度函数，通过粒子群迭代优化确定符合农田复杂动态环境的最优路由路径。算法具体步骤如下：

1）根据3.2 节内容进行网络节点反向探测，建立各节点到sink 节点的初始化路径Pi以及相应粒子i的初始化位置与速度。

2）按照式（2）计算每个粒子i的适应度函数值。

3）按照式（3）、式（4）求解个体极值、全局极值以及粒子位置、速度更新值。

4）重复第2 步和第3 步，直至个体极值稳定收敛于全局极值或达到最大迭代次数。

5）根据得出的最优路由路径开始进行数据多跳传输，同时获取节点能量、链路质量的数据，在下一步数据传输时进行路由路径更新。

根据上述算法流程可知，本文通过反向探测对传输路径、粒子速度与位置进行初始化优化，然后利用粒子更新得到农田WSN 路由。因此，本文算法复杂度为O(iter1·N1·T1(f))，其中：iter1为迭代次数；N1为粒子数量；T1（f）为与适应度函数、粒子维度等因素相关的一次迭代时间。灰狼算法的复杂度为O(iter2·N2·T2(f))，其中：iter2为迭代次数；N2为种群数量；T2（f）为与适应度函数、种群维度等因素相关的一次迭代时间。樽海鞘群算法的复杂度为O(iter3·N3·T3(f))，其中：iter3为迭代次数；N3为种群数量；T3（f）为与适应度函数、种群维度等因素相关的一次迭代时间。本文算法与灰狼算法等群体智能算法的复杂度一致，但在求解大规模优化问题时，灰狼算法等存在精度低、优化维数低、收敛速度慢等不足，而PSO 算法能够在更短时间内获得优化解［16］，有利于提高农田监测网络的整体效率。本文算法基于反向探测包理论缩短了初始位置与最优解的距离，进一步提高了PSO 算法的收敛速度。

4 实验与结果分析

为对RD-PSO 算法的性能进行验证，首先将其与传统PSO 算法［22］进行算法迭代收敛性能仿真对比，然后选取ELMR［23］、EEABR［24］和MR-PSO 算法［25］进行对比实验。实验场景具体参数设置如表1 所示。

表1 仿真参数设置Table 1 Simulation parameters setting

在目标区域内随机部署100 个节点，完成20 次独立随机部署并分别进行性能仿真实验，取平均值作为最终结果。

对比RD-PSO算法与传统PSO算法［15］的收敛速度，20 组独立实验中算法收敛迭代次数对比结果如图3 所示。从图3 可以看出，与传统PSO 算法相比，RD-PSO算法收敛所需的迭代次数整体较低，且波动幅度比传统PSO 算法小。传统PSO 算法由于随机性较大，路由算法的收敛会因节点分布和状态的不同而产生较大波动。对于每组实验节点而言，本文改进算法的收敛速度均优于传统PSO 算法，其原因有2 个方面：一是本文算法优化了粒子初始化方法，使得初始化粒子更接近最优解；二是虚拟力影响粒子的寻优过程，使得一条路径向全局最优路径的拟合速度加快。

图3 RD-PSO 算法与传统PSO 算法的收敛速度对比Fig.3 Comparison of convergence speed between RD-PSO algorithm and traditional PSO algorithm

不同路由算法的网络生存周期对比如图4 所示，可以看出，当系统运行约300 轮时，EEABR、MR-PSO算法开始出现死亡节点，当系统运行约400轮时，ELMR、RD-PSO 算法开始出现死亡节点。从10%节点死亡时间来看，ELMR 算法为520 轮，EEABR 算法为450 轮，MR-PSO 算法为700 轮，RD-PSO 算法约为820 轮；从全部节点死亡时间来看，ELMR 算法约为700 轮，EEABR和MR-PSO 算法约为800 轮，RD-PSO 算法约为850 轮，表明RD-PSO 算法的能耗性能最优，其次是MR-PSO 算法，ELMR 和EEABR 这2 种算法相对较 差。

图4 不同路由算法的网络生命周期对比Fig.4 Comparison of network life cycle of different routing algorithms

不同路由算法的网络节点剩余能量均方差对比如图5 所示，从中可以看出：ELMR 算法剩余能量均方差从一开始就迅速上升，在250 轮～450 轮时达到较高水平，300 轮峰值处约为E0的4.5%，450 轮后ELMR算法的剩余能量均方差开始逐步下降，对应图6 中也开始出现明显的存活节点数量减少，直到700 轮附近开始逐步减少至0；EEABR 算法剩余能量均方差在100 轮处达到最高，约为E0的2%，之后略微下降，在200～500 轮间维持在0.004～0.005 J 之间，之后缓慢下降至0；MR-PSO 算法剩余能量均方差整体上明显低于ELMR 和EEABR，但高于RD-PSO，其剩余能量均方差大部分保持在0.002 J 附近；RD-PSO 算法的能耗均衡性最好，其剩余能量均方差始终维持在0.001 J以下。图5表明，ELMR 和EEABR 算法的能耗均衡效果欠佳，而RD-PSO 算法从节点剩余能量角度对路由算法进行的能耗均衡改进取得了显著效果。

图5 不同路由算法的节点剩余能量均方差对比Fig.5 Comparison of mean square error of node residual energy between different routing algorithms

不同路由算法的网络传输平均跳数对比如图6所示，从中可以看出：整体上ELMR 算法的平均跳数最多，RD-PSO 算法最低，EEABR 与MR-PSO 算法居中，MR-PSO算法略高于EEABR算法；从平均跳数变化上看，ELMR算法初始跳数最大，开始后逐步下降，约至300轮时降到局部低点，后逐步上升，在500轮后迅速下降至最低，EEABR算法初始跳数最大，后逐步下降至6跳并稳定，在700轮后迅速下降至最低，MR-PSO算法在前300轮时平均跳数稳定在6跳，后整体提高到7跳、8跳，在750轮后迅速降至最低，RD-PSO算法在前450轮稳定在4跳、5跳，550轮后整体上升至5跳、6跳并保持稳定，在850轮后迅速降至最低。

图6 不同路由算法的平均跳数对比Fig.6 Comparison of average hops of different routing algorithms

从适应度函数对跳数的约束定义中不难得出，跳数较小的算法具有更佳的能耗性能，因此，图6 结果也验证了图4、图5中算法的能耗分析结果。

5 结束语

路由协议作为网络数据采集过程中的重要环节，对网络性能的影响重大，路由能耗优化是近年来农田WSN 领域的研究热点。本文针对农田复杂动态环境下WSN 监测应用中的能耗优化问题，在PSO算法的基础上提出一种改进的路由优化算法RDPSO，其根据农田WSN 应用中的剩余能量、传输跳数、链路质量等因素构建适应度函数，并采用反向探测的方式提高粒子初始化的效率。实验结果表明，相对ELMR、EEABR 和MR-PSO 路由算法，RD-PSO算法可以提高节点间的能耗均衡效果，延长网络生命周期，在农田复杂动态环境下实现高效可靠的WSN 数据汇集。开放农田中气象环境复杂，作物分布密集，这造成了农田WSN 中传输链路质量不稳定、数据传输可靠性不高等问题。因此，后续将引入机会路由理论，结合群体智能算法设计高效的农田数据机会传输机制，进一步提高网络能效并延长网络寿命。