協(xié)同移動邊緣計算分層資源配置機制

王界欽，林士飏，彭世明，賈碩，楊苗會

（山東理工大學交通與車輛工程學院，山東淄博 255000）

0 引言

智能交通系統(tǒng)（Intelligent Transportation System，ITS）的三層式架構(gòu)，利用道路感知器偵測交通流量信息后，通過網(wǎng)絡(luò)將信息上傳至云中心進行運算，再依據(jù)運算的結(jié)果進行支配決策，以提升交通安全水平。隨著生活質(zhì)量的不斷提高，汽車的各類云端增值業(yè)務(wù)（車載視頻、語音播報、衛(wèi)星定位等）與應(yīng)用服務(wù)（智能導(dǎo)航、自動駕駛等）也在不斷擴展，增加了傳輸數(shù)據(jù)量與計算量。因此，伴隨車聯(lián)網(wǎng)行業(yè)的發(fā)展以及ITS 的需求，云中心的大數(shù)據(jù)處理面臨成本高、傳輸性能差、即時性能低等諸多挑戰(zhàn)。移動邊緣計算（Mobile Edge Computing，MEC）服務(wù)器布置在移動網(wǎng)絡(luò)邊緣能減輕云中心計算負擔，例如構(gòu)建ITS 的MEC 分散式應(yīng)用服務(wù)，以邊緣云的計算能力完成車聯(lián)網(wǎng)所需要的大量運算任務(wù)，減少車載端的運算時間。

考慮到MEC 服務(wù)器計算資源的有限性、網(wǎng)絡(luò)負載分布的非均衡性，本文提出了一種MEC 分層協(xié)同資源配置機制（Hierarchical Resource Allocation Mechanism of cooperative MEC，HRAM）。主要工作如下：

1）提出一種MEC 分層協(xié)同資源配置方案，實現(xiàn)多跳內(nèi)的MEC 服務(wù)器計算資源共享；針對負載過大的MEC 服務(wù)器，能夠減緩計算壓力，加速卸載任務(wù)響應(yīng)，高效利用有限的計算資源。

2）提出基于層次分析法的目標節(jié)點選擇策略，綜合考慮服務(wù)能力、響應(yīng)時間、車流密度、方向一致性四項要素，統(tǒng)籌決策卸載任務(wù)的目標MEC 服務(wù)器。

3）提出動態(tài)權(quán)值任務(wù)路由策略，考慮同一轉(zhuǎn)發(fā)路徑下，多個卸載任務(wù)間的影響、資源競爭，通過動態(tài)調(diào)整路徑權(quán)值，以避免重復(fù)路徑的多次選擇，調(diào)用整體網(wǎng)絡(luò)的通信能力，有效減少時延。

1 相關(guān)研究

為解決MEC 服務(wù)器資源分配問題，文獻［1］中提出一種新的整數(shù)規(guī)劃（Integer Programming，IP）和JOR-MEC（Joint Offloading and Resource allocation-MEC）算法，并通過仿真證實算法能降低MEC 服務(wù)器的平均能耗。文獻［2］中，作者將計算任務(wù)分解，提出一種在線任務(wù)卸載算法，將最優(yōu)卸載到云中心與啟發(fā)式負載平衡卸載到云中心分別用于順序任務(wù)和并行任務(wù)。

近幾年來，深度強化學習（Deep Reinforcement Learning，DRL）和機器學習（Machine Learning，ML）在MEC 服務(wù)器任務(wù)卸載和資源分配上大放光彩。文獻［3］采用深度強化學習、考慮移動用戶設(shè)備（User Equipment，UE）在基站間的移動性，提出了一種MEC 環(huán)境下自適應(yīng)任務(wù)卸載和資源分配算法。對比其他算法，在減少任務(wù)平均響應(yīng)時間和系統(tǒng)總能耗，提高系統(tǒng)效用方面表現(xiàn)最佳，滿足用戶和服務(wù)提供商的利益。與文獻［3］相似，文獻［4］基于深度Q 網(wǎng)絡(luò)（Deep-Q Network，DQN）提出了一種MEC 任務(wù)卸載和資源分配算法——聯(lián)合任務(wù)卸載決策和帶寬分配優(yōu)化，最小化能耗成本、計算成本和延遲成本的算法，將非凸優(yōu)化問題轉(zhuǎn)化為強化學習問題，采用DQN 找尋最優(yōu)解。文獻［5］基于深度強化學習和聯(lián)邦學習（Federated Learning，F(xiàn)L）提出了一種智能資源配置模型，以解決在多變MEC 環(huán)境中網(wǎng)絡(luò)資源和計算資源合理分配的問題，仿真顯示，該模型在最小化系統(tǒng)平均能量消耗、最小化平均服務(wù)延遲、均衡資源分配方面有顯著表現(xiàn)。文獻［6］提出利用工業(yè)物聯(lián)網(wǎng)進行資源分配的強化學習（Reinforcement Learning，RL）解決方案?；趧討B(tài)規(guī)劃和多目標蟻群優(yōu)化算法，解決終端用戶間資源精確分配問題。為了實現(xiàn)MEC 服務(wù)器更高的能源效率和更好的用戶體驗，最大化上行通信中卸載任務(wù)數(shù)量，同時保證MEC 服務(wù)器的計算資源在一個可接受的水平，文獻［7］指出基于深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）的聯(lián)合邊緣設(shè)備的任務(wù)協(xié)同運作是降低延遲的有效方法，提出動態(tài)資源分配優(yōu)化方案，自動選擇最佳分區(qū)點以最小化所有車輛的整體延遲。為了進一步降低系統(tǒng)開銷，文獻［8］提出V2X（Vehicle-to-X）的卸載和資源分配問題，并給出最優(yōu)卸載決策、傳輸功率控制、子信道分配和計算資源分配方案。首先采用層次分析法選擇初始卸載節(jié)點，然后采用無狀態(tài)Q 學習法對傳輸功率、子信道和計算資源進行分配。

