无线传感器网路径时延区间估计算法研究＊

［黄河清］

1 引言

随着各种通信技术和手段的发展，网络正在从互联网向所有机器和设备具有互联能力的方向发展。传感器网络连接物联网和物理世界，承担收集和传输数据的任务。在无线传感器网络（WSN）中，强实时性的关键任务，如工业控制和智能交通，无线消息传输对实时性和可靠性提出了很高的要求。在多跳无线网络中，实时路由的主要含义是在有限的时间内将数据包从源节点路由到目的节点。实时路由的关键要素是消息的可靠和实时传输。然而，由于无线链路的时空动态和沿路径的队列变化特征等因素的影响，数据包跨路径成功传输的时间（即路径延迟）是不确定的。路径延迟的这种动态特性给实时路由的计算带来了根本性的挑战。

虽然在无线路由算法上已经做了大量的研究工作，但基于吞吐量或能效，对高效实时路由的研究效果较差。尽管现有的无线路由研究结果增加了最小化平均路径延迟的努力，但它们并不能保证一定的概率边界。因此，如何在不确定和动态的链路环境下提高实时路由的效率是实时无线传感器网络研究的重要任务。为了在无线传感器网络中实现概率延迟边界路由，我们提出了一种多时间尺度方法，该方法以自适应延迟界限估计（ADBE，adaptive delay bound estimation）表示。通过准确估计数据包时间的平均值和方差，并通过适应快速变化的队列，可以计算出路径延迟的方差和平均值，以解决实时路由中动态和不确定的路径延迟问题。利用上述路径延迟计算结果，通过实验评估了计算路径延迟上限的方法，并比较了它们的效率和效果。

通过检索无线传感器网络路由的现有研究文献，虽然也考虑了路径延迟要素，但大部分研究只努力最小化平均路径延迟，而不考虑路径延迟的概率特征，或者不对延迟概率边界进行分析。一些研究侧重于转发路径上链路可靠性、时效性等QoS 因素的统一划分，但缺乏网络异构性的引入。然而，在互联网流量工程的应用中已经提出了自适应时延边界估计。总之，现有的研究大多只关注数据传输的可靠性，缺乏实时性研究。因此，对实时路由中的动态和不确定链路时延的研究还存在不足。

端到端时延在硬实时系统中有严格的要求，主要依靠物理层的调度工作来满足实时性目标。如I-EDF[1]、dual-Mode[2]，但这种方法对物理条件要求很高。在SPEED[3]的研究中，提出了转发速度的概念，主要通过每一跳的转发速度来保证端到端的通信时延，但SPEED 没有考虑链路的质量，不能保证可靠性。其他研究从分层网络结构的角度考虑实时。例如，文献[4]通过调整非实时和实时数据占用的传输带宽来最大化每个集群的吞吐量，但在效率方面存在明显不足，难以满足实时性要求。本文接下来介绍了自适应路径延迟边界估计方法，提供实验数据验证结果，并对研究情况做一总结。

2 自适应路径延迟边界估计

2.1 路径延迟概率边界计算

通过在实验系统上测试验证，我们发现：在大流量模式下，网络中会出现严重的队列拥塞，队列溢出频繁发生;在中等流量模式下，网络的排队程度适中，但很少发生队列溢出[5];但在轻流量模式下，网络中不存在排队现象;基于以上条件假设，我们选取12 个节点作为业务数据源，1 个节点作为汇节点。在拓扑中，源节点和接收器节点几乎处于相反的位置，以创建多路由路径。每个源节点每75 ms、400 ms 和1 000 ms 生成一个重、中、轻流量数据包。

为了保证路由的延迟概率在限定范围内，如何量化路径上的延迟概率是一项重要的工作。如图1 所示，在给定路径P=v0,v1,...,vn,vn+1,中，假设在节点 vi（节点 0 到节点 n）呈现如下状态：

图1 路径延迟构成

其中，mi(t)表示 t 时间点队列中的数据包编号；dP(t)表示路径 P 在 t 时间点的当前延迟。

将数据包传输到 vn+1时，如果每个节点队列中的数据包数量保持固定，则dP(t)是到达目标节点vn+1的 v0数据包所经历的延迟。由此，节点vi将其队列中的第 j 个数据包路由到节点vi+1所花费的时间可以表示为：

2.2 时延动态分布的关键问题

由于无线传感器节点的资源限制，很难直接计算dP(t)的分布。另一种方法是对dP(t)进行采样，之后使用非参数方法（如P2 算法）来估计这些延迟样本的延迟分位数，但非参数分位数估计通常收敛缓慢，可能需要数百个样本。可以发现，路径延迟在一定时间范围内波动，远小于非参数估计方法的窗口要求。这在上面的公式1 中可以看出，路径延迟的分布随转发路径上的队列级别mi(t)（t 时间点队列中的数据包数）而变化，并显示出快速时变的特征。

仿真结果表明，非参数分位数估计收敛所需的样本量比相干窗口高两个数量级。因此，路径延迟分布的快速变化特性使得非参数分位数估计难以满足瞬时路径延迟分位数估计的灵活性和精度要求。

