基于負載均衡的多接口多信道分配算法研究

尹鳳杰，彭永倩

(遼寧大學 信息學院，遼寧 沈陽 110036)

0 引言

無線Mesh網絡是一種新型的多跳無線網絡，具有組網靈活、網絡覆蓋率高等優點.為充分利用正交信道，提高網絡吞吐量和帶寬利用率，信道分配已成為無線Mesh網絡中的研究熱點.根據802.11a和b/g的標準，分別有12個和3個不重疊的正交信道可供使用[1]，因此，對于一個接口來說，可以同時使用多個不重疊的信道.除此之外，還可讓一個節點配備多個接口，這就使得每個節點可同時使用多個互不重疊的正交信道，但節點間傳輸隊列過多，將存在信道間相互干擾與負載均衡問題.

在多接口多信道無線Mesh網絡中，信道數量可能多于節點接口數量.為了使網絡吞吐量達到最大，最佳的信道分配方式應該是在干擾可控范圍內允許有最大數量的并發傳輸存在，然而，這已經被證明是一個NP(Non-deterministic Polynomial)問題[2].同時，信道分配還可能會影響網絡的連通性[3]，目前主要是通過使用專用信道和同步信道的分配方式來解決這個問題.但是，同步信道分配需要保持時間同步，當傳錯率較高且重傳機會有限時，將會導致整體性能降低[4].

文獻[5]提出的BCMN/A協議用于簇內廣播，并且對來自簇的每個數據返回ACK(Acknowledge Characte)確認，以便共同優化生存時間和傳輸延遲，實驗結果表明，該協議可以將網絡的生存時間提高8%以上，并且將網絡延遲降低25%以上.文獻[6]根據無線Mesh網絡特點，提出一種基于AODV-MR的AODV-MRCR協議.該協議專門為網關流量保留一個信道列表，將網關流量和本地流量分開處理，因為網關流量具有較高的優先級，所以為它準備較多信道.然而對于本地流量，只保留一個固定信道，當本地流量較高時，這種方法效果并不理想.為了進一步提高效率，急需一種能夠均衡網關流量和本地流量的解決方案，因此，本文提出一種基于負載均衡的多接口多信道分配算法DACA-LB，該算法通過選擇干擾最小信道，動態接口調整來平衡負載，有效降低了平均排隊延遲，實現負載均衡和網絡吞吐量最大化.

1 DACA-LB框架結構

在無線Mesh網絡中影響多接口利用率的一個重要因素是切換問題[7]，頻繁切換會導致信道利用率降低，而靜態配置會因流量動態變化導致性能欠佳[8]，本文綜合考慮二者的平衡問題，采用動靜結合的方式設計DACA-LB框架結構，如圖1所示，該結構主要由信道分配、靜態接口設置以及動態自適應接口調整3部分組成，其中每個接口都可以在接收模式與發送模式之間轉換.

圖1 DACA-LB算法框架圖

為確保網絡連通性[9]，設置2個不同的接口總是分別處在接收模式和發送模式，本文統稱為靜態接口，它們將使用專用信道進行傳輸，若傳輸隊列變化大于專用信道所能承受的范圍，則需要從預留出來的自適應信道中選擇一條受干擾最小的信道進行傳輸.在選擇工作信道之后，信道信息將廣播給所有鄰居節點[10].鄰居節點保存該信息記錄，并根據該條信息向鄰居節點發送數據包.其中，專用信道是不會改變的，以確保鄰居節點之間的連通性.對于信道分配，須遵循2個原則：1)同一節點的接口應盡量選擇不同信道，以避免互相干擾；2)在理想情況下，優先選擇一個受干擾最小的信道[11].

除靜態接口外的其他接口，本文統稱為動態自適應接口，其在默認狀態下將全部處于發送模式.隨著時間的變化，當靜態接口負載達到一定閾值后，動態自適應接口將調整為接收模式或繼續保持發送模式，從而可以均衡接口之間的負載.

2 算法設計

2.1 干擾計算

本文采用的干擾模型如圖2所示，其中Rd、Rtx、Rcsin分別表示發射機和接收機之間的距離、傳輸范圍以及干擾范圍，一般情況下干擾范圍比傳輸范圍大，本文假設干擾范圍以外的并發傳輸對目標傳輸的影響是忽略不計的.

