梅希薇， 宋鑫宏， 方 偉

(江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122)

基于連通性的無線傳感器網(wǎng)絡覆蓋優(yōu)化算法*

梅希薇， 宋鑫宏， 方 偉

(江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122)

針對無線傳感器網(wǎng)絡(WSNs)的覆蓋優(yōu)化和連通性問題，提出了一種基于連通性的WSNs覆蓋優(yōu)化算法(CC—BCBS)。在二維監(jiān)測區(qū)域內(nèi)，CC—BCBS以傳感器節(jié)點間的通信半徑作為限制條件，只對連通的傳感器節(jié)點進行Voronoi圖劃分，根據(jù)節(jié)點對應泰森多邊形的覆蓋情況構造盲區(qū)圖，將盲區(qū)重心作為候選優(yōu)化位置，使節(jié)點盡可能最大化覆蓋監(jiān)測區(qū)域。節(jié)點通信半徑影響著區(qū)域覆蓋的冗余度，故針對劃分時可能出現(xiàn)的3種不同連通情況，給出了相應措施。仿真結果表明:CC—BCBS在覆蓋率，分布均勻性，平均連通個數(shù)與連通率方面相比BCBS等算法有明顯優(yōu)勢。

無線傳感器網(wǎng)絡； Voronoi圖； 連通性； 覆蓋優(yōu)化

0 引 言

在無線傳感器網(wǎng)絡(WSNs)[1]的覆蓋優(yōu)化問題中，網(wǎng)絡覆蓋率和連通性是重要的性能指標，網(wǎng)絡的覆蓋率代表了傳感器對目標區(qū)域的有效覆蓋范圍，連通性是網(wǎng)絡進行可靠數(shù)據(jù)傳輸?shù)幕A。如何在達到網(wǎng)絡覆蓋最優(yōu)化的過程中考慮連通性[2]等相關屬性，成為目前研究覆蓋控制方面的主要課題[3]。

很多專家學者從覆蓋優(yōu)化、連通，或兩者綜合的角度對WSNs進行了研究。文獻[4]將NSGA-II進行改進用于混合WSNs覆蓋優(yōu)化算法。文獻[5]提出的miniMax算法將泰森多邊形最小外接圓圓心作為目標點，VOR算法中傳感器節(jié)點向離其最遠泰森多邊形頂點移動。文獻[6]提出的混合部署 (VEDGE) 策略，將泰森多邊形最大內(nèi)切圓圓心和最小外接圓圓心中覆蓋率最高的位置，作為節(jié)點移動的目標位置。文獻[7]采用ASFA算法增強大規(guī)模WSNs覆蓋效果并延長其生存時間。文獻[8]提出的二進制沖撞比特搜索(binary collision-bit search,BCBS)算法采用優(yōu)化偽形心方式提升覆蓋率，但未考慮傳感器節(jié)點實際通信能力。文獻[9]提出的基于連通度獲得相對距離的非測距定位算法，大大提高了定位精度。文獻[10]提出當節(jié)點的通信半徑是其感知半徑的2倍或以上時，對目標區(qū)域保持全覆蓋的活躍節(jié)點集是全連通的。

針對WSNs的連通和覆蓋優(yōu)化問題，在前期研究的BCBS的基礎上，提出了一種基于連通性的WSNs覆蓋優(yōu)化算法研究(connectivity-considered BCBS，CC-BCBS)。與BCBS，CBS[11]，VEDGE[5]等算法進行對比實驗，結果表明：CC-BCBS算法在覆蓋率、分布均勻性、連通個數(shù)、連通率的性能中優(yōu)勢明顯。

1 無線傳感器覆蓋優(yōu)化模型

在大小為L×W的二維平面監(jiān)測區(qū)域T內(nèi)(L和W分別監(jiān)測區(qū)域的長和寬)，通過隨機部署的方式在T內(nèi)放置N個傳感器節(jié)點，得到傳感器節(jié)點集合為D={d1,d2,…,dN}。Di(i∈N)的感知范圍是以該節(jié)點為圓心，半徑等于感知半徑Rs的一個圓形區(qū)域，用位置坐標為di(xi,yi)，di={p∈L×W|ds(p,Si)≤Rs}表示，其中ds(p,Si)為點p與點Si的歐氏距離，傳感器網(wǎng)絡的覆蓋范圍C是網(wǎng)絡中所有活動節(jié)點的覆蓋范圍的并集。Rc表示通信半徑，文獻[12,13]證明，當Rc≥2Rs時，兩個傳感器節(jié)點是可以通信的。二維平面監(jiān)測區(qū)域分成a×b個網(wǎng)格，每個網(wǎng)格的交點位置為目標點位置。將傳感器節(jié)點通過一定的方式在監(jiān)測區(qū)域內(nèi)移動，在減小重疊區(qū)域、縮小盲區(qū)范圍的同時，提高傳感器節(jié)點在監(jiān)測區(qū)域內(nèi)的覆蓋率。

