WSNs中一种基于阈值修正的多跳分簇路由算法∗

徐会彬(.湖州师范学院信息工程学院,浙江 湖州33000；.浙江省现代农业资源智慧管理与应用研究重点实验室,浙江 湖州33000)

随着无线传感技术的发展,无线传感网络(Wireless Sensor Networks,WSNs)已在军事侦察、智能家居、智慧农业等领域广泛使用[1－2]。WSNs由多个节点组成的无线网络。这些节点能感知环境的一些物理特性,进而获取如压力、温湿度等各类数据。节点将其采集到的数据以多跳方式传输至汇聚节点。

WSNs内节点属于微型传感节点,它们的计算能力、内存和电源功率有限。通常,节点是由电池供电。一旦电池能量消耗殆尽,节点就无法继续工作。由于应用环境复杂多变,难以更换节点电池或者以其他方式补给能量。因此,能量成为制约WSNs长时间运行的瓶颈[3]。

相比于其他操作,传输数据消耗了节点的大部分能量。因此,学者通过优化数据传输策略降低节点的能耗。其中,分簇的策略受到广泛关注。低功耗自适应集簇分层型(Low Energy Adaptive Clustering Hierarchy,LEACH)[4]是最初的分簇路由。LEACH路由将WSN分成若干簇群。每个簇群由一个簇头。簇头收集本簇内感测的数据,再将数据传输至汇聚节点。LEACH路由通过分簇思想,提高数据传输效率,缓解了网络的能耗。

LEACH路由采用随机方式产生簇头,没有考虑节点能量以及距离等信息,存在一些不足。为此,研究人员针对这些不足,提出一些改进策略[5－7]。例如,文献[8]针对簇头的选择阈值进行改进。在阈值函数中引入能量,使剩余能量大的节点更容易成为簇头。但是该路由没有考虑节点离汇聚节点的距离。文献[9]通过距离和剩余能量信息对簇头的选择阈值进行修正,降低能耗。尽管该路由在选举簇头只考虑了距离和能量信息,没有考虑到节点分布情况。同时,该路由也没有优化簇间路由。

由于选择簇头的复杂性,研究人员将一些智能算法引入分簇路由。文献[10]提出的基于改进萤火虫聚类的能效路由(Energy Efficient Routing based on Improved Firefly Clustering,EIFC)。EIFC路由利用聚类算法构建簇,使簇分布更合理。但是节点运行聚类算法也增加了节点的能耗。

为此,本文提出基于阈值修正的多跳分簇路由(Threshold Correction-based Multi-hop Clustering Routing,TCCR)。TCCR路由在分簇过程中综合考虑了节点的能量、离汇聚节点的距离以及节点的分布密度信息,并通过构建适度因子优化簇间路由。

1 系统模型

1.1 网络模型

n个节点分布于区域内Θ。令S＝{s0,s1,…,sn}表示节点集,其中s0表示汇聚节点,其位于区域中心位置；其他节点随机分布于区域内,且n＝｜S｜－1。本文对WSNs内节点进行如下约束[11]:①所有节点是静态的。在区域Θ内部署了节点后,节点不再移动；②所有节点的初始能量相同Einit。所有节点的通信半径相同R。每个节点具有唯一的ID号。令si表示第i个节点的ID号,其中i＝1,2,…,n。③汇聚节点的能量不受限,且具有足够的数据处理能量；④只考虑因节点能量消耗殆尽而导致的节点死亡。

1.2 能量消耗模型

采用图1所示的一阶无线电模型[12]作为节点的能量消耗模型。

图1 一阶无线电模型

节点传输ℓ比特数据,且传输距离为d时所消耗能量为ETx(ℓ,d):

式中:Eelec表示传输一比特数据所消耗的能量；εfs、εmp分别表示自由空间损耗系数、多径衰落损耗系数；d0表示多径衰落与自由空间衰落两种衰落的切换阈值,其定义如式(2)所示:

相应地,若节点接收ℓ比特数据所消耗的能量为ERx(ℓ):

2 TCCR路由

TCCR路由先依据网络区域面积、汇聚节点位置以及节点通信半径估计簇头数。再依据节点剩余能量、相对距离和节点密度信息选择簇头。最后,构建簇间路由。

2.1 簇头数

为了更好地均衡网络能耗,使簇头分布更均匀,利用节点分布情况,估计簇头数k。节点部署后,先计算(n－1)个节点离s0的最大距离dmax和最小距离dmin:

式中:di,o表示节点si离s0的距离。

再将(dmax＋dmin)/R与n值进行比较,如果(dmax＋dmin)/R≤n,则k＝(dmax＋dmin)/2R,否则,k＝,如式(5)所示:

2.2 选择簇头

利用节点的剩余能量,离汇聚节点距离和节点密度三个因子选择簇头。

首先,计算节点的剩余能量因子[13]。令(r)表示节点si在r轮时的能量。节点si的剩余能量因子为:

然后,计算节点的距离因子。采用了随机方式部署节点,导致节点离汇聚节点的距离不尽相同。有些节点离汇聚节点距离较远,有些离汇聚节点距离较短。因此,定义节点的距离因子,评估节点离汇聚节点的较近:

除了能量和距离因子外,节点分布密度对簇头的选择有重要作用。若节点位于密集区域,理当增加成为簇头的概率；反之,在节点位于稀疏区域,应降低节点成为簇头的概率。因此,定义节点密度因子:

式中:Ni表示节点si的一跳邻居节点,其定义如式(10)所示:

依据式(9)可知,节点分布密度越大,密度因子。引用LEACH协议所采用的阈值函数,并对其进行改进,形成簇头选择阈值函数:

式中:Pi表示簇头比例,即Pi＝k/(n－1)；r表示当前执行的轮数；G表示上一轮为非簇头的节点集合；若上一轮已成为簇头,本轮不再参与簇头的竞选；Υi表示由节点的能量因子、距离因子和密度因子构建适度因子,其定义如式(12)所示:

式中:λ1,λ2和λ3为权重系数,且0<λ1,λ2,λ3<1,λ1＋λ2＋λ3＝1。

节点在竞争簇头时,先产生一个随机数。再将所产生的随机数与阈值比较。若随机数小于阈值,节点就宣称自己为本轮的簇头。并向邻居节点广播通告消息Avd_Mes。

2.3 形成簇的流程

利用2.2节产生k个簇头{Ch1,Ch2,…,Chk}。这些簇头就邻居节点广播Avd_Mes。非簇头节点收到Avd_Mes消息后,就选择接收信号最强的簇头加入。具体的流程如图2所示。

图2 簇的形成流程

最初,汇聚节点向全网广播Hello消息,其包含自汇聚节点的位置。接收Hello消息后,节点计算离汇聚节点的距离。然后,进入簇头选择阶段。在新一轮开始,节点先判断本轮是否为簇头。若本轮已是簇头,节点就不参与新一轮的簇头竞争。若不是,就产生随机数,并与阈值进行比较。

若产生的随机数小于阈值,就广播Avd_Mes消息,并接收非簇头节点发送的请求消息Join_Mes。若产生的随机数大于阈值,就等待接收由簇头广播的Avd_Mes消息。当接收了来自多个簇头广播的Avd_Mes消息后,非簇头节点就从中选择信号强度的簇头加入。重复上述过程,直到执行到最大轮数。

2.4 基于距离和能效的簇间路由

若簇头离汇聚节点距离小于R,该簇头就直接将数据传输至汇聚节点。若簇头离汇聚节点距离大于R,簇头就需构建多跳路径通往汇聚节点[14]。为了方便描述,将离汇聚节点距离大于R的簇头从R＝{Ch1,Ch2,…,Chk}中删除,构建新的簇头集R′＝{Ch1,Ch2,…,Chk′},且R′⊆R。

对于R′集中任意一个簇头Chi,若Chi需要向汇聚节点传输数据,它就从它的邻居簇头中选择具有最大适度因子的簇头作为下一跳转发节点:

式中:Q(j)表示簇头Chj的适度因子；dChj,o表示簇头Chj离汇聚节点距离；dCh,o表示簇头离汇聚节点的最大距离；(r)表示在当前r轮时簇头Chj的剩余能量；Einit表示簇头的初始能量；N(Chi)表示簇头Chi的邻居簇头集；α和β为距离因子和能效因子的权重系数。通过α、β系数控制距离、能量效率对适度因子的影响比重,且α＋β＝1。可依据不同的应用环境,设定α和β的值。

依据式(13)可知,离汇聚节点距离越大以及剩余能量越大的簇头,其适度因子越大。为此,簇头Chi就从其邻居簇头选择具有最大适度因子的簇头作为下一跳转发节点。利用适度因子选择下一跳转发节点,缩短数据传输路径,同时避免能量过低的簇头担任下一跳转发节点。

3 性能仿真

