動(dòng)態(tài)最優(yōu)路徑技術(shù)誘導(dǎo)方法范文

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

關(guān)鍵詞：動(dòng)態(tài)最優(yōu)路徑,遺傳算法；動(dòng)態(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ò)和遺傳算法的動(dòng)態(tài)路徑誘導(dǎo)方法，可以有效地保證在復(fù)雜多變的網(wǎng)絡(luò)環(huán)境下最優(yōu)選路的及時(shí)性和準(zhǔn)確性。

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

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

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

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

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

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

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

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

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

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

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

(1)染色體的編碼

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

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

在遺傳計(jì)算前期，根據(jù)每個(gè)染色體的有效基因片段，即染色體中連通的節(jié)點(diǎn)數(shù)P定義適應(yīng)度函數(shù)，即F(K)=P(K)/(1+PMAX)，其中P(K)表示第K個(gè)染色體的有效基因片段數(shù)，PMAX表示這一代所有個(gè)體中最大的有效基因片段數(shù)，加1是為避免出現(xiàn)適應(yīng)度值為1的情況；當(dāng)計(jì)算進(jìn)行到某一遺傳代數(shù)，以染色體的路阻(路由費(fèi)用)和定義適應(yīng)度函數(shù)。定義P為某一染色體從O到D所經(jīng)過(guò)的路徑的路阻之和，即該染色體的目標(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]。

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

(3)染色體的交叉

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

(4)染色體的變異

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

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

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

3仿真研究

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

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

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

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

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

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

4結(jié)束語(yǔ)

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

5參考文獻(xiàn)

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

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

[3]吳成東,楊麗英,許可.神經(jīng)網(wǎng)絡(luò)和遺傳算法在動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用[J].計(jì)算機(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.