車聯(lián)網(wǎng)場景下移動邊緣計算協(xié)作式資源分配策略*

劉 斐，曹鈺杰，章國安

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

0 引 言

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

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

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

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

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

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

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

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

2 問題建模

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

λ=λ1+λ2。

(1)

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

(2)

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

(3)

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

(4)

式中：0≤i≤N+s。

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

(5)

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

(6)

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

(7)

(8)

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

(9)

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

(10)

本文將所提方案建模為有約束的整數(shù)優(yōu)化問題，如公式(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)，計算出平均隊長、任務(wù)卸載成功率、單位時間總代價；

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

(7) end if；

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

(10)end for

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

3 性能仿真與分析

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

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

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

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

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

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

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

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

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

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

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

圖5 車輛密度對平均等待時延的影響

圖6 車輛密度對卸載成功率的影響

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

表2 不同方案下的對比

4 結(jié)束語

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