關(guān)學(xué)銘，齊先飛，馬遙知

(沈陽工業(yè)大學(xué)遼陽分校，遼寧 遼陽 111003)

0 引 言

隨著無線網(wǎng)絡(luò)的不斷發(fā)展，移動(dòng)終端的種類和數(shù)量與日俱增，用戶對無線網(wǎng)絡(luò)的體驗(yàn)要求也不斷提高，迫切需要更好的無線網(wǎng)絡(luò)架構(gòu)來提供高吞吐量、低延遲及高穩(wěn)定性的網(wǎng)絡(luò)。無線Mesh網(wǎng)絡(luò)因其高容量、高速率、易實(shí)現(xiàn)及代價(jià)小等優(yōu)點(diǎn)被各大研究機(jī)構(gòu)和部門關(guān)注，被視為解決無線網(wǎng)絡(luò)QoS的重要解決方案[1]。無線Mesh網(wǎng)絡(luò)實(shí)現(xiàn)容易使其適用于較偏遠(yuǎn)的區(qū)域，同樣也作為解決“最后一公里”網(wǎng)絡(luò)問題的方案。

無線Mesh網(wǎng)絡(luò)的路由是目前研究的熱點(diǎn)問題，目前主要的無線Mesh路由分為以下幾類：反應(yīng)式路由、先應(yīng)式路由、混合式路由、機(jī)會(huì)路由和基于網(wǎng)絡(luò)編碼的路由。前3種是早期網(wǎng)絡(luò)研究成果引入無線Mesh網(wǎng)絡(luò)，后2種是針對無線Mesh網(wǎng)絡(luò)特點(diǎn)提出的路由解決方案。

機(jī)會(huì)路由是由MIT的Biswas等[2]在2004年提出來的，機(jī)會(huì)路由是無線Mesh網(wǎng)絡(luò)路由的重要研究方向，與傳統(tǒng)路由相比，機(jī)會(huì)路由更加充分地發(fā)揮了無線網(wǎng)絡(luò)廣播的特性，不用預(yù)先設(shè)置路由線路，而是通過競爭的方式來動(dòng)態(tài)地確定數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)。數(shù)據(jù)傳遞之前需要確定轉(zhuǎn)發(fā)的候選節(jié)點(diǎn)，并通過對傳遞節(jié)點(diǎn)的優(yōu)先級進(jìn)行排序，候選節(jié)點(diǎn)都會(huì)接收到發(fā)送方廣播的數(shù)據(jù)包，通過競爭的方式最先成功轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)就是實(shí)際轉(zhuǎn)發(fā)的節(jié)點(diǎn)，其他節(jié)點(diǎn)將放棄轉(zhuǎn)發(fā)該數(shù)據(jù)包，數(shù)據(jù)轉(zhuǎn)發(fā)的路徑也是通過這種競爭的方式動(dòng)態(tài)地確定出來[3-4]。

機(jī)會(huì)路由能提高無線Mesh網(wǎng)絡(luò)的吞吐量和可靠性，目前已經(jīng)成為研究的熱點(diǎn)。目前主要的機(jī)會(huì)路由有ExOR、SOAR及ROMER等。ExOR[5]是最早被提出的一種機(jī)會(huì)路由算法，ExOR 路由充分利用了無線信道廣播的特性，通過選擇距離目的節(jié)點(diǎn)最近的幾點(diǎn)作為下一跳節(jié)點(diǎn)，ExOR使用ETX度量中間節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離，從而確定候選節(jié)點(diǎn)的集合。ExOR路由充分發(fā)揮了無線信道的開放性，提高了數(shù)據(jù)轉(zhuǎn)發(fā)的效率。但是ExOR的算法復(fù)雜性也限制了算法的性能提升，而且重復(fù)性數(shù)據(jù)的不斷增加會(huì)使算法性能隨之下降。SOAR[6]路由是基于ExOR的改進(jìn)算法，它也使用ETX作為路由度量。它在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立最短路徑，并通過設(shè)置EXT門限值來避免數(shù)據(jù)重復(fù)和干擾，算法將數(shù)據(jù)的傳輸節(jié)點(diǎn)集中在最短路徑附近，提高了網(wǎng)絡(luò)轉(zhuǎn)發(fā)的效率。ROMER[7]是一種按照分組方式實(shí)現(xiàn)機(jī)會(huì)轉(zhuǎn)發(fā)的路由算法。機(jī)會(huì)路由的主要研究問題大多集中在候選節(jié)點(diǎn)的選擇上，候選節(jié)點(diǎn)的算法以及候選節(jié)點(diǎn)數(shù)量的確定是主要的熱點(diǎn)研究問題[8-9]。

