蔣文賢，許曉璐

（華僑大學計算機科學與技術(shù)學院，福建廈門361021）

IEEE802.16網(wǎng)絡(luò)動態(tài)自適應(yīng)區(qū)分服務(wù)算法

蔣文賢，許曉璐

（華僑大學計算機科學與技術(shù)學院，福建廈門361021）

針對IEEE802.16MAC協(xié)議中的調(diào)度機制不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題，提出了一種基于服務(wù)類別優(yōu)先級的鏈路帶寬自適應(yīng)分配調(diào)度PDA?DFPQ算法。該算法分為兩級調(diào)度架構(gòu)，第一級是不同業(yè)務(wù)間的調(diào)度，采用服務(wù)質(zhì)量優(yōu)先級策略，高優(yōu)先級服務(wù)類分配合適的帶寬，以保障實時業(yè)務(wù)對最大時延限定的要求；第二級是同種業(yè)務(wù)內(nèi)的調(diào)度，采用自適應(yīng)調(diào)整機制，根據(jù)隊列長度和分組數(shù)動態(tài)設(shè)置權(quán)值系數(shù)，以保障不同用戶對公平性和非實時業(yè)務(wù)對吞吐量的要求。仿真結(jié)果表明：與DRR和RED?DFPQ算法相比較，改進的一級調(diào)度算法能降低時延，解決實時性問題；改進的二級調(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é)議提供了主動授予服務(wù)（unsolicited grant service，UGS）、實時輪詢服務(wù)（real?time polling service，rtPS）、拓展實時輪詢服務(wù)（extended real?time polling service，ertPS）、非實時輪詢服務(wù)（non?real?time polling Service，nrtPS）和盡力而為服務(wù)（best effort，BE）等5種不同服務(wù)類型的服務(wù)質(zhì)量（quality of service，QoS），但沒有提出保障QoS的具體實現(xiàn)方案和區(qū)分服務(wù)算法，而有效的上行鏈路和下行鏈路帶寬調(diào)度算法對QoS的保證具有重要意義。

文獻［2］提出了一種二級調(diào)度機制，第一級調(diào)度使用虧空公平優(yōu)先級隊列（deficit fair priority queue，DFPQ）算法。該算法定義了虧空計數(shù)器（deficit counter，DC），一旦某隊列的首個分組長度大于DC值就終止對該隊列的服務(wù)；而不同的業(yè)務(wù)在第二級調(diào)度中使用各自的調(diào)度算法；文獻［3］提出了基于隨機早期檢測（random early detection，RED）的DPFQ算法，針對高優(yōu)先級業(yè)務(wù)負載較高時無法保證低優(yōu)先級業(yè)務(wù)的QoS問題對DFPQ算法進行改進，設(shè)計了動態(tài)變化的DC值；文獻［4］為保證各種多媒體QoS，提出了一種基于正交頻分多址接入技術(shù)和自適應(yīng)調(diào)制編碼機制的二級調(diào)度方案；文獻［5］提出了一種移動IEEE802.16的跨層主動隊列管理方案，利用傳輸層的窗口變化信息，改善上行終端的丟棄率等特性，提高了上行鏈路的性能；文獻［6］提出一種基于傳輸速率自適應(yīng)的動態(tài)分配算法，并采用一個動態(tài)優(yōu)化的迭代算法自適應(yīng)調(diào)節(jié)用戶的傳輸速率來得到最優(yōu)的帶寬重分配矩陣，以此最大化無線網(wǎng)絡(luò)的效用函數(shù)；文獻［7］提出一個基于學習自動機的IEEE802.16上行鏈路的實時多媒體業(yè)務(wù)調(diào)度算法；文獻［8］提出了一種用于移動IEEE802.16上行鏈路流量的高效帶寬分配算法，使用智能系統(tǒng)方法，設(shè)計了自適應(yīng)的基于期限的方案，為實時應(yīng)用保證特定的最大時延要求；文獻［9］從數(shù)據(jù)調(diào)度競爭的角度出發(fā)，提出了一種節(jié)能的實時業(yè)務(wù)數(shù)據(jù)調(diào)度算法；文獻［10］提出了效用最大化的IEEE802.16帶寬分配算法和快速解法，可靈活地改變效用函數(shù)參數(shù)，在不同服務(wù)質(zhì)量要求下高效地做出分配。以上算法雖然在某些方面提高了性能，但沒有較好解決時延、吞吐量和公平性之間的平衡。

