能量采集無線傳感網(wǎng)絡(luò)中的概率目標(biāo)覆蓋問題

張 磊 王 然

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院 浙江 杭州 310018)

0 引 言

網(wǎng)絡(luò)生命周期用于評(píng)估已部署的無線傳感網(wǎng)絡(luò)在滿足其應(yīng)用需求的情況下能夠正常工作多長時(shí)間，是無線傳感網(wǎng)絡(luò)中一個(gè)重要的研究話題。在以前，傳感器節(jié)點(diǎn)主要是由普通的不可充電的電池供電。這種不可充電的普通傳感器節(jié)點(diǎn)只有有限的運(yùn)行時(shí)間，當(dāng)傳感器處于休眠狀態(tài)時(shí)，電池的電量并不能得到恢復(fù)。近些年來，能夠從環(huán)境能源中獲取能量的可充電傳感器節(jié)點(diǎn)開始被越來越多地應(yīng)用到無線傳感網(wǎng)絡(luò)中[1]，可以明顯地延長網(wǎng)絡(luò)生命周期。理論上講，無線傳感網(wǎng)絡(luò)中可充電節(jié)點(diǎn)越多，網(wǎng)絡(luò)的生命周期越長。但是，由于可充電節(jié)點(diǎn)的制作成本比普通傳感器的成本要高得多，因此在大型的無線傳感網(wǎng)絡(luò)中全部部署可充電節(jié)點(diǎn)是不現(xiàn)實(shí)的。一種可行的方法是部署由普通傳感器和可以充電的傳感器組成的混合無線傳感網(wǎng)絡(luò)[2]。為了充分利用可充電節(jié)點(diǎn)的優(yōu)勢，需要對(duì)混合無線傳感網(wǎng)絡(luò)中的傳感器進(jìn)行合理的調(diào)度。

文獻(xiàn)[3]把延長網(wǎng)絡(luò)生命周期問題建模為最大覆蓋集問題，并證明了該問題是NP-Complete問題，同時(shí)利用線性規(guī)劃和貪心策略設(shè)計(jì)了兩種有效的啟發(fā)式算法。文獻(xiàn)[4]把目標(biāo)連通覆蓋問題建模為一個(gè)最大覆蓋樹(MCT)問題，并證明了該問題是NP-Complete的，同時(shí)提出了一種有效的快速啟發(fā)式算法。文獻(xiàn)[5]針對(duì)k-覆蓋和Q-覆蓋問題提出了一種使網(wǎng)絡(luò)壽命最大化的節(jié)能方案，通過動(dòng)態(tài)更新傳感器的優(yōu)先級(jí)形成不同的覆蓋集合，從而延長網(wǎng)絡(luò)壽命。文獻(xiàn)[6]給出了定向傳感網(wǎng)絡(luò)的最大覆蓋集問題，并提出了一個(gè)基于貪心算法的目標(biāo)覆蓋調(diào)度方案，在此基礎(chǔ)上又提出了一種基于遺傳算法的目標(biāo)覆蓋調(diào)度方案，實(shí)驗(yàn)表明基于遺傳算法的調(diào)度方案能更好地延長網(wǎng)絡(luò)生命周期。文獻(xiàn)[7]首次提出了在定向傳感網(wǎng)絡(luò)(DSN)中傳感器功率可調(diào)的最大網(wǎng)絡(luò)生命周期問題(MNLAR)，并提出了兩種啟發(fā)式算法來解決這個(gè)問題。由于傳感器隨機(jī)部署可能滿足不了目標(biāo)的覆蓋要求，文獻(xiàn)[8]提出了移動(dòng)傳感器部署的問題(MSD)，通過最小化傳感器的移動(dòng)距離來延長網(wǎng)絡(luò)生命周期。

