喬平安，邵 凱，劉運(yùn)爽

(西安郵電大學(xué)計(jì)算機(jī)學(xué)院，陜西西安 710121)

路由度量準(zhǔn)則作為路由協(xié)議重要的組成部分，一個(gè)好的路由度量準(zhǔn)則能夠提升網(wǎng)絡(luò)的性能。由于現(xiàn)有路由度量準(zhǔn)則大多都針對(duì)單信道設(shè)計(jì)，對(duì)于多路徑多信道路由協(xié)議會(huì)導(dǎo)致無(wú)效的路由［1］，進(jìn)而會(huì)限制網(wǎng)絡(luò)的累積吞吐量［2］。本文提出了一種適用于多路徑多信道的路由選擇準(zhǔn)則，仿真結(jié)果顯示該準(zhǔn)則在吞吐量方面優(yōu)于已有的單信道路由選擇準(zhǔn)則。

1 基于WCETT的路由選擇準(zhǔn)則

微軟公司Draves提出了一種單路徑單信道的路由選擇準(zhǔn)則［3］，稱(chēng)為加權(quán)累計(jì)期望傳輸時(shí)間即WCETT準(zhǔn)則，WCETT準(zhǔn)則綜合考慮了帶寬等鏈路性能參數(shù)以及最小跳數(shù)等因素［4］。

首先，討論一條路徑累計(jì)期望傳輸時(shí)間計(jì)算，假如從A節(jié)點(diǎn)到B節(jié)點(diǎn)的鏈路為i，則該鏈路的期望傳輸時(shí)間值表示為ETTi，假如S表示分組的長(zhǎng)度;B表示鏈路的實(shí)際帶寬;N表示一個(gè)數(shù)據(jù)分組成功傳輸預(yù)計(jì)需要的次數(shù)，則ETT計(jì)算過(guò)程如下［5］

其中，fa，fb分別為某條鏈路的前向?qū)ǜ怕室约昂笙驅(qū)ǜ怕?。則一條路徑上所有n條鏈路的期望傳輸時(shí)間之和為，其中 n 為路由長(zhǎng)度，使用式(1)估計(jì)一個(gè)分組在鏈路上的預(yù)計(jì)傳輸時(shí)間。由于受到信道差異的影響，累計(jì)期望傳輸時(shí)間ETT并不能完全反映該條路徑的優(yōu)劣，應(yīng)考慮鏈路之間的相互干擾。假設(shè)一個(gè)n條路徑，路徑使用了k個(gè)信道進(jìn)行傳輸，數(shù)據(jù)分組在信道m(xù)上的傳輸時(shí)間之和表示為Xm，其中對(duì)總吞吐量影響最大的信道可能是受干擾最大的信道，稱(chēng)為瓶頸信道，因此，一條路徑的優(yōu)劣，應(yīng)是由累計(jì)期望傳輸時(shí)間與瓶頸信道傳輸兩個(gè)因素來(lái)決定的。即WCETT

2 MWCETT路由選擇準(zhǔn)則

由于WCETT路由選擇準(zhǔn)則無(wú)法反映多信道鏈路之間的干擾以及數(shù)據(jù)包通過(guò)節(jié)點(diǎn)時(shí)的擁塞情況，針對(duì)該準(zhǔn)則的缺點(diǎn)提出了一種適用于多路徑多信道的路由選擇準(zhǔn)則—MWCETT準(zhǔn)則。

2.1 MWCETT路由選擇準(zhǔn)則的確立

所謂多徑路由，就是在通過(guò)路由算法選擇傳輸路徑時(shí)，同時(shí)選擇多條路徑，將通信量按照一定的比例分配到不同的路徑上同時(shí)傳輸，以提高吞吐量，為方便分析，本文以3條路徑為例，這一分析可擴(kuò)展到≥4條路徑。

在節(jié)點(diǎn)A，B之間進(jìn)行通信，需選擇3條同時(shí)用于傳輸?shù)淖罴崖窂絃a，Lb，Lc，在此MWCETT路由選擇準(zhǔn)則是根據(jù)多條路徑的合計(jì)吞吐量的大小來(lái)確定的，影響吞吐量的因素較多，在此主要抓住3個(gè)因素:(1)單路徑的時(shí)延因子。即單條路徑上所花費(fèi)的總時(shí)延。(2)路徑干擾因子。該因子包括路徑內(nèi)使用相同信道的干擾以及路徑間信道間的干擾。(3)數(shù)據(jù)通過(guò)節(jié)點(diǎn)時(shí)的排隊(duì)時(shí)延因子。該因子是指所發(fā)送的數(shù)據(jù)包經(jīng)過(guò)某節(jié)點(diǎn)時(shí)排隊(duì)的遲延。因此，在路由選擇時(shí)，估算出單路徑的時(shí)延因子，路徑干擾因子以及數(shù)據(jù)包通過(guò)節(jié)點(diǎn)時(shí)的排隊(duì)時(shí)延因子，通過(guò)這些從而確定通信量在多條路徑上的分配比例。

