非并行二分法的覆蓋空洞修復(fù)算法

韓雨澇

攀枝花學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，四川 攀枝花617000

1 引言

網(wǎng)絡(luò)覆蓋服務(wù)質(zhì)量是度量無(wú)線(xiàn)傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量重要性能指標(biāo)之一[1-2]。節(jié)點(diǎn)對(duì)監(jiān)測(cè)區(qū)域的不充分的感知表現(xiàn)為網(wǎng)絡(luò)中節(jié)點(diǎn)分布不均勻，存在未被任何節(jié)點(diǎn)感知范圍覆蓋的區(qū)域，該區(qū)域稱(chēng)為覆蓋空洞（Coverage Hole，CH）[3-4]。覆蓋空洞邊緣區(qū)域的節(jié)點(diǎn)因過(guò)度承擔(dān)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)過(guò)早死亡，加大了覆蓋空洞的面積[5]。文獻(xiàn)[6]提出覆蓋空洞修復(fù)算法，向三角形網(wǎng)格中添加移動(dòng)節(jié)點(diǎn)使目標(biāo)區(qū)域完全覆蓋。文獻(xiàn)[7]提出分布式空洞修復(fù)算法HEAL，采用基于分布式虛擬力的覆蓋空洞修復(fù)方法，只有位于距離覆蓋空洞適當(dāng)距離的節(jié)點(diǎn)才會(huì)參與空洞修復(fù)。文獻(xiàn)[8]提出不需要節(jié)點(diǎn)地理位置信息的覆蓋空洞修復(fù)算法CHH，通過(guò)定位的方法計(jì)算節(jié)點(diǎn)之間距離以及到覆蓋空洞邊界節(jié)點(diǎn)距離，但在節(jié)點(diǎn)測(cè)距誤差較大的情況下，覆蓋空洞修復(fù)率低，且該算法只能完成閉合覆蓋空洞的修復(fù)。文獻(xiàn)[9]提出了一種覆蓋空洞檢測(cè)和修復(fù)算法，可以完整修復(fù)網(wǎng)絡(luò)中任意覆蓋空洞?；旌鲜絺鞲衅骶W(wǎng)絡(luò)[10]是在靜態(tài)網(wǎng)絡(luò)基礎(chǔ)上，部署少量移動(dòng)節(jié)點(diǎn)作為輔助節(jié)點(diǎn)。文獻(xiàn)[11]針對(duì)混合式無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)的問(wèn)題，提出移動(dòng)節(jié)點(diǎn)的路徑規(guī)劃算法，網(wǎng)絡(luò)空洞修復(fù)具有最小平均檢測(cè)延遲和最大覆蓋率。文獻(xiàn)[12]提出的Center算法通過(guò)估算覆蓋空洞的面積，結(jié)合覆蓋范圍冗余度、節(jié)點(diǎn)剩余能量以及移動(dòng)距離參數(shù)確定移動(dòng)節(jié)點(diǎn)完成空洞修復(fù)。文獻(xiàn)[13]提出未完全修復(fù)的HPA覆蓋空洞修復(fù)算法，將兩個(gè)相鄰未完全覆蓋交點(diǎn)連線(xiàn)的中垂線(xiàn)上的點(diǎn)作為移動(dòng)節(jié)點(diǎn)的修復(fù)目標(biāo)位置。上述方法存在的問(wèn)題是空洞修復(fù)效率不高，存在空洞修復(fù)冗余度高的問(wèn)題，且大多不能實(shí)現(xiàn)覆蓋空洞的完全修復(fù)。

