路邊停車檢測物聯(lián)網(wǎng)系統(tǒng)網(wǎng)關(guān)部署算法

郭小紅,張足生,李文杰,盧曜杰,柴浩镈

(東莞理工學(xué)院 網(wǎng)絡(luò)空間安全學(xué)院,廣東 東莞 523808)

0 引 言

隨著國內(nèi)城市化進(jìn)程的不斷加快,機(jī)動(dòng)車保有量急劇增加,停車難問題變得越來越嚴(yán)重。在高峰時(shí)段尋找一個(gè)可用的路邊停車位通常需要花費(fèi)較長時(shí)間,這會(huì)導(dǎo)致額外的交通擁堵和空氣污染?；谖锫?lián)網(wǎng)的智慧路邊停車檢測系統(tǒng)是緩解停車難問題的重要途徑之一[1-4]。

路邊停車檢測物聯(lián)網(wǎng)系統(tǒng)是由傳感器節(jié)點(diǎn)和網(wǎng)關(guān)組成的兩層網(wǎng)絡(luò)結(jié)構(gòu),在每個(gè)停車位上安裝傳感器節(jié)點(diǎn)對停車狀態(tài)進(jìn)行實(shí)時(shí)采集,網(wǎng)關(guān)節(jié)點(diǎn)安裝在路邊基礎(chǔ)設(shè)施(例如燈柱)上;傳感器節(jié)點(diǎn)將檢測結(jié)果發(fā)送給路側(cè)的網(wǎng)關(guān)節(jié)點(diǎn),再由網(wǎng)關(guān)節(jié)點(diǎn)轉(zhuǎn)發(fā)給遠(yuǎn)程服務(wù)器。網(wǎng)關(guān)設(shè)備的成本較高,如何在確保網(wǎng)絡(luò)連通性的前提下,合理選擇網(wǎng)關(guān)的布置位置使系統(tǒng)成本最小化是該文關(guān)注的問題。

路邊停車檢測物聯(lián)網(wǎng)系統(tǒng)網(wǎng)關(guān)部署具有如下顯著特征:其一,網(wǎng)關(guān)部署位置受限,為節(jié)約成本,網(wǎng)關(guān)通常部署在路邊燈柱上,即把路邊燈柱坐標(biāo)作為候選點(diǎn)集合,從中選取一個(gè)子集用于網(wǎng)關(guān)部署,實(shí)現(xiàn)傳感器節(jié)點(diǎn)的全覆蓋;其二,網(wǎng)關(guān)覆蓋對象是路邊停車檢測傳感器節(jié)點(diǎn),傳感器節(jié)點(diǎn)沿道路呈線狀分布且位置已知。已有算法大都沒有考慮以上特征,不能較好地適用于路邊停車場景。該文研究適于路邊停車檢測網(wǎng)關(guān)部署算法,主要貢獻(xiàn)如下:

(1)對網(wǎng)關(guān)部署問題進(jìn)行了數(shù)學(xué)定義,并將該問題抽象為集合覆蓋問題;

(2)提出了線狀部署算法,將路網(wǎng)中分布的傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)轉(zhuǎn)換為線性序列,采用按序迭代搜索方法得到一個(gè)覆蓋所有傳感器節(jié)點(diǎn)的最小網(wǎng)關(guān)集合;

(3)開發(fā)了可實(shí)用的路邊停車檢測網(wǎng)關(guān)部署系統(tǒng),并對提出的算法開展了仿真實(shí)驗(yàn)和真實(shí)數(shù)據(jù)集驗(yàn)證,結(jié)果表明該算法相比傳統(tǒng)算法能以較小的時(shí)間復(fù)雜度獲得更好的覆蓋效果。

1 相關(guān)工作

無線傳感器網(wǎng)絡(luò)的網(wǎng)關(guān)部署問題已有較多研究成果,大多以優(yōu)化部署位置、部署數(shù)量、能量消耗、流量負(fù)載等為目標(biāo),學(xué)者們針對不同的目標(biāo)提出了多種解決辦法。

