免時間戳交互的無線傳感網隱含節點同步參數估計算法

王恒 彭政岑 馬文巧 李敏

無線傳感網(Wireless sensor networks,WSNs)由負責感知和傳輸任務的傳感器節點組成,具有功耗低、成本小、易部署的優勢,被廣泛應用于環境監控、工業控制等領域[1-3].時間同步是無線傳感網的關鍵技術之一.無線傳感網的許多基礎功能,例如數據融合、傳輸調度和目標定位等,都需要節點間的精確時間同步[4-6].因此,對無線傳感網中的時間同步技術進行研究和探索具有重要意義.

由于時鐘的啟動時刻和振蕩器的變化特性不同,傳感器節點時鐘之間通常存在兩方面的偏差.一方面是時鐘的初始相位偏差,稱之為時鐘偏移;另一方面是時鐘運行速率的偏差,稱之為時鐘漂移.無線傳感網中的節點之間要維持高精度同步,就需要利用時間同步技術計算相對時鐘漂移和偏移.如果僅對時鐘漂移進行估計,那么只能校正節點之間的時鐘速率偏差,而相位偏差會一直存在,導致同步無法實現.反之,若只估計時鐘偏移,雖然能夠校正相位偏差,但是振蕩器的差異會導致同步時間較短,從而需要頻繁地進行重同步.因此,為了避免上述情況的出現,就必須對時鐘漂移和偏移參數進行聯合估計.

無線傳感網時間同步機制的設計所面臨的一項重要挑戰是:如何盡可能地減少同步能耗.由于網絡中節點間的同步通常需要傳輸同步信息,而同步信息傳輸所需能耗占據同步能耗的絕大部分.因此,一個有效的解決方案是設計以最小化同步信息傳輸數量為目標的低功耗同步協議.隱含同步是其中的一個典型協議[7],它基于無線媒介的廣播特性,利用監聽策略隱式地獲取同步信息,可以顯著減少同步信息傳輸數量.在該機制中,一個活躍節點(既發送同步信息又接收同步信息)和一個時鐘源節點之間執行雙向信息交換同步操作,而一些位于這兩個節點重疊通信范圍內的節點(稱之為隱含節點),只需監聽它們之間的信息交換過程就能實現與時鐘源節點的同步.在此過程中,隱含節點僅接收了信息,沒有發送任何信息,大幅度地降低了同步能耗.文獻[7-9]基于隱含同步機制,在不同的網絡場景下,利用統計信號處理技術設計了多種同步算法,實現節點之間的高精度低能耗同步.文獻[10-11]則將隱含同步機制與另一種同步機制(校正式同步)相結合,節點僅以少量的能量就能在估計時鐘參數的同時校正自己的本地時鐘,實現實時的同步.此外,文獻[12]還將隱含同步機制應用到了水下無線傳感網中,提出適用于水下傳感器節點的低功耗同步算法.

免時間戳同步是近年來提出的另一種低能耗的同步機制[13-16].由于其交互過程無需時間戳,同步功能可以無縫嵌入現有網絡數據流,從而能夠顯著減少能耗.在免時間戳同步中,首先活躍節點發送不含時間戳的數據包給時鐘源節點,并記錄此時的本地時間;接著時鐘源節點接收到數據包后在預定義的響應時間間隔返回不含時間戳的數據包;最后活躍節點在接收到返回的數據包后記錄自己的本地時間,并通過預定義的響應時間間隔規則估計時鐘參數,與時鐘源節點達到同步.該機制利用接收方對發送方的預定義響應時間來傳遞同步信息,避免了專用同步幀的傳輸.文獻[13]提出一種基于和響應策略的免時間戳同步協議,其中時鐘源節點響應時間和接收時間的和滿足特定的規則.通過在兩個不同的時間間隔各返回一個響應數據包,文獻[14]提出一種跟隨響應免時間戳同步協議.但是,由于跟隨響應數據包的存在,限制了該協議在實際網絡中的應用.為解決上述問題,文獻[15]提出一種基于動態響應的免時間戳同步協議,利用特定的映射規則,將連續的兩個或多個同步周期的響應時間設置為不同值,消除了跟隨響應數據包的傳輸.進一步,文獻[16]提出一種免時間戳交互與單向傳輸混合的同步機制,實現了時鐘漂移和偏移的聯合估計.

