無線傳感網不同于現有的無線自組網，它的每個網絡節(jié)點都受到計算能力、通信能力、儲存能力和帶電能力等諸多限制，并且以數據為中心、動態(tài)自組。正由于其上述限制，目前很多成熟的網絡協(xié)議不再適合無線傳感網，時鐘同步協(xié)議就是其中之一。

　　1 時鐘同步適用范圍

　　時鐘同步就是通過一定的機制使系統(tǒng)各節(jié)點的時間與標準時間同步，通常采用與協(xié)調世界時UTC(Coordinated Universal Time）同步。

　　有線網絡設計的最終目的在于利用現有資源最大限度地增大鏈路帶寬，提高服務質量，因而具有相對穩(wěn)定的網絡結構，可靠的鏈路連接，充足的能量供給。運行在其上的網絡協(xié)議通常很少考慮節(jié)約能量，降低節(jié)點負載，充分挖掘運行效率。所以其時鐘同步協(xié)議將更多以算法的精度、魯棒性和易擴充性為標準。

　　無線傳感網作為一個大范圍的分布式網絡，像其他網絡一樣，也需要時鐘同步以達到系統(tǒng)事件的協(xié)調控制，正確的數據融合。但它受能量供給、節(jié)點計算能力、鏈路質量的限制，必須對現有的時鐘同步協(xié)議重新分析和評估。如應用于Internet的網絡時間協(xié)議NTP(Network Time Protocol)，它采用層次結構，次層節(jié)點通過兩次包交換達到與上層節(jié)點時鐘同步，但由于其運算復雜，且需要較穩(wěn)定的網絡結構作為支撐，因而不適應對于能量、體積和計算能力都受限制且動態(tài)性強的無線傳感網絡。

　　2 無線傳感網絡中時鐘同步的基本概念

　　2.1 相關定義

　　要分析時鐘偏差，需給出如下定義。
　　(1)時間：Cp（t）表示網絡節(jié)點p的時間，當Cp（t）=t，表示p的時間與標準時間同步。
　　(2)震蕩頻率：時鐘所擁有的震蕩頻率，在t時刻p節(jié)點的時鐘頻率為Cp（t）′。
　　(3)時鐘偏差：表示某時鐘與標準時鐘的偏差，Cp（t）-t。兩個不同節(jié)點p和l的時鐘在t時刻的偏差可表示為Offset＝Cp（t）-Cl（t）。
　　(4)頻率偏差：表示某時鐘和標準時鐘的頻率偏差。兩個不同時鐘的Skew=Cp（t）′-Cl（t）′。

　　如果頻率偏差限制在ρ，標準時鐘頻率為1，則時鐘頻率將在(1-ρ，1+ρ)中變化?？炻龝r鐘與標準時鐘的比較如圖1所示。

　　(5)時鐘偏移：表示時鐘函數的二階倒數Cp（t）″，兩個不同時鐘的Drift=Cp（t）″-Cl（t）″。
　　
　　從圖1中可以發(fā)現，即使時鐘在開始是同步的，經過一段時間后，由于時鐘頻率的不同而不斷積累的時鐘偏差將越來越明顯。

　　2.2 網絡延時分析

　　網絡傳輸總會產生消息延時，因此一個節(jié)點的時間戳在到達對方節(jié)點時已不能代表自身的時間。這就需要對網絡延時作充分的分析，確定延時帶來的誤差來源。無線傳感網中消息發(fā)生延時的環(huán)節(jié)很多，其中主要存在于發(fā)送時間、訪問時間、傳送時間、廣播時間、收到時間、接收時間、中斷處理時間、編碼時間和解碼時間。其中每個環(huán)節(jié)都可能帶來延時誤差，對誤差充分、準確的估計才能設計出精確度高、負載低的時鐘同步算法。

　　3 無線傳感網時鐘同步協(xié)議分析

　　Jeremy Elson和Kay Romer在2002年8月的HotNets-I國際會議上率先提出并闡述了無線傳感網中時鐘同步機制的研究課題，在傳感網絡研究領域引起了關注。目前提出的基本同步機制有RBS、TPSN和DMTS等，同時新的算法仍在不斷涌現，如TINY/MINI-SYNC和FTSP等。

　　3.1 RBS時鐘同步協(xié)議

　　RBS(Reference Broadcast Synchronization)參考廣播時鐘同步協(xié)議是利用無線鏈路層廣播信道的特點，一個節(jié)點發(fā)送廣播消息，認為在同一廣播域的其他節(jié)點同時收到廣播消息，并記錄該點的時間戳，之后接收節(jié)點通過消息交換它們的時間戳，通過比較和計算，達到高度精確時鐘同步。時鐘同步協(xié)議的關鍵路徑如圖2所示。對于傳統(tǒng)的時鐘同步協(xié)議關鍵路徑是指從發(fā)送端讀取時鐘到接收端讀取時鐘所經過的時間，其中包含了信息包在進入信道之前在網絡適配器(NIC)內的停留時間，如圖2 (a)所示。而RBS的關鍵路徑指從信息包進入信道到最后一個接收端讀取時鐘所經過的時間，消除了發(fā)送和訪問時間，從而提高了精度，這也是RBS的優(yōu)點所在，從圖2可以看出RBS協(xié)議和傳統(tǒng)的基于發(fā)送/接收方式的時鐘同步協(xié)議在影響非決定性誤差上有著明顯的差異。

　　在RBS時鐘同步協(xié)議中為了對網絡上可能出現的非確定性延時作相應的補償，采用了多次發(fā)包求平均值的方案。RBS的時間偏差為：
　　　　
　　其中，i，j代表不同節(jié)點。K為數據包的序列號，m表示最大次數。

　　RBS的另一個特色是無本地時鐘校正，把計算出來的時鐘偏差和頻率偏差值保存在一張表中，當其他節(jié)點讀本地時間時，本地節(jié)點將會查詢該表翻譯出正確的時間。這主要是從減少能量消耗的角度考慮。此外RBS協(xié)議還采用了次 同步方式，就是只有在時鐘同步需要時才運行，這樣大大減少了能量的消耗。RBS在多跳網絡中也有應用。

　　3.2 TPSN時鐘同步協(xié)議

　　無線傳感網絡時間同步協(xié)議TPSN(Timing- sync Protocol for Sensor Networks）與傳統(tǒng)的NTP協(xié)議類似，采用如圖3所示的兩次握手交換時間戳來達到時鐘同步。假設t為服務器和客戶端之間的時間偏差，d為兩者之間的往返時間。則由于：
　　

　　計算出時鐘偏差t后就可以相應地調整本地時鐘與上一層節(jié)點同步。為減小訪問時間帶來的延時誤差，TPSN在MAC層開始發(fā)送時才打上發(fā)送時間戳。在 Mica平臺測試的結果表明TPSN時鐘同步平均偏差是16.9μs，而RBS是29.13μs，可見TPSN擁有更精確的時鐘同步。TPSN時鐘同步過程分為兩階段：第一階段是層次發(fā)現階段。該階段是在網絡部署后將網絡節(jié)點層次化。分為0到n個層次；第二個階段為時鐘同步階段，層次結構建立后，通過同步廣播包，從0層次到n層次逐層時鐘同步。TPSN協(xié)議可以支持外部時鐘源，使整個無線傳感網與外部時鐘同步，通常采用根節(jié)點裝載GPS同步設備。

　　3.3 DMTS時鐘同步協(xié)議

　　延遲測量時間同步DMTS（Delay Measurement Time Synchronization）協(xié)議是利用合理的估計網絡延時來設計時鐘同步算法。時鐘同步的步驟是：(1)在所有節(jié)點中選擇一個主節(jié)點；(2)主節(jié)點廣播其本地時鐘，并且在發(fā)送前導幀和起始符時打上時間戳t0，前導幀和起始符主要用于接收節(jié)點進行接受同步；(3)接收節(jié)點收到廣播分組后打上時間戳t1，并且在調整自身時鐘前打上時間戳t2。該過程中假設發(fā)送1比特位需要時間為t，發(fā)送信息位的個數是n，則接收節(jié)點應該調整自己的時鐘為t0＋nt＋（t2－t1）。圖4說明了DMTS協(xié)議的時鐘同步過程。

　　DMTS協(xié)議的精確性主要取決于延時測量的精確度，是一種靈活、輕量級、能量利用高效的時鐘同步機制，可應用于時鐘同步要求不太高的無線傳感網絡中。該機制還能夠更好地支持與外部時鐘源及多跳點的同步。

　　3.4 連續(xù)時鐘同步協(xié)議

　　在時鐘同步協(xié)議中，要求在重新調整時鐘時不可以向后調整時鐘，時鐘的調整應該是一個逐漸平滑的過程，以保持系統(tǒng)事件的連續(xù)性。假設在18時第一次同步，在 20時第二次同步，而某系統(tǒng)事件定在19時發(fā)生，若采用瞬間同步，則系統(tǒng)就會將該事件忽略，導致數據不完整。連續(xù)時鐘同步協(xié)議擴展了IEEE802.11 標準，采用了增大或減小時鐘頻率的方法來調整本地時鐘與時鐘源同步。

　　連續(xù)時鐘同步協(xié)議中的時間路徑如圖5所示。主節(jié)點在t1時間準備一個指示分組，在t2時間向鄰近節(jié)點廣播；假設該分組被鄰近節(jié)點及時接收，即在t3時間接收到分組且在t4時間記錄本地的時間戳；在t5時間主節(jié)點又會發(fā)送一個確認分組。最后每個接收節(jié)點計算與主節(jié)點的時鐘偏差并在t6時間調整本地時鐘。這里的本地時鐘是指與本地物理時鐘相對應的虛擬時鐘。

　　3.5 其他時無線網絡時鐘同步協(xié)議

　　作為一個新的領域無線傳感網的很多協(xié)議沒有向Internet上的協(xié)議那樣有統(tǒng)一的標準，而且常常是一個協(xié)議在一個平臺上是最優(yōu)的，但到另外的平臺可能不再是最優(yōu)，所以相關的協(xié)議也在不斷的發(fā)展中。時鐘同步中也還有其他很多優(yōu)秀的協(xié)議，如Maroti M等人提出的洪泛時間同步協(xié)議FTSP（Flooding Time Synchronization Protocol），Chaudhuri P提出的隨機時鐘同步協(xié)議PCS（Probabilistic Clock Synchronization）等。

　　4 協(xié)議比較

　　上述各種協(xié)議的設計思想都有不同的側重點，所以在具備很多優(yōu)點的同時也攜帶著這樣或那樣的不足。因此在選擇相關協(xié)議或設計新的協(xié)議時都必須要權衡這些因素。以下是關于這些協(xié)議的優(yōu)缺點比較。

　　RBS時鐘同步協(xié)議中發(fā)送和媒體訪問的時間偏差(即最大的時鐘誤差來源)被去除了。時鐘的調整不會影響時鐘偏差的計算，因為該協(xié)議不會調整本地的時鐘，而是維持了一張時鐘偏差表。RBS協(xié)議不僅適用于無線網絡，也適用于有線網絡。RBS的不足之處也很多，最重要的一個就是擁有O(N2)的時間復雜度，這對于能量有限的無線傳感網而言是最大的能量開銷。

　　TPSN時鐘同步協(xié)議取得了比RSB更精確的時鐘同步效果，而且方便地支持與外部時鐘源同步。但是其能量開銷相對較大，其最大的不足是在基于層次模型的情況下不利于網絡的動態(tài)變化，而無線傳感網的一個特點就是網絡具有動態(tài)性。

　　DMTS時鐘同步協(xié)議和上述兩種協(xié)議相比需要傳輸的消息少，能量開銷小，可以在全網絡中時鐘同步，并且支持與外部時鐘源同步。但是，這種算法在能量開銷與同步精度之間做了折中 ，所以精度相對弱些，可以應用于對精度要求不是很高的無線傳感網絡中。

　　連續(xù)時鐘同步協(xié)議在傳輸延時很小的情況下，可達到較高的精度要求。時間復雜度也很小，一次同步只需要一次發(fā)包。尤其是采用了連續(xù)調整時鐘的方法使得系統(tǒng)事件控制的連續(xù)性得以保證。

　　同樣，其他的時鐘同步協(xié)議也具有各種優(yōu)缺點，這些因素都決定了協(xié)議的設計平臺和系統(tǒng)的應用領域。

　　時鐘同步協(xié)議是無線傳感網的一個必不可少的要素，為系統(tǒng)的其他功能(如事件的協(xié)調、節(jié)點定位、系統(tǒng)安全等)提供了一個統(tǒng)一的時間軸。所以無線傳感網時鐘同步協(xié)議的研究和創(chuàng)新具有重要意義。

　　參考文獻

1 Romer K.Time synchronization in adhoc networks.ACM Int′l symp mobile AD Hoc Networking and computing(MobiHoc)，Long Beach，USA，2001
2 Elson J，Griod L，Esrein D.Fine-grained network time syn　chronization using reference broadcasts.In：Proc 5th symp operating systems design and implementation，Boston，MA， 2002
3 Sichitiu M L，Veeraritiphan C，Simple accurate time synchronization for wireless sensor networks.In：Proceedings of IEEE wireless communication and networking conference，2003
4 Gurewitz O，Cidon I，Sidi M.Network time synchronization using clock offset optimization.In：Proceeding of the 11th IEEE international conference on network protocols(ICNP′03)， 2003
5 Mock M，Frings R，Nett E et al.Continuous clock synchro- nization in wireless real-time applications.In：Proceedings of 19th IEEE synposium on reliable distributed systems，2002