一种用于工业无线传感器网络的数据汇聚机制

无线通信技术因为成本低廉、部署方便而逐渐应用在工业现场。与普通的无线传感器网络相比, 工业无线传感器网络(industrial wireless sensor networks, IWSNs)对数据通信的确定性与可靠性有更高的要求[1-2]。因此,对IWSNs的数据汇聚设计合理的机制,确保数据传输过程中的确定性和可靠性,显得尤为重要。

根据数据汇聚的工作模式,无线传感器网络大致可分为事件驱动型和周期汇报型2类[3-4]。在事件驱动型传感器网络中,节点一般很少产生数据,仅在待监测的事件发生时才产生事件报告;而在周期汇报型传感器网络中,所有节点周期性地向汇聚节点报告采集到的信息。

文献[5]提出了一个基于时分多址(time division multiple access,TDMA)机制的跨层优化数据收集协议LEEMA,建立以汇聚节点为根的路由树,再通过该路由树为节点分配工作时隙;LEEMA采用的是最小跳数路由,该路由虽然建立简单,但是不一定是最小能耗路由,其节能效果不一定最优。文献[6]提出了一种基于TDMA 机制的跨层设计方案,该方案采用了分簇的结构,并通过构建涉及网络层、介质访问控制(media access control,MAC)层和物理层的跨层优化模型来获得高能效的数据汇聚机制;该方案证明了传感网的MAC层上采用TDMA机制具有零冲突、高能效的特点;但该方案是一种集中式的优化方案,即由汇聚节点集中计算每个节点的数据汇聚方案,再把优化数据汇聚方案发送给每个节点。文献[7-8]采用图染色的方式对信道进行了分配,将染色相同的信道安排到同一时隙,但没有考虑到数据的发送规律。文献[9]通过分簇的方式,由簇头负责所有节点的数据汇聚,文献[10]提出了分布式的周期性开关数据汇聚机制,文献[11]在设计数据汇聚机制时考虑了覆盖度要求,但文献[9-11]都将减少传感器节点的能量消耗作为算法的主要设计因素。文献[12]提出了跨层优化算法,首先寻找传输功率与干扰最小的链路,再结合路由与链路速率控制进行数据汇聚。文献[13]针对内网数据聚合功能进行了建模,但主要目标是最大化网络吞吐量。文献[14-15]针对事件驱动型网络,设计了一种查询数据汇聚机制DCQS(dynamic conflict-free query scheduling),但未考虑工业应用中数据发送周期不同的特点。

与事件驱动型网络相比,周期汇报型网络中对节点汇报信息实时性要求往往较低,但每个节点都需要向汇聚节点周期性地发送信息,网络的数据量大,节点的无线信号冲突概率高,节点之间的无线信号相互干扰,MAC层设计复杂。与普通传感器网络不同,IWSNs具有高实时性、高可靠性、网络业务已知的特点。本文针对周期汇报型网络和IWSNs的特点,提出一种适用于周期汇报型工业无线传感器网络的数据汇聚机制(data sinking mechanism based on merging links with the same cycle and link competition,MLSCLC)。MLSCLC融合网络中所有同周期节点链路,并对融合后的链路使用优先级竞争机制分配节点工作时隙,从而确定每个节点的路径及工作/休眠时隙。

1 问题描述

IWSNs是由工作节点、路由节点、汇聚节点和管理节点组成的网络[16]。IWSNs的网络模型如图1所示,其中工作节点周期性地产生数据,路由节点除了周期性地产生数据,还具有路由和信息转发功能。

图1 网络模型

本文对IWSNs数据汇聚机制的研究主要基于如下假设:

(1) 工作节点与路由节点产生的数据需要在一定时间内发送到汇聚节点。

(2) 所有数据的产生均具有周期性。

(3) 节点间任何数据的1次发送,均在1个时隙内发送完毕。

(4) 所有节点对网络的全局信息包括节点位置、数据产生周期均已知。

2 MLSCLC描述

