戴志明，周明拓?，楊旸，李劍，劉軍

(1 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；2 中國科學(xué)院大學(xué)，北京 100049；3 上海霧計算實驗室，上海 201210；4 上海科技大學(xué)，上海 201210；5 思科(中國)有限公司上海分公司，上海 201103) (2019年12月13日收稿； 2020年3月19日收修改稿)

新一代信息技術(shù)例如物聯(lián)網(wǎng)、云計算、霧計算、人工智能、大數(shù)據(jù)等為許多行業(yè)帶來了寶貴的發(fā)展機(jī)遇[1-2]。傳統(tǒng)工業(yè)正經(jīng)歷著信息技術(shù)發(fā)展引起的技術(shù)變革。智能工廠就是在這樣一個背景下誕生的[3-4]。與傳統(tǒng)工廠相比，智能工廠需要處理海量的數(shù)據(jù)。一種方式是利用遠(yuǎn)端云計算，但是存在許多弊端[5]，例如：時延比較大、帶寬的要求比較高，以及安全和隱私無法保證。霧計算的出現(xiàn)能夠緩解這些問題[6]，它將計算、存儲、控制和網(wǎng)絡(luò)功能從云轉(zhuǎn)移到邊緣設(shè)備中，從而能夠減少數(shù)據(jù)傳輸時延和所需帶寬。它允許一群相鄰的終端用戶、網(wǎng)絡(luò)邊緣設(shè)備和訪問設(shè)備協(xié)同完成需要資源的任務(wù)。因此，許多原本需要云計算完成的計算任務(wù)可以通過數(shù)據(jù)產(chǎn)生設(shè)備周邊的分散計算資源在網(wǎng)絡(luò)邊緣有效完成。

智能工廠可以通過容器技術(shù)和容器自動編排的工具實現(xiàn)資源虛擬化和服務(wù)自動化部署[7]。容器是一種虛擬化的技術(shù)，與虛擬機(jī)相比，它更加輕量并且可以快速地在不同的操作平臺上部署。目前常見的有Docker容器。相關(guān)的編排工具有Kubernetes，這是一個能夠跨越多個計算節(jié)點并且管理多個計算節(jié)點上的容器的平臺工具。我們可以將智能工廠中的應(yīng)用容器化[8]，成為Docker容器，然后使用Kubernetes將Docker容器自動化部署到合適的霧計算節(jié)點上[9-10]。

如何將上述容器合理地部署到智能工廠的霧計算節(jié)點上，充分利用霧計算資源，本質(zhì)是一個資源分配調(diào)度問題。針對此問題目前已有一些相關(guān)研究。Skarlat等[11]對云、霧兩層的資源配置問題進(jìn)行優(yōu)化，將任務(wù)時延降低39%，為時延敏感的應(yīng)用提供了一個霧資源配置方案。Yin等[12]將虛擬機(jī)替換為容器，執(zhí)行智能工廠中的任務(wù)，提出基于容器的任務(wù)調(diào)度算法。將任務(wù)執(zhí)行分為2個步驟：首先考慮任務(wù)是接受還是拒絕執(zhí)行，再考慮是在本地霧節(jié)點運行還是上傳云，實驗驗證表明任務(wù)調(diào)度算法使任務(wù)執(zhí)行時間減少10%并且可以提高5%的任務(wù)并發(fā)能力。Gedawy等[13]利用一組異構(gòu)的移動和互聯(lián)網(wǎng)設(shè)備組成一個邊緣微云，在保證能耗低于閾值的條件下，最大化計算吞吐量和最小化時延。為解決這個非線性問題，他們使用了啟發(fā)式算法。其仿真結(jié)果表明，計算吞吐量提高30%并且時延減少10%～40%。但是現(xiàn)有的研究存在一些不足：其一，基本都是針對任務(wù)的處理時間進(jìn)行優(yōu)化，沒有考慮智能工廠中有限的計算資源；其二，基本都是針對某一個方面進(jìn)行改進(jìn)，并沒有從整體上結(jié)合智能工廠的特性，對其進(jìn)行全面優(yōu)化。