隨著無線能量傳輸技術(shù)的發(fā)展，無線電和MEC 計算資源的聯(lián)合分配備受關(guān)注。文獻［9］研究具有多個能量收集裝置的MEC 系統(tǒng)中無線電和計算資源分配的新方法，提出時間平均計算速率最大化（Time Average Computation Rate Maximization.TACRM）算法，動態(tài)決策每個時間塊內(nèi)無線設(shè)備的最優(yōu)帶寬、發(fā)送功率、時間分配和本地CPU 頻率，通過大量仿真實驗說明TACRM 算法能夠有效提高系統(tǒng)的數(shù)據(jù)處理速度。而文獻［10］在多用戶場景下聯(lián)合考慮計算資源、無線電資源以及數(shù)據(jù)安全，以最小化整個系統(tǒng)的時間和能耗為目標，提出具有數(shù)據(jù)安全的多用戶資源分配和計算卸載模型，對比局部執(zhí)行和完全卸載方案，能夠顯著提高整個系統(tǒng)的性能。文獻［11］考慮一種具有雙天線混合接入點（Hybrid Access Point，HAP）和單天線移動裝置的無線移動邊緣計算系統(tǒng)（Wireless Powered Mobile Edge Computing，WP-MEC），用于能量傳輸和數(shù)據(jù)傳輸；針對系統(tǒng)平均計算速率最大化問題，提出在線服務(wù)速率最大化（Online Service Rate Maximization，OSRM）算法。

文獻［12］提出一種高效、低復(fù)雜度的啟發(fā)式算法，以較低的時間成本提供接近最佳的解決方案，并給出最優(yōu)傳輸功率與MEC 服務(wù)器計算資源的關(guān)系；結(jié)果表明，在不同場景下，所提方案能實現(xiàn)更高的任務(wù)成功卸載次數(shù)。文獻［13］針對5G 通信網(wǎng)絡(luò)難以完成密集任務(wù)的問題，提出5G 邊緣計算中基于多用戶網(wǎng)絡(luò)系統(tǒng)模型的計算密集型任務(wù)處理模式，包括本地計算、霧節(jié)點計算和邊緣節(jié)點計算三種計算模式，將任務(wù)的卸載問題轉(zhuǎn)化為時延和能耗聯(lián)合優(yōu)化問題，用戶設(shè)備可根據(jù)計算任務(wù)的特點和系統(tǒng)狀態(tài)選擇處理計算任務(wù)的最佳方式，并通過仿真驗證方案在減少時延和能耗、提高任務(wù)處理效率和終端用戶體驗上的優(yōu)勢。文獻［14］為了實現(xiàn)用戶能源效率最大化，提出多用戶多MEC 服務(wù)器任務(wù)卸載模型，在仿真分析下，該模型可以減少單鏈路通信的壓力，保證用戶體驗和網(wǎng)絡(luò)性能，還能減少鏈路信令開銷。

雖然目前的相關(guān)研究從多方面著手解決車聯(lián)網(wǎng)中MEC服務(wù)器任務(wù)卸載和資源分配問題，但并未考慮眾多MEC 服務(wù)器間的協(xié)同以及合理分配問題，且不同方案的應(yīng)用場景各有不同。本文聚焦車聯(lián)網(wǎng)在5G 環(huán)境下多車輛、多任務(wù)構(gòu)成的MEC 通信小區(qū)組成的復(fù)合MEC 系統(tǒng)場景?？紤]MEC 服務(wù)器服務(wù)能力有限、負載差異大，同時為了能夠更好地滿足車輛的服務(wù)需求，提出一種移動邊緣計算分層協(xié)同資源配置方案。當本地端MEC 服務(wù)器因忙碌而無法滿足多余卸載任務(wù)的計算需求時，通過層次分析法進行多因素綜合考慮，從候選端中挑選合適的目標節(jié)點，讓多余的卸載任務(wù)分配到適當?shù)腗EC 服務(wù)器進行運算，再借由動態(tài)權(quán)值任務(wù)路由，達到合理分配與有效利用MEC 服務(wù)器的運算資源，減少不同MEC 服務(wù)器之間的數(shù)據(jù)多跳轉(zhuǎn)發(fā)時延，優(yōu)化卸載任務(wù)請求時延的目標。

2 系統(tǒng)模型

2.1 場景描述

圖1 為本文交通仿真場景。道路設(shè)施單元（Road Side Unit，RSU）部署在道路交接處，相鄰RSU 的覆蓋區(qū)域不重疊，且每個RSU 均配備MEC 服務(wù)器，形成獨立的通信小區(qū)。車輛單元（Vehicle Unit，VU）行駛過程中因自動駕駛不斷與周邊環(huán)境進行交互，產(chǎn)生大量計算任務(wù)，而大多數(shù)任務(wù)具備一定的時效性，車載終端計算能力有限，難以滿足眾多任務(wù)的需求，因此考慮將任務(wù)卸載到MEC 服務(wù)器上處理，分流上載云端所需的數(shù)據(jù)至云中心，最后將計算結(jié)果返回至車輛單元。

圖1 交通情景Fig.1 Traffic scenario

本文將請求任務(wù)卸載的車輛單元表示為集合VUs=｛VU1，VU2，…，VUi｝。每個車輛單元有一個或多個卸載任務(wù)，所有任務(wù)不可切分、相互獨立、互不影響，用集合TASKj=｛Task1，Task2，…，Taskj｝表示。卸載任務(wù)的屬性描述為一個三元組Taski，j=｛RTL，size，Tmax｝。其中，Taski，j表示第i個車輛單元的第j個任務(wù)，RTL表示卸載任務(wù)的所屬車輛實時位置，size表示卸載任務(wù)的數(shù)據(jù)量，Tmax表示卸載任務(wù)最大可容忍時延。

