主頁（http://www.by236.com）：遺傳算法在寬帶通信網設計中的應用

　　一、引言

　　ITU-T對寬帶業務定義為支持速率高于1.5 M bit/s（或者在ISDN、T1、DS1中數字術語的基本速率的傳輸通道能力）的業務。寬帶網絡主要是作為骨干傳輸網絡使用,要求提供較高的帶寬滿足數據流量的突發性,可按需分配帶寬,傳輸延遲小,節點多且連接關系復雜,節點發送數據類型多,流量差別大,并覆蓋比較大的區域。隨著網絡的迅速發展,網絡業務量成倍增加,以及網絡應用日益增多,網絡需要越來越高的帶寬傳輸數據、聲音、圖像等大量信息；光纖的鋪設解決了傳輸介質的帶寬,網絡瓶頸已經轉化為帶寬使用效率、交換能力、最佳或最短路由的選擇等問題。使用遺傳算法（Genetic Algorithm,GA）可以為這些問題提供快速簡便的解決方案,但原有解決方案通常都是基于窄帶網絡的研究方法,當遇到寬帶網絡問題時這些方法并不完全適用。本文著重于研究使用遺傳算法作為優化和研究工具為寬帶網絡設計提供一個比較標準的解決方案,并著重于網絡路由的優化方法。

　　二、寬帶通信網絡設計相關參數

　　寬帶網具有很大的傳輸帶寬,主要研究的是網絡的交換能力、路由選擇、網絡延遲和組織結構等方面。寬帶網傳輸延遲主要是受交換能力和路由選擇等影響形成的延遲。網絡采用不同的交換技術對網絡設計和業務具有一定的影響,主要體現在網絡規模、費用成本、交換速率、QoS、多播支持和靈活性等方面。當前寬帶網絡的主要發展方向是寬帶IP網絡。

　　為了在通信網中將遺傳算法用公式化的方法描述出來,下面給出通信網相關的研究設計參數定義。

　　● 鏈路設計：鏈路的設計包括鏈路的傳輸能力、帶寬、容量、傳輸延遲等方面的因素。寬帶網絡的主干帶寬非常大,鏈路的傳輸延遲、帶寬和容量的限制一般情況下可以不考慮,設計中主要考慮的是租用鏈路帶寬的費用以及帶寬分配和利用率等。若一條連接共租用了b條鏈路,每條鏈路i上租用的Ci容量的費用用di（Ci）表示,那么這條連接的總租用費用D就是：

　　● 交換節點設計

　　交換節點設計包括交換能力、接口能力、延遲、封裝延遲、路由等。

　　交換節點的交換能力對寬帶網絡有較大的影響,造成延遲的主要部分來自于此,因此交換能力往往會成為網絡交換的瓶頸。節點交換能力包括交換速率、交換接口的吞吐量等,交換速率主要受到硬件性能、數據包分析和封裝效率、路由選擇算法和選擇速率等影響,采用快速有效的路由選擇算法可以極大的提高交換速率,交換接口吞吐量和吞吐能力的大小直接制約著鏈路帶寬的使用率和傳輸時延,如果鏈路的流量大于接口的吞吐量會在節點緩沖中排隊等候造成時延。如果交換節點的交換能力強則數據包的延遲小,交換能力弱則延遲增大,甚至會發生擁塞導致丟包的情況。

　　● 包延遲

　　寬帶網絡的平均包延遲主要由兩方面構成：隊列延遲和交換延遲。在寬帶網絡中鏈路傳輸延遲非常小,可以不予考慮。網絡中到達節點的業務量是隨機的,數據隊列被存儲在交換節點的交換緩沖區中,如果緩沖區溢出會導致數據包丟失。假設在一個設計比較好的網絡中很少發生阻塞或者數據包很少丟失,那么這個網絡就可以近似地認為具有無限大緩沖隊列或者延遲系統。因此,隊列延遲和交換延遲都可以用M/M/1隊列來模擬。根據參考[3]中的平均等待時間計算公式可以計算延遲時間,平均等待時間計算公式為：

