韓雨澇

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

1 引言

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

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

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

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

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

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

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

3 CHRND算法設(shè)計

3.1 空洞修復(fù)驅(qū)動節(jié)點確定原則

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

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

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

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

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

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

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

圖1 覆蓋空洞劣弧確定

3.2 基于二分法的移動節(jié)點目標位置確定

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

圖2 最佳目標位置點確定

（1）最佳目標位置點確定

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

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

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

（2）覆蓋空洞分割分析

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

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

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

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

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

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

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

3.3 基于最小距離的移動修復(fù)節(jié)點確定

（1）k跳范圍移動節(jié)點獲取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.Nj按照二分法確定移動節(jié)點的目標位置Posj；

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

4.return 1；

5.end if

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

7.Nj沿直線移動到位置Posj；

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

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

10.增加移動節(jié)點Nj到集合H；

11.end if

12.end while

4 CHRND算法仿真與分析

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

4.1 CHRND算法性能分析

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

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

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

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

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

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

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

4.2 不同算法的比較

圖7 移動節(jié)點感知半徑與覆蓋冗余度

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

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

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

圖8 空洞區(qū)域面積與移動節(jié)點數(shù)量

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

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

圖9 移動節(jié)點數(shù)量與空洞修復(fù)率

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

（3）移動節(jié)點數(shù)量與平均移動距離

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

圖10 移動節(jié)點數(shù)量與平均移動距離

5 結(jié)束語

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