無線傳感網(wǎng) -第7章 同步技術(shù)

1、第第7章章 同步技術(shù)同步技術(shù)n7.1 時(shí)間同步的意義和特點(diǎn)時(shí)間同步的意義和特點(diǎn)n7.2 RBS同步機(jī)制同步機(jī)制n7.3 Tiny-sync/mini-sync同步機(jī)制同步機(jī)制n7.4 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議n7.5 時(shí)間同步的應(yīng)用示例時(shí)間同步的應(yīng)用示例n7.6 本章小結(jié)本章小結(jié)7.1 時(shí)間同步的意義和特點(diǎn)時(shí)間同步的意義和特點(diǎn)n7.1.1 傳感網(wǎng)時(shí)間同步的意義傳感網(wǎng)時(shí)間同步的意義n7.1.2 傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)7.1.1 傳感網(wǎng)時(shí)間同步的意義n無線傳感網(wǎng)的同步管理主要是指時(shí)間上的同步管理。無線傳感網(wǎng)的同步管理主要是指時(shí)間上的同步管理。q在分布式的無線傳感器

2、網(wǎng)絡(luò)應(yīng)用中，每個(gè)傳感器節(jié)點(diǎn)都有各自的本地時(shí)鐘。不同節(jié)點(diǎn)的晶體振蕩器頻率存在偏差，干擾等也會造成節(jié)點(diǎn)之間的運(yùn)行時(shí)間的偏差。分布式系統(tǒng)的協(xié)同工作需要節(jié)點(diǎn)間的時(shí)間同步。n時(shí)間同步機(jī)制是分布式系統(tǒng)基礎(chǔ)框架中的一個(gè)關(guān)鍵機(jī)制。時(shí)間同步機(jī)制是分布式系統(tǒng)基礎(chǔ)框架中的一個(gè)關(guān)鍵機(jī)制。n在分布式系統(tǒng)中，時(shí)間同步涉及在分布式系統(tǒng)中，時(shí)間同步涉及“物理時(shí)間物理時(shí)間”和和“邏輯時(shí)間邏輯時(shí)間”兩個(gè)不同兩個(gè)不同的概念。的概念。q“物理時(shí)間”表示人類社會使用的絕對時(shí)間，而“邏輯時(shí)間”體現(xiàn)了事件發(fā)生的順序關(guān)系，是一個(gè)相對概念。分布式系統(tǒng)通常需要個(gè)表示整個(gè)系統(tǒng)時(shí)間的全局時(shí)間。全局時(shí)間根據(jù)需要可以是物理時(shí)間也可以是邏輯時(shí)間。n時(shí)間同

3、步機(jī)制在傳統(tǒng)網(wǎng)絡(luò)中已經(jīng)得到了廣泛應(yīng)用，如網(wǎng)絡(luò)時(shí)間協(xié)議時(shí)間同步機(jī)制在傳統(tǒng)網(wǎng)絡(luò)中已經(jīng)得到了廣泛應(yīng)用，如網(wǎng)絡(luò)時(shí)間協(xié)議(Netwolk Time Protocl，NTP)是因特網(wǎng)采用的時(shí)間同步協(xié)議。另外，是因特網(wǎng)采用的時(shí)間同步協(xié)議。另外，GPS和無線測距等技術(shù)也可以用來提供網(wǎng)絡(luò)的全局時(shí)間同步。和無線測距等技術(shù)也可以用來提供網(wǎng)絡(luò)的全局時(shí)間同步。7.1.1 傳感網(wǎng)時(shí)間同步的意義（2）n在傳感網(wǎng)的很多應(yīng)用中，同樣需要時(shí)間同步機(jī)制。在傳感網(wǎng)的很多應(yīng)用中，同樣需要時(shí)間同步機(jī)制。q例如，在節(jié)點(diǎn)時(shí)間同步的基礎(chǔ)上，可以遠(yuǎn)程觀察衛(wèi)星和導(dǎo)彈發(fā)射的軌道變化情況等。另外，時(shí)間同步能夠用來形成分布式波束系統(tǒng)，構(gòu)成TDMA調(diào)度機(jī)

