[吳晨]
?
基于分離樹的能量有效數(shù)據(jù)轉(zhuǎn)發(fā)機制*
[吳晨]
摘要
在無線傳感網(wǎng)中,由于傳感器節(jié)點能量極度受限,而傳統(tǒng)的廣播通信方式會產(chǎn)生很大的數(shù)據(jù)冗余,因而造成能量利用率較低。文章通過建立以匯聚節(jié)點為根節(jié)點的分離樹來解決以上問題,m顆分離樹均勻覆蓋整個網(wǎng)絡(luò)并交替進行工作,不工作時則進入休眠狀態(tài)以節(jié)省能量。在數(shù)據(jù)轉(zhuǎn)發(fā)階段,分離樹中的節(jié)點有方向性地將數(shù)據(jù)轉(zhuǎn)發(fā)到匯聚節(jié)點,有效避免環(huán)路和回傳,從而大幅度降低了冗余數(shù)據(jù)的轉(zhuǎn)發(fā)。
關(guān)鍵詞:無線傳感網(wǎng) 分離樹 能量利用率 休眠狀態(tài) 數(shù)據(jù)冗余
吳晨
女,碩士研究生,重慶郵電大學(xué)。
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)是由大量帶有感知、檢測和處理功能的傳感器節(jié)點組成,但這些節(jié)點被布置在監(jiān)測區(qū)域,可以以自組織的方式形成無線網(wǎng)絡(luò)[1]。無線傳感器網(wǎng)絡(luò)在環(huán)境監(jiān)測、救援、生物醫(yī)學(xué)和智能家居等領(lǐng)域有廣泛的應(yīng)用[2]。傳感器節(jié)點是由電池供電,由于其部署場景的特殊性,使得不易補給,因此,合理高效的利用傳感器節(jié)點有限的能量極為重要[3]。而在傳統(tǒng)的通信方式中,每個傳感器節(jié)點將采集的信息直接以廣播的形式發(fā)送到匯聚節(jié)點,由于傳感器節(jié)點數(shù)量龐大、分布較密集,由此會產(chǎn)生頻繁的碰撞和沖突,導(dǎo)致廣播風(fēng)暴問題(Broadcast Storm Problem)[4]。各節(jié)點冗余數(shù)據(jù)較多,通信負(fù)載重,無謂消耗了寶貴的能量資源。
針對以上問題,國內(nèi)外學(xué)者已做大量研究。如文獻[5]中的概率廣播是研究較多的一種解決辦法,主要思想是一個節(jié)點在收到廣播消息之后以概率P進行轉(zhuǎn)播,但概率值的設(shè)定是一個NP問題,應(yīng)根據(jù)網(wǎng)絡(luò)情況動態(tài)的設(shè)置概率值的大小。文獻[6]中提出了一種基于計數(shù)器的方法,節(jié)點收到一個廣播消息后,發(fā)起一個計數(shù)器,并設(shè)初值為1,閾值為C,設(shè)置一個隨機等待時延,在等待時間段內(nèi),節(jié)點每收到一個副本消息計數(shù)器的值就加1,如果節(jié)點收到重復(fù)消息的數(shù)量小于C,就進行轉(zhuǎn)發(fā),否則,丟棄此消息。文獻[7]中提出構(gòu)建一個由連通支配集CDS(connected dominating set)構(gòu)成的主干網(wǎng),主干網(wǎng)中的節(jié)點稱為支配點,負(fù)責(zé)路由表的計算和維護、消息的收集和轉(zhuǎn)發(fā);網(wǎng)絡(luò)中其它節(jié)點稱為被支配點,主要負(fù)責(zé)信息的采集。通過構(gòu)造主干網(wǎng)使得消息限制在網(wǎng)絡(luò)的一小部分節(jié)點間轉(zhuǎn)發(fā),有效地減少了產(chǎn)生廣播風(fēng)暴的機率,而在任意圖中求解最小連通支配集是NP問題。分簇路由具有拓?fù)涔芾矸奖恪⒛芰坷酶咝?、?shù)據(jù)融合簡單等優(yōu)點,它是另外一種經(jīng)典的分層結(jié)構(gòu)路由協(xié)議,成為當(dāng)前重點研究的路由技術(shù)[8]。在分簇的拓?fù)涔芾頇C制下,網(wǎng)絡(luò)中的節(jié)點可以劃分為簇頭節(jié)點和成員節(jié)點兩類。在每個簇內(nèi),根據(jù)一定的機制算法選取某個節(jié)點作為簇頭,用于管理或控制整個簇內(nèi)成員節(jié)點,協(xié)調(diào)成員節(jié)點之間的工作,負(fù)責(zé)簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇間轉(zhuǎn)發(fā)。分簇算法中簇的構(gòu)建過程開銷大,簇頭節(jié)點通信任務(wù)重,會導(dǎo)致節(jié)點能耗不均。
以上這些方法雖然能夠一定程度上降低廣播風(fēng)暴發(fā)生概率,節(jié)約節(jié)點能量,但是需要所有節(jié)點均參與數(shù)據(jù)采集與轉(zhuǎn)發(fā),鄰居節(jié)點間的冗余數(shù)據(jù)較多,并且一次數(shù)據(jù)傳輸過程只能收集一種數(shù)據(jù)。本文的基于分離樹數(shù)據(jù)轉(zhuǎn)發(fā)機制,以匯聚節(jié)點為根節(jié)點來建立m顆均勻覆蓋整個網(wǎng)絡(luò)的分離樹,當(dāng)僅需采集一種數(shù)據(jù)時,僅其中一棵樹負(fù)責(zé)數(shù)據(jù)收集與轉(zhuǎn)發(fā),極大地減少了冗余數(shù)據(jù)量,其他樹中的節(jié)點則進行休眠,節(jié)約能耗。當(dāng)需要同時采集兩種或多種數(shù)據(jù)時(如溫度、濕度、光照等),多棵樹同時工作,分別各自采集不同數(shù)據(jù),這樣匯聚節(jié)點可以實現(xiàn)同時采集到多種數(shù)據(jù)。
2.1基本思想
本文所提出的機制主要思想是從匯聚節(jié)點開始構(gòu)建m個無交集的生成樹,m棵樹中的節(jié)點均勻分布在整個網(wǎng)絡(luò)。由于網(wǎng)絡(luò)節(jié)點分布較密集,鄰居節(jié)點之間采集的信息有很大的相似性和冗余性,因此在通信過程中,m棵樹交替進行通信任務(wù),其余的則處于休眠狀態(tài),能保證實現(xiàn)信息采集的目的的同時,節(jié)省更多能量。另一方面,由于樹形結(jié)構(gòu)的特殊性,各節(jié)點保存有父節(jié)點、子節(jié)點信息,因此在數(shù)據(jù)轉(zhuǎn)發(fā)過程中,可以保證數(shù)據(jù)有方向的傳送到匯聚節(jié)點,能有效避免環(huán)路和消息回傳的產(chǎn)生,同時消息碰撞的概率大大降低,緩解了廣播風(fēng)暴問題。
2.2網(wǎng)絡(luò)模型
為了簡化網(wǎng)絡(luò)模型,本文做了如下假設(shè):
(1)網(wǎng)絡(luò)中共有N個節(jié)點隨機部署在m*m的區(qū)域內(nèi);
(2)所有節(jié)點和匯聚節(jié)點一旦部署完畢處于靜止暫態(tài);
(3)節(jié)點可通過功率控制來調(diào)整發(fā)射功率;
(4)每個節(jié)點有唯一的id號;
(5)匯聚節(jié)點位于監(jiān)測區(qū)域外,并且能量不受限。
2.3分離樹的構(gòu)建
這里以m=2為例詳細(xì)說明分離樹的構(gòu)建過程。構(gòu)建過程中通過給節(jié)點標(biāo)記不同顏色(深色和淺色)來區(qū)分兩棵樹,除了匯聚節(jié)點每個節(jié)點充當(dāng)三種角色中的一個:深色節(jié)點、淺色節(jié)點,孤立節(jié)點。匯聚節(jié)點是深色、淺色兩個生成樹的共同節(jié)點,因此它可看做既是深色節(jié)點也是淺色節(jié)點。其構(gòu)建過程如下:首先由匯聚節(jié)點廣播一個hello消息給所有鄰居,收到此hello消息的鄰居節(jié)點隨機地給自己標(biāo)記深色、淺色(如圖1(a))。然后深色、淺色節(jié)點分別廣播red-hello、blue-hello給鄰居節(jié)點。一個節(jié)點一旦收到至少一個來自淺色或深色節(jié)點的hello消息,此節(jié)點將等待一段時間T來接受足夠的hello消息,然后根據(jù)這些鄰居的顏色再決定其自身顏色,以概率pr成為深色節(jié)點、pb成為淺色節(jié)點以概率成為葉節(jié)點。為了使更多的節(jié)點收到來自深色和淺色節(jié)點的hello消息,需要在給定鄰居情況下平衡兩種節(jié)點。因此,如果一個節(jié)點的淺色鄰居節(jié)點比深色多,那么此節(jié)點以更大概率選擇成為深色;如果一個節(jié)點的深色鄰居節(jié)點比淺色多,那么此節(jié)點更可能選擇標(biāo)記為淺色。一個節(jié)點通過接收到的red-hello、blue-hello消息估計兩種顏色的鄰居節(jié)點數(shù)量,并選擇它自己的顏色保證其他節(jié)點最大可能的接收到兩種顏色的節(jié)點消息。若一個節(jié)點沒有收到任何hello消息,表示此節(jié)點既不能標(biāo)記為淺色也不能標(biāo)記深色,成為孤立節(jié)點。當(dāng)所有節(jié)點均選定自己角色之后,建立起了深色、淺色兩顆以匯聚節(jié)點為根節(jié)點的分離樹(如圖1(b))。
圖1 分離樹的構(gòu)建過程
為了保證盡量多的節(jié)點參與路由,希望所選的分離樹盡可能大并覆蓋整個網(wǎng)絡(luò),需要采取合適的策略來決定的值,如果收到很少的hello消息,則應(yīng)該大一點,這樣可以得到更大覆蓋的樹。如果節(jié)點收到red-hello比blue-hello多,為了平衡兩種顏色此節(jié)點將會有更大的機會成為淺色節(jié)點。因此,由公式(1)(2)來計算pr、pb:
其中,Nred、Nblue分別表示收到的red-hello、blue-hello消息的數(shù)量;p是一個節(jié)點成為非葉子節(jié)點的概率,為了保證網(wǎng)絡(luò)全覆蓋,這里設(shè)置,即所建立的分離樹能夠完全覆蓋整個網(wǎng)絡(luò)。
2.4數(shù)據(jù)轉(zhuǎn)發(fā)過程
當(dāng)分離樹建立起之后,則可以開始數(shù)據(jù)傳輸過程,為了實現(xiàn)m顆分離樹分開各自通信,不同顏色節(jié)點互相不允許轉(zhuǎn)發(fā)彼此的消息。如果一個節(jié)點成為了淺色或是深色節(jié)點,他就會加入相應(yīng)的樹并轉(zhuǎn)發(fā)消息給它的父節(jié)點。當(dāng)采集單一數(shù)據(jù)時,分離樹交替工作,不工作的分離樹中的節(jié)點進入休眠狀態(tài)。工作狀態(tài)的節(jié)點將自己采集的數(shù)據(jù)和子節(jié)點發(fā)來的數(shù)據(jù)進行融合,然后發(fā)送給父節(jié)點,直到消息到達匯聚節(jié)點。當(dāng)需采集n(m≥ n)種數(shù)據(jù)時,任意n棵分離樹執(zhí)行通信任務(wù),其余進行休眠;當(dāng)其中某一分離樹由于節(jié)點能量耗盡而不能繼續(xù)任務(wù)時,則休眠的分離樹進行喚醒,繼續(xù)此中斷任務(wù),由此保證通信質(zhì)量。
為了研究本文所提出機制的有效性,用OMNeT++仿真軟件對此進行驗證,在相同實驗條件下,對比傳統(tǒng)的廣播方式和本文的機制,主要對比網(wǎng)絡(luò)中網(wǎng)絡(luò)開銷和節(jié)點能耗情況。
仿真參數(shù)設(shè)置如表1:
表1 仿真參數(shù)的設(shè)置
(1)廣播風(fēng)暴發(fā)生概率
圖2反映了廣播風(fēng)暴發(fā)生概率隨著節(jié)點數(shù)的變化趨勢,可見本文的分離樹機制性能相比廣播方式有明顯提高,主要原因是本文建立的兩顆分離樹交替工作,參與的節(jié)點數(shù)量有所減少,冗余數(shù)據(jù)大大減少;另外在數(shù)據(jù)轉(zhuǎn)發(fā)過程中,節(jié)點有方向性的將數(shù)據(jù)發(fā)給自己的父節(jié)點,碰撞的概率大大降低,廣播風(fēng)暴問題得到明顯緩解。
圖2 廣播風(fēng)暴發(fā)生概率隨著節(jié)點數(shù)的變化趨勢
(2)節(jié)點能耗情況
圖3反映了節(jié)點每一輪結(jié)束時剩余能量的變化情況,從圖中可以看出本文所提機制變化趨勢較平緩,即節(jié)點耗能速度較慢,主要是因為網(wǎng)絡(luò)中冗余數(shù)據(jù)大大減少,節(jié)點能量利用率得到提高;同時節(jié)點周期性的工作通信量有所降低,有助減少節(jié)點耗能;此外,節(jié)點在數(shù)據(jù)轉(zhuǎn)發(fā)過程中,每個節(jié)點都會對數(shù)據(jù)進行融合處理,使得數(shù)據(jù)包較小,減小了傳輸能耗。
圖3 節(jié)點剩余能量平均值隨運行時間的變化曲線
本文提出的基于分離樹的能量有效數(shù)據(jù)轉(zhuǎn)發(fā)機制利用以匯聚節(jié)點為根節(jié)點來建立m個均勻覆蓋整個網(wǎng)絡(luò)的分離樹,實現(xiàn)進一步降低能耗,還能同時采集多種數(shù)據(jù)。由于網(wǎng)絡(luò)節(jié)點分布密集,鄰居節(jié)點之間的感測數(shù)據(jù)有很大的相似性,故分離樹交替執(zhí)行通信任務(wù),完成通信目的,不工作時,使其處于休眠狀態(tài)以節(jié)省更多能耗。此外利用樹形結(jié)構(gòu)的特殊性,在數(shù)據(jù)轉(zhuǎn)發(fā)階段,有方向性的將數(shù)據(jù)以最短路徑發(fā)送給匯聚節(jié)點,使節(jié)點能量得到高效利用。仿真實驗表明,本文的機制能有效緩解廣播風(fēng)暴問題,實現(xiàn)了節(jié)能,節(jié)點能量利用率大大提高。
參考文獻
1Yu J,Wang N,Wang G,et al.Connected dominating sets in wireless ad hoc and sensor networks–A comprehensive survey[J].Computer Communications,2013,36(2):121-134
2Pantazis N,Nikolidakis S A,Vergados D D.Energy-efficient routing protocols in wireless sensor networks:A survey[J].Communications Surveys & Tutorials,IEEE,2013,15(2):551-591
3Kuila P,Jana P K.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014,33:127-140
4Tseng Y C,Ni S Y,Chen Y S,et al.The broadcast storm problem in a mobile ad hoc network[J].Wireless networks,2002,8(2-3):153-167
5Hanashi A M,Siddique A,Awan I,et al.Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc networks[J].Simulation Modelling Practice and Theory,2009,17(2):364-375
6Yassein M B,Nimer S F,Al-Dubai A Y.A new dynamic counter-based broadcasting scheme for Mobile Ad hoc Networks[J].Simulation Modelling Practice and Theory,2011,19(1):553-563
7凌飛,吳振華.能量均衡的最小連通支配集分布式算法[J].傳感技術(shù)學(xué)報,2013,25(9):1316-1321
8Liu X.A survey on clustering routing protocols in wireless sensor networks[J].Sensors,2012,12(8):11113-11153
收稿日期:(2016-02-03)
基金項目:國家物聯(lián)網(wǎng)專項(工信部科函[2014]351號)
DOI:10.3969/j.issn.1006-6403.2016.03.015