趙逢達(dá),默云鳳,孔令富,景 榮

(燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004 河北省計算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室,河北 秦皇島 066004)

1 引 言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是由大量傳感器節(jié)點(diǎn)以自組織多跳的方式組成的無線網(wǎng)絡(luò)[1].覆蓋率作為WSN 服務(wù)質(zhì)量的重要度量指標(biāo),反映了WSN所能提供的“感知”服務(wù),其能夠使WSN 的空間資源得到優(yōu)化分配,更好地完成環(huán)境感知、信息獲取和有效傳輸?shù)娜蝿?wù),所以提高覆蓋率對WSN 覆蓋空洞的修復(fù)有著重要意義.

大量中外文獻(xiàn)對WSN覆蓋空洞的修復(fù)問題進(jìn)行了研究,但是還沒有統(tǒng)一的分類標(biāo)準(zhǔn).在靜態(tài)WSN中,主要采用調(diào)節(jié)傳感器節(jié)點(diǎn)的屬性[2,3]和添加傳感器節(jié)點(diǎn)[4]的方式進(jìn)行覆蓋空洞的修復(fù);在動態(tài)WSN中通過節(jié)點(diǎn)的移動來完成覆蓋空洞的修復(fù).研究方法主要分為網(wǎng)絡(luò)覆蓋空洞修復(fù)策略、基于虛擬力以及圖論的算法等[5].韓蕊、閏雒恒、Lei Zuo、Jalal Habibi等人[6-9]分別提出基于現(xiàn)有理論的網(wǎng)絡(luò)覆蓋空洞修復(fù)方法;文獻(xiàn)[10]提出基于虛擬力的覆蓋空洞修復(fù)方法.文獻(xiàn)[11,12]是基于圖論的覆蓋空洞修復(fù)算法,通過最值化圖形面積或者兩點(diǎn)距離的方式完成覆蓋空洞的修復(fù).上面提到的覆蓋空洞修復(fù)方法假設(shè)網(wǎng)絡(luò)中不同位置被覆蓋的重要性是相同的,但是在真實(shí)環(huán)境中有些位置需要被優(yōu)先覆蓋(如涉及安全問題或重大機(jī)密問題).文獻(xiàn)[13-15]在覆蓋空洞修復(fù)方法中考慮到了覆蓋優(yōu)先級.孫澤宇[13]利用貪婪算法和節(jié)點(diǎn)調(diào)度機(jī)制完成具有不同覆蓋優(yōu)先級的監(jiān)測區(qū)域內(nèi)有效覆蓋問題,但未考慮傳感器節(jié)點(diǎn)異構(gòu)的情況.景榮等[14]提出通過剔除冗余候選中繼節(jié)點(diǎn)產(chǎn)生最優(yōu)部署位置的方法來完成覆蓋空洞的修復(fù),但該算法只適用于傳感器節(jié)點(diǎn)部署均勻的網(wǎng)絡(luò).在傳感器節(jié)點(diǎn)隨機(jī)部署的情況下,H.Mahboubi等人[15]提出了適用于具有不同覆蓋優(yōu)先級的異構(gòu)無線傳感器網(wǎng)絡(luò)的最大加權(quán)頂點(diǎn)(MWP)方法來獲得最大網(wǎng)絡(luò)覆蓋率.但是當(dāng)覆蓋優(yōu)先級高的點(diǎn)主要集中在某個區(qū)域內(nèi)時,按照該方法將傳感器節(jié)點(diǎn)移動到具有最大加權(quán)值的頂點(diǎn)的位置,此時傳感器節(jié)點(diǎn)的加權(quán)覆蓋面積可能不是最大的,可見該方法的適用性受限制.又由于該方法中的局部加權(quán)覆蓋面積采用中心點(diǎn)權(quán)重之和與面積的乘積,在提高算法簡潔性的同時降低了所得到覆蓋面積的精確度.因此該方法對傳感器節(jié)點(diǎn)覆蓋面積的精確獲取以及適用性都有待提高.

