喬平安，邵 凱，劉運爽

(西安郵電大學計算機學院，陜西西安 710121)

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

1 基于WCETT的路由選擇準則

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

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

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

2 MWCETT路由選擇準則

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

2.1 MWCETT路由選擇準則的確立

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

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

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

2.2 路徑干擾因子η的計算

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

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

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

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

2.3 路徑延時因子δ的計算

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

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

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

2.4 排隊時延因子

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

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

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

2.5 MWCETT準則

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

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

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

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

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

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

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

4 結(jié)束語

針對已有的WCETT路由準則進行了分析，提出了一種滿足無線Ad Hoc網(wǎng)絡(luò)多徑多信道傳輸?shù)腗WCETT路由選擇準則，仿真驗證了該路由準則在吞吐量方面要優(yōu)于現(xiàn)有的WCETT路由選擇準則，后期將繼續(xù)完善該路由選擇準則，并拓展應(yīng)用到多路徑多信道的無線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］ 秦裕斌，陳建華，黃曉．無線Mesh網(wǎng)絡(luò)技術(shù)及其應(yīng)用［J］．通信技術(shù)，2009，42(12):144 －146．

［4］ 姜維，唐俊華．隨機無線通信信道功率分配策略研究［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］ 王輝，俞能海．無線Ad Hoc網(wǎng)絡(luò)中多路徑負載平衡性能分析［J］．通信學報，2005，26(11):30 －35．

［7］ 楊文靜，楊新宇，董翅勇．移動Ad Hoc網(wǎng)絡(luò)中提高路由穩(wěn)定性的動態(tài)備份多徑路由［J］．西安交通大學學報，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．