基于自适应萤火虫的农业传感网络均衡分簇算法

袁旭华， 惠小静

(延安大学数学与计算机科学学院，陕西延安 716000)

为了对大棚农业的精细管理，农业物联网(agriculture internet of things，AIoT)[1]应运而生。在大棚监控系统中，运用农业物联网西游中的各种传感器(温度、湿度、pH值、光和二氧化碳等)设备，监测环境中的温度、相对湿度、pH值、光照度和二氧化碳浓度等指标，通过各种仪器实时显示到大棚监控中心，保证作物有一个良好的、适宜的生产环境，为精细农业精准控制提供科学依据，从而提高农作物产量、调节作物生长周期、提高经济效益的目的。无线传感器网络(wireless sensor networks，WSNs)作为农业物联网推广的重要载体、未来延伸Internet覆盖范围和实现普适计算的一项关键技术，得到国家、社会和学术界广泛重视，必将在农业生产、农业经济和社会发展等各个领域显示出巨大的应用价值[2]。农业WSNs通过对大棚监测区域部署各种传感器类型的节点，近距离多跳自组织的形式传输数据、节点之间相互协作、互相配合的智能网络。将采集到的数据进行初步预处理，以多跳自组织的形式发送给汇聚节点，汇聚节点再将收集到的信息传输给大棚监控中心，大棚监控中心进行适当的处理，最终将处理后的数据反馈给决策者并传送给所需的用户[3]。

农业无线传感器网络以数据为中心，以完成规定的任务为目标，当传感器网络执行具体应用任务过程中，完成规定功能的任务主要由完成任务时间、网络能量消耗情况、网络生存时间、网络内部负载均衡性以及稳定性和可靠性等性能决定，而这些参数都与大棚监测区域的传感器节点组成的网络结构息息相关，即与网络分簇数量、簇的结果相关。一般而言，大多传感器网络都是在经典分簇低功耗自适应集簇分簇型协议(LEACH，low energy adaptive clustering hierarchy)分簇架构基础上进一步研究的。大棚网络建立初期，分簇算法将监测区域划分为若干个区域(簇)，每个簇由簇头节点和簇成员节点构成，簇成员节点主要负责数据的感知、采集和预处理，之后将采集的数据发送给簇头，簇头对收集到簇成员节点的数据进行数据处理，之后转发给宿(sink)。簇头的工作职责主要是簇之间的相互通信以及簇内资源管理与分配，使簇内传感器节点负载均衡。簇结构数量及大小很大程度上会影响整个传感器网络性能，因此基于负载均衡的无线传感器网络分簇算法的研究对提高网络性能、延长网络寿命和提高网络寿命有着非常重要的意义[4]。

1　网络能耗模型及分簇算法

1.1　网络能耗模型

无线传感器网络能耗模型采用与LEACH算法相同的无线通信模型，传感节点无线通信能耗模型如图1所示。

从图1中可以看出，传感节点发送数据能量消耗主要分布在发射电路和放大器电路2个部分，发射电路的能耗与发送数据包的长度l有关，放大器电路的能耗与数据包的长度和传输距离d有关。无线传感器网络数据传输能耗模型分2种，即自由空间传输模型和多路径衰减模型，数据传输距离不同，采用的网络能耗模型也不同。另外该模型根据传输距离的长度给出1个参考阈值d0，当距离小于阈值d0时，采用自由空间传输能耗模型，发送数据所需能耗与距离的平方成正比。当距离大于参考阈值d0时，采用多路径衰减能耗模型，发送数据的能耗与距离的四次方成正比。传感器节点发送数据能耗的公式如式(1)所示[5]。

(1)

式中：ETx(l)是发射电路发送数据包长度l的发射能耗；ETx(l，d)是将数据包长度l发送至距离d的放大器能耗。而节点接收数据后，网络能耗为：

Erx(l)=l×Eelec。

(2)

簇头节点进行数据融合(l个簇头和N/k-1个簇成员节点)消耗的能量为

Eax=l×EDA(1=N/k-1)=l×EDA×N/k。

(3)

阈值d0由式(4)决定：

(4)

式中：Eelec与信道编码、调制、滤波、扩频信号等因素有关，参数εfsd2和εampd4取决于特定误比特率条件。节点发送或接收单位长度数据的能耗Eelec=50 nJ/bit，自由空间数据传输模型的放大器能耗参数εfs=10 pJ/(bit·m2)，多路径衰减数据传输模型的放大器能耗参数εamp=0.001 3 pJ/(bit·m4)，簇头数据融合的能量消耗EDA=5 pJ/bit。

