基于新型螞蟻算法的QoSR理論及技術(shù)研究.pdf

1、網(wǎng)絡(luò)服務(wù)質(zhì)量路由(QualityofServiceRouting)是計(jì)算機(jī)網(wǎng)絡(luò)理論研究的重要領(lǐng)域，隨著網(wǎng)絡(luò)的發(fā)展和網(wǎng)絡(luò)應(yīng)用的快速增長(zhǎng)，對(duì)網(wǎng)絡(luò)路由提出了更高的要求，為解決解決在Internet網(wǎng)上傳輸語(yǔ)音、視頻等數(shù)據(jù)時(shí)所遇到的帶寬變化、數(shù)據(jù)丟失、延遲、抖動(dòng)等QoS問題。本文對(duì)基于Internet網(wǎng)的QoSR問題的理論及技術(shù)進(jìn)行研究。 本文提出了一種擴(kuò)展的Dijkstra算法，該算法可找到QoS參數(shù)的極限值，能解決一些QoSR問題，

2、并對(duì)該算法進(jìn)行了復(fù)雜性分析與比較。 螞蟻算法作為探索類算法在近幾年逐步得到推廣和應(yīng)用，在研究螞蟻算法后，本文提出了一種新型的螞蟻算法，并保留螞蟻算法的信息素概念，該算法對(duì)經(jīng)典螞蟻算法做了3個(gè)方面的根本改進(jìn)，它們是： 1.摒棄螞蟻算法中概率方式的轉(zhuǎn)移模式，采用確定方式的轉(zhuǎn)移模式； 2.摒棄一群螞蟻的探路模式，采用一只螞蟻的探路模式； 3.螞蟻在探索路徑時(shí)，總是沿著信息素最小的路徑前進(jìn)。 通過實(shí)際編程

3、和計(jì)算，證實(shí)了新型的螞蟻算法能解決QoSR問題，能找到較優(yōu)QoSR或最優(yōu)QoSR。經(jīng)過對(duì)該算法的分析，發(fā)現(xiàn)其時(shí)間復(fù)雜性與螞蟻移動(dòng)的步數(shù)成線性關(guān)系。 本文在研究新型螞蟻算法后，證明了在一個(gè)連通的有限網(wǎng)絡(luò)中，采用該算法，螞蟻經(jīng)過有限步移動(dòng)后，可到達(dá)網(wǎng)絡(luò)中的任意一個(gè)結(jié)點(diǎn)。這個(gè)結(jié)論也證明了新型螞蟻算法算法有初始的QoSR解。本文對(duì)新型螞蟻算法的最優(yōu)性、簡(jiǎn)單性、魯棒性、收斂性、靈活性5種性能指標(biāo)進(jìn)行定性分析。分析結(jié)果表明該算法具有優(yōu)良的性

4、能特征。本文研究了該算法時(shí)間復(fù)雜性與螞蟻移動(dòng)步數(shù)之間的關(guān)系，得出結(jié)論是新型螞蟻算法的計(jì)算時(shí)間開銷與螞蟻移動(dòng)步數(shù)成線性關(guān)系。本文研究了螞蟻移動(dòng)步數(shù)與QoSR解的關(guān)系，得出結(jié)論是在螞蟻移動(dòng)MLog2N步后，就能尋找到較優(yōu)的QoS路由，有時(shí)能尋找到最優(yōu)的QoS路由。本文對(duì)該算法的時(shí)間復(fù)雜性進(jìn)行定量分析，最終得到的結(jié)論是新型螞蟻算法的時(shí)間復(fù)雜性為0(N3Log2N)。并與有關(guān)的QoSR算法的時(shí)間復(fù)雜性進(jìn)行比較，結(jié)果表明該算法的時(shí)間復(fù)雜性較優(yōu)。

5、 本文在研究新型螞蟻算法理論的基礎(chǔ)上，進(jìn)一步對(duì)新型螞蟻算法的魯棒性進(jìn)行實(shí)際計(jì)算與研究，結(jié)果證實(shí)新型螞蟻算法具有魯棒性。 本論文完成了5類實(shí)驗(yàn)，它們是： 1.擴(kuò)展Dijkstra算法求解QoS極限值計(jì)算實(shí)驗(yàn)； 2.新型螞蟻算法搜索QoSR的仿真實(shí)驗(yàn) 3.QoSR延時(shí)、抖動(dòng)、可靠性的仿真實(shí)驗(yàn) 4.新型螞蟻算法時(shí)間復(fù)雜性的計(jì)算實(shí)驗(yàn) 5.新型螞蟻算法魯棒性的計(jì)算實(shí)驗(yàn)。 本論文得到了國(guó)