基于貪婪策略的無線傳感器網絡覆蓋優化方法*

吳煜瑋，黎 聰

(電子科技大學 電子科學技術研究院，四川 成都611731)

0 引 言

覆蓋質量是無線傳感器網絡(WSNs)最為關心的重要問題之一。區域覆蓋的目標就是監測區域中每個位置都至少被一個傳感器所覆蓋到，Zhou Z H 等人［1］在該領域提出了著名的k-covered 問題。區域內任一點p 被k 個傳感器覆蓋，則該區域是k-covered。文獻［2］提出當Rc=2Rs時(其中，Rc為通信半徑，Rs為感知半徑)，k-covered 可轉換為k-connected，并證明了一個凸區域是k-covered 只需要保證它所有交點都是k-covered。文獻［3］研究了在保證網絡k-covered 的前提下，節點數、激活概率、感知半徑與覆蓋度之間滿足的關系。對于估算最初部署時需要激活的傳感器數量有指導性的意義。

Slijepeevic S 等人［4］提出將節點化為互不相交的集合，每個集合都能獨立滿足對目標區域的覆蓋質量。集合劃分的越多，網絡生存時間越長。由于尋找互不相交的集合是NP 完全問題，文獻［5］對此進行了改進，允許一個節點同時劃分到多個集合中。在此前提下，研究了網絡生存時間和節點調度問題，但不能保證對區域的完全覆蓋。文獻［6］用一種適合的算法判定監視區域是否被鄰居節點覆蓋，若能取代，則將該節點轉入休眠狀態。文獻［7］通過向周圍區域發送探測半徑為r 的廣播信息，若能收到回復信息，則將該節點轉入休眠狀態。這些研究都會涉及到計算傳感器感知區域的重合情況，計算開銷很大。

為了減小計算開銷，本文提出一種提高區域覆蓋的新方法，通過分析和計算傳感器分布的幾何特征，每次迭代激活最佳位置節點來達到有效覆蓋的目的。

1 模型設計與問題描述

1.1 傳感器模型

假設每個傳感器都精確知道自己所處在的位置坐標，并且每個傳感器都可以工作在激活模式(active)和休眠模式(sleep)，只要節點被激活就一直工作到能量耗盡為止。工作在激活模式下的節點集用Sa 表示，休眠模式下用Ss表示。本文所用均為靜態節點，每個節點的感知半徑Rs 都相同。每個節點的通信半徑Rc也相同，且滿足Rc=2Rs。節點的感知區域是以該節點為圓心，半徑為Rs的圓域。節點的通信區域是以該節點所處位置為圓心，半徑為Rc的圓域。所用節點的感知概率模型為布爾型，如圖1 所示，實心區域中的任意位置都能被節點si感知。

圖1 傳感器模型Fig 1 Sensor model

1.2 問題描述

假設目標監視區域為一平面矩形區域A，將足夠多的傳感器均勻隨機部署在區域A 中并假定同一位置僅有一只傳感器存在。假設區域A 的范圍遠遠大于傳感器的尺寸，故可以將傳感器模型簡化為一個點。節點所處的位置代表傳感器部署在區域中的位置。

當前時刻網絡的覆蓋情況由此時所處在激活模式的節點構成的監視范圍和監視范圍中的漏洞共同決定。監視范圍是當前激活節點可以覆蓋的最大范圍。如圖2 所示，黑色和灰色圓域各自代表激活節點和休眠節點的感知范圍，黑色虛線代表著當前時刻網絡的監視范圍。

圖2 監視范圍與凸包Fig 2 Monitoring range and convex hull

顯然，在監視范圍以外的目標監視區域還存在的監視空白，并且虛線內部存在著大量的覆蓋漏洞。當前時刻的覆蓋情況是由監視范圍和漏洞面積共同決定的，其關系如下

其中，Scoverage表示網絡的覆蓋面積，即已激活節點覆蓋范圍的并集。SMonitoregion表示監視范圍面積，SHole為監視范圍中存在的覆蓋漏洞面積。因此，可以從擴大SMonitoregion和減小SHole兩方面著手考慮達到提高Scoverage的目的。

如果將處在激活狀態傳感器所處位置抽象成為二維平面上的點集，凸包就是將最外層的傳感器連接起來構成的凸多邊形，它必須包含點集中所有已激活傳感器。如圖2所示，黑色的實線圈就是該無WSNs 的凸包。

在圖2 中，當前時刻激活節點所構成的監視范圍是黑色虛線的不規則多邊形內部，而黑色實線是當前時刻工作在激活模式節點的凸包包絡。可以看出黑色實線也同樣能夠近似表征當前時刻網絡的覆蓋情況。特別是當目標監視區域面積相比傳感器的感知范圍足夠小時，凸包面積與監視范圍相差無幾

