基于模擬退火遺傳算法的時(shí)延控制選播路由算法研究

摘要：考慮到選播的QoS路由問(wèn)題，提出了一種基于模擬退火遺傳算法的時(shí)延控制選播路由算法。該算法利用模擬退火的思想彌補(bǔ)了遺傳算法局部收斂較弱和較慢的缺陷，并根據(jù)給定的條件找到一條較好的路徑。網(wǎng)絡(luò)仿真模擬實(shí)驗(yàn)結(jié)果表明，該算法具有良好的收斂性和求解效果，可以找到滿足時(shí)延要求的低費(fèi)用的路由路徑。

關(guān)鍵詞：選播路由；服務(wù)質(zhì)量；遺傳算法；模擬退火算法；時(shí)延控制

中圖分類(lèi)號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0336-03

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的快速發(fā)展，人們發(fā)現(xiàn)傳統(tǒng)的盡力而為的數(shù)據(jù)傳輸服務(wù)已經(jīng)無(wú)法滿足網(wǎng)絡(luò)的正常運(yùn)行。一些音頻、視頻等流媒體業(yè)務(wù)對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)提出了更高的要求^[1]。網(wǎng)絡(luò)上多媒體業(yè)務(wù)的興起對(duì)時(shí)延提出了越來(lái)越高的要求。因?yàn)楝F(xiàn)有網(wǎng)絡(luò)上的多媒體業(yè)務(wù)大都是實(shí)時(shí)通信。如果通信的時(shí)延過(guò)長(zhǎng)，就會(huì)引起用戶視覺(jué)和聽(tīng)覺(jué)上的不舒服，甚至引起語(yǔ)義上的無(wú)法理解。所以研究滿足時(shí)延受限、最小花費(fèi)的網(wǎng)絡(luò)通信是目前網(wǎng)絡(luò)通信研究的主要課題之一。

選播作為IPv6中定義的一種標(biāo)準(zhǔn)通信服務(wù)模型^[2]，為解決網(wǎng)絡(luò)QoS問(wèn)題帶來(lái)了一些便利條件，如選播地址對(duì)應(yīng)多個(gè)目標(biāo)節(jié)點(diǎn)，這就為QoS資源預(yù)留提供了更多的選擇余地^[3]。在選播通信模式中，一組目的節(jié)點(diǎn)可用一個(gè)選播地址表示，提供相同服務(wù)的不同服務(wù)器擁有相同的選播地址。選播的數(shù)據(jù)報(bào)文將由路由系統(tǒng)盡力而為地保證被投遞到離這組選播組成員（主機(jī)）其中最近的任意一個(gè)^[2，4]，最好僅僅傳輸?shù)揭粋€(gè)主機(jī)。也就是說(shuō)，IPv6的選播通信服務(wù)實(shí)現(xiàn)在很大程度上取決于對(duì)路由的選擇。

研究表明^[4，5]，基于兩個(gè)或兩個(gè)以上不相關(guān)可加度量的QoS路由問(wèn)題是一個(gè)NP完全問(wèn)題。目前采用的方法多為啟發(fā)式算法。文獻(xiàn)[6]提出了一種滿足帶寬約束的選播路由算法。它應(yīng)用寬度優(yōu)先搜索算法來(lái)尋找從源節(jié)點(diǎn)到所有目標(biāo)節(jié)點(diǎn)的最大帶寬路徑。一些研究人員用遺傳算法來(lái)解決選播路由選擇問(wèn)題^[7，8]。因?yàn)檫z傳算法能從全局高度求出問(wèn)題的最優(yōu)解。但是現(xiàn)有的基于遺傳算法的選播路由算法也存在一些問(wèn)題，如算法容易局部收斂、初始種群的構(gòu)造和適應(yīng)值函數(shù)的設(shè)計(jì)還有改進(jìn)的空間等。

本文提出使用模擬退火遺傳算法來(lái)解決時(shí)延受限的選播路由問(wèn)題。基本的遺傳算法雖然把握搜索過(guò)程的整體能力較強(qiáng)，但是局部搜索能力較差；而模擬退火對(duì)整體的空間狀況了解不多，但在局部尋優(yōu)上有很大的優(yōu)勢(shì)。兩者相互結(jié)合就可以取長(zhǎng)補(bǔ)短，形成性能更優(yōu)良的全局搜索算法。

1模擬退火遺傳算法的介紹

