可持續(xù)WSN中基于能量采集感知的中繼節(jié)點(diǎn)部署算法

呂志恒

(永城職業(yè)學(xué)院信息工程系,河南 永城 476600)

目前,無(wú)線(xiàn)傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)已在多類(lèi)應(yīng)用中使用,如火災(zāi)檢測(cè)、康復(fù)醫(yī)療、戰(zhàn)場(chǎng)勘測(cè)。然而,由于WSNs是由微型的傳感節(jié)點(diǎn)組成,節(jié)點(diǎn)的能量(電池)是有限的[1-2]。一旦節(jié)點(diǎn)能量低至一定量時(shí),節(jié)點(diǎn)再也無(wú)法工作,形成覆蓋空洞,這就影響了WSNs性能。

針對(duì)WSNs的能量受限問(wèn)題,研究人員已提出不同的策略[3]。如休眠/喚醒機(jī)制、功率控制機(jī)制和能耗感知路由協(xié)議。休眠/喚醒機(jī)制是通過(guò)減少節(jié)點(diǎn)的工作時(shí)間,保存能量。而功率控制機(jī)制是通過(guò)降低節(jié)點(diǎn)發(fā)射功率,減少能耗。而能耗感知路由協(xié)議是從提高能量利用率角度,構(gòu)建路由。盡管這些機(jī)制能夠保存能量,但是它們均是在給定的有限能量基礎(chǔ)上,提高能量利用率,并沒(méi)有從根本上解決能量有限問(wèn)題。

近期,綠色能源概念已廣泛推廣,相關(guān)的研究也逐漸深入,如電磁波、太陽(yáng)能,風(fēng)能等[4-5]。因此,可利用這些綠色能源解決WSNs內(nèi)節(jié)點(diǎn)能量有限問(wèn)題。即節(jié)點(diǎn)從周期環(huán)境獲取能量,進(jìn)行能量補(bǔ)給。將這類(lèi)WSNs稱(chēng)為可持續(xù)WSNs。與太陽(yáng)能、風(fēng)能相比,利用電磁波給節(jié)點(diǎn)補(bǔ)給能量更為穩(wěn)定。因?yàn)樘?yáng)能和風(fēng)能隨環(huán)境天氣變化大,極為不穩(wěn)定。因此,本文選擇通過(guò)基站對(duì)節(jié)點(diǎn)進(jìn)行無(wú)線(xiàn)充電[6-7]。

即使在可持續(xù)WSNs,部分節(jié)點(diǎn)的能量可能也會(huì)提前消耗殆盡。因?yàn)椴煌墓?jié)點(diǎn)所采集的能量不同,能量消耗速度也不盡相同。當(dāng)節(jié)點(diǎn)能量消耗殆盡后,需要在其附近部署節(jié)點(diǎn),進(jìn)而修復(fù)覆蓋空洞。為此,將類(lèi)部署節(jié)點(diǎn)稱(chēng)為中繼節(jié)點(diǎn)RNs(Relay Nodes)。

考慮到成本問(wèn)題,可持續(xù)WSNs內(nèi)的RNs數(shù)是有限的,并需確定性部署。部署RNs的目的在于彌補(bǔ)能量消耗殆盡的節(jié)點(diǎn)所留下的覆蓋空洞,并保持網(wǎng)絡(luò)連通率。為此,本文的主要工作在于如何部署RNs,進(jìn)而實(shí)現(xiàn)以最小RNs數(shù)完成最大的數(shù)據(jù)包傳輸率的目的。

針對(duì)可持續(xù)WSNs,對(duì)RNs的部署問(wèn)題進(jìn)行研究,并提出基于最小生成樹(shù)MST(Minimum Spanning Tree)的部署算法EHA-DRN(Minimum Spanning Tree-based Deploying Relay Nodes algorithm)。EHA-DRN算法先依據(jù)節(jié)點(diǎn)所收集的能量的多少,然后依據(jù)節(jié)點(diǎn)能量采集率,并結(jié)合克魯斯卡爾(Kruskal)算法構(gòu)建MST。最后,檢測(cè)MST內(nèi)的非葉節(jié)點(diǎn)的能量是否能完成數(shù)據(jù)傳輸要求,如果不能完成,則稱(chēng)為低能量節(jié)點(diǎn)LENs(Low-Energy-Nodes)。這類(lèi)節(jié)點(diǎn)就需要RNs的協(xié)助,即在這些節(jié)點(diǎn)附近部署RNs,進(jìn)而維持網(wǎng)絡(luò)的覆蓋率。

