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

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

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

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

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

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

1.1 高速公路特征分析

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

1.2 車(chē)輛特性分析

1.2.1 車(chē)流分析

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

(1)

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

N=Lλ

(2)

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

f(x)=λe-λx

(3)

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

(4)

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

(5)

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

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

(6)

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

1.2.2 車(chē)輛簇分析

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

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

(7)

當(dāng)x

(8)

車(chē)輛簇長(zhǎng)度期望值為

(9)

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

(10)

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

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

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

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

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

1.3.3 端到端時(shí)延

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

(11)

1.3.4 連通率

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

(12)

式(12)中：N=λL。

2 車(chē)輛聚類(lèi)算法原理

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

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

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

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

(13)

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

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

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

(14)

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

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

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

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

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

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

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

di

(15)

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

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

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

(16)

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

(17)

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

Erx(j)=αrxβ

(18)

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

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

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

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

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

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

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

情況2當(dāng)LRSU

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

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

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

4 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 車(chē)輛節(jié)點(diǎn)分布Fig.3 Vehicle node distribution

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

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

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

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

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

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

圖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é)點(diǎn)數(shù)與周期數(shù)Fig.6 Relationship between number of nodes alive and cycles

4.2.4 端到端時(shí)延

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

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

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

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

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

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

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

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

4.3.2 車(chē)輛密度與平均車(chē)輛簇長(zhǎng)度關(guān)系

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

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

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

5 結(jié)論

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