機載云平臺系統中基于可靠性感知的卸載策略

鄭 萍

(南昌師范學院 數學與信息科學學院，江西 南昌 330032)

0 引言

隨著物聯網技術的發展，智能設備生成的數據量呈指數增長。物聯網設備的能量和處理能力有限，導致執行任務效率較低。針對這一問題，部分研究者提出將移動設備上的計算任務或數據傳輸至遠程云端執行[1-2]，然而，傳統的云計算傳輸延時較大，無法滿足用戶的實時需求[2-4]。移動邊緣計算(Mobile Edge Computing，MEC)可以有效降低時延。然而，對于通信鏈路不穩定的地區，數據傳輸可靠性降低[5-8]。通過無人機上搭載云平臺(Cloudlet)為移動用戶提供邊緣計算能力，有效降低網絡擁塞和時延。無人機邊緣計算相對于傳統的邊緣計算，雖然與數據源更近，但是邊緣計算資源受限，因此需要合理利用能量和計算資源，滿足大量用戶的請求，協調多個無人機之間的計算卸載[9-12]。

近年來,MEC的任務卸載引起了研究人員的廣泛關注。文獻[13]研究了多用戶MEC系統中高能效資源分配方案，將任務卸載和服務緩存聯合優化問題轉化為服務緩存和任務卸載問題，但未考慮到通信資源的分配。文獻[14]利用單個無人機協助多個移動終端進行任務卸載，但無法滿足多用戶密集型計算任務的需求。文獻[15]在系統時延約束下，建立了基于計算卸載和任務分配的聯合凸優化目標，但未考慮能耗優化。文獻[16]設計了多無人機下自適應任務卸載方案，但未考慮無人機飛行耗能。文獻[17]將多無人機視為MEC服務器，并研究了由2層無人機組成的MEC網絡的卸載問題，但是該卸載策略容易受到外部環境的影響，計算的可靠性低。文獻[18]針對無人機支持的網絡場景，通過軌跡優化和聯合資源分配的方法提升系統能量效率，但未考慮任務卸載的時延要求。

本文提出了一種可靠性感知計算卸載解決方案。該卸載策略優化無人機的位置、終端任務的劃分、通信和計算資源的分配，將卸載時延和可靠性計算問題表述為非凸混合整數非線性規劃(Mixed Integer Nonlinear Programming，MINLP)問題，再將其轉化為凸性函數，降低了計算的復雜度，利用基于連續凸逼近(Successive Convex Approximation，SCA)方法的低復雜度迭代算法求解。該算法可以在滿足時延和可靠性的同時，最大限度地增加卸載請求的數量。

1 系統模型

圖1所示為本文系統模型，由于本文分析機載云平臺卸載延遲和可靠性敏感計算問題，因此將系統模型分為計算模型、通信模型、可靠性模型以及延遲模型。通過非凸MINLP的形式對機載云平臺卸載延遲和可靠性敏感計算問題進行建模和公式表達。

圖1 基于MEC的系統模型Fig.1 System model based on MEC

1.1 計算模型

采用數據分區模型，其中一個任務可以部分卸載并在多個無人機上并行計算，例如圖像/視頻處理。假設任務劃分的粒度具有任意精度，并且任意2個子任務之間不存在重疊。Si={1,2,…,S}表示任務i可以創建為子任務集，最多可以創建M個子任務(即可用無人機的數量)，Sik變量表示任務i分配給子任務k∈S的大小，Sik=0意味著子任務不存在。為了提高任務i的可靠性，可以將子任務k卸載到多架無人機執行。因此，用oikj表示一個二元決策變量，其中oikj=1表示將任務i的子任務k卸載給UAVj，否則oikj=0。將任務i的子任務k卸載給機載云平臺j時，計算分配的資源量為fikj≥0 Hz，但不能超過機載云平臺的計算能力Fj。通過一個二元決策變量ai表示任務i是否允許被卸載至其他無人機上執行。綜上所述，本模型滿足以下約束條件：

(1)

sik≤ai,?{i,k}∈{N,S}，

(2)

oikj≤ai,?{i,k}∈{N,S,M}，

(3)

(4)

式(1)保證當任務被允許時子任務部分之和等于1。式(2)和式(3)確保未被允許的子任務為空且被忽略。式(4)保證一個已被卸載的子任務被允許。

1.2 通信模型

假設在一個開放的環境中，終端和無人機之間的通信信道由視距(Line-of-Sight，LOS)傳播鏈路所主導。因此，UEi和UAVj之間的信道增益為：

hij(θij)=θijgo，

(5)

(6)

式中，θij和go分別表示參考距離為1 m時的路徑損耗系數和信道功率增益。