為了解決上述問題,本文提出了一種具有覆蓋優(yōu)先級的異構(gòu)WSN覆蓋空洞修復(fù)方法,即最佳傳感器節(jié)點(diǎn)配置的方法(Optimal Sensor Configuration,OSC).為了更好地把握本文結(jié)構(gòu)以及更好地理解此覆蓋空洞修復(fù)方法(OSC),將覆蓋空洞修復(fù)方法流程圖展示如圖1所示.

該方法首先對異構(gòu)網(wǎng)絡(luò)進(jìn)行區(qū)域劃分,然后根據(jù)傳感器節(jié)點(diǎn)的局部加權(quán)覆蓋面積計算傳感器節(jié)點(diǎn)的候選位置,最后根據(jù)本文所提策略不斷調(diào)整傳感器節(jié)點(diǎn)的位置,使傳感器節(jié)點(diǎn)移動到最佳部署位置從而完成覆蓋空洞修復(fù)的任務(wù).與該類問題的其它方法相比,本文貢獻(xiàn)主要包括以下幾點(diǎn):

1.將具有覆蓋優(yōu)先級的異構(gòu)WSN中覆蓋空洞修復(fù)問題模型化,采用MW-Voronoi圖理論對監(jiān)測區(qū)域劃分,并利用不定積分的方法準(zhǔn)確獲取傳感器節(jié)點(diǎn)局部加權(quán)覆蓋面積.

2.提出the center multiplicatively weighted voronoi(簡稱CMWV)算法,它能使傳感器節(jié)點(diǎn)不斷調(diào)整自身位置到達(dá)最佳部署位置,從而使具有不同覆蓋優(yōu)先級的異構(gòu)WSN的整體加權(quán)覆蓋面積最大,完成網(wǎng)絡(luò)覆蓋空洞修復(fù)任務(wù).

3.與MWP方法進(jìn)行對比,驗(yàn)證OSC方法的高效性.

2 覆蓋空洞修復(fù)數(shù)學(xué)模型

2.1 前提假設(shè)

假設(shè)1.網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)具有精確的自定位功能.

假設(shè)2.傳感器節(jié)點(diǎn)的感知范圍和通信范圍都是以節(jié)點(diǎn)所在位置為圓心,以定長為半徑的圓形區(qū)域,且傳感器節(jié)點(diǎn)的通信半徑等于感知半徑的兩倍,感知范圍和通信范圍不隨時間的變化而變化.

假設(shè)3.傳感器節(jié)點(diǎn)之間的通信內(nèi)容包括其自身的感知半徑和位置信息.

假設(shè)4.傳感器節(jié)點(diǎn)之間實(shí)施同步協(xié)議,保證所有傳感器節(jié)點(diǎn)同時開始第一個階段.同時為了使修復(fù)方法更好地發(fā)揮作用,規(guī)定覆蓋周期足夠長.

2.2 覆蓋空洞修復(fù)理論描述

本文采用使傳感器節(jié)點(diǎn)向合適的方向移動來進(jìn)行覆蓋空洞修復(fù).在真實(shí)世界的許多應(yīng)用中,傳感器節(jié)點(diǎn)修復(fù)覆蓋空洞的最佳部署位置事先是不知道的,但傳感器節(jié)點(diǎn)的可移動性允許對自身位置進(jìn)行調(diào)整,通過合理部署傳感器節(jié)點(diǎn)完成修復(fù)覆蓋空洞的任務(wù).

