基于GPS軌跡數據的RSU部署方案

馮慧芳,吳青文

(西北師范大學 數學與統計學院,蘭州 730070)

0 概述

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

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

本文為此設計了一個RSU綜合部署方案,同時考慮城市路網拓撲結構和車輛移動規律,并對仿真結果進行分析。

1 相關工作

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

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

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

2 基于區域連通性的RSU部署方法

2.1 城區網格劃分

為考慮城市中交通流量的分布特征,采用網格劃分方法,結合目標城市經緯度和真實GPS數據的經緯度的范圍劃分網格單元。記區域范圍為:

D=[xmin,xmax,ymin,ymax]

其中,xmin和xmax分別表示區域經度的最大值和最小值,ymin和ymax為區域緯度的最大值和最小值。D的網格劃分為:

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

0≤j

其中,rx和ry分別為劃分網格的經度和緯度的粒度。

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

圖1 國芳百盛附近的路網拓撲和網格劃分

圖2 復雜網絡模型

2.2 網絡連通性評價

網絡連通性對整個網絡中移動節點間的信息傳遞有著重要影響,是對網絡性能評價的重要指標。

圖3 區域Ii與相鄰區域間的交通流轉移

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

pi,j=Mi,j/Mi

(1)

其中,Mi,j為單元格Ii向相鄰單元格Ni,j轉移的車輛數,Mi為單元格Ii處總的車輛數。

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

Di=Mi/Mmax

(2)

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

Ci,j=pi,j×Di

(3)

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

α=μ-σ

(4)

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

2.3 基于區域連通性的RSU部署算法

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

3 基于熱點區域的RSU部署

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

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

算法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聚類結果最終得到的簇頭,即為熱點區域,也就是RSU部署位置。

4 性能評價與分析

4.1 數據集及數據處理

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

4.2 基于區域連通性的RSU部署

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

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

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

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

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

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

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

圖5 RSU綜合部署位置

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

4.4 性能評價

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

(5)

其中,CI,JMIN為區域Ii與Ni,j的連通性最薄弱路徑下的權重和,N為網絡節點數。那么,平均最低連通性越大,則整個網絡連通性越好。

表2列出未進行部署、基于區域連通性的部署、基于熱點區域的部署及綜合部署4種方案下網絡的平均最低連通性。

表2 不同部署方案下的網絡平均最低連通性

從表2可以看出,部署RSU之后,網絡連通性都得到了提高,基于熱點區域的RSU部署方案的連通性比基于區域連通性的部署方案的連通性差,兼顧區域連通性和熱點的綜合部署方案更優。

5 結束語

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