基于同周期链路融合与链路竞争的数据汇聚机制分为2个阶段。第1阶段是同周期链路融合阶段,即每个节点确定自身到汇聚节点的数据发送链路,同周期链路融合;第2阶段是链路竞争阶段,即所有链路根据周期确定发送时隙,在同一时隙需要发送的链路根据优先级安排分配,需要分配的链路根据冲突情况分配链路时隙;节点根据链路确定的时隙,有选择地从休眠状态醒来,发送数据或接受数据。

2.1 同周期链路融合阶段

同周期链路融合阶段是准备工作,在网络中所有节点基于同周期的情况下需要预先融合链路为一条新的链路。考虑2个方面的原因:IWSNs中节点存在相同周期的可能性极大;在后续工作中,链路类型数量是影响链路冲突的主要因素,在准备工作中,融合网络中所有周期相同的节点链路为一条链路。本阶段的任务有2个:① 建立基于跳数的虚拟坐标,确定网络中所有节点的链路;② 融合周期相同的链路。

建立基于跳数的虚拟坐标的经典方法是,通过基站在网络部署初期向全网洪泛跳数包,每个节点转发跳数值最小的跳数包；最终所有节点获得自身距离基站和邻居节点距离基站的最小跳数。节点适当退避一段时间等待可能达到的更小跳数包再转发最小跳数包,能够有效地减少网络洪泛的通信量。建立跳数坐标的过程就是简单路由发现的过程。在跳数坐标建立以后,数据包可以简单地沿着跳数递减的方向前进并最终到达基站,跳数坐标只在拓扑发生变化时需要更新或重建。在全网泛洪阶段,节点接受的最小跳数包来源确定节点的父节点。根据所有节点来源最终指向汇聚节点,可得到节点到汇聚节点的链路。

定义1 竞争节点集CPT(u)。对于网络中一个发送节点u及其接受节点即u的父节点F(u),定义所有可能与链路(u,F(u))产生冲突的其他传输链路的发送节点集合为u的竞争节点集,记为CPT(u),并称节点u与CPT(u)中的节点有竞争关系。

示例网络拓扑图如图2所示,节点c的竞争节点集CPT(c)={a,q,r,s}。

图2 示例网络拓扑图

设网络中Li、Lj2条链路的周期相同,其中

算法1(链路融合算法) 将2条周期相同的链路融合为1条链路,其步骤如下:

(1) 在链路Li、Lj中,an=bm为汇聚节点,记融合后的链路为L。

(2) 计算2个链路Li、Lj的步长,将步长长的链路记为L1,步长短的链路记为L2,并将链路L1的末元素加入融合链路L。

(3) 根据竞争节点集CPT(u),计算链路L2的末元素是否与步骤(2)加入的元素有冲突,若无则将此元素加入融合链路L;将链路L1、L2中加入融合链路L的元素去除,若存在步长为0的链路,则转到步骤(4);否则,转到步骤(2)。

(4) 将步长不为0的链路中的节点全部加入融合链路L。

在图2中,节点a为汇聚节点,若节点q和节点w的周期相同,现需要融合2个节点的链路。记节点q的链路为节点w的链路为融合后的链路为L。根据链路融合算法融合后的链路为:

根据周期不同,将所有链路中周期相同的链路放入同一集合,记为周期链路集。在每个周期链路集合中,按照步长从大到小每次选出2条链路根据算法1融合为1条链路,依此类推融合集合中的所有链路为1条链路。

2.2 链路竞争阶段

定义2 初始并行时隙集合Rij。设网络中有链路Li和链路Lj,集合Sij′中元素表示链路Li这些时隙,链路Li可与链路Lj并行执行,则称集合Rij为链路Li和链路Lj的初始并行时隙集合。

定义3 并行时隙集合Sij。设网络中有链路Li和链路Lj,集合Rij为2条链路的初始并行时隙集合,其中链路Li的步长为m,则称集合Sij={x|x>m}∪Rij为链路Li和链路Lj的并行时隙集合。

定义4 并行时隙集合矩阵A。设网络中融合后的链路数量为n。若n阶矩阵A中任意元素aij=Sij,则称矩阵A是网络的并行时隙集合矩阵。其中aij表示链路i与链路j可以并行执行的时隙集合。

