常國鋒，王 滿

(1.新鄉(xiāng)學(xué)院計(jì)算機(jī)與信息工程學(xué)院，河南新鄉(xiāng)453003;2.南陽理工學(xué)院數(shù)理學(xué)院，河南南陽473004)

QoS組播路由是下一代Internet需要解決的一個(gè)難題［1－2］。而QoS組播路由算法是組播路由的核心技術(shù)，要求在分布的網(wǎng)絡(luò)中尋找一條既滿足多個(gè)約束條件，同時(shí)又滿足具有最小代價(jià)的最優(yōu)路徑。

BP神經(jīng)網(wǎng)絡(luò)通過學(xué)習(xí)和推理這兩個(gè)過程，能夠修正各個(gè)連接途徑的權(quán)值，無限地逼近樣本值，不斷修正結(jié)果，并且對(duì)相關(guān)信息實(shí)施處理［3－4］。BP神經(jīng)網(wǎng)絡(luò)在學(xué)習(xí)、分類和優(yōu)化上有優(yōu)勢(shì)，有較強(qiáng)的局部搜索能力。蟻群算法(Ant Colony Algorithm，AC)是蟻群能夠找到一條從巢穴到食物的最短路徑的方法［5］，蟻群算法的優(yōu)點(diǎn)是具有較強(qiáng)的魯棒性、分布式計(jì)算、易于融合其他算法，同時(shí)具有較強(qiáng)的全局搜索能力，但是收斂速度慢、易陷入局部最小點(diǎn)。

本文結(jié)合BP神經(jīng)網(wǎng)絡(luò)和蟻群算法的優(yōu)點(diǎn)，提出了一種新型的神經(jīng)網(wǎng)絡(luò)蟻群算法(Neural Network Ant Colony Algorithm，NNAC)。結(jié)合BP神經(jīng)網(wǎng)絡(luò)局部搜索的優(yōu)勢(shì)和蟻群算法全局搜索的優(yōu)勢(shì)，同時(shí)BP神經(jīng)網(wǎng)絡(luò)還能彌補(bǔ)蟻群算法易陷入局部最小點(diǎn)的不足。

1 QoS組播路由網(wǎng)絡(luò)模型

在QoS組播路由網(wǎng)絡(luò)模型中，通常用加權(quán)圖G=(V，E)表示通信網(wǎng)絡(luò)，V表示節(jié)點(diǎn)集，E表示鏈路集，節(jié)點(diǎn)數(shù)和鏈路數(shù)分別由表示［6－7］。同一對(duì)節(jié)點(diǎn)間的鏈路數(shù)≤1的網(wǎng)絡(luò)模型如圖1所示。

圖1 網(wǎng)絡(luò)模型圖

R+、R*分別表示正實(shí)數(shù)集和非負(fù)實(shí)數(shù)集。數(shù)據(jù)由源節(jié)點(diǎn)s∈V傳送到目的節(jié)點(diǎn)集D?V－{s}，組播組M={s}∪D。定義組播樹T=(VT，ET)，組播樹T由源節(jié)點(diǎn)傳送到目的節(jié)點(diǎn)的路徑為l(s，d)，則對(duì)于任意鏈路e∈E可定義以下QoS參數(shù):

時(shí)延函數(shù)

帶寬函數(shù)

時(shí)延抖動(dòng)函數(shù)

包丟失率函數(shù)

鏈路代價(jià)函數(shù)

求解多約束QoS組播路由優(yōu)化問題是指尋找從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的組播樹T，并且滿足QoS參數(shù)的約束條件

式中:Dp，Bp，Jp，Lp分別為時(shí)延、帶寬、時(shí)延抖動(dòng)、包丟失率約束量。

2 NNAC算法

結(jié)合BP神經(jīng)網(wǎng)絡(luò)局部搜索的優(yōu)勢(shì)和蟻群算法全局搜索的優(yōu)勢(shì)，進(jìn)行QoS組播路由算法的設(shè)計(jì)，提出了一種新型的神經(jīng)網(wǎng)絡(luò)蟻群算法(NNAC)［8－10］。

2.1 NNAC算法實(shí)現(xiàn)步驟

NNAC算法步驟為:

Step1:確定BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，給定BP神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值;對(duì)蟻群算法初始化設(shè)置，包括多路徑信息強(qiáng)度、螞蟻數(shù)量。

Step2:計(jì)算各個(gè)路徑的適應(yīng)度。

Step3:從源節(jié)點(diǎn)出發(fā)，通過賭輪規(guī)則選擇合適的路徑，進(jìn)行分泌物強(qiáng)度調(diào)整。

