無線網(wǎng)絡(luò)中基于優(yōu)先級隊列延遲限定的研究

盧浩洋，陳世平，2, 王迅登

(1.上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093；2. 上海理工大學(xué) 信息化辦公室，上海 200093)

?

無線網(wǎng)絡(luò)中基于優(yōu)先級隊列延遲限定的研究

盧浩洋1，陳世平1，2, 王迅登1

(1.上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093；2. 上海理工大學(xué) 信息化辦公室，上海 200093)

由于無線網(wǎng)絡(luò)環(huán)境下網(wǎng)絡(luò)節(jié)點的增加，網(wǎng)絡(luò)延時成為一個亟待解決的問題。為了提高服務(wù)質(zhì)量(QoS)，提高吞吐量，文中提出了一種基于優(yōu)先級的隊列延遲模型，通過將每一個包預(yù)設(shè)置優(yōu)先級來區(qū)分其重要性和實時性，同時將每一個AP設(shè)備中的隊列根據(jù)優(yōu)先級劃分為3種類型，并將預(yù)設(shè)優(yōu)先級的包放入其中進(jìn)行傳輸，從而有效減少發(fā)送端的隊列延遲。通過分析和仿真可以發(fā)現(xiàn)，與未劃分優(yōu)先級隊列的節(jié)點網(wǎng)絡(luò)相比，這種方案不僅使單個節(jié)點的延遲大幅減少，也使整個網(wǎng)絡(luò)的平均延遲明顯降低，網(wǎng)絡(luò)整體性能顯著提高。

無線網(wǎng)絡(luò)；隊列延遲；優(yōu)先級；預(yù)設(shè)置；服務(wù)質(zhì)量

隨著無線網(wǎng)絡(luò)的不斷發(fā)展，無線網(wǎng)路環(huán)境中各種業(yè)務(wù)的多樣性對于網(wǎng)絡(luò)延遲是一種挑戰(zhàn)，這種多樣性[1]主要體現(xiàn)在具有實時特性的數(shù)據(jù)包和對實時性要求較低的數(shù)據(jù)包。對于每個AP(AccessPoint)[2]設(shè)備，具有實時特性的數(shù)據(jù)包，通常對網(wǎng)絡(luò)的傳輸時延均有閥值限制要求，還具有數(shù)據(jù)量大，持續(xù)傳輸?shù)忍攸c；對于實時性要求較低的數(shù)據(jù)，通常對于時間還是可以容忍的。對于這兩大類的數(shù)據(jù)傳輸?shù)臋?quán)衡發(fā)送直接關(guān)系到網(wǎng)絡(luò)延時，進(jìn)而影響到用戶體驗的時間。

數(shù)據(jù)包在傳輸過程中，經(jīng)過每個AP逗留的延遲通常包括發(fā)送延遲和隊列延遲。對于發(fā)送延遲，無法準(zhǔn)確控制，但可通過設(shè)計一個有效的隊列調(diào)度算法減少數(shù)據(jù)包在隊列中逗留的延遲。傳統(tǒng)情況下，隊列的調(diào)度機(jī)制一般采用先來先服務(wù)(FIFO)[3]。明顯，這種調(diào)度機(jī)制有失實時性和公平性，為克服上述缺陷，本文提出了一種新的隊列調(diào)度機(jī)制：基于優(yōu)先級的隊列延遲調(diào)度機(jī)制(Delay-basedPriorityQuenueScheduling，DPQS)，進(jìn)而對每一個優(yōu)先級隊列[4]分配權(quán)重值，并分配帶寬值，按照優(yōu)先級的由高到低輪詢每一個優(yōu)先級隊列。

1　相關(guān)研究

為提供QoS[5]保證的策略，一種好的隊列調(diào)度機(jī)制需要考慮以下幾點：(1)在各種數(shù)據(jù)流的傳輸過程中，應(yīng)保證流的公平性；(2)數(shù)據(jù)流之間減少彼此之間的影響，不能影響流與流之間的帶寬分配；(3)若一個流占用的帶寬還有盈余，可允許其他流適當(dāng)占用。

