用于智能礦山移動邊緣計算的二維動態匹配算法

趙端，申澄洋，史新國，劉柯

（1.中國礦業大學 礦山互聯網應用技術國家地方聯合工程實驗室，江蘇 徐州 221116；2.中國礦業大學 信息與控制工程學院，江蘇 徐州 221116；3.淄博礦業集團有限責任公司 信息中心，山東 淄博 255299）

0 引言

近年來，煤炭行業的高質量發展目標對智能礦山建設提出了更高要求，少人、無人成為煤礦智能化下一階段的重要目標。在智能礦山發展初期，煤礦井下復雜通信環境導致的通信設備傳輸速率和帶寬不足的問題長期以來未能實現本質突破。云計算和5G 技術以其超高數據速率、超低延遲和超大規模接入的優點，為結合邊緣計算的智能礦山建設提供了解決方案[1]。

云計算技術可以較好地解決任務處理延遲高、速度慢等問題，提高用戶服務質量與用戶體驗質量[2]。但從用戶到云端的物理距離較遠，會造成一定的傳輸延遲和較慢的響應速度，盡管隨著5G 技術的發展，這種延遲可以被縮短到很低的數量級，但依然無法滿足部分延遲敏感任務如虛擬現實、實時軌跡預測等的延遲約束。為了緩解延遲約束問題，邊緣計算被提出。邊緣計算是將具有一定計算能力的計算設備和常用數據存儲設備部署在靠近用戶的邊緣端，從而使用戶任務處理延遲大大降低，達到了性能和延遲的均衡。因此，邊緣計算在結合物聯網和信息物理系統的場景中獲得大量應用[3]。

智能礦山建設中，邊緣計算服務能夠支持煤礦工業多類應用達到智能化水平，如高精度實時定位、遠程生產實時控制、煤礦井下智能巡檢和安全防護等。雖然邊緣服務器能夠較好地完成邊緣側移動用戶遷移來的任務，但通常邊緣服務器是輕量級的，其算力與云計算相比較為有限，如果某一區域內移動用戶任務量在短時間內激增，會導致任務出現排隊現象，從而造成延遲，影響服務質量，甚至無法滿足延遲約束。因此，目前在1 個區域內通常部署多個邊緣服務器，以滿足該區域內可能出現的任務擁塞。然而，移動用戶生成任務后往哪個邊緣服務器遷移的決策，以及使用何種功率進行任務數據包發送的選擇，均會大大影響整個網絡的整體延遲、任務完成率及能耗，因此，基于多對多匹配模型的計算遷移問題（Computing Offloading Problem，COP）成為目前移動邊緣計算（Mobile Edge Computing，MEC）的研究熱點。近年來，國內外學者開展了針對MEC 中COP 的研究。文獻[4]提出了一種MEC 多跳卸載算法，以降低區域中移動用戶整體能耗。文獻[5]提出了一種MEC 和無線能量傳輸技術結合的優化方法，在無線供電的多用戶MEC 系統中通過對接入點（Access Point，AP）的能量傳輸波束形成、用戶的中央處理單元（CPU）頻率及用戶之間的時間分配進行聯合優化來提高MEC 性能，使AP 總能量消耗達到最小。文獻[6]提出了一種基于邊緣計算架構的短期能量預測系統，對整個MEC 網絡能量消耗進行調控。文獻[7]利用MEC 中邊緣服務器數據存儲的文件熱度指標，提出了一種邊緣服務器數據更新機制，將較常用數據保存在靠近用戶的位置，將不常用數據傳輸至上層設備，降低了任務處理過程中的數據下載時間延遲。文獻[8]建立了移動用戶聯合卸載和傳輸功率分配模型，針對任務傳輸過程中的排隊現象，提出了一種離散功率調整機制，在滿足延遲約束的情況下，完成任務數據傳輸并最小化設備功率。文獻[9]聯合優化了用戶選擇和資源分配策略，并將問題轉換為混合整數非線性優化問題，再進一步松弛為凸優化問題，以獲得最大化的能源效率。最近一段時間，能量收集技術和無線能量傳輸技術取得了較大發展，無線設備可從自然環境中獲得能量或者通過無線充電設備獲得額外電量[10-11]，這為MEC 應用場景中無線設備能量約束問題提供了一種可行的優化方案。一些研究也將無線能量傳輸技術應用于MEC 場景中，在能量輔助設備的協助下，MEC 相關執行步驟得到了一定優化[12-13]。隨著無人機（Unmanned Aerial Vehicle，UAV）技術和機器學習技術的發展與廣泛應用，也有研究將UAV 技術應用于MEC 中作為可移動的中繼設備，對區域中無線通信網絡架構進行動態維護和優化[14]，根據UAV 本身的飛行能耗和無線傳輸能耗優化中繼節點位置及MEC 卸載匹配決策。文獻[15-16]提出了基于深度強化學習的MEC 資源分配機制，在較多實際數據支撐的條件下有效提升了MEC 整體性能。

