劉 斐，曹鈺杰，章國(guó)安

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226019)

0 引 言

隨著智能交通的快速發(fā)展、車輛數(shù)目的增加，產(chǎn)生了大量的卸載任務(wù)請(qǐng)求，導(dǎo)致服務(wù)器處理任務(wù)請(qǐng)求慢、效率差。以往的云計(jì)算模式下，將處理消息的工作部署在云端導(dǎo)致處理消息慢，數(shù)據(jù)傳輸滯后，占用高帶寬資源。移動(dòng)邊緣計(jì)算(Mobile Edge Computing，MEC)具有低時(shí)延和高計(jì)算能力，為用戶提供快速而強(qiáng)大的計(jì)算能力、高效的卸載效率等，滿足時(shí)延、帶寬、計(jì)算的服務(wù)需求。MEC計(jì)算卸載技術(shù)不僅減輕了核心網(wǎng)的壓力，而且降低了因傳輸帶來(lái)的時(shí)延。目前車聯(lián)網(wǎng)的發(fā)展重點(diǎn)已經(jīng)從核心網(wǎng)轉(zhuǎn)向邊緣網(wǎng)，把原有集中式的云計(jì)算平臺(tái)分布式部署在無(wú)線接入網(wǎng)絡(luò)的邊緣，可以大幅減少任務(wù)上傳至云服務(wù)器的傳輸計(jì)算時(shí)延，給用戶帶來(lái)低時(shí)延、高質(zhì)量的服務(wù)體驗(yàn)。