相比目前的其他研究，本文根據(jù)智能工廠的任務(wù)特性，使用Kubernetes實現(xiàn)智能工廠中的任務(wù)自動化部署，并且從框架、系統(tǒng)模型和算法3個方向?qū)χ悄芄S進(jìn)行整體改進(jìn)。首先對智能工廠中的霧計算框架進(jìn)行改進(jìn)，然后在改進(jìn)框架的基礎(chǔ)上將問題模型化，最后再利用改進(jìn)的算法對霧計算資源調(diào)度模型進(jìn)行求解，在保證任務(wù)時延最小的情況下，盡可能最大化智能工廠中資源利用率。通過使用Kubernetes實現(xiàn)智能工廠中任務(wù)的自動化部署，并且通過改進(jìn)的霧計算調(diào)度框架對任務(wù)進(jìn)行合理的分類處理。

本文的工作和貢獻(xiàn)主要包括以下3部分：

1)框架改進(jìn)：為了使智能工廠中的任務(wù)能夠得到合理的部署，基于一些工業(yè)互聯(lián)網(wǎng)中的霧計算架構(gòu)[14-15]，結(jié)合智能制造工廠的特性和需求，使用Kubernetes對現(xiàn)有的智能工廠的霧計算架構(gòu)進(jìn)行改進(jìn)，能夠?qū)⒉煌娜蝿?wù)自動地部署到不同的霧計算節(jié)點上，進(jìn)行不同的處理。并基于此改進(jìn)架構(gòu)，將智能工廠中的任務(wù)時延和集群均衡度協(xié)同優(yōu)化問題模型化，建立約束條件下的智能工廠霧計算資源調(diào)度模型。

2)算法改進(jìn)：Kubernetes的缺省調(diào)度策略是調(diào)度完一個容器應(yīng)用后才能調(diào)度下一個容器應(yīng)用，這種調(diào)度策略的缺點是結(jié)果局部最優(yōu)，如果直接使用Kubernetes的缺省調(diào)度器，會造成整個霧計算集群資源使用的不均衡，從而無法充分利用資源，并且智能工廠中任務(wù)的計算時延會增加。智能工廠中，任務(wù)和霧計算資源的管理分配是一個非線性問題，因此可以使用啟發(fā)式算法進(jìn)行解決[16]，比如遺傳算法[17]，但是傳統(tǒng)遺傳算法只能進(jìn)行單目標(biāo)優(yōu)化、輪盤賭算法容易陷入局部最優(yōu)，并且迭代效率太慢。因此本文提出基于遺傳算法改進(jìn)的區(qū)間劃分遺傳調(diào)度 (interval division genetic scheduling arithmetic，IDGSA)算法，將個體按區(qū)間劃分，使用區(qū)間劃分的思想，對傳統(tǒng)遺傳算法的交叉變異算子和輪盤賭選擇算子進(jìn)行優(yōu)化，通過更改目標(biāo)優(yōu)化權(quán)重，解決模型中任務(wù)時延和集群均衡度協(xié)同優(yōu)化問題，得到全局范圍內(nèi)的近似最優(yōu)解。

3)仿真驗證：本文利用一個生產(chǎn)襪子的智能制造工廠為例開展了仿真實驗驗證。實驗結(jié)果表明，在本文的實驗環(huán)境條件下，與Kubernetes缺省的調(diào)度算法相比，IDGSA算法數(shù)據(jù)處理時間減少50%，提高霧計算資源使用率達(dá)60%。與傳統(tǒng)的遺傳算法相比，在迭代次數(shù)更少的情況下，使得數(shù)據(jù)的處理時間減少7%，霧計算資源的使用率提高9%。這表明IDGSA算法能夠在保證時延較低的同時，最大化集群資源的使用率,且能夠在迭代次數(shù)更少的情況下獲得更優(yōu)的結(jié)果。

1 智能工廠中的調(diào)度框架

1.1 任務(wù)分類

智能工廠中，存在對時延和存儲有不同需求的多種任務(wù)。為了提高智能工廠的生產(chǎn)效率，對智能制造工廠中的不同任務(wù)進(jìn)行有效的分類是必要的。

·實時任務(wù)：數(shù)據(jù)小，同時要求時延小的任務(wù)，例如：對于關(guān)鍵智能設(shè)備的運行狀況以及故障的判斷。

·處理任務(wù)：數(shù)據(jù)較大、對于時延有一定要求的任務(wù)，例如：對于整個生產(chǎn)制造過程中的產(chǎn)品的質(zhì)量的監(jiān)控，工廠內(nèi)視頻信息的處理，以及智能工廠中生產(chǎn)用料的統(tǒng)計。

·存儲任務(wù)：數(shù)據(jù)大、對于時延要求不是很高的任務(wù)，例如：針對于各個生產(chǎn)線路的數(shù)據(jù)分析、整個工廠的能耗情況的分析，以及其他能提升工廠效益的智能計算和處理。

