混合遺傳算法在網絡擁塞控制中的仿真研究

趙 靜，路銀川，孔金生

（1. 中州大學 工程技術學院，鄭州 450044；2. 鄭州大學 電氣工程學院，鄭州 450002）

0 引言

過多的報文存在于網絡時，會引起網絡性能下降，即發生了擁塞[1]。擁塞的出現會增加鏈路的丟包率、加大節點之間的延遲、加劇網絡抖動、降低網絡吞吐量。擁塞的發生雖然意味著網絡能夠提供給用戶的資源遠遠小于用戶的需求量，但是單一的增加網絡資源不能緩解該現象，反而會加重擁塞程度。因此，采用有效的方法實現擁塞控制已成為當前網絡研究的熱點問題。

目前，人們提出了很多算法，如RED、REM[2]、Drop Tail隊列管理、DRED[3]、PI控制器[4]、PID控制器[5]等。但是它們都存在一些缺陷，如RED和Drop Tail算法受主觀因素影響大，穩定性差，魯棒性不強，控制過程中容易產生錯誤的數據，甚至發生丟失；PI控制器、REM、DRED、PID控制器等算法的動態性能不好，隊列波動較大。由于智能仿生類優化算法具有并行性和自適應能力好、魯棒性強等優點，特別適用于網絡擁塞控制[6,7]。但以往的研究大多是在網絡的帶寬、延遲等服務質量(QoS)參數一定的情況下，利用智能優化算法選擇一條滿足多個QoS要求的最佳路徑，這些研究方法其實更偏向于網絡調度。

為了實現避免網絡擁塞、改善網絡性能，本文在已有優化算法的基礎上，將遺傳算法和禁忌搜索算法結合起來，提出了一種混合遺傳算法，仿真結果表明這種算法能可靠、有效地實現擁塞控制。

1 QoS路由優化數學模型

計算機網絡規模龐大、結構復雜，為了能夠分析各種網絡擁塞控制策略，同時滿足用戶的網絡服務質量要求，需要建立QoS路由優化數學模型，其優化原則為：在保證帶寬和延遲等QoS參數滿足要求的前提下，盡可能減少使用的網絡資源，并均勻分布各處的網絡負載。這屬于NP-hard問題，不能得到最優解，只能找尋次優解，因此本文構造的QoS路由優化數學模型的表達式為：

其中，A(p)稱為資源消耗函數，反映的是網絡中某一業務量在所選路徑p中占用的網絡資源量，可表示為：

式中，h(p)為所選路徑p的跳數；B為業務量的請求帶寬；d(p)為路徑p的延遲。顯然，若路徑的h(p)越少、d(p)越小，它占用的網絡資源就少。

σ2為某條路徑p上鏈路利用率的方差，反映的是負載在該路徑上均衡分布的程度，可表示為：

式中，Em,n為節點m到節點n的鏈路利用率；為Em,n的均值；若m→n的鏈路屬于所選路徑，則ρm,n為1，否則，ρm,n為0。

k1和k2是兩個正實數，若取值適當可使目標函數M的兩部分基本相等。

因此，網絡擁塞控制問題可以描述為：在網絡拓撲結構已知的情況下，采用優化算法對鏈路的帶寬和延遲等參數進行優化，從而使目標函數M最小。

遺傳算法（GA）的全局搜索能力強，但卻具有較差的爬山能力、容易出現早熟；禁忌搜索（TS）的爬山能力強，但卻需要通過經驗去選擇初始參數，魯棒性差。為了彌補兩種算法的缺點，提高優化效率，本文在GA中融入TS的思想，提出了一種混合遺傳算法。

2 混合遺傳算法的實現

該算法的程序設計流程圖如圖1所示。

圖1 混合遺傳算法的程序設計流程圖

2.1 編碼

遺傳算法常用到的編碼方法有二進制編碼、十進制編碼、實數編碼等。為了便于描述優化問題，提高算法的精度，本文采用實數編碼。

2.2 適應度函數

適應度函數能反映同一群體中不同個體的優劣，是選擇操作的依據，通常采用最大值的形式。由于優化數學模型（1）式為最小值問題，所以本文采用對其求倒數的辦法來獲取適應度函數，即：

2.3 選擇

采用最基本的輪盤賭選擇。在這種方法中，個體進入下一代的概率Pi可表示為：

式中，Fi為該個體的適應度值；為種群中所有個體適應度值之和。

2.4 交叉和變異

采用自適應交叉、變異操作，交叉率Pc和變異率Pm的自適應調整公式為：

式中，Pc1、Pc2、Pm1和Pm2均為常數；Fmax為群體中最優個體的適應度；Favg為群體的平均適應度；F′為交叉操作中適應度值較大的個體；F 為要變異個體的適應度值。根據個體自身的性能好壞，選擇合適的Pc和Pm。

2.5 移動

