基于GPS軌跡數(shù)據(jù)的RSU部署方案

馮慧芳,吳青文

(西北師范大學 數(shù)學與統(tǒng)計學院,蘭州 730070)

0 概述

車載自組網(wǎng)絡(luò)(Vehicle Ad-hoc Network,VANET)是一種特殊的移動自組網(wǎng)絡(luò)(Mobile Ad-hoc Network,MANET),在智能交通系統(tǒng)中具有重要的應(yīng)用。VANET能夠提供較大范圍的交通預警、車輛協(xié)同安全駕駛、交通智能調(diào)度和增值服務(wù)等。由于其在社會和經(jīng)濟方面的巨大價值,已成為學術(shù)界、工業(yè)界和各國職能部門的研究熱點[1-2]。

在VANET中車輛間的通信模式主要有2種:一種是車輛與車輛之間建立的通信,簡稱V2V通信;另一種是車輛與路邊單元(Road Side Unit,RSU)之間建立的通信,簡稱為V2I通信。一方面,由于車輛的高速移動使得VANET的網(wǎng)絡(luò)拓撲結(jié)構(gòu)動態(tài)變化,導致了網(wǎng)絡(luò)中移動車輛之間的通信鏈路時斷時續(xù);另一方面,VANET中大尺度和小尺度的無線信道衰落對信道質(zhì)量影響很大,信道質(zhì)量不穩(wěn)定。這些因素導致VANET存在嚴重的網(wǎng)絡(luò)分割問題,使得V2V交流具有明顯的隨機性、不穩(wěn)定性。因此,V2I通信對提升網(wǎng)絡(luò)連通性具有更重要的影響[3]。由于部署大量的RSU來獲得更好的網(wǎng)絡(luò)通信能力會帶來極大的設(shè)施成本,因此如何結(jié)合城市路網(wǎng)拓撲結(jié)構(gòu)和車輛移動規(guī)律優(yōu)化部署RSU具有重要的研究意義。

本文為此設(shè)計了一個RSU綜合部署方案,同時考慮城市路網(wǎng)拓撲結(jié)構(gòu)和車輛移動規(guī)律,并對仿真結(jié)果進行分析。

1 相關(guān)工作

近年來,國內(nèi)外學者對RSU部署問題進行了廣泛研究,主要包括基于城市車輛密度、熱點檢測、路網(wǎng)幾何特性等的部署策略。文獻[4]提出了一種基于車輛密度的D-RSU部署方案,旨在以最低的部署成本在智能交通系統(tǒng)中實現(xiàn)安全預警。文獻[5]采用I-MCL聚類算法,以十字路口為RSU預部署位置,檢測覆蓋價值更高的十字路口,但覆蓋范圍僅限于十字路口而忽略了其他的區(qū)域。文獻[6]引入α-DBSCAN熱點檢測算法確定路網(wǎng)中最有覆蓋價值的區(qū)域,提出了基于路網(wǎng)的幾何特征、車輛的移動模式和資源限制的一種RSU稀疏覆蓋方案——GeoCover。文獻[7]研究了基于路網(wǎng)幾何特性的真實城市環(huán)境下RSU部署問題,提出綜合考慮中心性和均勻性的RSU部署算法,并通過仿真實驗結(jié)果表明,其部署方案可以有效優(yōu)化網(wǎng)絡(luò)性能。文獻[8]提出了成本預算有限時,最大化時空覆蓋的RSU部署算法,該算法是NP(Non-deter-ministic Polynomial)難度問題,作者給出了一種復雜度較低的求解方法。

RSU的部署策略不僅要考慮部署成本,還要考慮網(wǎng)絡(luò)的服務(wù)質(zhì)量 (Quality of Service,QoS)、能源節(jié)約等條件。文獻[9]提出了一種城市環(huán)境下基于圖模型的RSU優(yōu)化部署方案,該方案以QoS為優(yōu)化約束條件,通過解決Steiner樹問題尋找RSU的最佳部署位置。文獻[10]提出了以數(shù)據(jù)包延遲時間和丟包率作為評價指標的基于Voronoi圖的RSU動態(tài)資源管理方案。文獻[11]提出了一種利用膨脹染色算法對RSU候選位置進行劃分,利用劃分結(jié)果建立節(jié)點與RSU的連通概率模型,進一步確定RSU的部署位置。文獻[12]通過解決網(wǎng)絡(luò)瞬像調(diào)度問題和網(wǎng)絡(luò)瞬像選取問題,進一步研究了RSU在指定時段的最優(yōu)調(diào)度方案,以確保RSU系統(tǒng)消耗的能量最少,同時又能保證整個網(wǎng)絡(luò)的連通性。文獻[13]提出了考慮RSU成本的同時考慮QoS的多目標優(yōu)化算法,仿真實驗表明該算法性能優(yōu)于傳統(tǒng)的背包算法和PageRank算法,但是求解多目標優(yōu)化算法所采用的遺傳算法對初始種群的依賴較強,交叉率和變異率等參數(shù)的選擇影響結(jié)果的可靠性。另外,算法復雜度高,適合小規(guī)模數(shù)據(jù),對維數(shù)較高的問題,還是很難處理和優(yōu)化的,因此,不適合在真實城市場景中基于交通大數(shù)據(jù)的RSU部署。

