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

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

1 引言

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

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

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

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

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

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

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

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

2 相關工作

在C-V2X 場景下，V2X 的通信效率及穩(wěn)定性至關重要，通過V2V 通信可以使整個網(wǎng)絡中的系統(tǒng)負荷得到合理的分配，自適應地快速實現(xiàn)車聯(lián)網(wǎng)業(yè)務的高可靠低時延通信[2]?；贒2D（device to device）的緩存策略已經(jīng)被證明能有效提升網(wǎng)絡性能[4-7]，借助于V2V 的C-V2X 車輛緩存也將有利于車輛節(jié)點間數(shù)據(jù)共享，其中車輛緩存節(jié)點的選擇至關重要。

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

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

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

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

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

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

3 系統(tǒng)模型及問題描述

3.1 系統(tǒng)模型

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

圖1 城市環(huán)境的C-V2X 緩存文件傳輸場景

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

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

3.2 問題描述

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

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

針對節(jié)點全覆蓋問題，在本文的系統(tǒng)中，假設基站作為區(qū)域服務者具有宏觀調(diào)控的功能，可獲取覆蓋區(qū)域內(nèi)所有車輛節(jié)點的軌跡信息?；緦⒏鶕?jù)第t周期車輛軌跡信息，預測第t+1 周期的車輛位置，從而生成預測權重鄰接矩陣

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

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

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

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

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

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

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

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

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

4 算法流程及關鍵步驟

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

4.1 鏈路穩(wěn)定性度量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 仿真分析

5.1 仿真場景及參數(shù)設置

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

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

圖3 仿真場景

表1 關鍵仿真參數(shù)

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

5.2 性能指標

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

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

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

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

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

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

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

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

圖4 緩存節(jié)點個數(shù)比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結束語

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

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