工業(yè)物聯(lián)網(wǎng)的工業(yè)邊緣云部署算法

顏曉蓮 ，章 剛 ，邱曉紅 ，陳慶奎

(1.江西理工大學(xué)南昌校區(qū) 軟件工程學(xué)院，江西 南昌 330013；2.江西北大科技園，江西 南昌 300033； 3.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

1 問題的提出

工業(yè)物聯(lián)網(wǎng)(Industrial Internet of Things，IIOT)作為一種智能制造技術(shù)形態(tài)，能夠?qū)崿F(xiàn)原料靈活配置、過程按需執(zhí)行、工藝合理優(yōu)化和環(huán)境快速適應(yīng)，因此廣泛應(yīng)用于制造業(yè)領(lǐng)域[1-2]。隨著大批量工藝復(fù)雜且異構(gòu)的數(shù)字化生產(chǎn)設(shè)備接入IIOT，產(chǎn)生了生產(chǎn)設(shè)備實(shí)時(shí)性運(yùn)維等新型工業(yè)需求，然而受限于工業(yè)帶寬與傳輸距離，IIOT無法通過云端有效解決生產(chǎn)設(shè)備實(shí)時(shí)性運(yùn)維問題，在IIOT體系中引入邊緣端數(shù)字孿生技術(shù)勢(shì)在必行[3-4]。

作為IIOT實(shí)踐的產(chǎn)物，邊緣端數(shù)字孿生是一種集感知、通信、建模、分析和控制等技術(shù)為一體，能夠在靠近生產(chǎn)設(shè)備處構(gòu)建與物理設(shè)備完全對(duì)稱的虛擬映射，借助運(yùn)行數(shù)據(jù)模擬生產(chǎn)設(shè)備運(yùn)行過程，并通過智能分析提供實(shí)時(shí)運(yùn)維服務(wù)，從而滿足工業(yè)實(shí)時(shí)性要求的技術(shù)體系[4-5]。由于能夠在物理設(shè)備近端處搭建物理設(shè)備與虛擬設(shè)備溝通交互的橋梁，其必將成為工業(yè)物聯(lián)網(wǎng)的核心部件之一[5-6]。推動(dòng)工業(yè)物聯(lián)網(wǎng)與邊緣端數(shù)字孿生融合被視為工業(yè)物聯(lián)網(wǎng)技術(shù)成熟到一定階段的必然結(jié)果，而當(dāng)前邊緣端數(shù)字孿生技術(shù)全面融入工業(yè)物聯(lián)網(wǎng)體系依然面臨各類挑戰(zhàn)，工業(yè)邊緣云部署問題便是其中之一。

一般而言，制造型企業(yè)的生產(chǎn)資料分散在不同區(qū)域。在生產(chǎn)需求驅(qū)動(dòng)下，不同生產(chǎn)區(qū)域(或生產(chǎn)車間)需安置數(shù)量或規(guī)模不同的生產(chǎn)線(每條生產(chǎn)線上附屬的生產(chǎn)設(shè)備數(shù)量不同)方可滿足制造要求。為保證設(shè)備實(shí)時(shí)性運(yùn)維的服務(wù)質(zhì)量和節(jié)約成本，在每條生產(chǎn)線的內(nèi)部網(wǎng)關(guān)處(或多條生產(chǎn)線的共享網(wǎng)關(guān)處)部署工業(yè)邊緣云，覆蓋相應(yīng)的生產(chǎn)線及其生產(chǎn)設(shè)備，有效構(gòu)建起以數(shù)字化改造后的生產(chǎn)設(shè)備為終端，各類通信網(wǎng)絡(luò)為載體，工業(yè)邊緣云為核心的邊緣端數(shù)字孿生技術(shù)架構(gòu)，該架構(gòu)能夠有效貼近應(yīng)用場(chǎng)景，為生產(chǎn)設(shè)備提供實(shí)時(shí)性運(yùn)維服務(wù)。其中，工業(yè)邊緣云是適用于工業(yè)領(lǐng)域，部署于物理設(shè)備周圍，集建模、分析和控制等技術(shù)為一體的中低端服務(wù)器(或服務(wù)器集)。

由于企業(yè)產(chǎn)能受市場(chǎng)影響時(shí)刻變化，每個(gè)工廠內(nèi)的生產(chǎn)線會(huì)隨制造需求變化而動(dòng)態(tài)調(diào)整，包括擴(kuò)大或縮小生產(chǎn)線的數(shù)量和規(guī)模，這種無規(guī)則動(dòng)態(tài)調(diào)整容易造成工廠間生產(chǎn)線的差異化安置，以及生產(chǎn)設(shè)備不均勻分布。

