算法實現(xiàn) - 虛擬時鐘指數(shù)逼近的無線傳感器網(wǎng)絡(luò)時鐘同步協(xié)議

　　3 算法實現(xiàn)

　　3.1 時鐘模型

　　WSN中各節(jié)點的時鐘主要包括一個統(tǒng)一的基準(zhǔn)時鐘，一個相對于基準(zhǔn)時鐘的偏移，和由于時鐘頻率不一致而導(dǎo)致的扭曲。定義c（t）為一個參考時鐘，是一個統(tǒng)一穩(wěn)定的基準(zhǔn)值。每個節(jié)點有自己的時鐘，是一個關(guān)于t的函數(shù)ci（t），每個節(jié)點的本地時鐘相對基準(zhǔn)時鐘的偏移是指由于長期累積而導(dǎo)致的時鐘不一致，扭曲是指由于石英晶體振蕩器振蕩頻率不一致，從而導(dǎo)致了時鐘與基準(zhǔn)時鐘之間存在差別。

　　設(shè)兩個節(jié)點的時鐘分別為ci（t）和cj（t），如果時鐘在時間t完全正確，則ci（t）＝cj（t）＝c（t），但是在實際中兩個時鐘往往是不相等的。這是由于晶體振蕩器本身技術(shù)原因和外部工作環(huán)境（如溫度、壓力）等因素引起的，因此，t時刻每個節(jié)點的時鐘模型為：ci（t）=αit+βi，其中αi為晶體振蕩器自身頻率的不一致而帶來的扭曲，βi為時鐘長期積累的偏移。

　　為達到時鐘一致，最關(guān)鍵的問題是使得任何節(jié)點的ci（t）＝c（t），即補償時鐘的扭曲αi和時鐘偏移βi，在任何時刻各節(jié)點的時鐘不再偏移，且振蕩頻率也完全一致。

　　3.2 算法實現(xiàn)

　　TSMA要達到的目標(biāo)是內(nèi)部一致。在每個同步循環(huán)，算法更新每個節(jié)點的補償參數(shù)，通過這樣的方式使時鐘達到一致：limt→∞ci（t）=cv（t）。其中cv（t）是本算法的虛擬時鐘，虛擬時鐘并不是一個現(xiàn)實中存在的時鐘，而是所有節(jié)點以之為基準(zhǔn)的一個時鐘，是由本算法在運行過程中產(chǎn)生的。虛擬時鐘有相對于實際時鐘的扭曲率和相對偏移。各節(jié)點對本節(jié)點扭曲和偏移進行補償，從而同步于虛擬時鐘，實現(xiàn)全網(wǎng)同步。

　　設(shè)虛擬時鐘為cv（t）=α·t+β，為使得各節(jié)點時鐘最后同步于虛擬時鐘，需要采用修正參數(shù)，設(shè)對于扭曲的修正參數(shù)為α′，對于偏移的修正參數(shù)為β′，則運行過程中，通過修正參數(shù)使得時鐘保持一致的條件為：limt→∞（α′ci（t）+β′）=cv（t）=α·t+β，即limt→∞（α′ αit+α′βi+β′）=α·t+β，由此可得到修正參數(shù)為：

　　為得到補償各節(jié)點的時鐘扭曲和偏移，每個節(jié)點在算法執(zhí)行周期內(nèi)完成對兩種參數(shù)的修正。修正主要包括兩個過程：第一個過程為扭曲修正，通過修正扭曲值使得節(jié)點與虛擬時鐘頻率一致；第二個過程為偏移修正，通過修正偏移值確保全網(wǎng)時鐘同步。

　　3.2.1 扭曲修正

　　扭曲修正的目的是確保時鐘在相同的振蕩頻率下工作，即limt→∞α′αi=α。對扭曲參數(shù)的修正采用指數(shù)逼近的方式，以將所有的時鐘扭曲趨近于α，每個節(jié)點執(zhí)行的算法如下：

　　① 運行同步算法前，節(jié)點設(shè)置扭曲估計αi為１，同時準(zhǔn)備搜索鄰居節(jié)點的時鐘扭曲信息。

　　② 由于各節(jié)點并不一定知道鄰居節(jié)點的存在，在節(jié)點廣播自己的時鐘信息時，有可能別的節(jié)點也在廣播時鐘信息，從而導(dǎo)致廣播失敗，因此在MAC層需要一個類似CSMA/CD的協(xié)議，以確保各節(jié)點能正確廣播自己的時鐘信息。

　?、?設(shè)共有n個節(jié)點，第i（1≤i≤n）個節(jié)點存儲并廣播自己的時間信息（αi，Ti），其中Ti為本節(jié)點當(dāng)前時間值，由于節(jié)點距離和傳輸速度是已知的，所以接收到廣播的節(jié)點根據(jù)Ti確定接收時的時間是可行的。

