一种基于改进粒子群的无线传感器网络层次化聚类协议*

王 宁,周 圆,刘敬浩

(天津大学 电子与信息工程学院,天津 300072)

一种基于改进粒子群的无线传感器网络层次化聚类协议*

王 宁,周 圆*,刘敬浩

(天津大学 电子与信息工程学院,天津 300072)

延长网络的生存周期是无线传感器网络路由设计的主要目标之一。簇头的高能耗是网络快速死亡的一个重要原因。提出一种基于改进粒子群PSO(Particle Swarm Optimation)的无线传感器网络聚类路由协议IPSOCH。利用中继节点来分担簇头数据转发的任务,减轻簇头节点的负载,并利用改进的粒子群算法通过节点的剩余能量信息和位置信息来选择簇头和中继节点。仿真实验表明,IPSOCH协议比起现有的几种路由协议,能有效提高能量使用率,延长网络生存周期。

无线传感器网络;延长生存周期;分簇;中继节点;粒子群

无线传感器网络WSN(Wireless Sensor Network)是一种由大量传感器节点以自组织形式构成的无线网络系统,以协作的感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息,并最终把这些信息发送给汇聚节点或者基站[1]。在传感器网络中,每个传感器节点的计算能力、存储容量和通信能力都受到限制,而且,在许多无线传感器网络应用中,传感器节点被部署在恶劣环境中,造成更换电池困难而且昂贵。因此,在大多数情况下,传感器节点必须实现在较长时间内保持工作能力。所以,延长网络生存周期是网络路由协议设计中重点考虑的内容[2]。

目前,在无线传感器路由协议中,基于簇结构的层次化路由协议是延长网络生存时间的一种有效方法。最典型的无线传感器网络分簇路由协议是LEACH协议[3],其依据事先设定的概率来选择簇头节点,使各传感器节点轮流成为簇头从而均衡簇头节点的能耗。然而,由于簇头选择的随机性,能量低的节点也有可能被选为簇头节点,从而导致簇头节点过早死亡。此外,在LEACH协议中,簇头节点和基站之间信息传输完全采用单跳模式,这将会造成大量能量消耗,并且在簇头节点远离基站时会导致簇头的能耗过大。在此基础上文献[4]提出LEACH-C协议,其节点的剩余能量信息被加入簇头选择概率函数中,因而高能量的节点被选为簇头的概率更高。然而,LEACH-C协议在选择簇头时并没有考虑到节点的位置信息。文献[5]结合节点的数据传输的能耗,提出一种单跳与多跳结合的协议。文献[6]通过对簇头数量的估计控制簇头数量来均衡能耗,延长网络生存时间。文献[7]将数据采集周期与数据通信周期分离,采取簇内可变通信策略来减少能耗。

文献[8]提出的HEED协议是一种混合式分簇协议,依据节点的剩余能量为选择标准随机选出候选簇头,然后根据簇内能量的消耗代价产生最终的簇头。HEED协议限定在一定范围内仅有一个簇头,从而使整个网络的簇头分布更加均衡。但是HEED协议仅仅考虑到簇内的能耗而没有考虑到簇头与基站的距离。文献[9]提出了一种新型的无线传感器网络聚类协议EECS。在EECS协议中,通过竞争的方式选择簇头并考虑到了簇头与基站的距离。如果一个节点发现其在竞争范围之内较其他节点具有更高能量,便会申请成为簇头节点并广播给其他节点。然而,这个协议不适用于高密度的网络之中,因为会有较多的节点竞争成为簇头。TCAC协议[10]改进了EECS协议,其在确保整个网络的连通性的同时采用了动态控制节点的传输功率级的方法而使全网的能耗最少。

