車載多接入邊緣網(wǎng)絡(luò)中聯(lián)合資源分配和動(dòng)態(tài)任務(wù)卸載方案*

薛建彬,安 悅,關(guān)向瑞,安亞寧

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院， 甘肅 蘭州 730050)

隨著移動(dòng)網(wǎng)絡(luò)和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，專家預(yù)測(cè)：至2022年，汽車產(chǎn)業(yè)年銷量將達(dá)到600萬輛，全球汽車電子市場(chǎng)規(guī)模達(dá)3 800億美元，繼續(xù)呈加速增長(zhǎng)態(tài)勢(shì)，智能網(wǎng)聯(lián)車熱潮已經(jīng)襲來[1]。車輛激增涌現(xiàn)出了越來越多的時(shí)延敏感型和計(jì)算密集型的新型應(yīng)用，例如自動(dòng)駕駛、車輛社交網(wǎng)絡(luò)[2]和交互式游戲[3]，為了應(yīng)對(duì)不斷激增的數(shù)據(jù)流量和海量的設(shè)備連接，5G將滲透在未來生活的各個(gè)領(lǐng)域。車聯(lián)網(wǎng)技術(shù)與5G的落地應(yīng)用，將為未來無人駕駛汽車提供可靠的技術(shù)支持，并將車聯(lián)網(wǎng)帶入一個(gè)新時(shí)代——無人駕駛時(shí)代。但是，這些新型應(yīng)用給人們的生活帶來巨大便利的同時(shí)，大量的計(jì)算密集型應(yīng)用會(huì)消耗更多的能量，給車載終端造成巨大的壓力[4]。此外，由于移動(dòng)車載終端的計(jì)算資源有限，會(huì)增加消息處理的時(shí)延[5]，這對(duì)車聯(lián)網(wǎng)技術(shù)的研究產(chǎn)生了巨大的挑戰(zhàn)。

面對(duì)這些挑戰(zhàn)，提出了支持多接入邊緣計(jì)算(multi-access edge computating，MEC)[6]的車載網(wǎng)絡(luò)架構(gòu)。MEC服務(wù)器有強(qiáng)大的計(jì)算和存儲(chǔ)能力[7]，基于MEC的解決方案，可以提供低時(shí)延、高帶寬并切合各應(yīng)用場(chǎng)景的計(jì)算處理能力，具有很強(qiáng)的適用性，在這種協(xié)作架構(gòu)下，車輛產(chǎn)生的任務(wù)可以卸載至路邊基礎(chǔ)設(shè)施單元(rode side unit，RSU)上的MEC服務(wù)器執(zhí)行或者卸載至通信范圍內(nèi)的其他車輛上處理，從而節(jié)省了傳輸時(shí)延和處理能耗，解決了車輛自身計(jì)算資源不足的問題[8]。

針對(duì)車輛計(jì)算資源不足的問題，建議將車輛任務(wù)卸載到其通信范圍內(nèi)的其他車輛執(zhí)行，考慮到車輛的移動(dòng)性，在動(dòng)態(tài)網(wǎng)絡(luò)下定義了一個(gè)風(fēng)險(xiǎn)函數(shù)來評(píng)估任務(wù)卸載失敗的可能性，并聯(lián)合系統(tǒng)風(fēng)險(xiǎn)提出了卸載效用函數(shù)。

1 相關(guān)工作

隨著以大數(shù)據(jù)為主要特征的各種先進(jìn)技術(shù)在交通領(lǐng)域的應(yīng)用，車聯(lián)網(wǎng)成為必然的發(fā)展趨勢(shì)。然而現(xiàn)今的車載設(shè)備有限的計(jì)算和存儲(chǔ)能力難以滿足大量高計(jì)算需求和低時(shí)延的限制，因此如何平衡應(yīng)用時(shí)延高要求和車載終端計(jì)算能力，成為近些年研究的重點(diǎn)。多接入邊緣計(jì)算作為5G演進(jìn)的關(guān)鍵技術(shù)，有助于克服車聯(lián)網(wǎng)領(lǐng)域中的發(fā)展瓶頸，為其發(fā)展提供有力支持。

