負載約束的C-V2X 車輛緩存節點選擇算法

（福建師范大學光電與信息工程學院，福建 福州 350007）

1 引言

隨著現代交通和科技的發展，我國汽車行業的需求量日益增長，V2X（vehicle to everything）受到工業界和學術界的廣泛關注。高效的V2X 系統開發基于大量可靠功能的傳感器，通過在車輛、行人和道路基礎設施之間交換關鍵信息，提供增強的環境感知[1]。為充分利用蜂窩移動通信網絡的技術優勢，C-V2X（celluar vehicle to everything）應運而生，將車輛與一切事物連接，并向NR-V2X（new radio vehicle to everything）演進，在高度動態的車輛拓撲環境下，實現低時延、高可靠的數據傳輸。

V2X 融合了車輛和基站之間的蜂窩通信以及車輛之間的直通通信，2 種模式相互補充，實現基站和車輛之間的負載均衡[2]。若將車輛節點作為緩存節點，可通過車輛之間的連接為其他車輛提供數據服務，以降低數據響應時延，減輕基站的負荷，減少因基站切換引起的開銷，優化基站通信資源分配。在C-V2X 的演進中，3GPP R14 定義了針對車載通信的mode-3 和mode-4，這2 種模式都支持車輛間直通通信，區別在于mode-3 通過蜂窩網絡集中式分配無線資源，而mode-4 由車輛分布式自主選擇無線資源。相比之下，mode-3 中基站能獲取更完整的網絡狀態和不同車輛對資源的需求信息，更有效地利用無線資源[3]，因此本文主要研究C-V2X mode-3 下的車輛緩存節點選擇問題。城市環境C-V2X 中高度動態的車輛拓撲和車輛負載約束使車輛緩存節點的選擇面臨挑戰。1) 增加緩存節點的覆蓋面，則更多的車輛可通過V2V（vehicle to vehicle）從緩存節點獲取文件；2) 減少緩存節點數量，以減少指派緩存節點的控制開銷和預置緩存文件的帶寬開銷，并且過多的緩存節點將加劇信道競爭；3) 降低應答冗余，即減少緩存節點對于同一請求的重復應答，以節省帶寬開銷。因此，合適的緩存節點選擇成了亟須解決的問題。

由于車聯網本身具有快速的拓撲變化，且車輛節點服務能力有限，現有研究較少利用車輛可獲取的移動軌跡信息對鏈路變化進行預判，同時忽視了節點的服務能力上限以及緩存節點的覆蓋性等方面，故車聯網中節點篩選的研究尚不完善。本文提出基于負載約束的C-V2X 車輛緩存節點選擇算法，主要貢獻有以下幾個方面。

1) 合理定義節點狀態，即狀態未定節點、服務鄰居節點以及緩存節點，為緩存節點選擇奠定重要基礎。其中，狀態未定節點為初始狀態，通過所提算法將所有的狀態未定節點轉化為服務鄰居節點或緩存節點，實現了節點間的無重疊全覆蓋；服務鄰居節點有別于傳統鄰居節點的定義，是緩存節點根據每個周期可服務的節點個數上限擇優篩選出的鄰居節點的子集。

2) 定義鏈路穩定性度量，并構建預測權重鄰接矩陣，從微觀層面精確描述未來周期的拓撲關系，并以此篩選緩存節點，使緩存節點及其服務鄰居節點的選擇更加合理。

3) 根據節點的服務能力的局限性，將節點一個周期內可服務的節點個數上限作為負載約束，提出了在給定拓撲下，無重疊全覆蓋的最少緩存節點及其服務鄰居節點的選擇算法。該算法改進傳統的最小支配集篩選算法，結合C-V2X 場景中節點負載約束，以匹配實際節點響應能力，提升了算法的實用性，同時實現了不重疊全覆蓋，優化了系統帶寬利用率。

4) 將所提算法與窮舉算法計算得到的全局最優結果對比，經大量仿真，統計結果表明，所提算法在緩存節點個數和簇平均鏈路權重均值方面都接近全局最優結果。

5) 將所提算法與k-means 無監督聚類算法、最大連接度算法和CCMP 算法進行對比。所提算法在緩存節點及其服務鄰居節點的選擇方面更加合理，實現了無重疊全覆蓋，請求應答率、重復應答率、緩存源應答次數均值等性能指標均優于對比算法，并且重復應答率恒為零，請求應答率可達理論上界。

2 相關工作

在C-V2X 場景下，V2X 的通信效率及穩定性至關重要，通過V2V 通信可以使整個網絡中的系統負荷得到合理的分配，自適應地快速實現車聯網業務的高可靠低時延通信[2]。基于D2D（device to device）的緩存策略已經被證明能有效提升網絡性能[4-7]，借助于V2V 的C-V2X 車輛緩存也將有利于車輛節點間數據共享，其中車輛緩存節點的選擇至關重要。

