一種MANET網(wǎng)絡(luò)帶寬時(shí)延約束的多播路由算法研究

李?lèi)? 劉強(qiáng) 劉銀輝 趙航

摘要：本文提出一種啟發(fā)式的按需多播路由算法。在認(rèn)真研究MANET網(wǎng)絡(luò)的帶寬估計(jì)算法基礎(chǔ)上，有效限制了洪泛加入請(qǐng)求分組的數(shù)量，并基于MANET網(wǎng)絡(luò)特點(diǎn)提出了新的選擇函數(shù)，保證了公平地對(duì)待時(shí)延和帶寬性能。算法具有路由開(kāi)銷(xiāo)較少，成功率高的優(yōu)點(diǎn)。

關(guān)鍵詞： MANET；多播；NS2

中圖分類(lèi)號(hào)：TN711 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：

1引言

MANET網(wǎng)絡(luò)又稱(chēng)為移動(dòng)多跳無(wú)線(xiàn)網(wǎng)絡(luò)。因?yàn)榫哂袩o(wú)中心、自組織、多跳路由、動(dòng)態(tài)拓?fù)涞葏^(qū)別于普通網(wǎng)絡(luò)的特性，所以被重點(diǎn)研究和廣泛應(yīng)用。多播路由協(xié)議作為MANET網(wǎng)絡(luò)的重要組成部分，為支持多媒體應(yīng)用提供技術(shù)保障。文中針對(duì)MANET網(wǎng)絡(luò)經(jīng)典樹(shù)型多播路由協(xié)議的QoS問(wèn)題，提出一種優(yōu)化算法，在動(dòng)態(tài)環(huán)境中增加時(shí)延和帶寬約束，并有效控制了路由開(kāi)銷(xiāo)，經(jīng)仿真分析，改善了路由性能。

2問(wèn)題分析

2.1 MANET網(wǎng)絡(luò)中的帶寬估計(jì)

對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的帶寬估計(jì)，依網(wǎng)絡(luò)的MAC協(xié)議不同而將有所不同。IEEE 802.11DCF是標(biāo)準(zhǔn)委員會(huì)提出的針MANET的一種MAC協(xié)議，其采用的是CSMA/CA機(jī)制，文獻(xiàn)[1]在全面考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路的流內(nèi)干擾、流間干擾、帶寬的不對(duì)稱(chēng)性和隱藏節(jié)點(diǎn)等因素后提出：

（2-1）

設(shè)代表一條路徑，為路徑上的節(jié)點(diǎn)，為第個(gè)節(jié)點(diǎn)的可用帶寬。在充分考慮流內(nèi)干擾的情況下，路徑可用帶寬定義為：

（2-2）

2.2減少控制開(kāi)銷(xiāo)的方法

構(gòu)建QoS多播樹(shù)的分布式算法，是一個(gè)受約束Steiner樹(shù)的不斷生長(zhǎng)的過(guò)程。發(fā)現(xiàn)最優(yōu)路徑最為有效的方法就是洪泛加入請(qǐng)求，但全網(wǎng)廣播會(huì)引入過(guò)多的控制消息，降低網(wǎng)絡(luò)性能。本文提出一種限制洪泛的算法，即節(jié)點(diǎn)在洪泛加入請(qǐng)求時(shí)，按式（2-1）計(jì)算自己的節(jié)點(diǎn)可用帶寬并累計(jì)跳數(shù)，一并加入控制分組中發(fā)送出去，轉(zhuǎn)發(fā)節(jié)點(diǎn)依據(jù)式（2-2）對(duì)鏈路帶寬值和約束條件做出比較，如果不能滿(mǎn)足約束條件就停止轉(zhuǎn)發(fā)，否則繼續(xù)廣播，這樣，只有滿(mǎn)足約束條件的鏈路可以將加入請(qǐng)求傳遞到樹(shù)上，而不滿(mǎn)足約束條件的鏈路在中途即停止了加入請(qǐng)求的轉(zhuǎn)發(fā)，從而有效限制了洪泛控制消息的數(shù)量。

3BDCMR算法

基于前面的分析，本文提出一種MANET帶寬時(shí)延約束的多播路由算法BDCMR（MANET Bandwidth and Delay Constrained Multicast Routing）。算法結(jié)合鏈路可用帶寬的計(jì)算，使用自定義的路徑選擇函數(shù)，有效限制洪泛開(kāi)銷(xiāo)，提升了路由性能。描述如下：

給定移動(dòng)Ad hoc網(wǎng)絡(luò)，源節(jié)點(diǎn)，多播組集合，求得的多播樹(shù)為。