Kirkpatrick等人^[9]于1983年提出了模擬退火算法(simulated annealing algorithm，SA)。該算法是基于金屬退火的機(jī)理建立起的一種全局最優(yōu)化方法。它能夠以隨機(jī)搜索技術(shù)從概率的意義上找出目標(biāo)函數(shù)的全局最小點(diǎn)。Paul L.Stoffa在遺傳算法和模擬退火算法的基礎(chǔ)上，提出了模擬退火的遺傳算法（simulated annealing genetic algorithm，SAGA）^[10]。該算法利用適應(yīng)度拉伸的方法實(shí)現(xiàn)模擬退火算法與遺傳算法的結(jié)合。

遺傳算法在運(yùn)行早期個(gè)體差異較大，當(dāng)采用經(jīng)典的輪盤(pán)賭方式選擇時(shí)，后代產(chǎn)生的個(gè)體與父?jìng)€(gè)體適應(yīng)度大小成正比，因此在早期容易使個(gè)別好的個(gè)體后代充斥整個(gè)種群，造成早熟；在遺傳算法后期，適應(yīng)度趨向一致，優(yōu)秀的個(gè)體在產(chǎn)生后代時(shí)優(yōu)勢(shì)不明顯，從而使整個(gè)種群進(jìn)化停滯不前。因此對(duì)適應(yīng)度進(jìn)行適當(dāng)拉伸是必要的。這樣在溫度高時(shí)（遺傳算法的前期），適應(yīng)度相近的個(gè)體產(chǎn)生的后代概率相近；而當(dāng)溫度不斷下降后，拉伸作用強(qiáng)，使適應(yīng)度相近的個(gè)體適應(yīng)度差異放大，從而使優(yōu)秀的個(gè)體優(yōu)勢(shì)更明顯。

4．3算法的收斂性分析

實(shí)驗(yàn)中的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)由10到100變化，目的節(jié)點(diǎn)數(shù)固定為8，遺傳算法初始種群的規(guī)模設(shè)為20，進(jìn)化50代，遺傳算法

的交叉概率近似于0．4，變異概率為0．04。圖5給出了算法的收斂性。圖中的每個(gè)數(shù)據(jù)點(diǎn)都是經(jīng)過(guò)100次以上的隨機(jī)實(shí)驗(yàn)后統(tǒng)計(jì)平均得出的。從圖中可以看出，隨著圖中節(jié)點(diǎn)的增加，算法的進(jìn)化代數(shù)有所增加，但是增加的速度較為緩和；進(jìn)化到一定的代數(shù)時(shí)，算法得以收斂。

以上的仿真實(shí)驗(yàn)表明，本文提出的基于SAGA的時(shí)延控制選播路由算法的收斂速度較快，較好地平衡了網(wǎng)絡(luò)負(fù)載，提高了網(wǎng)絡(luò)的利用率和服務(wù)質(zhì)量。

參考文獻(xiàn)：

[1]VEGESNA S. IP服務(wù)質(zhì)量[M].北京：人民郵電出版社， 2001：10-36.

[2]DEERING S， HINDEN R. RFC 2460， Internet protocol version 6(IPv6) specification[S].[S.l.]: IETF， 1998.

[3]張麗，嚴(yán)偉，李曉明. Anycast——IP 的又一通信模式[J]. 計(jì)算機(jī)研究與發(fā)展，2003，40(6):784-790.

[4]PARTRIDGE C，MENDEZ T，MILLIKEN W.RFC 1546，Host any－cast server[R].[S.l.]: IETF，1993.

[5]JIA Wei－jia，XUAN Dong，ZHAO Wei. Integrated routing algorithms for anycast messages[J].IEEE Communications Magazine，2000，38(1)：48-53.

[6]LOW C P，SONG X.On finding feasible solutions for the delay constrained group multicast routing problem[J].IEEE Transactions on Computer，2002，51(5):581-587.

[7]陳燕，宋玲，李陶深. 基于遺傳算法的網(wǎng)絡(luò)負(fù)載均衡的選播路由算法[J].微電子學(xué)與計(jì)算機(jī)，2004，21(12):46-49.

[8]馬焱煒，盧葦.遺傳算法在選播路由中的應(yīng)用[J]. 交通與計(jì)算機(jī)， 2005，23(4): 87-90.

[9]KIRKPATRICK S C D，GELATT Jr，VECCHI M P.Optimization by simulated annealing[J].Science，1983，220(4598):671-680.

[10]王小平，曹立名.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002:36-80.

[11]WAXMAN B. Routing of multipoint connections[J].IEEE J Select Areas Commun，1988，6(9):1617－1622.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”