一種基于最優匹配的低能耗柵欄修復方法*

戴光麟徐瑞吉王宇翔池凱凱毛科技

(浙江工業大學計算機科學與技術學院，浙江 杭州310032)

柵欄覆蓋是無線傳感器網絡(Wireless Sensor Networks，WSN)覆蓋研究的一個重要方向[1-2]，最早由Gage 在機器人研究領域提出，其通常用于監控特定區域入侵者的入侵與否和入侵軌跡[3]。 憑借傳感器節點高效節能等優勢，柵欄覆蓋被廣泛地應用于軍事、工業、農業領域[4-5]。 柵欄構建后，特定區域集合內的相鄰傳感器節點檢測區域相互疊加，保證至少有一個節點能夠檢測到入侵者并記錄其入侵路徑，可提高網絡安全性[6-7]。 但在實際應用過程中，由于傳感器節點所處環境復雜，柵欄易出現間隙導致喪失功能，因此需要及時并高效完成柵欄修復[8-9]。

目前國內外對柵欄間隙修復的研究已取得很多成果。 文獻[4]提出了一種用于移動傳感器節點的k - 柵欄覆蓋算法(An autonomous deployment algorithm for k-barrier coverage with mobile sensors，MobiBar)，通過構建k 個不同的完整柵欄，利用有限的傳感器節點提供了最大程度的柵欄覆蓋，并利用可移動節點，使柵欄能夠自我修復和重建；文獻[10]提出了一種k 柵欄覆蓋方法，通過幾何數學模型優化節點位置，僅通過啟動睡眠的節點，即可完成柵欄間隙的修復，與采用可移動節點修復柵欄的方式相比，解決了可移動傳感器節點高能耗的問題，降低了柵欄間隙修復的總能耗。 在尋找最優修復路徑的算法上，文獻[11]引入了概率感知模型尋找最佳修復路徑，使用最大權匹配算法(Kuhn-Munkres，KM)調動移動節點完成柵欄修復；文獻[12]提出了一種基于概率感知模型的FDS-AD 算法，通過人為設定的概率閾值調動可移動傳感器節點，確定最佳修復路徑的同時，兼顧了能耗；文獻[13]則提出了一種WSN 柵欄間隙修復優化方法(An Optimization Method for WSN Barrier Gap Repair，OMBR)，利用k條最短路徑算法(Top-k-Shortest Paths，KSP)尋找所需可移動節點數量最少的可修復路徑，減少移動節點的能耗。 在降低可移動傳感器節點派遣能耗的算法中，文獻[14]提出了一種Optimal 柵欄間隙修復方法，定位到柵欄間隙位置后，通過二分法派遣可移動節點完成間隙修復，可有效縮短可移動節點的移動距離；文獻[15]通過梯度差分算法確定關鍵節點，在使用二分法派遣節點時引入決策算法進行優化，確定節點移動的最短路徑。

實際應用場景中，在構建柵欄初期，使用的節點僅占少數，大部分節點作為備用，當柵欄被破壞時才會接替運行并修復柵欄。 考慮到一般情況下可移動節點的成本往往非常高，在修復柵欄間隙時，需要充分考慮如何匹配最優的可移動節點，實現低功耗柵欄修復[16]。 將上述文獻與實際情況結合分析，本文提出了一種基于最優匹配的低能耗柵欄修復方法(Low-Power Barrier Coverage Repair Method Based on Optimal Match，BCR-OM)，該方法首先遍歷柵欄搜索柵欄間隙；然后計算完整修復柵欄間隙，所需的可移動傳感器節點的最小數量；隨后利用傳感器節點構建柵欄間隙修復路徑；最后利用Hungarian 算法得出節點的最佳派遣方案，將節點派遣至對應位置，使用較低能耗完成柵欄間隙的修復。

1 柵欄間隙搜索

1.1 相關假設與定義

假設在柵欄間隙搜索開始前，柵欄構建已完成。在特定的帶狀區域內，部署的可移動節點傳感器節點和靜態傳感器節點按照特定比例存在，且所有傳感器節點的位置已知(通過匯聚節點定位自身位置)，當傳感器節點感知到柵欄中出現間隙后，派遣可移動傳感器節點至待修復的位置，即可完成間隙修復。

如圖1 所示，圖中為一條帶狀柵欄，節點ni和節點ni＋1之間出現柵欄間隙，此時，間隙周邊存在可移動傳感器節點m，如果將節點m派遣至柵欄間隙處，即可修復柵欄。 假設傳感器節點m的最大可移動距離為D，可感知的范圍是半徑為R的圓形區域。