目前，在無線網(wǎng)絡(luò)中使用最多的隊列調(diào)度策略是先來先服務(wù)(FIFO)。

這種隊列實現(xiàn)起來相對較為簡單，調(diào)度也比較方便；最大時延可通過最大隊列的長度來決定，時延的大小與隊列的長度成正比。但這種隊列調(diào)度算法有明顯的弊端：(1)沒有兼顧實時性高和實時性低的分組公平對待；(2)當(dāng)遇到擁塞發(fā)生時，業(yè)務(wù)流的平均排隊時延均會增加，對于任何一種業(yè)務(wù)流的影響均一致，但對于實時性要求高的流不利；(3)隔離性不佳，當(dāng)有一個突發(fā)的業(yè)務(wù)流可能便會占用整個緩存空間，以至于其他的業(yè)務(wù)流均無法進(jìn)入。

2　系統(tǒng)建模

本文DPQS建模過程主要包括前期的預(yù)設(shè)優(yōu)先級，DPQS模型，后期的丟包處理，以及算法設(shè)計的介紹。設(shè)定一種減少數(shù)據(jù)包在AP中逗留延遲的調(diào)度方法，通過在外隊列中篩選數(shù)據(jù)包，子隊列中根據(jù)數(shù)據(jù)包劃分優(yōu)先級的方法來合理調(diào)度數(shù)據(jù)包的發(fā)送，本文不考慮數(shù)據(jù)包在傳輸過程中的延遲和在AP端中的發(fā)送延遲，而只考慮其在隊列中的延遲。

2.1預(yù)設(shè)值優(yōu)先級

通過分析IP版本4[6]的分組首部結(jié)構(gòu)可知:服務(wù)類型字段(TOS)包含8bit，其中還包括一個3bit的優(yōu)先權(quán)子字段，其取值可為000～111，4bit的TOS子字段和1bit未用位。文中可利用這一個未利用的8位字段，將數(shù)據(jù)包最多劃分為8種優(yōu)先級，進(jìn)而能將一個緩沖區(qū)中的子隊列最多劃分8個隊列，如圖1所示。

圖1　TOS字段

當(dāng)包進(jìn)入支持型隊列中的對應(yīng)的優(yōu)先級隊列時，同一優(yōu)先級隊列的包再按照FIFO的順序排列好，等待調(diào)度。

2.2DPQS模型

這里DPQS模型主要采用一種劃分緩沖區(qū)的做法，首先將一個緩沖區(qū)等分的劃分為3個隊列，分別為支持型隊列、非支持型隊列、盡力而為型隊列，當(dāng)一個數(shù)據(jù)包來到中繼節(jié)點時，其會先進(jìn)入支持型隊列，當(dāng)支持型隊列阻塞時，才會調(diào)度數(shù)據(jù)包進(jìn)入非支持型隊列，當(dāng)非支持型隊列阻塞時，會調(diào)度數(shù)據(jù)包進(jìn)入盡力而為型隊列中，若這3個隊列都阻塞，則會丟棄優(yōu)先級最低的數(shù)據(jù)包，并要求發(fā)送端降低發(fā)送速率。在此，支持性隊列的優(yōu)先級大于非支持型隊列，非支持型隊列優(yōu)先級大于盡力而為型隊列，既Priority(Support)>Priority(Unsupport)>Priority(Try)如圖2所示。

圖2　隊列模型

當(dāng)數(shù)據(jù)流通過時，整個數(shù)據(jù)包的調(diào)度大多數(shù)情況下均是在支持型隊列中調(diào)度，當(dāng)支持型隊列發(fā)送阻塞才會用到后續(xù)非支持型隊列和盡力而為型隊列。整個外圍隊列的調(diào)度機(jī)制必須滿足條件：(1)要產(chǎn)生盡可能少的非支持型和盡力而為型隊列數(shù)據(jù)包，爭取能在支持型隊列中全部調(diào)度完畢；(2)若支持型隊列中的數(shù)據(jù)包未發(fā)送完，就不會調(diào)度非支持型；同理，若非支持型隊列中的數(shù)據(jù)包未發(fā)送完，便不會發(fā)送盡力而為型隊列中的數(shù)據(jù)包。

