尚光龍, 呂 爭(zhēng)

(信陽職業(yè)技術(shù)學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,河南 信陽 464000)

0 引 言

隨著電子通信技術(shù)的發(fā)展及普及，無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)已被廣泛使用[1]。但是由于WSNs內(nèi)節(jié)點(diǎn)是微型設(shè)備，能量供給有限(一般是小容量的電池)。此外，WSNs網(wǎng)絡(luò)常部署于野外的惡劣環(huán)境，當(dāng)能量耗盡后，也不便于更換電池。這些特性加劇WSNs的能量問題[2]。目前，研究人員針對(duì)WSNs的能量問題提出不同的策略，但是這些策略多數(shù)屬于能量效率問題，即是基于有限的能量，如何提高能量效率，并沒有從根本上解決WSNs的能量問題。

從環(huán)境采集能量是解決WSNs問題的有效策略。即補(bǔ)給能量，而不是提高已有能量的效率。環(huán)境能量有電磁波、太陽能等[3-4]?；谶@些能量供給的WSNs稱為可持續(xù)WSNs。然而，若整個(gè)WSNs內(nèi)全部采用具有能量采集的節(jié)點(diǎn)，增加了部署成本。因此，本文只在部分區(qū)域部署這些節(jié)點(diǎn)。具體而言，當(dāng)某些節(jié)點(diǎn)原有電能消耗完盡，就在這些節(jié)點(diǎn)區(qū)域附近部署具有能量采集的節(jié)點(diǎn)，將這類節(jié)點(diǎn)稱為能補(bǔ)節(jié)點(diǎn)(Energy-provided Node, EPN)。

換而言之，EPNs節(jié)點(diǎn)替換那些能量消耗殆盡的節(jié)點(diǎn)?？紤]到EPNs的成本問題，在部署EPN時(shí)，希望EPNs的數(shù)目越少越好。因此，本文要解決的問題就是在保證網(wǎng)絡(luò)連通的同時(shí)，如何部署EPNs。為此，先假定每個(gè)節(jié)點(diǎn)周期地向基站傳輸感測(cè)數(shù)據(jù)。同時(shí)，每個(gè)節(jié)點(diǎn)的從環(huán)境采集能量的能力不同，所采集的能量也不同。本文引用能量采集率表征節(jié)點(diǎn)對(duì)環(huán)境采集的能量。

為此，本文針對(duì)可持續(xù)WSNs，提出基于最小生成樹的EPN部署算法(Minimum spanning Tree-based deploying ENPs algorithm, MST-DENP)。MST-DENP算法先基于節(jié)點(diǎn)的能量信息，計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重，然后再結(jié)合Kruskal算法構(gòu)建最小生成樹，最后檢測(cè)最小生成樹內(nèi)的非葉節(jié)點(diǎn)的能量，若能量過低，則就在這些節(jié)點(diǎn)區(qū)域部署ENP。

1 約束條件及能量模型

1.1 約束條件

網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)知道網(wǎng)絡(luò)拓?fù)湫畔?。假定?jié)點(diǎn)周期地向基站傳輸自己所感測(cè)到的數(shù)據(jù)[5]，并且每個(gè)節(jié)點(diǎn)的能量采集率不同。此外，假定，每個(gè)節(jié)點(diǎn)所采集的能量能夠完成它的基本任務(wù)。在每個(gè)周期T內(nèi)，節(jié)點(diǎn)i所接收的數(shù)據(jù)Reci：

Reci=Biγi

(1)

其中Bi為節(jié)點(diǎn)i產(chǎn)生的比特?cái)?shù)據(jù)，而γi表示節(jié)點(diǎn)i的支葉節(jié)點(diǎn)數(shù)，其定義如式(2)所示：

(2)

其中Ci為直系子節(jié)點(diǎn)數(shù)[6-7]。

網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)除了感測(cè)數(shù)據(jù)外，還得傳輸數(shù)據(jù)。節(jié)點(diǎn)i傳輸?shù)臄?shù)據(jù)為Tri，如式(3)所示：

Tri=Bi(γi+1)

(3)

1.2 能量采集模型

