考慮信息年齡的無人機輔助智能交通系統計算卸載優化

鐘偉鋒 黃旭民 康嘉文 謝勝利

(廣東工業大學自動化學院 廣州 510006)

1 引言

使用無人機(Unmanned Aerial Vehicle, UAV)的交通監控方法具有機動靈活、部署成本低、隱蔽性強、覆蓋范圍廣等優點，配合現有的固定式交通監控方法，可實現全方位覆蓋、全天候監控以及對道路突發事件的快速響應，是打造智能交通系統與建設智慧城市的重要抓手[1]。根據智能交通系統后臺(即控制中心)的管理需要，調度多架UAV前往不同觀察點，執行交通流量監測、運動目標跟蹤、車輛/行人/交通標志監測與識別等任務。為了配合UAV去完成計算密集型的任務(如流量預測[2]、目標監測與追蹤[3]、行為分析[4])，結合5G時代的移動邊緣計算(Mobile Edge Computing, MEC)技術，在基站側部署MEC服務器，為存儲容量小且計算能力有限的UAV提供額外的存儲空間與計算資源[5,6]?？梢詫⒊Ｓ玫慕煌ūO控應用程序提前緩存于MEC服務器，并把UAV計算任務卸載到MEC服務器，也可以讓UAV從MEC服務器下載應用程序，并在UAV本地執行計算任務。UAV到達指定觀察點后，采集周邊數據并現場處理數據，完成計算任務后，將最新數據的處理結果作為現場信息反饋至控制中心?？刂浦行耐ㄟ^綜合多架UAV提供的多種現場信息，來制定交通管理策略，如圖1所示。

圖1 智能交通系統示意圖

在UAV輔助的智能交通系統中，需要關注兩個關鍵問題，數據處理產生的能耗和數據的時效性。首先，系統部署完成之后，系統主要的運行成本來自系統能耗，因此需要根據MEC服務器的緩存狀態，制定區域內多架UAV與MEC服務器之間的協同通信和計算策略，以降低系統能耗和用電成本。此外，控制中心要求UAV提供足夠新鮮的現場信息，以滿足實時監控的需求，保證控制中心決策的時效性、準確性和可靠性。信息年齡(Age of Information, AoI)是一種衡量信息新鮮度的時間度量，可將其理解為從信息產生到當前時刻所經歷的時長，用于描述信息的時效性，AoI值越小信息新鮮度越高。因此，需要考慮針對智能交通系統設計一種衡量UAV所提供信息的AoI指標，并盡可能讓其減小。

目前，已有文獻針對UAV數據收集與處理中的AoI與能耗優化問題提出了不同的解決方案。文獻[5]提出終端用戶與UAV通信中的離散AoI，在用戶與UAV開始數據傳輸時AoI值為1，在傳輸過程中AoI值持續加1，傳輸完畢后重置為1。文獻[6]關注UAV與MEC服務器等邊緣節點狀態信息的AoI值，它與終端用戶偵測到邊緣節點可接入的時間相關。文獻[7]把UAV完成終端用戶計算卸載服務的時延作為計算任務的新鮮度指標。類似地，文獻[8]考慮物聯網(Internet of Things, IoT)設備狀態信息的AoI值，將其定義為從信息產生到完成信息處理得到結果的時延。進一步，文獻[9]考慮多架UAV協助多個IoT設備的狀態更新，分析出各IoT設備狀態更新數據處理的平均峰值AoI，隨后以最小化所有IoT設備的平均峰值AoI和任務處理產生的能耗為目標，聯合優化任務卸載與UAV飛行軌跡，然而此文獻假定所有IoT設備的本地算力相同且所執行任務相同，這在應用中有一定的局限性。基于相同的優化目標，文獻[10]考慮單架UAV依次飛往不同IoT設備附近，作為數據中繼轉發IoT設備數據至基站，各IoT設備的AoI值主要受UAV飛行次序和數據傳輸帶寬的影響。文獻[11]關注UAV飛往不同IoT設備同時進行數據采集和能量傳輸的場景，與文獻[5]類似，IoT設備AoI值的變化是離散的，通過聯合優化UAV飛行、數據采集與能量傳輸策略，來最小化UAV總能耗，此文獻同樣不涉及UAV的數據處理。文獻[12]中，終端用戶可將任務卸載至UAV或者基站，不同條件下的任務完成時延影響終端用戶的AoI值，而此文獻只優化通信信道的分配。