考慮到混合式WSN網(wǎng)絡(luò)模型有網(wǎng)絡(luò)成本低和節(jié)點(diǎn)移動(dòng)靈活的特點(diǎn)。本文在混合傳感器網(wǎng)絡(luò)模型下，提出基于非并行二分法的覆蓋空洞修復(fù)算法CHRND（Coverage Hole Repair algorithm based on Non-parallel Dichotomy），以非并行方式選擇具有劣弧的空洞邊界節(jié)點(diǎn)作為覆蓋空洞修復(fù)的驅(qū)動(dòng)節(jié)點(diǎn)，通過(guò)弧二分法確定移動(dòng)節(jié)點(diǎn)的最佳目標(biāo)位置，能以較少數(shù)量的移動(dòng)節(jié)點(diǎn)和較低覆蓋冗余實(shí)現(xiàn)覆蓋空洞的完全修復(fù)。

2 網(wǎng)絡(luò)模型

傳感器節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域隨機(jī)部署自組織構(gòu)成網(wǎng)絡(luò)表示為G=(V,E),V代表節(jié)點(diǎn)集合，包括移動(dòng)節(jié)點(diǎn)和靜態(tài)節(jié)點(diǎn)；E代表無(wú)線(xiàn)鏈路集合。網(wǎng)絡(luò)中覆蓋空洞修復(fù)由移動(dòng)節(jié)點(diǎn)的位置遷移完成。節(jié)點(diǎn)位置信息通過(guò)裝載GPS定位設(shè)備或已有的網(wǎng)絡(luò)定位算法[14]獲取。網(wǎng)絡(luò)中節(jié)點(diǎn)的感知范圍和通信范圍同構(gòu)，使用簡(jiǎn)單圓盤(pán)模型[15]，感知半徑和通信半徑分別記為RG和RT。本文基于以下定義：

定義1（空洞邊界節(jié)點(diǎn)（Hole Boundary Node，HBN））當(dāng)節(jié)點(diǎn)Ni存在未完全覆蓋交點(diǎn)P，則定義Ni為HBN節(jié)點(diǎn)。

定義2（驅(qū)動(dòng)節(jié)點(diǎn)）在組成覆蓋空洞的邊界節(jié)點(diǎn)集合中，用于確定覆蓋空洞修復(fù)移動(dòng)節(jié)點(diǎn)以及最佳目標(biāo)位置的節(jié)點(diǎn)稱(chēng)為驅(qū)動(dòng)節(jié)點(diǎn)。

定義3（空洞?。┟總€(gè)HBN節(jié)點(diǎn)的感知圓盤(pán)和覆蓋空洞鄰接的弧段，稱(chēng)為該HBN節(jié)點(diǎn)相對(duì)于當(dāng)前覆蓋空洞的空洞弧?；〉幕《刃∮?80°，稱(chēng)為空洞劣弧，否則稱(chēng)為空洞優(yōu)弧。

3 CHRND算法設(shè)計(jì)

3.1 空洞修復(fù)驅(qū)動(dòng)節(jié)點(diǎn)確定原則

空洞修復(fù)由驅(qū)動(dòng)節(jié)點(diǎn)發(fā)起，應(yīng)遵循以下原則。

原則1空洞修復(fù)應(yīng)至少保證所選驅(qū)動(dòng)節(jié)點(diǎn)的空洞弧能夠被完全覆蓋。

由于移動(dòng)節(jié)點(diǎn)的覆蓋圓盤(pán)無(wú)法對(duì)空洞優(yōu)弧完全覆蓋，故選擇的HBN節(jié)點(diǎn)對(duì)應(yīng)的空洞弧應(yīng)為劣弧。根據(jù)以下定理1：當(dāng)覆蓋空洞未被修復(fù)，必然存在空洞劣弧，使得算法能夠繼續(xù)修復(fù)空洞。另外，在空洞修復(fù)過(guò)程中，對(duì)于空洞優(yōu)弧，必然存在移動(dòng)節(jié)點(diǎn)的引入將其轉(zhuǎn)變?yōu)榱踊?，使得算法繼續(xù)進(jìn)行。

原則2在覆蓋空洞修復(fù)過(guò)程中，移動(dòng)節(jié)點(diǎn)的引入應(yīng)避免覆蓋空洞被分割。

