無線生理傳感器網絡TPSN算法的改進與分析＊

何曉梅，蔣邦英，齊華

（1.國家安全生產監督管理總局通信信息中心，北京100013；2.西安工業大學）

引 言

無線生理傳感器網絡（Wireless Body Sensor Networks，WBSN）是基于無線傳感器網絡（Wireless Sensor Network，WSN）的。通過生理傳感器網絡節點采集生理信息，通過互聯網或無線電傳輸到醫院、用戶或家屬等檢測終端，以便用戶或醫生隨時監測用戶的病情，做到早發現、早治療［1－2］。但是由于網絡傳送時延的不確定性，不能以數據包到達的時間作為傳感器節點數據的時間，因此必須在傳感器節點集中維持一個與中心節點同步的時鐘，即時間同步［3］。無線生理傳感器網絡具有傳感器節點較少、網絡結構固定和能量有限的特點，TPSN（Timing－sync Protocol for Sensor Networks）算法較其他時間同步算法在同步誤差和同步精度上更適合于無線生理傳感器網絡的要求。

1 TPSN算法描述

TPSN算法［4］采用Client／Server時間同步的模式，與傳統的網絡時間協議NTP類似，其要達到的目的是在全網絡范圍內提供節點時間同步。該算法具有精度高的優點，比較適合于對同步精度要求較高的環境。TPSN協議采用層次型網絡結構［5］，首先將所有節點按照層次結構進行分層，通過下層節點與其上層節點的時間同步，最終實現所有節點與根節點的時間同步。假定每個傳感器都有唯一的標識號ID，節點間的無線通信鏈路是雙向的，通過雙向的消息交換實現節點間的時間同步。其同步過程包括兩個階段:

①層次發現與建立階段。在網絡部署后，根節點通過廣播“級別發現”分組，啟動層次發現階段，級別發現分組包含發送節點的ID和級別。每個節點賦予一個級別，根節點被賦予最高級別，設為第0級，根節點的鄰居節點收到根節點發送的分組后，將自己的級別設置為分組中的級別加1（即第1級），然后廣播新的級別發現分組。節點收到第i級節點的廣播分組后，記錄發送這個廣播分組的節點ID，設置自己的級別為（i＋1），廣播級別設置為（i＋1）的分組。這個過程持續下去，直到網絡內的每個節點都賦予一個級別。

②同步階段。即實現所有節點的時間同步，第1級節點同步到根節點，第i級節點同步到第（i－1）級的一個節點，最終所有節點都同步到根節點，實現整個網絡的同步。TPSN算法示意圖如圖1所示。

節點1屬于（i－1）級節點，節點2屬于i級節點；T1和T4表示節點2本地時鐘在不同時刻測量的時間，T2和T3表示節點1本地時鐘在不同時刻測量的時間；σ表示兩個節點之間的時間偏差，d表示消息的傳播延遲，假設來回消息的延遲是相同的。節點2為待同步節點，節點1為參照節點，節點2在T1時間向節點1發送同步請求分組，分組中包含節點2的級別和T1時間。節點1在T2時間收到分組，T2＝T1＋d＋σ，然后在T3時刻發送應答分組給節點2，分組中包含節點1的級別和T1、T2、T3信息。節點在T4時刻收到應答，T4＝T3＋d－σ，因此可以推導出下面公式:

圖1 TPSN算法示意圖

節點2利用公式（1）和（2）估算往返時延d和時間偏差σ，根據d和σ的值調整自己的時鐘為t2＝t1＋d＋σ（t1為節點1的本地時鐘，t2為節點2的時間），從而達到與參考節點1同步的目的。

2 TPSN算法改進

在TPSN算法中，節點的同步是通過逐級消息交換實現的，而消息的交換必然會引起消息傳遞延遲，這樣就會引起同步誤差。并且在多跳網絡中，誤差隨著跳數的增加而增大。算法優化是通過減小消息交換延遲帶來的誤差來提高時間同步的精度。由TPSN算法的描述可知:誤差由傳輸延遲和時間偏差兩部分組成［6］，傳輸延遲為確定性部分，時間偏差為不確定性部分，而且若時鐘頻率的不一致還會導致時間漂移；所以非確定性部分由時間偏差和時間漂移組成。為了減小不確定部分引起的同步誤差，提高同步精度，下面采用最小二乘法對TPSN算法進行優化。為了表達方便，將優化后的TPSN算法稱為TPSN－LS（Time－sync for Senor Network with Least Square Method）。

若每個節點的時鐘頻率一樣，那么只需考慮時間偏差，但是實際上每個節點的時鐘頻率并不一樣，所以必須考慮時間漂移。設傳輸延遲為d，時間偏差為σ，若實際接收時間為T2，令T2在節點2上對應的時間為T′2，那么:

由式（1）得:

為了求時間偏差和時間漂移，我們建立數學模型:

其中，α表示兩節點相應的時間漂移；σ表示時間偏差。令i為第i次同步，那么式（5）可整理為:可以看到這個方程有兩個參數α和σ。這里用最小二乘法來求相關參數。

令yi＝Ti2，xi＝利用最小二乘法［7－9］求未知參數α和σ的估計值和得與所有的（xi，yi）（i＝1，2，…，n）擬合程度最好，即同步效果最好。

估計值與實際值的離差:

簡化后得:

節點2可以利用計算出來的時間偏差值α和時間漂移σ來修正自身的本地時間，達到時間同步。這樣計算出來的時間偏差在較長一段時間可以保持不變，為使用周期同步降低能耗提供了一種可行方法。

3 仿真結果

為了檢驗改進后的TPSN算法即TPSN－LS的性能，通過網絡仿真工具NS－2［10］對算法進行了仿真實驗。根據無線生理傳感器網絡的拓撲結構特點，選擇了100個節點，節點的距離最大1.5m，最小0.1m，出于節約能量考慮，根節點選擇在人體的中間部位，其余節點根據人體生理參數測量位置隨機分布。主要從累積誤差和同步精度兩方面進行了實驗，并從TPSN－LS算法的節點數目和層次數目對算法進行了性能分析，實驗結果如圖2、圖3所示。

圖2為時間同步的累積誤差。節點跳數最大為10，是同步一次的累積誤差。可以看出，TPSN算法的累積誤差隨節點跳數的增加而增加得較快，TPSN－LS算法的累積誤差隨節點跳數的增加而增加得較緩慢；相同節點跳數時，TPSN－LS算法的累積誤差比TPSN算法要小得多，且節點跳數越大，兩算法的累積誤差的差值就越大。所以，TPSN－LS能夠很好地減小時間同步的累積誤差，從而顯著提高了時間同步的精度。

圖2 時間同步的累積誤差

改進前后算法的時間偏差比較如圖3所示。采用TPSN－LS算法進行時間同步時，多次同步的時間偏差波動較小，且在同步次數為20以后，其時間偏差比較接近10μs，幾乎沒有波動；然而TPSN算法的波動一直都比較大，且相鄰同步次數的時間偏差的差值較大。在周期同步中，同步周期越長，能量損耗越少，而同步誤差的波動直接影響同步周期的長短。由于TPSN－LS算法在同步次數達到20以后就幾乎保持不變，而TPSN算法始終大幅度波動，所以TPSN－LS算法的同步周期要遠大于TPSN算法。因此，在周期同步中，無論是考慮精度還是能耗問題，TPSN－LS算法都比TPSN算法更適合無線生理傳感器網絡。

圖3 改進前后算法的時間偏差比較

結 語

與TPSN算法相比，改進后的算法更適用于周期同步。TPSN－LS算法不僅減小了時間誤差，提高了同步精度，且在周期同步中有利于減少能耗，延長網絡壽命。

［1］孔佳薇.體域網BSN的研究進展及應用前景［J］.上海市浦東科技信息中心，2010（7）:737－753.

［2］Eirik N?ss－Ulseth，Novelda AS，Dag Ausen.Biomedical Wireless Sensor Network–phase II，2010.

［3］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005:185－266.

［4］Ganeriwal S，Kumar R，Srivastava M B.Timing－sync protocol for sensor networks［C］／／Proceedings of first ACM Conference on Embedded Networks Sensor System，Los Angeles，CA，USA，2003.

［5］Dai Hui，Han R.TSync:A Lightweight Bidirectional Time Synchronization Service for Wireless Sensor Networks［J］.Mobile Computing and Communications Review，2004，8（1）:125－139.

［6］劉俊.無線傳感器網絡TPSN協議的改進［EB／OL］.［2012－02－16］.http:／／www.paper.edu.cn／index.php／default／releasepaper／content／201101－355.

［7］Gao Q，Blow K J，Holding D J.Simple algorithm for improving time synchronization in wire less sensor networks［J］.Electronics Letters，2004，40（14）:889－891.

［8］鄒樂強.最小二乘法原理及其簡單應用［J］.河南工程技術學校，2010（23）:282－283.

［9］Tomas Schonhoff，Arthur Giondano.Detection and Estimation Theory and Its Applications［M］.Beijing:publishing house of electorica industry，2007:182－255.

［10］方路平，劉世華，陳盼，等.NS－2網路模擬基礎與應用［M］.北京:國防工業出版社，2008（5）:42－104.