陸戰(zhàn)場中的計算卸載和資源分配*

楊 力，馬偉東，郭江宇，魏德賓，張鐘錚

（1.大連大學通信與網(wǎng)絡重點實驗室，遼寧 大連 116620；2.南京理工大學，南京 210094；3.北方自動控制技術(shù)研究院，太原 030006）

0 引言

隨著戰(zhàn)場信息化建設的快速發(fā)展，戰(zhàn)場數(shù)據(jù)逐漸呈現(xiàn)出種類繁多、更新頻率大、周期短的發(fā)展趨勢［1］，簡單的信息收集無法支撐作戰(zhàn)指揮，而將具備大帶寬、低時延等特點的5G 網(wǎng)絡與具備方便攜帶、功能全面等特點的智能設備應用于陸戰(zhàn)場，可提升戰(zhàn)場通信速度，保障信息及時性和繼承性［2］，也可縮短OODA 循環(huán)時間。但是軍事需求相較于民事需求更為復雜、苛刻，對智能設備的計算能力與存儲能力也提出了更高的要求，盡管近年來智能設備的性能在不斷提升，但仍表現(xiàn)出計算資源不足、設備功耗嚴重等問題。

云計算雖在一定程度上緩解了計算資源不足的問題，但由于其部署位置較遠，造成作戰(zhàn)場景下業(yè)務處理時延高、服務質(zhì)量無法保障的問題［3］。相比之下，邊緣計算由于其部署位置更靠近網(wǎng)絡邊緣，具備低時延、高可靠、高安全、低流量等特性，符合戰(zhàn)場低時延響應的需求［4］，同時使武器具備一定的自主決策能力、簡化指戰(zhàn)員的理解操作［5］。但邊緣計算的引入也同樣帶來了額外的時延和能耗，且MEC 資源有限，因此，如何有效地制定卸載策略與優(yōu)化資源分配成為當今研究熱點。

大量學者針對上述問題展開了詳細的研究，在優(yōu)化目標方面可分為以最小化任務執(zhí)行時間為目標、以最小化設備耗能為目標等方向。隨著5G 網(wǎng)絡的應用，部分學者以5G 網(wǎng)絡為應用背景，研究了5G 網(wǎng)絡中針對接入點激增、邊緣計算系統(tǒng)負載過大等問題的卸載策略制定。文獻［6］中，KHAN 等考慮到5G 異構(gòu)網(wǎng)絡的復雜性等特性，提出了CUMS（collaborative utility-maximization scheme）卸載策略，分3 部分——MD 分組，優(yōu)化資源分配與迭代資源分配對問題進行優(yōu)化，并最終得出最優(yōu)解。除此之外，在文獻［7-10］中分別基于免疫算法、基于遺傳算法等其他啟發(fā)式算法對問題進行求解。面對5G環(huán)境下的超密集組網(wǎng)（UDN）情況，CHEN 等提出了CRADE（channel resource allocation algorithm）算法來解決任務卸載和資源優(yōu)化問題［11］。但大部分研究的對象僅是單一類型的業(yè)務，未能考慮重要業(yè)務優(yōu)先享用邊緣資源的情況［12］，面對戰(zhàn)場態(tài)勢變化頻繁、單兵穿戴設備計算能力薄弱等問題，如何綜合考量各類型任務和設備本身的特性，劃分優(yōu)先級并將其與卸載決策的制定和資源分配的優(yōu)化相結(jié)合，進而避免低優(yōu)先級任務搶占高優(yōu)先級任務資源的現(xiàn)象影響邊緣計算系統(tǒng)在軍事應用背景中的性能。

區(qū)別于現(xiàn)階段的研究，本文在所構(gòu)建的網(wǎng)絡模型中根據(jù)不同類型任務的特點，對各類型任務的卸載優(yōu)先級進行劃分，考量各類型任務對耗時與耗能的需求，以最小化系統(tǒng)開銷為目標的同時提升高卸載優(yōu)先級任務的卸載數(shù)量，構(gòu)建待優(yōu)化問題，采用不同的求解方式制定卸載決策、優(yōu)化資源分配。本文的主要工作如下：

