基于奇偶轮成簇和双簇首的非均匀分簇协议

李安超，陈桂芬

(长春理工大学 电子信息工程学院,长春 130022)(*通信作者电子邮箱chenguif@163.com)

0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由部署在监测区域内的大量微型、低功耗的传感器节点根据路由协议自组织形成的网络[1]。由于传感器节点体积微小，处理能力与携带能量有限，因此研究合理高效的路由协议显得极为重要。合理的路由协议能有效延长网络生命周期，提高网络能量效率。路由协议可以根据拓扑结构分为平面型与分簇型路由协议[2]。相比平面型路由协议，分簇型路由协议[3]可拓展性强，网络性能优异，更适用于大规模网络。

低能量自适应分群分层(Low Energy Adaptive Clustering Hierarchy， LEACH)协议是一种经典分簇型路由协议，该协议在每轮数据采集中，随机选取部分节点担任簇首，通过单跳形式与基站通信。针对其未考虑节点剩余能量的问题，Heinzelman等[4]提出了基于节点能量的改进(Low Energy Adaptive Clustering Hierarchy Enhanced， LEACH-E)协议。Qing等[5]将LEACH协议应用于能量异构无线传感器网络并提出了改进的分布式能量有效成簇协议(Distribute Energy-Efficient Clustering protocol， DEEC)，该协议根据节点的剩余能量动态调整节点当选簇首的概率，性能较LEACH协议更加优异；但DEEC未考虑节点的位置因素且鲁棒性不高的缺点仍然存在。李安超等[6]改进簇首当选公式，综合考虑节点能量与位置，设立双阈值以提高能量利用率；但仍为单跳通信网络，簇首节点负担过重。周冬鑫等[7]将分层多跳的思想引入分簇路由协议中，提出了基于分层多跳的无线传感器网络分簇路由协议(Layer Based Multi-hop Clustering routing protocol for wireless sensor networks, LBMC)，LBMC根据通信代价分层的基础计算每层最佳簇首数量，簇首间采用多跳通信，均衡了网络负载；但仍采用均匀分簇思想，簇首分布不合理。

分簇路由协议中靠近基站的簇首同时执行接收、融合和传输数据任务，网络负担重，很容易因能量耗尽而失效。这一现象被称为“能量热区”问题。为解决这一问题，Soro等[8]经过研究，提出了非均匀分簇的思想。李成法等[9]提出了一种能量有效非均匀分簇(Energy-Efficient Uneven Clustering， EEUC)协议，对解决“能量热区”问题十分有效。EEUC协议通过设立竞争半径，使靠近基站的簇规模变小，均衡簇首能量消耗；但簇首随机选取，很容易使能量较低且远离基站的节点担任簇首；同时在簇间多跳阶段，仅以距离作为中继节点的评价标准，很容易产生局部最优整体较差现象。蒋畅江等[10]提出了一种分布式能量均衡非均匀成簇协议(Distributed Energy-Balanced Unequal Clustering routing protocol， DEBUC)。DEBUC基于时间的簇首竞争机制，广播时间取决于簇首的剩余能量和邻居节点的剩余能量，同时，控制簇首竞争半径，使靠近基站的簇群规模较小，以解决“能量热区问题”，但DEBUC没有限制簇群规模上限，会导致监测区域边缘的簇群规模过大，消耗大量能量。文献[11]提出了一种基于非均匀分簇的无线传感器网络分层路由协议(Hierarchical Routing Protocol for wireless sensor networks based on Non-uniform Clustering， HRPNC)，HRPNC通过分层机制改进簇首竞争公式，将簇群规模限定在一定范围内，避免了簇群规模过大的现象；但HRPNC未能考虑簇首剩余能量和转发次数，存在能量利用率不高的问题。

