VANET中基于車輛分簇的協(xié)作緩存策略

陳清秋，朱 琦

(南京郵電大學 江蘇省無線通信重點實驗室，江蘇 南京 210003)

0 引 言

隨著智能交通系統(tǒng)(ITS)的發(fā)展，司機和乘客不僅需要交通信息，還需要更多其他內(nèi)容(例如車內(nèi)娛樂和移動廣告)，這給車載網(wǎng)絡(luò)造成了很大的壓力[1-2]。邊緣緩存是在系統(tǒng)的邊緣部署緩存，在車載網(wǎng)絡(luò)中引入邊緣緩存技術(shù)，將內(nèi)容緩存在路邊單元和車輛中，可以減少從遠程內(nèi)容服務(wù)商獲取內(nèi)容的概率，有效地降低內(nèi)容獲取時延，緩解車載網(wǎng)絡(luò)的壓力[3-5]。

目前對于車載網(wǎng)絡(luò)中的緩存已有一些研究，文獻[6]根據(jù)路邊停放的車輛與沿路行駛的車輛可以形成一個車輛社交區(qū)域，提出了一種車輛社交網(wǎng)絡(luò)中的內(nèi)容分發(fā)策略，該策略中路邊停放的車輛與移動車輛一起分發(fā)內(nèi)容，以減少內(nèi)容下載延遲。在文獻[7]中，作者考慮到不同區(qū)域的內(nèi)容流行度的多樣性，提出了一種內(nèi)容流行度預測的線性模型，根據(jù)內(nèi)容流行度的預測結(jié)果進行內(nèi)容的緩存。文獻[8]在車輛內(nèi)容網(wǎng)絡(luò)的架構(gòu)下提出了一種基于交叉熵的邊緣緩存策略，將內(nèi)容緩存在路邊單元中，以動態(tài)地適應(yīng)內(nèi)容的流行度變化。文獻[9]提出了一種基于移動性預測的協(xié)作緩存策略，該策略中通過移動車輛過去的軌跡來預測車輛到達不同熱區(qū)域的概率，在熱區(qū)域停留時間較長的車輛優(yōu)先被選為緩存節(jié)點，以此來為其他車輛提供更好的服務(wù)。

文獻[10]根據(jù)服務(wù)質(zhì)量要求和有限的回程容量，提出了一種路邊單元放置策略，該策略將宏基站與路邊單元聯(lián)合起來，對文件傳輸服務(wù)和路邊單元布置開銷綜合考慮，能夠在滿足文件傳輸服務(wù)要求的前提下實現(xiàn)最低路邊單元布置開銷。以上對車載網(wǎng)絡(luò)中緩存策略的研究都沒有采用車輛分簇的方法。

車輛分簇在車載網(wǎng)絡(luò)中的應(yīng)用可以提高通信鏈路的穩(wěn)定性，減少車輛之間通信的干擾。文獻[11]提出了一種適用于高速公路場景下的車輛分簇方法，該方法考慮了相鄰車輛之間的速度差，以形成相對穩(wěn)定的車輛分簇。

在文獻[12]中，作者提出了一種新的基于權(quán)重的分簇方法，該方法考慮一個簇中有兩個簇頭，分別是主簇頭和從簇頭，當主簇頭不再適合管理車輛分簇的時候，從簇頭會取代主簇頭來進行簇內(nèi)的信息分發(fā)，以此來提高車輛分簇的穩(wěn)定性。文獻[13]提出了一種基于分簇的協(xié)作緩存方案，該方案中每個簇中包含一個簇頭和一個備份節(jié)點，簇頭負責維護簇內(nèi)緩存信息和節(jié)點信息，備份節(jié)點用于提高系統(tǒng)性能和簇內(nèi)信息的可用性，降低獲取內(nèi)容的時延和開銷。文獻[14]提出了一種基于分簇的車載內(nèi)容網(wǎng)絡(luò)(VCN)中的協(xié)作緩存算法，該算法綜合考慮了車輛的緩存容量和車輛分簇的全局緩存狀態(tài)，在滿足緩存容量限制的前提下可以有效地降低平均累積網(wǎng)絡(luò)成本。文獻[15]基于雙向高速公路情景，提出了一種基于分簇的路邊單元和移動車輛協(xié)作緩存策略，該策略中路邊單元對其覆蓋范圍之內(nèi)的車輛進行統(tǒng)一緩存調(diào)度，提高了在路邊單元覆蓋范圍之外車輛間通過V2V通信完成內(nèi)容交付的成功率。