1.2 任務(wù)分配

對任務(wù)進(jìn)行分級后如何將任務(wù)分配到合適的霧計算節(jié)點上是一個問題，以前使用的是霧、云分級的方式進(jìn)行任務(wù)的部署[18-19]，但是并沒有涉及到自動化部署以及容器應(yīng)用的監(jiān)控。因此本文結(jié)合Kubernetes對智能工廠中的霧計算框架做了進(jìn)一步的改進(jìn)。

Kubernetes中的組件主要包括：

Etcd：用于保存集群中所有網(wǎng)絡(luò)的配置和對象狀態(tài)信息；

Api Server：提供api接口并且是其他模塊之間數(shù)據(jù)交互和通信的樞紐；

Scheduler：Kubernetes中調(diào)度的執(zhí)行模塊，通過算法將任務(wù)調(diào)度到合適的節(jié)點上；

RC(replication controller)/Deployment：對Kubernetes集群中的任務(wù)的數(shù)量進(jìn)行監(jiān)控，穩(wěn)定任務(wù)數(shù)量。

本文提出的智能工廠的調(diào)度框架如圖1所示，首先將智能工廠中的任務(wù)進(jìn)行容器化，然后為容器化的任務(wù)打上對應(yīng)的Label，這些信息會存儲在Etcd中，隨后Scheduler會和Api server進(jìn)行交互，獲取Kubernetes集群中還未部署的任務(wù)，然后根據(jù)任務(wù)的Label將其自動部署到對應(yīng)的節(jié)點中。對于Label為實時任務(wù)的容器應(yīng)用將其分配給專屬的霧計算節(jié)點進(jìn)行處理，這類節(jié)點靠近設(shè)備，并且性能突出，能夠在最快的時間內(nèi)給予結(jié)果反饋。Label為存儲任務(wù)的容器應(yīng)用，將其部署在霧存儲節(jié)點上，這類節(jié)點處理性能一般，但是存儲性能好，更接近云端，能夠在合適的時間將數(shù)據(jù)上傳給云數(shù)據(jù)中心進(jìn)行處理。而對于Label為處理任務(wù)的容器應(yīng)用，將其部署在霧節(jié)點資源池上，資源池中的節(jié)點處理性能和存儲性能都比較良好，能夠?qū)χ悄芄S中數(shù)量最多的任務(wù)進(jìn)行處理。在整個過程中，Kubernetes中的Deployment模塊會對整個Kubernetes中的容器應(yīng)用進(jìn)行監(jiān)控，當(dāng)某個容器應(yīng)用出現(xiàn)問題的時候會重新創(chuàng)建。

圖1 任務(wù)調(diào)度框架Fig.1 Task scheduling framework

因為Label為處理任務(wù)的容器應(yīng)用最多，如何將這一部分的時延降低和資源使用率提高是最為重要的，因此后續(xù)提出相應(yīng)的系統(tǒng)模型和IDGSA算法對這類任務(wù)進(jìn)行合理的分配。

2 系統(tǒng)模型

2.1 系統(tǒng)模型描述

在一個智能制造工廠中，某條生產(chǎn)線就是一個服務(wù)，智能工廠中的服務(wù)可以使用appj(appj∈A)來定義，其中j代表智能工廠中的第j個服務(wù)，A代表整個智能工廠中的所有服務(wù)的集合。在執(zhí)行某個生產(chǎn)線appj的過程中使用到的所有容器應(yīng)用定義為集合S，其中第i個容器應(yīng)用定義為msi。msi,cpu，msi,memory分別代表容器應(yīng)用msi對霧計算節(jié)點CPU和內(nèi)存的最低需求，其中所有容器應(yīng)用在獨占一個CPU進(jìn)行任務(wù)處理的時候，所需要的時間為一個單位時間，用ut(unit time)表示，因為在處理任務(wù)的時候，對不同的容器應(yīng)用的個數(shù)可能有不同的需求，因此使用msreqi表示這條生產(chǎn)線上需要多少個這樣的容器應(yīng)用。在任務(wù)的處理過程中，容器應(yīng)用是按先后順序執(zhí)行的，因此容器應(yīng)用之間可能會使用到彼此的數(shù)據(jù)或者處理結(jié)果，所以2個具有消費關(guān)系的容器應(yīng)用可以表示為(msprovider,msconsumer)prov/cons，表示msconsumer需要用到msprovider的處理結(jié)果。霧計算節(jié)點資源池可以定義為集合P，節(jié)點資源池里面的霧計算節(jié)點使用pml表示，如果某個容器應(yīng)用msi被部署在節(jié)點pml上，則可以表示為alloc(msi)=pml。其中pml,cpu，pml,memory分別代表該霧計算節(jié)點的CPU資源和內(nèi)存資源。