Step4:將收集的參數(shù)作為BP神經(jīng)網(wǎng)絡(luò)初始權(quán)值和閾值，并對(duì)BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練。

Step5:應(yīng)用BP神經(jīng)網(wǎng)絡(luò)在當(dāng)前路徑中找到更優(yōu)解，如果有更優(yōu)解則替代原有路徑。

Step6:計(jì)算各組播樹的代價(jià)，判斷大部分路徑是否收斂于同一組播樹，收斂則為最優(yōu)路徑，退出程序;否則，只保留最小代價(jià)的組播樹，轉(zhuǎn)到Step7。

Step7:返回源節(jié)點(diǎn)，轉(zhuǎn)到Step2。

2.2 初始化

初始化中需要設(shè)定BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值para={wi}，wi為N個(gè)較小的隨機(jī)值，N個(gè)隨機(jī)值組成集合，i=1，2，…，N;j=1，2，…，N，設(shè)wi對(duì)應(yīng)的信息素為τij，初始時(shí)刻、信息素相等，上限為 τ0= τmax。

2.3 路徑適應(yīng)度

NNAC算法依據(jù)適應(yīng)度函數(shù)選取路徑［8］，選用的適應(yīng)度函數(shù)為

2.4 信息調(diào)整

分泌物強(qiáng)度調(diào)整函數(shù)為

式中:ω為常量參數(shù);l為鏈路代價(jià)。每當(dāng)蟻群走完一條路徑后，需要對(duì)所有路徑的分泌物揮發(fā)性進(jìn)行調(diào)整［9－10］

式中:η為分泌物揮發(fā)度;α為各個(gè)路徑的初始信息強(qiáng)度。

2.5 BP網(wǎng)絡(luò)訓(xùn)練和調(diào)整

BP神經(jīng)網(wǎng)絡(luò)采用包括輸入層、隱含層、輸出層的網(wǎng)絡(luò)結(jié)構(gòu)［11－13］。在BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)，并不知道準(zhǔn)確的輸出結(jié)果，將Step3中分泌物強(qiáng)度phePj最大的路徑和其他路徑進(jìn)行比較，來指導(dǎo)BP神經(jīng)網(wǎng)絡(luò)。同時(shí)，BP神經(jīng)網(wǎng)絡(luò)采用附加動(dòng)量法進(jìn)行訓(xùn)練，當(dāng)修正的權(quán)值對(duì)誤差的影響較大時(shí)，應(yīng)放棄新權(quán)值，并停止動(dòng)量;當(dāng)新的誤差變化率超過設(shè)定的最大誤差變化率值后，應(yīng)放棄對(duì)權(quán)值的變化。最大誤差變化率一般設(shè)置為1.04。附加動(dòng)量法判斷公式為

式中:mc為動(dòng)量因子，取0.95;k為訓(xùn)練次數(shù)。

設(shè) BP 神經(jīng)網(wǎng)絡(luò)輸入向量為 X= ［x1，x2，…，xn］T，輸出向量為 Y= ［y1，y2，…，yl］T，期望輸出為 D= ［d1，d2，…，dl］T。

BP神經(jīng)網(wǎng)絡(luò)的目的就是求誤差能量E的最小值，應(yīng)用BP神經(jīng)網(wǎng)絡(luò)在當(dāng)前路徑中找到更優(yōu)解的方程為

式中:cij表示鏈路代價(jià);dij表示時(shí)延;vij表示神經(jīng)元的輸出;λ→∞ ;能量函數(shù)u1項(xiàng)表示代價(jià)和時(shí)延的最小值;能量函數(shù)u2項(xiàng)表示每個(gè)節(jié)點(diǎn)的出、入邊數(shù)相等時(shí)的最小值，保證從源節(jié)點(diǎn)到目的節(jié)點(diǎn)為一完整路徑。

3 算法仿真分析

首先對(duì)NNAC算法全局最小值的尋找進(jìn)行仿真［14］。由于該算法采用附加動(dòng)量的BP神經(jīng)網(wǎng)絡(luò)進(jìn)行了訓(xùn)練，所以在附加動(dòng)量的驅(qū)動(dòng)下，可以避免局部極小值的干擾，從而最終尋找到全局最小值，結(jié)果如圖2所示。

圖2 NNAC算法全局最小值尋找結(jié)果

