分層學(xué)習(xí)的邊緣計(jì)算資源調(diào)度粒子群優(yōu)化算法

胡曉敏，陳鎮(zhèn)填，李 敏，2

1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

2.廣東工業(yè)大學(xué) 信息工程學(xué)院，廣州 510006

隨著物聯(lián)網(wǎng)行業(yè)的發(fā)展，智能移動(dòng)設(shè)備的數(shù)量快速增長，相應(yīng)的智能移動(dòng)應(yīng)用服務(wù)程序也越來越多，在教育、商業(yè)、游戲、安全和醫(yī)療保健等各個(gè)領(lǐng)域都有相關(guān)的智能移動(dòng)應(yīng)用程序[1]。這些應(yīng)用程序要求設(shè)備提供較高的服務(wù)質(zhì)量，如低延遲、數(shù)據(jù)安全和隱私保護(hù)，并且一臺(tái)智能移動(dòng)設(shè)備上往往會(huì)運(yùn)行多種應(yīng)用程序，對設(shè)備的硬件條件，特別是設(shè)備的計(jì)算能力和電池容量提出了較高的要求。然而，智能移動(dòng)設(shè)備具有便攜性和移動(dòng)性的特點(diǎn)，其硬件條件無法滿足應(yīng)用程序的服務(wù)質(zhì)量需求。邊緣計(jì)算技術(shù)為解決智能移動(dòng)設(shè)備在計(jì)算資源和能耗上的需求提供了手段。

邊緣計(jì)算是指在網(wǎng)絡(luò)邊緣執(zhí)行計(jì)算的一種新型計(jì)算模型[2]，通過使用部署在網(wǎng)絡(luò)邊緣的設(shè)備（如工作站、通信基站等）對終端設(shè)備（如智能家居、移動(dòng)設(shè)備等）產(chǎn)生的數(shù)據(jù)進(jìn)行處理，由邊緣計(jì)算設(shè)備提供計(jì)算能力，大大降低了對終端設(shè)備的硬件要求。如何更有效地利用邊緣計(jì)算設(shè)備的資源，降低終端設(shè)備的能耗，成為了邊緣計(jì)算資源調(diào)度的核心問題。針對這一問題，越來越多的研究人員通過研究計(jì)算卸載決策（computation offloading decision）和資源分配（resource allocation）這兩個(gè)方面來減少設(shè)備的能源消耗。Yang等人[3]在一個(gè)多服務(wù)器，多用戶設(shè)備構(gòu)成的計(jì)算模型中，針對移動(dòng)設(shè)備能耗問題提出了改進(jìn)的分支定界算法，從卸載決策和計(jì)算資源這兩方面進(jìn)行優(yōu)化，降低移動(dòng)設(shè)備的能源消耗。Guo等人[4]則提出了一種基于計(jì)算算法的遺傳算法（genetic algo‐rithm based computation algorithm），用于多服務(wù)器和多用戶設(shè)備組成的邊緣計(jì)算模型的能耗優(yōu)化問題，通過卸載決策，信道分配和資源分配這三個(gè)方面來降低用戶設(shè)備的能源消耗。Huang等人[5]提出多用戶合作的移動(dòng)邊緣計(jì)算卸載系統(tǒng)，移動(dòng)設(shè)備不僅可以將計(jì)算任務(wù)卸載給邊緣服務(wù)器完成，也可以選擇卸載給其他空閑的移動(dòng)設(shè)備。為了降低移動(dòng)設(shè)備計(jì)算能耗，作者提出了一種基于蟻群算法的雙層優(yōu)化方法，對移動(dòng)邊緣計(jì)算中的任務(wù)卸載決策和資源分配問題進(jìn)行聯(lián)合優(yōu)化，在滿足延遲約束下使得所有移動(dòng)用戶的總消耗最小化。

在邊緣計(jì)算能耗優(yōu)化問題上需要對多方面資源進(jìn)行合理的調(diào)度，如網(wǎng)絡(luò)信道分配、數(shù)據(jù)分流比例和計(jì)算資源分配，并且還會(huì)考慮最大延遲等多方面約束。因此邊緣計(jì)算的能耗優(yōu)化問題是一個(gè)復(fù)雜的非線性規(guī)劃問題[6]，傳統(tǒng)的數(shù)學(xué)優(yōu)化算法無法在合理的時(shí)間內(nèi)得到其最優(yōu)解。

