方 凱，吳武豪，陳 瓊

（中電?？导瘓F有限公司，浙江 杭州 310012）

0 引言

無線傳感器網(wǎng)絡柵欄覆蓋的主要作用是監(jiān)測是否有監(jiān)測目標發(fā)生入侵，如在軍事方面，將柵欄部署在陣地前沿能有效監(jiān)測敵人是否發(fā)動突襲；在環(huán)保方面，將柵欄部署在工廠周圍能監(jiān)測污染物擴散情況；在林業(yè)方面，將柵欄部署在保護區(qū)邊界可有效監(jiān)測火災的蔓延等[1]。

目前在 WSN（Wireless Sensor Network）柵欄覆蓋領域已取得豐厚的研究成果，如在柵欄構建方面Saipulla（2013）等人提出一種基于線性部署的柵欄構建方法，沿目標路徑部署傳感器節(jié)點，從而提高了柵欄覆蓋的數(shù)量[2]。毛科技（2015）等人對傳統(tǒng)的蟻群算法進行改進使之適用于WSN柵欄構建問題，在部署區(qū)域內(nèi)搜索存在的柵欄[3]。Wang Z（2017）等人考慮到利用WSN定位方法或GPS模塊獲得的節(jié)點位置信息存在誤差，提出一種位置容忍的柵欄構建方法，從而有效的解決節(jié)點位置不準確而導致柵欄構建不完整的問題[4]。Nguyen T G（2018）等人提出一種分布式的柵欄構建算法，利用網(wǎng)絡區(qū)域聚類技術減少節(jié)點間信息交換，通過移動少量可移動節(jié)點完成柵欄構建[5]。為延長柵欄的生存時間，柵欄調度算法被學者研究，如Kumar S（2017）等人提出了一種K-柵欄最佳調度算法，充分利用了傳感器節(jié)點的能耗，大幅延長了柵欄的生存時間[6]。Xu B（2016）等人通過構建入侵軌跡模型，預測柵欄中被頻繁攻擊的位置，并調度可移動節(jié)點強化這些位置，從而延長了柵欄的生存時間[7]。在柵欄修復方面的研究，如Deng（2013）等人提出了一種混合傳感器網(wǎng)絡柵欄間隙修復方法，通過調整傳感器節(jié)點的感知半徑，使可移動節(jié)點修復間隙的移動距離最短[8]。Chen J（2017）等人提出一種利用柵欄段旋轉方法修復柵欄間隙[9]。Xu H（2016）等人提出最小費用方案和自適應貪婪移動方案修復柵欄間隙[10]。

上述柵欄構建和柵欄修復方面的研究都取得了較好的成果，但這些方法對靜態(tài)節(jié)點的利用率不高，而對可移動節(jié)點的需求較大?？紤]到成本以及柵欄構建、修復的代價問題，本文提出一種能耗優(yōu)先的WSN柵欄覆蓋方法，該方法充分利用靜態(tài)傳感器節(jié)點構建和修復柵欄，如靜態(tài)傳感器節(jié)點不能完成柵欄構建或修復工作，再派遣少量的可移動節(jié)點，并且使可移動節(jié)點的移動距離最短，從而實現(xiàn)代價最小化。

1 相關模型

假設柵欄覆蓋的應用場景為理想場景，在節(jié)點部署區(qū)域中沒有障礙物的干擾，可移動節(jié)點都是沿直線移動，且傳感器節(jié)點采用電池供電，能耗有限。

在研究中傳感器節(jié)點采用二元感知模型，以傳感器節(jié)點為圓心，感知半徑為r，當監(jiān)測目標在節(jié)點感知范圍內(nèi)，則被節(jié)點感知的概率為1，否則為0，如公式1所示。

公式1中o表述傳感器節(jié)點位置，t表示監(jiān)測目標位置，d（o，t）表示監(jiān)測目標距離傳感器節(jié)點的歐氏距離，Po，t表示監(jiān)測目標在位置t處被節(jié)點o感知的概率。

柵欄覆蓋可分為強柵欄覆蓋和弱柵欄覆蓋，本文研究強柵欄覆蓋，傳感器節(jié)點部署在帶狀區(qū)域中，監(jiān)測目標沿任意路徑從帶狀區(qū)域的一側穿越到另一側至少能被一個傳感器節(jié)點感知，強柵欄覆蓋模型如圖1所示。

圖1 強柵欄覆蓋圖

