丁治強(qiáng),王 雷,張丙岳

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)與技術(shù)學(xué)院 自動(dòng)化系,合肥 230027)

1 引言

當(dāng)今社會(huì),城鎮(zhèn)規(guī)模越來(lái)越大,區(qū)域狀況愈加復(fù)雜,特別是人口密集地區(qū),復(fù)雜的環(huán)境給城市安全管理和威脅預(yù)防帶來(lái)了極大挑戰(zhàn)[1],若沒(méi)有有效的監(jiān)控及應(yīng)急處置預(yù)案,很容易發(fā)生危險(xiǎn)情況,威脅人們的生命財(cái)產(chǎn)安全,在這種情況下,只依靠人力巡邏等簡(jiǎn)單手段無(wú)法應(yīng)對(duì)如此嚴(yán)峻的挑戰(zhàn),無(wú)法做到防微杜漸,因此有效的監(jiān)控手段就顯得尤為重要[2],有效監(jiān)控的目標(biāo)就是對(duì)重要區(qū)域做到全方位無(wú)死角監(jiān)控,即盡可能提高監(jiān)控設(shè)備網(wǎng)絡(luò)的覆蓋率.本文針對(duì)復(fù)雜區(qū)域的監(jiān)控設(shè)備覆蓋算法進(jìn)行了研究,以期能對(duì)區(qū)域進(jìn)行更加有效的監(jiān)控,預(yù)防潛在的威脅.在區(qū)域覆蓋算法方面已有一些較為成熟的研究,從以下幾個(gè)方面來(lái)概括說(shuō)明,從區(qū)域的角度看,大部分研究針對(duì)二維空間區(qū)域,如著名的藝術(shù)館走廊監(jiān)控問(wèn)題[3]及圓周覆蓋問(wèn)題[4],文獻(xiàn)[5]提出了一種二維無(wú)線傳感器網(wǎng)絡(luò)的覆蓋性能提高算法.從設(shè)備的角度看,大部分研究是針對(duì)無(wú)線傳感器網(wǎng)絡(luò)[6,7],設(shè)備之間可以互相通信,且部署位置不定,靈活性較大.從感知區(qū)域的角度,大部分研究中設(shè)備感知區(qū)域?yàn)闊o(wú)向的圓形或球形區(qū)域[8],從覆蓋的目標(biāo)來(lái)看,大部分的研究是簡(jiǎn)單的完全區(qū)域覆蓋,不考慮實(shí)際的復(fù)雜場(chǎng)景.已有的一些三維空間區(qū)域的覆蓋算法研究成果,如文獻(xiàn)[9]中是將二維空間上的覆蓋算法擴(kuò)展到三維空間,抽象成數(shù)學(xué)模型進(jìn)行研究,文獻(xiàn)[10]中針對(duì)移動(dòng)傳感器網(wǎng)絡(luò),提出了一種基于改進(jìn)粒子群遺傳算法的三維覆蓋算法.從已有的研究成果可以看出,現(xiàn)有研究對(duì)有向感知設(shè)備的研究較少,對(duì)三維空間復(fù)雜區(qū)域的研究較少,即缺乏區(qū)域劃分,對(duì)區(qū)域中障礙物,重要監(jiān)控區(qū)域的區(qū)分不夠明確.本文針對(duì)三維空間區(qū)域,考慮區(qū)域中的復(fù)雜環(huán)境,并為各覆蓋區(qū)域區(qū)分重要程度,以此計(jì)算柵格化后的各區(qū)塊代表點(diǎn)及臨近設(shè)備對(duì)范圍內(nèi)設(shè)備的虛擬作用力,對(duì)有向設(shè)備的感知方向進(jìn)行調(diào)節(jié),以此提高區(qū)域覆蓋率,此外,針對(duì)調(diào)整部署后的盲區(qū)采用貪心策略增加設(shè)備節(jié)點(diǎn),減少節(jié)點(diǎn)冗余及重疊覆蓋,并用MATLAB進(jìn)行仿真實(shí)驗(yàn).

2 感知模型及區(qū)域劃分

感知模型是指設(shè)備的感知區(qū)域及作用范圍,與設(shè)備類(lèi)型相關(guān),不同的設(shè)備有不同的感知區(qū)域,常見(jiàn)的二維空間設(shè)備感知模型有以下幾種:圓盤(pán)感知模型,概率感知模型,方向感知模型.

圓盤(pán)感知模型:感知區(qū)域是一個(gè)以設(shè)備節(jié)點(diǎn)s為圓心的圓形區(qū)域,區(qū)域內(nèi)某點(diǎn)p被檢測(cè)到的概率公式如下:

其中,R為設(shè)備感知半徑,d(s,p)為s與p之間的歐式距離.擴(kuò)展到三維空間則為球體區(qū)域.

概率感知模型:是在圓盤(pán)感知模型的基礎(chǔ)上進(jìn)行的改進(jìn),假定在圓內(nèi)感知概率隨該點(diǎn)到圓心的距離增加而衰減,其感知概率公式如下:

其中,α =d(s,p)-(r-re),β,λ是可變參數(shù),用來(lái)刻畫(huà)衰減概率,r及re如圖1模型所示.

圖1 概率感知模型

方向感知模型:考慮現(xiàn)實(shí)中的一些設(shè)備,他們的感知區(qū)域并不是一個(gè)規(guī)則的區(qū)域,也并非360度無(wú)死角,像攝像頭的監(jiān)控區(qū)域就是在面對(duì)方向上的一定距離內(nèi)的一片區(qū)域.考慮二維空間上的帶方向的設(shè)備感知區(qū)域,將其抽象出來(lái)如圖2所示.

圖2 方向感知模型

感知概率如下:

其中,β是區(qū)域中某點(diǎn)到圓心的連線與方向向量V之間的夾角.

三維方向感知模型:將二維感知模型擴(kuò)展到三維,感知區(qū)域如圖3所示.

三維有向感知區(qū)域可以用四元組 (S,V,R,α)來(lái)表示,其中s(x,y,z)表示設(shè)備中心點(diǎn)三維坐標(biāo),V代表感知方向,R是感知半徑,圓錐角 α代表設(shè)備感知范圍.本文使用該模型作為設(shè)備感知模型.

本文研究以實(shí)際城鎮(zhèn)區(qū)域?yàn)楸尘?有各種功能分區(qū),本文中針對(duì)四類(lèi)區(qū)域進(jìn)行研究,分別是街道,廣場(chǎng),住宅區(qū),障礙物 (高墻)[11].將其抽象出來(lái),在俯視的二維空間上的表示如圖4.

圖3 三維方向感知模型

圖4 區(qū)域劃分

3 基于虛擬力的感知方向調(diào)整方案

初始情況下,三維空間中隨機(jī)放置一些設(shè)備節(jié)點(diǎn),感知方向也隨機(jī),通過(guò)以下算法調(diào)整各節(jié)點(diǎn)感知方向,使區(qū)域有效覆蓋率增加.

算法步驟如下:

1)區(qū)域劃分,將三維空間區(qū)域劃分出如圖4所示的四部分,覆蓋算法設(shè)計(jì)時(shí)只考慮覆蓋除障礙物外的有效區(qū)域[12].

2)區(qū)域柵格化,將劃分出的四部分區(qū)域分割成緊鄰的細(xì)粒度立方體方塊,每個(gè)小方塊的中心作為區(qū)塊代表點(diǎn),即虛擬力作用點(diǎn),示意圖如圖5.

3)設(shè)備部署,根據(jù)實(shí)際,設(shè)備可部署位置相對(duì)固定,仿真時(shí)隨機(jī)設(shè)置一些可部署點(diǎn),并放置一些感知方向隨機(jī)的設(shè)備.

4)計(jì)算虛擬合力,每臺(tái)設(shè)備的一定范圍內(nèi)的區(qū)塊代表點(diǎn)及其他設(shè)備對(duì)該設(shè)備具有力的作用,計(jì)算所有這些點(diǎn)對(duì)設(shè)備作用的合力.

受力分析示意如圖6所示,G是設(shè)備質(zhì)心點(diǎn),即受力點(diǎn).

圖5 區(qū)域柵格化

圖6 受力分析

單個(gè)區(qū)塊代表點(diǎn)或其他設(shè)備i對(duì)設(shè)備j的作用力如式(4)所示:

5)調(diào)整設(shè)備方向,將設(shè)備圍繞設(shè)備點(diǎn)轉(zhuǎn)動(dòng),使設(shè)備感知方向V與力的作用方向W平行.

6)計(jì)算區(qū)域覆蓋率,區(qū)域覆蓋率算法如式(5)所示:

其中,s?表示覆蓋的區(qū)域面積,s是區(qū)域總面積(只計(jì)算有效區(qū)域).

并與初始部署時(shí)的區(qū)域覆蓋率作比較,評(píng)估區(qū)域覆蓋提高的比率.

4 基于貪心策略的補(bǔ)充部署方案

