多速率WLAN網絡的時間公平調度算法

潘志鵬,吳 斌,葉甜春

(中國科學院微電子研究所,北京 100029)

多速率WLAN網絡的時間公平調度算法

潘志鵬,吳 斌,葉甜春

(中國科學院微電子研究所,北京 100029)

IEEE 802.11協議的分布式協調功能使得各站點以相同的概率接入信道,會導致多速率無線局域網的性能異常.該文通過對吞吐率公平與時間公平進行詳細的理論分析與比較,提出了一種線性可調節時間公平的循環輪詢隊列調度算法.該算法實時地統計各站點準確的信道占用時間,并采用循環輪詢方式保證各站點之間的時間公平性,提升系統的吞吐率性能.為保障業務流的服務質量,采用動態調節方式更新輪詢單位服務時間,實現了傳輸效率與延時性能的折中.經過NS-3仿真與硬件系統實測驗證表明,該算法在嚴格保證時間公平的同時,有效提升了系統上/下行吞吐率性能.

無線局域網;吞吐率公平;時間公平;隊列調度;NS-3仿真

現有無線局域網(Wireless Local Area Network,WLAN)支持802.11a/b/g/n/ac協議,存在1 Mbit/s至1 Gbit/ss多種發送速率.而多速率WLAN將導致高速率站點所獲得的吞吐率性能與低速率站點保持一致,引起性能異常現象[1-2].這是由于802.11協議所采用的帶沖突避免的載波偵聽多路訪問(Carrier Sense Multiple Access with Collision Avoidance,CSMA/CA)機制,本質上提供各個站點以同等概率接入信道,并不區分各站點的傳輸速率,而低速率站點將占用更多的信道時間資源來傳輸相同大小的數據幀,降低了系統資源使用效率的同時,也導致了高速率站點的不公平性.針對多速率WLAN的性能異常問題,大量文獻基于時間公平性提出了不同的系統優化算法.根據優化對象可將其細分成兩大類:上行優化算法[3-8]和下行優化算法[9-11].

上行優化算法是一種分布式協調方法,通常采用修改各站點媒體接入控制層(Media Access Control, MAC)的參數,實現上行鏈路資源的最優化分配.可修改的MAC接入參數包括競爭窗口[6-7]、最小競爭窗口[4-5]、仲裁幀間間隔[5]、數據幀大小[8]、多分布式協調功能(Distributed Coordination Function,DCF)實例[3]等.而下行優化算法則是一種集中式調節算法,利用接入點對各個站點的高效調度機制,可以保證各個站點獲得同等的信道時間資源,進而實現下行鏈路的最優化分配.

目前,接入點的隊列調度機制一般采用先到先服務(First-Come First-Served,FCFS)或循環輪詢(Round Robin,RR)算法,保證了各個站點的吞吐率公平,尤其是單速率WLAN網絡.而下行優化算法采用基于時間公平的隊列調度機制,如基于時間的調節器(Time-Based Regulator,TBR)算法[9]與差額傳輸時間(Deficit Transmission Time,DTT)算法[10]等,一定程度上提升了下行鏈路的系統吞吐率性能.

筆者以不修改MAC層接入參數為前提,提出了一種線性可調節時間公平的循環輪詢隊列調度算法(Time-based Fairness Round Robin,TFRR),在保證下行用戶數據報協議(User Datagram Protocol,UDP)與傳輸控制協議(Transmission Control Protocol,TCP)傳輸鏈路以及上行TCP傳輸鏈路的時間公平性的同時,又能有效地提升系統的吞吐率性能.

1　系統模型與理論分析

一個典型的基礎型WLAN網絡,由1個接入點(Access Point,AP)負責管理N個站點(Station,STA)的無線接入,而處于不同信道環境的STA會通過速率自適應選擇最佳的發送速率,最終導致同一個網絡存在多種傳輸速率.不同的公平機制嚴重影響了多速率WLAN的系統性能.以下針對吞吐率公平與時間公平進行詳細的理論分析與性能比較.

假設站點i的發送速率為ri,則傳輸長度為L的數據幀所需時間可表示為

其中,tov為固定冗余開銷,包括物理層前導碼傳輸時間、反饋幀信道占用時間、短幀間間隔、分布式協調功能幀間間隔以及平均退避時間.若各站點均嚴格遵循CSMA/CA的競爭接入機制,則可保證接入信道的概率完全一致,最終實現各站點之間的吞吐率公平.定義飽和狀態下,各個站點均接入一次信道,其時間總和為)

