劉振鵬，張慶文，李 明，李澤園，李小菲

(1.河北大學 電子信息工程學院 河北 保定 071002；2.河北大學 信息技術(shù)中心，河北 保定 071002)

0 引 言

為解決傳統(tǒng)網(wǎng)絡中分布式特點導致無法全局控制等問題，軟件定義網(wǎng)絡 (Software Defined Network)[1]被提出并在眾多研究者的關(guān)注下快速發(fā)展.其中，通信網(wǎng)絡路由的優(yōu)化問題[2-5]一直是其研究熱點.流量調(diào)度問題[6]的研究意義重大，路由選擇的優(yōu)劣決定著網(wǎng)絡是否發(fā)生擁塞等問題，對網(wǎng)絡整體性能有較大的影響，因此關(guān)于數(shù)據(jù)流最優(yōu)路徑的選擇問題越來越被重視.

目前針對該問題已經(jīng)提出很多方案，其中較傳統(tǒng)的等價多路徑算法(ECMP)[7]根據(jù)兩個節(jié)點間存在多條等價路徑的特點，以多條鏈路組合起來的鏈路聚合方式增強了吞吐量以及單鏈路故障時的容錯能力，該算法通過計算數(shù)據(jù)包報頭的五元組哈希值選擇路徑，對同一個目的節(jié)點有多條路徑可以選擇，且這幾條路徑是等價的，將數(shù)據(jù)流按照特定分配的方式均勻分配到各等價路徑中.但路徑中出現(xiàn)多條較大的數(shù)據(jù)流則容易發(fā)生擁塞.最短路徑算法[8]為CSPF算法中的一種，其核心思想是在保證跳數(shù)最小的鏈路中選擇可用帶寬最大的路徑作為傳輸路徑.該算法首先根據(jù)跳數(shù)來選擇可用路徑，并不能根據(jù)網(wǎng)絡狀態(tài)選擇最優(yōu)路徑，可能導致鏈路利用率不高.Awad等人[9]提出一種基于機器學習的多路徑路由(MLMR)框架，利用網(wǎng)絡狀態(tài)估計控制器提供的相應路由配置，并學習它們之間的映射功能，實時預測多路徑路由.Xu等人[10]提出了一種基于軟件定義網(wǎng)絡(SDN)的多路徑流量調(diào)度機制MTSS,該機制利用SDN網(wǎng)絡的數(shù)據(jù)流調(diào)度靈活性和多路徑特性，改善了云數(shù)據(jù)中心網(wǎng)絡的流量均衡，并提出了一種啟發(fā)式的MSS流量均衡算法.該算法對網(wǎng)絡鏈路進行周期性監(jiān)測，動態(tài)調(diào)整重鏈路上的流量，實現(xiàn)可編程的數(shù)據(jù)轉(zhuǎn)發(fā)和負載均衡.但在負載較大時會出現(xiàn)嚴重的網(wǎng)絡擁塞現(xiàn)象.在流量調(diào)度策略中，選擇最優(yōu)路徑的路由算法是該技術(shù)的核心，選擇最優(yōu)路徑時在保證跳數(shù)盡量小的同時，也應該考慮網(wǎng)絡的實時負載.

蟻群算法[11]在路由選擇中得到較好的應用，但其全局搜索能力較弱，算法容易陷入局部最優(yōu)解，且收斂速度慢.基于以上不足，本文提出一種蟻群優(yōu)化算法，通過將算法中的信息素濃度重要程度和揮發(fā)系數(shù)進行優(yōu)化，改進為動態(tài)參數(shù)，使算法前期和后期有著不同的側(cè)重點，算法前期著眼于有效提升全局搜索能力，增加輸出結(jié)果的可靠性；后期主要解決收斂速度問題，以減少算法運行時間.

1 蟻群算法與蟻群優(yōu)化算法

1.1 蟻群算法原理

蟻群優(yōu)化算法是一種仿生學算法，可以用來解決很多問題.在路由選擇問題中，將最優(yōu)路徑視為最優(yōu)解，將其他路徑作為能找到最優(yōu)解的最優(yōu)解空間.在該過程中，螞蟻在信息素的作用下選擇最佳路徑的正反饋機制，最終會讓大多數(shù)螞蟻使用最佳路徑，從而得出路由問題的最優(yōu)路徑.蟻群優(yōu)化算法中每只螞蟻根據(jù)信息素的濃度來選擇路徑[12-13]，路徑上的信息素越多，螞蟻選擇該路徑的概率越高，信息素也會隨時間慢慢揮發(fā)，因此在螞蟻經(jīng)過較少的路徑上信息素濃度會逐漸降低，被選擇的概率也漸漸降低.蟻群這種行為產(chǎn)生了一種正反饋機制，隨著時間的推移，蟻群漸漸聚集到信息素濃度最高的路徑.蟻群算法中，螞蟻選擇路徑的概率表示為式：

