基于多網(wǎng)卡多信道MESH網(wǎng)路由協(xié)議

摘要無線MESH網(wǎng)不同于傳統(tǒng)的無線多跳網(wǎng)絡(luò)，路由器是固定的，移動(dòng)性不是主要問題。因此迫切需要一種新的準(zhǔn)則適應(yīng)這種網(wǎng)絡(luò)。WMN使用多網(wǎng)卡和多信道以提高網(wǎng)絡(luò)容量。WCETT是為多網(wǎng)卡多信道無線MESH網(wǎng)絡(luò)設(shè)計(jì)的準(zhǔn)則,但是必需的帶寬計(jì)算很復(fù)雜。本文提出了一種新的路由準(zhǔn)則SMETT，以避免復(fù)雜的帶寬計(jì)算，并且設(shè)計(jì)一種名為傳輸感染因子的傳輸干擾模型使ETT更接近真正的傳輸。

關(guān)鍵詞無線MESH網(wǎng)絡(luò)；多信道；多網(wǎng)卡；路由準(zhǔn)則

1簡(jiǎn)介

無線MESH網(wǎng)絡(luò)在近幾年里已經(jīng)成為研究的熱點(diǎn)。由于它的一些特殊的應(yīng)用已經(jīng)引起了商業(yè)的注意和巨大的興趣。雖然WMN是由AdHoc網(wǎng)絡(luò)發(fā)展而來，但它是一種全新的拓?fù)?，AdHoc的路由已經(jīng)不再適用于WMN。絕大部分傳統(tǒng)的AdHoc路由準(zhǔn)則是選擇從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小跳數(shù)。如果WMN也使用最小跳數(shù)準(zhǔn)則，則容易在路由中包括較長(zhǎng)的無線鏈路，導(dǎo)致較低的吞吐量，從而影響其達(dá)到最佳性能。因此路由準(zhǔn)則可以根據(jù)無線鏈路的質(zhì)量來選擇較好的路徑。MESH路由問題的關(guān)鍵就在于改進(jìn)網(wǎng)絡(luò)容量和提高個(gè)別傳輸?shù)男阅苌稀Ｎ覀兺ㄟ^在每個(gè)節(jié)點(diǎn)上安裝多個(gè)網(wǎng)卡來改進(jìn)WMN容量的方法。這樣可以使節(jié)點(diǎn)能夠同時(shí)地傳輸和接收數(shù)據(jù)。同時(shí)每個(gè)節(jié)點(diǎn)有多個(gè)網(wǎng)卡，也能提供一個(gè)實(shí)現(xiàn)多信道的策略。目前已有很多方法可以進(jìn)行分布式的頻道分配。

本文提出一種新的路由準(zhǔn)則，稱為SMETT，是為多網(wǎng)卡多信道環(huán)境而設(shè)計(jì)的。與WCETT不同的是它不考慮無線鏈路的帶寬。因?yàn)闊o線網(wǎng)路的帶寬不容易計(jì)算，該如何避免帶寬的計(jì)算是一個(gè)主要議題。而且在本文中，當(dāng)我們計(jì)算ETT的時(shí)候，也考慮到鏈路的干擾。在無線網(wǎng)路中，如果他們?cè)诒舜说母蓴_范圍里，無線鏈路上的傳輸可能互相干擾。提供一種傳輸感染因子用于我們的準(zhǔn)則SMETT。

2問題的形成

系統(tǒng)體系結(jié)構(gòu)

如圖1所示，在無線MESH網(wǎng)絡(luò)體系結(jié)構(gòu)中，每個(gè)節(jié)點(diǎn)有多個(gè)網(wǎng)卡和多條信道。這里不考慮如何分配頻道。假設(shè)體系結(jié)構(gòu)的每個(gè)路由節(jié)點(diǎn)都是相對(duì)固定的，在給定區(qū)域的每個(gè)點(diǎn)至少被一個(gè)接入點(diǎn)覆蓋。為了覆蓋一個(gè)大的區(qū)域，需要很多的AP。通常情況下，把每個(gè)AP連接到以太網(wǎng)上，再依次連接到Internet是不現(xiàn)實(shí)的。因此只有一些AP連進(jìn)有線基礎(chǔ)設(shè)施，作為網(wǎng)關(guān)工作。移動(dòng)終端用戶直接從AP或從多跳AP訪問互聯(lián)網(wǎng)。

圖1WMN的體系結(jié)構(gòu)

傳輸干擾:

在有線網(wǎng)絡(luò)中，因?yàn)楦鞴?jié)點(diǎn)是獨(dú)立的，所以鏈路上的任何傳輸都不會(huì)干擾其他鏈路上的傳輸。然而，在無線網(wǎng)路中，如果他們?cè)诒舜说母蓴_范圍內(nèi)，一個(gè)無線鏈路上的傳輸就有可能干擾其他的鏈路。

