感知受限的移動傳感器節點掃描覆蓋優化算法

神顯豪，李 軍，奈 何

(廣西高校嵌入式技術與智能信息處理重點實驗室(桂林理工大學)，廣西 桂林 541004)

(*通信作者電子郵箱leejun19901113@163.com)

感知受限的移動傳感器節點掃描覆蓋優化算法

神顯豪，李 軍*，奈 何

(廣西高校嵌入式技術與智能信息處理重點實驗室(桂林理工大學)，廣西 桂林 541004)

(*通信作者電子郵箱leejun19901113@163.com)

移動無線傳感器網絡(WSN)的應用中，因為傳感器節點的感知范圍受限，其覆蓋分析就是一個針對目標區域的掃描覆蓋問題。提出了一種基于多目標優化的掃描覆蓋算法。在目標區域中，采用雙目標優化策略對單個移動傳感器節點進行路徑規劃，一方面使節點的覆蓋面最大化，另一方面使掃描覆蓋的路徑最短。仿真實驗在含有障礙物和不含障礙物的情況下進行，與多節點的編隊覆蓋算法相比，所提算法在適度降低覆蓋率的情況下，可大幅降低移動能耗。

移動傳感器節點；掃描覆蓋；雙目標優化；覆蓋率；能耗

GuilinGuangxi541004,China)

0 引言

在無線傳感器網絡(Wireless Sensor Network, WSN)研究中，覆蓋問題是基本問題之一，它直接影響到WSN的工作效率和質量。在移動無線傳感器網絡的應用中，因為移動傳感器節點的感知范圍受限，其覆蓋分析就是一個針對目標區域的掃描覆蓋問題。近年來國內外對移動傳感器節點的掃描覆蓋目標區域的算法也有一些研究。王偉等[1]提出了一種模擬退火算法的掃描覆蓋機制，比傳統的掃描覆蓋表現出更好的性能；雍毅等[2]提出了一種動態興趣點的掃描覆蓋，更能適應動態的目標區域；李小康等[3]提出了一種關于路徑增量與覆蓋間隔差異的插入啟發式算法；劉晨光等[4]設計了一種使用聚類方法的掃描覆蓋方法；舒莉等[5]設計了一種關于興趣點問題的掃描覆蓋；林鋒等[6]設計了一種掃描覆蓋方法，它使用具有移動性的傳感器節點當作輔助來修復覆蓋洞。上述幾種算法都是通過多個移動傳感器節點之間的編隊對覆蓋洞進行掃描覆蓋，沒有考慮到節點的能耗和生命周期，也沒有考慮在含有障礙物的情況下的路徑規劃等問題[7]。

在上述研究的理論基礎上，本文提出了一種優化的掃描覆蓋算法。在目標區域中，采用雙目標優化策略對單個移動傳感器節點進行路徑規劃，一方面使得節點的覆蓋面最大化，另一方面使掃描覆蓋的路徑最短。通過優化掃描覆蓋算法，既降低了節點在掃描覆蓋的過程中的能耗，又延長了節點的生命周期。

1 網絡模型

本文將計算域定義為D，緊子集定義為R2,障礙物的集合定義為Ω，一個封閉的集合包含了有限數量的連接部件和多個特定的障礙物。傳感器節點的半徑為r，水平集函數ψ(x)表明的環境包含了兩種情況：如果定義域的覆蓋部分是在障礙里面，那就表示為負的；如果定義域的覆蓋部分是在障礙外面，那就表示為正的。本文定義ψ(x)是障礙物Ω邊界的典型符號距離函數。一個傳感器節點x位于存在障礙物Ω的計算域D中，x為起始點，以直線的形式向前移動并且在點y的位置停下。如果x和y的絕對值之差小于等于r，那么就表示點y在障礙物的邊界或者之內。部分公式概念如表1所示。

下面定義半徑為r的傳感器節點移動到點y位置的檢測面積的水平集函數φ：

(1)

其中L(x，y)表示x到y的連線部分。z的位置在障礙物的邊界時ψ(z)=0，在障礙物內的時候ψ(z)<0,在障礙物外界的時候ψ(z)>0。

表1 公式概念

2 移動傳感器節點的路徑規劃

2.1 節點單位置的路徑規劃

考慮了移動傳感器節點單位置的最大覆蓋，更確切地說就是將移動傳感器節點移動到最大覆蓋范圍V的最佳位置。本文使用梯度上升的方法來實現這個目標，即本文按照梯度流來移動節點x的位置，公式[8]如下：

