丁治強,王 雷,張丙岳

(中國科學技術(shù)大學 信息科學與技術(shù)學院 自動化系,合肥 230027)

1 引言

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

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

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

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

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

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

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

圖1 概率感知模型

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

圖2 方向感知模型

感知概率如下:

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

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

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

本文研究以實際城鎮(zhèn)區(qū)域為背景,有各種功能分區(qū),本文中針對四類區(qū)域進行研究,分別是街道,廣場,住宅區(qū),障礙物 (高墻)[11].將其抽象出來,在俯視的二維空間上的表示如圖4.

圖3 三維方向感知模型

圖4 區(qū)域劃分

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

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

算法步驟如下:

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

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

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

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

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

圖5 區(qū)域柵格化

圖6 受力分析

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

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

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

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

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

4 基于貪心策略的補充部署方案

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

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

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

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

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

算法步驟如下:

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

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

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

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

5 仿真實驗設(shè)計及結(jié)果分析

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

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

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

圖9 實驗結(jié)果

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

6 結(jié)語

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