智能工廠中的霧計(jì)算資源調(diào)度*

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

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

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

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

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

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

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

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

2)算法改進(jìn)：Kubernetes的缺省調(diào)度策略是調(diào)度完一個(gè)容器應(yīng)用后才能調(diào)度下一個(gè)容器應(yīng)用，這種調(diào)度策略的缺點(diǎn)是結(jié)果局部最優(yōu)，如果直接使用Kubernetes的缺省調(diào)度器，會(huì)造成整個(gè)霧計(jì)算集群資源使用的不均衡，從而無(wú)法充分利用資源，并且智能工廠中任務(wù)的計(jì)算時(shí)延會(huì)增加。智能工廠中，任務(wù)和霧計(jì)算資源的管理分配是一個(gè)非線性問(wèn)題，因此可以使用啟發(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)算法，將個(gè)體按區(qū)間劃分，使用區(qū)間劃分的思想，對(duì)傳統(tǒng)遺傳算法的交叉變異算子和輪盤賭選擇算子進(jìn)行優(yōu)化，通過(guò)更改目標(biāo)優(yōu)化權(quán)重，解決模型中任務(wù)時(shí)延和集群均衡度協(xié)同優(yōu)化問(wèn)題，得到全局范圍內(nèi)的近似最優(yōu)解。

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

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

1.1 任務(wù)分類

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

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

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

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

1.2 任務(wù)分配

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

Kubernetes中的組件主要包括：

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

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

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

2.2.1 任務(wù)計(jì)算時(shí)間(Object1)

因?yàn)樯a(chǎn)線任務(wù)appi的一些容器應(yīng)用之間可能存在消費(fèi)關(guān)系，因此整個(gè)任務(wù)的計(jì)算時(shí)間可以使用所有容器任務(wù)完成時(shí)間中的最大值表示，如下所示

AllServicetime=max(S(ms1),

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

(1)

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

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

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)用的時(shí)間。為了便于計(jì)算，如果2個(gè)容器應(yīng)用部署在同一個(gè)霧計(jì)算節(jié)點(diǎn)上，那么transTime(msj)為0，如果在不同的霧計(jì)算節(jié)點(diǎn)上，那么transTime(msj)=0.1×S(msj)。

2.2.2 集群資源均衡度(Object2)

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

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

AllBalance=clusterBalance+singleBalance.

(4)

其中

clusterBalace=

(5)

(6)

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

(7)

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

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

本文定義了一個(gè)均衡因子作為模型的另外一個(gè)優(yōu)化目標(biāo)，這個(gè)優(yōu)化目標(biāo)綜合任務(wù)計(jì)算時(shí)間和集群均衡度2個(gè)目標(biāo)，可以讓工廠通過(guò)調(diào)整集群均衡度在TSB中的權(quán)重實(shí)現(xiàn)工廠對(duì)Object1或Object2的倚重。可以用下式表示

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

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

(8)

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

AllServicetime′,AllBalance′分別如下所示

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

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

Determine:

alloc(msi)=pml?msi∈appj

Minimizing: AllServicetime

AllBalance.

(9)

上述問(wèn)題實(shí)際屬于NP(nondeterministic polynomial)問(wèn)題，因此可以使用啟發(fā)式算法遺傳算法進(jìn)行解決，對(duì)于工廠中的任務(wù)分配，比較常用的就是遺傳算法。因此本文對(duì)傳統(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)個(gè)體。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度(fitness)大小選擇(selection)個(gè)體，并借助于自然遺傳學(xué)的遺傳算子(genetic operators)選擇合適的個(gè)體進(jìn)行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的解集的種群。但是在應(yīng)用于智能工廠時(shí)，傳統(tǒng)的遺傳算法無(wú)法處理雙目標(biāo)問(wèn)題，對(duì)于一些無(wú)效的結(jié)果沒(méi)有進(jìn)行合理的處理。并且存在迭代速度慢、結(jié)果局部最優(yōu)等情況。

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

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

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

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

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

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

