基于分簇的時間同步算法

宋協(xié)棟

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

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

1.引言

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

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

2.相關工作

2.1 網(wǎng)絡模型

有N個傳感器節(jié)點隨機部署在M*M的檢測區(qū)域內(nèi)，為了簡化網(wǎng)絡模型，采用如下合理的假設：

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

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

3） 簇內(nèi)成員節(jié)點都在彼此通信范圍內(nèi)。

2.2 DEEC分簇算法

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

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

3.算法設計

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

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

3.1 CTSA同步算法

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

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

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

簇內(nèi)同步過程算法具體過程：

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

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

3.2 CTSA能耗分析

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

同步信息數(shù)目計算公式為：

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

消耗總能量為：

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

4.總結

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

參考文獻：

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

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