車聯(lián)網(wǎng)中時(shí)延約束的路側(cè)單元部署方案研究

賈宗璞,楊煥煥,謝果君

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,454000,河南焦作)

車輛自組織網(wǎng)絡(luò)(VANET)存在著功能不一的交通安全類應(yīng)用、交通協(xié)調(diào)管理類應(yīng)用和娛樂(lè)類應(yīng)用,它們對(duì)智能交通系統(tǒng)(ITS)的實(shí)現(xiàn)起著重要作用。車輛感知數(shù)據(jù)的收集和分發(fā)是這些應(yīng)用的核心內(nèi)容,但由于車聯(lián)網(wǎng)中車輛移動(dòng)性高、拓?fù)渥兓l繁,單獨(dú)地車對(duì)車(V2V)通信往往效率較低,嚴(yán)重影響了車輛感知數(shù)據(jù)的獲取[1-3]。作為車聯(lián)網(wǎng)中必不可少的道路基礎(chǔ)設(shè)施單元,路側(cè)單元(RSU)可以利用車對(duì)基礎(chǔ)設(shè)施(V2I)通信降低智能車輛間的數(shù)據(jù)傳輸時(shí)延。然而,大量部署RSU不僅費(fèi)用較高[4],而且會(huì)受到候選部署點(diǎn)集合、交通特征、道路特征等諸多因素的影響[5]?，F(xiàn)有的關(guān)于RSU部署工作的研究主要是優(yōu)化數(shù)據(jù)傳輸時(shí)延、RSU覆蓋率和RSU部署費(fèi)用等,以提高網(wǎng)絡(luò)的性能。

關(guān)于數(shù)據(jù)傳輸時(shí)延的研究主要是降低RSU-RSU傳輸時(shí)延和車輛-RSU傳輸時(shí)延[6-7]。關(guān)于RSU部署費(fèi)用的研究則是降低RSU的安裝成本和維護(hù)成本[8-9]。就RSU覆蓋率的研究而言,Trullols等研究了基礎(chǔ)設(shè)施節(jié)點(diǎn)部署問(wèn)題,目標(biāo)是最大化區(qū)域內(nèi)與基礎(chǔ)設(shè)施連接的車輛數(shù)和連通時(shí)間,提出的貪婪算法和分區(qū)算法在大規(guī)模場(chǎng)景下有很好的適用性,但計(jì)算車輛覆蓋時(shí)需要獲取車輛的詳細(xì)行駛信息[10]。Li等解決了車聯(lián)網(wǎng)中預(yù)算和時(shí)延約束的RSU部署問(wèn)題,其中有線RSU(c-RSU)和無(wú)線RSU(w-RSU)兩種類型RSU的時(shí)延約束覆蓋范圍和部署代價(jià)完全不同,該問(wèn)題的目標(biāo)是在給定的預(yù)算和時(shí)延下確定RSU的最佳部署位置,最大化區(qū)域內(nèi)接收c-RSU廣播消息的車輛數(shù)[11]。Zhu等設(shè)計(jì)了c街道模型并提出基于貪心策略的近似算法,實(shí)現(xiàn)了RSU對(duì)目標(biāo)區(qū)域的最優(yōu)覆蓋,然后針對(duì)城市中地形復(fù)雜的區(qū)域,設(shè)計(jì)了Cue模型,提出基于shifting策略的近似算法,進(jìn)而有效地解決了城市場(chǎng)景下RSU的部署問(wèn)題[12]。Chi等提出了十字路口優(yōu)先級(jí)的RSU部署方案,根據(jù)車輛密度、十字路口普遍度計(jì)算路口權(quán)重值,并結(jié)合貪婪、動(dòng)態(tài)規(guī)劃和混合法確定RSU的部署數(shù)和部署位置,在確保最大連通性的同時(shí)降低RSU的部署成本[13]。

