基于节点度-限制的数据融合树构建算法*

宋三华

(黄淮学院信息工程学院,河南 驻马店 463000)

无线传感网络WSNs(Wireless Sensor Networks)由大量的微型传感节点组成[1-2],这些传感节点具有感测、通信能力,进而实现对环境的监测目的。目前,WSNs已广泛应用于军事勘测、环境管理以及健康医疗等领域[3-4]。

由于WSNs中节点能量受到限制,如何降低网络能耗成为WSNs的首要目标。依据文献[5]研究表明,传输数据所消耗的能量占居节点能耗的大部分。因此,如何优化路由,减少数据传输量,进而降低能耗成为WSNs的研究热点[6-8]。

数据融合是减少传输数据量的有效技术之一。因此,将数据融合与路由协议相结合可有效地减少数据传输量。现存的路由协议可分为基于数据DC(Data-Centric)和基于地址AC(Address-Centric)的两类协议[9]。

而基于数据融合树的路由是DC路由典型代表。文献[10]引用了基于贪婪递增融合树GITD(Greedy Incremental Tree Data),通过融合树优化路由。研究结果表明,基于DC路由的能耗低于基于AC路由。文献[11]引用根树概念建立树骨干网,利用簇头轮换机制降低能耗。此外,文献[12]提出了基于能耗的融合树构建算法。该算法从网络能耗决策路由。然而,这些算法多数是从能量角度构建融合树,并没有考虑了融合时延。

为此,本文提出基于节点度-限制的数据融合树构建DC-DATC(Degree-Constrained-based Data Aggregation Tree Constructing)算法。DC-DATC算法从节点度角度构建融合树,降低高节点度对数据融合时延的影响,同时优化融合树,减少了网络能耗。实验结果表明,提出的DC-DATC算法有效降低网络能耗和融合时延。

1 网络模型

建立图论G=(V,E)的无线传感网络,其中V为传感节点集,E为边集。同时假定传感节点的传输距离为R。如果两个节点i、j间的欧式距离‖i-j‖小于R,则它们间存在一条边(i,j)∈E。

在DC的无线传感网络,将每个节点的整个寿命划分为多个工作时期WP(Working Periods),且每个工作时期WP包含T个时隙。每个节点i随机在从T个时隙中选择一个时隙用于传输数据包或接收数据包。假定节点i所选择的时隙表示为A(i),且这个时隙称为节点i的活动时隙(Active time slot),而其他T-1个时隙为休眠时隙,如图1所示。图中描绘了3个工作时期WP,且每个WP内含5个时隙,即T=5,而节点i选择的时隙为2。

图1 基于DC的WSNs的工作时隙

假定每个节点仅有一个数据包要传,且每个节点在它的活动时隙只能接收数据包,但是,它能够在任何时隙发送数据。此外,假定节点能够融合它的子节点的数据[13],并通过数据融合树向它的父节点传输。所谓数据融合就是指将两个或多个数据转换成一个数据包。

此外,一个信宿节点s∈V能够接收其他所有节点的数据,直到网络内所有数据传输至信宿后,数据融合过程才结束。

2 问题描述

在给定图论G=(V,E)中和一个信宿s∈V。假定Sk表示在工作时期WPk内传输数据的节点集,并且保证Sk内的数据发送节点不发生冲突。因此,一个数据融合分配就可形式化表述为:

(1)

式中:L表示数据融合时延。

DC-DATC算法就是在一定的约束条件下,最小化融合时延,分别如式(2)～式(4)所示:

MinimineL

(2)

(3)

Si∩Sj=φ, ∀i≠j

(4)

将DC-DATC算法对节点u的安排表示为[tsch(u),p(u)],这表示节点u被安排工作时期tsch(u)内的A(p(u))时隙向它的父节点p(u)传输数据。

3 DC-DATC算法

DC-DATC算法目的在于节点度-限制的融合树DCT(Degree-Constrained Aggregation Tree),进而消除高节点度对数据融合时延的影响。给定预设的节点度阈值α,数据融合树中的每个节点的子节点数不大于α。这个参数α由环境决定[14]。然而,在节点密度不是足够高的环境下,并非所有节点均能满足节点度限制条件。为此,DC-DATC算法就试着减少融合树中节点度高于α的节点数。

