康江 馮釗 喬瑞娟 張雅男

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

關(guān)鍵詞：遺傳路由算法；柵格通信網(wǎng)；應用

隨著通信、計算機和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，通信網(wǎng)絡(luò)以綜合業(yè)務(wù)、異構(gòu)網(wǎng)絡(luò)資源共享為發(fā)展趨勢?，F(xiàn)有的電信網(wǎng)體系結(jié)構(gòu)從業(yè)務(wù)開放性、數(shù)據(jù)綜合業(yè)務(wù)及帶寬性能等方面，不能滿足將來業(yè)務(wù)的需求。為了提供安全、集成、一體化的端到端信息服務(wù)，構(gòu)建新一代的柵格化通信網(wǎng)絡(luò)[1]勢在必行。

1 柵格通信網(wǎng)的體系結(jié)構(gòu)

基于網(wǎng)絡(luò)構(gòu)建的、靈活分布的信息網(wǎng)格，支持在動態(tài)變化的網(wǎng)絡(luò)環(huán)境中分享和協(xié)同解決問題。柵格與網(wǎng)格沒有本質(zhì)的區(qū)別，網(wǎng)格是基于因特網(wǎng)構(gòu)建，而柵格是基于專用通信網(wǎng)絡(luò)構(gòu)建[2]。

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

本文提出一種柵格通信網(wǎng)的分層結(jié)構(gòu)。在通信網(wǎng)的網(wǎng)絡(luò)層上添加一個柵格通信服務(wù)層，更好的感知網(wǎng)絡(luò)資源從而支持柵格應用。

2 柵格通信網(wǎng)中的路由技術(shù)

目前基于柵格通信網(wǎng)研究的項目不多，大多是關(guān)于網(wǎng)絡(luò)架構(gòu)方面的，較少考慮底層通信網(wǎng)中承載柵格服務(wù)的具體路徑。

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

3 遺傳路由算法的應用

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

3.1 種群初始化

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

3.2 適應度函數(shù)

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

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

3.3 遺傳的操作

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

選擇是從群體中選擇優(yōu)良個體并淘汰劣質(zhì)個體。各個個體被選擇的概率與其適應度成正比。高適應度值趨向于被選中，低適應度趨向于被淘汰。采用保留最優(yōu)解與輪盤法想結(jié)合進行個體選擇。先按需保留最佳個體，再按概率選擇適當?shù)钠渌麄€體。設(shè)個體i被選中概率為（i=1，2，3，……n），其中n為種群大小。

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

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

⑵生成的子代鏈路不能含有相同的鏈路節(jié)點，防止路由環(huán)的出現(xiàn)。

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

4 仿真實驗及結(jié)果分析

采用網(wǎng)絡(luò)仿真軟件OMNeT++4.3構(gòu)建仿真環(huán)境對遺傳路由算法優(yōu)越性進行驗證。

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

表1 網(wǎng)絡(luò)節(jié)點收發(fā)包數(shù)統(tǒng)計表

路由數(shù) 算法 發(fā)送包數(shù) 接收包數(shù) 接收成功率

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表明兩種算法在網(wǎng)絡(luò)數(shù)據(jù)包接收成功率方面大體一致。圖2橫軸表示兩種算法搜索最優(yōu)路徑所用的時間，縱軸表示網(wǎng)絡(luò)的復雜度（本文采用網(wǎng)絡(luò)路由數(shù)量衡量），左右圖分別表示Dijkstra和遺傳遺傳算法復雜度。舍棄兩圖中剛開始統(tǒng)計的不合理數(shù)據(jù)，通過對比可以看出隨著網(wǎng)絡(luò)規(guī)模的擴大，Dijkstra搜索最優(yōu)路徑時間的增幅要明顯快于遺傳算法搜索最優(yōu)路徑時間的增幅。

綜上所述，遺傳路由算法可以降低柵格化通信網(wǎng)絡(luò)路由算法的復雜度。

[參考文獻]

[1]汪陶先.信息柵格與通信柵格[J].現(xiàn)代通信技術(shù)，2004（4）：1-6.

[2]范淑艷，熊高云.柵格通信網(wǎng)絡(luò)體系機構(gòu)及關(guān)鍵技術(shù)研究.西安電子科技大學學報，2009（6）：990-995

[3]黃天章，等.面向通信網(wǎng)絡(luò)服務(wù)架構(gòu)的通信網(wǎng)絡(luò)設(shè)計分析.通信系統(tǒng)與網(wǎng)絡(luò)技術(shù)，2012（3）：5-8.

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

[5]張培珍，楊根源，等.全球信息柵格服務(wù)質(zhì)量互通性研究[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