结合节点分组和门限优化的改进EEUC机制

黄金国，刘 涛，周先春，严锡君

(1.江苏开放大学 信息与机电工程学院，江苏 南京 210017；2.南京信息工程大学 电子与信息工程学院，江苏 南京 210017；3.河海大学 计算机与信息学院 江苏 南京 210098)

0 引 言

无线传感器网络的一个重要研究课题是研究如何有效管理节点的能量，以尽可能延长网络的生存时间[1-4]。为了提高传感器的能量利用效率，常采用聚类机制，但是该协议没有考虑多跳无线传感器网络中的热区问题。当簇首节点彼此协作以将其数据转发到基站时，更靠近基站的簇首节点负担沉重的中继业务，这些节点会过早消亡[5-9]。为了解决这个问题，文献[10]提出了一种EEUC(energy-efficient unequal clustering)机制，用于无线传感器网络中的周期性数据采集。该机制将无线传感器网络中的节点划分成大小不等的簇，靠近基站的簇的规模大于远离基站的簇的规模。因此，更靠近基站的簇首可以为簇间数据转发保留一些能量。该机制还提出了一种用于簇间通信的多跳路由协议，降低转发路径上的能量消耗。EEUC机制在无线传感器网络中得到广泛应用，许多学者在该机制的基础上研究改进机制，以期进一步提高能量利用效率。如文献[11]对EEUC的簇间多跳路由通信协议进行改进，为各簇首节点选择一个根节点，仅由根节点与基站进行通信，降低其它簇首节点作为中继节点的能耗，一定程度上缓解距离基站近的区域的热区问题。然而，根节点的能耗很大，也带来了新的能耗不均衡问题。文献[12]对EEUC的簇首选举进行改进，在原有簇首选举的基础上，又为每一个簇选出一个副簇首，这样每一个簇的两个簇首分别执行数据传输和数据采、融合任务，降低簇首能耗。但是，EEUC的分簇是不均匀的，有些簇规模很小，这些簇选择双簇首进行数据管理有可能增加能耗。文献[13]对EEUC机制的簇首选举和簇间通信两个部分进行改进，在选举簇首时引入能量、节点邻居数和距离等参量计算门限函数和竞争半径，在选择中继节点时引入候选中继节点己当选转发节点的次数以及簇内成员个数两个参量计算网络能量代价开销，一定程度上均衡了网络能耗。但是，对于EEUC机制划分的规模较大的簇，由于簇内成员过多导致簇首节点能耗过大，能耗分布仍不均衡。本文重点针对EEUC机制划分的规模较大的簇的能耗均衡问题进行深入研究，对大规模簇提出一种节点分组策略，由分组中心节点分担簇内节点的数据采集和融合任务，降低簇首节点能耗，进一步均衡网络能耗，延长网络生存时间。同时，也对EECU机制的簇首节点选举部分的门限函数进行改进，通过引入能量项和距离项，促使候选簇首节点偏向选择离基站更近和剩余能量更多的节点，这样也有助于避免将剩余能量偏低或者担任簇首节点后能耗偏大的节点作为候选簇首节点，从而避免这些节点过早消亡。

1 相关知识

1.1 网络模型

假设传感器网络由N个传感器节点组成，传感器节点均匀地部署在一个区域，以持续监控该区域的环境。传感器节点和底层网络模型满足以下假设：

(1)网络中存在一个远离监测区域的基站，传感器和基站在部署后都是静止的，基站能量是无限的。

(2)所有节点是均匀的，具有相同的能力。每个节点都被分配一个唯一的标识符(ID)。

(3)节点不需要配备GPS功能单元来获取精确的位置信息。

(4)节点可以使用功率控制来调整自身发射功率。

(5)链路具有对称性，也即如果给定发射功率，节点可以基于接收到的信号强度来计算发送节点与其近似距离。

(6)节点可以感知自身的剩余能量。

1.2 EEUC机制

