劉 鋰

（成都理工大學(xué)工程技術(shù)學(xué)院，四川 樂山 614000）

量子遺傳算法是量子算法與遺傳算法結(jié)合而成的，該算法將量子機(jī)制引入到常規(guī)遺傳算法中，彌補(bǔ)了量子算法與遺傳算法收斂度低、適應(yīng)度低等缺點(diǎn)，由于該算法具有量子算法的內(nèi)在并行性特征，被應(yīng)用到多個(gè)領(lǐng)域中均獲得了成功。隨著網(wǎng)絡(luò)的快速發(fā)展，當(dāng)網(wǎng)絡(luò)儲(chǔ)存資源達(dá)到極限時(shí)，經(jīng)常會(huì)發(fā)生網(wǎng)絡(luò)擁塞問題，會(huì)改變?cè)械木W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對(duì)網(wǎng)絡(luò)通信性能造成一定的影響。網(wǎng)絡(luò)擁塞控制路由算法成為解決網(wǎng)絡(luò)擁塞的有效手段，但是傳統(tǒng)算法在應(yīng)用過程中具有較差的適應(yīng)性，已經(jīng)無法滿足網(wǎng)絡(luò)擁塞路由控制需求，所以提出基于量子遺傳算法的網(wǎng)絡(luò)擁塞控制路由算法，提高算法的使用度，對(duì)提高網(wǎng)絡(luò)消息成功投遞率、降低網(wǎng)絡(luò)延遲具有重要的應(yīng)用價(jià)值。

1 基于量子遺傳算法的網(wǎng)絡(luò)擁塞控制路由算法

1.1 引入量子遺傳算法搜索路由

通常網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)為G=（V，E），其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，E表示網(wǎng)絡(luò)節(jié)點(diǎn)鏈路集合，網(wǎng)絡(luò)對(duì)于任意一條路由的選擇主要依靠4種度量定義，包括延時(shí)函數(shù)、寬帶函數(shù)、費(fèi)用函數(shù)、延時(shí)抖動(dòng)函數(shù)；對(duì)于任意一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的控制也是通過定義4種度量，包括延時(shí)函數(shù)、費(fèi)用函數(shù)、延時(shí)抖動(dòng)函數(shù)、節(jié)點(diǎn)包丟失率函數(shù)[1]。在應(yīng)用量子遺傳算法對(duì)網(wǎng)絡(luò)路由進(jìn)行搜索之前，先需要根據(jù)網(wǎng)絡(luò)的寬帶約束條件對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行處理，對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行編號(hào)，再刪除不滿足網(wǎng)絡(luò)約束條件的邊，以此形成一個(gè)符合寬帶約束條件的連通網(wǎng)絡(luò)。

節(jié)點(diǎn)編碼是量子遺傳算法搜索網(wǎng)絡(luò)路由的首要步驟，網(wǎng)絡(luò)節(jié)點(diǎn)編碼是否合理將直接關(guān)系到算法的搜索效率，此次采用兩個(gè)量子態(tài)疊加態(tài)的編碼方法，假設(shè)網(wǎng)絡(luò)中存在n個(gè)符合路由要求的節(jié)點(diǎn)，由路由節(jié)點(diǎn)的數(shù)量來確定量子比特的長(zhǎng)度。

以arfi表示量子比特的值，btai表示刀a值，next表示下一個(gè)量子比特。該編碼指針長(zhǎng)度等于路由節(jié)點(diǎn)數(shù)量，通過以上方法對(duì)每一個(gè)染色體進(jìn)行編碼，包含所有網(wǎng)絡(luò)路由目的節(jié)點(diǎn)，有助于提高網(wǎng)絡(luò)的收斂性。

對(duì)染色體量子比特編碼后，需要對(duì)初始種群進(jìn)行測(cè)量，由于上文設(shè)計(jì)的編碼是多維的，而對(duì)網(wǎng)絡(luò)擁塞路由搜索操作都是對(duì)1，2字符串進(jìn)行操作的，所以需要先把量子遺傳的編碼映射成二進(jìn)制編碼，再隨機(jī)產(chǎn)生一個(gè)[1，2]數(shù)，當(dāng)隨機(jī)產(chǎn)生的數(shù)值大于概率幅時(shí)，則初始種群測(cè)量結(jié)果為2，否則為1[2]。對(duì)所有初始種群測(cè)量結(jié)果進(jìn)行適應(yīng)度檢驗(yàn)，通過對(duì)初始種群中每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的適應(yīng)值來進(jìn)行篩選，適應(yīng)度函數(shù)公式：

公式（1）中，ω1是關(guān)于網(wǎng)絡(luò)分組丟失率的權(quán)重值；f(d)為針對(duì)分組丟失的罰函數(shù)；ω2是關(guān)于網(wǎng)絡(luò)路由延遲的權(quán)重值；f(c)為針對(duì)網(wǎng)絡(luò)延遲的罰函數(shù)；ω3是關(guān)于網(wǎng)絡(luò)延遲抖動(dòng)的權(quán)重值；f(h)為針對(duì)網(wǎng)絡(luò)延遲抖動(dòng)的罰函數(shù)。將適應(yīng)度最佳的測(cè)量結(jié)果的初始種群作為下一步演化的目標(biāo)值，該初始種群中的網(wǎng)絡(luò)路由作為搜索結(jié)果輸出。

量子遺傳算法搜索流程：（1）令搜索時(shí)間為零，設(shè)定種群規(guī)模。（2）對(duì)種群實(shí)施量子交叉，得到交叉后的種群。（3）對(duì)種群中每個(gè)量子個(gè)體進(jìn)行測(cè)量，得到譯碼后的量子集合。（4）運(yùn)用適應(yīng)度函數(shù)計(jì)算出量子個(gè)體的適應(yīng)度值，令量子集合中適應(yīng)度值大于1的量子個(gè)體作為新的種群，返回到步驟（1）進(jìn)行重新量子遺傳[3]。量子遺傳算法的循環(huán)深入，使網(wǎng)絡(luò)路由逐漸收斂于最優(yōu)解，擴(kuò)大網(wǎng)絡(luò)路由搜索空間。

