面向结构健康监测的改进FTSP算法设计

(西南科技大学 信息工程学院，四川 绵阳 621010)

桥梁在当今交通运输中起着重要作用。为了保障桥梁结构的安全性及稳定性，桥梁的结构健康监测是非常有必要的。由于桥梁结构健康监测大多采用分布式系统，因此，精确的时间同步技术和统一的时钟标准对分布式多传感器数据融合及分析非常重要。文献[1]和文献[2]描述了时间同步技术对于桥梁结构健康监测的必要性及精确性。除此之外，时间同步技术在环境监测[3-4]、医疗监护[5]和数据融合[6]等应用方面，同样起到了至关重要的作用。因此，时间同步技术在无线传感器网络许多应用领域均具有重要的研究意义。

近年来，针对不同领域的实际应用环境，国内外学者提出了许多时间同步算法及改进算法[7-12]，文献[7]提出了一种参考广播时间同步算法(Reference Broadcast Synchronization，RBS)，该算法采用只记录接收节点时间戳的方式，避免了发送节点引入的延迟误差，从而取得较高的时间同步精度，但存在计算量复杂等问题。文献[8]提出了一种双向成对时间同步算法TPSN(Timing-Sync Protocol for Sensor Network)，该算法采用分级双向的同步方式，减小通信过程中延迟因素，同样达到了较高的同步精度，但是算法本身没有对节点时钟漂移进行估计及补偿。文献[9]提出了一种泛洪时间同步算法(Flooding Time Synchronization Protocol,FTSP)，该算法采用单向广播消息及在MAC层标记时间戳的方式，减小了收、发节点通信过程中的延迟误差，整体性能优于RBS算法和TPSN算法。文献[10]和文献[11]都在CC2530平台上，采用SFD(Start of Frame Delimiter)硬件捕获机制对FTSP算法进行实现，试验结果表明单跳网络中平均同步误差分别为5.82 μs和5.613 μs，但是都没有对多跳网络进行同步测试，同时也没有考虑异常数据对算法同步精度及稳定性的影响问题。文献[12]针对异常数据对算法同步精度的影响，提出了有限加权最小二乘的FTSP算法，并在NS2平台上进行仿真试验，试验结果表明该算法有效提高了时间同步精度，但是不具有实际工程应用价值等问题。

本文针对上述文献[10]～文献[12]所存在的问题、桥梁结构健康监测无线数据同步采集的高精度需求问题，以及影响时间同步精度的几种延迟因素问题[13]，设计了一种基于SFD硬件捕获机制的改进FTSP时间同步算法。该算法通过硬件捕获的方式有效地降低了收、发节点通信过程中的延迟因素；采用了迭代加权最小二乘法对实时更新的观测数据对进行线性拟合，有效解决了采用传统最小二乘拟合时，异常数据点对时间同步精度及稳定性的影响，为后续的无线传感器网络桥梁结构健康监测无线数据同步采集提供了可靠保障。

1 经典FTSP时间同步算法

1.1 算法描述

经典的FTSP是基于Sender-Receiver的时间同步算法[9]，它是使用单向广播消息实现收、发节点之间的时间同步，最终目的是使整个网络实现时间同步。经典FTSP算法广播时间同步消息形式如图1所示。

图1 经典FTSP算法时间同步消息广播形式

经典FTSP算法是从发送节点的前导码字节Preamble开始无线广播时间同步消息，在SYNC字节发送完成后，在MAC层中给以后发送的每个字节标记时间戳。同理，接收节点在接收完SYNC字节后，同样给以后接收的每个字节标记上时间戳。这样，在收、发节点处便可获得多个时间戳。其中，CRC字节用于验证消息是否已损坏。当时间同步消息传输完成后，接收节点通过对捕获的时间戳进行处理，便可获得多个时间对(全局时间，本地时间)。最后采用最小二乘法对时钟漂移进行线性拟合估计及补偿，使得收、发节点时间达到同步。

1.2 线性最小二乘

FTSP时间同步算法需要些通过线性回归算法对节点的时钟漂移进行估计及补偿。由一元线性回归模型[14]，可得线性回归方程为

y=a+bx+ε

(1)

式中，a，b为方程的回归系数；a为截距；b为斜率。在FTSP算法中，a为时钟偏移(offset)；b为时钟漂移(skew)；ε为服从正态分布的回归值与测量值之间的随机误差。

将式(1)回归方程改写为向量的形式，表示如下。

Y=a+bx+ε=Xβ+ε

(2)

式中，β=(a,b)′为未知估计参数，X=(1,x)。

由式(2)可知，需要对未知参数β=(a,b)′进行估计。经典的FTSP算法采用的估计方法为普通最小二乘法(Ordinary Least Squares，OLS)[14,15]，该方法主要是通过最小化残差平方和的方式，拟合出数据的最佳匹配直线，从而实现对未知参数的估计。令残差平方和为目标函数Q(β)，则有

(3)

对式(3)进行求导，得到βOLS的估计方程为

(4)

(5)

(6)

(7)