在城市VAENT中,RSU的部署不僅僅要考慮城市路網(wǎng)拓撲結(jié)構(gòu),而且還要考慮車輛移動規(guī)律。因此,本文研究如何結(jié)合城市路網(wǎng)拓撲結(jié)構(gòu)和真實車輛移動規(guī)律對適量的RSU 進行優(yōu)化部署,并通過蘭州市的真實車載GPS軌跡數(shù)據(jù),對提出的部署方案進行詳細分析和仿真。

2 基于區(qū)域連通性的RSU部署方法

2.1 城區(qū)網(wǎng)格劃分

為考慮城市中交通流量的分布特征,采用網(wǎng)格劃分方法,結(jié)合目標城市經(jīng)緯度和真實GPS數(shù)據(jù)的經(jīng)緯度的范圍劃分網(wǎng)格單元。記區(qū)域范圍為:

D=[xmin,xmax,ymin,ymax]

其中,xmin和xmax分別表示區(qū)域經(jīng)度的最大值和最小值,ymin和ymax為區(qū)域緯度的最大值和最小值。D的網(wǎng)格劃分為:

D= {Aij|?rx,ry,0≤i

0≤j

其中,rx和ry分別為劃分網(wǎng)格的經(jīng)度和緯度的粒度。

以蘭州市城關(guān)區(qū)國芳百盛附近區(qū)域作為研究對象,將該路網(wǎng)拓撲劃分為rx×ry的單元格,若假設(shè)一個RSU可以覆蓋一個單元格,則有rx=ry。圖1為該區(qū)域的路網(wǎng)拓撲和網(wǎng)格劃分。為了便于后續(xù)建模,將劃分的網(wǎng)格Aij重新進行編號:按列從左到右、按行從下到上編號,得到新的網(wǎng)格編號i,i=1,2,…,mn。根據(jù)圖1,將圖中每個單元格看作一個節(jié)點,若單元格相鄰則對應(yīng)節(jié)點間產(chǎn)生一條邊,相鄰單元格之間的連通性指標為每條邊上的權(quán)重,構(gòu)建一個無向加權(quán)復雜網(wǎng)絡(luò)模型,如圖2所示。記復雜網(wǎng)絡(luò)為G=(V,E,W),其中,V為節(jié)點集,E為邊集,W為每條邊對應(yīng)的權(quán)重的集合。

圖1 國芳百盛附近的路網(wǎng)拓撲和網(wǎng)格劃分

圖2 復雜網(wǎng)絡(luò)模型

2.2 網(wǎng)絡(luò)連通性評價

網(wǎng)絡(luò)連通性對整個網(wǎng)絡(luò)中移動節(jié)點間的信息傳遞有著重要影響,是對網(wǎng)絡(luò)性能評價的重要指標。

圖3 區(qū)域Ii與相鄰區(qū)域間的交通流轉(zhuǎn)移

定義1(相鄰區(qū)域車輛轉(zhuǎn)移概率) 在路網(wǎng)拓撲中,將某單元格Ii向相鄰單元格Ni,j轉(zhuǎn)移車輛的概率pi,j定義為相鄰區(qū)域間車輛轉(zhuǎn)移概率,即:

pi,j=Mi,j/Mi

(1)

其中,Mi,j為單元格Ii向相鄰單元格Ni,j轉(zhuǎn)移的車輛數(shù),Mi為單元格Ii處總的車輛數(shù)。

定義2(區(qū)域車輛密度) 區(qū)域車輛密度Di定義為某單元格內(nèi)車輛數(shù)占所有單元格中最大車輛數(shù)的比例,即:

Di=Mi/Mmax

(2)

定義3(相鄰區(qū)域之間的連通性) 相鄰區(qū)域之間的連通性Ci,j定義為相鄰單元格車輛轉(zhuǎn)移概率與該單元格車輛密度的乘積,即:

Ci,j=pi,j×Di

(3)

定義4(連通性閾值) 將連通性的閾值α定義為連通性期望值與標準差的差,即:

α=μ-σ

(4)

其中,μ為連通性序列{Ci,j+Cj,i}的期望值,σ為其標準差。

2.3 基于區(qū)域連通性的RSU部署算法

在圖2中相鄰單元格間的中心位置視為RSU的預部署位置,定義區(qū)域總連通性CI,J=Ci,j+Cj,i,若CI,J<α,則認為區(qū)域Ii與Ij的連通性較差,需要部署RSU。

3 基于熱點區(qū)域的RSU部署

車輛節(jié)點在地理空間中呈現(xiàn)強烈的不均勻分布。一方面,網(wǎng)絡(luò)中存在大量的節(jié)點稀疏區(qū)域,在節(jié)點稀疏區(qū)域,基于連通性的部署方案可有效提高網(wǎng)絡(luò)通信能力。另一方面,網(wǎng)絡(luò)中存在車輛高密度的“熱點”區(qū)域,在這類區(qū)域內(nèi)網(wǎng)絡(luò)連通性較強,節(jié)點間的多跳鏈路較為穩(wěn)定,即使不部署RSU,V2V通信也具有較好的連通性能和數(shù)據(jù)分發(fā)性能。但是,由于信道冗余和數(shù)據(jù)通信量大,容易造成車輛節(jié)點負荷過重,導致網(wǎng)絡(luò)性能急劇下降。因此,在熱點區(qū)域合理部署RSU可以實現(xiàn)網(wǎng)絡(luò)負載平衡。

馬爾科夫聚類算法(Markov Cluster Algorithm,MCL)是用于圖形聚類的算法[14],已成功應(yīng)用于生物信息學等領(lǐng)域。該算法是基于圖的轉(zhuǎn)移矩陣進行聚類,不需預先設(shè)定聚類數(shù)目,通過模擬網(wǎng)絡(luò)流對網(wǎng)絡(luò)進行聚類,尤其對稀疏網(wǎng)絡(luò)非常有效。

算法1馬爾科夫聚類算法

輸入C,e(i),r(i)

輸出Clusters

1.Column normalization C

2.for k=1 to ∞

3.{T2k=Expek(T2k-1);

4.T2k+1=Γrk(T2k);

5.if (T2k+1is (near-) idempotent)

then break;}

6.Interpret T2k+1as Clusters

7.return Clusters

MCL聚類結(jié)果最終得到的簇頭,即為熱點區(qū)域,也就是RSU部署位置。

4 性能評價與分析

4.1 數(shù)據(jù)集及數(shù)據(jù)處理

本文采用的數(shù)據(jù)為2017年3月6日-2017年3月12日蘭州市3 000輛出租車GPS軌跡數(shù)據(jù),數(shù)據(jù)包括車輛ID、經(jīng)度、緯度、瞬時速度、記錄時間、車頭朝向以及車輛載客信息。軌跡點采樣時間間隔為30 s,數(shù)據(jù)集大小約10.6 GB。對GPS軌跡預處理步驟如下:1)通過MNTG(Minnesota Traffic Generator)[15]獲取蘭州市路網(wǎng)拓撲信息;2)將采集到的GPS位置點匹配到路網(wǎng)拓撲上,剔除異常值;3)對兩個時間連續(xù)的采集位置之間缺失的路徑進行規(guī)劃,計算出租車可能行駛路線;4)沿規(guī)劃后的路徑進行線性插值,獲得時間粒度為30 s的出租車GPS軌跡。

