基于Voronoi 圖的無線傳感網絡覆蓋盲區檢測方法

陳振峰，陳紀鑫

(1.廣州番禺職業技術學院財經學院，廣東 廣州 511483；2.華南理工大學建筑學院，廣東 廣州 510614)

近年來，無線傳感網絡(Wireless Sensor Network，WSN)[1]逐漸普及到人類生活的各行各業，成為當今社會的研究熱點。公共區域監控、黑客入侵檢測、智能機械操作、智慧城市建設均離不開無線傳感網絡的參與，可見無線傳感網絡已成功依靠其優質的網絡服務質量和高效的節點傳輸能力，成為21 世紀最有價值的計算機科研項目之一。然而無線傳感網絡內部分節點長期處于無覆蓋的活躍度低迷的休眠狀態，對網絡的連通性造成不可估量的影響。因此，相關的無線傳感網絡覆蓋盲區檢測與修復研究引起了學者的關注。

王寒露等[2]通過超聲檢測方法對擴散場扇掃重建，并利用10 MHz 超聲相控陣探頭搜查重建區域的時間寬窗，以獲取有效擴散時間內較為全面的網絡近表面盲區缺陷。但是該方法存在檢測效率低的問題。Iqbal 等[3]提出了基于復回波狀態網絡預測原理的正交幅度調制信號在線盲均衡算法。通過調整振幅和相位，實現由非線性信道引起的傳輸信號失真檢測。但是該方法存在檢測場景受限的問題。李志軍等[4]通過孤島檢測方法將無線傳感網絡節點映射至Q×C坐標系中，并利用真實校驗方法獲取坐標系內單位節點的負載品質因數，通過觀察橫、縱坐標下各節點的負載品質因網絡覆蓋盲區檢測數對應的節點活躍度，實現無線傳感網絡覆蓋盲區檢測。但是該方法存在檢測能耗高的問題。董鑫等[5]提出了裝有魚眼鏡頭的傳感器網絡連通保持覆蓋控制策略。在建立有向視覺傳感器節點覆蓋性能函數的基礎上，利用控制器約束節點的轉動角度、運動步長，從而確保整個網絡的連通性，以此提升覆蓋連通度，減少盲區的產生。但是該方法主要針對的是優化傳感器連通度提升策略，對其應用后是否依舊會產生覆蓋盲區，盲區出現數量等問題未進行分析。Kishk 等[6]利用可重構智能表面技術在移動用戶和沒有直接視線信道的基站之間提供間接視線鏈路。通過提供額外的間接視線鏈路來提高蜂窩網絡的覆蓋概率。但是該方法受節點冗余度影響，造成覆蓋檢測能耗較高。蔣世華等[7]提出了基于軸面對稱機制的物聯網節點覆蓋算法。該方法通過對稱分布簇頭節點分割物聯網，以提高覆蓋效率。利用鏡像節點、簇頭輪詢方法增強網絡傳輸能力。該方法降低了簇頭受限概率，但是受盲區的影響，造成檢測能耗較高。

為了提高無線傳感網絡通信效率，準確檢測盲區，提出基于Voronoi 圖的無線傳感網絡覆蓋盲區檢測方法。

1 無線傳感網絡覆蓋率

從宏觀視角觀察無線傳感網絡，其由傳感器節點[8]和網絡用戶共同組成。想要檢測無線傳感網絡覆蓋盲區，需要優先了解無線傳感網絡節點的分布關系和網絡大體覆蓋情況。

1.1 無線傳感網絡節點的分布關系

根據無線傳感網絡幾何判定理論可知，無線傳感網絡中的節點[9]不是無規則散亂分布，而是遵循極坐標平面極軸關系以三角形及三角形外接圓半徑的形式首尾相連。這種有規律的分布形式能夠最大限度提升節點間的通信半徑T和感知半徑U:

式中:f2表示無線傳感網絡選定平面的坐標原點；s表示相鄰節點的歐氏距離；d表示三角形邊長；i表示外接圓半徑；lo表示目標范圍內的節點數量；l3表示節點虛擬距離；l5表示節點移動步長；τ表示無線傳感網絡通信執行次數。

無線傳感網絡節點分布關系如圖1 所示。

圖1 無線傳感網絡節點分布關系

1.2 無線傳感網絡覆蓋情況