　　其中ρ=λ/μ,λ為到達率,μ為服務率。

　　以代表網絡中鏈路的數目,和分別代表鏈路m上的容量和總流量,以bit/s為單位。是網絡中交換的個數,和分別代表交換n的交換能力和總流量,也以bit/s為單位。σ是網絡中的平均流量。則隊列延遲和交換延遲計算如下：

　　隊列延遲主要是由于主干接口吞吐能力的限制引起的,當鏈路上需要傳輸的總流量小于該鏈路的接口吞吐能力時該流量可以順利傳輸,當總流量大于接口吞吐能力時則需要在緩沖中排隊等候發送。在這個M/M/1隊列中,到達率,服務率,由于傳輸延遲（即服務時間）小到可以不予考慮,主干隊列延遲時間就是等待時間,帶入公式1,得到平均隊列延遲時間T1為：

　　交換延遲主要是由于節點的交換能力的限制引起的,當到達節點的總流量小于該節點的交換能力時該流量可以順利進行交換,當總流量大于交換能力時就需要在緩沖中排隊等待交換。在這個M/M/1隊列中,到達率,服務率,由于寬帶網中交換速率普遍提高,線速交換的大量應用,交換處理時間（即服務時間）可以忽略不計,交換延遲就是等待時間,帶入公式1,平均交換延遲時間T2就是：

　　這樣整個網絡中（不包含傳播延遲）平包延遲T就是：

　　需要指出的是,用遺傳算法的解決方案不依賴于單一的延遲或者費用等結構的模型。對于不同的網絡或者同一網絡的不同需求可以具有不同的結構模型。

　　三、遺傳算法簡述

　　遺傳算法是根據生物學上的染色體基因因子構成機制而產生的一種計算工程學。通過遺傳算法可以找出最優解決方案。它是一種快捷、簡便、容錯性強的算法,可以直接對結構對象進行操作,易于優化和并行化,適應范圍廣。

　　遺傳算法是具有“生產+檢測”的迭代過程的搜索算法。它是一種群體型操作,該操作以群體中的所有個體為對象。選擇、交叉、變異和重排序是遺傳算法的主要操作算子。遺傳算法的運算過程為：選擇編碼方式→產生初始群體→計算初始群體適應度→如果不滿足終止條件則循環以下過程直到滿足為止：選擇→交叉→變異→（重排序）→計算新群體適應度。

　　四、使用遺傳算法建立網絡優化模型

　　網絡的總體優化過程可分為拓撲優化、路由優化和容量優化等多種優化處理過程。下面對優化過程

進行具體描述,并建立相應的的網絡模型。

　　4.1 基因因子表示方法

　　網絡拓撲可以用節點間連接邊的集合來定義,更直接的就是用鄰接矩陣表示。一個n×n的布爾值矩陣中,如果節點x到節點y之間有邊連接則a[x][y]值為1,否則為0。這是在假定鏈路是雙連接的情況下,也就是說這是一個對稱矩陣。這樣只需要n（n-1）/2個二進制值就可以表示這個矩陣。為方便起見,二維矩陣可以通過如下公式轉變為一維矩陣A：

a [k]=a [i] [j] [1]

　　這里,j > i,并且k =(2n - i)(i - 1)/2 + j - i容量、費用等參數也可以使用二維鄰接矩陣表示,在這個矩陣中的因子值就是連接之間的相應參數值。一個n×n的矩陣中,如果節點x到節點y之間有邊連接則a[x][y]對應參數值為C,否則為0,其中C就是這個相應的參數值。這是在假定鏈路是雙連接的情況下,這個矩陣也是一個對稱矩陣,只需要n（n-1）/2個二進制值就可以表示這個矩陣。為了方便起見,二維矩陣可以通過如下公式轉變為一維矩陣B：

