李旭杰，臧振楠，孫 穎，劉春燕，黃鳳辰

(1.南通河海大學(xué)海洋與近海工程研究院，江蘇 南通 226300；2.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)

0 引 言

泵閘站工程是防洪排澇及配水的基礎(chǔ)性工程，通過將物聯(lián)網(wǎng)技術(shù)、計(jì)算機(jī)技術(shù)、通信技術(shù)與自動(dòng)控制技術(shù)有機(jī)結(jié)合形成泵站智能監(jiān)控系統(tǒng)[1]，實(shí)現(xiàn)泵站實(shí)時(shí)智能監(jiān)測(cè)、控制及調(diào)度，可實(shí)現(xiàn)無(wú)人值守或少人值守，確保泵閘站安全、可靠、高效地運(yùn)行，有力提升水資源的高效利用。

但是，目前泵閘站型號(hào)多種多樣，測(cè)量設(shè)備的測(cè)量方式差異等，從而造成泵站(群)運(yùn)行監(jiān)控?cái)?shù)據(jù)的取值頻率、尺度和時(shí)間上存在較大差異。泵站自動(dòng)化監(jiān)控系統(tǒng)收集了大量泵站運(yùn)行時(shí)的工況、測(cè)控信息，各泵站平均采集指標(biāo)多達(dá)上千種。除少量數(shù)據(jù)以非實(shí)時(shí)方式被同步至管理調(diào)度系統(tǒng)外，大量數(shù)據(jù)只能保留在泵站現(xiàn)場(chǎng)，無(wú)法得到有效利用。隨著大量傳感器在泵閘站的部署及應(yīng)用，大量實(shí)時(shí)及非實(shí)時(shí)數(shù)據(jù)呈爆發(fā)性增長(zhǎng)，若采用傳統(tǒng)的端-云(服務(wù)器)信息傳輸及處理體系則易造成網(wǎng)絡(luò)堵塞及時(shí)延激增，甚至信息系統(tǒng)崩潰的危情。因此，如何設(shè)計(jì)優(yōu)化的信息傳輸體系及任務(wù)分發(fā)機(jī)制，及時(shí)處理泵閘站的實(shí)時(shí)、非實(shí)時(shí)等大量異構(gòu)數(shù)據(jù)則尤顯重要。邊緣計(jì)算可將數(shù)據(jù)在終端或邊緣端進(jìn)行計(jì)算處理，相比傳統(tǒng)的服務(wù)器端處理模式，可有效降低時(shí)延，提升系統(tǒng)效率。

目前，已有不少學(xué)者對(duì)邊緣架構(gòu)的處理模式進(jìn)行了研究。文獻(xiàn)[2]將霧計(jì)算網(wǎng)絡(luò)架構(gòu)作為云計(jì)算網(wǎng)絡(luò)架構(gòu)的擴(kuò)展，將云計(jì)算的計(jì)算、存儲(chǔ)等各項(xiàng)功能從云數(shù)據(jù)中心轉(zhuǎn)移到更加貼近終端用戶的網(wǎng)絡(luò)邊緣，從而有效降低了數(shù)據(jù)的傳輸時(shí)延。文獻(xiàn)[3]在更貼近終端用戶的網(wǎng)絡(luò)邊緣部署了大量的霧節(jié)點(diǎn)，其具有通信、計(jì)算、緩存、控制等能力；通過任務(wù)調(diào)度技術(shù)將任務(wù)分配給不同的邊緣服務(wù)器或霧節(jié)點(diǎn)進(jìn)行處理，可以有效縮短任務(wù)的響應(yīng)時(shí)延。文獻(xiàn)[4]中，作者首先介紹了一種支持多無(wú)人機(jī)的移動(dòng)邊緣計(jì)算系統(tǒng)，其中部署的無(wú)人機(jī)作為地面大規(guī)模終端所產(chǎn)生的任務(wù)卸載的計(jì)算服務(wù)器，然后提出了一種兩層優(yōu)化的策略來(lái)優(yōu)化無(wú)人機(jī)的數(shù)量和任務(wù)調(diào)度方案從而最小化系統(tǒng)的能耗。文獻(xiàn)[5]面向移動(dòng)邊緣計(jì)算系統(tǒng)，針對(duì)無(wú)人機(jī)電池容量有限的問題提出了一種以最小化系統(tǒng)能耗的任務(wù)調(diào)度方法。文獻(xiàn)[6]中，作者針對(duì)多無(wú)人機(jī)輔助的移動(dòng)邊緣計(jì)算系統(tǒng)，對(duì)計(jì)算資源分配、無(wú)人機(jī)的軌跡進(jìn)行了優(yōu)化，從而最小化系統(tǒng)中任務(wù)的完成時(shí)間。

