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

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

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

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

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

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

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

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

無線軀體傳感器網(wǎng)絡(luò)（WBSNs，Wireless Body Sensor Networks）是由多個感知節(jié)點組成的無結(jié)構(gòu)、自組織網(wǎng)絡(luò)。節(jié)點的休眠、喚醒和節(jié)點間的協(xié)同工作都需要時間同步，節(jié)點間的時間同步對于整個網(wǎng)絡(luò)來說至關(guān)重要。目前典型的時間同步算法有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種類型，而現(xiàn)有的時間同步算法是針對WSNs而設(shè)計的，對于節(jié)點能量更有限的WBSNs，雖然適用，但不能很好地滿足WBSNs低能耗的要求。因此，通過分析研究現(xiàn)有的同步算法，提出了一種基于TPSN和DMTS的低能耗時間同步算法。

1 理論基礎(chǔ)

1.1 TPSN算法

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

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

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

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

節(jié)點i計算出時間偏差Δ，從而調(diào)整自己的時鐘，達到同步。

1.2 DMTS(Delay Measurement Time Synchronization)

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

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

1.3 TPSN和DMTS性能分析

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

2 TPTS算法

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

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

圖2 層內(nèi)結(jié)構(gòu)圖Fig. 2 Layer structure

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

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

3 實驗結(jié)果及分析

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

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

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

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

4 結(jié) 論

基于TPSN和DMTS算法的低能耗時間同步算法，在繼承TPSN和DMTS算法性能優(yōu)勢的基礎(chǔ)上，在保證一定精度的前提下，通過減少信息交換次數(shù)來實現(xiàn)低能耗的要求。實驗結(jié)果表明，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] 楊穎. 訓(xùn)練場士兵生理狀況監(jiān)測系統(tǒng)研究與設(shè)計[D].西安:武警工程大學(xué), 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—)，女，四川南充人，碩士研究生。研究方向：無線數(shù)據(jù)通信、電子技術(shù)應(yīng)用 。