(2)

其中，Δx表示關于x的梯度算子。梯度算子可以近似地看作有限差分方程。如本文使用中心差分方程可以得到：

(3)

其中h表示空間步長。

為了能夠清晰地表示出移動傳感器節點達到最大化覆蓋的移動路徑，本文在目標區域中設置了三個障礙物，并且通過梯度流的方法移動傳感器節點，得到最大化覆蓋面積。如圖1所示，表示傳感器節點的初始位置；如圖2所示，表示移動傳感器節點x位移到與障礙物相切的位置，達到最大化覆蓋面積的位置[9]。移動傳感器節點在目標區域中移動，當碰撞到計算域D的邊界時，停止計算。其中陰影部分表明三個障礙物，虛線圓圈表示傳感器節點的感知面積。

圖1 傳感器節點初始位置

圖2 傳感器節點最大化覆蓋面積

2.2 節點多位置的路徑規劃

由移動傳感器節點單位置發散到移動傳感器節點的多位置，本文設{x1，x2，…，xm}表明m個傳感器節點，{r1，r2，…，rm}表明m個傳感器節點的半徑，每個傳感器節點的覆蓋范圍不同[10]。總的檢測范圍是多個傳感器節點的聯合覆蓋，多個傳感器節點的水平集函數如下所示：

(4)

另外，多個傳感器節點檢測面積V如下所示：

(5)

其中H表示一維的赫維賽德函數。

在目標區域中，兩個移動傳感器節點的情況下，需要尋找兩個新的位置達到彼此的覆蓋范圍不相交，這樣就使得覆蓋面積達到最大化[11]。如圖3所示兩個移動傳感器節點的初始狀態，如圖4所示兩個移動傳感器節點通過移動達到與障礙物相切，最終達到最大化覆蓋面積，其中陰影部分表明三個障礙物，虛線圓圈表明傳感器節點的檢測面積[12]。

圖3 兩個移動傳感器節點初始狀態

圖4 兩個節點的最大化覆蓋面積

當有三個移動傳感器節點時，本文也考慮了多個節點的局部優化。圖5為三個傳感器節點的初始狀態；圖6為三個傳感器節點達到的局部最大化覆蓋。其中陰影部分表示三個障礙物，虛線圈表示傳感器節點的覆蓋范圍[13]。

圖5 三個傳感器節點的初始狀態

圖6 三個傳感器節點的局部最大化覆蓋

2.3 解鎖方法

在移動傳感器節點的掃描過程中，面對障礙物的阻攔時需要改變位移的路徑[14]。掃描過程中有可能會出現路徑交叉的情況，這樣會延長完成覆蓋的時間[15]。為了解決交叉路徑問題，完成最短時間的優化，本文在交叉點的位置補充了兩個移動的位置。這樣就可以達到解鎖的目的，完成最短時間的最大覆蓋優化。如圖7所示，移動傳感節點的四個位置出現交叉，此時本文在交叉點位置加上了兩個移動位置完成解鎖，如圖8所示。

圖7 初始位置 圖8 解鎖

Fig.7InitialpositionFig.8Nodepositionafterunlock

為了能夠清晰地表示出該方法如何解鎖，本文給出了一般情況下的解鎖方法。

步驟1 假設移動傳感器節點的路徑為x1,x2,…,xm，其中路徑線段xixi+1和xjxj+1存在交叉點。

步驟2 假設路徑線段的交叉點為xinter，那么將xinter分別加入到xixi+1和xjxj+1兩個路徑線段之間。

步驟3 將交叉點加入到路徑線段之后，對移動傳感器節點的路徑重新排序如下所示：xi,xinter,xj,xj-1,xj-2,…,xi+2,xi+1,xinter,xj+1。

步驟4 重復步驟1到步驟3，直至路徑中不存在交叉點。

一般解鎖方法如圖9所示。

圖9 一般解鎖方法

3 掃描覆蓋算法設計

掃描覆蓋問題的目標是以最少數量的移動傳感器達到最大的覆蓋面積。在掃描覆蓋問題的相關場合中，決策者在目標區域布置少許的移動傳感器節點進行周期性的覆蓋，代替了大規模固定式傳感器節點覆蓋的間隔需要。由于目標區域覆蓋所需的節點數量減少，目標區域覆蓋所需的工作成本也隨之降低。