模擬自然界群體協(xié)作尋優(yōu)的群體智能算法，憑借其強(qiáng)大的全局搜索能力和尋優(yōu)能力，更少的計(jì)算代價(jià)和更快的收斂速度被廣泛應(yīng)用。其中粒子群優(yōu)化算法具有收斂速度快，設(shè)置參數(shù)少等特征，是求解一些實(shí)際工程問題的首要選擇。根據(jù)利用粒子群算法優(yōu)化計(jì)算卸載問題的方式，已有的做法可以分為三類：第一類是對粒子群算法的操作進(jìn)行改進(jìn)。如Adhikari等人[7]提出的加速粒子群算法，使用全局最優(yōu)個(gè)體來更新個(gè)體的速度和位置，目的是提高算法的收斂速度。Deng[8]和Wang[9]等人改進(jìn)了粒子群算法的慣性系數(shù)計(jì)算公式，根據(jù)粒子的適應(yīng)度值動(dòng)態(tài)地改變慣性系數(shù)。第二類是把粒子群算法與其他進(jìn)化算法相結(jié)合。如Chen等人[10]將粒子群算法與遺傳算法相結(jié)合，解決卸載深度網(wǎng)絡(luò)中間層的決策問題。第三種是利用粒子群算法解決任務(wù)卸載問題中的子問題。如Zhou等人[11]為解決超密集異構(gòu)網(wǎng)絡(luò)中的計(jì)算卸載問題，先采用遺傳算法進(jìn)行粗粒度搜索，再用粒子群算法進(jìn)行細(xì)粒度搜索得出最優(yōu)的計(jì)算卸載決策。Xue等人[12]提出粒子群和遺傳算法相結(jié)合的算法用于大型深度神經(jīng)網(wǎng)絡(luò)的遷移決策問題，提出層合并上傳算法解決上傳問題。Liu等人[13]則將概率任務(wù)卸載問題分解成多個(gè)無約束子問題，使用粒子群算法去求解每個(gè)子問題從而得到概率任務(wù)卸載問題的最優(yōu)解。

然而，上述提到的研究中都只是研究如何降低智能移動(dòng)設(shè)備端的能耗和網(wǎng)絡(luò)傳輸?shù)哪芎?，很少將邊緣服?wù)器端的能耗作為優(yōu)化目標(biāo)。對于提供云計(jì)算服務(wù)的企業(yè)來說，他們需要考慮如何充分利用服務(wù)器的計(jì)算資源，降低服務(wù)器的能耗，增加機(jī)器的使用時(shí)間，減少企業(yè)成本。受此啟發(fā)，針對優(yōu)化資源配置，減少設(shè)備能耗問題，本文對與計(jì)算任務(wù)和計(jì)算能耗的相關(guān)參數(shù)進(jìn)行建模，將降低服務(wù)器能耗作為優(yōu)化目標(biāo)之一，提出了與移動(dòng)設(shè)備計(jì)算能耗、數(shù)據(jù)傳輸能耗和邊緣服務(wù)器計(jì)算能耗相關(guān)的總能耗公式，并且增加了對邊緣服務(wù)器相關(guān)計(jì)算資源的限制作為新的約束條件，如邊緣服務(wù)器的存儲(chǔ)約束，最大能耗約束和CPU周期約束。

本文采用粒子群算法對總能耗優(yōu)化問題進(jìn)行求解，優(yōu)化每臺(tái)移動(dòng)設(shè)備對于移動(dòng)設(shè)備的計(jì)算速度，下載數(shù)據(jù)功耗，數(shù)據(jù)卸載百分比和剩余網(wǎng)絡(luò)帶寬占這四個(gè)參數(shù)的取值，更合理分配計(jì)算資源使得總能耗最小。針對粒子群存在容易陷入局部最優(yōu)和種群多樣性低等問題，本文引入分層學(xué)習(xí)策略對算法進(jìn)行改進(jìn)，通過分層學(xué)習(xí)的方式保存種群粒子的多樣性和提高算法全局搜索能力，并將改進(jìn)的算法稱為基于分層學(xué)習(xí)的粒子群算法（levelbased learning swarm optimizer，LLSO）。

1 問題建模

1.1 系統(tǒng)模型

考慮到智能移動(dòng)設(shè)備有限的計(jì)算資源，無法按需求完成計(jì)算任務(wù)，需要將部分或者全部計(jì)算任務(wù)傳輸給邊緣服務(wù)器處理，因此提出了用于聯(lián)合優(yōu)化的計(jì)算分流系統(tǒng)模型，如圖1所示。在圖1中，假設(shè)存在M臺(tái)智能移動(dòng)設(shè)備和S個(gè)支持上行和下行功能的傳輸通道，M臺(tái)智能移動(dòng)設(shè)備可以通過S個(gè)傳輸通道發(fā)送自己的計(jì)算數(shù)據(jù)和接受邊緣服務(wù)器的計(jì)算結(jié)果，并且傳輸通道之間不存在干擾。優(yōu)化算法會(huì)收集智能移動(dòng)設(shè)備和邊緣服務(wù)器的硬件資源信息，并且收集移動(dòng)設(shè)備需要運(yùn)行的計(jì)算任務(wù)和相關(guān)約束，在滿足所有約束條件的情況下，如計(jì)算延遲約束，移動(dòng)設(shè)備和服務(wù)器的最大能耗約束等，決定每臺(tái)設(shè)備最優(yōu)的執(zhí)行方案，合理地調(diào)整計(jì)算資源和規(guī)劃計(jì)算任務(wù)卸載比例，從而能夠消耗最少的移動(dòng)設(shè)備計(jì)算能耗，傳輸能耗和邊緣服務(wù)器計(jì)算能耗。

