無線Mesh網(wǎng)絡中基于公平的EDCA算法

在無線Mesh網(wǎng)絡中應用的MAC協(xié)議包括：CSMA/CA、DCF、PCF等，為了在MAC子層實現(xiàn)對不同業(yè)務流的QoS支持，IEEE 802.11e工作組在IEEE 802.11中DCF機制的基礎上提出了增強分布式信道接入機制(Enhanced Distributed Channel Access，EDCA)，使得無線Mesh網(wǎng)絡可以更好地提供音頻和視頻業(yè)務的服務。

EDCA將不同的業(yè)務流分為4個不同的優(yōu)先等級AC(Access Categories)，每一個AC對應一個隊列，通過設置仲裁幀間間隔(Arbitration Interframe Space，AIFS)、最小競爭窗口值CWmin、最大競爭窗口CWmax和傳輸機會TXOP(TraNSmission Opportunity)4個參數(shù)值實現(xiàn)不同業(yè)務流間的業(yè)務區(qū)分。文獻研究表明，由于無線網(wǎng)絡狀況的移動性和復雜性，EDCA算法中4個參數(shù)的靜態(tài)設置并不能使無線網(wǎng)絡的性能實現(xiàn)最優(yōu)，特別在高負載或突發(fā)業(yè)務量較大的狀況下，由于無線網(wǎng)絡中有較高的沖突率，EDCA的網(wǎng)絡性能急劇下降，無法滿足網(wǎng)絡用戶的要求。也有相關研究通過CW的自適應調整機制及相關退避算法的改進，如Lamia Romdhani提出的AEDCF機制(Adaptive EDCF，AEDCF);Younggoo Kwon提出的快速碰撞解決機制(Fast Collision Resolutio，F(xiàn)CR)等，使得EDCA算法更適合無線網(wǎng)絡環(huán)境。但這些研究都沒有考慮EDCA算法本身及參數(shù)AIFS、CWmin、CWmax和TXOP調整后對無線Mesh網(wǎng)絡公平性(節(jié)點間和不同業(yè)務流間)帶來的影響。

本文提出了一種基于公平的EDCA算法(Fairness-based EDCA，F(xiàn)EDCA)。FEDCA算法的基本思想是通過加權輪詢的方式確定傳輸?shù)臄?shù)據(jù)接入類別和本次信道偵聽的時間，通過公平因子的計算確定TXOP參數(shù)，以達到保證網(wǎng)絡公平性的條件下提高網(wǎng)絡性能和QoS保證的目的。并通過仿真結果驗證該算法的可行性。

1 EDCA算法

EDCA是IEEE 802.11e工作組在IEEE 802.11協(xié)議中DCF機制基礎上進行QoS支持提出的，其基本的接入信道方式與DCF保持一致，各移動節(jié)點以CSMA/CA方式通過競爭獲得信道接入的機會。同時EDCA提供了不同類型業(yè)務數(shù)據(jù)傳輸?shù)亩喾N信道接入類別AC，可以實現(xiàn)不同業(yè)務的服務區(qū)分。

1.1 EDCA算法簡介

為保證不同業(yè)務的不同QoS要求，EDCA算法定義了上層的8類業(yè)務類別(Traffic Category，TC)和本層的4類基于IEEE 802.1D的接入類別(Access Category，AC)，8類TC分別映射至4類AC的隊列中：AC_VO，AC_VI，AC_BE和AC_BK，分別代表語音(Voice)類，視頻(Video)類，盡力而為(Best Effort)類和背景(Background)類的業(yè)務。為實現(xiàn)4個AC隊列不同優(yōu)先級的區(qū)別，定義了4個參數(shù)：仲裁幀間間隔AIFS、最小競爭窗口值CWmin、最大競爭窗口CWmax和傳輸機會TXOP.不同的AC通過不同的參數(shù)設置，控制其接入信道的過程，從而實現(xiàn)了不同業(yè)務類型的區(qū)分。