考慮覆蓋空洞分割導(dǎo)致空洞數(shù)量增加，空洞碎片面積可能極小，造成大量空洞碎片的產(chǎn)生。為了滿(mǎn)足完全覆蓋服務(wù)質(zhì)量的要求，大量移動(dòng)節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)成本提高，而部分區(qū)域又存在冗余覆蓋，極大地浪費(fèi)了節(jié)點(diǎn)資源。如果隨機(jī)選擇的HBN節(jié)點(diǎn)導(dǎo)致空洞分割，算法需重新選擇HBN節(jié)點(diǎn)嘗試覆蓋空洞修復(fù)，直至所選HBN節(jié)點(diǎn)不產(chǎn)生空洞分割。

定理1在覆蓋空洞修復(fù)過(guò)程中，總能在組成覆蓋空洞的空洞弧集合中找到空洞劣弧，使得算法能夠繼續(xù)修復(fù)當(dāng)前覆蓋空洞。

證明 使用反證法，假設(shè)移動(dòng)節(jié)點(diǎn)在覆蓋空洞修復(fù)過(guò)程中，未能夠找到滿(mǎn)足條件的空洞劣弧，即全部空洞弧都為空洞優(yōu)弧。連接未完全覆蓋交點(diǎn)構(gòu)成圖1所示五邊形區(qū)域。由于全部弧均為優(yōu)弧，則該五邊形的每個(gè)內(nèi)角至少為180°，內(nèi)角和至少為900°，這與公式（1）計(jì)算的五邊形內(nèi)角和540°相矛盾，故問(wèn)題得以證明。

圖1 覆蓋空洞劣弧確定

3.2 基于二分法的移動(dòng)節(jié)點(diǎn)目標(biāo)位置確定

如圖2網(wǎng)絡(luò)覆蓋空洞區(qū)域表示為A，假定節(jié)點(diǎn)N6為當(dāng)前覆蓋空洞修復(fù)的驅(qū)動(dòng)節(jié)點(diǎn)，對(duì)應(yīng)的空洞弧為弧P1P2。采用弧二分法確定移動(dòng)節(jié)點(diǎn)的位置點(diǎn)T(xt,yt)，使得移動(dòng)節(jié)點(diǎn)以T(xt,yt)為圓心的感知圓盤(pán)恰好完全覆蓋空洞弧P1P2，即點(diǎn)T(xt,yt)到空洞弧的端點(diǎn)P1和P2的距離為節(jié)點(diǎn)感知半徑RG。

圖2 最佳目標(biāo)位置點(diǎn)確定

（1）最佳目標(biāo)位置點(diǎn)確定

最佳目標(biāo)位置點(diǎn)T(xt,yt)應(yīng)位于線(xiàn)段P1P2的中垂線(xiàn)的覆蓋空洞側(cè)，且到交點(diǎn)P1和P2距離均為RG。

方程組解(xt,yt)對(duì)應(yīng)目標(biāo)點(diǎn)T到節(jié)點(diǎn)N6的距離滿(mǎn)足式（3），保證了點(diǎn)T(xt,yt)位于線(xiàn)段P1P2的中垂線(xiàn)的覆蓋空洞側(cè)。

當(dāng)移動(dòng)節(jié)點(diǎn)目標(biāo)位置偏離點(diǎn)T(xt,yt)，不能保證移動(dòng)節(jié)點(diǎn)的引入對(duì)空洞弧P1P2的完全覆蓋，且有可能導(dǎo)致不必要的空洞分割；目標(biāo)位置點(diǎn)沿P1P2的中垂線(xiàn)向下偏移雖實(shí)現(xiàn)了空洞弧P1P2的完全覆蓋，但減少了移動(dòng)節(jié)點(diǎn)有效修復(fù)面積，增加了修復(fù)的覆蓋冗余。綜上所述，點(diǎn)T(xt,yt)為移動(dòng)節(jié)點(diǎn)的最佳目標(biāo)位置。