工業(yè)邊緣云是構(gòu)建邊緣端數(shù)字孿生技術(shù)架構(gòu)的核心，也是提供實(shí)時(shí)性運(yùn)維服務(wù)的關(guān)鍵。當(dāng)每個(gè)工廠內(nèi)的生產(chǎn)線數(shù)量和規(guī)模發(fā)生改變時(shí)，由于工業(yè)邊緣云的網(wǎng)絡(luò)資源、存儲(chǔ)資源和計(jì)算資源有限，為保障繼續(xù)提供實(shí)時(shí)性運(yùn)維服務(wù)并節(jié)約成本，必須對(duì)工業(yè)邊緣云原有的部署方式進(jìn)行調(diào)整。任何隨意部署，包括不充分部署或過度部署，都將造成服務(wù)延遲增加、工業(yè)邊緣云負(fù)載失衡及企業(yè)成本增加等一系列問題?？傊?，合理部署工業(yè)邊緣云，不僅能夠提升資源利用率、節(jié)約企業(yè)生產(chǎn)成本，還能優(yōu)化工業(yè)邊緣云的負(fù)載，保障服務(wù)質(zhì)量，為邊緣端數(shù)字孿生乃至IIOT后期實(shí)踐打下基礎(chǔ)。工業(yè)邊緣云部署的示意圖如圖1所示。

綜上可知，工業(yè)邊緣云部署是保障實(shí)時(shí)性運(yùn)維服務(wù)質(zhì)量與節(jié)約成本的前提，而且依此產(chǎn)生的工業(yè)邊緣云部署問題(Industrial Edge Cloud Deployment Problem，IECDP)正逐漸成為熱點(diǎn)[7-9]。通過綜合考量已有成果及實(shí)踐中所關(guān)注的重點(diǎn)，本文認(rèn)為IECDP指在部署總成本受限的條件下，如何合理部署工業(yè)邊緣云，使其在所提供的總服務(wù)延遲最小的同時(shí)總負(fù)載最小[9-13]。

值得注意的是，邊緣云(服務(wù)器)部署問題不只是工業(yè)物聯(lián)網(wǎng)所關(guān)注的基礎(chǔ)性問題，也是移動(dòng)邊緣計(jì)算體系中主要討論的基礎(chǔ)問題之一。與IECDP不同之處在于，移動(dòng)邊緣云(服務(wù)器)部署主要關(guān)注的是如何在移動(dòng)用戶周圍合理部署移動(dòng)邊緣云(服務(wù)器)，使得服務(wù)質(zhì)量優(yōu)、移動(dòng)用戶訪問延時(shí)小、服務(wù)提供商收益高[8-13]。

綜上所述，IECDP的研究不但為工業(yè)物聯(lián)網(wǎng)與邊緣側(cè)計(jì)算融合研究提供了基礎(chǔ)理論依據(jù)，而且將為其他領(lǐng)域中的邊緣云部署問題研究提供解決思路。

2 現(xiàn)狀描述

現(xiàn)有研究成果有關(guān)工業(yè)物聯(lián)網(wǎng)中IECDP的討論比較少，但對(duì)移動(dòng)邊緣計(jì)算領(lǐng)域中的邊緣云(服務(wù)器)部署問題有詳細(xì)介紹。

首先，移動(dòng)邊緣計(jì)算的目標(biāo)是保證移動(dòng)用戶能夠就近獲取云計(jì)算服務(wù)。然而由于移動(dòng)用戶不但會(huì)在某范圍內(nèi)頻繁移動(dòng)，而且對(duì)服務(wù)的需求也不相同，在移動(dòng)邊緣云(服務(wù)器)覆蓋范圍受限的條件下，為保證移動(dòng)用戶獲得高質(zhì)量服務(wù)，有效地部署移動(dòng)邊緣云(服務(wù)器)極為重要?，F(xiàn)階段大多數(shù)移動(dòng)邊緣計(jì)算的研究均基于邊緣云(服務(wù)器)已部署完成的前提進(jìn)行，必然會(huì)影響后期研究成果，因?yàn)椴煌牟渴鸩呗詫?duì)研究成果的影響也不同，可見移動(dòng)邊緣云(服務(wù)器)部署是移動(dòng)邊緣計(jì)算體系中的一個(gè)基礎(chǔ)性問題。WANG等[8]討論移動(dòng)互聯(lián)網(wǎng)環(huán)境中具有約束限制的邊緣服務(wù)器放置策略，將放置問題抽象為多目標(biāo)多約束優(yōu)化問題，并提出啟發(fā)式混合整型規(guī)劃算法解決。文獻(xiàn)[9-11]集中討論如何在規(guī)模城市中為移動(dòng)用戶安置邊緣側(cè)服務(wù)器，從而提高移動(dòng)服務(wù)質(zhì)量問題，區(qū)別在于，文獻(xiàn)[9]以工作任務(wù)卸載平均等待時(shí)間為優(yōu)化指標(biāo)，基于排隊(duì)論和分類算法思想設(shè)計(jì)部署模型；文獻(xiàn)[10]以移動(dòng)用戶平均訪問延時(shí)為優(yōu)化指標(biāo)，用線性規(guī)劃思想設(shè)計(jì)部署算法；文獻(xiàn)[11]以邊緣服務(wù)器部署成本為優(yōu)化指標(biāo)，采用改進(jìn)型貪婪算法予以解決；文獻(xiàn)[12]討論隨機(jī)分布環(huán)境下的Cloudlet放置問題，以覆蓋移動(dòng)用戶數(shù)量為優(yōu)化指標(biāo)，提出基于K-means思想的Cloudlet部署算法；文獻(xiàn)[13]以服務(wù)提供商收益為優(yōu)化指標(biāo)，提出一種基于資源需求預(yù)測(cè)的邊緣端服務(wù)器放置啟發(fā)式算法。

