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

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,長(zhǎng)春 130012)

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

(8)

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

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

(9)

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

2.1 煙花算法

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

(10)

(11)

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

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

(12)

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

完成上述過(guò)程后,還需進(jìn)行高斯變異操作[11],對(duì)第k維的任一個(gè)火花xi進(jìn)行高斯變異操作,計(jì)算公式為

ΔXi,k=Xi,k×m,

(13)

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

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

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

(14)

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

2.2 高斯變異算子的改進(jìn)

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

(15)

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

2.3 選擇策略的改進(jìn)

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

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

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

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

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

改進(jìn)后的選擇策略增加了適應(yīng)度較差個(gè)體被選擇的概率,增加了種群多樣性.

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

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

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

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

(16)

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

3.2 調(diào)度過(guò)程

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

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

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

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

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

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

改進(jìn)煙花算法流程如圖1所示.

圖1 改進(jìn)煙花算法流程Fig.1 Flow chart of improved fireworks algorithm

4 仿真分析

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

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

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

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

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

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