以上研究較新穎，但實施難度較大，工程實現方式較復雜，應用難度高，并且多為面向個人用戶的商業化服務優化，目前還未有針對智能礦山中MEC 資源分配優化的相關研究[17]。本文將多邊緣服務器、多移動用戶的應用場景建模為多對多匹配問題，并引入邊緣服務器動態算力和移動用戶動態剩余能量2 個動態參數，將傳統的靜態模型轉換為動態匹配模型，提出一種基于移動用戶對邊緣服務器偏好表及邊緣服務器對移動用戶偏好表的二維動態匹配算法，使區域內移動用戶任務在滿足延遲約束條件下提高總任務完成率，進而最大化系統效用。

1 算法應用場景模型

在智能礦山工業生產環境中任務內容量激增情況下，傳統邊緣計算卸載機制難以滿足服務質量。因此，本文對MEC 任務卸載過程中的邊緣服務器與移動用戶多對多匹配問題進行優化，以找到滿足預設條件的解。具體應用場景舉例：由于自然災害、電力事故等導致部分邊緣服務器無法提供服務或需使用備用電源，伴隨移動用戶信息傳輸的爆發式增長。以上情況可描述為資源緊缺狀態下出現較大任務量的應用場景模型，在該應用場景模型下對計算和能源資源的合理分配顯得尤為重要，采用優異的資源分配算法將大大改善特殊情況下無法滿足服務質量要求的情況。密集任務條件下MEC 模型如圖1所示。短時間內多任務進入MEC 服務區域，導致邊緣服務器無法為所有任務同時提供滿足延遲約束的服務，因此部分用戶無法在延遲約束下完成任務。需要注意的是，由于邊緣計算概念中資源被提供方通常稱作“用戶”，本文討論的應用場景中“用戶”為井下設備。

圖1 密集任務條件下MEC 模型Fig.1 Mobile edge computing model under intensive task conditions

1.1 網絡模型

MEC 服務器部署在智能礦山場景中的基站上，具有一定的數據存儲能力和計算能力。本文定義邊緣服務器集S={s1，s2，···，sm}（sj為邊緣服務器，j=1，2，···，m，m為邊緣服務器數量），移動用戶集U={u1，u2，···，un}（ui為移動用戶，i=1，2，···，n，n為移動用戶數量）。令二進制函數Ψ（ui，sj）表示移動用戶ui在時隙Δt內是否將任務遷移到邊緣服務器sj：

1.2 通信模型

移動用戶與邊緣服務器之間采用無線通信模式，根據香農公式，移動用戶ui至邊緣服務器sj的傳輸速率為

式中：B為信道帶寬；Pi為移動用戶ui的功率；hi,j為移動用戶ui到邊緣服務器sj的信道增益；σ2為高斯噪聲功率譜密度。

生成任務的移動用戶將決定直接發送任務數據包到邊緣服務器還是通過路徑空閑的移動用戶進行中繼發送，由于發送消耗能量與傳輸路徑距離呈正相關，所以移動用戶更偏向于通過中繼用戶進行卸載。

1.3 任務處理模型

定義邊緣服務器sj的計算能力=FjTlatency，其中Fj為邊緣服務器CPU 頻率，Tlatency為用戶延遲約束的最大容忍延遲，所用時間若超過最大容忍延遲即認為服務未達到預期需求。定義完成移動用戶ui的任務所需計算量為。

設一個邊緣服務器是單線程的，同時僅能處理1 個任務，所有移動用戶的最大容忍延遲Tlatency均相同，并且將Tlatency作為標準時隙Δt，所有移動用戶在時隙開始時刻確定是否生成任務，若ui生成任務，則令移動用戶ui在時隙Δt內所產生的任務=1，否則=0。在1 輪任務處理過程中，MEC 網絡模型中所有移動用戶在標準時隙開始時刻確定其任務狀態信息，并 形成一張任務 狀態表，以表示所有移動用戶的任務狀態，其中為移動用戶ui當前位置坐標信息。

1.4 偏好模型