以上車輛分簇方法中簇間通信是通過V2V方式進行的，而在不相鄰的簇之間進行多跳通信會帶來很高的通信時延和成本。該文提出了一種基于車輛分簇的協(xié)作緩存策略，相鄰簇間通信通過V2V方式進行，不相鄰簇間通信以路邊單元作為中繼。首先根據(jù)車輛的速度和位置以及鄰居車輛的數(shù)目對車輛進行分簇，移動車輛發(fā)出內(nèi)容請求，按照簇頭-相鄰簇-RSU-不相鄰簇的順序進行內(nèi)容搜索，當找到本地緩存內(nèi)容時，按原傳輸路徑將內(nèi)容返回請求車輛。由于移動車輛和路邊單元的緩存容量是有限的，該文設(shè)計了一種基于蟻群算法(ACO)的緩存放置算法，可以充分利用有限的緩存空間，對緩存內(nèi)容進行協(xié)同分配，實現(xiàn)內(nèi)容請求時延和成本的聯(lián)合最小化。通過仿真分析，該算法擁有很好的性能。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示。

一條長度為10 km的單向道路上均勻分布著NR個RSU，隨機分布著NV個移動車輛，每個RSU的緩存容量為SRSU，每個車輛的緩存容量為SV。移動車輛首先進行分簇，隨后在請求內(nèi)容時，可以通過V2V和V2R兩種方式進行。移動車輛先向簇頭請求內(nèi)容，如果簇頭沒有緩存內(nèi)容，則向RSU和其他簇發(fā)出請求，車輛與不相鄰簇之間進行通信時，需要以RSU作為中繼。當RSU和移動車輛都沒有緩存請求內(nèi)容時，則需要從遠程內(nèi)容服務(wù)商獲取內(nèi)容。

1.1 內(nèi)容請求和緩存模型

車輛請求內(nèi)容的流行度遵循齊夫分布[16]，則內(nèi)容q(q∈{1,2,…,Q})的請求概率為：

(1)

其中，s為齊夫分布的參數(shù)，eq為內(nèi)容q請求次數(shù)的排序。參數(shù)s越大，表明受歡迎內(nèi)容出現(xiàn)的概率越高，相應(yīng)內(nèi)容請求頻率就會越高，這些內(nèi)容被緩存的概率也會越高。

在RSURi(i∈{1,2,…,NR})覆蓋范圍下,車輛分成NC個簇。在第i個RSU覆蓋范圍下，第j(j∈{1,2,…,NC})個簇內(nèi)的第k(k∈{1,2,…,n})輛車表示為Vi,j,k，其中Vi,j,1為簇頭，其余車輛為簇成員。移動車輛發(fā)出內(nèi)容請求時，首先向簇頭Vi,j,1發(fā)出請求信息，Vi,j,1檢查本地緩存內(nèi)容，如果有則直接將內(nèi)容q返回請求車輛中。若簇頭沒有緩存內(nèi)容q，會將請求轉(zhuǎn)發(fā)給相鄰簇的簇頭Vi,o,1，如果Vi,o,1緩存有內(nèi)容q，則將內(nèi)容返回給簇頭Vi,j,1，簇頭再將內(nèi)容發(fā)送給請求車輛。若本簇簇頭和相鄰簇頭都沒有緩存內(nèi)容q，Vi,j,1會將請求信息轉(zhuǎn)發(fā)給RSU，如果RSU緩存有請求內(nèi)容，則將內(nèi)容返回，否則將會轉(zhuǎn)發(fā)請求信息至與j不相鄰的簇中。需要注意，簇頭與不相鄰的簇進行通信，必須要以RSU作為中繼。這里考慮到不相鄰簇頭之間進行通信，如果以V2V方式直接進行，需要多跳通信，會產(chǎn)生更高的時延和資源浪費，并且通信鏈路很不穩(wěn)定。若通過RSU中繼通信，可以降低內(nèi)容請求時延，提高車輛在RSU覆蓋范圍內(nèi)的內(nèi)容交付成功率。

