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

　　引言

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

　　本文采用一個虛擬的時鐘作為全網同步的基準，所有節點在進入網絡后逐次逼近一個統一的虛擬時鐘，逼近過程采用基于本地時鐘的指數逼近方式，最終實現同步。

　　1 近期工作

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

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

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

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

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

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

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

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

　　2 數學準備

　　為實現最終結果全網各節點逼近一個統一的值，合理的策略是找到一個基準時鐘，對于相差較大的節點調整大，相差較小的節點調整小，保證向一個統一的時鐘逼近，最終實現同步。

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

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

　　圖1 調整因子和修正值關系圖