綜上所述，目前較少對(duì)泵閘站數(shù)據(jù)處理任務(wù)的分發(fā)進(jìn)行分析及優(yōu)化。因此，本文針對(duì)泵閘站系統(tǒng)，研究設(shè)計(jì)一種基于邊緣計(jì)算架構(gòu)的泵閘站數(shù)據(jù)處理分發(fā)機(jī)制，對(duì)需要及時(shí)處理的任務(wù)在終端上即時(shí)處理，或?qū)⑷蝿?wù)遷移至邊緣節(jié)點(diǎn)進(jìn)行處理，從而整體提升系統(tǒng)性能。

1 系統(tǒng)架構(gòu)模型

1.1 通信模型

上述系統(tǒng)架構(gòu)模型中，泵閘站傳感器與泵閘邊緣節(jié)點(diǎn)的信道可建模為自由空間傳播信道模型。泵閘站傳感器與泵閘邊緣節(jié)點(diǎn)之間的信道增益可以表示為

(1)

(2)

(3)

(4)

式中：B為信道帶寬；Pi為泵閘站傳感器節(jié)點(diǎn)的發(fā)射功率；n0為噪聲功率譜密度。

1.2 計(jì)算模型

在該系統(tǒng)架構(gòu)模型中，泵閘站傳感器的任務(wù)處理方式有兩種：本地計(jì)算和完全分發(fā)給泵閘邊緣節(jié)點(diǎn)計(jì)算。具體計(jì)算模型如下：

(1)本地計(jì)算

當(dāng)泵閘站傳感器Si在本地計(jì)算其任務(wù)Taski時(shí)，將Si的CPU的計(jì)算能力表示為fi，則本地計(jì)算任務(wù)的處理時(shí)延表示為[7]

(5)

(2)泵閘邊緣節(jié)點(diǎn)

當(dāng)泵閘站傳感器Si與泵閘邊緣節(jié)點(diǎn)Ej之間的距離滿足式(3)并根據(jù)任務(wù)分發(fā)決策將其任務(wù)Taski分發(fā)到泵閘邊緣節(jié)點(diǎn)上計(jì)算時(shí)，Taski的傳輸時(shí)延可以表示為

(6)

Taski的計(jì)算時(shí)延可以表示為

(7)

式中：fi,j表示泵閘邊緣節(jié)點(diǎn)Ej的計(jì)算服務(wù)器分配給任務(wù)Taski的計(jì)算資源。

在大多數(shù)實(shí)際場(chǎng)景中，任務(wù)計(jì)算結(jié)果的數(shù)據(jù)包比特?cái)?shù)較小，與很多研究類似，本文忽略計(jì)算結(jié)果的返回時(shí)延。任務(wù)Taski的處理時(shí)延記作傳輸時(shí)延和計(jì)算時(shí)延之和[8]：

(8)

通過優(yōu)化本地的fi以及邊緣端的fi,j可取得更好的時(shí)延性能。

2 問題建模與優(yōu)化指標(biāo)

根據(jù)上述系統(tǒng)架構(gòu)模型的分析，本小節(jié)進(jìn)一步對(duì)問題進(jìn)行描述并分析優(yōu)化的性能指標(biāo)。

