基于“溫度”的無線Mesh網絡負載均衡路由協議研究

楊峰　楊艷華　彭杰　吳啟祥

摘要：為了解決無線Mesh網絡路由開銷過大和負載不均的問題，分析了無線Mesh網絡的網絡架構和業務特點，并提出了一種基于“溫度”的無線Mesh網絡負載均衡路由機制。在建立路由時為每個節點設置一個溫度數值，并依據該數值確定數據的路由方向，進而選擇負載較輕的備選路由節點，以確定最終的路徑，從而有效控制網絡中的路由開銷，在保障網絡負載均衡的同時提高了無線Mesh網絡的整體路由效率。

關鍵詞：無線Mesh網絡 溫度值 負載均衡 路由機制

1 無線Mesh網絡概述

無線Mesh網絡（WMN，Wireless Mesh Network）是一種新型的寬帶無線網絡架構，它不同于傳統的無線網絡，可以看成是無線局域網（WLAN，Wireless Local Area Network）和Ad Hoc網絡的融合[1]。無線Mesh網絡節點之間以完全對等的無線連接方式構成網狀網絡，這大大提高了網絡部署的延展性。

WMN的網絡架構如圖1所示，包括網狀網端口節點（MPP，Mesh Point with a Portal）、網狀網節點（MP，Mesh Point）、網狀網接入節點（MAP，Mesh Access Point）和用戶終端節點（STA，Station）。其中，MAP實現STA接入Mesh網絡的功能；MPP實現Mesh網絡與外部網絡的互通功能。

WMN與傳統無線網絡最大的區別是：WMN網絡中的節點相互作為其鄰居節點的路由器，通過節點轉發，可實現網絡內部節點之間和內部節點與外部網絡之間的通信。WMN網絡中的節點既可以作為數據轉發實體，又可以作為連接到其他有線網絡的橋接器。

對于用戶終端節點來說，WMN的骨干部分主要是為用戶提供穩定的無線接入功能，所以通常WMN的骨干Mesh節點是固定不動的，網絡架構以及數據路由方式與Ad Hoc網絡還是有所不同[2]。另外，用戶接入Mesh網絡主要的目的是通過網關節點接入Internet，故可以預計網絡的主要業務存在于各節點與網關節點之間[3]。由于WMN網絡的這些特點，因此如何為WMN中的業務選擇一條最佳的傳輸路由，將直接影響WMN的數據傳輸效率[4]。

2 研究現狀

由于WMN繼承了Ad Hoc的許多特性，因而適用于移動自組網的路由協議常被引入使用[5-7]。目前，主流的Ad Hoc路由協議是自組網按需距離矢量路由（AODV，Ad hoc On-demand Distance Vector Routing）協議，它是數據驅動的距離矢量協議。其特點是按需維護路由信息，該方法最大程度地減少了維護的路由信息數量，但由于在沒有路由時需要執行路由學習查找過程，增大了數據的傳輸時延以及網絡中尋路信息的數量。尤其是對于頻繁上下線的用戶來說，路由信息將頻繁改變，這大大增加了網絡的路由開銷，嚴重影響了網絡的整體性能。

此外，雖然無線Mesh網絡與Ad Hoc網絡的拓撲結構類似，但路由技術還是有本質區別[8]。文獻[9]首先給出一種分層的部署場景模型及相關假設，并在此基礎上利用混合整數線性規劃（MILP，Mixed Integer Linear Programming）方法對測量報告（MR，Measurement Report）部署問題進行形式化描述；然后提出一種基于網絡流的MR部署貪心算法NF Greedy，該算法以迭代的方式從MR候選位置集中選擇權重最大的節點進行相應的節點部署，通過一系列仿真實驗將NF Greedy算法與現有算法進行對比，實驗結果表明該算法與基于MILP的算法相比，雖然所部署的MR數量略多，但是能夠適用于較大規模的WMN。文獻[10]提出了一種針對無線Mesh網絡的具有公平性擁塞控制策略，與IEEE 802.11e EDCA相比，在有效緩解網絡擁塞的同時，可以保證高優先級業務與低優先級業務之間的公平性，使整個系統吞吐量提高了6.3%，防止了“餓死現象”的發生，并通過仿真證明了該算法的有效性。

由于Ad Hoc網絡路由技術的主要目標是為了適應網絡快速變化的拓撲結構，且設備的業務也受能量限制，因此重點關注路由的節能問題。而無線Mesh網絡拓撲相對穩定，大容量、高傳輸可靠性和低時延是路由設計的首要目標。

3 基于“溫度”的WMN負載均衡路由

機制

上述文獻通過不同方面對WMN的路由協議進行研究，以優化網絡性能。本文針對WMN的網絡架構和業務特點，提出了一種基于“溫度”值的無線網狀網負載均衡路由管理方法，可以有效減少網絡中的路由開銷，保障網絡路由的負載均衡，提高路由的建立效率。本文的主要思想來源于空調的制冷效果，空調制冷的特點如下：

（1）距離空調越近溫度就越低；反之，越遠的溫度就越高。

