多速率WLAN網(wǎng)絡(luò)的時(shí)間公平調(diào)度算法

潘志鵬,吳 斌,葉甜春

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

多速率WLAN網(wǎng)絡(luò)的時(shí)間公平調(diào)度算法

潘志鵬,吳 斌,葉甜春

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

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

無線局域網(wǎng);吞吐率公平;時(shí)間公平;隊(duì)列調(diào)度;NS-3仿真

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

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

目前,接入點(diǎn)的隊(duì)列調(diào)度機(jī)制一般采用先到先服務(wù)(First-Come First-Served,FCFS)或循環(huán)輪詢(Round Robin,RR)算法,保證了各個(gè)站點(diǎn)的吞吐率公平,尤其是單速率WLAN網(wǎng)絡(luò).而下行優(yōu)化算法采用基于時(shí)間公平的隊(duì)列調(diào)度機(jī)制,如基于時(shí)間的調(diào)節(jié)器(Time-Based Regulator,TBR)算法[9]與差額傳輸時(shí)間(Deficit Transmission Time,DTT)算法[10]等,一定程度上提升了下行鏈路的系統(tǒng)吞吐率性能.

筆者以不修改MAC層接入?yún)?shù)為前提,提出了一種線性可調(diào)節(jié)時(shí)間公平的循環(huán)輪詢隊(duì)列調(diào)度算法(Time-based Fairness Round Robin,TFRR),在保證下行用戶數(shù)據(jù)報(bào)協(xié)議(User Datagram Protocol,UDP)與傳輸控制協(xié)議(Transmission Control Protocol,TCP)傳輸鏈路以及上行TCP傳輸鏈路的時(shí)間公平性的同時(shí),又能有效地提升系統(tǒng)的吞吐率性能.

1　系統(tǒng)模型與理論分析

一個(gè)典型的基礎(chǔ)型WLAN網(wǎng)絡(luò),由1個(gè)接入點(diǎn)(Access Point,AP)負(fù)責(zé)管理N個(gè)站點(diǎn)(Station,STA)的無線接入,而處于不同信道環(huán)境的STA會(huì)通過速率自適應(yīng)選擇最佳的發(fā)送速率,最終導(dǎo)致同一個(gè)網(wǎng)絡(luò)存在多種傳輸速率.不同的公平機(jī)制嚴(yán)重影響了多速率WLAN的系統(tǒng)性能.以下針對(duì)吞吐率公平與時(shí)間公平進(jìn)行詳細(xì)的理論分析與性能比較.

假設(shè)站點(diǎn)i的發(fā)送速率為ri,則傳輸長(zhǎng)度為L(zhǎng)的數(shù)據(jù)幀所需時(shí)間可表示為

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

在該時(shí)間段T內(nèi),吞吐率公平條件下總共傳輸了N個(gè)數(shù)據(jù)幀,則系統(tǒng)飽和吞吐率為

若采用時(shí)間公平機(jī)制,各個(gè)站點(diǎn)接入信道的時(shí)間保持一致,則每個(gè)站點(diǎn)所分配的信道時(shí)間為T/N,可得到時(shí)間段T內(nèi)系統(tǒng)飽和吞吐率為

比較時(shí)間公平與吞吐率公平兩種公平機(jī)制下,系統(tǒng)飽和吞吐率的比值可表示為

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

2　基于時(shí)間公平的TFRR算法

TFRR算法實(shí)現(xiàn)了基于線性可調(diào)節(jié)時(shí)間公平的隊(duì)列調(diào)度機(jī)制,集成于MAC軟件驅(qū)動(dòng)層,其體系架構(gòu)如圖1所示,主要由4個(gè)功能模塊組成:隊(duì)列調(diào)度、有效剩余時(shí)間更新、延時(shí)評(píng)估以及線性可調(diào)節(jié)公平.

圖1　TFRR算法體系架構(gòu)

算法的核心思想是,AP實(shí)時(shí)統(tǒng)計(jì)各目的站點(diǎn)的上/下行數(shù)據(jù)幀傳輸?shù)男诺勒加脮r(shí)間,進(jìn)而更新其有效剩余時(shí)間,并以此作為隊(duì)列調(diào)度的依據(jù),同時(shí)結(jié)合循環(huán)輪詢方式,最終可實(shí)現(xiàn)站點(diǎn)之間的時(shí)間公平性.另外,為保障特定數(shù)據(jù)流的服務(wù)質(zhì)量(Quality of Service,QoS)性能,增加了延時(shí)評(píng)估模塊,采用動(dòng)態(tài)調(diào)節(jié)方式更新每次輪詢各個(gè)目的站點(diǎn)可使用的信道時(shí)間資源.而考慮到不同場(chǎng)景的應(yīng)用需求,增加了線性可調(diào)節(jié)公平模塊,通過配置不同的權(quán)衡因子可實(shí)現(xiàn)吞吐率公平與時(shí)間公平的折中.