國(guó)內(nèi)外大量的研究學(xué)者對(duì)移動(dòng)邊緣計(jì)算進(jìn)行了深入的研究。文獻(xiàn)[1]針對(duì)移動(dòng)邊緣計(jì)算中有限的資源，通過(guò)在線學(xué)習(xí)的方法最小化任務(wù)的時(shí)延。文獻(xiàn)[2]為了方便處理云計(jì)算的任務(wù)負(fù)載的動(dòng)態(tài)變化，以經(jīng)濟(jì)模型為基礎(chǔ)，提出了一個(gè)云計(jì)算資源提供者的聯(lián)邦體系結(jié)構(gòu)，基于經(jīng)濟(jì)模型的聯(lián)邦云以聯(lián)邦資源調(diào)度的方式來(lái)提供資源利用率，節(jié)約云計(jì)算運(yùn)營(yíng)成本，增強(qiáng)了云計(jì)算盈利能力。文獻(xiàn)[3]針對(duì)MEC服務(wù)器的副本，分析了收入、成本和利潤(rùn)，提出了MEC自適應(yīng)復(fù)制算法，可以根據(jù)每個(gè)時(shí)間間隔動(dòng)態(tài)調(diào)節(jié)副本。采用了自適應(yīng)算法將請(qǐng)求轉(zhuǎn)發(fā)到相鄰MEC服務(wù)器中的副本，平衡MEC服務(wù)器的負(fù)載，此方案可以有效地縮短平均響應(yīng)時(shí)間 并提高數(shù)據(jù)包的QoS，以獲得更好的利潤(rùn)。文獻(xiàn)[4]將移動(dòng)邊緣計(jì)算系統(tǒng)內(nèi)的隨機(jī)請(qǐng)求建模為M/M/1到達(dá)服務(wù)器的任務(wù)流，優(yōu)化任務(wù)分配給服務(wù)器的平均響應(yīng)時(shí)間，通過(guò)貪婪算法和禁忌算法驗(yàn)證可以比隨機(jī)分配算法減少20%～30%的平均響應(yīng)時(shí)間。文獻(xiàn)[5]針對(duì)計(jì)算資源在邊緣計(jì)算中易受限制的問(wèn)題，提出兩個(gè)數(shù)據(jù)中心協(xié)作共享的方案，該方案可以有效的降低任務(wù)請(qǐng)求的阻塞概率和服務(wù)時(shí)延。文獻(xiàn)[6]采用馬爾科夫決策過(guò)程方法來(lái)處理任務(wù)是在本地執(zhí)行還是MEC服務(wù)器執(zhí)行，分析每個(gè)任務(wù)的平均延遲和移動(dòng)設(shè)備的平均功耗，制定了一個(gè)功率約束延遲最小化問(wèn)題，并提出了一種高效的一維搜索算法來(lái)尋找最優(yōu)的任務(wù)調(diào)度策略，降低了平均執(zhí)行延遲。文獻(xiàn)[7]采用云計(jì)算和邊緣計(jì)算協(xié)作的方式來(lái)提升邊緣云的效率，提出聯(lián)合通信和計(jì)算資源分配優(yōu)化方案，和傳統(tǒng)方案相比獲得了更好的時(shí)延性能。文獻(xiàn)[8]在云計(jì)算和移動(dòng)邊緣計(jì)算協(xié)作的基礎(chǔ)上，提出計(jì)算卸載和資源分配協(xié)同優(yōu)化的方案，設(shè)計(jì)了一種分布式計(jì)算卸載和資源分配優(yōu)化算法，得到非凸問(wèn)題的最優(yōu)解，可以有效地提高系統(tǒng)的實(shí)用性和計(jì)算時(shí)間性能。文獻(xiàn)[9]針對(duì)服務(wù)器集群的情況，提出三種服務(wù)器負(fù)載方案，即沒(méi)有共享負(fù)載、隨機(jī)共享、最小負(fù)載共享，將任務(wù)流請(qǐng)求轉(zhuǎn)發(fā)至負(fù)載最小的服務(wù)器可以降低任務(wù)不被處理的概率，同時(shí)也可以減少任務(wù)被處理所耗費(fèi)的時(shí)間。文獻(xiàn)[10]提出基于能效的聯(lián)合資源分配和功率控制的D2D中繼算法，首先對(duì)等效D2D中繼鏈路進(jìn)行資源分配，減小算法復(fù)雜度的同時(shí)使得D2D鏈路對(duì)蜂窩鏈路產(chǎn)生的干擾最?。蝗缓笠再Y源分配結(jié)果和功率控制算法為依據(jù)進(jìn)行中繼選擇。文獻(xiàn)[11]提出一種在MEC服務(wù)器協(xié)作空間中的資源分配方案，設(shè)置一個(gè)MEC核心服務(wù)器，為其他服務(wù)器存儲(chǔ)、提供最新的資源信息，根據(jù)實(shí)際應(yīng)用，優(yōu)化卸載任務(wù)的傳輸時(shí)延。文獻(xiàn)[12]在MEC架構(gòu)下設(shè)想了一個(gè)基于WiFi的多用戶模型，致力于解決任務(wù)分配與資源分配問(wèn)題，提出時(shí)延滿足約束下移動(dòng)設(shè)備的能耗最小的方案，NS3仿真得到所提方法在能耗和任務(wù)完成時(shí)延優(yōu)于其他策略。文獻(xiàn)[13]提出一種新型的云無(wú)線接入結(jié)構(gòu)，聯(lián)合優(yōu)化卸載決策、無(wú)線和計(jì)算資源分配來(lái)最大化運(yùn)營(yíng)商盈利，將此優(yōu)化問(wèn)題解耦為兩個(gè)子優(yōu)化問(wèn)題，并分別迭代得到次優(yōu)解，仿真表明此方法可以以較低的復(fù)雜度為運(yùn)營(yíng)商實(shí)現(xiàn)較高的盈利增加。文獻(xiàn)[14]在協(xié)作MEC下提出一種聯(lián)合計(jì)算和高可靠低時(shí)延通信(The Ultra Reliable Low Latency Communication，URLLC)資源分配策略，對(duì)原優(yōu)化問(wèn)題進(jìn)行解耦得到兩個(gè)子優(yōu)化問(wèn)題，證明此方案下的性能比非合作MEC環(huán)境更優(yōu)越。文獻(xiàn)[15]為了降低車聯(lián)網(wǎng)中計(jì)算任務(wù)的時(shí)延和系統(tǒng)成本，提出一種多平臺(tái)卸載智能資源分配算法，仿真表明該算法實(shí)現(xiàn)了時(shí)延成本的顯著降低，節(jié)省系統(tǒng)總成本達(dá)80%。