针对以上协议的缺点，本文提出了一种基于奇偶轮成簇和双簇首的非均匀分簇协议(Uneven Clustering protocol based on Odd-even round clustering and Double cluster head, UCOD)：UCOD设立双簇首和奇偶轮不同的入簇机制，提高网络数据传输效率；对网络节点进行分级，簇首根据能量、位置、转发次数和周围节点数选择多跳中继节点。实验结果表明，与DEBUC和HRPNC相比，UCOD能够有效地优化网络负载，提高系统鲁棒性，延长网络生命周期。

1 相关工作

1.1 异构无线传感器网络

传统分簇路由协议的应用环境为同构无线传感器网络，要求部署的节点所有属性完全一致，协议要求十分严格。在近几年的无线传感器网络研究中，异构无线传感器网络逐渐走进人们的视野。异构无线传感器网络是指由不同类型的传感器节点所组成的网络，可以根据节点的感测、计算、能量和通信能力划分为4种类型：计算能量异构型、节点能量异构型、链路异构型和网络协议异构型[12]。在实际中，由于运输、电池批次、存储等问题，节点配置的初始能量不可能完全相同，因此节点能量异构型传感器网络更易实现且更符合实际。

多级能量异构网络能量模型如下。

在多级能量异构传感器网络中，为每个节点分配一个不同的能量增益倍数ai，假设初始最低能量为Eo，则所有节点的能量被限制在最小值Eo、最大值Eo(1+amax)的范围内，其中amax为所有能量增益倍数ai的最大值。

本文采用文献[13]中的无线通信能量消耗模型。节点发送数据所消耗的能量可分为发送数据能耗ETX(l,d)和接收数据能耗ERX(l)两部分。能耗公式如式(1)：

(1)

其中：d为两节点间的通信距离；当d

ERX(l)=lEelec

(2)

Ec=(M+1)lEDA

(3)

(4)

其中：EDA为单位数据融合的能耗；M为簇内成员的节点数。在数据融合阶段，目前已经有很多性能优异的融合协议[14]，本文中假设采集的数据具有一定的冗余性，簇首节点可以将簇内采集的数据融合成一定长度的数据包并进行转发。

1.2 网络模型

为了避免其他因素产生影响，本文对无线传感器网络中的节点设定以下性质：

1)节点具有唯一的编号(ID)，在监测区域内随机分布，且部署后不再移动；

2)基站位置固定且处理能力与能量无限；

3)节点具有位置感知能力，可根据接收信号的强度RSSI定位各自位置[15]；

4)每个节点具有与基站直接通信的能力；

5)节点通信功率可以根据通信距离进行调节。

2 基于奇偶轮成簇的非均匀分簇机制

针对无线传感器网络存在“能量热区”和系统鲁棒性较差的问题，提出了一种基于奇偶轮成簇和双簇首的非均匀分簇路由协议(UCOD)。该协议实现步骤包括两个部分，簇首选取算法及簇间多跳路由算法。图1为非均匀分簇网络模型示意图。

图1 非均匀分簇网络模型示意图

2.1 簇首选取算法

在簇首选取阶段，根据节点节点的剩余能量、位置分布及竞争半径确定主副簇首节点。算法1给出了节点参与簇首竞争选取阶段的算法伪代码。

算法1 簇首竞争选取算法。

1)μ← RAND(0,1)

2) Ifμ

3)beViceHead← true

4) End if

5) IfbeViceHead=true then

6) Broadcast VICE_HEAD_MSG(ID,Rc,Er)

7) Else

8) Exit

9) End if

10) On receiving a VICE_HEAD_MSG formsi

11) Ifd(si,sj)

12) Addsjtosi .CH

13) End if

14) WhilebeViceHead=true do

15) Ifsj∈si .CH,mj=max(mi .CH) then

16) Broadcast MAIN_HEAD_MSG(ID) and then exit

17) End if

18) On receiving a MAIN_HEAD_MSG formsj

19) Ifsk∈si .CHthen

20) Broadcast QUIT_ELECTION_MSG(ID) and then exit

21) End if

22) End while

下面对算法1进行解释。算法第1)～9)行是副簇首(ViceHead)当选过程。由于副簇首节点主要负责传送数据至基站，所以副簇首距离基站的远近显得格外重要，副簇首当选概率公式如式(5)：

