唐　波，吳爽爽，彭　力

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122）

一種基于幀間信息差的改進(jìn)TPSN算法*

唐波*，吳爽爽，彭力

（江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無錫214122）

在無線傳感器網(wǎng)絡(luò)中，TPSN時(shí)間同步算法作為一種基于成對(duì)的雙向同步算法，取得了良好的時(shí)間同步精度，但是同步能耗大。根據(jù)TPSN算法中傳感器節(jié)點(diǎn)收到的數(shù)據(jù)在時(shí)間上和空間上的相關(guān)性，通過壓縮數(shù)據(jù)來減少數(shù)據(jù)流量，提出了一種基于幀間信息差的改進(jìn)TPSN算法。在改進(jìn)TPSN算法中傳感器節(jié)點(diǎn)首次時(shí)間同步時(shí)存儲(chǔ)同步幀，之后的同步幀均采用與前一幀的信息差，壓縮了同步幀的數(shù)據(jù)量，減少了報(bào)文開銷，從而降低了同步能耗。仿真結(jié)果表明，改進(jìn)TPSN算法有效地降低了時(shí)間同步的能耗，同時(shí)保持了TPSN算法的精度。

無線傳感器網(wǎng)絡(luò)；時(shí)間同步；數(shù)據(jù)壓縮；低功耗

EEACC：7230doi：10.3969/j.issn.1004-1699.2015.12.017

隨著集成、控制、信息處理、通信等技術(shù)的發(fā)展，無線傳感網(wǎng)絡(luò)的應(yīng)用變得越來越常見了，在軍隊(duì)、醫(yī)療、環(huán)境監(jiān)測甚至于辦公、家用方面都扮演了非常重要的角色。無線傳感器網(wǎng)絡(luò)從發(fā)展至今，相關(guān)研究已經(jīng)進(jìn)行了很長一段時(shí)間。無線傳感器網(wǎng)絡(luò)實(shí)際上是一種分布式系統(tǒng)，網(wǎng)絡(luò)中的節(jié)點(diǎn)采用無線通信方式，同時(shí)具有以下特性：節(jié)點(diǎn)規(guī)模有限，數(shù)據(jù)存儲(chǔ)空間有限，能量存儲(chǔ)較低和運(yùn)算能力較差［1-4］。因此，無線傳感器網(wǎng)絡(luò)系統(tǒng)要達(dá)成某個(gè)功能，必須要所有的傳感器節(jié)點(diǎn)相互配合。無線傳感器網(wǎng)絡(luò)中許多的應(yīng)用實(shí)例要求，所有的傳感器節(jié)點(diǎn)都同步到全局時(shí)鐘上，如數(shù)據(jù)采集時(shí)間標(biāo)記、協(xié)同休眠、定位、數(shù)據(jù)融合等［5］。

在無線傳感器網(wǎng)絡(luò)時(shí)間同步算法中，從算法傳遞報(bào)文的方式來看，TPSN（Timing-sync Protocol for Sensor Networks）協(xié)議是基于成對(duì)（Pair-Wise）的雙向同步算法。該算法消除了發(fā)送、訪問和接收時(shí)間的影響，并且計(jì)算復(fù)雜度低，精度高，被廣泛應(yīng)用在無線傳感器網(wǎng)絡(luò)的實(shí)例中，但是這種成對(duì)雙向同步報(bào)文開銷多，系統(tǒng)的能耗較大。Kyoung-lae Noh提出的PBS［6］（Pairwise Broadcast Synchronization）算法、劉慶龍?zhí)岢龅腅ETS［5］（Energy-Efficient Time Synchronization）時(shí)間同步算法、陶志勇提出的基于等級(jí)層次結(jié)構(gòu)的改進(jìn)TPSN算法［7］都是在TPSN算法的基礎(chǔ)上，通過減少報(bào)文交換次數(shù)，從而降低時(shí)間同步算法的能耗。但是上述三種算法利用分簇結(jié)合廣播消息的方式改變了TPSN算法的層次型網(wǎng)絡(luò)結(jié)構(gòu)，增加了網(wǎng)絡(luò)層次發(fā)現(xiàn)階段的復(fù)雜度，算法部署實(shí)施困難。