針對(duì)車輛自身資源不足的問題，Hou等[9]提議將道路空閑車輛作為基礎(chǔ)設(shè)施，讓這些車輛提供卸載所需的計(jì)算資源。此外，文獻(xiàn)[10]引入了M/M/1排隊(duì)模型，設(shè)計(jì)了一種基于MEC負(fù)載狀態(tài)的預(yù)測(cè)性卸載策略，通過車與車通信方式進(jìn)行任務(wù)卸載。文獻(xiàn)[11]不僅考慮將車輛產(chǎn)生的任務(wù)卸載至邊緣服務(wù)器，還進(jìn)一步把任務(wù)劃分為可分割和不可分割，再分別進(jìn)行卸載，以減少系統(tǒng)能耗。

前期研究任務(wù)卸載的目的是為了優(yōu)化終端設(shè)備的能耗或者節(jié)省任務(wù)處理時(shí)延，但隨著研究的深入，在計(jì)算卸載過程中，除了上述優(yōu)化目標(biāo)外，還有許多學(xué)者研究了卸載過程中的無線電資源分配和計(jì)算資源分配[12]。例如，Wang等[13]在考慮系統(tǒng)總收入的條件下，聯(lián)合優(yōu)化卸載決策和資源分配，以提高無線網(wǎng)絡(luò)的性能。此外，車聯(lián)網(wǎng)絡(luò)的服務(wù)質(zhì)量和網(wǎng)絡(luò)成本也值得重點(diǎn)關(guān)注。文獻(xiàn)[14]提出了一種時(shí)延預(yù)測(cè)的組合方式，將任務(wù)自適應(yīng)地卸載到MEC服務(wù)器，節(jié)省了計(jì)算成本。Si等[15]將車輛視為邊緣節(jié)點(diǎn)，利用車輛的潛在資源，減輕了網(wǎng)絡(luò)中的數(shù)據(jù)擁塞問題，提升了用戶的服務(wù)質(zhì)量。

總的來說，大部分已有研究將任務(wù)卸載處理可以節(jié)省成本[16]，或提高用戶的卸載效用[17]，能夠彌補(bǔ)車輛自身資源匱乏的缺點(diǎn)。但這些方案都有一些局限性，以上研究都假設(shè)系統(tǒng)是準(zhǔn)靜態(tài)的，并沒有考慮到車輛速度過快導(dǎo)致車與車或者車與基礎(chǔ)設(shè)施通信過程中連接中斷的問題[18]。一旦在任務(wù)卸載期間車輛或是MEC服務(wù)器與產(chǎn)生任務(wù)的終端車輛斷開連接，將會(huì)增大網(wǎng)絡(luò)時(shí)延和能耗成本。因此，為了提高網(wǎng)絡(luò)性能，在車輛卸載過程中，應(yīng)考慮到車輛的移動(dòng)性對(duì)系統(tǒng)的影響。

2 系統(tǒng)模型

圖1 基于V2V通信的計(jì)算任務(wù)卸載Fig.1 Computing task offloading based on V2V communication

2.1 本地計(jì)算任務(wù)模型

(1)

(2)

其中，ε為能量系數(shù)，它的值取決于芯片結(jié)構(gòu)。

2.2 任務(wù)卸載模型

任務(wù)節(jié)點(diǎn)n卸載它的任務(wù)Kn到其中一個(gè)處理車輛j，產(chǎn)生的延遲由三部分組成：傳輸延遲，在處理節(jié)點(diǎn)的計(jì)算延遲，輸出結(jié)果回傳延遲。但是，由于輸出數(shù)據(jù)遠(yuǎn)小于輸入數(shù)據(jù)，因此，第三部分的延遲經(jīng)?？梢院雎浴?/p>

(3)

(4)

其中，hnj為任務(wù)車輛n和處理車輛j之間的信道增益，pn為任務(wù)車輛n的發(fā)射功率，σ2為背景噪聲方差。

