無線Mesh網(wǎng)負載均衡技術(shù)

1、無線 Mesh 網(wǎng)負載均衡技術(shù)摘 要：介紹了基于無線 mesh 網(wǎng)的負載均衡技術(shù)的相 關(guān)研究。提出了合理控制信號功率，提高 WMN 頻率空間復 用率，有效控制無線鏈路間的干擾范圍，降低節(jié)點間同頻干 擾，以此來增加網(wǎng)絡(luò)容量、有效提高系統(tǒng)負載性能；詳細分 析了目前現(xiàn)有幾種常用負載均衡機制的差異， 指出無線 mesh 網(wǎng)負載均衡的發(fā)展趨勢和研究方向。?關(guān)鍵詞： WMN ；自適應(yīng)；負載均衡；負載均衡算法?中圖分類號： TP393.17 文獻標識碼： A 文章編號：1672-7800 (2011) 05-0147-02?1 WMN 負載均衡的設(shè)計背景與發(fā)展趨勢 ?1.1 WMN 負載均衡的設(shè)計背景 ?近

2、年來隨著無線寬帶技術(shù)的迅速發(fā)展，無線通信技術(shù) 被越來越廣泛地使用，無線通信節(jié)點迅速增加，在這種高業(yè) 務(wù)量環(huán)境下，如果網(wǎng)絡(luò)中某個節(jié)點發(fā)生擁塞，成為整個網(wǎng)絡(luò) 的瓶頸節(jié)點時， 人們就希望數(shù)據(jù)包能順利地 “繞過” 該節(jié)點， 平穩(wěn)地到達目的節(jié)點；同時還希望提高網(wǎng)絡(luò)資源利用率，避 免出現(xiàn)一部分資源被過度利用，而另一部分資源卻閑置在一 邊造成資源浪費，從而達到整個網(wǎng)絡(luò)的負載均衡，正是在這 種需求下，負載均衡受到越來越多地關(guān)注。 ?而 WMN 主要應(yīng)用于無線寬帶接入和大容量數(shù)據(jù)傳輸， 側(cè)重于提高整個網(wǎng)絡(luò)的高吞吐量，因此很容易出現(xiàn)單節(jié)點擁 塞現(xiàn)象，如何提高網(wǎng)絡(luò)傳輸容量自然就成為 WMN 主要的設(shè) 計目標。 ?1

3、.2 負載均衡發(fā)展趨勢 ?目前 WMN 組網(wǎng)協(xié)議設(shè)計的基本思路是： 根據(jù) WMN 的 結(jié)構(gòu)特性，硬件上利用新的無線電技術(shù)，提高頻譜空間復用 和多信道技術(shù)；算法上在參考( Mobile Ad hoc Network ， MANET)相關(guān)協(xié)議的同時，依據(jù)現(xiàn)有的有線網(wǎng)絡(luò)均衡思想， 再根據(jù) WMN 的特點優(yōu)化負載均衡算法，同時還要考慮網(wǎng)絡(luò) 拓撲結(jié)構(gòu)的變化、上層業(yè)務(wù)數(shù)據(jù)的速率變化以及節(jié)點能量的 變化等多個方面因素。 ?2 現(xiàn)有的負載均衡策略 ?為了實現(xiàn)無線 mesh 網(wǎng)的負載均衡， 目前通常采用的策 略是：提高硬件技術(shù)和改進算法。 ?2.1 硬件技術(shù)對負載均衡的支持 ?無線 mesh 網(wǎng)的傳輸， 采用的

4、是多跳技術(shù)， 節(jié)點與節(jié)點 間數(shù)據(jù)傳輸不可避免的會出現(xiàn)同頻干擾現(xiàn)象。為提高頻帶利 用率，硬件上采用新的物理層無線電技術(shù)，如：定向智能天 線、自適應(yīng)調(diào)制編碼、( Multiple Input Multiple Output ，MIMO ) (多輸入 / 多輸出)技術(shù)、可重配置無線電、感知無線電、軟 件無線電技術(shù)以及多信道系統(tǒng)功率智能控制等技術(shù)，降低節(jié) 點間同頻干擾，提高了空間頻率復用和網(wǎng)絡(luò)容量，且降低了 整體信號功率。 ?WMN 的優(yōu)勢在于：在不犧牲信道容量的情況下， 在 一些AP (Access Point)信號覆蓋不到、 信號很弱或者根本不 具有直接視距無線鏈路的用戶之間，通過移動終端多跳轉(zhuǎn)發(fā)