將免時間戳同步與隱含同步相結合,能夠聯合發揮兩種同步機制的低能耗優勢,從而進一步降低無線傳感網同步能耗開銷.文獻[15]對其進行了初步的研究,但是,在基于動態響應的免時間戳同步方法中,隱含節點只能估計時鐘漂移,不能估計時鐘偏移,從而無法實現隱含節點的完全同步.因此,針對此問題,本文提出了一種在不傳遞時間戳的情況下,隱含節點能夠聯合估計時鐘漂移和偏移的低功耗同步協議.主要貢獻如下:

1)提出了一種基于免時間戳交互的隱含同步協議,隱含節點記錄監聽到數據包的本地時間戳,再結合預定義的響應規則就能完成對時鐘漂移和偏移的聯合估計,以少量的能耗達到與時鐘源節點的完全同步;

2)針對典型的高斯隨機時延,推導了隱含節點時鐘漂移和偏移的聯合最大似然估計器(Maximum likelihood estimator,MLE),以及相應的克拉美羅下限(Cramer-Rao lower bound,CRLB);

3)仿真結果表明,所提估計算法能夠有效實現對隱含節點時鐘漂移和偏移參數的免時間戳聯合估計,并具有達到CRLB的優良性能.

1 同步協議描述

本節將對所提的基于免時間戳交互的隱含同步協議進行介紹,并建立節點的時鐘模型.

1.1 交互過程

考慮一個由多個節點構成的無線傳感網,其中節點O是時鐘源節點,為網絡提供參考時間;節點P是活躍節點,周期性地與時鐘源節點O進行雙向信息交互;節點Q是位于活躍節點P與時鐘源節點O公共廣播領域內的隱含節點,能夠監聽它們之間的信息交互過程,如圖1 所示.

圖1 網絡結構圖Fig.1 Network structure

當網絡同步開始,活躍節點P與時鐘源節點O之間進行免時間戳同步,隱含節點Q監聽兩節點的交互信息進行隱含同步.具體的同步過程如圖2 所示,以第j輪通信過程為例,詳細步驟如下.

圖2 節點 Q 監聽節點 O 與節點 P 之間的N輪免時間戳交互Fig.2 The N rounds of timestamp-free exchange between node O and P with node Q overhearing them

在上述過程中,活躍節點P與時鐘源節點O之間進行免時間戳同步,隱含節點Q監聽它們之間的成對信息.因此,節點Q只接收了信息,節省了由發送報文產生的能耗.

1.2 時鐘模型

網絡中每個傳感器節點的時鐘相對于理想時間都存在時鐘漂移和偏移.其時鐘模型可以表示為:

其中,C(t0)和t0分別表示節點的本地時間和理想時間,α和?分別表示時鐘漂移和偏移.

同步信息在傳輸過程中會經歷多種時延,這些時延可分為固定時延和隨機時延[17].其中固定時延包括傳輸時間、接收時間、傳播時間,隨機時延包括發送時間、接收處理時間和信道訪問時間.一般情況下,固定時延被假設為一個常數,而隨機時延則會根據不同的網絡場景被建模為服從不同分布的隨機變量.例如,延遲是由許多獨立的隨機過程相互疊加時,根據中心極限定理,隨機時延可以被建模為高斯分布[18].此外,該隨機時延模型已被實驗證明是合理的[19].因此,在本文中,假設固定時延是已知常數,隨機時延是獨立同分布的高斯分布,其均值為0,方差為σ2.

根據時鐘模型式(2),時鐘源節點O在j輪同步信息交換過程中,本地時間戳可以表示為:

2 參數估計

基于上述的時間戳表達式,本節將推導隱含節點時鐘漂移和偏移的聯合MLE 以及相應的CRLB.

2.1 聯合MLE

最大似然估計是一種能夠簡便地實現復雜估計問題求解的估計方法,其是利用已知的觀測數據,反推最大概率產生該觀測信息的參數值.無線傳感網中的時間同步就是通過觀測的同步信息計算時鐘參數.此外,在式(13)中,Γ 是由已知觀測數據構成的矢量矩陣;M是秩為2的觀測矩陣; Θ 是包含2個待估時鐘參數的矢量,并且與Γ呈線性關系;W是均值為0,方差為的高斯噪聲矢量,其中 1 是單位矩陣,滿足線性模型的最大似然估計定理.因此,根據文獻[20]中的定理7.5,時鐘參數矢量 Θ的MLE 為:

將式(14)進行數學運算,節點Q時鐘漂移和偏移的最大似然估計器分別表示為:

