無人機輔助車聯網中基于車輛動態聚類的協作卸載策略*

姜宇晴，李曦，紀紅，張鶴立

（北京郵電大學信息與通信工程學院，北京 100876）

0 引言

在智能交通系統中，隨著C-V2X（Cellular-Vehicle to Everything，蜂窩車聯網）[1]等技術的不斷發展，各類計算密集、低時延、高可靠的新型智能應用層出不窮，網聯自動駕駛便是其典型場景之一[2]。網聯自動駕駛需實時高效連通各類車輛、道路、RSU（Road Side Unit，路側單元）等實體，實現路況實時準確感知、海量信息高效處理、安全行駛以及提供娛樂服務等[3-4]，這些業務對網絡接入覆蓋提出了極高的要求。傳統地面基站由于部署成本高、選址要求嚴格等因素，無法保證系統廣域覆蓋。UAV（Unmanned Aerial Vehicle，無人機）基站由于其靈活性強、易部署等特點，被引入智能交通系統中，構建無人機輔助車聯網，為車輛提供無線接入服務，并提升服務質量[5-6]。

目前已有大量學者針對無人機基站的部署問題開展了廣泛研究。文獻[7]提出一種適用于智能交通系統的UAV 與RSU 聯合部署及調度策略，通過啟發式算法得到無人機部署位置的次優解，以有效提高覆蓋面積。文獻[8]設計了衛星-無人機-車輛三層緩存網絡架構，提出了一種能量感知的編碼緩存策略，以大幅提高系統的能效性能。此外，很多研究人員針對提升無人機基站輔助車輛網絡的吞吐量、時延、能耗等性能指標進行了研究。文獻[9]提出了一種多無人機輔助移動車聯網模型，無人機追蹤車輛并發送下行鏈路信息，通過聯合優化車輛通信調度、無人機功率分配及軌跡，以實現系統吞吐量最大化。文獻[10]從用戶的角度出發，提出了一種基于學習的無人機臨時輔助車輛邊緣計算網絡信道、任務分配策略，無人機作為臨時中繼及計算節點以支持決策系統，實現了數據傳輸速率的有效提高。文獻[11]研究了車輛聚類方式以及車輛密度對無人機輔助車輛網絡性能指標的影響，采用快速全局k-均值方法進行車輛劃分，并部署無人機作為車簇間車輛通信的中繼節點，以最小化系統時延及能耗。

在分布密集且動態性強的網聯自動駕駛場景中，移動車輛節點智能交互頻繁、計算任務量大且必須滿足時延限制以保證駕駛安全，目前還缺乏公認的高效解決方案。針對此問題，本文接下來將提出基于車輛動態聚類的協作卸載策略，以降低車輛計算卸載時延，提升服務質量。

1 系統模型

1.1 網絡模型

在無人機輔助車聯網中，考慮由無人機集合M={1,2,…,j,…,M}、車輛集合N={1,2,…,i,…,N}（M<

圖1 多無人機輔助車簇協作計算卸載

假定每架無人機以速度VjUAV飛行，每輛車以速度Vi行駛，無人機對其所負責的車簇進行追蹤，由于車輛的移動性以及一簇內車輛軌跡并不完全相同，因此簇內車輛的位置分布以及成員是時變的，無人機需根據車輛的地理位置、信道條件等因素對簇內成員進行動態調整，并調整自己的位置。

當無人機所服務的簇內有車輛請求卸載時，無人機可依據任務大小、自身帶寬、算力等因素，決定由自身執行或與鄰居無人機協作，以完成計算卸載任務[14]。

1.2 通信模型

本場景中無線頻段分為兩部分，一部分用于無人機與車輛的通信，另一部分用于無人機間的通信。每架無人機可采用OFDM（Orthogonal Frequency Division Multiplexing，正交頻分復用）在某一特定時隙同時與多輛車通信，無人機與車輛間的通信帶寬分給與其通信的多輛車。無人機-車輛信道主要為LoS（Line of Sight，視距無線傳輸）信道[15]，車輛i 至無人機j 的上行信道功率增益為：

其中di,j(t) 表示在t 時刻車輛i 至無人機j 的距離，γ0表示當二者間距為1 米時的信道功率增益。設無人機j 與車簇j 的總帶寬為Bj，分給車輛i 的帶寬為Bi,j(t)，無人機j的發射功率為Pj，車輛i 的發射功率為Pi，那么車輛i 與無人機j 的上行數據傳輸速率為：

其中N0表示噪聲功率，qj(t) 表示t 時刻車簇j 中請求卸載的車輛數。

考慮無人機與其鄰居無人機間的協作，設無人機j 的鄰居集合為К={1,2,…,K}，無人機j 可將車輛i 上傳的計算任務自己執行或卸載至鄰居無人機k（k ∈К）執行，設無人機j 與k 的通信帶寬為B’j，則其傳輸給k 的速率為：

