面向結(jié)構健康監(jiān)測的改進FTSP算法設計

(西南科技大學 信息工程學院，四川 綿陽 621010)

橋梁在當今交通運輸中起著重要作用。為了保障橋梁結(jié)構的安全性及穩(wěn)定性，橋梁的結(jié)構健康監(jiān)測是非常有必要的。由于橋梁結(jié)構健康監(jiān)測大多采用分布式系統(tǒng)，因此，精確的時間同步技術和統(tǒng)一的時鐘標準對分布式多傳感器數(shù)據(jù)融合及分析非常重要。文獻[1]和文獻[2]描述了時間同步技術對于橋梁結(jié)構健康監(jiān)測的必要性及精確性。除此之外，時間同步技術在環(huán)境監(jiān)測[3-4]、醫(yī)療監(jiān)護[5]和數(shù)據(jù)融合[6]等應用方面，同樣起到了至關重要的作用。因此，時間同步技術在無線傳感器網(wǎng)絡許多應用領域均具有重要的研究意義。

近年來，針對不同領域的實際應用環(huán)境，國內(nèi)外學者提出了許多時間同步算法及改進算法[7-12]，文獻[7]提出了一種參考廣播時間同步算法(Reference Broadcast Synchronization，RBS)，該算法采用只記錄接收節(jié)點時間戳的方式，避免了發(fā)送節(jié)點引入的延遲誤差，從而取得較高的時間同步精度，但存在計算量復雜等問題。文獻[8]提出了一種雙向成對時間同步算法TPSN(Timing-Sync Protocol for Sensor Network)，該算法采用分級雙向的同步方式，減小通信過程中延遲因素，同樣達到了較高的同步精度，但是算法本身沒有對節(jié)點時鐘漂移進行估計及補償。文獻[9]提出了一種泛洪時間同步算法(Flooding Time Synchronization Protocol,FTSP)，該算法采用單向廣播消息及在MAC層標記時間戳的方式，減小了收、發(fā)節(jié)點通信過程中的延遲誤差，整體性能優(yōu)于RBS算法和TPSN算法。文獻[10]和文獻[11]都在CC2530平臺上，采用SFD(Start of Frame Delimiter)硬件捕獲機制對FTSP算法進行實現(xiàn)，試驗結(jié)果表明單跳網(wǎng)絡中平均同步誤差分別為5.82 μs和5.613 μs，但是都沒有對多跳網(wǎng)絡進行同步測試，同時也沒有考慮異常數(shù)據(jù)對算法同步精度及穩(wěn)定性的影響問題。文獻[12]針對異常數(shù)據(jù)對算法同步精度的影響，提出了有限加權最小二乘的FTSP算法，并在NS2平臺上進行仿真試驗，試驗結(jié)果表明該算法有效提高了時間同步精度，但是不具有實際工程應用價值等問題。

本文針對上述文獻[10]～文獻[12]所存在的問題、橋梁結(jié)構健康監(jiān)測無線數(shù)據(jù)同步采集的高精度需求問題，以及影響時間同步精度的幾種延遲因素問題[13]，設計了一種基于SFD硬件捕獲機制的改進FTSP時間同步算法。該算法通過硬件捕獲的方式有效地降低了收、發(fā)節(jié)點通信過程中的延遲因素；采用了迭代加權最小二乘法對實時更新的觀測數(shù)據(jù)對進行線性擬合，有效解決了采用傳統(tǒng)最小二乘擬合時，異常數(shù)據(jù)點對時間同步精度及穩(wěn)定性的影響，為后續(xù)的無線傳感器網(wǎng)絡橋梁結(jié)構健康監(jiān)測無線數(shù)據(jù)同步采集提供了可靠保障。

1 經(jīng)典FTSP時間同步算法

1.1 算法描述

經(jīng)典的FTSP是基于Sender-Receiver的時間同步算法[9]，它是使用單向廣播消息實現(xiàn)收、發(fā)節(jié)點之間的時間同步，最終目的是使整個網(wǎng)絡實現(xiàn)時間同步。經(jīng)典FTSP算法廣播時間同步消息形式如圖1所示。

圖1 經(jīng)典FTSP算法時間同步消息廣播形式

經(jīng)典FTSP算法是從發(fā)送節(jié)點的前導碼字節(jié)Preamble開始無線廣播時間同步消息，在SYNC字節(jié)發(fā)送完成后，在MAC層中給以后發(fā)送的每個字節(jié)標記時間戳。同理，接收節(jié)點在接收完SYNC字節(jié)后，同樣給以后接收的每個字節(jié)標記上時間戳。這樣，在收、發(fā)節(jié)點處便可獲得多個時間戳。其中，CRC字節(jié)用于驗證消息是否已損壞。當時間同步消息傳輸完成后，接收節(jié)點通過對捕獲的時間戳進行處理，便可獲得多個時間對(全局時間，本地時間)。最后采用最小二乘法對時鐘漂移進行線性擬合估計及補償，使得收、發(fā)節(jié)點時間達到同步。

