異構(gòu)WSNs中節(jié)點(diǎn)穩(wěn)定匹配的覆蓋空洞修復(fù)優(yōu)化算法*

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

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

覆蓋空洞修復(fù)是衡量異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)HWSNs(Heterogeneous Wireless Sensor Networks)性能的重要指標(biāo)之一,反映了一個(gè)區(qū)域被“感知”程度的優(yōu)劣[1-3]。在實(shí)際應(yīng)用中,由于網(wǎng)絡(luò)初始節(jié)點(diǎn)隨機(jī)部署,節(jié)點(diǎn)能耗不均或受周圍復(fù)雜情況影響,造成節(jié)點(diǎn)失效,目標(biāo)無(wú)法被有效監(jiān)測(cè),網(wǎng)絡(luò)出現(xiàn)覆蓋空洞,導(dǎo)致感知信息的不完整,造成網(wǎng)絡(luò)通信不順暢,影響整個(gè)網(wǎng)絡(luò)的性能。因此,如何對(duì)覆蓋空洞進(jìn)行及時(shí)有效的感知并修復(fù),是異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)亟待解決的基本問(wèn)題。

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

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

1 系統(tǒng)模型

1.1 異構(gòu)網(wǎng)絡(luò)模型假設(shè)

無(wú)線傳感器網(wǎng)絡(luò)中,異構(gòu)節(jié)點(diǎn)被隨機(jī)部署到目標(biāo)區(qū)域執(zhí)行監(jiān)測(cè)任務(wù),為保證后續(xù)工作的開(kāi)展。本文假設(shè)采用如下網(wǎng)絡(luò)模型:

假設(shè)1利用定位技術(shù),網(wǎng)絡(luò)中所有節(jié)點(diǎn)具有自定位能力,靜態(tài)傳感器節(jié)點(diǎn)部署后不再移動(dòng)。

假設(shè)2所有節(jié)點(diǎn)有相同的計(jì)算能力、通信能力、相同且有限的初始能量和自身唯一標(biāo)識(shí)ID。

假設(shè)3節(jié)點(diǎn)通信半徑Rc為感知半徑Rs的兩倍,節(jié)點(diǎn)感知范圍和通信范圍都是以節(jié)點(diǎn)位置為圓心,以Rs、Rc為半徑的圓形區(qū)域。

假設(shè)4某監(jiān)測(cè)區(qū)域內(nèi)一點(diǎn)至少被一個(gè)節(jié)點(diǎn)有效監(jiān)測(cè),則該監(jiān)測(cè)點(diǎn)被有效覆蓋。

1.2 異構(gòu)節(jié)點(diǎn)感知模型

覆蓋空洞問(wèn)題中,一個(gè)區(qū)域發(fā)生的事件通常會(huì)被多個(gè)傳感器節(jié)點(diǎn)同時(shí)感測(cè),本文采用Neyman-Pearson模型感知多個(gè)節(jié)點(diǎn)對(duì)目標(biāo)的聯(lián)合探測(cè)概率[7,16]。假設(shè)部署在目標(biāo)監(jiān)測(cè)區(qū)域的所有節(jié)點(diǎn)表示為{Si,i=1,2,3,…,n},該感知模型以傳感器節(jié)點(diǎn)為圓心,感知半徑為Rs的圓?？紤]目標(biāo)可能同時(shí)被多個(gè)節(jié)點(diǎn)感知,采用聯(lián)合感知模型來(lái)計(jì)算節(jié)點(diǎn)感知概率。感知圓監(jiān)測(cè)區(qū)域內(nèi),任意節(jié)點(diǎn)?j與傳感器節(jié)點(diǎn)i的歐氏距離為:

(1)

節(jié)點(diǎn)i從目標(biāo)接收到的能量Eri如下:

(2)

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

(3)

式(3)中,Einit表示節(jié)點(diǎn)初始能量。

在T0狀態(tài)下,Eri的探測(cè)概率為:

(4)

在T1狀態(tài)下,Eri的探測(cè)概率為:

采用Neyman-Pearson模型,傳感器節(jié)點(diǎn)的探測(cè)概率PD可表示為[16]:

(6)

式中,α表示誤警率,φ(·)為標(biāo)準(zhǔn)正態(tài)分布累積分布函數(shù),PD表示在可接受最小誤警率α的情況下,目標(biāo)的最大探測(cè)概率。

