面向區(qū)域覆蓋的異構(gòu)傳感器節(jié)點(diǎn)部署*

宋志強(qiáng), 周獻(xiàn)中, 陳春林

(1.南京大學(xué) 工程管理學(xué)院，江蘇 南京 210008；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 機(jī)電與信息技術(shù)學(xué)院，江蘇 蘇州 215009)

面向區(qū)域覆蓋的異構(gòu)傳感器節(jié)點(diǎn)部署*

宋志強(qiáng)1,2, 周獻(xiàn)中1, 陳春林1

(1.南京大學(xué) 工程管理學(xué)院，江蘇 南京 210008；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院 機(jī)電與信息技術(shù)學(xué)院，江蘇 蘇州 215009)

摘要:針對(duì)異構(gòu)傳感器節(jié)點(diǎn)隨機(jī)部署于被監(jiān)測(cè)區(qū)域時(shí)容易產(chǎn)生覆蓋漏洞的問(wèn)題，提出一種基于取樣直線(xiàn)掃描的覆蓋漏洞修復(fù)算法，基于取樣直線(xiàn)掃描，找到覆蓋漏洞；通過(guò)移動(dòng)傳感器節(jié)點(diǎn)修復(fù)覆蓋漏洞。該算法以完全覆蓋被監(jiān)測(cè)區(qū)域?yàn)閮?yōu)化目標(biāo)，對(duì)于具有相同感知半徑的同構(gòu)傳感器節(jié)點(diǎn)和具有不同感知半徑的異構(gòu)傳感器節(jié)點(diǎn)同樣適用。仿真實(shí)驗(yàn)表明：該算法能有效修復(fù)覆蓋漏洞。

關(guān)鍵詞:無(wú)線(xiàn)傳感器網(wǎng)絡(luò)； 異構(gòu)傳感器節(jié)點(diǎn)； 區(qū)域覆蓋； 覆蓋漏洞修復(fù)算法

0引言