則上行鏈路發(fā)送任務(wù)Kn的時(shí)間為：

(5)

任務(wù)在處理車輛處花費(fèi)的時(shí)間為：

(6)

(7)

則卸載的總時(shí)延為：

(8)

上行鏈路的能量消耗為：

(9)

2.3 卸載風(fēng)險(xiǎn)模型

定義當(dāng)卸載時(shí)間大于車輛之間連接時(shí)間為風(fēng)險(xiǎn)。設(shè)計(jì)一個(gè)風(fēng)險(xiǎn)評(píng)估模型來估計(jì)車輛卸載失敗的可能性，風(fēng)險(xiǎn)被公式化為卸載時(shí)間與車輛連接時(shí)間的比例。

(10)

2.4 卸載效用模型

定義卸載效用函數(shù)為：

(11)

3 問題建模和解耦

3.1 問題建模

對(duì)于給定的卸載決策和資源分配，定義系統(tǒng)的卸載效用為所有用戶卸載效用的加權(quán)和。本節(jié)將優(yōu)化問題公式化為混合整數(shù)非線性規(guī)劃(mixed integer nonlinear programming, MINLP)，目標(biāo)函數(shù)為：

(12)

(13)

(14)

0

(15)

(16)

(17)

約束式 (13)是一個(gè)二進(jìn)制卸載變量，表示任務(wù)可以在本地計(jì)算，也可以卸載到處理車輛執(zhí)行。式(14)表示一個(gè)任務(wù)至多卸載至一個(gè)處理車輛執(zhí)行，式(15)表示傳輸功率約束，式(16)表示每個(gè)卸載任務(wù)都應(yīng)該分配計(jì)算資源，式(17)表示分配的總的計(jì)算資源應(yīng)該在處理車輛的服務(wù)能力之內(nèi)。

3.2 問題分解

給定一個(gè)滿足約束式(13)、式(14)的任務(wù)卸載決策，整理可將目標(biāo)函數(shù)重寫為：

(18)

對(duì)于給定的卸載決策，式(18)中的第一項(xiàng)為常數(shù)。 其中

(19)

所以目標(biāo)變成了

(20)

根據(jù)式(8)、式(9)、式(19)?？梢缘玫?/p>

(21)

3.2.1 功率分配問題

s.t. 0

(22)

s.t. 0

(23)

引理1達(dá)到最優(yōu)值v*的條件是，當(dāng)且僅當(dāng)

=0

(24)

該定理的證明可在文獻(xiàn)[21]中得到。

上述定理表示問題P1可以通過它的等價(jià)問題式 (24)得到。此外，由于v*一般是未知的，故用v代替[22]，如算法1所示。

問題式(23)可以改成以下形式：

0

(25)

為了解決P2，注意到問題P2為凸函數(shù)和線性函數(shù)的加權(quán)和，同時(shí)約束條件為凸條件，因此問題P2為凸函數(shù)[23]。 該問題滿足斯萊特條件，可以使用拉格朗日對(duì)偶分解和梯度下降法來解決[24]。 利用拉格朗日乘子法可將問題轉(zhuǎn)化為：

(26)

該問題可以通過一個(gè)主問題和多個(gè)子問題的迭代來解決[24]。 子問題為：

(27)

拉格朗日函數(shù)為：

(28)

其中，k=(k1,k2,…,kNoff)≥0。通過KKT(Karush-Kuhn-Tucker)條件，求函數(shù)L(p,k)對(duì)于pn的微分，可以獲得每個(gè)用戶的最優(yōu)傳輸功率分配。

(29)

算法1 迭代功率分配解決P1

主問題通過拉格朗日乘子來解決，利用梯度下降法更新拉格朗日乘子，k的表達(dá)式為：

(30)

3.2.2 計(jì)算資源分配問題

(31)

(32)

(33)

注意到式(32)～(33)兩個(gè)約束條件都是凸條件，將目標(biāo)函數(shù)P3用Υ(,Α)來表示。Υ(,Α)關(guān)于fnj的二階導(dǎo)數(shù)為：