4、制，實(shí)現(xiàn)多傳感器節(jié)點(diǎn)的數(shù)據(jù)融合，以及用時(shí)間序列的目標(biāo)位置來估計(jì)目標(biāo)的運(yùn)行速度和方向，或者通過測量聲音的傳播時(shí)間確定節(jié)點(diǎn)到聲源的距離或聲源的位量。n無線傳感網(wǎng)時(shí)間同步機(jī)制的意義和作用主要體現(xiàn)在如下兩方面。無線傳感網(wǎng)時(shí)間同步機(jī)制的意義和作用主要體現(xiàn)在如下兩方面。q首先，傳感器節(jié)點(diǎn)通常需要彼此協(xié)作，去完成復(fù)雜的監(jiān)測和感知任務(wù)。n數(shù)據(jù)融合是協(xié)作操作的典型例子，不同的節(jié)點(diǎn)采集的數(shù)據(jù)最終融合并形成一個(gè)有意義的結(jié)果。例如，在車輛跟蹤系統(tǒng)中，傳感器節(jié)點(diǎn)記錄車輛的位置和時(shí)間，并傳送給網(wǎng)關(guān)匯聚節(jié)點(diǎn)，然后結(jié)合這些信息來估計(jì)車輛的位置和速度。如果傳感器節(jié)點(diǎn)缺乏統(tǒng)一的時(shí)間同步，則對車輛的位置估計(jì)將是不準(zhǔn)確的。q其次，傳

5、感網(wǎng)的一些節(jié)能方案是利用時(shí)間同步來實(shí)現(xiàn)的。n例如，傳感器可以在適當(dāng)?shù)臅r(shí)候休眠，在需要的時(shí)候再被喚醒。在應(yīng)用這種節(jié)能模式的時(shí)候，網(wǎng)絡(luò)節(jié)點(diǎn)應(yīng)該在相同的時(shí)間休眠或被喚醒，也就是說在數(shù)據(jù)到來時(shí)，節(jié)點(diǎn)的接收器并沒有關(guān)閉。在這里，傳感網(wǎng)時(shí)間同步機(jī)制的設(shè)計(jì)目的，是為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的本地時(shí)鐘提供共同的時(shí)間戳。7.1.2 傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)n由于傳感網(wǎng)節(jié)點(diǎn)的能量受限，以及低價(jià)格和小體積成為了傳感網(wǎng)時(shí)間同步的主要限制。由于傳感網(wǎng)節(jié)點(diǎn)的能量受限，以及低價(jià)格和小體積成為了傳感網(wǎng)時(shí)間同步的主要限制。n現(xiàn)有網(wǎng)絡(luò)的時(shí)間同步機(jī)制往往關(guān)注最小化同步誤差來達(dá)到最大的同步精度方面，而很少考慮現(xiàn)有網(wǎng)絡(luò)的

6、時(shí)間同步機(jī)制往往關(guān)注最小化同步誤差來達(dá)到最大的同步精度方面，而很少考慮計(jì)算和通信的開銷，以及能耗問題。無法套用傳統(tǒng)的時(shí)間同步機(jī)制協(xié)議。計(jì)算和通信的開銷，以及能耗問題。無法套用傳統(tǒng)的時(shí)間同步機(jī)制協(xié)議。n網(wǎng)絡(luò)時(shí)間協(xié)議網(wǎng)絡(luò)時(shí)間協(xié)議(NTP)在因特網(wǎng)得到了廣泛使用，具有精度高、魯棒性好和易擴(kuò)展等優(yōu)點(diǎn)。但在因特網(wǎng)得到了廣泛使用，具有精度高、魯棒性好和易擴(kuò)展等優(yōu)點(diǎn)。但是它依賴的條件在傳感網(wǎng)中難以得到滿足，因而不能直接移植運(yùn)行，這主要是由于以下原因。是它依賴的條件在傳感網(wǎng)中難以得到滿足，因而不能直接移植運(yùn)行，這主要是由于以下原因。n（1）NTP協(xié)議很少考慮協(xié)議很少考慮網(wǎng)絡(luò)鏈路網(wǎng)絡(luò)鏈路失效問題。而在傳感網(wǎng)中，

