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

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

　　1 時(shí)鐘同步適用范圍

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

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

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

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

　　2.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　4 協(xié)議比較

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

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

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

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

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

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

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

　　參考文獻(xiàn)

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