无线传感器网络TPSN-RBS联合时间同步算法*

姜　帆， 郑　霖

(1.无线宽带与信号处理重点实验室，广西 桂林 541004；2.桂林电子科技大学 信息与通信学院，广西 桂林 541004)



无线传感器网络TPSN-RBS联合时间同步算法*

姜帆1,2， 郑霖1,2

(1.无线宽带与信号处理重点实验室，广西 桂林 541004；2.桂林电子科技大学 信息与通信学院，广西 桂林 541004)

摘要:针对大规模多跳传感器网络节点间所存在的同步误差及其累积误差问题，提出了一种基于加权最小二乘法的TPSN-RBS联合时间同步算法。该算法充分利用可监听到的消息，通过加权最小二乘法估计得到节点逻辑时钟的时间偏移和频率偏移的最优解。用Cramér-Rao下界对本算法进行性能分析，同时与TPSN算法进行仿真对比，结果表明:该算法提高了节点间的同步精度，且在节点密集的大规模无线传感器网络中，在保证较低通信量的同时降低了累积误差。

关键词：无线传感器网络； 时间同步； 加权最小二乘法

0引言

时间同步是无线传感器网络(WSNs) 的一项重要支撑技术，时间同步在很多方面都有广泛的应用。从目前的研究成果来看，无线传感的网络中的时间同步技术主要可以分为基于发送者—接收者的同步 (sender-receiver synchronization,SRS)机制[1]，这种算法单跳同步精度比较高，但是需要多次的时间信息收发，因此,需要较大的通信量和存储空间。基于接收者的同步(receiver-only synchronization,ROS)[2]，以及基于接收者—接收者的同步 (receiver-recei-ver synchronization,RRS)机制[3]，这些算法很难做到同时兼顾同步精度和能耗，且这些算法的同步误差随跳距累积，难以扩展到大规模高密度无线传感器网络。针对上述问题，研究者分别从两方面对时间同步算法进行改进:一是在成对节点间将最优融合估计引入到时间偏移和相位偏移的估计中，如最大似然估计[4,5]、最小二乘估计[6,7]以及卡尔曼滤波[8,9];二是改进全网时间同步协议[10,11]来达到提高时间同步性能的目的。

常用最优融合估计的有：最小二乘估计、线性最小方差估计、极大后验估计、Bayes估计以及极大似然估计等[12]。最小二乘估计使用的最优指标是使两侧估计的精度达到最佳，估计中不必使用与被估计量有关的动态信息与统计信息。该方法的最大优点是算法简单，在对被估计量和量测误差缺乏了解的情况下仍能使用。

本文基于加权最小二乘法，提出了一种无线传感器网络TPSN-RBS联合时间同步算法。它利用传感器节点时间同步协议(timing-sync protocol for sensor networks，TPSN)的单跳同步精度高的优点和参考广播同步 (reference broadcast synchronization，RBS) 算法通信量低的优点，同时结合了加权最小二乘估计，对节点的时间偏移和频率偏移同时进行同步。该算法在降低了通信量的基础上，提高了单跳同步的精度，并且在大规模网络中，降低了时间同步的累积误差。

1算法模型

1.1时钟模型

节点i的本地时钟可表示为

(1)

其中，fi(t)为节点i本地时钟的频率偏差，t0为初始时刻，Ti(t0)为节点在t0时刻的本地时间。

在每个节点内有一个本地时钟和逻辑时钟。同步算法就是要使所有节点的逻辑时钟值同步。

1.2基于邻节点信息的时钟同步模型

本文中的算法结合了TPSN和RBS两种算法，兼顾了同步精度和通信量，同时降低了集中式网络层次结构中的累积误差。

图1为整体网络结构;图2为整体网络结构中的参考节点和下层节点之间的连接情况，参考节点P和下层节点A，B，C都在彼此的通信范围内，它是整体网络结构中的一个典型的上下层节点连接结构。因此，在阐述该算法时，皆以此结构为例。

图1　整体网络结构Fig 1　Overall network structure

图2　部分网络结构Fig 2　Part of the network structure

图3所示即为时间信息传播模型，在一个同步周期内的时钟消息发送情况。下层节点A,B,C分别给在其广播范围内的其他节点广播时钟信息，接收节点记录下接收到的消息。在下层节点结束广播消息时，参考节点P将接收到下层节点的消息时所记录下的时间广播发送给下层节点。待同步节点最后收到参考节点发送过来的消息时，同时完成了TPSN算法和RBS算法，最后一个接收到的数据包包含了TPSN算法和RBS算法所需要的信息。

图3　时间信息传输模型Fig 3　Time information transmission model

下面对加权最小二乘估计法在该时间同步算法中的应用进行推导说明。

在时间同步过程中，根据TPSN同步原理，通过节点A和节点P的信息交换，可以得到下面两个方程

(2)

由上述方程可以推出

(3)

