陶建林，苗春雨，戴國勇

(1.浙江工業(yè)職業(yè)技術學院，浙江紹興312000；2.浙江師范大學數理與信息工程學院，浙江金華321004；3.浙江工業(yè)大學計算機科學與技術學院，杭州310023；4.安恒信息技術有限公司網絡空間安全學院，杭州310051)

無線傳感器網絡柵欄覆蓋在入侵檢測等諸多領域都有著廣泛的用途，如可將傳感器網絡部署在工廠周圍，有效的監(jiān)測污染物的擴散范圍；在軍事方面，將傳感器部署在陣地前沿，能夠有效的監(jiān)測敵人是否發(fā)動突襲[1－2]。無線傳感器網絡主要部署在帶狀區(qū)域或環(huán)形區(qū)域中，將區(qū)域一分為二，其作用是高效的監(jiān)測目標是否由一個區(qū)域穿越到另一區(qū)域中，這種技術被稱為無線傳感器網絡柵欄覆蓋[3－4]。傳感器網絡由于節(jié)點自身原因或外界因素的影響(泥石流、洪災等)，柵欄極易被破壞，從而導致柵欄失去功能[5]。在柵欄被破壞后如何修復和重建是熱點研究問題。

目前的研究一般采用移動節(jié)點解決柵欄間隙問題，如Saipulla等人[6]提出柵欄間隙的尋找方法，并利用最大流算法和二分法對柵欄間隙進行修復，使修復代價最小。戴光麟等人[7]改進了參考文獻[6]提出的方法，利用鄰居可移動節(jié)點集合降低了修復算法的復雜度。Xu B等人[8]建立入侵軌跡模型預測入侵者穿越柵欄時的位置，并將可移動節(jié)點移動到頻繁穿越位置強化柵欄，防止出現(xiàn)柵欄間隙。Deng等人[9]研究了一種混合傳感器網絡柵欄間隙修復方法，假設傳感器節(jié)點的感知范圍可調，利用移動節(jié)點修復柵欄使得移動距離最短。Chen等人[10]根據節(jié)點間距離查找柵欄間隙，并通過旋轉柵欄中關鍵傳感器節(jié)點或一段柵欄修復柵欄間隙。Dash等人[11]提出一種分布式的柵欄修復方法，首先查找間隙處是否有冗余柵欄可以替換，如果有，則替換，否則派遣移動節(jié)點對間隙進行修復。Xu H等人[12]提出最小費用方案和自適應貪婪移動方案修復柵欄間隙，其中最小費用方案為集中式算法，修復柵欄間隙費用最小。上述柵欄間隙修復方法都是利用可移動節(jié)點修復柵欄較短的柵欄間隙，而不適用于柵欄被大段破壞后的重建問題。

在柵欄重建方面的研究，如Tian等人[13]根據不同天氣，調度不同類型的傳感器節(jié)點，實現(xiàn)雨天和晴天的柵欄重建。而針對柵欄出現(xiàn)大范圍破壞后的重建研究較少，柵欄間隙修復和重建的區(qū)別在于失效柵欄的長度，柵欄間隙一般較短，使用少量可移動傳感器節(jié)點即可完成修復，而重建柵欄的長度較長，需充分利用靜態(tài)傳感器節(jié)點以降低代價。本文利用KSP算法尋找k條重建路徑，然后利用Hungarian算法選擇最佳重建路徑并派遣可移動節(jié)點重建柵欄，使能耗盡可能的降低。

1 相關模型和定義

1.1 相關模型

①傳感器節(jié)點采用二元感知模型，以傳感器節(jié)點為圓心，感知半徑為r，當監(jiān)測目標進入感知范圍內，傳感器節(jié)點能夠監(jiān)測到目標的概率為1，否則為0，如式(1)所示，靜態(tài)傳感器節(jié)點和可移動傳感器節(jié)點的感知半徑相同。

式(1)中o表示傳感器節(jié)點，t表示監(jiān)測目標，d(o，t)表示傳感器節(jié)點與監(jiān)測目標的歐氏距離，Po，t表示節(jié)點監(jiān)測到目標的概率。

②可移動節(jié)點在移動時消耗的能量遠遠高于感知消耗的能量，因此可移動節(jié)點感知消耗的能量忽略不計，且移動過程消耗的能量與移動距離呈正比，移動1 m消耗的能量為3.6 J[14－15]。

