第五章(支撐技術(shù)-時(shí)間同步)2014

1、無(wú)線傳感器網(wǎng)絡(luò)講義第五章第五章 支撐技術(shù)支撐技術(shù)時(shí)間同步機(jī)制時(shí)間同步機(jī)制MICA2 mote by Inteland the University of California, Berkeley時(shí)間同步機(jī)制時(shí)間同步機(jī)制5.1 概述5.2 TPSN時(shí)間同步協(xié)議5.1 5.1 概述概述 對(duì)于任何一個(gè)分布式系統(tǒng)來(lái)說(shuō)，時(shí)間同步都是一個(gè)關(guān)鍵的組成部分。傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)會(huì)隨著時(shí)間的進(jìn)行而產(chǎn)生時(shí)鐘漂移傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)會(huì)隨著時(shí)間的進(jìn)行而產(chǎn)生時(shí)鐘漂移，在無(wú)線傳感器網(wǎng)絡(luò)的許多應(yīng)用中，用戶(hù)向無(wú)線傳感器網(wǎng)絡(luò)咨詢(xún)或無(wú)線傳感器網(wǎng)絡(luò)向外部網(wǎng)絡(luò)報(bào)告都需要說(shuō)明事件發(fā)生的時(shí)間。因此，需要一個(gè)共同的時(shí)間以使得網(wǎng)路中的節(jié)點(diǎn)全部或部分

2、在瞬間是同步的全部或部分在瞬間是同步的。例如：傳感器節(jié)點(diǎn)需要彼此之間并行操作和協(xié)作去完成復(fù)雜的傳感任務(wù)。如果在收集信息過(guò)程中，傳感器節(jié)點(diǎn)缺乏統(tǒng)一的時(shí)間戳（即沒(méi)有同步），結(jié)果將是不準(zhǔn)確的。許多節(jié)能方案是利用時(shí)間同步來(lái)實(shí)現(xiàn)的。例如，傳感器可以在適當(dāng)?shù)臅r(shí)候休眠（通過(guò)關(guān)閉傳感器和收發(fā)器進(jìn)入節(jié)能模式），在需要的時(shí)候再喚醒。在應(yīng)用這種節(jié)能模式的時(shí)候，節(jié)點(diǎn)應(yīng)該在相同的時(shí)間進(jìn)行休眠和喚醒。5.1 5.1 概述概述三個(gè)時(shí)間術(shù)語(yǔ)：三個(gè)時(shí)間術(shù)語(yǔ)：物理時(shí)間：用來(lái)表示人類(lèi)社會(huì)使用的絕對(duì)時(shí)間。邏輯時(shí)間：表達(dá)事件發(fā)生的順序關(guān)系，是一個(gè)相對(duì)概念。全局時(shí)間：分布式系統(tǒng)通常需要一個(gè)表示整個(gè)系統(tǒng)的全局時(shí)間，全局時(shí)間根據(jù)需要可以是物

3、理時(shí)間或邏輯時(shí)間。5.1 5.1 概述概述時(shí)間同步技術(shù)中的主要性能指標(biāo)：時(shí)間同步技術(shù)中的主要性能指標(biāo)： 時(shí)間同步技術(shù)的根本目的是為網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時(shí)鐘提供共同的時(shí)間戳?xí)r間同步技術(shù)的根本目的是為網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時(shí)鐘提供共同的時(shí)間戳。對(duì)無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步應(yīng)主要考慮以下幾個(gè)方面的問(wèn)題：(1)能量效率能量效率。同步所需的時(shí)間越長(zhǎng)，消耗的能量越多，效率就越低。設(shè)計(jì)WSN的時(shí)間同步算法需以考慮傳感器節(jié)點(diǎn)有效的能量資源為前提。(2)可擴(kuò)展性和健壯性可擴(kuò)展性和健壯性。時(shí)間同步機(jī)制應(yīng)該支持網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目或者密度的有效擴(kuò)展，并保障一旦有節(jié)點(diǎn)失效時(shí)，余下網(wǎng)絡(luò)有效且功能健全。(3)精確度精確度。針對(duì)不同的應(yīng)用

