無線傳感器組網(wǎng)-時(shí)間同步技術(shù)

第七章、時(shí)間同步技術(shù)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)基本概念時(shí)間同步的定義WSN時(shí)間同步技術(shù)背景時(shí)間同步技術(shù)的分類時(shí)間同步技術(shù)的應(yīng)用場(chǎng)合關(guān)鍵問題：時(shí)鐘模型時(shí)間同步技術(shù)的定義無線傳感器網(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)偏差。無線傳感器網(wǎng)絡(luò)的時(shí)間同步是指各個(gè)獨(dú)立的節(jié)點(diǎn)通過不斷與其他節(jié)點(diǎn)交換本地時(shí)鐘信息，最終達(dá)到并且保持全局時(shí)間協(xié)調(diào)一致的過程。即以本地通信確保全局同步。思考為什么需要時(shí)間同步？時(shí)間同步能解決什么問題？根據(jù)CSMA/CA協(xié)議，當(dāng)節(jié)點(diǎn)要傳輸一個(gè)分組時(shí)，它首先偵聽信道狀態(tài)。如果信道空閑，而且經(jīng)過一個(gè)幀間間隔時(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é)議需要嚴(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)檢測(cè)到信道空閑時(shí)才進(jìn)行計(jì)時(shí)。如果信道忙，退避計(jì)時(shí)器中止計(jì)時(shí)，直到檢測(cè)到信道空閑時(shí)間大于DIFS后才繼續(xù)計(jì)時(shí)。當(dāng)多個(gè)節(jié)點(diǎn)推遲且進(jìn)入隨機(jī)退避時(shí)，利用隨機(jī)函數(shù)選擇最小退避時(shí)間的節(jié)點(diǎn)作為競(jìng)爭(zhēng)優(yōu)勝者。偵聽偵聽睡眠睡眠●節(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é)議(SensorMAC)是在802.1lMAC協(xié)議的基礎(chǔ)上，針對(duì)傳感器網(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)度偵聽周期，從而減少了數(shù)據(jù)分組的傳輸延遲。如果在這段時(shí)間內(nèi)沒有接收到RTS，則轉(zhuǎn)入睡眠狀態(tài)直到下一次調(diào)度偵聽周期。流量自適應(yīng)偵聽機(jī)制需要時(shí)間同步RTSA數(shù)據(jù)1RTS數(shù)據(jù)2BCTSACK偵聽睡眠偵聽CTSACKBCTSACK偵聽偵聽CTSACKRTSA數(shù)據(jù)1RTS數(shù)據(jù)2偵聽睡眠WSN時(shí)間同步技術(shù)背景集中式系統(tǒng)與分布式系統(tǒng)集中式：在事件間有著明確的時(shí)間先后關(guān)系時(shí)，不存在同步問題；時(shí)間關(guān)系不明確時(shí)仍存在。分布式：同步是必需的，只是對(duì)同步的要求程度不同需要解決的問題同步精度功耗可擴(kuò)展性WSN時(shí)間同步機(jī)制的主要性能參數(shù)最大誤差：一組傳感器節(jié)點(diǎn)之間的最大時(shí)間差或相對(duì)外部標(biāo)準(zhǔn)時(shí)間的最大差值。同步期限：節(jié)點(diǎn)保持時(shí)間同步的時(shí)間長度。同步范圍：節(jié)點(diǎn)保持時(shí)間同步的區(qū)域范圍?？捎眯裕悍秶采w的完整性。效率：達(dá)到同步精度所經(jīng)歷的時(shí)間以及消耗的能量。代價(jià)和體積：需要考慮節(jié)點(diǎn)的價(jià)格和體積。時(shí)間同步技術(shù)的分類根據(jù)同步的級(jí)別，可以分為排序、相對(duì)同步與絕對(duì)同步，其間為遞進(jìn)關(guān)系。排序只能區(qū)分事件發(fā)生的先后相對(duì)同步：維持本地時(shí)鐘的運(yùn)行，定期獲取其他節(jié)點(diǎn)的時(shí)鐘偏移和飄移，經(jīng)過換算達(dá)到同步的目的。如RBS協(xié)議絕對(duì)同步：本地時(shí)鐘和參考時(shí)鐘保持一致，修改本地時(shí)鐘。如TPSN協(xié)議根據(jù)參考源不同，可以分為外同步（與外部某時(shí)間同步，如GPS）與內(nèi)同步（網(wǎng)絡(luò)內(nèi)部某個(gè)節(jié)點(diǎn)的時(shí)鐘）。根據(jù)同步對(duì)象的范圍不同，可以分為局部同步與全網(wǎng)同步時(shí)間同步技術(shù)的應(yīng)用場(chǎng)合多傳感器數(shù)據(jù)壓縮與融合鄰近傳感節(jié)點(diǎn)對(duì)相同事件的感知數(shù)據(jù)需要融合，基于時(shí)間戳判斷是否同一事件，需要時(shí)鐘同步低功耗MAC協(xié)議、路由協(xié)議不發(fā)送數(shù)據(jù)時(shí)，節(jié)點(diǎn)處于休眠狀態(tài)，網(wǎng)絡(luò)節(jié)點(diǎn)的同步休眠需要時(shí)鐘同步測(cè)距、定位距離測(cè)量和定位是基于無線電信號(hào)的傳輸時(shí)間，時(shí)間同步越準(zhǔn)確，距離測(cè)量也越準(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í)間同步技術(shù)的重要性時(shí)間同步技術(shù)對(duì)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位、無線信道時(shí)分復(fù)用、低功耗睡眠、路由協(xié)議、數(shù)據(jù)融合、傳感事件排序等應(yīng)用及服務(wù)，都會(huì)產(chǎn)生直接或間接地重要影響。時(shí)間同步機(jī)制幾乎滲透至每一個(gè)與數(shù)據(jù)相關(guān)的環(huán)節(jié)，其實(shí)現(xiàn)的好壞直接決定了以數(shù)據(jù)為中心的無線傳感器網(wǎng)絡(luò)整體系統(tǒng)性能的優(yōu)劣。關(guān)鍵問題：時(shí)鐘模型硬件時(shí)鐘模型軟件時(shí)鐘模型硬件時(shí)鐘模型基本名詞時(shí)間、晶振、時(shí)鐘（RTC）時(shí)鐘偏移（clockoffset）：是指兩個(gè)時(shí)鐘瞬時(shí)讀數(shù)的差。晶振計(jì)時(shí)的時(shí)刻與實(shí)際時(shí)刻的差值，反映計(jì)時(shí)的準(zhǔn)確性時(shí)鐘率偏移（ClockSkew）：是指兩個(gè)時(shí)鐘的頻率差。它可以看作是Clockoffset的一階導(dǎo)數(shù)。時(shí)間漂移(ClockDrift)：是指時(shí)鐘頻率的變化，反映晶振的穩(wěn)定性。實(shí)際晶振的頻率有可能隨著外界環(huán)境溫度、濕度的變化而有所改變。ClockDrift可以看作是Clockoffset的二階導(dǎo)數(shù)。速率恒定模型該模型認(rèn)為頻率保持恒定不變，最常用，但不適應(yīng)環(huán)境變化劇烈的場(chǎng)合飄移有界模型常用于確定同步誤差上下界，頻率穩(wěn)定度常用ppm（百萬分之一）飄移變化有界模型時(shí)鐘的漂移變化率是有限的。軟件時(shí)鐘模型以軟件虛擬時(shí)鐘一般是個(gè)分段連續(xù)、嚴(yán)格單調(diào)的函數(shù)相關(guān)術(shù)語信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)鄰居節(jié)點(diǎn)跳數(shù)、跳段距離基礎(chǔ)設(shè)施到達(dá)時(shí)間、到達(dá)時(shí)間差接收信號(hào)強(qiáng)度指示到達(dá)角度視線關(guān)系、非視線關(guān)系內(nèi)容提要基本概念傳統(tǒng)方法與面臨的挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)傳統(tǒng)同步：NTP與GPSNTP：網(wǎng)絡(luò)時(shí)間協(xié)議GPS：全球定位系統(tǒng)NTP（NetworkTimeProtocol）體系結(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獲取時(shí)間，Stratum-3從Stratum-2獲取時(shí)間，以此類推，但Stratum層的總數(shù)限制在15以內(nèi)。所有這些服務(wù)器在邏輯上形成階梯式的架構(gòu)相互連接，而Stratum-1的時(shí)間服務(wù)器是整個(gè)系統(tǒng)的基礎(chǔ)。NTP（NetworkTimeProtocol）體系結(jié)構(gòu)（單機(jī)）NTP的適用性NTP不適合于WSN：體積、計(jì)算能力和存儲(chǔ)空間存在限制傳輸方式不同：無線而非有線目標(biāo)不同：WSN僅需局部最而非全局最優(yōu)GPS（GlobalPositionSystem）從根本上解決了人類在地球上的導(dǎo)航與定位問題。每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時(shí)間信息地面接收裝置同時(shí)接收4顆衛(wèi)星的時(shí)間信息，采用偽距測(cè)量定位方法可計(jì)算出時(shí)間和位置信息缺點(diǎn)（室內(nèi)、功耗、安全性、可靠性）時(shí)間同步協(xié)議應(yīng)用于無線傳感器網(wǎng)絡(luò)

面臨的挑戰(zhàn)室內(nèi)、礦井、森林，有遮擋網(wǎng)絡(luò)規(guī)模大、多點(diǎn)協(xié)作傳輸延遲的不確定性低功耗、低成本和小體積可擴(kuò)展性、移動(dòng)性健壯性、安全性傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReceptiontimeReceivetimePropagationtimeSenderReceiver發(fā)送時(shí)間：發(fā)送節(jié)點(diǎn)構(gòu)造和發(fā)送時(shí)間同步消息所用時(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í)間。傳輸延遲：發(fā)送節(jié)點(diǎn)傳輸?shù)浇邮展?jié)點(diǎn)所經(jīng)歷的時(shí)間。傳播時(shí)間（Transmissiontime）:發(fā)送節(jié)點(diǎn)發(fā)送數(shù)據(jù)所經(jīng)歷的時(shí)間接收時(shí)間：從接收節(jié)點(diǎn)的網(wǎng)絡(luò)接口接收到消息到消息接收結(jié)束收到時(shí)間（Receivetime）通知主機(jī)消息達(dá)到事件所經(jīng)歷的時(shí)間間隔。傳輸延遲的進(jìn)一步細(xì)化時(shí)間典型值特性Sendtime&Receivetime0~100ms不確定，依賴處理器負(fù)載、操作系統(tǒng)系統(tǒng)調(diào)用開銷Accesstime10~500ms不確定，依賴信道負(fù)載。Transmissiontime&Receptiontime10~20ms確定，依賴報(bào)文長度和發(fā)送速率。Propagationtime<1μs（距離<300米）確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。Interruptwaitingtime在大多數(shù)情況下<5μs，在重負(fù)載下，可達(dá)30μs不確定，依賴處理器類型和處理器負(fù)載。Encodingtime&Decodingtime100~200μs，<2μs的抖動(dòng)確定，依賴射頻芯片的種類和設(shè)置。Bytealignmenttime0~400μs確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。低功耗、低成本和小體積軟硬件都要受到該限制存儲(chǔ)與計(jì)算能力均比較小電能供應(yīng)的緊張（電池體積有限）網(wǎng)絡(luò)規(guī)模大、密度高通信距離近分布式、協(xié)作可擴(kuò)展性（Scalability）在大規(guī)模網(wǎng)絡(luò)中尤為重要滿足不同的網(wǎng)絡(luò)類型、網(wǎng)絡(luò)規(guī)模滿足不同的應(yīng)用需求健壯性外部環(huán)境復(fù)雜，抗干擾能力要強(qiáng)需要應(yīng)對(duì)安全性挑戰(zhàn)無線傳感器網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性較強(qiáng)網(wǎng)絡(luò)規(guī)模變化、需求變化內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)典型時(shí)間同步協(xié)議NTP（NetworkTimeProtocol）DMTS