在柵欄構建階段，主要能量消耗發(fā)生在可移動節(jié)點移動過程中，而在感知方面的能量消耗較少。參考文獻[11～12]研究了可移動節(jié)點移動能耗模型，由于節(jié)點在移動過程中消耗的能量遠遠高于感知所消耗的能量，且本文的衡量指標是節(jié)點移動所消耗的能量，因此節(jié)點感知的能耗忽略不計，移動1m消耗能量為3.6J。

2 柵欄構建方法

2.1 拓撲圖建立

靜態(tài)傳感器節(jié)點和可移動傳感器節(jié)點按一定比例隨機部署在帶狀區(qū)域中，且節(jié)點位置可通過WSN定位方法或GPS模塊得到，在構建柵欄過程中為充分利用靜態(tài)傳感器節(jié)點，盡可能降低可移動節(jié)點的需求量，采用靜態(tài)傳感器節(jié)點構建全連接拓撲圖，如圖2a）所示，圖中S為部署區(qū)域最左端節(jié)點，E 為部署區(qū)域最右端節(jié)點，di，j為節(jié)點 ni和 nj之間的歐氏距離。

在拓撲圖中從節(jié)點S開始到節(jié)點E結束，存在一條路徑，當該路徑被靜態(tài)節(jié)點和可移動節(jié)點完全覆蓋時，則完成了柵欄的構建。為了得到柵欄構建過程中不同路徑所需要的可移動節(jié)點數(shù)量，需要將全連接拓撲圖轉化為可移動節(jié)點需求圖，如圖2b）所示。

圖2 拓撲圖轉換過程圖

圖 2b）中 Mni，j表示節(jié)點 ni和節(jié)點 nj之間的邊被節(jié)點感知區(qū)域完全覆蓋所需要的最少可移動節(jié)點數(shù)量，如公式2所示。

式中：di,j——節(jié)點ni和nj之間的歐氏距離；

r——感知半徑。

2.2 最優(yōu)柵欄構建路徑

圖2b）構建了部署區(qū)域內(nèi)可移動節(jié)點需求圖，倘若存在一條路徑從節(jié)點S開始，到節(jié)點E結束，移動少量的可移動節(jié)點到該路徑上某些位置即可完成路徑的全覆蓋，則該路徑被稱為柵欄構建路徑。若構建柵欄過程中移動節(jié)點的移動距離總和最短，則該路徑為最佳柵欄構建路徑。

如果能夠在拓撲圖中尋找到最佳柵欄構建路徑，則構建柵欄的能耗會最低。影響柵欄構建能耗的因素有2個：①柵欄構建過程中需要移動的傳感器節(jié)點數(shù)量；②可移動節(jié)點的平均移動距離。由于傳感器節(jié)點隨機部署在區(qū)域中，因此并不能計算出哪條柵欄構建路徑構建柵欄的移動節(jié)點移動距離之和最短，但可以首先從因素①考慮，利用KSP[13～14]算法選擇需要可移動節(jié)點數(shù)量最少的前K條路徑，當K取值合適時，最佳柵欄構建路徑被包含在其中。如圖3所示，圖中利用KSP算法計算得到需要可移動節(jié)點數(shù)量最少的前3條柵欄構建路徑Path1、Path2、Path3，將可移動節(jié)點移動到待修復位置即可完成柵欄構建，其中Path1需要4個可移動節(jié)點、Path2需要5個可移動節(jié)點，Path3需要4個可移動節(jié)點。

圖3 柵欄構建路徑圖

當確定K條柵欄構建路徑后，采用匈牙利算法虛擬派遣可移動節(jié)點到待修復位，并計算沿每條構建路徑完成構建柵欄可移動節(jié)點移動距離之和。匈牙利算法是一種最優(yōu)指派方法[15][16]，假設指派a個工人完成a個任務，每個工人可以做多種工作，但是對每種工作的收費不同，利用匈牙利算法分配工作能使完成所有工作花費的代價最小。同樣的利用匈牙利算法派遣可移動節(jié)點完成柵欄構建能夠實現(xiàn)最優(yōu)派遣，保證可移動節(jié)點的移動距離總和最短。本文對匈牙利算法進行改進使之適用于柵欄覆蓋問題。傳統(tǒng)的匈牙利算法需要a個人去完成a個任務，而在柵欄覆蓋問題上，派遣m個可移動節(jié)點去修復n個待修復位置，而m與n可能并不相同，如果m＞n，則虛擬出m-n個待修復位，可移動節(jié)點到虛擬待修復位的距離都為0；如果m＜n，則不能完成柵欄構建。如圖4所示，圖中總共有m1、m2、m3二個可移動節(jié)點，兩個修復位置1和2，因此需要虛擬出一個修復位置o，根據(jù)上述規(guī)則建立匈牙利算法的代價矩陣，如公式3所示。

