無線Mesh網(wǎng)絡(luò)機會路由技術(shù)研究

李鋒，沈崧

（中國航天科工集團第二研究院七〇六所 北京　100085）

無線Mesh網(wǎng)絡(luò)機會路由技術(shù)研究

李鋒，沈崧

（中國航天科工集團第二研究院七〇六所 北京100085）

文章介紹了無線Mesh網(wǎng)絡(luò)的特點和機會路由的原理，分析了ExOR的優(yōu)缺點，針對其沒有考慮路由路徑中轉(zhuǎn)發(fā)節(jié)點自身的因素，過度使用最優(yōu)路徑而導(dǎo)致網(wǎng)絡(luò)局部擁塞的問題，提出了路由節(jié)點能力評估模型，結(jié)合原有路徑度量方法，構(gòu)成新的路由度量。并引入?yún)?shù)限制候選轉(zhuǎn)發(fā)節(jié)點的個數(shù)，避免數(shù)據(jù)進入質(zhì)量較差的路徑。仿真實驗表明，新的機會路由方案，能夠較好地實現(xiàn)網(wǎng)絡(luò)負載均衡，數(shù)據(jù)吞吐量和網(wǎng)絡(luò)利用率都有所提升。

無線Mesh網(wǎng)絡(luò)；機會路由；路由度量；負載均衡

無線Mesh網(wǎng)絡(luò) （Wireless Mesh Network，WMN）［1］，又稱“無線網(wǎng)狀網(wǎng)”、“無線網(wǎng)格網(wǎng)”，是一種具有自組織、多跳、多點分布的新型無線寬帶接入網(wǎng)絡(luò)。無線網(wǎng)狀網(wǎng)極其廣泛，可以應(yīng)用于偏遠地區(qū)的寬帶接入、網(wǎng)絡(luò)語音通訊，政府機構(gòu)、學(xué)校、企事業(yè)單位的無線寬帶接入，遠程醫(yī)療、安全監(jiān)控、交通監(jiān)測、數(shù)字城市、軍隊戰(zhàn)場通訊系統(tǒng)等各個方面。路由技術(shù)作為WMN的關(guān)鍵技術(shù)之一，是目前國內(nèi)外研究的熱點問題。本文研究的機會路由［2］是由麻省理工大學(xué)的研究者提出的，機會路由是一種多路徑路由［3］，與傳統(tǒng)路由相比它沒有固定的傳輸路徑，通過多個中繼節(jié)點相互合作進行通信，充分利用無線廣播的特性，大大提高了端到端的數(shù)據(jù)吞吐量和網(wǎng)絡(luò)資源的利用率。然而無線鏈路質(zhì)量隨距離增加而下降，且易受臨近無線鏈路的干擾。因此在設(shè)計路由度量的時候，我們因該考慮到鏈路質(zhì)量的因素。另外過度使用最優(yōu)路徑可能導(dǎo)致網(wǎng)絡(luò)局部擁塞，嚴重影響網(wǎng)絡(luò)資源的均衡性。文中以此為出發(fā)點，參考現(xiàn)有的ExOR協(xié)議［4］，設(shè)計了一種新的路由度量。

1　無線Mesh網(wǎng)絡(luò)及其特點優(yōu)勢

無線Mesh網(wǎng)絡(luò)中的節(jié)點通常包括移動用戶、無線Mesh路由器和網(wǎng)關(guān)［5］。移動用戶通過無線技術(shù)接入無線Mesh路由器，不同于傳統(tǒng)無線網(wǎng)絡(luò)的單點AP（Access Point）接入，WMN中的移動用戶也可以為其他客戶端轉(zhuǎn)發(fā)數(shù)據(jù)。多個無線Mesh路由器可以構(gòu)成WMN骨干網(wǎng)［6］，無線Mesh路由器相互協(xié)同工作，數(shù)據(jù)經(jīng)過它們之間的合作多跳轉(zhuǎn)發(fā)，在網(wǎng)內(nèi)來回傳遞或穿過網(wǎng)關(guān)實現(xiàn)與Internet的通信。從而為移動用戶提供了類似“最后一英里”的骨干網(wǎng)接入環(huán)境，也稱為“Mesh云”。Mesh網(wǎng)具有可靠性和冗余性，當(dāng)其中的一些節(jié)點停止工作，其它節(jié)點可以選擇別的路徑繼續(xù)通信，從而保證整個網(wǎng)絡(luò)的運行。Mesh網(wǎng)也可以兼容多種通信技術(shù)，如802.11，802.15，802.16，蜂窩無線網(wǎng)技術(shù)等。

