基于二分K-means的无线传感器网络分簇方法

张本宏, 江贺训

(合肥工业大学 计算机与信息学院, 安徽 合肥 230601)

无线传感器网络(wireless sensor network,WSN)是由部署在监测区域内大量的微型传感器节点和基站组成的,通过无线通信方式形成的一个多跳的自组织的网络系统[1]。目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息,并发送给汇聚节点[2]。由于WSN的能耗低、抗毁坏性强，可以被广泛应用于环境监测、国防军事、安全监测、家居生活等众多领域。因为无线传感器节点通常是投放到人迹罕至的地方,而无线传感网络节点的计算能力、带宽、能量都十分有限[3]，所以WSN的路由协议设计的重要目标是降低节点能量损耗,延长整个网络的生命周期[4-5]。分簇算法是有效管理网络能耗从而延长网络整体寿命的方法之一。分簇算法通过将整个网络分成几个较小的簇进行管理,在每个簇中选举簇头对簇内节点采集的数据进行接收并融合再传输给基站,降低了网络整体的通信,较好地提高了网络均衡能耗。文献[6]提出了低功耗自适应集簇分层型协议(low-energy adaptive clustering hierarchy,LEACH)算法,该算法是一种基于层次式路由的分簇方法,采用随机选举簇头的策略,网络中的传感器节点都有一定的几率被选为簇头节点。虽然LEACH分簇算法可以在一定程度上降低网络的能耗提高网络生命周期，但是无法保证选举簇头的数量是否合适，同时也不能保证选举出的簇头在网络中均匀分布。文献[7]对LEACH分簇算法的缺陷进行改进，提出了LEACH-CC算法,传感器节点将自己的剩余能量和位置信息发送给基站,由基站根据信息对网络进行分簇以确定合适的簇头数量；文献[8]提出一种能耗均衡的混合通信算法,由基站通过分析节点剩余能量以及簇头之间的距离选举簇头,并且簇内节点分别以一定的概率通过单跳和多跳混合的方式与簇头通信;文献[9]提出一种基于压缩感知理论的WSN六边形格状优化分簇路由算法,定量分析数据传输次数与分簇多少的关系。虽然能够在一定程度上降低网络的能耗但是不能保证簇头的均匀分布以及合理的簇头数量。

这些分簇算法虽然能在一定程度上提高能量的有效性,但是不能保证各个簇的能量消耗均衡。与非簇头节点相比,由于簇首节点既要负责接收并融合簇内采集的数据又要将数据传送给远端的基站,导致簇头节点能量损耗过快容易过早失效,从而导致网络整体效率降低。因此在选举簇头时需要考虑好节点的剩余能量以及簇头的能量均衡负载。文献[10]提出负载均衡感知的无线传感器网络容错分簇算法,利用遗传因子算法设计了一种自适应的基于离散粒子群算法来优化簇头的选举;文献[11]提出DBCL算法,通过控制每个簇中的成员数量达到各个簇之间能量负载均衡的效果,但是算法仍然采用的是随机选举簇头的方式,没有考虑节点的剩余能量;文献[12]提出EACHS分簇算法先通过LEACH分簇算法分簇,然后调整簇头节点的位置,并且控制每个簇内成员节点的数量从而达到能量负载均衡的目的。以上几种算法都不能保证选出合适的簇头节点，并且不能保证簇头节点均匀分布在无线传感网络中,从而导致网络能量消耗更大,影响网络的整体寿命。

簇头节点的数量对网络能耗很大,簇头数量过多，簇内节点数量就会过少,过量的簇头消耗的能量反而更多;簇头数量太少失去了分簇算法的意义。因此,选出均匀分布于无线传感网络中并具有高效能量的最优簇头集合是一个重要问题。二分K-means[13]是基于传统K-means聚类算法提出的改进型算法,它解决了K-means算法对于初始种子选取过于依赖导致的分簇不均问题,并且运行简单快捷。本文基于二分K-means算法提出了一种优化簇头选举的均匀分簇(uniform clustering optimization algorithm,UCOA)算法，其他分簇算法是先以一定概率选举簇头，再通过簇头广播信息成员节点加入的成簇方式,UCOA分簇算法首先基于对网络能耗的理论分析确定WSN的最佳簇头数目,然后利用二分K-means进行网络均匀分簇。在各个分好的簇中利用改进过后的簇头选举算法选出每个簇中唯一的簇头。这样既能保证成簇的均匀也能保证拥有合适的簇头数目。

