基于主动链路质量估计的采集树协议

Collection Tree Protocol Based on Active Link Quality Estimation

摘要: 采集树协议CTP依赖数据包和信标的传输估计链路质量，在此基础上选择多跳传输路径，在长时间未进行传输的情况下，无法更新链路质量估计，当采用休眠机制时，难以利用信标序号估计链路质量。本文提出一种基于主动链路质量估计的采集树协议ALE-CTP，对CTP的链路估计方法做出改进，通过在本地采集干扰和噪声强度并计算输入特征，各节点能够利用基于线性回归的模型LEAPS主动估计链路质量。LEAPS采用近似的信干噪比样本的1~3阶原点矩作为输入特征，由于链路质量估计不依赖于传输过程，即使长时间没有数据或信标传输，也能对实时的链路质量进行准确估计。在TinyOS中实现了ALE-CTP，并在真实环境中进行了测试，实验结果显示，与采用4Bit的CTP相比，在有较强干扰的条件下，ALE-CTP具有更高的切换成功率和较短的响应时间，交付率提高了23%，时延降低13%。

Abstract: The Collection Tree Protocol (CTP) estimates link quality based on the transmission of data packets and beacons, and selects multi-hop transmission paths accordingly. In the absence of transmission for a long time, the link quality estimation cannot be updated. When a sleep mechanism is employed, it is difficult to estimate link quality using beacon sequence numbers. In this paper we propose a collection tree protocol ALE-CTP based on active link quality estimation, which improves the link estimation method of CTP. By collecting interference plus noise intensity and calculating input features locally, each node can actively estimate link quality using the offline trained model LEAPS. LEAPS is based on linear regression and uses the first to third order origin moments of the approximate signal to interference plus noise ratio (SINR) samples as input features. It makes link quality estimation independent of transmission process, enabling accurate real-time estimation of link quality even in the absence of data or beacon transmissions over extended periods. ALE-CTP was implemented in TinyOS and tested in a real environment. The experimental results showed that compared with CTP using 4Bit, ALE-CTP had a higher switching success rate and shorter response time under strong interference conditions. The delivery rate was increased by 23% and the latency was reduced by 13%.

1. 引言

采集树协议[1] (Collection Tree Protocol, CTP)是典型的无线传感器网络(Wireless Sensor Network, WSN)通信协议，根据估计的链路质量建立和维护多跳传输路径，形成动态的树状网络拓扑。CTP采用的链路质量估计方法为4Bit，对于传输路径上的链路，通过统计数据包成功传输的比例估计预期传输数量(Expected Transmissions, ETX)，对于非传输路径上的链路，根据接收的信标序号计算包接收率(Packet Reception Ratio, PRR)，再转换为ETX。当数据传输间隔较长时，统计包接收数量需要较长时间，由于长时间不能更新链路质量估计，通信效率和可靠性可能因此降低。当采用低功耗侦听模式时[2]，根据包序号估计PRR存在困难，导致无法准确估计非传输路径上的链路的质量。

为缩短链路质量估计的时间，一些研究采用映射模型估计链路质量，根据物理层参数与PRR的关系，利用传输过程中获取的物理层参数估计PRR。映射模型分为基于通信理论建立的模型[3] [4]、通过实验建立的经验模型[5]以及采用机器学习方法建立的模型[6]-[10]。采用映射模型的方法面临的一个问题是特征重叠，即对于特定的物理层参数取值，PRR的取值范围可能很大，导致较大的预测误差。

为了减小映射模型的预测误差，文献[11]-[17]采用映射模型与统计模型相结合的方法，利用相邻窗口的PRR的相关性提高预测精度，不过，此类方法同样存在特征重叠和依赖于传输的问题，当长时间没有进行传输或难以根据序号统计接收成功率时，无法更新链路质量估计。

近年来，一些研究尝试采用深度学习方法提高链路质量估计的精度[3] [7] [9] [18]-[21]，由于复杂度较高，所提出的方法难以在资源有限的WSN中实现。