在成功了解無線傳感網絡節點分布關系的基礎上，推測無線傳感網絡大體覆蓋情況?？紤]到單個節點不受通信半徑和感知半徑的約束，能在初始能量的支持下圍繞穩態范圍移動，且網絡節點分布關系在節點周期性運行途中不會發生離散現象。在推測無線傳感網絡大體覆蓋情況時，需要追蹤傳感器節點運行軌跡，并在不干擾傳感器節點拓撲結構的同時，沿追蹤路徑構建柵欄[10]，使傳感器節點在運行過程中覆蓋的網絡區域得以保留。

傳感器節點作為暴露在網絡通信地帶，隨不同應用場合改變二維空間曲線的信息傳輸載體，能夠通過解耦合的方式移動節點傳輸貢獻量[11]對應的歐幾里德距離，實現傳感器節點的周期性運行。正常情況下，傳感器節點的鄰近節點受到節點分布關系的限制，必須保持固定部署位置完成網絡通訊任務。這種限定條件使得傳感器節點在一次運行周期內的傳輸貢獻量固定不變，極大程度降低了節點運行軌跡的追蹤難度。極坐標[12]不同于傳統二維坐標，其坐標系極角升序排列關系與無線傳感網絡節點分布關系一一對應，將無線傳感網絡與極坐標結合，通過追蹤坐標系內傳感器節點的運行軌跡，即可實現實際應用中網絡節點運行軌跡的追蹤。傳感器節點傳輸貢獻量，如式(2)所示:

式中:T表示節點通信半徑；U表示節點感知半徑；xi表示放置策略；n表示無線傳感網絡頂端和底端的中心位置；表示節點冗余度；u表示節點在目標區域中的最小收斂時速。

傳感器節點解耦合，如式(3)所示:

式中:ceil(·)表示取整函數，?表示跟蹤過程中傳感器節點理想軌跡偏移率；c表示傳感器節點垂足坐標；x表示傳感器節點備選路段。

極坐標中傳感器節點在橫、縱坐標上移動的歐幾里德距離，如式(4)所示:

式中:σ表示節點傳輸貢獻量在橫坐標上的對應位移；qn表示節點傳輸貢獻量在縱坐標上的對應位移；qn＋1表示全軌跡劃分交點數；q2表示傳感器源點和目的地的垂直距離；η表示無線傳感網絡的全局拓撲信息；sn表示鄰近節點的聯通半徑；sm表示起點集合節點數量；f3表示終點集合節點數量；B表示同構節點數據傳輸速率。

在成功獲取傳感器節點運行軌跡的基礎上，沿追蹤路徑構建柵欄。根據Gage 機器人在網絡通信背景下獲取的有效追蹤檢測區域內節點移動軌跡，可知傳感器節點的運行軌跡多呈現多邊形結構，因此在沿途構建柵欄過程中，應優先確定多邊形結構的形心位置，以達到網絡覆蓋區域的無窮方向取整估算。多邊形結構形心位置，如式(5)所示:

式中:Δω表示多邊形面積；z表示節點多數性能指標；Δj表示虛線圓圓心所標記的中心位置；r表示傳感器節點當前位置。

柵欄公式如式(6)所示:

多邊形結構的二維平面圖如圖2 所示。

圖2 多邊形結構的二維平面圖

柵欄能夠保留傳感器節點運行途中覆蓋的網絡區域，通過統計柵欄在平面中的全部位置，即可得到無線傳感網絡的大體覆蓋情況。

2 無線傳感網絡覆蓋盲區檢測

Voronoi 圖[13]又稱Dirichlet 圖，是由來自俄國的Voronoi Diagram 教授就幾何晶體、信息系統、建筑理論等一系列問題提出的全景分割算法[14]，該算法因其優越的網絡空間分割能力和節點調度能力被廣泛應用于各種科研領域當中。由于Voronoi 圖與無線傳感網絡節點運行軌跡在行為邏輯表現出高度一致性，Voronoi 圖也常被應用于無線傳感網絡相關的研究當中。采用Voronoi 圖檢測無線傳感網絡覆蓋盲區的基本思路圍繞排除已覆蓋區域和具備檢測條件的未覆蓋無線傳感網絡空洞特征展開。

2.1 排除已覆蓋區域

掌握了無線傳感網絡的大體覆蓋情況，以此為基礎，在Voronoi 圖的指導下通過排除已覆蓋區域，獲取具備檢測條件的未覆蓋無線傳感網絡空洞，其具體過程如下:首先將無線傳感網絡與Voronoi 圖結合，然后過濾已覆蓋區域?？紤]到無線傳感網絡已覆蓋區域和未覆蓋區域存在數學理論和物理特性的差異，在獲取網絡空洞的過程中，應忽略兩區域差異引發的節點感知強度和通信能力隨節點活性喪失而產生的能量損耗，如式(7)所示:

式中:k?表示已覆蓋區域和未覆蓋區域的垂直平分線；t3表示兩區域的數學理論差異；t6表示兩區域的物理特性差異；yn表示覆蓋區域的節點數量；ym表示空洞節點數量；α表示節點感知精度；ε2表示已覆蓋區域的節點稀疏性。

無線傳感網絡空洞的表達式:

式中:ψk表示空洞圓盤面積；δ表示取余數；e表示空洞圓心距。

2.2 未覆蓋無線傳感網絡空洞特征

未覆蓋的無線傳感網絡空洞之所以具備盲區檢測價值，是因為其空洞暴露程度和節點能量均與已覆蓋的無線傳感網絡不同，即未覆蓋的無線傳感網絡空洞具有檢測效果顯著的盲區特征。以上述無線傳感網絡空洞為基礎，分別計算空洞區域的暴露程度和節點能量，作為檢測無線傳感網絡覆蓋盲區的特征樣本?？斩磪^域暴露程度，如式(9)所示:

式中:κ表示空洞區域內節點的給定HBN 序列；γ2表示鄰近節點覆蓋矛盾；b表示空洞有向鏈路；hij表示空洞數量。

空洞區域節點能量，如式(10)所示:

式中:p2表示順時針節點序列；dij表示負無窮方向取整；cosμ表示目標點到空洞區域的最近距離。

粒子群分類器[15]是由粒子群編碼和分類規則適應度共同組成的擇優信任匹配算法，常被應用于多種領域的數據集分類工作中。將空洞區域的暴露程度和節點能量作為特征樣本輸入粒子群分類器中，根據分類器的輸出結果，即可實現無線傳感網絡覆蓋盲區的有效檢測。粒子群分類器如式(11)所示:

式中:pvj表示粒子的適應度；dirs表示粒子的速度；I表示分類器迭代次數。

粒子群分類器檢測特征樣本的表達式，如式(12)所示:

式中:ζ表示特征樣本均勻性；sinθi表示矛盾數據剔除率；cosθj表示特征樣本分類敏感度。根據上述過程中，實現基于Voronoi 圖的無線傳感網絡覆蓋盲區檢測，并將其總結為下述步驟:

步驟1:明確無線傳感網絡節點的分布關系和當前覆蓋情況；

步驟2:融合無線傳感網絡與Voronoi 圖:忽略已覆蓋區域和未覆蓋區域差異引發的節點感知強度和通信能力隨節點活性喪失而產生的能量損耗上，根據式(8)獲取無線傳感網絡空洞，并利用Voronoi圖生成無線傳感網絡覆蓋盲區示意圖；

步驟3:計算空洞區域的暴露程度和節點能量，作為檢測無線傳感網絡覆蓋盲區的特征樣本；

步驟4:將獲取的特征樣本輸入粒子群分類器中，根據式(11)輸出無線傳感網絡覆蓋盲區檢測結果。

3 仿真與結果

為了驗證基于Voronoi 圖的無線傳感網絡覆蓋盲區檢測方法的整體有效性，需要對其進行測試。

3.1 仿真設置

利用MATLAB2020B 軟件，在200 m×200 m 的無線傳感網絡區域中，以20 m 為節點通信半徑隨機部署10×105 個傳感器節點。在無線傳感網絡中采取隨機部署的方式，部署傳感器節點，由于所使用路由算法、環境等因素的影響，導致部分節點失效，造成無線傳感網絡存在覆蓋盲區。其他相關參數如表1所示，無線傳感網絡覆蓋盲區如圖3 所示。

表1 仿真環境的相關參數

圖3 無線傳感網絡覆蓋盲區示意圖

圖3 矩形區域是需要被無線傳感網絡傳感器檢測的目標區域，灰色的部分為覆蓋盲區。

3.2 仿真結果分析

根據上述參數設置，將文獻[2]擴散場扇掃重建格林函數實現近表盲區缺陷檢測方法、文獻[3]基于復回波狀態網絡預測的覆蓋盲區檢測方法作為對比方法進行測試，結果如下。

3.2.1 檢測效率

分別采用所提方法、文獻[2]方法和文獻[3]方法檢測設定仿真環境的覆蓋盲區數量，分別為5、15、20、25、30 個，并記錄不同方法的檢測時長，每種情況下分別進行多次運算，取其時間平均值，得到的結果如圖4 所示。

