異構無線傳感器網絡覆蓋優化算法

杜曉玉孫力娟*②郭 劍韓 崇

(南京郵電大學計算機學院 南京 210003)②(南京郵電大學江蘇省無線傳感網高技術研究重點實驗室 南京 210003)

1 引言

隨著無線傳感網技術和微電子制造的發展，由大量具有感知能力，計算能力和通信能力的微型傳感器節點組成的無線傳感器網絡被應用到軍事領域或民用領域，比如環境監測、工業控制、戰場監視、高危環境的探測、生物醫學、智能家居及健康監測等[17]-。網絡覆蓋是無線傳感器網絡的基本問題之一，它反映了傳感器網絡節點對指定的監控區域監控程度，在很大程度上影響了網絡的成本以及網絡在各種具體應用中的性能。

覆蓋問題在多機器人系統以及計算幾何等領域已進行了廣泛的研究。無線傳感器網絡覆蓋問題與計算幾何中著名的藝術館走廊的監控問題和圓周覆蓋問題密切相關[4]。藝術館走廊的監控問題是考慮使用最少數量的攝像機，使得藝術館走廊內任何角落都能至少被一臺攝像機監視。2維平面上的藝術館走廊監控問題的解決方法是用互不交疊的多個三角形模擬畫廊，在每個三角形的任意一個頂點上安裝一臺攝像機就可以解決此問題， 但3維空間中此問題是一個NP完全問題[4]。監測區域的邊界覆蓋研究是柵欄覆蓋研究的一個特例，文獻[1]研究了圓形區域邊界的節點覆蓋調度問題，通過計算與區域邊界相交的感知圓對監測區域的張角來計算覆蓋整個圓周所需的最小數目的傳感器節點。在一些無線傳感器網絡的監測應用中，隨機部署的傳感器節點不需要完全覆蓋全部的監測區域，只需要監測區域內的多個重點對象，這類問題稱為多目標覆蓋問題[5,6]。文獻[5]設計了一個傳感器節點的感知能耗模型并針對此模型，提出一種啟發式分布貪婪算法來解決多目標覆蓋問題，該算法以最大化覆蓋目標的數量為優化目標建立數學模型，通過改變節點優先級的方式調整傳感器節點的感知半徑，從而節省網絡能耗。文獻[6]研究了通過調度傳感器節點成多個節點集合，使得網絡的生存壽命最長，且連通的目標覆蓋問題，要求每個節點集合中的傳感器節點既能覆蓋目標，又能連通所有的活動傳感器節點和匯聚節點。基于虛擬力的覆蓋算法也是目前研究的熱點[72]-1，虛擬力算法的核心思想是假定傳感器節點部署在虛擬力場中，節點與節點，移動節點與目標區域邊界之間存在相互作用力，并基于運動圖式理論來共同控制移動節點的運動，實現覆蓋的優化。

異構無線傳感器網絡的異構特性體現在節點異構性、鏈路異構性和網絡協議異構性3方面[10,1316]-。其中節點異構性又包括感知能力、計算能力、通信能力和能量等方面的異構性，通信能力、感知能力和能量對覆蓋的影響最大。現有文獻中關于隨機部署的異構無線傳感器網絡覆蓋問題的研究非常少，受到簡單隨機抽樣[17]和最優化算法[17,18]的啟發，針對異構傳感網絡節點初始隨機部署時產生覆蓋盲區的問題，本文提出了一種基于采樣的異構傳感網覆蓋優化算法(Coverage Optimization algorithm based on Sampling for Homogeneous WSNs , COSH)。以提高網絡覆蓋率和節點移動距離最小為優化目標，根據采樣直線與平面感知圓的交點坐標之間的關系，建立二次優化的數學模型，在節點移動距離最小的情況下達到對直線段的最優覆蓋。當監測平面中多條采樣直線段可以達到最優覆蓋時，平面的覆蓋可得到優化。本文主要創新點是： (1)通過對平面的采樣，將 2 維平面的覆蓋問題轉化為 1 維直線的覆蓋問題。(2)根據感知圓與采樣直線交點坐標建立非線性二次優化數學型，并采取約束條件緊縮的方法，將約束條件轉化為線性約束，求解問題的次優解。

2 數學模型及假設

假設監測區域H為矩形，N個半徑異構的無線傳感器節點隨機分布在矩形區域H內，假設無線傳感器網絡具有以下性質：

(1)傳感器節點感知半徑異構，即傳感器節點具有不同的感知半徑，傳感器節點的感知模型為二元感知模型，第i個傳感器節點iC的位置為，感知半徑為。

(2)各傳感節點的通信半徑是其最大感知半徑的兩倍，無線傳感器網絡保證其連通性。

