無(wú)線傳感器網(wǎng)絡(luò)課件：時(shí)鐘同步

時(shí)鐘同步9.1時(shí)鐘同步基礎(chǔ)9.2時(shí)鐘同步協(xié)議

9.1時(shí)鐘同步基礎(chǔ)

9.1.1同步消息現(xiàn)有的大多數(shù)時(shí)鐘同步協(xié)議是基于“成對(duì)同步(pairwisesynchronization)”的，即一對(duì)節(jié)點(diǎn)使用至少一個(gè)同步消息來(lái)相互同步它們的時(shí)鐘，通過(guò)多對(duì)節(jié)點(diǎn)之間重復(fù)這一同步過(guò)程直到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都調(diào)整了它們的時(shí)鐘為止，這樣就能夠?qū)崿F(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)鐘同步。1．單向消息交換當(dāng)僅使用單個(gè)消息同步兩個(gè)節(jié)點(diǎn)的時(shí)鐘時(shí)，使用成對(duì)同步機(jī)制是最簡(jiǎn)單的方法，即一個(gè)節(jié)點(diǎn)向另一個(gè)節(jié)點(diǎn)發(fā)送時(shí)間戳，節(jié)點(diǎn)i在時(shí)間t1給節(jié)點(diǎn)j發(fā)送了同步消息。時(shí)間t1作為時(shí)間戳嵌入在該消息中。根據(jù)接收到的該消息，節(jié)點(diǎn)j從它的本地時(shí)鐘獲得時(shí)間戳t2。兩個(gè)時(shí)間戳之間的差值就是時(shí)鐘偏移值δ(節(jié)點(diǎn)i和j時(shí)鐘之間)。兩個(gè)時(shí)間戳之間的差值可精確表示如下：在無(wú)線介質(zhì)上傳播時(shí)間非常小，并且一般忽略或假定為某一常數(shù)值。要注意的是，使用這種方法節(jié)點(diǎn)j能夠計(jì)算出偏移值并調(diào)整它的時(shí)鐘與節(jié)點(diǎn)i的時(shí)鐘相匹配。2．雙向消息交換更為精確的方法是使用兩個(gè)同步消息，節(jié)點(diǎn)j在時(shí)間t3發(fā)布包含時(shí)間戳t1、t2和t3的消息作為響應(yīng)。根據(jù)在時(shí)間t4接收到的第二個(gè)消息，再假定傳播時(shí)延是固定值，兩個(gè)節(jié)點(diǎn)都能夠確定時(shí)鐘偏移值，節(jié)點(diǎn)i現(xiàn)在能夠更準(zhǔn)確地計(jì)算傳播時(shí)延和偏移量，計(jì)算方法如下：3．接收器-接收器同步應(yīng)用接收器-接收器同步原理的協(xié)議采取的是一種不同的方法，其同步是基于同一消息到達(dá)每個(gè)接收器的時(shí)間，這有別于大多數(shù)同步機(jī)制中傳統(tǒng)的發(fā)送器-接收器方法。在廣播通信環(huán)境中，這些接收器在大概相同的時(shí)間獲得某個(gè)發(fā)送器的發(fā)送消息，然后交換這些消息的到達(dá)時(shí)間計(jì)算偏移值。如果有兩個(gè)接收器，就需要三個(gè)消息來(lái)同步兩個(gè)接收器。9.1.2通信時(shí)延節(jié)點(diǎn)間通信時(shí)延的不確定性對(duì)時(shí)鐘同步所能達(dá)到的精確程度影響較大。一般情況下，同步消息所經(jīng)歷的時(shí)延是幾種時(shí)延的總和，下面詳細(xì)介紹這幾種時(shí)延。發(fā)送時(shí)延(tsend)：節(jié)點(diǎn)i發(fā)布帶有時(shí)間戳的同步分組SYNC啟動(dòng)兩個(gè)節(jié)點(diǎn)之間的時(shí)鐘同步握手過(guò)程，節(jié)點(diǎn)生成SYNC分組并傳輸?shù)骄W(wǎng)絡(luò)接口的時(shí)間即為發(fā)送時(shí)延。發(fā)送時(shí)延是嵌入式設(shè)備上操作系統(tǒng)、內(nèi)核和發(fā)送器時(shí)延的和。重要的問(wèn)題是，由于嵌入式系統(tǒng)中每個(gè)硬件和軟件組件之間交互時(shí)間的差異性和復(fù)雜性，導(dǎo)致發(fā)送時(shí)延是不確定的。接入時(shí)延(tacc)：這個(gè)時(shí)延是發(fā)送者接入物理信道所花費(fèi)的時(shí)間，由所使用的介質(zhì)訪問(wèn)控制(MAC)協(xié)議決定。基于競(jìng)爭(zhēng)的MAC協(xié)議要求節(jié)點(diǎn)接入信道之前，必須等待空閑信道，因?yàn)榇蠖鄶?shù)MAC協(xié)議使用指數(shù)退避機(jī)制，當(dāng)多個(gè)設(shè)備同時(shí)接入信道時(shí)會(huì)發(fā)生碰撞，導(dǎo)致時(shí)延進(jìn)一步增加?；跁r(shí)分復(fù)用(TDMA)的MAC協(xié)議經(jīng)歷的時(shí)延可預(yù)測(cè)，設(shè)備在能夠傳輸前必須等待它的周期性時(shí)隙。傳播時(shí)延(tprop)：一旦節(jié)點(diǎn)接入信道，從發(fā)送器到接收器傳輸同步分組SYNC經(jīng)歷的時(shí)間稱為傳播時(shí)延。當(dāng)節(jié)點(diǎn)使用相同的物理介質(zhì)時(shí)，如空氣，傳播時(shí)延非常小可以忽略不計(jì)。然而，在地下、水下等環(huán)境中會(huì)引入較大的時(shí)延，對(duì)時(shí)間同步影響大。接收時(shí)延(trecv)：這是接收方節(jié)點(diǎn)j接收器從傳輸介質(zhì)上接收、解碼同步分組SYNC，并通知操作系統(tǒng)所需要的時(shí)間。接收時(shí)延的重要組件是傳輸時(shí)延ttx，它是完整接收SYNC分組所需要的時(shí)間，trecv的大小取決于SYNC分組的長(zhǎng)度和傳輸速率。

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

