吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (05): 1338-1342.doi: 10.7964/jdxbgxb201305031

• paper • Previous Articles     Next Articles

Improvement of earliest deadline first scheduling algorithm

CHENG Yu1, ZHAO Hong-wei1, LONG Man-li2, LI Yu-cui1   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
    2. School of Foreign Language Education, Jilin University, Changchun 130012, China
  • Received:2012-06-15 Online:2013-09-01 Published:2013-09-01

Abstract:

In the process of service flow scheduling based on IEEE802.16d agreement, a good scheduling algorithm should ensure that higher priority tasks get priority service;meanwhile, the occupation of system resources during the scheduling process should be minimized. The advantages and disadvantages of two kinds of existing Earliest Deadline First (EDF) algorithms, i.e. the non-preemptive EDF algorithm and preemptive EDF algorithm, are analyzed in depth. Then an improved semi-preemptive EDF algorithm based on the importance of factors is proposed. In this algorithm the time characteristics, the importance characteristics and the order of reference are taken as the adjustable parameters, and the transmission distance is also taken into account. By simulation, the improved EDF algorithm is applied to the Real-Time Polling Service (RTPS) service flow scheduling of IEEE802.16d agreement. The experimental results show that the improved EDF algorithm has a better balance between advantages and disadvantages than non-preemptive and preemptive EDF algorithms, with smaller and more stable delay.

Key words: computer applications, earliest deadline first, delay time, deadline time, time characteristics, preempt

CLC Number: 

  • TP393

[1] IEEE P802.16H/D10-2009.IEEE standard for local and metropolitan area networks Part 16: air interface for fixed broadband wireless access systems[S].

[2] Chen Jian-feng,Jiao Wen-hua,Wang Hong-xi. A service flow management strategy for IEEE 802.16 broadband wireless access systems in TDD mode[C]//2005 IEEE International Conference on Communications. Seoul, Kerea: Institute of Electrical and Electronics Engineers Inc,2005.

[3] Ng T S E, Stoica Ion, Zhang Hui. Packet fair queueing algorithms for wireless networks with location-dependent errors[C]//Proceedings of the 1998 17th Annual IEEE Conference on Computer Communications, INFOCOM. Part 1 (of 3). San Francisco, CA, USA: IEEE, Piscataway, NJ, United States, 1998.

[4] Sayenko Alexander, Alanen Olli, Karhula Juha, et al. Ensuring the QoS requirements in 802.16 scheduling[C]//Proceedings of the 9th ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems. Malaga, Spain: Association for Computing Machinery, 2006.

[5] 胡军. 基于IEEE802.16的MAC层协议分析及QoS技术研究[D]. 重庆:重庆大学通信工程学院,2008. Hu Jun. MAC protocol analysis and QoS technology research based on IEEE802.16[D].Chongqing: Collage of Communication Engineering, Chongqing University,2008.

[6] 陈永锐,栗欣,乐正友. 基于预留的802.16MAC层资源调度算法[J]. 微电子学与计算机,2008, 25(1):62-65. Chen Yong-rui, Li Xin, Le Zheng-you. A fair scheduling algorithm based on resource reservation[J]. Micro Electronics & Computer, 2008, 25(1):62-65.

[7] Zhang Gang,Liu Chun-gui,Wang Feng, et al. Quality of service scheduling based on GPSS in IEEE 802.16 WiMax networks[C]//2008 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2008, Dalian, China,2008.

[8] Gakhar Kamal, Achir Mounir, Gravey Annie. Dynamic resource reservation in IEEE 802.16 broadband wireless networks[C]//2006 Fourteenth International Workshop on Quality of Service, IWQoS 2006. New Haven, CT, United States: Institute of Electrical and Electronics Engineers Inc, 2006.

[9] Wongthavarawat Kitti, Ganz Aura. Packet scheduling for QoS support in IEEE 802.16 broadband wireless access systems[J]. International Journal of Communication Systems,2003, 16: 81-96.

[10] Dusit Niyato, Ekram Hossain. QoS-aware bandwidth allocation and admission control in IEEE 802.16 broadband wireless access networks: A non-cooperative game theoretic approach[J]. Computer Networks, 2007, 51(11): 3305-3321.