1.2　分簇算法

无线传感器网络分簇算法主要针对监测区域中的传感器节点，通过何种方法对监测区域中的所有传感节点进行分簇，使簇内成员节点以最少的能量完成网络数据的采集、处理和传输，最终传送给宿节点。现有的分簇方法大都偏重于算法的网络能耗、计算复杂度、网络数据传输时延等方面，但很难保证适当的簇数量、簇内成员节点之间的通信质量以及簇之间的负载均衡性问题。监测区域中的簇头节点数过多或者过少都会导致网络出现各种问题，性能下降，降低网络寿命。如监测区域中的簇头节点数过多，不方便宿节点的管理，导致和宿节点直接通信的簇头节点太多，造成数据传输拥塞，延长数据传输时延和增加通信能耗。如监测区域中的簇头节点数过少，会导致簇内成员节点过多，造成簇头节点能耗过多，管理难度增大，最终导致负载不均衡，造成部分节点能量消耗过快而过早失效，影响整个网络的连通性和可靠性。

目前已经有很多专家学者在无线传感器网络分簇算法中展开深入的研究，并取得了一些成果。最典型的则属于低功耗自适应集簇分簇型协议LEACH分簇算法，现在许多算法都是基于此方法开展进一步工作的。如Yue等对无线传感器网络分簇方法进行了整理总结，分别从平面路由层分簇协议和异构路由分簇方法进行总结[6]。Liu等针对分布式传感器网络提出了一种基于聚类的负载均衡分簇算法，构建了一种更加稳定的分簇架构，延长了网络寿命[7]。Javaid等针对异构无线传感器网络分簇算法，提出一种EDDEEC(enhanced developed distributed energy-efficient clustering)分簇方法，提高了网络工作效率，节省了网络能耗，延长了网络寿命[8]。在文献[9]中，针对无线传感器网络非均匀分簇问题，提出一种能量模糊感知分簇方法，节约了网络能耗，提高了网络寿命。Bagci等提出一种新的路由分簇协议ECHERP(equalized cluster head election routing protocol)，大大提高了工作效率，节省了网络能耗[10]。Nikolidakis等结合群智能仿生优化算法，提出一种基于人工蜂群算法的无线传感器网络路由分簇算法，仿真结果表明该方法非常成功地应用于WSNs分簇方法中，节省了网络能耗，延长了网络寿命[11]。从以上研究成果来看，上述这些算法都从网络能耗、网络寿命角度出发，对其进行优化和改善。但上述方法要求传感器网络簇头节点需要较强的计算能力、通信能力和存储能力，整个计算过程网络能耗开销非常大，同时没有考虑网络簇内成员节点的多跳数据传输情况。因此，本研究综合考虑负载均衡和能量消耗2个优化目标，搜索过程充分考虑了网络分簇的负载均衡性、簇内数据传输距离、跳数、时延和带宽等因素，将群智能萤火虫算法与无线传感器网络分簇路由算法相结合，提出一种新的自适应萤火虫WSNs负载均衡分簇算法。

2　改进的萤火虫算法

英国剑桥大学Yang博士对萤火虫发光行为进行抽象，于2007年提出了萤火虫算法(glowworm swarm optimization，GSO)[12]，该算法是一种新元启发式群智能算法，具有操作简单、并行鲁棒性较强等特点，在高维空间复杂函数优化方面得到成功应用[13]。一般典型的萤火虫优化算法由算法初始化、荧光素更新、飞行位置更新以及萤火虫决策域更新4个部分构成[14]。萤火虫i在寻找食物过程中，种群个体之间都会相互沟通与协作，主要通过飞行过程中发出荧光素向周围传送食物源信息，食物源越大，荧光素则越浓，吸引其他萤火虫飞往食物源较多的地方。萤火虫的决策范围根据式(5)进行确定。

(5)

(6)

式中：xi(k)为第k次迭代计算中萤火虫i位置；li(k)表示第k次迭代中萤火虫i荧光素值；在第k次迭代中，萤火虫i向邻居萤火虫个体j运动的概率用pij(k)表示，由式(7)表示为：

(7)

萤火虫i向荧光素多的地方运动后的位置由式(8)得到：

(8)

式中：S表示萤火虫搜索食物源的运动步长。

萤火虫i搜索食物源运动到新地方后，按照式(9)对萤火虫发出的荧光素值进行更新：