1.2 相關定義

定義1 柵欄重建，當柵欄遭受大范圍的破壞后，利用靜態(tài)節(jié)點和可移動節(jié)點重新構建柵欄的過程，如圖1中一段較長的柵欄受泥石流沖擊后，傳感器節(jié)點脫離了柵欄，需對損壞的柵欄段進行重建。

定義2 重建路徑，充分利用靜態(tài)傳感器節(jié)點重建柵欄，從柵欄損壞段的最左端S節(jié)點開始，經過若干個靜態(tài)傳感器節(jié)點到最右端D節(jié)點，則經過的路徑被稱重建路徑，其中重建柵欄消耗能量最少的路徑稱為最佳重建路徑。

定義3 修復位置，如圖1，重建路徑中節(jié)點i和j的感知區(qū)域并沒有重疊，如果可移動節(jié)點移動到位置m，使得節(jié)點i和j之間的邊被感知區(qū)域完全覆蓋，則稱m為修復位，如果需要多個可移動節(jié)點才能完全覆蓋節(jié)點之間的邊，則修復位在節(jié)點之間的邊上均勻分布。

定義4 柵欄重建能耗，指可移動節(jié)點完成柵欄重建所消耗的能量總和，因此只與移動節(jié)點的總移動距離有關。

圖1 柵欄重建圖

2 柵欄重建路徑

2.1 全連接拓撲圖建立

假設傳感器節(jié)點已利用GPS設備或相關定位算法獲得了自身的位置，為充分利用靜態(tài)傳感器節(jié)點，減少可移動節(jié)點的使用，首先利用部署區(qū)域中的靜態(tài)傳感器節(jié)點構建全連接拓撲圖G(V，E)，如圖2所示。假設柵欄重建處有4個靜態(tài)傳感器節(jié)點n1、n2、ni、nj，以左側柵欄最右端節(jié)點 S 為開始點，右側柵欄最左端節(jié)點D為結束點構建全連接拓撲圖，其中 V 和 E 如式(2)、式(4)所示，numi，j表示節(jié)點 ni和nj之間的邊被節(jié)點感知范圍完全覆蓋所需最少傳感器節(jié)點的數量，如公式(5)所示。

圖2 靜態(tài)節(jié)點全連接拓撲圖

式(2)表示拓撲圖G中靜態(tài)傳感器節(jié)點集合，nw表示靜態(tài)傳感器節(jié)點，w表示G中靜態(tài)傳感器節(jié)點數量，式(3)中 ei，j表示節(jié)點 ni和 nj之間的邊(節(jié)點S和D對應的邊也包含其中)，式(4)表示拓撲圖G的邊集合，sn為圖G節(jié)點總共數量，sn＝w＋2，式(5)中d(ei，j)表示靜態(tài)節(jié)點ni和 nj之間的歐氏距離，r表示節(jié)點的感知范圍，1≤i，j≤sn。

2.2 柵欄重建路徑選擇

影響柵欄重建能耗的因素有2點：①需要移動的傳感器節(jié)點數量；②可移動節(jié)點在重建柵欄時的移動平均距離。由于本文假設傳感器節(jié)點在區(qū)域中均勻隨機部署，因此暫時無法選擇某條重建路徑使重建柵欄的能耗最低(節(jié)點的移動距離總和最短)，但可以從所需移動節(jié)點數量上考慮，當某條重建路徑所需的可移動節(jié)點數量越少，則重建柵欄所消耗的能量越小的概率越高，因此本文利用KSP算法[16－18]搜索拓撲圖G中所需移動節(jié)點數量由少到多的前k條重建路徑，表示為集合Rp，如式(6)所示，當k取值合適時，最佳修復路徑被包含在這k條路徑中，倘若尋找到最佳重建路徑，則可達到柵欄重建能耗最低的目的。

圖3 重建路徑修復圖

3 移動節(jié)點重建柵欄過程

3.1 重建路徑判斷

在1.2小節(jié)利用KSP算法尋找到k條重建路徑，但并非都能夠完成柵欄的重建。由于可移動節(jié)點數量和移動距離有限，最大可移動距離為R，當重建路徑上的修復位置不能被移動節(jié)點完全覆蓋，則該重建路徑不能完成柵欄重建，如圖3所示。