其中，ρ=Aarca/Carea為區域A 的面積與傳感器感知范圍Carea的比值，SConvexHull為凸包面積，并且隨著比值ρ 的不斷增大，凸包的面積將趨近于真正的監視范圍。因此，可以用凸包來代替監視范圍，式(1)修改如下

這樣提高覆蓋面積SCoverage可以從增大凸包面積SConvexHull和減小覆蓋漏洞SHole兩方面著手。一方面當凸包面積SConvexHull一定時，減小凸包內存在的覆蓋漏洞SHole可以提高覆蓋面積SCoverage;另一方面，當凸包內覆蓋漏洞SHole不存在或者說可以忽略時，增大凸包面積也能提高覆蓋面積SCoverage。為了達到盡可能少激活傳感器并且快速增大覆蓋面積的目的，本算法采取在已存在網絡基礎上每一次僅激活一只傳感器，最有效地利用該傳感器增大凸包面積SConvexHull或者填補覆蓋漏洞SHole。

假設當前狀態下處于激活狀態Sa 集合中節點總數共有n 個，處于休眠狀態Ss 集合節點個數為m。當前網絡的覆蓋面積可表示為

其中，Ci為第i 號節點的感知范圍，i∈Sa。SCoverage就是所有處于激活狀態節點感知范圍的并集。激活一個來自Ss節點集合后網絡的覆蓋面積用S'Coverage表示，目標是使得S'Coverage最大

其中，Cj為第j 號節點的感知范圍，j∈Ss。

要使得S'Coverage最大，只有通過比較來自Ss 集合不同節點產生的效益，選擇激活產生效益最大對應的那個節點來達到在下一個狀態時最好的覆蓋水平。故問題轉化為如何選擇激活一個Ss 集合節點，使得覆蓋率得到最大提升。

2 解決方案

為了尋找出最佳待激活節點，本文提出的解決方案如圖3 所示。

2.1 求出Sa 集合凸包和對Ss 集合節點分類

求出由當前Sa 集合構成的最大包絡外包絡，簡化為點集Sa 構成的凸包面積。如圖2，區域中，黑色實線圍成的封閉凸多邊形就是當前狀態下Sa 點集的凸包。

圖3 算法流程圖Fig 3 Flow chart of algorithm

這樣Ss 集合可劃分為兩類。如圖2 所示，處于黑色凸包包絡以外的休眠節點sleep_out 集合，處于黑色凸包包絡以內的休眠節點sleep_in 集合。選擇激活sleep_out 集合中節點可以增大凸包面積SConvexHull，選擇激活sleep_in 集合中節點可以彌補覆蓋漏洞。

2.2 增大凸包面積/減小漏洞面積

考慮激活盡可能少的傳感器數量完成相同的任務，故采取每一輪循環只激活一只傳感器最大化的提升覆蓋面積。最大程度增大凸包面積或者最大程度彌補覆蓋漏洞都是最大化提升覆蓋面積的有效手段。

2.2.1 增大凸包面積

如圖4 所示，區域H1是Sa 集合的凸包，凸包外部有兩個處于休眠模式的節點A 與節點B，只有處于包絡外圍的點才有機會改變凸包的形狀。假如激活A 節點相應增大的面積為H1區域，激活節點B 后增大的面積為H2區域。通過計算可以得出H1面積大于H2區域面積。所有在當前狀態下把節點A 選作增大凸包候選激活節點，稱作T2。

圖4 增大凸包面積Fig 4 Increasing area of convex hull

2.2.2 減小漏洞面積

在Sa 集合的凸包內，并不能保證凸包內部區域實現完整覆蓋，故需要增加節點填補凸包內部存在的漏洞。

定義 給定平面上一點集P，要求以不在同一直線上的三個點作一個圓，要求這樣的圓域內部不包含P 集合中的其他點并且圓心位于所限定區域的內部，這樣的圓稱作空圓。

定理 當空圓半徑Rh＞Rs時，空圓中一定存在覆蓋漏洞。

證明 從定義可知，由激活節點構成的空圓內部不包含其他處在激活模式節點，顯然，當空圓半徑Rh＞Rs時，空圓圓心點一定未能被覆蓋到，故這樣的空圓中一定會存在覆蓋漏洞。

空圓的半徑越大，意味著節點與節點間的距離越大，覆蓋漏洞面積也遠。因此，選擇激活最大空圓內的休眠節點達到最有效地減小覆蓋漏洞的目的。將最靠近最大空圓圓心的休眠節點激活能最大程度上地消除最大空圓內部的覆蓋漏洞，該節點作為減小覆蓋漏洞候選激活節點，稱作T2。

2.3 選擇最終激活的節點