此外，現有文獻也提出了基于UAV的緩存輔助邊緣計算優化方案。文獻[13]認為UAV可以緩存部分終端用戶的應用程序以服務相應用戶，其余用戶的應用程序緩存在MEC服務器中，然后構建針對數據緩存、任務卸載、通信和計算資源分配的聯合優化問題。類似地，文獻[14]也考慮由UAV緩存應用程序，并定時更新緩存內容，進而聯合優化UAV的緩存選擇、UAV飛往不同終端用戶的軌跡以及用戶任務卸載目的地的選擇等。文獻[15]考慮由MEC服務器與兩架UAV聯合提供緩存空間，使它們向過往車輛提供計算卸載，主要優化系統中存儲、通信與計算資源的分配，默認每輛車均需要任務卸載，目標是最大化所服務的車輛數量。然而，以上文獻中UAV提前緩存好與任務處理相關的應用程序的假設在應用中將受到挑戰。一方面，在現場飛行的UAV可能會被要求臨時承擔未計劃的任務，此時UAV不一定已緩存相應的應用程序。另一方面，UAV作為低功耗的嵌入式設備，其存儲空間相當有限，無法緩存全部應用程序(包含可執行文件、函數庫與輔助數據等)，尤其當面向智能交通系統的應用程序數據量過大時，UAV難以充當高效的緩存節點。此時MEC服務器與云計算服務器是更好的應用程序緩存地點。

綜上所述，同時考慮多架UAV進行數據收集與處理的AoI約束、MEC服務器緩存部分應用程序等條件，并從系統能耗優化角度研究多架UAV與MEC服務器之間協同的工作，在現有文獻中是欠缺的。為了解決以上問題，本文針對如圖1所示的UAV輔助智能交通系統，提出一種考慮信息年齡的計算卸載方案，集中式聯合優化多架UAV任務卸載決策、UAV上下行通信帶寬分配和所有被卸載任務的計算資源分配，滿足交通監測的實時性需求，最小化數據處理產生的系統能耗。

本文的主要貢獻如下：

(1) 考慮UAV交通監測與MEC技術結合的智能交通系統，其中多架UAV執行不同類型的交通監測任務，MEC服務器同時提供數據緩存與計算卸載。利用MEC服務器緩存常用的UAV交通監測應用程序，可提高緩存輔助邊緣計算的可執行性。

(2) 模型中考慮多架UAV數據收集與處理的AoI約束，要求每架UAV的AoI峰值不超過某個給定值，構建包括所有UAV與MEC服務器在內的系統能耗最小化問題，聯合決策UAV任務卸載、通信和計算資源分配。

(3) 運用離散化和線性化手段，將復雜的混合整數且非凸的能耗最小化問題轉化為近似的混合整數線性規劃問題，并設計離散點生成算法來調節近似誤差。實驗結果表明，本方法適用于大型優化問題，可以快速獲得原非凸問題的近似最優解。

2 系統模型

2.1 系統描述

如圖1所示，控制中心根據決策需要，指派多架UAV前往不同觀察點(比如十字路口、主干道出入口與停車場的上空)，以監測當前的車流量、行人數量與空余車位等交通要素。UAV到達觀察點后，采集圖像數據，并執行相關數據分析與計算任務，以得到有效的現場信息。為了配合UAV, MEC服務器被部署于通信網絡的邊緣，與本地基站有線連接，它可以提供存儲空間以緩存常用的交通監測應用程序(比如流量預測、車輛監測與行人識別)，也可以為鄰近UAV提供計算資源。值得一提的是，由于每個應用程序包含可執行文件、函數庫與輔助數據等，存儲容量有限的UAV無法提前安裝好所有的應用程序。在此條件下，如果UAV選擇本地執行任務，則需要向MEC服務器請求緩存數據以加載應用。如果UAV選擇卸載計算任務，則需要將所收集的數據上傳至MEC服務器，由MEC服務器啟動相應的應用程序來處理計算任務。計算完成后UAV得到的現場信息不能超過規定的最大AoI。最終，把現場信息上傳至控制中心，為綜合決策提供依據。

