Efficient Resource Management for Uplink Scheduling in IEEE 802.16e Standard
Adv. Sci. Technol. Eng. Syst. J. 2(1), 263–268 (2017);
DOI: 10.25046/aj020132
The IEEE 802.16e standard, known as mobile Worldwide Interoperability for Microwave Access (WiMAX) becomes the most demanding broadband wireless access (BWA) technology recently. Its main advantage is rapid delivery of services in remote areas due to the cost efficiency factor. The base station (BS) supports data rate up to 70 Mbps, mobile stations with 5–15 km length of coverage, and for the fixed stations the wireless access range up to 50 km. To resolve the bandwidth contention issue and guarantee seamless packet transmission from the subscriber stations (SS) to the BS, the uplink (UL) traffic scheduling must be efficient and reliable. This paper studies the work on the UL scheduling algorithm, namely minimum rest time (MRT). The MRT goal is to strengthen the packet transferring time between the SS and the BS by refining the pre-stipulated expired time and the deadline time of the earliest expiry first (EEF) and earliest deadline first (EDF) hybrid algorithms. These legacy algorithms are inadequate to support the multi-class traffic systems due to the shortage of quality of service (QoS) parameters featuring. Moreover, the algorithms are highly static. Using the Omnet++ with the relevant performance metrics the obtained results confirmed the MRT outperforms effectively from the legacy algorithms.
1. Introduction
The high cost factor in establishing the wired broadband network in rural areas has become the major driving force of the expansion efficient wireless network systems. The present wireless broadband technologies have their own nature in giving the solutions to the challenges and issues imposed by the technology itself. Such challenges include QoS traffic channels, scarce bandwidth resource, interference, error rate, and mobility barrier. Presently, the mobile WiMAX standard becomes the most promising and widely being used for broadband wireless technology [1].
The outstanding features of the mobile WiMAX are wide frequency range coverage, last-mile accessing, and increased QoS traffic supports for various types of applications, especially the multimedia applications [2–3]. It efficiently can serve the metropolitan area (e.g., WMAN) network with high-speed data rates and wide range signal coverage. The two main architecture entities of the standard are BS and SS. The BS provides the air interface for the subscriber (up to 30 miles) while for the mobile
stations is between three to ten miles. The SS (referred as customer premises equipment (CPE) can take either indoor or outdoor provides the connectivity among the subscriber’s equipment and the BS. Others existing broadband wireless technology solutions are the IEEE 802.11a with data rate 54 Mbps with coverage area up to hundreds of meters, the enhanced data rates for GSM evolution (EDGE) with 384 Kbps and coverage zone up to few kilometers and the code-division multiple access 2000 (CDMA2000), with data rate of two Mbps and coverage zone up to few kilometers.
Figure 1 illustrates the three setup modes for the mobile WiMAX standard, namely i) point-to-point (PTP), ii) point-to-multipoint (PMP), and iii) mesh [4]. The PTP setup mode interconnects two BSs that having different or miscellaneous networks. On the other hand, the PMP mode was designed for the mobility structure where the respective SSs are directly connected to the localized BS. In the mesh mode, the BS and several SSs are connected to each other in an ad hoc manner. Each SS acts as a router that helps and collaborates directly to transmit the data onto the SSs. The transmission schemes for all setup modes take place through two independent channels, either UL channels (from SS to BS) or downlink (DL) channel (from BS to SS) [5-6]. Note that, the UL channel is shared among all SSs while the BS is only using the DL channel scheme.
The main attention of this paper is the scheduling algorithms those guarantee the data packet flows for the UL traffic channel. To satisfy user demands and supporting new set of real-time services and applications, a realistic and dynamic resource allocation algorithm is mandatory. The UL scheduling algorithm at the BS should lead its decision with all the SSs whereas the DL channel algorithm is only worried in communicating the decision locally to the BS [7]. But, the UL scheduling algorithm design is a challenging task due to the requirement in different level of QoS classes, fairness and application difficulty [6]. One of the efficient UL hybrid scheduling algorithms is the earliest deadline first (EDF). However, the main problem with the algorithm is when the difference among the deadline is quite large, the lower priority queues have to starve. Moreover, the earliest expiry first (EEF) algorithm has given a solution to solve the packet waiting time avoiding, missing deadline, and delay reducing. However, the EEF algorithm has the limitations when the packet transmission time is not being considered. The packets with high and low priorities are being transmitted together, thus will create a delay in the network. To overcome the limitations of the existing algorithms, this paper studies the optimized UL scheduling, namely minimum rest time (MRT). The algorithm controls and monitors the packets flow using both their rest time and expiry time, respectively. Using comprehensive simulations, the rest and the expiry time parameters have shown a significant impact to QoS of the packets transmission as compared to the legacy UL scheduling algorithms.
The remainder of this paper is organized as follows. Section 2 discusses the background of mobile WiMAX UL scheduling algorithms and their related works. Section 3 provides the detailed explanations about the proposed MRT hybrid-scheduling algorithm. The performance of the proposed algorithm is being evaluated in Section 4. Finally, this paper concludes with Section 5.
2. Background and Related Works
2.1. WiMAX Uplink Scheduling
The main issues raised by many researchers in providing efficient mobile WiMAX services is a packet scheduling. The scheduling issue is constantly emerging the relation to the demands for WiMAX-related services. Thus, the scheduling algorithm should take into account the diverse WiMAX QoS classes and the service requirements. The UL scheduling algorithms are essential in solving the QoS bandwidth allocation contention among the users with diverse service classes of traffic. The examples of the traffic classes are best effort (BE), non-real-time polling service (nrtPS), unsolicited grant service (UGS), and real-time polling service (rtPS). Note that, IEEE 802.16e standard is the expansion from IEEE 802.16-d standard with additional mobility feature. The feature brings a significant effect on the QoS traffic. Figure 2 shows the expansion of both standards that yield the extended real-time polling service (ertPS) traffic class [8]. The ertPS traffic class takes the advantages of both the UGS and the rtPS classes [10]. Unlike the UGS class, the ertPS class is being designed to support the VoIP traffic with silence detention and the traffic flow that generates the variable sized packets. The packets are coupled with QoS guarantee and its space is generated in a periodical manner [2,7, 16–17].
As indicated by [11–12], there are three categories of the UL scheduling algorithms are i) homogenous, ii) hybrid, and iii) opportunistic.
The hybrid scheduling is the ideal for the UL since it explicitly caters to all the required QoS parameters associated with the WiMAX traffic classes. This motivates us to mainly focus on optimizing the UL scheduling in guaranteeing efficient mobile WiMAX services.
2.2. WiMAX Uplink Scheduling
Table 1 summarizes the existing hybrid scheduling algorithms with the different QoS traffic classes. In deriving various solutions for optimize the UL scheduling algorithm, most researchers force to create hybrid scheduling [11]. The algorithms combine the legacy algorithms to satisfy the QoS requirements of the multi-class traffic as specified in the IEEE 802.16e standard.
Table 1: Hybrid Scheduling Algorithms
|
Authors |
Algorithms |
QoS classes |
| Oad et. al [15] | EEF + WFQ + FIFO | (EEF à rtPS)
(WFQ à nrtPS) (FIFO à BE) |
| Wongthavarawat
and Ganz [19] |
EDF + WFQ + FIFO | (EDF à rtPS)
(WFQ à nrtPS) (FIFO à BE) |
| Vinay et. al [14] | EDF + WFQ | (EDF à rtPS)
(WFQ à nrtPS, BE) |
| Settembre et. al [20] | WRR + RR | (WRR à rtPS, nrtPS)
(RR à BE) |
| Gidlund et. al [16] | EDF + WFQ | (EDF à ertPS, rtPS)
(WFQ à nrtPS, BE) |
| Chowdhury et. al [7] | EDF + DFPQ
|
(EDF à UGS, rtPS)
(DFPQ à nrtPS, BE) |
The work by [13] has evaluated the various scheduling algorithms used for the UL traffic in WiMAX. Under the hybrid EDF, weighted fair queuing (WFQ) and first in first out (FIFO) schedulers, the UL traffic produces the greatest throughput. In addition, the hybrid scheduler that appoints multiple legacy algorithms with the established traffic classes have been studied and being evaluated by [14]. For instance, the EDF scheduler for the rtPS, the WFQ scheduler for nrtPS, and the FIFO scheduler for the BE class. The schedulers those serve various traffic classes perform better than the legacy algorithms as they satisfy the multi-class traffic QoS requirements. Further, the hybrid algorithm explicitly caters to all the required QoS parameters associated with the respective traffic classes in the IEEE 802.16e standard.
2.3. EEF+WFQ+FIFO Hybrid Algorithm Scheduling
The algorithm has been designed as an extraction from the EDF hybrid sub-scheduling algorithm [14]. It controls and displays the data packets using the deadline and an individual packet expiry time. Thus, packets are being scheduled based on a mixture of specified deadlines and the on-going knowledgeable delay. Therefore, packets with the smallest time expires will be scheduled first while packets with bigger time expires are always buffered indefinitely. In many instances, those packets will expire and miss their time expire.
Further, the algorithm has catered distinctly each of the diverse requirements of the multiclass traffic supported by the WiMAX. However, in ensuring a preferred service sorted based on traffic constraints, the algorithm is of absolute the chronological preference. For instance, the service is always given to the higher priority traffic class where the lower priority traffic class will be the only service when higher priority has finished. Once the allocation is done, there are no changes until the end of the transmission. This causes rigid and non-flexible resource utilization.
2.4. EDF+WFQ+FIFO Hybrid Algorithm Scheduling
As mentioned by [18], no single inheritance schedulers that can fulfill all the QoS requirements of the WiMAX network applications. The EDF+WFQ+FIFO scheduling algorithm was proposed to provide low-delay and packet loss for real-time applications [19]. In addition, it is designed for handling the diversified QoS traffic classes. The traffic classes create an effective management but they impose higher QoS demands in the networks. The algorithm service is being executed with different QoS schedulers to meet these requirements. For instance, the EDF is being used for the rtPS traffic, the WFQ for the nrtPS traffic, while the BE traffic employs the FIFO scheduler.
The hybrid EDF+WFQ+FIFO scheduling uses the stern priority service mechanism. That means all the bandwidth for the higher priority SSs are being distributed evenly until they do not have any packets to transmit. The disadvantage is that lower priority SSs will starve in the presence of many higher priority SSs due to the strict priority overall bandwidth allocation. Further, the algorithm does not take into consideration the variable channel conditions of each SS and constraints the flexibility of the WiMAX. In addition, it does not provide different bandwidth grant sizes for different quality of service classes.
3. MRT+WFQ+FIFO Algorithm
The MRT algorithm has been designed as an abstraction from the EEF hybrid sub-scheduling algorithm. The algorithm has controls and monitors the data packets using their packet rest time and respective expiry time. When compared with the EEF, the packets in the MRT algorithm are being scheduled based on a combination of the specified packet rest time to reduce the happened earlier expiry time. Packets that have shorter MRT are being scheduled first as opposed to those with longer MRT. This means the data packets with a shorter time to expire being served first, but must have a minimum MRT time. On the other hand, packets with maximum MRT has a long expiry time due to all minimum will be served and transferred gradually to serve the longer MRT value packets. To help in this manner, the priority queue is being used to arrange packet arrival time according to the priority. This grants minimum delay time for the earliest packet to be served.
3.1. MRT Algorithm Efficiency
Both diagrams in Figure 3 show how to select the priority packet (e.g., the 4th packet) to be served in the MRT algorithm. The algorithm considers the transmission time of the packet and those packets that are present in the queue are more sensitive to their deadlines. If the expiry time is being crossed, then the packet is useless. To reduce the delay, the MRT algorithm works based on the minimum time for the packet to stay in the queue. Thus, it will lead to the validity of minimum waiting at the packet to be expired.
Figure 4 simplifies the MRT scheduling algorithm. To determine the packet to be served in the MRT algorithm, the calculation for the packet as follows: Any packet has the current time (curr_TMS) and arrival time (packet_arr_TMS), respectively. The waiting time (wait_TMS) of the packet in the queue is being calculated as:
wait_TMS = curr_TMS – packet_arr_TMS (1)
Each packet has the deadlines which not being crossed each other. The time to expire (TTE) is being calculated as:
TTE = deadline – wait_TMS (2)
The packet is being transmitted from the source to destination. Moreover, when it arrives at the queue, it may have minimum time to stay or TTE. Thus, the MRT time is being calculated as:
MRT = (TTE – packet_arr_TMS) – curr_TMS (3)
| 1. | Arrival ⟸ arrival( ) |
| 2. | if flowType == ertPS then |
| 3. | CheckQueueSize < MaximumQueueSize |
| 4. | ++npa_ertPS |
| 5. | ++Cqsize |
| 6. | PacketArrivalTimeQueue ⟸ simclock |
| 7. | AssignDeadlineArrivalPacket ⟸ deadlineertPS |
| 8. | else if (queue ertPS > 0) || ( queueertPS < threshold1) then |
| 9. | Priority ⟸ deadlineertPS; |
| 10. | end else if |
| 11. | else DropThePacket then |
| 12. | ++plr |
| 13. | end if |
| 14. | end arrival |
| 15. | |
| 16. | Departure ⟸ departure() |
| 17. | if CheckQueueSize != 0 then |
| 18. | ++npd_ertPS |
| 19. | Delay ⟸ simclock – PacketArrivalTimeQueue |
| 20. | CurrentDiffernce ⟸ deadlineertPS – Delay |
| 21. | TimeToExpireertPS[currentDiffernce] |
| 22. | RestTime =TimeToExpireertPS –simclock |
| 23. | MiniRestTime ⟸ RestTime |
| 24. | SearchingMinimumValue ⟸ MiniRestTime |
| 25. | else CheckQueueSize == 0 then |
| 26. | BSS ⟸ BaseStation_IDLE |
| 27. | end if |
| 28. | end departure |
Figure 4: Pseudo code of the MRT Scheduling
4. Experimental Setups and Evaluations
4.1. Simulation Model and Parameter
The traffic rate for each traffic class used in the simulation is tabulated in Table 2 and the proposed MRT algorithm was implemented using the Omnet++ simulation tool.
Table 2: Simulation Parameters
|
Inputs |
Values |
Packet Size (bytes) |
Rate (Kbps) |
Load (l) (Kbps) |
| BS | 1 | |||
| SS | 6 to 36 | |||
| SS ratio | 3:1:1:1 | |||
| Simulation time (simClock) | 50 secs. | |||
| Service time | 20 Mhz | |||
| Voice | 23 | |||
| Video | 150 – 300 | |||
| FTP | 150 | |||
| HTTP | 100 | |||
| ertPS | 64 | 1000 | ||
| rtPS | 500 | 3000 | ||
| nrtPS | 500 | 2500 | ||
| BE | 64 | 300 |
The MRT scheduling algorithm performance has been evaluated by conducting extensive simulation experiments. The main components of the developed simulator were oriented on the BS and SSs. The BS representing the scheduling algorithms and each sub-scheduling algorithm within the hybrid QoS classes (i.e., ertPS, rtPS, nrtPS and BE) are being executed individually. The simulation run time was set to 50 seconds for ensuring equal comparison algorithm platforms. In this study, six experiments were conducted according to various numbers of SS (e.g., 5, 12, 18, 24, 30, and 36).
4.2. Performance Metrics
The selections of the performance metrics in this study are based on the substantial adoption in UL scheduling for both EEF and EDF algorithms. The performance metrics and their respective derivation are as follows:
Avg_throughput = Packets departure / Simulation time (4)
Avg_delay = Total delays / Packets departure (5)
Missed_deadline (misdl) ratio = tpkt_misdl / npa (6)
Parameters tpkt_misdl refers to the misdl overall total while the npa is the total number of packets arrived. And
Avg_queue = Total queue / time (7)
The parameter time in (7) refers to simulation clock time (e.g., simclock).
4.3. Results and Discussions
The results of the proposed MRT algorithm are presented in comparison with EEF+WFQ+FIFO and EDF+WFQ+FIFO algorithms. The average throughput results are illustrated in Figure 5. As can be seen, the average throughput gradually decreases as the number of SS grew among the algorithms. The proposed MRT algorithm performs better due to the reflection of the dynamic versatile expire time parameter. Compared to the existing algorithms, they depend on the static pre-defined deadline parameter.
Next, since there is many packets waiting in the queue and eventually expired, the MRT algorithm has shown the significant ability in reducing the delays. Figure 6 shows the average delay between the existing and the proposed algorithm. Although the MRT algorithm shows mild increase for the delay, the maximum value achieved before being constantly maintained (i.e., from the number of SS equivalent to 36) is still lower as compared to existing algorithms.
Figure 7 illustrates the packets missed deadline ratio performance among the algorithms where the proposed MRT gives the lowest ratio. By using the MRT time, each of the arrived queued packets which have the earlier waiting will be propagated to have the priority to be served first. Thus, the algorithm performs slightly better the existing UL scheduling algorithms.
In terms of the queue size performance, the percentage of queue size gradually increases when the number of SS increases, see Figure 8. Again, as compared to the MRT algorithm, the algorithm guarantees the lowest average queue size when the packets are being transmitted from the source to destination. Thus, theses simulation results have proven that the proposed MRT algorithm has superior performance.
5. Conclusion
The acquired results prove that the proposed MRT algorithm has successfully enhanced by increasing transfer packets arriving at a base station in the UL mode for the mobile WiMAX network system. The results of reviewed scheduling algorithms for the mobile WiMAX have greatly influenced the direction in which the designed and proposed solutions have taken form. In this research, the scheduling algorithm tailored at enhancing the collective performance of hybrid algorithms in the mobile WiMAX domains has been designed and developed. The spectrum of constraints that have been extracted from the hybrid EEF+WFQ+FIFO algorithm includes the static nature by which priorities are assigned and maintained during the entire duration of a transmission time. Reengineering the scheduling mechanics governing the EEF algorithms is the main contribution of this study. The dominance of the pre-stipulated deadline is indeed acknowledged in the proposed and developed enhanced MRT. However, the significance of providing a monitoring mechanism that gauges between the stipulated and the reality of performance is the essential focus of the MRT algorithm. Unlike the legacies algorithms, the MRT algorithm is able to revaluing the packets of interest for the transmission in case when packets decline the service due to a longer deadline. In such cases, the proposed MRT algorithm is being arranged with real-time statistics of the expiry time and will serve as the main denominator of the priority. The results acquired from the conducted performance analysis using the relevant performance metrics have proven the MRT outperforms successfully from the legacy algorithms. The future work that would further provide contributions to the elevation of WiMAX includes the incorporation of mobile SS, correlating the different traffic classes in a holistic admission control and the complementary downlink algorithms analysis.
Acknowledgment
The authors wish to thank the reviewers for their constructive comments and suggestions helped in improving this research paper.
- Singh, A. Vaish, P. K. Keserwani, “Research Issues in Wireless Networks” International Journal of Advanced Research in Computer Science and Software Engineering (IJARCSSE), 4(2), 572 – 575, 2014.
- J. Lakkakorpi, A. Sayenko, J. Moilanen, “Comparison of Different Scheduling Algorithms for WiMAX Base Station” in Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC 2008), Las Vegas Nevada USA, 2008.
- N. A. El-fishawy, M. Zahra, M. Ebrahim, M. M El-gamala, “ModifiedCross-layer Scheduling for Mobile WiMAX Networks” in 28th National Radio Science Conference (NRSC), Egypt, 2011.
- C. So-In, R. Jain, AK Tamimi, “Scheduling in IEEE 802.16e Mobile WiMAX Networks: Key Issues and a Survey” IEEE Journal on Selected Areas in Communications, 27(2), 156–171, 2009.
- K. Komaljot, S. Amitabh. “Bandwidth-Aware Stochastic Uplink Scheduling in WIMAX Networks”, International Journal of Advance Research, Ideas and Innovations in Technology (IJARIIT), 2(3), 1-5, 2016.
- Ruey-Rong Su, I-Shyan Hwang, Bor-Jiunn Hwang, “A new cross-layer scheme that combines grey relational analysis with multiple attributes and knapsack algorithms for WiMAX uplink bandwidth allocation”, EURASIP Journal on Wireless Communications and Networking, 1-11, 2016.
- P. Chowdhury, I. S Misra, “A Fair and Efficient Packet Scheduling Scheme for IEEE 802.16 BWA Systems” arXiv preprint arXiv:1009.6091. 2010
- M. S. Arhaif, “Comparative Study of Scheduling Algorithms in WiMAX” International Journal of Scientific and Engineering Research, 2(2), 1 – 7, 2011.
- L. Nuaymi, WiMAX: Technology for Broadband Wireless Access, John Wiley & Sons, 2007.
- M. D. Priya, M. L. Valarmathi, D. Prithviraj. “Performance Analysis of Scheduling Mechanisms in WiMAX Networks”, SOP Transaction on Wireless Communications, 1(1), 40 – 49, 2014.
- S. R. Puranik, M. Vijayalakshmi, L. Kulkarni, “A Survey and Analysis on Scheduling Algorithms in IEEE 802.16e (WiMAX) Standard”, International Journal of Computer Applications, 79(12), 1 – 10, 2013.
- A. Kanda, A. K. Gill, A. K. “Comparative Study of Various Scheduling Schemes of Wimax” International Journal of Computer Science and Network Security (IJCSNS), 15(9), 91 – 94, 2015.
- P. Dhrona, N. A. Ali, H. Hassanein, “A Performance Study of Scheduling Algorithms in Point-to-Multipoint WiMAX networks” in 33rd IEEE Conference on Local Computer Networks (LCN), Montreal, AB, Canada, 2008.
- K. Vinay, N. Sreenivasulu, D. Jayaram, D. Das, “Performance Evaluation of End-to-End Delay by Hybrid Scheduling Algorithm for QoS in IEEE 802.16 Network” in IFIP International Conference on Wireless and Optical Communications Networks, Bangalore, India, 2006.
- A. Oad, S. K. Subramaniam, Z. A. Zukarnain, “Enhanced uplink scheduling algorithm for efficient resource management in IEEE 802.16” EURASIP Journal on Wireless Communications and Networking, 2015(1), 1 – 12, 2015.
- M. Gidlund, G. Wang, “Uplink Scheduling Algorithms for QoS Support in Broadband Wireless Access Networks” Journal of Communications, 4(2), 133 – 142, 2009.
- M. Oktay, H. A. Mantar, “A Real-time Scheduling Architecture for IEEE 802.16 – WiMAX Systems” in IEEE 9th International Symposium on Applied Machine Intelligence and Informatics (SAMI), Smolenice, Slovakia, 2011.
- N. A. Ali, P. Dhrona, H. Hassanein, “A Performance Study of Uplink Scheduling Algorithms in Point-to-Multipoint WiMAX Networks” Computer Communications, 32(3), 511 – 521, 2009.
- K Wongthavarawat, A Ganz, “Packet Scheduling for QoS Support in IEEE 802.16 Broadband Wireless Access Systems” International Journal of Communication Systems, 16(1), 81 – 96, 2003.
- M. Settembre, M. Puleri, S. Garritano, P. Testa, R. Albanese, M. Mancini, V. Lo Curto, “Computer Networks”, International Symposium on IEEE, 11 – 16, 2006.