在空洞修復(fù)過程中,由于傳感器節(jié)點(diǎn)感知半徑不完全相同且不同位置點(diǎn)被覆蓋的優(yōu)先級不同,所以本文中覆蓋空洞修復(fù)的本質(zhì)是增大網(wǎng)絡(luò)的總加權(quán)覆蓋面積,使得空洞范圍不斷減小到消失.由假設(shè)可知,網(wǎng)絡(luò)中每個傳感器節(jié)點(diǎn)都能獲取其自身及相鄰傳感器節(jié)點(diǎn)的感知半徑和位置信息.根據(jù)這些信息采用MW-Voronoi 圖理論方法對網(wǎng)絡(luò)進(jìn)行分塊研究,劃分后每個子區(qū)域中有且僅有一個傳感器節(jié)點(diǎn).在本文提出的覆蓋空洞修復(fù)方法下,每個傳感器節(jié)點(diǎn)向合適的方向不斷移動,使得每個傳感器節(jié)點(diǎn)局部加權(quán)覆蓋面積不斷增大,從而增大網(wǎng)絡(luò)的總加權(quán)覆蓋面積.

2.3 覆蓋空洞修復(fù)模型化

本節(jié)首先對覆蓋空洞修復(fù)過程中用到的相關(guān)概念進(jìn)行解釋說明,然后將具有覆蓋優(yōu)先級的異構(gòu)WSN中覆蓋空洞修復(fù)問題進(jìn)行模型化.為了完成覆蓋空洞修復(fù)的任務(wù),將網(wǎng)絡(luò)中某個空洞范圍視作監(jiān)測區(qū)域,進(jìn)行覆蓋空洞修復(fù)研究.

2.3.1 相關(guān)定義

乘法加權(quán)泰森多邊形可用于定性分析、統(tǒng)計分析、鄰近分析等,在分析和設(shè)計覆蓋空洞的修復(fù)過程中此圖非常有用,介紹如下.

假設(shè)二維平面R2中存在n個具有不同加權(quán)值的節(jié)點(diǎn),即(S1,ω1),(S2,ω2),…,(Sn,ωn),這些點(diǎn)的集合用S表示,其中對?i∈n,Si的加權(quán)因子ωi>0.

定義1.節(jié)點(diǎn)(Si,ωi)到位置點(diǎn)q的加權(quán)距離定義如下:

(1)

其中,d(q,Si)是平面內(nèi)節(jié)點(diǎn)Si和位置點(diǎn)q之間的歐氏距離.

將平面劃分為n個區(qū)域使得每個區(qū)域有且只有一個節(jié)點(diǎn),且這個節(jié)點(diǎn)是到它所在區(qū)域任何位置點(diǎn)的加權(quán)距離最近的節(jié)點(diǎn).這種圖劃分的方法稱為the multiplicatively weighted Voronoi(MW-Voronoi)diagram[16].每個區(qū)域的特性用數(shù)學(xué)公式可表示為:

Πi={q∈R2|dω(q,Si)≤dω(q,Sj),?j∈n{i}}

(2)

定義2.平面內(nèi)任意給定兩個節(jié)點(diǎn)A、B以及正實(shí)數(shù)k,滿足AE/BE=k的所有點(diǎn)E的軌跡,就叫做線段AB形成的Apollonion circle 即ΩAB,k[17].

在本節(jié)后規(guī)定用Πi來表示第i個MW-Voronoi區(qū)域,為了構(gòu)建Πi,首先找出所有節(jié)點(diǎn)Sj∈S{Si}的 Apollonion circle,即ΩSiSj,ωi/ωj.這會形成許多Apollonion circle,其中包含第i個節(jié)點(diǎn)的最小閉合區(qū)域就是Πi區(qū)域,如圖2所示.

圖2 擁有4個鄰點(diǎn)s2,s3,s4,s5的s1節(jié)點(diǎn)的MW-Voronoi區(qū)域[10]

2.3.2 覆蓋空洞修復(fù)的建模

假設(shè)用一個R2的二維平面區(qū)域來表示監(jiān)測區(qū)域,集合S表示隨機(jī)分布在區(qū)域中的N個感知半徑為ri的傳感器節(jié)點(diǎn),傳感器節(jié)點(diǎn)的感知半徑不完全相同.該區(qū)域中不同位置被覆蓋的重要性用優(yōu)先級函數(shù)φ(q)來表示.例如q點(diǎn)的重要性大于p點(diǎn),那么q點(diǎn)比p點(diǎn)被覆蓋的優(yōu)先級高,即φ(q)>φ(p).運(yùn)用MW-Voronoi圖理論對監(jiān)測區(qū)域進(jìn)行劃分,所有傳感器節(jié)點(diǎn)在提出的方法下向合適的方向移動,盡可能多地覆蓋優(yōu)先級高的區(qū)域.即通過傳感器節(jié)點(diǎn)之間有限信息的交換,提高監(jiān)測區(qū)域的總加權(quán)覆蓋面積.

