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

1、無(wú)線傳感器網(wǎng)絡(luò)TPSN協(xié)議的改進(jìn)劉俊(中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 徐州 221116摘要:針對(duì)無(wú)線傳感器網(wǎng)絡(luò)TPSN同步協(xié)議能耗問(wèn)題,提出一種改進(jìn)的同步算法,該算法結(jié)合了TPSN協(xié)議和RBS協(xié)議的特點(diǎn),利用無(wú)線信道的廣播特性,在兩個(gè)節(jié)點(diǎn)廣播域里的所有節(jié)點(diǎn)通過(guò)監(jiān)聽(tīng)這兩個(gè)節(jié)點(diǎn)之間的分組交換而達(dá)到同步。仿真實(shí)驗(yàn)證明,該算法降低了整個(gè)網(wǎng)絡(luò)的能量消耗。關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);TPSN;時(shí)間同步中圖分類(lèi)號(hào):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ú)線傳感器網(wǎng)絡(luò)是一種新的分布式系統(tǒng),節(jié)點(diǎn)之間相互獨(dú)立并且以無(wú)線的方式通信,每個(gè)節(jié)點(diǎn)都維護(hù)一個(gè)本地計(jì)時(shí)器,計(jì)時(shí)信號(hào)由廉價(jià)的晶體振蕩器提供。由于晶體振蕩器制造工藝的差別,并且其在運(yùn)行過(guò)程中極易受到電壓、溫度以及晶體老化等多種偶然因素的影響,每個(gè)晶體的頻率很難保持一致,進(jìn)而導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)的計(jì)時(shí)速率總有偏差,造成網(wǎng)絡(luò)中節(jié)點(diǎn)時(shí)間的失步12。為了維護(hù)節(jié)點(diǎn)本地時(shí)間的一致性,必須進(jìn)行時(shí)間同步操作。目前,無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步需要重點(diǎn)解決的問(wèn)題主要有以下三個(gè)方面1:(1如何設(shè)計(jì)時(shí)間同步協(xié)議,使得同步精度盡可能高;(2如何設(shè)計(jì)滿足應(yīng)用需求的低功耗的時(shí)間同步協(xié)議,以盡可能延長(zhǎng)網(wǎng)絡(luò)壽命;(3如何設(shè)計(jì)可擴(kuò)展性強(qiáng)的時(shí)間同

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

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

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

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

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

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

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

12、odes節(jié)點(diǎn)A在給P發(fā)送同步請(qǐng)求分組后,節(jié)點(diǎn)B在T2時(shí)刻監(jiān)聽(tīng)到該分組,同樣節(jié)點(diǎn)P在給A發(fā)送應(yīng)答分組后,節(jié)點(diǎn)B在T4時(shí)刻也能夠監(jiān)聽(tīng)到P的應(yīng)答分組。對(duì)于節(jié)點(diǎn)B,假定B 與A之間的時(shí)間偏差為AB,B與P之間的時(shí)間偏差為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é)點(diǎn)B在計(jì)算時(shí)間偏差PB和傳輸延遲d后,將

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

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

15、兩個(gè)協(xié)議之間。參考文獻(xiàn) (References1 李曉維,徐勇軍,任豐原.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)M.北京:北京理工大學(xué)出版社,2007年.2 孫利民,李建中,陳漁,等et al.無(wú)線傳感器網(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ú)線傳感器網(wǎng)絡(luò)時(shí)間同步的研究D. 遼寧:遼寧科技大學(xué),2008年.5 K.-L. Noh, E. Serpedin, and K. Qaraqe, A new approach for time synchronization in wireless sensor networks: pair