基于改進煙花算法的以太網(wǎng)通信鏈路調(diào)度方法

王宏志,郭嫚嫚,胡黃水,武莎莎

(長春工業(yè)大學 計算機科學與工程學院,長春 130012)

近年來,隨著列車通信網(wǎng)絡結構體系的發(fā)展,軌道交通列車正向高速、穩(wěn)定、舒適化方向發(fā)展,因此對列車通信網(wǎng)絡的實時性提出了更高要求. 工業(yè)以太網(wǎng)[1]以其穩(wěn)定性、可靠性、實時性已成為工業(yè)控制網(wǎng)絡領域的研究熱點. 但目前的工業(yè)以太網(wǎng)技術均采用帶有沖突檢測的載波監(jiān)聽多路訪問(CSMA/CD)技術,沒有完備的延遲時間和通信響應,所以合理地安排數(shù)據(jù)傳輸過程中的調(diào)度問題尤為重要.

目前,智能優(yōu)化算法及其改進算法被廣泛應用于網(wǎng)絡調(diào)度中. 文獻[2]實現(xiàn)了煙花算法徑向配電網(wǎng)的爆炸過程組合優(yōu)化問題,在功率流期間生成網(wǎng)絡的適當父節(jié)點-子節(jié)點路徑,提高了配電系統(tǒng)的功率最小化和電壓分布；文獻[3]提出了一種基于差分進化算子的煙花混合優(yōu)化算法,結合差分進化運算符(突變、交叉和選擇)進行迭代次數(shù)的更新,提高了種群的多樣性,但某些質(zhì)量差的組件會導致選出較低的適應度值,影響下一代煙花個體質(zhì)量；Zheng等[4]提出了一種增強型煙花算法,解決了函數(shù)最佳值與搜索空間距離的問題,但未考慮適應度值對選擇策略的影響; 文獻[5]將改進后的增強型煙花算法應用于高速列車的實際調(diào)度中,從新的高斯變異算子----基于生物地理優(yōu)化的遷移算子(migration operator based on biogeographic optimization,BBO)以及新的選擇策略進行改進,增加了調(diào)度的多樣性,并抑制了過早收斂；Cheng等[6]將改進的具有新爆炸算子和預留策略的多目標返工算法與重新調(diào)度煙花算法相結合,以開發(fā)方案的開發(fā)成本和持續(xù)時間及魯棒性和穩(wěn)定性為目標函數(shù),提高了算法的穩(wěn)定性,但增加了算法復雜度. 本文提出一種基于改進煙花算法的實時周期消息任務調(diào)度方法(real-time scheduling algorithm based on modified coefficient of variation of fireworks algorithm,CVFWA). 仿真實驗結果表明,該算法在降低調(diào)度序列傳輸時延和收斂速度等方面均具有良好的性能.

1 通信鏈路調(diào)度問題建模

1.1 系統(tǒng)模型的建立

為滿足數(shù)據(jù)傳輸時延的要求,本文系統(tǒng)模型是由1個源主機和3個目的主機組成的工業(yè)以太網(wǎng)網(wǎng)絡,針對該模型,提出如下假設：

1) 本文的數(shù)據(jù)調(diào)度問題主要針對在源主機和目的主機之間的數(shù)據(jù)鏈路,數(shù)據(jù)類型為實時周期數(shù)據(jù);

2) 源交換機發(fā)出的數(shù)據(jù)到達過程均服從Poisson分布,終端交換機接受數(shù)據(jù)的過程也服從Poisson分布;

3) 在任務開始調(diào)度前有足夠的時間對數(shù)據(jù)進行調(diào)度規(guī)劃安排,緩沖區(qū)的長度足夠大,能容納所有的傳輸序列流.

1.2 調(diào)度數(shù)學模型的建立

針對上述模型的分析與假設,將實時周期消息[7]任務的調(diào)度轉化為數(shù)學模型,可表示為一個三元組：

DPRT={D1,D2,…,DN},i∈1,2,…,N,

(1)

τi=(Ti,Pi,deadi),i=1,2,…,N,

(2)

其中：DPRT表示實時周期數(shù)據(jù)任務的集合,由N個互相獨立的實時周期任務組成；τi表示每個實時周期任務,Ti表示當前任務的周期,Pi表示當前任務的最壞執(zhí)行時間,deadi表示當前任務的截止期.

基于假設2)可知,數(shù)據(jù)包的發(fā)送過程滿足：

(3)

鏈路傳輸速率取決于鏈路信道狀態(tài)與資源分配策略,因此需滿足：

(4)

其中:Cv(τi)表示數(shù)據(jù)鏈路的傳輸速率;θi表示保證目的主機能實現(xiàn)可靠通信的信干噪比,用公式表示為

(5)

