低冗余度WSN 非均匀分簇算法应用研究

陈 树，韩 进，蒋 伟

(江南大学物联网工程学院，江苏 无锡 214122)

1 概述

无线传感器网络理论研究模型大都基于高节点冗余度的网络，但在很多应用场景中，部署高冗余度的无线传感网络是不现实的。通常用于工业生产的无线传感网络节点价格比较高，不会有大量的冗余节点，这就造成了整个网络节点的低冗余度。这种低冗余度要求整个系统数据传输的能耗均匀分布和传感节点之间的能耗均匀，避免出现节点早衰现象。作为传感器网络数据传输路径选择的路由策略对均衡节点能耗负载、节省通信能量、延长网络生存时间起决定作用［1］。但常规的路由协议不能简单直接地应用到低冗余度的网络中，必须选择基本的路由算法并进行适当地修改，以符合实际应用场景。通过对现有无线传感器网络路由算法的研究，发现分簇路由协议技术能显著降低数据延迟，提高能量利用率，有效延长网络生命周期，相比之下具有更好的适用性。目前，研究者已就如何延长无线传感器网络生存时间提出多种分簇路由协议。例如，Heinzelman 等人提出了经典的低功耗自适应分簇协议LEACH［2］，设计思想是随机按“轮”的形式以一定概率周期性的循环选择簇首节点，即让节点轮流担任簇首，从而将网络中的能量负载平均分配到每个传感器节点，延长网络生存周期。但此算法是随机选取簇头，难以保证每轮的簇头数目一致和簇头在网络中均匀分布，无法确保整个网络能耗的均衡性，可能会出现节点成堆死亡的情况。之后Heinzelman 等人又提出了LEACH-C 算法［3］，该算法虽然提高了成簇质量，采用多跳的簇间路由机制，但是其网络流量、时间延迟及信号干扰的概率会增加，成簇开销也增大，存在严重“热区”问题。文献［4］提出了一种EECS 的非均匀分簇算法，该算法通过选举得到簇首节点，剩余节点根据通信代价公式，选择加入到代价最小的簇中，从而构造大小不同的簇以均衡簇首负载，然后簇首以单跳的方式与基站通信。之后文献［5］又提出了一种新的非均匀分簇路由算法EEUC，构造不同规模的簇来改善多跳路由的“热区”问题。但上述2 种算法都存在簇首数目随机和簇间传输方式单一的问题，造成簇首能耗不易控制。

对于低冗余度网络，任何节点的过早死亡、能耗不均和不稳定因素都会给工业生产过程造成较大影响。由于上述各种分簇协议均存在一些问题，因此不能直接应用到低冗余度的网络。针对该问题，本文提出一种基于粒子群优化(Particle Swarm Optimization，PSO)算法和最短路由树的分簇路由算法。该算法在EEUC 协议基础上引入粒子群算法优化非均匀分簇过程，并将所有簇首节点以基站为根构成最短路由树，树内节点通过多跳路由将数据传输给基站。

2 网络模型

2.1 前提假设

假设无线传感器网络的特性如下:

(1)节点均匀部署在方形网络中，且位置不再变动;基站位于网络空间外侧，其能量和计算能力不受限制，传输范围覆盖整个网络。

(2)簇首节点和普通节点的ID 号均唯一，且簇首节点具有数据融合和转发能力。

(3)节点位置坐标已事先测得，发射功率可根据接收节点的距离自动调节。

(4)每个普通节点最大通信半径设为Rmax，簇首节点的竞争半径设为Rc。

(5)算法无需周期性地从普通节点中选取簇首节点，由控制中心根据选簇机制一次性选取固定数目的簇首节点，最后可由工作人员根据选好的最优簇首组合的位置部署簇首节点。

2.2 能量模型

无线传感器网络的能耗大部分来自通信，通信所消耗的能量比感知和计算所消耗的能量要大得多，本文不考虑节点运算和存储所消耗的能量，参考文献［2］得到本文算法的无线通信能耗模型，发送和接收l 字节数据的消耗能量分别为:

其中，l 表示收发的字节数;d 表示通信距离;在文献［5］中若通信距离小于阈值d0，功率放大损耗采用自由空间模型;若通信距离不小于阈值d0时，采用多路径衰减模型;Eelec表示收发电路的基本功耗系数;Efs，Eamp表示功率放大电路的功耗系数。

3 本文算法