傳感器節(jié)點(diǎn)的部署問(wèn)題是各類(lèi)系統(tǒng)應(yīng)用的關(guān)鍵問(wèn)題之一，有的應(yīng)用場(chǎng)合要求傳感器節(jié)點(diǎn)完全覆蓋被監(jiān)測(cè)區(qū)域，以確保被監(jiān)測(cè)區(qū)域內(nèi)發(fā)生的事件可以被傳感器及時(shí)感知。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的區(qū)域覆蓋問(wèn)題，主要研究工作集中于同構(gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋問(wèn)題，即假設(shè)感器節(jié)點(diǎn)的感知半徑是相同的[1～9]。針對(duì)環(huán)境安全且規(guī)模較小的場(chǎng)合，文獻(xiàn)[1]利用靜止傳感器節(jié)點(diǎn)，研究確定性部署。文獻(xiàn)[2]首先在區(qū)域內(nèi)密集部署靜態(tài)傳感器節(jié)點(diǎn)，然后通過(guò)多目標(biāo)經(jīng)驗(yàn)競(jìng)爭(zhēng)算法激活最少的傳感器節(jié)點(diǎn)工作，而其它傳感器節(jié)點(diǎn)則處于休眠模式。文獻(xiàn)[3]的研究均基于Voronoi圖，利用Voronoi圖找出覆蓋空洞，采用相應(yīng)的算法修復(fù)空洞。文獻(xiàn)[4～7]利用虛擬力方法來(lái)研究移動(dòng)傳感器節(jié)點(diǎn)的部署問(wèn)題，其核心思想是通過(guò)節(jié)點(diǎn)之間的引力和斥力，引導(dǎo)節(jié)點(diǎn)移動(dòng)。文獻(xiàn)[8]專(zhuān)門(mén)研究了采用虛擬力方法部署移動(dòng)傳感器節(jié)點(diǎn)的缺陷，并對(duì)虛擬力方法作相應(yīng)改進(jìn)?；诋悩?gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋，相關(guān)研究較少，文獻(xiàn)[9]研究了異構(gòu)傳感器節(jié)點(diǎn)的覆蓋問(wèn)題，但該方法不能保證對(duì)區(qū)域的完全覆蓋。在實(shí)際的應(yīng)用中，各傳感器節(jié)點(diǎn)通常是異構(gòu)的，研究異構(gòu)傳感器節(jié)點(diǎn)的區(qū)域覆蓋更具現(xiàn)實(shí)意義。

移動(dòng)傳感器節(jié)點(diǎn)由于具備移動(dòng)特性，比傳統(tǒng)的靜態(tài)傳感器節(jié)點(diǎn)更具應(yīng)用價(jià)值。本文首先隨機(jī)部署感知半徑不同的靜態(tài)傳感器節(jié)點(diǎn)，然后利用覆蓋漏洞修復(fù)算法找出覆蓋漏洞，最后通過(guò)移動(dòng)傳感器節(jié)點(diǎn)修復(fù)覆蓋漏洞，使被監(jiān)測(cè)區(qū)域達(dá)到完全覆蓋。

1問(wèn)題描述

考慮N個(gè)靜態(tài)傳感器節(jié)點(diǎn)隨機(jī)部署于二維被監(jiān)測(cè)區(qū)域A中，N個(gè)靜態(tài)傳感器組成的集合可由式(1)表示

S={s1,s2,…,sN}

(1)

被監(jiān)測(cè)區(qū)域A長(zhǎng)L，寬W。各傳感器節(jié)點(diǎn)si可表述為

si={xi,yi,ri},i=1,2,…,N

(2)

式中(xi,yi)為節(jié)點(diǎn)坐標(biāo)，ri為感知半徑。對(duì)于位于區(qū)域A內(nèi)的任意點(diǎn)p(x,y)，將節(jié)點(diǎn)si和點(diǎn)p之間的歐氏距離記為d(p,si)

(3)

各傳感器節(jié)點(diǎn)采用0/1感知模型，即傳感器節(jié)點(diǎn)的感知范圍是以節(jié)點(diǎn)為圓心的圓，如果事件發(fā)生在節(jié)點(diǎn)的感知圓內(nèi)，則感知概率為1，若事件發(fā)生在感知圓外，則感知概率為0,則節(jié)點(diǎn)si對(duì)點(diǎn)p的感知概率可表示為

(4)

記節(jié)點(diǎn)si的覆蓋范圍為Si，Si的面積可表示為

(5)

則區(qū)域A中N個(gè)靜態(tài)傳感器節(jié)點(diǎn)的覆蓋面積STotal為N個(gè)靜態(tài)傳感器節(jié)點(diǎn)覆蓋面積的并集，即

(6)

記被監(jiān)測(cè)區(qū)域A的面積為SA，則被監(jiān)測(cè)區(qū)域A的初始覆蓋率為

(7)

部署移動(dòng)傳感器節(jié)點(diǎn)的目的為最大化被監(jiān)測(cè)區(qū)域A的覆蓋率，即使得STotal=SA，即完全覆蓋被監(jiān)測(cè)區(qū)域，覆蓋率為100 %。

假設(shè)由靜態(tài)傳感器節(jié)點(diǎn)和移動(dòng)傳感器節(jié)點(diǎn)組成的傳感網(wǎng)具有如下性質(zhì)：1)傳感器節(jié)點(diǎn)可通過(guò)GPS或其他方式獲知自身位置，并通過(guò)網(wǎng)絡(luò)發(fā)送至監(jiān)測(cè)中心，即監(jiān)測(cè)中心可知傳感器節(jié)點(diǎn)的位置信息；2)傳感器節(jié)點(diǎn)通信半徑至少是其感知半徑的2倍，即對(duì)于任意傳感器節(jié)點(diǎn)si，其通信半徑rci≥2ri；3)移動(dòng)傳感器節(jié)點(diǎn)能量充足，可移動(dòng)至指定位置；4)傳感器網(wǎng)絡(luò)保證節(jié)點(diǎn)在其通信半徑范圍內(nèi)的連通性。

2覆蓋漏洞修復(fù)算法

2.1覆蓋漏洞檢測(cè)

定義 取樣直線(xiàn)：在二維平面內(nèi)沿x軸方向或y軸方向與被監(jiān)測(cè)區(qū)域相交的任意直線(xiàn)。

如圖1所示，水平方向直線(xiàn)與被監(jiān)測(cè)區(qū)域交于A(yíng),B兩點(diǎn)，垂直方向直線(xiàn)與被監(jiān)測(cè)區(qū)域交于C,D兩點(diǎn)，直線(xiàn)AB和CD都是取樣直線(xiàn)。

圖1　取樣直線(xiàn)Fig 1　Sampling straight line

當(dāng)感知圓si的圓心到取樣直線(xiàn)的距離小于其感知半徑時(shí)，感知圓和該取樣直線(xiàn)相交，相交的直線(xiàn)段被該圓覆蓋；當(dāng)感知圓si的圓心到取樣直線(xiàn)的距離大于其感知半徑時(shí)，感知圓和該取樣直線(xiàn)不相交；當(dāng)感知圓si的圓心到取樣直線(xiàn)的距離等于其感知半徑時(shí)，感知圓和該取樣直線(xiàn)相切。

