基于負(fù)載感知的網(wǎng)關(guān)選擇的低成本的WMNs路由

沈宇春, 劉曉霞

(1. 呼和浩特職業(yè)學(xué)院 計算機信息學(xué)院，內(nèi)蒙古 呼和浩特 010051;2. 四川水利職業(yè)技術(shù)學(xué)院 信息工程系,四川崇州 611231)

0 引 言

與多跳移動自組織網(wǎng)絡(luò)(Multi-hop Mobile Ad-hoc Network, MANET)不同，無線網(wǎng)狀網(wǎng)絡(luò) (Wireless Mesh Networks，WMNs)[1]具有相對靜止結(jié)構(gòu)和低移動特點，其是有線和無線網(wǎng)絡(luò)的結(jié)合體。具體而言，WMNs以無線Mesh路由(MRs)為主干網(wǎng)，以移動點為用戶終端。用戶通過MRs轉(zhuǎn)發(fā)消息，并利用網(wǎng)關(guān)(GWs)連通Internet。

在單一GWs的WMNs中，GW選擇問題變得非常簡單。確實，所有上行或下行流量均通過同一個GW連通Internet。因此，GW可能成為網(wǎng)絡(luò)的瓶頸[2]。為了消除此問題，引用多個GWs分擔(dān)負(fù)載，并提高網(wǎng)絡(luò)性能。然而，只單方面地提高GWs數(shù)量并不一定能增加WMNs的容量。事實上，網(wǎng)絡(luò)容量與網(wǎng)絡(luò)連通率、GWs位置更相關(guān)。信號干擾和GWs的擁塞情況對WMNs性能也有消極的影響。為了改善WMNs的網(wǎng)絡(luò)性能，研究人員采用了不同的方案策略[2-5]。

此外，WMNs的網(wǎng)絡(luò)性能也受路由策略的影響。不同的路由指標(biāo)，對路由有不同的影響。通常，良好的路由指標(biāo)應(yīng)不降低網(wǎng)絡(luò)穩(wěn)定性，同時，也隱含了Mesh網(wǎng)絡(luò)特性。

網(wǎng)絡(luò)穩(wěn)定是多數(shù)網(wǎng)絡(luò)的主要性能指標(biāo)。當(dāng)網(wǎng)絡(luò)不穩(wěn)定，重建路由的頻率就會增加。這個增加是由于多條鏈路質(zhì)量過低導(dǎo)致的，低質(zhì)量的鏈路會導(dǎo)致路由翻轉(zhuǎn)，最終降低網(wǎng)絡(luò)性能。確實，不穩(wěn)定(頻繁地路由翻轉(zhuǎn))可能會導(dǎo)致傳遞失序、高擾動、數(shù)據(jù)包丟失、高時延。

為此，提出基于路徑成本和概率-網(wǎng)關(guān)的WMNs路由PCPG。PCPG路由從路徑成本和網(wǎng)關(guān)兩個角度決策路由。首先，通過期望鏈路質(zhì)量、干擾率計算路徑成本，然后，再依據(jù)網(wǎng)關(guān)負(fù)載計算選擇網(wǎng)關(guān)的概率，進而構(gòu)建穩(wěn)定路由。實驗數(shù)據(jù)表明，提出的PCPG路由能夠有效地控制時延、并提高了吞吐量。

1 PCPG路由

考慮多跳WMNs，將節(jié)點分為兩類：MRs和GWs。MRs形成多跳無線主干網(wǎng)，完成用戶與Internet間的流量傳輸。為了將流量傳輸至Internet，流量需通過網(wǎng)關(guān)傳輸。每個MR裝備了多個無線接口，且每個接口上具有多個信道。假定MR的接口有多個不同的信道。

多跳WMNs由MRs和GWs構(gòu)成，MRs構(gòu)成主干網(wǎng)，且完成用戶與Internet間的流量傳輸，而GWs連通Internet。整個WMNs要看成圖G=(V,E)，其中V為節(jié)點集(MRs和GWs)，E為鏈路集。令ij表示兩個MRs(υi、υj)間的鏈路，且υi、υj∈V。

PCPG路由從路由成本角度選擇路由，并且路由成本包含了鏈路質(zhì)量、干擾以及網(wǎng)關(guān)信息，有利于路由的穩(wěn)定。

1.1 期望鏈路質(zhì)量

期望鏈路質(zhì)量(Expected Link Quality, ELQ)類似于ETX，但優(yōu)于ETX。ETX是基于正向鏈路與反向鏈路具有相同的數(shù)據(jù)傳遞率，然而，實際上，正向鏈路與反向鏈路的傳遞率并不相同[6]。為此，本文引用的ELQ只包含正向鏈路的傳遞率。