所以,利用估計器(15),隱含節點Q可以估計自身的時鐘漂移和偏移,達到與時鐘源節點O的同步.與現有的免時間戳同步與隱含同步相結合的同步機制相比,本文所提的同步機制完成了對隱含節點完整時鐘參數(時鐘漂移和偏移)的估計,實現了與時鐘源節點的完全時間同步.

2.2 克拉美羅下限(CRLB)

CRLB 是衡量無偏估計器性能的一個理論標準[20],無偏估計量的方差只能無限逼近或等于CRLB,而不會小于CRLB,當兩者相等時,表示估計器性能達到最優.由于它容易被確定,常被用來評估無偏估計器性能的好壞,判斷估計器性能是否達到了最優.為了評估所提聯合MLE的性能,本節推導矢量參數的CRLB.首先需要計算2×2的費希爾信息矩陣,然后再求其逆矩陣可分別得到的CRLB.

再對式(17)～式(19)求負期望可得費希爾信息矩陣如下:

最后,求得費希爾信息矩陣的逆矩陣為:

費希爾信息矩陣的逆矩陣的對角元素即為相應參數的CRLB[20].因此,時鐘漂移α(QO)和時鐘偏移?(QO)的CRLB 分別表示為:

3 仿真驗證與對比分析

本節基于MATLAB 仿真平臺,驗證所提隱含節點的聯合最大似然估計器的有效性.同時,在估計性能、能量開銷、計算數量三個方面,將所提同步機制與現有的相關同步機制進行了對比.

3.1 仿真驗證

圖3 為隱含節點Q相對于時鐘源節點O的時鐘漂移最大似然估計器的MSE 和CRLB.從圖中可以看出,時鐘漂移最大似然估計器的MSE 曲線與CRLB 曲線基本重合,表明了其估計性能達到最優,同時也驗證了估計器的有效性.而且隨著觀測次數的增加,所提估計器的估計精度不斷提高.

圖3 隱含節點 Q 時鐘漂移估計 (QO)的MSE 與CRLBFig.3 MSE and CRLB of estimated clock skew(QO)for silent nodeQ

圖4 所示為隱含節點Q相對于時鐘源節點O的時鐘偏移最大似然估計器的仿真結果.在圖4 中,時鐘偏移最大似然估計器的性能隨著觀測次數的增加不斷提高,而且MSE 曲線與CRLB 曲線基本重合,表明該估計器的性能達到了最優,同時驗證了該估計器的有效性.值得注意的是,在仿真中,系數ξ=1.4,這表明隱含節點Q在通信過程中只是獲取到2/5的就以此實現了相對于時鐘源節點O的時鐘偏移估計.此外,時鐘偏移的估計精度是影響同步精度的主要因素.因為隱含節點Q根據估計的時鐘漂移與偏移調整本地時間,減小與時鐘源節點O的時間偏差,而時鐘漂移的估計精度比時鐘偏移的估計精度高出約 1 06個數量級,其對同步精度的影響較小,可以忽略不計.所以可以利用時鐘偏移的估計精度反映節點間的同步精度.從圖4 中可以看出,時鐘偏移的估計精度為 1 0-1數量級,而時鐘偏移被設置為數ms,因此,所提同步算法可達到數百μs的同步精度.

圖4 隱含節點 Q 時鐘偏移估計 (QO)的MSE 與CRLBFig.4 MSE and CRLB of estimated clock offset(QO)for silent nodeQ

從仿真結果可以看出,隱含節點Q監聽活躍節點P和時鐘源節點O之間的免時間戳同步過程,通過觀測到的數據集就可以同時估計相對于節點O的時鐘漂移和偏移,達到與節點O的同步.與文獻[15]中的基于動態響應的免時間戳的隱含同步方式相比,所提的免時間戳隱含同步方法繼承了現有免時間戳同步和隱含同步的優勢,能夠大幅度地減少同步能量消耗,同時也可以無縫地嵌入到網絡數據流之中.進一步,隱含節點又能夠聯合估計相對于時鐘源節點的時鐘漂移和偏移,實現隱含節點的完全同步,彌補了目前兩種機制結合使用的不足.

3.2 對比分析