本文提出一种基于主动链路质量估计的采集树协议(Active Link Estimation based Collection Tree Protocol, ALE-CTP)，对CTP的链路质量估计方法进行改进，采用近似的信干噪比ASINR (Approximate Signal to Interference plus Noise Ratio)的1~3阶原点矩作为链路估计模型LEAPS (Link Estimation with ASINR Power Series)的输入特征，使链路质量估计独立于传输过程，即使长时间不进行数据或信标传输，也能对实时的链路质量进行准确估计，在TinOS中实现了ALE-CTP，实验结果表明，当存在干扰时，ALE-CTP能够更快地响应链路质量的变化，从而提高交付率，减小时延。下面首先介绍链路估计模型LEAPS和在线链路质量估计算法，然后说明ALE-CTP的实现方法，并给出实验结果和分析，最后对全文进行总结。

2. 链路估计模型

基于为了实现主动的链路质量估计，本文采用ASINR作为链路估计模型的输入参数，在时刻t，节点i接收节点j发送的信号的ASINR瞬时值${\gamma }_{ij}\left(t\right)$ 的计算方法如下：

${\gamma }_{ij}\left(t\right)=\overline{{\phi }_j}-\eta \left(t\right)$ (1)

其中，$\overline{{\phi }_j}$ 为最近获取的邻居节点j的接收信号强度(Reception Signal Strength, RSS)均值，$\eta \left(t\right)$ 为节点i在时刻t采集的干扰与噪声强度(Interference plus Noise Strength, INS)。对于固定位置部署的WSN，RSS的波动范围通常较小，因此，可以用最近获取的RSS均值作为当前的RSS的近似值，从而能够以独立于传输的方式估计链路质量。

Figure 1. The correlation coefficient between the mean ASINR and PRR with different statistical windows

图1. 采用不同统计窗口的ASINR均值与PRR的相关系数

受干扰影响，原始的ASINR样本与PRR的相关性较低，为此，本文利用ASINR提取输入特征，选择ASINR样本的1~3阶原点矩作为LEAPS的输入特征。图1显示了按不同统计窗口计算的ASINR样本均值(即1阶原点矩)与按不同统计窗口计算的PRR之间的相关系数，可以看到，当两者的窗口相同时，相关系数最大，因此，本文采用与PRR相同的统计窗口计算ASINR样本的原点矩。为了减小计算和存储开销，利用指数加权移动平均值(Exponential Weighted Moving Average, EWMA)与窗口均值之间的近似相等关系，在计算PRR和ASINR的原点矩时，本文进一步使用按小窗口计算的均值的EWMA代替按大窗口计算的均值，变量x的EWMA的计算方法如式(2)和式(3)所示。

$y_0=x_0$ (2)

$y_k=\left(1-\alpha \right)y_{k-1}+\alpha \cdot x_k,\left(k\ge 1\right)$ (3)

上式中，$\alpha$ 为平滑系数，在本文实验中，取统计窗口大小为5，$\alpha =0.1$ ，所得到的窗口均值的EWMA与按大小为75的统计窗口计算的均值近似相等。

LEAPS采用线性回归算法估计链路质量，PRR估计值$\widehat{P}$ 的计算方法如式所示：

$\widehat{P}={\omega }^{T}X$ (1)

$X={\left(1,{\overline{\gamma }}_E,{\overline{{\gamma }^2}}_E,{\overline{{\gamma }^3}}_E\right)}^T$ (5)

其中，$\omega \text{=}{\left({\omega }_{\text{0}},{\omega }_1,{\omega }_2,{\omega }_3\right)}^T$ 为系数向量，$X$ 为输入特征向量，${\overline{{\gamma }^m}}_E$ $\left(1\le m\le 3\right)$ 为统计窗口中的ASINR样本的m阶原点矩的EWMA。

采用多种条件下采集的数据训练模型，可以求出系数向量的估计值$\widehat{\omega }$ ：

$\widehat{\omega }={\left(X^{\mathrm{T}}X\right)}^{-1}{X}^{T}Y$ (6)

$X=\left(\begin{array}{cccc}1& {\overline{\gamma }}_{E1}& {\overline{{\gamma }^2}}_{E1}& {\overline{{\gamma }^3}}_{E1}\\ 1& {\overline{\gamma }}_{E2}& {\overline{{\gamma }^2}}_{E2}& {\overline{{\gamma }^3}}_{E2}\\ ⋮& ⋮& ⋮& ⋮\\ 1& {\overline{\gamma }}_{En}& {\overline{{\gamma }^2}}_{En}& {\overline{{\gamma }^3}}_{En}\end{array}\right)$ (7)

$Y={\left(P_1,P_2,\cdots ,P_n\right)}^T$ (8)

其中，X为输入特征矩阵，Y为输出向量，n为训练集中输入特征向量或PRR样本的数量。

