面向海量終端輕量級(jí)認(rèn)證的調(diào)度算法

王傳君，繆巍巍，曽 锃，張明軒，張 震

(國網(wǎng)江蘇省電力公司信息通信分公司， 南京 210024)

物聯(lián)網(wǎng)的理念使得設(shè)備可以不通過人作為中間媒介而直接進(jìn)行信息交互，大大增加了信息傳播的速度與范圍，也方便了人們的生活[1-2]。國網(wǎng)也提出了泛在電力物聯(lián)網(wǎng)這一概念并對(duì)建設(shè)做出了全面部署安排。然而，這種不需要人參與的信息交互在帶來便利的同時(shí)也引入了新的安全問題。在網(wǎng)絡(luò)安全形勢(shì)日益嚴(yán)峻的現(xiàn)在，網(wǎng)絡(luò)攻擊的破壞性和威脅性持續(xù)增加，電力關(guān)鍵信息基礎(chǔ)設(shè)施已成為網(wǎng)絡(luò)打擊破壞的首要攻擊目標(biāo)。

出于安全考慮，電力系統(tǒng)在物聯(lián)設(shè)備接入平臺(tái)之前都會(huì)對(duì)設(shè)備進(jìn)行認(rèn)證。業(yè)界物聯(lián)網(wǎng)平臺(tái)主要采用token認(rèn)證[3]、TLS證書認(rèn)證[4]等方式實(shí)現(xiàn)邊緣設(shè)備的認(rèn)證接入。電力物聯(lián)網(wǎng)下連的各電力終端涉及生產(chǎn)數(shù)據(jù)、控制操作等功能，當(dāng)通過邊緣設(shè)備實(shí)現(xiàn)匯聚接入后，需要強(qiáng)化對(duì)邊緣設(shè)備的安全認(rèn)證，防止邊緣設(shè)備被反向控制、系統(tǒng)/APP被惡意篡改等。

現(xiàn)階段應(yīng)用與邊緣設(shè)備的認(rèn)證技術(shù)大部分需要繁雜的加密計(jì)算，即使采用輕量級(jí)認(rèn)證系統(tǒng)[5-6]或者簡(jiǎn)化的加密算法，如AES[7]和SHA-1[8]也需要數(shù)千個(gè)(或數(shù)萬個(gè))門電路和數(shù)千個(gè)時(shí)鐘周期，因此大部分物聯(lián)網(wǎng)設(shè)備無法應(yīng)用這些加密算法實(shí)現(xiàn)認(rèn)證。同時(shí)大量邊緣設(shè)備的可信認(rèn)證[9-10]需要占用物聯(lián)管理平臺(tái)的計(jì)算與通信資源，就算是輕量級(jí)的認(rèn)證機(jī)制[11-12]，也很難在有限時(shí)間與資源約束下實(shí)時(shí)響應(yīng)。與之前的工作不同，我們關(guān)注的更多是如何在海量設(shè)備同時(shí)進(jìn)行驗(yàn)證時(shí)能夠合理調(diào)度平臺(tái)的計(jì)算資源使得驗(yàn)證能夠在最短的時(shí)間內(nèi)完成，對(duì)于設(shè)備具體使用哪種認(rèn)證方式不做考慮，上述參考文獻(xiàn)都是提出了一種新的輕量級(jí)身份驗(yàn)證機(jī)制，是系統(tǒng)與機(jī)制層面的工作，我們的主要是理論工作。

在電力物聯(lián)網(wǎng)場(chǎng)景下，設(shè)備的認(rèn)證會(huì)經(jīng)過3個(gè)模塊，分別是設(shè)備連接模塊、設(shè)備管理模塊和影子設(shè)備模塊。每個(gè)模塊由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)的計(jì)算能力之間存在著差異?？梢灶A(yù)見的是，隨著物聯(lián)網(wǎng)的不斷發(fā)展，需要進(jìn)行認(rèn)證的設(shè)備也將越來越多。根據(jù)沙利文數(shù)據(jù)顯示，2020年全球有超過500億的終端與設(shè)備聯(lián)網(wǎng)，中國的聯(lián)網(wǎng)設(shè)備預(yù)計(jì)從2016年的8.4億個(gè)增長(zhǎng)到35億個(gè)。如何快速有效地為海量設(shè)備進(jìn)行實(shí)時(shí)認(rèn)證成為了一個(gè)重要且具有挑戰(zhàn)性的問題。