4.2 基于區(qū)域連通性的RSU部署

對出租車GPS樣本數(shù)據(jù)分析得到連通性期望值μ=0.313 4,連通性閾值α=0.132 7。根據(jù)基于區(qū)域連通性的RSU部署算法,表1列出了連通性較差的區(qū)域,用節(jié)點對表示。圖4為對應(yīng)到路網(wǎng)拓撲上的RSU的部署位置。

表1 連通性較差的RSU部署位置

圖4 基于連通性的RSU部署位置

由圖1和圖4可知,該區(qū)域上半部分路網(wǎng)較為稀疏,且連通性較差的區(qū)域主要分布在該區(qū)域上側(cè),這是由于該區(qū)域上半部分對應(yīng)的區(qū)域為北濱河東路和南濱河東路。一般來說,出租車都在市區(qū)內(nèi)行駛,除非堵車或者客人路途較遠且走濱河路比較劃算,才會從南、北濱河東路行駛,故該區(qū)域上半部分連通性較差與事實相符。另外,24號節(jié)點對應(yīng)的區(qū)域為甘肅畫院和雁灘花園,早高峰時期目的地為該區(qū)域的車輛并不多,故24號節(jié)點與18、23、30號節(jié)點之間連通性不強,因此需要部署RSU。

4.3 基于熱點和區(qū)域連通性的RSU綜合部署