上述研究工作的傳感器監(jiān)測模型都是基于0/1圓盤模型，該模型只是對(duì)實(shí)際監(jiān)測模型的粗略近似，相較于0/1圓盤模型，概率監(jiān)測模型能夠更好地反映真實(shí)環(huán)境中傳感器的監(jiān)測情況。文獻(xiàn)[9]研究了基于概率監(jiān)測模型下的柵欄覆蓋問題，并引入了流圖的概念，在此基礎(chǔ)上提出了一種解決多項(xiàng)式時(shí)間調(diào)度問題的近似算法。文獻(xiàn)[10]采用概率監(jiān)測模型來解決連通目標(biāo)覆蓋問題(CTC)，并提出了一種有效的啟發(fā)式算法CWGC-PM來延長網(wǎng)絡(luò)壽命。文獻(xiàn)[11]也是基于概率監(jiān)測模型解決連通目標(biāo)覆蓋問題，與文獻(xiàn)[10]不同的是文獻(xiàn)[11]是通過圖論的方法把連通目標(biāo)覆蓋問題映射成一個(gè)流圖，并提出了一個(gè)有效的近似算法。

近年來，能量采集技術(shù)被應(yīng)用于無線傳感網(wǎng)絡(luò)中，將環(huán)境能量轉(zhuǎn)換成電能，可以有效地延長網(wǎng)絡(luò)壽命[12]。文獻(xiàn)[13]提出了在能量采集無線傳感網(wǎng)絡(luò)中的永久性目標(biāo)覆蓋問題，并證明了該問題是NP-Complete問題，同時(shí)設(shè)計(jì)了一個(gè)有效的多項(xiàng)式算法來解決該問題。文獻(xiàn)[14]首次解決了在能量采集無線傳感網(wǎng)絡(luò)中的連通目標(biāo)覆蓋問題，文中提出了兩種解決方案，第一種是基于線性規(guī)劃的直接求解，第二種是基于貪心策略的啟發(fā)式方法。文獻(xiàn)[15]提出了一個(gè)關(guān)于能量采集傳感器節(jié)點(diǎn)部署位置的新問題，他們的目標(biāo)是通過確定部署位置，最小化放置傳感器節(jié)點(diǎn)的數(shù)量，使網(wǎng)絡(luò)滿足連通目標(biāo)覆蓋的同時(shí)保證每個(gè)節(jié)點(diǎn)的能量收支平衡。文獻(xiàn)[16]研究了由普通傳感器和太陽能傳感器組成的混合無線傳感網(wǎng)絡(luò)的最大生命周期問題，文中提出了一種可信信息覆蓋模型，并設(shè)計(jì)了一種基于優(yōu)先級(jí)的貪婪調(diào)度算法(PGS)，但他們并沒有考慮網(wǎng)絡(luò)的連通以及傳感器的剩余能量對(duì)網(wǎng)絡(luò)壽命的影響。

與現(xiàn)有工作不同，本文研究的是在概率監(jiān)測模型下，由普通傳感器和太陽能傳感器組成的混合無線傳感網(wǎng)絡(luò)的最大生命周期問題。本文的工作旨在滿足連通目標(biāo)覆蓋的同時(shí)，盡可能地延長網(wǎng)絡(luò)壽命。本文考慮了不同的光照強(qiáng)度以及傳感器的剩余能量對(duì)網(wǎng)絡(luò)壽命的影響，充分利用了網(wǎng)絡(luò)中分布不均勻的能量。

本文的主要貢獻(xiàn)如下:

(1) 首次探究了在由普通傳感器和太陽能傳感器組成的混合無線傳感網(wǎng)絡(luò)中基于概率連通目標(biāo)覆蓋下的最大生命周期問題，建立了非線性整型數(shù)學(xué)模型。

(2) 證明了該問題是一個(gè)NP-hard問題，并通過圖論的方法設(shè)計(jì)了一個(gè)近似算法。該算法選擇喚醒剩余能量更充足且對(duì)整個(gè)網(wǎng)絡(luò)貢獻(xiàn)更大的節(jié)點(diǎn)，因此能夠更有效地利用環(huán)境能源。

(3) 進(jìn)行了一系列仿真實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

1 模型與問題定義

1.1 傳感器監(jiān)測模型

傳感器的監(jiān)測模型采用文獻(xiàn)[17]中給出的指數(shù)衰減概率監(jiān)測模型，如式(1)中所示。目標(biāo)的監(jiān)測概率是與目標(biāo)跟傳感器之間的距離有關(guān)的遞減函數(shù)。

(1)

