改进的基于分簇无线传感器网络的数据聚合算法
付帅1, 马建峰1, 李洪涛1, 王长广2
1.西安电子科技大学 计算机学院,西安 710071
2.河北师范大学 信息技术学院,石家庄 050024

作者简介:付帅(1986-),女,博士研究生.研究方向:无线传感器网络,能量有效设计.E-mail:ljhfs0803@126.com

摘要

为了有效地延长分簇无线传感器网络的寿命,提出了一种改进的解决不均衡能量消耗问题的新算法EESA(Energy-efficient separating algorithm)。在考虑簇间能耗平衡的基础上,根据网络拓扑和能量消耗来计算簇半径,对基本的簇划分方式进行了改进,并通过将单个簇头的任务分配给两个节点完成以实现簇内的能耗平衡的方法从任务分离角度对簇头选举策略进行了改进。仿真结果表明:EESA可以有效避免能量洞问题,并减少整个传感器网络的能量消耗,从而延长了网络寿命。

关键词: 计算机系统结构; 无线传感器网络; 分簇; 能量均衡
中图分类号:TP393 文献标志码:A 文章编号:1671-5497(2014)04-1118-08
Improved data aggregation algorithm based on clustered wireless sensor network
FU Shuai1, MA Jian-feng1, LI Hong-tao1, WANG Chang-guang2
1.School of Computer Science and Technology,Xidian University,Xi'an 710071,China
2.College of Information Technical,Hebei Normal University,Shijiazhuang 050024,China
Abstract

In order to effectively prolong the lifetime of cluster-based Wireless Sensor Networks (WSNs), an improved Energy-Efficient Separation Algorithm (EESA) is proposed to solve the uneven energy dissipation problem. On the basis of inter-cluster energy balance, the basic clustering algorithm is improved. EESA uses network topology and energy consumption to calculate q cluster radius. The selection strategy of cluster heads is modified from the perspective of task separation, in which the task of a single cluster head is assigned to two nodes to obtain the intra-cluster energy balance. Simulation results show that EESA can avoid the energy hole problem effectively and reduce energy consumption of the whole WSN, thus prolonging the network lifetime.

Keyword: computer system organization; wireless sensor network; clustering; energy balance
0 引 言

无线传感器网络(WSN)已广泛运用于民用和军事领域中,如智能家居、生物医疗、环境监测、机械制造和空间探索等[ 1]。近年来随着传感器节点的集成化和微型化,节点的电源大多采用能量受限的电池。由于节点通常位于无人区域或危险环境中,难以进行能源补给,而可再生能源技术目前尚不成熟,因此通过优化系统能耗,最大限度地延长网络寿命成为无线传感器网络面临的首要挑战[ 2, 3]

分簇为无线传感器网络提供了一种有效的分布式管理框架[ 4, 5],其优点是方便管理,增强网络的可扩展性及易于实现数据聚合。在多跳转发模式下,簇头之间连接成网络骨干网,对本簇内的数据进行聚合处理后将其中继到基站。但是,距离基站较近的簇头节点常因中继任务过重而提前死亡,从而导致“能量洞”的出现[ 6, 7]。LEACH[ 8](Low-energy adaptive clustering hierarchy)是最早提出的分簇协议,采用等概率随机循环的方式选择簇头。但是LEACH没有考虑以下问题:①所有簇头都将数据直接传送到基站,没有对数据传送阶段作很好的优化;②簇头是随机选取的,不能保证其在网络中均匀分布。此后人们在LEACH协议的基础上进行了改进,以进一步减少能量消耗。MR-LEACH[ 9](Multihop routing with low energy adaptive clustering hierarchy)就是一个典型的改进协议。MR-LEACH根据节点的剩余能量来选择簇头,同时采用多跳传输的方式将数据中继到基站。但该算法中继路径的建立没有考虑所有簇头负载量的均衡,高层的簇头只根据基站广播的控制数据包来确定其中继节点。这会导致某些节点因能耗量过大提前死亡,进而影响网络寿命。文献[10]设计了一种能量有效的分簇算法EECA(energy efficient clustering algorithm),通过优化簇头选举策略及采用构建权值函数以确定中继路径的方式来延长网络的生存期。但这种中继路径的建立方法不能减轻热点区域簇头的负载量,“能量洞”的出现仍然会影响网络的寿命。文献[11]提出了一种ACT(Arranging cluster sizes and transmission ranges for wireless sensor networks)协议,通过计算簇头的能耗量来确定簇半径,然后根据理想位置选举簇头节点。同时,按照中继负载等量分配的原则来构建数据聚合树。但ACT存在以下不足:①随着时间的延长,簇头节点会逐渐偏离理想位置,不能继续保持最优性;②距离基站较近的簇头仍承担着较重的负载,“能量洞”问题没有得到解决。

