物聯(lián)網(wǎng)低時(shí)延云霧混合網(wǎng)絡(luò)負(fù)載均衡策略

吳海超，王新民

(1.長(zhǎng)春財(cái)經(jīng)學(xué)院 信息工程學(xué)院，吉林 長(zhǎng)春 130122；2.長(zhǎng)春工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，吉林 長(zhǎng)春 130122)

0 引 言

隨著互聯(lián)網(wǎng)接入設(shè)備的高速增長(zhǎng)和物聯(lián)網(wǎng)(Internet of things，IoT)的出現(xiàn)，未來(lái)霧計(jì)算被越來(lái)越多行業(yè)不斷引入。相較于其它算法，霧計(jì)算的最大優(yōu)勢(shì)在于它能夠不受中心化的困擾，可以充分利用本地位置感知分發(fā)的技術(shù)，并且該算法還可以應(yīng)用于不同類別的終端設(shè)備中[1-4]。正是因?yàn)檫@些優(yōu)點(diǎn)，在可以預(yù)見(jiàn)的車聯(lián)網(wǎng)、物聯(lián)網(wǎng)、智能電網(wǎng)等等各種場(chǎng)景中都將會(huì)發(fā)揮重要的作用，甚至可以超過(guò)云計(jì)算的應(yīng)用。霧計(jì)算與云計(jì)算區(qū)別的主要因素是它與終端用戶的密切關(guān)系[5]。隨著計(jì)算機(jī)技術(shù)迭代更新速度加快以及人們對(duì)移動(dòng)終端的依賴程度越來(lái)越高，去中心化成為了必然趨勢(shì)，所以霧計(jì)算的重要性將會(huì)越來(lái)越突出，盡管在短時(shí)間內(nèi)它還無(wú)法取代云計(jì)算，但是在一些重要場(chǎng)景中霧計(jì)算以及發(fā)揮了一定的作用[6-8]。

為了減少IoT中負(fù)載均衡時(shí)所帶來(lái)的服務(wù)時(shí)延，提出了一種面向低時(shí)延的云霧混合網(wǎng)絡(luò)及其負(fù)載均衡策略，對(duì)邊緣設(shè)備產(chǎn)生的物聯(lián)網(wǎng)請(qǐng)求進(jìn)行調(diào)度，將其分配給霧和云上的足夠資源。所提策略的創(chuàng)新點(diǎn)總結(jié)如下：

(1)為了彌補(bǔ)云計(jì)算高時(shí)延的不足，所提策略構(gòu)建了云霧混合網(wǎng)絡(luò)，將物聯(lián)網(wǎng)設(shè)備的服務(wù)請(qǐng)求合理分配到云和霧計(jì)算中，以充分利用霧計(jì)算低時(shí)延與云計(jì)算處理能力強(qiáng)的優(yōu)勢(shì)，滿足系統(tǒng)低時(shí)延、數(shù)據(jù)處理速度快的需求。

(2)針對(duì)現(xiàn)有IoT負(fù)載均衡方案時(shí)延較大的問(wèn)題，所提方案將物聯(lián)網(wǎng)服務(wù)請(qǐng)求的均衡建模成一個(gè)優(yōu)化問(wèn)題，并利用改進(jìn)的蝙蝠算法求解此問(wèn)題，合理分配云霧計(jì)算資源，實(shí)現(xiàn)服務(wù)總時(shí)延最小化。

1 相關(guān)研究

霧計(jì)算的概念最早出現(xiàn)在2012年，提出該概念的機(jī)構(gòu)是思科。該技術(shù)的出現(xiàn)將云計(jì)算擴(kuò)展到網(wǎng)絡(luò)邊緣[9]。在云計(jì)算技術(shù)的實(shí)施過(guò)程中，可以利用已經(jīng)搭建的網(wǎng)絡(luò)架構(gòu)，通過(guò)相關(guān)的軟件和硬件技術(shù)，將數(shù)據(jù)中心和最終的用戶相互連接起來(lái)，形成霧計(jì)算層。該層面上的相關(guān)設(shè)備可以完成相關(guān)的計(jì)算功能，從而有效節(jié)省了大量的計(jì)算時(shí)間，降低了網(wǎng)絡(luò)時(shí)延，可以滿足更多用戶的需求。除此以外，通過(guò)使用霧計(jì)算還可以實(shí)現(xiàn)對(duì)于位置的感知功能[10,11]。霧網(wǎng)絡(luò)中所用到的各類設(shè)備大部分都是與用戶終端比較接近的設(shè)備，包括交換機(jī)、路由器等。文獻(xiàn)[12]提出了一個(gè)醫(yī)療保健參考模型，該模型由4個(gè)層級(jí)組成，分別為集成了用于收集數(shù)據(jù)的不同物理傳感器的傳感層、提供網(wǎng)絡(luò)支持和在有線或無(wú)線網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)木W(wǎng)絡(luò)層、創(chuàng)建和管理各種類型的服務(wù)來(lái)滿足用戶需求的服務(wù)層、同時(shí)還包括可以實(shí)現(xiàn)將用戶與應(yīng)用該軟件相互連接功能的接口層。

