一種基于遺傳算法的多站點協同計算卸載算法*

季子豪，江凌云

(南京郵電大學通信與信息工程學院，江蘇 南京 210003)

1 引言

隨著物聯網IoT(Internet of Things)、5G技術的發展，終端設備的數量迅速增加，其產生的數據量呈指數級增長，當前核心網的帶寬無法承受日益龐大的數據量傳輸。此外，增強現實、虛擬現實和無人駕駛等，尤其是基于人工智能的新型應用程序的出現對時延和功耗提出了更高的要求[1]。IoT終端的計算、存儲和電池能力有限，無法獨立完成這些計算密集型應用任務。邊緣計算(Edge Computing)為解決這些問題提供了有效途徑。邊緣計算的思想是在靠近終端側部署計算資源和存儲資源，對終端的計算任務和存儲任務就近處理，以此優化計算密集型應用的響應延遲[2]。

計算卸載是邊緣計算領域的一項關鍵技術[3]。計算卸載技術通過將資源受限的IoT終端的計算任務卸載到計算資源更強的邊緣節點或中心云執行，可以優化物聯網應用的響應延遲，同時有效降低終端設備的能耗。關于單一設備的計算卸載已經有很多研究人員進行了研究，即將應用程序完整地部署在一臺設備上，在進行卸載決策時，對應用程序的各任務進行代價分析，判斷哪些任務卸載到邊緣節點執行，哪些任務在本地執行，可以使得應用程序的總執行代價最小。

但是，在未來的IoT環境中，大部分應用服務都將以分布式架構的形式進行部署，一個完整的IoT應用被拆分為多個具有依賴關系的子任務，這些子任務初始部署在多個站點中，例如IoT終端、邊緣節點或中心云，這些站點協作完成整個應用任務。但是，受計算資源、存儲容量和電池電量的影響，在終端進行數據處理可能會耗費過長時間，需要將自身的計算任務卸載到邊緣節點或中心云處理[4]；同樣，受網絡帶寬的影響，終端和邊緣節點之間的數據傳輸代價可能大于本地執行代價[5]，不適合卸載任務。在這樣的場景下，站點間的通信代價無法被簡單忽略，進行計算卸載決策、尋找最優任務分配策略十分具有挑戰性。

本文的其余部分組織如下：第2節介紹計算卸載的相關工作；第3節建立多站點協同計算卸載問題的數學模型；第4節描述遺傳算法，并利用遺傳算法尋找最優卸載決策，提出基于遺傳算法的多站點協同計算卸載算法GAMCCO(Genetic Algorithm-based Multi-site Collaborative Computation Offloading);第5節進行仿真實驗，并對結果進行討論；最后對本文進行了總結和展望。

2 相關工作

作為邊緣計算領域的一項關鍵技術，計算卸載已經得到了廣泛的研究。文獻[6]提出了MAUI計算卸載框架，該框架將計算卸載問題轉化為整數線性規劃問題，將一些繁重的計算任務卸載到鄰近的邊緣云服務器上，以降低移動設備的能耗。文獻[7]提出了基于遺傳算法的任務調度方案，該方案將應用程序劃分為多個子任務，分別計算每一個子任務的本地執行代價和遠程執行代價，構建具有時延約束的能耗模型，最后利用遺傳算法分析該能耗模型，得出最佳卸載方案。文獻[8]將應用程序建模為由細粒度任務組成的通用拓撲結構，這些細粒度任務可以在本地或邊緣節點上執行，然后將計算卸載問題規約為具有時延約束的工作流調度問題，提出了基于拉格朗日松弛的聚合代價算法計算工作流調度問題的最優解。文獻[9]針對單一云服務器計算資源有限的情形，考慮將計算任務卸載到多個云服務器上，提出了基于遺傳算法的多站點計算卸載決策GAMCO(Genetic-based decision Algorithm for Multi-site Computation Offloading)，實現應用程序的性能提升。文獻[10]實現了一個多站點自適應卸載框架，該框架把設備的硬件信息變化和實時網絡條件納入考量，將移動設備的計算任務卸載到自組織云、邊緣云和中心云中，以加快應用程序的執行。文獻[11]針對動態環境中的計算卸載，采用隨機博弈方法建立了動態模型，并提出多代理隨機學習的方法尋找最優決策。文獻[12]提出了一種能量高效的動態上傳策略，利用動態電壓和頻率分配技術優化移動設備的性能。文獻[13]則是采用馬爾可夫決策過程，將多站點卸載問題轉化為具有時延約束、最小卸載代價的最短路徑問題，并提出基于能耗的多點卸載策略算法，尋找多站點任務卸載的解決方案。