Figure 2. Partial correlation coefficients between input features and target variables obtained by different imputation methods

图2. 不同填充方法得到的输入特征与目标变量的偏相关系数

对于训练集和测试集中与接收失败的包对应的记录，需要采取适当的方法进行预处理，本文采用训练集中的ASINR最小值对缺失的ASINR样本进行填充。图2显示了分别采用最小值、0和均值填充时，PRR与ASINR样本的1~3阶原点矩的偏相关系数的绝对值，可以看到，采用最小值填充，能够使PRR与输入特征之间具有更高的相关性，同时，各输入特征与PRR之间的偏相关系数均高于0.95，表明以ASINR的1~3阶原点矩作为线性模型的输入特征能够获得较高的预测精度。

3. 在线链路质量估计算法

在线估计链路质量的算法可以用图3所示的状态图表示，当节点接收到数据包或信标时，将更新对应邻居节点的RSS均值；节点按照特定的周期采集ASINR样本，每到采集时刻，节点通过读取RSSI寄存器，得到INS，结合最近获取的各邻居节点的RSS，计算每个已知链路的ASINR及其2次和3次方样本，当得到一个链路在当前窗口中的所有样本后，计算输入特征并利用LEAPS估计该链路的PRR。

Figure 3. Online link quality estimation state diagram

图3. 采用在线估计链路质量状态图

4. ALE-CTP的实现

在TinyOS中实现了ALE-CTP，在设计ALE-CTP软件时，尽量保持与现有系统的兼容，并减少对相关组件的修改，下面介绍ALE-CTP的软件结构，链路估计器、转发引擎和路由引擎的设计方法。

4.1. ALE-CTP的结构

Figure 4. Structure of ALE-CTP

图4. ALE-CTP的结构

ALE-CTP由转发引擎、路由引擎和基于LEAPS的链路估计器三个组件构成，转发引擎的主要功能是发送和接收数据，路由引擎选择传输路径，向转发引擎提供下一跳目的节点的地址，链路估计器根据ASINR预测链路质量，为路由引擎提供已知链路的链路质量信息。图4显示了ALE-CTP的软件结构，按照TinyOS的图示规则，以矩形表示组件，虚线边框的矩形代表通用组件，以有向线段表示接口。与CTP相比，主要差别是采用LEAPS链路估计器替换了原有的4Bit链路估计器，由于转发引擎与路由引擎之间的接口没有改变，因此在图4中仅显示了转发引擎和路由引擎与链路估计器之间的接口。

在转发引擎与链路估计器之间仍采用接口Link-Estimator连接，在路由引擎与链路估计器之间保留用于信标收发的接口和用于链路估计的LinkEstimator接口，由于ALE-CTP仅利用物理层参数估计链路质量，因此取消了接口Comparebit。

Table 1. Modifications to the LinkEstimator interface

表1. 接口LinkEstimator的修改项目

增加的接口函数	减少的接口函数
UpdateRSS	txAck
LQChanged	txNoAck
	clearDLQ

对LinkEstimator接口的定义进行了修改，如表1所示，增加了2个函数，其中，命令函数UpdateRSS用于更新RSS，当节点接收到数据包时，由转发引擎调用该函数更新邻居表中与发送节点对应的RSS均值。LQChanged为事件函数，当链路质量发生明显变化时，由链路估计器触发路由引擎执行该函数，将广播信标的时间间隔设置为最小值，从而使邻居节点能够根据链路质量变化情况，及时调整传输路径。由于无需利用数据包传输估计链路质量，因此删除了LinkEstimator接口中有关数据包传输统计的函数。

4.2. 链路估计器设计

LEAPS链路估计器实现了图3所示的在线链路质量估计算法，定时采集INS样本，计算各已知链路的输入特征并采用LEAPS估计PRR，由于路由引擎根据ETX选择下一跳目的节点，因此，在计算出PRR估计值后，再按式(9)将PRR估计值$\widehat{P}$ 转换为ETX的估计值$\widehat{E}$ 。当ETX估计值发生明显改变时，将触发LQChanged事件，通过广播信标，使邻居节点及时更新链路质量。

$\widehat{E}=10/\widehat{P}$ (2)