4、和目的，精確度的需求有所不用。(4)同步期限（壽命）同步期限（壽命）。同步算法提供的同步時(shí)間可以是瞬時(shí)的，也可以和網(wǎng)絡(luò)的壽命一樣長(zhǎng)。(5)有效范圍有效范圍?？梢越o網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)提供時(shí)間（全局同步），也可以給局部區(qū)域的節(jié)點(diǎn)提供時(shí)間（局部同步）。(6)成本和尺寸成本和尺寸。傳感器網(wǎng)絡(luò)時(shí)間同步方案必須考慮節(jié)點(diǎn)有限的尺寸和成本，在節(jié)點(diǎn)上安裝較大或昂貴的硬件（例如GPS）是不合適的。5.1 5.1 概述概述同步過(guò)程中的主要影響因素： 在傳感器網(wǎng)絡(luò)中，報(bào)文傳輸延遲的不確定性報(bào)文傳輸延遲的不確定性對(duì)于同步的精度、誤差的估計(jì)會(huì)造成很大的影響。一方面來(lái)看，傳輸延遲的數(shù)量級(jí)遠(yuǎn)大于同步精度，因此不可忽略；另一方面，

5、它又極易受到偶然因素（如：處理器負(fù)載、信道擁塞等）的影響，具有高度的不確定性，導(dǎo)致難于估計(jì)。因此對(duì)傳輸延遲的測(cè)量、分析和補(bǔ)償成為了WSN時(shí)鐘同步的難點(diǎn)。相關(guān)研究把傳輸延遲分為六個(gè)部分，如下圖所示。5.1 5.1 概述概述發(fā)送時(shí)間(Send time)：發(fā)送方產(chǎn)生同步報(bào)文并轉(zhuǎn)交給MAC層的時(shí)間，與處理器負(fù)載和系統(tǒng)調(diào)用時(shí)間有關(guān)。訪問(wèn)時(shí)間訪問(wèn)時(shí)間(Access time)：指同步報(bào)文在MAC層排隊(duì)等待發(fā)送的時(shí)間，取決于無(wú)線信道的負(fù)載，隨機(jī)性很大，是最不確定性因素。傳送時(shí)間(Transmission time)：發(fā)送方傳輸同步報(bào)文的時(shí)間?？梢杂砂l(fā)送速率和報(bào)文長(zhǎng)度計(jì)算出來(lái)。傳播時(shí)間(Propagatio

6、n time)：發(fā)送方到接收方的電磁波傳播時(shí)間。在小范圍內(nèi)，可以認(rèn)為節(jié)點(diǎn)的廣播報(bào)文到達(dá)其他節(jié)點(diǎn)的傳播時(shí)間是相同的。接收時(shí)間(Reception time)：接收方接收同步報(bào)文的時(shí)間，可以認(rèn)為它和傳送時(shí)間完全對(duì)稱(chēng)。接受時(shí)間(Receive time)：接收方處理同步報(bào)文的時(shí)間，與發(fā)送時(shí)間類(lèi)似。注注：有的資料將報(bào)文延遲分為四個(gè)部分：發(fā)送時(shí)間（1）、訪問(wèn)時(shí)間（2）、傳輸時(shí)間（3、4）和接收時(shí)間（5、6）。5.1 5.1 概述概述無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步算法：無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步算法：時(shí)間同步算法分類(lèi)方法很多，按照一對(duì)節(jié)點(diǎn)的同步方式可以分為3類(lèi)：基于接受者基于接受者- -接受者（接受者（recei

7、verreceiverreceiverreceiver）的同步算法）的同步算法。這種算法的典型代表是參考廣播時(shí)間同步協(xié)議RBS（Reference Broadcast Synchronization）?；诔蓪?duì)（基于成對(duì)（pair-wisepair-wise）的雙向同步算法）的雙向同步算法。代表的協(xié)議有：TPSN（Timing-sync Protocol for SensorNetworks）、TS/MS（Tiny-Sync and Mini-Sync）、LTS（Lightweight Time Synchronization）等?；诎l(fā)送者基于發(fā)送者- -接受者（接受者（sender-rec

8、eiversender-receiver）的單向）的單向(one(oneway)way)同步算法同步算法。目前，基于該方法的典型代表是：延遲測(cè)量時(shí)間同步協(xié)議DMTS(Delay Measurement Time Synchronization)和洪泛時(shí)間同步協(xié)議FTSP(Flooding Time synchronization Protocol)。5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議思想?yún)f(xié)議思想TPSN （ Timing-sync Protocol for Sensor Networks ）是類(lèi)似于NTP（Network Time Protocol）的