霧計(jì)算拓寬了云計(jì)算技術(shù)的功能，兩種不同的計(jì)算方法在使用過(guò)程中可以相互影響，通過(guò)兩者的配合確保了用戶服務(wù)質(zhì)量的提升[13]。通過(guò)利用當(dāng)前快速發(fā)展的現(xiàn)代化網(wǎng)絡(luò)技術(shù)，加強(qiáng)對(duì)霧計(jì)算的研究，將會(huì)有效提升物聯(lián)網(wǎng)技術(shù)的發(fā)展質(zhì)量。霧層負(fù)責(zé)處理對(duì)物聯(lián)網(wǎng)設(shè)備的本地緩沖和不同連接要求，而云層負(fù)責(zé)處理與霧層的連接、用戶或設(shè)備數(shù)據(jù)的管理以及例如儀表板、規(guī)則引擎，大數(shù)據(jù)分析和集成框架的應(yīng)用服務(wù)[14]。文獻(xiàn)[15]中提出了一個(gè)工作流服務(wù)請(qǐng)求和動(dòng)態(tài)最小響應(yīng)時(shí)間，該響應(yīng)時(shí)間分析了在邊緣計(jì)算中映射請(qǐng)求的同一層級(jí)的算法。實(shí)驗(yàn)結(jié)果表明，該算法在響應(yīng)時(shí)間和阻塞率上都有很好的性能。

霧計(jì)算在實(shí)施過(guò)程中所用到的各種不同的組成設(shè)備相互之間比較分散，同時(shí)計(jì)算速度有限，僅僅依靠單一的設(shè)備在較短的時(shí)間內(nèi)是無(wú)法完成繁重的數(shù)據(jù)處理工作的，應(yīng)該使用分布式的計(jì)算方法，對(duì)計(jì)算量進(jìn)行劃分，然后由不同的設(shè)備進(jìn)行計(jì)算，完成計(jì)算后統(tǒng)一反饋結(jié)果，從而計(jì)算速度[16]。所以，重點(diǎn)針對(duì)霧計(jì)算過(guò)程中每個(gè)設(shè)備的計(jì)算效率、花費(fèi)的成本等，從而以此為依據(jù)分配工作任務(wù)，實(shí)現(xiàn)提升計(jì)算速度，降低時(shí)延的目的，應(yīng)該加強(qiáng)對(duì)霧網(wǎng)絡(luò)分布式負(fù)載均衡算法的研究。文獻(xiàn)[17]闡明了一個(gè)關(guān)于云計(jì)算和邊緣計(jì)算中的網(wǎng)絡(luò)流量問(wèn)題的核心挑戰(zhàn)，并提出了兩個(gè)優(yōu)化模型，使得每個(gè)節(jié)點(diǎn)的平均分組時(shí)間與平均到達(dá)時(shí)間的最大百分比達(dá)到了最小化，而第二個(gè)模型處理了最大化本地網(wǎng)絡(luò)鏈路利用率的問(wèn)題。

考慮到環(huán)境的性質(zhì)，安全性是霧計(jì)算中的一個(gè)主要挑戰(zhàn)。文獻(xiàn)[18]提出了一個(gè)網(wǎng)絡(luò)安全框架，可識(shí)別出在分布式霧計(jì)算環(huán)境中的惡意邊緣設(shè)備。該框架采用兩階段馬爾可夫模型對(duì)惡意或合法邊緣設(shè)備進(jìn)行早期預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明了所提框架的有效性。文獻(xiàn)[19]深入探討了在制造集群場(chǎng)景中如何能夠利用霧計(jì)算科學(xué)確定能耗值。首先，該文獻(xiàn)構(gòu)建了相應(yīng)的數(shù)學(xué)模型，同時(shí)提出了相應(yīng)的優(yōu)化函數(shù)，然后，使用改進(jìn)的粒子群優(yōu)化算法獲得最優(yōu)解，并將完成任務(wù)的優(yōu)先級(jí)構(gòu)建到制造集群。最后，引入了多智能體系統(tǒng)來(lái)實(shí)現(xiàn)制造集群的分布式調(diào)度。通過(guò)糖果包裝生產(chǎn)線的實(shí)驗(yàn)對(duì)所提出的ELBS方法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明所提出的方法為混合作業(yè)機(jī)器人提供了最佳的調(diào)度和負(fù)載平衡。

2 系統(tǒng)模型及問(wèn)題建模

2.1 云霧混合網(wǎng)絡(luò)

提出的云霧混合網(wǎng)絡(luò)集成了霧計(jì)算與云計(jì)算，其為一個(gè)3層體系的架構(gòu)，如圖1所示。其中：邊緣層由終端節(jié)點(diǎn)、嵌入式系統(tǒng)、傳感器和執(zhí)行器組成，計(jì)算、能量和帶寬都非常有限；霧層包括路由器、網(wǎng)關(guān)、交換機(jī)等中間網(wǎng)絡(luò)設(shè)備，均具備計(jì)算和存儲(chǔ)功能，且接入點(diǎn)采用4G、5G、LTE、Wi-Fi等不同的協(xié)議；云層由在存儲(chǔ)和處理能力方面具有非常豐富的虛擬化能力的云數(shù)據(jù)中心組成。

圖1 云霧混合網(wǎng)絡(luò)的架構(gòu)

這些請(qǐng)求來(lái)源異構(gòu)資源的集合ζ={si|i=1,…,m}的處理能力，一個(gè)資源代表著一個(gè)已完成請(qǐng)求處理的物理設(shè)備。其中資源si可能位于靠近霧邊緣的位置，也可能位于遠(yuǎn)離云邊緣的位置。每個(gè)請(qǐng)求φj均會(huì)存在的時(shí)延為：傳輸時(shí)延，即將請(qǐng)求數(shù)據(jù)包的比特?cái)?shù)據(jù)推送到連接鏈路上所需的時(shí)間；排隊(duì)時(shí)延，即請(qǐng)求數(shù)據(jù)包通過(guò)網(wǎng)絡(luò)路由器和交換機(jī)所花費(fèi)的時(shí)間；傳播時(shí)延，即信號(hào)在到達(dá)目的地之前通過(guò)傳輸媒體進(jìn)行傳播的時(shí)間。由于傳播時(shí)延與其它時(shí)延相比是微不足道的，所以傳播時(shí)延忽略不計(jì)。