在上述過程中，各UAV與MEC服務器都需要進行優化決策。UAV的決策變量主要為0-1任務卸載變量，即選擇本地執行任務或卸載任務至MEC服務器。MEC服務器需要分配與各UAV數據傳輸的通信帶寬，也需要將自身有限的計算資源分配給那些被卸載的任務。本文關注所有UAV與MEC服務器的能耗總和，稱之為系統能耗。通過掌握各UAV與MEC服務器的狀態和參數，集中式聯合優化上述的決策變量。優化目標是，最小化系統能耗，同時保證滿足AoI和資源容量等約束條件。

2.2 數學模型

(1) 通信模型。參考文獻[16]，本文考慮準靜態決策模型，首先指派UAV去觀察點執行監測任務，UAV到達觀察點后保持懸停狀態，使自身空中位置不變，通過建立視距信道與MEC服務器進行無線通信。設無線信道為準靜態信道，即信道狀態在數據傳輸過程中保持不變。考慮某區域內多架UAV和1個MEC服務器組成的系統。用I表示所有UAV的集合，將每架UAV標記為i ∈I。為防止UAV之間的通信干擾，UAV與基站之間無線通信采用正交頻分多址接入技術[17]，信道功率增益采用自由空間路徑損耗模型[18]。定義從基站到UAVi的數據下行速率為

其中，bi為分配給UAVi的通信帶寬，di為UAVi在觀察點與基站的通信距離，gi為1 m基準距離的信道增益，α為信道衰落指數(一般取2)，Qi為UAVi的接收功率，N0為噪聲功率。設式(1)中對數函數所包含的均為常數，使用常數Yi替代對數部分。定義從UAVi到基站的數據上行速率為

其中，Pi表示UAVi的發射功率。同樣，使用常數Xi替代對數部分。參考文獻[19]，本文考慮每架UAV的上下行通信帶寬大小一樣，以簡化模型。

(2) 時延模型?？紤]二進制任務卸載方式，定義0-1變量ai，ai=0 表 示UAVi在本地執行計算任務，ai=1表 示UAVi將計算任務卸載到MEC服務器，有

若UAV在本地執行計算任務，則UAVi的總時間為

其中，等號右邊第1項τi為UAV前往觀察點的用時；第2項為UAV采集指定數據量Di的用時，si為數據采集速率；第3項為UAV下載指定應用程序的用時，Ui為所請求的應用程序的數據量，ci=1表示應用程序Ui已緩存在MEC服務器，ci=0表示當前MEC服務器沒有緩存Ui，需要從云端獲取Ui，RM是云端到MEC服務器的數據傳輸速率；最后一項為UAV的CPU計算時間，為UAVi的本地計算資源，Wi為處理數據Di所需的CPU周期數。類似的，若將UAV計算任務卸載到MEC服務器，則UAVi的總時間花費為

(3) 信息年齡模型。各UAV有不同的數據收集與處理過程，故UAV所提供的現場信息有不同的AoI值。AoI值越小，現場信息新鮮度越高；AoI值越大，現場信息越不新鮮。參考文獻[5]，將時間離散化為若干個時隙，將每個時隙記為δ=1,2,...，時隙長度為 Δδ。定義在時隙δ中UAVi的AoI值為

設AoI初始值為1，UAV到達觀察點并收集充足輸入數據之后，在數據處理完畢之前，UAV未能提供有效的現場信息，此時AoI值會持續增加。當UAV得到計算結果并將其作為現場信息傳輸至控制中心后，AoI被重置為初始值。本文關注UAVi最終提供現場信息時的AoI值，即