但是，以上關于計算卸載的研究工作都是假設應用程序初始完整地部署在一臺設備上，并將計算任務從該設備上卸載到其余站點執行，并未考慮到應用程序分布式部署在多個設備上的情形。因此，本文基于應用程序分布式部署的情形，將多站點協同計算卸載問題建模為一個通用的代價模型，利用遺傳算法尋找最優的卸載方案，以最小化總執行代價。

3 計算卸載模型

本節首先基于應用程序分布式部署的假設，對多站點協同計算卸載的場景進行描述，并以此構建任務依賴關系圖。然后根據站點間通信代價、任務執行的時延代價和能耗代價進行模型構建，最終得出模型的數學表達式。

3.1 系統場景

傳統的計算卸載場景如圖1所示。終端設備上有一個完整的應用程序待執行，應用程序由多個子任務組成，根據相應的計算卸載算法判斷哪些子任務在本地執行，哪些子任務需要卸載到邊緣節點或中心云執行。針對這種場景的計算卸載算法無法用于應用程序在多站點分布式部署的情形。

Figure 1 Edge computing scenario for single device computation offloading

本文考慮這樣一個需要多站點協同計算的邊緣計算場景，如圖2所示。該場景包含多個IoT終端、1個邊緣節點和1個中心云，一共涉及K個節點。物聯網應用程序在開發時已經被劃分為K個子任務V={v1,v2,…,vK}，并以分布式的形式部署在IoT終端、邊緣節點和中心云上，應用程序執行時需要這些站點協同計算。應用程序的子任務之間具有依賴關系，初始部署在各個IoT終端上的計算任務既可以在該終端本地執行，也可以根據上下文信息卸載到邊緣節點或中心云執行。

Figure 2 Edge computing scenario for multi-site collaborative computation offloading

Figure 3 Dependency relationship graph among application components

3.2 系統代價模型

3.2.1 參數描述

下面對計算卸載模型涉及的參數進行簡要描述：

(1)計算卸載方案為X={x1,x2,…,xK}，其中xk∈{-1,0,1}，xk=-1表示將任務vk卸載到云端執行，xk=0表示將任務vk卸載到邊緣節點執行，xk=1表示在站點k處執行即本地執行。

(3)本文構造的計算卸載代價模型由時延代價和能耗代價組成，用于尋找應用程序組件的最佳卸載決策，以最小化應用程序的總執行代價。計算卸載決策X所對應的應用程序代價如式(1)所示：

(1)

其中，T(X)和E(X)分別表示應用程序使用卸載方案X的時延代價和能耗代價；Torigin和Eorigin分別表示應用程序組件不經過計算卸載，直接按照初始部署執行的總時延和能耗代價，可以認為是一個常數；α和β分別表示時延和能耗在整個代價模型中所占的比重。

3.2.2 時延代價模型

時延代價包括任務計算時延和數據通信時延。對于每一個站點k，fk表示該站點的計算能力，任務vk在各站點本地的計算時延可以表示為式(2)：

(2)

在邊緣節點的計算時延由式(3)表示：

(3)

在云端的計算時延由式(4)表示：

(4)

其中，fe和fc分別表示邊緣節點和云端的計算能力。

(5)

當計算任務vi和任務vj的卸載目的地一致時，它們之間的數據通信時延為0。

時延模型的優化目標是找到應用程序的最佳計算卸載決策Xbest，滿足應用程序各組件的時延代價加權最小。

根據候選卸載決策X給出的應用程序時延模型如式(6)所示：

