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