李悅 劉強 劉銀輝 趙航

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

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

中圖分類號：TN711 文獻標識碼：A 文章編號：

1引言

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

2問題分析

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

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

（2-1）

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

（2-2）

2.2減少控制開銷的方法

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

3BDCMR算法

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

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

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

（3-1）

其中：

（3-2）

（3-3）

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

4BDCMR算法的仿真分析

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

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

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

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

5 結(jié)束語

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

參考文獻

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

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

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

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