基于粒子群和最短路由树的非均匀分簇路由算法采用集中式控制策略［6］，簇首选举和最短路由树建立过程的能量开销都由能量不受限制的基站承担执行，从而减少网络传感节点的能耗，较好地适应了低冗余度无线传感网络。整个算法过程分为3 个阶段:粒子群优化的非均匀分簇阶段;基站和簇首节点之间建立最短路由树阶段;数据传输和路由更新阶段。

3.1 非均匀分簇

非均匀分簇阶段分为簇首选取和普通节点加入簇，而簇首选取引入粒子群优化算法完成非均匀分簇。PSO 算法具有收敛速度快、算法简单和易于实现等优点，在求解单目标优化问题上是一种有效的方法［7］，将其引入簇首选取阶段可以减少非均匀分簇算法的复杂度。

首先，为达到非均匀分簇效果，分簇时引入大小不同的竞争半径，如式(3)所示，竞争半径是根据簇首到基站距离计算得到，使得远离基站的簇首数量少，成簇规模大;靠近基站的簇首数量多，成簇规模小［8］。

其中，λ 属于［0，1］的常数;Dmax和Dmin分别表示簇首节点和基站之间距离的最大值和最小值;d(Cm，BS)表示簇首节点Cm到基站的距离;R0为竞争半径最大值。

其次，在PSO 算法优化分簇过程时，适应值函数设定是否理想直接决定最终选取的簇首优劣。根据本文研究背景，算法将簇内通信代价和簇首位置作为适应值函数的影响因子。因此，PSO 算法的适应值函数可构造为:

其中，f1(pi)为成簇紧凑性评价因子，等于普通节点至其簇首的最大平均欧式距离;Cpi，m表示粒子pi中簇首Cm所属普通节点数目;f2(pi)为所有簇首包含节点数之和与节点总数比值的倒数，表示簇首节点覆盖范围的大小;α 和β 属于［0，1］且α+β=1，通过调节f1(pi)和f2(pi)在适应值函数中所占比例，从而优化簇分布及簇选择。根据适应值函数的定义，本文PSO 优化分簇过程可以简单描述为:在假定的网络搜索空间中，找到一个最优簇首组合(M 个簇首)，使得适应函数值最小。PSO 优化分簇算法基本步骤如下:

(1)初始化Q 个粒子，每个粒子包含M 个簇首节点，代表一种可能的分簇方式。

(2)初始化每个粒子pi:

1)初始化粒子pi的位置，即从［0，L］内随机产生一个实数作为每个粒子位置向量中每一维的值。

2)初始化粒子pi的速度，即从［-V，V］内随机产生一个实数作为每个粒子速度向量中每一维的值。

(3)计算每个粒子的适应函数值:

1)对于每个普通节点ci(i=1，2，…，N)，计算其到所有簇首节点Cm(m=1，2，…，M)的距离d(ci，CHpi，m);根据式(3)计算每个簇首的竞争半径，并计算其竞争半径范围内所包含的的节点数Cpi，m。

2)运用式(4)～式(6)计算粒子的适应函数值fit(pi)。

(4)确定每个粒子的局部最优解和种群最优解。

(5)根据文献［7］中的粒子群算法基本公式更新每个粒子的位置和速度。

(6)重复步骤(3)～步骤(5)，直至达到最大迭代次数。

最后，当基站从上位机得到最优簇首组合及簇成员信息后，广播非均匀分簇结果给每个节点，普通节点加入簇，组建网络的分簇阶段基本完成。

3.2 最短路由树的建立

本文采用Dijkstra 算法建立基站和簇首之间的最短路由树。Dijkstra 算法是解决关于带权有向图的最短路径问题的一种贪心算法，它要逐个地找出从源节点出发到所有其他节点的最短路径，算法的本质特征是能够确定路径顺序，按照加权长度顺序首先找出最短路径，直至最后找出从源节点到所有节点的最短路径［9］。

为了均衡簇间多跳传输的能耗，将节点的传输能耗、剩余能量和成簇规模作为路由树边的权值公式影响因子，公式如式(7)所示。

其中，W(i，j)表示图中连接相邻簇首节点i 和节点j的边的权值;Etx(l，d)表示节点j 向节点i 发送l 比特数据所消耗的能量，其大小可根据式(1)计算得到;Re(i)，Re(j)分别表示节点i 和节点j 的剩余能量;Cn(i)和N 分别表示节点i 的簇成员数和网络普通节点总数;ε 和θ 是属于［0，1］的常数;ω 为公式归一化常数。