(34)

因此P3是一個(gè)凸優(yōu)化問題，可以用KKT來解決。

(35)

Υ(

(36)

證明：?jiǎn)栴}P3的拉格朗日函數(shù)為：

(37)

γ=(γ1,…,γj)是拉格朗日乘子，對(duì)fnj求一階導(dǎo)數(shù)，可得：

(38)

令式(38)等于0 ，求解出fnj，然后可得到最優(yōu)的計(jì)算資源分配。

(39)

(40)

(41)

把式(41)代入式(39)可得：

(42)

最后，目標(biāo)函數(shù)P3可表示為：

Υ(

(43)

3.2.3 聯(lián)合任務(wù)卸載調(diào)度和資源分配

在上述分析中，對(duì)于一個(gè)給定的卸載決策，獲得了功率分配和計(jì)算資源分配，根據(jù)式(18)、式(21)和式(36)可得：

(44)

(45)

(46)

其中，p*可以通過算法1 獲得，F(xiàn)*可以通過式(35)得到。 原始問題可重寫為：

(47)

解決問題式(38)的一個(gè)直接方法是窮舉所有可能的卸載決策，進(jìn)而得到最優(yōu)的卸載決策，但此種方法復(fù)雜度為Ο(2n)，其中n=N×J，顯然，使用窮舉法是不切實(shí)際的，因此提出一種次優(yōu)卸載決策的方法來降低復(fù)雜度[25]。程序初始時(shí)，假設(shè)卸載集合=?，找到效用最大的集合，如果存在一個(gè)決策anj∈，將它刪除后集合的效用比刪除之前的集合效用大，那么執(zhí)行刪除操作，從集合中刪除這個(gè)決策，直到再也找不出這樣的決策就停止刪除操作；如果存在一個(gè)決策anj∈Q/，將該決策加入集合中，使得系統(tǒng)效用的值變大，那么執(zhí)行交換操作，直到再也找不出這樣的決策，程序結(jié)束。最后，找到了使系統(tǒng)效用最好的卸載決策集合，具體步驟如算法3所示。

4 仿真分析

圖2(a)～(c)所展示的是用戶數(shù)和系統(tǒng)效用之間的關(guān)系，將用戶數(shù)逐步增加，并在三種不同工作負(fù)載的情況下進(jìn)行比較。從圖2(a)～(c)可以看出，隨著任務(wù)量的增加，所有方案的性能也顯著增加。這是因?yàn)?，?dāng)任務(wù)需要更多的計(jì)算資源時(shí)，用戶將從把任務(wù)卸載到處理車輛中獲益更多。還發(fā)現(xiàn)，隨著用戶數(shù)的增加，系統(tǒng)效用也在增加。這是因?yàn)?，?dāng)有許多用戶競(jìng)爭(zhēng)無線資源和計(jì)算資源來卸載他們的任務(wù)時(shí)，發(fā)送任務(wù)和在處理車輛上執(zhí)行任務(wù)的開銷會(huì)更高，從而降低了卸載效用。從圖中還可以看出，在用戶數(shù)相同的情況下，本文所提JDTORA方案與聯(lián)合任務(wù)卸載和資源分配(joint task offloading and resource allocation, JTORA)方案的系統(tǒng)效用性能極其接近，差值趨于0 。這說明在考慮卸載風(fēng)險(xiǎn)的情況下，即對(duì)影響系統(tǒng)卸載的因素考慮更為全面時(shí)，系統(tǒng)效用依舊可以趨于不考慮風(fēng)險(xiǎn)的優(yōu)解，驗(yàn)證了所提方案的有效性。與傳統(tǒng)的全部本地計(jì)算方案進(jìn)行了比較，本地計(jì)算時(shí)的卸載效用值為0，因此，當(dāng)用戶數(shù)相同的情況下，本文所提方案的效用大于本地卸載方案的效用。

(a) cn=1 000