該算法以每個(gè)獨(dú)立站點(diǎn)個(gè)體為調(diào)節(jié)粒度,可有效保證站點(diǎn)之間無線信道占用時(shí)間的公平性.其中,針對(duì)下行UDP/TCP流,AP端會(huì)根據(jù)各站點(diǎn)的有效信道利用時(shí)間,實(shí)現(xiàn)對(duì)不同目的站點(diǎn)的數(shù)據(jù)幀緩存隊(duì)列的主動(dòng)調(diào)度,進(jìn)而達(dá)到下行接入的時(shí)間公平性;而針對(duì)上行TCP流,AP端通過控制不同站點(diǎn)的TCP反饋幀的調(diào)度順序,間接實(shí)現(xiàn)了對(duì)不同發(fā)送速率站點(diǎn)的TCP流量控制,同樣可保證上行接入的時(shí)間公平性.

2.1隊(duì)列調(diào)度

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

圖2　隊(duì)列調(diào)度流程

2.2有效剩余時(shí)間更新

有效剩余時(shí)間更新涉及3個(gè)過程:隊(duì)列初始化、輪詢周期內(nèi)及輪詢周期結(jié)束.當(dāng)站點(diǎn)i通過AP的認(rèn)證與關(guān)聯(lián)操作后,AP會(huì)為該目的站點(diǎn)初始化一個(gè)緩存隊(duì)列,并將其有效剩余時(shí)間設(shè)置為

其中,Tu為每次輪詢各站點(diǎn)的單位服務(wù)時(shí)間.

在輪詢周期k內(nèi),AP會(huì)實(shí)時(shí)地統(tǒng)計(jì)各個(gè)站點(diǎn)所占用的無線信道時(shí)間,包含上/下行流量,對(duì)應(yīng)AP端的接收/發(fā)送事件,每個(gè)數(shù)據(jù)幀占用的信道時(shí)間采用式(1)的計(jì)算方式.進(jìn)而更新接收/發(fā)送數(shù)據(jù)幀所對(duì)應(yīng)站點(diǎn)隊(duì)列的有效剩余時(shí)間,更新過程可表示為

其中,TRX和TTX分別為接收和發(fā)送數(shù)據(jù)幀的信道占用時(shí)間.

而輪詢周期k結(jié)束(RndComplete有效)時(shí),AP會(huì)再一次更新所有站點(diǎn)隊(duì)列的有效剩余時(shí)間,即

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

2.3延時(shí)評(píng)估

一個(gè)數(shù)據(jù)幀的傳輸延時(shí)主要由兩部分組成:排隊(duì)延時(shí)和媒體接入延時(shí).其中,排隊(duì)延時(shí)除了受數(shù)據(jù)幀到達(dá)速率和無線傳輸速率影響外,不同的隊(duì)列調(diào)度機(jī)制也將導(dǎo)致差異化的延時(shí)性能.而媒體接入延時(shí)是數(shù)據(jù)幀被成功調(diào)度并啟動(dòng)發(fā)送開始,直到目的端正確接收為止,該延時(shí)主要受網(wǎng)絡(luò)中的站點(diǎn)數(shù)和各站點(diǎn)的傳輸速率影響.

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

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

其中,dmin為所有業(yè)務(wù)流之中最小的傳輸延時(shí)限制值.

2.4線性可調(diào)節(jié)公平

時(shí)間公平算法通過限制各站點(diǎn)接入信道時(shí)間的一致性,避免了多速率網(wǎng)絡(luò)的性能異?，F(xiàn)象,可提高整個(gè)系統(tǒng)的吞吐率性能.但這是以減小低速率站點(diǎn)的吞吐率為代價(jià)的,在流量飽和情況下會(huì)導(dǎo)致低速率站點(diǎn)與高速率站點(diǎn)之間吞吐率性能的極度不公平性.某些應(yīng)用場(chǎng)景,如機(jī)場(chǎng)、咖啡廳等公共場(chǎng)所,將會(huì)受益于時(shí)間公平算法所帶來的性能提升;而有些應(yīng)用場(chǎng)景,比如應(yīng)急通信場(chǎng)所,則更傾向于吞吐率公平所能維持的性能穩(wěn)定性.因此,為適應(yīng)不同的場(chǎng)景需求,文中采用了線性可調(diào)節(jié)公平機(jī)制.具體調(diào)節(jié)效果可歸納為