式中sij表示為滿足數(shù)據(jù)接收端主機的通信服務質(zhì)量,在其能從源主機的發(fā)送端接收到的二進制比特流中區(qū)分出數(shù)據(jù)幀的起始與終止而對鏈路設定的信道增益,δi表示源主機端的發(fā)送功率,Ip表示接收端導致的噪聲干擾,N0表示信道中的背景噪聲.

(6)

在時延方面,調(diào)度模型存在如下關系：

(7)

(8)

其中L(τi)max表示實時周期數(shù)據(jù)中的最大數(shù)據(jù)長度,B表示被分配的帶寬.

綜上對實時周期數(shù)據(jù)傳輸?shù)姆治?基于改進煙花算法的工業(yè)以太網(wǎng)通信鏈路調(diào)度方法的適應度函數(shù)可表示為

(9)

2 工業(yè)以太網(wǎng)通信鏈路調(diào)度算法

2.1 煙花算法

煙花算法[9]是一種新型智能算法,其根據(jù)煙花爆炸擴散等現(xiàn)象類比提出. 算法主要包括以下內(nèi)容：爆炸算子、高斯變異算子、映射規(guī)則和選擇策略[10]. 對于煙花爆炸的火花數(shù)Fi和爆炸幅度Ri,計算公式如下：

(10)

(11)

其中Fi表示第i個煙花產(chǎn)生爆炸火花的數(shù)量,f表示產(chǎn)生所有爆炸火花的總個數(shù),其為一個常數(shù),Xmax表示最差的適應度值,f(Xi)表示第i個煙花的適應度值,ε是為防止分母為0設置的一個常數(shù)值,Ri表示第i個煙花產(chǎn)生爆炸幅度的范圍,R表示最大的爆炸半徑,Xmin表示最優(yōu)煙花個體產(chǎn)生的適應度值.

為使煙花產(chǎn)生的每代都是高質(zhì)量的火花,需要對爆炸產(chǎn)生的火花數(shù)量進行設置：

(12)

其中a和b是常數(shù),取值范圍為[0,1],round是取整函數(shù).

完成上述過程后,還需進行高斯變異操作[11],對第k維的任一個火花xi進行高斯變異操作,計算公式為

ΔXi,k=Xi,k×m,

(13)

其中:Xi,k表示煙花在第k維的位置矢量值; ΔXi,k表示煙花個體經(jīng)過變異后的位置矢量值;m～N(1,1),N(1,1)表示一個能使m服從的均值為1、方差為1的高斯分布.

此外,還需對爆炸后的煙花進行可行解空間的設定,以保證其上下界范圍,對于不在范圍內(nèi)的火花重新映射,計算公式為

Xi,k=XL-Bou,k+|Xi,k|%(XH-Bou,k-XL-Bou,k),

(14)

其中XH-Bou,k和XL-Bou,k分別表示第k維中煙花位置i矢量的可行解空間上下界.

2.2 高斯變異算子的改進

考慮到不同維度對變異的期望程度不同,本文在此基礎上提出一種新的高斯變異算子,通過引入變異系數(shù)描述算子的變異程度,選出變異系數(shù)最大的維度進行變異操作. 變異維度選取公式如下：

(15)

其中i表示某一維度,n表示候選煙花的數(shù)量,VC表示變異系數(shù),w表示煙花各維度的標準差,α表示煙花維度的均值. 通過上述方法選取將進行變異操作的維度,選擇變異系數(shù)最大的煙花維度進行變異操作,變異系數(shù)越大,表示離散程度越大.

2.3 選擇策略的改進

傳統(tǒng)煙花算法采用基于“精英-距離”的選擇策略[12],通過計算歐氏距離占比概率高低作為選取下一代煙花的標準. 傳統(tǒng)煙花算法性能一般,且局部搜索能力較差,盡管還有錦標賽選擇策略[13],但單純依靠該方法會使適應度值出現(xiàn)優(yōu)劣問題,兩端的適應度選擇不均衡,存在較大缺陷. 本文針對上述問題,提出一種基于中位數(shù)錦標賽的選擇策略,操作過程如下：

1) 從總體中選擇一定數(shù)量的煙花作為候選集參與下一代煙花的個體選擇,候選集設為K,個體總數(shù)為M；

2) 將每個候選集煙花個體的適應度值按升序的方式排列,取出適應度值的中位數(shù)Zn；

3) 選出中位數(shù)對應的適應度值,將候選個體分為K1和K2兩組;

4) 在3)中的兩組候選集中,每組隨機選擇M/2組候選個體,將每組中的最優(yōu)秀個體作為下一代爆炸中心.

改進后的選擇策略增加了適應度較差個體被選擇的概率,增加了種群多樣性.

3 工業(yè)以太網(wǎng)調(diào)度過程

3.1 實時周期數(shù)據(jù)任務調(diào)度編碼

為提高實時周期數(shù)據(jù)任務[14]在煙花算法下調(diào)度機制的有效性,利用離散機制進行實時周期數(shù)據(jù)任務的編碼. 待調(diào)度的任務數(shù)據(jù)表示為