9、傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議。目的是提供傳感器網(wǎng)絡(luò)全網(wǎng)范圍全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步。節(jié)點(diǎn)結(jié)構(gòu)中包含一個(gè)根節(jié)點(diǎn)根節(jié)點(diǎn)，它與外界通信獲取外界時(shí)間，以此作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)鐘源。將節(jié)點(diǎn)分級(jí)分級(jí)后（根節(jié)點(diǎn)是0級(jí)，累加），每個(gè)節(jié)點(diǎn)同上一級(jí)的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終與根節(jié)點(diǎn)同步。節(jié)點(diǎn)對(duì)之間的同步采用發(fā)送者-接收者同步機(jī)制（RBS）。5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議過(guò)程協(xié)議過(guò)程協(xié)議假設(shè)：協(xié)議假設(shè)：每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識(shí)號(hào)ID。節(jié)點(diǎn)間的無(wú)線通信鏈路是雙向的，通過(guò)雙向消息交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。整個(gè)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)按層次結(jié)構(gòu)管理，由TPSN協(xié)議生成和維護(hù)。5.2

10、TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議過(guò)程：協(xié)議過(guò)程：第一階段第一階段 層次發(fā)現(xiàn)階段（層次發(fā)現(xiàn)階段（Level Discovery Phase）目的：生成節(jié)點(diǎn)層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)被賦予一個(gè)級(jí)別，根節(jié)點(diǎn)為0級(jí)，第i級(jí)的節(jié)點(diǎn)至少能夠與一個(gè)第（i-1）級(jí)的節(jié)點(diǎn)通信。網(wǎng)絡(luò)部署后，由根節(jié)點(diǎn)廣播級(jí)別發(fā)現(xiàn)分組（level_discovery packet）來(lái)啟動(dòng)層次發(fā)現(xiàn)階段，級(jí)別發(fā)現(xiàn)分組包含節(jié)點(diǎn)的ID和級(jí)別。鄰居節(jié)點(diǎn)收到分組后，將自己的級(jí)別設(shè)置為分組中的級(jí)別加1，然后廣播新的級(jí)別發(fā)現(xiàn)分組。節(jié)點(diǎn)收到第i級(jí)節(jié)點(diǎn)的廣播分組后，記錄發(fā)送這個(gè)廣播分組的節(jié)點(diǎn)ID，設(shè)置自己的級(jí)別為（i+1），

11、廣播級(jí)別為（i+1）的分組，這個(gè)過(guò)程持續(xù)到網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)都被賦予一個(gè)級(jí)別。節(jié)點(diǎn)一旦建立自己的級(jí)別，就忽略任何其他級(jí)別發(fā)現(xiàn)分組，防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞。5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議層次發(fā)現(xiàn)階段（廣播級(jí)別發(fā)現(xiàn)分組）層次發(fā)現(xiàn)階段（廣播級(jí)別發(fā)現(xiàn)分組）根根節(jié)節(jié)點(diǎn)點(diǎn)11212122222說(shuō)明：區(qū)域內(nèi)最先探測(cè)到目標(biāo)的節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果有多個(gè)節(jié)點(diǎn)同時(shí)探測(cè)到目標(biāo)，則隨機(jī)地選取一個(gè)，也可以在配置時(shí)就地隨機(jī)地選擇一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)（根節(jié)點(diǎn)的層號(hào)為0），最終形成分層次的拓?fù)浣Y(jié)構(gòu)。 5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議過(guò)程：協(xié)議過(guò)程：第二階段第二階段

12、同步階段（同步階段（Synchronization PhaseSynchronization Phase） 目的：實(shí)現(xiàn)所有樹(shù)節(jié)點(diǎn)的時(shí)間同步，第1級(jí)節(jié)點(diǎn)同步到根節(jié)點(diǎn)，第i級(jí)的節(jié)點(diǎn)同步到第（i-1）級(jí)的一個(gè)節(jié)點(diǎn)，最終所有節(jié)點(diǎn)同步到根節(jié)點(diǎn)，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步。層次結(jié)構(gòu)建立以后，根節(jié)點(diǎn)通過(guò)廣播時(shí)間同步分組（time_sync packet）啟動(dòng)同步階段。第1級(jí)節(jié)點(diǎn)收到分組后，各自分別等待一段隨機(jī)時(shí)間，再通過(guò)與根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)。第2級(jí)節(jié)點(diǎn)偵聽(tīng)到第1級(jí)節(jié)點(diǎn)的交換消息后，后退和等待一段隨機(jī)時(shí)間，再與它記錄的上一級(jí)別的節(jié)點(diǎn)交換消息進(jìn)行同步，網(wǎng)絡(luò)中的節(jié)點(diǎn)依次與上一級(jí)節(jié)點(diǎn)同步，最終都同步到根節(jié)點(diǎn)。等