9.2.1NTP協(xié)議互聯(lián)網(wǎng)中，NTP協(xié)議用于協(xié)調(diào)每個(gè)主機(jī)時(shí)鐘晶振的頻率，通過(guò)層次化的時(shí)間服務(wù)器結(jié)構(gòu)實(shí)現(xiàn)主機(jī)間的時(shí)鐘同步。在該層次化結(jié)構(gòu)中，根節(jié)點(diǎn)和UTC(世界標(biāo)準(zhǔn)時(shí)間)同步，各層中的時(shí)間服務(wù)器與它們子網(wǎng)中的節(jié)點(diǎn)時(shí)鐘同步。NTP同步的精確度是毫秒級(jí)的，然而，NTP協(xié)議假設(shè)兩臺(tái)主機(jī)之間在兩個(gè)方向上的傳輸時(shí)延是相同的，這種假設(shè)在互聯(lián)網(wǎng)中是合理的。在大規(guī)模網(wǎng)絡(luò)中，盡管NTP協(xié)議能夠提供很好的時(shí)鐘同步，但傳感器網(wǎng)絡(luò)的許多特征使得該協(xié)議不適合。使用NTP協(xié)議協(xié)調(diào)傳感器節(jié)點(diǎn)的時(shí)鐘晶振很有用，但由于傳感器節(jié)點(diǎn)的頻繁故障，使得傳感器節(jié)點(diǎn)與時(shí)間服務(wù)器的連接可能存在問(wèn)題。另外，由于環(huán)境干擾、感知區(qū)域不同部分間的時(shí)延差別較大等的影響，很難要求同步所有傳感器節(jié)點(diǎn)，并且傳感器網(wǎng)絡(luò)由于故障等影響，可能使網(wǎng)絡(luò)斷開(kāi)連接而成為多個(gè)小的感知區(qū)域。9.2.2TPSN協(xié)議TPSN(Timing-syncProtocolforSensorNetworks)協(xié)議類似于NTP協(xié)議，采用層次結(jié)構(gòu)來(lái)實(shí)現(xiàn)整個(gè)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)與時(shí)間服務(wù)器的同步，它要求根節(jié)點(diǎn)同步感知區(qū)域中的所有節(jié)點(diǎn)或一部分節(jié)點(diǎn)。TPSN由兩個(gè)階段組成：層發(fā)現(xiàn)階段、同步階段。1．層發(fā)現(xiàn)階段層發(fā)現(xiàn)階段的目標(biāo)是創(chuàng)建一個(gè)層次化的樹(shù)形網(wǎng)絡(luò)拓?fù)?，拓?fù)渲械拿總€(gè)節(jié)點(diǎn)都被分配在相應(yīng)層上，根節(jié)點(diǎn)(例如配備連接外部世界的GPS網(wǎng)關(guān))位于0層。通過(guò)廣播層發(fā)現(xiàn)消息level_discovery根節(jié)點(diǎn)啟動(dòng)層發(fā)現(xiàn)過(guò)程，該消息中包含發(fā)送者的身份信息和層編號(hào)。根節(jié)點(diǎn)的一跳鄰居使用來(lái)自根節(jié)點(diǎn)的層發(fā)現(xiàn)消息來(lái)確定它自己所在的層次，重新生成并廣播包含自己身份和層編號(hào)的層發(fā)現(xiàn)消息level_discovery，重復(fù)此過(guò)程直到網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)已經(jīng)確定它所在的層為止。2．同步階段同步階段中，沿著層發(fā)現(xiàn)階段建立的層次化樹(shù)結(jié)構(gòu)的邊，TPSN使用成對(duì)同步，即每個(gè)第i層上的節(jié)點(diǎn)用第i-1層上節(jié)點(diǎn)時(shí)鐘同步自己的時(shí)鐘。在t1時(shí)刻節(jié)點(diǎn)j發(fā)布包含節(jié)點(diǎn)層編號(hào)和時(shí)間戳的同步脈沖，在t2時(shí)刻節(jié)點(diǎn)k收到該消息，并在t3時(shí)刻用確認(rèn)消息響應(yīng)，該響應(yīng)消息包含時(shí)間信息t1、t2、t3和節(jié)點(diǎn)k的層編號(hào)。最后，節(jié)點(diǎn)j在t4時(shí)刻收到節(jié)點(diǎn)k發(fā)送的消息。TPSN假定傳播時(shí)延為D，并且在同步期間時(shí)鐘偏移沒(méi)有改變，由于t1和t4是使用節(jié)點(diǎn)j的時(shí)鐘測(cè)量的，t2和t3是使用節(jié)點(diǎn)k的時(shí)鐘測(cè)量的，所以這些時(shí)間滿足下面的關(guān)系：t2?=?t1?+?D?+?offsett4?=?t3?+?D?-?offset基于這些參數(shù)，節(jié)點(diǎn)j可以計(jì)算出時(shí)間偏移offset和傳播時(shí)延D如下：9.2.3RBS協(xié)議RBS(Reference-BroadcastSynchronization)協(xié)議依賴于一組相互需要時(shí)鐘同步的接收節(jié)點(diǎn)之間的廣播消息。在無(wú)線通信環(huán)境中，廣播消息大約在相同時(shí)間到達(dá)發(fā)送節(jié)點(diǎn)通信范圍內(nèi)的多個(gè)接收節(jié)點(diǎn)，同步消息時(shí)延的大小取決于傳播時(shí)延和接收方接收并處理廣播消息所需要的時(shí)間。RBS協(xié)議的優(yōu)勢(shì)在于消除了發(fā)送方引起的非確定性同步誤差，因?yàn)樗械耐椒椒ㄊ腔谀撤N形式的消息交換的，所以消息的不確定性延遲限制了可以獲得的時(shí)間同步粒度。9.2.4LTS協(xié)議LTS(LightweightTree-BasedSynchronization)協(xié)議的主要目標(biāo)是用盡可能少的開(kāi)銷來(lái)提供一個(gè)指定的精度(而不是最大精度)。對(duì)于集中式和分布式多跳同步機(jī)制而言，LTS可以被不同的同步算法使用。為了理解LTS采取的方法，我們首先考慮一對(duì)節(jié)點(diǎn)同步的消息交換。首先，節(jié)點(diǎn)j給節(jié)點(diǎn)k發(fā)送一個(gè)時(shí)間戳為發(fā)送時(shí)間t1的同步消息，根據(jù)該消息到達(dá)節(jié)點(diǎn)k的時(shí)間t2，節(jié)點(diǎn)k的響應(yīng)消息攜帶時(shí)間戳t3以及之前記錄的時(shí)間t1和t2，節(jié)點(diǎn)j在時(shí)刻t4收到該消息。要注意的是，這里的時(shí)間t1和t4是基于節(jié)點(diǎn)j的時(shí)鐘記錄的，而時(shí)間t2和t3則是基于節(jié)點(diǎn)k的時(shí)鐘記錄的。假定傳播時(shí)延為D(進(jìn)一步假設(shè)兩個(gè)方向上的傳播時(shí)延相同)以及節(jié)點(diǎn)j與節(jié)點(diǎn)k之間的未知時(shí)鐘偏移為offset，節(jié)點(diǎn)k的時(shí)鐘讀數(shù)t2如下：類似地，節(jié)點(diǎn)j的時(shí)鐘讀數(shù)t4為可用如下公式計(jì)算時(shí)鐘偏移值：LTS協(xié)議的集中式多跳時(shí)鐘同步版本是基于單個(gè)參考節(jié)點(diǎn)的，該參考節(jié)點(diǎn)是包括網(wǎng)絡(luò)中所有節(jié)點(diǎn)的生成樹(shù)的根節(jié)點(diǎn)。為了最大限度地提高同步精度，樹(shù)的深度應(yīng)盡量最小化，這是因?yàn)槌蓪?duì)同步引起的錯(cuò)誤是遞增的，因此以跳數(shù)為函數(shù)沿著樹(shù)的分支遞增。在LTS中，每次執(zhí)行同步算法時(shí)都要執(zhí)行如廣度優(yōu)先搜索等樹(shù)構(gòu)造算法。一旦樹(shù)建立，參考節(jié)點(diǎn)通過(guò)執(zhí)行與它的每個(gè)孩子節(jié)點(diǎn)的成對(duì)同步過(guò)程啟動(dòng)同步機(jī)制。一旦同步完成，每個(gè)孩子節(jié)點(diǎn)與它自己的子節(jié)點(diǎn)重復(fù)此步驟，直到樹(shù)中所有節(jié)點(diǎn)都實(shí)現(xiàn)同步。9.2.5FTSP協(xié)議FTSP(FloodingTimeSynchronizationProtocol)協(xié)議的目標(biāo)是實(shí)現(xiàn)全網(wǎng)微秒級(jí)誤差的時(shí)鐘同步，F(xiàn)TSP協(xié)議的同步可擴(kuò)展到數(shù)百個(gè)節(jié)點(diǎn)，并且對(duì)包括鏈路和節(jié)點(diǎn)故障等造成的網(wǎng)絡(luò)拓?fù)渥兓哂恤敯粜浴TSP協(xié)議與其他方案的不同之處在于它使用單個(gè)廣播來(lái)建立發(fā)送者和接收者之間的同步點(diǎn)，同時(shí)消除了同步誤差產(chǎn)生的大多數(shù)來(lái)源。在該分析方法中，在時(shí)刻t1傳感器節(jié)點(diǎn)無(wú)線射頻模塊使用中斷信號(hào)通知CPU，它已準(zhǔn)備接收要傳輸下一個(gè)消息塊。中斷處理時(shí)間d1后，在時(shí)刻t2，CPU生成時(shí)間戳，該時(shí)間是無(wú)線射頻模塊編碼和將消息塊轉(zhuǎn)換為電磁波時(shí)需要的，并且把該時(shí)間描述為編碼時(shí)間d1。傳播時(shí)延后的是解碼時(shí)間d4，這是無(wú)線射頻模塊從電磁波解碼消息為二進(jìn)制數(shù)據(jù)的時(shí)間。字節(jié)對(duì)齊時(shí)間t5是由于節(jié)點(diǎn)j和節(jié)點(diǎn)k的不同字節(jié)對(duì)齊引起的時(shí)延。也就是說(shuō)，接受無(wú)線電射頻模塊必須從一個(gè)已知的同步字節(jié)來(lái)判斷偏移量，然后相應(yīng)地對(duì)收到的信息做移位操作。最后，節(jié)點(diǎn)k的無(wú)線射頻模塊在時(shí)刻t6發(fā)出中斷信號(hào)，這允許CPU在時(shí)刻t7獲得最終的時(shí)間戳。1．FTSP時(shí)間戳FTSP中，發(fā)送方使用單個(gè)無(wú)線射頻廣播與一個(gè)或多個(gè)接收方實(shí)現(xiàn)同步，這個(gè)廣播消息包含發(fā)送者的時(shí)間戳。消息抵達(dá)后，接收方從消息中提取時(shí)間戳，并讀取消息到達(dá)的本地時(shí)鐘時(shí)間戳，該全球-本地時(shí)間對(duì)提供了一個(gè)同步點(diǎn)。發(fā)送方的時(shí)間戳必須嵌入當(dāng)前發(fā)送的消息中，因此時(shí)間戳必須由包含時(shí)間戳的字節(jié)在介質(zhì)中傳輸之前生成。FTSP中，同步消息以幾個(gè)前導(dǎo)碼開(kāi)始，其后是幾個(gè)SYNC字節(jié)，數(shù)據(jù)字段和用于錯(cuò)誤檢測(cè)的循環(huán)冗余校驗(yàn)碼。2．多跳同步類似于TPSN，F(xiàn)TSP依賴于一個(gè)選舉出的同步根節(jié)點(diǎn)來(lái)同步整個(gè)網(wǎng)絡(luò)時(shí)鐘，其中根節(jié)點(diǎn)的選舉是基于唯一的節(jié)點(diǎn)編號(hào)IDs的。根節(jié)點(diǎn)保持與全球時(shí)間同步并且網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)保持與根節(jié)點(diǎn)時(shí)鐘同步，并通過(guò)廣播包含自己時(shí)間戳的消息觸發(fā)同步過(guò)程。根節(jié)點(diǎn)通信范圍內(nèi)的所有節(jié)點(diǎn)都可以直接從廣播消息建立同步點(diǎn)，其他節(jié)點(diǎn)從靠近根節(jié)點(diǎn)的已同步節(jié)點(diǎn)的廣播消息中收集同步點(diǎn)信息。9.2.6TDP協(xié)議TDP協(xié)議的目標(biāo)是整個(gè)網(wǎng)絡(luò)在可容忍的范圍內(nèi)維持一個(gè)共同的時(shí)間。而且，可根據(jù)具體的應(yīng)用和網(wǎng)絡(luò)需求調(diào)整可容忍的級(jí)別，這種均衡的網(wǎng)絡(luò)時(shí)間也可以在匯聚節(jié)點(diǎn)使用時(shí)間轉(zhuǎn)換算法轉(zhuǎn)換為全球時(shí)間，提供了到NTP和互聯(lián)網(wǎng)的網(wǎng)關(guān)。為了提供多跳同步，TDP給網(wǎng)絡(luò)中的節(jié)點(diǎn)分配三種不同的職責(zé)，分別如下：主節(jié)點(diǎn)(Masternode)：主節(jié)點(diǎn)初始化同步消息并且建立一個(gè)類似于樹(shù)的結(jié)構(gòu)同步網(wǎng)絡(luò)中的一部分。TDP協(xié)議在網(wǎng)絡(luò)中分配許多主節(jié)點(diǎn)以減少同步的跳數(shù)和最小化收斂時(shí)間。擴(kuò)散領(lǐng)導(dǎo)節(jié)點(diǎn)(Diffusedleaders)：為了沿樹(shù)形結(jié)構(gòu)傳播同步消息，TDP協(xié)議選擇擴(kuò)散領(lǐng)導(dǎo)者節(jié)點(diǎn)，這些節(jié)點(diǎn)進(jìn)一步向主節(jié)點(diǎn)廣播范圍之外傳播同步消息。正常節(jié)點(diǎn)(Regularnodes)：最低限度參與同步處理的除主節(jié)點(diǎn)和擴(kuò)散領(lǐng)導(dǎo)者節(jié)點(diǎn)之外的任意節(jié)點(diǎn)，例如，僅僅根據(jù)接收到的同步消息校正它自己的時(shí)鐘。TDP遵循周期性的過(guò)程，該過(guò)程由主動(dòng)和被動(dòng)兩個(gè)階段組成。隨著被動(dòng)階段持續(xù)時(shí)間的增加，一方面網(wǎng)絡(luò)偏離均衡時(shí)間越大，需要重新同步；另一方面，過(guò)小的被動(dòng)持續(xù)時(shí)間導(dǎo)致需要更加頻繁地同步過(guò)程，增加協(xié)議開(kāi)銷。TDP提供了一種自適應(yīng)的機(jī)制，可根據(jù)傳感器網(wǎng)絡(luò)的定時(shí)需求調(diào)整同步調(diào)度。根據(jù)這種結(jié)構(gòu)，TDP協(xié)議由兩個(gè)主要過(guò)程組成：選擇/重選擇過(guò)程(ERP)，該過(guò)程選擇主節(jié)點(diǎn)和擴(kuò)散領(lǐng)導(dǎo)節(jié)點(diǎn)；時(shí)間擴(kuò)散過(guò)程(TP)，該過(guò)程執(zhí)行時(shí)鐘同步過(guò)程。選擇/重新選擇過(guò)程(ERP)：ERP的目標(biāo)是區(qū)別適合作為主節(jié)點(diǎn)或擴(kuò)散領(lǐng)導(dǎo)節(jié)點(diǎn)的節(jié)點(diǎn)，并且執(zhí)行選擇過(guò)程。錯(cuò)誤時(shí)鐘隔離算法(FIA)：FIA確保阻止有高頻噪聲時(shí)鐘或高的存取時(shí)延波動(dòng)的節(jié)點(diǎn)成為主節(jié)點(diǎn)或擴(kuò)散領(lǐng)導(dǎo)節(jié)點(diǎn)，這種技術(shù)通過(guò)下節(jié)描述的同行評(píng)價(jià)過(guò)程PEP。負(fù)載分布式算法(