顧及視線效應(yīng)的城市戶外傳感網(wǎng)絡(luò)空間布局優(yōu)化

張笑雨,馬瀟雅,2

(1. 長(zhǎng)江大學(xué)地球科學(xué)學(xué)院,湖北 武漢 430100; 2. 自然資源部城市國(guó)土資源監(jiān)測(cè)與仿真重點(diǎn)試驗(yàn)室,廣東 深圳 518034)

城市戶外空間由不同類型傳感器構(gòu)成的傳感網(wǎng)絡(luò)是智慧城市基礎(chǔ)設(shè)施建設(shè)的重要內(nèi)容[1-3]。城市中的部分傳感器,如基于可見(jiàn)光的傳感器和激光雷達(dá)等,其服務(wù)范圍易受障礙物遮擋而導(dǎo)致其真實(shí)有效感知范圍非常有限[4]。這種服務(wù)需求與傳感器設(shè)備之間需要視距可見(jiàn)才能實(shí)現(xiàn)感知服務(wù)覆蓋的特性,在設(shè)施選址問(wèn)題中通常被定義為視線效應(yīng)(line-of-sight,LOS)[5-6]。在傳感網(wǎng)絡(luò)布局規(guī)劃中,決策者往往需要根據(jù)建筑物的形態(tài)與空間分布,在建筑物密集的區(qū)域部署大量傳感器,以實(shí)現(xiàn)對(duì)重點(diǎn)區(qū)域的無(wú)縫服務(wù)覆蓋[7-8]。以最小的設(shè)備數(shù)量和運(yùn)營(yíng)成本,實(shí)現(xiàn)有效服務(wù)范圍的最大化,是城市傳感網(wǎng)絡(luò)空間布局優(yōu)化問(wèn)題的核心目標(biāo)和主要難題[9]。

城市傳感網(wǎng)絡(luò)的空間布局優(yōu)化問(wèn)題從本質(zhì)上是一類特殊的最大覆蓋選址問(wèn)題(maximal covering location problem,MCLP)。針對(duì)不同設(shè)施選址的應(yīng)用場(chǎng)景,國(guó)內(nèi)外相關(guān)學(xué)者先后對(duì)經(jīng)典MCLP模型進(jìn)行了改進(jìn)。如文獻(xiàn)[10]提出了基于歐式距離同心圓模式的通信基站服務(wù)覆蓋模型;文獻(xiàn)[11]設(shè)計(jì)了顧及任意凸多邊形障礙物阻隔效應(yīng)的設(shè)施選址模型;文獻(xiàn)[12]設(shè)計(jì)了針對(duì)具有盲區(qū)的有向視覺(jué)傳感器在保持連通性前提下的最大保持覆蓋控制模型。

但顧及LOS服務(wù)覆蓋特性的選址優(yōu)化模型仍有待深入研究。如文獻(xiàn)[13]提出一種顧及LOS效應(yīng)的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化模型,但該模型不適用于建筑物密集分布的城市復(fù)雜建筑環(huán)境。文獻(xiàn)[14]提出了一種基于GIS視域分析方法的校園安全監(jiān)控?cái)z像頭網(wǎng)絡(luò)布局優(yōu)化模型,但模型僅用于解決小區(qū)域內(nèi)的選址優(yōu)化問(wèn)題,難以實(shí)現(xiàn)對(duì)大空間范圍的監(jiān)控傳感網(wǎng)絡(luò)的高效率優(yōu)化。

本文提出一種基于可視多邊形算法(visibility polygon,VP)[15]的城市戶外傳感網(wǎng)絡(luò)覆蓋模型。此外,MCLP問(wèn)題是一類典型NP-hard問(wèn)題[16-17],現(xiàn)有研究表明,以遺傳算法(genetic algorithm,GA)為代表的啟發(fā)式優(yōu)化算法是解決這類NP問(wèn)題的有效工具[18-21]。因此,本文將耦合遺傳算法和GIS技術(shù)相結(jié)合,設(shè)計(jì)城市戶外傳感網(wǎng)絡(luò)布局選址優(yōu)化算法,并以某城市街區(qū)傳感網(wǎng)絡(luò)中的攝像頭空間布局優(yōu)化問(wèn)題為例,對(duì)設(shè)計(jì)算法的有效性進(jìn)行驗(yàn)證。

