無線Ad Hoc網(wǎng)絡(luò)中的組播路由算法研究.pdf

1、隨著現(xiàn)代無線通信技術(shù)和因特網(wǎng)的發(fā)展與進(jìn)步，任何人在任何時(shí)間、任何地點(diǎn)都能夠獲取信息并與他人通信，已經(jīng)成為人們對(duì)現(xiàn)代信息網(wǎng)絡(luò)的切實(shí)要求。無線Ad Hoc網(wǎng)絡(luò)是一種移動(dòng)通信技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)相結(jié)合的網(wǎng)絡(luò)，是由彼此對(duì)等的、自主的移動(dòng)節(jié)點(diǎn)組成的多跳自組織無線網(wǎng)絡(luò)。無線Ad Hoc網(wǎng)絡(luò)無需固定基礎(chǔ)設(shè)施支持，能快速、簡單組網(wǎng)，并且按照其設(shè)計(jì)的初衷，能夠自組織、自修復(fù)，因此，正在成為下一代無線網(wǎng)絡(luò)的有力競(jìng)爭者。在Ad Hoc網(wǎng)絡(luò)中，網(wǎng)絡(luò)的住處交換采

2、用了計(jì)算機(jī)網(wǎng)絡(luò)中的分組交換機(jī)制，組網(wǎng)卻不受地理位置和有無固定的通信基礎(chǔ)設(shè)施的限制，可獨(dú)立組網(wǎng)，也可聯(lián)入其他網(wǎng)絡(luò)。此外，用戶終端可以自由移動(dòng)，每個(gè)終端都兼有路由器和主機(jī)兩種功能。 由于架構(gòu)無線Ad Hoc網(wǎng)絡(luò)非常方便，而且可快速適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)渥兓?，所以它可廣泛應(yīng)用于災(zāi)難救助、戰(zhàn)場(chǎng)指揮、臨時(shí)會(huì)議、協(xié)同工作等場(chǎng)合，這些應(yīng)用通常都有一個(gè)共同的特征，就是一到多或是多到多的數(shù)據(jù)傳輸，因此，組播通信在無線Ad Hoc網(wǎng)絡(luò)中具有非常重要的作

3、用。 在無線Ad Hoc網(wǎng)絡(luò)中，一個(gè)通信請(qǐng)求可以通過單跳完成，也可以通過若干個(gè)中繼節(jié)點(diǎn)完成，因此，在設(shè)計(jì)路由算法時(shí)必須要考慮中繼節(jié)點(diǎn)的選擇，另外，由于網(wǎng)絡(luò)中節(jié)點(diǎn)是依靠電池供應(yīng)能量的，所以，節(jié)能問題是無線Ad Hoc網(wǎng)絡(luò)中的一個(gè)核心問題。本文就無線Ad Hoc網(wǎng)絡(luò)的組播節(jié)能問題進(jìn)行了研究，并取得了一定的成果。 本文的主要工作和貢獻(xiàn)包括： 1.研究了無線Ad Hoc網(wǎng)絡(luò)的研究熱點(diǎn)以及現(xiàn)有的組播路由協(xié)議，并深入分析了基

4、于源端的樹型結(jié)構(gòu)組播路由算法，研究了該類算法的不足，并提出了改進(jìn)方案。 2.提出了一個(gè)最小化能量組播路由算法。在無線Ad Hoc網(wǎng)絡(luò)中，能量消耗是路由算法的一個(gè)重要衡量標(biāo)準(zhǔn)。本文先利用圖理論為該問題建模，簡單分析了網(wǎng)絡(luò)中只有三個(gè)節(jié)點(diǎn)的情況，并推廣到一般網(wǎng)絡(luò)。然后在分析現(xiàn)有算法不足的基礎(chǔ)上，提出了一個(gè)以最小化能量為目標(biāo)的路由算法GMBR(Greedy Maximum-Branch Replacement)，并比較了該算法和已有算法

5、的性能，實(shí)驗(yàn)結(jié)果顯示所提算法在節(jié)省總能量消耗方面優(yōu)于原算法，能夠有效地減少能量消耗，并且很容易改進(jìn)成一個(gè)并行算法進(jìn)一步提高效率。最后將該算法擴(kuò)展到了組播情況。 3.提出了一個(gè)最大化網(wǎng)絡(luò)生命期組播路由算法。在無線Ad Hoc網(wǎng)絡(luò)中，如果只是以最小化能量為目標(biāo)，勢(shì)必會(huì)導(dǎo)致網(wǎng)絡(luò)中某一部分節(jié)點(diǎn)能量消耗過快，從而會(huì)縮短網(wǎng)絡(luò)生命期。因此，在前面章節(jié)的基礎(chǔ)上，本文研究了節(jié)能問題的另一方面一最大化網(wǎng)絡(luò)生命期。本文首先給出了該問題的理論模型，并分

6、析了節(jié)點(diǎn)初始能量相等和不相等兩種情況，然后針對(duì)節(jié)點(diǎn)初始能量不相等的情況提出了一個(gè)貪心算法WMST(Weighted Minimum Spanning Tree)，該算法考慮了節(jié)點(diǎn)的能量和鏈路的能量消耗。實(shí)驗(yàn)結(jié)果表明，算法存優(yōu)化生命期方面優(yōu)于已有算法。 4.提出了一個(gè)平衡能量負(fù)載組播路由算法。本文先證明了最大化網(wǎng)絡(luò)生命期并不能保證總能量最小，然后在前面提出的最大化網(wǎng)絡(luò)生命期算法WMST的基礎(chǔ)上，本文作出了進(jìn)一步改進(jìn)，提出了Impr