文獻(xiàn)[5]提出了一種近似算法,期望以最小化網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量實(shí)現(xiàn)區(qū)域傳感器節(jié)點(diǎn)的覆蓋。文獻(xiàn)[6]將網(wǎng)關(guān)部署問題轉(zhuǎn)化為最小化網(wǎng)絡(luò)全局能耗的混合整數(shù)線性規(guī)劃問題,并提出了一種基于啟發(fā)式的貪婪算法。文獻(xiàn)[7]提出基于度和權(quán)重的兩種啟發(fā)式算法,通過將網(wǎng)絡(luò)節(jié)點(diǎn)分組來進(jìn)行網(wǎng)關(guān)選擇,以實(shí)現(xiàn)最小化網(wǎng)關(guān)數(shù)目和最小化節(jié)點(diǎn)與網(wǎng)關(guān)的路徑長度的目標(biāo)。文獻(xiàn)[8]為了平衡網(wǎng)絡(luò)負(fù)載,提出基于流量模式和網(wǎng)絡(luò)拓?fù)涞膯l(fā)式網(wǎng)關(guān)部署算法。文獻(xiàn)[9]為了找到網(wǎng)絡(luò)中所需網(wǎng)關(guān)的最小數(shù)量及其最佳位置以滿足不同的業(yè)務(wù)需求,提出一種基于外部懲罰函數(shù)模擬退火的啟發(fā)式算法。文獻(xiàn)[10]為了降低網(wǎng)絡(luò)生存成本并優(yōu)化無線傳感器網(wǎng)格的通信,提出了一種用于多網(wǎng)關(guān)部署的線性規(guī)劃啟發(fā)式方法。

文獻(xiàn)[11]提出了改進(jìn)的粒子群優(yōu)化算法,以網(wǎng)絡(luò)的負(fù)載均衡為目標(biāo)來優(yōu)化網(wǎng)關(guān)的部署。文獻(xiàn)[12]為了降低部署成本和系統(tǒng)干擾,采用多目標(biāo)粒子群算法來優(yōu)化信道分配和部署網(wǎng)關(guān)。文獻(xiàn)[13-14]也采用類似的粒子群算法解決無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)部署問題。文獻(xiàn)[15]提出了一種網(wǎng)關(guān)選擇算法,在保證網(wǎng)絡(luò)全覆蓋的情況下,利用遺傳算法最小化網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量,該算法可以有效減少網(wǎng)關(guān)部署數(shù)量。文獻(xiàn)[16]以最小化數(shù)據(jù)包延遲為目標(biāo),提出了一種遺傳算法來解決無線自組織網(wǎng)絡(luò)中的網(wǎng)關(guān)分配和調(diào)度問題。文獻(xiàn)[17]基于網(wǎng)絡(luò)流量選出候選網(wǎng)關(guān),然后提出一種聚類算法從候選網(wǎng)關(guān)中選出最優(yōu)的網(wǎng)關(guān)。文獻(xiàn)[18]將邊緣網(wǎng)關(guān)部署問題轉(zhuǎn)化為二進(jìn)制整數(shù)規(guī)劃問題,并設(shè)計(jì)了一種基于Q-learning強(qiáng)化學(xué)習(xí)的改進(jìn)蜘蛛猴算法求解。

還有許多其他方法解決網(wǎng)關(guān)部署問題。文獻(xiàn)[19]提出了一種多項(xiàng)式時(shí)間近似最優(yōu)算法,通過不斷迭代求解最小支配集,并利用最小支配集求解得到最小化的網(wǎng)關(guān)數(shù)目。文獻(xiàn)[20]利用網(wǎng)關(guān)選擇算法求解網(wǎng)關(guān)的部署位置,構(gòu)建以網(wǎng)關(guān)為根的轉(zhuǎn)發(fā)樹,然后通過轉(zhuǎn)發(fā)樹間的節(jié)點(diǎn)遷移實(shí)現(xiàn)網(wǎng)關(guān)的負(fù)載均衡。文獻(xiàn)[21]提出了一種基于高斯混合模型的邊緣計(jì)算網(wǎng)關(guān)設(shè)備部署方法,該方法可以在保證每個(gè)網(wǎng)關(guān)設(shè)備負(fù)載均衡的同時(shí)優(yōu)化部署網(wǎng)關(guān)設(shè)備的數(shù)量。文獻(xiàn)[22]提出了一種基于Stackelberg博弈的網(wǎng)關(guān)選擇與關(guān)聯(lián)問題的解析模型,在不同干擾下優(yōu)化傳感器網(wǎng)絡(luò)的性能。

