张文柱，孙瑞华，高 鹏，孔维鹏

(西安建筑科技大学 信息与控制工程学院，西安 710055)

E-mail:srh_xauat@163.com

1 引 言

为满足我国城市化建设的发展需求，充分利用城市地下空间资源，需要加快城市地下综合管廊的建设[1].然而城市地下综合管廊管线种类多样，设备繁杂，采用传统人工巡检和维护等方式会存在智能化水平不足、工作效率低下、运营成本偏高等问题，因此建立完善的综合管廊环境监测系统是十分必要的[2].

无线传感器网络WSNs(Wireless Sensor Networks)是由大量部署在监测区域内的、具有无线通信与计算能力的微小、廉价传感器节点，通过自组织方式构成的，能根据环境自主完成指定任务的分布式智能化网络系统.其被广泛应用于战场监视、环境监测、智慧农业和目标追踪等领域[3，4].传感器节点部署区域环境复杂，能量受限，在大规模无线传感器网络中，存在网络能耗不均衡，网络寿命较短等问题[5].因此研究适用管廊环境的节能高效的数据传输策略，均衡网络能耗，延长网络生命周期成为WSNs路由协议研究的关键.

为了均衡网络能耗，缓解“能量热区”问题，许多路由协议被提出.LEACH(Low Energy Adaptive Clustering Hierarchy)协议[6]最早采用分簇算法，节点轮流担任簇首并通过单跳方式与Sink节点通信.但是容易造成簇首节点分布不均、能量较低等问题.Qing等[7]提出DEEC协议，引入剩余能量因子，避免了能量较低节点担任簇首.但是没有考虑节点位置影响，可能会造成簇首节点分布不均匀.黄利晓等[8]提出了LEACH-improved路由协议，对簇首选举阈值进行了改进,保证了节点能量负载的均衡性.Fu等[9]引入模糊逻辑推理的方式，综合节点剩余能量、通信半径、邻居节点的数量和节点的计算能力进行簇首选举，仿真表明该方法可以有效均衡网络能耗.但是以上算法只是通过改善簇首选举方法降低网络能耗，并没有解决“能量热区”问题.

Soro等[10]针对“能量热区”问题，首次提出不均等分簇路由协议UCS，根据簇首期望转发负荷调整成簇规模，解决了不同簇首间的负载均衡问题.Lin等人[11]提出EEREG路由协议，划分网络分区，计算簇首最优竞争半径，在延长网络寿命的同时均衡了全网能量消耗.李双双等[12]引入群体智能优化算法PMBA优化簇首选举，建立多基站传输机制，缓解了“能量热区”问题.然而，上述路由算法大多适用于长宽差距不大的监测环境，针对管廊狭长环境适用性较差.为此，周志鑫等[13]提出LEACH-HC协议，采用选举簇首与固定簇首混合部署策略；余修武等[14]针对深井环境提出UCRP协议，根据距离因子、剩余能量因子和邻居节点个数计算簇首竞争半径，有效降低节点能量开销.

综上所述，学者们提出了大量改进的路由协议，在长宽差距不大的典型应用环境中取得了很好的效果，但是由于应用背景不同，路由算法间的通用性较低，管廊中传感器节点异构性较强，适用管廊等狭长应用背景的路由协议较少.本文针对综合管廊环境特点和应用需求，提出了一种基于梯度的异构无线传感器网络非均匀分簇路由协议GUCRP(Gradient-Based Unequal Clustering Routing Protocol)，将网络进行虚拟梯度分区，计算每一梯度最优簇数，根据节点能量异构性计算簇首竞争半径，形成非均匀分簇；综合剩余能量因子和距离因子选取下一跳路由,最终达到均衡网络能耗，改善“能量热区”问题，延长网络寿命的目的.

2 网络与能耗模型

2.1 网络模型