7、無線鏈路的通信質(zhì)量受環(huán)境影失效問題。而在傳感網(wǎng)中，無線鏈路的通信質(zhì)量受環(huán)境影響較大，甚至?xí)r常會有通信中斷的情況。響較大，甚至?xí)r常會有通信中斷的情況。n（2）NTP協(xié)議的協(xié)議的網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)相對穩(wěn)定。而傳感網(wǎng)的拓?fù)浣Y(jié)構(gòu)是動態(tài)變化的，簡單的靜態(tài)手工相對穩(wěn)定。而傳感網(wǎng)的拓?fù)浣Y(jié)構(gòu)是動態(tài)變化的，簡單的靜態(tài)手工配置無法適應(yīng)這種變化。配置無法適應(yīng)這種變化。n（3）NTP協(xié)議中協(xié)議中時(shí)間基準(zhǔn)時(shí)間基準(zhǔn)服務(wù)器間的同步需要通過其他基礎(chǔ)設(shè)施的協(xié)助。如服務(wù)器間的同步需要通過其他基礎(chǔ)設(shè)施的協(xié)助。如GPS系統(tǒng)和無系統(tǒng)和無線電廣播報(bào)時(shí)系統(tǒng)，而在傳感網(wǎng)的有些應(yīng)用中，無法取得相應(yīng)基礎(chǔ)設(shè)施的支持。線電廣播報(bào)時(shí)系統(tǒng)，而在傳感網(wǎng)的有

8、些應(yīng)用中，無法取得相應(yīng)基礎(chǔ)設(shè)施的支持。n（4）NTP協(xié)議需要協(xié)議需要頻繁交換信息頻繁交換信息，來不斷校準(zhǔn)時(shí)鐘頻率偏差帶來的誤差。并通過復(fù)雜的修，來不斷校準(zhǔn)時(shí)鐘頻率偏差帶來的誤差。并通過復(fù)雜的修正算法，消除時(shí)間同步消息在傳輸和處理過程中受到的非確定因素干擾，正算法，消除時(shí)間同步消息在傳輸和處理過程中受到的非確定因素干擾，CPU使用、信道偵使用、信道偵聽和占用都不受任何約束。而傳感網(wǎng)存在資源約束，必須考慮能量消耗。聽和占用都不受任何約束。而傳感網(wǎng)存在資源約束，必須考慮能量消耗。7.1.2 傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)（傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)（2）n另外，另外，GPS系統(tǒng)雖然能夠以納秒級的精度與世界標(biāo)

9、淮時(shí)間系統(tǒng)雖然能夠以納秒級的精度與世界標(biāo)淮時(shí)間UTC保保持同步，但需要配置高成本的接收機(jī)，同時(shí)無法在室內(nèi)、森林或持同步，但需要配置高成本的接收機(jī)，同時(shí)無法在室內(nèi)、森林或水下等有障礙的環(huán)境中使用。如果是用于軍事目的，沒有主控權(quán)水下等有障礙的環(huán)境中使用。如果是用于軍事目的，沒有主控權(quán)的的GPS系統(tǒng)也是不可依賴的。系統(tǒng)也是不可依賴的。n在傳感網(wǎng)絡(luò)中只可能為極少數(shù)節(jié)點(diǎn)配備在傳感網(wǎng)絡(luò)中只可能為極少數(shù)節(jié)點(diǎn)配備GPS接收機(jī)，這些節(jié)點(diǎn)可接收機(jī)，這些節(jié)點(diǎn)可以為傳感網(wǎng)提供基準(zhǔn)時(shí)間。以為傳感網(wǎng)提供基準(zhǔn)時(shí)間。n基于傳感網(wǎng)的特點(diǎn)，以及其在能量、價(jià)格和體積等方面的約束，基于傳感網(wǎng)的特點(diǎn)，以及其在能量、價(jià)格和體積等方面的約

10、束，使得使得NTP、GPS等現(xiàn)有時(shí)間同步機(jī)制并不適用于通常的傳感網(wǎng)，等現(xiàn)有時(shí)間同步機(jī)制并不適用于通常的傳感網(wǎng)，需要專門的時(shí)間同步協(xié)議才能使其正常工作。需要專門的時(shí)間同步協(xié)議才能使其正常工作。7.1.2 傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)（傳感網(wǎng)時(shí)間同步協(xié)議的特點(diǎn)（3）n目前幾種成熟的傳感網(wǎng)時(shí)間同步協(xié)議是：目前幾種成熟的傳感網(wǎng)時(shí)間同步協(xié)議是：RBS（Reference Broadcast Synchronization，RBS)、Tiny-sync/Mini-Sync和和TPSN(Timing sync Protocol for Sensor Networks，TPSN) 。nRBS同步協(xié)議的基本思想是：