子程序利用一個(gè)簡(jiǎn)單的載波偵聽多路訪問算法。當(dāng)一個(gè)分組想要傳輸時(shí)，它通過傳輸分組占用介質(zhì)。如果偵聽到介質(zhì)是空閑的，那么分組將會(huì)被傳輸。否則，在當(dāng)前沖突窗口大小內(nèi)任意選擇的退避計(jì)算器工作，并且讓退避計(jì)算器開始倒計(jì)時(shí)，直到媒體空閑。當(dāng)它感覺媒體忙碌時(shí)，節(jié)點(diǎn)中止計(jì)算器的倒計(jì)時(shí)窗口。這稱為二進(jìn)制指數(shù)退避。

當(dāng)一個(gè)節(jié)點(diǎn)傳輸一個(gè)分組時(shí)，它需要為可能的重傳將發(fā)送的分組存在緩沖器中。當(dāng)分組被確認(rèn)收到時(shí)，緩沖器中的分組才被移去。如果有任何傳輸失敗，緩沖器會(huì)為重傳保護(hù)丟失的分組。因此緩沖器不空的時(shí)候?qū)?huì)增加。由于如果一個(gè)分組仍然存在緩沖器中，節(jié)點(diǎn)會(huì)試著占用媒體，所以這會(huì)影響在它的干擾范圍內(nèi)的節(jié)點(diǎn)的傳輸。

預(yù)期傳輸時(shí)間

在提出預(yù)期傳輸時(shí)間前，我們首先簡(jiǎn)短地描述ETX準(zhǔn)則。ETX度量準(zhǔn)則用于測(cè)量傳輸?shù)念A(yù)期數(shù)量，包括重傳。ETX的推導(dǎo)開始于前向和反向的分組損失概率的測(cè)量，分別用pf和pr表示，然后計(jì)算預(yù)期傳輸數(shù)量。

我們從計(jì)算分組傳輸不成功概率開始。因?yàn)閰f(xié)議需要的是傳輸成功，所以分組必須成功地被應(yīng)答。讓p表示從x到y(tǒng)的分組傳輸不成功的概率：

將會(huì)重傳一個(gè)傳輸不成功的分組。讓S表示分組從x到y(tǒng)經(jīng)k次嘗試后成功發(fā)送的概率。

最后，從x到y(tǒng)成功地傳送一個(gè)分組的必需的預(yù)期傳輸數(shù)量用ETX表示：

ETX準(zhǔn)則用于路由選擇。它將選擇最低的積累ETX的路徑。但是ETX準(zhǔn)則不一定能為WMN選擇較高吞吐量的路徑。例如，它可能選擇鏈路，但不選損失概率比較低的鏈路。在文章[3]中，作者給出了一個(gè)信道差異性優(yōu)先選擇，提供了一種新的準(zhǔn)則，稱為預(yù)期傳輸時(shí)間。它定義為“帶寬修正ETX”。讓S表示分組的大小，B表示鏈路的帶寬。那么ETT表示為：

根據(jù)方程和來計(jì)算ETT，需要知道向前和反向損失率以及每個(gè)鏈路的帶寬。有兩種方法可以獲得每個(gè)鏈路的帶寬。一種方法是每個(gè)網(wǎng)卡給定值的固定帶寬，但是固定速率不可能適合實(shí)際傳輸。另一個(gè)方法是讓網(wǎng)卡自動(dòng)地為每個(gè)分組選擇帶寬，這也是不現(xiàn)實(shí)的。

3SMETT:激勵(lì)預(yù)期傳輸時(shí)間總數(shù)

傳輸感染因子

在前面，我們解釋了如何工作，說明了節(jié)點(diǎn)的緩沖器能影響鏈路上的傳輸。如果緩沖器是空的,只要它接受，節(jié)點(diǎn)能發(fā)送分組。那么它不影響其他傳輸。然而，如果節(jié)點(diǎn)緩沖器長(zhǎng)時(shí)間不空，就不會(huì)傳輸剛剛收到的分組。因此節(jié)點(diǎn)緩沖器不空的時(shí)間會(huì)影響鏈路上其它的傳輸。我們定義一個(gè)鏈路傳輸感染因子如下。

TIF不但解釋了一個(gè)鏈路上最初的傳輸負(fù)載，而且解釋了因丟失分組重傳而增加的負(fù)載。例如，傳輸時(shí)間是方程ETT的2倍，如果鏈路的損失率是0，即ETX=1，那么TIF=，因?yàn)楣?jié)點(diǎn)的緩沖器一半時(shí)間不空，節(jié)點(diǎn)的傳輸是忙碌的。然而，如果鏈路的損失率是，緩沖器由于重傳不會(huì)是空的。那么，TIF=1。