针对无线传感器网络的自身特点以及上述算法的优缺点,本文提出了一种改进的能量高效的数据聚合算法EESA。分别在簇划分方式,簇头选举策略和数据中继路径的构建方法上进行了改进,同时考虑了簇间能耗平衡和簇内能耗平衡两个方面。新算法不仅减轻了热点区域簇头的负载,更平衡了全网节点的能耗,从而延长了网络寿命。

1 网络模型

考虑一个面积为 L×W的矩形传感器网络( L W分别表示感知区域的长度和宽度), N个传感器节点均匀分布在该区域中。

1.1 假设

(1)基站和传感器节点的位置是固定的。所有节点以密度 ρ均匀分布在该区域中,并通过交换信息来识别自身和基站的地理位置。

(2)每个节点拥有一个唯一标识符(ID)。所有节点的初始能量相同且传输能量可控。在最高能量级状态下,节点可以直接与基站通信。

(3)链路是对称的。如果传输能量已知,节点可以根据接收到的信号强度来估算到另一个节点的距离。

(4)所有节点以相同的固定速率进行感知且不间断地向用户发送数据。每个数据包的长度相等。

1.2 能耗模型

采用经典能耗模型[ 5]进行计算。将一个 l比特的消息传输距离 d消耗的能量为:

式中: Eelect表示发送或接收1 bit的数据消耗的能量; εfs εamp分别表示由发送者和接收者间的不同距离决定的放大1 bit数据所消耗的能量。如果该距离小于一个阈值 d0,使用自由空间模型(fs);否则,使用多径模型(mp)。

接收该消息所消耗的能量为:

聚合该消息所消耗的能量为:

式中: Eagg表示聚合1 bit的数据消耗的能量。

EMAX表示节点剩余能量的阈值。如果一个节点的剩余能量小于该值,它将放弃竞选簇头节点。根据等式(1)(2)(3),可以得到 EMAX的值:

式中: φ表示每一轮获取数据的次数; θ表示聚合数据的压缩比例; d表示当前处理节点和它下一跳节点间的距离; λ表示一个节点的邻居数。

2 改进的能量均衡的数据聚合算法

各种按循环运行的延长无线传感器网络生存周期的节能算法从本质上都是在最小化系统能量损耗的同时,把能量损耗均匀分布到每个节点上。在分簇无线传感器网络中,能耗的不均衡性主要体现在两个方面:①采用多跳传输模式时,不同簇头会因到基站的距离不同而消耗不等的能量,即簇间能耗不均衡问题;②簇头因需要完成比簇内成员节点更多的工作而消耗较多的能量,即簇内能耗不均衡问题。但是簇头也只是普通的传感器节点,能量有限,簇头的过早死亡必然会导致网络寿命的缩短。所以减少簇头节点的能耗,确保整个网络节点能耗的均衡是延长网络寿命的关键。因此,本文所做的一些改进主要从能耗的均衡性出发。

2.1 分簇方式的改进

图1 分层的网络拓扑结构Fig.1 Level structure of network topology

基本的成簇算法在划分簇时不考虑能量的消耗,大致可以分为均匀分簇和不均匀分簇两大类。EESA从能量消耗的角度出发,对分簇方式进行了改进。如图1所示,假定一个实验网络拥有 Y个不同规模的簇层,且每个簇的成员节点都向簇头传送1 bit的数据。为方便计算,我们将位于两个不同层次的簇之间的传输距离看作是它们的半径之和(第1层除外)。也就是说, Y层到 Y-1层的传输距离为( ry+ry-1), Y-1层到 Y-2层的传输距离为( ry-1 +ry-2)等(图2)。由于最外层(第 Y层)的簇头节点没有中继任务而只负责处理本簇内节点传输的数据,它的总能耗可以表示为:

