基于TPSN和DMTS的低能耗時間同步算法

何秀春 ， 張金榜 ， 劉 軍 ， 林 語

（1. 武警工程大學 研究生管理大隊，陜西 西安 710086；2. 武警警官學院 信息工程系，四川 成都 610213；3.武警工程大學 信息工程系，陜西 西安 710086）

基于TPSN和DMTS的低能耗時間同步算法

何秀春1， 張金榜2， 劉 軍3， 林 語1

（1. 武警工程大學 研究生管理大隊，陜西 西安 710086；2. 武警警官學院 信息工程系，四川 成都 610213；3.武警工程大學 信息工程系，陜西 西安 710086）

針對現有時間同步算法不能滿足WBSNs能量受限的問題，提出了一種基于TPSN和DMTS的低能耗時間同步算法。該算法在保證一定同步精度的前提下，通過減少信息交換次數來達到低能耗的要求。實驗表明，TPTS算法比TPSN和DMTS減少了開銷，降低了能量消耗，滿足了低能耗的要求。

TPSN；DMTS；低能耗；時間同步算法

無線軀體傳感器網絡（WBSNs，Wireless Body Sensor Networks）是由多個感知節點組成的無結構、自組織網絡。節點的休眠、喚醒和節點間的協同工作都需要時間同步，節點間的時間同步對于整個網絡來說至關重要。目前典型的時間同步算法有RBS[1]（Reference Broadcast Synchronization）、TPSN[2]（Timing-sync Protocol for Sensor Networks）、DMTS[3]（Delay Measurement Time Synchronization）、FTSP[4]（Flooding Time Synchronization Protocol）、LTS(Lightweight Time Synchronization)[5]、Tiny-sync和Mini-sync[6]6種類型，而現有的時間同步算法是針對WSNs而設計的，對于節點能量更有限的WBSNs，雖然適用，但不能很好地滿足WBSNs低能耗的要求。因此，通過分析研究現有的同步算法，提出了一種基于TPSN和DMTS的低能耗時間同步算法。

1 理論基礎

1.1 TPSN算法

TPSN是由Saurabh Ganeriwal等人于2003年提出的基于成對雙向消息傳送的發送者與接收者之間的全網時間同步。具體描述如下：同步過程分分層和同步兩個階段。分層階段是一個網絡拓撲的建立過程。首先確定根節點及等級，此節點是全網的時鐘參考節點，等級為0級，根節點廣播包含有自身等級信息的數據包，相鄰節點收到該數據包后，確定自身等級為1級，然后1級節點繼續廣播帶有自身等級信息的數據包，以此類推，i級節點廣播帶有自身等級信息的數據包，其相鄰節點收到后確定自身等級為i+1，直到網絡中所有節點都有自身的等級。一旦節點被定級，它將拒收分級數據包。同步階段從根節點開始，與其下一級節點進行成對同步，然后i級節點與i-1級節點同步，直到每個節點都與根節點同步。成對同步的過程如圖1示。

圖1 成對同步過程Fig. 1 Twin synchronization process

節點i在本地時刻T1時向節點j發送同步請求，該請求中包含節點i的等級和T1，節點j在本地時刻T2時收到請求并在T3時發送同步應答，該應答包含T2和T3，節點i于本地時刻T4收到應答信息，根據時間關系可列出方程:

其中d是消息傳輸遲延，Δ為時鐘偏差，經過計算得：

節點i計算出時間偏差Δ，從而調整自己的時鐘，達到同步。

1.2 DMTS(Delay Measurement Time Synchronization)

DMTS 是由Ping S于2003年提出的基于基準節點廣播的發送者與接收者之間的全網時間同步。具體描述為：選擇一個基準節點，廣播包含時間的同步消息，接收節點根據時間信息估算消息傳輸時延，調整自身本地時間為同步消息所帶時間加傳輸時延，消息傳輸時延（td）等于發射時延（ts）加接收處理時間（tv），發射時延為發射前導碼和起始符所需的時間，等于發射位數（n）乘以發射一位所需的時間（t），接收處理時間等于接收處理完成時間（ t2）減消息到達時間（t1），所以得出公式：

將DMTS應用到多跳網絡中還采用與TPSN相同的分層方法進行同步，只不過將每一層看作一個單跳網絡，基準節點依次定在0級，1級，2級，…，n級，逐步實現全網同步。為避免廣播消息回傳，每一個節點只接收上一層等級比自己低的節點廣播。

1.3 TPSN和DMTS性能分析

分析對比TPSN和DMTS算法，DMTS的同步精度略低于RBS，而TPSN的同步精度近似于RBS的兩倍，即TPSN的同步精度幾乎是DMTS的2倍。雖然TPSN的能耗高于DMTS，但是DMTS是以犧牲同步精度換取低能耗，若要保持同一精度，則DMTS的能耗將遠遠高于TPSN[7]。

2 TPTS算法

TPTS算法分為兩個階段。第一階段為層次建立階段。首先確定根節點及分層，此節點是全網的時鐘參考節點，賦予層次號0，根節點廣播包有自身層次號的數據包，相鄰節點收到該數據包后，確定自身層次號為1，然后1層節點含繼續廣播帶有自身層次號的數據包，以此類推，i層節點廣播帶有自身層次號的數據包，其相鄰節點收到后確定自身層次為i+1，直到網絡中所有節點都有自身的層次。已確定層次的節點拒收其他數據包。至此，全網建立起一個層次結構。

