彭琦 唐碧華 劉凱明 劉元安

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

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

彭琦 唐碧華 劉凱明 劉元安

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

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

1.引言

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

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

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

2.研究背景

2.1 基于IEEE802.11s的WLAN Mesh

IEEE802.11s標準提供了一種

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

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

2.2 OLSR協(xié)議簡介

OLSR—優(yōu)化鏈路狀態(tài)路由算法,是一種專門為無線分布式網(wǎng)絡(luò)所設(shè)計的表驅(qū)動路由算法，它的設(shè)計充分的考慮了無線網(wǎng)絡(luò)對于表驅(qū)動路由協(xié)議的需求，很好地解決了傳統(tǒng)表驅(qū)動路由協(xié)議和按需驅(qū)動路由協(xié)議開銷較大的問題。OLSR中的節(jié)點定期向網(wǎng)絡(luò)中廣播包含該節(jié)點周圍局部拓撲信息的拓撲控制分組，通過這樣的分布式操作過程，每個節(jié)點都能夠根據(jù)其接收到的局部拓撲信息構(gòu)造出全局子網(wǎng)拓撲，從而進行路由路徑的計算。整個OLSR算法的核心可以劃分MPR選擇、拓撲表的計算和更新以及路由的計算和維護三個部分。

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

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

3.1 EOLSR的路由建立過程

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

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

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

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

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

為了使結(jié)果更加準確，進一步提高網(wǎng)絡(luò)的性能。我們在計算的同時考慮到節(jié)點的當前負載情況，如果節(jié)點當前負載大于某一預(yù)設(shè)值時，就不再選用該節(jié)點作為中繼節(jié)點，即將HELLO信息中的Willingness字段設(shè)置為WILL_NEVER，表示該節(jié)點不會被選為MPR節(jié)點，這樣做能有效地避開網(wǎng)絡(luò)中的一些負載過高的節(jié)點，從而提高網(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的路由維護過程

經(jīng)過上面對MPR選擇策略的修改，我們可以使MPR集合的選擇在Mesh骨干網(wǎng)絡(luò)中的節(jié)點間動態(tài)地變化，為了避免計算浪費，同時也為了提高網(wǎng)絡(luò)的健壯性，在一次新的MPR選擇過程結(jié)束后，如果一個原來在MPR集合中的節(jié)點在此次計算中沒有當選，即，且此節(jié)點對于兩跳鄰居的連通度γ沒有發(fā)生明顯地變化，即（δ表示最大誤差），則通過這個節(jié)點的路由可以作為備份路由，存入拓撲表中。并通過TC（Topology Control）拓撲控制信息廣播出去，為了區(qū)分主路徑和備份路徑，我們在TC信息中添加了一個Flag字段，當一個中間節(jié)點收到TC信息后，就將TC信息中的新當選MPR作為主路徑，原MPR作為備份存入到拓撲表中。

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

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

圖3 備份路由的計算過程

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

4.仿真分析

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

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

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

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

5.結(jié)論

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

[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計劃項目(2008AA01Z211)和國家自然科學(xué)基金(60802033,60873190)資助課題

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

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

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