根據(jù)現(xiàn)有文獻對IEEE802.16調(diào)度機制的研究，針對其不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題，將分層設(shè)計和自適應(yīng)控制的思想引入到QoS調(diào)度機制中，提出了一種基于服務(wù)類別優(yōu)先級的鏈路帶寬自適應(yīng)分配調(diào)度算法PDA?DFPQ。

1 調(diào)度服務(wù)算法

該算法分為兩級調(diào)度架構(gòu)，第一級是不同業(yè)務(wù)間的調(diào)度，采用服務(wù)質(zhì)量優(yōu)先級策略，高優(yōu)先級服務(wù)類分配合適的帶寬，以保障實時業(yè)務(wù)對最大時延限定的要求，解決實時性問題；第二級是同種業(yè)務(wù)內(nèi)的調(diào)度，采用自適應(yīng)調(diào)整機制，根據(jù)隊列長度和分組數(shù)動態(tài)設(shè)置權(quán)值系數(shù)，以保障不同用戶對公平性和非實時業(yè)務(wù)對吞吐量的要求，解決突發(fā)性問題。總體調(diào)度框架圖如圖1所示。

圖1 IEEE802.16總體調(diào)度框架設(shè)計圖Fig.1 IEEE802.16 overall scheduling framework design

1.1 基于優(yōu)先級策略的第一級調(diào)度設(shè)計

第一級調(diào)度也稱為類間調(diào)度，是指各種不同類型的業(yè)務(wù)流所在隊列的調(diào)度服務(wù)。用戶站（subscribe sta?tion，SS）到基站（base station，BS）的連接將分配一種服務(wù)類型，BS針對每 個服務(wù)類別都建立與之相應(yīng)的調(diào)度隊列，每個隊列有一組與之相關(guān)聯(lián)的各自不同的QoS需求參數(shù)。

由于UGS服務(wù)類型的分組是以恒定速率和固定大小進行傳輸?shù)?，在IEEE802.16系統(tǒng)中，BS以主動授權(quán)方式為其分配帶寬，因而UGS業(yè)務(wù)無需進入第一級調(diào)度。余下rtPS、ertPS、nrtPS和BE4種類型業(yè)務(wù)進入第一級調(diào)度，采用服務(wù)類型優(yōu)先級算法。同類分組具備相同的QoS要求，隊頭分組的QoS優(yōu)先級函數(shù)值大小決定分組的順序，取值最大的分組將獲得優(yōu)先調(diào)度的權(quán)利。如圖2所示。

圖2 鏈路帶寬分配過程Fig.2 The link bandwidth allocation process

1.2 基于動態(tài)自適應(yīng)的第二級調(diào)度設(shè)計

第二級調(diào)度也稱為類內(nèi)調(diào)度，指各個相同類型的業(yè)務(wù)流間的調(diào)度。在IEEE802.16中提供QoS的基本思想：將帶有某個特定連接標識符（connection identifi?er，CID）標識的服務(wù)流，與來自MAC層接口的分組數(shù)據(jù)相關(guān)聯(lián)。如圖3所示。

1）UGS業(yè)務(wù)。

為有效保障UGS各業(yè)務(wù)流間的公平性，采用先進先出（first in first out，F(xiàn)IFO）方式，同時滿足了業(yè)務(wù)流對時延、速率等方面的要求，而不受到其他條件的制約。

2）rtPS和ertPS業(yè)務(wù)。

rtPS及ertPS業(yè)務(wù)流均屬于可變大小且大小不固定的分組，若分組時延超過一定要求會被丟棄，進而影響到用戶的感知，因此必須保證這2類業(yè)務(wù)的時延要求，這里選用基于改進的PDA?DFPQ算法。

3）nrtPS業(yè)務(wù)。