以上研究成果部分嘗試借助分類思想(如K-means或K-median)，以優(yōu)化指標(biāo)為導(dǎo)向不斷調(diào)整分類策略，使得優(yōu)化指標(biāo)最優(yōu)，從而確定潛在的邊緣端服務(wù)器部署點(diǎn)[8-10，13]；部分嘗試從某一特性出發(fā)，預(yù)測(cè)出移動(dòng)用戶的遷移軌跡，并基于遷移軌跡確定潛在的邊緣端服務(wù)器部署點(diǎn)[11-12]。雖然都具有一定優(yōu)勢(shì)，但是顯然都不適合解決IECDP，主要原因?yàn)椋孩俟I(yè)制造領(lǐng)域，生產(chǎn)需求驅(qū)動(dòng)著生產(chǎn)線的動(dòng)態(tài)調(diào)整，無法通過預(yù)測(cè)方式獲得；②相對(duì)移動(dòng)用戶異構(gòu)的應(yīng)用需求，生產(chǎn)線及生產(chǎn)任務(wù)均具有同構(gòu)屬性，而且生產(chǎn)線動(dòng)態(tài)調(diào)整的頻率較低，無法通過分類策略劃分。

因此，本文提出一種啟發(fā)式遺傳算法(Heuristic Genetic Algorithm，HGA)有效地解決IECDP，主要工作如下：

(1)討論了工業(yè)物聯(lián)網(wǎng)與邊緣端數(shù)字孿生融合的基礎(chǔ)性問題——工業(yè)邊緣云部署問題，并進(jìn)一步將該問題轉(zhuǎn)化為帶約束的最小子集劃分問題。

(2)針對(duì)傳統(tǒng)遺傳算法在解決帶約束的最小子集劃分問題時(shí)存在的不足，提出HGA進(jìn)行解答。該算法以保障種群多樣性和可靠有效為導(dǎo)向，分別從編碼方式選定、初始種群篩選、下一代種群選擇、交叉和變異等方面進(jìn)行深度優(yōu)化，確保提高HGA的搜索準(zhǔn)度和搜索速度。

(3)構(gòu)建模擬場(chǎng)景，確定期望負(fù)載偏差率、期望服務(wù)延時(shí)偏差率、算法收斂率和解誤差率4個(gè)測(cè)試指標(biāo)，通過4組實(shí)驗(yàn)數(shù)據(jù)嘗試驗(yàn)證HGA的有效性、收斂性和全局搜索能力。

3 問題描述

(1)IECDP描述

給定一組邊緣云EC集合、生產(chǎn)線LINE集合及每個(gè)生產(chǎn)線所對(duì)應(yīng)的生產(chǎn)設(shè)備集合，在部署總成本Cost[EC]受限的條件下，尋找一種邊緣云部署方案，使邊緣云總服務(wù)延時(shí)Delay[EC]最小的同時(shí)邊緣云總負(fù)載Balance[EC]最小，目標(biāo)函數(shù)形式化為：

minDelay[EC](X)&&minBalance[EC](X)。

s.t.

Cost[EC](X)≤CostC。

(1)

其中：X為部署方案解；CostC為企業(yè)成本約束量。邊緣云總服務(wù)延時(shí)指所有邊緣云服務(wù)延時(shí)的總和，表示為

(2)

單個(gè)邊緣云ECi服務(wù)延時(shí)包括ECi所覆蓋的生產(chǎn)設(shè)備與其之間的數(shù)據(jù)傳輸延時(shí)，以及ECi對(duì)每個(gè)生產(chǎn)線的服務(wù)處理延時(shí)，表示為

(3)

式中：T[·]為生產(chǎn)設(shè)備與邊緣云之間的數(shù)據(jù)傳輸延時(shí)；Dispose[·]為邊緣云服務(wù)處理延時(shí)。

同理，邊緣云總負(fù)載指所有邊緣云負(fù)載的總和，表示為

(4)

單個(gè)邊緣云ECi負(fù)載包括CPU消耗、內(nèi)存消耗和通信消耗，通信消耗指與生產(chǎn)設(shè)備通信的消耗，即

(5)

式中：BCPU[·]為CPU消耗；BCACHE[·]為內(nèi)存消耗；BCOM[·]為通信消耗。

(2)問題變換

