羅 優(yōu),李 暉,2,周又玲,王 萍,林志陽

(1.海南大學(xué) 信息與通信工程學(xué)院，?？?570228；2.南京信息工程大學(xué)濱江學(xué)院，江蘇 無錫 214105)

0 引 言

隨著城市化進程的快速推進以及汽車數(shù)量的飛速增長，道路安全、交通效率和環(huán)境污染等一系列交通問題日益突出。為了建立更加安全、綠色、高效的交通管理系統(tǒng)，實現(xiàn)人、車、環(huán)境的協(xié)調(diào)發(fā)展，車聯(lián)網(wǎng)技術(shù)應(yīng)運而生。車聯(lián)網(wǎng)(Internet of Vehicles，IoV)通過車內(nèi)、車與車、車與路、車與人、車與服務(wù)平臺的全方位萬物互聯(lián)，可實現(xiàn)智能交通管理控制、車輛智能化控制和智能動態(tài)信息服務(wù)的一體化。隨著車聯(lián)網(wǎng)的迅速發(fā)展，一系列涵蓋行駛安全、交通效率和車輛通信服務(wù)的車載應(yīng)用也隨之迅速發(fā)展，如自動駕駛技術(shù)、增強現(xiàn)實技術(shù)等。

當(dāng)前車載技術(shù)無法滿足日益增長的車載應(yīng)用對時延的需求[1]，將移動邊緣計算(Mobile Edge Computing，MEC)集成到通信網(wǎng)絡(luò)架構(gòu)中，可以有效解決車聯(lián)網(wǎng)中計算密集型任務(wù)和延遲敏感型任務(wù)所導(dǎo)致的指數(shù)級增長的移動流量，因為在物聯(lián)網(wǎng)業(yè)務(wù)場景中，邊緣模塊[2-3]可以提供低業(yè)務(wù)延遲、低能耗、適當(dāng)?shù)木彺?、快速的通信和靈活的計算。Cui等人[4]提出了一種聯(lián)合云計算、移動邊緣計算及本地計算的多平臺智能卸載方案，根據(jù)任務(wù)屬性利用強化學(xué)習(xí)算法選擇卸載平臺，旨在最小化時延并節(jié)省系統(tǒng)總成本，但所提網(wǎng)絡(luò)模型中的控制面和數(shù)據(jù)面是深度耦合，使得任務(wù)處理缺乏靈活性。Zhang等人[5]提出了一種基于分層云的車載邊緣計算卸載框架，通過引入鄰域中的備份服務(wù)器來解決MEC服務(wù)器計算資源有限問題。Li等人[6]提出了一種新的架構(gòu)，它結(jié)合了遠程中央云、附近的邊緣計算服務(wù)器和車載云，以擴展車輛移動應(yīng)用的可用云服務(wù)?；谠频腗EC卸載框架的提出能夠進一步降低任務(wù)持續(xù)時間，包括移動設(shè)備將任務(wù)卸載到云端的傳輸時間、云中的執(zhí)行時間以及云發(fā)送的傳輸任務(wù)結(jié)果到移動設(shè)備的時間，同時減少移動設(shè)備的能耗和傳輸成本。左超等人[7]提出了一種面向設(shè)備優(yōu)先級的貪心算法，通過對每個設(shè)備能耗和 CPU 占用率設(shè)定優(yōu)先級，獲得當(dāng)前最優(yōu)的任務(wù)分配方案，同時采用結(jié)合面向設(shè)備優(yōu)先級的貪心策略的粒子群算法優(yōu)化提出的貪心算法。

朱新峰等人[8]基于“分治”的思想，提出了一種考慮用戶綜合需求的動態(tài)資源分配策略，進行計算資源和頻譜資源的分配以尋求吞吐量和時延性能方面的提升。Ning等人[9]在智能車聯(lián)網(wǎng)中構(gòu)建了一個三層卸載框架，以在滿足用戶延遲約束的同時最大程度地降低總體能耗，提出了一種基于深度強化學(xué)習(xí)的方案來解決優(yōu)化問題。劉斐等人[10]分析了邊緣計算服務(wù)器容限閾值和車輛密度對平均等待時延和卸載成功率的影響。