目前基于無線傳感器網(wǎng)絡(luò)的部署問題的研究,大部分是針對傳感器隨機(jī)分布、網(wǎng)關(guān)位置不受限制的情況下,如何部署網(wǎng)關(guān)對傳感器節(jié)點(diǎn)進(jìn)行覆蓋,不符合路邊停車檢測的應(yīng)用場景。因此,該文研究路邊停車檢測物聯(lián)網(wǎng)系統(tǒng)網(wǎng)關(guān)部署優(yōu)化算法,確保每一個(gè)傳感器節(jié)點(diǎn)至少被一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)覆蓋的情況下,最小化網(wǎng)關(guān)節(jié)點(diǎn)的部署數(shù)量以降低網(wǎng)關(guān)的部署成本。

2 問題描述與建模

路邊停車檢測物聯(lián)網(wǎng)是一種兩層結(jié)構(gòu)網(wǎng)絡(luò),如圖1所示。第一層為部署在每個(gè)停車位上的傳感器節(jié)點(diǎn),實(shí)現(xiàn)停車位狀態(tài)的實(shí)時(shí)檢測。第二層為網(wǎng)關(guān)節(jié)點(diǎn)與其通信范圍內(nèi)的所有傳感器節(jié)點(diǎn)及遠(yuǎn)程服務(wù)器之間的上行和下行通信。為了節(jié)約部署成本,網(wǎng)關(guān)節(jié)點(diǎn)通常安裝在路邊已有的基礎(chǔ)設(shè)施上(如路燈),如圖1所示,道路兩側(cè)的燈柱都是部署網(wǎng)關(guān)的候選點(diǎn)。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)

給定W=(S,G),S={s1,s2,…,sn}為路邊停車檢測傳感器節(jié)點(diǎn)集合,G={g1,g2,…,gm}為網(wǎng)關(guān)候選節(jié)點(diǎn)集合。傳感器節(jié)點(diǎn)si由電池供電,為了節(jié)省能量簡化通信模型,si只能與附近的網(wǎng)關(guān)節(jié)點(diǎn)gj通信,傳感器節(jié)點(diǎn)之間不通信。

網(wǎng)關(guān)部署時(shí)選擇路側(cè)已有的基礎(chǔ)設(shè)施(如路燈)作為候選位置。該文的目標(biāo)是在m個(gè)候選位置中部署最少的網(wǎng)關(guān),使這些網(wǎng)關(guān)能覆蓋所有的傳感器節(jié)點(diǎn),即保證每一個(gè)傳感器節(jié)點(diǎn)至少能與一個(gè)網(wǎng)關(guān)通信。網(wǎng)關(guān)部署問題相關(guān)的定義如下:

定義1(傳感器節(jié)點(diǎn)坐標(biāo)集):令(six,siy)表示傳感器節(jié)點(diǎn)si(i=1,2,…,n)在路邊停車位上的坐標(biāo),s={(s1x,s1y),(s2x,s2y),…,(snx,sny)}為傳感器節(jié)點(diǎn)坐標(biāo)集。

定義2(網(wǎng)關(guān)候選節(jié)點(diǎn)坐標(biāo)集):令(gjx,gjy)表示網(wǎng)關(guān)候選點(diǎn)gj(j=1,2,…,m)在路側(cè)基礎(chǔ)設(shè)施上的坐標(biāo),g={(g1x,g1y),(g2x,g2y),…,(gmx,gmy)}為網(wǎng)關(guān)候選點(diǎn)坐標(biāo)集。

定義3(節(jié)點(diǎn)覆蓋):網(wǎng)關(guān)節(jié)點(diǎn)的覆蓋范圍是以節(jié)點(diǎn)坐標(biāo)(gjx,gjy)(j=1,2,…,m)為圓心,通信半徑為R的圓。當(dāng)滿足式(1)時(shí),傳感器節(jié)點(diǎn)si被網(wǎng)關(guān)候選節(jié)點(diǎn)gj覆蓋。

