一種事件觸發型傳感器網絡時鐘同步算法

（中國海洋大學 計算機科學系， 山東 青島 266071）

摘要：通過介紹時鐘同步機制的作用和現狀，針對節點能源有限的特點，提出一種事件觸發型傳感器網絡時鐘同步算法。仿真結果表明該算法能較好地節約能源開銷，延長網絡壽命。

關鍵詞： 傳感器網絡； 時鐘同步； 事件觸發

中圖法分類號： TP311文獻標識碼： A

文章編號： 1001 3695(2006)08 0245 03

Event Triggered Time Synchronization Algorithm for Sensor Networks

WEI Nuo， GUO Zhong wen， YANG Bin， GONG Zhao jie

(Dept.of Computer Science， Ocean University of China， Qingdao Shandong 266071，China)

Abstract: By introducing the function and current research state of time synchronization， an event triggered time synchronization algorithm is proposed，the simulation result indicates that the algorithm can save energy efficiently and prolong the life of networks.

Key words: Sensor Networks； Time Synchronization； Event triggered

傳感器網絡是一種特殊的Ad hoc網絡，可應用于布線和電源供給困難的區域、人員不能到達的區域（如受到污染、環境不能被破壞或敵對區域）和一些臨時場合（如發生自然災害時，固定通信網絡被破壞）等。它不需要固定網絡支持，具有快速展開、抗毀性強等特點，現被廣泛地應用在環境科學、醫療健康、工業傳感、智能交通控制、能源空間探索等許多領域[1]。時鐘同步作為傳感器網絡的一個重要機制，也日益得到人們的關注。由于傳感器節點一般采用電池供電，一旦電池能量耗盡，該節點就失去作用。因此在傳感器網絡設計中，任何技術和協議的采用都要以節能為前提，基于此筆者提出一種節能的傳感器網絡事件觸發型時鐘同步算法。

1 傳感器網絡中的時鐘同步機制

1.1 時鐘同步的作用

很多傳感器網絡在實際應用中均對時鐘同步有很高要求，精確的時鐘同步不僅能夠保證處理分析數據的正確性，而且可以預測系統下一個時段的操作。時鐘同步在傳感器網絡中的作用主要體現在以下三個方面：

（1）觀測者與傳感器網絡之間的交互作用。為了跟蹤、報告、處理一些現象和事件，如要獲得某個物體的移動速度或加速度，需要將有關的數據準確地發送到觀測者（可能是人員或計算機），這時就需要準確記錄現象和事件發生的物理時間。

（2）傳感器網絡內部節點之間的交互作用。一個重要的例子就是在無線網絡中使用時分復用機制時，系統給每個節點劃分一個時間片，在規定的時間里完成對數據的存取，這就需要參與的節點均共享一個時鐘標準。此外，很多數據擴散算法均要根據時間排序來處理數據，但是由于傳感器網絡中消息的延遲，使得它們可能不能按照發送的順序到達接收者，所以需要根據所記錄的時間信息來確定先后順序。

（3）傳感器網絡和現實世界之間的交互作用。在傳感器網絡中，很多節點可能監測同一個物理現象，傳感器網絡的作用就是把這些分散的觀測結果進行綜合分析。例如，在交通監控系統中，通過多個傳感器來測量車輛行駛的狀況，以此預測車輛的行駛方向和速度，如果沒有統一的時鐘信號，那些從傳感器獲得的數據就不能匹配。

1.2 時鐘同步算法的設計原則

（1）節省能源。由于傳感器節點的微型化，節點的電源能量非常有限，而且受到環境限制難以更換電池，所以傳感器節點的電池能量直接決定了網絡的工作壽命，是整個網絡設計最主要的約束之一。

（2）適應網絡結構的動態變化。由于傳感器網絡自身的特點，網絡中的節點可能由于發生故障或能源耗盡離開網絡，也可能為了某種工作需要加入到網絡中來。這些特點使得傳感器網絡的拓撲結構變化很快，這對網絡算法的有效性提出了挑戰。

（3）可擴展性。傳感器網絡的節點數目眾多，分布密集，節點數量和密度都要比Ad hoc網絡高幾個數量級，因此算法要支持大規模的傳感器網絡。

1.3 時鐘同步算法的研究現狀

Elson等人提出了RBS[2]（Reference Broadcast Synchronization）算法，節點通過物理層的廣播周期性地發送包含參考時間信息的消息到其鄰節點，接收者之間互相交換消息的到達時間，通過線性衰減來計算它們之間的時鐘偏差并以此調整自身時鐘，實現整個網絡的同步。

