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

唐　波，吳爽爽，彭　力

（江南大學物聯網工程學院，江蘇無錫214122）

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

唐波*，吳爽爽，彭力

（江南大學物聯網工程學院，江蘇無錫214122）

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

無線傳感器網絡；時間同步；數據壓縮；低功耗

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

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

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

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

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

1　TPSN算法介紹

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

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

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

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

2　節點通信能耗模型

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

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

圖2　R無線傳感器網絡功耗分布圖

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

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

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

3　改進TPSN算法介紹

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

改進TPSN算法適用于層次型網絡結構，網絡層次發現階段和TPSN算法相同。改進TPSN算法時間同步階段的算法描述如下，以第2節圖1中A節點和B節點間的時間同步為例。

andk1i；

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

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

4　改進TPSN算法能耗分析

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

表1　R網絡參數

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

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

其中kE為同步幀之間差別字節數的期望。

5　仿真

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

表2　R仿真網絡參數配置

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

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

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

圖4　R節點總數變化時同步能耗對比

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

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

6　結論

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

［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］周賢偉，韋煒，覃伯平.無線傳感器網絡的時間同步算法研究［J］.傳感技術學報，2006，19（1）：20-25+29.

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

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

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

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

［10］項鵬遠.基于數據壓縮的無線傳感器網絡節能技術研究［D］.浙江工業大學，2012.

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

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

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

TP393

A

1004-1699（2015）12-1830-05

項目來源：江蘇省產學研聯合創新資金-前瞻性聯合研究項目（BY2013015-33；BY2014024；BY2014023-362014；BY2014023-25）

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