假設(shè)路徑Lk的第i跳期望傳輸時(shí)間ETT表示為ETTki，用SR(Lk)表示路徑Lk上所使用的信道。接下來(lái)通過(guò)單路徑時(shí)延因子δ，路徑干擾因子η，排隊(duì)時(shí)延因子φ這3方面的組合關(guān)系獲得MWCETT路由選擇準(zhǔn)則。

2.2 路徑干擾因子η的計(jì)算

當(dāng)分組使用多個(gè)信道在多條路徑上同時(shí)傳輸時(shí)，使用相同信道的鏈路之間不可避免會(huì)產(chǎn)生干擾，該種干擾無(wú)形之中影響了整個(gè)網(wǎng)絡(luò)的吞吐量。因此，文中希望找到鏈路之間干擾最小的一些路徑，由于受干擾最大的瓶頸信道對(duì)網(wǎng)絡(luò)的吞吐量影響最大，在此將瓶頸信道的傳輸時(shí)間稱(chēng)為路徑間的干擾因子η，路徑間的干擾因子η反映了多條路徑有相同信道的鏈路之間的干擾，瓶頸信道取決于多路徑的負(fù)載組合分配。

假設(shè)無(wú)線路徑Lk有Nk個(gè)信道，則定義路徑在信道j上的累積傳輸時(shí)間Ykj如下

現(xiàn)在定義一個(gè)多路徑組合的瓶頸信道傳輸時(shí)間，考慮在路徑 La，Lb和 Lc上通信量分配(x∶y∶z)，x 分組在路徑La上，y分組在路徑Lb上以及z分組在Lc上消耗的時(shí)間為 x×Yaj+y× Ybj+z×Zcj，這樣在 La∪Lb∪Lc中的信道j上每個(gè)分組消耗的時(shí)間均值Wj(x，y，z)為

從式(4)可看出，通信量分配比例(x∶y∶z)決定了分組在信道上的消耗時(shí)間，消耗時(shí)間最長(zhǎng)的信道為瓶頸信道。如果用Sabc表示路徑組合(La，Lb，Lc)上的信道總數(shù)，則在通信量分配比例為(x∶y∶z)的情況下瓶頸信道的傳輸時(shí)間為因此多路徑信道干擾因子

2.3 路徑延時(shí)因子δ的計(jì)算

路徑延遲因子δ反映了路徑的端對(duì)端特性，其計(jì)算由單路徑的路徑質(zhì)量準(zhǔn)則WCETT推導(dǎo)出來(lái)。對(duì)于有nk個(gè)信道有n跳的路徑Lk，其WCETT公式為

由式(6)可知，在一條路徑上的WCETT值越小，預(yù)期的吞吐量越高，為了反映多條路徑上分組的累積傳輸時(shí)間，定義路徑延時(shí)因子δ(x，y，z)為多條路徑上WCETT上的加權(quán)平均值，如下所示

式中，δ(x，y，z)反映了組合路徑 La，Lb，Lc端到端的延時(shí)情況。

2.4 排隊(duì)時(shí)延因子

Li為在節(jié)點(diǎn)i上等待隊(duì)列的平均長(zhǎng)度，vi為該節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的速率，由Liang Ma提出的在路徑Lp中節(jié)點(diǎn)的負(fù)載度［8］可表示為

La，Lb和Lc為3條無(wú)線自組網(wǎng)中的路徑，則定義該路徑中節(jié)點(diǎn)排空該隊(duì)列的累積時(shí)間為

式中，φ(x，y，z)反映了組合路徑 La，Lb，Lc端到端節(jié)點(diǎn)排隊(duì)時(shí)延情況。

2.5 MWCETT準(zhǔn)則

由式(5)、式(7)和式(9)可看出，多路徑間的干擾因子η，路徑延時(shí)因子δ，排隊(duì)時(shí)延因子φ取決于負(fù)載分配比率x∶y∶z，單一的路徑干擾因子η，路徑延時(shí)因子δ，排隊(duì)時(shí)延因子φ只能反映路徑間路徑內(nèi)的干擾，端到端的延遲，或數(shù)據(jù)包通過(guò)節(jié)點(diǎn)時(shí)的排隊(duì)延時(shí)其中的一種情況，只有綜合考慮信道間的干擾，端到端的延遲以及排隊(duì)時(shí)延的特性，才能全面反映路徑的變化。因此，提出了一種新的由η，δ以及φ組合的多信道多路徑路由選擇準(zhǔn)則—MWCETT準(zhǔn)則。

