遺傳路由算法在柵格通信網中的應用

康江 馮釗 喬瑞娟 張雅男

摘 要：遺傳算法是一種通過模擬自然進化過程搜索最優解的方法。針對Dijkstra算法在復雜的柵格化通信網路由中的應用的局限性，本文將遺傳算法引入到路由算法中，通過仿真表明隨著網絡規模的擴大，遺傳路由算法可降低路由算法的復雜度，提高網絡運行的效率。

關鍵詞：遺傳路由算法；柵格通信網；應用

隨著通信、計算機和網絡技術的迅猛發展，通信網絡以綜合業務、異構網絡資源共享為發展趨勢。現有的電信網體系結構從業務開放性、數據綜合業務及帶寬性能等方面，不能滿足將來業務的需求。為了提供安全、集成、一體化的端到端信息服務，構建新一代的柵格化通信網絡[1]勢在必行。

1 柵格通信網的體系結構

基于網絡構建的、靈活分布的信息網格，支持在動態變化的網絡環境中分享和協同解決問題。柵格與網格沒有本質的區別，網格是基于因特網構建，而柵格是基于專用通信網絡構建[2]。

新一代的柵格化通信網絡除了具備支持綜合業務、統一通信、集成服務和集成應用等主要通信網絡功能還需具備規模和功能擴展、平臺和網絡開放及資源的有限共享、端到端高性能的通信能力等特征[3]。

本文提出一種柵格通信網的分層結構。在通信網的網絡層上添加一個柵格通信服務層，更好的感知網絡資源從而支持柵格應用。

2 柵格通信網中的路由技術

目前基于柵格通信網研究的項目不多，大多是關于網絡架構方面的，較少考慮底層通信網中承載柵格服務的具體路徑。

文獻[4]提出了一種以信息安全程度為QoS參考量的策略路由技術。該策略路由技術在一定程度可以提高柵格通信網絡的安全可靠性，但是文中只在給出的簡單網絡中進行了有效驗證。文獻[4]采用了最短路徑路由算法中常用的Dijkstra（迪杰斯特拉）算法對文中提出的柵格化網絡跨域通信資源聯合調度方法進行了驗證。Dijkstra算法適合求解確定起點的最短路徑路由問題，然而隨著網絡規模與復雜度的增加，Dijkstra算法復雜度會呈現幾何級數的增長，該算法不能很好的去適應。本文采用具有較強的自適應性及全局優化性的遺傳算法對底層通信網的具體路徑選擇進行研究。

3 遺傳路由算法的應用

遺傳算法（Genetic Algorithm-GA），是模擬自然生物界系統優勝劣汰的一種智能搜索算法，它可在大的搜索空間尋找最優解或近似最優解。以下為遺傳算法的一般流程。

3.1 種群初始化

種群的選定是遺傳算法的前提。遺傳算法要求所選初始種群的規模要適當，使算法既能體現良好的優化性能又不至于陷入局部最優解。本文選定起點到終點的所有路徑作為初始種群。

3.2 適應度函數

自然界中，個體的適應值，即是它的繁殖能力，將直接關系到后代的數量。遺傳算法在運算過程中用適應度函數來評價個體優劣。然而網絡中的鏈路具有帶寬、時延、延時抖動、包丟失率等屬性，很難從某一角度評價鏈路的優劣。本文構建如下適應度函數對各條鏈路進行客觀的評價：

其中B（x）正比于各條鏈路中具有最小帶寬的節點鏈路，D（x）、J（x）、L（x）分別反比于節點鏈路的最大時延、延時抖動、丟包率。，是正加權系數，分別表示帶寬、時延、延時抖動、丟包率在適應度函數中所占的比例。，它們的值根據具體應用的側重點確定。

3.3 遺傳的操作

遺傳算法的核心步驟是選擇、交叉、變異。

選擇是從群體中選擇優良個體并淘汰劣質個體。各個個體被選擇的概率與其適應度成正比。高適應度值趨向于被選中，低適應度趨向于被淘汰。采用保留最優解與輪盤法想結合進行個體選擇。先按需保留最佳個體，再按概率選擇適當的其他個體。設個體i被選中概率為（i=1，2，3，……n），其中n為種群大小。