1.2 實(shí)現(xiàn)網(wǎng)絡(luò)擁塞控制路由

上文利用量子遺傳算法搜索出的路由只是符合網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)延遲抖動(dòng)、網(wǎng)絡(luò)分組丟失條件，而網(wǎng)絡(luò)擁塞產(chǎn)生的原因最主要是網(wǎng)絡(luò)寬帶對(duì)路由影響，所以要在量子遺傳算法搜索到的路由集合中選擇出受寬帶約束最小的網(wǎng)絡(luò)路由。此次利用KMB方法，在應(yīng)用過程中實(shí)際是尋找網(wǎng)絡(luò)中的Steiner點(diǎn)。網(wǎng)絡(luò)中存在若干個(gè)節(jié)點(diǎn)，但僅存在一個(gè)Steiner點(diǎn)，該點(diǎn)到所有節(jié)點(diǎn)的距離和最小，網(wǎng)絡(luò)路由穿過Steiner點(diǎn)說明受網(wǎng)絡(luò)寬帶約束最小。具體應(yīng)用過程：（1）求出量子遺傳算法搜索結(jié)果中各個(gè)路由的路徑距離，兩兩節(jié)點(diǎn)間為最小代價(jià)路徑。（2）對(duì)原有網(wǎng)絡(luò)構(gòu)造進(jìn)行處理，生產(chǎn)新的網(wǎng)絡(luò)拓?fù)錁?gòu)造。

公式（2）中，Vn表示量子遺傳算法計(jì)算得到的網(wǎng)絡(luò)節(jié)點(diǎn)集合；En表示量子遺傳算法計(jì)算得到的網(wǎng)絡(luò)節(jié)點(diǎn)鏈路集合，其中的每一條邊是Vn中兩個(gè)節(jié)點(diǎn)之間的最短路徑；（3）在新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，節(jié)點(diǎn)與節(jié)點(diǎn)之間距離最短，且用符合Steiner點(diǎn)條件的鏈路替換原有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)與節(jié)點(diǎn)之間最短路徑，以此完成網(wǎng)絡(luò)擁塞路由控制，實(shí)現(xiàn)基于量子遺傳算法的網(wǎng)絡(luò)擁塞控制路由算法設(shè)計(jì)。

2 對(duì)比實(shí)驗(yàn)

2.1 實(shí)驗(yàn)設(shè)計(jì)

本次實(shí)驗(yàn)以Visual C++8.0作為編程工具，在CPU為Celeron3.10 GHz，內(nèi)存為128 MB的計(jì)算機(jī)上進(jìn)行仿真。

為了保證結(jié)果的有效性，實(shí)驗(yàn)中網(wǎng)絡(luò)所有路由節(jié)點(diǎn)的延時(shí)、延時(shí)抖動(dòng)、分組丟失等方面約束條件相同，并且采用一個(gè)四元組來定義網(wǎng)絡(luò)中的延遲、延遲抖動(dòng)、寬帶、分組丟失，具體實(shí)驗(yàn)參數(shù)設(shè)定如表1所示。

表1 實(shí)驗(yàn)參數(shù)

2.2 實(shí)驗(yàn)結(jié)果

此次實(shí)驗(yàn)選取網(wǎng)絡(luò)中一個(gè)小空間內(nèi)部署較多的節(jié)點(diǎn)，并且令網(wǎng)絡(luò)節(jié)點(diǎn)擁有較少的儲(chǔ)存空間，將網(wǎng)絡(luò)消息產(chǎn)生速率和大小調(diào)高，網(wǎng)絡(luò)會(huì)在最快的時(shí)間內(nèi)表現(xiàn)出擁塞。運(yùn)用此次設(shè)計(jì)算法與傳統(tǒng)算法對(duì)該網(wǎng)絡(luò)路由進(jìn)行控制，對(duì)比兩種算法的適應(yīng)度，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 兩種算法適應(yīng)度對(duì)比

可以看出，運(yùn)用此次設(shè)計(jì)算法產(chǎn)生的網(wǎng)絡(luò)路由比傳統(tǒng)算法計(jì)算得到的網(wǎng)絡(luò)路由適應(yīng)度更高。兩種算法在對(duì)網(wǎng)絡(luò)擁塞控制路由的過程中都表現(xiàn)出一定的隨機(jī)性，但是隨著迭代次數(shù)的增高，傳統(tǒng)算法計(jì)算得到的路由適應(yīng)度逐漸下降，而對(duì)此次設(shè)計(jì)算法影響并不大，依然能夠?qū)β酚蛇M(jìn)行有效控制，由此證明此次設(shè)計(jì)算法可以滿足網(wǎng)絡(luò)擁塞路由控制需求。

3 結(jié)語

在已有研究的基礎(chǔ)上，本團(tuán)隊(duì)將量子遺傳算法應(yīng)用到網(wǎng)絡(luò)擁塞控制路由算法中，形成一種新的算法，該算法具有較高的收斂性和適應(yīng)性，對(duì)保持網(wǎng)絡(luò)穩(wěn)定運(yùn)行具有重要的應(yīng)用價(jià)值。由于時(shí)間有限，雖然取得了一定的研究成果，但也存在一些不足之處，對(duì)于網(wǎng)絡(luò)擁塞控制路由算法的研究有待更加深入的探討，比如，改進(jìn)算法的終止條件等，以期為該方面研究提供參考依據(jù)。