MWCETT解決了端到端延遲，信道干擾以及排隊(duì)遲延的問(wèn)題。MWCETT值越低，路徑累積吞吐量就越高。α與β是兩個(gè)分別滿(mǎn)足0≤α≤1，0≤β≤1的可調(diào)因子。若β=0，只考慮節(jié)點(diǎn)的排隊(duì)遲延問(wèn)題。若β選擇1，而α≠0且α≠1，該準(zhǔn)則只考慮端到端的遲延問(wèn)題以及信道間的干擾問(wèn)題。若β選擇1，而α=0時(shí)該準(zhǔn)則只考慮端到端的時(shí)延問(wèn)題;若β選擇1，而α=1時(shí)該準(zhǔn)則只考慮信道的干擾問(wèn)題。α，β之間的不同取值嘗試著在信道干擾因子、端到端延遲因子以及排隊(duì)遲延因子之間獲得均衡。

3 仿真結(jié)果及性能分析

對(duì)于MSR協(xié)議分別應(yīng)用傳統(tǒng)的WCETT路由選擇準(zhǔn)則以及MWCETT路由選擇準(zhǔn)則進(jìn)行性能的驗(yàn)證，在NS2環(huán)境下進(jìn)行實(shí)驗(yàn)仿真，仿真環(huán)境在2 000×1 500的矩形區(qū)域內(nèi)。對(duì)于MWCETT準(zhǔn)則取α=0.5，β=0.5，選取3條路徑進(jìn)行傳輸，實(shí)驗(yàn)中業(yè)務(wù)源CBR(恒定比特率)數(shù)目分別為20個(gè)和30個(gè)。在這兩種情況下，分別對(duì)WCETT路由準(zhǔn)則與MWCETT路由準(zhǔn)則下MSR協(xié)議的吞吐量進(jìn)行仿真。

從圖1和圖2可以看出，在中載和重載下，MWCETT準(zhǔn)則下的吞吐量與WCETT準(zhǔn)則下的吞吐量變化趨勢(shì)基本相同。但在路由跳數(shù)相同時(shí)MWCETT準(zhǔn)則的吞吐量要優(yōu)于WCETT準(zhǔn)則，這是由于應(yīng)用MWCETT準(zhǔn)則的MSR協(xié)議選擇了路徑內(nèi)、路徑間信道干擾小、端到端延遲小且排隊(duì)遲延短的路徑進(jìn)行數(shù)據(jù)傳輸，而應(yīng)用WCETT準(zhǔn)則的MSR協(xié)議只考慮了單條路徑內(nèi)的干擾以及端到端的遲延情況，所以前者在吞吐量方面會(huì)優(yōu)于后者。

圖1 MWCETT與WCETT準(zhǔn)則下吞吐量比較(20個(gè)數(shù)據(jù)源)

圖2 MWCETT與WCETT準(zhǔn)則下吞吐量的比較(30個(gè)數(shù)據(jù)源)

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

針對(duì)已有的WCETT路由準(zhǔn)則進(jìn)行了分析，提出了一種滿(mǎn)足無(wú)線Ad Hoc網(wǎng)絡(luò)多徑多信道傳輸?shù)腗WCETT路由選擇準(zhǔn)則，仿真驗(yàn)證了該路由準(zhǔn)則在吞吐量方面要優(yōu)于現(xiàn)有的WCETT路由選擇準(zhǔn)則，后期將繼續(xù)完善該路由選擇準(zhǔn)則，并拓展應(yīng)用到多路徑多信道的無(wú)線Mesh網(wǎng)絡(luò)中。

［1］ Akyildiz I F，Wang X D，Wang W L．Wireless meshnetwork:a survey［J］．Computer Networks，2005，47(4):445 －487．

［2］ 孫志．基于WCETT的多信道WMN路由度量的研究［J］．通信技術(shù)，2013，46(6):82 －84．

［3］ 秦裕斌，陳建華，黃曉．無(wú)線Mesh網(wǎng)絡(luò)技術(shù)及其應(yīng)用［J］．通信技術(shù)，2009，42(12):144 －146．

［4］ 姜維，唐俊華．隨機(jī)無(wú)線通信信道功率分配策略研究［J］．信息安全與通信保密，2013(1):40－42．

［5］ Akyildiz I F，Wang X D，Wang W L．Wireless meshnetwork:a survey［J］．Computer Networks，2005，47(4):445 －487．

［6］ 王輝，俞能海．無(wú)線Ad Hoc網(wǎng)絡(luò)中多路徑負(fù)載平衡性能分析［J］．通信學(xué)報(bào)，2005，26(11):30 －35．

［7］ 楊文靜，楊新宇，董翅勇．移動(dòng)Ad Hoc網(wǎng)絡(luò)中提高路由穩(wěn)定性的動(dòng)態(tài)備份多徑路由［J］．西安交通大學(xué)學(xué)報(bào)，2010，44(12):16－21．

［8］ Ma L，Denko K M．A routing metric for load － balancingin wireless mesh networks［C］．Niagara Falls，Canada:Advanced Information Networking and Applications Workshops，AINAW，2007:238 －242．