當(dāng)點(diǎn)j處于K個(gè)傳感器節(jié)點(diǎn)的感知圓覆蓋范圍內(nèi)時(shí),目標(biāo)點(diǎn)區(qū)域內(nèi)的聯(lián)合感知概率為:

(7)

網(wǎng)絡(luò)節(jié)點(diǎn)集S的覆蓋率定義如下:

(8)

式中,A表示區(qū)域面積,S[C(Pn]表示區(qū)域節(jié)點(diǎn)的覆蓋面積,假設(shè)S(Pcov)>0.9時(shí),整個(gè)監(jiān)測(cè)區(qū)域被有效覆蓋。

1.3 空洞模型

本文主要研究有界區(qū)域內(nèi),異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)部署造成的覆蓋空洞問(wèn)題。網(wǎng)絡(luò)中20個(gè)初始節(jié)點(diǎn)隨機(jī)分布形成的Voronoi多邊形如圖1所示,各節(jié)點(diǎn)區(qū)域是距離各個(gè)節(jié)點(diǎn)距離最近的凸區(qū)域,該區(qū)域內(nèi)任一點(diǎn)與任何其他節(jié)點(diǎn)之間的距離都大于該點(diǎn)與節(jié)點(diǎn)S的距離,相鄰區(qū)域邊上的點(diǎn)到兩區(qū)域節(jié)點(diǎn)的距離相等,圖1中點(diǎn)K到節(jié)點(diǎn)S1與節(jié)點(diǎn)S2距離相等。由于節(jié)點(diǎn)隨機(jī)分布,很容易造成覆蓋空洞情況發(fā)生,導(dǎo)致區(qū)域監(jiān)測(cè)效果達(dá)不到預(yù)期效果,由20個(gè)節(jié)點(diǎn)隨機(jī)分布造成的覆蓋空洞如圖2所示,僅感知圓區(qū)域被有效覆蓋,其他區(qū)域?yàn)楦采w空洞區(qū)域,靜態(tài)傳感器節(jié)點(diǎn)與Voronoi多邊形的距離為:

(9)

V表示Voronoi多邊形頂點(diǎn),S表示靜態(tài)傳感器節(jié)點(diǎn),如果d(s,v)>Rs,則節(jié)點(diǎn)S所在的Voronoi多邊形區(qū)域出現(xiàn)覆蓋空洞,多個(gè)節(jié)點(diǎn)連接在一起,構(gòu)成一個(gè)覆蓋空洞區(qū)域。

圖1 有界Voronoi劃分

圖2 覆蓋空洞模型

2 覆蓋空洞修復(fù)優(yōu)化算法ROA-NSM

蓋爾-沙普利算法(Gale-Shapley Algorithm)是基于穩(wěn)定匹配策略而設(shè)計(jì)的貪心算法,但其雙向匹配關(guān)系造成算法收斂速度過(guò)慢,ROA-NSM算法通過(guò)距離閾值函數(shù)和能量閾值函數(shù)確定節(jié)點(diǎn)優(yōu)先級(jí),對(duì)移動(dòng)節(jié)點(diǎn)與虛擬修復(fù)節(jié)點(diǎn)建立穩(wěn)定匹配關(guān)系,加快算法收斂速度,提高覆蓋空洞修復(fù)效率。

2.1 虛擬修復(fù)節(jié)點(diǎn)位置坐標(biāo)的計(jì)算

與Voronoi多邊形互為偶圖的Delaunay三角形,是與該多邊形共享一條邊的相關(guān)點(diǎn)連接而成的三角形。圖3中小黑點(diǎn)為傳感器節(jié)點(diǎn),任意3個(gè)距離最近的節(jié)點(diǎn)構(gòu)成一個(gè)Delaunay三角形,圖3中節(jié)點(diǎn){S1,S8,S3,S2,S10}構(gòu)成一個(gè)覆蓋空洞區(qū)域。圖4為空洞修復(fù)模型,其中Si為靜態(tài)節(jié)點(diǎn),Vi為虛擬修復(fù)節(jié)點(diǎn),P是三角形S1S2S3的形心。

圖3 Delaunay三角形

圖4 Delaunay三角形修復(fù)模型

Delaunay三角形空洞修復(fù)步驟如下:

Step1根據(jù)靜態(tài)節(jié)點(diǎn)構(gòu)成覆蓋空洞多邊形,找出空洞節(jié)點(diǎn)集Sh;

Step2遍歷覆蓋空洞區(qū)域節(jié)點(diǎn)集Shi,從任意一個(gè)節(jié)點(diǎn)出發(fā),以最近的三點(diǎn)構(gòu)成一個(gè)三角形;

Step3計(jì)算該三角形形心坐標(biāo)P(x0,y0),(x0,y0)為三角形頂點(diǎn)的橫、縱坐標(biāo),點(diǎn)P的計(jì)算公式為:

(10)

(11)

Step5順時(shí)針旋轉(zhuǎn)移動(dòng)到靜態(tài)節(jié)點(diǎn)S2,S3,重復(fù)Step 4,完成該三角形區(qū)域覆蓋;

Step6繼續(xù)移動(dòng)到覆蓋空洞另一個(gè)三角形,重復(fù)Step 3～Step 5,完成該覆蓋空洞區(qū)域覆蓋;

Step7繼續(xù)遍歷余下覆蓋空洞區(qū)域,重復(fù)Step 3～Step 6,完成整個(gè)網(wǎng)絡(luò)空洞修復(fù)。

2.2 節(jié)點(diǎn)優(yōu)先級(jí)排序

通過(guò)Delaunay三角剖分計(jì)算虛擬修復(fù)節(jié)點(diǎn)位置坐標(biāo),虛擬修復(fù)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)基于閾值函數(shù)f進(jìn)行優(yōu)先級(jí)排序,f1表示基于移動(dòng)節(jié)點(diǎn)能量的優(yōu)先級(jí)函數(shù),f2表示基于距離的優(yōu)先級(jí)函數(shù),距離越短,優(yōu)先級(jí)越高。閾值函數(shù)的大小決定了節(jié)點(diǎn)排序的優(yōu)先級(jí),f越大,節(jié)點(diǎn)優(yōu)先級(jí)越高,排序越靠前。

f=f1n1-f2n2

(12)

(13)

(14)

2.3 基于節(jié)點(diǎn)優(yōu)先級(jí)排序結(jié)果的預(yù)剪枝處理

如果網(wǎng)絡(luò)中存在的虛擬修復(fù)節(jié)點(diǎn)過(guò)多,移動(dòng)節(jié)點(diǎn)與虛擬修復(fù)節(jié)點(diǎn)邀約匹配時(shí),一個(gè)虛擬修復(fù)節(jié)點(diǎn)的邀約常會(huì)被多個(gè)移動(dòng)節(jié)點(diǎn)拒絕,為減少邀約過(guò)程中節(jié)點(diǎn)匹配收斂速度慢的特性,考慮節(jié)點(diǎn)能量有限,多次匹配易使節(jié)點(diǎn)能耗過(guò)多消耗,對(duì)節(jié)點(diǎn)優(yōu)先級(jí)排序后結(jié)果進(jìn)行預(yù)剪枝處理,剪去匹配關(guān)系中排名后1/4匹配結(jié)果,以加快ROA-NSM算法收斂速度。

2.4 穩(wěn)定匹配算法執(zhí)行過(guò)程

ROA-NSM算法開(kāi)始執(zhí)行時(shí),虛擬修復(fù)節(jié)點(diǎn)vi向移動(dòng)節(jié)點(diǎn)mi按優(yōu)先級(jí)順序發(fā)出邀約匹配請(qǐng)求,如移動(dòng)節(jié)點(diǎn)mi還未與其他節(jié)點(diǎn)匹配,則該虛擬修復(fù)節(jié)點(diǎn)與該移動(dòng)節(jié)點(diǎn)進(jìn)行匹配,一旦移動(dòng)節(jié)點(diǎn)處于匹配狀態(tài),則一直處于匹配狀態(tài),但與其配對(duì)的虛擬修復(fù)節(jié)點(diǎn)是可變的,當(dāng)收到更好的邀約匹配時(shí),比較這兩個(gè)虛擬修復(fù)節(jié)點(diǎn)優(yōu)先級(jí),選擇優(yōu)先級(jí)較大的節(jié)點(diǎn)相匹配,另一個(gè)虛擬修復(fù)節(jié)點(diǎn)恢復(fù)為未匹配狀態(tài)。