本文提出的二維動態匹配算法是基于偏好的，包含邊緣服務器對移動用戶的偏好及移動用戶對邊緣服務器的偏好。進行任務處理初始化時，每個邊緣服務器形成一張針對移動用戶的一維偏好表，移動用戶也形成針對邊緣服務器的一維偏好表。由于邊緣服務器能源約束較低，不必考慮移動傳輸的能源消耗，僅考慮邊緣服務器算力消耗，所以邊緣服務器優先偏好任務計算量小的移動用戶。而移動用戶由電池供電，具有一定的能量約束，因此需要考慮影響能量消耗的因素。本文以物理距離表征能耗性質，即移動用戶更偏向于將任務卸載到最近的邊緣服務器。同時，由于本文旨在對整個智能礦山MEC網絡進行優化，需盡可能使煤礦邊緣服務器算力資源均勻分配，所以將邊緣服務器的算力作為動態參數。例如，當第1 個移動用戶的任務分配到邊緣服務器sj后，sj的算力更新為，此時移動用戶對邊緣服務器的偏好表發生更改，第2 個移動用戶將向位于新的偏好表首位的邊緣服務器提出卸載請求，依此類推，直到匹配完成。

移動用戶對邊緣服務器的偏好與傳輸路徑距離和邊緣服務器剩余算力有關，因此，令移動用戶對邊緣服務器的偏好值為

式中：ε，ω為偏好系數，由于邊緣服務器剩余算力和距離同樣重要，本文中取 ω=ε，在計算資源稀缺的應用中可取 ω＞ε，在能量資源稀缺的應用中可取 ω＜ε；di,j為移動用戶ui到邊緣服務器sj的物理距離。

2 問題分析

定義Dk為第j個邊緣服務器當前時間段第k個子任務的數據大小，Rk為第k個子任務的傳輸速率，則第k個子任務排隊等待時間為

任務數據包傳輸階段耗時為

第k個子任務排隊過程和傳輸過程總耗時為

卸載完成后，邊緣服務器執行處理任務的時間為

單個移動用戶的任務從生成到收到結果的總時間為

由于計算結果數據包與任務數據包相比通常要小數個數量級，所以可以忽略計算結果從邊緣服務器回傳的時間。優化模型可描述為在邊緣服務器算力不超過限制的情況下，最小化總任務完成時間及移動用戶發送、中繼、接收的耗能（其中耗能通過移動用戶發送功率表示）。

式中：Ei為當前剩余能量；Ed為維持MEC 各設備正常運行的最低能量。

約束C1表示每個移動用戶只能將任務卸載到1 個邊緣服務器，約束C2表示移動用戶任務完成時間需要滿足延遲約束，約束C3表示移動用戶的當前剩余能量要高于維持MEC 各設備正常運行的最低能量。

3 算法實現

移動用戶將自身狀態信息傳輸至邊緣服務器，邊緣服務器根據收到的狀態信息，形成邊緣服務器集S對移動用戶集U的偏好表及移動用戶集U對邊緣服務器集S的偏好表。設經過邊緣服務器排序后的移動用戶偏好表KS={u1,u2,···,un}，由于邊緣服務器僅考慮移動用戶產生的任務的困難程度，所以各邊緣服務器對移動用戶的偏好表是相同的，均為根據移動用戶生成任務所需計算量排序的一維偏好表。而不同移動用戶由于物理位置和能耗不同，其對邊緣服務器的偏好表可能是無規律且各不相同的，分別記為。將邊緣服務器對移動用戶偏好表及移動用戶對邊緣服務器偏好表相結合，可形成一張二維動態偏好表，為便于算法執行，將其抽象為二維矩陣：

智能礦山MEC 資源分配模型與約會匹配模型[18]類似，約會匹配模型是一個經典的穩定匹配模型，最終會達到匹配穩定狀態，本文中移動用戶與邊緣服務器之間的匹配也可視為穩定匹配問題，期望求出滿足約束條件的最大化用戶總任務完成率的穩定匹配狀態。與約會匹配模型不同的是，為了減少算法計算量，MEC 資源分配模型中邊緣服務器對移動用戶的偏好表被設置為靜態，而邊緣服務器的剩余算力是動態變化的，因此移動用戶對邊緣服務器的偏好表也是動態變化的。二維動態匹配算法如下。

二維動態匹配算法結合邊緣計算實際情況，將邊緣服務器對移動用戶的偏好設為靜態量，生成MEC 匹配決策時，直接提取當前二維矩陣M中位于M（1，1）的移動用戶和位于M（1，2）的邊緣服務器形成匹配即可；更新未匹配移動用戶對邊緣服務器的偏好表時，將M（1，2）處邊緣服務器的剩余算力作為比較值，在各移動用戶對邊緣服務器的偏好表中從后向前插入排序即可。對于剛匹配成功的邊緣服務器，由于剩余算力急劇減少，移動用戶對其偏好會下降很多。因此大多數情況下，M（1，2）處的邊緣服務器將在第1 次迭代時就被插入到移動用戶對邊緣服務器偏好表的最后一位，這樣大大減少了處理時間。