nrtPS業(yè)務(wù)支持非實時且不定期的大小可變的分組，時延上是沒有明確限制，但對最大持續(xù)傳輸速率、最小預(yù)留業(yè)務(wù)速率有要求，采用加權(quán)輪詢（weighted round robin，WRR）算法進行調(diào)度，通過權(quán)重系數(shù)設(shè)定業(yè)務(wù)隊列服務(wù)時間，高優(yōu)先級隊列具有優(yōu)先權(quán)。加權(quán)值表示獲取資源的比重，權(quán)重采用的公式：Wi＝其中pi為優(yōu)先級參數(shù)折算后的系數(shù)，ri為帶寬速率的差值。

4）BE業(yè)務(wù)。

對于BE業(yè)務(wù)，由于沒有對QoS嚴格的要求，考慮到多用戶間BE業(yè)務(wù)流的公平性，因此采用輪詢（round robin，RR）調(diào)度算法，為每個BE流提供相同的機會傳輸分組，即每次調(diào)度執(zhí)行i＝（i+1）mod n，并選出第i用戶進行調(diào)度。

2 仿真與分析

2.1 實驗參數(shù)設(shè)置

系統(tǒng)是基于單個BS，在TDMA訪問模式下使用點對多點（point to multipoint，PMP）方式執(zhí)行，多個SS終端隨機分布在3 km半徑范圍內(nèi)，部署3臺服務(wù)器，其中流媒體服務(wù)器主要是處理rtPS和ertPS業(yè)務(wù)、FTP服務(wù)器主要是處理nrtPS業(yè)務(wù)、Web服務(wù)器主要是處理BE業(yè)務(wù)，仿真的網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖4所示。

算法仿真在OPNET環(huán)境中實現(xiàn)，參數(shù)設(shè)置主要包括Config模塊、Application模塊和Profiles模塊，由于IEEE802.16網(wǎng)絡(luò)業(yè)務(wù)流具有自相似特性，利用Pareto ON／OFF仿真業(yè)務(wù)源，到達率為λ，ON期間服從Pareto分布，OFF期間服從泊松分布。

2.2 第一級調(diào)度仿真

對提出的PDA?DFPQ算法和傳統(tǒng)的虧空輪詢（defi?cit round robin，DRR）算法和RED?DFPQ算法在平均時延的性能進行對比；對5種業(yè)務(wù)進行仿真，SS數(shù)量從5個逐步增加到50個，仿真結(jié)果如圖5和圖6所示。圖5顯示了3種調(diào)度算法在不同SS數(shù)量下的平均隊列時延。其中PDA?DFPQ算法的時延最小，主要是其服務(wù)類別優(yōu)先級最高，減少了數(shù)據(jù)包隊列時延，因此，實時流量可在規(guī)定的時延約束下完成。而且隨著SS數(shù)目的增加，PDA?DFPQ中隊列時延的曲線變得平緩，這表明可滿足不同時延的要求，算法趨于平穩(wěn)。每個服務(wù)類別隊列獲取了合適的帶寬，使每個請求在其時限約束內(nèi)都可達到所需的數(shù)據(jù)，可以認為實現(xiàn)了調(diào)度算法中的公平性。而DRR和RED?DFPQ在SS數(shù)量較多時，平均隊列時延急劇增長，原因是簡單對各種業(yè)務(wù)的輪循或加權(quán)輪循，未考慮每個隊列的實際帶寬請求。

圖3 調(diào)度算法流程圖Fig.3 Scheduling algorithm flow chart

圖4 網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig.4 Typical network topology

圖5 隊列平均時延對比Fig.5 Comparion of queue average delay

圖6 顯示了PDA?DFPQ實現(xiàn)的各種服務(wù)類別的平均時延。

圖6 服務(wù)類別平均時延Fig.6 The average delay in service classes

可以看出UGS服務(wù)類別的時延最小，這是因為調(diào)度算法除了給UGS固定帶寬，還授予更高的權(quán)限。相比之下，當SS的數(shù)量增加時，BE和nrtPS數(shù)據(jù)包經(jīng)歷的時延增加了，這是因為較多幀時隙去滿足rtPS等實時流量需要。但BE業(yè)務(wù)時延也有一定的期限保障，這是因為調(diào)度算法也為非實時應(yīng)用保證了最小的預(yù)留速率。另一方面，ertPS和rtPS數(shù)據(jù)包時延相對較小，主要是PDA?DFPQ可以維持最大時延，為其相應(yīng)的服務(wù)請求區(qū)分保證公平性。

2.3 第二級調(diào)度仿真

