同闪灯时间同步算法

摘要：太阳能同步道钉及太阳能同闪边界led 灯，是指离散安装的太阳能同时闪烁led 灯采用统一的闪烁频率、占空比，在协调统一的状态下同步工作。它能够以最佳的视觉效果显示道路走向及道路障碍物位置等。太阳能同时闪烁led 灯时间同步算法是最新的时间同步技术。最近几年，许多基于时间信息交换的时间同步协议已被提出.然而，在大规模无线网络中，同步误差随跳距的累积问题和可扩展性需求是传统的时间同步技术面临的主要挑战.为了应对这两个挑战，提出系统时间特征修正同步算法.本文探讨系统时间特征修正同步算法，最后展望了未来时间同步算法的研究方向。

引言

　　无线网络时间同步技术融合了低功耗嵌入式cpu、无线网络和通信、分布式信息处理、系统时间特征修正同步算法等技术。在环境、资源、智能交通、矿井安全等领域都有着良好的应用前景，是近年来国内外信息领域研究和竞争的焦点。而时间同步同步算法是无线传感器网络中一项非常关键的基础技术。网络时间协议NTP[1](NetworkTime Protocol)是传统网络的时间同步协议，最早由美国Delaware大学的Mill 教授提出。然而NTP 是应传统网络的能量效率、网络动态、基础设施和系统而构建，因此并不适合低功耗、低成本、微型化、高集成、协作式多跳自组织的无线传感器网络。另外，无线传感器网络时间同步算法还要考虑能量消耗、可拓展性、精确度、鲁棒性等问题，这些都对无线传感器网络的时间同步算法提出了新的要求和挑战。

　　在2002 年的HotNets 上，J Elson 和Kay Romer 首次提出并阐述了无线传感器网络时间同步技术的课题，在国际上引发了广泛的关注和思考，吸引了许多大学和研究机构参与研究，已经提出许多种不同的实现算法及改进算法，典型的有RBS 算法、TPSN 算法、还有TDP算法、FTSP 算法、DMTS 算法、LTS 算法、TS/MS 算法、HRTS 算法、OFDC 算法、CHTS 算法、CRIT 算法以及最新的基于萤火虫技术和协作技术的时间同步算法等。结合这些特点我们提出了系统时间特征修正同步算法，并且在我们的产品上得到了实现。

　　1 时间同步的概况

　　在嵌入式cpu 应用结构中，时钟通常用晶体振荡器脉冲来度量，即

       式中C(t)为构造的本地时钟，t 为真实时间变量，k 为依赖于晶振的物理特性常量，ω(τ)为晶振的频率，间隔c(t)-c(t0)被用来作为度量时间。对于理想的时钟，有r(t)=dc(t)/dt=1，也就是说，理想时钟的变化速率r(t)为1。但在工程实践中，因为温度、压力、电源电压等外界环境的变化，往往会导致晶振频率产生波动。因此构造理想时钟比较困难，但在一般情况下晶振频率的波动幅度并非任意的，而是局限在一定范围之内。为了方便描述与分析，定义了速率恒定模型、漂移有界模型和漂移变化有界模型。

       假定c(t)是一个理想的时钟。如果在t 时刻有c(t)=ci(t)，则称ci(t)在t 时刻是准确的；如果dc(t)/dt=dci(t)/dt，则称时钟ci(t)在t 时刻是精确的；如果ci(t)=ck(t)，则称时钟ci(t)在t 时刻与时钟ck(t)是同步的。上述定义表明，两个同步时钟不一定是准确或精确的，时间同步与时间的准确性和精度没有必然的联系。

       如果采用时钟速率恒定模型，由式（1），时钟ci(t)可以简化表示为：

       由此可知，时钟ci(t)和ck(t)之间应该存在如下的线性关系：

       式中aik、bik 为相对漂移量和相对偏移量。