為了更好地理解正向、反向鏈路以及ETX的問題，用圖1進行舉例說明。圖1中的df、dr分別表示正、反鏈路的傳遞率。依據(jù)ETX的假設(shè)條件，正向鏈路A→B與反向鏈路B→A具有相同數(shù)據(jù)傳遞率。而實際上，通常是利用探測包ACKs估計、反向傳遞率，然而數(shù)據(jù)包尺寸遠(yuǎn)大于ACKs的尺寸。換而言之，探測包ACKs對低質(zhì)量鏈路具有更強的魯棒性。此外，由于反向鏈路dr只考慮了ACKs，它在估計鏈路質(zhì)量方面上的重要性遠(yuǎn)低于df。

圖1 正、反向鏈路質(zhì)量

因此，本文不再引用ETX估計鏈路質(zhì)量[7]，而是ELQ，其定義如下：

(1)

從式(1)可知，ELQ只考慮了正向鏈路的傳遞率。這有利用于快速測量鏈路質(zhì)量。

1.2 干擾率IR

數(shù)據(jù)傳輸不僅受到鏈路質(zhì)量的影響，同時，也受到同信道的干擾影響[8]。為此，引用干擾率(Interference Ratio, IR)。從節(jié)點S至節(jié)點R鏈路的IR可定義為：

(2)

其中PR(S)表示R接收的信號功率、N為背景噪聲，ψ表示干擾節(jié)點R的節(jié)點集。PR(k)表示干擾節(jié)點k的干擾功率。

而Pmax表示接收節(jié)點可容忍的最大干擾，定義如式(3)：

(3)

其中T是信號功率閾值。當(dāng)傳輸信號的SINR大于T，才認(rèn)為此成功傳輸此信號。

最后，利用ELQ和IR估計鏈路成本(Link Cost，LC)。信道i上的鏈路l的鏈路質(zhì)量LC可表示為[9]：

(4)

其中n表示共享同一信道i的一跳鄰居數(shù)。

1.3 路徑成本

接下來，計算路徑成本。由第r個MR至第g個GW的路徑pr→g的路徑成本 (Path Cost，PC)PCr→g：

(5)

式(5)的右邊有兩項信息，都是與鏈路質(zhì)量LC相關(guān)。若只用右邊第二項，則不能充分反映路徑質(zhì)量。

圖2 路徑成本示意圖

1.4 網(wǎng)關(guān)選擇

在WMNs中，數(shù)據(jù)流是通過網(wǎng)關(guān)GWs流入Internet。因此，網(wǎng)關(guān)傳輸數(shù)據(jù)時的穩(wěn)定性對整個數(shù)據(jù)流傳輸?shù)牧鲿承云鹬P(guān)鍵的作用[8]。為此，需要選擇最合適的GW。本文選擇基于概率策略去選擇GWs。

假定每個GW先廣播網(wǎng)關(guān)通告消息(Gateways Advertisement Messages, GWADV)。GWADV的消息格式如表1所示。

表1 GWADV格式

其中idM為消息的id，而idG為廣播GWADV的身份。Iface為接口，Load表示其負(fù)載。

(6)

其中ρ為控制參數(shù)，且ρ∈[0,1]。而I為布爾變量，如果網(wǎng)關(guān)g的負(fù)載最低，其值為1，否則為零。

(7)

其中G表示節(jié)點i連通的網(wǎng)關(guān)集。而g′為網(wǎng)關(guān)集內(nèi)的一個網(wǎng)關(guān)。hopg表示節(jié)點i離網(wǎng)關(guān)g的跳數(shù)。

為了更好地理解網(wǎng)關(guān)的選擇過程，用圖3示例說明[12]。如圖4所示，三個網(wǎng)關(guān)G1、G2、G3；三個中間MRs R1、R2、 R3；兩個源節(jié)點S1、S2。假定S1離G1、G2、G3的跳數(shù)分別為2、2、3。而S2離G1、G2、G3的跳數(shù)分別為5、3、2。

圖3 網(wǎng)關(guān)選擇示意圖

首先，每個網(wǎng)關(guān)周期地向MRs發(fā)送GWADV消息。一旦接收到GWADV消息，S1和S2就利用式(6)計算與之連通的網(wǎng)關(guān)的概率。即S1選擇G1、G2、G3的概率分別為0.37、0.37、0.25(如表2的第一行)。而S2選擇G1、G2、G3的概率分別為0.19、0.32、0.48(如表2的第二行)。

表2 S1選擇網(wǎng)關(guān)的概率

表3 S2選擇網(wǎng)關(guān)的概率