在傳感器節點覆蓋功能的水平集框架中，目標區域被描述的正值表示在覆蓋區域的障礙外，負值表示在障礙物內，零值表示在障礙物的邊界。傳感器節點直線前進遇到障礙物時，會導致覆蓋范圍丟失，如果目標區域中的點和傳感器節點的線段不相交于任何障礙物，那么該目標區域的點就會被傳感器節點所覆蓋。本文考慮了傳感器節點的有限覆蓋范圍，使用單個移動傳感器節點代替多個固定傳感器節點對目標區域進行掃描覆蓋。對于存在障礙物的目標區域，本文通過移動傳感器節點的路徑規劃方法實現最大化覆蓋。掃描算法設計如下：

步驟1 將多個固定傳感器節點，依次地加入到目標區域中，按照幾何方式布置達到全覆蓋。

步驟2 存在障礙物的情況下，利用單個移動傳感器節點代替多個固定傳感器節點，按原路徑進行掃描覆蓋。

步驟3 根據路徑規劃，使得移動傳感器節點達到最大覆蓋，通過位移多個節點所掃描的位置，達到節點的最大化覆蓋面積，并且刪除冗余的節點。

步驟4 按照最短路徑算法Dijkstra，利用移動傳感器節點求出全覆蓋下的最優路徑。

步驟5 如果初始化路徑中存在交叉路徑，那么使用解鎖方法來達到收斂。

步驟6 計算原有路徑長度和掃描覆蓋之后的路徑長度，進行比較。如果優化之后的路徑長度較短，那就說明本文掃描覆蓋方法的有效性；反之，則效果不佳。

4 仿真實驗及性能評估

4.1 實驗參數設置

本文采用Matlab2012b仿真平臺來進行仿真。平臺是基于IntelCorei5-2300的CPU，4GB的運行內存的PC。為了表示傳感器節點的覆蓋性能，本文分別在沒有障礙物的情況和存在障礙物的情況下進行分析。

1)無障礙物場景下的參數設置。

假定在20m×20m的目標區域內，依次布置的固定式傳感器節點數N=16，節點的理想探測半徑為r=6。無障礙物的仿真參數如表2所示。

表2 無障礙物場景下的仿真參數

2)有障礙物場景下的參數設置。

表3 有障礙物場景下的仿真參數

4.2 實驗結果對比

1)無障礙物場景。

本文使用16個固定式傳感器節點依次部署在20 m×20 m的目標區域中，達到全覆蓋的效果，如圖10所示。

接下來本文利用單個移動傳感器節點按照原來的路徑進行掃描，掃描過程按照幾何的方法進行。如圖11所示，移動傳感器節點移動了16次位置，并且存在冗余覆蓋面積。接下來本文會使用優化的掃描覆蓋算法來對移動次數優化，防止移動傳感器節點的能量耗盡。

由圖11可知，移動傳感器節點代替固定傳感器節點進行掃描覆蓋完成后，明顯存在冗余節點位置，冗余覆蓋。使用本文提出的掃描覆蓋算法，進行路徑規劃，并且將冗余節點位置去除。這樣可以達到移動傳感器節點以最少時間、最短路徑，達到最大化覆蓋面積的效果。如圖12可知，移動傳感器節點移動了10次位置，達到了全覆蓋的效果。

圖10 16個固定節點的全覆蓋

圖11 移動傳感器節點路徑覆蓋16個固定傳感器節點

圖12 優化掃描覆蓋的路徑

2)有障礙物場景。

在含有障礙物的情況下，該算法先假設障礙物不存在，使用36個固定傳感器節點依次部署在30 m×30 m的目標區域中，達到全覆蓋的效果，如圖13所示。

接下來利用單個移動傳感器節點按照原來的路徑進行掃描，掃描過程按照幾何的方法進行。如圖14所示，移動傳感器節點移動了36次位置，并且存在冗余覆蓋面積。接下來本文會使用優化的掃描覆蓋算法來對移動次數優化，防止移動傳感器節點的能量耗盡，來延長網絡壽命。

此時加入障礙物，也就相當于在復雜地形下，移動傳感器節點的路徑位置，如圖15所示障礙物阻擋了多個傳感器節點位置的感知面積。

圖13 36個固定節點的全覆蓋

圖14 移動傳感器節點路徑覆蓋36個固定傳感器節點

圖15 存在障礙物的移動路徑

經過掃描覆蓋優化方法之后，去除冗余的移動傳感器節點位置，減小了移動路徑的長度，縮短了移動到全覆蓋的時間，移動傳感器節點位移了33次，如圖16所示。

4.3 計算開銷性能和路徑長度

圖16 優化的移動路徑

