# On the Modelling of the Mobile WiMAX (IEEE 802.16e) Uplink Scheduler

Authors: Darmawaty Mohd Ali; Kaharudin Dimyati
Journal: Modelling and Simulation in Engineering
 (2010)

---

## Abstract

Packet scheduling has drawn a great deal of attention in the field of wireless networks as it plays an important role in distributing shared resources in a network. The process involves allocating the bandwidth among users and determining their transmission order. In this paper an uplink (UL) scheduling algorithm for the Mobile Worldwide Interoperability for Microwave Access (WiMAX) network based on the cyclic polling model is proposed. The model in this study consists of five queues (UGS, ertPS, rtPS, nrtPS, and BE) visited by a single server. A threshold policy is imposed to the nrtPS queue to ensure that the delay constraint of real time traffic (UGS, ertPS, and rtPS) is not violated making this approach original in comparison to the existing contributions. A mathematical model is formulated for the weighted sum of the mean waiting time of each individual queues based on the pseudo-conservation law. The results of the analysis are useful in obtaining or testing approximation for individual mean waiting time especially when queues are asymmetric (where each queue may have different stochastic characteristic such as arrival rate and service time distribution) and when their number is large (more than 2 queues).


---

## Body

## 1. Introduction

Mobile WiMAX is a promising Broadband Wireless Access (BWA) that has received great interest due to the need for data access at all time. The salient features of the Mobile WiMAX that are attractive are the capability of handling the quality of service (QoS) and the physical layer (PHY), scalability, and the medium access control (MAC) layer, which are exclusively designed to meet different kinds of traffic. IEEE 802.16e does define the means and method in supporting the different classes of traffic. However, it does not specify how to effectively schedule and guarantee the QoS according to the different types of applications. An extensive numbers of scheduling schemes have been proposed by researchers, and the most common approach has been by means of simulation. Simulation is a widely used technique for computing the performance measures of all kinds of models. With such manner, the performance of the Mobile WiMAX system in terms of delay, throughput, jitter, and packet loss is evaluated. However, despite of the flexibility, simulation may be rather inefficient in many cases and results based on simulation are relatively inaccurate as compared to the mathematical analysis [1].A number of works have been focusing on evaluating the analytical model of the scheduling scheme in the context of Mobile WiMAX system. The authors in [2] put forward the idea of scheduling algorithm for the voice over IP (VoIP) services. The algorithm is claimed to solve the problem of the waste of the uplink resources algorithm caused by Unsolicited Grant Service (UGS) and MAC overhead and access delay due to the Real-Time Polling Service (rtPS) algorithm. The system model is represented as a one-dimensional Markov chain with an on-off model for the voice traffic. From here the average number of voice users in on-state, the maximum number of users that can be serviced in one MAC frame, the system throughput, and the access delay were established.In [3] a novel scheduling scheme was presented to provide QoS satisfaction and service differentiation in terms of delay. The time window, Ti, of the Proportional Fairness (PF) is manipulated to distinguish the service and QoS assurance of each queue. The mean queue length and mean waiting time of the system is derived using the M/M/1 Markov model.The study in [4] concentrates on the performance analysis for the polling (rtPS and Non-Real-Time Polling Service (nrtPS)) service based on an approximation model known as the exhaustive time-limited polling model with vacation. Furthermore, the model assumes that the UGS and polling service (PS) classes are completely partitioned which allow for independent analysis of the PS traffic. The blocking probability, mean residence time, and waiting time distribution are derived from the BMAP/D/1/K model.The author in [5] formulated the analytical model taking into account the modulation and coding scheme (MCS) as well as the signaling overhead in the downlink. The VoIP packets are scheduled based on the First-In-First-Out (FIFO) policy, and the traffic is modeled as an exponentially distributed on-off model. The aggregate VoIP traffic from the N subscriber station (SS) is represented as the two-state Markov-modulated Poisson process (MMPP). The analysis is done independently for the Extended-Real Time Polling Service (ertPS), UGS, and rtPS.Though the above study focused on the analytical model as part of the findings, the model is derived assuming that the traffic from different classes in the Mobile WiMAX is totally separated which allows for independent analysis. However, this is not always true in the actual condition. Mobile WiMAX networks are designed  to allow for the coexistence of various types of traffic ranging from real-time traffic such as VoIP and video conferencing to non-real-time traffic such as file transfer and e-mail service through various scheduling services. Thus, employing a single scheduling service would lead certain applications to fail to function properly. For instance, delay is the most critical issue for the real-time traffic and should not  suits  with scheduling service without the QoS requirement (such as nrtPS and BE) considering that the performance could deteriorate.In this paper, different scheduling services of the Mobile WiMAX are combined to obtain the weighted sum of mean waiting time for each queue. Owing to the extreme complexity of the analysis which is due to the amount and asymmetric characteristics of each queue, an approximation model referred to as pseudoconservation law is used. In the case of symmetric queues, the laws give exact expression of the mean waiting times [6, 7]. On the contrary, an accurate approximate model can be obtained as in the case of asymmetric queues. We first describe an uplink scheduling scheme of the Mobile WiMAX which is based on cyclic polling model followed by our mathematical model for the proposed scheme. Then the weighted sum of the mean waiting time for the individual queues or also known as pseudoconservation law for the proposed scheduling algorithm is obtained. The rest of the paper is organized as follows. Section 2 discusses the system model of the proposed scheduling scheme, and Section 3 presents the detailed description. Section 4 is devoted to the derivation of the pseudoconservation law, and finally the paper is concluded in Section 5.


