分簇型無線傳感器網絡時間同步機制的研究

楊 東，李燈熬，趙菊敏，安文秀

(太原理工大學信息工程學院，山西太原 030024)

無線傳感器網絡(WSN)是近年來逐漸興起的一種融多種技術的新興領域，用以自動感知、采集、傳輸和實時監測待檢測對象信息［1］。無線傳感器網絡是一種面向應用的網絡，在實際應用中，缺乏時間信息的監測結果對于監測者來說是不具有任何意義的。時間同步機制的性能對無線傳感器網絡有著至關重要的影響。

WSN時間同步機制于2002年由Elson［2］等人在Hot-Net－Ⅰ國際會議上首次提出，并被無線傳感器網絡研究者廣泛關注。多年來眾多研究學者已提出了多種經典時間同步算法?，F行的經典時間同步算法可分為3類:基于接收者—接收者的時間同步算法(典型代表算法RBS［3］)、基于接收者—發送者的時間同步算法(典型代表算法TPSN［4－5］)和基于發送者的時間同步算法(典型代表算法DMTS［6］和 FTSP)。

隨著無線傳感器網絡研究水平提高及應用的推廣，網絡的大規模性成為無線傳感器網絡發展的必然趨勢。時間同步機制的研究也必然致力于在降低網絡能量消耗的基礎上提高大規模網絡的時間同步精度。在網絡規模增大和網絡消耗降低的要求下，已有的很多算法得到了限制［7］。RBS 算法復雜度為O(m，n)，信息交換量為O(n2)(m，n分別為廣播消息的個數和節點數目)。當節點數目較大時，信息交換量非常大，消耗網絡較多的能量，不適用于節點數目較多的網絡。同時RBS算法只能相對同步，同步精度較低。DMTS同步算法是以在犧牲同步精度的基礎上，降低算法的復雜度和網絡的開銷，只能適用于對同步要求不是很高的網絡，不能適應未來無線傳感器網絡的發展要求。FTSP算法中，參考節點多次發送廣播消息，通過集中式線性回歸法對時鐘的相對漂移和相對偏移進行估計。當網絡中節點數目較多時，FTSP算法需要非常多的能量來維護大量的歷史數據，用來提高估計精度，從而加大了網絡的能量消耗。

TPSN算法應用于層次型網絡結構，采用雙向同步機制，同步精度較高，在同步過程中信息交換量為O(2n+1)。當n變大時，TPSN算法的信息交換量遠低于RBS的信息交換量，常用于大規模網絡，且易于實現。但是TPSN算法中未考慮根節點的失效問題，且同步精度隨著網絡跳數的增加而降低。考慮到上述問題，本文提出了一種新的同步算法:創建分簇型網絡結構，通過分簇降低網絡跳數避免同步誤差的積累量增大，同時用簇首節點代替根節點，通過周期性選取簇首節點，均衡簇首節點的能量消耗，降低簇首節點的失效率。在同步過程中，同時采用單向廣播同步機制和雙向時間同步機制，提高同步過程中的同步精度。

1 基于分簇型網絡結構的時間同步算法

本文提出的算法分為2個階段:分簇結構的建立階段和時間同步階段。在分簇結構的建立階段，利用本文提出的優化LEACH算法創建網絡拓撲結構，并選取各簇簇首節點，其他節點根據收到簇首節點發送消息的信號強度選擇加入簇，使每個節點均處于簇結構中。在時間同步階段，首先進行的是簇首節點或助理簇首節點與基站之間的時間同步，該階段使用雙向時間同步機制;其次，完成上述時間同步階段后，開始啟動簇首節點與同簇內其他節點的時間同步階段，在該階段使用雙向時間同步機制與單向廣播時間同步機制相結合的時間同步機制。

1.1 分簇型網絡結構的創建

在無線傳感器網絡層次型拓撲控制算法方面，研究者提出了較多經典拓撲結構控制算法。其中，較為經典的是LEACH(Low Energy Adaptive Clustering Hierarchy)算法［8］，該算法能夠周期性自動形成簇型網絡拓撲結構，運行階段可分為簇的建立階段和穩定的數據通信階段。在LEACH算法選取簇首節點過程中，節點產生一個0～1的隨機數，若該隨機數小于閾值T(n)，則該節點以T(n)的概率當選簇首節點。已當選過的節點則把T(n)的值設置為0，在下輪選取中不再當選。閾值T(n)表示為

LEACH算法可以保證每一個傳感器節點以相同的概率當選簇首節點，均衡了簇首節點所消耗的能量，從而避免了因簇首節點能量過低而導致全網絡失效的情況出現，較好地提高了整個網絡的運行時間。但是LEACH算法存在著一些缺陷:首先，該算法在簇首選取機制中，傳感器節點隨機數產生的隨機性較強，有可能導致產生較多的傳感器節點距離簇首節點的位置較遠，容易造成簇首節點的能量消耗過多、過快;其次，該算法簇首選取機制中并沒有考慮到傳感器節點的初始能量和剩余能量的問題，有可能會出現剩余能量較低的節點被選取為簇首節點，加速簇首節點因能量消耗過快而迅速導致死亡。