IECDP屬于帶約束的多目標(biāo)優(yōu)化問題，在實(shí)際求解過程中存在一定難度。通過分析所求問題，因?yàn)楣I(yè)邊緣云部署在單一網(wǎng)關(guān)處(或共享網(wǎng)關(guān)處)覆蓋所有域內(nèi)生產(chǎn)線及其生產(chǎn)設(shè)備，而每個(gè)生產(chǎn)線需要被工業(yè)邊緣云覆蓋(暫不考慮生產(chǎn)線被多重覆蓋情況)，所以IECDP可轉(zhuǎn)化為帶約束的最小子集劃分問題(Minimum Subset Partition Problem with Constraints，MSPPC)。IECDP轉(zhuǎn)化的意義在于，將IECDP轉(zhuǎn)化為經(jīng)典NP難問題的同時(shí)對(duì)目標(biāo)優(yōu)化函數(shù)進(jìn)行降維，降低計(jì)算復(fù)雜度。

s.t.

(6)

對(duì)每個(gè)生產(chǎn)線而言，其劃分權(quán)重由某個(gè)邊緣云為該生產(chǎn)線提供服務(wù)所產(chǎn)生的服務(wù)延時(shí)，以及邊緣云處理該生產(chǎn)線業(yè)務(wù)所造成的資源消耗(負(fù)載)的線性加權(quán)組成[7-8]，其劃分代價(jià)由部署到某個(gè)邊緣云所需的代價(jià)組成。

MSPPC屬于經(jīng)典的NP難問題，本文提出HGA來解決。

4 改進(jìn)的啟發(fā)式遺傳算法

4.1 傳統(tǒng)遺傳算法

傳統(tǒng)遺傳算法(Genetic Algorithm，GA)[14]由美國學(xué)者John Holland提出，是模擬生物進(jìn)化的一種高效、通用、并行優(yōu)化算法，該算法的本質(zhì)是通過不斷迭代來靠近最優(yōu)解。GA在解決MSPPC問題上具有一定優(yōu)勢(shì)，因?yàn)镸SPPC的本質(zhì)是尋找一個(gè)由單個(gè)或多個(gè)子集組成的集合。對(duì)于任意給定的由N個(gè)生產(chǎn)線組成的集合，其子集個(gè)數(shù)為2N-1(不包括空集)，根據(jù)MSPPC的思想，如果將被選中的子集賦值1，未被選中的子集賦值0，則問題的最終解可用一組數(shù)字0和1表達(dá)。而GA相對(duì)于已有的智能算法，更貼合MSPPC的思想，有利于快速搜索問題的最終解。

GA存在早熟現(xiàn)象[14](也稱過早收斂，指算法過早陷入局部最優(yōu)，很難從局部最優(yōu)跨到全局最優(yōu))，因此提出HGA，在優(yōu)化相關(guān)問題的同時(shí)解決MSPPC。

4.2 算法描述

算法的改進(jìn)思想為：①以提高全局搜索準(zhǔn)度和提升收斂速度為目標(biāo)；②為保證種群可靠和有效，篩選多樣化的可行解作為初始種群；③為保持種群多樣性，選擇下一代種群時(shí)，有目的地進(jìn)行混合式挑選；④為維持種群多樣性并提升探索新區(qū)域的能力，進(jìn)行多輪多維度多點(diǎn)交叉操作；⑤實(shí)施較優(yōu)新個(gè)體優(yōu)先動(dòng)態(tài)變異策略，進(jìn)一步保障種群多樣化，及其可靠性和有效性。

4.2.1 編碼

采用二進(jìn)制編碼方式，對(duì)被選中的子集賦值1，未被選中的子集賦值0，則任意一個(gè)問題解可以用一組0與1的二進(jìn)制碼表示，即表示為一條染色體。

4.2.2 初始化種群

種群由一組染色體(或解)組成，為提升搜索速度并提高搜準(zhǔn)率，采用多輪隨機(jī)不重復(fù)解策略產(chǎn)生種群，過程如下：

(1)設(shè)定一個(gè)數(shù)組array保存初始化種群，轉(zhuǎn)步驟(2)。

(2)隨機(jī)產(chǎn)生一組問題解，刪除不滿足條件的解，并與數(shù)組array中的問題解逐一比較，刪除重復(fù)解，將剩余滿足條件且不重復(fù)的解存入數(shù)組array，轉(zhuǎn)步驟(3)。

(3)判定數(shù)組array中解的個(gè)數(shù)是否滿足種群規(guī)模，如果不滿足，則轉(zhuǎn)步驟(2)，否則退出初始化過程。

多輪隨機(jī)不重復(fù)解策略的優(yōu)勢(shì)在于，不但實(shí)現(xiàn)的初始化種群由可行解組成，而且能夠盡可能保證可行解的多樣性，為提升搜索速度并提高搜準(zhǔn)率打下基礎(chǔ)。

4.2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)反映被選個(gè)體(染色體)的優(yōu)劣，個(gè)體的性能越好(滿足約束條件且權(quán)重小)，適應(yīng)度函數(shù)值越大；個(gè)體的性能越差(不滿足約束條件或權(quán)重大)，適應(yīng)度函數(shù)值越小。適應(yīng)度函數(shù)F(X)定義為：