1 問題描述

隨著無線網(wǎng)絡(luò)的不斷發(fā)展，移動(dòng)終端的種類和數(shù)量與日俱增。在有線網(wǎng)絡(luò)中，數(shù)據(jù)鏈路所受的干擾較少，數(shù)據(jù)傳輸?shù)馁|(zhì)量較高，數(shù)據(jù)的丟失率較低，一般會(huì)使用數(shù)據(jù)轉(zhuǎn)發(fā)的跳數(shù)、往返時(shí)延等作為路由的度量標(biāo)準(zhǔn)來說明網(wǎng)絡(luò)鏈路及轉(zhuǎn)發(fā)的性能[10]。而在無線網(wǎng)絡(luò)中是使用信道作為傳輸路徑，這就使得傳輸數(shù)據(jù)過程中很容易受到干擾，信號的質(zhì)量也得不到保證，很容易造成數(shù)據(jù)的丟包，因此，無線網(wǎng)絡(luò)說明鏈路質(zhì)量的路由度量方法與有線網(wǎng)絡(luò)不同，一般是使用時(shí)延、誤碼率等作為度量標(biāo)準(zhǔn)。傳統(tǒng)機(jī)會(huì)路由[11]有其自身的優(yōu)勢，但也有缺點(diǎn)[12-13]，研究表明使用機(jī)會(huì)路由過程中，真正負(fù)責(zé)轉(zhuǎn)發(fā)的網(wǎng)絡(luò)節(jié)點(diǎn)往往總是同一批候選節(jié)點(diǎn)，其他的候選節(jié)點(diǎn)很少有成功轉(zhuǎn)發(fā)的機(jī)會(huì)。一直處于這種“壟斷”的轉(zhuǎn)發(fā)狀態(tài)，可能會(huì)導(dǎo)致網(wǎng)絡(luò)資源利用率低、網(wǎng)絡(luò)負(fù)載不均衡等問題的出現(xiàn)。無線Mesh網(wǎng)絡(luò)機(jī)會(huì)路由測量算法復(fù)雜度高也會(huì)給網(wǎng)絡(luò)帶來負(fù)擔(dān)。無線Mesh網(wǎng)絡(luò)機(jī)會(huì)路由算法會(huì)選擇某種度量標(biāo)準(zhǔn)(如ETX、ETT等)來確定候選節(jié)點(diǎn)集合，并對候選節(jié)點(diǎn)集合進(jìn)行排序，然后對數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)，候選集合通過競爭的方式來爭取轉(zhuǎn)發(fā)的機(jī)會(huì)[14]。候選節(jié)點(diǎn)的確定需要轉(zhuǎn)發(fā)節(jié)點(diǎn)對候選節(jié)點(diǎn)集合進(jìn)行排序等操作，這將為轉(zhuǎn)發(fā)節(jié)點(diǎn)帶來額外的開銷，在無線Mesh終端設(shè)備密集的區(qū)域這些開銷將嚴(yán)重影響網(wǎng)絡(luò)性能，特別是對服務(wù)質(zhì)量要求較高的業(yè)務(wù)，這樣的問題可能導(dǎo)致網(wǎng)絡(luò)延遲增大、網(wǎng)絡(luò)資源利用率下降等問題。

為了解決以上問題，本文對機(jī)會(huì)路由候選節(jié)點(diǎn)算法進(jìn)行研究，從問題分析可知，減少候選節(jié)點(diǎn)數(shù)量會(huì)使候選節(jié)點(diǎn)選擇時(shí)的系統(tǒng)開銷降低，但是這樣會(huì)降低網(wǎng)絡(luò)轉(zhuǎn)發(fā)的成功概率，增加數(shù)據(jù)重傳的次數(shù)。

設(shè)機(jī)會(huì)路由發(fā)送節(jié)點(diǎn)(S)的候選節(jié)點(diǎn)個(gè)數(shù)為n，發(fā)送節(jié)點(diǎn)到候選節(jié)點(diǎn)的成功概率是p1，候選節(jié)點(diǎn)(C1, C2, …, Cn)轉(zhuǎn)發(fā)到目標(biāo)節(jié)點(diǎn)(D)的成功概率是p2，如圖1所示。

圖1 機(jī)會(huì)路由候選轉(zhuǎn)發(fā)

圖1所示機(jī)會(huì)轉(zhuǎn)發(fā)成功的概率p為:

p=(1-(1-p1)/n)p2

從上式可知，增加候選節(jié)點(diǎn)數(shù)量將會(huì)使網(wǎng)絡(luò)轉(zhuǎn)發(fā)的成功概率增加，這與之前減少候選節(jié)點(diǎn)的方案矛盾，因此，候選節(jié)點(diǎn)的選擇對網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)效率有重要的影響。

本文通過對傳統(tǒng)的機(jī)會(huì)路由算法進(jìn)行研究與分析，并在傳統(tǒng)的機(jī)會(huì)路由算法基礎(chǔ)上提出一種動(dòng)態(tài)機(jī)會(huì)路由算法。算法通過預(yù)留候選節(jié)點(diǎn)的方式來提高轉(zhuǎn)發(fā)效率，而不是去構(gòu)造最優(yōu)機(jī)會(huì)轉(zhuǎn)發(fā)節(jié)點(diǎn)，通過降低選取候選節(jié)點(diǎn)網(wǎng)絡(luò)開銷的方式提高數(shù)據(jù)轉(zhuǎn)發(fā)效率，從而提高網(wǎng)絡(luò)的服務(wù)質(zhì)量。

2 基于預(yù)留的機(jī)會(huì)路由算法

為改善傳統(tǒng)機(jī)會(huì)路由候選節(jié)點(diǎn)網(wǎng)絡(luò)負(fù)載，本文提出基于預(yù)留的動(dòng)態(tài)路由算法(BRDOA)，通過減輕候選節(jié)點(diǎn)選擇和排序復(fù)雜度，實(shí)現(xiàn)提高網(wǎng)絡(luò)轉(zhuǎn)發(fā)效率和網(wǎng)絡(luò)QoS的目的。網(wǎng)絡(luò)節(jié)點(diǎn)需要學(xué)習(xí)節(jié)點(diǎn)的一些狀態(tài)信息，如候選節(jié)點(diǎn)變化率、時(shí)間限定t以及平均變化率的動(dòng)態(tài)調(diào)整。

2.1 網(wǎng)絡(luò)模型及算法設(shè)計(jì)

本文網(wǎng)絡(luò)模型使用無向圖G=(V,L)來表示。其中V表示網(wǎng)絡(luò)的節(jié)點(diǎn)集合，vi∈V(i=1，2，…，N)表示網(wǎng)絡(luò)中的任意節(jié)點(diǎn)，N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)；L表示無線Mesh網(wǎng)絡(luò)中的鏈路集合，l(i，j)∈L表示vi到vj的任意鏈路。

網(wǎng)絡(luò)轉(zhuǎn)發(fā)節(jié)點(diǎn)需要維護(hù)一個(gè)時(shí)間段t內(nèi)的候選節(jié)點(diǎn)信息，并計(jì)算出候選節(jié)點(diǎn)在這個(gè)時(shí)間段內(nèi)的變化率，即:

αi=Δfi/fi, i=1，2，…，N

其中，fi表示第i次轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)候選節(jié)點(diǎn)數(shù)，Δfi表示第i次轉(zhuǎn)發(fā)時(shí)相對上一次轉(zhuǎn)發(fā)的變化節(jié)點(diǎn)數(shù)，αi則表示第i次轉(zhuǎn)發(fā)候選節(jié)點(diǎn)的變化率，通過αi計(jì)算出時(shí)間t內(nèi)候選節(jié)點(diǎn)的平均變化率，即β為：

β=(∑αx)/(j-i), x=i，i+1，…，j

通過平均變化率選出候選預(yù)留集合，在預(yù)留集合中節(jié)點(diǎn)的排序使用最近歷史排序數(shù)據(jù)即可。但是，由于隨著t設(shè)置的不同，變化率也有所不同，變化率過大，會(huì)導(dǎo)致預(yù)留候選集合數(shù)據(jù)過多，這樣不僅不能提高網(wǎng)絡(luò)資源利用率，還會(huì)導(dǎo)致歷史數(shù)據(jù)對傳輸?shù)挠绊懺龃蟆１疚囊氡恢T多領(lǐng)域應(yīng)用的帕累托法則來應(yīng)對以上問題[15]，即20%節(jié)點(diǎn)決定了網(wǎng)絡(luò)整體的轉(zhuǎn)發(fā)率，因此，設(shè)置β的最大上限βmax為:βmax=20%，如果β>20%，那么就讓節(jié)點(diǎn)自動(dòng)調(diào)整時(shí)間t，縮短時(shí)間t會(huì)使傳輸過程減少，節(jié)點(diǎn)變化率也會(huì)下降，從而達(dá)到控制β上限的目的。

