神顯豪，李　軍，奈　何（桂林理工大學信息科學與工程學院，廣西桂林541004）

?

基于三維地形修正的無線傳感器網絡覆蓋盲區(qū)檢測*

神顯豪*，李軍，奈何
（桂林理工大學信息科學與工程學院，廣西桂林541004）

摘要：三維地形下傳感器節(jié)點經隨機部署后，由于地形起伏的特點，會導致覆蓋盲區(qū)的產生。為了能夠有效檢測覆蓋盲區(qū)，本文提出了一種基于三維地形修正的無線傳感器網絡覆蓋盲區(qū)檢測方法，通過建立單位球感知模型，隨機部署傳感器節(jié)點，對節(jié)點進行Delaunay三角剖分。計算出三角形的外接圓，根據邊界檢測算法求出覆蓋盲區(qū)邊界，并且剔除假邊界節(jié)點，得出改善后的邊界。計算傳感器節(jié)點的坡度和坡向信息，根據地形修正原理計算出傳感器節(jié)點的實際探測半徑，最終得出覆蓋盲區(qū)的最小邊界。仿真實驗結果驗證了該檢測方法可有效檢測三維地形下的覆蓋盲區(qū)，對于起伏較大的地形也有一定的適應性。

關鍵詞：覆蓋盲區(qū)；三維地形修正；坡度和坡向；Delaunay三角剖分；外接圓

無線傳感器網絡WSN（Wireless Sensor Net?work）是由大量廉價的微型傳感器節(jié)點隨機部署在某一需要監(jiān)測的區(qū)域，通過無線通信的方式自組織而形成的網絡系統(tǒng)［1］。覆蓋性能是衡量WSN服務質量的關鍵指標，不斷改進和提高覆蓋性能成為近年來研究的主要熱點，覆蓋盲區(qū)（或空洞）的修復是其中的一個重要研究內容。在目標區(qū)域中，傳感器節(jié)點采用隨機部署，導致部分監(jiān)測區(qū)域沒有傳感器節(jié)點，從而出現(xiàn)覆蓋盲區(qū)（或覆蓋空洞），嚴重影響網絡的性能。另外，隨著網絡的運行，傳感器節(jié)點的能量耗盡也會導致覆蓋盲區(qū)的形成。因此，當網絡中出現(xiàn)覆蓋盲區(qū)時，應該立即被檢測到，維持WSN的完整性和可靠性［2］。

目前對于WSN覆蓋盲區(qū)的研究，許多研究者提出了一些解決方法。如高昊，王慶生，馮秀芳等人［3］，提出一種基于幾何圖形的分布式覆蓋盲區(qū)發(fā)現(xiàn)算法，該算法根據幾何圖形學的相關理論判斷節(jié)點附近是否存在覆蓋盲區(qū)；李明義，陳俊杰提出的無線傳感器網絡中覆蓋空洞的檢測算法［4］，根據無線傳感器網絡的覆蓋空洞是由邊界弧包圍的，通過計算覆蓋空洞的邊界節(jié)點和邊界弧，進而檢測到覆蓋空洞；戴國勇，陳麓屹，周斌彬等人提出的基于Voronoi圖的無線傳感器網絡覆蓋空洞檢測算法［5］，該算法利用節(jié)點的位置信息在覆蓋區(qū)域范圍內構建Voronoi圖，通過計算每個Voronoi區(qū)域內的節(jié)點到該區(qū)域的頂點和邊的距離來判斷是否存在覆蓋空洞；邢冬平，段富，樊茂森提出的基于極坐標的無線傳感器網絡覆蓋盲區(qū)發(fā)現(xiàn)算法［6］，該算法運用極坐標來表示節(jié)點之間的關系，通過幾何算法來檢測無線傳感網絡中是否存在覆蓋盲區(qū)。上述的幾種算法都屬于二維平面的覆蓋盲區(qū)檢測方法，并不適用于三維地形。劉曄，傅忠謙［7］提出一種基于數(shù)字高程地圖坡度信息的地形修正方法，通過構建傳感器節(jié)點方向梯度感知模型，實現(xiàn)起伏地形下的陷阱空洞檢測。但是該方法只適用于坡度變化平緩的三維起伏地形，對于起伏較大的三維地形并不適用。

在上述研究的理論基礎上，本文針對更實際的三維起伏地形，提出了基于三維地形修正的WSN覆蓋盲區(qū)檢測方法，該方法能夠有效的檢測目標區(qū)域中的覆蓋盲區(qū)。

1　覆蓋盲區(qū)的形成

