基于CVT模型的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化*

項(xiàng)馨儀， 趙杰煜， 劉 超

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

0 引 言

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

本文通過結(jié)合CVT模型和圓覆蓋思想，設(shè)計(jì)并實(shí)現(xiàn)了一種WSNs的覆蓋性能增強(qiáng)算法，通過移動(dòng)WSNs節(jié)點(diǎn)有效地提高網(wǎng)絡(luò)覆蓋能力，可以實(shí)現(xiàn)網(wǎng)絡(luò)100 %覆蓋。

1 基于CVT模型的WSNs覆蓋優(yōu)化算法

1.1 模型假設(shè)

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

2)Rc為Rs的2倍，移動(dòng)傳感網(wǎng)絡(luò)具有連通性。

3)節(jié)點(diǎn)可以在二維平面上自由移動(dòng)，并且具有足夠的能量移到指定固定位置停止移動(dòng)。

4)將準(zhǔn)覆蓋區(qū)域T離散化為a×b個(gè)目標(biāo)節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)的位置記為tj=(xi,yj)，其中j∈[1,a×b]。

定義1采用圓盤感知模型計(jì)算目標(biāo)節(jié)點(diǎn)被傳感器節(jié)點(diǎn)覆蓋的概率。假設(shè)目標(biāo)節(jié)點(diǎn)tj和傳感器節(jié)點(diǎn)si之間的距離為

(1)

傳感器節(jié)點(diǎn)能夠覆蓋到目標(biāo)節(jié)點(diǎn)的概率如下：

若d(si,tj)≤Rs，則目標(biāo)節(jié)點(diǎn)被該區(qū)域傳感器節(jié)點(diǎn)覆蓋，傳感器節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)的感知概率記為1；否則,目標(biāo)節(jié)點(diǎn)未被覆蓋，傳感器節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)的感知概率記為0。

定義2分布均勻性U,指?jìng)鞲衅鞴?jié)點(diǎn)覆蓋是否均勻，是某節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的距離標(biāo)準(zhǔn)差,值越小代表傳感器節(jié)點(diǎn)分布的覆蓋均勻性越好。

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

(2)

CE越大，傳感器節(jié)點(diǎn)覆蓋效率越高。

1.2 問題描述

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

受Voronoi圖啟發(fā)來解決傳感器節(jié)點(diǎn)覆蓋區(qū)域存在覆蓋空洞和重疊覆蓋等問題:1)將傳感器節(jié)點(diǎn)簡(jiǎn)化為圓心，其覆蓋范圍假設(shè)為一個(gè)圓;2)依據(jù)Voronoi圖劃分準(zhǔn)覆蓋區(qū)域，可以得到傳感器節(jié)點(diǎn)所處位置對(duì)應(yīng)的多個(gè)Voronoi多邊形;3)通過一定規(guī)則移動(dòng)傳感器節(jié)點(diǎn)，其對(duì)應(yīng)的圓隨即變化位置和大小，直至覆蓋圓完全覆蓋準(zhǔn)覆蓋區(qū)域,停止移動(dòng)傳感器節(jié)點(diǎn)。

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

(3)

如圖1所示，采用Voronoi圖和圓覆蓋結(jié)合的方式構(gòu)建了20個(gè)移動(dòng)傳感器節(jié)點(diǎn)模型示例。其中，矩形區(qū)域?yàn)閃SNs準(zhǔn)覆蓋區(qū)域，實(shí)心點(diǎn)為移動(dòng)傳感器節(jié)點(diǎn)，實(shí)線覆蓋圓為每個(gè)傳感器節(jié)點(diǎn)的感知圓盤，多邊形區(qū)域?yàn)槊總€(gè)實(shí)心點(diǎn)構(gòu)建的Voronoi區(qū)域。將無線傳感網(wǎng)絡(luò)準(zhǔn)覆蓋區(qū)域劃分成若干個(gè)Voronoi區(qū)域，可以較好地呈現(xiàn)覆蓋情況。

圖1 移動(dòng)傳感器節(jié)點(diǎn)覆蓋模型示意圖

1.3 基于CVT模型的WSNs覆蓋優(yōu)化算法

普通的Voronoi圖只能研究固定的靜態(tài)傳感器節(jié)點(diǎn)網(wǎng)絡(luò)覆蓋情況，針對(duì)移動(dòng)傳感網(wǎng)絡(luò)引進(jìn)CVT，定義為每個(gè)Voronoi區(qū)域的生成點(diǎn)是在該Voronoi區(qū)域上的質(zhì)心，即

(4)

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

