基于机器学习方法的无线传感网络时钟同步算法

刘学超+郭改枝+潘亮

摘 要： 提出一种无线传感网络同步的方法，结合发送者?接收者同步（SRS）和接收者?接收者同步（RRS）两种方法，使得位于特定区域的传感器节点通过监听一对超级传感器节点交换时钟消息，借助最小二乘法精确估计出时钟偏差以及频率偏差进行补偿，实现节点间同步。该时钟同步方案的设计与其他已提出的同步方案相比，显著降低了整个网络的能量消耗而不引起任何同步精度的损失。

关键词： 无线传感网络； 最小二乘法； 时钟同步； 时钟偏差； 频率偏差； 均方误差

中图分类号： TN915.02?34 文献标识码： A 文章编号： 1004?373X（2018）05?0065?04

Abstract： A method of wireless sensor network （WSN） synchronization is proposed， which is combined with SRS （sender?receiver synchronization） and RRS （receiver? receiver synchronization） methods to make that the sensor nodes located in a specific area can exchange the clock messages by monitoring a pair of super sensor nodes. The least square method is used to accurately estimate the clock offset and frequency offset for compensation， so as to realize the synchronization among nodes. In comparison with other clock synchronization schemes， the proposed clock synchronization scheme can significantly reduce the energy consumption of the entire network without any loss of synchronization accuracy.

Keywords： wireless sensor network； least square method； clock synchronization； clock offset； frequency offset； mean square error

0 引 言

随着互联网的不断发展，无线传感器网络（WSN）逐渐在各领域中被广泛的应用，微机电系统（MEMS）、数字电路设计和无线通信的发展给无线传感网络的普及提供了很多便利条件。无线传感器网络将会是未来通信环境的基础设施，一个新的问题随之产生，即网络同步问题。无线传感器网络的时间同步对于维持数据的一致性、协调性以及执行其他基本操作都至关重要[1]。

一般来说，在网络同步中存在两种不同的方法，即发送者?接收者同步（SRS）和接收者?接收者同步（RRS）。前者是针对一对节点之间的双向消息交换的经典模型，后者是在同步节点之间比较来自参考节点的信标包进行同步。大多数现有的时间同步协议都可以归类为这两种方法之一[2]。例如，参考广播同步（RBS）协议[3]基于RRS，使得在参考节点传输范围内的一组无线传感器同步，它需要子节点（除了参考节点）之间的消息交换对来补偿它们的相对时钟偏移。无线传感器时钟同步算法（TPSN）[4]采用SRS，因为它取决于假定双向定时消息交换的一系列成对同步。TPSN基于网络的层级结构，并且通过沿着分层树的每个分支（边）交换定时消息来同步整个网络。本文提出成对广播同步（PBS）方案，其依赖于新颖的时间同步方法实现网络范围内的同步，既不同于SRS也不同于RRS，称之为仅接收者同步（ROS）。

1 主要思想

首先需要有进行双向时钟信息交換的两个节点，这两个节点的能量必须足够大，因此可称为超级节点。由于功率约束，传感器的通信范围严格地限于其半径，半径的大小取决于发射功率（参见图1）的（无线电几何）圆，所以在无线传感器探头布控过程中，需要合理放置两个超级节点，使得以超级节点为中心的这两个圆有尽可能大的交集并且使得尽可能多的待同步节点同时处于两个超级节点的通信范围内。

假设一个无线传感器网络的节点布控如图1所示，当两个超级节点进行同步信息交换时，处于两圆交集内的每个节点（例如，节点）可以监听到来自节点和节点的消息包。节点和节点之间进行双向定时消息交换，节点为父节点。此时，在两圆交集的所有节点可以监听到分别来自节点和节点包含成对同步时间戳的同步消息。在这个过程中，该范围内的其他待同步节点不需要发送额外定时消息就可以同步到父节点上，这种同步方法显著减少了发送定时消息的数量。

2 算法描述与实现