在大多数实际应用中,基站与传感器网络相距较远,簇头节点收发消息较之于其他节点都要消耗更多的能量。在有些协议中采用中继节点来分担簇头的数据传输任务,降低簇头节点的能量消耗,但大部分协议的中继节点是随机利用的。SEECH协议[11]是第1个通过一定参数选择中继节点的路由协议。在SEECH协议中,一部分剩余能量较高的节点被选作中继节点,簇头选择距其最近的中继节点作为下一跳节点。即簇头从该簇成员节点接收数据并进行数据融合,再将融合后的数据发送给中继节点,再由中继节点将数据发送给基站。这样,中继节点承担了簇头的传输任务,降低了簇头节点的能耗。然而,两个或多个簇头可能同时选择一个中继节点作为下一跳节点,这将造成中继节点能耗过快。此外,簇头选择中继节点时需要额外的能量开销。同时,在中继节点的选择过程中也未考虑节点的地理位置信息。

本文在总结前人已有的路由协议的基础上,提出了一种基于改进PSO算法的无线传感器网络层次化聚类协议IPSOCH来延长网络的生存时间。首先,用中继节点均衡簇头的能耗。与SEECH协议不同的是,每个簇头都对应于一个中继节点。这样做有两个好处:①簇头节点无需额外的能量来选择其下一跳节点;②避免了在中继节点选择过程中的消息冲突。此外,中继节点的选择不仅仅考虑了节点剩余能量,还会参照其与对应簇头的距离以及自己和基站的距离。最后根据节点的剩余能量信息和位置信息建立适应值函数,并利用改进的PSO算法来选择出合适的簇头和中继节点。

1 系统模型

1.1 网络模型

假定网络中具有N个传感器节点,被均匀部署在边长为M的正方形区域中,并持续地对环境进行监测。传感器网络模型具有以下性质:①每个传感器节点的能量是有限的,并且每个节点部署后都有一个唯一标识(ID)且位置是已知的;②每个节点的功能相同,均具有融合数据的能力;③传感器节点和基站部署后都处于不再发生位置移动;④节点一旦部署将无法维护,即节点无法进行电池更换;⑤每个节点的发射功率可以根据与接收端的距离进行调节。

图1 能量消耗模型

1.2 能耗模型

本文采用与文献[12]相同的能耗模型,如图1所示。向距离为d的目标节点发送一个k比特的数据包的能耗为:

(1)

节点接收k比特数据消耗的能量为:

ERX(k)=kEelec

(2)

数据融合也会消耗一定的能量,融合单位比特数据所耗费的能量用EDA表示。

2 IPSOCH分簇路由协议

在本协议中,节点被分为簇头,中继节点和普通节点。与LEACH协议相似,协议的执行过程具有周期性,每轮循环周期分为两个阶段:簇建立阶段和数据传输阶段。在簇建立阶段,簇头与中继节点以及各个节点的通信链路被确定,从而全网拓扑被建立起来。在数据传输阶段,普通节点将感知到的信息传送给簇头,簇头将数据融合后传送给中继节点,中继节点再将数据传送给基站。

2.1 簇头的选择

我们假设在全网范围内随机部署了N个传感器节点,并被分成n个个簇。我们定义簇头的集合为CH,即CH={CH1,CH2,…,CHj,…,CHn},将非簇头节点的集合定义为non-CH。

在本协议中,簇头负责接收簇内节点的数据,数据融合以及与相对应的中继节点进行通信。在簇头选择中将考虑节点的剩余能量和位置信息。基于以上两点本文采用以下适应值函数:

(3)

(4)

(5)

如果一个节点剩余能量更多且距离基站更近,其被选择成为簇头的可能性更大。所提出的节点选择方式可看做NP困难问题(非确定性多项式困难问题)。本文中,我们采用改进型PSO来解决这一问题,详见2.3节。

2.2 中继节点的选择

为了降低簇头节点能量消耗,协议利用中继节点分担簇头节点的数据传输任务。中继节点应该具有以下特点:①节点具有较高的能量,因其相较于普通节点能耗更大;②节点距离基站和簇头比较近,因为传输数据消耗能量是节点最主要的能耗。与其他协议不同的是,本协议中中继节点的选择与簇头节点相关联,并且每个簇头节点只对应一个中继节点。因此,簇头节点与中继节点间的通信开销将会降低。

