方 凱，吳武豪，陳 瓊

（中電?？导瘓F(tuán)有限公司，浙江 杭州 310012）

0 引言

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

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

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

1 相關(guān)模型

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

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

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

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

圖1 強(qiáng)柵欄覆蓋圖

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

2 柵欄構(gòu)建方法

2.1 拓?fù)鋱D建立

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

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

圖2 拓?fù)鋱D轉(zhuǎn)換過程圖

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

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

r——感知半徑。

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

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

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

圖3 柵欄構(gòu)建路徑圖

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

圖4 匈牙利派遣圖

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

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

2.3 柵欄構(gòu)建過程

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

圖5 柵欄構(gòu)建圖

3 柵欄間隙修復(fù)

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

圖6 柵欄間隙圖

4 仿真實驗

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

圖7 柵欄構(gòu)建結(jié)果圖

4.1 柵欄構(gòu)建

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

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

圖8 柵欄構(gòu)建能耗圖

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

圖9 柵欄覆蓋率圖

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

4.2 柵欄修復(fù)

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

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

圖10 柵欄修復(fù)能耗圖

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

圖11 柵欄修復(fù)率圖

5 結(jié)語

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