（2）覆蓋空洞分割分析

考慮到覆蓋空洞分割造成空洞數(shù)量的增加，產(chǎn)生大量空洞碎片，導(dǎo)致移動(dòng)節(jié)點(diǎn)數(shù)量增加以及覆蓋冗余問(wèn)題的出現(xiàn)。為此，在移動(dòng)節(jié)點(diǎn)遷徙之前檢查在位置點(diǎn)T(xt,yt)的移動(dòng)節(jié)點(diǎn)引入是否會(huì)導(dǎo)致空洞分割。

當(dāng)節(jié)點(diǎn)Ny在目標(biāo)位置T(xt,yt)的引入和構(gòu)成覆蓋空洞A的HBN節(jié)點(diǎn)序列集合HA中任意節(jié)點(diǎn)Ni滿(mǎn)足式（4）條件，則覆蓋圓盤(pán)之間存在覆蓋交點(diǎn)。

解方程組（5）得到對(duì)應(yīng)交點(diǎn)記為Pj

當(dāng)HA中不存在其他節(jié)點(diǎn)Nk和Pj滿(mǎn)足式（6）條件，則定義交點(diǎn)Pj為未完全覆蓋交點(diǎn)。

最后，如果移動(dòng)節(jié)點(diǎn)Ny的引入產(chǎn)生的未完全覆蓋交點(diǎn)的數(shù)量m不大于2，根據(jù)定理2可知，移動(dòng)節(jié)點(diǎn)在目標(biāo)位置點(diǎn)T(xt,yt)的引入不會(huì)導(dǎo)致覆蓋空洞分割。

定理2在覆蓋空洞修復(fù)過(guò)程中，當(dāng)移動(dòng)節(jié)點(diǎn)的感知圓盤(pán)與組成覆蓋空洞A的集合HA所有HBN節(jié)點(diǎn)的感知圓盤(pán)的未完全覆蓋交點(diǎn)不大于2個(gè)，則覆蓋空洞不會(huì)被分割。

證明 采用反證法，假設(shè)移動(dòng)節(jié)點(diǎn)引入產(chǎn)生的未完全覆蓋交點(diǎn)不大于2個(gè)，導(dǎo)致覆蓋空洞被分割，則至少產(chǎn)生兩個(gè)覆蓋空洞區(qū)域。圖3（a）所示的每個(gè)分割的覆蓋空洞存在2個(gè)未完全覆蓋交點(diǎn)，特殊情況如圖3（b）所示兩個(gè)未完全覆蓋交點(diǎn)為同一交點(diǎn)?？傊?，空洞分割產(chǎn)生的未完全覆蓋交點(diǎn)大于等于3個(gè)，這與假設(shè)矛盾，故得以證明。

3.3 基于最小距離的移動(dòng)修復(fù)節(jié)點(diǎn)確定

（1）k跳范圍移動(dòng)節(jié)點(diǎn)獲取

網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)向HBN節(jié)點(diǎn)廣播移動(dòng)節(jié)點(diǎn)通知（Mobile Node Notification，MNN）消息，該消息包含了移動(dòng)節(jié)點(diǎn)ID、位置和消息生命期k。HBN節(jié)點(diǎn)收到MNN消息，存儲(chǔ)移動(dòng)節(jié)點(diǎn)的ID和位置信息，當(dāng)參數(shù)k減1不為0時(shí)，繼續(xù)廣播消息，直到k減1為0，消息不再?gòu)V播。最終，每個(gè)HBN節(jié)點(diǎn)獲得了k跳內(nèi)范圍內(nèi)移動(dòng)節(jié)點(diǎn)信息。將HBN節(jié)點(diǎn)Nk的移動(dòng)節(jié)點(diǎn)集合記為Yk。FCN節(jié)點(diǎn)收到MNN消息，無(wú)需存儲(chǔ)移動(dòng)節(jié)點(diǎn)信息，僅當(dāng)k-1不為0，繼續(xù)廣播該消息。