(3)覆蓋算法執行之前，節點已準確定位，節點位置坐標已知[19]。

(4)節點在平面上可以自由移動，并節點有充足的剩余能量移動到指定位置。

定義.. 1 采樣直線。c為在2維平面中任意一條直線，直線c與監測區域的邊界相交于點A和點B。AB為監測平面的采樣直線，如圖1所示。

定義2 感知圓。傳感器節點iC位于2維平面中點，傳感半徑為ir ，那么由iC所涵蓋的感知區域是一個以為圓心，半徑為ir的圓，該圓稱為感知圓，記為iS ，定義為

定義3 覆蓋率。已覆蓋的區域Q的面積S(Q)和節點部署區域H的面積S(H)之比為覆蓋率。

3 基于采樣的覆蓋增強算法

感知圓iS的圓心到采樣直線的距離小于感知圓的半徑，圓與直線相交所形成的直線段被感知圓覆蓋。將與直線相交的感知圓沿直線方向移動，根據感知圓與直線交點坐標建立最優化方程，在節點移動距離最小的情況下，感知圓對直線達到最大覆蓋。因此2維平面的覆蓋問題可轉化為多個采樣直線的覆蓋優化問題，當多個采樣直線達到覆蓋優化時，2維監測平面可以達到覆蓋增強效果。

如圖2所示，矩形EFGH為2維監測平面，分別沿x軸和y軸方向對監測平面進行直線采樣，采樣直線平行于x軸或者y軸。AB為平面中一條平行于x軸的采樣直線，直線方程為為 n個與直線相交的感知圓，對應的傳感器節點位置坐標為，其中，感知圓的半徑為。假設感知圓點iS與采樣直線的交點為，交點坐標滿足不等式。稱為感知圓點與采樣直線的下交點，為上交點，如圖3所示。

圖 1 采樣直線

圖 2 異構網采樣示意圖

圖3 感知圓與采樣直線相交

若直線AB被感知圓完全覆蓋，每個感知圓與采樣直線的下交點位于至少一個感知圓的上交點的左側，而上交點位于至少一個感知圓的下交點的右側，同時，至少有一個感知圓的下交點位于左邊界的左側，并且至少有一個感知圓的上交點位于右邊界的右側。約束條件可寫為

上述問題為非線性二次規劃問題，非常難以求解，采取約束條件緊縮的方法，將約束條件轉化為線性的約束條件，求可行解。

定理 1 感知圓順序不變時，對采樣直線完全覆蓋所需移動距離之和小于順序改變時移動的距離之和。

證明 如圖4所示，假設在x軸區間(l, 0)內存在有兩個感知圓 S1, S2，其圓心分別為。其中。兩個感知圓與x軸的交點為和，交點坐標滿足如式(4)的不等式。

圖4 感知圓位置變化圖

傳感器節點沿直線方向左右移動，若移動之后感知圓對監測區域內的直線完全覆蓋，則兩感知圓對采樣直線的覆蓋線段必定存在重疊部分。假設覆蓋優化之后感知圓的圓沿x軸的排列順序未變，則，同時。即此時最小移動距離之和為。

若感知圓沿著 x軸方向的排列順序發生了變化，優化后節點 1在節點 2右側，即。同理，根據圓的位置關系可以推導出完全覆蓋時最小移動距離之和為，則有根據圓的性質可得

證畢

感知圓iS與直線段相交所形成的線段長度為如圖6所示，如果Ll＜，即達不到完全覆蓋的理想情況，式(10)的最優化問題無解，此時無法達到最優覆蓋。當覆蓋圓與直線段AB相交所形成的線段互不相交時，即任意一個感知圓與直線相交的下交點位于前一感知圓的上交點的右側，而上交點位于下一感知圓的下交點的左側時，感知圓對直線段的覆蓋區域達到最大，最優化算法為, n個感知圓與直線AB相交的線段的總長度L為。如果L大于采樣直線的長度l，采樣直線可以完全被覆蓋，如圖5所示，優化之后感知圓在采樣直線方向的相對位置順序不改變，iS與直線段相交的坐標應滿足如式(8)和式(9)的不等式：

4 算法流程圖

N個傳感器節點隨機分布在長為l，寬為w的區域內，節點半徑為

如圖 5(b)所示，優化之后感知圓對采樣直線完全覆蓋，即任意一個感知圓與直線相交的下交點位于前一感知圓的上交點的左側，而上交點位于下一感知圓的下交點的右側，優化算法為為所有傳感器節點感知半徑的最小值，R為傳感器節點感知半徑的最大值。采樣直線的初始位置為，采樣的步長為d。單次覆蓋優化算法的函數為

圖5 L＆gt;l，覆蓋優化前后對比圖

圖6 L＆lt;l，覆蓋優化前后對比圖

