機(jī)載云平臺(tái)系統(tǒng)中基于可靠性感知的卸載策略

鄭 萍

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

0 引言

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

近年來(lái),MEC的任務(wù)卸載引起了研究人員的廣泛關(guān)注。文獻(xiàn)[13]研究了多用戶MEC系統(tǒng)中高能效資源分配方案，將任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化問(wèn)題轉(zhuǎn)化為服務(wù)緩存和任務(wù)卸載問(wèn)題，但未考慮到通信資源的分配。文獻(xiàn)[14]利用單個(gè)無(wú)人機(jī)協(xié)助多個(gè)移動(dòng)終端進(jìn)行任務(wù)卸載，但無(wú)法滿足多用戶密集型計(jì)算任務(wù)的需求。文獻(xiàn)[15]在系統(tǒng)時(shí)延約束下，建立了基于計(jì)算卸載和任務(wù)分配的聯(lián)合凸優(yōu)化目標(biāo)，但未考慮能耗優(yōu)化。文獻(xiàn)[16]設(shè)計(jì)了多無(wú)人機(jī)下自適應(yīng)任務(wù)卸載方案，但未考慮無(wú)人機(jī)飛行耗能。文獻(xiàn)[17]將多無(wú)人機(jī)視為MEC服務(wù)器，并研究了由2層無(wú)人機(jī)組成的MEC網(wǎng)絡(luò)的卸載問(wèn)題，但是該卸載策略容易受到外部環(huán)境的影響，計(jì)算的可靠性低。文獻(xiàn)[18]針對(duì)無(wú)人機(jī)支持的網(wǎng)絡(luò)場(chǎng)景，通過(guò)軌跡優(yōu)化和聯(lián)合資源分配的方法提升系統(tǒng)能量效率，但未考慮任務(wù)卸載的時(shí)延要求。

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

1 系統(tǒng)模型

圖1所示為本文系統(tǒng)模型，由于本文分析機(jī)載云平臺(tái)卸載延遲和可靠性敏感計(jì)算問(wèn)題，因此將系統(tǒng)模型分為計(jì)算模型、通信模型、可靠性模型以及延遲模型。通過(guò)非凸MINLP的形式對(duì)機(jī)載云平臺(tái)卸載延遲和可靠性敏感計(jì)算問(wèn)題進(jìn)行建模和公式表達(dá)。

圖1 基于MEC的系統(tǒng)模型Fig.1 System model based on MEC

1.1 計(jì)算模型

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

(1)

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

(2)

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

(3)

(4)

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

1.2 通信模型

假設(shè)在一個(gè)開(kāi)放的環(huán)境中，終端和無(wú)人機(jī)之間的通信信道由視距(Line-of-Sight，LOS)傳播鏈路所主導(dǎo)。因此，UEi和UAVj之間的信道增益為：

hij(θij)=θijgo，

(5)

(6)

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

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

(7)

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

1.3 可靠性模型

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

(8)

1.4 延遲模型

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

(9)

(10)

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

1.5 問(wèn)題制定

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

(11)

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

(12)

(13)

(14)

(15)

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

2 卸載算法

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

2.1 式(8)凸化

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

(16)

對(duì)式(16)兩邊取自然對(duì)數(shù)，并利用它的性質(zhì)將其等價(jià)改寫(xiě)為:

(17)

(18)

(19)

(20)

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

2.2 式(9)近似

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

(21)

(22)

(23)

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

(24)

2.3 式(12)的近似

(25)

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

(26)

2.4 混合整數(shù)SOCP問(wèn)題變換

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

(27)

式中，km={kik≥0，i∈N，j∈M}為一個(gè)新的松弛變量；m為二次曲線逼近技術(shù)的參數(shù)，可以選擇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)目標(biāo)是放松變量o和a。當(dāng)A是一個(gè)較大的整數(shù)值時(shí)，該變量由式(29)和式(30)執(zhí)行。

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

算法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 仿真與分析

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

表1 仿真參數(shù)

為了驗(yàn)證所提算法的合理性，對(duì)所提出的SCA-SOCP算法進(jìn)行性能評(píng)估，如圖2所示。

(a) 算法的收斂性評(píng)估

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

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

在對(duì)所提出的SCA-SOCP算法進(jìn)行性能評(píng)估后，還分析了不同時(shí)延要求和無(wú)人機(jī)云平臺(tái)的可靠性對(duì)卸載率的影響，如圖3所示。

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

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

由圖3可以看出，當(dāng)時(shí)延要求增加時(shí)，可以獲得更高的卸載率；當(dāng)可用無(wú)人機(jī)數(shù)量增加時(shí)，可以獲得更多的計(jì)算資源。隨著無(wú)人機(jī)的可靠性增加，當(dāng)終端卸載任務(wù)量增加時(shí)，在時(shí)延和可靠性之間存在一種折衷，即增加任務(wù)分區(qū)可以降低由并行計(jì)算所導(dǎo)致的任務(wù)延遲，但可靠性會(huì)降低。

本文將算法1與無(wú)線帶寬在終端間平均分配的SCA-EB算法，以及未優(yōu)化無(wú)人機(jī)位置的SCA-FP算法進(jìn)行比較，同時(shí)研究任務(wù)大小增加的影響，結(jié)果如圖4所示?？梢钥闯?，算法1在卸載率方面優(yōu)于其他方法，證明優(yōu)化無(wú)人機(jī)的位置可以產(chǎn)生積極的影響，因?yàn)橥ㄟ^(guò)增加上行速率可以降低傳輸延遲。此外，對(duì)于計(jì)算量大的任務(wù)，需要消耗更多的資源來(lái)滿足時(shí)延要求，由于通信和計(jì)算資源在其他2種方法中沒(méi)有進(jìn)行優(yōu)化，因此相對(duì)于本文提出的算法卸載率更低。

圖4 任務(wù)大小對(duì)卸載率影響Fig.4 Influence of task size on unloading rate

4 結(jié)論

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