重建路徑path1存在3個修復位置，在移動范圍R內，可移動節(jié)點mn1移動到修復位置2，mn2移動到修復位置3，完成這兩個修復位置的修復，但是沒有移動節(jié)點可移動到修復位置1，因此重建路徑path1沒有足夠的移動節(jié)點完成柵欄重建。

參考文獻[6]提出利用最大流方法判斷柵欄間隙能否被修復，但該方法相對復雜，不適用于柵欄重建問題。本文提出一種基于集合運算方法判斷某條重建路徑能否成功重建柵欄，如圖4所示。

圖4 柵欄重建判斷圖

圖中柵欄重建路徑從S點開始，到D點結束，存在3個修復位置，倘若所有的修復位置至少都能夠分配到一個可移動節(jié)點，則沿著該重建路徑能夠重建柵欄。在移動距離為R時，可移動到修復位置1、2、3的移動節(jié)點集合分別表示為 Set1＝{mn1，mn2}、Set2＝{mn2}、Set3＝{mn3，mn4，mn5}，當同時滿足以下三個條件時，該路徑能夠完成柵欄的重建。

①所有移動節(jié)點集合并集的元素數量大于或等于重建路徑中修復位置總數，即｜Set1∪Set2∪……Sett｜≥t，t為重建路徑中修復位置的總數。

②所有移動節(jié)點集合都不為空，即對a取任何值，Seta≠?，1≤a≤t。

③任意兩個修復位置的移動節(jié)點集合并集的元素數量都大于或等于2，即對a，b取任何值，都滿足｜Seta∪Setb｜≥ 2，1≤a，b≤t，a≠b。

基于上述三個條件，可以判斷圖4所示的重建路徑能夠完成柵欄的重建。具體判斷方法如表1所示。

表1 重建路徑能否重建柵欄的判斷方法表

3.2 最佳柵欄重建

2.2小節(jié)采用KSP算法選擇了k條重建路徑，然后利用3.1小節(jié)提出的重建路徑判斷方法篩選出若干條(H條)能夠完成柵欄重建的重建路徑，本節(jié)采用改進的Hungarian算法派遣可移動節(jié)點重建柵欄，并從H條重建路徑中找到一條最佳重建路徑，使移動節(jié)點消耗的能量總和最少。

Hungarian算法一般用于人員最優(yōu)指派問題，假設u個工人去完成u個任務，每個任務只能派遣1個工人，而每個工人對不同任務的熟練程度是不同的，Hungarian算法能夠最優(yōu)的指派人員去做相應的工作，使完成所有工作花費的時間總和最短[19－20]。因此該算法能夠貼切的應用于柵欄重建時的可移動節(jié)點派遣問題，使所有節(jié)點的移動距離總和最少。在H條重建路徑中的任意一條都滿足修復位置總數(z)少于等于可移動節(jié)點總數(t)，即滿足3.1小節(jié)的條件1。將可移動節(jié)點派遣到修復位置問題類比到人員指派問題，用t個可移動節(jié)點移動到z個修復位置，每個修復位置最多接受一個可移動節(jié)點，則剩余t－z個可移動節(jié)點沒有使用，因此本文在修復路徑上虛擬出t－z個虛擬修復位置，使t個可移動節(jié)點被派遣到t個修復位置，具體方法如圖5所示，總共分為兩種情況。

圖5 移動節(jié)點與修復位置情況圖

圖5 (a)重建路徑中存在2個修復位置，且可移動節(jié)點數量也為2，可移動節(jié)點mn1可以移動到修復位置a，距離為d1，而不能移動到修復位置b(超出可移動節(jié)點的最大可移動距離R)，則規(guī)定mn1移動到修復位置b的距離為＋∞；節(jié)點mn2可同時移動到修復位置a和b，距離分別是d2和d3，利用節(jié)點與修復位置的距離作為重建柵欄的代價，構建Hungarian算法的代價矩陣，如式(7)所示。

圖5(b)重建路徑中存在2個修復位置，而可移動節(jié)點有3個，因此需要虛擬一個修復位置，如圖5(b)中虛擬位置o所示。所有可移動節(jié)點與虛擬位置o的距離都為0，假設可移動節(jié)點與修復位置的距離大于移動節(jié)點的最大移動距離R時，則規(guī)定該節(jié)點與修復位置的距離為＋∞。構建的Hungarian算法代價矩陣如公式(8)所示。