1)統(tǒng)計(jì)無(wú)效個(gè)體中資源使用過(guò)度的節(jié)點(diǎn)；

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

3)生成新的子個(gè)體。

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

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

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

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

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

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

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

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

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

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

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

將整個(gè)種群定義為P，一個(gè)種群里面有N個(gè)個(gè)體，通過(guò)雙適應(yīng)度函數(shù)計(jì)算得到個(gè)體xi的適應(yīng)度值為f(xi)。在第T次迭代的時(shí)候，整個(gè)種群P中的個(gè)體的適應(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劃分為

其中：

所以個(gè)體xi被選中的概率為

(10)

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)背景

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

本文首先對(duì)不同均衡度優(yōu)化權(quán)重下的IDGSA算法的性能進(jìn)行了實(shí)驗(yàn)仿真，在仿真時(shí)改變均衡度優(yōu)化目標(biāo)在均衡因子TSB中所占的權(quán)重，也就是改變仿真圖3(a)、3(b)子圖的橫坐標(biāo)。當(dāng)式(8)中β(均衡度的優(yōu)化權(quán)重)為0.9的時(shí)候代表均衡度函數(shù)在最后的結(jié)果所占的權(quán)重為90%，時(shí)間函數(shù)所占的權(quán)重為10%。仿真圖3(a)左邊和右邊的縱坐標(biāo)分別代表任務(wù)計(jì)算時(shí)間和集群均衡度。對(duì)于均衡度函數(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ù)的計(jì)算時(shí)間逐漸變大，而集群中均衡度逐漸變小(代表資源使用率逐漸變高)。并且從圖3(b)中可以看到，當(dāng)β為0.9時(shí)TSB取值最小，也就是能在保證任務(wù)計(jì)算時(shí)間較小的同時(shí)，保證集群均衡度也較小(集群資源使用率較高)，2個(gè)優(yōu)化目標(biāo)同時(shí)達(dá)到一個(gè)相對(duì)最優(yōu)值(均衡最優(yōu))。同時(shí)工廠也可以根據(jù)圖3(b)中的結(jié)論，動(dòng)態(tài)調(diào)整均衡度優(yōu)化權(quán)重，從而實(shí)現(xiàn)自己對(duì)不同優(yōu)化目標(biāo)的倚重，或者使用相對(duì)最優(yōu)值來(lái)保證2個(gè)優(yōu)化目標(biāo)的均衡最優(yōu)。

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

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

圖4(a)表示使用IDGSA算法和傳統(tǒng)遺傳算法求解后得到的均衡因子TSB，其中β=0.9代表集群均衡度在均衡因子中所占的權(quán)重為0.9，因?yàn)楦鶕?jù)4.2.1中的結(jié)論，此時(shí)2個(gè)優(yōu)化目標(biāo)達(dá)到均衡最優(yōu)。從圖中可以看出在迭代到500次的時(shí)候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ù)計(jì)算時(shí)間，同樣可以看到IDGSA算法在迭代次數(shù)為500左右的時(shí)候已經(jīng)取得比傳統(tǒng)遺傳算法更好的結(jié)果，而遺傳算法要迭代到1 500次左右才能取到最優(yōu)解。因此可以得到2個(gè)結(jié)論：第一，IDGSA算法最終取得的結(jié)果都優(yōu)于傳統(tǒng)遺傳算法。第二，IDGSA算法能夠在更少的迭代次數(shù)中達(dá)到最優(yōu)，當(dāng)2個(gè)算法的迭代次數(shù)相同的時(shí)候，IDGSA算法的結(jié)果總是優(yōu)于遺傳算法。這個(gè)結(jié)論和我們?cè)诜治鯥DGSA算法的時(shí)候得到結(jié)論是一致的。

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

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

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

5 結(jié)論

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