在無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)收到的數(shù)據(jù)在時(shí)間上的相關(guān)性和相鄰傳感器節(jié)點(diǎn)收到的數(shù)據(jù)在空間上的相關(guān)性［8］，給TPSN算法在數(shù)據(jù)收發(fā)方面進(jìn)行數(shù)據(jù)壓縮提供了可能。幾種常用的無損數(shù)據(jù)壓縮方法［9］如游程長度編碼、哈夫曼編碼、基于字典壓縮算法等雖然取得良好的壓縮效果，但是就TPSN算法而言復(fù)雜度大。

本文提出了一種基于幀間信息差的改進(jìn)TPSN算法，減少數(shù)據(jù)量的方法簡單。在成對(duì)雙向報(bào)文交互中，每次傳遞幀間信息差實(shí)現(xiàn)數(shù)據(jù)壓縮，從而降低報(bào)文開銷，達(dá)到降低系統(tǒng)能耗的目的。

1　TPSN算法介紹

TPSN算法利用了層次型網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)具有唯一的標(biāo)識(shí)號(hào)，節(jié)點(diǎn)間可進(jìn)行雙向無線通信，并且通過雙向的消息交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。在TPSN算法中網(wǎng)絡(luò)具有一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)的時(shí)鐘作為傳感器網(wǎng)絡(luò)內(nèi)部時(shí)間同步的基準(zhǔn)時(shí)間源。TPSN算法分為兩個(gè)階段，層次發(fā)現(xiàn)階段和同步階段。在層次發(fā)現(xiàn)階段，TPSN協(xié)議將所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行分級(jí)，根節(jié)點(diǎn)的級(jí)別是0，在根節(jié)點(diǎn)廣播域內(nèi)的鄰居節(jié)點(diǎn)收到根節(jié)點(diǎn)發(fā)送的分組后，將自己的級(jí)別設(shè)置1級(jí)。依此類推，直到每個(gè)節(jié)點(diǎn)都有自己的級(jí)別。在同步階段，根節(jié)點(diǎn)廣播時(shí)間同步分組，第1級(jí)節(jié)點(diǎn)收到分組后，各自隨機(jī)等待一段時(shí)間，然后與根節(jié)點(diǎn)交換消息，從而同步到根節(jié)點(diǎn)。依此類推，直到所有節(jié)點(diǎn)完成同步，都同步到根節(jié)點(diǎn)。

圖1　RTPSN算法中相鄰級(jí)別節(jié)點(diǎn)同步過程

如圖1所示，節(jié)點(diǎn)A為第i級(jí)，節(jié)點(diǎn)B為第i+1級(jí)，t1和t4代表節(jié)點(diǎn)B的本地時(shí)鐘在不同時(shí)刻測量的時(shí)間，t2和t3代表節(jié)點(diǎn)A本地時(shí)鐘在不同時(shí)刻測量的時(shí)間，Δ代表兩個(gè)節(jié)點(diǎn)之間的時(shí)間偏差，d代表消息傳播時(shí)延，設(shè)請(qǐng)求消息和應(yīng)答消息的傳播時(shí)延沒有差異。

節(jié)點(diǎn)B在t1時(shí)刻發(fā)送同步請(qǐng)求給節(jié)點(diǎn)，同步幀包含了B的級(jí)別和t1，節(jié)點(diǎn)A在t2時(shí)刻收到同步幀，則有t2=t1+d+Δ。節(jié)點(diǎn)A在t3時(shí)刻返回同步幀給B，同步幀中包含節(jié)點(diǎn)A的級(jí)別和t1、t2和t3的信息，節(jié)點(diǎn)B在t4記錄同步幀到達(dá)的時(shí)刻，則有t4=t3+d-Δ，據(jù)此可以推出式（1）：

2　節(jié)點(diǎn)通信能耗模型