根据前提假设，网络中簇首一旦选定，其拓扑结构不再改变，因此，在每轮采集周期中，所有簇首节点间的拓扑结构可用一个带权值的有向连通图G=(V，E)表示，其中，V 表示网络中所有的簇首节点(包括基站)的集合;E 表示图中所有边的集合。本文为了便于簇间多跳路径的建立，根据簇首到基站的距离将所有簇首节点分属不同的层次，处于n 层的簇首和基站通信需要n -1 层的簇首节点进行转发，且簇首节点不对来自上一层的簇首数据包进行融合处理，只是转发给自己的下一跳簇首，这样可以形成较好的树型结构［10］。假设源顶点到某个节点v的通信代价为D(v)，表示从源顶点到节点v 所经过的整条链路权值之和。则利用Dijkstra 算法构造最短路由树的步骤如下:

(1)初始化。设网络顶点集合为U，选择基站为源顶点S0，并加入到集合U 中，此时U={S0}，对于所有不在U 中的节点v，有如下公式:

其中，W(s0，v)可根据式(7)计算得到;∞可以用一很大的数值代替，只要比树中任何边的权值大就行。

(2)从V-U 的集合中找到节点u，且其D(u)的值最小，然后将其加入到U 中。接着对所有其他V-U中的节点v，用{D(v)，D(u)+W(u，v)}中的较小的值去更新原有的D(v)值，即:

(3)重复步骤(2)，直至所有簇首节点都在U 中为止，即U=V。

最终建立完成以基站为根的最短路由树。基站则根据最短路由树计算出每个簇首节点的路由表信息并将其广播给所有簇首节点，然后簇首节点可以按照路由表，将数据发送给各自的下一跳节点，最终将数据转发给基站。网络模型如图1 所示。

图1 最短路由树网络模型

3.3 数据传输和路由更新

数据传输主要分为簇内传输和簇间传输2 个阶段。簇内传输时，节点按照时分多址(Time Division Multiple Address，TDMA)的方式将检测数据传输给簇首节点;簇间传输时，簇首节点根据已经建立好的最短路由树将融合好的数据传输给自己的父节点，然后经过转发，最终到达基站［11］。

簇间多跳传输阶段，必须考虑某一条路径中转发节点能耗过快而提早死亡的情况。因此，在每一轮传输结束后，基站重新计算路由树中各边的权值，当某条边的权值高于设定的阈值时，则对最短路由树进行动态更新。参考文献［12］得到本文算法动态路由更新的基本过程如下:

(1)网络中某条边的权值过高导致网络路径被割断，原来的最短路由树被分为了2 棵独立的树，此时需要变更路径。

(2)将原来最短路由树中到源顶点的最短路径没有改变的树中节点构成集合TN1，而被切断的树中的节点构成集合TN2。

(3)将集合TN2 中的节点再按照上一节中Dijkstra 算法的基本思路逐个地加入到集合TN1 中，同时将对应节点从TN2 中删除，直到集合TN2为空。

最后便得到了动态更新后的最短路由树。利用此方法不需要重新计算生成整个网络的最短路由树，不但节省了计算时间，而且还避免了不必要的网络能耗。

4 实验结果及分析

为评估本文算法在低冗余度的无线传感器网络中的可用性和有效性，笔者引入EECS 和EEUC 算法与之比较。仿真环境和具体参数如下:在100 ×100的方形区域均匀部署200 个传感器节点;控制包大小200 bit;数据包大小4 000 bit;节点初始能量总和100 J，簇首数目M=10，基站坐标(50，125);λ=0.5，R0=70 m;ε=0.3，θ=0.5，ω=1 000。PSO 参数设置［7］:种群规模Q=50;学习因子c1=c2=2;惯性因子w=0.8;r1，r2 随机给出;α=0.7，β=0.3;最大迭代次数为100。

将本文算法和EECS、EEUC 算法进行比较后可知，EECS 算法为均衡节点能耗，将节点分成大小不同的簇，但是簇首与基站的通信采用简单的单跳机制，容易过快地消耗簇首能量，而导致整个网络的生存周期变短。EEUC 算法则在非均匀分簇的基础上，簇间采用多跳路由方式传输和转发数据，所以消耗的能量更少，一定程度上延长了网络生命周期。不同于上述2 种算法，本文算法不仅在分簇阶段引入粒子群算法优化选簇过程，而且在数据传输和转发阶段，采用多跳路由并通过建立最短路由树的形式寻求最优路径，以及动态路由更新机制，使得能量消耗比其他算法要慢的多，显著地延长了网络有效生命时间。