本文的創(chuàng)新點(diǎn)之處在于:①依據(jù)節(jié)點(diǎn)采集能量的能力,計(jì)算邊權(quán)重,然后依據(jù)邊權(quán)重,并利用Kruskal算法構(gòu)建最小生成樹(shù)MST;②依據(jù)MST部署RNs。檢測(cè)最小生成樹(shù)上的非葉節(jié)點(diǎn)的能量是否能完成數(shù)據(jù)傳輸,如果不能,則在附近部署RNs。

1 約束條件及能量模型

1.1 約束條件

利用無(wú)向圖G=(V,E)表示網(wǎng)絡(luò)拓?fù)鋄8],其中V為頂點(diǎn)集、而E為邊集。若某節(jié)點(diǎn)在自己的通信范圍內(nèi),則它們之間便可形成一條邊。本文引用周期流量。所謂周期流量是指節(jié)點(diǎn)周期地向基站傳輸感測(cè)數(shù)據(jù)包,且數(shù)據(jù)包格式固定,數(shù)據(jù)包大小為λ比特。

具體而言,節(jié)點(diǎn)i在時(shí)期T內(nèi)接收的數(shù)據(jù)流表示為Reci,其由自己產(chǎn)生的數(shù)據(jù)包和從支葉節(jié)點(diǎn)所接收的數(shù)據(jù)流組成,定義如式(1)所示:

Reci=λγi

(1)

式中:

(2)

式中:γi為節(jié)點(diǎn)i的支葉節(jié)點(diǎn)(子節(jié)點(diǎn)和孫子節(jié)點(diǎn)),而Ci表示直系子節(jié)點(diǎn)數(shù)[9-10]。

而節(jié)點(diǎn)i向基站傳輸?shù)臄?shù)據(jù)流Tri:

Tri=λ(γi+1)

(3)

1.2 能量模型

本文基于無(wú)線(xiàn)充電的能量模型。節(jié)點(diǎn)通過(guò)無(wú)線(xiàn)網(wǎng)絡(luò)進(jìn)行充電[11-12],并引用Beamforming技術(shù)形成尖利能量束[13],再傳遞至節(jié)點(diǎn),如圖1所示。節(jié)點(diǎn)依據(jù)功率beacon包獲取電能,并由能量管理單元管理所采集的能量,同時(shí)將多余能量存儲(chǔ)。同時(shí),將傳輸數(shù)據(jù)包與充電能量路徑分開(kāi),這有利于減少彼此的干擾。

圖1 節(jié)點(diǎn)充電模型

假定節(jié)點(diǎn)i在單位時(shí)間內(nèi)采集的能量為hi,即能量采集率。依據(jù)文獻(xiàn)[13],hi與多個(gè)因素有關(guān),其定義如式(4)所示:

(4)

此外,令Ep表示在每個(gè)周期內(nèi)執(zhí)行感測(cè)、計(jì)算任務(wù)時(shí)所消耗的能量。而Et、Er分別表示傳輸或接收一比特所消耗的能量。因此節(jié)點(diǎn)i所消耗的總能量Ei:

Ei=ReciEr+TriEt+Ep

(5)

2 EHA-DRN算法

整個(gè)EHA-DRN算法由兩個(gè)階段構(gòu)成:①構(gòu)建最小生成樹(shù);②部署RNs。如圖2所示。在構(gòu)建最小生成樹(shù)階段,利用節(jié)點(diǎn)的能量采集率,計(jì)算節(jié)點(diǎn)權(quán)重,然后再計(jì)算邊權(quán)重,最后構(gòu)建最小生成樹(shù)。而在部署RNs階段,先檢測(cè)低能量節(jié)點(diǎn)LENs,再部署RNs。

圖2 EHA-DRN算法框圖

2.1 權(quán)重

ωi=(hmax-hi)/hmax

(6)