傳輸時(shí)延是一個(gè)關(guān)于數(shù)據(jù)包長(zhǎng)度和鏈路傳輸速率的函數(shù)，由于其對(duì)于固定的包大小和傳輸速率具有確定的值，因此可以預(yù)先評(píng)估。相反，排隊(duì)時(shí)間本質(zhì)上是隨機(jī)的，因此總時(shí)延可以看成一個(gè)隨機(jī)變量，其平均值為

(1)

物聯(lián)網(wǎng)數(shù)據(jù)處理包括數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)聚合以及分析、特征提取、圖像、視頻處理等，數(shù)據(jù)處理的時(shí)間由請(qǐng)求的數(shù)據(jù)大小和處理請(qǐng)求的資源的處理能力所決定，資源si處理每個(gè)請(qǐng)求φj所需的時(shí)間Tij，其中資源能力是根據(jù)處理速度Vi確定的。此外，如果資源正忙于為其它請(qǐng)求提供服務(wù)，則請(qǐng)求可能會(huì)遇到額外的時(shí)延。

負(fù)載均衡策略的目標(biāo)在于特定時(shí)間將Ψ中的請(qǐng)求分配給ζ中的有能力的資源，以達(dá)到時(shí)延最小化的目的。請(qǐng)求φj的時(shí)延為從請(qǐng)求在霧邊緣啟動(dòng)到完全處理并將結(jié)果返回給請(qǐng)求者的往返時(shí)間(round-trip time，RTT)。負(fù)載均衡模型中假設(shè)：①作為計(jì)算處理器的資源在霧端和云端時(shí)一次只能處理一個(gè)請(qǐng)求；②請(qǐng)求可以隨時(shí)啟動(dòng)；③每個(gè)請(qǐng)求數(shù)據(jù)量大小由請(qǐng)求擁有的數(shù)據(jù)包數(shù)量決定，每個(gè)請(qǐng)求可以具有多個(gè)分組，且其中每個(gè)數(shù)據(jù)分組的大小是相同的；④如果請(qǐng)求開(kāi)始處理，則必須在不中斷的情況下完成。

2.2 目標(biāo)函數(shù)與約束條件

一個(gè)集合中有n個(gè)請(qǐng)求，Ψ={φj|j=1,…,n}由邊緣層物聯(lián)網(wǎng)設(shè)備生成，并且需要由一組m資源ζ={si|i=1,…,m}進(jìn)行處理，資源分布在霧和云之間[20]。負(fù)載均衡模型的目標(biāo)是，在考慮各種約束條件下，完成總時(shí)延的最小化，即使用m個(gè)可用資源為n個(gè)請(qǐng)求提供服務(wù)時(shí)的往返時(shí)間總和。目標(biāo)函數(shù)表示如下

(2)

式中：Xij為決策變量，用于指示請(qǐng)求φj是否被分配給資源si。給定請(qǐng)求的單個(gè)時(shí)延為

(3)

從數(shù)學(xué)的角度來(lái)看，時(shí)延是啟動(dòng)時(shí)間和服務(wù)結(jié)束時(shí)間之間的差，其中，服務(wù)時(shí)間包括了開(kāi)始時(shí)間、處理時(shí)間、傳輸和排隊(duì)時(shí)間，計(jì)算如下

Tij=TSij+tij+QTij-T0j

(4)

式中：TSij是資源si處理請(qǐng)求φj的開(kāi)始時(shí)間，tij是請(qǐng)求的處理時(shí)間，QTij是請(qǐng)求φj到達(dá)資源si之前的傳輸和排隊(duì)時(shí)間，T0j是請(qǐng)求rj的啟動(dòng)時(shí)間。

每個(gè)請(qǐng)求的處理時(shí)間等于請(qǐng)求數(shù)據(jù)大小除以資源處理能力，假設(shè)Qi表示請(qǐng)求的數(shù)據(jù)量大小，fi表示資源的處理能力，則處理時(shí)間通過(guò)tij=Qi/fi得到。請(qǐng)求φj從邊緣層到位于霧或云中的資源si的傳輸和排隊(duì)時(shí)間為

(5)

一個(gè)請(qǐng)求的時(shí)延是其各個(gè)數(shù)據(jù)包時(shí)延的總和，該數(shù)據(jù)包的時(shí)延是在特定平均值周圍分布的單個(gè)時(shí)延。

設(shè)定目標(biāo)函數(shù)是為了在滿足約束集合的條件下實(shí)現(xiàn)其最小化。約束條件包括：

(1)每個(gè)請(qǐng)求φj只能由一個(gè)資源來(lái)完成服務(wù)

(6)

(2)請(qǐng)求φj在被傳輸?shù)劫Y源之前不能開(kāi)始處理。這個(gè)時(shí)間量包括啟動(dòng)時(shí)間加上到霧或云計(jì)算所在位置的傳輸和排隊(duì)時(shí)間。即為了處理請(qǐng)求，需要先創(chuàng)建該請(qǐng)求并將其傳輸?shù)劫Y源，表示如下

TSij≥T0j+QTij,?rj∈Ψ,?si∈ζ

(7)

(3)每個(gè)資源si一次只能處理一個(gè)請(qǐng)求。如果有兩個(gè)請(qǐng)求同時(shí)到達(dá)資源進(jìn)行處理，則其中一個(gè)請(qǐng)求必須在另一個(gè)請(qǐng)求完成后才能開(kāi)始進(jìn)行處理。這兩個(gè)請(qǐng)求的執(zhí)行順序由參數(shù)βijk定義，如果βijk=1，則資源si執(zhí)行請(qǐng)求φj，然后執(zhí)行請(qǐng)求φk，反之亦然。對(duì)于?si∈ζ, ?φj,φk∈Ψ,φj≠φk，決策變量βijk的定義如下

