一种新的无线传感器网络时间同步算法

游继安，李　哲

(湖北工程学院 新技术学院，湖北 孝感 432000)

一种新的无线传感器网络时间同步算法

游继安，李哲

(湖北工程学院 新技术学院，湖北 孝感 432000)

摘要：在分析以往各种时间同步优化算法的基础上,提出一种改进的无线传感器网络时间同步算法。该算法主要分为三步：首先对节点进行筛选，排除通信有故障的节点，然后将全网节点进行分层以减少WSN网络的复杂性，最后设计相应的传输协议，利用时间同步算法对分层后的节点进行时间同步。实验结果表明，该算法不仅明显提高了网络同步时间的准确度，而且减少了计算时间开销。

关键词：无线传感器网络;时间同步;分层;传输协议

中图分类号：TP393.1

文献标志码：码：A

文章编号：号：2095-4824(2015)06-0059-07

收稿日期：2015-09-11

基金项目：湖北工程学院新技术学院科学研究项目(Hgxky12)

作者简介：游继安(1987-)，男，湖北孝感人，湖北工程学院新技术学院助教，硕士。

Abstract：Based on the analysis of the advantages and disadvantages of the previous various time synchronization algorithms, an improved WSN time synchronization algorithm is proposed. The newly proposed algorithm is divided into three steps. First, the fault nodes are excluded from the network. Second, the layering nodes in the whole network are conducted to reduce the complexity of the WSN. Finally the corresponding transmission protocol is designed for time synchronization of layered nodes. Experimental results showed that the proposed algorithm significantly improved the network synchronization time and reduced the computational cost at the same time.

无线传感器网络(Wireless Sensor Networks, WSN)的研究起源于越战，主要应用于军事领域，直到“911事件”后，才迎来了WSN的飞速发展。目前，无线传感网络已经在环境监测、工业、农业、医疗、太空探索以及军事等诸多领域都有广泛的应用[1-2]。

WSN主要包括传感器，微控制器以及网络通信三个部分。以上三部分中，传感器与微控制器在市场上的应用相对来说比较成熟。只有网络通信这一部分有较大的研究空间。确切地说，决定一个WSN系统的优劣并不取决于WSN的硬件配置，而是网络通信算法现阶段。WSN通信主要存在能量受限、扩展性、鲁棒性、精确性以及收敛性等问题，而在以上问题中，时间一致性是众多问题中最基础的问题之一。

常规的时间同步方法分为两步。第一步是对每个网络的中心节点的时间进行同步，该同步方法称为时间比对。目前，常规的时间比对系统主要有以下六类：(1)GPS[3]；(2)GLONASS[4]；(3)中国北斗卫星导航定位系统[5]；(4)电视时钟系统[6]；(5)OMEGA系统[7]；(6)罗兰——C导航系统和无线电报时系统[8-9]。在以上六种时间比对方法中，GPS系统与北斗系统应用最为广泛。第二步是运用时间同步算法达到同步网络中所有节点时间的目的。对于常规的时间同步算法，应用较为广泛的有RBS、TPSN和FTSP等算法。

1常规的时间同步算法

1.1RBS-参考广播时间同步协议

RBS算法是由加州大学Jeremy Elson等人于2002年提出的，是一种基于Receiver-Receiver架构的时间同步模式。该算法中，Sender利用广播发送消息的方式将消息发出后，两个不同Receiver接收消息后，记录消息中的时间和记录接收到消息的时间，然后两个不同Receiver交换记录接收到消息的时间，就知道两个Receiver间的时钟偏移量，其中一个Receiver根据这个时间偏移量来更改自己的时间值，另一个Receiver的时间值不变。RBS的时间同步方法如图1所示。

1.2TPSN-传感器网络时间同步协议

TPSN算法是加州大学网Saurabh Ganeriwal 等人于2003年提出的，该协议采用双向成对同步方法，这种方法主要由两个阶段组成：分层阶段与同步阶段。首先选取一个根节点，并由这个根节点把分层数据包广播出去，收到数据包的节点确定自己的层次号后，将重新打包的数据包广播出去，重复该过程，直到所有节点均已分层完毕，分层过程如图2(a)中的第1步(虚线标识的动作)所示。