圖1 計(jì)算卸載系統(tǒng)模型Fig.1 Computation offloading system model

1.2 能耗優(yōu)化建模

智能移動(dòng)設(shè)備和邊緣服務(wù)器的總能耗是由每臺(tái)智能移動(dòng)設(shè)備的本地計(jì)算能耗ELm，服務(wù)器處理每臺(tái)智能移動(dòng)設(shè)備分流數(shù)據(jù)產(chǎn)生的計(jì)算能耗ECm以及數(shù)據(jù)傳輸過程產(chǎn)生的傳輸能耗ηm這三個(gè)方面構(gòu)成，計(jì)算公式如下：

每臺(tái)智能移動(dòng)設(shè)備的本地計(jì)算能耗ELm與設(shè)備的計(jì)算功率和工作時(shí)長有關(guān)[14]，用PLm表示單臺(tái)智能移動(dòng)設(shè)備的計(jì)算功率，用tLm表示單臺(tái)智能移動(dòng)設(shè)備的工作時(shí)長，因此可以得到本地計(jì)算能耗ELm的計(jì)算公式為：

以上公式中計(jì)算功率與智能移動(dòng)設(shè)備的計(jì)算速度有關(guān)。用fm表示編號(hào)第m臺(tái)智能移動(dòng)設(shè)備的計(jì)算速度，單位cycle/s，因此，智能移動(dòng)設(shè)備的計(jì)算功率可以通過下面的公式計(jì)算得到：

其中，kL為智能移動(dòng)設(shè)備芯片結(jié)構(gòu)相關(guān)的一個(gè)常數(shù)，其值與移動(dòng)設(shè)備的硬件條件相關(guān)。

工作時(shí)長與智能移動(dòng)設(shè)備需要處理的計(jì)算數(shù)據(jù)量和數(shù)據(jù)復(fù)雜性相關(guān)，數(shù)據(jù)量越多，數(shù)據(jù)的復(fù)雜性越大，計(jì)算速度越慢，需要的工作時(shí)長就越長。根據(jù)文獻(xiàn)[15]，使用Im表示第m臺(tái)智能移動(dòng)設(shè)備需要計(jì)算的數(shù)據(jù)量，使用一個(gè)常數(shù)α來表示所有計(jì)算數(shù)據(jù)的復(fù)雜性。由于模型中會(huì)將部分?jǐn)?shù)據(jù)分流到服務(wù)器去計(jì)算，因此使用λm表示第m臺(tái)智能移動(dòng)設(shè)備在本地計(jì)算的數(shù)據(jù)量占總數(shù)據(jù)量的比例，其取值范圍為[0，1]。根據(jù)以上關(guān)系，可以得到智能移動(dòng)設(shè)備的工作時(shí)長計(jì)算公式如下：

單臺(tái)智能移動(dòng)設(shè)備的計(jì)算能耗根據(jù)公式（2）~（4）化簡之后如下所示：

可見單臺(tái)智能移動(dòng)設(shè)備的計(jì)算能耗與智能移動(dòng)設(shè)備芯片結(jié)構(gòu)，智能移動(dòng)設(shè)備的計(jì)算速度，需要計(jì)算的數(shù)據(jù)量和數(shù)據(jù)的復(fù)雜性有關(guān)。假設(shè)每臺(tái)智能移動(dòng)設(shè)備的電池容量有限，用ELmax表示每臺(tái)智能移動(dòng)設(shè)備能夠用于計(jì)算的最大能耗，因此每臺(tái)移動(dòng)設(shè)備在處理數(shù)據(jù)所消耗的能源需滿足：

與智能移動(dòng)設(shè)備本地的計(jì)算能耗類似，邊緣服務(wù)器的計(jì)算能耗也是通過邊緣服務(wù)器的功率P和計(jì)算時(shí)間tCm的乘積計(jì)算得來，經(jīng)相同的推導(dǎo)和化簡后如公式（7）所示。在公式（7）中，用ECm表示服務(wù)器處理第m臺(tái)智能移動(dòng)設(shè)備分流數(shù)據(jù)產(chǎn)生的計(jì)算能耗，而第m臺(tái)智能移動(dòng)設(shè)備會(huì)保留λm的數(shù)據(jù)量在本地計(jì)算，所以服務(wù)器需要處理的數(shù)據(jù)量是(1-λm)·Im。具體公式如下：