1.2 線性最小二乘

FTSP時間同步算法需要些通過線性回歸算法對節(jié)點的時鐘漂移進行估計及補償。由一元線性回歸模型[14]，可得線性回歸方程為

y=a+bx+ε

(1)

式中，a，b為方程的回歸系數(shù)；a為截距；b為斜率。在FTSP算法中，a為時鐘偏移(offset)；b為時鐘漂移(skew)；ε為服從正態(tài)分布的回歸值與測量值之間的隨機誤差。

將式(1)回歸方程改寫為向量的形式，表示如下。

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

(2)

式中，β=(a,b)′為未知估計參數(shù)，X=(1,x)。

由式(2)可知，需要對未知參數(shù)β=(a,b)′進行估計。經(jīng)典的FTSP算法采用的估計方法為普通最小二乘法(Ordinary Least Squares，OLS)[14,15]，該方法主要是通過最小化殘差平方和的方式，擬合出數(shù)據(jù)的最佳匹配直線，從而實現(xiàn)對未知參數(shù)的估計。令殘差平方和為目標函數(shù)Q(β)，則有

(3)

對式(3)進行求導，得到βOLS的估計方程為

(4)

(5)

(6)

(7)

2 改進FTSP時間同步算法設計

2.1 基于SFD捕獲機制的改進FTSP算法描述

較之經(jīng)典的FTSP算法，設計了一種基于SFD硬件捕獲機制的改進FTSP算法，該算法采用了硬件捕獲及迭代加權最小二乘估計的方式，減少了傳輸過程中延遲因素及異常數(shù)據(jù)點所帶來的影響，從而有效地提高了時間同步精度及穩(wěn)定性。改進FTSP算法廣播時間同步消息形式如圖2所示。

圖2 SFD的FTSP算法時間同步消息廣播形式

為實現(xiàn)時間同步，在一個給定信息中必須存在一個根節(jié)點(點對點單跳網(wǎng)絡時,即為發(fā)送節(jié)點)，發(fā)送節(jié)點在遇到SFD字節(jié)時，觸發(fā)SFD中斷，同時在該字節(jié)的末尾標記一個發(fā)送時間戳TG，并將該時間戳插入到MAC層的時間同步消息中發(fā)送出去。同理，接收節(jié)點在接收消息時，遇到SFD字節(jié)時，同樣觸發(fā)SFD中斷，并在該字節(jié)末尾標記一個本地接收時間戳TL。當一條時間同步消息發(fā)送完成時，可以獲得一組時間對(TG,TL)。

之后，采用周期性廣播消息的方式，獲取更多的時間對，用來計算本地時鐘和全局時鐘的時鐘偏移；對于計算所獲得的若干個時鐘偏移，采用迭代加權最小二乘法來估測接收節(jié)點的本地時鐘漂移；根據(jù)擬合結(jié)果，對接收節(jié)點本地時鐘進行補償及調(diào)整，使得收、發(fā)節(jié)點時間達到同步。

2.2 迭代加權最小二乘

經(jīng)典的FTSP算法，采用普通最小二乘法線性擬合估計的時鐘漂移時，異常數(shù)據(jù)點會對擬合曲線造成較大的誤差干擾，影響時間同步精度及其穩(wěn)定性，因此，抑制或消除異常數(shù)據(jù)點對FTSP算法的影響顯得非常必要。

為了能夠有效地抑制異常數(shù)據(jù)點對FTSP 算法同步精度及穩(wěn)定性的影響，對其進行了改進，采用了一種迭代加權最小二乘法(Iteratively Reweighted Least Squares，IRLS)[15]對時鐘漂移回歸系數(shù)進行估計。該方法主要思想是：根據(jù)回歸殘差的大小合理確定各數(shù)據(jù)點的權值ωi，對于殘差值較大的數(shù)據(jù)點分配較小的權值，對于殘差值較小的數(shù)據(jù)點分配較大的權值。權值合理確定完畢后，再建立加權最小二乘估計方程，最后通過反復迭代改進各權值的系數(shù)，直至達到試驗理想結(jié)果。

令優(yōu)化后的目標函數(shù)Q(β)為

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

(8)

對式(8)目標函數(shù)進行求導，得到βIRLS的估計方程。

∑φ(ri)Xi=0

(9)