EEUS、EECS 和本文算法存活节点数随着网络生命时间的变化情况如图2 所示。

图2 网络节点存活数量比较

可以看出，在相对有效的网络生命时间里(存活节点数大于100)，EECS 和EEUC 算法分别在243 轮和345 轮时开始出现第1 个节点的死亡，而本文算法将第1 个节点的死亡时间推迟到649 轮，这是因为本文算法相比于其他2 种算法有如下优势:

(1)为了均衡网络能耗，在选择簇首时，利用PSO 算法选取最优簇首组合分布信息，而EECS 和EEUC 的簇首数目都是随机的，很容易造成能耗不均的问题。

(2)通过在基站与簇首之间建立最短路由树的形式寻找最优路径以及采用动态更新路由机制，减少了多跳传输的能耗，有效地延长了网络生命周期。

(3)根据低冗余度WSN 的特点，本文算法在WSN 初始能量相同的情况下，采用簇首和普通节点能量差异化分配机制，使得簇首节点的初始能量略高于普通节点的初始能量，这样可以延长固定簇首生命时间，保证网络有效运行。

EEUS、EECS 和本文算法前100 轮采集周期各个协议簇首平均能耗变化如图3 所示。可以看出，EECS 算法的簇首平均能耗处于偏高的位置振荡，原因是EECS 算法中所有簇首采用单跳方式与基站通信，比EEUC 算法和本文算法的簇间多跳传输方式要消耗更多的能量。而EECS 和EEUC 算法簇首平均能耗出现不稳定的振荡现象，则是由于2 种算法在选择簇首时数目是随机的，导致簇首多时，能耗低;反之，能耗高的问题，造成节点能耗不均衡。所以，本文算法所采用的选簇方式和簇间多跳路径选择机制使得簇首平均能耗处于低位稳定的状态，能够较好地均衡节点能耗，延长网络寿命。

图3 网络簇首平均能耗比较

5 结束语

本文针对低冗余度的无线传感器网络，提出一种基于粒子群和最短路由树的非均匀分簇路由算法，该算法具有如下特点:(1)利用PSO 算法优化分簇过程，一次性选择固定数目簇首，不仅满足实际网络简单稳定的要求，还降低了算法复杂度，提高了分簇效率;(2)通过建立最短路由树的方式进行数据的传输和转发以及动态地更新最短路由树，能够很好地均衡网络节点能耗;(3)用来检测参数的普通节点不担任簇首，节点能耗更均衡、寿命更长，保证了检测质量。仿真结果表明，本文算法在应用到节点冗余度低的无线传感器网络中时，能有效降低节点死亡速度，延长网络有效生存时间，为进一步应用到工业生产中的低冗余度无线传感器网络提供理论依据。

［1］沈 波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588-1600.

［2］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences.Hawaii，USA:［s.n.］，2000:3005-3014.

［3］Heinzelman W.An Application-specific Protocol Architecture for Wireless MicroSensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An Energy Efficient Cluster Scheme in Wireless Senor Networks［C］//Proceedings of the 24th IEEE Inter-national Conference on Performance，Computing，and Communications.Phoenix，USA:IEEE Press，2005:535-540.

［5］李成法，陈贵海，吴 杰，等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报，2007，30(1):27-36.

［6］蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报，2012，23(5):1223-1231.

［7］苏 兵，黄冠发.基于粒子群优化的WSN 非均匀分簇路由算法［J］.计算机应用，2011，31(9):2340-2343.

［8］李 鉴，石 馨，刘贺平.煤矿巷道无线传感器网络非均匀分簇数据传送机制［J］.中国地质大学学报，2013，38(1):196-200.

［9］Conmen T H，Leiserson C E，Rivest R L，et al.算法导论［M］.2 版.潘金贵，顾铁成，李成法，等，译.北京:机械工业出版社，2006.

［10］尚凤军，任东海.无线传感器网络中分布式多跳路由算法研究［J］.传感技术学报，2012，25(4):530-534.

［11］张明才，薛安荣，王 伟.基于最小生成树的非均匀分簇路由算法［J］.计算机应用，2012，32(3):787-790.

［12］Narvaez P，Siu K Y，Tzeng H Y.New Dynamic Algorithms for Shortest Path Tree Computation［J］.IEEE/ACM Transactions on Networking，2000，8(9):734-746.