在WSN研究中，覆蓋問題是基本問題之一，它影響到WSN的工作效率和質量。覆蓋問題的核心是網絡中傳感器節(jié)點通過收集信息來實現(xiàn)對目標區(qū)域的監(jiān)測和感知。通過合理的部署網絡中的傳感器節(jié)點，在保證滿足相關的網絡服務質量的要求下，最大程度的對監(jiān)測區(qū)域進行覆蓋。通常情況下，部署方式采取隨機部署，傳感器節(jié)點隨機播散在目標區(qū)域中。然而這種方式很難一次把多個傳感器節(jié)點的位置部署合理，導致網絡覆蓋不合理，最后形成感知重疊區(qū)和盲區(qū)［8］。如圖1所示，二維平面的覆蓋研究方法不能應用于三維平面，三維地形下的傳感器節(jié)點經隨機部署后，由于三維地形的起伏特點，會導致覆蓋盲區(qū)的產生［9］。

由圖1可知，投影到二維平面上的傳感器節(jié)點實現(xiàn)了全覆蓋。然而，傳感器節(jié)點只能被放置在地表面，在三維地形表面上仍然存在覆蓋盲區(qū)。

圖1　覆蓋盲區(qū)的截面圖

2　網絡模型與度量

2.1建立單位球感知模型

假設：目標區(qū)域是三維空間類的一個凸表面S，在笛卡爾積坐標系統(tǒng)中S可以表示為一個單值函數(shù)z=h(x，y)，當且僅當函數(shù)為z=c，c為常數(shù)時S為平面。一個傳感器si被放置在目標區(qū)域S中，當傳感器的坐標滿足目標區(qū)域S的方程時，那么si∈S。

本文采用單位球感知模型，假設在三維的歐幾里得空間中每個傳感器的感知半徑r都相同，每個傳感器可以通過自己的感知范圍感知和探測事件。這樣感知區(qū)域形成了一個在三維空間中以si為中心，r為半徑的球體。單位球模型的二維平面如圖2所示。

圖2　單位球模型的二維平面

2.2傳感器部署模型

傳感器節(jié)點在目標區(qū)域的隨機部署［10］，考慮了表面泊松點分布部署模型。假設n個傳感器是均勻分布的，目標區(qū)域的面積S→∞，那么就能得到泊松分布的參數(shù)［11］：

那么m個傳感器位于面積為G的傳感器集合中的概率為：

2.3坡度與坡向的定義

坡度是三維地形表面陡緩的程度，通常把坡面的垂直高度和水平距離的比叫做坡度，即坡角的正切值。坡向是坡面法線在水平面上的投影的方向，亦高程下降最快的方向。三維地形表面上的傳感器節(jié)點實際覆蓋面可以等效成平面。在笛卡爾積坐標系中，通過AB線段為直徑的圓來表示坡度和坡向，如圖3所示。

圖3　AB段的坡度和坡向

其中，P點為三維凸曲面上的一點，PQ為AB段的法線，q為Q在XY平面上的投影，Oq為PQ在XY平面上的投影，α為法線PQ與Z軸的夾角，同時∠PBO=α，即坡度為I=tan α。β是Oq與OB的夾角，即坡向。γ為點P在β方向上的坡度。

通過GIS軟件，從DEM地圖數(shù)據中提取高程數(shù)據和坡度信息，在曲面z=h(x，y)上，對于點p(x，y)方向梯度為：

單位矢量，方向梯度的模為坡度。

點P沿著β方向的坡度G為：

由式（4）、式（5）可知：

圖3中，AB段為直徑，即|AB|=2r。由于三維地形的起伏特點，傳感器節(jié)點沿β方向的實際探測半徑r’與理想探測半徑r的關系可表示為：

2.4地形修正原理

如圖4所示，在50 m×50 m的區(qū)域中，隨機部署40個傳感器節(jié)點。圖中給出了高程數(shù)值為100 到150的等高線。

圖4　地形修正原理

已知傳感器節(jié)點坐標，可計算出每個節(jié)點的坡度和坡向角。沿著坡向方向，節(jié)點相交的兩條等高線之間的差值，即高度差為Δh。相交的兩條等高線之間的距離為Δd，那么坡度I可以表示為：

可以根據公式（8）算出實際探測半徑。最終算出三維地形下每個傳感器節(jié)點在二維平面上的橢圓投影，達到地形修正的目的。

2.5Delaunay三角形剖分