(7)

s.t.

其中：X為候選解(即一組子集劃分)；Θ∪(X)，Θ∩(X)，ΘC(X)分別為并集、交集和約束的懲罰因子；r∪，r∩，rC分別表示并集、交集和約束懲罰程度；ΘW(X)為目標(biāo)函數(shù)。

4.2.4 選擇操作

選擇操作需要保持種群的多樣性，本文采取混合式選擇法，按一定規(guī)則選取一組較優(yōu)個(gè)體與較差個(gè)體作為下一輪迭代種群，具體過程如下：

(1)在可行解作為初始種群的條件下，種群中的較優(yōu)個(gè)體靠近最優(yōu)區(qū)域，較差個(gè)體會(huì)遠(yuǎn)離最優(yōu)區(qū)域。任一個(gè)體都具有個(gè)體偏移特征，個(gè)體偏移反映個(gè)體在種群中所處的位置(靠近或遠(yuǎn)離最優(yōu)區(qū)域)，設(shè)Un(Xi,·)為個(gè)體i的偏移量，則：

(8)

(9)

式中：Un(Xi,Xj)為個(gè)體i相對(duì)個(gè)體j的偏移量，反映個(gè)體i相對(duì)個(gè)體j所處的位置；Un(Xi,·)反映個(gè)體i所處種群的位置；N0為種群規(guī)模。

(2)對(duì)種群中的所有個(gè)體i，根據(jù)式(8)和式(9)計(jì)算其個(gè)體偏移量Un(Xi,·)。

(3)根據(jù)步驟(2)計(jì)算結(jié)果，借鑒聚類思想將種群等分為較優(yōu)個(gè)體和較差個(gè)體兩類。

(4)對(duì)較優(yōu)個(gè)體類而言，以等概率選擇一定數(shù)量個(gè)體，根據(jù)式(7)計(jì)算適應(yīng)度并排序，選取適應(yīng)度值最大的個(gè)體為候選個(gè)體，重復(fù)步驟(4)，直至滿足退出條件。

(5)對(duì)較差個(gè)體類而言，以等概率選擇一定數(shù)量個(gè)體，根據(jù)式(7)計(jì)算適應(yīng)度并排序，選取適應(yīng)度值最小的個(gè)體為候選個(gè)體，重復(fù)步驟(5)，直至滿足退出條件。

(6)合并步驟(4)和步驟(5)產(chǎn)生的候選個(gè)體，組成下一輪迭代種群。

選擇規(guī)則基于以上混合選擇策略，可以保證被選種群趨于多樣化。

4.2.5 交叉與變異操作

(1)交叉操作體現(xiàn)全局搜索能力，本文采取多輪多維度多點(diǎn)交叉法，具體過程如下：

1)基于被選中種群，按較優(yōu)個(gè)體與較優(yōu)個(gè)體、較優(yōu)個(gè)體與較差個(gè)體、較差個(gè)體與較差個(gè)體兩兩隨機(jī)組合思想，根據(jù)步驟(2)進(jìn)行交叉操作。

2)交叉操作采用隨機(jī)多點(diǎn)交叉策略，即任意兩個(gè)個(gè)體隨機(jī)選擇多個(gè)交叉點(diǎn)進(jìn)行多點(diǎn)交叉。

3)對(duì)新產(chǎn)生的種群，根據(jù)選擇操作中的步驟(2)和步驟(3)將種群劃分為較優(yōu)個(gè)體集和較差個(gè)體集，并進(jìn)行合并和排序。

4)如果滿足退出條件，則退出交叉操作，否則轉(zhuǎn)步驟(1)。

交叉規(guī)則優(yōu)勢(shì)在于，通過較優(yōu)個(gè)體與較優(yōu)個(gè)體、較優(yōu)個(gè)體與較差個(gè)體、較差個(gè)體與較差個(gè)體多輪多維度多點(diǎn)的交叉操作，在維持種群多樣性的同時(shí)，不斷探索新的區(qū)域，提升全局搜索能力。

(2)變異操作體現(xiàn)局部挖掘能力，具體過程如下：

1)基于上述交叉操作結(jié)果，對(duì)被選中的種群重新按適應(yīng)度值的大小排序，并計(jì)算每個(gè)個(gè)體i的適應(yīng)度比例Fitness(Xi)，

(10)

式中N0為種群規(guī)模。

2)根據(jù)式(11)計(jì)算每個(gè)個(gè)體i的累積適應(yīng)度比例，

(11)

3)根據(jù)均勻分布策略隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)γ∈[0,1]。

4)若γ的值落在兩個(gè)個(gè)體累積適應(yīng)度比例之間，則以累積適應(yīng)度比例高的個(gè)體為被選待變異個(gè)體，并隨機(jī)選取一個(gè)指針作為變異點(diǎn)進(jìn)行變異操作。