2.2 優(yōu)化目標(biāo)

在本文中優(yōu)化目標(biāo)有3個：1)任務(wù)計算時間；2)集群資源均衡度；3)集群均衡度和時延均衡因子。

2.2.1 任務(wù)計算時間(Object1)

因為生產(chǎn)線任務(wù)appi的一些容器應(yīng)用之間可能存在消費關(guān)系，因此整個任務(wù)的計算時間可以使用所有容器任務(wù)完成時間中的最大值表示，如下所示

AllServicetime=max(S(ms1),

S(ms2),…,S(msi)).

(1)

其中S(msi)代表容器應(yīng)用msi的數(shù)據(jù)處理時間。

單個容器應(yīng)用的計算時間分為2種情況：1)與其他容器應(yīng)用沒有消費關(guān)系；2)與其他容器應(yīng)用有消費關(guān)系。所以單個容器應(yīng)用的計算時間可以表示為

S(msi)=max(selfTime(msi),waitTime(msi)).

(2)

waitTime(msi)=max(S(msj)+transTime(msj)),

?msj|(msj,msi)pro/cons.

(3)

其中transTime(msj)表示provider容器應(yīng)用將處理結(jié)果傳輸給consumer容器應(yīng)用的時間。為了便于計算，如果2個容器應(yīng)用部署在同一個霧計算節(jié)點上，那么transTime(msj)為0，如果在不同的霧計算節(jié)點上，那么transTime(msj)=0.1×S(msj)。

2.2.2 集群資源均衡度(Object2)

為了能夠充分使用集群中的霧計算資源，利用集群均衡度來定義資源的使用情況，應(yīng)該盡量保證節(jié)點中各種資源使用情況基本一致，避免出現(xiàn)某一個霧計算節(jié)點上CPU資源使用過度，但是還有許多內(nèi)存資源的情況。同時集群中各個節(jié)點的資源使用情況也應(yīng)當(dāng)一致。因此集群資源均衡度可以分為2個部分來考慮：1)單個霧計算節(jié)點上各種資源的均衡使用情況；2)整個集群中，不同的節(jié)點之間資源的均衡使用情況。

所以可以將整個集群均衡度公式化表示為

AllBalance=clusterBalance+singleBalance.

(4)

其中

clusterBalace=

(5)

(6)

clusterBalance等于整個集群中不同霧計算節(jié)點的均衡度，clusterBalance的值越小就表示整個集群中，不同的霧計算節(jié)點上的資源的使用情況越均勻，沒有出現(xiàn)一些霧計算節(jié)點超負(fù)荷運行、而有些霧計算節(jié)點有很多空余資源還沒有使用的現(xiàn)象。

(7)

singleBalance代表某一個霧計算節(jié)點中各項資源使用均衡度，其中pml,cpuuse,pml,memoryuse分別代表節(jié)點上已經(jīng)使用的CPU和內(nèi)存。這樣可以保證在單個霧計算節(jié)點中不會出現(xiàn)一種資源使用過度、另外一種資源幾乎沒有使用的情況，使得節(jié)點上所有資源能夠充分地得到利用。

2.2.3 集群均衡度和時延均衡因子TSB(tradeoff between servicetime and balance)(Object3)

本文定義了一個均衡因子作為模型的另外一個優(yōu)化目標(biāo)，這個優(yōu)化目標(biāo)綜合任務(wù)計算時間和集群均衡度2個目標(biāo)，可以讓工廠通過調(diào)整集群均衡度在TSB中的權(quán)重實現(xiàn)工廠對Object1或Object2的倚重?？梢杂孟率奖硎?/p>

TSB(i)=β×AllBalance(i)′+

(1-β)×AllServicetime(i)′.

(8)

式中，使用min-max歸一化方法對2個不同量綱的優(yōu)化目標(biāo)進(jìn)行去量綱化處理，其中β代表集群資源均衡度在TSB所占的權(quán)重。

AllServicetime′,AllBalance′分別如下所示

其中:i，j代表迭代次數(shù)，NUM代表IDGSA算法限定的最大迭代次數(shù)。

綜上所訴，智能制造工廠中的容器應(yīng)用調(diào)度問題可以總結(jié)為：

Determine:

alloc(msi)=pml?msi∈appj