2 典型同步算法

       Elson、Girod 和Estrin 以“第三节点”实现同步的思想提出了RBS 算法，这是一种基于接收者接收者的时间同步协议。根节点周期性地向其广播域中的子节点发送不包含时间戳的参照广播（References Broadcast）消息。接收到广播消息后，邻居子节点用自己的本地时钟记录各自的接收时刻作为参考比对时钟，然后相互交换它们记录的时间信息，这样接收节点就能知道彼此之间的时钟偏移量。然后计算相对其他各个节点的时钟偏移的平均值，并相应进行调整。

       TPSN 算法是由Ganeriwal 等人提出的，是一种基于发送者和接收者的时间同步算法。采用层次型网络结构。算法分两步：首先是层次发现阶段，建立网络拓扑结构；然后每个节点与上一级的一个节点进行时间同步，最终实现所有节点都与根节点的时间同步。

       FTSP 协议是一种单向广播的发送者和接收者的时间同步协议。协议首先要网络动态地选择一个节点作为网络的根节点，其时间作为全网的参考时间，根节点把含有当前本地时间的信息包发送给它单跳广播域内的邻居节点；邻居节点在收到信息后分别记录相应的接收时间，采用参数拟合技术算出相对于根节点的时间漂移和时间偏移；然后这些与根节点同步了的邻居节点也作为参考节点，采用与根节点同步的相同的办法，使它们的邻居节点也实现与其同步。

       萤火虫同步技术和协作同步技术是为了实现节点的同步性，即使节点的某些周期性动作具有相同的周期和相位，例如使一群萤火虫同步闪烁并且闪烁周期相同。1990 年，Mirollo 和Strogatz 在Peskin模型的基础上提出了更一般的脉冲耦合振荡器模型（后简称为M&S 模型）。并在无线多跳网络测试床Gains 上实现了M&S 模型的萤火虫同步算法。

        目前的萤火虫同步算法的一个限制是要求每个节点具有相似性，但这种机制在非相似节点所组成的网络下能否起到同步的作用，目前还不清楚，萤火虫同步的理论研究还远未结束。

3 同步技术现状分析

       同步技术包括频率同步技术和时间同步技术两个方面，其中频率同步技术比较成熟不再赘述，下面将就无线网络对时间同步的需求和在无线网络中得到应用的现有时间同步技术展开分析。

3.1 时间同步需求

       时间同步在无线网络中有着越来越广泛的需求，各种无线网络对时间同步的需求可分为高精度时间需求(微秒级和纳秒级)和普通精度时间需求(毫秒级和秒级)。对于太阳能同步道钉及太阳能同闪边界led 灯，时间同步的要求是20ms；如果太阳能同步道钉及太阳能同闪边界led 灯的时间同步不能达到上述要求，将可能导致同时闪烁不能正常建立。无线传感器网络的最常见的几种同步算法的性能比较如表1所列。

表1  几种常用时间同步算法的性能比较

       由于无线传感器网络节点配置低，节点晶振漂移现象严重，为了保证节点间能以一个统一步调运作，必须对各节点进行定期时间同步。时间同步对时间敏感监测应用非常关键，同时它也是一些依赖于局部同步或全局同步的网络协议设计的基础。传统因特网上的时间同步技术由于实现复杂及开销大不利于无线网路应用。例如J.Elson等人提出了一个基于广播参考的时间同步算法（Reference-Broadcast Synchronization，RBS），该算法与传统的由一个服务器广播同步信号给多个客户进行时间同步的思想不同，在该算法中，相邻节点间定期广播参考信号，各节点以自己的时钟记录事件，随后用接收到广播的参考时间加以校正。这种同步算法应用在确定来自不同节点的监测事件的先后关系时有足够的精度。

4 系统时间特征修正同步算法

4.1太阳能同步道钉及太阳能同闪边界led 灯的同步的硬件软件等资源限制

(1)硬件资源有限。节点由于受价格、体积和功耗的限制，其计算能力、程序空间和内存空间比弱很多。这一点决定了在节点操作系统设计中，协议层次不能太复杂。

(2)电源容量有限。节点由太阳能电池和镍氢电池供电，电池的容量不是很大。其特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，因此在设计过程中，任何技术和协议的使用都要以节能为前提。

(3)无中心。无线网络中没有严格的控制中心，所有结点地位平等，是一个对等式网络。结点可以随时加入或离开网络，任何结点的故障不会影响整个网络的运行，具有很强的抗毁性。

(4)自组织。网络的布设和展开无需依赖于任何预设的网络设施，节点通过分层协议和分布式算法协调各自的行为，节点开机后就可以快速、自动地组成一个独立的网络。

