基于動態(tài)路徑誘導(dǎo)的網(wǎng)絡(luò)路由技術(shù)

摘要：隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，一些基于純數(shù)學(xué)模型的路由算法已經(jīng)面臨新的挑戰(zhàn)。針對網(wǎng)絡(luò)路由對實(shí)時性和可靠性的要求，采用動態(tài)路徑誘導(dǎo)算法對網(wǎng)絡(luò)流量進(jìn)行實(shí)時預(yù)測，可以解決傳統(tǒng)的誘導(dǎo)算法存在的時變性差和收斂慢的問題。動態(tài)路徑誘導(dǎo)算法基于神經(jīng)網(wǎng)絡(luò)時間預(yù)測模型和遺傳算法，經(jīng)仿真表明該動態(tài)路徑誘導(dǎo)方法在網(wǎng)絡(luò)繁忙時能顯著改善網(wǎng)絡(luò)路由性能。

關(guān)鍵詞：遺傳算法；動態(tài)路徑誘導(dǎo)；最優(yōu)路徑；神經(jīng)網(wǎng)絡(luò)

Abstract:Withtheconstantexpansion of the network size, some routing algorithms based on pure mathematical models have been confronted with new challenges. In order to meet the requirements for real-time and reliability of network routing, a new dynamic route guidance method resolved the limitation of traditional dynamic route guidance algorithm by forecasting the network traffic and composing real-time road weight matrix. This method is based on Neural Network (NN) and Genetic Algorithm (GA), and it has been proven by lab experiments that it can significantly optimize the performance of network routing in the busy network.

Keywords:geneticalgorithm;dynamic route guidance; optimal route; neural network

隨著各種網(wǎng)絡(luò)設(shè)備、高帶寬的傳輸媒質(zhì)和豐富多彩的網(wǎng)絡(luò)內(nèi)容不斷涌現(xiàn)，一些基于純數(shù)學(xué)模型的路由算法已面臨挑戰(zhàn)。基于神經(jīng)網(wǎng)絡(luò)和遺傳算法的動態(tài)路徑誘導(dǎo)方法，可以有效地保證在復(fù)雜多變的網(wǎng)絡(luò)環(huán)境下最優(yōu)選路的及時性和準(zhǔn)確性。

1  網(wǎng)絡(luò)路由概述

網(wǎng)絡(luò)路由發(fā)生在開放系統(tǒng)互聯(lián)(OSI)七層協(xié)議規(guī)定的第三層網(wǎng)絡(luò)層，分為轉(zhuǎn)發(fā)和選路，在此只考慮選路問題。當(dāng)分組從發(fā)送方流向接受方時，網(wǎng)絡(luò)層必須決定這些分組所采用的路徑或者路由，計算這些路徑的算法稱為選路算法，例如在圖1中一個選路算法將決定分組從主機(jī)PC1到達(dá)PC2所遵循的路徑。

用圖論中的模型來表示路由選路，圖G=(N,E),其中N是網(wǎng)絡(luò)環(huán)境中的路由設(shè)備集合(n1,n2……nn)，E是路由設(shè)備之間的路徑集合。對于E中的每一條邊用c(v1,v2)表示，表示v1和v2之間的單位路由費(fèi)用量，具體費(fèi)用可以在幾個基礎(chǔ)上進(jìn)行運(yùn)算再制定。若v1和v2之間不通就用∞表示，實(shí)際應(yīng)用中就用一個很大的整數(shù)值表示該邊不存在。將各邊組織成一個矩陣W={c(v1,v2)) v1,v2∈N}，此時W就反映了這個時間段的網(wǎng)絡(luò)路由代價情況。根據(jù)不同的路由目標(biāo)可以制定不同的路由邊權(quán)值，例如可以將數(shù)據(jù)包通過此段路徑的平均時間作為權(quán)值，可以將數(shù)據(jù)包的最短選路路徑做為權(quán)值，可以將數(shù)據(jù)包選路費(fèi)用作為權(quán)值，還可以根據(jù)特殊的要求制定不同的權(quán)值賦予不同的含義。

2  動態(tài)選路誘導(dǎo)算法

