無線傳感器網(wǎng)絡(luò)同步算法的研究與探討
無線傳感器網(wǎng)絡(luò)的最常見的幾種同步算法的性能比較如表1所列。本文引用地址:http://m.ptau.cn/article/160602.htm
3 螢火蟲同步算法和梯度同步算法
前面的時間同步技術(shù)都是基于時間信息交換的同步技術(shù),然而在大規(guī)模的無線傳感器網(wǎng)絡(luò)中,存在同步誤差會隨著跳距而積累的問題和可拓展性需求等問題。螢火蟲同步技術(shù)和協(xié)作同步技術(shù)是為了實現(xiàn)節(jié)點的同步性,即使節(jié)點的某些周期性動作具有相同的周期和相位,例如使一群螢火蟲同步閃爍并且閃爍周期相同。1990年,Mirollo和Strogatz在Peskin模型的基礎(chǔ)上提出了更一般的脈沖耦合振蕩器模型(后簡稱為M&S模型)。在此模型中,振蕩器使用狀態(tài)變量x來描述,x的變化服從函數(shù)f(φ),其中f是一個[0,1]到[0,1]的光滑單淵遞增上凸函數(shù),φ是相位變量且滿足(T是同步周期)。Mirollo和Strogatz從理論上證明了在M&S模型下,多個耦合振蕩器系統(tǒng)在幾乎所有的初始情況下都能夠達(dá)到同步,并在無線多跳網(wǎng)絡(luò)測試床Gains上實現(xiàn)了M&S模型的螢火蟲同步算法。
麻省理工學(xué)院的Rui Fan、Nancy Lynch兩位作者第一次提出了GCS梯度同步算法。在移動自組織網(wǎng)絡(luò)中往往是鄰居節(jié)點聯(lián)系比較密切,而相距較遠(yuǎn)的節(jié)點很少交換消息,因此相距較遠(yuǎn)的節(jié)點可以允許較大誤差。如數(shù)據(jù)融合中,具有相同父節(jié)點的子節(jié)點需要精確的同步,但是較遠(yuǎn)的節(jié)點不是同一個父節(jié)點,可以允許誤差大一些。作者就是根據(jù)這一特征提出了梯度同步算法。在通常的時間同步算法的基礎(chǔ)上,假設(shè)兩任意節(jié)點i、j,f(dij)為節(jié)點i和節(jié)點j之間的最大時鐘差,時鐘記為。信息從節(jié)點i傳到j(luò)的傳播時間為0到dij,dij為節(jié)點i到節(jié)點j的距離。D=maxijdij為網(wǎng)絡(luò)的直徑。GCS提出了兩要求:
計算出時鐘漂移的最低邊界滿足f(D)=Ω(d+lgD/lg lgD),這也就是說節(jié)點之間的時鐘漂移不只與兩個節(jié)點問的距離有關(guān),還與整個網(wǎng)絡(luò)的規(guī)模有關(guān),越近的節(jié)點同步效果越好,反之越差。GTSP(Gradient Time Synchronization Protocol)協(xié)議中,每個節(jié)點通過接收鄰居節(jié)點的時間來修正自己的時鐘,整個網(wǎng)絡(luò)無需建立一個拓?fù)錁浣Y(jié)構(gòu),也無需參考節(jié)點,主要是實現(xiàn)直接的鄰居節(jié)點間直接的高精度的同步,同時考慮時間漂移和偏移補(bǔ)償,漂移補(bǔ)償采用式(5)。通過這種補(bǔ)償機(jī)制,所有節(jié)點的邏輯漂移將趨近值Xss;時鐘偏移補(bǔ)償采用式(6)。協(xié)議的作者在Mica2節(jié)點上進(jìn)行了仿真,通過20個節(jié)點實驗,采用Mac層時間戳技術(shù),得出鄰居節(jié)點之間的平均同步精度達(dá)到4.0μs,整個網(wǎng)絡(luò)的平均同步精度達(dá)到14.0μs。
4 分布式時隙同步算法
主從同步方法是網(wǎng)絡(luò)中所有的節(jié)點與參考節(jié)點保持時間同步,對參考節(jié)點依賴性高,且同步的誤差隨著跳數(shù)而累積;分布式同步則利用網(wǎng)絡(luò)中所有節(jié)點的彼此時間信息進(jìn)行調(diào)整,不依賴任何特殊的節(jié)點,且不會有誤差的累積,因此更加適合于大型的多跳自組織的無線傳感器網(wǎng)絡(luò)。分布式時隙同步算法利用了網(wǎng)絡(luò)中鄰居節(jié)點的時隙偏差值來計算時隙的調(diào)整量,實驗證明該算法收斂速度快,平均每個節(jié)點的計算量小,非常適合于移動自組網(wǎng)的無線傳感器網(wǎng)絡(luò)終端節(jié)點的運行。采用固定的時隙調(diào)整時,根據(jù)節(jié)點間時隙基準(zhǔn)是超前還是滯后來調(diào)整時隙基準(zhǔn)?;诜植际揭恢碌臒o線傳感器網(wǎng)絡(luò)的時間同步協(xié)議的收斂和加速問題研究中,將分布式一致的收斂和加速問題映射到馬爾科夫鏈的狀態(tài)轉(zhuǎn)移過程,但是排除了連通度對收斂速度的影響,得出收斂速度與節(jié)點鄰居數(shù)和網(wǎng)絡(luò)規(guī)模有關(guān)的結(jié)論,并通過100個節(jié)點組網(wǎng)實驗得出了可以降低25%的迭代數(shù)的結(jié)論。
評論