其中，■·」表示向下取整?？刂浦行膶λ蠻AV有統一的AoI要求。設Amax為每架UAV提供現場信息時允許的最大AoI值，有

(4) 能耗模型。本文主要考慮系統中UAV的通信與計算能耗。若UAVi在本地執行計算任務，則相關的能耗為

其中，等號右邊第1項為UAV下載應用程序的能耗，第2項為UAV的CPU能耗。?i為UAVi的能耗系數，代表 CPU的有效開關電容[20]。若將UAVi的計算任務卸載到MEC服務器，則相關的能耗為

其中，等號右邊第1項為UAV上傳所采集數據的能耗，第2項中參數?s為MEC服務器的CPU能耗系數。最終，處理UAVi計算任務所導致的系統能耗可表示為

參考文獻[21]，認為相比于計算輸入數據量，計算輸出數據量可忽略不計，進而在式(4)-式(5)和式(10)-式(11)中忽略MEC服務器將輸出結果回傳給UAV以及UAV將輸出結果作為現場信息發送至控制中心兩個過程所需的時間和能耗。參考文獻[13]，本文關注系統中每架UAV的通信與計算能耗，不計及UAV的飛行和懸停能耗。

(5) 資源容量約束。設MEC服務器的存儲容量為Cs，有MEC服務器數據存儲約束條件

設B為通信帶寬總量，有帶寬總量約束條件

設F為MEC服務器的計算資源總量，對于所有被卸載的任務有計算資源總量約束條件

3 問題描述與求解方案

3.1 系統優化問題

本文優化目標是最小化所有UAV與MEC服務器的總能耗，即系統能耗。將系統能耗最小化問題記為P1，形式如下。

問題的決策變量是 {ai,bi,fiM}i∈I。P1是一個非凸的混合整數非線性規劃(Mixed-Integer NonLinear Programming, MINLP)問題，如果問題規模較大，則很難得到問題的全局最優解[22]。本文求解P1的思路如下：首先采用線性化手段將P1轉化為混合整數線性規劃(Mixed-Integer Linear Programming, MILP)問題，即用MILP問題來近似原MINLP問題，然后提出一種算法來調節由線性化帶來的近似誤差，最后使用現有的求解器來求解MILP問題。

3.2 問題轉換

首先處理式(8)中的取整操作，定義新的整數變量zi，令

其中，Z+={0,1,2,...}是整數集合。式(19)能夠保證整數zi等價于Ti/Δδ」，故可用zi替換原本式(8)中的Ti/Δδ」，得到式(18)。因此，式(18)-式(20)等價于原來的式(8)，且是線性的。

其中，tx,tn分別是的上下界。注意，此時把a當作一個獨立變量。線性不等式(21)和式(22)可以保證：當ai=0 時，有ai=0 ；當ai=1時，有ai=。這與原本雙線性項的效果一樣。因此，可以使用滿足式(21)和式(22)的變量ai(獨立變量)，來等價替換原本的雙線性項ai(兩個變量的乘積)?？梢杂猛瑯拥姆椒▉砭€性化其他雙線性項，具體公式省略。

式(23)和式(24)均為線性等式。然后將式(10)和式(11)分別改寫為

其中，式(25)和式(26)是線性的，mi為中間變量。進一步將式(27)等效地松弛為

可以設r=1/B，r為一個足夠大的數值。計算資源總量約束可改寫為

可以設r=1/F，r為一個足夠大的數值。通過引入新變量ai}i∈I，轉換后的優化問題仍含有非線性函數：式(28)中的 1/(r)2，式(29)中的 1/和式(31)中的1/。接下來參考文獻[24]，采用離散化手段，用一組直線函數來近似一個非線性函數。

3.3 離散化

然后使用式(34)、式(35)來近似非線性約束式(31)。

其中，Fi是中間變量。式(34)中含有雙線性項air，可采用與式(21)、式(22)類似的方式對其進行等價線性化。類似地，針對f2()=1/()2定義另一個離散點集合 {r}。與式(33)類似，定義經過r,r+1的直線,k+1()，然后使用式(36)來近似非線性約束式(28)。