現(xiàn)有的網(wǎng)絡(luò)路由算法一旦選定路徑就會按照既定的路徑路由，即使這條路徑上的網(wǎng)絡(luò)流量已經(jīng)飽和，而Internet上網(wǎng)絡(luò)流量隨時都在發(fā)生變化，因此勢必會造成網(wǎng)絡(luò)選路的進(jìn)一步惡化和無限的路由延遲。動態(tài)選路誘導(dǎo)算法依據(jù)神經(jīng)網(wǎng)絡(luò)和遺傳算法中染色體變異原理，根據(jù)選路路徑上前一段時間的網(wǎng)絡(luò)流量進(jìn)行下一步的路由路徑選擇，使網(wǎng)絡(luò)中各路由節(jié)點(diǎn)不會出現(xiàn)一些非常忙碌而另一些非常空閑的情況，同時減少了選路時延，增強(qiáng)了網(wǎng)絡(luò)程序的時用性。

2.1神經(jīng)網(wǎng)絡(luò)路由時間預(yù)測模型

神經(jīng)網(wǎng)絡(luò)模型可以演變出新型的數(shù)據(jù)建模方法，它具有非線性、適應(yīng)性與集成性等特點(diǎn)，能夠準(zhǔn)確、有效地實(shí)現(xiàn)路由信息的預(yù)測。神經(jīng)網(wǎng)絡(luò)路由時間預(yù)測模型由數(shù)據(jù)處理器和神經(jīng)網(wǎng)絡(luò)組成，將實(shí)測的路由時間數(shù)據(jù)和網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行處理構(gòu)成輸入樣本，分為輸入層、隱層和輸出層3層結(jié)構(gòu)。

設(shè)qi(τ)為路段i上τ時刻的網(wǎng)絡(luò)流量向量，qi(τ-1)為路段i上τ-1時刻的網(wǎng)絡(luò)流量向量，Qi(τ)=[q1(τ)，q2(τ)……qd(τ)]；d為所研究網(wǎng)絡(luò)的某條選路的路徑跳數(shù)總和，若只考慮研究選路路徑的網(wǎng)絡(luò)流量，則置d =1；設(shè)ti(τ)為路段i上τ時刻的行程時間向量，ti(τ-1)為τ-1時刻的行程時間向量,Ti(τ)=[t1(τ)，t2(τ)……td (τ)]�？紤]到路徑的費(fèi)用和網(wǎng)絡(luò)流的特性，采用當(dāng)前時間段和前m個時間段的網(wǎng)絡(luò)流量和選路時間對未來時間段的選路時間進(jìn)行預(yù)測。將 Qi(τ)， Qi (τ-1)…… Qi(τ-m)和Ti(τ)，Ti(τ-1)……Ti(τ-m)作為輸入，Ti(τ+1)為輸出值[1]，具體模型如圖2所示。

根據(jù)神經(jīng)網(wǎng)絡(luò)預(yù)測模型計算可以得到的某時刻計算機(jī)網(wǎng)絡(luò)各路徑的權(quán)重[2]，即平均路由時間Xij，表示在某時刻從節(jié)點(diǎn)i 路由到節(jié)點(diǎn)j 所花費(fèi)的時間，如果兩節(jié)點(diǎn)間的路徑不連通，則Xij的值等于一個大于所有路徑的權(quán)值的和的值M。

2.2基于遺傳算法的最優(yōu)網(wǎng)絡(luò)路由選路算法

該算法首先根據(jù)遺傳算法中的染色體上基因的排列規(guī)則排列路由節(jié)點(diǎn)，節(jié)點(diǎn)的所有排列順序就是所研究網(wǎng)絡(luò)中的路由選路路徑，然后通過染色體交叉、變異對初始生成的選路路徑進(jìn)行優(yōu)化，經(jīng)過一定代數(shù)的變異遺傳，得到最優(yōu)的選路路徑。

(1) 染色體的編碼

最優(yōu)路徑選擇算法中的基因是路由節(jié)點(diǎn)，這些節(jié)點(diǎn)的排列順序就是所要求的路徑，所以采取有序的實(shí)數(shù)編碼方式[3]。

(2) 適應(yīng)度函數(shù)的確定

在遺傳計算前期，根據(jù)每個染色體的有效基因片段，即染色體中連通的節(jié)點(diǎn)數(shù)p定義適應(yīng)度函數(shù)，即f(k)=p(k)/(1+pmax)，其中p(k)表示第k個染色體的有效基因片段數(shù)，pmax表示這一代所有個體中最大的有效基因片段數(shù)，加1是為避免出現(xiàn)適應(yīng)度值為1的情況；當(dāng)計算進(jìn)行到某一遺傳代數(shù)，以染色體的路阻(路由費(fèi)用)和定義適應(yīng)度函數(shù)。定義p為某一染色體從O到D所經(jīng)過的路徑的路阻之和，即該染色體的目標(biāo)函數(shù)p=∑d(i,j ),d(i,j )為i和j 之間的費(fèi)用，則適應(yīng)度函數(shù)為f (k)=1-p(k)/∑p(i )，其中k =1，2，3……M，M為群體規(guī)模[4]。