WMN具有下列優(yōu)勢：快速部署和易于安裝、非視距傳輸（NLOS）、健壯性、結(jié)構(gòu)靈活、高帶寬。

2　機會路由

由麻省理工大學(xué)研究者提出的機會路由策略，是一種用于無線多跳網(wǎng)絡(luò)的路由協(xié)議，其從源節(jié)點到目的節(jié)點發(fā)送的數(shù)據(jù)包并不是按一條固定的最佳路徑傳輸，而是充分利用無線網(wǎng)絡(luò)的廣播傳輸特性，每次數(shù)據(jù)包都轉(zhuǎn)發(fā)給一組節(jié)點，這些節(jié)點根據(jù)它們到目的節(jié)點的度量（Metric）來確定它們優(yōu)先級，優(yōu)先級高的節(jié)點，優(yōu)先轉(zhuǎn)發(fā)數(shù)據(jù)包給另外一組節(jié)點，如此重復(fù)直到目的節(jié)點。

圖1列舉了機會路由的兩個典型例子，來說明機會路由的優(yōu)點，假設(shè)各鏈路獨立，各鏈路正確傳輸報文的概率已在圖中標明。在圖1（a）中，傳統(tǒng)的單路徑路由會選擇S→B→D的傳輸路徑，一個數(shù)據(jù)包從S到D的成功傳遞概率為50% *100%=50%，成功送達一個數(shù)據(jù)包平均需要傳輸1/0.5+1=3次，而機會路由則同時利用A、B、C作為中繼，一個數(shù)據(jù)包從S到D的傳遞成功率為：［1-（1-0.5）3］*100%=87.5%，其中（1-0.5）3為A、B、C都沒有收到S發(fā)送的數(shù)據(jù)的概率。因此成功傳遞所需次數(shù)為1/［1-（1-0.5）3］+1=2.143。機會路由比傳統(tǒng)的但路徑路由的成功傳遞率更高，所需的平均傳遞次數(shù)更少，因而能大大提高數(shù)據(jù)的吞吐量。圖1（b），傳統(tǒng)路由中按照路由表逐次傳遞數(shù)據(jù)，而忽略目的節(jié)點有一定的概率直接接收到數(shù)據(jù)，使得資源利用率較低。而機會路由則可以避免這方面的不足，提高數(shù)據(jù)傳輸效率。

圖1　機會路由典型示例Fig.1　Typical example of opportunistic routing

ExOR（Extremely Opportunistic Routing）協(xié)議是一種基于端到端最短路徑策略的機會路由協(xié)議，它的路由度量為ETX端到端的期望傳輸次數(shù)（expected transmission count），其主要工作原理：源節(jié)點向目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)時，首先根據(jù)每個候選節(jié)點的ETX的排序來選擇轉(zhuǎn)發(fā)節(jié)點。候選集中的轉(zhuǎn)發(fā)節(jié)點也根據(jù)自身的ETX大小來給自己編排優(yōu)先級別號。當(dāng)候選集中的節(jié)點收到上游節(jié)點的廣播數(shù)據(jù)分組時，優(yōu)先級最高的那個節(jié)點則自動進行數(shù)據(jù)分組的轉(zhuǎn)發(fā)，同時發(fā)送通知信息給其他候選節(jié)點，其他候選節(jié)點偵聽到通知信息則放棄發(fā)送同一分組信息，轉(zhuǎn)而發(fā)送其他信息分組和優(yōu)先級搞的節(jié)點未能發(fā)送的分組，依次發(fā)送，直到目的節(jié)點接收到大部分的分組數(shù)據(jù)為止。

