基于路径到达率和动态广播时延的汇聚树协议①

赵 城潘露萍

(浙江工业大学信息工程学院 杭州 310023)

0 引 言

无线传感器网络(wireless sensor network，WSN)由具有传感、数据处理和短距离无线通信功能的传感器节点组成，已广泛应用于国防军事、环境监测、生物医疗、交通管理、抢险救灾等众多领域。传感器节点通常都由干电池供电，能量和无线通信能力有限，因此如何快速有效又节能地采集传感器数据，延长网络寿命一直是研究的重点。

汇聚树路由协议[1](collection tree protocol, CTP)是基于树状结构的汇聚协议，应用非常广泛[2,3]。在CTP协议下，每个节点将各自的数据上传给父节点，最后汇聚到根节点sink，采用了基于期望传输次数(expected transmissions count, ETX)的距离向量路由算法。传统的CTP协议用ETX[4]来衡量链路质量，虽然计算比较简便，但在多跳路径中，ETX的简单相加往往会与实际链路质量产生偏差。对CTP这种逐级上传的多跳网络架构，用单跳链路质量的乘积能更好地表示整条上传路径的质量。

本论文采用节点到根节点整条路径的数据包到达率(packet delivery ratio, PDR)来衡量路径质量。本文的主要贡献如下：

(1) 提出了基于路径到达率的PDR-CTP协议，通过计算和仿真表明，同传统的基于ETX的CTP协议相比，可以有效提高路径端到端数据传递的成功率，另外还可以节省平均总传递次数和平均延时，节省能耗，提高网络生存时间。

(2) 提出了动态延时广播算法，在建树过程中，通过动态延迟，使得质量好的节点先行广播，提高建树过程的稳定性，减少广播次数，节省能耗。

1 相关工作

在WSN中，无线链路质量一直是研究的重点[5]，目前比较常用的衡量指标有ETX、packet reception ratio(PRR)[6]、four-bit(4B)[7]、request number of packets (RNP)[8]、window mean with exponentially weighted moving average (WMEWMA)[9]，这些指标各有侧重点，文献[10]对这些指标进行了详细的分析和比较。但这些指标都只衡量了2个相邻节点的链路质量，对于多跳路径质量，只是简单地将这些指标进行线性叠加，显然这与实际多跳路径的质量不符。因此如何衡量多跳链路的质量是本文研究的出发点。

对CTP协议，目前已有一些相关研究工作。文献[11]和文献[12]分别对传统CTP协议的静态和动态性能进行了评价，并分析了原因。文献[13]提出了多通道汇聚树概念，在增加相应路由开销的基础上提高了汇聚树的稳定性，并可以减少数据汇聚时间。为了解决网络抖动和拥塞，文献[14]提出用概率来随机选择父节点，虽然能在一定程度上减少广播开销，但显然有很大概率无法选到最佳的父节点。文献[15]提出了衡量链路质量的fuzzy logic indicator(FLI)指标，它将PRR和其动态方差以及更新时间统一在一起考虑，利用模糊逻辑控制思维来选择路由节点，实验数据显示比原有协议有所提高。文献[16]也对路由选择指标进行了改进，但它们都只考虑了单跳的链路质量。文献[17]将PDR和ETX结合起来，提出了QoF指标，实验表明该算法减少了汇聚树的传输开销，并提高了端到端的到达率，但没有对建树时的广播泛滥进行改进。文献[18]对通信系统时延进行了研究，指出时延能影响通信性能，因此在CTP协议中设置合适的时延很有必要。文献[19]提出了average transmission time(ATT)用最短传输时间来代替ETX，平均减少了17.7%的延迟。文献[20]提出了一种基于度约束最短传输树的多路径传输协议，使网络中每个节点均有2条互不相关路径到达汇聚节点并且传输距离最短，提高了数据传输可靠性，但以上算法都没有考虑多跳链路的质量。

综上所述，本文提出的基于路径PDR和动态广播延迟策略的CTP协议对建立高效节能的汇聚树路由具有一定的研究意义。

2 基于链路PDR的CTP协议

2.1 传统CTP存在问题

