簇规模约束与簇头最优化选择的WSN聚类协议

王义勇, 汪 毅

(1.浙江经济职业技术学院 数字信息技术学院，浙江 杭州 310018； 2.华中农业大学 信息学院，湖北 武汉 430070)

0 引 言

在无线传感器网络(wireless sensor network，WSN)[1-3]中，传感器节点通常采用自身携带的电池供电，且电池不易更换或者充电，因此传感器节点的能量是有限的。如果传感器的能量耗尽，则该传感器节点将会失效，导致传感器网络的拓扑结构变化。传感器节点失效越多，传感器网络瘫痪越快。因此，需要研究传感器节能技术，延长无线传感器网络生存时间[4-6]。对于无线传感器网络而言，其能耗主要来源于传感器节点的无线通信模块。为了降低传感器节点的通信能耗，通常采用的技术手段是设计分簇路由协议，将网络中的节点聚类成若干个节点簇，每一个簇选择一个簇头，由簇头节点收集簇中其它节点的信息，与基站进行通信交互，这样簇中其它节点大部分时间可以关闭无线通信模块，从而降低了这些节点的能耗，总体上降低了网络的能耗，延长了网络的生存时间[7-14]。学者们[12]针对这些问题提出了许多有意义的改进聚类协议，如文献[13]提出了一种聚类区域自适应调整的聚类协议，主要改进在于引入了节点的剩余能量参量，选择剩余能量大的节点作为簇头节点，避免簇头节点过早失效。文献[14]类似，也是通过引入能量参量来均衡节点能耗。然而，这类聚类协议仍然采用随机方式建立节点簇，存在节点簇规模差异大的问题，而且选择簇头时没有考虑节点是否可信，容易因为数据转发失败率高而过多消耗能量。针对这些问题，本文在文献[13]所述聚类协议的基础上，提出一种簇规模约束与簇头最优化选择的聚类协议，主要思想是在节点簇建立阶段引入规模约束，通过固定阈值法创建规模基本一致的节点簇。同时在簇头选择时引入节点的信任度参量，并依据最优化理论设计簇头节点选择的目标函数，选择最优的节点作为簇头节点。另外还增加簇头节点回收步骤，对剩余能量和信任度低于设定阈值的簇头节点进行回收，避免节点过早失效，目标是解决现有聚类协议存在的簇头分布不均匀、负载不均衡、网络生存时间短的问题。

1 本文聚类协议

本文为了解决现有聚类协议在无线传感器网络(WSN)应用中存在的簇头分布不均匀、负载不均衡、网络生存时间短的问题，提出一种簇规模约束与簇头最优化选择的聚类协议。本文所述聚类协议主要包括3个阶段，分别是节点簇划分、簇头节点选择和簇头节点回收。由基站监测簇头节点能量和信任度，当簇头节点能量下降到能量阈值之下，或者簇头节点的信任度下降到信任度阈值之下时，回收该簇头节点。在介绍本文协议之前，首先给出无线传感器网络的通用假设条件：

(1)无线传感器网络中存在一个基站，且基站的能量是无限的；

(2)无线传感器网络中传感器节点是固定的且初始能量相同；

(3)无线传感器网络中每个节点都知道其位置信息；

(4)无线传感器网络中每个节点都可以作为簇头或簇成员；

(5)簇成员节点可以直接将数据包转发给簇头节点；

(6)簇头节点可以通过其它簇头节点将数据转发到基站。

1.1 节点簇划分

对于无线传感器网络的节点聚类而言，如果聚类簇过小，会导致簇数量过大，引起网络拥堵，进而增加通信开销。如果聚类簇过大，会导致簇头节点的通信任务过大，从而增加网络的能量消耗。文献[12,13]所述的聚类协议采用随机聚类的方式划分节点簇，容易导致节点簇的规模差异大，引发节点簇之间负载不均衡、能量消耗大的问题。因此，本文在建立簇时对簇的规模进行约束，按照空间分布构建规模近似的节点簇。具体思路是：引入一个固定阈值N，在建立节点簇时，任选一个节点，以半径R画一个圆，如果圆内节点的数量不小于N，则将该圆内的节点作为一个节点簇。否则，增加圆的半径，直至圆内节点的数量不小于N。节点簇构建的伪代码见表1。其中，阈值N、初始半径R0和半径步长△R是事先设置的参数，具体在实验部分讨论。按照表1的节点簇创建流程，依次对网络中的节点进行划分，每一次划分都得到一个节点簇，然后对剩余的节点集合继续进行划分，直到网络中的所有节点都分配到节点簇中。也可以规定节点簇数量，如果划分的节点簇数量与规定的节点簇数量不一致，则重新开始节点簇划分过程，利用初始节点选择的随机性更新节点簇，直至节点簇数量达到规定数量。本文在随机划分节点簇的基础上引入规模约束，对于均衡网络负载很有意义。