(6)

(7)

3.2.3 能耗代價模型

與終端相比，邊緣節點和云端的電量近乎是無限的，因此本文只考慮終端產生的能耗。終端產生的能耗包括計算能耗和數據傳輸的通信能耗。與以往關于計算卸載的研究類似，在數據傳輸的通信能耗這一方面，本文只考慮終端發送數據的能耗，因為與發送功率相比，接收功率往往很小，可以忽略不計。

任務vk在各站點的計算能耗如式(8)所示：

(8)

(9)

能耗模型的優化目標是找到應用程序的最佳計算卸載決策Xbest，使得應用程序各組件的能耗代價加權最小。

根據候選卸載決策X給出的應用程序能耗模型如式(10)所示：

(10)

4 GAMCCO算法

由于考慮了多站點之間的任務依賴關系，求解最佳計算卸載策略的難度大大提高，很難在多項式時間內計算出最優解。因此，本文引入遺傳算法，提出GAMCCO算法來尋找計算卸載策略的最優解。

遺傳算法借鑒了自然界的遺傳選擇和自然淘汰的生物進化過程，其核心思想是模擬一個人工種群的進化過程，通過選擇、交叉和變異機制，經過若干代進化后，產生最優個體，是一種高效的全局搜索算法，適合處理傳統尋優算法難以解決的非線性問題。

遺傳算法的個體對應到計算卸載問題中即為計算卸載方案，染色體表示經過編碼后的卸載方案，基因表示每個任務的卸載目的地。

4.1 編碼和初始種群

實現遺傳算法的第1步是對求解問題的解空間進行編碼。在本文提出的多站點協同計算卸載模型中，應用程序被劃分為K個需要卸載的子任務，因此在遺傳算法中每條染色體由K個基因組成，部署在各站點的任務可以在本地執行，也可以遷移到邊緣節點或遷移到云端執行，因此每個基因有3個可能值(云：-1，邊緣：0，本地：1)。一條染色體就是一個可能的計算卸載方案，如圖4所示，是一個由K個基因構成的染色體。

Figure 4 A chromosome with K genes

初始種群使用隨機構造的方法產生，初始種群規模為M。

4.2 適應度函數

遺傳算法對一個個體(解)的好壞用適應度函數值來評價[14]。在本文中，適應度函數定義為應用程序計算卸載總代價的倒數，如式(11)所示，以此評判每個計算卸載方案的優劣，適應度函數值越大，對應的總代價越小，那么計算卸載方案越好。

(11)

在每一次的迭代進化過程中，采取精英選擇的策略保留每一代的精英解。進行第i次迭代時，首先計算第i代種群中每個個體的適應度函數值，并將種群中的個體按照適應度函數值大小降序排列，然后丟棄適應度較低的后一半個體，選擇種群中適應度較高的前一半個體延續到下一步的交叉過程。

4.3 交叉過程

交叉過程中，2個父親染色體按照某種規則交換其部分基因，產生子代染色體。本文選取了單點交叉的方式進行交叉操作。所謂單點交叉，就是在父親染色體中隨機選擇1個交叉點，然后以交叉點為界，交換2個父親染色體交叉點位置的左右基因，產生2個新的染色體。一個單點交叉的例子如圖5所示。

Figure 5 An example of a single point crossing

4.4 變異過程

變異操作是根據設定的變異概率選取染色體的若干位基因改變其值，其目的是產生新的個體，保持種群的多樣性，防止過早陷入局部最優。本文對交叉過程產生的染色體種群進行基因變異。另一方面，變異操作完成后，為了將盡可能多的卸載方案納入考量，防止適應度函數過早收斂，本文構造與當前的精英染色體數目相等的隨機染色體，兩者共同組成新一代的染色體種群。在這一步中使用隨機染色體和精英染色體共同組成新種群的方法則是對經典遺傳方法的改進，經典遺傳方法只會保留精英個體，容易過早收斂。

4.5 終止條件