定義3.優(yōu)先級函數(shù)在Πi區(qū)域(即第i個MW-Voronoi區(qū)域)上的積分被稱為第i個區(qū)域的加權(quán)值,用α∏i表示,即

(3)

定義4.在區(qū)域Πi中傳感器節(jié)點(diǎn)Si的感知半徑為ri,q是該區(qū)域中的任意一點(diǎn).以q為圓心ri為半徑的圓與區(qū)域Πi的交集被稱為q點(diǎn)的覆蓋面積,記做覆蓋面積w.r.t.q.同理,覆蓋面積w.r.t.傳感器Si的位置,則被稱為該傳感器節(jié)點(diǎn)Si的局部覆蓋面積.

定義5.在區(qū)域Πi中傳感器節(jié)點(diǎn)Si的感知半徑為ri,x是該區(qū)域中的任意一點(diǎn).優(yōu)先級函數(shù)在該區(qū)域的覆蓋面積w.r.t.x上的積分被稱為第i個區(qū)域的加權(quán)覆蓋面積,用數(shù)學(xué)公式表示為

(4)

其中C(x,ri)是以x為圓心,ri為半徑的圓.

(5)

同理,在某個MW-Voronoi區(qū)域中,令pi為傳感器節(jié)點(diǎn)Si的位置,那么傳感器節(jié)點(diǎn)Si的加權(quán)覆蓋面積w.r.t.pi和加權(quán)空洞面積w.r.t.pi分別被稱為傳感器節(jié)點(diǎn)Si的局部加權(quán)覆蓋面積和傳感器節(jié)點(diǎn)Si的局部加權(quán)空洞面積.優(yōu)先級函數(shù)在區(qū)域中所有覆蓋區(qū)域和非覆蓋區(qū)域上的積分分別稱為總加權(quán)覆蓋面積和總加權(quán)空洞面積.

3 OSC方法

本節(jié)提出了一種傳感器節(jié)點(diǎn)部署算法,該算法能使傳感器到達(dá)最佳部署位置;隨后給出了部署協(xié)議,遵循該協(xié)議能使網(wǎng)絡(luò)的整體加權(quán)覆蓋面積最大,最后給出該部署協(xié)議的正確性分析.

3.1 CMWV算法

給出如下公式:

(6)

C∏i為第i個傳感器節(jié)點(diǎn)在第i個MW-Voronoi區(qū)域中修復(fù)覆蓋空洞的最佳部署位置,該算法為CMWV算法,其中α∏i為定義3中的第i個區(qū)域的加權(quán)值.

CMWV算法能使傳感器節(jié)點(diǎn)不斷調(diào)整自身位置到達(dá)最佳部署位置,從而使得具有不同覆蓋優(yōu)先級的異構(gòu)WSN的局部加權(quán)覆蓋面積最大.

3.2 部署協(xié)議

在部署協(xié)議中,CMWV算法會一直迭代直到達(dá)到協(xié)議終止條件后停止運(yùn)行,該算法每次迭代都要經(jīng)過五個階段.

第一階段,每個傳感器節(jié)點(diǎn)都要向其鄰居傳感器節(jié)點(diǎn)廣播自己的位置和感知半徑信息,同時接收來自它們的位置和感知半徑的信息,隨后每個傳感器節(jié)點(diǎn)根據(jù)這些信息建立自己的MW-Voronoi區(qū)域.

第二階段,按照本節(jié)所提出的CMWV算法,每個傳感器節(jié)點(diǎn)利用所獲得的信息可計算出自己所在區(qū)域中的候選位置.

