基于車輛簇的高速公路路側單元部署研究

葛家麗，呂文紅，付守艷，屈衍璽

(山東科技大學交通學院,青島 266590)

路側單元(road side unit,RSU)是車輛自組織網絡(vehicular ad-hoc network,VANET)中必不可少的組成部分。RSU的主要功能是與車輛信息交互,為駕駛決策提供信息支持。隨著智能交通系統(intelligent traffic system,ITS)的發展,RSU研究受到越來越廣泛的關注,除了RSU功能外,RSU部署也成為研究熱點。從部署場景角度,可以分為城市環境和高速公路環境。從性能需求角度,可分為最小成本部署、最大覆蓋率部署、最短通信時延部署、最大吞吐量部署以及最高連通性部署等,目標是確定RSU部署位置、部署數量和部署間隔等。從分析影響因素角度,可分為考慮行車軌跡、通信方式和車輛簇特性等一種或幾種影響因素。考慮車輛簇特性可以有效降低RSU部署成本,保障信息傳遞安全性和時效性。現有的車輛聚類方法有基于網絡拓撲,基于道路環境,基于車流特性和基于聚類算法等。

Kim等[1]考慮了城市VANET下,基于靜態位置、移動但不可控車輛和移動且完全可控車輛三種不同部署方法的組合部署策略,首先將城市地圖抽象成網格圖,將部署問題轉化為帶有基數約束的預算最大覆蓋問題(BMCP-CC),通過多項式時間近似算法求解,并與單一部署策略相比,該算法覆蓋范圍更大,部署成本更小。Silva等[2]提出一種基于部分移動信息的RSU部署算法(PMCP-b),首先將道路劃分成相同大小的城市單元,通過相鄰單元之間的遷移率來推斷RSU的最優位置,并與不考慮車輛移動信息的部署策略(MCP-kp)和考慮全部車輛移動信息的部署策略(MCP-g)進行比較,結果表明,與MCP-kp相比,PMCP-b覆蓋率提高了6.8%,與MCP-g相比,PMCP-b覆蓋率提高了8.34%。Liu等[3]研究高速公路VANET環境中RSU部署問題,通過曲線擬合方法得到傳輸距離與連接概率簇之間的關系,推導出信息傳輸距離與時延的關系,分析最優RSU數與公路長度的關系。Wu等[4]研究高速公路多車道環境中RSU部署問題,考慮了直接通信和多跳通信兩種通信模式,提出容量最大化部署策略(CMP),與均勻分布布置和熱點布置相比,CMP部署策略需要的RSU數量少,網絡吞吐量更大。Zheng等[5]研究單向高速公路上單向出入口的雙向連接問題,考慮車輛到達率、車速以及車輛通過出入口概率等因素,提出了連通性分析模型,基于該模型分析沒有部署RSU和在出入口部署一個RSU時的網絡連通性。丁正超等[6]基于北京市路網地圖和出租車移動軌跡數據,提出一種基于連接時長的RSU部署方案,并采用二進制粒子群算法求解,通過仿真與貪心算法相比較,車輛覆蓋率和連接時長更優。奎曉燕等[7]基于北京市的車載移動數據集,提出了綜合考慮中心性和均勻性的RSU部署算法,以優化網絡整體性能,以真實車載移動軌跡為基礎的仿真實驗結果表明,所提出的RSU部署算法可以有效提升網絡性能。Ren等[8]針對城市場景提出了一種基于移動性和穩定性的聚類算法(MSCA),該算法利用了車輛移動方向,相對位置和鏈路壽命,通過更改車速和交通流量,評估MSCA算法的性能,評估結果表明,提出的算法平均簇頭壽命和平均簇數方面性能更好。Dror等[9]提出了一種用于車輛自組織網絡的分層聚類的算法(HCA),HCA算法是一種快速的隨機聚類和調度算法,處理信道訪問并調度群集內的信息傳輸,并將該算法與K-ConID聚類算法進行比較,比較結果表明,該算法形成的車輛網絡拓撲變化更穩定。Vodopivec等[10]、Bali等[11]、Cooper等[12]綜述了大量VANET聚類算法,首先從不同角度,如網絡拓撲、基礎設施要求、節點移動性、車流密度、通信模式等,分別提出不同聚類算法分類方法,然后對每類算法進行詳細描述,包括算法優缺點,現有解決方案和未來研究方向等。

本文基于經典K-means聚類算法,結合高速公路道路環境和車流特性,提出一種改進K-means聚類算法,基于該算法進行車輛聚類分析和RSU部署研究。

1 高速公路環境分析

1.1 高速公路特征分析

