混合遺傳算法在網(wǎng)絡擁塞控制中的仿真研究

趙 靜，路銀川，孔金生

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

0 引言

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

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

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

1 QoS路由優(yōu)化數(shù)學模型

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

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

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

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

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

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

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

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

2 混合遺傳算法的實現(xiàn)

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

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

2.1 編碼

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

2.2 適應度函數(shù)

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

2.3 選擇

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

式中，F(xiàn)i為該個體的適應度值；為種群中所有個體適應度值之和。

2.4 交叉和變異

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

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

2.5 移動

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

2.6 禁忌表

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

2.7 特赦準則

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

2.8 終止條件

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

3 仿真研究

3.1 網(wǎng)絡參數(shù)設置

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

圖2 網(wǎng)絡拓撲圖

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

3.2 結果分析

3.2.1 網(wǎng)絡性能的比較

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

表1 優(yōu)化前后封包情況

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

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

3.2.2 QoS參數(shù)的平均優(yōu)化結果

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

圖5 平均收斂特性的對比

4 結束語

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

[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路由選擇優(yōu)化[J]. 計算機應用, 2005, 25(2):256-258.

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