某一移動節(jié)點通過兩個階段實現(xiàn)一個AC隊列內的數(shù)據(jù)發(fā)送。首先在一個節(jié)點內部爭奪傳輸機會TXOP，獲得傳輸機會的隊列才有可能獲得信道接入的機會。其次，獲得信道接入機會的分組再在不同的節(jié)點間通過CSMA/CA方式獲得信道接入機會才可以進行數(shù)據(jù)傳輸。EDCA算法完成數(shù)據(jù)傳輸?shù)谝浑A段的任務：不同隊列通過競爭獲得傳輸機會。

IEEE 802.11e EDCA的基本訪問機制如圖1所示。

圖1 IEEE 802.11e EDCA的基本訪問機制

當因競爭信道發(fā)生沖突時，就進入退避過程。在此過程中，將退避計數(shù)器Backoff Timer置為[0，CW[AC]]范圍內的任一整數(shù)值：Backoff_Timer(BT)=uniform[0，CW]×aSlotTime.CW[AC]的初始值設為CWmin[AC].當發(fā)生碰撞時，CW[AC]的值就增加為(CW[AC]+1)×2-1，當CW[AC]增加到CWmax[AC]時，就維持CWmax[AC]的值不變，不再增加。當數(shù)據(jù)幀成功發(fā)送之后，將CW[AC]的值重置為CWmin[AC]，繼續(xù)偵聽信道。退避計時器每檢測到一個空閑時隙，其值(BT)減1，最先減到零的數(shù)據(jù)幀占用信道，若節(jié)點內多個AC的退避計時器同時減到零，則較高優(yōu)先級隊列的數(shù)據(jù)幀將占用信道，其他數(shù)據(jù)幀又進入新一輪的退避過程。

1.2 EDCA算法分析

從圖1中可以看出，較高優(yōu)先級的AC通過設置較小的AIFS、CWmin和CWmax將優(yōu)先獲得無線信道的訪問權，從而實現(xiàn)不同不同業(yè)務的業(yè)務區(qū)分。IEEE 802.11e標準中給出了一組EDCA參數(shù)建議值，適合于大部分情況下的網(wǎng)絡應用。但由于無線網(wǎng)絡本身的移動性和可擴展性，在網(wǎng)絡規(guī)模較大或網(wǎng)絡流量動態(tài)變化時，標準中的建議值會對無線Mesh網(wǎng)絡各移動節(jié)點及某一節(jié)點下的不同業(yè)務流造成不公平的現(xiàn)象，具體體現(xiàn)在以下幾個方面：

(1)AIFS、AIFSN設置值導致節(jié)點間的不公平性。IEEE 802.11e標準中給出AIFS[AC]=aSIFSTime+AIFSN[AC]×aSlotTime.網(wǎng)絡中所有移動節(jié)點AIFS、AIFSN值相同，這樣有可能在網(wǎng)絡中引起準同步現(xiàn)象(某一節(jié)點本次通過競爭獲得信道使得下次競爭獲得信道的概率增大)的出現(xiàn)，導致無線網(wǎng)絡中其他節(jié)點多次競爭而無法獲得信道的現(xiàn)象頻繁出現(xiàn)，從而使得不同節(jié)點接入信道、共享資源的不公平，同時進一步降低網(wǎng)絡鏈路的利用率，影響業(yè)務流的服務質量。

(2)AIFSN值的固定設置導致不同等級業(yè)務流間的不公平。由于高優(yōu)先級的AIFSN值較小，在高優(yōu)先級需傳輸?shù)臄?shù)據(jù)較多的情況下，低優(yōu)先級的業(yè)務流在競爭信道時始終無法獲得信道，必然導致低優(yōu)先級業(yè)務的“饑餓”現(xiàn)象。