不同于以上文獻(xiàn)，本文將多服務(wù)器排隊(duì)模型應(yīng)用于移動(dòng)邊緣計(jì)算這樣復(fù)雜的環(huán)境，設(shè)置多個(gè)邊緣計(jì)算服務(wù)器相互協(xié)作，盡可能地降低任務(wù)卸載時(shí)的平均等待時(shí)延，實(shí)現(xiàn)任務(wù)高效卸載。為了實(shí)現(xiàn)這一目的，本文分析邊緣計(jì)算服務(wù)器容限閾值和車輛密度對(duì)平均等待時(shí)延和卸載成功率的影響，提出在邊緣計(jì)算服務(wù)器容限閾值、卸載成功率滿足約束的條件下，多個(gè)邊緣計(jì)算服務(wù)器相互協(xié)作的資源分配方案，設(shè)計(jì)一種最小代價(jià)算法，得到卸載任務(wù)的平均等待時(shí)延以及單位時(shí)間總代價(jià)。

1 系統(tǒng)模型及方案

本文設(shè)想一個(gè)雙向4車道的高速公路模型，該模型包括邊緣計(jì)算服務(wù)器、路邊單元(Road Side Unit,RSU)、車輛。道路旁的路邊單元等距離分布，其分布間距為D，RSU的覆蓋半徑為D/2。每個(gè)路邊單元均通過(guò)有線電纜連接著邊緣計(jì)算服務(wù)器，同樣，邊緣計(jì)算服務(wù)器的覆蓋半徑亦為D/2。有線電纜的連接可認(rèn)為通信帶寬非常大，故而可以忽略路邊單元和邊緣計(jì)算服務(wù)器之間的傳輸時(shí)延。模型如圖1所示。

圖1 雙向4車道系統(tǒng)模型

將M/M/1和M/M/s的排隊(duì)模型運(yùn)用于任務(wù)卸載中，卸載任務(wù)到達(dá)邊緣計(jì)算服務(wù)器后以隊(duì)列的形式保存，遵循先到達(dá)先服務(wù)的準(zhǔn)則，分析該模型下的性能指標(biāo)。車輛的到達(dá)時(shí)間間隔服從參數(shù)為λ的泊松分布，邊緣計(jì)算服務(wù)器處理任務(wù)的服務(wù)時(shí)間間隔服從參數(shù)為μ的負(fù)指數(shù)分布，本文假設(shè)每一輛車輛都有同樣大小的卸載任務(wù)要處理，而任務(wù)上傳至服務(wù)器的過(guò)程可以看作是車輛到達(dá)的子過(guò)程[16]，即任務(wù)到達(dá)服務(wù)器的時(shí)間間隔也服從參數(shù)為λ的泊松分布。定義系統(tǒng)負(fù)荷水平ρ=λ/μ，表示服務(wù)被占用的平均概率，即邊緣計(jì)算服務(wù)器的繁忙程度[17]。以任務(wù)的平均等待時(shí)延和任務(wù)的卸載成功率作為研究性能的指標(biāo)，分別表示任務(wù)到達(dá)邊緣計(jì)算服務(wù)器到被成功處理所需的平均等待時(shí)間和任務(wù)被邊緣計(jì)算服務(wù)器成功處理并接受服務(wù)的概率。

