一種低能耗多跳無線傳感器網絡時間同步算法

張 超 黃友銳 陳珍萍

1(安徽理工大學計算機科學與工程學院 安徽 淮南 232001)2(安徽理工大學電氣與信息工程學院 安徽 淮南 232001)3(蘇州科技大學電氣與信息工程學院 江蘇 蘇州 215009)

0 引 言

時間同步是無線傳感器網絡的一項基本技術，也是一項極為重要的技術。時間同步是許多關鍵技術的基礎，比如節點定位、數據融合、休眠調度和TDMA(Time Division Multiple Address)時間調度。無線傳感器網絡的主要作用是感知周圍的環境并將獲取的信息發送到處理中心以進行進一步處理[1]。由于無線傳感器網絡具有規模大、動態性、能量有限、環境復雜等特點[2]。因此對于一些需要較高計算開銷和較大能耗的網絡時間同步協議，比如網絡時間協議(Network Time Protocol，NTP)和全球定位系統(Global Position System，GPS)，并不適用于WSN中。故必須設計針對WSN的時間同步算法，這將具有重要的理論意義和應用價值。

現有的WSN時間同步算法可分為集中式算法和分類式算法兩類。集中式同步算法又可分為以下三種類型：(1) 基于僅發送端(ROS)的時間同步算法，比如延遲測量時間同步(Delay Measurement Time Synchronization,DMTS)[3]和洪泛時間同步協議(Flooding Time Synchronization Protocol,FTSP)[4]。該類同步算法實現簡單、功耗較低，但是有一定的同步誤差。(2) 基于發送端-接收端(SRS)的時間同步，典型的算法就是TPSN(Timing-Sync Protocol for Sensor Network)[5]算法。它將NTP算法思想應用到WSN中，具有相當高的同步精度，且能夠很好地應用到多跳傳感器網絡中去，但是功耗和開銷也相當大。(3) 基于接收端-接收端(RRS)的時間同步，代表算法就是參考廣播同步(Reference Broadcasting Synchronization，RBS)[6]算法。該算法最大的特點就是消除了影響同步精度的接入延遲和發送延遲，以此來保證同步精度，但是卻很難應用到多跳網絡中去。在分布式同步算法中，主要有利用調整脈沖信號間隔來與周圍節點同步的螢火蟲同步算法，還有通過利用鄰居節點信息交互來同步的一致性同步算法。

以上集中式算法能較好地應用于單跳網絡中，但是應用到多跳網絡中會存在比較大的缺陷，存在擴展性和魯棒性以及開銷大的問題[7]。比如若將TPSN算法應用到多跳網絡中，當跳數較少時同步精度尚可，而當跳數較多時累計誤差較大。而且節點之間需要頻繁通信，需要的通信開銷非常大，所以有必要具體研究針對多跳網絡的時間同步算法。文獻[8]提出的LECTS(Low Energy Consumption Time Synchronization)算法雖然能有效降低節點的同步開銷且可以應用到多跳網絡中，但是同步精度卻非常低。文獻[9]將整個網絡分為主網絡和次網絡，以簇首節點形成的網絡稱為主網絡，單簇內的所有節點形成的網絡稱為次網絡。在主網絡中使用類似于TPSN算法同步方式進行同步，在次網絡中使用類似于DMTS算法同步方式進行同步。將這兩種同步方式的有效結合減少了同步開銷，但是并未消除TPSN算法累積誤差大的問題。本文在文獻[8]和文獻[9]算法基礎上提出一種改進的低能耗多跳時間同步算法(Low-energy Multi-hop Time Synchronization，LMTS)，該算法在主網絡中估計簇首節點時鐘頻偏和相偏來保證同步精度，在次網絡中將ROS和SRS方法相結合來降低同步能量的消耗。

1 LMTS算法描述

為了解決同步精度和能量消耗之間平衡的問題，LMTS算法基于分簇網絡實現全局時間同步。算法將網絡中節點分為匯聚節點、簇首節點和普通節點三種類型，以簇首節點和匯聚節點生成的網絡稱為主網絡，單個簇所生成的網絡稱為次網絡。LMTS算法分為兩個階段，分別為拓撲生成階段和時間同步階段。