如圖2所示，由于指令計(jì)算和數(shù)據(jù)采集耗能遠(yuǎn)遠(yuǎn)小于無線通信模塊，而且這種常量性消耗不影響通訊模型，因此我們主要對(duì)無線通信能耗進(jìn)行分析［10］。假設(shè)網(wǎng)絡(luò)環(huán)境為自由空間，將一個(gè)k比特的信息傳送距離d，射頻電路的發(fā)送耗能和接收耗能分別滿足式（2）和式（3）：

其中Ee表示發(fā)射裝置和接收裝置每發(fā)送或接收單位比特的能耗；ε表示發(fā)射放大器將每比特?cái)?shù)據(jù)傳送單位平方米所耗的能量［11］。

圖2　R無線傳感器網(wǎng)絡(luò)功耗分布圖

采用TPSN算法進(jìn)行時(shí)間同步，節(jié)點(diǎn)j與其父親層次節(jié)點(diǎn)進(jìn)行同步時(shí)，同步幀長度為K字節(jié)，同步過程包含兩次發(fā)送和兩次接收操作，節(jié)點(diǎn)j能耗為Ej，則有式（4）：

將式（2）和式（3）帶入式（4）得式（5）：

假設(shè)網(wǎng)絡(luò)包含M個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)層次為H層，每個(gè)節(jié)點(diǎn)的通信半徑為R，整個(gè)網(wǎng)絡(luò)覆蓋區(qū)域是半徑為H?R的圓形。那么所有子節(jié)點(diǎn)到同一個(gè)父親節(jié)點(diǎn)的距離的期望為，則該網(wǎng)絡(luò)進(jìn)行N次時(shí)鐘同步所消耗的總能量為式（6）：

3　改進(jìn)TPSN算法介紹

目前能量高效的時(shí)間同步技術(shù)的研究有很多，主要方式可分為：減少網(wǎng)絡(luò)流量、提高傳輸效率與減少重傳次數(shù)、均衡網(wǎng)絡(luò)的能量消耗、優(yōu)化鏈路等方法［10-12-13］。其中減少網(wǎng)絡(luò)流量的方法最為常用，可以通過減少通信次數(shù)、數(shù)據(jù)壓縮和融合、減少包頭長度等方法來實(shí)現(xiàn)。通常時(shí)間同步信息幀至少包含的基本信息包括節(jié)點(diǎn)層次、標(biāo)識(shí)號(hào)和時(shí)間信息，根據(jù)TPSN算法拓?fù)浣Y(jié)構(gòu)固定和周期性時(shí)間同步的特點(diǎn)，時(shí)間同步信息幀中的基本信息在時(shí)間上可能是不變的或者差異較小。本文利用時(shí)間同步幀在時(shí)間上的信息差作為同步幀，信息差由有差別字節(jié)的索引號(hào)和字節(jié)差值構(gòu)成。

改進(jìn)TPSN算法適用于層次型網(wǎng)絡(luò)結(jié)構(gòu)，網(wǎng)絡(luò)層次發(fā)現(xiàn)階段和TPSN算法相同。改進(jìn)TPSN算法時(shí)間同步階段的算法描述如下，以第2節(jié)圖1中A節(jié)點(diǎn)和B節(jié)點(diǎn)間的時(shí)間同步為例。

andk1i；

其中i為時(shí)鐘同步的次數(shù)，SYNC代表長度為K字節(jié)的同步幀，時(shí)刻表示第i次同步時(shí)與TPSN算法對(duì)應(yīng)的t1,t2,t3,t4時(shí)刻。表示第i次時(shí)鐘同步在t1時(shí)刻的同步幀，包含了t1時(shí)刻信息；表示第i次時(shí)鐘同步在t3時(shí)刻的同步幀，包含了t1,t2,t3時(shí)刻信息。表示由第i次和第i-1次在t1時(shí)刻同步幀之間的信息差構(gòu)成的幀，k1i表示第i次和第i-1次在t1時(shí)刻同步幀之間有差別的字節(jié)數(shù)。假設(shè)每個(gè)差別的字節(jié)需要用兩個(gè)字節(jié)，其中一個(gè)字節(jié)表示差別字節(jié)的索引號(hào)，另一個(gè)字節(jié)表示字節(jié)間的差值，那么幀的長度為2k1i。表示由第i次和第i-1次在t3時(shí)刻同步幀之間的信息差構(gòu)成的幀，表示第i次和第i-1次在t3時(shí)刻同步幀之間有差別的字節(jié)數(shù)。同理可得幀的長度為2k3i。