在多跳路径中，ETX的简单相加往往会与实际链路质量产生偏差，如图1所示。

图中，节点S为网络中的根节点，即数据汇聚中心，B、C、D、E为其子节点。p1、p2、p3、p4、p5为相邻节点间数据包传递成功的几率，对节点E，它到根节点S有两条路径，E→D→B→S和E→C→S。在不考虑失败重传的情形下，2条路径端到端传递成功几率PDR为

PDREDBS=p1×p3×p4=0.729

PDRECS=p2×p5=0.54

可得PDREDBS>PDRECS。

但是2条路径的ETX却正好相反：

ETXECS=10/9+5/3=30/9

ETXEDBS=10/9+10/9+5/3=25/9

可得ETXEDBS>ETXECS。

可见，在多跳链路中，ETX的简单相加不能很好地表示整条链路的质量，因此本文采用单跳链路质量的乘积这一指标，能更好地刻画整条上传路径的质量。

2.2 PDR-CTP路由策略

同传统CTP协议类似，本文提出的基于路径PDR的CTP协议，在新节点加入汇聚树时，计算它通过各条备选路径到达根节点的到达率，从中选择PDR最高的路径。同时为了避免建树时的广播泛滥，在建树时，对PDR较低的节点进行延迟发送广播，以确保PDR高的节点先发送广播，减少广播泛滥几率。PDR-CTP建立树的过程如下：

(1)sink节点发起建立汇聚树通知，向周围节点广播自身信息，PDRs→s=1。

(2)节点k收到sink节点的广播信号后，更新自己到sink节点的到达率PDRk→s，并根据PDRk→s设置一点的延迟Tdelay后，向周围节点广播自身信息PDRk→s。

(3)中间过程，节点i收到j发出的汇聚树广播信号后，计算自身到sink节点的到达率PDRi→s=PDRi→j×PDRj→s。同时检查是否已有到达sink节点的路径，若没有则选择节点j作为自身的父节点加入汇聚树。若已经存在，则比较新旧PDRi→s大小，若新PDRi→s较小，则忽略该广播信息，若新PDRi→s较大，则放弃原来的父节点，选择j作为自身的父节点重新加入汇聚树。并根据PDRi→j设置一定的延迟Tdelay后，向周围节点广播自身信息PDRi→s。

(4)重复过程(3)直到所有节点都加入汇聚树。

本协议关键在于到达率PDR的计算，对一个单跳链路i→j，影响PDRi→j主要有以下2点：

(1)i与j之间单个数据包的传递成功率pij；

(2)重传上限r,当i与j之间重传次数大于r次时，将放弃数据包的再次传递。

根据以上2点，可以计算出i与j间总的数据包到达率为

PDRi→j=1-(1-pij)r+1

(1)

这样i到sink节点总的数据包到达率为

PDRi→s=PDRi→(i-1)×PDR(i-1)→(i-2)×…

×PDR(s-1)→s

(2)

2.3 PDR-CTP性能分析

PDR-CTP协议从到达率PDR着手，将一个多跳路径的各链路质量进行相乘，而传统CTP则是将多条路径的各链路质量进行相加。从理论上讲，各链路质量相乘更能体现整条路径的质量优劣。

对到达率要求比较高的网络，显然采用路径PDR作为选择路径的指标会更好一点。特别是在链路质量比较差的LLN网络中，选用PDR指标要明显优于ETX指标。

对某个节点i，它到sink节点的到达率和ETX分别为PDRi→s、ETXi→s。由于到达率PDR的下降，i节点信息成功传递到根节点S的几率下降，失败之后，节点i只能重新发起上传任务。这样节点i信息成功传递到根节点S，所需要的总传递次数设为ETXTi→s(expected transmission count in total)可得：

ETXTi→s=ETXi→s/PDRi→s

(3)

对于一条路径n→(n-1)→…→1，有：

(4)

(5)

(6)

由上式可以看出，ETXTn→1表示了实际的平均传递次数，与ETXn→1存在很大的差异。而在传统CTP协议中，ETXTn→1=ETXn→1因此从理论上用此标准往往无法找到数据传递的最优路径。