影響機會路由的關(guān)鍵因素有兩點：其一，如何選擇轉(zhuǎn)發(fā)節(jié)點，在無線Mesh網(wǎng)絡(luò)中，也就是設(shè)計合適的路由度量的問題；其二，如何協(xié)調(diào)候選轉(zhuǎn)發(fā)節(jié)點，使其不會發(fā)生沖突，順利的轉(zhuǎn)發(fā)報文。本文參考基于端到端策略的ExOR協(xié)議，考慮鏈路質(zhì)量度對數(shù)據(jù)路由的影響，以及網(wǎng)絡(luò)資源均衡的問題，提出了一種改進的路由度量。

3　基于ExOR協(xié)議的路由度量的改進

3.1總體設(shè)計思路

基于端到端的最短路徑策略的ExOR協(xié)議是一種有效的簡單機會路由協(xié)議，它充分利用的廣播傳輸?shù)奶匦?，通過節(jié)點間的協(xié)作，能夠提高數(shù)據(jù)的傳輸效率，保證傳輸?shù)姆€(wěn)定性，但是卻無法做到全局最優(yōu)，過度使用最優(yōu)路徑反而帶來網(wǎng)絡(luò)的局部擁塞，嚴重影響網(wǎng)絡(luò)資源的均衡性。

ExOR協(xié)議的路由度量為端到端的期望傳輸次數(shù)ETX，源節(jié)點向目的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)時，根據(jù)每個候選節(jié)點的ETX的排序來選擇轉(zhuǎn)發(fā)節(jié)點。但是這種算法卻沒有考慮路由節(jié)點自身是否滿足條件就強制轉(zhuǎn)發(fā)，常使得數(shù)據(jù)偏離到鏈路質(zhì)量較差路徑上，另外候選節(jié)點過多而混入質(zhì)量較差的節(jié)點，也可能使得數(shù)據(jù)進入鏈路質(zhì)量較差的傳輸路徑，從而導(dǎo)致重傳的可能性變大，數(shù)據(jù)延時加大，甚至數(shù)據(jù)丟失。

為了減輕最優(yōu)路徑的負擔(dān)，防止網(wǎng)絡(luò)擁塞，本文建立了一種鏈路節(jié)能力評估模型，將節(jié)點能力和ETX相結(jié)合作為一種新的路由度量，這樣降低負載過重的節(jié)點的能力，減輕其負擔(dān)，以此達到網(wǎng)絡(luò)資源均衡的目的。針對候選節(jié)點過多而造成的問題，引入EAX來限制候選節(jié)點集的大小。這里的EAX（期望任意路徑傳輸數(shù)）指數(shù)據(jù)發(fā)端到終端所有可能的路徑的ETX的加權(quán)平均。這種改進的機會路由協(xié)議是一種基于ExOR協(xié)議的改進，本文稱其為EExOR協(xié)議（Extention of Extremely Opportunistic Routing）。

3.2EExOR協(xié)議路由度量模型

新的路由度量，同時考慮鏈路質(zhì)量和節(jié)點能力的因素，其中鏈路質(zhì)量仍由源節(jié)點通過候選節(jié)點到達目的節(jié)點的期望傳輸次數(shù)（ETX）表示。在本文的節(jié)點能力評估模型中，引入環(huán)境屬性，既包含節(jié)點資源，又包含消息屬性。融入此消彼長的因素，隨著節(jié)點負載過重，降低其對外能力，限制轉(zhuǎn)發(fā)數(shù)據(jù)流量，實現(xiàn)自我保護，以達到網(wǎng)絡(luò)資源均衡的目的。

3.2.1前提假設(shè)