以上大多數(shù)的研究主要將傳輸時(shí)延、部署費(fèi)用等作為RSU部署的優(yōu)化目標(biāo),以覆蓋率為目標(biāo)的部署主要考慮對(duì)車輛的覆蓋,部署算法需要車輛的詳細(xì)移動(dòng)信息,這些信息不僅涉及用戶的隱私[14],而且較難獲取。因此,本文將RSU對(duì)車輛的覆蓋轉(zhuǎn)化為對(duì)區(qū)域內(nèi)劃分子路段的覆蓋,通過(guò)各路段上車輛的密度和平均速度求解路段上的數(shù)據(jù)傳輸時(shí)延,設(shè)計(jì)基于Dijkstra的0-1覆蓋矩陣求解算法,將時(shí)延約束的RSU部署問(wèn)題(DBRD)轉(zhuǎn)化為集合覆蓋問(wèn)題。提出改進(jìn)遺傳算法的RSU部署方案(IGARD),在限定RSU部署數(shù)的前提下從候選位置集中選出最佳部署位置以最大化時(shí)延內(nèi)覆蓋路段數(shù)。與傳統(tǒng)的遺傳算法相比,IGARD方案基于貪心算法的思想產(chǎn)生初始種群,新解產(chǎn)生時(shí)根據(jù)設(shè)計(jì)的交叉算子和變異算子執(zhí)行交叉和變異操作,且在執(zhí)行過(guò)程中對(duì)不滿足約束條件的潛在解進(jìn)行修復(fù)。這樣不僅可以將帶約束條件的研究問(wèn)題轉(zhuǎn)化為無(wú)約束條件問(wèn)題,避免了確定罰函數(shù)的困難,而且平衡了算法的集中搜索和多樣性搜索能力。仿真結(jié)果進(jìn)一步證實(shí)了算法的有效性。

1 系統(tǒng)模型

1.1 問(wèn)題模型

城市道路模型圖可表示為無(wú)向圖G=(V,E),V是十字路口集合,V={I1,I2,…,In}且滿足|V|=n,E是相鄰十字路口間的路段,E={E1,E2,…,Es}。設(shè)車輛和RSU的通信半徑為R,相鄰十字路口間的距離D={D1,D2,…,Ds}。對(duì)于Di∈D且Di>R的路段Ei,將其按照R的間距劃分為若干個(gè)子路段。圖1給出了n=9時(shí)的城市道路模型圖。

劃分完成后形成另一無(wú)向圖G1=(V1,E1),V1={V,M},E1={e(i,j),?i,j,i∈V1,j∈V1},M是E∈G(V,E)劃分時(shí)形成的頂點(diǎn),M={m1,m2,…,mk}且|V1|=N,|E1|=m。對(duì)eij∈E1有e(i,j)={lij,ρij,vij},lij、ρij、vij分別為路段e(i,j)的歐氏距離、車輛密度和平均速度。

圖1 城市道路模型圖

1.2 通信模型

本文的場(chǎng)景是多個(gè)RSU和多個(gè)車輛組成的網(wǎng)絡(luò),網(wǎng)絡(luò)通信場(chǎng)景如圖2所示。圖2中,虛線覆蓋的區(qū)域?yàn)镽SU的部署區(qū)域,RSU設(shè)施表示可供選擇的RSU部署候選位置,含有通信鏈路的RSU設(shè)施表示在該處部署了RSU。本文的通信模型為圓盤通信模型,任意兩個(gè)節(jié)點(diǎn)可以通信,當(dāng)且僅當(dāng)它們之間的歐氏距離小于或等于其通信半徑R。以i和j為端點(diǎn)的路段e(i,j)為例,根據(jù)文獻(xiàn)[15],其上的數(shù)據(jù)傳輸時(shí)延t(i,j)可以表示為

圖2 網(wǎng)絡(luò)通信場(chǎng)景圖

(1)

式中:thop為數(shù)據(jù)的一跳傳輸時(shí)延,thop=psize/s,psize為數(shù)據(jù)包大小,s為數(shù)據(jù)傳輸帶寬。式(1)表明,道路e(i,j)上有(1-e-Rρij)的車輛車間距離小于等于R,它們使用轉(zhuǎn)發(fā)方式傳輸數(shù)據(jù),其余的e-Rρij的車輛車間距離大于R,它們使用攜帶方式傳輸數(shù)據(jù)。另外,當(dāng)lij>R時(shí),需將e(i,j)劃分為若干子路段,此時(shí)子路段上的數(shù)據(jù)傳輸時(shí)延仍舊由式(1)計(jì)算。