11、多個(gè)節(jié)點(diǎn)接收同一個(gè)同步信號，然后在多個(gè)收到同步信同步協(xié)議的基本思想是：多個(gè)節(jié)點(diǎn)接收同一個(gè)同步信號，然后在多個(gè)收到同步信號的節(jié)點(diǎn)之間進(jìn)行同步。這種同步算法消除了同步信號發(fā)送方的時(shí)間不確定性。號的節(jié)點(diǎn)之間進(jìn)行同步。這種同步算法消除了同步信號發(fā)送方的時(shí)間不確定性。RBS同步協(xié)議的優(yōu)點(diǎn)是時(shí)間同步與同步協(xié)議的優(yōu)點(diǎn)是時(shí)間同步與MAC層協(xié)議分離，它的實(shí)現(xiàn)不受限于應(yīng)用層是否可以獲層協(xié)議分離，它的實(shí)現(xiàn)不受限于應(yīng)用層是否可以獲得得MAC層時(shí)間戳，協(xié)議的互操作性較好。這種同步協(xié)議的缺點(diǎn)是協(xié)議開銷較大。層時(shí)間戳，協(xié)議的互操作性較好。這種同步協(xié)議的缺點(diǎn)是協(xié)議開銷較大。nTiny-sync/Mini-sync是兩種簡單的

12、輕量級時(shí)間同步機(jī)制。這兩種算法假設(shè)節(jié)點(diǎn)的時(shí)鐘是兩種簡單的輕量級時(shí)間同步機(jī)制。這兩種算法假設(shè)節(jié)點(diǎn)的時(shí)鐘漂移遵循線性變化，因此兩個(gè)節(jié)點(diǎn)之間的時(shí)間偏移也是線性的，通過交換時(shí)標(biāo)分組來漂移遵循線性變化，因此兩個(gè)節(jié)點(diǎn)之間的時(shí)間偏移也是線性的，通過交換時(shí)標(biāo)分組來估計(jì)兩個(gè)節(jié)點(diǎn)間的最優(yōu)匹配偏移量。為了降低算法的復(fù)雜度，通過約束條件丟棄冗余估計(jì)兩個(gè)節(jié)點(diǎn)間的最優(yōu)匹配偏移量。為了降低算法的復(fù)雜度，通過約束條件丟棄冗余分組。分組。nTPSN時(shí)間同步協(xié)議采用層次結(jié)構(gòu)，能夠?qū)崿F(xiàn)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的時(shí)間同步。所有節(jié)點(diǎn)按照時(shí)間同步協(xié)議采用層次結(jié)構(gòu)，能夠?qū)崿F(xiàn)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的時(shí)間同步。所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行邏輯分級，表示節(jié)點(diǎn)到根節(jié)點(diǎn)的距

13、離，通過基于發(fā)送者層次結(jié)構(gòu)進(jìn)行邏輯分級，表示節(jié)點(diǎn)到根節(jié)點(diǎn)的距離，通過基于發(fā)送者接收者的節(jié)點(diǎn)接收者的節(jié)點(diǎn)對方式，每個(gè)節(jié)點(diǎn)與上一級的一個(gè)節(jié)點(diǎn)進(jìn)行同步，最終所有節(jié)點(diǎn)都與根節(jié)點(diǎn)實(shí)現(xiàn)時(shí)間對方式，每個(gè)節(jié)點(diǎn)與上一級的一個(gè)節(jié)點(diǎn)進(jìn)行同步，最終所有節(jié)點(diǎn)都與根節(jié)點(diǎn)實(shí)現(xiàn)時(shí)間同步。同步。7.2 RBS同步機(jī)制同步機(jī)制nRBS協(xié)議是基于接收者和接收者時(shí)間同步機(jī)制的代表協(xié)議，基本原理如圖所示。協(xié)議是基于接收者和接收者時(shí)間同步機(jī)制的代表協(xié)議，基本原理如圖所示。n發(fā)送節(jié)點(diǎn)廣播一個(gè)參考（發(fā)送節(jié)點(diǎn)廣播一個(gè)參考（reference）分組，廣播域中兩個(gè)節(jié)點(diǎn)都能夠接收到這個(gè)）分組，廣播域中兩個(gè)節(jié)點(diǎn)都能夠接收到這個(gè)分組，每個(gè)接收節(jié)點(diǎn)分別根