3.1 仿真参数

本文在MATLAB 2016b软件上建立仿真平台,分析TCCR路由性能。在100 m×100 m方形区域内随机部署100个传感节点和一个汇聚节点,汇聚节点位于汇聚区域中心,即汇聚节点位置坐标为(50,50),初始分布图如图3所示。

图3 初始节点分布图

仿真参数如表1所示。利用这些参数进行Monte Carlo实验,每次实验进行2000轮,共进行50次,取平均值作为最终的实验数据。

表1 仿真参数

为了更好地分析TCCR路由性能,选择经典的LEACH路由和EIFC路由作为参照,分析死亡节点数,剩余能量,汇聚节点接收的数据量和数据包传输时延性能。

3.2 死亡节点数

首先分析TCCR路由、LEACH和EIFC路由的死亡节点数情况,如图4所示。显然,死亡节点数越多,路由的能耗性能越差。

图4 死亡节点数

从图4可知,相比于EIFC路由和LEACH路由,提出的TCCR路由降低了死亡节点数的增长速度。LEACH路由最早出现死亡节点数,其约在350轮就出现一个死亡节点。相比于LEACH路由,EIFC路由约在580轮时出现一个死亡节点。而TCCR路由的第一个死亡节点出现的轮数最晚,约在630轮,分别比LEACH路由和EIFC路由延迟了约80%和8.6%。

除了延迟第一个死亡节点出现的轮数,TCCR路由也推迟了全部死亡节点数出的轮数。TCCR路由直到约2000轮时100个节点才全部死亡。而LEACH路由在1200轮时100个节点就基本上全部死亡。上述数据表明,提出的TCCR路由通过优化簇头的分布,并选择离剩余能量高,离汇聚节点距离短和节点密度高的节点作为簇头,均衡网络能耗。

3.3 网络剩余能量

本小节分析三个路由协议的网络剩余能量。节点的初始能量为0.5 J,共100个节点,因此网络的初始为50 J,也是网络的拥有的最大能量。图5显示了网络剩余能量随轮数的变化情况。

图5 网络剩余能量

从图5可知,最初,三个路由的网络剩余能量均为50 J。随着轮数的增加,三个路由的网络剩余能量迅速下降,但是它们的下降速度并不相同。其中LEACH路由的网络剩余能量下降速度最快。执行到300轮,LEACH路由的网络剩余能量就下降了50%。而TCCR路由的网络剩余能量是三者之中能量下降最慢的。

在网络能量损耗了90%时,LEACH路由执行的轮数约640；EIFC路由执行的轮数约682；TCCR路由执行的轮数约845。相比于LEACH路由和EIFC路由,TCCR路由有效地延缓了能量损耗速度。

上述数据表明,相比于LEACH路由和EIFC路由,TCCR路由平衡网络能耗。这得益于TCCR路由合理地选择簇头,没有过度浪费能量。

3.4 汇聚节点接收的数据量

汇聚节点接收的数据量反映了路由传输数据包的性能。在限定的轮数内,汇聚节点接收的数据量越大,传输数据包的性能越好,所构建的路由越稳定。

图6给出了在600轮内,LEACH路由、EIFC路由和TCCR路由中汇聚节点接收的数据量情况。从图可知,TCCR路由的汇聚节点接收的数据量最大,优于LEACH路由和EIFC路由,提升了数据传输效率。这主要原因在于:TCCR路由在构建簇间路由时,充分考虑了簇头的剩余能量以及离汇聚节点距离。一方面尽量缩短数据传输路径,另一方面尽量选择剩余能量高的簇头传输数据,避免能量过低的簇头参与路由。

图6 汇聚节点接收的数据量

4 结束语

针对WSNs现有分簇路由算法的不足,提出基于阈值修正的多跳分簇路由TCCR。TCCR路由的核心是对选择簇头的阈值进行修正。即在传统的LEACH簇头选择阈值的基础上,加入节点的剩余能量、离汇聚节点距离和节点密度,对产生簇头阈值进行修正,进而解决簇头分布不合理以及能耗不均衡问题。在簇间通信阶段,利用距离和能量构建适度因子选择下一跳转发节点。

仿真结果表明,提出的TCCR路由具有较好的稳定性,均衡了节点间能耗,降低了节点的能耗速度,延长了网络寿命,也提升了数据传输效率。本文只考虑了同构网络,并没有考虑到节点间的差异性。后期,将研究异构网络的分簇路由,这是后期的研究工作。