一種基于幀間信息差的改進TPSN算法*

唐　波，吳爽爽，彭　力

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

一種基于幀間信息差的改進TPSN算法*

唐波*，吳爽爽，彭力

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

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

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

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

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

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

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

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

1　TPSN算法介紹

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

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

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

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

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

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

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

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

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

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

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

3　改進TPSN算法介紹

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

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

andk1i；

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

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

4　改進TPSN算法能耗分析

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

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

應用改進TPSN算法，該網(wǎng)絡第1次時鐘同步所消耗的能量為式（10）：

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

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

5　仿真

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

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

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

圖3　R改進TPSN與TPSN算法同步能耗對比

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

圖4　R節(jié)點總數(shù)變化時同步能耗對比

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

圖5　RTPSN與改進TPSN算法同步精度對比

6　結(jié)論

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

［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)絡的時間同步算法研究［J］.傳感技術(shù)學報，2006，19（1）：20-25+29.

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

［5］劉慶龍，高航.能量高效的WSN時間同步算法［J］.計算機系統(tǒ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］陶志勇，胡明.基于等級層次結(jié)構(gòu)的TPSN算法改進［J］.傳感技術(shù)學報，2012，25（5）：691-695.

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

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

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

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

［12］汪付強，曾鵬，于海斌.一種能量高效的無線傳感器網(wǎng)絡時間同步算法［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-），男，江蘇揚州人，碩士研究生，研究方向為無線傳感器網(wǎng)絡時間同步算法，tangb1992@foxmail.com；

吳爽爽（1992-），女，浙江金華人，碩士研究生，研究方向為無線傳感器網(wǎng)絡時間同步算法，1304614163@qq.com；

TP393

A

1004-1699（2015）12-1830-05

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

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