相比普通道路,高速公路除了具備道路基本功能外,還具備其獨特的特點,如:實行出入口控制,雙向車流分隔行駛,基礎設施、管理及服務完善,此外,高速公路的兩個最大特點是車輛高速性和低密度性。根據《中華人民共和國道路交通安全法實施條例》,高速公路車道設置明確的速度限制,最低時速為60 km/h,最高時速為120 km/h。當車速超過100 km/h時,應當與同車道的前車保持100 m以上的安全車距,車速低于100 km/h時,與同車道前車車距不得少于50 m,這也保證了正常路況下高速公路的低密度性。

1.2 車輛特性分析

1.2.1 車流分析

根據調查研究結果可知,泊松分布適用于車流密度較低、車輛之間相互影響較小,且沒有其他外界干擾因素的情況。因此,假設到達高速公路RSU附近的車輛數服從泊松分布,即在長度為L的路段上有n輛車的概率為

(1)

式(1)中：λ為車輛密度。則路段上的平均車輛節點數為

N=Lλ

(2)

由于車輛到達服從泊松分布,車輛到達的時間間隔服從指數分布。假設車輛行駛速度相同,則車輛間的距離x也服從指數分布:

f(x)=λe-λx

(3)

假設車輛通信覆蓋范圍為圓形,通信半徑為Rv,如果車輛間能夠通信,需滿足車輛間距x小于車輛通信范圍Rv,即x

(4)

則車輛間不能通信(即x>Rv)的概率為

(5)

由于車輛間的距離分布是獨立的,因此,當兩輛車的車間距大于車輛通信半徑,即x>Rv時,能夠車車通信的概率為

Ph(x>Rv)=(1-e-λRv)h

(6)

式(6)中：h為兩車之間能夠車車通信的跳數。

1.2.2 車輛簇分析

考慮車輛簇后,由于車輛簇內每個節點均可獲得簇頭廣播的信息,因此,車輛簇長度可以由簇內車輛節點距離小于車輛通信半徑的車輛間隔個數計算,則車輛簇內有n個車輛間隔的概率為

p(n)=(e-λRv)2(1-e-λRv)n

(7)

當x

(8)

車輛簇長度期望值為

(9)

當x>Rv時,車輛間隔的期望值為

(10)

1.3 網絡性能指標

1.3.1 網絡剩余能量

網絡節點在收發數據時需要消耗能量,當網絡運行時間相同時,如果網絡剩余能量越多,說明網絡耗能越低,網絡性能越好。

1.3.2 存活節點數

網絡生命周期與網絡能量損耗有關,也與網絡節點分布情況有關,如果聚類效果不好,節點耗能不均衡,可能導致部分節點失效。因此,網絡運行時間相同時,存活節點數越多,說明網絡耗能越均衡,網絡生命周期越長。

1.3.3 端到端時延

端到端時延是移動自組網中經常采用的一個網絡性能度量參數,它指的是網絡中應用層各節點平均的端到端時延。假設一組數據Pi,離開發送節點的時間為Tsi,到達接收節點的時間為Tri,則該組數據端到端時延為D=Tri-Tsi,平均端到端時延為

(11)

1.3.4 連通率

網絡連通率定義為高速公路路段內所有車輛均位于RSU通信范圍內的概率。假設路段上有N輛車,M個車輛簇,則該路段上車輛連通率為

(12)

式(12)中：N=λL。

2 車輛聚類算法原理

2.1 經典K-means聚類算法原理

在基于劃分方式的聚類算法中,K-means算法是一種最常用的聚類算法,經典K-mean算法思想如下：

Step 1初始化:從待分析的數據集中隨機選擇k個對象,作為要分成的k個簇的初始均值或聚類中心,c1,c2,…,ck。

Step 2計算距離:分別計算其余數據對象到k個聚類中心的距離。一般距離采用歐式距離計算:

(13)

式(13)中：u表示數據對象集；ci表示第i個聚類中心；m表示數據集u內有m個數據對象。

Step 3成簇:將數據對象分配到與其最近的聚類中心所在的簇中,如果數據對象到多個聚類中心的距離相等,則可劃分到其任意簇中。

Step 4更新簇頭:計算每個簇內所有數據對象的距離平均值,作為k個簇新的聚類中心,并計算準則函數值或記錄迭代次數。 一般準則函數采用平方誤差函數:

(14)

式(14)中：E表示所有數據對象的平均方差和；xi表示平均值。

Step 5判斷準則函數是否收斂或者是否達到設定的最大迭代次數,如果是,結束。否則返回Step 2,直至聚類結束。

經典K-means算法是一種無監督學習的聚類算法,其優點有算法思想簡單,運算效率高,適用于處理簇間區別較大的數據；缺點為在K-means算法中,初始聚類中心k是任意給定的,且k對結果影響較大,如果初始值選擇不合適或選取異常節點,聚類結果誤差較大。