1.3 DBRD問(wèn)題

RSU部署時(shí)選擇十字路口為候選位置[10]。本文目標(biāo)是在n個(gè)候選位置中部署r個(gè)RSU,使時(shí)延τ內(nèi)將數(shù)據(jù)傳輸至RSU的子路段總數(shù)最多。設(shè)e(i,j)上車輛將數(shù)據(jù)傳輸至RSU的最小時(shí)延為tj(1≤j≤m)。對(duì)任一eij∈E1,定義0-1變量xi、yj,當(dāng)tj≤τ時(shí),yj=1,否則yj=0;在Ii處部署RSU時(shí),xi=1,否則xi=0。那么,DBRD問(wèn)題可形式化為

(2)

定理1DBRD問(wèn)題是NP-hard問(wèn)題。

證明首先引入集合覆蓋問(wèn)題(SCP)[16-17]。SCP問(wèn)題表述如下:給定n個(gè)元素集合E={e1,e2,…,en},E的子集集合S={s1,s2,…,sm},求E的一個(gè)覆蓋C,使C在E的所有覆蓋中所含元素個(gè)數(shù)最少且C中元素并集為E。因?yàn)镾CP問(wèn)題是NP-hard問(wèn)題,將DBRD問(wèn)題轉(zhuǎn)化為SCP問(wèn)題后,即可證明DBRD問(wèn)題是NP-hard問(wèn)題。設(shè)在Ii處部署RSU時(shí)各子路段在τ內(nèi)將數(shù)據(jù)傳輸至RSU的集合為Si,則問(wèn)題轉(zhuǎn)化為τ限制的集合覆蓋問(wèn)題(τ-LSCP)

(3)

問(wèn)題的目標(biāo)為最大化RSU覆蓋的子路段數(shù)量,即最大化Si的并集,約束條件為RSU的部署數(shù)等于r。因此,DBRD問(wèn)題是NP-hard問(wèn)題。

1.4 數(shù)據(jù)傳輸延遲計(jì)算方法

將DBRD問(wèn)題轉(zhuǎn)化為τ-LSCP問(wèn)題后,獲取Si(1≤i≤n)是求解τ-LSCP問(wèn)題的前提。設(shè)計(jì)0-1覆蓋矩陣Tmn,當(dāng)路段e(i,j)上的車輛將數(shù)據(jù)傳輸至i處RSU的最小時(shí)延tji≤τ時(shí),Tji=1,否則Tji=0。那么,Si可表示為

(4)

因此,問(wèn)題轉(zhuǎn)化為求路段e(i,j)上車輛將數(shù)據(jù)傳輸至i處RSU時(shí)最小時(shí)延tji的值。設(shè)路段e(i,j)距離i處RSU的距離為dji,則tji為

(5)

式中:Pik∈P為路段e(i,j)上車輛將數(shù)據(jù)傳輸至i處RSU時(shí)的所有路徑;t(j,k)為數(shù)據(jù)在e(j,k)的傳輸時(shí)延。經(jīng)1.2節(jié)中式(1)求解t(j,k)后,為無(wú)向圖G1=(V1,E1)的各條邊附上相應(yīng)的權(quán)值t(j,k),G1即為無(wú)向帶權(quán)圖。此時(shí)無(wú)向帶權(quán)圖表示的道路模型如圖3所示,n=9。

圖3 無(wú)向帶權(quán)圖表示的道路模型

對(duì)tji(1≤j≤m,1≤i≤n),使用Dijkstra算法求出e(i,j)兩側(cè)端點(diǎn)到源點(diǎn)Ii的最短路徑(最小傳輸延遲)后記錄在disk[]數(shù)組中,取兩者中的較小值加上t(i,j)即可,計(jì)算方法如下式

tji=min{disk[i],disk[j]}+t(i,j)

