基于動態路徑誘導的網絡路由技術

摘要：隨著網絡規模的不斷擴大，一些基于純數學模型的路由算法已經面臨新的挑戰。針對網絡路由對實時性和可靠性的要求，采用動態路徑誘導算法對網絡流量進行實時預測，可以解決傳統的誘導算法存在的時變性差和收斂慢的問題。動態路徑誘導算法基于神經網絡時間預測模型和遺傳算法，經仿真表明該動態路徑誘導方法在網絡繁忙時能顯著改善網絡路由性能。

關鍵詞：遺傳算法；動態路徑誘導；最優路徑；神經網絡

Abstract: With the constant expansion 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.

Key words: genetic algorithm; dynamic route guidance; optimal route; neural network

隨著各種網絡設備、高帶寬的傳輸媒質和豐富多彩的網絡內容不斷涌現，一些基于純數學模型的路由算法已面臨挑戰。基于神經網絡和遺傳算法的動態路徑誘導方法，可以有效地保證在復雜多變的網絡環境下最優選路的及時性和準確性。

1 網絡路由概述

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

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

2 動態選路誘導算法

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

2.1 神經網絡路由時間預測模型

神經網絡模型可以演變出新型的數據建模方法，它具有非線性、適應性與集成性等特點，能夠準確、有效地實現路由信息的預測。神經網絡路由時間預測模型由數據處理器和神經網絡組成，將實測的路由時間數據和網絡流量數據進行處理構成輸入樣本，分為輸入層、隱層和輸出層3層結構。

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

根據神經網絡預測模型計算可以得到的某時刻計算機網絡各路徑的權重[2]，即平均路由時間Xij，表示在某時刻從節點i 路由到節點j 所花費的時間，如果兩節點間的路徑不連通，則Xij的值等于一個大于所有路徑的權值的和的值M。

2.2 基于遺傳算法的最優網絡路由

選路算法

該算法首先根據遺傳算法中的染色體上基因的排列規則排列路由節點，節點的所有排列順序就是所研究網絡中的路由選路路徑，然后通過染色體交叉、變異對初始生成的選路路徑進行優化，經過一定代數的變異遺傳，得到最優的選路路徑。

(1) 染色體的編碼

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

(2) 適應度函數的確定

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

(3) 染色體的交叉

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

(4) 染色體的變異

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

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

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

3 仿真研究

研究結果用如圖3所示的網絡連接圖測試。

以路由時間最短作為最優目標，通過神經網絡對路由網各路徑任意時刻的平均路由時間進行預測，動態地得出該路網任意時刻的權重。取

t -1、t -2、t -3、t -4四個時間段路網的數據流量和平均路由時間作為神經網絡的輸入，因此神經網絡輸入層取8個節點；輸出層取1個節點，輸出為t時刻該路由網各路徑的行程時間。根據實驗，隱層取3個節點。由神經網絡預測所得t時刻路網各路段的平均行程時間構成路阻矩陣，路阻矩陣的大小是16×16，兩節點間的路段不連通時，用一個大于所有路阻和的數1 000表示。

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

用Matlab對上述試驗模型進行仿真試驗，仿真結果表明，對于86個OD對尋優，遺傳算法計算得到77條最優路徑，83條有效路徑，求解準確率為0.895，有效率為0.989，平均尋優時間為8 ms~15 ms，滿足了路徑誘導的準確性和實時性。

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

從表1可以看出，當網絡流量在不斷變化時，在不同時刻對應各條路徑的費用也在不斷的變化，路徑最短的所需的費用并不是最少的。

4 結束語

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

5 參考文獻

[1] 景玲， 黃席樾， 潘婭. 基于遺傳算法的動態路徑誘導[J]. 重慶大學學報， 2002， 25(4): 68-71.

[2] 徐仙偉，葉小嶺.遺傳算法優化BP網絡初始權重用于入侵檢測[J].計算機應用研究， 2005， 22(3): 127-128， 132.

[3] 吳成東，楊麗英，許可.神經網絡和遺傳算法在動態路徑誘導中的應用[J].計算機應用研究， 2006， 25(4): 23-28.

[4] FU L. 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] Wahle j， 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.

收稿日期：2007-09-06

朱能方，本科畢業于安徽大學，碩士畢業于電子科技大學。現工作于中興通訊股份有限公司，主要研究方向為網絡信息安全。

黃迪明，電子科技大學計算機系教授。主要研究方向為網絡信息技術、信息安全、軟件工程等，已發表學術論文20余篇。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”