基于TPSN和DMTS的低能耗时间同步算法

何秀春 ， 张金榜 ， 刘 军 ， 林 语

（1. 武警工程大学 研究生管理大队，陕西 西安 710086；2. 武警警官学院 信息工程系，四川 成都 610213；3.武警工程大学 信息工程系，陕西 西安 710086）

基于TPSN和DMTS的低能耗时间同步算法

何秀春1， 张金榜2， 刘 军3， 林 语1

（1. 武警工程大学 研究生管理大队，陕西 西安 710086；2. 武警警官学院 信息工程系，四川 成都 610213；3.武警工程大学 信息工程系，陕西 西安 710086）

针对现有时间同步算法不能满足WBSNs能量受限的问题，提出了一种基于TPSN和DMTS的低能耗时间同步算法。该算法在保证一定同步精度的前提下，通过减少信息交换次数来达到低能耗的要求。实验表明，TPTS算法比TPSN和DMTS减少了开销，降低了能量消耗，满足了低能耗的要求。

TPSN；DMTS；低能耗；时间同步算法

无线躯体传感器网络（WBSNs，Wireless Body Sensor Networks）是由多个感知节点组成的无结构、自组织网络。节点的休眠、唤醒和节点间的协同工作都需要时间同步，节点间的时间同步对于整个网络来说至关重要。目前典型的时间同步算法有RBS[1]（Reference Broadcast Synchronization）、TPSN[2]（Timing-sync Protocol for Sensor Networks）、DMTS[3]（Delay Measurement Time Synchronization）、FTSP[4]（Flooding Time Synchronization Protocol）、LTS(Lightweight Time Synchronization)[5]、Tiny-sync和Mini-sync[6]6种类型，而现有的时间同步算法是针对WSNs而设计的，对于节点能量更有限的WBSNs，虽然适用，但不能很好地满足WBSNs低能耗的要求。因此，通过分析研究现有的同步算法，提出了一种基于TPSN和DMTS的低能耗时间同步算法。

1 理论基础

1.1 TPSN算法

TPSN是由Saurabh Ganeriwal等人于2003年提出的基于成对双向消息传送的发送者与接收者之间的全网时间同步。具体描述如下：同步过程分分层和同步两个阶段。分层阶段是一个网络拓扑的建立过程。首先确定根节点及等级，此节点是全网的时钟参考节点，等级为0级，根节点广播包含有自身等级信息的数据包，相邻节点收到该数据包后，确定自身等级为1级，然后1级节点继续广播带有自身等级信息的数据包，以此类推，i级节点广播带有自身等级信息的数据包，其相邻节点收到后确定自身等级为i+1，直到网络中所有节点都有自身的等级。一旦节点被定级，它将拒收分级数据包。同步阶段从根节点开始，与其下一级节点进行成对同步，然后i级节点与i-1级节点同步，直到每个节点都与根节点同步。成对同步的过程如图1示。

图1 成对同步过程Fig. 1 Twin synchronization process

节点i在本地时刻T1时向节点j发送同步请求，该请求中包含节点i的等级和T1，节点j在本地时刻T2时收到请求并在T3时发送同步应答，该应答包含T2和T3，节点i于本地时刻T4收到应答信息，根据时间关系可列出方程:

其中d是消息传输迟延，Δ为时钟偏差，经过计算得：

节点i计算出时间偏差Δ，从而调整自己的时钟，达到同步。

1.2 DMTS(Delay Measurement Time Synchronization)

DMTS 是由Ping S于2003年提出的基于基准节点广播的发送者与接收者之间的全网时间同步。具体描述为：选择一个基准节点，广播包含时间的同步消息，接收节点根据时间信息估算消息传输时延，调整自身本地时间为同步消息所带时间加传输时延，消息传输时延（td）等于发射时延（ts）加接收处理时间（tv），发射时延为发射前导码和起始符所需的时间，等于发射位数（n）乘以发射一位所需的时间（t），接收处理时间等于接收处理完成时间（ t2）减消息到达时间（t1），所以得出公式：

将DMTS应用到多跳网络中还采用与TPSN相同的分层方法进行同步，只不过将每一层看作一个单跳网络，基准节点依次定在0级，1级，2级，…，n级，逐步实现全网同步。为避免广播消息回传，每一个节点只接收上一层等级比自己低的节点广播。

1.3 TPSN和DMTS性能分析

分析对比TPSN和DMTS算法，DMTS的同步精度略低于RBS，而TPSN的同步精度近似于RBS的两倍，即TPSN的同步精度几乎是DMTS的2倍。虽然TPSN的能耗高于DMTS，但是DMTS是以牺牲同步精度换取低能耗，若要保持同一精度，则DMTS的能耗将远远高于TPSN[7]。

2 TPTS算法

TPTS算法分为两个阶段。第一阶段为层次建立阶段。首先确定根节点及分层，此节点是全网的时钟参考节点，赋予层次号0，根节点广播包有自身层次号的数据包，相邻节点收到该数据包后，确定自身层次号为1，然后1层节点含继续广播带有自身层次号的数据包，以此类推，i层节点广播带有自身层次号的数据包，其相邻节点收到后确定自身层次为i+1，直到网络中所有节点都有自身的层次。已确定层次的节点拒收其他数据包。至此，全网建立起一个层次结构。