第1项表示簇头节点接收本簇内成员节点发送数据的能耗;第2项表示进行数据聚合的能耗;第3项表示将处理后的数据从第 Y层传输到第 Y-1层的能耗。由于第 Y-1层的簇头节点不仅要考虑本簇内节点传输的数据,还要对中继的 Y层数据进行处理,它们消耗的总能量可以表示为:

同理,第 Y-2层的簇头节点要同时对本簇内和中继的第 Y-1层的数据进行处理,所消耗的总能量可以表示为:

通过这种方式,每一层的簇头节点消耗的总能量可以通过下式计算得到:

其中 r1, r2,…, ry分别表示第1层,第2层,…,第 y层的簇半径; r表示第1层到基站的传输距离(见公式(12)); Ei(1≤ i y)表示第 i层的簇头节点消耗的能量。

由于假定每一层的簇头消耗的能量基本相等,可以用下式来计算每一层的簇半径:

根据式(8)(9),计算得到所有的簇半径,簇划分完成。

图2 簇半径的计算Fig.2 Calculation of cluster radius

2.2 簇头选举策略的改进

为了减轻簇头的负载,不同于以往的单个簇头选举策略,EESA同时选举两个不同的节点——处理节点和转发节点作为簇头节点(见图3)。通过任务分离,

图3 簇头节点选举Fig.3 Election of cluster heads

将单个簇头的任务分配给两个节点完成,以减小簇头和簇内成员节点之间的能耗差。选举结束后,结合2.1节计算得到的簇半径,完成簇的形成过程。簇头节点传输模式如图4所示。

图4 簇头节点传输模式Fig.4 Transmission mode of cluster heads

2.2.1 处理及转发节点选举

在每一轮的开始,每个节点都会在其通信半径范围内广播基本消息 E_Msg( IDs, Ers, L( xs, ys))。 Ers L( xs, ys)分别表示节点 s的剩余能量和位置。所有处在广播源半径范围内的节点都被看作是邻居节点,并在接收到广播消息后更新自己的邻居信息表。每个剩余能量大于 EMAX的节点都有机会参与选举并成为候选节点,假定候选节点所占比例为 p。以第 j层为例(1≤ j Y),簇头的选举过程如下:

每个候选节点 s都会根据更新后的信息表计算其通信半径范围内所有邻居节点的平均剩余能量 Eres:

s和其邻居节点间的平均通信距离可以表示为:

dsm来表示节点 s m之间的距离,则:

同时考虑到剩余能量和距离,每个候选节点分别应用等式(13)(14)来计算处理节点和转发节点的竞争指标值:

其中 μ τ的值是由簇内的节点分布及剩余能量情况决定的。 d( s, BS)表示节点 s和基站之间的距离。然后,候选节点在其通信半径范围内广播竞争消息 Com_Pro( IDs, Ers, CLPs, CLFs)。

广播完成后,所有的候选节点都转换为接收状态并等待时间 T T的长度设定至少要保证节点可以接收到来自所有邻居节点的竞争消息。之后,每个候选节点将自身和接收到的竞争指标值进行对比。 CLP值最大的节点将成功当选为处理节点,而 CLF值最大的节点将成功当选为转发节点。如果出现两个相等的 CLP CLF的最高指标值,拥有较大剩余能量的节点当选。如果一个候选节点同时具备 CLP CLF的最高指标值,它将同时扮演处理节点和转发节点这两种角色。

2.2.2 簇的形成

根据对比结果,竞选处理节点成功的节点将在其通信半径内广播竞选成功消息 Suc_Pro( IDs, Ers, L( xs, ys)),其余节点则等待接收该消息。一旦某个候选节点接收到一个或多个竞选成功消息,它将放弃继续竞争并发送加入消息 Join_Pro( IDs, Ers, L( xs, ys))到接收信号强度最大的广播节点。由于转发节点只负责转发处理后的数据,因此不需要向其所有邻居节点广播竞选成功消息。它只将竞选成功消息添加到加入簇的数据包信息中,并将其发送给同簇的处理节点(如果转发节点和处理节点为同一节点,该步骤省略)。因此,与已有算法相比,本文提出的新算法不会增加更多的消息负载。此后,处理节点会为所有簇成员分配TDMA时隙。