在基于邊緣計(jì)算架構(gòu)的泵閘站數(shù)據(jù)處理任務(wù)分發(fā)模型中，多個(gè)泵閘站傳感器節(jié)點(diǎn)有計(jì)算任務(wù)需求，這些泵閘站傳感器節(jié)點(diǎn)產(chǎn)生的任務(wù)大小通常是不同的。同時(shí)，泵閘站傳感器節(jié)點(diǎn)可能位于多個(gè)泵閘邊緣節(jié)點(diǎn)的通信覆蓋范圍內(nèi)。因此，根據(jù)任務(wù)Taski是否在本地計(jì)算或者任務(wù)Taski是否分發(fā)到泵閘邊緣節(jié)點(diǎn)Ej計(jì)算，定義二進(jìn)制決策變量μi,0和μi,j。具體定義如下：

(9a)

(9b)

式中：μi,0表示任務(wù)Taski是否在本地計(jì)算；μi,j表示是否將任務(wù)Taski分發(fā)到泵閘邊緣節(jié)點(diǎn)Ej計(jì)算。

根據(jù)上述分析，泵閘站傳感器Si產(chǎn)生的任務(wù)Taski的處理時(shí)延可以表示為

(10)

則系統(tǒng)模型中所有泵閘站傳感器產(chǎn)生的任務(wù)的處理時(shí)延之和，即所有任務(wù)處理總時(shí)延為

(11)

由上可見，如何選擇μi,j則直接影響系統(tǒng)的分發(fā)性能。為滿足泵閘站傳感器對(duì)時(shí)延敏感型任務(wù)的計(jì)算需求，本文最小化系統(tǒng)中所有任務(wù)處理總時(shí)延，并根據(jù)上述分析將優(yōu)化問題建模如下：

P1:minF(μi,0,μi,j,fi,j)

(12a)

(12b)

(12c)

(12d)

(12e)

根據(jù)問題建模以及對(duì)相關(guān)約束條件的分析，μi,0是整數(shù)變量，而fi,j是線性變量，因此目標(biāo)函數(shù)是一個(gè)混合整數(shù)非線性函數(shù)。

3 泵閘站數(shù)據(jù)處理任務(wù)分發(fā)算法

上一小節(jié)對(duì)系統(tǒng)模型進(jìn)行了詳細(xì)描述并提出了本文的性能優(yōu)化指標(biāo)以及相應(yīng)的目標(biāo)函數(shù)優(yōu)化問題。由于問題P1中約束C2用于約束整數(shù)變量μi,0和μi,j，約束C3和C4用于約束線性變量fi,j，它們之間是相互解耦的，因此，本小節(jié)將優(yōu)化問題P1轉(zhuǎn)化為兩個(gè)子問題分別進(jìn)行求解。其中，當(dāng)泵閘站傳感器節(jié)點(diǎn)產(chǎn)生的任務(wù)的分發(fā)決策確定時(shí)，將原問題轉(zhuǎn)化為泵閘邊緣節(jié)點(diǎn)服務(wù)器計(jì)算資源分配子問題，可證該子問題是一個(gè)典型的凸優(yōu)化問題。當(dāng)最優(yōu)的計(jì)算資源分配策略確定時(shí)，將原問題轉(zhuǎn)化為計(jì)算任務(wù)分發(fā)子問題，該子問題是一個(gè)0-1整數(shù)規(guī)劃問題。針對(duì)子問題1，其含有線性約束，因此可利用拉格朗日乘子法將有限制的凸優(yōu)化問題轉(zhuǎn)化為沒有限制的問題來(lái)求解。針對(duì)子問題2，其為典型的組合優(yōu)化問題，其變量空間的不連續(xù)性導(dǎo)致難以用傳統(tǒng)的優(yōu)化方法來(lái)進(jìn)行求解，因此利用樽海鞘群算法(Salp Swarm Algorithm，SSA)來(lái)進(jìn)行求解。