表1 节点簇构建伪代码

1.2 簇头节点选择

簇头的选择是一个最优化过程，需要从节点簇的所有节点中选择一个最适合的节点来担任簇头，选择的依据需根据网络的任务而定。考虑到簇头需要担负簇成员节点与基站之间的通信桥梁任务，簇头节点的通信远比簇成员节点频繁。文献[12]采用轮转法选择簇头，节点担任簇头的频率越低，越有机会被选为簇头，这样节点可以轮流担任簇头，维护通信过程中的能量均衡。该方法定义了一个门限函数，为

(1)

在每一轮选择时，各个节点随机产生一个随机数，与门限函数进行比较，如果小于门限函数，则被选为簇头节点。

该聚类协议采用随机方式选择簇头，容易出现簇头分布不均匀的现象，导致节点簇规模差异大，进而导致不同节点簇之间负载不均匀的现象。而且该聚类协议没有考虑节点的剩余能量，可能出现簇头节点剩余能量不足的现象，导致节点存活时间短，进而导致网络拓扑结构变化，引起网络能耗不均衡现象和降低网络的生存时间。

为了解决文献[12]所述聚类协议的不足，文献[12,13]的基础上，引入了能量参量，在选择簇头时除了要考虑节点担任簇头的频率之外，还需要考虑节点的剩余能量，因为簇头所需要消耗的能量远大于簇成员节点。因此文献[13]选择剩余能量最多的节点作为簇头。文献[12,13]中的门限函数进行改进，为

(2)

然而，文献[13]所述聚类协议选择的簇头仍然具有随机性，导致节点簇的规模差异大，引发负载不均匀现象。而且文献[12,13]在选择簇头时都没有考虑节点是否可信。然而，簇头节点需要管理簇成员节点的所有通信活动，因此簇头节点必须是值得信任的节点，这样可以提高数据转发的成功率，降低簇头节点的能耗。基于这一思想，本文在文献[13]所述聚类协议的基础上，引入节点的信任度参量，作为簇头选择的依据，目标是选择最值得信赖的节点作为簇头。另外，本文在上一小节提出了规模约束的节点簇划分方法，可以解决节点簇规模差异大的问题。由于本文在选择簇头时节点簇是已经划分好的，因此不需要像文献[12,13]那样，设计一个门限函数，将每轮选择中小于门限函数的所有节点都作为簇头。本文将簇头的选择看作一个最优化过程，融合前述的簇头选择策略和节点信任度度量，构建一个簇头选择目标函数，在每一个节点簇中，选择一个使得目标函数达到最大值的节点作为簇头节点。下面首先介绍信任度的计算方法，然后给出目标函数的表达方式。

信任度通常是基于节点转发数据包的行为计算的。在无线传感器网络中，节点在接收数据包之后会将数据包转发给其它节点，由于网络中可能存在恶意节点或者失效节点，此类节点在转发数据包时经常会出现丢包现象。丢包现象越频繁，节点的信任度越低。因此可以基于数据包转发频率来计算节点的信任度参量。

对于节点簇中任意节点p，其邻居节点集合记为pii=1,2,…,Np，Np为邻居节点集合中的元素数量，也即节点p的邻居节点数量。在时间段Δt(本文Δt=60 s)内，监听节点p是否转发来自邻居节点pi的数据包。假设，Mp,pi表示的是，在时间段Δt内，该邻居节点pi发送给节点p的数据包的数量，Np,pi是在时间段Δt内节点p成功转发的来自邻居节点pi的数据包数量，于是节点p对邻居节点pi的数据包转发频率可以表示为

(3)

数据包转发频率fp,pi越大，说明邻居节点pi选择节点p为其转发数据的可靠性越强。因此，本文采用数据包转发频率构建节点的信任度参量。对于节点簇而言，节点p的信任度由其对所有邻居节点的数据包转发频率的平均值来表示，为

(4)

信任度vp越大，说明节点p对节点簇中所有邻居节点的数据包转发频率越高，这样该节点作为簇头节点可以更可靠地管理簇成员节点的通信活动。

为了兼顾节点的信任度、剩余能量以及节点作为簇头的比例，本文设计的簇头选择的目标函数为

(5)

簇头节点选择算法的伪代码见表2。

表2 簇头节点选择伪代码

按照表2的簇头节点选择流程，选出每一个簇的簇头节点，由基站进行声明。

1.3 簇头节点回收

