遺傳路由算法在柵格通信網(wǎng)中的應(yīng)用

康江 馮釗 喬瑞娟 張雅男

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

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

隨著通信、計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，通信網(wǎng)絡(luò)以綜合業(yè)務(wù)、異構(gòu)網(wǎng)絡(luò)資源共享為發(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)格，支持在動(dò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ù)和集成應(yīng)用等主要通信網(wǎng)絡(luò)功能還需具備規(guī)模和功能擴(kuò)展、平臺(tái)和網(wǎng)絡(luò)開放及資源的有限共享、端到端高性能的通信能力等特征[3]。

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

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

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

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

3 遺傳路由算法的應(yīng)用

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

3.1 種群初始化

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

3.2 適應(yīng)度函數(shù)

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

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

3.3 遺傳的操作

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

[參考文獻(xiàn)]

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

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

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

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

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