基于CVT模型的無線傳感器網絡覆蓋優化*

項馨儀， 趙杰煜， 劉 超

(寧波大學 信息科學與工程學院，浙江 寧波 315211)

0 引 言

覆蓋性能是衡量無線傳感器網絡(wireless sensor networks，WSNs)[1]的重要技術指標，能夠描述網絡服務質量和網絡感知能力[2～4]?；谟嬎銕缀螌W中的Voronoi圖[5～7]來提高網絡覆蓋效率獲得廣泛的關注和應用。Lee H J等人[8]提出了基于Voronoi圖形質心的部署策略(centroid-based scheme，CBS)，通過使用Voronoi多邊形及其重心(幾何中心)來修復覆蓋問題。但CBS無法確保Voronoi多邊形的形心位于Voronoi多邊形內盲區的中心位置，其覆蓋效率有待提升。Mahboubi H[9,10]利用Voronoi圖設計了一種基于Minimax 算法和Voronoi圖邊界的Maxmin-Edge 的混合部署策略(vertex-edge based strategy，VEDGE)，取二者計算結果中覆蓋率較高的位置作為節點移動的目標位置。方偉[11]提出了基于Voronoi盲區多邊形質心的覆蓋控制部署策略(blind-zone centroid-based scheme，BCBS)，將Voronoi盲區多邊形的形心替代作為傳感器節點移動的候選目標區域來提高網絡覆蓋率。劉志強等人[12]結合Lloyd算法基于Voronoi圖和質心化的Voronoi圖(centroidal voronoi tessellation，CVT)理論，通過調整目標覆蓋區域邊界或調度傳感器節點改變覆蓋效率，實現了靜態和動態邊界區域的有效覆蓋。上述方法的實驗結果中并未出現100%的覆蓋率；仍可進行改進。

本文通過結合CVT模型和圓覆蓋思想，設計并實現了一種WSNs的覆蓋性能增強算法，通過移動WSNs節點有效地提高網絡覆蓋能力，可以實現網絡100 %覆蓋。

1 基于CVT模型的WSNs覆蓋優化算法

1.1 模型假設

假設N只傳感器節點S隨機部署在一個大小為L×W的二維矩形平面T內，在WSNs準覆蓋區域T范圍內合理布置傳感器節點和劃分區域，可使網絡覆蓋率最大化。假設：1)無線傳感器節點集S={s1,s2,…,sN}，所有節點具有相同的感知半徑Rs和通信半徑Rc，每個節點的位置記為si=(xi,yi)。

2)Rc為Rs的2倍，移動傳感網絡具有連通性。

3)節點可以在二維平面上自由移動，并且具有足夠的能量移到指定固定位置停止移動。

4)將準覆蓋區域T離散化為a×b個目標節點，每個傳感器節點的位置記為tj=(xi,yj)，其中j∈[1,a×b]。

定義1采用圓盤感知模型計算目標節點被傳感器節點覆蓋的概率。假設目標節點tj和傳感器節點si之間的距離為

(1)

傳感器節點能夠覆蓋到目標節點的概率如下：

若d(si,tj)≤Rs，則目標節點被該區域傳感器節點覆蓋，傳感器節點對目標節點的感知概率記為1；否則,目標節點未被覆蓋，傳感器節點對目標節點的感知概率記為0。

定義2分布均勻性U,指傳感器節點覆蓋是否均勻，是某節點與其鄰居節點之間的距離標準差,值越小代表傳感器節點分布的覆蓋均勻性越好。

定義3覆蓋效率(coverage efficiency,CE)用于衡量WSNs覆蓋范圍的利用率，為節點已覆蓋有效范圍的并集與每個節點劃分的區域面積總和之比，即

(2)

CE越大，傳感器節點覆蓋效率越高。

1.2 問題描述

由模型假設可知每個傳感器節點都能夠獲取自身位置和感知范圍，節點在移動過程中其感知范圍(覆蓋圓)和Voronoi區域形成如下關系：1)覆蓋圓包含了Voronoi區域，感知范圍與Voronoi頂點存在一個或多個交點；2)Voronoi區域可能包含了覆蓋圓，此時感知范圍與Voronoi多邊形可能無交點；3)隨機部署的傳感器節點的感知范圍可能存在重疊情況，不同的覆蓋圓相交。