上述文獻大多考慮計算卸載過程中資源分配、設(shè)備能耗及傳輸成本問題，但對于任務(wù)具體卸載策略研究較少。本文通過采用“車-邊-云”協(xié)同卸載網(wǎng)絡(luò)架構(gòu)，并采用粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法對卸載系數(shù)和任務(wù)分配系數(shù)求解，得到最佳卸載方案，實現(xiàn)車輛卸載時延最小化。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

在車聯(lián)網(wǎng)中，本文選取一個由車輛、移動邊緣設(shè)備、云組成的三層網(wǎng)絡(luò)架構(gòu)，其架構(gòu)如圖1所示。該車聯(lián)網(wǎng)架構(gòu)由終端車輛端、MEC邊緣計算服務(wù)器以及云服務(wù)器組成。終端車輛可以與其他設(shè)備進行無線通信。MEC邊緣計算服務(wù)器由固定邊緣節(jié)點和移動邊緣節(jié)點組成，移動邊緣節(jié)點由用戶終端附近的帶有可用計算資源的移動車輛以及專門部署的移動服務(wù)器車輛組成，固定邊緣節(jié)點由用戶附近的帶有MEC功能的路側(cè)單元(Road Site Unit，RSU)以及部署了MEC設(shè)備的基站組成，其中邊緣節(jié)點的計算能力各不相同，且固定邊緣節(jié)點的計算能力強于移動邊緣節(jié)點。中心云服務(wù)器有強大的計算、存儲和網(wǎng)絡(luò)資源，可進行快速的任務(wù)處理。

圖1 車聯(lián)網(wǎng)網(wǎng)絡(luò)架構(gòu)圖

考慮將傳統(tǒng)的RSU或基站作為一個接入點為車輛提供網(wǎng)絡(luò)接入，但不進行計算卸載。假設(shè)在單向行駛的道路上有一終端車輛需要將一個計算密集型任務(wù)S進行卸載，該任務(wù)由云服務(wù)器、邊緣節(jié)點、車輛本地CPU三者聯(lián)合共同卸載。假設(shè)該任務(wù)可以按任意比例劃分成多個子任務(wù)，子任務(wù)之間不存在重疊。假設(shè)卸載θS至MEC邊緣節(jié)點，那么剩余任務(wù)總量為(1-θ)S,u(1-θ)S表示卸載至云服務(wù)器的任務(wù)大小，那么剩余任務(wù)(1-θ)(1-u)S在車輛終端CPU進行計算。其中，θ表示卸載至邊緣計算的卸載系數(shù)，u表示卸載至云計算的卸載系數(shù)。設(shè)完成計算任務(wù)下的CPU周期數(shù)為C=aD，其中，a表示計算任務(wù)的計算復(fù)雜度，任務(wù)不同，計算復(fù)雜度就不同(例如對同一個視頻，可以有剪輯、去噪、去水印等不同復(fù)雜度的操作)；D表示任務(wù)的輸入數(shù)據(jù)大小[11]。因此，計算任務(wù)的總時延包括本地計算時延、邊緣計算時延、云計算時延。

1.2 計算模型

假設(shè)有g(shù)個移動邊緣節(jié)點，r個固定邊緣節(jié)點。移動邊緣節(jié)點和終端車輛都在同一個接入點RSU的覆蓋范圍內(nèi)，移動邊緣節(jié)點的坐標(biāo)隨機分布在50 m×200 m的道路上。di,dot為終端車輛到邊緣節(jié)點的距離，di,c為終端車輛與遠端云的距離。假設(shè)移動邊緣節(jié)點的坐標(biāo)為{(m1,n1),(m2,n2),…,(mg,ng)}，接入點的坐標(biāo)為(mdot,ndot)，則車輛i與接入點的距離公式可表示為

(1)

車輛與MEC服務(wù)器之間是通過LTE- Advanced無線直連的方式進行通信的，車輛上傳鏈路的信道被認為是頻率平坦型快衰落的瑞利信道。參考文獻[12]，則車輛i至接入點傳輸速度為

(2)

接入點至車輛i傳輸速度為

(3)

終端車輛至遠端云的傳輸速度為

(4)

式中：Bi,dot、Bdot,i為車輛i與接入點之間的帶寬，Bv,c為車輛與云端的帶寬，Pi和Pdot為車輛i和接入點的傳輸功率，N0表示高斯白噪聲功率，h表示信道衰落因子，δ表示路徑損耗常數(shù)。

1.2.1 MEC計算時延