車輛緩存節點為其通信范圍內的節點提供文件共享服務，也可廣義地視為形成車輛簇，以車輛緩存節點為簇頭，以被服務節點為簇成員。因此，除緩存節點篩選算法外，成簇以及簇頭選擇算法可為車輛緩存節點的選擇提供重要參考。

利用節點屬性構建節點度量值，再通過門限、最值等篩選條件求得簇頭并成簇是常見的算法思路。這在無線傳感網等節點固定的網絡[8-10]以及車聯網等節點移動的網絡[11-18]中均得到廣泛應用。在無線傳感網中，由于節點能量有限，節點的剩余能量是著重考慮的因素。Ray 等[8]以節點剩余能量、節點到基站的距離、連續輪數為參數構建節點度量，度量值小于所設定門限的節點為簇頭。Qiao 等[9]將節點剩余能量和節點到數據采集中心的距離整合為競爭半徑，將該值最大的節點作為簇頭，其他節點就近成簇。Saloni 等[10]將區域劃分為網格，網格中選擇剩余能量最大的節點作為每輪的簇頭。多因素加權獲得度量值并與門限比較得到簇頭并成簇的方法值得借鑒，但是節點移動的網絡中節點拓撲結構變化導致所需要考慮的因素有別于固定網絡。Gao 等[11]將中斷容忍網中每個節點到其他節點可達率的平均概率作為度量值，然后選擇度量值排名靠前的若干節點作為簇頭。車聯網中移動性信息是關鍵因素之一，尤其是速度。Rawashdeh 等[12]考慮了車聯網中節點的速度、位置、節點度和方向等移動信息，將它們整合為適應性度量值，從而選擇該值最大的節點成為簇頭，并將其通信范圍內速度差小于某個門限的節點成簇。Daknou 等[13]以速度最慢的節點作為成簇發起點，將高速公路分區，每個簇中節點以與鄰居的距離和速度差作為參數，加權得到適應度度量，度量值最小的節點作為簇頭。Farooq等[14]令不同車道的車輛各自成簇，同一車道速度相近的車輛成簇，速度最接近設定門限的節點作為簇頭。速度關系本質上體現的是節點間的連接關系，此外，還可以根據節點密度劃分出熱區，并選擇在熱區的平均逗留時間更長的節點作為緩存節點[15]，也可以直接研究節點連接關系，并綜合其他因素完成簇頭篩選和成簇。Alsuhli 等[16]綜合考慮節點與鄰居的平均距離、速度差、連接度、信道質量、鏈路持續時間并歸一化后加權得到度量值，該度量值越大，越有資格成為簇頭，同時還選擇了備用簇頭，簇頭收到入簇請求后，若其簇成員數目未達上限則納入簇。Qi 等[17]通過分割道路完成初始分簇，只有當兩節點鏈路的持續時間超過給定門限時，才記為有效鏈路；根據有效鏈路統計節點的連接度，在連接度大于門限的節點中選擇距離RSU（road side unit）最近的節點作為簇頭。Cheng 等[18]通過連接預測評估節點間拓撲關系，若節點的鄰居節點密度大于門限，則將其設置為核心車輛節點。

盡管車聯網拓撲高度動態，但車輛節點之間具有明顯的跟隨特性，在道路約束下的車輛軌跡也存在規律性，這些都體現在更本質的微觀鄰接關系中。因此，本文也從節點的連接關系入手，與上述文獻不同的是，將節點的屬性轉化為更本質的鏈路屬性，構建鏈路穩定性度量，并且采用基于貪婪思想的迭代算法篩選簇頭并成簇，而非使用門限或最值選擇簇頭。這是因為車聯網具有高度動態的環境，節點間相對關系復雜多變，難以用絕對門限清晰劃分度量值的優劣。

利用優化算法逐步得到優化的節點作為簇頭并成簇也是行之有效的手段，還可避免設定門限的缺陷。Shin 等[19]將節點的剩余能量和連接度整合為度量flooding value，通過迭代交替地將節點的該度量值替換為最大和最小鄰居度量值，收斂之后根據迭代過程中度量值的規律篩選簇頭。針對VANET（vehicular ad-hoc network）動態環境，Fathian 等[20]提出了多目標數據包絡分析聚類算法的數學聚類模型和蟻群算法的啟發式聚類模型，聚類后將最靠近簇中心位置的節點作為簇頭。Ahmad 等[21]引入博弈思想，綜合考慮車輛的速度、位置、方向和LTE（long term evolution）鏈路質量等參數，提出合作利益感知聚類算法，以節點是否接受成為簇頭作為策略，最大化整體利益并完成簇頭篩選，同時采用輪值簇頭機制提升公平性。采用節點集合覆蓋理論的算法可以獲得精簡優化的簇頭集合，例如，Liu 等[22]提出基于廣義控制集和局部內容流行度的內容中心移動自組網協同緩存方案，根據連接度篩選簇頭節點，并將給定多跳范圍內的鄰居節點納為簇成員。Liu 等[23]提出基于最小頂點覆蓋集理論的靜態網絡節點選擇算法，通過社會化關系的協同緩存來確定緩存點，以解決車輛流動性帶來的不連接問題。Li 等[24]考慮用戶分布和流量負載的情況，構建了基站和用戶之間的二部圖，并通過求解最小支配集獲得最優傳輸路徑，基站被默認為簇頭，與其連接的用戶可視為簇成員。