1 顧及LOS效應(yīng)的傳感網(wǎng)絡(luò)布局優(yōu)化建模

1.1 顧及LOS效應(yīng)的傳感器服務(wù)覆蓋模擬

假定傳感網(wǎng)絡(luò)中布設(shè)的傳感器在沒(méi)有障礙物阻隔效應(yīng)的情況下,對(duì)于給定有效服務(wù)距離R,其在二維空間內(nèi)的服務(wù)覆蓋范圍是一個(gè)以傳感器為中心,半徑為R的理想圓[22]。然而,由于城市內(nèi)不規(guī)則分布建筑物的阻隔效應(yīng),傳感器的實(shí)際有效服務(wù)覆蓋范圍是一個(gè)不規(guī)則的多邊形(如圖1(b)所示)。對(duì)于任意給定地理坐標(biāo)的傳感器部署候選站點(diǎn)x和建筑物分布集合,利用VP算法和GIS獲取其真實(shí)服務(wù)覆蓋范圍的基本步驟如下。

圖1 顧及LOS效應(yīng)的傳感器服務(wù)覆蓋范圍建模

(2)傳感器站點(diǎn)的可視范圍生成。根據(jù)候選站點(diǎn)x的點(diǎn)位、理論覆蓋圓和圓形內(nèi)的建筑物分布、形狀,利用VP算法生成候選站點(diǎn)x對(duì)應(yīng)的可視多邊形。其基本思路為:以x為中心,以圓形區(qū)域內(nèi)的建筑物拐點(diǎn)為終點(diǎn),生成系列視線,若視線遇到障礙物或圓形邊界,且視線不與任意障礙物相交,則生成一個(gè)視線端點(diǎn)。該端點(diǎn)即為視域范圍的輪廓點(diǎn),按照順時(shí)針?lè)较蜻B接各端點(diǎn)即可生成可視多邊形(如圖1(b)所示)。關(guān)于VP算法更多詳細(xì)的情況可參考文獻(xiàn)[15]。

考慮相鄰傳感器設(shè)備之間LOS服務(wù)覆蓋可能存在重疊情況,在生成單個(gè)站點(diǎn)的可視范圍后,利用GIS的多邊形合并(Union)功能,將多個(gè)站點(diǎn)的獨(dú)立可視多邊形融合成單個(gè)多邊形。圖1(b)—(c)中的藍(lán)色多邊形區(qū)域分別為傳感器站點(diǎn)x和y獨(dú)立生成的可視服務(wù)范圍;圖1(d)則展示了規(guī)劃區(qū)域中被傳感網(wǎng)絡(luò)站點(diǎn)x和y最終覆蓋的區(qū)域。

1.2 傳感網(wǎng)絡(luò)布局優(yōu)化問(wèn)題的定義

二維場(chǎng)景下的傳感網(wǎng)絡(luò)布局優(yōu)化問(wèn)題主要包括對(duì)服務(wù)覆蓋需求、建筑物集合和候選站點(diǎn)集的建模。本文服務(wù)覆蓋需求可用連續(xù)多邊形進(jìn)行表達(dá),建筑物則使用二維多邊形表達(dá)。

獲取候選站點(diǎn)時(shí),首先利用GIS疊置分析方法,排除空間上不適合布設(shè)監(jiān)控站點(diǎn)的區(qū)域(如坑塘水面、建筑物、河流等)。利用系統(tǒng)抽樣方法按照固定間距對(duì)可部署的候選區(qū)域進(jìn)行抽樣[13],從而有效降低算法搜索空間。

基于給定的采樣間距d,對(duì)可部署區(qū)域進(jìn)行抽樣,d越小,則采樣和優(yōu)化算法的尋優(yōu)結(jié)果精度越高;反之,則精度越低。隨著采樣間距的降低,算法尋優(yōu)耗費(fèi)的時(shí)間呈指數(shù)上升。如圖2所示。

圖2 候選站點(diǎn)提取原理