（DelayMeasurementTimeSynchronization）RBS

（ReferenceBroadcastSynchronization）TPSN

（Timing-syncProtocolforSensorNetworks）HRTS

（HierarchyReferencingTimeSynchronizationProtocol）FTSP

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

簡(jiǎn)單直觀單報(bào)文同步同步精度低t0+nt+(t2-t1)

廣播方式同步能耗低發(fā)送者接收者發(fā)送前導(dǎo)碼、同步字（nt）嵌入時(shí)標(biāo)t0：（回避發(fā)送端的處理延遲和MAC層的訪問延遲)接收前導(dǎo)碼、同步字接收ACK接收數(shù)據(jù)發(fā)送ACK接收處理時(shí)標(biāo)t1時(shí)標(biāo)t2發(fā)送時(shí)間訪問時(shí)間發(fā)送者在信道空閑后或爭(zhēng)用到信道后才插入本地時(shí)間t0；接收處理報(bào)文的時(shí)間：前導(dǎo)碼時(shí)間nt，報(bào)文處理時(shí)間t2-t1；接收方的同步時(shí)刻為：t0+nt+t2-t1DMTS的優(yōu)缺點(diǎn)DMTS算法結(jié)合鏈路層標(biāo)記時(shí)間戳和時(shí)延估計(jì)等技術(shù)，消除了發(fā)送時(shí)間和訪問時(shí)間的影響，算法簡(jiǎn)單，通信開銷小。DMTS單跳同步誤差受同步精度和計(jì)時(shí)精度影響。多跳精度隨跳數(shù)的增加而下降，由于誤差的正負(fù)相加抵消了一部分，兩跳的誤差約為單跳誤差的1.5倍。DMTS算法沒有估計(jì)時(shí)鐘的頻率偏差，時(shí)鐘保持同步的時(shí)間較短；也沒有消除時(shí)鐘計(jì)時(shí)對(duì)同步精度的影響，因而其精度不高，不適用于定位等要求高精度同步的應(yīng)用。RBS(ReferenceBroadcastsynchronization)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í)刻。接收者相互交換它們記錄的時(shí)刻并計(jì)算差值，該差值就是接收者之間的時(shí)鐘偏移。但這有一個(gè)前提，就是接收者必須同時(shí)收到此消息，即接收者同步。假設(shè)是否成立？RBS接收節(jié)點(diǎn)時(shí)間相移接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0RBS性能的影響因素及改善技術(shù)影響RBS機(jī)制性能的主要因素包括時(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)RBS中是通過廣播同步信標(biāo)分組實(shí)現(xiàn)接收節(jié)點(diǎn)之間的相對(duì)時(shí)間同步，信標(biāo)分組本身并不需要攜帶任何時(shí)標(biāo)，不依賴于信標(biāo)的發(fā)送時(shí)間。由于無線信道的廣播特性，信標(biāo)分組相對(duì)所有接收節(jié)點(diǎn)而言同時(shí)發(fā)送到物理信道上，這樣就除去發(fā)送時(shí)間和訪問時(shí)間引入的時(shí)間同步誤差。對(duì)于傳播時(shí)間，RBS只關(guān)心各個(gè)接收節(jié)點(diǎn)之間消息傳播時(shí)間的差值。對(duì)于射頻信號(hào)來說，傳播時(shí)間差值非常小，RBS忽略了傳播時(shí)間帶來的時(shí)間偏差。RBS的不足RBS的缺點(diǎn)是對(duì)網(wǎng)絡(luò)有一定的要求，它不適合點(diǎn)對(duì)點(diǎn)通信的網(wǎng)絡(luò)，且要求網(wǎng)絡(luò)有物理廣播信道。擴(kuò)展性不好，因?yàn)楣?jié)點(diǎn)間本地時(shí)間戳通信需要額外的消息交換開銷，不能很好地應(yīng)用到大規(guī)模的多跳網(wǎng)絡(luò)中。RBS有很大的交換次數(shù)，對(duì)于具有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)很可能也是一個(gè)普通的網(wǎng)絡(luò)節(jié)點(diǎn)因而也需要同步，為使該節(jié)點(diǎn)和其它節(jié)點(diǎn)進(jìn)行同步，需要另外一個(gè)節(jié)點(diǎn)作為參照廣播發(fā)射節(jié)點(diǎn)，這導(dǎo)致了相當(dāng)高的能耗。TPSN（Timing-syncProtocolforSensorNetworks）--傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議2003年11月，SaurabhGaneriwal提出了TPSN同步機(jī)制，目的是通過采用層次型網(wǎng)絡(luò)結(jié)構(gòu)來提供全網(wǎng)范圍內(nèi)節(jié)點(diǎn)同步。該機(jī)制分為拓?fù)浣㈦A段和同步建立階段，考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息交換計(jì)算消息的平均延遲，提高了精度。TPSN時(shí)間同步協(xié)議思想Thursday,January12,20231、TPSN是類似于NTP（NetworkTimeProtocol）時(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í)后（根節(jié)點(diǎn)是0級(jí)，累加），每個(gè)節(jié)點(diǎn)同上一級(jí)的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終與根節(jié)點(diǎn)同步5、節(jié)點(diǎn)對(duì)之間的同步采用發(fā)送者-接收者同步機(jī)制每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識(shí)號(hào)ID節(jié)點(diǎn)間的無線通信鏈路是雙向的，通過雙向消息交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步整個(gè)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)按層次結(jié)構(gòu)管理，由TPSN協(xié)議生成和維護(hù)TPSN協(xié)議過程（1）協(xié)議準(zhǔn)備階段Thursday,January12,2023目的：生成節(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)分組來啟動(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ā)現(xiàn)分組，防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞第一階段層次發(fā)現(xiàn)階段（LevelDiscoveryPhase）Thursday,January12,2023TPSN協(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)交換消息同步到根節(jié)點(diǎn)第2級(jí)節(jié)點(diǎn)偵聽到第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)等待一段隨機(jī)時(shí)間是為了保證該級(jí)節(jié)點(diǎn)在上一級(jí)節(jié)點(diǎn)同步完成后才啟動(dòng)消息交換第二階段同步階段（SynchronizationPhase）Thursday,January12,2023TPSN協(xié)議過程（3）節(jié)點(diǎn)A節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)TPSN原理--相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制令Δ為當(dāng)節(jié)點(diǎn)A的本地時(shí)刻為T1時(shí)，節(jié)點(diǎn)A和B之間的時(shí)偏。報(bào)文的傳輸延遲均為d。TPSN算法優(yōu)點(diǎn)與缺點(diǎn)TPSN算法優(yōu)點(diǎn)：TPSN基于雙向報(bào)文交換，因此同步精度高。對(duì)任意節(jié)點(diǎn)其同步誤差取決于它距離根節(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ì)上是對(duì)同步，因此全網(wǎng)同步的同步能耗高。一旦根節(jié)點(diǎn)失效，就要重新選擇根節(jié)點(diǎn)并重新進(jìn)行分級(jí)和同步階段的處理，增加了計(jì)算和能量開銷。另外，TPSN算法沒有對(duì)時(shí)鐘的頻差進(jìn)行估計(jì)，這使得它需要頻繁同步，開銷較大。理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半結(jié)合對(duì)clockskew的估計(jì)，可以提高TPSN的精度TPSN同步誤差的分析HRTS(HierarchyReferencingTimeSynchronizationProtocol)基于雙向報(bào)文交換（如TPSN）的傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議具有同步精度高的優(yōu)點(diǎn)，但一次只能同步一對(duì)節(jié)點(diǎn)。n個(gè)節(jié)點(diǎn)的單跳網(wǎng)絡(luò)則需要n-1次同步操作，同步功耗較大。RBS只需要一次同步過程就可完成一個(gè)單跳網(wǎng)內(nèi)所有節(jié)點(diǎn)間的同步，同步功耗低，當(dāng)然同步精度也相對(duì)變差。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ā)出一個(gè)同步請(qǐng)求報(bào)文，該報(bào)文隨機(jī)指定一個(gè)鄰居節(jié)點(diǎn)（例如n1）作為應(yīng)答者節(jié)點(diǎn)（即對(duì)應(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)文，對(duì)于應(yīng)答者節(jié)點(diǎn)n1來說，只要將其本地時(shí)間減去Δ就達(dá)到與BS節(jié)點(diǎn)的瞬時(shí)同步。對(duì)于其他節(jié)點(diǎn)來說，只要在其本地時(shí)間加上T2?T2'?Δ即可達(dá)到與BS節(jié)點(diǎn)間的瞬時(shí)同步HRTS同步過程

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é)議的特點(diǎn)根節(jié)點(diǎn)和應(yīng)答者節(jié)點(diǎn)本質(zhì)上是采用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（FloodingTimeSynchronizationProtocol）

