免时间戳交互的无线传感网隐含节点同步参数估计算法

王恒 彭政岑 马文巧 李敏

无线传感网(Wireless sensor networks,WSNs)由负责感知和传输任务的传感器节点组成,具有功耗低、成本小、易部署的优势,被广泛应用于环境监控、工业控制等领域[1-3].时间同步是无线传感网的关键技术之一.无线传感网的许多基础功能,例如数据融合、传输调度和目标定位等,都需要节点间的精确时间同步[4-6].因此,对无线传感网中的时间同步技术进行研究和探索具有重要意义.

由于时钟的启动时刻和振荡器的变化特性不同,传感器节点时钟之间通常存在两方面的偏差.一方面是时钟的初始相位偏差,称之为时钟偏移;另一方面是时钟运行速率的偏差,称之为时钟漂移.无线传感网中的节点之间要维持高精度同步,就需要利用时间同步技术计算相对时钟漂移和偏移.如果仅对时钟漂移进行估计,那么只能校正节点之间的时钟速率偏差,而相位偏差会一直存在,导致同步无法实现.反之,若只估计时钟偏移,虽然能够校正相位偏差,但是振荡器的差异会导致同步时间较短,从而需要频繁地进行重同步.因此,为了避免上述情况的出现,就必须对时钟漂移和偏移参数进行联合估计.

无线传感网时间同步机制的设计所面临的一项重要挑战是:如何尽可能地减少同步能耗.由于网络中节点间的同步通常需要传输同步信息,而同步信息传输所需能耗占据同步能耗的绝大部分.因此,一个有效的解决方案是设计以最小化同步信息传输数量为目标的低功耗同步协议.隐含同步是其中的一个典型协议[7],它基于无线媒介的广播特性,利用监听策略隐式地获取同步信息,可以显著减少同步信息传输数量.在该机制中,一个活跃节点(既发送同步信息又接收同步信息)和一个时钟源节点之间执行双向信息交换同步操作,而一些位于这两个节点重叠通信范围内的节点(称之为隐含节点),只需监听它们之间的信息交换过程就能实现与时钟源节点的同步.在此过程中,隐含节点仅接收了信息,没有发送任何信息,大幅度地降低了同步能耗.文献[7-9]基于隐含同步机制,在不同的网络场景下,利用统计信号处理技术设计了多种同步算法,实现节点之间的高精度低能耗同步.文献[10-11]则将隐含同步机制与另一种同步机制(校正式同步)相结合,节点仅以少量的能量就能在估计时钟参数的同时校正自己的本地时钟,实现实时的同步.此外,文献[12]还将隐含同步机制应用到了水下无线传感网中,提出适用于水下传感器节点的低功耗同步算法.

免时间戳同步是近年来提出的另一种低能耗的同步机制[13-16].由于其交互过程无需时间戳,同步功能可以无缝嵌入现有网络数据流,从而能够显著减少能耗.在免时间戳同步中,首先活跃节点发送不含时间戳的数据包给时钟源节点,并记录此时的本地时间;接着时钟源节点接收到数据包后在预定义的响应时间间隔返回不含时间戳的数据包;最后活跃节点在接收到返回的数据包后记录自己的本地时间,并通过预定义的响应时间间隔规则估计时钟参数,与时钟源节点达到同步.该机制利用接收方对发送方的预定义响应时间来传递同步信息,避免了专用同步帧的传输.文献[13]提出一种基于和响应策略的免时间戳同步协议,其中时钟源节点响应时间和接收时间的和满足特定的规则.通过在两个不同的时间间隔各返回一个响应数据包,文献[14]提出一种跟随响应免时间戳同步协议.但是,由于跟随响应数据包的存在,限制了该协议在实际网络中的应用.为解决上述问题,文献[15]提出一种基于动态响应的免时间戳同步协议,利用特定的映射规则,将连续的两个或多个同步周期的响应时间设置为不同值,消除了跟随响应数据包的传输.进一步,文献[16]提出一种免时间戳交互与单向传输混合的同步机制,实现了时钟漂移和偏移的联合估计.