由于ETT表示鏈路的損失概率，因此TIF與它有關(guān)?，F(xiàn)在我們假設(shè)鏈路K-1和鏈路K是連續(xù)的鏈路，他們的ETT分別是ETXK-1和ETXK。當(dāng)ETXK/ETXK-1小于時(shí)，鏈路K會(huì)比鏈路K-1有較多的空閑時(shí)間，那么TIFK可表示為TIFK-1*EK/EK-1。當(dāng)大于時(shí)，意味著節(jié)點(diǎn)K緩沖器是充滿的，一些分組可能被丟棄。因此，TIFK可以表示為：

激勵(lì)預(yù)期傳輸時(shí)間METT

激勵(lì)預(yù)期傳輸時(shí)間考慮了傳輸干擾。它是一種“干擾調(diào)整的ETT”。首先，我們假設(shè)路徑的源節(jié)點(diǎn)是處于無干擾理想狀態(tài)。因此，首先我們?cè)O(shè)定TIF初值為TIF1=1。然后，讓ETXk表示鏈路k預(yù)期的傳輸次數(shù)，S是分組的大小，而Dk是鏈路k發(fā)送數(shù)據(jù)速率。因此，鏈路的干擾調(diào)整k定義為：

因?yàn)楦蓴_，如果緩沖器不空，所有的分組將會(huì)競(jìng)爭(zhēng)占用媒體。如TIF定義，如果真正的傳輸時(shí)間是方程的2倍，那么TIF=。因此TIF與METT是反比，且最初的ETT被定義為，鏈路的激勵(lì)ETT必須分開TIFk。因?yàn)門IF能表示真正的傳輸，所以使用B是不必要的。我們改為使用Dk。

根據(jù)方程、和計(jì)算METT，我們需要了解正向和反向的損失概率、傳輸率、每個(gè)鏈路的傳輸感染因子。pf和pr的值可通過用廣播分組技術(shù)來估計(jì)，每個(gè)節(jié)點(diǎn)定期地送出廣播探測(cè)分組。廣播分組不由轉(zhuǎn)發(fā)。節(jié)點(diǎn)跟蹤從每個(gè)相鄰節(jié)點(diǎn)在滑動(dòng)時(shí)間窗口期間收到的探測(cè)分組數(shù)，包括他們自己的探測(cè)信息。節(jié)點(diǎn)能從相鄰節(jié)點(diǎn)在時(shí)間窗口內(nèi)收到的探測(cè)分組數(shù)直接計(jì)算pr，還可以使用從相鄰節(jié)點(diǎn)收到的最后一個(gè)探測(cè)分組有關(guān)他們自己的信息來計(jì)算pf。然后計(jì)算ETX。我們也能使用方程計(jì)算TIF。

路徑準(zhǔn)則

通過計(jì)算，我們得到所有鏈路的METT。這部分提出如何計(jì)算在源節(jié)點(diǎn)上所有的METT。我們的路徑準(zhǔn)則稱為SMETT。它是路徑的預(yù)期傳輸時(shí)間。因此我們能設(shè)定SMETT是路徑上所有單跳的METT的總和。

同時(shí)，SMETT需要考慮信道差異性的影響。只是增加METT不能保證這個(gè)特性，因?yàn)槲覀儾荒軈^(qū)別在不同的頻道上的單跳。為了反映這一點(diǎn)，我們的準(zhǔn)則定義了附加項(xiàng)Xi。

Xj是信道j上單跳的傳輸時(shí)間總和，總吞吐量受瓶頸頻道支配，瓶頸頻道有最大的Xj。另外，我們引入一個(gè)可調(diào)參數(shù)用來計(jì)算SMETT。

4結(jié)論

本文提出了一種新的多網(wǎng)卡多信道無線MESH網(wǎng)絡(luò)的路由準(zhǔn)則。這個(gè)路由準(zhǔn)則避免了計(jì)算網(wǎng)絡(luò)帶寬，而且考慮可能是整個(gè)傳輸?shù)钠款i的干擾。它更適合真實(shí)的世界。

路由仿真顯示這個(gè)新的路由準(zhǔn)則工作得很好:與單跳計(jì)數(shù)準(zhǔn)則和WCETT準(zhǔn)則相比較。平均吞吐量比單跳計(jì)數(shù)準(zhǔn)則改進(jìn)了20%以上，比WCETT改進(jìn)了10%以上。整個(gè)丟失概率也已經(jīng)減少。

參考文獻(xiàn)

[1]RichardDraves,JitendraPadhye,BrianZill，“RoutinginMulti-Radio,Multi-HopWirelessMeshNetworks”,MicrosoftResearch,September2005

[2]AshishRaniwala，KartikGopalan，andTzi-ckerChiueh，“CentralizedChannelAssignmentandRoutingAlgorithmsforMulti-ChannelWirelessMeshNetwork”，MobileComputingandCommunicationsReview，，，，April2004

[3]AshishRaniwalaa