Li={τ1,τ2,…,τn},i∈N,

(16)

其中i表示實時周期中數(shù)據(jù)包的序號,τi表示任務的序列. 通過煙花算法合理安排任務調(diào)度序列,使工業(yè)以太網(wǎng)數(shù)據(jù)鏈路上的數(shù)據(jù)包到達時間達到最小值.

3.2 調(diào)度過程

步驟1) 設置煙花算法中的參數(shù),包括任務數(shù)量N、待調(diào)度的任務數(shù)據(jù)Li、爆炸火花數(shù)量Fi、爆炸幅度Ri和最大迭代次數(shù)I等；

步驟2) 根據(jù)3.1中的任務調(diào)度編碼方法,初始化煙花位置并將煙花位置轉化成實時周期數(shù)據(jù)的調(diào)度序列；

步驟3) 計算當前位置的煙花個體及其目標函數(shù)值,并統(tǒng)計當前最優(yōu)位置及函數(shù)值；

步驟4) 產(chǎn)生爆炸火花,并根據(jù)式(10)～(12)計算其爆炸數(shù)目和爆炸范圍；

步驟5) 產(chǎn)生高斯變異火花,先根據(jù)2.2的改進方法計算并選取變異維度,再根據(jù)式(13)進行變異操作,按式(14)對超出范圍的煙花重新映射到范圍內(nèi)；

步驟6) 根據(jù)2.3提出的方法計算中位數(shù)錦標賽選擇策略下的下一代煙花個體,檢驗是否達到最大迭代次數(shù),若未達到則返回步驟3),令iter=iter+1,直至找到最優(yōu)煙花序列,算法結束,輸出最優(yōu)函數(shù)值.

改進煙花算法流程如圖1所示.

圖1 改進煙花算法流程Fig.1 Flow chart of improved fireworks algorithm

4 仿真分析

圖2 不同算法調(diào)度序列適應度與迭代次數(shù)的關系Fig.2 Relationship between scheduling sequence fitness and number of iterations of different algorithms

在MATLAB 2016a環(huán)境下,搭建通信鏈路調(diào)度模型,設從源主機到目的主機的通信鏈路中,煙花群規(guī)模為20,維度為10,爆炸火花個數(shù)為40,爆炸半徑為40 m,爆炸數(shù)目限制因子a=0.3,b=0.6,變異火花數(shù)為10個,變量上下界為[-10,10],最大迭代次數(shù)為50次,調(diào)度任務數(shù)量為10,源主機的信干噪比需求為8 dB. 仿真實驗中,本文將煙花算法(FWA)和基于錦標賽選擇策略的煙花算法(LoTFWA)與改進后的煙花算法(CVFWA)進行性能比較.

圖2為不同算法獲得調(diào)度序列的適應度值與迭代次數(shù)的關系. 由圖2可見,相比于煙花算法(FWA)和基于錦標賽選擇策略的煙花算法(LoTFWA),本文的改進煙花算法(CVFWA)收斂性更優(yōu),有效降低了網(wǎng)絡中的傳輸時延. 圖3為不同算法數(shù)據(jù)鏈路的傳輸速率與迭代次數(shù)的關系. 由圖3可見,在保障鏈路數(shù)據(jù)正常通信的情況下,CVFWA算法相比于FWA算法和LoTFWA算法傳輸速率更快,有效提高了鏈路數(shù)據(jù)通信的實時性能. 圖4為由不同算法獲得源主機的信干噪比與迭代次數(shù)的關系. 由圖4可見,FWA算法的信干噪比不能滿足本文所設定的信干噪比值,所以源主機與目的主機之間的鏈路無法實現(xiàn)數(shù)據(jù)通信. LoTFWA算法雖能滿足設定要求,但沒有CVFWA算法效果好,因此,CVFWA算法更能滿足本文設定的信干噪比參數(shù)的要求,實現(xiàn)節(jié)點之間的可靠通信.

圖3 不同算法鏈路傳輸速率與迭代次數(shù)的關系Fig.3 Relationship between link transmission rate and number of iterations of different algorithms

圖4 不同算法源主機信干噪比與迭代次數(shù)的關系Fig.4 Relationship between SINR of source host and number of iterations of different algorithms

綜上所述,本文在傳統(tǒng)煙花算法的基礎上提出了一種基于改進煙花算法的以太網(wǎng)通信鏈路調(diào)度方法,增加了對變異維度的選取,同時將選擇策略改進為中位數(shù)錦標賽選擇策略. 仿真實驗結果表明,在保障鏈路數(shù)據(jù)正常通信的情況下,CVFWA算法不僅有效降低了節(jié)點間鏈路數(shù)據(jù)的傳輸時間,而且加快了節(jié)點間鏈路數(shù)據(jù)的傳輸速率,提高了節(jié)點間鏈路數(shù)據(jù)通信的可靠性,在一定程度上保持了鏈路通信的實時性.