5)判定變異后的新個(gè)體是否在本輪中重復(fù)出現(xiàn)，是則重新選取一個(gè)指針作為變異點(diǎn)進(jìn)行變異操作，直至出現(xiàn)新個(gè)體。

6)如果滿足退出條件，則退出變異操作，否則轉(zhuǎn)步驟(3)。

變異規(guī)則的優(yōu)勢(shì)在于，對(duì)交叉操作產(chǎn)生的較優(yōu)新個(gè)體所在區(qū)域優(yōu)先進(jìn)行局部深挖，并在深挖過程中不斷調(diào)整深挖方向，以保持種群的多樣性，進(jìn)一步提升全局搜索能力。

4.2.6 算法過程

步驟1按照二進(jìn)制編碼規(guī)則和適應(yīng)度函數(shù)定義確定適應(yīng)度函數(shù)F(X)。

步驟2初始化參數(shù)r∩，r∪，rC，設(shè)定種群規(guī)模N0，并根據(jù)定義初始化種群，設(shè)定迭代次數(shù)It0，根據(jù)適應(yīng)度函數(shù)F(X)計(jì)算種群中所有個(gè)體的適應(yīng)度值。

步驟3為保持個(gè)體多樣化，根據(jù)種群選擇規(guī)則挑選候選種群。

步驟4根據(jù)交叉與變異規(guī)則產(chǎn)生下一代種群，再根據(jù)適應(yīng)度函數(shù)F(X)計(jì)算下一代種群的適應(yīng)度值。

步驟5檢查搜索條件是否達(dá)到退出準(zhǔn)則，是則保存搜索到的解集并退出，否則轉(zhuǎn)步驟3。

4.3 算法有效性分析

HGA的有效性體現(xiàn)在提高全局搜索能力和提升算法的收斂速度。根據(jù)HGA的思想，在編碼階段采用二進(jìn)制編碼方式可降低算法設(shè)計(jì)難度；在初始化階段，以多樣化的可行解作為初始種群，可在提高搜優(yōu)概率的同時(shí)提升收斂速度；在下一代選擇階段，采用有目的等概率的混合式選擇操作可提高全區(qū)域搜優(yōu)概率；在交叉階段，采用多輪多維度多點(diǎn)操作可提升探索新區(qū)域的能力；在變異階段，通過較優(yōu)新個(gè)體優(yōu)先動(dòng)態(tài)變異操作，可以進(jìn)一步提升全局搜索能力并保證算法快速收斂?？傊?，HGA在每次迭代搜索過程中，都能保持種群的多樣性和可靠性，從而為提高全局搜索能力和算法的收斂速度打下基礎(chǔ)。

5 實(shí)驗(yàn)與分析

(1)軟硬件環(huán)境

20個(gè)曙光天闊系列服務(wù)器，CPU型號(hào)為Xeon E5-2620V3，內(nèi)存8 G，SATA硬盤300 G，操作系統(tǒng)為SUSE Linux Enterprise Server 15。

(2)核心參數(shù)設(shè)置

在綜合考慮文獻(xiàn)對(duì)參數(shù)取值的建議并基于多次重復(fù)實(shí)驗(yàn)的結(jié)果，參數(shù)設(shè)定為：r∪,r∩,rC∈(0.2,0.6)。劃分權(quán)重中兩個(gè)線性加權(quán)系數(shù)取值分別在0.35～0.65之間，且兩系數(shù)之和為1[7-8]，It0∈[80～100]，N0∈[60～80]。

(3)場(chǎng)景模擬

將20個(gè)曙光服務(wù)器分成兩個(gè)功能區(qū)，其中12個(gè)服務(wù)器隨機(jī)放置在不同區(qū)域，用于仿真生產(chǎn)線及其所提交的服務(wù)請(qǐng)求(例如生產(chǎn)線數(shù)量及規(guī)模增加或減少，則服務(wù)請(qǐng)求量變大或變小)，服務(wù)請(qǐng)求類型包括傳輸請(qǐng)求、存儲(chǔ)請(qǐng)求、計(jì)算請(qǐng)求等。剩余8個(gè)服務(wù)器同樣隨機(jī)放置在不同區(qū)域，用于仿真工業(yè)邊緣云和處理接入請(qǐng)求[15-17]。

(4)對(duì)比算法

為展示實(shí)驗(yàn)的客觀性，分別選取智慧城市的邊緣服務(wù)器部署算法(Edge Server Placement algorithm，ESP)[8]和自適應(yīng)Cloudlet部署方法(Adaptive Cloudlet Placement Method，ACPM)[12]與本文HGA進(jìn)行比較。

(5)測(cè)試指標(biāo)

為體現(xiàn)實(shí)驗(yàn)的全面性，本文從多個(gè)維度驗(yàn)證HGA的性能：

1)期望負(fù)載偏差率(Expectation Load Deviation Rate，ELDR)

ELDR=(算法實(shí)際總負(fù)載-期望最小總負(fù)載) /

期望最小總負(fù)載。