在本文中，設(shè)計(jì)面向海量邊緣設(shè)備實(shí)時(shí)認(rèn)證的調(diào)度算法。每當(dāng)有邊緣設(shè)備請(qǐng)求進(jìn)行認(rèn)證時(shí)，該框架能夠根據(jù)物聯(lián)管理平臺(tái)上各個(gè)模塊節(jié)點(diǎn)當(dāng)前的處理資源，靈活地將該認(rèn)證請(qǐng)求調(diào)度到最適合的節(jié)點(diǎn)上進(jìn)行處理，使得該設(shè)備的請(qǐng)求能夠在最短的時(shí)間內(nèi)完成認(rèn)證。鑒于該問題是NP完全的，最終設(shè)計(jì)了2種不同的調(diào)度算法。其中貪心算法(SJF)每次都會(huì)將認(rèn)證請(qǐng)求調(diào)度到處理能力最快的節(jié)點(diǎn)上，經(jīng)過理論證明，SJF在某些情況下能夠達(dá)到2近似。啟發(fā)式算法(MBF)則每次都將認(rèn)證請(qǐng)求調(diào)度到邊際效益最大的節(jié)點(diǎn)上，通過仿真實(shí)驗(yàn)，在設(shè)備數(shù)量較少時(shí)MBF的表現(xiàn)非常接近最優(yōu)算法。

1 海量設(shè)備輕量級(jí)認(rèn)證系統(tǒng)概述

1.1 海量設(shè)備輕量級(jí)認(rèn)證系統(tǒng)

設(shè)備的認(rèn)證環(huán)境中，大量的邊緣設(shè)備與物聯(lián)管理平臺(tái)連接，并且需要在管理平臺(tái)上進(jìn)行輕量級(jí)認(rèn)證[5-6]。認(rèn)證會(huì)經(jīng)過3個(gè)模塊，分別是設(shè)備連接模塊、設(shè)備管理模塊和影子設(shè)備模塊。每個(gè)模塊由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)的計(jì)算能力之間存在著差異。為了提高認(rèn)證效率和專用性，每個(gè)節(jié)點(diǎn)經(jīng)過提前配置，能夠?yàn)樘囟悇e的設(shè)備提供認(rèn)證服務(wù)。物聯(lián)管理平臺(tái)上每個(gè)節(jié)點(diǎn)的處理能力都是有限的。為了更靈活地利用節(jié)點(diǎn)資源，一般會(huì)利用虛擬化技術(shù)[13]將節(jié)點(diǎn)的資源池化成多個(gè)虛擬機(jī)，假設(shè)模塊節(jié)點(diǎn)上的虛擬機(jī)都具有相同的處理能力。

考慮到無線專用網(wǎng)絡(luò)[16]的快速發(fā)展與設(shè)備和物聯(lián)管理平臺(tái)之間距離較短，不妨假設(shè)設(shè)備與物聯(lián)管理平臺(tái)之間的傳輸時(shí)延可以忽略不計(jì)，于是主要的耗時(shí)就是認(rèn)證階段。同時(shí)，為了認(rèn)證的連續(xù)性，假設(shè)在認(rèn)證過程中，設(shè)備無法從當(dāng)前模塊節(jié)點(diǎn)切換到另一個(gè)模塊節(jié)點(diǎn)。

1.2 問題描述

為使所有種類的設(shè)備在最短時(shí)間內(nèi)能得到認(rèn)證。需要決策的變量是每個(gè)種類的設(shè)備需要在物聯(lián)管理平臺(tái)上的哪個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證。于是本文的問題描述如下：