## 2. System Model

We consider a UL scheduler in Mobile WiMAX BS which acts as a server. The scheduler serves 5 queues where scheduling services Unsolicited Grant Service (UGS), Extended Real-Time Polling Service (ertPS), Real-Time Polling Service (rtPS), Non-Real-Time Polling Service (nrtPS), and Best Effort (BE) are symbolized asQ1, Q2, Q3, Q4, and Q5, respectively. Each queue has an infinite buffer capacity (any number of bandwidth requests can wait without loss upon arrival) to store the waiting or incoming bandwidth requests. Infinite buffer capacity assumption is often the best approximation that helps to assist the analysis [8]. The bandwidth requests or grants arrive at all queues according to the independent Poisson processes with an arrival rate of λ1,λ2,…,λN. The compound arrival rate is given as follows:(1)Λ=∑i=1Nλi.
Though the arrival of UGS and ertPS grants is modeled as a constant bit rate, in the case of multiple session arrival, the Poisson process provides adequate accuracy [9].Similarly, letbi be the service time of Qi with the first two moments:(2)βi=E[bi],βi(2)=E[bi2].
The server switches from Qi to the next queue with nonzero walk time with the first moment, si, and the second moment, si(2). The first moment of total walk time, s, is given as (3)s=∑i=1Nsi.
The switchover process is independent, and the arrival and service time is assumed to be independent and identically distributed (iid). The offered traffic at the ith queue is ρi=λiβi, and the total offered traffic is(4)ρ=∑i=1Nρi.
We consider a single server serving N queues as Q1,Q2,…QN. The order of service within each queue is first-come-first-serve (FCFS). The queues are attended by a server in cyclic order and incurs nonzero switchover time. Each queue will be served under exhaustive service discipline in which the server continues to work until the queue becomes empty. When Qi is empty, server immediately begins to switch to Qi+1. The proposed scheduling algorithm works as follows.The server servesQ1 until there are no more bandwidth requests available. When Q1 is empty, the server immediately begins to switch to Q1. Q2 is served next and once the queue is empty, the server will move to Q3. At Q3, when the queue is empty, the server will check on the amount of bandwidth request available at Q4. If the amount of bandwidth request exceeds the threshold assigned, n, then the server will carry out the service to Q4 and subsequently Q5. On the other hand, the server will return to service Q1 if the amount of the bandwidth request is less than the threshold assigned.


### 2.1. Definition of Key Parameters

We define some of the important parameters as a reference to this model. The cycle time,Ci, for Qi is the time between two successive arrivals or visits at Qi by the server. The mean cycle time, E[Ci], is independent of i (do not depend on the successive starting point of the cycle) and is equal to the sum of total switchover time and total mean amount of work departing during a cycle (which is also equal to mean amount of work arrived in a cycle, ρE[C] [10]):(5)E[Ci]=∑i=1Nsi+∑i=1NρiE[Ci].
Hence,(6)E[C]=s1-ρ.
The visit period of Qi, Vi, is defined as the time the server spends serving bandwidth requests at Qi. The server is working at a fraction ρi of the time at Qi, thus, the mean visit period of Qi, ρiE[C], is equal to(7)E[Vi]=ρis1-ρ.
Intervisit time, Ii, of Qi is the total time the server is unavailable to Qi during a cycle. A cycle time is the sum of visit period, and the intervisit time, E[Ii], can be derived as follows:(8)E[C]=E[Ii]+ρis1-ρ,E[Ii]=s1-ρ-ρis1-ρ=s1-ρi1-ρ.


