胡中栋,易 涛,王振东

(江西理工大学信息工程学院,江西 赣州 341000)

随着现代电子技术的发展,无线传感器网络广泛用于各类应用,如康复医疗、战场野外环境检测等[1-2]。由于无线传感器网络常部署于野外恶劣环境,更换节点的电池是不现实的。因此,能耗成为无线传感器网络的研究热点[3-4]。通过提高数据汇聚、传输效率,可以有效地节省能量。如何均衡网络能量消耗,最大限度地延长网络生命周期成为无线传感器网络路由协议的评价标准。研究表明,平面路由协议在工作过程中需要维护大量的路由表信息,不太适合大规模无线传感器网络,在某种程度上,层次路由协议解决了这个问题。

LEACH协议是最具有代表性的一种层次路由协议。目前,许多层次路由协议都是基于LEACH协议的研究和改进,Heinzelman等人在文献[5]中提出一种集中式的簇构造算法LEACH-C以及一种考虑节点能量的算法LEACH-F。文献[6]中提到的DEEC协议中,在簇首选举时考虑到初始能量和剩余能量,没有考虑到节点位置,无法解决簇头节点分布不均匀的状况;而在文献[7]提出路由协议中,在簇首选举时以节点的剩余能量、节点度、节点能量消耗速度等参数构建节点的簇首竞争时间,但是没有考虑到全网能量以及节点位置。在文献[8-9]提出的路由协议中,前者没考虑全网能量后者没有考虑距离因素,且这两种协议一定程度上增加了计算开销;文献[10-11]这两种协议在簇头选举时没有综合考虑节点的能量和位置,也没有解决簇头分布不均的状况;文献[12]提出的算法在簇首的选择阶段综合考虑了距离和能量因素,但是没有解决簇首分布不均匀的缺陷,而文献[13]提出的协议在进行阈值计算时没有考虑节点以及基站的位置,并且在相邻节点剩余能量预测上可能会出现与实际情况相差较大的情况。

LEACH路由协议的簇头选举没有考虑节点能量和位置的影响,而基于LEACH的各种改进的路由协议虽然考虑了节点能量、或综合考虑节点能量和距离因素的影响,但都没有解决簇首分布不均匀以及簇首数量过多或过少的缺陷。因此,本文在LEACH协议的基础上,提出一种基于最优分簇的能量异构无线传感器网络路由协议OCRP(Energy Heterogeneous Wireless Sensor Networks Routing Protocol Based on Optimal Clustering),该算法的主要思想是:首先根据待测区范围的大小和传感器节点的多少,计算出最优分簇的数量。将待测区域按最优簇数分区,每个分区选择一个簇头,这样使簇头的分布较为均匀;同时改进簇头选举机制,在簇头选举阶段,根据节点的位置信息、剩余能量以及整个网络的初始能量和剩余能量选举簇头。

1 EH-LEACH路由协议

文献[14]提到一种称为低功耗自适应分簇路由协议LEACH(Low Energy Adaptive Clustering Hierarchy)。本文提到的EH-LEACH算法EH-LEACH(Energy Heterogeneous Low Energy Adaptive Clustering Hierarchy)中,各节点的能量是不同的。在簇的建立阶段,各节点以循环的方式随机成为簇头节点。在数据通信阶段,簇头将融合后的数据传输给Sink节点。LEACH协议有分层簇型结构、簇头节点动态分配等优点,尤其在处理具有高度相关性的数据时,由于数据融合性较好,大部分冗余数据都能被消除,因此在能耗方面性能较好。LEACH算法中各节点成为簇头的阈值函数为:

(1)

式中:p指的是节点竞选为簇头的平均概率,r是指网络当前运行在第几轮,G则是指节点在已经运行1/p轮后仍然未能担任簇首的节点集合。rmod(1/p)表示未当选过簇头的节点数目。

根据EH-LEACH协议,节点ni产生一个0～1之间的随机数作为概率门限来决定是否成为簇头,由于该数值的随机性,在每一轮的簇头选举过程中都可能会出现过多或过少的簇头,另一种可能出现的问题是簇头分布不均匀。

2 DEEC路由协议