综合管廊是一种长带状分布的空间，可以将其简化为一个L×M的矩形区域(L≫M).假设传感器网络由N个随机部署的传感器节点组成，模型具体描述如下：1)Sink节点位于管廊外侧，计算能力不受限制，有持续的能量供应.2)节点初始能量不同，周期性传输数据.3)节点位置一旦部署不再改变，可以通过定位算法获悉自身位置.4)节点可以感知自身剩余能量，并对数据进行融合.5)节点无线发射功率可自主调控.

建立基于梯度的路由协议，需对网络进行分区设计，具体步骤如下：

网络部署阶段，所有节点初始梯度值IG设置为0.

1.Sink节点广播一条包含跳数值HC的信息Imessage给其邻居节点，初始HC为0.

2.邻居节点接收Imessage后，更新自身梯度值IG(IG=HC+1),更新后的IG替换Imessage中的HC值并将此消息继续广播给邻居节点.

3.收到新消息的节点继续更新自身梯度值，并重复步骤3继续向下传递，直至网络中所有节点设置完毕.

所有节点不重复接收消息，自身梯度值一旦设置将不再更改.最终整个网络内的传感器节点依据自身梯度值，构建梯度路由模型，如图1所示.

2.2 能耗模型

在无线传感器网络中，传感器节点的能量主要消耗在感知、传输和处理数据过程中，其中数据传输能耗占比最大[15].根据发送端与接收端的距离，无线传感器网络信道模型可以分为两种：自由空间模型和多径衰减模型.本文中能耗模型如图2所示.

节点发送kbit数据消耗的能量为：

(1)

接收kbit数据消耗的能量为：

Erx(k，d)=kEelec(k)

(2)

式中：Eelec表示发送电路或接收电路发送或接收1bit数据的能耗；εfs和εamp表示放大器特性常数；d表示传输距离；d0表示传输距离阈值,计算如下：

(3)

图2 能耗模型Fig.2 Energy consumption model

3 GUCRP路由协议

本文提出的GUCRP路由协议包括网络初始化、簇首选举和数据传输三个阶段.

3.1 网络初始化阶段

网络初始化阶段，监测区域被划分为k个梯度单元，各梯度单元区域的面积集合为S,则S={S1,S2,S3，…，Sk}.为了达到更好的网络性能，从最小化相邻梯度单元数据传输能耗出发，计算最佳梯度单元个数.

假设每一轮梯度i中簇首节点ni所承担的平均数据传输量为Dai，可得到下式：

(4)

其中:Si代表梯度i区域面积；ρ代表节点密度；δ代表数据融合率；a代表每一个传感器节点的数据包大小；ci代表梯度i中簇首数量.

设梯度i单元中，簇首节点发送数据的平均能耗为ECH(i),可得：

ECH(i)=Dai(Eelec+εampdA4)

(5)

其中：dA代表相邻两梯度单元中簇首节点间的平均距离.

假设节点服从均匀分布，相邻两梯度单元之间簇首的平均距离dA可以表示如下：

(6)

结合式(4)、式(5)、式(6)可得梯度i中簇首节点的数据总传输能耗为：

(7)

为了最小化数据传输能耗，ECH应取最小值.对ECH求解关于k的一阶导数，可得：

(8)

令式(8)等于0，可得：

(9)

3.2 簇首选举阶段

3.2.1 簇首竞选

对分布式分簇策略而言，簇首的选择至关重要.簇首节点不仅需要转发簇成员节点采集的信息，还需要承担簇间信息中继任务，相比簇成员节点会消耗更多能量.GUCRP路由协议在簇首选择阶段，综合考虑节点的剩余能量因子和距离因子，使剩余能量最高的节点担任最终簇首.首先采用式(10)计算出节点竞选簇首的概率.

(10)

在分布式路由算法中，获取精确的全网平均剩余能量信息较为困难且会造成信息冗余，耗能增加.因此采用估算法统计全网平均剩余能量，如式(11)所示：

(11)

式(11)中：Eini代表全网初始总能量；Eround代表每一轮消耗的能量[7]；r为当前轮次.

计算出簇首竞选概率后，引入阈值函数作为簇首节点竞选的门限值，如式(12)所示.

(12)