圖3 覆蓋空洞分割交點(diǎn)數(shù)量

（2）基于最小距離的移動(dòng)修復(fù)節(jié)點(diǎn)確定

Nk使用最小距離法在驅(qū)動(dòng)節(jié)點(diǎn)Nk的移動(dòng)節(jié)點(diǎn)集合Yk中，選取距離目標(biāo)點(diǎn)T(xt,yt)位置最近的移動(dòng)節(jié)點(diǎn)，作為當(dāng)前修復(fù)節(jié)點(diǎn)，記為Nr。

之后，節(jié)點(diǎn)Nk向移動(dòng)節(jié)點(diǎn)Nr發(fā)送移動(dòng)節(jié)點(diǎn)確認(rèn)消息（Mobile Node Confirmation），Nr收到消息后廣播移動(dòng)節(jié)點(diǎn)刪除消息（Mobile Node Cancellation，MNC），k跳內(nèi)的HBN節(jié)點(diǎn)接收到MNC消息，刪除移動(dòng)節(jié)點(diǎn)Nr的信息。最后，移動(dòng)節(jié)點(diǎn)Nr遷移到位置點(diǎn)T(xt,yt)，完成此次覆蓋空洞的修復(fù)。

3.4 非并行方式的覆蓋空洞修復(fù)

在覆蓋空洞修復(fù)過(guò)程中，移動(dòng)節(jié)點(diǎn)采用并行方式修復(fù)覆蓋空洞，雖能快速完成覆蓋空洞的修復(fù)，但冗余問(wèn)題嚴(yán)重。如圖4（a）同時(shí)選擇N1和N2作為驅(qū)動(dòng)節(jié)點(diǎn)，分別獨(dú)立確定移動(dòng)節(jié)點(diǎn)目標(biāo)位置L1和L2，并發(fā)在L1和L2位置修復(fù)覆蓋空洞，覆蓋空洞修復(fù)冗余嚴(yán)重。相比之下，采用圖4（b）的非并行方式的覆蓋空洞修復(fù)策略，驅(qū)動(dòng)節(jié)點(diǎn)N1確定移動(dòng)節(jié)點(diǎn)的目標(biāo)位置L1，移動(dòng)節(jié)點(diǎn)首先在L1位置修復(fù)覆蓋空洞。然后，驅(qū)動(dòng)節(jié)點(diǎn)N2對(duì)當(dāng)自己新的空洞弧使用二分法確定目標(biāo)位置L2，并在該位置修復(fù)覆蓋空洞，有效地提高了節(jié)點(diǎn)利用率，覆蓋冗余明顯降低。最后，在移動(dòng)節(jié)點(diǎn)引入使得空洞不被分割基礎(chǔ)上，定理3保證了按照該非并行二分法方式能夠?qū)崿F(xiàn)覆蓋空洞完全修復(fù)。

定理3移動(dòng)節(jié)點(diǎn)引入使得空洞不被分割基礎(chǔ)上，采用非并行二分法能夠保證覆蓋空洞被完全修復(fù)。

圖4 覆蓋空洞修復(fù)方式比較