假設(shè)網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)數(shù)mn大于虛擬修復(fù)節(jié)點(diǎn)數(shù)vn,根據(jù)vn確定mn的個(gè)數(shù),具體步驟如下:

Step1喚醒覆蓋空洞周圍的移動(dòng)節(jié)點(diǎn),加入移動(dòng)節(jié)點(diǎn)集T(m,n),式(12)計(jì)算每個(gè)移動(dòng)節(jié)點(diǎn)與虛擬節(jié)點(diǎn)之間的閾值函數(shù)f,按f進(jìn)行優(yōu)先級(jí)排序存入表T(Sm,i);

Step2將虛擬修復(fù)節(jié)點(diǎn)vi附近移動(dòng)節(jié)點(diǎn)同樣按照式(12)進(jìn)行優(yōu)先級(jí)排序保存至各自的待匹配列表T(Sv,i),f越大,優(yōu)先級(jí)越高,在T(Sv,i)中排序越靠前;

Step3虛擬修復(fù)節(jié)點(diǎn)向移動(dòng)節(jié)點(diǎn)發(fā)出匹配邀約,在其表T(Sv,i)從前往后開(kāi)始,依次向優(yōu)先級(jí)高的移動(dòng)節(jié)點(diǎn)發(fā)出匹配邀約;

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

圖5 ROA-NSM節(jié)點(diǎn)匹配

Step4根據(jù)得到的穩(wěn)定匹配結(jié)果,移動(dòng)節(jié)點(diǎn)移動(dòng)到虛擬修復(fù)節(jié)點(diǎn)處進(jìn)行覆蓋空洞修復(fù)。

基于四個(gè)節(jié)點(diǎn)的ROA-NSM算法執(zhí)行步驟為:

Step1v1向m1、v2向m2、v3向m4發(fā)出匹配邀約,m4對(duì)v3的優(yōu)先級(jí)排名靠后1/4,剪去該匹配關(guān)系;

Step2v3向m1發(fā)出匹配邀約,m1拒絕v1;

Step3v1向m2發(fā)出邀約,m2拒絕v2;

Step4v2向m3,v4向m1發(fā)出邀約,m1拒絕v4;

Step5v4向m4發(fā)出邀約,匹配完成。

通過(guò)ROA-NSM算法完成該優(yōu)先秩評(píng)定矩陣邀約匹配后,穩(wěn)定匹配結(jié)果為:

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

因此,虛擬修復(fù)節(jié)點(diǎn)v1用移動(dòng)節(jié)點(diǎn)m2修復(fù),v2用m3修復(fù),v3用m1修復(fù),v4用m4修復(fù),得到的結(jié)果與Gale-Shapley算法相同,但步驟更為精簡(jiǎn)。

圖6(a)是使用ROA-NSM算法,修復(fù)由靜態(tài)節(jié)點(diǎn)S={S1,S8,S3,S2,S10}構(gòu)成一個(gè)覆蓋空洞第一輪和最后一輪匹配過(guò)程。圖6(b)表示具體節(jié)點(diǎn)修復(fù)匹配,圖中實(shí)線表示虛擬修復(fù)節(jié)點(diǎn)向移動(dòng)節(jié)點(diǎn)發(fā)出匹配邀約,而實(shí)際修復(fù)關(guān)系如圖中虛線所示。

圖6 節(jié)點(diǎn)匹配修復(fù)

圖7 基于穩(wěn)定匹配的覆蓋空洞修復(fù)流程圖

2.5 ROA-NSM算法流程及時(shí)間復(fù)雜度分析

ROA-NSM算法從最理想的角度來(lái)說(shuō),每個(gè)虛擬修復(fù)節(jié)點(diǎn)剛好與優(yōu)先級(jí)最高移動(dòng)節(jié)點(diǎn)匹配成功,則整個(gè)算法只需遍歷一次,復(fù)雜度為O(n);從最壞的情況來(lái)說(shuō),每個(gè)匹配過(guò)的虛擬修復(fù)節(jié)點(diǎn)后來(lái)又被拒絕,匹配了最多n次后才成功匹配,考慮“預(yù)剪枝”對(duì)算法的影響,時(shí)間復(fù)雜度不會(huì)超過(guò)O(n2)。

3 仿真與結(jié)果分析