假定節(jié)點(diǎn)i的能量采集率表示為hi。網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的能量采集率并不相同[8-9]?？紤]到能量采集的穩(wěn)定，本文選擇利用無線電充電作為能量采集模型。之所以不選擇太陽能、風(fēng)能，原因在這于這些能量受環(huán)境變化大，不穩(wěn)定。如太陽能存在強(qiáng)烈的時(shí)間周期性，中午太陽強(qiáng)烈，而午夜就無陽光。因此，引用無線電充電模型，便以控制。

具體而言，網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)利用無線信號(hào)充電，從基站發(fā)送的信號(hào)獲取電能。文獻(xiàn)[10-11]已分析無線充電的可行性。通過Beamforming技術(shù)獲取能量?；纠脙蓚€(gè)獨(dú)立通道分別傳輸數(shù)據(jù)和能量。采用獨(dú)立的通路，有利于避免數(shù)據(jù)傳輸與能量傳輸間的干擾。

Ehi表示節(jié)點(diǎn)i所采集的能量。ηhi表示能量效率，T是采集能量的時(shí)間。

Ehi=ηhiPt(di)-βξiT

(4)

其中Pt表示基站傳輸功率，β為路徑衰落指數(shù)。而基站與節(jié)點(diǎn)i的歐式距離為di。而ξi表示路徑衰落信道。

(5)

節(jié)點(diǎn)在完成感測(cè)、計(jì)算數(shù)據(jù)任務(wù)，需消耗自己的電能。假定在一個(gè)周期內(nèi)節(jié)點(diǎn)所消耗的能量為Ei，其定義如式(6)：

Ei=ReciEr+TriEt+Ep

(6)

其中Ep為感測(cè)數(shù)據(jù)和計(jì)算數(shù)據(jù)任務(wù)所消耗的能量，而Er、Et分別表示接收、傳輸單比特?cái)?shù)據(jù)所消耗的能量。

當(dāng)節(jié)點(diǎn)消耗的能量小于所采集的能量時(shí)，節(jié)點(diǎn)就可以存活更長(zhǎng)時(shí)間，如式(7)所示。若不滿足式(7)，則表明節(jié)點(diǎn)能量處于快速消耗期，應(yīng)需對(duì)其補(bǔ)給。

hiT≥Ei

(7)

其中hiT表示節(jié)點(diǎn)所采集的能量。

2 MST-DENP算法

MST-DENP算法利用Kruskal算法構(gòu)建最小生成樹，然后再檢測(cè)最小生成樹中非葉節(jié)點(diǎn)的所采集的能量是否滿足式(7)所示。若不滿足，則就在這些節(jié)點(diǎn)附近部署ENPs節(jié)點(diǎn)。MST-DENP算法的框架如圖1所示。

圖1 MST-DENP算法的框架

2.1 權(quán)益值

先依據(jù)節(jié)點(diǎn)所采集的能量給節(jié)點(diǎn)定義節(jié)點(diǎn)權(quán)益值。節(jié)點(diǎn)i的歸一化權(quán)益值為：

ωi=(hmax-hi)/hmax

(8)

依據(jù)式(8)便可估算節(jié)點(diǎn)的權(quán)益值，且權(quán)益值越大，節(jié)點(diǎn)采集能量越少。此外，通過所有節(jié)點(diǎn)的權(quán)益值，可建立基于權(quán)益值的拓?fù)鋱D(Vertex Weighted Graph, VWG)。

獲取各點(diǎn)的權(quán)益值后，便可計(jì)算各邊的權(quán)益值。每條邊的權(quán)益值等于兩端點(diǎn)權(quán)益值之和。假定節(jié)點(diǎn)υ和節(jié)點(diǎn)u所構(gòu)成的邊的權(quán)益值表示為Wu,υ：

Wu,υ=ωu+ωυ

(9)

為了更好地理解節(jié)點(diǎn)權(quán)益值和邊權(quán)益值，進(jìn)行示例分析?？紤]圖2(a)所示的網(wǎng)絡(luò)結(jié)構(gòu)，圖中標(biāo)識(shí)的數(shù)字表示該節(jié)點(diǎn)所采集的能量，如節(jié)點(diǎn)1所采集的能量h1=10。

然后，依據(jù)式(8)計(jì)算各節(jié)點(diǎn)的權(quán)益值，例如節(jié)點(diǎn)1的權(quán)益值ω1=(30-10)/30=0.66。圖2(b)標(biāo)出了各節(jié)點(diǎn)的權(quán)益值。

