基于改進螢火蟲算法的RapidIO路由選擇策略

殷從月，張興明，任權，魏帥

?

基于改進螢火蟲算法的RapidIO路由選擇策略

殷從月，張興明，任權，魏帥

（國家數字交換系統工程技術研究中心，河南 鄭州 450002）

針對RapidIO網絡QoS路由選擇問題，提出一種基于改進螢火蟲算法的RapidIO路由選擇策略。首先，利用高斯變異和存儲機制對傳統螢火蟲算法進行優化，高斯變異可以有效控制算法搜索空間中解的散射程度，使算法避免陷入局部最優，存儲機制有利于評估并存儲每只螢火蟲的歷史狀態，防止信息丟失。然后，將改進后的螢火蟲算法與實際RapidIO網絡QoS問題相結合，選擇出最終的最佳路由策略。實驗結果表明，在所模擬的RapidIO測試網絡中，改進后的螢火蟲算法時延為42 ms，時延抖動為8 ms，代價最低為64 ms，共需要迭代的次數為8，相較于其他算法曲線更加穩定，更能快速找到最優解，表現出的性能最優，有效解決了RapidIO網絡QoS路由選擇問題。

RapidIO；螢火蟲算法；高斯變異；存儲機制；服務質量

1 引言

隨著嵌入式系統互聯技術的不斷發展，PCI Express、InfiniBand、RapidIO、HyperTransPort等高性能I/O互聯技術的出現使信號處理和數據傳輸的效率越來越高[1]。其中，RapidIO總線技術支持多種拓撲結構，具有低時延、高帶寬、高可靠性（硬件保證高達99.999%）的特點，在嵌入式系統應用中發揮著重要作用[2]。此外，RapidIO作為一項高速總線技術，對網絡分組丟失率、吞吐量、帶寬、延遲等QoS（quality of service）參數要求較高。

RapidIO網絡QoS問題是一個NPC問題（non-deterministic polynomial complete problem），主要目標是在多約束條件下選擇滿足QoS請求的傳輸路徑，目前最常用的求解方法為啟發式算法[3]。文獻[4]采用蟻群優化算法解決QoS多約束路由問題（ACO, ant colony optimization algorithm），但該算法收斂速度慢，容易陷入局部最優，導致搜索停滯，不利于發現更好的解，而且搜索時間長，算法復雜度較高；文獻[5]將A星算法（ASO, a-star optimization algorithm）與RapidIO路由分配問題相結合，但將啟發值項設定為0會使該算法變成廣度優先搜索的模式，從而失去A星算法啟發式的特點，并且不同節點之間對應不同的優化次序，因此產生的結果不同，難以達到負載均衡以及延遲上的最優化效果，此外，該算法在運行過程中的節點狀態需要大量的空間進行存儲，這會嚴重影響算法執行速度；文獻[6-7]利用遺傳算法（GA, genetic algorithm）選擇滿足條件的路徑，但該算法為局部搜索算法，會因陷入局部極值而找不到可行解；文獻[8]通過約束嚴苛度的定義來評價各個QoS度量參數，再引入K最短路徑算法來選擇可行路徑（CSKPA, constraint severity-K Shortest path algorithm），但該算法是基于搜索策略提出的，沒有充分考慮道路網絡的分布特性，同時沒有限制搜索區域，算法執行效率較低；文獻[9]將廣度優先搜索和貪婪算法相結合（BGA, breadth first search and greedy algorithm）來解決QoS路由選擇問題，該算法一定程度上更適用于較大規模的RapidIO網絡，但時間和空間的復雜度仍然較高。

上述研究表明，在RapidIO網絡QoS路由選擇問題中，關鍵是找到能夠滿足QoS請求的耗費最小的組播樹[10]。此外，RapidIO作為一種具有高實時性需求的嵌入式應用，無法不限時地逼近最優解，因此反復改進、在一定時間內不斷追求近似解的方式比較適合于這種QoS目標關聯較為緊密的網絡，該方式可以避免局部元陷入自然獨立的狀態，在全局范圍內快速地進行搜索，使多目標優化過程中的平衡問題得到有效解決[11]。