其中,βTFRR為權(quán)衡因子,滿足0≤βTFRR≤1,表示時(shí)間公平與吞吐率公平之間的折中效果,即βTFRR越大,時(shí)間公平效果越明顯;反之,則吞吐率公平效果就越顯著.特別地,當(dāng)βTFRR=1時(shí),系統(tǒng)將采用TFRR隊(duì)列調(diào)度算法實(shí)現(xiàn)完全的時(shí)間公平;而當(dāng)βTFRR=0時(shí),系統(tǒng)則采用基本的RR隊(duì)列調(diào)度算法實(shí)現(xiàn)完全的吞吐率公平.

3　NS-3　仿真

3.1仿真系統(tǒng)構(gòu)建

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

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

將仿真系統(tǒng)設(shè)置為1個(gè)AP和10個(gè)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,對(duì)應(yīng)的穩(wěn)定傳輸速率等效于54 Mbit/s、36 Mbit/s、18 Mbit/s和6 Mbit/s.上層UDP協(xié)議流量采用泊松分布方式產(chǎn)生,而TCP協(xié)議采用了Westwood無線擁塞控制協(xié)議.所有的數(shù)據(jù)幀大小均設(shè)置為1 500 B.針對(duì)FCFS、RR、DTT和TFRR這4種算法,分別仿真了下行UDP、下行TCP以及上行TCP這3種流量場(chǎng)景.

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

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

3.3延時(shí)性能分析

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

圖4　TFRR算法的延時(shí)分布特性

圖5　TFRR算法的線性可調(diào)節(jié)公平

3.4可調(diào)節(jié)公平性

針對(duì)下行TCP仿真場(chǎng)景,線性地調(diào)整權(quán)衡因子βTFRR的大小,并依次統(tǒng)計(jì)系統(tǒng)的吞吐率性能(S)與公平性系數(shù)(Fairness Index,FI)大小,采用Jain公平因子[13]評(píng)估系統(tǒng)的公平系數(shù),結(jié)果如圖5所示.從圖5可明顯地發(fā)現(xiàn),隨著權(quán)衡因子的逐漸遞增,系統(tǒng)的吞吐率性能呈現(xiàn)線性遞增趨勢(shì).這是由于權(quán)衡因子越大,系統(tǒng)的時(shí)間公平性比重越高,有利于提升多速率網(wǎng)絡(luò)的系統(tǒng)吞吐率性能,而公平性系數(shù)與權(quán)衡因子也同樣近似于線性關(guān)系.

3.5移動(dòng)場(chǎng)景

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

圖6　移動(dòng)場(chǎng)景的網(wǎng)絡(luò)拓?fù)?/p>

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

圖7(c)則表明了,AP采用TFRR隊(duì)列調(diào)度算法所獲得的系統(tǒng)吞吐率性能將遠(yuǎn)大于RR算法和DTT算法的,這也體現(xiàn)了TFRR算法在真實(shí)的混合流量環(huán)境下所具有的性能優(yōu)越性.

4　實(shí)測(cè)驗(yàn)證

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

5　結(jié)束語(yǔ)

針對(duì)多速率WLAN網(wǎng)絡(luò)分析了時(shí)間公平條件下的性能優(yōu)越性,筆者提出了線性可調(diào)節(jié)時(shí)間公平的循環(huán)輪詢隊(duì)列調(diào)度算法.該算法不僅利用不同速率站點(diǎn)之間的時(shí)間公平提升系統(tǒng)的吞吐率性能,又兼顧了數(shù)據(jù)幀的傳輸延時(shí)限制.同時(shí),針對(duì)不同的應(yīng)用場(chǎng)景需求,還支持線性可調(diào)節(jié)公平機(jī)制,實(shí)現(xiàn)了吞吐率公平與時(shí)間公平的折中.最后,通過NS-3仿真與硬件系統(tǒng)測(cè)試驗(yàn)證了該算法的有效性與可行性.

[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 網(wǎng)絡(luò)出版時(shí)間：2015-10-21

國(guó)家科技重大專項(xiàng)資助項(xiàng)目(2013ZX03004007);北京市科技新星計(jì)劃資助項(xiàng)目(2010B060)

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

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.046.html