證明 在移動(dòng)節(jié)點(diǎn)引入使得空洞不被分割的基礎(chǔ)上，由于每個(gè)移動(dòng)節(jié)點(diǎn)對(duì)覆蓋空洞的修復(fù)最少能夠消除2個(gè)未完全覆蓋交點(diǎn)，根據(jù)定理2，每次空洞修復(fù)最多引入2個(gè)未完全覆蓋交點(diǎn)。如在圖5所示的覆蓋空洞區(qū)域，移動(dòng)節(jié)點(diǎn)的引入消除了P1到P4共4個(gè)未完全覆蓋交點(diǎn)，引入了P5和P6共2個(gè)未完全覆蓋交點(diǎn)。定理1保證了算法能以非并行方式對(duì)覆蓋空洞連續(xù)修復(fù)，隨著移動(dòng)節(jié)點(diǎn)的持續(xù)引入，覆蓋空洞區(qū)域面積逐步減少，未完全覆蓋交點(diǎn)數(shù)量減少，當(dāng)未完全覆蓋交點(diǎn)數(shù)量為0，則覆蓋空洞已被完全修復(fù)。

圖5 覆蓋空洞完全修復(fù)

算法1 CHRND空洞修復(fù)算法

0.whileHBN節(jié)點(diǎn)集合HA不為空

1.任選空洞弧為劣弧的HBN節(jié)點(diǎn)N1；

2.Nj按照二分法確定移動(dòng)節(jié)點(diǎn)的目標(biāo)位置Posj；

3.if Posj位置移動(dòng)節(jié)點(diǎn)引入導(dǎo)致空洞分割then

4.return 1；

5.end if

6.Nj用最小距離法確定到Posj的最近移動(dòng)節(jié)點(diǎn)Nj；

7.Nj沿直線(xiàn)移動(dòng)到位置Posj；

8.集合HA刪除Nj引入已完全覆蓋的HBN節(jié)點(diǎn)；

9.if HBN節(jié)點(diǎn)序列集合HA不為空then

10.增加移動(dòng)節(jié)點(diǎn)Nj到集合H；

11.end if

12.end while

4 CHRND算法仿真與分析

選取Matlab7.0作為仿真實(shí)驗(yàn)平臺(tái)，無(wú)線(xiàn)傳感器節(jié)點(diǎn)在400 m×100 m矩形區(qū)域內(nèi)隨機(jī)部署，靜態(tài)節(jié)點(diǎn)數(shù)量為400個(gè)，節(jié)點(diǎn)感知半徑為RG=10 m，通信半徑為RT=20 m，靜態(tài)節(jié)點(diǎn)能量Estatic_init=100 J，移動(dòng)節(jié)點(diǎn)能量Emobile_init=200J，假定發(fā)送和接收一個(gè)消息能耗均為0.2 J，節(jié)點(diǎn)在移動(dòng)過(guò)程中能量消耗為1 J/m。

4.1 CHRND算法性能分析

假定覆蓋空洞完全修復(fù)需要N個(gè)移動(dòng)節(jié)點(diǎn)。定義覆蓋空洞完全修復(fù)對(duì)應(yīng)的覆蓋冗余度為節(jié)點(diǎn)覆蓋總面積之和減去覆蓋空洞面積的值與覆蓋空洞面積的比值。

以下比較了CHRND算法與采用并行方式修復(fù)策略在不同覆蓋空洞面積和不同節(jié)點(diǎn)感知半徑下完成空洞完全修復(fù)產(chǎn)生的覆蓋冗余度。

（1）不同空洞面積完全修復(fù)對(duì)應(yīng)的覆蓋冗余度

圖6給出了在RG=10 m前提下的覆蓋空洞面積與空洞修復(fù)覆蓋冗余度關(guān)系?？梢钥闯?，CHRND算法覆蓋冗余度在0.152～0.354之間，當(dāng)空洞面積區(qū)域較小，覆蓋冗余度較大，隨著空洞面積增大，覆蓋冗余度降低。這是因?yàn)榭斩疵娣e較大，降低了空洞修復(fù)產(chǎn)生碎片的機(jī)會(huì)，也降低了修復(fù)節(jié)點(diǎn)與其他節(jié)點(diǎn)覆蓋重疊的可能。另外，相對(duì)于采用并行方式修復(fù)策略，CHRND算法的空洞修復(fù)覆蓋冗余度顯著降低，能以較少數(shù)量移動(dòng)節(jié)點(diǎn)實(shí)現(xiàn)空洞區(qū)域完全修復(fù)。