EEUC机制采用非均匀分簇和多跳路由组织无线传感器网络，均衡网络内节点的能耗。EEUC是一种分布式竞争机制，簇首节点通过局部竞争选举，这与LEACH机制不同。节点的竞争半径随着距离基站的距离而减小。这样带来的结果是，靠近基站的分簇的规模较小，这样降低簇内数据传输的能耗，为簇首节点作为中继节点转发其它簇的数据节约能量。EEUC机制的簇内数据传输方式与LEACH机制相同，而簇间数据传输采用多跳路由协议，簇首根据节点的剩余能量及其到基站的距离从其相邻簇首中选择一个最优的中继节点，实现簇首节点到基站的数据传输任务。EEUC机制的最大优势是可以均衡网络能耗，显著改善网络寿命。因此，EEUC机制以及以该机制为基础的改进机制在无线传感器网络领域得到了广泛应用。

EEUC机制使用一种简化的能耗模型，该模型依据发射机和接收机之间的距离d，选择使用自由空间(d2功率损耗)和多径衰减(d4功率损耗)两种信道模型。在距离d上传输l位数据包的能耗可以表示为

(1)

对应的接收能耗可以表示为

ERx(l)=lEelec

(2)

其中，Eelec表示数据收发过程中的电路能耗，εfs和εmp分别表示自由空间和多径衰减两种信道模型的能耗，d0为距离阈值，可以表示为

(3)

传感器节点在数据融合时也会消耗能量，记为EDA。EEUC机制还假设传感器感知的信息是高度相关的，因此簇首节点可以将从其簇成员节点收集的数据融合成单个长度固定的数据包。

2 改进EEUC机制

EEUC采用非均匀分簇思想，距离基站越远的簇，其簇的规模越大，这样尽管可以降低通信能耗，但是簇首节点的数据接收及融合任务重，能耗较高。为了均衡大规模簇的节点能耗，本文采用节点分组的思想，由分组的中心节点分担簇首节点的数据接收和融合任务，从而降低簇首节点的能耗。此外，改进簇首节点选举的门限函数，通过引入能量项和距离项，促使候选簇首节点偏向选择离基站更近和剩余能量更多的节点，避免将剩余能量偏低或者担任簇首节点后能耗偏大的节点作为候选簇首节点而导致这些节点过早消亡。详细描述如下。

2.1 簇首选举

对于每一个候选簇首节点，计算节点的竞选半径，然后构建候选簇首节点的邻居节点表，将候选簇首节点和其邻居节点的剩余能量进行排序，选择剩余能量最大的节点作为最终的簇首节点，同时竞选半径内的所有节点不再参与簇首选举过程。

LEACH协议设计的门限函数为

(4)

在每一轮选举时，各个节点随机产生一个0～1之间的随机数u，如果u

但是，LEACH协议设计的门限函数没有考虑节点的剩余能量。由于簇首节点需要进行大量的数据处理与传输工作，耗费能量很大，因此，剩余能量较小的节点不易作为候选簇首节点。另外，簇首节点担负着簇内节点与基站的通信任务，簇首节点离基站越近，网络传输能耗越小。基于这一思路，本文对门限函数进行改进，引入能量项和距离项，可以表示为

(5)

(6)

得到候选簇首节点之后，需要为每一个候选簇首节点计算竞选半径，本文仍采用EEUC机制的竞选半径计算方法，候选簇首节点n的竞选半径可以表示为

(7)

其中，Rmax表示竞选半径的最大值，dmax和dmin分别表示网络中节点到基站的最大和最小距离，c表示一个范围在0～1之间的参数。在本文中取值为0.5。

这样，每一个候选簇首节点n在其竞选半径内维护一个邻居节点列表，列表中的任一节点i满足以下两个条件：

(1)节点i为候选簇首节点；

(2)节点i与节点n的距离小于各自竞选半径的最大值。

之后，将候选簇首节点和其邻居节点列表中的节点剩余能量进行排序，选择剩余能量最大的节点作为最终的簇首节点，同时竞选半径内的所有节点不再参与簇首选举过程。

2.2 簇建立

在完成簇首节点的选举任务之后，唤醒网络中处于休眠状态的节点(也即非候选簇首节点)。选出的每个簇首节点在网络区域广播邀请成员消息。网络中的非簇首节点选择距离最近且接收信号强度最大的簇首节点，并发送加入簇的消息给该簇首节点，直到网络中的节点都加入簇首节点所在的簇内，完成簇的建立任务。