交叉是指把兩個父代個體的部分基因加以替換重組而生成新個體的操作，模擬自然界有性繁殖生成新個體，使其比它的兩個父代有更高的適應值。交叉是遺傳算法主要搜索工具，也是區別于其他進化算法的主要標志。由于網絡中連路的特殊性，防止兩個父代個體產生錯誤的子代，因此交叉必須滿足以下兩個條件：

⑴進行繁殖的兩個父代個體必須具有相同的鏈路節點，防止不存在相同節點的鏈路交叉產生后代

⑵生成的子代鏈路不能含有相同的鏈路節點，防止路由環的出現。

遺傳算法中同樣引入變異產生新個體，即將個體染色體上的某些基因用其它等位值替代，從而形成新個體。交叉與變異相互配合，共同完成對搜索空間的優化搜索。

4 仿真實驗及結果分析

采用網絡仿真軟件OMNeT++4.3構建仿真環境對遺傳路由算法優越性進行驗證。

仿真系統包含2個網管域。每個域內異構通信網絡拓撲分別由Area1.ned和Area2.ned進行描述，設置為有若干個路由器和多條有線光纖、衛星等不同類型的傳輸鏈路構成的網絡拓撲。兩個域內路由器分別設置為10、30、50等3組進行仿真。源和目的節點在兩個域內隨機選擇，目的節點優先考慮跨域選擇。設置源節點業務類型為普通報文。每一組均用Dijkstra算法、遺傳算法分別進行5次實驗查找最短路徑，分別記錄查詢到最短路徑的時間，同時記錄報文在源與目的節點的報文接收數量。實驗結果如下：

表1 網絡節點收發包數統計表

路由數 算法 發送包數 接收包數 接收成功率

10 遺傳 3065 2597 84.75%

迪杰斯 3065 2609 85.12%

30 遺傳 3065 2303 75.16%

迪杰斯 3065 2319 75.66%

50 遺傳 3065 1886 61.53%

迪杰斯 3065 1896 61.85%

表1表明兩種算法在網絡數據包接收成功率方面大體一致。圖2橫軸表示兩種算法搜索最優路徑所用的時間，縱軸表示網絡的復雜度（本文采用網絡路由數量衡量），左右圖分別表示Dijkstra和遺傳遺傳算法復雜度。舍棄兩圖中剛開始統計的不合理數據，通過對比可以看出隨著網絡規模的擴大，Dijkstra搜索最優路徑時間的增幅要明顯快于遺傳算法搜索最優路徑時間的增幅。

綜上所述，遺傳路由算法可以降低柵格化通信網絡路由算法的復雜度。

[參考文獻]

[1]汪陶先.信息柵格與通信柵格[J].現代通信技術，2004（4）：1-6.

[2]范淑艷，熊高云.柵格通信網絡體系機構及關鍵技術研究.西安電子科技大學學報，2009（6）：990-995

[3]黃天章，等.面向通信網絡服務架構的通信網絡設計分析.通信系統與網絡技術，2012（3）：5-8.

[4]任勇毛，唐海娜，李俊，等.支持網格應用的光網絡控制和管理[J].軟件學報，2008，19（6）：1481-1490.

[5]張培珍，楊根源，等.全球信息柵格服務質量互通性研究[J].計算機測量與控制，2010.18（2）：393-396.

[6]ZHANG Yongding，ZHENG Xiangquan，WEN Xiang.Research on grid-enabled communication network architecture[C].Changzhou：IEEE 2010 International conference on research challenges in computer science（ICRCCS2010），2010.

[7]Christodoulopoulos K，Doulamis N，Vararigous E M.Joint Communication and Computation Task Scheduling in Grids [C].Proceedings of the 8th IEEE International Symposium on Cluster Computing and Grid（CCGRID08）.Lyou：IEEE，2008：17-25.

[8]Chen Fu，Yang Jiahai，Yang Yang.Toplogy Discovery Service Research in Grid Environments[C].Proceedings of the 7th World Congress on Intelligent Control and Automation（WCICA 2008）.Chongqing：IEEE，2008：2104-2109