在目標區(qū)域內，以傳感器節(jié)點為頂點對目標區(qū)域進行Delaunay三角剖分。假設V是二維實數(shù)域上的有限點集，e是點構成的封閉線段，e的集合為E。那么點集V的一個三角剖分T=(V，E)是一個平面圖G，該平面圖滿足條件：①除端點外，平面圖G中的邊不包含點集V中的其他任何點。②沒有相交邊。③平面圖G中所有的面都是三角面，并且所有三角面的合集是點集V的凸包。若存在一個圓經過V中a，b兩點，并且圓內不含其他的點，則稱ab邊為Delaunay邊。如果V的一個三角剖分T只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分［12］。

2.6外接圓

每個Delaunay三角形的外接圓都是不包括其他Delaunay三角形的任何頂點的圓［13］。假定a，b，c 是Delaunay三角形的三條邊，S是三角形的面積，（x，y）為外接圓的圓心，如圖5所示。

圖5　外接圓

外接圓半徑R表示為：

Android操作系統(tǒng)維護著自己的一套事件分發(fā)機制，Android應用程序、觸發(fā)事件和后臺邏輯處理，都是根據該機制一步步向下執(zhí)行，惡意軟件的敏感行為也不例外。若能在事件傳送到終點前將事件截獲并對其操作進行一定修改，就可以有效地抑制惡意行為的效果，這就是Hook機制。

假定三條邊的坐標分別是（x1，y1），（x2，y2），（x3，

y3），那么外接圓的圓心坐標（x，y）可表示為：

2.7邊界節(jié)點和假邊界節(jié)點

在覆蓋盲區(qū)的邊界上，能夠包圍覆蓋盲區(qū)的節(jié)點稱為邊界節(jié)點［14］。然而這些邊界節(jié)點中存在著假邊界節(jié)點。假定覆蓋盲區(qū)邊界中Delaunay三角形的三個頂點分別是S1，S2，S3，如圖6、圖7所示。

圖6　邊界節(jié)點

圖7　假邊界節(jié)點

因為覆蓋盲區(qū)是在Delaunay三角形之外的部分，圖6中存在部分區(qū)域未被任何節(jié)點覆蓋，如陰影部分所示，所以S1，S2，S3都是邊界節(jié)點。然而圖7 的Delaunay三角形中沒有未被覆蓋的區(qū)域，所以S1和S2節(jié)點是邊界節(jié)點，而S3是假邊界節(jié)點。

假邊界節(jié)點的判定如下：假設S1，S2，S33個節(jié)點的感知半徑為r，外接圓的圓心為Oc，外接圓半徑為R。圖中O1為S1和S3的垂直平分線與S2的交點，同理O2為S2和S3的垂直平分線與S1和S2的交點，直線S3O3垂直于直線S1S2，如圖8所示。如果S3O1>r或者S3O2>r，那么在ΔS1S2S3中肯定存在一些覆蓋盲區(qū)。如果S3O1>r、S3O2>r并且S3O3<=r，那么在ΔS1S2S3中存在兩個分離的覆蓋盲區(qū)。

圖8　假邊界節(jié)點的判定

對于外接圓圓心在Delaunay三角形外面并且R>r的邊界節(jié)點，利用假邊界節(jié)點的判定方法，判斷Delaunay三角形內部是否被節(jié)點全覆蓋。如果Delaunay三角形中不存在覆蓋盲區(qū)，那么Delaunay三角形中最長邊對應的節(jié)點為假邊界節(jié)點。

3　覆蓋盲區(qū)的檢測算法和地形修正

傳感器節(jié)點隨機部署在目標區(qū)域中，可能會存在覆蓋盲區(qū)。通過Delaunay三角形剖分算法對傳感器節(jié)點中心點進行三角形劃分。根據每個De?launay三角形的坐標來算出自身的外接圓。假設傳感器節(jié)點半徑為r，每個外接圓的半徑為R，相鄰兩個Delaunay三角形的公共邊長為d，檢測算法如下：①將N個傳感器節(jié)點隨機部署在目標區(qū)域中，對每個節(jié)點的中心點進行Delaunay三角形剖分。②做出每個Delaunay三角形的外接圓。比較節(jié)點半徑和外接圓半徑，如果R>r，那么肯定存在覆蓋盲區(qū)，保存下這個Delaunay三角形和外接圓，否則去掉外接圓。③計算剩余兩個相鄰三角形的公共邊長d。如果d>2r，或者公共邊不與兩個三角形外接圓的中心連線相交，那么對這些三角形進行聚類分組得到邊界節(jié)點，每個聚類分組都會存在覆蓋盲區(qū)。④對每個聚類分組中的傳感器節(jié)點（邊界節(jié)點）中心點，用能夠包含覆蓋盲區(qū)的最小多邊形的方法，表示出覆蓋盲區(qū)邊界。⑤對邊界節(jié)點進行假邊界節(jié)點的判定，去掉假邊界節(jié)點之后，再次用能夠包含覆蓋盲區(qū)的最小多邊形方法，表示出覆蓋盲區(qū)的邊界。⑥由于三維地形的起伏特點，傳感器節(jié)點隨機部署在目標區(qū)域的實際覆蓋面積會變小，經過地形修正的傳感器節(jié)點的二維覆蓋區(qū)域為橢圓。利用坡度和坡向角算出實際半徑，最后使用檢測算法求出修正后的覆蓋盲區(qū)邊界。

