薛 亮，王 然

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

柵欄覆蓋在國防和林業(yè)方面有著重要作用[1]。為了增加柵欄的可靠性，文獻[2]提出了K-柵欄覆蓋的概念，要求監(jiān)測目標在穿越區(qū)域時至少能被K個傳感器節(jié)點所感知。

目前大部分研究主要集中在使用靜態(tài)傳感器構建K-柵欄覆蓋方面[3-5]。然而，靜態(tài)傳感器并不能覆蓋到區(qū)域中某些特定的位置，從而導致覆蓋漏洞出現(xiàn)，影響覆蓋的質量。因此，使用移動傳感器構建柵欄的研究受到了越來越多的關注。文獻[6]使用移動傳感器構建1-柵欄覆蓋。文獻[7～10]利用移動傳感器構造節(jié)能的K-柵欄覆蓋問題，并著重于減少傳感器移動的距離。

上述研究都是試圖通過減少傳感器能耗的方式來實現(xiàn)延長網絡壽命的目標。近年來，能量收集技術成為了一種新的可供選擇的方案。傳感器配備能量收集模塊[11]，可收集環(huán)境中的能量(例如太陽能[12]、風能[13]等)來給電池補充能量。文獻[14]將能量收集技術與K-柵欄覆蓋相結合，最大化網絡的壽命，但該研究僅考慮了傳感器的靜態(tài)場景。文獻[15]使用具備能量收集能力的移動傳感器和不具備能量收集能力的靜態(tài)傳感器共同構建柵欄覆蓋。然而上述研究都沒有考慮到區(qū)域內不同位置能量的差異性，例如部署在森林里的傳感器由于存在樹葉遮擋，導致各個位置接收到的太陽能強度存在差異。

基于能量收集技術，本研究認為傳感器能夠收集太陽能，且監(jiān)測區(qū)域內不同位置的太陽能強度不一致。本文使用移動傳感器構建K-柵欄覆蓋，提出了一種集中式的柵欄構建和調度(Barrier Construction And Scheduling，BCAS)算法，有效地構建并調度柵欄，最大程度地延長了網絡壽命。

1 相關模型

1.1 網絡模型

圖1 網絡示意圖Figure 1. Network diagram

1.2 傳感器模型

傳感器的監(jiān)測半徑為R，使用ZigBee技術直接與基站通信，并且具有移動和能量收集能力。電池容量為B，即傳感器的初始能量。傳感器有兩種狀態(tài)：活動狀態(tài)和睡眠狀態(tài)。傳感器在活動狀態(tài)下執(zhí)行監(jiān)測任務需要消耗能量，在睡眠狀態(tài)下不執(zhí)行任務，不需要消耗能量。假設傳感器電池容量存在一個閾值百分比ε，當傳感器的剩余能量小于Bε時，睡眠狀態(tài)的傳感器不能被激活，活動狀態(tài)的傳感器在監(jiān)測任務執(zhí)行完畢后立即睡眠。不考慮傳感器移動的時間，即傳感器的位置變化是瞬時完成的，因此可以認為傳感器在移動時是不能收集能量的。

1.3 能耗模型