FTSP[3](Flooding Time Synchronization Protocol)算法利用節點間交換時鐘信息和線性衰減來達到同步。網絡中具有最小ID的節點被選為主節點并且能夠作為參考時間的來源，主節點周期性以泛洪方式在整個網絡中廣播包含它當前時刻的消息，通過更新時間戳，接收到這個消息的節點會記錄消息的到達時間并且廣播到鄰節點，每個節點計算出它們與主節點的時鐘偏差并調整自己的時鐘。

在Qun Li等人提出的AD[4](Asynchronous Diffusion)算法中，每個節點周期性地向其鄰節點廣播包含它當前時間信息的數據包。接收者計算出這些時間的平均值并發送到其鄰節點，然后將該平均值當作新的時間值。如此循環下去，直到達到整個網絡同步。

2 事件觸發型時鐘同步算法

2.1 問題的提出

傳統的時鐘同步算法主要是通過周期性的同步來最小化同步誤差，以達到最大精度，而沒有考慮到能量的消耗。對于傳感器網絡而言，電源單元是最重要的模塊之一。有的系統可能采用太陽能電池等方式來補充能量，但是大多數情況下傳感器節點的電池是不可補充的，因此節省節點能量至關重要。如果需要監測的事件并不是頻繁發生，那么為了避免消耗大量不必要的能源，我們提出一種傳感器網絡的事件觸發型時鐘同步算法。

2.2 傳感器網絡能量消耗模型

傳感器節點之間是靠無線電進行通信，針對傳感器網絡的無線信道有許多假設和模型，其中傳感器網絡的一階能量消耗模型得到廣泛的應用[5]。如圖1所示，發送數據包消耗能量包括發射電路耗能、放大電路耗能兩部分，接收數據只有接收電路消耗能量。

該模型包括兩種發送者能量消耗方式，即自由空間傳送方式和多通路衰減方式。對于兩種方式的選擇主要取決于發送者和接收者之間的距離 d，當兩者之間的距離d小于閾值d₀ 時選擇自由空間傳送方式；否則就選擇多通路衰減方式。

發送者消耗能量計算公式為

接收者消耗能量計算公式為E_Rx(l)=E_elec×ι其中， E_elec 取決于信道編碼和信號傳播方式。

2.3 算法描述

在通常情況下，傳感器網絡中的各個節點是不同步的，它們以自己的時鐘頻率運轉。當某個事件發生時，監測到該事件的傳感器節點會根據自己的本地時鐘記錄下事件發生的時間T_{a?；颈O測事件發生后，會給節點發送一個同步脈沖，建立樹型結構，開始節點的同步。具體過程可以分成兩個階段。}

2.3.1 樹的形成階段

以基站（第0層）為根節點廣播層次發現數據包，這個數據包中包含發送者所從屬的層數，當根節點的直接鄰節點收到這個數據包后，設置層數為1，然后廣播包含該層數的新的發現數據包，重復這個過程，直到網絡中所有的節點均從屬于一個確定的層次。

如果一個節點要加入到該網絡中，但網絡中的層次發現階段已經結束，那么它可以廣播層次請求數據包，接收到該請求的鄰節點通過發送其所在層次的數據包作為回應，那么該節點層次就是其鄰節點的所在層次加1。

由于傳感器節點會隨時耗盡能源，當位于i-1層的所有節點均因為能源耗盡而退出網絡時，為了避免位于第 i 層的節點收不到任何回復而與網絡失去聯絡，可以在網絡中設置一個超時裝置。當超過某一設定時間值時，重新發送層次請求數據包。如果此時網絡處于連接狀態，它至少會收到一個回復，從而可以確定新的層次。

如果我們考慮到時鐘偏差，那么同步精度同樣會受到算法運行時間的影響，為了最小化運行時間，同步應該沿著分支并行運行，這樣所有的葉子節點幾乎均可以在同一個時刻完成同步。

在傳統的樹型結構中，同步誤差的方差隨著跳數增大而呈線性增長趨勢。兩個鄰近節點的同步誤差是一個高斯隨機變量，其方差是接收方方差 m 的四倍[6]，因此位于一個擴展樹第 d 層的節點，其時鐘誤差的方差為4×d×m 。由于時鐘同步的精度隨著子節點與根節點之間距離的增大而降低，所以最小深度的樹應該有最小的誤差，因此在樹的形成階段也可以考慮采用最小深度樹的生成算法。

2.3.2 時鐘同步階段