根據(jù)上述原則,給出優(yōu)化問(wèn)題的變量約定如下:對(duì)于面積為SA的多邊形規(guī)劃區(qū)域A,通過(guò)系統(tǒng)抽樣方法獲取了由N個(gè)點(diǎn)構(gòu)成的候選站點(diǎn)集合C。假定計(jì)劃在區(qū)域A部署P個(gè)傳感器,每個(gè)傳感器設(shè)備的有效服務(wù)視距為R。從候選站點(diǎn)集合中選取P個(gè)位置,可獲得優(yōu)化問(wèn)題的一個(gè)可行解SL。

對(duì)可行解SL中的任意站點(diǎn)i,可利用VP算法獲取其可視多邊形V(i)。則范圍A內(nèi)所有被可行解SL內(nèi)P個(gè)站點(diǎn)覆蓋的多邊形區(qū)域LOSV定義為

使用訓(xùn)練得到的轉(zhuǎn)移概率矩陣和風(fēng)險(xiǎn)概率臨界值可以識(shí)別異常交易行為，以第二章中提到的短信支付流程為例，正常交易序列間的概率和黑客交易序列間的概率如圖6 所示，其中每個(gè)節(jié)點(diǎn)為從日志中提取的每一步交易名稱，節(jié)點(diǎn)間的值為交易間轉(zhuǎn)移的概率。

LOSV=∪iSLVi

(1)

式中,區(qū)域內(nèi)最終被所有站點(diǎn)覆蓋的區(qū)域LOSV是所有可視多邊形V(i)覆蓋區(qū)域的并集,可利用GIS的多邊形求并方法獲取。

按照以上約定,研究提出的顧及LOS效應(yīng)的傳感網(wǎng)絡(luò)布局優(yōu)化問(wèn)題定義為

Maximize: SC=(SLOS×100)/SA

(2)

Subject to

(3)

式中,SC為整個(gè)規(guī)劃區(qū)域內(nèi)被傳感網(wǎng)絡(luò)站點(diǎn)直接視線覆蓋的面積占比;SLOS為多邊形LOSV的面積;式(2)定義了問(wèn)題的優(yōu)化目標(biāo),即對(duì)于給定數(shù)量的傳感器站點(diǎn),實(shí)現(xiàn)其LOS覆蓋范圍的最大化;式(3)用于確保整個(gè)候選站點(diǎn)集合C中有且僅有不重復(fù)的P個(gè)站點(diǎn)被選中。

2 城市傳感網(wǎng)絡(luò)布局優(yōu)化方法

2.1 遺傳算法的優(yōu)化流程

遺傳算法尋優(yōu)能力強(qiáng)、算法框架靈活,目前已廣泛應(yīng)用于空間設(shè)施選址優(yōu)化領(lǐng)域[17,23-25]。經(jīng)典的遺傳算法流程如圖3所示。

圖3 遺傳算法的基本流程

遺傳算法步驟通常為:①編碼。通過(guò)一定的編碼方案,將現(xiàn)實(shí)世界問(wèn)題的決策變量逐個(gè)映射為基因;現(xiàn)實(shí)世界問(wèn)題的一個(gè)可行解即對(duì)應(yīng)遺傳算法中的一個(gè)染色體,構(gòu)成算法的基本進(jìn)化單元。②種群初始化。根據(jù)編碼方案和給定的種群規(guī)模,隨機(jī)生成第一代染色體種群。③個(gè)體適應(yīng)度評(píng)價(jià)。通過(guò)給定適應(yīng)度函數(shù)評(píng)估種群內(nèi)每個(gè)染色體的適應(yīng)度。適應(yīng)度高的染色體表明該染色體對(duì)應(yīng)可行解的質(zhì)量越優(yōu)。④終止條件判斷。判斷算法是否達(dá)到最大迭代次數(shù)或是否已收斂,若滿足其中任意一個(gè)條件,算法則終止并執(zhí)行步驟⑧,否則執(zhí)行步驟⑤。⑤選擇。通過(guò)“輪盤(pán)賭算法”隨機(jī)選擇雙親個(gè)體遺傳下一代,適應(yīng)度值越高的個(gè)體被選中的概率越大,從而實(shí)現(xiàn)染色體的“優(yōu)勝劣汰”。⑥交叉。兩雙親染色體的基因在同一位置處切斷其基因鏈,并相互交叉重新組合為兩個(gè)后代個(gè)體。⑦變異。將個(gè)體基因鏈中的基因用其他隨機(jī)選擇的新基因替換,從而生成新一代個(gè)體,繼續(xù)執(zhí)行步驟③。⑧解碼。輸出染色體種群中適應(yīng)度最高的個(gè)體作為優(yōu)化問(wèn)題的最優(yōu)解以輔助決策。循環(huán)執(zhí)行步驟③—⑦,直至滿足步驟④的終止條件。