圖4 匈牙利派遣圖

公式3中di，j表示傳感器節(jié)點距離待修復位的歐氏距離 （di，j≤R，R為可移動節(jié)點的最大移動距離），其中 di，o=0，表示節(jié)點距離虛擬修復位 o的距離都為0。

建立匈牙利算法的代價矩陣后即可計算出沿K條柵欄構建路徑構建柵欄可移動節(jié)點的移動距離之和，假設分別完成圖3中3條柵欄構建路徑可移動節(jié)點移動的距離總和為D1、D2和D3，且D1＜D2，D1＜D3，則 Path1是最佳柵欄構建路徑，沿該路徑構建柵欄消耗的能量最低。

2.3 柵欄構建過程

2.2小節(jié)從圖2b）可移動節(jié)點需求拓撲圖中選擇了最佳柵欄構建路徑，并采用匈牙利算法得到可移動節(jié)點最優(yōu)派遣方式，因此本節(jié)根據(jù)派遣方案將可移動節(jié)點移動到最佳柵欄構建路徑的修復位置完成柵欄構建，如圖5所示。圖中可移動傳感器節(jié)點 m1、m2、m3、m4被派遣到最佳柵欄構建路徑上，完成柵欄的構建，且能夠保證構建柵欄時可移動節(jié)點的移動距離之和最短。

圖5 柵欄構建圖

3 柵欄間隙修復

柵欄運行一段時間后，由于傳感器節(jié)點能量耗盡或故障等原因導致柵欄出現(xiàn)間隙，監(jiān)測目標可通過間隙穿越柵欄而不被檢測到，因此需要對柵欄間隙進行修復。修復方法與上述柵欄構建方法類似，首先定位到柵欄間隙的左右端，判斷柵欄中相鄰傳感器節(jié)點的感知區(qū)域是否相互重疊。如果不重疊，則判斷該處出現(xiàn)間隙，然后繼續(xù)尋找柵欄間隙的另一側，如圖6中柵欄出現(xiàn)了間隙，間隙最左側為L傳感器節(jié)點，最右側為R節(jié)點。定位到柵欄間隙后，以L節(jié)點為起始節(jié)點，R節(jié)點為結束點構建靜態(tài)節(jié)點全連接拓撲圖，然后將全連接拓撲圖轉化為可移動節(jié)點需求拓撲圖，最后利用匈牙利算法派遣可移動節(jié)點完成柵欄的修復工作。

圖6 柵欄間隙圖

4 仿真實驗

采用i5處理器、8G內(nèi)存的PC機，利用Matlab平臺進行仿真實驗。將靜態(tài)傳感器節(jié)點和可移動傳感器節(jié)點按照一定比例混合，隨機均勻部署在一個長為1000m，寬為200m的帶狀區(qū)域中，靜態(tài)節(jié)點和可移動節(jié)點的感知半徑r=50m，根據(jù)提出的方法構建柵欄如圖7所示。實驗分析了本文提出的方法的相關性能，并在柵欄構建方面與任勇默（2017）[17]等提出的FCOIS方法進行對比，在柵欄修復方面與 Saipulla A（2013）[18]等提出的 Optimal方法、貪婪算法（Greedy）進行對比。

圖7 柵欄構建結果圖

4.1 柵欄構建

部署區(qū)域確定的情況下，影響柵欄構建的因素主要包括傳感器節(jié)點數(shù)量、可移動節(jié)點與靜態(tài)節(jié)點的比例、傳感器節(jié)點的感知半徑r。評價柵欄構建方法的指標為可移動節(jié)點的能耗、柵欄構建率。實驗結果如圖8和圖9所示，實驗中可移動節(jié)點和靜態(tài)節(jié)點各占50%，可移動節(jié)點最大移動距離R=200m。

實驗結果表明，隨著帶狀區(qū)域內(nèi)傳感器節(jié)點數(shù)量增加，構建柵欄時消耗的能量逐漸降低。因為部署傳感器節(jié)點數(shù)量增加，節(jié)點密度提高，構建柵欄時可移動節(jié)點需要移動的距離更短，因此能耗逐漸減低，且本文提出的方法在構建柵欄時的能耗遠低于FCOIS方法。因為本文的方法首先利用靜態(tài)傳感器節(jié)點構建柵欄，當靜態(tài)傳感器節(jié)點不能完成柵欄構建時，才移動少量的可移動節(jié)點完成柵欄構建；而FCOIS方法完全采用可移動節(jié)點構建柵欄，因此需要移動的節(jié)點數(shù)量遠多于本文方法。在傳感器節(jié)點數(shù)量為50個時，節(jié)約了971.6J能量，在傳感器節(jié)點為150個時，節(jié)約了426.5J能量。