将免时间戳同步与隐含同步相结合,能够联合发挥两种同步机制的低能耗优势,从而进一步降低无线传感网同步能耗开销.文献[15]对其进行了初步的研究,但是,在基于动态响应的免时间戳同步方法中,隐含节点只能估计时钟漂移,不能估计时钟偏移,从而无法实现隐含节点的完全同步.因此,针对此问题,本文提出了一种在不传递时间戳的情况下,隐含节点能够联合估计时钟漂移和偏移的低功耗同步协议.主要贡献如下:

1)提出了一种基于免时间戳交互的隐含同步协议,隐含节点记录监听到数据包的本地时间戳,再结合预定义的响应规则就能完成对时钟漂移和偏移的联合估计,以少量的能耗达到与时钟源节点的完全同步;

2)针对典型的高斯随机时延,推导了隐含节点时钟漂移和偏移的联合最大似然估计器(Maximum likelihood estimator,MLE),以及相应的克拉美罗下限(Cramer-Rao lower bound,CRLB);

3)仿真结果表明,所提估计算法能够有效实现对隐含节点时钟漂移和偏移参数的免时间戳联合估计,并具有达到CRLB的优良性能.

1 同步协议描述

本节将对所提的基于免时间戳交互的隐含同步协议进行介绍,并建立节点的时钟模型.

1.1 交互过程

考虑一个由多个节点构成的无线传感网,其中节点O是时钟源节点,为网络提供参考时间;节点P是活跃节点,周期性地与时钟源节点O进行双向信息交互;节点Q是位于活跃节点P与时钟源节点O公共广播领域内的隐含节点,能够监听它们之间的信息交互过程,如图1 所示.

图1 网络结构图Fig.1 Network structure

当网络同步开始,活跃节点P与时钟源节点O之间进行免时间戳同步,隐含节点Q监听两节点的交互信息进行隐含同步.具体的同步过程如图2 所示,以第j轮通信过程为例,详细步骤如下.

图2 节点 Q 监听节点 O 与节点 P 之间的N轮免时间戳交互Fig.2 The N rounds of timestamp-free exchange between node O and P with node Q overhearing them

在上述过程中,活跃节点P与时钟源节点O之间进行免时间戳同步,隐含节点Q监听它们之间的成对信息.因此,节点Q只接收了信息,节省了由发送报文产生的能耗.

1.2 时钟模型

网络中每个传感器节点的时钟相对于理想时间都存在时钟漂移和偏移.其时钟模型可以表示为:

其中,C(t0)和t0分别表示节点的本地时间和理想时间,α和ϑ分别表示时钟漂移和偏移.

同步信息在传输过程中会经历多种时延,这些时延可分为固定时延和随机时延[17].其中固定时延包括传输时间、接收时间、传播时间,随机时延包括发送时间、接收处理时间和信道访问时间.一般情况下,固定时延被假设为一个常数,而随机时延则会根据不同的网络场景被建模为服从不同分布的随机变量.例如,延迟是由许多独立的随机过程相互叠加时,根据中心极限定理,随机时延可以被建模为高斯分布[18].此外,该随机时延模型已被实验证明是合理的[19].因此,在本文中,假设固定时延是已知常数,随机时延是独立同分布的高斯分布,其均值为0,方差为σ2.

根据时钟模型式(2),时钟源节点O在j轮同步信息交换过程中,本地时间戳可以表示为:

2 参数估计

基于上述的时间戳表达式,本节将推导隐含节点时钟漂移和偏移的联合MLE 以及相应的CRLB.

2.1 联合MLE

最大似然估计是一种能够简便地实现复杂估计问题求解的估计方法,其是利用已知的观测数据,反推最大概率产生该观测信息的参数值.无线传感网中的时间同步就是通过观测的同步信息计算时钟参数.此外,在式(13)中,Γ 是由已知观测数据构成的矢量矩阵;M是秩为2的观测矩阵; Θ 是包含2个待估时钟参数的矢量,并且与Γ呈线性关系;W是均值为0,方差为的高斯噪声矢量,其中 1 是单位矩阵,满足线性模型的最大似然估计定理.因此,根据文献[20]中的定理7.5,时钟参数矢量 Θ的MLE 为:

将式(14)进行数学运算,节点Q时钟漂移和偏移的最大似然估计器分别表示为:

所以,利用估计器(15),隐含节点Q可以估计自身的时钟漂移和偏移,达到与时钟源节点O的同步.与现有的免时间戳同步与隐含同步相结合的同步机制相比,本文所提的同步机制完成了对隐含节点完整时钟参数(时钟漂移和偏移)的估计,实现了与时钟源节点的完全时间同步.

2.2 克拉美罗下限(CRLB)

CRLB 是衡量无偏估计器性能的一个理论标准[20],无偏估计量的方差只能无限逼近或等于CRLB,而不会小于CRLB,当两者相等时,表示估计器性能达到最优.由于它容易被确定,常被用来评估无偏估计器性能的好坏,判断估计器性能是否达到了最优.为了评估所提联合MLE的性能,本节推导矢量参数的CRLB.首先需要计算2×2的费希尔信息矩阵,然后再求其逆矩阵可分别得到的CRLB.

再对式(17)～式(19)求负期望可得费希尔信息矩阵如下:

最后,求得费希尔信息矩阵的逆矩阵为:

费希尔信息矩阵的逆矩阵的对角元素即为相应参数的CRLB[20].因此,时钟漂移α(QO)和时钟偏移ϑ(QO)的CRLB 分别表示为:

3 仿真验证与对比分析

本节基于MATLAB 仿真平台,验证所提隐含节点的联合最大似然估计器的有效性.同时,在估计性能、能量开销、计算数量三个方面,将所提同步机制与现有的相关同步机制进行了对比.

3.1 仿真验证

图3 为隐含节点Q相对于时钟源节点O的时钟漂移最大似然估计器的MSE 和CRLB.从图中可以看出,时钟漂移最大似然估计器的MSE 曲线与CRLB 曲线基本重合,表明了其估计性能达到最优,同时也验证了估计器的有效性.而且随着观测次数的增加,所提估计器的估计精度不断提高.

图3 隐含节点 Q 时钟漂移估计 (QO)的MSE 与CRLBFig.3 MSE and CRLB of estimated clock skew(QO)for silent nodeQ

图4 所示为隐含节点Q相对于时钟源节点O的时钟偏移最大似然估计器的仿真结果.在图4 中,时钟偏移最大似然估计器的性能随着观测次数的增加不断提高,而且MSE 曲线与CRLB 曲线基本重合,表明该估计器的性能达到了最优,同时验证了该估计器的有效性.值得注意的是,在仿真中,系数ξ=1.4,这表明隐含节点Q在通信过程中只是获取到2/5的就以此实现了相对于时钟源节点O的时钟偏移估计.此外,时钟偏移的估计精度是影响同步精度的主要因素.因为隐含节点Q根据估计的时钟漂移与偏移调整本地时间,减小与时钟源节点O的时间偏差,而时钟漂移的估计精度比时钟偏移的估计精度高出约 1 06个数量级,其对同步精度的影响较小,可以忽略不计.所以可以利用时钟偏移的估计精度反映节点间的同步精度.从图4 中可以看出,时钟偏移的估计精度为 1 0-1数量级,而时钟偏移被设置为数ms,因此,所提同步算法可达到数百μs的同步精度.

图4 隐含节点 Q 时钟偏移估计 (QO)的MSE 与CRLBFig.4 MSE and CRLB of estimated clock offset(QO)for silent nodeQ

从仿真结果可以看出,隐含节点Q监听活跃节点P和时钟源节点O之间的免时间戳同步过程,通过观测到的数据集就可以同时估计相对于节点O的时钟漂移和偏移,达到与节点O的同步.与文献[15]中的基于动态响应的免时间戳的隐含同步方式相比,所提的免时间戳隐含同步方法继承了现有免时间戳同步和隐含同步的优势,能够大幅度地减少同步能量消耗,同时也可以无缝地嵌入到网络数据流之中.进一步,隐含节点又能够联合估计相对于时钟源节点的时钟漂移和偏移,实现隐含节点的完全同步,弥补了目前两种机制结合使用的不足.

3.2 对比分析