2.2 面向城市傳感網(wǎng)絡(luò)空間布局優(yōu)化的遺傳算法

為耦合GIS技術(shù)以求解傳感網(wǎng)絡(luò)布局優(yōu)化問(wèn)題,經(jīng)典遺傳算法的編碼方案、個(gè)體適應(yīng)度評(píng)價(jià)、交叉和變異算子需要針對(duì)問(wèn)題的特點(diǎn)重新設(shè)計(jì)。

(1)編碼。對(duì)候選點(diǎn)集C中的每個(gè)站點(diǎn)進(jìn)行整數(shù)編碼,為每個(gè)候選站點(diǎn)分配整數(shù)作為其唯一的ID。對(duì)于任意給定數(shù)量的P個(gè)待部署站點(diǎn),其可行解對(duì)應(yīng)的染色體可用一條長(zhǎng)度為P的整型數(shù)組進(jìn)行表達(dá)。染色體中的每個(gè)基因存儲(chǔ)了其對(duì)應(yīng)站點(diǎn)在集合中的整數(shù)編號(hào)。

(2)個(gè)體適應(yīng)度評(píng)價(jià)。對(duì)于任意給定以整型數(shù)組表達(dá)的染色體,根據(jù)其整數(shù)編號(hào)找到其在集合C中的地理坐標(biāo),并在GIS的支持下,利用VP算法和式(2)—式(3)定義的目標(biāo)函數(shù)計(jì)算每個(gè)染色體的適應(yīng)度值。

(3)交叉。通過(guò)輪盤(pán)賭策略選擇兩個(gè)父代染色體后,根據(jù)給定的交叉概率Pc在染色體上隨機(jī)選擇一個(gè)交叉點(diǎn)。位于交叉點(diǎn)后的兩個(gè)父代染色體互相交換基因值,從而產(chǎn)生兩個(gè)新的染色體(如圖4(a)所示)。為了滿足式(3)定義的約束條件,若染色體中出現(xiàn)了兩重復(fù)的候選站點(diǎn)編號(hào),則對(duì)該染色體實(shí)施修復(fù)操作:去掉重復(fù)的編號(hào),從候選點(diǎn)集中隨機(jī)選取一新染色體代替。

圖4 交叉與變異操作

(4)變異。根據(jù)給定的變異概率Pm實(shí)施變異操作時(shí),隨機(jī)從候選站點(diǎn)集合C中選擇一個(gè)不存在于當(dāng)前種群中的站點(diǎn)以替換當(dāng)前基因的站點(diǎn)編號(hào)(如圖4(b)所示),從而實(shí)現(xiàn)染色體的變異。

3 實(shí)證研究

3.1 試驗(yàn)設(shè)計(jì)

以某城市街區(qū)公共區(qū)域攝像頭布局優(yōu)化問(wèn)題為案例,研究區(qū)總面積約為36.7 hm2,區(qū)域范圍內(nèi)建筑面積密度約為0.37,研究區(qū)及建筑物形狀分布如圖5所示。

圖5 研究區(qū)域

排除建筑物等不適宜部署區(qū)域后,按照15 m的采樣間距,在研究區(qū)利用系統(tǒng)抽樣方法獲得995個(gè)攝像頭站點(diǎn)布設(shè)候選點(diǎn)。在該區(qū)域布設(shè)有效監(jiān)控視距為40 m、360°旋轉(zhuǎn)的監(jiān)控?cái)z像頭。監(jiān)控網(wǎng)絡(luò)布設(shè)的目標(biāo)為覆蓋整個(gè)街區(qū)面積的90%。P的初始值設(shè)置為80,試驗(yàn)時(shí)P值逐次增加5,直至P=150。確保每次試驗(yàn)算法都能收斂,設(shè)置算法最大迭代次數(shù)為2000,種群規(guī)模為100。交叉概率設(shè)置為0.8,變異概率設(shè)置為0.08。具體參數(shù)配置見(jiàn)表1。