式中：λ表示與傳感器物理特性相關(guān)的強(qiáng)度系數(shù)；di,j表示傳感器i和目標(biāo)j之間的距離；Rs表示傳感器的監(jiān)測半徑。

假如任意一個(gè)目標(biāo)，它的監(jiān)測概率要求不小于ε，那么對(duì)于被傳感器集合St所監(jiān)測到的目標(biāo)t來說，滿足式(2)。

(2)

對(duì)式(2)做如下變型:

(3)

由式(3)我們可以給出總監(jiān)測閾值和傳感器監(jiān)測增益的定義：

定義1監(jiān)測閾值：

Ψ=-ln(1-ε)

(4)

式中：Ψ表示目標(biāo)需要滿足的最低的監(jiān)測增益要求。

定義2監(jiān)測增益：

ψi,t=-ln(1-pi,t)

(5)

式中：ψi,t表示傳感器si對(duì)目標(biāo)t的監(jiān)測增益。

1.2 數(shù)據(jù)通信與能量消耗模型

傳感器監(jiān)測目標(biāo)時(shí)會(huì)持續(xù)產(chǎn)生監(jiān)測數(shù)據(jù)，數(shù)據(jù)需要通過傳感器傳遞給基站。在這個(gè)過程中，不同的傳感器承擔(dān)著不同的作用，有的傳感器只作為監(jiān)測節(jié)點(diǎn)，承擔(dān)監(jiān)測目標(biāo)和傳輸數(shù)據(jù)的功能，有的傳感器既要承擔(dān)監(jiān)測功能又要作為多個(gè)傳感器節(jié)點(diǎn)的中繼轉(zhuǎn)發(fā)數(shù)據(jù)，能量消耗會(huì)比較高。節(jié)點(diǎn)的能量消耗大體可以分為三類，分別為監(jiān)測數(shù)據(jù)能耗、傳輸數(shù)據(jù)能耗和接收數(shù)據(jù)能耗。假設(shè)監(jiān)測節(jié)點(diǎn)單位時(shí)間產(chǎn)生的監(jiān)測數(shù)據(jù)為μbit，li,j表示傳感器si是否與傳感器sj通信，傳感器節(jié)點(diǎn)單位比特?cái)?shù)據(jù)產(chǎn)生的監(jiān)測能耗、傳輸能耗和接收能耗分別表示為es、et和er，Ωs和Ωr分別表示為監(jiān)測節(jié)點(diǎn)集合以及中繼節(jié)點(diǎn)集合。我們給出傳感器節(jié)點(diǎn)的數(shù)據(jù)通信及能量消耗模型，如式(6)、式(7)所示，fi表示傳感器si單位時(shí)間內(nèi)需要轉(zhuǎn)發(fā)的數(shù)據(jù)流量，ei表示傳感器si單位時(shí)間的能量消耗。

(6)

(7)

1.3 能量采集模型

目標(biāo)區(qū)域由太陽能傳感器和普通傳感器混合部署，不同的太陽能傳感器由于接收光的位置、天氣和障礙物的阻擋，導(dǎo)致其所對(duì)應(yīng)的光照強(qiáng)度不同，所以單位時(shí)間內(nèi)收集到的能量也不同。我們使用的是同構(gòu)的太陽能傳感器，不同的太陽能傳感器ri在單位時(shí)間內(nèi)收集到的能量可由式(8)表示。

Ei=ω·τ·ξ·δi

(8)

式中：ω表示太陽能電池板的能量轉(zhuǎn)化率；τ為太陽能電池板的表面積；ξ為太陽能節(jié)點(diǎn)的充電效率；δi為太陽能輻射強(qiáng)度。

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

我們在一個(gè)長度為L、寬度為W的矩形監(jiān)測區(qū)域中，隨機(jī)部署N個(gè)普通傳感器和M個(gè)能夠收集環(huán)境能源的太陽能傳感器，所有傳感器位置的集合分別為Sc={c1,c2,…，cN}和Sr={r1,r2,…，rM}。同時(shí)，隨機(jī)部署D個(gè)需要被監(jiān)測的目標(biāo)，目標(biāo)位置的集合為A={a1,a2,…，aD}，Sc∩A=?且Sr∩A=?。