圖1 柵欄間隙圖

1.2 柵欄間隙搜索算法

在進行柵欄間隙修復前首先需要查找出柵欄間隙的位置。 由于柵欄中所有傳感器節點的坐標都已經獲得，且傳感器節點的感知半徑都為R，因此基于傳感器節點之間的距離和感知半徑判斷柵欄中兩個相鄰傳感器節點之間是否存在間隙，當兩相鄰節點的距離大于2 倍感知半徑，則可認為柵欄存在間隙。表1 詳細介紹了本文提出的柵欄間隙搜索方法，該算法將搜索到的柵欄間隙保存在集合Gap 中，該集合是一個n行，2 列的數組，Gap(i，1)記錄該間隙的前一個傳感器節點編號ni，Gap(i，2)用于記錄柵欄的間隙長度L。

圖2 柵欄搜索過程圖

對于節點nt，執行步驟3 ～7 具有常數復雜度。因為需要對柵欄中num 個節點依次執行步驟3 ～7，因此算法的總復雜度正比于柵欄節點數目num。 如圖2 所示，傳感器節點nt與nt＋1之間存在柵欄間隙，且為搜索到的第一個柵欄間隙，則Gap(0，1)＝t，Gap(0，2)＝d-2R。

表1 柵欄間隙搜索算法

2 柵欄間隙修復

2.1 確定可修復間隙數量

在進行柵欄修復前，首先要基于冗余的靜態節點及其位置，在充分利用靜態節點的前提下，確定所存在的間隙的位置、間隙的數量、間隙周圍的可移動節點數量是否滿足間隙修復要求。

尋找到待修復的柵欄間隙后，即可開始對柵欄間隙進行修復。 將待修復的柵欄間隙平均分段，分段數量記為mnum，如式(1)所示。

因傳感器節點覆蓋最大長度為2R，對式(1)上取整。 分段后，如圖3 所示，子間隙的中心點gi、gi＋1、gi＋2就是該段柵欄間隙的待修復位置，將可移動傳感器節點派遣至gi、gi＋1、gi＋2即可完成柵欄間隙修復，此時mnum即為最少派遣的可移動傳感器節點數。

圖3 柵欄間隙修復過程圖

修復柵欄間隙應首先考慮最大修復率，其次考慮最小化修復代價。 如圖4 所示，節點S和D之間出現柵欄間隙，以節點S為起點，節點D為終點，結合間隙周圍的冗余靜態節點構建全連接拓撲圖G＝(V，E)，V是靜態節點集合，如式(2)所示，其中nw表示靜態節點，w表示G中靜態節點數量，E是節點間構成的邊的集合，如式(3)所示，ei，j表示節點ni和nj之間的邊，sn＝w＋2。

圖4 靜態節點全連接拓撲圖

以numi，j表示節點ni和nj之間的邊被節點感知范圍完全覆蓋所需最少傳感器節點的數量，其值如式(4)所示，d(ei，j)表示節點ni和nj之間的距離，r表示節點的感知范圍，1 ≤i，j≤sn。

一旦計算完每對靜態節點間(包括S、D節點與靜態節點間)修復所需的最少移動節點數，即可確定需要可移動節點最少的一條由S到D且中間經過部分靜態節點的路徑Path，隨后即可在該路徑上確定待修復位置以及所需要的可移動節點數量。 此時Path 中所包含的靜態節點已經被選定參與到S和D之間的間隙修復。

2.2 基于Hungarian 算法的柵欄修復

選擇靜態節點參與柵欄間隙修復后，節點仍可能存在間隙，此時需要利用周圍可移動節點完成修復。 為保證間隙修復的代價最小(即可移動節點在修復過程中的移動距離和最小)， 本文利用Hungarian 算法來選擇可移動傳感器節點，從而使修復后可移動節點在修復柵欄間隙移動過程中消耗總能量降低。 Hungarian 算法是一種最優化指派算法，如指派g個人去做g個任務，每個人對不同任務的熟悉程度不同，利用Hungarian 算法可選擇最合適的人去做某一項工作，使得g個人完成g個任務所花的時間之和最短[13]。 不同的人完成不同的任務所需的時間，可以用n維方陣來刻畫，稱為代價矩陣，如式(5)所示。

式中:ai，j表示工人i完成第j項任務時所需的開銷。