(6)

0-1覆蓋矩陣Tmn的求解算法如下。

算法10-1覆蓋矩陣Tmn求解算法。

輸入RSU候選位置集合V={I1,I2,…,In},無(wú)向帶權(quán)圖G1=(V1,E1),傳輸延遲τ

輸出矩陣Tmn

1double dist [N];∥記錄圖中各頂點(diǎn)到源點(diǎn)Ii的最小傳輸延遲的數(shù)組

2for inti=1 ton∥遍歷RSU候選位置集合V={I1,I2,…,In}

3 Dijkstra(G1,dist,Ii);∥Dijkstra算法求出圖中各頂點(diǎn)到源點(diǎn)Ii的最小傳輸延遲

4 for intj=1 tom∥遍歷圖中所有的邊eij∈E1

5tji=min{disk[i],disk[j]}+t(i,j);∥計(jì)算所有路段到Ii處RSU的最小傳輸延遲

6 if(tji≤τ)Tji=1;

7 else if(tji>τ)Tji=0;

8 end for

9end for

定理20-1覆蓋矩陣Tmn求解算法的時(shí)間復(fù)雜度為O[n(N2+m)]。

證明RSU部署候選位置集合|V|=n,為獲取每個(gè)位置Ii對(duì)應(yīng)的Si,需要進(jìn)行n次運(yùn)算。每次運(yùn)算使用Dijkstra算法計(jì)算圖中頂點(diǎn)到源點(diǎn)Ii的最小傳輸延遲,時(shí)間復(fù)雜度為O(N2)。獲得dist [N]數(shù)組后,需要計(jì)算eij∈E1上車輛將數(shù)據(jù)傳輸至i處RSU時(shí)的最小時(shí)延tji,時(shí)間復(fù)雜度為O(m),即每次運(yùn)算時(shí)間復(fù)雜度為O(N2+m),故0-1覆蓋矩陣求解算法時(shí)間復(fù)雜度為O[n(N2+m)]。

2 改進(jìn)遺傳算法的RSU部署方案

在1.4節(jié)中,通過(guò)算法1求得0-1覆蓋矩陣后,τ-LSCP問(wèn)題可表述為:給定0-1矩陣Tmn,Tji=1表示第j行被第i列覆蓋,Tji=0則表示第j行未被第i列覆蓋。τ-LSCP問(wèn)題需要尋找包含r個(gè)列的集合D,使D中元素覆蓋的總行數(shù)最多。引入n維0-1向量X={x1,x2,…,xn},若第i列選入集合D,則xi=1,否則xi=0,因此X是τ-LSCP問(wèn)題的解。圖4給出了τ-LSCP問(wèn)題實(shí)例圖。

圖4 τ -LSCP問(wèn)題實(shí)例圖

基于此,提出了改進(jìn)遺傳算法的RSU部署方案IGARD,流程圖如圖5所示,其基本步驟如下。

步驟1使用貪心算法產(chǎn)生初始種群P={x1,x2,…,xM},設(shè)計(jì)適應(yīng)度函數(shù)f(x),計(jì)算個(gè)體的適應(yīng)度,記P中最優(yōu)解為x*,B=f(x*)。

步驟2通過(guò)以下方式產(chǎn)生新解:①?gòu)腜中任選2個(gè)解xi、xj,交叉產(chǎn)生解xs,變異得新解xz;②從P中任選一個(gè)解xi變異得新解xz。

步驟3將x*與xs比較,若找到比x*適應(yīng)度更優(yōu)的解,則更新解x*和B=f(x*)。

步驟4重復(fù)步驟2～步驟3至最大迭代次數(shù)結(jié)束。

2.1 編碼

改進(jìn)的遺傳算法中個(gè)體使用n維0-1向量進(jìn)行編碼,當(dāng)個(gè)體某一維位置取值為1時(shí),表示該維度對(duì)應(yīng)的列加入選中列集合。例如{0,1,1,0}表示將第2列和第3列加入選中列集合。

2.2 產(chǎn)生初始種群

