基於誤差統計的無線傳感器網絡時間同步方法及裝置的製作方法
2023-06-26 11:50:16
專利名稱：基於誤差統計的無線傳感器網絡時間同步方法及裝置的製作方法
技術領域：
本發明涉及在無線傳感器網絡中的時間同步技術，尤其是一種基於誤差統計的無線傳感器網絡時間同步方法及裝置。
背景技術：
無線傳感器網絡是由大量傳感器節點以自組織方式構成的多跳無線網絡系統，其目的是協同地感知、採集、處理和傳輸網絡覆蓋區域內感知對象的監測信息，並報告給用戶。無線傳感器網絡融合了傳感技術、嵌入式技術、無線網絡技術、分布式智能信息處理等技術，具有規模大、成本低、組網靈活等特點，已經廣泛應用於軍事、科研、工業監控、醫療等領域。
時間同步是無線傳感器網絡的基本功能之一，對於提高無線傳感器網絡的整體性能具有重要意義。如在目標跟蹤系統中，多個傳感器節點協同工作來完成對目標運動速度和運動軌跡的監測，這需要節點之間保持時間的一致，通過交換各自的監測信息，根據信息中的時間先後關係，來對目標的運動速度、方向和軌跡等進行計算。例如，在停車場車位管理系統中，無線傳感器網絡作為數據收集型網絡，傳感器節點需要定期地採集數據，並傳送給匯聚節點進行處理，傳感器節點需要保持時間的一致性，才能保證所有節點同時對數據進行採集。
在已知的現有技術中，無線傳感器網絡中的時間同步方法主要包括RBS(ReferenceBroadcast Synchronization)參考廣播同步方法，DMTS(Delay Measurement TimeSynchronization)延遲測量時間同步方法和TPSN(Timing-sync Protocol for SensorNetworks)時間同步方法。這幾種方法都從不同的角度入手，通過減少消息傳播關鍵路徑上的傳播延遲引入的誤差來提高時間同步精度，具有各自的優缺點。RBS時間同步方法中雖然消除了發送端傳播延遲引入的同步誤差，提高了同步精度，但是這種方法只適用於小規模的網絡，擴展性差，交換消息數量多；DMTS時間同步方法複雜度低，容易擴展到大規模的網絡，但對消息傳播延遲的補償是一個固定值，不能適應網絡部署情況的變動，同步精度相對較低；TPSN時間同步方法將NTP時間同步方法引入到無線傳感器網絡中，取得了比較好的精度，但是同步過程複雜度相對較大，交換的消息數量多，收斂速度慢。具體而言，上述方法對傳播延遲引入的誤差的估計，不能實際反映出網絡的整體延遲情況。
發明內容
針對以上問題，本發明的目的在於提供一種基於誤差統計的無線傳感器網絡時間同步方法(An Error Statistic Based Time Synchronization Protocol)，簡稱ESTS，以及用於實現該方法的裝置。
基於誤差統計的無線傳感器網絡時間同步方法中，通過動態均勻地抽取網絡邊緣節點作為延遲統計節點，對同步過程中消息的傳播延遲進行實際測量，客觀地反映了網絡實際的部署情況和傳播延遲，並通過洪泛過程對由此而引起的同步誤差進行補償。這種方法具有良好的自適應性、可擴展性和較高的同步精度，在同步精度和能量消耗之間取得了很好的折中。
基於誤差統計的無線傳感器網絡時間同步方法包括以下步驟1)利用同步命令消息的洪泛過程在短時間內達到網絡低精度時間同步，同時建立網絡樹狀層次結構；2)利用洪泛消息傳播的單向性，根據網絡的實際部署情況，動態均勻地選取部分網絡邊緣節點作為延遲統計節點；3)延遲統計節點利用網絡樹狀層次結構，通過向匯聚節點發送延遲統計消息，統計同步命令消息從匯聚節點到延遲統計節點、以及延遲統計消息從延遲統計節點到匯聚節點路徑上的傳播延遲；4)根據收到的延遲統計消息，匯聚節點計算網絡平均每跳傳播延遲；5)利用延遲補償消息的洪泛過程，節點根據網絡平均每跳傳播延遲和距離匯聚節點的跳數，對同步精度進行補償，達到網絡高精度時間同步。
根據本發明的另一目的，用於實現上述方法的裝置即無線傳感器網絡的結構示意圖如圖1所示。無線傳感器網絡通常包括匯聚節點和傳感器節點，傳感器節點負責採集各種感知數據，轉發其它節點採集的數據；匯聚節點負責收集傳感器節點採集的數據。網絡中通常只有一個匯聚節點，其它節點均為傳感器節點。這些節點在同步過程中被組織成樹狀的層次結構，以匯聚節點為根節點。
其中，匯聚節點包括消息的發送和接收模塊、系統時間模塊、時間戳模塊、時間同步的啟動模塊、計算網絡平均每跳延遲的模塊和誤差補償的啟動模塊。各模塊間的關係如圖6所示。
消息的發送和接收模塊負責發送和接收各種同步消息；系統時間模塊維持節點的本地時鐘；時間戳模塊為各種同步消息添加時間信息，時間戳模塊通過系統時間模塊獲取消息發送時的系統時間。
時間同步的啟動模塊通過發送同步命令消息啟動網絡的同步過程，消息中含有匯聚節點的節點編號和延遲累計欄位，通過消息的發送和接收模塊發送給接收節點，並在消息的發送和接收模塊發送消息時，由時間戳模塊為消息添加時間信息。
計算網絡平均每跳延遲的模塊通過消息的發送和接收模塊接收延遲統計節點發送來的延遲統計消息，根據消息中的延遲統計欄位和消息經過的跳數計算消息的平均每跳傳播延遲。
誤差補償的啟動模塊通過消息的發送和接收模塊向網絡中洪泛延遲補償消息，延遲補償消息中含有網絡的平均每跳傳播延遲，啟動誤差補償過程。
傳感器節點包括消息的發送和接收模塊、系統時間模塊、時間戳模塊、時間同步模塊、網絡平均每跳延遲的統計模塊、同步精度的補償模塊和定時器模塊。各模塊間的關係如圖7所示。
消息的發送和接收模塊實現發送和接收各種同步消息的功能；系統時間模塊維持節點的本地時鐘；時間戳模塊為各種同步消息添加時間信息，時間戳模塊通過系統時間模塊獲取消息發送時的系統時間。
時間同步模塊接收同步命令消息，根據同步命令消息中的時間戳信息，調整節點的本地時間，完成同消息發送節點的時間同步；同時將消息的發送節點作為自己的父節點，記錄距離匯聚節點的跳數，計算同步命令消息中的延遲累計欄位；然後再通過消息的發送接收模塊轉發出去。
定時器模塊用於協助判斷節點是否是延遲統計節點，節點在通過消息發送和接收模塊轉發同步命令消息後，啟動定時器；如果定時器超時前收到了其它節點轉發的同步命令消息，則節點不是延遲統計節點，否則節點是延遲統計節點。
網絡平均每跳延遲的統計模塊用於處理和轉發延遲統計消息，延遲統計消息中含有路徑上的累計延遲和所經過的跳數；如果節點是延遲統計節點，則節點通過消息的發送和接收模塊向父節點發送延遲統計消息；如果節點不是延遲統計節點，節點在收到延遲統計消息後，會按照方法中所述的方式計算延遲累計欄位，將跳數欄位加一，然後通過消息的發送和接收模塊發送給自己的父節點。
同步精度的補償模塊用於接收和轉發誤差補償消息，對自己的同步精度進行補償；節點收到誤差補償消息後，會根據自己距離匯聚節點的跳數和消息中的網絡平均每跳延遲對自己的同步精度進行補償；然後再通過消息的發送和接收模塊將消息轉發出去。
本發明的技術效果在於通過洪泛的方式，使網絡在短時間內達到低精度的時間同步，並建立網絡的樹狀層次結構；通過動態均勻地抽取網絡邊緣節點作為延遲統計節點，對同步過程中消息的傳播延遲進行實際測量，客觀的反映了網絡中的傳播延遲，通過洪泛誤差補償消息對傳播延遲引入的同步誤差進行補償，大大提高了時間同步的精度。這種方法具有良好的自適應性、可擴展性和較高的同步精度，在同步精度和能量消耗之間取得了很好的折中。
圖1無線傳感器網絡拓撲示意2時間同步方法流程3時間同步命令消息格式圖4延遲統計節點的選取示意5延遲統計原理示意6匯聚節點裝置的模塊關係7傳感器節點裝置的模塊關係8實驗--時間同步過程示意9實驗--廣播時間查詢消息示意圖具體實施方案下面參照附圖並結合實施例對本發明進行詳細的描述。
ESTS時間同步方法的流程如圖2所示，匯聚節點通過其時間同步的啟動模塊廣播同步命令消息、啟動時間同步過程。同步命令的消息格式如圖3所示，其中，hop代表發送該消息的節點距離匯聚節點的跳數；nodeId是發送該消息的節點編號；sendTimeStamp是發送該消息時加入的時間戳，表示發送該消息指定字節時節點的本地時間；delay記錄同步過程中的傳播累積延遲，初始化為0；匯聚節點的鄰居節點(傳感器節點)收到同步命令消息後，節點首先記錄收到該消息的時間，稱為接收時間戳receiveTimeStamp，該時間戳是節點接收消息指定字節時讀取的本地系統時間，記錄hop欄位+1作為距離匯聚節點的跳數，記錄消息中的nodeId作為自己的父節點。然後節點按照公式1調整本地系統時間，實現與匯聚節點之間的時間同步，其中Tcurrent是節點的本地時間。同步完成後，節點轉發該同步命令消息，nodeId欄位設置為自身的節點編號，hop欄位設置為自己距離匯聚節點的跳數，並在MAC層發送時為消息添加sendTimeStamp欄位。
Tcurrent＝Tcurrent+(sendTimeStamp-receiveTimeStamp)公式1
距離匯聚節點兩跳的節點收到同步命令消息後，進行類似的處理。依此類推，同步命令消息逐步在網絡中傳播，最後達到整個網絡的時間同步。節點只對收到的第一個同步命令消息進行處理，隨著同步消息在網絡中的傳播，網絡中每個節點都會與父節點同步，根據記錄的父節點的編號和距離匯聚節點的跳數，在低精度時間同步的同時建立網絡的樹狀層次關係。
上述過程中，同步命令消息以洪泛方式從匯聚節點向網絡邊緣傳播，由於節點僅對收到的第一個同步命令消息進行處理並轉發，同步命令消息以類似於同心圓的形式向網絡邊緣擴散，最後消息到達網絡的邊緣並停止傳播。在網絡邊緣上，總會有這樣的一些節點，它們是鄰近區域內最後收到同步消息的節點。如圖4所示，標有N0的節點是網絡中不同區域內最後收到同步消息的節點。這些節點會比較均勻的分布在網絡的邊緣，選取這些邊緣節點作為N0進行延遲統計，能夠比較客觀地反映出網絡中的延遲情況。如果N0節點的數量太大，可以以一定的概率捨棄一些節點，這樣能夠避免在統計網絡平均延遲時產生過多的通信開銷。
實現過程中使用定時器，節點在收到第一個同步命令消息後，節點會首先進行同步，然後轉發該同步命令消息。節點在轉發該消息後，啟動一個定時器，如果在定時器超時的時候沒有收到其它節點轉發的同步命令消息，則節點認為自己是網絡邊緣節點；如果在超時前收到了同步命令消息，則認為自己不是網絡邊緣節點。
延遲統計節點通過向匯聚節點發送延遲統計消息完成延遲統計過程。延遲統計過程如圖5所示，假設一個消息從匯聚節點出發，沿著匯聚節點-N1-N2-…-Nn-1-N0路逕到達N0節點，此後該消息又沿著相反的路徑傳回到匯聚節點。假設消息在Trs時刻(匯聚節點的本地時間)從匯聚節點發送出去，在T1r時刻(N1節點的本地時間)N1節點收到了該消息，在T1s時刻(N1節點的本地時間)N1節點將消息轉發給N2節點。N0節點在T0r時刻(N0節點的本地時刻)收到該消息，然後在T0s時刻(N0節點的本地時刻)將消息轉發給Nn-1節點，依次類推，最後消息在T』rr時刻(匯聚節點的本地時間)回到匯聚節點。
T』rr-Trs是消息從離開匯聚節點，到重新回到匯聚節點所經歷的時間，即消息在網絡中傳播的時間。Δti＝Tis-Tir和Δti′＝Tis′-Tir′(i＝1，2，…n-1)分別是消息在第i個節點兩次停留的時間，即第i個節點在收到消息，到發送該消息所經歷的時間。假設τ是兩個節點之間的傳播延遲，則有下列公式，通過公式2可以解得網絡中的每跳平均延遲τ。
Trr=Trs++t1++t2+++t0+++t2++t1+]]>=Trs+2n+(i=1n-1ti+t0+i=1n-1ti)]]>公式2
=(Trr-Trs)-[i=1n-1(Tis-Tir)+(T0s-T0r)+i=1n-1(Tis-Tir)]2n]]>公式3延遲的統計過程在快速同步階段就已經開始，同步命令消息中的delay欄位就是用於延遲的統計。匯聚節點在廣播同步命令消息時，將delay欄位初始化為0；如圖5所示，節點N1在收到同步命令消息後，首先完成節點同步，然後計算ΔT1＝T1r-Trs，將結果累加到delay欄位；並廣播給下一跳節點，下一跳節點在收到同步命令消息時也作類似的處理。
當消息傳輸到N0節點，N0節點是通過上述延遲統計節點的選取過程選出的節點。N0節點的定時器超時的時侯，沒有收到其它節點轉發的同步命令消息，N0節點將發起延遲統計過程，N0節點向自己的父節點發送延遲統計消息，格式類似於同步命令消息，消息中包括已有的延遲和N0節點距離匯聚節點的跳數；父節點收到該消息後，將消息中的跳數欄位加1，delay欄位的處理與快速同步階段相同，然後再轉發給自己的父節點；消息逐跳的向匯聚節點傳輸，最後到達匯聚節點，並作相應的處理。此時消息中的delay欄位中含有整個過程中的消息傳播延遲，跳數欄位含有消息經過的總跳數，據此計算網絡平均每跳傳播延遲。
匯聚節點在收到一定數目的延遲統計消息後計算整個網絡的平均每跳延遲。然後匯聚節點廣播延遲補償消息，消息中包含網絡平均每跳延遲。每個節點在收到延遲補償消息後，根據自己距離匯聚節點的跳數hop和網絡平均每跳延遲error對自己的時鐘進行如下校正Tcorrected＝Tcurrent+hop×error，其中，Tcurrent是節點的當前時間，Tcorrected是校正後的時間。然後廣播轉發誤差補償消息，節點僅對收到的第一個誤差補償消息進行處理。
為了更好地對本發明的優勢進行描述，我們使用Mica2節點，在TinyOS作業系統下對ESTS方法進行了實現，對同步精度進行了實際的網絡測量，並與已有的同步方法進行了比較。
精度測量利用了無線信道的廣播特性，在一跳的通信範圍內的多個節點，如果其中一個節點廣播消息，其它節點幾乎會在同一時間收到該消息。通過比較每個節點收到廣播消息的時間，可以比較節點之間的時間偏差。在試驗中將所有節點放置在一跳通信範圍之內，通過指定同步消息的傳播路徑來達到多跳網絡的效果。設置一個輔助節點，進行節點同步精度測量，在網絡完成時間同步後廣播一個消息，然後逐一查詢網絡中每個節點收到該消息的時間，每個節點收到消息的時間同匯聚節點收到消息的時間相比較，就是網絡中節點的同步誤差。
如圖8所示，實驗中使用8個節點組成一個7跳的網絡，匯聚節點編號為0，其它節點根據距離匯聚節點的遠近依次為1號，2號，…，7號節點。所有節點都放在一跳的通信範圍內，但是每個節點僅同自己相鄰的節點通信(編號比自己小1的和編號比自己大1的，0號節點僅與1號節點通信，7號節點僅與6號節點通信)。匯聚節點發起時間同步過程，同步消息從匯聚節點依次廣播到7號節點，如圖8中標有①的過程。延遲統計消息從7號節點沿著相反的路徑回到匯聚節點，如圖8中標有②的過程。
當匯聚節點收到1號節點傳上來的延遲統計消息後，匯聚節點不再廣播誤差補償消息，而是向輔助節點發送請求，請求消息中含有網絡平均每跳傳播延遲，圖8中標有③的過程。輔助節點收到請求消息後，廣播時間查詢消息。0～7號節點收到該消息時，記錄收到該消息的接收時間戳，如圖9中所示。
輔助節點發送廣播消息後，依次查詢0～7號節點記錄的接收時間戳。輔助節點首先對查詢的1～7號節點的接收時間戳進行補償，在每個節點的接收時間戳上加上平均每跳傳播延遲與節點距離匯聚節點的跳數之積，然後減去匯聚節點的接收時間戳，就是每個節點同匯聚節點之間的同步誤差。
試驗共進行了12次，單跳平均同步精度是7.56μs。我們對現有的時間同步方法和ESTS時間同步方法從3個方面進行了比較單跳平均同步精度、收斂速度和同步過程中的能量消耗。從表1中可以看到ESTS時間同步方法的單跳平均同步精度為7.56μs，收斂速度較快。能量消耗是通過同步過程中交換的消息數量來衡量，ESTS在時間同步過程中的能量消耗比較距常，沒有過多的能量開銷。
表1時間同步方法性能對比其中，表1中的RBS、DMTS、TPSN的各項數據分別來自以下文獻[1].J.Elson，L Girod，and D.Estrin.Fine-Grained Network Time Synchronization usingReference Broadcasts.Proc.Fifth Symposium on Operating Systems Design andImplementation(OSDI2002)，Vol 36，pp.147-163，2002. .Ping S.Delay measurement time synchronization for wireless sensor networks.IntelResearch Berkeley lab，June 2003.Http://www.intel research.net/publication/Berkely/081120031327 137.pdf .Ganeriwal S，Kumar R，Srivastava M B.Timing-sync protocol for sensor networks.InProc1st Int』l Conf on Embedded Networked Sensor Systems(SenSys 2003)，Los Angels，CA.November 5-7，2003.138～149。
權利要求
1.一種基於誤差統計的無線傳感器網絡時間同步方法，包括如下步驟1)利用同步命令消息的洪泛過程在短時間內達到網絡低精度時間同步，同時建立網絡樹狀層次結構；2)利用洪泛消息傳播的單向性，根據網絡的實際部署情況，動態選取部分或全部網絡邊緣節點作為延遲統計節點；3)延遲統計節點利用網絡樹狀層次結構，通過向匯聚節點發送延遲統計消息，統計同步命令消息從匯聚節點到延遲統計節點、以及延遲統計消息從延遲統計節點到匯聚節點路徑上的傳播延遲；4)根據收到的延遲統計消息，匯聚節點計算網絡平均每跳傳播延遲；5)利用延遲補償消息的洪泛過程，節點根據網絡平均每跳傳播延遲和距離匯聚節點的跳數，對同步精度進行補償，達到網絡高精度時間同步。
2.如權利要求1所述的方法，其特徵在於，所述的同步命令消息包括以下信息發送該消息的節點距離匯聚節點的跳數、發送該消息的節點編號、發送該消息指定字節時節點的本地時間、同步過程中的傳播累積延遲。
3.如權利要求1所述的方法，其特徵在於，所述的網絡邊緣節點是這樣確定的傳感器節點僅對收到的第一個同步命令消息進行處理並轉發，在轉發該消息後，啟動一個定時器，如果在定時器超時的時候沒有收到其它節點轉發的同步命令消息，則認為自己是網絡邊緣節點。
4.一種基於誤差統計的無線傳感器網絡，包括匯聚節點和傳感器節點，網絡中所有的節點以匯聚節點為根節點組成樹狀結構，其中，傳感器節點用於採集各種感知數據、轉發其它節點採集的數據；匯聚節點用於收集傳感器節點採集的數據。
5.如權利要求4所述的無線傳感器網絡，其特徵在於，所述的匯聚節點包括以下功能模塊消息的發送和接收模塊，用於發送和接收各種同步消息；系統時間模塊，用於維持節點的本地時鐘；時間戳模塊，用於為各種同步消息添加時間信息，所述的時間戳模塊通過系統時間模塊獲取消息發送時的系統時間；時間同步的啟動模塊，用於通過發送同步命令消息啟動網絡的同步過程；計算網絡平均每跳延遲的模塊，用於通過消息的發送和接收模塊接收延遲統計節點發送來的延遲統計消息，根據消息中的延遲統計欄位和消息經過的跳數計算消息的平均每跳傳播延遲；誤差補償的啟動模塊，用於通過消息的發送和接收模塊向網絡中洪泛延遲補償消息，延遲補償消息中含有網絡的平均每跳傳播延遲，啟動誤差補償過程。
6.如權利要求4所述的無線傳感器網絡，其特徵在於，所述的傳感器節點包括以下功能模塊消息的發送和接收模塊，用於發送和接收各種同步消息；系統時間模塊，用於維持節點的本地時鐘；時間戳模塊，用於為各種同步消息添加時間信息，所述的時間戳模塊通過系統時間模塊獲取消息發送時的系統時間；時間同步模塊，用於接收同步命令消息並完成同消息發送節點的時間同步；定時器模塊，用於協助判斷節點是否是延遲統計節點；網絡平均每跳延遲的統計模塊，用於處理和轉發延遲統計消息；同步精度的補償模塊，用於接收和轉發誤差補償消息，對本節點的同步精度進行補償。
全文摘要
基於誤差統計的無線傳感器網絡時間同步方法，包括步驟利用同步命令消息的洪泛過程在短時間內達到網絡低精度時間同步，同時建立網絡樹狀層次結構；動態選取部分或全部網絡邊緣節點作為延遲統計節點；統計同步命令消息從匯聚節點到延遲統計節點、以及延遲統計消息從延遲統計節點到匯聚節點路徑上的傳播延遲；計算網絡平均每跳傳播延遲；根據網絡平均每跳傳播延遲和距離匯聚節點的跳數，對同步精度進行補償，達到網絡高精度時間同步。用於實現的無線傳感器網絡，包括匯聚節點和傳感器節點，網絡中所有的節點以匯聚節點為根節點組成樹狀結構。這種方法具有良好的自適應性、可擴展性和較高的同步精度，在同步精度和能量消耗之間取得了很好的折中。
文檔編號H04B7/26GK101087219SQ20061001218
公開日2007年12月12日 申請日期2006年6月9日 優先權日2006年6月9日
發明者孫利民, 王海東, 何慶偉, 柯欣 申請人:中國科學院軟體研究所