該指標(biāo)主要衡量各算法實(shí)際計(jì)算的總負(fù)載距離期望總負(fù)載的程度，值越小越靠近期望總負(fù)載。

2)期望服務(wù)延時(shí)偏差率(Expectation Service Delay Deviation Rate，ESDDR)

ESDDR=(算法實(shí)際總服務(wù)延時(shí)-

期望最小總服務(wù)延時(shí)) /期望最小總服務(wù)延時(shí)。

該指標(biāo)主要衡量各算法實(shí)際計(jì)算的總服務(wù)延時(shí)距離期望總服務(wù)延時(shí)的程度，值越小越靠近期望總服務(wù)延時(shí)。

3)算法收斂率(Algorithm Convergence Rate，ACR)

ACR=(收斂延時(shí)均值-正常收斂均值) /

正常收斂均值。

該指標(biāo)主要衡量各部署算法的執(zhí)行效率和收斂速度。

4)解誤差率(Solutions Error Rate，SER)

SER=(算法搜索到最優(yōu)解均值-期望最優(yōu)解) /

期望最優(yōu)解。

該指標(biāo)主要衡量HGA、精英遺傳算法(Elite Genetic Algorithm，EGA)[18-19]與GA[14]的全局最優(yōu)解搜索能力。

實(shí)驗(yàn)1通過不斷增加仿真生產(chǎn)線數(shù)量并給定相應(yīng)的部署總成本，測(cè)試各類部署算法的ELDR。其中，處于不同區(qū)域的12個(gè)服務(wù)器隨機(jī)模擬功能各異的生產(chǎn)線，并由各生產(chǎn)線模擬數(shù)量不同的服務(wù)請(qǐng)求；剩余放置在不同區(qū)域的8個(gè)服務(wù)器分別模擬功能一致的工業(yè)邊緣云,并由工業(yè)邊緣云各自模擬計(jì)算生產(chǎn)線請(qǐng)求時(shí)的處理情況。

如圖2所示，生產(chǎn)線為200個(gè)時(shí)，HGA的ELDR接近7.6%，ESP的ELDR接近9.1%，ACPM的ELDR接近9.3%，HGA相對(duì)其他兩種算法分別降低了16.4%和18.2%。

生產(chǎn)線為250個(gè)時(shí)，HGA的ELDR接近11%，ESP的ELDR接近15%，ACPM的ELDR接近14.6%，HGA相對(duì)其他兩種算法分別降低了26.6%和24.6%。

生產(chǎn)線為300個(gè)時(shí)，HGA的ELDR接近15%，ESP的ELDR接近23%，ACPM的ELDR接近28%，HGA相對(duì)其他兩種算法分別降低了34.7%和36.4%。

實(shí)驗(yàn)2基于實(shí)驗(yàn)1的環(huán)境，測(cè)試各類部署算法的ESDDR。

如圖3所示，生產(chǎn)線為200個(gè)時(shí)，HGA的ESDDR接近9.1%，ESP的ESDDR接近11.8%，ACPM的ESDDR接近11.5%，HGA相對(duì)其他兩種算法分別降低了22.8%和20.8%。

生產(chǎn)線為250個(gè)時(shí)，HGA的ESDDR接近13%，ESP的ESDDR接近18.5%，ACPM的ESDDR接近19%，HGA相對(duì)其他兩種算法分別降低了29.7%和31.5%。

生產(chǎn)線為300個(gè)時(shí)，HGA的ESDDR接近16.6%，ESP的ESDDR接近23.9%，ACPM的ESDDR接近24.6%，HGA相對(duì)其他兩種算法分別降低了30.5%和32.5%。

由實(shí)驗(yàn)1和實(shí)驗(yàn)2可見，隨著生產(chǎn)線規(guī)模和數(shù)量的增加，各算法的ELDR和ESDDR均相應(yīng)增加。基于K-median的ESP主要根據(jù)移動(dòng)用戶的異構(gòu)應(yīng)用需求分類部署，但生產(chǎn)線的生產(chǎn)任務(wù)同構(gòu)無法有效進(jìn)行分類部署，降低了ESP搜索最優(yōu)解的性能；ACPM主要根據(jù)地理信息位置預(yù)測(cè)移動(dòng)用戶的遷移軌跡并預(yù)留多個(gè)潛在部署點(diǎn)，但生產(chǎn)線動(dòng)態(tài)調(diào)整頻率偏低，無法通過軌跡預(yù)測(cè)潛在部署點(diǎn)，降低了ACPM搜索最優(yōu)解的性能。因此，HGA的性能相對(duì)較優(yōu)。

實(shí)驗(yàn)3基于實(shí)驗(yàn)1的環(huán)境，測(cè)試各類部署算法的ACR。

如圖4所示，生產(chǎn)線為200個(gè)時(shí)，HGA的ACR接近5.8%，ESP的ACR接近8.1%，ACPM的ACR接近7.7%，HGA相對(duì)其他兩種算法分別降低了28.3%和24.6%。

