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

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

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

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

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

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

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

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