改進的量子遺傳算法在網絡擁塞控制中的應用

王飛

摘 要： 當前以遺傳算法為基礎的網絡擁塞控制方法對網絡擁塞存在控制目標選取耗時，最優(yōu)目標參數選取不均等問題，控制效果不佳。針對這一問題，結合量子計算的優(yōu)點，提出一種基于改進量子遺傳算法的網絡擁塞控制算法，首先對網絡擁塞的原理進行分析，建立QoS路由擁塞控制數學模型，將量子計算引入遺傳算法進行改進，在靜態(tài)旋轉角的量子遺傳算法的基礎上，保證擁塞目標參數的選取準確性，給出算法的實現方法和具體流程。實驗結果表明，該算法的搜索速度快、效率高、可以很好地優(yōu)化網絡性能，實現擁塞控制。

關鍵詞： 網絡擁塞控制； QoS路由； 量子遺傳算法； 網絡性能優(yōu)化

中圖分類號： TN915?34； TP391.9 文獻標識碼： A 文章編號： 1004?373X（2016）06?0033?04

Application of improved quantum genetic algorithm in control of network congestion

WANG Fei

（Henan Polytechnic Institute， Nanyang 473000， China）

Abstract： Since the current network access and congestion control method based on the genetic algorithm has poor control effect such as time?consuming target selection and optimal target's parameters selection， a network congestion control algorithm based on the improved quantum genetic algorithm is proposed in combination with the advantage of quantum computation. The principle of network congestion is analyzed. QoS routing congestion control mathematical model is established. The genetic algorithm， introducing quantum computation， is improved to guarantee the accuracy of the selection of congestion target parameters on the basis of the static rotation angle of quantum genetic algorithm. The implementation method and the specific process of the algorithm is given. The test results show that the algorithm has fast search speed and high efficiency， can optimize the network performance in a good way， and achieve the goal of congestion control.

Keywords： network congestion control； QoS routing； quantum genetic algorithm； network performance optimization

0 引 言

隨著互聯網技術的快速發(fā)展，網絡資源被越來越多的用戶所占用，當網絡資源遠遠不能滿足用戶需求時，就會產生“擁塞”。網絡擁塞現象最早出現在1986年10月，自此以后，人們在網絡擁塞領域進行了大量的研究工作。1988年，Jacobson提出了基于TCP流的端到端網絡擁塞控制算法[1]，1996年Raj Jain教授提出了ATM擁塞控制中的顯式速率指示[2]；K.Ramakrishnan和S.Floyd提出了TCP/IP協議上的顯式擁塞指示（ECN）方法[3?4]。近年來，隨著智能仿生類優(yōu)化算法的發(fā)展，人們在應用優(yōu)化理論進行擁塞控制算法的分析和設計方面做了大量的工作，并取得了一定的進展。其中遺傳算法（GA）憑借其并行搜索、魯棒性強等優(yōu)點，獲得了廣泛的應用；但是卻存在收斂速度慢、易陷入局部最優(yōu)等缺陷。

為了解決傳統方法存在的問題，本文建立了QoS路由優(yōu)化數學模型，將量子計算和遺傳算法融合形成量子遺傳算法（QGA）并應用到網絡擁塞控制過程中，它將量子的矢量表達引入到遺傳編碼中，通過量子邏輯門實現染色體的更新操作，該算法可以用一條染色體同時表示多種狀態(tài)的信息，具有收斂速度快、搜索效率高、能跳出局部最優(yōu)等優(yōu)點。通過對靜態(tài)旋轉角的量子遺傳算法進行改進，并進行了仿真及性能分析。

1 QoS路由擁塞控制問題的提出

計算機網絡異常龐大、復雜，為了研究各種網絡擁塞控制算法，首先需要建立QoS路由擁塞控制數學模型。

任何網絡都可以用加權圖[G=（V，E）]表示，其中，V是網絡中的交換節(jié)點集合；E是連接節(jié)點的鏈路集合。對于[?（i，j）∈V]，定義鏈路[E（i，j）]上的兩個QoS參數：帶寬[bi，j]和延遲[di，j]。設p為該網絡中源節(jié)點s到目的節(jié)點d的一條路徑，跳數為[h（p）]，其瓶頸帶寬[B（p）=][min（bi，j?（i，j）∈p）]，延遲[D（p）=（i，j）∈pdi，j]。

若路徑p上某業(yè)務量的請求帶寬是B，則該業(yè)務量占用的網絡資源消耗函數可表示為：

[R（p）=（i，j）∈pB×D（p）=h（p）×B×D（p）] （1）

式（1）表明：跳數越少、延遲越小的路徑，消耗的網絡資源越少。