2.2 改進K-means聚類算法原理

針對經典K-means算法存在的缺點及高速公路場景下車路通信特點,在經典K-means算法基礎上,主要從以下兩個方面進行改進。

2.2.1 考慮簇頭與RSU的距離選擇簇頭

假設某個車輛節點i到RSU的距離為di,RSU通信半徑為Ru,選擇初始簇頭和更新簇頭時,只有當車輛節點i滿足約束條件式(15)時才能作為簇頭,否則,視作簇內普通成員節點。

di

(15)

2.2.2 考慮簇頭與RSU節點間的通信能量確定簇頭數個數

RSU中消耗能量的主要模塊是無線通信模塊。根據RSU到車輛節點之間的距離不同,能量模型分別采用兩種模型,即自由空間(free space，FS)模型和多路徑衰落(multi-path fading，MP)模型,近距離采用自由空間模型,遠距離采用多路徑衰落模型。

節點間的距離與能耗成正比,根據兩個節點之間的距離是否大于設定的閾值d0來選擇模型,閾值d0由RSU通信范圍Ru和車輛通信范圍Rv確定。當兩節點間距離D(i,j)≥d0時,選擇多路徑衰落模型；當D(i,j)

(16)

式(16)中：εfs為自由空間模型的電路耗能放大系數；εmp為多路徑衰減空間模型的放大系數；αtx為傳輸能量損耗，αrx為接收能量損耗。其中,閾值d0為

(17)

節點j接收βbit數據的能量損耗公式如下:

Erx(j)=αrxβ

(18)

改進K-means聚類算法流程圖,如圖1所示。

圖1 改進K-means聚類算法流程圖Fig.1 Improved K-means clustering algorithm flowchart

3 高速公路路側單元部署方案

假設兩個Ec表示車輛簇長度，RSU之間的距離為LRSU,RSU與車輛簇之間會存在以下三種位置關系：

情況1當LRSU>Ec+2Ru時,位置關系如圖2(a)所示。

圖2 RSU與車輛簇的位置關系Fig.2 Relative location among road side unit and vehicle cluster

該部署場景下,路側單元部署間隔較大,部署數量少,成本低,但是車輛簇可能同時與路側單元A、B斷開連接,破壞網絡連通性,導致信息中斷,數據傳遞時延大幅度增加。

情況2當LRSU

該部署場景下,車輛簇始終與路側單元A、B保持連接,網絡連通性強,但需要部署大量RSU,部署成本較高。此外,同一車輛可能同時接收多個RSU信息,造成信息冗余或信號干擾等問題。

情況3當LRSU=Ec+2Ru時,位置關系如圖2(c)所示。

該部署場景下,車輛簇在行駛過程中,某一時間點內,能且只能與一個RSU保持連接。與情況1和情況2相比,情況3既能保證網絡連通性,又節省部署成本,但難點在于如何確定合適的RSU部署間隔。因此,研究基于情況3的部署場景,研究車輛簇與RSU部署間隔之間的關系。

4 仿真結果分析

4.1 仿真場景及參數設置

選擇高速公路單向四車道場景進行仿真。采用MATLAB進行仿真分析,道路、車輛及通信環境仿真參數設定如下：

4.1.1 道路參數設置

根據《公路工程技術標準》(JTG B01—2017),高速公路單向四車道寬度為15 m,考慮現實情況中,設置應急車道及RSU安裝可能距離路沿一定距離,因此設置仿真路寬為20 m,其他詳細道路環境仿真參數如表1所示。

表1 道路環境仿真參數

4.1.2 車輛參數設置

假設每輛車均具備無線通信功能,RSU通信范圍遠大于高速公路車道寬度,因此,將車輛近似看作一維的直線運動。根據1.1節分析可以得出,高速公路單向四車道車輛正常行駛狀態下,車輛數最多為70 輛,設置通信半徑R=Ru=Rv,詳細車輛參數設置見表2所示。

表2 車輛仿真參數

4.1.3 通信環境參數設置

采用IEEE 802.11p 通信協議,IEEE 802.11p是專門針對智能交通中高速運動的車車之間以及車路之間的通信而制定的通信標準。詳細通信環境參數設置見表3所示。

4.2 改進K-means聚類算法有效性分析

根據2.2節分析,高速公路車輛分布服從泊松分布,本研究采用MATLAB仿真軟件進行車輛聚類分析,根據4.1節仿真場景參數設置,在1 500 m×20 m的仿真路段區域內,以隨機生成20 個車輛節點為例,研究改進K-means聚類算法效果,車輛節點分布情況如圖3所示。其中,橫坐標是路段長度,縱坐標是路段寬度,RSU坐標為(500,0)。

