一种无线传感网络中细粒度延迟测量方法

摘要

一种无线传感网络中细粒度延迟测量方法，步骤为：(1)在无线传感网节点上记录两个本地包间的转发包单跳延迟和；(2)在PC端对收到的包记录进行处理，将每个数据包的逐跳时延当作未知量，建立多种约束条件，包括先进先出约束，路径顺序约束，和单跳转发包时延之和约束；(3)判断需求为求解到达时间的估计值还是上下界，选择不同的优化方法，包括：(4)求解优化问题，选取使短时间内在同一跳上多个包的延迟差异尽可能小到达时间的解，由到达时间获得每个包在每一跳的延迟。

说明书

技术领域

本发明涉及一种无线传感网络中细粒度延迟测量方法，特别是利用尽可能少的节点计算开销及包传输代价，精确恢复出每个包逐跳延迟的方法。

背景技术

无线传感网是一种基于无线通信的可以实现一定应用目的的新型网络，广泛应用于环境监测、目标定位等场合。在实际应用中，数据包通常通过多跳无线网络传送到汇聚节点。延迟信息是无线传感网络运行状态的重要组成部分。数据包传输延迟对于很多时间敏感的应用是极其重要的性能指标。现有的大量工作针对端到端延迟进行测量和优化，通常缺乏将延迟准确分解到逐跳上的轻量级方法。端到端延迟无法定位到问题节点，因此，如何准确测量数据包逐跳延迟，是无线传感网络的重要技术。

对数据包逐跳延迟测量问题主要有两个需求。首先，要求方法是轻量级的，以增强其在资源受限的无线传感网中的可扩展性。因此，在每一跳上直接在数据包尾加入在当前节点的延迟是不可行的，这样会导致网络及资源开销呈线性增长。其次，要求方法是精确的，数据包在每个节点上的停留时间可能为几毫秒，因此要求精度达到毫秒级。

在一个单汇聚节点的无线传感网络中，所有传感节点采集传感数 据并周期性的将数据通过多跳路由的形式发送至汇聚节点。节点可以自己产生数据包，也可以帮助其他节点转发数据包。端到端的延迟信息能够很容易地记录进数据包中，与之相比，逐跳的延迟测量方法达到轻量级和精确性非常具有挑战。原因在于精确性与资源开销间的权衡。

在无线传感网中已存在一些延迟测量方法，例如[7]，MNT，MessageTracing等。其中，[7]通过在MAC层显式地记录数据包的发送和接收时间戳，然后累加其在每一跳的停留时间，记录到包中的固定字段上。这种方法只能获得端到端的延迟，并不能分解到逐跳上。MNT和MessageTracing为最近的两种细粒度延迟重建方法。其中MNT通过推测数据包到达路径上的每个节点时，当前节点在该数据报到达前后生成两个的本地包，本地包的生成时间是已知的，因此可以获得该数据包逐跳延迟的上下界。MessageTracing通过在每个节点上进行数据包的发送和接收事件的日志记录，从而重建出逐跳延迟。这两种方法恢复出来的逐跳延迟准确性都不够高。

发明内容

本发明要克服现有技术的上述缺点，提供一种准确性高的无线传感网络中细粒度延迟测量方法。

为实现以上目的，本发明所采取的技术方案是：该无线传感网络中细粒度延迟测量方法包括以下步骤：

(1)在无线传感网节点上记录两个本地包间的转发包单跳延迟和；

(2)在PC端对收到的包记录进行处理，将每个数据包的逐跳时延当作未知量，建立多种约束条件，包括先进先出约束，路径顺序约束，和单跳转发包时延之和约束；

(3)判断需求为求解到达时间的估计值还是上下界，选择不同的优化方法，包括：

31)判断需求为求解到达时间的估计值，对时间窗口内所有包在每一跳的到达时间变量，建立优化目标函数；

32)判断需求为求解到达时间的上下界，利用图论模型选择适当的到达时间变量及限制条件，建立相应的优化目标函数；

(4)求解优化问题，选取使短时间内在同一跳上多个包的延迟差异尽可能小到达时间的解，由到达时间获得每个包在每一跳的延迟。

进一步地，本发明在步骤(1)中，转发包单跳延迟和，是根据本地包的生成与发送时间，转发包的到达与发送时间获得，具体方法为：

11)在节点设置缓冲区，保存单跳转发包时延之和；

12)在数据包中设置延迟字段，记录两个连续的本地包之间，转发包的单跳时延之和；

13)节点生成本地包时，保存当前的本地时间，作为其生成时间；

14)节点接收转发包时，触发中断处理器来记录当前的本地时间作为接收时间；

15)节点在转发包时，触发中断处理器来记录当前的本地时间作为转发时间；

16)将从包生成时间或接收时间到其转发时间的间隔累加到节点缓冲区的值上；

17)在下一个本地包生成时，将延迟字段的值更新为缓冲区中数据；

18)节点将缓冲区清空；

本发明在所述步骤(2)中，利用无线传感网络收发数据的特性，建立三种约束条件，具体方法为(由于数据包逐跳时延和数据包到达时间可以简单的线性转换，我们在下文的表述中将根据需要选择使用逐跳时延或者逐跳到达时间)：