表1 遺傳算法參數(shù)配置

3.2 試驗(yàn)結(jié)果

基于試驗(yàn)區(qū)數(shù)據(jù)和表1設(shè)置的算法參數(shù),通過(guò)多次運(yùn)行優(yōu)化算法后,獲得試驗(yàn)區(qū)不同數(shù)量下的監(jiān)控?cái)z像頭網(wǎng)絡(luò)最優(yōu)服務(wù)覆蓋率和空間分布,如圖6—圖7所示。

圖6 不同攝像頭設(shè)施數(shù)量下的最優(yōu)服務(wù)覆蓋率

圖7 LOS服務(wù)覆蓋范圍

當(dāng)研究區(qū)內(nèi)部署的設(shè)施數(shù)量分別為80、120、150時(shí),由算法獲取的最優(yōu)服務(wù)覆蓋率分別為74.67%、90%和 95.74%?？傮w上看,隨著區(qū)域內(nèi)部署監(jiān)控?cái)z像頭個(gè)數(shù)的增加,所能有效覆蓋的區(qū)域也隨之穩(wěn)步增大。然而,當(dāng)站點(diǎn)個(gè)數(shù)超過(guò)120個(gè)時(shí),通過(guò)增加站點(diǎn)個(gè)數(shù)提升覆蓋比率的趨勢(shì)有所放緩。

圖7中,當(dāng)P=80時(shí),優(yōu)化算法傾向于將攝像頭站點(diǎn)布設(shè)于建筑物稀疏分布的開(kāi)闊區(qū)域,從而獲得更好的服務(wù)覆蓋效果;而在建筑物密集分布的區(qū)域布設(shè)同等數(shù)量的設(shè)施可獲得的有效服務(wù)覆蓋明顯低于開(kāi)闊區(qū)域。因此,當(dāng)P太小時(shí),在建筑物密集分布的區(qū)域出現(xiàn)了大量的監(jiān)控服務(wù)盲區(qū)(圖7(a)中A、B和C空白區(qū)域)。而隨著站點(diǎn)數(shù)量的增加,越來(lái)越多的攝像頭站點(diǎn)被布設(shè)到建筑物密集分布的區(qū)域,以減少監(jiān)控盲區(qū)。站點(diǎn)的空間分布和建筑物的分布狀況存在明顯的相關(guān)性。從圖7(a)—(h)可以看出,隨著P值的增加,圖7(a)中位于建筑物密集分布區(qū)的大片監(jiān)控盲區(qū)逐漸縮小,直至徹底消失(圖7(h)中D和E區(qū)域)。由此可見(jiàn),本文設(shè)計(jì)的傳感網(wǎng)絡(luò)布局優(yōu)化算法能夠有效地提高網(wǎng)絡(luò)的實(shí)際服務(wù)覆蓋范圍。

考慮試驗(yàn)區(qū)的監(jiān)控服務(wù)覆蓋率目標(biāo)和攝像頭監(jiān)控網(wǎng)絡(luò)布設(shè)、運(yùn)營(yíng)成本,結(jié)合模型獲取的優(yōu)化方案,綜合確定當(dāng)P=120時(shí),圖7(e)中的攝像頭布局是一種合理可行且具有較好經(jīng)濟(jì)效益的監(jiān)控網(wǎng)絡(luò)布設(shè)方案。

3.3 LOS效應(yīng)對(duì)優(yōu)化方案質(zhì)量的影響

為進(jìn)一步評(píng)估網(wǎng)絡(luò)布局優(yōu)化時(shí),考慮LOS效應(yīng)的必要性,研究設(shè)計(jì)了一個(gè)未考慮LOS效應(yīng)的對(duì)比試驗(yàn)。將建筑物集合從模型運(yùn)行數(shù)據(jù)集中移除,即可直接模擬未考慮LOS效應(yīng)的監(jiān)控網(wǎng)絡(luò)布局優(yōu)化場(chǎng)景。在對(duì)比試驗(yàn)中,將設(shè)施數(shù)量P初始值設(shè)置為70,其他算法參數(shù)設(shè)置與參照試驗(yàn)完全一致。未顧及LOS效應(yīng)的監(jiān)控網(wǎng)絡(luò)布局優(yōu)化結(jié)果分別如圖8、圖9所示。

