IEEE802.16網絡動態自適應區分服務算法

蔣文賢，許曉璐

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

IEEE802.16網絡動態自適應區分服務算法

蔣文賢，許曉璐

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

針對IEEE802.16MAC協議中的調度機制不能提供流媒體業務區分服務的問題，提出了一種基于服務類別優先級的鏈路帶寬自適應分配調度PDA?DFPQ算法。該算法分為兩級調度架構，第一級是不同業務間的調度，采用服務質量優先級策略，高優先級服務類分配合適的帶寬，以保障實時業務對最大時延限定的要求；第二級是同種業務內的調度，采用自適應調整機制，根據隊列長度和分組數動態設置權值系數，以保障不同用戶對公平性和非實時業務對吞吐量的要求。仿真結果表明：與DRR和RED?DFPQ算法相比較，改進的一級調度算法能降低時延，解決實時性問題；改進的二級調度算法能均衡用戶速率，提高網絡吞吐量和公平性，解決突發性問題。

無線網絡；IEEE802.16；帶寬調度；自適應；區分服務

IEEE802.16［1］MAC（media access control，MAC）協議提供了主動授予服務（unsolicited grant service，UGS）、實時輪詢服務（real?time polling service，rtPS）、拓展實時輪詢服務（extended real?time polling service，ertPS）、非實時輪詢服務（non?real?time polling Service，nrtPS）和盡力而為服務（best effort，BE）等5種不同服務類型的服務質量（quality of service，QoS），但沒有提出保障QoS的具體實現方案和區分服務算法，而有效的上行鏈路和下行鏈路帶寬調度算法對QoS的保證具有重要意義。

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

根據現有文獻對IEEE802.16調度機制的研究，針對其不能提供流媒體業務區分服務的問題，將分層設計和自適應控制的思想引入到QoS調度機制中，提出了一種基于服務類別優先級的鏈路帶寬自適應分配調度算法PDA?DFPQ。

1 調度服務算法

該算法分為兩級調度架構，第一級是不同業務間的調度，采用服務質量優先級策略，高優先級服務類分配合適的帶寬，以保障實時業務對最大時延限定的要求，解決實時性問題；第二級是同種業務內的調度，采用自適應調整機制，根據隊列長度和分組數動態設置權值系數，以保障不同用戶對公平性和非實時業務對吞吐量的要求，解決突發性問題。總體調度框架圖如圖1所示。

圖1 IEEE802.16總體調度框架設計圖Fig.1 IEEE802.16 overall scheduling framework design

1.1 基于優先級策略的第一級調度設計

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

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

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

1.2 基于動態自適應的第二級調度設計

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

1）UGS業務。

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

2）rtPS和ertPS業務。

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

3）nrtPS業務。

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

4）BE業務。

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

2 仿真與分析

2.1 實驗參數設置

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

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

2.2 第一級調度仿真

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

圖3 調度算法流程圖Fig.3 Scheduling algorithm flow chart

圖4 網絡拓撲結構Fig.4 Typical network topology

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

圖6 顯示了PDA?DFPQ實現的各種服務類別的平均時延。

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

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

2.3 第二級調度仿真

第二級調度方案主要對rtPS業務和BE業務進行仿真，其中rtPS代表了實時流量，BE優先級最低。

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

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

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

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

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

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

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

3 結束語

針對IEEE802.16中MAC協議的調度機制不能提供流媒體業務區分服務的問題，引入分層設計和自適應控制的思想，提出了一種基于服務類別優先級鏈路帶寬自適應分配調度算法，仿真結果表明該算法不僅能降低時延，保障實時業務的要求，而且能均衡各類型業務性能，提高網絡吞吐量和公平性，具有較強的網絡自適應能力。在后續的工作中，將考慮不同路由策略下的無線網絡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二級調度方案［J］.計算機研究與發展，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］陳賡，夏瑋瑋，沈連豐.基于傳輸速率自適應的動態帶寬分配算法［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無線網絡QoS測量及優化研究［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.網絡出版時間：2014?11?27.

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

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

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