line為采樣直線的直線方程，C_n為節點的坐標和半徑的集合，E_v為邊界參數，是監測區域的邊界位置，表示了采樣直線最大的采樣值。若采樣直線的與x軸平行，則直線方程為y=yi, E_v l= ；若與y軸平行，直線方程為x = xj, E_v w= 。集合C為函數的輸出，是所有節點新的坐標值。單次覆蓋優化算法函數cover的流程圖如圖7所示。

縱向直線采樣的覆蓋優化算法與橫向采樣類似，將算法中對交點的橫坐標計算替換為交點的縱坐標計算即可。橫向覆蓋優化和縱向覆蓋優化之間存在相互影響，當采樣步長較小時，相鄰兩條采樣直線的優化結果也會相互影響，因此采用多次迭代的方法，使覆蓋率達到一個穩定值。算法的偽碼如表1所示。

5 仿真分析

圖7 單次覆蓋優化算法的流程圖

表1 COSH算法偽碼

為了驗證 COSH算法的有效性，本文利用Matlab進行仿真實驗。在實驗中，無線傳感器節點隨機分布在長度為300 m，寬度為300 m的部署區域中。節點的最大感知半徑R為40 m，最小值感知半徑r為15 m，每個傳感器節點的感知半徑為區間[15,40]內的隨機數。圖8為40個傳感器節點的隨機分布在部署區域中的網絡布局圖，圖中數字為節點的ID號。設定采樣步長為20 m，經過2次COSH算法的迭代計算，新的網絡布局如圖9所示。由仿真圖可以看出，經過COSH算法優化之后節點較為均勻的分布在監測區域內，覆蓋冗余及覆蓋盲區的現象均有所減少。

為進一步驗證算法的性能，通過實驗對文獻[7]所提出的虛擬力算法和COSH算法的收斂速度及覆蓋率進行比較，圖10~圖12節點數目分別為40, 50,60時覆蓋率隨迭代次變化的對比圖，圖13為隨機部署，6次迭代的虛擬力算法和2次迭代的COSH算法覆蓋率隨傳感器節點數量變化的仿真圖。由仿真結果可以看出，COSH算法的收斂速度要遠遠高于虛擬力算法，COSH算法可在3次迭代以內達到最佳覆蓋率，但虛擬力覆蓋通常經過10次迭代計算才能達到最佳覆蓋率，從數據上看，COSH算法覆蓋優化效果遠高于虛擬力算法。

COSH的覆蓋優化效果不僅和迭代次數有關，也受到采樣直線步長的影響，圖14為COSH算法在不同節點數目的情況下覆蓋率隨采樣步長的變化圖。當采樣步長較小時，兩次采樣直線之間距離較小，優化結果會相互影響，因此在計算量增加的情況下覆蓋率反而有所下降。采樣步長過大時，無法對整個監測區域的覆蓋情況進行優化，同樣覆蓋率也不能得到有效的提高。綜合兩方面的因素考慮，我們選擇采樣步長為 /2R 。圖15為COSH算法在不同節點數目的情況下，每次迭代優化時節點的平均移動距離的變化圖。由圖中可以看出算法，第 1次迭代優化移動距離最大，隨著迭代次數的增加，節點的平均移動距離減少，并收斂于穩定值。這表明算法的收斂速度很快，經過2~3次迭代就可以達到較優的覆蓋效果。結合圖10~圖13分析，3次迭代之后節點位置在小范圍內微調，但對覆蓋率的提高影響不大，在滿足覆蓋要求的前提下算法可在 3次迭代之內完成。

圖 8 隨機分布網絡布局圖

圖9 COSH算法網絡布局

圖10覆蓋率隨迭代次數的變化(40個節點)

圖11覆蓋率隨迭代次數的變化(50個節點)

圖12覆蓋率隨迭代次數的變化(60個節點)

圖13 覆蓋率隨節點數量的變化

圖14 覆蓋率隨采樣步長的變化

圖15 平均節點移動距離隨迭代次數的變化

6 結束語

針對異構傳感網絡節點初始隨機部署時產生覆蓋盲區的問題，本文提出一種適用于異構網絡的采樣覆蓋優化算法。通過對監測平面進行直線采樣，對采樣直線的覆蓋進行優化。根據直線段與平面感知圓的交點坐標之間的關系，以提高網絡覆蓋率和節點移動距離最小為優化目標，建立二次優化的數學模型，在節點移動距離最小的情況下達到對直線段的最優覆蓋。多條采樣直線段可以達到最優覆蓋時，平面的覆蓋可得到優化。由實驗結果可以看出，該算法可有效地提高異構網的覆蓋率。經過2~3次迭代計算，異構網的覆蓋率可提高20%左右，并且該算法的收斂速度和覆蓋的優化效果要高于普通的優化算法。