(1)

在尋路過程中信息素的更新起著重要作用，每次信息素的更新包括兩部分：信息素揮發(fā)和信息素累加，螞蟻經(jīng)過的路徑會累加信息素，但如果沒有持續(xù)累加，該路徑信息素濃度會漸漸揮發(fā).其具體更新機制的數(shù)學表達式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

式中：τij(t+1)表示信息素更新后的信息素濃度，ρ為信息素揮發(fā)系數(shù)，Δτij(t)為位置i到位置j的信息素濃度增量，I為螞蟻數(shù)量.

信息素濃度的增量Δτij的計算模型分為三種：蟻量系統(tǒng)模型、蟻密系統(tǒng)模型、蟻周系統(tǒng)模型.其中蟻量系統(tǒng)模型表達式為:

(4)

式中：Q為釋放信息素總量，dij為位置i到位置j的距離.

蟻密系統(tǒng)模型表達式為：

(5)

蟻周系統(tǒng)模型表達式為：

(6)

式中：Lk為螞蟻經(jīng)過的路徑長度.由于本文需要選擇鏈路負載較小且跳數(shù)較小的路徑，所以本文選用蟻周系統(tǒng)模型，即式(6).路徑跳數(shù)越多，信息素濃度增量越小，有Lk=mk.

1.2 蟻群優(yōu)化算法設(shè)計

1.2.1 蟻群優(yōu)化算法

在蟻群算法中，因為靠信息素濃度來決定選擇路徑的概率，算法很容易陷入局部最優(yōu)解，導致算法并沒有找到最優(yōu)路徑就收斂，搜索能力有限.信息素的更新過于復雜也容易導致算法收斂速度很慢，增加迭代次數(shù).本文對算法的優(yōu)化在于對信息素濃度的重要程度、信息素濃度更新規(guī)則以及信息素揮發(fā)機制等方面的改進，以增強算法的全局搜索能力，增加最優(yōu)路徑的可靠性，并簡化復雜的信息素更新規(guī)則，加快收斂速度.

1)啟發(fā)函數(shù)的定義.啟發(fā)函數(shù)的定義對算法影響較大，必須能較清晰地表達出不同路徑的相對優(yōu)劣.由于SDN控制器可以獲取鏈路的狀態(tài)信息，可以準確地獲得當前鏈路的負載情況，由此定義：

(7)

(8)

ηij(t)=(1-δij(t))

(9)

2)對信息素濃度重要程度改進.定義每條路徑的信息素初始濃度為τ0，在式(1)中α與β為信息素濃度與啟發(fā)式的重要程度，兩個值對算法有著極大的影響.在蟻群算法中，隨著信息素濃度的增加，信息素濃度高的路徑會聚集更多的螞蟻，由于正反饋的機制，信息素濃度也會越來越高，往往會造成算法過早地收斂于一條信息素濃度較高的路徑，且蟻群一旦開始聚集，這個過程就是不可逆的.本文對算法中的信息素濃度α重要程度進行改進，表達式為：

(10)

式中：nmax表示最大迭代次數(shù)，αmax表示信息素濃度重要程度的最大值，二者均為設(shè)定的固定值，n為當前迭代次數(shù).α按照(10)定義，其變化趨勢會呈現(xiàn)一個平滑增加的曲線，迭代前期，由于迭代次數(shù)較小，α的值也較小，此時信息素濃度的影響最低，雖然隨著迭代次數(shù)的增加，信息素累積，但算法對路徑的選擇依然主要取決于啟發(fā)函數(shù)，增強了算法的全局搜索能力，迭代后期，路徑上信息素濃度較高，且α的值也越來越大，算法迅速收斂，此時算法的最優(yōu)路徑可靠性更高.

3)對揮發(fā)系數(shù)的改進.因為信息素濃度增量采用蟻周系統(tǒng)模型式(6)，即螞蟻經(jīng)過的跳數(shù)越多，信息素濃度增量越少.為了避免算法陷入局部最優(yōu)解，以及加快后期的收斂速度，算法對揮發(fā)系數(shù)ρ也采用逐步減小的動態(tài)參數(shù)，其表達式如下：

(11)

式中：ρ為揮發(fā)系數(shù)，ρmax為信息素揮發(fā)系數(shù)最大值，ρmin為信息素揮發(fā)系數(shù)最小值.揮發(fā)系數(shù)的動態(tài)遞減設(shè)定，首先加強了前期算法的全局搜索能力，最大程度上避免算法陷入局部最優(yōu)解的可能性，使算法輸出的最優(yōu)路徑更可靠.其次算法后期揮發(fā)系數(shù)的減小，使信息素濃度快速增加，加快后期的收斂.因為信息素揮發(fā)系數(shù)ρ的取值范圍是(0,1)，一般取ρmax的值為：ρmax=1，所以式(11)可以簡化為：

