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

1 引言

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

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

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

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

2) 定義鏈路穩(wěn)定性度量，并構(gòu)建預(yù)測權(quán)重鄰接矩陣，從微觀層面精確描述未來周期的拓?fù)潢P(guān)系，并以此篩選緩存節(jié)點(diǎn)，使緩存節(jié)點(diǎn)及其服務(wù)鄰居節(jié)點(diǎn)的選擇更加合理。

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

3.1 系統(tǒng)模型

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

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

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

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

3.2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

4 算法流程及關(guān)鍵步驟

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

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

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

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

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

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

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

4.2 基于負(fù)載約束的最小支配集算法

針對預(yù)測權(quán)重鄰接矩陣t1+W，定義3 種節(jié)點(diǎn)的狀態(tài)，即狀態(tài)未定節(jié)點(diǎn)、服務(wù)鄰居節(jié)點(diǎn)以及緩存節(jié)點(diǎn)，分別對應(yīng)狀態(tài)標(biāo)志位0、1、2，從而可構(gòu)建第t+1 周期的節(jié)點(diǎn)標(biāo)志位向量為

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

算法1基于負(fù)載約束的最小支配集算法

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

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

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

例如，假設(shè)有{1,2,3,4,5,6,7}共7 個(gè)節(jié)點(diǎn)，其拓?fù)潢P(guān)系及鏈路權(quán)重如圖2(a)所示，設(shè)Nmax=3，則根據(jù)所提算法執(zhí)行緩存節(jié)點(diǎn)及其服務(wù)鄰居節(jié)點(diǎn)的篩選，具體過程如下。

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

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

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

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

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

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

5 仿真分析

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

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

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

圖3 仿真場景

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

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

5.2 性能指標(biāo)

將本文所提算法與窮舉法對比，通過大量隨機(jī)拓?fù)涞姆抡娌⒔y(tǒng)計(jì)，以驗(yàn)證篩選出的緩存節(jié)點(diǎn)個(gè)數(shù)和簇平均鏈路權(quán)重均值接近全局最優(yōu)解的程度。其中，緩存節(jié)點(diǎn)個(gè)數(shù)的準(zhǔn)確性通過給定拓?fù)湎?，本文所提算法與窮舉法計(jì)算的最優(yōu)緩存節(jié)點(diǎn)個(gè)數(shù)差值，即緩存節(jié)點(diǎn)個(gè)數(shù)偏差的分布衡量；同理，簇平均鏈路權(quán)重均值也通過與最優(yōu)結(jié)果偏差的均值和標(biāo)準(zhǔn)差衡量。

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

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

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

3) 緩存節(jié)點(diǎn)應(yīng)答次數(shù)均值。定義為一個(gè)周期內(nèi)，每個(gè)緩存節(jié)點(diǎn)平均的響應(yīng)次數(shù)。其值越大，說明平均意義下，緩存節(jié)點(diǎn)能夠?yàn)樵蕉嗥胀ü?jié)點(diǎn)提供文件共享。該指標(biāo)體現(xiàn)了緩存節(jié)點(diǎn)選擇的合理性，同時(shí)也側(cè)面反映了分擔(dān)基站負(fù)載的程度。

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

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

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

圖4 緩存節(jié)點(diǎn)個(gè)數(shù)比較

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

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

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

圖5 簇平均鏈路權(quán)重均值偏差

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

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

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

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

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

圖7 不同車輛緩存空間的請求應(yīng)答率差值

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

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

隨著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。這是因?yàn)镸axDegree 算法僅從連接度考慮，CCMP 算法從熱區(qū)逗留時(shí)間角度考慮了車輛密集程度，而k-means 算法從位置和鏈路的角度綜合考慮，所以k-means 考慮因素更周全，與NmaxMDS 算法的性能差距更小。

圖8 不同服務(wù)鄰居節(jié)點(diǎn)上限的請求應(yīng)答率差值比較

6 結(jié)束語

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

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