李騰龍

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

0 引 言

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

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

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

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

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

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

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

1.1 柵欄調(diào)度和移動(dòng)充電策略

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

為了保證柵欄的可持續(xù)運(yùn)行，我們?cè)诒O(jiān)控區(qū)域中構(gòu)建k+1條弱柵欄以保證網(wǎng)絡(luò)的k-弱柵欄覆蓋，同時(shí)MC為另一條柵欄進(jìn)行充電。

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

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

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

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

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

圖1 充電車移動(dòng)路徑

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

同時(shí)，MC必須能夠在一個(gè)時(shí)間片段內(nèi)完成充電任務(wù)，即MC在一條柵欄中的移動(dòng)時(shí)間和充電時(shí)間必須小于等于τ：

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

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

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

圖2 當(dāng)0<(L-rmin)mod(2rmin)≤rmin，充電車最長(zhǎng)移動(dòng)距離

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

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

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

圖4 充電車最短移動(dòng)距離

于是，我們得到弱柵欄的長(zhǎng)度范圍：

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

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

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

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

2 最小能耗k-弱柵欄構(gòu)造與移動(dòng)充電調(diào)度算法

2.1 算法步驟

2.1.1 構(gòu)建基礎(chǔ)柵欄圖

我們把lslot設(shè)置為左邊界，把rslot設(shè)置為右邊界。

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

（2）對(duì)于任意兩個(gè)傳感器節(jié)點(diǎn)si和sj，如果si和sj的感知區(qū)域在垂直方向上相互重疊，即|xixj|<(ri+rj)。那么，我們?cè)黾右粭l從si到sj的邊，即(si,sj)∈E；相應(yīng)的邊流量為1，即cap(si,sj)=1。

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

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

圖5 基本柵欄構(gòu)造圖

2.1.2 分割點(diǎn)為邊

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

圖6 分割點(diǎn)的方法

圖7 無向圖中分割點(diǎn)的方法

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

圖8 柵欄覆蓋圖

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

2.1.3 權(quán)重分配

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

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

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

2.1.4 最小費(fèi)用最大流算法

引理1:柵欄圖中最大流對(duì)應(yīng)的傳感器節(jié)點(diǎn)可以構(gòu)造k+1柵欄。

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

定理1：柵欄覆蓋圖的最小費(fèi)用為EAVE。

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

2.2 算法近似度分析

假定MC對(duì)單條柵欄進(jìn)行充電時(shí)的最大移動(dòng)路徑長(zhǎng)度為：

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

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

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

本章利用C++設(shè)計(jì)了模擬實(shí)驗(yàn)，并設(shè)計(jì)了一個(gè)貪心算法與我們的近似算法進(jìn)行比較。貪心算法首先采用最小費(fèi)用最大流求出k+1條柵欄，接著采用和近似算法相同的充電調(diào)度策略。

我們?cè)谝粋€(gè)矩形區(qū)域內(nèi)隨機(jī)拋灑了200個(gè)傳感器節(jié)點(diǎn)，區(qū)域?qū)挾葹?0 m，長(zhǎng)度從100 m一直增加到300 m。同時(shí)設(shè)置傳感器的初始電量為E=1 000 J，傳感器si單位時(shí)間能耗為傳感器節(jié)點(diǎn)的感知半徑在19～23 m之間隨機(jī)分布。MC電量滿足一條柵欄的能耗需求，移動(dòng)速率為5 m/s，移動(dòng)能耗為100 J/m，充電輸出功率為5 J/s，能量轉(zhuǎn)化率為0.976 5。

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

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

如圖10所示，我們?cè)诓煌瑐鞲衅鞲兄霃较略O(shè)置的節(jié)點(diǎn)數(shù)目是相同的，當(dāng)半徑較小時(shí)，構(gòu)成相同長(zhǎng)度的柵欄所需要的傳感器數(shù)目越多，近似算法的能量節(jié)約百分比也越大。近似算法在構(gòu)造柵欄時(shí)同時(shí)考慮了節(jié)點(diǎn)能耗和充電車移動(dòng)能耗，所以當(dāng)網(wǎng)絡(luò)規(guī)模越大，傳感器數(shù)目較多時(shí)，近似算法的優(yōu)化空間越大，能耗節(jié)約率自然越高。

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

4 結(jié) 語

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