1、第七章、時(shí)間同步(tngb)技術(shù)共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)與挑戰(zhàn)(tio zhn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步(tngb)協(xié)議新型同步機(jī)制總結(jié)共七十二頁基本概念時(shí)間同步的定義(dngy)WSN時(shí)間同步技術(shù)背景時(shí)間同步技術(shù)的分類時(shí)間同步技術(shù)的應(yīng)用場合關(guān)鍵問題：時(shí)鐘模型共七十二頁時(shí)間同步技術(shù)(jsh)的定義無線傳感器網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有自己的內(nèi)部時(shí)鐘，即本地時(shí)間。由于不同節(jié)點(diǎn)的晶體振蕩頻率存在偏差，再加上溫度的差異、電磁波干擾等，即使在某個(gè)時(shí)間點(diǎn)所有節(jié)點(diǎn)時(shí)鐘一致，一段時(shí)間后他們的時(shí)間也會(huì)再次出現(xiàn)偏

2、差。無線傳感器網(wǎng)絡(luò)的時(shí)間同步是指各個(gè)獨(dú)立的節(jié)點(diǎn)通過不斷與其他節(jié)點(diǎn)交換本地時(shí)鐘信息，最終達(dá)到并且保持全局時(shí)間協(xié)調(diào)一致的過程(guchng)。即以本地通信確保全局同步。共七十二頁思考(sko)為什么需要時(shí)間(shjin)同步？時(shí)間同步能解決什么問題？共七十二頁 根據(jù)CSMA/CA協(xié)議，當(dāng)節(jié)點(diǎn)要傳輸一個(gè)(y )分組時(shí)，它首先偵聽信道狀態(tài)。如果信道空閑，而且經(jīng)過一個(gè)(y )幀間間隔時(shí)間DIFS后，信道仍然空閑，則站點(diǎn)立即開始發(fā)送信息。如果信道忙，則站點(diǎn)始終偵聽信道，直到信道的空閑時(shí)間超過DIFS。當(dāng)信道最終空閑下來的時(shí)候，節(jié)點(diǎn)進(jìn)一步使用二進(jìn)制退避算法，進(jìn)入退避狀態(tài)來避免發(fā)生碰撞。CSMA/CA協(xié)議(x

3、iy)需要嚴(yán)格的時(shí)間同步共七十二頁 網(wǎng)絡(luò)節(jié)點(diǎn)在進(jìn)入退避狀態(tài)時(shí)，啟動(dòng)一個(gè)退避計(jì)時(shí)器，當(dāng)計(jì)時(shí)達(dá)到退避時(shí)間后結(jié)束退避狀態(tài)。在退避狀態(tài)下，只有當(dāng)檢測到信道空閑時(shí)才進(jìn)行計(jì)時(shí)。如果(rgu)信道忙，退避計(jì)時(shí)器中止計(jì)時(shí)，直到檢測到信道空閑時(shí)間大于DIFS后才繼續(xù)計(jì)時(shí)。當(dāng)多個(gè)節(jié)點(diǎn)推遲且進(jìn)入隨機(jī)退避時(shí)，利用隨機(jī)函數(shù)選擇最小退避時(shí)間的節(jié)點(diǎn)作為競爭優(yōu)勝者。共七十二頁偵聽(zhn tn)偵聽(zhn tn)睡眠睡眠節(jié)點(diǎn)協(xié)同進(jìn)行周期性偵聽和睡眠的狀態(tài)切換，確保節(jié)點(diǎn)能同步進(jìn)行偵聽和睡眠調(diào)度。調(diào)度周期：周期性偵聽和睡眠的時(shí)間之和為一個(gè)調(diào)度周期。S-MAC協(xié)議需要嚴(yán)格的時(shí)間同步S-MAC協(xié)議(Sensor MAC) 是在80

4、2.1l MAC協(xié)議的基礎(chǔ)上，針對傳感器網(wǎng)絡(luò)的節(jié)省能量需求而提出的。共七十二頁 流量自適應(yīng)偵聽機(jī)制的基本思想是在一次通信過程中，通信節(jié)點(diǎn)的鄰居在通信結(jié)束后不立即進(jìn)入睡眠狀態(tài)，而是保持偵聽一段時(shí)間。 如果節(jié)點(diǎn)在這段時(shí)間內(nèi)接收到RTS，則可以立刻接收數(shù)據(jù)，無須等到下一次調(diào)度(diod)偵聽周期，從而減少了數(shù)據(jù)分組的傳輸延遲。如果在這段時(shí)間內(nèi)沒有接收到RTS，則轉(zhuǎn)入睡眠狀態(tài)直到下一次調(diào)度偵聽周期。流量自適應(yīng)偵聽機(jī)制需要時(shí)間(shjin)同步共七十二頁RTSA數(shù)據(jù)(shj)1RTS數(shù)據(jù)(shj)2BCTSACK偵聽睡眠偵聽CTSACKBCTSACK偵聽偵聽CTSACKRTSA數(shù)據(jù)1RTS數(shù)據(jù)2偵聽睡眠

5、共七十二頁WSN時(shí)間同步(tngb)技術(shù)背景集中式系統(tǒng)與分布式系統(tǒng)集中式：在事件間有著(yu zhe)明確的時(shí)間先后關(guān)系時(shí)，不存在同步問題；時(shí)間關(guān)系不明確時(shí)仍存在。分布式：同步是必需的，只是對同步的要求程度不同需要解決的問題同步精度功耗可擴(kuò)展性共七十二頁WSN時(shí)間同步機(jī)制(jzh)的主要性能參數(shù)最大誤差：一組傳感器節(jié)點(diǎn)之間的最大時(shí)間差或相對外部標(biāo)準(zhǔn)時(shí)間的最大差值。同步(tngb)期限：節(jié)點(diǎn)保持時(shí)間同步(tngb)的時(shí)間長度。同步范圍：節(jié)點(diǎn)保持時(shí)間同步的區(qū)域范圍?？捎眯裕悍秶采w的完整性。效率：達(dá)到同步精度所經(jīng)歷的時(shí)間以及消耗的能量。代價(jià)和體積：需要考慮節(jié)點(diǎn)的價(jià)格和體積。共七十二頁時(shí)間同步技術(shù)(

6、jsh)的分類根據(jù)同步的級(jí)別，可以分為排序、相對同步與絕對同步，其間為遞進(jìn)關(guān)系。排序只能(zh nn)區(qū)分事件發(fā)生的先后相對同步：維持本地時(shí)鐘的運(yùn)行，定期獲取其他節(jié)點(diǎn)的時(shí)鐘偏移和飄移，經(jīng)過換算達(dá)到同步的目的。如RBS協(xié)議絕對同步：本地時(shí)鐘和參考時(shí)鐘保持一致，修改本地時(shí)鐘。如TPSN協(xié)議根據(jù)參考源不同，可以分為外同步（與外部某時(shí)間同步，如GPS ）與內(nèi)同步（網(wǎng)絡(luò)內(nèi)部某個(gè)節(jié)點(diǎn)的時(shí)鐘）。根據(jù)同步對象的范圍不同，可以分為局部同步與全網(wǎng)同步共七十二頁時(shí)間(shjin)同步技術(shù)的應(yīng)用場合多傳感器數(shù)據(jù)壓縮(sh j y su)與融合鄰近傳感節(jié)點(diǎn)對相同事件的感知數(shù)據(jù)需要融合，基于時(shí)間戳判斷是否同一事件，需要時(shí)

7、鐘同步低功耗MAC協(xié)議、路由協(xié)議不發(fā)送數(shù)據(jù)時(shí)，節(jié)點(diǎn)處于休眠狀態(tài)，網(wǎng)絡(luò)節(jié)點(diǎn)的同步休眠需要時(shí)鐘同步測距、定位距離測量和定位是基于無線電信號(hào)的傳輸時(shí)間，時(shí)間同步越準(zhǔn)確，距離測量也越準(zhǔn)確分布式系統(tǒng)的傳統(tǒng)要求分布式系統(tǒng)的數(shù)據(jù)庫查詢，狀態(tài)等一致性的要求協(xié)作傳輸、處理的要求協(xié)作傳輸是基于電磁波的能量累加效應(yīng)，多個(gè)節(jié)點(diǎn)以相同的調(diào)制解調(diào)方式同時(shí)發(fā)送信號(hào)，使得遠(yuǎn)處的匯集節(jié)點(diǎn)能接收到信號(hào)共七十二頁時(shí)間同步(tngb)技術(shù)的重要性時(shí)間同步技術(shù)對無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位、無線信道時(shí)分復(fù)用、低功耗睡眠、路由協(xié)議、數(shù)據(jù)融合、傳感事件排序等應(yīng)用(yngyng)及服務(wù)，都會(huì)產(chǎn)生直接或間接地重要影響。時(shí)間同步機(jī)制幾乎滲透至每一個(gè)

8、與數(shù)據(jù)相關(guān)的環(huán)節(jié)，其實(shí)現(xiàn)的好壞直接決定了以數(shù)據(jù)為中心的無線傳感器網(wǎng)絡(luò)整體系統(tǒng)性能的優(yōu)劣。共七十二頁關(guān)鍵問題：時(shí)鐘(shzhng)模型硬件時(shí)鐘(shzhng)模型軟件時(shí)鐘模型共七十二頁硬件時(shí)鐘(shzhng)模型基本名詞時(shí)間、晶振、時(shí)鐘（RTC）時(shí)鐘偏移（clock offset）：是指兩個(gè)時(shí)鐘瞬時(shí)讀數(shù)的差。晶振計(jì)時(shí)的時(shí)刻與實(shí)際時(shí)刻的差值，反映計(jì)時(shí)的準(zhǔn)確性時(shí)鐘率偏移（Clock Skew）：是指兩個(gè)時(shí)鐘的頻率差。它可以看作是Clock offset的一階導(dǎo)數(shù)。時(shí)間漂移(Clock Drift)：是指時(shí)鐘頻率的變化，反映晶振的穩(wěn)定性。實(shí)際晶振的頻率有可能隨著外界環(huán)境溫度、濕度的變化而有所改變。Cl

9、ock Drift可以看作是Clock offset的二階導(dǎo)數(shù)。速率恒定模型該模型認(rèn)為頻率保持恒定不變，最常用，但不適應(yīng)環(huán)境變化劇烈(jli)的場合飄移有界模型常用于確定同步誤差上下界，頻率穩(wěn)定度常用ppm（百萬分之一）飄移變化有界模型時(shí)鐘的漂移變化率是有限的。共七十二頁軟件時(shí)鐘(shzhng)模型以軟件虛擬(xn)時(shí)鐘一般是個(gè)分段連續(xù)、嚴(yán)格單調(diào)的函數(shù)共七十二頁相關(guān)(xinggun)術(shù)語信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)鄰居節(jié)點(diǎn)跳數(shù)、跳段距離基礎(chǔ)設(shè)施到達(dá)時(shí)間、到達(dá)時(shí)間差接收信號(hào)強(qiáng)度指示到達(dá)角度(jiod)視線關(guān)系、非視線關(guān)系共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)方法(fngf)與面臨的挑戰(zhàn)典型

