基于分簇的時間同步算法

宋協棟

摘要：由于無線傳感器網絡中的節點能量有限，能量有效是拓撲設計的一個重要問題，它能在很大程度上影響著網絡的壽命。分簇是提高網絡壽命和可擴展性的一種基本機制。在本文中，提出了一種能量有效的分簇機制CTSA來最小化無線傳感器網絡中的能量消耗。

關鍵詞：無線傳感器網絡 分簇 時間同步 能量有效

1.引言

時間同步問題是支持無線傳感器網絡廣泛應用的基礎支撐技術，實時保證網絡的同步精度是目前研究時間同步問題關注的焦點所在。無線傳感器網絡的獨特性為時間同步問題的研究增加了難度，如傳感器節點采用電池供電，能量有限，因此設計時間同步算法時應該綜合考慮同步精度和能量消耗，盡量取到平衡點；傳感器節點資源有限，無論是信息存儲還是數據計算都不能太復雜[1]。

針對現有時間同步機制的不足，本文以TPSN同步算法和RBS同步算法為基礎，綜合考慮了分簇對時間同步算法的影響，設計了一種基于分簇的時間同步算法。算法首先以DEEC分簇算法為基礎進行網絡拓撲結構的構建，均衡網絡中節點的能量消耗，之后，簇間采用雙向成對同步的同步方式使得簇頭與BS節點進行同步，簇內以簇頭節點為基準節點，按照單向廣播同步的同步方式，并采用在MAC層增加時間戳的方式，去掉訪問時間和發送時間對時間同步的影響，提高算法同步精度。

2.相關工作

2.1 網絡模型

有N個傳感器節點隨機部署在M*M的檢測區域內，為了簡化網絡模型，采用如下合理的假設：

1） 基站BS遠離監測區域，是靜止的，有供電設施，提供標準全局時間。普通傳感器節點電池供電，能量受限。

2） 所有傳感器節點一旦部署完畢就不再移動或者是微移動的。

3） 簇內成員節點都在彼此通信范圍內。

2.2 DEEC分簇算法

DEEC（Distributed energy-efficient clustering algorithm，分布式能量有效成簇算法）[2]規定每個節點根據其初始能量和剩余能量來決定其成為簇頭的概率，即簇頭輪轉周期適應節點的能量變化。算法實現了具有較高的初始能量和剩余能量的傳感器節點比低能量的傳感器節點有更多機會成為簇頭，即能量高的節點成為簇頭的次數會更多，從而實現能量的均衡消耗，延長網絡壽命。

算法過程同Leach算法，簇頭的選舉周期性按照“輪（round）”來隨機選取，各個節點產生一個0到1之間的隨機數，如果該數小于Ti（將Pi帶入Ti就可以得到不同節點的Ti）則相應的節點即作為簇頭，然后確定的簇頭節點發送一個短消息，其它節點按照收到簇頭信息信號的強度決定加入哪一個簇。

3.算法設計

分析已有無線傳感器網絡時間同步算法可知，節點的同步誤差隨著距離和跳數的增加而增大，因此利用簇的形式來減少同步路徑上的同步跳數，降低同步誤差，提高同步精度。

根據網絡規模的不同，本文考慮這樣一種情況，無線傳感器網絡規模不大，簇頭節點可以與BS節點一跳通信，部分簇成員節點無法與BS直接通信，設計基于分簇的單跳時間同步算法CTSA，簇頭節點與BS以TPSN算法雙向成對同步方式進行雙向同步。

3.1 CTSA同步算法

在單跳分簇情形下，簇頭節點可以與BS節點一跳通信，以BS節點為根節點，所有簇頭節點作為上層節點，簇成員節點作為下層節點。

算法首先按照DEEC分簇算法構建網絡，BS節點作為基準節點連通外部互連網與內部傳感器網絡，有基礎供電設施，即能量不受限制，并且能夠提供全局的標準時間。BS節點向其通信范圍內所有簇的簇頭節點發送同步信息，簇頭節點以一跳的方式進行回復，以雙向成對同步方式進行時間同步，以此來保證初級節點的同步精度。

將網絡的整個過程劃分為輪（round）），每一輪又有多個期（epoch）組成，每一輪由建立拓撲結構和時間同步兩個階段構成。在建立拓撲結構階段網絡中的傳感器節點按照自組織的方式以DEEC分簇方法建立全網的拓撲結構，選取網絡中能量較高的節點作為簇頭節點。網絡中節點的狀態分別為：簇頭節點和簇成員節點，簇頭節點保持活動狀態，而其它簇成員節點進入睡眠狀態，減少能量消耗，直到簇頭節點將其喚醒。進入時間同步階段，BS節點按照雙向成對同步的方式同步所有簇頭節點，保證簇頭節點同步的精度，之后每個簇內部分布式的進行內部時間同步，按照單向廣播同步算法的方式。為了提高簇內節點的時間同步精度，簇頭節點通過多次廣播時間同步信息，接收者節點之間多次記錄到達的時間信息，采用4.1中的線性回歸的方式來減少時間同步誤差。一個同步周期即一個epoch。網絡定時重構，重復以上過程。

簇內同步過程算法具體過程：

1） 簇頭節點O于t1時刻廣播同步信息，簇內成員節點記錄到達時間，此處以節點A和節點B為例，收到同步信息時間分別為t2和t5。隨即選擇成員節點回復，此處假設為節點A，在時間t3回復信息，信息包含t2和t3，簇頭節點O在時間t4收到，按雙向成對同步的方式可以得到時間偏差為 。

2） 簇頭節點O再次廣播同步信息，信息中包含t2和時間偏差Δ。簇成員節點收到后可以計算達到同步。

3.2 CTSA能耗分析

同步開銷，即發送的時間同步信息數包括兩部分：BS節點與簇頭節點同步時交換的同步信息數和簇內節點同步時交換的同步信息數。設節點總數為N=n+1，n表示普通傳感器節點的數目，“”表示1個BS節點。

同步信息數目計算公式為：

能量的消耗按照同步算法過程分三部分：建立分簇的網絡拓撲結構消耗的能量E1，簇頭與節點BS同步消耗的能量E2，簇內節點同步消耗的能量E3。各部分能量消耗公式如下：

消耗總能量為：

dtoBS表示簇頭節點距離BS節點的平均距離，按照網絡模型可以得到dtoBS>d0，因此采用多路徑衰減模型。

4.總結

本文設計了特定情況下的基于分簇的時間同步算法，基于單跳的分簇時間同步算法CTSA，算法將分簇的思想引入時間同步算法中，可以均衡網絡中節點的能量消耗，而且減少跳數，減少能量消耗。并通過理論驗證證明了該算法的正確性和優越性。

參考文獻：

[1]李善倉，張克旺.無線傳感器網絡原理與應用[M].機械工業出版社，2008.

[2]卿利，朱清新，王明文.異構傳感器網絡的分布式能量有效成簇算法[N].軟件學報，2006，17（3）：481-489.