第五階段,當(dāng)每個傳感器節(jié)點(diǎn)的局部加權(quán)覆蓋面積增加都不超過預(yù)設(shè)值時,算法停止.

算法運(yùn)行停止后,可獲得最大整體加權(quán)覆蓋面積.

3.3 部署協(xié)議的正確性分析

在無線傳感器網(wǎng)絡(luò)覆蓋空洞修復(fù)過程中,部署協(xié)議的關(guān)鍵就是每個傳感器節(jié)點(diǎn)僅在一種情況下移動,這種情況就是傳感器節(jié)點(diǎn)候選位置的局部加權(quán)覆蓋面積在相應(yīng)MW-Voronoi區(qū)域中增加.由此推論,網(wǎng)絡(luò)的總加權(quán)覆蓋面積也會增加,理論及證明如下.

(7)

(8)

(9)

(10)

從公式(7),(10)可知,β′>β.

4 仿真實(shí)驗(yàn)

鑒于WSN中覆蓋空洞修復(fù)問題的復(fù)雜性,不同的覆蓋空洞修復(fù)方法的有效性的評估和對比主要通過仿真軟件進(jìn)行的.因?yàn)镸ATLAB仿真軟件的實(shí)時性控制和精確度較高,能更好地模擬真實(shí)環(huán)境,本文擬在64位Windows系統(tǒng)上的MATLAB軟件上進(jìn)行仿真.在實(shí)驗(yàn)中,將本文中的OSC方法與文獻(xiàn)[15]中的MWP方法進(jìn)行比較.在MWP方法中,每個傳感器節(jié)點(diǎn)找到相應(yīng)子區(qū)域的最大加權(quán)頂點(diǎn)位置,并且不斷向此位置點(diǎn)移動直到此位置點(diǎn)被覆蓋為止.實(shí)驗(yàn)從加權(quán)覆蓋率和運(yùn)行時間兩方面對兩種方法進(jìn)行對比.實(shí)驗(yàn)時,為了排除偶然性因素的影響使結(jié)論更具有普遍意義,需要設(shè)置重復(fù)組求其平均值,以下實(shí)驗(yàn)中涉及的所有數(shù)據(jù)結(jié)果都是50次仿真實(shí)驗(yàn)的平均值.

4.1 實(shí)驗(yàn)設(shè)置

在監(jiān)測區(qū)域A上隨機(jī)部署n個感知半徑為ri的傳感器節(jié)點(diǎn),傳感器節(jié)點(diǎn)的感知半徑不一定相同,其中區(qū)域A為一個面積為50m*50m的二維平面區(qū)域.用給定的優(yōu)先級函數(shù)φ(q)表示監(jiān)測區(qū)域A中不同位置被覆蓋的重要性,規(guī)定網(wǎng)絡(luò)中通信半徑為20m.在MATLAB仿真實(shí)驗(yàn)中,當(dāng)給定的傳感器節(jié)點(diǎn)的局部加權(quán)覆蓋面積增加值都不超過1%時算法停止,否則繼續(xù)執(zhí)行算法.

4.2 運(yùn)行實(shí)例

初始設(shè)置如下:監(jiān)測區(qū)域中隨機(jī)部署著27個傳感器節(jié)點(diǎn):15個感知半徑為1m,6個感知半徑為5/6m的,3個感知半徑為7/6m的,3個感知半徑為1.5m的.給定優(yōu)先級函數(shù)為φ1(q)=exp(-k*[(xq-25)2+(yq-25)2]),k=0.4,其中xq和yq分別是q點(diǎn)的橫坐標(biāo)和縱坐標(biāo).圖3是該方法的運(yùn)行實(shí)例,圖中給出了三個特定時間點(diǎn)的圖像,區(qū)域中各個位置的覆蓋優(yōu)先級用灰度來表示,且該點(diǎn)的灰度和其自身的覆蓋優(yōu)先級成正比,黑色代表最高優(yōu)先級.圖中黑點(diǎn)表示傳感器節(jié)點(diǎn)的位置,實(shí)心灰色圓形表示傳感器節(jié)點(diǎn)的感知范圍,圖中其余曲線代表MW-Voronoi子區(qū)域的邊界.修復(fù)覆蓋空洞過程中,覆蓋優(yōu)先級高的位置需要優(yōu)先被覆蓋.從圖3(c)看出算法停止后傳感器節(jié)點(diǎn)聚集在覆蓋優(yōu)先級高的區(qū)域,由此可知OSC方法對修復(fù)覆蓋空洞有作用.

