異構WSNs中節點穩定匹配的覆蓋空洞修復優化算法*

茍平章,毛 剛,李鳳珍,賈向東

(西北師范大學計算機科學與工程學院,蘭州 730070)

覆蓋空洞修復是衡量異構無線傳感器網絡HWSNs(Heterogeneous Wireless Sensor Networks)性能的重要指標之一,反映了一個區域被“感知”程度的優劣[1-3]。在實際應用中,由于網絡初始節點隨機部署,節點能耗不均或受周圍復雜情況影響,造成節點失效,目標無法被有效監測,網絡出現覆蓋空洞,導致感知信息的不完整,造成網絡通信不順暢,影響整個網絡的性能。因此,如何對覆蓋空洞進行及時有效的感知并修復,是異構無線傳感器網絡亟待解決的基本問題。

許多中外文獻對WSNs覆蓋空洞修復方法進行了研究,文獻[4]提出基于Voronoi圖分布式本地DHD(Deployment Algorithm for Hole Detection and Healing)算法發現覆蓋空洞,當兩個移動節點距離太靠近時相互排斥,距離太遠則相互吸引,移動節點整體的合力確定移動的方向和距離。文獻[5]提出基于Voronoi覆蓋空洞修復算法EECHS(Estimation and Enhancing of Coverage Holes Strategy),隨機部署的節點將監測區域劃分為若干Voronoi,再分割為若干三角形并結合相鄰節點生成的Voronoi找到覆蓋空洞位置,連接節點與相鄰公共邊兩端點形成一個夾角,在夾角平分線上找到最優空洞修復點,但算法復雜程度較高且修復后節點冗余較大。文獻[6]提出一種三角形網格空洞修復方法,利用ATN(Advanced Triangle Net)算法檢測節點與其鄰居節點構成的三角形網格是否被完全覆蓋,若沒有完全覆蓋則利用TNR(Triangle Net Recovery)算法通過向三角形網格特定位置添加節點使三角形網格達到完全覆蓋,該算法無需地理信息支持,但修復精度不夠,需要填補大量節點。文獻[7]提出一種基于極坐標的最小能耗覆蓋空洞修復算法,雖然算法有效減少移動修復節點個數,延長網絡生存周期,但空洞模型過于理想化,不適用于復雜節點分布環境。文獻[8]提出了最短k覆蓋區段和最長的k未覆蓋區段,但計算和交通量非常大。文獻[9]基于Voronoi圖劃分無線傳感器網絡高覆蓋度和節點移動最小化的問題,引入貪心算法和匈牙利算法求解最優解,不同傳感器節點負載更加均衡,網絡生存周期增長。文獻[10]提出一種基于泰森多邊形形心的覆蓋策略BCBS(Blind-zone Centroid-based Scheme),將多邊形的幾何中心作為節點移動的候選目標位置,移動節點移動到候選目標位置,進行空洞修復。文獻[11]提出的 VABC(Voronoi Artificial Bee Colony)算法通過Voronoi多邊形確定覆蓋盲區,盲區產生蜜源指導引領蜂搜尋,最優蜜源處即為移動節點最優部署位置,該方法收斂速度慢,容易造成局部最優解。文獻[12]提出一種基于樹和圖論的方法探測和修復覆蓋空洞,將大的空洞分為若干小的空洞逐個修復。文獻[13]提出一種基于全向傳感器柵欄分區構建算法FCOIS(Fence Construction for Omnidirectional Isomorphism Sensor Based on Subarea),根據節點初始隨機分布情況劃分子區域,采用貪婪算法對每個子區域內按序構建柵欄形成的空隙進行填充。文獻[14]對節點執行若干次迭代,以實現滿足初始隨機分布的覆蓋范圍的最終均勻分布,但收斂時間相應地更長。文獻[15]提出MNCO(Mobile Node’s Optimization Strategy)算法,在混合傳感器網絡中,采用基于誤警率的概率探測模型,計算節點的聯合探測概率尋找覆蓋空洞,但未對節點具體的移動方向進行優化。文獻[16]提出一種改進的C-V(Chan-Vese)模型計算出覆蓋空洞的數量和大小,改進粒子群算法的適應值函數達到網絡覆蓋優化的目的。

