廖禮 馬建林

摘 要 多約束QoS路由是用來尋找一條同時滿足多個約束條件的可行路徑，這是NPC問題。本文主要介紹基于PCNN的算多約束QoS路由算法，通過對常見算法的分析，得出了PCNN在解決多約束QoS問題中的優(yōu)勢。

關鍵詞 脈沖耦合神經(jīng)網(wǎng)絡 多約束QoS路由 最短路徑

中圖分類號：TP393文獻標識碼：A

0引言

QoS路由（QoS Routing）是根據(jù)網(wǎng)絡上可利用資源和流（flow）的QoS需求決定流的路由的機制。QoS路由應該實現(xiàn)以下三個目標：

（1）確定動態(tài)可行路徑;

（2）優(yōu)化路由資源利用;

（3）對整體性能影響盡可能小。

如果能通過有效的方法找出既滿足應用的QoS需求，又具有最小代價，負載分布均衡的路由，則阻塞概率將大大降低，同時也將顯著提高網(wǎng)絡的利用效率。

服務時被要求提供的QoS，對于給定路徑的指標一般可以分為三類：

（1）可加性?？俀oS等于構成這條路徑的所有鏈路QoS值的和（如跳數(shù)、成本、鏈路長度、時延等），可加性能夠在問題中作預處理操作;

（2）可乘性?？俀oS等于構成這條路徑的所有鏈路QoS值的積（如誤差率，丟包率和鏈路利用率等）;

（3）最大最小性?？俀oS等于構成這條路徑的所有鏈路QoS值中的最小者（如費用，時延、跳數(shù)等），總QoS等于構成這條路徑的所有鏈路QoS值中的最大者（如流量、帶寬和帶寬利用率等）。

1基于PCNN的多約束QoS路由算法

脈沖耦合神經(jīng)網(wǎng)絡（PCNN，pulse-coupled neural network）作為有著生物學背景的新一代人工神經(jīng)網(wǎng)絡，在圖像處理、模式識別、路徑優(yōu)化求解等方面具有重要的應用。PCNN網(wǎng)絡使用其自動波特性求解路徑優(yōu)化問題，是一種非確定性方法，用夠?qū)崿F(xiàn)用最小的努力求得問題的全局最優(yōu)結果，這一成果已經(jīng)在求解最短路徑問題（SP）中得到了很好的運用。

多約束QoS路由選擇問題（單播）實際上是一個帶約束條件的最短路問題。因此利用基于PCNN 的最短路求解方法，并對在PCNN上傳播的每一個自動波隨時進行約束條件滿足與否的檢驗，是完全可以實現(xiàn)解決的。如果所有約束條件均滿足，則該自動波繼續(xù)傳播。如果約束條件中至少有一個不滿足，則該自動波消失，從而允許其它自動波在網(wǎng)絡上繼續(xù)傳播。那么最先到達目標神經(jīng)元的自動波走過的路徑即為滿足要求多約束的QoS路由路徑，即為文中提到的式（6）的解。但實際中需對基于PCNN的最短路算法進行改進。若某自動波不滿足任一個約束，則允許其他自動波繼續(xù)傳播，這就需要將不滿足約束的自動波走過的路徑的神經(jīng)元熄火，它們的再次點火則應由其他自動波的繼續(xù)傳播引起。這就涉及一個自動波回退、熄火的過程，從點火神經(jīng)元i回退的一般過程如下：

（1）判斷到達神經(jīng)元i的自動波是從哪個神經(jīng)元的點火傳播來的（設判斷結果為是從神經(jīng)元1的點火傳播來的），是否是多個自動波通過競爭傳播來的。若是，則設置，從而使得該自動波無法繼續(xù)傳播下去，結束回退，否則做（2）;

（2）使自動波回退到神經(jīng)元l，即神經(jīng)元i熄火，即使，且，并刪除該自動波在路徑矩陣中的路徑，轉(zhuǎn)去做（1）。

上述熄火、回退過程是沿傳播到神經(jīng)元i的自動波路徑不斷逆向而行的過程，直到該自動波是以競爭形式獲得傳播并通過設置鏈路費用為無窮來抑制不滿足約束的自動波的傳播，從而允許其它自動波在網(wǎng)絡上繼續(xù)傳播。

這樣我們就獲得了基于PCNN的QoS路由選擇算法：

step 1：如果NDV（D）>jitter，則式（6）無解，算法結束，否則轉(zhuǎn)到step 2;

step 2：初始化。即對于，設，;

step 3：讓start神經(jīng)元點火。即設，并保持其余神經(jīng)元的各個狀態(tài)不變（其中 為一正數(shù)）;

step 4：對于，若神經(jīng)元i點火，即若，計算鏈路路徑start-i的QoS指標，若至少有一個指標不滿足約束條件，則回退神經(jīng)元i，否則做step 5;

step 5：自動波及其傳播。對于，若，計算鏈路路徑start-（i，j）的QoS指標，且若所有指標均滿足約束條件、、、，并實現(xiàn)路徑記錄;

step 6：重復做step4～5，直到end神經(jīng)元點火，或者自動波回退到start神經(jīng)元為止。

step 7：對于end神經(jīng)元點火的情況，根據(jù)路徑記錄矩陣B=（bij），從神經(jīng)元end開始進行路徑回溯，即可得到滿足所有約束條件下費用最小的鏈路路徑，即式（6）的解;對于自動波回溯到start神經(jīng)元的情況，則式（6）無解，即沒有滿足所有約束的鏈路路徑。算法結束。

2總結

將基于PCNN的QoS路由算法結果與螞蟻算法、遺傳算法、Hopfield算法的結果進行了對比，發(fā)現(xiàn)運用PCNN的QoS路由算法大大降低了迭代次數(shù)，明顯提高了效率，并且算法全局收斂。另外，運用PCNN求解QoS路由問題后面又相繼提出了Q-PCNNs模型和CPCNN模型，在保留PCNN基本特性的前提下，對模型做了適當?shù)母倪M，使模型更加適合于解決QoS路由問題求解。

參 考 文 獻

[1] 趙榮昌，馬義德，綻琨.三態(tài)層疊脈沖耦合神經(jīng)網(wǎng)絡及其思想在最短路徑求解中的應用[J].系統(tǒng)工程與電子技術，2008（09）.

[2] 張軍英，王德峰，石美紅.基于點火耦合神經(jīng)網(wǎng)絡的多約束QoS路由選擇算法[J].通信學報，2002（06）.

[3] 董繼揚，張軍英.基于累積競爭神經(jīng)網(wǎng)絡的多約束路由算法[J].控制與決策，2004，19（07）：751-755.

[4] 朱尚明，黃明.基于脈沖耦合神經(jīng)網(wǎng)絡的QoS路由算法[J].華東理工大學學報（自然科學版），2008（03）.

[5] John Caulfield，H.&J.M.Kinser.Finding shortest path in the shortest time using PCNNS[J].IEEE Trans Neural Networks，1999，10（03）：604-606.

[6] 顧曉東，余道衡，張立.時延PCNN及其用于求解最短路徑[J].電子學報，2004，32（09）：1441-1443.

[7] 張軍英，王德峰，石美紅.輸出-閾值耦合神經(jīng)網(wǎng)絡及基于此的最短路徑問題求解[J].中國科學（E輯），2003（33）.