Ad Hoc網(wǎng)絡中基于蟻群算法的QoS路由研究.pdf

1、Ad Hoc網(wǎng)絡是由一組帶有無線收發(fā)裝置的移動節(jié)點所組成的臨時性多跳自治系統(tǒng)，在軍事和民用領域具有廣闊的應用前景。近年來，隨著各類多媒體業(yè)務及實時業(yè)務的普及和推廣，要求網(wǎng)絡在帶寬、時延等方面提供保障，在Ad Hoc網(wǎng)絡中提供QoS支持越來越重要。然而考慮到Ad Hoc網(wǎng)絡中節(jié)點是移動的，網(wǎng)絡拓撲結構不斷變化，同時這些節(jié)點的計算能力和存儲容量較低、能量受限，如何設計出滿足QoS要求的路由是一個具有挑戰(zhàn)性的課題。 Ad Hoc的Qo

2、S路由是一個滿足多約束的問題，是NP完全問題，傳統(tǒng)的路由算法難以有效解決。作為是一種全新啟發(fā)式算法，蟻群算法不依賴于具體問題的數(shù)學描述，具有全局優(yōu)化能力和本質上的并行性，是解決NP完全問題的有效方法。本文將蟻群算法應用于Ad Hoc網(wǎng)絡QoS路由問題研究，把源節(jié)點和目的節(jié)點分別當作“蟻巢”和“食物”，數(shù)據(jù)包視為“螞蟻”，在經(jīng)過的路徑上留下的“信息素”用路由表代替，信息素濃度以概率值的形式表示。通過信息素表來選擇下一步所要走的路徑，經(jīng)過多

3、次迭代，找到滿足多個QoS約束條件且信息素最高的路由。Ad Hoc網(wǎng)絡頻繁的拓撲變化與蟻群算法內(nèi)在收斂速度慢是一對矛盾，因此算法設計的關鍵是要改進收斂速度以適應Ad Hoc網(wǎng)絡動態(tài)的網(wǎng)絡環(huán)境。 本文針對蟻群算法固有的缺陷和應用于Ad Hoc網(wǎng)絡QoS路由可能產(chǎn)生的擁塞問題，提出一種基于雙向收斂蟻群算法的多約束QoS路由算法，其中包括時延、帶寬、延時抖動、成本約束。在進行全局信息素更新時，采用了雙向收斂的策略，對歷史最優(yōu)解的路徑上

4、的信息素給予獎勵，而將歷史最差解看作目前不可接受解，對其信息素進行懲罰，引導其它螞蟻盡量遠離歷史最差解，從而加快算法的收斂速度。同時算法能對擁塞鏈路做出較快的反應，進行擁塞回避，從而實現(xiàn)網(wǎng)絡業(yè)務流負載均衡。仿真表明：該算法同傳統(tǒng)的按需路由算法和ARA算法相比，在端到端時延和包投遞率方面可獲得較好的性能。 本文利用遺傳算法的快速全局搜索能力和蟻群算法的正反饋收斂機制，引入遺傳蟻群算法(Genetic Algorithm Ant C