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

　　隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和應(yīng)用，用戶對(duì)網(wǎng)絡(luò)的移動(dòng)性和可靠性要求越來越高，基于IEEE 802.11系列標(biāo)準(zhǔn)的無線Mesh網(wǎng)絡(luò)近年來得到了快速、廣泛的應(yīng)用。在無線Mesh網(wǎng)絡(luò)中，任何無線設(shè)備節(jié)點(diǎn)都可以同時(shí)作為接入點(diǎn)(AP)和路由器，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都可以發(fā)送和接收信號(hào)，每個(gè)節(jié)點(diǎn)都可以與一個(gè)或者多個(gè)對(duì)等節(jié)點(diǎn)進(jìn)行直接通信。但由于無線網(wǎng)絡(luò)本身的特性和多種物理層傳輸技術(shù)的應(yīng)用，合適的媒體接入控制MAC 協(xié)議對(duì)無線Mesh網(wǎng)絡(luò)至關(guān)重要。

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

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

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

　　1 EDCA算法

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

　　1.1 EDCA算法簡(jiǎn)介

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

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

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

　　圖1 IEEE 802.11e EDCA的基本訪問機(jī)制

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

　　1.2 EDCA算法分析

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

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

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

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

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

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

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

　　2 FEDCA算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

　　圖3 公平因子F[AC]與ΔTXOP[AC]關(guān)系示意圖

　　2.2 FEDCA算法討論

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

　　(1)公平性的度量。FEDCA算法采用比例公平作為衡量公平性的標(biāo)準(zhǔn)，也就是每一類業(yè)務(wù)占用的網(wǎng)絡(luò)資源是成比例的，這樣除了可實(shí)現(xiàn)各等級(jí)業(yè)務(wù)間的公平外還可提高系統(tǒng)的吞吐量。FEDCA算法對(duì)每一類業(yè)務(wù)分配一個(gè)公平因子

用于表明該類業(yè)務(wù)在本移動(dòng)節(jié)點(diǎn)共享資源中可使用的份額;(2)在加權(quán)輪詢調(diào)度時(shí)給每一子隊(duì)列分配的權(quán)值W[AC]與關(guān)系FD[AC]:

　　FEDCA算法

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

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

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

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

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

　　3 仿真分析

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

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

　　圖4 無線網(wǎng)絡(luò)仿真的拓?fù)浣Y(jié)構(gòu)圖

　　圖5 VO、VI吞吐量隨時(shí)間變化圖

　　圖6 吞吐量與負(fù)載關(guān)系仿真圖

　　圖7 平均延遲與負(fù)載仿真圖

　　4 結(jié)論

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