1.2 時延分析

車載網(wǎng)絡(luò)中，網(wǎng)絡(luò)拓撲變化快，系統(tǒng)對時延的變化十分敏感。在文中場景下，不同的內(nèi)容獲取方式會產(chǎn)生不同的請求時延[17-19]，假設(shè)請求內(nèi)容為q，內(nèi)容q的大小為sq。當移動車輛從簇頭獲得請求內(nèi)容時，只需要在車輛和簇頭之間建立通信連接，此時的內(nèi)容獲取時延為：

(2)

(3)

(4)

(5)

兩個簇頭之間的通信不受簇成員之間的影響。當移動車輛從RSU獲取內(nèi)容時，需要在移動車輛、簇頭和RSU之間建立通信連接，內(nèi)容從路邊單元傳輸?shù)酱仡^，再經(jīng)簇頭傳回請求車輛，此時的內(nèi)容請求時延為：

(6)

(7)

(8)

表示第j個簇內(nèi)的車輛Vi,j,k從不相鄰的p簇中獲取內(nèi)容。

1.3 成本分析

內(nèi)容請求過程中，成本分為兩個方面，一個是內(nèi)容緩存成本，一個是內(nèi)容傳輸成本。給定RSU的存儲容量為SRSU，車輛的存儲容量為SV，初始緩存內(nèi)容大小分別為CRSU和CV，應(yīng)滿足約束條件CRSU≤SRSU，CV≤SV。車輛緩存內(nèi)容成本為CSV,RSU緩存成本為CSR，且CSV

CC=CRSU·CSR+CV·CSV

(9)

傳輸成本方面，RSU傳輸一個內(nèi)容q的傳輸成本為CRR，車輛傳輸一個內(nèi)容q的傳輸成本為CVV，且CVV

CT=CqR·CRR+CqV·CVV

(10)

成本為內(nèi)容緩存成本和傳輸成本之和。

C=CC+CT

(11)

1.4 問題建模

內(nèi)容請求時延是評判系統(tǒng)性能的重要因素，它可以直接反映出設(shè)計系統(tǒng)模型的好壞。同樣，緩存成本也是評估系統(tǒng)性能好壞的一個標準。因此，該文同時考慮了時延和成本，目標是實現(xiàn)成本和時延的聯(lián)合最小化，以獲得最優(yōu)的緩存策略。對于緩存放置方案而言，應(yīng)綜合考慮緩存成本、內(nèi)容獲取時延和緩存內(nèi)容的多樣性。為了避免緩存冗余，該文規(guī)定同一個內(nèi)容q不能被重復緩存，即在所有的RSU和移動車輛的緩存過程中，內(nèi)容q只能被緩存一次。定義一個緩存放置矩陣AQ,NC+1，其中a=1表示緩存內(nèi)容q，a=0表示不緩存?？紤]到有限的緩存容量，目標函數(shù)可以表示為：

s.t.:a:,:={0,1}

(12)

在(12)中，前兩個約束條件表示內(nèi)容不能被重復緩存，后兩個約束是緩存容量約束，表示每個節(jié)點緩存的內(nèi)容大小不能大于本身的緩存容量。

2 協(xié)作緩存算法

本節(jié)中給出基于車輛分簇的協(xié)作緩存算法。首先，為了車輛通信的穩(wěn)定，該文給出一種基于權(quán)重的分簇方法(WCA)對車輛進行分簇。而問題P1是一個多目標優(yōu)化問題，該文設(shè)計了一種基于蟻群算法的緩存放置算法對其進行求解。

2.1 分簇算法