在上述優化方法中，迭代運算是重要的組成部分，快速收斂并減少交互開銷至關重要，并且若帶寬有限且需要實現全覆蓋，相較于其他優化方法，基于最小支配集的方法可以快速計算出簇頭。但其緩存節點服務能力有限，每個周期只能服務有限數量的鄰居節點，目前研究較少直接考慮該因素。因此，利用交通流規律以及拓撲鄰接關系，實現緩存節點和服務鄰居節點的篩選有待進一步研究。

針對以上問題，本文提出了基于負載約束的C-V2X 車輛緩存節點選擇算法。該算法定義了鏈路穩定性度量以及3 種節點狀態，充分利用車輛軌跡的可預測性，在預測未來周期權重鄰接矩陣的基礎上，以服務鄰居節點上限作為負載約束，完成最小支配集篩選，以最少緩存節點不重疊地覆蓋所有節點。所提算法對于C-V2X 的動態拓撲具有較強的自適應性和實效性，在請求應答、重復應答率以及緩存源平均響應次數方面具有顯著優勢，能有效提高車輛緩存節點的利用率，減輕基站負荷。

3 系統模型及問題描述

3.1 系統模型

本文研究城市環境的C-V2X 緩存文件傳輸場景，如圖1 所示。該場景中，主干道交匯處形成岔路口，每條主干道為雙向多車道。設一個通信半徑為RB的基站覆蓋該路口，其覆蓋范圍內車輛數為Nveh，總車輛集合為N={n1,n2,…,nNveh}。

圖1 城市環境的C-V2X 緩存文件傳輸場景

假設車輛節點都具有相同的緩存空間，可容納C個文件。車輛節點既可以發出請求，也可以作為請求響應者。假設車輛內都裝有GPS 等定位設備，可以實時獲取車輛的軌跡信息并上報給基站。在第t周期，第i∈{1,2,…,Nveh}輛車的軌跡信息定義為，其中，(,)為位置坐標，為速度。設車輛的通信半徑為Rveh，每輛車可以從通信范圍內的緩存節點獲取文件，也可以從所歸屬的基站獲取。

基站作為區域服務者，為覆蓋區內車輛節點提供文件服務和資源控制管理，基站通信半徑為RB。通過給基站配置存儲設備和計算設備，可讓基站具備緩存能力和邊緣計算能力。基站采用3GPP R14 版本中設定的mode-3 模式管理車輛間通信的無線資源分配，以實現更高效的子載波利用率[3]。車輛節點在基站的集中控制下與緩存源節點通信，獲取所需文件。同時，基站在緩存源節點的指派上借鑒底層的半持續調度（SPS,semi-persistent scheduling）機制，即在給定時間段內車輛節點由指定緩存源節點管轄，期間各子幀的數據獲取均優先請求該指定緩存節點。這與底層的無線資源SPS 機制匹配，以優化數據分組傳輸效率。

3.2 問題描述

普通節點會先向自己所連接的緩存節點發起文件請求。當緩存節點已緩存相應文件時，則響應請求；否則用戶經一跳或者多跳V2V 鏈路向基站發出該文件請求，由基站經回程鏈路獲取數據后進行響應。通過回程鏈路響應將嚴重增加響應時延，并且城市場景下高密度交通流發出的大量文件請求將導致基站過載，無法同時響應過多文件請求。為了減少通過回程鏈路的文件響應時延并減輕基站負載，應使車輛節點的請求盡可能由周邊車輛緩存節點提供響應，即提高車輛緩存節點的利用率。具體地，應提高車輛節點的請求應答，即提高當前周期所有車輛發送的文件請求中，能被緩存節點響應的請求的比例，該比例越大說明越多的請求能被周邊緩存節點響應，對基站負載的分流作用越明顯。請求應答比傳統的緩存響應率更直接地體現了請求用戶成功獲取所需文件的效率。

緩存文件流行度估計及分配策略不在本文討論范圍內，設文件流行度服從Zipf 分布[6,25-26]，節點發出的請求也服從該分布，緩存節點緩存最流行的前C個文件[27]。將請求應答最大化問題轉化為節點全覆蓋問題，即當選擇的緩存節點能夠覆蓋所有普通節點時，每個普通節點總在至少一個緩存節點的通信范圍內。那么，從概率意義上，當緩存節點在其緩存空間C的約束下緩存最流行的C個文件時，將實現請求應答的最大化，其理論上限為Zipf 分布CDF（cumulative distribution function）中C對應的值。