李哲(1986-)，男，湖北汉川人，湖北工程学院新技术学院讲师，博士研究生。

图1　RBS时间同步协议的基本原理

(a)

(b)

同步阶段：该阶段的基本模式如图2(b)所示，该阶段的核心点是节点间成对地交换带有时间同步参数的消息，以达到时间同步的目的。该阶段可以用以下公式进行计算：

(1)

(2)

上式中：δ为时间漂移，d为时间传播延迟。

该同步方法不仅同步精度高(同步精度大约为RBS同步方法的两倍)，而且在大型网络中仍有较好的同步性能，该算法的同步误差只取决于网络中的同步跳数，与网络中的总节点数无关，而且该算法也有较好的可扩展性。

1.3FTSP时间同步算法

FTSP算法是由美国田纳西州范德堡大学的Branislav Kusy等人于2004年提出的，其主要思想是使用单双向结合传播消息的方法实现节点间的时间同步，广播消息的形式如图3所示。

图3　FTSP的消息交换图

FTSP主要的基本过程是：首先给每个节点规定一个全网唯一的ID标志号,通过根节点将时间同步包sync广播出去，收到时间同步包的节点根据时间同步包来同步自身的时间，同步完成后，生成一个新的时间包，并广播出去，达到同步全网节点时间的目的。同步过程如图4所示。

图4　FTSP中数据包经过无线信道

如果为多跳网络，则在广播时间同步前，还需要对网络上的节点进行分层，然后再对所有节点进行时间同步。

2系统设计

2.1改进的时间同步算法

2.1.1算法原理

总结现有WSN时间同步算法的特点可知，当WSN节点数量较少且分布集中时，采用简单的算法就可以解决时间同步问题，如RBS算法。但当节点数量较多、网络结构复杂，且网络节点数目不确定时，就需要寻求更加有效的时间同步算法。复杂的网络通常不能一次性使所有节点时间同步，因此，就必须对网络进行分层，而分层较有效的一种方法是广播消息分层法，当WSN所有节点分层完后，再对WSN的所有节点进行时间同步。本文提出的改进时间同步算法主要分为三个阶段。