經過上述遺傳算法的操作，可以得到新一代的染色體種群，根據本文提出的適應度函數，對新一代種群進行適應度評估。如果當前迭代次數已經達到了預先設定的最大值，或者在連續的若干代染色體種群中，最低適應度函數值沒有改進，那么遺傳尋優過程的終止條件得到滿足，算法終止；否則，繼續重復遺傳迭代進化過程，直至滿足算法的終止條件。

4.6 算法流程

本文提出的卸載架構如圖6所示，其中設備D1、D2和D3是終端節點，具備計算和本地組網功能，邊緣節點作為控制調度器進行參數收集和卸載決策。云、邊緣節點和終端共同構成了一項服務。UE是用戶設備，由它來調用該服務。當邊緣節點接收到用戶的調用請求后，分析各站點的硬件信息和網絡條件，進行分析決策，并將決策結果告知各站點進行計算，最終將計算結果返回給用戶。

Figure 6 Offloading framework

基于遺傳算法的多站點協同計算卸載算法(GAMCCO)的流程圖如圖7所示。

Figure 7 Flow chart of GAMCCO

5 仿真和評估

本節將使用Matlab對提出的GAMCCO算法進行仿真并加以分析。

5.1 參數設置

仿真場景包括1個中心云、1個邊緣節點和多個終端節點，總計為K個。對于終端節點，假設除了部署在各節點的任務不同外，它們的硬件完全相同，即擁有完全一樣的計算能力和功耗。仿真實驗的部分參數如表1所示。

以圖像拼接應用為例，圖像拼接技術的原理是根據圖像重疊部分將多幅銜接的圖像拼合成一幅高分辨率全景圖。目前圖像拼接過程主要包括以下幾個主要步驟：圖像預處理、圖像配準、圖像融合與邊界平滑。其中，圖像預處理主要是對各攝像終端采集的圖像進行幾何畸變校準和噪聲點抑制，使

Table 1 Parameters of simulation experiment

參考圖像不存在明顯的幾何畸變。該步驟可以在各攝像終端直接運行，當終端資源受限時可以選擇卸載到邊緣節點或云端運行。本文分析了此應用程序內部的方法調用關系，將其細分為由10個任務組成的應用，并構造相應的任務依賴關系圖，然后利用模擬的數據集進行仿真實驗。以下Cttotal是根據一組模擬的數據集計算出的時延代價矩陣，Cttotal中的行代表應用程序的子任務，列代表云端、邊緣節點或本地，Cttotal[i][j]表示應用程序子任務vi在站點j處執行的總代價(包括通信時延代價和計算時延代價)。當給定卸載方案X={x1,x2,…,xK}時，根據Cttotal和X即可計算出式(1)中T(X)所表示的應用程序總時延代價。同理，總能耗代價E(X)也可根據能耗代價矩陣和卸載方案X計算得到。設置了時延因子α和能耗因子β后，式(1)的總代價W(X)也可計算得出。

X′表示初始種群中的卸載方案樣本的集合，它的每一列都表示一個卸載方案。由于本文將初始種群設置為100個，所以X′的列數為100，行數為子任務數。實際實驗時，本文使用多組模擬的數據集計算平均結果，盡可能確保實驗結果不具備偶然性。

5.2 結果分析

遺傳算法的參數對GAMCCO算法的性能有著很大的影響，例如初始種群規模、突變概率和遺傳迭代次數等。為了使GAMCCO算法獲得最佳性能，本文利用控制變量的方法研究了突變概率和遺傳迭代次數對總代價的影響。圖8展示了突變概率對算法總代價的影響。具體設置為初始種群規模100，迭代次數100，突變概率在[0,0.2]變化，同時適應度函數中的時延因子α和能耗因子β都設置為0.5。從圖8可以看出，在[0,0.04]內，總代價呈下降趨勢，然后隨著突變概率的增加，總代價上升，突變概率增加到0.15以后，總代價上下起伏。這是因為隨著突變概率的增加，種群中的較優解可能會變異為較差解，導致性能下降。

Figure 8 Impact of mutation probability on the performance of the algorithm

