無線傳感網(wǎng)絡(luò)中時鐘同步的研究

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

　　1 時鐘同步適用范圍

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

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

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

　　2 無線傳感網(wǎng)絡(luò)中時鐘同步的基本概念

　　2.1 相關(guān)定義

　　要分析時鐘偏差，需給出如下定義。
　　(1)時間：Cp（t）表示網(wǎng)絡(luò)節(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+ρ)中變化。快慢時鐘與標準時鐘的比較如圖1所示。

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

　　2.2 網(wǎng)絡(luò)延時分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　3.5 其他時無線網(wǎng)絡(luò)時鐘同步協(xié)議

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

　　4 協(xié)議比較

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

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

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

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

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

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

　　時鐘同步協(xié)議是無線傳感網(wǎng)的一個必不可少的要素，為系統(tǒng)的其他功能(如事件的協(xié)調(diào)、節(jié)點定位、系統(tǒng)安全等)提供了一個統(tǒng)一的時間軸。所以無線傳感網(wǎ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，F(xiàn)rings 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