Minimizing: AllServicetime

AllBalance.

(9)

上述問題實際屬于NP(nondeterministic polynomial)問題，因此可以使用啟發(fā)式算法遺傳算法進(jìn)行解決，對于工廠中的任務(wù)分配，比較常用的就是遺傳算法。因此本文對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，提出IDGSA算法，引入?yún)^(qū)間劃分的概念，以改進(jìn)傳統(tǒng)遺傳算法的性能。

3 IDGSA算法

遺傳算法借鑒生物進(jìn)化論中遺傳、突變、自然選擇以及雜交等生物現(xiàn)象進(jìn)行種群優(yōu)化，尋找最優(yōu)個體。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度(fitness)大小選擇(selection)個體，并借助于自然遺傳學(xué)的遺傳算子(genetic operators)選擇合適的個體進(jìn)行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的解集的種群。但是在應(yīng)用于智能工廠時，傳統(tǒng)的遺傳算法無法處理雙目標(biāo)問題，對于一些無效的結(jié)果沒有進(jìn)行合理的處理。并且存在迭代速度慢、結(jié)果局部最優(yōu)等情況。

因此本文提出IDGSA算法，對于初始化產(chǎn)生的個體不是可行解的情況進(jìn)行修正(將資源使用過度的節(jié)點上的容器應(yīng)用分配給其他節(jié)點)，并且對傳統(tǒng)遺傳算法中的交叉變異算子和輪盤賭選擇算子使用區(qū)間劃分的思想進(jìn)行改進(jìn)。與傳統(tǒng)遺傳算法相比，在提高迭代速度的同時取得了更優(yōu)的結(jié)果，并且同時保證了種群的多樣性，避免陷入局部最優(yōu)的情況。表1中的偽代碼對IDGSA算法進(jìn)行了闡述。

表1 IDGSA算法偽代碼Table 1 IDGSA algorithm pseudo code

3.1 節(jié)點和任務(wù)初始化

首先根據(jù)給定的容器應(yīng)用任務(wù)和霧計算節(jié)點，隨機(jī)初始化一個種群。種群中每個個體由多個染色體組成。染色體為一組基于字符串的表達(dá)式，代表容器應(yīng)用集合與霧計算節(jié)點的對應(yīng)關(guān)系。在調(diào)度容器應(yīng)用的時候，一個節(jié)點上面可以部署多個容器應(yīng)用，一個容器應(yīng)用可以部署在任意一個霧計算節(jié)點中，染色體的表達(dá)式例子如表2所示。表2中的第1條染色體表示在主機(jī)pm1中部署了5個容器應(yīng)用，分別為{ms1,ms2,ms3,ms4,ms5}。

表2 染色體表達(dá)式Table 2 Chromosome expression

在算法開始的時候隨機(jī)生成多個個體，組成一個種群，將所有的容器應(yīng)用部署到不同的霧計算節(jié)點上，因為節(jié)點的資源有限，如果一個節(jié)點上面部署了太多的容器以至于超過節(jié)點的固有資源，那么這個個體就是無效的。因此首先在任務(wù)初始化的時候會對產(chǎn)生的個體進(jìn)行一次篩選，對于有效個體計算它們的任務(wù)計算時間。對于無效個體IDGSA算法提出的解決方案是：

1)統(tǒng)計無效個體中資源使用過度的節(jié)點；

2)將資源使用過度的節(jié)點上的容器應(yīng)用隨機(jī)分配給資源使用量為0、或者資源使用較少的節(jié)點；

3)生成新的子個體。

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

遺傳算法通過不斷的迭代，尋求最優(yōu)個體。每一代個體，都是通過適應(yīng)度函數(shù)來計算個體的適應(yīng)度。如果一個個體的適應(yīng)度越大，那么這個個體的生存能力就越強(qiáng)，因此被選擇生存下來的機(jī)率就越大。但是傳統(tǒng)的遺傳算法只定義了一個適應(yīng)度函數(shù)，無法同時優(yōu)化論文模型的2個目標(biāo)Object1和Object2。因此本文的IDGSA算法采用雙適應(yīng)度函數(shù)，分別是任務(wù)計算時間適應(yīng)函數(shù)timefitnessfunc和集群均衡度適應(yīng)函數(shù)balancefitnessfunc，其中2個適應(yīng)度函數(shù)的值分別是優(yōu)化目標(biāo)Object1和Object2的值，也就是AllServictime,AllBalance的值。采用雙適應(yīng)度函數(shù)可以使得IDGSA算法根據(jù)工廠中生產(chǎn)線的實際運行情況來選擇最適合的個體。如果生產(chǎn)線對于集群資源均衡更加看重，那么可以增加均衡度的權(quán)重；如果任務(wù)對于計算時間更加敏感，那么可以增加時間適應(yīng)度函數(shù)的權(quán)重，這樣便于企業(yè)根據(jù)不同的生產(chǎn)線或者生產(chǎn)策略進(jìn)行動態(tài)調(diào)整。因此結(jié)合2.2節(jié)的分析，IDGSA算法的雙適應(yīng)度函數(shù)可以使用TSB的值，這樣在迭代的過程中最符合預(yù)期的后代就能保留下來。因此IDGSA算法的適應(yīng)度函數(shù)即為式(8)。