參考Mesh網(wǎng)絡(luò)現(xiàn)有的各種協(xié)議，文中做出以下假設(shè)：

1）節(jié)點是無私的，會盡自己的能力轉(zhuǎn)發(fā)數(shù)據(jù)。

2）當(dāng)節(jié)點資源緊缺時，通過降低自身對外的能力，實現(xiàn)自我保護，減少局部擁塞。

3）數(shù)據(jù)包的發(fā)送過程中節(jié)點與節(jié)點之間的投遞率保持穩(wěn)定不變，與此同時，同一節(jié)點與不同鄰居節(jié)點之間的鏈路始終保持統(tǒng)計獨立。

4）文中討論的Mesh網(wǎng)絡(luò)都是有源或可充電的，不涉及能耗問題。

3.2.2網(wǎng)絡(luò)模型

本文中的網(wǎng)絡(luò)模型以無向圖圖來G=（V，L，D）表示來表示。V為網(wǎng)絡(luò)中節(jié)點集合，節(jié)點數(shù)為N=［V］，Vi∈V（i=1，2，…，N）表示網(wǎng)絡(luò)中的任意節(jié)點，N個節(jié)點隨機分布于一個給定的區(qū)域內(nèi)。L是節(jié)點間鏈路集合的表示，D則是節(jié)點間的投遞率集合的表示，其中l(wèi)（i，j）∈L為任意兩個節(jié)點間的鏈路，并且其對應(yīng)的投遞率為d（i，j）∈D，它表示一個數(shù)據(jù)包經(jīng)節(jié)點Vi的一次傳輸成功到達節(jié)點Vj的概率。節(jié)點間的投遞率可以通過洪泛的方式來獲取。

3.2.3環(huán)境屬性設(shè)計

候選節(jié)點的選取是機會路由中兩個關(guān)鍵點之一，它決定著整個網(wǎng)絡(luò)的性能優(yōu)劣，是與整體設(shè)計思路密切相關(guān)的重要因素。也影響到基于端到端路徑的策略是否能夠選取全局最優(yōu)解的問題。因此根據(jù)實際環(huán)境，獲取最有效的路由度量標準更為關(guān)鍵。EExOR協(xié)議中的環(huán)境屬性包含兩個因素：消息屬性和節(jié)點資源。

消息的屬性包括消息的大小l和剩余時間TTL。消息的大小即為消息本身占緩存區(qū)的大小。而TTL預(yù)示著消息消亡前的剩余時間。這意味著消息在網(wǎng)絡(luò)中存在時間越長，那么它的傳輸就越緊迫。

節(jié)點資源主要參考因素為緩存空間。緩存空間是路由節(jié)點本身存儲信息能力的資源體現(xiàn)，決定著信息轉(zhuǎn)發(fā)等待時間的長短。定義緩存空間為剩余存儲容量空閑百分比，其公式定義如下

其中Bsi和Buf分別為剩余存儲空間和總的存儲容量。Bi則是緩存區(qū)的空閑百分比。很明顯節(jié)點空閑緩存區(qū)越大，其承載數(shù)據(jù)傳輸?shù)哪芰驮酱蟆?/p>

3.2.4節(jié)點能力評估

文中設(shè)計的EExOR協(xié)議中，由于節(jié)點是無私的，會盡自己的能力轉(zhuǎn)發(fā)數(shù)據(jù)，評估節(jié)點對外數(shù)據(jù)轉(zhuǎn)發(fā)能力時，需考慮自身現(xiàn)有資源，做出合適的能力評估，另外網(wǎng)絡(luò)中數(shù)據(jù)包受其生存時間的限制，有時急需轉(zhuǎn)發(fā)，因而評估節(jié)點能力也應(yīng)該到消息的屬性。定義節(jié)點能力參數(shù)如下：

這里l表示需要傳遞消息的大小，Bi表示節(jié)點i的緩存區(qū)空閑百分比，Tres和Tttl分別表示消息的剩余TTL和消息的原始的TTL。α和β分別是Bi和TTL的權(quán)值，并且α+β=1。因此0≤Ci≤1。