針對節點全覆蓋問題，在本文的系統中，假設基站作為區域服務者具有宏觀調控的功能，可獲取覆蓋區域內所有車輛節點的軌跡信息。基站將根據第t周期車輛軌跡信息，預測第t+1 周期的車輛位置，從而生成預測權重鄰接矩陣

其中，鏈路的權重表示第t+1 周期車輛節點i和j之間鏈路穩定性度量的值。

基站利用預測的Wt+1，采用緩存節點選擇算法計算緩存節點集合Mt+1={m1,m2,…,mNM}，其節點個數為NM。為減少基站配置及管理緩存節點的開銷，并且減少緩存節點之間信道競爭，應使滿足最優性能時，選擇的緩存節點個數最少，則目標函數為

對于任一緩存節點mk,k∈{1,2,…,NM}，在給定數據幀長和數據傳輸速率的條件下，其每個周期的服務能力有限，設最多只能響應Nmax個鄰居節點的請求，則將該約束稱為負載約束。因此，所研究的問題轉化為負載約束下的節點全覆蓋問題，即緩存節點mk將在其通信半徑范圍內所有節點中選擇不多于Nmax個節點作為服務鄰居節點。將緩存節點mk的q個服務鄰居節點集合記為

這些緩存節點可以覆蓋基站管轄范圍內其他所有普通節點，即緩存節點集合t+1M 與所有緩存節點的服務鄰居節點集合的并集等于N，表示為

為提高系統帶寬利用率，應減少重復應答率。重復應答率即多個緩存節點重復響應同一請求的比例。因此，令每個普通節點只與一個緩存節點建立連接，以實現無重復響應，即一個普通節點在同一周期內對一份文件的請求不會同時被2 個以上的緩存節點響應。因此，所研究的問題進一步轉化為在負載約束和無重疊覆蓋約束下，以最少的緩存節點實現節點全覆蓋問題，即任意2 個緩存節點mk和mu的鄰居集合的交集為空，表示為

另外，每個緩存節點及其服務鄰居節點構成一個簇，緩存節點為簇頭，服務鄰居節點為簇成員。為提高簇穩定性和傳輸可靠性，在確保每個普通節點能且僅能被一個緩存節點覆蓋的前提下，每個緩存節點選擇其覆蓋范圍內鏈路權重大的節點作為服務鄰居節點。緩存節點選擇的服務鄰居節點應使簇平均鏈路權重最大化，因此，所研究的問題轉化為在負載約束和無重疊覆蓋約束下，以最少的緩存節點實現簇平均鏈路權重最大化的節點全覆蓋問題。設緩存節點mk的最優鄰居集合為，對應的簇平均鏈路權重為，則目標函數為

式(6)表示每個緩存節點應選擇最優鄰居，以使簇平均鏈路權重的期望最大化。

綜上所述，可構建待優化的目標函數，如式(7)所示。

該優化問題具有NP-hard 性質，在高度動態的車輛拓撲環境下，為滿足低時延的傳輸要求，求解最優解將導致算法復雜度和計算時延惡化，因此，本文借鑒貪婪思想，提出負載約束下的最小支配集算法，快速計算可行次優解。仿真表明，所提算法的緩存節點個數和簇平均鏈路權重接近窮舉法計算的最優結果。

4 算法流程及關鍵步驟

以車輛節點軌跡信息為基礎，以最小化緩存節點個數以及最大化簇平均鏈路權重的期望為目標，采用負載約束的最小支配集算法，實現車輛節點的全覆蓋。首先，基站收集當前周期內所有節點的行駛信息，以預測得到所覆蓋的范圍內下一周期的拓撲；然后，定義鏈路穩定性度量，以構建預測權重鄰接矩陣；最后，根據預測權重鄰接矩陣實現下個周期的緩存節點選擇。

4.1 鏈路穩定性度量

定義鏈路穩定性度量,?i,j∈[1,Nveh]表示在第t周期車輛節點i和j之間歸一化通信距離容差和歸一化鏈路持續時間的加權和。在第t周期，設車輛節點i和j在相互的通信范圍內且距離為，車輛節點的通信半徑為Rveh，則通信距離容差為Rveh-，從而可得歸一化通信距離容差為

其中，dmin表示在安全距離限制下的兩車最小距離。該值越大說明兩車距離越近，相同遮擋條件下的信道質量越好，并且在兩車的車速均不變時，鏈路持續時間越長。當車間距大于或等于車輛通信半徑時，兩車通信距離容差均視為0，即無法通信。