在車載自組織網(wǎng)絡(luò)初始狀態(tài)下，每輛車都處于獨立狀態(tài)，隨后通過選擇簇頭來劃分不同的簇，該文采用基于權(quán)重的分簇方法[20]來進行分簇?？紤]到車輛周圍的鄰居車輛數(shù)量N、車輛與鄰居的平均距離d、車輛與鄰居車輛的速度差總和vd三個因素。車輛周圍的鄰居車輛數(shù)量表示車輛通信范圍內(nèi)的其他車輛數(shù)目，車輛與鄰居的平均距離表示該車輛與其通信范圍內(nèi)其他車輛的平均歐氏距離，移動車輛的鄰居車輛越多、與鄰居車輛的平均距離越小，說明該車輛越適合被選為簇頭。車輛與鄰居車輛的速度差可以用來評估分簇的穩(wěn)定性，簇頭與簇成員之間速度越接近，說明簇成員在簇內(nèi)的時間越長，通信的成功率也就越高。所以車輛與鄰居的速度差總和越小，說明該車輛越適合被選為簇頭。根據(jù)以上的分析，將權(quán)重定義為：

(13)

其中，w1,w2,w3為各個影響因素的加權(quán)因子。

w1+w2+w3=1

(14)

車輛與鄰居車輛的平均距離為：

(15)

其中，x1和xk表示車輛V1和Vk的橫坐標，y1和yk表示車輛V1和Vk的縱坐標。

車輛與鄰居車輛的速度差之和為：

(16)

其中，v1和vk是車輛V1和Vk的速度，vd表示車輛V1與鄰居車輛的速度差之和。由于車輛的移動性，簇頭和簇成員的狀態(tài)可能會發(fā)生改變，隨之會出現(xiàn)簇的切換和簇的合并，具體過程如下：

(1)簇的切換：簇成員可能會移動到其他簇的覆蓋范圍內(nèi)，此時，它可以接收到兩個簇頭的權(quán)重信息，通過比較兩個簇頭的權(quán)重大小，車輛可以選擇繼續(xù)留在本簇還是成為另一個簇的簇成員。

(2)簇的合并：兩個簇頭有可能進入彼此的覆蓋范圍內(nèi)，此時，簇頭之間會比較彼此的權(quán)重大小，權(quán)重小的簇頭會向簇成員發(fā)送信息，使簇成員回到獨立狀態(tài)，隨后進行重新分簇。

車輛進行分簇時，選擇權(quán)重w最大的車輛作為簇頭(CH)，隨后簇頭將自己的權(quán)重作為信息發(fā)送給鄰居車輛，鄰居車輛對比自身的權(quán)重和簇頭的權(quán)重，若比其小，則加入本簇，自身從獨立狀態(tài)變成簇成員(CM)。為了限制每個簇的大小，該文給定一個閾值θ，當簇成員數(shù)量等于θ時，本簇達到飽和狀態(tài)，不再接收獨立車輛的進入，具體算法如算法1所示。

算法1：分簇算法。

輸入：移動車輛[1,2,…,n]

輸出：分簇結(jié)果

1.隨機生成n個移動車輛，根據(jù)通信范圍確定鄰居車輛數(shù)N

2.fori= 1:n

3.forj= 1:n&j～=i

4.根據(jù)式(15)和式(16)計算車輛與鄰居的平均距離和速度差之和

5.根據(jù)式(14)計算車輛的權(quán)重

6.ifwi>wj

7.車輛i成為簇頭，車輛j成為簇成員

8.簇內(nèi)車輛數(shù)目達到閾值θ時，停止分簇

9.endif

10.endfor

11.endfor

12.完成分簇

2.2 基于蟻群算法的緩存放置算法

問題P1是一個多目標優(yōu)化問題，蟻群算法[21]是一種啟發(fā)式全局優(yōu)化算法，可以很好地解決多目標優(yōu)化問題，所以該文提出了一種基于蟻群算法的緩存放置算法來解決問題P1。蟻群算法是一種模擬螞蟻覓食的優(yōu)化算法，螞蟻在運動過程中，會在經(jīng)過的路徑上釋放信息素，在運動過程中，螞蟻可以感知周圍信息素的強弱，以此來引導自己的行進方向。較短路徑上的螞蟻釋放的信息素較多，隨著時間的推移，較短路徑上累積的信息素濃度越來越高，更多的螞蟻通過感知選擇該路徑。這是一種正反饋現(xiàn)象，最終，螞蟻會聚集在最優(yōu)路徑上，通過最短的路徑到達食物源。