在該時間段T內,吞吐率公平條件下總共傳輸了N個數據幀,則系統飽和吞吐率為

若采用時間公平機制,各個站點接入信道的時間保持一致,則每個站點所分配的信道時間為T/N,可得到時間段T內系統飽和吞吐率為

比較時間公平與吞吐率公平兩種公平機制下,系統飽和吞吐率的比值可表示為

當且僅當t1=t2=…=tN時等式成立,此時也意味著r1=r2=…=rN.由此可知,對于多速率WLAN,時間公平條件下的系統吞吐率性能(S2)將大于吞吐率公平下的系統性能(S1).因此,文中重點研究時間公平性機制,并提出相應的優化算法.

2　基于時間公平的TFRR算法

TFRR算法實現了基于線性可調節時間公平的隊列調度機制,集成于MAC軟件驅動層,其體系架構如圖1所示,主要由4個功能模塊組成:隊列調度、有效剩余時間更新、延時評估以及線性可調節公平.

圖1　TFRR算法體系架構

算法的核心思想是,AP實時統計各目的站點的上/下行數據幀傳輸的信道占用時間,進而更新其有效剩余時間,并以此作為隊列調度的依據,同時結合循環輪詢方式,最終可實現站點之間的時間公平性.另外,為保障特定數據流的服務質量(Quality of Service,QoS)性能,增加了延時評估模塊,采用動態調節方式更新每次輪詢各個目的站點可使用的信道時間資源.而考慮到不同場景的應用需求,增加了線性可調節公平模塊,通過配置不同的權衡因子可實現吞吐率公平與時間公平的折中.

該算法以每個獨立站點個體為調節粒度,可有效保證站點之間無線信道占用時間的公平性.其中,針對下行UDP/TCP流,AP端會根據各站點的有效信道利用時間,實現對不同目的站點的數據幀緩存隊列的主動調度,進而達到下行接入的時間公平性;而針對上行TCP流,AP端通過控制不同站點的TCP反饋幀的調度順序,間接實現了對不同發送速率站點的TCP流量控制,同樣可保證上行接入的時間公平性.

2.1隊列調度

TFRR算法實時統計并判斷各隊列的有效剩余時間,并結合循環輪詢機制,實現了高效的隊列調度.詳細的隊列調度流程如圖2所示.當各站點隊列均處于流量飽和條件下時,TFRR算法使得高速率站點相比于低速率站點可傳輸更多的數據幀,既保證了站點之間的時間公平性,又提升了系統的吞吐率性能.而在流量非飽和條件下,TFRR算法會將多余的傳輸機會分配給有需求的站點,以充分利用無線信道資源.

圖2　隊列調度流程

2.2有效剩余時間更新

有效剩余時間更新涉及3個過程:隊列初始化、輪詢周期內及輪詢周期結束.當站點i通過AP的認證與關聯操作后,AP會為該目的站點初始化一個緩存隊列,并將其有效剩余時間設置為

其中,Tu為每次輪詢各站點的單位服務時間.

在輪詢周期k內,AP會實時地統計各個站點所占用的無線信道時間,包含上/下行流量,對應AP端的接收/發送事件,每個數據幀占用的信道時間采用式(1)的計算方式.進而更新接收/發送數據幀所對應站點隊列的有效剩余時間,更新過程可表示為

其中,TRX和TTX分別為接收和發送數據幀的信道占用時間.

而輪詢周期k結束(RndComplete有效)時,AP會再一次更新所有站點隊列的有效剩余時間,即

其中,α為歷史殘留系數,通常設置α≤1/2,可保證有效剩余時間只受短期內的傳輸效果影響,且隨時間呈指數遞減關系;n表示站點i連續隊列為空的輪詢次數.這就意味著,如果一個站點長時間與AP無任何的數據通信,其有效剩余時間將趨于穩定值Tu.而在流量飽和條件下各站點每輪循環內所獲得的調度服務時間將保持一致,實現各站點之間的時間公平.

2.3延時評估

一個數據幀的傳輸延時主要由兩部分組成:排隊延時和媒體接入延時.其中,排隊延時除了受數據幀到達速率和無線傳輸速率影響外,不同的隊列調度機制也將導致差異化的延時性能.而媒體接入延時是數據幀被成功調度并啟動發送開始,直到目的端正確接收為止,該延時主要受網絡中的站點數和各站點的傳輸速率影響.