(1)

在城市路邊停車場景中,無線通信被街道之間的建筑物阻擋,網(wǎng)關(guān)只能與同一條道路上的傳感器節(jié)點(diǎn)通信,不能與其他道路上的節(jié)點(diǎn)通信。但處于交叉路口附近的網(wǎng)關(guān)可以在其通信半徑內(nèi)與其他道路上的傳感器節(jié)點(diǎn)通信。如圖2所示,g10只能覆蓋Road2上的傳感器,處于交叉路口的網(wǎng)關(guān)g7能覆蓋Road1上的傳感器節(jié)點(diǎn){s11,s12}和Road2上的傳感器節(jié)點(diǎn){s13,s14,s15}。

定義4(網(wǎng)關(guān)覆蓋集合):網(wǎng)關(guān)覆蓋集合為一個(gè)網(wǎng)關(guān)gj所能覆蓋的傳感器節(jié)點(diǎn)組成的集合,標(biāo)記為Gj。如圖2中g(shù)7覆蓋的傳感器節(jié)點(diǎn)為{s11,s12,…,s15},即G7={s11,s12,…,s15},用sizeof(Gj)表示Gj中傳感器的數(shù)量,sizeof(G7)=5。

定義5:路邊停車系統(tǒng)網(wǎng)關(guān)覆蓋問題定義為T=Gateway_Deployment(S,G,R)

圖2 交叉路口網(wǎng)關(guān)的覆蓋

輸入:S={s1,s2,…,sn}為路邊停車檢測傳感器節(jié)點(diǎn)集合,G={g1,g2,…,gm}為網(wǎng)關(guān)候選點(diǎn)集合,R為網(wǎng)關(guān)與傳感器之間的通信半徑。

minisize:sizeof(T)

(2)

(3)

輸出:T={Gk}k∈K是S的一個(gè)集合覆蓋。

3 線狀部署算法

線狀部署算法(Linear Deployment,LD)是根據(jù)路邊停車檢測傳感器節(jié)點(diǎn)呈線狀分布且地理位置已知的特點(diǎn)而設(shè)計(jì)的網(wǎng)關(guān)部署方法。首先將路網(wǎng)中的傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)轉(zhuǎn)化成線性序列,然后采用按序迭代搜索策略得到網(wǎng)關(guān)覆蓋集合。

3.1 線性排序

道路上傳感器節(jié)點(diǎn)部署在每個(gè)停車位的中間位置,網(wǎng)關(guān)候選點(diǎn)為路邊基礎(chǔ)設(shè)施(例如路燈),所以傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)都具有沿道路線性分布特征。用節(jié)點(diǎn)的編號順序來反映節(jié)點(diǎn)之間的地理位置的有序性。初始時(shí),傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)是無序的,如圖3(a)所示。為了方便計(jì)算,將路網(wǎng)中的傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)分別轉(zhuǎn)換為線性序列。給每條道路都標(biāo)記一個(gè)起點(diǎn)和一個(gè)終點(diǎn)坐標(biāo),如圖3所示,Road1的起點(diǎn)和終點(diǎn)坐標(biāo)分別為C1和C2,Road2的起點(diǎn)和終點(diǎn)坐標(biāo)分別為C3和C4。

(a)未排序

(b)排序后圖3 對傳感器節(jié)點(diǎn)和網(wǎng)關(guān)侯選點(diǎn)進(jìn)行排序

采取如下步驟對節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)進(jìn)行排序:

步驟一:對Road1中的傳感器節(jié)點(diǎn)按照C1→C2的方向進(jìn)行排序,每個(gè)傳感器節(jié)點(diǎn)計(jì)算與C1點(diǎn)的歐氏距離,然后對Road1中的傳感器節(jié)點(diǎn)按距離從小到大重新編號,這樣編號的相鄰性就反映了節(jié)點(diǎn)地理位置的相鄰性。同理,可以對Road1上的網(wǎng)關(guān)候選點(diǎn)按照C1→C2的方向排序。

步驟二:對Road2中的傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)分別按照C3→C4的方向進(jìn)行排序。