我们定义中继节点的集合为RL,即RL={RL1,RL2,…,RLz,…,RLn},定义普通节点集合为CO。与3.1小节中的簇头选择方式相类似,为了选择中继节点,我们定义了一个适应度函数:

(6)

(7)

(8)

2.3 基于改进粒子群的目标节点更新算法

粒子群优化算法[13]是Eberhart 和 Kennedy两位博士提出的,其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。因其具有收敛速度快、简单、高效等特点,PSO已经成为一种被广泛应用的优化算法,并成功应用于许多实际问题。因此,PSO可以用来进行网络中簇头和中继节点的选择。然而,PSO算法局部搜索能力较弱,导致其收敛性较差,为了解决这一问题,我们通过线性改变惯性权重来改进PSO算法。算法由如下5个主要步骤组成:

①优化问题和算法参数初始化。创建一定数量的粒子,每个粒子代表问题的初始解,即选择出的目标节点,粒子的数量设为M,每个粒子i具有一个速度矢量vi=[vi1,vi2,…,vid]和一个位置矢量xi=[xi1,xi2,…,xid]来表示其当前状态,式中i为正整数,代表粒子群中的某一粒子,d代表问题的维数。

②计算适应值函数。在d维空间中进行粒子搜索,依照式(3)或式(6)来计算每个粒子的适应值,在搜索过程中,每个粒子记录个体最优解Pi=[pi1,pi2,…,pid]和由粒子群中任全局最优解Pg=[pg1,pg2,…,pgd]。

③更新速度和位置矢量。粒子的速度根据下式进行更新:

(9)

粒子位置更新公式为:

(10)

式中:vij是第i个粒子速度矢量的第j维值,通常被约束在区间[vmin,vmax]间,用以表示粒子的增长。数r1、r2∈[0,1]是d维空间中产生的随机数。c1和c2为加速因子,通常设为2.0或根据状态更新进行动态控制。参数w为惯性权值,其大小决定了粒子前一次迭代过程的速度对本次迭代过程中粒子速度信息的影响深度,从而权衡局部搜索能力和全局搜索能力。当惯性权值比较大有利于粒子跳出局部搜索寻找全局最优解,相反惯性权值比较小时,有利于寻找局部最优解,加快收敛速度。

④惯性权值调整。为了避免算法陷入局部最优解搜索,本文中采用了一种改进型的PSO算法[14],通过调整惯性权值来避免陷入局部搜索,其权值可由式(11)表示:

(11)

式中:wmax和wmin分别表示最大和最小惯性权值,并且通常设为0.9和0.4。Interationmax为最大允许迭代次数,Interationi表示当前迭代次数。

⑤返回到步骤③进行循环,直到达到最大迭代次数。当前最优解即选为目标节点。

2.4 协议描述

①簇建立阶段:每一个节点通过一条Node-MSG信息来广播自己的剩余能量信息和位置信息,基站通过这些信息选出簇头。在簇头被确定后,每个簇头将会向整个网络广播一条消息(即CH-ADV)来表明身份,其采用了载波监听多路访问(CSMA)MAC协议。这一消息包括簇头ID和用于表明身份的报文头。类似地,一旦中继节点被确定,一个包括中继节点ID、对应簇头节点ID和表明身份的报文头的消息RL-ADV被广播到全网来明确其中继节点的身份。每个普通节点基于从每个簇头接受的CH-ADV消息的强度,选择最近的簇头加入。在每个普通节点确定其所加入的簇头之后,其必须向其簇头发送JOIN-REQ消息来表明身份。这一消息同样较为简单,由节点ID,所属簇头ID和发送节点剩余能量信息组成。这样,节点簇形成,网络中每个节点的身份确定下来。