1）構(gòu)建單小區(qū)、多用戶的邊緣計算網(wǎng)絡模型，在此網(wǎng)絡模型中討論不同計算模式下的系統(tǒng)功耗與時延。

2）根據(jù)各類型任務輸入量、計算量以及時延需求，采用AHP（層次分析法），劃分各種類型任務卸載優(yōu)先級，以此作為后續(xù)制定卸載決策的基礎。

3）根據(jù)待優(yōu)化問題的特性，將優(yōu)化問題轉(zhuǎn)化卸載決策制定與資源分配優(yōu)化兩個子問題，針對子問題1，采用改進后的免疫算法進行求解，在此基礎上，使用拉格朗日乘數(shù)法對子問題2 進行求解。

1 系統(tǒng)模型與問題分析

本章將詳細介紹本文所使用的網(wǎng)絡模型，并在此基礎上敘述任務卸載過程、討論本地計算模式和卸載計算模式下的時延構(gòu)成與能耗構(gòu)成。

1.1 網(wǎng)絡模型

本文構(gòu)建了一個單小區(qū)、多用戶的邊緣計算網(wǎng)絡模型，并根據(jù)文獻［13］將網(wǎng)絡中待卸載任務劃分為時間敏感型任務、能量消耗型任務以及成本需求型任務。如圖1 所示，網(wǎng)絡中包括一個邊緣計算服務器與若干智能設備，其中，邊緣計算服務器可配備在通信節(jié)點車輛或情報處理車輛；智能設備通過無線網(wǎng)絡向邊緣計算服務器提出卸載請求，且每個設備都攜帶一個特定類型的待計算任務。網(wǎng)絡中，認為每個智能設備在整個通信過程與卸載過程中僅通過一條穩(wěn)定的無線鏈路與基站進行交流，各無線鏈路間不存在干擾，鏈路環(huán)境穩(wěn)定。所涉的參數(shù)如下頁表1 所示。

表1 關(guān)鍵參數(shù)Table 1 Key parameters

圖1 邊緣計算網(wǎng)絡模型Fig.1 Edge computing network model

1.2 計算模型

為方便表達，本文將任務描述成四元組，即I={Dk，Ck，Pk，Rk}。其中，Dk表示任務的輸入量；Ck表示完成任務所需要的計算量；Pk表示任務的優(yōu)先級；Rk表示結(jié)果大小。由于任務可以選擇卸載執(zhí)行或本地執(zhí)行，接下來將從本地計算與卸載計算兩個模式討論計算過程中的耗時與耗能

1.2.1 本地計算模式

其中，式（1）表示任務本地執(zhí)行的耗時；式（2）表示任務本地執(zhí)行耗能；ξ 代表與芯片硬件架構(gòu)相關(guān)的功耗系數(shù)。

1.2.2 卸載計算模式

卸載計算模式下，各設備通過無線傳輸?shù)姆绞脚c邊緣計算服務器溝通，并將任務卸載至邊緣計算服務器進行執(zhí)行，計算結(jié)果通過無線網(wǎng)絡回傳至相應設備。此模式下的時延分別由任務上傳時延、任務執(zhí)行時延與結(jié)果回傳時延構(gòu)成，由于計算任務的輸出結(jié)果大小遠小于輸入量大小，故忽略因結(jié)果回傳而帶來的時延與功耗。由此，可將卸載模式時延表示為：

1.3 問題分解

基于以上分析，可進一步將設備k 的耗能與耗時歸納為：

式中，dk表示設備k 是否選擇卸載任務；dk=0 表示選擇本地執(zhí)行任務，反之為卸載執(zhí)行。進而根據(jù)不同類型任務對時延和功耗的不同需求，將執(zhí)行任務k 的系統(tǒng)開銷定義為：

綜上所述，以降低系統(tǒng)開銷為目標優(yōu)化卸載決策與資源分配，并表達為：