[1] Khedr A M and Osamy W. Minimum perimeter coverage of query regions in a heterogeneous wireless sensor network[J].Information Sciences, 2011, 181(15): 3130-3142.

[2] Bai Xiao-le, Yun Zi-qiu, Dong Xuan, et al.. Optimal multiple-coverage of sensor networks[C]. 30th IEEE International Conference on Computer Communications,Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2011), Shanghai,2011: 2498-2506.

[3] Ammari H M and Das S K. A study of k-coverage and measures of connectivity in 3D wireless sensor networks[J].IEEE Transactions on Computers, 2010, 59(2): 243-257.

[4] Marengoni M I C, Draper B A, Hanson A, et al.. A system to place observers on a polyhedral terrain in polynomial time[J].Image and Vision Computing, 2000, 18(10): 773-780.

[5] Qun Zao and Gurusamy M. Lifetime maximization for connected target coverage in wireless sensor networks[J].IEEE/ACM Transactions on Networking, 2008, 16(6):1378-1391.

[6] Naderan M, Dehghan M, and Pedram H. Sensing task assignment via sensor selection for maximum target coverage in WSNs[J]. Journal of Network and Computer Applications,2013, 36(1): 262-273.

[7] Yi Zou and Chakrabarty K. Sensor deployment and target localization based on virtual forces[C]. The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, USA, 2003:1293-1303.

[8] 周浦城, 崔遜學, 王書敏, 等. 基于虛擬力的無線傳感器網絡覆蓋增強算法[J]. 系統仿真學報, 2009, 21(5): 1416-1419.Zhou Pu-cheng, Cui Xun-xue, Wang Shu-min, et al.. Virtual force-based wireless sensor network coverage-enhancing algorithm[J]. Journal of System Simulation, 2009, 21(5):1416-1419.

[9] 李明, 石為人. 虛擬力導向差分算法的異構移動傳感網絡覆蓋策略[J]. 儀器儀表學報, 2011, 32(5): 1043-1051.Li Ming and Shi Wei-ren. Virtual force-directed differential evolution algorithm based coverage-enhancing algorithm for heterogeneous mobile sensor networks[J]. Chinese Journal of Scientific Instrument, 2011, 32(5): 1043-1051.

[10] 黃帥, 程良倫. 一種基于虛擬力的有向傳感器網絡低冗余覆蓋增強算法[J]. 傳感器技術學報, 2011, 24(3): 418-422.Huang Shuai and Cheng Liang-lun. A low redundancy coverage-enhancing algorithm for directional sensor network based on fictitious force[J]. Chinese Journal of Sensors and Actuators, 2011, 24(3): 418-422.

[11] Huang Jun-jie, Sun Li-juan, Wang Ru-chuan, et al.. Improved virtual potential field algorithm based on probability model in three-dimensional directional sensor networks[J].International Journal of Distributed Sensor Networks, 2012,DOI:10.1155/2012/942080.

[12] Huang Jun-jie, Huang Hai-ping, Sun Peng, et al.. Probability model based coverage-enhancing algorithm for WSNs of nodes’ adjustable movement pattern[J]. International Journal of Distributed Sensor Networks, 2012, DOI:10.1155/2012/570643.

[13] 洪榛, 俞立, 張貴軍. 多級異構無線傳感網高效動態聚簇策略研究[J]. 自動化學報, 2013, 39(4): 454-460.Hong Zhen, Yu Li, and Zhang Gui-jun. Efficient and dynamic clustering scheme for heterogeneous multi-level wireless sensor networks[J]. Acta Automatica Sinica, 2013, 39(4):454-464.

[14] 李明. 異構傳感器網絡覆蓋算法研究[D]. [博士論文], 重慶大學, 2011.Li Ming. Study on coverage algorithms for heterogeneous wireless sensor networks[D]. [Ph.D. dissertation], Chongqing University, 2011.

[15] Kumar D, Aseri T C, and Patel R B. EEHC: energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communications, 2009, 32(4):662-667.

[16] 王明慈, 沈恒范. 概率論與數理統計[M]. 北京:高等教育出版社, 2007: 119-145.

[17] Cardei M, Thai M T, Ying-shu L, et al.. Energy-efficient target coverage in wireless sensor networks[C]. 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2005), Miami 2005:1976-1984.

[18] Sengupta S, Das S, Nasir M D, et al.. Multi-objective node deployment in WSNs: in search of an optimal trade-off among coverage, lifetime, energy consumption, and connectivity[J].Engineering Applications of Artificial Intelligence, 2013,26(1): 405-416.

[19] Kashi S S and Sharifi M. Coverage rate calculation in wireless sensor networks[J]. Computing, 2012, 94(11): 833-856.