2.2.3 数据聚合树的构建

在数据聚合树的构建过程中,EESA选择距离当前转发节点最近的两个低层处理节点作为候选中继节点,并将候选节点的剩余能量和转发当前数据需要消耗的能量进行对比,根据对比结果确定中继节点。以第 p层和第 q层(1≤ p<q y)为例,假定 q层的某个簇 u的转发节点要在 p层选择一个处理节点作为中继节点。假定 p层的簇 v和簇 w是离簇 u最近的两个簇。根据等式(1), CLFu可以计算出它将数据包分别发送到 CLPv CLPw所消耗的能量差值:

式中: ku表示簇 u发送的数据量。

同时,计算出节点 CLPv CLPw的剩余能量差值:

ΔE ΔET进行对比,若 ΔE的值大于 ΔET,将选择 CPv作为中继节点;否则,选择 CPw作为中继节点。也就是说,距离当前转发节点较远的候选节点只有在它的剩余能量远远大于距离当前转发节点较近的候选节点时,它才可能被选择。每个簇的转发节点都会按照同样的方式找出自己的中继节点,该网络的骨干网形成(见图4)。这种策略不仅考虑了簇头节点的剩余能量,同时考虑了网络总能耗的平衡,因此极大地提高了能量的利用率。

3 算法性能评估
3.1 消息复杂度分析

由于EESA的簇头选举过程是消息驱动的,所以首先讨论算法的消息复杂度。

定理1 EESA成簇算法的消息复杂度为 O( N),其中 N为传感器节点总数。

证明 在簇头选举阶段的开始,所有节点共广播 N个基本消息 E_Msg( IDs, Ers, L( xs, ys))。由于所有剩余能量大于 EMAX的节点都有机会参与选举并成为候选节点,假定候选节点的比例为 p,则 Np个候选节点产生。所有候选节点共发送 Np个竞争消息 Com_Pro( IDs, Ers, CLPs, CLFs)。假定选举得到 k个处理节点,则共要发送 k个竞选成功消息 Suc_Pro( IDs, Ers, L( xs, ys))。相应地,其他普通节点共要发送 N-k个加入簇消息 Join_Pro( IDs, Ers, L( xs, ys))。由于转发节点只需要将竞选成功消息添加到加入簇数据包中,所以不会产生额外的消息负载。因此,在每轮的成簇阶段需要广播的消息总数为 N+Np+k+N-k=( p+2) N,即 O( N)。

表1给出了EESA与其他同类算法消息复杂度的对比结果。由表1可知,虽然EESA选举两个不同的节点作为簇头,它的消息复杂度并没有增加。所以很明显,EESA的性能要优于其他已有算法。

表1 消息复杂度对比 Table 1 Comparison of message complexity
3.2 正确性分析

定理2 如果两个节点互为邻居,二者在参与簇头选举时不会产生冲突。

证明 假定 Su Sv是两个邻居节点,二者同时参与簇头竞争选举。根据EESA,如果 Su Sv拥有相等的 CLP CLF的最高指标值,拥有较大剩余能量的节点当选。在二者的 CLP CLF的最高指标值相等且剩余能量相等的情况下,若 Su首先成为簇头节点,则会发送竞选成功消息通知 Sv, Sv接到消息后会退出竞争成为普通节点。反之亦然。因此,EESA的簇头选举策略不会引起邻居节点间的冲突,选举得到的簇头分布状况良好。

4 仿真实验

实验将EESA与ACT[ 11],EECA[ 10]和MR-LEACH[ 9]算法在网络寿命、平均剩余能量、簇头节点的能耗标准差及节点平均剩余能量的变化等几个方面进行了对比。所有节点都在彼此相互的感知范围内以保证正在进行的传送不会被其他节点破坏。

4.1 仿真环境

仿真结果由网络仿真器Omnet++实验得出。假定MAC层是理想的且通信链路无误。实验在稳态下进行,仿真参数如表2所示。

表2 仿真参数 Table 2 Simulation parameters
4.2 实验结果

4.2.1 网络寿命