链路估计器在信标和数据的接收过程中获取RSS，当接收到信标时，链路估计器分别读取RSS和当前节点与信标发送节点间链路的ETX，并更新邻居表。由于不需要统计信标的接收成功率，因此处理流程得到简化。如上所述，数据包的RSS由转发引擎读取，链路估计器通过执行LinkEstimator接口的函数UpdateRSS计算RSS均值并更新邻居表。

对链路估计器的邻居表结构进行了修改，增加了用于存储RSS、ASINR及其2次和3次方样本、输入人特征和PRR估计值的成员，不再使用与数据包和信标接收数量统计相关的成员。

4.3. 转发引擎与路由引擎的设计

对CTP的转发引擎和路由引擎只进行了少量修改，在转发引擎处理转发数据包的流程中增加了读取RSS和调用UpdateRSS更新邻居表的操作。在路由引擎中增加了对LQChanged事件的处理，同时，修改了信标发送方法，在信标广播间隔复位为最小值后的几个周期内增加了重发过程，以提高信标接收成功的概率。

5. 测试实验与分析

5.1. 实验方法

分别进行了链路估计模型和ALE-CTP的性能测试实验， 采用CC2530模块作为WSN节点，CC2530芯片集成了主控单元和射频电路，与IEEE 802.15.4标准兼容。在室内外多种条件下进行了实验，在模型测试实验中，分别采用1对1和n对1的网络拓扑，其中，n对1的网络又分为直线和星形两种结构，在ALE-CTP的测试实验中采用多跳树型网络。为测试存在干扰条件下链路估计模型的性能，分别使用2.4GHz 频段的多个信道进行实验，在住宅进行的实验中，节点之间存在障碍物(墙壁和楼板)，其他实验均为视距通信，实验条件如表2所示。

Table 2. Experimental conditions

表2. 实验条件

地点	信道	发送功率/dBm	发送周期/ms	距离/m
光电楼	11, 22, 26	−22~4.5	100~2000	5~30
地下停车场	26	−22, −8, 4.5	500	5~10
住宅	15, 18, 22	−22~4.5	50~2000	6
校园绿地	15	−20, −10, −4	200	40

在模型测试实验中，也使用了公共数据集due [22]，due包括在多种距离、功率、周期和包长度等条件下采集的数据，在一种距离条件下，一次实验的数据集中包含240余万条记录。

5.2. 模型测试

为了评估LEAPS的性能，分别进行了离线和在线测试实验。在离线测试实验中，使用自建的数据集和公共数据集训练和测试模型，图5显示了离线测试的结果。训练模型的数据集是在光电楼9楼采集，采集实验使用n对1直线布局的网络，训练集中包含22903条记录，测试数据集包括在光电楼、住宅和停车场采集的数据以及公共数据集due，图中分别使用后缀“1”和“n”表示1对1和n对1网络。图5也给出了现有模型4C [13]和LF^I [8]的测试结果，4C基于逻辑回归，采用最近获取的LQI和前一个窗口的PRR预测当前窗口的PRR，LFI采用wed作为逻辑回归模型的输入特征，wed由LQI和SNR按加权欧氏距离算法求得，为了减小输入参数的波动，分别采用卡尔曼滤波和EWMA对LQI和SNR进行处理。

从图5中看到，LEAPS预测值的平均绝对误差MAE明显小于4C和LFI，根据图1所示的相关性分析结果，输入特征与PRR采用相同的统计窗口时，具有最高的相关性，4C和LFI的输入特征与PRR的统计窗口大小均存在明显差别，导致预测误差较大。由于4C未对LQI进行滤波处理，因此，除了光电楼n对1数据集以外，4C的预测误差明显高于LFI。

使用不同数据集测试LEAPS的MAE略有差别，与训练集相比，测试集的MAE有所增加，不过最大值小于0.013，表明LEAPS具有较高的预测精度和较强的泛化能力。

Figure 5. Prediction errors across different datasets

图5. 不同数据集的预测误差

在线测试实验中，节点运行实现了LEAPS模型的测试程序，在线估计链路质量并将预测的PRR传送到上位机，同时，也将接收的数据包上传到上位机，从而可以对预测值和真实值进行比较。

(a) 高质量链路

(b) 中等质量链路

(c) 低质量链路

(d) 大幅波动的链路

Figure 6. Comparison of predicted values and actual values for different types of links

图6. 不同类型链路的预测值与真实值比较