在初始部署及感知方向調(diào)整結(jié)束后,仍有可能存在大量盲區(qū),一是初始部署節(jié)點(diǎn)數(shù)量有限,二是設(shè)備感知范圍有限.通過(guò)在區(qū)域內(nèi)剩余設(shè)備可部署位置上部署感知方向合適的節(jié)點(diǎn)來(lái)補(bǔ)充區(qū)域覆蓋率.

首先,以設(shè)備感知模型方向向量V代表設(shè)備,由于設(shè)備感知方向可在三維空間任意變化,為了研究方便,本文將其量化,以45°為步長(zhǎng),則在三維空間上共有18個(gè)可變位置,示意圖如圖7所示.

圖7 設(shè)備感知方向量化

圖8 區(qū)域劃分規(guī)格

下面考慮盲區(qū),假定將使用方向調(diào)節(jié)算法優(yōu)化后的設(shè)備覆蓋不超過(guò)50%的柵格化小區(qū)塊作為盲區(qū),即盲區(qū)由覆蓋不超過(guò)一半的小區(qū)塊集合組成.

算法步驟如下:

1)確定可部署位置上未部署設(shè)備的節(jié)點(diǎn)集合A={a1,a2,a3,···},以及以柵格化區(qū)塊組成的盲區(qū)B={b1,b2,b3,···}.

2)計(jì)算集合A中每個(gè)元素在18個(gè)量化感知方向上分別可包含的盲區(qū)區(qū)塊數(shù)量,求出其最大值,集合表示為Am={a1m,a2m,a3m,···}.

3)使用類(lèi)似貪心算法的思想,在集合Am中選擇值最大的元素,即選擇能覆蓋盡可能多的盲區(qū)區(qū)塊的可部署節(jié)點(diǎn)作為選定部署點(diǎn),并且將選中點(diǎn)相應(yīng)的在集合A中的元素去除.

4)若集合A為空,則結(jié)束算法,否則跳到步驟2)循環(huán)執(zhí)行.

5 仿真實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

使用Matlab工具進(jìn)行仿真實(shí)驗(yàn),區(qū)域設(shè)定如表1所示.其他參數(shù)設(shè)定如下:設(shè)備感知半徑為30,感知區(qū)域角70°,三維空間環(huán)境中預(yù)先設(shè)置16個(gè)設(shè)備可部署點(diǎn),初始時(shí)部署8臺(tái)設(shè)備,其感知方向隨機(jī)設(shè)置,并作為隨機(jī)部署方案與本文提出的改進(jìn)方案進(jìn)行對(duì)比.區(qū)域柵格化的步長(zhǎng)(即小區(qū)塊的尺寸)從3到10以1為步進(jìn)單位,產(chǎn)生共八種柵格化方案.區(qū)域權(quán)重設(shè)定:街道為-5,廣場(chǎng)為-3,居民區(qū)為-2,障礙物為 8,臨近設(shè)備為 1.

表1 區(qū)域設(shè)定

檢驗(yàn)在不同區(qū)域柵格化粒度情形下,隨機(jī)部署方案及我們提出的感知方向調(diào)整方案和設(shè)備增加部署方案在區(qū)域覆蓋率上的對(duì)比情況,結(jié)果如圖9所示.

圖9 實(shí)驗(yàn)結(jié)果

從圖9中可以看出,在實(shí)驗(yàn)參數(shù)設(shè)定下,隨機(jī)部署方案覆蓋率較低,只有大約30%左右,原因是感知方向過(guò)于隨機(jī),無(wú)法對(duì)區(qū)域進(jìn)行有效的監(jiān)控,提出的感知方向調(diào)整方案則有效增強(qiáng)了區(qū)域覆蓋,將區(qū)域覆蓋率提高到60%左右,而增加設(shè)備部署后,盲區(qū)狀況得到有效改善,區(qū)域覆蓋率可達(dá)90%左右,不同柵格化方案均能得到同樣的對(duì)比結(jié)果,證明了算法的可行性及有效性.

6 結(jié)語(yǔ)

本文針對(duì)現(xiàn)實(shí)中的有向監(jiān)控設(shè)備網(wǎng)絡(luò),提出在三維空間區(qū)域中結(jié)合虛擬力及區(qū)域權(quán)重的設(shè)備監(jiān)控方向調(diào)整算法,以及基于貪心策略的區(qū)域覆蓋增強(qiáng)算法,Matlab仿真實(shí)驗(yàn)表明,本文提出的方案能有效提高區(qū)域覆蓋率,減少盲區(qū)及節(jié)點(diǎn)冗余.