13、待一段隨機(jī)時(shí)間是為了保證該級(jí)節(jié)點(diǎn)在上一級(jí)節(jié)點(diǎn)同步完成后才啟動(dòng)消息交換。5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議同步階段（廣播時(shí)間同步分組）同步階段（廣播時(shí)間同步分組）根根節(jié)節(jié)點(diǎn)點(diǎn)11212122222說(shuō)明：在同步建立后，如果有新的節(jié)點(diǎn)加入時(shí)，首先等待給自己分配一個(gè)層次號(hào)，并啟動(dòng)等待定時(shí)器。如果在限定的時(shí)間內(nèi)沒(méi)有給自己分配一個(gè)層號(hào)，就發(fā)出一個(gè)層次加入請(qǐng)求信息，相鄰節(jié)點(diǎn)接收到這個(gè)請(qǐng)求后就將自己所屬的層號(hào)發(fā)送給這個(gè)節(jié)點(diǎn)。新加入節(jié)點(diǎn)將這個(gè)層號(hào)加1后作為自己的層號(hào)。 5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議 如下圖所示：其中節(jié)點(diǎn)S屬于第i級(jí)節(jié)點(diǎn)，節(jié)點(diǎn)R屬于第(i-1)級(jí)節(jié)

14、點(diǎn)，T T1 1和T T4 4表示節(jié)點(diǎn)S本地時(shí)鐘在不同時(shí)刻測(cè)量的時(shí)間，T T2 2和T T3 3表示節(jié)點(diǎn)R本地時(shí)鐘在不同時(shí)刻測(cè)量的時(shí)間，表示兩個(gè)節(jié)點(diǎn)之間的時(shí)間偏差，d d表示消息的傳播時(shí)延，假設(shè)來(lái)回消息的延遲是相同的。節(jié)點(diǎn)S在T1時(shí)間發(fā)送同步請(qǐng)求分組給節(jié)點(diǎn)R，分組中包含分組中包含S S的級(jí)別和的級(jí)別和T T1 1時(shí)間時(shí)間，節(jié)點(diǎn)R在T2時(shí)間收到分組，T2=(T1+d+)，然后在T3時(shí)間發(fā)送應(yīng)答分組給節(jié)點(diǎn)S，分組中包含節(jié)點(diǎn)分組中包含節(jié)點(diǎn)R R的級(jí)別和的級(jí)別和T T1 1、T T2 2和和T T3 3信信息息，節(jié)點(diǎn)S在T4時(shí)間收到應(yīng)答，T4=(T3+d-)，因此可以推出： 節(jié)點(diǎn)S在計(jì)算時(shí)間偏差后計(jì)算

15、時(shí)間偏差后，將它的時(shí)間同步到節(jié)點(diǎn)R。5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議過(guò)程：協(xié)議過(guò)程：相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制i-1級(jí)級(jí)i級(jí)級(jí)消息傳播消息傳播時(shí)延時(shí)延兩節(jié)點(diǎn)間的兩節(jié)點(diǎn)間的時(shí)間偏差時(shí)間偏差5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議過(guò)程：協(xié)議過(guò)程：相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制結(jié)論結(jié)論5.2 TPSN5.2 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSNTPSN協(xié)議特點(diǎn)協(xié)議特點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)1.減少了同步誤差 在發(fā)送時(shí)間、訪問(wèn)時(shí)間、傳輸時(shí)間和接收時(shí)間四個(gè)消息延遲組成部分中，訪問(wèn)時(shí)間往往是無(wú)線傳輸消息時(shí)延中最不確定的因素。為了提高兩個(gè)節(jié)點(diǎn)間的時(shí)間同步精度，TPSNTPSN同步協(xié)議在同步協(xié)議在MACMAC層消息開(kāi)始發(fā)送到無(wú)線信道時(shí)才給消息層消息開(kāi)始發(fā)送到無(wú)線信道時(shí)才給消息添加時(shí)標(biāo)添加時(shí)標(biāo)，消除了訪問(wèn)時(shí)間帶來(lái)的時(shí)間同步誤差。2.提高了同步精度 考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息交換計(jì)算消息的平均延遲，提高了時(shí)間同步的精度（可