給定需要認(rèn)證的設(shè)備種類集合U與每種設(shè)備的數(shù)量Si，用來進(jìn)行認(rèn)證的物聯(lián)管理平臺(tái)中的模塊節(jié)點(diǎn)集合E與每個(gè)模塊節(jié)點(diǎn)上虛擬機(jī)的數(shù)量kj。給定模塊節(jié)點(diǎn)配置rij。本文的目的是決定每種設(shè)備應(yīng)該被分配到哪個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證，從而使所有設(shè)備的認(rèn)證時(shí)間最短(CASP)。

因?yàn)樵O(shè)備是在虛擬機(jī)上進(jìn)行認(rèn)證，所以只需要關(guān)注最后完成認(rèn)證的虛擬機(jī)即可知道所有設(shè)備完成認(rèn)證的時(shí)間。于是目標(biāo)變成了：

(1)

需要注意的是，認(rèn)證需要考慮模塊節(jié)點(diǎn)的資源約束，且一個(gè)虛擬機(jī)同時(shí)只能對(duì)一個(gè)設(shè)備進(jìn)行認(rèn)證：

(2)

(3)

單個(gè)設(shè)備可以同時(shí)使用多個(gè)虛擬機(jī)進(jìn)行認(rèn)證，這會(huì)加快認(rèn)證的速度。假設(shè)所有設(shè)備都使用相同的認(rèn)證程序，認(rèn)證的速度只與處理能力有關(guān)，且虛擬機(jī)只有在完成當(dāng)前種類所有設(shè)備的認(rèn)證后才能認(rèn)證新的種類。令vi表示設(shè)備ui的處理速度，表達(dá)式為：

(4)

2 問題分析與算法設(shè)計(jì)

2.1 問題復(fù)雜度分析

通過將makespan問題[17]規(guī)約到CASP的一個(gè)特例來證明CASP是NP完全的。

Makespan問題的定義如下：給定n個(gè)作業(yè)的集合J={J1，J2，…，Jn}與每個(gè)作業(yè)所對(duì)應(yīng)的處理時(shí)間，m個(gè)處理能力相同的機(jī)器，問是否存在一組作業(yè)與機(jī)器的映射，使得可以用最少的時(shí)間處理完所有的作業(yè)。

通過如下的構(gòu)造將makespan問題規(guī)約到CASP問題的特例。

1) 對(duì)于每個(gè)作業(yè)Ji，將CASP問題中種類ui的認(rèn)證構(gòu)造成一個(gè)作業(yè)；

2) 對(duì)于每個(gè)作業(yè)Ji的處理時(shí)間，首先假設(shè)每個(gè)種類只能使用一個(gè)虛擬機(jī)進(jìn)行認(rèn)證(這是CASP問題的一個(gè)特例)，之后將設(shè)備種類ui的總認(rèn)證時(shí)長(zhǎng)Si/c構(gòu)造成makespan問題中作業(yè)的處理時(shí)間；

3) 對(duì)于處理能力相同的機(jī)器，將模塊節(jié)點(diǎn)的數(shù)量設(shè)置為1，并將虛擬機(jī)的數(shù)量ki設(shè)置為1，于是這些處理能力都為c的虛擬機(jī)便構(gòu)造成了makespan問題中處理能力相同的機(jī)器；

這樣的構(gòu)造是可以在多項(xiàng)式時(shí)間之內(nèi)完成的，于是，本文將解決NP難的makespan問題規(guī)約成了解決CASP問題的一個(gè)特例，這也意味著CASP問題是NP完全的。

2.2 算法設(shè)計(jì)

2.2.1貪心算法

CASP是NP完全的，這意味著無法在多項(xiàng)式時(shí)間內(nèi)找到它的最優(yōu)解。提出了基于處理時(shí)間貪心的設(shè)備認(rèn)證調(diào)度算法(SJF)來求解。具體步驟如下：