在無線網狀網中，終端接入的主要目的是接入Internet，可以預計網狀網網關節點（端口節點）的業務量將是最繁重的。距離端口節點近的Mesh節點由于要為其他節點提供轉發業務，因此業務量也較重；距離端口節點較遠的Mesh節點由于承擔的轉發業務較少，或者僅僅為終端提供接入功能，因此業務量較少。

（2）使用空調時，為了保持室內的制冷效果，通常將門窗密閉以防止冷氣擴散。

在無線網狀網中，路由的建立和維護的過程中會產生大量的路由開銷。如果不對這些開銷進行控制，擴散到外網，不僅浪費了網絡資源，而且會對外網產生一些不必要的干擾。因此，需要采用一種機制將域內的路由信息限制在本Mesh網絡內部。

基于以上兩個方面啟示，本文的路由機制步驟如下：

（1）網狀網端口節點廣播聲明消息

網狀網組網完成后，所述端口節點向網狀網內部周期廣播一個網狀網端口節點也稱為根節點的聲明消息（RANN，Root Announcement），聲明自己為端口節點。該聲明消息包含的內容如下：

◆源地址（產生RANN消息的節點地址）：MPP節點地址。

◆本節點地址：本節點的IP地址。

◆上一跳地址：這里初始值設置為MPP節點。

◆溫度值：網狀網節點的默認值是一個足夠大的正整數。當MPP節點產生RANN消息向外廣播時，將其溫度值修改為0。

◆跳數值TTL：該TTL值是為了防止RANN消息被無限轉發。RANN消息每走一跳，TTL值減1，當TTL值為0時，RANN消息停止轉發。根據網絡的規模設置一個合適的TTL值，如網絡的節點數為10，則TTL值為15基本可以滿足網絡中的所有節點都能接收到RANN消息。

（2）端口聲明消息處理

網狀網內的Mesh節點收到RANN消息后，根據溫度值判斷是否已經接收過該RANN消息，如果已經接收過，則丟棄該消息；否則，接收該消息。

節點收到RANN消息后提取其溫度值，與本節點的溫度值進行比較，當該溫度值不小于本節點的溫度值時，則丟棄該消息；否則，接收該消息。

接收該RANN消息，提取其源地址、上一跳地址、溫度值、TTL值。

建立本節點到上一跳節點的路由，將RANN消息中本節點地址加到本節點的路由表的上一跳地址。將該消息的溫度值加1，作為本節點的溫度值。

同時，向上一跳節點單播返回一個路由回復消息（RREP，Route Reply）。該RREP消息包含的內容如下：

◆源地址（產生該RREP消息的節點地址）：本節點地址。

◆上一跳地址：本節點地址。

◆下一跳地址：向本節點轉發RANN消息的節點地址，即RANN消息中的上一跳地址。

◆目的地址：產生RANN消息的節點地址，該路由回復消息RREP最終會轉發給節點MPP。

然后將RANN消息的源地址不變，上一跳地址更新為本節點的地址，溫度值更新為本節點的溫度值加1，TTL值減1，并向與本節點相連的節點轉發該RANN消息。

（3）路由回復消息RREP的處理

提取其下一跳地址，與本節點地址進行比較，如果一致，則接收該消息；否則，丟棄該消息。

節點接收該消息后，提取其上一跳地址，添加到本地路由表的下一跳地址，建立到發送該消息的節點的路由。如果本節點是MPP節點，則銷毀該消息；如果本節點不是MPP節點，則轉發該RREP消息，具體步驟如下：

◆將RREP消息的下一跳地址設置為本地路由表的上一跳地址。

◆將RREP消息的上一跳地址設置為本地節點的地址。

◆沿下一跳地址方向轉發該RREP消息。

（4）路由建立過程完成后，節點的路由表里就存儲了到端口節點的路由，同時保存了到溫度值較高且路由回復信息由其轉發的節點之間的路由。

（5）域內各節點向周圍一跳節點發送一個信標幀，包含自己的溫度值和IP地址。收到周圍節點發送來的信標幀后，獲取周圍節點的IP地址和溫度值以確定冷源的方向。

（6）Mesh節點收到數據包后，查看該數據包的目的地址是否為Mesh內部地址。如果不是，則將該數據包轉發給其周圍溫度值較低的節點，直到接收數據包的節點為端口節點，再由端口節點轉發到外網。

如果該數據包的目的地址是Mesh內部地址，首先查找本地路由表，若沒有到該目的地址的路由，則將該數據包轉發給其周圍溫度值較低的節點，當周圍有多個溫度值一樣的節點時，通過比對周圍溫度值較低節點的負載情況，選擇負載較輕的節點作為下一跳節點，以保障網絡的負載均衡。直到找到路由，將數據包送至目的地。

4 具體實施方式

下面將結合實例來說明本文的具體實施方式。

實例1：網內節點與網外節點之間的通信（節點MP8與節點X通信）（見圖2）

具體步驟如下：

（1）依據端口節點MPP的聲明信息及網絡內部節點對該消息的回復，以節點MPP為冷源的樹狀路由在網絡中建立，并為網內各Mesh節點分配了溫度值。

（2）節點之間進行溫度值的交互，確定冷源的方向。