14、據(jù)自己的本地時(shí)鐘記錄接收到分組，每個(gè)接收節(jié)點(diǎn)分別根據(jù)自己的本地時(shí)鐘記錄接收到reference分組的時(shí)刻，分組的時(shí)刻，然后交換它們記錄的然后交換它們記錄的reference分組的接收時(shí)間。分組的接收時(shí)間。n兩個(gè)接收時(shí)間的差值相當(dāng)于兩個(gè)接收節(jié)點(diǎn)間的時(shí)間差值，其中一個(gè)節(jié)點(diǎn)根據(jù)這個(gè)兩個(gè)接收時(shí)間的差值相當(dāng)于兩個(gè)接收節(jié)點(diǎn)間的時(shí)間差值，其中一個(gè)節(jié)點(diǎn)根據(jù)這個(gè)時(shí)間差值更改它的本地時(shí)間，從而達(dá)到兩個(gè)接收節(jié)點(diǎn)的時(shí)間同步。時(shí)間差值更改它的本地時(shí)間，從而達(dá)到兩個(gè)接收節(jié)點(diǎn)的時(shí)間同步。7.2 RBS同步機(jī)制（同步機(jī)制（2）nRBS機(jī)制中不是通告發(fā)送節(jié)點(diǎn)的時(shí)間值，而是通過廣播同步參考機(jī)制中不是通告發(fā)送節(jié)點(diǎn)的時(shí)間值，而是通過

15、廣播同步參考分組來實(shí)現(xiàn)接收節(jié)點(diǎn)間的相對時(shí)間同步，參考分組本身不需要攜分組來實(shí)現(xiàn)接收節(jié)點(diǎn)間的相對時(shí)間同步，參考分組本身不需要攜帶任何時(shí)標(biāo)，也不需要知道是何時(shí)發(fā)送出去的。帶任何時(shí)標(biāo)，也不需要知道是何時(shí)發(fā)送出去的。n影響影響RBS機(jī)制性能的主要因素包括接收節(jié)點(diǎn)間的時(shí)鐘偏差（時(shí)鐘機(jī)制性能的主要因素包括接收節(jié)點(diǎn)間的時(shí)鐘偏差（時(shí)鐘歪斜）、接收節(jié)點(diǎn)的非確定性因素、接收節(jié)點(diǎn)的個(gè)數(shù)等等。歪斜）、接收節(jié)點(diǎn)的非確定性因素、接收節(jié)點(diǎn)的個(gè)數(shù)等等。n為了提高時(shí)間同步的精度，為了提高時(shí)間同步的精度，RBS機(jī)制采用了統(tǒng)計(jì)技術(shù)，通過多次機(jī)制采用了統(tǒng)計(jì)技術(shù)，通過多次發(fā)送參考消息，獲得接收節(jié)點(diǎn)之間時(shí)間差異的平均值。對于時(shí)鐘發(fā)送參考

16、消息，獲得接收節(jié)點(diǎn)之間時(shí)間差異的平均值。對于時(shí)鐘偏差問題，采用了最小平方的線性回歸方法進(jìn)行線性擬合，直線偏差問題，采用了最小平方的線性回歸方法進(jìn)行線性擬合，直線的斜率就是兩個(gè)節(jié)點(diǎn)的時(shí)鐘偏差，直線上的點(diǎn)就表示節(jié)點(diǎn)間的時(shí)的斜率就是兩個(gè)節(jié)點(diǎn)的時(shí)鐘偏差，直線上的點(diǎn)就表示節(jié)點(diǎn)間的時(shí)間差。間差。7.3 Tiny-sync/mini-sync同步機(jī)制同步機(jī)制n在通常情況下，節(jié)點(diǎn)的硬件時(shí)鐘是時(shí)間的單調(diào)非遞減函數(shù)。用來產(chǎn)生在通常情況下，節(jié)點(diǎn)的硬件時(shí)鐘是時(shí)間的單調(diào)非遞減函數(shù)。用來產(chǎn)生實(shí)時(shí)時(shí)間的晶體頻率依賴于周圍環(huán)境條件，在相當(dāng)長一段時(shí)間內(nèi)可以實(shí)時(shí)時(shí)間的晶體頻率依賴于周圍環(huán)境條件，在相當(dāng)長一段時(shí)間內(nèi)可以認(rèn)為保持不變