表3 通信環境參數設置

圖3 車輛節點分布Fig.3 Vehicle node distribution

4.2.1 簇頭數與能量損耗關系

根據2.2節分析可知,每個簇中簇頭能量消耗最高,因此如果簇頭數量過多,網絡耗能就會提高,造成能量浪費；如果簇頭數量過少,會導致簇頭節點通信負擔重,節點易失效,網絡生命周期短等問題。圖4為20 個車輛節點時,簇頭數與能量損耗的關系，可以看出,當車輛N=20時,當k>4時,能量損耗較低。本研究取k=4時,比較經典K-means聚類算法和改進K-means聚類算法。

4.2.2 網絡剩余能量

圖5為網絡剩余能量與周期數的關系，可知,當周期數相同時,采用改進K-means聚類算法的聚類網絡剩余能量更多,說明改進后的聚類網絡節點分布更合理,并且經典K-means聚類算法耗能更快,當周期數大于200時,網絡耗能穩定。

4.2.3 存活節點數

圖6為網絡存活節點數與周期數的關系，可以看出與經典K-means算法相比,當周期數相同時,基于改進K-means聚類算法的聚類網絡中存活節點數更多,且經典K-means聚類算法節點死亡更快,說明基于改進K-means聚類算法的簇內節點分布更均衡。

圖4 能量損耗與簇頭數的關系Fig.4 Relationship between energy loss and cluster heads

圖5 網絡剩余能量與周期數的關系Fig.5 Relationship between network residual energy and cycles

圖6 網絡存活節點數與周期數Fig.6 Relationship between number of nodes alive and cycles

4.2.4 端到端時延

端到端時延為RSU到簇頭以及簇頭到簇內所有節點信息傳輸的總時延。相同車流密度下,端到端時延越小,說明聚類越合理,網絡通信效率越高。圖7為20 個車輛節點與1個RSU通信構成車路通信網絡,網絡運行周期數為500 次后,得到的平均端到端時延。由圖7可知,相同車輛密度情況下,基于改進K-means聚類算法的網絡端到端時延更小,且隨著車輛密度增大,改進K-means聚類算法優勢更明顯。

圖7 車輛密度與端到端時延的關系Fig.7 Relationship between vehicle density and end-to-end delay

綜上所述,改進K-means聚類算法比經典K-means 聚類算法更適用于稀疏高速公路場景的車路協同網絡,網絡耗能更低,端到端時延更小,網絡生命周期更長。

4.3 高速公路路側單元部署分析

基于上述提出的改進K-means車輛聚類方法以及4.1節設置的仿真環境,研究RSU部署。

4.3.1 車輛密度與車輛連通率的關系

基于MATLAB軟件,仿真1 000次,得出網絡連通率受車輛密度影響,如圖8所示。由圖8可知:①當通信半徑相同時,車輛密度越高,車輛連通率越高,當通信半徑R>400m時,低車輛密度時網絡連通率大于70%；②車輛密度相同時,通信半徑越大,網絡連通率越高,當車輛密度λ>0.04 veh/m且R>200 m時,網絡連通率均大于80%。

圖8 車輛密度和網絡連通率關系Fig.8 Relationship between vehicle density and vehicle connectivity

4.3.2 車輛密度與平均車輛簇長度關系

根據1.2節分析,仿真1 000次,得出通信半徑R與車輛簇長度之間的關系,如圖9所示。由圖9可以看出:①平均車輛簇長度隨著車輛密度的變化而變化，當車流密度相同時,通信半徑越大,平均車輛簇長度越長；②通信半徑相同時,車流密度越大,平均車輛簇長度越長,這也與實際情況相符。

圖9 車輛密度與平均車輛簇長度關系Fig.9 Relationship between vehicle density and average vehicle cluster length

根據第3節情況3可知:部署間隔為平均車輛簇長度加2個RSU通信半徑R,即LRSU=Ec+2R,因此,圖9結果可以為高速公路部署RSU提供部署間隔依據。

5 結論

針對高速公路道路環境特點和車輛特性,提出了一種基于改進K-means聚類算法的車輛聚類方法,并從網絡剩余能量、存活節點數和端到端時延三個方面與經典K-means算法進行比較,結果表明,研究提出的改進K-means聚類算法網絡耗能更小,節點聚類分布更均衡,網絡端到端時延更小。然后基于提出改進K-means聚類算法進行車輛聚類,并通過MATLAB軟件仿真,分析RSU通信半徑、車輛密度、車輛連通率、平均車輛簇長度之間的關系,從而得出RSU通信半徑和部署間隔,可以為高速公路RSU部署提供依據。