3 算法實(shí)現(xiàn)
3.1 時(shí)鐘模型
WSN中各節(jié)點(diǎn)的時(shí)鐘主要包括一個(gè)統(tǒng)一的基準(zhǔn)時(shí)鐘,一個(gè)相對(duì)于基準(zhǔn)時(shí)鐘的偏移,和由于時(shí)鐘頻率不一致而導(dǎo)致的扭曲。定義c(t)為一個(gè)參考時(shí)鐘,是一個(gè)統(tǒng)一穩(wěn)定的基準(zhǔn)值。每個(gè)節(jié)點(diǎn)有自己的時(shí)鐘,是一個(gè)關(guān)于t的函數(shù)ci(t),每個(gè)節(jié)點(diǎn)的本地時(shí)鐘相對(duì)基準(zhǔn)時(shí)鐘的偏移是指由于長(zhǎng)期累積而導(dǎo)致的時(shí)鐘不一致,扭曲是指由于石英晶體振蕩器振蕩頻率不一致,從而導(dǎo)致了時(shí)鐘與基準(zhǔn)時(shí)鐘之間存在差別。
設(shè)兩個(gè)節(jié)點(diǎn)的時(shí)鐘分別為ci(t)和cj(t),如果時(shí)鐘在時(shí)間t完全正確,則ci(t)=cj(t)=c(t),但是在實(shí)際中兩個(gè)時(shí)鐘往往是不相等的。這是由于晶體振蕩器本身技術(shù)原因和外部工作環(huán)境(如溫度、壓力)等因素引起的,因此,t時(shí)刻每個(gè)節(jié)點(diǎn)的時(shí)鐘模型為:ci(t)=αit+βi,其中αi為晶體振蕩器自身頻率的不一致而帶來的扭曲,βi為時(shí)鐘長(zhǎng)期積累的偏移。
為達(dá)到時(shí)鐘一致,最關(guān)鍵的問題是使得任何節(jié)點(diǎn)的ci(t)=c(t),即補(bǔ)償時(shí)鐘的扭曲αi和時(shí)鐘偏移βi,在任何時(shí)刻各節(jié)點(diǎn)的時(shí)鐘不再偏移,且振蕩頻率也完全一致。
3.2 算法實(shí)現(xiàn)
TSMA要達(dá)到的目標(biāo)是內(nèi)部一致。在每個(gè)同步循環(huán),算法更新每個(gè)節(jié)點(diǎn)的補(bǔ)償參數(shù),通過這樣的方式使時(shí)鐘達(dá)到一致:limt→∞ci(t)=cv(t)。其中cv(t)是本算法的虛擬時(shí)鐘,虛擬時(shí)鐘并不是一個(gè)現(xiàn)實(shí)中存在的時(shí)鐘,而是所有節(jié)點(diǎn)以之為基準(zhǔn)的一個(gè)時(shí)鐘,是由本算法在運(yùn)行過程中產(chǎn)生的。虛擬時(shí)鐘有相對(duì)于實(shí)際時(shí)鐘的扭曲率和相對(duì)偏移。各節(jié)點(diǎn)對(duì)本節(jié)點(diǎn)扭曲和偏移進(jìn)行補(bǔ)償,從而同步于虛擬時(shí)鐘,實(shí)現(xiàn)全網(wǎng)同步。
設(shè)虛擬時(shí)鐘為cv(t)=α·t+β,為使得各節(jié)點(diǎn)時(shí)鐘最后同步于虛擬時(shí)鐘,需要采用修正參數(shù),設(shè)對(duì)于扭曲的修正參數(shù)為α′,對(duì)于偏移的修正參數(shù)為β′,則運(yùn)行過程中,通過修正參數(shù)使得時(shí)鐘保持一致的條件為:limt→∞(α′ci(t)+β′)=cv(t)=α·t+β,即limt→∞(α′ αit+α′βi+β′)=α·t+β,由此可得到修正參數(shù)為:
為得到補(bǔ)償各節(jié)點(diǎn)的時(shí)鐘扭曲和偏移,每個(gè)節(jié)點(diǎn)在算法執(zhí)行周期內(nèi)完成對(duì)兩種參數(shù)的修正。修正主要包括兩個(gè)過程:第一個(gè)過程為扭曲修正,通過修正扭曲值使得節(jié)點(diǎn)與虛擬時(shí)鐘頻率一致;第二個(gè)過程為偏移修正,通過修正偏移值確保全網(wǎng)時(shí)鐘同步。
3.2.1 扭曲修正
扭曲修正的目的是確保時(shí)鐘在相同的振蕩頻率下工作,即limt→∞α′αi=α。對(duì)扭曲參數(shù)的修正采用指數(shù)逼近的方式,以將所有的時(shí)鐘扭曲趨近于α,每個(gè)節(jié)點(diǎn)執(zhí)行的算法如下:
?、?運(yùn)行同步算法前,節(jié)點(diǎn)設(shè)置扭曲估計(jì)αi為1,同時(shí)準(zhǔn)備搜索鄰居節(jié)點(diǎn)的時(shí)鐘扭曲信息。
?、?由于各節(jié)點(diǎn)并不一定知道鄰居節(jié)點(diǎn)的存在,在節(jié)點(diǎn)廣播自己的時(shí)鐘信息時(shí),有可能別的節(jié)點(diǎn)也在廣播時(shí)鐘信息,從而導(dǎo)致廣播失敗,因此在MAC層需要一個(gè)類似CSMA/CD的協(xié)議,以確保各節(jié)點(diǎn)能正確廣播自己的時(shí)鐘信息。
③ 設(shè)共有n個(gè)節(jié)點(diǎn),第i(1≤i≤n)個(gè)節(jié)點(diǎn)存儲(chǔ)并廣播自己的時(shí)間信息(αi,Ti),其中Ti為本節(jié)點(diǎn)當(dāng)前時(shí)間值,由于節(jié)點(diǎn)距離和傳輸速度是已知的,所以接收到廣播的節(jié)點(diǎn)根據(jù)Ti確定接收時(shí)的時(shí)間是可行的。
?、?節(jié)點(diǎn)i收到第j(1≤j≤n)個(gè)節(jié)點(diǎn)的廣播包,包含了節(jié)點(diǎn)j的時(shí)間信息(αi,Tj),如果第j個(gè)節(jié)點(diǎn)是第1次出現(xiàn),則節(jié)點(diǎn)i只存儲(chǔ)節(jié)點(diǎn)j的時(shí)間信息,直到收到節(jié)點(diǎn)j的下一個(gè)時(shí)間信息(αj+1,Tj+1)。
?、?此時(shí)比較節(jié)點(diǎn)i和節(jié)點(diǎn)j的扭曲,計(jì)算R1=αi(Tj+1-Tj)和R2=αj(Ti+1-Ti),若R1》R2,則需要對(duì)節(jié)點(diǎn)i的扭曲率進(jìn)行修正,設(shè)兩者的差值為λi=αi-αj,調(diào)整因子為σ=min(αi,αj)max(αi,αj),設(shè)置扭曲率和校正值為λ′i=λi(e-eσ)(e- 1),設(shè)置修正值調(diào)整的閾值RT,當(dāng)節(jié)點(diǎn)i首次出現(xiàn)λ′i低于閾值要求時(shí)不作調(diào)整,以避免部分失效節(jié)點(diǎn)重新進(jìn)入網(wǎng)絡(luò)時(shí)對(duì)鄰居節(jié)點(diǎn)造成影響。則節(jié)點(diǎn)i新的扭曲值為
則αi=α,同時(shí)保留最新的節(jié)點(diǎn)i和節(jié)點(diǎn)j的時(shí)間信息T,即Ti=Ti+1,Tj=Tj+1。
⑥ 節(jié)點(diǎn)重復(fù)步驟②~⑤,直到R1=R2,兩節(jié)點(diǎn)扭曲率一致,此時(shí)節(jié)點(diǎn)已經(jīng)更新了自己的時(shí)鐘扭曲率,只需要保持偏移一致,即可達(dá)到時(shí)鐘同步。
3.2.2 偏移修正
修正完扭曲率后,需要對(duì)偏移進(jìn)行修正,以達(dá)到節(jié)點(diǎn)時(shí)鐘同步。修正偏移值的關(guān)鍵是找到合適的偏移值,使得各節(jié)點(diǎn)能夠同步到一個(gè)統(tǒng)一的偏移值,從而統(tǒng)一于一個(gè)虛擬的時(shí)鐘。設(shè)每個(gè)節(jié)點(diǎn)的偏移值為βi,1≤i≤n,則節(jié)點(diǎn)i在接收到鄰居節(jié)點(diǎn)的偏移值后,很容易得到一個(gè)平均值β-1n∑ni=1βi,顯然這一平均值即為要找的虛擬時(shí)鐘的偏移值,當(dāng)各節(jié)點(diǎn)同步于這一偏移值,便實(shí)現(xiàn)了全網(wǎng)時(shí)鐘同步。由于部分節(jié)點(diǎn)的時(shí)鐘偏移值較大,同時(shí)每次更新的節(jié)點(diǎn)為一跳內(nèi)的節(jié)點(diǎn),采用一次調(diào)整偏移值至平均值的方法并不能以最快的速度使得全網(wǎng)節(jié)點(diǎn)偏移同步,而采用逐次指數(shù)逼近的方式,對(duì)偏移相差較大的節(jié)點(diǎn)修正參數(shù)較大,偏移相差較小的節(jié)點(diǎn)修正參數(shù)較小,使得全網(wǎng)所有節(jié)點(diǎn)逼近統(tǒng)一的偏移值。本算法采用了如下步驟:
?、?節(jié)點(diǎn)i首先估計(jì)自己的偏移值βi,1≤i≤n,并開始收聽廣播,和扭曲修正一樣,廣播已經(jīng)考慮了沖突避免。
② 節(jié)點(diǎn)收集一跳內(nèi)的鄰居偏移值,得到偏移平均值β-1n∑ni=1βi。
?、?節(jié)點(diǎn)i計(jì)算與平均偏移值的差值λi=βi-β-,設(shè)調(diào)整因子為γi=min(βi,β-)max(βi,β-),顯然0≤γi≤1,則某節(jié)點(diǎn)所需調(diào)整的參數(shù)為λ′i=λi(e-eγi)(e-1)。設(shè)置修正值調(diào)整的閾值RT,當(dāng)節(jié)點(diǎn)i首次出現(xiàn)λ′i低于閾值要求時(shí)不作調(diào)整,以避免部分失效節(jié)點(diǎn)重新進(jìn)入網(wǎng)絡(luò)時(shí)對(duì)鄰居節(jié)點(diǎn)的影響。新的偏移值為
則βi=β,節(jié)點(diǎn)i采用指數(shù)逼近的方法,逐次向平均值逼近。
④ 節(jié)點(diǎn)i再次收聽鄰居節(jié)點(diǎn)廣播,重復(fù)步驟②③,直到λi=βi-β-低于設(shè)定值,實(shí)現(xiàn)了全網(wǎng)同步。
由于指數(shù)逼近的方式在節(jié)點(diǎn)偏移相差較大時(shí)調(diào)整較大,節(jié)點(diǎn)偏移相差較小時(shí)調(diào)整較小,適用于網(wǎng)絡(luò)中有新節(jié)點(diǎn)出現(xiàn)時(shí)導(dǎo)致偏移相差較大的情況。采用指數(shù)逼近方式后,與平均值誤差較大的節(jié)點(diǎn)調(diào)整大,加快了收斂速度,與平均值相差小的節(jié)點(diǎn)調(diào)整小,控制了向鄰居節(jié)點(diǎn)擴(kuò)散偏移調(diào)整的范圍。同時(shí),在全網(wǎng)節(jié)點(diǎn)偏移一致后,指數(shù)逼近的方式使得節(jié)點(diǎn)調(diào)整幅度小,避免了由于某一個(gè)時(shí)鐘節(jié)點(diǎn)失誤而帶來的大范圍時(shí)鐘偏移調(diào)整,保證了全網(wǎng)時(shí)鐘同步的穩(wěn)定性。
4 仿真
本文采用指數(shù)逼近的方式調(diào)整各節(jié)點(diǎn)時(shí)鐘扭曲和偏移參數(shù),使得各節(jié)點(diǎn)修正時(shí)鐘扭曲和偏移,最終同步于一個(gè)統(tǒng)一的時(shí)鐘,為顯示算法有效性和可靠性,用 Matlab進(jìn)行了仿真。仿真環(huán)境為在8×8的格狀網(wǎng)絡(luò)里放置64個(gè)節(jié)點(diǎn),每個(gè)格子包含一個(gè)節(jié)點(diǎn),節(jié)點(diǎn)處于每個(gè)格子的中央?yún)^(qū)域,設(shè)每個(gè)節(jié)點(diǎn)用于校準(zhǔn)的晶振參考值是32 768 Hz,即一個(gè)振蕩周期為30.5 μs,小于一個(gè)周期的時(shí)鐘誤差是無法識(shí)別的,因此用1 tick =30.5 μs來表示時(shí)鐘誤差的最小單位。每個(gè)節(jié)點(diǎn)的扭曲率服從平均值為1、方差為10-5的正態(tài)分布,節(jié)點(diǎn)的初始偏移在0~1000隨機(jī)分布。具體得到:節(jié)點(diǎn)扭曲 ——平均值為1,方差為10-5的正態(tài)分布,即N(1,10-5);初始偏移——在0~1000 tick間隨機(jī)分布。
在運(yùn)行過程中,每個(gè)節(jié)點(diǎn)運(yùn)行扭曲和偏移的修正協(xié)議,網(wǎng)絡(luò)中沒有一個(gè)實(shí)際的基準(zhǔn)時(shí)鐘,而是在運(yùn)行過程中逐漸收斂到一個(gè)統(tǒng)一的時(shí)鐘,從而實(shí)現(xiàn)節(jié)點(diǎn)同步。
設(shè)同步每個(gè)循環(huán)周期為30 s,節(jié)點(diǎn)在每個(gè)循環(huán)期間隨機(jī)廣播自己的同步幀,節(jié)點(diǎn)的傳輸距離為2個(gè)單位,即節(jié)點(diǎn)距離相差不超過2時(shí)可以收到對(duì)方消息。為避免網(wǎng)絡(luò)穩(wěn)定運(yùn)行時(shí)部分偏差較大的節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)中大部分節(jié)點(diǎn)同時(shí)調(diào)整參數(shù),仿真中對(duì)首次出現(xiàn)的調(diào)整參數(shù)低于10%的修正參數(shù)不作調(diào)整。為驗(yàn)證本算法的對(duì)多種網(wǎng)絡(luò)拓?fù)涞倪m應(yīng)性,設(shè)置了不同的網(wǎng)絡(luò)狀況,以檢驗(yàn)算法的有效性和可靠性。
圖2演示了節(jié)點(diǎn)使用本算法在網(wǎng)絡(luò)運(yùn)行初期、穩(wěn)定工作狀態(tài)、部分節(jié)點(diǎn)忽然失效或主動(dòng)停止工作時(shí)的性能。每個(gè)同步周期設(shè)置為30 s。仿真持續(xù)時(shí)間為30 min,分為A、B、C、D四個(gè)不同區(qū)域。區(qū)域A所有節(jié)點(diǎn)均工作,由于各節(jié)點(diǎn)運(yùn)行本算法前時(shí)鐘偏差較大,前3個(gè)同步階段,節(jié)點(diǎn)根據(jù)收到的偏移值調(diào)整參數(shù),偏移校正效果不明顯,從第3個(gè)周期開始,節(jié)點(diǎn)開始補(bǔ)償時(shí)鐘偏移和扭曲,經(jīng)過9個(gè)循環(huán)周期的補(bǔ)償,所有節(jié)點(diǎn)到達(dá)同步狀態(tài),即任意兩節(jié)點(diǎn)間的時(shí)鐘偏差在10個(gè)節(jié)拍以內(nèi)。在區(qū)域B的開始階段,50%的節(jié)點(diǎn)選擇隨機(jī)關(guān)閉,又隨機(jī)工作,一但一個(gè)節(jié)點(diǎn)打開,即開始運(yùn)用本算法,因?yàn)椴捎弥笖?shù)逼近的方式,節(jié)點(diǎn)一但開始工作時(shí)即開始執(zhí)行本算法,由于大部分節(jié)點(diǎn)已經(jīng)同步,新加入的節(jié)點(diǎn)的時(shí)鐘調(diào)整不會(huì)對(duì)已經(jīng)同步的節(jié)點(diǎn)造成影響,由圖中可以看出節(jié)點(diǎn)能夠在開始工作后迅速進(jìn)入同步狀態(tài)。在區(qū)域C中,30%的節(jié)點(diǎn)停止工作。在區(qū)域D,這30%的節(jié)點(diǎn)開始工作,由于沒有時(shí)鐘調(diào)整,剛開始工作時(shí)與別的節(jié)點(diǎn)時(shí)鐘無法同步,此時(shí)能夠看到,各節(jié)點(diǎn)開始工作后時(shí)鐘很快收斂,實(shí)現(xiàn)了全網(wǎng)時(shí)鐘同步。
圖2 動(dòng)態(tài)網(wǎng)絡(luò)下時(shí)鐘同步的性能
結(jié)語(yǔ)
從WSN時(shí)鐘同步的發(fā)展趨勢(shì)來看,隨著WSN節(jié)點(diǎn)數(shù)量的增加,采用基于本地信息的分布式同步策略,能夠提高WSN節(jié)點(diǎn)工作效率和穩(wěn)定性。本算法在動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)下實(shí)現(xiàn)了較快的收斂速度,未來的工作集中在網(wǎng)絡(luò)穩(wěn)定運(yùn)行后如何減少由于時(shí)鐘同步帶來的非必要消耗,從而提高節(jié)點(diǎn)生存時(shí)間和網(wǎng)絡(luò)生命周期。
評(píng)論
查看更多