其中，kC是與邊緣服務(wù)器芯片結(jié)構(gòu)相關(guān)的一個(gè)常數(shù)，fC表示邊緣服務(wù)器的計(jì)算速度這兩個(gè)參數(shù)都與服務(wù)器的硬件條件相關(guān)。用ECmax表示服務(wù)器的最大能耗限制，因此，服務(wù)器在處理所有移動(dòng)設(shè)備的數(shù)據(jù)產(chǎn)生的能耗要滿足：

同時(shí)，對于邊緣服務(wù)器接收M臺(tái)智能移動(dòng)設(shè)備傳輸過來的總數(shù)據(jù)量也有一定的限制，通過服務(wù)器最大CPU周期數(shù)Amax和服務(wù)器最大內(nèi)存存儲(chǔ)空間Gmax來表現(xiàn)，具體約束如下：

其中，α表示數(shù)據(jù)量的復(fù)雜性，而ζ表示每比特的數(shù)據(jù)所占用的內(nèi)存空間。

對于第m臺(tái)智能移動(dòng)設(shè)備在傳輸數(shù)據(jù)到服務(wù)器的過程中的數(shù)據(jù)傳輸能耗ηm計(jì)算公式如下：

這個(gè)公式求和的兩個(gè)部分分別代表數(shù)據(jù)傳輸中的上行鏈路能耗和下行鏈路能耗。其中，PIL表示智能移動(dòng)設(shè)備的閑置功率，kTL表示智能移動(dòng)設(shè)備傳輸數(shù)據(jù)的增強(qiáng)系數(shù)，PTm表示智能移動(dòng)設(shè)備傳輸數(shù)據(jù)的功率，PDL表示智能移動(dòng)設(shè)備下載數(shù)據(jù)的功率，下標(biāo)L代表這些參數(shù)跟本地智能移動(dòng)設(shè)備相關(guān)。

γm表示第m臺(tái)智能移動(dòng)設(shè)備在每條傳輸通道上所占用的帶寬比例，其取值范圍為[0，1]，為確保最大限度地利用帶寬，γm需要滿足：

tU表示智能移動(dòng)設(shè)備上傳數(shù)據(jù)所需要的時(shí)間，tD表示數(shù)據(jù)從服務(wù)器傳回智能移動(dòng)設(shè)備的時(shí)間。tU、tD分別通過以下公式計(jì)算：

其中，RUm和RDm分別表示上行鏈路的和下行鏈路的信道傳輸速率，β1、β2分別表示在上傳和下載數(shù)據(jù)過程中的額外開銷。

數(shù)據(jù)傳輸能耗與傳輸時(shí)間有關(guān)，而數(shù)據(jù)傳輸時(shí)間跟信道傳輸速率相關(guān)。信道傳輸速率與數(shù)據(jù)占用的信道帶寬W，數(shù)據(jù)傳輸功率PT和噪聲干擾功率N0相關(guān)。在數(shù)據(jù)傳輸過程中存在干擾而導(dǎo)致信道衰弱現(xiàn)象，假設(shè)該模型的數(shù)據(jù)傳輸信道為瑞利衰落信道。根據(jù)文獻(xiàn)[14]，上行鏈路和下行鏈路的傳輸分別在不同的頻率上進(jìn)行。數(shù)據(jù)傳輸之間的路徑損耗用(dm)-v表示，dm表示第m臺(tái)智能移動(dòng)設(shè)備到服務(wù)器的距離，v則表示路徑衰減指數(shù)。h1、h2分別表示上行鏈路和下行鏈路的信道衰減系數(shù)。因此，鏈路的信道傳輸速率為通道數(shù)量S，傳輸帶寬占比γm，鏈路帶寬W，與數(shù)據(jù)傳輸功率衰減和噪聲干擾有關(guān)的對數(shù)函數(shù)的乘積。上行鏈路的速率RUm和下行鏈路的速率RDm的計(jì)算公式為：

其中，S表示通道數(shù)量。WU和WD分別表示上行鏈路和下行鏈路的帶寬。PTC表示服務(wù)器的傳輸數(shù)據(jù)的功率，N0表示高斯白噪聲的功率。以上這些參數(shù)的取值都與對應(yīng)的物理網(wǎng)絡(luò)設(shè)備有關(guān)。

智能移動(dòng)設(shè)備將部分?jǐn)?shù)據(jù)分流給服務(wù)器完成計(jì)算的時(shí)間tC的計(jì)算如公式（17），該時(shí)間包括數(shù)據(jù)上傳時(shí)間tU、數(shù)據(jù)下載時(shí)間tD和服務(wù)器處理第m臺(tái)智能移動(dòng)設(shè)備數(shù)據(jù)的時(shí)間tCm這三部分。

其中，上傳數(shù)據(jù)時(shí)間tU和數(shù)據(jù)傳回時(shí)間tD由公式（14）和（15）計(jì)算得到，而服務(wù)器處理數(shù)據(jù)的時(shí)間tCm與需要處理的數(shù)據(jù)量有關(guān)，具體計(jì)算公式如下：