圖3 OSC方法的運(yùn)行實(shí)例

4.3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)1.本實(shí)驗(yàn)的初始設(shè)置與運(yùn)行實(shí)例中的完全相同.圖4描繪了每個周期算法執(zhí)行后的加權(quán)覆蓋率,圖中數(shù)據(jù)顯示兩種算法都進(jìn)行一次迭代后,OSC方法的加權(quán)覆蓋率可達(dá)到40%,MWP方法的加權(quán)覆蓋率在25%左右;隨著迭代周期的增加OSC方法所獲得加權(quán)覆蓋率都要比MWP方法高,且運(yùn)用OSC方法獲得的最終加權(quán)覆蓋率要遠(yuǎn)遠(yuǎn)大于運(yùn)用MWP方法達(dá)到的最終加權(quán)覆蓋率.

圖4 每個周期的覆蓋率

實(shí)驗(yàn)2.運(yùn)行時間是評估覆蓋空洞修復(fù)方法優(yōu)劣性的重要標(biāo)準(zhǔn)之一.鑒于不同算法每個周期中傳感器節(jié)點(diǎn)的部署時間相差不了多少,因此達(dá)到截止條件時算法的運(yùn)行周期數(shù)可作為評估運(yùn)行時間的標(biāo)準(zhǔn).給出四個場景,都用實(shí)驗(yàn)1中的優(yōu)先級函數(shù)φ1(q).第一個場景中隨機(jī)部署9個傳感器節(jié)點(diǎn):5個感知半徑為1m,2個感知半徑為5/6m,1個感知半徑為7/6m,1個感知半徑為1.5m.第二個場景中不同感知半徑的傳感器節(jié)點(diǎn)個數(shù)變?yōu)閳鼍耙恢械膬杀?即有10個感知半徑為1m,4個感知半徑為5/6m,2個感知半徑為7/6m,2個感知半徑為1.5m.類似地,場景三中不同感知半徑的傳感器節(jié)點(diǎn)數(shù)目為場景一中的3倍,場景四中不同感知半徑的傳感器節(jié)點(diǎn)數(shù)目為場景一中的4倍.圖5描述了在達(dá)到截止條件時每個算法的運(yùn)行周期數(shù)都隨傳感器節(jié)點(diǎn)數(shù)目的增多而減少.這是因?yàn)楫?dāng)監(jiān)測區(qū)域存在大量傳感器節(jié)點(diǎn)時,劃分后的部分子區(qū)域范圍小于傳感器節(jié)點(diǎn)的感知范圍,傳感器節(jié)點(diǎn)覆蓋了大部分子區(qū)域,算法達(dá)到截止條件的時間更快.圖示OSC方法的運(yùn)行周期數(shù)要小于MWP方法,因此OSC方法運(yùn)行時間更短.

圖5 滿足不同傳感器節(jié)點(diǎn)數(shù)目達(dá)到截止條件時需要的周期數(shù)

實(shí)驗(yàn)3.實(shí)驗(yàn)1優(yōu)先級函數(shù)的至高點(diǎn)僅有一個,但現(xiàn)實(shí)中可能會出現(xiàn)多個至高點(diǎn)同時存在的情況.為進(jìn)一步比較兩種算法,實(shí)驗(yàn)設(shè)置與實(shí)驗(yàn)1相同,只是優(yōu)先級函數(shù)改變?yōu)?/p>