(5)多跳路由。网络中节点通信距离有限，一般在几百米范围内，节点只能与它的邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信，则需要通过中间节点进行路由。无线网络中的多跳路由是由普通网络节点完成的，没有专门的路由设备。这样每个节点既可以是信息的发起者，也是信息的转发者。

(6)动态拓扑。无线传感器网络是一个动态的网络，节点可以随处移动；一个节点可能会因为电池能量耗尽或其他故障，退出网络运行；一个节点也可能由于工作的需要而被添加到网络中。这些都会使网络的拓扑结构随时发生变化，因此网络应该具有动态拓扑组织功能。

(7)节点数量众多，分布密集。为了对一个区域执行监测任务，往往有成千上万传感器节点空投到该区域。传感器节点分布非常密集，利用节点之间高度连接性来保证系统的容错性和抗毁性。

       时间同步不确定性的影响因素因受到各种器件、负载，报文传输延迟的不确定性的影响，主要的影响因素如图1 所示。

1) 发送时间(Send time)：发送方用于构造分组，并将分组转交给发送方的MAC(Medium Access Control)层的时间。主要取决于时间同步程序的操作系统调用时间和处理器负载等。

2) 访问时间(Access time)：分组到达MAC 层后，获取信道发送权的时间。主要取决于共享信道的竞争、当前的负载等。

3)传送时间(Transmission time)：发送分组的时间，主要取决于报文的长度等。

4)传播时间(Propagation time)：分组离开发送方后，并将分组传输到接收方之间的无线传输时间。主要取决于传输介质、传输距离等。

5) 接收时间(Reception time)：接收端接收到分组，并将分组传送到MAC 层所需的时间。

6) 接受时间(Receive time)：处理接收到分组的时间。主要受到操作系统的影响。

4.2系统时间特征修正同步算法

4.2.1系统时间特征算法简介

为了方便描述本文所提出的算法，以5 个节点为例，如图所示：

      实线表示节顺序节点关系，虚线表示节点在通信范围内可以侦听到的节点， A 节点通过使用NLDE—DATA.request 原语，并设置DstAddr 参数为0xffff(广播网络地址)广播形式发送时间同步组包命令，包含自身的时间特征信号Tm，同步包中包含了A 节点的层次号0 与节点A 的ID 号，每一个节点都是其下一跳同步节点，当B 节点收到A 节点发送的广播组包后，记下自己的层次号为1，父节点的ID 号为A，同样B 节点也以广播的方式发送同步组包，C,D 两个节点收到B 节点的广播请求后，分别记下自己的层次号为2、3 父节点的ID 号为B。5 个图2 节点实验组网图节点组成1个路由表。各个节点接收到相邻居的节点Tm 后，算出本组时间特征Tm1，发送出去。并在组内快速形成同步闪烁。当接收到其他组发来的Tm 后，算出经过修正的Tm，此时的Tm 为系统特征，注意系统时间特征是动态特征。

       当系统经过多次系统特征建立过程后，系统特征越来越趋向稳定。

4.2.2 系统时间特征修正同步算法

      系统时间特征修正同步算法参考于RBS 与TPSN 2 种同步算法的原理，在组网中综合运用了2 种算法的特点，设计算法原理图如图3所示。

      首先对于路由节点B 的同步，采用类似于TPSN 算法，节点B在本地时钟为T1 时发送同步请求包，请求包中包括了节点B 的层次号1 与时钟T1，当参考节点A 收到同步请求包时，记下本地时

钟为T21，并在本地时钟为T3 时发送同步应答包，应答包中包括了节点A 的层次号，T1,T21,T3。节点B 在本地时钟为T41 时收到应答包。假设来回报文的传输延迟相同，都为d，且m 为节点B 在T1 时刻与节点A 的时偏，设来回时偏相同，由T 21 = T1+ m + dT = T 3 . m +d 可得到：

