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

3 螢火蟲(chóng)同步算法和梯度同步算法
前面的時(shí)間同步技術(shù)都是基于時(shí)間信息交換的同步技術(shù)，然而在大規(guī)模的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，存在同步誤差會(huì)隨著跳距而積累的問(wèn)題和可拓展性需求等問(wèn)題。螢火蟲(chóng)同步技術(shù)和協(xié)作同步技術(shù)是為了實(shí)現(xiàn)節(jié)點(diǎn)的同步性，即使節(jié)點(diǎn)的某些周期性動(dòng)作具有相同的周期和相位，例如使一群螢火蟲(chóng)同步閃爍并且閃爍周期相同。1990年，Mirollo和Strogatz在Peskin模型的基礎(chǔ)上提出了更一般的脈沖耦合振蕩器模型(后簡(jiǎn)稱(chēng)為M＆S模型)。在此模型中，振蕩器使用狀態(tài)變量x來(lái)描述，x的變化服從函數(shù)f(φ)，其中f是一個(gè)[0，1]到[0，1]的光滑單淵遞增上凸函數(shù)，φ是相位變量且滿(mǎn)足(T是同步周期)。Mirollo和Strogatz從理論上證明了在M＆S模型下，多個(gè)耦合振蕩器系統(tǒng)在幾乎所有的初始情況下都能夠達(dá)到同步，并在無(wú)線(xiàn)多跳網(wǎng)絡(luò)測(cè)試床Gains上實(shí)現(xiàn)了M＆S模型的螢火蟲(chóng)同步算法。
麻省理工學(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í)鐘漂移的最低邊界滿(mǎn)足f(D)=Ω(d+lgD／lg lgD)，這也就是說(shuō)節(jié)點(diǎn)之間的時(shí)鐘漂移不只與兩個(gè)節(jié)點(diǎn)問(wèn)的距離有關(guān)，還與整個(gè)網(wǎng)絡(luò)的規(guī)模有關(guān)，越近的節(jié)點(diǎn)同步效果越好，反之越差。GTSP(Gradient Time Synchronization Protocol)協(xié)議中，每個(gè)節(jié)點(diǎn)通過(guò)接收鄰居節(jié)點(diǎn)的時(shí)間來(lái)修正自己的時(shí)鐘，整個(gè)網(wǎng)絡(luò)無(wú)需建立一個(gè)拓?fù)錁?shù)結(jié)構(gòu)，也無(wú)需參考節(jié)點(diǎn)，主要是實(shí)現(xiàn)直接的鄰居節(jié)點(diǎn)間直接的高精度的同步，同時(shí)考慮時(shí)間漂移和偏移補(bǔ)償，漂移補(bǔ)償采用式(5)。通過(guò)這種補(bǔ)償機(jī)制，所有節(jié)點(diǎn)的邏輯漂移將趨近值Xss；時(shí)鐘偏移補(bǔ)償采用式(6)。協(xié)議的作者在Mica2節(jié)點(diǎn)上進(jìn)行了仿真，通過(guò)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)依賴(lài)性高，且同步的誤差隨著跳數(shù)而累積；分布式同步則利用網(wǎng)絡(luò)中所有節(jié)點(diǎn)的彼此時(shí)間信息進(jìn)行調(diào)整，不依賴(lài)任何特殊的節(jié)點(diǎn)，且不會(huì)有誤差的累積，因此更加適合于大型的多跳自組織的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。分布式時(shí)隙同步算法利用了網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的時(shí)隙偏差值來(lái)計(jì)算時(shí)隙的調(diào)整量，實(shí)驗(yàn)證明該算法收斂速度快，平均每個(gè)節(jié)點(diǎn)的計(jì)算量小，非常適合于移動(dòng)自組網(wǎng)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)終端節(jié)點(diǎn)的運(yùn)行。采用固定的時(shí)隙調(diào)整時(shí)，根據(jù)節(jié)點(diǎn)間時(shí)隙基準(zhǔn)是超前還是滯后來(lái)調(diào)整時(shí)隙基準(zhǔn)?；诜植际揭恢碌臒o(wú)線(xiàn)傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議的收斂和加速問(wèn)題研究中，將分布式一致的收斂和加速問(wèn)題映射到馬爾科夫鏈的狀態(tài)轉(zhuǎn)移過(guò)程，但是排除了連通度對(duì)收斂速度的影響，得出收斂速度與節(jié)點(diǎn)鄰居數(shù)和網(wǎng)絡(luò)規(guī)模有關(guān)的結(jié)論，并通過(guò)100個(gè)節(jié)點(diǎn)組網(wǎng)實(shí)驗(yàn)得出了可以降低25％的迭代數(shù)的結(jié)論。