假設(shè)總?cè)蝿?wù)為S，卸載至MEC邊緣節(jié)點的計算的任務(wù)為θS，任務(wù)θS先到達接入點，再由接入點將任務(wù)分配至各固定邊緣節(jié)點和各移動邊緣節(jié)點，可求得終端車輛至接入點的傳輸時延可表示為

(5)

接入點分配給移動邊緣節(jié)點的任務(wù)為βiθS，βi表示卸載至邊緣計算中單個固定邊緣節(jié)點的任務(wù)分配系數(shù)，所以移動邊緣邊緣節(jié)點執(zhí)行時延包括接入點將任務(wù)傳輸給移動邊緣節(jié)點的傳輸時延和移動邊緣節(jié)點自身處理時延，所以移動邊緣計算節(jié)點的執(zhí)行時延為

(6)

同理，固定邊緣節(jié)點的執(zhí)行時延為

(7)

邊緣節(jié)點執(zhí)行時延為各邊緣節(jié)點執(zhí)行時延的最大值，因為分配給各邊緣節(jié)點的任務(wù)不重疊，獨立處理，因此邊緣結(jié)點執(zhí)行時延為

(8)

所以邊緣計算總時延為終端車輛至接入點的傳輸時延和邊緣結(jié)點執(zhí)行時延之和為

(9)

運算結(jié)果的回傳時延可忽略不計。

1.2.2 云計算時延

(10)

(11)

所以云計算的總時延為

(12)

運算結(jié)果的回傳時延也可忽略不計。

1.2.3 本地終端處理時延

由上節(jié)可得，由終端車輛計算的計算任務(wù)為(1-θ)(1-u)S，可得車輛終端計算時延為

(13)

基于上述三部分的時延分析，總時延取各部分時延最大值，所以總時延可表示為Tt=max{TL,TC,TM}，即

(14)

所以時延最優(yōu)化模型為

(15)

s.t. 0≤u≤1，

0≤θ≤1，

0≤βi≤1，

0≤βj≤1。

由于u、θ、βi、βj均為變量，為了求得時延最小，必須求出一組最優(yōu)的u、θ、βi、βj?？蓪⑿遁d系數(shù)和任務(wù)分配系數(shù)定義為一個(g+r+2)維的向量X=(x1,x2,…,xg,xg+1,…,xg+r,xg+r+1,xg+r+2)，其中，g為移動邊緣節(jié)點個數(shù)，r為固定邊緣節(jié)點個數(shù)，(x1,x2,…,xg)為各移動節(jié)點任務(wù)分配系數(shù)βi，(xg+1,…,xg+r)為固定邊緣節(jié)點分配系數(shù)βi，xg+r+1表示卸載系數(shù)θ，xg+r+2表示卸載系數(shù)u，因此總時延公式的求解可以轉(zhuǎn)化為對向量X的求解。于是總時延表達式可寫為

(16)

s.t. C1:0≤xi≤1,1≤i≤g+r+2，

式中：X∈J，J為可行解的搜索范圍，C1表示不管是卸載系數(shù)還是邊緣節(jié)點分配系數(shù)的范圍在(0,1)之間，C2表示邊緣節(jié)點中任務(wù)的分配系數(shù)之和為1。

2 基于粒子群算法的任務(wù)卸載策略

2.1 基本PSO算法

粒子群優(yōu)化算法的基本概念源于對鳥群捕食的研究。PSO中，優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱為粒子。假定在D維搜索空間中，由M個粒子組成一個種群進行“飛行”(即搜索)，第i個粒子的位置表示為Xi=(xi1,xi2,…,xiD)，第i個粒子的速度表示為Vi=(vi1,vi2,vi3,…,vid)，每個粒子在飛行過程中搜索到的最好位置稱為個體極值pbest=(pi1,pi2,…,piD)，整個種群搜索到的最好位置稱為全局極值gbest=(gi1,gi2,…,giD)，粒子搜索過程中的速度和位置更新公式如下：

vid=wvid+τ1η1(pid-xid)+τ2η2(gid-xid) ，

(17)

xid=xid+vid。

(18)

式中：1≤i≤M,1≤d≤D;τ1、τ2為學(xué)習(xí)因子，通常設(shè)置為2；η1、η2是[0,1]之間均勻分布的隨機數(shù)；w為慣性權(quán)重；vid∈[-vmax,vmax]，其中vmax是預(yù)先給定的最大速度。公式(17)中等號右邊第一部分表示粒子當(dāng)前狀態(tài);等號右邊第二部分是粒子的自我學(xué)習(xí)部分，粒子對搜索歷史過程的思考，引導(dǎo)個體最優(yōu)位置方向運動;等號右邊第三部分是社會認知部分，粒子群體通過相互交流向全局最優(yōu)方向運動。

