張 磊 王 然

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

0 引 言

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

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

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

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

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

本文的主要貢獻如下:

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

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

(3) 進行了一系列仿真實驗驗證了本文算法的有效性。

1 模型與問題定義

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

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

(1)

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

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

(2)

對式(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對目標(biāo)t的監(jiān)測增益。

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

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

(6)

(7)

1.3 能量采集模型

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

Ei=ω·τ·ξ·δi

(8)

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

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

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

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

1.5 問題定義

本文主要研究由太陽能傳感器和普通傳感器組成的無線傳感網(wǎng)絡(luò)的網(wǎng)絡(luò)生命周期問題。每輪從隨機部署的太陽能節(jié)點集合Sr和普通節(jié)點集合Sc中選擇部分節(jié)點工作，使A中的每個目標(biāo)滿足最低的概率覆蓋要求，且整個網(wǎng)絡(luò)保持連通。通過K輪的傳感器睡眠-喚醒調(diào)度，得到其所對應(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的計算如下：

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

(10)

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

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

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

證明：在文獻[17]中，作者首次提出了以最大化網(wǎng)絡(luò)生命周期為目標(biāo)的連通目標(biāo)覆蓋(CTC)問題，并通過將該問題建模為一個最大覆蓋樹(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時，本文研究的問題就轉(zhuǎ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)以及匯點之間的抽象關(guān)系構(gòu)建了圖P=(S∪A∪{s}∪{t},E)，如圖1所示。其中：S表示傳感器集合；A表示目標(biāo)集合；s表示一個虛擬點；t表示匯點(基站)；E表示邊的集合。

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

(1) 虛擬邊：任意目標(biāo)與虛擬點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)的傳感器或者匯點相連通的邊，邊的容量設(shè)置為+∝。即?si∈S,?sj∈S∪{t}，如果di,j∈E，且的容量等于+∝。

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

(11)

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

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

2.2 MOWMF算法

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

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

(12)

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

當(dāng)我們通過網(wǎng)絡(luò)流算法確定了合適的傳感器集合之后，還需要確定傳感器集合的工作時間。在本文中，我們采用了固定長度時間片的方式，讓被選出的傳感器工作一段固定的時間并更新傳感器節(jié)點的權(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é)點添加到集合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)；

/*傳感器的剩余能量不足以維持一個t0時間片*/

18.T=T∪{tk}；

19.k=k+1；

20.reGenerate(P)；

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

21.goto 4；

22.return {T,C}；

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

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

其中：flow表示路徑中新增的流值；weight表示新增節(jié)點的權(quán)值；id表示搜索過程中節(jié)點的編號；pre表示前驅(qū)節(jié)點。在優(yōu)先級隊列中，擁有最大比值flow/weight的節(jié)點排在隊首，通過每次彈出隊首元素來尋找最優(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計算增廣路徑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é)點的剩余能量*/

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

18.newNode.pre=node；

19.Q.push(newNode)；

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

3 模擬實驗

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

表1 實驗參數(shù)

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

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

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

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

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

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

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

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

4 結(jié) 語

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