由此可知,眾多影響因素中,隊列調度是惟一可供調節且影響著系統的延時性能.因此,TFRR算法增加了延時評估功能模塊.該模塊根據當前活躍站點數(NSTA)以及各站點的延時限制,選擇合適的單位服務時間.在流量飽和條件下,一個完整的輪詢周期Tpoll可表示為

一方面,單位服務時間越大,則輪詢周期越長,會導致服務間隔增大,影響了特定流量的延時性能;另一方面,單位服務時間越小,則站點每次服務所分配的傳輸時間越短,降低了MAC層傳輸效率,尤其是支持11n/ac協議幀聚合功能的站點.綜上所述,在保證所有業務流的QoS前提下,理應選擇最大的單位服務時間以提高數據幀傳輸效率.因此,可采用的更新方式為

其中,dmin為所有業務流之中最小的傳輸延時限制值.

2.4線性可調節公平

時間公平算法通過限制各站點接入信道時間的一致性,避免了多速率網絡的性能異常現象,可提高整個系統的吞吐率性能.但這是以減小低速率站點的吞吐率為代價的,在流量飽和情況下會導致低速率站點與高速率站點之間吞吐率性能的極度不公平性.某些應用場景,如機場、咖啡廳等公共場所,將會受益于時間公平算法所帶來的性能提升;而有些應用場景,比如應急通信場所,則更傾向于吞吐率公平所能維持的性能穩定性.因此,為適應不同的場景需求,文中采用了線性可調節公平機制.具體調節效果可歸納為

其中,βTFRR為權衡因子,滿足0≤βTFRR≤1,表示時間公平與吞吐率公平之間的折中效果,即βTFRR越大,時間公平效果越明顯;反之,則吞吐率公平效果就越顯著.特別地,當βTFRR=1時,系統將采用TFRR隊列調度算法實現完全的時間公平;而當βTFRR=0時,系統則采用基本的RR隊列調度算法實現完全的吞吐率公平.

3　NS-3　仿真

3.1仿真系統構建

利用NS-3軟件[12]構建了由1個AP和N個STA組成的基礎型WLAN網絡.每個節點包含了對上層應用、傳輸控制/網絡通信協定(Transmission Control Protocol/Internet Protocol,TCP/IP)協議棧、WLAN網絡設備和無線信道等各個層次的精確模擬.為仿真真實場景的上、下行流量特性,采用開/關或泊松分布兩種方式產生特定模式的傳輸控制/用戶數據報協議(Transmission Control Protocol/User Datagram Protocol,TCP/UDP)數據流.WLAN網絡設備采用802.11a協議,其中間層包含了基本DCF競爭接入機制、隊列調度算法和速率自適應等模塊.仿真實驗中,添加了對FCFS、RR、DTT和TFRR這4種隊列調度算法的模型構建及性能仿真.

3.2吞吐率性能與公平性比較

將仿真系統設置為1個AP和10個STA,其中,STA-1～STA-3、STA-4～STA-5、STA-6～STA-7和STA-8～STA-10與AP的距離分別為10 m、40 m、70 m和100 m,對應的穩定傳輸速率等效于54 Mbit/s、36 Mbit/s、18 Mbit/s和6 Mbit/s.上層UDP協議流量采用泊松分布方式產生,而TCP協議采用了Westwood無線擁塞控制協議.所有的數據幀大小均設置為1 500 B.針對FCFS、RR、DTT和TFRR這4種算法,分別仿真了下行UDP、下行TCP以及上行TCP這3種流量場景.

圖3表明了TFRR算法的系統吞吐率性能在3種不同的流量場景下,相比于FCFS算法與RR算法提升了50%～75%;而在上行TCP場景下,相比于DTT算法提升了47%.進一步分析可知,TFRR算法是惟一一個能在3種流量場景下均保持嚴格時間公平的算法,而FCFS算法與RR算法維持了系統吞吐率公平,DTT算法則僅僅保證了下行流量的時間公平.

圖3　上/下行吞吐率性能比較

3.3延時性能分析