2 改进FTSP时间同步算法设计

2.1 基于SFD捕获机制的改进FTSP算法描述

较之经典的FTSP算法，设计了一种基于SFD硬件捕获机制的改进FTSP算法，该算法采用了硬件捕获及迭代加权最小二乘估计的方式，减少了传输过程中延迟因素及异常数据点所带来的影响，从而有效地提高了时间同步精度及稳定性。改进FTSP算法广播时间同步消息形式如图2所示。

图2 SFD的FTSP算法时间同步消息广播形式

为实现时间同步，在一个给定信息中必须存在一个根节点(点对点单跳网络时,即为发送节点)，发送节点在遇到SFD字节时，触发SFD中断，同时在该字节的末尾标记一个发送时间戳TG，并将该时间戳插入到MAC层的时间同步消息中发送出去。同理，接收节点在接收消息时，遇到SFD字节时，同样触发SFD中断，并在该字节末尾标记一个本地接收时间戳TL。当一条时间同步消息发送完成时，可以获得一组时间对(TG,TL)。

之后，采用周期性广播消息的方式，获取更多的时间对，用来计算本地时钟和全局时钟的时钟偏移；对于计算所获得的若干个时钟偏移，采用迭代加权最小二乘法来估测接收节点的本地时钟漂移；根据拟合结果，对接收节点本地时钟进行补偿及调整，使得收、发节点时间达到同步。

2.2 迭代加权最小二乘

经典的FTSP算法，采用普通最小二乘法线性拟合估计的时钟漂移时，异常数据点会对拟合曲线造成较大的误差干扰，影响时间同步精度及其稳定性，因此，抑制或消除异常数据点对FTSP算法的影响显得非常必要。

为了能够有效地抑制异常数据点对FTSP 算法同步精度及稳定性的影响，对其进行了改进，采用了一种迭代加权最小二乘法(Iteratively Reweighted Least Squares，IRLS)[15]对时钟漂移回归系数进行估计。该方法主要思想是：根据回归残差的大小合理确定各数据点的权值ωi，对于残差值较大的数据点分配较小的权值，对于残差值较小的数据点分配较大的权值。权值合理确定完毕后，再建立加权最小二乘估计方程，最后通过反复迭代改进各权值的系数，直至达到试验理想结果。

令优化后的目标函数Q(β)为

Q(β)=∑ρ((Yi-Xiβ)2)=∑ωi(Yi-Xiβ)2=min

(8)

对式(8)目标函数进行求导，得到βIRLS的估计方程。

∑φ(ri)Xi=0

(9)

为了使IRLS估计具有稳健性，对残差进行标准化，可得

(10)

式中，s为残差尺度；med表示取中位数。

令残差权重ωi=φ(ri/s)/ri，将式(10)标准化残差ui代入式(9)估计方程中得

(11)

将式(11)向量化之后得

XTω·u=XTω·ε=0

(12)

将式(2)代入式(12)得

XTωY=XTωXβ

(13)

求得βIRLS为

βIRLS=(XTωX)-1XTωY

(14)

3 改进FTSP时间同步算法实现

为了对改进FTSP算法进行试验验证，对试验的硬件开发平台及软件程序进行了设计。

3.1 硬件平台

试验硬件平台主要采用的是TI公司生产的CC2530芯片，该芯片是一款符合ZigBee标准的片上系统(SoC)芯片，它具有优良的射频收发性能及增强型的8051 MCU。利用CC2530芯片作为本试验算法实现的解决方案，不但能够有效地降低节点的成本及体积，而且更具有实际应用价值。传感器收、发节点硬件平台结构框图如图3所示。

图3 传感器收、发节点硬件平台结构框图

由图3可知，传感器收、发节点硬件平台主要由CC2530芯片、传感器扩展板、电源底板、串口、显示屏和天线等组成。

3.2 软件设计

针对硬件平台的操作需要通过软件设计实现的需求，本试验使用IAR8.1工具作为开发环境对算法进行了软件设计。总体程序设计流程图如图4所示。

针对单跳及多跳网络同步过程中的根节点及非参考路由节点工作性质的不同，由图4可知，本实验将软件设计分为了广播和同步两个部分。

图4 软件设计程序流程图

广播部分程序设计描述为：① 对CC2530芯片、系统配置资源及时间同步消息包序列号seqnum进行初始化；② 启动定时器定时广播周期为30 s，定时时间到，则广播时间同步消息包(包含序列号seqnum和本地时间戳Tstamp)；③ 判断广播时间同步消息包是否损坏；④ 当判断时间同步消息包完整无损时，则表示成功广播一次时间同步消息包，同步包序列号seqnum加1，以此周期循环便可实现所提算法的广播部分。

同步部分程序设计描述为：① 当接收到广播时间同步消息包(收到时刻的序列号seqnum_R)时，判断接收的时间同步消息包是否为最新的序列号；② 当判断为最新序列号的同步消息包时，则计算本节点与广播节点的时钟偏移；③ 将计算得到的数值保存到实时更新的数据对(time,offset)数组中，当数组长度≥8时，采用迭代加权最小二乘法对实时更新的数据对进行线性拟合估计；④ 对拟合估计后的时钟漂移进行补偿，最终提高了本地节点与广播节点的时间同步精度及稳定性。

