无线传感器网络时钟同步的研究

摘要：在无线传感器网络中，时钟同步是十分必要的。有限的电池能量，存储以及带宽限制等传感器固有的特性的存在，导致传统的时钟同步算法不适合无线传感器网络。本文阐述了时钟同步问题和时钟同步的必要性，介绍了一些传感器网络的时钟同步算法，并深入研究了在考虑节点移动的情况下，利用节点的移动来传递时钟信息的思想，模拟证明我们的算法性能良好。

关键词：无线传感器网络；时钟同步；多跳

引言

传感器节点，又称为无线传送器，是一种具有感知、计算、存储和通信功能的器件。传感器节点组成大规模的网络，来完成一个感知任务。比如要检测一座森林的平均温度，那么需要在森林中均匀地布置大量的传感器，每个传感器将探测到的温度发送给sink节点，再由它传送到主机集中处理。无线传感器网络(以下简称WSN)的主要特征是节点的随意部署(比如飞机空投)，所以预先无法知道节点的确定位置。这可以用于战争或者救灾等(因为在这些情况下，无法在目标区域准确的放置传感器节点)。WSN的特征还有如下:有限资源，大规模的密集网络，动态拓扑结构。通常情况下，为了完成给定的任务，我们需要比预算投入更多的节点，来补偿无法准确定位这个缺点，不过可以利用多余节点来提高系统容错能力。

WSN的许多应用要求传感器节点的时钟保持同步。本文所指的时钟同步是指一个节点保存它跟其他节点之间的相对时钟漂移，以便需要时进行转换。有限的电池能量，存储以及带宽限制等传感器固有的特性的存在，导致传统的时钟同步算法不适合WSN，因此人们提出了一系列新的时钟同步算法。本文对它们作了介绍；并在此基础上，结合接力赛的思想和sink节点的移动模型，深入研究了如何利用节点的移动来传递时钟信息。

WSN时钟同步

时钟同步问题回顾
一般的计算设备，比如个人计算机上都配备有时钟。由于它们步调的不一致，或者某些外部事件的刺激，导致它们的时钟产生漂移。对任何的时钟，我们都可以用下面的公式来估计它的值:

C_i(t)=a_i(t)*t+b_i(t)

a_i(t)表示时钟漂移，b_i(t)表示时钟偏移。同样我们可以用下面的公式来表示两个时钟间的相对关系:

C₁(t)=a₁₂(t)*C₂(t)+b₁₂(t)

a₁₂表示相对漂移，b₁₂表示相对偏移。时钟同步算法的目的就是求出两个时钟之间的相对漂移和相对偏移，这样就可以将一个时钟调整到另外一个时钟的步调(pace)上，而且通过重复的同步训练，使它们在一段时间内保持一致。

时钟同步问题的必要性
在传统的网络中使用的NTP(Network Time Protocol)由于其良好的可扩展性和健壮性而具有不可替代的作用。但是，该协议要求能够始终占用CPU资源，以便它可以执行连续的操作，使时钟一直保持同步；当没有数据包达到时，节点仍然处于监听状态。然而由于WSN本身电池能量的限制，所以为了节能，它要求的是事后同步(Post-Facto Synchronization)，也就是只有需要同步的时候才执行同步算法，而不需要时，就让时钟保持各自的步调。当然，这只是一个主要原因，其他可以参考。

在WSN中，时钟同步是至关重要的。比如多个传感器联合来探测一个运动目标(比如车辆或者坦克)的轨迹，每个传感器将它观测到的位置和时间返回到处理中心，如果这些时钟不事先同步，那么无法判断观测到的位置的时序，从而无法计算出轨迹。

从上面我们可以知道，WSN需要有适应自身的时钟同步算法。

无线传感器网络；时钟同步；多跳
设计一种时钟同步算法，需要认真考虑如下因素:

功耗
由于电池能量的限制，对于传感器网络来说，要延长系统的生命期，必须最小限度的，而且均匀的使用节点能量(负载均衡)。

可扩展性
一种同步算法应该适应大规模数量的节点的加入。

精度
对于一些应用，它们要求较高的精度(比如微妙级)。

容错能力
即使某些传感器节点失败，时钟同步算法应该仍然继续工作。

成本
不应考虑使用大量昂贵的GPS设备，而应使用便宜的普通传感器节点。

响应速度
有些应用要求实时的响应(比如紧急救援等)，因此希望能够事先同步(相对于事后同步)。

时钟同步问题遇到的挑战
节点之间为了达到同步需要交换各种各样的消息，因此节点处理消息时间和消息传送延迟的不确定性，是对WSN时钟同步问题的最大的挑战。我们可以将不确定性时间分解为以下几部分:

1)传送时间:发送者构造消息的时间。
2)访问时间:每个包为了获得MAC层的使用，而需要等待一段时间。
3)传输时间:消息在节点间传送的时间。
4)接收时间:接收者接受该消息，并将它传给主机的时间。

WSN时钟同步算法
关于时钟同步的算法大致有两种：

