一种基于帧间信息差的改进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