為了使IRLS估計具有穩(wěn)健性，對殘差進行標準化，可得

(10)

式中，s為殘差尺度；med表示取中位數(shù)。

令殘差權重ω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時間同步算法實現(xiàn)

為了對改進FTSP算法進行試驗驗證，對試驗的硬件開發(fā)平臺及軟件程序進行了設計。

3.1 硬件平臺

試驗硬件平臺主要采用的是TI公司生產(chǎn)的CC2530芯片，該芯片是一款符合ZigBee標準的片上系統(tǒng)(SoC)芯片，它具有優(yōu)良的射頻收發(fā)性能及增強型的8051 MCU。利用CC2530芯片作為本試驗算法實現(xiàn)的解決方案，不但能夠有效地降低節(jié)點的成本及體積，而且更具有實際應用價值。傳感器收、發(fā)節(jié)點硬件平臺結(jié)構框圖如圖3所示。

圖3 傳感器收、發(fā)節(jié)點硬件平臺結(jié)構框圖

由圖3可知，傳感器收、發(fā)節(jié)點硬件平臺主要由CC2530芯片、傳感器擴展板、電源底板、串口、顯示屏和天線等組成。

3.2 軟件設計

針對硬件平臺的操作需要通過軟件設計實現(xiàn)的需求，本試驗使用IAR8.1工具作為開發(fā)環(huán)境對算法進行了軟件設計?？傮w程序設計流程圖如圖4所示。

針對單跳及多跳網(wǎng)絡同步過程中的根節(jié)點及非參考路由節(jié)點工作性質(zhì)的不同，由圖4可知，本實驗將軟件設計分為了廣播和同步兩個部分。

圖4 軟件設計程序流程圖

廣播部分程序設計描述為：① 對CC2530芯片、系統(tǒng)配置資源及時間同步消息包序列號seqnum進行初始化；② 啟動定時器定時廣播周期為30 s，定時時間到，則廣播時間同步消息包(包含序列號seqnum和本地時間戳Tstamp)；③ 判斷廣播時間同步消息包是否損壞；④ 當判斷時間同步消息包完整無損時，則表示成功廣播一次時間同步消息包，同步包序列號seqnum加1，以此周期循環(huán)便可實現(xiàn)所提算法的廣播部分。

同步部分程序設計描述為：① 當接收到廣播時間同步消息包(收到時刻的序列號seqnum_R)時，判斷接收的時間同步消息包是否為最新的序列號；② 當判斷為最新序列號的同步消息包時，則計算本節(jié)點與廣播節(jié)點的時鐘偏移；③ 將計算得到的數(shù)值保存到實時更新的數(shù)據(jù)對(time,offset)數(shù)組中，當數(shù)組長度≥8時，采用迭代加權最小二乘法對實時更新的數(shù)據(jù)對進行線性擬合估計；④ 對擬合估計后的時鐘漂移進行補償，最終提高了本地節(jié)點與廣播節(jié)點的時間同步精度及穩(wěn)定性。

4 試驗及結(jié)果分析

為了驗證改進FTSP算法的有效性，對最小二乘法估計(OLS)和迭代加權最小二乘法估計(IRLS)分別在點對點單跳網(wǎng)絡和多跳網(wǎng)絡完成試驗測試，試驗環(huán)境和參數(shù)為：常溫室內(nèi)環(huán)境，傳感器節(jié)點使用3.3 V直流供電，無線傳輸距離為1 m，單次試驗時間為30 min。

4.1 點對點單跳網(wǎng)絡同步試驗

點對點單跳網(wǎng)絡試驗是節(jié)點時間同步性能的一個重要指標，為了驗證改進FTSP算法的有效性，在上述試驗環(huán)境下進行了多次試驗，選取試驗較好的一組數(shù)據(jù)，利用Matlab軟件進行同步誤差計算及繪圖，得到圖5所示的點對點單跳網(wǎng)絡同步中，F(xiàn)TSP算法改進前及改進后的試驗結(jié)果對比圖。

圖5 單跳網(wǎng)絡FTSP算法改進前后試驗結(jié)果對比圖

由圖5可知，5 min前，同步誤差幅度波動較大，這里的同步誤差原因是由傳感器節(jié)點本身晶振的不穩(wěn)定及算法補償性能決定的。5 min后，同步誤差收斂于穩(wěn)定的范圍內(nèi)(圖5中放大的小坐標圖)，改進后的FTSP算法(IRLS估計)與改進前的FTSP算法(OLS估計)相比，同步誤差有了很大的降低，且穩(wěn)定性也有所提高。對圖5試驗數(shù)據(jù)進行統(tǒng)計分析，得到如表1所示的單跳網(wǎng)絡FTSP算法改進前后誤差對比統(tǒng)計表。