步驟三:合并Road1和Road2的排序結(jié)果,將它們的序號前后相接,例如Road1中傳感器節(jié)點(diǎn)排序后的編號為s1,s2,…,si,則Road2中的第一個(gè)傳感器從si+1開始編號。這樣可以將路網(wǎng)中的傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)轉(zhuǎn)換為兩個(gè)簡單的線性序列,用編號反映節(jié)點(diǎn)之間地理位置之間的關(guān)系,排序后的結(jié)果如圖3(b)所示。對于更復(fù)雜的路網(wǎng)也可以按照同樣的方法實(shí)現(xiàn)傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)的排序。

3.2 按序迭代搜索

為了使排好序的相鄰的傳感器節(jié)點(diǎn)盡可能地被同一個(gè)網(wǎng)關(guān)覆蓋,采用按序迭代搜索策略,給定T為選擇的網(wǎng)關(guān)集合,S為傳感器節(jié)點(diǎn)集合,初始時(shí)T=?,S={s1,s2,…,sn},Gcover={G1,…,Gj,…,Gm}。搜索策略如下:

步驟一:取S中序號排在最前面的兩個(gè)傳感器節(jié)點(diǎn),標(biāo)識(shí)為sfirst,ssecond;

步驟二:搜索能同時(shí)覆蓋{sfirst,ssecond}的網(wǎng)關(guān)集合,計(jì)算網(wǎng)關(guān)的權(quán)值,如式(4)所示,如果存在多個(gè)權(quán)值大于0的網(wǎng)關(guān),則選擇權(quán)重最大的網(wǎng)關(guān)節(jié)點(diǎn)gk加入T,轉(zhuǎn)到步驟四;

步驟三:若不存在能同時(shí)覆蓋{sfirst,ssecond}的網(wǎng)關(guān),則搜索能覆蓋sfirst的網(wǎng)關(guān),選擇權(quán)重最大的網(wǎng)關(guān)節(jié)點(diǎn)gk加入T;

步驟四:將gk所覆蓋的傳感器節(jié)點(diǎn)從集合S中刪除;

步驟五:如果S不為空繼續(xù)執(zhí)行步驟一,否則退出迭代。

網(wǎng)關(guān)候選點(diǎn)gj的權(quán)重W(gj)計(jì)算如式(4):

W(gj)=wj*sizeof(Gj∩S)

(4)

其中,wj為網(wǎng)關(guān)gj的權(quán)重系數(shù),Gj∩S表示網(wǎng)關(guān)gj所覆蓋集合與S集合的交集,sizeof(Gj∩S)表示該交集中節(jié)點(diǎn)的數(shù)量,因?yàn)镾集合隨著每輪迭代而改變,所以該數(shù)量也是動(dòng)態(tài)改變的。

(5)

其中,sfirst∈Gjandssecond∈Gj表示gj能同時(shí)覆蓋{sfirst,ssecond},取系數(shù)為2;sfirst∈Gjandssecond?Gj表示gj只能覆蓋sfirst,不能覆蓋ssecond,取系數(shù)為1;否則不是合適的網(wǎng)關(guān)候選點(diǎn),所以取系數(shù)為0。

以圖4為例,LD每輪迭代的參數(shù)值如表1所示,按序迭代搜索如下:

步驟一:集合S中序號最靠前的兩個(gè)傳感器節(jié)點(diǎn)為sfirst=s1、ssecond=s2;

步驟二:搜索能同時(shí)覆蓋s1和s2的網(wǎng)關(guān),有{g1,g2,g3,g4},因此這4個(gè)網(wǎng)關(guān)的權(quán)值系數(shù)都為2,g5和g6不能覆蓋s1或s2所以權(quán)值系數(shù)都為0。因?yàn)間4處于交叉入口,既可以覆蓋Road1上的傳感器節(jié)點(diǎn)也能覆蓋Road2上的傳感器節(jié)點(diǎn)。由表1可得W(g4)最大。將g4加入T中;轉(zhuǎn)到步驟三;

步驟三:將g4所覆蓋的傳感器節(jié)點(diǎn)從集合S中刪除;

步驟四:因S不為空,則進(jìn)行第二輪迭代。