其中，條件c1 表示設備k 的任務僅能選擇本地執(zhí)行或卸載執(zhí)行；條件c2 表示被卸載的任務總數(shù)不能超過MEC Sever 可服務任務數(shù)的上限；條件c3、c4 表示分配給各個卸載任務計算資源的取值范圍，且總和不能超過MEC Sever 的總計算資源；條件c5 與c6 表示時間參數(shù)與功耗參數(shù)的取值范圍及關(guān)系。

由于卸載策略為離散型變量，而計算資源為連續(xù)性變量，故待式（12）為MINP（混合整數(shù)非線性規(guī)劃問題），直接對其求解存在極大的困難，為了方便求解，將上述問題解耦成兩個子問題，解耦后的兩個問題為：1）卸載策略制定問題；2）資源分配優(yōu)化問題。

2 問題求解

2.1 卸載優(yōu)先級劃分

不同類型的任務具有不同的數(shù)據(jù)輸入量、時延要求及計算要求，難以根據(jù)單一的任務屬性劃分其卸載優(yōu)先級，對此，本文采用多屬性決策AHP 予以解決。

首先，如式（13）所示，構(gòu)建矩陣

可見矩陣A 為一致陣，根據(jù)一致陣每一個列向量都是特征向量的特性，本文采取簡化計算法計算矩陣的特征向量與特征值，過程如下：

計算后的特征向量為：

時延敏感型任務卸載優(yōu)先級> 能量消耗型任務卸載優(yōu)先級>成本需求型任務卸載優(yōu)先級。符合戰(zhàn)場在信息收集和行動指揮方面低時延的需求。

2.2 基于免疫算法的卸載決策的制定

將上文中所涉及的subProblem1 表示為：

可見式（14）為NP 問題，直接求解復雜且困難。為解決式（14），本文參考文獻［16-17］，采取啟發(fā)式算法求解，由于免疫算法具有“確定”與“隨機”結(jié)合與全局尋優(yōu)的特點，本文擬將任務卸載優(yōu)先級與免疫算法結(jié)合，改進免疫算法中的變異操作，使算法在以最小化開銷為目標的求解過程中，將更多的高卸載優(yōu)先級任務卸載至邊緣計算服務器。詳細過程如算法1 所示。

算法根據(jù)設備數(shù)生成相應數(shù)量的待卸載任務，并根據(jù)其他限制條件生成數(shù)量為S 的初始種群，即備選解。當進化代數(shù)為0，即初代種群，算法根據(jù)下述各式計算各個抗體的目標值、濃度、親和度及激勵值等參數(shù)，并根據(jù)排序結(jié)果，選擇初代最優(yōu)抗體。當算法進入迭代階段，通過反復計算上述各值，并根據(jù)激勵值選擇抗體進行克隆、交叉操作。結(jié)合任務卸載優(yōu)先級的概念，對抗體進行變異操作。變異操作結(jié)束后，針對變異后的抗體采取克隆抑制操作，選取目標值低、濃度低的個體進入下一代種群，保證種群多樣性。每次迭代后都將本代最優(yōu)抗體與當前最優(yōu)抗體進行比較，生成新的最優(yōu)抗體，直至算法迭代次數(shù)達到最大，算法最后輸出的最優(yōu)抗體即為卸載決策。

算法1.基于免疫算法的卸載策略制定輸入：種群個體S，迭代次數(shù)T，交叉率pc，變異率images/BZ_22_2075_578_2225_621.png編碼長度CHROMLENGTH.初始化：生成CHROMLENGTH 個卸載任務，生成S 個個體將最優(yōu)解的目標值初始化為Ibest=∞。標記任務優(yōu)先級while iteration ≤T do for i=0 to S do依據(jù)式（14）計算個體目標值依據(jù)式（19）計算個體親和度依據(jù)式（20）計算個體激勵值end for免疫選擇操作for i=1 to S do隨機選取兩個抗體以交叉率pc 執(zhí)行交叉操作end for for i=1 to S do隨機選取一個基因位，依據(jù)式（21）進行變異操作end for克隆抑制操作，選取低目標值、低濃度抗體并形成新種群查詢本次迭代后最優(yōu)抗體的images/BZ_22_1731_1547_1787_1593.pngif images/BZ_22_1313_1606_1464_1651.pngthenimages/BZ_22_1285_1664_1445_1710.pngend if end while輸出：Offloading strategy A