3.1 节点度对融合时延的影响分析

首先给出融合时延定义。本文将信宿接收网络内所有节点数据所需的工作时期WP数定义为融合时延。

为了减少融合时延,融合树应最大化在同一个时期内工作的节点数。而融合树内高节点度的节点数越多,融合时延也就越大。原因在于:高节点度的节点越多,在同一时期内传输数据的节点数也就越少,这就增加了工作时期数,最终增加了融合时延。

3.2 基于节点度构建融合树的具体过程

此外,DC-DATC算法主要由两个阶段构成:初始阶段和主要阶段。在初始阶段,先构成初始的数据融合树,然后,在主要阶段进一步完善树的构建。在阐述DC-DATC算法前,先引用以下变量:

①nn(u):节点u的邻居节点数;

②ChS(u):在DCT树中节点u的子节点集;

③nch(u):在DCT树中节点u的子节点数;

④napc(u):节点u的可选父节点APC(Available Parent Candidates)数。若节点υ是节点u的一个邻居节点,如果υ满足以下两个条件,则υ称为u的APC。两个条件:ⓐ在DCT树中,υ没有被选成为u的子节点;ⓑnch(υ)<α;

⑤NAS(u):节点u的可选活动者集。NAS(u)是指被加到DCT树后,能构建DCT的节点u的子节点。

⑥state(u):节点u的状态。DC-DATC算法规定节点u有4种状态:等待(WAIT)、活动(ACTIVATED)、监听(LISTEN)和完成(COMPLETE)

此外,依据napc值,将网络内所有节点划分两类:①特殊节点,如果napc(u)=1,则节点u称为特殊节点;②普通节点,如果napc(u)>1,则节点u称为普通节点。

3.3 初始阶段

初始阶段的过程如算法1所示。最初,所有节点处于WAIT状态。特殊节点υ(napc(υ)=1)先向它的邻居节点发送JOIN_REQ消息,请求加入DCT。JOIN_REQ消息包含了节点的ID号。一旦接收到JOIN_REQ消息,它的唯一邻居节点u就是更新局部变量,并广播JOIN_ACCEPT消息,如算法1的第Step 3至第Step 6所示。

图2 DC-DATC算法的初始阶段

图3 算法1的执行主流程

一旦接收到JOIN_ACCEPT消息,节点υ就加入DCT,并将它的状态修改成COMPLETE,如第Step 7至第Step 9所示。同时,如果nch(u)≥α,节点u的其他邻居节点就它们的APC数减一。因为节点u不再是这些节点的APC。应当注意:在更新napc后(第Step 4或第Step 10),普通节点就成为新的特殊节点,然后再重复上述过程。算法1执行过程如图3所示。

3.4 主要阶段

主要阶段的伪代码如算法2所示。如果信宿s的所有邻居节点已经被选为了信宿s的子节点,即DCT已经构成完毕,此时DC-DATC算法就停止,如第2行所示。否则的话,信宿s就成为第1个活动节点,然后就开始寻找它的子节点。当state(s)≠COMPLETE,DC-DATC算法工作如2所示。

图4 DC-DATC算法的主要阶段

活动节点u就向它的邻居节点发送FIND_CHILD消息,寻找子节点。一旦从WAIT状态的邻居节点接收到JOIN_REQ消息,活动节点u就为将它的特殊邻居节点的退避时间设为零,如第Step 13所示。对于普通邻居,它的退避时间t(u,υ):

t(u,υ)=d(u)+sl(υ,u)+rand(0,1)+[nch(υ)×T]

(5)

式中:sl(υ,u)的定义如式(6)所示:

(6)

在整个退避时间内,如果u接收到来自υ的JOIN_CONFIRM消息,则u就取消退避时间t(u,υ),如Step 18所示。否则的话,一旦t(u,υ)到期,u就执行Procedure1,如算法2的Step 18所示。由于特殊节点的退避时间是零,特殊节点的邻居节点总是被选为u的子节点。而对于u的普通邻居节点υ,一旦t(u,υ)到期,u就选择节点υ作为它的子节点,并将此节点加入NAS(u),因此,节点υ成为新的活动节点,如Procedure1的Step 4所示。

