能量采集無線傳感網絡中的概率目標覆蓋問題

張 磊 王 然

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

0 引 言

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

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

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

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

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

本文的主要貢獻如下:

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

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

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

1 模型與問題定義

1.1 傳感器監測模型

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

(1)

式中：λ表示與傳感器物理特性相關的強度系數；di,j表示傳感器i和目標j之間的距離；Rs表示傳感器的監測半徑。

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

(2)

對式(2)做如下變型:

(3)

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

定義1監測閾值：

Ψ=-ln(1-ε)

(4)

式中：Ψ表示目標需要滿足的最低的監測增益要求。

定義2監測增益：

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

(5)

式中：ψi,t表示傳感器si對目標t的監測增益。

1.2 數據通信與能量消耗模型

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

(6)

(7)

1.3 能量采集模型

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

Ei=ω·τ·ξ·δi

(8)

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

1.4 網絡模型

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

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

1.5 問題定義

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

本文問題可表示為如下非線性0-1整數規劃問題：

(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是睡眠狀態；xi=1時表示傳感器si是被喚醒狀態。mi=0時表示處于喚醒狀態傳感器si不是監測節點，即不執行監測功能；mi=1時表示處于喚醒狀態的傳感器si是監測節點，即執行監測功能。

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

定理1能量采集無線傳感網絡中概率目標覆蓋的最大生命周期問題是NP-hard問題。

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

2 問題轉化與算法

2.1 問題轉化

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

圖1中有三種代表不同關系的邊：

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

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

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

定義3節點的權值：

(11)

式中：wi表示在網絡流圖中代表傳感器si的節點i的權值。

定義4最優權值最大流問題：在本文構建的網絡流圖P=(S∪A∪{s}∪{t},E)中，尋找權值最小的節點集合C?S，使得子圖P′=(C∪A∪{s}∪{t},E′)的最大流等于D·Ψ。

2.2 MOWMF算法

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

針對最優權值最大流問題，本文使用了一種基于FindPathEx增廣路徑搜索算法的網絡流算法，其與傳統的網絡流算法最大的不同就是在于尋找增廣路徑的方法。FindPathEx增廣路徑搜索算法的主要思想是每次都尋找比值ρ最大的增廣路徑：

(12)

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

當我們通過網絡流算法確定了合適的傳感器集合之后，還需要確定傳感器集合的工作時間。在本文中，我們采用了固定長度時間片的方式，讓被選出的傳感器工作一段固定的時間并更新傳感器節點的權值，然后執行新一輪的網絡流算法，選出新的合適的傳感器集合。MOWMF算法流程如算法1所示。

算法1MOWMF算法

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

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

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

2.k=1；

3.Ck=?；

4.sumflow=0；

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

6.iff≠0 then

7.sumflow+=f；

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

/*把增廣路徑o(s,t)中的新增節點添加到集合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)；

/*重新生成網絡流圖*/

21.goto 4；

22.return {T,C}；

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

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

其中：flow表示路徑中新增的流值；weight表示新增節點的權值；id表示搜索過程中節點的編號；pre表示前驅節點。在優先級隊列中，擁有最大比值flow/weight的節點排在隊首，通過每次彈出隊首元素來尋找最優的增廣路徑。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)

/*根據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)；

/*更新節點的剩余能量*/

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

18.newNode.pre=node；

19.Q.push(newNode)；

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

3 模擬實驗

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

表1 實驗參數

3.1 不同參數對算法性能的影響

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

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

圖3中顯示了目標的覆蓋要求對算法性能的影響。目標數量和傳感器的總數量分別固定在40和300。可以看出，目標的覆蓋要求越高，網絡生命周期越短。這是因為隨著覆蓋要求的提高，平均每個目標需要被更多的傳感器所監測，網絡中被喚醒的傳感器數目增多，傳感器的能量消耗增加，從而使網絡壽命變短。

3.2 與其他相關算法的比較

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

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

圖5統計了在不同的算法場景下傳感器的平均剩余能量?？梢钥闯觯疚乃惴ㄔ谒惴▓绦型瓿芍髠鞲衅鞯氖Ｓ嗄芰扛?，能量利用率更高。這也進一步說明了MOWMF算法的有效性。

4 結 語

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