針對以上LEACH算法中存在的缺陷，本文提出的時間同步算法提供了良好的網絡拓撲結構。本文提出了一種LEACH優化算法，在優化算法中，簇首節點選取閾值中融入簇首節點剩余能量和鄰居節點密度因子，同時在非簇首節點中選取助理簇首節點用以均衡簇首節點的能量消耗。設定簇首節點選取的時間門限值Tth，該值與節點的剩余能量相關，使簇首節點的當選周期與剩余能量有關。優化算法的具體描述如下:

定義E0為傳感器節點的初始能量，在本文中，假定所有傳感器節點的初始能量E0是相等的;定義Eres(r)為第r輪簇首節點選取時，節點i的剩余能量，則節點i從網絡結構初始化至第r輪簇首選取時，因接收、發送消息共消耗的能量(r)，(r)分別為

式中:為第m輪期間，節點i接收數據的比特數;為第m輪期間，節點i發送數據的比特數;dm為第m輪期間節點i的通信距離總和。

在綜合分析以上兩個因素對簇首節點的影響后，結合上述公式，本文提出了優化算法的簇首節點選取機制的閾值T'(n)，T'(n)表達式為

式中:N為無線傳感器網絡簇首節點的總次數;α根據網絡的實際情況確定且0＜α＜1。

由于簇首節點在整個時間同步算法中具有重要的作用，其一但失效不僅會影響時間同步機制的同步精度，嚴重者甚至會危及整個無線傳感器網絡的使用壽命。同時，簇首節點將與基站和簇內非同步節點進行大量的信息交換，能量消耗要遠超過簇內其他節點。為了均衡簇首節點的能量消耗，提高整個網絡的能量利用率，本文提出一種簇首節點助理機制。在該機制中，該節點主要用來實現數據融合并將融合后的數據傳遞給基站。所以在助理簇首節點選取的過程中，該節點與基站位置的距離成為重要的選取原則。定義dBS(i)為節點i與基站之間的距離，則助理簇首節點的選取閾值為

式中:β和γ均根據網絡的實際情況所定，β和γ均為小于1的實數;G'為簇內非簇首節點。

1.2 時間同步階段

時間同步階段主要分為2個階段:簇首節點及助理簇首節點與基站的時間同步階段;簇首節點與同簇內待同步節點時間同步階段。在簇首節點及助理簇首節點與基站間的時間同步階段采用雙向時間同步機制。在簇首節點與同簇內的其他待同步節點時間同步階段采用雙向時間同步機制和單向時間同步機制混合式時間同步機制。

在簇首節點及助理簇首節點與基站實現時間同步的階段，時間同步原理如圖1所示，簇首節點或助理簇首節點在T1時刻向基站發送時間同步請求消息，基站在T2時刻收到該請求消息后，并在T3時刻響應該消息，簇首節點或助理簇首節點在T4時刻收到基站發送的響應消息。根據式(7)和式(8)計算自身節點與基站之間的時間偏差和時間消息傳播時延，并根據計算結果調整自身本地時鐘，從而實現簇首節點或助理簇首節點與基站的時間同步。

式中:d為消息傳播時延;Δ為兩節點間的時間偏移值。

圖1 簇首節點或助理簇首節點與基站時間同步原理圖

在簇首節點與同簇內待同步節點時間同步階段，采用雙向時間同步機制和單向廣播時間同步機制混合式時間同步機制。具體同步過程如下:

1)簇首節點在T1時刻廣播啟動簇內節點時間同步消息，簇內各節點記錄各自收到該廣播消息的時刻Tk(i)，并保存該時刻。

2)隨機選擇一簇內待同步節點，并在T2時刻響應該廣播消息，并發送響應消息給簇首節點。該消息中包含其在步驟1)中收到的時間同步啟動消息的時刻T2和發送響應消息的時刻T3。

3)簇首節點于T4時刻收到該響應節點發送的響應消息，并根據式(7)和式(8)計算簇首節點與該相應節點間的時間偏移值Δ和消息傳播延遲d。

4)簇首節點廣播時間校正消息，該消息中包含響應節點在步驟1)中收到的時間同步啟動消息的時刻T2以及步驟3)中簇首節點計算出的時間偏移值Δ和消息傳播延遲d。

5)簇內待同步節點收到步驟4)中的時間校正消息后，讀取該消息包，比較在步驟1)中自身保存的Tk(i)與T2值的大小，得到自己與簇首節點間的時鐘偏差，并根據δ'調整本地時鐘，從而實現待同步節點與簇首節點間的同步。

簇首節點與同簇內待同步節點時間同步機制原理圖如圖2所示。

2 實驗仿真分析

圖2 簇首節點與同簇內待同步節點時間同步原理圖