對于[?E（i，j）∈p]，鏈路利用率[Ui，j=Bbi，j]，為了反映路徑p上負載分布是否均衡，通常用鏈路利用率的方差表示，如下式所示：

[δ2=i=1nj=1n（Ui，j-U）2ρi，j] （2）

其中，[U=（i，j）∈pUi，jh（p）]為[Ui，j]的均值。

QoS路由擁塞控制的基本原則是：從給定的網絡G中選取源節(jié)點s到目的節(jié)點d的路徑p，在帶寬、延遲等參數滿足要求的前提下，應盡量消耗較少的網絡資源，并盡可能使網絡負載均衡分布，從而達到擁塞控制的目的。基于上述原則，本文建立的QoS路由擁塞控制數學模型是：在網絡拓撲結構已知的情況下，對所選路徑p中的QoS參數進行優(yōu)化，使得：

[B（p）>BD（p）≤Dmin（R（p））min（δ2）] （3）

其中，D是業(yè)務量的請求延遲。

2 改進的量子遺傳算法的提出

為了解決傳統遺傳算法的問題，結合量子計算的優(yōu)勢，將量子計算引入遺傳算法中，通常采用量子位作為信息的載體。一個量子位可以表示0和1之間的任意疊加態(tài)，即：

[ψ=α0+β1] （4）

其中，[0]表示自旋向下態(tài)；[1]表示自旋向上態(tài)。[α]和[β]為兩個復數，代表[0]和[1]出現的概率幅，并且滿足：

[α2+β2=1] （5）

量子遺傳算法采用的是量子位染色體表示法，如式（6）所示：

[xki=αk11βk11αk12βk12......αk1tβk1tαk21βk21αk22βk22......αk2tβk2t......αkm1βkm1αkm2βkm2......αkmlβkml] （6）

式中：[xki]表示第k代第i個個體的染色體；m為染色體的基因個數；l為每個基因的量子比特數。這種表示方法可以同時將多個狀態(tài)用一個染色體來反映，從而使量子遺傳算法具有更好的多樣性和收斂性。