從上式可以看出，節(jié)點能力越高，其轉(zhuǎn)發(fā)數(shù)據(jù)的愿望就越高，相反的，愿望就越低。節(jié)點的空閑緩存區(qū)越小，其轉(zhuǎn)發(fā)數(shù)據(jù)的愿望就越小，更多的考慮自身數(shù)據(jù)處理要求；消息在節(jié)點緩存區(qū)滯留時間越長，對下一節(jié)點轉(zhuǎn)發(fā)愿望的影響就越大，消息得到轉(zhuǎn)發(fā)的可能性就越高。這樣消息得到轉(zhuǎn)發(fā)，節(jié)點的空閑緩存就變大了，就能滿足更多的數(shù)據(jù)轉(zhuǎn)發(fā)的請求。綜上，節(jié)點總是盡自己的能力轉(zhuǎn)發(fā)數(shù)據(jù)，同時又能平衡消息的迫切性。

3.2.5路由度量選路

節(jié)點在選擇候選節(jié)點時，由路由度量確定各候選節(jié)點的優(yōu)先級，本文設(shè)計的路由度量由ETX和節(jié)點能力參數(shù)Ci通過線性耦合共同確定，路由節(jié)點優(yōu)先級定義如下：

式（3）中ETX為源節(jié)點通過候選節(jié)點i到達目的節(jié)點的期望傳輸次數(shù)，ETX的計算參見3.1節(jié)中ExOR協(xié)議。數(shù)據(jù)到達目的節(jié)點的路徑越短，候選節(jié)點的ETX越小，Pi越小，候選節(jié)點i優(yōu)先級越高。上式中Ci為候選節(jié)點的能力值，Ci越大，Pi越小，候選節(jié)點i優(yōu)先級越高。在選擇候選節(jié)點時，由EAX限制候選節(jié)點集的大小，選擇優(yōu)先級高的節(jié)點作為候選節(jié)點。這里EAX（期望任意路徑傳輸數(shù)）指數(shù)據(jù)發(fā)端到終端所有可能的路徑的ETX的加權(quán)平均。

綜上，EExOR協(xié)議在路由選路和候選節(jié)點的選擇過程中，既考慮了鏈路質(zhì)量的因素，又考慮到節(jié)點自身能力。而在節(jié)點能力評估模型中也很好的平衡了節(jié)點資源和消息屬性對節(jié)點能力的影響。在EExOR協(xié)議中生存時間越短的消息，能夠得到更快的轉(zhuǎn)發(fā)，如此能夠減少數(shù)據(jù)丟失，提高傳輸效率。當(dāng)節(jié)點負載過重時，通過調(diào)整自身能力值，較少數(shù)據(jù)流量，實現(xiàn)網(wǎng)絡(luò)的負載平衡，減少擁塞，提高網(wǎng)絡(luò)的吞吐量。

4　仿真驗證與性能分析

文中采用NS2仿真軟件在Linux操作系統(tǒng)下進行仿真。選取無線網(wǎng)絡(luò)最常用的3個指標：網(wǎng)絡(luò)端到端的成功投遞率、端到端平均延遲和吞吐量。

消息的產(chǎn)生率能夠反映這個網(wǎng)絡(luò)的負載擁塞狀態(tài)，產(chǎn)生率越大，整個網(wǎng)絡(luò)的傳輸壓力越大，每個節(jié)點的緩存空間就越擁擠。如圖2所示，ExOR和EExOR協(xié)議隨著產(chǎn)生率的增加，成功投遞率都有所減少。在相同的消息產(chǎn)生率下，EExOR協(xié)議的成功投遞率明顯比ExOR協(xié)議的高。

圖2　成功投遞率Fig.2　Successfully delivery rate

