一種低能耗的無線傳感器網(wǎng)絡(luò)強(qiáng)柵欄重建方法研究?

陶建林，苗春雨，戴國勇

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

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

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

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

1 相關(guān)模型和定義

1.1 相關(guān)模型

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

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

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

1.2 相關(guān)定義

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

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

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

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

圖1 柵欄重建圖

2 柵欄重建路徑

2.1 全連接拓?fù)鋱D建立

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

圖2 靜態(tài)節(jié)點全連接拓?fù)鋱D

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

2.2 柵欄重建路徑選擇

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

圖3 重建路徑修復(fù)圖

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

3.1 重建路徑判斷

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

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

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

圖4 柵欄重建判斷圖

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

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

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

③任意兩個修復(fù)位置的移動節(jié)點集合并集的元素數(shù)量都大于或等于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é)采用改進(jìn)的Hungarian算法派遣可移動節(jié)點重建柵欄，并從H條重建路徑中找到一條最佳重建路徑，使移動節(jié)點消耗的能量總和最少。

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

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

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

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

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

表2 最佳柵欄重建表

4 仿真實驗

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

圖6 柵欄重建結(jié)果圖

4.1 柵欄重建長度影響

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

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

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

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

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

圖7 柵欄重建長度分析結(jié)果圖

4.2 節(jié)點比例影響

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

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

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

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

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

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

5 總結(jié)

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