则在T41 时,41 刻，若在节点B 的本地时间增加修正量m，就能达到节点B 与参考节点A 之间的同步。

        对于终端节点C 与D，采用类似于RBS 的算法，当节点B 在T1 时刻发送同步请求包时，因节点C 与D 都在侦听的范围内，当节点C 收到请求包时，记下本地时钟为T22，当节点D 收到请求包时，记下本地时钟为T23，修正Tm。当节点A 发送同步响应包时，因节点C 与D 都在侦听范围内，当节点C 收到响应包时，记下本地时钟为T42，修正Tm。当节点D 收到响应包时，记下本地时钟为T43，修正Tm。因响应包中包括了节点A 的层次号，T1,T21,T3，设节点C 与节点A 的时偏为m1，则节点C 可以根据m1=T22-T21 来修改自己的本地时钟和Tm。设节点D 与节点A 的时偏为m2，则同样节点D 也可以根据m2=T23-T21来修改自己的本地时钟和Tm 。

4.2.3系统时间特征算法和节点个性时间特征修正同步算法

        假设网内任意节点C，对应其所有的邻居节点的时隙差值为Δt，可以算出所有邻居节点的时隙偏差值的加权平均值为εi，时隙修正量ω（n）。节点互同步过程如图所示，假设节点D 能感知其邻居节点（节点A、节点B、节点D、节点E）的参考时隙偏差Δt1(n)、Δt2（n）和Δt3(n)，Δt4(n)，从而计算出自己的个性时间特征时隙调整量：

ε5=ω1×0+ω2×Δt2(n)+ω3×Δt3(n)+ω4×Δt4(n)+ω5×Δt(n)

        式中ω1+ω2++ω3+ω4+ω5=1，然后计算出系统时隙特征：

Tm5(n+1)=Tm5(n)-E5(n)

        即可根据和邻居节点的系统时隙特征，选择合适的时隙修正量使全网时间同步。为了理论分析，可以认为时间基准偏差εi 是该节点i 与全网所有节点时隙偏差的加权平均值，不连通节点的权值为0，即εi(n)=ΣTm=1ωkΔtik(n)，式中N 为网络的节点数。一种可行的权值选择方法是采用邻居节点的算术平均法，把相邻的节点的时隙偏差算术平均后作为时隙的修正量。对此算法的收敛性的实测得出，随着节点覆盖半径的提高，每个节点的连通度增大，网络的最大跳数变少，因而收敛速度提高。算法平均迭代5 次可以达到最大时隙偏差收敛。

5 总结及展望

       本文从时间同步的概念出发，首先简要介绍了几种典型的时间同步算法及分析了他们的优缺点，并对它们的时间同步算法的性能进行了综合比较，然后还介绍了与传统基于时间信息交换的时间同步算法的新技术：系统时间特征修正同步算法。虽然目前对于无线网络时间同步算法的研究已经取得了如此大的进展，并设计出来太阳能同步道钉及太阳能同闪边界led 灯。

       采用固定的时隙调整时，根据节点间时隙基准是超前还是滞后来调整时隙基准。基于分布式一致的无线传感器网络的时间同步协议的收敛和加速问题研究中，将分布式一致的收敛和加速问题映射到马尔科夫链的状态转移过程，但是排除了连通度对收敛速度的影响，得出收敛速度与节点邻居数和网络规模有关的结论，并通过100 个节点组网实验得出了可以降低25%的迭代数的结论。

实测结论

       功耗：一次饱和充电最长使用120 小时，最短使用95 小时；

       同步精度：实测小于20ms；

       同步距离：连续10 公里铺满，间隔30 米，48 小时同步误差小于20ms。

       通过我们设计的太阳能同步道钉及太阳能同闪边界led 灯的实际使用情况证明，我们的系统时间特征修正同步算法性能稳定，同步准确，同步距离可以不受限制的安装，打破了市场上已有的同步频闪灯在安装距离上的限制，真正实现了在浓雾天气，漆黑的夜晚安全引导车辆的作用。相对只在路口，拐弯等地方安装的产品，应对恶劣天气的能力大大提高。

其他用途

       无线网络时间同步技术还被应用于其他一些领域。比如一些危险的工业环境如井矿、核电厂等将可以大大改善工厂的运作条件。它可以大幅降低检查设备的成本，同时由于可以提前发现问题，因此将能够缩短停机时间，提高效率，并延长设备的使用时间。尽管无线传感器技术目前仍处于初步应用阶段，但已经展示出了非凡的应用价值，相信随着相关技术的发展和推进，一定会得到更大的应用。