WSNs覆蓋性能指標一般包括覆蓋率、覆蓋效率、分布均勻性、連通率。

覆蓋率CR定義為所有傳感器節(jié)點的覆蓋面積之和與目標區(qū)域面積的比值，覆蓋率總是小于或等于1[14]。

(1)

式中 CR為覆蓋率;Ci為第i個節(jié)點的覆蓋面積;N為節(jié)點的個數(shù);A為整個目標區(qū)域的面積。

平均連通個數(shù)AN在本文中定義為迭代后全連通個數(shù)與總迭代次數(shù)的比值，即

(2)

式中 AN為平均連通個數(shù);M為迭代次數(shù);Am為每次迭代達到全連通的傳感器個數(shù)。

連通率CN即傳感器節(jié)點達到全連通的平均迭代次數(shù)與總迭代次數(shù)的比值，反映了傳感器節(jié)點連通性能的好壞，即

(3)

式中 CN為連通率;N為運行次數(shù);M為迭代次數(shù);Cm為第m次迭代時傳感器節(jié)點是否全連通。Cm為個布爾型變量，若連通則Cm=1；否則，Cm=0。

分布均勻性U反映了節(jié)點在監(jiān)測區(qū)域的分布情況，U越小節(jié)點分布越均勻,定義為傳感器節(jié)點與其鄰居節(jié)點之間距離的標準差的均值[15]。

(4)

(5)

(6)

Di,j=d(si,zj)

(7)

式中 ki為第i個節(jié)點的鄰居節(jié)點個數(shù)；Mi為第i個節(jié)點與鄰居節(jié)點的平均距離；Di,j為第i個節(jié)點與第j個鄰居節(jié)點之間的距離；Ui為傳感器節(jié)點di與其鄰居節(jié)點Z之間距離的標準差。

2 CC-BCBS算法

2.1BCBS算法

Voronoi圖是劃分傳感器節(jié)點的有效方式，傳感器節(jié)點數(shù)量與感知范圍的大小影響其在監(jiān)測區(qū)域內(nèi)的覆蓋部署效果，如果覆蓋率未達到100 %，則必然存在未覆蓋區(qū)域，稱之為感知盲區(qū)[16]。BCBS算法對感知盲區(qū)的處理方法是構造與泰森盲區(qū)多邊形[8]。用傳統(tǒng)泰森多邊形法時，如果在部署過程中未考慮鄰居節(jié)點對當前傳感器節(jié)點的影響，則會產(chǎn)生偽形心[7]。BCBS算法對此進行改進，并依據(jù)泰森多邊形頂點覆蓋情況討論盲區(qū)的形狀：泰森多邊形頂點全覆蓋時，盲區(qū)頂點為鄰居節(jié)點與當前感知圓盤[17]交點，如圖1(a)中虛線表示新的傳感器與周圍鄰居節(jié)點感知圓盤的交點(1,2,3,4)圍成的多邊形，實心三角形為多邊形形心位置，原泰森多邊形形心位置用叉表示，通過比較在不同形心位置的覆蓋率來選擇最佳部署節(jié)點位置；泰森多邊形頂點部分覆蓋時，如圖1(b)所示，盲區(qū)頂點由兩部分組成，一部分為已覆蓋頂點的鄰居節(jié)點與當前感知圓盤交點(3,4,5)，另一部分為未覆蓋的頂點(1,2)所圍成的多邊形；泰森多邊形頂點都沒被覆蓋時，盲區(qū)為當前傳感器所在泰森多邊形的頂點。繼而通過對盲區(qū)形心和偽形心位置的選取，來提高監(jiān)測區(qū)域的覆蓋率。該算法雖然提高了傳感器節(jié)點的覆蓋率，但是未考慮是否在全連通的情況下進行有效信息傳輸。

圖1 泰森多邊形頂點全部覆蓋和部分覆蓋

2.2 連通性與Voronoi圖劃分的關系