应用几种不同算法时的网络寿命曲线如图5所示。从图中可以看出,采用EESA的网络寿命最长。MR-LEACH只根据节点的剩余能量来选择簇头,EECA在选择簇头时同时参照节点的剩余能量和通信距离等因素,但是由于二者没有对多跳通信模式下簇头能量消耗的不均衡性做出改善,部分簇头节点的过早死亡导致了网络寿命的缩短。ACT根据每个簇头的能耗量对簇的规模进行调整,但是同样存在能量洞问题。同时,随着时间的进行,选举得到的簇头节点会逐渐偏离理想位置,使得簇头与簇内成员节点之间的能耗差值迅速增大。而EESA通过计算簇间能耗来确定簇,同时采用任务分离方法减少关键节点的能耗,从而延长了网络的寿命。由此可见,EESA算法能够均衡节点间的能量消耗,对于提高传感器网络的生存时间具有重要意义。

图5 网络寿命Fig.5 Network lifetime

4.2.2 平均剩余能量

图6给出了4种算法中节点的平均剩余能量。显然,EESA算法对节点能耗的控制比较好。MR-LEACH,EECA和ACT都采用了多跳通信模式,节点剩余能量的差别在于它们的簇头选举方式和数据聚合树的构建方式不同。在每一轮簇头选举中,

图6 平均剩余能量Fig.6 Average residual energy

MR-LEACH直接指定剩余能量最大的节点为簇头,并由基站来确定每个簇头的下一跳节点。EECA在选举簇头时同时考虑了剩余能量和通讯距离两个因素,并通过构建一个由这两个因素关联而成的权值函数来为每个簇头选择最优的中继节点。ACT根据每个簇头的能耗量来计算簇半径,然后选举最接近理想位置的节点作为簇头。同时,按照中继负载等量分配的原则来构建数据聚合树。由此可见,MR-LEACH因缺乏对影响因素的全面考虑而导致了过多的能耗;EECA没有对热点问题做出任何改善,能量洞仍然存在;而ACT则会由于运行后期所选簇头节点远远偏离理想位置而导致能耗的增加。EESA从三个方面改善了热点问题:①根据簇头的总能耗相等来计算簇半径,达到了簇间的能耗平衡;②同时选举两个节点来共同完成单一簇头的工作,通过任务分离减缓了簇内关键节点的能耗;③通过计算差值 ΔE-ΔET来构建数据聚合树,实现了整个网络总能耗的平衡。因此,EESA具备最高的能量效用,剩余能量最多。

4.2.3 簇头节点的能耗标准差

图7所示,由于簇头的选举方式和承担的负载量不同,簇头节点的能耗标准差也呈现出不规则的振荡。在簇头选举过程中,MR-LEACH只考虑节点的剩余能量,EECA算法设计同时参照了节点的剩余能量和通讯距离这两个因素。在多跳通信模式下,每个簇头因负载量不同而消耗不同的能量。所以,MR-LEACH和EECA算法曲线波动较大,簇头节点能量消耗不均衡。ACT根据簇头的能量消耗来计算簇半径,在一定程度上减轻了热点问题。同时,后期维护采用的跨层数据传输模式也使得位于不同层次的簇头拥有相近的能耗量。因此,ACT的算法曲线相对平稳。从图中可以看出,EESA算法的曲线最稳定。这是因为EESA采用簇头节点负载平衡的思想来减轻热点问题,同时,簇头任务的分离降低了簇内关键节点的能耗,避免了能量差异较大的节点出现。

图7 簇头能量消耗标准差Fig.7 The standard deviation of energy consumption of cluster leaders

4.2.4 平均剩余能量的变化

图8给出了网络中节点平均剩余能量的变化曲线。本文采用节点平均剩余能量的变化来衡量几种算法能耗的均衡程度。平均剩余能量的变化越小,表明能耗越均衡。由图8可以看出,与其余3种算法相比,EESA的平均剩余能量的变化较小,即获得了更均衡的能耗。这是因为,在采用EECA,ACT,和MR-LEACH这三种算法时,“能量洞”问题明显,距离基站较近的簇头节点常因负载过重而先于其他节点死亡,从而导致了其平均剩余能量变化曲线的振荡。而EESA同时从簇间和簇内能耗平衡角度进行了考虑,有效地缓解了“能量洞”效应,所以平均剩余能量的变化最小。

