基于分簇的多跳无线传感网络时间同步算法

摘   要：针对典型的时间同步算法应用到多跳拓扑网络时存在时间同步精确度差、收敛速度慢、功耗较大等问题，文章提出一种基于分簇的多跳无线传感网络时间同步算法。该算法结合了TPSN算法和RBS算法的同步思想，摒弃了TPSN算法同步周期长的缺点而保留了其同步精确度高的优点，也解决了RBS同步开销大和难于应用到多跳网络的问题。该算法具有相当高的同步精度，并有效降低了同步功耗，具有一定的实用性。

关键词：无线传感网络;时间同步;分簇;多跳;同步能耗

1    时间同步技术简介

时间同步技术是无线传感器网络（Wireless Sensor Network，WSN）中一项极为重要的技术，也是诸如节点定位、数据融合和休眠调度等许多关键技术的基础。无线传感器网络相对于传统有线网络在规模上和组织方式上有明显不同，因此，一些传统网络的时间同步协议无法适应无线传感网络的环境条件，必须设计适用于WSN的时间同步算法[1]。自WSN时间同步概念提出以来，国内外学者和科研机构也研究了多种类型的时间同步算法。目前存在的时间同步算法主要可分为3种类型：（1）基于仅接收端（Receive-Only Synchronization，ROS）的时间同步算法，属于此类型的算法主要有DMTS[2]和FTSP[3]算法。（2）基于发送端-接收端（Sender-Receiver Synchronization，SRS）的时间同步算法，其中，典型的算法是TPSN算法[4]。（3）基于接收端-接收端（Receiver-Receiver Synchronization，RRS）同步算法，典型的算法是RBS算法[5]。

以上算法基本上都是基于单跳网络提出的，但在现实环境中大部分网络都是多跳网络，所以有必要具体研究如何将适用于单跳网络的时间同步算法应用到多跳的网络环境中。本文在经典同步算法的基础上提出一种基于分簇的多跳无线传感器网络时间同步（Cluster-Based Time Synchronization algorithm for multi-hop wireless sensor networks，CBTS）算法，该算法不仅确保了同步精度，而且有效保证了能量消耗。

2    算法分析

2.1  层次构造阶段

层次构造过程在网络初始化时执行，首先，为网络中每个节点赋予一个唯一的ID号;其次，选取根节点指定其为第0层并广播层次建立消息包level_constuct，接收到广播消息的节点将自己本地的level值置为分层消息中包含的level值加1，同时，将该发送节点作为自身父节点，并向其发送level_response分组，该分组包含自己的ID号。已重置过level值的节点对其后收到的分层消息都不做处理。父节点收到level_response分组后保存分组中包含的ID，并将这些节点作为自己的子节点，通过变量（Child_count）统计子节点个数。重复以上过程直至所有节点都加入网络，至此整个网络建立完成。

2.2  时间同步阶段

2.2.1  反馈节点的同步

假设P节点为簇首节点，A，B，C为簇内节点，B节点设为反馈节点。节点P在时间T1，i（P）时刻广播包含时间戳T1，i（P）的报文，簇内节点A，B，C都接收到该报文并标记接收时刻T2，i（A），T2，i（B），T2，i（C），反馈节点B在T3，i（B）时刻发送反馈报文，节点P在T4，i（P）时刻接收到该报文。故可以得到如下公式：

其中，d（BP）和Xi（BP）分别表示信息从节点B传输到节点P的固定时延部分和随机时延部分。定义上行链路延迟为，下行链路延迟为。由Shrestha等[6]的研究可知，利用最大似然估计可求得，其中，代表上行链路的测量延迟平均值，即，代表下行链路的测量延迟平均值，即。假使节点的频偏在一定范围内保持不变，一次继续广播一个包含φ（BP），d（BP）和T1，i（P）的三元分组数据包，簇内接收到数据包后便可求得与P节点的相位偏差，再用线性估计方法调整频率偏差，并且在簇首节点设置一个同步精度，因此可以校正節点B，假设节点B同步后的时间为T（B）。CBTS单跳同步算法原理如图1所示。

2.2.2 普通节点同步

节点P广播同步消息后，A，B，C接收到数据包，因为在此过程中消除了接入延迟和发送延迟，这也是延迟中最不确定和影响最大的延迟，所以假设节点A，B，C同时受到节点P广播的数据包，然后分别记录下各自接收到数据包时刻的时间戳。记为T（A），T（B），T（C），因为B已完成了同步，所以A，C都根据B来调整自己的时间差，即，。于是就保证了该单跳区域内节点与节点P同步，这是单跳的情况，多跳也依此方式进行同步。由于每个节点都有子节点计数器，当子节点为0时，则无需广播数据包，有效节省了能量。

3    算法同步误差分析

本算法结合了SRS和ROS同步方式进行同步，在同步时报文的传输延迟主要分为：发送延迟、访问延迟、传输延迟、传播延迟、接收延迟和接收处理延迟。CBTS算法在同步的第一阶段使用双向信息交换的方式，在这个过程中，算法的同步误差主要体现在不确定延迟的估计上，即Xi（BP）和Xi（PB）的值，节点B的同步误差表达式为：

（3）

其中，Xi（BP）和Xi（PB）分别表示节点B到节点P和节点P到节点B的不确定延迟，表示节点B和节点P同步一轮的时钟漂移。

在同步的第二阶段，父节点广播一个数据包，子节点接收该数据包并记录其时间戳，这个过程中消除了发送端的发送延迟和访问延迟两大不确定延迟，因此能够极大地提高同步精度，同步时误差主要体现在节点的时钟频偏和同步过程中产生的时钟漂移。节点A，C的同步误差可表示为：

（4）

其中，表示其他節点分别与B节点在接收P广播时的接收误差。

4  结语

本文提出了一种基于分簇的WSN时间同步算法，该算法建立在分簇网络的基础上，利用簇内节点同步方式进行优化，结合了SRS和ROS同步方法，有效保证了同步精度的同时，也降低了同步消息包的收发数量，从而大大降低了网络能耗。

[参考文献]

[1]张超.无线传感器网络时间同步技术进展[J].重庆工商大学学报（自然科学版），2019（6）：88-94.

[2]PING S.Delay measurement time synchronization for wireless sensor networks[J].Intel Research Berkeley Lab，2003（6）：1-12.

[3]MAROTI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol[C].Hangzhou：International Conference on Embedded Networked Sensor Systems，2004.

[4]GANERIWAL S，KUMAR R，SRIVASTAVA M，et al.Timing-sync protocol for sensor networks[C].Beijing：International Conference on Embedded Networked Sensor Systems，200.

[5]ELSON J，GIROD L，ESTRIN D，et al.Fine-grained network time synchronization using reference broadcasts[C].Shanghai：Operating Systems Design and Implementation，2002.

[6]SHRESTHA D，PANG Z，DZUNG D.Precise clock synchronization in high performance wireless communication for time sensitive networking[J].IEEE Access，2018（9）：1.

Abstract：In this paper， a clustering-based time synchronization algorithm for multi-hop wireless sensor networks is proposed to solve the problems of poor time synchronization accuracy， slow convergence and high power consumption. The algorithm combines the idea of TPSN algorithm and RBS algorithm， but discards the disadvantage of long synchronization period of TPSN algorithm， and retains the advantage of high synchronization accuracy. It also solves the problem of RBS synchronization overhead and difficult to apply to multi-hop network. The algorithm has quite high synchronization accuracy， and effectively reduces the synchronization power consumption， and has certain practicability.

Key words：wireless sensor networks;time synchronization; clustering; multi-hop; synchronous energy consumption