17、。由于節(jié)點(diǎn)之間時(shí)鐘頻偏和時(shí)鐘相偏往往存在差異，但認(rèn)為保持不變。由于節(jié)點(diǎn)之間時(shí)鐘頻偏和時(shí)鐘相偏往往存在差異，但是它們時(shí)鐘頻偏或相偏之間的差值在一段時(shí)間內(nèi)保持不變，根據(jù)節(jié)點(diǎn)是它們時(shí)鐘頻偏或相偏之間的差值在一段時(shí)間內(nèi)保持不變，根據(jù)節(jié)點(diǎn)之間的線性相關(guān)性，可以得出：之間的線性相關(guān)性，可以得出：122121)()(bttatt式中，a12和b12分別表示兩個(gè)時(shí)鐘之間的相對時(shí)鐘頻偏和相對時(shí)鐘相偏。Tiny-sync算法和Mini-sync算法采用傳統(tǒng)的雙向消息設(shè)計(jì)來估計(jì)節(jié)點(diǎn)時(shí)鐘間的相對漂移和相對偏移。節(jié)點(diǎn)1給節(jié)點(diǎn)2發(fā)送探測消息，時(shí)間戳是t0，節(jié)點(diǎn)2在接收到消息后產(chǎn)生時(shí)間戳tb。并且立刻發(fā)送應(yīng)答消息。7.3

18、Tiny-sync/mini-sync同步機(jī)制同步機(jī)制(2)121212120)()()()(bttattbttattbrb最后節(jié)點(diǎn)1在收到應(yīng)答消息時(shí)產(chǎn)生時(shí)間戳tr，利用這些時(shí)間戳的絕對順序和上面的等式可以得到下面的不等式：三個(gè)時(shí)間戳（t0、tb、tr）叫做數(shù)據(jù)點(diǎn)，Tiny-sync和Mini-sync利用這些數(shù)據(jù)點(diǎn)進(jìn)行工作。隨著數(shù)據(jù)點(diǎn)數(shù)目的增多，算法的精確度也提高。每個(gè)數(shù)據(jù)點(diǎn)遵循相對漂移和相對偏移的兩個(gè)約束條件。7.3 Tiny-sync/mini-sync同步機(jī)制同步機(jī)制(3)圖7-3描述了數(shù)據(jù)點(diǎn)加在a12和b12上的約束。Tiny-sync中每次獲得新的數(shù)據(jù)點(diǎn)時(shí)，首先和以前的數(shù)據(jù)點(diǎn)比較，

19、如果新的數(shù)據(jù)點(diǎn)計(jì)算出的誤差大于以前數(shù)據(jù)點(diǎn)計(jì)算出的誤差，則拋棄新的數(shù)據(jù)點(diǎn)，否則就采用新的數(shù)據(jù)點(diǎn)，而拋棄舊的數(shù)據(jù)點(diǎn)。這樣時(shí)間同步總共只需要存儲三到四個(gè)數(shù)據(jù)點(diǎn)，就可以實(shí)現(xiàn)一定精度的時(shí)間同步。7.3 Tiny-sync/mini-sync同步機(jī)制同步機(jī)制(4)圖圖7-4所示，在收到所示，在收到(A1,B1)和和(A2,B1)后，計(jì)算出頻偏和相偏的估計(jì)值，在收到數(shù)據(jù)點(diǎn)后，計(jì)算出頻偏和相偏的估計(jì)值，在收到數(shù)據(jù)點(diǎn)(A3,B3)之之后，約束后，約束A1、B1、A3、B3被儲存，被儲存，A2、B2被丟棄了，但是后來接收到數(shù)據(jù)點(diǎn)被丟棄了，但是后來接收到數(shù)據(jù)點(diǎn)(A4,B4)可以可以和和(A2,B2)聯(lián)合而構(gòu)成更好的

20、估計(jì)，但是此時(shí)聯(lián)合而構(gòu)成更好的估計(jì)，但是此時(shí)(A2,B2)已經(jīng)丟棄，只能獲得次優(yōu)估計(jì)。已經(jīng)丟棄，只能獲得次優(yōu)估計(jì)。Mini-sync算法是為了克服Tiny-sync算法中丟失有用數(shù)據(jù)點(diǎn)的缺點(diǎn)而提出的，該算法建立約束條件來確保僅丟掉將來不會有用的數(shù)據(jù)點(diǎn)，并且每次獲取新的數(shù)據(jù)點(diǎn)后都更新約束條件。7.4 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議7.4 TPSN時(shí)間同步協(xié)議時(shí)間同步協(xié)議nTPSN時(shí)間同步協(xié)議類似于傳統(tǒng)網(wǎng)絡(luò)的時(shí)間同步協(xié)議類似于傳統(tǒng)網(wǎng)絡(luò)的NTP協(xié)議，目的是提供傳感協(xié)議，目的是提供傳感網(wǎng)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步。網(wǎng)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步。n在網(wǎng)絡(luò)中有一個(gè)節(jié)點(diǎn)可以與外界通信，從而獲取外部時(shí)間，這

21、種在網(wǎng)絡(luò)中有一個(gè)節(jié)點(diǎn)可以與外界通信，從而獲取外部時(shí)間，這種節(jié)點(diǎn)被稱為根節(jié)點(diǎn)。根節(jié)點(diǎn)可裝配諸如節(jié)點(diǎn)被稱為根節(jié)點(diǎn)。根節(jié)點(diǎn)可裝配諸如GPS接收機(jī)這樣的復(fù)雜硬接收機(jī)這樣的復(fù)雜硬件部件，并作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)鐘源。件部件，并作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)鐘源。nTPSN協(xié)議采用層次型網(wǎng)絡(luò)結(jié)構(gòu)，首先將所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)協(xié)議采用層次型網(wǎng)絡(luò)結(jié)構(gòu)，首先將所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行分級，然后每個(gè)節(jié)點(diǎn)與上一級的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終行分級，然后每個(gè)節(jié)點(diǎn)與上一級的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終所有節(jié)點(diǎn)都與根節(jié)點(diǎn)的時(shí)間同步，節(jié)點(diǎn)對之間的時(shí)間同步是基于所有節(jié)點(diǎn)都與根節(jié)點(diǎn)的時(shí)間同步，節(jié)點(diǎn)對之間的時(shí)間同步是基于發(fā)送者發(fā)送者接收者的同

