有向監控設備三維區域覆蓋算法①

丁治強,王 雷,張丙岳

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

1 引言

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

2 感知模型及區域劃分

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

圓盤感知模型:感知區域是一個以設備節點s為圓心的圓形區域,區域內某點p被檢測到的概率公式如下:

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

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

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

圖1 概率感知模型

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

圖2 方向感知模型

感知概率如下:

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

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

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

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

圖3 三維方向感知模型

圖4 區域劃分

3 基于虛擬力的感知方向調整方案

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

算法步驟如下:

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

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

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

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

受力分析示意如圖6所示,G是設備質心點,即受力點.

圖5 區域柵格化

圖6 受力分析

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

5)調整設備方向,將設備圍繞設備點轉動,使設備感知方向V與力的作用方向W平行.

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

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

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

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

在初始部署及感知方向調整結束后,仍有可能存在大量盲區,一是初始部署節點數量有限,二是設備感知范圍有限.通過在區域內剩余設備可部署位置上部署感知方向合適的節點來補充區域覆蓋率.

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

圖7 設備感知方向量化

圖8 區域劃分規格

下面考慮盲區,假定將使用方向調節算法優化后的設備覆蓋不超過50%的柵格化小區塊作為盲區,即盲區由覆蓋不超過一半的小區塊集合組成.

算法步驟如下:

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

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

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

4)若集合A為空,則結束算法,否則跳到步驟2)循環執行.

5 仿真實驗設計及結果分析

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

表1 區域設定

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

圖9 實驗結果

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

6 結語

本文針對現實中的有向監控設備網絡,提出在三維空間區域中結合虛擬力及區域權重的設備監控方向調整算法,以及基于貪心策略的區域覆蓋增強算法,Matlab仿真實驗表明,本文提出的方案能有效提高區域覆蓋率,減少盲區及節點冗余.