初始并行时隙集合示例如图3所示。图3中,链路Li和链路Lj在链路Li的第2、第3时隙可以并行执行,在链路Li的第1、第4时隙不可以并行执行。因此链路Li和链路Lj的无冲突并行时隙集合为Rij={2,3}。将集合Sij′扩充,与链路Li步长外时隙集合S2={5,6,…}取并集,得到并行时隙集合矩阵A中aij=S2∪Rij={2,3,5,6,…}。

图3 初始并行时隙集合示例

在图2示例网络中,所有节点数据发送的周期见表1所列。

表1 示例网络节点周期表

融合后的链路有以下3条。

(1) 周期为4的链路为:

(2) 周期为5的链路为:

(3) 周期为6的链路为:

示例网络对应的并行时隙集合矩阵A为:

定义5 单位集合u1。设并行时隙集合S1={n1,n2,n3,…},将集合S1中所有元素按照数轴的方向向左平移1个单位后得到集合S2,向右平移1个单位后得到集合S3,称u1=S1-S2=S3-S1为单位集合。

定义6 单位集合矩阵U。将单位矩阵中所有元素为单位集合的矩阵称为单位集合矩阵U。

算法2(链路竞争算法) 步骤如下:

(1) 计算当前时隙下已经分配的链路及其已经执行的时隙。

(2) 对应已分配的链路,在并行时隙集合矩阵A中选出第i列中部分元素

(3) 列向量D·i元素减去已经执行时隙向量与单位集合矩阵U乘积,差值即为链路Li与当前时隙已经分配的链路的并行时隙集合向量。

(4) 在差值向量中,对向量中的所有元素,即所有集合取交集。

(5) 交集中的最小非负数,即为链路Li需要推迟的时隙。

记当前时隙已经分配的链路向量为Slink,在本时隙时集合Slink中的链路已经执行的时隙向量为Sslot,则Slink和Sslot为:

本时隙需要分配的链路Li在并行时隙集合矩阵A中选出第i列根据集合Slink,在A.i中选出对应的元素记为列向量D·i元素减去已经执行时隙向量与单位集合矩阵U乘积,差值即为链路Li与当前时隙已经分配的链路的并行时隙集合向量,记为:

在差值向量R中,对向量中的所有元素,即所有集合取交集,即

在集合I中取最小非负数,即为链路Li需要推迟的时隙。链路竞争算法示例如图4所示。图4中,当前时隙为tc,当前已分配链路有L1、L2,且两者已经执行了3时隙、5时隙,待分配链路为L3。根据链路竞争算法,可以算出链路L3需要推迟0时隙即可执行,即链路L3在当前时隙tc可执行。

图4 链路竞争算法示例

定义7 链路的优先级P。定义链路的优先级为链路中节点发送数据的紧急程度。为了将链路的优先级数字化,称链路的优先级与链路的周期成反比,与链路的步长成正比,即

(1)

其中,C为链路的周期；Hc为链路的步长；k为优先级比例。由(1)式可以看出,链路的周期越短,链路的步长越长,链路的优先级就越高。这与节点数据发送的紧急程度相同,因此(1)式可以表示链路的优先级P与链路的周期C、步长Hc的关系。

为了方便处理链路的时隙分配,所有链路建立一张表,表示链路的一些信息。将同周期链路融合阶段建立的链路附加周期、发送时隙、优先级建立链路时隙表,见表2所列。

表2 链路时隙表

算法3(链路分配算法) 步骤如下:

(1) 根据链路时隙表发送时隙,将在本时隙的链路加入任务池,修改对应的发送时隙为本时隙与周期之和。

(2) 若任务池中的链路数大于0,则转到步骤(3),否则转到步骤(5)。

(3) 从任务池中选择优先级最高的链路。

(4) 对选出的链路,根据算法2分配的时隙,安排节点活动状态,转到步骤(2)。

(5) 等待下一个时隙执行本算法。

