無線生理傳感器網(wǎng)絡(luò)TPSN算法的改進與分析＊

何曉梅，蔣邦英，齊華

（1.國家安全生產(chǎn)監(jiān)督管理總局通信信息中心，北京100013；2.西安工業(yè)大學(xué)）

引 言

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

1 TPSN算法描述

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

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

②同步階段。即實現(xiàn)所有節(jié)點的時間同步，第1級節(jié)點同步到根節(jié)點，第i級節(jié)點同步到第（i－1）級的一個節(jié)點，最終所有節(jié)點都同步到根節(jié)點，實現(xiàn)整個網(wǎng)絡(luò)的同步。TPSN算法示意圖如圖1所示。

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

圖1 TPSN算法示意圖

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

2 TPSN算法改進

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

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

由式（1）得:

為了求時間偏差和時間漂移，我們建立數(shù)學(xué)模型:

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

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

估計值與實際值的離差:

簡化后得:

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

3 仿真結(jié)果

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

圖2為時間同步的累積誤差。節(jié)點跳數(shù)最大為10，是同步一次的累積誤差?？梢钥闯觯琓PSN算法的累積誤差隨節(jié)點跳數(shù)的增加而增加得較快，TPSN－LS算法的累積誤差隨節(jié)點跳數(shù)的增加而增加得較緩慢；相同節(jié)點跳數(shù)時，TPSN－LS算法的累積誤差比TPSN算法要小得多，且節(jié)點跳數(shù)越大，兩算法的累積誤差的差值就越大。所以，TPSN－LS能夠很好地減小時間同步的累積誤差，從而顯著提高了時間同步的精度。

圖2 時間同步的累積誤差

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

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

結(jié) 語

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

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

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

［3］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，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］劉俊.無線傳感器網(wǎng)絡(luò)TPSN協(xié)議的改進［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］鄒樂強.最小二乘法原理及其簡單應(yīng)用［J］.河南工程技術(shù)學(xué)校，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網(wǎng)路模擬基礎(chǔ)與應(yīng)用［M］.北京:國防工業(yè)出版社，2008（5）:42－104.