一種適用于無線Mesh骨干網(wǎng)絡(luò)的負(fù)載均衡路由算法

彭琦 唐碧華 劉凱明 劉元安

北京郵電大學(xué) 電子工程學(xué)院 無線電與電磁兼容實(shí)驗(yàn)室 100876

一種適用于無線Mesh
骨干網(wǎng)絡(luò)的負(fù)載均衡路由算法

彭琦 唐碧華 劉凱明 劉元安

北京郵電大學(xué) 電子工程學(xué)院 無線電與電磁兼容實(shí)驗(yàn)室 100876

無線Mesh網(wǎng)絡(luò)（WMNs）以其靈活的配置和低成本的特性極大地?cái)U(kuò)展了傳統(tǒng)無線網(wǎng)絡(luò)的覆蓋范圍。路由算法作為無線Mesh網(wǎng)絡(luò)研究的一個(gè)核心，其設(shè)計(jì)的優(yōu)劣會(huì)給網(wǎng)絡(luò)的性能造成重要的影響。文章中提出了一種適用于無線Mesh骨干網(wǎng)絡(luò)的負(fù)載均衡路由算法，使網(wǎng)絡(luò)性能在吞吐量和時(shí)延方面得到了一定程度的提升。

1.引言

無線Mesh網(wǎng)絡(luò)（Wireless Mesh Networks，WMNs）作為一種高速率高容量多點(diǎn)對(duì)多點(diǎn)的分布式網(wǎng)絡(luò)以及解決“最后一公里”問題的可行方案，正逐漸受到越來越多人的關(guān)注[1]。WMNs能夠和其他網(wǎng)絡(luò)系統(tǒng)有效地融合，從而快捷、高效地?cái)U(kuò)展無線網(wǎng)絡(luò)的覆蓋范圍。其自組織、自配置和自愈的特性，以及對(duì)移動(dòng)用戶的有效管理和跟蹤機(jī)制，使之成為部署社區(qū)寬帶網(wǎng)絡(luò)、企業(yè)內(nèi)部網(wǎng)絡(luò)和城域網(wǎng)絡(luò)的理想選擇[2]。

WMNs可以提供典型的因特網(wǎng)接入場(chǎng)景，通過部署一個(gè)或多個(gè)網(wǎng)關(guān)節(jié)點(diǎn)可以實(shí)現(xiàn)WMNs中的節(jié)點(diǎn)與外部網(wǎng)絡(luò)的互聯(lián)。其骨干網(wǎng)中的節(jié)點(diǎn)大都是靜止的或者具有很小的移動(dòng)性。Yang等在文獻(xiàn)[3]中證明了先驗(yàn)式的逐跳路由協(xié)議最適合于此種類型的Mesh網(wǎng)絡(luò)，也最能夠滿足無線Mesh網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和業(yè)務(wù)模型。因此我們選用OLSR（optimized link state routing Protocol）[4]協(xié)議作為研究的基礎(chǔ)。