針對以上問題，本文提出一種基于改進螢火蟲算法的RapidIO路由選擇策略，該策略主要采用基于高斯變異和存儲機制的螢火蟲算法（GMGSO, glowworm swarm optimization algorithm based on gaussian mutation and memory Mechanism）來解決RapidIO網絡QoS路由選擇問題。在常規QoS模型和螢火蟲算法（GSO, glowworm swarm optimization algorithm）的基礎上加入高斯變異和存儲機制，高斯變異使搜索空間中解的散射程度得到控制，以此提高收斂速度并在搜索空間中尋找新的區域，使算法有效避免陷入局部最優；存儲機制有利于記錄GSO算法中每只螢火蟲的位置，如果在之前的搜索迭代過程中未能找到滿足QoS請求的解，則通過存儲機制對得到的解進行評估并存儲評估結果。實驗結果表明，GMGSO算法可以快速找到最優解并且最優解的可靠性較高，保證解的質量，有效解決了RapidIO網絡中的QoS路由選擇問題。

2 問題模型

2.1 RapidIO網絡結構

RapidIO網絡主要由2個部分組成，分別為交換機和終端器件[12]。圖1是一個典型的RapidIO網絡拓撲結構。RapidIO網絡控制和數據信息的傳遞過程需要RapidIO包，通過交換機的內置路由表，可以實現RapidIO包的路由，即這些數據分組包含不同的目的ID，而內置路由表在交換機的每一個端口處也均有配置，根據數據分組所提供的目的ID，交換機通過路由表映射的方式將RapidIO包從輸入端口傳送至不同的輸出端口[13]。對RapidIO包封裝和解析的處理主要由終端器件實現，每個終端器件都匹配一個設備標識符ID，是數據分組的目的端（源端），在RapidIO網絡數據交換過程中起到發起或接收數據的作用，通過交換機可以實現終端設備的互聯[14]。

圖1 RapidIO網絡拓撲結構

2.2 QoS模型

在RapidIO網絡中，時延、跳數、分組丟失率和帶寬是最常見的QoS問題[15]，QoS路由問題實際上就是找出所有滿足這些約束條件的路徑，因此將RapidIO網絡中的QoS路由選擇問題抽象化，可以建立其相應的數學模型。

3 解決方案

3.1 GSO算法

群體智能優化算法的目的是依據優化問題的目標函數尋求全局解，與尋求多個解相比，找到一個全局解顯得更容易。由于優化問題具有相同或不同的目標函數值，所以在該算法中能夠立即找到不同種類的解非常關鍵，因此一個群體可以將自己劃分成不同的類別很重要[18]。GSO算法屬于群體智能優化算法，該算法模仿了螢火蟲在控制自身發光方面的行為。這些螢火蟲為了不同的目的而發光，如在繁殖過程中吸引其他螢火蟲[19]。

通過以下2個步驟識別實際選擇的相鄰個體，首先，找出向具有更高熒光素水平的相鄰個體移動的方向并計算其概率，如式(14)所示。

在螢火蟲移動階段，根據被選擇的相鄰位置來更新螢火蟲的位置，如式(15)所示。

在GSO算法的搜索空間中，組播樹被編碼成個體，即個體編碼。文獻[20]提出了一種基于先前節點序列的編碼機制，這是因為在組播樹中除了源節點，對所有其他節點而言只存在一個先前節點，這個方法有利于編碼和解碼，可以避免在組播樹中創建環路，具體的編碼方法如式(17)所示

其中，表示節點的先前節點。不在組播樹內節點的先前節點可以用0表示，源節點的先前節點則用其本身表示。如圖2所示，組播樹可以被編碼為 ，同理所編成的碼也可以解碼為圖2所示的組播樹。

雖然文獻[20]所提的方法可以有效避免環路，但同時會產生許多不符合要求的樹，因此可以對此編碼方法進行改進，具體編碼方法如算法1所示。

算法1 組播樹編碼算法

3) 從該組目的節點中隨機選擇一個目的節點作為當前節點。

4) 從與當前節點相連的一組節點中刪除當前節點的直接后繼節點，并且生成當前節點的一組新的先前節點。

5) 從當前節點的一組先前節點中隨機選取一個節點作為當前節點的先前節點，并且這個被選擇的先前節點成為新的當前節點。

6) 如果當前節點的先前節點集為空，即“0”，則轉到步驟3)，否則轉到步驟6)。

7) 如果所有目的節點的先前節點集為空，即“0”，則輸出組播樹的代碼，否則轉到步驟3)。

3.2 高斯變異

正態分布具有許多優良特性，許多隨機因素、自然效應和概率分布可以由它來近似或體現[21]。高斯分布在數學、物理學和工程學中是極為重要的概率分布，因此它在統計方面發揮著重要作用[22]。高斯變異是在個體的原始狀態中添加隨機高斯向量的分布，其定義如式(18)所示。

3.3 存儲機制