3.3 區(qū)間劃分的選擇算子

傳統(tǒng)的遺傳算法選擇優(yōu)秀個體，進(jìn)行交叉、變異，產(chǎn)生下一代使用的方法叫做輪盤賭選擇算子。輪盤賭選擇算子的思想就是按照適應(yīng)度值的大小選擇個體進(jìn)行交叉、變異然后產(chǎn)生下一代個體。

傳統(tǒng)的輪盤賭算子思想：個體被選中的概率與其適應(yīng)度函數(shù)值成正比，設(shè)群體大小為N，個體xi的適應(yīng)度為f(xi)，則個體xi的選擇概率為

雖然這種選擇算子構(gòu)造簡單、應(yīng)用廣泛，但是存在缺陷，因為這樣雖然能保留優(yōu)秀的基因，但是保存下來的一直是那些適應(yīng)度值較大的個體。因此會導(dǎo)致種群的個體多樣性較差，最終使得結(jié)果趨向于局部最優(yōu)，無法得到更好的結(jié)果。為了避免IDGSA算法和傳統(tǒng)遺傳算法一樣，過早地收斂而放棄一些搜索子空間，本文提出一種使用區(qū)間劃分思想優(yōu)化的選擇算子：區(qū)間劃分輪盤賭選擇算子。

區(qū)間劃分的輪盤賭選擇算子操作步驟：

1)根據(jù)算法中的適應(yīng)度函數(shù)，計算得到種群中所有個體的適應(yīng)度值;

2)選出整個種群中適應(yīng)度值為最優(yōu)的以及最差的個體，然后將適應(yīng)度值在最優(yōu)與最差這個區(qū)間的個體劃分為M個等級，將種群的個體按照適應(yīng)度值分配至相應(yīng)的等級區(qū)域;

3)計算M個區(qū)域，每一個區(qū)域平均適應(yīng)度值(這個區(qū)域中所有個體值除以這個區(qū)域的個體數(shù)目)；

4)M個區(qū)域中，假設(shè)每個等級區(qū)域被選中的概率為Pm，其中Pm為當(dāng)前等級區(qū)域的平均適應(yīng)度值除以全部等級區(qū)域(M個)的平均適應(yīng)度值之和，計算Pm;

將整個種群定義為P，一個種群里面有N個個體，通過雙適應(yīng)度函數(shù)計算得到個體xi的適應(yīng)度值為f(xi)。在第T次迭代的時候，整個種群P中的個體的適應(yīng)度值可以表示為

P(T)={f(x1),f(x2),f(x3),…,f(xN)}

其中：f(xi)max,f(xj)min分別代表種群P中適應(yīng)度值的最大值和最小值，因此可以得到種群P的子空間的適應(yīng)度值的大小范圍為

因此可以將第T次迭代的種群P劃分為

其中：

所以個體xi被選中的概率為

(10)

從式(10)可以看出P(xi)與nm成反比，因此如果某一個區(qū)間的個體數(shù)量過大，那么其被選擇的概率會有所降低，如果區(qū)間的個體數(shù)量較小，那么被選擇的概率就會變大。所以當(dāng)整個種群中所有個體的適應(yīng)度差異過大的時候，區(qū)間劃分的輪盤賭選擇算子能夠避免適應(yīng)度較差的個體被提早淘汰，提高選擇的多樣性。同時能夠自動避免選擇的個體集中于某一區(qū)域，所以最后的結(jié)果能夠跳出局部最優(yōu)，得到全局范圍內(nèi)的近似最優(yōu)解。

3.4 區(qū)間劃分的交叉變異算子

