［吳晨］

?

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

［吳晨］

摘要

在無線傳感網(wǎng)中，由于傳感器節(jié)點(diǎn)能量極度受限，而傳統(tǒng)的廣播通信方式會(huì)產(chǎn)生很大的數(shù)據(jù)冗余，因而造成能量利用率較低。文章通過建立以匯聚節(jié)點(diǎn)為根節(jié)點(diǎn)的分離樹來解決以上問題，m顆分離樹均勻覆蓋整個(gè)網(wǎng)絡(luò)并交替進(jìn)行工作，不工作時(shí)則進(jìn)入休眠狀態(tài)以節(jié)省能量。在數(shù)據(jù)轉(zhuǎn)發(fā)階段，分離樹中的節(jié)點(diǎn)有方向性地將數(shù)據(jù)轉(zhuǎn)發(fā)到匯聚節(jié)點(diǎn)，有效避免環(huán)路和回傳，從而大幅度降低了冗余數(shù)據(jù)的轉(zhuǎn)發(fā)。

關(guān)鍵詞：無線傳感網(wǎng) 分離樹 能量利用率 休眠狀態(tài) 數(shù)據(jù)冗余

吳晨

女，碩士研究生，重慶郵電大學(xué)。

引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs)是由大量帶有感知、檢測(cè)和處理功能的傳感器節(jié)點(diǎn)組成，但這些節(jié)點(diǎn)被布置在監(jiān)測(cè)區(qū)域，可以以自組織的方式形成無線網(wǎng)絡(luò)[1]。無線傳感器網(wǎng)絡(luò)在環(huán)境監(jiān)測(cè)、救援、生物醫(yī)學(xué)和智能家居等領(lǐng)域有廣泛的應(yīng)用[2]。傳感器節(jié)點(diǎn)是由電池供電，由于其部署場(chǎng)景的特殊性，使得不易補(bǔ)給，因此，合理高效的利用傳感器節(jié)點(diǎn)有限的能量極為重要[3]。而在傳統(tǒng)的通信方式中，每個(gè)傳感器節(jié)點(diǎn)將采集的信息直接以廣播的形式發(fā)送到匯聚節(jié)點(diǎn)，由于傳感器節(jié)點(diǎn)數(shù)量龐大、分布較密集，由此會(huì)產(chǎn)生頻繁的碰撞和沖突，導(dǎo)致廣播風(fēng)暴問題(Broadcast Storm Problem)[4]。各節(jié)點(diǎn)冗余數(shù)據(jù)較多，通信負(fù)載重，無謂消耗了寶貴的能量資源。

1　相關(guān)工作

針對(duì)以上問題，國(guó)內(nèi)外學(xué)者已做大量研究。如文獻(xiàn)[5]中的概率廣播是研究較多的一種解決辦法，主要思想是一個(gè)節(jié)點(diǎn)在收到廣播消息之后以概率P進(jìn)行轉(zhuǎn)播，但概率值的設(shè)定是一個(gè)NP問題，應(yīng)根據(jù)網(wǎng)絡(luò)情況動(dòng)態(tài)的設(shè)置概率值的大小。文獻(xiàn)[6]中提出了一種基于計(jì)數(shù)器的方法，節(jié)點(diǎn)收到一個(gè)廣播消息后，發(fā)起一個(gè)計(jì)數(shù)器，并設(shè)初值為1，閾值為C，設(shè)置一個(gè)隨機(jī)等待時(shí)延，在等待時(shí)間段內(nèi)，節(jié)點(diǎn)每收到一個(gè)副本消息計(jì)數(shù)器的值就加1，如果節(jié)點(diǎn)收到重復(fù)消息的數(shù)量小于C，就進(jìn)行轉(zhuǎn)發(fā)，否則，丟棄此消息。文獻(xiàn)[7]中提出構(gòu)建一個(gè)由連通支配集CDS（connected dominating set）構(gòu)成的主干網(wǎng)，主干網(wǎng)中的節(jié)點(diǎn)稱為支配點(diǎn)，負(fù)責(zé)路由表的計(jì)算和維護(hù)、消息的收集和轉(zhuǎn)發(fā)；網(wǎng)絡(luò)中其它節(jié)點(diǎn)稱為被支配點(diǎn)，主要負(fù)責(zé)信息的采集。通過構(gòu)造主干網(wǎng)使得消息限制在網(wǎng)絡(luò)的一小部分節(jié)點(diǎn)間轉(zhuǎn)發(fā)，有效地減少了產(chǎn)生廣播風(fēng)暴的機(jī)率，而在任意圖中求解最小連通支配集是NP問題。分簇路由具有拓?fù)涔芾矸奖?、能量利用高效、?shù)據(jù)融合簡(jiǎn)單等優(yōu)點(diǎn)，它是另外一種經(jīng)典的分層結(jié)構(gòu)路由協(xié)議，成為當(dāng)前重點(diǎn)研究的路由技術(shù)[8]。在分簇的拓?fù)涔芾頇C(jī)制下，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以劃分為簇頭節(jié)點(diǎn)和成員節(jié)點(diǎn)兩類。在每個(gè)簇內(nèi)，根據(jù)一定的機(jī)制算法選取某個(gè)節(jié)點(diǎn)作為簇頭，用于管理或控制整個(gè)簇內(nèi)成員節(jié)點(diǎn)，協(xié)調(diào)成員節(jié)點(diǎn)之間的工作，負(fù)責(zé)簇內(nèi)信息的收集和數(shù)據(jù)的融合處理以及簇間轉(zhuǎn)發(fā)。分簇算法中簇的構(gòu)建過程開銷大，簇頭節(jié)點(diǎn)通信任務(wù)重，會(huì)導(dǎo)致節(jié)點(diǎn)能耗不均。

