本文节选自《智慧农业（中英文）》2020年第2卷第3期，于合龙教授团队的文章《基于粒子群与模拟退火协同优化的农田物联网混合多跳路由算法》，其引用格式如下，欢迎大家阅读、引用。
点击直达知网阅读
点击直达官网阅读（全文，免费）
引文格式：孙浩然, 孙琳, 毕春光, 于合龙. 基于粒子群与模拟退火协同优化的农田物联网混合多跳路由算法[J]. 智慧农业（中英文） , 2020, 2(3): 98-107.
SUN Haoran, SUN Lin, BI Chunguang, YU Helong. Hybrid Multi-Hop Routing Algorithm for Farmland IoT based on Particle Swarm and Simulated Annealing Collaborative Optimization Method[J]. Smart Agriculture, 2020, 2(3): 98-107.
基于粒子群与模拟退火协同优化的农田网络监测模型构建与数据传输路径优化方法
1 农田网络监测模型构建为对农田网络高效、低能耗进行定量分析与研究，首先需要建立农田网络监测模型。模型构建主要分为两方面，一方面需要定义网络模型对网络节点的拓扑组织关系，另一方面需要定义网络的能耗模型以便进行能耗分析与仿真。
1.1 网络模型构建
由于大规模农田场景WSNs覆盖范围大，传感器节点数目多，成簇结构网络中“簇首-Sink节点”间单跳的数据模式易导致远端簇首节点快速死亡。因此，本研究采用一种下层成簇、簇首多跳的混合型网络结构，如图1所示。
图1 网络拓扑结构示意图
Fig. 1 Schematic diagram of network topology
本研究提出的PSMR算法采用了上下分层的混合型网络结构，该结构中下层采用成簇机制，提高组网效率，而且相邻区域节点成簇为网络数据融合提供基础；上层采用平面多跳结构，有利于均衡不同区域能耗。为便于分析，可将大规模农田WSNs中参与数据汇集的节点抽象化为一个无向赋权图G（V，E）。其中V代表的是WSNs当前轮次的簇首集合，V=｛C1，C2，…，Cn｝，每一个节点的通信半径为do，e是相邻节点Ci与Cj间的数据传输路径，e=（Ci，Cj）∈E，即E为相邻节点间传输路径集合。G中的一条数据传输链路P（C1，sink）是C1到sink节点间边的有序组合序列，P（C1，sink）=（（C1，C2），（C2，C3），…，（Ci，sink））。而路由优化的目的就是寻找满足簇首与sink节点间低传输能耗与时延要求的数据传输链路P。路由算法需要解决的问题即是为每一个节点找到一条到sink节点的路径，使得网络整体上能耗性能最优。结合参考文献中的仿真模型，对网络模型作以下假设。
（1）N个传感器节点随机布置在M×Mm2的正方形农田中。
（2）传感器节点具有环境感知、数据融合及传输功能。
（3）传感器和sink节点在部署后，在各自初始位置保持静止状态。
（4）传感器节点能量有限且无法补充。
（5）所有的传感器节点都有簇内传输与簇间传输两种传输模式，但只有当选择簇首后才可以进行较大功率的簇间数据传输。
1.2 能耗模型构建
根据节点间数据传输距离的差异性，本研究采用了两种不同的能耗模型：当节点数据传输距离小于距离阈值do时，采用自由空间衰减模型计算节点能耗，其路径损耗指数为2；当节点数据传输距离大于等于距离阈值do时，采用多路径衰减模型计算节点能耗，其路径损耗指数为4。然后由此节点向距离为d的另一节点发送k b数据时能耗Etr的计算方式为：
其中，Eele为节点处理1 b数据所需能量；εfa和εmf分别为两种模型中功率放大器的能耗系数；距离阈值do由能耗放大系数决定，是εfa与εmf比的算术平方根。
传感器接收kb数据的能耗Ere为：
1.3 网络路由结构构建
混合结构网络的路由构建主要分为两部分，首先是底层的成簇，网络节点根据节点位置、能耗等参数确定权重，竞争成为簇首，未成为簇首节点选择邻近的簇首加入。完成成簇后，簇首再以平面路由方式组网连接，形成各自到sink节点的路由路径。
1.3.1 成簇过程
由于簇首承担着局部数据的融合与上传任务，簇首的能耗远大于普通节点，因此本研究提出的PSMR算法采用剩余能量和节点度计算权值的方式筛选簇首，使节点密集区域的高能节点有更高的概率担任簇首，簇首竞争权值如
其中，r是网络当前轮次；α与β为权重因子；T（i，r）是节点i在第r次的竞争权值；N（i，r）是节点i在第r次的节点度；E（i，r）是节点i在第r次的剩余能量。当节点i的竞争权值T大于全部邻居节点时成为簇首。当网络结构划分结束后，普通节点按照传输距离选择最近的簇首加入，并开始初始化簇首在与sink节点在数据汇集中的传输链路。
1.3.2 初始数据传输链路的构建
在簇首与sink节点的初始数据传输链路构建中，当前簇首根据邻居节点的通信能耗、剩余能量、与sink节点间距离作为选择下一跳节点进行数据转发的依据，具体公式如下。
其中，W(i, j )为链路选择权重；a、b、c是选择中继转发簇首的权重因子；i是数据发送节点；j是节点i的邻居节点；dist是两节点间的传输距离；E(j )是第j个节点的剩余能量；Eo是网络节点的初始能量。该公式表明当选择下一中转节点进行数据转发时，优先选择剩余能量多，与节点i之间通信距离更接近于do且离sink节点最近的相邻簇首，以此构造出初始数据发送簇首与sink节点间的数据传输链路。网络初始数据转发树如图2所示，远端簇头通过多跳转发传输至sink节点，避免了远距离传输高额能耗，可有效改善网络的能耗均衡性能。
图2 网络数据转发树
Fig. 2 Forwarding tree of network data
2 数据传输路径优化方法WSNs应用场景不同，数据传输的要求也不同。WSNs在大规模农田中部署时，收集不同位置的作物生长及环境信息，并通过对这些信息分析后，对不同位置的作物采取不同措施，因此，需要环境监测精度高、数据传输可靠性强、节点适应性强。根据农田中不同作物的生长周期不同，WSNs在大规模农田进行多源异构数据监测和收集中属于一种能耗低的数据传输路径，使其能够在大规模农田中实现长时间的数据收集。本研究通过节点剩余能量、节点度加权选择簇首，采用成簇结构实现异构网络高效动态组网，通过簇首间多跳数据结构解决簇首远距离传输能耗过高问题，利用PSO与SA对数据传输路径的适应函数进行协同优化，提高算法的收敛速度，实现sink节点加速采集簇首中聚合的数据。
2.1 适应度函数的构建
通过对大规模农田WSNs数据传输过程进行分析，发现大规模农田WSNs对数据汇集阶段的传输能耗、质量、时延都有着较为严苛的需求，因此本研究采用多参数加权求和的方式构建了数据传输链路优化的适应度函数，如
其中，fitness为适应度函数；w1、w2、w3为权重因子；HopCountmin为数据传输链路的最小跳数；Energymax为同一条数据传输链路的簇首平均最大能量值；distmin是链路平均最小的单次数据转发距离，如
其中，dist用于计算节点i与数据转发节点NextNode内距离最短的节点间距离。每一次数据转发的路径长度，决定了转发节点的传输能耗。
HopCountmin具体计算如公（7）所示。
其中，NodeCount用于统计该链路数据上传中转发簇首的数目，目的是使参与一次数据汇集的中间转发节点尽可能的少，减少数据转发过程中的传输时延，为农田WSNs决策提供高时效性的数据支撑。
由于转发节点承担着网络额外的能量消耗，高能量节点进行数据转发，在保证数据传输质量的同时，可以有效均衡网络负载。Energymax具体计算如
其中，E是簇首的剩余能量值。
2.2 基于PSO的混合型路由优化方法
以网络传输距离、拟消耗传输能量和传输跳数构造的
PSO以其实现简单、收敛速度快、适用性强的特点，非常适合应用于节点计算能力薄弱、数据传输时效性要求较高的农田WSNs数据传输链路优化阶段。通过随机定义粒子位置和速度，计算每个粒子的适应值。由PSO算法率计算粒子的应适度函数值，Pi粒子的pbest值可以表示为Pi =（pi1，pi2，…，pij）。最佳粒子是当前情况群体中所经历的历史最优位置向量Pg =（pg1，pg2，…，pgD）。粒子的速度和位置可以用下面的等式表示。
其中，xi，j和Vi，j表示在t迭代中当前速度和位置；pi，j表示在第i个粒子的j维分量更新前的历史最佳位置；pgj表示种群历史最佳位置；φ为权重值；c1、c2为学习因子；r1、r2为均匀随机数。
但PSO在优化过程中需要进行大量的迭代运算，加速了网络的能量损耗，且PSO易陷入局部最优解而浪费大量的计算资源。针对这一问题，本研究引入具有突跳能力的SA算法用于对PSO进一步处理，以此避免陷入局部最优节解。利用PSO得到粒子的应适度函数值Pi以及最优粒子的适应度为Pg，通过
其中，f 是算法构建的适应度函数；S用于更新当前温度t下粒子i的适应度。
当粒子的当前适应度比以前更差时，更新将以一定的概率li被接受，如
其中，
其中，Te0代表初始温度，当迭代次数逐渐增加时，退火温度逐渐减小。基于退火模拟更新位置步骤如下。
①根据i的适应值。
②如果新的适应值比先前的适应值好，那么粒子i的位置将被更新，否则跳到步骤③。
③生成一个介于0和1之间的随机数，表示为r。
④用i的概率。
⑤如果li大于r，那么粒子i的位置将被更新，否则将被拒绝。
⑥重复步骤①至⑤，直到所有粒子都被计算一次。
⑦通过
2.3 PSMR算法构建流程
PSMR是在成簇型路由算法的基础上，对上层簇首与sink节点间的数据传输路径进行优化。在开始阶段，簇首竞争及网络结构换分完成后，按照
a. 将节点与下一跳候选节点的剩余能量及两点间的传输距离作为约束，构建源节点与sink节点间多条多跳的数据传输链路，作为初始粒子。
b. 对粒子的位置和速度进行初始化，并分别计算出其相应的个体极值与全局极值，并将适应度和当前位置分别存放在代表个体信息的Pi和全局信息的Pg内。
c. 确定当前温度下粒子的适应值Pi，并与全局极值进行比较及替换操作。
d. 通过
e. 判断目标函数值是否达到最优值或算法达到最大迭代次数，若未达到算法停止要求，则重复步骤b到e；否则输出当前全局极值，并将当前粒子作为源节点与sink节点间通信的数据传输链路。
簇首按照构建的数据传输链路将局部监测数据逐步的向sink节点汇集，并当网络完成一轮数据采集与上传后，重新开始网络结构与数据传输链路的构建过程，当监测区域内的节点出现大面积死亡、网络陷入瘫痪状态或网络运行到预先设定的最大轮次时，停止数据采集与传输工作，并向用户发送监测结束消息。
PSMR的流程如图3所示。
图3 PSMR算法优化流程图
Fig. 3 PSMR algorithm optimization flow chart
3 算法仿真试验及性能分析3.1 仿真实验参数
为考察PSMR算法性能，本研究选择WSNs路由算法最常见的网络生命周期、节点剩余能量标准差和网络每轮能量消耗3个指标，在Matlab平台上进行了仿真试验。仿真场景参数如表1所示。在性能对比方面，首先将PSMR算法与PSO和SA算法进行了纵向对比，并进一步将PSMR与EMR、GPSR-A算法进行横向性能对比分析。
表1网络仿真参数
Table1 Network simulation parameters
在大规模农田WSNs监测中，评价网络性能的核心指标参数为网络生命周期，当节点死亡数目超过总节点数目的30%后，网络出现大面积空洞，采集的数据无法完全代表监测区域的环境情况，因此本研究将网络开始工作到节点死亡数目达到总结点数目30%的这一段时间定义为网络的生命周期。
3.2 仿真实验结果
3.2.1 纵向性能对比
如前文所述，PSMR采用PSO与SA结合方法对路由路径进行优化，由此本研究首先对比PSMR与PSO、SA的网络生命周期，从图4中可以看出存活节点数在保持一段时间不变后均呈现逐渐下降的趋势。其中SA算法的保持时间最短，约在200轮时起出现首个死亡节点，PSO和PSMR出现首个死亡节点的时间约在500轮。SA算法的生命周期最短为600轮左右，PSO算法的生命周期约在1000轮左右，PSMR算法的生命周期大致相同为1260轮左右。从图4中可以看出，PSO算法收敛速度较快，因此前期性能与PSMR相当，而SA算法收敛速度慢，前期的性能较差，造成较早的节点死亡。PSO算法易陷入局部极值，因此在中后期出现存活节点数量的迅速下降，而SA算法存活节点数量呈缓慢下降趋势。图4的结果也印证了2.2小节的讨论分析。
图4 PSMR和PSO、SA网络生命周期对比图
Fig. 4 Network life cycle comparison chart of PSMR, PSO and SA
3.2.2 横向性能对比
如图5所示，EMR、GPSR-A和PSMR 3种算法网络生命周期均呈现出保持稳定不变到逐渐下降的趋势。其中EMR的网络生命周期最短，为800轮左右；PSMR和GPSR-A算法的网络生命周期大致相同，为1260轮左右。以网络生命周期作为评价性能依据，PSMR较EMR提升了57%，并且PSMR的第一个节点死亡轮数较GPSR-A算法更晚，在网络生命周期内，节点存活率高于GPSR-A算法。可见，基于PSMR的数据采集质量更优，更好地满足了大规模农田WSNs长时间的监测需求。
图5 PSMR和EMR、GPSR-A网络生命周期对比图
Fig. 5 Network life cycle comparison chartof PSMR, EMR and GPSR-A
对比EMR、GPSR-A和PSMR 3种算法的网络剩余能量标准差变化情况，结果如图6所示。3种算法的剩余能量标准差总体上呈现逐渐上升再下降的趋势。其中PSMR的网络剩余能量标准差最小，平均约为0.025 J；其次分别是EMR和GPSR-A算法，网络剩余能量标准差平均值分别约为0.04和0.065 J。PSMR通过动态划分网络结构的方式起到了均衡簇首和普通节点能耗差异的效果，并且多特征值的数据传输链路优化保证了簇首在数据转发中的低能量损耗，因此PSMR的能量均衡性较好。EMR通过节点剩余能量和通信能耗选择数据转发节点，缩小了节点的能耗差异，但该种方式的路径选择导致每一跳的传输能耗都存在较多差异，且易导致数据转发次数过多；由于离sink节点近的簇首频繁参与数据转发，能量开销较大，因此网络能量标准差有所下降。GPSR-A算法中全网节点都需要构建与sink节点间的数据传输链路，并以一种贪婪选择的方式选取转发节点，该种方式可以有效的缩减数据转发次数，但节点间的数据转发距离差异较大，且平面网络结构下距离sink节点较近的节点因承担着更重的数据转发任务容易早衰，因此网络剩余能量标准差最大。
图6 网络剩余能量标准差对比图
Fig. 6 Standard deviation of network residual energy comparison chart
对比EMR、GPSR-A和PSMR 3种算法的每轮能量消耗情况，结果如图7所示，可以看出PSMR、EMR由于周期性的簇首轮换及构建数据传输链路更新导致每轮能量消耗存在着较大的波动。PSMR考虑了传输跳数与间距，每轮能量消耗较EMR更小。而EMR由于有过多的节点参与了数据转发，因此网络的能量消耗较大。GPSR-A算法每一跳都保持了较长的通信距离，在网络初期节点能耗较大，而随着部分节点死亡和数据传输链路的重新构建，网络轮能量消耗速度随着网络周期轮数的增加呈逐渐降低的趋势。结合图5可以看出，在800轮之后，网络存活节点数量已出现明显下降。
图7 每轮网络能量消耗对比图
Fig. 7 Network energy consumption per round comparison chart
通过与EMR、GPSR-A算法的性能对比，可见PSMR的网络生命周期更长、节点剩余能量标准差更低，每轮网络能量消耗与GPSR-A相当，低于EMR，延缓了节点死亡的速度，说明根据分簇的方式动态构建混合型网络结构与多特征值选取数据传输链路的优化方法在提高节点能量利用率、均衡网络负载上效果较好，进而延长了网络生命周期。
小
店
欢迎光临选购
微信交流服务群
为方便农业科学领域读者、作者和审稿专家学术交流，促进智慧农业发展，为更好地服务广大读者、作者和审稿人，编辑部建立了微信交流服务群，有关专业领域内的问题讨论、投稿相关的问题均可在群里咨询。
入群方法：加小编微信331760296，备注：姓名、单位、研究方向，小编拉您进群，机构营销广告人员勿扰。
信息发布
科研团队介绍及招聘信息、学术会议及相关活动的宣传推广