算法1 中，依據(jù)式（15）、式（16）計算各抗體間相似度，

進而依據(jù)式（17）、式（18）計算抗體濃度，其中，rad 為相似度閾值，

依據(jù)式（14）、式（19）分別計算各個抗體的目標值與親和度，

根據(jù)式（20）計算各抗體的激勵值。

為模仿基因突變過程以獲取更優(yōu)結(jié)果，算法對克隆后的抗體將進行變異操作。依據(jù)抗體長度隨機生成變異位；判斷變異位任務所屬的優(yōu)先級，如式（21）所示，根據(jù)不同任務卸載優(yōu)先級的變異率進行變異；重復此操作直至所有克隆個體都經(jīng)歷變異過程。針對過程中存在的不合理個體，算法采取遺棄并補充新抗體重新進行變異操作的處理方式。

2.3 基于拉格朗日乘數(shù)法的資源分配優(yōu)化

通過上述方法，已經(jīng)獲得卸載決策，由于sub-Problem2 為有約束條件最優(yōu)化問題，故在上述研究的基礎上，使用拉格朗日乘數(shù)法對subProblem2 進行精準求解，具體如下。

將subProblem2 表示為：

并將其與約束條件構(gòu)建成如下拉格朗日函數(shù)：

結(jié)合約束條件，即可獲得最終結(jié)果：

3 仿真及結(jié)果分析

本章將對上述算法進行實驗仿真，驗證其可行性與優(yōu)越性。本文對時間敏感型任務、能量消耗型任務與成本需求型任務設置同文獻［18-20］，并取各自平均值，如表2 所示，實驗其他設置如表3 所示。

表2 任務設置Table 2 Task settings

表3 仿真參數(shù)設置Table 3 Simulation parameter settings

為方便比較，共設置以下幾種情況：

1）全本地模式：所有待執(zhí)行任務不進行卸載，全部本地執(zhí)行；

2）全卸載模式：在滿足約束的條件下，將所有任務卸載至MEC Sever 進行執(zhí)行，不在本地執(zhí)行；

3）改進算法：即本文所討論的結(jié)合任務卸載優(yōu)先級的免疫算法，通過多次迭代求解卸載決策，并結(jié)合拉格朗日乘數(shù)法，獲取最終系統(tǒng)開銷；

4）傳統(tǒng)算法：即未改進的免疫算法，默認認為所有任務都是同等優(yōu)先級，在執(zhí)行變異操作過程中不細致區(qū)分，且計算資源分配方式為平均分配。

3.1 算法收斂性分析

針對式（14）的求解過程雖包含兩個階段，但算法的收斂性僅與改進后的免疫算法有關(guān)，故僅對其進行收斂性驗證。本文在用戶總數(shù)為15 個且每個用戶僅攜帶一個待卸載任務的條件下，針對時間敏感型任務在總?cè)蝿罩姓急葹?0%、60%、80%三種情況進行驗證，仿真結(jié)果如圖2 所示。

圖2 算法斂散性Fig.2 Convergence of algorithms

由圖2 可知，改進后的免疫算法運行先期呈現(xiàn)逐步降低趨勢，高卸載優(yōu)先級任務不同占比情況下雖略有差別，但當?shù)螖?shù)達到80 代左右時，所有情況的系統(tǒng)開銷變化甚微，直至1 000 代算法結(jié)束，基本保持不變。由此可知，改進后的免疫算法具有收斂性。

3.2 系統(tǒng)開銷及卸載數(shù)量分析

針對系統(tǒng)開銷問題，在逐步增加用戶數(shù)量的同時考量高卸載優(yōu)先級任務在不同占比情況下的系統(tǒng)開銷大小，如圖3 所示。

圖3 系統(tǒng)開銷Fig.3 System overhead