10、時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)共七十二頁傳統(tǒng)(chuntng)同步：NTP與GPSNTP：網(wǎng)絡(luò)時(shí)間(shjin)協(xié)議GPS：全球定位系統(tǒng)共七十二頁NTP（Network Time Protocol） 體系結(jié)構(gòu)共七十二頁NTP提供準(zhǔn)確時(shí)間，首先要有準(zhǔn)確的時(shí)間來源，這一時(shí)間應(yīng)該是國際標(biāo)準(zhǔn)時(shí)間UTC。 NTP獲得UTC的時(shí)間來源可以是原子鐘、天文臺(tái)、衛(wèi)星，也可以從Internet上獲取。這樣就有了準(zhǔn)確而可靠的時(shí)間源。時(shí)間按NTP服務(wù)器的等級(jí)傳播。按照離外部UTC 源的遠(yuǎn)近將所有服務(wù)器歸入不同的Stratum（層）中。Stratum-1在頂層，有外部UTC接入，而Stratum-2則從Stratum-1

11、獲取時(shí)間，Stratum-3從Stratum-2獲取時(shí)間，以此類推，但Stratum層的總數(shù)限制在15以內(nèi)。所有這些服務(wù)器在邏輯上形成階梯式的架構(gòu)相互連接(linji)，而Stratum-1的時(shí)間服務(wù)器是整個(gè)系統(tǒng)的基礎(chǔ)。共七十二頁NTP（Network Time Protocol）體系結(jié)構(gòu)（單機(jī)）共七十二頁NTP的適用性NTP不適合于WSN：體積(tj)、計(jì)算能力和存儲(chǔ)空間存在限制傳輸方式不同：無線而非有線目標(biāo)不同： WSN僅需局部最而非全局最優(yōu)共七十二頁GPS（Global Position System） 從根本上解決了人類在地球上的導(dǎo)航與定位問題。每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并

