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

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

關鍵詞：選播路由；服務質量；遺傳算法；模擬退火算法；時延控制

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

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

隨著計算機網絡技術的快速發展，人們發現傳統的盡力而為的數據傳輸服務已經無法滿足網絡的正常運行。一些音頻、視頻等流媒體業務對網絡服務質量(QoS)提出了更高的要求^[1]。網絡上多媒體業務的興起對時延提出了越來越高的要求。因為現有網絡上的多媒體業務大都是實時通信。如果通信的時延過長，就會引起用戶視覺和聽覺上的不舒服，甚至引起語義上的無法理解。所以研究滿足時延受限、最小花費的網絡通信是目前網絡通信研究的主要課題之一。

選播作為IPv6中定義的一種標準通信服務模型^[2]，為解決網絡QoS問題帶來了一些便利條件，如選播地址對應多個目標節點，這就為QoS資源預留提供了更多的選擇余地^[3]。在選播通信模式中，一組目的節點可用一個選播地址表示，提供相同服務的不同服務器擁有相同的選播地址。選播的數據報文將由路由系統盡力而為地保證被投遞到離這組選播組成員（主機）其中最近的任意一個^[2，4]，最好僅僅傳輸到一個主機。也就是說，IPv6的選播通信服務實現在很大程度上取決于對路由的選擇。

研究表明^[4，5]，基于兩個或兩個以上不相關可加度量的QoS路由問題是一個NP完全問題。目前采用的方法多為啟發式算法。文獻[6]提出了一種滿足帶寬約束的選播路由算法。它應用寬度優先搜索算法來尋找從源節點到所有目標節點的最大帶寬路徑。一些研究人員用遺傳算法來解決選播路由選擇問題^[7，8]。因為遺傳算法能從全局高度求出問題的最優解。但是現有的基于遺傳算法的選播路由算法也存在一些問題，如算法容易局部收斂、初始種群的構造和適應值函數的設計還有改進的空間等。

本文提出使用模擬退火遺傳算法來解決時延受限的選播路由問題。基本的遺傳算法雖然把握搜索過程的整體能力較強，但是局部搜索能力較差；而模擬退火對整體的空間狀況了解不多，但在局部尋優上有很大的優勢。兩者相互結合就可以取長補短，形成性能更優良的全局搜索算法。

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

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

遺傳算法在運行早期個體差異較大，當采用經典的輪盤賭方式選擇時，后代產生的個體與父個體適應度大小成正比，因此在早期容易使個別好的個體后代充斥整個種群，造成早熟；在遺傳算法后期，適應度趨向一致，優秀的個體在產生后代時優勢不明顯，從而使整個種群進化停滯不前。因此對適應度進行適當拉伸是必要的。這樣在溫度高時（遺傳算法的前期），適應度相近的個體產生的后代概率相近；而當溫度不斷下降后，拉伸作用強，使適應度相近的個體適應度差異放大，從而使優秀的個體優勢更明顯。

4．3算法的收斂性分析

實驗中的網絡節點數由10到100變化，目的節點數固定為8，遺傳算法初始種群的規模設為20，進化50代，遺傳算法

的交叉概率近似于0．4，變異概率為0．04。圖5給出了算法的收斂性。圖中的每個數據點都是經過100次以上的隨機實驗后統計平均得出的。從圖中可以看出，隨著圖中節點的增加，算法的進化代數有所增加，但是增加的速度較為緩和；進化到一定的代數時，算法得以收斂。

以上的仿真實驗表明，本文提出的基于SAGA的時延控制選播路由算法的收斂速度較快，較好地平衡了網絡負載，提高了網絡的利用率和服務質量。

參考文獻：

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

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

[3]張麗，嚴偉，李曉明. Anycast——IP 的又一通信模式[J]. 計算機研究與發展，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]陳燕，宋玲，李陶深. 基于遺傳算法的網絡負載均衡的選播路由算法[J].微電子學與計算機，2004，21(12):46-49.

[8]馬焱煒，盧葦.遺傳算法在選播路由中的應用[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]王小平，曹立名.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002:36-80.

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

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”