第二階段為同步階段。同步階段又分為層間同步和層內同步。層間同步采用成對雙向消息傳遞機制，層內同步采用基準節點單向廣播機制，每層節點中隨機選出一個基準節點，層內結構形成主從關系。如圖2所示。

圖2 層內結構圖Fig. 2 Layer structure

除根節點外，每層基準節點按層次號依次向上層發送同步請求。1層基準節點向根節點發送同步請求，兩節點間采用成對雙向消息同步算法TPSN進行同步，1層基準節點計算出節點之間時間偏移和傳播時延，調整本地時鐘，與根節點達到同步。然后1層基準節點在層內廣播一個同步消息，層內其他從節點收到消息后估計消息時延，調整本地時鐘。至此實現了一層節點的同步。同步過程中設立一個同步計時器，用于記錄層間同步時間T。間隔時間t（T≤t≤2T）后，2層基準節點向1層基準節點請求同步，t的選取保證每層基準節點已與根節點達到同步。以下各層按照層間和層內的同步方法實現全網同步。

該算法結合單向廣播和成對雙向消息傳遞進行橫向和縱向時間同步，橫向指層內廣播，縱向指層間成對，橫縱交錯，實現了所有節點的同步。

3 實驗結果及分析

為驗證TPTS的性能，采用網絡仿真工具NS-2（Network Simulator version 2）進行實驗仿真，在同一精度的前提下衡量TPTS算法在能耗方面的改進。仿真環境為50×50 的正方形區域，隨機分布30個節點，節點間無線通信距離為100 m。

圖3 TPTS算法與TPSN算法消息開銷比較Fig. 3 TPTS algorithm and TPSN algorithm message overhead comparison

仿真結果如圖3所示。TPTS算法比TPSN算法的同步開銷要小的多，并隨節點數量的增加，點每個節的相鄰節點數目增多，其同步開銷的差別越大。這是因為TPTS算法中每層只有一個基準節點，層間同步過程需2個消息交換的開銷，而基準節點與本層的其他節點只需要1個消息開銷，消息開銷隨節點數目的增加變化較平緩；而TPSN算法則需要2倍于節點數目的開銷，隨著節點數目的增加，消息交換的次數也極具增加，同時產生了大量的冗余信息包，造成了消息開銷的快速增長。顯然，TPTS算法明顯減少了同步階段所需的消息交換次數，降低了同步過程所需的通信開銷。

由1.3可知：在保證同一時間同步精度的情況下，DMTS的能耗比TPSN高得多。因此，可以得出結論如下：在保證同一精度前提下，TPTS的能耗小于TPSN和DMTS。

4 結 論

基于TPSN和DMTS算法的低能耗時間同步算法，在繼承TPSN和DMTS算法性能優勢的基礎上，在保證一定精度的前提下，通過減少信息交換次數來實現低能耗的要求。實驗結果表明，TPTS與TPSN和DMTS相比，減少了開銷，降低了能量消耗，更適用于WBSNs。

[1] Jeremy E,Lewis G,DeborahE.Fine-Grained Network Time Synchronization Using Reference Broadcasts [C]//In Proc.of the Fifth Symposium on Operating Systems Design and Implementation, Boston, MA, 2002: 147-163.

[2] Saurabh G,Ram K,ManiS.Timing-Sync Protocol for Sensor Networks[C]//In Proc.ACM SenSys, Los Angeles,CA,2003.

[3] Ping S. Delay measurement time synchronization for wireless sensor networks[R]. Intel Research Berkeley lab, 2003.

[4] Maroti M, Kusy B, Simon G, et al. The flooding time synchronization protocol[C]// In Proc.of the 2nd ACM Conference on Embedded Networked Sensor Systems(SenSys), Baltimore, Mariland, 2004: 39-49.

[5] Jana V G, Jan R .Lightweight Time Synchronization for Sensor Networks[C]//In Proc. of 2nd ACM Int'l.] Conference on Wireless Sensor Networks and Apps.San Diego,CA, Sept. 2003.

[6] Sichitiu Mihail L, Veerarittipahan Chanchai. Simple, Accurate Time Synchronization for Wireless Sensor Networks[C]//In Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC2003), New Orleans, LA, March 2003:1266-1273.

[7] 楊穎. 訓練場士兵生理狀況監測系統研究與設計[D].西安:武警工程大學, 2012.

The time synchornization arithmetic of lower power based on TPSN and DMTS

HE Xiu-chun1, ZHANG Jin-bang2, LIU Jun3, LIN Yu1
（1. Graduate Management Team, Engineering University of CAPF, Xi’an 710086, China;2. Department of Information Engineering,Officers College of CAPF, Chengdu 610213, China;3. Department of Information Engineering, Engineering University of CAPF, Xi’an 710086, China）

A lower power time synchronization arithemetic based on TPSN and DMTS, which aiming at the issues that the existing time synchronization can not meet with the problem that the poser is limited in Wireless Body Sensor Networks. This arithmetic realizes the purpose of lower power through reducing the degree of communication, when the precision is determinate. The experimentation shows that the TPSN is lower spending and lower power than TPSN and DMTS，which has meet with the lower power intention.

Timing-sync Protocol for Sensor Networks; Delay Measurement Time Synchronization; low power; time synchornization arithmetic

TN96

A

1674-6236(2014)03-0021-02

2013–06–20 稿件編號：201306128

何秀春(1987—)，女，四川南充人，碩士研究生。研究方向：無線數據通信、電子技術應用 。