EHA-DRN算法先引用節(jié)點(diǎn)能量采集率計(jì)算節(jié)點(diǎn)權(quán)重。節(jié)點(diǎn)i的權(quán)重ωi如式(7)所示:

ωi=(hmax-hi)/hmax

(7)

再依據(jù)節(jié)點(diǎn)權(quán)重,計(jì)算邊重。每條邊權(quán)重等于這邊條的兩個(gè)端節(jié)點(diǎn)的權(quán)重之和,如式(8)所示:

圖3 基于邊權(quán)重的網(wǎng)絡(luò)拓?fù)鋱D

(8)

式中:Wu,υ表示節(jié)點(diǎn)u、υ間所構(gòu)成的邊權(quán)重。

依據(jù)各邊的權(quán)重,便形成基于邊權(quán)重的網(wǎng)絡(luò)拓?fù)鋱D。圖3顯示了構(gòu)建基于邊權(quán)重的網(wǎng)絡(luò)拓?fù)鋱D過(guò)程。如圖3所示,圖3(a)表示網(wǎng)絡(luò)拓?fù)鋱D,數(shù)字表示節(jié)點(diǎn)的能量采集率h。例如,節(jié)點(diǎn)5的能量采集容量h5=20。依據(jù)式(6),可計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重,其中hmax=30,如圖3(b)所示。例如,節(jié)點(diǎn)5的權(quán)值ω5=(30-20)/30=0.33。

結(jié)合圖3(c),并依據(jù)式(8)計(jì)算各邊權(quán)重,如圖3所示。例如,由節(jié)點(diǎn)5和節(jié)點(diǎn)9構(gòu)成的邊的權(quán)值就等于0.49=0.33+0.16。

2.2 最小生成樹(shù)

依據(jù)基于邊權(quán)重的網(wǎng)絡(luò)拓?fù)鋱D,結(jié)合Kruskal算法產(chǎn)生最小生成樹(shù)。

Kruskal算法是構(gòu)建最小生成樹(shù)的常用算法,其是通過(guò)邊權(quán)重產(chǎn)生最小連通圖Γ。其思路簡(jiǎn)述如下:先從E中選擇權(quán)重最小的邊,若該邊的頂點(diǎn)在Γ中不同的連通分量上,則該邊加入Γ中,否則丟棄。然后,再?gòu)腅中選擇權(quán)重最小的邊,依次類(lèi)推,直到所有頂點(diǎn)均連通在同一個(gè)拓?fù)鋱D內(nèi)。

仍以圖3為例,描述構(gòu)建最小生成樹(shù)的原理。先從找到最小權(quán)重的邊,從圖3(c)可知,邊權(quán)重最小值為0。具有0權(quán)重的邊有多邊,隨機(jī)從中選擇一邊,假定選擇了是節(jié)點(diǎn)2連通基站的邊。然后,再?gòu)闹羞x擇最小權(quán)重的邊,再把節(jié)點(diǎn)1、節(jié)點(diǎn)3分別連接基站的邊加入,依據(jù)類(lèi)推,便形成如圖4所示的最小生成樹(shù)。

2.3 基于MST的LENs檢測(cè)

構(gòu)建了最小生成樹(shù)后,再檢測(cè)LENs節(jié)點(diǎn)。假定γi表示節(jié)點(diǎn)i的支葉節(jié)點(diǎn)數(shù),如果γi=0,則表示γi最低層葉節(jié)點(diǎn)(無(wú)子節(jié)點(diǎn)),否則為有子節(jié)點(diǎn)。

基于MST的LENs檢測(cè)過(guò)程如下:

①對(duì)于節(jié)點(diǎn)i∈NMST,如果節(jié)點(diǎn)γi=0,則i+1,再執(zhí)行①;否則執(zhí)行②;其中NMST表示最小生成樹(shù)的節(jié)點(diǎn)集。

②如果γi≠0,則檢測(cè)是否滿(mǎn)足式(9)。如果滿(mǎn)足則跳到步驟①,否則就將節(jié)點(diǎn)i加入R。其中R表示LENs的節(jié)點(diǎn)。

hiT≥Ei,?i∈NMST

(9)

最后,依據(jù)R部署RNs節(jié)點(diǎn),并由RNs負(fù)責(zé)數(shù)據(jù)包的傳輸,減少LENs節(jié)點(diǎn)的任務(wù),進(jìn)而保存它們的能量。