假設一個帶寬為BMHz的共用無線電頻譜。由于任務輸出大小通常比任務輸入小得多，因此本文忽略了下行通信。子任務的卸載率為：

(7)

式中，Pij為UEi到UAVj的發射功率；N0為噪聲功率譜密度；bij為UEi和UAVj之間通信分配的帶寬。

1.3 可靠性模型

云計算系統的可靠性是衡量系統能夠提供不中斷的無故障服務的穩定程度。即可靠性定義為：在某種規定的條件下，系統能夠在約定的時間范圍內穩定提供無故障服務的能力。本文利用平均故障間隔時間和從歷史故障和維修記錄中得到的平均修復時間來表示機載云平臺j的可靠性，用φj表示。假設通信鏈路可靠，LOS鏈路提高了上行傳輸效率。為了保證任務的可靠性，采用冗余的方式，即在多架無人機上并行傳輸和計算一個子任務,保證任務i∈N可靠性的條件如下：

(8)

1.4 延遲模型

完成任務i的端到端時延取決于最后一個子任務完成的時延，因此每個被卸載的子任務的總時延必須遵守任務延遲閾值，滿足約束條件：

(9)

(10)

式中，rikj為決策變量，表示子任務k在UEi與UAVj之間進行傳輸的卸載率Rij(θij,bij)的部分。式(9)確保滿足終端最大時延要求，其中時延由上傳時延和計算時延組成；式(10)確保子任務滿足最大任務卸載率。

1.5 問題制定

通過優化無人機的位置、無人機子任務的數量和大小、無人機與子任務之間的關聯以及分配的子任務無線電和計算資源，在滿足終端所需的延遲和可靠性的同時，最大限度地增加可執行任務數量。本文采用集中式方法，控制器離線進行優化程序。由于終端的任務請求在一段時間內重復出現，并在操作運行之前收集，因此無人機的位置在整個卸載過程中可以進行優化，移動終端定期進行任務卸載。另外，可通過重新分配無線電和計算資源來處理請求中的變化。將計算卸載問題構造成非凸性MINLP函數，其表達式如下：

(11)

s.t.(1),(2),(3),(4),(8),(9),(10)

(12)

(13)

(14)

(15)

式(12)是式(6)的簡化公式，降低了問題的復雜性。約束條件式(13)保證所有執行卸載任務滿足無人機云的計算能力，約束條件式(14)表示任務的通信帶寬滿足系統無線電帶寬B，約束條件式(15)為完整性和非負條件。

2 卸載算法

由于式(11)及其約束條件的高復雜性和非凸性，將其轉換為更易于處理的形式，并使用低復雜性的基于SCA的迭代算法來求解問題的近似解。首先將非凸約束凸化為近似式(11)。然后利用基于SCA的二階錐規劃(Second Order Cone Programming，SOCP)算法進行迭代求解直到收斂。

2.1 式(8)凸化

引入松弛變量α={αik≥0,i∈N,k∈S}，將約束條件式(8)改寫為：

(16)

對式(16)兩邊取自然對數，并利用它的性質將其等價改寫為:

(17)

(18)

(19)

(20)

式中，αik≥0為新的松弛變量；ε為趨于零的正數。

2.2 式(9)近似

本文引入松弛變量β={βik≥0,?i∈N,k∈S}，將式(9)等價改寫為：

(21)

(22)

(23)

將約束條件式(22)改寫為以下線性形式：

(24)

2.3 式(12)的近似

(25)

將約束條件式(12)改寫為以下形式:

(26)

2.4 混合整數SOCP問題變換

非凸型約束條件線性化后，將問題進一步轉化為SOCP形式，可以有效提高求解速度和精確度。本文利用二次錐近似法將約束條件式(10)改寫為：

(27)

式中，km={kik≥0，i∈N，j∈M}為一個新的松弛變量；m為二次曲線逼近技術的參數，可以選擇m=4以獲得較高的精度。注意，約束條件式(19)可以被一組類似于式(27)中的二階錐不等式所代替。

2.5 SOCP變換和基于SCA的算法

(28)

s.t.(1)～(4),(13)～(15),(19)～(21),(24),(26),(27)

(29)

(30)

0≤oijk≤1,0≤ai≤1，

(31)

式(31)目標是放松變量o和a。當A是一個較大的整數值時，該變量由式(29)和式(30)執行。

本文定義Γ(n)為在第n次迭代時得到的客觀值，當|Γ(n)-Γ(n+1)|≤10-3時，建立了算法1的收斂準則。

算法11:Set n:=0;2:Initialize starting points for β(n) and θ(n);3:repeat;4:Solve the SOCP problem (16) in order to obtain;P?,θ?,s?,o?,a?,f?,b?,r?,α?,β?,k?,δo?,δa?;5:Set n=n+1;6:Update β(n)=β(n) and θ(n)=θ?;7:until Convergence of the object function (28).

