無(wú)線(xiàn)傳感器網(wǎng)絡(luò )同步算法的研究與探討

3 螢火蟲(chóng)同步算法和梯度同步算法
前面的時(shí)間同步技術(shù)都是基于時(shí)間信息交換的同步技術(shù)，然而在大規模的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中，存在同步誤差會(huì )隨著(zhù)跳距而積累的問(wèn)題和可拓展性需求等問(wèn)題。螢火蟲(chóng)同步技術(shù)和協(xié)作同步技術(shù)是為了實(shí)現節點(diǎn)的同步性，即使節點(diǎn)的某些周期性動(dòng)作具有相同的周期和相位，例如使一群螢火蟲(chóng)同步閃爍并且閃爍周期相同。1990年，Mirollo和Strogatz在Peskin模型的基礎上提出了更一般的脈沖耦合振蕩器模型(后簡(jiǎn)稱(chēng)為M＆S模型)。在此模型中，振蕩器使用狀態(tài)變量x來(lái)描述，x的變化服從函數f(φ)，其中f是一個(gè)[0，1]到[0，1]的光滑單淵遞增上凸函數，φ是相位變量且滿(mǎn)足(T是同步周期)。Mirollo和Strogatz從理論上證明了在M＆S模型下，多個(gè)耦合振蕩器系統在幾乎所有的初始情況下都能夠達到同步，并在無(wú)線(xiàn)多跳網(wǎng)絡(luò )測試床Gains上實(shí)現了M＆S模型的螢火蟲(chóng)同步算法。
麻省理工學(xué)院的Rui Fan、Nancy Lynch兩位作者第一次提出了GCS梯度同步算法。在移動(dòng)自組織網(wǎng)絡(luò )中往往是鄰居節點(diǎn)聯(lián)系比較密切，而相距較遠的節點(diǎn)很少交換消息，因此相距較遠的節點(diǎn)可以允許較大誤差。如數據融合中，具有相同父節點(diǎn)的子節點(diǎn)需要精確的同步，但是較遠的節點(diǎn)不是同一個(gè)父節點(diǎn)，可以允許誤差大一些。作者就是根據這一特征提出了梯度同步算法。在通常的時(shí)間同步算法的基礎上，假設兩任意節點(diǎn)i、j，f(dij)為節點(diǎn)i和節點(diǎn)j之間的最大時(shí)鐘差，時(shí)鐘記為。信息從節點(diǎn)i傳到j(luò )的傳播時(shí)間為0到dij，dij為節點(diǎn)i到節點(diǎn)j的距離。D=maxijdij為網(wǎng)絡(luò )的直徑。GCS提出了兩要求：

計算出時(shí)鐘漂移的最低邊界滿(mǎn)足f(D)=Ω(d+lgD／lg lgD)，這也就是說(shuō)節點(diǎn)之間的時(shí)鐘漂移不只與兩個(gè)節點(diǎn)問(wèn)的距離有關(guān)，還與整個(gè)網(wǎng)絡(luò )的規模有關(guān)，越近的節點(diǎn)同步效果越好，反之越差。GTSP(Gradient Time Synchronization Protocol)協(xié)議中，每個(gè)節點(diǎn)通過(guò)接收鄰居節點(diǎn)的時(shí)間來(lái)修正自己的時(shí)鐘，整個(gè)網(wǎng)絡(luò )無(wú)需建立一個(gè)拓撲樹(shù)結構，也無(wú)需參考節點(diǎn)，主要是實(shí)現直接的鄰居節點(diǎn)間直接的高精度的同步，同時(shí)考慮時(shí)間漂移和偏移補償，漂移補償采用式(5)。通過(guò)這種補償機制，所有節點(diǎn)的邏輯漂移將趨近值Xss；時(shí)鐘偏移補償采用式(6)。協(xié)議的作者在Mica2節點(diǎn)上進(jìn)行了仿真，通過(guò)20個(gè)節點(diǎn)實(shí)驗，采用Mac層時(shí)間戳技術(shù)，得出鄰居節點(diǎn)之間的平均同步精度達到4．0μs，整個(gè)網(wǎng)絡(luò )的平均同步精度達到14．0μs。


4 分布式時(shí)隙同步算法
主從同步方法是網(wǎng)絡(luò )中所有的節點(diǎn)與參考節點(diǎn)保持時(shí)間同步，對參考節點(diǎn)依賴(lài)性高，且同步的誤差隨著(zhù)跳數而累積；分布式同步則利用網(wǎng)絡(luò )中所有節點(diǎn)的彼此時(shí)間信息進(jìn)行調整，不依賴(lài)任何特殊的節點(diǎn)，且不會(huì )有誤差的累積，因此更加適合于大型的多跳自組織的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )。分布式時(shí)隙同步算法利用了網(wǎng)絡(luò )中鄰居節點(diǎn)的時(shí)隙偏差值來(lái)計算時(shí)隙的調整量，實(shí)驗證明該算法收斂速度快，平均每個(gè)節點(diǎn)的計算量小，非常適合于移動(dòng)自組網(wǎng)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )終端節點(diǎn)的運行。采用固定的時(shí)隙調整時(shí)，根據節點(diǎn)間時(shí)隙基準是超前還是滯后來(lái)調整時(shí)隙基準?；诜植际揭恢碌臒o(wú)線(xiàn)傳感器網(wǎng)絡(luò )的時(shí)間同步協(xié)議的收斂和加速問(wèn)題研究中，將分布式一致的收斂和加速問(wèn)題映射到馬爾科夫鏈的狀態(tài)轉移過(guò)程，但是排除了連通度對收斂速度的影響，得出收斂速度與節點(diǎn)鄰居數和網(wǎng)絡(luò )規模有關(guān)的結論，并通過(guò)100個(gè)節點(diǎn)組網(wǎng)實(shí)驗得出了可以降低25％的迭代數的結論。