在監(jiān)測區(qū)域中，存在一個(gè)基站o，用于收集所有監(jiān)測節(jié)點(diǎn)所監(jiān)測到的目標(biāo)信息，每個(gè)目標(biāo)需要達(dá)到最低的概率覆蓋要求，同時(shí)每個(gè)監(jiān)測節(jié)點(diǎn)需要直接或間接地與匯點(diǎn)保持通信(通過中繼節(jié)點(diǎn))。

1.5 問題定義

本文主要研究由太陽能傳感器和普通傳感器組成的無線傳感網(wǎng)絡(luò)的網(wǎng)絡(luò)生命周期問題。每輪從隨機(jī)部署的太陽能節(jié)點(diǎn)集合Sr和普通節(jié)點(diǎn)集合Sc中選擇部分節(jié)點(diǎn)工作，使A中的每個(gè)目標(biāo)滿足最低的概率覆蓋要求，且整個(gè)網(wǎng)絡(luò)保持連通。通過K輪的傳感器睡眠-喚醒調(diào)度，得到其所對(duì)應(yīng)的工作周期集合為{t1,t2,…,tK}，我們的目標(biāo)是使T=t1+t2+…+tK最大。

本文問題可表示為如下非線性0-1整數(shù)規(guī)劃問題：

(9)

s.t.

0≤Bi≤B?si∈S

xi∈{0,1}，yi∈{0,1} ?i=1,2,…，N

li,j∈{0,1} ?i=1,2,…，N?j=1,2,…，N+1

mi∈{0,1} ?i=1,2,…，N

式中：Bi表示傳感器si的剩余能量。Bi的計(jì)算如下：

Bi=min{(Bi-xi·(ei·tk+yi·Ei·tk)),B}

(10)

yi=0時(shí)表示傳感器si是普通傳感器；yi=1時(shí)表示傳感器si是太陽能傳感器；xi=0時(shí)表示傳感器si是睡眠狀態(tài)；xi=1時(shí)表示傳感器si是被喚醒狀態(tài)。mi=0時(shí)表示處于喚醒狀態(tài)傳感器si不是監(jiān)測節(jié)點(diǎn)，即不執(zhí)行監(jiān)測功能；mi=1時(shí)表示處于喚醒狀態(tài)的傳感器si是監(jiān)測節(jié)點(diǎn)，即執(zhí)行監(jiān)測功能。

式(9)中各約束分別表示：各個(gè)傳感器的總能量約束、各個(gè)狀態(tài)下傳感器的能量約束、任何目標(biāo)都要滿足覆蓋要求、任意傳感器的收發(fā)數(shù)據(jù)量守恒、到達(dá)基站的數(shù)據(jù)流量與監(jiān)測目標(biāo)產(chǎn)生的數(shù)據(jù)流量相等。

定理1能量采集無線傳感網(wǎng)絡(luò)中概率目標(biāo)覆蓋的最大生命周期問題是NP-hard問題。

證明：在文獻(xiàn)[17]中，作者首次提出了以最大化網(wǎng)絡(luò)生命周期為目標(biāo)的連通目標(biāo)覆蓋(CTC)問題，并通過將該問題建模為一個(gè)最大覆蓋樹(MCT)問題，證明了其NP完全性。本文研究的是在異構(gòu)傳感器網(wǎng)絡(luò)中，基于概率覆蓋模型下以最大化網(wǎng)絡(luò)生命周期為目標(biāo)的連通目標(biāo)覆蓋問題。當(dāng)太陽能傳感器在網(wǎng)絡(luò)中的能量收集率Ei等于0、目標(biāo)的監(jiān)測概率要求ε=e-λRs時(shí)，本文研究的問題就轉(zhuǎn)化為文獻(xiàn)[17]中的CTC問題，同構(gòu)連通目標(biāo)覆蓋是異構(gòu)概率連通目標(biāo)覆蓋的一種特殊情況，因此，能量采集無線傳感網(wǎng)絡(luò)中概率目標(biāo)覆蓋的最大生命周期是NP-hard問題。

2 問題轉(zhuǎn)化與算法

2.1 問題轉(zhuǎn)化

