劉 鋰

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

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

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

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

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

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

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

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

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

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

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

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

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

2 對比實驗

2.1 實驗設(shè)計

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

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

表1 實驗參數(shù)

2.2 實驗結(jié)果

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

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

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

3 結(jié)語

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