式(12)中：pi为节点ni竞选簇首的概率；r为当前轮数；G是1/pi轮中未被选举为簇首节点的集合.

初始阶段节点ni在(0,1)区间产生一个随机数与阈值函数门限值比较，决定是否当选候选簇首节点；入选为候选簇首节点后通过簇首竞争半径建立邻居表信息，根据剩余能量因子确定最终簇首节点.簇首节点竞选成功后广播FinalHead_msg,其余节点接收到消息后回复QuitHead_msg,选举结束.

3.2.2 簇首竞争半径

为了缓解“能量热区”问题，GUCRP协议从均衡网络能耗角度出发，提出了不均等分簇路由协议，采用基于梯度的路由对网络进行均等划分，使靠近Sink节点的区域形成更多的分簇分散大量的数据转发任务.

为了均衡相邻梯度单元中簇首数据传输量，令Dai=Da(i+1)，可得：

(13)

同时，梯度1单元中簇首数量可以由式(14)得出：

c1=kfρS1

(14)

kf为梯度1中簇首所占百分比.

通过式(13)、式(14)计算出各梯度中簇首的最佳数量后，引入簇首竞争半径求解最终簇首竞争半径.

假设网络中传感器节点均为同构，则在同一梯度中形成的若干分簇大小规模均相等.设Ri为梯度i中簇首的竞争半径，可得：

(15)

结合式(13)和式(15)可得出Ri和Ri+1之间的关系，如下所示：

(16)

而在本文提出的异构网络中，传感器节点分为普通节点和高级节点.为了均衡网络能耗，在同一梯度中由高级节点担任簇首的簇成簇规模要大于普通节点担任簇首的簇成簇规模，即高级节点的簇首竞争半径大于普通节点的簇首竞争半径.

假设E0代表普通节点的初始能量，μ代表高级节点占总节点数的百分比，α代表高级节点超出普通节点能量的百分比.网络中所有传感器节点的初始总能量可以被表示为：

ET=ρS(1-μ)E0+ρSμ(1+α)E0=ρS(1+αμ)E0

(17)

式(17)表明，在异构网络中实质上可以认为有ρS(1+αμ)个初始能量为E0的普通节点.

在同构网络中，梯度i单元中传感器节点的个数可以表示为ρSi，单个传感器节点的覆盖范围为1/ρ，因此在梯度i单元中簇首的平均覆盖范围可以被表示为：

(18)

由公式(17)可得，在异构网络中，梯度i单元中传感器节点的个数增加了(1+αμ)倍.单个传感器节点的覆盖范围为1/ρ(1+αμ)，梯度i中簇首的平均覆盖范围表示如下：

(19)

因此，梯度i中普通节点担任簇首和高级节点担任簇首所形成的簇首加权平均覆盖范围表示如下：

(20)

根据式(19)、式(20)，可以得出在异构网络中普通节点和高级节点的簇首竞争半径，表示如下：

(21)

3.3 数据传输阶段