圖2 具有節(jié)點(diǎn)值的網(wǎng)絡(luò)拓?fù)鋱D

再依據(jù)節(jié)點(diǎn)的權(quán)益值，計(jì)算各邊的權(quán)益值。圖3顯示了各邊的權(quán)益值。例如，節(jié)點(diǎn)1和節(jié)點(diǎn)5所構(gòu)成的邊的權(quán)益值等于0.66+0.33=0.99。

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

2.2 最小生成樹

通過3.1節(jié)獲取了各邊權(quán)益值后，再利用Kruskal算法構(gòu)建最小生成樹。Kruskal算法將最小權(quán)益值的邊加入最小生成樹，然后在保持網(wǎng)絡(luò)連通的前提下，再選擇具有最小權(quán)益值的邊加入，重復(fù)此過程，直到網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)均在樹內(nèi)，并保持網(wǎng)絡(luò)連通。

圖4 最小生成樹

以圖3為例，節(jié)點(diǎn)5共參與三條邊，其中與節(jié)點(diǎn)2所構(gòu)成的邊的權(quán)益值最小，因此，節(jié)點(diǎn)5就向節(jié)點(diǎn)2傳輸數(shù)據(jù)。最終形成如圖4所示的最小生成樹。

2.3 部署EPN

本節(jié)分析如何依據(jù)最小生成樹，尋找不滿足式(7)的節(jié)點(diǎn)，進(jìn)而在這些節(jié)點(diǎn)附近部署EPNs節(jié)點(diǎn)。換而言之，部署EPNs節(jié)點(diǎn)等于搜索不滿足式(7)的節(jié)點(diǎn)，搜索過程如圖5所示。假定R為滿足式(7)的節(jié)點(diǎn)集，其初始值為空。

用無向圖G=(V,E)表示網(wǎng)絡(luò)拓?fù)鋱D，其中V為節(jié)點(diǎn)集，而E為邊集。假定3.1節(jié)構(gòu)建的最小生成樹表示為MST,并且以基站BS為根的最小生成樹為(V,ε,BS),其中ε為支葉節(jié)點(diǎn)。

具體而言，先依式(8)計(jì)算各節(jié)點(diǎn)權(quán)益值，然后再計(jì)算各邊權(quán)益值，并形成邊權(quán)益值矩陣W′。隨后，構(gòu)成最小生成樹。若節(jié)點(diǎn)的所采集能量不滿足式(7)，則就加入R。|R|表示需要部署的EPNs節(jié)點(diǎn)數(shù)。MST-DENP算法的目的就是在維持網(wǎng)絡(luò)連通的前提下，最小化|R|。

圖5 基于MST的構(gòu)建R的過程

3 性能仿真

3.1 仿真參數(shù)

本小節(jié)利用NS3[13]仿真軟件建立仿真平臺(tái)，分析MST-DENP算法的性能。同時(shí)，選擇文獻(xiàn)[14]的MRA算法和文獻(xiàn)[2]利用ILP推導(dǎo)的成本下限(記為ILP)作為參照，并進(jìn)行比較。其中成本是指部署ENPs的節(jié)點(diǎn)數(shù)。部署的節(jié)點(diǎn)數(shù)越低，成本低少，性能越好。

仿真區(qū)域大小為100 m×100 m，節(jié)點(diǎn)數(shù)為N，并且從中隨機(jī)一個(gè)節(jié)點(diǎn)為基站。節(jié)點(diǎn)初始能量為Einit=10 J。傳感節(jié)點(diǎn)周期地產(chǎn)生數(shù)據(jù)包，并向基站傳輸，數(shù)據(jù)包大小為32 bytes。

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

首先分析數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況，實(shí)驗(yàn)數(shù)據(jù)如圖6所示。從圖6可知，提出的MST-DENP算法的數(shù)據(jù)傳遞率高于MBA算法，且在節(jié)點(diǎn)數(shù)變化區(qū)間，保持90%的數(shù)據(jù)包傳遞率。原因在于：MST-DENP算法利用最小生成樹部署ENPs，以最小成本，構(gòu)建網(wǎng)絡(luò)連通圖，提高了數(shù)據(jù)包傳遞率。

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