(3) 染色體的交叉

在父母染色體A、B中隨機(jī)地選取一個交叉點(diǎn)Q，交叉點(diǎn)Q不能為起點(diǎn)和終點(diǎn)，Q至少應(yīng)從第三個節(jié)點(diǎn)開始；當(dāng)Max(PA,PB)≥Min(ZA,ZB)時，雙親染色體不交叉，以保證有效基因片段和零基因不被交叉，其中Z表示染色體中非零基因的個數(shù)；當(dāng)Max(PA,PB)≤Min(ZA,ZB)時，Q應(yīng)在Max(PA,PB)和Min(ZA,ZB)之間,以保證父母染色體的有效基因片段不被破壞，并去除交叉所得兩個新染色體中重復(fù)的節(jié)點(diǎn)和冗余節(jié)點(diǎn)，在染色體的末端補(bǔ)0[4]。

(4) 染色體的變異

將無效基因片段的第一位進(jìn)行變異，變異后的染色體如果比原染色體的有效基因片段長，即P值增加，則替換母染色體，否則不予替換；當(dāng)無效基因片段的第一位為D，且該染色體是不合理的，則在D的前一個位置插入一個節(jié)點(diǎn)，插入后要保證所得染色體仍是合法的，即符合編碼規(guī)則，且不能改變?nèi)旧�體的長度。染色體的選擇：首先將本代染色體經(jīng)輪盤賭選擇、交叉、變異后得到下一代染色體。由于在前幾代的遺傳計算中，大量的染色體都是不合理的，因此，將本代中合理的染色體代替下一代中基因片段小的不合理的染色體；如果本代中沒有合理的染色體，則不進(jìn)行替換。當(dāng)遺傳計算進(jìn)行到一定代數(shù)時，染色體大部分是合理的，這時將本代路阻(選路費(fèi)用)和最小的染色體與下一代路阻(算路費(fèi)用)和最大的染色體進(jìn)行比較，如果本代最優(yōu)的染色體比下一代最差染色體的路阻小，則進(jìn)行替換，反之則不替換；如果本代群體中路阻和最小的個體不是合理的路徑，也不進(jìn)行替換操作。

(5) 染色群體的更新方式

群體的設(shè)計需要平衡群體多樣性維護(hù)和快速收斂，從數(shù)學(xué)的角度講，允許父輩中的優(yōu)良個體進(jìn)入下一輪的競爭確保了最優(yōu)解的迭代穩(wěn)定性，而將后代中劣化的個體提前淘汰出局加速了尋優(yōu)過程的實(shí)現(xiàn)。采取讓子代中的優(yōu)秀個體和父輩中的優(yōu)良個體同時進(jìn)入下一代的群體更新方式，即父輩個體經(jīng)過交叉、變異操作后得到臨時子個體，將父輩個體和臨時子代個體進(jìn)行比較，選擇適應(yīng)度高的個體作為子代個體進(jìn)入下一代的競爭。這種群體更新方式能保證每一次交叉、變異操作都將產(chǎn)生兩個更好的子個體，從而保證該算法的收斂性。

3  仿真研究

研究結(jié)果用如圖3所示的網(wǎng)絡(luò)連接圖測試。

以路由時間最短作為最優(yōu)目標(biāo)，通過神經(jīng)網(wǎng)絡(luò)對路由網(wǎng)各路徑任意時刻的平均路由時間進(jìn)行預(yù)測，動態(tài)地得出該路網(wǎng)任意時刻的權(quán)重。取t -1、t -2、t -3、t -4四個時間段路網(wǎng)的數(shù)據(jù)流量和平均路由時間作為神經(jīng)網(wǎng)絡(luò)的輸入，因此神經(jīng)網(wǎng)絡(luò)輸入層取8個節(jié)點(diǎn)；輸出層取1個節(jié)點(diǎn)，輸出為t時刻該路由網(wǎng)各路徑的行程時間。根據(jù)實(shí)驗(yàn)，隱層取3個節(jié)點(diǎn)。由神經(jīng)網(wǎng)絡(luò)預(yù)測所得t時刻路網(wǎng)各路段的平均行程時間構(gòu)成路阻矩陣，路阻矩陣的大小是16×16，兩節(jié)點(diǎn)間的路段不連通時，用一個大于所有路阻和的數(shù)1 000表示。