22、步機(jī)制。接收者的同步機(jī)制。1TPSN協(xié)議的操作過程協(xié)議的操作過程nTPSN協(xié)議假設(shè)每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識號協(xié)議假設(shè)每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識號ID，節(jié)點(diǎn)間的無線通信鏈路是雙向的，通過雙向的消息，節(jié)點(diǎn)間的無線通信鏈路是雙向的，通過雙向的消息交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。TPSN協(xié)議將整個(gè)網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行管理，負(fù)責(zé)生成和維協(xié)議將整個(gè)網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)按照層次結(jié)構(gòu)進(jìn)行管理，負(fù)責(zé)生成和維護(hù)層次結(jié)構(gòu)。很多傳感網(wǎng)依賴網(wǎng)內(nèi)處理，需要類似的層次型結(jié)構(gòu)，如護(hù)層次結(jié)構(gòu)。很多傳感網(wǎng)依賴網(wǎng)內(nèi)處理，需要類似的層次型結(jié)構(gòu)，如TinyDB需要數(shù)據(jù)融合樹。這樣，整需要數(shù)據(jù)融合樹。這

23、樣，整個(gè)網(wǎng)絡(luò)只需要生成和維護(hù)一個(gè)共享的層次結(jié)構(gòu)。個(gè)網(wǎng)絡(luò)只需要生成和維護(hù)一個(gè)共享的層次結(jié)構(gòu)。TPSN協(xié)議包括如下兩個(gè)階段。第一個(gè)階段生成層次結(jié)構(gòu)，協(xié)議包括如下兩個(gè)階段。第一個(gè)階段生成層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)部被賦予一個(gè)級別，根節(jié)點(diǎn)被賦予最高級別第每個(gè)節(jié)點(diǎn)部被賦予一個(gè)級別，根節(jié)點(diǎn)被賦予最高級別第0級，第級的節(jié)點(diǎn)至少能夠與一個(gè)第（）級的節(jié)點(diǎn)級，第級的節(jié)點(diǎn)至少能夠與一個(gè)第（）級的節(jié)點(diǎn)通信；第二個(gè)階段實(shí)現(xiàn)所有樹節(jié)點(diǎn)的時(shí)間同步，第通信；第二個(gè)階段實(shí)現(xiàn)所有樹節(jié)點(diǎn)的時(shí)間同步，第1級節(jié)點(diǎn)同步到根節(jié)點(diǎn)，第級的節(jié)點(diǎn)同步到第（）級的級節(jié)點(diǎn)同步到根節(jié)點(diǎn)，第級的節(jié)點(diǎn)同步到第（）級的一個(gè)節(jié)點(diǎn)，最終所有節(jié)點(diǎn)都同步到根節(jié)點(diǎn)，實(shí)現(xiàn)整個(gè)