ifXij+Xik=2 thenβijk+βikj=1TSik≥βijk(TSij+tij)

(8)

(4)請(qǐng)求之間的優(yōu)先依賴性。即使請(qǐng)求被分配了到不同的處理器中，如果它的前例沒(méi)有完成處理，那么此請(qǐng)求不能開(kāi)始進(jìn)行處理。即

(9)

(5)請(qǐng)求必須在特定截止期限之前送達(dá)，即

Tij≤Dj

(10)

式中：Dj為請(qǐng)求φj的截止期限。

3 基于改進(jìn)蝙蝠算法的時(shí)延優(yōu)化負(fù)載均衡策略

3.1 蝙蝠算法

由于蝙蝠算法(bat algorithm，BA)在全局搜索場(chǎng)景中效果十分顯著，并且收斂效率也相對(duì)較高，程序編譯并不復(fù)雜。所以在云霧混合網(wǎng)絡(luò)情況下的負(fù)載均衡一般通過(guò)BA算法對(duì)其進(jìn)行優(yōu)化。這種算法是近年來(lái)剛剛興起的一種算法，其計(jì)算出的任何一個(gè)優(yōu)化解都將會(huì)被視作一個(gè)蝙蝠[21]。對(duì)于任何一個(gè)蝙蝠而言都會(huì)相對(duì)應(yīng)有一個(gè)適應(yīng)度，BA算法在運(yùn)用過(guò)程中將會(huì)通過(guò)調(diào)整頻率、脈沖發(fā)射率以及不同的響度對(duì)最優(yōu)蝙蝠開(kāi)展全域內(nèi)的搜索。

對(duì)于優(yōu)化問(wèn)題而言，BA算法雖然具有明顯的優(yōu)勢(shì)，然而其缺點(diǎn)也十分明顯，一是經(jīng)常得到局部最優(yōu)的結(jié)果，二是收斂速度相對(duì)較慢[22]。為盡可能克服這些缺點(diǎn)，本文中將會(huì)通過(guò)負(fù)載均衡的方法對(duì)蝙蝠種群數(shù)據(jù)前期做初始化處理，這樣能夠有效提升最終解的質(zhì)量，然后還要充分利用Powell搜索，進(jìn)而能夠有效提升其收斂效率。

具體來(lái)講，基本蝙蝠算法主要分成6步進(jìn)行：

步驟1首先對(duì)模型中的參數(shù)開(kāi)展初始化操作：一般要設(shè)定一個(gè)最大迭代次數(shù)值，這里將其記作Gmax，然后要確定合適的搜索精度這里記作ε，還要確定脈沖頻率的最大值以及其最小值這里用hmax,hmin表示，蝙蝠的初始化位置通過(guò)向量Xi(i=1,2,3,…N)表示，那么針對(duì)當(dāng)前蝙蝠群中進(jìn)行搜索后就能夠得到的一個(gè)最優(yōu)蝙蝠位置，用X*表示。

步驟2在種群迭代中根據(jù)以下公式更新蝙蝠的速度和位置

(11)

步驟3生成隨機(jī)數(shù)1，如果1>ri(ri為第i只蝙蝠的脈沖頻度)，則更新當(dāng)前最優(yōu)蝙蝠位置

Xnew=Xold+εAt

(12)

步驟4生成隨機(jī)數(shù)2，如果2

(13)

步驟5通過(guò)以上幾步能夠得出蝙蝠群體的適應(yīng)度值，然后利用該值就能夠做出科學(xué)的評(píng)估，以此為基礎(chǔ)就能夠進(jìn)一步確定其最優(yōu)位置以及具體的適應(yīng)度值。完成此過(guò)程后，需要再次做迭代操作，重新回到步驟2開(kāi)始，直至能夠符合開(kāi)始所設(shè)置的精度要求或者能夠符合迭代次數(shù)超過(guò)設(shè)定的最大值的條件。

步驟6結(jié)束算法，最終能夠得到最優(yōu)函數(shù)值以及蝙蝠的最優(yōu)位置。

3.2 基于Powell局部搜索的改進(jìn)BA算法

Powell算法無(wú)須對(duì)目標(biāo)函數(shù)做求導(dǎo)處理，所以這就決定了當(dāng)其導(dǎo)數(shù)不連續(xù)情況下同樣能夠引用該方法，另外該算法也無(wú)須求出相應(yīng)的梯度，其搜索精度相對(duì)較高，基于以上這些優(yōu)點(diǎn)該算法得到了廣泛應(yīng)用。然而任何一種算法都有其固有缺陷，Powell算法的應(yīng)用對(duì)初始點(diǎn)有著嚴(yán)格的要求，所以一般在引用該方法時(shí)要通過(guò)負(fù)載均衡對(duì)其做初始化處理。其具體的計(jì)算過(guò)程如圖2所示。

圖2 Powell算法的流程

通過(guò)負(fù)載均衡進(jìn)一步求出的蝙蝠種群的初始化結(jié)果，假設(shè)n個(gè)初始蝙蝠種群的無(wú)關(guān)搜索方向記作d(i)(i=0,1,2,…,n-1)，令c(0)=c(j)，從c(0)開(kāi)始依次沿搜索方向進(jìn)行一維搜索，獲得c(i)(i=1,2,…,n)。設(shè)d(n)=c(n)-c(0)，如果|d(n)|≤δ，在得出c(n)后計(jì)算也就會(huì)相應(yīng)終止；不然，從c(n)開(kāi)始將會(huì)沿d(n)方向開(kāi)展線性搜索直至最終求出c(n+1)。