大多數(shù)智能移動(dòng)設(shè)備上的應(yīng)用程序都有相應(yīng)的延遲需求，最大完成時(shí)間包含兩個(gè)方面，一方面是智能移動(dòng)設(shè)備本地計(jì)算的時(shí)間tLm，由公式（4）計(jì)算得到，另一方面就是智能移動(dòng)設(shè)備將部分?jǐn)?shù)據(jù)卸載到服務(wù)器完成計(jì)算的時(shí)間tC。由于這兩方面的計(jì)算是并行進(jìn)行的，花費(fèi)時(shí)間較多的那部分時(shí)間視為該計(jì)算任務(wù)的最終完成時(shí)間，因此該計(jì)算任務(wù)的最終完成時(shí)間需要滿足：

其中，Lmax表示應(yīng)用程序的延遲限制，即智能移動(dòng)設(shè)備處理數(shù)據(jù)的最大完成時(shí)間。

2 基于分層學(xué)習(xí)的粒子群算法

粒子群算法因?yàn)槠浣Y(jié)構(gòu)簡單，收斂速度快等特點(diǎn)，受到國內(nèi)外大量的研究，并應(yīng)用到與各種實(shí)際問題中[16-17]。但是在解決復(fù)雜的約束問題時(shí)，粒子群算法存在容易陷入局部最優(yōu)和缺失種群多樣性等問題。因此，本文采用了分層學(xué)習(xí)的策略來對傳統(tǒng)的粒子群算法進(jìn)行改進(jìn)，提出了利用基于分層學(xué)習(xí)的粒子群算法（levelbased learning swarm optimizer，LLSO），來提高PSO面對復(fù)雜優(yōu)化問題時(shí)的全局搜索能力和種群多樣性。

2.1 優(yōu)化目標(biāo)函數(shù)

本文的優(yōu)化目標(biāo)是最小化如公式（1）所示的所有本地設(shè)備的計(jì)算能耗，數(shù)據(jù)傳輸能耗和邊緣服務(wù)器計(jì)算能耗的總和。由于同時(shí)還需要滿足各種約束，如延遲約束，服務(wù)器存儲(chǔ)約束，移動(dòng)設(shè)備和服務(wù)器最大能耗約束以及傳輸網(wǎng)絡(luò)的帶寬約束，本文將所有的約束條件轉(zhuǎn)化成對應(yīng)的懲罰函數(shù)，因此優(yōu)化目標(biāo)是最小化總能耗和懲罰函數(shù)值的和，即：

其中，Ω表示所有懲罰函數(shù)值的總和，N為正整數(shù)，表示懲罰函數(shù)的權(quán)重，x代表問題的解。

懲罰函數(shù)Ω的計(jì)算方式如下：

其中，y1、y2為指數(shù)常量，分別取值為2和1。gp(x)表示不等式約束的懲罰函數(shù)，p=1,2,…,5。hq表示等式約束的懲罰函數(shù)，具體公式如下：

公式（22）到（27）分別是由移動(dòng)設(shè)備最大能耗約束（6），服務(wù)器最大能耗約束（8），服務(wù)器CPU計(jì)算周期約束（9），服務(wù)器存儲(chǔ)約束（10），延遲約束（19）和帶寬約束（12）轉(zhuǎn)化的各類懲罰函數(shù)。對于不等式約束，如果差值小于0，說明沒有違反約束情況，懲罰值設(shè)為0，若差值大于0，說明違反了約束條件，將差值設(shè)為懲罰值。對于等式約束，差值不等于0表明違反約束，并用差值的絕對值表示懲罰值。

2.2 個(gè)體編碼

LLSO算法的解向量x表示當(dāng)前所有智能移動(dòng)設(shè)備的資源分配情況，由智能移動(dòng)設(shè)備相關(guān)的四個(gè)參數(shù)構(gòu)成：智能移動(dòng)設(shè)備的計(jì)算速度fm，智能移動(dòng)設(shè)備下載數(shù)據(jù)的功耗PTm，計(jì)算數(shù)據(jù)卸載百分比λm和剩余網(wǎng)絡(luò)帶寬占比μm。假設(shè)智能移動(dòng)設(shè)備的數(shù)量為M，向量x的長度是4M，其中第1到M的元素存放每臺(tái)智能移動(dòng)設(shè)備的計(jì)算速度fm，接下來的M個(gè)元素存放智能移動(dòng)設(shè)備的功耗PTm，接著存放M個(gè)分流百分比λm，最后的M個(gè)位置存放 參 數(shù) μm，最 終 向 量x的 編 碼 方 式 如 下x=(f1,f2,…fM,PT1,PT2,…,PTM,λ1,λ2,…,λM,μ1,μ2,…,μM)。算法通過不斷迭代優(yōu)化，調(diào)整設(shè)備的計(jì)算功率參數(shù)，數(shù)據(jù)卸載比例以及傳輸網(wǎng)絡(luò)帶寬比例，最終輸出的結(jié)果就是能耗最低的資源分配方式。同時(shí)LLSO算法中每個(gè)粒子會(huì)維護(hù)一個(gè)速度向量v。速度向量v是保存每個(gè)粒子的速度，表示資源分配變化的范圍，向量v的長度也是4M，分別存放著每臺(tái)智能移動(dòng)設(shè)備不同參數(shù)對應(yīng)的不同速度值。