生產(chǎn)線為250個(gè)時(shí)，HGA的ACR接近10.1%，ESP的ACR接近14.6%，ACPM的ACR接近13.1%，HGA相對(duì)其他兩種算法分別降低了30.8%和22.9%。

生產(chǎn)線為300個(gè)時(shí)，HGA的ACR接近15%，ESP的ACR接近22%，ACPM的ACR接近20.6%，HGA相對(duì)其他兩種算法分別降低了31.8%和27.1%。

由實(shí)驗(yàn)3可見，隨著生產(chǎn)線規(guī)模和數(shù)量的增加，各算法的ACR均相應(yīng)增加，以ESP增加幅度為最大，主要原因是ESP的分類策略(基于K-median思想)有較大的時(shí)間開銷；ACPM軌跡預(yù)測(cè)策略的時(shí)間開銷得益于生產(chǎn)線動(dòng)態(tài)調(diào)整的頻率較低，因軌跡預(yù)測(cè)收斂性較快而提升了算法的執(zhí)行效率，但相對(duì)于HGA，其收斂性仍然較差。

實(shí)驗(yàn)4基于實(shí)驗(yàn)1的環(huán)境，測(cè)試HGA，EGA及傳統(tǒng)GA的SER。

如圖5所示，生產(chǎn)線為200個(gè)時(shí)，HGA的SER接近1.2%，EGA的SER接近1.25%，GA的SER接近1.3%， HGA分別降低了4.16%和7.6%。

生產(chǎn)線為250個(gè)時(shí)，HGA的SER接近1.9%，EGA的SER接近2.12%，GA的SER接近2.3%， HGA分別降低了10.3%和17.3%。

生產(chǎn)線為300個(gè)時(shí)，HGA的SER接近3.2%，EGA的SER接近3.9%，GA的SER接近4.7%， HGA分別降低了17.9%和31.9%。

由實(shí)驗(yàn)4可見，隨著生產(chǎn)線規(guī)模和數(shù)量的增加，各算法的SER均相應(yīng)增加。以GA為例，其思想是隨機(jī)產(chǎn)生初始種群，采用輪盤賭策略選擇種群，交叉和變異時(shí)完全采用隨機(jī)策略，這些操作將導(dǎo)致搜索速度變慢且易陷入局部最優(yōu)。而EGA的思想在于每次迭代時(shí)，盡可能將較優(yōu)解保留至下一代種群中，這樣雖然能夠提高收斂性，但是易陷入局部最優(yōu)，再加上隨機(jī)初始化種群、隨機(jī)單點(diǎn)交叉及基本變異等操作，進(jìn)一步限制了其搜索準(zhǔn)度。因此，HGA的全局最優(yōu)解搜索能力較優(yōu)。

通過以上多組實(shí)驗(yàn)測(cè)試說明，HGA在優(yōu)化傳統(tǒng)GA弊端(早熟)的同時(shí)，相對(duì)已有科研成果，能夠更加有效地對(duì)工業(yè)邊緣云進(jìn)行部署，為后期工業(yè)物聯(lián)網(wǎng)的場(chǎng)景應(yīng)用打下了基礎(chǔ)。

6 結(jié)束語

以物聯(lián)網(wǎng)為代表的新一代信息技術(shù)與制造業(yè)深度融合是學(xué)界和業(yè)界共同關(guān)注的話題，本文以此為背景，討論了工業(yè)物聯(lián)網(wǎng)與邊緣端數(shù)字孿生深度融合的一個(gè)基礎(chǔ)性問題——工業(yè)邊緣云部署問題，分析了其探討意義及價(jià)值，從優(yōu)化論角度將該問題轉(zhuǎn)化為帶約束的最小子集劃分問題，并針對(duì)該NP難問題提出一種HGA。算法以可行解作為初始種群，經(jīng)過混合選擇法、多維度交叉和優(yōu)先變異等操作，能夠較好地求解實(shí)際問題。通過對(duì)比實(shí)驗(yàn)，算法在ELDR,ESDDR,ACR,SER 4方面均有較優(yōu)的性能。

雖然本文所提算法在解決工業(yè)邊緣云部署問題上表現(xiàn)良好，但是仍有需要改進(jìn)之處：①在新一代信息技術(shù)加持下，生產(chǎn)線和生產(chǎn)設(shè)備必將自動(dòng)化、智能化。在產(chǎn)能驅(qū)動(dòng)下，生產(chǎn)線和生產(chǎn)設(shè)備會(huì)根據(jù)實(shí)際情況智能化動(dòng)態(tài)調(diào)整，如何實(shí)現(xiàn)自適應(yīng)性動(dòng)態(tài)工業(yè)邊緣云部署是今后工作的一個(gè)重點(diǎn)。②隨著產(chǎn)業(yè)分工的全球化，跨國型企業(yè)生產(chǎn)線規(guī)模必將延伸，本文算法所支持的生產(chǎn)線規(guī)模依然偏小，未來如何支持上千個(gè)生產(chǎn)線的工業(yè)邊緣云部署是今后工作的另一個(gè)方向。