針對(duì)網(wǎng)絡(luò)覆蓋問題的優(yōu)化方法是迭代更新上一次的候選傳感器節(jié)點(diǎn)對(duì)應(yīng)的Voronoi區(qū)域的外接圓的圓心。問題求解的目標(biāo)是優(yōu)化傳感器節(jié)點(diǎn){ci}的位置，使覆蓋圓盤的半徑達(dá)到極限。更確切的表述如下問題：給定一個(gè)二維區(qū)域的最優(yōu)覆蓋，求解已知數(shù)目的覆蓋圓盤的最小半徑，根據(jù)數(shù)學(xué)理論推導(dǎo)，定義覆蓋圓盤的半徑R如下

(5)

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

1.4 算法描述

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

2)對(duì)準(zhǔn)覆蓋區(qū)域通過離散采樣技術(shù)得到采樣點(diǎn)集合{sj}，以此實(shí)現(xiàn)近似Voronoi區(qū)域的表達(dá)。在生成采樣點(diǎn)集{sj}中，設(shè)定公差ε控制采樣點(diǎn)集的密度。

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

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

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境配置

根據(jù)準(zhǔn)覆蓋區(qū)域進(jìn)行離散采樣初始化數(shù)據(jù)，同時(shí)初始化覆蓋圓盤的數(shù)目和初始圓心，以及設(shè)定程序終止條件；對(duì)準(zhǔn)覆蓋區(qū)域進(jìn)行Delaunay三角化；進(jìn)行迭代求解。搭建的實(shí)驗(yàn)環(huán)境平臺(tái)是Windows 7系統(tǒng)，英特爾雙核處理器、2.4 GHz主頻、6 GB內(nèi)存的計(jì)算機(jī)，以C++編程實(shí)現(xiàn)。

2.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果中，以9個(gè)節(jié)點(diǎn)覆蓋方形區(qū)域和8個(gè)節(jié)點(diǎn)覆蓋圓形區(qū)域?yàn)槔?，?zhǔn)覆蓋區(qū)域的離散表示、迭代過程和求解結(jié)果如圖2和圖3所示。

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

圖2 方形區(qū)域的覆蓋過程

圖3給出了8個(gè)節(jié)點(diǎn)對(duì)圓形區(qū)域的覆蓋過程，證明區(qū)域形狀的多樣性未對(duì)本算法產(chǎn)生影響。

圖3 圓形區(qū)域的覆蓋過程

根據(jù)實(shí)驗(yàn)結(jié)果，不同數(shù)目的圓盤個(gè)數(shù)實(shí)現(xiàn)準(zhǔn)覆蓋區(qū)域的覆蓋情況如表1所示，N為圓盤的個(gè)數(shù)，R為圓盤的半徑，D為對(duì)準(zhǔn)覆蓋區(qū)域的覆蓋率?？梢钥闯觯涸谕瑯拥臏?zhǔn)覆蓋區(qū)域，隨著節(jié)點(diǎn)數(shù)目增加，圓盤平均半徑不斷減小，對(duì)準(zhǔn)覆蓋區(qū)域的最終覆蓋率均能達(dá)到100 %。與文獻(xiàn)[7，11]對(duì)比，本算法覆蓋率優(yōu)于基于連通性BCBS(connectivity considered BCBS，CC-BCBS)算法和BCBS算法。

表1 不同數(shù)目節(jié)點(diǎn)的覆蓋效率表

3 結(jié)束語

通過實(shí)驗(yàn)表明:該模型能夠調(diào)整移動(dòng)傳感器節(jié)點(diǎn)至最佳位置，合理劃分準(zhǔn)覆蓋區(qū)域，有效提高準(zhǔn)覆蓋區(qū)域網(wǎng)絡(luò)覆蓋率至100 %，減少網(wǎng)絡(luò)擁塞和覆蓋盲區(qū)，提供了更高的網(wǎng)絡(luò)通信服務(wù)。本文忽略了外部復(fù)雜環(huán)境因素對(duì)傳感器節(jié)點(diǎn)規(guī)劃的影響，下一步要做的工作是將算法進(jìn)行改進(jìn)，使其適合更復(fù)雜環(huán)境下的移動(dòng)傳感網(wǎng)絡(luò)的覆蓋優(yōu)化。

參考文獻(xiàn):

[1] 仲元昌,陳 鋒,李發(fā)傳,等.大規(guī)模無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].傳感器與微系統(tǒng),2014,33(11):117-120.

[2] 凡高娟,郭拯危.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署研究進(jìn)展[J].傳感器與微系統(tǒng),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] 祁育仙,李國(guó)勇.混合WSNs中基于多目標(biāo)優(yōu)化的覆蓋控制算法[J].傳感器與微系統(tǒng),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] 梅希薇,宋鑫宏,方 偉.基于連通性的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].傳感器與微系統(tǒng),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圖盲區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制部署策略[J].物理學(xué)報(bào),2014,63(22):128-137.

[12] 劉志強(qiáng),沈廼桐,毛 強(qiáng),等.無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋的CVT算法[J].傳感器與微系統(tǒng),2015,34(6):115-118.