一旦产生了新的子节点后,节点u就更新nch(u),再向它的一跳邻居节点发送JOIN_ACCEPT消息,其包含了它的子节点信息,如Procedure1的Step 1至Step 2所示。

为了满足节点度的限制,节点u就将nch(u)与α进行比较。如果已选择了新的活动节点,并且nch(u)=α,则节点u就停止子节点的选择过程,然后再将自己状态修改为LISTEN,如Procedure1 Step 5至Step 9所示。通过这种方式,保证节点u的度不大于α。然而,如果节点u没有选择任何新的活动节点,它将继续执行子节点的选择过程。

图5 Procedure1的伪代码

图6 Procedure2的伪代码

如果节点u不能找到任何活动节点,它就向它的父节点发送STUCK消息,请求父节点寻找新的活动节点,并将自己的状态修改为COMPLETE,如算法2的Step 23至Step 25所示。一旦接收到来自活动节点u的JOIN_ACCEPT消息,处于WAIT状态节点υ就加入DCT。Procedure2显示节点υ加入DCT的过程。节点υ先向一跳邻居节点发送JOIN_CONFIRM消息,其包含自己的ID和父节点的ID,进而告知邻居节点,它已经选择了父节点。

如果节点υ是特殊节点,由于它与邻居节点没有可选链路时,节点υ就将改变状态,进入COMPLETE,不再参与树构建。否则,如果节点υ是普通节点,它将成为新的活动节点,继续构建DCT。

已接收到NAS集内所有节点发送的STUCK消息后,处于LISTEN状态的节点就知道它的所选择的活动节点不能再找到新的活动节点,如算法2的Step 35所示。因此,它将执行Procedure 3,进而寻找新的活动节点。节点就向它的一跳邻居节点广播FIND。如果没有发现活动节点,它就通过发送STUCK消息寻找新的活动节点。如果信宿s已接收到来自NAS(s)内所有节点的STUCK消息,信宿s就改变状态,进入COMPLETE状态,并停止DCT算法。

图7 Procedure 3的伪代码

构建整个DCT的主要过程如图8所示。首先执行初始阶段,然后由信宿检测是否有节点已成为自己的子节点。若是,结束算法;否则信宿作为活动节点,寻找子节点。产生了新子节点后,就相继执行Procedure 1、Procedure 2和Procedure 3。

图8 构建整个DCT的主要过程

4 性能分析

4.1 仿真参数

利用MATLAB建立仿真平台,并分析基于DC-DATC算法性能。假定N个传感节点分布于100 m×100 m的正方形区域,信宿位于区域边界上。传感节点传输距离R=25 m。

为了更好地比较基于DC-DATC的路由的性能,选择基于GITD的路由[15]和基于AC路由[16]。主要考查算法的数据融合时延和网络能耗。数据融合时延是指在一个工作时期内信宿s接收到所有节点数据的时间。每次实验,独立重复50次,取平均值作为最终的仿真数据。

4.2 数据分析

在本次实验中,假定节点数N从70～120变化,且T=100。平均能量随节点数变化曲线如图9所示。所谓平均能量是指出现第1个失效节点时,网络中剩余节点的平均能量。平均能量越高,说明能耗越不平衡。

图9 平均能量随节点数变化曲线

从图9可知,AC路由的能耗不平衡,原因在于AC路由的中间转发节点过多,这加大了能耗。当中间节点能量已消耗殆尽,而其他节点能量还很高。而GITDC和DC-DATC路由通过有效的数据融合树传输数据,平衡了网络能耗。

接下来,分析网络寿命。网络寿命是指第一传感节点失效时间,实验数据如图10所示。

图10 网络寿命

从图10可知,基于DC-DATC的路由的网络寿命优于CA和GITDC路由。节点数越多,优势越明显。原因在于:基于DC-DATC路由通过DC-DATC树,优化数据传输,减少了中间节点的参与,同时通过DC技术,降低了能耗。