為了分析TFRR算法的單位服務時間對各個站點延時性能的影響,基于下行UDP仿真場景,設置STA-1～STA-5速率為54 Mbit/s,STA-6～STA-10速率為6 Mbit/s,并為各站點添加了1.5 Mbit/s的下行UDP流量,此時高速率站點將處于流量非飽和狀態,而低速率站點則是流量飽和狀態.將參數Tu分別固定為1 ms、3 ms和5 ms,仿真了各站點的吞吐率性能與數據幀傳輸延時分布情況.結果表明,各站點的吞吐率性能并不受Tu大小的影響,而高速率站點的傳輸延時會隨著Tu的增大而呈線性增加,其傳輸延時的累積分布函數(Cumulative Distribution Function,CDF)如圖4所示.這是由于飽和流量站點的服務周期增加了非飽和流量站點的排隊等待延時.因此,實際應用場景下有必要根據式(10)對Tu參數進行約束,既可保證所有站點的延時性能,又盡可能地提高數據傳輸效率.

圖4　TFRR算法的延時分布特性

圖5　TFRR算法的線性可調節公平

3.4可調節公平性

針對下行TCP仿真場景,線性地調整權衡因子βTFRR的大小,并依次統計系統的吞吐率性能(S)與公平性系數(Fairness Index,FI)大小,采用Jain公平因子[13]評估系統的公平系數,結果如圖5所示.從圖5可明顯地發現,隨著權衡因子的逐漸遞增,系統的吞吐率性能呈現線性遞增趨勢.這是由于權衡因子越大,系統的時間公平性比重越高,有利于提升多速率網絡的系統吞吐率性能,而公平性系數與權衡因子也同樣近似于線性關系.

3.5移動場景

為模擬真實環境,設置了如圖6所示的節點分布及其位置移動場景.其中, STA-1～STA-3和STA-6～STA-8為靜止節點,與AP的距離分別為10 m和100 m;STA-4和STA-5為移動節點,以2 m/s的固定速率移動.為比較RR算法、DTT算法和TFRR算法的隊列調度性能,系統添加了混合的上、下行TCP流量,仿真效果如圖7所示.需要指出的是,在RR算法下各站點的性能變化情況類似于DTT算法的,因此,僅給出了DTT算法與TFRR算法的實時仿真效果.

圖6　移動場景的網絡拓撲

從圖7(a)可知,在混合流量條件下,RR算法或DTT算法并不能很好地保證系統中各站點之間的吞吐率公平或時間公平,而是隨著移動場景的改變而起伏變化.而圖7(b)則表明,TFRR算法在嚴格保證各站點接入信道時間一致性的同時,使得各站點的吞吐率性能具備了一定的比例公平性.其中,STA-4隨著距離的不斷增加導致其吞吐率性能的逐級遞減,直至與AP解關聯;STA-5在前半段時間內逐漸靠近AP,而在后半段時間內逐漸遠離AP,反映在吞吐率性能上則是先逐級遞增,然后再逐級遞減;STA-2和STA-7的吞吐率性能并不受移動節點的影響,反而會由于STA-4退出網絡,活躍站點數的減小,最終使得后半段時間內的吞吐率性能略有提升.

圖7(c)則表明了,AP采用TFRR隊列調度算法所獲得的系統吞吐率性能將遠大于RR算法和DTT算法的,這也體現了TFRR算法在真實的混合流量環境下所具有的性能優越性.

4　實測驗證

為了驗證TFRR算法的可行性,搭建了一個硬件系統測試平臺,包含1個AP和2個STA.所有節點均采用集成Atheros的AR5212A無線模塊的便攜式電腦,移植開源驅動軟件Madwifi之后,可支持IEEE 802.11a/b/g協議.速率自適應選擇AMRR算法,兩個STA的最佳傳輸速率分別為54 Mbit/s與6 Mbit/s.在AP端實現了RR和TFRR兩種隊列調度算法,并置于硬件系統中進行實測分析.采用Iperf軟件分別測試了RR算法與TFRR算法的飽和UDP與TCP吞吐率性能,實測結果如圖8所示.無論是UDP流量,還是TCP流量,RR算法保證了各站點的吞吐率公平,而TFRR算法在時間公平的基礎上則是保證了各站點吞吐率性能的比例公平性.這也直接導致了TFRR算法的系統UDP與TCP吞吐率性能相比于RR算法分別提升了107%與96.5%.

5　結束語

針對多速率WLAN網絡分析了時間公平條件下的性能優越性,筆者提出了線性可調節時間公平的循環輪詢隊列調度算法.該算法不僅利用不同速率站點之間的時間公平提升系統的吞吐率性能,又兼顧了數據幀的傳輸延時限制.同時,針對不同的應用場景需求,還支持線性可調節公平機制,實現了吞吐率公平與時間公平的折中.最后,通過NS-3仿真與硬件系統測試驗證了該算法的有效性與可行性.