我們通過網(wǎng)絡(luò)中不同類型的傳感器與目標(biāo)以及匯點(diǎn)之間的抽象關(guān)系構(gòu)建了圖P=(S∪A∪{s}∪{t},E)，如圖1所示。其中：S表示傳感器集合；A表示目標(biāo)集合；s表示一個(gè)虛擬點(diǎn)；t表示匯點(diǎn)(基站)；E表示邊的集合。

圖1中有三種代表不同關(guān)系的邊：

(1) 虛擬邊：任意目標(biāo)與虛擬點(diǎn)s相連通的邊，邊的容量設(shè)置為Ψ。即?ai∈A,∈E，的容量等于Ψ。

(2) 監(jiān)測邊：任意傳感器與其監(jiān)測范圍內(nèi)的目標(biāo)相連通的邊，邊的容量設(shè)置為ψi,j。即?si∈S,?ai∈A，如果di,j∈E，且的容量等于ψi,j。

(3) 通信邊：任意傳感器與其通信范圍內(nèi)的傳感器或者匯點(diǎn)相連通的邊，邊的容量設(shè)置為+∝。即?si∈S,?sj∈S∪{t}，如果di,j∈E，且的容量等于+∝。

定義3節(jié)點(diǎn)的權(quán)值：

(11)

式中：wi表示在網(wǎng)絡(luò)流圖中代表傳感器si的節(jié)點(diǎn)i的權(quán)值。

定義4最優(yōu)權(quán)值最大流問題：在本文構(gòu)建的網(wǎng)絡(luò)流圖P=(S∪A∪{s}∪{t},E)中，尋找權(quán)值最小的節(jié)點(diǎn)集合C?S，使得子圖P′=(C∪A∪{s}∪{t},E′)的最大流等于D·Ψ。

2.2 MOWMF算法

最優(yōu)權(quán)值最大流問題的目的是在每一輪傳感器選擇的過程中尋找有充足剩余能量的傳感器組合，同時(shí)保證網(wǎng)絡(luò)連通和覆蓋的要求。通過解決多輪最優(yōu)權(quán)值最大流，得到多種傳感器睡眠-喚醒調(diào)度策略，使網(wǎng)絡(luò)生命周期得以延長。

針對(duì)最優(yōu)權(quán)值最大流問題，本文使用了一種基于FindPathEx增廣路徑搜索算法的網(wǎng)絡(luò)流算法，其與傳統(tǒng)的網(wǎng)絡(luò)流算法最大的不同就是在于尋找增廣路徑的方法。FindPathEx增廣路徑搜索算法的主要思想是每次都尋找比值ρ最大的增廣路徑：

(12)

在這種選取策略下，那些流值較大、新增節(jié)點(diǎn)的權(quán)值較小的路徑將會(huì)被優(yōu)先選取出來。根據(jù)之前定義的節(jié)點(diǎn)的權(quán)值可以知道，節(jié)點(diǎn)的權(quán)值越小，說明節(jié)點(diǎn)的剩余能量越大，即節(jié)點(diǎn)的能量消耗更小，能量收集更大。這樣的選取策略符合現(xiàn)實(shí)場景的需求，那些有著高能量收集效率的太陽能節(jié)點(diǎn)會(huì)被優(yōu)先選取，能夠充分利用環(huán)境能源。當(dāng)ρ=0時(shí)，說明網(wǎng)絡(luò)當(dāng)前的流量就是最大流，再也找不到新的增廣路徑。

當(dāng)我們通過網(wǎng)絡(luò)流算法確定了合適的傳感器集合之后，還需要確定傳感器集合的工作時(shí)間。在本文中，我們采用了固定長度時(shí)間片的方式，讓被選出的傳感器工作一段固定的時(shí)間并更新傳感器節(jié)點(diǎn)的權(quán)值，然后執(zhí)行新一輪的網(wǎng)絡(luò)流算法，選出新的合適的傳感器集合。MOWMF算法流程如算法1所示。

算法1MOWMF算法

輸入：傳感器集合S=Sc∪Sr，目標(biāo)集合A，基站t。

輸出：生命周期T，傳感器子集C={C1,C2,…，CK}。

1.生成網(wǎng)絡(luò)流圖P=(S∪A∪{s}∪{t},E)；

2.k=1；