PBS同步中父节点和子节点实现同步的消息交换模型如图2所示。代表之间的时钟偏移，假设时钟消息交换了次，在第次信息交换时的本地时钟是，的本地时钟是。节点向节点发送同步消息包中包含节点的标识符（ID）和节点发送消息时的时间戳。节点在时刻接收到该同步消息包并且在时刻向节点发送确认消息，该消息包含节点的标识符（ID），节点在时刻收到该消息，故本次消息交换完成消息包内共有4个时戳被记录。

在整个消息交换的过程中，延迟是不可忽略的。分组延迟包含以下几个部分：发送延迟、接收延迟、传输延迟、处理延迟、信道访问延迟。这些延迟分量可以进一步分为两个部分：固定延迟和随机延迟。关于这些延迟的详细研究请参考文献[5]。

到目前为止，已经提出了几个随机延迟模型。单服务器M/M/1队列可以有效地表示点到点连接的累积链路延迟，其中随机延迟被建模为指数随机变量。假设延迟是多个独立随机过程的加法，则建模为高斯延迟模型是合适的。卡方检验表明，随机延迟建模为高斯分布随机变量后具有99.8%的置信度。本文中假设随机延迟和是服从均值为方差为的正态分布。endprint

如图2所示，在两圆交集中的任意节点，例如，节点当节点和节点交换时钟消息时，节点能够监听到这两个时钟消息。因此，当节点从节点接收到分组时，节点可以在其本地时钟观测到一组时间读数。关于时间戳集合的信息也可以通过从节点接收分组来获得。本文同时考虑时钟偏移和时钟频偏的影响，节点第次收到同步消息的时间戳可以表示为：

式中：代表之间的相对时钟偏移；代表之间的相对时钟频偏。

（节点在第次收到同步消息的时间）可表示为：

要使时钟偏差以及时钟频偏的计算尽可能达到精确的程度，本文借助最小二乘法来估计时钟偏差以及时钟频偏，需要构造一元线性回归模型，由式（1）、式（2）得：

定义：其中。

因此，上述一元线性回归模型变成。

根据最小二乘法，要使残差平方和达到最小才能达到最佳拟合曲线的标准：

残差平方和如下：

通过最小确定最佳拟合直线，可视为以为变量关于的函数，即转换为一个求极值的问题，可通过求倒数得到：

本文采用估计的方法[6]得出式（4），可实现节点与节点同步，同理在这个区域内的其他节点也实现了与节点的同步而不需要发送其他信息，有效地节省了大部分能量。

3 几种经典时钟同步方案的对比

该部分将提出的PBS与其他已提出的同步协议（例如TPSN，RBS和FTSP）针对能量消耗量（所需定时消息的数量）和同步精度进行比较。

令为同步过程所需的定时消息的数目，其中为网络中整体传感器节点的数目，则有以下4个结论。

结论1：

参考节点必须在RBS广播信标包次。此外，每个传感器节点必须在接收到广播信标时与网络中的所有其他节点一起发送时间读数，以补偿彼此之间的相对时钟偏移。由于网络中惟一对的数量为，因此[7]。

结论2：

由于网络中的每个节点都连接到除参考节点之外的其父节点，所以在分层树中存在个分支（边）。此外，对于TPSN，在每个成对同步中需要个定时消息。TPSN中所需的定时消息的数目等于成对同步的数目乘以每个成对同步所需的定时消息的数目，因此[7]

结论3：

对于FTSP，每个传感器节点必须在接收到信标（或广播信标）时向其他节点发送其时间读数，以便它们可以估计彼此之间的相对时钟偏移。因此，FTSP中所需的定时消息的数目等于传感器节点的数目乘以信标的数目[8]。

结论4：

本文提出的时间同步算法——成对广播同步（PBS）在每个同步周期中仅需要个定时消息，因此，的大小不取决于网络中的传感器数量，这将会节省巨大的能量。此外，网络规模越大，该优势越明显。因此，PBS相对于RBS，TPSN和FTSP在能量节省方面有巨大的优势。

下面将通过计算克拉美罗界[9?10]来衡量本文提出的同步算法的精度。

式（3）用矩阵表示法可以表示为：

其中噪声因子最小二乘估计得出可计算出费雪信息矩阵。

令，因此：