在本文中，我們根據(jù)IEEE802.11s WLAN Mesh網(wǎng)絡(luò)的特點(diǎn)，提出了一種基于OLSR路由協(xié)議的改進(jìn)算法，該算法分別在OLSR協(xié)議的多點(diǎn)中繼集合(MPR)選擇階段和路由維護(hù)階段進(jìn)行了改進(jìn)，首先通過修改MPR選擇策略，使得MPR集的選擇結(jié)果可以動(dòng)態(tài)地變化，避免了網(wǎng)絡(luò)中“熱區(qū)”的出現(xiàn)，從而可以使數(shù)據(jù)分組更加均勻地在網(wǎng)絡(luò)中傳輸，實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡的效果；其次，在路由維護(hù)階段，改進(jìn)的算法將前一次的MPR計(jì)算結(jié)果作為備份存入拓?fù)浔碇腥ィ@樣當(dāng)網(wǎng)絡(luò)出現(xiàn)鏈路斷裂或節(jié)點(diǎn)擁塞時(shí)，就能夠快速地根據(jù)拓?fù)浔碇械男畔⒂?jì)算出備份路由，即避免了計(jì)算的浪費(fèi)，又提高網(wǎng)絡(luò)的健壯性。WLAN的Mesh組網(wǎng)方式，它適用于諸如辦公樓、家庭網(wǎng)絡(luò)等場(chǎng)景。其典型結(jié)構(gòu)可以分為三層。最低一層為“終端用戶層”，由用戶終端設(shè)備組成，包括手機(jī)、筆記本電腦、PDA等設(shè)備；“終端用戶層”之上是“無線Mesh層”，由無線Mesh接入點(diǎn)MAP (Mesh Access Point)和Mesh入口節(jié)點(diǎn)MPP(Mesh Portal Point)構(gòu)成，組成Mesh骨干網(wǎng)，終端用戶可以通過該層接入核心網(wǎng)絡(luò)，如因特網(wǎng)、PSTN等，終端用戶之間也可以通過該層進(jìn)行數(shù)據(jù)交互；WMN的第三層為“核心網(wǎng)絡(luò)層”，主要為終端與各種網(wǎng)絡(luò)互連等提供服務(wù)。一種基于IEEE802.11s的典型結(jié)構(gòu)如下圖所示：

2.研究背景

2.1 基于IEEE802.11s的WLAN Mesh

IEEE802.11s標(biāo)準(zhǔn)提供了一種

圖1 基于802.11s的Mesh網(wǎng)絡(luò)結(jié)構(gòu)

其中的MPP（Mesh Portal Point）作為網(wǎng)關(guān)節(jié)點(diǎn)，網(wǎng)絡(luò)中的節(jié)點(diǎn)通過MPP連接到其他網(wǎng)絡(luò)；MP（Mesh Point）作為第二層路由器，它決定了數(shù)據(jù)包在Mesh骨干網(wǎng)中的轉(zhuǎn)發(fā)；MAP（Mesh Access Point）則提供了傳統(tǒng)用戶節(jié)點(diǎn)的接口。

2.2 OLSR協(xié)議簡(jiǎn)介

OLSR—優(yōu)化鏈路狀態(tài)路由算法,是一種專門為無線分布式網(wǎng)絡(luò)所設(shè)計(jì)的表驅(qū)動(dòng)路由算法，它的設(shè)計(jì)充分的考慮了無線網(wǎng)絡(luò)對(duì)于表驅(qū)動(dòng)路由協(xié)議的需求，很好地解決了傳統(tǒng)表驅(qū)動(dòng)路由協(xié)議和按需驅(qū)動(dòng)路由協(xié)議開銷較大的問題。OLSR中的節(jié)點(diǎn)定期向網(wǎng)絡(luò)中廣播包含該節(jié)點(diǎn)周圍局部拓?fù)湫畔⒌耐負(fù)淇刂品纸M，通過這樣的分布式操作過程，每個(gè)節(jié)點(diǎn)都能夠根據(jù)其接收到的局部拓?fù)湫畔?gòu)造出全局子網(wǎng)拓?fù)洌瑥亩M(jìn)行路由路徑的計(jì)算。整個(gè)OLSR算法的核心可以劃分MPR選擇、拓?fù)浔淼挠?jì)算和更新以及路由的計(jì)算和維護(hù)三個(gè)部分。

OLSR協(xié)議采用了多點(diǎn)中繼技術(shù)（Multipoint Relaying Technique）[5]作為其構(gòu)建的基礎(chǔ)，只有被選為MPR的節(jié)點(diǎn)才向全網(wǎng)廣播信息。MPR節(jié)點(diǎn)的選取必須滿足條件：如果一個(gè)節(jié)點(diǎn)選擇了其部分(也可以是全部)一跳鄰居作為它的MPR節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)通過這些MPR節(jié)點(diǎn)必須能夠到達(dá)它所有的兩跳鄰居，即MPR節(jié)點(diǎn)提供對(duì)所有兩跳鄰居的連通性。OLSR中MPR的核心思想就是在某一時(shí)刻盡量使用信道狀態(tài)較好的節(jié)點(diǎn)來搭建路由。