假設(shè)有b只螞蟻，每只螞蟻都可以構(gòu)建一種緩存放置方案。第t次迭代的信息素為τb(t)，則第t+1次迭代的信息素τb(t+1)為：

τb(t+1)=(1-ρ)·τb(t)+χb

(17)

其中，ρ是信息素衰減系數(shù)，1-ρ表示迭代一次后信息素揮發(fā)情況，χb為第b只螞蟻構(gòu)建的緩存放置方案留下的信息素，定義為第b種放置方案下時延和成本加權(quán)和的倒數(shù)，以此來評估該方案的性能，χb越大表明該方案下系統(tǒng)性能越好，χb可以表示為：

(18)

可以看出，放置方案得到的時延和成本越小，該方案累積的信息素就越多。在蟻群算法中除了信息素，還有一個重要因素是啟發(fā)式信息α，α越大表示該路徑越有可能成為最優(yōu)路徑。文中α越大表示緩存放置方案越有可能成為最優(yōu)方案，α可表示為：

(19)

其中β(b)定義如下，β(b)越小表示內(nèi)容更加均勻地緩存在移動車輛和RSU中。

(20)

螞蟻會根據(jù)轉(zhuǎn)移概率來選擇緩存放置方案，轉(zhuǎn)移概率與信息素和啟發(fā)式信息有關(guān)，其計算公式為：

(21)

其中，u和v代表了信息素和啟發(fā)式信息對選擇放置方案的影響。根據(jù)文獻[22]的研究結(jié)果，該文將u,v設(shè)置為1和5，信息素揮發(fā)因子ρ設(shè)置為0.5。

在選擇緩存放置方案時，每個螞蟻可以構(gòu)建一種緩存放置方案，然后計算每個方案的時延和成本，根據(jù)結(jié)果計算信息素和啟發(fā)式信息，隨后可以得到下一次螞蟻構(gòu)建每種方案的概率，重復以上步驟直到找出時延和成本最小的緩存放置方案，具體算法如算法2所示。

算法2：基于蟻群算法的緩存放置算法。

輸入:系統(tǒng)模型參數(shù)

輸出:緩存放置方案

1.forb= 1:NA

2.forq= 1:Q

3.初始化緩存放置方案

4.根據(jù)第一節(jié)中的時延成本分析計算T(b)和C(b)

5.根據(jù)式(19)和式(20)計算τb和αb

6.根據(jù)式(21)計算P(b)

7.構(gòu)建新緩存放置方案

8.更新信息素

9.根據(jù)式(18)找出性能最好的方案

3 仿真結(jié)果與分析

本節(jié)進行仿真分析，仿真參數(shù)設(shè)置如下[23-24]：帶寬設(shè)置為10 MHz，車輛和RSU的發(fā)射功率分別為25 dBm和50 dBm，噪聲功率為-114 dBm。在緩存方面，將CSR和CSV設(shè)置為0.5和0.3，CRR和CVV分別設(shè)置為0.8和0.5，WT和WC均設(shè)置為0.5，遠程內(nèi)容服務(wù)商的傳輸成本為1.5，內(nèi)容q的大小為2 Mb，總成本表示時延和成本的加權(quán)和，總緩存容量表示RSU和簇頭的總?cè)萘浚彺婷新时硎綬SU和簇頭中緩存有移動車輛所請求內(nèi)容的概率。圖2表示算法的收斂性，可以看出，在迭代12次左右時，算法達到收斂。

為了評估文中轉(zhuǎn)發(fā)策略的性能，將其與文獻[25]中的轉(zhuǎn)發(fā)策略進行對比。從圖3可以看出，采用文中轉(zhuǎn)發(fā)策略得到的總成本更低，這是因為文獻[25]中簇頭之間只能通過V2V方式進行通信，兩個不相鄰的簇頭進行通信則需要多跳V2V，這會產(chǎn)生更高的內(nèi)容請求時延和傳輸成本。而在文中轉(zhuǎn)發(fā)策略中，不相鄰的簇頭之間以RSU作為中繼進行通信，可以有效降低傳輸時延和成本，故總成本更低。為了進一步研究系統(tǒng)模型參數(shù)對系統(tǒng)性能的影響，以下針對具體參數(shù)進行仿真分析。