为了准确灵活地估计精确的路径延迟分位数并降低计算复杂度，我们提出了一个上限边界来识别概率路径延迟，并利用延迟边界进行实时数据传输路径的选择。路径延迟的上限可以通过切比雪夫neQuality 概率不等式推导出来，正确识别的延迟边界可以达到比最大延迟小一个数量级，从而避免了对网络实时容量的不利影响。

因此，我们需要设计一种更灵活、更准确的机制来估计路径延迟的均值和标准差，避免大多数概率不等式使用相应的随机变量计算方法的缺点。因为路径延迟统计的准确估计通常需要相当大的样本量，可以高达300 到600[6]，这明显大于节点队列级别的一致性窗口。

2.3 自适应延迟边界估算

为了应对路径延迟和统计分布变化带来的挑战，将路径延迟变化因子分解为动态排队和动态分组时间两个类别。利用队列和数据包时间的不同统计时间尺度，提出一种自适应时延界限估计（ADBE）方法，该方法可以通过两种方式准确估计路径时延的均值和方差：（1）在短时间尺度上适应快速变化的队列；（2）在长时间尺度上准确估计数据包时间的均值和方差。

2.3.1 包转发时间分布

经过对实验数据的详细分析，我们发现瞬时数据包时间的分布具有良好的稳定性，尽管在一定的网络条件下瞬时数据包时间变化很快。通过分析数据包时间平稳窗口的大小，如图2 中的直方图所示，可以得出结论，在时间序列的连续区间中，每个静止窗口都是时间序列中最大的连续段。

图2 包时间与静止窗口分布图

为了适应无线传感器网络中嵌入式节点的存储资源限制和实时传输要求，节点队列的最大大小通常小于稳定性窗口的大小。这意味着公式（1）中dji(t)的方差和平均值相同，表示为路径延迟σ2(di(t)) 和平均路径延迟μ(di(t))的总变化。

因此可以计算出平均路径延迟：

2.3.2 包时间的非相关性

同一节点或不同节点的传输时间通常并不重要，对于给定的时间点，我们通过对沿路径排队的所有数据包的延迟方差求和，然后将总和的平方根作为标准偏差的等效值来计算从源节点到目标节点的路径延迟标准偏差。

对于图 1 中的路径 P，dP(t) 的标准偏差计算如下：

从上面的分析结果中，我们可以进一步推断出一个节点可以对不同数据包的下一跳做出很好的选择。假设每个节点vi（i 从0 到n）具有Ni(t)可选的下一跳数，mki(t)表示在时间t 处路由到第k 个跳的数据包数，di,k(t)表示相应的数据包时间。

沿路径P 的延迟标准差和平均值可以根据公式（2）和（3）计算如下：

2.3.3 网络排队时间的短时稳定性

这里，从vi到vn+1的延迟标准差和平均值分别用σ(diP(t)) 和μ(diP(t))表示。每个节点vi可以通过公式（4）计算从自身到vn+1的延迟的平均值和方差。方法是计算沿路径P 的每个跃点的平均值和方差。这样，我们得到以下结果。

通过允许vi+1连接σ2(diP(t))和μ(diP(t))来控制信令或数据传输，vi可以在τi的最短时间内快速准确地估计σ2(diP(t))和μ(diP(t))。

3 路径概率延迟边界实验分析

根据上面提出的ADBE 算法估计路径延迟均值和方差，节点的概率延迟边界值由概率不等式得到。

在随机变量 x 的条件下，如果下面条件满足：

Pr{X ≥ f(x)} ≤ g(x),QqX=f (g-1(1-q))

则X 的q 分位数上的上限QqX=f (g-1(1-q))可以通过以下步骤计算出来，其中g-1是g 的反函数：

使g(x)=1-q

实验采用选取12 个节点作为业务数据源，1 个节点作为汇节点。在拓扑中，源节点和接收器节点几乎处于相反的位置，以创建多路由路径。每个源节点每 75 ms、400 ms和 1 000 ms 生成一个重、中、轻流量数据包。链路排队变化的经验累积分布（cumulative distribution function，CDF）的实验数据如图3 所示，从图3 可以看出，网络队列在几个数据包间隔的时间尺度上相对稳定，85%概率的链路排队变化绝对值保持2 以下。

图3 CDF 与排队变化关系

基于上述分析，本算法具有相对稳定的短期网络排队和快速信息扩散，ADBE 方法能够准确、灵活地估计路径延迟的均值和方差。

4 总结

由于无线传感器网络的动态性和不可靠性，端到端时延不确定，对实时路由的设计提出了严峻的挑战。因此，考虑到链路质量和链路时延，本文设计了一种新的路径时延估计算法ADBE。针对路径时延高度变化对路径时延分位数分布式估计的挑战，利用转发可靠性来表示节点在给定时延阈值下成功转发数据包到邻居节点的概率，以保证路由的实时性和可靠性，并提供一定水平的QoS。当链路质量在环境中较差时，在满足实时性要求的基础上，通过权衡传输时延和传输可靠性，可以实现更高的传输成功率，实验结果也证明了所提方法的优点。