### 2.2. Stability Criteria

For a system to be ergodic,ρ<1 would be the necessary condition to ensure stability for the exhaustive service.


## 2.1. Definition of Key Parameters

We define some of the important parameters as a reference to this model. The cycle time,Ci, for Qi is the time between two successive arrivals or visits at Qi by the server. The mean cycle time, E[Ci], is independent of i (do not depend on the successive starting point of the cycle) and is equal to the sum of total switchover time and total mean amount of work departing during a cycle (which is also equal to mean amount of work arrived in a cycle, ρE[C] [10]):(5)E[Ci]=∑i=1Nsi+∑i=1NρiE[Ci].
Hence,(6)E[C]=s1-ρ.
The visit period of Qi, Vi, is defined as the time the server spends serving bandwidth requests at Qi. The server is working at a fraction ρi of the time at Qi, thus, the mean visit period of Qi, ρiE[C], is equal to(7)E[Vi]=ρis1-ρ.
Intervisit time, Ii, of Qi is the total time the server is unavailable to Qi during a cycle. A cycle time is the sum of visit period, and the intervisit time, E[Ii], can be derived as follows:(8)E[C]=E[Ii]+ρis1-ρ,E[Ii]=s1-ρ-ρis1-ρ=s1-ρi1-ρ.


## 2.2. Stability Criteria

For a system to be ergodic,ρ<1 would be the necessary condition to ensure stability for the exhaustive service.


## 3. Related Works

In sequence to the scheduling services that have been designed by the WiMAX forum to efficiently deliver broadband data services such as video, voice, and data, we have come to the idea that an algorithm implemented in the Mobile WiMAX uplink scheduler must be twofold: (1) able to blend efficiently with the bandwidth request strategy and bandwidth allocation and (26) decide on the algorithm taking into account the implementation and computation complexity. The IEEE 802.16e adopts a centralized based scheduling with the intention that the resources can be dynamically allocated and the scheduler can provide superior QoS for both the UL and downlink (DL). A proper choice of good scheduling algorithm [11] for the UL scheduler is critical as it will ensure that performance is more predictable and the QoS is better enforced [12].There are five types of scheduling services defined in the standard: UGS, rtPS, ertPS, nrtPS, and BE. UGS is appropriate for a fixed sized packet transmitted at periodic intervals. Thus, bandwidth request is not required. rtPS is suitable for real-time data  streaming with variable packet size, and the MSs  can send bandwidth request in response to the bandwidth request opportunities assigned by the base station (BS) through polling opportunities. ertPS is added to the IEEE 802.16e to deal with the variable rate of real-time application. The scheduling service is designed with the basis of UGS and rtPS, and BS will provide unicast grants in unsolicited manner to the service. nrtPS suits for a delayed tolerant application with variable packet size. Similar to the rtPS, nrtPS will be polled by the BS on a regular basis (not necessary periodic). Finally BE is recommended for data streaming with no throughput and delayed guarantee. MS may use both, which is either unicast or contention request.Since the standard does not distinctly define the scheduling algorithm to be applied, we have proposed a UL scheduling algorithm based on the cyclic polling model. The delay property is critical to real-time traffic since any violation to the delay bound may cause the packets to be discarded. One way of accomplishing this is to assign different priorities to the real-time traffic (voice, video) and non-real-time traffic. Thus, a threshold-type of service seems to be suitable for this purpose. In order to assign that, we exploit the nrtPS features to guarantee the delay property of the real-time traffic by imposing a threshold policy. The server visits (polls) the UGS, ertPS, and rtPS in a cyclic manner, serves each queue with exhaustive service strategy, and continues serving if the requests in nrtPS buffer do not exceed the predetermined threshold,n,  as shown in Figure 1. If the number of requests in nrtPS is greater than or equals n, the server will instantly begin to service the requests in nrtPS after serving the rtPS queue with an exhaustive service policy too as shown in Figure 2. This is to ensure that the future opportunities for the non-real-time traffic scheduling services are not starved.Figure 1
The Mobile WiMAX uplink scheduler for threshold less thann.Figure 2
The Mobile WiMAX uplink scheduler for threshold greater than or equal ton.To incorporate the correlation between each of the scheduling services, switchover time is introduced. Switchover time is defined as the amount of time taken by the server to switch from one scheduling service to another. Thus, the analytical model will not be established independently for each scheduling service, instead, it will be established as a whole. In order to do that, the pseudoconservation law will be used to derive the model.