圖8 柵欄構建能耗圖

在柵欄構建成功率方面，部署傳感器節(jié)點數(shù)量相同時，F(xiàn)COIS算法的成功率高于本文方法。因為FCOIS完全采用可移動節(jié)點構建柵欄，因此節(jié)點具有較高的靈活性，能夠自由移動到任何指定位置完成柵欄的構建；而本文方法構建柵欄大部分采用靜態(tài)傳感器節(jié)點，倘若靜態(tài)傳感器節(jié)點部署位置比較集中，則可移動節(jié)點即使能夠移動較遠距離也不能完成柵欄構建。當傳感器節(jié)點數(shù)量為90個時，F(xiàn)COIS方法的柵欄構建成功率達到100%，當傳感器節(jié)點數(shù)量為130個時（在部署區(qū)域內(nèi)部署130個傳感器節(jié)點密度合適），本文方法的柵欄構建成功率達到100%。

圖9 柵欄覆蓋率圖

綜上實驗結果，本文提出的方法在柵欄構建方面，能夠節(jié)約大量的能耗，且當帶狀區(qū)域內(nèi)部署的傳感器節(jié)點達到一定數(shù)量時，具有100%的柵欄構建成功率。

4.2 柵欄修復

Saipulla A （2013）[18]提出的 Optimal柵欄間隙修復方法首先定位到間隙所在位置，然后計算需要的可移動節(jié)點數(shù)量，最后采用二分法派遣可移動節(jié)點完成柵欄修復使得可移動節(jié)點移動距離之和最短。貪婪算法派遣最近的可移動傳感器節(jié)點修復柵欄。而本文提出的柵欄間隙修復方法首先尋找可以使用的靜態(tài)傳感器節(jié)點，當靜態(tài)傳感器節(jié)點不能完成柵欄修復時，派遣可移動節(jié)點修復柵欄。在帶狀區(qū)域中部署100個傳感器節(jié)點，可移動節(jié)點占30%，靜態(tài)節(jié)點各占70%，可移動節(jié)點最大移動距離R=200m，實驗結果如圖10和圖11所示。

由圖10可以看出，在柵欄間隙修復方面，隨著柵欄間隙長度的增加，二種柵欄修復方法修復柵欄的能耗呈梯度升高。因為柵欄間隙為50m和100m時需要的可移動節(jié)點數(shù)量相同，250m和300m需要的移動節(jié)點數(shù)量相同，因此消耗的能耗呈梯度提高。且本文的方法的能耗低于Optimal方法和Greedy方法，因為首先考慮使用靜態(tài)節(jié)點修復柵欄間隙，當靜態(tài)節(jié)點不能完成修復時，再派遣可移動節(jié)點，因此需要調度的可移動節(jié)點數(shù)量相對其他兩種方法較少，因此節(jié)點移動的總距離更短，消耗的能量更低。Optimal方法的能耗低于Greedy方法，因為Optimal方法使用二分搜索方法，能夠使派遣的可移動節(jié)點最優(yōu) （總移動距離最短），而Greedy方法每次都派遣距離待修復位置最近的可移動節(jié)點完成柵欄修復，會陷入局部最優(yōu)問題，因此Greedy方法修復柵欄間隙的能耗高于Optimal方法。

圖10 柵欄修復能耗圖

在柵欄修復率方面的實驗如圖11所示。實驗結果表明隨著柵欄間隙長度的增加，柵欄修復成功率會逐漸降低。因為柵欄間隙長度增加，需要的可移動節(jié)點數(shù)量增加，但可移動節(jié)點存在最大可移動距離R，故修復率逐漸降低。本文方法的柵欄修復成功率最高，在柵欄間隙長度為350m時，比Optimal方法提高了8%左右，比Greedy方法提高了12.6%左右，Optimal方法的修復成功率高于Greedy方法。

圖11 柵欄修復率圖

5 結語

本文研究了一種低能耗的WSN柵欄覆蓋方法，通過構建靜態(tài)節(jié)點拓撲圖，利用KSP算法和匈牙利算法構建柵欄使得可移動節(jié)點移動距離之和最小，即柵欄構建的能耗最小。然后提出了柵欄間隙修復方法，同樣利用前述算法支配可移動節(jié)點修復間隙，實驗結果表明該方法在柵欄覆蓋方面具有較好的性能。后續(xù)工作將進一步研究能耗最低的K-柵欄覆蓋方法。