初始種群的產(chǎn)生通過(guò)貪心算法完成,這樣可以避免過(guò)多無(wú)效解的出現(xiàn)。假設(shè)τ-LSCP問(wèn)題的解向量為xj={xj(1),xj(2),…,xj(n)},選中列集合為D,未選中列集合為M,選中列已覆蓋行集合為U,則初始種群產(chǎn)生的步驟如下。

步驟1初始化D=φ,M={1,2,…,n},xj={xj(i)}={0,…,0},1≤i≤n,U=E1。

步驟2記Si表示第i列加入D后新覆蓋的行,可用性價(jià)比Q(i)=|Si∩U|表示。

步驟3構(gòu)造候選列集合RCL={i∈M,ξQmax≤Q(i)≤Qmax}。ξ為(0,1)內(nèi)的數(shù),設(shè)置目的是平衡初始種群產(chǎn)生的隨機(jī)性和貪婪性。

步驟4從RCL中任選一列i加入D,令M=M-{i},xj(i)=1,U=U-Si。

步驟5若|D|=r,結(jié)束并輸出xj,否則轉(zhuǎn)至步驟2。

步驟6重復(fù)運(yùn)行步驟1～步驟5,直至初始種群的數(shù)量達(dá)到M,并輸出P={x1,x2,…,xM}。

圖5 IGARD方案流程圖

2.3 適應(yīng)度函數(shù)

本文適應(yīng)度函數(shù)如下

(7)

式中:Si為第i列覆蓋的行,f(x)為適應(yīng)度,表示Si并集元素?cái)?shù)。因種群初始化時(shí)已剔除無(wú)效個(gè)體,故求解問(wèn)題已轉(zhuǎn)化為無(wú)約束問(wèn)題,適應(yīng)度函數(shù)即為本文目標(biāo)函數(shù)。

2.4 選擇、交叉和變異算子

本文使用輪盤賭選擇法選擇個(gè)體,基本思想是根據(jù)個(gè)體適應(yīng)度大小進(jìn)行選擇操作。首先依據(jù)種群中個(gè)體的適應(yīng)度計(jì)算其被遺傳到下一代種群中的概率為

(8)

然后根據(jù)P(xi)計(jì)算個(gè)體的累計(jì)概率

(9)

最后在[0,1]內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)k。若k

選擇算子執(zhí)行完畢后,交叉算子從下一代種群中隨機(jī)選擇2個(gè)解xi,xj,交叉產(chǎn)生解xs。首先初始化解xs={xs(i)}={0,…,0},1≤i≤n。然后比較xi和xj,若xi(i)=xj(i)=1,令xs(i)=1,否則xs(i)=0。因?yàn)榻徊娈a(chǎn)生的解xs中選中列數(shù)小于r,因此需要使用貪心算法進(jìn)行修復(fù)。依據(jù)Q(i)=Si∩U計(jì)算出解xs中所有未選列的性價(jià)比值,重復(fù)執(zhí)行2.2節(jié)中步驟3和步驟4,直至解xs滿足|xs(i)=1|=r。

3 性能分析

本文通過(guò)仿真實(shí)驗(yàn)對(duì)IGARD方案的相關(guān)性能(路段覆蓋率和RSU平均擴(kuò)展通信范圍)與其他部署方案進(jìn)行了對(duì)比。仿真平臺(tái)為Visual Studio 2015,仿真語(yǔ)言為C++,仿真環(huán)境為城市場(chǎng)景。實(shí)驗(yàn)?zāi)J(rèn)參數(shù)見(jiàn)表1,表中c×c表示RSU部署區(qū)域包含c2個(gè)十字路口,相鄰十字路口間的路段被劃分為3個(gè)子路段,每個(gè)子路段長(zhǎng)度為R,則部署區(qū)域?yàn)?R(c-1)×3R(c-1)。

表1 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)

