基于優(yōu)先權(quán)排隊(duì)論的霧計(jì)算資源配置算法

朱 敏

（江蘇航運(yùn)職業(yè)技術(shù)學(xué)院智能制造與信息學(xué)院，江蘇南通 226010）

引言

物聯(lián)網(wǎng)技術(shù)與應(yīng)用的發(fā)展，離不開云計(jì)算技術(shù)與基礎(chǔ)設(shè)施的支持。然而，云端數(shù)據(jù)中心通常遠(yuǎn)離物聯(lián)網(wǎng)終端設(shè)備，數(shù)據(jù)傳輸所造成的網(wǎng)絡(luò)瓶頸會導(dǎo)致延遲和低質(zhì)量的物聯(lián)網(wǎng)服務(wù)。使得一些對實(shí)時(shí)性要求較高的物聯(lián)網(wǎng)應(yīng)用，如智能制造、智慧醫(yī)療等無法正常運(yùn)作。霧計(jì)算由此出現(xiàn)。它是一種分布式的計(jì)算方式。霧計(jì)算設(shè)施通常位置上靠近物聯(lián)網(wǎng)終端設(shè)備，因而能減少延遲，提供更高質(zhì)量的用戶服務(wù)。霧計(jì)算不是云計(jì)算的替代品，而是云計(jì)算的有效補(bǔ)充，兩種技術(shù)相輔相成。物聯(lián)網(wǎng)終端設(shè)備可以將平常零散的數(shù)據(jù)先發(fā)送到霧計(jì)算設(shè)備，經(jīng)過聚集和初步處理后再批量發(fā)送到云端，以減少對云端的訪問數(shù)，而將復(fù)雜的計(jì)算任務(wù)交給云端處理。Mahmud 等人的研究認(rèn)為霧計(jì)算是對云計(jì)算范式在物聯(lián)網(wǎng)邊緣的一種擴(kuò)展，是對云計(jì)算高延遲和網(wǎng)絡(luò)擁塞問題的一種解決方案，并就霧計(jì)算在結(jié)構(gòu)、服務(wù)及安全等方面所面對的主要挑戰(zhàn)和重要的研究方向展開討論[1]。在文獻(xiàn)[2]中作者研究了霧層和云層之間的相互關(guān)系，對霧計(jì)算系統(tǒng)的服務(wù)延遲、能耗、運(yùn)營成本等方面精細(xì)建模。研究表明，當(dāng)系統(tǒng)中延遲敏感型的應(yīng)用較多時(shí)，霧計(jì)算能取得比云計(jì)算更好的綜合性能。在文獻(xiàn)[3]中作者將排隊(duì)論應(yīng)用于霧計(jì)算的分析與研究，提出了一個(gè)基于開放性多類別排隊(duì)網(wǎng)絡(luò)的模型，將到達(dá)任務(wù)在霧層與云平臺間作有效分配。在文獻(xiàn)[4]中作者提出了一個(gè)基于優(yōu)先隊(duì)列任務(wù)調(diào)度算法，以減少延遲敏感型任務(wù)的響應(yīng)時(shí)間，并針對非計(jì)算型任務(wù)提出了一種動態(tài)優(yōu)先級方案，從而將延遲控制在某個(gè)可接受的閾值之內(nèi)。

霧計(jì)算的關(guān)鍵在于處理好計(jì)算任務(wù)在霧節(jié)點(diǎn)與云平臺之間的分配問題，因此應(yīng)用程序的任務(wù)調(diào)度和資源分配是它面對的主要挑戰(zhàn)。本研究基于帶優(yōu)先權(quán)的排隊(duì)理論，根據(jù)計(jì)算任務(wù)對延遲的敏感程度將它們分成高、中、低三個(gè)優(yōu)先級層次，提出了一種霧計(jì)算環(huán)境下有優(yōu)先權(quán)的任務(wù)調(diào)度和資源分配方案。并對這種方案進(jìn)行模擬驗(yàn)證。

1 基于優(yōu)先權(quán)排隊(duì)論的資源配置模型

系統(tǒng)模型基于霧計(jì)算的計(jì)算架構(gòu)，包括3 個(gè)層次，物聯(lián)網(wǎng)終端設(shè)備層、霧計(jì)算層和云計(jì)算層。云計(jì)算層處于頂層，即遠(yuǎn)端的云計(jì)算數(shù)據(jù)中心。中間層是霧層，由一定數(shù)量的霧節(jié)點(diǎn)組成。每個(gè)霧節(jié)點(diǎn)都是一個(gè)微型數(shù)據(jù)中心。底層為物聯(lián)網(wǎng)終端設(shè)備層，它們是服務(wù)請求的發(fā)起者。

終端設(shè)備層發(fā)出的服務(wù)請求首先發(fā)送到最近的霧節(jié)點(diǎn)。霧節(jié)點(diǎn)收到客戶端請求后，根據(jù)請求的優(yōu)先級，可用資源等要素，將請求放入不同優(yōu)先級的隊(duì)列中。然后按照優(yōu)先順序，依次為隊(duì)列中的任務(wù)提供服務(wù)。如果某個(gè)任務(wù)本節(jié)點(diǎn)有能力處理，則將該任務(wù)就地處理后發(fā)送給客戶端。如果本節(jié)點(diǎn)資源不足，而霧計(jì)算層中的其它節(jié)點(diǎn)有資源處理，則將該任務(wù)發(fā)往其它霧節(jié)點(diǎn)處理。否則就將服務(wù)請求發(fā)送到云計(jì)算中心處理。我們將任務(wù)的優(yōu)先級分成H、M、L 三個(gè)等級，對應(yīng)三個(gè)隊(duì)列QH、QM、QL。每一個(gè)到達(dá)的任務(wù)都有一個(gè)最大可容忍延遲delayi。對一些有極高延遲要求的任務(wù)，這些任務(wù)必須在一個(gè)較小的延遲內(nèi)得到響應(yīng)。我們設(shè)一個(gè)閾值TH1。若一個(gè)任務(wù)的delayi小于TH1，就賦予這個(gè)任務(wù)高優(yōu)先級（H）；若一個(gè)任務(wù)的delayi大于TH1，但小于TH2，則賦予中優(yōu)先級（M）；其它對延遲不敏感的任務(wù)賦予低優(yōu)先級（L）。