觀察到，S1和S2在所有時刻(t=0,t=3,t=5,t=6)并沒有選擇同一個網(wǎng)關(guān)。因此，源節(jié)點并沒有總是選擇最低負(fù)載網(wǎng)關(guān)。

2 系統(tǒng)仿真

2.1 仿真場景

利用NS-2仿真器建立仿真平臺，進而分析PCPG協(xié)議的性能[13]。在1000 m×1000 m區(qū)域內(nèi)部署18個節(jié)點，其中15個MRs、3個GWs，并且每個節(jié)點有4個接口。同時，引用基于802.11b的MAC層協(xié)議，數(shù)據(jù)傳輸率為11 Mbps。流量類型為CBR，尺寸為1000 bytes。每次實驗獨立仿真50次，取平均值作為最終實驗數(shù)據(jù)。

PCPG路由是通過路徑成本和基于概率的網(wǎng)關(guān)選擇策略發(fā)現(xiàn)路由。為了更好地分析PCPG路由性能，選擇基于ETX、NG、LG、IR的路由進行比較，且分別在仿真圖中標(biāo)記為ETX、NG、LG、IR?；贓TX路由是選擇具有最小ETX的路由傳輸數(shù)據(jù)，而基于IR路由是選擇最小IR路由傳輸數(shù)據(jù)?；贜G路由是選擇最短路徑傳輸數(shù)據(jù)，而基于LG路由是選擇具有最小LG的路徑傳輸數(shù)據(jù)。同時，選擇網(wǎng)絡(luò)吞吐量、平均端到端傳輸時延、平均數(shù)據(jù)包丟失率作為性能指標(biāo)。

2.2 仿真結(jié)果及分析

首先，分析數(shù)據(jù)傳輸時延，實驗數(shù)據(jù)如圖4所示。從圖4可知，提出的PCPG路由具有最低時延特性。原因在于：PCPG協(xié)議在選擇路由時，充分考慮了鏈路質(zhì)量， 同時也考慮了網(wǎng)關(guān)負(fù)載，這利用于穩(wěn)定路由。從圖4可知，當(dāng)數(shù)據(jù)率為1500kb/s時，PCPG路由的時延比基于ETX、NG、LG、IR路由時延分別降低了近52%、58%、46%、13%。

圖4 端到端傳輸時延隨數(shù)據(jù)率的變化曲線

基于NG和ETX路由是僅通過跳數(shù)、探測包的丟失率選擇路由，這不利用于選擇穩(wěn)定路由，加大了傳輸時延。而基于LG路由是只通過GW負(fù)載決策路由、而基于IR路由是通過干擾率決策路由，這種單一度量策略，可能會形成低干擾、高負(fù)載GW或者低負(fù)載、高干擾路由，這都不利于路由的連通性，也必然增加了傳輸時延。

接下來，分析PCPG路由的吞吐量，實驗數(shù)據(jù)如圖5所示。從圖5可知，相比于基于ETX、NG、LG、IR路由，PCPG路由具有最大的吞吐量，原因在于：PCPG所決策的路由較穩(wěn)定，并且在選擇網(wǎng)關(guān)，充分考慮了網(wǎng)關(guān)的負(fù)載，這利用于提高吞吐量。例如，當(dāng)數(shù)據(jù)率為3000 kb/s時, 與基于ETX、NG、LG、IR路由相比， 吞吐量分別下降近26%、13%、33%、10%。

最后，分析了數(shù)據(jù)包丟失率隨數(shù)據(jù)率的性能影響，實驗數(shù)據(jù)如圖6所示。從圖6可知，PCPG路由的數(shù)據(jù)包丟失率最低。當(dāng)數(shù)據(jù)率為2500kb/s時，PCPG路由時延分別比基于ETX、LG、NG、IR路由下降了25%、10%、35%、17%。此外，從圖7可知，數(shù)據(jù)包丟失率隨數(shù)據(jù)率的增加而上升，原因在于數(shù)據(jù)率的增加，加大網(wǎng)絡(luò)負(fù)載，降低了數(shù)據(jù)包丟失率。

圖6 數(shù)據(jù)包丟失率隨數(shù)據(jù)率的變化曲線

3 結(jié) 語

針對無線Mesh網(wǎng)絡(luò)WMNs的路由問題，提出基于路徑成本和概率-網(wǎng)關(guān)的WMNs路由PCPG。PCPG路由從期望鏈路質(zhì)量、干擾率以及網(wǎng)關(guān)負(fù)載方面決策路由，進而構(gòu)建穩(wěn)定、強健路由。實驗數(shù)據(jù)表明，與傳統(tǒng)的WMNs路由相比，提出的PCPG路由能夠有效地提高吞吐量，縮短傳輸時延。