面向物聯(lián)網(wǎng)的QoS路由近似算法研究.pdf

1、隨著物聯(lián)網(wǎng)的高速發(fā)展，人們對其業(yè)務質(zhì)量和組網(wǎng)技術提出了更高的服務質(zhì)量(Quality of Service，QoS)要求。目前，面向物聯(lián)網(wǎng)如何更好的保障QoS，成為物聯(lián)網(wǎng)行業(yè)與產(chǎn)業(yè)繼續(xù)發(fā)展壯大的關鍵，是當前國際家電、IT廠商等業(yè)界關注的焦點，同時也是學術界研究的熱點問題。
　　根據(jù)不同業(yè)務類型所提出的QoS要求和網(wǎng)絡環(huán)境的資源配置，研究高效可行的QoS路由算法，是QoS路由機制有效運行的技術支撐，也是物聯(lián)網(wǎng)保障QoS的切實可行方案

2、之一。在智能算法、確定性算法和近似算法等QoS路由算法的熱點研究中，近似算法以其高效、合理可行的特點，在物聯(lián)網(wǎng)不同網(wǎng)絡環(huán)境下的業(yè)務應用中表現(xiàn)出一定優(yōu)勢。
　　本論文以“面向物聯(lián)網(wǎng)的QoS路由算法”為主線，針對工程實踐中業(yè)務應用的多約束QoS路由、多播保障QoS路由、多播多約束QoS路由和WMN(Wireless Mesh Network)網(wǎng)絡保障QoS路由等幾個關鍵問題展開研究。從近似的角度尋找當前性能最優(yōu)的解，并探討其在不同網(wǎng)絡

3、環(huán)境中應用的合理性。本文主要研究內(nèi)容與貢獻如下:
　　(1)通過研究單播多約束QoS最優(yōu)路由問題，根據(jù)不同網(wǎng)絡環(huán)境分別提出了高效可行的路由算法。首先，針對穩(wěn)定可靠的網(wǎng)絡環(huán)境，結合目前最快的確定性算法，通過縮放和取整技術，從近似的角度逼近所有QoS約束，最后找到“最優(yōu)”路徑，相應提出了一種計算時間合理、近似率較高的路由算法;其次，針對時變、不可靠的網(wǎng)絡環(huán)境，通過尋找每條邊上最主要的度量，從近似角度找到“最優(yōu)”路徑并滿足QoS約束，相

4、應提出了一種快速計算且可行的路由算法。理論分析并證明了兩種算法的時間復雜度和近似率，通過仿真對比現(xiàn)有算法驗證了性能。它們分別是工程實踐中穩(wěn)定可靠網(wǎng)絡和時變、容錯能力差網(wǎng)絡環(huán)境下的一種合理高效的求解方案。
　　(2)通過研究網(wǎng)絡中的多播生成樹問題，考慮多播目的節(jié)點數(shù)量及分布狀態(tài)，提出了兩種高效可行的路由算法。首先，針對多播目的節(jié)點數(shù)量較多、分布集中情況，結合性能最好的多播生成樹算法，基于多播路徑共享的思想，讓多播目的節(jié)點根據(jù)優(yōu)先級順

5、序加入生成樹，從而減少多播生成樹總度量值，相應提出了一種高效可行的近似算法;其次，針對多播目的節(jié)點數(shù)量較少、分布分散情況，根據(jù)目的節(jié)點與當前生成樹距離，調(diào)整多播目的節(jié)點優(yōu)先級值，相應提出了一種改進的合理可行的近似算法。理論分析并證明了兩種算法的時間復雜度和近似率，均與性能最好的多播生成樹算法一致。通過仿真驗證了兩種算法在不同情況下的優(yōu)勢。多播路由業(yè)務中不同目的節(jié)點數(shù)量及分布狀態(tài)下，它們是合理可行的求解方案。
　　(3)通過研究多播

6、多約束QoS最優(yōu)路由問題，根據(jù)不同網(wǎng)絡環(huán)境分別提出了高效可行的多播生成樹算法。首先，針對穩(wěn)定可靠的網(wǎng)絡環(huán)境，參考性能最好的多播生成樹算法，結合目前最快的確定性算法，通過縮放和取整技術，從近似的角度逼近所有QoS約束并找到“最優(yōu)”多播生成樹，相應提出了一種合理計算時間、近似率較高的路由算法;其次，針對時變、不可靠的網(wǎng)絡環(huán)境，通過選取每條邊上最主要的度量，從近似角度在最短時間內(nèi)找到“最優(yōu)”多播生成樹并滿足QoS約束，相應提出了一種快速計算可

7、行的路由算法。理論分析并證明了兩種算法的時間復雜度和近似率，通過仿真對比現(xiàn)有算法驗證了性能。它們是分別針對工程實踐中不同網(wǎng)絡環(huán)境下的一種合理高效的求解方案。
　　(4)通過研究WMN網(wǎng)絡的Anypath路由問題，針對時變特性強、容錯能力差的WMN網(wǎng)絡，研究高效可行的Anypath路由算法。根據(jù)工程實踐中的業(yè)務應用，提出了新的Anypath路由問題，建立了數(shù)學模型。根據(jù)Anypath路由的期望度量值，強制一個特定QoS約束下同時逼近