提出了一個基于虛擬時鐘指數(shù)逼近的無線傳感器網(wǎng)絡時鐘同步協(xié)議，采用一個虛擬時鐘作為全網(wǎng)同步的基礎，從而實現(xiàn)全網(wǎng)同步。由于采用虛擬時鐘，使得各節(jié)點進入網(wǎng)絡時有了統(tǒng)一的標準，對時鐘扭曲和偏移采用指數(shù)逼近的方法，在相差較大時調(diào)整快，提高了同步效率。仿真數(shù)據(jù)證明，本協(xié)議能有效地提高同步效率，并適應于不同的網(wǎng)絡拓撲。

　　引言

　　WSN時鐘同步［1］關鍵問題主要有兩個方面：一是標準的確立，即有一個時鐘作為全網(wǎng)基準，不管是事實上存在的時鐘，還是虛擬的時鐘；二是標準的共享，即各節(jié)點都按照標準來調(diào)整自己的工作狀態(tài)。目前WSN時鐘同步主要集中于兩個方面：集中式和分布式。集中式如TPSN［2］、RBS［3］、 FTSP［4］。分布式同步如ATS［5］、CCS［6］、GCS［7］。

　　本文采用一個虛擬的時鐘作為全網(wǎng)同步的基準，所有節(jié)點在進入網(wǎng)絡后逐次逼近一個統(tǒng)一的虛擬時鐘，逼近過程采用基于本地時鐘的指數(shù)逼近方式，最終實現(xiàn)同步。

　　1 近期工作

　　WSN中時鐘同步的主要方法如下，前三者為集中式同步，后三者為分布式同步方法：

　　TPSN（TimingSync Protocol for Sensor Networks）［2］是用于WSN中時鐘同步的技術，主要包括標準發(fā)現(xiàn)階段和同步階段。發(fā)現(xiàn)階段將整個網(wǎng)絡劃分為樹狀層次拓樸，根結(jié)點是首要結(jié)點，然后采用普通的握手協(xié)議實現(xiàn)全網(wǎng)同步。TPSN利用MAC層時間戳減少信息傳輸?shù)难訒r和提高同步準確性，收斂速度隨著網(wǎng)絡規(guī)模的擴大線性增長。該算法的限制是，當根結(jié)點或者父結(jié)點失效時，需要有相應的策略去選擇新的根結(jié)點或父結(jié)點。同時由于地理上相近的節(jié)點，并不一定能夠在實際中成為樹狀網(wǎng)絡中的鄰近節(jié)點，因此降低了同步性能。

　　RBS（Reference Broadcast Synchronization）［3］著眼于提供基于信標信號單跳范圍內(nèi)的節(jié)點同步方案，其最大的貢獻在于去除了信息傳輸過程中的兩個影響因素——傳輸時間和接入時間，即消息花在非時鐘同步上的時間最少。RBS采用最小方差線性回歸的方法補償時鐘扭曲，收斂速度隨著網(wǎng)絡規(guī)模也呈線性增長趨勢，使用信標節(jié)點使得傳輸易受到干擾，同時也會因為節(jié)點移動而導致時鐘同步失敗。

　　FTSP（Flooding Time Synchronization Protocol ）［4］是一個自治、多跳的同步協(xié)議，通過無線棧中低層無線消息中的時間戳，完全消除了CSMA協(xié)議中的接入時間，從而提供了較高的準確性。FTSP通過線性回歸補償部分節(jié)點的時鐘扭曲能夠得到更高的準確性。FTSP還采用了幾種機制來提高節(jié)點和鏈路失敗后的魯棒性，比如周期性地采用洪泛同步方式同步節(jié)點時鐘，由于FTSP對動態(tài)拓撲的適應性和對不同時鐘扭曲的修正能力，成為事實上的WSN時鐘同步標準，但和TPSN一樣，F(xiàn)TSP也無法消除本身收斂速度慢等限制。