受Voronoi圖啟發來解決傳感器節點覆蓋區域存在覆蓋空洞和重疊覆蓋等問題:1)將傳感器節點簡化為圓心，其覆蓋范圍假設為一個圓;2)依據Voronoi圖劃分準覆蓋區域，可以得到傳感器節點所處位置對應的多個Voronoi多邊形;3)通過一定規則移動傳感器節點，其對應的圓隨即變化位置和大小，直至覆蓋圓完全覆蓋準覆蓋區域,停止移動傳感器節點。

Vi={x∈Ω|d(x,xi)≤d(x,xj),?j≠i}

(3)

如圖1所示，采用Voronoi圖和圓覆蓋結合的方式構建了20個移動傳感器節點模型示例。其中，矩形區域為WSNs準覆蓋區域，實心點為移動傳感器節點，實線覆蓋圓為每個傳感器節點的感知圓盤，多邊形區域為每個實心點構建的Voronoi區域。將無線傳感網絡準覆蓋區域劃分成若干個Voronoi區域，可以較好地呈現覆蓋情況。

圖1 移動傳感器節點覆蓋模型示意圖

1.3 基于CVT模型的WSNs覆蓋優化算法

普通的Voronoi圖只能研究固定的靜態傳感器節點網絡覆蓋情況，針對移動傳感網絡引進CVT，定義為每個Voronoi區域的生成點是在該Voronoi區域上的質心，即

(4)

式中V為區域；x為生成點;ρ(x)>0為定義在區域Ω的密度函數。已知傳感器節點集合{ci|i=1,2,…,n|，集合中的每一個點表示一個Voronoi區域Ωi?Ω。一個非常明顯的結論是：準覆蓋區域的外接圓的半徑的上確界即為覆蓋圓。

針對網絡覆蓋問題的優化方法是迭代更新上一次的候選傳感器節點對應的Voronoi區域的外接圓的圓心。問題求解的目標是優化傳感器節點{ci}的位置，使覆蓋圓盤的半徑達到極限。更確切的表述如下問題：給定一個二維區域的最優覆蓋，求解已知數目的覆蓋圓盤的最小半徑，根據數學理論推導，定義覆蓋圓盤的半徑R如下

(5)

理論上，準覆蓋區域Ω可近似為ε-dense的采樣集合。外接圓心Ωi等價于針對Ωi的采樣點集合求解的Voronoi圖的其中一個頂點。通過針對準覆蓋區域點集不斷迭代求解半徑逐漸增大的封閉圓盤，直到所求的圓盤完全覆蓋準覆蓋區域內所有的點。

1.4 算法描述

1)確定帶有邊界的準覆蓋區域(歐氏空間)T，給定的覆蓋圓盤數目n。

2)對準覆蓋區域通過離散采樣技術得到采樣點集合{sj}，以此實現近似Voronoi區域的表達。在生成采樣點集{sj}中，設定公差ε控制采樣點集的密度。

3)對準覆蓋區域進行Voronoi圖劃分，將劃分后得到所有Voronoi圖區域的集合記為V，V={v1,v2,…,vN}。針對點集{sj}構建三角剖分，以便于任意兩點間的歐氏距離的查找訪問。

8)保存求解的圓心半徑、覆蓋圓盤半徑和覆蓋結果。

2 實驗與結果分析

2.1 實驗環境配置

根據準覆蓋區域進行離散采樣初始化數據，同時初始化覆蓋圓盤的數目和初始圓心，以及設定程序終止條件；對準覆蓋區域進行Delaunay三角化；進行迭代求解。搭建的實驗環境平臺是Windows 7系統，英特爾雙核處理器、2.4 GHz主頻、6 GB內存的計算機，以C++編程實現。

2.2 實驗結果分析

實驗結果中，以9個節點覆蓋方形區域和8個節點覆蓋圓形區域為例，準覆蓋區域的離散表示、迭代過程和求解結果如圖2和圖3所示。