节点簇中的簇头作为控制中心进行数据传输的协调工作。簇头建立一个TDMA时间表,时间表用来分配普通节点与簇头以及簇头与中继节点之间的通信时隙,并广播SCHEDULE-MSG消息给簇中普通节点和相应中继节点。这避免了消息的冲突,也使得在普通节点的非传输时段和中继节点的非接收时段,其无线电模块可以处于休眠状态来节省能量的消耗。这一方法可增加频谱效率,降低每个节点的能量损耗。当所有节点均获取了TDMA时间表后,节点簇建立阶段完成,同时在特定网络拓扑状态下的数据传输阶段开始。

②数据传输阶段:在这一阶段,普通节点根据TDMA时间表向其簇头传输数据。簇头则必须一直处于工作状态来接受簇内节点发送的数据,并将这些数据进行融合。此后,簇头将已融合的数据发送给中继节点。通过分析簇头节点建立的TDMA时间表,中继节点可以控制接收器开关状态来节省能量。最后,中继节点将融合的数据传送给基站。

2.5 消息复杂度分析

假设网络中有N个节点,其中选出有n个簇头和n个中继节点,在每一轮的开始,每一个节点广播了一条Node-MSG 信息,复杂度为O(N);在每一轮中,每个簇头需要广播一个CH-ADV消息和一条SCHEDULE-MSG时间表消息,复杂度为O(2n);每一个中继节点也要广播一条表明身份的RL-ADV消息,复杂度为O(n);另外每一个普通节点需要发送一条JOIN-REQ来加入簇头,复杂度为O(N-2n)。所以整个协议消息复杂度为O(N+N-2n+n+n+n),即O(N)。

3 性能分析与仿真

本节通过计算机仿真来评估所提出的路由算法的性能。我们知道节点数量,网络覆盖面积和基站位置是影响整个网络生存周期的3个最主要参数。本节将这3个参数纳入考虑,通过与其他路由协议的比较来评估本协议。仿真采用MATLAB数学工具实现,下面所列出的实验值是经过20次试验取得的平均值。

表1 仿真参数

本协议采用改进型PSO算法来增强PSO算法的搜索能力。图2将协议与基于PSO的协议进行了性能对比。如图所示,较于基于PSO的协议,本协议在第1个节点死亡的时间(First Node Die,FND),一半节点死亡的时间(Half of Nodes Die,HND)和全部节点死亡的时间(Last Node Die,LND)分别提高109.6%,111.0%和108.0%。改进型PSO算法利用线性改变权重的方法来避免粒子局限于搜索局部最优解,因此簇头和中继节点选择会更加合理,使得协议的生存周期更长。

图2 改进PSO与基本PSO性能比较

图3 情景1中死亡节点数量变化

实验中根据节点数量,网络覆盖面积和基站位置不同设计了3个场景来评估本协议的性能,如表2所示。我们将本协议与LEACH[4],TCAC[10]以及采用了中继节点的SEECH[11]进行性能比较。

表2 3种仿真方案

图3～图5给出了存活节点的数量随轮数的变化。由图3、图4可看出,IPSOCH协议的网络的生存周期明显长与其他3种协议。由图5可以看出,本协议的第1个节点虽然比SEECH早死,但最后一个节点死亡时间却比SEECH高出50%,说明IPSOCH协议能够很好的节省能量,延长网络的生存周期。

图4 情景2中死亡节点数量变化

图5 情景3中死亡节点数量变化

SECCH和IPSOCH协议中都利用了中继节点,虽然增加中继节点的选择这一步骤在一定程度上会增加协议的复杂度,但是很大的延长了网络的生命周期。在SEECH中,两个或多个的簇头可能选择同一个中继节点,造成中继节点的能量被快速消耗。在本协议中,针对每一个簇头对应选择出一个合适的中继节点,因此簇头不需要额外能量来选择其下一跳节点,此外在中继节点的选择不仅基于节点剩余能量,还需考虑与对应的簇头和基站的距离因素。所以,IPSOCH协议能够很好的延长网络的生存周期。

5 结语

本文提出了一种层次型聚类无线传感器网络路由协议。该协议利用中继节点分担簇头节点的能耗,根据节点的剩余能量和位置信息,利用改进的粒子群算法来优化节点簇的建立过程,使数据传输距离最短且整个网络能耗最小,因此全网生存周期得以延长。实验通过改变节点密度,网络覆盖面积和基站位置,表明协议可以很好的延长网络的生存周期。

