李騰龍

（杭州電子科技大學 計算機學院，浙江 杭州 310018）

0 引 言

柵欄覆蓋是無線傳感器網(wǎng)絡[1]的基本問題之一，根據(jù)入侵路線的不同，柵欄覆蓋可以分為強柵欄和弱柵欄。柵欄覆蓋廣泛應用于環(huán)境監(jiān)測、森林火災檢測等領域。由于傳感器節(jié)點電池能量的限制，如何延長柵欄覆蓋的網(wǎng)絡壽命是[2]一個關鍵問題。現(xiàn)有的延長柵欄壽命的方法有兩種：睡眠調度機制[2-7]和能量收集機制[8-9]。

Kumar[3]首先介紹了睡眠調度機制，通過控制無線傳感器網(wǎng)絡中傳感器的工作睡眠狀態(tài)，延長網(wǎng)絡的生命周期。一般來說，基于睡眠調度策略延長網(wǎng)絡生命周期的方法與網(wǎng)絡中冗余傳感器的數(shù)量有很強的相關性。

延長柵欄網(wǎng)絡壽命的另一種方法是部署具有能量收集能力的傳感器[8-9]。傳感器節(jié)點可以將環(huán)境中的能量轉換為電能[10-13]，因此，單個傳感器可以工作更長時間，從而延長網(wǎng)絡的使用壽命。具有能量收集能力的柵欄覆蓋最初是在文獻[2]中提出的，其目標是為柵欄應用提供最大的生命周期。

雖然睡眠調度機制和能量收集機制提供了可行的解決辦法，但是僅僅維持柵欄的持續(xù)工作是不夠的。一方面，通過控制構成柵欄的傳感器激活狀態(tài)可以延長網(wǎng)絡的工作壽命，但是由于單個傳感器電池容量的限制，其壽命也是有限的。另一方面，傳感器節(jié)點在獲取可再生能源的過程中往往受到環(huán)境的制約。例如，文獻[14]中能量收集系統(tǒng)高度依賴于陽光直射的強度。

隨著無線充電技術的發(fā)展，利用移動充電車[15-16]來延長網(wǎng)絡壽命越來越受到關注。本文我們將采用移動充電車（Mobile Charger，MC）與可充電傳感器構造可持續(xù)運行的k-弱柵欄。一個MC帶著足夠的電量從基站出發(fā)，分別訪問柵欄中的每個傳感器節(jié)點并對其進行充電，以保證k-弱柵欄持續(xù)運行，同時使MC在每個充電周期的平均能耗輸出最小。

1 可持續(xù)工作k-弱柵欄與移動充電策略

本文的目標是構建k-弱柵欄監(jiān)控區(qū)域內的入侵者，同時最小化MC的輸出能耗，包括移動能耗以及充電能耗。在弱柵欄中，入侵者的穿越路徑是垂直于監(jiān)控區(qū)域的。

1.1 柵欄調度和移動充電策略

在一個長為L寬為H的矩形區(qū)域隨機拋灑有n個靜止可充電傳感器，S={s1,s2,…,sn}。同時，區(qū)域中有一個MC為柵欄提供能量補充。

為了保證柵欄的可持續(xù)運行，我們在監(jiān)控區(qū)域中構建k+1條弱柵欄以保證網(wǎng)絡的k-弱柵欄覆蓋，同時MC為另一條柵欄進行充電。

我們設置k-弱柵欄網(wǎng)絡的運行時間片段為τ，在每個時間片段內，MC為一條柵欄充電，另外k條柵欄處于工作狀態(tài)。網(wǎng)絡的周期為T=(k+1)×τ，MC每個周期對每條柵欄充電服務一次，工作方式為一對一無線充電。

在每個周期T，每個傳感器節(jié)點只有一次充電機會，傳感器節(jié)點的初始電量均為E。傳感器節(jié)點si單位時間能耗為ωi，當傳感器節(jié)點的剩余電量小于Emin時，傳感器節(jié)點將進入睡眠狀態(tài)。因此，為了保證傳感器在任意時刻的電量都不小于Emin，傳感器節(jié)點si每次補充的電量必須不小于k×τ×ωi。

