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

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

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

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

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

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

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

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

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

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

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

1.2 問題描述

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

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

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

(1)

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

(2)

(3)

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

(4)

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

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

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

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

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

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

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

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

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

2.2 算法設(shè)計

2.2.1貪心算法

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

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

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

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

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

接下來將證明在圖1的場景下，SJF算法能夠達到2近似。

圖1 CASP的特殊場景示意圖

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

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

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

2.2.2啟發(fā)式算法

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

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

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

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

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

3 實驗驗證與分析

3.1 實驗設(shè)置

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

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

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

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

3.2 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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