(3)CWmin和CWmax的設置。從EDCA的基本訪問機制來看，CW[AC]的值成為影響AC隊列發(fā)送數(shù)據(jù)和發(fā)送數(shù)據(jù)失敗后重新競爭獲得信道的關鍵因素。CWmin和CWmax值雖然實現(xiàn)了不同業(yè)務間的業(yè)務區(qū)分，但在網(wǎng)絡高負載情況下，同樣會導致低優(yōu)先級業(yè)務的“饑餓”現(xiàn)象。

(4)TXOP的設置。TXOP反映了獲得數(shù)據(jù)發(fā)送機會的隊列最大發(fā)送數(shù)據(jù)幀數(shù)。如果采用IEEE 802.11e標準中的參考值，就會導致不公平的信道競爭機制在各業(yè)務流間更大的不公平。

(5)EDCA算法沒有考慮節(jié)點的移動性及信道干擾導致誤碼對網(wǎng)絡公平性的影響。

基于此，為提高無線網(wǎng)絡的公平性、網(wǎng)絡性能及不同業(yè)務流的QoS保證，F(xiàn)EDCA算法對EDCA算法中的AIFSN、CWmin、CWmax和TXOP四個參數(shù)依據(jù)公平性原則進行調整，以保證移動節(jié)點間和不同等級業(yè)務間的公平。

2 FEDCA算法實現(xiàn)

基于以上分析，本節(jié)詳細討論無線網(wǎng)絡中FEDCA算法具體實現(xiàn)過程。

2.1 FEDCA算法的實現(xiàn)

為保證移動節(jié)點間和同一節(jié)點內的不同等級業(yè)務流的公平，F(xiàn)EDCA算法實現(xiàn)過程可以概括為：加權輪詢調度、擁塞窗口CW動態(tài)調整、公平因子計算及TXOP調整。

(1)加權輪詢調度。FEDCA算法執(zhí)行模型如圖2所示。

圖2 FEDCA算法執(zhí)行模型

加權輪詢調度的思想是為保證各等級業(yè)務間的公平性，給每一子隊列分配一個權值，根據(jù)不同的權值來調度不同子隊列中的數(shù)據(jù)，而不是采用EDCA算法中的最小退避窗口的隊列獲得數(shù)據(jù)發(fā)送的機會。其具體的實現(xiàn)過程為每一子隊列AC分配一個對應的權值W[AC](該權值表明該子隊列可以連續(xù)發(fā)送數(shù)據(jù)的次數(shù))，按輪詢的方式為每個子隊列發(fā)送數(shù)據(jù)，如果某一子隊列內的數(shù)據(jù)不夠發(fā)送Wi次或為空，轉到下一子隊列準備發(fā)送數(shù)據(jù)，如此輪流執(zhí)行。

(2)擁塞窗口CW動態(tài)調整。為保證各移動節(jié)點間和同一移動節(jié)點內不同等級業(yè)務的公平性和提高系統(tǒng)的吞吐量，F(xiàn)ECDA算法中所有業(yè)務等級的擁塞窗口CW都采用先指數(shù)退避在線性退避的方式，即對任意隊列在CWCWmax，擁塞窗口維持CWmax不變。

(3)公平因子計算及TXOP調整。在每一輪輪詢數(shù)據(jù)轉發(fā)完成后，為保證同一移動節(jié)點中不同等級業(yè)務流的公平，F(xiàn)EDCA算法通過對每一子隊列的公平因子F[AC]計算，并與事先規(guī)定的公平因子FD[AC]比較，通過比較的結果確定下一輪調度的每一子隊列大小TXOP[AC]=(TXOP[AC]+ΔTXOP[AC])，其具體變化關系如圖3所示。

圖3公平因子F[AC]與ΔTXOP[AC]關系示意圖

2.2 FEDCA算法討論

從FEDCA算法實現(xiàn)過程來看：

(1)公平性的度量。FEDCA算法采用比例公平作為衡量公平性的標準，也就是每一類業(yè)務占用的網(wǎng)絡資源是成比例的，這樣除了可實現(xiàn)各等級業(yè)務間的公平外還可提高系統(tǒng)的吞吐量。FEDCA算法對每一類業(yè)務分配一個公平因子用于表明該類業(yè)務在本移動節(jié)點共享資源中可使用的份額;

