引言

無線傳感器網絡技術融合了傳感器、低功耗嵌入式計算器、無線網絡和通信、分布式信息處理等技術，利用傳感節點通過自組網絡對監測對象進行實時監測、感知和采集，在環境、資源、智能交通、礦井安全等領域都有著良好的應用前景，是近年來國內外信息領域研究和競爭的焦點。而時間同步技術是無線傳感器網絡中一項非常關鍵的基礎技術。網絡時間協議NTP(Network Time Protocol)是傳統網絡的時間同步協議，最早由美國Delaware大學的Mill教授提出。然而NTP是應傳統網絡的能量效率、網絡動態、基礎設施和系統而構建，因此并不適合低功耗、低成本、微型化、高集成、協作式多跳自組織的無線傳感器網絡。另外，無線傳感器網絡時間同步算法還要考慮能量消耗、可拓展性、精確度、魯棒性等問題，這些都對無線傳感器網絡的時間同步算法提出了新的要求和挑戰。

在2002年的HotNets上，J Elson和Kay Romer首次提出并闡述了無線傳感器網絡時間同步技術的課題，在國際上引發了廣泛的關注和思考，吸引了許多大學和研究機構參與研究，已經提出許多種不同的實現算法及改進算法，典型的有RBS算法、TPSN算法、還有TDP算法、FTSP算法、DMTS算法、LTS算法、TS／MS算法、HRTS算法、OFDC算法、CHTS算法、CRIT算法以及最新的基于螢火蟲技術和協作技術的時間同步算法等。

1 概念與定義

在計算機體系結構中，時鐘通常用品體振蕩器脈沖來度量，即

式中C(t)為構造的本地時鐘，t為真實時間變量，k為依賴于晶振的物理特性常量，ω(τ)為晶振的頻率，間隔c(t)-c(t0)被用來作為度量時間。對于理想的時鐘，有r(t)=dc(t)／dt=1，也就是說，理想時鐘的變化速率r(t)為1。但在工程實踐中，因為溫度、壓力、電源電壓等外界環境的變化，往往會導致晶振頻率產生波動。因此構造理想時鐘比較困難，但在一般情況下晶振頻率的波動幅度并非任意的，而是局限在一定范圍之內。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。

假定c(t)是一個理想的時鐘。如果在t時刻有c(t)=ci(t)，則稱ci(t)在t時刻是準確的；如果dc(t)／dt=dci(t)／dt。則稱時鐘ci(t)在t時刻是精確的；如果ci(t)=ck(t)，則稱時鐘ci(t)在t時刻與時鐘ck(t)是同步的。上述定義表明，兩個同步時鐘不一定是準確或精確的，時間同步與時間的準確性和精度沒有必然的聯系。

如果采用時鐘速率恒定模型，由式(1)，時鐘ci(t)可以簡化表示為：

ci(t)=ai·t+bi (2)

由此可知，時鐘ci(t)和ck(t)之間應該存在如下的線性關系：

ci(t)=aik·ck(t)+bik (3)

式中aik、bik為相對漂移量和相對偏移量。

2 典型同步算法

Elson、Girod和Estrin在參考文獻中以“第三節點”實現同步的思想提出了RBS算法，這是一種基于接收者一接收者的時間同步協議。根節點周期性地向其廣播域中的子節點發送不包含時間戳的參照廣播(Referenccs Broadcast)消息。接收到廣播消息后，鄰居子節點用自已
的本地時鐘記錄各自的接收時刻作為參考比對時鐘，然后相互交換它們記錄的時間信息，這樣接收節點就能知道彼此之間的時鐘偏移量。然后利用式(4)計算相對其他各個節點的時鐘偏移的平均值，并相應進行調整。當所有節點都獲得相對其他節點的時鐘偏移量平均值時，所有接收同一參照廣播消息的接收節點便獲得了一個相對網絡時間，即：

式中：n為待同步節點數，m為參考廣播的次數，Ti,k為第i個節點接收第k次參考廣播的本地時刻。顯然，由offset(i，j)形成的矩陣為對稱矩陣，且對角線元素為0。

TPSN算法是由Ganeriwal等人提出的，是一種基于發送者和接收者的時間同步算法。采用層次型網絡結構。算法分兩步：首先是層次發現階段，建立網絡拓撲結構；然后每個節點與上一級的一個節點進行時間同步，最終實現所有節點都與根節點的時間同步。

FTSP協議是一種單向廣播的發送者和接收者的時間同步辦議。協議首先要網絡動態地選擇一個節點作為網絡的根節點，其時間作為全網的參考時間，根節點把含有當前本地時間的信息包發送給它單跳廣播域內的鄰居節點；鄰居節點在收到信息后分別記錄相應的接收時間，采用參數擬合技術算出相對于根節點的時間漂移和時間偏移；然后這些與根節點同步了的鄰居節點也作為參考節點，采用與根節點同步的相同的辦法，使它們的鄰居節點也實現與其同步。

無線傳感器網絡的最常見的幾種同步算法的性能比較如表1所列。