那么改進(jìn)TPSN算法的時(shí)間同步偏差Δi和傳播延時(shí)di結(jié)果如式（9）：

4　改進(jìn)TPSN算法能耗分析

利用式（2）和式（3）的通信能耗模型計(jì)算改進(jìn)TPSN算法能耗。網(wǎng)絡(luò)參數(shù)見表1。

表1　R網(wǎng)絡(luò)參數(shù)

應(yīng)用改進(jìn)TPSN算法，該網(wǎng)絡(luò)第1次時(shí)鐘同步所消耗的能量為式（10）：

由式（10）和（12）可知，該網(wǎng)絡(luò)應(yīng)用改進(jìn)TPSN算法進(jìn)行N次時(shí)鐘同步能耗期望為式（13）：

其中kE為同步幀之間差別字節(jié)數(shù)的期望。

5　仿真

仿真采用離散事件模擬器NS［14］（Network Simulator），比較TPSN算法和改進(jìn)TPSN算法在同步能耗、同步精度方面的表現(xiàn)。網(wǎng)絡(luò)基本參數(shù)見表2。

表2　R仿真網(wǎng)絡(luò)參數(shù)配置

如圖3所示，TPSN算法同步能耗基本維持穩(wěn)定，不隨kE的變化而變化，這是因?yàn)門PSN算法每次發(fā)送的都是定長同步幀。當(dāng)kE≤25時(shí)，改進(jìn)TPSN算法的能耗要明顯低于TPSN算法，并且隨著kE增大大致呈線性增長的趨勢(shì)；當(dāng)kE＞25時(shí)，改進(jìn)TPSN算法實(shí)質(zhì)上與TPSN算法是相同的，兩者的能耗基本持平。前者由式（13）可知，改進(jìn)TPSN算法的總能耗和kE之間呈線性關(guān)系；后者由于改進(jìn)TPSN算法中規(guī)定，用兩個(gè)字節(jié)來表示一個(gè)字節(jié)差，并且當(dāng)兩倍的差別字節(jié)數(shù)大于初始同步幀長度時(shí)，改進(jìn)TPSN算法回歸到TPSN算法上，因此能耗近似。

圖3　R改進(jìn)TPSN與TPSN算法同步能耗對(duì)比

如圖4所示是TPSN算法和改進(jìn)TPSN算法在節(jié)點(diǎn)總數(shù)變化時(shí)的能耗對(duì)比圖。曲面1為TPSN算法能耗圖，同步能耗與節(jié)點(diǎn)總數(shù)呈線性關(guān)系，不隨kE的變化而變化。曲面2為改進(jìn)TPSN算法能耗圖，同步能耗隨著節(jié)點(diǎn)總數(shù)和kE的增大而增大，當(dāng)kE＞25時(shí)，改進(jìn)TPSN算法經(jīng)由圖中的切換線與TPSN算法能耗一致。

圖4　R節(jié)點(diǎn)總數(shù)變化時(shí)同步能耗對(duì)比

如圖5所示，TPSN算法和改進(jìn)TPSN算法的同步誤差都隨著節(jié)點(diǎn)總數(shù)的增大而增大，并且同步誤差基本一致，符合式（1）和式（9）的理論分析結(jié)果。

圖5　RTPSN與改進(jìn)TPSN算法同步精度對(duì)比

6　結(jié)論

本文提出了一種低功耗的改進(jìn)TPSN算法，采用減少數(shù)據(jù)流量的方式，通過使用同步幀前后之間的信息差替代完整的時(shí)間同步幀，降低了同步報(bào)文交互量，減少了同步能耗。與TPSN算法對(duì)比仿真分析結(jié)果表明，本文算法在保證時(shí)間同步精度的情況下，有效地降低了時(shí)間同步能耗。