12、不斷發(fā)射其時(shí)間信息地面接收裝置同時(shí)接收4顆衛(wèi)星的時(shí)間信息，采用偽距測量定位方法可計(jì)算出時(shí)間和位置信息缺點(diǎn)（室內(nèi)(sh ni)、功耗、安全性、可靠性）共七十二頁時(shí)間同步協(xié)議應(yīng)用于無線傳感器網(wǎng)絡(luò)面臨(minlng)的挑戰(zhàn)室內(nèi)、礦井、森林，有遮擋網(wǎng)絡(luò)(wnglu)規(guī)模大、多點(diǎn)協(xié)作傳輸延遲的不確定性低功耗、低成本和小體積可擴(kuò)展性、移動(dòng)性健壯性、安全性共七十二頁傳輸(chun sh)延遲的不確定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver發(fā)送時(shí)間：發(fā)送節(jié)點(diǎn)構(gòu)造和發(fā)送時(shí)間同

13、步消息所用時(shí)間。e.g., 系統(tǒng)調(diào)用時(shí)間；內(nèi)核調(diào)度時(shí)間；消息從主機(jī)發(fā)送到網(wǎng)絡(luò)接口時(shí)間。訪問時(shí)間：發(fā)送節(jié)點(diǎn)等待訪問網(wǎng)絡(luò)傳輸信道的時(shí)間。傳輸延遲(ynch)：發(fā)送節(jié)點(diǎn)傳輸?shù)浇邮展?jié)點(diǎn)所經(jīng)歷的時(shí)間。傳播時(shí)間（Transmission time）:發(fā)送節(jié)點(diǎn)發(fā)送數(shù)據(jù)所經(jīng)歷的時(shí)間接收時(shí)間：從接收節(jié)點(diǎn)的網(wǎng)絡(luò)接口接收到消息到消息接收結(jié)束收到時(shí)間（Receive time）通知主機(jī)消息達(dá)到事件所經(jīng)歷的時(shí)間間隔。共七十二頁傳輸(chun sh)延遲的進(jìn)一步細(xì)化時(shí)間典型值特性Send time & Receive time0100ms不確定，依賴處理器負(fù)載、操作系統(tǒng)系統(tǒng)調(diào)用開銷Access time10500ms不確

14、定，依賴信道負(fù)載。Transmission time & Reception time1020ms確定，依賴報(bào)文長度和發(fā)送速率。Propagation time1s（距離300米）確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。Interrupt waiting time在大多數(shù)情況下5s，在重負(fù)載下，可達(dá)30s不確定，依賴處理器類型和處理器負(fù)載。Encoding time & Decoding time100200s，2s的抖動(dòng)確定，依賴射頻芯片的種類和設(shè)置。Byte alignment time0400s確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。共七十二頁低功耗、低成本和小體積(tj)軟硬件都要受到該限制