2.3 算法流程

在算法開始運(yùn)行前會(huì)先進(jìn)行初始化粒子操作，在四個(gè)參數(shù)不同的取值范圍內(nèi)隨機(jī)生成一個(gè)浮點(diǎn)數(shù)。四個(gè)優(yōu)化參數(shù)對應(yīng)取值范圍為fm∈[0,fmax]，PTm∈[0,Pmax]，λm∈[0,1]，μm∈[0,1]。其中fmax表示智能移動(dòng)設(shè)備的最快計(jì)算速度，Pmax表示智能移動(dòng)設(shè)備最大傳輸功率。在初始化完成后，會(huì)先將參數(shù)μ換算成每臺(tái)智能移動(dòng)設(shè)備真實(shí)的帶寬占比γ，計(jì)算方法如下，其中γ1=μ1：

換算完成后，還會(huì)對參數(shù)λ和參數(shù)γ之間的數(shù)據(jù)關(guān)系進(jìn)行一個(gè)判斷：如果當(dāng)γ的值為0時(shí)，說明某個(gè)智能移動(dòng)設(shè)備沒有使用帶寬通道去傳輸數(shù)據(jù)給服務(wù)器計(jì)算，表示所有數(shù)據(jù)必須在智能移動(dòng)設(shè)備上計(jì)算，因此需要將對應(yīng)的參數(shù)λ的值修改為1。最后更新粒子群的全局最優(yōu)粒子。

在進(jìn)化的過程中，不同適應(yīng)度的粒子在局部尋優(yōu)和全局尋優(yōu)中有著不同的作用[16]，因此將它們區(qū)別開來，根據(jù)適應(yīng)度的不同劃分不同的層次。分層學(xué)習(xí)策略先將種群按照適應(yīng)度值的大小進(jìn)行排序并進(jìn)行分層操作，層數(shù)較低的粒子在進(jìn)行更新操作時(shí)，學(xué)習(xí)的對象是層數(shù)較高的任意一個(gè)粒子。這種方法促使粒子向比自身更優(yōu)的粒子學(xué)習(xí)，同時(shí)也保留了搜索的多樣性。

假設(shè)種群的數(shù)量為NP(number of particles)，將該種群按照適應(yīng)度的大小分為NH(number of height)層，每一層用Hi(1≤i≤NH)表示，那么劃分到同一層的粒子數(shù)量為HS(height size)，并且HS=NP/NH。如圖2所示，將初始化之后的種群按照目標(biāo)函數(shù)值從小到大進(jìn)行排序，然后按順序每HS個(gè)粒子劃分為一層，其中前HS個(gè)粒子劃分為第一層H1，最后HS個(gè)粒子劃分到最后一層HNH。

圖2 分層學(xué)習(xí)策略Fig.2 Strategy of level-based learning

在分層操作完成后進(jìn)行算法的個(gè)體更新操作，與傳統(tǒng)的PSO算法按下標(biāo)順序更新粒子不同，LLSO算法是從層級(jí)最低，即位于HNH層的粒子開始更新，再更新層級(jí)較高的粒子。在更新操作中，假設(shè)位于第i層中的第j個(gè)粒子xi,j,1

其中，r1、r2、r3都是在[0，1]中隨機(jī)生成的隨機(jī)數(shù)，而?是控制參數(shù)，主要影響粒子xl2,k2的更新效果，其取值范圍在[0，1]。

LLSO算法的偽代碼如算法1所示。第1行初始化粒子群，在參數(shù)的取值范圍內(nèi)隨機(jī)生成浮點(diǎn)數(shù)，第2行根據(jù)公式（20）計(jì)算每個(gè)粒子的適應(yīng)度值，并初始化全局最優(yōu)粒子。第4到15行是算法的迭代優(yōu)化過程：第5行進(jìn)行分層操作，第6到13行對每個(gè)粒子進(jìn)行更新操作，對于每個(gè)待更新的粒子，首先選取層級(jí)較高的兩個(gè)粒子，再根據(jù)公式（29）、（30）更新該粒子的速度信息和位置信息，最后再更新粒子的適應(yīng)度值。第14行在更新完粒子后重新比較每個(gè)粒子的適應(yīng)度值，更新全局最優(yōu)粒子。第16行輸出最終的優(yōu)化結(jié)果。

算法1基于分層學(xué)習(xí)的粒子群算法

輸入：種群大小NP，分層數(shù)量NH，控制參數(shù)?，最大適應(yīng)度評估次數(shù)MAX_FES

