何秀春 ， 張金榜 ， 劉 軍 ， 林 語(yǔ)

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

基于TPSN和DMTS的低能耗時(shí)間同步算法

何秀春1， 張金榜2， 劉 軍3， 林 語(yǔ)1

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

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

TPSN；DMTS；低能耗；時(shí)間同步算法

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

1 理論基礎(chǔ)

1.1 TPSN算法

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

圖1 成對(duì)同步過(guò)程Fig. 1 Twin synchronization process

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

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

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

1.2 DMTS(Delay Measurement Time Synchronization)

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

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

1.3 TPSN和DMTS性能分析

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

2 TPTS算法

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

圖3 TPTS算法與TPSN算法消息開(kāi)銷(xiāo)比較Fig. 3 TPTS algorithm and TPSN algorithm message overhead comparison

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

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

4 結(jié) 論

基于TPSN和DMTS算法的低能耗時(shí)間同步算法，在繼承TPSN和DMTS算法性能優(yōu)勢(shì)的基礎(chǔ)上，在保證一定精度的前提下，通過(guò)減少信息交換次數(shù)來(lái)實(shí)現(xiàn)低能耗的要求。實(shí)驗(yàn)結(jié)果表明，TPTS與TPSN和DMTS相比，減少了開(kāi)銷(xiāo)，降低了能量消耗，更適用于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)練場(chǎng)士兵生理狀況監(jiān)測(cè)系統(tǒng)研究與設(shè)計(jì)[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 稿件編號(hào)：201306128

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