通信小區(qū)中所屬的MEC 服務(wù)器稱為本地MEC 服務(wù)器，即本地端LN（Local Node），重點研究本地端移動車輛的任務(wù)卸載策略。定義其他通信小區(qū)所屬MEC 服務(wù)器為候選端（Candidate Node，CN），并根據(jù)MEC 服務(wù)器間信息傳遞次數(shù)（層數(shù)）n，定義集合CN=｛MEC1，1，MEC1，2，…MECn，m｝，其中n∈Nhop，m表示n層的MEC 服務(wù)器編號。

RSU 作為車輛單元和MEC 服務(wù)器之間傳輸數(shù)據(jù)的媒介，除傳輸請求任務(wù)封包和返回數(shù)據(jù)外，還需定期收集車輛單元的信息（如：實時位置RTLi、車速vi、車輛任務(wù)）、檢測通信小區(qū)的車流密度MEC 服務(wù)器周期性地交換本地/鄰近服務(wù)器的相關(guān)信息，實現(xiàn)數(shù)據(jù)共享。現(xiàn)對數(shù)據(jù)信息進行分類定義：

定義1本地信息流（Local Stream，LS）。

在一個通信小區(qū)內(nèi)，MEC 服務(wù)器位置信息、空閑服務(wù)能力、RSU 采集的車輛單元信息為本文研究的基礎(chǔ)信息，能直觀體現(xiàn)通信小區(qū)狀態(tài)，定期更新、存儲于本地端，是不同通信小區(qū)信息交流的重要信息。簡記為本地信息流。

定義2鄰居節(jié)點信息流（Neighbors Stream，NS）。

不同通信小區(qū)間需要周期性地交換數(shù)據(jù)，即MEC 服務(wù)器發(fā)送/接收Nhop 范圍內(nèi)的LS，建立、維護鄰居數(shù)據(jù)表。對接收端而言，所有接收的LS 均非描述本端狀態(tài)的信息，因此，定義該類信息流為鄰居節(jié)點信息流。

定義3卸載轉(zhuǎn)移信息流（Upload Transfer Stream，UTS）。

當本地端未能滿足卸載任務(wù)的服務(wù)需求時，卸載任務(wù)需要轉(zhuǎn)移。本地端首先根據(jù)選擇策略，確定候選端中合適的MEC 服務(wù)器作為目標節(jié)點；隨后，本地端根據(jù)給定的目標節(jié)點，結(jié)合路由策略確定轉(zhuǎn)發(fā)節(jié)點、轉(zhuǎn)發(fā)路徑。該類計算數(shù)據(jù)及卸載任務(wù)所屬車輛信息描述了任務(wù)的整體狀態(tài)，在本地端、轉(zhuǎn)發(fā)節(jié)點、目標節(jié)點間進行傳輸，為便于后文描述，定義為卸載轉(zhuǎn)移信息流。

2.2 通信模型

在本模型中，車輛單元的卸載任務(wù)需要從車載端通過無線信道傳輸?shù)絉SU，再上載至本地MEC 服務(wù)器。同一通信小區(qū)內(nèi)，RSU 通常位于MEC 服務(wù)器附近，因此忽略RSU 到MEC 服務(wù)器的通信時延［15］。載波聚合（Carrier Aggregation，CA）作為5G 增強技術(shù)之一，聚合多個載波單元進行傳輸，從而大幅度提高上下行傳輸性能，以滿足5G 車聯(lián)網(wǎng)的通信需求。根據(jù)3GPP（3rd Generation Partnership Project）協(xié)議TS38.306 規(guī)范，對于5G 新空口（New Radio，NR）技術(shù)，計算給定的頻帶載波近似聚合速率VCA［16］為：

各參數(shù)說明如表1 所示。

表1 參數(shù)名及意義說明Tab.1 Parameter names and meanings

移動用戶的空口速率一般按上、下行分開測試和表示，表示為數(shù)據(jù)的吞吐量。5G NR 峰值數(shù)據(jù)吞吐速率受網(wǎng)絡(luò)對上下行時隙的分配比例、網(wǎng)絡(luò)環(huán)境、用戶數(shù)、網(wǎng)絡(luò)側(cè)和終端側(cè)的能力等因素影響。本文把VUs 的上行傳輸速率以5G NR Uu 接口的速度計算，采用頻率范圍為FR1，根據(jù)基礎(chǔ)配置下終端數(shù)據(jù)理論吞吐率，確定上行傳輸速率Vuplink的范圍在309.1 Mb/s～618.1 Mb/s。由于本文考慮的卸載任務(wù)為計算密集型任務(wù)，輸出相較于輸入非常小，因此本文不考慮從MEC 服務(wù)器返回VUs 的下行傳輸時延［17］。

2.3 執(zhí)行方式?jīng)Q策模型

在一個周期內(nèi)，VUs 的卸載任務(wù)由車載端依次上載至本地端，受本地端有限服務(wù)能力約束，不能滿足所有卸載任務(wù)的時延要求，本地端需決策任務(wù)執(zhí)行方式，令typei，j∈｛0，1｝。當typei，j=0 時，表示Taski，j將在本地端執(zhí)行；反之，Taski，j將轉(zhuǎn)移至候選端執(zhí)行。

為了能充分利用本地端的計算資源，同時滿足卸載任務(wù)最大可容忍時延，提出找尋本地端臨界服務(wù)狀態(tài)的方案，明確卸載任務(wù)的執(zhí)行方式。