3.Ck=?；

4.sumflow=0；

5.調(diào)用算法2尋找一條增廣路徑o(s,t)，增廣路徑的流等于f；

6.iff≠0 then

7.sumflow+=f；

8.addTo(o(s,t),Ck)

/*把增廣路徑o(s,t)中的新增節(jié)點(diǎn)添加到集合Ck中*/

9.goto 5；

10.else then

11.ifsumflow≥D·Ψthen

12.C=C∪{Ck}；

13.tk=t0；

14.for each nodeiinCkdo

15.updateBiandwi；

16.ifwi≥1 then

17.tk=min(tk,Bi/ei)；

/*傳感器的剩余能量不足以維持一個(gè)t0時(shí)間片*/

18.T=T∪{tk}；

19.k=k+1；

20.reGenerate(P)；

/*重新生成網(wǎng)絡(luò)流圖*/

21.goto 4；

22.return {T,C}；

FindPathEx增廣路徑搜索算法利用了優(yōu)先級(jí)隊(duì)列和廣度優(yōu)先搜索算法，在搜索時(shí)使用Node類來記錄節(jié)點(diǎn)的信息。

class Node { intid; Nodepre; floatflow; floatweight; }

其中：flow表示路徑中新增的流值；weight表示新增節(jié)點(diǎn)的權(quán)值；id表示搜索過程中節(jié)點(diǎn)的編號(hào)；pre表示前驅(qū)節(jié)點(diǎn)。在優(yōu)先級(jí)隊(duì)列中，擁有最大比值flow/weight的節(jié)點(diǎn)排在隊(duì)首，通過每次彈出隊(duì)首元素來尋找最優(yōu)的增廣路徑。FindPathEx搜索算法流程如算法2所示。

算法2FindPathEx搜索算法

輸入：P=(S∪A∪{t}∪{t},E)。

輸出：增廣路徑o(s,t)，增廣流f。

1.flow=0；

2.priorityQueueQ；

3.node=newNode(s)；

4.Q.push(node)；

5.whileQis not empty do

6.Nodenode=Q.pop()；

7.ifnode.id=tthen

8.flow=node.flow；

9.o(s,t)=getPath(node.pre)

/*根據(jù)node.pre計(jì)算增廣路徑o(s,t)*/

10.break；

11.v=node.id；

12.setvvisited；

13.for each neighborsiofvdo

14.ifinot visited andflowof>0 then

15.newNode=newNode(i)；

16.updateEnergy(i)；

/*更新節(jié)點(diǎn)的剩余能量*/

17.newNode.flow=min(flowof ,node.flow)；

18.newNode.pre=node；

19.Q.push(newNode)；

20.return {flow,o(s,t)}；

3 模擬實(shí)驗(yàn)

在本節(jié)中，我們模擬了一個(gè)由普通傳感器和太陽能傳感器組成的混合無線傳感網(wǎng)絡(luò)，所有的傳感器均勻分布在隨機(jī)部署了若干個(gè)目標(biāo)的矩形區(qū)域中，區(qū)域面積固定在200 m×150 m。為了方便，我們把每個(gè)太陽能傳感器的光照強(qiáng)度設(shè)置為[0,480] W/m2之間的隨機(jī)數(shù)。通過一系列仿真實(shí)驗(yàn)對(duì)MOWMF算法進(jìn)行了性能評(píng)估，并與其他相關(guān)算法進(jìn)行了對(duì)比。表1為實(shí)驗(yàn)相關(guān)的仿真參數(shù)及其數(shù)值。

表1 實(shí)驗(yàn)參數(shù)

3.1 不同參數(shù)對(duì)算法性能的影響

我們通過改變相關(guān)的實(shí)驗(yàn)參數(shù)來探究不同因素對(duì)MOWMF算法的影響，這些參數(shù)包括了太陽能傳感器所占的比例、覆蓋要求、傳感器的總數(shù)量等。對(duì)于所有的實(shí)驗(yàn)結(jié)果，我們均進(jìn)行了100次模擬實(shí)驗(yàn)，最終取平均值。