3.基于OLSR協(xié)議的改進(jìn)方案

3.1 EOLSR的路由建立過程

OLSR協(xié)議中MPR選擇機(jī)制通常采用基于貪婪策略的啟發(fā)式算法，這種方法在傳統(tǒng)的Ad-Hoc網(wǎng)絡(luò)中能夠取得令人滿意的效果，但是在無線Mesh骨干網(wǎng)絡(luò)中，節(jié)點(diǎn)通常具有較小的移動(dòng)性，網(wǎng)絡(luò)拓?fù)湟不竟潭ǎ@樣在網(wǎng)絡(luò)中用同樣的算法進(jìn)行多次MPR集合選擇的結(jié)果基本上是固定的，據(jù)此形成的網(wǎng)絡(luò)拓?fù)淇蚣芤矝]有變化。這樣就造成了兩方面的問題，一方面是網(wǎng)絡(luò)資源的嚴(yán)重浪費(fèi)，因?yàn)楦鶕?jù)OLSR協(xié)議的規(guī)定，數(shù)據(jù)包只會(huì)通過MPR節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，這樣就會(huì)導(dǎo)致無線Mesh網(wǎng)絡(luò)中其他大量節(jié)點(diǎn)閑置；另一方面，當(dāng)網(wǎng)絡(luò)負(fù)載增加時(shí)，MPR節(jié)點(diǎn)的負(fù)擔(dān)加重，很容易形成網(wǎng)絡(luò)中的“熱區(qū)”，造成網(wǎng)絡(luò)瓶頸，從而影響整個(gè)網(wǎng)絡(luò)的性能。針對(duì)上述問題，我們提出了一種改進(jìn)型的路由算法EOLSR(Enhanced OLSR)，該算法修改了OLSR協(xié)議中的MPR選擇策略，并引入了備份路由機(jī)制，在選擇MPR集時(shí)，除了考慮到其對(duì)于兩跳鄰居的連接性外，還要考慮節(jié)點(diǎn)當(dāng)選為MPR的概率，并在拓?fù)浔碇杏涗汳PR的改變，當(dāng)MPR選擇發(fā)生變化時(shí)，先前的MPR路徑就作為備份存入拓?fù)浔碇校⒃诰W(wǎng)絡(luò)發(fā)生擁塞時(shí)通過本地計(jì)算快速得到備份路由，從而緩解主路徑的負(fù)擔(dān)。

為了表征節(jié)點(diǎn)當(dāng)選為MPR的優(yōu)先級(jí)并實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡，我們?cè)诠?jié)點(diǎn)的鄰居表中分別加入三個(gè)參數(shù)，一個(gè)MPR概率參數(shù)α、一個(gè)MPR標(biāo)識(shí)參數(shù)β和一個(gè)連通度參數(shù)γ。其中α參數(shù)是一個(gè) 形式的變量，分母M是一個(gè)累加計(jì)數(shù)，表示網(wǎng)絡(luò)中一共進(jìn)行MPR計(jì)算的次數(shù)，每進(jìn)行一次MPR計(jì)算，M的值就加1。N表示該節(jié)點(diǎn)當(dāng)選為MPR的次數(shù)，初始化為0，該節(jié)點(diǎn)每當(dāng)選一次MPR，N的值加1，反之則不變；參數(shù)β是一個(gè)標(biāo)志位，用來表示此節(jié)點(diǎn)在上一次計(jì)算中是否當(dāng)選為MPR節(jié)點(diǎn)，如果是則置1，反之置0。連通度參數(shù)γ表示該鄰居可以連接到的兩跳鄰居節(jié)點(diǎn)數(shù)目，即該鄰居節(jié)點(diǎn)對(duì)于兩跳鄰居的連通性。修改后的鄰居表如下所示：

圖2 修改后的節(jié)點(diǎn)鄰居表