輸出：全局最優(yōu)個(gè)體

1.初始化粒子群，計(jì)算每層劃分的個(gè)體數(shù)量，令fes=0

2.計(jì)算種群中所有粒子的適應(yīng)度值，初始化全局最優(yōu)粒子

3.fes+=NP；

4.while fes

5. 按照粒子適應(yīng)度值大小進(jìn)行分層操作；

6. For i=NH to 2 do

7. For j=1 to HS do

8. 隨機(jī)選取層級(jí)較高的粒子xl1,k1,xl2,k2作為進(jìn)化榜樣；

9. 根據(jù)公式（29）、（30）更新粒子xi,j的速度信息和位置信息；

10. 計(jì)算粒子新的適應(yīng)度值；

11. End For

12.fes+=HS；

13. End For

14. 更新全局最優(yōu)粒子；

15.End while

16.輸出全局最優(yōu)個(gè)體

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)介紹和參數(shù)設(shè)計(jì)

為了驗(yàn)證LLSO算法在解決邊緣計(jì)算資源調(diào)度問題上的性能，本文將使用LLSO算法用于移動(dòng)設(shè)備的能耗優(yōu)化問題。實(shí)驗(yàn)會(huì)測試LLSO算法對于不同移動(dòng)設(shè)備數(shù)量情況下的優(yōu)化性能，因此本次實(shí)驗(yàn)中智能移動(dòng)設(shè)備的數(shù)量的取值范圍為[5，10]。而本次實(shí)驗(yàn)的模型參數(shù)，即目標(biāo)函數(shù)中與智能移動(dòng)設(shè)備和服務(wù)器相關(guān)的常數(shù)參數(shù)，根據(jù)文獻(xiàn)[18-19]，做出以下設(shè)置，如表1所示。

表1 目標(biāo)函數(shù)參數(shù)默認(rèn)值Table 1 Default values of parameters of objective function

LLSO中引入了兩個(gè)參數(shù)，分層的數(shù)量NH和控制參數(shù)?。NH大小影響進(jìn)化過程中種群的多樣性，控制參數(shù)影響著粒子xl2,k2在進(jìn)化過程中的影響力，而該粒子具有更多的全局尋優(yōu)潛力。因此這兩個(gè)參數(shù)會(huì)影響LLSO算法的整體表現(xiàn)，根據(jù)文獻(xiàn)[17]，將這兩個(gè)參數(shù)設(shè)置為NH=4、?=0.4。種群數(shù)量NP=100。

同時(shí)為了驗(yàn)證LLSO算法在優(yōu)化結(jié)果和優(yōu)化速度上的優(yōu)勢，本文選擇其他具有代表性的啟發(fā)式算法對同一個(gè)問題同時(shí)進(jìn)行優(yōu)化，并比較它們的優(yōu)化結(jié)果。選取的算法如下：模擬退火算法（SA）[20]、遺傳算法（GA）[21]、粒子群算法（PSO）[22-23]，基于模擬退火的粒子群算法（SA-based PSO，SAPSO）[24]和基于遺傳模擬退火的粒子群算法（genetic simulated-annealing-based particle swarm optimization，GSP）[25]。對比算法的參數(shù)設(shè)置如下：根據(jù)文獻(xiàn)[25]，GSP算法中的初始溫度參數(shù)設(shè)為108，降溫速率為0.95，變異概率為0.01，慣性權(quán)重的取值范圍為[0.4，0.95]，加速因子1.496，學(xué)習(xí)因子0.5。SA算法的初始溫度為108，降溫速率為0.95。GA算法中的交叉概率為0.8，變異概率為0.01。根據(jù)文獻(xiàn)[26]，PSO算法中加速因子c1為1.85，加速因子c2為2，慣性權(quán)重的取值范圍為[0.38，0.99]。

3.2 實(shí)驗(yàn)結(jié)果

表2的數(shù)據(jù)是六種算法在不同數(shù)量的移動(dòng)設(shè)備的情況下獨(dú)立運(yùn)行100次的能耗優(yōu)化的結(jié)果，每種算法在目標(biāo)函數(shù)評價(jià)達(dá)到200 000次時(shí)停止優(yōu)化，并且用可行解概率來表示每種算法在100次獨(dú)立運(yùn)行中得到可行解次數(shù)百分比，即可行解懲罰值為0的結(jié)果。從表2的結(jié)果可以看出，在100次獨(dú)立運(yùn)行中，本文提出LLSO算法的能耗優(yōu)化結(jié)果比其他五種算法的優(yōu)化結(jié)果較好，并且在所有不同移動(dòng)設(shè)備數(shù)量情況下LLSO算法的可行解概率都能達(dá)到100%。當(dāng)移動(dòng)設(shè)備數(shù)量較少時(shí)，如M=5和M=6時(shí)，所有算法都能求出可行解，其中GA和GSP算法的能耗平均值與LLSO算法比較接近，但LLSO算法的能耗優(yōu)化結(jié)果最低。當(dāng)移動(dòng)設(shè)備的數(shù)量增多時(shí)，如M=9和M=10時(shí)，SA和PSO這兩種算法的可行解概率都低于20%，說明這兩種算法在移動(dòng)設(shè)備數(shù)量較多的優(yōu)化模型中已經(jīng)無法適用，GSP、GA和SAPSO四種算法的可行解概率低于90%，而LLSO算法的可行解概率仍是100%。