5、， 建立非視距連接，這樣可以有效提高信號覆蓋，擴展網(wǎng)絡(luò)范 圍。在此架構(gòu)下，無線鏈路間距更短、發(fā)射功率更小，節(jié)點 間干擾更少，因此頻率復用效率更高。并且距離較近的終端 節(jié)點可以直接通信，而無需占用 AP 的資源，減少網(wǎng)絡(luò)整體 的負擔，提高網(wǎng)絡(luò)的總?cè)萘俊??早期的功率控制研究大多是基于圖論的拓撲控制模型。 如果兩個節(jié)點之間的距離是在無線傳輸范圍內(nèi)，則兩個節(jié)點 就是鄰居節(jié)點，就可以建立一條邊。而傳輸范圍取決于信號 功率、路徑距離、以及接收靈敏度等因素，因此要在保持連 通性的前提下盡量減少節(jié)點的度數(shù)，而度數(shù)的減少也就意味 著節(jié)點間的干擾也小了；而最近的研究表明，基于圖論的拓 撲控制模型并不能完全刻畫節(jié)

6、點間的互相干擾問題，轉(zhuǎn)而采用基于 SINR（ Signal to Interference plus Noise Ratio ）信號與 干擾和噪聲比來進行功率控制，通過感知周邊節(jié)點的拓撲結(jié) 構(gòu)，采用自適應(yīng)算法智能控制單節(jié)點信號發(fā)射功率，動態(tài)調(diào) 整載波偵聽門限值，從而提高空間復用度。但是降低節(jié)點信 號功率的同時也可能帶來一些問題：比如可能造成數(shù)據(jù)包傳 輸率的下降， 此外由于信號覆蓋面降低， 傳輸?shù)奶鴶?shù)會增多， 造成時延增大，還會導致 AP 鄰近節(jié)點負載過重的問題，這 些都是今后研究中需要解決的課題。 ?2.2 基本的網(wǎng)絡(luò)負載均衡算法 ? 現(xiàn)有的負載均衡算法繼承了有線網(wǎng)絡(luò)的思想，主要包 括以下幾種

7、： ?（1）輪轉(zhuǎn)法。在節(jié)點信號覆蓋區(qū)內(nèi)的所有節(jié)點都具有 同等地位，對這些節(jié)點采用順序選擇，將收到的數(shù)據(jù)包輪流 發(fā)送給下一跳節(jié)點。因此可以很容易算出，每個節(jié)點被選中 概率是 1/N 。?（2）散列法。通過單映射不可逆 HASH 函數(shù)，以事先 定義的規(guī)則的映射方式， 將數(shù)據(jù)包發(fā)往下一跳。 在該算法中， 如何選擇HASH函數(shù)，對預防碰撞影響很大。？（3）最少連接法。紀錄當前所有活躍節(jié)點，將數(shù)據(jù)包 發(fā)給目前具有最少連接數(shù)的偏僻節(jié)點。 ？（ 4）最短時延法。記錄節(jié)點到下一跳節(jié)點的時延，將數(shù)據(jù)包分配給時延最短的節(jié)點？（5）權(quán)重輪循法。根據(jù)數(shù)據(jù)包的優(yōu)先級或者當前的負 載狀況來建立負載平衡多優(yōu)先級隊列，每個隊

8、列中的每個等 待發(fā)送的數(shù)據(jù)包都具有相同處理等級；在同一個隊列里的數(shù) 據(jù)包可以按照前面的輪轉(zhuǎn)法或者最少連接法進行均衡，而隊 列之間按照優(yōu)先級的先后順序進行均衡處理。在這里權(quán)重值 是基于每個節(jié)點傳輸能力的一個估計。該算法可以看作是對 其它算法的一個補充，一般不單獨使用。 ?（6）權(quán)重隨機法。此種均衡算法類似于加權(quán)法，不過 在傳輸數(shù)據(jù)包時是個隨機選擇的過程。 ?（7）隨機法。節(jié)點隊列里的數(shù)據(jù)包隨機傳輸給鄰居內(nèi) 的多個節(jié)點。 ?（8）動態(tài)反饋法。根據(jù)結(jié)點的實時負載情況，不斷調(diào) 整節(jié)點間數(shù)據(jù)包的傳輸比例來避免個別結(jié)點超載時，依然收 到大量數(shù)據(jù)包，造成丟包，從而提高系統(tǒng)整體吞吐率。2.3 基于無線 mes