傳統(tǒng)的遺傳算法使用輪盤賭算子選擇出合適的個體后，就會采用交叉、變異的方式獲得下一代個體。但是傳統(tǒng)的遺傳算法對種群的進(jìn)化采取統(tǒng)一的交叉變異算子的方式，這樣既不利于優(yōu)秀個體的保留，也不利于產(chǎn)生更加優(yōu)秀的個體。因此本文采用區(qū)間劃分的交叉變異算子，經(jīng)過適應(yīng)度函數(shù)計算種群中個體的適應(yīng)度后，將所有個體按照適應(yīng)度值的大小分成不同的區(qū)間，分別為適應(yīng)度值較低的突變區(qū)間和適應(yīng)度值較高的保留區(qū)間，以及適應(yīng)度值適中的漸變區(qū)間。然后對于不同區(qū)間里面的個體采取不同的交叉變異算子，對種群的個體進(jìn)行更新。

對于適應(yīng)度值高的個體，采用直接保留的方式，從而保證每一次迭代的過程中，最優(yōu)秀的個體能夠保存下來。對于適應(yīng)度低的個體，采用突變的方式改變其染色體，從而有機(jī)會將適應(yīng)度值低的個體突變成適應(yīng)度高的優(yōu)秀個體，使得種群在迭代的過程中能夠跳出局部最優(yōu)解并且避免早熟現(xiàn)象的發(fā)生，增加全局尋優(yōu)能力。對于適應(yīng)度值適中的個體，用我們自定義的區(qū)間劃分遺傳算子，選擇出父代然后通過交叉遺傳的方式將較優(yōu)秀的個體保留下來。

區(qū)間劃分交叉變異算子的思想如圖2所示。

圖2 區(qū)間劃分示意圖Fig.2 Interval division diagram

4 仿真實驗

4.1 實驗背景

論文采用背景是一個生產(chǎn)襪子的智能制造工廠 Socks Shop開展仿真實驗，實驗中的參數(shù)值來自于對Socks Shop的分析[20]。Socks Shop是一個微服務(wù)的Demo應(yīng)用，模擬一個生產(chǎn)襪子的智能制造工廠的實際運行情況，每個容器應(yīng)用對于資源的使用的情況來自于對這個Demo的負(fù)載測試，某個任務(wù)所需要的每個容器應(yīng)用的個數(shù)來自于CBMG(customer behavior model graph)的分析[21]。在Socks Shop這個Demo中，處理一個用戶的請求為一個任務(wù)，這個任務(wù)可以通過表3中所有容器應(yīng)用的協(xié)作來完成，其中Consumes表示容器應(yīng)用與其他容器應(yīng)用之間的消費關(guān)系，NUM表示完成這個任務(wù)所需要的某個容器應(yīng)用的個數(shù)，CPU、Memory分別代表容器應(yīng)用在霧計算節(jié)點上運行時，對CPU和內(nèi)存的最低要求。

表3 Socks Shop中的容器應(yīng)用Table 3 Container application in Socks Shop

4.2 仿真結(jié)果與分析

4.2.1 不同優(yōu)化權(quán)重下IDGSA的結(jié)果

本文首先對不同均衡度優(yōu)化權(quán)重下的IDGSA算法的性能進(jìn)行了實驗仿真，在仿真時改變均衡度優(yōu)化目標(biāo)在均衡因子TSB中所占的權(quán)重，也就是改變仿真圖3(a)、3(b)子圖的橫坐標(biāo)。當(dāng)式(8)中β(均衡度的優(yōu)化權(quán)重)為0.9的時候代表均衡度函數(shù)在最后的結(jié)果所占的權(quán)重為90%，時間函數(shù)所占的權(quán)重為10%。仿真圖3(a)左邊和右邊的縱坐標(biāo)分別代表任務(wù)計算時間和集群均衡度。對于均衡度函數(shù)優(yōu)化權(quán)重的每次取值，IDGSA算法的迭代次數(shù)為4 000。從仿真圖3(a)

圖3 不同均衡度優(yōu)化權(quán)重下的仿真結(jié)果Fig.3 Simulation results under different equalization optimization weights

中可以看到，隨著β的增加，任務(wù)的計算時間逐漸變大，而集群中均衡度逐漸變小(代表資源使用率逐漸變高)。并且從圖3(b)中可以看到，當(dāng)β為0.9時TSB取值最小，也就是能在保證任務(wù)計算時間較小的同時，保證集群均衡度也較小(集群資源使用率較高)，2個優(yōu)化目標(biāo)同時達(dá)到一個相對最優(yōu)值(均衡最優(yōu))。同時工廠也可以根據(jù)圖3(b)中的結(jié)論，動態(tài)調(diào)整均衡度優(yōu)化權(quán)重，從而實現(xiàn)自己對不同優(yōu)化目標(biāo)的倚重，或者使用相對最優(yōu)值來保證2個優(yōu)化目標(biāo)的均衡最優(yōu)。