搜索方向的確定一般利用如下公式進(jìn)行計(jì)算：f(c(0))-2f(c(0))+f(2c(n)-c(0))<2[f(c(m))-f(c(m+1))]，如果成立，則說(shuō)明d(0),d(1),…,d(n-1)線性相關(guān)，需要調(diào)整搜索方向；否則，說(shuō)明d(0),d(1),…,d(n-1)線性無(wú)關(guān)，不調(diào)整搜索方向。

3.3 基于改進(jìn)BA算法的云霧網(wǎng)絡(luò)負(fù)載均衡策略

云霧網(wǎng)絡(luò)數(shù)據(jù)中心有m個(gè)霧計(jì)算設(shè)備，需要處理α個(gè)邊緣終端所產(chǎn)生的調(diào)度響應(yīng)。每個(gè)霧設(shè)備中具有的資源向量可以被劃分為兩個(gè)類別，包括空閑資源向量、被使用的資源向量。負(fù)載均衡代表了讓全部的邊緣終端都可以與相鄰的霧設(shè)備相連，經(jīng)過(guò)不斷演化計(jì)算，每個(gè)終端最終都可以與霧設(shè)備保持最小的距離[24]。兩者之間的距離可以通過(guò)資源相關(guān)系數(shù)進(jìn)行表示，如果該系數(shù)較小，則代表將要用到的資源和霧設(shè)備兩者可以產(chǎn)生非常多的互補(bǔ)，如果空間不受限制，那么這個(gè)時(shí)候?qū)?huì)被分配至其它相關(guān)性并不顯著的一些設(shè)備之中。假如利用皮爾遜相關(guān)系數(shù)?vp對(duì)于虛擬資源以及物理節(jié)點(diǎn)兩者之間的相關(guān)性進(jìn)行計(jì)算，相關(guān)性的大小保持在[-1,1]。則邊緣終端與霧設(shè)備的距離為

(14)

邊緣終端與霧設(shè)備的距離取值范圍為[0,1]。如果將邊緣終端與不活躍霧設(shè)備之間間隔設(shè)置為最大值，該值的大小為1，那么這一狀態(tài)代表了僅在邊緣終端不能放置的情況下，才可以分配至新霧設(shè)備中[25]?；诟倪M(jìn)BA算法的云霧網(wǎng)絡(luò)負(fù)載均衡策略的算法偽代碼如算法1所示。

算法1：基于改進(jìn)BA的云霧網(wǎng)絡(luò)負(fù)載均衡策略

初始化：首先要確定合理的基本參數(shù)；假設(shè)在實(shí)際運(yùn)行時(shí)受到了n個(gè)服務(wù)請(qǐng)求，這些請(qǐng)求的數(shù)據(jù)集用Ψ表示，這里再假設(shè)霧設(shè)備數(shù)是m，那么通過(guò)負(fù)載均衡再做出初始化操作，并且要把聚類中心設(shè)定成蝙蝠的位置編碼，這樣將會(huì)最終得到N個(gè)數(shù)量的初始蝙蝠。

Begin

(1)將蝙蝠種群的速度、脈沖頻率、脈沖響度以及脈沖發(fā)射速率做出初始化處理。

(2)利用公式計(jì)算出所有的蝙蝠所對(duì)應(yīng)的適應(yīng)度值，然后獲取一個(gè)最優(yōu)解，再通過(guò)速度以及位置公式進(jìn)一步對(duì)剩余蝙蝠所對(duì)應(yīng)的信息做出具體的調(diào)整。

If1>ri，then

對(duì)目前群體中的最佳蝙蝠位置通過(guò)隨機(jī)擾動(dòng)的方式獲取替換當(dāng)前蝙蝠的位置，具體公式如下:Xnew=Xold+εAt。

If2

得到一個(gè)新解，通過(guò)Ai以及ri公式對(duì)音強(qiáng)進(jìn)行降低處理，在此過(guò)程中還要進(jìn)一步增大脈沖發(fā)生率；

Otherwise, 不調(diào)整Ai以及ri，再次回到步驟(5)。

(5)對(duì)蝙蝠群體做出科學(xué)的評(píng)估，同時(shí)對(duì)最優(yōu)位置通過(guò)Powell算法開(kāi)展局部搜索。

(6)判斷算法是否能夠完全符合起初設(shè)定的終止條件：如果符合(|d(n)|≤δ)或超過(guò)了設(shè)定的最大迭代次數(shù)，就進(jìn)行步驟(7)；否則，設(shè)i=i+1，再次回到步驟(2)。

(7)輸出：最優(yōu)的蝙蝠位置以及其所對(duì)應(yīng)的負(fù)載均衡方案。

End

4 改進(jìn)BA算法實(shí)驗(yàn)

在改進(jìn)BA算法應(yīng)用于實(shí)時(shí)仿真環(huán)境之前，需要針對(duì)算法中的不同參數(shù)在方案實(shí)現(xiàn)中的作用進(jìn)行探究。改進(jìn)BA算法實(shí)現(xiàn)時(shí)最重要的兩個(gè)參數(shù)分別是種群規(guī)模N和最大迭代次數(shù)Gmax，直接影響著負(fù)載均衡方案的質(zhì)量和運(yùn)行時(shí)間。

4.1 種群規(guī)模

考慮到改進(jìn)BA算法的整體時(shí)延Tij和傳輸時(shí)間QTij會(huì)決定所得最優(yōu)解的質(zhì)量，通過(guò)實(shí)驗(yàn)確定種群規(guī)模。實(shí)驗(yàn)中考慮了不同規(guī)模的調(diào)度問(wèn)題κ，其中每個(gè)值是包含n請(qǐng)求和m資源的一個(gè)元組(n/m)。針對(duì)κ中的每個(gè)值，仿真進(jìn)行5次不同的實(shí)驗(yàn)。實(shí)驗(yàn)中計(jì)算得到整體時(shí)延和傳輸時(shí)間的平均值，并且最大迭代次數(shù)為50。整體時(shí)延以及運(yùn)行時(shí)間與種群規(guī)模的關(guān)系如圖3所示。