[1] 李凌晶,孙力娟,王汝传,等. 能量有效的无线传感器网络可信路由协议[J]. 系统工程与电子技术,2010,32(12):2711-2715.

[2] 张文梅,廖福保. 改进的无线传感器网络非均匀分簇路由算法[J]. 传感技术学报,2015,28(5):739-743.

[3] Heinzelman W B,Chandrakasan A P,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[4] 杜超. 基于NS2的LEACH-C协议分析与仿真[J]. 电子测量技术,2011,34(9):121-123.

[5] 李亚男,徐夫田,陈金鑫. 基于LEACH的WSNs分簇优化策略[J]. 传感技术学报,2014,27(5):670-674.

[6] 吕涛,朱清新,张路桥. 一种基于 LEACH 协议的改进算法[J]. 电子学报,2011,39(6):1405-1409.

[7] 叶继华,王文,江爱文. 一种基于LEACH的异构WSN能量均衡成簇协议[J]. 传感技术学报,2015,28(12):1853-1860.

[8] Younis O,Fahmy S. HEED:A Hybrid,Energy-Efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[9] Manjeshwar A,Agrawal D P. Teen:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks[J]. Parallel and Distributed Processing Symposium,International. 2001,3:30189a.

[10] Dahnil D P,Singh Y P,Ho C K. Topology-Controlled Adaptive Clustering for Uniformity and Increased Lifetime in Wireless Sensor Networks[J]. Wireless Sensor Systems,IET,2012,2(4):318-327.

[11] Tarhani M,Kavian Y S,Siavoshi S. SEECH:Scalable Energy Efficient Clustering Hierarchy Protocol in Wireless Sensor Networks[J]. Sensors Journal,IEEE,2014,14(11):3944-3954.

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

[13] Kenney J. The Particle Swarm:Social Adaptation of Knowledge. Evolutionary Computation,1997.,IEEE International Conference on. IEEE,1997:303-308.

[14] Zhan Z H,Zhang J,Li Y,et al. Orthogonal learning particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2011,15(6):832-847.

A Clustering Hierarchy Protocol Based on an Improved PSO Algorithm in Wireless Sensor Networks**

WANGNing,ZHOUYuan*,LIUJinghao

(School of Electric Information Engineering,Tianjin University,Tianjin 300072,China)

Maximizing the lifetime is a major objective for designing and planning the operation of a wireless sensor network(WSN). Huge energy consumption of cluster heads is the vital reason for the network’s rapidly death. A clustering hierarchy protocol for WSN was brought forward. The protocol takes both energy efficiency and transmission distance of the nodes into consideration,and relay nodes are used to balance the heavy consumption of cluster heads. In this way,the network results in better distributed sensors and a well-balanced clustering system enhancing the network’s lifetime. Simulation experiments compare the proposed protocol with comparative protocols by varying a number of parameters,e.g.,the number of the nodes,the network area size,and the position of the BS. Simulation results show that the proposed protocol performs well over other comparative protocols in various scenes.

wireless sensor networks;prolong network lifetime;clustering;relay node;PSO

王 宁(1991-),男,天津大学硕士研究生,主要研究方向为无线传感器网络,wangning866@tju.edu.cn;周 圆(1983-),女,博士,天津大学副教授,主要研究方向为无线传感器网络,网络视频通信,视频编码与传输等,zhouyuan@tju.edu.cn; 刘敬浩(1963-),男,天津大学副教授,主要研究方向为网络虚拟环境技术、计算机通信等,liujinghao@tju.edu.cn。

项目来源:国家863项目(2015AA01A706);国家自然基金项目(61201179,61571326)

2016-03-17 修改日期:2016-08-29

TP393.1

A

1004-1699(2017)01-0120-06

C:6150P

10.3969/j.issn.1004-1699.2017.01.022