步驟2決定初始的分配方案。如果模塊節(jié)點(diǎn)ej有足夠的虛擬機(jī)，則所有可以在該模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證的種類都能分配到一個(gè)虛擬機(jī)，只有當(dāng)虛擬機(jī)的數(shù)量小于種類數(shù)量的時(shí)候才需要進(jìn)行決策。在SJF算法中，每次都會(huì)將虛擬機(jī)分配給最快完成認(rèn)證的設(shè)備種類，即一個(gè)設(shè)備種類可以獲得一個(gè)虛擬機(jī)中當(dāng)且僅當(dāng)該種類獲得該虛擬機(jī)后能夠比其他的設(shè)備種類更快完成認(rèn)證；

步驟3虛擬機(jī)重分配。每當(dāng)一種設(shè)備完成認(rèn)證后，負(fù)責(zé)該種類認(rèn)證的虛擬機(jī)就可以再次分配給其他種類的設(shè)備進(jìn)行驗(yàn)證。在虛擬機(jī)的再次分配中，SJF會(huì)將其分配給完成時(shí)間最快的種類；

步驟4當(dāng)所有設(shè)備都完成認(rèn)證后算法終止。

當(dāng)模塊節(jié)點(diǎn)上的虛擬機(jī)數(shù)量是O(n)時(shí)，算法SJF的復(fù)雜度是O(n3)。初始化分配時(shí)，對(duì)于m個(gè)模塊節(jié)點(diǎn)上的O(n)個(gè)虛擬機(jī)，需要對(duì)可以認(rèn)證的O(n)個(gè)設(shè)備種類進(jìn)行比較，這里的復(fù)雜度是O(mn2)。當(dāng)有設(shè)備種類完成認(rèn)證后，需要對(duì)空閑的虛擬機(jī)進(jìn)行再分配，此時(shí)需要O(n)的對(duì)比。而最多需要重新分配O(n)次虛擬機(jī)。于是當(dāng)m

接下來將證明在圖1的場(chǎng)景下，SJF算法能夠達(dá)到2近似。

圖1 CASP的特殊場(chǎng)景示意圖

在圖1中，每種設(shè)備都能在2個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證，而模塊節(jié)點(diǎn)有且僅有一個(gè)虛擬機(jī)。這意味著每種設(shè)備最多可以獲得2c的處理能力。為了方便表述，本文定義ti=Si/c，并定義最優(yōu)解的完成時(shí)間為T*。

不失一般性，假設(shè)ti是所有種類里耗時(shí)最長(zhǎng)的，up是所有種類里最后一個(gè)完成的。這里需要對(duì)2種情況進(jìn)行討論。

綜上，在某些特殊場(chǎng)景下，算法SJF能夠取得2+ε的近似比，其中ε<1。

2.2.2啟發(fā)式算法

針對(duì)一般場(chǎng)景下的CASP問題，設(shè)計(jì)了一個(gè)邊際最優(yōu)調(diào)度的啟發(fā)式算法(MBF)來解決它。

2) 決定初始的分配方案。本文使用細(xì)粒度的分配方式，最小的分配單位是一個(gè)虛擬機(jī)。在進(jìn)行決策時(shí)，首先定義認(rèn)證效益(MB)這一概念，其表達(dá)式為Si/vi-Si/(vi+c)。在初始階段，所有的設(shè)備種類處理速度都為0，此時(shí)每次分配都將一個(gè)虛擬機(jī)分配給處理時(shí)長(zhǎng)最短的且還未分配到虛擬機(jī)的種類。這一階段持續(xù)到虛擬機(jī)分配結(jié)束或者所有能夠分配的種類都至少分配到一個(gè)虛擬機(jī)為止。對(duì)于初始階段剩余的虛擬機(jī)，算法再按照認(rèn)證效益從大到小的順序進(jìn)行分配，直到所有的虛擬機(jī)分配完成；

3) 虛擬機(jī)重分配。每當(dāng)一種設(shè)備完成認(rèn)證后，分配給它的虛擬機(jī)就空閑了，此時(shí)算法會(huì)對(duì)這些虛擬機(jī)進(jìn)行再分配，分配的策略依然是按照認(rèn)證效益從大到小的順序；