圖4表示總成本和總緩存容量、齊夫參數(shù)s之間的關(guān)系，內(nèi)容數(shù)Q設(shè)置為20。當總緩存容量固定時，隨著s的增大，受歡迎內(nèi)容出現(xiàn)的概率就越高，受歡迎內(nèi)容被緩存在RSU和簇頭中的概率也就越高，這降低了車輛需要從遠程內(nèi)容服務(wù)商獲取內(nèi)容的概率，減少了內(nèi)容獲取時延和傳輸成本，故總成本也隨之降低。當齊夫參數(shù)s固定時，增加總緩存容量，簇頭和RSU中可以緩存更多內(nèi)容，本地緩存成本會有所增加，但內(nèi)容獲取時延和傳輸成本會大大降低，故總成本會降低。

圖5表示總成本和總緩存容量、內(nèi)容數(shù)之間的關(guān)系，齊夫參數(shù)s設(shè)置為0.7。當總緩存容量固定時，隨著內(nèi)容數(shù)的增加，總成本也隨之增大，這是因為簇頭和RSU中緩存的內(nèi)容數(shù)是固定的，此時增加總內(nèi)容數(shù)，車輛有更高的概率需要從遠程內(nèi)容服務(wù)商獲取內(nèi)容，而從內(nèi)容服務(wù)商獲取內(nèi)容需要更高的請求時延和傳輸成本，總成本也就隨之增加。當內(nèi)容數(shù)固定時，隨著總緩存容量的增加，RSU和簇頭中緩存的內(nèi)容隨之增加，緩存成本會略微增大，而車輛有更高的概率從簇頭和RSU中獲取內(nèi)容，內(nèi)容的請求時延和傳輸成本會隨之降低，總成本也隨之減少。

圖6表示緩存命中率與總緩存容量、齊夫參數(shù)s之間的關(guān)系，內(nèi)容總數(shù)Q設(shè)置為20。當總緩存容量固定時，隨著s的變大，受歡迎內(nèi)容出現(xiàn)的概率就越高，受歡迎內(nèi)容被緩存的概率也就越高，移動車輛越有可能從RSU和簇頭中獲取內(nèi)容，所以緩存命中率會隨之

提高。當齊夫參數(shù)s固定時，隨著總緩存容量的增加，簇頭和RSU中可以緩存更多內(nèi)容，移動車輛有更高概率從中獲取請求內(nèi)容，緩存命中率也隨之提高。

圖7表示緩存命中率和總緩存容量、內(nèi)容數(shù)之間的關(guān)系，齊夫參數(shù)s設(shè)置為0.7。當總緩存容量固定時，隨著內(nèi)容總數(shù)的增加，緩存命中率不斷降低，這是因為簇頭和RSU中緩存的內(nèi)容數(shù)是固定的，此時增加總的內(nèi)容數(shù)，車輛需要從遠程內(nèi)容服務(wù)商獲取內(nèi)容，降低了車輛從本地獲取內(nèi)容的概率，緩存命中率也隨之降低。

4 結(jié)束語

為了充分利用車載網(wǎng)絡(luò)中的緩存資源，降低內(nèi)容請求時延和緩存成本，該文提出了一種基于車輛分簇的協(xié)作緩存策略。具體來說，為了車輛通信的穩(wěn)定性，首先對車輛進行分簇，隨后在內(nèi)容請求過程中，車輛可以從簇頭和路邊單元中獲取內(nèi)容，不同的內(nèi)容獲取方式有著不同的時延，為了使時延和成本聯(lián)合最小化，設(shè)計了一種基于蟻群算法的緩存放置算法對其進行求解，得到了最優(yōu)緩存放置方案，最后通過仿真證明該算法具有很好的性能。在未來的工作中，將進一步研究地面和空中緩存節(jié)點之間的協(xié)作，以進一步提高系統(tǒng)性能。