在給定的監(jiān)測區(qū)域范圍內(nèi)，傳感器的通信半徑以及個數(shù)等參數(shù)設置對網(wǎng)絡中節(jié)點的部署效果起到了一定的影響：如圖2(a)所示，傳感器個數(shù)不變的情況下，傳感器的通信半徑過小難使網(wǎng)絡快速連通。而圖2(b)中通信半徑設置過大，則網(wǎng)絡很容易達到飽和，不同節(jié)點直接相互干擾性強，不利于節(jié)點向正確方向的移動。

本文中利用三角剖分生成Voronoi圖[18]，孤立節(jié)點表示與所有鄰居節(jié)點的通信半徑均小于2倍感知半徑的點。當有一個孤立節(jié)點時，則在劃分Voronoi圖時去掉該點及其鄰居節(jié)點的關聯(lián)信息。由于2個節(jié)點無法構成三角網(wǎng)，故本文規(guī)定當只有2個節(jié)點可相互通信時等待被傳喚，暫不進行劃分。當有大于2個可通信節(jié)點時，進行Voronoi圖劃分。如圖3所示，節(jié)點13，16，19，27為孤立節(jié)點，無法與其他節(jié)點通信，故在劃分Voronoi圖時去這些點。如節(jié)點4，7只能互相通信，故不進行Voronoi圖劃分；節(jié)點2，15，26，29，30中可通信節(jié)點的數(shù)量大于2，故將參與Voronoi圖劃分。

圖2 傳感器部署效果

2.3 CC-BCBS算法描述

傳感器感知半徑同構且感知范圍有限的情況下，用合適的的節(jié)點數(shù)盡可能最大化覆蓋監(jiān)測區(qū)域，即監(jiān)測區(qū)域中每個傳感器節(jié)點有效覆蓋區(qū)域面積最大，減少感知圓盤之間的重復部分，從而充分利用每一個感知圓盤。由文獻[10]可知，3個半徑相同的圓相交于一點，當圓心構成的三角形是等邊三角形時，這些圓構成的總圓域對監(jiān)測區(qū)域的覆蓋范圍最大。

本節(jié)提出的基于連通性的WSNs覆蓋優(yōu)化(CC-BCBS)算法，是在之前提出的BCBS算法優(yōu)化網(wǎng)絡覆蓋率的基礎上，為了提高傳感器節(jié)點的連通率和分布均勻性，考慮了傳感器感知半徑的大小對其在監(jiān)測區(qū)域內(nèi)數(shù)量分布的影響，且以通信半徑為前提，針對部署過程中可能產(chǎn)生的3種不同的連通情況從而進行Voronoi圖劃分。該算法不僅兼顧了連通性、分布均勻性，還使覆蓋率得到了提高，具體描述如下：

1)隨機部署傳感器節(jié)點的初始位置，得到傳感器節(jié)點集D={dc1,dc2,…,dcn,dpq,…,dpn}，dci為可通信節(jié)點，dpi為不可通信節(jié)點。節(jié)點間距離矩陣Dmk={d11,d12,…d1k;…;dm1,dm2,…,dmk}，dmk表示第m和第k個節(jié)點的距離。

2)用2.2節(jié)闡述的劃分方式在保證dmk≥2Rs前提下構造初始Voronoi圖(Rs為感知半徑)。

3)當前節(jié)點di與鄰居節(jié)點組成節(jié)點集Di=D_i{di,z1,z2,…,ze}，Di對應的泰森多邊形集合為Vk={vi,vz1,vz2,…,vze}，其中e是鄰居節(jié)點個數(shù)。依據(jù)泰森多邊形頂點覆蓋情況判斷是否存在盲區(qū)：若當前節(jié)點di全被覆蓋，說明不存在泰森盲區(qū)，轉步驟(8)；否則，存在泰森盲區(qū)(盲區(qū)為2.1節(jié)闡述的泰森多邊形頂點部分被覆蓋和全都未被覆蓋時所對應的形狀)，繼續(xù)進行下一步驟。

4)得到當前節(jié)點di在當前位置(dx,dy)對應的初始局部覆蓋率qi。

5)得到當前節(jié)點di在盲區(qū)重心wi處對應覆蓋率ti，并將wi作為最優(yōu)候選位置。

6)限制最大移動步長：若wi與di距離dwi_di大于最大步長，則將兩點所連線段上與wi距離為Maxstep的點賦值給wi，wi=(wx,wy)。求其新的局部覆蓋率ti。