4) 當(dāng)所有的設(shè)備得到認(rèn)證后算法終止。

看起來似乎MBF能夠充分地利用每一個(gè)虛擬機(jī)，因?yàn)樘摂M機(jī)每次都會(huì)被分配給邊際效益最大的設(shè)備種類。然而，這樣的分析并沒有考慮到模塊節(jié)點(diǎn)配置的影響?？紤]如下的一個(gè)場(chǎng)景，模塊節(jié)點(diǎn)e1可以為種類u1與u2提供認(rèn)證服務(wù)，且e1上只有一個(gè)虛擬機(jī)，初始時(shí)，由于e1上的虛擬機(jī)是第一個(gè)進(jìn)行分配的，按照處理時(shí)長(zhǎng)的順序，虛擬機(jī)被分配給了u2。然而種類u1的設(shè)備只能在模塊節(jié)點(diǎn)e1上進(jìn)行認(rèn)證，而種類u2的設(shè)備則可以在多個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證。這樣的分配很可能會(huì)錯(cuò)過一些更好的方案。為了避免這種情況，就需要在初始分配時(shí)檢查所有可能的分配情況，即所有模塊節(jié)點(diǎn)的全排列，共有m!種情況。很顯然，要想檢查所有的排列是不現(xiàn)實(shí)的。因此，MBF算法會(huì)檢查R種排列，最后在這R種排列中選擇最小的完成時(shí)間作為算法的輸出。每種排列的復(fù)雜度都與SJF的復(fù)雜度相同。當(dāng)m

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

3.1 實(shí)驗(yàn)設(shè)置

1) 環(huán)境設(shè)置：將物聯(lián)設(shè)備分為輸電設(shè)備、變電設(shè)備、配電設(shè)備與用電設(shè)備等種類，其中每種電力設(shè)備設(shè)置為4 000～8 000個(gè)，每個(gè)設(shè)備的認(rèn)證時(shí)間設(shè)置為400～600 μs。在電力物聯(lián)網(wǎng)場(chǎng)景下，設(shè)備的認(rèn)證會(huì)經(jīng)過3個(gè)模塊，分別是設(shè)備連接模塊、設(shè)備管理模塊以及影子設(shè)備模塊。每個(gè)模塊由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)的計(jì)算能力之間存在著差異。為了方便起見，在設(shè)備的認(rèn)證過程中只考慮設(shè)備管理模塊，本文的方法也可以擴(kuò)展到設(shè)備連接模塊與影子設(shè)備模塊的處理分析。每種設(shè)備能在1～10個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證。

2) 對(duì)比算法：除了本文中提出的SJF算法和MBF算法之外，還將介紹隨機(jī)算法(RA)作為參照。RA算法分配的粒度也是單個(gè)虛擬機(jī)，每次分配虛擬機(jī)時(shí)，都會(huì)隨機(jī)選擇一個(gè)種類進(jìn)行分配，直到虛擬機(jī)全部分配或者所有種類都完成認(rèn)證。

在正式進(jìn)入驗(yàn)證環(huán)節(jié)之前，首先將MBF算法與暴力搜索算法(OPT)進(jìn)行對(duì)比。鑒于運(yùn)行暴力搜索算法的復(fù)雜度太高，只進(jìn)行了小規(guī)模的實(shí)驗(yàn)對(duì)比(10種設(shè)備，每種設(shè)備最多在3個(gè)模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證，每個(gè)模塊節(jié)點(diǎn)只有一個(gè)虛擬機(jī))，實(shí)驗(yàn)結(jié)果如圖2所示?？梢钥闯觯∫?guī)模時(shí)，MBF算法的性能非常接近暴力搜索算法(最優(yōu)解)。

圖2 MBF算法與暴力搜索算法實(shí)驗(yàn)結(jié)果直方圖