設周期間隔為Δt，車輛節點i和j在第t周期中，將相互處于對方覆蓋范圍內的時間長度定義為鏈路持續時間，該值由軌跡預測確定[28]。由于鏈路持續時間每周期更新，當值大于周期間隔時，將鏈路持續時間的上限設為Δt，再將其對周期間隔進行歸一化，得到歸一化鏈路持續時間為

鏈路持續時間越長，說明兩車的拓撲關系越穩定，但并不意味著兩車之間的信道質量越好，鏈路穩定性還要考慮兩車之間的傳輸距離、遮擋情況以及干擾等。本文著重研究緩存節點選擇，將鏈路穩定性度量簡化為歸一化通信距離容差和歸一化鏈路持續時間的加權和，即

其中，ρ∈[ 0,1]為加權因子。基站根據第t周期的軌跡信息完成第t+1 周期的軌跡預測并計算，以此作為鏈路權重，并根據式(1)得到Wt+1。

4.2 基于負載約束的最小支配集算法

針對預測權重鄰接矩陣t1+W，定義3 種節點的狀態，即狀態未定節點、服務鄰居節點以及緩存節點，分別對應狀態標志位0、1、2，從而可構建第t+1 周期的節點標志位向量為

所有節點狀態標志位均初始化為0，根據預測權重鄰接矩陣計算每個節點連接狀態未定節點的連接度，即該節點通信覆蓋范圍內連接的狀態未定節點的個數。在服務鄰居個數上限Nmax（即負載約束）下，綜合考慮節點連接度和鏈路穩定性度量，篩選最少的緩存節點t+1M 構成最小支配集，并擇優篩選各緩存節點的服務鄰居節點，實現無重疊的全覆蓋，并最大化簇平均鏈路權重均值，即最優化式(7)的目標函數。具體步驟如算法1 所示。

算法1基于負載約束的最小支配集算法

在上述算法中，與傳統的連接度定義不同，算法中定義的連接度Zi（i∈{1,2,…,Nveh}）是指節點連接狀態未定節點的個數。使用重新定義的連接度，可以避免不完全覆蓋，并且算法執行過程中著重處理未被覆蓋的節點，從而提高算法效率。

在緩存節點選擇方面，優先考慮Zi=0 的孤立節點，將其設置為緩存節點，一方面可以獲取自身所需的文件，另一方面還可以作為攜帶轉發的錨點。其次，考慮Zi=1 的節點，因為這些節點的鄰居節點有且僅有一個，借鑒傳統最小支配集的構建規則，將其鄰居節點置為緩存節點。若多個節點的連接度為1，則優先處理鏈路權重大的節點，因為這些節點能由鄰居節點提供更穩定的數據傳輸，提高數據傳輸成功率。在沒有Zi=0,1的節點時選擇連接度最大的節點作為緩存節點，借鑒貪婪思想，最大程度地完成節點覆蓋。

在服務鄰居節點選擇方面，由于數據幀大小有限，每個緩存節點同一個周期只能為Nmax個鄰居節點提供服務。在篩選鄰居節點的過程中，優先選擇Zi較小的鄰居節點是為了解決節點全覆蓋性，因為Zi較大的鄰居節點被其他緩存節點選擇為服務鄰居節點的可能性更大。考慮緩存節點與鄰居節點鏈路權重在該鄰居節點所有鏈路權重中的排序位次，是為了判斷緩存節點對于該鄰居節點的重要性以及鏈路的穩定性。

例如，假設有{1,2,3,4,5,6,7}共7 個節點，其拓撲關系及鏈路權重如圖2(a)所示，設Nmax=3，則根據所提算法執行緩存節點及其服務鄰居節點的篩選，具體過程如下。

1) 將連接度為0 的孤立節點設置為緩存節點，本例中無孤立節點，可跳過此步驟。

2) 處理連接度為1 的節點，即當某節點的鄰居節點只有一個時，則考慮將該節點的鄰居節點設置為緩存節點。如圖2(a)所示，節點3 的連接度為1，其鄰居節點有且僅有節點2，因此將節點2 設為緩存節點，節點3 納入節點2 的服務鄰居節點集合。

3) 由于Nmax=3，緩存節點2 還可以在剩余的鄰居節點{1,4,5}中選擇2 個節點作為服務鄰居節點。其中，連接狀態未定節點的度最小的是節點5，因此將其納入節點2 的服務鄰居節點集合。

4) 對于節點1 和節點4，鏈路1—2 在節點1的所有鏈路從大到小的排序中位次為2，鏈路2—4在節點4 的鏈路排序位次為1，因此，將節點4 納入節點2 的服務鄰居節點集合。至此，完成緩存節點2 的服務鄰居節點篩選，即節點{3,4,5}。