## 4. Pseudoconservation Law

In the situation of zero switchover times, the server works when there is work in the system and becomes idle if no work is present. Thus, the conservation law holds for the total amount of work in the system. The amount of work in the system is independent of the service policy and, hence, is equal to the amount of work in an M/G/1 queue [13–16] with the arrival rate of λi and service time of βi:(9)E[VM/G/1]=ρ∑i=1Nλiβi(2)2(1-ρ),∑i=1NρiEWi=ρ∑i=1Nλiβi(2)2(1-ρ).
In the case of nonzero switchover times, the amount of work (the weighted sum of the waiting times,ρiEWi. Let Wi be the waiting time, and let it define time between the arrival of bandwidth requests at Qi and the moment at which it starts to receive service with mean EWi) is no longer independent of the service policy. This is called the pseudoconservation law and established as follows [13–16]:(10)Vcd̲̲VM/G/1+Y,
where, d̲̲ is the equality in distribution, Vc is the amount of work in a cyclic system at an arbitrary epoch, VM/G/1 is the amount of work in a corresponding M/G/1 system at an arbitrary epoch, Y is the amount of work in a cyclic-service system at an arbitrary epoch in a switching, and period/nonserving interval, where VM/G/1, and Y are independent.Here, epoch designates an instant in time.It follows that(11)E[Vc]=E[VM/G/1]+E[Y].
Moreover, E[Y] can be defined as(12)E[Y]=∑i=1NsisE[Yi].
From [15], E[Y] is composed of three terms: EMi(1), EMi(2), and ρ(si(2)/2si), where EMi(1) is the mean amount of work in Qi at a departure epoch of the server from Qi, EMi(2) is the mean amount of work in the rest of the system at a departure epoch of server from Qi, and ρ(si(2)/2si) is the mean amount of work arrived in the system in the preceding part of the switching interval under consideration:(13)E[Yi]=∑i=1NEMi(1)+∑i=1NEMi(2)+∑i=1Nρsi(2)2si.EMi(1) is totally dependent on the choice of service strategies applied to the queue and can only be determined when the service strategy is identified. Therefore, parameter EMi(2) will be investigated in the next section, that is, the mean amount of work in the rest of the system at a departure epoch of server from Qi when the requests in nrtPS are less than n and greater than or equal to n, respectively.


### 4.1. Derivation ofEMi(2) When Requests in nrtPS Are Less Than n

As discussed in the previous section, when the bandwidth request inQ4 is less than n, the server will only carry out the service for Q1, Q2, and Q3 cyclically with an exhaustive service policy. In this case, Q4 and Q5 will not be attended by the server as if the queues do not exist in the scheduler. Thus, a cycle in the condition when requests in nrtPS are less than n consists of server visits to Q1, Q2, and Q3 in a cyclic order. The total switchover time and total offered traffic are defined as s=∑i=13si and ρ=∑i=13ρi, respectively. From (7), the mean visit time of Qi is (14)E[Vi]=ρis1-ρ,
that is, Qi is visited once in a cycle.Thus, the total amount of work at the departure epoch of server fromQ1, Q2, and Q3 can be derived as follows:(15)s1sEM1(2)+s2sEM2(2)+s3sEM3(2),
where(16)EMi(2)=ρi-1(si-1+ρis1-ρ)+ρi-2×(si-2+ρi-1s1-ρ+si-1+ρis1-ρ)+⋯+ρi+1(si+1+ρi+2s1-ρ+ρi+3s1-ρ+⋯+si-1+ρis1-ρ).
Solving (16) and expanding (15) yield(17)s1s[ρ2(s2+ρ3s1-ρ+s3+ρ1s1-ρ)+ρ3(s3+ρ1s1-ρ)]+s2s[ρ3(s3+ρ1s1-ρ+s1+ρ2s1-ρ)+ρ1(s1+ρ2s1-ρ)]s3s[ρ2(s2+ρ3s1-ρ)+ρ1(s1+ρ2s1-ρ+s2+ρ3s1-ρ)]
which can then be simplified into(18)∑i=13sisEMi(2)=ρs∑h∑<kshsk+s1-ρ∑h∑<kρhρk.