這3個隊列又分別劃分幾個子隊列，這些子隊列均按照優(yōu)先級劃分。子隊列的個數(shù)主要取決于TOS字段中劃分的優(yōu)先級個數(shù)。

子隊列中根據(jù)業(yè)務(wù)應(yīng)用類型對接受到的包分類處理，并將其分別劃分到對應(yīng)的優(yōu)先級隊列中，然后根據(jù)不同的優(yōu)先級，為優(yōu)先級隊列分配對應(yīng)的權(quán)重值；并根據(jù)各優(yōu)先級隊列分配到的權(quán)重值，為各個優(yōu)先級隊列分配相應(yīng)的帶寬。

當(dāng)發(fā)送數(shù)據(jù)包時，按照優(yōu)先級的順序依次輪詢各優(yōu)先級隊列，并根據(jù)各個隊列分配得到的帶寬從對應(yīng)隊列中取出相應(yīng)數(shù)量的數(shù)據(jù)包進(jìn)行調(diào)度。

這樣，該調(diào)度機(jī)制不但能保證高優(yōu)先級的業(yè)務(wù)需求可及時地得到滿足，還具有一定的公平性。當(dāng)服務(wù)不能及時滿足時，可利用降低低優(yōu)先級帶寬和減少低優(yōu)先級需求來保證實時高優(yōu)先級的業(yè)務(wù)的帶寬保證,如圖3所示。

圖3　優(yōu)先級隊列模型

如圖3所示，若劃分的優(yōu)先級隊列只有3個，隊列A中的優(yōu)先級是最高的，故會最先調(diào)度，之后依次調(diào)度隊列B和隊列C中的數(shù)據(jù)包。外隊列的這3種類型均會有這些優(yōu)先級子隊列，但本文希望盡量不要用到非支持型隊列和盡力而為型隊列。

這種優(yōu)先級劃分還會維持一個延遲閥值。每一個子隊列中都會設(shè)置一個閥值T(T>0)，當(dāng)發(fā)現(xiàn)該數(shù)據(jù)包在對應(yīng)的隊列中逗留時間已超過T時，該數(shù)據(jù)包將失效，且優(yōu)先級的大小與延遲閥值的設(shè)定成反比。

區(qū)別于常用的優(yōu)先級調(diào)度算法機(jī)制的特點還有就是當(dāng)數(shù)據(jù)包進(jìn)入支持型隊列時，該數(shù)據(jù)包首先會先在TOS字段中查找屬于自己的優(yōu)先級，本應(yīng)加入對應(yīng)的優(yōu)先級K隊列，當(dāng)發(fā)現(xiàn)高于K優(yōu)先級隊列中不擁擠或數(shù)據(jù)包量較少的情況下，可越級進(jìn)入相應(yīng)高優(yōu)先級隊列，占用高帶寬，發(fā)送更快，節(jié)約延遲。

這樣會產(chǎn)生兩種情況，超過隊長L或小于隊長L。當(dāng)在高優(yōu)先級隊列中混雜著低優(yōu)先級數(shù)據(jù)包時，陸續(xù)進(jìn)來高優(yōu)先級包，若在所有包長總和小于隊長L時，則按照FIFO順序依次傳輸。若包長總和大于L時，就將低優(yōu)先級中的包調(diào)度到對應(yīng)優(yōu)先級隊列中。

若此時包長總和>L時，本該將低優(yōu)先級包調(diào)度對應(yīng)隊列中，但此時低優(yōu)先級包已傳輸一部分，在此用傳輸率P來表示，若P>50%，則將該包繼續(xù)發(fā)送，直至發(fā)送完成；若P<50時，直接將該包丟棄。