圖4 不同方法的檢測時長

如圖4 可見，采用所提方法檢測無線傳感網絡覆蓋盲區，其檢測時長僅有0.2 s，說明所提方法的效率較高。因為所提方法以無線傳感網絡大體覆蓋情況為基礎，在Voronoi 圖的指導下通過排除已覆蓋區域，獲取具備檢測條件的未覆蓋無線傳感網絡空洞，并將網絡空洞的暴露程度和節點能量作為樣本特征輸入粒子群分離器中，進一步提高了檢測結果的可信度和檢測效率。采用文獻[2]方法和文獻[3]方法檢測無線傳感網絡覆蓋盲區，二者檢測時長均與所提方法存在較大差距，說明文獻[2]方法和文獻[3]方法的效率較低。經上述對比，可知所提方法的檢測效率明顯優于對比方法。

3.2.2 檢測能耗

在算法檢測過程中，參與檢測的無線傳感網絡面積越大、節點數量越多，檢測所消耗的能耗越高。檢測能耗的增高不僅會使算法冗余信息處理誤差升高，還會增加檢測負擔，使檢測效率大幅度下降。分別采用所提方法、文獻[2]方法和文獻[3]方法檢測上述仿真環境的覆蓋盲區，并記錄無線傳感網絡檢測面積增大的過程中，節點數量為10×102、10×103、10×104、10×105時的檢測能耗，上述數量分別標記為A～D。以檢測能耗為指標，判斷不同方法應用后的盲區檢測性能。不同方法的檢測能耗如圖5所示。

圖5 不同方法的檢測能耗

由圖5 可見，采用所提方法檢測無線傳感網絡覆蓋盲區，隨著網絡檢測面積的增大、節點數量的增多，其檢測能耗正比上升，且始終不超過20 J，說明所提方法的檢測能耗不僅穩定，而且維持在較低水平，不會由于計算負擔增大而產生檢測效率低下等問題。采用文獻[2]方法和文獻[3]方法檢測無線傳感網絡覆蓋盲區，隨著網絡檢測面積的增大、節點數量的增多，二者檢測能耗上升明顯且無等價關系，說明文獻[2]方法和文獻[3]方法的檢測能耗較高，極易由于計算負擔增大而產生檢測效率低下等問題。經上述對比，可知所提方法的檢測能耗明顯優于對比方法。

3.2.3 檢測差異度

檢測率即所提方法應用后的無線傳感網絡覆蓋盲區檢測效果，以檢測差異度為指標進行測試。差異度作為反映算法檢測結果與實際結果相似度的評估指標，主要用于體現檢測結果的精確度。差異度越大，檢測結果與實際結果的相似度越小，算法精確度越??；差異度越小，檢測結果與實際結果的相似度越大，算法精確度越高。差異度計算公式見式(13):

式中:ξm表示差異度閾值；κ表示檢測結果；iimage表示實際結果。

分別采用所提方法、文獻[2]方法和文獻[3]方法檢測上述仿真環境的覆蓋盲區，得到不同空洞圓心距下的覆蓋盲區檢測差異度。結果如圖6 所示。

圖6 不同方法的差異度

由圖6 可見，所提方法檢測結果的差異度較低，低于0.24，說明所提方法檢測結果與實際結果較為相符。文獻[2]方法和文獻[3]方法檢測結果的差異度較高，說明文獻[2]方法和文獻[3]方法檢測結果與實際結果的相似度較小。經上述對比，可知所提方法的檢測精確度明顯優于對比方法。

4 結束語

無線傳感網絡是具有節點組織性、通信可靠性、聯通自主性的高功能無線覆蓋網絡。為了使無線傳感網絡不受覆蓋盲區的阻礙，提出基于Voronoi 圖的無線傳感網絡覆蓋盲區檢測方法。在明確無線傳感網絡空洞覆蓋情況的基礎上，利用Voronoi 圖排除已覆蓋區域，提取未覆蓋無線傳感網絡空洞。通過將空洞暴露程度和節點能量輸入粒子群分離器中，實現無線傳感網絡覆蓋盲區檢測。仿真結果表明，所提方法在提高網絡覆蓋盲區檢測效率的同時，降低了檢測能耗和檢測差異度。由此驗證了所提方法可以有效提高無線傳感網絡節點通信能力，減少覆蓋盲區對通信質量造成的影響。實時監控網絡覆蓋盲區檢測過程，將是研究人員下一步工作的重點。