如圖3所示，整體來看，EExOR協(xié)議比ExOR協(xié)議的網(wǎng)絡(luò)平均延時短，其原因在于EExOR協(xié)議中，節(jié)點根據(jù)自身負載和消息屬性調(diào)整自身能力，使得網(wǎng)絡(luò)負載均衡性更高，且生存時間短的消息會得到優(yōu)先轉(zhuǎn)發(fā)。擁塞少了，消息時延也就越小。

從圖4中可以看出，EExOR和ExOR分別隨著產(chǎn)生率的增加而趨于平緩。從圖中的整體趨勢來看，EExOR的吞吐量要高于ExOR，說明EExOR協(xié)議的網(wǎng)絡(luò)局部擁塞更少了，網(wǎng)絡(luò)資源的均衡性得到了提高。

仿真實驗表明，相比于ExOR協(xié)議，EExOR在成功投遞率、傳輸時延和吞吐量這3個性能指標上都有所提升。

5　結(jié)　論

Mesh網(wǎng)絡(luò)具有重要的理論價值和廣泛的應(yīng)用前景，它是當(dāng)今無線網(wǎng)絡(luò)領(lǐng)域的研究熱點。本文通過研究Mesh網(wǎng)絡(luò)的機會路由協(xié)議，提出了基于ExOR協(xié)議的改進方案。設(shè)計了一種節(jié)點能力評估模型，結(jié)合原有的路由度量ETX，能夠更好地選擇機會路由中數(shù)據(jù)轉(zhuǎn)發(fā)的候選節(jié)點，同時引入EAX限制候選節(jié)點個數(shù)。新的EExOR協(xié)議能夠較好地實現(xiàn)網(wǎng)絡(luò)負載均衡，提高了數(shù)據(jù)的吞吐量和網(wǎng)絡(luò)的利用率。

圖3　平均時延Fig.3　The average time delay

圖4　端到端吞吐量Fig.4　The throughput from end to end

［1］Steve Methley.無線Mesh網(wǎng)絡(luò)基礎(chǔ)［M］.王平，李穎哲，黃飛，譯.西安：西安交通大學(xué)出版社，2012.

［2］王夢瑩.無線Mesh網(wǎng)絡(luò)的改進研究［D］.南京：南京郵電大學(xué)，2013.

［3］Brunoa R，Nurchis M.Survey on diversity-based routing in wireless mesh networks：challenges and solution［J］.Computer Communications，2010，33（3）：268-282

［4］ExOR:Opportunistic Multi-Hop Routing for Wireless Networks，Sanjit Biswas，Robert Morris，Presented at SIGCOMM′05，2005，Copyright ACM，Philadelphia，Penn.2005，ACM No. 1-59593-009-4/05/0008.

［5］IEEE 802.11s.IEEE amendment:mesh networking.IEEE P802.11s/D1.06，2007，Piscataway.

［6］鄭彥光，徐平平，常瑞.無線Mesh網(wǎng)絡(luò)技術(shù)及其應(yīng)用［J］.電力系統(tǒng)通信，2007，28（177）:1-2.

The study of opportunistic routing for wireless mesh networks

LI Feng，SHEN Song
（Second Academy of China Aerospace Science and Industry Corporation，Beijing 100854，China）

This paperintroduces the character of wireless Mesh networks and the principle of opportunistic routing，analyzed the advantages and disadvantages of ExOR.The ExOR protocol ignores the ability of routing nodes during data transmision and excessive uses of the optimal path which leads to local network congestion problem.To solve these problems the routing node capability assessment model is put forward，and forms a new routing metric combining the original path measurement method. And we introduce a parameter to limit the candidate number of routing nodes，to avoid the data into the path of poor quality. The simulation experiments shows that the new routing scheme can well realize the network load balance，improve data throughput network utilization.

wireless Mesh networks；opportunistic routing；routing metric；load balance

TP393

A

1674－6236（2016）05-0058-04

2015-04-18稿件編號：201504194

李 鋒（1990—），男，湖南永順人，碩士研究生。研究方向：計算機系統(tǒng)結(jié)構(gòu)。