基于螞蟻算法的QoS路由算法研究.pdf

1、隨著Imemet的飛速發(fā)展，IP網(wǎng)絡(luò)不但在規(guī)模而且在用戶數(shù)量方面都得到了巨大增長，同時新的多媒體業(yè)務(wù)也越來越普遍，QoS路由問題已經(jīng)成為Imemet發(fā)展中最具有挑戰(zhàn)性的、最為活躍的研究領(lǐng)域之一。QoS受限路由問題是NP完全問題，用常規(guī)方法難以獲得滿意的結(jié)果。智能技術(shù)具有自適應(yīng)、自學(xué)習(xí)和推理等功能，在一些問題上能夠得到比常規(guī)方法更好的效果，目前已在通信、電子等諸多領(lǐng)域中得到廣泛應(yīng)用。 00S路由的任務(wù)就是在網(wǎng)絡(luò)中尋找一條路徑，它能

2、夠滿足帶寬、時延、時延抖動和費(fèi)用的限制。人們嘗試著采用螞蟻算法來尋找路由，獲得了滿意的結(jié)果。但是，這種算法也存在一些缺陷，如：需要較長的搜索時間，螞蟻算法的復(fù)雜度可以反映這一點(diǎn)；容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度后，所有個體所發(fā)現(xiàn)的解完全一致，不能對解空間進(jìn)一步進(jìn)行搜索，不利于發(fā)現(xiàn)更好的解。 在研究傳統(tǒng)的螞蟻算法的優(yōu)點(diǎn)及其缺點(diǎn)，提出了一種新的QoS路由算法。 算法通過螞蟻泛濫來尋找路由，螞蟻攜帶著所經(jīng)路徑的信息。算法

3、的關(guān)鍵是利用螞蟻所經(jīng)節(jié)點(diǎn)來控制泛濫的規(guī)模：所有中間節(jié)點(diǎn)只復(fù)制和泛濫到達(dá)它的最優(yōu)的一只螞蟻。這樣，通過約束條件下的窮舉搜索，最后一定可以找到源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的滿足QoS要求的路由。 算法充分考慮了部分鏈路出現(xiàn)擁塞的情況。每當(dāng)擁塞出現(xiàn)，從源節(jié)點(diǎn)和目的節(jié)點(diǎn)兩邊逐漸增大搜索范圍重新尋路，并盡量利用源路由有用信息，加快算法收斂。這樣，通過加快二次尋路速度的辦法，實(shí)現(xiàn)了擁塞鏈路上的數(shù)據(jù)改道和分流，減少了網(wǎng)絡(luò)振蕩。 通過算法理論分析