4 试验及结果分析

为了验证改进FTSP算法的有效性，对最小二乘法估计(OLS)和迭代加权最小二乘法估计(IRLS)分别在点对点单跳网络和多跳网络完成试验测试，试验环境和参数为：常温室内环境，传感器节点使用3.3 V直流供电，无线传输距离为1 m，单次试验时间为30 min。

4.1 点对点单跳网络同步试验

点对点单跳网络试验是节点时间同步性能的一个重要指标，为了验证改进FTSP算法的有效性，在上述试验环境下进行了多次试验，选取试验较好的一组数据，利用Matlab软件进行同步误差计算及绘图，得到图5所示的点对点单跳网络同步中，FTSP算法改进前及改进后的试验结果对比图。

图5 单跳网络FTSP算法改进前后试验结果对比图

由图5可知，5 min前，同步误差幅度波动较大，这里的同步误差原因是由传感器节点本身晶振的不稳定及算法补偿性能决定的。5 min后，同步误差收敛于稳定的范围内(图5中放大的小坐标图)，改进后的FTSP算法(IRLS估计)与改进前的FTSP算法(OLS估计)相比，同步误差有了很大的降低，且稳定性也有所提高。对图5试验数据进行统计分析，得到如表1所示的单跳网络FTSP算法改进前后误差对比统计表。

表1 单跳网络FTSP算法改进前后误差对比统计表

由表1分析可知，单跳网络同步0～5 min时，同步误差幅度较大，主要由两节点初始同步时晶振不稳定所造成。同步5 min之后，时钟偏移和时钟漂移开始共同补偿，误差开始收敛，并趋于稳定。此时可以看出单跳网络中，改进前FTSP算法(OLS估计)，最大同步误差为14 μs，最小同步误差为1 μs，平均同步误差为5.515 μs；而改进后的FTSP算法(IRLS估计)，最大同步误差为5 μs，最小同步误差为1 μs，平均同步误差为3.148 μs。改进后的FTSP算法与改进前的FTSP算法相比较，最大同步误差降低了64.29%，平均同步误差降低了42.92%，误差波动较平稳。表明了改进后的FTSP算法在单跳网络中，很好地抑制了异常数据点对同步精度及稳定性的影响。

4.2 多跳网络同步试验

由上述试验结果可知，改进的FTSP算法在点对点单跳网络中很好地抑制了异常数据对同步精度的影响，为了进一步验证改进FTSP算法在桥梁结构健康监测的多跳网络中时间同步效果及异常数据对同步精度的影响，根据桥梁结构形状，选取了4个传感器节点组成的3跳链状网络拓扑结构进行多次试验，选取试验较好的一组数据，利用Matlab软件进行同步误差计算及绘图，得到如图6所示的多跳网络同步中，FTSP算法改进前及改进后的试验结果对比图。

图6 多跳网络FTSP算法改进前后试验结果对比图

由图6可知，当同步误差收敛后，改进后的FTSP算法(IRLS估计)和改进前的FTSP算法(OLS估计)相比，同步误差同样有了很大的降低。对图6试验数据进行统计分析，得到如表2所示的多跳网络FTSP算法改进前后误差对比统计表。

表2 多跳网络FTSP算法改进前后误差对比统计表

由表2分析可知，3跳网络同步5 min之后，误差趋于稳定范围内。此时可以看出3跳网络中，改进前FTSP算法(OLS估计)，最大同步误差为31 μs，最小同步误差为1 μs，平均同步误差为12.668 μs；而改进后的FTSP算法(IRLS估计)，最大同步误差为18 μs，最小同步误差为1 μs，平均同步误差为9.167 μs。改进后的FTSP算法与改进前的FTSP算法相比较，最大同步误差降低了41.94%，平均同步误差降低了27.64%，误差波动较平稳。表明了改进后的FTSP算法在多跳网络中，同样很好地抑制了异常数据点对同步精度及稳定性的影响。

5 结束语

本文在采用最小二乘估计的经典FTSP算法上进行了改进，设计一种基于SFD硬件捕获机制的迭代加权最小二乘估计FTSP时间同步算法。该算法通过硬件捕获的方式有效地减少了发送、访问、传输和接收等延迟误差，以及通过迭代加权最小二乘估计有效地抑制了异常数据的干扰。并在同样的试验环境下，对改进前后的FTSP算法，分别在单跳网络和多跳网络中进行同步测试。

试验结果表明，在单跳网络和多跳网络中，与经典的FTSP算法相比，改进FTSP算法均明显地提高了时间同步精度及稳定性。正如文献[1]所描述的桥梁结构健康监测可以接受时间同步误差小于1 ms，满足了桥梁结构健康监测无线传感器网络同步数据采集高精度的需求，未来将会从低功耗方面对算法进行研究。