當(dāng)支持型隊列中的數(shù)據(jù)包發(fā)生阻塞時，會從優(yōu)先級最低的隊列中調(diào)度數(shù)據(jù)包放到非支持型隊列中。同理，非支持型隊列發(fā)送阻塞時，也會調(diào)用優(yōu)先級最低的隊列中數(shù)據(jù)包，將其放入到盡力而為的隊列中。圖4是數(shù)據(jù)包通過時，調(diào)度的具體流程圖。其中，P(k)表示優(yōu)先級為K的數(shù)據(jù)包；L(support)代表的是支持型隊列中包的長度；RalaxValue是判斷當(dāng)前支持型隊列是否空閑的臨界值；Q(i

圖4　DPQS流程圖

2.3丟包處理

本文沿用有線網(wǎng)絡(luò)中常用的基于RED擁塞避免策略，RED[7]算法常用于路由器的隊列管理中，從而控制緩存空間的長度。之所以將其應(yīng)用到無線網(wǎng)絡(luò)中，是為了采用擁塞度門限值來進(jìn)行擁塞調(diào)節(jié)。通過丟棄分組或通知源節(jié)點降低發(fā)送速率的方法，保證隊列長度不超過對應(yīng)的門限值，如圖5所示。

圖5　RED算法丟棄函數(shù)

該RED函數(shù)橫坐標(biāo)K代表的是平均長度，縱坐標(biāo)P代表的是分組丟棄概率。該RED算法在計算平均對長K時，采用了類似低通濾波器帶權(quán)值的方法

K=(1-η)×K+η×q

其中，η為權(quán)值，相當(dāng)于低通濾波器的時間常數(shù)；q為采樣測量時實際隊列的長度。

本文通過引入RED算法門限值，設(shè)定了兩個關(guān)于擁塞程度的門限值K1和K2。當(dāng)支持型隊列接受分組時產(chǎn)生的擁塞度值K1且K2時，則根據(jù)分組中已設(shè)定好的優(yōu)先級，對優(yōu)先級最低的分組進(jìn)行丟棄。

3　仿真實驗

模擬仿真實驗采用Matlab[8]軟件進(jìn)行，仿真運行平臺為Pentium(R)Dual-CoreCPU，內(nèi)存4GB。通過與FIFO隊列的性能進(jìn)行比較，評估DPQS隊列的性能指標(biāo)。本文著重評估了整個隊列系統(tǒng)的吞吐量以及在隊列中逗留的延遲性能進(jìn)行分析比對。

實驗1驗證兩種隊列調(diào)度模型對吞吐量的影響，對FIFO模型和DPQS兩種模型的網(wǎng)絡(luò)吞吐量進(jìn)行了研究，所得實驗結(jié)果如圖6所示。

圖6　網(wǎng)絡(luò)吞吐量

實驗結(jié)果分析：根據(jù)圖中所示的信息可得出，DPQS模型的吞吐量始終處于一個較高的狀態(tài)，且趨于穩(wěn)定，但FIFO模型的吞吐量總體上呈現(xiàn)出遞減趨勢，且并不穩(wěn)定?？梢钥闯?，DPQS在網(wǎng)絡(luò)吞吐量上明顯占用優(yōu)勢，而總體提高了QoS。

實驗2驗證兩種隊列所產(chǎn)生的延遲比較。對FIFO模型和DPQS兩種調(diào)度模型的隊列延遲進(jìn)行了研究比較，所得到的實驗結(jié)果如圖7所示。

圖7　數(shù)據(jù)包在隊列中的延遲

通過圖7所示的結(jié)果可看出，每個AP節(jié)點的延遲時間均有著明顯的變化，相對于FIFO隊列模型，DPQS模型的隊列延遲始終處于一個較低的水平，延

遲改善的主要原因在于對數(shù)據(jù)流進(jìn)行了優(yōu)先級劃分，區(qū)分了業(yè)務(wù)類型，有針對性地調(diào)度策略，較好的解決了傳輸次序的合理性。

4　結(jié)束語

本文提出了一種較為新穎的基于優(yōu)先級的隊列調(diào)度模型，通過預(yù)設(shè)值優(yōu)先級的方式區(qū)分業(yè)務(wù)類型，再將整個AP隊列緩沖區(qū)劃分為3種隊列模型，在子隊列中根據(jù)預(yù)設(shè)優(yōu)先級劃分優(yōu)先級隊列的方式來調(diào)度傳遞過來的數(shù)據(jù)包。并配置RED丟包處理機(jī)制來有效地處理廢棄數(shù)據(jù)包，再通過M1+M2/M/1/L[9]來分析兩種模型的合理性，驗證DPQS模型的可行性。最后，通過模擬仿真實驗來證明該模型具有一定的擴(kuò)展性，降低了隊列時延，提高了網(wǎng)絡(luò)系統(tǒng)的吞吐量，網(wǎng)絡(luò)整體性能也得到顯著提高。

[1]AshourM,Le-NgocT.End-to-enddelaymarginbalancingapproachforroutinginmulti-classnetworks[J].WirelessNetworks, 2007, 13(3):311-322.

[2]徐浩.無線網(wǎng)絡(luò)傳統(tǒng)AP與現(xiàn)代AP性能探討[J].價值工程,2013(28):238-239.

[3]印紅云,王志良,王莉.網(wǎng)絡(luò)中常用的隊列管理方法比較[J].微計算機(jī)信息,2005(11):3-4.

[4]周鵬,郝明,唐政,等.基于QoS的優(yōu)先級隊列調(diào)度算法[J].電子科技,2013,26(5):122-124.

[5]Charikarm,NaorJ,SchieberB.ResourceoptimizationinQoSmulticastroutingofreal-timemultimedia[J].IEEE/ACMTransactionsonNetworking, 2004, 12(2):340-348

[6]沈慶偉,張霖.基于隧道的IPv4/IPv6過渡技術(shù)分析[J].計算機(jī)技術(shù)與發(fā)展,2007,17(5):170-172,176.

[7]FloydS,JacobsonV.Randomearlydetectiongatewaysforcongestionavoidance[J].IEEE/ACMTransactionsonNetworking,1993,1(4):397-413.

[8]李柏年,吳禮斌.Matlab數(shù)據(jù)分析方法[M].北京:機(jī)械工業(yè)出版社,2012.

[9]KronerH,HebuterneG,BoyerP,etal.PrioritymanagementinATMswitchingnodes[J].IEEEJournalonSelectedAreasinCommunications, 1991, 9(3):418-427.

Research on Wireless Network Transmission Side Defining Priority-based Queuing Delay

LUHaoyang1,CHENShiping1,2,WANGXundeng1

(1.SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China;2.InformationOffice,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

Wirelessnetworkstechnologyhasbroadprospectsintoday'ssociety.Withtheincreaseinwirelessnetworknodes,networklatencyhasbecomeanimportantproblemtobesolved.Inordertoprovidequalityofservice(QoS)andincreasethroughput,weproposeamodelbasedonpriorityqueuingdelayofeachpacketbypre-settingprioritiestodistinguishtheirimportanceandtimeliness,whileeachoftheAPaccordingtothepriorityqueueisdividedintothreetypes,andthedefaultprioritypacketsintowhichtransmission,thuseffectivelyreducingthesenderqueuingdelays.Simulationshowsthatcomparedtonon-prioritizedqueueofnodesinthenetwork,thisprogramgreatlyreducesboththedelayofasinglenodeandtheaveragedelayacrossthenetwork,thusasignificantlyimprovedoverallnetworkperformance.

wirelessnetworks;queuingdelay;priority;pre-setting;QoS

2015- 12- 17

國家自然科學(xué)基金資助項目(61170277；61472256)；上海市教委科研創(chuàng)新重點基金資助項目(12zz137)；上海市一流學(xué)科建設(shè)基金資助項目(S1201YLXK)。

盧浩洋(1991-)，男，碩士研究生。研究方向：計算機(jī)網(wǎng)絡(luò)等。陳世平(1964-)，男，教授，博士生導(dǎo)師。研究方向：計算機(jī)網(wǎng)絡(luò)等。王迅登(1990-)，男，碩士研究生。研究方向：計算機(jī)網(wǎng)絡(luò)等。

10.16180/j.cnki.issn1007-7820.2016.09.012

TN929

A

1007-7820(2016)09-041-04