li(k)=(1-λ)li(k-1)+ωf[xi(k)]。

(9)

式中：li(k)表示在第k次迭代计算中萤火虫个体i荧光素值；λ∈(0，1)[15]。

在萤火虫算法中，由于算法本身在搜索最优解过程中容易陷入局部最优以及寻优速度较慢等问题。同时，搜索过程中如果步长较大，则容易寻找到全局最优解，但与之付出的是搜索精度大大降低，还会出现较大的波动情况；如果搜索过程中如果步长较小，搜索最优解的速度降低，搜索精度明显提高。这是一个相互影响、相互制约的关系，必须在它们二者之中进行权衡，由此提出自适应搜索的改进萤火虫算法，同时引入萤光因子Yi

(10)

式中：φi表示第i头萤火虫的当前状态；φmax表示荧光素浓度最高时种群个体当前状态；dmax为最佳萤火虫到其他萤火虫个体之间的距离最大值。

基于萤火虫算法中的萤光因子自适应调整搜索步长最佳策略为

si=smin+(smax-smin)Yi。

(11)

式中：smin、smax分别是搜索步长的最小值、最大值。

根据前面的(10)、(11)计算公式自适应调整搜索步长。当种群个体第i头萤火虫靠近荧光素浓度最大的萤火虫区域时，距离越近，那么‖φi-φmax‖越小，另外可通过计算公式(10)可知，所求得的萤光因子Yi值越小，而根据计算公式(11)得出的自适应调整搜索步长最佳策略si也越小。

因此，为了保证搜索过程中尽快寻找到全局最优解，在搜索最优解过程中必须进行动态调整，采取以下措施：自适应调整步长的萤火虫算法在搜索最优解初期，采取步长较大的搜索方式，进行第1步精度较差的大范围搜索，尽快完成全局搜索最优解，在最优解邻域附近进行步长较小的精度搜索，即局部搜索，搜索更精确的最优解。

3　基于改进萤火虫算法的分簇算法

假定在边长为M的正方形传感器网络监测区域中，随机部署N个传感器感知节点，簇头节点到宿节点之间的距离为dChtoBS。另外，假定监测区域中N个传感器感知节点均匀划分为k个簇区域，每个簇成员节点的个数为(N/k-1)，并参考“1.1”中的网络能耗模型可知，簇头的能耗ECH主要由以下2个部分组成：接收簇成员节点的能耗和向宿节点转发数据产生的能耗。其他的簇内成员节点的能耗ENEN主要由感知节点感知数据产生的能耗以及向簇头转发数据产生的能耗。

假定传感器感知节点在监测区域中服从泊松分布，每个簇所占区域S面积可以计算为M2/k，监测区域中传感器节点的密度函数为

(12)

传感器节点到簇头节点距离的平方数学期望为

E[dtoCH2]=E[x2+y2]=M2/2kπ。

(13)

无线传感器网络整个监测区域总的能量消耗为

Etotal=k×Ecluster=k×ECH+k×(N.k-1)×ENEN；

(14)

(15)

将式子(13)代入(15)，可以计算得到网咯总能量消耗为

(16)

对于式(16)，关于k的计算，求k的一阶导数，可以得到下式

(17)

本研究通过求取最佳的分簇数目k值，运用改进的萤火虫算法对网络总能量消耗最小，也就是传感器网络总能耗最小对应的分簇最佳数值。基于改进萤火虫算法的WSNs分簇算法寻找最佳分簇值k的工作流程如图2所示。

4　仿真结果与分析

4.1　仿真环境设置

为了测试本研究提出的负载均衡分簇算法性能，用Matlab 2014b仿真软件进行仿真试验和性能分析。假设无线传感器网络节点随机均匀分布在(500×500)m2的二维空间中，传感器节点规模200个。仿真轮询次数设为100，每次仿真中传感节点均有10个数据包从源节点向移动Sink传送，每个数据包容量4 kb。了使模型的结果更有说服力，本研究给出的结果都是100次试验的平均结果。仿真环境参数设置如表1所示。

表1　仿真环境参数设置

为了更好地说明本研究提出算法的优越性，对LEACH算法[16]、ACO蚁群算法[17]、PSO粒子群算法[18-19]和本研究提出的改进萤火虫算法(IGSO)算法4种数据融合算法进行对比。首先给出无线传感器网络分簇图，具体如图3所示。

4.2　算法仿真对比分析