15、存儲(chǔ)與計(jì)算能力均比較小電能供應(yīng)的緊張（電池體積有限）網(wǎng)絡(luò)規(guī)模大、密度高通信(tng xn)距離近 分布式、協(xié)作共七十二頁可擴(kuò)展性（Scalability）在大規(guī)模網(wǎng)絡(luò)中尤為重要滿足不同的網(wǎng)絡(luò)類型(lixng)、網(wǎng)絡(luò)規(guī)模滿足不同的應(yīng)用需求共七十二頁健壯性外部環(huán)境復(fù)雜，抗干擾能力要強(qiáng)需要(xyo)應(yīng)對安全性挑戰(zhàn)無線傳感器網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性較強(qiáng)網(wǎng)絡(luò)規(guī)模變化、需求變化共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型(xnxng)同步機(jī)制總結(jié)共七十二頁典型時(shí)間同步(tngb)協(xié)議NTP（Network Time Protocol）DMTS （Delay Measurement

16、 Time Synchronization） RBS （Reference Broadcast Synchronization） TPSN （Timing-sync Protocol for Sensor Networks） HRTS （Hierarchy Referencing Time Synchronization Protocol） FTSP （Flooding Time Synchronization Protocol） 共七十二頁DMTS (Delay Measurement Time Synchronization)DMTS基于同步消息在傳輸路徑上所有延遲的估計(jì)，實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間

17、同步在DMTS機(jī)制中，選擇一個(gè)節(jié)點(diǎn)作為時(shí)間主節(jié)點(diǎn)(leader)廣播(gungb)同步時(shí)間。所有接收節(jié)點(diǎn)測量這個(gè)時(shí)間廣播(gungb)分組（packet）的延遲，設(shè)置它的時(shí)間為接收到分組攜帶的時(shí)間加上這個(gè)廣播分組的傳輸延遲，這樣所有接收到廣播分組的節(jié)點(diǎn)都與主節(jié)點(diǎn)進(jìn)行時(shí)間同步。時(shí)間同步的精度主要由延遲測量的精度所決定。共七十二頁主節(jié)點(diǎn)在檢測到信道空閑時(shí)，給廣播分組加上時(shí)間戳t0，用來去除發(fā)送端的處理延遲和MAC層的接入延遲。在發(fā)送廣播分組前，主節(jié)點(diǎn)需要發(fā)送前導(dǎo)碼和起始字符，以便接收節(jié)點(diǎn)進(jìn)行(jnxng)接收同步，根據(jù)發(fā)送的信息位個(gè)數(shù)n和發(fā)送每比特位需要的時(shí)間t，可以估計(jì)出前導(dǎo)碼和起始字符的發(fā)送時(shí)

18、間位nt。接收節(jié)點(diǎn)在廣播分組到達(dá)時(shí)刻加上時(shí)間戳t1，并在調(diào)整自己的時(shí)鐘之前時(shí)刻再記錄時(shí)間t2，接收端的接收處理延遲就是(t2-t1)。這樣，如果忽略無線信號(hào)的傳播延遲，接收節(jié)點(diǎn)從t0時(shí)刻到調(diào)整時(shí)鐘前的時(shí)間長度約為nt + (t2-t1) 。因此，接收節(jié)點(diǎn)為了與發(fā)送節(jié)點(diǎn)時(shí)鐘同步，調(diào)整其時(shí)鐘為t0 + nt + (t2-t1) 。共七十二頁發(fā)送者接收者：DMTS 簡單(jindn)直觀 單報(bào)文同步同步精度低 t0+nt+(t2-t1) 廣播方式同步能耗低發(fā)送者接收者發(fā)送前導(dǎo)碼、同步字 （nt）嵌入時(shí)標(biāo)t0：（回避發(fā)送端的處理延遲和MAC層的訪問延遲)接收前導(dǎo)碼、同步字接收ACK接收數(shù)據(jù)發(fā)送ACK接

19、收處理時(shí)標(biāo)t1時(shí)標(biāo)t2發(fā)送時(shí)間訪問時(shí)間發(fā)送者在信道空閑后或爭用到信道后才插入本地時(shí)間(shjin)t0；接收處理報(bào)文的時(shí)間：前導(dǎo)碼時(shí)間nt，報(bào)文處理時(shí)間t2-t1；接收方的同步時(shí)刻為：t0+ nt+ t2-t1共七十二頁DMTS的優(yōu)缺點(diǎn)DMTS算法結(jié)合鏈路層標(biāo)記時(shí)間戳和時(shí)延估計(jì)等技術(shù)，消除了發(fā)送時(shí)間和訪問(fngwn)時(shí)間的影響，算法簡單，通信開銷小。DMTS單跳同步誤差受同步精度和計(jì)時(shí)精度影響。多跳精度隨跳數(shù)的增加而下降，由于誤差的正負(fù)相加抵消了一部分，兩跳的誤差約為單跳誤差的1.5倍。DMTS算法沒有估計(jì)時(shí)鐘的頻率偏差，時(shí)鐘保持同步的時(shí)間較短；也沒有消除時(shí)鐘計(jì)時(shí)對同步精度的影響，因而其精度

20、不高，不適用于定位等要求高精度同步的應(yīng)用。共七十二頁RBS (Reference Broadcast synchronization)RBS協(xié)議不是去同步報(bào)文的收發(fā)雙方，而是去同步報(bào)文的多個(gè)接收者。如下圖所示：在由3個(gè)節(jié)點(diǎn)組成的單跳網(wǎng)絡(luò)中，參考節(jié)點(diǎn)每發(fā)出一個(gè)參考報(bào)文，其廣播域內(nèi)的其他接收者節(jié)點(diǎn)都將接收到該報(bào)文，并各自記錄下接收到該參考報(bào)文時(shí)的本地時(shí)刻。接收者相互交換它們(t men)記錄的時(shí)刻并計(jì)算差值，該差值就是接收者之間的時(shí)鐘偏移。但這有一個(gè)前提，就是接收者必須同時(shí)(tngsh)收到此消息，即接收者同步。假設(shè)是否成立？共七十二頁RBS接收節(jié)點(diǎn)(ji din)時(shí)間相移接收者接收者同步的基本依