4.2.2 IDGSA算法與傳統(tǒng)遺傳算法的比較

為證明IDGSA算法的優(yōu)勢，將IDGSA算法與傳統(tǒng)遺傳算法進(jìn)行仿真比較。仿真實驗中，種群大小為200，迭代次數(shù)為4 000，橫坐標(biāo)是迭代次數(shù)，縱坐標(biāo)分別是均衡因子TSB、任務(wù)完成時間、集群均衡度。

圖4(a)表示使用IDGSA算法和傳統(tǒng)遺傳算法求解后得到的均衡因子TSB，其中β=0.9代表集群均衡度在均衡因子中所占的權(quán)重為0.9，因為根據(jù)4.2.1中的結(jié)論，此時2個優(yōu)化目標(biāo)達(dá)到均衡最優(yōu)。從圖中可以看出在迭代到500次的時候IDGSA算法已經(jīng)取得最優(yōu)解，而傳統(tǒng)遺傳算法要迭代到1 500次才取得最優(yōu)解，并且最后的結(jié)果也是IDGSA更優(yōu)。

圖4 IDGSA算法與傳統(tǒng)遺傳算法的性能比較仿真圖Fig.4 Performance comparison simulation diagram betweenIDGSA algorithm and traditional genetic algorithm

圖4(b)和4(c)分別表示IDGSA算法和傳統(tǒng)遺傳算法求解后得到的集群均衡度和任務(wù)計算時間，同樣可以看到IDGSA算法在迭代次數(shù)為500左右的時候已經(jīng)取得比傳統(tǒng)遺傳算法更好的結(jié)果，而遺傳算法要迭代到1 500次左右才能取到最優(yōu)解。因此可以得到2個結(jié)論：第一，IDGSA算法最終取得的結(jié)果都優(yōu)于傳統(tǒng)遺傳算法。第二，IDGSA算法能夠在更少的迭代次數(shù)中達(dá)到最優(yōu)，當(dāng)2個算法的迭代次數(shù)相同的時候，IDGSA算法的結(jié)果總是優(yōu)于遺傳算法。這個結(jié)論和我們在分析IDGSA算法的時候得到結(jié)論是一致的。

4.2.3 IDGSA算法與Kubernetes默認(rèn)算法的比較

因為需要用自定義的IDGSA算法代替Kubernetes的默認(rèn)調(diào)度算法，因此將IDGSA算法的性能與Kubernetes默認(rèn)算法進(jìn)行比較。通過改變霧計算資源池中的霧計算節(jié)點的個數(shù)，比較在資源情況發(fā)生變化的時候，2個算法的性能表現(xiàn)情況。圖5(a)和5(b)中，橫坐標(biāo)代表霧計算節(jié)點的個數(shù)，可以看到隨著霧計算節(jié)點個數(shù)的增加，2個算法的任務(wù)計算時間和資源均衡度都在下降。但最后的結(jié)果表明，與Kubernetes的默認(rèn)調(diào)度算法相比，IDGSA算法數(shù)據(jù)的處理時間減少約50%，資源的使用率提高約60%。并且可以明顯看到無論霧計算資源是充足還是緊缺，IDGSA算法與Kubernetes默認(rèn)算法相比，任務(wù)處理時間都更短，資源的使用率也更高。

圖5 IDGSA與Kubernetes默認(rèn)算法的性能比較仿真圖Fig.5 Performance comparison simulation diagram betweenIDGSA algorithm and Kubernetes algorithm

5 結(jié)論

本文根據(jù)智能工廠的特點和需求，改進(jìn)了面向智能工廠的霧計算架構(gòu)，并提出智能工廠中的任務(wù)調(diào)度系統(tǒng)模型以及IDGSA算法，通過優(yōu)化任務(wù)時延和資源均衡度，提高智能工廠中的生產(chǎn)效率和降低生產(chǎn)成本。仿真實驗表明，所提出的IDSGA算法能夠在保證時延較低的同時，最大化集群資源的使用率,且能夠在迭代次數(shù)更少的情況下獲得更優(yōu)的結(jié)果。本文的研究可以為智能工廠提高計算資源利用效率、提高生產(chǎn)效率和降低生產(chǎn)成本等提供參考。