傳統GSO算法在搜索過程中不會保留任何搜索空間信息，也不會保留每只螢火蟲的歷史狀態信息，這導致螢火蟲在不顧之前狀態如何的情況下進行移動，螢火蟲的歷史信息到最后很有可能會消失。如果在之前的搜索迭代過程中未能找到滿足QoS請求的解，則通過存儲機制對得到的解進行評估。之后具有目標值的新解被插入存儲機制中，以防循環評估。此外，應該增加新的吸收參數（absorption parameter）[23]，同時參數應隨時間和歷史狀態而變化。

3.4 QoS-GMGSO算法

綜合上述內容，將傳統GSO算法與高斯變異和存儲機制相結合成QoS-GMGSO算法，具體過程如算法2所示，主要分為以下步驟。

第1步，對QoS-GMGSO算法中的參數進行初始化，參數的設置和傳統GSO算法中的設置相同，同時需要設置算法的終止條件。

第2步，計算當前螢火蟲的適應值并啟動調用板。

第3步，利用存儲機制存儲當前參數并時刻檢查各項參數是否更新，若更新則及時存儲新的參數并保留更新前的參數。

第4步，當算法到達熒光素水平更新階段時，使用式(12)更新每只螢火蟲的熒光素水平值。

第5步，當算法到達螢火蟲移動階段時，利用式(14)計算每只螢火蟲的相鄰個體和每只相鄰個體可以被選為目標的概率。

第7步，利用式(15)計算搜索空間中每只螢火蟲的目標位置。

第8步，利用式(16)更新每只螢火蟲的決策域，此時螢火蟲移動階段結束。

第9步，計算當前螢火蟲的適應值，若該值比調用板上的數據更好，則調用板會被更新。

第10步，高斯變異階段，利用式(18)將種群中最差的螢火蟲用歷史最佳螢火蟲代替，從而形成中間狀態種群，然后計算當前螢火蟲的適應值，若該值比調用板上的數據更好，則調用板會被更新。

第11步，當算法完成一次迭代時，如果已經滿足終止條件，則退出迭代過程，否則轉到第4步進行下一次迭代。

圖3為QoS-GMGSO算法的流程。圖中從上到下依次按照傳統GSO算法模塊、存儲機制模塊以及高斯變異模塊的順序進行，首先對每只螢火蟲進行初始化，接著利用存儲機制對不斷被更新的相關參數進行存儲，再通過高斯變異模塊優化算法過程，提高算法搜索速度和解質量，最終輸出滿足QoS請求的解。

算法2 QoS-GMGSO算法

1) 設置QoS-GMGSO算法的維數和螢火蟲數量

2) 初始化QoS-GMGSO算法中其他所有參數

6) end for

12) end for

24) end for

25) end for

26) end while

圖3 QoS-GMGSO算法流程

4 實驗與結果分析

實驗采用Matlab進行仿真，先假定一組用于實驗的包含節點和鏈路的RapidIO模擬測試網絡拓撲結構圖和約束條件，再將GMGSO算法與ACO算法[4]、ASO算法[5]、GA算法[6-7]、CSKPA算法[8]和BGA算法[9]分別應用在該拓撲結構上，同時對滿足QoS請求的輸出結果進行比較。

4.1 實驗設置

4.1.1 RapidIO模擬測試網絡

為了驗證QoS-GMGSO算法的有效性，通過如圖4所示的RapidIO網絡拓撲結構進行模擬測試。假設圖中所用交換機為Tsi578芯片[24]，圖中包含了各個節點和鏈路的約束條件，節點的約束條件包括時延、時延抖動、分組丟失率和代價，鏈路的約束條件包括時延、時延抖動、帶寬和代價，將節點1設置成源節點（配置主機），將節點2、3、6、7設置成數據必須最終到達的目的節點（終端器件）。

圖4 RapidIO模擬測試網絡拓撲結構

圖5 RapidIO模擬測試組播樹簡圖

4.1.2 實驗參數設置

表1 QoS-GMGSO算法實驗參數

4.2 實驗結果分析

4.2.1 最佳組播樹

圖5(a)顯示了鏈路的初始狀態和節點的初始位置；圖5(b)顯示了在考慮帶寬約束條件之后的組播樹，節點4和5之間的鏈路因不滿足該約束條件而被刪除；圖5(c)顯示了在考慮分組丟失率約束條件之后的組播樹；圖5(d)顯示了在20次迭代之后最終的最佳組播樹。

4.2.2 不同算法的性能對比

圖6 不同算法性能對比

5 結束語