(12)

1.2.2 算法步驟

通過對蟻群算法的改進使其更適用于路由選擇問題，算法有效地提升了全局搜索能力，且收斂速度較快，蟻群優(yōu)化算法的具體流程為：

步驟一：初始化網(wǎng)絡及參數(shù)，包括網(wǎng)絡拓撲、鏈路狀態(tài)、鏈路集合、節(jié)點集合,和關(guān)于蟻群算法的螞蟻數(shù)量I、最大跳數(shù)mmax、最大迭代次數(shù)nmax、信息素濃度重要程度最大值αmax、啟發(fā)式重要程度β,以及涉及信息素濃度更新的各鏈路信息素濃度初始值τ0、揮發(fā)系數(shù)最小值ρmin、信息素總增量Q.

步驟二：根據(jù)式(10)計算本次迭代的信息素濃度重要程度α，由初始節(jié)點根據(jù)式(1)和式(9)以及式(12)計算選擇概率來選擇交換機，直至所有螞蟻到達目的節(jié)點或達到最大跳數(shù)mmax，單次迭代完成.

步驟三：根據(jù)式(2)和式(3)以及式(6)更新信息素濃度τij(t+1)，判斷更新迭代次數(shù)是否達到最大迭代次數(shù)nmax，未達到則重復步驟二.

步驟四：迭代次數(shù)達到迭代次數(shù)nmax，完成迭代，結(jié)束迭代并輸出最優(yōu)路徑.

算法流程如圖1所示.

圖1 螞蟻優(yōu)化算法流程圖Fig.1 Flow chart of ant colony optimization algorithm

2 仿真實驗及結(jié)果分析

實驗環(huán)境以Mininet[14-16]為實驗仿真平臺，模擬搭建4個pod，四個核心交換機的Fat-Tree結(jié)構(gòu)，如圖2所示的SDN網(wǎng)絡，使用Ryu控制器作為SDN控制器.并使用Mininet自帶的Iperf軟件在模擬網(wǎng)絡中生成流量負載并設(shè)置相關(guān)參數(shù)，將本文算法和等價多路徑算法ECMP和最短路徑算法作對比，通過分析實驗結(jié)果驗證本文提出的蟻群優(yōu)化算法的有效性.

圖2 實驗拓撲圖Fig.2 Experimental topological graph

2.1 實驗環(huán)境

處理器：INTEL CoreI5-5200U；內(nèi)存：8GB；操作系統(tǒng)：Ubuntu 16.04；仿真平臺：Mininet；控制器：Ryu.

2.2 實驗設(shè)置

實驗采用4個pod的Fat-Tree網(wǎng)絡拓撲，交換機為OpenFlow交換機，各鏈路帶寬設(shè)置為100 Mb/s.使用Iperf工具產(chǎn)生模擬流量，由于蟻群優(yōu)化算法相比ECMP算法等更復雜，完成路徑選擇時間更長，所以并不適合處理占用帶寬較小的小流.實驗模擬主機向網(wǎng)絡隨機發(fā)送大流，定義向網(wǎng)絡中發(fā)送的大流的主機數(shù)量占比為網(wǎng)絡負載.在蟻群優(yōu)化算法中，初始參數(shù)的合理設(shè)定十分重要，對算法效果有著決定性的作用.在對部分參數(shù)設(shè)定范圍的研究基礎(chǔ)上[17]，設(shè)定參數(shù)如表1.

表1 算法初始參數(shù)值設(shè)定Tab.1 Setting of algorithm initial parameters

螞蟻數(shù)量的設(shè)定取決于網(wǎng)絡的規(guī)模，在實驗中根據(jù)網(wǎng)絡拓撲中主機個數(shù)將其設(shè)定為10.最大跳數(shù)的設(shè)定如果太大，會增加算法每次迭代的時間，太小會影響算法效果，實驗中將其設(shè)定為11.最大迭代次數(shù)根據(jù)相關(guān)文獻[18]，選擇算法迭代50次.信息素重要程度和啟發(fā)式重要程度有著相對性，算法中由于信息素濃度重要程度是遞增的，且為信息素濃度后期收斂的主要參考，所以信息素濃度重要程度最大值設(shè)為3，啟發(fā)式重要程度設(shè)為2.信息素初始濃度各鏈路相同均為1，揮發(fā)系數(shù)的最小值設(shè)為0.5.將本文蟻群優(yōu)化算法與經(jīng)典的ECMP和最短路徑算法進行對比.

2.3 實驗結(jié)果及分析

