WSN中基于樹的負(fù)載均衡的數(shù)據(jù)收集算法*

劉正波,朱 亮

(1.石家莊郵電職業(yè)技術(shù)學(xué)院電信工程系移動通信教研室,石家莊 050000;2.河北大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院,河北 保定 071002)

WSN中基于樹的負(fù)載均衡的數(shù)據(jù)收集算法*

劉正波1*,朱 亮2

(1.石家莊郵電職業(yè)技術(shù)學(xué)院電信工程系移動通信教研室,石家莊 050000;2.河北大學(xué)數(shù)學(xué)與計算機(jī)學(xué)院,河北 保定 071002)

部署無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)的根本目的在于數(shù)據(jù)收集。然而,節(jié)點能量有限特性給具有低能耗的數(shù)據(jù)收集算法的設(shè)計提出了挑戰(zhàn)。為此,提出基于樹的負(fù)載均衡的數(shù)據(jù)收集TLBDG(Tree-based Load Balanced Data Gathering)算法。TLBDG算法構(gòu)建了一棵以基站為根的負(fù)載均衡的數(shù)據(jù)收集樹,并以最小跳數(shù)路徑轉(zhuǎn)發(fā)數(shù)據(jù)包。TLBDG算法具體思想為:先依據(jù)節(jié)點離基站的跳數(shù)形成層次結(jié)構(gòu),然后再生成以基站為根的樹型數(shù)據(jù)傳輸路道。實驗結(jié)果表明,提出的TLBDG算法能夠均衡負(fù)載,并延長生命周期。

網(wǎng)絡(luò);數(shù)據(jù)收集;樹;負(fù)載均衡;跳數(shù)

近期,無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)已成為國內(nèi)外關(guān)注的熱點。通過融合傳感器技術(shù)、通信技術(shù)和分布式信息處理技術(shù),WSNs能實時感測數(shù)據(jù)環(huán)境數(shù)據(jù),達(dá)到監(jiān)測環(huán)境的目的[1]。

WSNs由海量的微型、低功耗的傳感節(jié)點組成,這些節(jié)點具有感測、傳輸數(shù)據(jù)能力。當(dāng)傳感節(jié)點感測數(shù)據(jù)后,就將數(shù)據(jù)向基站(Sink)傳輸,即Sink收集數(shù)據(jù)。

因此,數(shù)據(jù)收集是無線傳感網(wǎng)絡(luò)的重點工作。每個傳感節(jié)點周期感測數(shù)據(jù),然后以多跳方式傳輸至基站,這一過程稱為數(shù)據(jù)收集(data gathering)。現(xiàn)有的數(shù)據(jù)收集算法有基于簇、基于鏈路和基于樹3種收集算法。

基于簇的數(shù)據(jù)收集算法是指將網(wǎng)絡(luò)內(nèi)節(jié)點依據(jù)某些指標(biāo),如距離、能量,劃分為多個群(簇)。每個簇內(nèi)產(chǎn)生一個簇頭,由它負(fù)責(zé)將簇內(nèi)信息傳輸至基站,典型的算法有:LEACH[2]、HEED[3]和CEDA[4]等。而基于鏈的數(shù)據(jù)收集算法是將網(wǎng)絡(luò)內(nèi)所有節(jié)點構(gòu)成一條鏈,并在鏈上產(chǎn)生一個節(jié)點與基站通信,典型的算法有:CCS[5]、DRAEM[6]。

而基于樹的數(shù)據(jù)收集算法是將所有節(jié)點構(gòu)成一棵生成樹,并由基站作為根節(jié)點。節(jié)點將數(shù)據(jù)傳輸至父節(jié)點。每個節(jié)點均依據(jù)這一原則轉(zhuǎn)發(fā)數(shù)據(jù),最終基站將接收到網(wǎng)絡(luò)內(nèi)所有數(shù)據(jù)。與基于簇和基于鏈的拓?fù)浣Y(jié)構(gòu)相比,基于樹的拓?fù)浣Y(jié)構(gòu)具有最小圖的連通圖,并具有高的連通性和可靠性,已被廣泛應(yīng)用。

典型的基于樹的數(shù)據(jù)收集算法,有PEDAP[7]、MLDGA[8]、MNL[9]和MAXLAT[10]。PEDAP算法先生成只含有基站的樹,然后以節(jié)點權(quán)值為標(biāo)準(zhǔn),據(jù)此選擇節(jié)點加入樹,進(jìn)而構(gòu)成一棵樹。而PEDAP-AP算法在構(gòu)成樹是考慮了節(jié)點本身的剩余能量。盡管如此,但PEDAP和PEDAP-AP兩個算法所生成的樹中,各子樹節(jié)點數(shù)不均勻,使它們的能耗不平衡。