圖8 LOS效應(yīng)對(duì)設(shè)施服務(wù)覆蓋范圍的影響

當(dāng)數(shù)量為70時(shí),在不考慮LOS效應(yīng)的情景下,算法獲得的理論最優(yōu)服務(wù)覆蓋率已達(dá)85.49%;而受LOS效應(yīng)的影響,該方案對(duì)應(yīng)的實(shí)際有效監(jiān)控服務(wù)覆蓋率僅36.08%。在未考慮LOS效應(yīng)的情景下,理論上僅需約80個(gè)監(jiān)控?cái)z像頭即可實(shí)現(xiàn)對(duì)試驗(yàn)區(qū)內(nèi)90%以上的區(qū)域進(jìn)行覆蓋。而在LOS效應(yīng)的影響下,其真實(shí)有效的LOS監(jiān)控覆蓋率僅為40.14%,比理論覆蓋率低52.31%。在不考慮LOS效應(yīng)下,隨著區(qū)域部署攝像頭個(gè)數(shù)的增加,其理論監(jiān)控覆蓋比率穩(wěn)步上升。而由于受到LOS效應(yīng)的影響,其對(duì)應(yīng)的真實(shí)LOS監(jiān)控服務(wù)覆蓋比率呈現(xiàn)出一定的波動(dòng)性。

此外,由圖9可知,在不顧及LOS效應(yīng)的場(chǎng)景下,優(yōu)化算法傾向于在研究區(qū)內(nèi)均勻地選取備選站點(diǎn),導(dǎo)致所獲得的優(yōu)化方案存在大量的監(jiān)控服務(wù)盲區(qū)。因此,在選址優(yōu)化模型中實(shí)現(xiàn)對(duì)LOS效應(yīng)的模擬仿真,對(duì)于傳感網(wǎng)絡(luò)布局優(yōu)化十分必要。

4 結(jié) 語(yǔ)

城市傳感網(wǎng)中,如攝像頭等類型的傳感器需直接視距可見(jiàn),方能實(shí)現(xiàn)有效覆蓋的特殊服務(wù)覆蓋性,而利用現(xiàn)有各類基于MCLP模型的方法難以滿足傳感網(wǎng)絡(luò)空間布局優(yōu)化的需要。針對(duì)該問(wèn)題,本文提出了一種基于可視多邊形算法的傳感器服務(wù)范圍建模模型,實(shí)現(xiàn)了對(duì)顧及LOS效應(yīng)的傳感器站點(diǎn)有效覆蓋范圍的模擬仿真。耦合GIS和遺傳算法完成區(qū)域傳感網(wǎng)絡(luò)空間布局的優(yōu)化。最后,以某城市街區(qū)傳感網(wǎng)絡(luò)中的攝像頭空間布局優(yōu)化問(wèn)題為例,驗(yàn)證了優(yōu)化模型的有效性。

試驗(yàn)結(jié)果表明,本文提出的模型能夠有效提高傳感網(wǎng)絡(luò)的真實(shí)空間服務(wù)范圍。另外,對(duì)比試驗(yàn)結(jié)果表明,在不顧及LOS效應(yīng)情景下,優(yōu)化模型傾向于在研究區(qū)內(nèi)均衡的布設(shè)監(jiān)控?cái)z像頭站點(diǎn)。然而,由于建筑物對(duì)監(jiān)控范圍的限制作用,由此獲得的優(yōu)化方案其真實(shí)有效服務(wù)覆蓋比理論服務(wù)覆蓋范圍低達(dá)52.31%。因此,在傳感網(wǎng)絡(luò)布局優(yōu)化過(guò)程中顧及傳感器服務(wù)覆蓋的視線效應(yīng)是非常必要的。

本文設(shè)計(jì)的顧及LOS效應(yīng)的傳感網(wǎng)絡(luò)布局優(yōu)化模型,對(duì)于其他具有相似服務(wù)覆蓋特性的設(shè)施網(wǎng)絡(luò)布局優(yōu)化具有非常重要的借鑒意義。如路燈、智慧城市Wi-Fi熱點(diǎn)、5G通信基站等。后續(xù)研究將關(guān)注具有類似LOS服務(wù)覆蓋特征的設(shè)施網(wǎng)絡(luò)優(yōu)化。