b [k] = a [i] [j] [2]

　　這里,j > i,并且k= （2n - i）（i - 1）/2 + j - i這樣,代表網絡的拓撲、容量或者費用等參數的染色體基因就可以用一個長度為n（n - 1）/ 2位的二進制串來表示,它等同于式[1]和[2]的矩陣A和B。這樣選擇、交叉、突變以及其他的遺傳算法常規分析動作就可以分別運用到運算中來。并且在運算中,往往需要把A和B兩個矩陣結合起來進行分析和研究。比如已知網絡中兩節點間的路由矩陣A和網絡的費用矩陣B,就可以得出兩節點之間的路由總費用D：

　　其中N為網絡中的節點數量。通過遺傳算法的運算改變節點的路由矩陣A就可以通過上式得到相應路由的總費用。

　　在實際的網絡優化設計中,染色體的編碼還往往采取域的概念,就是將某些相關的節點或者鏈路等基因因子結合在一起作為一個整體參加運算,并在運算中采取一定的運算規則,使得這個域中的基因因子同時發生符合某種規則的變化,這樣可以大大簡化和方便遺傳算法的運算。

　　4.2 寬帶網絡優化中遺傳算法的應用

　　首先討論寬帶網絡優化中遺傳算法的終止條件：網絡設計中遺傳算法的終止條件可以結合寬帶網絡設計的相關參數條件來采用某種判定準則,當判定出染色體集群已經進化成熟且不再有進化趨勢時就可以終止算法的運行,常用判定準則有：連續幾代個體平均適應度的差異小于某一個極小的閾值；或者群體中所有個體適應度的方差小于某一個極小的閾值。當優化過程中連續幾代子染色體集群中的最優子染色體始終相同,或者總費用、總延遲等參數指標已經達到設計要求的標準,那么也可以判定已經到達優化的終止條件。也可以通過預先設定遺傳運算發生的次數來終止遺傳算法的運算。

　　選擇運算：選擇運算按照一定的比例在當前父染色體集群中選擇一些優良的染色體復制到下一代子染色體集群中,繼續進行遺傳運算。在選擇運算中為了防止出現局部最優化（早熟）的情況,可以采用加長編碼長度或者結合模擬退火算法等其他算法的方法進行運算,降低出現局部最優的可能。交叉運算：以路由優化為例,可以將路由方案看作是染色體,路由染色體可以用下面的路徑列表來表示：

P = {p1,p2,……,p n（n-1）/2}

這里,p k = Path（i,j）=[i,x1,x2,……,xe,j]是代表從節點i到節點j的路由路徑的基因因子,i=1,……, n；k=g（i,j）

　　對于一個特定的路由方案P,鏈路的流量可以根據業務量需求來分配。這樣,路由方案的適合程度可以用從容量分配優化中得到的最佳解決方案中得出。

　　對于父染色體P1和P2交叉運算得到子染色體P的運算中,

P1 = {p1,p2, ……, pn（n-1）/2}

P2 = {p’1 , p’2, ……,p’n（n-1）/2}

P= P1?P2 ={s（p1,p’1）,s（p2,p’2）,……,s（pn（n-1）/2,p’n(n-1)/2）}

這里,如果pi路徑比pj短,否則一般交叉發生的概率為0.4--0.99。

　　突變運算：突變運算一般在交叉運算之后進行。為了使突變在二進制以外的實際應用中得以進行,可以采用隨機突變,概率函數為：g = g + Ψ(μ,σ),其中g是真實值基因因子,Ψ是隨機函數,一般是高斯隨機函數,μ,σ分別是和隨機函數有關的平均值和變量。

　　在通信網絡優化設計的具體應用中,路由優化的突變運算就是將路由路徑p重新隨機選擇一條可行路由；容量優化則是將鏈路L上的容量重新取值；突變發生的概率為0.0001--0.1。

