非并行二分法的覆蓋空洞修復算法

韓雨澇

攀枝花學院 數學與計算機學院，四川 攀枝花617000

1 引言

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

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

2 網絡模型

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

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

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

定義3（空洞弧）每個HBN節點的感知圓盤和覆蓋空洞鄰接的弧段，稱為該HBN節點相對于當前覆蓋空洞的空洞弧。弧的弧度小于180°，稱為空洞劣弧，否則稱為空洞優弧。

3 CHRND算法設計

3.1 空洞修復驅動節點確定原則

空洞修復由驅動節點發起，應遵循以下原則。

原則1空洞修復應至少保證所選驅動節點的空洞弧能夠被完全覆蓋。

由于移動節點的覆蓋圓盤無法對空洞優弧完全覆蓋，故選擇的HBN節點對應的空洞弧應為劣弧。根據以下定理1：當覆蓋空洞未被修復，必然存在空洞劣弧，使得算法能夠繼續修復空洞。另外，在空洞修復過程中，對于空洞優弧，必然存在移動節點的引入將其轉變為劣弧，使得算法繼續進行。

原則2在覆蓋空洞修復過程中，移動節點的引入應避免覆蓋空洞被分割。

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

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

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

圖1 覆蓋空洞劣弧確定

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

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

圖2 最佳目標位置點確定

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

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

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

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

（2）覆蓋空洞分割分析

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

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

解方程組（5）得到對應交點記為Pj

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

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

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

證明 采用反證法，假設移動節點引入產生的未完全覆蓋交點不大于2個，導致覆蓋空洞被分割，則至少產生兩個覆蓋空洞區域。圖3（a）所示的每個分割的覆蓋空洞存在2個未完全覆蓋交點，特殊情況如圖3（b）所示兩個未完全覆蓋交點為同一交點。總之，空洞分割產生的未完全覆蓋交點大于等于3個，這與假設矛盾，故得以證明。

3.3 基于最小距離的移動修復節點確定

（1）k跳范圍移動節點獲取

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

圖3 覆蓋空洞分割交點數量

（2）基于最小距離的移動修復節點確定

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

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

3.4 非并行方式的覆蓋空洞修復

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

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

圖4 覆蓋空洞修復方式比較

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

圖5 覆蓋空洞完全修復

算法1 CHRND空洞修復算法

0.whileHBN節點集合HA不為空

1.任選空洞弧為劣弧的HBN節點N1；

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

3.if Posj位置移動節點引入導致空洞分割then

4.return 1；

5.end if

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

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

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

9.if HBN節點序列集合HA不為空then

10.增加移動節點Nj到集合H；

11.end if

12.end while

4 CHRND算法仿真與分析

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

4.1 CHRND算法性能分析

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

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

（1）不同空洞面積完全修復對應的覆蓋冗余度

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

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

（2）不同節點感知半徑完全修復對應的冗余度

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

4.2 不同算法的比較

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

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

（1）覆蓋空洞區域面積與移動節點數量關系

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

圖8 空洞區域面積與移動節點數量

（2）網絡覆蓋修復率

網絡覆蓋修復率定義為移動節點完成空洞區域的修復面積與覆蓋空洞的總面積比值。

圖9 移動節點數量與空洞修復率

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

（3）移動節點數量與平均移動距離

移動距離是影響移動節點能耗的一個重要因素，與網絡中移動節點的數量有關。圖10給出了覆蓋空洞面積為2 000m2下的不同移動節點數量對應的平均移動距離。可以看出，隨著移動節點數量增加，其平均移動距離減小，這是因為移動節點數量增加，更有利于選擇距離目標位置更近的節點。進一步發現，CHRND算法節點平均移動距離低于其他兩種算法，這是因為CHRND算法使用非并行二分法確定移動節點的目標位置，使用最小距離法選擇距離目標位置最近的移動節點，而HPA和Center算法移動節點的目標位置的選擇結合了節點能耗等多種因素，使得節點移動距離較長。

圖10 移動節點數量與平均移動距離

5 結束語

無線傳感器網絡覆蓋空洞影響網絡服務質量性能。為此，提出了基于非并行二分法的覆蓋空洞修復算法——CHRND，移動節點以非并行方式實現覆蓋空洞的完全修復。仿真結果顯示，CHRND算法能以較少數量的移動節點實現覆蓋空洞的完全修復，移動節點修復利用率較高，具有極少的冗余覆蓋，適用于通過一定數量的移動節點要求空洞區域完全修復的應用場景。