第二阶段为同步阶段。同步阶段又分为层间同步和层内同步。层间同步采用成对双向消息传递机制，层内同步采用基准节点单向广播机制，每层节点中随机选出一个基准节点，层内结构形成主从关系。如图2所示。

图2 层内结构图Fig. 2 Layer structure

除根节点外，每层基准节点按层次号依次向上层发送同步请求。1层基准节点向根节点发送同步请求，两节点间采用成对双向消息同步算法TPSN进行同步，1层基准节点计算出节点之间时间偏移和传播时延，调整本地时钟，与根节点达到同步。然后1层基准节点在层内广播一个同步消息，层内其他从节点收到消息后估计消息时延，调整本地时钟。至此实现了一层节点的同步。同步过程中设立一个同步计时器，用于记录层间同步时间T。间隔时间t（T≤t≤2T）后，2层基准节点向1层基准节点请求同步，t的选取保证每层基准节点已与根节点达到同步。以下各层按照层间和层内的同步方法实现全网同步。

该算法结合单向广播和成对双向消息传递进行横向和纵向时间同步，横向指层内广播，纵向指层间成对，横纵交错，实现了所有节点的同步。

3 实验结果及分析

为验证TPTS的性能，采用网络仿真工具NS-2（Network Simulator version 2）进行实验仿真，在同一精度的前提下衡量TPTS算法在能耗方面的改进。仿真环境为50×50 的正方形区域，随机分布30个节点，节点间无线通信距离为100 m。

图3 TPTS算法与TPSN算法消息开销比较Fig. 3 TPTS algorithm and TPSN algorithm message overhead comparison

仿真结果如图3所示。TPTS算法比TPSN算法的同步开销要小的多，并随节点数量的增加，点每个节的相邻节点数目增多，其同步开销的差别越大。这是因为TPTS算法中每层只有一个基准节点，层间同步过程需2个消息交换的开销，而基准节点与本层的其他节点只需要1个消息开销，消息开销随节点数目的增加变化较平缓；而TPSN算法则需要2倍于节点数目的开销，随着节点数目的增加，消息交换的次数也极具增加，同时产生了大量的冗余信息包，造成了消息开销的快速增长。显然，TPTS算法明显减少了同步阶段所需的消息交换次数，降低了同步过程所需的通信开销。

由1.3可知：在保证同一时间同步精度的情况下，DMTS的能耗比TPSN高得多。因此，可以得出结论如下：在保证同一精度前提下，TPTS的能耗小于TPSN和DMTS。

4 结 论

基于TPSN和DMTS算法的低能耗时间同步算法，在继承TPSN和DMTS算法性能优势的基础上，在保证一定精度的前提下，通过减少信息交换次数来实现低能耗的要求。实验结果表明，TPTS与TPSN和DMTS相比，减少了开销，降低了能量消耗，更适用于WBSNs。

[1] Jeremy E,Lewis G,DeborahE.Fine-Grained Network Time Synchronization Using Reference Broadcasts [C]//In Proc.of the Fifth Symposium on Operating Systems Design and Implementation, Boston, MA, 2002: 147-163.

[2] Saurabh G,Ram K,ManiS.Timing-Sync Protocol for Sensor Networks[C]//In Proc.ACM SenSys, Los Angeles,CA,2003.

[3] Ping S. Delay measurement time synchronization for wireless sensor networks[R]. Intel Research Berkeley lab, 2003.

[4] Maroti M, Kusy B, Simon G, et al. The flooding time synchronization protocol[C]// In Proc.of the 2nd ACM Conference on Embedded Networked Sensor Systems(SenSys), Baltimore, Mariland, 2004: 39-49.

[5] Jana V G, Jan R .Lightweight Time Synchronization for Sensor Networks[C]//In Proc. of 2nd ACM Int'l.] Conference on Wireless Sensor Networks and Apps.San Diego,CA, Sept. 2003.

[6] Sichitiu Mihail L, Veerarittipahan Chanchai. Simple, Accurate Time Synchronization for Wireless Sensor Networks[C]//In Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC2003), New Orleans, LA, March 2003:1266-1273.

[7] 杨颖. 训练场士兵生理状况监测系统研究与设计[D].西安:武警工程大学, 2012.

The time synchornization arithmetic of lower power based on TPSN and DMTS

HE Xiu-chun1, ZHANG Jin-bang2, LIU Jun3, LIN Yu1
（1. Graduate Management Team, Engineering University of CAPF, Xi’an 710086, China;2. Department of Information Engineering,Officers College of CAPF, Chengdu 610213, China;3. Department of Information Engineering, Engineering University of CAPF, Xi’an 710086, China）

A lower power time synchronization arithemetic based on TPSN and DMTS, which aiming at the issues that the existing time synchronization can not meet with the problem that the poser is limited in Wireless Body Sensor Networks. This arithmetic realizes the purpose of lower power through reducing the degree of communication, when the precision is determinate. The experimentation shows that the TPSN is lower spending and lower power than TPSN and DMTS，which has meet with the lower power intention.

Timing-sync Protocol for Sensor Networks; Delay Measurement Time Synchronization; low power; time synchornization arithmetic

TN96

A

1674-6236(2014)03-0021-02

2013–06–20 稿件编号：201306128

何秀春(1987—)，女，四川南充人，硕士研究生。研究方向：无线数据通信、电子技术应用 。