根据定义由费雪信息矩阵可计算出克拉美罗界如下：

通过Matlab进行仿真，结果如图3所示，给出了PBS中所提出的时钟偏移均方误差（MSE）和克拉美罗界的对比，以及时钟频偏的均方误差（MSE）和克拉美罗界的对比。

由图3可知，克拉美罗界几乎等于均方误差，所以该无偏估计的性能是很好的。值得说明的是发送同步消息的次数的取值越大均方误差越小，在该同步算法中尽量使相对于其他已提出的算法在能量节省方面有明显的优势。

4 结 语

时钟同步为无线传感器网络提供了公共的时间标准，从而为传感器网络节点的相互协作以及网络的数据融合提供了基础前提。所以，时钟同步是无线传感器网络中最基本、最重要的问题之一。当前已有时钟同步算法主要存在的问题是同步精度不高并對硬件节点的能耗要求比较大，实际应用中无线传感器网络节点并不是很方便更换电池，因此改进时钟同步方案的主要目的旨在改善上述两个问题。将本文提出的方法与三种经典的时钟同步算法进行比较，本文方法在有效节省能量的同时保证了时间同步的精度。

参考文献

[1] 张玉强，何泾沙，徐晶，等.基于移动参考节点的无线传感器时钟同步方法[J].通信学报，2015，36（z1）：171?180.

ZHANG Yuqiang， HE Jingsha， XU Jing， et al. Time synchronization method for wireless sensor networks based on mobile reference nodes [J]. Journal on communications， 2015， 36（S1）： 171?180.

[2] 林晓鹏.无线传感器网络时间同步技术分析[J].智能计算机与应用，2016，6（2）：17?19.

LIN Xiaopeng. The analyzing of time synchronization technique for wireless sensor networks [J]. Intelligent computer and applications， 2016， 6（2）： 17?19.

[3] ELSON J， GIROD L， ESTRIN D. Fine?grained network time synchronization using reference broadcasts [C]// Proceedings of the 5th Symposium on Operating System Design and Implementation. Boston： ACM， 2002： 147?163.endprint

[4] GANERIWAL S， KUMAR R， SRIVASTAVA M B. Timing?sync protocol for sensor networks [C]// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. Los Angeles： ACM， 2003： 138?149.

[5] 王树宝，拱长青，王富良，等.TCP/IP网络时间同步机制的误差分析[J].计算机工程，2009，35（18）：111?112.

WANG Shubao， GONG Changqing， WANG Fuliang， et al. Error analysis of time synchronization mechanism in TCP/IP network [J]. Computer engineering， 2009， 35（18）： 111?112.

[6] 陈辉，熊辉，殷昌盛，等.基于无线传感器网络时钟同步的定位算法研究[J].现代电子技术，2015，38（7）：23?27.

CHEN Hui， XIONG Hui， YIN Changsheng， et al. Survey on clock synchronization localization algorithm based on wireless sensor network [J]. Modern electronics technique， 2015， 38（7）： 23?27.

[7] 郝纲，庄毅.一种用于大规模无线传感器网络的时钟同步算法[J].计算机科学，2015，42（12）：189?194.

HAO Gang， ZHUANG Yi. Time synchronization algorithm for large?scale wireless sensor networks [J]. Computer science， 2015， 42（12）： 189?194.

[8] 殷鹏.基于安全性的无线传感器网络时钟同步算法研究[J].现代电子技术，2017，40（4）：151?154.

YIN Peng. Research on security?based clock synchronization algorithm for wireless sensor network [J]. Modern electronics technique， 2017， 40（4）： 151?154.

[9] 张安然.无线传感网络的FTSP时间同步算法优化与实现[D].呼和浩特：内蒙古大学，2017.

ZHANG Anran. Optimization and realization of flooding time synchronization protocol in wireless sensor network [D]. Hohhot： Inner Mongolia University， 2017.

[10] NAZ A， PIRANDA B， GOLDSTEIN S C， et al. A time synchronization protocol for modular robots [C]// Euromicro International Conference on Parallel， Distributed， and Network?Based Processing. [S.l.]： IEEE， 2016： 109?118.endprint