DEEC路由协议[15]是一种以LEACH路由协议为基础改进的多级HWSNs分簇路由协议,该协议中各节点轮流当选为簇头,由于各节点初始能量不同,节点成为簇头的机率也不同,并且该算法考虑到节点的初始和剩余能量,延长了网络的生存周期。假设N个传感器节点均匀部署在M×M区域内,簇头数与传感器节点总数之比为popt,那么节点成为簇头的概率为:

(2)

DEEC路由算法中各个节点si在每一轮成为簇头的阈值函数为:

(3)

由于DEEC路由协议是在LEACH路由协议基础上改进的,因此在每一轮的簇头选举过程中都可能会出现过多或过少的簇头,另一种可能出现的问题是簇头分布不均匀。且DEEC算法没有考虑簇头节点位置的影响,距离基站比较远的簇头将会消耗更多的能量,从而造成全网能量消耗不均衡,此类节点也会过早死亡。

3 OCRP路由协议

3.1 网络模型

假定N个传感器节点随机分布在一个M×M的正方形区域或L×M的长方形区域内,根据计算出的最优分簇数K,将该区域分为K个分区。①传感器网络为静态网络,节点部署后不再移动且节点位置已知。每个节点有一个全局唯一的id标识。②节点有不同的初始能量,其能量是有限且不可再补充。③节点的无线发射功率可控,即节点可以根据接收者的距离来调整其发射功率。④网络节点都是全双工通信,能与基站直接通信。假设能量从节点i传输到节点j消耗的能量等同于从节点j传输到节点i消耗的能量。

在能量异构网络中,节点的能量值是在一个区间随机分布的,我们区分节点为普通节点和高能节点两种。普通节点的初始能量为Einit,高能节点的初始能量为设Einit(1+ai),ai表示高能节点超过普通节点能量的倍数。因此节点的初始能量可以描述为在闭区间[Einit,Einit(1+amax)]内随机分布,因此网络表现为能量异构形式。设任意节点配备的初始能量为Einit(1+ai),则能量异构网络总的初始能量为:

(4)

(5)

OCRP路由协议中,每个节点当选为簇头的加权概率pi如式(6),其中,popt是节点si成为簇头的平均概率,即首轮节点当选簇头的概率:

(6)

3.2 最优分簇

分簇路由协议中,簇首数目对网络性能的影响很大,根据文献[16],最优簇首数目为:

(7)

式中:εfs和εmp分别为自由空间信道模型和多径衰落信道模型的两种能耗模型下的传输功率放大器的能耗参数,N为节点个数,M为区域边长,dtoBS表示节点到基站的距离。

从式(7)可以看出,最优簇首数目kopt与传感器节点的覆盖面积M2以及网络中的节点总数N密切相关。监测区域面积越大,则最优簇首节点的数目越大;全网节点总数越多,最优簇首节点的数目也越大。另外,最优簇首数目kopt还与基站到网络中节点的距离有关。基站与网络中节点的距离越远,最优簇首节点的数目就越小;基站与网络中节点的距离越近,最优簇首节点的数目就越大。当N=100,M=100 m,基站与网络中节点的距离的取值范围为75 m

3.3 簇的建立阶段

3.3.1 分簇

根据节点坐标位置确定所属分区。由于受成本的限制,无线传感器网络节点大多数没有GPS定位装置,仅有少量传感器节点带有GPS定位装置,其位置是已知的。通过测距或非测距定位技术可以确定其余节点的位置。根据节点的坐标可以确定每个节点所属的分区。

3.3.2 簇头的产生

在OCRP路由协议中,节点ni产生一个0～1之间的随机数作为概率门限来决定是否成为簇头,如果这个数小于阈值T(n),则该节点向周围节点广播它是簇头的消息。综合考虑簇头的选举受到节点位置和能量的影响,得到新的T(n)的计算公式如式(8),其中,r是目前循环进行的轮数;G是最近1/(pi(r/mod(1/pi)))轮中还未当选过簇头的节点集合。

(8)

式中:A和B为控制因子,其取值范围为[0,1],且A和B之和为1,Eres为节点的剩余能量,Eini为节点的初始能量,∑Eres为全网的剩余能量,∑Eini为全网的初始能量,davg为各节点与基站间距离的平均值,di为节点j与基站间的距离。