21、據(jù)：接收者時(shí)間(shjin)相移均值為0共七十二頁RBS性能的影響因素(yn s)及改善技術(shù)影響RBS機(jī)制性能的主要因素包括(boku)時(shí)鐘偏差、接收節(jié)點(diǎn)間的時(shí)間速率、接收節(jié)點(diǎn)非確定因素和接收節(jié)點(diǎn)的個(gè)數(shù)等。為提高時(shí)間同步精度，RBS機(jī)制采用了統(tǒng)計(jì)技術(shù)，通過發(fā)送節(jié)點(diǎn)發(fā)送多個(gè)消息，獲得接收節(jié)點(diǎn)之間時(shí)間差異的平均值。共七十二頁RBS的優(yōu)點(diǎn)(yudin)RBS中是通過廣播同步信標(biāo)分組實(shí)現(xiàn)接收節(jié)點(diǎn)之間的相對時(shí)間(shjin)同步，信標(biāo)分組本身并不需要攜帶任何時(shí)標(biāo)，不依賴于信標(biāo)的發(fā)送時(shí)間(shjin)。由于無線信道的廣播特性，信標(biāo)分組相對所有接收節(jié)點(diǎn)而言同時(shí)發(fā)送到物理信道上，這樣就除去發(fā)送時(shí)間和訪問時(shí)間引

22、入的時(shí)間同步誤差。對于傳播時(shí)間，RBS只關(guān)心各個(gè)接收節(jié)點(diǎn)之間消息傳播時(shí)間的差值。對于射頻信號(hào)來說，傳播時(shí)間差值非常小，RBS忽略了傳播時(shí)間帶來的時(shí)間偏差。共七十二頁RBS的不足(bz)RBS的缺點(diǎn)是對網(wǎng)絡(luò)有一定的要求，它不適合點(diǎn)對點(diǎn)通信的網(wǎng)絡(luò)，且要求網(wǎng)絡(luò)有物理廣播信道。擴(kuò)展性不好，因?yàn)楣?jié)點(diǎn)間本地時(shí)間戳通信需要額外的消息交換開銷，不能很好地應(yīng)用到大規(guī)模的多跳網(wǎng)絡(luò)中。RBS有很大的交換次數(shù)，對于具有2個(gè)節(jié)點(diǎn)的單跳網(wǎng)絡(luò)，需要O(n2)的消息交換，如果n很大時(shí)，消息交換開銷是相當(dāng)大的，導(dǎo)致節(jié)點(diǎn)的計(jì)算開銷也非常之大。RBS中接收節(jié)點(diǎn)之間進(jìn)行相互同步，但并不與發(fā)送節(jié)點(diǎn)同步；實(shí)際上，在WSN中發(fā)送節(jié)點(diǎn)很可能

23、也是一個(gè)普通的網(wǎng)絡(luò)節(jié)點(diǎn)因而也需要同步，為使該節(jié)點(diǎn)和其它節(jié)點(diǎn)進(jìn)行同步，需要另外一個(gè)節(jié)點(diǎn)作為(zuwi)參照廣播發(fā)射節(jié)點(diǎn)，這導(dǎo)致了相當(dāng)高的能耗。共七十二頁TPSN（Timing-sync Protocol for Sensor Networks）-傳感器網(wǎng)絡(luò)(wnglu)時(shí)間同步協(xié)議 2003年11月，Saurabh Ganeriwal提出了TPSN同步機(jī)制，目的是通過采用層次型網(wǎng)絡(luò)結(jié)構(gòu)來提供全網(wǎng)范圍內(nèi)節(jié)點(diǎn)同步。該機(jī)制分為拓?fù)浣?jinl)階段和同步建立(jinl)階段，考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息交換計(jì)算消息的平均延遲，提高了精度。共七十二頁TPSN時(shí)間同步協(xié)議(xiy)思想Wedn

24、esday, July 27, 20221、TPSN是類似于NTP（Network Time Protocol）時(shí)間同步協(xié)議2、目的是提供傳感器網(wǎng)絡(luò)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步3、節(jié)點(diǎn)結(jié)構(gòu)中包含一個(gè)根節(jié)點(diǎn)，它與外界通信獲取外界時(shí)間，以此作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)鐘源4、將節(jié)點(diǎn)分級(jí)(fn j)后（根節(jié)點(diǎn)是0級(jí)，累加），每個(gè)節(jié)點(diǎn)同上一級(jí)的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終與根節(jié)點(diǎn)同步5、節(jié)點(diǎn)對之間的同步采用發(fā)送者-接收者同步機(jī)制共七十二頁每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識(shí)號(hào)ID節(jié)點(diǎn)間的無線通信鏈路是雙向的，通過雙向消息(xio xi)交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步整個(gè)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)按層次結(jié)構(gòu)管理，由TPSN協(xié)議生成和維護(hù)TP

25、SN協(xié)議(xiy)過程（1）協(xié)議準(zhǔn)備階段Wednesday, July 27, 2022共七十二頁目的：生成節(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ò)部署(b sh)后，由根節(jié)點(diǎn)廣播級(jí)別發(fā)現(xiàn)分組來啟動(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），廣播級(jí)別為（i+1）的分組，這個(gè)過程持續(xù)到網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)都被賦予一個(gè)級(jí)別節(jié)點(diǎn)一旦建立自己的級(jí)別，就忽略任何其他級(jí)別發(fā)