根据算法3,为每条链路分配无冲突时隙,按照分配的时隙,链路中的节点安排休眠、发送及接受数据时隙。

3 实验仿真

本文使用NS3仿真软件对随机网络进行实验,从平均响应时间、数据保真度和吞吐率3个方面分析MLSCLC的性能。数据保真度是指汇聚节点能够在截止日期前收到数据的比例。为了测试MLSCLC的性能,将其与数字数据开关阵列(digital data switching matrix,DDSM)[3]进行比较。DDSM是一种基于周期汇报型网络的数据汇聚机制。在未特别指明的情况下,节点随机分布在100 m×100 m的矩形区域内,节点的干扰半径等于通信半径,均设置为15 m,网络带宽为2 Mb/s,数据分组长度为20 Bytes,时隙长度为10 ms;在网络中,存在5种不同的节点周期,其周期长度与基准周期的比值为1∶1.5∶2.5∶3∶5∶6。仿真在以下2种情况下进行：

(1) 不同的网络规模。将节点数量作为自变量,节点数量的取值范围为60～200,并以40 ms为基准周期。

(2) 不同的基准周期。将基准周期作为自变量,取值范围从100 ms到10 ms，将网络节点数量固定为100。

3.1 平均响应时间性能分析

MLSCLC和DDSM 2种机制在不同网络规模下平均响应时间的比较如图5a所示,在不同的基本基准周期下平均响应时间的比较如图5b所示。

图5 2种机制在不同条件下平均响应时间的比较

由图5可以看出,在网络规模较小或基准周期较大时,MLSCLC平均响应时间低于DDSM;随着网络规模的增大,因为MLSCLC需要对不同周期的链路采用竞争算法,需要解决的冲突越来越多,所以2种机制表现的差异逐步减小。

3.2 数据保真度性能分析

MLSCLC和DDSM 2种机制在不同网络规模下数据保真度的比较如图6a所示,在不同的基本基准周期下数据保真度的比较如图6b所示。

图6 2种机制在不同条件下数据保真度的比较

由图6可以看出,当网络规模增大时或基准周期减小时,MLSCLC与DDSM相比数据保真度更高;在网络规模小或基准周期长时,由于冲突的范围小,两者数据保真度差异不大,但是当网络规模逐步增大或基准周期减小时,由于冲突的范围的增大,而DDSM需要等待子节点的数据发送完成后才能发送本节点的数据,周期短的节点数据无法在截止时间内发送到汇聚节点,造成数据保真度的降低。

3.3 吞吐率性能分析

MLSCLC和DDSM 2种机制在不同网络规模下吞吐率的比较如图7a所示,在不同的基本基准周期下吞吐率的比较如图7b所示。

图7 2种机制在不同条件下吞吐率的比较

由图7a可以看出,随着网络规模的增大,网络中冲突发生概率增加,2种机制下网络吞吐率不断下降。因为DDSM每轮都需要计算上一圈中能量剩余最多的节点,带来了额外的计算时间,所以MLSCLC的吞吐率都高于DDSM。

由图7b可以看出,在基准周期为0.1 s之前,由于基准周期长度的约束力不高,随着基准周期的增大,2种机制下网络吞吐率不断提高;但在基准周期40 ms之后,由于基准周期对网络的影响越来越大,随着基准周期的增大,2种机制下网络吞吐率不断下降。同样,MLSCLC吞吐率都高于DDSM。

MLSCLC在吞吐率性能上高于DDSM的原因有:① 初始时,每个节点的链路都是最短链路;② 融合同周期链路后,链路竞争阶段的冲突范围大幅度降低;③ 由于平均响应时间的减少,网络的吞吐率随之增加。

4 结 论

本文针对周期汇报型无线传感器网络提出了一种基于同周期节点链路融合与链路竞争的数据汇聚机制。根据网络特点,融合同周期节点链路、设计链路的并行时隙集合矩阵,并以此为依据进行数据汇聚。通过仿真证明了MLSCLC可以在满足工业网络可靠性和实时性的前提下,合理安排时隙,降低了网络的平均响应时间,并提高了数据保真度及吞吐率。