為了驗證本文提出的優化算法性能，對所提出的優化算法進行了實驗仿真，并與TPSN算法的實驗仿真結果進行比較。在實驗中假設基站的能量是無窮的，所有傳感器節點均是不可移動的。其中，節點部署范圍100 m×100 m，基站位置(50，50)，節點數300，節點的初始能量E0為0.15 J，Eelse為50 nJ/bit，Efs為10 pJ/(bit×m2)。

從圖3可知，本文算法與TPSN算法隨著節點數目的增加，節點的信息交換量也隨之增加。當網絡節點數目小于50時，二者之間的差距不明顯，但是隨著網絡中節點數目的增多，TPSN算法中的信息交換量要明顯大于相同數目下本文算法中的信息交換量。導致這種情況出現的原因是:TPSN算法中同步節點采用雙向時間同步機制，每對節點間實現同步需要2條消息進行交換。而在本文算法中，只有簇首節點和助理簇首節點采用雙向同步機制，而在簇內節點進行同步時，采用單向廣播時間同步機制。在整個網絡中，采用單向廣播時間同步機制的節點數目要遠小于采用雙向時間同步機制的節點數目。所以當網絡中節點數目增多時，本文算法在信息交換量的優勢明顯優于TPSN算法。

圖3 本文算法與TPSN算法信息交換量的比較

由圖4可知，本文算法與TPSN算法在同步過程中，隨著跳數的增加同步誤差越來越大。TPSN中同步誤差一方面由于雙向時間同步機制中存在消息傳播時延，更主要的是隨著跳數的增加，同步誤差在逐漸積累，導致隨著跳數的增加同步誤差越來越大。本文算法中出現的同步誤差首先出現在簇首節點與基站進行的雙向時間同步機制，其次，較大程度的同步誤差是由于簇首節點在簇內節點同步過程中隨機選擇的應答節點。若應答節點與周圍鄰居節點的時鐘偏移存在較大誤差，則也會導致本文中同步精度的降低。同時，亦可觀察到，當網絡跳數等于1時，二者之間存在較小的差距，但是隨著跳數的增加，在相同的網絡跳數情況下，本文的同步誤差要小于TPSN算法中的同步誤差，即本文的時間同步精度要高于TPSN時間同步精度。

圖4 本文算法與TPSN算法同步誤差的比較

如圖5所示，在相同的輪數情況下，本文算法節點消耗的能量要低于TPSN算法。其主要原因是在本文算法中采用分簇型網絡結構，在簇首節點閾值中融入節點剩余能量因子和鄰居節點密度因子。鄰居節點密度因子越大，簇首節點周圍的鄰居節點數目也就越多，簇內節點的部署也越均勻，簇首節點的通信總距離也就越小，從而簇首節點的通信消耗也就越小。另一方面，本文設定簇首節點的當選時間門限值，該值隨著簇首節點剩余能量的變化自動變化簇首時間的當選周期，剩余能量越低，簇首節點的當選時間也就越短，縮短簇首節點的工作時間，從而降低了節點的能量消耗。最后，本文中助理簇首節點均衡了簇首節點的能量消耗，提高了網絡利用率。

3 總結

本文提出一種新的時間同步算法，在該算法的分簇結構創建階段，簇首選取閾值融入簇首節點的剩余能量因子和鄰居節點密度因子，同時設定了助理簇首節點和簇首節點工作時間門限值，較好地優化了網絡結構，降低了網絡的跳數。在時間同步階段，采用了雙向時間同步機制和單向廣播時間同步機制。實驗證明，該算法降低了網絡跳數，提高了時間同步精度，降低了節點的能量消耗，延長了無線傳感器網絡的運行壽命，具有一定的實用價值。

圖5 本文算法簇首節點與TPSN算法根節點剩余能量比較

:

［1］程敏敏，宋家友，張漢.基于梯度的分簇式路由協議［J］.電視技術，2012，36(15):108－111.

［2］汪富強，曾鵬，于海斌.一種低開銷的時間同步算法［J］.儀器儀表學報，2011，32(6):1357－1361.

［3］ELSON J，GRIOD L，ESREIN D.Fine－grained network time synchronization using reference broadcasts［C］//Proc.5th Symposium Operating Systems Design and Implementation.Boston，MA:ACM Press，2002:147－163.

［4］GANERIWAL S，KUMAR R，SRIVASTAVA M B.Timing－sync protocol for sensor networks［C］//Proc.1st International Conference on Embedded Networked Sensor Systems(SenSys 2003).Los Angeles，CA:IEEE Press，2003:138－149.

［5］GANERIWAL S，KUMAR R，ADLAKHA S，et al.Network－wide time synchronization in sensor networks［EB/OL］.［2013－02－10］.http://nesl.ee.ucla.edu/fw/ram/ram － homepage/content/papers/time_sync.pdf.

［6］PING S.Delay measurement time synchronization for wireless networks［EB/OL］.［2013－02－10］.http://www.intel_research .net/publication/Berkeley/0811200031327－137.pdf.

［7］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［8］周治平，王亭，張明亮.傳感網絡中一種能量有效的簇頭選舉機制［J］.計算機工程與應用，2012，48(8):105－108.