通過鄰居表中的參數(shù)，我們可以在選擇MPR集合時(shí)，計(jì)算一個(gè)節(jié)點(diǎn)的MPR優(yōu)先級(jí)參數(shù)D(y)，參數(shù)D(y)越大表示優(yōu)先級(jí)越高。D(y)的計(jì)算如式（1）所示：

因?yàn)镸PR集的選擇是一個(gè)NP完全的問題，所以MPR集的選擇并不需要追求最優(yōu)化，但是為了達(dá)到更好的效果，MPR集合一定要足夠小。用公式（1）進(jìn)行計(jì)算時(shí)，如果兩個(gè)節(jié)點(diǎn)在上一次計(jì)算中均未當(dāng)選為MPR節(jié)點(diǎn)，即β為0，則只比較它們的連通度參數(shù)γ，待選節(jié)點(diǎn)的連通度越大，最終得到的MPR集合就會(huì)相應(yīng)的越小。若β不為0，則在考慮連通度的同時(shí)，還需要考慮節(jié)點(diǎn)當(dāng)選為MPR的概率，從而選擇合適的節(jié)點(diǎn)。計(jì)算出的優(yōu)先級(jí)參數(shù)D(y)通過HELLO信息傳遞給所有的鄰居節(jié)點(diǎn)，這樣鄰居節(jié)點(diǎn)在進(jìn)行MPR集合選擇的時(shí)候就可以根據(jù)此參數(shù)來選擇合適的MPR節(jié)點(diǎn)。

為了使結(jié)果更加準(zhǔn)確，進(jìn)一步提高網(wǎng)絡(luò)的性能。我們?cè)谟?jì)算的同時(shí)考慮到節(jié)點(diǎn)的當(dāng)前負(fù)載情況，如果節(jié)點(diǎn)當(dāng)前負(fù)載大于某一預(yù)設(shè)值時(shí)，就不再選用該節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，即將HELLO信息中的Willingness字段設(shè)置為WILL_NEVER，表示該節(jié)點(diǎn)不會(huì)被選為MPR節(jié)點(diǎn)，這樣做能有效地避開網(wǎng)絡(luò)中的一些負(fù)載過高的節(jié)點(diǎn)，從而提高網(wǎng)絡(luò)的性能。

這樣，我們可以將MPR選擇的流程形式化描述如下：

Algorithm: MPR_selection (x,N, N2)

Input: X: An arbitrary node

N1: Symmetric 1-hop neighbors of X N2: 2-hop neighbors of X with only symmetric neighbors in N1

Output: MPR: MPR set of node X

1 Begin

2 Start with an empty MPR set

3 Add to MPR the nodes of N1 that are the only ones able to reach a node in N2

4 Exclude the covered nodes by the last step from N2

5 Delete the nodes whose loadis larger than a given value

6 While N2 is not empty

{

7 select the node of N1 that has the highest D(y) which is calculated from formula (1)mentioned above. At the same time,increase the value of N and M by 1 and setβ as 1

8 Add to MPR the selected node

9 Exclude the covered nodes by the selected node from N2

}

10 End

3.2 EOLSR的路由維護(hù)過程

經(jīng)過上面對(duì)MPR選擇策略的修改，我們可以使MPR集合的選擇在Mesh骨干網(wǎng)絡(luò)中的節(jié)點(diǎn)間動(dòng)態(tài)地變化，為了避免計(jì)算浪費(fèi)，同時(shí)也為了提高網(wǎng)絡(luò)的健壯性，在一次新的MPR選擇過程結(jié)束后，如果一個(gè)原來在MPR集合中的節(jié)點(diǎn)在此次計(jì)算中沒有當(dāng)選，即，且此節(jié)點(diǎn)對(duì)于兩跳鄰居的連通度γ沒有發(fā)生明顯地變化，即（δ表示最大誤差），則通過這個(gè)節(jié)點(diǎn)的路由可以作為備份路由，存入拓?fù)浔碇小２⑼ㄟ^TC（Topology Control）拓?fù)淇刂菩畔V播出去，為了區(qū)分主路徑和備份路徑，我們?cè)赥C信息中添加了一個(gè)Flag字段，當(dāng)一個(gè)中間節(jié)點(diǎn)收到TC信息后，就將TC信息中的新當(dāng)選MPR作為主路徑，原MPR作為備份存入到拓?fù)浔碇小?/p>