此時(shí)集合S的序號最靠前兩個(gè)傳感器節(jié)點(diǎn)為sfirst=s21、ssecond=s22,第二輪迭代中g(shù)8和g9權(quán)值最大且相等,因?yàn)間8排在g9的前面,所以選擇了g8加入T中;同理,第三輪迭代選擇了g12加入T中,將g12所覆蓋的傳感器節(jié)點(diǎn)從集合S中刪除后發(fā)現(xiàn)S為空, 全部傳感器節(jié)點(diǎn)被覆蓋,退出迭代,得到最終選擇的網(wǎng)關(guān)集合T={g4,g8,g12}。LD的偽代碼如算法1所示。

圖4 LD得到的覆蓋情況

表1 迭代參數(shù)

算法1T=Linear_Deployment(S,G,R)

輸入:S={s1,s2,…,sn}為傳感器節(jié)點(diǎn)集合

G={g1,g2,…,gm}為網(wǎng)關(guān)候選點(diǎn)集合

R為網(wǎng)關(guān)與傳感器節(jié)點(diǎn)間的通信半徑

輸出:選擇的網(wǎng)關(guān)集合T

1.對傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)進(jìn)行排序;//按3.1節(jié)描述的步驟排序

2.計(jì)算每個(gè)網(wǎng)關(guān)候選點(diǎn)對傳感器節(jié)點(diǎn)的覆蓋,得到Gcover={G1,…,Gj,…,Gm};

3.T=?;

4. whileS=?

5. 取集合S中最前面兩個(gè)節(jié)點(diǎn)分別賦值給sfirst和ssecond;

6. 計(jì)算能覆蓋sfirst的網(wǎng)關(guān)集合C(sfirst);

7. 計(jì)算能覆蓋ssecond的網(wǎng)關(guān)集合C(ssecond);

8.V=C(first)∩C(second) //V表示同時(shí)覆蓋sfirst和ssecond的網(wǎng)關(guān)集合

9. ifV≠?

10.gk={gk|gk∈V,W(gk)=max{W(gj)},gj∈V};

11. else

12.gk={gk|gk∈C(first),W(gk)=max{W(gj)},gj∈C(first)};

13. end if

14. 將gk加入T中 //gk表示選中的網(wǎng)關(guān);

15. 從S中刪除被gk覆蓋的傳感器;

16. end while

17. returnT

4 實(shí) 驗(yàn)

為了充分驗(yàn)證算法的性能,設(shè)計(jì)兩類驗(yàn)證方法:一是開展了Matlab仿真實(shí)驗(yàn);二是設(shè)計(jì)開發(fā)了可實(shí)用的網(wǎng)關(guān)部署系統(tǒng),該系統(tǒng)利用采集的路邊停車檢測傳感器節(jié)點(diǎn)坐標(biāo)和網(wǎng)關(guān)侯選點(diǎn)坐標(biāo)作為數(shù)據(jù)集,對算法的有效性進(jìn)行了驗(yàn)證。

將網(wǎng)關(guān)節(jié)點(diǎn)部署數(shù)量、覆蓋冗余度、時(shí)間復(fù)雜度作為算法性能的評價(jià)指標(biāo)。令Ns表示傳感器節(jié)點(diǎn)的數(shù)量、Nc(i)表示能覆蓋第i個(gè)傳感器節(jié)點(diǎn)的網(wǎng)關(guān)數(shù)量,則覆蓋冗余度C定義如下:

(6)

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

4.1.1 路網(wǎng)和數(shù)據(jù)集

仿真實(shí)驗(yàn)中用(i+j)×N表示路網(wǎng),(i+j)表示路網(wǎng)上有i行j列路,1列路可以把i行路分為i+1個(gè)路段,1行路可以把j列路分為j+1個(gè)路段,因此,i行j列路可分為num_segment=((i+1)*j+(j+1)*i)個(gè)路段。N為每個(gè)路段一側(cè)的傳感器節(jié)點(diǎn)數(shù)量,每條路段的兩側(cè)都布置有傳感器節(jié)點(diǎn),因此,路網(wǎng)上的傳感器節(jié)點(diǎn)數(shù)量為(2N*num_segment)。