在圖2中，我們主要考慮的是太陽能傳感器所占的比例對(duì)算法性能的影響。我們把目標(biāo)數(shù)量固定在40，傳感器的總數(shù)量為200～400，覆蓋要求設(shè)置為0.8。可以看出，隨著傳感器總數(shù)量的增加，網(wǎng)絡(luò)壽命也在延長，而在傳感器總數(shù)量相同的情況下，太陽能傳感器所占比例越大，網(wǎng)絡(luò)壽命也越長。這是因?yàn)閭鞲衅鲾?shù)量越多，可以完成目標(biāo)覆蓋要求的傳感器組合也就越多。另一方面，由于太陽能傳感器可以收集能量，延長使用壽命，所以太陽能傳感器所占的比例越高，網(wǎng)絡(luò)壽命也就越長。

圖3中顯示了目標(biāo)的覆蓋要求對(duì)算法性能的影響。目標(biāo)數(shù)量和傳感器的總數(shù)量分別固定在40和300。可以看出，目標(biāo)的覆蓋要求越高，網(wǎng)絡(luò)生命周期越短。這是因?yàn)殡S著覆蓋要求的提高，平均每個(gè)目標(biāo)需要被更多的傳感器所監(jiān)測，網(wǎng)絡(luò)中被喚醒的傳感器數(shù)目增多，傳感器的能量消耗增加，從而使網(wǎng)絡(luò)壽命變短。

3.2 與其他相關(guān)算法的比較

針對(duì)延長由普通傳感器和太陽能傳感器組成的混合無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)生命周期問題，我們將MOWMF算法與文獻(xiàn)[2]中提出的基于優(yōu)先級(jí)的貪婪調(diào)度算法(PGS)以及基于優(yōu)先級(jí)的隨機(jī)選擇算法(PRAN)進(jìn)行了比較。由于這兩種算法對(duì)應(yīng)的模型與本文模型有一些差異，我們這里只采用其算法思想應(yīng)用到本文的模型中。

我們把目標(biāo)數(shù)量固定在40，傳感器的總數(shù)量為200～400，太陽能傳感器所占比例為20%，覆蓋要求設(shè)置為0.8。如圖4所示，在傳感器數(shù)量以及太陽能傳感器所占比例相同的情況下，MOWMF算法要優(yōu)于另外兩種。PGS算法是基于優(yōu)先級(jí)的貪婪調(diào)度策略，該算法把傳感器集合分為已被喚醒的傳感器集合、未被喚醒的太陽能傳感器集合和未被喚醒的普通傳感器集合三類，每次都從優(yōu)先級(jí)更高的集合中選擇傳感器。PGS并未考慮傳感器的剩余能量，這樣就容易導(dǎo)致在陰天或者夜晚太陽能光照強(qiáng)度很弱的時(shí)候使太陽能節(jié)點(diǎn)更快地耗盡能量。MOWMF算法是根據(jù)傳感器的剩余能量、能量消耗、能量收集通過網(wǎng)絡(luò)流的方法來選擇更優(yōu)的傳感器節(jié)點(diǎn)。

圖5統(tǒng)計(jì)了在不同的算法場景下傳感器的平均剩余能量。可以看出，本文算法在算法執(zhí)行完成之后傳感器的剩余能量更少，能量利用率更高。這也進(jìn)一步說明了MOWMF算法的有效性。

4 結(jié) 語

本文基于概率連通目標(biāo)覆蓋模型研究了在能量采集無線傳感網(wǎng)絡(luò)中的生命周期問題，經(jīng)過分析發(fā)現(xiàn)該問題是一個(gè)NP-hard問題。為了解決這個(gè)問題，我們根據(jù)傳感器的剩余能量、能量消耗和太陽能傳感器的能量收集定義了傳感器的權(quán)值，并通過圖論的方法提出一個(gè)有效的近似算法。我們進(jìn)行了一系列的仿真實(shí)驗(yàn)，比較了太陽能傳感器所占的比例、傳感器的總數(shù)量和覆蓋要求等不同因素對(duì)網(wǎng)絡(luò)生命周期的影響，并通過與相關(guān)算法的比較證明了本文算法的有效性。未來將考慮增大那些剩余能量較高的太陽能節(jié)點(diǎn)的工作功率，從而進(jìn)一步提高環(huán)境能源的利用率。