表1 單跳網(wǎng)絡FTSP算法改進前后誤差對比統(tǒng)計表

由表1分析可知，單跳網(wǎng)絡同步0～5 min時，同步誤差幅度較大，主要由兩節(jié)點初始同步時晶振不穩(wěn)定所造成。同步5 min之后，時鐘偏移和時鐘漂移開始共同補償，誤差開始收斂，并趨于穩(wěn)定。此時可以看出單跳網(wǎng)絡中，改進前FTSP算法(OLS估計)，最大同步誤差為14 μs，最小同步誤差為1 μs，平均同步誤差為5.515 μs；而改進后的FTSP算法(IRLS估計)，最大同步誤差為5 μs，最小同步誤差為1 μs，平均同步誤差為3.148 μs。改進后的FTSP算法與改進前的FTSP算法相比較，最大同步誤差降低了64.29%，平均同步誤差降低了42.92%，誤差波動較平穩(wěn)。表明了改進后的FTSP算法在單跳網(wǎng)絡中，很好地抑制了異常數(shù)據(jù)點對同步精度及穩(wěn)定性的影響。

4.2 多跳網(wǎng)絡同步試驗

由上述試驗結(jié)果可知，改進的FTSP算法在點對點單跳網(wǎng)絡中很好地抑制了異常數(shù)據(jù)對同步精度的影響，為了進一步驗證改進FTSP算法在橋梁結(jié)構健康監(jiān)測的多跳網(wǎng)絡中時間同步效果及異常數(shù)據(jù)對同步精度的影響，根據(jù)橋梁結(jié)構形狀，選取了4個傳感器節(jié)點組成的3跳鏈狀網(wǎng)絡拓撲結(jié)構進行多次試驗，選取試驗較好的一組數(shù)據(jù)，利用Matlab軟件進行同步誤差計算及繪圖，得到如圖6所示的多跳網(wǎng)絡同步中，F(xiàn)TSP算法改進前及改進后的試驗結(jié)果對比圖。

圖6 多跳網(wǎng)絡FTSP算法改進前后試驗結(jié)果對比圖

由圖6可知，當同步誤差收斂后，改進后的FTSP算法(IRLS估計)和改進前的FTSP算法(OLS估計)相比，同步誤差同樣有了很大的降低。對圖6試驗數(shù)據(jù)進行統(tǒng)計分析，得到如表2所示的多跳網(wǎng)絡FTSP算法改進前后誤差對比統(tǒng)計表。

表2 多跳網(wǎng)絡FTSP算法改進前后誤差對比統(tǒng)計表

由表2分析可知，3跳網(wǎng)絡同步5 min之后，誤差趨于穩(wěn)定范圍內(nèi)。此時可以看出3跳網(wǎng)絡中，改進前FTSP算法(OLS估計)，最大同步誤差為31 μs，最小同步誤差為1 μs，平均同步誤差為12.668 μs；而改進后的FTSP算法(IRLS估計)，最大同步誤差為18 μs，最小同步誤差為1 μs，平均同步誤差為9.167 μs。改進后的FTSP算法與改進前的FTSP算法相比較，最大同步誤差降低了41.94%，平均同步誤差降低了27.64%，誤差波動較平穩(wěn)。表明了改進后的FTSP算法在多跳網(wǎng)絡中，同樣很好地抑制了異常數(shù)據(jù)點對同步精度及穩(wěn)定性的影響。

5 結(jié)束語

本文在采用最小二乘估計的經(jīng)典FTSP算法上進行了改進，設計一種基于SFD硬件捕獲機制的迭代加權最小二乘估計FTSP時間同步算法。該算法通過硬件捕獲的方式有效地減少了發(fā)送、訪問、傳輸和接收等延遲誤差，以及通過迭代加權最小二乘估計有效地抑制了異常數(shù)據(jù)的干擾。并在同樣的試驗環(huán)境下，對改進前后的FTSP算法，分別在單跳網(wǎng)絡和多跳網(wǎng)絡中進行同步測試。

試驗結(jié)果表明，在單跳網(wǎng)絡和多跳網(wǎng)絡中，與經(jīng)典的FTSP算法相比，改進FTSP算法均明顯地提高了時間同步精度及穩(wěn)定性。正如文獻[1]所描述的橋梁結(jié)構健康監(jiān)測可以接受時間同步誤差小于1 ms，滿足了橋梁結(jié)構健康監(jiān)測無線傳感器網(wǎng)絡同步數(shù)據(jù)采集高精度的需求，未來將會從低功耗方面對算法進行研究。