李校红
(西安欧亚学院信息工程学院，陕西 西安 710065)
摘要：针对传统无线路由算法节点选择存在很大的随机性，一旦选择边沿节点将造成长距离通信，从而降低通信效率的问题，设计了一种基于改进粒子群算法的能量优化模型。该模型利用改进粒子群算法对簇头选择进行优化，并综合考虑簇头能量、簇头传输距离、簇头分布等因素，设计新的适应度函数，从而在大范围内降低网络传输的能量损耗。此外还针对无线网络节点过早死的问题，提出一种基于最小能耗的单级跳和多级跳结合的通信方式，从而均衡整个无线网络能量，延长整个网络的寿命。最后通过仿真验证了模型的可行性。
关键词：改进粒子群算法；无线网络；簇头；能量均衡；适应度函数
网络覆盖控制是传感器网络应用的基本问题。如何保证覆盖区域的无线网络通信效率，并延长覆盖区域的网络寿命，成为当前研究的热点。但是研究发现，传统的低功耗自适应无线分簇路由算法中，对节点的选择随意性较大，通信簇头也呈现出不规律性的分布。为保证整个无线网络的均衡，LEACH算法将所有的能量分布到全部节点中。一旦选择边节点簇头，势必经过长距离的传播才能到达簇头，从而大大降低整个网络的通信效率，也加剧了整个网络的能量消耗[1-2]。为解决该问题，优化无线网络，王秋鹏[3]引入睡眠调度机制和最佳路由等方法对无线网络的能量进行优化，从而延长整个网络的寿命。刘伟等[4]提出一种自适应逃逸粒子算法对网络覆盖节点进行优化，从而计算最优网络节点位置，实现整体网络能量消耗最小化。本文在上述研究的基础上，提出一种改进粒子群算法，将其应用到簇头选举中，并结合适应度函数，从而减少整个网络的能量消耗。最后采用单跳和多跳结合的网络传输方式，从而保证整体网络的均衡。
粒子群算法在寻找最优解时，主要通过不断迭代的方式，从而解决其中的连续优化问题。假设在n维空间中，存在m个粒子，从而构成了种群数量为X的粒子群，其中X=(X1,X2,…,Xm)。这些粒子具有以下属性：1)第i个粒子飞行的速度为vi=(vi1,vi2,vi3,…,vin)，第i个粒子的位置为Xi=(Xi1,Xi2,Xi3,…,Xin)。2)第i个粒子的最好位置pi=(pi1,pi2,pi3,…,pin)，此时为个体最优；所有粒子的最好位置为pg=(pg1,pg2,pg3,…,pgn)，此时为全局最优。
在粒子群算法中，个体最优和全局最优决定了粒子下一步的运行轨迹，而飞行的方向和位置则主要取决于速度v。因此，粒子通过个体极值pbest和全局最优值gbest来更新自己的位置和速度，并通过迭代的方式来寻找其中的最优解。
vid(t+1)=ωvid(t)+c1[pbest-
xid(t)]rand1()+c2[gbest-xid(t)]rand2()
(1)
xid(t+1)=xid(t)+vid(t+1)
(2)
式中：ω为惯性权重，该值越小表示局部搜索能力越强，值越大表示全局搜索能力越强；vid(t)为粒子当前的速度；xid(t)为粒子当前的位置；c1、c2为学习因子，使调节粒子往最好位置的步长；rand1、rand2为介于(0,1)的随机函数；t表示当前迭代次数。
根据上述算法得到的算法流程如图1所示。
2.1 惯性权重和学习因子改进
有学者认为传统的粒子算法很容易陷入局部最优的问题中，从而在簇头选举中找不到整个网络最优的簇头[6-8]。本文主要从惯性权重和学习因子入手解决传统粒子算法容易陷入局部搜索的问题。
图1 粒子群算法描述
通过式(1)可以看出，粒子的速度和位置与惯性权重ω和学习因子c1,c2有很密切的关系，其中ω的取值决定其偏向于局部搜索还是全局搜素。由此，笔者提出对ω进行余弦改进，具体思路就是在最初时刻ω较小时，可以在粒子周围搜索找到局部最优解；在后期则将ω变大，以此改变传统的容易陷入局部搜索的问题，改为搜索全局最优；在找到全局最优后，ω再次变小，进行局部搜索，从而加快算法的收敛速度。具体表达式为：
(3)
式中：ωmax和ωmin分别为惯性权重的最大值和最小值，通常在0.4～0.9之间；itercur为当前迭代次数；itermax为最大进化代数。
同时，传感器网络中的最优簇头的选取还与学习因子有关，其中c1为自我学习因子，c2为社会学习因子。对学习因子的设置过大或者过小，都不利于对粒子的搜索。因此，在进行最优簇头选取期间，同样采用对惯性权重改进的思路，即将c1先变大再变小，同时将c2先变小再变大，以此在前期扩大局部搜索范围，而到了后期，由于学习因子发生对称变化，可以快速进行全局搜索，因此避免了陷入局部最优的问题。具体方法则是通过余弦对学习因子进行改进，表达式为：
(4)
(5)
式中：c1s,c1e,c2s,c2e分别为c1,c2的初始值和最终值；k为控制因子。研究表明c1s=2.5、c1e=0.5、c2s=0.5、c2e=2.5时，算法效果最佳。
2.2 适应度函数设计
适应度函数主要用于评价粒子的质量，其运用通常取决于具体优化问题，被看成是算法和具体寻优问题的接口。考虑到无线传感网络的整体能耗和负载程度，在定义适应度函数时主要考虑网络能耗、簇头能量比例、能耗均衡度、簇内节点距离4个因素。根据能量通信模型，将其适应度函数设计为：
F=αf1+βf2+λf3+ρf4
(6)
式中：α,β,γ,ρ为分别对应4个适应度函数f1,f2,f3,f4的权重；F表示整体的适应度函数。
1)网络能耗。
网络能耗关系着整个网络的性能和寿命。根据无线通信能耗模型[9]，可得到整体无线网络的能耗。具体表达式为：
(7)
式中：|Ck|为第k个簇之中传感器的节点数量；Eelec为节点接收或发送1bit的数据所耗费的能量；εfs,εamp为不同通信模式下的放大电路能耗系数；EDA为每处理1bit数据所耗费的能量；dtoBS为簇头到基站的平均距离；dtoCH为成员节点到簇头的距离的数学期望值。
2)簇内节点距离。
在保障通信能量的同时，还必须要保证节点与簇头之间的距离必须在合理范围之内[10]，从而保障不同节点的通信。因此，不同节点之间的通信距离为：
(8)
式中：dmknj为第k个簇头与其所属的第j个节点的距离。
3)簇头剩余能量比例。
不同簇头的能量消耗是不同的，在选择时应尽量选择能量较高的节点作为簇头[11]。因此适应度函数f3为：
(9)
式中：E0为被选择的能量较高的节点；Et为该节点的整体能量。
4)节点剩余能量均衡度。
当选择的节点能量越高，那么整个网络的均衡度就越高，网络空洞也就可以避免[12]。因此适应度函数f4为：
(10)
式中：u为能量消耗修正系数。
2.3 簇间数据传输优化
在生成簇之后，不同的簇与簇之间会建立一条链路，从而实现不同簇之间的通信。如簇头之间的距离较远，那么对节点能量的消耗会很大，甚至导致簇头因能量消耗过快而出现早亡。为解决这个问题，通常会引入多级跳通信方式。是选择单级跳通信还是多级跳通信，主要取决于节点能量的消耗情况[13]。假设在网络之中存在(n+1)个位于同一个直线上的节点，具体如图2所示，其中相邻节点的距离为d。
图2 节点网络
根据无线通信能耗模型，如果采用单级跳通信，其能量消耗为：
Es_hop=ETs(k,nd)=kEelec+kεfs(nd)2
(11)
式中：Es_hop为单级跳消耗的能量；ETs为接收kbit数据消耗的总能量；εfs为功率放大电路能耗系数；Eelec为节点接收或发送1bit数据时消耗的能量；k表示接收的是kbit数据。
如果采用多级跳通信，其总能量消耗为：
Em_hop=nETs(k,d)+(n-1)ERx(k)=k(2n-1)Eelec+nkεfs(nd)2
(12)
式中：Em_hop为多级跳的能量消耗。
是采用单级跳通信还是采用多级跳通信，只需要比较两者之间的能耗大小即可。
根据上述改进，将分簇路由算法设计如图3所示。
为验证上述算法的正确性，选择MATLAB平台对上述算法与传统的LEACH路由算法进行仿真比较。仿真环境为100个节点随机部署在100m×100m的区域之内。汇聚节点位于区域外， 坐标为(50,150)，监测区域范围坐标为(0，0)到(100,100)。通过一轮分簇，可以得到如图4所示的仿真对比结果。
图3 改进粒子群分簇路由算法
图4 LEACH与改进粒子群算法分簇结果比较
同时验证采用单级跳或者多级跳之后的能量消耗情况，设定c1=c2=2.0，惯性权重ω=0.6，适应度权重因子α,β,λ,ρ分别为0.25,0.20,0.30,0.25，最大循环次数为1 000次。通过仿真可以得到如图5所示的结果。
其中APSO为改进粒子群算法，EBUCP为引入单级跳或多级跳通信的改进离群算法。通过仿真可以看出,本文设计的EBUCP算法在能量消耗方面要差于改进的APSO，但是其能量消耗非常均匀。由此验证该算法可提高整个网络的能量使用效率。
图5 仿真结果比较
本文针对传统分簇算法存在的问题，引入粒子群改进算法和单级跳+多级跳结合通信的方式，实现了无线网络节点的能量优化，为提高整个无线网络的寿命和通信质量奠定了基础，也为无线传感节点的覆盖优化提供了参考。
参考文献：
[1] 司海飞，杨忠，王珺. 无线传感器网络研究现状与应用[J]. 机电工程，2011，28(1)：16-20.
[2] 李建中，高宏. WSN 的研究进展[J]. 计算机研究与发展，201，45(1)：1-15.
[3] 王秋鹏. 无线传感器网络能量优化技术[J]. 新技术新工艺，2014(8)：84-86.
[4] 刘伟，崔永锋. 自适应逃逸粒子群算法的网络节点覆盖优化仿真[J]. 微电子学与计算机，2013(10)：165-168.
[5] 苏淑霞. 粒子群算法在云计算任务调度中的应用[J]. 南京师大学报(自然科学版)，2014(4)：145-149.
[6] 李擎，张超，陈鹏，等. 一种基于粒子群参数优化的改进蚁群算法[J]. 控制与决策，2013(6)：873-878,883.
[7] 张超，李擎，陈鹏，等. 一种基于粒子群参数优化的改进蚁群算法及其应用[J]. 北京科技大学学报，2013(7)：955-960.
[8] 程声烽，程小华，杨露. 基于改进粒子群算法的小波神经网络在变压器故障诊断中的应用[J]. 电力系统保护与控制，2014(19)：37-42.
[9] 高德民，钱焕延，严筱永，等. 无线传感器网络k-Anycast通信模型研究[J]. 计算机科学，2011(8)：33-37.
[10] 廖先林，陆畅，姜婷，等. 一种能耗均匀的WSN分簇路由协议研究与设计[J]. 小型微型计算机系统，2014(10)：2199-2202.[11] 江明华. 通信网簇间的自适应路由算法[J]. 舰船科学技术，2015(4)：199-202,206.
[12] 王菲. 无线传感网络低空干扰下的通信优化模型仿真[J]. 计算机仿真，2015(1)：331-334.
[13] 沈海洋. 基于遗传PSO的无线传感网络覆盖优化算法研究[J]. 微电子学与计算机，2013(3)：148-151.
LI Xiaohong
(College of Information Engineering, Xi'an Eurasian institute, Shaanxi Xi'an, 710065, China)
Abstract：There is a lager random in traditional wireless routing algorithm for choosing nodes, and once selected edge nodes will cause long distance communication, thereby reduce the efficiency of communication. Aiming at above problem, it proposes an energy optimization model based on improved particle swarm optimization algorithm. Using the improved particle swarm algorithm, it optimizes the cluster head selection, and designs a new fitness function for energy of the cluster head cluster head, transmission distance, cluster head distribution and other factors into consideration. This method can reduce the maximum range of network transmission energy loss. In view of the wireless network node premature death, it puts forward a multi path communication mode based on minimum energy consumption, balances the entire wireless network energy and prolongs the network lifetime. The simulation proves this method.
Key words：improved particle swarm optimization algorithm; wireless network; cluster head; energy balance; fitness function
DOI：10.3969/j.issn.2095-509X.2016.11.013
收稿日期：2016-08-08
作者简介：李校红(1976—)，女，湖南邵阳人，西安欧亚学院讲师，主要研究方向为数据通信。
中图分类号：TP
文献标志码：B
文章编号：X(2016)11-0063-04
联系客服