1.3 計算模型

若無人機j 卸載至其鄰居無人機k，其分給任務i 的算力為Ci,k(t)，則無人機k 的計算時延為：

2 問題建模

本文主要解決區域內多車輛節點請求多無人機計算卸載的問題，將整個問題分為車簇劃分和計算卸載兩個子問題，并對兩個子問題分別進行建模。

2.1 分簇問題建模

假定以全簇車輛平均歷史請求任務量之和與全域車輛平均歷史請求任務量之和的比值作為衡量無人機負載的依據，則無人機j 的負載率可表示為：

為了平衡多架無人機之間的負載，因此在分簇時需要綜合考慮車輛的地理位置、無人機最大可服務數和車輛平均歷史請求任務量。

隨著車輛的移動，當簇內某些車輛偏離絕大部分車輛的軌跡時，為了保障簇內整體性能，可以將這些偏離的車劃分至別的簇中，但由于接入其他簇中會占用簇內原有車輛的資源，因此需要綜合考慮全局，做出全局利益最大化的決策。為了便于分析，在進行分簇時假定簇內所有車輛平分帶寬資源，在后續計算卸載時將會對帶寬資源進行分配優化。由式(2) 可得車輛i 與無人機j 的上行數據傳輸速率，此時qj(t)=Cj，同理可得i 接入無人機k 的上行數據傳輸速率：

此時無人機j 所服務的車輛數變為Cj-1，無人機j 和k 通過判斷全域車輛上行數據傳輸速率之和是否提高決定是否執行轉接操作。

2.2 卸載問題建模

基于上述劃分的車簇結果，推導出車輛節點從發送卸載請求開始，至得到計算結果的總時延表達式，然后提出問題建模表達式。車輛總時延由通信時延和計算時延兩部分組成，由于計算結果數據量很小，因此暫不考慮回程時延。

若車輛i 的計算任務由無人機j 執行，則其總時延可表示為：

當k 被選中時，βj,k(t)=1，否則，βj,k(t)=0。

由于任務i 可由無人機j 或k 執行，那么任務i 的總時延可表示為：

其中C1、C2 為卸載決策時的限制條件，C3、C4 表示無人機算力資源分配的限制條件,C5、C6 表示無人機帶寬資源分配的限制條件。

3 基于車輛動態聚類的協作卸載策略

所提策略包含車輛動態聚類算法和基于遺傳算法的協作卸載策略兩部分，分別對應解決第二章所述車簇劃分和計算卸載兩個子問題。

3.1 車輛動態聚類算法

（1）基于負載均衡的初始加權聚類算法

針對k-均值聚類算法[16]進行改進，將其原有的依靠節點歐氏距離來衡量相似度的劃分標準進行修改，綜合考慮車輛的地理位置和負載均衡，采用節點歐氏距離與平均歷史請求任務量這兩個屬性的加權值作為相似度的判定依據。并根據無人機最大可服務數對簇內成員進行調整，無人機位于車簇的質心上空。具體步驟如下所示：

算法1 基于負載均衡的初始加權聚類算法

輸入：車輛位置信息數據集、無人機最大可服務數Nmaxj、車輛平均歷史請求任務量Dqi；

輸出：車簇初始劃分結果；

1 選擇節點間距最遠的M 個點作為初始質心；

2 根據車輛地理位置及平均歷史請求任務量計算每輛車到M 個質心的加權距離，將其劃分給最近的質心；

3 將超出無人機最大可服務數的簇進行拆分：計算超出的數量n，將簇內距離鄰居簇質心最近的n 個節點劃分給鄰居簇；

4 計算當前簇的質心、負載率。返回步驟2，直到質心以及簇內成員不再變化；

5 輸出車簇初始劃分結果。

（2）基于事件觸發的動態調整算法

得到車簇初始劃分結果后，實時監測車輛位置、速度等信息，一旦滿足觸發條件則進行動態調整。車簇動態調整基于兩個事件觸發：當車輛i 與簇內其他節點的相對速度超過閾值Vmax時；當車輛i 位置偏離簇內其他節點，并且若轉接至本簇無人機j 的鄰居無人機k 后，其上行數據傳輸速率增加時，則觸發動態調整。具體步驟如下所示：

算法2 基于事件觸發的動態調整算法

輸入：車輛位置速度、發射功率；無人機位置、帶寬；分簇情況；

輸出：更新后的分簇結果；

1 判斷車輛與簇內其他節點的相對速度，若大于閾值則跳轉至步驟3；

2 計算車輛與本簇無人機和鄰居無人機的上行數據傳輸速率，若本簇信道條件更好，則保持原有分簇，跳轉至步驟5；

3 假設車輛轉接后無人機調整至新簇的質心上空，計算此時的全域車輛上行數據傳輸速率和；若增加則執行轉接操作，否則不執行；