表4 有無障礙情況下的參數對比

Tab.4 Parameter comparison with/without obstacles

場景路徑網絡區域范圍/(m×m)固定傳感器節點數感知半徑/m通信半徑/m節點的移動次數移動路徑長度/m無障礙物有障礙物原始路徑20×20166121660．00優化路徑20×20166121036．27原始路徑30×303652/25236175．00優化路徑30×303652/25233164．48

4.4 仿真對比

與傳統掃描覆蓋[5]相比，本文采用的是單個移動傳感器節點掃描覆蓋，通過路徑規劃使得節點達到最大覆蓋面積，而不是用多個移動傳感器節點實行編隊掃描覆蓋，后者大幅增加了成本，也增加了能耗。下面對本文提出的單個移動傳感器節點掃描覆蓋方法和雙節點編隊的掃描覆蓋方法進行仿真對比。如圖17所示，本文采用單個移動傳感器節點和兩個節點作對比，評估它們每個節點的時間和能耗。如圖18所示，在有限的時間內本文提出的單移動傳感器節點和雙移動傳感器節點編隊的覆蓋率作出了對比。

圖17 能耗仿真對比

根據圖17的仿真結果，在相同時間內本文提出的單個移動傳感器節點，沒有節點之間的編隊和通信，減少了能量消耗，延長了節點的生命周期。這樣可以確保移動傳感器節點在維持覆蓋的時間上能夠延長。根據圖18的仿真結果可知，隨著時間的增加，單移動傳感器節點和雙移動傳感器節點的覆蓋率都在增加，其中雙移動節點的覆蓋率較高些。

圖18 覆蓋率仿真對比

相比之下，雖然雙移動傳感器節點的覆蓋率較高些，但是它的兩個節點之間需要進行編隊和通信消耗了部分能量，每個節點能耗是單移動傳感器節點的近乎兩倍。為了延長節點的生命周期，在滿足覆蓋維持的前提下，可以選擇單移動傳感器節點對目標區域進行掃描覆蓋。

5 結語

本文提出了一種優化的掃描覆蓋。在目標區域中，使用單個移動傳感器節點來代替固定傳感器節點，對目標區域進行掃描修復。通過節點的路徑規劃，使得節點的覆蓋面最大化，同時掃描覆蓋的路徑最短。實驗結果表明，本文提出的算法在適度降低覆蓋率的情況下，可大幅降低移動能耗。

References)

[1] 王偉，林鋒，周激流.Sweep Coverage中的節點移動控制[J].四川大學學報(自然科學版),2010,47(5):1015-1019.(WANG W, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage [J].Journal of Sichuan University (Natural Science Edition), 2010, 47(5): 1105-1109.)

[2] 雍毅，林鋒，周激流.基于Dynamic POIs的Sweep Coverage節點移動算法[J].四川大學學報(自然科學版),2012,49(4):795-799.(YONG Y, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage based on dynamic POIS [J].Journal of Sichuan University (Natural Science Edition), 2012, 49(4): 795-799.)

[3] 李小康，林鋒，周激流.一種Sweep coverage問題的插入啟發式算法[J].四川大學學報(自然科學版),2015,52(1):74-78.(LI X K, LIN F, ZHOU J L.A novel insert heuristic algorithm for sweep coverage problem [J].Journal of Sichuan University (Natural Science Edition), 2015, 52(1): 74-78.)

[4] 劉晨光，林鋒，周激流.一種基于A-means聚類算法的Sweep coverage機制[J].計算機應用研究,2012,29(3):1051-1053.(LIU C G, LIN F, ZHOU J L.Sweep coverage approach with A-means clustering algorithm [J].Application Research of Computers, 2012, 29(3): 1051-1053.)

[5] 舒莉，林鋒，劉中豪,等.基于興趣點分類的無線傳感器網絡掃描覆蓋機制[J].西南交通大學學報,2014,49(1):165-172.(SHU L, LIN F, LIU Z H.POI classfication based sweep coverage scheme in wireless sensor networks [J].Journal of Southwest Jiaotong University, 2014, 49(1): 165-172.)

[6] 林鋒，王偉，周激流.MASC:一種基于移動輔助節點的Sweep Coverage機制[J].四川大學學報(工程科學版),2010,42(6):119-125.(LIN F, WANG W, ZHOU J L.MASC: a sweep coverage approach with mobile-assisted carriers [J].Journal of Sichuan University (Engineering Science Edition), 2010, 42(6): 119-125.)[7] 張洪德,石為人,楊磊,等.基于粒子均衡的移動傳感器網絡覆蓋控制研究[J].儀器儀表學報,2016,37(5):1049-1057.(ZHANG H D, SHI W R, YANG L, et al.Study on equilibrium of particle based coverage control for mobile sensor network [J].Chinese Journal of Scientific Instrument, 2016, 37(5): 1049-1057.)