為了保持種群的多樣性，QGA一般采用量子旋轉門作用于各疊加態(tài)或糾纏態(tài)的基態(tài)，通過改變它們的概率幅去更新種群[5]。若[ζi=αiβi]、[ζ'i=α'iβ'i]表示更新前后染色體中第i個量子比特旋轉門的概率幅，則量子旋轉門的更新策略可以表示為：

[ζ′i=cosδi -sinδisinδi cosδiζi] （7）

式中[δi]為旋轉角，其大小和方向由不同的調整策略來確定。

本文提出的改進量子遺傳算法（IQGA）是在QGA的基礎上引入了量子交叉操作、動態(tài)旋轉門調整機制和量子變異操作。下面分別介紹IQGA中引入的這三種策略。

2.1 量子交叉操作

量子交叉操作通過暫時交換個體之間的部分基因，以生成高適應度值的新個體，從而極大地提高IQGA的搜索能力，實現過程如下：

（1） 隨機排序種群中的所有個體；

（2） 采用均勻交叉的方法產生新種群，交叉概率的自適應調整公式為：

[pc=pc1-（pc1-pc2）（f′-favg）fmax-favg， f′≥favgpc1， f′

式中：[fmax]為群體中最優(yōu)個體的適應度；[favg]為群體的平均適應度；[f′]為要交叉的兩個個體中較大的適應度值；[pc1=0.9]，[pc2=0.7]。

2.2 動態(tài)旋轉門調整策略

量子遺傳算法是采用量子旋轉門進行種群更新的，其中，量子旋轉角[δ]是算法的關鍵，其旋轉方向和角度大小會影響算法的收斂速度。

旋轉角有靜態(tài)和動態(tài)兩種調整策略，本文采用一種自適應變化的量子旋轉門調整策略，設[f′]為當前的適應度值，[favg]為群體的平均適應度值，[fmax]為群體中最大的適應度值，則旋轉角[δ]按式（9）自適應調整：

[δ=mfmax-f'fmax-favg， f′≥favgn， f′

式中m，n的取值范圍是[0.001π，0.05π]。

式（9）表明，當[f′]高于群體的平均適應度[favg]時，說明當前個體具有較好的性能，自適應調整旋轉角，使其向著有利于當前群體的方向演化；當[f']低于群體的平均適應度[favg]時，說明當前個體性能不好，此時應對它采用較大的旋轉角。這樣既不影響群體的收斂性，又保證了其多樣性。

2.3 量子變異操作

量子變異的作用是輕微打亂某個體的進化方向，以防止該個體陷入局部最優(yōu)，從而提高整個算法的搜索能力。本文采用的量子變異操作實現過程為：

（1） 隨機選定參與變異的個體；

（2） 按一定的概率確定個體中的變異位；

（3） 對變異位量子比特概率幅[α，β]進行非門運算，實現量子變異操作。

3 基于改進量子遺傳算法的網絡擁塞控制的應用

根據QoS路由優(yōu)化數學模型和IQGA中的各種設置，可以給出算法的實現流程圖，如圖1所示。

算法實現步驟如下：

Step1：生成初始種群[X（k0）]。將全部染色體的量子比特編碼[α0i β0i]都初始化為[12 12]，以使其全部可能狀態(tài)的等概率疊加都表示出來。

Step2：測量初始種群中的個體，得到一組狀態(tài)[P（t0）]。

Step3：計算各狀態(tài)的適應度。根據QoS路由優(yōu)化數學模型，構建適應度函數：

[fitness=1F=1a×R（p）+b×δ2] （10）

式中a和b是使目標函數F的兩部分大致相等的正實數。

Step4：記錄最優(yōu)個體及其適應度，判斷是否滿足終止條件，若滿足，則終止程序；否則，利用量子交叉、量子變異以及動態(tài)旋轉門調整策略獲取新的種群[X（k+1）]，并返回Step3。

4 仿真實例

4.1 參數設置

下面利用該算法對計算機網絡進行仿真研究。仿真網絡采用最常見的Waxman模型[6]，鏈路生成概率滿足式（11）：

[p（i，j）=αexprand（0，L）Lβ] （11）

式中：[α]，[β]為模型參數；[L]為模型中距離最遠的兩節(jié)點之間的長度。仿真時，設網絡節(jié)點N=8，[α=0.2]，[β=0.4]，鏈路可用帶寬范圍是[1.6，3.0]，延遲范圍是[3，5]，生成的拓撲網絡如圖2所示。

假設節(jié)點3上的業(yè)務流cbr0請求帶寬是1.6 Mb/s，節(jié)點4上的業(yè)務流cbr1請求帶寬是0.8 Mb/s，二者共同流向目的節(jié)點1。為了避免產生網絡擁塞，下面利用本文提出的改進量子遺傳算法優(yōu)化鏈路3?2和鏈路2?1上的QoS參數。參數設置如下：種群大小為60，交叉概率[pc1=0.9]，[pc2=0.7]，變異概率[pm]=0.01，迭代次數為100。

4.2 結果分析

優(yōu)化前后業(yè)務流cbr0的傳輸情況如表1所示。可以看出，通過該網絡鏈路的帶寬、延遲參數進行優(yōu)化，可以降低丟包率，防止出現網絡擁塞。

為了進一步驗證該算法的有效性，采用靜態(tài)旋轉角的量子遺傳算法對該網絡進行同條件優(yōu)化。

可以看出：與QGA相比，本文所提的算法可以獲得更好的最優(yōu)解；同時，QGA在90代左右目標函數才達到穩(wěn)定，而IQGA進行到40代左右目標函數就基本穩(wěn)定了，因此改進的量子遺傳算法具有更快的收斂速度，全局優(yōu)化性能好。

5 結 語

針對網絡擁塞現象，提出了一種避免網絡擁塞的改進量子遺傳算法。該算法在標準量子遺傳算法的基礎上引入自適應量子交叉和變異操作，并采用動態(tài)旋轉門調整機制。仿真結果表明：該算法的收斂速度快、搜索效率高、可以滿足QoS路由優(yōu)化的要求，更適合用于大型網絡的擁塞控制研究。

參考文獻

[1] 趙廣松，陳鳴.基于接收閾值的容延網絡擁塞控制機制[J].軟件學報，2013，24（1）：153?163.

[2] 張行功，郭宗明.率失真優(yōu)化的無線多跳網絡多路徑選擇算法[J].軟件學報，2011，22（10）：2412?2424.

[3] 李國華，李建中，高宏.ε?近似和加權公平性保證的無線傳感器網絡擁塞控制算法[J].計算機學報，2011，34（11）：2197?2210.

[4] 金彥亮，楊宇航，張珠明，等.一種適用于無線網絡的基于速率的端到端擁塞控制算法[J].上海大學學報（自然科學版），2010，16（6）：597?602.

[5] 余小華，陳瑛.一種新的無線傳感器網絡擁塞控制算法[J].計算機工程，2011，37（11）：108?110.

[6] 蔣波.網絡中的擁塞避免控制模型的仿真分析[J].計算機仿真，2013（6）：275?278.