傳感器需要不斷監(jiān)測目標區(qū)域以檢測入侵者，并且還需要與基站通信，將數(shù)據傳輸?shù)交静⒔邮栈镜恼{度信息，因此需要考慮傳感器的監(jiān)測能耗率與通信能耗率。本文將監(jiān)測能耗率和通信能耗率看作一個定值，稱為傳感能耗率，記為es(單位為J·s-1)。此外，還需要考慮傳感器的移動能耗，將傳感器每米移動的能耗記為em(單位為J·m-1)。

1.4 能量收集模型

區(qū)域Ω內不同太陽能區(qū)域中的太陽能強度隨機分布在[a，b](單位為W)之間。本文用λu代表第u個太陽能區(qū)域內的太陽能強度，用ξ代表太陽能的接收效率。因此第u個太陽能區(qū)域內傳感器si的能量收集率計算式為

ei(u)=ξλu

(1)

由于在現(xiàn)實中光照強度都是隨時間變化的，文獻[17～19]中采用取平均值的方式來表示光照強度，因此本文也采用這種方式。

1.5 時隙劃分

將網絡的運行時間離散化為小時隙，每個時隙的長度相等，表示為τt(t=1，2，…，T)，其中T為最后一個時隙。第t個時隙開始時傳感器si的剩余能量Eit為

(2)

(3)

(4)

其中，t=1，2，…，T；Ei0=B，為傳感器si的初始能量；τt-1代表第t-1個時隙的長度；τ0=0；ei(ut-1)代表在第t-1個時隙位于ut-1號太陽能區(qū)域中傳感器si的能量收集率；es代表傳感器傳感的能耗率；lit代表傳感器si在時隙t開始前移動的距離；em代表傳感器每米移動的能耗；xit和yit為傳感器si在第t個時隙在區(qū)域內Ω位置的橫縱坐標值。

在每個時隙開始前，柵欄中傳感器剩余能量不得低于Bε才能確保節(jié)點能被激活；在時隙結束時，剩余能量必須大于0，才能確保節(jié)點在時隙內不會死去。考慮最極端的情況，時隙開始時剩余能量正好為Bε，時隙結束時剩余能量正好為0，因此時隙的長度τt可以計算為

(5)

其中，a為監(jiān)測區(qū)域Ω內最小的太陽能強度值；ξ代表太陽能的接收效率。

傳感器的移動距離限制如式(6)所示。

(6)

2 問題定義

定義1移動K-柵欄網絡的生命周期：給定監(jiān)測區(qū)域Ω和移動傳感器集合S，從形成K-柵欄覆蓋開始到無法調度移動傳感器為形成K-柵欄覆蓋的時間段，即移動K-柵欄網絡的生命周期。

定義2移動K-柵欄網絡的生命周期最大化問題：給定監(jiān)測區(qū)域Ω和移動傳感器集合S，調度傳感器移動形成K-柵欄，并按時隙調度，使K-柵欄的網絡生命周期最大。

基于以上定義可以將問題形式化

(7)

約束于

(8)

(9)

si∈Ba，?t=1，2，…，T

(10)

式(7)是優(yōu)化目標，表示最大化K-柵欄的生命周期。式(8)表示時隙開始前傳感器的剩余能量必須大于等于閾值能量。式(9)表示時隙結束后傳感器的剩余能量必須大于0。式(10)中Ba表示構成柵欄的傳感器節(jié)點集合。上述約束作用于柵欄中的每個傳感器和每個時隙。

3 算法設計

監(jiān)測區(qū)域Ω內的太陽能強度是連續(xù)分布的，但這并不利于處理，因此需要使用離散化的思想，用邊長為2R的小網格離散化區(qū)域Ω。傳感器可以移動至網格的中心。傳感器的能量收集率為該網格中心處的太陽能強度乘以太陽能接收效率。

本文提出的柵欄構建與調度算法主要分為構建階段與調度階段。在構建階段構建出滿足柵欄覆蓋要求的柵欄個數(shù)，在調度階段選擇柵欄調度并進行節(jié)點移動以修補柵欄，延長網絡的壽命。

3.1 構建階段

定義3基線柵欄位置：能為區(qū)域提供1-柵欄覆蓋的網格位置。

圖2 監(jiān)測區(qū)域的劃分Figure 2. Division of monitoring area

算法1 基線柵欄位置選擇算法Input: 太陽能強度λu,區(qū)域Ω,監(jiān)測半徑R,傳感器集合SOutput: 區(qū)域Ω的基線柵欄位置bp1. 用邊長2R的小正方形離散化區(qū)域Ω,得到水平子區(qū)域集合AH2. count=03. for AHz∈AH do:4. 選擇最高平均太陽能強度的一行網格為基線柵欄位置bpz,如果存在多行滿足條件的網格則計算AHz內傳感器縱坐標平均值,選擇縱坐標值離該平均值最近那行網格作為基線柵欄位置bpz。5. if count>0 do:6. 選擇平均太陽能強度較大的一列網格位置使AHz-1中bpz-1與AHz中bpz相連,形成Ω中完整的基線柵欄位置bp7. end if8. count++9. end for

下一步需要將各個水平子區(qū)域內的基線柵欄位置連接，形成整個監(jiān)測區(qū)域Ω內完整的基線柵欄位置。對于相鄰的水平子區(qū)域AHz和AHz+1內的子基線柵欄位置bpz和bpz+1有兩種方式可以連接。如圖3所示，分別選擇AHz中的網格sg1、sg2、sg3和AHz+1中的網格sg4、sg5、sg6。選擇的標準為用于連接兩個子基線柵欄位置的網格的平均太陽能強度最大。假設sg1、sg2、sg3處的平均太陽能強度大于sg4、sg5、sg6處的平均太陽能強度，此時會選擇AHz中的網格sg1、sg2、sg3用于連接。對每個水平子區(qū)域都執(zhí)行上述過程，直至形成整個監(jiān)測區(qū)域內完整的基線柵欄位置。具體過程見算法1。

圖3 連接位置的選擇Figure 3. Choice of connection location

接下來考慮為區(qū)域Ω構建K-柵欄覆蓋，考慮柵欄運行在能量收集的情況下，并且區(qū)域內的傳感器有一定的冗余。因此可以在Ω內形成K+1條柵欄，在每個時隙開始前選擇其中的K條激活，剩下的一條保持睡眠以補充能量。被選擇激活的柵欄中每個傳感器的能量不低于Bε，因此需要找出K+1個基線柵欄位置。

將監(jiān)測區(qū)域Ω在豎直方向上平均分成K+1個豎直子區(qū)域。分別在每個豎直子區(qū)域AVz內執(zhí)行算法1找到對應的基線柵欄位置bp。然后，調度豎直子區(qū)域AVz內傳感器，將其移動到基線柵欄位置bp處形成柵欄。傳感器的移動不能跨越區(qū)域，構成柵欄的傳感器集合為baz。本文采用貪心思想調度傳感器移動。對于基線柵欄位置bp上的每個網格sgu，遍歷豎直子區(qū)域AVz內的傳感器集合Sz，找到與sgu中心距離最短的傳感器sbest，將其移動至sgu處，并更新sbest的剩余能量。具體步驟見算法2。

算法2 K+1柵欄構建算法Input: 太陽能強度λu,區(qū)域Ω,監(jiān)測半徑R,傳感器集合S,柵欄數(shù)KOutput: 區(qū)域Ω內的柵欄集合Ba1. 將區(qū)域Ω劃分為K+1個豎直子區(qū)域,得到豎直子區(qū)域集合AV2. 對AVz∈AV執(zhí)行算法1, 得到基線柵欄位置集合Bp3. for all bp∈Bp do:4. for grid sgu in bp do:5. for si∈Sz do:6. 計算len(si, sgu) 7. if len(si, sgu)

3.2 網絡規(guī)模分析

區(qū)域Ω中能夠形成的柵欄數(shù)是有限制的，與區(qū)域中傳感器的節(jié)點密度有關，下面給出關于節(jié)點密度的定義。

定義4節(jié)點密度：監(jiān)測區(qū)域Ω內傳感器的數(shù)量與區(qū)域Ω面積的比值。

監(jiān)測區(qū)域Ω內的節(jié)點密度ρ可以表示為

(11)

將監(jiān)測區(qū)域劃分為K+1個豎直子區(qū)域，每個豎直子區(qū)域AVz內的節(jié)點數(shù)量為NA。

圖4 構成柵欄所需的最少傳感器Figure 4. Minimal sensors required to form a barrier

(12)

每個豎直子區(qū)域AVz內形成柵欄覆蓋所需的最少節(jié)點數(shù)為Nmin，如圖4所示。

(13)

要保證豎直子區(qū)域AVz內節(jié)點數(shù)大于Nmin才能形成柵欄覆蓋，因此可以推出監(jiān)測區(qū)域Ω內能夠滿足的柵欄數(shù)K的上限。

(14)

圖5 構成柵欄所需的最多傳感器Figure 5. The most sensors required to form a barrier

由于實際應用時并不會總以最小的節(jié)點數(shù)形成柵欄，因此一般情況下并不能達到上限條件。由此可知，豎直子區(qū)域AVz內形成柵欄所需的最大節(jié)點數(shù)Nmax，如圖5所示。

(15)

只要保證每個豎直子區(qū)域內的節(jié)點數(shù)NA≥Nmax就能在區(qū)域內形成柵欄覆蓋?？梢酝瞥鲆欢軡M足所需柵欄覆蓋數(shù)的節(jié)點密度ρ。

(16)

3.3 調度階段

在監(jiān)測區(qū)域Ω內生成K+1條柵欄后，需要調度算法來選擇K條柵欄激活并調度，以延長網絡的生命周期。調度算法分為兩部分：柵欄選擇策略和修補策略。柵欄選擇策略為：在每個時隙τt開始時選擇K條傳感器平均剩余能量最大的柵欄激活執(zhí)行監(jiān)測任務，剩下的傳感器進入睡眠狀態(tài)以補充能量。

在時隙τt結束后可能存在一些柵欄中傳感器的剩余能量小于Bε，要在下一個時隙τt+1開始前對柵欄進行修補，替換掉這些能量小于閾值的傳感器節(jié)點。將豎直區(qū)域AVz中傳感器集合Sz節(jié)點分為兩類：構成柵欄的節(jié)點集合baz和其他不是構成柵欄的節(jié)點Szno(baz∪Szno=Sz)。定義移動權值ω(si，sj)為

(17)

其中，Ej為傳感器sj的剩余能量；len(si，sj)為傳感器si和傳感器sj之間的距離。

修補策略為：對于豎直子區(qū)域AVz中構成柵欄的傳感器集合baz中能量小于Bε的傳感器si，遍歷Szno節(jié)點集合，選擇移動權重ω最大的節(jié)點sbest移動至節(jié)點si處進行替換以修補柵欄。更新sbest的剩余能量，對每個豎直子區(qū)域AVz都執(zhí)行一次修補策略。

在每個時隙開始前都執(zhí)行該調度算法，直至無法形成滿足區(qū)域所需的K-柵欄覆蓋要求。調度算法的具體過程見算法3。

算法3 柵欄調度算法Input: 柵欄集合Ba,柵欄數(shù)K,傳感器集合S,電池容量B,閾值ε1. for baz∈Ba do:2. for si∈baz do:3. if Eiωmaxdo:7. ωmax=ω(si, sj), sbest= sj8. end if9. end for10. 移動 sbest到si, Ebest= Ebest - em×len(si, sbest) 11. baz= baz∪{sbest}, baz= baz(?si} 12. Szno= Szno∪{si}, Szno= Szno(?sbest}13. end if14. end for 15. end for16. 選擇Ba中傳感器平均剩余能量最大的K條baz激活,其余睡眠

4 模擬實驗

為了驗證所提BCAS算法的性能，本文在IntelliJ IDEA平臺下使用Java語言進行了模擬實驗，并且與文獻[8]中提到的MobiBar算法和文獻[9] 中提到的Single Sensor 算法做了對比。為了保證實驗的穩(wěn)定性和準確性，每組實驗都進行了50次模擬。實驗區(qū)域的大小設置為400 m×150 m，太陽能區(qū)域大小為40 m×15 m，傳感器節(jié)點均勻分布在區(qū)域Ω內，傳感器的節(jié)點密度ρ為3，電池容量B為1 100 mAh×4 V，太陽能強度范圍為0.008～0.036 W，監(jiān)測半徑R為5 m，太陽能接收效率ξ為0.2。將傳感的能耗率es設置為0.03 J·s-1，傳感器移動能耗em為1 J·m-1，傳感器能量閾值百分比ε為3%，柵欄個數(shù)K為3。

本文使MobiBar算法和Single Sensor算法與BCAS算法運行于同樣的能量收集區(qū)域，并且需要形成滿足K-柵欄覆蓋要求的柵欄數(shù)。對于Single Sensor算法，將整個監(jiān)測區(qū)域分為兩塊，分別形成子柵欄并連接。本文分別從網絡生命周期和構建柵欄平均移動距離的角度比較了算法的性能。

圖6 柵欄數(shù)對生命周期的影響Figure 6. The effect of the number of barriers on lifetime

圖6表明，隨著柵欄數(shù)K的增加，BCAS算法下生命周期依次減小。這因為監(jiān)測區(qū)域內傳感器密度不變，而隨著需要滿足的柵欄數(shù)的增加，監(jiān)測區(qū)域也會被劃分成越來越多的子區(qū)域，每個子區(qū)域內的傳感器數(shù)量會越來越少，因此能夠用來修補柵欄的冗余傳感器也會減少。然而MobiBar算法和Single Sensor算法的生命周期變化較小。這因為MobiBar和Single Sensor算法沒有針對能量收集的場景進行調度優(yōu)化。在柵欄數(shù)K變化的情況下，與MobiBar算法和Single Sensor算法相比，BCAS算法的生命周期平均提升了大約183%。

圖7 節(jié)點密度對生命周期的影響Figure 7. The effect of node density on lifetime

圖7顯示，隨著節(jié)點密度ρ的增加，BCAS算法的生命周期也會增加，而MobiBar和Single Sensor算法的生命周期變化較小。這是因為隨著傳感器密度增加，用來修補柵欄的傳感器也會增加，因此生命周期得以延長，而MobiBar和Single Sensor算法并沒有充分地利用冗余節(jié)點。相比MobiBar和Single Sensor算法，在節(jié)點密度變化的情況下，BCAS算法的生命周期平均提升了168%。

圖8 柵欄數(shù)對平均移動距離的影響Figure 8. The effect of the number of barriers on average moving distance

圖8顯示出隨著柵欄數(shù)K的增加，3種算法的平均移動距離都會增加。這因為隨著柵欄數(shù)的增加，監(jiān)測區(qū)域會被劃分為越來越多的子區(qū)域，每個子區(qū)域內可供選擇移動的傳感器也變少，平均移動距離因此變大。在K=1時，MobiBar算法的平均移動距離最小，在K>1時，BCAS算法具有較好的性能，而MobiBar算法性能最差。在K變化時，與MobiBar算法和Single Sensor算法相比，BCAS算法平均移動距離減少了約20.6%和12%。

圖9 節(jié)點密度對平均移動距離的影響Figure 9. The effect of node density on average moving distance

圖9表明，隨著節(jié)點密度ρ的增加，3種算法的平均移動距離都在下降。這因為隨著傳感器密度增加，可供選擇的傳感器數(shù)量也會增加，平均移動距離因此下降。在傳感器密度變化的過程中，BCAS算法的平均移動距離少于MobiBar算法和Single Sensor算法。在密度小于0.008時，Single Sensor算法的平均移動距離要小于MobiBar算法；密度大于0.008時，則相反。隨著傳感器密度的變化，與MobiBar算法和Single Sensor算法相比，BCAS算法的平均移動距離分別減少了20.2%和14.2%。

5 結束語

本文在能量收集的移動傳感網絡中構建了K-柵欄覆蓋，提出了最大化基于能量收集的移動傳感器網絡中K-柵欄覆蓋的生命周期問題。為了解決該問題，本文使用離散化的思想，將監(jiān)測區(qū)域劃分為小網格 ，提出BCAS算法來構建和調度柵欄，并進行了模擬實驗，實驗結果證明了BCAS算法的有效性。由于本文使用的是集中式算法，需要基站集中計算，資源消耗較大，因此未來將專注于研究相應的分布式算法以降低資源消耗。