基于神經網絡實現QOS路由優化研究

陳曉琳

【摘 要】本文結合BP神經算法特性，分析了BP神經算法在解決QOS問題的可行性，并提出了解決該問題的有效算法模型，詳細說明了如何運用該模型算法來解決QOS多播路由決策的問題。

【關鍵詞】神經網絡；QOS路由；優化算法

1 基于BP神經網路優化的可行性分析

由于BP神經網絡是一個既向前傳播也能向后傳播的過程。它在多級網絡中，可以計算出隱藏層的任何神經元的誤差。它利用最后輸出端的誤差計算出前一個神經元輸出端的誤差，并再次利用這個誤差值估計出更前一層的誤差值。循環下來，就可獲得所有其他各層的誤差估計。這誤差估計雖然它本身的精度會在向后傳播的過程中不斷降低，但卻可以為多層網絡的訓練提供有效算法。

BP神經網絡作為一個有導師訓練的網絡。在輸入一個向量時，也會被要求給出對應的一個理想輸出向量，使網絡中出現異相聯的映射。也就是輸入向量與對應的輸出向量之間構成一個“訓練對”。

根據以上的研究分析，我們可以得出采用有導師學習的訓練方法，需進行以下步驟：1）從訓練的樣本集合中取一個樣本（Ai，Bi）；2）計算神經網絡中的實際輸出O；3）求D=Bi-O；4）根據D調整權矩陣W；5）對每個樣本重復上述過程，直到對整個樣本集來說，誤差不超過規定范圍。

BP神經網絡向前傳播訓練方法：1）從樣本集中取一個樣本（XP，YP）；2）計算相應的實際輸出OP；

在這個過程中，信息從輸入層經過逐級的變換，傳送到輸出層。它是在網絡完成訓練后正常執行的過程，這個過程在網絡中執行以下運算：

OP=Fn（...F2（F1（XPW（1））W（2））...）W（n））

BP神經網絡向后傳播階段訓練方法[1]：1）計算實際輸出Op與相應的理想輸出Yp的差；2）依照極小化誤差的方式來調整網絡的權矩陣。

以上兩個階段的訓練方法都必須受到精度的控制，即：

Ep=■■（ypj-Opj）2

以上即作為網絡中關于第p個樣本的誤差測度。而將網絡關于整個樣本集的誤差測度定義為E=■Ep

值得注意的是，在開始調整神經元的連接權時，得先求出輸出層的誤差，而其它層的誤差要通過此誤差反向逐層推算后才能得到。

那么在這里還要注意誤差傳播分析中輸出層權和隱藏層權的調整，下圖是ANP到ANq接：

圖1

ANP是輸出層的第q個神經元，Wpq是從其前導層的第p個神經元到ANq得聯接權。取wpq=wpq+Δwpq （1）

據Delta規則Wij（t+1）=W（t）+α（yi-aj（t））O（t） （2）

有Δwpq=αδvp （3）

那么在實際的路由問題中，我們就可以利用神經網絡這種不斷調整其連接權值或閥值的過程來不斷的為我們每一個節點選擇其最優的路由決定，并最終達到整個路徑或延時方面的最優化。每一個節點中的神經元會根據每一次反饋過來的信息進行下一步選擇。但由于每個節點同時存在很多不同的相連的路徑，那么數據會通過各個不同路徑先向前傳播，然后根據最終到達目的節點的信息反饋到源節點，供其參考，最后選擇最終合適的路徑。

2 QOS路由優化算法的實現

被調整后的神經網絡連接權值，可以使任意一個輸入都可在網絡對中得到最佳的的輸出或者結果，這也是BP神經網絡學習的最終目的。正向傳播和反向傳播構成了BP神經網絡的學習過程。正向傳播按照字面意思，就肯定是向前傳遞網絡信息，并針對某一輸入值得到相應輸出結果；而反向傳播既是向后一層一層的傳遞誤差值，不斷地向后反饋信息，調整每個神經元之間的的連接權值，使網絡在得到不同的輸入信息后都能經過正確的計算得到最佳的輸出結果，并且誤差得保持在一定的范圍之內。

BP神經算法的學習方法是對需要得到訓練的樣本進行針對網絡權值的調整的訓練。每組都由相應的輸入以及希望得到的輸出這兩個結構的組成。在向前傳播的過程中，將需要得到訓練的樣本輸入，通過每一個神經元進行處理，并最終到達輸出。在這整個過程中，上一級的神經元就會影響到下一級的神經元，如果通過層層傳播，最終得到的結果不是期望的結果，就會進行下一步，向后傳播。

向后傳播則是將誤差信號依照原來的方式向后傳播，傳播的過程中根據一定的規則對每個節點的權重閥值進行更改，這個過程直到到達最開始的神經元才停止，轉而開始上面的步驟，向前傳播。這個過程循環往復下去，直至最終的輸出結果達到期望的要求，那么這個時候算法的學習才算完畢，否則，繼續往復下去。