執(zhí)行方式?jīng)Q策算法的偽代碼如算法1 所示。車載端首先上載所有卸載任務(wù)至本地端，按從小到大的順序存儲于本地端中，并以數(shù)據(jù)大小為索引，存儲任務(wù)來源及具體編號。默認所有任務(wù)執(zhí)行方式為候選端執(zhí)行，即初始化數(shù)組type=1。本地端可提供的服務(wù)能力將由所有分配至本地端的卸載任務(wù)均分，分配值Nloc由1 開始迭代，直至分配任務(wù)中存在任務(wù)的處理時間與上行時間之和超出最大任務(wù)響應(yīng)時間，或者分配值迭代至卸載任務(wù)總數(shù)Numtotal，此時可以確定于本地端執(zhí)行的卸載任務(wù)數(shù)Nloc-1，數(shù)組type（1）～type（Nloc-1）更新為0，從而確定了本地端與候選端各需執(zhí)行的任務(wù)。按照任務(wù)大小進行排序，使計算量高的任務(wù)被分配到計算能力更好的候選端上，減少時延；而本地端有限的服務(wù)能力也能夠在保證時延的前提下被輕量級任務(wù)合理利用。

算法1 執(zhí)行方式?jīng)Q策算法。

2.4 計算模型

本文在進行任務(wù)卸載計算時主要考慮到處理時延（processing delay）、傳輸（發(fā)送）時延（transmission delay）和傳播時延（propagation delay）。

2.4.1 本地端計算

當卸載任務(wù)Taski，j確定在本地端執(zhí)行時，卸載任務(wù)的時延主要包括傳輸時延和處理時延。令表示本地端可以提供的計算能力（CPU 周期數(shù)），per表示單位bit 所需CPU 周期數(shù)，則Taski，j由車載端上載至本地端的傳輸時延在本地端的處理時延分別為：

2.4.2 候選端計算

當卸載任務(wù)Taski，j確定轉(zhuǎn)移到候選端執(zhí)行時，卸載任務(wù)的時延主要包括傳輸時延、傳播時延和處理時延。由本地端發(fā)送卸載任務(wù)的傳輸時延為：

由本地端到目標節(jié)點MECtarget的傳播時延為：

卸載任務(wù)Taski，j在目標節(jié)點上的處理時延為：

其中：rdata表示數(shù)據(jù)發(fā)送速率；d1，m表示當目標節(jié)點處于1 hop時，本地端與編號為m的目標節(jié)點之間的通信鏈路距離；rf表示傳播速度；Δdu-1表示當目標節(jié)點處于nhop 時，目標節(jié)點與轉(zhuǎn)發(fā)節(jié)點之間、轉(zhuǎn)發(fā)節(jié)點與轉(zhuǎn)發(fā)節(jié)點之間的通信鏈路距離表示目標節(jié)點執(zhí)行卸載任務(wù)Taski，j所分配的計算能力（以CPU 周期數(shù)表示）。

3 目標節(jié)點選擇與路由

3.1 基于層次分析法的目標節(jié)點選擇策略

本地端周期性接收NS 維護鄰居數(shù)據(jù)表，以保證數(shù)據(jù)信息的時效性，為目標節(jié)點選擇提供基礎(chǔ)。對typei，j=1 的卸載任務(wù)，本文利用層次分析法（Analytic Hierarchy Process，AHP）選擇較為合適的目標節(jié)點，根據(jù)多因素的權(quán)重系數(shù)，確定候選端的優(yōu)先級（preference）。層次分析法是一個多標準決策（Multiple Criteria Decision Making，MCDM）/多屬性決策（Multiple Attribute Decision Making，MADM）模型，包括目標層、準則層和方案層，應(yīng)用于諸多領(lǐng)域，是一種合理解決優(yōu)先級調(diào)度的手段［17］。

本文主要考慮候選端狀態(tài)以及移動車輛信息，整理為四項影響因素，建立層次結(jié)構(gòu)模型如圖2 所示。下面詳細分析所選影響因素。

圖2 層次分析法結(jié)構(gòu)模型Fig.2 Analytic hierarchy process structure model

3.1.1 服務(wù)能力

受交通流量在時間和空間上的不均勻分布影響，不同通信小區(qū)的服務(wù)壓力不盡相同。本文的研究目的之一就是要降低通信小區(qū)間的服務(wù)壓力，減少資源浪費和非必要時延，因此候選端的服務(wù)能力是選擇目標節(jié)點的重要因素之一。本文以候選端CPU 的負載率表示服務(wù)能力，記為。

3.1.2 響應(yīng)時間

在本文研究中，決定卸載任務(wù)是否在不超出Tmax的條件下完成的主要依據(jù)是：卸載任務(wù)的響應(yīng)時間是否滿足Tmax，即滿足條件：

3.1.3 車流密度

候選端中，對于車流密度較小的通信小區(qū)，其對應(yīng)的MEC 服務(wù)器服務(wù)壓力較低；反之，對于車流密度較大的通信小區(qū)，對應(yīng)的MEC 服務(wù)器服務(wù)壓力較大，甚至會“溢出”。車流密度會間接影響候選端的服務(wù)能力，可作為考量因素之一，記為

3.1.4 方向一致性

3.1.5 權(quán)重分析

為了確定目標節(jié)點，需要確定影響因素兩兩之間的尺度關(guān)系。對卸載任務(wù)而言，保證時效性具有重要意義，甚至影響車輛行駛安全。因此，在本文層次分析模型中，響應(yīng)時間最重要，服務(wù)能力因影響卸載任務(wù)的執(zhí)行時間而間接影響響應(yīng)時間，重要程度次之，車流密度比方向一致性重要，構(gòu)造層次分析判斷矩陣其中：