4　仿真評估

4.1表面的生成

論文采用MATLAB 2012b仿真平臺來進行仿真。為了表示表面的覆蓋性能，我們用單值函數(shù)z=h(x，y)，來表示生成的表面。

其中x和y∈［0，50］，系數(shù)C=1，2，3時生成曲面。在［0，50］×［0，50］m的區(qū)域中，曲面有1，4，9個頂峰和低谷。圖9~圖11為曲面的等高線，單位為米。圖中標注了每條等高線的數(shù)值。

圖9　C=1時的等高線

圖10　C=2時的等高線

圖11　C=3時的等高線

4.2仿真結果對比

假設在50 m×50 m的區(qū)域內，隨機部署的傳感器節(jié)點數(shù)N=40，節(jié)點的理想探測半徑為r=6。每個Delaunay三角形的外接圓半徑為R。仿真參數(shù)如表1所示。對40個傳感器節(jié)點的中心點進行Delaunay三角剖分，可以得到多個Delaunay三角形。如圖12所示。其中圓形區(qū)域表示節(jié)點的覆蓋區(qū)域。

表1　仿真參數(shù)

圖12　Delaunay三角剖分

已知Delaunay三角形的頂點坐標，可以求出每個三角形的外接圓半徑R和外接圓心。如圖13所示，如果R>r時，表示存在覆蓋盲區(qū)。

圖13　Delaunay三角形的外接圓

根據覆蓋盲區(qū)邊界的檢測算法，對符合條件的Delaunay三角形進行聚類分組。分組得到多個邊界節(jié)點之后，用能夠包含覆蓋盲區(qū)的最小多邊形的方法來表示出覆蓋盲區(qū)的邊界，如圖14所示。

圖14　覆蓋盲區(qū)的邊界

去掉邊界節(jié)點中存在的假邊界節(jié)點，得出改善的盲區(qū)邊界。如圖15所示。

圖15　去掉假邊界節(jié)點后的邊界

根據地形起伏程度，如表2所示，設置了3種地形。對三維起伏地形進行地形修正之后，得出覆蓋盲區(qū)邊界。

表2　地形參數(shù)

在地形I，II，III的情況下，地形修正后覆蓋盲區(qū)的邊界如圖16~圖18所示。

圖16　地形I的修正結果

圖17　地形II的修正結果

圖18　地形III的修正結果

在區(qū)域范圍相同、節(jié)點數(shù)目相同的情況下，隨著頂峰和低谷數(shù)增加，地形起伏程度逐漸增大。由上述地形I、地形II和地形III修正結果對比可知，隨著地形起伏程度增大，盲區(qū)面積逐漸增大，導致覆蓋邊界逐漸增大，WSN的覆蓋率逐漸下降。仿真結果表明，該結果在起伏較大的地形情況下同樣適用。

為了進一步評價三維地形修正方法的性能，在相同的仿真實驗條件下，與未去掉假邊界節(jié)點的傳統(tǒng)修正方法［7］進行對比，其中“平面”表示傳感器節(jié)點隨機部署后未進行地形修正的覆蓋率，仿真對比如圖19所示。

圖19　與傳統(tǒng)修正方法的仿真對比

由圖19可知，傳統(tǒng)修正方法和三維地形修正方法隨著地形起伏程度增大，經地形修正后的覆蓋率均逐漸下降。三維地形修正方法在三種地形下的覆蓋率均低于傳統(tǒng)修正方法，說明它能檢測出目標區(qū)域中更多的覆蓋盲區(qū)。因此，三維地形修正方法對覆蓋盲區(qū)的檢測效果更好，更適用于起伏較大的三維地形。

5　結論

對于三維地形起伏的特點，本文提出了一種基于三維地形修正的WSN覆蓋盲區(qū)檢測方法。通過覆蓋盲區(qū)邊界檢測算法，求出目標區(qū)域的覆蓋盲區(qū)邊界，經過地形修正后得出最終的覆蓋盲區(qū)邊界。仿真實驗結果表明，地形修正后的覆蓋盲區(qū)邊界明顯變大，該結果在三維起伏較大的地形條件下得出，對三維起伏地形下的傳感器節(jié)點部署具有參考價值。

