改進的量子遺傳算法在網(wǎng)絡(luò)擁塞控制中的應(yīng)用

王飛

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

關(guān)鍵詞： 網(wǎng)絡(luò)擁塞控制； QoS路由； 量子遺傳算法； 網(wǎng)絡(luò)性能優(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 引 言

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

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

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

計算機網(wǎng)絡(luò)異常龐大、復(fù)雜，為了研究各種網(wǎng)絡(luò)擁塞控制算法，首先需要建立QoS路由擁塞控制數(shù)學模型。

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

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

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

式（1）表明：跳數(shù)越少、延遲越小的路徑，消耗的網(wǎng)絡(luò)資源越少。

對于[?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路由擁塞控制的基本原則是：從給定的網(wǎng)絡(luò)G中選取源節(jié)點s到目的節(jié)點d的路徑p，在帶寬、延遲等參數(shù)滿足要求的前提下，應(yīng)盡量消耗較少的網(wǎng)絡(luò)資源，并盡可能使網(wǎng)絡(luò)負載均衡分布，從而達到擁塞控制的目的?；谏鲜鲈瓌t，本文建立的QoS路由擁塞控制數(shù)學模型是：在網(wǎng)絡(luò)拓撲結(jié)構(gòu)已知的情況下，對所選路徑p中的QoS參數(shù)進行優(yōu)化，使得：

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

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

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

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

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

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

[α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為染色體的基因個數(shù)；l為每個基因的量子比特數(shù)。這種表示方法可以同時將多個狀態(tài)用一個染色體來反映，從而使量子遺傳算法具有更好的多樣性和收斂性。

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

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

式中[δi]為旋轉(zhuǎn)角，其大小和方向由不同的調(diào)整策略來確定。

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

2.1 量子交叉操作

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

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

（2） 采用均勻交叉的方法產(chǎn)生新種群，交叉概率的自適應(yīng)調(diào)整公式為：

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

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

2.2 動態(tài)旋轉(zhuǎn)門調(diào)整策略

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

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

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

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

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

2.3 量子變異操作

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

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

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

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

3 基于改進量子遺傳算法的網(wǎng)絡(luò)擁塞控制的應(yīng)用

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

算法實現(xiàn)步驟如下：

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

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

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

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

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

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

4 仿真實例

4.1 參數(shù)設(shè)置

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

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

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

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

4.2 結(jié)果分析

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

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

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

5 結(jié) 語

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

參考文獻

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

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

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

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

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

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