本文提出一種節點穩定匹配的覆蓋空洞修復優化算法ROA-NSM(Repair Optimization Algorithm for Node Stable Matching),該算法采用延遲匹配策略建立基于優先級的移動節點與虛擬修復節點之間的對應關系,并給出具體的節點優先級計算方法,通過對初始的匹配結果進行預剪枝加快算法收斂速度。首先,對目標監測區域隨機分布的靜態節點進行Voronoi多邊形劃分,采用聯合感知模型判斷多邊形區域中是否存在覆蓋空洞;其次,計算空洞節點形成Delaunay三角形的形心,利用形心與節點距離確定虛擬修復節點位置;最后,建立基于優先級的節點穩定匹配關系,根據匹配結果完成空洞修復。仿真結果表明,ROA-NSM算法加快節點匹配收斂速度,減少了匹配次數,在保證網絡覆蓋率的同時降低了移動節點的移動距離,驗證了該算法在空洞修復上的可行性。

1 系統模型

1.1 異構網絡模型假設

無線傳感器網絡中,異構節點被隨機部署到目標區域執行監測任務,為保證后續工作的開展。本文假設采用如下網絡模型:

假設1利用定位技術,網絡中所有節點具有自定位能力,靜態傳感器節點部署后不再移動。

假設2所有節點有相同的計算能力、通信能力、相同且有限的初始能量和自身唯一標識ID。

假設3節點通信半徑Rc為感知半徑Rs的兩倍,節點感知范圍和通信范圍都是以節點位置為圓心,以Rs、Rc為半徑的圓形區域。

假設4某監測區域內一點至少被一個節點有效監測,則該監測點被有效覆蓋。

1.2 異構節點感知模型

覆蓋空洞問題中,一個區域發生的事件通常會被多個傳感器節點同時感測,本文采用Neyman-Pearson模型感知多個節點對目標的聯合探測概率[7,16]。假設部署在目標監測區域的所有節點表示為{Si,i=1,2,3,…,n},該感知模型以傳感器節點為圓心,感知半徑為Rs的圓。考慮目標可能同時被多個節點感知,采用聯合感知模型來計算節點感知概率。感知圓監測區域內,任意節點?j與傳感器節點i的歐氏距離為:

(1)

節點i從目標接收到的能量Eri如下:

(2)

式中,Erj為j處發生事件釋放的能量,ni表示均值為0,方差為σ2的高斯噪聲,γ為感應信號衰減指數,通常取值為2或4,T0、T1分別表示目標存在和目標缺失的情況,β定義為:

(3)

式(3)中,Einit表示節點初始能量。

在T0狀態下,Eri的探測概率為:

(4)

在T1狀態下,Eri的探測概率為:

采用Neyman-Pearson模型,傳感器節點的探測概率PD可表示為[16]:

(6)

式中,α表示誤警率,φ(·)為標準正態分布累積分布函數,PD表示在可接受最小誤警率α的情況下,目標的最大探測概率。

當點j處于K個傳感器節點的感知圓覆蓋范圍內時,目標點區域內的聯合感知概率為:

(7)

網絡節點集S的覆蓋率定義如下:

(8)