GUCRP协议数据传输采用单跳与多跳相结合的方式.根据梯度分区，梯度1单元中节点的下一跳是Sink节点，节点采集到的数据直接发送给Sink节点，其他梯度节点通过多跳方式传输数据.假设节点ni是梯度i(1

步骤 1.ni从相邻靠近Sink节点的i-1梯度单元中随机选择ωci-1个簇首节点作为下一跳候选簇首节点NEXT_Htentative，并建立候选簇首节点集合SCH.其中ω是(0,1)之间的随机数.

步骤 2.ni与集合SCH中的候选簇首节点交换路由信息，获取剩余能量和距离信息，并通过式(22)、式(23)计算候选簇首节点集合SCH中各簇首节点的代价函数Cost(i，j)，如下所示：

(22)

(23)

式中：ej代表候选节点的剩余能量；e0代表节点的初始能量；dis(ni,nj)代表节点i到j的距离；dis(ni,BS)和dis(nj,BS)分别代表节点i和j到Sink节点的距离.

最终节点ni选择代价最小的候选簇首节点作为最终下一跳簇首节点NEXT_Hfinal.

3.4 GUCRP协议整体流程

按照GUCRP协议规定，网络初始化阶段Sink节点向全网播报一条报文消息，其中包含网络的梯度分区值，每一梯度的最佳分簇值，同构网络中簇首节点的竞争半径以及异构网络中高级节点和普通节点担任簇首时的竞争半径.接收到此消息后所有节点进入分簇阶段.簇首具体选举过程如算法1所示.

算法1.

1.start

2.p←rand(0,1)

3.ifp

4.n←TCH，计算簇首竞争半径R

5. 广播CompeteHead_msg(ID,IG,Re)

6.else

7.n进入阶段Sleeping

8.EXIT

9.endif

10.当节点a收到CompeteHead_msg

11.计算n和a之间的距离d(n,a)

12.ifd(n,a)

13.a←Nn_CH

14.end if

15.ifNn_CH=NULLthen

16.n←FinalCH

17. EXIT

18.else

19.Remax(Ren,Rea)，∀a∈Nn_CH←FinalCH

20. EXIT

21.FinalCH广播FinalHead_msg

22.end

簇首选举成功后，非簇首节点根据簇首节点广播信号强度，计算簇首节点与自身之间的距离，最终根据距离因子，选取最近的簇首入簇.进入数据传输阶段，簇首节点依据代价函数选取下一跳路由进行数据传输.在数据传输阶段为了避免信道冲突，簇首节点采用时分多址技术(TDMA)为不同的簇成员节点分配时隙，簇成员节点只在所分配的时隙内传递数据，其余时间处于睡眠状态.GUCRP协议的流程图如图3所示.

图3 GUCRP协议流程图Fig.3 GUCRP protocol flow chart

4 仿真实验及性能分析

4.1 仿真参数设置

实验采用MATLAB R2016a仿真软件进行仿真测试，设置两种方案：从网络寿命、网络能耗、吞吐量三个方面将GUCRP协议与DEEC协议、OCRP协议[16]、LEACH-HC协议进行比较分析，验证GUCRP协议的有效性；改变网络中的节点密度，验证协议的扩展性.

参考符合城市综合管廊的特殊环境，仿真环境设置为1000×10的长方形区域，具体仿真参数设置如表1所示.

GUCRP协议仿真实验时，公式(21)中权重因子γ=0.3和β=0.7.

4.2 仿真结果分析

4.2.1 网络有效性分析

本文以节点的平均剩余能量作为网络能耗的评价标准，网络寿命是衡量算法有效性的重要指标.本文以节点死亡数量随网络运行时间的变化来衡量网络寿命.

表1 仿真参数Table 1 Simulation parameters

一般情况下，节点的平均剩余能量越大说明网络的生命周期越长.图4为4种协议的节点平均剩余能量随网络运行轮数增长的变化情况.可以直观得出，刚开始时GUCRP协议的节点剩余能量较低，但随着网络运行轮数的增长，GUCRP协议的节点平均剩余能量明显大于其他3种协议.这是因为GUCRP协议建立基于梯度的不均等分簇路由协议，在网络初始化阶段需要消耗部分能量传递初始化消息，在后期网络拓扑趋于稳定后能耗减小.由于采用了最优分簇思想，优化簇首选举策略，OCRP和GUCRP协议的能量消耗曲线随时间增长缓慢下降.同时随着轮数的增加，网络中生存节点数量变少，当节点被选为簇首时，所需要转发的数据负担逐渐变小，4种协议的能量消耗率逐渐变低.这表明GUCRP协议可以有效延长网络的生命周期.

图4 节点平均剩余能量随时间变化图Fig.4 Graph of node average remaining energy over time

图5 节点死亡数量随时间变化图Fig.5 Graph of node deaths over time

图6 网络吞吐量Fig.6 Network throughput

图5为4种协议死亡节点数量随网络运行轮数增长变化的情况.FND(First Node Death)代表第一个节点陷入死亡，如图5所示DEEC协议、LEACH-HC协议、OCRP协议、GUCRP协议出现FND时间分别为321轮、376轮、509轮、692轮.这表明GUCRP协议通过对网络进行分区划分最优簇数，根据节点能量异构性[16]进行不均等分簇，优化簇首选举机制，更好的均衡了网络能耗，避免了单个节点因过度耗能而过早死亡的现象.另外，由于“热区”问题的存在，DEEC协议随时间增长死亡节点数量增速加快；同时LEACH-HC协议采用混合分簇策略，在固定簇首的能量耗尽之后，网络中出现节点突发大量死亡现象；而OCRP协议和GUCRP协议节点的死亡速度相对均衡.由于GUCRP协议采用非均匀分簇方法均衡不同簇首间的能量消耗，因此在网络生存时间和稳定性方面优于其他3种协议.

网络吞吐量是指Sink节点在整个网络生命周期内接收到的数据量，可以直观反映网络的整体性能.

图6为在网络生命周期内，Sink节点接收到的数据包变化情况.GUCRP协议的网络吞吐总量分别是其他3种协议的1.58倍、1.34倍和1.07倍.DEEC 协议在生命周期内的吞吐量最小，LEACH-HC协议和OCRP协议的网络吞吐量相差较大，这是因为两者都采用均匀分簇思想，数据传输机制大致相像，但LEACH-HC协议中包含部分固定簇首，能量过早耗尽后即陷入死亡.GUCRP协议在数据传输阶段，通过基于梯度的不均等分簇策略，不均等分簇策略均衡节点能耗，延长了网络生命周期，提升了网络的整体吞吐量.

4.2.2 网络的扩展性分析

为进一步检验算法的性能，保持网络环境和仿真参数不变，改变网络中节点密度，将节点数量取值区间设为[100,300]，从网络平均能量消耗和网络吞吐量方面进行仿真分析.

图7 网络平均能量消耗Fig.7 Network average energy consumption

随着节点数量的增多网络中节点密度逐渐增大.图7为改变网络中节点密度后，GUCRP协议和DEEC、LEACH-HC、OCRP协议的网络平均能耗图.从图中可以看出，GUCRP协议和OCRP协议相较于其他两种协议相对较稳定，在不同节点密度的网络环境中网络能耗呈缓慢增长的趋势.这是由于随着节点密度的增加，网络中传输的数据包变大，所消耗的能量增加，GUCRP和OCRP协议充分考虑节点的剩余能量，对簇首节点进行优化分配，最大限度地保证了网络的连通性和均衡性，使网络能耗最小化.

图8展示了不同节点密度条件下四种协议的网络吞吐量变化情况，从图中可以得出，随着节点密度的增加，DEEC协议网络吞吐量增长速度慢于其他三种协议.这是因为随着节点密度的增加，数据传输过程中产生了数据冲突，造成了更多的能耗，影响了整体吞吐量.与此同时伴随着节点密度的增加，簇首选举过程中的传输延迟逐渐增大，LEACH-HC、OCRP和GUCRP协议的网络吞吐量增长率逐步降低，由于GUCRP事先划分了路由分区，采用最优分簇策略，受此因素影响较小.

图8 网络吞吐量Fig.8 Network throughput

5 结 论

针对管廊监测系统中无线传感器网络节点能量受限，长距离传输引发“能量热区”，导致网络生命周期较短问题，提出了一种基于梯度的异构无线传感器网络非均匀分簇路由协议GUCRP.GUCRP首先对网络进行分区，计算各梯度最优分簇和能量异构节点的竞争半径，靠近Sink节点区域的簇首节点竞争半径较小，以此均衡不同梯度中的能量消耗，改善“能量热区”问题；同一梯度单元中高级节点簇首竞争半径大于普通节点，避免了能量较低节点过早陷入死亡.在数据传输过程综合考虑下一跳节点的剩余能量和节点位置，保证数据传输的通信代价最小，降低网络能耗.仿真结果表明该算法能有效均衡了网络能耗，延长了网络的生存周期.