而文獻(xiàn)[8]提出了基于PEDAP的改進(jìn)算法MLDGA。MLDGA算法改進(jìn)了PEDAP的權(quán)值,該權(quán)值融入了樹的生命周期。但是,MLDGA算法生成樹仍不均衡,而且需要頻繁更換樹結(jié)構(gòu),增加網(wǎng)絡(luò)開銷。

文獻(xiàn)[11]提出MNL算法,MNL算法是以節(jié)點剩余能量為指標(biāo),構(gòu)造生成樹,它的思路與MLDGA類似。而MAXLAT算法是最大化生命周期為目標(biāo)構(gòu)造樹,同時避開了能量瓶頸節(jié)點。但是該算法需要將網(wǎng)絡(luò)內(nèi)所有信息集中到基站,這增加了通信開銷。

為此,本文提出基于樹的負(fù)載均衡的數(shù)據(jù)收集算法TLBDG(Tree-based Load Balanced Data Gathering)。TLBDG通過選擇最小跳數(shù),構(gòu)建負(fù)載均衡的生成樹。實驗數(shù)據(jù)表明,提出的TLBDG算法能夠有效地通過平衡負(fù)載,降低能耗,延長網(wǎng)絡(luò)的生命周期。

1 網(wǎng)絡(luò)模型及問題描述

現(xiàn)有的數(shù)據(jù)收集算法是針對單跳網(wǎng)絡(luò)。單跳網(wǎng)絡(luò)中的節(jié)點都能以直接通信方式與其他節(jié)點傳輸消息,這有利于平衡網(wǎng)絡(luò)能耗。然而,在實際的大型網(wǎng)絡(luò)中,由于節(jié)點能量受限,節(jié)點不可能與網(wǎng)絡(luò)內(nèi)所有的其他節(jié)點能夠直接通信,通常需要多跳通信才能將數(shù)據(jù)傳輸至基站,這就是多跳網(wǎng)絡(luò)。為此,本文以多跳無線傳感網(wǎng)絡(luò)為研究對象。

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

假定n個節(jié)點和一個基站節(jié)點隨機(jī)分布于M×M區(qū)域。整個網(wǎng)絡(luò)形成了一個無向的連通圖G(V,E),其中V={1,2,…,i,…,n,S0}為節(jié)點集合,而S0表示基站。而E表示邊集。若兩個節(jié)點互處于通信半徑內(nèi),則它們存在邊。此外,網(wǎng)絡(luò)還具有如下性質(zhì):①考慮靜態(tài)的連通網(wǎng)絡(luò),網(wǎng)絡(luò)一旦部署后,節(jié)點就不再移動;②考慮同構(gòu)網(wǎng)絡(luò),即所有節(jié)點的初始能量相同,且能量耗盡后,不能補充,即失效;③基站不受能量限制。

定義1輪(round) 指基站從所有節(jié)點收集一次數(shù)據(jù)的過程。可能每一輪持續(xù)時間不同,但每個節(jié)點在每一輪只產(chǎn)生固定比特的感應(yīng)數(shù)據(jù)。

定義2生命周期(LifeTime) 對于單個節(jié)點而言,節(jié)點的生命周期就是節(jié)點能存活的輪數(shù),而網(wǎng)絡(luò)的生命周期等于網(wǎng)絡(luò)內(nèi)節(jié)點的最小生命周期。

此外,引用文獻(xiàn)[11]的能量消耗模型。傳輸距離d、k比特數(shù)據(jù)包所消耗的能量Etr(k,d),如式(1)所示:

(1)

式中:Eelec、εfs和εmp為能量消耗參數(shù),它們典型取值分別為50 nJ/bit、10 pJ/(bitm2)和0.001 3 pJ(bit/m4)。而d0=75 m。

而接收單位距離的k比特數(shù)據(jù)包的所消耗的能量Erx(k)為:

Erx(k)=k×Eelec

(2)

1.2 問題描述

由于傳感節(jié)點能量受限,并且無線傳感網(wǎng)絡(luò)常部署于危險或偏遠(yuǎn)的環(huán)境,更換失效或能量殆盡的傳感節(jié)點是不可能。一旦失效,這些節(jié)點就無法感測數(shù)據(jù)和傳輸數(shù)據(jù),必然形成覆蓋空洞。為此,研究人員試圖通過改進(jìn)數(shù)據(jù)收集算法,提高節(jié)點能效,進(jìn)而延長傳感節(jié)點的工作時間。