### 4.2. Derivation ofEMi(2) When Requests in nrtPS Are Greater Than or Equal to n

When the bandwidth request inQ4 is greater than or equal to n, the server will visit Q4 after the completion (Q3 is empty) of Q3 and subsequently Q5. Q4 and Q5 will be served according to the exhaustive service strategy. Thus, a cycle in the condition when requests in nrtPS are greater than or equal to n consists of server visits to Q1, Q2, Q3, Q4, and Q5 in a cyclic order. The total switchover time and total offered traffic in the condition that requests in nrtPS are greater than or equal to n are s=∑i=15si and ρ=∑i=15ρi, respectively.Even though the server visitsQ4 and Q5 at times when the requests of nrtPS are greater than or equal to n, the amount of work that arrives in a cycle still holds for Q4 and Q5 in view of the fact that the definition of the cycle time for Q4 and Q5 is still valid (Q4 and Q5 are visited by the server once in a cycle). As a result, the amount of work in Q4 can be derived as follows.Letqi,n be the steady-state probability that the queue length of Qi is n when the server arrives.Therefore,∑n=0∞qi,n=1. ∑n=1Ni-1qi,n is the probability that less than n bandwidth requests are served in a visit period.  1-∑n=1Ni-1qi,n is the probability that greater than or equal to n bandwidth requests are served in a visit period. λis/(1-ρ) is the mean number of bandwidth request arrival during a visit period.We obtained the expression of the mean number of messages served in a visit period which is also equal to the mean number of message arriving during a cycle:(19)∑n=1Ni-1nqi,n+∑n=Ni∞Ni(1-∑n=0Ni-1qi,n)=λis1-ρ.
The amount of work in Q4 can be established as follows:(20)βi∑n=1Ni-1nqi,n+βi∑n=Ni∞Ni(1-∑n=0Ni-1qi,n)=βiλis1-ρ=ρis1-ρ.
The first term denotes the amount of work when less than n bandwidth requests arrive at Q4 and the server is still serving Q1, Q2, and Q3. The second term reflects the amount of work when the request is greater than or equal to n. At this point, the server switches to Q4 at the completion of Q3 and later Q5. The third term represents the amount of work that arrives in a cycle or a visit period to Q4. Consequently, the amount of work that arrives in Q4 is denoted as(21)ρ4s1-ρ.Equation (21) also holds for the  amount of work that arrives in Q5. Thus the total amount of work at the departure epoch of server from Q1, Q2, Q3, Q4, and Q5 can be obtained from(22)s1sEM1(2)+s2sEM2(2)+s3sEM3(2)+s4sEM4(2)+s5sEM5(2).By noting that EMi(2) is given by (16) and solving (22) which then can be simplified to:(23)∑i=15sisEMi(2)=ρs∑h∑<kshsk+s1-ρ∑h∑<kρhρk.


### 4.3. Derivation of Pseudoconservation Law for the Uplink Scheduler

With reference to (11), E[Vc] is defined as [8, 14] (24)E[Vc]=∑i=1NρiEWi+12∑i=1Nλiβi(2).
Solving (11) from (9) and (24), (25)∑i=1NρiEWi=ρ∑i=1Nλiβi(2)2(1-ρ)+E[Y].
From (12), (26)E[Y]=∑i=1NsisE[Yi],
which is consequently composed of(27)E[Yi]=∑i=15EMi(1)+∑i=13EMi(2)+∑i=15EMi(2)+∑i=15ρsi(2)2si,
where EMi(2) is derived based on the condition of  the amount of bandwidth requests in nrtPS which are less than n and greater than or equals to n. EMi(1)depends on the service strategy applied to the queues. For exhaustive service, EMi(1) = 0 since there are no bandwidth requests left behind the server leaving the queue.Thus,E[Y] is defined as follows:(28)E[Y]=∑i=13si2(1-ρi)[(∑i=13ρ)2-∑i=13ρi2]+∑i=15si2(1-ρi)[(∑i=15ρ)2-∑i=15ρi2]+∑i=15ρsi(2)2si.By inserting (28) into (25), finally, the weighted sum of the mean waiting times for the individual queues or pseudoconservation law can be written as follows:    (29)∑i=15ρiEWi=ρ∑i=15λiβi(2)2(1-ρ)+∑i=13si2(1-ρi)[(∑i=13ρ)2-∑i=13ρi2]+∑i=15si2(1-ρi)[(∑i=15ρ)2-∑i=15ρi2]+∑i=15ρsi(2)2si.
It is worth mentioning that the order of the queues in the cycle does not influence the mean workload of the system or the weighted sum of mean waiting times as in (29) as long as it does not affect s and E[Y]E[Y] appears to be linearly dependent on the mean total switchover time [17].