同樣地，針對f3()=1/定義離散點集合 {r}，定義經過,k+1的 直線,k+1()，然后使用式(37)、式(38)來近似非線性約束式(29)。

其中，Bi是中間變量。值得注意的是，被近似的3個函數在其定義域中均為凸函數，過凸函數上任意兩點的線段總在該段凸函數的上方，故式(34)-式(38)中的多條直線形成了對原函數的高估(Overestimation)，即式(34)-式(38)高估了資源實際使用量。因此，滿足約束(34)-式(38)的解，也滿足原本的資源約束式(28)、式(29)、式(31)。

最終，原問題P1被轉換為以下問題，記為P2。

表1 P2與P1的關系

3.4 離散點生成算法

在rk ≤r ≤rk+1范圍里，始終有lk,k+1(r)≥f(r)。因此，用lk,k+1(r) 來近似f(r)的最大垂直誤差是

這是一個凸優化問題，進一步通過分析其KKT條件[25]，可知最優解為

即在點r*處，可得近似誤差的最大值Δ*。算法1給出了生成離散點集合R={rk}的具體步驟。

算法的輸入參數δ是預設的最大允許誤差。在第9, 第13行中可以設置δ0=0.1δ，從而使得實際最大誤差Δ*在δ附近且小于等于δ。算法思路如下：最初，離散點集合R中只有1個離散點r1，從第1個點r1開始，找到第2個點r2使得兩點之間的Δ*在δ附近，然后再找第3個點r3，使得r2和r3之間的Δ*在δ附近，如此重復，直至達到最后一個點rmax?？梢姡惴看紊梢粋€離散點，都能保證最大垂直誤差Δ*≤δ，故在最差的情況下，式(34)和式(37)的近似誤差為Iδ，式(36)的近似誤差為δ。算法只涉及簡單代數計算，并采用二分法尋找新點，能夠快速獲得合適的離散點集合R。仿真中，在δ=0.05下算法1運算時間＜0.01 s。在求解P2之前，只需針對 1/, 1/()2, 1/分別運行算法1各1次即可，然后將生成的離散點代入P2中的約束式(34)、式(36)、式(37)。

算法1 離散點生成算法

4 仿真結果

4.1 仿真設定

考慮系統中有1個MEC服務器和I架UAV，設UAV數量為I=10,20,30。設UAV參數服從給定范圍的均勻分布，接收功率Qi ∈[0.4,1] W，發射功率Pi ∈[0.4,1] W, 數據上行和下行參數Xi ∈[1.25,2.5] B，Yi ∈[1.25,2.5] B，計算資源∈[0.5,1] GHz，能耗參數?i ∈[1,5]×10-27Ws3，飛行時間τi ∈[5,20] s，數據采集速度si ∈[1,5] MB/s，計算任務參數Ui ∈[1,5] MB，Di ∈[5.5,10] MB，Wi ∈[1,2]×109CPU周期， Δδ=1 s。云端傳輸速率RM=10 MB/s, MEC服務器緩存容量Cs=6IMB，帶寬總量B=4IMHz, MEC服務器計算資源總量F=2IGHz。本文中的優化問題和算法都通過MATLAB和YALMIP來實現。

4.2 計算性能結果

首先比較原非凸MINLP問題P1和MILP問題P2的結果。使用YALMIP內置的求解器BNB來求解P1，設置運算時間上限為1小時。在求解P2之前，先設置最大允許誤差δ，通過算法1得到P2中的離散點集合，然后使用求解器GUROBI求解P2。圖2給出了不同求解方案下的系統能耗。圖中不同的δ值表示本方法在P2中使用了不同的離散點集合，δ值越小，近似誤差越小，但離散點數量越多。由本方法的結果可知，UAV數量I越多，計算任務數量越多，系統能耗越高。

圖2 不同求解方案下的系統能耗