[1]HEUSSE M,ROUSSEAU F,BERGER S G,et al.Performance Anomaly of 802.11b[C]//Proceedings of IEEE INFOCOM.Piscataway:IEEE,2003:836-843.

[2]GORBENKO A,TARASYUK O,KHARCHENKO V,et al.Estimating Throughput Unfairness in a Mixed Data Rate Wi-Fi Environment[C]//2013 International Conference on Digital Technologies.Piscataway:IEEE,2013:181-184.

[3]YAZICI M A,AKAR N.Running Multiple Instances of the Distributed Coordination Function for Air-time Fairness in Multi-rate WLANs[J].IEEE Transactions on Communications,2013,61(12):5067-5076.

[4]JOSHI T,MUKHERJEE A,YOO Y,et al.Airtime Fairness for IEEE 802.11 Multirate Networks[J].IEEETransactions on Mobile Computing,2008,7(4):513-527.

[5]LIN P,CHOU W,LIN T.Achieving Airtime Fairness of Delaysensitive Applications in Multirate IEEE 802.11 Wireless LANs[J].IEEE Communications Magazine,2011,49(9):169-175.

[6]LE Y,MA L,CHENG W,et al.A Time Fairness Based MAC Algorithm for Throughput Maximization in 802.11 Networks[J].IEEE Transactions on Computers,2015,64(1):19-31.

[7]TARASYUK O,GORBENKO A,KHARCHENKO V,et al.Contention Window Adaptation to Ensure Airtime Consumption Fairness in Multirate Wi-Fi Networks[C]//2014 10th International Conference on Digital Technologies. Piscataway:IEEE,2014:344-349.

[8]HU S P,LI J D,PAN G F.Performance and Fairness Enhancement in IEEE 802.11 WLAN Networks[J].AEUInternational Journal of Electronics and Communications,2014,68(7):667-675.

[9]TAN G,GUTTAG J.Time-based Fairness Improves Performance in Multi-rate WLANs[C]//Proceedings of the Annual Conference on USENIX Annual Technical Conference.Berkeley:USENIX Assoc,2004:269-282.

[10]GARROPPO R G,GIORDANO S,LUCETTI S,et al.Providing Air-time Usage Fairness in IEEE 802.11 Networks with the Deficit Transmission Time(DTT)Scheduler[J].ACM Wireless Networks,2007,13(4):481-495.

[11]SHAPIRA N,HENCINSKI O,SHIRI M,et al.Airtime-aware Scheduling for Wireless Local-area Network:US 0269635[P].2014-09-18.

[12]NS-3 PROJECT.NS-3 Manual[EB/OL].[2015-03-12].http://www.nsnam.org/docs/release/3.19/manual/ns-3-manual.pdf.

[13]JAIN R,DURRESI A,BABIC G.Throughput Fairness Index:an Explanation:ATM Forum/99-0045[R].Columbus: ATM,1999.

(編輯:齊淑娟)

Airtime fairness scheduling algorithm for multi-rate WLANs

PAN Zhipeng,WU Bin,YE Tianchun
(Institute of Microelectronics,Chinese Academy of Sciences,Beijing 100029,China)

The DCF(Distributed Coordination Function)used in the IEEE 802.11 protocol provides equal transmission opportunities to each station,which will lead to the performance anomaly in the multi-rate wireless local area network(WLAN).In this paper,we propose a round-robin queue scheduler based on linear scaling of airtime fairness after a detailed theoretical analysis of throughput fairness and airtime fairness.It counts the accurate channel occupancy time of each station,then adopts round-robin to ensure the airtime fairness,and finally improves the system throughput.According to the quality of service(QoS) of data flows,the proposed algorithm can achieve a compromise between transmission efficiency and delay performance by dynamically updating the polling cycle.Simulation by NS-3 and verification by the hardware system show that the proposed algorithm can effectively improve the system uplink and downlink throughput performance while ensuring per-station airtime fairness.

WLAN;throughput fairness;airtime fairness;queue scheduler;NS-3 simulation

TN925+.93

A

1001-2400(2016)04-0128-07

10.3969/j.issn.1001-2400.2016.04.023

2015-03-31 網絡出版時間：2015-10-21

國家科技重大專項資助項目(2013ZX03004007);北京市科技新星計劃資助項目(2010B060)

潘志鵬(1988-),男,中國科學院博士研究生,E-mail:panzhipeng@ime.ac.cn.

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.046.html