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

　　引言

　　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 調整因子和修正值關系圖

　　3 算法實現

　　3.1 時鐘模型

　　WSN中各節點的時鐘主要包括一個統一的基準時鐘，一個相對于基準時鐘的偏移，和由于時鐘頻率不一致而導致的扭曲。定義c（t）為一個參考時鐘，是一個統一穩定的基準值。每個節點有自己的時鐘，是一個關于t的函數ci（t），每個節點的本地時鐘相對基準時鐘的偏移是指由于長期累積而導致的時鐘不一致，扭曲是指由于石英晶體振蕩器振蕩頻率不一致，從而導致了時鐘與基準時鐘之間存在差別。

　　設兩個節點的時鐘分別為ci（t）和cj（t），如果時鐘在時間t完全正確，則ci（t）＝cj（t）＝c（t），但是在實際中兩個時鐘往往是不相等的。這是由于晶體振蕩器本身技術原因和外部工作環境（如溫度、壓力）等因素引起的，因此，t時刻每個節點的時鐘模型為：ci（t）=αit+βi，其中αi為晶體振蕩器自身頻率的不一致而帶來的扭曲，βi為時鐘長期積累的偏移。

　　為達到時鐘一致，最關鍵的問題是使得任何節點的ci（t）＝c（t），即補償時鐘的扭曲αi和時鐘偏移βi，在任何時刻各節點的時鐘不再偏移，且振蕩頻率也完全一致。

　　3.2 算法實現

　　TSMA要達到的目標是內部一致。在每個同步循環，算法更新每個節點的補償參數，通過這樣的方式使時鐘達到一致：limt→∞ci（t）=cv（t）。其中cv（t）是本算法的虛擬時鐘，虛擬時鐘并不是一個現實中存在的時鐘，而是所有節點以之為基準的一個時鐘，是由本算法在運行過程中產生的。虛擬時鐘有相對于實際時鐘的扭曲率和相對偏移。各節點對本節點扭曲和偏移進行補償，從而同步于虛擬時鐘，實現全網同步。

　　設虛擬時鐘為cv（t）=α·t+β，為使得各節點時鐘最后同步于虛擬時鐘，需要采用修正參數，設對于扭曲的修正參數為α′，對于偏移的修正參數為β′，則運行過程中，通過修正參數使得時鐘保持一致的條件為：limt→∞（α′ci（t）+β′）=cv（t）=α·t+β，即limt→∞（α′ αit+α′βi+β′）=α·t+β，由此可得到修正參數為：

　　為得到補償各節點的時鐘扭曲和偏移，每個節點在算法執行周期內完成對兩種參數的修正。修正主要包括兩個過程：第一個過程為扭曲修正，通過修正扭曲值使得節點與虛擬時鐘頻率一致；第二個過程為偏移修正，通過修正偏移值確保全網時鐘同步。

　　3.2.1 扭曲修正

　　扭曲修正的目的是確保時鐘在相同的振蕩頻率下工作，即limt→∞α′αi=α。對扭曲參數的修正采用指數逼近的方式，以將所有的時鐘扭曲趨近于α，每個節點執行的算法如下：

　　① 運行同步算法前，節點設置扭曲估計αi為１，同時準備搜索鄰居節點的時鐘扭曲信息。

　　② 由于各節點并不一定知道鄰居節點的存在，在節點廣播自己的時鐘信息時，有可能別的節點也在廣播時鐘信息，從而導致廣播失敗，因此在MAC層需要一個類似CSMA/CD的協議，以確保各節點能正確廣播自己的時鐘信息。

　　③ 設共有n個節點，第i（1≤i≤n）個節點存儲并廣播自己的時間信息（αi，Ti），其中Ti為本節點當前時間值，由于節點距離和傳輸速度是已知的，所以接收到廣播的節點根據Ti確定接收時的時間是可行的。

　　④ 節點i收到第j（1≤j≤n）個節點的廣播包，包含了節點j的時間信息（αi，Tj），如果第j個節點是第１次出現，則節點i只存儲節點j的時間信息，直到收到節點j的下一個時間信息（αj+1，Tj+1）。

　　⑤ 此時比較節點i和節點j的扭曲，計算R1=αi（Tj+1-Tj）和R2=αj（Ti+1-Ti），若R1》R2，則需要對節點i的扭曲率進行修正，設兩者的差值為λi=αi-αj，調整因子為σ=min（αi，αj）max（αi，αj），設置扭曲率和校正值為λ′i=λi（e-eσ）（e- 1），設置修正值調整的閾值RT，當節點i首次出現λ′i低于閾值要求時不作調整，以避免部分失效節點重新進入網絡時對鄰居節點造成影響。則節點i新的扭曲值為

　　則αi=α，同時保留最新的節點i和節點j的時間信息T，即Ti=Ti+1，Tj=Tj+1。

　　⑥ 節點重復步驟②～⑤，直到R1＝R2，兩節點扭曲率一致，此時節點已經更新了自己的時鐘扭曲率，只需要保持偏移一致，即可達到時鐘同步。

　　3.2.2 偏移修正

