無線傳感器網絡中基于簇結構的雙向同步算法

無線傳感器網絡中基于簇結構的雙向同步算法

1節(jié)點月間信息同步校正時間同步是無線傳感器網絡的一項基本技術支持技術。在無線傳感器網絡的應用中,傳感器節(jié)點采集的數(shù)據(jù)如果沒有空間和時間信息是沒有任何意義的。準確的時間同步是實現(xiàn)傳感器網絡自身協(xié)議的運行、定位、多傳感器數(shù)據(jù)融合、移動目標的跟蹤、基于的協(xié)議以及基于睡眠/偵聽模式的節(jié)能機制等技術的基礎。面向無線傳感器網絡的時間同步協(xié)議按照一對節(jié)點的同步方式可以分為參考廣播同步、單向同步和雙向同步3類。參考廣播同步算法需要第三方發(fā)送參考廣播,并且進行同步的各接收節(jié)點需要交互大量的參考廣播的時間信息并進行偏移矩陣計算,對節(jié)點能耗和計算能力要求較高。雙向時間同步可以準確估計無線傳輸延遲,但是仍不可避免過多報文交互使節(jié)點能耗較大的問題。單向同步算法以單向廣播時間信息進行同步,相對雙向報文交互極大降低了能量消耗,但是在無線傳播延遲較大場合,如水聲通信,單向同步算法將無法獲得可靠的同步。本文通過節(jié)點間的時鐘頻率偏移和相位偏移進行最大似然估計并獲得同步校正算法,網絡結構采用分級分簇的樹形拓撲網絡,簇內節(jié)點通過監(jiān)聽簇頭節(jié)點的主動雙向同步過程完成被動的雙向同步,最終實現(xiàn)全網時間同步。基于頻偏和相偏的同步校正算法提高了網絡的同步精度,分級分簇的樹形拓撲結構以及主動雙向同步和被動雙向同步結合的模式相對于傳統(tǒng)的雙向同步算法極大地降低了同步報文開銷,適用于對于同步精度和能耗要求較高的網絡。2節(jié)點本地時間同步算法傳感器網絡中節(jié)點的物理時鐘依靠對自身晶振中斷計數(shù)實現(xiàn)。晶振的頻率誤差和初始計時時刻不同,使得節(jié)點之間物理時鐘不同步。如果能估算出物理時鐘之間的關系,就可以構造對應的邏輯時鐘以達成同步。一般來講節(jié)點的本地時間都是采用晶振進行計時,而高精度的時鐘對應較高的能量消耗,另外不同廠商生產的晶振穩(wěn)定性不同,晶振穩(wěn)定性越高意味著更高的價格。衡量晶振穩(wěn)定性以ppm(μs/min)為單位,也就是每秒鐘偏差1μs,通常普通的晶振偏移在20至50個ppm(μs/min),也有一些帶有溫度補償?shù)母呖煽烤д衿顑H僅有1.5個ppm(μs/min)左右。實際應用中根據(jù)需要權衡使用,另外由于溫度和環(huán)境的變化,以及設備的老化等原因也會引起時鐘偏差,使得節(jié)點在運行過程中產生時鐘漂移,因此在設計時間同步協(xié)議的過程中要合理考慮這些因素,提高算法的可靠性和適應性。定義t為實際時間,用T(t)表示節(jié)點本地時間,而且根據(jù)節(jié)點時間特性,T(t)>0,且T(t)為增函數(shù),假設存在標準的不存在偏差的時鐘,那么dT(t)/dt=1,但實際上用于計時的晶振都存在偏差,由此可以定義時鐘偏移率為:ρ(t)=dΤ(t)dt-1,|ρ(t)|<ρ0(ρ0ρ(t)=dT(t)dt?1,|ρ(t)|<ρ0(ρ0為一常數(shù))而且由T(t)為增函數(shù)的特性可以得出:-1<ρ(t),?t令f(t)=dT(t)/dt,那么節(jié)點本地時鐘T(t)可以表示為:Ti(t)=∫tt0tt0fi(τ)dτ+Ψi(t0)(1)通過對式(1)進行泰勒級數(shù)展開得到本地時間表示為:Ti(t)=βi+αit+γit2+…(2)式(2)中i為節(jié)點順序,β為本地時間和實際度量時間t之間的偏移量,α為時鐘飄移率,γ為二次項系數(shù),可以表征時鐘的動態(tài)變化。如果式(2)中二次項以上的系數(shù)都為0,那么式(2)可以簡化為線性模型:Ti(t)=βi+αit(3)目前大多數(shù)時間同步算法都是基于線性模型的算法。如果節(jié)點工作環(huán)境變化較大,而且系統(tǒng)對時間同步精度要求較高的情況下,時間同步算法需要考慮高次項系數(shù),這樣相應地也增加了計算開銷。對于環(huán)境相對穩(wěn)定的系統(tǒng),節(jié)點的頻率偏差由晶振的制作工藝決定,而偏移量是固定不變的。3基于餡料雙向時間同步策略通過第2節(jié)的分析,節(jié)點間的時鐘不僅存在表征時間值差異的相位偏移和表征時間快慢的頻率偏移,進行節(jié)點間的同步研究需要很好地處理節(jié)點間的相偏和頻偏。如果所有節(jié)點出廠時的晶振頻率都是相同的,并且在使用過程中不隨時間漂移,一次同步就可以完全同步2個節(jié)點的時鐘。但實際上由于出廠時晶振頻率的微小差異及外部環(huán)境帶來的漂移,在一段時間后,原本已經時間同步的2個節(jié)點將不再時間同步,如圖1所示。在t1時刻,節(jié)點A和B之間的本地時鐘差異為DA->Bt1A?>Bt1;在t2時刻,A與B間的本地時間差異變?yōu)镈A->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個節(jié)點的同步精度控制在30μs以內,同步頻率必須大于1Hz,這將給網絡帶來非常大的通信開銷。但是,如果使用較長的同步周期,則必須估計2個節(jié)點之間的頻率漂移因素才能獲得較高的同步精度。因此,采用雙向時間同步對節(jié)點間頻率偏差和相位偏差進行修正,結合已有的MAC層時間戳處理方法,建立一套基于簇狀結構的時間同步方法。網絡中各簇的簇首使用直接的雙向同步與同步源進行同步,其他簇內節(jié)點通過監(jiān)聽簇首的同步過程間接地進行雙向時間同步,以此達到全網高精度的時間同步。本文的HTSP算法采用基于簇結構的直接雙向時間同步和間接雙向時間同步的方法相對于傳統(tǒng)的時間同步算法具有更高的優(yōu)勢。相對于RBS算法避免了大量時間相關報文的交互和高復雜度的運算。相對于TPSN算法盡管HTSP保持了雙向時間同步特征,但由于采用了間接雙向同步報文同步方法,極大地降低了同步過程中報文的消耗,在保證同步精度的情況下具有更好的能量有效性。相對于單向時間同步算法如FTSP本文同步算法具有更大的適應性,適用于無線傳播延遲較大的場合如水聲通信等。3.1節(jié)點時鐘差異通過模型(3)可以看出不同節(jié)點間的時鐘存在常數(shù)項的差異即相位偏移(簡稱相偏),以及時間頻率的差異即頻率偏移(簡稱頻偏)。目前用于校正相偏和頻偏的方法較多,RBS算法中節(jié)點間交互接收到基準節(jié)點的時間信息,通過這種方式,接收節(jié)點能夠知道彼此之間的時鐘偏移量,然后利用偏移矩陣計算相對于所有其他節(jié)點時鐘偏移的平均值;TPSN通過雙向的報文交互,估算出節(jié)點間的傳輸延遲,獲得更為精準的節(jié)點間的相偏;FTSP使用線性回歸的方式對節(jié)點間的頻偏進行校正。本文通過最大似然估計對節(jié)點間的相偏和頻偏進行校正,從而獲得更精準的時間同步。圖1給出同步校正頻偏和相偏原理圖,節(jié)點A與節(jié)點B之間不僅存在著時鐘的相位偏差θ1,而且存在時鐘之間的頻率偏差θ2,正是頻率偏差的作用使得節(jié)點之間的相位偏差在不斷地增大。節(jié)點A和B之間時間的精確同步,需要通過N次的報文雙向交換來實現(xiàn)。如圖2所示,時間值T1,q、T4,q、T5,q是由節(jié)點A的時鐘測得的,時間值T(R)2,q(R)2,q、T(R)3,q(R)3,q、T(R)6q(R)6q是由節(jié)點B的時鐘測得的,其中q表示時鐘同步過程的輪序號。其中θ(R)1(R)1表示絕對的時鐘相位偏差,θ1表示在T(R)3,1(R)3,1時刻的相對的時鐘相位偏差。假設d為報文傳遞過程中時間延遲的固定部分(如電波在空中的傳播時間),而Xq和Yq分別表示報文M2和M3傳遞過程中,時間延遲的隨機部分。節(jié)點時鐘之間的時間差異由相位偏移和頻率偏移共同作用的結果,而且這里的相位偏差相當于初始相位偏差。節(jié)點之間時間差異的逐漸增大很大程度上取決于時鐘之間的頻率偏差。由于石英晶體的工作頻率各不相同,節(jié)點間的時鐘差異是單調遞增的(或者暫時性的遞減,后遞增)。所以在圖1中,第1次和第N次報文交換中得到的時間戳之間的時鐘差異最大。定義式(4)形式如下:D(j)?Ν∑i=2Dj,i=Τj,Ν-Τj,1(4)圖2中X和Y都是報文傳遞過程中的隨機延時,由于無線信道的鏈路復雜性,可以將X、Y看作是很多獨立同分布的隨機延時的累積。根據(jù)中心極限定理,對于大量的獨立同分布的隨機變量的和的概率密度函數(shù)接近于高斯隨機變量。通過對隨機變量的分析轉化可以獲得如式(5)所示的似然函數(shù)。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)取自然對數(shù),并令其對數(shù)等于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的似然函數(shù)如式(8)所示:L(θ1,μ,δ2)=-1/2πδ2e-[Ν∑q=1(U′q-d′-θ1-μ)2+Ν∑q=1(V′q-d′+θ1-μ)2]/2δ2(8)對似然函數(shù)的取對數(shù)形式并令其等于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。節(jié)點B可以通過式(7)校正自身的時鐘頻偏,根據(jù)式(9)校正自身的時鐘相偏。事實上正是因為時鐘頻率的漂移才使得節(jié)點之間時間差異逐漸增大,所以時間同步的本質應該修正時鐘的頻率偏移。因此,這一改進無論從理論分析還是實際應用來說,意義都很重大。3.2節(jié)點雙向報文同步機制目前已經有很多分簇算法用于網絡中數(shù)據(jù)交互的低能耗和可靠性,本文將基于文獻中的分簇方法,建立一套以簇為單位的直接間接同步結合的算法結構。單個節(jié)點廣播范圍內只有一個簇首節(jié)點執(zhí)行雙向同步過程,其他節(jié)點通過監(jiān)聽簇頭節(jié)點同步過程被動進行雙向同步過程這里稱作偽雙向同步,因為這些節(jié)點從報文交互上看是進行的是單向傳遞,但算法的執(zhí)行過程仍然按照雙向同步過程執(zhí)行。圖3為單跳同步執(zhí)行過程示例,其中節(jié)點O為基準源,節(jié)點A、B和C處于節(jié)點O的一跳范圍內并與節(jié)點O進行同步,這里假設各個節(jié)點之間都能夠直接通信。具體過程如下:1)同步請求階段:節(jié)點A向節(jié)點O發(fā)送同步請求報文,時間記為T(A)3,q,報文中包含T(A)3,q和A的節(jié)點號,節(jié)點O收到報文時間記為T4,q=T(A)3,q+θ(A)1+dA,O+Xq。其中,θ(A)1是節(jié)點A與基準節(jié)點O的時間偏差;dA,O是節(jié)點A到節(jié)點O的報文傳輸延遲;Xq為報文傳輸過程中的隨機延遲。在節(jié)點A發(fā)送請求報文的同時,節(jié)點B和節(jié)點C同樣監(jiān)聽到該請求報文并記錄監(jiān)聽到該報文時刻記為T(B)3,q和T(C)3,q。2)同步響應階段:節(jié)點O收到來自節(jié)點A的同步請求報文,發(fā)送響應報文,發(fā)送時刻記為T5,q,報文中包含T4,q和T5,q,節(jié)點A收到響應報文時間記為T(A)6,q,有T(A)6,q=T(A)5,q-θ(A)1+dO,A+Yq。同樣節(jié)點B和節(jié)點C可以監(jiān)聽到響應報文并將監(jiān)聽時刻記為T(B)6,q和T(C)6,q。3)同步數(shù)據(jù)保存階段:通過N次同步過程節(jié)點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)校正自身的時鐘相偏,達到節(jié)點同步目的。這里節(jié)點A為直接的雙向同步,而節(jié)點B和節(jié)點C通過監(jiān)聽節(jié)點A的同步過程間接獲得同步所需同步信息。盡管節(jié)點B和節(jié)點C沒有直接向基準節(jié)點O發(fā)送同步請求報文,通過監(jiān)聽節(jié)點A的同步交互可以模擬節(jié)點B和節(jié)點C向基準節(jié)點O發(fā)送同步請求的過程,如圖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分別表示節(jié)點A和基準節(jié)點O和節(jié)點B之間的相偏,dA,O、dA,B分別為節(jié)點A到基準節(jié)點O和節(jié)點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分別表示節(jié)點A和基準節(jié)點O和節(jié)點B之間的相偏,可以獲得θ(AB)1-θ(AΟ)1=-θ(BΟ)1,而由于節(jié)點A為選定節(jié)點,可以獲得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)使得節(jié)點B虛擬出一個同步請求報文發(fā)送到基準節(jié)點O,也就是節(jié)點達到了雙向報文同步的要求。同理節(jié)點C也滿足雙向同步報文的要求。算法擴展到多跳,需要執(zhí)行網絡分簇,網絡結構如圖4所示,分簇過程根據(jù)節(jié)點自身獲得級別與周圍同級別鄰居之間無線報文交互情況進行。分為以下幾個方面。首先根節(jié)點將自身級別定為0級,并周期性廣播包含節(jié)點級別和節(jié)點號分級信息的無線報文,所有接收到該報文的節(jié)點將自己的級別定為該級別加1并把報文發(fā)送方的節(jié)點號和級別加入鄰居列表。其次級別1的節(jié)點在確定自身級別后向外廣播分級信息,接收到該分級信息的節(jié)點如果沒有節(jié)點級別則把自己的級別定為該級別加1,并把該節(jié)點號和級別加入鄰居列表。以此類推,直到所有節(jié)點都有自己的級別,形成如圖4所示不同級別節(jié)點構成的網絡結構。通過以上分級操作網絡中的節(jié)點分為父節(jié)點、同級鄰居節(jié)點和子節(jié)點3種類型。每個節(jié)點的子節(jié)點為一簇,并選取同級節(jié)點中度數(shù)最大(互為鄰居個數(shù))的節(jié)點作為的該節(jié)點和所有其同級鄰居節(jié)點簇頭。當然也可能出現(xiàn)如圖4中12號節(jié)點,雖然同樣是節(jié)點3的鄰居,但不在簇首節(jié)點10通信范圍內,只能單獨成簇。通過以上步驟生成一個分級分簇的樹形拓撲網絡,每個節(jié)點和它的子節(jié)點形成了一個連通的單跳區(qū)域,并將網絡劃分為很多單跳算法可以直接應用的單跳區(qū)域,通過式(7)和式(9)完成各簇內節(jié)點的時間同步校正。實際應用中,可以根據(jù)網絡需要布設大功率路由節(jié)點作為簇首,使之可以覆蓋更大范圍通信距離并能有效減少簇的個數(shù),對于網絡中其他節(jié)點可以實現(xiàn)更為有效的低能耗運行。選用簇頭節(jié)點和父節(jié)點進行雙向同步,其他簇內節(jié)點被動監(jiān)聽同步的方式,相對于傳統(tǒng)雙向時間同步協(xié)議可以大大減小同步報文的消耗。從多跳機制的原理可以看出,一次全網同步只需要2n次報文傳輸,其中n為拓撲樹中的非葉子節(jié)點(有子節(jié)點的節(jié)點)個數(shù)。4實驗配置和結果分析4.1實驗方案和機制設置為了更真實地反映客觀的物理環(huán)境,對同步開銷和精度的測試主要通過物理實驗完成。物理實驗使用由中國科學院沈陽自動化研究所研制的SIA2420模塊。SIA2420采用符合IEEE802.15.4標準的無線射頻芯片CC2420和低功耗16位微控制器TIMSP430,并且在射頻前端分別增加PA和LNA,提高了發(fā)射功率和接收靈敏度,在室外可視通信距離能達到1000m以上,由于采用了先進功耗管理技術,在典型的Mesh網絡中工作的最小電流僅30μA。無線通信速率能夠提供最大250Kb/s。SIA2420裝配2個不同頻率晶振(32kHz和8MHz)都可以用作時鐘源。對TimerA配置使用高速晶振(8MHz)的8分頻作為時鐘源,從而獲得分辨率為1μs的時鐘源。實驗中將20個實驗節(jié)點均勻布設在100m×200m的實驗工廠環(huán)境中,環(huán)境中有一些機器遮擋物,以及少量大功率電機工作。通過降低發(fā)射功率將節(jié)點通信半徑降低到百米以內,根據(jù)實驗記錄形成如圖5所示拓撲結構,通過該拓撲結構對算法性能進行分析。實驗其他設置如圖5所示。網絡中使用能夠覆蓋全網的查詢節(jié)點和監(jiān)聽節(jié)點,查詢節(jié)點在固定時刻向全網發(fā)送同步查詢報文,網絡中的節(jié)點在收到查詢報文后發(fā)送響應報文,此時監(jiān)聽節(jié)點監(jiān)聽到這些報文并上傳到上位機,上位機對數(shù)據(jù)進行統(tǒng)計和分析工作。性能評價指標主要從時間同步精度(包括最大誤差、平均誤差),以及誤差分布進行評價分析。4.2同步精度測試圖6給出了通過實驗獲得的相同節(jié)點使用不同算法電流曲線圖。圖中在測試時間內,本文的HTSP算法發(fā)送報文次數(shù)明顯少于另外2種,TPSN次之,RBS需要交互報文次數(shù)最多,因此消耗的電流也最