無線傳感器網絡中分層時間比較時鐘同步方法
2023-06-07 16:18:41 1
專利名稱：無線傳感器網絡中分層時間比較時鐘同步方法
技術領域：
本發明涉及一種無線網絡技術領域的方法，具體是一種無線傳感器網絡中分 層時間比較時鐘同步方法。
背景技術：
近年來，由低功耗無線傳感器所組成的無線傳感器網絡(wireless sensor networks, WSNs)應用愈加廣泛。時間同步是WSNs應用的重要組成部分，控制消 息衝突、數據融合、節點定位等方面都要求節點間保持時鐘同步。
國內外許多大學和研究機構都對無線傳感器網絡的同步技術進行了深入研究 並提出了多種時間同步方法，從不同方面滿足傳感器網絡的應用需要。到目前為 止，已經提出了十幾種實現方法，典型的有RBS、 TPSN、 LTS、 TS/MS、 TSync、 DMTS、 FTSP、 AD、 TSS和TDP。這些方法雖然從不同的方面滿足了應用需要，但是相應的 他們自身有不少缺陷，比如RBS精度較好，但是在有的網絡協議中無法應用。TS/MS、 Tsync精度更好，但是方法複雜，對於無線網絡中有限的運算能力和網絡開銷而言 有點過大了。
經對現有技術文獻的檢索發現，Rui Fan, Indraneel Chakraborty， and Nancy Lynch, 在2005年8月23日的Lecture Notes in Computer Science, Principles of Distributed Systems (計算機科學講座筆記，分布式系統原理)中發表的文 章《Clock Synchronization for Wireless Networks》(無線網絡的時鐘同步)， 該文章提出了一種同步方式，採取外部時鐘同步與內部時鐘同步並行的方式，通 過不斷比對時間坐標大小，取其最大(其實也是同步時可能與外部基準時間最接 近的)為其邏輯時間，同步周期採用固定周期。該方法的計算開銷和通信開銷較 小，避開了隨機性最大的數據包處理延時的估計，同時避免了一些算法可能會將 時鐘回撥的可能性，但是該方法僅對穩定的單跳網絡效果較好，在規模較大的動 態網絡裡同步精度較差，這顯然對於某些實際應用是不夠的。
發明內容
本發明的目的是針對上述現有技術的不足，提供了一種無線傳感器網絡中分 層時間比較時鐘同步方法，通過分層以及時間戳比較，減少了同步通訊的開銷， 採用估計逼近時鐘漂移，調整參數P的方法，進一步降低同步的開銷，同時，拋 棄了失效的時間戳，減小了對節點存儲的開銷，本發明能夠應用到動態多跳網絡 中去。
本發明通過如下技術方案實現的，本發明包括如下步驟
步驟一，網絡開始初始化以總的基站/協調器為頂層，根據信號強度和設備 種類發出隸屬關係確認幀，對應的設備接受到確認幀後，並返回應答幀，以此類 推，完成對整個網絡的分層設置，同時確認網絡達到穩定狀態；
步驟二，從頂層開始，逐層開始同步，同步分為兩個部分外時鐘源同步和 內時鐘源同步，外部時鐘源同步過程中，若節點i接到GPS同步信號，節點i的 當前有效數組坐標i. current加一，外部時鐘源同步為內部時鐘源同步提供時間 基準，各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時間；
步驟三，各節點統一設定同步周期，隨後各節點根據最初若干次同步結果以 及同步精度調整時鐘漂移參數P、同步周期T，若節點某次同步滿足同步精度， 則增加同步周期T，減少系統開銷；若不滿足，則調整時鐘漂移參數P，並將減 少同步周期T ;
步驟四，節點i檢査當前有效數組坐標是否大於數組長度，如果成立，當前 有效數組坐標清零，拋棄失效的時間戳，如果不成立，當前有效數組坐標繼續計 數，重複步驟二。
所述各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時 間，包括如下步驟
第一步，如果節點i發現節點i的邏輯時鐘等於節點i的預訂同步次數與節 點同步周期的乘積，節點i開始同步，並檢査外部時鐘源是否存在，若存在，則 發出外部同步服務請求，進入第二步；無論外部時鐘源是否存在都開始內部時鐘 同步，即執行第三步，同時節點i的預訂同步次數增加一，但第o層節點始終不 進行內部時鐘同步；
第二步，節點i進行外部時鐘源同步如果節點i接到GPS同步信號，節點 i的當前有效數組坐標i. current加一，將GPS時間戳存入數組i. local [i. current]
5和i.max_gps中，i. local [i. current]隨物理時鐘同步更新，i. local []表示節點 i對該節點所處時間坐標的最佳估計，i. max一gps表示最近的GPS時間戳；
第三步，節點i進行內部時鐘同步節點i向直屬的上級節點j發出同步服 務請求，如果節點i收到從上級節點j發來的同步幀 sync—message (j. local [j. current] ， j. max一gps)，節點i檢査節點j的GPS時間 戳是否和節點i的i.max—gps —樣新，隨後檢查j. local [j. current]是否比 i. global[i. current]大，i. global[]表示節點i對該節點所屬網絡的其他節點時 間最佳估計，如果兩者皆滿足，代表節點i對其他節點的估計i. global[i. current] 有誤差， 貝'J更新 i. global [i. current] 為 j. local [j. current]， j. global [j. current]以物理時鐘的(1- P ) /(1+ P )倍更新;
第四步，節點i比較數組i. local []各元素，取最大者為i.mlocal，比較數 組i. global []各元素，取最大者為i. mglobal;
第五步，節點i比較i.mlocal和i. mglobal的大小，取較大者為i. logical 表示節點i的邏輯時鐘，完成節點時鐘同步，i. logical隨物理時間同步更新。
與現有技術相比，本發明包括如下有益效果
1、 本發明通過時間戳比較來避免對節點間數據包傳輸延時的估計；從實際的 無線網絡的搭建和抓包分析可以知道節點間的傳輸延時由於信道能量檢測和信道 衝突檢測，節點的任務調度的影響，隨機性是非常大的，採用時間戳比較繞開了 對這些因素的估計，從而在保證一定精度的條件下，降低系統開銷；
2、 本發明通過分層的方法減小了節點間的同步誤差極限；換言之，節點間的 同步誤差極限和節點的同步精度都取決於該節點所屬網絡的最大延時，故將一個 大的網絡分層，分成若干個小網進行同步，有助於減小誤差；
3、 本發明通過變周期的方法，減小了同步通訊的開銷；在實際工程中，各節 點所使用的晶振是有較大差別的，有的精度好，有的精度差。如果一刀切的統一 同步周期，顯然是給有限的網絡信道流量增加不小的開銷，增加全網絡能量消耗， 而讓節點自行統計來變更同周期可以避免不必要的能量消耗和流量開銷；
4、 本發明通過估計逼近時鐘漂移，調整參數P的方法，進一步降低同步的開 銷，在前面節點同步過程中，可以看到，如果P估計較準的話，顯然本節點對其 他節點的時鐘估計更準，相應的同步周期就可以設的更長，自然開銷就小了；
5、 本發明通過將i. Current清零來拋棄失效的時間戳，減小了對節點存儲的
6開銷；雖然隨著半導體工藝的不斷發展，片上資源越來越豐富，但是，對於節點 所使用的單片機而言資源受較大限制的狀況在可見得將來一段時間內仍然是無法 改變的。本同步機制中兩個最佳估計數組在較短的時間內是不佔多少資源的，但 是時間長了，顯然不行的，同時過舊的時間戳也是沒有意義的。所以要拋棄失效 的時間戳。
綜上，本發明能更好的符合無限傳感器網絡時間同步算法的精度適中，低開 銷，健壯的要求。
圖1是本發明方法的工作流程圖: ——
圖2是本發明的實施例仿真結果圖中，(a)為模擬的未經處理晶振頻率變化圖，(b)為經過參數調整後邏輯頻 率變化圖，(c)為處理前後的同步周期進行對比柱狀圖。
具體實施例方式
下面結合附圖對本發明的實施例作詳細說明本實施例在以本發明技術方案 為前提下進行實施，給出了詳細的實施方式和具體的操作過程，但本發明的保護 範圍不限於下述的實施例。
本實施例應用於無線傳感器網絡搭建項目中的實驗網絡的時鐘同步研究的應 用中，主要採用了基於紫芯公司的ASAP1810/20開發板和TI的CC2420無線傳感 器開發板，並在其上進行開發組網實驗。
本實施例中無線傳感器網絡由126個從設備和一個主設備組成，其中主設備設 有GPS時鐘源，網絡的分層層數由各節點按照其物理位置和功能自行劃分。
如圖1所示，本實施例包括如下步驟
步驟一，網絡開始初始化以總的基站/協調器為頂層，根據信號強度和設備
種類發出隸屬關係確認幀，對應的設備接受到確認幀後，並返回應答幀，以此類
推，完成對整個網絡的分層設置，同時確認網絡達到穩定狀態；
步驟二，從頂層開始，逐層開始同步，同步分為兩個部分外時鐘源同步和 內時鐘源同步，外部時鐘源同步過程中，若節點i接到GPS同步信號，節點i的 當前有效數組坐標i. current加一，外部時鐘源同步為內部時鐘源同步提供時間 基準，各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時間； 步驟三，各節點統一設定同步周期，隨後各節點根據最初若干次同步結果以及同步精度調整時鐘漂移參數P、同步周期T，若節點某次同步滿足同步精度， 則增加同步周期T，減少系統開銷；若不滿足，則調整時鐘漂移參數P，並將減 少同步周期t;
步驟四，節點i檢査當前有效數組坐標是否大於數組長度，如果成立，當前 有效數組坐標清零，拋棄失效的時間戳，如果不成立，當前有效數組坐標繼續計 數，重複步驟二。
所述各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時 間，包括如下步驟
第一步，節點i內建立兩個數組i. local [p]、 i. global [p],八個變量-i. current、 i. next—sync、 i.mlocal、 i.mglobal、 i.max一gps、 p、 i.logical、 t ，其中，i. current表示節點i的當前有效數組坐標；i. local []表示節點i對 該節點所處時間坐標的最佳估計；i. global []表示節點i對該節點所屬網絡的其 他節點時間最佳估計；i.mlocal代表i. local []中最大值；i.mglobal代表 i. global []中最大值；i. max_gpS表示最近的GPS時間戳；P表示時鐘漂移，單位 ppm (每百萬分之一)；T表示節點同步周期；p表示數組長度；i. logical表示 節點i的邏輯時鐘；i. next—sync表示節點i的預定同步次數；
第二步，如果節點i發現i. logical=i. next—sync* t ，節點i開始同步，並 檢查外部時鐘源是否存在，若存在，則發出外部同步服務請求，進入步驟三；無 論外部時鐘源是否存在都開始內部時鐘同步，即執行步驟四，同時變量 i. next—sync加一，但第0層節點始終不進行內部時鐘同步；
第三步，節點i進行外部時鐘源同步過程如果節點i接到GPS同步信號， i. current力口一，將GPS時間戳存入i. local[i. current]禾口 i.max—gps中， i. local [i. current]隨物理時鐘同步更新；
第四步，節點i進行內部時鐘同步過程節點i向直屬的上級節點j發出同 步服務請求，如果節點i收到從上級節點j發來的同步幀 sync—message (j. local [j. current] ， j. max—gps)，節點i檢査節點j的GPS時間 戳是否和節點i的i.max—gps —樣新，隨後檢查j. local [j. current]是否比 i. global[i. current]大，如果兩者皆滿足，代表節點i對其他節點的估計 i. global [i. current] 有誤差， 貝U 更新 i. global [i. current] 為 j. local [j. current] ， j. global [j. current]以鬥勿理時鐘的(1— p ) /(1+ p )倍更新；第五步，節點i比較數組i. local[]各元素，取最大者為i.mlocal，比較數 組i. global []各元素，取最大者為i.mglobal;
第六步，節點i比較i.mlocal和i.mglobal的大小，取較大者為i. logical 即邏輯時鐘已完成節點時鐘同步，i. logical隨物理時間同步更新。
本實施例中，節點間的同步誤差如下述公式|/.log /ca/ (0 - ,log /^/ (0|
S 2(Z) ++ D))，節點間的同步誤差大約控制在節點間信號延遲2倍以內，
網絡結構呈二叉樹結構向下遞推，本實施例的目的是使用該方法，在儘量小的網 絡開銷和節點計算開銷下，滿足網絡的同步精度要求。
將本實施樹方法以軟體的形式寫入各開發—板中，再以該TF發板為無線傳感器網 絡節點組建網絡，觀察網絡通信情況，主要是確認網絡已經建立，頂層節點接入 外部時鐘源。在實施例中，晶振漂移P取10—4秒，同步周期t取1秒。網絡的分
層層數根據節點的通信容量和信號覆蓋範圍而定。
在該實際組網實驗的基礎上，對調整參數P和調整同步周期t之間的關係進
行了模擬仿真，仿真結果如圖2所示，圖(a)為模擬的未經處理晶振頻率變化圖，
(b)為經過參數調整後邏輯頻率變化圖，這兩幅圖中的縱坐標分別表示原始頻率
和基準頻率、邏輯頻率和基準頻率之差。而圖(c)為一柱狀圖，表示將處理前後
的同步周期進行對比。其中，1號柱代表處理前的同步周期，2號柱代表處理後的
同步周期。由該圖可知，經過處理的邏輯頻率比原始頻率穩定性要好很多，由此
可以在滿足一定定時精度的條件下，儘可能地延長同步周期，這對於能耗敏感的
無線傳感器網絡有著很大的意義，尤其是在發射功耗遠遠超過運算功耗的情況下。
權利要求
1、一種無線傳感器網絡中分層時間比較時鐘同步方法，其特徵在於，包括如下步驟步驟一，網絡開始初始化以總的基站/協調器為頂層，根據信號強度和設備種類發出隸屬關係確認幀，對應的設備接受到確認幀後，並返回應答幀，以此類推，完成對整個網絡的分層設置，同時確認網絡達到穩定狀態；步驟二，從頂層開始，逐層開始同步，同步分為兩個部分外時鐘源同步和內時鐘源同步，外部時鐘源同步過程中，若節點i接到GPS同步信號，節點i的當前有效數組坐標i.current加一，外部時鐘源同步為內部時鐘源同步提供時間基準，各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時間；步驟三，各節點統一設定同步周期，隨後各節點根據最初若干次同步結果以及同步精度調整時鐘漂移參數ρ、同步周期τ，若節點某次同步滿足同步精度，則增加同步周期τ，減少系統開銷；若不滿足，則調整時鐘漂移參數ρ，並將減少同步周期τ；步驟四，節點i檢查當前有效數組坐標是否大於數組長度，如果成立，當前有效數組坐標清零，拋棄失效的時間戳，如果不成立，當前有效數組坐標繼續計數，重複步驟二。
2、 根據權利要求1所述的無線傳感器網絡中分層時間比較時鐘同步方法，其特徵是，所述各節點根據內時間源和外時鐘源同步結果的比較獲得該節點的邏輯時間，包括如下步驟第一步，如果節點i發現節點i的邏輯時鐘等於節點i的預訂同步次數與節點同步周期的乘積，節點i開始同步，並檢査外部時鐘源是否存在，若存在，則發出外部同步服務請求，進入第二步；無論外部時鐘源是否存在都開始內部時鐘同步，即執行第三步，同時節點i的預訂同步次數增加一，但第o層節點始終不進行內部時鐘同步；第二步，節點i進行外部時鐘源同步如果節點i接到GPS同步信號，節點i的當前有效數組坐標i. current加一，將GPS時間戳存入數組i. local[i. current]和i.max—gps中，i. local[i. current]隨物理時鐘同步更新，i. local []表示節點i對該節點所處時間坐標的最佳估計，i.max—gps表示最近的GPS時間戳；第三步，節點i進行內部時鐘同步節點i向直屬的上級節點j發出同步服務請求，如果節點i收到從上級節點j發來的同步幀sync_message (j. local [ j. current] ， j. max—gps)， 節點i檢査節點j的GPS時間戳是否和節點i的i.max—gps —樣新，隨後檢查j. local [j. current]是否比i. global [i. current]大，i. global []表示節點i對該節點所屬網絡的其他節點時間最佳估計，如果兩者皆滿足，代表節點i對其他節點的估計i. global [i. current] 有誤差， 則更新 i. global [i. current] 為j. local [j. current] ， j. global [j. current]以物理時鐘的(1—P )/(1+P )倍更新；第四步，節點i比較數組i.local[]各元素，取最大者為i.mlocal，比較數組i. global []各元素，取最大者為i.mglobal;第五步，節點i比較i.mlocal和i.mglobal的大小，取較大者為i. logical表示節點i的邏輯時鐘，完成節點時鐘同步，i. logical隨物理時間同步更新。
全文摘要
一種無線網絡技術領域的無線傳感器網絡中分層時間比較時鐘同步方法包括以下步驟步驟一，網絡開始初始化，並從基站/協調器開始按照信號強度和設備種類分層；步驟二，整個網絡分為外時鐘源同步和內時鐘源同步，節點採用時間戳比較的方法同步，上下級節點以伺服器/客戶端模式同步；步驟三，根據歷次同步效果來調整同步周期，時鐘漂移參數；步驟四，自動拋棄陳舊的時間戳。本發明與現有技術相比，能更好地符合無線傳感器網絡時間同步方法的精度，同時具有低開銷、健壯的優點。
文檔編號H04W56/00GK101466142SQ20091004503
公開日2009年6月24日 申請日期2009年1月8日 優先權日2009年1月8日
發明者任千裡, 濤 劉, 劉凱凱, 戎蒙恬, 鑫 李 申請人:上海交通大學