1.2 連續(xù)工作k-弱柵欄網(wǎng)絡的分析

當無線傳感器網(wǎng)絡工作時，根據(jù)柵欄調度以及充電策略，我們可以得到網(wǎng)絡的平均能耗，即MC的最小輸出功率EAVE：

其中，μi是第i條柵欄的表示符號，|μi|是充電對第i條柵欄充電時的移動距離，ε是MC單位距離移動能耗，α是MC能量轉化功率。在本文中，我們假定MC每次從左邊界(lslot)或者右邊界(rslot)的中心位置出發(fā)。如圖1所示，MC需要對兩條柵欄進行充電。

圖1 充電車移動路徑

為了保證節(jié)點在每個周期內不會能量耗盡而進入休眠狀態(tài)，每個傳感器節(jié)點的電池容量必須能夠連續(xù)工作kτ的時間。因此：

同時，MC必須能夠在一個時間片段內完成充電任務，即MC在一條柵欄中的移動時間和充電時間必須小于等于τ：

其中，v是MC移動速率，c為MC的輸出功率。從式（2）和式（3）我們可以得到：

其中，ωmax是傳感器節(jié)點的最大能耗速率。

MC每次從監(jiān)控區(qū)域的一側出發(fā)，沿著柵欄中傳感器的位置依次進行充電。如圖2所示，當監(jiān)控區(qū)域的長度滿足0<(L-rmin)mod(2rmin)≤rmin時，我們給出了一種長度最長的柵欄構造方法。傳感器節(jié)點沿著監(jiān)控區(qū)域的一側依次排列，同時相鄰兩個傳感器之間有一些空隙，另一側的傳感器節(jié)點對這些空隙進行填補。這種情況下構成弱柵欄的傳感器節(jié)點最多有柵欄長度為：

圖2 當0<(L-rmin)mod(2rmin)≤rmin，充電車最長移動距離

如圖3所示，當rmin<(L-rmin)mod(2rmin)或者(L-2rmin)mod(2rmin)=0，構成一條柵欄的傳感器節(jié)點上界為于是，柵欄長度為：

圖3 當rmin＜(L-rmin)mod(2rmin)≤rmin或者(L-rmin)mod(2rmin)=0，充電車最長移動距離

如圖4所示，我們在監(jiān)測區(qū)域的左右兩個停駐點連線位置從左到右布置傳感器節(jié)點。除了最后兩個傳感器節(jié)點之外，相鄰兩個節(jié)點的感知范圍恰好相互接觸。這時構成弱柵欄的傳感器節(jié)點的最小數(shù)目為同時，MC的最短移動距離為L。

圖4 充電車最短移動距離

于是，我們得到弱柵欄的長度范圍：

聯(lián)立式（4）和式（7），可以得到：

除了上面描述的限制條件，MC的能量必須要滿足移動和充電的需求，即：接著，聯(lián)立式（7）、式（9），可以得到：

這樣，我們得到了弱柵欄問題中，MC需要滿足的能量條件，即式（8）和（10）。

我們的優(yōu)化目標是最小化MC的輸出能耗，即網(wǎng)絡的平均能耗EAVE。從式（1）可知，網(wǎng)絡周期T越長，網(wǎng)絡的平均能耗EAVE越小。當無線傳感器網(wǎng)絡滿足我們的約束條件時，可以得到一個可行的無線充電調度方案。同時，由式（2）可知，我們設置時間片段τ的大小為

2 最小能耗k-弱柵欄構造與移動充電調度算法

2.1 算法步驟

2.1.1 構建基礎柵欄圖

我們把lslot設置為左邊界，把rslot設置為右邊界。

（1）對于任意一個傳感器節(jié)點s，如果它可以覆蓋到左邊界lslot，那么邊〈lslot,s〉∈E，邊對應的流量為1，即cap(lslot,s)=1。