其中：c為任務(wù)數(shù)量；r為車輛數(shù)量；s為該項分數(shù)。接著構(gòu)建判斷矩陣見表2。

表2 判斷矩陣Tab.2 Judgment matrix

根據(jù)構(gòu)造的判斷矩陣計算最大特征值λmax，求出對應(yīng)的歸一化特征向量，即四項因素的指標權(quán)重Δ如下：

權(quán)重的分配的合理性需通過一致性檢驗。見式（12）：

其中：CI表示一致性指標。RI表示平均一致性指標（4 階矩陣為0.90）。CR表示判斷矩陣的隨機一致性比率，當CR＜0.1 時，判定判斷矩陣A具有滿意的一致性；否則需要調(diào)整判斷矩陣A直至滿意的一致性為止。計算顯示，CR值小于0.1，滿足一致性檢驗要求，確定權(quán)重可信。

在進行數(shù)據(jù)分析之前，通常需要對數(shù)據(jù)進行標準化處理（normalization），本文選用z-score 標準化方法，基于均值和標準差對所有卸載任務(wù)構(gòu)成的基礎(chǔ)數(shù)據(jù)集BD=進行標準化處理，如式（13）所示：

其中：Zk∈[0，1]，表示第k個因素的標準化結(jié)果；Mk表示第k個因素樣本均值；σk表示第k個因素樣本標準差；BD（k）為基礎(chǔ)數(shù)據(jù)集BD中的第k個元素值。

最終，以標準化后的各因素與對應(yīng)權(quán)重的乘積和作為目標節(jié)點的選擇依據(jù)。卸載任務(wù)Taski，j選擇目標節(jié)點MECtarget見式（14）：

3.2 動態(tài)權(quán)值任務(wù)路由策略

本節(jié)的主要工作是確定卸載任務(wù)Taski，j的轉(zhuǎn)發(fā)路徑，特別是當目標節(jié)點在多層（如2 hop、3 hop、…）時，途經(jīng)的MEC服務(wù)器節(jié)點，即轉(zhuǎn)發(fā)節(jié)點。

Dijkstra 算法［18］作為典型的單源最短路徑算法之一，常用于求解給定起始節(jié)點、目標節(jié)點之間路徑的最優(yōu)解問題；基本原理是基于廣度優(yōu)先搜索（Breadth First Search）思想，以起始節(jié)點S為中心向外層層延伸，直至到達目標節(jié)點O。該算法總能求出給定S、O之間的最短路徑最優(yōu)解。對于通信網(wǎng)絡(luò)來說，找尋請求端到服務(wù)端之間的最小時延能夠減少數(shù)據(jù)的響應(yīng)時間，更好地保證時效性。對于單個卸載任務(wù)來說，應(yīng)用Dijkstra 算法能夠找到卸載任務(wù)從本地端轉(zhuǎn)發(fā)至目標節(jié)點的最短響應(yīng)時間；但本文研究為多個卸載任務(wù)同時卸載至多個目標節(jié)點，傳統(tǒng)Dijkstra 算法并不適用，因此，本文基于Dijkstra 算法面向單起始節(jié)點、多卸載任務(wù)、多目標節(jié)點提出一種動態(tài)權(quán)值任務(wù)路由策略。

頂點集合V=｛LN，CN｝=｛v0，v1，1，v1，2，…，vn，m｝；

對于不同的卸載任務(wù)，其數(shù)據(jù)大小存在差異。由式（15）可知，對同一有向邊，權(quán)值會隨卸載任務(wù)大小的改變而改變；同時，在同一周期內(nèi)存在多個卸載任務(wù)由本地端轉(zhuǎn)發(fā)至多個目標節(jié)點，雖然可以應(yīng)用Dijkstra 算法，將多個卸載任務(wù)獨立化處理，轉(zhuǎn)化為多次的單起始節(jié)點、單卸載任務(wù)、單目標節(jié)點問題，以確定最優(yōu)轉(zhuǎn)發(fā)路徑。然而，根據(jù)其原理分析，同一轉(zhuǎn)發(fā)節(jié)點、同一轉(zhuǎn)發(fā)路徑會被多次重復(fù)選擇，資源競爭不可避免，因而卸載任務(wù)間的影響不可忽略，傳統(tǒng)Dijkstra 算法并不適用。

在本節(jié)的研究中規(guī)定：轉(zhuǎn)發(fā)節(jié)點的轉(zhuǎn)發(fā)能力、同一路徑節(jié)點間的傳播能力會被途經(jīng)該轉(zhuǎn)發(fā)節(jié)點、該路徑的卸載任務(wù)均分，使得有向邊的權(quán)值增大，以降低同一轉(zhuǎn)發(fā)路徑多次選取的頻率。式（15）變更為：

其中：p1表示途經(jīng)轉(zhuǎn)發(fā)節(jié)點vn-1，m的卸載任務(wù)數(shù)；p2表示途經(jīng)節(jié)點vn-1，m、vn，m通信鏈路的卸載任務(wù)數(shù)。

本節(jié)所提面向動態(tài)權(quán)值任務(wù)轉(zhuǎn)發(fā)策略如算法2 所示。首先構(gòu)建本地端、候選端的鄰接矩陣，并將算法1 求得轉(zhuǎn)移卸載任務(wù)編號倒序，即按由大至小的順序?qū)π遁d任務(wù)進行轉(zhuǎn)發(fā)路徑選擇，使計算量高的任務(wù)被分配到發(fā)送時延和轉(zhuǎn)發(fā)時延較低的轉(zhuǎn)發(fā)節(jié)點，以縮小卸載任務(wù)間的時延差距。然后基于Dijkstra 算法思想，根據(jù)卸載任務(wù)順序以及基于AHP 確定的對應(yīng)目標節(jié)點得到轉(zhuǎn)發(fā)節(jié)點。但不同任務(wù)因大小及執(zhí)行順序的不同，鄰接矩陣會隨之改變，因此在分配任務(wù)b的轉(zhuǎn)發(fā)節(jié)點前，都應(yīng)由式（16）確定獨有的鄰接矩陣。