如圖2所示，AB為被監(jiān)測(cè)區(qū)域內(nèi)平行于x軸的一條取樣直線(xiàn)，其直線(xiàn)方程為y=y0。s1,s2,…,sn為n個(gè)與該直線(xiàn)相交的感知圓，其傳感器節(jié)點(diǎn)坐標(biāo)分別為(x1,y1)，(x2,y2),…,(xn,yn)。假設(shè)由節(jié)點(diǎn)si形成的感知圓和取樣直線(xiàn)AB的兩個(gè)交點(diǎn)坐標(biāo)分別為(xi_l,y0),(xi_r,y0)，交點(diǎn)橫坐標(biāo)滿(mǎn)足xi_l

圖2　感知圓與取樣直線(xiàn)相交示意圖Fig 2　Diagram of sensing circles and sampling straight lines intersect

基于上述分析，取樣直線(xiàn)被感知圓完全覆蓋的條件可歸納為

(8)

若不滿(mǎn)足式(8)的條件，則取樣直線(xiàn)未能被感知圓完全覆蓋，即感知圓和取樣直線(xiàn)之間存在覆蓋漏洞。如圖3所示，灰色區(qū)域Ⅰ,Ⅱ,Ⅲ均為覆蓋漏洞。2.2節(jié)設(shè)計(jì)覆蓋漏洞修復(fù)算法，使得傳感器節(jié)點(diǎn)能完全覆蓋被監(jiān)測(cè)區(qū)域。

圖3　覆蓋漏洞示意圖Fig 3　Diagram of coverage leak

2.2修補(bǔ)算法

被監(jiān)測(cè)區(qū)域A長(zhǎng)為L(zhǎng)，寬為W，N個(gè)靜止無(wú)線(xiàn)傳感器節(jié)點(diǎn)s1,s2,…,sn隨機(jī)分布于監(jiān)測(cè)區(qū)域A。傳感器節(jié)點(diǎn)si的感知半徑為ri(i=1,2,…,N)，Rmin≤ri≤Rmax，Rmin,Rmax分別為N個(gè)節(jié)點(diǎn)感知半徑的最小值和最大值，假設(shè)移動(dòng)傳感器節(jié)點(diǎn)的感知半徑也在Rmin與Rmax之間。單次覆蓋漏洞修補(bǔ)算法流程圖如圖4所示。

圖4　單次覆蓋漏洞修補(bǔ)算法流程圖Fig 4　Algorithm flow chart of single coverage leak repair algorithm

3仿真實(shí)驗(yàn)

為驗(yàn)證算法有效性，采用MatlabR2010b仿真，被監(jiān)測(cè)區(qū)域A=200m×200m=40 000m2，首先在被監(jiān)測(cè)區(qū)域隨機(jī)部署40個(gè)靜態(tài)傳感器節(jié)點(diǎn)。

靜態(tài)傳感器節(jié)點(diǎn)感知半徑為8～20m的隨機(jī)數(shù)，N=40時(shí)，共做100次實(shí)驗(yàn)。算法僅作水平取樣就能完成被監(jiān)測(cè)區(qū)域的完全覆蓋，因隨機(jī)部署靜態(tài)傳感器時(shí)的初始覆蓋率不同，故無(wú)人平臺(tái)數(shù)(即移動(dòng)傳感器節(jié)點(diǎn)數(shù))量在77～87之間變化。在僅改變靜態(tài)傳感器節(jié)點(diǎn)數(shù)量，其余參數(shù)不變的情況下，進(jìn)一步驗(yàn)證算法性能，當(dāng)N分別為60,80,100,120,140,160,180,200時(shí)，再分別做100次實(shí)驗(yàn)，仿真實(shí)驗(yàn)時(shí)算法僅作水平取樣時(shí)，就能完成被監(jiān)測(cè)區(qū)域的完成覆蓋，仿真實(shí)驗(yàn)表明算法的有效性，其中N=80時(shí)移動(dòng)傳感器節(jié)點(diǎn)部署前后對(duì)照?qǐng)D如圖5所示。

圖5　覆蓋漏洞修補(bǔ)算法運(yùn)行前后部署對(duì)照?qǐng)DFig 5　Deployment comparison chart before and after coverage leak repair algorithm running

N從40變化至200時(shí)，完成被監(jiān)測(cè)區(qū)域完全覆蓋所需的移動(dòng)傳感器節(jié)點(diǎn)數(shù)量變化情況如圖6所示。從圖6可看出，隨著靜態(tài)傳感器節(jié)點(diǎn)的增加，修補(bǔ)覆蓋漏洞所需的移動(dòng)傳感器節(jié)點(diǎn)數(shù)量逐漸減少，原因是靜態(tài)傳感器增加后，初始覆蓋率會(huì)相應(yīng)提高。具體選擇部署多少靜態(tài)傳感器節(jié)點(diǎn)及移動(dòng)傳感器節(jié)點(diǎn)，可根據(jù)其價(jià)格綜合衡量。