式中,A表示區域面積,S[C(Pn]表示區域節點的覆蓋面積,假設S(Pcov)>0.9時,整個監測區域被有效覆蓋。

1.3 空洞模型

本文主要研究有界區域內,異構無線傳感器網絡節點隨機部署造成的覆蓋空洞問題。網絡中20個初始節點隨機分布形成的Voronoi多邊形如圖1所示,各節點區域是距離各個節點距離最近的凸區域,該區域內任一點與任何其他節點之間的距離都大于該點與節點S的距離,相鄰區域邊上的點到兩區域節點的距離相等,圖1中點K到節點S1與節點S2距離相等。由于節點隨機分布,很容易造成覆蓋空洞情況發生,導致區域監測效果達不到預期效果,由20個節點隨機分布造成的覆蓋空洞如圖2所示,僅感知圓區域被有效覆蓋,其他區域為覆蓋空洞區域,靜態傳感器節點與Voronoi多邊形的距離為:

(9)

V表示Voronoi多邊形頂點,S表示靜態傳感器節點,如果d(s,v)>Rs,則節點S所在的Voronoi多邊形區域出現覆蓋空洞,多個節點連接在一起,構成一個覆蓋空洞區域。

圖1 有界Voronoi劃分

圖2 覆蓋空洞模型

2 覆蓋空洞修復優化算法ROA-NSM

蓋爾-沙普利算法(Gale-Shapley Algorithm)是基于穩定匹配策略而設計的貪心算法,但其雙向匹配關系造成算法收斂速度過慢,ROA-NSM算法通過距離閾值函數和能量閾值函數確定節點優先級,對移動節點與虛擬修復節點建立穩定匹配關系,加快算法收斂速度,提高覆蓋空洞修復效率。

2.1 虛擬修復節點位置坐標的計算

與Voronoi多邊形互為偶圖的Delaunay三角形,是與該多邊形共享一條邊的相關點連接而成的三角形。圖3中小黑點為傳感器節點,任意3個距離最近的節點構成一個Delaunay三角形,圖3中節點{S1,S8,S3,S2,S10}構成一個覆蓋空洞區域。圖4為空洞修復模型,其中Si為靜態節點,Vi為虛擬修復節點,P是三角形S1S2S3的形心。

圖3 Delaunay三角形

圖4 Delaunay三角形修復模型

Delaunay三角形空洞修復步驟如下:

Step1根據靜態節點構成覆蓋空洞多邊形,找出空洞節點集Sh;

Step2遍歷覆蓋空洞區域節點集Shi,從任意一個節點出發,以最近的三點構成一個三角形;

Step3計算該三角形形心坐標P(x0,y0),(x0,y0)為三角形頂點的橫、縱坐標,點P的計算公式為:

(10)

(11)

Step5順時針旋轉移動到靜態節點S2,S3,重復Step 4,完成該三角形區域覆蓋;

Step6繼續移動到覆蓋空洞另一個三角形,重復Step 3～Step 5,完成該覆蓋空洞區域覆蓋;

Step7繼續遍歷余下覆蓋空洞區域,重復Step 3～Step 6,完成整個網絡空洞修復。

2.2 節點優先級排序

通過Delaunay三角剖分計算虛擬修復節點位置坐標,虛擬修復節點與移動節點基于閾值函數f進行優先級排序,f1表示基于移動節點能量的優先級函數,f2表示基于距離的優先級函數,距離越短,優先級越高。閾值函數的大小決定了節點排序的優先級,f越大,節點優先級越高,排序越靠前。

f=f1n1-f2n2

(12)

(13)

(14)

2.3 基于節點優先級排序結果的預剪枝處理

如果網絡中存在的虛擬修復節點過多,移動節點與虛擬修復節點邀約匹配時,一個虛擬修復節點的邀約常會被多個移動節點拒絕,為減少邀約過程中節點匹配收斂速度慢的特性,考慮節點能量有限,多次匹配易使節點能耗過多消耗,對節點優先級排序后結果進行預剪枝處理,剪去匹配關系中排名后1/4匹配結果,以加快ROA-NSM算法收斂速度。

2.4 穩定匹配算法執行過程

ROA-NSM算法開始執行時,虛擬修復節點vi向移動節點mi按優先級順序發出邀約匹配請求,如移動節點mi還未與其他節點匹配,則該虛擬修復節點與該移動節點進行匹配,一旦移動節點處于匹配狀態,則一直處于匹配狀態,但與其配對的虛擬修復節點是可變的,當收到更好的邀約匹配時,比較這兩個虛擬修復節點優先級,選擇優先級較大的節點相匹配,另一個虛擬修復節點恢復為未匹配狀態。

假設網絡中移動節點數mn大于虛擬修復節點數vn,根據vn確定mn的個數,具體步驟如下:

Step1喚醒覆蓋空洞周圍的移動節點,加入移動節點集T(m,n),式(12)計算每個移動節點與虛擬節點之間的閾值函數f,按f進行優先級排序存入表T(Sm,i);

Step2將虛擬修復節點vi附近移動節點同樣按照式(12)進行優先級排序保存至各自的待匹配列表T(Sv,i),f越大,優先級越高,在T(Sv,i)中排序越靠前;

Step3虛擬修復節點向移動節點發出匹配邀約,在其表T(Sv,i)從前往后開始,依次向優先級高的移動節點發出匹配邀約;

采用二分圖G=(M,Δ,V)為移動節點與虛擬修復節點的匹配關系建立數學模型。移動節點M={m1,m2…,mn},虛擬節點V={v1,v2,…,vn},Δ表示所有可能邊的集合。引入優先秩評定矩陣表示節點的優先級關系[17],該矩陣為n階方陣,i行、j列元素是數對(p,q),p表示vi對mi的排名優先級,q表示mi對vi排名優先級。穩定節點匹配對應矩陣不同行、列所有位置的集合。一個4階的優先秩評定矩陣節點優先級匹配關系如圖5(a)所示,圖5(b)為節點按優先級邀約匹配得到的匹配結果。v1對m1的排名優先級為1,m1對v1的排名優先級為2。

圖5 ROA-NSM節點匹配

Step4根據得到的穩定匹配結果,移動節點移動到虛擬修復節點處進行覆蓋空洞修復。

基于四個節點的ROA-NSM算法執行步驟為:

Step1v1向m1、v2向m2、v3向m4發出匹配邀約,m4對v3的優先級排名靠后1/4,剪去該匹配關系;

Step2v3向m1發出匹配邀約,m1拒絕v1;

Step3v1向m2發出邀約,m2拒絕v2;

Step4v2向m3,v4向m1發出邀約,m1拒絕v4;

Step5v4向m4發出邀約,匹配完成。

通過ROA-NSM算法完成該優先秩評定矩陣邀約匹配后,穩定匹配結果為:

v1?m2,v2?m3,v3?m1,v4?m4

因此,虛擬修復節點v1用移動節點m2修復,v2用m3修復,v3用m1修復,v4用m4修復,得到的結果與Gale-Shapley算法相同,但步驟更為精簡。

圖6(a)是使用ROA-NSM算法,修復由靜態節點S={S1,S8,S3,S2,S10}構成一個覆蓋空洞第一輪和最后一輪匹配過程。圖6(b)表示具體節點修復匹配,圖中實線表示虛擬修復節點向移動節點發出匹配邀約,而實際修復關系如圖中虛線所示。

圖6 節點匹配修復

圖7 基于穩定匹配的覆蓋空洞修復流程圖

2.5 ROA-NSM算法流程及時間復雜度分析

ROA-NSM算法從最理想的角度來說,每個虛擬修復節點剛好與優先級最高移動節點匹配成功,則整個算法只需遍歷一次,復雜度為O(n);從最壞的情況來說,每個匹配過的虛擬修復節點后來又被拒絕,匹配了最多n次后才成功匹配,考慮“預剪枝”對算法的影響,時間復雜度不會超過O(n2)。

3 仿真與結果分析

本文采用MATLAB2014a對算法進行驗證,假設在200 m×200 m的異構WSNs環境中隨機部署100個靜止節點和50個移動節點,具體實驗參數設置如表1所示。

表1 網絡環境與參數設置

圖8 覆蓋空洞修復前后傳感器節點位置分布圖

圖8為異構WSNs中覆蓋空洞修復前后節點分布圖。靜態節點隨機部署完成后,節點位置不再改變,通過移動節點的移動對覆蓋空洞進行修復。

圖9為ROA-NSM算法節點優先級匹配對應關系,通過距離閾值函數和能量閾值函數對節點進行優先級排序,優先級數值越小,級別越高,ROA-NSM算法對排序結果采用預剪枝剪去優先級列表中后1/4的節點。圖9(a)中星號為虛擬修復節點,小圈為移動節點,虛擬修復節點對移動節點發出匹配邀約,星號的縱坐標表示最終接受邀約的移動節點在優先級列表中的排名,小圈的縱坐標表示最終匹配的虛擬修復節點在優先級列表中的排名。從圖9(a)中可得,ROA-NSM算法最終匹配結果都是各自列表排名前3/4節點,且小圈總是處于星號的上方;圖9(b)橫坐標為節點匹配的輪數,縱坐標表示該輪匹配結束后,節點匹配對象在優先級列表中平均優先級,ROA-NSM算法匹配了69次。

圖9 ROA-NSM算法節點優先級匹配對應關系

圖10為Gale-Shapley算法的節點優先級匹配圖,Gale-Shapley算法匹配90次,ROA-NSM算法節點的匹配次數比Gale-Shapley算法減少了23.3%。由虛擬修復節點向移動節點發出邀約得到對虛擬修復節點更有利的匹配結果,虛擬修復節點匹配對象的平均優先級總高于移動節點匹配對象的平均優先級。

為驗證ROA-NSM算法的空洞覆蓋度,與BCBS和VABC算法進行對比。圖11是3種算法迭代次數與覆蓋率對比圖,隨著迭代次數的增加,3種算法網絡覆蓋率都上升,移動節點移動到最優的位置進行空洞修復。ROA-NSM算法覆蓋率總是優于VABC算法,直到18次迭代,ROA-NSM算法網絡覆蓋度超過BCBS算法,覆蓋度達到94.2%,優于其他2種算法。

圖10 Gale-Shapley算法節點優先級匹配對應關系

圖11 迭代次數與網絡覆蓋率比較

圖12 平均移動距離與網絡覆蓋率對比圖

圖12(a)為移動節點數與平均移動距離對比圖,將ROA-NSM算法與MNCO算法、C-V算法進行對比,驗證提出算法的有效性。3種算法的平均移動距離都隨著移動節點數目的增加而減少。ROA-NSM算法采用延遲匹配策略,考慮距離和能量因素,從每個虛擬修復節點的優先級列表中,查找一個最優節點用于匹配修復。圖12(b)為移動節點數與網絡覆蓋率對比圖,隨著移動節點數目的增加,網絡覆蓋率增強,當移動節點超過23時,覆蓋率超過90%,與C-V,MNCO算法相比,ROA-NSM算法移動節點移動距離分別減少20%和23.1%,覆蓋率分別提高1.35%和3.25%。

4 結束語

針對異構無線傳感器網絡中節點隨便部署造成覆蓋空洞問題,本文將圖論中Voronoi多邊形、Delaunay三角形與Gale-Shapley延遲匹配算法相結合,考慮Gale-Shapley在匹配數據量大時算法的低收斂性,對節點距離和能量閾值函數進行加權排序,引入“預剪枝策略”剪去優先級較低的節點,提出異構WSNs覆蓋空洞穩定匹配修復優化算法ROA-NSM,建立移動節點與虛擬修復節點的穩定匹配關系修復覆蓋空洞。在算法匹配次數、網絡覆蓋率、節點移動距離等方面進行仿真實驗分析,ROA-NSM算法移動節點的平均移動距離短并且保證了網絡的高覆蓋率,驗證了算法的有效性。