首先比較在同一路段設(shè)置1個(gè)和3個(gè)邊緣計(jì)算服務(wù)器，計(jì)算和仿真得出平均等待時(shí)延的理論值和仿真值。接著，進(jìn)一步選擇M/M/s/N/∞模型[18]，其中N表示邊緣計(jì)算服務(wù)器的容限大小，當(dāng)隊(duì)列中任務(wù)等待隊(duì)長(zhǎng)(Lq)超過(guò)N時(shí)，新任務(wù)請(qǐng)求將會(huì)被拒絕處理，∞表示任務(wù)的總數(shù)不受限制，并且N≥s，本文后續(xù)提到M/M/s模型即代表M/M/s/N/∞模型。然后給邊緣計(jì)算服務(wù)器容限設(shè)置不同閾值T，在不同不同系統(tǒng)負(fù)荷水平ρ下比較分析設(shè)置的閾值高低對(duì)任務(wù)的平均等待時(shí)延和任務(wù)卸載成功載率的影響。進(jìn)一步地，考慮在不同邊緣計(jì)算服務(wù)器個(gè)數(shù)下比較分析車輛密度對(duì)任務(wù)的平均等待時(shí)延和任務(wù)卸載成功率的影響。最后，引入代價(jià)因子a和b，構(gòu)造代價(jià)函數(shù)f(s)，提出在邊緣計(jì)算服務(wù)器容限閾值和任務(wù)卸載成功率滿足約束的條件下，多個(gè)邊緣計(jì)算服務(wù)器相護(hù)協(xié)作的資源分配方案，通過(guò)單位時(shí)間總代價(jià)指標(biāo)優(yōu)化邊緣計(jì)算服務(wù)器個(gè)數(shù)，設(shè)計(jì)了最小代價(jià)算法求解該方案下的單位時(shí)間總代價(jià)和任務(wù)平均等待時(shí)延，并將所提方案和已有方案的性能進(jìn)行對(duì)比分析。

2 問(wèn)題建模

雙向4車道高速公路模型下，假設(shè)兩個(gè)相向車道下的車輛到達(dá)時(shí)間間隔分別服從參數(shù)為λ1和λ2的泊松分布，那么同向兩車道的車輛的到達(dá)時(shí)間間隔分布服從0.5λ1和0.5λ2的泊松分布。每車道的車輛產(chǎn)生的任務(wù)之間相互獨(dú)立，每個(gè)任務(wù)到達(dá)服務(wù)器的時(shí)間間隔隨機(jī)，多個(gè)服務(wù)器處理任務(wù)的服務(wù)時(shí)間間隔也是相互獨(dú)立且每臺(tái)邊緣計(jì)算服務(wù)器的服務(wù)率都是μ，4車道下總的車輛到達(dá)率[19]為λ：

λ=λ1+λ2。

(1)

M/M/s模型下系統(tǒng)負(fù)荷水平ρ為

(2)

定義車輛密度λu為每邊緣計(jì)算服務(wù)器范圍的車輛數(shù)，vu為車輛每秒內(nèi)經(jīng)過(guò)邊緣計(jì)算服務(wù)器覆蓋范圍數(shù)，則在M/M/s排隊(duì)模型中的每一車道的λ′滿足公式(3)。需要注意的是，此處車輛密度λu的單位是vehicle/D。

(3)

記Pi表示排隊(duì)系統(tǒng)的狀態(tài)概率:

(4)

式中：0≤i≤N+s。

根據(jù)正則性條件，即

(5)

在ρ≠1的情況下，計(jì)算出狀態(tài)概率P0:

(6)

[1-ρ(N-s+1)-(1-ρ)·(N-s+1)·ρ(N-s)]，

(7)

(8)

任務(wù)卸載成功率表示為任務(wù)被邊緣計(jì)算服務(wù)器成功處理并接受服務(wù)的概率，如公式(9)所示:

(9)

[1-ρ(N-s+1)-(1-ρ)·(N-s+1)·ρ(N-s)] 。

(10)

本文將所提方案建模為有約束的整數(shù)優(yōu)化問(wèn)題，如公式(11)：

[1-ρ(N-s+1)-(1-ρ)·(N-s+1)·ρ(N-s)]

s.t.

C1:N=T*,s≤T*；

(11)

(1)輸入：s、λ、μ、N、α、β、T*的值以及目標(biāo)函數(shù)f(s)；

(2)fors∈[1，T*]且s為整數(shù)；