1.1 拓撲生成階段

在網絡拓撲生成過程中，由于采用有效的拓撲生成策略能夠平衡整個網絡節點能量的消耗[10]。在文獻[11]提出的非均勻分簇方法基礎上，本文LMTS算法進行簇首節點的選舉，以及動態拓撲的生成。在進行簇首節點的選舉時，采用基于定時器的選舉方法，全局網絡節點根據自身相對剩余能量和與匯聚節點的距離設置競爭簇首的等待時間，等待時間越小則競爭成功概率越大。在競爭簇首成功后，普通節點再選擇加入距離最近且通信半徑更大的簇。

簇首節點的選擇過程為：首先，匯聚節點廣播一個消息包分組，包中包含自身ID、層次號level和消息包序號Seq，其他節點在接收到該消息包后，根據信號的強度(RSSI)計算出與匯聚節點的距離[12]；然后，開啟定時器競選簇首，當成功競選后，則向周圍節點發送廣播消息宣布成功競選，當其他節點接收到該消息后，未能成功競選的節點立即清零定時器并退出競爭，如此可實現第一層次簇首節點的選擇；其他層次節點也重復上述競選過程，直到選出全部簇首節點。

當簇首節點競選完成后，普通節點再根據到簇首節點的距離來選擇自己加入的簇。當與多個簇首相等時，則選擇加入通信半徑更大的簇。最后生成的網絡拓撲如圖1所示，其中：“*”表示匯聚節點，“+”表示簇首節點，其余為普通節點。

圖1 網絡拓撲圖

1.2 時間同步階段

LMTS算法將網絡拓撲劃分為主網絡和次網絡兩種類型，在主網絡中簇首節點通過SRS方法進行同步，在次網絡中普通節點采用SRS和ROS相結合的方式與簇首節點進行同步。通過這種方式進行同步，能夠在保證同步精度的同時有效降低了同步能耗，也緩解了ROS方法累積誤差大的問題。

1.2.1 主網絡同步

在主網絡中，簇首節點間通過雙向時間戳消息交換機制來估計節點的時鐘頻偏和時鐘相偏，從而完成節點的同步[13]。同步信息交換模型如圖2所示。

圖2 時間戳交換模型

圖2中，假設A為參考節點，B為待同步節點，A、B節點存在時鐘頻偏和時鐘相偏。信息交換的時間戳T1,k、T4,k均以節點A的本地時鐘為基準，T2,k、T3,k均以節點B的本地時鐘為基準，k表示第k次消息交換。在T1,k時刻，節點A向節點B發送同步請求分組，節點B在T2,k時刻接收到該分組，并在T3,k時刻回復一個包含{T1,k、T2,k、T3,k}的分組包，節點A在T4,k時刻接收到該分組包。

若以節點A為標準時間，則B節點時間戳T2,k可表示為：

T2,k=ω(T1,k+d+Xk)+φ

(1)

B節點的第k次下行信息的時間戳T3,k為：

T3,k=ω(T4,k-d-Yk)+φ

(2)

式中：d表示傳輸過程中的固定延遲；Xk和Yk分別表示第k次上行和下行過程中的隨機延遲；ω表示B節點相對于A節點的相對頻偏；φ表示B節點相對于A節點的相對相偏。

fX,Y(x,y)=(2πσ2)-N×

(3)

L(φ,ω,σ2)=(2πσ2)-N×

(4)

通過對式(4)求解可得時鐘相偏和時鐘頻偏的聯合最大似然估計為:

(5)

(6)

以上描述了主網絡中單跳時同步方法。當擴展到多跳網絡中時，利用上述拓撲生成方法生成如圖3所示的主網絡拓撲。首先第一層簇首節點利用上述的同步方式與匯聚節點保持同步，當同步完成后，第二層簇首節點再通過這種同步方式與第一層簇首節點進行同步。按照此同步方式依次進行下去,直至主網絡中所有節點都能與匯聚節點保持同步。因為在同步過程中調整了時鐘頻偏和相偏，故而能很好地保證同步精度，同時也為每個簇首節點下的次網絡同步提供了同步精度的保障。