当该簇产生了1个簇头时,停止选簇头。节点当选为簇首后,就立即向全网广播簇首当选消息。根据该簇节点的数目创建TDMA时隙表,同时簇首还需要确立簇内成员节点的CDMA(Code Division Multiple Access)编码方式,并将TDMA时隙和CDMA编码方式一同发送给簇内节点。

OCRP路由协议的簇首选举机制是在DEEC算法的基础上引入节点初始能量、剩余能量,全网初始能量和剩余能量以及节点的位置,文献[6]中提到的簇头选举机制只考虑能量因素,无法减小距离基站较远的节点被选举为簇头的概率,因此无法避免能量空洞现象的出现,OCRP路由协议的簇头选举机制考虑到节点和网络的能量以及节点和基站间的距离,选举出的簇头生命周期更长,网络中各节点能耗也更均衡。

3.4 稳定数据传输阶段

成员节点接收到簇首给其分配的CDMA编码方式和TDMA时隙后,OCRP路由协议就进入到稳定数据传输阶段。节点持续获取环境监测数据,并且在给定的TDMA时隙内完成向簇首节点传输数据的任务。为了降低节点能耗,在传递完监测数据后,成员节点关闭其信号发射器,并且进入睡眠状态。簇首节点需要融合处理接收到的成员节点数据,以便除去数据中的冗余部分,从而降低簇首节点因传输冗余数据而增加的额外能耗。最后,簇首节点将处理后的数据传递至基站。

基站完成全网数据的接收工作后,整个网络进入下一轮的工作周期。为了尽可能的降低网络能耗,在一般情况下,数据稳定传输阶段的持续时间比簇建立阶段要长。

3.5 通信模型

OCRP路由协议采用与LEACH协议相同中的一阶无线电模型[5](First Order Radio Model)来模拟网络能耗,该模型如图1所示。

图1 无线电通信模型

在此模型中,当信号的传输距离d小于某个临界值d0时,则按自由空间信道模型(Free Space Model)来计算传输能耗,传输功率放大器的能耗值与发射距离d的平方成正比;当信号的传输距离d大于临界值d0时,则按多径衰落信道模型(Multi Paths Model)来计算传输能耗,传输功率放大器的能耗值与发射距离d的四次方成正比。其中εfs和εmp分别为上述两种能耗模型下的传输功率放大器的能耗参数。临界值d0计算如下:

(9)

式中:hr表示天线能够接收到信号的最远距离,ht表示天线的高度,L表示传输的损耗,λ表示无线电信号的波长大小。d0也可以通过式(10)来计算。

(10)

当传输距离为d时,节点发送kbit数据的能耗计算如下:

(11)

式中:Eelec表示传感器节点发送或者接收1 bit数据的能量消耗,ET-e(k)为发送电路发送kbit数据的能耗,ET-a(k,d)表示当传输距离为d时,传输功率放大器发送kbit数据的能耗。而接收电路接收kbit数据所消耗的能量计算如下:

ER(k)=ER-e(k)=kEelec

(12)

4 仿真实验

4.1 仿真参数设置

使用MATLAB R2014a仿真软件对EH-LEACH路由协议、DEEC路由协议和OCRP路由协议分别在两个不同场景中进行了仿真实验。仿真环境分别为100 m×100 m的正方形区域、120 m×80 m的长方形区域,每个协议都进行了100遍实验,每遍实验时,重新随机产生100个传感器节点,如图2所示,且各节点的初始能量是异构的。取100遍实验的节点存活数和发送到基站的数据的平均值为实验结果,并绘制对比曲线。在每遍实验中,EH-LEACH路由协议、DEEC路由协议和OCRP路由协议的节点分布完全相同,同一个节点的初始能量都是相同的,即这3个分簇路由协议的运行环境是完全一样。假设基站(或汇聚节点)位于区域的中心位置。为了与其他的协议进行对比,忽略无线信道干扰和信号碰撞等随机因素产生的影响。

图2 100 m×100 m正方形区域节点随机分布图

仿真参数如表1所示。

表1 仿真参数

OCRP路由协议仿真实验时,在公式(8)中,取控制因子A=0.3,B=0.7,由于各节点初始能量是异构的,能量范围在0.5 J～1 J之间。

4.2 仿真结果分析