　　④ 節(jié)點i收到第j（1≤j≤n）個節(jié)點的廣播包，包含了節(jié)點j的時間信息（αi，Tj），如果第j個節(jié)點是第１次出現(xiàn)，則節(jié)點i只存儲節(jié)點j的時間信息，直到收到節(jié)點j的下一個時間信息（αj+1，Tj+1）。

　?、?此時比較節(jié)點i和節(jié)點j的扭曲，計算R1=αi（Tj+1-Tj）和R2=αj（Ti+1-Ti），若R1》R2，則需要對節(jié)點i的扭曲率進行修正，設(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é)點i首次出現(xiàn)λ′i低于閾值要求時不作調(diào)整，以避免部分失效節(jié)點重新進入網(wǎng)絡(luò)時對鄰居節(jié)點造成影響。則節(jié)點i新的扭曲值為

　　則αi=α，同時保留最新的節(jié)點i和節(jié)點j的時間信息T，即Ti=Ti+1，Tj=Tj+1。

　?、?節(jié)點重復(fù)步驟②～⑤，直到R1＝R2，兩節(jié)點扭曲率一致，此時節(jié)點已經(jīng)更新了自己的時鐘扭曲率，只需要保持偏移一致，即可達到時鐘同步。

　　3.2.2 偏移修正

　　修正完扭曲率后，需要對偏移進行修正，以達到節(jié)點時鐘同步。修正偏移值的關(guān)鍵是找到合適的偏移值，使得各節(jié)點能夠同步到一個統(tǒng)一的偏移值，從而統(tǒng)一于一個虛擬的時鐘。設(shè)每個節(jié)點的偏移值為βi，1≤i≤n，則節(jié)點i在接收到鄰居節(jié)點的偏移值后，很容易得到一個平均值β-1n∑ni=1βi，顯然這一平均值即為要找的虛擬時鐘的偏移值，當(dāng)各節(jié)點同步于這一偏移值，便實現(xiàn)了全網(wǎng)時鐘同步。由于部分節(jié)點的時鐘偏移值較大，同時每次更新的節(jié)點為一跳內(nèi)的節(jié)點，采用一次調(diào)整偏移值至平均值的方法并不能以最快的速度使得全網(wǎng)節(jié)點偏移同步，而采用逐次指數(shù)逼近的方式，對偏移相差較大的節(jié)點修正參數(shù)較大，偏移相差較小的節(jié)點修正參數(shù)較小，使得全網(wǎng)所有節(jié)點逼近統(tǒng)一的偏移值。本算法采用了如下步驟：

　　① 節(jié)點i首先估計自己的偏移值βi，1≤i≤n，并開始收聽廣播，和扭曲修正一樣，廣播已經(jīng)考慮了沖突避免。

　　② 節(jié)點收集一跳內(nèi)的鄰居偏移值，得到偏移平均值β-1n∑ni=1βi。

　?、?節(jié)點i計算與平均偏移值的差值λi=βi-β-，設(shè)調(diào)整因子為γi=min（βi，β-）max（βi，β-），顯然0≤γi≤1，則某節(jié)點所需調(diào)整的參數(shù)為λ′i=λi（e-eγi）（e-1）。設(shè)置修正值調(diào)整的閾值RT，當(dāng)節(jié)點i首次出現(xiàn)λ′i低于閾值要求時不作調(diào)整，以避免部分失效節(jié)點重新進入網(wǎng)絡(luò)時對鄰居節(jié)點的影響。新的偏移值為

　　則βi=β，節(jié)點i采用指數(shù)逼近的方法，逐次向平均值逼近。

　?、?節(jié)點i再次收聽鄰居節(jié)點廣播，重復(fù)步驟②③，直到λi=βi-β-低于設(shè)定值，實現(xiàn)了全網(wǎng)同步。

　　由于指數(shù)逼近的方式在節(jié)點偏移相差較大時調(diào)整較大，節(jié)點偏移相差較小時調(diào)整較小，適用于網(wǎng)絡(luò)中有新節(jié)點出現(xiàn)時導(dǎo)致偏移相差較大的情況。采用指數(shù)逼近方式后，與平均值誤差較大的節(jié)點調(diào)整大，加快了收斂速度，與平均值相差小的節(jié)點調(diào)整小，控制了向鄰居節(jié)點擴散偏移調(diào)整的范圍。同時，在全網(wǎng)節(jié)點偏移一致后，指數(shù)逼近的方式使得節(jié)點調(diào)整幅度小，避免了由于某一個時鐘節(jié)點失誤而帶來的大范圍時鐘偏移調(diào)整，保證了全網(wǎng)時鐘同步的穩(wěn)定性。