當I=10，BNB得到的P1全局最優結果是28.42 J，本方法在δ=0.05,0.1,0.2的結果分別是28.67 J, 30.22 J, 32.35 J?？梢姡闹翟叫?，本方法的結果越接近全局最優結果。隨著UAV數量I增加，P1問題規模增大，BNB無法在1h內得到全局最優。當I=20，BNB得到的P1局部最優結果是61.08 J，本方法在δ=0.05,0.1,0.2的結果分別是57.15 J, 60.24 J, 64.53 J。當I=30，BNB無法在1 h內得到可行解，本方法在δ=0.05,0.1,0.2的結果分別是85.43 J, 90.07 J, 96.55 J?？梢姡痉椒ㄔ谇蠼獯笠幠栴}方面更有優勢，而且減小δ值可以降低本方法對原問題P1的近似誤差。

但是，δ值越小，離散點數量越多，這會導致P2中的約束條件數量增多，進而增加求解問題的運算時間。表2給出了不同求解方案的運算時間。運算時間包括兩部分：YALMIP導入問題的時間和求解器求解問題的時間。P1是非凸MINLP問題，約束條件數量較小，最花費時間的環節在于求解器搜索全局最優解。當I=10時，大概需要11分鐘才能獲得P1全局最優解。P2是MILP問題，求解器求解這類問題的速度較快，但隨著P2的約束條件數量增多，導入問題的時間和求解問題的時間都會增大。如表2所示，δ值越大，運算時間越短。通過調節δ值，本方法可以在結果準確性和運算時間之間取得較好的平衡。比如，在δ=0.05和I=10的情況下，與全局最優解對比，本方法的能耗增加了0.88%，但運算時間降低了約98%。

表2 不同求解方案的運算時間

本方法采用的近似手段是對原非線性函數的高估，即使δ值較大，P2的近似誤差較大，但P2的解仍然是原問題P1的可行解，并不違反帶寬和計算資源上限約束條件。因此，可以在允許的最大誤差內盡可能提高δ值。簡單起見，仿真時所有非線性函數使用同一個δ值。實際上可采用不同的值。假如允許的最大帶寬誤差為 ΔB，則相應的δ值可設為 ΔB/I。假如允許的最大計算資源誤差為 ΔF，則相應的δ值可設為ΔF/I。

4.3 系統決策結果

接下來，考慮本方法在δ=0.05和I=10情況下的決策結果。本文的優化目標是最小化系統能耗，所以MEC服務器CPU能耗系數?s的大小對系統決策的影響較大。從圖3可以看出，?s值越小，系統能耗越小。圖中橫坐標表示控制中心設定的信息年齡AoI上限Amax。如圖所示，Amax值越大，系統能耗越低。這是因為較大的AoI上限可以降低UAV和MEC服務器的計算資源使用量，進而降低CPU能耗。

圖3 不同能耗系數 ?s 與不同信息年齡上限 A max下的系統能耗

圖4給出了在不同情況下從UAV卸載到MEC服務器的計算任務數量。在Amax=3的情況下，MEC服務器的任務數量都是4。這意味著，當AoI上限Amax較小時，系統優化空間較小，不論MEC能耗系數?s是多大，計算卸載的決策都不變。但隨著Amax的提高，系統優化空間增大，不同的?s會導致不同的計算卸載決策。如果MEC服務器能耗系數?s較小，如?s=5，那么系統會增加在MEC服務器上執行的計算任務數量。如果MEC服務器能耗系數?s較大，如?s=10,15，系統趨向于在UAV上完成計算任務，所以MEC服務器的任務數量較少。

圖4 不同能耗系數 ?s 與不同信息年齡上限 A max下在MEC服務器上執行的計算任務數量

5 結束語

本文考慮UAV交通監測與MEC技術結合的智能交通系統，研究UAV到達現場執行交通監測任務過程中的任務卸載、通信與計算資源分配聯合決策問題，尤其考慮多架UAV進行數據收集與處理的AoI約束條件，并由MEC服務器提供緩存輔助邊緣計算。本文旨在最小化系統能耗，把優化問題構造為非凸的MINLP問題，進一步采用線性化手段并設計算法來高效求解問題。仿真結果驗證了所提方法在不同UAV任務條件下的有效性和優越性。