參考文獻：

［1］王偉，林鋒，周激流.無線傳感器網絡覆蓋問題的研究進展［J］.計算機應用研究，2010，27（1）：32-35.

［2］胥楚貴，鄧曉衡，鄒豪杰.無線傳感器網絡覆蓋空洞修復策略［J］.傳感技術學報，2010，23（2）：256-259.

［3］高昊，王慶生，馮秀芳，等.無線傳感器網絡中覆蓋盲區(qū)發(fā)現(xiàn)算法［J］.傳感器與微系統(tǒng)，2012，31（9）：109-115.

［4］李明義，陳俊杰.無線傳感器網絡中覆蓋空洞的檢測算法［J］.計算機測量與控制，2013，21（9）：2501-2505.

［5］戴國勇，陳麓屹，周斌彬，等.基于Voronoi圖的無線傳感器網絡覆蓋空洞檢測算法［J］.計算機應用，2015，35（3）：620-623.

［6］邢冬平，段富，樊茂森.基于極坐標的無線傳感器網絡覆蓋盲區(qū)發(fā)現(xiàn)算法［J］.傳感器與微系統(tǒng)，2014，33（9）：117-119.

［7］劉曄，傅忠謙.基于地形修正的無線傳感器網絡陷阱空洞檢測［J］.傳感技術學報，2014，27（6）：785-790.

［8］Xiao Yang L，Kai Liang W，Yanmin Z，et al. Mobility Increases the Surface Coverage of Distributed Sensor Networks［J］. Comput?er Networks，2013，57：2348-2361.

［9］劉志坤，夏清濤，羅浩.無線傳感器網絡三維覆蓋策略研究［J］.武漢理工大學學報（交通科學與工程版），2013，37（3）：581-584.

［10］李猛，丁代榮，郭廷立.一種無線傳感器網絡節(jié)點隨機部署策略［J］.計算機工程，2012，38（5）：99-101.

［11］徐奕昕，白焰，趙天陽，等.泊松分布下無線傳感器網絡多目標覆蓋控制［J］.計算機應用，2013，33（7）：1820-1824.

［12］余杰，呂品，鄭昌文. Delaunay三角網構建方法比較研究［J］.中國圖象圖形學報，2010，15（8）：1158-1167.

［13］Hwa Chun M，Prasan Kumar S，Yen Wen C. Computational Geom?etry Based Distributed Coverage Hole Detection Protocol for the Wireless Sensor Networks［J］. Journal of Network and Computer Applications，2011，34：1743-1756.

［14］Wei L，Wei Z. Coverage Hole and Boundary Nodes Detection in Wireless Sensor Networks［J］. Journal of Network and Computer Applications，2015，48：35-43.

神顯豪（1980-），男，廣西南寧橫縣人，博士，桂林理工大學副教授，主要研究方向為智能故障診斷、無線傳感器網絡，lyj_sxh@sina.com；

李軍（1990-），男，安徽滁州市人，桂林理工大學碩士研究生，研究方向為無線傳感器網絡，leejun19901113@163.com；

奈何（1992-），男，湖北省襄陽市人，桂林理工大學碩士研究生，研究方向：無線傳感器網絡，985515263@qq.com。

Research on the Capacity of Wireless Networks Based on the Network Coding*

MENG Limin*，ZHANG Jing，ZHOU Kai，YING Songxiang
（College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China）

Abstract：The network capacity has been a hotspot in the field of wireless network. Network coding has the advan?tage that the intermediate node can encode the data it receives，which can efficiently improve end-to-end through?put. In this paper，we first analyze the multi-hop capacity of wireless network based on the signal-to-interference ra?tio model proposed by Gupta. Then an algorithm of wireless network capacity based on the network coding is pro?posed and to compute the upper bound of the network capacity，we obtain the network maximum flow and each link flow by utilizing the method which solves linear programming problems in the MATLAB. The simulation experi?ments show that the capacity using network coding is higher than that of traditional routing strategy and the upper bound of network capacity has a trend of first increasing and then decreasing with the number of nodes.

Key words：wireless network；network capacity；network coding；max-flow min-cut theorem

doi：EEACC：723010.3969/j.issn.1004-1699.2016.01.020

收稿日期：2015-08-12修改日期：2015-09-20

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）01-0109-07

項目來源：國家自然科學基金項目（E050603）；廣西高等學?？蒲许椖浚╕B2014157）；廣西自然科學基金項目（2015GXNSFBA139254）