(5)

在选取副簇首时，每个节点产生0到1的随机数，若该随机数小于设定的阈值，则该节点成为副簇首节点。阈值如式(6)：

(6)

pi可以从式(5)确定。从式(5)～(6)中可以看出，节点距离基站越近且剩余能量越大，节点当选副簇首的概率越高。当节点当选副簇首后，广播副簇首信息VICE_HEAD_MSG，簇首信息包括当选节点的ID、竞争半径Rc和当前剩余能量Er。

算法第10)～13)行是副簇首竞选过程。从能量模型的角度分析，当两个副簇首节点距离很近时，会造成簇内节点分布不均，浪费网络能量，因此，本文在副簇首的选取上引入了非均匀的竞争半径。如图2所示。S1、S3可以当选副簇首，而S2不能当选，因为S2位于S1的竞争半径范围内。

当第一个副簇首节点确定，在其淘汰半径内的所有节点均失去竞争簇首的机会。竞争半径公式如式(7)：

Rc=[μ(di-dmin)/(dmax-dmin)+

(7)

其中：Rmax是竞争半径的最大取值；di表示当前副簇首节点距离基站距离，dmin和dmax分别代表节点距离基站最近与最远距离；μ代表一个可变参数，可以根据检测区域的面积及节点能量进行适当调节。在非均匀分簇协议中，靠近基站的簇首不仅需要接收簇内节点数据，还需接收来自簇首间的数据，因此靠近基站的簇首的竞争半径应较小；同时大的竞争半径意味着簇内节点数目较多，需要较大的能量以支撑。

图2 节点竞争示意图

副簇首选定后，普通节点根据最近的副簇首进行入簇。在簇内，进行主簇首的选取过程。见算法第14)～17)行。由于主簇首主要收集簇内节点采集的数据，因此，选择距离所有簇内节点距离最近且能量较高的节点当选主簇首最为合理，同时，主簇首还需将压缩数据传送至副簇首，主副簇首节点间的距离也是影响主簇首当选的因素。综合上述分析，设定的主簇首当选公式如式(8)：

(8)

(9)

图3 UCOD系统模型

从第二轮循环开始，为减少节点频繁参与簇首选取过程，设定奇数轮中全局节点选取簇首，偶数轮中簇首从奇数轮簇内选取，这样，将减少一半节点因入簇选择所消耗的能量。在偶数轮中，副簇首选取的机制可以简化为式(10)：

(10)

其中：dmax′表示该簇内节点距离基站的最远距离；davg′表示该簇内所有节点距离基站的平均值。

主簇首的选择可以利用式(8)选出。簇首选取算法流程如图4所示。

图4 簇首选取算法流程

2.2 簇间多跳路由协议

当主副簇首选定后，将执行数据采集和传输过程；同时副簇首间采用多跳通信方式最终将数据汇聚到基站。传统的多跳路由协议(如EEUC协议)主要考虑两个指标：节点距离中继节点的位置d2(si,sj)和中继节点到基站的位置d2(sj,BS)，并最终使评价指标Erelay=d2(si,sj)+d2(sj,BS)获得最小的待选节点作为中继节点。这样的机制，很容易造成局部评价指标最好而整体评价指标较差的局部最优现象，因此，本文将网络划分为多级同心圆网络，对每一级圆环内节点采用不同的多跳方式，分层考虑中继节点的选择。网络划分如图5所示。

图5 网络划分示意图

假定Δd如式(11)：

(11)

其中c为待定系数，可以根据检测区域的面积进行调整。假设检测区域边长为D，基站位于检测区域外，共划分为K级同心圆网络。为了使K级同心圆网络能完全覆盖检测区域，需满足KΔd≥D，对上述公式进行求解可以得出c系数的公式：

c≥D/(Kd0)

(12)

同时，当Δd≥d0的情况下，会导致内环节点负担过重，不利于网络能量均衡，因此，最终确定的c系数的公式如式(13)：

1≥c≥D/(Kd0)