學習過程的循環往復，最終到整個神經網絡得到理想的結果為止。在這里需要注意的是，神經網絡在進行訓練的實際過程中，是只有向前傳播而沒有向后傳播的。

具體步驟如下：在此次學習算法中，只考慮QOS路由的最小跳轉數，根據BP神經網絡模型的相關理論，本文首先建立一個反饋式神經網絡路由分配計算機結構。

定義反饋函數R，它表示反向傳播中對神經網絡的反饋：1）定義參考數值P；2）若Rk≥Pk-1，那么有W+ij修正為w+ji+Rk； w-jt修正為w-jt+Rk/（n-1） .（ t≠i）

當該路徑的回饋函數大于等于P，到達神經元j的所有正權重加強，這個就意味改路徑下次被使用的機率增大，而且其它的負權重會相應加強些許，以期達到平衡。反之，神經元j的負權重被加強，該路徑被使用的機率減小，而且其正權重相應加強達到平衡。

在此例中，節點A到目的節點F，路徑（A，C，F）跳轉2次，測量數據包返回起始節點A，獲得的路徑值為2。α為學習速率，用來控制反饋函數的取值范圍。若α值取0.5，路徑（A，C，F）的反饋函數為1，路徑（A，E，C，F）的反饋值為0.667，很顯然前一個路徑為改變權重值做出最大的貢獻，那么神經元就優先選擇該路徑。

3 BP神經網絡算法過程

1）分別對輸入層到隱含層的權值、隱含層到輸出層的權值和輸入層到隱含層的閥值進行初始化。（其中p0表示訓練樣本輸入；t0表示訓練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經元數目；r表示迭代次數；lv表示權值學習率；lf表示閥值學習率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權值

v=rand（1，n（1））； %初始化隱含層到輸出層的權值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計算隱含層的輸出

o3=v*o2+theta2； %計算輸出層的輸出

e=t（：，g0）-o3；

3）對神經網絡中的各層次進行訓練，即對輸出層、隱含層和輸入層進行閥值調整。

theta2=theta2+lf*e； %調整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調整輸入層至隱含層權值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調整隱含層閥值

w=w+lv*o1*g； %調整隱含層至輸出層權值

4 結語

本文針對QOS的特診及相應的一些參數特點，構建了QOS組播路由的數學模型。然后在此基礎之上利用神經網絡的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經網絡算法作為參考依據的原因。和算法過程。

【參考文獻】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經網絡學習的神經網絡控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網絡技術與應用[M].北京：人民郵電出版社，2003，3：15-16.

[責任編輯：丁艷]

3 BP神經網絡算法過程

1）分別對輸入層到隱含層的權值、隱含層到輸出層的權值和輸入層到隱含層的閥值進行初始化。（其中p0表示訓練樣本輸入；t0表示訓練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經元數目；r表示迭代次數；lv表示權值學習率；lf表示閥值學習率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權值

v=rand（1，n（1））； %初始化隱含層到輸出層的權值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計算隱含層的輸出

o3=v*o2+theta2； %計算輸出層的輸出

e=t（：，g0）-o3；

3）對神經網絡中的各層次進行訓練，即對輸出層、隱含層和輸入層進行閥值調整。

theta2=theta2+lf*e； %調整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調整輸入層至隱含層權值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調整隱含層閥值

w=w+lv*o1*g； %調整隱含層至輸出層權值

4 結語

本文針對QOS的特診及相應的一些參數特點，構建了QOS組播路由的數學模型。然后在此基礎之上利用神經網絡的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經網絡算法作為參考依據的原因。和算法過程。

【參考文獻】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經網絡學習的神經網絡控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網絡技術與應用[M].北京：人民郵電出版社，2003，3：15-16.

[責任編輯：丁艷]

3 BP神經網絡算法過程

1）分別對輸入層到隱含層的權值、隱含層到輸出層的權值和輸入層到隱含層的閥值進行初始化。（其中p0表示訓練樣本輸入；t0表示訓練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經元數目；r表示迭代次數；lv表示權值學習率；lf表示閥值學習率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權值

v=rand（1，n（1））； %初始化隱含層到輸出層的權值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計算隱含層的輸出

o3=v*o2+theta2； %計算輸出層的輸出

e=t（：，g0）-o3；

3）對神經網絡中的各層次進行訓練，即對輸出層、隱含層和輸入層進行閥值調整。

theta2=theta2+lf*e； %調整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調整輸入層至隱含層權值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調整隱含層閥值

w=w+lv*o1*g； %調整隱含層至輸出層權值

4 結語

本文針對QOS的特診及相應的一些參數特點，構建了QOS組播路由的數學模型。然后在此基礎之上利用神經網絡的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經網絡算法作為參考依據的原因。和算法過程。

【參考文獻】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經網絡學習的神經網絡控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網絡技術與應用[M].北京：人民郵電出版社，2003，3：15-16.

[責任編輯：丁艷]