[11] Cristian Vasar, Octavian Prostean, Ioan Filip, et al. Markov models for wireless sensor network [C]2009 IEEE 5th International Conference on Intelligent Computer Communication and Processing. Cluj-Napoca, Romania: IEEE Computer Society,2009.

[12] Cristian Vasar, Octavian Prostean, Ioan Filip, et al. A reliability analysis for wireless sensor networks in a wind farm[C]//22nd International Symposium on Information, Communication and Automation Technologies, Sarajevo, Bosnia and Herzegovina: IEEE Computer Society,2009.

[13] Chen Yun-xia, Zhao Qing. On the lifetime of wireless sensor networks[J]. IEEE Communications Letters, 2005, 9(11): 976-978.

[14] Roberto Verdone, Chiara Buratti. Modelling for wireless sensor network protocol design[C]//Wreless AD-HOC Networks. International Workshop. King's College London, UK: Curran Associates, Inc, 2005.

[15] 阚君满,秦俊,赵宏伟,等.基于累计价值的最早最终截止期优先调度策略[J].吉林大学学报:理学版,2012,50(2):315-319. Kan Jun-man, Qin Jun, Zhao Hong-wei,et al. First priority schedule strategy based on accumulated value earliest deadline[J]. Journal of Jilin University(Science Edition),2012,50(2):315-319.

[1] WU Jiao-rong, WANG Yu-qin, WEI Ming, LIN Bin. Impact of length of road-side bus lane on bus operational reliability [J]. 吉林大学学报(工学版), 2017, 47(1): 82-91.
[2] ZHANG Hao, LIU Hai-ming, WU Chun-guo, ZHANG Yan-mei, ZHAO Tian-ming, LI Shou-tao. Detection method of vehicle in highway green toll lane based on multi-feature fusion [J]. 吉林大学学报(工学版), 2016, 46(1): 271-276.
[3] CHEN Yun-han,QIN Gui-he,CHEN Si-guo,CANG Chen-yang,GAO Yang. Worst case of CAN massage response time in FPNS [J]. 吉林大学学报(工学版), 2014, 44(5): 1398-1403.
[4] ZHAO Hong-wei, CHENG Yu, LI Zhuo, LI Yu-cui. Design of QoS architecture in IEEE802.16d [J]. 吉林大学学报(工学版), 2013, 43(03): 701-705.
[5] GUAN Jian, LIU Yan-heng, LU Ying-qi, LIU Xue-jie, WANG Long, LIU Yang. Concentric ring cluster routing algorithm based on coverage for WSN [J]. 吉林大学学报(工学版), 2013, 43(01): 158-164.
[6] JIANG Ju-lang, HUANG Zhong, ZHENG Jiang-yun. Algorithm for texture atlas generation based on triangular bounding box [J]. , 2012, (06): 1543-1547.
[7] ZHAO Hong-wei, CUI Hong-rui, DAI Jin-bo, ZANG Xue-bai. Contour detection based on HMAX model and non-classical receptive field inhibition [J]. 吉林大学学报(工学版), 2012, 42(01): 128-133.
[8] YANG Li-li|JIA Hong-fei|JUAN Zhi-cai. Transfer system reliability and its influencing factors of rail transit terminal [J]. 吉林大学学报(工学版), 2011, 41(4): 944-949.
[9] ZHAO Xin,WANG Xiao-dong. Efficient self-adaptive broadcast authentication mechanism in wireless sensor networks [J]. 吉林大学学报(工学版), 2011, 41(03): 758-764.
[10] ZHAO Hong-Wei, ZHAO De-Fang, ZHANG Yuan, WEI Li. Application software thread of mobile video system based ARM9 [J]. 吉林大学学报(工学版), 2010, 40(增刊): 301-0303.
[11] DING Ying, LI Wen-Hui, FAN Jing-Tao, YANG Hua-Min. Fuzzy integral feature based algorithm for moving infrared object detection [J]. 吉林大学学报(工学版), 2010, 40(05): 1330-1335.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!