7)比較覆蓋率ti和qi：如果qi≤ti，則用盲區(qū)重心位置(wx,wy)替換掉原來的節(jié)點位置作為當前節(jié)點位置，即di=(wx,wy)；否則節(jié)點位置不變，即di=(dx,dy)，轉步驟(10)。

8)在Di內(nèi)刪去節(jié)點di，得到鄰居節(jié)點集Ze={z1,z2,…,ze}，在保證Di內(nèi)兩個傳感器節(jié)點間的距離大于或等于2倍感知半徑的前提下重構Voronoi圖，由鄰居節(jié)點集Ze形成新的泰森多邊形V＇e={v＇z1,v＇z2,…,v＇ze}。

9)計算V＇e內(nèi)新產(chǎn)生泰森多邊形頂點覆蓋情況，若新頂點全被覆蓋，說明不存在泰森盲區(qū)，計算V＇e的重心wi=(wx,wy)，則用新找到的重心位置(wx,wy)更新原來的節(jié)點位置，即di=(wx,wy)，進入下一步驟。否則，存在泰森盲區(qū)(盲區(qū)為上節(jié)討論的泰森多邊形頂點部分被覆蓋和全都未被覆蓋時所對應的形狀)，轉步驟(4)。

10)重復步驟(3)～(9)，直到所有節(jié)點都執(zhí)行完為止。

11)重復步驟(2)～(10)，直到滿足停止條件。

以下顯示了在二維矩形平面內(nèi)CC-BCBS的某一次部署全過程。

表1 仿真環(huán)境參數(shù)

圖3(a)～ (c)展示了CC-BCBS算法在迭代過程中傳感器節(jié)點的分布圖，點代表傳感器節(jié)點，圓圈代表每個傳感器節(jié)點的感知范圍，線表示對區(qū)域進行Voronoi圖劃分。30個節(jié)點的初始覆蓋率為74.12 %(圖3(a)),此時節(jié)點19無法通信，則在劃分Voronoi圖時去掉該點以及其鄰居節(jié)點25,27,16,14,3,12的關聯(lián)信息。18次迭代后為97.93 %(圖3 (b))，最終覆蓋率為98.61 %(圖3(c))?？梢钥闯鲇勺畛醯纳y分布到最終均勻分布，且在迭代早期傳感器分布情況較優(yōu)。

圖3 一次迭代部署過程

3 實 驗

本次實驗從覆蓋率、分布均勻性、平均連通個數(shù)、連通率來對CC-BCBS等6種算法實驗結果比較如圖4。共進行30次隨機部署實驗，每次迭代30次，實驗參數(shù)與表1相同。

圖4為傳感器節(jié)點覆蓋率變化曲線，該曲線圖表明了在算法運行初期，CC-BCBS的覆蓋率效果提升快，且在第3次運行時其覆蓋率就已經(jīng)超過其他5種算法，算法最終覆蓋率達到98.14 %并趨于穩(wěn)定，故CC-BCBS算法在該性能中占優(yōu)。由于分布均勻性數(shù)值越低越好，由圖4(b)知，CC-BCBS平均分布均勻性為1.277 2，故在該性能中占優(yōu)。

圖4(a)表明CC-BCBS和VOR 2種算法在迭代完成后連通個數(shù)最多(平均連通個數(shù)為30)且處于全連通狀態(tài)，BCBS算法平均連通個數(shù)是29.35，CC-BCBS和VOR算法在該性能中占優(yōu)。圖4(d)表明CC-BCBS和VOR算法連通率達100 %，BCBS在每次運行中連通率都有所變化但變化不大，CBS，VEDGE和miniMax次之。

圖4 6種算法實驗結果比較

4 結束語

本文提出的基于連通性的WSNs覆蓋優(yōu)化算法，具有連通性強、覆蓋率高、節(jié)點分布均勻性好的優(yōu)點。在相同的環(huán)境參數(shù)下，由于傳感器節(jié)點隨機部署位置的不同，算法結果也對應有所變化，雖然達到了全連通，但在初次達到全連通的代數(shù)上還是有改進的空間，而且覆蓋率還有提升空間。將本文提出的算法用于不規(guī)則監(jiān)測區(qū)域以及三維空間也是下一步的研究方向。

[1] 霍慧慧,李國勇.改進的離散果蠅優(yōu)化算法在WSNs覆蓋中的應用[J].傳感器與微系統(tǒng),2016,35(2):157-160.

[2] 翟正怡.無線傳感器網(wǎng)絡中的覆蓋優(yōu)化算法與連通問題研究[D].上海：同濟大學,2008.