首先,將所提的隱含節點Q的時鐘漂移最大似然估計器與類似的估計器(文獻[15]中的式(26))進行估計性能比較.為了確保比較的公平性,在兩種估計器的對比仿真中,各個參數的初始化設置均相同,文獻[15]中兩個連續周期內ACK的響應時間間隔設置為{10,30}.仿真結果如圖3 所示,本文所提的隱含節點Q的時鐘漂移估計器的性能顯著優于文獻[15]中的時鐘漂移估計器,而且其估計精度大約高出101～103個數量級.其原因是所提同步機制通過預設時鐘源節點O返回ACK的本地時間,傳遞了部分時間戳信息給隱含節點Q,時間戳信息的獲取有利于時鐘漂移估計精度的提高.圖5 所示為不同系數ξ下時鐘漂移估計器性能對比結果,其中設置ξ={1.2,1.3,1.4,1.5,1.6}.從圖中可以看出,隨著系數ξ的增大,所提時鐘漂移估計器的估計性能不斷提高,表明隱含節點Q獲取的時間戳信息越多,時鐘漂移的估計效果越好.同時,從仿真的角度說明,相較于文獻[15]中無法獲取時間戳信息的隱含節點,所提同步機制的隱含節點由于能夠間接地獲取部分時間戳信息,因此其時鐘漂移估計器性能更優.但是,需要注意的是,不能為了提高時鐘漂移的估計性能無限地增加ξ,因為ξ的取值必須確保響應時間間隔不會過大,影響網絡的正常運行.

圖5 不同系數 ξ 下時鐘漂移估計器性能對比結果Fig.5 The performance comparison results of clock skew estimator under different coefficientξ

其次,將所提同步機制與隱含同步機制[7]、基于動態響應的免時間戳同步機制[15]進行信令流程及能耗開銷對比.無線傳感網的時間同步依賴于信息交互,交互流程所導致的能耗開銷是影響同步能耗的重要因素.在隱含同步機制中,隱含節點監聽的是傳統的雙向信息交互過程,需要專用的同步幀傳遞時間戳信息,同步幀的傳輸需要消耗額外的能量.在基于動態響應的免時間戳同步機制中,待同步節點無需發送時間戳信息,在普通數據收發中實現同步,無需消耗額外的能量.在所提機制中,隱含節點監聽的是時鐘源節點和活躍節點的免時間戳交互過程,不需要專用同步幀,沒有額外的能量開銷.因此,相較于隱含同步機制,所提機制避免了網絡中專用同步幀傳輸,顯著減少了能耗.與免時間戳機制相比,所提機制能夠一次性實現公共廣播領域內多個節點的同步,而免時間戳機制只能實現一個節點的同步,對于網絡整體的能耗而言,所提機制更具優勢.

最后,分析所提同步算法、隱含同步算法[7]、基于動態響應的免時間戳同步算法[15]以及免時間戳與隱含同步結合算法[15]的計算復雜度,主要是對算法中加法和減法、乘法和除法計算數量進行比較,對比結果如表1 所示.從表中可以看出,4 種同步算法時鐘參數的計算復雜度均為 O (N2).而本文算法時鐘參數乘除法的計算數量高于隱含同步算法和免時間戳同步算法時鐘參數計算數量,這是因為時鐘源節點O返回ACK的本地時間中包含系數ξ,導致算法中乘除法的數量相對較高.Wang等[16]研究表明,傳輸1 比特數據超過100 米消耗的能量與執行300 萬條指令所需能量大致相等.因此,雖然本文算法的計算數量略高,但能夠在不傳輸專用同步幀的情況下實現多個節點的同步,它仍然是一個高能效的同步方案.相較于文獻[15]中的免時間戳與隱含同步結合算法,本文算法時鐘漂移的計算復雜度略低于其時鐘漂移計算復雜度,而且本文算法還可以估計時鐘偏移,實現完整的同步.

表1 本文算法與隱含同步算法、免時間戳同步算法以及免時間戳和隱含同步結合算法的計算數量對比結果Table 1 The comparison results of the number of calculations among proposed algorithm,implicit synchronization algorithm,timestamp-free synchronization algorithm and combination algorithm of timestamp-free and implicit synchronization

4 結論

本文提出了一種能夠聯合估計免時間戳同步場景中隱含節點的時鐘漂移和偏移的同步協議.在高斯隨機時延下,推導了隱含節點時鐘漂移和偏移的最大似然估計器和相應的CRLB.最后,通過數值仿真驗證了所提估計器的有效性,并且與現有的相關同步方案在估計性能、能量開銷和計算數量三個方面進行了對比,論證了所提方案低功耗的優勢.