## 4.1. Derivation ofEMi(2) When Requests in nrtPS Are Less Than n

As discussed in the previous section, when the bandwidth request inQ4 is less than n, the server will only carry out the service for Q1, Q2, and Q3 cyclically with an exhaustive service policy. In this case, Q4 and Q5 will not be attended by the server as if the queues do not exist in the scheduler. Thus, a cycle in the condition when requests in nrtPS are less than n consists of server visits to Q1, Q2, and Q3 in a cyclic order. The total switchover time and total offered traffic are defined as s=∑i=13si and ρ=∑i=13ρi, respectively. From (7), the mean visit time of Qi is (14)E[Vi]=ρis1-ρ,
that is, Qi is visited once in a cycle.Thus, the total amount of work at the departure epoch of server fromQ1, Q2, and Q3 can be derived as follows:(15)s1sEM1(2)+s2sEM2(2)+s3sEM3(2),
where(16)EMi(2)=ρi-1(si-1+ρis1-ρ)+ρi-2×(si-2+ρi-1s1-ρ+si-1+ρis1-ρ)+⋯+ρi+1(si+1+ρi+2s1-ρ+ρi+3s1-ρ+⋯+si-1+ρis1-ρ).
Solving (16) and expanding (15) yield(17)s1s[ρ2(s2+ρ3s1-ρ+s3+ρ1s1-ρ)+ρ3(s3+ρ1s1-ρ)]+s2s[ρ3(s3+ρ1s1-ρ+s1+ρ2s1-ρ)+ρ1(s1+ρ2s1-ρ)]s3s[ρ2(s2+ρ3s1-ρ)+ρ1(s1+ρ2s1-ρ+s2+ρ3s1-ρ)]
which can then be simplified into(18)∑i=13sisEMi(2)=ρs∑h∑<kshsk+s1-ρ∑h∑<kρhρk.


## 4.2. Derivation ofEMi(2) When Requests in nrtPS Are Greater Than or Equal to n

When the bandwidth request inQ4 is greater than or equal to n, the server will visit Q4 after the completion (Q3 is empty) of Q3 and subsequently Q5. Q4 and Q5 will be served according to the exhaustive service strategy. Thus, a cycle in the condition when requests in nrtPS are greater than or equal to n consists of server visits to Q1, Q2, Q3, Q4, and Q5 in a cyclic order. The total switchover time and total offered traffic in the condition that requests in nrtPS are greater than or equal to n are s=∑i=15si and ρ=∑i=15ρi, respectively.Even though the server visitsQ4 and Q5 at times when the requests of nrtPS are greater than or equal to n, the amount of work that arrives in a cycle still holds for Q4 and Q5 in view of the fact that the definition of the cycle time for Q4 and Q5 is still valid (Q4 and Q5 are visited by the server once in a cycle). As a result, the amount of work in Q4 can be derived as follows.Letqi,n be the steady-state probability that the queue length of Qi is n when the server arrives.Therefore,∑n=0∞qi,n=1. ∑n=1Ni-1qi,n is the probability that less than n bandwidth requests are served in a visit period.  1-∑n=1Ni-1qi,n is the probability that greater than or equal to n bandwidth requests are served in a visit period. λis/(1-ρ) is the mean number of bandwidth request arrival during a visit period.We obtained the expression of the mean number of messages served in a visit period which is also equal to the mean number of message arriving during a cycle:(19)∑n=1Ni-1nqi,n+∑n=Ni∞Ni(1-∑n=0Ni-1qi,n)=λis1-ρ.
The amount of work in Q4 can be established as follows:(20)βi∑n=1Ni-1nqi,n+βi∑n=Ni∞Ni(1-∑n=0Ni-1qi,n)=βiλis1-ρ=ρis1-ρ.
The first term denotes the amount of work when less than n bandwidth requests arrive at Q4 and the server is still serving Q1, Q2, and Q3. The second term reflects the amount of work when the request is greater than or equal to n. At this point, the server switches to Q4 at the completion of Q3 and later Q5. The third term represents the amount of work that arrives in a cycle or a visit period to Q4. Consequently, the amount of work that arrives in Q4 is denoted as(21)ρ4s1-ρ.Equation (21) also holds for the  amount of work that arrives in Q5. Thus the total amount of work at the departure epoch of server from Q1, Q2, Q3, Q4, and Q5 can be obtained from(22)s1sEM1(2)+s2sEM2(2)+s3sEM3(2)+s4sEM4(2)+s5sEM5(2).By noting that EMi(2) is given by (16) and solving (22) which then can be simplified to:(23)∑i=15sisEMi(2)=ρs∑h∑<kshsk+s1-ρ∑h∑<kρhρk.