首先,将所提的隐含节点Q的时钟漂移最大似然估计器与类似的估计器(文献[15]中的式(26))进行估计性能比较.为了确保比较的公平性,在两种估计器的对比仿真中,各个参数的初始化设置均相同,文献[15]中两个连续周期内ACK的响应时间间隔设置为{10,30}.仿真结果如图3 所示,本文所提的隐含节点Q的时钟漂移估计器的性能显著优于文献[15]中的时钟漂移估计器,而且其估计精度大约高出101～103个数量级.其原因是所提同步机制通过预设时钟源节点O返回ACK的本地时间,传递了部分时间戳信息给隐含节点Q,时间戳信息的获取有利于时钟漂移估计精度的提高.图5 所示为不同系数ξ下时钟漂移估计器性能对比结果,其中设置ξ={1.2,1.3,1.4,1.5,1.6}.从图中可以看出,随着系数ξ的增大,所提时钟漂移估计器的估计性能不断提高,表明隐含节点Q获取的时间戳信息越多,时钟漂移的估计效果越好.同时,从仿真的角度说明,相较于文献[15]中无法获取时间戳信息的隐含节点,所提同步机制的隐含节点由于能够间接地获取部分时间戳信息,因此其时钟漂移估计器性能更优.但是,需要注意的是,不能为了提高时钟漂移的估计性能无限地增加ξ,因为ξ的取值必须确保响应时间间隔不会过大,影响网络的正常运行.

图5 不同系数 ξ 下时钟漂移估计器性能对比结果Fig.5 The performance comparison results of clock skew estimator under different coefficientξ

其次,将所提同步机制与隐含同步机制[7]、基于动态响应的免时间戳同步机制[15]进行信令流程及能耗开销对比.无线传感网的时间同步依赖于信息交互,交互流程所导致的能耗开销是影响同步能耗的重要因素.在隐含同步机制中,隐含节点监听的是传统的双向信息交互过程,需要专用的同步帧传递时间戳信息,同步帧的传输需要消耗额外的能量.在基于动态响应的免时间戳同步机制中,待同步节点无需发送时间戳信息,在普通数据收发中实现同步,无需消耗额外的能量.在所提机制中,隐含节点监听的是时钟源节点和活跃节点的免时间戳交互过程,不需要专用同步帧,没有额外的能量开销.因此,相较于隐含同步机制,所提机制避免了网络中专用同步帧传输,显著减少了能耗.与免时间戳机制相比,所提机制能够一次性实现公共广播领域内多个节点的同步,而免时间戳机制只能实现一个节点的同步,对于网络整体的能耗而言,所提机制更具优势.

最后,分析所提同步算法、隐含同步算法[7]、基于动态响应的免时间戳同步算法[15]以及免时间戳与隐含同步结合算法[15]的计算复杂度,主要是对算法中加法和减法、乘法和除法计算数量进行比较,对比结果如表1 所示.从表中可以看出,4 种同步算法时钟参数的计算复杂度均为 O (N2).而本文算法时钟参数乘除法的计算数量高于隐含同步算法和免时间戳同步算法时钟参数计算数量,这是因为时钟源节点O返回ACK的本地时间中包含系数ξ,导致算法中乘除法的数量相对较高.Wang等[16]研究表明,传输1 比特数据超过100 米消耗的能量与执行300 万条指令所需能量大致相等.因此,虽然本文算法的计算数量略高,但能够在不传输专用同步帧的情况下实现多个节点的同步,它仍然是一个高能效的同步方案.相较于文献[15]中的免时间戳与隐含同步结合算法,本文算法时钟漂移的计算复杂度略低于其时钟漂移计算复杂度,而且本文算法还可以估计时钟偏移,实现完整的同步.

表1 本文算法与隐含同步算法、免时间戳同步算法以及免时间戳和隐含同步结合算法的计算数量对比结果Table 1 The comparison results of the number of calculations among proposed algorithm,implicit synchronization algorithm,timestamp-free synchronization algorithm and combination algorithm of timestamp-free and implicit synchronization

4 结论

本文提出了一种能够联合估计免时间戳同步场景中隐含节点的时钟漂移和偏移的同步协议.在高斯随机时延下,推导了隐含节点时钟漂移和偏移的最大似然估计器和相应的CRLB.最后,通过数值仿真验证了所提估计器的有效性,并且与现有的相关同步方案在估计性能、能量开销和计算数量三个方面进行了对比,论证了所提方案低功耗的优势.