3.1 基于拉格朗日乘子法的計(jì)算資源分配

拉格朗日乘子法通過使用拉格朗日乘子將相關(guān)的約束條件與原目標(biāo)函數(shù)構(gòu)成一個(gè)新的拉格朗日函數(shù)，將有約束的最優(yōu)化問題轉(zhuǎn)化為一個(gè)無(wú)約束的極值問題，使得目標(biāo)函數(shù)保持線性關(guān)系并進(jìn)行求解[9]。針對(duì)上述分析的計(jì)算資源分配子問題，其滿足拉格朗日乘子法的使用條件，因此可以使用該方法進(jìn)行求解。

在上一節(jié)分析的系統(tǒng)模型中，泵閘邊緣節(jié)點(diǎn)僅為確定分發(fā)到其上處理的計(jì)算任務(wù)分配計(jì)算資源，因此，定義一個(gè)集合H表示確定分發(fā)到泵閘邊緣節(jié)點(diǎn)Ej的任務(wù)集合，記作H={i|μi,j=1}。由此，將計(jì)算資源分配子問題P2的目標(biāo)函數(shù)表示為

(13)

此外，計(jì)算資源子問題P2可以建模為

P2:minT(fi,j)

(14a)

(14b)

(14c)

定理1：計(jì)算資源分配子問題P2是一個(gè)凸優(yōu)化問題。

證明：首先，使用海塞矩陣(Hessian Matrix)對(duì)目標(biāo)函數(shù)求二階導(dǎo)數(shù)。海塞矩陣的每一項(xiàng)可以具體表示為

(15)

由于目標(biāo)函數(shù)T(fi,j)的約束C3和C4是關(guān)于fi,j的線性約束，即目標(biāo)函數(shù)T(fi,j)的域是凸的，因此，目標(biāo)函數(shù)T(fi,j)是關(guān)于計(jì)算資源fi,j的凸函數(shù)，計(jì)算資源分配子問題P2是一個(gè)凸優(yōu)化問題。

根據(jù)凸優(yōu)化相關(guān)理論，使用拉格朗日乘子法和KKT(Karush-Kuhn-Tucher)條件以求得子問題P2的最優(yōu)解。

引入拉格朗日乘子λ且λ≥0，根據(jù)式(14)凸優(yōu)化問題構(gòu)建目標(biāo)函數(shù)T(fi,j)的拉格朗日函數(shù)：

(16)

(17)

通過求解式(17)，可以得到最優(yōu)計(jì)算資源分配策略

(18)

將式(18)代入式(13)中，可以得到計(jì)算資源分配子問題P2目標(biāo)函數(shù)T(fi,j)的最優(yōu)值為

(19)

3.2 基于樽海鞘群算法的泵閘站數(shù)據(jù)處理任務(wù)分發(fā)算法

樽海鞘群算法是一種新型的啟發(fā)式智能優(yōu)化算法，于2017年由Mirjalili等[10]提出。為模擬樽海鞘鏈的覓食行為，首先按照樽海鞘在種群中的位置，將其分為兩種類型，將位于樽海鞘鏈最前端的樽海鞘稱作領(lǐng)導(dǎo)者，將其他個(gè)體稱作追隨者。處于樽海鞘鏈最前端的領(lǐng)導(dǎo)者對(duì)于食物源的位置有著最優(yōu)的判斷，因此領(lǐng)導(dǎo)者能夠朝著食物源的正確方向移動(dòng)并指導(dǎo)緊隨其后的追隨者移動(dòng)。在基本的樽海鞘群算法中，只有一個(gè)領(lǐng)導(dǎo)者，當(dāng)解決的問題存在大量局部最優(yōu)解時(shí)，算法容易陷入局部最優(yōu)解，可將領(lǐng)導(dǎo)者的數(shù)量設(shè)置為種群數(shù)量的一半，從而增強(qiáng)算法的局部開發(fā)能力[11]。