4.2.1网络总能耗对比传感器网络总的能量消耗定义为整个网络传感器节点所消耗的能量总和。网络的总能量消耗越小，表明该网络工作效率越高，传输的数据量越少， 网络的生命周期也就越长。以传感器总能量消耗作为衡量指标，4种算法的网络总能耗如图4所示。

从图4可以看出，随着仿真轮数的增加，4种算法的网络能耗都在逐渐增加，但LEACH算法增长幅度最大，本研究提出的算法的增长幅度最小。另外，LEACH路由协议的能耗最大，ACO算法较大，PSO算法能耗较小，改进的萤火虫算法最小。以60轮数为参考，本研究提出的算法比LEACH协议、ACO算法和PSO算法的能耗分别节省了32.8%、22.8%和12.8%。

4.2.2网络负载均衡性对比网络负载均衡是影响网络生存周期的重要指标，网络负载越均衡，网络的生存周期越长。网络负载均衡一般用负载均衡因子(load balancing factor，LLBF)来表示。LLBF定义为监测区域中网络所有感知节点(包括簇头节点)方差的倒数。具体计算为

(18)

式中：参数nc为传感器节点个数；xi为第i个簇头成员中感知节点数；u为所有簇头节点的平均节点数。4种算法的网络负载平衡性能对比结果如图5所示。

图5显示，随着仿真轮数的增加，LEACH分簇协议的网络负载均衡性在不断增大，网络的负载均衡性能逐渐变差。其余3种算法的负载均衡性能较好，但是3种算法的负载均衡性能相差不大。整体来看，本研究提出的改进萤火虫算法的网络负载均衡能力最好，ACO算法和PSO算法区别很小。

4.2.3簇头个数对比LEACH协议、ACO算法和PSO算法和本研究提出的萤火虫算法产生的簇头节点个数如图6所示。通常最佳的簇头节点数是总的传感节点数的6%～10%，簇头数越多，且保持恒定，网络性能越好。经统计，本研究提出算法的簇头节点数几乎都保持在15～24个。LEACH协议的簇头节点数在11～28个之间波动剧烈。ACO算法和PSO算法的簇头节点数保持在13～26个，但是由于存活的节点数减少，簇头节点数也随之减少，保持在20个左右，波动较大。由此可以看出，本研究提出的算法性能最好。

4.2.4簇头节点能耗对比由于簇头节点承担着数据采集、融合和传输等多重任务，因此能量消耗最大。通过簇头节点的能量消耗情况可知整个网络能量消耗情况，4种算法每一轮簇头节点能量消耗如图7所示。

在LEACH协议中，簇头节点须要传输所有的感知数据，能量消耗较多，感知数据量急剧减少，簇头能量消耗也快速降低。在ACO算法和PSO算法的负载均衡分簇算法中，由于在分簇过程中考虑到簇内成员节点的能耗均衡问题，使得簇内成员节点相互协作，簇头能耗也较小，PSO算法的簇头能耗比ACO算法小一些。在本研究提出的算法中，簇头节点能量消耗相对较小，并且比较平稳。

4.2.5存活节点数对比网络存活节数是反映WSNs网络性能的重要指标之一，网络的存活节点数越多，证明网络能够更长时间地执行监测任务，避免频繁地更换电池。通过与其他3种算法比较，图8对本研究所提出的负载均衡分簇算法进行了性能评估，该图主要对不同负载均衡分簇算法的存活节点数随轮次增加而变化的曲线图进行比较。

从图8可以看出，在LEACH协议中，50%的传感节点的死亡时间为47轮。在ACO分簇算法中，50%的传感节点的死亡时间为45轮。PSO算法在网络运行100轮时，节点死亡率为70.3%，本研究提出的算法为55.7%。由于本研究提出的算法考虑了无线传感器网络的剩余能量和到汇聚节点的距离等因素，且将每个节点的感知数据协同通信，均衡分簇，通过簇头节点传递给汇聚节点，网络能量消耗较小。

4.2.6网络传输时延对比笔者用成功接收到的数据包的传输时延来衡量协议的实时性。一个数据在源节点的发送时刻记为Ts，在宿节点的接收时刻记为Tr，则平均传输时延为：

(19)

式中：Nr为成功接收到的包的总数。

从图9可以看出，随着仿真轮数的增加，数据传输延时明显增大，这主要因为随着算法的运行，网络节点能耗逐渐增大，剩余能量越来越少，冲突和重传次数增加，产生较大的延迟，但是本研究提出负载均衡分簇算法的时延明显比ACO分簇算法和PSO分簇方法小一些。LEACH协议数据传输量最大，网络时延最大。

