無線傳感器網(wǎng)絡(luò)TPSN 協(xié)議的改進(jìn)

1、無線傳感器網(wǎng)絡(luò)TPSN協(xié)議的改進(jìn)劉俊(中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221116摘要:針對無線傳感器網(wǎng)絡(luò)TPSN同步協(xié)議能耗問題,提出一種改進(jìn)的同步算法,該算法結(jié)合了TPSN協(xié)議和RBS協(xié)議的特點,利用無線信道的廣播特性,在兩個節(jié)點廣播域里的所有節(jié)點通過監(jiān)聽這兩個節(jié)點之間的分組交換而達(dá)到同步。仿真實驗證明,該算法降低了整個網(wǎng)絡(luò)的能量消耗。關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);TPSN;時間同步中圖分類號:TP393Improved Algorithm of TPSN for Wireless Sensor NetworksLiu Jun(School of Computer Science

2、 and Technology, China University of Mining and Technology,Xuzhou Jiangsu 221116, ChinaAbstract: Considering the energy consumption of TPSN in wireless sensor network, an improved algorithm that combines the features of TPSN and RBS protocol was presented. Using of the broadcast nature of wireless c

3、hannel, all the nodes in the broadcast domain of two nodes can achieve synchronization by monitoring the packets exchange between nodes. Simulation results show that the algorithm reduces the energy consumption of the entire networks.Key words: wireless sensor networks; TPSN; time synchronization0引言

4、無線傳感器網(wǎng)絡(luò)是一種新的分布式系統(tǒng),節(jié)點之間相互獨立并且以無線的方式通信,每個節(jié)點都維護(hù)一個本地計時器,計時信號由廉價的晶體振蕩器提供。由于晶體振蕩器制造工藝的差別,并且其在運行過程中極易受到電壓、溫度以及晶體老化等多種偶然因素的影響,每個晶體的頻率很難保持一致,進(jìn)而導(dǎo)致網(wǎng)絡(luò)中節(jié)點的計時速率總有偏差,造成網(wǎng)絡(luò)中節(jié)點時間的失步12。為了維護(hù)節(jié)點本地時間的一致性,必須進(jìn)行時間同步操作。目前,無線傳感器網(wǎng)絡(luò)時間同步需要重點解決的問題主要有以下三個方面1:(1如何設(shè)計時間同步協(xié)議,使得同步精度盡可能高;(2如何設(shè)計滿足應(yīng)用需求的低功耗的時間同步協(xié)議,以盡可能延長網(wǎng)絡(luò)壽命;(3如何設(shè)計可擴(kuò)展性強的時間同

5、步算法,以適應(yīng)不斷擴(kuò)大的網(wǎng)絡(luò)規(guī)模和由此帶來的系統(tǒng)動態(tài)性的增強。無線傳感器網(wǎng)絡(luò)時間同步協(xié)議TPSN3(Timing-sync Protocol for Sensor Networks類似于傳統(tǒng)網(wǎng)絡(luò)的NTP時間同步協(xié)議,目的是提供傳感器網(wǎng)絡(luò)全網(wǎng)范圍內(nèi)節(jié)點間的時間同步。在網(wǎng)絡(luò)中有一個與外界通信獲取外界時間的節(jié)點稱為根節(jié)點,根節(jié)點可裝配如GPS接收機的復(fù)雜硬件部件,并作為整個網(wǎng)絡(luò)的時鐘源。TPSN協(xié)議采用層次型網(wǎng)絡(luò)結(jié)構(gòu),首先將所有節(jié)點按照層次結(jié)構(gòu)進(jìn)行分層,然后每個節(jié)點都要與上層節(jié)點交換分組達(dá)到時間同步,最終所有節(jié)點都與根節(jié)點時間同步,由此可看出,下層有多少個節(jié)點,就需要與上層進(jìn)行多少次分組交換,這樣的

6、同步方式消耗了很大的能量,因此本文在該協(xié)議的基礎(chǔ)上,結(jié)合RBS 協(xié)議分組廣播性的特點,提出一種新的改進(jìn)算法,這種算法能大大減少節(jié)點間分組交換的次作者簡介:劉俊,(1985 -,男,江蘇連云港人,碩士研究生,主要研究方向:無線傳感器網(wǎng)絡(luò). E-mail: liujuncumtcs數(shù),從降低整個網(wǎng)絡(luò)的能量消耗。1TPSN協(xié)議介紹TPSN協(xié)議假定每個傳感器都有唯一的標(biāo)識號ID,節(jié)點間的無線通信鏈路是雙向的,通過雙向的消息交換實現(xiàn)節(jié)點間的時間同步,TPSN協(xié)議將整個網(wǎng)絡(luò)內(nèi)所有的節(jié)點按照層次結(jié)構(gòu)進(jìn)行管理,負(fù)責(zé)生成和維護(hù)層次結(jié)構(gòu)4。TPSN協(xié)議包括兩個階段:第一個階段生成層次數(shù)結(jié)構(gòu),每個節(jié)點賦予一個級別,

7、根節(jié)點賦予最高級別第0級,第i級的節(jié)點至少能夠與一個第(i-1級的節(jié)點通信;第二個階段實現(xiàn)所有樹節(jié)點的時間同步,第1級節(jié)點同步到根節(jié)點,第i級節(jié)點同步到第(i-1級的一個節(jié)點,最終所有節(jié)點都同步到根節(jié)點,實現(xiàn)整個網(wǎng)絡(luò)的同步。下面詳細(xì)介紹該協(xié)議的這兩個階段。1.1層次發(fā)現(xiàn)階段在網(wǎng)絡(luò)部署完成后,根節(jié)點通過廣播級別發(fā)現(xiàn)(level discovery分組啟動層次發(fā)現(xiàn)階段,級別發(fā)現(xiàn)分組包含發(fā)送節(jié)點的ID和級別。根節(jié)點的鄰居節(jié)點收到根節(jié)點發(fā)送的分組后,將自己的級別設(shè)置為分組中的級別加1,即為第1級,建立它們自己的級別,然后廣播新的級別發(fā)現(xiàn)分組,其中包含的級別為1,節(jié)點收到第i級節(jié)點的廣播分組后,記錄發(fā)送

8、這個廣播分組的節(jié)點ID,設(shè)置自己的級別為(i-1,廣播級別設(shè)置為(i-1的分組。這個過程持續(xù)下去,直到網(wǎng)絡(luò)內(nèi)的每個節(jié)點都賦予一個級別。節(jié)點一旦建立自己的級別,就忽略任何其他級別發(fā)現(xiàn)分組,以防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞。層次發(fā)現(xiàn)階段建立的層次生成樹如圖1所示: 圖1 層次生成樹Fig.1 Levels spanning tree1.2同步階段層次結(jié)構(gòu)建立以后,根節(jié)點通過廣播時間同步分組啟動同步階段。第1級節(jié)點收到這個分組后,各自分別等待一段時間,通過與根節(jié)點交換消息同步到根節(jié)點,第2級節(jié)點偵聽到第1級節(jié)點的交換消息后,后退和等待一段隨機時間,并與它在層次發(fā)現(xiàn)階段記錄的第1個級別的節(jié)點交換信息進(jìn)行同步。這

9、樣每個節(jié)點與層次結(jié)構(gòu)中最靠近的上一級節(jié)點同步,最終所有節(jié)點都同步到根節(jié)點。鄰居級別的兩個節(jié)點對間通過交換兩個消息實現(xiàn)時間同步,如圖2所示: 圖2 TPSN協(xié)議節(jié)點間分組交換Fig.2 Packet exchange between nodes in TPSN其中節(jié)點A屬于第i級節(jié)點,節(jié)點P屬于第(i-1級節(jié)點,T1和T4表示節(jié)點A本地時鐘在不同時刻測量的時間,T2和T3表示節(jié)點P本地時鐘在不同時刻測量的時間,AP 表示節(jié)點A和P之間的時間偏差,d表示消息的傳播時間,并且假使來回消息的延遲是相同的。節(jié)點A在T1時間發(fā)送同步請求分組給節(jié)點P,分組中包含A的級別和T1時間,節(jié)點P在T2時間收到分組,

10、T2=(T1+d+AP,然后在T3時間發(fā)送應(yīng)答分組給節(jié)點A,分組中包含節(jié)點P的級別和T1、T2、T3信息,節(jié)點A在T4時間收到應(yīng)答,T4=(T3+d-AP,因此可以推出:AP = ( (T2-T1 - (T4-T3 / 2 (1d = (T2-T1 + (T4-T3 / 2 (2節(jié)點A在計算好時間偏差后,將它的時鐘同步到節(jié)點P。理論分析和實驗證明,TPSN同步誤差是RBS的一半,能夠達(dá)到17us左右3,TPSN同步精度高的本質(zhì)原因是由于采用了雙向報文來估計報文傳輸延遲,并且當(dāng)雙向報文傳輸完全對稱時,TPSN具有最小的同步誤差。TPSN本質(zhì)上又是對同步,全網(wǎng)同步需要交換的分組個數(shù)num=2(N-

11、1(N為網(wǎng)絡(luò)中的節(jié)點個數(shù)5,因此TPSN全網(wǎng)同步的能耗高。下面提出一種改進(jìn)算法,降低同步能耗。2TPSN算法的改進(jìn)由于受能量的限制,無線傳感器網(wǎng)絡(luò)中節(jié)點的通信距離是有限的,通常認(rèn)為每個節(jié)點的通信范圍都是一個圓6,如圖3所示。 圖3 兩節(jié)點間的通信模型Fig.3 communication model between two nodes節(jié)點B即在節(jié)點P的通信范圍內(nèi),也在A的通信范圍內(nèi),當(dāng)節(jié)點P與節(jié)點A進(jìn)行分組交換時,由于無線信道的廣播特性,B能監(jiān)聽到P和A之間通信的報文信息。如圖4所示: 圖4 三個節(jié)點間的分組交換Fig.4 packet exchange between the three n

12、odes節(jié)點A在給P發(fā)送同步請求分組后,節(jié)點B在T2時刻監(jiān)聽到該分組,同樣節(jié)點P在給A發(fā)送應(yīng)答分組后,節(jié)點B在T4時刻也能夠監(jiān)聽到P的應(yīng)答分組。對于節(jié)點B,假定B 與A之間的時間偏差為AB,B與P之間的時間偏差為PB,并且假使A到B之間的傳播延遲與B到P之間的傳播延遲相等,均為d,則有:T2 = T1 + d +AB (3T4 = T3 + d -PB (4AB =AP +PB(5由(1(2(3(4(5可得PB = (2*T2 + T3 + T4 2*T4 T2 T1 / 4 (6d = (2*T2 + 2*T4 + T4 T1 3*T3 / 4 (7節(jié)點B在計算時間偏差PB和傳輸延遲d后,將

13、它的時鐘同步到節(jié)點P。我們提出的該改進(jìn)算法降低了同步分組交換次數(shù),尤其是所有節(jié)點都在一跳范圍內(nèi)時,只需一次同步請求,所有節(jié)點都可達(dá)到同步,因此該算法非常適用于節(jié)點密集部署的傳感器網(wǎng)絡(luò)中。3仿真結(jié)果我們用NS2分別仿真了RBS、TPSN以及我們提出的改進(jìn)算法,建立以下仿真場景:網(wǎng)絡(luò)范圍為1000m*1000m,節(jié)點個數(shù)300,初始能量100J,發(fā)送數(shù)據(jù)包所需能量為0.1J,節(jié)點傳輸半徑為250m。仿真結(jié)果如圖5所示:由圖可知,RBS協(xié)議消耗的能量最多,其次是TPSN協(xié)議,消耗能量最少的是我們提出的算法,我們的算法設(shè)計的目標(biāo)是減少分組發(fā)送量,因為節(jié)點發(fā)送一個分組所消耗的能量遠(yuǎn)遠(yuǎn)大于處理一個分組所消

14、耗的能量,并且由圖中可很容易看出,節(jié)點所消耗的總能量與節(jié)點的個數(shù)近似成線性比例關(guān)系,而我們的算法所消耗的總能量隨著節(jié)點數(shù)目增多,增長的最緩慢,因此在稠密部署的WSN中,我們的算法具有很大的優(yōu)勢。 圖5 各算法間的能量消耗比較Fig.5 energy consumption between these algorithms4結(jié)論本文在無線傳感器網(wǎng)絡(luò)TPSN同步協(xié)議的基礎(chǔ)上,提出一種改進(jìn)算法,該算法利用無線信道的廣播特性,通過減少節(jié)點間同步分組交換的次數(shù)實現(xiàn)降低能量消耗的目的,仿真結(jié)果顯示,我們的算法確實降低了整個網(wǎng)絡(luò)的能量消耗。由于該算法結(jié)合了RBS和TPSN兩個協(xié)議的特點,所以其同步精度介于這

15、兩個協(xié)議之間。參考文獻(xiàn) (References1 李曉維,徐勇軍,任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)M.北京:北京理工大學(xué)出版社,2007年.2 孫利民,李建中,陳漁,等et al.無線傳感器網(wǎng)絡(luò)M.北京:清華大學(xué)出版社,2006年.3 Saurabh Ganeriwal, Ram Kumar, Mani B. Srivastava .Timing-sync Protocol for Sensor NetworksJ . Proceedings of the First International Conference on Embedded Networked Sensor Systems, 2003:138-149.4 孫佳偉.無線傳感器網(wǎng)絡(luò)時間同步的研究D. 遼寧:遼寧科技大學(xué),2008年.5 K.-L. Noh, E. Serpedin, and K. Qaraqe, A new approach for time synchronization in wireless sensor networks: pair