樽海鞘群算法的具體流程如圖1所示。

圖1 樽海鞘群算法流程圖

在樽海鞘群算法的搜索空間中，定義矢量X表示個(gè)體數(shù)為NP的樽海鞘種群的位置：

(20)

根據(jù)3.1小節(jié)的分析與討論，確定了在泵閘邊緣節(jié)點(diǎn)進(jìn)行計(jì)算的任務(wù)分配到的最佳計(jì)算資源的封閉形式解。將最優(yōu)的計(jì)算資源分配結(jié)果(式(18))代入原始問題P1中，可以得到

(21)

原始問題P1轉(zhuǎn)變?yōu)殛P(guān)于μi,0和μi,j的分發(fā)決策的0-1整數(shù)規(guī)劃問題。因此，可以將計(jì)算任務(wù)分發(fā)子問題建模為

P3:minU(μi,0,μi,j)

(22a)

(22b)

(22c)

計(jì)算任務(wù)分發(fā)子問題P3是組合優(yōu)化問題中的NP-hard問題，可以使用前面介紹的樽海鞘群算法通過搜索和迭代進(jìn)行求解。本文所提出的基于樽海鞘群算法的泵閘站任務(wù)分發(fā)算法詳細(xì)實(shí)現(xiàn)步驟如下：

(1)種群編碼及初始化

本文將泵閘站任務(wù)分發(fā)問題建模為整數(shù)規(guī)劃問題，為使得樽海鞘群算法能夠應(yīng)用于解決多任務(wù)分發(fā)問題，需要建立以下映射關(guān)系：以樽海鞘種群中個(gè)體的位置代表任務(wù)分發(fā)決策，將尋找最優(yōu)任務(wù)分發(fā)決策的過程轉(zhuǎn)化為樽海鞘群算法覓食尋優(yōu)，尋找食物源的過程，因此需對(duì)樽海鞘群算法進(jìn)行離散處理。

(23)

Xi=(1,3,0,2,0,3,4,1,2) 。

(24)

上式表示9個(gè)泵閘站傳感器和4個(gè)泵閘邊緣節(jié)點(diǎn)場(chǎng)景下的多任務(wù)分發(fā)問題的一個(gè)可行的解決方案，其中，行向量中的位置表示泵閘站傳感器的編號(hào)，對(duì)應(yīng)的值表示對(duì)應(yīng)泵閘站傳感器的分發(fā)決策。對(duì)應(yīng)的分發(fā)策略為Task3和Task5在本地計(jì)算，Task1和Task8分發(fā)給泵閘邊緣節(jié)點(diǎn)E1計(jì)算，Task4和Task9分發(fā)給泵閘邊緣節(jié)點(diǎn)E2計(jì)算，Task2和Task6分發(fā)給泵閘邊緣節(jié)點(diǎn)E3計(jì)算，Task7分發(fā)給泵閘邊緣節(jié)點(diǎn)E4計(jì)算。

(2)食物源位置初始化

本文以優(yōu)化系統(tǒng)中任務(wù)處理總時(shí)延為目標(biāo)，因此使用公式(21)作為樽海鞘群算法的適應(yīng)度函數(shù)。根據(jù)種群初始化結(jié)果，計(jì)算所有個(gè)體的適應(yīng)度函數(shù)值，選取適應(yīng)度函數(shù)值最優(yōu)的個(gè)體的位置，并將其標(biāo)記為食物源的位置，記為F=(F1,…,Fm,…,FM)，F(xiàn)即為當(dāng)前種群的全局最優(yōu)解。

(3)種群位置更新