　　修正完扭曲率后，需要對偏移進行修正，以達到節點時鐘同步。修正偏移值的關鍵是找到合適的偏移值，使得各節點能夠同步到一個統一的偏移值，從而統一于一個虛擬的時鐘。設每個節點的偏移值為βi，1≤i≤n，則節點i在接收到鄰居節點的偏移值后，很容易得到一個平均值β-1n∑ni=1βi，顯然這一平均值即為要找的虛擬時鐘的偏移值，當各節點同步于這一偏移值，便實現了全網時鐘同步。由于部分節點的時鐘偏移值較大，同時每次更新的節點為一跳內的節點，采用一次調整偏移值至平均值的方法并不能以最快的速度使得全網節點偏移同步，而采用逐次指數逼近的方式，對偏移相差較大的節點修正參數較大，偏移相差較小的節點修正參數較小，使得全網所有節點逼近統一的偏移值。本算法采用了如下步驟：

　　① 節點i首先估計自己的偏移值βi，1≤i≤n，并開始收聽廣播，和扭曲修正一樣，廣播已經考慮了沖突避免。

　　② 節點收集一跳內的鄰居偏移值，得到偏移平均值β-1n∑ni=1βi。

　　③ 節點i計算與平均偏移值的差值λi=βi-β-，設調整因子為γi=min（βi，β-）max（βi，β-），顯然0≤γi≤1，則某節點所需調整的參數為λ′i=λi（e-eγi）（e-1）。設置修正值調整的閾值RT，當節點i首次出現λ′i低于閾值要求時不作調整，以避免部分失效節點重新進入網絡時對鄰居節點的影響。新的偏移值為

　　則βi=β，節點i采用指數逼近的方法，逐次向平均值逼近。

　　④ 節點i再次收聽鄰居節點廣播，重復步驟②③，直到λi=βi-β-低于設定值，實現了全網同步。

　　由于指數逼近的方式在節點偏移相差較大時調整較大，節點偏移相差較小時調整較小，適用于網絡中有新節點出現時導致偏移相差較大的情況。采用指數逼近方式后，與平均值誤差較大的節點調整大，加快了收斂速度，與平均值相差小的節點調整小，控制了向鄰居節點擴散偏移調整的范圍。同時，在全網節點偏移一致后，指數逼近的方式使得節點調整幅度小，避免了由于某一個時鐘節點失誤而帶來的大范圍時鐘偏移調整，保證了全網時鐘同步的穩定性。

　　4 仿真

　　本文采用指數逼近的方式調整各節點時鐘扭曲和偏移參數，使得各節點修正時鐘扭曲和偏移，最終同步于一個統一的時鐘，為顯示算法有效性和可靠性，用 Matlab進行了仿真。仿真環境為在8×8的格狀網絡里放置64個節點，每個格子包含一個節點，節點處于每個格子的中央區域，設每個節點用于校準的晶振參考值是32 768 Hz，即一個振蕩周期為30.5 μs，小于一個周期的時鐘誤差是無法識別的，因此用1 tick =30.5 μs來表示時鐘誤差的最小單位。每個節點的扭曲率服從平均值為１、方差為10-5的正態分布，節點的初始偏移在0～1000隨機分布。具體得到：節點扭曲 ——平均值為1，方差為10-5的正態分布，即N（1，10-5）；初始偏移——在0～1000 tick間隨機分布。

　　在運行過程中，每個節點運行扭曲和偏移的修正協議，網絡中沒有一個實際的基準時鐘，而是在運行過程中逐漸收斂到一個統一的時鐘，從而實現節點同步。

　　設同步每個循環周期為30 s，節點在每個循環期間隨機廣播自己的同步幀，節點的傳輸距離為2個單位，即節點距離相差不超過2時可以收到對方消息。為避免網絡穩定運行時部分偏差較大的節點導致網絡中大部分節點同時調整參數，仿真中對首次出現的調整參數低于10%的修正參數不作調整。為驗證本算法的對多種網絡拓撲的適應性，設置了不同的網絡狀況，以檢驗算法的有效性和可靠性。

　　圖2演示了節點使用本算法在網絡運行初期、穩定工作狀態、部分節點忽然失效或主動停止工作時的性能。每個同步周期設置為30 s。仿真持續時間為30 min，分為A、B、C、D四個不同區域。區域A所有節點均工作，由于各節點運行本算法前時鐘偏差較大，前3個同步階段，節點根據收到的偏移值調整參數，偏移校正效果不明顯，從第３個周期開始，節點開始補償時鐘偏移和扭曲，經過9個循環周期的補償，所有節點到達同步狀態，即任意兩節點間的時鐘偏差在10個節拍以內。在區域B的開始階段，50％的節點選擇隨機關閉，又隨機工作，一但一個節點打開，即開始運用本算法，因為采用指數逼近的方式，節點一但開始工作時即開始執行本算法，由于大部分節點已經同步，新加入的節點的時鐘調整不會對已經同步的節點造成影響，由圖中可以看出節點能夠在開始工作后迅速進入同步狀態。在區域C中，30％的節點停止工作。在區域D，這30%的節點開始工作，由于沒有時鐘調整，剛開始工作時與別的節點時鐘無法同步，此時能夠看到，各節點開始工作后時鐘很快收斂，實現了全網時鐘同步。

　　圖2 動態網絡下時鐘同步的性能

　　結語

　　從WSN時鐘同步的發展趨勢來看，隨著WSN節點數量的增加，采用基于本地信息的分布式同步策略，能夠提高WSN節點工作效率和穩定性。本算法在動態網絡結構下實現了較快的收斂速度，未來的工作集中在網絡穩定運行后如何減少由于時鐘同步帶來的非必要消耗，從而提高節點生存時間和網絡生命周期。