(4)根據(jù)公式(7)、(9)、(10)，計(jì)算出平均隊(duì)長(zhǎng)、任務(wù)卸載成功率、單位時(shí)間總代價(jià)；

(6) 將滿足條件的f(s)存放于矩陣A中；

(7) end if；

(8)對(duì)矩陣A的元素排序，得到f(s*)；

(10)end for

最后，本文對(duì)所提算法做一個(gè)粗略的分析，通過(guò)一維遍歷搜索得到滿足約束條件的目標(biāo)值并用冒泡排序的方法對(duì)矩陣A內(nèi)的目標(biāo)值排序得到最優(yōu)f(s*)，使得本文算法復(fù)雜度大大降低，加之約束條件s≤T*的存在，進(jìn)一步降低了運(yùn)算時(shí)間，故而本文算法在最差的情況下整體的復(fù)雜度在O(n2)以下。

3 性能仿真與分析

本節(jié)將在上述模型下通過(guò)仿真來(lái)評(píng)估比較在不同系統(tǒng)參數(shù)下所提方案的性能，仿真分析是在Matlab R 2018b內(nèi)完成，參數(shù)取值參考文獻(xiàn)[2,4,11]，如表1所示。

表1 仿真參數(shù)設(shè)置

3.1 單服務(wù)器和多服務(wù)器下的平均等待時(shí)延

同一路段下設(shè)置1個(gè)和3個(gè)邊緣計(jì)算服務(wù)器，分別計(jì)算和仿真得到平均等待時(shí)延的理論值和仿真值，如圖2所示。在相同的系統(tǒng)負(fù)荷水平下，多個(gè)服務(wù)器下的平均等待時(shí)延性能優(yōu)于單服務(wù)器，隨著系統(tǒng)負(fù)荷逐漸增大，平均等待時(shí)延性能提升越明顯，故M/M/s模型更適應(yīng)移動(dòng)邊緣計(jì)算這樣復(fù)雜的環(huán)境，能夠提供更加高效的服務(wù)。

圖2 多服務(wù)器和單服務(wù)器下不同系統(tǒng)負(fù)荷對(duì)平均等待時(shí)延的影響

3.2 邊緣計(jì)算服務(wù)器容限的閾值對(duì)平均等待時(shí)延和任務(wù)卸載成功率的影響

在不同的系統(tǒng)負(fù)荷水平下，分析比較了邊緣計(jì)算服務(wù)器容限閾值對(duì)平均等待時(shí)延和卸載成功率的影響，如圖3和圖4所示。由圖3橫向比較可知，任務(wù)的平均等待時(shí)延性能和邊緣計(jì)算服務(wù)器容限閾值呈負(fù)相關(guān)，邊緣計(jì)算服務(wù)器容限的閾值減小時(shí)，更多的任務(wù)請(qǐng)求被拒絕處理，因此隊(duì)列的平均隊(duì)長(zhǎng)更小了，導(dǎo)致平均等待時(shí)延下降。例如，ρ=0.7時(shí)，邊緣計(jì)算服務(wù)器容限沒(méi)有閾值和閾值為5下的平均等待時(shí)延分別是0.861 3 s和0.328 8 s，降幅約62%；ρ=0.5時(shí)，平均等待時(shí)延分別是0.173 1 s和0.105 4 s，降幅約39%。由圖3縱向比較可知，系統(tǒng)負(fù)荷較高時(shí)的平均等待時(shí)延降幅大于較低的，系統(tǒng)負(fù)荷增大時(shí)，雖然任務(wù)請(qǐng)求數(shù)量隨之增加，但是在降低容限閾值的情況下，隊(duì)列中任務(wù)平均隊(duì)長(zhǎng)更低，故而平均等待時(shí)延性能曲線降幅大。根據(jù)圖4，T≥20時(shí)，不同系統(tǒng)負(fù)荷下的任務(wù)卸載成功率均是100%;T≤15時(shí)，任務(wù)卸載成功率出現(xiàn)下降，而且是系統(tǒng)負(fù)荷高的先下降。因此，平均等待時(shí)延性能的提升是在降低邊緣計(jì)算服務(wù)器容限閾值，犧牲部分的卸載成功率的前提下得到的。