　　重排序運算：染色體中基因因子的排列順序對于染色體特性的決定是至關重要的。重排序的目的就是查找更具有進化潛力的基因因子序列。在路由優化中,如果進行重排序運算,有可能會發現一條新的更為優化的路由方案。重排序運算發生的幾率非常小。

　　寬帶IP網絡路由是現代寬帶通信網中的一項關鍵技術,現已有許多關于寬帶IP網路由的協議和產品,但是幾乎所有的路由協議都是以Dijkstra于五十年代提出的最短路徑模型（Dijkstra算法）為基礎的。當最短路徑被阻塞時,數據包就被緩存以等待最短路徑修復,這種路由策略并不高效,不能很好的反映網絡的動態性,也難以有效的實現網絡負載的分擔,從而使得數據包在網絡中的實際傳輸時間與期望值差別很大,網絡帶寬利用率低、傳輸延遲大和傳輸總費用高。寬帶網絡中數據傳輸的路由優化問題是寬帶網絡設計的重點之一,未來的智能路由器應該能夠適應動態變化的網絡,使數據包得以避免擁塞從而獲取各方面的優勢。遺傳算法可以很方便的和現存路由協議結合起來,對通信網中的路由算法進行優化,以獲得通信網的最佳路由。比如OSPF(開放式最短路徑優先協議)中每個參與路由器都有網絡的完全拓撲信息,可以用遺傳算法與OSPF路由算法相結合進行路由優化和選擇；另外BGP(邊界網關協議)、RIP（路由信息協議）等路由協議的路由算法也可以很方便的和遺傳算法融合。

　　五、應用舉例以及分析

　　建立遺傳算法的例程如下：

Chromosome GAs_Optimize(Chromosome Parent)

double xRate=0.5;//交叉概率

double mRate=0.05;//突變概率

double tRate=0.005//重排序概率

int Population_size=20;//父集群大小

int Sub_Population_size=20;//子集群大小

Population Pop(Population_size, Parent);//設置父集群

Population SubPop(Sub_Population_size);//設置子集群

GAs Optimize(Pop, xRate, mRate, tRate);//設置運算參數

Optimize.Evaluate(Pop);//計算群體適合度

While (Optimize.Terminate=FALSE) {//判斷是否符合終止條件

Optimize.Select_Parent(Pop, SubPop);//選擇操作

Optimize.Recombine(SubPop);//臨時保存子集群

Optimize.Cross(SubPop);//交叉操作

Optimize.Mutate(SubPop);//突變操作

Optimize.Taxis(SubPop);//重排序操作

Optimize.Reinsert(Pop, SubPop);//將子集群重新插入父集群

Optimize.Evaluate(SubPop);}return Optimize.getbest();//返回最優化結果}

　　使用了遺傳算法使得網絡設計的限制問題變得簡單化了。如圖2所示的網絡,該網絡是一個雙向傳輸網絡,每條主干線上的數字代表該主干線的使用費用,現在要選擇一條從節點A到節點F的最小費用的路由,而其他的因素暫時不予考慮。則該問題就是一個路由優化問題。

　　在這個通信網絡中二維延遲矩陣為：

　　轉換成一維延遲矩陣D為：

　　D = {AB,AC,BC,BD,CD,CE,CG,DE,DF,EF,GF}

　　　= {4,3,2,5,2,3,2,1,3,4,4}

　　要使用遺傳算法進行分析,首先要正確選擇遺傳染色體基因的表示法,以及遺傳算法的交叉、突變等運算的基本規則。針對該網絡的優化問題我們制定規則如下：

　　1、染色體基因用位串編碼表示,每一條主干傳輸線作為染色體基因的一個因子,一條主干傳輸線被選中則將對應因子標示為1,未選中則標示為0；