3.2 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證虛擬機(jī)的數(shù)量對(duì)完成時(shí)間的影響，將設(shè)備的種類設(shè)置為10個(gè)，將認(rèn)證模塊節(jié)點(diǎn)的數(shù)量設(shè)置為10，并提前配置好模塊節(jié)點(diǎn)可以認(rèn)證的設(shè)備種類，然后觀察虛擬機(jī)數(shù)量對(duì)實(shí)驗(yàn)的影響，結(jié)果如圖3所示。可以看出，完成時(shí)間隨著虛擬機(jī)數(shù)量的增加而不斷遞減，這是很顯然的，虛擬機(jī)越多，模塊節(jié)點(diǎn)的處理能力就越大，總完成時(shí)間就減少了。虛擬機(jī)較少時(shí)，SJF的性能也更接近MBF算法。

圖3 不同虛擬機(jī)數(shù)量的完成時(shí)間直方圖

為了探究完成時(shí)間與種類數(shù)量的關(guān)系，將模塊種類的數(shù)量設(shè)置為10，將每個(gè)模塊節(jié)點(diǎn)上的虛擬機(jī)設(shè)置為2～5個(gè)，設(shè)備種類的變化數(shù)量來觀察影響，結(jié)果如圖4所示?？梢钥闯觯瓿蓵r(shí)間隨著種類的增加而不斷遞增，這是很合理的，隨著設(shè)備種類的變多，需要進(jìn)行驗(yàn)證的設(shè)備也變多了，總認(rèn)證時(shí)間也相應(yīng)變多了。同時(shí)，在設(shè)備種類數(shù)量較少的時(shí)候各算法之間的性能差別也較小，這是因?yàn)樵O(shè)備種類較少時(shí)，模塊節(jié)點(diǎn)的處理能力是完全足夠的，所以設(shè)備認(rèn)證時(shí)幾乎沒有等待時(shí)間。

圖4 不同設(shè)備種類的完成時(shí)間直方圖

為了探究完成時(shí)間與模塊節(jié)點(diǎn)數(shù)量的關(guān)系，將設(shè)備的種類設(shè)置為10，將每個(gè)模塊節(jié)點(diǎn)上的虛擬機(jī)設(shè)置為2～5個(gè)，然后變化設(shè)備種類的數(shù)量來觀察影響，結(jié)果如圖5所示。可以看出，完成時(shí)間隨著模塊節(jié)點(diǎn)數(shù)量的增加而不斷減少，這是合理的，隨著模塊節(jié)點(diǎn)的變多，可以進(jìn)行認(rèn)證的虛擬機(jī)也變多了，認(rèn)證的時(shí)間也相應(yīng)變少了。同時(shí)，在模塊節(jié)點(diǎn)數(shù)量較少的時(shí)候各算法之間的性能表現(xiàn)差不多，這是因?yàn)槟K節(jié)點(diǎn)數(shù)量較少時(shí)，可供選擇的調(diào)度方案并不多，最佳調(diào)度與最差調(diào)度之間的差別也不大。

圖5 不同模塊節(jié)點(diǎn)數(shù)量的完成時(shí)間直方圖

系統(tǒng)環(huán)境的配置(每個(gè)模塊節(jié)點(diǎn)可以認(rèn)證的設(shè)備類型)也會(huì)對(duì)結(jié)果產(chǎn)生較大的影響。為了研究系統(tǒng)配置對(duì)認(rèn)證完成時(shí)間的影響，將設(shè)備種類設(shè)置為10，模塊節(jié)點(diǎn)數(shù)量設(shè)置為10，每個(gè)節(jié)點(diǎn)上的虛擬機(jī)設(shè)置為5。然后變化的是每類設(shè)備提供認(rèn)證服務(wù)的模塊節(jié)點(diǎn)數(shù)量，從而觀察認(rèn)證時(shí)間的變化，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 不同提供服務(wù)的模塊節(jié)點(diǎn)數(shù)量的完成時(shí)間直方圖

由圖6可以看出，隨著每個(gè)種類的設(shè)備可以在更多的模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證，認(rèn)證的完成時(shí)間也隨之遞減。這是顯然的，當(dāng)為每類設(shè)備提供認(rèn)證服務(wù)模塊節(jié)點(diǎn)數(shù)量變多后，每種設(shè)備能夠接觸到的虛擬機(jī)數(shù)量也變多了，這使得虛擬機(jī)的分配更加地靈活，而且能夠使得資源得到充分利用。