對(duì)NNAC算法進(jìn)行仿真分析的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)采用8節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)，如圖3所示。拓?fù)浣Y(jié)構(gòu)圖中的源節(jié)點(diǎn)為s，目的節(jié)點(diǎn)為a，c，e，f，圖中各個(gè)邊上的數(shù)值代表延時(shí)和代價(jià)，用 (Dp，CP)表示，(Dp，CP)的數(shù)值是隨機(jī)的，BP 神經(jīng)網(wǎng)絡(luò)誤差能量的公式中的u1=1 000，u2=200。

圖3 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

利用MATLAB編寫NNAC算法程序，得到最優(yōu)組播樹如圖4所示。通過圖4可知，總延時(shí)為35，總代價(jià)費(fèi)用為21。

圖4 NNAC算法最優(yōu)組播樹

為了進(jìn)一步分析NNAC算法的性能，引入AC算法，通過兩種算法進(jìn)行最優(yōu)組播樹的尋找成功率進(jìn)行對(duì)比分析，通過實(shí)驗(yàn)可以得到如表1所示結(jié)果。

表1 AC算法與NNAC算法成功率對(duì)比表 %

通過表1可以看出，兩種算法在指定的網(wǎng)絡(luò)環(huán)境下，完成150個(gè)度約束組播路由路徑時(shí)，NNAC算法在進(jìn)行最優(yōu)組播樹的尋找成功率上高于AC算法。因?yàn)镹NAC算法融合了BP神經(jīng)網(wǎng)絡(luò)局部搜索的優(yōu)勢(shì)，克服了易陷入局部最小點(diǎn)的不足。

4 結(jié)論

本文結(jié)合BP神經(jīng)網(wǎng)絡(luò)和蟻群算法，提出了一種新型的NNAC算法。該算法結(jié)合了BP神經(jīng)網(wǎng)絡(luò)局部搜索和蟻群算法全局搜索的優(yōu)勢(shì)，改善了QoS組播路由路徑尋找的方法。通過實(shí)驗(yàn)仿真分析，NNAC算法能夠有效地提高最優(yōu)組播樹的尋找成功率，同時(shí)該算法還克服了AC算法易陷入局部最小點(diǎn)的不足。

［1］葛連升，江林，秦豐林.QoS組播路由算法研究綜述［J］.山東大學(xué)學(xué)報(bào):理學(xué)版，2010(1):55－65.

［2］黃小鳳.計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法研究［D］.長沙:湖南大學(xué)，2010.

［3］劉建國.基于卡爾曼濾波的BP神經(jīng)網(wǎng)絡(luò)模型在橋梁形變中的應(yīng)用［D］.西安:長安大學(xué)，2010.

［4］ YANG B.BP neural network optimization based on an improved genetic algorithm［C］//Proc.2002 International Conference on Machine Learning and Cybernetics.［S.l.］:IEEE Press，2002:64－68.

［5］ TSENG Shengyuan，LIN Changchun，HUANG Yuehmin.Ant colonybased algorithm for constructing broadcasting tree with degree and delay constraints［J］.Expert Systems with Applications，2008，35(3):1473－1481.

［6］陳杰，張洪偉.基于自適應(yīng)蟻群算法的QoS組播路由算法［J］.計(jì)算機(jī)工程，2008，34(13):200－20.

［7］丁國強(qiáng)，孫澤宇，李傳鋒.改進(jìn)遺傳蟻群算法求解優(yōu)化問題的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)測(cè)量與控制，2011，19(10):2558－2561.

［8］王興偉，鄒榮珠，黃敏.基于螞蟻算法的ABC支持型QoS組播路由機(jī)制［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，2009，30(7):959－963.

［9］孫力娟，王汝傳.基于蟻群算法和遺傳算法融合的QoS組播路由問題求解［J］.電子學(xué)報(bào)，2006，34(8):1391－1395.

［10］葛連升，王華，王海洋.求解度約束組播路由的新型蟻群算法［J］.電子學(xué)報(bào)，2009，37(7):1447－1551.

［11］ LIUW，WANG L.Solving the delay constrainedmulticast routing problem using the transiently chaotic neural network［J］.Advances in Neural Networks(ISNN):LNCS，2007(4492):57－62.

［12］ WANG L，LIUW，SHIH.Delay－constrained multicast routing using the noisy chaotic neural networs［J］.IEEE Transa.Computers，2009，58(1):82－89.

［13］陳陽舟，田秋芳，張利國.基于神經(jīng)網(wǎng)絡(luò)的城市快速路交通擁堵判別算法［J］.計(jì)算機(jī)測(cè)量與控制，2011，19(1):167－169.

［14］尚濤，謝龍漢，杜如虛.MATLAB工程計(jì)算及分析［M］.北京:清華大學(xué)出版社，2011.