本文采用MATLAB2014a對(duì)算法進(jìn)行驗(yàn)證,假設(shè)在200 m×200 m的異構(gòu)WSNs環(huán)境中隨機(jī)部署100個(gè)靜止節(jié)點(diǎn)和50個(gè)移動(dòng)節(jié)點(diǎn),具體實(shí)驗(yàn)參數(shù)設(shè)置如表1所示。

表1 網(wǎng)絡(luò)環(huán)境與參數(shù)設(shè)置

圖8 覆蓋空洞修復(fù)前后傳感器節(jié)點(diǎn)位置分布圖

圖8為異構(gòu)WSNs中覆蓋空洞修復(fù)前后節(jié)點(diǎn)分布圖。靜態(tài)節(jié)點(diǎn)隨機(jī)部署完成后,節(jié)點(diǎn)位置不再改變,通過(guò)移動(dòng)節(jié)點(diǎn)的移動(dòng)對(duì)覆蓋空洞進(jìn)行修復(fù)。

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

圖9 ROA-NSM算法節(jié)點(diǎn)優(yōu)先級(jí)匹配對(duì)應(yīng)關(guān)系

圖10為Gale-Shapley算法的節(jié)點(diǎn)優(yōu)先級(jí)匹配圖,Gale-Shapley算法匹配90次,ROA-NSM算法節(jié)點(diǎn)的匹配次數(shù)比Gale-Shapley算法減少了23.3%。由虛擬修復(fù)節(jié)點(diǎn)向移動(dòng)節(jié)點(diǎn)發(fā)出邀約得到對(duì)虛擬修復(fù)節(jié)點(diǎn)更有利的匹配結(jié)果,虛擬修復(fù)節(jié)點(diǎn)匹配對(duì)象的平均優(yōu)先級(jí)總高于移動(dòng)節(jié)點(diǎn)匹配對(duì)象的平均優(yōu)先級(jí)。

為驗(yàn)證ROA-NSM算法的空洞覆蓋度,與BCBS和VABC算法進(jìn)行對(duì)比。圖11是3種算法迭代次數(shù)與覆蓋率對(duì)比圖,隨著迭代次數(shù)的增加,3種算法網(wǎng)絡(luò)覆蓋率都上升,移動(dòng)節(jié)點(diǎn)移動(dòng)到最優(yōu)的位置進(jìn)行空洞修復(fù)。ROA-NSM算法覆蓋率總是優(yōu)于VABC算法,直到18次迭代,ROA-NSM算法網(wǎng)絡(luò)覆蓋度超過(guò)BCBS算法,覆蓋度達(dá)到94.2%,優(yōu)于其他2種算法。

圖10 Gale-Shapley算法節(jié)點(diǎn)優(yōu)先級(jí)匹配對(duì)應(yīng)關(guān)系

圖11 迭代次數(shù)與網(wǎng)絡(luò)覆蓋率比較

圖12 平均移動(dòng)距離與網(wǎng)絡(luò)覆蓋率對(duì)比圖

圖12(a)為移動(dòng)節(jié)點(diǎn)數(shù)與平均移動(dòng)距離對(duì)比圖,將ROA-NSM算法與MNCO算法、C-V算法進(jìn)行對(duì)比,驗(yàn)證提出算法的有效性。3種算法的平均移動(dòng)距離都隨著移動(dòng)節(jié)點(diǎn)數(shù)目的增加而減少。ROA-NSM算法采用延遲匹配策略,考慮距離和能量因素,從每個(gè)虛擬修復(fù)節(jié)點(diǎn)的優(yōu)先級(jí)列表中,查找一個(gè)最優(yōu)節(jié)點(diǎn)用于匹配修復(fù)。圖12(b)為移動(dòng)節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)覆蓋率對(duì)比圖,隨著移動(dòng)節(jié)點(diǎn)數(shù)目的增加,網(wǎng)絡(luò)覆蓋率增強(qiáng),當(dāng)移動(dòng)節(jié)點(diǎn)超過(guò)23時(shí),覆蓋率超過(guò)90%,與C-V,MNCO算法相比,ROA-NSM算法移動(dòng)節(jié)點(diǎn)移動(dòng)距離分別減少20%和23.1%,覆蓋率分別提高1.35%和3.25%。

4 結(jié)束語(yǔ)

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