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

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

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

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

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