4 其余車輛根據當前的分簇情況和無人機部署，判斷是否轉接其他簇，重復步驟3；直到全域車輛上行數據傳輸速率和不再發生改變；

5 輸出更新后的分簇結果。

3.2 基于遺傳算法的協作卸載策略

當有任務需要計算卸載時將會執行卸載算法。由于問題P1 為0-1 非線性混合整數規劃問題，難以直接求解。為解決該問題，將引入多目標遺傳算法[17]對其求解。

（1）編碼及種群初始化

對請求任務的卸載決策向量進行編碼，每條染色體的長度為L，表示此時有L 個任務需要決策。任務可選擇的無人機數目為M，即基因的選擇有M 種可能。同理，對算力資源分配及帶寬資源分配向量進行編碼，每條染色體的長度也各為L，此時基因值為浮點數。

（2）適應度函數

遺傳算法在每一次迭代中會生成X 條染色體，根據適應度函數對本次生成的所有染色體進行評估，使得計算卸載任務成功率越高的染色體適應度越高。每次迭代淘汰適應度低的染色體，保留適應度高的染色體，以不斷接近最優。

（3）交叉及變異

從上一代染色體中選取適應度較大的兩個染色體，在交叉點處交換二者基因，從而產生新的基因。通過交叉產生新的染色體，隨機選擇其若干基因并修改基因值，以防止陷入局部最優。此過程用于產生新的計算卸載和資源分配決策變量。

（4）復制

將沒有進行交叉變異操作的染色體進行復制，將其計算卸載和資源分配決策變量保留至下一代。

（5）終止條件

算法達到最大迭代次數Z 終止算法流程。

4 仿真結果分析

4.1 參數設置

設置仿真區域為2 km×2 km 的正方形，車輛以最高20 m/s 的速度在區域內行駛。車輛數目N=20，無人機數目M=4[18]，遺傳算法最大迭代次數Z=50 000。其余參數設置如表1 所示：

表1 仿真參數表

4.2 仿真結果及分析

（1）車簇劃分結果分析

圖2 和圖3 分別是采用k-均值聚類算法和本文所提基于負載均衡的加權聚類算法的車簇分布圖。圖4 結果表明，所提基于負載均衡的加權聚類算法能夠有效降低多無人機負載率方差，平衡負載。且隨著無人機數量的增加，平均歷史請求任務量這一屬性所占權值越小的算法，其無人機負載率方差下降得越快。當平均歷史請求任務量這一屬性所占權值較大時，面對無人機數量的變化，能夠在平衡負載方面擁有較好的性能。

圖2 基于k-均值聚類算法的車簇分布圖

圖3 基于所提聚類算法的車簇分布圖

圖4 無人機負載率方差隨數量變化圖

（2）計算卸載結果分析

為了分別體現出所提車輛動態聚類算法和基于遺傳算法的協作卸載策略兩部分算法的性能特點，將所提算法與采用k-均值聚類且無人機協作的卸載算法（稱為k-均值協作算法）進行對比，用于比較出所提車輛動態聚類算法的性能；將所提算法與采用k-均值聚類但無人機間不協作且資源平分的算法（稱為k-均值無協作算法）[19]進行對比，用于比較出基于遺傳算法的協作卸載策略的性能，得到以下的仿真結果。

圖5 結果表明，相比于其余兩種算法，所提算法的任務成功率更高。在任務請求數較少時，三種算法均可滿足帶寬及算力資源需求。然而隨著任務請求數的增多，帶寬及算力資源被更多車輛所共享，在請求密集的情況下，所提算法的成功率下降更為緩慢，仍可以保持相對較好的性能。

圖5 任務成功率隨請求數變化圖

圖6 結果表明，k-均值無協作算法相比于其余兩種算法，成功任務平均時延更低，原因在于：另兩種算法以達到全局最優為目的，在滿足絕大多數任務時延容忍的條件下，將資源更多地分配給了時延容忍更低的任務，造成了時延容忍高的任務其計算時延有所增加。同時，所提算法相比于k-均值協作算法擁有更低的成功任務平均時延。

圖6 成功任務平均時延隨任務請求數變化圖

圖7 結果表明，其余兩種算法相比于k-均值無協作算法，任務計算卸載時延間的方差更低，這也更好地印證了上述根據圖6 結果分析出的原因。

圖7 任務時延方差隨任務請求數變化圖

5 結束語

在無人機輔助車聯網中，針對網聯自動駕駛場景存在的動態節點智能交互頻繁且時延要求高的網絡特點，提出了基于車輛動態聚類的協作卸載策略。仿真結果表明，所提策略可以有效降低計算卸載時延，提升服務質量。未來工作將繼續在無人機基站輔助車聯網中，針對網聯自動駕駛場景展開研究，考慮無人機飛行高度變化、剩余電量、系統能耗優化等因素并進行分析討論。