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

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

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

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

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

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

1 高速公路環(huán)境分析

1.1 高速公路特征分析

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

1.2 車輛特性分析

1.2.1 車流分析

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

(1)

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

N=Lλ

(2)

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

f(x)=λe-λx

(3)

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

(4)

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

(5)

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

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

(6)

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

1.2.2 車輛簇分析

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

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

(7)

當(dāng)x

(8)

車輛簇長度期望值為

(9)

當(dāng)x>Rv時,車輛間隔的期望值為

(10)

1.3 網(wǎng)絡(luò)性能指標(biāo)

1.3.1 網(wǎng)絡(luò)剩余能量

網(wǎng)絡(luò)節(jié)點在收發(fā)數(shù)據(jù)時需要消耗能量,當(dāng)網(wǎng)絡(luò)運(yùn)行時間相同時,如果網(wǎng)絡(luò)剩余能量越多,說明網(wǎng)絡(luò)耗能越低,網(wǎng)絡(luò)性能越好。

1.3.2 存活節(jié)點數(shù)

網(wǎng)絡(luò)生命周期與網(wǎng)絡(luò)能量損耗有關(guān),也與網(wǎng)絡(luò)節(jié)點分布情況有關(guān),如果聚類效果不好,節(jié)點耗能不均衡,可能導(dǎo)致部分節(jié)點失效。因此,網(wǎng)絡(luò)運(yùn)行時間相同時,存活節(jié)點數(shù)越多,說明網(wǎng)絡(luò)耗能越均衡,網(wǎng)絡(luò)生命周期越長。

1.3.3 端到端時延

端到端時延是移動自組網(wǎng)中經(jīng)常采用的一個網(wǎng)絡(luò)性能度量參數(shù),它指的是網(wǎng)絡(luò)中應(yīng)用層各節(jié)點平均的端到端時延。假設(shè)一組數(shù)據(jù)Pi,離開發(fā)送節(jié)點的時間為Tsi,到達(dá)接收節(jié)點的時間為Tri,則該組數(shù)據(jù)端到端時延為D=Tri-Tsi,平均端到端時延為

(11)

1.3.4 連通率

網(wǎng)絡(luò)連通率定義為高速公路路段內(nèi)所有車輛均位于RSU通信范圍內(nèi)的概率。假設(shè)路段上有N輛車,M個車輛簇,則該路段上車輛連通率為

(12)

式(12)中：N=λL。

2 車輛聚類算法原理

2.1 經(jīng)典K-means聚類算法原理

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

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

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

(13)

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

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

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

(14)

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

Step 5判斷準(zhǔn)則函數(shù)是否收斂或者是否達(dá)到設(shè)定的最大迭代次數(shù),如果是,結(jié)束。否則返回Step 2,直至聚類結(jié)束。

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

2.2 改進(jìn)K-means聚類算法原理

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

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

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

di

(15)

2.2.2 考慮簇頭與RSU節(jié)點間的通信能量確定簇頭數(shù)個數(shù)

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

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

(16)

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

(17)

節(jié)點j接收βbit數(shù)據(jù)的能量損耗公式如下:

Erx(j)=αrxβ

(18)

改進(jìn)K-means聚類算法流程圖,如圖1所示。

圖1 改進(jìn)K-means聚類算法流程圖Fig.1 Improved K-means clustering algorithm flowchart

3 高速公路路側(cè)單元部署方案

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

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

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

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

情況2當(dāng)LRSU

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

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

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

4 仿真結(jié)果分析

4.1 仿真場景及參數(shù)設(shè)置

選擇高速公路單向四車道場景進(jìn)行仿真。采用MATLAB進(jìn)行仿真分析,道路、車輛及通信環(huán)境仿真參數(shù)設(shè)定如下：

4.1.1 道路參數(shù)設(shè)置

根據(jù)《公路工程技術(shù)標(biāo)準(zhǔn)》(JTG B01—2017),高速公路單向四車道寬度為15 m,考慮現(xiàn)實情況中,設(shè)置應(yīng)急車道及RSU安裝可能距離路沿一定距離,因此設(shè)置仿真路寬為20 m,其他詳細(xì)道路環(huán)境仿真參數(shù)如表1所示。

