基于方向梯度的WSN三維覆蓋策略

王丹丹 徐汀榮

(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

基于方向梯度的WSN三維覆蓋策略

王丹丹 徐汀榮

(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

針對無線傳感器網絡中的三維表面覆蓋問題，提出一種基于方向梯度的覆蓋算法。首先將三維表面垂直投影到二維平面上，然后采用區域離散化的思想，將二維平面離散成若干個網格點，再根據方向梯度概率感知模型，確定每個點覆蓋的范圍，最后通過貪婪算法找出滿足覆蓋率的最小覆蓋集。該方法采用的方向梯度概率感知模型，充分考慮了三維表面地形的影響以及實際應用中的感知范圍衰減因素。通過大量仿真實驗表明，該方法能有效覆蓋三維區域。

無線傳感器網絡 三維表面覆蓋 方向梯度

0 引 言

近年來，無線傳感器網絡WSN在軍事、工農業控制、城市管理、搶險救災等各個領域得到了廣泛應用。無線傳感器網絡通過部署在監測區域中的傳感器節點進行數據收集，然后把數據發送給匯聚節點，匯聚節點再通過互聯網或衛星傳輸給任務管理節點。在無線傳感器網絡中，節點的部署是基本且重要的問題。

最早對無線傳感器網絡覆蓋問題的研究主要集中在二維理想平面，節點采用傳統的圓盤模型對目標監測區域進行覆蓋。隨著對無線傳感器網絡技術研究的不斷深入，二維平面模型越來越不適用于現實世界中的復雜應用場景，基于空間的三維無線傳感器網絡成為無線傳感器網絡研究中的熱門領域，與二維平面中節點的圓盤感知模型不同，三維空間中的節點模型為球體感知模型。三維表面覆蓋是三維無線傳感器網絡中的一種特殊情形，對應于現實世界中的山體，是在實際應用場景中衍生出來的一種新的網絡模型。文獻[1]針對三維表面覆蓋問題，先把目標區域分成N個子區域，再利用多目標覆蓋的遺傳算法在各個子區域中進行選擇、交叉、變異操作，來保證網絡的覆蓋和連通。該方法基于圓盤感知模型，沒有考慮地形對其感知范圍的影響。文獻[ 2 ]選用馬鞍形曲面進行研究，節點的感知模型選用符合三維曲面固有特性的概率感知模型。先隨機部署傳感器節點，再利用差分進化算法進行優化，實現對目標區域中節點部署問題的研究。該方法是在規則三維表面進行的節點部署，不能滿足實際應用需求。文獻[ 3 ]提出了一種把降維和遺傳算法相結合來解決三維覆蓋問題的策略。針對無線傳感器網絡中的確定性覆蓋問題,首先把三維曲面進行降維,然后采用改進的遺傳算法通過不斷迭代來搜索全局最優覆蓋解。文獻[ 4 ]把三維表面覆蓋問題分為規則地形覆蓋和不規則地形覆蓋兩類。規則地形提出圓錐模型和余弦模型來刻畫，從而得出期望覆蓋率。針對不規則地形，采用基于數字高程模型中的規則三角網解決方案，來估算網絡的期望覆蓋率。文獻[ 5 ]中使用基于方向梯度的感知模型對已經部署好節點的三維表面進行陷阱空洞的檢測。使用該模型與之前的圓盤模型相比，原有陷阱空洞的直徑增加，并且能發現新的陷阱空洞，該模型更能反映起伏地形的特征。

本文基于方向梯度感知模型提出了一種對傳感器節點進行確定性部署的方法。充分考慮三維表面地形對節點感知范圍的影響，根據節點在各個方向上的方向梯度大小，確定每個點的實際覆蓋范圍。由于方向梯度的感知模型是非線性模型，求解感知范圍比較困難，因此通過區域離散化的方法，把求解覆蓋范圍轉化為求解覆蓋點?？紤]到信號衰減等因素的影響，利用概率感知模型，確定節點對每個點的感知概率，再利用貪婪算法找出滿足目標覆蓋率的最小覆蓋集。

1 覆蓋策略描述

1.1 網絡模型

本文在三維區域中根據提出的算法確定性部署若干個節點，采用如下假設：

a) 傳感器節點沿各個方向的理想探測半徑為r。

b) 不考慮三維表面凹凸點對感知結果的影響。

1.2 基于方向梯度的覆蓋算法

考慮三維表面的影響，采用基于方向梯度的感知模型對目標區域進行覆蓋。

1.2.1 三維轉化成二維

由于節點的感知模型是球體，而三維表面是不規則的，無法確定節點在三維上的感知區域，從而在三維表面直接確定節點的覆蓋集是比較困難的，所以本文采用投影的方式，把三維表面垂直投影到二維上，在二維上進行覆蓋集的選取。