圖3(a)～(b)表示當(dāng)用戶對(duì)時(shí)間的偏好因子從0.1到0.9變化時(shí)，用戶的平均時(shí)間消耗和能量消耗變化趨勢(shì)。從圖中可以看出，當(dāng)用戶對(duì)時(shí)間的偏好α增加時(shí)，平均時(shí)間消耗降低，相反，平均能量消耗隨之增加。此外，圖中顯示當(dāng)用戶數(shù)更多時(shí)，用戶會(huì)經(jīng)歷更大的時(shí)間消耗和能量消耗，這是因?yàn)楫?dāng)爭(zhēng)奪有限資源的用戶數(shù)更多時(shí)，用戶從卸載的任務(wù)中獲益的機(jī)會(huì)更小。

(a) 平均時(shí)間消耗(a) Average time consumption

圖4顯示的是用戶數(shù)與系統(tǒng)風(fēng)險(xiǎn)之間的關(guān)系。本文的風(fēng)險(xiǎn)是由于任務(wù)卸載引起的，從圖中可以直觀地看出，當(dāng)任務(wù)不進(jìn)行卸載時(shí)(anj=0),系統(tǒng)風(fēng)險(xiǎn)為0；而當(dāng)用戶數(shù)增加時(shí)，系統(tǒng)的風(fēng)險(xiǎn)也隨之增大。這是因?yàn)楫?dāng)更多的用戶卸載它們的任務(wù)時(shí)，增大了系統(tǒng)的卸載風(fēng)險(xiǎn)。

圖4 不同工作負(fù)載情況下，針對(duì)不同用戶數(shù)的系統(tǒng)風(fēng)險(xiǎn)比較Fig.4 Comparison of system risks with different numbers of users under different workloads

5 結(jié)論

通過卸載決策和資源分配的聯(lián)合優(yōu)化，設(shè)計(jì)了邊緣車聯(lián)網(wǎng)系統(tǒng)中基于考慮卸載風(fēng)險(xiǎn)的效用最大化問題。優(yōu)化問題被表述為混合整數(shù)非線性規(guī)劃問題，此問題是難以解決的，因此將原始問題解耦成兩個(gè)子問題，分別使用凸優(yōu)化技術(shù)和分式規(guī)劃技術(shù)解決。最后，聯(lián)合兩個(gè)子問題的解在多項(xiàng)式時(shí)間內(nèi)求出了最優(yōu)的卸載決策。仿真結(jié)果表明所提方案在有大量用戶車輛的實(shí)際環(huán)境中是有效的。 與其他研究不同的是，本文考慮到車輛的移動(dòng)性，設(shè)計(jì)了聯(lián)合資源分配的動(dòng)態(tài)任務(wù)卸載方案，建模了一個(gè)風(fēng)險(xiǎn)函數(shù)來評(píng)估車輛連接中斷的風(fēng)險(xiǎn)。本文的主要貢獻(xiàn)如下：

1)設(shè)計(jì)了一個(gè)邊緣車輛網(wǎng)絡(luò)中的動(dòng)態(tài)卸載模型，為了在動(dòng)態(tài)網(wǎng)絡(luò)中成功卸載任務(wù)，定義了一個(gè)風(fēng)險(xiǎn)函數(shù)來評(píng)估任務(wù)卸載失敗的可能性。

2)聯(lián)合系統(tǒng)風(fēng)險(xiǎn)定義了一個(gè)新的卸載效用函數(shù)，并將此問題建模為任務(wù)卸載決策、功率分配和計(jì)算資源分配的聯(lián)合優(yōu)化問題，以最大化系統(tǒng)的總效用。

3)混合整數(shù)非線性規(guī)劃問題是難以解決的，通過計(jì)算發(fā)現(xiàn)，可以將問題解耦成資源分配問題和具有特定解的卸載決策問題。進(jìn)一步地，將資源分配問題分解為功率分配和計(jì)算資源分配，分別使用分式規(guī)劃和凸優(yōu)化技術(shù)進(jìn)行求解。

4)仿真結(jié)果表明所提動(dòng)態(tài)卸載方案能夠得到近似最優(yōu)解，這證明了該方案的有效性。