1 系统模型

1.1 拓扑模型

假设现有一个用于数据采集的无线传感网络,形状近似为一个边长为M的正方形区域，其中均匀且随机地分布着N个传感器节点。传感器节点的位置固定且具有唯一的网络标识,初始能量相同且有限并能随时感知自己的剩余能量,传感器节点的感知半径相同,能根据自己到簇头之间的距离自适应地调整发射频率。基站位置固定并且离传感网络很远。利用聚类算法将整个无线传感网络均匀分成几个簇,在各个簇内以节点的剩余能量和距离基站的远近作为考量选举簇头。簇内节点与相应的簇头采取单跳通信而簇头与基站之间采取多跳单跳混合通信的设计思想。簇头节点采用TDMA的方式为簇内的节点分配数据传输所需要的时间点,不同的簇采用不同的CDMA代码的方式与簇头节点直接通信,以求避免来自其他簇中节点的干扰。

1.2 能量模型

假设每轮进行数据采集时簇内的节点只会发送一个自己所采集到的数据包给所在簇的簇头节点,并且与任何其他簇中的节点都不会进行通信。每个簇中的传感器节点受到自己所在簇内的簇头管理,将自己所收集到的信息发送给簇头,簇头对簇内节点传输过来的数据包进行必要的融合。在每一轮数据采集的期间每个簇头只会发送一个数据包给基站。为了方便计算,参考文献[14]中的能量损耗模型,如图1所示。

图1 能量损耗模型

图1中,Eelec为无线发射线路节点发送或接收一个数据包所需要的能量消耗;k1为无线发射功率放大器在自由空间时的消耗参数;k2为无线发射功率放大器在多路径传输时的消耗参数。假设所有的簇头在进行路由处理和MAC时不考虑数据包的碰撞和空闲监听的能量损耗。从一个传感器节点发送a个数据包到另一个传感器节点,传输距离为d的能量损耗包括发送a个数据的能耗以及传输过程中放大器的能耗,即

ETX(a,d)=ETX-elec(a)+ETX-amp(a,d)=

(1)

节点接收a个数据包的能耗为:

ERX=ERX-elec(a)=aEelec

(2)

2 分簇策略

WSN的分簇算法中,需要合理的簇数量以及兼顾选举簇头时考虑到簇间能耗负载均衡,因为簇头需要处理簇间的大部分事务,能耗是所有节点中最大的，所以选举簇头时需要考虑的一个重要因素就是节点剩余能量。同时簇头需要直接与基站通信,远距离的通信势必导致能耗的增加,因此在选举簇头时应该考虑到节点与基站距离的远近。本文将簇头数目、节点剩余能量、节点距离因子加入到簇头的优化选举中,并设计出一种用于簇头选举的基于二分K-means的簇头选举算法。

2.1 最优簇头数的计算

根据本文的拓扑模型,设无线传感网络中有Y个簇,则有Y个簇头,每个簇中的非簇头节点平均为N/Y-1个。每个簇头消耗的能量组成为接收簇内成员数据所产生的能耗,融合数据产生的能耗,将融合数据发送到基站所产生的能耗以及功率放大器在多路径传输中产生的能耗为:

(3)

簇内每个非簇头节点的能耗为:

(4)

每个簇的能耗为:

(5)

所有簇的总能耗为:

(6)

由于(6)式中的(1-A/a)KEelec与其他项比较数值太小,忽略不计所有簇的总能耗,(6)式可以简化为:

(7)

(8)

2.2 均匀分簇

无线传感网络的分簇方法一般都是先进行簇头的选举,然后通过簇头广播信息成簇。这样导致的问题就是不能保证簇头的均匀分布,加大无线传感器网络的能量损耗。UCOA分簇算法采用二分K-means对无线传感网络先进行均匀分簇,再在分好的簇内进行簇头选举。通常为了快速均匀分簇会采用K-means算法,K-means算法最关键的步骤是进行初始质心的选择,K-means初始时随机指定若干个节点为质心,可能导致质心在网络中分布不均从而导致聚类效果不佳。为了改善K-means聚类算法对于初始质心的选择过于依赖,采用二分K-means算法进行分簇以保证分簇的均匀。在具体的无线传感器网络可以计算出最优簇头数目,通过设定k值为最优簇头数目保证簇头个数的合理。在无线传感网络节点布置好之后,以基站为原点建立二维坐标系,节点将自己的位置信息发送给基站从而得到所有节点的坐标。分簇步骤如下:

(1) 将无线传感网络中的所有节点初始化为一个簇,利用K-means聚类算法将其分成2个簇。

(2) 分别计算簇的误差平方和(sum of squares for error,SSE),计算公式为：

(9)

其中,ci为质心坐标;x为质心ci的簇内节点;dist为空间2个向量的欧几里得距离。

SSE能够很好地衡量聚类性能,SSE值越小,说明节点越接近于它们的质心,聚类效果越好;反之,SSE值越大,说明该簇聚类的效果越不好,有更大的可能性是将几个簇当成了一个簇。因此需要首先对该簇进行划分。

(3) 利用K-means算法将SSE更大的那个簇分成2个簇。

(4) 重复步骤(2)、步骤(3)直到将网络分成k个簇为止。

2.3 簇头选举

考虑到簇头所承担的簇内簇间事务很多,能量消耗巨大。将剩余能量和节点距离基站距离远近加入到簇头选举的考虑中。UCOA分簇算法只进行一次分簇,而簇头的选举每轮都会进行。将节点剩余能量和节点距离基站距离远近加入对簇头选举阈值公式中,选举簇头的时候每个节点会随机产生一个0～1之间的数,然后与阈值T(n)比较,若这个数比阈值小则当选为簇头。阈值公式为:

(10)

(11)

(12)

其中,P为每一个区域里面簇头个数的百分比,在UCOA分簇算法中要求每个簇内只能有一个簇头节点,因此具体到分好的每个簇内P值就是簇内节点个数的倒数;rmod(1/p)为以1/p轮为周期的循环在当前还剩余的轮数;G为剩余轮数中还没有成为过簇头节点的集合;ω(n)为加入了剩余能量因子和距离远近因子的阈值修正函数;Eini(n)为节点的初始能量;Eres(n)为节点当前的剩余能量;Dmax(n)为每个簇内节点中距离基站最远的距离;Dmin(n)为簇内节点中距离基站最近的距离。网络运行之初所有节点的初始能量都相同,此时主要由节点距离基站距离远近控制簇头的选举,距离基站近的节点当选簇头耗能相对更少。随着网络运行轮数的增加,节点耗能不均衡性开始体现,因此此时应该将剩余能量在阈值修正函数中的权重增加以求更好的网络耗能均衡。若某个簇中选出的簇头不止一个,则优先选择剩余能量大的节点当选簇头。

3 数据传输阶段

无线传感网络中簇头节点与基站,簇内成员节点与簇头节点都是通过单跳方式进行数据传输的,长距离的数据传输会造成能量的过早耗尽,UCOA分簇算法中簇头采用单跳与多跳相结合的数据传输方式进行网络通信。文献[15]分析了单跳路由和多跳路由的能量消耗关系,它将无线传感网络简化为一个简单的线性网络,在线性网络中各节点的距离相等,两点之间的距离为s。当一个节点与汇聚节点距离为ns,这个节点发送kbit数据到汇聚节点时,根据(1)式可以算出直接通信Edirect的值，即

Edirect=ETX(a,d=ns)=

aEelec+k1a(ns)2=

a(Eelec+k1n2s2)

(13)

而在多跳路由中,若每个节点把数据先传送给离自己最近的节点最后到达汇聚节点,则离汇聚节点距离为ns的节点传送abit数据到汇聚节点的过程中需要有n次的数据发送和n-1次的数据接收,根据(1)式、(2)式可以得到多跳通信的能量消耗EMTE为:

EMTE=nETX(a,d=s)+(n-1)ERX(a)=

n(aEelec+k1as2)+a(n-1)Eelec=

a(2n-1)Eelec+k1ns2

(14)

当Edirect

a(Eelec+k1n2s2)

(15)

当Edirect=50 nJ/bit,k1=10 pJ/bit时,若设n=2,则由(15)式得s<71,因此当节点距离汇聚节点的传输距离大于71 m时采用多跳传输,当传输距离小于71 m时采用通信直接传输。

4 仿真与分析

4.1 仿真环境与性能指标

为了验证分簇算法效果,采用仿真工具Matlab对LEACH、UCOA分簇算法进行仿真比较。在本实验中布置无线传感网络覆盖区域为直角坐标区域:0≤x≤100,0≤y≤100,区域内随机分布100个传感器节点,基站的坐标为(50,150)。具体的仿真参数见表 1所列。

表1 仿真参数