5) 剩余的狀態未定節點為節點{1,6,7}，其中節點6 連接狀態未定節點的度最大，因此將其選為緩存節點。其鄰居節點個數為2，即節點{1,7}，該值小于Nmax，因此，均納入節點6 的服務鄰居節點集合。對應結果如圖2(b)所示。

圖2 基于負載約束的最小支配集算法案例

5 仿真分析

5.1 仿真場景及參數設置

通過對市區中心某十字路口早高峰實地考察，仿真場景設定為雙向六車道的單個十字路口，每條支路長度為1 km，總面積為2 km×2 km，車流量在交通燈作用下呈現波動上升趨勢，如圖3 所示。設定仿真軟件SUMO（simulation of urban mobility）的參數，從而生成交通流數據，即提取以十字路口為圓心、以500 m 為半徑的車輛軌跡，再采用NS3（network simulator）完成算法性能的分析和評估，關鍵仿真參數如表1 所示。

基站的服務范圍為500 m，車輛之間的通信半徑為50 m。可請求的文件種類總數為20，后續將評估每車的緩存空間分別為1、3、5 時的性能，且所有車輛的緩存空間保持一致。文件流行度服從Zipf 分布，節點請求也服從Zipf 分布。此外，緩存節點可以發出請求，且可以被自身響應，每個緩存節點緩存最流行的前C個文件。C-V2X mode-3 參數設定中，設子載波帶寬為180 kHz，噪聲功率為-113 dBm，數據傳輸率為1 Mbit/s[3]。信道采用Winner+B1 城市場景模式[29]。為匹配車輛間通信半徑設定，發射功率設為10 dBm，并限定數據分組到達率容限為90%。

圖3 仿真場景

表1 關鍵仿真參數

為了評估算法的性能，將所提算法（下文簡稱NmaxMDS 算法）與窮舉法、CCMP 算法[6]、k-means無監督聚類算法（下文簡稱k-means 算法）[30]、最大連接度算法（下文簡稱MaxDegree 算法）[31]進行對比。

5.2 性能指標

將本文所提算法與窮舉法對比，通過大量隨機拓撲的仿真并統計，以驗證篩選出的緩存節點個數和簇平均鏈路權重均值接近全局最優解的程度。其中，緩存節點個數的準確性通過給定拓撲下，本文所提算法與窮舉法計算的最優緩存節點個數差值，即緩存節點個數偏差的分布衡量；同理，簇平均鏈路權重均值也通過與最優結果偏差的均值和標準差衡量。

此外，將所提算法與3 種代表性算法的緩存節點選擇部分進行比較，由于這些對比算法并不以節點的全覆蓋作為首要優化目標，因此所比較的性能指標不同于上述與窮舉法比較的情況，而主要衡量緩存節點的利用率以及為基站負載分流的程度，所采用的具體性能指標如下。

1) 請求應答率。定義為一個周期內，所有普通節點發出的文件請求中，能被車輛緩存節點響應的請求占據所有請求的比例。該指標反映的是緩存節點為基站分擔負載的程度，其值越大說明越少的文件請求需要從基站獲得響應，即基站負荷越小。同時，該指標還能體現緩存分布的合理性和多樣性。另外，為了更清晰體現該指標性能差異，本節將直觀地比較所提算法與對比算法請求應答率差值，差值越大說明所提算法的優勢越明顯。

2) 重復應答率。定義為一個周期內，被緩存源應答的請求中，同時被多個緩存源應答的請求的比例。該指標體現了緩存分布的冗余度，當節點的請求同時被多個緩存節點響應時，將導致響應冗余和帶寬浪費。

3) 緩存節點應答次數均值。定義為一個周期內，每個緩存節點平均的響應次數。其值越大，說明平均意義下，緩存節點能夠為越多普通節點提供文件共享。該指標體現了緩存節點選擇的合理性，同時也側面反映了分擔基站負載的程度。

5.3 NmaxMDS 算法與窮舉法的性能比較

窮舉法采用遍歷嘗試的方式。緩存節點個數以1為初始值逐步增加，并且每個緩存節點遍歷嘗試所有不超過Nmax個鄰居的鄰居節點組合，直至找到可實現無重疊全覆蓋的最少的緩存節點個數，并且每個緩存節點的服務鄰居節點個數不超過Nmax。隨著緩存節點個數的增加，窮舉法需要嘗試的緩存節點組合以及緩存節點的服務鄰居組合增量巨大，但總節點數過少無法體現算法間性能優劣，因此設節點總數為4～9，服務鄰居個數上限分別為2 和3。為減少隨機誤差，每組參數均重復執行300 次后計算統計平均值。