當(dāng)網(wǎng)絡(luò)中的主路徑斷裂或節(jié)點(diǎn)發(fā)生擁塞的時(shí)候，以及相鄰節(jié)點(diǎn)的丟失或重建和接口信息發(fā)生變化導(dǎo)致需要重新計(jì)算路由的時(shí)候，我們就可以使用存儲(chǔ)在拓?fù)浔碇械膫浞菪畔⑼ㄟ^本地計(jì)算快速地計(jì)算出備份路由，從而保證網(wǎng)絡(luò)發(fā)送信息的通暢。計(jì)算備份路由的過程按照下面的流程進(jìn)行：

首先，從一跳鄰居開始計(jì)算，將拓?fù)浔砝镒鳛閭浞莸腗PR節(jié)點(diǎn)存入路由表中去，目的地址和下一跳地址都是這些MPR節(jié)點(diǎn)；其次，在路由表中記錄距離源節(jié)點(diǎn)為h=h+1跳的目標(biāo)節(jié)點(diǎn)的路由項(xiàng)。以下的算法從距離為1跳開始執(zhí)行，每次跳數(shù)增加1，如果在路由計(jì)算中沒有發(fā)現(xiàn)新的路由，那么該算法就停止：對(duì)于拓?fù)浔碇械囊恍腥绻鸐PR Selector節(jié)點(diǎn)的地址不等于路由表中的任何一個(gè)目的節(jié)點(diǎn)地址，并且，TC信息發(fā)送節(jié)點(diǎn)地址等于路由表中的目的節(jié)點(diǎn)地址而且跳數(shù)為h，那么就在路由表中生成一條新的路由，目的節(jié)點(diǎn)地址=MPR Selector節(jié)點(diǎn)地址，下一跳節(jié)點(diǎn)地址=所對(duì)應(yīng)h跳路由的下一跳節(jié)點(diǎn)地址，最后，計(jì)算完成，將計(jì)算出的備份路由存入路由表中，備份路由的計(jì)算過程如圖3所示。

圖3 備份路由的計(jì)算過程

經(jīng)過上述改進(jìn)，在節(jié)點(diǎn)相對(duì)固定的WMNs骨干網(wǎng)絡(luò)中，MPR集的選擇結(jié)果可以擴(kuò)展到更大的范圍，從而使分組業(yè)務(wù)可以在全網(wǎng)范圍內(nèi)更加均衡地分布，網(wǎng)絡(luò)資源也可以得到更加充分地利用，避免了“熱區(qū)”的出現(xiàn)，在一定程度上實(shí)現(xiàn)了網(wǎng)絡(luò)負(fù)載均衡；備份路由機(jī)制的引入，既避免了計(jì)算的浪費(fèi)，又可以在網(wǎng)絡(luò)擁塞時(shí)緩解網(wǎng)絡(luò)負(fù)擔(dān)，從而提高了網(wǎng)絡(luò)的健壯性。

4.仿真分析

為了定量的分析改進(jìn)協(xié)議的性能，我們使用OPNET[6]對(duì)EOLSR進(jìn)行了建模和仿真，網(wǎng)絡(luò)拓?fù)洳捎昧朔謱咏Y(jié)構(gòu)，上層節(jié)點(diǎn)基本固定，下層節(jié)點(diǎn)具有一定的移動(dòng)性；在一個(gè)大小為1000*1000的網(wǎng)絡(luò)場(chǎng)景中，分布50個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)隨機(jī)的選擇自己的運(yùn)動(dòng)方向，運(yùn)動(dòng)速度為5m/s，隨著仿真時(shí)間的推移，分別使用10，20，30，40，50個(gè)通信源節(jié)點(diǎn)來發(fā)送數(shù)據(jù)，仿真使用了802.11 MAC協(xié)議，并采用了恒定比特率（CBR）的傳輸，每個(gè)數(shù)據(jù)包的大小為512字節(jié)。仿真中我們將本文中提出的改進(jìn)型協(xié)議EOLSR與原OLSR協(xié)議和按需源路由協(xié)議DSR分別在端到端平均時(shí)延和網(wǎng)絡(luò)吞吐量方面進(jìn)行了對(duì)比。仿真結(jié)果如下圖所示：

