ABSTRACT
WiMAX (Worldwide Interoperability for Microwave Access) is a new technology of WMAN (Wireless Metropolitan Area Network) whose specification was defined by IEEE 802.16 and supports the Quality of Service (QoS) for Media Access Control (MAC) layer. This study aims at the real-time scheduling of multimedia service to meet the demands of QoS in WMAN. Although, there have been three scheduling algorithms, Earliest Deadline First (EDF), Round-Robin (RR) and Weighted-Fair Queuing (WFQ) mostly adopted by many studies that are about scheduling of service class, it can not provide a good distribution for resources under complex conditions to meet user required QoS. Therefore, an efficient scheduler is very important for IEEE 802.16 to support QoS. This study proposes a novel scheduling scheme which combines with the Connection Admission Control (CAC) and the existing EDF(k) scheduling under Point to Multipoint (PMP) operation mode to resolve the scheduling of real-time multimedia. This study takes the dropping rate of multimedia transmission into account for the design of scheduling of real-time multimedia, because we will confront the transmission demand of real-time High Definition (HD) video for multimedia in the future and then the impact on data dropping will become important due to increasing demands of data transmission. The simulation results show that the proposed scheme can reduce more average latency to meet stricter deadline criteria than the original EDF scheduling. Furthermore, the proposed scheme can achieve better QoS with less resource for the point of view of system.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2010.1053.1067
URL: https://scialert.net/abstract/?doi=itj.2010.1053.1067
INTRODUCTIONS
According to the deployment experience for wireless communication, the service area is too small for small area of communication, such as wireless local area network (WLAN) and can not support mobile services (In-Stat/MDR, 2006; Pagani, 2004). The large area of communication, such as 2G and 3G, can support only low speed transmission and it can not provide the bandwidth demand for multimedia transmission. By contrast, based on the specification of IEEE 802.16x, WiMAX can satisfy such a bandwidth demand of high speed (Shahid et al., 2008; Ei and Furong, 2010). The WiMAX technology can provide higher speed transmission. However, how to reduce the loss of data transmission and to reduce the loads of base stations will be an important issue to maintain the QoS (Sarkar and Sachdeva, 2009; Luo and Li, 2008; Delicado et al., 2006). Although, the bandwidth needs to be managed effectively under scarce network resource for QoS, the tolerance of response time of information access will be a more important impact factor for the corresponding user when there are possibilities of losses and dropping for data transmission. Thus, it will be an important issue for the specification of IEEE 802.16x to design a scheduling that can provide high QoS and reduce additional overloads for base stations (Sarkar and Sachdeva, 2009; Luo and Li, 2008; Delicado et al., 2006).
For wireless communication, the scope of QoS is limited to satisfy the basic requirement that includes throughput, rate of package loss, latency and jitter for a specified application service (Menascé, 2002). Although, there have been defined QoS classification and method of bandwidth allocation for the present standard of IEEE 802.16x (IEEE Std 802.16e-2005, 2005), related schedulers are not included in the standard and they are opened and defined by manufacturing venders of communication devices. There have been many researches of QoS issue proposed for IEEE 802.16 standard (Cicconetti et al., 2007; Mai et al., 2007). Sayenko et al. (2006) designed a variety of service time slots that allow intermediary insertion for the applied order of time slot and also tried to find optimal parameter settings that take the overhead of MAC frame into account. According to the demands of different service classes, Wongthavarawat and Ganz (2003) designed a connection admission control and the framework of transmission scheduling that arranges similar service classes and is assisted by considerations of connection admission to meet the QoS demand of IEEE 802.16. Chu et al. (2002) proposed a basic QoS framework that is based on priorities of service classes and dynamic bandwidth allocations to achieve an effective scheduling strategy for providing QoS guarantees of IEEE 802.16. Based on two states Markov process to represent changes of channel state, Zhang et al. (2008) focused on VoIP to calculate the optimal output ratio of system. Lee et al. (2005) had also proposed a method that is similar to Zhang et al. (2008) focusing on the scheduling of VoIP and the design basis of the proposed scheme depends on connection situations. Except for scheduling mechanisms of MAC layer to guarantee the QoS, there have been other researches that are designed by cross layer protocol, such as Msadaa et al. (2007), or designed by other scheduling mechanisms, such as Shreedhar and Varghese (1996), to achieve the guarantee of QoS.
Effectively reducing the dropping rate of package can help the multimedia to be played more perfectly and it can achieve the QoS of multimedia service that is expected by users. The stable data transmission relies on the scheduling mechanism of MAC layer for IEEE 802.16x. There are four classes of service defined in the specification of IEEE 802.16x and they are Unsolicited Grant Service (UGS), real-time Polling Service (rtPS), non-real-time Polling Service (nrtPS) and Best Effort (BE), respectively (IEEE Std 802.16-2004, 2004; IEEE Std 802.16e-2005, 2005; Nair et al., 2004). Although, there are corresponding limitations for these services, the final purposes are to improve the QoS. Since it is evident that physical layer and MAC layer of IEEE 802.16 specification is different from other IEEE 802.11 family, the existing wireless schedulers can not meet the specification and limitations of IEEE 802.16x.
This study aims at real-time transmission of multimedia data, so the real-time feature must be taken into account first. According to the real-time demands of multimedia transmission, dynamic schedulers will have high priority for this study. Although, there have been fair based schedulers that improve the utilization of network resource proposed in literature, heavy overload is caused by the translations of floating computations. To reduce the overload that is caused by a scheduler, a periodic multi-processor scheduling in real-time operation system is applied to the scheduling of data transmission for IEEE 802.16 in this study. Based on the default environment that comprises only limited bandwidths, the connection admission control and the EDF(k) scheduling are applied to the scheduling of network bandwidth to achieve higher utilization with less bandwidth and the QoS will be improved further in this research.
BACKGROUNDS
Due to the extreme expansions of intelligent mobile appliances, interconnect networks have been evolved from wired media to wireless ones gradually. WiMAX is regarded as the major specification of 4G among developing 4G mobile communication technologies. However, there has been no clear definition for scheduling in MAC layer for WiMAX standard. There will be expected numerous connections and data transmissions appearing while WiMAX actually operating. It will be a serious test to achieve maximum utilization with limited network resource after the technology is deployed.
Wimax:
The framework of WiMAX specification is developed by the work group of IEEE 802.16. The IEEE 802.16 specification which is a protocol aiming at establishing connections between backbone networks and end users has been focusing on the WMAN technology. Opposite to other designs that spend expensive cost for infrastructure construction, the IEEE 802.16 standard provides the advantages of relatively cheaper cost of device construction, easy deployment and convenient expansion. IEEE 802.16 protocols consist of Subscriber Station (SS) and Base Station (BS) and a cell is composed of one BS and one or more SSs. The BS is charge of the issues of MAC, QoS and security for a given cell.
The transmission directions of WiMAX can be differentiated two ways: one is downlink channel, from BS to SS and the other is uplink channel, from SS to BS. For downlink, it operates with broadcast mode and provides relative information that includes both DL-MAP and UL-MAP messages concerning the information of bandwidth allocation for all SSs and the SS will know when the data will be transmitted and received according to the received MAP. For uplink, it must operate with multiplexing mode to distribute transmission time among SSs, because there will be many SSs that are ready to perform transmissions. The multiplexing mode is completed by Time Division Multiple Access (TDMA) and the framework of TDMA regards frame as a basic unit which can be divided into two subframes. They are downlink subframe and uplink subframe, respectively and each subframe is composed of several time slots whose amount can be dynamically adjusted according to the bandwidth allocation of BS. Besides, the BS will transmit data in the designated time slot.
Because WiMAX can support a variety of multimedia services and adopts connection-oriented mechanism that takes QoS into account first, the management of service streams that are based on data services is one of successful key points for WiMAX. In order to increase the utilization of spectrum, to meet the fairness among users and to support different QoS guarantees simultaneously, it is necessary to study and implement the kernel mechanism of QoS which comprises resource management and scheduling algorithms in the MAC layer.
Connection admission control:
The method of connection admission control has not been defined in WiMAX standard and it is left to be implemented by device venders and service providers. The method of Minimum Reserved Traffic Rate (MRTR) is currently adopted by most of them. Because UGS, ertPS, rtPS and nrtPS (IEEE Std 802.16-2004, 2004; IEEE Std 802.16e-2005, 2005; Nair et al., 2004) have their own MRTR and to be assumed as rmin(i, j) that represents the MRTR of the jth connection for the ith class of service flow, the CAC can be designed easily and summarized by Eq. 1.
(1) |
where, Ca and Ctotal represent the available capacity of current system and the total capacity of whole system, respectively. Once a new connection intends to add to the system, the newer Ca in Eq. 1 will be recalculated and checked if it is greater than 0 or not. It is worth mentioning that the BE will always enter the system if the BE is not limited by its MRTR and it will cause unsuitable side effect under such a heavy system load.
There have been many researches related to CAC proposed in literature and the admission control policy of batch-and-prioritized was proposed by Ayyagari and Ephremides (1999). Ayyagari and Ephremides (1999) adopted two parameters to be the CAC criteria and they are transmission rate and tolerance of delay time, respectively. Requested services are regarded as a request of batch service for the system and then the requested services will be served according to their priorities. The framework of admission control of wireless had been discussed by Xiao et al. (2000) and a cell is regarded as the unit of bandwidth management. Moreover, the overload probability Pco must be lower than the predefined probability PQoS and the Poc of each cell will be checked if its value is greater than PQoS or not for judging if the probability of system overload is greater than the predefined QoS for each fixed time period T. If the Pco is greater than PQoS, the connection request will be rejected.
Based on Kwon et al. (1998), CAC and bandwidth reallocation algorithm (CAC-BRA) had been proposed by Xiao et al. (2000). The authors thought that the system will allocate bandwidth to each request as possible as it can before the system load is not under overload in each cell for wireless networks. The maximum bandwidth of each request is designated as bk and some original requests will receive bandwidth that is below the excepted bk if the cell is under overload. For such a method not only decides a new request to be accepted or rejected, but also changes the amount of bandwidth that is requested originally. Once a new request arrives, some requests existing in the cell will be asked to reduce bandwidth for achieving the requirement of newer request.
WiMAX scheduling:
The major purpose of MAC layer for IEEE 802.16 standard is to increase the utilization of network resource under limited resource situation. There exist direct correlations between the scheduling mechanism and the QoS. In general, the usually adopted schedulers can be classified into two classes: one is fixed priority schedulers, such as Rate Monotonic (RM), which will give tasks higher priorities while the execution periods are shorter, because RM scheduling thinks that the task with shorter execution period will have higher real-time demands and should give them higher priorities to meet system requirements. Once the execution time and the period of each task are determined, the priority of each task for the execution process of system will never be changed that is so-called the scheduling algorithms of fixed priorities. The others are dynamical schedulers, such as EDF schedulers, which think the task with the earliest execution deadline has the highest priority. Because the priorities of task execution will be adjusted by execution deadlines, they are named dynamical schedulers.
Related to the studies of WiMAX scheduling, the scheduling of distributed fair priority queuing (DFPQ) was proposed for the QoS guarantee of IEEE 802.16 in Chen et al. (2005). The QoS of UGS is determined by fixed bandwidth allocation from a BS, so it will be excluded from scheduling considerations. Firstly, the BS will determine the maximum bandwidth of allocation for the QoS of each service, that is to say, the maximum quantum of transmission for each pass is predefined according to its corresponding QoS. The major purpose of DFPQ scheduling is not to let the queues of some QoSs occupy all bandwidth of system but to allocate bandwidth to the QoS queue of each service according to fairness, so the situation of starvation for each service queue will never occur. However, the delay times of service queues of high priority will increase due to fairness.
Based on the speed of network traffic, Weighted Round-Robin (WRR) scheduling (Katevenis et al., 1991) as shown in Fig. 1, adopts Round-Robin (RR) with increasing weight mechanism.
Fig. 1: | WRR scheduling |
Fig. 2: | DRR scheduling |
There is at least one packet processed for each queue and the weight of each queue is determined by the average length of each packet. If the average package length is unknown, the rate of packet transmission for its corresponding queue can not be determined. If the weight of a specified queue is 1, the queue will send out a packet. For long-term considerations, WRR scheduling is a fair scheduling algorithm, but WRR scheduling may be in unfair situations for the data flow of short term.
Deficit Round-Robin (DRR) scheduling (Shreedhar and Varghese, 1996), as shown in Fig. 2, adopts RR scheme and adds deficit mechanism that means to give a certain quota of packet for a queue. The difference between DRR and WRR is that the weights of DRR dont depend on the average packet length but depend on the allocated value of deficit counter of each nonempty queue. The deficit counter will be checked if there is any remaining deficit, which can be allocated, before DRR decides to send out a packet. If the deficit value is greater than the sent packet length, the packet of queue can be sent out and the value of counter will be subtracted by a deficit value that is the same as the amount of sent packet and the following packets of queue will be continuously judged in the same way. DRR will possess the best excellent condition under small size of packet and the small number of queues, but the unfairness that is the same as WRR will also occur for DRR under the data flow of longer service time.
In literature, the schedulers that were adopted by IEEE 802.16 are EDF, RR, WFQ (Weighted-Fair Queuing), DRR (Shreedhar and Varghese, 1996), WRR (Katevenis et al., 1991), FQ (Fair Queuing) (Demers et al., 1990) etc. and the related QoS metrics are compared among different schedulers and connection parameter settings. However, these researches aimed at the SS services that include four classes simultaneously and seldom one takes different service classes into account. Therefore, it is impossible to compare the differences among a variety of service classes for schedulers. The design of scheduler by Demers et al. (1990), can achieve fairness and ideal scheduling results, but complicated and unconventional computations of parameter settings easily cause heavy overload for the BS. Other simpler schedulers, such as RR and EDF, are not idea under the limitations of complex conditions and can not use network resources effectively. For past studies in scheduling designs, overload and resource utilization have not been taken into account simultaneously, so a newer design concept of scheduling should take both issues mentioned above into account simultaneously.
PROPOSED SCHEME
This study aims at the scheduling of rtPS class of multimedia services in the MAC layer for IEEE 802.16 and applies the EDF(k) scheduling to multimedia services for reducing the average latency. Besides, it can also improve the situation of missing deadline that is scheduled by the EDF scheduling.
Fig. 3: | Flow of proposed scheduling strateg |
Based on the transmitted protocol information, such as the demand of maximum or minimum bandwidth, maximum delay etc., within connection processes, this paper combines the CAC process and the EDF(k) scheduling to propose a novel scheduling that is suitable for the scheduling of IEEE 802.16 real-time multimedia services and can reduce the rate of packet loss of multimedia transmission for guaranteeing QoS.
Process of scheduling strategy:
This study focuses on the Point-to-Multi-Point (PMP) operation mode and applies the EDF(k) algorithm to the scheduling of multimedia services at MAC layer and discusses the impact on related parameter settings that have concern with bandwidth requests between SSs and the BS. The process of scheduling strategy, as shown in Fig. 3, specifies how to apply the proposed rtPS CAC to judge if the bandwidth is enough to admit the connection requests or not and then to apply the EDF(k) algorithm for scheduling the requests of multimedia service proposed in this research.
In the proposed scheduling strategy, the BS will ascertain that if the requested service is rtPS class or not when a SS asks the BS for a connection request. If the service of connection request is the rtPS class, the CAC of rtPS will judge if the connection can be admitted or not according to related parameters of bandwidth for connection requests. If the CAC of rtPS admits the requested connection, the BS will schedule the service of rtPS class according to the EDF(k) algorithm. On the contrary, if the CAC of rtPS doesnt admit the requested connection, the SS should not ask for a connection request until next polling period.
CAC of rtPS:
This study regards the demand of requested bandwidth of the connection establishment as the key factor that is applied to determine if the connection can be admitted or not. If the available bandwidth, abbreviated to be BW_available, is greater than or equal to the maximum sustained traffic rate (MSTR) of connection i, the requested connection will be admitted and established. If the available bandwidth is smaller than the MSTR, the allocated bandwidth to BE can be collected and reallocated to the requested connection with the available bandwidth due to the lowest service priority for BE. The requested connection will be admitted if the sum of available bandwidth and collected bandwidth from BE service is greater than the MSTR of rtPS class. If the sum of available bandwidth and collected bandwidth from BE service is still less than the MSTR of rtPS class, the Minimum Reserved Traffic Rate (MRTR) will be taken into account for determining if the request can be admitted in MRTR mode.
According to the requested amount of bandwidth for the rtPS service, the CAC of rtPS class can be summarized as three steps and shown as follows:
The major task of step 1 is to pass four parameters and they are Conn[i]_mstr, representing the Maximum Sustained Traffic Rate (MSTR) of connection i,
Conn[i]_mrtr, representing the minimum Reserved Traffic Rate (MRTR) of connection i, BW_available, representing available bandwidth and BW_BE, bandwidth of BE, respectively. In step 2, the demand of bandwidth is judged according to connection request and the connection admission is also determined in this step. For the final step, the number of connections will be increased after the connection request is admitted.
Applying EDF(k) to the scheduling of IEEE 802.16:
According to the research by Goossens et al. (2003), if a periodic system τ of m processors that adopts priority-oriented scheduling can provide m(2-1/m) processors, all of the tasks in the system can be finished before their deadlines. Although Goossens et al. (2003) proposed the scheduling of EDF-US[m(2-1/m)] that can meet the deadlines for all tasks and it seems a high efficiency scheduling, additional processors need to be added to the system. In other words, the scheduling of EDF-US[m(2-1/m)] will be a priority-oriented scheduler that needs more system resources. In order to meet the deadlines of all tasks and not to add extra processors for a system, the EDF(k) scheduling was proposed for resolving such a problem by Goossens et al. (2003). If the EDF(k) scheduler was applied to the scheduling of tasks for a periodic system τ, only m, which represents the required minimum number of processors for system τ, processors were taken to let all tasks be executed before their deadlines. The utilization ui can be defined by Eq. 2, where Ci is the execution requirement and Pi is the execution period for task i, respectively and U(τk) is the accumulated utilization for system τ.
(2) |
Furthermore, the value of m can be derived from Eq. 3 to 5 and the relation, as shown in Eq. 3, between mmin and k should be defined first. The following step is to find the value of k and it is so-called kmin that can be derived from Eq. 4 based on mmin. Finally, k can be substituted by kmin in Eq. 5 and then m can be obtained.
(3) |
(4) |
(5) |
Cottet et al. (2002) and Lee et al. (2006, 2008) also showed that if the EDF(k) scheduler is applied to a periodic task system τ which is possessed of m processors, all executed tasks will meet their own execution deadlines. In Goossens et al. (2003), the research target focuses on a periodic operating system and the adopted parameters belong to the terms of operating system for the computation process of scheduling algorithm. Therefore, the same settings of parameters in operating system can not be applied to the network environment of IEEE 802.16 for this study. There must be the parameter correspondents between the IEEE 802.16 standard and operating systems to meet the basis of theory and corresponding verifications.
The calculation equation of utilization must be transferred first, because individual utilization of connection should be calculated beforehand for determining two key values kmin and mmin of the EDF(k) scheduler. The Ci represents the execution requirement of task i for a periodic system, but comparatively Ci represents the bandwidth requirement of connection i for IEEE 802.16 standard; in the same way, Pi represents the execution period of task i for period system and Pi represents call arrival rate that follows Poisson distribution. The task utilization of a periodic system is in proportion to the bandwidth utilization ui for IEEE 802.16 network. Thus, the utilization of connection i, represented by Conn[i]_u, can not obtain by Eq. 2 directly and can be derived from Eq. 6, where BW_req[i], c_arrival, s_time, BC and T are the bandwidth requirement of connection i, call arrival rate, service time, bandwidth capacity and total execution time of system, respectively and the service time of each connection follows the exponential distribution. The flow of applying the EDF(k) algorithm to the scheduling of IEEE 802.16 can be summarized as four steps and the details are shown as follows:
(6) |
There are four classes of service priorities that are based on IEEE 802.16 standard declared at step 1 and the related parameter declarations of bandwidth and connection are also described in step 1. At step 2, the utilization of individual connection is calculated by the parameters that include required bandwidth, call arrival rate, connection service time, the sum of connected time and the sum of bandwidth for a system and the accumulated utilization of a system is also calculated at step 2. At step 3, connections are ranked by the decreasing order of their utilization and the kmin and mmin are derived from Eq. 4 and 5, respectively. Finally, the
EDF(k) algorithm is applied to the scheduling with two parameters which are mmin and Conn_Count, respectively. The parameters, mmin and Conn_Count, will be regarded as the criteria of applying the EDF algorithm or FIFO one when the EDF(k) algorithm is called by the connection scheduling.
RESULTS AND DISCUSSION
According to the proposed design architecture, the simulations are based on PMP mode and designed by WiMAX module of NS-2 network simulator (Belghith and Nuaymi, 2008) to aim at the scheduling experiments of rtPS class on MAC layer. There will be several simulation scenarios that are concerned with the parameter settings proposed to compare QoS metrics while different schedulers are applied to the system.
Simulation assumptions:
The architecure of simulation network which adopts the operation mode of PMP, as shown in Fig. 4, based on IEEE 802.16-2004 standard is composed of one BS and several SSs. The BS is connected to destination nodes with wired networks and provides limited bandwidth for SSs with the allocation stratgy of fixed bandwidth and certain conncections.
Although there are both Time Division Duplex (TDD) and Frequency Division Duplex (FDD) access modes existing in the physical layer of IEEE 802.16, most of the manufacturing venders in Europe suggest adopting TDD and FDD for long term evolution (LTE) for WiMAX to avoid duplicate investing in further integration of both 4G technologies. Therefore, the TDD mode is adopted for the simulation of physical layer of network and occurring errors on physical layer are not considered in the simulations.
The major parameters of rtPS connection are Minimum Reserved Traffic Rate (MRTR), Maximum Sustained Traffic Rate (MSTR), maximum latency and request/transmission policy, respectively. The most important one is maximum latency among four parameters, because there are time limitations for a video frame. If the video packets arrive late, it will cause a time lag of playing video. Furthermore, the expired packets will be regarded as noneffective packets and be dropped. Thus, such a service class must meet the delay time and can not exceed the maximum latency.
The header types of MAC layer can be classified into two classes: one is the native type and the other is the type of Bandwidth Request (BR). The header of native type is applied to transmitting data or MAC message and the header of BR is applied to asking for more bandwidth of uplink. The maximum length of MAC Protocol Data Unit (PDU) that is composed of header, data content and Cyclical Redundancy Check (CRC) is 2048 bytes. In PMP mode, the norm of MAC specifies automatic repeat request (ARQ), fragmentation, encapsulation and admission management of sub-header. The sub-headers of ARQ and admission management are applied to exchanging ARQs and statuses of bandwidth allocation between the BS and SSs and the sub-headers of fragmentation and encapsulation are applied to allocating transmission bandwidth rapidly.
For simulations, the CRC of MAC header will not be considered and multimedia data has the precedence that considers downlink form BS to SS for transmission. All of SSs are based on IEEE 802.16-2004 standard and only one connection is established between each SS and BS.
Fig. 4: | Simulated network architecture |
Table 1: | Parameter settings of simulation network. |
According to the stipulations of researches (IEEE Std 802.16-2004, 2004; IEEE Std 802.16-2005, 2005; Nair et al., 2004), it will provide single service for one connection for simplifying simulations, so each connection will ask the BS for one kind of service.
The related settings of parameters are shown in Table 1 that includes eleven parameters adopted for simulations. The details are described as follows: The OFDM technique and TDD access mode are adopted for PHY layer. 64-QAM 3/4 is adopted for channel modulation and the length of time slot is 108 bytes; the BS can provide 7 MHz bandwidth, transmit 200 frames per second and contain 151 slots for each frame; the transmission ratio of uplink to downlink can be dynamically adjusted according to the demand; both fragmentation and encapsulation will not be adopted for packet transmission, so the PDU of MAC layer can transmit in best effort. Therefore, the parameter settings of CRC and ARQ will be turned off for simulations.
The parameter settings of rtPS and BE classes are shown in Table 2, which includes nine parameters adopted for simulations. The details are described as follow: The MSTR defines the peak rate of information transmission, that is to say, the maximum bandwidth can be provided by the BS. For simulations, the MSTR of rtPS class is 2 Mbps and the one of BE is defined 7 Mbps according to the requirements of simulation for ms for rtPS class and none for BE class due to no QoS guarantee needed for BE class conveniently comparing the utilization of system resource after scheduling; in opposition to the MSTR, the MRTR that is the minimum reserved bandwidth provided by BE class is defined to be 512 kbps.
Table 2: | Parameter settings of rtPS and BE |
Because the priority of BE class is the least one for the QoS design of IEEE 802.16, the remaining bandwidth will be allocated to BE class while satisfying other service classes. Therefore, the BS should not reserve any bandwidth for BE class and the default value of MRTR for BE class is set none in simulations. The maximum latency that defines the delay time of maximum toleration is regarded as 10.
The traffic priority defines the priority of transmission and the value is between 0 and 7 where the bigger value represents the bigger priority and the default value is 0. Because this paper aims at multimedia services, the default value of rtPS class is set 7 and the parameter setting of BE class is the default value 0. The policy of transmission request defines which bandwidth request will be adopted or not adopted and the setting value of rtPS class is set Bit #6 and the same as BE due to no adoption of CRC in simulations.
Simulation scenarios:
Although there have been many studies (Wongthavarawat and Ganz, 2003; Cicconetti et al., 2007; Sarkar and Sachdeva, 2009) proposed to discuss the scheduling of services in IEEE 802.16, there no one aims at discussing only the scheduling of the rtPS class that is specified as real-time multimedia service in IEEE 802.11. Therefore, the design scenarios of simulation can only focus on how to compare the proposed scheduling with the EDF scheduling for real-time multimedia service and compared metrics include latency, jitter, throughput and rate of packet loss. There are two simulation scenarios are proposed and compared in this study.
Fig. 5: | Simulation topology of case 1 |
Fig. 6: | Simulation topology of case 2 |
Table 3: | Parameter settings of case 1 |
Case 1:
The simulation case 1 consists of six SSs, one BS and one destination node, as shown in Fig. 5. The rtPS class is adopted by five SSs and the BE class is adopted by the other one. Besides, the UDP protocol is adopted by all of them. The compared schemes are the EDF scheduling and the proposed one, respectively. The simulations are executed two rounds and they are the EDF scheduling and the proposed one, respectively. In the first round simulation, the BS will adopt the EDF scheduling for rtPS class and adopt the RR scheduling for BE class. In the second round simulation, the BS will adopt the proposed scheduling for rtPS class and adopt the RR scheduling for BE class. For the connection settings of rtPS class, the setting value of MSTR is 2 Mbps and the setting value of MRTR is 512 kbps and the bandwidth demand is 7 Mbps for BE class, as shown in Table 3 that describes the detail information for the EDF algorithm and the proposed scheduling for simulations of case 1. Both the two round simulations are executed 10000 times, respectively and executed 60 sec for each time. The compared performance metrics are latency, jitter, throughput and rate of packet loss, respectively.
Case 2:
The simulation of case 2 consists of 4 SSs, one BS and one destination node, as shown in Fig. 6. The rtPS class and the UDP protocol are adopted by all SSs. The compared schemes are the EDF scheduling and the proposed one, respectively. For the connection settings of rtPS class, the setting values of MSTR and MRTR are 2 Mbps and 512 kbps, respectively. In the simulation process, the SSs ask for connections in batch mode and issue a connection request each 5 sec, that is to say, four SSs have issued connection requests after 15 sec. At thirtieth second, SS1 issues the request of changing bandwidth and the setting value of MSTR is changed over 1 Mbps and the setting value of MRTR keeps up 512 kbps. In the same way, the requests of changing bandwidth also occur in the following connection requests of SS2, SS3 and SS4 and the setting values of MSTR and MRTR are the same as SS1 which has changed the setting values after the thirtieth second. Besides, the simulation events that indicate when the bandwidth requests are changed for four SSs within simulation executions are shown in Table 4 and it specifies the simulation events adopted during simulations for four SSs.
Table 4: | Simulation events of case 2 |
The simulation scenario aims at discussing the impact on the scheduling schemes while the connection requests change bandwidth request for SSs. Both the two scheduling schemes are executed 10000 times, respectively and executed 60 sec for each time. The compared performance metrics are latency, jitter, throughput and rate of packet loss, respectively.
Simulation results and discussions:
There are two kinds of simulation results that compare performance metrics of multimedia service between the proposed scheduling and the EDF scheduling are illustrated and discussed in this paper and the performance metrics include latency, jitter, throughput and rate of packet loss.
Simulation results of case 1:
According to the simulation results, as shown in Fig. 7, the average latency of the EDF scheduling is approaching to 10 msec and the average latency of the proposed one is approaching to 5 msec. Because the parameter setting of frame interval is 5 msec, the latency should be distributed over a multiple of 5 msec. In the simulations of case 1, the BS provides 7 Mbps bandwidth that can meet the demands of both the EDF scheduling, requiring 2.5 M (512 kx5 = 2.5 M) bandwidth and the proposed scheduling, requiring 7 M (2 M 3 + 512 kx2 = 7 M) bandwidth, so the latencies of both the scheduling schemes are below 10 msec. However, the average latency of the proposed scheduling is lower than the EDF scheduling and it signifies that the proposed scheduling can reduce average latency compared to the EDF scheduling and meet stricter deadline limitations.
Fig. 7: | Latency comparison of case 1 |
Many packets must be queued and wait for transmissions while the network traffic is large, so the transmission time from the sending node to the destination node is uncertainly identical for each packet and the difference is so-called jitter. Thus, the jitter has relation with delay variance. The simulation results, as shown in Fig. 8, show that the mean time of jitter of the EDF scheduling is between 4.5 and 5.0 msec and the mean time of the proposed scheduling is about 1.0 msec. According to both twisted lines as shown in Fig. 8, the average jitter of the proposed scheduling is lower than the EDF scheduling and the value fluctuation of the proposed scheduling is also smaller than the EDF scheduling, that is to say, the proposed scheduling can reduce more jitter than the EDF scheduling in the same operation situation of network.
There will be some packet losses for transmissions while the network traffic is heavy and exceeds the capacity of network device or transmission media or the quality of transmission line is unstable. The rate of packet loss is an important indicator for judging if the network traffic is under congestion or not. If a scheduling has lower rates of packet loss under peak traffic, it means that the scheduling can provide a better QoS for users. As shown in Fig. 9, the average rate of packet loss of the EDF scheduling is between 4.0 and 4.5% and the average rate of packet loss of the proposed scheduling is about 1.5%. According to the results of both twisted lines as shown in Fig. 9, the bandwidth that is provided by the proposed scheduling is more than the EDF scheduling, but the average rate of packet loss of the proposed scheduling is only one third of the EDF scheduling. It implies that the proposed scheduling can achieve lower rates of packet loss and provide better QoS than the EDF scheduling in the same situation of network operation.
Fig. 8: | Jitter comparison of case 1 |
Fig. 9: | Comparison of rate of packet loss of case 1 |
In order to compare the throughputs between the EDF scheduling and the proposed scheduling in case 1, the simulations are conducted individually and the results of throughput of case 1 are shown in Fig. 10 and 11, respectively. Firstly, for the results of throughput of the EDF scheduling in case 1, as shown in Fig. 10, 5 service requests of rtPS will ask 2.5 Mbps (512 kbpsx5) bandwidth demands for SSs, so the average throughput of rtPS is less than 2.5 Mb. The remaining bandwidth that is less than 4.5 Mb is allocated to the BE service and then the total throughputs of the EDF scheduling algorithm are about 6.5 Mb due to about 4% rate of packet loss caused by the EDF scheduling. Secondary, for the results of throughput of the proposed scheduling in case 1, as shown in Fig. 10, the bandwidth demands of rtPS for 5 SSs are about 7Mbps (2 Mbpsx3 + 512 kbpsx2), so all of the available bandwidth is allocated to the rtPS and the average throughput is approaching to 7 Mb. After allocating the remaining bandwidth to the BE service, the total throughputs are about 6.9 Mb due to 1% rate of packet loss caused by the proposed scheduling. According to the comparisons between Fig. 10 and 11, the proposed scheduling can distribute more system resource to rtPS services than the EDF scheduling. In other words, the proposed scheduling can meet the demand of multimedia transmission.
Fig. 10: | Throughput of EDF scheduling of case 1 |
Fig. 11: | Throughput of proposed scheduling of case 1 |
Summarizing the above simulation results of case 1, the proposed scheduling has superiors in four QoS metrics of multimedia service. It implies that the proposed scheduling can provide better QoS than the EDF scheduling.
Simulation results of case 2:
The simulation results of latency of case 2 are shown in Fig. 12 and it shows that the average latency of the proposed scheduling varies with bandwidth demand. The average latency of the EDF scheduling will increase while the bandwidth demand of connection increases; on the other hand, the average latency of the proposed scheduling will decrease while the bandwidth demand of connection decreases. However, the average latency of the EDF scheduling has kept about 8.4 msec since the twentieth seconds later, because the allocated bandwidth has not been changed.
Fig. 12: | Latency comparison of case 2 |
Fig. 13: | Jitter comparison of case 2 |
As shown in Fig. 11, the average latency of the EDF scheduling is still kept in the same level after the request of MSTR changing is proposed by SSs. The reason is that the MRTR mechanism is adopted by the CAC of rtPS for the EDF scheduling algorithm, so the average latency of rtPS has still kept 8.4 ms since twentieth second even though the MSTR has been changed. Comparing to both twisted lines in Fig. 11, the average latency of the proposed scheduling is much lower than the EDF scheduling; that is to say, the proposed scheduling can reduce more average latency than the EDF scheduling when the same requests of connection bandwidth are updated by SSs.
As shown in Fig. 13, the jitter values of the EDF scheduling jump uncertainly between 3.5 and 4.5 msec and the jitter values of the proposed scheduling distribute uniformly in 0.5 msec. The simulation results also show that the jitter values and variances of the proposed scheduling are lower than the EDF scheduling one, so it means that the proposed scheduling can keep lower jitters and reduce more jitter variances than the EDF scheduling when the same request of connection bandwidth are updated by SSs.
Fig. 14: | Comparison of rate of packet loss for case 2 |
Fig. 15: | EDF throughput of case 2 |
The rate of packet loss of case 2 is shown in Fig. 14. The rate of packet loss of the proposed scheduling is similar to its average latency that varies with bandwidth demand and its value is between 1.5 and 3.0% and the values of the EDF scheduling are between 3.0 and 4%. The proposed scheduling can provide more bandwidth for SSs than the EDF scheduling, because its rate of packet loss is lower that the EDF scheduling; that is to say, the proposed scheduling can reduce more rate of packet loss effectively and provide better QoS than the EDF scheduling when the same request of connection bandwidth are updated by SSs.
In order to compare the throughputs between the EDF scheduling and the proposed scheduling in case 2, the simulations are conducted individually and the results of throughput of case 2 are shown in Fig. 15 and 16, respectively. As shown in Fig. 15, the throughput of the EDF scheduling has still been kept in the same value after the MSTR is asked by SSs. The reason is that the MRTR mechanism is adopted by the CAC of rtPS for the EDF scheduling, so the allocated bandwidth will not be changed.
Fig. 16: | Throughput of the proposed scheduling of case 2 |
Thus, the throughput has been kept 2 Mb after simulation conducted 20 sec and the total throughput is about 6.6 Mb due to the rate of packet loss.
As shown in Fig. 16, the throughput of rtPS for the proposed scheduling will vary with the MSTR, because the MSTR is taken into account first for the CAC of rtPS. The MRTR will be regarded as the second consideration while the available bandwidth can meet the demand of MSTR and the advantages are that the available bandwidth can be allocated effectively to meet the bandwidth demand of rtPS as possible as it can and the jitter and the rate of packet loss will also be reduced.
Summarizing the above simulation results of case 2, the proposed scheduling algorithm has superiors in four QoS metrics of multimedia service. It implies that the proposed scheduling can provide better QoS than the EDF scheduling for different scenarios. According to the simulation results of scenario 1 and 2, no matter how the proposed scheme is operating in different scenarios, it can achieve better QoS than the existing EDF scheduling.
CONCLUSIONS
In this study, a CAC framework of WiMAX that is based on the specification of IEEE802.16 standard is proposed and some related issues of QoS that are not specified in the specification are also designed and described as follows:
• | Definitions of service class and researches of related parameters |
• | Design of admission control |
• | Design of bandwidth allocation |
• | Design of scheduling algorithm |
This study aims at the transmission of rtPS class of multimedia for the MAC layer in IEEE 802.16 and a CAC mechanism of rtPS and the EDF(k) scheduling are combined to design a novel scheduling scheme of multimedia transmission for IEEE 802.16 standard. The exchange of protocol information during the process of connection establishment is applied to the proposed scheme, so more transmission latency, jitter, rate of packet loss can be reduced and more throughputs increase for multimedia services than the existing EDF scheduling. The simulation results show that the QoS metrics of rtPS for the proposed scheduling are superior to the existing EDF scheduling in different scenarios, so the proposed can provide better QoS to meet users demands and achieve higher system utilization.
The exiting EDF(k) scheduling is combined with CAC mechanism for a new application in this paper. For theory application and innovation, this paper introduces the EDF(k) scheduling from traditional real-time operating system into the application domain of communication first and a modified method that applies the EDF(k) scheduling is proposed for the scheduling of MAC layer. Therefore, the major contribution in academic field is to improve the point of view for application, to expand the application domain of theory and to improve the performance of existing technology.
Due to the technology evolution of wireless network, the transmitted services of network have been upgraded as users expect. The demand of data transmission is also evolved into multimedia and the requirement of QoS has also been improved at the same time. There have evidently grown for investments in the research and development of wireless technology for worldwide governments. This study focuses on the improvements of transmission QoS and system performance for WiMAX network and it can be also be applied to different kinds of wireless systems that need to apply a scheduling mechanism to its services. Therefore, the proposed scheme can be a construction template of wireless networks nowadays or in the future. Moreover, the real-time scheduling can be expanded to other application domains that have similar application architectures due to the successful application of the proposed scheme in the scheduling of real-time multimedia of WiMAX.
ACKNOWLEDGMENT
This study was supported in part by the National Science Council of Taiwan under the Grants NSC 98-2221-E-412-003.
APPENDIX
ARQ | = | Automatic repeat request |
BE | = | Best effort |
BS | = | Base station |
BR | = | Bandwidth request |
CAC | = | Connection admission control |
CAC-BRA | = | CAC and bandwidth reallocation algorithm |
CRC | = | Cyclical redundancy check |
DFPQ | = | istributed fair priority queuing |
DRR | = | Deficit round-robin |
EDF | = | Earliest deadline first |
FDD | = | Frequency division duplex |
FQ | = | Fair queuing |
HD | = | High definition |
LTE | = | Long term evolution |
MAC | = | Media access control |
MRTR | = | Minimum reserved traffic rate |
MSTR | = | Maximum sustained traffic rate |
nrtPS | = | non-real-time polling service |
PDU | = | Protocol data unit |
PMP | = | Point to multipoint |
QoS | = | Quality of service |
RR | = | Round robin |
rtPS | = | Real-time polling service |
SS | = | Subscriber station |
TDMA | = | Time division multiple access |
UGS | = | Unsolicited grant service |
VoIP | = | Voice over internet protocol |
WFQ | = | Weighted-fair queuing |
WiMAX | = | Worldwide interoperability for microwave access |
WLAN | = | Wireless local area network |
WMAN | = | Wireless metropolitan area network |
WRR | = | Weighted round-robin |
REFERENCES
- Ayyagari, D. and A. Ephremides, 1999. Admission control with priorities: Approaches for multi-rate wireless systems. Mobile Networks Appl., 4: 209-218.
CrossRefDirect Link - Belghith, A. and L. Nuaymi, 2008. Design and implementation of a QoS-included WiMAX module for NS-2 simulator. Proceedings of the 1st International Conference on Simulation Tools and Techniques for Communications, Networks and Systems and Workshops, March 3-7, Marseille, France, pp: 40-54.
Direct Link - Cicconetti, C., A. Erta, L. Lenzini and E. Mingozzi, 2007. Performance evaluation of the IEEE 802.16 MAC for QoS Support. IEEE Transact. Mobile Comput., 6: 26-38.
Direct Link - Delicado, J., L. Orozco-Barbosa, F. Delicado and P. Cuenca, 2006. A QoS-aware protocol architecture for WiMAX. Proceedings of Electrical and Computer Engineering 2006, May 7-10, Ottawa, Ont, pp: 1779-1782.
CrossRefDirect Link - Ei, T. and W. Furong, 2010. Trajectory-aware vertical handoff protocol between WiMAX and 3GPP networks. Inform. Technol. J., 9: 201-214.
CrossRefDirect Link - Goossens, J., S. Funk and S. Baruah, 2003. Priority-driven scheduling of periodic task systems on multiprocessor. Real-Time Syst., 25: 187-205.
CrossRefDirect Link - Kwon, T., Y. Choi, C. Bisdikian and M. Naghshineh, 1998. Call admission control for adaptive multimedia in wireless/mobile networks. Proceedings of ACM Workshop on Wireless Mobile Multimedia, Oct. 25-30, Dallas, Texas, United States, pp: 111-116.
Direct Link - Lee, H., T. Kwon and D.H. Cho, 2005. An enhanced uplink scheduling algorithm based on voice activity for voip services in IEEE 802.16d/e system. IEEE Commun. Lett., 9: 691-693.
Direct Link - Lee, L.T., H.Y. Chang and S.W. Chao, 2008. A hybrid task scheduling for multi-core platform. Proc. 2008 2nd Int. Conf. Future Generation Commun. Networking Symposia, 5: 40-45.
CrossRefDirect Link - Luo, S. and Z. Li, 2008. An efficient QoS-aware resource allocation scheme in WiMAX. Proc. Intel. Inform. Tech. Appl. 2nd Int. Symp., 2: 796-800.
CrossRefDirect Link - Msadaa, I.C., F. Filali and F. Kamoun, 2007. An adaptive QoS architecture for IEEE 802.16 broadband wireless networks. Proceedings of IEEE International Conference on Mobile Adhoc and Sensor Systems, Oct. 8-11, Pisa, Itly, pp: 1-3.
Direct Link - Nair, G., J. Chou, T. Madejski, K. Perycz, D. Putzolu and J. Sydir, 2004. IEEE 802.16 medium access control and service provisioning. Int. Technol. J., 8: 213-228.
Direct Link - Pagani, M., 2004. Determinants of adoption of third generation mobile multimedia services. J. Interactive Marketing, 18: 46-59.
CrossRefDirect Link - Sarkar, M. and H. Sachdeva, 2009. A QoS aware packet scheduling scheme for WiMAX. Proceedings of the World Congress on Engineering and Computer Science, Oct. 20-22, San Francisco, USA., pp: 802-816.
Direct Link - Sayenko, A., O. Alanen, J. Karhula and T. Hamalainen, 2006. Ensuring the QoS requirements in 802.16 scheduling. Proceedings of the 9th ACM International Symposium on Modeling Analysis and Simulation of Wireless and Mobile Systems, October 2-6, 2006, Terromolinos, Spain, pp: 108-117.
Direct Link - Shahid, M.K., T. Shoulian and A. Shan, 2008. Mobile broadband: Comparison of mobile WiMAX and cellular 3G/3G+ technologies. Inform. Technol. J., 7: 570-579.
CrossRefDirect Link - Shreedhar, M. and G. Varghese, 1996. Efficient fair queuing using deficit round robin. IEEE Trans. Network., 4: 375-385.
Direct Link - Wongthavarawat, K. and A. Ganz, 2003. Packet scheduling for quality support in IEEE 802.16 broadband wireless access systems. Int. J. Commun. Syst., 16: 81-96.
CrossRefDirect Link - Xiao, Y., C.L.P. Chen and Y. Wang, 2000. An optimal distributed call admission control for adaptive multimedia in wireless/mobile networks. Proceedings of the 8th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, Aug. 29-Sept. 1, IEEE Computer Society, Washington DC, USA., pp: 477-477.
Direct Link - Mai, Y.T., C.C. Yang and Y.H. Lin, 2007. Cross-layer QoS framework in the IEEE 802.16 network. Proceedings of 9th International Conference on Advanced Communication Technology, Volume 3, February 12-14, Phoenix Park, Korea, pp: 2090-2095.
Direct Link