2.3 簇内节点分组

按照EEUC的建簇思想，建立的簇是不均匀的，越靠近基站的簇的规模越小，越远离基站的簇的规模越大。这样做的目标在于均衡网络能耗，因为距离基站越近的簇首节点作为中继节点的概率越大，需要执行的数据转发任务越多，簇首节点的能耗也就越大。因此可以通过降低这些簇的规模来减少簇内数据接收和融合的能耗。而距离基站越远的簇首节点作为中继节点的概率越小，其主要能耗在于执行簇内的数据接收和融合，因此可以设计较大规模的簇。这样，当簇的规模较大时，簇首节点接收大量簇成员节点数据并进行融合的能耗很大。为了均衡大规模簇的节点能耗，本文在规模较大的簇内进行节点分组。簇内的分组中心节点分担了部分数据接收和融合任务，簇首节点的数据接收和融合任务得以大幅降低，能耗也随之下降，簇内节点能耗更加均衡。而且，簇首节点只对簇内各分组的中心节点采用TDMA策略分配时隙，由于分组中心节点的数量远小于原来的簇成员节点数量，而分组中的数据通信在一跳通信范围内，整体的数据传输能耗也得以降低。

如上所述，本文只对规模较大的簇进行节点分组，因此在执行节点分组之前需要判断簇的规模。由式(7)可知，簇首节点的竞选半径与簇首节点到基站的距离成反比，也即竞选半径越大，说明簇首节点离基站越远。由EEUC的设计规则知，离基站越远的簇的规模越大。这样，竞选半径越大，簇的规模越大。因此，本文依据竞选半径来度量簇的规模。由式(7)可知，竞选半径的范围为1-cRmax,Rmax，本文取黄金分割点处的半径值作为阈值TR，即

TR=1-cRmax+0.618Rmax-1-cRmax=
1-0.382cRmax

(8)

在进行簇内节点分组之前，先判断簇首节点的竞选半径是否大于阈值TR，是则启动节点分组任务，否则不启动节点分组任务。节点分组的伪代码见表1。

表1 节点分组伪代码

其中，Φ表示空集。

2.4 数据传输

数据传输包括两个部分，一是簇内的数据传输，由簇首节点收集各传感器节点采集的数据；二是簇间的数据传输，由簇首节点选择中继簇首节点，通过多跳通信将数据传输给基站。本文的簇间数据传输方式与EEUC机制相同，这里不再赘述。而簇内数据传输与EEUC机制有所差异。本文将簇内数据传输分为两种模式：一种是没有包含节点分组的簇的簇内数据传输模式，一种是包含节点分组的簇的簇内数据传输模式。前一种簇内数据传输模式和EEUC机制相同，而后一种簇内数据传输模式和EEUC机制是有差异的，具体表现在：EEUC机制中每一个簇成员节点在簇首节点分配的时隙内与簇首节点进行通信，将传感器采集的数据转发给簇首节点；而本文机制中每一个分组中心节点在簇首节点分配的时隙内与簇首节点进行通信，将分组内所有传感器采集的数据融合后转发给簇首节点。这样可以均衡大规模簇内节点能耗。

3 仿真实验

本文采用Matlab 2012版本的软件平台进行无线传感器网络仿真实验，参数见表2。

表2 实验参数

下面将本文聚类机制与传统EEUC机制以及文献[13]改进的EEUC机制进行对比分析，从簇首节点能耗、网络剩余能量和网络生命周期3个方面评测3种聚类机制的性能，详细描述如下。

3.1 簇首节点能耗