(13)

网络划分确定后，在Ⅰ级内节点(d(sj,BS)<Δd)直接与基站进行通信；在Ⅱ级以上的节点(d(sj,BS)>Δd)选择多跳通信方式与基站通信。

网络中节点最大转发跳数公式如式(14)：

T=floor(d(sj,BS)/Δd)

(14)

其中floor()函数代表向上取整函数。

在多跳执行阶段，中继节点的选择按照逐级递减的方式进行，如Ⅲ级内节点与基站通信的路线为Ⅲ→Ⅱ→Ⅰ。中继节点的选择可以根据下一跳节点的位置、剩余能量、转发次数和周围节点数决定。评价指标如式(15)所示：

(15)

2.3 算法复杂度分析

假设无线传感器网络中共有N个节点，每轮选取K个主簇首和K个副簇首，下面分析整体算法的复杂度。

首先由K个副簇首节点当选，广播K条VICE_HEAD_MSG消息；然后簇内选取主簇首，同样广播K条MAIN_HEAD_MSG消息；接着竞争失败的簇首广播N-2K条QUIT_ELECTION_MSG消息和N-2K条JOIN_CLUSTER_MSG入簇消息。在偶数轮，由于节点不需要入簇选择，所以算法整体消息开销为：

K+K+0.5×(N-2K)+0.5×(N-2K)=N

(16)

算法整体复杂度为O(N)，说明算法开销较小。

3 仿真分析

在仿真分析环节，硬件环境为Intel Core i5- 3337U处理器，4 GB内存；软件环境为Windows 10 x64；仿真软件为Matlab R2013b。为了验证UCOD的性能，通过与DEBUC和HRPNC进行比较，从簇首生成数量、能量效率和系统稳定性方面进行性能分析。为了保持实验数据的一致性，将三种协议置于多级能量异构无线传感器网络下进行仿真。仿真参数如表1所示。

3.1 簇首特性

UCOD改进了DEBUC所提出的竞争半径公式。从式(7)可以看出，UCOD的竞争半径主要由参量μ和最大竞争半径Rmax所决定。图6为不同μ参数下生成的簇首数对比。

图6为不同μ参数下UCOD簇首生成数对比。从图6中可以看出，随着最大竞争半径的增大，簇首数不断减少。这是因为越大的竞争半径意味着网络需要越少的簇首来覆盖整个监测区域。UCOD中μ参量对簇首数也产生着很大的影响，当μ=0.25、0.75时，整体簇首数少于当μ=0.45时生成的簇首数。这是因为UCOD中竞争半径由两因素构成：位置与能量，当μ取值较小时，竞争半径着重考虑节点剩余能量，剩余能量较大的簇首拥有更大的竞争半径和更多的簇内节点，充足的能量可以保证簇内正常的数据传输；当μ取值较大时，竞争半径着重考虑节点位置，距离基站较近的簇首拥有较小的竞争半径，可以预留能量转发其他簇首传输的数据。μ值偏大或偏小都会导致竞争半径考虑单一因素，不能综合位置与能量进行分析。

表1 仿真参数

图6 簇首生成数与μ、Rmax关系

3.2 能量效率

在能量效率比较环节，将UCOD与DEBUC、HRPNC相比较，以网络生命周期、网络能量消耗、网络数据传输为指标进行分析。

图7为三种协议能量效率对比。无线传感网络中，当节点数量小于10%时，网络不能继续工作，因此，无线传感器网络的有效生命周期应以剩余10%节点为基准。从图7(a)网络生命周期对比中可以看出，UCOD能有效地延长网络生命周期。DEBUC网络生命周期为1 241轮，UCOD网络生命周期为1 594轮，比DEBUC提高了28.4%。这是由于UCOD采用了奇偶轮不同的成簇机制，使全局节点减少入簇选择所消耗的能量；多跳机制中，簇首根据剩余能量、位置、转发次数和周围节点数确定中继节点，数据传输更加高效。