圖6 覆蓋空洞面積與覆蓋冗余度

（2）不同節(jié)點(diǎn)感知半徑完全修復(fù)對(duì)應(yīng)的冗余度

圖7給出了在空洞面積S=5 000 m2前提下的移動(dòng)節(jié)點(diǎn)感知半徑與空洞修復(fù)覆蓋冗余度關(guān)系?？梢钥闯觯?dāng)移動(dòng)節(jié)點(diǎn)感知半徑較小，覆蓋冗余較小，隨著移動(dòng)節(jié)點(diǎn)感知半徑增大，空洞修復(fù)覆蓋冗余度顯著增加。這是因?yàn)楫?dāng)節(jié)點(diǎn)感知半徑增大，使得每個(gè)修復(fù)節(jié)點(diǎn)空洞修復(fù)利用率降低。此外，同圖1結(jié)論一致，圖7也驗(yàn)證了相比于并行修復(fù)策略，CHRND算法采用非并行方法能顯著降低空洞修復(fù)的覆蓋冗余度。

4.2 不同算法的比較

圖7 移動(dòng)節(jié)點(diǎn)感知半徑與覆蓋冗余度

仿真實(shí)驗(yàn)分別從覆蓋空洞修復(fù)所需移動(dòng)節(jié)點(diǎn)數(shù)量、覆蓋空洞修復(fù)率以及移動(dòng)節(jié)點(diǎn)平均移動(dòng)距離三個(gè)方面，比較了本文CHRND算法與現(xiàn)有覆蓋空洞修復(fù)算法Center[12]和HPA[13]。

（1）覆蓋空洞區(qū)域面積與移動(dòng)節(jié)點(diǎn)數(shù)量關(guān)系

移動(dòng)節(jié)點(diǎn)數(shù)量為200個(gè)，圖8給出三種算法在不同覆蓋空洞面積下所需移動(dòng)節(jié)點(diǎn)的數(shù)量，可以看出，隨著覆蓋空洞面積的增加，三種算法所需的移動(dòng)節(jié)點(diǎn)數(shù)量均增加。CHRND算法所需移動(dòng)節(jié)點(diǎn)數(shù)量低于Center算法，這是因?yàn)镃HRND算法使用非并行二分法確定移動(dòng)節(jié)點(diǎn)最佳位置，避免了并發(fā)修復(fù)產(chǎn)生的過(guò)度冗余。另外，CHRND算法移動(dòng)節(jié)點(diǎn)數(shù)量要高于HPA算法，這是因?yàn)镠PA算法不要求空洞完全修復(fù)，允許空洞碎片存在，使得每個(gè)節(jié)點(diǎn)的利用率較高，空洞修復(fù)具有較低的冗余度，而CHRND算法要求實(shí)現(xiàn)覆蓋空洞完全修復(fù)。

圖8 空洞區(qū)域面積與移動(dòng)節(jié)點(diǎn)數(shù)量

（2）網(wǎng)絡(luò)覆蓋修復(fù)率

網(wǎng)絡(luò)覆蓋修復(fù)率定義為移動(dòng)節(jié)點(diǎn)完成空洞區(qū)域的修復(fù)面積與覆蓋空洞的總面積比值。

圖9 移動(dòng)節(jié)點(diǎn)數(shù)量與空洞修復(fù)率

