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é)論。