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

廖禮 馬建林

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

關鍵詞 脈沖耦合神經網絡 多約束QoS路由 最短路徑

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

0引言

QoS路由（QoS Routing）是根據網絡上可利用資源和流（flow）的QoS需求決定流的路由的機制。QoS路由應該實現以下三個目標：

（1）確定動態可行路徑;

（2）優化路由資源利用;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

step 3：讓start神經元點火。即設，并保持其余神經元的各個狀態不變（其中 為一正數）;

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

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

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

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

2總結

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

參 考 文 獻

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

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

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

[4] 朱尚明，黃明.基于脈沖耦合神經網絡的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].中國科學（E輯），2003（33）.