為了更準(zhǔn)確地模擬真實(shí)的城市環(huán)境,假設(shè)部署區(qū)域內(nèi)各子路段上的車輛密度和車輛平均速度是不均勻分布的?？拷致房谔幍淖勇范紊宪囕v密度相對(duì)較高,車輛平均速度相對(duì)較低。遠(yuǎn)離十字路口處的子路段上車輛密度相對(duì)較低,車輛平均速度相對(duì)較高。當(dāng)部署區(qū)域?yàn)?×8時(shí),區(qū)域內(nèi)包含336個(gè)子路段,此時(shí),車輛密度和平均速度的具體分布情況分別如圖6、圖7所示。

圖6 部署區(qū)域內(nèi)各子路段上車輛密度的分布圖

圖7 部署區(qū)域內(nèi)各子路段上車輛平均速度的分布圖

路段覆蓋率是衡量部署方案有效性的指標(biāo),是部署方案性能的直接體現(xiàn),表示為

(10)

式中:Rvalid是RSU的有效覆蓋路段,它等于總路段Rall減去被多個(gè)RSU重復(fù)覆蓋的路段。

RSU的平均擴(kuò)展通信范圍與路段上車輛的密度和平均速度相關(guān),通過(guò)多跳轉(zhuǎn)發(fā)RSU的直接通信范圍得到擴(kuò)大。該參數(shù)是單個(gè)RSU部署位置最優(yōu)性的體現(xiàn),可以間接反應(yīng)出RSU覆蓋區(qū)域的重復(fù)度

(11)

式中:Rvalid可由式(10)獲得;Rdirect是RSU直接覆蓋路段的總和;a是RSU部署數(shù)。

在此與RSU的熱點(diǎn)部署方案和均勻部署方案[6]、MCP-g部署方案[13]對(duì)比了路段覆蓋率和RSU的平均擴(kuò)展通信范圍。熱點(diǎn)部署方案在覆蓋路段最多的位置處部署RSU,直至部署數(shù)為r。均勻部署方案將n個(gè)RSU候選位置分為r個(gè)區(qū)域,取各區(qū)域中點(diǎn)處為RSU部署位置。MCP-g部署方案使用貪婪的啟發(fā)式算法在各候選位置處選出r個(gè)使未覆蓋路段覆蓋最多的位置。將道路模型圖轉(zhuǎn)換為無(wú)向帶權(quán)圖后計(jì)算0-1覆蓋矩陣,在其上運(yùn)行RSU部署方案進(jìn)而得到實(shí)驗(yàn)結(jié)果。

3.1 RSU部署數(shù)對(duì)性能的影響

本組實(shí)驗(yàn)主要研究RSU部署數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響。設(shè)置部署區(qū)域?yàn)?×8,數(shù)據(jù)傳輸最大時(shí)延τ=6 s。圖8和圖9分別給出了4種方案關(guān)于路段覆蓋率和RSU平均擴(kuò)展通信范圍的對(duì)比圖。

圖8 a對(duì)路段覆蓋率的影響

圖9 a對(duì)RSU平均擴(kuò)展通信范圍的影響

由圖8、圖9可知,RSU部署數(shù)增加時(shí),4種方案的路段覆蓋率都逐漸增加,RSU平均擴(kuò)展通信范圍都逐漸下降,但本文方案優(yōu)于其他3種方案。這是因?yàn)镽SU部署數(shù)的增加使更多的路段被覆蓋,提高了路段覆蓋率,但重復(fù)覆蓋路段也逐漸增加,進(jìn)而降低了RSU平均擴(kuò)展通信范圍。同時(shí)由于V2V通信的存在,RSU的平均擴(kuò)展通信范圍一定大于其直接通信范圍。MCP-g部署方案雖然考慮到了重復(fù)覆蓋的路段,但在部署過(guò)程中只考慮單個(gè)位置的覆蓋路段數(shù)會(huì)導(dǎo)致部署方案具有很大的局限性。熱點(diǎn)部署方案基于貪心算法的思想部署RSU,但未考慮重復(fù)覆蓋的路段。均勻部署方案基于分治的思想部署RSU,容易忽略部署的熱點(diǎn)位置。因此,這兩種方案的性能低于本文算法。

3.2 限定傳輸最大時(shí)延對(duì)性能的影響