本文針對RapidIO網絡QoS路由選擇問題，提出了一種基于改進螢火蟲算法的RapidIO路由選擇策略，并通過模擬的RapidIO測試網絡來驗證其有效性。GMGSO算法利用高斯變異和存儲機制對傳統GSO算法進行優化，高斯變異有效地提高了算法收斂速度，使算法避免陷入局部最優，存儲機制評估和記錄每只螢火蟲的歷史狀態，有效防止信息的丟失。然后將GMGSO算法與RapidIO網絡QoS問題相結合，通過QoS-GMGSO算法選擇出路由最優方案。仿真結果表明，與其他算法相比，GMGSO算法時延更加穩定，代價更低，更能快速找到最優解并且解質量較高。

[1] 張娟, 蘇海冰, 吳欽章. 基于多處理器的高速RapidIO[J]. 計算機工程, 2010, 36(18): 238-239. ZHANG J, SU H B, WU Q Z. Multi processor based on high speed RapidIO[J]. Computer Engineering, 2010, 36(18):238-239.

[2] 黃亮, 劉福巖. 基于RapidIO和存儲映射的高速互連網絡[J]. 計算機工程, 2008, 34(14):116-117.HUANG L, LIU F Y. High speed Internet based on RapidIO and storage mapping[J]. Computer Engineering, 2008, 34(14): 116-117.

[3] DONG W, ZHANG W, YANG W. Node constraint routing algorithm based on reinforcement learning[C]//IEEE International Conference on Signal Processing. 2017: 1752-1756.

[4] QIN L, CHEN Y, LUO J, et al. A new way of solving multiple constrained QoS multi-routing problems[C]//International Multi- Symposiums on Computer and Computational Sciences. 2006: 668-675.

[5] 潘靈, 桑楠. 一種RapidIO網絡路徑分配策略[J]. 計算機應用, 2008, 28(s2): 294-295.PAN L, SANG N. A RapidIO network path allocation strategy[J]. Computer Application, 2008, 28(s2): 294-295.

[6] 蔡煒, 張建東, 蔡惠智. RapidIO網絡QoS多目標優化[J]. 計算機應用, 2010, 30(12): 3172-3175.CAI W, ZHANG J D, CAI H Z. RapidIO network QoS multi-objective optimization[J]. Computer Application, 2010, 30(12): 3172-3175.

[7] 蔡煒, 張建東, 蔡惠智. RapidIO網絡路由分配策略的優化和改進[J]. 計算機工程與應用, 2011, 47(14): 87-90.CAI W, ZHANG J D, CAI H Z. RapidIO network route allocation strategy optimization and improvement[J]. Computer Engineering and Applications, 2011, 47(14): 87-90.

[8] 李宗燦, 曹建. 基于約束分析的RapidIO路由選擇算法[J]. 計算機工程與設計, 2014, 35(11): 3771-3775.LI Z C, CAO J. RapidIO routing algorithm based on constraint analysis[J]. Computer Engineering and Design, 2014, 35(11): 3771-3775.

[9] DONG W, ZHANG W, YANG W. Node constraint routing algorithm based on reinforcement learning[C]//IEEE International Conference on Signal Processing. 2017:1752-1756.

[10] MATVEEVA N, SUVOROVA E, SHEYNIN Y. QoS mechanisms in SpaceFibre and RapidIO: SpaceWire networks and protocols, long paper[C]//Spacewire Conference. 2016:1-8.

[11] JAYASHEELAN P, JANE F M M. Effective route planning in road networks using multi constraint routing algorithm[C]//IEEE International Conference on Current Trends in Advanced Computing. 2016:1-6.

[12] MCKENNY M, DINES J A B, HARLE D. Transporting multiple classes of traffic over a generic routing device - an investigation into the performance of the RapidIO? interconnect architecture[C]//The, IEEE International Conference on Networks. 2003:39-44.

[13] ZHANG X, GAO M, LIU G. A Scalable heterogeneous multi-processor signal processing system based on the RapidIO Interconnect[C]//International Symposium on Intelligent Information Technology Application Workshops 2008:761-764.

[14] 石海洋. 一種RapidIO交換網絡配置方法的設計與實現[J]. 航空計算技術, 2012, 42(2):132-134.SHI H Y. Design and implementation of a RapidIO switching network configuration method[J]. Aviation Computing Technology, 2012, 42(2): 132-134.

[15] 王婷, 戴小氐, 朱守園,等. 一種靜態配置復雜RapidIO網絡的方法[J]. 信息通信, 2017(1):136-137.WANG T, DAI X D, ZHU S Y, et al. A method for statically configuring a complex RapidIO network[J]. Information and Communication, 2017(1):136-137.

