基于量子遺傳算法的網絡擁塞控制路由算法研究

劉 鋰

（成都理工大學工程技術學院，四川 樂山 614000）

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

1 基于量子遺傳算法的網絡擁塞控制路由算法

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

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

節點編碼是量子遺傳算法搜索網絡路由的首要步驟，網絡節點編碼是否合理將直接關系到算法的搜索效率，此次采用兩個量子態疊加態的編碼方法，假設網絡中存在n個符合路由要求的節點，由路由節點的數量來確定量子比特的長度。

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

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

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

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

1.2 實現網絡擁塞控制路由

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

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

2 對比實驗

2.1 實驗設計

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

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

表1 實驗參數

2.2 實驗結果

此次實驗選取網絡中一個小空間內部署較多的節點，并且令網絡節點擁有較少的儲存空間，將網絡消息產生速率和大小調高，網絡會在最快的時間內表現出擁塞。運用此次設計算法與傳統算法對該網絡路由進行控制，對比兩種算法的適應度，實驗結果如圖1所示。

圖1 兩種算法適應度對比

可以看出，運用此次設計算法產生的網絡路由比傳統算法計算得到的網絡路由適應度更高。兩種算法在對網絡擁塞控制路由的過程中都表現出一定的隨機性，但是隨著迭代次數的增高，傳統算法計算得到的路由適應度逐漸下降，而對此次設計算法影響并不大，依然能夠對路由進行有效控制，由此證明此次設計算法可以滿足網絡擁塞路由控制需求。

3 結語

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