現(xiàn)有的數(shù)據(jù)收集算法難以保證數(shù)據(jù)傳輸?shù)母咝?并且通常以增加投入傳感節(jié)點數(shù)的方式改善數(shù)據(jù)傳輸?shù)倪B通性,但節(jié)點數(shù)的增加必然會加大網(wǎng)絡(luò)流量,增加了能耗。如線性路由拓?fù)浣Y(jié)構(gòu)[12],如圖1所示。圖1中每個節(jié)點數(shù)據(jù)包都進(jìn)行2次收發(fā),形成了18次收/發(fā)過程,造成能量浪費。

圖1 線性路由拓?fù)浣Y(jié)構(gòu)

為此,本文不采用線性路由拓?fù)浣Y(jié)構(gòu),而是基于樹型拓?fù)浣Y(jié)構(gòu),進(jìn)而提高數(shù)據(jù)收集的效率。

2 TLBDG算法

TLBDG算法是通過節(jié)點跳數(shù)以及負(fù)載構(gòu)建數(shù)據(jù)收集樹。

2.1 最優(yōu)候選轉(zhuǎn)發(fā)集

對于任意節(jié)點i,它離基站節(jié)點的跳數(shù)表示為hi。它首先通過網(wǎng)絡(luò)的初始知識,建立一跳鄰居集N1-hop(i),其定義如式(3)所示:

N1-hop(i)={j|dij≤R}

(3)

式中:dij表示傳感節(jié)點i與j的歐式距離,而R表示傳感節(jié)點的通信半徑。

然后,基于一跳鄰居集N1-hop(i),把它拆分為兩個子集S(hi-1)和S(hi+1),且N1-hop(i)=S(hi-1)∪S(hi+1)。S(hi-1)內(nèi)的節(jié)點離基站的跳數(shù)為hi-1,而S(hi+1)內(nèi)的節(jié)點離基站的跳數(shù)為hi+1。

節(jié)點i就是從S(hi-1)內(nèi)選擇一個節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點,將其稱為路由節(jié)點。為此,節(jié)點建立最優(yōu)候選轉(zhuǎn)發(fā)集Option_list(i),其S(hi-1)構(gòu)成,并包含S(hi-1)內(nèi)每個節(jié)點ID號和它們子節(jié)點數(shù),即:

Option_list(i)←{node_id,number of children}
i∈S(hi-1)

(4)

2.2 路由節(jié)點的選擇

當(dāng)節(jié)點i啟動路由節(jié)點選擇過程開始前,先判斷比它跳數(shù)更高的節(jié)點是不是已經(jīng)完成了路由節(jié)點next-node(i)選擇階段。若完成了,則節(jié)點i啟動路由節(jié)點的選擇過程。為此,引入集count(i),其表示S(hi+1)內(nèi)需要選擇路由節(jié)點的節(jié)點數(shù)。這一過程的形式表述如下:

if count(i)==φ then
tigger next-node-selection algorithm

(5)

當(dāng)count(i)為空時,就啟動路由節(jié)點選擇階段。如果hi大于1,則表示自己不是基站節(jié)點的一跳鄰居,就廣播請求消息REQ,否則,就廣播消息Selected,表示路由節(jié)點就是基站,這一過程的形式化表述如下:

if count(i)==φ then
ifhi>1 then
broadcasts REQ message
else
broadcasts Selected message with next-node(i)=Sink

(6)

圖2 傳輸REQ和Replay消息的示意圖

當(dāng)節(jié)點i收到來自上一跳節(jié)點發(fā)送的REQ消息時,就回復(fù)Replay消息。Replay消息包含節(jié)點i需要轉(zhuǎn)發(fā)的數(shù)據(jù)包數(shù),且表示為Q(i),和count(i)信息,如圖2所示。

傳輸REQ和Replay消息的形式化表述如式(7)所示:

if receives REQ(j)message fromj∈S(hi+1) then

sends Replay(Qi,count(i))message toj

(7)

當(dāng)節(jié)點i從下一跳節(jié)點收到Replay消息后,從中構(gòu)建Option_list(i),并從中選擇子節(jié)點最小的節(jié)點作為路由節(jié)點next-node(i),如圖3所示。