26、現(xiàn)分組，防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞第一階段 層次發(fā)現(xiàn)(fxin)階段（Level Discovery Phase）Wednesday, July 27, 2022TPSN協(xié)議過程（2）共七十二頁目的：實(shí)現(xiàn)所有樹節(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)通過廣播時(shí)間同步分組啟動(dòng)同步階段第1級(jí)節(jié)點(diǎn)收到分組后，各自分別等待一段隨機(jī)時(shí)間，再通過與根節(jié)點(diǎn)交換(jiohun)消息同步到根節(jié)點(diǎn)第2級(jí)節(jié)點(diǎn)偵聽到第1級(jí)節(jié)點(diǎn)的交換消息后，等待一段隨機(jī)時(shí)間，再與它記錄的上一級(jí)別的節(jié)點(diǎn)交換消息進(jìn)行同步，網(wǎng)絡(luò)中的

27、節(jié)點(diǎn)依次與上一級(jí)節(jié)點(diǎn)同步，最終都同步到根節(jié)點(diǎn)等待一段隨機(jī)時(shí)間是為了保證該級(jí)節(jié)點(diǎn)在上一級(jí)節(jié)點(diǎn)同步完成后才啟動(dòng)消息交換第二階段 同步(tngb)階段（Synchronization Phase）Wednesday, July 27, 2022TPSN協(xié)議過程（3）共七十二頁節(jié)點(diǎn)A節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)TPSN原理-相鄰(xin ln)級(jí)別節(jié)點(diǎn)間的同步機(jī)制令為當(dāng)節(jié)點(diǎn)A的本地時(shí)刻為T1時(shí)，節(jié)點(diǎn)A和B之間的時(shí)偏。報(bào)文的傳輸(chun sh)延遲均為d。共七十二頁TPSN算法(sun f)優(yōu)點(diǎn)與缺點(diǎn)TPSN算法優(yōu)點(diǎn)：TPSN基于雙向報(bào)文交換，因此同步精度高。對任意節(jié)點(diǎn)其同步誤

28、差取決于它距離根節(jié)點(diǎn)的跳數(shù)，而與網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)無關(guān)，使TPSN同步精度不會(huì)隨節(jié)點(diǎn)數(shù)目增加而降級(jí)，從而使TPSN具有較好的擴(kuò)展性。TPSN算法的缺點(diǎn)：TPSN本質(zhì)上是對同步，因此全網(wǎng)同步的同步能耗高。一旦根節(jié)點(diǎn)失效，就要重新選擇根節(jié)點(diǎn)并重新進(jìn)行分級(jí)和同步階段的處理，增加了計(jì)算和能量開銷。另外，TPSN算法沒有對時(shí)鐘的頻差進(jìn)行估計(jì)，這使得它需要(xyo)頻繁同步，開銷較大。共七十二頁理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半結(jié)合對clock skew的估計(jì)，可以(ky)提高TPSN的精度TPSN同步(tngb)誤差的分析共七十二頁HRTS( Hierarchy Referencing Ti

29、me Synchronization Protocol )基于雙向報(bào)文交換（如TPSN）的傳感器網(wǎng)絡(luò)時(shí)間同步(tngb)協(xié)議具有同步(tngb)精度高的優(yōu)點(diǎn)，但一次只能同步(tngb)一對節(jié)點(diǎn)。n個(gè)節(jié)點(diǎn)的單跳網(wǎng)絡(luò)則需要n-1次同步操作，同步功耗較大。RBS只需要一次同步過程就可完成一個(gè)單跳網(wǎng)內(nèi)所有節(jié)點(diǎn)間的同步，同步功耗低，當(dāng)然同步精度也相對變差。HRTS是一種結(jié)合了RBS所使用的參考廣播同步技術(shù)和TPSN所使用的雙向報(bào)文交互同步技術(shù)的方法，減少了同步所需的報(bào)文開銷。圖描述了層級(jí)時(shí)間同步的過程。假設(shè)單跳網(wǎng)絡(luò)有包含時(shí)間基準(zhǔn)節(jié)點(diǎn)在內(nèi)的3個(gè)節(jié)點(diǎn)BS、n1和n2。共七十二頁步驟1：時(shí)間基準(zhǔn)節(jié)點(diǎn)BS發(fā)出一

30、個(gè)同步請求報(bào)文，該報(bào)文隨機(jī)指定一個(gè)鄰居節(jié)點(diǎn)（例如n1）作為應(yīng)答者節(jié)點(diǎn)（即對應(yīng)于上圖中的B節(jié)點(diǎn)）。n1記錄報(bào)文到達(dá)時(shí)刻T2，同時(shí)n2也記錄下該報(bào)文的到達(dá)時(shí)刻，記為T2 。步驟2：應(yīng)答者節(jié)點(diǎn)n1向BS節(jié)點(diǎn)發(fā)一個(gè)同步應(yīng)答報(bào)文，報(bào)文中包含了T2與T3。步驟3：現(xiàn)在BS節(jié)點(diǎn)已經(jīng)和n1節(jié)點(diǎn)進(jìn)行了一次雙向報(bào)文交換，BS節(jié)點(diǎn)計(jì)算出它與n1節(jié)點(diǎn)之間的時(shí)鐘偏移。步驟4：BS節(jié)點(diǎn)發(fā)送一個(gè)包含和T2信息的報(bào)文。步驟5：當(dāng)n1、n2節(jié)點(diǎn)接收到該報(bào)文，對于應(yīng)答者節(jié)點(diǎn)n1來說，只要將其本地時(shí)間減去就達(dá)到與BS節(jié)點(diǎn)的瞬時(shí)(shn sh)同步。對于其他節(jié)點(diǎn)來說，只要在其本地時(shí)間加上T2 T2 即可達(dá)到與BS節(jié)點(diǎn)間的瞬時(shí)同步 H