在算法中信息素濃度的重要程度α由公式(10)計算變化，呈遞增趨勢直到達到最大值αmax，如圖3所示.其變化趨勢相對啟發(fā)式的重要程度來看算法前期信息素濃度的大小對螞蟻選擇下一跳位置的影響并不大，最大程度地避免了算法前期陷入局部最優(yōu)解，增強了全局搜索能力，后期隨著α的逐漸增大，信息素的累積也逐漸增加，螞蟻開始趨向收斂于信息素積累較多的路徑中，最后α繼續(xù)增加，超過啟發(fā)式重要程度，所有螞蟻收斂于一條路徑.

圖3 信息素濃度重要程度α與啟發(fā)式重要程度β變化趨勢Fig.3 Change trend of pheromone importance α and heuristic importance β

揮發(fā)系數(shù)如式(12)變化，隨著迭代次數(shù)增加，揮發(fā)系數(shù)ρ由大到小遞減，如圖4所示.前期揮發(fā)系數(shù)較大，后期揮發(fā)系數(shù)逐漸減小，和信息素濃度重要程度α相互影響下，前期信息素濃度的影響會比較小，對算法全局搜索能力有顯著的提升以及后期的收斂也會較明顯.

圖4 揮發(fā)系數(shù)ρ隨迭代次數(shù)n增加的變化趨勢Fig.4 Variation trend of volatilization coefficient ρ with the increase of iteration times n

1) 鏈路利用率對比.網(wǎng)絡鏈路利用率指的是被利用鏈路數(shù)目占鏈路總數(shù)比例.相同負載下，鏈路利用率越高，表示網(wǎng)絡流量分布越均勻，算法性能越強.圖5為網(wǎng)絡中鏈路利用率的對比結(jié)果，隨著網(wǎng)絡負載的逐漸增大，鏈路利用率逐漸增加.當網(wǎng)絡負載達到一定程度后，由于蟻群優(yōu)化算法對于網(wǎng)絡鏈路負載的計算，其鏈路利用率高于ECMP和最短路徑算法，后期網(wǎng)絡負載達到1時，本文算法較ECMP鏈路利用率提升17.1%，ECMP是將同一目的節(jié)點的數(shù)據(jù)包按特定分配方式，均勻分配到多條等價路徑上，因此在負載達到一定程度后該算法缺乏對于網(wǎng)絡鏈路差異性的判斷，所以其鏈路利用率最低.本文算法相較最短路徑算法鏈路利用率提升9.9%(見表2)，最短路徑算法側(cè)重于根據(jù)跳數(shù)尋找最優(yōu)路徑，然后在具有最小跳數(shù)的路徑中選擇可用帶寬最大的路徑，且一旦需要重新計算路徑時也會從剩余的幾條最小跳數(shù)路徑中選擇帶寬最大的路徑作為輸出結(jié)果，該算法注重跳數(shù)的優(yōu)勢，鏈路利用率較低.

圖5 鏈路利用率對比Fig.5 Comparison of link utilization

表2 負載為1時蟻群優(yōu)化策略鏈路利用率和相對提升Tab.2 Link utilization and relative promotion of ant colony optimization strategy when load is 1

2) 網(wǎng)絡平均吞吐量對比.網(wǎng)絡的平均吞吐量是指網(wǎng)絡系統(tǒng)在單位時間吞吐量的平均值，其直觀地反映了網(wǎng)絡的傳輸性能.圖6為平均吞吐量對比，ECMP在三種算法策略中平均吞吐量是最低的，其中等價路徑分配模式很容易造成網(wǎng)絡擁塞，從而導致其平均吞吐量最低，最短路徑算法首先選擇跳數(shù)最小的路徑，然后在選擇跳數(shù)最小的路徑中帶寬最大的路徑，減少了網(wǎng)絡擁塞發(fā)生的機率.本文算法將鏈路負載和路徑的跳數(shù)同時代入計算，選擇的最優(yōu)路徑可靠性更高(見表3).

表3 負載為1時蟻群優(yōu)化策略平均吞吐量和相對提升Tab.3 Average throughput and relative improvement of ant colony optimization strategy when load is 1

圖6 平均吞吐量對比Fig.6 Average throughput comparison

3 總 結(jié)

本文提出了一種基于蟻群優(yōu)化算法的SDN網(wǎng)絡路由策略，蟻群優(yōu)化算法作為動態(tài)路由算法其復雜度高于等價多路徑算法ECMP，因此蟻群優(yōu)化算法更適用于處理網(wǎng)絡中占用帶寬較大的大流.通過將蟻群算法中的信息素濃度重要程度和揮發(fā)系數(shù)由固定參數(shù)改進為動態(tài)參數(shù)，使算法更適用于網(wǎng)絡中的路由算法，同時解決了蟻群算法自身全局搜索能力弱、收斂速度慢的不足.