　　GCS（Global clock synchronization）［5］中，每個節(jié)點依次向鄰居廣播自己的同步申請，鄰居依次回答并包含自己的本地消息，處于本次接收中心的節(jié)點從時間戳中計算一個平均值并向鄰居廣播，從而得到一個基準，一直重復，直到全網(wǎng)同步，這種分布式的策略無法補償時鐘扭曲，不能從根本上解決時鐘同步的效率問題。

　　ATS（Average Time Synchronization）［6］使用兩種一致算法以調(diào)整補償參數(shù)，聚集所有節(jié)點于一個穩(wěn)定的虛擬時鐘。ATS分為兩個階段，第一階段網(wǎng)絡中各節(jié)點廣播一個本地時間戳，用以估計相互間的時鐘扭曲率，然后廣播節(jié)點自身相對一個虛擬（實際存在）時鐘扭曲率的當前估計，并接收別的節(jié)點的扭曲估計，從而調(diào)整它們實際的時鐘。在消除偏移錯誤時也采用同樣的原則，這種分布式協(xié)議，收斂速度較慢，且與網(wǎng)絡拓樸結(jié)構有關，還需要進行算法改進，以提高收斂速度和對網(wǎng)絡結(jié)構的自適應能力。

　　CCS（Consensus Clock Synchronization）［7］利用平均一致算法補償時鐘偏移，通過在每次偏移補償中消除累積偏移錯誤，節(jié)點能夠從一致時間中獲得自己的時鐘扭曲，這一信息可以用于自身的糾正，從這一意義上說CCS是一種增強型的ATS，提供了一種分布式的解決方案，其缺點仍然是收斂速度不快。

　　本文的方法和CCS相近，是一種分布式的利用節(jié)點本地信息修正時鐘參數(shù)的算法，不同之處在于采用了指數(shù)方式逐次逼近的方式補償時鐘扭曲和偏移參數(shù)，這樣能像集中式那樣收斂速度快，同時隨著網(wǎng)絡規(guī)模的增長收斂時間呈線性變化，且在消息丟失和節(jié)點失效時具有較高的可靠性。

　　2 數(shù)學準備

　　為實現(xiàn)最終結(jié)果全網(wǎng)各節(jié)點逼近一個統(tǒng)一的值，合理的策略是找到一個基準時鐘，對于相差較大的節(jié)點調(diào)整大，相差較小的節(jié)點調(diào)整小，保證向一個統(tǒng)一的時鐘逼近，最終實現(xiàn)同步。

　　為實現(xiàn)節(jié)點時鐘與基準時鐘相差越大，所需的修正參數(shù)就越大。本算法采用修正參數(shù)與平均值的差值大小指數(shù)對應關系，即越接近平均值的節(jié)點偏移，調(diào)整的修正參數(shù)越小。指數(shù)方式的調(diào)整方式能夠優(yōu)化節(jié)點調(diào)整的效率和可靠性，從而得到更佳的收斂速度和可靠性，設第某節(jié)點本身的偏移值為β，所需要逼近的值為 β-，λ=β-β-，設調(diào)整因子為γ=min（β，β-）max（β，β-），顯然0≤γ＜1，則某節(jié)點所需調(diào)整的參數(shù)為：

　　調(diào)整因子和修正值關系如圖1所示，當調(diào)整因子越大，表明與標準值越接近，所調(diào)整的比例便越小，即節(jié)點與標準值差值λ為0時，節(jié)點不需要對自己的值作任何改動，而節(jié)點自身值與平均值相差越大時，節(jié)點所需調(diào)整的參數(shù)越大。在實際執(zhí)行時，可以設置λ′的一個閾值RT，使得需要調(diào)整的數(shù)值在某一范圍內(nèi)時，即 λ′小于某一規(guī)定值時，節(jié)點可在一定時間內(nèi)不調(diào)整，這樣可以在很大程度上避免由于某個新的節(jié)點參數(shù)與別的節(jié)點參數(shù)相差太大時，導致整個網(wǎng)絡節(jié)點調(diào)整的情況。RT值的設置與網(wǎng)絡規(guī)模對同步收斂速度的要求有關。

　　圖1 調(diào)整因子和修正值關系圖