（3）如果節點MP8有數據包要路由到節點X時，發現X不是Mesh內部節點，則沿著冷源的方向轉發路由請求信息到周圍溫度值低的節點。MP8轉發路由請求消息到MP7或MP9，由于MP9、MP6的溫度值與MP7一樣，因此MP7將轉發路由請求消息到MP3或MP2，然后轉發路由請求消息到MPP。

（4）對于步驟（3）中的溫度值相同的節點，通過比較其待發數據包的數量，選擇負載較輕的節點作為下一跳節點。具體來說，當節點MP8發現下一跳節點有多個選項時，發送待發送數據包查詢消息給待選的下一跳節點MP7和MP9，這兩個節點收到消息后，反饋待發送數據包信息給節點MP8，由節點MP8決定選擇哪個節點作為下一跳節點，這種通過比較路由節點負載情況以決定下一跳節點的機制，可有效保障網絡的負載均衡。

（5）當每個路由節點選定后，由MPP將路由請求消息轉發給與其相連的外網路由器，最終建立節點MP8與節點X之間的路由：MP8→MP7→MP3→MPP→X。

（6）節點MP8沿著建立好的路由發送數據到節點X。

通過這種方式，網內節點與網外節點可以迅速建立路由進行相互通信。對于終端用戶來說，通過無線Mesh網絡接入Internet是其最終目的。通過這種路由機制，可以使用戶快速接入網絡，提高入網體驗。

實例2：網內節點之間的通信（見圖3）

具體步驟如下：

（1）依據端口節點MPP的聲明信息及網絡內部節點對該消息的回復，以節點MPP為冷源的樹狀路由在網絡中建立，并為網內各Mesh節點分配了溫度值。

（2）如果節點MP8要發送數據給節點MP2，首先判斷MP2為網絡內部節點，然后檢查是否有到節點MP2的有效路由。

（3）如果沒有到節點MP2的有效路由，則節點MP8立即轉發路由請求信息到周圍溫度值低的節點MP7或MP9，具體選擇節點MP7還是節點MP9的方法與實例1中步驟（4）一致。

（4）重復步驟（2）和（3），建立一條MP8→

MP7→MP3→MPP→MP2的路由。

（5）節點MP8沿著建立好的路由發送數據到節點MP2。

通過這種方式，網內節點之間也可以迅速建立路由。由圖3可以看出，在節點MP8與節點MP2之間沒有建立最短路由，但是在實際組網過程中，網狀網節點數量不大。另外，由于作為終端用戶接入Mesh的主要目的是通過其接入Internet，所以這種網內節點之間的通信不是業務的主流。基于此，這種路由機制可以滿足用戶接入Internet和與Mesh內節點之間的通信需求。

5 結論

本文針對WMN的網絡架構和業務特點，并結合空調的制冷原理，提出了一種基于“溫度”的無線Mesh網絡路由機制，在建立路由時為每個節點設置一個溫度數值，使得網絡的尋路機制方向明確，尋路效率高。通過采用先應式機制，在數據發送之前建立樹狀路由，并且對數據包的目的節點進行判斷，如果數據包的目的節點為網外節點，則直接轉發給端口節點，以進一步減小接入時延。在路由建立過程中發送RANN消息時采用廣播方式，而其余時間采用單播消息進行路由控制。由于WMN的網絡特點，網絡擴展的概率較小，因此不需要頻繁地廣播RANN消息，可以明顯降低網絡的路由開銷，從而保障網絡的負載均衡以及提高網絡的路由效率。

參考文獻：

[1] 劉波，周丹. 無線Mesh網絡協議標準研究[J]. 信息技術與標準化， 2009（3）： 27-29.

[2] 張牧，嚴軍榮. 802.11s無線mesh網絡研究進展與挑戰[J]. 計算機工程與應用， 2010，46（22）： 75-79.

[3] 王東，邵春菊，劉佳. Mesh網絡關鍵技術及組網性能分析[A]. 2008年中國通信學會無線及移動通信委員會學術年會論文集[C]. 2008.

[4] 胡云. 面向Internet接入無線Mesh網絡性能分析及協議優化研究[D]. 合肥： 中國科學技術大學， 2011.

[5] 吳瑋. Ad Hoc網絡擁塞檢測與控制的研究[D]. 哈爾濱： 哈爾濱工業大學， 2011.

[6] 沈呈，陸一飛，夏勤，等. 基于節點區分和跨層設計的無線Mesh網路由協議[J]. 東南大學學報： 自然科學版， 2009，39（4）： 700-704.

[7] 王吉喆. 無線Mesh網可靠路由技術研究[D]. 哈爾濱： 哈爾濱工程大學， 2010.

[8] 王曉翔. 無線Mesh網絡路由技術研究[D]. 重慶： 重慶大學， 2012.

[9] 吳文甲，楊明，羅軍舟. 無線Mesh網絡中滿足帶寬需求的路由器部署方法[J]. 計算機學報， 2014，37（2）： 344-355.

[10] 朱翠濤，王俊. 無線Mesh網絡中基于公平性的擁塞控制[J]. 中南民族大學學報： 自然科學版， 2009，28（1）： 85-88.★