圖5 EHA-DRN算法的偽代碼

整個(gè)算法的偽代碼如圖5所示。先依據(jù)節(jié)點(diǎn)能量采集率計(jì)算節(jié)點(diǎn)權(quán)重和邊權(quán)重,再形成邊權(quán)重矩陣W′。再將E、V和W′作為Kruskal算法的輸入,輸出為以基站為根節(jié)點(diǎn)的MST樹(shù)。再檢測(cè)MST樹(shù)內(nèi)的有子節(jié)點(diǎn),并判斷是否滿(mǎn)足式(9),如果不滿(mǎn)足,就將加入R。其中|R|表示需要部署RNs的節(jié)點(diǎn)數(shù),|R|越少,成本越低。

3 仿真分析

3.1 仿真參數(shù)

引用NS3[14]網(wǎng)絡(luò)仿真器建立仿真平臺(tái)。在仿真中,N個(gè)隨機(jī)在分布于100 m×100 m區(qū)域。同時(shí),引用文獻(xiàn)[12]的能量模型參數(shù)。節(jié)點(diǎn)周期性地向基站傳輸數(shù)據(jù)包,數(shù)據(jù)包大小為32 byte。選擇部署成本和數(shù)據(jù)包傳輸成功率作為性能指標(biāo)。其中,部署成本為部署RNs的節(jié)點(diǎn)數(shù),節(jié)點(diǎn)數(shù)越多,說(shuō)明成本越高。

此外,為了對(duì)比分析,選擇文獻(xiàn)[15]的MRA算法和文獻(xiàn)[2]基于ILP推導(dǎo)成本下限作為參照。每次實(shí)驗(yàn)數(shù)據(jù)獨(dú)立重復(fù)20次,取平均值作為最終實(shí)驗(yàn)數(shù)據(jù)。

圖6 成本隨節(jié)點(diǎn)數(shù)的變化曲線(xiàn)

3.2 數(shù)據(jù)分析

先分析網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)對(duì)部署成本的影響。成本隨節(jié)點(diǎn)數(shù)的變化曲線(xiàn)如圖6所示。

從圖6可知,節(jié)點(diǎn)數(shù)的增加提高部署成本。這主要是因?yàn)?網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)越多,出現(xiàn)低能量節(jié)點(diǎn)的概率越大,需要部署更多的中繼節(jié)點(diǎn)。此外,同MBA算法相比,提出的EHA-DRN算法的部署成本得到有效地控制。這說(shuō)明,利用最小生成樹(shù)搜索低能量節(jié)點(diǎn),可減少部署成本。當(dāng)然,將EHA-DRN與LB-ILP算法進(jìn)行比較不難發(fā)現(xiàn),EHA-DRN算法的部署成本仍有一定的下降空間。

接下來(lái),分析網(wǎng)絡(luò)密度對(duì)部署成本的影響,實(shí)驗(yàn)數(shù)據(jù)如圖7所示。其中,網(wǎng)絡(luò)密度是指網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)所連接的平均邊數(shù)。

圖7 成本隨網(wǎng)絡(luò)密度的變化曲線(xiàn)

從圖7可知,網(wǎng)絡(luò)密度的增加,降低了部署成本。這主要是因?yàn)?網(wǎng)絡(luò)密度越大,節(jié)點(diǎn)所連接的邊數(shù)越多,那么節(jié)點(diǎn)擁有更多邊去傳輸數(shù)據(jù),換而言之,由更的邊分擔(dān)了數(shù)據(jù)傳輸任務(wù),最終降低了節(jié)點(diǎn)的能耗,使得低能量節(jié)點(diǎn)數(shù)越少。與MBA算法相比,提出的EHA-DRN算法的部署成本得到控制,但仍與LB-ILP的所推導(dǎo)的成本下限有差異。

最后,分析MBA和EHA-DRN算法的數(shù)據(jù)包傳遞率,實(shí)驗(yàn)數(shù)據(jù)如圖8所示。