［1］Chang Qianfeng,Zhang Menglei，Yao Mingwu.A New Energy-Efficient Time Synchronization Protocol in Wireless Sensor Networks［C］//2014 IEEE International Conference on Computer and Information Technology（CIT），2014：684-688.

［2］Lü Guangshen，Yu Fengqi，Dong Chuchu.An Implementation of Low-Power Data Transmission Based on Time Synchronization［C］//2012 8th International Conference on Wireless Communications，Networking and Mobile Computing（WiCOM），2012：1-5.

［3］周賢偉，韋煒，覃伯平.無線傳感器網(wǎng)絡(luò)的時(shí)間同步算法研究［J］.傳感技術(shù)學(xué)報(bào)，2006，19（1）：20-25+29.

［4］徐煥良，劉佼佼，王浩云，等.WSN/WSAN中的時(shí)間同步算法研究［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（31）：56-60.

［5］劉慶龍，高航.能量高效的WSN時(shí)間同步算法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2014，23（6）：148-152.

［6］Kyoung-lae Noh，Serpedin，E.，Qaraqe，K.A New Approach for Time Synchronization in Wireless Sensor Networks：Pairwise Broadcast Synchronization［J］.IEEE Transactions on Wireless Communications，2008，7（9）：3318-3322.

［7］陶志勇，胡明.基于等級(jí)層次結(jié)構(gòu)的TPSN算法改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2012，25（5）：691-695.

［8］林蔚，韓麗紅.無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)壓縮算法綜述［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33（9）：2043-2048.

［9］鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（9）：73-76.

［10］項(xiàng)鵬遠(yuǎn).基于數(shù)據(jù)壓縮的無線傳感器網(wǎng)絡(luò)節(jié)能技術(shù)研究［D］.浙江工業(yè)大學(xué)，2012.

［11］平安，龔鋼軍，劉向軍.無線傳感器網(wǎng)絡(luò)的能量估計(jì)路由算法［J］.計(jì)算機(jī)仿真，2013，30（8）：285-288.

［12］汪付強(qiáng)，曾鵬，于海斌.一種能量高效的無線傳感器網(wǎng)絡(luò)時(shí)間同步算法［J］.信息與控制，2011，40（6）：753-759+766.

［13］Zhang Jian，Lin Shiping，Liu Dandan.Cluster-Based Time Synchronization Protocol for Wireless Sensor Networks［C］//14th International Conference，ICA3PP，2014：700-711.

［14］Gopal Chand Gautam，Sharma T P.Energy Efficient Time Synchronization Protocol for Wireless Sensor Networks［C］//First International Conference，ACC，2011：421-430.

An Improved TPSN Algorithm Based on Inter-Frame Information Gap*

TANG Bo*，WU Shuangshuang，PENG Li
（School of IoT Engineering，Jiangnan University，Wuxi Jiangsu 214122，China）

In wireless sensor networks，as a kind of time synchronization algorithm based on pair-wise synchronization，TPSN has achieved good time synchronization accuracy with the cost of high energy consumption.According to the relevance in time and space of the data received by sensor nodes in TPSN algorithm，an improved TPSN algorithm based on inter-frame information gap was proposed via compressing the data to reduce the data traffic.In the improved TPSN algorithm，the sync frame was stored the first time of time synchronization by sensor nodes，after that，the sync frame was replaced by the information gap between the new sync frame and the sync frame received last time.The new algorithm has compressed the amount of data of sync frame and reduced the message overhead，thereby the energy consumption has been reduced.The simulation results show that the improved TPSN algorithm effectively reduce the energy consumption of time synchronization，while maintaining the accuracy of TPSN algorithm.

wireless sensor network；time synchronization；data compression；low power consumption

唐波（1992-），男，江蘇揚(yáng)州人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)時(shí)間同步算法，tangb1992@foxmail.com；

吳爽爽（1992-），女，浙江金華人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)時(shí)間同步算法，1304614163@qq.com；

TP393

A

1004-1699（2015）12-1830-05

項(xiàng)目來源：江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金-前瞻性聯(lián)合研究項(xiàng)目（BY2013015-33；BY2014024；BY2014023-362014；BY2014023-25）

2015-05-09修改日期：2015-09-19