9、h 網(wǎng)的負載均衡算法 ?2.3.1 預設(shè)參數(shù)機制 ?此類算法會預先設(shè)定好用于計算負載的相關(guān)參數(shù)和權(quán) 系數(shù)，當負載超過預先設(shè)定的閾值就執(zhí)行事先定義的均衡操 作，但是由于是參數(shù)是預先設(shè)定的，如參數(shù)設(shè)置不當，有可 能導致系統(tǒng)性能嚴重下降，而參數(shù)的設(shè)置既是關(guān)鍵點，也是 難點。目前已經(jīng)有人提出具有負載感知的自適應(yīng)算法，通過 不斷更新負載信息實現(xiàn)自主學習，并且自動進行參數(shù)的最優(yōu) 化，使網(wǎng)絡(luò)負載逐步實現(xiàn)均衡。 例如：LWR(Load Aware Routing) 算法在網(wǎng)絡(luò)負載較重時，中繼節(jié)點收到源節(jié)點發(fā)送來的 RREQ(Route Reques時就直接丟棄。這種丟包策略對減少無 效數(shù)據(jù)包的轉(zhuǎn)發(fā)，降低負載具

10、有十分重要的作用。但是該算 法只有在收集到足夠的負載信息的條件下才能做丟包決策， 否則，可能會使后續(xù)節(jié)點無法及時了解網(wǎng)絡(luò)狀態(tài)，導致網(wǎng)絡(luò) 出現(xiàn)“隱藏節(jié)點”和“偽斷裂”現(xiàn)象。 LSR(Load Sensitive on Demand Routing)算法則通過路由比較函數(shù)所得出的權(quán)值來 選定一條最佳的路由。 ?2.3.2 基于負載感知機制 ? 負載均衡是一個動態(tài)過程，因此有學者提出了基于流 的負載感知路由協(xié)議：鏈路上每個節(jié)點都參與負載信息的更 新過程。由于路由發(fā)現(xiàn)需要進行泛洪，路由更新需要負載參 數(shù)傳遞。泛洪可以獲得精確的網(wǎng)絡(luò)信息，但要消耗大量的網(wǎng) 絡(luò)資源，負載參數(shù)的頻繁傳遞會使整個網(wǎng)絡(luò)充斥著大量

11、的控 制包，造成網(wǎng)絡(luò)資源利用率降低。因此根據(jù)路由選擇和維護 發(fā)起點又分為源節(jié)點感知、中繼節(jié)點感知和目的節(jié)點感知路 由選擇。 ?(1)源節(jié)點感知路由選擇。 這類算法采用源節(jié)點發(fā)起路由 選擇和路由維護，中繼節(jié)點感知網(wǎng)絡(luò)狀態(tài)并把負載信息發(fā)送 給源節(jié)點。 ?AMR(Aggregated Multipath Routing) ，采用請求 / 響應(yīng)機制的按需路由算法，源節(jié)點采用類似于 DSR(DynamicSource Routing)泛洪方式來獲取網(wǎng)絡(luò)狀態(tài)信息并建立多路徑拓撲結(jié)構(gòu)。當網(wǎng)絡(luò)出現(xiàn)擁塞或者失效時，源節(jié)點通過修改路 由，來避開該鏈路。該算法由于采用網(wǎng)絡(luò)圖來保留路由狀態(tài) 信息，復雜度是 0(n?2

12、)，因此存儲復雜度偏大，而且路由 請求中存有大量冗余信息，過長的等待期以及路徑計算復雜 度大都是需要解決的問題。 ?MSR(Multi Path Source Routing)，基于啟發(fā)的、利用加權(quán)輪詢多路徑調(diào)度機制實現(xiàn)負載均衡。類似DSDV(Destination-Sequenced Distance Vector)， MSR也是通過源節(jié)點沿多條路徑周期性發(fā)送探測包，根據(jù)反饋信息計算各 路徑延時并求出權(quán)值，再把負載依據(jù)權(quán)值，分配給多條路 由。 ?DLAR(Dynamic Load Aware Routing),該算法避免采用MSR周期發(fā)送探測包的方式，改由中繼節(jié)點，周期性地將自身緩存中數(shù)據(jù)包

13、的數(shù)目作為負載信息發(fā)給鄰居節(jié)點，后續(xù)節(jié) 點據(jù)此參數(shù)來監(jiān)測負載狀態(tài)。如果出現(xiàn)擁塞現(xiàn)象，目的節(jié)點 通過廣播發(fā)送請求數(shù)據(jù)包(RREQ至源節(jié)點，尋找替代路由。為了減少廣播次數(shù)，后續(xù)的算法中出現(xiàn)了，由目的節(jié)點或者 擁塞節(jié)點后的中繼節(jié)點來進行路由維護和選擇。 ?(2)中繼節(jié)點及目的節(jié)點感知路由選擇。采用中繼或目的節(jié)點進行備用路由的選擇和維護，比采用源節(jié)點選擇路由具 有更好的靈活性和更高的可靠性。 ?LBAR(Load Balanced Ad Hoc Routing，) 從源節(jié)點到目的 節(jié)點鏈路上的結(jié)點參數(shù)都會周期性的傳送到目的節(jié)點。當鏈 路發(fā)生擁塞或者主路徑失效后，目的節(jié)點根據(jù)收集的所有可 能路徑的相關(guān)信

14、息選出最佳路徑作為備用路由。作為 ABR(Associativity Based Routing)的改進協(xié)議，LBAR 更能準確 細致的反應(yīng)網(wǎng)絡(luò)的環(huán)境特性。 ?DLLMR(Dynamic Load-aware Based Load-balancedRouting)，一種基于DSR的改進算法。源節(jié)點利用多條路由， 搜索剩余負載容量的節(jié)點來進行路由選擇和負載均衡。目的 節(jié)點向源節(jié)點發(fā)送 RREP( Route Reply)時，中繼節(jié)點根據(jù)分 組中的負載信息更新自己的路由表，同時廣播尋找更好的路 徑。 ?LLDR(Least Loaded Dynamic Routing Protocol，由源節(jié)點

15、來建立傳輸路徑，而路由維護由目的節(jié)點來完成，中繼節(jié)點 不發(fā)送探測包，而是采用DF(Dynamic Fragmen tation)機制：在分組中周期性捎帶負載信息，使后續(xù)節(jié)點能及時了解鏈路 上的負載狀況。當負載超過門限，目的節(jié)點會重新選擇一條 路由。 ?2.3.3 硬件與算法相結(jié)合的負載均衡機制 ?采用軟件與硬件相結(jié)合的方式，通過自適應(yīng)技術(shù)對負載進行實時監(jiān)測與控制，實現(xiàn)信號發(fā)射功率與傳輸性能的最優(yōu)化，由于充分利用了無線 mesh 網(wǎng)的結(jié)構(gòu)特性，使得這種思想具有重要的現(xiàn)實意義。 ?MRPLB (Multi Path Routing with Load Balancing) ，一種利 用報文粒度的流

16、量分布方法和負載均衡機制共同作用來實 現(xiàn)擁塞避免。該算法需要硬件支持來實現(xiàn)對信號發(fā)射功率的 實時監(jiān)測，利用智能控制技術(shù)把信號發(fā)射功率降低到一個合 理的水平，使節(jié)點間干擾更少，頻率復用率更高。 ?3 結(jié)束語 ?本文首先介紹了通過硬件合理控制信號發(fā)射功率來降 低節(jié)點間同頻干擾，提高頻帶復用率來均衡網(wǎng)絡(luò)資源；然后 分析和比較了當前提出的幾種負載均衡路由技術(shù)各自的優(yōu) 缺點。通過分析，筆者認為：目前路由選擇機制，已開始由 單純的源節(jié)點路由選擇向多節(jié)點共同參與路由選擇，這樣不 但提高了靈活性而且增強了網(wǎng)絡(luò)的健壯性；此外均衡算法也 陸續(xù)開始向軟、硬件相結(jié)合以及智能化方向發(fā)展，由于自適 應(yīng)算法具有自主優(yōu)化系統(tǒng)參數(shù)、自我學習能力、高度的靈活 性和對網(wǎng)絡(luò)負載的敏感性的特點，都將成為未來無線 mesh 網(wǎng)絡(luò)的重點研究方向之一。 ?參考文獻： ? 1 方旭明 .下一代無線因特網(wǎng)技術(shù)：無線 Mesh 網(wǎng)絡(luò) M .北京：人民郵電出版社， 2006.? 2 M.JOA-NG,I.U,A peer-to-peer zone-ba