5　结束语

负载均衡分簇路由算法一直是农业物联网感知层传感网络关键技术之一，是农业领域学者关注的重点。本研究将群智能萤火虫算法与农业WSNs分簇路由算法相结合，提出了一种基于自适应萤火虫的农业WSNs负载均衡分簇算法。该算法综合考虑负载均衡和能量消耗2个优化目标，搜索过程充分考虑了农业网络分簇的负载均衡性、簇内数据传输距离等因素。试验表明，提出的算法在感知范围内自适应地调整搜索步长，降低振荡现象，提高求解精度。同时有效地减少簇首选举和路由维护的开销，提高网络寿命，实时寻找性能更好的路由，具有较好的稳定性。

本研究提出的萤火虫智能分簇算法主要针对较大规模的农业无线传感器网络，同时算法本身的能耗和仿真耗时也较多，都是在离线状态下完成的，下一步将对算法进一步优化，以及重点考虑算法的实用性和扩展算法的应用领域。

参考文献：

[1]Liu Y H，He Y，Li M，et al. Does wireless sensor network scale? a measurement study on GreenOrbs[J]. IEEE Transactions on Parallel and Distributed Systems，2013，24(10)：1983-1993.

[2]袁志强. 基于ZigBee技术的温室大棚无线监控系统设计[J]. 江苏农业科学，2012，40(11)：396-397.

[3]Othman M F，Shazali K. Wireless sensor network applications：a study in environment monitoring system[J]. Procedia Engineering，2012，41：1204-1210.

[4]Suryadevara N K，Mukhopadhyay S C. Wireless sensor network based home monitoring system for wellness determination of elderly[J]. Sensors Journal，IEEE，2012，12(6)：1965-1972.

[5]Tyagi S，Kumar N. A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks[J]. Journal of Network and Computer Applications，2013，36(2)：623-645.

[6]Yue Y，Li J Q，Fan H H，et al. Optimization-based artificial bee colony algorithm for data collection in Large-Scale Mobile wireless sensor networks[J]. Journal of Sensors，2016(4)：1-12.

[7]Liu X. A survey on clustering routing protocols in wireless sensor networks[J]. Sensors，2012，12(8)：11113-11153.

[8]Liao Y，Qi H，Li W Q. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks[J]. IEEE Sensors Journal，2013，13(5)：1498-1506.

[9]Javaid N，Qureshi T N，Khan A H，et al. EDDEEC：enhanced developed distributed energy-efficient clustering for heterogeneous wireless sensor networks[J]. Procedia Computer Science，2013，19：914-919.

[10]Bagci H，Yazici A. An energy aware fuzzy approach to unequal clustering in wireless sensor networks[J]. Applied Soft Computing，2013，13(4)：1741-1749.

[11]Nikolidakis S A，Kandris D，Vergados D D，et al. Energy efficient routing in wireless sensor networks through balanced clustering[J]. Algorithms，2013，6(1)：29-42.

[12]Karaboga D，Okdem S，Ozturk C. Cluster based wireless sensor network routing using artificial bee colony algorithm[J]. Wireless Networks，2012，18(7)：847-860.

[13]Zainal N，Zain A M，Radzi N H M，et al. Glowworm swarm optimization (GSO) algorithm for optimization problems：a state-of-the-art review[C]//Applied Mechanics and Materials，2013：507-511.

[14]Huang K，Zhou Y. Improved variation step adaptive GSO algorithm[J]. Computer Engineering，2012，38(4)：185-187.

[15]Marinaki M，Marinakis Y. A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands[J]. Expert Systems With Applications，2016，46：145-163.

[16]Jayakumar D N，Venkatesh P. Glowworm swarm optimization algorithm with topsis for solving multiple objective environmental economic dispatch problem[J]. Applied Soft Computing，2014，23：375-386.

[17]黄成，张润，吴晓蓓，等. 三维空间下基于簇首优化机制的LEACH路由算法[J]. 南京理工大学学报(自然科学版)，2015，39(2)：241-245.

[18]缪聪聪，陈庆奎，曹剑炜，等. 基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法[J]. 计算机应用，2013，33(12)：3410-3414.

[19]苏金树，郭文忠，余朝龙，等. 负载均衡感知的无线传感器网络容错分簇算法[J]. 计算机学报，2014，37(2)：445-456.