3 仿真與分析

對本文提出的卸載算法進行詳細的評估。仿真場景設置為UAV-MEC物聯網系統下的物聯網設備(地面終端設備)數據處理場景，如圖1所示。在仿真過程中，假定物聯網系統中所有的設備都隨機分布在以無人機起始點為中心的半徑為10 000d0的圓形覆蓋范圍(參考距離d0=1 m)。無人機以固定高度H=50 m保持飛行狀態。參考距離d0=1 m，信道功率增益設置為g0=-50 dB，對于物聯網系統中的第i個地面終端設備，其所需計算任務的輸入數據大小di，遵循均勻分布[30,70]kb。設置Ci=[150,250]Hz，機載云平臺的計算能力Fj=1 200 MHz，系統中第i個地面終端的計算能力為Cmax=300 MHz。噪聲功率譜密度N0=-174 dBm/Hz。另外，第i個地面終端設備的傳輸功率被設定為Pij=30 dBm，假設系統無線電帶寬為B=40 MHz。根據機載云平臺計算能力，實驗場景由M=3架安裝Cloudlet的無人機和N=20個地面終端設備組成。具體仿真參數如表1所示。

表1 仿真參數

為了驗證所提算法的合理性，對所提出的SCA-SOCP算法進行性能評估，如圖2所示。

(a) 算法的收斂性評估

(b) 不同可靠性需求的終端對卸載率影響

首先，對算法收斂性進行評估，如圖2(a)所示，在有限次迭代之后，目標值收斂到穩定值。而針對不同等級的移動終端，分析了Cloudlet可靠性對卸載率的影響，如圖2(b)所示。其中，Rel1，Rel2，Rel3分別表示了Cloudlet的可靠性。當終端可靠性要求較低時，具有較低可靠性的Cloudlet對任務的卸載率影響低，因為子任務需要的冗余小，且不占用大量資源。當終端對Cloudlet可靠性要求較高時，子任務需要更多的冗余，從而消耗更多的資源，限制了移動終端數量。此外，當終端的可靠性要求較高時，算法1的復雜度增加，需要更多次的迭代才能收斂。因此，需要權衡無人機Cloudlet可靠性和資源利用率。圖2(c)表示Cloudlet的計算資源和不同等級終端的時延對卸載率的影響。由于當Cloudlet計算資源增加，卸載率就會提高，因此計算時延將會降低，從而滿足任務時延要求。然而，當任務具有嚴格的時延限制時，卸載率會下降，此時與可用的Cloudlet計算能力無關。因為子任務需要消耗更多的資源來滿足任務時延要求，限制其他任務的可用資源，從而降低了任務卸載率。

在對所提出的SCA-SOCP算法進行性能評估后，還分析了不同時延要求和無人機云平臺的可靠性對卸載率的影響，如圖3所示。

(a) 不同延遲需求下卸載率變化

(b) 不同計算資源下卸載率變化圖3 不同時延要求和不同計算資源對卸載率的影響Fig.3 Influence of different delay requirements and computing resources on unloading rate

由圖3可以看出，當時延要求增加時，可以獲得更高的卸載率；當可用無人機數量增加時，可以獲得更多的計算資源。隨著無人機的可靠性增加，當終端卸載任務量增加時，在時延和可靠性之間存在一種折衷，即增加任務分區可以降低由并行計算所導致的任務延遲，但可靠性會降低。

本文將算法1與無線帶寬在終端間平均分配的SCA-EB算法，以及未優化無人機位置的SCA-FP算法進行比較，同時研究任務大小增加的影響，結果如圖4所示。可以看出，算法1在卸載率方面優于其他方法，證明優化無人機的位置可以產生積極的影響，因為通過增加上行速率可以降低傳輸延遲。此外，對于計算量大的任務，需要消耗更多的資源來滿足時延要求，由于通信和計算資源在其他2種方法中沒有進行優化，因此相對于本文提出的算法卸載率更低。

圖4 任務大小對卸載率影響Fig.4 Influence of task size on unloading rate

4 結論

本文研究了基于機載云平臺的可靠性感知MEC卸載問題，根據所需的延遲和可靠性，最大化所允許的任務數量。提出了一種基于連續凸近似方法的低復雜度迭代算法。該算法優化了無人機的位置、終端的任務劃分、終端設備與無人機的關聯以及考慮計算冗余的資源分配。仿真實驗表明，與典型卸載策略算法相比，提出的SCA-SOCP卸載算法可靠性更高，可有效減少任務計算時延，節約成本，驗證了該算法的有效性，未來工作會綜合考慮系統能耗、延遲以及可靠性，來研究機載云平臺卸載策略。