圖4 反映了不同的拓撲節點總個數和不同Nmax約束下，NmaxMDS 算法和窮舉法的緩存節點個數的比較。統計2 種算法得到緩存節點個數差值出現的次數，再除以總的仿真重復執行次數，即可得到各緩存節點個數偏差占比。從圖4 中可以看出，在不同的節點總數和Nmax約束下，緩存節點個數偏差占比趨于穩定，無偏差比例平均值為95.61%。隨著節點個數增多，緩存節點個數偏差占比沒有顯著差異變化。NmaxMDS算法最終的緩存節點個數較大程度上與窮舉法吻合，有偏差的比例平均值僅為4.39%，且僅比窮舉法的緩存節點個數多一個，但顯然NmaxMDS 算法的時間復雜度遠小于窮舉法。

圖4 緩存節點個數比較

在不同節點個數且不同Nmax約束下，NmaxMDS算法和窮舉法之間的簇平均鏈路權重均值偏差如圖5所示。從圖5 可以看出，NmaxMDS 算法的簇平均鏈路權重均值比窮舉法平均約小11.88%，平均標準差約為8.08%。這是由于為了適應C-V2X 低時延的需求，NmaxMDS 算法采用貪婪思想的思想，以犧牲準確度為代價，提高執行速度，但NmaxMDS 算法所得結果較接近窮舉法的最佳結果。

5.4 NmaxMDS 算法與其他緩存節點選擇算法的性能比較

圖6 呈現了不同周期下，NmaxMDS 算法和MaxDegree 算法、CCMP 算法以及k-means 算法之間的性能比較，其中設C=5，Nmax=3，并且為減少隨機誤差，各算法重復執行300 次后計算統計平均值。

圖5 簇平均鏈路權重均值偏差

從圖6(a)可以看出，NmaxMDS 算法的請求應答率均值保持在58.70%，標準差為1.07%。圖6(a)中的理論值由相同參數設定下，Zipf 分布的CDF計算得到，即文件種類數為20、最流行的前5 個文件的CDF 值為59.32%，NmaxMDS 算法與之偏差約為0.62%。這是由于非理想信道導致的分組丟失引起部分性能損失。NmaxMDS 算法中每個節點均有且僅有一個緩存節點管轄，且緩存節點存儲最流行的前5 個文件，只要請求這5 個文件必然獲得響應，因此理論上可達請求應答率的理論值。其他3種算法隨著周期的增多都呈現波動且略微下降的趨勢，這是因為在如圖3(b)所示的車流量波動上升作用下，由于不完全覆蓋導致更多的節點無法從緩存節點獲得所需文件。CCMP 算法和k-means 算法的請求應答在0.37～0.46 波動，且k-means 算法略優于CCMP 算法。CCMP 算法在進行緩存節點選擇時，考慮了對于節點軌跡的預測和節點在熱區的逗留時長，未考慮節點的覆蓋面。k-means 算法中，設各周期的K值與NmaxMDS 算法的緩存節點個數對應一致，雖然該算法也考慮了鏈路穩定性度量，但對緩存節點的篩選不夠完善。MaxDegree 算法的請求應答最低，且在0.17～0.35 波動，這是因為在進行緩存節點選擇時，僅根據節點的連接度進行選擇，雖然連接度大的節點可以覆蓋更多節點，但是對于節點的服務能力沒有進行適度考慮，容易造成大量的覆蓋冗余，也導致了覆蓋不完全。NmaxMDS算法綜合考慮連接度、負載約束和鏈路穩定性，提升了緩存節點的請求應答，提升網絡的服務性能。

圖6 不同周期下算法性能分析

圖6(b)顯示了4 種算法的重復應答率。3 種對比算法在考慮節點分配成簇的情況下沒有考慮節點本身的負載約束，因此一個節點可能會被多個簇頭共同覆蓋，從而導致了較高的重復應答率。其中，MaxDegree 算法的全覆蓋性不佳，導致了其重復應答率比例較低，其波動一方面由拓撲的隨機性引起，另一方面由于車流量的起伏變化導致。NmaxMDS 算法在服務鄰居節點個數上限約束下，實現了無重疊覆蓋，因此該性能指標恒等于0，可以降低緩存節點之間的信道競爭，減少冗余響應所耗費的帶寬資源。