圖3 主網絡拓撲結構

1.2.2 次網絡同步

在主網絡中節點完成同步后，簇首節點啟動次網絡的同步。根據自身剩余能量和與簇首節點距離，次網絡中節點以競爭簇首的方式來競爭成為回應節點，簇首節點與回應節點進行雙向交換時間同步，其余節點基于偵聽的方式間接同步到簇首節點。圖4描述了次網絡的同步模型。

圖4 次網絡同步模型

圖4中，假設節點B成功競選為回應節點后。同步過程如下：簇首節點P在TP1時刻廣播同步請求分組，簇內節點A、B、C接收到該分組并標記接收時刻TA2、TB2、TC2，回應節點B在TB3時刻發送反饋分組，分組中包含TB1、TB2和TB3，節點P在TP4時刻接收到該分組后在TP5時刻再次發送包含{TP1、TB2、TB3、TP4、TP5}的消息包，簇內節點A、B、C接收到該分組并標記接收時刻TA6、TB6、TC6。由于傳播延遲極小故可忽略不計，因此假設在第一個過程中A、B、C同時收到P節點發送的請求分組，故A、C與B的時間差可由下式計算：

ΔAB=TB2-TA2

(7)

ΔCB=TB2-TC2

(8)

在鏈路對稱的情況下，節點B根據時間戳{TP1、TB2、TB3、TP4、TP5、TB6}可由下式得到其與簇首節點之間的分組延遲時間。

(9)

故A、C節點與簇首節點P的時間差分別為：

ΔAP=ΔAB+ΔBP

(10)

ΔCP=TCB+ΔBP

(11)

則校正自身時間偏差為T=t+ΔnP，即可以與簇首節點進行同步，其中：t為節點本地時間，n為次網絡中普通節點編號。

以上描述了單個次網絡中普通節點與簇首節點的同步方式，其他次網絡也采用這種同步方式與簇首節點進行同步。因為在主網絡同步結束后簇首節點與匯聚節點保持了同步，所以次網絡同步結束后所有普通節點也相當于間接與匯聚節點保持了同步。

至此，主網絡和次網絡中所有節點最終都和匯聚節點進行了同步，保證了全局網絡時間的一致性。

2 實驗仿真與分析

2.1 同步誤差分析

為了驗證本文所提LMTS算法的性能，在MATLAB平臺上進行了算法的仿真驗證，并與TPSN算法和LECTS算法進行性能的比較。在250 m×250 m的正方形區域內，隨機部署100個節點，匯聚節點部署在區域中心。仿真中考慮了時鐘頻偏對節點時間的影響，節點的頻率偏移量為0～30×10-6，隨機延遲設置為0～30 μs，構建簇狀網絡進行仿真實驗。

圖5給出了不同跳數下不同算法的平均同步精度的變化。通過仿真結果可以看出，當跳數大于3時，本文算法同步精度要高于TPSN算法和LECTS算法。且隨著跳數的增多，LMTS算法的優勢變得更加明顯。因為它在主網絡中有效估計了頻偏和相偏，從而能夠長期有效地精確同步，而TPSN和LECTS由于節點頻偏和跳數增加產生的累積誤差影響了同步精度。同時隨著同步報文數的增多，TPSN算法收斂速度也會變得很慢。

圖5 不同跳數下同步誤差對比

圖6給出了在不同節點數下三種同步算法的同步誤差變化量的對比。同時表1也是利用統計學統計了各個算法所有觀察次數的平均同步誤差、同步誤差標準差、最大同步誤差和最小同步誤差。可以看出，由于是單跳情況，TPSN算法和LECTS算法不存在累積誤差，所以LMTS優勢并不明顯，但同步精度也優于LECTS算法。雖然同步精度次于TPSN算法，但同步開銷相對于TPSN算法來說有極大的優勢。