仿真中用到的路網(wǎng)分為不含交叉路口的單道路路網(wǎng)和含交叉路口的多道路路網(wǎng)。其中(1+0)×N表示單道路路網(wǎng),(1+2)×N、(1+3)×N、(2+2)×N為3種多道路路網(wǎng)。在(1+0)×N單道路路網(wǎng)上設(shè)置N=[200,300,…,1 000],生成的傳感器節(jié)點(diǎn)數(shù)量為{200,300,…,1 000},在3種多道路路網(wǎng)上設(shè)置N=[50,100,150],(1+2)×N路網(wǎng)上生成的傳感器節(jié)點(diǎn)數(shù)量為{700,1 400,2 100},(1+3)×N路網(wǎng)上生成的傳感器節(jié)點(diǎn)數(shù)量為{1 000,2 000,3 000},(2+2)×N路網(wǎng)上生成的傳感器節(jié)點(diǎn)數(shù)量為{1 200,2 400,3 600}。

4.1.2 仿真結(jié)果分析

仿真實(shí)驗(yàn)實(shí)現(xiàn)了該文提出的線狀部署算法(LD)、樸素貪心算法[23](Naive Greedy,NG)以及分支定界法[24-25](Branch and Bound,BB)和遺傳算法[26-27](Genetic Algorithm,GA),并對這些算法的性能進(jìn)行對比。

設(shè)傳感器節(jié)點(diǎn)與網(wǎng)關(guān)候選點(diǎn)的初始通信半徑R=60 m,圖5是單道路路網(wǎng)的仿真結(jié)果,其中圖5(a)、圖5(b)和5(c)分別是網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量、覆蓋冗余度、算法運(yùn)行時(shí)間在上述4種算法下的對比結(jié)果。由圖5(a)可知,LD所需部署的網(wǎng)關(guān)節(jié)點(diǎn)個(gè)數(shù)明顯少于其他3種算法。具體為比GA、BB和NG分別減少8.4%、25.1%和44.1%。由圖5(b)可知, LD的覆蓋冗余度低于其他3種算法,具體為比GA、BB和NG分別降低3.8%、18.9%和44.4%。由圖5(c)可知,LD比其他3種算法時(shí)間復(fù)雜度更低。

圖6是多道路路網(wǎng)上的仿真結(jié)果,其中圖6(a)、圖6(b)、圖6(c)分別是網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量、覆蓋冗余度、運(yùn)行時(shí)間在4種算法下的對比結(jié)果。由圖6(a)可知,隨著傳感器規(guī)模的增大,所需部署的網(wǎng)關(guān)數(shù)量也在增加。LD的網(wǎng)關(guān)節(jié)點(diǎn)個(gè)數(shù)比GA、BB和NG分別減少5.7%、9.3%和39.9%。由圖6(b)可知,LD覆蓋冗余度低于其他3種算法,具體為比GA、BB、NG分別降低4.1%、8.4%和30.7%。由圖6(c)可以看出,傳感器節(jié)點(diǎn)的規(guī)模增加時(shí),算法運(yùn)行時(shí)間也隨著增加,并且LD比其他3種算法花費(fèi)時(shí)間更少。

由圖5和圖6分析可得,在不同路網(wǎng)和傳感器規(guī)模下,LD在網(wǎng)關(guān)節(jié)點(diǎn)數(shù)量、覆蓋冗余度和算法運(yùn)行時(shí)間上均占有一定優(yōu)勢。

圖5 單道路路網(wǎng)上的仿真結(jié)果

圖6 多道路路網(wǎng)上的仿真結(jié)果

圖7 不同半徑下四種算法所需部署的網(wǎng)關(guān)數(shù)量

設(shè)置通信半徑R分別為40 m、60 m、80 m、100 m、120 m進(jìn)行仿真,結(jié)果如圖7所示。圖7(a)為(1+0)×N單道路路網(wǎng),傳感器節(jié)點(diǎn)數(shù)量為1 000時(shí)的計(jì)算結(jié)果;圖7(b)為(1+3)×N多道路路網(wǎng),傳感器節(jié)點(diǎn)數(shù)量為2 000時(shí)的計(jì)算結(jié)果。由圖7可知擴(kuò)大網(wǎng)關(guān)的通信半徑能有效地減少網(wǎng)關(guān)的部署數(shù)量,降低部署成本。而且在不同通信半徑下LD所需部署的網(wǎng)關(guān)數(shù)量都是最少的。