Hungarian 算法對矩陣進行一系列操作，當矩陣中出現n個滿足不同行不同列的0 時，算法停止，此時即可確定哪個工人去執行哪項任務。 具體步驟如下:①每行減去此行最小數②判斷是否達到算法目標，如未達到算法目標，繼續下一步。 否則結束。③行列交替尋找沒有選中0 的行或列。 首先按行找到沒有選中0 的行(具體見步驟實例)，在找到的行后標記；隨后標記該行中有0 的列。 在已標記的列中，如果有0，繼續標記有0 的行，交替標記后，直到所有目標行列都被標記。 ④將未標記的行與已標記的列劃線，即可劃去矩陣中出現的所有0，隨后在剩余元素中尋找最小的值min。 ⑤將步驟④中劃線的行減去min(若元素為0，變成-min)，然后將劃線的列加上min(另矩陣元素全部大于等于0)。 返回步驟②。

利用Hungarian 算法分析節點派遣問題。 當修復位置總數z大于可移動節點總數t時，無法完成間隙的修復，此情況不在本文的考慮范圍內。 當修復位置總數z小于等于可移動節點總數t時，通過派遣t個可移動傳感器節點至z個待修復位置實現柵欄間隙修復，此時每個待修復位置接受一個可移動傳感器節點，剩余t-z個節點無需移動。 在修復路徑上虛擬出t-z個虛擬修復位置，使t個可移動節點被派遣到t個修復位置，具體方法如圖5 所示，共分為兩種情況:修復位置總數等于可移動節點總數；修復位置總數小于可移動節點總數。

圖5 間隙修復過程情況圖

圖5(a)間隙修復路徑中存在2 個待修復位置，可移動的傳感器節點數分別為mn1和mn2，節點mn1可以移動到位置a，移動距離為d1，但無法移動到位置b(因為其余位置b的距離大于最大可移動距離D)，因此定義可移動傳感器節點mn1與待修復位置b的距離為＋∞；節點mn2與位置a和位置b的距離均小于D，因此能夠移動到位置a與位置b，且移動距離為d2與d3，利用可移動傳感器節點與待修復位置的距離作為修復柵欄間隙的代價，構建Hungarian 算法的代價矩陣，如式(6)所示。

圖5(b)間隙修復路徑中存在2 個待修復位置，而可移動節點有3 個，分別為mn1、mn2和mn3，此時需要虛擬一個待修復位置，如圖中虛擬位置O所示。 假設所有可移動傳感器節點與虛擬待修復位置O的距離都為0，當可移動傳感器節點與待修復位置的距離大于節點的最大移動距離D時，則定義該節點與待修復位置的距離為＋∞。 構建的Hungarian算法代價矩陣如式(7)所示。

3 仿真實驗及分析

本實驗采用MATLAB 進行仿真測試，MATLAB軟件運行在i5-9400F 處理器、16G 內存的PC 機上。實驗開始前，將靜態傳感器節點和可移動傳感器節點按照特定比例混合，隨機均勻地放置在一個長為1 000 m，寬為200 m 的帶狀區域中，實驗中的傳感器節點感知范圍為半徑R＝50 m 的圓形，構建的柵欄如圖6 所示。 實驗分析了本文提出的BCR-OM方法的相關性能，在柵欄修復方面與文獻[14]提出的Optimal 方法、貪婪算法(Greedy)進行對比。 在柵欄構建階段，主要能量消耗發生在可移動節點移動過程中，而在感知方面的能量消耗較少，因此傳感器節點感知的能耗忽略不計(節點移動能耗遠高于感知能耗)。 移動1 m 消耗能量為3.6 J。

圖6 間隙修復結果圖

3.1 柵欄間隙修復實驗

文獻[14]提出的Optimal 柵欄間隙修復方法首先定位到間隙所在位置，然后計算需要的可移動節點數量，最后派遣可移動的傳感器節點移動至對應的待修復區域完成柵欄間隙修復。 在派遣過程中，它使用二分法優化減少節點的移動距離，同時使用Greedy 算法派遣最近的可移動傳感器節點修復柵欄間隙。 而本文提出的BCR-OM 柵欄間隙修復方法首先尋找可以使用的靜態傳感器節點，當靜態傳感器節點不能完成柵欄修復時，派遣可移動節點修復柵欄。 在帶狀區域中部署100 個傳感器節點，可移動節點占30%，靜態節點占70%，可移動節點最大移動距離R ＝200 m。 由于傳感器節點的感知能耗較小，相對于可移動傳感器移動位置產生的能耗可忽略不計，柵欄修復能耗主要來自于可移動傳感器節點的移動產生的能耗，因此本實驗調整間隙的長度來模擬不同環境，通過對比修復間隙所需能耗來對比算法效率。 實驗結果如圖7 所示。