圖2 干擾模型

圖2所示為節點A向節點B發送數據包時，節點C會受到來自節點A的干擾，由于節點D處于節點B的干擾范圍內，因此，節點C和節點D應該避免和節點A同時發送，這樣就可以消除隱藏終端問題.節點E在節點A和節點B的干擾范圍之外，所以節點E和節點A可以同時傳輸，避免暴露終端的問題.通常，干擾范圍內的節點數量大于正交信道的數量，因此，在其干擾范圍內，可能找不到空閑信道.

2.2 信道分配

默認情況下，為靜態發送/接收接口設置專用傳輸信道，并為專用傳輸信道設置一個能夠承受的隊列數量動態變化范圍R∈[2r-1，2r+1](r為常數且r≥1)，當隊列的數量變化超出范圍R，則隊列將切換信道.本文用Numq來表示當前信道中的隊列數量，Numq越大，信道越繁忙，干擾可能就越多.當隊列離開信道時，信道負載變輕，Numq減1；當有隊列加入當前信道，則Numq加1.可以看出信道能夠承受的隊列數量動態變化范圍R的中值為2r，若Numq變化大于2r，則節點切換信道.因此，應根據動態需求，將r設置為一個合適的值來控制信道的切換頻率，用于避免隊列調整過于頻繁.

當一個節點需要切換到與其鄰居節點相同的信道時，應優先選擇使用次數最少的信道.本節在監聽各個接口無線網絡活動的基礎上計算信道的狀態，并通過公式(1)對信道的繁忙時間比P(ch)進行計算[12].

(1)

其中，tactive表示在時間T內信道ch的活動時間.

(2)

假設2個接口之間有n條傳輸信道，給各信道編號為chj(j=1，2，…，n)，且時間T內各個信道的活動時間用tactive(chj)表示，P(chj)則表示信道chj的繁忙時間比.N(chj)表示所有通過信道chj發送數據包的接口結合，且該集合內的所有接口都處于干擾源的干擾范圍內.結合圖2所示，假設節點B、C的某個接口均通過信道ch發送數據包，且2個節點均處在節點A的干擾范圍內，所以有N(ch)={B、C}.圖3給出了信道分配的完整過程，每個接口選擇干擾最小的信道chmin傳輸數據包.

圖3 信道分配流程圖

2.3 靜態接口

對于靜態接口，本文采用專用信道來降低發送節點與接收節點之間的協調復雜性，在確保網絡連通性的同時降低信道間的切換開銷.根據DACA-LB算法的框架結構，靜態接口應根據從鄰居節點得到的發送(或接收)接口信息來使用信道，在此過程中，確認發送/接收接口尤為關鍵，若默認的發送/接收接口處理的數據包多于其他接口，不僅導致其他接口的利用率降低，而且吞吐量也會隨著沖突率的上升而下降.

節點可以通過交換接口信息，向它們的鄰居節點發送其選擇的信道列表[15]，鄰居節點信息交換過程如圖4所示.通過與直接相連的鄰居節點交換接口信息，節點A首先收集單跳鄰居節點B至E的接口配置信息，節點B至E也會將收到的來自節點A的接口信息并轉發給其各自鄰居節點，使得節點A在獲得其兩跳鄰居節點F至I接口信息的同時，還可獲得三跳鄰居節點G至M接口信息，以此類推，獲得更多節點信息.

圖4 鄰居交換信息過程

2.4 自適應接口的調整

動態自適應接口，可用作發送或接收接口，以平衡所有接口間的負載.如果源節點存在大量隊列等待發送，則需要更多的自適應接口調整為發送接口，節點收集和聚合信息則需要更多的接收接口.本文通過監聽無線網絡的活動狀態，周期性地從各個節點中收集CPU利用率、內存利用率以及網絡利用率，并根據這些參數計算出接口的動態閾值，依據閾值的大小均衡接口負載.本文定義使用接口i傳輸數據時的最大負載為Loadmax，接口i在為隊列q服務時的平均負載值可用公式(3)求得.

(3)

其中，Dataq表示接口要傳輸的數據大小，ts、tr分別表示數據發送時刻和接收時刻.