圖9展示了遺傳迭代次數對算法總代價的影響。具體參數設置為初始種群規模100，突變概率0.04，迭代次數從1增加至100，時延因子α和能耗因子β都為0.5。從圖9可以發現，隨著迭代次數的增加，總代價雖有起伏，但仍呈下降趨勢，當迭代次數達到80后，代價曲線基本平穩。

Figure 9 Impact of the number of genetic iterations on the performance of the algorithm

根據以上實驗，本文將遺傳算法參數設置為種群數100，突變概率0.04，遺傳迭代次數100。為了評估所提算法的可行性和性能，將GAMCCO算法的結果和以下幾種卸載方案對比：

(1)本地卸載方案(Local)：所有站點的計算任務都在各站點本地執行。

(2)邊緣卸載方案(Edge)：所有站點的計算任務都遷移到邊緣節點執行。

(3)遺傳方案(GA)：使用遺傳算法的經典實現對本文所建立的代價模型進行遺傳尋優。

(4)多站點卸載方案(GAMCO)：對該算法的代價模型和卸載方案進行了擴展，使其能適用于本文的多站點協同計算卸載的場景，并進行了仿真。

圖10～圖12展示了GAMCCO算法和以上4種卸載方案的對比。圖10中時延因子α和能耗因子β都設置為0.5，橫坐標為遺傳迭代次數，縱坐標為總代價，由于本文所建立的代價函數模型是卸載方案代價與本地代價的比值，因此縱坐標的總代價沒有單位。

Figure 10 Comparison of 4 offloading schemes when α=0.5 and β=0.5

圖11中時延因子α設置為1，能耗因子β設置為0，這時只考慮時延代價。

Figure 11 Comparison of 4 offloading schemes when α=1 and β=0

圖12中時延因子α設置為0，能耗因子β設置為1，此時考慮的是能耗代價。

Figure 12 Comparison of 4 offloading schemes when α=0 and β=1

從圖10～圖12中可以發現，GAMCCO算法求出的方案均優于其余4種卸載方案。和GAMCCO算法相比，GA算法的曲線收斂較快，這是由于本文在實現GA經典方法時，在遺傳選擇的步驟中僅僅使用精英選擇的策略篩選出了精英解，并沒有對種群的其余個體進行替換，導致大部分的卸載方案都沒有被考慮進去，從而過早陷入了局部最優，最差的情況在到達第30次迭代左右就收斂。而GAMCCO算法在遺傳迭代步驟中，使用精英選擇策略+隨機解替換的方式，篩選出當前種群的較優解，同時將較差解替換為隨機解，考量到了更多的卸載方案，因此收斂性能較好。但是，無論是GAMCCO還是GA算法求出的方案，都優于本地執行和邊緣執行。而GAMCO算法則是采用了2個初始種群進行遺傳迭代，即采用固定種群+隨機種群的方式，也能避免過早收斂的情況，如圖12所示，迭代到達80次才收斂，但其性能仍然劣于本文提出的GAMCCO算法的。GAMCCO算法可以有效降低多站點協同計算卸載時的總代價。

6 結束語

隨著物聯網和分布式服務的發展，未來物聯網應用程序將普遍采用分布式部署的方式。然而分布式部署引入了站點間任務依賴的問題，使得這種場景下的計算卸載更為復雜。為了優化應用程序的執行代價(時延和能耗)，本文提出了基于遺傳算法的多站點協同計算卸載算法GAMCCO。該算法分析了應用程序各站點、各任務之間的依賴關系，將計算任務卸載到邊緣節點或云端，以縮短應用程序的執行時間，降低終端的能耗。實驗結果表明，GAMCCO算法可以有效減少應用的執行時間，降低能耗代價。本文還將GAMCCO算法和GA算法、GAMCO算法進行了比較，GAMCCO算法比GA算法收斂更慢，不會過早收斂，性能也優于GA和GAMCO算法的。但是，本文提出的算法并不總是能得到最優解，在實驗中存在著收斂較快，陷入局部最優的情況。未來將繼續對代價模型進行完善，同時考慮將遺傳算法和其他的啟發式算法相結合，盡可能減少陷入局部最優的情況。