31、RTS同步(tngb)過程 BS n1 n2 n3 (a) BS n1 n2 n3 (b) BS n1 n2 n3 (c) n4 BS n1 n2 n3 (d) n4 節(jié)點(diǎn)A節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)共七十二頁HRTS協(xié)議(xiy)的特點(diǎn)根節(jié)點(diǎn)和應(yīng)答者節(jié)點(diǎn)本質(zhì)上是采用(ciyng)TPSN同步。根節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是雙向報(bào)文交換同步（但非TPSN）。應(yīng)答者節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是接收者-接收者同步。HRTS協(xié)議充分利用了無線傳輸?shù)膹V播特性（類似于DMTS）來進(jìn)一步降低協(xié)議的同步功耗。共七十二頁FTSP（Flooding Time Synchronization

32、 Protocol） 泛洪時(shí)間同步協(xié)議（Flooding Time Synchronization Protocol）由Vanderbilt大學(xué)Miklos,Branislav等提出，目標(biāo)是實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步并且誤差控制在微秒級(jí)。該算法使用單個(gè)廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時(shí)間同步。 多跳的FTSP協(xié)議采用層次結(jié)構(gòu)，根節(jié)點(diǎn)為同步源，可以適應(yīng)大量傳感器節(jié)點(diǎn)，對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和根節(jié)點(diǎn)的失效(sh xio)有健壯性，精確度較好。該算法通過采用MAC層時(shí)間戳和線性回歸偏差補(bǔ)償彌補(bǔ)了相關(guān)的錯(cuò)誤源。共七十二頁FTSP（Flooding Time Synchronization Protoco

33、l） FTSP協(xié)議的同步原理：在傳感網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)有唯一的ID號(hào)，通過根節(jié)點(diǎn)的自動(dòng)選擇算法選出ID號(hào)最小的節(jié)點(diǎn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)就是選中的同步時(shí)間基準(zhǔn)點(diǎn)。同步從根節(jié)點(diǎn)開始，時(shí)間同步信息分組采用廣播的方式發(fā)送。未同步節(jié)點(diǎn)接收到已同步節(jié)點(diǎn)廣播的時(shí)間信息分組后，從信息分組中估算本地時(shí)間與全局時(shí)間的時(shí)間漂移和時(shí)鐘偏移，調(diào)整自己的本地時(shí)間，使之與全局時(shí)間達(dá)成統(tǒng)一。在節(jié)點(diǎn)同步后，生成新的時(shí)間信息分組廣播到網(wǎng)絡(luò)中。重復(fù)這個(gè)過程，直到(zhdo)整個(gè)網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)都時(shí)間同步。 FTSP協(xié)議主要采用下面機(jī)制來降低時(shí)間延遲對時(shí)間同步精度的影響：在MAC層記錄時(shí)間信標(biāo)，細(xì)分消息傳輸中的時(shí)間延遲并對這些延遲進(jìn)行補(bǔ)償，利用

34、線性回歸算法估算時(shí)間漂移。共七十二頁FTSP的特點(diǎn)(tdin)FTSP算法通過對收發(fā)過程的分析，把時(shí)延進(jìn)一步分為發(fā)送中斷處理時(shí)延、編碼時(shí)延、傳播時(shí)延、解碼時(shí)延、字節(jié)對齊時(shí)延、接收終端處理時(shí)延，進(jìn)一步降低了時(shí)延的不確定性。通過發(fā)射多個(gè)時(shí)間戳（單個(gè)報(bào)文中包括多個(gè)時(shí)間戳），使得接收節(jié)點(diǎn)可以利用最小方差線性擬合估算自己和發(fā)送節(jié)點(diǎn)的漂移和偏移差。通過良好的根節(jié)點(diǎn)選舉機(jī)制，針對根節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入以及拓?fù)?tu p)結(jié)構(gòu)變化等情況進(jìn)行了優(yōu)化，使得算法的健壯性很好，適合于軍事等惡劣應(yīng)用情況。共七十二頁FTSP的特點(diǎn)(tdin)與典型應(yīng)用FTSP是現(xiàn)有的典型時(shí)間同步協(xié)議中精度最高的同步協(xié)議，并且有良好的健壯