在重建柵欄過程中，根據上述兩種情況構建重建路徑的代價矩陣，然后利用Hungarian算法分別計算H條重建路徑的重建代價，即沿每條重建路徑重建柵欄，移動節(jié)點的移動距離總和，最后選擇節(jié)點移動距離總和最短的一條重建路徑，該路徑為最佳重建路徑，并派遣移動節(jié)點沿最佳重建路徑重建柵欄使得總能耗盡可能降低，實現(xiàn)算法如表2。

表2 最佳柵欄重建表

4 仿真實驗

采用 i5處理器、8 G內存的 PC機，利用MATLAB平臺進行仿真實驗。將靜態(tài)和可移動傳感器節(jié)點按照不同比例隨機均勻的部署在一個長為3 000 m，寬為300 m的矩形區(qū)域中，節(jié)點總數為100，所有節(jié)點感知半徑r相同，可移動節(jié)點的最大移動距離為R。該區(qū)域中存在一條被破壞的柵欄，對損壞部分進行重建(節(jié)點S和D之間)，如圖6所示。實驗從柵欄重建的移動節(jié)點需求數量、可移動節(jié)點的平均移動距離、柵欄重建總能耗和柵欄重建率四項指標分析對比了BRMLE柵欄重建方法和參考文獻[6]提出的最佳柵欄修復方法Optimal(柵欄修復是柵欄重建的一種)。

圖6 柵欄重建結果圖

4.1 柵欄重建長度影響

柵欄重建長度是影響重建的重要因素之一，理論上重建長度越長，則需要的可移動節(jié)點數量越多，消耗的能量越多，柵欄重建率越低。實驗中可移動節(jié)點的最大移動距離R＝70 m，同時實驗分析了可移動節(jié)點占40%和60%的情況對柵欄重建的影響，結果如圖7所示。

圖7(a)分析了柵欄重建長度與可移動節(jié)點需求數量的關系，實驗結果表明Optimal方法在可移動節(jié)點比例為40%和60%時，重建柵欄所需要的可移動節(jié)點數量相同。隨著重建長度的增加，完成柵欄重建需要的可移動節(jié)點數量呈線性增加，在重建相同長度的柵欄時BRMLE方法需要的可移動節(jié)點數量少于Optimal方法(當可移動節(jié)點比例為40%時，重建2 700 m的柵欄，Optimal方法平均需要31個可移動節(jié)點，而BRMLE方法僅需要18個可移動節(jié)點)，因為BRMLE方法充分利用靜態(tài)傳感器節(jié)點，當靜態(tài)傳感器節(jié)點不能完成柵欄重建時，才派遣可移動節(jié)點，而Optimal方法完全采用可移動傳感器節(jié)點完成柵欄重建。BRMLE方法中可移動節(jié)點占比越低，需要的移動節(jié)點數量越少，有利于節(jié)約成本。

圖7(b)分析了柵欄重建長度和可移動節(jié)點平均移動距離的關系，實驗結果表明柵欄重建長度與可移動節(jié)點的平均移動距離無關，柵欄重建過程中，可移動節(jié)點的平均移動距離基本保持穩(wěn)定，在可移動節(jié)點占比相同的情況下BRMLE方法和Optimal方法的可移動節(jié)點平均移動距離基本相同，因為可移動節(jié)點在部署區(qū)域中均勻隨機分布。可移動節(jié)點占60%時平均移動距離為24.3 m，可移動節(jié)點占40%時平均移動距離為31.5 m，因為可移動節(jié)點占比越高，移動節(jié)點在區(qū)域中越密集，到達修復位置的距離越短。

圖7(c)分析了柵欄重建長度與柵欄重建總能耗的關系，能耗模型如1.1小節(jié)所示，重建能耗和可移動節(jié)點需求數量、節(jié)點的平均移動距離相關，實驗結果表明隨著柵欄重建長度的增加，總能耗呈線性增加，因為柵欄重建長度增加，需要的可移動節(jié)點數量呈線性增加，而在可移動節(jié)點比例不變的情況下，平均移動距離基本穩(wěn)定，因此總能耗呈線性增加。BRMLE方法消耗的總能量低于Optimal方法，當可移動節(jié)點占40%時，重建2 700 m柵欄，BRMLE方法消耗的能量為75.3 J，Optimal方法消耗的能量為1498.6 J，因為BRMLE方法充分利用靜態(tài)傳感器節(jié)點，需要的可移動節(jié)點數量少于Optimal方法，而兩種方法的可移動節(jié)點平均移動距離基本相同，導致BRMLE方法重建柵欄時可移動節(jié)點的總移動距離更短，因此消耗的總能量越少。