　　4 仿真

　　本文采用指數(shù)逼近的方式調(diào)整各節(jié)點時鐘扭曲和偏移參數(shù)，使得各節(jié)點修正時鐘扭曲和偏移，最終同步于一個統(tǒng)一的時鐘，為顯示算法有效性和可靠性，用 Matlab進行了仿真。仿真環(huán)境為在8×8的格狀網(wǎng)絡(luò)里放置64個節(jié)點，每個格子包含一個節(jié)點，節(jié)點處于每個格子的中央?yún)^(qū)域，設(shè)每個節(jié)點用于校準(zhǔn)的晶振參考值是32 768 Hz，即一個振蕩周期為30.5 μs，小于一個周期的時鐘誤差是無法識別的，因此用1 tick =30.5 μs來表示時鐘誤差的最小單位。每個節(jié)點的扭曲率服從平均值為１、方差為10-5的正態(tài)分布，節(jié)點的初始偏移在0～1000隨機分布。具體得到：節(jié)點扭曲 ——平均值為1，方差為10-5的正態(tài)分布，即N（1，10-5）；初始偏移——在0～1000 tick間隨機分布。

　　在運行過程中，每個節(jié)點運行扭曲和偏移的修正協(xié)議，網(wǎng)絡(luò)中沒有一個實際的基準(zhǔn)時鐘，而是在運行過程中逐漸收斂到一個統(tǒng)一的時鐘，從而實現(xiàn)節(jié)點同步。

　　設(shè)同步每個循環(huán)周期為30 s，節(jié)點在每個循環(huán)期間隨機廣播自己的同步幀，節(jié)點的傳輸距離為2個單位，即節(jié)點距離相差不超過2時可以收到對方消息。為避免網(wǎng)絡(luò)穩(wěn)定運行時部分偏差較大的節(jié)點導(dǎo)致網(wǎng)絡(luò)中大部分節(jié)點同時調(diào)整參數(shù)，仿真中對首次出現(xiàn)的調(diào)整參數(shù)低于10%的修正參數(shù)不作調(diào)整。為驗證本算法的對多種網(wǎng)絡(luò)拓撲的適應(yīng)性，設(shè)置了不同的網(wǎng)絡(luò)狀況，以檢驗算法的有效性和可靠性。

　　圖2演示了節(jié)點使用本算法在網(wǎng)絡(luò)運行初期、穩(wěn)定工作狀態(tài)、部分節(jié)點忽然失效或主動停止工作時的性能。每個同步周期設(shè)置為30 s。仿真持續(xù)時間為30 min，分為A、B、C、D四個不同區(qū)域。區(qū)域A所有節(jié)點均工作，由于各節(jié)點運行本算法前時鐘偏差較大，前3個同步階段，節(jié)點根據(jù)收到的偏移值調(diào)整參數(shù)，偏移校正效果不明顯，從第３個周期開始，節(jié)點開始補償時鐘偏移和扭曲，經(jīng)過9個循環(huán)周期的補償，所有節(jié)點到達同步狀態(tài)，即任意兩節(jié)點間的時鐘偏差在10個節(jié)拍以內(nèi)。在區(qū)域B的開始階段，50％的節(jié)點選擇隨機關(guān)閉，又隨機工作，一但一個節(jié)點打開，即開始運用本算法，因為采用指數(shù)逼近的方式，節(jié)點一但開始工作時即開始執(zhí)行本算法，由于大部分節(jié)點已經(jīng)同步，新加入的節(jié)點的時鐘調(diào)整不會對已經(jīng)同步的節(jié)點造成影響，由圖中可以看出節(jié)點能夠在開始工作后迅速進入同步狀態(tài)。在區(qū)域C中，30％的節(jié)點停止工作。在區(qū)域D，這30%的節(jié)點開始工作，由于沒有時鐘調(diào)整，剛開始工作時與別的節(jié)點時鐘無法同步，此時能夠看到，各節(jié)點開始工作后時鐘很快收斂，實現(xiàn)了全網(wǎng)時鐘同步。

　　圖2 動態(tài)網(wǎng)絡(luò)下時鐘同步的性能

　　結(jié)語

　　從WSN時鐘同步的發(fā)展趨勢來看，隨著WSN節(jié)點數(shù)量的增加，采用基于本地信息的分布式同步策略，能夠提高WSN節(jié)點工作效率和穩(wěn)定性。本算法在動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)下實現(xiàn)了較快的收斂速度，未來的工作集中在網(wǎng)絡(luò)穩(wěn)定運行后如何減少由于時鐘同步帶來的非必要消耗，從而提高節(jié)點生存時間和網(wǎng)絡(luò)生命周期。