无线传感器网络中基于簇结构的双向同步算法

无线传感器网络中基于簇结构的双向同步算法

1节点月间信息同步校正时间同步是无线传感器网络的一项基本技术支持技术。在无线传感器网络的应用中,传感器节点采集的数据如果没有空间和时间信息是没有任何意义的。准确的时间同步是实现传感器网络自身协议的运行、定位、多传感器数据融合、移动目标的跟踪、基于的协议以及基于睡眠/侦听模式的节能机制等技术的基础。面向无线传感器网络的时间同步协议按照一对节点的同步方式可以分为参考广播同步、单向同步和双向同步3类。参考广播同步算法需要第三方发送参考广播,并且进行同步的各接收节点需要交互大量的参考广播的时间信息并进行偏移矩阵计算,对节点能耗和计算能力要求较高。双向时间同步可以准确估计无线传输延迟,但是仍不可避免过多报文交互使节点能耗较大的问题。单向同步算法以单向广播时间信息进行同步,相对双向报文交互极大降低了能量消耗,但是在无线传播延迟较大场合,如水声通信,单向同步算法将无法获得可靠的同步。本文通过节点间的时钟频率偏移和相位偏移进行最大似然估计并获得同步校正算法,网络结构采用分级分簇的树形拓扑网络,簇内节点通过监听簇头节点的主动双向同步过程完成被动的双向同步,最终实现全网时间同步。基于频偏和相偏的同步校正算法提高了网络的同步精度,分级分簇的树形拓扑结构以及主动双向同步和被动双向同步结合的模式相对于传统的双向同步算法极大地降低了同步报文开销,适用于对于同步精度和能耗要求较高的网络。2节点本地时间同步算法传感器网络中节点的物理时钟依靠对自身晶振中断计数实现。晶振的频率误差和初始计时时刻不同,使得节点之间物理时钟不同步。如果能估算出物理时钟之间的关系,就可以构造对应的逻辑时钟以达成同步。一般来讲节点的本地时间都是采用晶振进行计时,而高精度的时钟对应较高的能量消耗,另外不同厂商生产的晶振稳定性不同,晶振稳定性越高意味着更高的价格。衡量晶振稳定性以ppm(μs/min)为单位,也就是每秒钟偏差1μs,通常普通的晶振偏移在20至50个ppm(μs/min),也有一些带有温度补偿的高可靠晶振偏差仅仅有1.5个ppm(μs/min)左右。实际应用中根据需要权衡使用,另外由于温度和环境的变化,以及设备的老化等原因也会引起时钟偏差,使得节点在运行过程中产生时钟漂移,因此在设计时间同步协议的过程中要合理考虑这些因素,提高算法的可靠性和适应性。定义t为实际时间,用T(t)表示节点本地时间,而且根据节点时间特性,T(t)>0,且T(t)为增函数,假设存在标准的不存在偏差的时钟,那么dT(t)/dt=1,但实际上用于计时的晶振都存在偏差,由此可以定义时钟偏移率为:ρ(t)=dΤ(t)dt-1,|ρ(t)|<ρ0(ρ0ρ(t)=dT(t)dt−1,|ρ(t)|<ρ0(ρ0为一常数)而且由T(t)为增函数的特性可以得出:-1<ρ(t),∀t令f(t)=dT(t)/dt,那么节点本地时钟T(t)可以表示为:Ti(t)=∫tt0tt0fi(τ)dτ+Ψi(t0)(1)通过对式(1)进行泰勒级数展开得到本地时间表示为:Ti(t)=βi+αit+γit2+…(2)式(2)中i为节点顺序,β为本地时间和实际度量时间t之间的偏移量,α为时钟飘移率,γ为二次项系数,可以表征时钟的动态变化。如果式(2)中二次项以上的系数都为0,那么式(2)可以简化为线性模型:Ti(t)=βi+αit(3)目前大多数时间同步算法都是基于线性模型的算法。如果节点工作环境变化较大,而且系统对时间同步精度要求较高的情况下,时间同步算法需要考虑高次项系数,这样相应地也增加了计算开销。对于环境相对稳定的系统,节点的频率偏差由晶振的制作工艺决定,而偏移量是固定不变的。3基于馅料双向时间同步策略通过第2节的分析,节点间的时钟不仅存在表征时间值差异的相位偏移和表征时间快慢的频率偏移,进行节点间的同步研究需要很好地处理节点间的相偏和频偏。如果所有节点出厂时的晶振频率都是相同的,并且在使用过程中不随时间漂移,一次同步就可以完全同步2个节点的时钟。但实际上由于出厂时晶振频率的微小差异及外部环境带来的漂移,在一段时间后,原本已经时间同步的2个节点将不再时间同步,如图1所示。在t1时刻,节点A和B之间的本地时钟差异为DA->Bt1A−>Bt1;在t2时刻,A与B间的本地时间差异变为DA->Bt2A−>Bt2,并且DA->Bt2A−>Bt2=DA->Bt1A−>Bt1+RDA->Bt1->t2A−>Bt1−>t2。其中,RDA->Bt1->t2A−>Bt1−>t2部分是由t1到t2的晶振频率的差异引起的。对于频率偏差为30ppm(μs/min)的晶振,每秒会产生约30μs的时间偏差,这就意味着要使2个节点的同步精度控制在30μs以内,同步频率必须大于1Hz,这将给网络带来非常大的通信开销。但是,如果使用较长的同步周期,则必须估计2个节点之间的频率漂移因素才能获得较高的同步精度。因此,采用双向时间同步对节点间频率偏差和相位偏差进行修正,结合已有的MAC层时间戳处理方法,建立一套基于簇状结构的时间同步方法。网络中各簇的簇首使用直接的双向同步与同步源进行同步,其他簇内节点通过监听簇首的同步过程间接地进行双向时间同步,以此达到全网高精度的时间同步。本文的HTSP算法采用基于簇结构的直接双向时间同步和间接双向时间同步的方法相对于传统的时间同步算法具有更高的优势。相对于RBS算法避免了大量时间相关报文的交互和高复杂度的运算。相对于TPSN算法尽管HTSP保持了双向时间同步特征,但由于采用了间接双向同步报文同步方法,极大地降低了同步过程中报文的消耗,在保证同步精度的情况下具有更好的能量有效性。相对于单向时间同步算法如FTSP本文同步算法具有更大的适应性,适用于无线传播延迟较大的场合如水声通信等。3.1节点时钟差异通过模型(3)可以看出不同节点间的时钟存在常数项的差异即相位偏移(简称相偏),以及时间频率的差异即频率偏移(简称频偏)。目前用于校正相偏和频偏的方法较多,RBS算法中节点间交互接收到基准节点的时间信息,通过这种方式,接收节点能够知道彼此之间的时钟偏移量,然后利用偏移矩阵计算相对于所有其他节点时钟偏移的平均值;TPSN通过双向的报文交互,估算出节点间的传输延迟,获得更为精准的节点间的相偏;FTSP使用线性回归的方式对节点间的频偏进行校正。本文通过最大似然估计对节点间的相偏和频偏进行校正,从而获得更精准的时间同步。图1给出同步校正频偏和相偏原理图,节点A与节点B之间不仅存在着时钟的相位偏差θ1,而且存在时钟之间的频率偏差θ2,正是频率偏差的作用使得节点之间的相位偏差在不断地增大。节点A和B之间时间的精确同步,需要通过N次的报文双向交换来实现。如图2所示,时间值T1,q、T4,q、T5,q是由节点A的时钟测得的,时间值T(R)2,q(R)2,q、T(R)3,q(R)3,q、T(R)6q(R)6q是由节点B的时钟测得的,其中q表示时钟同步过程的轮序号。其中θ(R)1(R)1表示绝对的时钟相位偏差,θ1表示在T(R)3,1(R)3,1时刻的相对的时钟相位偏差。假设d为报文传递过程中时间延迟的固定部分(如电波在空中的传播时间),而Xq和Yq分别表示报文M2和M3传递过程中,时间延迟的随机部分。节点时钟之间的时间差异由相位偏移和频率偏移共同作用的结果,而且这里的相位偏差相当于初始相位偏差。节点之间时间差异的逐渐增大很大程度上取决于时钟之间的频率偏差。由于石英晶体的工作频率各不相同,节点间的时钟差异是单调递增的(或者暂时性的递减,后递增)。所以在图1中,第1次和第N次报文交换中得到的时间戳之间的时钟差异最大。定义式(4)形式如下:D(j)≜Ν∑i=2Dj,i=Τj,Ν-Τj,1(4)图2中X和Y都是报文传递过程中的随机延时,由于无线信道的链路复杂性,可以将X、Y看作是很多独立同分布的随机延时的累积。根据中心极限定理,对于大量的独立同分布的随机变量的和的概率密度函数接近于高斯随机变量。通过对随机变量的分析转化可以获得如式(5)所示的似然函数。L(θ′2,δ2)=14πδ2e-[D2(4)(θ′2-D(3)/D(4))2+D2(5)(θ′2-D(6)/D(5))2]/4δ2(5)对式(5)取自然对数,并令其对数等于0,则得到θ′2的最大似然估计为:ˆθ′2=D(3)D(4)+D(5)D(6)D2(4)+D2(5)(6)式中:θ′2≜11+θ2。由此可以得到θ2的最大似然估计如式(7)所示:ˆθ2=1ˆθ′2-1=D2(4)+D2(5)D(3)D(4)+D(5)D(6)-1(7)同理对相偏θ1的似然函数如式(8)所示:L(θ1,μ,δ2)=-1/2πδ2e-[Ν∑q=1(U′q-d′-θ1-μ)2+Ν∑q=1(V′q-d′+θ1-μ)2]/2δ2(8)对似然函数的取对数形式并令其等于0可以得到相偏的最大似然估计形式如式(9)所示:ˆθ1=ˉU′q-ˉV′q2(9)式中:U′q=Τ4,q-(1+ˆθ2)Τ3,q‚ˉU′q=1Ν-1Ν∑q=2U′q‚V′q=(1+ˆθ2)Τ6,q-Τ5,q‚ˉV′q=1Ν-1Ν∑q=2V′q。节点B可以通过式(7)校正自身的时钟频偏,根据式(9)校正自身的时钟相偏。事实上正是因为时钟频率的漂移才使得节点之间时间差异逐渐增大,所以时间同步的本质应该修正时钟的频率偏移。因此,这一改进无论从理论分析还是实际应用来说,意义都很重大。3.2节点双向报文同步机制目前已经有很多分簇算法用于网络中数据交互的低能耗和可靠性,本文将基于文献中的分簇方法,建立一套以簇为单位的直接间接同步结合的算法结构。单个节点广播范围内只有一个簇首节点执行双向同步过程,其他节点通过监听簇头节点同步过程被动进行双向同步过程这里称作伪双向同步,因为这些节点从报文交互上看是进行的是单向传递,但算法的执行过程仍然按照双向同步过程执行。图3为单跳同步执行过程示例,其中节点O为基准源,节点A、B和C处于节点O的一跳范围内并与节点O进行同步,这里假设各个节点之间都能够直接通信。具体过程如下:1)同步请求阶段:节点A向节点O发送同步请求报文,时间记为T(A)3,q,报文中包含T(A)3,q和A的节点号,节点O收到报文时间记为T4,q=T(A)3,q+θ(A)1+dA,O+Xq。其中,θ(A)1是节点A与基准节点O的时间偏差;dA,O是节点A到节点O的报文传输延迟;Xq为报文传输过程中的随机延迟。在节点A发送请求报文的同时,节点B和节点C同样监听到该请求报文并记录监听到该报文时刻记为T(B)3,q和T(C)3,q。2)同步响应阶段:节点O收到来自节点A的同步请求报文,发送响应报文,发送时刻记为T5,q,报文中包含T4,q和T5,q,节点A收到响应报文时间记为T(A)6,q,有T(A)6,q=T(A)5,q-θ(A)1+dO,A+Yq。同样节点B和节点C可以监听到响应报文并将监听时刻记为T(B)6,q和T(C)6,q。3)同步数据保存阶段:通过N次同步过程节点A、B、C分别获得一组同步信息序列{T(A)3,q,T4,q,T5,q,T(A)6,q}(q=1,2,…,N)、{T(B)3,q,T4,q,T5,q,T(B)6,q}(q=1,2,…,N)、{T(C)3,q,T4,q,T5,q,T(C)6,q}(q=1,2,…,N)。4)同步校正阶段:通过式(7)校正自身的时钟频偏,式(9)校正自身的时钟相偏,达到节点同步目的。这里节点A为直接的双向同步,而节点B和节点C通过监听节点A的同步过程间接获得同步所需同步信息。尽管节点B和节点C没有直接向基准节点O发送同步请求报文,通过监听节点A的同步交互可以模拟节点B和节点C向基准节点O发送同步请求的过程,如图3中的虚线部分。由图3中时间记录时间先后顺序可以获得式(10)和式(11)。T4,q=T(A)3,q+θ(A0)1+dA,O+XAΟq(10)T(B)3,q=T(A)3,q+θ(AB)1+dA,B+XABq(11)式中:θ(AΟ)1、θ(AB)1分别表示节点A和基准节点O和节点B之间的相偏,dA,O、dA,B分别为节点A到基准节点O和节点B的传输延迟,XAΟq、XABq分别为A到O和B传输延迟中的随机部分。由式(10)和式(11)可以获得式(12):T(B)3,q=T4,q+(θ(AB)1-θ(AΟ)1)+dA,B-dA,O+XABq-XAΟq(12)由于θ(AΟ)1、θ(AB)1分别表示节点A和基准节点O和节点B之间的相偏,可以获得θ(AB)1-θ(AΟ)1=-θ(BΟ)1,而由于节点A为选定节点,可以获得dA,B-dA,O=-dBO,同理有XABq-XAΟq=-XBΟq,代入式(12)可以得到式(13):T4,q=T(B)3,q+θ(BΟ)1+dB,O+XBΟq(13)式(13)使得节点B虚拟出一个同步请求报文发送到基准节点O,也就是节点达到了双向报文同步的要求。同理节点C也满足双向同步报文的要求。算法扩展到多跳,需要执行网络分簇,网络结构如图4所示,分簇过程根据节点自身获得级别与周围同级别邻居之间无线报文交互情况进行。分为以下几个方面。首先根节点将自身级别定为0级,并周期性广播包含节点级别和节点号分级信息的无线报文,所有接收到该报文的节点将自己的级别定为该级别加1并把报文发送方的节点号和级别加入邻居列表。其次级别1的节点在确定自身级别后向外广播分级信息,接收到该分级信息的节点如果没有节点级别则把自己的级别定为该级别加1,并把该节点号和级别加入邻居列表。以此类推,直到所有节点都有自己的级别,形成如图4所示不同级别节点构成的网络结构。通过以上分级操作网络中的节点分为父节点、同级邻居节点和子节点3种类型。每个节点的子节点为一簇,并选取同级节点中度数最大(互为邻居个数)的节点作为的该节点和所有其同级邻居节点簇头。当然也可能出现如图4中12号节点,虽然同样是节点3的邻居,但不在簇首节点10通信范围内,只能单独成簇。通过以上步骤生成一个分级分簇的树形拓扑网络,每个节点和它的子节点形成了一个连通的单跳区域,并将网络划分为很多单跳算法可以直接应用的单跳区域,通过式(7)和式(9)完成各簇内节点的时间同步校正。实际应用中,可以根据网络需要布设大功率路由节点作为簇首,使之可以覆盖更大范围通信距离并能有效减少簇的个数,对于网络中其他节点可以实现更为有效的低能耗运行。选用簇头节点和父节点进行双向同步,其他簇内节点被动监听同步的方式,相对于传统双向时间同步协议可以大大减小同步报文的消耗。从多跳机制的原理可以看出,一次全网同步只需要2n次报文传输,其中n为拓扑树中的非叶子节点(有子节点的节点)个数。4实验配置和结果分析4.1实验方案和机制设置为了更真实地反映客观的物理环境,对同步开销和精度的测试主要通过物理实验完成。物理实验使用由中国科学院沈阳自动化研究所研制的SIA2420模块。SIA2420采用符合IEEE802.15.4标准的无线射频芯片CC2420和低功耗16位微控制器TIMSP430,并且在射频前端分别增加PA和LNA,提高了发射功率和接收灵敏度,在室外可视通信距离能达到1000m以上,由于采用了先进功耗管理技术,在典型的Mesh网络中工作的最小电流仅30μA。无线通信速率能够提供最大250Kb/s。SIA2420装配2个不同频率晶振(32kHz和8MHz)都可以用作时钟源。对TimerA配置使用高速晶振(8MHz)的8分频作为时钟源,从而获得分辨率为1μs的时钟源。实验中将20个实验节点均匀布设在100m×200m的实验工厂环境中,环境中有一些机器遮挡物,以及少量大功率电机工作。通过降低发射功率将节点通信半径降低到百米以内,根据实验记录形成如图5所示拓扑结构,通过该拓扑结构对算法性能进行分析。实验其他设置如图5所示。网络中使用能够覆盖全网的查询节点和监听节点,查询节点在固定时刻向全网发送同步查询报文,网络中的节点在收到查询报文后发送响应报文,此时监听节点监听到这些报文并上传到上位机,上位机对数据进行统计和分析工作。性能评价指标主要从时间同步精度(包括最大误差、平均误差),以及误差分布进行评价分析。4.2同步精度测试图6给出了通过实验获得的相同节点使用不同算法电流曲线图。图中在测试时间内,本文的HTSP算法发送报文次数明显少于另外2种,TPSN次之,RBS需要交互报文次数最多,因此消耗的电流也最