由于簇头节点需要管理簇成员节点的所有通信活动，因此簇头节点的能量消耗非常大。簇头节点必须有足够的能量才能有效地执行其所有任务。为了避免簇头节点因能量消耗过大而失效，本文制定簇头节点回收策略，对剩余能量过小的簇头节点进行回收。同时，考虑到数据传输的可靠性，对信任度过小的簇头节点也需要进行回收。簇头节点回收的伪代码见表3。其中，Emin和vmin分别表示能量阈值和信任度阈值。在本文中，这两个阈值取经验值，分别为Emin=0.3Einit、vmin=0.3。

表3 簇头节点回收伪代码

本文通过对簇头节点进行回收，可以避免单个节点过载而提前失效，均衡网络中节点的能量消耗。同时防止恶意节点攻击，提高数据转发成功率，降低节点能耗。

2 仿真实验与分析

为了便于对比，本文参考文献[13]的实验环境设计仿真实验，仿真参数见表4。其中，仿真计算机平台性能为Intel I7 CPU、DDR3 16 G RAM，软件平台为Matlab 2012。

对于文献[12,13]所述聚类协议，簇头数目比例设置为5%，与文献[13]设置一样。对于本文而言，节点簇的划分方式采用规模约束方式，相应的参数有阈值N、初始半径R0和半径步长△R，为了偏于对比，尽可能使得本文构建的节点簇数量与文献[12,13]得到的节点簇数量一致，因此本文设置参数N=18、R0=30、△R=1。按照该组参数划分节点簇，得到的节点簇数量为5，与文献[12,13]得到的节点簇数量相同。

表4 仿真实验相关参数

与文献[13]一样，本文从负载均衡度、节点生存时间和网络能量3个分析进行分析，对比文献[12,13]和本文所述聚类协议的性能差异，详细描述如下。

2.1 负载均衡度分析

图1给出了3种聚类协议得到的节点簇中的节点数量分布，可见，本文构建的5个节点簇的规模基本一致，最大节点数量为22，最小节点数量为19。文献[12]构建的5个节点簇的规模差异最大，最大节点数量为64，最小节点数量为4。文献[13]构建的5个节点簇的最大节点数量为26，最小节点数量为16。因此，本文聚类协议选择的簇头的负载分布最均衡。

图1 负载均衡度对比

2.2 节点生存时间分析

图2展示了3种聚类协议下网络中节点的生成时间对比情况，文献[12]聚类协议在第220 s开始出现节点失效现象，文献[13]聚类协议在第310 s开始出现节点失效现象，本文聚类协议在第340 s开始出现节点失效现象，与文献[12,13]所述聚类协议相比，本文聚类协议的节点失效时间分别推迟了55%和10%，这说明本文聚类协议可以有效延长节点的生存时间。另外，从图中可以看出，文献[12,13]和本文聚类协议的节点全部失效时间分别是580 s、690 s和760 s，很明显本文聚类协议验证了网络的生存时间。究其原因，主要是因为本文聚类协议划分的节点簇的规模基本一致，能耗更均衡。本文聚类协议通过簇头节点回收，避免簇头节点过早失效，进而也延长了网络的生存时间。

图2 节点生存时间对比

2.3 网络能量分析

图3展示了3种聚类协议的网络能耗对比情况。其中，网络中100个节点的初始能量共计150 J。随着时间的增长，网络能耗不断增大，文献[12]聚类协议在580 s时耗尽全部能量，文献[13]聚类协议在690 s时耗尽全部能量，而本文聚类协议在760 s时耗尽网络能量。可见，本文聚类协议的能耗最低，而且，本文聚类协议的能耗曲线相对而言更加平缓，说明本文聚类协议的能耗更均衡，可以更高效利用网络能量，延长网络生存时间。

图3 网络能耗对比

3 结束语

本文对文献[12,13]的聚类协议进行改进，主要改进包括：①在节点簇建立阶段，在随机选择的基础上采用固定阈值法对节点簇规模进行约束，保证建立的簇规模基本一致，均衡簇头节点的负载；②在簇头节点选择阶段，除了考虑节点的剩余能量和节点作为簇头的比例之外，还兼顾节点的信任度，减少数据转发失败造成的能量消耗，同时采用最优化理论，设计簇头节点选择目标函数来代替门限函数，选择最优的簇头；③在簇头节点回收阶段，对剩余能量和信任度低于阈值的簇头节点进行回收，避免簇头节点过早失效，延长网络生存时间。仿真实验结果表明，与文献[12,13]的聚类协议相比，改进的聚类协议的簇头分布更均匀，负载更均衡，网络生存时间更长，而且网络能量消耗也更慢。