如圖3（a）所示，若高卸載優(yōu)先級任務占比為40%，當用戶數(shù)量較小時，改進后的免疫算法雖比全本地模式與傳統(tǒng)算法具備更低的系統(tǒng)開銷，但表現(xiàn)仍不如全卸載模式。當用戶數(shù)量到達35 個后，全卸載模式的系統(tǒng)開銷高于改進后的算法與傳統(tǒng)算法，這是由于隨著用戶數(shù)量的增大，邊緣計算服務器中有限的計算資源不能夠滿足所有任務的計算需求，影響任務執(zhí)行質(zhì)量。圖3（b），圖3（c）所顯示的情況大致與圖3（a）相同，改進算法分別于用戶數(shù)量30個和25 個左右時表現(xiàn)優(yōu)于全卸載模式。且隨著高優(yōu)先級任務占比的逐步提升，系統(tǒng)開銷逐漸減少，這是因為高優(yōu)先級任務輸入量與計算量都小于其他兩種類型的計算任務，當高優(yōu)先級任務占比較少時，其他兩種任務占比較多，故而系統(tǒng)開銷較大。

針對高卸載優(yōu)先級任務被卸載數(shù)量問題，仿真結(jié)果如圖4 所示。

圖4 高優(yōu)先級任務卸載數(shù)量Fig.4 Number of high-priority tasks unloaded

由圖4（a）可知，當高卸載優(yōu)先級任務占比為40%時，改進算法的高卸載優(yōu)先級任務卸載數(shù)量少于傳統(tǒng)算法的高卸載優(yōu)先級任務卸載數(shù)量，這是因為傳統(tǒng)算法在進行變異操作時，不區(qū)分任務卸載優(yōu)先級，導致低卸載優(yōu)先級任務和高卸載優(yōu)先級任務具備同樣地位，使得低卸載優(yōu)先級任務搶占高卸載優(yōu)先級任務的卸載機會。由圖4（b）、圖4（c）可知，隨著高優(yōu)先級任務占比的增加與任務數(shù)量的增加，改進算法的卸載數(shù)量呈現(xiàn)大于傳統(tǒng)算法的卸載數(shù)量的趨勢。當高卸載優(yōu)先級任務占比較多時，改進算法可使更多的高卸載優(yōu)先級任務被卸載執(zhí)行。結(jié)合針對圖3 的分析可知，改進算法實現(xiàn)了降低系統(tǒng)開銷的同時增加高卸載優(yōu)先級任務卸載數(shù)量的目標。

3.3 算法卸載率分析

由圖5 可知，無論高卸載優(yōu)先級任務占比如何，改進算法的最終卸載率都由初始的1.0 左右逐步降低至0.5～0.6 左右。這是因為當用戶數(shù)量較少時，邊緣計算服務器可滿足有所任務的卸載需求，但MEC Sever 服務能力有限，隨著用戶數(shù)量的增加，邊緣計算服務器不得不拒絕部分卸載請求，當達到最大可卸載數(shù)量后，剩余任務將在本地執(zhí)行，故圖5呈現(xiàn)逐步降低趨勢。

圖5 卸載率Fig.5 Unloading rate

4 結(jié)論

本文以陸戰(zhàn)場為應用背景，提出了一種考慮任務卸載優(yōu)先級的卸載策略制定和資源分配優(yōu)化解決方法。基于所提出的單邊緣計算服務器、多用戶網(wǎng)絡模型，討論了不同模式下的耗時模型、耗能模型；將難于直接求解的問題分解為兩個易于求解的子問題，并分別采用改進后的免疫算法與拉格朗日乘數(shù)法求解，意在降低系統(tǒng)開銷的同時使更多的高卸載優(yōu)先級任務能夠被卸載至網(wǎng)絡邊緣。經(jīng)過實驗仿真，驗證了改進后算法的收斂性與優(yōu)越性。

在未來工作中，將以此研究為基礎，把針對任務卸載優(yōu)先級的卸載策略推廣至星地結(jié)合網(wǎng)絡環(huán)境中，并繼續(xù)優(yōu)化包括無線資源、發(fā)射功率在內(nèi)的其他資源分配。同時結(jié)合機器學習的思想，將戰(zhàn)場任務分類細致化、準確化，將卸載優(yōu)先級劃分合理化，為戰(zhàn)場指揮提供技術(shù)支撐。