圖8為4種算法在(1+2)×N路網(wǎng)上傳感器節(jié)點(diǎn)數(shù)量為1 400時(shí)的覆蓋結(jié)果。從圖中可以得出LD需要部署39個(gè)網(wǎng)關(guān),GA需要部署40個(gè)網(wǎng)關(guān),BB需要部署42個(gè)網(wǎng)關(guān),NG需要部署63個(gè)網(wǎng)關(guān)。觀察發(fā)現(xiàn)LD得出的覆蓋圖中存在較少的重疊區(qū)域,LD比其他3種算法的覆蓋冗余度更低。

圖8 多道路路網(wǎng)上數(shù)據(jù)集為1 000時(shí)4種算法的覆蓋結(jié)果

4.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

基于百度地圖設(shè)計(jì)了路邊停車網(wǎng)關(guān)部署軟件系統(tǒng)。已采集了佛山市容桂區(qū)路邊停車位及附近路燈的坐標(biāo)數(shù)據(jù),將停車位坐標(biāo)和網(wǎng)關(guān)候選點(diǎn)坐標(biāo)(路燈坐標(biāo))上傳到系統(tǒng)中,該系統(tǒng)經(jīng)算法計(jì)算得到最終的網(wǎng)關(guān)節(jié)點(diǎn)部署數(shù)量和對應(yīng)的候選點(diǎn)坐標(biāo)。當(dāng)網(wǎng)關(guān)通信半徑R=60 m時(shí),LD在不同規(guī)模傳感器節(jié)點(diǎn)的覆蓋效果如圖9所示。圖9中圓點(diǎn)標(biāo)記的是停車位,圓圈標(biāo)記的是網(wǎng)關(guān)的覆蓋結(jié)果。圖9(a)為兩條道路,228個(gè)傳感器節(jié)點(diǎn)的覆蓋,需要部署6個(gè)網(wǎng)關(guān);圖9(b)為4條道路,354個(gè)節(jié)點(diǎn)的覆蓋,需要部署9個(gè)網(wǎng)關(guān);圖9(c)為6條道路,484個(gè)傳感器節(jié)點(diǎn)的覆蓋,需要部署12個(gè)網(wǎng)關(guān)。

網(wǎng)關(guān)部署軟件系統(tǒng)實(shí)現(xiàn)了提出的LD及NG對比驗(yàn)證。隨著傳感器規(guī)模的增加,所需部署的網(wǎng)關(guān)數(shù)量也在增加,LD比NG在網(wǎng)關(guān)部署數(shù)量上減少46.0%,覆蓋冗余度上減少53.4%。

由網(wǎng)關(guān)部署軟件系統(tǒng)驗(yàn)證的結(jié)果可得,LD在網(wǎng)關(guān)部署數(shù)量和覆蓋冗余度上均占有一定優(yōu)勢,具有較好的覆蓋效果,具有更好的實(shí)用性。

圖9 LD對不同規(guī)模傳感器節(jié)點(diǎn)的覆蓋效果

5 結(jié)束語

該文研究了路邊停車檢測物聯(lián)網(wǎng)系統(tǒng)網(wǎng)關(guān)部署問題,將該問題轉(zhuǎn)化為集合覆蓋問題求解。針對停車檢測物聯(lián)網(wǎng)系統(tǒng)中傳感器節(jié)點(diǎn)線狀分布且地理位置已知的特點(diǎn),提出了線狀部署算法,通過最小化網(wǎng)關(guān)節(jié)點(diǎn)部署數(shù)量降低部署成本。將傳感器節(jié)點(diǎn)和網(wǎng)關(guān)候選點(diǎn)轉(zhuǎn)化為線性序列,按序迭代搜索最小網(wǎng)關(guān)集合。實(shí)驗(yàn)結(jié)果表明,該算法能以較小的時(shí)間復(fù)雜度獲得較好的覆蓋效果,具有更好的實(shí)用性。