應(yīng)用基于MCL的熱點檢測算法,得到該城區(qū)的熱點區(qū)域,這些熱點區(qū)域編號分別為7、8、17、22、28、30和34。由圖1可知,17號節(jié)點對應(yīng)的區(qū)域路網(wǎng)較為密集,且緊鄰東方紅廣場,7號節(jié)點對應(yīng)西北民族大學,且緊鄰蘭州市衛(wèi)生學校,人流量較大,出租車數(shù)量較多,該區(qū)域為熱點區(qū)域,這與熱點檢測結(jié)果較為一致。

結(jié)合基于區(qū)域連通性的RSU部署算法,給出一種綜合部署方案:根據(jù)聚簇大小按照從大到小排序得到熱點排序;若聚簇大小相同,根據(jù)區(qū)域密度進行排序得到熱點降序排列。受部署成本限制,故不在所有的熱點區(qū)域都部署RSU,一般選前top-k的熱點進行部署。本文選擇top-3的RSU部署區(qū)域分別為17、22、7號節(jié)點,結(jié)合基于區(qū)域連通性的RSU部署,最終得到的總的部署位置如圖5所示。

圖5 RSU綜合部署位置

如果不計成本,在劃分為網(wǎng)格的城區(qū),預先部署基于覆蓋的RSU,如圖4所示,圖中沒有編號的圓圈代表了預部署的RSU。那么本文提出的綜合部署方案就可以變?yōu)镽SU調(diào)度方案,可以根據(jù)城市實時交通流,在熱點區(qū)域啟動RSU模式開關(guān)的最優(yōu)調(diào)度,使得網(wǎng)絡(luò)中的車輛在任意時刻都可以通過RSU保持連通,并且在該時間段內(nèi)RSU消耗的總能量最小化。因此,要根據(jù)城市具體的情況,研究VANET中RSU的部署問題或調(diào)度問題。對西部城市蘭州市來說,經(jīng)濟欠發(fā)達,不可能在整個城區(qū)部署基于覆蓋的RSU,故研究RSU的部署方案更切實際。

4.4 性能評價

本文根據(jù)路網(wǎng)拓撲和交通流量建立了無向加權(quán)復雜網(wǎng)絡(luò)模型,網(wǎng)絡(luò)中任意節(jié)點對之間通過單跳或多跳連通,由于選擇路徑的不同,兩節(jié)點間多條路徑上邊權(quán)重和也是不同的。邊權(quán)重越大,節(jié)點間的連通性越好。通過計算尋找節(jié)點對之間權(quán)重和最小的路徑,即找到節(jié)點對之間連通性最薄弱的路徑。

(5)

其中,CI,JMIN為區(qū)域Ii與Ni,j的連通性最薄弱路徑下的權(quán)重和,N為網(wǎng)絡(luò)節(jié)點數(shù)。那么,平均最低連通性越大,則整個網(wǎng)絡(luò)連通性越好。

表2列出未進行部署、基于區(qū)域連通性的部署、基于熱點區(qū)域的部署及綜合部署4種方案下網(wǎng)絡(luò)的平均最低連通性。

表2 不同部署方案下的網(wǎng)絡(luò)平均最低連通性

從表2可以看出,部署RSU之后,網(wǎng)絡(luò)連通性都得到了提高,基于熱點區(qū)域的RSU部署方案的連通性比基于區(qū)域連通性的部署方案的連通性差,兼顧區(qū)域連通性和熱點的綜合部署方案更優(yōu)。

5 結(jié)束語

本文基于真實出租車GPS軌跡數(shù)據(jù)提出一種基于城市環(huán)境的RSU部署方案。部署分2次進行:第1次部署考慮了城市環(huán)境下連通性較差的區(qū)域,以保證整個城市交通網(wǎng)絡(luò)的連通性;第2次部署考慮了交通壓力較大的熱點區(qū)域,幫助緩解熱點區(qū)域信息冗余問題。研究結(jié)果表明,與基于區(qū)域連通性和基于熱點的部署方案相比,兼顧區(qū)域連通性和熱點區(qū)域的綜合部署方案更優(yōu)。因此,通過合理部署RSU,不僅節(jié)約了部署成本,而且極大地提高了城市VANET的性能。下一步將通過實際部署案例檢查部署方法的有效性。