一种是send-receiver模式的，比如TPSN(Timing Sync Protoco lfor Sensor Networks)，它分为两步，第一步是先建立层关系结构，再在每层之间用send-receiver算法同步(可以考虑使用RBS算法)。第二步主要思想如下(也就是这种模式的核心思想):

节点A在T₁时刻给节点B发送一个包，节点B在T₂时刻收到该包，在T₃时刻返回一个响应包给A，节点A在T₄时刻收到该响应包。那么在假定来回传输延迟固定和相对漂移为1的情况下，我们可以假设相对偏移为$，传输延迟为d，那么:

这样如果A和B需要同步，那么就可以将A的时钟加上$就可以了。

还有Tiny-Sync and Mini-Sync，它利用线性拟合得出节点间时钟的相对漂移和相对偏移的范围，当然已经有人提出改进的版本，这里就不详细介绍了。

另外一种是receiver-receiver模式的，比如RBS算法。它的思想是两个节点通过交换第三者传送过来的信号的时间来得出时钟关系。目前已经对它提出了改进。这种同步算法精度高，但是比起前面的算法消息复杂性高。还有另外一些算法，比如使用贝叶斯估计的算法SAITS。我们给出的算法都是假设相对时钟漂移为1的，当然可以根据Least Squares Linear Regression求出节点间的相对时钟漂移。

在[4]中Multihop的情况下，以节点为顶点，如果节点之间可以通信就建立一条边，E为两个节点间允许的最大同步误差(可以由历史记录的线性拟合剩余误差来决定)，则可以取E为边权，建立无向图，使用Dijkstra算法来找到最佳的同步路径。在[7]中提到在全局同步中，联合所有需要同步的节点，找具有最早期限(因为有些节点更需要立即同步)而且需要同步的节点数最多的作为同步转换路径。同时[4]中提到，前面的思想都需要利用全局信息，不具有可扩展性，因而可以利用包来传送转换参数以达到时钟同步。

利用节点移动性来传递时钟信息

在[1]中作者提到，节点移动情况下，可以使用节点的移动来传递时钟信息，以达到时钟同步。在[10]中，Arnab给出了一个利用sink节点的移动来节能的模型:sink节点具有很强的能量供给并且它环绕整个网络移动，只有当它处在普通传感器节点的通信范围内时，普通节点才可以发送数据给它(其余时间普通节点处于sleep状态)。下面我们要讨论的同步是两个节点之间的时钟同步。

定义A和B同步:如果A和B之间可以直接通信，那么将A的时钟调整到B的时钟步调上，而B的时钟保持原来的步调。

算法A1。利用节点的移动性，如果需要同步的节点之间距离比较近，但是它们无法直接通信，则可以通过移动其中一个节点的邻居到另外一个节点的通信范围来传递时钟信息。比如节点A需要和节点C同步，假设节点B在它们之间移动(人为控制移动)，那么当B和A可以通信时，B先和A同步；当B出现在C的通讯范围内时，将C和B同步。这样C和A就达到同步。

算法A2.如果需要同步的节点之间距离比较远，而且没有在两者之间直接移动的节点，那么我们可以利用接力赛的思想，来实现逐跳同步。比如节点A需要和节点C进行同步，那么在A和偏方向(可以由相对位置来确定)的邻居B₁之间运用算法A1使B₁和A达到同步，然后在B₁和偏方向的邻居B₂之间运用算法A1(如果需要节点移动，那么本次使用的移动节点应该和上次不同，因为节点移动非常耗能，过多的移动会使节点更早死亡)，将B₂和B₁同步。依次类推，直到C与A达到同步。(伪代码省略)