[3] 趙 旭,雷 霖,代傳龍.無線傳感器網(wǎng)絡的覆蓋控制[J].傳感器與微系統(tǒng),2007,26(8):62-66.

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

[5] Wang G,Cao G,Porta T F L.Movement-assisted sensor deployment[J].IEEE Transactions on Mobile Computing,2006,5(6):640-652.

[6] Mahboubi H,Moezzi K,Aghdam A G,et al.Distributed deployment algorithms for efficient coverage in a network of mobile sensors with nonidentical sensing capabilities[J].IEEE Transactions on Vehicular Technology,2014,63(8):3998-4016.

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

[8] 方 偉,宋鑫宏.基于Voronoi圖盲區(qū)的無線傳感器網(wǎng)絡覆蓋控制部署策略[J].物理學報,2014(22):132-141.

[9] 徐磊磊,徐保國.無線傳感器網(wǎng)絡中一種基于連通性的非測距定位算法[J].傳感器與微系統(tǒng),2016,35(1):127-130.

[10] Xing Guoliang,Wang Xiaorui.Integrated coverage and connectivity configuration for energy conservation in sensor networks[J].ACM Transactionson Sensor Networks，2005,1(1):36-72.

[11] Lee H J,Kim Y H,Han Y H,et al.Centroid-based movement assisted sensor deployment schemes in wireless sensor network-s[C]∥Proceedings of the 2009 IEEE 70th Vehicular Technology Conference Fall(VTC 2009-Fall),IEEE:Piscataway,NJ,2009：89-91.

[12] Zhang H H,Hou J C.Maintaining sensing coverage and connecti-vity in large sensor networks[J].Ad Hoc & Sensor Wireless Networks,2004,1(2)：1097-1100.

[13] Tian D,Georganas N D.Connectivity maintenance and coverage preservation in wireless sensor networks[C]∥Canadian Confe-rence on Electrical and Computer Engineering,2004:1097-1100.

[14] 曾映蘭,陳 靜,鄭金華.基于遺傳算法的WSNs覆蓋優(yōu)化方法[J].計算機工程與應用,2009,45(11):89-91.

[15] 劉麗萍.無線傳感器網(wǎng)絡節(jié)能覆蓋[D].杭州：浙江大學,2006.

[16] Yue X,Yu J,Zhao M.PBADaPCo:An efficient algorithm based on improved edge weighted voronoi diagram to detect and make-up potential blind areas in wireless sensor networks[C]∥Proceedings of 2008 the 3rd International Conference on Innovative Computing Information and Control,IEEE Computer Society,2008:589.

[17] 任永功,廖士中.利用類Delaunay三角剖分實現(xiàn)Voronoi圖[J].計算機科學,2002,29(9):78-79.

Connectivity-based coverage optimization algorithm for WSNs*

MEI Xi-wei, SONG Xin-hong, FANG Wei

(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

Aiming at problem of coverage optimization and connectivity in wireless sensor networks(WSNs),a connectivity considered-BCBS(CC-BCBS)is proposed.In two-dimensional monitoring region,CC-BCBS uses communication radius as restriction condition, and just partitions connected sensor nodes by Voronoi diagram.CC-BCBS constructs the blind-zone area according to different coverage means of Voronoi polygon,and sets the centroid of the blind-zone as the optimal candidate position so as to improve the coverage rate.The influence that communication radius has on coverage redundancy is considered.Reasonable measures areshowed in case of three kinds of connectivity cases that might occur when doing partitions.Simulation results show that the algorithm has obvious advantages in coverage rate,distribution uniformity,average connect number and connectivity rate compared with algorithm like BCBS and so on.

wireless sensor networks(WSNs); Voronoi diagram; connectivity; coverage optimization

10.13873/J.1000—9787(2017)05—0145—04

2016—05—29

國家自然科學基金資助項目(61105128,61170119,61373055)；江蘇省自然科學基金資助項目(BK20131106，BK20130161)；江南大學自主科研計劃重點項目(JUSRP51410B)；中國博士后基金資助項目(2014M560390)

TP 393

A

1000—9787(2017)05—0145—04

梅希薇(1992-)，女，碩士，研究方向為無線傳感器網(wǎng)絡覆蓋控制優(yōu)化算法。

方 偉(1980-)，男，通訊作者，博士，主要從事計算智能、無線傳感器覆蓋優(yōu)化的研究，E—mail：fangwei@jiangnan.edu.cn。