求得t 時刻路網(wǎng)的路阻矩陣后，采用遺傳算法進(jìn)行最優(yōu)路徑的選擇，遺傳算法參數(shù)的確定如下：由于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為16，所以染色體的編碼長度為16。綜合考慮論文所研究的網(wǎng)絡(luò)規(guī)模、遺傳算法的求解精度和遺傳算法的收斂速度等方面的因素，并通過多次仿真實(shí)驗(yàn)的驗(yàn)證可知，種群規(guī)模選為160時，最優(yōu)路徑選擇算法的性能最好。經(jīng)仿真實(shí)驗(yàn)驗(yàn)證，遺傳終止代數(shù)可取為8[5]。

用Matlab對上述試驗(yàn)?zāi)Ｐ瓦M(jìn)行仿真試驗(yàn)，仿真結(jié)果表明，對于86個OD對尋優(yōu)，遺傳算法計算得到77條最優(yōu)路徑，83條有效路徑，求解準(zhǔn)確率為0.895，有效率為0.989，平均尋優(yōu)時間為8 ms~15 ms，滿足了路徑誘導(dǎo)的準(zhǔn)確性和實(shí)時性。

對隨機(jī)產(chǎn)生的OD對(1，16)分別求解t1、t2、t3時刻的最優(yōu)路徑，可得R1為t1時刻最優(yōu)路徑1-5-6-11-12-16，R2為t2時刻最優(yōu)路徑1-2-6-11-15-16，R3為t3時刻最短路徑1-2-3-4-8-12-16。具體計算結(jié)果見表1所示。

從表1可以看出，當(dāng)網(wǎng)絡(luò)流量在不斷變化時，在不同時刻對應(yīng)各條路徑的費(fèi)用也在不斷的變化，路徑最短的所需的費(fèi)用并不是最少的。

4  結(jié)束語

實(shí)驗(yàn)室模擬條件下不存在路由擁塞導(dǎo)致的網(wǎng)絡(luò)延遲以及真實(shí)環(huán)境中存在各種網(wǎng)絡(luò)問題。從表3的試驗(yàn)結(jié)果來看，基于神經(jīng)網(wǎng)絡(luò)的遺傳算法的動態(tài)路徑誘導(dǎo)算法在動態(tài)路由中可以得到很好的預(yù)測流量，并且最優(yōu)路徑的求解率達(dá)到89.5％、有效率達(dá)到98.9％，解決了傳統(tǒng)的誘導(dǎo)算法帶來的收斂慢的問題，滿足路由的實(shí)時性。但是對于大規(guī)模的復(fù)雜的Internet路由，需要做進(jìn)一步的研究來保證選路問題的及時性和收斂性，從而使選路在各方面得到最優(yōu)化保證。

5  參考文獻(xiàn)

[1]景玲,黃席樾,潘婭. 基于遺傳算法的動態(tài)路徑誘導(dǎo)[J]. 重慶大學(xué)學(xué)報, 2002, 25(4): 68-71.

[2]徐仙偉,葉小嶺.遺傳算法優(yōu)化BP網(wǎng)絡(luò)初始權(quán)重用于入侵檢測[J].計算機(jī)應(yīng)用研究,2005,22(3): 127-128, 132.

[3]吳成東,楊麗英,許可.神經(jīng)網(wǎng)絡(luò)和遺傳算法在動態(tài)路徑誘導(dǎo)中的應(yīng)用[J].計算機(jī)應(yīng)用研究,2006,25(4): 23-28.

[4]FUL.An adaptive routing algorithm for in-vehicle route guidance systems with real-time information [J].Transportation Research: Part B, 2001, 35( 8) : 749-765.

[5]Wahlej,Annen o, Schuster c, et al. A dynamic route guidance system based on real traffic data [J]. European Journal of Operational Research, 2001, 13(1): 302-308.

作者簡介：

朱能方，本科畢業(yè)于安徽大學(xué)，碩士畢業(yè)于電子科技大學(xué)�，F(xiàn)工作于中興通訊股份有限公司，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全。黃迪明，電子科技大學(xué)計算機(jī)系教授。主要研究方向?yàn)榫W(wǎng)絡(luò)信息技術(shù)、信息安全、軟件工程等，已發(fā)表學(xué)術(shù)論文20余篇。