算法A1伪代码:
A1(A，C，B)//将C通过A和B同步
{
ifcommunicate(A，C)//A和C可以直接通信
then{
　sync(A，C);//将A和C同步
　exit;//成功退出
　　　 }
else{
choosingA’sneighborB;//任选A的邻居B
sync(B，A);//将B和A同步
move(B，C);//将B移动到C的通信范围内
sync(C，B);//将C和B同步
}

算法A3.在整个网络中均匀部署若干电池能量相对较多的漫游节点，利用[10]中给出的移动的sink节点定期对它们进行同步训练，这样普通传感器节点只需和漫游节点同步，从而可以加快节点的同步速度。如图1，实心矩形和曲线表示漫游节点及其轨迹，实心椭圆表示传感器节点，空心椭圆表示漫游节点。一种特殊情况就是如果A需要和C同步，那么A和M1同步，C和M2同步，而M1和M2本来已经同步，这样A和C达到同步。但是，如果B和C需要同步，那么B先发一个hello消息给它的所有邻居，询问它们周围有无漫游节点；A收到该消息后，发现自己通信范围内出现漫游节点M1，那么将本身和M1同步；最后使B和A同步。这样我们通过一跳询问，就找到了漫游节点，而实际应用中，我们可能需要通过多跳询问来达到目的。

图1　漫游节点示意图

搜索漫游节点的伪代码：

While((k {k++; //k 0是节点发送hello消息的最大允许跳数
　if 发现漫游节点then found = true;
}

算法A4.在二层网络架构中，如果两个节点需要同步，类似利用两次握手，再加上簇头间的同步操作，来实现multihop同步。(已经在二层架构下实现)

图2　二层架构下的移动sink节点

算法A5.在二层网络架构中，我们同样可以用[10]中给出的移动的sink节点定期对簇头进行同步训练；这样如果两个节点之间需要同步，那么它们只需要和簇头进行同步操作即可。如图2，当sink节点在M附近时，M和它同步；当sink节点移动到N附近时，N和它同步。这样，如果普通节点A和B需要同步，只需A和M同步，B和N同步即可。

算法分析

定义算法成功：执行时钟同步算法最终达到同步。

定理1.节点之间存在路由的概率是P_r，A₂成功的概率是P₂那么它们满足P_r≤P₂。

证明：对于节点密集的WSN，任选两个节点A和C，如果它们之间存在路由，则执行A₂一定能够找到同步路径，并最终达到同步；如果执行A2最终成功，那么中间节点的移动可能贡献一部分，而此时A和C之间并不一定有存在路由。因此P_r≤P₂。证毕

因为传感器网络是高密度的，所以节点之间的连通性是可以保证的，即节点间都存在路由。定理1中Pr可以近似为1，那么A₂一定能成功，同理我们可以证明A4也一定能成功。

定理2.针对A₃，我们假设节点的最小距离为通信半径RC，漫游节点数目为M，整个有效区域的面积为S，则当传感器网络规模相当大时，如果满足那么执行A3一定能成功。

证明：任选节点A和C，它们执行算法A4成功，等价于在某一时刻，有两个漫游节点分别出现在它们的k0跳通信范围内(假设概率为P)，因为漫游节点位置满足均匀分布，所以A(或者C)通过k0跳搜索而发现漫游节点的个数是M*P(k0RC)²/S(一般不超过1)，那么

考虑到传感器网络规模相当大，那么所放置的漫游节点数目也是相当大的(M-1≈M)，上式中P=1时，

实际中，我们不可能在目标区域中设置大量的漫游节点，因为节点移动非常耗能，但是我们可以通过设置k0来控制它的数目。

算法模拟

我们模拟的平台是ns2。
先模拟算法A2。我们将100个传感器随机分布在平面上，任意选取10对节点，分别测量它们路由存在的百分比(图中下面的曲线)和执行A2成功的百分比(图3中上面的曲线)。

图3　执行算法A2成功的概率和路由存在的概率的对照

我们可以发现，执行算法A2成功的可能性始终大于路由成功的概率，满足理论分析。

再来模拟算法A3。我们将1000个传感器节点随机均匀的布置在S=3000×400的区域内，在其中任意选取30对节点用来做实验；假设节点的通信半径RC为100，取k₀为2，π=3.14159；漫游节点均匀布置且数目从3开始增加到10，可以得出30对节点执行算法A3成功的百分比跟加入的漫游节点数的关系(图4)。从图中，可以看出当漫游节点数目等于10时，执行算法A3成功的概率将近，即在这时30对节点中，28对成功达到同步。实际中，我们需要比预算投入更多的漫游节点。

图4　执行算法A3达到同步的

节点百分比和加入漫游节点数目的关系最后，我们对算法A4和A5分别进行了模拟，结果发现算法A5的同步操作速度明显高于已有的算法A4(我们这里不给出模拟数据)。

结论和将来的工作

本文深入研究了如何利用节点的移动来传递时钟信息，并结合接力赛的思想和sink节点的移动来传递时钟的模型，提出了一些算法，并做了分析和模拟。在实际的大规模网络中，如何根据具体的应用和网络拓扑将这几种算法思想结合起来以完成节点间的同步，成了我们今后的工作。

References:
[ 1 ] Sivrikaya, F ik ret Yener, Bulent. T ime synch ronization in sen2so r netwo rk s: a survey [ J ]. IEEE N etwo rk, JulyöA ugust,2004, 18 (4) : .

[ 4 ] Elson J , Girod L , Estrin D. F ine2grained time synch ronizationusing reference broadcasts [C ]. P roc. 5th Symp. Op. Sys. De2sign and Imp lementation,Bo ston, MA , Dec. 2002.

[ 7 ] V an Greunen, Jana (U niversity of Califo rnia, Berkeley ) ;Rabaey, Jan Source. L igh tweigh t time synch ronization fo r sen2so r netwo rk s[C ]. P roceedings of the Second ACM Internation2alWo rk shop on W ireless Senso r N etwo rk s and App lications,W SNA 2003, 2003: 11219.

[ 10 ] Chak rabarty A , Sabharwal A , A azhang B. U sing p redictableobserver mobility fo r power efficient design of a senso r netwo rk[C ]. In: Second International Wo rk shop on Info rmation P ro2cessing in Senso r N etwo rk s ( IPSN ) , Palo A lto, CA , U SA ,Ap ril 2003: 1292145.