圖4 三種協(xié)議的端到端平均時(shí)延對(duì)比

圖5 三種協(xié)議的網(wǎng)絡(luò)吞吐量對(duì)比

圖4 和圖5分別顯示了三種不同協(xié)議的端到端時(shí)延和網(wǎng)絡(luò)吞吐量隨著網(wǎng)絡(luò)中業(yè)務(wù)量增大的變化趨勢(shì)。從圖中我們可以看出，改進(jìn)型的協(xié)議EOLSR在時(shí)延和吞吐量方面均取得了一定程度的改善，因?yàn)镋OLSR協(xié)議考慮到了全網(wǎng)范圍的負(fù)載均衡，因而能夠使負(fù)載在骨干網(wǎng)絡(luò)中更加均勻地分布，降低了碰撞和丟包的概率；而網(wǎng)絡(luò)一旦發(fā)生擁塞或鏈路斷裂，備份機(jī)制的引入又使得該協(xié)議又能夠快速地計(jì)算出備份路由傳輸數(shù)據(jù)，保證了數(shù)據(jù)傳輸?shù)倪B續(xù)性，這樣就減小了數(shù)據(jù)傳輸端到端傳輸?shù)臅r(shí)延，同時(shí)也提高了網(wǎng)絡(luò)吞吐量。

5.結(jié)論

本文在分析無線Mesh網(wǎng)絡(luò)特征的基礎(chǔ)上，提出了一種基于OLSR協(xié)議的改進(jìn)算法，該算法克服了原協(xié)議應(yīng)用在無線Mesh網(wǎng)絡(luò)中易形成“熱區(qū)”的問題，使網(wǎng)絡(luò)負(fù)載可以更加均衡地分布，充分地利用網(wǎng)絡(luò)資源；并在路由維護(hù)階段引入了備份機(jī)制，通過備份信息快速計(jì)算備份路由，提高網(wǎng)絡(luò)健壯性。仿真結(jié)果也表明了改進(jìn)的協(xié)議能夠有效地提高網(wǎng)絡(luò)的吞吐量并減低端到端平均時(shí)延。

[1] F.Akyildiz, Xudong Wang, Weilin Wang. Wireless mesh networks: a survey[J] Computer Networks 2005 5(47):445-487

[2]傲丹，方旭明.無線網(wǎng)格網(wǎng)關(guān)鍵技術(shù)及其應(yīng)用[J].電訊技術(shù).2005（2）：16-22

[3] Yang Yaling, Wang Jun. Design guidelines for routing metrics in multihop wireless networks[C] Proceedings of the 27th IEEE Communications Phoenix. USA,2008: 2288 - 2296

[4]T.Clausen, K.Jacquet, A.Laouiti,Optimized Link State Routing Protocol,IETF Internet RFC 3626

[5]Qayyum A, Viennot L, Laouiti A Multipoint Relaying: An efficient technique for flooding in mobile wireless networks[C]Proceedings of the 35th Annual Hawaii International Conference.Hawaii: IEEE,2001

[6]陳敏.OPNET網(wǎng)絡(luò)仿真[M].清華大學(xué)出版社.2004

10.3969/j.issn.1001-8972.2011.02.040

國家863計(jì)劃項(xiàng)目(2008AA01Z211)和國家自然科學(xué)基金(60802033,60873190)資助課題

彭琦(1987- ) 男，碩士，北京郵電大

學(xué)，主要研究方向是無線Mesh網(wǎng)絡(luò)的路由協(xié)議。

無線Mesh網(wǎng)絡(luò); 路由協(xié)議; 負(fù)載均衡