根據節點收集到的信息可得到接口i使用信道ch傳輸數據時能夠承擔的最大負載利用率MaxU，可用公式(4)求得.

MaxU=Max(Cq，Mq，Nq)

(4)

其中，Cq、Mq、Nq分別表示CPU利用率、內存利用率和網絡利用率，規定三者取值為0～1之間.

由公式(3)和公式(4)可得接口i在為隊列q服務時能夠提供的最大負載Loadmax(i，q)，可通過公式(5)計算.

(5)

假設最多只能有n個隊列同時在接口i上工作，則可以通過公式(6)估計接口i傳輸數據包時的最大負載Loadmax.

(6)

同時假設接口i中正在運行的隊列有qk，qk+1，…，qn，根據公式(5)和公式(6)可以計算出下一時間段接口能夠承受的負載增量ΔLoad，其公式如下(7)所示.

(7)

根據公式(7)可以得出隊列qk+1的最大負載不能超過ΔLoad，則可以把ΔLoad看作一個閾值，如果Loadav(i，qn+1)>ΔLoad，就需要把一個動態的接口調整為接收模式或繼續保持發送模式，借此來緩解當前接口的流量負載，否則繼續使用當前接口.

2.5 DACA-LB算法的實現總體流程

DACA-LB算法的總體實現流程如圖5所示，若節點A向節點B發送數據，節點A中某一隊列進入默認發送接口后，將判斷隊列負載是否超過接口的閾值，若超過則任意選擇一個動態自適應接口傳輸此隊列(若為接收過程，則需要將接口調整為接收模式)；若沒有超過閾值，則繼續使用當前默認發送接口.其次，根據2.2節中提到的方法判斷當前隊列是否需要切換信道，若需切換，則選擇受干擾最小的信道；若無需切換，則保持當前信道即可，并根據最后的接收節點情況選擇適合的接口，完成傳輸任務.

圖5 DACA-LB協議整體流程圖

3 實驗及分析

本文通過在Linux環境下使用NS2-35評估所提DACA-LB算法的整體性能，在此次仿真實驗中除了增加MAC狀態統計模塊外，無需做其他修改，且當接口在進行信道切換時，該接口不能發送或接收任何數據包.IEEE802.11a標準規定了12個可使用的不重疊信道，且在理論上它們之間不存在干擾，然而，由于技術的限制，在相鄰不重疊信道上工作的接口也可能相互干擾[16]，因此本文將正交信道的數量設置為5到12.隨著仿真時間的增加，節點間的負載也在不斷增加，導致信道分配狀態不穩定，為了更好地觀察各種算法的性能比較，將仿真時間設置為400 s.本實驗中接口數設置為2～5之間，小于可用的正交信道數目，其中，所有接口的傳輸距離為250 m，載波監聽范圍為500 m，其他仿真參數設置如表1所示.

表1 仿真參數設置

本文結合AODV路由協議從信道數量和接口數量方面對DACA-LB網絡吞吐量性能產生的影響進行實驗分析，并與現有協議進行對比.分析圖6的實驗結果可知，在接口數量不變的情況下，信道數量越多，其吞吐量增加越明顯，但其增長速度逐漸放緩，原因是鏈路層協議可以很好地利用信道資源，但是由于接口數量的限制，導致可使用的信道數量有限，所以增長速度變得緩慢.除此之外，信道數量增多將會產生更多的信道切換，從而導致更高的網絡開銷.對于接口數量而言，當信道數量不變，隨著接口數量的增加，其吞吐量越高.由此可見，增加接口和信道數量均可提高網絡吞吐量.但是，若信道數量足夠多，卻沒有與之相匹配的接口數量，則不能提高吞吐量，反之亦然.

圖6 具有不同信道數和接口數的吞吐量變化

本文通過將DACA-LB算法與不同路由協議相結合，對其性能進行評估，分別是：a)DACA-LB+AODV[17]；b)DACA-LB+WCETT[18]；c)AODV-MR，1種結合鏈路和路由協議的跨層解決方案.本次模擬實驗設置在1 000×1 000 m2的區域中隨機分布100個節點，所有節點均配備4個接口，且12個正交信道全部可用.

