WiMAX系统的分组调度算法研究
摘要
WiMAX标准定义了无线城域网的MAC层和物理层技术规范。在MAC层,标准将不同的业务流归类为UGS,rtPS,nrtPS和BE四种类型,分别对四种业务流进行QoS保证。在物理层,采用OFDM等技术为数据在复杂的物理环境中传输提供可靠的保证。虽然标准为不同业务提供了QoS保障机制,但是标准并没有给出保证这些QoS需求所要使用的资源调度算法。因此,这些问题成为人们对WiMAX技术进行深入研究的热点。
本文主要研究了基于WiMAX的QoS保障机制的资源调度算法设计与实现。首先对WiMAX标准的内容做了简单的介绍,接着对WiMAX的带宽管理机制和现有的各种分组调度算法做了综述。在此基础上提出了DRR算法在WiMAX系统中的改进算法(I-DRR)。利用搭建的WiMAX仿真平台对改进的DRR算法性能进行了仿真研究。仿真结果表明,I-DRR算法在吞吐量、时延、带宽利用率方面确实比DRR算法有了很大的提高。通过与PQ算法相比较发现,I-DRR算法具有更好的公平性。
The MAC layer and PHY layer specifications are defined in WiMAX standard. Service flows are classified into the UGS, rtPS, nrtPS and BE types according to their QoS requirements, and the QoS requirements are satisfied by the MAC layer mechanisms respectively. In PHY layer, OFDM technique is introduced to guarantee the reliable data transmission in complicated physical environments. Although perfect QoS guarantee are provided for different services, the packet scheduling algorithms to implement the QoS support are not given by the standard. All these issues are left for people to reaserch.
The design and implementation of packet scheduling algorithms based on WiMAX’s QoS guarantee are discussed in this thesis.
In this paper, WiMAX standard is described firstly. Then we give an introduction to the basic knowledge and research on bandwidth management mechanism and existing packet scheduling algorithms. Based on these, the I-DRR(Improved-DRR) algorithm which is improved from Deficit Round Robin algorithm is given and is simulated on simulation tool we have implemented for WiMAX. The simulation results show that compared with DRR, the I-DRR has better performaces on throughput, delay and bandwidth usage ratio and shows better fairness than Priority Queue algorithm.
本文主要研究了基于WiMAX的QoS保障机制的资源调度算法设计与实现。首先对WiMAX标准的内容做了简单的介绍,接着对WiMAX的带宽管理机制和现有的各种分组调度算法做了综述。在此基础上提出了DRR算法在WiMAX系统中的改进算法(I-DRR)。利用搭建的WiMAX仿真平台对改进的DRR算法性能进行了仿真研究。仿真结果表明,I-DRR算法在吞吐量、时延、带宽利用率方面确实比DRR算法有了很大的提高。通过与PQ算法相比较发现,I-DRR算法具有更好的公平性。
The MAC layer and PHY layer specifications are defined in WiMAX standard. Service flows are classified into the UGS, rtPS, nrtPS and BE types according to their QoS requirements, and the QoS requirements are satisfied by the MAC layer mechanisms respectively. In PHY layer, OFDM technique is introduced to guarantee the reliable data transmission in complicated physical environments. Although perfect QoS guarantee are provided for different services, the packet scheduling algorithms to implement the QoS support are not given by the standard. All these issues are left for people to reaserch.
The design and implementation of packet scheduling algorithms based on WiMAX’s QoS guarantee are discussed in this thesis.
In this paper, WiMAX standard is described firstly. Then we give an introduction to the basic knowledge and research on bandwidth management mechanism and existing packet scheduling algorithms. Based on these, the I-DRR(Improved-DRR) algorithm which is improved from Deficit Round Robin algorithm is given and is simulated on simulation tool we have implemented for WiMAX. The simulation results show that compared with DRR, the I-DRR has better performaces on throughput, delay and bandwidth usage ratio and shows better fairness than Priority Queue algorithm.
引文
[1] IEEE802.16 working group, IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std. October 2004
[2] Alan Demers, S.keshav, and S.Shenker. Analysis and Simulation of a Fair Queuing Algorithm. Proc.ACM SIGCOMM’89. 1989. 3-12
[3] S.Lu, V.Bharghavan, and R.Srikant. Fair Scheduling in Wireless Network. IEEE/ACM Trans.Networking. 1999,vol.7,no 4. 472-489
[4] Y. Cao, and V. O. K. Li. Scheduling Algorithms in Broad-Band Wireless Networks. Proceedings of the IEEE. January 2001.Vol. 89. 76-86.
[5] A.K.Parekh, and R.G.Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case . IEEE/ACM Trans.Networking. 1993,7,vol.1. 334-357
[6] R. Bennett ,and H.Zhang. WF2Q:Worst2case fair weighted fair queuing [C] . IEEE INFOCOM’96 , Mar. 1996 . 120 - 128.
[7] M.Shreedhar and G.Varghese. Efficient Fair Queuing using Deficit Round Robin. Proc.ACMSIGCOMM’95. 1995. 231-242
[8]宋舰,李乐民.无线网络中的分组调度算法.通信学报. 2003.3,vol.24,no.3. 42-48
[9] BHARGHAVAN, V.LU, and S.NANDAGOPAL T. Fair queueing in wireless networks: issues and approaches. IEEE Personal Communications Magazine, 1999, vol.6,no.1. 44-53
[10] M.Shreedhar and G.Varghese. A unified architecture for the design and evaluation of wireless fair queuing algorithms. ACMMOBICOMM 1999[C]. Seattle WA, 1999. 132-142
[11] BUCHELI S. Compensation modeling for QoS support on a wireless network. http://ipoint.vlsi.uiucedu/wireless/papers/stefan_thesis.pdf, 2000
[12] P.Bhagwat, P.Bhattacharya and A.Krishma. Enhancing throughput over wireless LANs using Channel State Dependent Packet Scheduling. IEEE INFOCOM’96. 1997
[13] J. Gomez, A. T. Campbell, and H. Morikawa. The Havana framework for supporting application and channel dependent QoS in wireless networks. Proc. ICNP’99. Nov. 1999. 235-244
[14] E.L.Hahne, R.G.Gallager. Round Robin Scheduling for Fair Flow Control in Data Communication Networks. International Conference on Communications. 1986.7. 103-107
[15] J.R.Moorman, John.Lockwood, and Sung-M Kang. Wireless Quality of Service Using Multiclass Priority Fair Queuing. IEEE JOURNAL. 2000
[16]李小花,李小军. IP网络QoS几种排队算法的对比分析.四川理工学院学报(自然科学版). 2006,7,vol.19,no3. 81-84
[17]宣孝英,石冰心,邹玲.无线网络包调度算法综述.计算机工程与应用.2003,vol.17. 20-21
[18]王重钢,隆克平,龚向阳,等.分组交换网络中队列调度算法的研究及其展望.电子学报. 2001, 4, vol.29, no4. 553-558
[19]邬海涛,王重钢,隆克平,等.一种新的基于GPS的分组公平调度器.电子学报. 2002, 4, vol.30, no4. 460-463
[20] Jiang Chen, Wenhua Jiao, and Qian guo. An Integrated QoS Control Architecture for IEEE 802.16 Broadband Wireless Access Systems
[21] K.Wongthavarawat, Aura Ganz. Packet Scheduling for QoS Support in IEEE802.16 Broadband Wireless Access Systems. Int. J. Commun. Syst. 2003,vol.16. 81-96
[22]张金文,等. 802.16宽带无线城域网技术.电子工业出版社. 2006.4
[23]彭木根,王文博,等.下一代宽带无线通信系统OFDM&WiMAX.机械工业出版社. 2007.1
[24] P.Ramanathan, P.Agrawal. Adapting Packet Fair Queuing Algorithms to wireless Networks. ACM/IEEE MOBICOM’98, Dallas, TX. 1-9.
[25]王彬,吕登芳,马凤国. IEEE802.16和WiMAX的组网技术.中兴通讯技术. 2006.4, vol.12, no.2. 21-26
[26]李茗,彭木根,王文博. WiMAX系统QoS机制研究.现代电信科技. 2005.7, no.7. 25-30
[27] M.Hawa, D.W. Petr . Quality of service scheduling in cable and broadband wireless access systems. Tenth IEEE International Workshop on Quality of Service. 2002. 247-255 .
[28] Jianfeng Chen, Wenhua Jiao, Hongxi Wang. A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode. IEEE. 2005.
[29] Luís Felipe M. de Moraes and Paulo Ditarso Maciel Jr. An Alternative QoS Architecture for the IEEE 802.16 Standard.
[30] Jenhui Chen, Chih-Chieh Wang, Frank Chee-Da Tsai,etc. The Design and Implementation of WiMAX Module for ns-2 Simulator.
[31]徐雷鸣,庞博,赵耀. NS与网络模拟.人民邮电出版社. 2003.11
[32]林闯,单志广,任丰原.计算机网络服务质量(QoS).清华大学出版社. 2004.4.
[33] Janez Bostiè, and Gorazd Kandus. MAC Scheduling for Fixed Broadband Wireless Access Systems.
[34] X. Xu, D. Liang, H. Jiang, and X. Lin. Dynamic Bandwidth Allocation in Fixed BWA Systems. Proc. of Inter. Conf. on Comm. Technology (ICCT’03), vol. 2, Apr. 2003.
[35] The Network Simulator-ns-2. http://www.isi.edu/nsnam/ns/index.html, 2000.
[2] Alan Demers, S.keshav, and S.Shenker. Analysis and Simulation of a Fair Queuing Algorithm. Proc.ACM SIGCOMM’89. 1989. 3-12
[3] S.Lu, V.Bharghavan, and R.Srikant. Fair Scheduling in Wireless Network. IEEE/ACM Trans.Networking. 1999,vol.7,no 4. 472-489
[4] Y. Cao, and V. O. K. Li. Scheduling Algorithms in Broad-Band Wireless Networks. Proceedings of the IEEE. January 2001.Vol. 89. 76-86.
[5] A.K.Parekh, and R.G.Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case . IEEE/ACM Trans.Networking. 1993,7,vol.1. 334-357
[6] R. Bennett ,and H.Zhang. WF2Q:Worst2case fair weighted fair queuing [C] . IEEE INFOCOM’96 , Mar. 1996 . 120 - 128.
[7] M.Shreedhar and G.Varghese. Efficient Fair Queuing using Deficit Round Robin. Proc.ACMSIGCOMM’95. 1995. 231-242
[8]宋舰,李乐民.无线网络中的分组调度算法.通信学报. 2003.3,vol.24,no.3. 42-48
[9] BHARGHAVAN, V.LU, and S.NANDAGOPAL T. Fair queueing in wireless networks: issues and approaches. IEEE Personal Communications Magazine, 1999, vol.6,no.1. 44-53
[10] M.Shreedhar and G.Varghese. A unified architecture for the design and evaluation of wireless fair queuing algorithms. ACMMOBICOMM 1999[C]. Seattle WA, 1999. 132-142
[11] BUCHELI S. Compensation modeling for QoS support on a wireless network. http://ipoint.vlsi.uiucedu/wireless/papers/stefan_thesis.pdf, 2000
[12] P.Bhagwat, P.Bhattacharya and A.Krishma. Enhancing throughput over wireless LANs using Channel State Dependent Packet Scheduling. IEEE INFOCOM’96. 1997
[13] J. Gomez, A. T. Campbell, and H. Morikawa. The Havana framework for supporting application and channel dependent QoS in wireless networks. Proc. ICNP’99. Nov. 1999. 235-244
[14] E.L.Hahne, R.G.Gallager. Round Robin Scheduling for Fair Flow Control in Data Communication Networks. International Conference on Communications. 1986.7. 103-107
[15] J.R.Moorman, John.Lockwood, and Sung-M Kang. Wireless Quality of Service Using Multiclass Priority Fair Queuing. IEEE JOURNAL. 2000
[16]李小花,李小军. IP网络QoS几种排队算法的对比分析.四川理工学院学报(自然科学版). 2006,7,vol.19,no3. 81-84
[17]宣孝英,石冰心,邹玲.无线网络包调度算法综述.计算机工程与应用.2003,vol.17. 20-21
[18]王重钢,隆克平,龚向阳,等.分组交换网络中队列调度算法的研究及其展望.电子学报. 2001, 4, vol.29, no4. 553-558
[19]邬海涛,王重钢,隆克平,等.一种新的基于GPS的分组公平调度器.电子学报. 2002, 4, vol.30, no4. 460-463
[20] Jiang Chen, Wenhua Jiao, and Qian guo. An Integrated QoS Control Architecture for IEEE 802.16 Broadband Wireless Access Systems
[21] K.Wongthavarawat, Aura Ganz. Packet Scheduling for QoS Support in IEEE802.16 Broadband Wireless Access Systems. Int. J. Commun. Syst. 2003,vol.16. 81-96
[22]张金文,等. 802.16宽带无线城域网技术.电子工业出版社. 2006.4
[23]彭木根,王文博,等.下一代宽带无线通信系统OFDM&WiMAX.机械工业出版社. 2007.1
[24] P.Ramanathan, P.Agrawal. Adapting Packet Fair Queuing Algorithms to wireless Networks. ACM/IEEE MOBICOM’98, Dallas, TX. 1-9.
[25]王彬,吕登芳,马凤国. IEEE802.16和WiMAX的组网技术.中兴通讯技术. 2006.4, vol.12, no.2. 21-26
[26]李茗,彭木根,王文博. WiMAX系统QoS机制研究.现代电信科技. 2005.7, no.7. 25-30
[27] M.Hawa, D.W. Petr . Quality of service scheduling in cable and broadband wireless access systems. Tenth IEEE International Workshop on Quality of Service. 2002. 247-255 .
[28] Jianfeng Chen, Wenhua Jiao, Hongxi Wang. A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode. IEEE. 2005.
[29] Luís Felipe M. de Moraes and Paulo Ditarso Maciel Jr. An Alternative QoS Architecture for the IEEE 802.16 Standard.
[30] Jenhui Chen, Chih-Chieh Wang, Frank Chee-Da Tsai,etc. The Design and Implementation of WiMAX Module for ns-2 Simulator.
[31]徐雷鸣,庞博,赵耀. NS与网络模拟.人民邮电出版社. 2003.11
[32]林闯,单志广,任丰原.计算机网络服务质量(QoS).清华大学出版社. 2004.4.
[33] Janez Bostiè, and Gorazd Kandus. MAC Scheduling for Fixed Broadband Wireless Access Systems.
[34] X. Xu, D. Liang, H. Jiang, and X. Lin. Dynamic Bandwidth Allocation in Fixed BWA Systems. Proc. of Inter. Conf. on Comm. Technology (ICCT’03), vol. 2, Apr. 2003.
[35] The Network Simulator-ns-2. http://www.isi.edu/nsnam/ns/index.html, 2000.