1.2.2 基于方向梯度的概率感知模型

把三維問題轉化為二維問題后，若直接采用二維上的圓盤感知模型會造成如圖1所示的問題[6]。在二維平面上可以完全覆蓋，在三維上卻會出現覆蓋漏洞。所以本文把基于方向梯度的感知模型[5]和指數衰減概率模型[7]相結合得到了基于方向梯度的概率感知模型。

圖1 三維感知漏洞問題

用坡度表示地形陡緩程度，如圖2所示，把坡面的垂直高度h和水平距離l的比叫作坡度，用字母i表示。坡向是斜坡面對的方向，即高度下降最快的方向。

(1)

圖2 坡度和方向梯度概念

為了表示坡面上的點沿任一方向高程值的變化，引出了方向梯度的概念，用g表示。

(2)

其中，ω表示方向角，即與坡向的夾角。當ω為0時，即方向與坡向一致，此時方向梯度等于坡度。

由式(1)、式(2)兩個公式可以推出該點沿ω方向的實際感知半徑，用sr表示。

sr=rcos[arctan(icosω)]

(3)

由此可得出坡面上任意一個點的覆蓋區域。

因為在實際三維應用場景中，監測結果受到噪聲干擾，信號衰減等因素的影響，所以需要采用如下所示的概率感知模型來反應節點的實際監測能力，P(s,t)表示節點s監測到目標點t的概率。

(4)

其中，d=d(s,t)-(sr-ur)，d(s,t)表示節點和目標點的距離，α和β是衰減因子。sr是利用方向梯度感知模型預先計算好的節點感知半徑，ur是一個不確定的感知范圍，當目標點t在sr-ur范圍內的時候，能百分百被覆蓋，當目標點在sr+ur范圍外的時候，不能被覆蓋，當目標點介于兩者之間時，感知概率滿足式(4)中的指數函數。

1.2.3 區域離散化

由于方向梯度感知模型得到的覆蓋半徑是可變的，求解相應面積時比較復雜，所以本文采用區域離散化的方法，把平面區域上的覆蓋轉化成點的覆蓋問題。如圖3所示，橢圓所在區域是點的覆蓋區域，把其中包含的完整網格離散化形成圖4所示區域中的點，根據文獻[ 8 ]中的引理，該方法能保證所求離散問題的可行解也是對原來對應連續問題的可行解。

圖3 節點覆蓋區域

圖4 離散化后需要覆蓋的點集

1.2.4 貪婪算法

把離散化后形成的網格點的位置作為覆蓋集節點的候選位置。節點覆蓋的最終目標是覆蓋網格點的概率盡可能大。經過區域離散化后可以確定每個節點覆蓋的網格點的概率，依次遍歷每個節點，從中選取使得現有覆蓋概率提升最大的點加入覆蓋集，每次選取完之后，加入覆蓋集的節點不參加下一輪的選舉，在剩下的點中選取覆蓋概率提升最大的點加入。重復進行上述步驟直到區域中每個網格點被覆蓋的概率達到95%以上，由此確定覆蓋集。完整的覆蓋集生成算法如下：

算法1基于方向梯度概率模型的貪婪算法

輸入：劃分網格大小rows×cols，三維表面網格頂點坐標w(x,y,z)，感知半徑sr，不確定感知范圍ur。

輸出：覆蓋集C，每個點的平均覆蓋概率P。

標記：currP:記錄每個點當前覆蓋概率的數組G:網格點集

第1步C=?

第2步

1) 劃分網格，記錄每個網格中心點的位置坐標，把該網格點g加入G

從表2中的數據可看出，用GM(1，1)模型得到的預測值并不是很理想，其平均相對誤差為0.038 2%。利用GM(1，1)預測模型來預測第8次沉降值，得到的預測沉降值為20.76，相對誤差為0.055%，后驗差比值C為0.065。

2) 根據每個網格點的高度信息，得出每個點的坡度，坡向，存儲到坡度矩陣SlopeMatrix，坡向矩陣AspectMatrix中

第3步 根據上述坡度坡向信息，結合概率感知模型，確定每個點對其他點的感知概率

第4步 While(P<0.95)

a) 對每個點g∈G,計算點g加入C后，currP提高的概率

b) 找出能使currP提升最高的點v，C=C∪{v}

c) 更新currP中目前對每個點的覆蓋概率

第5步 ReturnC,P

2 算法分析

在第二階段根據坡度矩陣和坡向矩陣信息，確定每個點對其他點的覆蓋概率，需要使用兩重循環遍歷查找所有點，對應的時間復雜度為O(n2)，把找出來的結果存儲到一個矩陣中，第i行存儲編號為i的點對其他點的覆蓋概率。