上述過程已經找出兩個候選激活節點。分別計算假設激活它們后所對應的凸包增大面積和最大空圓面積

其中，Hull_add 為假如激活T1節點后凸包增大面積，Empty_circle 為最大空圓面積，optimum 為最終激活節點。

如圖5 所示，凸包增大面積是A1區域，最大空圓面積是A2區域。當A1區域面積大于A2區域面積時，將T1節點作為最終激活節點;否則，將T2作為最終激活節點。

圖5 最終激活節點的選擇Fig 5 Choice of final activated node

2.4 重新計算區域覆蓋率

將所激活的節點從Ss 集合中刪除，同時添加到Sa 集合中，再進行判定是否達到覆蓋要求。若仍小于覆蓋度閾值，則按照此方法繼續激活Ss 集合節點，直到該區域覆蓋度達到閾值要求。

3 仿真與評估

本文在Matlab 上對算法進行了仿真實驗。在平面上100 m×100 m 的矩形區域中一共投放了400 個節點，每個節點的感知半徑Rs為10 m，通信半徑Rc為20 m。在最開始隨機激活50 個節點使其保持在工作狀態，而其余節點處于休眠狀態。實驗目標是使得該區域99%的面積得到覆蓋。

仿真結果如圖6 為初始節點的覆蓋情況，圖7(a)為使用本文提出的算法后的覆蓋情況，圖7(b)為使用隨機激活算法后的覆蓋情況。圖7(a)總共使用了86 個節點達到目標覆蓋，而圖7(b)卻花費了高達147 個節點才實現同等的覆蓋水平。

圖6 初始分布的節點覆蓋情況Fig 6 Coverage of initial deployed nodes

圖7 兩種算法覆蓋情況Fig7 Coverage of two kinds of algorithms

新增節點數和監視區域的覆蓋率之間的關系如圖8 所示。按照本文的算法，僅僅新激活了10 個節點，就將覆蓋度從最初部署時的77%增加到了90%，而隨機激活算法新激活了25 個才達到同等覆蓋水平。顯然，使用本文的算法能更快速有效地彌補監視區域所存在的漏洞，從而迅速提高覆蓋水平。為了不失一般性，本文模擬了30 次并記錄下統計結果，利用本文的算法，達到95%的覆蓋度平均需要新增18.5 個節點，而隨機調度算法則需要付出61.5 個新增節點。為了探究在相同目標覆蓋率下不同的感知半徑和新增節點數之間的關系，進行了30 次仿真實驗，結果顯示:本文提出的算法在不同的感知半徑下都能很好地節約傳感器資源，感知半徑越小，節省的節點資源越多，統計結果如圖9。

圖8 覆蓋率與新增節點數Fig 8 Coverage ratio and added nodes

4 結 論

圖9 半徑與新增節點數的關系Fig 9 Relationship between radius and added node numbers

本文針對已存在網絡不能滿足覆蓋指標的情況，提出了一種根據網絡的幾何特征不斷選擇最佳激活節點，最終達到覆蓋要求的方法。本文提出的算法避免了傳統調度算法需要建立在計算得到各節點感知模型重疊情況的弊端，大大降低了計算開銷。仿真結果證實了本文作者提出的算法能迅速增大覆蓋率并且很大程度上節省了節點資源。在今后的工作中，將引入可移動無線傳感器和分布式算法對該問題進行優化求解。

［1］ Zhou Z H，Samir D，Gupta H.Connected K－coverage problem in sensor networks［C］∥Proceedings of IEEE the Thirteenth International Conference on Computer Communications and Networks，Chicago，IL，2004.

［2］ Wang X R，Xing G L，Zhang Y F.Integrated coverage and connectivity configuration in wireless sensor networks［C］∥Proceedings of the 1st International Conference on Embedded Networked Sensor Systems，New York，NY，USA:ACM，2003.

［3］ Kumar S，Lai T H，Balogh J.On K－coverage in a mostly sleeping sensor network［C］∥Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，New York，NY，USA:ACM，2004.

［4］ Slijepcevic S，Potkonjak M.Power efficient organization of wireless sensor networks［C］∥IEEE International Conference on Communications(ICC)，Washington:IEEE Computer Society，2001.

［5］ Berman P，Calinescu G，Shah C，et al.Power efficient monitoring management in sensor networks［C］∥IEEE Wireless Communications and Networking Conference(WCNC)，Atlanta:IEEE Computer Society，2004:21－25.

［6］ Tian D，Georganas N D.A coverage－preserving node scheduling scheme for large wireless sensor networks［C］∥Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications，New York，NY，USA:ACM，2002.

［7］ Ye F，Zhong G，Lu S，et al.Energy efficient robust sensing coverage in large sensor networks［R］.Los Angeles:UCLA Technical Report，2002.