圖6(c)顯示了4 種算法的緩存源應答次數均值。從圖6(c)可以看出，MaxDegree 算法的緩存源應答次數均值最小，波動區間位于0.7～1.4 次/緩存節點，CCMP 算法和k-means 算法變化趨勢和值都較為接近，且隨著周期變化均呈逐步上升趨勢，在仿真周期末期趨于平緩，達到約1.5 次/緩存節點。算法隨著周期變化，緩存應答次數均值明顯上升且相對于其他算法的優勢逐步增大，仿真周期末期趨于平緩，達到約2.2 次/緩存節點。MaxDegree 算法只考慮了緩存節點可連接節點的數量，忽視了其服務能力，造成了節點的不完全覆蓋，也出現較多的重疊覆蓋，從而降低了緩存應答次數均值。CCMP算法和k-means 算法均從成簇的角度以逗留時長和鏈路穩定性度量等為性能進行簇頭及其鄰居的篩選，故減少了部分冗余響應，但是全覆蓋性仍不足。NmaxMDS 算法除了對車輛軌跡進行提前預測外，在分簇階段也從微觀本質上考慮鏈路的連接實質，提高了緩存節點的應答次數，減輕了基站負擔。具體地，在仿真周期初期，車輛密度較小，孤立節點以及連接度低的節點較多，因此有較多的節點無法相互提供文件共享，從而導致緩存應答次數較小，且與對比算法差距不大。隨著車輛密度增加，鏈路資源逐漸增多，更合理的緩存節點及其服務鄰居節點的選擇逐步突顯了NmaxMDS 算法的優勢。而在仿真周期末期車輛密集，緩存節點的服務能力趨于飽和，因此緩存應答次數趨于平緩，但NmaxMDS算法仍然保持較大優勢。

圖7 反映了3 種對比算法與NmaxMDS 算法在不同車輛緩存空間條件下的請求應答率差值，其中設Nmax=3，C=5,10,15。從圖7 可以看出，該差值均大于零，即NmaxMDS 算法的請求應答率性能在不同車輛緩存空間下均優于對比算法，并且隨著車輛緩存空間的增加，優勢更加明顯。當緩存空間為5 時，NmaxMDS 算法與MaxDegree 算法、CCMP 算法和k-means 算法的差值中位數分別為0.32、0.18 和0.17。當緩存空間增加到15 時，對應的差值中位數增加到0.49、0.28 和0.26。因為更大的緩存空間意味著能存儲更多文件，普通節點能夠以更大概率從緩存節點獲取文件。緩存節點的全覆蓋性越好，請求應答率就越高，并且每個緩存節點更大的緩存空間更加突顯了NmaxMDS 算法在全覆蓋性方面的優勢。

圖7 不同車輛緩存空間的請求應答率差值

NmaxMDS 算法與3 種對比算法在請求應答率差值的75%分位點和25%分位點的變化趨勢與中位數類似，但在這2 個分位點之間的間距方面，與MaxDegree 算法差值的間距最大，k-means 算法的間距次之，CCMP 算法的間距最小。在NmaxMDS算法中，每個普通節點都與一個緩存節點連接，保持接近理論值的請求應答率，2 個分位點的間距越大說明算法效果的穩定性受節點密度和分布的影響越大，其性能的波動明顯。

圖8 呈現了NmaxMDS 算法與3 種對比算法在不同服務鄰居節點上限約束下的請求應答率差值，其中，C=5，Nmax=1,3,5。從圖8 可以看出，請求應答率差值均大于零，說明NmaxMDS 算法優于各對比算法。隨著Nmax增加，NmaxMDS 與3 種對比算法的請求應答率差值逐漸減小。這是因為每個緩存節點可服務更多的鄰居節點時，普通節點可選擇的緩存節點更多。對于每個緩存節點的服務鄰居節點的準確篩選的要求降低，弱化了各算法之間的性能差距。

隨著Nmax增加，NmaxMDS 算法與MaxDegree算法的差值最大，中位數分別是0.37、0.32 和0.29；與CCMP 算法的差值次之，中位數分別是0.31、0.18和0.11；與k-means 算法的差值最小，中位數分別為0.30、0.17 和0.09。這是因為MaxDegree 算法僅從連接度考慮，CCMP 算法從熱區逗留時間角度考慮了車輛密集程度，而k-means 算法從位置和鏈路的角度綜合考慮，所以k-means 考慮因素更周全，與NmaxMDS 算法的性能差距更小。

圖8 不同服務鄰居節點上限的請求應答率差值比較

6 結束語

在城市環境下，C-V2X 車輛拓撲快速變化且傳輸時延要求較高，車輛緩存節點通過V2V 傳輸可降低數據傳輸時延，減輕基站負荷。本文提出NmaxMDS 算法解決緩存節點及其服務鄰居節點的選擇問題，定義鏈路穩定性度量并構建預測權重鄰接矩陣；構建最小化緩存節點個數以及最大化簇平均鏈路權重均值的目標函數；定義3 種節點狀態，在緩存節點負載約束下，求解車輛拓撲的最小支配集，實現無重疊的節點全覆蓋。仿真結果表明，所提算法得到的緩存節點個數和簇平均鏈路權重均值接近窮舉法計算的全局最優結果；在請求應答率、重復應答率和緩存源應答次數等方面均優于對比算法，并且重復應答率恒為零，請求應答率可達理論上界，證明了所提算法可有效提升緩存節點利用率，減輕基站負荷。

在后續工作中，考慮適度地在緩存節點之間引入重疊覆蓋，并利用緩存節點間的協作關系，進一步提升緩存節點的請求應答。