在第三階段，循環選取網格點加入覆蓋集，直到覆蓋概率達到目標覆蓋閾值。每次循環需要遍歷所有未加入覆蓋集的網格點，找出使覆蓋概率提高最多的點加入覆蓋集，之后更新當前所有點的覆蓋概率，該過程的時間復雜度為O(n2)。循環的執行次數要根據實際選取的節點感知半徑還有網格大小決定，最壞情況總的時間復雜度為O(n3)。

3 實驗仿真與結果分析

實驗采用MATLAB進行仿真，在如圖5所示的三維表面進行節點的部署。

圖5 三維表面

3.1 實驗仿真參數設置

實驗過程中的參數值設置如表1所示。二維平面大小指圖5所示的三維表面垂直投影到平面上形成的區域大小。

3.2 仿真結果及分析

圖6是把二維平面劃分成50×50個網格，利用本文提出的覆蓋策略進行實驗得出的節點部署位置。該圖是節點投影到二維平面上形成的圖，圖中節點分布比較密集的部分是山體區域，該區域坡度比較大，映射到平面后，相應的覆蓋半徑比較小，因而部署密集。而在平原地區，節點的部署比較稀疏。

圖6 覆蓋集節點分布圖

下面考慮網格劃分大小對覆蓋集大小的影響，如圖7所示。

圖7 覆蓋集和網格點關系圖

圖7中橫坐標表示劃分成的網格的粒度，例如，50表示劃分成50×50個網格，縱坐標表示覆蓋集的大小。隨著網格數的增加，覆蓋集的大小基本在97個左右波動。網格劃分得越細越能表現三維的地形特征，從而得出的覆蓋集更具有實際意義。

4 結 語

為了解決三維表面上的確定性部署問題，本文提出基于方向梯度的覆蓋算法進行求解。目前，關于二維平面和三維空間上的覆蓋問題的研究很多，但是基于三維表面的研究很少。本文提出的基于方向梯度的覆蓋算法為該類問題提供了一種可行性方案，利用區域離散化方法近似表示目標區域，再用貪婪算法求出了三維表面的覆蓋集，并通過仿真實驗驗證了該方法在三維表面環境中是正確并且可靠的。

[1] Unaldi N,Temel S.Wireless Sensor Deployment Method on 3D Environments to Maximize Quality of Coverage and Quality of Network Connectivity[C]//World Congress on Engineering and Computer Science,2014.

[2] 陳樹,季忠軍.復雜三維曲面覆蓋算法研究[J].計算機工程與應用,2016,52(20):127-131.

[3] Feng L,Sun Z,Qiu T.Genetic Algorithm-Based 3D Coverage Research in Wireless Sensor Networks[C]//Seventh International Conference on Complex,Intelligent,and Software Intensive Systems.IEEE,2013:623-628.

[4] Liu L,Ma H.On Coverage of Wireless Sensor Networks for Rolling Terrains[J].IEEE Transactions on Parallel & Distributed Systems,2012,23(1):118-125.

[5] 劉曄,傅忠謙.基于地形修正的無線傳感器網絡陷阱空洞檢測[J].傳感技術學報,2014(6):785-790.

[6] Zhao M C,Lei J,Wu M Y,et al.Surface coverage in wireless sensor networks[J].Proceedings-IEEE INFOCOM,2009,39(3):109-117.

[7] Zou Y,Chakrabarty K.Sensor deployment and target localization based on virtual forces[C]//Joint Conference of the IEEE Computer and Communications.IEEE Societies.IEEE,2003,2:1293-1303.

[8] 趙銘辰.無線傳感器網絡表面覆蓋問題的研究[D].上海交通大學,2010.

AMETHODOFCOVERAGEINTHREE-DIMENSIONALWSNBASEDONDIRECTIONALGRADIENT

Wang Dandan Xu Tingrong

(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)

Aiming at the problem of 3D surface coverage in wireless sensor networks, a coverage algorithm based on directional gradient is proposed. First, the 3D surface was projected onto the 2D plane directly by the projection method. Then, the 2D plane was divided into a number of grids and each grid was considered as a grid point by the way of zone discretization. Next the actual sensing radius of each direction was decided by the directional gradient probability sensing model. Finally, we found the minimal cover set satisfying the coverage rate using the greedy algorithm. In this method, the directional gradient probability sensing model was adopted, which fully considered the influence of the 3D surface topography and the attenuation factor of the sensing range in the practical application. A large number of simulation experiments show that the proposed algorithm can effectively cover the 3D terrains.

WSN 3D Coverage Directional gradient

TP393

A

10.3969/j.issn.1000-386x.2017.09.028

2016-11-06。國家自然科學基金項目(61472469)。王丹丹，碩士生，主研領域：無線傳感器網絡。徐汀榮，教授。