蔣文賢,許曉璐
(華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建廈門361021)
IEEE802.16網(wǎng)絡(luò)動(dòng)態(tài)自適應(yīng)區(qū)分服務(wù)算法
蔣文賢,許曉璐
(華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建廈門361021)
針對(duì)IEEE802.16MAC協(xié)議中的調(diào)度機(jī)制不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題,提出了一種基于服務(wù)類別優(yōu)先級(jí)的鏈路帶寬自適應(yīng)分配調(diào)度PDA?DFPQ算法。該算法分為兩級(jí)調(diào)度架構(gòu),第一級(jí)是不同業(yè)務(wù)間的調(diào)度,采用服務(wù)質(zhì)量?jī)?yōu)先級(jí)策略,高優(yōu)先級(jí)服務(wù)類分配合適的帶寬,以保障實(shí)時(shí)業(yè)務(wù)對(duì)最大時(shí)延限定的要求;第二級(jí)是同種業(yè)務(wù)內(nèi)的調(diào)度,采用自適應(yīng)調(diào)整機(jī)制,根據(jù)隊(duì)列長(zhǎng)度和分組數(shù)動(dòng)態(tài)設(shè)置權(quán)值系數(shù),以保障不同用戶對(duì)公平性和非實(shí)時(shí)業(yè)務(wù)對(duì)吞吐量的要求。仿真結(jié)果表明:與DRR和RED?DFPQ算法相比較,改進(jìn)的一級(jí)調(diào)度算法能降低時(shí)延,解決實(shí)時(shí)性問題;改進(jìn)的二級(jí)調(diào)度算法能均衡用戶速率,提高網(wǎng)絡(luò)吞吐量和公平性,解決突發(fā)性問題。
無線網(wǎng)絡(luò);IEEE802.16;帶寬調(diào)度;自適應(yīng);區(qū)分服務(wù)
IEEE802.16[1]MAC(media access control,MAC)協(xié)議提供了主動(dòng)授予服務(wù)(unsolicited grant service,UGS)、實(shí)時(shí)輪詢服務(wù)(real?time polling service,rtPS)、拓展實(shí)時(shí)輪詢服務(wù)(extended real?time polling service,ertPS)、非實(shí)時(shí)輪詢服務(wù)(non?real?time polling Service,nrtPS)和盡力而為服務(wù)(best effort,BE)等5種不同服務(wù)類型的服務(wù)質(zhì)量(quality of service,QoS),但沒有提出保障QoS的具體實(shí)現(xiàn)方案和區(qū)分服務(wù)算法,而有效的上行鏈路和下行鏈路帶寬調(diào)度算法對(duì)QoS的保證具有重要意義。
文獻(xiàn)[2]提出了一種二級(jí)調(diào)度機(jī)制,第一級(jí)調(diào)度使用虧空公平優(yōu)先級(jí)隊(duì)列(deficit fair priority queue,DFPQ)算法。該算法定義了虧空計(jì)數(shù)器(deficit counter,DC),一旦某隊(duì)列的首個(gè)分組長(zhǎng)度大于DC值就終止對(duì)該隊(duì)列的服務(wù);而不同的業(yè)務(wù)在第二級(jí)調(diào)度中使用各自的調(diào)度算法;文獻(xiàn)[3]提出了基于隨機(jī)早期檢測(cè)(random early detection,RED)的DPFQ算法,針對(duì)高優(yōu)先級(jí)業(yè)務(wù)負(fù)載較高時(shí)無法保證低優(yōu)先級(jí)業(yè)務(wù)的QoS問題對(duì)DFPQ算法進(jìn)行改進(jìn),設(shè)計(jì)了動(dòng)態(tài)變化的DC值;文獻(xiàn)[4]為保證各種多媒體QoS,提出了一種基于正交頻分多址接入技術(shù)和自適應(yīng)調(diào)制編碼機(jī)制的二級(jí)調(diào)度方案;文獻(xiàn)[5]提出了一種移動(dòng)IEEE802.16的跨層主動(dòng)隊(duì)列管理方案,利用傳輸層的窗口變化信息,改善上行終端的丟棄率等特性,提高了上行鏈路的性能;文獻(xiàn)[6]提出一種基于傳輸速率自適應(yīng)的動(dòng)態(tài)分配算法,并采用一個(gè)動(dòng)態(tài)優(yōu)化的迭代算法自適應(yīng)調(diào)節(jié)用戶的傳輸速率來得到最優(yōu)的帶寬重分配矩陣,以此最大化無線網(wǎng)絡(luò)的效用函數(shù);文獻(xiàn)[7]提出一個(gè)基于學(xué)習(xí)自動(dòng)機(jī)的IEEE802.16上行鏈路的實(shí)時(shí)多媒體業(yè)務(wù)調(diào)度算法;文獻(xiàn)[8]提出了一種用于移動(dòng)IEEE802.16上行鏈路流量的高效帶寬分配算法,使用智能系統(tǒng)方法,設(shè)計(jì)了自適應(yīng)的基于期限的方案,為實(shí)時(shí)應(yīng)用保證特定的最大時(shí)延要求;文獻(xiàn)[9]從數(shù)據(jù)調(diào)度競(jìng)爭(zhēng)的角度出發(fā),提出了一種節(jié)能的實(shí)時(shí)業(yè)務(wù)數(shù)據(jù)調(diào)度算法;文獻(xiàn)[10]提出了效用最大化的IEEE802.16帶寬分配算法和快速解法,可靈活地改變效用函數(shù)參數(shù),在不同服務(wù)質(zhì)量要求下高效地做出分配。以上算法雖然在某些方面提高了性能,但沒有較好解決時(shí)延、吞吐量和公平性之間的平衡。
根據(jù)現(xiàn)有文獻(xiàn)對(duì)IEEE802.16調(diào)度機(jī)制的研究,針對(duì)其不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題,將分層設(shè)計(jì)和自適應(yīng)控制的思想引入到QoS調(diào)度機(jī)制中,提出了一種基于服務(wù)類別優(yōu)先級(jí)的鏈路帶寬自適應(yīng)分配調(diào)度算法PDA?DFPQ。
該算法分為兩級(jí)調(diào)度架構(gòu),第一級(jí)是不同業(yè)務(wù)間的調(diào)度,采用服務(wù)質(zhì)量?jī)?yōu)先級(jí)策略,高優(yōu)先級(jí)服務(wù)類分配合適的帶寬,以保障實(shí)時(shí)業(yè)務(wù)對(duì)最大時(shí)延限定的要求,解決實(shí)時(shí)性問題;第二級(jí)是同種業(yè)務(wù)內(nèi)的調(diào)度,采用自適應(yīng)調(diào)整機(jī)制,根據(jù)隊(duì)列長(zhǎng)度和分組數(shù)動(dòng)態(tài)設(shè)置權(quán)值系數(shù),以保障不同用戶對(duì)公平性和非實(shí)時(shí)業(yè)務(wù)對(duì)吞吐量的要求,解決突發(fā)性問題??傮w調(diào)度框架圖如圖1所示。
圖1 IEEE802.16總體調(diào)度框架設(shè)計(jì)圖Fig.1 IEEE802.16 overall scheduling framework design
1.1 基于優(yōu)先級(jí)策略的第一級(jí)調(diào)度設(shè)計(jì)
第一級(jí)調(diào)度也稱為類間調(diào)度,是指各種不同類型的業(yè)務(wù)流所在隊(duì)列的調(diào)度服務(wù)。用戶站(subscribe sta?tion,SS)到基站(base station,BS)的連接將分配一種服務(wù)類型,BS針對(duì)每 個(gè)服務(wù)類別都建立與之相應(yīng)的調(diào)度隊(duì)列,每個(gè)隊(duì)列有一組與之相關(guān)聯(lián)的各自不同的QoS需求參數(shù)。
由于UGS服務(wù)類型的分組是以恒定速率和固定大小進(jìn)行傳輸?shù)?,在IEEE802.16系統(tǒng)中,BS以主動(dòng)授權(quán)方式為其分配帶寬,因而UGS業(yè)務(wù)無需進(jìn)入第一級(jí)調(diào)度。余下rtPS、ertPS、nrtPS和BE4種類型業(yè)務(wù)進(jìn)入第一級(jí)調(diào)度,采用服務(wù)類型優(yōu)先級(jí)算法。同類分組具備相同的QoS要求,隊(duì)頭分組的QoS優(yōu)先級(jí)函數(shù)值大小決定分組的順序,取值最大的分組將獲得優(yōu)先調(diào)度的權(quán)利。如圖2所示。
圖2 鏈路帶寬分配過程Fig.2 The link bandwidth allocation process
1.2 基于動(dòng)態(tài)自適應(yīng)的第二級(jí)調(diào)度設(shè)計(jì)
第二級(jí)調(diào)度也稱為類內(nèi)調(diào)度,指各個(gè)相同類型的業(yè)務(wù)流間的調(diào)度。在IEEE802.16中提供QoS的基本思想:將帶有某個(gè)特定連接標(biāo)識(shí)符(connection identifi?er,CID)標(biāo)識(shí)的服務(wù)流,與來自MAC層接口的分組數(shù)據(jù)相關(guān)聯(lián)。如圖3所示。
1)UGS業(yè)務(wù)。
為有效保障UGS各業(yè)務(wù)流間的公平性,采用先進(jìn)先出(first in first out,F(xiàn)IFO)方式,同時(shí)滿足了業(yè)務(wù)流對(duì)時(shí)延、速率等方面的要求,而不受到其他條件的制約。
2)rtPS和ertPS業(yè)務(wù)。
rtPS及ertPS業(yè)務(wù)流均屬于可變大小且大小不固定的分組,若分組時(shí)延超過一定要求會(huì)被丟棄,進(jìn)而影響到用戶的感知,因此必須保證這2類業(yè)務(wù)的時(shí)延要求,這里選用基于改進(jìn)的PDA?DFPQ算法。
3)nrtPS業(yè)務(wù)。
nrtPS業(yè)務(wù)支持非實(shí)時(shí)且不定期的大小可變的分組,時(shí)延上是沒有明確限制,但對(duì)最大持續(xù)傳輸速率、最小預(yù)留業(yè)務(wù)速率有要求,采用加權(quán)輪詢(weighted round robin,WRR)算法進(jìn)行調(diào)度,通過權(quán)重系數(shù)設(shè)定業(yè)務(wù)隊(duì)列服務(wù)時(shí)間,高優(yōu)先級(jí)隊(duì)列具有優(yōu)先權(quán)。加權(quán)值表示獲取資源的比重,權(quán)重采用的公式:Wi=其中pi為優(yōu)先級(jí)參數(shù)折算后的系數(shù),ri為帶寬速率的差值。
4)BE業(yè)務(wù)。
對(duì)于BE業(yè)務(wù),由于沒有對(duì)QoS嚴(yán)格的要求,考慮到多用戶間BE業(yè)務(wù)流的公平性,因此采用輪詢(round robin,RR)調(diào)度算法,為每個(gè)BE流提供相同的機(jī)會(huì)傳輸分組,即每次調(diào)度執(zhí)行i=(i+1)mod n,并選出第i用戶進(jìn)行調(diào)度。
2.1 實(shí)驗(yàn)參數(shù)設(shè)置
系統(tǒng)是基于單個(gè)BS,在TDMA訪問模式下使用點(diǎn)對(duì)多點(diǎn)(point to multipoint,PMP)方式執(zhí)行,多個(gè)SS終端隨機(jī)分布在3 km半徑范圍內(nèi),部署3臺(tái)服務(wù)器,其中流媒體服務(wù)器主要是處理rtPS和ertPS業(yè)務(wù)、FTP服務(wù)器主要是處理nrtPS業(yè)務(wù)、Web服務(wù)器主要是處理BE業(yè)務(wù),仿真的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4所示。
算法仿真在OPNET環(huán)境中實(shí)現(xiàn),參數(shù)設(shè)置主要包括Config模塊、Application模塊和Profiles模塊,由于IEEE802.16網(wǎng)絡(luò)業(yè)務(wù)流具有自相似特性,利用Pareto ON/OFF仿真業(yè)務(wù)源,到達(dá)率為λ,ON期間服從Pareto分布,OFF期間服從泊松分布。
2.2 第一級(jí)調(diào)度仿真
對(duì)提出的PDA?DFPQ算法和傳統(tǒng)的虧空輪詢(defi?cit round robin,DRR)算法和RED?DFPQ算法在平均時(shí)延的性能進(jìn)行對(duì)比;對(duì)5種業(yè)務(wù)進(jìn)行仿真,SS數(shù)量從5個(gè)逐步增加到50個(gè),仿真結(jié)果如圖5和圖6所示。圖5顯示了3種調(diào)度算法在不同SS數(shù)量下的平均隊(duì)列時(shí)延。其中PDA?DFPQ算法的時(shí)延最小,主要是其服務(wù)類別優(yōu)先級(jí)最高,減少了數(shù)據(jù)包隊(duì)列時(shí)延,因此,實(shí)時(shí)流量可在規(guī)定的時(shí)延約束下完成。而且隨著SS數(shù)目的增加,PDA?DFPQ中隊(duì)列時(shí)延的曲線變得平緩,這表明可滿足不同時(shí)延的要求,算法趨于平穩(wěn)。每個(gè)服務(wù)類別隊(duì)列獲取了合適的帶寬,使每個(gè)請(qǐng)求在其時(shí)限約束內(nèi)都可達(dá)到所需的數(shù)據(jù),可以認(rèn)為實(shí)現(xiàn)了調(diào)度算法中的公平性。而DRR和RED?DFPQ在SS數(shù)量較多時(shí),平均隊(duì)列時(shí)延急劇增長(zhǎng),原因是簡(jiǎn)單對(duì)各種業(yè)務(wù)的輪循或加權(quán)輪循,未考慮每個(gè)隊(duì)列的實(shí)際帶寬請(qǐng)求。
圖3 調(diào)度算法流程圖Fig.3 Scheduling algorithm flow chart
圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.4 Typical network topology
圖5 隊(duì)列平均時(shí)延對(duì)比Fig.5 Comparion of queue average delay
圖6 顯示了PDA?DFPQ實(shí)現(xiàn)的各種服務(wù)類別的平均時(shí)延。
圖6 服務(wù)類別平均時(shí)延Fig.6 The average delay in service classes
可以看出UGS服務(wù)類別的時(shí)延最小,這是因?yàn)檎{(diào)度算法除了給UGS固定帶寬,還授予更高的權(quán)限。相比之下,當(dāng)SS的數(shù)量增加時(shí),BE和nrtPS數(shù)據(jù)包經(jīng)歷的時(shí)延增加了,這是因?yàn)檩^多幀時(shí)隙去滿足rtPS等實(shí)時(shí)流量需要。但BE業(yè)務(wù)時(shí)延也有一定的期限保障,這是因?yàn)檎{(diào)度算法也為非實(shí)時(shí)應(yīng)用保證了最小的預(yù)留速率。另一方面,ertPS和rtPS數(shù)據(jù)包時(shí)延相對(duì)較小,主要是PDA?DFPQ可以維持最大時(shí)延,為其相應(yīng)的服務(wù)請(qǐng)求區(qū)分保證公平性。
2.3 第二級(jí)調(diào)度仿真
第二級(jí)調(diào)度方案主要對(duì)rtPS業(yè)務(wù)和BE業(yè)務(wù)進(jìn)行仿真,其中rtPS代表了實(shí)時(shí)流量,BE優(yōu)先級(jí)最低。
圖7和圖8分別對(duì)比了3種調(diào)度算法在rtPS和BE業(yè)務(wù)這2種服務(wù)類別吞吐量。很顯然,用于rtPS業(yè)務(wù)的吞吐量比BE高,因?yàn)檎{(diào)度算法的優(yōu)先級(jí)是給實(shí)時(shí)業(yè)務(wù)的,分配更多的帶寬給rtPS流。相應(yīng)地,rtPS業(yè)務(wù)的時(shí)延也較小。
圖7 服務(wù)類別平均時(shí)延Fig.7 The average delay in service classes
圖8 服務(wù)類別平均時(shí)延Fig.8 The average delay in service classes
雖然BE業(yè)務(wù)的時(shí)延受到一定的影響,但仍在可以接受的范圍內(nèi)。PDA?DFPQ算法下的rtPS業(yè)務(wù)吞吐量總體高于DRR和RED?DFPQ算法下的吞吐量,這是因?yàn)镻DA?DFPQ算法采用自適應(yīng)調(diào)整機(jī)制,動(dòng)態(tài)分配不同的權(quán)值系數(shù),允許長(zhǎng)度更大的分組得到更高的服務(wù)機(jī)會(huì),網(wǎng)絡(luò)中傳輸?shù)姆纸M數(shù)量較多,更好地保障了分組調(diào)度情況;而對(duì)比DRR、RED?DFPQ算法,PDA?DF?PQ算法中BE的吞吐量保持在特定最小預(yù)留速率下,這是因?yàn)镻DA?DFPQ賦予了rtPS隊(duì)列足夠的帶寬,使得當(dāng)rtPS在其時(shí)限到期前,有足夠的時(shí)間讓調(diào)度算法能夠優(yōu)先服務(wù)BE業(yè)務(wù)。
圖9顯示了PDA?DFPQ、RED?DFPQ和DRR公平性的對(duì)比。可以看出,DRR公平性隨著流量負(fù)載的增加而惡化,因?yàn)樗鼮閷?shí)時(shí)業(yè)務(wù)賦予了高優(yōu)先級(jí),當(dāng)實(shí)時(shí)業(yè)務(wù)SS連接時(shí),非實(shí)時(shí)業(yè)務(wù)則趨向于餓死。另一方面,當(dāng)系統(tǒng)負(fù)載低于30個(gè)SS時(shí),DRR顯示出公平性方面的穩(wěn)定,這是因?yàn)樗鼮閷?shí)時(shí)業(yè)務(wù)采用了額外的隊(duì)列。但當(dāng)系統(tǒng)負(fù)載超過40個(gè)SS時(shí),這些額外的隊(duì)列為非實(shí)時(shí)業(yè)務(wù)而得不到帶寬。這是因?yàn)榉菍?shí)時(shí)業(yè)務(wù)進(jìn)行很長(zhǎng)時(shí)間,而DC沒有服務(wù)完實(shí)時(shí)服務(wù)類別的隊(duì)列。相比之下,即使當(dāng)SS為50個(gè)時(shí),PDA?DFPQ的公平性也比RED?DFPQ和DRR要好。
圖9 服務(wù)類別平均時(shí)延Fig.9 The average delay in service classes
因此,可以得出,在可接受范圍內(nèi)犧牲非實(shí)時(shí)業(yè)務(wù)的吞吐量性能以換取實(shí)時(shí)業(yè)務(wù)的吞吐量?jī)?yōu)化,更好地保證了實(shí)時(shí)業(yè)務(wù)的QoS要求。
針對(duì)IEEE802.16中MAC協(xié)議的調(diào)度機(jī)制不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題,引入分層設(shè)計(jì)和自適應(yīng)控制的思想,提出了一種基于服務(wù)類別優(yōu)先級(jí)鏈路帶寬自適應(yīng)分配調(diào)度算法,仿真結(jié)果表明該算法不僅能降低時(shí)延,保障實(shí)時(shí)業(yè)務(wù)的要求,而且能均衡各類型業(yè)務(wù)性能,提高網(wǎng)絡(luò)吞吐量和公平性,具有較強(qiáng)的網(wǎng)絡(luò)自適應(yīng)能力。在后續(xù)的工作中,將考慮不同路由策略下的無線網(wǎng)絡(luò)QoS性能,從而增強(qiáng)算法的普適性。
[1]PITIC R,SERRELLI F,REDANA S,et al.Performance e?valuation of utility?based scheduling schemes with QoS guar?antees in IEEE 802.16/WiMAX systems[J].Wireless Com?munications and Mobile Computing,2010,10(7):912?931.
[2]SAFA H,ARTAIL H,KARAM M,et al.New scheduling architecture for IEEE802.16 wireless metropolitan area net?work[C]//Computer Systems and Applications,(AICCSA' 07.IEEE/ACS International Conference).[S.l.],2007:203?210.
[3]TING P C,YU C Y,CHILAMKURTI N,et al.A proposed RED?based scheduling scheme for QoS in WiMAX networks[C]//Wireless Pervasive Computing,(ISWPC 2009.4th International Symposium).[S.l.],2009:1?5.
[4]陳婷,李建東,鐘紹波等.一種面向公平保證QoS的WiMAX二級(jí)調(diào)度方案[J].計(jì)算機(jī)研究與發(fā)展,2009,46(7):1094?1101.
CHEN Ting,LI Jiandong,ZHONG Shaobo,et al.A fair?ori?ented two?level scheduling scheme for QoS guarantee in WiMAX[J].Journal of Computer Research and Develop?ment,2009,46(7):1094?1101.
[5]SADRI Y,KHANMOHAMMADI S.A QoS aware dynamic scheduling scheme using fuzzy inference system for IEEE 802.16 networks[J].Wireless Personal Communications,2013,72(4):2107?2125.
[6]陳賡,夏瑋瑋,沈連豐.基于傳輸速率自適應(yīng)的動(dòng)態(tài)帶寬分配算法[J].通信學(xué)報(bào),2014,35(5):25?32.
CHEN Geng,XIA Weiwei,SHEN Lianfeng.Dynamic band?width allocation algorithm based on transmission rate adapta?tion[J].Journal on Communications,2014,35(5):25?32.
[7]MISRA S,BANERJEE B,WOLFINGER B E.A learning automata?based uplink scheduler for supporting real?time multimedia interactive traffic in IEEE802.16 WiMAX net?works[J].Computer Communications,2012,35(15):1871?1881.
[8]ALSAHAG A M,ALI B M,NOORDIN N K,et al.Fair up?link bandwidth allocation and latency guarantee for mobile WiMAX using fuzzy adaptive deficit round robin[J].Journal of Network and Computer Applications,2014,39(3):17?25.
[9]IYENGAR R,SIKDAR B.A queueing model for polled serv?ice in WiMAX/IEEE802.16 networks[J].IEEE Transac?tions on Communications,2012,60(7):1777?1781.
[10]聶偉.WiMAX無線網(wǎng)絡(luò)QoS測(cè)量及優(yōu)化研究[D].成都:電子科技大學(xué),2011:101?112.
NIE Wei.Research on QoS measurement and optimization in WiMAX wireless communication networks[D].Cheng?du:University of Electronic Science and Technology of Chi?na,2011:101?112.
Algorithm for IEEE802.16 network dynamic adaptive differentiated services
JIANG Wenxian,XU Xiaolu
(College of Computer Science and Technology,Huaqiao University,Xiamen 361021,China)
Considering that IEEE802.16 MAC protocol scheduling mechanism cannot provide streaming media traffic of differentiated services,a link bandwidth adaptive allocation scheduling algorithm based on service class priority and PDA?DFPQ is proposed.The first level is scheduling between different services,using the priority strategy for quality of service,which allocates proper bandwidth for high service class,so as to ensure real?time services to the maximum delay limit requirements.The second level is scheduling of the same kind of services,using an adaptive adjustment mechanism,it dynamically sets the weight coefficients according to the queue length and the number of packets to ensure the requirements of different users for fairness and non?real time services for throughput.The sim?ulation results indicated that compared with the DRR and RED?DFPQ algorithm,the improved first level scheduling algorithm can reduce the delay and solve the real?time scheduling problem.The improved second level scheduling algorithm can balance the user rate,increase the network throughput and fairness,and thus solve sudden problems.Keywords:wireless networks;IEEE802.16;bandwidth scheduling;adaption;differentiated services
10.3969/j.issn.1006?7043.201309060
http://www.cnki.net/kcms/doi/10.3969/j.issn.1006?7043.201309060.html
TP393.01
A
1006?7043(2015)02?0186?05
2013?09?17.網(wǎng)絡(luò)出版時(shí)間:2014?11?27.
國(guó)家自然科學(xué)基金資助項(xiàng)目(61302094);福建省科技計(jì)劃重點(diǎn)資助項(xiàng)目(2014H0030);泉州市科技計(jì)劃重點(diǎn)資助項(xiàng)目(2014Z102).
蔣文賢(1974?),男,副教授.
蔣文賢,E?mail:jwx@hqu.edu.cn.