圖7(d)分析了柵欄重建長度和柵欄重建率的關系，實驗結果表明隨著柵欄重建長度的增加，柵欄重建率逐漸降低，其中BRMLE方法降低的幅度逐漸減少，最終區(qū)域平穩(wěn)，而Optimal方法的柵欄重建率呈線性降低。柵欄重建長度相同時，BRMLE方法的柵欄重建率遠遠高于Optimal方法，當可移動節(jié)點占40%時，重建2 700 m柵欄，BRMLE方法的重建率為64.7%，而Optimal方法的重建率為11.4%。

圖7 柵欄重建長度分析結果圖

4.2 節(jié)點比例影響

實驗分析可移動節(jié)點占總節(jié)點比例對柵欄重建的影響，實驗中重建1 000 m的柵欄，同時分析了可移動節(jié)點不同最大移動距離R情況下算法的性能。

圖8(a)分析了可移動節(jié)點比例和可移動節(jié)點需求數量關系，實驗結果表明隨著可移動節(jié)點比例的增加，BRMLE方法需要的可移動節(jié)點數量逐漸增加，而Optimal方法不變，因為Optimal方法直接重建S到D的直線路徑，因此需要的移動節(jié)點數量不變，而BRMLE方法需要利用靜態(tài)傳感器節(jié)點，當可移動節(jié)點比例增加，靜態(tài)節(jié)點的比例降低，因此需要的可移動節(jié)點數量增加。BRMLE方法需要的可移動節(jié)點數量低于Optimal方法，當可移動節(jié)點占100%時，兩種方法需要的可移動節(jié)點數量相同，因為此時BRMLE方法的柵欄重建路徑與Optimal方法相同。

圖8(b)分析了可移動節(jié)點比例與節(jié)點平均移動距離關系，實驗結果表明隨著可移動節(jié)點比例的增加，平均移動距離都逐漸減低，最后區(qū)域平穩(wěn)，因為可移動節(jié)點的比例增加，則部署區(qū)域中可移動節(jié)點密度越大，距離重建路徑中修復位置的距離也就越近。且在R相同時，BRMLE和Optimal方法的平均移動距離基本相同。

圖8(c)分析了可移動節(jié)點比例與柵欄重建總能耗關系，實驗結果表明隨著可移動節(jié)點比例的增加，BRMLE方法消耗的總能量逐漸增加，因為可移動節(jié)點比例增加，靜態(tài)節(jié)點的比例降低，需要的可移動節(jié)點數量會增加，而節(jié)點平均移動距離降低，綜合來看，消耗的總能量小幅度升高。Optimal方法消耗的總能量逐漸降低，因為可移動節(jié)點比例增加，Optimal方法需要的可移動節(jié)點數量不變，而可移動節(jié)點的平均移動距離降低，因此消耗的總能量降低。BRMLE方法消耗的總能量低于Optimal方法。

圖8(d)分析了可移動節(jié)點比例與柵欄重建率關系，實驗結果表明隨著可移動節(jié)點比例增加，柵欄重建率都成升高趨勢。在可移動節(jié)點比例相同時BRMLE方法的柵欄重建率遠高于Optimal方法，因為BRMLE方法選擇需要可移動節(jié)點數量最少，移動距離總和最短的重建路徑，因此具有較大的概率完成柵欄的重建。

圖8 節(jié)點比例分析結果圖

5 總結

研究了一種能耗優(yōu)先考慮的1－強柵欄重建方法(BRMLE)，利用KSP算法搜尋k條重建路徑，然后利用Hungarian算法選擇最佳重建路徑并派遣可移動節(jié)點完成柵欄的重建。實驗與目前較優(yōu)秀的Optimal方法進行對比，證明了BRMLE在可移動節(jié)點需求數量、柵欄重建率、能量消耗等方面都具有較好的性能。后續(xù)工作希望進一步研究K－強柵欄重建方法。