表1 道路環(huán)境仿真參數(shù)

4.1.2 車輛參數(shù)設(shè)置

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

表2 車輛仿真參數(shù)

4.1.3 通信環(huán)境參數(shù)設(shè)置

采用IEEE 802.11p 通信協(xié)議,IEEE 802.11p是專門針對智能交通中高速運(yùn)動的車車之間以及車路之間的通信而制定的通信標(biāo)準(zhǔn)。詳細(xì)通信環(huán)境參數(shù)設(shè)置見表3所示。

4.2 改進(jìn)K-means聚類算法有效性分析

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

表3 通信環(huán)境參數(shù)設(shè)置

圖3 車輛節(jié)點分布Fig.3 Vehicle node distribution

4.2.1 簇頭數(shù)與能量損耗關(guān)系

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

4.2.2 網(wǎng)絡(luò)剩余能量

圖5為網(wǎng)絡(luò)剩余能量與周期數(shù)的關(guān)系，可知,當(dāng)周期數(shù)相同時,采用改進(jìn)K-means聚類算法的聚類網(wǎng)絡(luò)剩余能量更多,說明改進(jìn)后的聚類網(wǎng)絡(luò)節(jié)點分布更合理,并且經(jīng)典K-means聚類算法耗能更快,當(dāng)周期數(shù)大于200時,網(wǎng)絡(luò)耗能穩(wěn)定。

4.2.3 存活節(jié)點數(shù)

圖6為網(wǎng)絡(luò)存活節(jié)點數(shù)與周期數(shù)的關(guān)系，可以看出與經(jīng)典K-means算法相比,當(dāng)周期數(shù)相同時,基于改進(jìn)K-means聚類算法的聚類網(wǎng)絡(luò)中存活節(jié)點數(shù)更多,且經(jīng)典K-means聚類算法節(jié)點死亡更快,說明基于改進(jìn)K-means聚類算法的簇內(nèi)節(jié)點分布更均衡。

圖4 能量損耗與簇頭數(shù)的關(guān)系Fig.4 Relationship between energy loss and cluster heads

圖5 網(wǎng)絡(luò)剩余能量與周期數(shù)的關(guān)系Fig.5 Relationship between network residual energy and cycles

圖6 網(wǎng)絡(luò)存活節(jié)點數(shù)與周期數(shù)Fig.6 Relationship between number of nodes alive and cycles

4.2.4 端到端時延

端到端時延為RSU到簇頭以及簇頭到簇內(nèi)所有節(jié)點信息傳輸?shù)目倳r延。相同車流密度下,端到端時延越小,說明聚類越合理,網(wǎng)絡(luò)通信效率越高。圖7為20 個車輛節(jié)點與1個RSU通信構(gòu)成車路通信網(wǎng)絡(luò),網(wǎng)絡(luò)運(yùn)行周期數(shù)為500 次后,得到的平均端到端時延。由圖7可知,相同車輛密度情況下,基于改進(jìn)K-means聚類算法的網(wǎng)絡(luò)端到端時延更小,且隨著車輛密度增大,改進(jìn)K-means聚類算法優(yōu)勢更明顯。

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

綜上所述,改進(jìn)K-means聚類算法比經(jīng)典K-means 聚類算法更適用于稀疏高速公路場景的車路協(xié)同網(wǎng)絡(luò),網(wǎng)絡(luò)耗能更低,端到端時延更小,網(wǎng)絡(luò)生命周期更長。

4.3 高速公路路側(cè)單元部署分析

基于上述提出的改進(jìn)K-means車輛聚類方法以及4.1節(jié)設(shè)置的仿真環(huán)境,研究RSU部署。

4.3.1 車輛密度與車輛連通率的關(guān)系

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

圖8 車輛密度和網(wǎng)絡(luò)連通率關(guān)系Fig.8 Relationship between vehicle density and vehicle connectivity

4.3.2 車輛密度與平均車輛簇長度關(guān)系

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

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

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

5 結(jié)論

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