[16] 施春輝, 柴小麗, 宋慰軍,等. 基于SoPC的前端RapidIO接口設計[J]. 計算機工程, 2011, 37(20):239-241.SHI C H, CHAI X L, SONG W J, et al. SoPC-based front-end RapidIO interface design[J]. Computer Engineering, 2011, 37(20): 239-241.

[17] DOLGOPOLIK M V. Smooth exact penalty functions: a general approach[J]. Optimization Letters, 2018, 10(3):635-648.

[18] SHAHINZADEH H, MOAZZAMI M, FADAEI D, et al. Glowworm swarm optimization algorithm for solving non-smooth and non-convex economic load dispatch problems[C]//Iranian Joint Congress on Fuzzy and Intelligent Systems. 2017:103-109.

[19] NUNES H, POMBO J, FERMEIRO J, et al. Glowworm swarm optimization for photovoltaic model identification[C]//Young Engineers Forum. 2017:59-64.

[20] SUN J, FANG W, WU X, et al. QoS multicast routing using a quantum-behaved particle swarm optimization algorithm[J]. Engineering Applications of Artificial Intelligence, 2011, 24(1): 123-131.

[21] CALSINA A, CUADRADO S, DESVILLETTES L, et al. Asymptotic profile in selection-mutation equations: gauss versus cauchy distributions[J]. Journal of Mathematical Analysis & Applications, 2016, 444(2):1515-1541.

[22] WAN C, WANG J, YANG G, et al. Particle swarm optimization based on Gaussian mutation and its application to wind farm micro-siting[C]//Decision and Control. 2010:2227-2232.

[23] LAIDANI N, BARTALI R, GOTTARDI G, et al. Optical absorption parameters of amorphous carbon films from Forouhi Bloomer and Tauc Lorentz models: a comparative study[J]. Journal of Physics Condensed Matter, 2008, 20(1):105-112.

[24] 任雪倩, 李金城, 趙建中,等. 基于串行RapidIO的Buffer層設計[J].微電子學與計算機, 2016, 33(9):47-50.REN X Q, LI J C, ZHAO J Z, et al. Design of Buffer layer based on serial RapidIO[J]. Microelectronics and Computers, 2016, 33(9): 47-50.

RapidIO routing strategy based on improved glowworm swarm optimization algorithm

YIN Congyue, ZHANG Xingming, REN Quan, WEI Shuai

National Digital Switching System Engineering & Technological Research Center, Zhengzhou 450002, China

Aiming at the problem of QoS routing in RapidIO network, a RapidIO routing strategy based on improved glowworm swarm optimization algorithm was proposed. Firstly, gaussian mutation and storage mechanism were used to optimize the traditional firefly algorithm. Gaussian mutation can effectively control the scattering degree of the solution in the search space of the algorithm, so that the algorithm avoids falling into a local optimum. The storage mechanism is conducive to evaluating and storing the historical state of each glowworm, preventing information loss. Then combine the improved glowworm swarm optimization algorithm with the actual RapidIO network QoS problem and select the final best routing strategy. The experimental results show that in the simulated RapidIO test network, the improved glowworm swarm optimization algorithm has a delay of 42 ms, delayed jitter of 8 ms, a minimum cost of 64 ms, and a total of 8 iterations, which is more stable than other algorithm curves. It can find the optimal solution more quickly and show the best performance, effectively solving the QoS routing problem of RapidIO network.

RapidIO, glowworm swarm optimization algorithm, gaussian mutation, storage mechanism; quality of service

TP393.02

A

10.11959/j.issn.2096-109x.2018054

2018-04-14；

2018-05-08

殷從月，503637088@qq.com

國家科技重大專項基金資助項目（No.2016ZX01012101）；國家自然科學基金資助項目（No.61572520，No.61521003）

The National Science Technology Major Project (No.2016ZX01012101), The National Natural Science Foundation of China (No.61572520, No.61521003)

殷從月（1994-），女，江蘇揚州人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為RapidIO網絡、異構計算系統。

張興明（1963-），男，河南新鄉人，國家數字交換系統工程技術研究中心教授、碩士生導師，主要研究方向為新型網絡體系結構。

任權（1994-），男，湖南常德人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為網絡安全防御、頑健網絡體系結構。

魏帥（1984-），男，河南南陽人，國家數字交換系統工程技術研究中心講師，主要研究方向為嵌入式計算。