圖7 柵欄修復能耗圖

在柵欄間隙修復方面，隨著柵欄間隙長度的增加，三種柵欄修復方法修復柵欄的能耗呈梯度升高，因為柵欄間隙為50 m 和100 m 時需要的可移動節點數量相同，250 m 和300 m 需要的移動節點數量相同，因此消耗的能耗呈梯度提高。 且BCR-OM 方法的能耗低于Optimal 方法和Greedy 方法，因為BCR-OM 首先考慮使用靜態節點修復柵欄間隙，當靜態節點不能完成修復時，再派遣可移動節點，因此需要調度的可移動節點數量相對其他兩種方法較少，節點移動的總距離更短，消耗的能量更低。

考慮到實際場景中柵欄并不能夠完全被修復，在柵欄間隙長度不同的情況下，若僅考慮修復能耗，無法確定算法修復效率，必須與柵欄修復成功率結合，才能對比相關算法的效率，因此需要引入柵欄修復率這一參數用于描述修復情況。 在柵欄修復率方面的實驗如圖8 所示，實驗結果表明隨著柵欄間隙長度的增加，柵欄修復成功率會逐漸降低，柵欄間隙長度增加，則需要的可移動節點數量增加，而可移動節點存在最大可移動距離R，因此修復率逐漸降低。BCR-OM 方法的柵欄修復成功率最高，在柵欄間隙長度為350 m 時，比Optimal 方法提高了8%左右，比Greedy 方法提高了12.6%左右，Optimal 方法的修復成功率高于Greedy 方法。

圖8 柵欄修復率圖

3.2 節點平均移動距離對比實驗

本文方法(BCR-OM)修復柵欄間隙理論上能夠保證柵欄中所有間隙的修復代價最小。 通過柵欄間隙修復實驗，可發現當部署的可移動傳感器節點較少時，由于間隙過長，可移動傳感器節點無法確保間隙修復率達到100%，因此本實驗將可移動傳感器節點數作為參數，通過對比可以的節點數量確定的情況下，完成修復時節點的平均移動距離，實現算法效率的對比以及可靠性比較。 此處將本文提出的方法與Greedy 算法進行對比，研究修復柵欄間隙過程中，可移動傳感器節點的移動的平均距離。 實驗中，將可移動傳感器節點的最大可移動距離D設置為30 m 和40 m。 實驗結果如圖9 所示，橫坐標為柵欄構建初期部署的可移動傳感器節點的數量，縱坐標表示完成柵欄間隙修復后，可移動傳感器節點的平均移動距離(m)。

圖9 節點平均移動距離圖

從圖9 的實驗結果圖中可以看出，當可移動節點的最大可移動距離相同的情況下，本文提出的BCR-OM 方法修復柵欄時可移動節點的平均移動距離大于Greedy 算法。 這是因為Greedy 算法總是派遣局部最接近待修復位置的可移動節點修復柵欄間隙，然而這種修復方法，經常會出現無法修復的情況，其實這些用Greedy 算法無法修復的情況，很可能用BCR-OM 方法是能修復的。 結果圖中Greedy算法的節點平均移動距離，為修復成功情況的平均結果，不含未修復成功的實驗情況。 本文的BCROM 方法對所有待修復位置進行宏觀考慮，對于能修復的情況，確保了找出代價最小的修復方案來，在確保能修復的場景都被修復該條件下，實現總體修復代價的最小化。 由于BCR-OM 方法所對應的平均移動距離，是對所有能修復的情況進行統計平均的，所以才出現了平均移動距離略大于Greedy 算法的平均移動距離的情況。 就單個Greedy 算法也可修復的場景來說，BCR-OM 方法的節點總移動距離一定小于Greedy 算法所對應的節點總移動距離。

從圖9 中還可以看出隨著可移動節點的最大移動距離D的逐漸的增加，其平均移動距離也在增加。

4 總結

本文主要介紹了一種基于最優匹配的低能耗柵欄修復方法，該方法主要研究如何派遣可移動節點修復柵欄間隙使得修復代價最小。 仿真實驗結果表明本文提出的柵欄間隙修復方法在修復率以及修復代價上都優于傳統的柵欄修復方法。 但是在成功修復的情況下，本方法的修復代價還是略高于Greedy算法。 考慮到實際應用環境往往較為復雜，仿真實驗太過理想化，本研究接下的工作擬搭建一套真實硬件網絡構成的測試平臺，通過半仿真實驗，進一步完善本文柵欄修復方法。