圖2(a)給出了節點對方形準覆蓋區域的網絡覆蓋情況，以離散技術對準覆蓋區域進行充分采樣并初始化節點位置，灰色點表示該子區域內的采樣點集，黑色點表示節點隨機初始位置。圖2(b)為節點覆蓋過程的中間迭代。本文算法具有較快的收斂性，當節點少于5時，迭代2次基本能夠達到90 %以上的覆蓋率；給定數目較多的節點，迭代10次可以基本達到理想的覆蓋率。每個節點對應的Voronoi區域大小隨著迭代次數的增加會趨于均勻。覆蓋結果如圖2(c)所示，節點覆蓋率隨著迭代次數的增加大幅提高，最終達到了100 %，可以直觀看出節點分布趨于均勻，此時每個Voronoi區域面積基本一致。

圖2 方形區域的覆蓋過程

圖3給出了8個節點對圓形區域的覆蓋過程，證明區域形狀的多樣性未對本算法產生影響。

圖3 圓形區域的覆蓋過程

根據實驗結果，不同數目的圓盤個數實現準覆蓋區域的覆蓋情況如表1所示，N為圓盤的個數，R為圓盤的半徑，D為對準覆蓋區域的覆蓋率?？梢钥闯觯涸谕瑯拥臏矢采w區域，隨著節點數目增加，圓盤平均半徑不斷減小，對準覆蓋區域的最終覆蓋率均能達到100 %。與文獻[7，11]對比，本算法覆蓋率優于基于連通性BCBS(connectivity considered BCBS，CC-BCBS)算法和BCBS算法。

表1 不同數目節點的覆蓋效率表

3 結束語

通過實驗表明:該模型能夠調整移動傳感器節點至最佳位置，合理劃分準覆蓋區域，有效提高準覆蓋區域網絡覆蓋率至100 %，減少網絡擁塞和覆蓋盲區，提供了更高的網絡通信服務。本文忽略了外部復雜環境因素對傳感器節點規劃的影響，下一步要做的工作是將算法進行改進，使其適合更復雜環境下的移動傳感網絡的覆蓋優化。

參考文獻:

[1] 仲元昌,陳 鋒,李發傳,等.大規模無線傳感器網絡覆蓋優化算法[J].傳感器與微系統,2014,33(11):117-120.

[2] 凡高娟,郭拯危.無線傳感器網絡節點部署研究進展[J].傳感器與微系統,2012,31(4):1-3.

[3] Li F,Luo J,Xin S,et al.Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing mo-del[J].Computer Networks,2016,108(10):120-132.

[4] 祁育仙,李國勇.混合WSNs中基于多目標優化的覆蓋控制算法[J].傳感器與微系統,2016,35(2):136-139.

[5] Du Q,Gunzburger M,Ju L.Advances in studies and applications of centroidal voronoi tessellations[J].Numerical Mathematics Theory Methods & Applications,2010,3(2):119-142.

[6] Abo-Zahhad M,Sabor N,Sasaki S,et al.A centralized immune-Voronoi deployment algorithm for coverage maximization and energy conservation in mobile wireless sensor networks[J].Information Fusion,2016,30(C):36-51.

[7] 梅希薇,宋鑫宏,方 偉.基于連通性的無線傳感器網絡覆蓋優化算法[J].傳感器與微系統,2017,36(5):145-148.

[8] Lee H J,Kim Y H,Han Y H,et al.Centroid-based movement assisted sensor deployment schemes in wireless sensor net-works[C]∥Vehicular Technology Conference,IEEE,2009:1-5.

[9] Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for improved coverage in mobile sensor net-works[J].IEEE Transactions on Industrial Informatics,2011,10(6):1244-1249.

[10] Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J].IEEE Transactions on Industrial Informatics,2014,10(1):163-174.

[11] 方 偉,宋鑫宏.基于Voronoi圖盲區的無線傳感器網絡覆蓋控制部署策略[J].物理學報,2014,63(22):128-137.

[12] 劉志強,沈廼桐,毛 強,等.無線傳感器網絡動態覆蓋的CVT算法[J].傳感器與微系統,2015,34(6):115-118.