基于分離樹的能量有效數(shù)據(jù)轉(zhuǎn)發(fā)機制*

［吳晨］

?

基于分離樹的能量有效數(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ù)載重，無謂消耗了寶貴的能量資源。

1　相關(guān)工作

針對以上問題，國內(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　基于分離樹的能量有效數(shù)據(jù)轉(zhuǎn)發(fā)機制

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ì)量。

3　仿真分析

為了研究本文所提出機制的有效性，用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é)點剩余能量平均值隨運行時間的變化曲線

4　總結(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