仿真实验是在异构无线传感器网络下进行的,通过比较EH-LEACH、DEEC和OCRP协议的网络生存周期和网络吞吐量来验证算法的效率。

4.2.1 网络生命周期

整个网络中存活节点数量随网络运行时间的变化反映出网络生命周期的长短,也是反映该算法效率的一项重要指标,通过不同算法存活节点数量随时间变化的图像能够更加直观的比较不同算法中网络生命周期的变化。

图3是100×100场景下的网络生命周期。OCRP协议的第1个节点死亡的时间是EH-LEACH的1.575倍,30%节点死亡的时间是EH-LEACH的1.149倍,50%节点死亡的时间是EH-LEACH的1.081倍。OCRP协议的第1个节点死亡的时间是DEEC的1.369倍,30%节点死亡的时间是DEEC的1.070倍,50%节点死亡的时间是DEEC的1.053倍。这表明,OCRP协议使能量的损耗更加均匀的分布到所有节点中,避免了单个节点因能量损耗过大而过早死亡。在某个时间点,OCRP网络中的节点开始迅速死亡,所以后期的存活节点迅速降低,无线传感器网络中死亡节点的数目占有一定比例时就可以认为网络的死亡,因此,这个不影响OCRP协议在延长无线传感器网络生命周期中的优越表现。

图3 100 m×100 m正方形区域存活节点数量变化

OCRP协议通过划分最优分簇、簇头相对均匀分布和改进簇头的选举机制,减少部分节点因能耗快而过早死亡的现象,使得每轮的能量消耗减少,延长了节点的存活时间和网络的生存周期。

4.2.2 网络吞吐量

网络吞吐量是指网络中各节点与基站通信过程中发送的数据量。

图4是100×100场景下基站收到的数据包和时间的关系。在50%节点死亡之前,OCRP协议能够发送的有效数据包总量是EH-LEACH的1.176倍,是DEEC的1.111倍。这是因为EH-LEACH中距离基站较远的节点因为和基站通信的距离较远,导致它们的负载过大,能量很快耗尽而过早死亡,网络的节点变少,覆盖面积变小。DEEC中没有解决网络的路由开销和电路消耗问题,网络节点总体负载相比OCRP较大,造成其网络生命周期相对较短,这进一步说明了OCRP能够节省网络能量消耗,提高传感器的能量利用率。

图4 100 m×100 m正方形区域网络吞吐量

OCRP协议通过固定分簇的方法使簇头的分布更加均匀,减少了部分节点的通信负载,使得部分节点能耗过快的情况大量减少,这样,节点能发送更多的数据包,传感器节点的能量利用率也会更高。为了研究在不同区域且基站位于不同位置的环境中算法的性能,本文还做了在120 m×80 m的长方形区域中的仿真实验,图5为节点分布图,基站位置为(120,80)。

图5 120 m×80 m长方形区域节点分布图

图6 120 m×80 m长方形区域存活节点数量变化

图6是120 m×80 m场景下的网络生命周期。OCRP协议的第1个节点死亡的时间是EH-LEACH的1.700倍,30%节点死亡的时间是EH-LEACH的1.204倍,50%节点死亡的时间是EH-LEACH的1.037倍。OCRP协议的第1个节点死亡的时间是DEEC的1.664倍,30%节点死亡的时间是DEEC的1.135倍,50%节点死亡的时间是DEEC的1.035倍。

图7是120 m×80 m场景下基站收到的数据包和时间的关系。在50%节点死亡之前,OCRP能够发送的有效数据包总量是EH-LEACH的1.159倍,是DEEC的1.127倍。

图7 120 m×80 m长方形区域网络吞吐量

5 结束语

在能量异构无线传感器网络环境下,通过计算最优簇首数对待测区域进行固定分区,同时考虑到节点位置和节点能量以及全网能量对整个网络的生存周期和网络吞吐量的影响,改进了簇头选举机制。通过理论分析和仿真实验,相比于DEEC和EH-LEACH,OCRP协议在网络生存周期和网络吞吐量上有着较为明显的提升,表明OCRP协议不仅具有良好的性能,解决了EH-LEACH分簇不均匀的弊端,还能充分利用有限的节点能量,从而有效地均衡了无线传感器网络的能量消耗,延长了网络的生存周期。