第一阶段为节点的筛选阶段。节点的筛选过程，主要有两个核心点。第一是在制节点时，需要核对节点的传输时间，例如，核对节点规合时，规定节点的单次单向传输时间范围在[t1，t2](t1

第二阶段是对全网节点进行分层，给每个节点分配一个层次号。在该阶段中，所采用的分层方法是洪泛广播方法。首先需要选取根节点，并规定该节点的层次号为0，然后由该节点广播消息包，消息包主要包括该节点的ID号与该节点的层次号，收到广播消息的节点取出消息包中的节点层次号与自身的层次号进行对比，若是自身的层次号比该层次号小1，则将该节点加入下层节点的列表中，若自身层次号大于该层次号，则改变自身层次号令其等于该层次号加1，并记录上层节点的ID。最后，将本节点的层次号与ID号进行打包，并利用洪泛广播的方式发送出去，不断重复以上过程，直到所有节点都分层完毕为止。

第三阶段为时间同步阶段。从节点层次号为0的节点开始，逐层同步网络中的其他节点，同步方法由双向时间同步法改进而来。首先，根节点从下层节点列表中选取一个节点作为响应节点，然后，将时间同步消息广播出去，接收到广播消息的节点利用本地时间记录消息的接收时间，只有根节点指定的响应节点向根节点返回消息，根节点接收到消息后，用双向成对时间同步方法来计算时间偏移值δ、传播延迟值d以及响应节点接收到消息的时间T2。然后，由根节点将包含这三个参数的数据包广播出去，响应节点根据数据包中的时间偏移值δ和传播延迟值d来调整本地时间，广播域内的其他节点接收到数据包后，记录接收时间T2'，由此计算出

(3)

T=t+δ'

(4)

式中：t为叶子节点接收消息的时间。层次号为1的节点时间同步完成后，再由根节点选取第一层节点中的部分节点(节点数目的选取根据实际网络布局决定)作为根节点，重复之前的动作，直到所有节点的时间同步完成为止。消息交换及时间标记过程如图5所示。

2.1.2算法流程

按上述三阶段的时间同步过程，第一阶段的工作需要提前完成，在网络布局完成之后，再分别进行第二阶段与第三阶段的工作。其工作流程图如图6所示。

2.1.3通信协议

根节点与叶子节点通过无线串口进行连接，采用高级数据链路控制(High Level Data Link Control，HDLC)协议进行串口通信。HDLC是一种数据链路层协议，确保传送到下一层的数据在传输过程中能够准确地被接收。一般来说，串口消息包括两部分，即串口消息头和有效载荷，没有footer和metadata部分。完整的串口数据消息格式如图7所示。

(c)

图7　串口通信格式

在图7所示的串口数据帧中，F占一个字节，表示帧定界符，标识帧的开始或者结束。HDLC规定每一个数据帧都必须以0x7E作为开始和结束标志。P占用一个字节，为TinyOS串口协议栈的协议字段(TinyOS是专门为WSN设计的操作系统)，当该字段值等于0x44时，表示串口数据帧需要确认，接收端收到数据帧后需要返回确认帧。当该字段值等于0x45时，则不需要返回确认帧；S为序列号字段，占一个字节长度；D表示包格式类型，占一个字节格式，默认值为0。payload的内容即为串口消息，包括串口消息头和有效载荷部分，串口消息头格式如图7所示，最大有效载荷仍然使用默认的28个字节。CRC为两个字节的循环校验码，采用ITU-T标准CRC生成多项式。G_16(x) = x16+ x12+ x5+ 1，校验范围从P字段开始到payload结束。

(1)下行数据。当WSN根节点向叶子节点以洪泛广播形式发送消息时，需要按照协议规定的格式封装数据包，然后发送到串口。普通节点接收到串口数据后，按照协议进行解包，再根据命令类型封装成不同的数据包，然后下发到网络中。普通节点接收到根节点下发的命令后，需要记录接收信息的时间T2，并从数据包中取出根节点所在的网络号与自身的网络号进行对比。当串口消息头中的type字段值等于0x14时，表示是时间同步数据包，如果值等于0x15时，表示广播分层数据包。串口消息头的前两个字节为根节点的ID号，串口消息头的第三、第四字节分别为包类型与分发命令类型，第五、六个字节为δ，第七、八字节为d，第九字节为层次号，TinyOS规定下行数据必须有S字段。分发命令类型01表示下行数据，02表示上行数据。包类型分为广播分层数据包01(如图2(a)中的第1步)与广播时间同步数据包02(如图2(a)中的第3步)两种。下行数据包格式如图8所示。

图8　下行广播命令串口数据包示例

(2)上行数据。网络中所有节点分层结束后，第一层节点开始向层次号为0的根节点发送消息，0号根节点接收到普通节点上传的数据后，需要将数据进行解封，然后再封装成串口消息包发送到根节点。上行数据不需要确认帧，因此P字段值为0x45。本文规定当串口消息头中的type字段值等于0x35时，表示上传时间同步数据，等于值0x36时表示上传的传感器数据，值等于0x37表示上传的状态数据，值等于0x38时表示上传的拓扑数据。TinyOS规定上行数据没有S字段。图9为普通节点发送消息到WSN根节点的传感器数据格式。

图9　行串口数据包格式示例

需要指出的是，串口数据帧中CRC字段采用的是小端格式，即数据传输时先传送低字节后再传送高字节，其他数据采用的是大端格式，即数据传输时先传送高字节后传送低字节。状态数据、拓扑数据格式和传感器数据格式类似，仅仅是串口消息头中的类型标识不同。

对RBS、TPSN、FTSP以及本文算法等4种算法的同步类型、同步方式、同步精度、算法复杂性以及算法收敛时间作比较，结果如表1所示。

表1　4种同步算法的比较

由以上分析得知，以上四种时间同步方法都采用了泛洪与广播的方式。RBS对于节点较少且分布集中的网络有较好的时间同步效果。TPSN算法采用双向成对时间同步方法来同步节点时间，因此，该算法有较好的同步精度，但由于该算法对每个节点采用双向成对同步方法，因此其收敛时间一般。FTSP算法采用单双结合的方式对全网节点的时间进行同步，该算法的复杂度较高，同步精度也较高，但是其收敛时间较长。本文算法采用单向与双向相结合的时间同步模式，因此算法复杂度较低，同度精度较高，收敛时间比较短。

3系统测试

利用软件仿真方法来测试本文算法的性能，软件仿真的具体步骤如下：

采用MATLAB对本文算法进行仿真，模拟出如下实验环境：在面积为100 m×100 m的范围内，网络节点数为30，节点的通信半径为10米。本文应用一个6×30的矩阵来表示无线网络中的节点，每一列表示一个节点的相应信息，每个节点的第1行表示节点为的ID，第2、3行分别表示节点的横坐标和纵坐标，第4行表示每个节点的初始时间，第5行表示每个节点所在的层次，第6行表示节点的剩余能量。

将表1中另外三种算法与本文算法进行比较，当某一普通节点失效时，上述四种同步算法分别按照各自的同步方法重新对所有网络节点进行时间同步，图10为某一节点失效后网络中节点同步时间与误差间的关系。

图10　叶子节点失效后同步时间与误差的关系

若某一普通节点失效或有新节点加入时，需要重新对网络进行分层，并且重新配置网络参数。本文改进的新型时间同步算法只需要通过邻节点便可以计算出新加入节点的同步时间值。从图11可以看出，本文算法明显减少了节点的同步时间。

图11　节点数与同步时间的关系

4结束语

本文提出了一种改进的时间同步算法，该算法极大地节省了节点的开销，最大限度的减少了因节点缺失造成的损失。同时，该算法因为采用了单双结合的时间同步方法，因此具有较好的时间同步精度与较高的时间同步效率。经测试，本文提出的时间同步算法具有较高的鲁棒性，时间精度较高，具有较好的实际应用价值，且扩展性较好。

[参考文献]

[1]AN T R, Gao F, Zhang G, et al. Integration of IoT and DRAGON-lab in cloud environment[J].中国邮电高校学报:英文版, 2012(2):87-91

[2]Lai M, Zhou T, Liu Z. IOT technology application model research of transportation industry in China[J].中国工程科学:英文版, 2013, 11:90-96.

[3]Yi T H, Li H N, Gu M. Experimental assessment of high-rate GPS receivers for deformation monitoring of bridge[J].Measurement, 2013, 46(1):420-432.

[4]郭际明, 孟祥广, 李宗华,等.GLONASS卫星广播星历精度分析[J].大地测量与地球动力学, 2011, 1(1):68-71.

[5]胡志刚. 北斗卫星导航系统性能评估理论与试验验证[D].武汉:武汉大学,2013.

[6]王冠凌,郎朗,王满海,等.基于ZigBee和GPS广播电视时钟授时系统的研究[J].自动化与仪器仪表,2008(5):15-18.

[7]梁丽敏. 提高Omega系统叠前时间偏移处理质量的技术对策[C]//中国地球物理学会第22届年会论文集, 2006.

[8]林雪原,何友. GPS/罗兰C/SINS/AHRS组合导航系统及试验[J].电子科技大学学报,2008,37(1):4-7.

[9]何松. 基于FPGA的罗兰C路基导航系统RS编译码器的设计与实现[D].成都：西南交通大学,2014.

A Novel Time Synchronization Algorithm for Wireless Sensor Networks

You Ji’an, Li Zhe

(CollegeofTechnology,HubeiEngineeringUniversity,Xiaogan,Hubei432000,China)

Key Words：wireless sensor networks; time synchronization; layering; transmission protocol

(责任编辑：张凯兵)