對(duì)于，則節(jié)點(diǎn)a和節(jié)點(diǎn)b之間的路徑用表示；表示節(jié)點(diǎn)a的度；表按式（2-1）計(jì)算得到的節(jié)點(diǎn)a的可用帶寬；，為源節(jié)點(diǎn)沿多播樹(shù)到達(dá)目的節(jié)點(diǎn)的路徑。對(duì)于，有三個(gè)正實(shí)數(shù)，，，分別表示的可用帶寬、時(shí)延和代價(jià)。設(shè)路徑的帶寬為，的時(shí)延為，的代價(jià)為。網(wǎng)絡(luò)中帶寬和時(shí)延約束為： ； ；。公式（3-1）為選擇函數(shù)，其中（3-2）式和（3-3）式為指示函數(shù)，其目的在于，當(dāng)存在多條可行鏈路時(shí)，通過(guò)它找出最優(yōu)路徑，從而構(gòu)建最優(yōu)多播樹(shù)。式（3-1）中表示從源節(jié)點(diǎn)S到節(jié)點(diǎn)的代價(jià)，表示任意鏈路的代價(jià)，通過(guò)節(jié)點(diǎn)連接到多播樹(shù)上。選擇函數(shù)以得值小者為佳。

（3-1）

其中：

（3-2）

（3-3）

則帶寬時(shí)延約束的多播路由問(wèn)題可以表述為：尋找從源節(jié)點(diǎn)S到所有目的節(jié)點(diǎn)的多播樹(shù)，并且滿(mǎn)足、和條件。

4BDCMR算法的仿真分析

為驗(yàn)證BDCMR算法的性能，在NS2環(huán)境下，對(duì)比MAODV-QoS協(xié)議做出了仿真分析。以下的仿真數(shù)據(jù)來(lái)自多次試驗(yàn)的平均值。

從圖4-1可以看出在BDCMR中由于選路時(shí)依據(jù)選擇函數(shù)做出判斷，所以樹(shù)的整體成功率高于MAODV-QoS，尤其在多播節(jié)點(diǎn)較多時(shí)優(yōu)勢(shì)更為明顯。在圖4-2中，隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的增加網(wǎng)絡(luò)中更多的組播組成員要加入多播樹(shù)，開(kāi)銷(xiāo)變大，MAODV-QoS的請(qǐng)求分組是洪泛方式廣播的，而在BDCMR中節(jié)點(diǎn)轉(zhuǎn)發(fā)路由請(qǐng)求分組依據(jù)對(duì)當(dāng)前鏈路是否可行（即滿(mǎn)足約束條件）做出判斷，所以控制開(kāi)銷(xiāo)小于前者。圖4-3和圖4-4表現(xiàn)的是，帶寬約束為1.5Mbps時(shí)延約束為100ms時(shí)，多播樹(shù)的平均路徑帶寬和平均路徑時(shí)延隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目的變化情況?？梢钥闯鯞DCMR的路徑平均帶寬指標(biāo)總體上好于MAODV-QoS，同時(shí)平均路徑時(shí)延總體上也要小于后者，而且BDCMR的兩項(xiàng)指標(biāo)更加平滑。

圖4-1 成功率隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化 圖4-2路由開(kāi)銷(xiāo)隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化

圖4-3平均路徑帶寬隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化圖4-4平均路徑時(shí)延隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的變化

5 結(jié)束語(yǔ)

在MANET網(wǎng)絡(luò)中，帶有QoS約束的多播路由協(xié)議是保證多媒體應(yīng)用的重要基礎(chǔ)。本文基于對(duì)MANET網(wǎng)絡(luò)帶寬估計(jì)的研究，有效控制了洪泛廣播開(kāi)銷(xiāo)，使用自定義的路徑選擇函數(shù)，提出了一種帶有時(shí)延和帶寬約束的多播路由算法。在NS2下，對(duì)BDCMR算法進(jìn)行了仿真，結(jié)果顯示，在成功率、路由開(kāi)銷(xiāo)和時(shí)延方面協(xié)議性能得到改善。

參考文獻(xiàn)

[1] 周賢偉,劉臻臻，林琳.一種具有時(shí)延約束的組播路由算法研究[J].計(jì)算機(jī)應(yīng)用研究,2009，26（9）：3259-3262.

[2] 孫寶林,李臘元. QoS動(dòng)態(tài)多播路由協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng),2005,26(11):1877-1880

[3] 王巖,張連芳,竇志斌.無(wú)線(xiàn)Ad hoc多媒體網(wǎng)絡(luò)中的可用帶寬估計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(33):107-110.

[4] 石堅(jiān),鄒玲.Ad Hoc網(wǎng)絡(luò)中一種基于QoS的分布式多播路由算法[J].通信學(xué)報(bào)