　　2、染色體基因分塊表示,同一起點的鏈路的染色體基因因子放入同一個塊中,從某一節點出發沒有分支路由的鏈路因子也放入同一塊中。

　　3、交叉運算中,塊與塊之間可以進行交叉運算,但塊內的因子不能進行交叉運算；

　　4、突變運算中,以塊為單位進行突變；無效主干傳輸線因子可自動優化并恢復為0。

　　根據以上規則,進行圖2的網絡路由優化。染色體的基因因子分塊分為以下幾塊：AB、AC塊,BC、BD塊,CD、CE、CG、GF塊,DE、DF塊和EF塊。隨機選擇兩條染色體基因作為初始運算染色體集群：使用R1、R2作為父染色體集群進行遺傳算法運算,得到的第一代子染色體集群為：繼續進行遺傳算法得到第二代子染色體集群為：

　　繼續進行遺傳算法運算得到的子染色體集群和第二代子染色體集群相比,最優子染色體基因仍然是R5,那么遺傳算法到此終止。從子染色體集群中我們可以很清楚的得出結論,延遲最短的路由就是A郈郉郌, 次短路由是A郈郍郌。

　　如果網絡鏈路發生了阻塞或者故障導致CG鏈路不能使用,那么就需要重新計算次短路由,染色體基因因子重新分塊為：AB、AC塊,BC、BD塊,CD、CE塊,DE、DF塊和EF塊。再次使用遺傳算法進行計算,初始運算染色體集群為：運算得到第一代子染色體集群為繼續進行遺傳算法得到第二代子染色體集群為：

　　這里終止條件和上一次運算的終止條件相同。最短路由仍然是A郈郉郌,次短路由是A郈郋郌。在這個例子中,遺傳算法的計算過程大概僅需要3個運算循環15 ~ 18次運算就可以完成,如果使用Dijkstra算法進行運算,那么所用的時間復雜性為n(n—1) 3/2,即n2量級,在這個例子中就需要7個運算循環72次運算。隨著網絡結構的復雜情況和節點鏈路數量的增加,與使用Dijkstra算法相比,遺傳算法的運算速度更快,其優越性更加顯著。

六、結論

　　寬帶通信網絡的優化是一個復雜且涉及范圍廣泛的課題,是寬帶通信網絡技術中不可缺少的部分。網絡優化的傳統方法有很多,比如梯度法、爬山法、模擬退火算法、列表尋優法等,但是他們的局限性也非常大,算法也比較復雜,在許多限制條件下不能有效的發揮作用。遺傳算法由于其高效、快速等優點成為眾多方法中比較好的一種。可以在遺傳算法中融合其它優化方法的思想,構成一種混合遺傳算法。基于遺傳算法的網絡優化方法是網絡優化發展的主要方向之一。本文對遺傳算法在網絡優化中的應用只進行了初步的探討,要將這種方法完善還需要做進一步探討和研究。

七、參考文獻

[1]Holland, J. H: Adaption in natural and artifical systems. MIT Press , 1975

[2]Thomas Back: Evolutionary Algorithms in Theory and Practice. Oxford University Press , 1996

[3]周炯磐：《通信網理論基礎》,人民郵電出版社,1992

[4]盛友招：《排隊論及其在計算機通信中的應用》,北京郵電大學出版社,1998

[5]周明、孫樹棟：《遺傳算法原理及應用》,國防工業出版社,1999

[6]葉敏：《程控數字交換與現代通信網》,北京郵電大學出版社,1998

[7]趙慧玲等：《寬帶Internet網絡技術》,電子工業出版社,1999

[8]William Stallings：《局域網與城域網（第五版）》,電子工業出版社,1998

[9]趙慧玲等：《ATM、幀中繼、IP技術與應用》,電子工業出版社,1998

[10]陳國良等：《遺傳算法及其應用》,人民郵電出版社,1996

[11]顧冠群等：《計算機網絡》,江蘇省科學技術出版社,1989