算法2 動態(tài)權(quán)值任務(wù)路由策略。

輸入CN及相對計算資源fc、Tmax、per、size、w、LN、MECtarget，轉(zhuǎn)移的卸載任務(wù)數(shù)Numtransfer及任務(wù)編號。

輸出卸載任務(wù)的轉(zhuǎn)發(fā)節(jié)點Nodes。

由算法2 可得到所有轉(zhuǎn)移卸載任務(wù)選擇的轉(zhuǎn)發(fā)節(jié)點，將轉(zhuǎn)發(fā)節(jié)點依序相連即構(gòu)成轉(zhuǎn)發(fā)路徑。

綜上，HRAM 算法示意圖如圖3 所示。

圖3 HRAM算法示意圖Fig.3 Schematic diagram of HARM algorithm

4 仿真實驗及性能分析

4.1 實驗環(huán)境

本文的仿真實驗是在內(nèi)存為12 GB、處理器為Intel Core i5-6300HQ，頻率為2.30 GHz，Windows 10 操作系統(tǒng)下進行，仿真工具為Matlab R2019b，實驗的具體參數(shù)配置見表3。

表3 參數(shù)配置Tab.3 Parameter configuration

本文以三層式（N=3 hop）為例，仿真驗證本文方案。除本地端外，按照4、8、8 的結(jié)構(gòu)方式分三層放置MEC 服務(wù)器，作為候選端，如圖4 所示。

圖4 MEC服務(wù)器部署示意圖Fig.4 Schematic diagram of MEC server deployment

4.2 對比算法

為了驗證本文提出的HRAM 算法的性能，下面與其他算法進行分析比較。

RATOS 算法：任務(wù)卸載單層式（1 hop）資源分配（Resource Allocation of Task Offloading in Single-hop）算法。該算法的處理思想是僅考慮近端1 hop 通信范圍內(nèi)的MEC 服務(wù)器，將計算資源均勻分配給所有的卸載任務(wù)。

RATOM 算法：任務(wù)卸載多層式（Nhop）資源分配（Resource Allocation of Task Offloading in Multi-hop）算法。該算法考慮Nhop 通信范圍內(nèi)的MEC 服務(wù)器，根據(jù)計算資源量，按比例分配卸載任務(wù)，以最小化任務(wù)計算時間為目標，轉(zhuǎn)發(fā)路徑規(guī)則遵循Dijkstra 算法。

4.3 復(fù)雜度分析

算法復(fù)雜度是衡量算法運行效率的標尺，質(zhì)量的優(yōu)劣會影響到算法甚至程序效率?？紤]最壞情況，對于算法1 而言，步驟7）～15）的循環(huán)次數(shù)取決于Nloc的值，當Nloc=Numlocalmax+1 循環(huán)結(jié)束；隨著Nloc的迭代，內(nèi)嵌for 循環(huán)、確定最大任務(wù)響應(yīng)時間的執(zhí)行次數(shù)均取決于Nloc。因此，在忽略常量、低次冪和最高次冪的系數(shù)后，計算得出算法1 的時間復(fù)雜度為，主要取決于本地端承載的最大卸載任務(wù)數(shù)。

同樣，對算法2 而言，步驟5）～8）的執(zhí)行次數(shù)為r；步驟10）～22）的執(zhí)行次數(shù)取決于Numtransfer，并且隨著Numtransfer的迭代，內(nèi)嵌while 循環(huán)的執(zhí)行次數(shù)為r，伴隨每次pb數(shù)組的求和，存儲、更新最短路徑和確定最小權(quán)值的執(zhí)行次數(shù)均為r。因此，算法2 的時間復(fù)雜度為O（r2×Numtransfer），主要取決于轉(zhuǎn)移任務(wù)數(shù)、服務(wù)節(jié)點數(shù)；為了能夠找到最適轉(zhuǎn)發(fā)路徑，執(zhí)行過程中時間成本會隨服務(wù)節(jié)點相較于本地端的層次分布（hop 的增加）成倍數(shù)增長，因此，算法2 的時間復(fù)雜度實際會受到轉(zhuǎn)移任務(wù)數(shù)量、服務(wù)節(jié)點數(shù)以及hop 的影響，候選端應(yīng)限制在合理hop 內(nèi)。

4.4 邏輯分析

參考圖3，對于算法1 執(zhí)行方式?jīng)Q策算法，當存在任務(wù)的響應(yīng)時間超出Tmax時，確定本地端的可承載的最大任務(wù)數(shù)為Nloc-1，此時對于按由小到大順序排列的任務(wù)來說，前Nloc-1 個任務(wù)將分配給本地端執(zhí)行，其他任務(wù)則擇優(yōu)選擇目標節(jié)點執(zhí)行。算法2 中，任務(wù)會遍歷所有從本地端連通至目標節(jié)點的所有路徑，如v1，1—v2，1—…—vm，1、v1，2—v2，2—…—vm，2、…、v1，n—v2，n—…—vm，n，計算每條路徑的權(quán)值和，選擇權(quán)值和最小的路徑作為該任務(wù)的轉(zhuǎn)發(fā)路徑，其他路徑舍棄，并且根據(jù)式（16）更新有向圖權(quán)值。

4.5 實驗結(jié)果及分析