(2)在加權輪詢調度時給每一子隊列分配的權值W[AC]與關系FD[AC]：

(3)FEDCA算法通過輪詢的方式確定可以發(fā)送的隊列數(shù)據(jù)，在發(fā)送成功后其擁塞窗口CW的變化方式與EDCA算法一致，發(fā)送失敗后擁塞避免的過程也與EDCA算法一致，但其擁塞窗口的變化采用FEDCA算法描述中的方法，目的是維護節(jié)點內各等級業(yè)務的公平性。

(4)每一業(yè)務等級的公平因子FD[AC]計算公式為：

式中：Total-Length[AC]為本輪輪詢調度中隊列AC被調度的數(shù)據(jù)總長度;為保證每一隊列能計算出該隊列在本輪調度中的公平因子FD[AC]，對某一隊列應維護一個計數(shù)器，用于統(tǒng)計該隊列調度的數(shù)據(jù)長度Total-Length[AC].

(5)ΔTXOP[AC]的計算公式為：

如圖3 所示，為了體現(xiàn)不同業(yè)務間的區(qū)分ΔTXOP[高] > ΔTXOP [低];F [高] max > F [低] max;F[高] min < F [低] min .同時圖3給出的ΔTXOPmin[AC]與Fmin[AC]示意圖，具體的各參數(shù)的設置可根據(jù)網(wǎng)絡實際情況和網(wǎng)絡管理員自行設定。考慮到無線網(wǎng)絡運行的可靠性和穩(wěn)定性，本算法建議ΔTXOP [AC] max不超過TXOPmin[AC]的參考值的1/8 為宜，最大不能超過1/4。

3 仿真分析

為了驗證FEDCA 算法性能，通過網(wǎng)絡仿真工具NS2 實現(xiàn)該算法和EDCA 算法的性能比較。仿真所采用的拓撲結構如圖4所示，仿真時物理層采用802.11b，物理帶寬設為11 Mb/s，4個移動節(jié)點分別發(fā)送VI、VO、BE和BK四種業(yè)務流，這4種業(yè)務流占總負載的比例為1∶1∶2∶4。分別對FEDCA、EDCA 算法的吞吐量、端到端的延遲及等級業(yè)務流量VO、VI的變化情況進行了仿真，仿真結果如圖5~圖7所示。

從圖5的仿真結果可以看出，同一等級的業(yè)務采用FEDCA 算法業(yè)務量的變化幅度及變換頻率比EDCA算法要小，而且不同等級的業(yè)務量比例基本保持不變，從而保證了移動節(jié)點內各業(yè)務間的公平性;從圖6仿真結果可看出FEDCA算法能提高各類業(yè)務的吞吐量，從而提高了無線信道利用率;同時圖7的仿真結果表明FEDCA算法能減少數(shù)據(jù)幀的平均轉發(fā)延遲，從而提高了網(wǎng)絡的QoS。

圖4 無線網(wǎng)絡仿真的拓撲結構圖

圖5 VO、VI吞吐量隨時間變化圖

圖6 吞吐量與負載關系仿真圖

圖7 平均延遲與負載仿真圖

4 結論

本文提出的FEDCA算法能夠根據(jù)網(wǎng)絡的公平性要求，通過加權輪詢的方式解決移動節(jié)點內的不同子隊列競爭信道的問題，改變擁塞窗口的變化方式，提高系統(tǒng)的吞吐量和公平性，通過公平因子調整EDCA算法中的TXOP參數(shù)，最終實現(xiàn)提高無線Mesh網(wǎng)絡的公平性和改善網(wǎng)絡性能的目的。通過仿真分析可知，F(xiàn)EDCA 算法保證了移動節(jié)點間和節(jié)點內不同業(yè)務的公平性，同時能夠提高網(wǎng)絡性能和實現(xiàn)對不同業(yè)務的區(qū)分。