35、性，不會(huì)因?yàn)閭€(gè)別節(jié)點(diǎn)的失效而收到影響。但FTSP基于MAC層時(shí)間戳技術(shù)的細(xì)節(jié)(xji)技術(shù)的實(shí)現(xiàn)來提高同步精度，使得FTSP協(xié)議的通用性不強(qiáng)。并且洪泛的方式使得能耗開銷巨大。用于ZigBee網(wǎng)絡(luò)的同步休眠與喚醒算法共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間(shjin)同步協(xié)議新型同步機(jī)制總結(jié)共七十二頁螢火蟲同步(tngb)1935年，Science1975年, Peskin的RC模型1989年，M&S模型(未考慮延遲(ynch)1998年，Ernst（考慮有延遲）2005年，真實(shí)地實(shí)現(xiàn)簡單，高效，可擴(kuò)展性強(qiáng)共七十二頁M&S模型(mxng)研究由初始不同步狀態(tài)如何達(dá)到

36、同步狀態(tài)個(gè)體性質(zhì)相同,因此一旦達(dá)到同步則永遠(yuǎn)同步螢火蟲之間的交互(jioh)被建模成電量耦合耦合延遲規(guī)定為0最終結(jié)論為:系統(tǒng)的同步收斂性取決于個(gè)體在自由狀態(tài)下的動(dòng)力學(xué)特性同步的實(shí)質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量 ,相位差通過同步過程不斷縮小，最終達(dá)到完全相同,即同步狀態(tài) 共七十二頁Ernst的研究(ynji)M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定(gdng)時(shí)的情況M&S模型只研究了正耦合的情況，Ernst還研究了負(fù)耦合的情況共七十二頁螢火蟲同步(tngb)的特點(diǎn)同步可直接在物理層而不需要以報(bào)文的方式實(shí)現(xiàn)。直接用硬件實(shí)現(xiàn)，使得同步精度不會(huì)受到MA

37、C延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影響。由于對任何同步信號(hào)的處理方式均相同，與同步信號(hào)的來源無關(guān)，因此可擴(kuò)展性以及適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)變化的能力很強(qiáng)。機(jī)制非常簡單，不需要對其它節(jié)點(diǎn)的時(shí)間(shjin)信息進(jìn)行存儲(chǔ)。螢火蟲同步算法的一個(gè)限制是要求每個(gè)節(jié)點(diǎn)具有相似性，但這種機(jī)制在非相似節(jié)點(diǎn)所組成的網(wǎng)絡(luò)下能否起到同步的作用，目前還不清楚。由于螢火蟲同步的理論研究還遠(yuǎn)未結(jié)束，工程實(shí)用性還有待考察。共七十二頁螢火蟲同步技術(shù)的未來(wili)發(fā)展螢火蟲同步技術(shù)對耦合延遲、耦合強(qiáng)度、耦合性質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾?。雖然在如兩個(gè)振蕩器的同步收斂性等研究上取得了一定的進(jìn)展，但無論是理論研究還是仿真研究，研究者在某

38、些(mu xi)結(jié)論上還不能達(dá)成一致的認(rèn)識(shí)。但可以認(rèn)同的一點(diǎn)是：在實(shí)際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會(huì)取得在一定誤差范圍內(nèi)的同步。共七十二頁內(nèi)容提要(ni rn t yo)基本概念傳統(tǒng)與挑戰(zhàn)典型(dinxng)時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)共七十二頁總結(jié)(zngji) 在無線傳感器網(wǎng)絡(luò)中，時(shí)間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗(nn ho)、可擴(kuò)展性和健壯性需求經(jīng)典的時(shí)間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時(shí)鐘飄移補(bǔ)償、MAC層時(shí)間戳技術(shù)以及雙向報(bào)文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性來降低同步能耗螢火蟲同步側(cè)重于提高可擴(kuò)展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)

39、絡(luò)的應(yīng)用 共七十二頁時(shí)間同步算法(sun f)分類基于Sender/Receiver的時(shí)間同步通信雙方中的發(fā)送節(jié)點(diǎn)需要記錄時(shí)間消息發(fā)送時(shí)刻的時(shí)間信標(biāo)，而接收節(jié)點(diǎn)則需要記錄時(shí)間消息接收時(shí)刻的時(shí)間信標(biāo)，同步過程中只需要一次通信。該模式的代表算法是FTSP， DMTS ?；赗eceiver/Receiver的時(shí)間同步在實(shí)現(xiàn)時(shí)間同步的過程中，節(jié)點(diǎn)只需要在接收時(shí)間消息的時(shí)刻記錄時(shí)間信標(biāo)，而發(fā)送時(shí)刻不需要記錄時(shí)間信標(biāo)，節(jié)點(diǎn)只需要知道接收到時(shí)間消息的精確時(shí)刻。典型協(xié)議有RBS等。基于Pair-Wise（成對）的時(shí)間同步這種算法利用成對同步方法進(jìn)行發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)間的時(shí)間同步，然后擴(kuò)展到整個(gè)網(wǎng)絡(luò)形成網(wǎng)絡(luò)的

40、時(shí)間同步。此類算法使得網(wǎng)絡(luò)的同步報(bào)文開銷較大，對于低開銷要求較高的工業(yè)無線網(wǎng)絡(luò)應(yīng)用有一定的局限性。而且同步階段所用時(shí)間隨節(jié)點(diǎn)數(shù)目的增加而線性增加,不適合(shh)對快速性要求較高的工業(yè)無線網(wǎng)絡(luò)。典型的算法主要有TPSN等。共七十二頁主要(zhyo)參考文獻(xiàn)（詳見原著）1 Elson J., Rmer K. Wireless sensor networks: a new regime for time synchronization. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 149-154.3 Elson J., Girod

41、 L., Estrin D. Fine-grained time synchronization using reference broadcasts. In: Proc. 5th Symposium on Operation System Design and Implementation, Boston, 2002, 147-163.4 Ganeriwal S., Kumar R., Srivastava M. Timing-sync protocol for sensor networks. In: Proc. 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, 2003, 138-149.7 Mills D. L. Network time protocol (Version3) specification, implementation and analysis. University of Delaware