從圖3(a)中可知，隨著種群規(guī)模的增加，改進(jìn)BA算法的整體時(shí)延逐漸減小，但在種群數(shù)量達(dá)到40之后，整體時(shí)延減小量變得微不足道。而從圖3(b)可知，傳輸時(shí)間隨著種群規(guī)模的增加而繼續(xù)急劇增加。因此，綜合兩者，改進(jìn)BA算法將種群數(shù)量設(shè)為60，如此系統(tǒng)僅需花費(fèi)中等運(yùn)行時(shí)間而能獲得高質(zhì)量的負(fù)載均衡方案。

4.2 迭代最大次數(shù)

為了確定最大迭代次數(shù)的最佳值，在進(jìn)行實(shí)驗(yàn)時(shí)同時(shí)考慮了獲得解的質(zhì)量(如確定的整體時(shí)延)和改進(jìn)BA算法的運(yùn)行時(shí)間。實(shí)驗(yàn)中相應(yīng)的平均整體時(shí)延和運(yùn)行時(shí)間的平均值與最大迭代次數(shù)的關(guān)系如圖4所示。

圖3 整體時(shí)延、運(yùn)行時(shí)間與種群規(guī)模的關(guān)系

圖4 平均整體時(shí)延、運(yùn)行時(shí)間與最大迭代次數(shù)的關(guān)系

從圖4中可知，最大迭代次數(shù)的增加會(huì)將解的質(zhì)量(時(shí)延)提高到某一點(diǎn)。但是，最大迭代次數(shù)的增加通常會(huì)急劇增加算法的運(yùn)行時(shí)間。因此，所提算法中最大迭代次數(shù)設(shè)為20，如此系統(tǒng)僅需花費(fèi)中等運(yùn)行時(shí)間而能獲得高質(zhì)量的負(fù)載均衡方案。

5 仿真實(shí)驗(yàn)與結(jié)果分析

基于離散事件仿真器構(gòu)建所提策略的仿真模型。在邊緣層請(qǐng)求遵循一種特定的分布，并根據(jù)到達(dá)時(shí)間的生成，每個(gè)生成的請(qǐng)求都與其在模型中的定義屬性相關(guān)聯(lián)。請(qǐng)求從邊緣傳輸?shù)剿岣倪M(jìn)BA算法的調(diào)度器，該調(diào)度器會(huì)決定在霧資源或云資源上分配請(qǐng)求的時(shí)間和位置。所提策略集成改進(jìn)BA算法與離散事件模擬器，改進(jìn)BA算法的調(diào)度器會(huì)在特定的定義時(shí)間范圍內(nèi)接收請(qǐng)求。最初，模擬器中的所有資源都是可利用的，但隨著時(shí)間的推移，請(qǐng)求被啟動(dòng)，也將會(huì)被分配給資源。因此改進(jìn)BA算法會(huì)生成一個(gè)負(fù)載均衡方案，并且當(dāng)新的請(qǐng)求到達(dá)時(shí)，其會(huì)為了將來(lái)的決策而將已生成的方案內(nèi)容保留。實(shí)驗(yàn)中假設(shè)所有的請(qǐng)求數(shù)據(jù)包的實(shí)際時(shí)延可以與平均值相同，也可以基于所使用的分布而有不同的值，且傳輸和排隊(duì)時(shí)延分布設(shè)為具有特定均值和方差的高斯分布。

為了論證所提策略的性能，將其與文獻(xiàn)[12]、文獻(xiàn)[17]、文獻(xiàn)[19]中的策略進(jìn)行對(duì)比分析，其中選取總體平均服務(wù)時(shí)延和錯(cuò)過(guò)截止期限的請(qǐng)求數(shù)作為評(píng)價(jià)策略性能的指標(biāo)。并且實(shí)驗(yàn)基于兩種調(diào)度模式展開(kāi)，即靜態(tài)調(diào)度模式和動(dòng)態(tài)調(diào)度模式。在靜態(tài)模式下，請(qǐng)求之間的到達(dá)間隔時(shí)間被消除，并且假設(shè)所有請(qǐng)求都在時(shí)間0時(shí)批量一次生成。在動(dòng)態(tài)調(diào)度中，請(qǐng)求是服從泊松分布，并根據(jù)到達(dá)率生成。

5.1 靜態(tài)調(diào)度

實(shí)驗(yàn)中使用了16臺(tái)服務(wù)器，平均處理速度為每秒處理500個(gè)數(shù)據(jù)包，且處理速度廣泛分布在每秒處理50到1000包之間。服務(wù)器的平均時(shí)延設(shè)置為每個(gè)數(shù)據(jù)包平均5 ms，且服務(wù)器時(shí)延一般分布在從1 ms～9.7 ms。實(shí)驗(yàn)總共處理了100個(gè)請(qǐng)求，優(yōu)先級(jí)設(shè)為在1到16上均勻分布。截止期限要求的平均值設(shè)為400 s，波動(dòng)范圍是50 s。不同負(fù)載的平均整體時(shí)延、錯(cuò)過(guò)截止期限請(qǐng)求數(shù)與平均請(qǐng)求數(shù)據(jù)量關(guān)系的對(duì)比如圖5所示。

圖5 靜態(tài)調(diào)度下平均整體時(shí)延、錯(cuò)過(guò)截止 期限的請(qǐng)求數(shù)與平均請(qǐng)求數(shù)據(jù)量的關(guān)系