接下來，分析成本隨節(jié)點(diǎn)數(shù)N的變化情況，如圖7所示。從圖7可知，節(jié)點(diǎn)數(shù)的增加，提高了成本。原因在于節(jié)點(diǎn)數(shù)越多，出現(xiàn)低能量的節(jié)點(diǎn)數(shù)也就越多，部署成本自然也越高。相比于MBA算法，MST-DENP算法控制了部署成本。然而，與ILP相比，MST-DENP算法仍有改進(jìn)的空間。

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

最后，分析網(wǎng)絡(luò)密度對(duì)部署成本的影響，實(shí)驗(yàn)數(shù)據(jù)如圖8所示。此處引用的網(wǎng)絡(luò)密度是指節(jié)點(diǎn)參與平均邊數(shù)。

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

從圖8可知，網(wǎng)絡(luò)密度的增加，降低了部署成本。這主要是因?yàn)榫W(wǎng)絡(luò)密度越大，網(wǎng)絡(luò)路徑越多，數(shù)據(jù)傳輸路徑可選擇性越高，能量消耗也就越平均，這就降低低能量節(jié)點(diǎn)，最終控制了部署成本。與MBA算法相比，提出的MST-DENP算法有效地控制部署成本。

4 結(jié) 語

針對(duì)WSNs的能量問題，分析了可持續(xù)WSNs網(wǎng)絡(luò)。利用無線電對(duì)低能量節(jié)點(diǎn)進(jìn)行補(bǔ)給。依據(jù)節(jié)點(diǎn)能量采集計(jì)算各邊權(quán)益值，并利用Kruskal算法構(gòu)建最小生成樹，最后利用最小生成樹部署能量補(bǔ)給節(jié)點(diǎn)。實(shí)驗(yàn)數(shù)據(jù)表明，提出的MST-DENP算法降低了成本，并提出了數(shù)據(jù)包傳遞率。后期，將優(yōu)化MST-DENP算法，進(jìn)一步減少部署成本，使其性能逼近ILP性能。

：

[1] D. Yang, S. Misra, X. Fang, G. Xue, and J. Zhang.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ǎng)絡(luò)成簇算法[J].傳感技術(shù)學(xué)報(bào),2015,28(2):244-248.

[3] Z. Zheng, L. X. Cai, R. Zhang, and X. S. Shen.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.

[4] A. Chelli, M. Bagaa, D. Djenouri, I. Balasingham, and T. Taleb.One-step approach for two-tiered constrained relay node placement in wireless sensor networks[J]. IEEE Wireless Commun. Letters, 2016,5(4): 448-451.

[5] R. V. Prasad, S. Devasenapathy, V. S. Rao, and J. Vazifehdan. Reincarnation in the ambiance: Devices and networks with energy harvesting[J].IEEE Commun. Surveys and Tutorials, 2014,16(1): 195-213.

[6] A. Castagnetti, A. Pegatoquet, T. N. Le, and M. Auguin. A joint duty-cycle and transmission power management for energy harvesting wsn[J].IEEE Trans. Industrial Informatics,2014,10(2): 928-936.

[7] N. Michelusi and M. Zorzi. Optimal adaptive random multi-access in energy harvesting wireless sensor networks[J]. IEEE Transactions on Communications, 2015,63(4): 1355-1372.

[8] P. Zhang, G. Xiao, and H.-P. Tan. Clustering algorithms for maximizing the lifetime of wireless sensor networks with energy-harvesting sensors[J].Computer Networks,2013,57(14): 2689-2704.

[9] S. Misra, N. E. Majd, and H. Huang. Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks[J]. IEEE Trans. Computers,2014,63(12):23-33.

[10] K. Huang and V. K. N. Lau. Enabling wireless power transfer in cellular networks: Architecture, modeling and deployment[J].IEEE Transactions on Wireless Communications, 2014,13(2):902-912.

[11] K. Huang and X. Zhou. Cutting the last wires for mobile communications by microwave power transfer[J].IEEE Communications Magazine,2015,53(6): 86-93.

[12] M. Xia and S. A¨ssa. On the efficiency of far-field wireless power transfer[J].IEEE Trans. Signal Processing, 2015,63(11): 2835-2847.

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

[14] D. Djenouri and M. Bagaa. Energy harvesting aware relay node addition for power-efficient coverage in wireless sensor networks[C].in IEEE International Conference on Communications, ICC, London, UK, 2015: 86-91.