無線傳感網(wǎng)絡(luò)中分布式資源分配和隊(duì)列調(diào)度問題研究.pdf

1、無線傳感網(wǎng)絡(luò)被廣泛應(yīng)用在軍事、工業(yè)、醫(yī)療、運(yùn)輸?shù)阮I(lǐng)域，其作為時(shí)代的產(chǎn)物在未來將占據(jù)越來越重要的地位。這種網(wǎng)絡(luò)通常由大量低功耗、低成本的傳感節(jié)點(diǎn)構(gòu)成。源節(jié)點(diǎn)負(fù)責(zé)收集所探測范圍內(nèi)的數(shù)據(jù)，并且通過中繼節(jié)點(diǎn)以多跳方式將數(shù)據(jù)傳遞給匯聚節(jié)點(diǎn)。然而，由于無線傳感網(wǎng)絡(luò)中的傳感節(jié)點(diǎn)主要通過能量有限的電池進(jìn)行供電，并且有限的網(wǎng)絡(luò)信道容量限制了數(shù)據(jù)速率在整個(gè)網(wǎng)絡(luò)中的傳輸與分配，因此，如何通過有效分配網(wǎng)絡(luò)資源和進(jìn)行隊(duì)列調(diào)度來保證無線傳感網(wǎng)絡(luò)的服務(wù)質(zhì)量是確保網(wǎng)絡(luò)

2、性能的一個(gè)關(guān)鍵問題。此外，隨著傳感網(wǎng)絡(luò)規(guī)模的不斷增大和流量的快速增長，僅通過一個(gè)基站節(jié)點(diǎn)負(fù)責(zé)集中處理來自于各個(gè)匯聚節(jié)點(diǎn)的數(shù)據(jù)已經(jīng)相當(dāng)困難，如何通過節(jié)點(diǎn)和鏈路之間局部網(wǎng)絡(luò)的信息交互分布式解決網(wǎng)絡(luò)資源分配和隊(duì)列調(diào)度問題，不僅可以大幅度改善網(wǎng)絡(luò)性能，而且還能大大提高網(wǎng)絡(luò)實(shí)際問題的求解速度。因此，如何在資源有限的情況下，通過快速優(yōu)化算法來分布式解決網(wǎng)絡(luò)資源分配和隊(duì)列調(diào)度問題，是一項(xiàng)意義非常重大的研究課題。
　　本文在充分了解國內(nèi)外有關(guān)無線

3、傳感網(wǎng)絡(luò)分布式資源分配、隊(duì)列調(diào)度和分布式算法研究現(xiàn)狀的基礎(chǔ)上，深入研究了資源有限和網(wǎng)絡(luò)穩(wěn)定約束下無線傳感網(wǎng)絡(luò)流控制優(yōu)化問題和分布式快速優(yōu)化算法，主要的工作和創(chuàng)新點(diǎn)包括:
　　(1)在單徑、路由確定的無線傳感網(wǎng)絡(luò)情況下，提出了一種基于節(jié)點(diǎn)能量和鏈路容量共同約束的流控制問題模型。傳統(tǒng)的網(wǎng)絡(luò)效用最大化問題僅僅考慮了鏈路容量對網(wǎng)絡(luò)性能的制約作用，而沒有考慮到無線傳感網(wǎng)絡(luò)主要通過能量有限的電池進(jìn)行供電這一實(shí)際特點(diǎn)。文章則考慮了這一有限資源對

4、無線傳感網(wǎng)絡(luò)整體性能的影響。此外，傳統(tǒng)意義上用來解決流控制問題的方法主要為對偶-次梯度算法，而在實(shí)際應(yīng)用中，這一算法存在收斂速度慢、步長選擇敏感等缺點(diǎn)，為了提高分布式優(yōu)化算法的整體性能，文章設(shè)計(jì)了具有二階收斂速度的分布式牛頓算法，研究結(jié)果和仿真實(shí)驗(yàn)表明，通過問題轉(zhuǎn)化和使用矩陣分裂技術(shù)，該算法在與對偶次梯度算法交互信息幾乎相同的情況下，運(yùn)行時(shí)間和迭代次數(shù)遠(yuǎn)小于傳統(tǒng)一階求解算法，收斂速度提高將近兩個(gè)數(shù)量級。
　　(2)在研究點(diǎn)(1)的

5、研究基礎(chǔ)上，把網(wǎng)絡(luò)場景擴(kuò)展到多徑、路由不確定的情況中，進(jìn)一步建立了一個(gè)能夠?qū)崿F(xiàn)效用比例公平的聯(lián)合路由選擇與流控制的效用最大化問題模型。與傳統(tǒng)網(wǎng)絡(luò)模型不同，該問題模型不僅考慮了鏈路容量、節(jié)點(diǎn)能量等有限資源對網(wǎng)絡(luò)的限制，而且把資源傳輸時(shí)如何選擇最優(yōu)路由考慮在內(nèi)。此外，為了實(shí)現(xiàn)流控制的效用比例公平，該研究點(diǎn)的優(yōu)化目標(biāo)選擇了能夠?qū)崿F(xiàn)比例公平的“偽效用函數(shù)”。特別需要指出的是，由于該優(yōu)化問題網(wǎng)絡(luò)場景完全不同于前一問題（如多徑、系數(shù)矩陣不滿足行滿秩

6、、Hessian矩陣分塊對角等），導(dǎo)致牛頓算法的分布式計(jì)算及其在網(wǎng)絡(luò)內(nèi)的執(zhí)行過程與(1)完全不同。文章通過一系列問題等價(jià)轉(zhuǎn)化、變量重組、使用矩陣分裂技術(shù)，最終實(shí)現(xiàn)了問題的高效求解。最后，文章用Matlab仿真平臺驗(yàn)證了分布式牛頓算法的性能。
　　(3)提出了一個(gè)隊(duì)列穩(wěn)定、資源有限以及流無溢出（no-underflow constraints）約束情況下，關(guān)于如何調(diào)度隊(duì)列以確保網(wǎng)絡(luò)穩(wěn)定、實(shí)現(xiàn)網(wǎng)絡(luò)效用時(shí)間平均最大化的調(diào)度問題模型。此外

7、，為了研究鏈路相互干擾時(shí)對無線傳感網(wǎng)絡(luò)隊(duì)列調(diào)度性能的影響，文章在該模型的基礎(chǔ)上進(jìn)一步提出了干擾矩陣概念，引入了鏈路干擾約束模型，把前一問題模型擴(kuò)展成鏈路有干擾情況下的資源隊(duì)列調(diào)度問題。針對這兩個(gè)問題，文章設(shè)計(jì)了基于李雅普優(yōu)化方法和對偶理論的擾動最大加權(quán)算法(Perturbed Max-weight algorithm)，高效求解了有干擾和無干擾兩種情況下的資源隊(duì)列調(diào)度問題。最后，文章從理論上對這一算法性能進(jìn)行了分析證明，并用Matlab