2.2 解決等式約束問題的PSO算法(FS-PSO)

基本的PSO算法中沒有處理約束條件的機制。通常，粒子群算法求解有等式約束的優(yōu)化問題的方法是將一個約束變?yōu)閮蓚€不等式約束，但很難隨機產(chǎn)生可行解，導(dǎo)致收斂速度慢。為了解決本文時延公式中變量的約束條件，參考文獻[13]和文獻[14]的等式約束處理方法，可對本文的優(yōu)化問題進行轉(zhuǎn)化，從而求出最優(yōu)解。因此，定義適應(yīng)度函數(shù)為

(19)

式中：Ttmax為群體中最差可行個體的適應(yīng)度值，

(20)

式中：δ是較小的整數(shù)。

FS-PSO粒子群算法的具體實現(xiàn)過程如下:

Step1 粒子群初始化：規(guī)定最大迭代數(shù)T；給定群體規(guī)模N，在可行域中隨機產(chǎn)生每個粒子的位置Xi,規(guī)定速度為Vi。

Step2 通過上述的適應(yīng)度函數(shù)，計算每個粒子適應(yīng)度值Fit(Xi)。

Step3 計算每個粒子的個體最優(yōu)位置pbest和全局最優(yōu)位置gbest。

Step4 根據(jù)公式(21)更新粒子的速度和位置。

假設(shè)Qn為等式約束(20)的系數(shù)矩陣，r(Qn)是矩陣Qn的秩，Pn為系數(shù)矩陣Qn的階梯型矩陣，在階梯形矩陣中選取r(Qn)個線性無關(guān)的列，將這些列的序號集合記為(m1,m2,…,mr(Qn))，未被選中的列的序號集合記為(q1,q2,…,qn-r(Qn))，通過公式(21)來更新速度向量和位置向量部分分量的值。

vit=wvit+τ1η1(pit-xit)+τ2η2(git-xit) 。

(21)

式中：t=q1,q2,…,qn-r(Qn),xit=xit+vit，t=q1,q2,…,qn-r(Qn)。

剩下的分量值通過等式方程組求出。

Step5 對粒子的個體極值和全局極值進行更新。

Step6 若達到終止條件，即最大迭代次數(shù)，算法輸出全局最佳位置，該位置就是本文的最優(yōu)卸載策略，進而求出最優(yōu)時延，若沒有達到終止條件，則將更新后的粒子轉(zhuǎn)向Step 2。

3 仿真與分析

為了驗證本文所提提出的架構(gòu)及卸載策略的時延性能，將所提的策略與其他幾種策略進行比較。

(1)“車-邊-云”協(xié)同卸載(本文卸載策略)：終端車輛卸載部分計算任務(wù)至邊緣節(jié)點(固定邊緣節(jié)點和移動邊緣節(jié)點)和云端處理，剩余計算任務(wù)由終端車輛本地處理。

(2)“車-邊”協(xié)同卸載：終端車輛僅卸載部分計算任務(wù)，由邊緣節(jié)點進行計算，剩余任務(wù)由終端車輛本地處理。

(3)僅邊緣節(jié)點卸載(僅邊)：終端車輛卸載全部的計算任務(wù)，全部任務(wù)由邊緣節(jié)點處理。

(4)僅車本地卸載(僅車)：終端車輛直接進行本地任務(wù)執(zhí)行，不進行計算卸載。

最后將本文采用的改進可解等式約束的粒子群優(yōu)化算法(FS-PSO)與貪婪算法(Greedy Algorithm)、遺傳算法(Genetic Algorithm)進行比較。PSO算法和遺傳算法都屬于全局優(yōu)化算法，從隨機解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度來評價解的品質(zhì)。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

3.1 仿真參數(shù)設(shè)置

表1給出了相關(guān)仿真參數(shù)設(shè)置。

表1 相關(guān)仿真參數(shù)

3.2 仿真結(jié)果分析