以上這些方法雖然能夠一定程度上降低廣播風(fēng)暴發(fā)生概率，節(jié)約節(jié)點(diǎn)能量，但是需要所有節(jié)點(diǎn)均參與數(shù)據(jù)采集與轉(zhuǎn)發(fā)，鄰居節(jié)點(diǎn)間的冗余數(shù)據(jù)較多，并且一次數(shù)據(jù)傳輸過程只能收集一種數(shù)據(jù)。本文的基于分離樹數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制，以匯聚節(jié)點(diǎn)為根節(jié)點(diǎn)來建立m顆均勻覆蓋整個(gè)網(wǎng)絡(luò)的分離樹，當(dāng)僅需采集一種數(shù)據(jù)時(shí)，僅其中一棵樹負(fù)責(zé)數(shù)據(jù)收集與轉(zhuǎn)發(fā)，極大地減少了冗余數(shù)據(jù)量，其他樹中的節(jié)點(diǎn)則進(jìn)行休眠，節(jié)約能耗。當(dāng)需要同時(shí)采集兩種或多種數(shù)據(jù)時(shí)（如溫度、濕度、光照等），多棵樹同時(shí)工作，分別各自采集不同數(shù)據(jù)，這樣匯聚節(jié)點(diǎn)可以實(shí)現(xiàn)同時(shí)采集到多種數(shù)據(jù)。

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

2.1基本思想

本文所提出的機(jī)制主要思想是從匯聚節(jié)點(diǎn)開始構(gòu)建m個(gè)無交集的生成樹，m棵樹中的節(jié)點(diǎn)均勻分布在整個(gè)網(wǎng)絡(luò)。由于網(wǎng)絡(luò)節(jié)點(diǎn)分布較密集，鄰居節(jié)點(diǎn)之間采集的信息有很大的相似性和冗余性，因此在通信過程中，m棵樹交替進(jìn)行通信任務(wù)，其余的則處于休眠狀態(tài)，能保證實(shí)現(xiàn)信息采集的目的的同時(shí)，節(jié)省更多能量。另一方面，由于樹形結(jié)構(gòu)的特殊性，各節(jié)點(diǎn)保存有父節(jié)點(diǎn)、子節(jié)點(diǎn)信息，因此在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，可以保證數(shù)據(jù)有方向的傳送到匯聚節(jié)點(diǎn)，能有效避免環(huán)路和消息回傳的產(chǎn)生，同時(shí)消息碰撞的概率大大降低，緩解了廣播風(fēng)暴問題。

2.2網(wǎng)絡(luò)模型

為了簡(jiǎn)化網(wǎng)絡(luò)模型，本文做了如下假設(shè)：

（1）網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)隨機(jī)部署在m*m的區(qū)域內(nèi)；

（2）所有節(jié)點(diǎn)和匯聚節(jié)點(diǎn)一旦部署完畢處于靜止暫態(tài)；

（3）節(jié)點(diǎn)可通過功率控制來調(diào)整發(fā)射功率；

（4）每個(gè)節(jié)點(diǎn)有唯一的id號(hào)；

（5）匯聚節(jié)點(diǎn)位于監(jiān)測(cè)區(qū)域外，并且能量不受限。

2.3分離樹的構(gòu)建