對于多個卸載任務(wù)選擇同一目標節(jié)點的情況，本文以實例說明。如圖5 所示，有編號為1、2 的卸載任務(wù)需從本地端v0轉(zhuǎn)發(fā)至目標節(jié)點v3，1，數(shù)據(jù)封包大小分別為425 Kb、475 Kb。首先，根據(jù)任務(wù)1 的數(shù)據(jù)封包大小計算出任務(wù)1 從本地端v0到目標節(jié)點v3，1之間所有有向邊的權(quán)值，如圖5（a）所示，確定最優(yōu)轉(zhuǎn)發(fā)路徑為v0—v1，2—v2，2—v3，1。對比圖5（a）、（c）并結(jié)合式（15）可知，對不同大小的卸載任務(wù)而言，最優(yōu)轉(zhuǎn)發(fā)路徑始終唯一，為v0—v1，2—v2，2—v3，1，這顯然是不合理的，因為當有足夠多的卸載任務(wù)途經(jīng)同一轉(zhuǎn)發(fā)路徑，會造成轉(zhuǎn)發(fā)節(jié)點發(fā)送飽和，卸載任務(wù)之間競爭資源。對比圖5（a）、（b），確定任務(wù)1 的轉(zhuǎn)發(fā)路徑后，為降低再次選擇的可能性，更新轉(zhuǎn)發(fā)路徑途經(jīng)v0—v1，2—v2，2—v3，1的有向邊權(quán)重。觀察圖5（b）、（c）、（d），受任務(wù)1 轉(zhuǎn)發(fā)路徑選擇以及任務(wù)數(shù)據(jù)封包大小變化的影響，圖（d）中有向邊權(quán)值發(fā)生變化，任務(wù)2 的最優(yōu)轉(zhuǎn)發(fā)路徑更新為v0—v1，1—v2，1—v3，1。由此可見，本文提出的動態(tài)權(quán)值任務(wù)路由策略降低單一通信線路重復(fù)選擇的概率，有效調(diào)用整體網(wǎng)絡(luò)的通信能力，而非固定于同一路由，能降低整體網(wǎng)絡(luò)擁塞（network congestion）。

圖5 轉(zhuǎn)發(fā)路徑選擇Fig.5 Forwarding path selection

圖6 顯示控制卸載任務(wù)數(shù)量（卸載任務(wù)數(shù)為16）不變，卸載任務(wù)平均時延隨候選端平均服務(wù)能力變化的情況。圖6（a）表示在三種算法下，16 個卸載任務(wù)在目標節(jié)點完成計算的平均處理時延隨服務(wù)能力的變化。經(jīng)觀察發(fā)現(xiàn)，卸載任務(wù)的平均處理時延隨著服務(wù)能力的升高而降低，并且降低的幅度減小。三種算法下卸載任務(wù)的平均處理時延也趨于穩(wěn)定，主要是因為MEC 服務(wù)器的計算資源從匱乏到充足，卸載任務(wù)間的資源競爭關(guān)系減弱。圖6（b）表示三種算法下，16 個卸載任務(wù)由本地端發(fā)送，傳輸?shù)侥繕斯?jié)點經(jīng)歷的平均轉(zhuǎn)發(fā)時延。觀察發(fā)現(xiàn)，RATOS 算法平均轉(zhuǎn)發(fā)時延最低，RATOM 算法的平均轉(zhuǎn)發(fā)時延最高，這是因為RATOS 算法的目標節(jié)點僅為1 hop MEC 服務(wù)器，RATOM 算法和HRAM 算法還會選擇Nhop 的MEC 服務(wù)器作為目標節(jié)點，卸載任務(wù)需層層發(fā)送、傳輸?shù)侥繕斯?jié)點，因而RATOM 算法和HRAM 算法的平均轉(zhuǎn)發(fā)時延會高于RATOS 算法；此外，RATOM 算法和HRAM 算法均基于Dijkstra 算法，但HRAM 算法考慮卸載任務(wù)間路徑選擇的相互影響，路徑權(quán)值會動態(tài)變化，降低選擇重復(fù)轉(zhuǎn)發(fā)路徑的可能，所以時延低于RATOM 算法。

圖6 服務(wù)能力對卸載任務(wù)平均處理時延、轉(zhuǎn)發(fā)時延的影響Fig.6 Influence of service capability on average processing delay and forwarding delay of offloading tasks

圖7 表示16 個卸載任務(wù)在不同算法下，本地端發(fā)送UTS到目標節(jié)點，完成卸載任務(wù)計算的任務(wù)請求時延隨服務(wù)能力的變化曲線。整體來看，隨著服務(wù)能力的增加，三種算法下卸載任務(wù)的請求時延均有降低，并且差異性變小。當MEC服務(wù)器的服務(wù)能力較低時，RATOS 算法的時延相較于HRAM算法和RATOM 算法的時延較高，因為RATOS 算法僅考慮了1 hop 內(nèi)的目標節(jié)點，服務(wù)能力有限，而卸載任務(wù)眾多，資源競爭大，導(dǎo)致時延明顯增高；而HRAM 算法和RATOM 算法在本文實驗中考慮了3 hop 及以內(nèi)的目標節(jié)點，可選擇目標節(jié)點較多，在服務(wù)能力有限的情況下，能明顯縮短任務(wù)請求時延。實驗結(jié)果表明，HRAM 能夠更加充分使用MEC 服務(wù)器的服務(wù)能力，實現(xiàn)高效響應(yīng)任務(wù)請求。當服務(wù)能力達到60%左右時，RATOS 算法逐漸優(yōu)于RATOM 算法。通過對比分析圖6 發(fā)現(xiàn)，造成該現(xiàn)象的原因是：隨著MEC 服務(wù)器服務(wù)能力的增加，不同算法下卸載任務(wù)的處理時延愈發(fā)接近，但RATOS 算法和RATOM 算法的平均轉(zhuǎn)發(fā)時延保持穩(wěn)定，從而造成RATOS 算法在充足MEC 服務(wù)器服務(wù)能力下，相較于RATOM 算法有較低的時延。HRAM 算法在不同服務(wù)能力下始終保持最低的卸載任務(wù)請求時延，究其原因，與RATOS 算法相比，HRAM 算法考慮更多的候選端，在目標節(jié)點選擇上更具優(yōu)勢；與RATOM 算法相比，HRAM 算法考慮卸載任務(wù)間的影響，盡可能規(guī)避重復(fù)轉(zhuǎn)發(fā)路徑，使其具有更低的平均請求時延。本實驗中HRAM 算法相較于RATOS 算法降低40.16%的任務(wù)請求時延，相較于RATOM 算法降低19.01%的任務(wù)請求時延。實驗證實了HRAM 算法在降低任務(wù)請求時延上具有一定的優(yōu)勢。