圖9 給出了不同移動(dòng)節(jié)點(diǎn)數(shù)量下的網(wǎng)絡(luò)覆蓋空洞修復(fù)率情況，可以看出，隨著移動(dòng)節(jié)點(diǎn)數(shù)量增多，三種算法覆蓋空洞修復(fù)率提高。當(dāng)移動(dòng)節(jié)點(diǎn)較少時(shí)，三種算法的覆蓋空洞修復(fù)率較低，而HPA算法覆蓋空洞修復(fù)率相對(duì)較高，這是因?yàn)槿N算法覆蓋空洞修復(fù)所需移動(dòng)節(jié)點(diǎn)數(shù)量均不足，而HPA算法在給定移動(dòng)節(jié)點(diǎn)數(shù)量下實(shí)現(xiàn)空洞修復(fù)最大化，并不要求空洞完全修復(fù)。隨著移動(dòng)節(jié)點(diǎn)數(shù)量增加，當(dāng)移動(dòng)節(jié)點(diǎn)比例超過(guò)29%，CHRND算法覆蓋空洞修復(fù)率可達(dá)100%。Center算法修復(fù)率低于CHRND算法，達(dá)到相同的修復(fù)率所需移動(dòng)節(jié)點(diǎn)較多，Center算法雖也可完成覆蓋空洞的完全修復(fù)，但所需移動(dòng)節(jié)點(diǎn)數(shù)量比例超過(guò)了50%。HPA算法目標(biāo)是提高節(jié)點(diǎn)使用率，因此在空洞修復(fù)過(guò)程中可能產(chǎn)生空洞碎片，增加了覆蓋所需節(jié)點(diǎn)數(shù)量。Center算法修復(fù)率低于CHRND算法，這是因?yàn)镃enter算法僅考慮HBN節(jié)點(diǎn)的一跳范圍內(nèi)移動(dòng)節(jié)點(diǎn)，使得移動(dòng)節(jié)點(diǎn)數(shù)量存在不足。

（3）移動(dòng)節(jié)點(diǎn)數(shù)量與平均移動(dòng)距離

移動(dòng)距離是影響移動(dòng)節(jié)點(diǎn)能耗的一個(gè)重要因素，與網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)的數(shù)量有關(guān)。圖10給出了覆蓋空洞面積為2 000m2下的不同移動(dòng)節(jié)點(diǎn)數(shù)量對(duì)應(yīng)的平均移動(dòng)距離?？梢钥闯?，隨著移動(dòng)節(jié)點(diǎn)數(shù)量增加，其平均移動(dòng)距離減小，這是因?yàn)橐苿?dòng)節(jié)點(diǎn)數(shù)量增加，更有利于選擇距離目標(biāo)位置更近的節(jié)點(diǎn)。進(jìn)一步發(fā)現(xiàn)，CHRND算法節(jié)點(diǎn)平均移動(dòng)距離低于其他兩種算法，這是因?yàn)镃HRND算法使用非并行二分法確定移動(dòng)節(jié)點(diǎn)的目標(biāo)位置，使用最小距離法選擇距離目標(biāo)位置最近的移動(dòng)節(jié)點(diǎn)，而HPA和Center算法移動(dòng)節(jié)點(diǎn)的目標(biāo)位置的選擇結(jié)合了節(jié)點(diǎn)能耗等多種因素，使得節(jié)點(diǎn)移動(dòng)距離較長(zhǎng)。

圖10 移動(dòng)節(jié)點(diǎn)數(shù)量與平均移動(dòng)距離

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

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋空洞影響網(wǎng)絡(luò)服務(wù)質(zhì)量性能。為此，提出了基于非并行二分法的覆蓋空洞修復(fù)算法——CHRND，移動(dòng)節(jié)點(diǎn)以非并行方式實(shí)現(xiàn)覆蓋空洞的完全修復(fù)。仿真結(jié)果顯示，CHRND算法能以較少數(shù)量的移動(dòng)節(jié)點(diǎn)實(shí)現(xiàn)覆蓋空洞的完全修復(fù)，移動(dòng)節(jié)點(diǎn)修復(fù)利用率較高，具有極少的冗余覆蓋，適用于通過(guò)一定數(shù)量的移動(dòng)節(jié)點(diǎn)要求空洞區(qū)域完全修復(fù)的應(yīng)用場(chǎng)景。