這里以m=2為例詳細(xì)說明分離樹的構(gòu)建過程。構(gòu)建過程中通過給節(jié)點(diǎn)標(biāo)記不同顏色（深色和淺色）來區(qū)分兩棵樹，除了匯聚節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)充當(dāng)三種角色中的一個(gè)：深色節(jié)點(diǎn)、淺色節(jié)點(diǎn)，孤立節(jié)點(diǎn)。匯聚節(jié)點(diǎn)是深色、淺色兩個(gè)生成樹的共同節(jié)點(diǎn)，因此它可看做既是深色節(jié)點(diǎn)也是淺色節(jié)點(diǎn)。其構(gòu)建過程如下：首先由匯聚節(jié)點(diǎn)廣播一個(gè)hello消息給所有鄰居，收到此hello消息的鄰居節(jié)點(diǎn)隨機(jī)地給自己標(biāo)記深色、淺色（如圖1（a））。然后深色、淺色節(jié)點(diǎn)分別廣播red-hello、blue-hello給鄰居節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)一旦收到至少一個(gè)來自淺色或深色節(jié)點(diǎn)的hello消息，此節(jié)點(diǎn)將等待一段時(shí)間T來接受足夠的hello消息，然后根據(jù)這些鄰居的顏色再?zèng)Q定其自身顏色，以概率pr成為深色節(jié)點(diǎn)、pb成為淺色節(jié)點(diǎn)以概率成為葉節(jié)點(diǎn)。為了使更多的節(jié)點(diǎn)收到來自深色和淺色節(jié)點(diǎn)的hello消息，需要在給定鄰居情況下平衡兩種節(jié)點(diǎn)。因此，如果一個(gè)節(jié)點(diǎn)的淺色鄰居節(jié)點(diǎn)比深色多，那么此節(jié)點(diǎn)以更大概率選擇成為深色；如果一個(gè)節(jié)點(diǎn)的深色鄰居節(jié)點(diǎn)比淺色多，那么此節(jié)點(diǎn)更可能選擇標(biāo)記為淺色。一個(gè)節(jié)點(diǎn)通過接收到的red-hello、blue-hello消息估計(jì)兩種顏色的鄰居節(jié)點(diǎn)數(shù)量，并選擇它自己的顏色保證其他節(jié)點(diǎn)最大可能的接收到兩種顏色的節(jié)點(diǎn)消息。若一個(gè)節(jié)點(diǎn)沒有收到任何hello消息，表示此節(jié)點(diǎn)既不能標(biāo)記為淺色也不能標(biāo)記深色，成為孤立節(jié)點(diǎn)。當(dāng)所有節(jié)點(diǎn)均選定自己角色之后，建立起了深色、淺色兩顆以匯聚節(jié)點(diǎn)為根節(jié)點(diǎn)的分離樹（如圖1（b））。

圖1　分離樹的構(gòu)建過程

為了保證盡量多的節(jié)點(diǎn)參與路由，希望所選的分離樹盡可能大并覆蓋整個(gè)網(wǎng)絡(luò)，需要采取合適的策略來決定的值，如果收到很少的hello消息，則應(yīng)該大一點(diǎn)，這樣可以得到更大覆蓋的樹。如果節(jié)點(diǎn)收到red-hello比blue-hello多，為了平衡兩種顏色此節(jié)點(diǎn)將會(huì)有更大的機(jī)會(huì)成為淺色節(jié)點(diǎn)。因此，由公式（1）（2）來計(jì)算pr、pb:

其中，Nred、Nblue分別表示收到的red-hello、blue-hello消息的數(shù)量；p是一個(gè)節(jié)點(diǎn)成為非葉子節(jié)點(diǎn)的概率，為了保證網(wǎng)絡(luò)全覆蓋，這里設(shè)置，即所建立的分離樹能夠完全覆蓋整個(gè)網(wǎng)絡(luò)。

2.4數(shù)據(jù)轉(zhuǎn)發(fā)過程

當(dāng)分離樹建立起之后，則可以開始數(shù)據(jù)傳輸過程，為了實(shí)現(xiàn)m顆分離樹分開各自通信，不同顏色節(jié)點(diǎn)互相不允許轉(zhuǎn)發(fā)彼此的消息。如果一個(gè)節(jié)點(diǎn)成為了淺色或是深色節(jié)點(diǎn)，他就會(huì)加入相應(yīng)的樹并轉(zhuǎn)發(fā)消息給它的父節(jié)點(diǎn)。當(dāng)采集單一數(shù)據(jù)時(shí)，分離樹交替工作，不工作的分離樹中的節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。工作狀態(tài)的節(jié)點(diǎn)將自己采集的數(shù)據(jù)和子節(jié)點(diǎn)發(fā)來的數(shù)據(jù)進(jìn)行融合，然后發(fā)送給父節(jié)點(diǎn)，直到消息到達(dá)匯聚節(jié)點(diǎn)。當(dāng)需采集n（m≥ n）種數(shù)據(jù)時(shí)，任意n棵分離樹執(zhí)行通信任務(wù)，其余進(jìn)行休眠；當(dāng)其中某一分離樹由于節(jié)點(diǎn)能量耗盡而不能繼續(xù)任務(wù)時(shí)，則休眠的分離樹進(jìn)行喚醒，繼續(xù)此中斷任務(wù)，由此保證通信質(zhì)量。