當樹型結構建立起來后，根節點會沿著樹的分支開始廣播時鐘同步數據包，位于第 i 層的節點A和位于第 i +1層的節點B使用經典的Pair wise[7]方式來同步。如圖2所示，T₁，T₄為節點A的本地時間，T₂，T₃為節點B的本地時間。T₁時刻，A發送一個包含T₁的數據包到B，B在T₂時刻收到此數據包，則T₂=T₁+D+d，其中D和d分別為數據包在A，B間的傳輸時間和A，B節點間的時鐘偏差。同樣，T₃時刻，B發送一個確認數據包到A，A在T₄時刻收到此數據包，則有T₄=T₃+D-d ，假設在這段時間里，時鐘偏移量和傳輸延遲不變，可以計算出：

D=(T₂T₁)+(T₄T₃)]/2，d=(T₂T₁) (T₄T₃)]/2

A可以根據 d 糾正其時間偏差，從而達到與B同步。

為了避免介質存取沖突，兩個節點在交換數據包前要等待一定時間。當它們接收到確認數據包后，就會根據計算出來的時鐘偏差調整時間。整個同步過程會在整個網絡中重復進行，直到所有的節點均與根節點同步。假設每個節點同步后的時間是T_b ， 這時該節點的本地時間是T_c ，那么可以計算出該節點監測到事件發生時的標準時間是T_b（T_aT_c）。

3 仿真及性能評估

假設傳感器節點個數N＝100，方形區域邊長 M×M ＝100m×100m，網絡中各節點均勻分布，每個節點的能量為2J。能量消耗模型中，參數的典型值為 E_elec ＝50nJ/bit，ε_amp＝0.0013 pJ/bit/m⁴，ε_fs ＝10pJ/bit/m²。周期型同步中，采用同樣的樹型結構，同步周期 T 設為30min[8]。圖3給出了在5h內，事件觸發型時鐘同步算法和周期型時鐘同步算法能量消耗的比較。

仿真結果表明，當事件的觸發間隔和同步周期相同時，兩種算法消耗同樣的能量。當事件發

生頻率較低時（在本仿真中事件觸發間隔>30min），觸發型時鐘同步算法所消耗的能量要明顯地低于周期型同步算法。因此觸發型時鐘同步算法在事件觸發間隔較大的情況下，具有良好的節能性。

4 總結

時鐘同步是傳感器網絡的重要組成部分，傳感器網絡的許多應用，如數據融合、信號處理等領域，均需要多個節點具有彼此同步的物理時鐘。受傳感器節點能源的限制，傳感器網絡的時鐘同步應考慮到同步時機和同步方式。本文在介紹傳感器網絡時鐘同步機制的基礎上，提出一種事件觸發型時鐘同步算法。仿真結果表明，與傳統的周期型時鐘同步算法相比，該算 法在事件發生頻率較低的情況下，能夠較好地節約節點能量，節省系統開銷。

參考文獻：

[1] 馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述[J].通信學報， 2004， 25(4)：114－124.

[2] Jeremy Elson，Lewis Girod，Deborah Estrin.Fine grained Network Time Synchronization Using Reference Broadcasts [C].The 5th Symposium on Operating Systems Design and Implementation (OSDI 2002)， 2002.147－163.

[3] Miklos Maroti， Branislav Kusy， Gyula Simon， et al. The Flooding Time ynchronization Protocol[R].Technical Report， 2004.

[4] Qun Li，Daniela Rus. Global Clock Synchronization in Sensor Networks[C].IEEE INFOCOM， 2004.19－28.

[5] Wendi Radio Heinzelman，Anantha Chandrakasan，Hari Alakrishnan .Energy Efficient Communication Protocol for Wireless Microsensor Networks[C]. Proceedings of the 33rd Hawaii International，2002.49－98.

[6] Jean Marc Berthaud. Time Synchronization over Networks Using Convex Closures[J].IEEE/ACM Transactions on Networking，2000，8(2):265－277.

[7] Jana van Greunen，Jan Rabaey. Lightweight Time Synchronization for Sensor Networks[J].The 2nd ACM International Workshop on Wireless Sensor Networks and Applications，2003，9(2):11－19.

[8] John Wiley ，Sons. Time Synchronization and Calibration in Wireless Sensor Networks in Handbook of Sensor Networks[C].Algorithms and Architectures，2005.34－58.

作者簡介：魏諾(1982 )，女，研究生，研究方向為傳感器網絡以及Ad hoc網絡；郭忠文(1965 )，男，教授，主要研究方向為傳感器網絡、Ad hoc網絡以及移動Agent；楊彬(1981 )，女，研究生，研究方向為傳感器網絡以及Ad hoc網絡；宮召杰(1975 )，男，研究生，研究方向為傳感器網絡以及Ad hoc網絡。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。