VANET中基于車輛分簇的協作緩存策略

陳清秋，朱 琦

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

0 引 言

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

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

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

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

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

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

1 系統模型

系統模型如圖1所示。

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

1.1 內容請求和緩存模型

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

(1)

其中，s為齊夫分布的參數，eq為內容q請求次數的排序。參數s越大，表明受歡迎內容出現的概率越高，相應內容請求頻率就會越高，這些內容被緩存的概率也會越高。

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

1.2 時延分析

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

(2)

(3)

(4)

(5)

兩個簇頭之間的通信不受簇成員之間的影響。當移動車輛從RSU獲取內容時，需要在移動車輛、簇頭和RSU之間建立通信連接，內容從路邊單元傳輸到簇頭，再經簇頭傳回請求車輛，此時的內容請求時延為：

(6)

(7)

(8)

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

1.3 成本分析

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

CC=CRSU·CSR+CV·CSV

(9)

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

CT=CqR·CRR+CqV·CVV

(10)

成本為內容緩存成本和傳輸成本之和。

C=CC+CT

(11)

1.4 問題建模

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

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

(12)

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

2 協作緩存算法

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

2.1 分簇算法

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

(13)

其中，w1,w2,w3為各個影響因素的加權因子。

w1+w2+w3=1

(14)

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

(15)

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

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

(16)

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

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

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

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

算法1：分簇算法。

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

輸出：分簇結果

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

2.fori= 1:n

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

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

5.根據式(14)計算車輛的權重

6.ifwi>wj

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

8.簇內車輛數目達到閾值θ時，停止分簇

9.endif

10.endfor

11.endfor

12.完成分簇

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

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

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

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

(17)

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

(18)

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

(19)

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

(20)

螞蟻會根據轉移概率來選擇緩存放置方案，轉移概率與信息素和啟發式信息有關，其計算公式為：

(21)

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

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

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

輸入:系統模型參數

輸出:緩存放置方案

1.forb= 1:NA

2.forq= 1:Q

3.初始化緩存放置方案

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

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

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

7.構建新緩存放置方案

8.更新信息素

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

3 仿真結果與分析

本節進行仿真分析，仿真參數設置如下[23-24]：帶寬設置為10 MHz，車輛和RSU的發射功率分別為25 dBm和50 dBm，噪聲功率為-114 dBm。在緩存方面，將CSR和CSV設置為0.5和0.3，CRR和CVV分別設置為0.8和0.5，WT和WC均設置為0.5，遠程內容服務商的傳輸成本為1.5，內容q的大小為2 Mb，總成本表示時延和成本的加權和，總緩存容量表示RSU和簇頭的總容量，緩存命中率表示RSU和簇頭中緩存有移動車輛所請求內容的概率。圖2表示算法的收斂性，可以看出，在迭代12次左右時，算法達到收斂。

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

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

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

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

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

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

4 結束語

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