算法1 Priority 算法，為到達(dá)的任務(wù)賦優(yōu)先級。

輸入：N, delayi,TH1,TH2、

輸出：Pri, QH,QM,QL

如圖1 所示，我們將排隊(duì)理論[5]應(yīng)用于系統(tǒng)建模。假設(shè)有n 個(gè)物聯(lián)網(wǎng)終端設(shè)備發(fā)出請求任務(wù)，其任務(wù)的到達(dá)過程服從總到達(dá)率為λ 的泊松過程。霧層服務(wù)器處理任務(wù)的時(shí)間服從參數(shù)為μ 的負(fù)指數(shù)分布。霧層服務(wù)器符合M/M/k 隊(duì)列模型，其中k 表示系統(tǒng)中霧服務(wù)器的數(shù)量。

圖1 系統(tǒng)排隊(duì)模型

圖2 所示為隊(duì)列系統(tǒng)的連續(xù)時(shí)間馬爾可夫鏈狀態(tài)轉(zhuǎn)換關(guān)系圖。其中λ 為到達(dá)率，μ 為服務(wù)率。M/M /k 隊(duì)列系統(tǒng)中有i 個(gè)任務(wù)的穩(wěn)態(tài)概率通常為

圖2 馬爾可夫鏈狀態(tài)轉(zhuǎn)換關(guān)系

假如所有服務(wù)臺都處于忙期，一個(gè)新的任務(wù)進(jìn)入而需要等待的概率為

設(shè)定在排隊(duì)系統(tǒng)中一個(gè)正接受服務(wù)的任務(wù)不能被后到達(dá)的優(yōu)先權(quán)更高的任務(wù)所中止，即這是非強(qiáng)占型的排隊(duì)系統(tǒng)，則在有3 個(gè)優(yōu)先等級的隊(duì)列中，正在接受服務(wù)中的任務(wù)的平均剩余服務(wù)時(shí)間W0為

3 個(gè)不同優(yōu)先級（1 為最高、3 為最低）平均等待時(shí)間分別為

假設(shè)α1、α2分別為高、中優(yōu)先級任務(wù)在總?cè)蝿?wù)數(shù)中的平均占比，則有

某一任務(wù)在隊(duì)列系統(tǒng)中的平均逗留時(shí)間可以表示為

這樣我們的基于優(yōu)先權(quán)的資源提供策略就可以轉(zhuǎn)換成一個(gè)最小化任務(wù)延遲的優(yōu)化問題。該問題可以形式化地表示如下

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

我們通過仿真實(shí)驗(yàn)對模型進(jìn)行評估與分析，表1所示為仿真參數(shù)及其取值。

表1 仿真參數(shù)及取值

我們首先將本方案下不同優(yōu)先權(quán)限任務(wù)的系統(tǒng)延遲進(jìn)行了比較，并且把有優(yōu)先權(quán)的方案與通常的無優(yōu)先權(quán)的排隊(duì)方案同時(shí)進(jìn)行了比較，見圖3。結(jié)果顯示，高優(yōu)先級與中優(yōu)先級的任務(wù)的延遲得到顯著的改善，都比無優(yōu)先分級的情況要好，但低優(yōu)先級任務(wù)的延遲變得更大了，顯然，高、中優(yōu)先級的改善是以犧牲低優(yōu)先級為代價(jià)的。

圖3 到達(dá)任務(wù)系統(tǒng)延遲

其次，我們考察了在系統(tǒng)空閑（ρ=0.3）與繁忙（ρ=0.8）兩種情境下到達(dá)任務(wù)的延遲情況。由圖4 可知，對高優(yōu)先級任務(wù)而言，延遲的變化很小，而無優(yōu)先級的延遲則要大得多。兩者相比，在系統(tǒng)空閑（ρ=0.3）時(shí)，高優(yōu)先級任務(wù)的延遲性能比無優(yōu)先級任務(wù)提升了25.53%；而在系統(tǒng)繁忙（ρ=0.8））時(shí)，延遲性能的提升更為顯著，達(dá)到了76.19%。圖5 顯示了低優(yōu)先級任務(wù)在系統(tǒng)繁忙與空閑時(shí)的不同變化。低優(yōu)先級任務(wù)在系統(tǒng)繁忙時(shí)延遲會顯著增加，遠(yuǎn)大于無優(yōu)先級時(shí)的情況。

圖4 高優(yōu)先權(quán)任務(wù)延遲比較

圖5 低優(yōu)先權(quán)任務(wù)延遲比較

3 結(jié)論

本研究提出了一種基于優(yōu)先權(quán)排隊(duì)論的資源分配方案，旨在使一些延遲敏感型的物聯(lián)網(wǎng)應(yīng)用能夠在鄰近的霧計(jì)算層得到優(yōu)先處理。實(shí)驗(yàn)結(jié)果顯示，高、中優(yōu)先級任務(wù)的延遲得到顯著的改善，大大優(yōu)于無優(yōu)先權(quán)的通常情境。