圖3 閾值對(duì)平均等待時(shí)延的影響(s=3)

圖4 閾值對(duì)卸載成功率的影響(s=3)

3.3 車輛密度對(duì)平均等待時(shí)延和任務(wù)卸載成功率的影響

上文分析得到在邊緣計(jì)算服務(wù)器相同處理能力下，系統(tǒng)負(fù)荷水平影響著時(shí)延性能幅度的變化，車輛到達(dá)率與車輛密度相關(guān)，因此車輛密度也影響著平均等待時(shí)延和卸載成功率。接下來(lái)分析比較部署2、3、4個(gè)邊緣計(jì)算服務(wù)器且容限均為25，車輛密度對(duì)平均等待時(shí)延以及任務(wù)卸載成功率的影響，如圖5和圖6所示。由圖5橫向來(lái)看，車輛密度為5～10時(shí)，任務(wù)請(qǐng)求少且都可以被及時(shí)處理，故而平均等待時(shí)延很低；車輛密度在20～35時(shí)，由于車距突然超過(guò)安全駕駛距離，任務(wù)數(shù)增多，邊緣計(jì)算服務(wù)器內(nèi)等待處理的任務(wù)突增，平均等待時(shí)延突增；車輛密度超過(guò)50后，邊緣計(jì)算服務(wù)器已不能及時(shí)處理新的任務(wù)請(qǐng)求，大量任務(wù)請(qǐng)求會(huì)被拒絕，平均等待時(shí)延增加趨于平緩。根據(jù)圖6，車輛密度很小時(shí)，卸載成功率都是100%;車輛密度大于50后，任務(wù)的卸載成功率明顯下降；車輛密度為80時(shí)，s=2下的卸載成功率已不足50%。縱向來(lái)看，增加邊緣計(jì)算服務(wù)器個(gè)數(shù)，被拒絕處理的任務(wù)請(qǐng)求路由到空閑邊緣計(jì)算服務(wù)器等待處理，可以顯著提升平均等待時(shí)延性能和卸載成功率。因此,可以根據(jù)車輛密度設(shè)置邊緣計(jì)算服務(wù)器個(gè)數(shù)可以實(shí)現(xiàn)低時(shí)延需求和高卸載成功率。

圖5 車輛密度對(duì)平均等待時(shí)延的影響

圖6 車輛密度對(duì)卸載成功率的影響

3.4 本文所提方案與已有方案的性能比較

表2 不同方案下的對(duì)比

4 結(jié)束語(yǔ)

本文提出了一種滿足邊緣計(jì)算服務(wù)器容限閾值和任務(wù)卸載成功率約束條件下的多個(gè)邊緣計(jì)算服務(wù)器相互協(xié)作的資源分配方案，設(shè)計(jì)了最小代價(jià)算法求解相互協(xié)作邊緣計(jì)算服務(wù)器的具體個(gè)數(shù)以及所提方案下的單位時(shí)間總代價(jià)和任務(wù)平均等待時(shí)延。將本文所提方案與已有方案進(jìn)行比較，結(jié)果表明，本文所提方案的單位時(shí)間總代價(jià)有所降低，卸載任務(wù)的平均等待時(shí)延性能得到提升。本文算法有一定的實(shí)用價(jià)值，可以在降低單位時(shí)間總代價(jià)的基礎(chǔ)上實(shí)現(xiàn)時(shí)延性能的大幅提升，滿足現(xiàn)實(shí)生活中的需求。未來(lái)工作中將考慮任務(wù)上傳至邊緣計(jì)算服務(wù)器的能量消耗，進(jìn)一步考慮在滿足任務(wù)時(shí)延需求的限制下最小化能量消耗，為車聯(lián)網(wǎng)的發(fā)展提供更大的幫助。