φ2(q)=exp(-k*[(xq-10)2+(yq-40)2])+exp(-k*[(xq-25)2+(yq-7.5)2])+exp(-k*[(xq-37.5)2+(yq-32.5)2])

其中k=0.4,圖6描繪了在算法執(zhí)行完每個周期時,兩種算法的加權(quán)覆蓋率.從圖中可以看出,OSC方法所達(dá)到的加權(quán)覆蓋率都要比MWP方法的加權(quán)覆蓋率要高.說明在優(yōu)先級函數(shù)具有多個至高點(diǎn)時,OSC方法比MWP方法加權(quán)覆蓋率高,可得OSC方法與優(yōu)先級函數(shù)的至高點(diǎn)個數(shù)無關(guān).

實(shí)驗(yàn)4.本實(shí)驗(yàn)應(yīng)用優(yōu)先級函數(shù)φ1(q),其他設(shè)置與實(shí)驗(yàn)1相同,通過討論優(yōu)先級函數(shù)的平滑程度對網(wǎng)絡(luò)加權(quán)覆蓋率的影響來分析所提算法的性能.圖7描述了不同k值時的最終加權(quán)覆蓋率.

圖6 每個周期的加權(quán)覆蓋率

從圖7可以看出,在優(yōu)先級函數(shù)比較平滑時,由MWP方法所得到的加權(quán)覆蓋率要高.隨著優(yōu)先級函數(shù)變得尖銳,即不同位置被修復(fù)的重要程度不同時OSC方法比MWP方法更占優(yōu)勢.可得OSC方法的性能與覆蓋優(yōu)先級函數(shù)的平滑程度有關(guān),且更適合優(yōu)先級函數(shù)非平滑的情況.

圖7 場景一中k值不同時的最終加權(quán)覆蓋面積

通過上述實(shí)驗(yàn)設(shè)置和實(shí)驗(yàn)結(jié)果分析可以看出,我們所提出的OSC方法能夠在異構(gòu)和優(yōu)先級兩種實(shí)際條件約束下,從覆蓋率、效率兩個評價指標(biāo)上優(yōu)于對比算法MWP,即OSC方法的約束條件更加非理想化,更加接近于實(shí)際應(yīng)用環(huán)境,故其在實(shí)際環(huán)境中的適用性更占優(yōu)勢.

5 結(jié)束語

WSN中覆蓋空洞修復(fù)問題一直是該領(lǐng)域的熱點(diǎn),覆蓋率對網(wǎng)絡(luò)的服務(wù)質(zhì)量有著直接影響,所以提高覆蓋率是覆蓋空洞修復(fù)中的重要內(nèi)容.針對具有覆蓋優(yōu)先級的異構(gòu)WSN中覆蓋空洞的修復(fù)問題,提出了最佳傳感器節(jié)點(diǎn)配置的方法.該方法采用MW-Voronoi圖理論對監(jiān)測區(qū)域的劃分,運(yùn)用CMWV算法使傳感器節(jié)點(diǎn)不斷調(diào)整位置到達(dá)最佳部署位置,此時無線傳感器網(wǎng)絡(luò)的整體加權(quán)覆蓋面積最大.實(shí)驗(yàn)表明,在不同覆蓋優(yōu)先級及不同網(wǎng)絡(luò)規(guī)模下,OSC方法比MWP方法不僅在加權(quán)覆蓋率至少提高10%,且減少了空洞修復(fù)時間;特殊情況下,在網(wǎng)絡(luò)不同位置的覆蓋優(yōu)先級(即重要性)幾乎相同時,MWP方法效果更好一些,但是在實(shí)際應(yīng)用中不同位置被覆蓋的重要性不可能完全相同.因此在修復(fù)覆蓋空洞的實(shí)際應(yīng)用中OSC方法適用性更強(qiáng).本文的下一步工作重點(diǎn)是研究具有覆蓋優(yōu)先級的異構(gòu)WSN中存在障礙物時的覆蓋空洞的修復(fù)問題.