樽海鞘群算法在每次迭代過程中，種群中的每個(gè)個(gè)體通過跟隨全局最優(yōu)或其他同伴的位置來(lái)更新自身的位置，具體表現(xiàn)為兩種不同的位置更新方式，即領(lǐng)導(dǎo)者位置更新方式和追隨者位置更新方式[12]。傳統(tǒng)的樽海鞘群算法只有一個(gè)領(lǐng)導(dǎo)者，這種機(jī)制會(huì)增大算法陷入局部最優(yōu)解的概率。因此，將種群中的前NP/2個(gè)個(gè)體均按照領(lǐng)導(dǎo)者的方式對(duì)其位置進(jìn)行更新，種群中的后NP/2個(gè)個(gè)體的位置按照追隨者的方式更新，并分別進(jìn)行離散處理，從而增強(qiáng)算法的局部探索能力。具體地，對(duì)領(lǐng)導(dǎo)者位置更新進(jìn)行離散處理，種群中前NP/2個(gè)個(gè)體Xi,i>NP/2的位置更新如下：

(25)

(26)

式中：l為當(dāng)前的迭代次數(shù)；L為最大的迭代次數(shù)。

對(duì)追隨者位置更新進(jìn)行離散處理，種群中后NP/2個(gè)個(gè)體Xi,i>NP/2的位置更新如下：

(27)

(4)種群位置修正

(28)

式中：%表示取余。

此外，由于仍需要考慮泵閘邊緣節(jié)點(diǎn)的通信覆蓋約束，如公式(3)所示，因此修正結(jié)果首先需要判斷是否滿足通信覆蓋約束，若不滿足，則在該修正值的基礎(chǔ)上累加1，直至滿足約束條件位置。至此，得到新一代的樽海鞘種群。

(5)食物源位置更新

對(duì)于新種群中的每個(gè)個(gè)體，計(jì)算其適應(yīng)度函數(shù)值，找出當(dāng)前適應(yīng)度函數(shù)值最優(yōu)的個(gè)體，并將其與食物源位置相比較。如果優(yōu)于F，則將原來(lái)的食物源位置更新為此個(gè)體的位置，完成全局最優(yōu)解的更新；反之不更新，繼續(xù)更新種群位置，進(jìn)入下一次迭代。

綜上所述，基于樽海鞘群算法的泵閘站任務(wù)分發(fā)算法具體步驟歸納如下：

Step1 初始化參數(shù)：種群大小NP，泵閘站傳感器數(shù)量M，最大迭代次數(shù)L，上邊界ub，下邊界lb，樽海鞘種群位置X，等。

Step2 根據(jù)公式(21)計(jì)算所有個(gè)體的適應(yīng)度函數(shù)值，并按照適應(yīng)度值排序，找到當(dāng)前種群最優(yōu)個(gè)體，記為食物源F。

Step3 根據(jù)公式(26)更新c1，在區(qū)間[0,1]內(nèi)隨機(jī)生成c2、c3。

Step4 如果i≤NP/2，根據(jù)公式(25)更新領(lǐng)導(dǎo)者位置。

Step5 如果i>NP/2，根據(jù)公式(27)更新追隨者位置。

Step6 根據(jù)公式(28)進(jìn)行位置修正。

Step7 計(jì)算種群個(gè)體的適應(yīng)度函數(shù)值，并更新食物源位置。

Step8 若達(dá)到設(shè)定迭代次數(shù)L，結(jié)束算法，返回最優(yōu)分發(fā)策略；若否，則返回Step 3。

Step9 結(jié)束。

4 仿真分析

4.1 仿真場(chǎng)景與參數(shù)設(shè)定

為驗(yàn)證樽海鞘群算法在解決泵閘站任務(wù)分發(fā)性能優(yōu)化問題時(shí)的合理性與有效性，使用Matlab仿真平臺(tái)對(duì)系統(tǒng)模型進(jìn)行模擬，并對(duì)實(shí)驗(yàn)結(jié)果展開分析[13-14]。具體參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置

4.2 結(jié)果分析