經過選擇、交叉、變異操作，遺傳算法為禁忌搜索產生了較好的初始個體。禁忌搜索按照特定的搜索方向“移動”，每次“移動”產生一個試驗個體。根據編碼特點，本文采用單點移動，即在碼串中隨機選擇一位，按照設定好的步長遞增或遞減。

2.6 禁忌表

禁忌表對已經進行的優化過程進行記錄和選擇，可防止禁忌搜索陷入局部最優。這里采用動態設置方式，即每次循環結束，將最早進入禁忌表的反方向“移動”替換成當前的反方向“移動”，并定義“移動”的禁忌長度，最后將其它反方向“移動”的禁忌長度都減1。

2.7 特赦準則

為了盡可能不錯過產生最優解的“移動”，禁忌搜索還采用了“特赦準則”策略，并保留最優個體記錄，以便替代下一代中的最劣個體。

2.8 終止條件

該混合優化算法中存在兩個循環：內循環和外循環。內循環的終止條件是禁忌搜索的最大允許迭代次數；外循環的終止條件有兩個：遺傳算法的最大允許迭代次數和優化判據，其中優化判據為禁忌搜索前后最優個體適應度值的變化是否不大于某個給定的常數。

3 仿真研究

3.1 網絡參數設置

為了驗證該混合遺傳算法的有效性，對圖2所示的網絡拓撲圖進行仿真研究。

圖2 網絡拓撲圖

網絡中的每條鏈路設置一組QoS參數：[帶寬延遲]=[1Mb 10ms]。假設源節點0和1上有兩個相同的流量發生器cbr0和cbr1，每隔5ms便產生500Byte大小的數據分組，流向目的節點3。cbr0封包在0.5s時開始發送，4.5s時停止；cbr1封包在1.0s時開始發送，4.0s時停止。由于節點0和節點1的請求帶寬為0.8Mb，而鏈路2-3的帶寬僅為1Mb，當兩組業務流共同流經鏈路2-3時，必定會出現爭奪網絡資源的現象，從而引起網絡擁塞。下面利用本文提出的混合遺傳算法對鏈路2-3的帶寬和延遲參數進行優化。

3.2 結果分析

3.2.1 網絡性能的比較

優化前后cbr0封包和cbr1封包的情況見表1。圖3、圖4分別為優化前后cbr0和cbr1封包端到端的延遲時間。從仿真結果可以看出，利用混合遺傳優化算法對網絡參數優化后，減小了封包端到端的延遲時間，避免了網絡擁塞。

表1 優化前后封包情況

圖3 cbr0封包端到端的延遲時間

圖4 cbr1封包端到端的延遲時間

3.2.2 QoS參數的平均優化結果

為了進一步驗證本文中混合遺傳算法的優化性能，采用GA對同一網絡進行優化，對比兩種算法的收斂特性，其結果如圖5所示。由圖5可知：混合遺傳算法在第70代左右就生成了最優目標函數值，而GA在第80代左右才生成最優目標函數值；而且，經混合遺傳算法優化后的目標函數值小于GA優化后的目標函數值。這說明混合遺傳算法具有較快的收斂速度，全局優化性能好。

圖5 平均收斂特性的對比

4 結束語

針對網絡擁塞現象，本文提出了一種避免網絡擁塞的混合遺傳算法。該算法結合了遺傳算法和禁忌搜索的特點，既避免了遺傳算法陷入局部最優解，又為禁忌搜索提供了較好的初始個體，減少調用的次數，加快了算法的收斂。仿真結果反映出該混合遺傳算法在減小網絡資源利用、均衡分布負載的同時，可以降低丟包率、減小端到端的延遲時間，達到避免網絡擁塞的目的，為進一步實施擁塞控制提供了有效途徑。

[1] JACOBSON V. Congestion Avoidance and Control[J].ACM Computer Communication Review, 1988,18(4):314-329.

[2] ATHURALLYA S, LI V H, LOW SH, et al. REM: Active Queue Management[J]. IEEE Network, 2001, 15(3):48-53.

[3] AWEYA J, OUELLETTE M, MONTUNO D Y. A Control Theoretic Approach to Active Queue Management[J].Computer Networks, 2001, 36(2): 203-235.

[4] HOLLOT C V, MISRA V, TOWSLEY D. On Designing Improved Controllers for AQM Routers Supporting TCP Flows[C]. In Proceedings of IEEE INFOCOM,2001:1726-1734.

[5] 任豐原,王福豹,任勇,山秀明.主動隊列管理中的PID控制器[J]. 電子與信息學報, 2003, 25(1): 94-99.

[6] 金瓊,周世紀,彭燕妮.基于改進遺傳算法的QoS路由選擇優化[J]. 計算機應用, 2005, 25(2):256-258.

[7] 陳曦.基于免疫粒子群優化算法的多約束路由選擇算法[J]. 長沙交通學院學報,2006,22(2):56-59.