圖3 節(jié)點i接收Replay消息的示意圖

節(jié)點i收到多條Replay消息后,就構(gòu)建Option_list(i),并選擇具有最小轉(zhuǎn)發(fā)消息數(shù)的節(jié)點作為路由節(jié)點,最后廣播Selected消息,通告已選擇的路由節(jié)點。這個過程形式化表述如式(6)所示:

if receives Reply message fromj∈S(hi-1)then
Option_list(i)←Option_list(i)∪{j,Qj};
selects next-node(i)=kwith minimum(Qk);
Broadcasts Selected message with next-node(i)

(8)

2.3Q集的更新

每當(dāng)節(jié)點i收到Selected消息,就意味著S(hi+1)內(nèi)有一個節(jié)點已成功找到路由節(jié)點。此時,應(yīng)將count(i)減1。同時,就將Q(i)+1,更新過程如式(9)所示:

if receives Selected message fromj∈S(hi+1)then

ifhj=hi+1 then

S(hi+1)←S(hi+1)j

count(i)=count(i)-1

ifi=next-node(i)then

Qi←Qi+1

(9)

3 性能分析

3.1 仿真參數(shù)

利用VISUAL C++模擬TLBDG算法,并分析它的性能。在100 m×100 m區(qū)域內(nèi)隨機(jī)分布了100個節(jié)點和一個基站節(jié)點。所有節(jié)點最大傳輸范圍為80 m,初始能量為10 J。每次實驗獨立重復(fù)50次,取平均值作為最終的實驗數(shù)據(jù)。

3.2 實驗數(shù)據(jù)

3.2.1 基站位置和通信半徑對網(wǎng)絡(luò)生命周期的影響

本次實驗著重考查基站位置對生命周期的影響,因此,實驗中考慮了兩種情況:基站位于邊界中點和基站位于區(qū)域中心。

圖4比較將基站位于仿真區(qū)域中心和邊界中點兩種情況下,通信半徑對網(wǎng)絡(luò)生命周期的影響。從圖4可知,在通信半徑較小階段,基站位于區(qū)域中心情況所消耗的能量小,所以生命周期大。但隨著通信半徑的增加,基站位于區(qū)域中心時所消耗的能量過多,其生命周期下降。此外,從圖4可知,這兩種情況下,當(dāng)通信半徑約為25 m時,它們的生命周期達(dá)到最大。

圖4 網(wǎng)絡(luò)生命周期隨通信半徑變化關(guān)系

圖 5 同類算法的生命周期對比

3.2.2 生命周期

為了更好地分析TLBDG算法性能,選擇同類算法PEDAP-PA 、MLDGA、MNL和MAXLAT進(jìn)行比較。同時考慮兩種場景:100節(jié)點和200節(jié)點。即分析網(wǎng)絡(luò)密度對網(wǎng)絡(luò)生命周期的影響,且基站位于區(qū)域中心,實驗數(shù)據(jù)分別如圖5(a)、圖5(b)所示。

從圖5可知,在兩種場景下,TLBDG算法的網(wǎng)絡(luò)生命周期最高,均高于PEDAP-PA 、MLDGA、MNL和MAXLAT。與場景一(100節(jié)點)相比,場景二情況下,TLBDG算法的生命周期下降了約24.5%。而PEDAP-PA 、MLDGA、MNL也下降了約50%。但是MAXLAT并沒有下降。這主要是因為:MAXLAT生成的樹節(jié)點分布均勻。而PEDAP-PA 、MLDGA、MNL所生成的樹節(jié)點分布不均勻。從這些數(shù)據(jù)可知,節(jié)點密度對網(wǎng)絡(luò)生命周期存在不小的影響。

而TLBDG算法通過以最小負(fù)載原則,生成樹,并完成數(shù)據(jù)傳輸,能夠有效地節(jié)省能量,降低能耗,從而提高了網(wǎng)絡(luò)生命周期。

3.2.3 能量消耗

本次實驗分析TLBDG算法和PEDAP-PA 、MLDGA、MNL和MAXLAT的能耗問題。節(jié)點數(shù)為200個。實驗數(shù)據(jù)如表1所示。

表1 網(wǎng)絡(luò)能量消耗至50%的運行輪數(shù)

從表1可知,在網(wǎng)絡(luò)整體能量下降至50%,TLBDG算法已經(jīng)運行了1082輪,而PEDAP-PA、MNL只運行了477輪、478輪。

4 總結(jié)