圖6 同步精度隨同步節點數變化趨勢

表1 不同算法同步精度對比 μs

2.2 同步能耗分析

由于傳感器節點一般成本都比較低，通常置于復雜的環境中，因此更換電池是不現實且沒必要的，所以節點能量是有限的。而節點的能量主要是在發射、接收及偵聽的過程中所消耗的[14]。因此本文主要通過節點在信息傳輸時需要發送和接收的報文數量來衡量節點的能量消耗。參照文獻[15]提出的能耗模型來計算能耗開銷，并給出發送(ETx)和接收(ERx)比特數為k、距離為d的數據包所消耗的能量的計算公式：

(12)

ERx=k×Eelec

(13)

式(12)表示節點發送kbit數據時消耗的能量。式中:Eelct為節點發送或接收每比特數據所消耗的能量；εfs和εmp分別為兩種不同信道傳播模型下的功率放大電路能耗系數；d表示發送節點和接收節點間的距離，當d小于閾值d0時，采用自由空間模型，當發送距離d大于等于d0時，采用多路徑衰減模型。式(13)表示節點接收kbit數據的能耗。

在TPSN算法中，所有節點都需要雙向交換數據包才能同步，每個節點在發送和接收報文時都要消耗能量。而LMTS算法中的簇內節點只需要接收報文而不需要發送報文，因此根據式(13)即可計算其接收能耗，且這些節點又都在參考節點的一跳范圍之內，因此可以采用式(12)的自由空間模型來計算簇首節點的發送能耗。本文算法在應用到大規模網絡時相比于TPSN算法能大大降低能耗。

本文同時從同步過程中消息發送和接收數量上對TPSN、LECTS和本文算法做了對比分析。假設一個網絡中有1個匯聚節點和N個待同步節點，以及M個簇首節點。LMTS算法與其他同步算法如TPSN、LECTS算法在單次同步時所需要發送和接收的報文數如表2所示。

表2 不同算法同步報文開銷對比

由表2可知，不同算法所需的能耗取決于節點發送和接收的報文數，且節點發送和接收報文時能耗也不同。無線射頻模塊CC2530在發送狀態下的電流消耗為29 mA，在接收狀態下為24 mA[16]。若假設該網絡中簇首節點數量M約為總節點數量N的30%，則由表2可計算出LMTS算法相比于TPSN算法能節省20.4%的能量[17]。

本文通過仿真實驗對不同算法進行對比分析。實驗條件為將不同數目節點隨機放置在100 m×100 m的正方形區域內，節點的通信范圍為25 m，并假設參考節點放置在模擬區域的正中央。每次增加25個傳感器節點，統計每次同步時不同算法所需要的消息包數目，結果如圖7所示。

圖7 同步消息包數目隨節點數變化趨勢

通過圖7可以看出，隨著節點數目的增多，三種算法所需的消息包數目都逐漸增加。因為TPSN算法中每個節點都需要進行雙向同步，所以所需的消息包開銷呈線性增加。而LMTS主要銷耗在主網絡的簇首節點間雙向同步上，次網絡中普通節點只需要接收而不用發送消息包，因此相比于TPSN算法能大大減少開銷。LECTS在全網絡中都只需要進行單向廣播，因此僅需極低的消息包交換數量，但也因此會帶來同步精度降低的問題。

3 結 語

本文算法在主網絡中對簇首節點進行時鐘頻偏和時鐘相偏進行估計，有效提高了簇首節點的同步精度，降低了整個網絡的累積誤差。在次網絡中結合SRS和ROS同步機制，使得在應用到多跳網絡中時能夠減少節點同步開銷，同時還能有效保證同步精度，并且有較好的可擴展性。本文算法能夠有效平衡同步精度和能耗的關系，能夠有效應用到能耗有限的大規模網絡中。但對于一些對同步精度要求極高的場合還需要針對次網絡的同步方法做進一步優化，這也是下一步的研究方向。