基于改進煙花算法的以太網通信鏈路調度方法

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

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

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

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

1 通信鏈路調度問題建模

1.1 系統模型的建立

為滿足數據傳輸時延的要求,本文系統模型是由1個源主機和3個目的主機組成的工業以太網網絡,針對該模型,提出如下假設：

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

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

3) 在任務開始調度前有足夠的時間對數據進行調度規劃安排,緩沖區的長度足夠大,能容納所有的傳輸序列流.

1.2 調度數學模型的建立

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

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

(1)

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

(2)

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

基于假設2)可知,數據包的發送過程滿足：

(3)

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

(4)

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

(5)

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

(6)

在時延方面,調度模型存在如下關系：

(7)

(8)

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

綜上對實時周期數據傳輸的分析,基于改進煙花算法的工業以太網通信鏈路調度方法的適應度函數可表示為

(9)

2 工業以太網通信鏈路調度算法

2.1 煙花算法

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

(10)

(11)

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

為使煙花產生的每代都是高質量的火花,需要對爆炸產生的火花數量進行設置：

(12)

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

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

ΔXi,k=Xi,k×m,

(13)

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

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

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

(14)

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

2.2 高斯變異算子的改進

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

(15)

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

2.3 選擇策略的改進

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

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

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

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

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

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

3 工業以太網調度過程

3.1 實時周期數據任務調度編碼

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

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

(16)

其中i表示實時周期中數據包的序號,τi表示任務的序列. 通過煙花算法合理安排任務調度序列,使工業以太網數據鏈路上的數據包到達時間達到最小值.

3.2 調度過程

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

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

步驟3) 計算當前位置的煙花個體及其目標函數值,并統計當前最優位置及函數值；

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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