圖7探究了完成時(shí)間與設(shè)備數(shù)量的關(guān)系。實(shí)驗(yàn)中將設(shè)備的種類固定為4種，并改變每種設(shè)備的數(shù)量來探究對(duì)結(jié)果的影響。很顯然，當(dāng)設(shè)備數(shù)量增加時(shí)，需要更多的時(shí)間去進(jìn)行認(rèn)證。

圖7 不同類別設(shè)備數(shù)量的完成時(shí)間直方圖

觀察圖5可以看出，當(dāng)虛擬機(jī)的數(shù)量從5增加到6時(shí)，算法SJF和MBF的性能沒有發(fā)生變化。這是因?yàn)槟K節(jié)點(diǎn)已經(jīng)將能夠分配的虛擬機(jī)都分配了，多出的虛擬機(jī)也因?yàn)榭梢苑?wù)的設(shè)備種類限制而無法進(jìn)行分配。觀察圖6可以看出，當(dāng)模塊節(jié)點(diǎn)的數(shù)量為2時(shí)，3個(gè)算法的完成時(shí)間是相同的，這是因?yàn)樵谀K節(jié)點(diǎn)的配置時(shí)，某些種類的設(shè)備只能在某個(gè)特定的模塊節(jié)點(diǎn)上進(jìn)行認(rèn)證，所有這些設(shè)備必須進(jìn)行排隊(duì)才可以進(jìn)行認(rèn)證。

本文中還對(duì)不同算法的運(yùn)行時(shí)間進(jìn)行了實(shí)驗(yàn)。結(jié)果如圖8和圖9所示。可以看出，算法SJF和RA的運(yùn)行時(shí)間遠(yuǎn)低于MBF算法。這是因?yàn)镸BF算法需要在初始分配時(shí)，對(duì)模塊節(jié)點(diǎn)的不同排列進(jìn)行檢查，而這一操作花費(fèi)了大量的時(shí)間。在圖8中，當(dāng)設(shè)備種類的數(shù)量增加時(shí)，3個(gè)算法的運(yùn)行時(shí)間都增加了，且變化的幅度都差不多，因?yàn)殡S著設(shè)備種類的增加，每個(gè)模塊節(jié)點(diǎn)都需要對(duì)更多設(shè)備的認(rèn)證請(qǐng)求做出決策，從而導(dǎo)致時(shí)間變長(zhǎng)。在圖9中，當(dāng)模塊節(jié)點(diǎn)的數(shù)量增加時(shí)，算法MBF的運(yùn)行時(shí)間很明顯比RA和SJF增長(zhǎng)的快。如之前所說，在初始分配時(shí)，MBF需要檢查模塊節(jié)點(diǎn)的一些排列，而排列的增長(zhǎng)是與模塊節(jié)點(diǎn)的數(shù)量指數(shù)相關(guān)的。所以MBF的運(yùn)行時(shí)間也增長(zhǎng)得很快。

圖8 不同設(shè)備種類的完成時(shí)間曲線

圖9 不同模塊節(jié)點(diǎn)數(shù)量的完成時(shí)間曲線

當(dāng)所有的模塊節(jié)點(diǎn)都只有一個(gè)虛擬機(jī)的時(shí)候，算法SJF就是最優(yōu)算法。在這種情況下，CASP變成了一個(gè)簡(jiǎn)單的調(diào)度問題，此時(shí)最優(yōu)策略就是最短任務(wù)優(yōu)先，即SJF算法。

4 結(jié)論

研究了海量設(shè)備的認(rèn)證調(diào)度問題(CASP)，證明了CASP是NP完全的。提出了2近似的SJF和MBF算法，實(shí)驗(yàn)結(jié)果表明：SJF在小規(guī)模時(shí)性能接近MBF算法，在某些特殊情況下具有最優(yōu)解。