車聯網場景下移動邊緣計算協作式資源分配策略*

劉 斐，曹鈺杰，章國安

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

0 引 言

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

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

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

1 系統模型及方案

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

圖1 雙向4車道系統模型

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

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

2 問題建模

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

λ=λ1+λ2。

(1)

M/M/s模型下系統負荷水平ρ為

(2)

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

(3)

記Pi表示排隊系統的狀態概率:

(4)

式中：0≤i≤N+s。

根據正則性條件，即

(5)

在ρ≠1的情況下，計算出狀態概率P0:

(6)

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

(7)

(8)

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

(9)

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

(10)

本文將所提方案建模為有約束的整數優化問題，如公式(11)：

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

s.t.

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

(11)

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

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

(4)根據公式(7)、(9)、(10)，計算出平均隊長、任務卸載成功率、單位時間總代價；

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

(7) end if；

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

(10)end for

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

3 性能仿真與分析

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

表1 仿真參數設置

3.1 單服務器和多服務器下的平均等待時延

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

圖2 多服務器和單服務器下不同系統負荷對平均等待時延的影響

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

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

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

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

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

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

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

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

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

表2 不同方案下的對比

4 結束語

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