表2 六種算法在不同移動(dòng)設(shè)備數(shù)量的優(yōu)化結(jié)果Table 2 Optimization results of six algorithms in different number mobile devices

圖3展示的是六種算法在六種不同移動(dòng)設(shè)備的情況下的能耗優(yōu)化收斂趨勢圖，其收斂曲線展示的是100次獨(dú)立運(yùn)行的平均值收斂情況。從圖中可以看出LLSO算法在所有情況下的平均優(yōu)化結(jié)果都優(yōu)于其他五種算法，在20 000次評價(jià)次數(shù)的時(shí)候已經(jīng)接近收斂。GSP算法與LLSO的收斂趨勢比較接近，但GSP算法的優(yōu)化結(jié)果沒有LLSO算法好。GA算法的收斂速度最快，在第5 000次迭代的時(shí)候就接近收斂，收斂結(jié)果與GSP算法相同。當(dāng)移動(dòng)設(shè)備數(shù)量較少時(shí)，GA算法的優(yōu)化結(jié)果與LLSO算法的優(yōu)化結(jié)果相近，相差不到0.1，但當(dāng)移動(dòng)設(shè)備數(shù)量增多時(shí)，優(yōu)化結(jié)果的差距逐漸增大，當(dāng)M=10時(shí)，LLSO算法的優(yōu)化結(jié)果比GA算法提高10%左右。SA、PSO和SAPSO算法與LLSO算法相比優(yōu)化結(jié)果較差，并且在M大于7時(shí)這三種算法的收斂曲線出現(xiàn)波動(dòng)，說明這三種算法在移動(dòng)設(shè)備數(shù)量較多時(shí)無法優(yōu)化出滿足約束條件的結(jié)果，導(dǎo)致能耗值收斂曲線出現(xiàn)上升的現(xiàn)象。

圖3 六種算法能耗值優(yōu)化收斂圖Fig.3 Energy consumption optimization convergence diagram of six algorithms

圖4展示的是六種算法在不同移動(dòng)設(shè)備情況下100次獨(dú)立運(yùn)行的能耗優(yōu)化結(jié)果的分布情況。從圖中可以看出，LLSO算法的結(jié)果最好，優(yōu)化結(jié)果分布最為集中，說明LLSO算法的表現(xiàn)穩(wěn)定，并且能耗平均值和中位數(shù)都比其他四種算法較低。GA算法和GSP算法的結(jié)果分布情況相近。而SA、PSO和SAPSO算法的優(yōu)化結(jié)果分布較差，其中PSO算法在不同數(shù)量移動(dòng)設(shè)備情況的優(yōu)化結(jié)果的分布范圍比其他算法的大，可以看出PSO算法的優(yōu)化結(jié)果不穩(wěn)定。

圖4 六種算法優(yōu)化結(jié)果分布對比Fig.4 Comparison of optimization results distribution of six algorithms

4 結(jié)束語

隨著物聯(lián)網(wǎng)行業(yè)的發(fā)展，智能移動(dòng)設(shè)備越來越普及，但是移動(dòng)設(shè)備因其便攜性和移動(dòng)性的特點(diǎn)，使得移動(dòng)設(shè)備無法滿足對于計(jì)算資源要求較高的應(yīng)用程序。而邊緣計(jì)算技術(shù)為解決這一問題提供了解決方案，通過將部分任務(wù)分給邊緣服務(wù)器完成來滿足應(yīng)用服務(wù)的計(jì)算需求。而如何制定計(jì)算卸載決策，合理分配資源，成為邊緣計(jì)算資源調(diào)度中一個(gè)挑戰(zhàn)。因此本文提出了一種移動(dòng)設(shè)備計(jì)算卸載模型，通過調(diào)整計(jì)算卸載的比例和計(jì)算資源的分配，使得所有移動(dòng)設(shè)備和邊緣服務(wù)器消耗的總能量達(dá)到最小，并使用基于分層學(xué)習(xí)的粒子群算法來優(yōu)化這一問題，并通過對比實(shí)驗(yàn)證明該算法比其他優(yōu)化算法獲得了具有更低的能耗的解。本文的未來工作包括設(shè)計(jì)新的搜索模式用于算法求解大規(guī)模問題，提高移動(dòng)設(shè)備數(shù)量較多時(shí)算法得出可行解的能力。