本站小編為你精心準備了動態(tài)最優(yōu)路徑技術(shù)誘導(dǎo)方法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

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

Abstract:Withtheconstantexpansionofthenetworksize,someroutingalgorithmsbasedonpuremathematicalmodelshavebeenconfrontedwithnewchallenges.Inordertomeettherequirementsforreal-timeandreliabilityofnetworkrouting,anewdynamicrouteguidancemethodresolvedthelimitationoftraditionaldynamicrouteguidancealgorithmbyforecastingthenetworktrafficandcomposingreal-timeroadweightmatrix.ThismethodisbasedonNeuralNetwork(NN)andGeneticAlgorithm(GA),andithasbeenprovenbylabexperimentsthatitcansignificantlyoptimizetheperformanceofnetworkroutinginthebusynetwork.

隨著各種網(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)選路的及時性和準確性。

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

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

用圖論中的模型來表示路由選路，圖G=(N,E),其中N是網(wǎng)絡(luò)環(huán)境中的路由設(shè)備集合(n1,n2……nn)，E是路由設(shè)備之間的路徑集合。對于E中的每一條邊用c(v1,v2)表示，表示v1和v2之間的單位路由費用量，具體費用可以在幾個基礎(chǔ)上進行運算再制定。若v1和v2之間不通就用∞表示，實際應(yīng)用中就用一個很大的整數(shù)值表示該邊不存在。將各邊組織成一個矩陣W={c(v1,v2))v1,v2∈N}，此時W就反映了這個時間段的網(wǎng)絡(luò)路由代價情況。根據(jù)不同的路由目標可以制定不同的路由邊權(quán)值，例如可以將數(shù)據(jù)包通過此段路徑的平均時間作為權(quán)值，可以將數(shù)據(jù)包的最短選路路徑做為權(quán)值，可以將數(shù)據(jù)包選路費用作為權(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ò)選路的進一步惡化和無限的路由延遲。動態(tài)選路誘導(dǎo)算法依據(jù)神經(jīng)網(wǎng)絡(luò)和遺傳算法中染色體變異原理，根據(jù)選路路徑上前一段時間的網(wǎng)絡(luò)流量進行下一步的路由路徑選擇，使網(wǎng)絡(luò)中各路由節(jié)點不會出現(xiàn)一些非常忙碌而另一些非常空閑的情況，同時減少了選路時延，增強了網(wǎng)絡(luò)程序的時用性。

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

神經(jīng)網(wǎng)絡(luò)模型可以演變出新型的數(shù)據(jù)建模方法，它具有非線性、適應(yīng)性與集成性等特點，能夠準確、有效地實現(xiàn)路由信息的預(yù)測。神經(jīng)網(wǎng)絡(luò)路由時間預(yù)測模型由數(shù)據(jù)處理器和神經(jīng)網(wǎng)絡(luò)組成，將實測的路由時間數(shù)據(jù)和網(wǎng)絡(luò)流量數(shù)據(jù)進行處理構(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(τ)]。考慮到路徑的費用和網(wǎng)絡(luò)流的特性，采用當前時間段和前m個時間段的網(wǎng)絡(luò)流量和選路時間對未來時間段的選路時間進行預(yù)測。將Qi(τ)，Qi(τ-1)……Qi(τ-m)和Ti(τ)，Ti(τ-1)……Ti(τ-m)作為輸入，Ti(τ+1)為輸出值[1]，具體模型如圖2所示。

根據(jù)神經(jīng)網(wǎng)絡(luò)預(yù)測模型計算可以得到的某時刻計算機網(wǎng)絡(luò)各路徑的權(quán)重[2]，即平均路由時間XIJ，表示在某時刻從節(jié)點I路由到節(jié)點J所花費的時間，如果兩節(jié)點間的路徑不連通，則XIJ的值等于一個大于所有路徑的權(quán)值的和的值M。,XbR/K[dJ*N"eUo#cA$~^bw+2GFic9測控技術(shù)論文UzsOX€zCjY6dN}€;||i5

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

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

(1)染色體的編碼

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

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

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

論文動態(tài)最優(yōu)路徑技術(shù)的路徑誘導(dǎo)方法來自免費

(3)染色體的交叉

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

(4)染色體的變異

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

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

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

3仿真研究

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

以路由時間最短作為最優(yōu)目標，通過神經(jīng)網(wǎng)絡(luò)對路由網(wǎng)各路徑任意時刻的平均路由時間進行預(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é)點；輸出層取1個節(jié)點，輸出為T時刻該路由網(wǎng)各路徑的行程時間。根據(jù)實驗，隱層取3個節(jié)點。由神經(jīng)網(wǎng)絡(luò)預(yù)測所得T時刻路網(wǎng)各路段的平均行程時間構(gòu)成路阻矩陣，路阻矩陣的大小是16×16，兩節(jié)點間的路段不連通時，用一個大于所有路阻和的數(shù)1000表示。

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

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

對隨機產(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可以看出，當網(wǎng)絡(luò)流量在不斷變化時，在不同時刻對應(yīng)各條路徑的費用也在不斷的變化，路徑最短的所需的費用并不是最少的。

4結(jié)束語

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

5參考文獻

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

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

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

[4]FUL.Anadaptiveroutingalgorithmforin-vehiclerouteguidancesystemswithreal-timeinformation[J].TransportationResearch:PartB,2001,35(8):749-765.

[5]Wahlej,Anneno,Schusterc,etal.Adynamicrouteguidancesystembasedonrealtrafficdata[J].EuropeanJournalofOperationalResearch,2001,13(1):302-308.