21)将收到的包记录按固定的时间窗口进行分段；

22)对每个时间窗口内的包，建立其路径上未知节点到达时间的变量；

23)根据在同一节点上先到达的节点先离开，建立在本节点上两个包到达时间变量及其下一跳到达时间变量间的先进先出约束；

24)根据数据包是按顺序到达其路径上的每个节点，建立其每一跳到达时间变量间的路径顺序约束；

25)根据步骤(1)中计算的单跳转发包时延之和，一定包含传播时间在两个本地包生成之间的转发包，建立不等式约束条件。

本文提出了一种无线传感网络中细粒度延迟测量方法，与现有技术相比，本发明的有益效果是：该方法开销低，对于节点端来说，只需要在每个数据包里附加2字节的额外开销来获得建立约束条件的数据；该方法精确度高，能准确恢复逐包逐跳延迟，达到了平均3.58ms 的延迟测量精度。

附图说明

图1是本发明无线传感网络节点程序的部署方法工作流程图。

具体实施方式

下面结合附图对本发明作进一步描述。

为了准确的阐述本文提出的数据包逐跳时延测量技术，我们使用如下符号系统：

该无线传感网络中细粒度延迟测量方法包括以下步骤：

(1)在无线传感网节点上记录两个本地包间的转发包单跳延迟和；

(1.1)在节点设置缓冲区，保存单跳转发包时延之和；

(1.2)在数据包中设置延迟字段，记录两个连续的本地包之间，转发包的单跳时延之和；

(1.3)生成本地包时，保存当前的本地时间，作为其生成时间；

(1.4)节点接收转发包时，触发中断处理器来记录当前的本地时间作为接收时间；

(1.5)节点在转发包时，触发中断处理器来记录当前的本地时间作为转发时间；

(1.6)将从包生成时间或接收时间到其转发时间的间隔累加到节点缓冲区的值上；

(1.7)在下一个本地包生成时，将延迟字段的值更新为缓冲区中数据；

(1.8)节点将缓冲区清空；

(2)在PC端对收到的包记录进行处理，将每个数据包的逐跳时延当作未知量，建立多种约束条件，包括先进先出约束，路径顺序约束，和单跳转发包时延之和约束；

(2.1)将收到的包记录按固定的时间窗口进行分段；

(2.2)对每个时间窗口内的包，建立其路径上未知节点到达时间的变量；

(2.3)根据在同一节点上先到达的节点先离开，建立在本节点上两个包到达时间变量及其下一跳到达时间变量间的先进先出约束；

对于两个数据包x和y，节点n存在于两个包的路径中，令n＝N_ix(x)＝N_iy(y)。我们可以得到以下约束：

(t_ix(x)-t_iy(y))(t_ix+1(x)-t_iy+1(y))＞0.>

(2.4)据数据包是按顺序到达其路径上的每个节点，建立其每一跳到达时间变量间的路径顺序约束，在实际的无线传感网络系统中，一个数据包在一个转发节点的逗留时间存在一个最小值w。这个最小值的来源主要是数据包在节点的协议栈中传递的时间以及发送时的MAC初始退避时间。因此我们可以得到以下线性约束：

t₀(p)＜t₁(p)-w＜…＜t_|p|-1(p)-(|p|-1)w.>

(2.5)根据步骤(1)中计算的单跳转发包时延之和，一定包含传播时间在两个本地包生成之间的转发包x，建立不等式约束条件。

其中C*(p)即表示符合前文所述条件数据包x的集合。

(3)判断需求为求解到达时间的估计值还是上下界，选择不同的优化方法，包括：

(3.1)判断需求为求解到达时间的估计值，对时间窗口内所有包在每一跳的到达时间变量，建立优化目标函数；

其中N表示网络中除sink节点外所有节点的集合；x，y代表经过同一个转发节点n的两个数据包；e表示x，y这两个数据包的发出时间差的上界；D_n(x)和D_n(y)分别表示数据包x和y在节点n上的单跳时延。该优化目标是最小化符合上述条件的所有数据包>

(3.2)判断需求为求解到达时间的上下界，利用图论模型选择适当的到达时间变量及限制条件，建立相应的优化目标函数；

(3.2.1)将所有未知量和约束条件通过图论进行建模。图中的节点表示未知量，节点间的边表示该两个未知量存在约束条件；

(3.2.2)采用平衡标签传播(balanced label propagation)的算法，从整个图中裁剪出以当前未知量为中心的一个子图；

(3.2.3)将子图转化为相应的到达时间变量与限制条件。

(3.3)使用凸优化快速求解优化问题，选取使短时间内在同一跳上多个包的延迟差异尽可能小到达时间的解，由到达时间获得每个包在每一跳的延迟。

本说明书实施例所述的内容仅仅是对发明构思的实现形式的列举，本发明的保护范围不应当被视为仅限于实施例所陈述的具体形式，本发明的保护范围也及于本领域技术人员根据本发明构思所能够想到的等同技术手段。