其中，f′=1/fPA，fPA=fP/fA，φ′=φPA/fPA,φPA=φA-φP，D为传输延迟中的固定传输延迟，d1和d2为随机传输延迟。

节点A和节点P被动收听节点B和C广播的消息，最后节点P把标记的收听时间发送回给节点A时，对于节点A就可以看作RBS同步过程，根据节点A所得到的时间同步消息，可以得到下面的方程

(4)

由上面两个方程可以推出

(5)

由于

(6)

式(6)可以写成

(7)

同理，在节点C广播时间同步消息时，节点A可以得到一个类似的方程

(8)

因此，通过上述讨论，由式(3)、式(7)、式(8)可以得到以下一组方程组

(9)

这是一组关于未知量f′和φ′的矛盾方程组，即方程的数量大于未知量的数量。下面使用加权最小二乘方法对于这个矛盾方程组进行求解。

令

(10)

AX+e=B.

(11)

计算得到f′和φ′，对节点中的全局参考时钟的频偏和相偏进行校正。

2算法描述

节点i执行的算法迭代过程如下：

1)在初始时刻n=0初始化节点初始频率相位信息；

2)构建节点网络，给节点i分配能接收到消息的上层节点和同层节点；

3)在一个时间周期内，从根节点开始，下层节点首先广播时间同步消息；

4)下层节点广播消息结束，上层节点广播时间同步消息；

5)每个下层节点根据记录的发送时间和接收时间，使用加权最小二乘法同时估计频偏和相偏；

6)校正本地频偏和相偏。

3克拉美罗下界分析

在实际应用中，估计的最佳性能可以通过一个下界得到。克拉美罗下界(Cramér-Rao lower bound,CRLB)表述了无偏估计量理论上所能达到的最小方差

其中,I(θ)为费雪信息量(Fisher information)，定义为

(12)

通常可以利用估计量自身的概率分布函数(probability distribution function,PDF)来计算得到。

在式(11)中，有

式(11)可以写成e=B-AX,e的协方差矩阵为

(13)

在未知矢量上，有联合似然函数

(14)

考虑CRLB，定义矩阵I为

(15)

将上式简化可得到

I=A-1Ce(AT)-1.

(16)

I为费雪信息矩阵，因此

(17)

在式(17)中，频率偏移估计的均方误差中包含瞬时时间分量。

4仿真分析

利用Matlab仿真软件对算法进行数值仿真。该算法从全网同步误差、多跳累积误差和通信量三个方面与TPSN算法进行比较。

4.1算法性能比较

图4为一个6层网络中节点的连接情况。将位于第1行第1列的节点作为参考节点，观察全网节点的平均误差随时间的变化情况。

图4　网络节点连接情况Fig 4　Connectivity of network node

图5表示了两种算法的全网节点误差的均方误差(mean square error,MSE)随着时间同步周期的变化而变化情况。从图中可以看出，最小二乘时间同步(least square time synchronization,LSTS)LSTS算法的全网节点误差在经过了一段时间的同步之后，平均误差趋于稳定，且误差的MSE为0.1 μs。

图5　LSTS算法和TPSN算法全网节点平均误差的MSE对比Fig 5　Comparison of MSE of entire network nodes averageerror between LSTS algorithm and TPSN algorithm

图6表示了两种算法累积误差的均方误差的对比，可以看出: LSTS算法的累计误差比TPSN算法的累计误差小2个数量级。

图6　LSTS算法和TPSN算法累计误差的MSE对比Fig 6　Comparison of MSE of accumulative error between LSTS algorithm and TPSN algorithm

下面来分析两种算法在通信量上的对比。从图4网络节点连接图中可以得到在第n层中有2n-1个节点，从第n层节点和第n+1层节点在两种算法中的通信过程来分析。假设n≥2，在LSTS算法中，在一个同步周期内，每个节点仅广播一次时间信息消息，那么,LSTS算法的通信量可以表示成(2n-1)+(2n+1)=4n。在TPSN算法中，每个下层节点都要同它的每一个上层邻节点有一次时间信息交换，由网络节点连接图中可以得到n+1层节点与n层节点的连接关系，则TPSN算法的通信量可以表示成2(1+4×2+(2n+1-5)×3)=12n-6。对于全网节点来说，两种算法的通信量关系也是如此。

从上述分析中可以看出:LSTS算法中是通过广播的方式来传递时间信息，因此，LSTS算法与TPSN算法相比，通信量大大降低。

4.2MSE仿真分析

图7和图8分别表示随着观测节点层数的递增，LSTS算法估计的相位偏移和频率偏移MSE与CRLB的对比。仿真结果表明:LSTS算法估计的相位偏移和频率偏移MSE随观测节点数变化的趋势与CRLB相同，并且，相位偏移和频率偏移MSE略大于CRLB。

图7　CRLB和LSTS算法的相位偏移MSE对比Fig 7　Comparison of phase offset MSE between CRLBand LSTS algorithms