4 仿真分析

采用Matlab 軟件進行仿真，在20 m×100 m（寬×長）的煤礦井下綜采工作面區域內部署3 個邊緣服務器，設置在某一時間段內有100～1 000 個移動用戶在區域內活動的仿真實驗組，移動用戶生成任務是隨機的，包括環境感知傳感設備數據采集處理任務，機械手、運輸設備和鉆井機械設備等位置及狀態感知任務，井下人員定位設備數據采集任務等。為方便起見，將任務數據大小分為20 kB，1 MB，20 MB 3 種，任務處理難度與任務數據大小無關，以所需邊緣服務器CPU 計算次數1×106，1×107，1×108表示3 種計算難度，任務數據大小和所需邊緣服務器CPU 計算次數由程序隨機等概率生成，設邊緣服務器CPU 頻率為2 GHz，延遲約束Tlatency為2 s。

用總任務完成率 υcompleted表示匹配結果的好壞程度：

式中：βcompleted為完成的任務數；βgenerated為1 個時隙中生成的任務總數。

選用隨機卸載算法、分區卸載算法、基于能量收集的匹配算法與本文提出的二維動態匹配算法進行仿真對比。隨機卸載算法即生成的所有用戶任務隨機進行卸載，直到區域內總算力耗盡或總耗能達到閾值；分區卸載算法即提前將區域分成子區域（子區域數量與區域中邊緣服務器數量相等），在預設的子區域內生成的任務自動卸載至該子區域所對應的邊緣服務器進行處理；基于能量收集的匹配算法即為用戶配備能量收集裝置，設置能量收集能力為能量消耗閾值的10%，使用二維動態匹配算法進行資源分配。仿真結果如圖2 所示。

圖2 不同MEC 資源分配算法總任務完成率對比Fig.2 The results of comparison of different mobile edge computing resource allocation algorithms on task completion rate

從圖2 可看出，4 種算法的總任務完成率均隨著區域內移動用戶數增加而下降，這是因為當區域內移動用戶數激增時，計算負載過大，導致邊緣計算服務器無法滿足所有任務的延遲約束。在區域內移動用戶較少時，4 種算法均可達到較高的總任務完成率；當移動用戶個數大于200 時，4 種算法的總任務完成率均開始下降，其中分區卸載算法和隨機卸載算法下降速度較快，這是因為在數據量激增的情況下，使用普通算法的卸載機制此時已接近滿載，而本文提出的二維動態匹配算法能夠優先執行計算量較小的任務，從而使總任務完成率隨任務增加而下降的趨勢放緩，并且在極端情況下，即區域內移動用戶個數在短時間內增至500 以上時，能夠保持較高的總任務完成率。在區域內總移動用戶個數為600 以下時，基于能量收集的匹配算法和本文提出的二維動態匹配算法在總任務完成率上無明顯差異；移動用戶個數在600 以上時，基于能量收集的匹配算法表現指標略優于本文算法，但未達10%，即未能較好地利用所收集的能量。這是因為能量收集技術更多用于耗能平均的無線傳感網中，對于任務耗能差異較大的任務群無法做到將收集的能量按比例分配，生成低難度任務的移動用戶收集的能量無法轉移至高耗能用戶處使用，而高耗能用戶本身收集的能量又不足以滿足其過高的能量需求。再者，能量收集技術更多應用于工業場景，對于面向消費者的商業服務領域的應用場景，能量收集裝置無法大規模部署。綜上可得，本文提出的二維動態匹配算法在移動用戶數增加的情況下能夠較好地保證一定的總任務完成率，滿足移動用戶體驗質量及服務質量需求。

5 結語

針對智能礦山應用中任務數據量突然增大情況下MEC 應用場景保證服務質量的問題，將問題類比約會匹配問題并進一步轉換為二維動態匹配問題，對邊緣服務器對用戶的偏好表進行了優化，降低了匹配過程計算量。仿真結果表明，提出的二維動態匹配算法形成的任務卸載匹配所達到的總任務完成率與常規MEC 場景卸載算法相比有明顯提高。未來將考慮引入中繼移動用戶進行數據輔助中繼傳輸，進一步降低移動用戶能耗，提升用戶體驗質量。