（2）對于任意兩個傳感器節(jié)點si和sj，如果si和sj的感知區(qū)域在垂直方向上相互重疊，即|xixj|<(ri+rj)。那么，我們增加一條從si到sj的邊，即(si,sj)∈E；相應的邊流量為1，即cap(si,sj)=1。

（3）對于任意一個傳感器節(jié)點s，如果它可以覆蓋到右邊界rslot，那么邊〈s,rslot〉∈E，邊對應的流量為1，即cap(s,rslot)=1。

如圖5所示，在基本的柵欄構造圖中，如果網(wǎng)絡中存在k+1條不相交的路徑，那么我們可以得到k+1條柵欄。同時，在一條柵欄中，除了左右兩個停駐點之外，其它節(jié)點都有一個前驅節(jié)點和一個后繼節(jié)。這保證了相鄰兩個節(jié)點之間的流量為1，但是這并不能保證每個傳感器節(jié)點只屬于一條柵欄。我們將在下一節(jié)中使用分割點為邊的方法來保證每個傳感器節(jié)點僅屬于一條柵欄。

圖5 基本柵欄構造圖

2.1.2 分割點為邊

在本章節(jié)中，我們使用分割節(jié)點為邊的方法來限制節(jié)點的流量。如圖6所示，對于每個傳感器節(jié)點s，我們添加一個虛節(jié)點s′；接著，我們增加一條有向邊〈s,s′〉從s指向s′，同時，我們設置邊的容量為1。對于節(jié)點s與其它傳感器節(jié)點之間邊的關系，指向傳感器節(jié)點的邊都連向s，而從節(jié)點發(fā)出的邊都從虛節(jié)點s′出發(fā)。而對于一條無向邊來說，我們需要用兩條有向邊來表示，如圖7所示。

圖6 分割點的方法

圖7 無向圖中分割點的方法

每一條經(jīng)過節(jié)點s的流量必須通過邊〈s,s′〉，因此，邊的容量被限制為cap(s,s′)。分割節(jié)點為邊是通過把一個傳感器節(jié)點換成一條有容量限制的邊的策略來保證節(jié)點不會被重復使用，即避免了柵欄相交的可能性，如圖8所示。

圖8 柵欄覆蓋圖

為了保證柵欄數(shù)目為k+1，我們把節(jié)點rslot的容量限制為k+1。即增加rslot的虛節(jié)點r′slot以及有向 邊〈rslot,r′slot〉。 邊 的 容 量 為cap(rslot,r′slot)=k+1，費用為0。

2.1.3 權重分配

本章節(jié)的目標是找到最小的網(wǎng)絡平均能耗EAVE，對于我們找到的k+1條柵欄，根據(jù)式可以計算出EAVE的值：

MC的輸出能耗包括移動能耗以及對傳感器節(jié)點充電需要的能耗。我們設置w1=ε/T，w2=k/(k+1)α。其中，w1為MC在每個周期T移動一個單位（米）距離的能耗，w2為一個比例系數(shù)，它表示當傳感器節(jié)點的能耗速率為ωi時，MC每個周期T的能耗增量為w2×ωi。

我們?yōu)槊織l邊設置相應的權重，可以得到一個完整的柵欄圖。其中，頂點si與頂點s′i之間的有向邊設置權重為w2×ωi。相鄰兩個傳感器節(jié)點之間的有向邊，即頂點si和頂點sj之間的權重為w1×dist(si,sj)，其中，dist(si,sj)為節(jié)點si與sj之間的距離。

2.1.4 最小費用最大流算法

引理1:柵欄圖中最大流對應的傳感器節(jié)點可以構造k+1柵欄。

證明：根據(jù)柵欄圖構造的步驟1和步驟2，每個傳感器節(jié)點si可以分割成兩個節(jié)點si和s′i。同時，我們在節(jié)點si和s′i之間增加一條有向邊，邊的容量為1。這樣，每個傳感器節(jié)點的流量都被限制為1，傳感器節(jié)點都具有一個前驅節(jié)點和一個后繼節(jié)點。因此，從lslot到rslot的增廣路徑一定是相互排斥的。另外，我們把節(jié)點rslot的流量設置為k+1，因此，整個網(wǎng)絡的最大流為k+1。在文獻[3]中有k+1條不相交路徑可以構建k+1條柵欄。