对于聚类协议而言，无线传感器网络中每一个簇的簇首节点的能耗是最大的。因为这些节点要负责簇内其它节点的数据收集、融合和传输任务，而且部分簇首节点还要作为中继节点负责远离基站的簇首节点的中继通信。因此，降低簇首节点的能耗对于延长网络的生命周期具有重要作用。本小节对簇首节点的能耗进行对比分析，随机抽取十轮的簇首节点总能耗结果，如图1所示。可见，文献[13]改进的EEUC机制的簇首节点总能耗总体上略低于EEUC机制，但在某些轮(如图1中的第3轮、第5轮和第6轮)的簇首节点总能耗略高于EEUC机制。而本文改进的EEUC机制在每一轮的簇首节点总能耗都低于传统EEUC机制和文献[13]改进的EEUC机制。总体上，传统EEUC机制、文献[13]改进的EEUC机制以及本文改进的EEUC机制的簇首节点总能耗的十轮平均值分别为1.3340、1.3150和1.2320，可见，总体上本文改进的EEUC机制的簇首节点总能耗的十轮平均值相对传统EEUC机制、文献[13]改进的EEUC机制分别下降7.6%和6.3%。这主要归功于本文的节点分组策略，将规模较大的簇的簇首节点的能耗分摊到簇内分组的中心节点身上，从而降低了簇首节点的能耗。

图1 簇首节点能耗对比

3.2 网络剩余能量

无线传感器网络的生命周期与网络中节点的剩余能量相关，当网络中所有节点的剩余能量为0时，无线传感器网络达到最长生命周期，也即网络消亡。本小节对网络的剩余能量进行对比分析，实验结果如图2所示。网络初始状态下所有节点的总能量为200 J。节点在数据采集、融合和传输过程中都会耗费能量，网络的剩余能量随着轮数的增加一直在下降。由图2可见，传统EEUC机制在第787轮耗尽网络能量，文献[13]改进的EEUC机制在第862轮耗尽网络能量，而本文改进的EEUC机制在第1033轮耗尽网络能量，这也说明了改进的EEUC机制的能耗更均衡，其原因主要是本文的节点分组策略均衡了簇内节点的能耗。

图2 网络剩余能量对比

3.3 网络生命周期

网络生命周期是评价无线传感器网络路由协议优劣的重要指标，当无线传感器网络中所有节点都消亡之后，网络也随之消亡，网络的生命周期达到最大。因此，可以通过分析网络中节点的消亡情况来分析网络的生命周期。图3展示了3种聚类机制下网络节点数量随测试轮数的变化曲线。初始状态下，网络中无线传感器节点的总数为400。当节点的能量消耗完毕之后，节点随之消亡。由图3可见，传统EEUC机制在第694轮开始出现传感器节点消亡的现象，在第787轮网络中的传感器节点全部消亡；文献[13]改进的EEUC机制在第773轮开始出现传感器节点消亡的现象，在第862轮网络中的传感器节点全部消亡；而本文改进的EEUC机制在第989轮开始出现传感器节点消亡的现象，在第1033轮网络中的传感器节点全部消亡。可见，本文改进的EEUC机制的网络生命周期最长。而且，本文改进的EEUC机制的传感器节点消亡曲线最陡峭，这也说明本文改进EEUC机制的节点能耗更均衡。另外，本文改进的EEUC机制的传感器节点的最早消亡时间要晚于传统EEUC机制和文献[13]改进的EEUC机制，这除了是因为本文通过节点分组降低了簇首节点的能耗之外，还由于本文在簇首选举阶段改进了门限函数，通过引入能量项和距离项，促使候选簇首节点偏向选择离基站更近和剩余能量更多的节点，这样也有助于避免将剩余能量偏低或者担任簇首节点后能耗偏大的节点作为候选簇首节点，从而避免这些节点过早消亡。

图3 网络生命周期对比

4 结束语

管理节点能量是无线传感器网络的重要研究课题之一。EEUC机制的非均匀分簇思想在高效利用传感器节点能量方面取得了有益成果，是学者们研究的主要方向之一。本文针对EEUC机制所存在的大规模簇的能量不均衡问题，提出了两种改进策略。一是在候选簇头选择的门限函数构建时引入能量项和距离项，保证剩余能量越大、距离基站越近、担任簇首节点次数少的节点越有机会成为候选簇首节点；二是对大规模簇进行节点分组，由分组的中心节点分担簇首节点对组内成员节点采集的数据的收集和融合任务，均衡簇内节点能耗。实验结果表明，本文改进的EEUC机制降低了簇首节点能耗，延缓了网络能量消耗，延长了网络生命周期。