[8] XIAO Y L, KAI L W, YANMIN Z, et al.Mobility increases the surface coverage of distributed sensor networks [J].Computer Networks, 2013, 57(11): 2348-2361.

[9] 方如舉,王建平,孫偉.無線傳感器網絡通信的擁塞控制策略[J].電子測量與儀器學報,2016,30(4):558-567.(FANG R J, WANG J P, SUN W.The congestion control strategy for WSNs communication [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(4): 558-567.)

[10] 徐雪松,楊勝杰,陳榮元.復雜環境移動群機器人最優路徑規劃方法[J].電子測量與儀器學報,2016,30(2):274-282.(XU X S, YAN S J, CHEN R Y.Dynamic differential evolution algorithm for swarm robots search path planning [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 274-282.)

[11] MA H-C, SAHOO P K, CHEN Y-W.Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks [J].Journal of Network and Computer Applications, 2011, 34(5): 1743-1756.

[12] 張建軍,陳曉,趙意.一種無線傳感器節點動態采樣策略[J].電子測量與儀器學報,2016,30(2):249-255.(ZHANG J J, CHEN X, ZHAO Y.Dynamic sampling control strategy for wireless sensor nodes [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 249-255.)

[13] SUNG H K, SEONG J K, HAOMIN Z.Path optimization with limited sensing ability [J].Journal of Computational Physics, 2015, 299: 887-901.

[14] 鄧亞平，吳川平.基于移動節點的無線傳感器網絡中的瓶頸節點[J].計算機應用,2011,31(7):1939-1943.(DENG Y P, WU C P.Bottleneck nodes in wireless sensor networks based on mobile sensors [J].Journal of Computer Applications, 2011, 31(7): 1939-1943.)

[15] GORAIN B, MANDAL P S.Approximation algorithms for sweep coverage in wireless sensor networks [J].Journal of Parallel and Distributed Computing, 2014, 74(8): 2699-2707.

This work is partially supported by National Natural Science Foundation of China (E050603), Scientific Research Project of Guangxi Higher Education Institutions (YB2014157), Natural Science Foundation of Guangxi (2015GXNSFBA139254).

SHEN Xianhao, born in 1980, Ph.D., associate professor.His research interests include intelligent fault diagnosis, wireless sensor network.

LI Jun, born in 1990, M.S.candidate.His research interests include wireless sensor network.

NAI He, born in 1992, M.S.candidate.His research interests include wireless sensor network.

Sweep coverage optimization algorithm for mobile sensor node with limited sensing

SHEN Xianhao, LI Jun*, NAI He

(GuangxiUniversitiesKeyLaboratoryofEmbeddedTechnologyandIntelligentInformationProcessing(GuilinUniversityofTechnology),

In the applications of mobile Wireless Sensor Network (WSN), since the sensing range of the sensor nodes is limited, the coverage analysis is a scan coverage problem for the target area.In this paper, a new scan coverage algorithm based on multi-objective optimization was proposed.In the target area, the double objective optimization strategy was used on path planning for a single mobile sensor node, which could maximize the coverage of the node and make scan coverage path to the shortest.Simulation experiments were carried out under the conditions with obstacles and without obstacles.Compared with the formation coverage algorithm for multiple nodes, the proposed algorithm can significantly reduce the mobile energy consumption while moderately reducing coverage rate.

mobile sensor node; sweep coverage; double objective optimization; coverage rate; energy consumption

2016-07-26;

2016-08-06。 基金項目:國家自然科學基金資助項目(E050603)；廣西高等學?？蒲许椖?YB2014157)；廣西自然科學基金資助項目(2015GXNSFBA139254)。

神顯豪(1980—)，男，廣西橫縣人，副教授，博士，主要研究方向：智能故障診斷、無線傳感器網絡； 李軍(1990—)，男，安徽滁州人，碩士研究生，主要研究方向：無線傳感器網絡； 奈何(1992—)，男，湖北襄陽人，碩士研究生，主要研究方向：無線傳感器網絡。

1001-9081(2017)01-0060-05DOI:10.11772/j.issn.1001-9081.2017.01.0060

TP

A