算法描述如下：

1. initial t;

2. fi←Candidate i;

3. fi-1←Candidate i-1;

4. αi←(fi- fi-1)/ fi

5. β←(αi+αi+1+…+αj)/(j-i)

6. Pareto principle, βmax←0.2

7. if (β>βmax) reduce t and return 1.

8. Forward

BRDOA算法依據(jù)歷史轉(zhuǎn)發(fā)數(shù)據(jù)以及預(yù)留節(jié)點(diǎn)平均變化率來確定預(yù)留節(jié)點(diǎn)數(shù)量，在傳統(tǒng)機(jī)會(huì)路由算法的基礎(chǔ)上增加了候選節(jié)點(diǎn)預(yù)留機(jī)制，從而降低排序帶來的系統(tǒng)開銷。

2.2 路由度量選擇

節(jié)點(diǎn)在選擇候選節(jié)點(diǎn)時(shí)，由路由度量確定各候選節(jié)點(diǎn)的優(yōu)先級，選擇高效的路由度量方法有助于路由轉(zhuǎn)發(fā)速度的提升。ExOR采用的是EXT度量方式[16]，本文同樣采用EXT[17]度量方法，BRDOA主要是對候選節(jié)點(diǎn)進(jìn)行預(yù)約分配，對于任何的機(jī)會(huì)路由算法來說都要進(jìn)行這個(gè)過程，因此，BRDOA可以在現(xiàn)有許多機(jī)會(huì)路由算法和度量方式基礎(chǔ)上進(jìn)行引入來提高路由算法性能，本文在ExOR和EXT基礎(chǔ)上進(jìn)行改進(jìn)以實(shí)現(xiàn)BRDOA算法，通過仿真實(shí)驗(yàn)驗(yàn)證算法效率。

3 實(shí)驗(yàn)仿真

BRDOA是基于傳統(tǒng)機(jī)會(huì)路由算法提出的機(jī)會(huì)路由算法，它與ExOR和SOAR都是通過無線網(wǎng)絡(luò)的廣播特性實(shí)現(xiàn)路由轉(zhuǎn)發(fā)的，而且BRDOA與ExOR和SOAR一樣使用EXT度量方式，因此通過對比BRDOA與ExOR及SOAR的算法性能，來判斷BRDOA算法是否能夠提高網(wǎng)絡(luò)轉(zhuǎn)發(fā)效率。

算法使用仿真實(shí)驗(yàn)驗(yàn)證，使用的是NS2仿真軟件進(jìn)行仿真，為了能夠驗(yàn)證算法的轉(zhuǎn)發(fā)效率和網(wǎng)絡(luò)QoS特性，選取投遞率、端到端延遲和吞吐量作為檢驗(yàn)指標(biāo)，將BRDOA算法與SOAR、ExOR算法進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明BRDOA的成功投遞率、端到端時(shí)延和吞度量皆優(yōu)于SOAR和ExOR，BRDOA算法有效地提高了網(wǎng)絡(luò)轉(zhuǎn)發(fā)效率，對網(wǎng)絡(luò)QoS性能有所改進(jìn)。結(jié)果如圖2～圖4所示。

圖2 成功投遞率對比圖

圖4 吞吐量對比圖

4 結(jié)束語

無線Mesh網(wǎng)絡(luò)作為無線網(wǎng)絡(luò)的重要解決方案將被越來越多的單位和部門重視，機(jī)會(huì)路由為無線Mesh網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)奠定基礎(chǔ)，也同樣會(huì)被進(jìn)一步地開發(fā)，BRDOA作為一種基于預(yù)留模式的機(jī)會(huì)路由，可以提高無線Mesh網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)效率，改善無線Mesh網(wǎng)絡(luò)的QoS，采用EXT的度量方式，使路由性能更高，本文提出的算法BRDOA通過仿真實(shí)驗(yàn)驗(yàn)證，結(jié)合無線Mesh網(wǎng)絡(luò)具體情況，采用適當(dāng)?shù)膮?shù)設(shè)置，未來將會(huì)成為無線Mesh網(wǎng)絡(luò)的路由轉(zhuǎn)發(fā)的重要解決方案。但是，BRDOA算法也有其不足之處，算法不適用于網(wǎng)絡(luò)空閑的無線Mesh網(wǎng)絡(luò)中，網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)量較低情況下，候選節(jié)點(diǎn)集合過程對網(wǎng)絡(luò)開銷影響較小，不適用BRDOA算法。