基于遺傳算法的QoS組播路由算法研究.pdf

1、隨著Internet和寬帶網(wǎng)絡(luò)技術(shù)的日益發(fā)展，傳統(tǒng)的以文字和圖片為主的服務(wù)已不能滿足用戶的需要，具有視頻和音頻的多媒體服務(wù)成為主流。近幾年嵌入式網(wǎng)絡(luò)數(shù)字視頻監(jiān)控系統(tǒng)正在得到廣泛應(yīng)用。由于嵌入式網(wǎng)絡(luò)數(shù)字視頻監(jiān)控系統(tǒng)傳輸?shù)臄?shù)據(jù)量大而系統(tǒng)資源有限，采用點對點的傳輸方式會增加服務(wù)器的負(fù)擔(dān)，造成網(wǎng)絡(luò)擁塞。而組播技術(shù)可以將相同的數(shù)據(jù)從嵌入式網(wǎng)絡(luò)視頻服務(wù)器同時并行地發(fā)送到接收者，大大節(jié)省了網(wǎng)絡(luò)帶寬，減少了數(shù)據(jù)冗余，即使用戶數(shù)量成倍增加，主干網(wǎng)絡(luò)帶寬也

2、不會隨之增加。同時視頻監(jiān)控系統(tǒng)對信息傳送的時延和時延抖動有嚴(yán)格的要求，要求傳輸?shù)臄?shù)據(jù)必須在一定的時延限制內(nèi)到達(dá)所有的接收者，并且接收者之間的延遲差別也需在一定的范圍內(nèi)，即滿足一定服務(wù)質(zhì)量(QoS)的要求。因此在嵌入式網(wǎng)絡(luò)數(shù)字視頻監(jiān)控系統(tǒng)中我們需要解決QoS組播路由問題。該問題的目標(biāo)是尋找一棵滿足QoS要求的組播樹，使該樹覆蓋所有的組成員，同時使網(wǎng)絡(luò)費用達(dá)到最小。 遺傳算法是近幾年提出的一種模擬生物界自然選擇和遺傳機制，具有高度并

3、行，群體尋優(yōu)的新型最優(yōu)化搜索算法，近年來已有一些學(xué)者采用遺傳算法來求解QoS組播路由問題。本文在分析現(xiàn)有遺傳算法的基礎(chǔ)上，提出了兩種改進的遺傳算法。第一個改進算法針對遺傳算法運行初期易陷入早熟，運行后期收斂緩慢的問題進行了改進，采用初始群體均衡生成法和自適應(yīng)變異操作可以很好地抑制早熟現(xiàn)象，引入排序?qū)m應(yīng)度進行拉伸，從而加快了算法的收斂速度。仿真實驗結(jié)果表明改進后的遺傳算法收斂速度快，性能好，可以滿足系統(tǒng)資源有限和實時性的要求。第二種改進

4、算法是在分析了遺傳算法和蟻群算法各自優(yōu)缺點的基礎(chǔ)上，將兩種算法進行融合來求解QoS組播路由問題，算法的前一階段利用遺傳算法的快速性、隨機性、全局收斂性產(chǎn)生后一階段蟻群算法所需要的初始信息素，加快了蟻群算法利用正反饋特性進行搜索的速度。經(jīng)融合后的算法，在時間效率上優(yōu)于蟻群算法，在求解效率上優(yōu)于遺傳算法，形成了一種時間效率和求解效率都比較好的啟發(fā)式算法。 本文最后針對現(xiàn)有視頻監(jiān)控系統(tǒng)單播傳輸存在的問題，將組播技術(shù)應(yīng)用到網(wǎng)絡(luò)視頻監(jiān)控系