從圖5中可以看出，與其它策略相比，所提策略在總體時(shí)延方面具有更好的表現(xiàn)。文獻(xiàn)[17]和文獻(xiàn)[19]這兩種策略的結(jié)果非常接近，因?yàn)樗鼈兌际腔趦?yōu)先級(jí)來(lái)實(shí)現(xiàn)資源內(nèi)的請(qǐng)求分配，但調(diào)度是不同的。文獻(xiàn)[12]需要最長(zhǎng)的時(shí)延時(shí)間，因此以循環(huán)調(diào)度的方式進(jìn)行請(qǐng)求分配時(shí)是不會(huì)考慮請(qǐng)求優(yōu)先級(jí)的。

此外，與其它策略相比，所提策略可以在更長(zhǎng)的時(shí)間內(nèi)保持無(wú)請(qǐng)求錯(cuò)過(guò)其截止期限的記錄。但在平均6500個(gè)數(shù)據(jù)包的情況下，所提策略無(wú)法保證滿足所有請(qǐng)求滿足它們的截止期限，因?yàn)檎?qǐng)求的服務(wù)時(shí)延增加了，截止期限也變得十分關(guān)鍵。即使所提策略是可行的，但也不能保證滿足所有的要求。如圖5(b)所示，這一結(jié)論可以通過(guò)平均請(qǐng)求數(shù)據(jù)量大小位于6000到8000的之間時(shí)呈現(xiàn)的結(jié)果中得到驗(yàn)證。當(dāng)數(shù)據(jù)量達(dá)到8000個(gè)包時(shí)，問(wèn)題變得不可行，因此所提策略也無(wú)法找到可行的調(diào)度方案。

5.2 動(dòng)態(tài)調(diào)度

實(shí)驗(yàn)的環(huán)境配置包括了16個(gè)服務(wù)器和500個(gè)請(qǐng)求，以評(píng)估請(qǐng)求隨時(shí)間到達(dá)的時(shí)延。請(qǐng)求是服從泊松分布，平均的到達(dá)時(shí)間為1 s，優(yōu)先級(jí)設(shè)為在1到16上均勻分布。截止期限要求的平均值設(shè)為200 s，波動(dòng)范圍是50 s，資源調(diào)度的時(shí)間范圍是10 s，平均請(qǐng)求數(shù)據(jù)大小通常分布在1000到10 000個(gè)數(shù)據(jù)包之間。負(fù)載的平均整體時(shí)延、錯(cuò)過(guò)截止期限請(qǐng)求數(shù)與平均請(qǐng)求數(shù)據(jù)量之間的對(duì)比關(guān)系如圖6所示。

圖6 動(dòng)態(tài)調(diào)度下平均整體時(shí)延、錯(cuò)過(guò)截止 期限的請(qǐng)求數(shù)與平均請(qǐng)求數(shù)據(jù)量的關(guān)系

從圖6中可以看出，與其它策略相比，所提策略遺傳算法在總體時(shí)延方面具有更好的表現(xiàn)。文獻(xiàn)[12]和文獻(xiàn)[17]這兩種策略的結(jié)果非常接近，但隨著平均請(qǐng)求數(shù)據(jù)量的增加，這兩種策略之間差異會(huì)增大。

此外，如圖6(b)所示，如果平均請(qǐng)求數(shù)據(jù)量小于5000個(gè)數(shù)據(jù)包，所提策略可以實(shí)現(xiàn)了0個(gè)請(qǐng)求錯(cuò)過(guò)其截止期限，在平均6000個(gè)數(shù)據(jù)包的情況下，其依然可以實(shí)現(xiàn)了0個(gè)請(qǐng)求丟失，而文獻(xiàn)[12]和文獻(xiàn)[17]中策略丟失了近20%的請(qǐng)求，文獻(xiàn)[19]中策略丟失了35%的請(qǐng)求。在平均請(qǐng)求數(shù)據(jù)量為6000個(gè)數(shù)據(jù)包這一節(jié)點(diǎn)之后，大多數(shù)請(qǐng)求的截止期限要求變得非常關(guān)鍵，其中一些請(qǐng)求甚至一件不可完成。因此，當(dāng)數(shù)據(jù)大小增加到6000個(gè)數(shù)據(jù)包以上時(shí)，所提策略也開(kāi)始丟失請(qǐng)求，但其在請(qǐng)求錯(cuò)過(guò)其截止期限方面的表現(xiàn)仍是最優(yōu)的。

5.3 云計(jì)算網(wǎng)絡(luò)與云霧混合網(wǎng)絡(luò)的對(duì)比分析

一般來(lái)說(shuō)，云資源具有強(qiáng)大的處理能力，但同時(shí)也具有較大的平均傳輸和網(wǎng)絡(luò)時(shí)延。相反，霧資源的處理能力有限，但由于其離邊緣較近，所以造成的平均時(shí)延較小。為了能夠針對(duì)擁有最小的時(shí)延一組請(qǐng)求進(jìn)行服務(wù)，考慮了3個(gè)參數(shù)：平均時(shí)延率τf/τc；處理速度比Vf/Vc；資源數(shù)量比率Mf/Mc。

實(shí)驗(yàn)中通過(guò)固定另外兩個(gè)參數(shù)，且只改變一個(gè)參數(shù)的方式研究了每個(gè)參數(shù)對(duì)服務(wù)時(shí)延的影響。其中，云端配置了4個(gè)超級(jí)云服務(wù)器，具非常高的處理能力，可以每秒處理5000個(gè)數(shù)據(jù)包。然而這些服務(wù)器的平均時(shí)延設(shè)置得相對(duì)比較高，每個(gè)數(shù)據(jù)包為10 ms。為了評(píng)估時(shí)延，在這組實(shí)驗(yàn)中總共處理了500個(gè)請(qǐng)求，這些請(qǐng)求的到達(dá)時(shí)間遵循泊松分布，平均到達(dá)時(shí)間為1 s，并且平均請(qǐng)求數(shù)據(jù)量的大小從1000包變?yōu)?0 000包。

