基于小世界和隨機圖理論的多QoS路由算法研究.pdf

1、路由一直是計算機網(wǎng)絡(luò)通信的關(guān)鍵理論和技術(shù)問題，尤其是目前 Internet 發(fā)展非常迅速，而且其節(jié)點數(shù)還正在呈指數(shù)級增長；網(wǎng)絡(luò)傳輸正在向大容量、高速化、多媒體化方向發(fā)展，傳統(tǒng)的路由算法已經(jīng)不能滿足日益增長的、對路由的各種QoS需求，因此必須研究新的具有 QoS 約束的路由算法。 本文將多 QoS 約束路由算法作為研究課題，以小世界理論為基礎(chǔ)，建立小世界網(wǎng)絡(luò)模型，提出 Internet 靜態(tài)網(wǎng)絡(luò)模型和動態(tài)網(wǎng)絡(luò)模型的新概念，獲得分布

2、式路由算法從一個源節(jié)點s到一個目標節(jié)點t消息傳輸期望步驟數(shù)的上限與下限；通過對隨機圖理論的研究，建立基于隨機圖的 k-叉樹網(wǎng)絡(luò)模型，獲得單播與組播平均跳數(shù)的函數(shù)關(guān)系式，得到分布式路由算法對于巨型、復(fù)雜網(wǎng)絡(luò)來講是高效的結(jié)論，建立了隨機圖仿真模型和方法，為研究多 QoS 約束路由算法奠定理論基礎(chǔ)；設(shè)計和實現(xiàn)基于二值編碼單親GA的分布式 QoS 路由算法 DQRGA，分析該算法的時間復(fù)雜度和空間復(fù)雜度，并與傳統(tǒng)的源路由算法進行性能比較，結(jié)果證

3、明該算法優(yōu)于傳統(tǒng)的集中式算法：在時間復(fù)雜度上優(yōu)于N/「log<,2>N」倍，在空間復(fù)雜度上優(yōu)于(log<,2>N)<'2>，其中 N 為網(wǎng)絡(luò)的節(jié)點數(shù)；設(shè)計與實現(xiàn)一種新的基于小世界和隨機圖理論的分布式路由算法 DRBSR，分析和計算該算法的時間復(fù)雜度和空間復(fù)雜度，并與傳統(tǒng)的路由算法進行性能比較，結(jié)果證明 DRBSR 算法優(yōu)于傳統(tǒng)的集中式算法；根據(jù)業(yè)務(wù)劃分的不同，考慮到多 QoS 約束和網(wǎng)絡(luò)資源利用率，設(shè)計和實現(xiàn)基于Dijkstra策略的Q

4、oS路由算法Fallback<'++>，分析該算法的時間復(fù)雜度和空間復(fù)雜度，結(jié)果證明該算法優(yōu)于 Fallback<'+>。 多 QoS 約束組播路由一直是路由算法研究中的難點問題之一，不但由于該問題是一個NP完全問題，而且還因為QoS參數(shù)是不確定的，甚至是模糊的，傳統(tǒng)的多QoS約束組播路由算法大多數(shù)屬于精確算法，不能很好地反映網(wǎng)絡(luò)的實際情況。本文提出基于模糊信息的綜合QoS約束的組播路由新算法IQMRFI，首次將模糊集理論應(yīng)用到

5、路由算法中，定義各個QoS參數(shù)的隸屬度和理想點，建立計算各個QoS參數(shù)到理想點的距離的模型和方法，將多目標規(guī)劃簡化為單目標規(guī)劃，設(shè)計和實現(xiàn)了 IQMRFI 算法，分析該算法的時間復(fù)雜度和空間復(fù)雜度，分別為O(mn<'2>)和O(5|E|)，并進行了仿真，結(jié)果證明IQMRFI 算法在路由選擇成功率和運行時間上都優(yōu)于傳統(tǒng)的QoS組播路由算法。本內(nèi)容屬于網(wǎng)絡(luò)基礎(chǔ)理論的原始性創(chuàng)新研究，不僅在理論上具有重要的意義，而且對未來新的Internet