最后,数据包传输时延,实验数据如图8所示。从图11可知,提出的基于DC-DATC的路由的数据包传输时延最低,这进一步说明,通过DC-DATC构建的树能够有效地优化数据传输,使得数据包快速传输到信宿,进而降低了传输时延。

图11 数据包传输时延

5 总结

本文针对无线传感网络的数据传输问题,展开分析,并提出基于节点度-限制的数据融合树构建DC-DATC算法。DC-DATC算法从节点度角度构建融合树,进而优化数据传输路线,减少了数据传输量,一方面平衡了网络能耗,另一方面也中间节点传输的数据量。最终,通过平衡能耗,延长了网络寿命。

[1] Rehman A,Abbasi A Z,Islam N,et al. A Review of Wireless Sensors and Networks Applications in Agriculture[J]. Compute Stand Interfaces,2014,36(2):263-270.

[2] Li Z,Wang N,Franzen A,et al. Practical Deployment of an in-Field Soil Property Wireless Sensor Network[J]. Compute Stand Interfaces,2014,36(2):278-287.

[3] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[4] 门顺治,孙顺远,徐保国. 基于PSO的非均匀分簇双簇头路由算法[J]. 传感技术学报,2014,27(9):1281-1286.

[5] Akyildiz I F,Su W,Cayirci E. A Survey on Sensor Networks[J]. IEEE Commun. Mag,2013,40(8):102-114.

[6] Kang B,Kwon N,Choo H. Developing Route Optimization-Based PMIPv6 Testbed for Reliable Packet Transmission[J]. IEEE Access,2016,4(3):1039-1049.

[7] Incel O D,Ghosh A,Krishnamachari B. Scheduling Algorithms for Tree-Based Data Collection in Wireless Sensor Networks[C]//Theoretical Aspects of Distributed Computing in Sensor Networks. Berlin,Germany,2012:407-445.

[8] Kang B,Choo H. An SDN-Enhanced Load-Balancing Technique in the Cloud System[J]. J Supercomputing,2016,72(1):1-24.

[9] Kang B,Choo H. A Cluster-Based Decentralized Job Dispatching for the Large-Scale Cloud[J]. EURASIP J Wireless Commun Netw,2016,1(2):1-8.

[10] Fafoutis X,Mauro A D,Vithanage M D. Receiver Initiated Medium Access Control Protocols for Wireless Sensor Networks[J]. Comput Netw,2015,76(3):55-74.

[11] Kumar N,Misra S,Obaidat M S. Collaborative Learning Automata-Based Routing for Rescue Operations in Dense Urban Regions Using Vehicular Sensor Networks[J]. IEEE Syst J,2015,9(3):1081-1090.

[12] Kang B,Myoung S,Choo H. Distributed Degree-Based Link Scheduling for Collision Avoidance in Wireless Sensor Networks[J]. IEEE Access,2016,4(6):7452-7468.

[13] Jung S G,Kang B,Yeoum S,et al. Trail-Using Ant Behavior Based Energy-Efficient Routing Protocol in Wireless Sensor Networks[J]. Int J Distrib Sensor Netw,2016,1(7):1-8.

[14] Aldeer M,Howard R,Al-Hilli A. Minimizing Energy Consumption in Transmit-Only Sensor Networks Via Optimal Placement of the Cluster Heads[C]//Proc 8th Wireless of the Students,by the Students,and for the Students Workshop,2016:36-38.

[15] Razaque A,Elleithy K M. Low Duty Cycle,Energy-Efficient and Mobility-Based Boarder Node-MAC Hybrid Protocol for Wireless Sensor Networks[J]. J Signal Process Syst,2015,81(2):265-284.

[16] Han G,Dong Y,Guo H,et al. Cross-Layer Optimized Routing in Wireless Sensor Networks with Duty Cycle and Energy Harvesting[J]. Wireless Commun. Mobile Comput,2015,15(16):1957-1981.

[17] Madden S,Franklin M J,Hellerstein J M,et al. TAG:A Tiny Aggregation Service for Ad-Hoc Sensor Networks[J]. ACM SIGOPS OperSyst Rev,2012,36(2):131-146.