(1)平均時(shí)延率的影響

實(shí)驗(yàn)中霧服務(wù)器的數(shù)量設(shè)為云服務(wù)器數(shù)量的4倍，即Mf/Mc=4，并且霧服務(wù)器的處理能力只有10%，即Vf/Vc=10%。平均時(shí)延率τf/τc將改變?yōu)?0%、20%、50%和70%。平均時(shí)延率對(duì)總體平均服務(wù)時(shí)延的影響如圖7所示。

圖7 不同平均時(shí)延率對(duì)平均時(shí)延的影響對(duì)比

從圖7中可以看出，當(dāng)平均時(shí)延率從10%增加到70%時(shí)，會(huì)增加霧的時(shí)延，并且霧的時(shí)延會(huì)不斷增加直到平均時(shí)延率處于與云時(shí)延相同時(shí)的節(jié)點(diǎn)。這是因?yàn)殪F服務(wù)器遠(yuǎn)離邊緣設(shè)備，更靠近云服務(wù)器。在這種情況下，霧服務(wù)器與云服務(wù)器兩者產(chǎn)生的時(shí)延一樣低。

(2)處理速度比的影響

實(shí)驗(yàn)中霧服務(wù)器的數(shù)量設(shè)為云服務(wù)器數(shù)量的4倍，即Mf/Mc=4，霧服務(wù)器的平均時(shí)延τf/τc為10%。處理速度比Vf/Vc分別被設(shè)置為4%、7%、15%和20%。處理速度比對(duì)總體平均服務(wù)時(shí)延的影響如圖8所示。

從圖8中可以看出，當(dāng)處理速度比從20%降低到4%時(shí)，霧的時(shí)延會(huì)增加，并且霧的時(shí)延會(huì)不斷增加直到其超越云的時(shí)延。這是因?yàn)殪F服務(wù)器具有緩慢的處理速度。在這種情況下，即使這些資源比云資源更接近邊緣，但由于處理速度慢，霧也會(huì)產(chǎn)生較高的時(shí)延。

(3)計(jì)算資源數(shù)量比率的影響

實(shí)驗(yàn)中服務(wù)器的平均時(shí)延率設(shè)為云平均時(shí)延的10%，并且霧服務(wù)器的處理能力設(shè)為云服務(wù)器能力的10%。霧資源的數(shù)量相對(duì)于云資源數(shù)量比的變化為100%、150%、200%、400%和800%。資源數(shù)量比率對(duì)總體平均服務(wù)時(shí)延的影響如圖9所示。

從圖9中可以看出，當(dāng)資源的數(shù)量比率從800%降低到 100%時(shí)，霧的時(shí)延會(huì)增加，并且霧的時(shí)延會(huì)不斷增加直到其超越云的時(shí)延，因?yàn)殪F服務(wù)器具有很少的資源。因此即使這些資源更接近邊緣并且具有良好的處理能力，但由于霧服務(wù)器的資源很少，這也會(huì)以負(fù)面的方式影響霧服務(wù)器中產(chǎn)生的時(shí)延。

圖8 處理速度比對(duì)平均時(shí)延的影響

圖9 計(jì)算資源數(shù)量比率對(duì)平均時(shí)延的影響對(duì)比

6 結(jié)束語(yǔ)

當(dāng)前，我國(guó)現(xiàn)代化信息技術(shù)發(fā)展迅速，已經(jīng)廣泛深入到各個(gè)不同的領(lǐng)域，以具有較低延時(shí)為代表的信息服務(wù)質(zhì)量變得越發(fā)重要。霧計(jì)算的出現(xiàn)對(duì)云計(jì)算技術(shù)起到了發(fā)展提升作用，提出了一種面向低時(shí)延的云霧混合網(wǎng)絡(luò)及其負(fù)載均衡策略。基于構(gòu)建了云霧混合網(wǎng)絡(luò)，將物聯(lián)網(wǎng)設(shè)備的有限功能要求應(yīng)用程序合理分配到云和霧計(jì)算中，并且將物聯(lián)網(wǎng)服務(wù)請(qǐng)求的均衡建模成一個(gè)優(yōu)化問(wèn)題，利用改進(jìn)的BA算法進(jìn)行求解，合理分配云和霧計(jì)算資源，降低用戶請(qǐng)求的處理時(shí)延，滿足低時(shí)延需求?；陔x散事件仿真器構(gòu)建實(shí)驗(yàn)?zāi)Ｐ蛯?duì)所提策略進(jìn)行測(cè)試，通過(guò)種群規(guī)模和最大迭代次數(shù)等參數(shù)對(duì)改進(jìn)BA影響的分析，得到將兩參數(shù)分別設(shè)為60、20，能夠在較合適的時(shí)延時(shí)間內(nèi)實(shí)現(xiàn)高質(zhì)量的負(fù)載均衡。并且與其它策略相比，在靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種場(chǎng)景下，所提策略的總時(shí)延也有了顯著改善。最后，論證了將霧計(jì)算與云計(jì)算相結(jié)合的重要性，在如資源平均時(shí)延、處理能力、資源數(shù)量等參數(shù)方面，霧計(jì)算相較于云計(jì)算具有更好的性能。

所提策略中僅考慮時(shí)延最小化這一目標(biāo)函數(shù)，接下來(lái)的研究將考慮多個(gè)目標(biāo)函數(shù)，并且全面考慮關(guān)鍵請(qǐng)求調(diào)度、允許搶占、優(yōu)先處理等方面，從而實(shí)現(xiàn)資源利用率的最大化以及時(shí)延的最小化。