【正文】 計(jì) 算出的誤差大于以前數(shù)據(jù)點(diǎn)計(jì)算出的誤差，則拋棄新的數(shù)據(jù)點(diǎn)，否則就采用新的數(shù)據(jù)點(diǎn)， 而拋棄舊的數(shù)據(jù)點(diǎn)。這樣時間同步總共只需要存儲三到四個數(shù)據(jù)點(diǎn)，就可以實(shí)現(xiàn)一定精度 的時間同步。圖 探測消息的數(shù)據(jù)點(diǎn)關(guān)系 DMTS時間同步機(jī)制延遲測量時間同步機(jī)制 （DMTS: Delay measurement time Synchronization) 倒是基于同步消息在傳輸路徑上所有延遲的估計(jì)，來達(dá)到節(jié)點(diǎn)間的時間同步。由于在 RBS 機(jī)制中 需要交換的同步消息個數(shù)多，消耗很多的能量，并且使得時間同步的收斂的速度變慢，所 以希望有更為高效的時間同步機(jī)制，避免往返消息的 RRT 估計(jì)，并減少交換消息的個數(shù)， 還希望能兼顧擴(kuò)展性，能量消耗和計(jì)算代價等因素。DMTS 機(jī)制選擇一個節(jié)點(diǎn)作為時間主節(jié)點(diǎn)（leader ）廣播同步時間。所有接收到廣播的 節(jié)點(diǎn)測量這個廣播消息的延遲，設(shè)置它的時間為接收到分組攜帶的時間加上這個廣播分組 的傳輸延遲，這樣所有接收到廣播分組的節(jié)點(diǎn)都與主節(jié)點(diǎn)進(jìn)行同步。DMTS 時間同步的精度 主要是有延遲測量的精度來決定，并且沒有復(fù)雜的運(yùn)算和操作過程，是一種輕量級（lightweight) 能量有效的時間同步機(jī)制。DMTS 的時間廣播傳輸過程如下：，給廣播分組加上時間戳to (MAC 層)。2. 主節(jié)點(diǎn)發(fā)送前導(dǎo)碼和起始字符，以便接收點(diǎn)進(jìn)行接收同步，并且估計(jì)前導(dǎo)碼和起始 字符的發(fā)送時間 nt。，并且調(diào)整自己的時間之前時刻再 記錄時間t2 ，接收端的接收處理延遲就是（t2t1）+ nt + (t2t1)。圖 3. 7 OMTS 時間同步機(jī)制中廣播分組延遲的測量OMTS協(xié)議在多跳網(wǎng)絡(luò)中采用了層次型分級結(jié)構(gòu)來實(shí)現(xiàn)全網(wǎng)范圍內(nèi)的時間同步，這和TPSN 算法有些類似。在該協(xié)議中定義了時間源級別的概念，也就是其它節(jié)點(diǎn)和主節(jié)點(diǎn)之間的距離(跳數(shù))。主節(jié)點(diǎn)的時間級別是 0，主節(jié)點(diǎn)廣播范圍內(nèi)的鄰節(jié)點(diǎn)的時間級別為1，時 間級別為 1 的節(jié)點(diǎn)廣播范圍內(nèi)的鄰節(jié)點(diǎn)時間級別為2，以此類推。為了避免冗余分組的傳輸，采用的方法是只接收級別比自己低的節(jié)點(diǎn)廣播的分組。在傳感器網(wǎng)絡(luò)中，往往需要傳感器節(jié)點(diǎn)與外部時間進(jìn)行同步，這就要求時間主節(jié)點(diǎn)能夠與外部網(wǎng)絡(luò)通信，從而獲得世界標(biāo)準(zhǔn)時間值。通常選擇基站作為默認(rèn)的時間主節(jié)點(diǎn)，因?yàn)樗軌颢@得更好的能源支持，并且便于與外部網(wǎng)絡(luò)相連和通信。時間主節(jié)點(diǎn)選取可以采 用節(jié)點(diǎn) ID 最小的策略。 FTSP 時間同步機(jī)制泛洪時間同步協(xié)議 (FTSP: Flooding Time Synchronization Protocol) [剖時間同步 機(jī)制由 Vanderbilt 大學(xué) Branislav Kusy等提出的，綜合考慮了能量感知、可擴(kuò)展性、魯棒性、穩(wěn)定性和收斂性等方面的要求。問FTSP 算法也是使用單個廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時間同步，采用同步時間數(shù)據(jù)的線性回歸方法估計(jì)時鐘漂移和偏差。多跳網(wǎng)絡(luò)的問FTSP機(jī)制采用層次結(jié)構(gòu)，根節(jié)點(diǎn)就是選中的同步源。根節(jié)點(diǎn)屬于級別 0， 根節(jié)點(diǎn)通過廣播選出級別 l的節(jié)點(diǎn)，以此推廣到全網(wǎng)，級別 i 的節(jié)點(diǎn)同步到級別 (il) 的節(jié)點(diǎn)。所有節(jié)點(diǎn)周期性廣播時間同步消息維持時間同步層次結(jié)構(gòu)，1 級節(jié)點(diǎn)在收到根節(jié) 點(diǎn)的廣播消息后同步到根節(jié)點(diǎn)，同樣，2 級節(jié)點(diǎn)在收到 1 級節(jié)點(diǎn)的廣播消息后同步到 1 級發(fā)送節(jié)點(diǎn)，以此推廣到全網(wǎng)，所有的節(jié)點(diǎn)都能獲得時間同步。FTSP 算法實(shí)現(xiàn)步驟如下：(1) FTSP 算法在完成 SYNC 字節(jié)發(fā)射后給時間同步消息標(biāo)記時間戳并發(fā)射出去 (SYNC 字節(jié)類似 DMTS 算法中的起始符)。消息數(shù)據(jù)部分的發(fā)射時間可通過數(shù)據(jù)長度和發(fā)射速率得 出。(2) 接收節(jié)點(diǎn)記錄 SYNC 字節(jié)最后到達(dá)時間，并計(jì)算位偏移 (bit offset)。在收到完整消息后，接收節(jié)點(diǎn)計(jì)算位偏移產(chǎn)生的時間延遲，這通過偏移位數(shù)與接收速率得出。(3) 接收節(jié)點(diǎn)計(jì)算與發(fā)送節(jié)點(diǎn)間的時鐘偏移量，然后調(diào)整本地時鐘和發(fā)送節(jié)點(diǎn)時間同 步。FTSP 算法對時鐘漂移和偏差進(jìn)行了線性回歸分析，F(xiàn)TSP 算法考慮到在特定時間范圍 內(nèi)節(jié)點(diǎn)時鐘晶振頻率是穩(wěn)定的，因此節(jié)點(diǎn)問時鐘偏移量與時間成線性關(guān)系:通過發(fā)送節(jié)點(diǎn) 周期性廣播時間同步消息，接收節(jié)點(diǎn)取得多個數(shù)據(jù)對 (time. offset). 并構(gòu)造最佳擬合直線 L(time)。通過回歸直線 L，在誤差允許的時間間隔內(nèi)，節(jié)點(diǎn)可直接通過 L 計(jì)算某一時 間點(diǎn)節(jié)點(diǎn)間的時鐘偏移量而不必發(fā)送時間同步消息進(jìn)行計(jì)算，從而減少了消息的發(fā)送次數(shù)。FTSP 機(jī)制還考慮了根節(jié)點(diǎn)的選擇、根節(jié)點(diǎn)和子節(jié)點(diǎn)的失效所造成的拓?fù)浣Y(jié)構(gòu)的變化以及冗余信息的處理等方面問題。節(jié)點(diǎn)通過一段時間的偵聽和等待，進(jìn)入時間同步的初始化階段，如果收到了同步消息，則節(jié)點(diǎn)用新的時間數(shù)據(jù)更新線性回歸表，如果沒有收到消息，該節(jié)點(diǎn)就宣布自己是根節(jié)點(diǎn)。但是這樣可能會造成多個節(jié)點(diǎn)同步宣布自己為根節(jié)點(diǎn)的情況，所以FTSP 機(jī)制中選擇 ID 編號最小的節(jié)點(diǎn)作為根節(jié)點(diǎn)。如果新的全局時間和舊的全局 時間存在較大的偏差，跟節(jié)點(diǎn)切換就存在收斂問題，這就需要潛在的新根節(jié)點(diǎn)收集足夠多的數(shù)據(jù)來精確估計(jì)全局時間。對于冗余消息的消除，F(xiàn)TSP 機(jī)制采用根節(jié)點(diǎn)逐個增大消息的序列號，其他節(jié)點(diǎn)只記錄 收到消息的最大序列號，并用這個序列號發(fā)送自己的消息。例如:假設(shè)節(jié)點(diǎn) N 有 7 鄰居節(jié) 點(diǎn)，這 7 個鄰居節(jié)點(diǎn)之間能夠相互通信，并且都在根節(jié)點(diǎn)的通信范圍之內(nèi)，但是 N 節(jié)點(diǎn)不 在根節(jié)點(diǎn)的通信范圍之內(nèi)。這樣。根節(jié)點(diǎn)發(fā)送的消息就到達(dá)不了 N，但是 N 能收到 7個相 鄰節(jié)點(diǎn)發(fā)送的消息，如果 N 節(jié)點(diǎn)把 7 個節(jié)點(diǎn)發(fā)送的同步消息全部都接收的話，就很多余， 所以節(jié)點(diǎn) N 在收到一個節(jié)點(diǎn)發(fā)送的消息之后，記下該消息的最大序列號，并且把數(shù)據(jù)放到 回歸表中，放棄其他六個節(jié)點(diǎn)的相同序列號的同步消息。 典型時間同步算法分析無線傳感器網(wǎng)絡(luò)時間同步機(jī)制的分析將會從開銷對比、精度對比和協(xié)議復(fù)雜度上綜合 對比上面所述的三類時間同步機(jī)制的典型算法。在無線傳感器網(wǎng)絡(luò)的時間同步協(xié)議中，消 息傳輸延遲的計(jì)算精度決定了時間同步的精度。消息傳輸?shù)臄?shù)量在一定程度上決定了時間 同步的復(fù)雜度和開銷。 時間同步消息傳輸延遲的分解為了對時間同步誤差進(jìn)行詳細(xì)的分析，Kopetz 和 Schwabl 把消息傳輸延遲分為四個部分，但是根據(jù)消息傳輸?shù)倪^程，在從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)之間的關(guān)鍵路徑上，又可以把兩個傳感器節(jié)點(diǎn)之間的消息傳輸延遲進(jìn)一步細(xì)分為六個部分，如圖 所示。把初始化消息分組的節(jié)點(diǎn)稱為發(fā)送者，對這個消息做出回應(yīng)的節(jié)點(diǎn)稱為接收者。圖 消息傳輸延遲分解(1)發(fā)送時間：在應(yīng)用層上構(gòu)造分組并把分組傳遞到 MAC 層的時間，包括時間同步 應(yīng)用程序的系統(tǒng)調(diào)用時間、操作系統(tǒng)的上下文切換和內(nèi)核協(xié)議處理時間以及把消息從主機(jī) 發(fā)送到網(wǎng)絡(luò)接口的時間。發(fā)送時間是非確定性的因素，最大的可達(dá)幾百毫秒。(2)訪問時間:在分組到達(dá) MAC層之后，分組等待網(wǎng)絡(luò)傳輸信道空閑的時間。這與 底層的 MAC 協(xié)議密切相關(guān)，在基于競爭的 MAC 協(xié)議中，發(fā)送節(jié)點(diǎn)必須得到信道空閑后才能 傳輸數(shù)據(jù)，發(fā)送過程中產(chǎn)生沖突需要重傳。訪問延遲是分組傳輸延遲中最關(guān)鍵的因素，它根據(jù)當(dāng)前的網(wǎng)絡(luò)流通情況在毫秒和秒之間變化。(3) 傳輸時間：在物理層上傳輸分組的時間，其中還包括了對分組的編碼和把分組 轉(zhuǎn)換成電磁波形式的時間。傳輸時間主要依賴與分組的長度和無線電波的速度。(4) 傳播時間：一旦分組離開發(fā)送端之后，從發(fā)送端到接收端無線傳輸?shù)臅r間，這個時間依賴與節(jié)點(diǎn)之間的距離，它在 300m 范圍之內(nèi)都是小于一個微秒的。(5) 接收時間：接收端將分組按照比特方式進(jìn)行接收，并且把分組傳到 MAC 層的時 間，其中還包括把接收到的電磁波轉(zhuǎn)換并譯碼成二進(jìn)制數(shù)據(jù)的時間。從圖 可以看出， 接收時間和傳輸時間是有重疊的。(6) 接收處理時間:把接收到的比特還原成發(fā)送者發(fā)送的分組，然后把分組傳送到 應(yīng)用層的時間。接收處理時間會隨著操作系統(tǒng)所引入的各種各樣的延遲而改變。 典型時間同步算法分析RBS 算法分析：RBS 算法是基于接收者和接收者的時間同步機(jī)制的代表，該算法不是同步發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)，也不是廣播發(fā)送節(jié)點(diǎn)的時間值，而是通過廣播同步分組實(shí)現(xiàn)接收節(jié)點(diǎn)間的相對時間同步。由于無線信道的廣播特性，參考分組相對于所有接收節(jié)點(diǎn)來說同時發(fā)送到物理 信道上，所以RBS 算法能夠去除發(fā)送時間和訪問時間引入的誤差，由于是同一個參考分組，所以影響 RBS 算法同步精度的因素主要有無線傳播時間、接收處理時間和待同步的兩個節(jié) 點(diǎn)之間的相對時間漂移。在消息的開銷方面，如果有兩個接收節(jié)點(diǎn)，RBS 時間同步機(jī)制需要4 個接收消息和 3個發(fā)送消息。如果考慮到實(shí)際的網(wǎng)絡(luò)中發(fā)送節(jié)點(diǎn)往往也需要同步，則需要利用另一個節(jié)點(diǎn)，通過讓另外一個節(jié)點(diǎn)成為發(fā)送節(jié)點(diǎn)來實(shí)現(xiàn)。TPSN 算法分析：TPSN 算法是基于發(fā)送者和接收者的雙向時間同步機(jī)制的代表，相鄰節(jié)點(diǎn)之間的單跳同步是通過交換兩個消息實(shí)現(xiàn)的，這種雙向通信，可以把同步信息時延的影響降低 50 %。由于在發(fā)送時間、訪問時間、傳播時間和接收時間四個消息延遲組成部分中，訪問時 間往往是無線傳輸消息時延中最不確定的因素，為了提高兩個節(jié)點(diǎn)間的時間同步精度， TPSN 協(xié)議在 MAC 層消息開始發(fā)送到無線信道的時刻，才給同步消息加上時標(biāo)，消除了訪問 時間到來的時間同步誤差。與 RBS 機(jī)制相比，TPSN 協(xié)議考慮了傳播時間和接收時間，利用雙向消息交換計(jì)算消息的平均時延，提高了時間同步的精度。TPSN 協(xié)議的提出者在 Mica 平臺上實(shí)現(xiàn)了 TPSN 和 RBS 兩種機(jī)制，對于一堆時鐘為4HMz的 Mica 節(jié)點(diǎn)，TPSN 時間同步平均誤差是 ，而 RBS 是 29. 13us 。如果考慮生成層次結(jié)構(gòu)的消息開銷，一個節(jié)點(diǎn)的 時間同步需要傳遞3個消息，協(xié)議開銷比較大。TPSN 協(xié)議能夠?qū)崿F(xiàn)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時間同步，同步誤差與跳數(shù)成正比增長。它一般用來實(shí)現(xiàn)短期間的全網(wǎng)節(jié)點(diǎn)時間同步，如果需要長時間的全網(wǎng)節(jié)點(diǎn)時間同步，則需要周期性的執(zhí)行TPSN 協(xié)議進(jìn)行重同步，兩次時間同步的時間間隔根據(jù)具體的應(yīng)用確定。另外， TPSN協(xié)議可以與后同步策略結(jié)合使用。TPSN協(xié)議的一個顯著不足是沒有考慮根節(jié)點(diǎn)的失效問題。TPSN 雖然提高了精度，但由于了雙向消息交換計(jì)算消息的平均延遲，增加了消息交換，實(shí)質(zhì)上是用增加消息交換為代價換來更高的精度。為減少時間同步的消息交換開銷，節(jié)約節(jié)點(diǎn)能量，本論文將在 TPSN 算法的基礎(chǔ)上進(jìn)行了改進(jìn)，在基于 TPSN 算法雙向成對同步機(jī) 制上使用廣播同步機(jī)制，有效利用網(wǎng)絡(luò)中節(jié)點(diǎn)的廣播信息，使網(wǎng)絡(luò)中節(jié)點(diǎn)廣播域內(nèi)只有一個下層節(jié)點(diǎn)與之進(jìn)行雙向成對同步，從而達(dá)到了減少消息開銷和節(jié)約能量的目的，使算法 能適用于一些對能耗要求高的應(yīng)用。Minisync 和 Tinysync算法分析 這兩個算法是輕量級的時間同步算法，通過交換少量消息能夠提供具有確定誤差上界的頻偏和相偏估計(jì)，同時僅僅需要非常有限的網(wǎng)絡(luò)通信帶寬、存儲容量和處理能力等資源，這正是傳感器網(wǎng)絡(luò)最需要的特征。這兩個算法的前提假設(shè)是節(jié)點(diǎn)的時間是“真實(shí)時間”的線性變化，它的時鐘頻偏和相偏是不變的，對于需要長期監(jiān)測的傳感器網(wǎng)絡(luò)應(yīng)用，傳感器節(jié)點(diǎn)低成本的晶體振蕩器很難保證時鐘頻偏和相偏的長時間穩(wěn)定性。DMTS算法分析DMTS 算法是基于發(fā)送者和接收者的單向時間同步機(jī)制的代表算法。該算法是把父節(jié)點(diǎn)的時間廣播出去，讓父節(jié)點(diǎn)廣播范圍內(nèi)的子節(jié)點(diǎn)根據(jù)分組中包含的時間和傳輸延遲時間來調(diào)整自身節(jié)點(diǎn)的時間。DMTS 算法是在檢測到信道空閑時給廣播分組加上時間戳，這樣就消 除了發(fā)送端的處理延遲和 MAC 層的訪問延遲，傳輸前導(dǎo)碼和起始字符的時間可以根據(jù)它們 的長度計(jì)算得出，接受處理時間可以根據(jù)接收端打的兩個時標(biāo)計(jì)算，故 DMTS算法受到無 線傳播時間、父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的相對時間漂移以及打時標(biāo)過程的影響。對于傳播時間的影響，由于無線電波的傳播速度是 300 米/微秒，而 WSN 中無線器件的覆蓋范圍非常小，最多不會超過 100 米，所以傳播時間通常是在微秒范圍之內(nèi)，它對誤 差的影響就可以忽略不計(jì)。DMTS 也是一種輕量的時間同步機(jī)制，并且能量高效，能夠?qū)崿F(xiàn)全網(wǎng)節(jié)點(diǎn)的時間同步。 與 RBS 時間同步機(jī)制相比，DMTS 機(jī)制的計(jì)算開銷要小很多，需要傳輸?shù)南⑸?，但是同步精度較低。有一點(diǎn)值得重視的是，DMTS 機(jī)制能夠與外部時間標(biāo)準(zhǔn)時間進(jìn)行同步，但它的同 步精度相對較低。DMTS 機(jī)制在實(shí)現(xiàn)復(fù)雜度、能量高效、同步精度三者之間進(jìn)行了折中，能夠很好的適用于對同步精度要求不高的傳感器網(wǎng)絡(luò)。FTSP 算法分析FTSP 時間同步機(jī)制將消息傳輸延遲進(jìn)一步分解為發(fā)送中斷時延、編碼時延、傳播時延、 解碼時延、字節(jié)對齊時延、接收中斷處理時延，每一步都仔細(xì)考慮和細(xì)化，以提高同步的 精度。FTSP 時間同步機(jī)制對與節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入、拓?fù)渥兓惹闆r也進(jìn)行了優(yōu)化，增強(qiáng)機(jī)制的強(qiáng)健性，適合于軍事等惡劣情況的應(yīng)用。因此 FTSP 機(jī)制采用的時間數(shù)據(jù)的線性 回歸方法估計(jì)時鐘漂移和偏差等一系列處理方法，無疑增大了同步機(jī)制的復(fù)雜性。在精度方面，基于接收者和接收者的時間同步機(jī)制排除了發(fā)送端對同步精度的影響，具有較高的同步精度?；诎l(fā)送者和接收者的雙向時間同步機(jī)制，如果采用在 MAC層消息開始發(fā)送到無線信道的時刻打時標(biāo)的方法，也能帶來很高的同步精度。從表 中可以看 出，在相同的硬件平臺上，TPSN 協(xié)議的同步精度比 RBS 協(xié)議高。DMTS 協(xié)議是犧牲精度來 換取能量節(jié)約的，所以適合使用在精度要求不太高的場合，而FTSP 協(xié)議由于增加了對位偏移產(chǎn)生的時間延遲的估計(jì)，因而具有比 DMTS 算法更高的同步精度。有關(guān)協(xié)議復(fù)雜度方面，基于發(fā)送者和接收者的單向時間同步機(jī)制利用根節(jié)點(diǎn)的廣播信息實(shí)現(xiàn)同步，子節(jié)點(diǎn)之間、子節(jié)點(diǎn)和根節(jié)點(diǎn)之間不進(jìn)行任何交互，所以 DMTS 協(xié)議的復(fù)雜度比較低，但是由于FTSP 協(xié)議中利用線性回歸的方法擬合回歸曲線，這就增加了該協(xié)議的復(fù)雜度:基于發(fā)送者和接收者的雙向時間同步機(jī)制子節(jié)點(diǎn)和根節(jié)點(diǎn)之間必須進(jìn)行交互以 取得同步，它們通過兩次消息交換才能實(shí)現(xiàn)時間