## 4.3. Derivation of Pseudoconservation Law for the Uplink Scheduler

With reference to (11), E[Vc] is defined as [8, 14] (24)E[Vc]=∑i=1NρiEWi+12∑i=1Nλiβi(2).
Solving (11) from (9) and (24), (25)∑i=1NρiEWi=ρ∑i=1Nλiβi(2)2(1-ρ)+E[Y].
From (12), (26)E[Y]=∑i=1NsisE[Yi],
which is consequently composed of(27)E[Yi]=∑i=15EMi(1)+∑i=13EMi(2)+∑i=15EMi(2)+∑i=15ρsi(2)2si,
where EMi(2) is derived based on the condition of  the amount of bandwidth requests in nrtPS which are less than n and greater than or equals to n. EMi(1)depends on the service strategy applied to the queues. For exhaustive service, EMi(1) = 0 since there are no bandwidth requests left behind the server leaving the queue.Thus,E[Y] is defined as follows:(28)E[Y]=∑i=13si2(1-ρi)[(∑i=13ρ)2-∑i=13ρi2]+∑i=15si2(1-ρi)[(∑i=15ρ)2-∑i=15ρi2]+∑i=15ρsi(2)2si.By inserting (28) into (25), finally, the weighted sum of the mean waiting times for the individual queues or pseudoconservation law can be written as follows:    (29)∑i=15ρiEWi=ρ∑i=15λiβi(2)2(1-ρ)+∑i=13si2(1-ρi)[(∑i=13ρ)2-∑i=13ρi2]+∑i=15si2(1-ρi)[(∑i=15ρ)2-∑i=15ρi2]+∑i=15ρsi(2)2si.
It is worth mentioning that the order of the queues in the cycle does not influence the mean workload of the system or the weighted sum of mean waiting times as in (29) as long as it does not affect s and E[Y]E[Y] appears to be linearly dependent on the mean total switchover time [17].


## 5. Concluding Remarks

In this paper, we have presented the use of the pseudoconservation law to derive the weighted sum of the mean waiting times for the proposed scheduling algorithm of the Mobile WiMAX uplink scheduler. The proposed scheduling algorithm is based on a cyclic polling model with the threshold policy imposed onQ4 or nrtPS and each queue is served under the exhaustive discipline. We have obtained the weighted sum of the mean waiting times for the individual queues, in view of the fact that the explicit expression for individual waiting times was in general very complicated. From the derivation in Section 4.2, of work at Q4 and Q5, that is, when the threshold is greater than or equal to≥n, condition is equivalent to the amount of work that arrives in a cycle (that is the amount of work that arrives in a cycle still holds for Q4 and Q5).Pseudoconservation law seems to be very useful in several purposes. In many complex systems, they are the only meaningful exact relations that can be obtained [13]. Thus, they provide important insight such as measure of overall performance, demonstration on the effects of various parameters on Wi’s, and a basis of approximation and bounds [1, 18]. Note that this work is different from that in [14, 15] where mixed service strategies are considered for a discrete-time and continuous-time cyclic service.



---

*Source: 804939-2011-03-03.xml*