另一方面，HRPNC的网络生命周期为1 401轮，UCOD比HRPNC提高了13.7%。这是因为UCOD引入了双簇首并改进簇首竞争半径公式，提高了能量效率，延长了网络生命周期。

图7(b)为网络传输数据对比。UCOD传输12×104b数据，HRPNC传输10×104b数据，DEBUC传输6×104b数据。UCOD传输数据量分别比HRPNC和DEBUC提高了20%和100%，一方面，UCOD拥有更长的生命周期，意味着可以传输更多的数据；另一方面，UCOD引入主副簇首机制，使簇内数据传输更加高效。

图7(c)为网络能量消耗对比。可以看出，在相同的初始网络能量下，三种协议消耗的网络总能量曲线最终重合，与初始设定相符；但从三种协议能量消耗曲线斜率来看，DEBUC>HRPNC>UCOD，能量消耗曲线斜率代表网络能耗的高低，表明UCOD相比另两种协议能耗更低。UCOD改进了主副簇首选取公式：主簇首选取上着重考虑簇间各节点间距离与剩余能量；副簇首选取上着重考虑剩余能量与到基站的距离，相比DEBUC和HRPNC优化了网络负载，提高了网络能量效率。

图7(d)为节点剩余能量方差对比。由于采用能量异构无线传感器网络，在初始阶段三种协议节点剩余能量方差相同且不为零。随着实验的进行，可以看出，UCOD节点剩余能量方差明显小于DEBUC和HRPNC，这说明UCOD通过构建合理的多跳机制，平均节点剩余能量，均衡网络整体负载。

图7 三种协议能量效率对比

3.3 系统稳定性

在这一环节，分别以丢包率和不同参数δ下网络生命周期为指标研究UCOD的系统稳定性。

在丢包率对比环节，人为毁坏部分簇首节点来模拟网络拓扑结构突变情况。设定单簇首网络中簇首节点损坏时，簇内节点直接将数据传送至基站，UCOD中副簇首节点担任主副簇首任务继续执行工作。

图8为不同簇首损坏率下的丢包率对比。

图8 三种协议的丢包率对比

从图8中可以看出随着簇首损坏率的上升，三种协议的丢包率也随之上升，在簇首损坏率50%的条件下，UCOD丢包率为18.0%，DEBUC为57.1%，HRPNC为45.5%，UCOD丢包率比DEBUC和HRPNC分别减少了39.1和27.5个百分点。这是由于DEBUC和HRPNC簇首损坏后，节点只能被迫选择直接与基站通信，部分节点因大量耗能而死亡，从而使丢包率上升；而UCOD采用双簇首机制，在部分簇首节点损坏后网络仍能以单簇首网络的形式正常工作。

图9为不同参数δ下UCOD的生命周期变化。δ参数直接决定主簇首开始休眠时的能量门限，对网络的整体运作影响很大。由于DEBUC与HRPNC并无参数δ，本次仿真仅作单独实验。

图9 不同参数δ下生命周期对比

从图9中可以看出：当δ取0.3时，UCOD网络生命周期最长；在δ小于0.3时，会导致主簇首节点剩余能量不足以支撑一轮数据采集所消耗的能量而导致死亡；而δ过大会导致主簇首大部分时间处于休眠状态，影响网络能量效率。随着δ的不断增大，生命周期趋于平稳，这是由于此时网络大部分副簇首执行主副簇首功能，类似单簇首网络。

4 结语

针对无线传感器网络设计中“能量热区”和系统鲁棒性较差的问题，本文设计了一种基于奇偶轮入簇和双簇首的非均匀分簇路由协议(UCOD)。该协议引入双簇首和奇偶轮不同的入簇机制，改进簇首竞争半径公式，并基于节点分级实现多跳传输。实验结果表明，UCOD比起DEBUC和HRPNC能有效地提高网络生命周期、数据传输、能量效率和系统稳定性。由于本文对节点空间定位技术只是简单引用，并未考虑空间定位算法对路由协议的影响，下一步工作中将对空间定位技术进行研究，使UCOD在均衡网络负载上更加完善。