在所有節點中統一選擇源/目的對，并將目的對的數量設置為50～500，以顯示不同流量負載下的性能.分析圖7的實驗結果可知，DACA-LB+AODV與DACA-LB+WCETT的性能表現十分接近，AODV-MR性能表現最差.這是因為AODV-MR算法只是進行簡單的信道分配，沒有考慮負載平衡問題，所以其性能較差.其次，可知DACA-LB+WECTT組合的吞吐量并沒有明顯高于DACA-LB+AODV組合的吞吐量，這是因為在WCETT路由協議中并沒有考慮信道分布和信道切換的開銷，除此之外，隨著網絡負載增加到一定數值，大多數信道和接口已經被利用，二者的吞吐量趨于一致.

圖7 不同隨機源/目的對情況下的吞吐量變化

任意選擇網絡中5個節點，將其設置為具有比其他節點較高流量負載的網關，網絡中的其他節點將隨機選擇附近的網關接入互聯網，圖8為3種算法隨著并發流數目的增加，網絡吞吐量變化的趨勢圖.分析可知，3種算法的吞吐量變化趨勢與圖7結果相似.由此得出結論，場景DACA-LB+AODV和DACA-LB+WCETT的性能相近，并且二者性能均優于AODV-MR.當并發流數量較少時，三者性能相似，隨著流量的增加，DACA-LB 的負載均衡可以大幅度地提高整體性能.圖7與圖8的2種仿真實驗結果表明，本文所提DACA-LB算法能夠動態平衡流量負載，獲得較高的吞吐量，且能與現有的路由協議實現較好地結合.

圖8 5個網關情況下的吞吐量變化

除此之外，本文還通過網絡吞吐量和平均丟包率2種性能指標，將DACA-LB算法與ELIA和LBIA-OCA信道分配算法進行對比分析[19]，以驗證所提算法的有效性.ELIA和LBIA-OCA算法均是通過選擇受干擾最小的信道進行傳輸，同時考慮節點接口間的負載均衡，但執行方式與本文所提算法不同.在此次對比實驗中，將并發流數目范圍設置為4～22，報文發送速率為200 Kbps.隨著流量的增加，網絡吞吐量的變化如圖9所示.

圖9 不同信道分配算法下的吞吐量變化

分析圖9的實驗結果可知，性能排序為：DACA-LB最優，ELIA次之，LBIA-OCA最差.在3種算法中，網絡吞吐量隨著流量的增加幾乎呈線性上升趨勢，但上升速度逐漸變緩，其中，DACA-LB和ELIA的性能均明顯優于LBIA-OCA算法.當網絡負載較輕，3種算法產生的網絡吞吐量幾乎相同，但在LBIA-OCA算法中，隨著流量的增加，為相鄰隊列分配相同信道的可能性隨之增加，進而數據包在傳輸之前必須在緩沖隊列中等待較長時間，且可能發生更多回收，這就導致較差的網絡性能.由于DACA-LB算法考慮了節點接口間的負載均衡，使得網絡并沒有隨著負載的增加陷入瓶頸，而是繼續保持上升趨勢.

分析圖9和圖10的實驗結果可知，3種算法的平均丟包率與網絡吞吐量是成反比的，即丟包越多，網絡吞吐量越低.同時，隨著并發流的增加，DACA-LB算法的丟包率明顯低于其他2種算法，表現出更佳的性能，這主要得益于DACA-LB算法充分利用信道和接口資源，降低了丟包率.

圖10 不同信道分配算法下的平均丟包率變化

4 結束語

本文提出一種基于負載均衡的多接口多信道分配算法DACA-LB，該算法通過平衡負載來使網絡吞吐量最大化，從而提高整體性能.通過動態自適應的接口分配方式，在保證用戶需求的基礎上，提高接口利用率，有效減少請求響應時間；該算法部署在所有節點上，以分布式方式控制數據傳輸，且上行鏈路與下行鏈路數據均由高負載水平匯聚節點的無線接口來接收和發送.仿真結果表明，DACA-LB算法能夠在保證平均丟包率較小的情況下實現較大的吞吐量，提高網絡性能.但該算法目前只能在接口間平衡接收和發送流量的負載，如何平衡節點間的流量負載將作為下一步研究重點.