定理1：柵欄覆蓋圖的最小費用為EAVE。

證明：根據(jù)引理1，從lslot到rslot的增廣路徑一定是相互排斥的。我們假定一條增廣路徑為μi=〈lslot,sa,s′a,sb,s′b,…,sz,s′z,rslot,r′slot〉，相應的總費用增加的值為w1×dist(lslot,sa)+w2×ωa+w1×dist(s′z,sb)+w2×ωb+…+w2×ωz+w1×dist(s′z,rslot)+0=w1+|μ|+w2×(ωa+…+ωz)。我們記ψ=|μ1|+…+|μk+1|，那么，k+1 條增廣路徑增加的總費用為EAVE=w1×ψ+w2Σμ1∪…∪μk+1ωi。因此，柵欄覆蓋圖的最小費用為EAVE。

2.2 算法近似度分析

假定MC對單條柵欄進行充電時的最大移動路徑長度為：

我們記問題的最優(yōu)解為E*。當傳感器沿著左右停駐點(lslot,rslot)位置的連線方向依次布置時，MC的移動距離以及充電能耗都可以得到最小值。同時，我們采用相同的周期計算網(wǎng)絡的最優(yōu)解E*：

根據(jù)式（13）以及式（14），可以計算出算法的近似度為O(k)：

3 模擬實驗

本章利用C++設計了模擬實驗，并設計了一個貪心算法與我們的近似算法進行比較。貪心算法首先采用最小費用最大流求出k+1條柵欄，接著采用和近似算法相同的充電調度策略。

我們在一個矩形區(qū)域內隨機拋灑了200個傳感器節(jié)點，區(qū)域寬度為30 m，長度從100 m一直增加到300 m。同時設置傳感器的初始電量為E=1 000 J，傳感器si單位時間能耗為傳感器節(jié)點的感知半徑在19～23 m之間隨機分布。MC電量滿足一條柵欄的能耗需求，移動速率為5 m/s，移動能耗為100 J/m，充電輸出功率為5 J/s，能量轉化率為0.976 5。

如圖9所示，在不同的區(qū)域長度下，我們提出的近似算法的平均能耗總是低于貪心算法的平均能耗。由于我們設置的傳感器數(shù)目相同，當區(qū)域長度最小時，網(wǎng)絡中傳感器節(jié)點最稠密，近似算法相比貪心算法的能耗節(jié)約百分比越大。因此，面對密集型傳感器網(wǎng)絡時，近似算法的優(yōu)化空間越大。

圖9 不同監(jiān)控區(qū)域長度時，近似算法網(wǎng)絡平均能耗相比貪心算法每周期減少的百分比

如圖10所示，我們在不同傳感器感知半徑下設置的節(jié)點數(shù)目是相同的，當半徑較小時，構成相同長度的柵欄所需要的傳感器數(shù)目越多，近似算法的能量節(jié)約百分比也越大。近似算法在構造柵欄時同時考慮了節(jié)點能耗和充電車移動能耗，所以當網(wǎng)絡規(guī)模越大，傳感器數(shù)目較多時，近似算法的優(yōu)化空間越大，能耗節(jié)約率自然越高。

圖10 近似算法網(wǎng)絡平均能耗相比貪心算法每周期減少的百分比

4 結 語

本文提出了一種結合k-弱柵欄構造與移動充電調度的近似算法。我們以最小化網(wǎng)絡平均能耗為目標，提出了最小能耗k-弱柵欄構造與移動充電調度問題。我們根據(jù)網(wǎng)絡規(guī)模對問題進行了分析，設計了MC的循環(huán)調度策略與柵欄求解方法。最后通過模擬實驗，證明了近似算法的有效性。