24、網(wǎng)絡(luò)的時(shí)間同步。下面詳細(xì)說明該協(xié)議的兩個(gè)階段的一個(gè)節(jié)點(diǎn)，最終所有節(jié)點(diǎn)都同步到根節(jié)點(diǎn)，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步。下面詳細(xì)說明該協(xié)議的兩個(gè)階段的實(shí)施細(xì)節(jié)。實(shí)施細(xì)節(jié)。n第一階段被稱為第一階段被稱為“層次發(fā)現(xiàn)階段層次發(fā)現(xiàn)階段”。首先，在網(wǎng)絡(luò)部署后，根節(jié)點(diǎn)通過廣播。首先，在網(wǎng)絡(luò)部署后，根節(jié)點(diǎn)通過廣播“級別發(fā)現(xiàn)級別發(fā)現(xiàn)”分組，啟動層次分組，啟動層次發(fā)現(xiàn)階段。級別發(fā)現(xiàn)分組包含發(fā)送節(jié)點(diǎn)的發(fā)現(xiàn)階段。級別發(fā)現(xiàn)分組包含發(fā)送節(jié)點(diǎn)的ID和級別。根節(jié)點(diǎn)的鄰居節(jié)點(diǎn)收到根節(jié)點(diǎn)發(fā)送的分組后，將自己和級別。根節(jié)點(diǎn)的鄰居節(jié)點(diǎn)收到根節(jié)點(diǎn)發(fā)送的分組后，將自己的級別設(shè)置為分組中的級別加的級別設(shè)置為分組中的級別加1，即為第，即為第1級，建立

25、它們自己的級別，然后廣播新的級別發(fā)現(xiàn)分組，其中包級，建立它們自己的級別，然后廣播新的級別發(fā)現(xiàn)分組，其中包含的級別為含的級別為1。節(jié)點(diǎn)收到第。節(jié)點(diǎn)收到第i級節(jié)點(diǎn)的廣播分組后，記錄發(fā)送這個(gè)廣播分組的節(jié)點(diǎn)級節(jié)點(diǎn)的廣播分組后，記錄發(fā)送這個(gè)廣播分組的節(jié)點(diǎn)ID，設(shè)置自己的級別為，設(shè)置自己的級別為（），廣播級別被設(shè)置為（）的分組。這個(gè)過程持續(xù)進(jìn)行，直到網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)都被賦予了一個(gè)級別。（），廣播級別被設(shè)置為（）的分組。這個(gè)過程持續(xù)進(jìn)行，直到網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)都被賦予了一個(gè)級別。節(jié)點(diǎn)一旦建立自己的級別，就忽略任何其他級別的發(fā)現(xiàn)分組，以防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞。節(jié)點(diǎn)一旦建立自己的級別，就忽略任何其他級別的發(fā)現(xiàn)分組，

26、以防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞。n第二個(gè)階段被稱為第二個(gè)階段被稱為“同步階段同步階段”。在層次結(jié)構(gòu)建立以后，根節(jié)點(diǎn)通過廣播時(shí)間同步分組啟動同步階段。第。在層次結(jié)構(gòu)建立以后，根節(jié)點(diǎn)通過廣播時(shí)間同步分組啟動同步階段。第1級節(jié)點(diǎn)收到這個(gè)分組后，各自分別等待一段隨機(jī)時(shí)間，通過與根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)。第級節(jié)點(diǎn)收到這個(gè)分組后，各自分別等待一段隨機(jī)時(shí)間，通過與根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)。第2級節(jié)點(diǎn)級節(jié)點(diǎn)偵聽到第偵聽到第1級節(jié)點(diǎn)的交換消息后，后退和等待一段隨機(jī)時(shí)間，并與它在層次發(fā)現(xiàn)階段記錄的第級節(jié)點(diǎn)的交換消息后，后退和等待一段隨機(jī)時(shí)間，并與它在層次發(fā)現(xiàn)階段記錄的第1個(gè)級別的節(jié)個(gè)級別的節(jié)點(diǎn)交換消息以進(jìn)行同步。等待一段時(shí)間的目的是保證第點(diǎn)交換消息以進(jìn)行同步。等待一段時(shí)間的目的是保證第2級節(jié)點(diǎn)在第級節(jié)點(diǎn)在第1級節(jié)點(diǎn)的時(shí)間同步完成后才啟動消息級節(jié)點(diǎn)的時(shí)間同步完成后才啟動消息交換。最后每個(gè)節(jié)點(diǎn)與層次結(jié)構(gòu)中最靠近的上一級節(jié)點(diǎn)進(jìn)行同步，從而使所有節(jié)點(diǎn)都同步到了根節(jié)點(diǎn)。交換。最后每個(gè)節(jié)點(diǎn)與層次結(jié)構(gòu)中最靠近的上一級節(jié)點(diǎn)進(jìn)行同步，從而使所有節(jié)點(diǎn)都同步到了根節(jié)點(diǎn)。7.5 時(shí)間同步的應(yīng)用示例n磁阻傳感網(wǎng)如何對機(jī)動車輛進(jìn)行測速。n網(wǎng)絡(luò)必須先完成時(shí)間同