泛洪時(shí)間同步協(xié)議（FloodingTimeSynchronizationProtocol）由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)，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和根節(jié)點(diǎn)的失效有健壯性，精確度較好。該算法通過采用MAC層時(shí)間戳和線性回歸偏差補(bǔ)償彌補(bǔ)了相關(guān)的錯(cuò)誤源。FTSP（FloodingTimeSynchronizationProtocol）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è)過程，直到整個(gè)網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)都時(shí)間同步。FTSP協(xié)議主要采用下面機(jī)制來降低時(shí)間延遲對(duì)時(shí)間同步精度的影響：在MAC層記錄時(shí)間信標(biāo)，細(xì)分消息傳輸中的時(shí)間延遲并對(duì)這些延遲進(jìn)行補(bǔ)償，利用線性回歸算法估算時(shí)間漂移。FTSP的特點(diǎn)FTSP算法通過對(duì)收發(fā)過程的分析，把時(shí)延進(jìn)一步分為發(fā)送中斷處理時(shí)延、編碼時(shí)延、傳播時(shí)延、解碼時(shí)延、字節(jié)對(duì)齊時(shí)延、接收終端處理時(shí)延，進(jìn)一步降低了時(shí)延的不確定性。通過發(fā)射多個(gè)時(shí)間戳（單個(gè)報(bào)文中包括多個(gè)時(shí)間戳），使得接收節(jié)點(diǎn)可以利用最小方差線性擬合估算自己和發(fā)送節(jié)點(diǎn)的漂移和偏移差。通過良好的根節(jié)點(diǎn)選舉機(jī)制，針對(duì)根節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入以及拓?fù)浣Y(jié)構(gòu)變化等情況進(jìn)行了優(yōu)化，使得算法的健壯性很好，適合于軍事等惡劣應(yīng)用情況。FTSP的特點(diǎn)與典型應(yīng)用FTSP是現(xiàn)有的典型時(shí)間同步協(xié)議中精度最高的同步協(xié)議，并且有良好的健壯性，不會(huì)因?yàn)閭€(gè)別節(jié)點(diǎn)的失效而收到影響。但FTSP基于MAC層時(shí)間戳技術(shù)的細(xì)節(jié)技術(shù)的實(shí)現(xiàn)來提高同步精度，使得FTSP協(xié)議的通用性不強(qiáng)。并且洪泛的方式使得能耗開銷巨大。用于ZigBee網(wǎng)絡(luò)的同步休眠與喚醒算法內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)螢火蟲同步1935年，Science1975年,Peskin的RC模型1989年，M&S模型(未考慮延遲)1998年，Ernst（考慮有延遲）2005年，真實(shí)地實(shí)現(xiàn)簡(jiǎn)單，高效，可擴(kuò)展性強(qiáng)M&S模型研究由初始不同步狀態(tài)如何達(dá)到同步狀態(tài)個(gè)體性質(zhì)相同,因此一旦達(dá)到同步則永遠(yuǎn)同步螢火蟲之間的交互被建模成電量耦合耦合延遲規(guī)定為0最終結(jié)論為:系統(tǒng)的同步收斂性取決于個(gè)體在自由狀態(tài)下的動(dòng)力學(xué)特性同步的實(shí)質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量,相位差通過同步過程不斷縮小，最終達(dá)到完全相同,即同步狀態(tài)Ernst的研究M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時(shí)的情況M&S模型只研究了正耦合的情況，Ernst還研究了負(fù)耦合的情況螢火蟲同步的特點(diǎn)同步可直接在物理層而不需要以報(bào)文的方式實(shí)現(xiàn)。直接用硬件實(shí)現(xiàn)，使得同步精度不會(huì)受到MAC延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影響。由于對(duì)任何同步信號(hào)的處理方式均相同，與同步信號(hào)的來源無關(guān)，因此可擴(kuò)展性以及適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)變化的能力很強(qiáng)。機(jī)制非常簡(jiǎn)單，不需要對(duì)其它節(jié)點(diǎn)的時(shí)間信息進(jìn)行存儲(chǔ)。螢火蟲同步算法的一個(gè)限制是要求每個(gè)節(jié)點(diǎn)具有相似性，但這種機(jī)制在非相似節(jié)點(diǎn)所組成的網(wǎng)絡(luò)下能否起到同步的作用，目前還不清楚。由于螢火蟲同步的理論研究還遠(yuǎn)未結(jié)束，工程實(shí)用性還有待考察。螢火蟲同步技術(shù)的未來發(fā)展螢火蟲同步技術(shù)對(duì)耦合延遲、耦合強(qiáng)度、耦合性質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾?。雖然在如兩個(gè)振蕩器的同步收斂性等研究上取得了一定的進(jìn)展，但無論是理論研究還是仿真研究，研究者在某些結(jié)論上還不能達(dá)成一致的認(rèn)識(shí)。但可以認(rèn)同的一點(diǎn)是：在實(shí)際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會(huì)取得在一定誤差范圍內(nèi)的同步。內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)總結(jié)在無線傳感器網(wǎng)絡(luò)中，時(shí)間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗、可擴(kuò)展性和健壯性需求經(jīng)典的時(shí)間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時(shí)鐘飄移補(bǔ)償、MAC層時(shí)間戳技術(shù)以及雙向報(bào)文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性來降低同步能耗螢火蟲同步側(cè)重于提高可擴(kuò)展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡(luò)的應(yīng)用時(shí)間同步算法分類基于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等?；赑air-Wise（成對(duì)）的時(shí)間同步這種算法利用成對(duì)同步方法進(jìn)行發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)間的時(shí)間同步，然后擴(kuò)展到整個(gè)網(wǎng)絡(luò)形成網(wǎng)絡(luò)的時(shí)間同步。此類算法使得網(wǎng)絡(luò)的同步報(bào)文開銷較大，對(duì)于低開銷要求較高的工業(yè)無線網(wǎng)絡(luò)應(yīng)用有一定的局限性。而且同步階段所用時(shí)間隨節(jié)點(diǎn)數(shù)目的增加而線性增加,不適合對(duì)快速性要求較高的工業(yè)無線網(wǎng)絡(luò)。典型的算法主要有TPSN等。主要參考文獻(xiàn)（詳見原著）[1]ElsonJ.,R?merK..Wirelesssensornetworks:anewregimefortimesynchronization.ACMSIGCOMMComputerCommunicationReview,2003,33(1):149-154.[3]ElsonJ.,GirodL.,EstrinD..Fine-grainedtimesynchronizationusingreferencebroadcasts.In:Proc.5thSymposiumonOperationSystemDesignandImplementation,Boston,2002,147-163.[4]GaneriwalS.,KumarR.,SrivastavaM..