圖2描述了不同算法下隨著迭代次數(shù)的增加，最佳任務(wù)處理總時(shí)延的變化情況。實(shí)驗(yàn)結(jié)果表明，樽海鞘群算法不僅收斂速度最快，并且性能表現(xiàn)最優(yōu)。在收斂速度方面，樽海鞘群算法在第21代就開始收斂，而遺傳算法在第28代開始收斂到一個(gè)可行解。在性能表現(xiàn)方面，遺傳算法收斂到的最佳任務(wù)處理總時(shí)延比樽海鞘群算法高，隨機(jī)算法性能表現(xiàn)最差。樽海鞘群算法中由于種群中存在領(lǐng)導(dǎo)者，領(lǐng)導(dǎo)者在全局范圍內(nèi)進(jìn)行尋優(yōu)，算法在剛開始迭代時(shí)就在靠近最優(yōu)解的方向?qū)?yōu)，因此樽海鞘群算法的收斂速度更快。該結(jié)果證明了樽海鞘群算法在全局搜索能力和尋優(yōu)速度方面的優(yōu)越性。

(a)Di∈[10,500]×103 b,Ci∈[20,1 000]×106 cycle

(b)Di∈[10,500]b,Ci∈[20,1 000]×103 cycle圖2 不同算法下的任務(wù)處理總時(shí)延

為提高實(shí)驗(yàn)結(jié)果的可靠性，增加了蒙特卡洛仿真實(shí)驗(yàn)次數(shù)并進(jìn)行統(tǒng)計(jì)，圖3描述了不同算法下最低任務(wù)處理總時(shí)延的累積分布函數(shù)曲線(Cumulative Distribution Function,CDF)曲線，展示了最低任務(wù)處理總時(shí)延的分布情況。由于每次仿真時(shí)泵閘站傳感器產(chǎn)生的任務(wù)的數(shù)據(jù)量大小都會(huì)重新初始化，同時(shí)泵閘邊緣節(jié)點(diǎn)相對(duì)于泵閘站傳感器的分布具有隨機(jī)性，因此最低任務(wù)處理總時(shí)延在一定范圍內(nèi)波動(dòng)。從圖3中CDF曲線的走勢(shì)可以看出，隨機(jī)算法的性能最劣，基于樽海鞘群算法的性能最優(yōu)。在樽海鞘群算法下，系統(tǒng)中任務(wù)處理總時(shí)延低于45 s的概率為0.76，而遺傳算法和隨機(jī)算法下相應(yīng)的概率分別只有0.67和0.42。該實(shí)驗(yàn)結(jié)果進(jìn)一步體現(xiàn)了樽海鞘群算法可以有效提高時(shí)延敏感型任務(wù)的處理性能。

(a)Di∈[10,500]×103 b,Ci∈[20,1 000]×106 cycle

(b)Di∈[10,500]b,Ci∈[20,1 000]×103 cycle圖3 不同算法下最佳任務(wù)處理總時(shí)延的CDF曲線

圖4給出了在樽海鞘群算法、遺傳算法和隨機(jī)算法三種不同算法下，優(yōu)化所得的最低任務(wù)處理總時(shí)延與泵閘站傳感器數(shù)量的變化情況。從圖中可以直觀地看出，在泵閘站傳感器數(shù)量較少時(shí)，樽海鞘群算法和另外兩種算法的最低任務(wù)處理總時(shí)延仿真結(jié)果差異并不明顯。隨著泵閘站傳感器數(shù)量的增加，三種算法下的系統(tǒng)中所有任務(wù)處理總時(shí)延呈上升趨勢(shì)。在泵閘站傳感器數(shù)量大于20時(shí)，樽海鞘群算法優(yōu)化所得的系統(tǒng)中所有任務(wù)處理總時(shí)延明顯低于遺傳算法和隨機(jī)算法所得到的所有任務(wù)處理總時(shí)延；當(dāng)泵閘站傳感器數(shù)量大于100時(shí)，樽海鞘群算法下得到最低任務(wù)處理總時(shí)延依舊是最優(yōu)的，但三種算法下的最低任務(wù)處理總時(shí)延差異較小。這是由于泵閘站傳感器較多時(shí)，網(wǎng)絡(luò)中泵閘站傳感器和泵閘邊緣節(jié)點(diǎn)資源有限，不能滿足大規(guī)模泵閘站傳感器的計(jì)算需求。