本組實(shí)驗(yàn)主要研究限定傳輸最大時(shí)延對(duì)實(shí)驗(yàn)結(jié)果的影響。設(shè)置部署區(qū)域?yàn)?×8,a為15。圖10和圖11分別給出了4種方案關(guān)于路段覆蓋率和RSU平均擴(kuò)展通信范圍的對(duì)比圖。

圖10 限定傳輸最大時(shí)延對(duì)路段覆蓋率的影響

圖11 限定傳輸最大時(shí)延對(duì)RSU平均擴(kuò)展通信范圍的影響

由圖10、圖11可知,限定傳輸最大時(shí)延增加時(shí),路段覆蓋率和RSU平均擴(kuò)展通信范圍均逐漸增大,且表現(xiàn)出幾乎相同的增長(zhǎng)趨勢(shì),但本文方案優(yōu)于其他3種方案。這是因?yàn)樵诓渴饏^(qū)域和RSU部署數(shù)一定時(shí),路段覆蓋率和RSU平均擴(kuò)展通信范圍只取決于RSU有效覆蓋的路段。限定傳輸最大時(shí)延的增加使更多路段的車輛可以在時(shí)延內(nèi)將數(shù)據(jù)傳輸至RSU,提高了路段覆蓋率和RSU平均擴(kuò)展通信范圍。本文使用貪心算法產(chǎn)生初始種群,經(jīng)過(guò)了選擇、交叉、變異、染色體修復(fù)等一系列循環(huán)迭代,從全局考慮總覆蓋路段部署RSU,而不局限于考慮單個(gè)位置的新覆蓋路段數(shù),因而與其他3種部署方案相比,獲得了更優(yōu)的部署位置。

3.3 部署區(qū)域?qū)π阅艿挠绊?/h3>

本組實(shí)驗(yàn)主要研究部署區(qū)域大小對(duì)實(shí)驗(yàn)結(jié)果的影響。設(shè)置a為15,數(shù)據(jù)限定傳輸最大時(shí)延τ=6 s。圖12和圖13分別給出了4種方案關(guān)于路段覆蓋率和RSU平均擴(kuò)展通信范圍的對(duì)比圖。

圖12 部署區(qū)域?qū)β范胃采w率的影響

圖13 部署區(qū)域?qū)SU平均擴(kuò)展通信范圍的影響

由圖12、圖13可知,部署區(qū)域面積增大時(shí),路段覆蓋率逐漸下降,RSU平均擴(kuò)展通信范圍逐漸增加,且本文方案的性能優(yōu)于其他3種方案。這是因?yàn)椴渴饏^(qū)域增大時(shí),RSU有效覆蓋的路段增加,提高了RSU的平均擴(kuò)展通信范圍,但其增加低于區(qū)域內(nèi)子路段的增加,使得路段覆蓋率逐漸降低。MCP-g部署方案與熱點(diǎn)部署方案只考慮單個(gè)RSU部署后覆蓋的路段,容易產(chǎn)生局部最優(yōu)解。均勻部署方案雖從全局考慮部署位置,但缺少貪婪性。因此,這3種方案的性能均低于本文算法。

4 結(jié) 論

本文研究了RSU的部署問(wèn)題,證明了該問(wèn)題是NP-hard問(wèn)題且可以轉(zhuǎn)化為集合覆蓋問(wèn)題求解。為獲取候選位置集中各元素覆蓋的子路段數(shù),設(shè)計(jì)了0-1覆蓋矩陣和基于Dijkstra的求解算法。針對(duì)轉(zhuǎn)化后的τ-LSCP問(wèn)題,提出基于改進(jìn)遺傳算法的RSU部署方案，以最大化時(shí)延內(nèi)將數(shù)據(jù)傳輸至RSU的子路段數(shù)。使用貪心算法產(chǎn)生初始種群,按照設(shè)定的交叉算子、變異算子執(zhí)行交叉和變異操作并修復(fù)染色體,循環(huán)迭代求得RSU的部署位置。仿真結(jié)果表明,利用本文方案部署RSU可以提高路段覆蓋率,進(jìn)而提高網(wǎng)絡(luò)的性能。