图8　CRLB和LSTS算法的频率偏移MSE对比Fig 8　Comparison of frequency offset MSE betweenLSTS and CRLB algorithms

5结束语

信息融合算法对于无线传感器网络中同步中相差和频差的估计具有较高的准确度。本文提出了一种基于加权最小二乘法的TPSN-RBS联合时间同步算法LSTS。该算法充分利用了可监听到的时间信息，在单跳同步中具有较高的精度，在大规模多跳网络中具有较小的累积误差，与传统同步算法相比，降低了通信量。

参考文献:

[1]Ganeriwal S,Kumar R,Sribastava M B.Timing-sync protocol for sensor networks[C]∥Proceedings of the 1st International Conference on Embedded Networked Sensor System,Los Angeles,California,USA,2003:138-139.

[2]Maroti M,Kusy B,Simon G,et al.The flooding time synchronization protocol[C]∥Proceedings of the 2nd International Confe-rence on Embedded Networked Sensor System,Baltimore,USA,2004:39-49.

[3]Elson J,Girod L,Estrin D.Fine-griained network time synchronization using reference broadcasts[C]∥Proceedings of the 5th Symposium on Operating System Design and Implementation,Boston,MA,2002:147-163.

[4]Tian X,Miao Y,Hu T,et al.Maximum likelihood estimation based on time synchronization algorithm for wireless sensor networks[C]∥2009 ISECS International Colloquium on Computing,Communication,Control and Management,CCCM 2009,2009:416-420.

[5]Cao X,Yang F,Gan X,et al.Joint estimation of clock skew and offset in pairwise broadcast synchronization mechanism[J].IEEE Transaction on Communications,2013,61(6):2508-2521.

[6]Chepuri S P,Rajan R T,Leus G,et al.Joint clock synchronization and raning:Asymmetrical time-stamping and passive listening[J].IEEE Signal Processing Letters,2013,20(1):51-54.

[7]Akhlaq M,Sheltami T R. RTSP:An accurate and energy-efficient protocol for clock synchronization in WSNs[J].IEEE Transactions on Instrumentation and Measurement,2013,62(3):578-589.

[8]Xu X,Xiong Z,Sheng X,et al.A new time synchronization method for reducing quantization error accumulation over real-time networks:Theory and experiments[J].IEEE Transaction on Industrial Informatics,2013,9(3):1659-1669.

[9]Giorgi G.An event-based Kalman filter for clock synchro-nization[J].IEEE Transactions on Instrumentation and Measurement,2015,64(2):449-457.

[10] Yildirim K S,Kantarci A.Timing synchronization based on slow-flooding in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(1):244-253.

[11] Chang Q,Zhang M,Yao M.A new energy-efficient timing synchronization protocol in wireless sensor networks[C]∥2014 IEEE International Conference on Computer and Information Technology(CIT),2014:684-688.

[12] 韩崇昭,朱洪艳,段战胜.多元信息融合[M].北京:清华大学出版社,2006:231-236.

[13] Kyoung-lae Noh,Chaudhari Q M,Serpedin E,et al.Novel clock phase offset and skew estimation using two-way timing message exchanges for wireless sensor networks[J].IEEE Transactions on Communications,2007,55(4):766-777.

[14] Leng M,Wu Y.On cock synchronization algorithms for wireless sensor networks under unknown delay[J].IEEE Transactions on Vehicular Technology,2010,59(1):182-190.

姜帆(1989-)，女，辽宁抚顺人，硕士研究生，主要研究领域为无线传感器网络。

TPSN-RBS joint time synchronization algorithm for wireless sensor networks*

JIANG Fan1,2， ZHENG Lin1,2

(1.Key Laboratory of Wireless Wideband Communication and Signal Processing, Guilin 541004,China； 2.School of Information and Communication Engineering, Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:A TPSN-RBS joint time synchronization algorithm based on weighted least square method is proposed,aiming at synchronization errors and its calculative errors existing between massive multiple hops sensor network nodes.The optimal solution for the time offset and frequency offset of logical clock of node is obtained by weighted least square method,using messages that can be heard.The Cramér-Rao lower bound is used for performance analysis,and compared with the TPSN algorithm,the simulation results show that,the synchronization precision between nodes is improved,and in large-scale wireless sensor networks with dense nodes,assure lower communication traffic,at the sometime cumulative errors are reduced.

Key words:wireless sensor networks(WSNs); time synchronization; weighted least square method

作者简介:

中图分类号：TP 393

文献标识码：A

文章编号：1000—9787(2016)01—0149—04

*基金项目：国家自然科学基金资助项目(61362006)；省部共建教育部重点实验室认知无线电基金资助项目(2013ZR08)；2014年度广西高校科学技术研究项目(YB2014137)

收稿日期：2015—03—30

DOI:10.13873/J.1000—9787(2016)01—0149—04