ETXT指标不仅衡量了数据节点i到sink节点所需要的总传递次数，同时也体现了平均能耗和平均时延的大小。

假设传输一次数据包的平均时间为T0，可得T0=ts+tp+tt，其中，ts为数据包发送时间，tp为数据包处理时间，tt为数据包在空中的传递时间。

计算可得i节点到sink节点路径的平均时延Ti→s。

Ti→s=ETXTi→s×T0

(7)

同样可假设每次送一个数据包所需要的平均能耗为E0(实际中质量较差的链接可能会选择更高的发射功率)，可得i节点到sink节点路径的平均能耗Ei→s为

Ei→s=ETXTi→s×E0

(8)

当路径跳数为1时，ETX评价指标与实际到达率PDR、总传递次数ETXT相符。随着跳数的增加，ETX评价指标与实际到达率PDR、总传递次数ETXT将产生偏差，因此选用链路总PDR作为指标能更好地体现实际情况，这不仅可以提高总的到达率，还可以减少总的传递次数，节省能耗。

以图1为例，若取p1=p2=p3=p4=0.5，p5=0.3，r=3，有：

ETXTEDBS=10/5+10/5+10/5=6

ETXTECS=10/5+10/3=80/15

可得ETXTEDBS>ETXTECS。

PDREDBS=[1-(1-0.5)4]

×[1-(1-0.5)4]

×[1-(1-0.5)4]=0.8239

PDRECS=[1-(1-0.5)4]×[1-(1-0.3)4]

=0.7124

可得PDREDBS>PDRECS。

以节点E信息成功传递到根节点S为前提，所需要的总传递次数为ETXT，有：

ETXTEDBS=ETXTEDBS/PDREDBS=6/0.8239

=7.282

ETXTECS=ETXTECS/PDRECS=(80/15)/0.7142

=7.486

可得ETXTECS>ETXTEDBS，这表明链路E→D→B→S不仅到达率PDR优于链路E→C→S，而且总传递次数ETXT也要优于E→C→S。

另外可得2条路径的平均时延分别为

TEDBS=ETXTEDBS×T0=7.282T0

TECS=ETXTECS×T0=7.486T0

TEDBS

能耗方面，假设每次送一个数据包所需要的能耗为E0，同样可得：

EEDBS=EEDBS×T0=7.282E0

EECS=EECS×T0=7.486E0

EEDBS

2.4 建树过程中时延Tdelay的选择

在建立汇聚树的过程中，PDR较小的节点有可能先接收到建树的广播信息，若其先行继续向下广播，很多节点会以此节点作为父节点。而当这些节点接收到PDR较大的节点发出的广播时，这些节点会更改自身在树中的结构并再次广播，这样就会产生广播泛滥。因此，如何让PDR大的节点先行广播也是一个很重要的问题。

本文在建树过程中，采取了一种动态延迟策略，当一个节点i接收到建树的广播信息后，根据上一跳的链路质量(ETX)，设立一个动态延时值，Tdelay=K(ETX-1)，K为加权因子。通过延时值的动态调整，加大PDR好的节点先行广播的几率，以减少建树时广播的泛滥，节省能耗。

对于一条路径1→2→…→n, 假设pij为节点i与节点j之间单次传递成功的概率，假设重传上限为r，可以得到一个数据包经过k次重传，从节点1成功传到节点n的概率为P1→n(重传=k)。

P1→n(重传=k)

(9)

数据包成功从节点1传到n的总传递次数为(n-1+k)。可得节点1传到n的总传递次数为m的概率P1→n(总=m)为

P1→n(总=m)=P1→n(重传=m-n+1)

(10)

以图1为例，节点E有很大概率先收到C发出的广播信息，若直接向下继续广播，会造成广播泛滥，因此需要设置延迟，使节点E接收到D发出的广播信息后，再向下广播。

假设重传上限为r=3，每次传输处理时间都一致，则数据包时延主要取决于重传递次数。

数据包从路径E→D→B→S走时，当总传播次数为m, 传递成功，概率记为PEDBS(总=m)，有:

PEDBS(总=m)=PEDBS(重传=m-3)，根据式(7)计算，可得：

PEDBS(总=3)=p1p3p4=0.729

PEDBS(总=4)=[(1-p1)+(1-p3)

+(1-p4)]p1p3p4=0.2187PEDBS(总=5)=0.04374

PEDBS(总=6)=0.005103

PEDBS(总=loss)=0.002997001

数据包从路径E→C→S走时，有:

PECS(总=m)=PECS(重传=m-2)

PECS(总=2)=p2p5=0.54

PECS(总=3)=0.27

PECS(总=4)=0.1134

PECS(总=5)=0.0108

PECS(总=6)=0.000864

PECS(总=loss)

=0.064936

则E在收到C建树信息之前进行向下广播的概率为Pf=P(ECS

P(ECS2)

+PECS(总=3)PEDBS(总>3)

+PECS(总=4)PEDBS(总>4)

+PECS(总=5)PEDBS(总>5)

+PECS(总=6)PEDBS(总>6)

=0.6191

加入动态延迟后，广播泛滥概率Pf将减少。

当K=2.5时，有：

P(ECS

=PECS(总=2)PEDBS(总>3)

+PECS(总=3)PEDBS(总>4)

+PECS(总=4)PEDBS(总>5)

+PECS(总=5)PEDBS(总>6)

+PECS(总=6)PEDBS(总>7)

=0.13

但同时付出的代价是建树时延增加了1.11T0。

当K=5时，有：

P(ECS

=PECS(总=2)PEDBS(总>4)

+PECS(总=3)PEDBS(总>5)

+PECS(总=4)PEDBS(总>6)

+PECS(总=5)PEDBS(总>7)

+PECS(总=6)PEDBS(总>8)

=0.0265

付出的代价是建树时延增加了2.22T0。以上结果见表1。

表1 动态时延算法结果

由以上分析可以得出，动态延迟算法能够提高PDR大的节点先行进行广播的概率，减少建树期间的广播数量，节省能源。

对于能量受限和负荷过重的节点i，同样可以选择合适的Tdelay，让剩余能量较高和空闲的节点承担更多的中继任务，以提高整个网络的生存时间。剩余能量较多的节点，选择较小的Tdelay，可以提高被选中做中继节点的概率，承担更多的任务。能量剩余较少的节点，选择较大的Tdelay，当有别的候选路径时，能避免被选中，同时在没有备用路径时，也可以承担起中继任务。

3 仿真分析

本节使用OMNET网络仿真软件对本协议进行了网络仿真验证。网络拓扑结构如图2所示，100个节点均匀分布在100 m×100 m的平地上。使用IEEE802.15.4协议，传输速率为1～35 kbps，传输频段为2 440 MHz。

图2 仿真网络场景

初始时刻，随机选取图中任一节点为根节点，分别用CTP和PDR-CTP路由协议进行建树。图3是2种路由协议在不同速率下的建树时间和广播开销。采用PDR-CTP建树时，延迟参数K=3。仿真结果显示，PDR-CTP协议的广播开销要明显小于CTP协议，而且平均建树时间只增大了20%。

表2 建树开销

树建立后，选取相同的较远节点，分别对2种协议下的节点到根节点S的到达率、时延和吞吐率进行了统计平均。图3、图4、图5为仿真结果。可见，利用PDR-CTP协议建立起的采集树，其端到端平均到达率PDR，平均时延和吞吐率要明显好于CTP协议，这充分说明根据PDR-CTP协议建立起的采集树成功避免了ETX小但整体质量不佳的链路。

图3 平均端到端到达率

图4 平均延时

图5 平均数据吞吐率

4 结 论

本文提出了一种基于路径到达率PDR和动态广播时延的汇聚树路由协议。同传统的基于ETX的汇聚树协议相比，本协议能更好地刻画多跳路径质量，有效提高端到端的数据到达率，还可以在一定程度上减少总的数据传递次数，减少平均时延。另外建树时的动态延迟策略可以减少建树时经常发生的广播泛滥，节省建树开销。