圖7 服務(wù)能力對卸載任務(wù)平均時延的影響Fig.7 Influence of service capability on average delay of offloading tasks

圖8 顯示在不同算法下，卸載請求的總時延隨卸載任務(wù)數(shù)量變化的關(guān)系曲線。從整體來看，三種算法的總時延與卸載任務(wù)呈正相關(guān)；同時，增長速度有明顯提高。RATOS 算法的總時延變化最大，主要是由于仿真環(huán)境中1 hop 的MEC 服務(wù)器所能提供的計算資源有限，隨卸載任務(wù)的增多會出現(xiàn)不能及時響應(yīng)的現(xiàn)象，卸載任務(wù)需要排隊執(zhí)行，使得卸載請求的總時延大幅增加；HRAM 算法的總時延變化最小，主要原因是調(diào)整路徑權(quán)值，避免轉(zhuǎn)發(fā)節(jié)點多次重復(fù)選擇的現(xiàn)象。節(jié)點的發(fā)送速率固定，多次重復(fù)選擇會造成數(shù)據(jù)發(fā)送不及時、數(shù)據(jù)擁塞；同時，多個任務(wù)于同一路線同時轉(zhuǎn)發(fā)，會共享傳播速度，增加傳播時延，這也是HRAM 算法與RATOM 算法隨著卸載任務(wù)數(shù)量增加，總時延差距增大的主要原因。

圖8 卸載任務(wù)請求總時延Fig.8 Total delay of offloading task requests

本文以卸載任務(wù)的時效性作為另一個評估算法的指標。將卸載任務(wù)的請求時延不超出最大可容忍時延視為卸載成功，卸載成功的卸載任務(wù)數(shù)占卸載任務(wù)總數(shù)的比值即為卸載成功率。圖9 顯示在滿足卸載任務(wù)最大可容忍時延前提下，不同算法在不同卸載任務(wù)總數(shù)下的卸載成功率對比。整體來看，三種方案隨卸載任務(wù)數(shù)的增加，卸載成功率均呈現(xiàn)降低趨勢。仿真環(huán)境中，當卸載任務(wù)為30 時，RATOS 算法失效，此時卸載任務(wù)的請求時延均超出最大可容忍時延，任務(wù)量的需求完全超出1 hop MEC 服務(wù)器可提供的服務(wù)能力。因為隨著卸載任務(wù)總數(shù)的增加，從本地端向1 hop 目標節(jié)點轉(zhuǎn)發(fā)卸載任務(wù)時，會出現(xiàn)發(fā)送飽和；另外，MEC 服務(wù)器節(jié)點間的傳輸能力以及目標節(jié)點的服務(wù)能力均由卸載任務(wù)所均分，都會造成卸載任務(wù)響應(yīng)時間的增大，使得卸載成功率降低。對比HRAM 算法和RATOM 算法，HRAM 算法體現(xiàn)出同樣有限的服務(wù)能力，能夠滿足更多卸載任務(wù)計算需求的優(yōu)秀性能。究其原因，HRAM 算法中面向動態(tài)權(quán)值的任務(wù)轉(zhuǎn)發(fā)策略充分調(diào)用整體網(wǎng)絡(luò)的通信能力，降低重復(fù)轉(zhuǎn)發(fā)路徑的選擇可能，較RATOM 算法縮短卸載任務(wù)的發(fā)送時延和傳輸時延。

圖9 卸載成功率Fig.9 Offloading success rate

5 結(jié)語

為了更好地合理分配、有效利用MEC 服務(wù)器有限資源，減少數(shù)據(jù)多跳轉(zhuǎn)發(fā)時延，優(yōu)化卸載任務(wù)請求時延，本文提出移動邊緣計算分層協(xié)同資源配置方案，對本地端無力滿足的卸載任務(wù)，通過層次分析法，綜合考慮多因素，選擇合理的MEC 服務(wù)器目標節(jié)點來完成。

在多層式的目標節(jié)點的環(huán)境下，基于Dijkstra 算法研發(fā)隨卸載任務(wù)增加動態(tài)更新路徑權(quán)重值算法，優(yōu)化轉(zhuǎn)發(fā)路徑，減少多卸載任務(wù)、重復(fù)轉(zhuǎn)發(fā)路徑的情況。實驗結(jié)果表明，HRAMCM 算法在滿足任務(wù)最大可容忍時延的同時，能夠減少卸載任務(wù)的請求時延；在有限的服務(wù)能力內(nèi)，能夠為更多的卸載任務(wù)提供服務(wù)。在今后的研究中，將會考慮更加復(fù)雜的車聯(lián)網(wǎng)下MEC 場景。例如：增加同一車輛任務(wù)的關(guān)聯(lián)性，擴大MEC 服務(wù)器部署規(guī)模等。