由圖8可知,EHA-DRN算法的數(shù)據(jù)包傳遞率得到有效地提高,數(shù)據(jù)包傳遞率不低于0.9。這主要是因?yàn)?EHA-DRN算法通過(guò)節(jié)點(diǎn)能量采集率建立最小生成樹(shù),并由最小生成樹(shù)傳輸數(shù)據(jù)包,縮短了數(shù)據(jù)傳輸路徑,也降低了低能量節(jié)點(diǎn)參與數(shù)據(jù)傳輸?shù)母怕省?/p>

圖8 數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況

4 總結(jié)

基于可持續(xù)WSNs,提出基于能量采集感知的中繼節(jié)點(diǎn)部署EHA-DRN算法。EHA-DRN算法從節(jié)點(diǎn)能量采集率構(gòu)建邊權(quán)重,然后再利用Kruskal算法產(chǎn)生最小生成樹(shù)。最后,依據(jù)最小生成樹(shù),檢測(cè)低能量節(jié)點(diǎn),并在這些低能量節(jié)點(diǎn)附近部署中繼節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明,提出的EHA-DRN算法降低了部署成本,也提高了數(shù)據(jù)包傳輸成功率。

后期,將進(jìn)一步優(yōu)化EHA-DRN算法,降低部署成本,使其逼近基于LB-ILP所推導(dǎo)的成本下限。這是后期的工作方向。

參考文獻(xiàn):

[1] Yang D,Misra S,Fang X,et al. Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks:Computational Complexity and Efficient Approximations[J]. IEEE Trans Mob Comput,2012,11(8):1399-1411.

[2] 陳東海,李長(zhǎng)庚. 基于簇頭功能分化的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)成簇算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(2):244-248.

[3] Wang F,Wang D,Liu J. Traffic-Aware Relay Node Deployment:Maximizing Lifetime for Data Collection Wireless Sensor Networks[J]. IEEE Trans Parallel Distrib Syst,2011,22(8):1415-1423.

[4] Zheng Z,Cai L X,Zhang R,et al. Rnp-sa:Joint Relay Placement and Sub-Carrier Allocation in Wireless Communication Networks with Sustainable Energy[J]. IEEE Trans Wireless Commun,2012,11(10):3818-3828.

[5] Chelli A,Bagaa M,Djenouri D,et al. One-Step Approach for Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks[J]. IEEE Wireless Commun Letters,2016,5(4):448-451.

[6] Zhang P,Xiao G,Tan H P. Clustering Algorithms for Maximizing the Lifetime of Wireless Sensor Networks with Energy-Harvesting Sensors[J]. Computer Networks,2013,57(14):2689-2704.

[7] Misra S,Majd N E,Huang H. Approximation Algorithms for Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks[J]. IEEE Trans Computers,2014,63(12):23-33.

[8] Prasad R V,Devasenapathy S,Rao V S,et al. Reincarnation in the Ambiance:Devices and Networks with Energy Harvesting[J]. IEEE Commun Surveys and Tutorials,2014,16(1):195-213.

[9] Castagnetti A,Pegatoquet A,Le T N,et al. A Joint Duty-Cycle and Transmission Power Management for Energy Harvesting Wsn[J]. IEEE Trans Industrial Informatics,2014,10(2):928-936.

[10] Michelusi N,Zorzi M. Optimal Adaptive Random Multi-Access in Energy Harvesting Wireless Sensor Networks[J]. IEEE Transactions on Communications,2015,63(4):1355-1372.

[11] Huang K,Lau V K N. Enabling Wireless Power Transfer in Cellular Networks:Architecture,Modeling and Deployment[J]. IEEE Transactions on Wireless Communications,2014,13(2):902-912.

[12] Huang K,Zhou X. Cutting the Last Wires for Mobile Communications by Microwave Power Transfer[J]. IEEE Communications Magazine,2015,53(6):86-93.

[13] Xia M,A?ssa S. On the Efficiency of Far-Field Wireless Power Transfer[J]. IEEE Trans Signal Processing,2015,63(11):2835-2847.

[14] Kim B,Lee D,Choi T. Performance Evaluation for Modbus/TCP Using Network Simulator NS3[C]//2015 IEEE Region 10 Conference,2015:1-6.

[15] Djenouri D,Bagaa M. Energy Harvesting Aware Relay Node Addition for Power-Efficient Coverage in Wireless Sensor Networks[C]//IEEE International Conference on Communications,ICC,London,UK,2015:86-91.