根据仿真参数可以计算出距离阈值d0=87.5 m,根据上文中的最优簇头公式求得最优簇头数Y=5。实验分别从网络簇头分布、网络节点存活情况、网络节点能量消耗几个方面对比LEACH和UCOA分簇算法的性能。路由协议的性能主要以第1个死亡节点出现的时间为依据,传感器节点开始死亡的时间越晚,死亡出现得越集中,表明协议性能就越好。若节点的剩余能量为0,则表明节点死亡;若整个网络的死亡节点数占到总节点数的80%,则可以视作整个网络死亡。因此本文的仿真评估以第1个节点死亡的轮数和所有节点总数的80%死亡的轮数作为评判标准。

4.2 仿真结果与分析

LEACH与UCOA分簇算法某轮中的簇头分布如图2所示,LEACH分簇算法以随机指定的方式选取簇头节点,不能保证簇头数量合理还可能导致簇头节点分布不均,有的地方簇头密集有的地方簇头稀疏,加剧网络能量的损耗。UCOA分簇算法通过设定最优簇头数的方式首先对整个无线传感器网络进行均匀分簇,再在各个簇中利用优化过的簇头选举算法来选举簇头,既保证了簇头数量的合理，也保证了簇头的均匀分布,从而很好地均衡了簇头以及簇间的能耗均衡。

(a) LEACH分簇算法

(b) UCOA分簇算法图2 LEACH、UCOA分簇算法簇头分布

LEACH分簇算法与UCOA分簇算法运行期间网络存活节点的数目变化情况的仿真结果如图3所示。从图3可以看出,LEACH分簇算法第1个节点死亡出现在820 轮左右。而UCOA分簇算法第1个死亡节点出现在1 260 轮左右。第1个死亡节点的轮数推迟了53%左右。整个网络运行期间UCOA分簇算法出现了几次大面积节点死亡的现象,这是由于UCOA分簇算法网络能耗均匀节点死亡时间段集中,但是也恰恰说明节点的真实工作效率高。而LEACH分簇算法的节点死亡相对比较分散,特别是一些关键性节点的死亡影响整个网络工作的效率导致剩下节点的作用有限。LEACH分簇算法随机选举节点成为簇头,容易导致簇头分布不均,数量不合适。在簇间传输时只使用单跳传输节点耗能不均。UCOA分簇算法先使用二分K-means将整个网络均匀分簇,在选举簇头时加入剩余能量和节点与基站之间距离远近做调节使得节点耗能均衡。当网络死亡节点数超过80%时网络失效,从80%节点死亡到全部节点死亡,UCOA分簇算法只经过了很短的时间。而LEACH分簇算法经过了很漫长的一段时间。这是由于LEACH算法簇头的选举与轮数r和簇头概率p有关,随着网络剩余的节点越来越少,LEACH算法越来越难选出簇头,在很多轮中其实是没有选出簇头的，也就是网络没有进行工作也没有能量的损耗。而UCOA分簇算法在每个簇中产生唯一的簇头，每轮中都会选择一个簇头。因此从80%死亡节点到节点全部死亡,UCOA分簇算法经历的时间非常短。这也说明了UCOA分簇算法耗能更加均衡。为了更直观地说明UCOA分簇算法的性能,根据节点不同阶段的死亡时间绘制节点死亡时间表和节点生存周期柱状图,见表2所列,如图4所示。

图3 存活节点趋势

表2 节点死亡时间对照 轮

图4 网络生命周期柱状图

网络剩余能量对比如图5所示,由图5可知,随着程序的不断运行,在初期2种算法的耗能差不多。但是随着实验轮数的不断增加,两者的网络总能耗都在增加时,UCOA分簇算法的耗能明显比LEACH分簇算法更慢,而随着实验不断进行，这种优势体现得更加明显。相同的实验轮数时，UCOA分簇算法的网络总体剩余能量远远高于LEACH分簇算法。

图5 网络剩余能量对比

5 结 论

合理高效地利用无线传感网络节点有限的能量,从而延长整个网络的生命周期是当前对无线传感器网络研究的热点问题之一。本文在研究了WSN分簇算法的优缺点基础之上,提出了一种基于二分K-means的均匀分簇路由算法。首先基于对网络能量模型分析计算网络最优簇头数目。利用二分K-means对无线传感网络的节点进行均匀分簇。并利用改进的簇头阈值计算公式在簇中选出唯一的簇头。簇头与基站进行数据传输时运用单跳与多跳相结合的方式。仿真实验表明,本文提出的算法均衡了网络的能耗,延长了网络整体生存时间。