圖2描述了在輸入數(shù)據(jù)大小影響下各策略的時延性能，假設(shè)計算復(fù)雜度為6 800 cycle/B。可以看出隨著輸入數(shù)據(jù)的增加。任務(wù)卸載所產(chǎn)生的時延也隨之增加，這是因為隨著數(shù)據(jù)大小的增加，計算過程中傳輸時延以及處理時延都會有所增加。本文采用的“車-邊-云“卸載策略在時延方面明顯優(yōu)于其他卸載策略，與僅車輛終端計算相比減少約2.6 s。這是因為本文策略將車輛、MEC設(shè)備、云三部分資源充分調(diào)度，且云的計算資源強大，減少了處理時延。相較與其他三種策略的時延，所提出的策略時延性能分別提升了32.6%、45.3 %和88.5%。

圖2 不同輸入數(shù)據(jù)大小各策略時延的對比

圖3顯示了不同復(fù)雜度下各策略時延的大小，對輸入的計算任務(wù)可以有不同的處理操作，就會產(chǎn)生不同的計算復(fù)雜度。假設(shè)輸入數(shù)據(jù)大小為580 kB，可以看出，“僅邊”卸載策略在復(fù)雜度趨向于0時，仍然有一定的傳輸時延。這是因為卸載了全部的計算任務(wù)至邊緣節(jié)點進行計算，有一定的傳輸時延。當(dāng)計算度復(fù)雜度低于2 000 cycle/B時，“車-邊-云”協(xié)同卸載策略時延高于“車-邊”卸載時延和“僅邊”卸載時延。這是因為計算復(fù)雜度較低時，云端處理時延所帶來的時延優(yōu)勢不能抵消掉任務(wù)傳輸至云的傳輸時延較長問題。隨著計算復(fù)雜度的增加，任務(wù)卸載的時延也隨之增加，當(dāng)計算復(fù)雜度超過2 000 cycle/B時，本文所提的卸載策略產(chǎn)生的時延是最小的。

圖3 不同復(fù)雜度下各策略時延的對比

圖4給出了不同策略在隨機計算復(fù)雜度和隨機數(shù)據(jù)大小下的時延性能對比，其中，假設(shè)輸入數(shù)據(jù)大小的范圍為375～425 kB，CPU周期范圍為1 950～2 050 Mcycle。可以看出“車-邊-云”卸載策略在車輛隨機任務(wù)下可以更地好降低任務(wù)完成時延，10個隨機任務(wù)下幾個策略的平均時延分別為0.189 s、0.252 s、0.298 s、1.306 s且與其他三種策略相比時延分別提升了21.4%、36.6%、85.5%，證明了所提策略的有效性。

圖4 隨機數(shù)據(jù)大小和隨機CPU周期數(shù)下的時延性能對比

圖5描述了相同策略下本文的改進算法與貪婪算法和遺傳算法的時延性能對比?？傮w來說，隨著計算復(fù)雜度的增加，“車-邊-云”卸載策略中基于粒子群優(yōu)化算法的任務(wù)完成時間一直處于最低狀態(tài)，其次是貪婪算法，時延最大的是遺傳算法，這說明粒子群算法比其他兩種算法能夠更好地縮短用戶完成時間，提高用戶體驗。當(dāng)計算復(fù)雜度為8 000 cycle/B時，三種算法的時延分別0.216 2 s、0.296 3 s、0.339 3 s，說明粒子群優(yōu)化算法對卸載任務(wù)分配更加合理。

圖5 相同策略下不同算法時延性能對比

4 結(jié)束語

本文提出了車聯(lián)網(wǎng)中基于本地、邊緣MEC設(shè)備和云服務(wù)器共同卸載的卸載策略，實現(xiàn)了車、MEC設(shè)備、云三方面的資源調(diào)度。此外，本文采用了改進的粒子群算法可解決本文時延優(yōu)化問題的等式約束。數(shù)值結(jié)果表明，所提出的卸載策略可以提高任務(wù)執(zhí)行效率，降低時延，實現(xiàn)了對車載任務(wù)的最優(yōu)卸載。但本文僅考慮了單個任務(wù)，未考慮車輛任務(wù)的多樣性；也僅考慮車輛在理想情況下的任務(wù)卸載，未考慮無線通信鏈路的不穩(wěn)定性，不符合車聯(lián)網(wǎng)的實際情形，因此后續(xù)將考慮多任務(wù)卸載以及多任務(wù)情況下任務(wù)的優(yōu)先級，按任務(wù)重要度進行卸載，并研究車輛在非理想鏈路情況下的可靠性傳輸。