面向結構健康監測的改進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，滿足了橋梁結構健康監測無線傳感器網絡同步數據采集高精度的需求，未來將會從低功耗方面對算法進行研究。