3　仿真分析

為了研究本文所提出機(jī)制的有效性，用OMNeT++仿真軟件對(duì)此進(jìn)行驗(yàn)證，在相同實(shí)驗(yàn)條件下，對(duì)比傳統(tǒng)的廣播方式和本文的機(jī)制，主要對(duì)比網(wǎng)絡(luò)中網(wǎng)絡(luò)開銷和節(jié)點(diǎn)能耗情況。

仿真參數(shù)設(shè)置如表1：

表1　仿真參數(shù)的設(shè)置

（1）廣播風(fēng)暴發(fā)生概率

圖2反映了廣播風(fēng)暴發(fā)生概率隨著節(jié)點(diǎn)數(shù)的變化趨勢(shì)，可見本文的分離樹機(jī)制性能相比廣播方式有明顯提高，主要原因是本文建立的兩顆分離樹交替工作，參與的節(jié)點(diǎn)數(shù)量有所減少，冗余數(shù)據(jù)大大減少；另外在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，節(jié)點(diǎn)有方向性的將數(shù)據(jù)發(fā)給自己的父節(jié)點(diǎn)，碰撞的概率大大降低，廣播風(fēng)暴問題得到明顯緩解。

圖2　廣播風(fēng)暴發(fā)生概率隨著節(jié)點(diǎn)數(shù)的變化趨勢(shì)

（2）節(jié)點(diǎn)能耗情況

圖3反映了節(jié)點(diǎn)每一輪結(jié)束時(shí)剩余能量的變化情況，從圖中可以看出本文所提機(jī)制變化趨勢(shì)較平緩，即節(jié)點(diǎn)耗能速度較慢，主要是因?yàn)榫W(wǎng)絡(luò)中冗余數(shù)據(jù)大大減少，節(jié)點(diǎn)能量利用率得到提高；同時(shí)節(jié)點(diǎn)周期性的工作通信量有所降低，有助減少節(jié)點(diǎn)耗能；此外，節(jié)點(diǎn)在數(shù)據(jù)轉(zhuǎn)發(fā)過程中，每個(gè)節(jié)點(diǎn)都會(huì)對(duì)數(shù)據(jù)進(jìn)行融合處理，使得數(shù)據(jù)包較小，減小了傳輸能耗。

圖3　節(jié)點(diǎn)剩余能量平均值隨運(yùn)行時(shí)間的變化曲線

4　總結(jié)

本文提出的基于分離樹的能量有效數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制利用以匯聚節(jié)點(diǎn)為根節(jié)點(diǎn)來建立m個(gè)均勻覆蓋整個(gè)網(wǎng)絡(luò)的分離樹，實(shí)現(xiàn)進(jìn)一步降低能耗，還能同時(shí)采集多種數(shù)據(jù)。由于網(wǎng)絡(luò)節(jié)點(diǎn)分布密集，鄰居節(jié)點(diǎn)之間的感測(cè)數(shù)據(jù)有很大的相似性，故分離樹交替執(zhí)行通信任務(wù)，完成通信目的，不工作時(shí)，使其處于休眠狀態(tài)以節(jié)省更多能耗。此外利用樹形結(jié)構(gòu)的特殊性，在數(shù)據(jù)轉(zhuǎn)發(fā)階段，有方向性的將數(shù)據(jù)以最短路徑發(fā)送給匯聚節(jié)點(diǎn)，使節(jié)點(diǎn)能量得到高效利用。仿真實(shí)驗(yàn)表明，本文的機(jī)制能有效緩解廣播風(fēng)暴問題，實(shí)現(xiàn)了節(jié)能，節(jié)點(diǎn)能量利用率大大提高。

參考文獻(xiàn)

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é)報(bào),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）

基金項(xiàng)目：國(guó)家物聯(lián)網(wǎng)專項(xiàng)(工信部科函[2014]351號(hào))

DOI:10.3969/j.issn.1006-6403.2016.03.015