圖4 不同算法下最佳任務(wù)處理總時(shí)延與泵閘站傳感器節(jié)點(diǎn)數(shù)量的關(guān)系

為了驗(yàn)證基于拉格朗日乘子法的計(jì)算資源分配的優(yōu)越性，圖5展示了平均資源分配和最優(yōu)資源分配下的系統(tǒng)中所有任務(wù)處理總時(shí)延，分別對(duì)比了隨機(jī)算法、遺傳算法和樽海鞘群算法下的兩種計(jì)算資源分配情況。從仿真結(jié)果可以看出，隨著泵閘站傳感器數(shù)量的增多，兩種資源分配方案下得到的任務(wù)處理總時(shí)延也隨之增加。此外，對(duì)于相同數(shù)量的泵閘站傳感器，三種算法下的基于拉格朗日乘子法的最優(yōu)資源分配得到的任務(wù)處理總時(shí)延總是低于平均資源分配，進(jìn)一步體現(xiàn)了基于拉格朗日乘子法的最優(yōu)資源分配在所研究問題中的重要作用。

圖5 不同資源分配方法下的任務(wù)處理總時(shí)延

圖6描述了在終端節(jié)點(diǎn)數(shù)量從10增加到50時(shí)，任務(wù)全隨機(jī)卸載和平均資源分配、樽海鞘群卸載和平均資源分配、樽海鞘群卸載和拉格朗日資源分配等幾種算法的系統(tǒng)任務(wù)處理總時(shí)延。從圖中可見，任務(wù)全隨機(jī)卸載和平均資源分配的任務(wù)處理總時(shí)延最高，本文所提的樽海鞘群卸載和拉格朗日資源分配算法的任務(wù)處理總時(shí)延最低。本文所提算法比任務(wù)全隨機(jī)卸載和平均資源分配算法可以降低76.9%的任務(wù)處理時(shí)延，比樽海鞘群卸載和平均資源分配算法降低了29.2%的任務(wù)處理時(shí)延。這是由于任務(wù)全隨機(jī)卸載和平均資源分配算法沒有對(duì)邊緣節(jié)點(diǎn)的計(jì)算資源進(jìn)行有效的利用，所以性能最劣。樽海鞘群卸載和平均資源分配算法雖然對(duì)卸載策略進(jìn)行了優(yōu)化但對(duì)平均資源的分配沒有優(yōu)化，其性能也較差。樽海鞘群卸載和拉格朗日資源分配對(duì)本地節(jié)點(diǎn)、邊緣節(jié)點(diǎn)的計(jì)算資源進(jìn)行了最優(yōu)的分配，有效降低了任務(wù)處理總時(shí)延。

圖6 不同任務(wù)卸載與資源分配算法下的任務(wù)處理總時(shí)延

5 結(jié) 論

本文針對(duì)泵閘站數(shù)據(jù)處理任務(wù)分發(fā)問題，將其建模為混合整數(shù)非線性規(guī)劃問題。為求解該問題，將其解耦為計(jì)算資源分配子問題和任務(wù)分發(fā)子問題，然后利用拉格朗日乘子法對(duì)計(jì)算資源分配子問題進(jìn)行求解計(jì)算，利用樽海鞘群算法對(duì)任務(wù)分發(fā)子問題進(jìn)行求解計(jì)算。通過不斷迭代交替求解，得到最佳的計(jì)算資源分配和任務(wù)分發(fā)策略。仿真結(jié)果表明，本文所提算法能夠有效降低系統(tǒng)中所有任務(wù)處理的總時(shí)延，從而保障了泵閘站傳感器時(shí)延敏感型任務(wù)的處理質(zhì)量。