图8 平均剩余能量的变化Fig.8 Variance of average residual energy

5 结束语

降低能量消耗是无线传感器网络的一个根本问题。本文针对分簇无线传感器网络中的能量消耗不均衡问题,提出了一种改进的新算法EESA。该算法分别从簇间和簇内的能耗平衡角度进行考虑,对基本的簇划分方式和簇头选举策略进行了改进。根据网络拓扑和能量消耗来成簇的方式解决了多跳模式下簇头因负载量不同而导致能耗量不同的问题,实现了簇间的能耗平衡。同时,任务分离方法有效降低了簇内关键节点的能耗,使得网络内所有节点的能耗量趋向于均衡。仿真结果表明,该算法可以有效提高WSN的能量利用率并延长网络寿命。

The authors have declared that no competing interests exist.

参考文献
[1] Kalpakis K. Everywhere sparse approximately optimal minimum energy data gathering and aggregation in sensor networks[J]. ACM Transactions on Sensor Networks, 2010, 7(1): 1-23. [本文引用:1]
[2] Aslam N, Phillips W, Robertson W, et al. A multi-criterion optimization technique for energy efficient cluster formation in wireless sensor networks[J]. Information Fusion, 2011, 12(3): 202-212. [本文引用:1] [JCR: 2.262]
[3] 林恺, 赵海, 尹震宇, . 一种基于能量预测的无线传感器网络分簇算法[J]. 电子学报, 2008, 36(4): 824-828.
Lin Kai, Zhao Hai, Yin Zhen-yu, et al. A clustering hierarchy arithmetic based on energy prediction for wireless sensor networks[J]. Acta Electronica Sinica, 2008, 36(4): 824-828. [本文引用:1] [CJCR: 0.686]
[4] Kim T, Lee Y, Sung J, et al. Hierarchical network protocol for large EESAle wireless sensor networks[C]∥Proc of IEEE Consumer Communications and Networking Conference, Las Vegas: CCNC, 2010: 1-2. [本文引用:1]
[5] 杨靖, 熊伟丽, 秦宁宁, . 用于无线传感器网络的高能效数据收集算法[J]. 吉林大学学报: 工学版, 2011, 41(6): 1720-1725.
Yang Jing, Xiong Wei-li, Qin Ning-ning, et al. Energy-efficient data gathering algorithm for wireless sensor networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2011, 41(6): 1720-1725. [本文引用:2] [CJCR: 0.701]
[6] Liu A F, Zhang P H, Chen Z G. Theoretical analysis of the lifetime and energy hole in cluster based wireless sensor networks[J]. Journal of Parallel and Distributed Computing, 2011, 71(10): 1327-1355. [本文引用:1] [JCR: 0.859]
[7] 李巧勤, 刘明, 杨梅, . 负载相似节点分布解决传感器网络能量洞问题[J]. 软件学报, 2011, 22(3): 451-465.
Li Qiao-qin, Liu Ming, Yang Mei, et al. Load-similar node distribution for solving energy hole problem in wireless sensor networks[J]. Journal of Software, 2011, 22(3): 451-465. [本文引用:1] [CJCR: 2.181]
[8] Heinzelman W R, Chand rakasan A, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670. [本文引用:1] [JCR: 2.418]
[9] Farooq M O, Dogar A B, Shah G A. MR-LEACH: multi-hop routing with low energy adaptive clustering hierarchy[C]∥Proc of the IEEE Fourth International Conference on Sensor Technologies and Applications, Venice/Mestre: SENSORCOMM, 2010: 262-268. [本文引用:2]
[10] Sha C, Wang R C, Huang H P, et al. Energy efficient clustering algorithm for data aggregation in wireless sensor networks[J]. Journal of China Universities of Posts and Telecommunications, 2010, 17(Suppl2): 104-109, 122. [本文引用:1] [CJCR: 0.596]
[11] Lai W K, Fan C F, Lin L Y. Arranging cluster sizes and transmission ranges for wireless sensor networks[J]. Information Sciences, 2012, 183(1): 117-131. [本文引用:1] [JCR: 3.643]