无线传感器网络同步算法的研究与探讨

摘要：时间同步是无线传感器网络进行数据融合、TDMA调度、定位等基本应用的基础。从时间同步的概念和定义出发，首先对几种经典的常用的时间同步算法及新型的萤火虫同步和梯度同步算法进行了介绍，然后主要分析分布式的时隙互同步算法，最后展望了未来时间同步算法的研究方向。
关键词：无线传感器网络；梯度同步；分布式时隙同步算法

引言
无线传感器网络技术融合了传感器、低功耗嵌入式计算器、无线网络和通信、分布式信息处理等技术，利用传感节点通过自组网络对监测对象进行实时监测、感知和采集，在环境、资源、智能交通、矿井安全等领域都有着良好的应用前景，是近年来国内外信息领域研究和竞争的焦点。而时间同步技术是无线传感器网络中一项非常关键的基础技术。网络时间协议NTP(Network Time Protocol)是传统网络的时间同步协议，最早由美国Delaware大学的Mill教授提出。然而NTP是应传统网络的能量效率、网络动态、基础设施和系统而构建，因此并不适合低功耗、低成本、微型化、高集成、协作式多跳自组织的无线传感器网络。另外，无线传感器网络时间同步算法还要考虑能量消耗、可拓展性、精确度、鲁棒性等问题，这些都对无线传感器网络的时间同步算法提出了新的要求和挑战。
在2002年的HotNets上，J Elson和Kay Romer首次提出并阐述了无线传感器网络时间同步技术的课题，在国际上引发了广泛的关注和思考，吸引了许多大学和研究机构参与研究，已经提出许多种不同的实现算法及改进算法，典型的有RBS算法、TPSN算法、还有TDP算法、FTSP算法、DMTS算法、LTS算法、TS／MS算法、HRTS算法、OFDC算法、CHTS算法、CRIT算法以及最新的基于萤火虫技术和协作技术的时间同步算法等。

1 概念与定义
在计算机体系结构中，时钟通常用品体振荡器脉冲来度量，即

式中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)=ai·t+bi (2)
由此可知，时钟ci(t)和ck(t)之间应该存在如下的线性关系：
ci(t)=aik·ck(t)+bik (3)
式中aik、bik为相对漂移量和相对偏移量。

2 典型同步算法
Elson、Girod和Estrin在参考文献中以“第三节点”实现同步的思想提出了RBS算法，这是一种基于接收者一接收者的时间同步协议。根节点周期性地向其广播域中的子节点发送不包含时间戳的参照广播(Referenccs Broadcast)消息。接收到广播消息后，邻居子节点用自已
的本地时钟记录各自的接收时刻作为参考比对时钟，然后相互交换它们记录的时间信息，这样接收节点就能知道彼此之间的时钟偏移量。然后利用式(4)计算相对其他各个节点的时钟偏移的平均值，并相应进行调整。当所有节点都获得相对其他节点的时钟偏移量平均值时，所有接收同一参照广播消息的接收节点便获得了一个相对网络时间，即：

式中：n为待同步节点数，m为参考广播的次数，Ti,k为第i个节点接收第k次参考广播的本地时刻。显然，由offset(i，j)形成的矩阵为对称矩阵，且对角线元素为0。
TPSN算法是由Ganeriwal等人提出的，是一种基于发送者和接收者的时间同步算法。采用层次型网络结构。算法分两步：首先是层次发现阶段，建立网络拓扑结构；然后每个节点与上一级的一个节点进行时间同步，最终实现所有节点都与根节点的时间同步。
FTSP协议是一种单向广播的发送者和接收者的时间同步办议。协议首先要网络动态地选择一个节点作为网络的根节点，其时间作为全网的参考时间，根节点把含有当前本地时间的信息包发送给它单跳广播域内的邻居节点；邻居节点在收到信息后分别记录相应的接收时间，采用参数拟合技术算出相对于根节点的时间漂移和时间偏移；然后这些与根节点同步了的邻居节点也作为参考节点，采用与根节点同步的相同的办法，使它们的邻居节点也实现与其同步。