高效能量的數(shù)據(jù)收集是制約無線傳感網(wǎng)絡(luò)發(fā)展的關(guān)鍵因素之一。為此,本文研究了WSNs中基于樹的收集問題,并提出基于樹的負(fù)載均衡的數(shù)據(jù)收集算法TLBDG。TLBDG算法通過節(jié)點離基站的最小跳數(shù)構(gòu)建樹,形成以根節(jié)點為樹型數(shù)據(jù)傳輸網(wǎng)絡(luò)。實驗數(shù)據(jù)表明,TLBDG算法通過平衡負(fù)載,提高了網(wǎng)絡(luò)的生命周期。

[1] 黃媛. 無線傳感器網(wǎng)絡(luò)中一種基于可靠性的數(shù)據(jù)收集算法[J]. 計算機(jī)工程,2015,41(2):85-92.

[2] 李碩,樊建席,王成. 一種新型無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集生成樹[J]. 小型微型計算機(jī)系統(tǒng),2012,33(6):1238-1242.

[3] Younis O,Fahmy S. HEED:A Hybrid Energy Efficient Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Trans on Mobile Computing,2014,3(4):366-379.

[4] Taherkordi A,Mohammadi R,Eliassen F. A Communication Efficient Distributed Clustering Algorithm for Sensor Networks[C]//Proc of the 22nd IEEE Conference on Advanced Information Networking and Applications,Atlanta,USA 2013:634-638.

[5] Jung S M,Han Y J,Chung T M. The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[C]//Proc of the 12th IEEE Conference on Advanced Communication Technology,Shanghai,China,2013:260-265.

[6] Lindsey S,Raghavendra C,Sivalingam K M. Data Gathering Algorithms in Sensor Networks Using Energy Metrics[J]. IEEE Trans on Parallel and Distributed Systems,2012,13(9):924-935.

[7] Tan H O,Korgeoglu I. Power Efficient Data Gathering and Aggregation in Wireless Sensor Networks[J]. SIGMOD Record,2013,32(4):66-71.

[8] Zhang Q,Xie Z P,Ling B. A Maximum Lifetime Data Gathering Algorithm for Wireless Sensor Networks[J]. Journal of Software,2015,16(11):1946-1957.

[9] Liang W F,Liu Y Z. Online Data Gathering for Maximizing Network Lifetime in Sensor Networks[J]. IEEE Trans on Mobile Computing,2013,6(1):2-11.

[10] Liang J B,Wang J X,Li T S. Maximum Lifetime Algorithm for Precise Data Gathering Based on Tree in Wireless Sensor Networks[J]. Journal of Software,2013,21(9):2289-2303.

[11] Heinzelman W B,Chandrakasan A P,Balakrishnan H. An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Trans on Wireless Communications,2012,1(4):660-670.

[12] 劉卉,李澤軍. 基于投影矢量的雙組播樹高效路由數(shù)據(jù)收集[J]. 傳感技術(shù)學(xué)報,2013,26(4):570-577.

劉正波(1971-),男,講師,主要研究領(lǐng)域移動通信,lzhengb@163.com。

Tree-BasedLoadBalancedDataGatheringAlgorithminWirelessSensorNetworks*

LIUZhengbo1*,ZHULiang2

(1.Department of Mobile Communications,Telecommunications Engineering,Shijiazhuang Posts and Telecommunications Technical College, Shijiazhuang 050000,China;2.School of Mathematics and Computer Science,Hebei University,Baoding Hebei 071002)

Data gathering is a fundamental task in Wireless Sensor Networks(WSNs). The sensor nodes are highly resource constrained,and how to design a low energy consumption data gathering is a great challenge. Therefore,Tree-based Load Balanced Data Gathering(TLBDG)algorithm was proposed in this paper. TLBDG algorithm has construct a load-balanced data gathering tree rooted at the Sink node to forward packets via minimum hops. In TLBDG,firstly the hierarchical structure was established based on the minimum hops from each sensor node to the base station,secondly,a tree transmission path whose root was the base station is got. Simulation result shows that the proposed TLBDG can achieve load balanced,and long lifetime.

wireless sensor networks,data gathering,tree,load balanced;Hop

項目來源:河北省自然科學(xué)基金項目(F2011201146);保定市科學(xué)技術(shù)研究與發(fā)展指導(dǎo)計劃項目(13ZR058)

2017-03-13修改日期:2017-05-23

TP393

:A

:1004-1699(2017)09-1417-05

10.3969/j.issn.1004-1699.2017.09.020