第二級調(diào)度方案主要對rtPS業(yè)務(wù)和BE業(yè)務(wù)進行仿真，其中rtPS代表了實時流量，BE優(yōu)先級最低。

圖7和圖8分別對比了3種調(diào)度算法在rtPS和BE業(yè)務(wù)這2種服務(wù)類別吞吐量。很顯然，用于rtPS業(yè)務(wù)的吞吐量比BE高，因為調(diào)度算法的優(yōu)先級是給實時業(yè)務(wù)的，分配更多的帶寬給rtPS流。相應(yīng)地，rtPS業(yè)務(wù)的時延也較小。

圖7 服務(wù)類別平均時延Fig.7 The average delay in service classes

圖8 服務(wù)類別平均時延Fig.8 The average delay in service classes

雖然BE業(yè)務(wù)的時延受到一定的影響，但仍在可以接受的范圍內(nèi)。PDA?DFPQ算法下的rtPS業(yè)務(wù)吞吐量總體高于DRR和RED?DFPQ算法下的吞吐量，這是因為PDA?DFPQ算法采用自適應(yīng)調(diào)整機制，動態(tài)分配不同的權(quán)值系數(shù)，允許長度更大的分組得到更高的服務(wù)機會，網(wǎng)絡(luò)中傳輸?shù)姆纸M數(shù)量較多，更好地保障了分組調(diào)度情況；而對比DRR、RED?DFPQ算法，PDA?DF?PQ算法中BE的吞吐量保持在特定最小預(yù)留速率下，這是因為PDA?DFPQ賦予了rtPS隊列足夠的帶寬，使得當rtPS在其時限到期前，有足夠的時間讓調(diào)度算法能夠優(yōu)先服務(wù)BE業(yè)務(wù)。

圖9顯示了PDA?DFPQ、RED?DFPQ和DRR公平性的對比?？梢钥闯?，DRR公平性隨著流量負載的增加而惡化，因為它為實時業(yè)務(wù)賦予了高優(yōu)先級，當實時業(yè)務(wù)SS連接時，非實時業(yè)務(wù)則趨向于餓死。另一方面，當系統(tǒng)負載低于30個SS時，DRR顯示出公平性方面的穩(wěn)定，這是因為它為實時業(yè)務(wù)采用了額外的隊列。但當系統(tǒng)負載超過40個SS時，這些額外的隊列為非實時業(yè)務(wù)而得不到帶寬。這是因為非實時業(yè)務(wù)進行很長時間，而DC沒有服務(wù)完實時服務(wù)類別的隊列。相比之下，即使當SS為50個時，PDA?DFPQ的公平性也比RED?DFPQ和DRR要好。

圖9 服務(wù)類別平均時延Fig.9 The average delay in service classes

因此，可以得出，在可接受范圍內(nèi)犧牲非實時業(yè)務(wù)的吞吐量性能以換取實時業(yè)務(wù)的吞吐量優(yōu)化，更好地保證了實時業(yè)務(wù)的QoS要求。

3 結(jié)束語

針對IEEE802.16中MAC協(xié)議的調(diào)度機制不能提供流媒體業(yè)務(wù)區(qū)分服務(wù)的問題，引入分層設(shè)計和自適應(yīng)控制的思想，提出了一種基于服務(wù)類別優(yōu)先級鏈路帶寬自適應(yīng)分配調(diào)度算法，仿真結(jié)果表明該算法不僅能降低時延，保障實時業(yè)務(wù)的要求，而且能均衡各類型業(yè)務(wù)性能，提高網(wǎng)絡(luò)吞吐量和公平性，具有較強的網(wǎng)絡(luò)自適應(yīng)能力。在后續(xù)的工作中，將考慮不同路由策略下的無線網(wǎng)絡(luò)QoS性能，從而增強算法的普適性。

［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二級調(diào)度方案［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)的動態(tài)帶寬分配算法［J］.通信學報，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測量及優(yōu)化研究［D］.成都：電子科技大學，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ò)出版時間：2014?11?27.

國家自然科學基金資助項目（61302094）；福建省科技計劃重點資助項目（2014H0030）；泉州市科技計劃重點資助項目（2014Z102）.

蔣文賢（1974?），男，副教授.

蔣文賢，E?mail：jwx＠hqu.edu.cn.