实验结果显示(见图6和表3)，对于各种类型的链路，LEAPS均具有较高的在线预测精度，不同类型链路总体平均的MSE为0.011，MAE为0.075，由于高质量链路的RSS较大，且波动很小，因此高质量链路的预测误差最小，对于中等质量的链路，在采集INS样本期间的RSS与最近获取的RSS的差值较大，导致预测误差有所增大。如图6(d)所示，对于大幅波动的链路，LEAPS的预测值不仅与真实值的变化趋势较为一致，而且能够快速响应链路质量的明显改变，从而使路由引擎能够根据链路质量的变化及时调整传输路径。

Table 3. Online prediction errors for different types of links

表3. 不同类型链路的在线预测误差

	高质量链路	中等质量链路	低质量链路	大幅波动链路
MSE	0.00093	0.018	0.012	0.011
MAE	0.022	0.11	0.073	0.074

5.3. ALE-CTP的测试

ALE-CTP的测试实验在光电楼9楼进行，如图7所示，测试系统由被测的网络、上位机和干扰源组成，被测网络包括4个节点，节点1~3为传感器节点，节点4为汇聚节点(sink)，节点1按设定的周期采集数据，并将数据发送到sink，由于节点1与sink之间没有点对点传输路径，因此，需要通过节点2或节点3转发数据，sink收到数据之后，通过串口上传到上位机。节点2和节点3不采集数据，并且相互之间不存在视距传输路径。使用两个与被测网络相同的节点作为干扰源，干扰节点A和B分别放置在节点2和3的附近，并且，节点A和B之间以及两者各自与节点1之间不存在视距传输路径。节点A和B按相同的周期(150 s)交替产生干扰信号，分别使节点1与2之间的链路和节点1与3之间的链路质量出现明显下降。

Figure 7. Composition and deployment location of the testing system

图7. 测试系统组成与部署位置

分别在被测网络中运行基于ALE-CTP和CTP的测试程序，每次实验持续约20分钟，重复测试3次，实验结果如表4所示，其中，SSR (Successful Switch Ratio)为切换成功率，表示在交替干扰作用下，路由引擎切换路径的次数占干扰交替次数的比例，切换开始时间${\tau }_S$ 是从干扰发生时刻$t_0$ 到路由引擎开始更换路径的时刻$t_1$ 之间的时间，过渡时间${\tau }_T$ 是从$t_1$ 到完成更换路径的时刻$t_2$ 之间的时间，交付率(delivery ratio)为sink收到的包数量占发送节点发送的包数量的比例，时延是sink收到包的时刻与发送节点发送时刻之间的时间间隔。

Table 4. Performance comparison between ALE-CTP and CTP under controlled interference conditions

表4. 受控干扰作用下ALE-CTP与CTP的性能比较

	SSR/%	${\tau }_S$ /s	${\tau }_T$ /s	交付率/%	时延/ms
ALE-CTP	84.08	20.54	4.03	63.32	4.05
CTP	24.15	29.53	4.12	51.58	4.67

从表4可以看到，ALE-CTP的切换成功率明显高于CTP，表明ALE-CTP对链路质量的估计更为准确，并能够根据链路质量的变化及时更换传输路径。导致CTP切换成功率较低的主要原因是CTP的链路估计更新周期较长，对于转发节点，4Bit只能通过对信标计数估计链路质量，只有接收一定数量的信标才能更新链路估计，而发送信标的间隔按指数规律不断延长[1]，直到达到最大间隔512 s，当切换干扰节点时，在150 s的干扰作用期间，4Bit可能无法获取足够数量的信标，从而导致切换失败。由上文所述的在线链路质量估计算法可知，ALE-CTP的链路质量估计独立于传输过程，在长时间没有信标传输的情况下，也能按设定的周期估计链路质量，因此具有较高的切换成功率。

由于4Bit依赖于信标的接收，因此在能够成功切换的情况下，CTP完成切换的时间也明显长于ALE-CTP。基于更准确的链路估计，ALE-CTP的交付率比CTP提高了23%，时延减小了13%。

6. 结束语

针对本文提出了基于主动链路质量估计的汇聚树协议ALE-CTP，对CTP的链路质量估计方法做出改进，使链路质量估计独立于数据包和信标的传输过程，实验结果显示，与CTP相比，ALE-CTP具有更高的链路质量预测精度和更快的响应速度，因而提高了数据包的交付率，并减小了时延。未来将使用不同规模的网络在更多条件下进行测试，以便对ALE-CTP做出更加全面的评价。