圖6　移動(dòng)傳感器節(jié)點(diǎn)隨靜態(tài)傳感器節(jié)點(diǎn)變化Fig 6　Mobile sensor nodes change with static sensor nodes

4結(jié)論

針對(duì)靜態(tài)傳感器節(jié)點(diǎn)隨機(jī)部署于被監(jiān)測(cè)區(qū)域時(shí)，容易存在覆蓋漏洞的問(wèn)題，本文提出一種基于取樣直線(xiàn)掃描的覆蓋漏洞修復(fù)算法。該算法對(duì)于同構(gòu)傳感器節(jié)點(diǎn)和具有不同感知半徑的異構(gòu)傳感器節(jié)點(diǎn)同樣適用。算法能夠修補(bǔ)靜態(tài)傳感器節(jié)點(diǎn)部署于被監(jiān)測(cè)區(qū)域形成的覆蓋漏洞，使被監(jiān)測(cè)區(qū)域達(dá)到完全覆蓋，以保證整個(gè)區(qū)域任何地點(diǎn)可能發(fā)生的異常情況均能被傳感器監(jiān)測(cè)到，實(shí)現(xiàn)無(wú)遺漏地監(jiān)測(cè)關(guān)鍵區(qū)域。

參考文獻(xiàn):

[1]KarK,BanerjeeS.Nodeplacementforconnectedcoveragein

sensornetworks[C]∥ModelingandOptimizationinMobile,AdHocandWirelessNetworks，WiOpt’03，2003 :1-2.

[2]EnayatifarR,YousefiM,AbdullahAH,etal.Anovelsensordeploymentapproachusingmulti-objectiveimperialistcompetitivealgorithminwirelesssensornetworks[J].ArabianJournalforScienceandEngineering,2014,39(6):4637-4650.

[3]趙春江,吳華瑞,劉強(qiáng),等.基于Voronoi的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋控制優(yōu)化策略[J].通信學(xué)報(bào),2013,34(9):115-122.

[4]HuangJ,SunL,WangR,etal.Improvedvirtualpotentialfieldalgorithmbasedonprobabilitymodelinthree-dimensionaldirectionalsensornetworks[J].InternationalJournalofDistributedSensorNetworks,2012,2012:1-9.

[5]SongZ,ZhouX,LiH.Virtualforce-aidedparticleswarmoptimizationfordeploymentofmobilenodesinwirelesssensornetwork-s[C]∥Proceedingsofthe2012InternationalConferenceonElectronics,CommunicationsandControl,IEEEComputerSociety,2012:81-84.

[6]HanYH,KimY,KimWT,etal.Anenergy-efficientself-deploymentwiththecentroid-directedvirtualforceinmobilesensornetworks[J].Simulation,2012,88(10):1152-1165.

[7]NanG,ChenZ,LiM,etal.Distributeddeploymentalgorithmbasedonboundaryexpansionandvirtualforceformobilesensornetworks[J].NeuralNetworkWorld,2014,24(3):309-332.

[8]BartoliniN,BongiovanniG,LaPortaT,etal.Onthevulnerabilitiesofthevirtualforceapproachtomobilesensordeployment[J].IEEETransactionsonMobileComputing,2014,13(11):2592-2605.

[9]杜曉玉,孫力娟,郭劍,等.異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報(bào),2014,36(3):696-702.

Deploymentofheterogeneoussensornodesforregionalcoverage*

SONGZhi-qiang1,2,ZHOUXian-zhong1,CHENChun-lin1

(1.SchoolofEngineeringManagement,NanjingUniversity,Nanjing210008,China;2.SchoolofElectromechanicalandInformationTechnology,SuzhouInstituteofTrade&Commerce,Suzhou215009,China)

Abstract:Aiming at problem that heterogeneous sensor nodes are randomly deployed in monitored area prone to genenate coverage leak,a coverage leak repair algorithm based on sampling straight line scan is proposed.Coverage leak are found based on sampling straight line scan;coverage leak are repaired by mobile sensor nodes.The algorithm treats the completely covered area by sensor nodes as the optimization goal and it is applicable for both homogeneous sensor nodes with the sensing radius of and the perception of the heterogeneous sensor nodes with different sensing radius.Simulation results show that the algorithm can effectively repair coverage leak.

Key words:wireless sensor networks(WSNs); heterogeneous sensor nodes;regional coverage; coverage leak repair algorithm

DOI:10.13873/J.1000—9787(2016)04—0119—04

收稿日期：2015—07—05

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61273327)

中圖分類(lèi)號(hào):TP 393

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1000—9787(2016)04—0119—04

作者簡(jiǎn)介:

宋志強(qiáng)(1977-)，男，江蘇張家港人，博士研究生，副教授，主要研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)、群智能系統(tǒng)任務(wù)規(guī)劃與優(yōu)化調(diào)度。