Ageing and Priority-Based Scheduling for Uplink in WiMAX Networks

Abstract

WiMAX is an emerging technology for next-generation wireless networks which supports a large number of users in an economic way. To achieve quality of service (QoS) requirements, an efficient and reliable scheduling algorithm is needed. The existing approaches in the literature have been proven to provide the best performance in allocating bandwidth to subscriber stations to maximize the throughput and ensure the constraints of delay in each class of traffic. In these approaches, starvation of lower priority class was not considered, which is of great significance in reality. In this paper, we have considered the starvation of lower priority classes to provide QoS requirement to each class of traffic in an acceptable way, and a bandwidth scheduling algorithm is proposed. A comparative study between the proposed scheduling algorithm and the existing scheduling algorithm shows the better performance in terms of maximizing the network throughput in given network, while minimizing the starvation of lower priority classes.

1 Introduction

Fixed WiMAX based on IEEE 802.16 standard is cost effective for fixed wireless networks. IEEE 802.16e is the new version to the fixed WiMAX mobility. WiMAX provides high data rate mobile wireless services for metropolitan areas. WiMAX coverage range is up to thirty-mile radius and data rates between 1.5 to 75 Mbps theoretically. The WiMAX defines the two modes of operation namely mesh and point-to-multipoint (PMP) mode. In mesh mode, each subscriber station (SS) can communicate to each other and to the base station (BS). In point-to-multipoint mode, subscriber stations can communicate only through base station. The base station is responsible for providing the QoS to each of its subscriber stations.

The scheduling algorithm must be simple to implement because real-time application supported by subscriber station needs the quick response from the centralized base station. So the time complexity of scheduling algorithm must be simple. Lots of research on scheduling algorithm has been investigated in [1, 2]. The issues in allocating resource are more challenging. In our proposed scheduling algorithm, base station uses the ageing and priority-based scheduling (APBS) to schedule the traffic of different classes. The downlink scheduler at the base station schedules the entire bandwidth among the subscriber stations depending on the grant per connection type.

The rest of the paper is organized as follows: Sect. 2 presents the previous works. In Sect. 3, problem is defined in formal notation. The proposed approach is presented in Sect. 4. The complexity analysis and results are described in Sect. 5 and Sect. 6, respectively. Finally, conclusion and future work are drawn in Sect. 7.

2 Previous Works

Our study focuses on centralized scheduling in point-to-multipoint (PMP) mode. In the literature, many scheduling algorithms have been proposed for downlink scheduling. There are different types of scheduling algorithm, namely traditional, dynamic scheduling. In [3] traditional scheduling algorithms uses the same Schelling technique as in computer operating system. It shares the equal network resources to all the subscribers without concern about the priority. However, this technique is not suitable for WiMAX scheduling, where the traffic demand of varying size arrives in random fashion. The authors Sagar et al. in [4] proposed the weight round robin (WRR) for scheduling the bandwidth to each queue. But it is not suitable for WiMAX scheduling because the main drawback of WRR is that when the traffic has a variable packet size, WRR provides an incorrect percentage of bandwidth allocation.

The dynamic schedulers are adaptive in bandwidth allocation. The authors Fathi et al. [5] proposed joint scheduling and call admission control (CAC) technique for scheduling packets. In [6] proposed the joint routing and scheduling algorithm for WiMAX network with the provision for fairness in bandwidth allocation and increase in throughput.

Best of our knowledge, no work has been conducted to overcome the starvation of lower ordered traffic request, while maintaining the quality of service to each class of traffic.

3 Problem Formulation

The WiMAX network consists of base station (BS), subscriber station (ss) and users. The base station is connected to subscriber station in point-to-point mode. The user under the coverage of base station is directly connected through wireless links. The user not under the coverage area of base station is connected through subscriber stations. Given a network topology, which is a directed graph G(V,E), where V is a set of subscriber stations/user and E is the set of bidirectional wireless link between the base station and subscriber station/user at the particular instant of time. ‘C’ is the capacity of each link between the base station to subscriber station/users. The base station is responsible for allocating network resource to subscriber stations. The connection requests from all class of traffic are represented by notation(S, B.requested, $Class_{tupe}$, B, $stat_{timeofrequest}$, request.duration), where S, B.requested and $star_{timeof request}$, request.duration represent the source node, bandwidth demanded and arrival time of each request and duration of the request, respectively. The centralized uplink bandwidth scheduling with the prime objective is to maximize the network throughput and meanwhile eliminate the starvation due to the higher class traffic is considered.

Assumptions:

We use the following assumptions in this work.

• Traffic demands is static in nature. i.e. traffic demands are known in advance.

• The total number of traffic is $R_{i} = N$.

• $w_{Mn}$ is 1 if the relay station M associated to base station n, $M\in ss$ and $j\in BS$ 0 otherwise.

• $R_{i}$, where ${M_i^{ss}}$ is the number of subscriber station(M)/user including the traffic class i in the network.

• $B_{k,i}$ bandwidth request of kth subscriber/user with traffic class belong to i th class of traffic.

• $\beta _n$ is 1 if the BS is installed at site n, $n\varepsilon BS$ 0 otherwise.

• $\gamma M$ is 1 if the ss is installed at site M, $M\varepsilon ss$ 0 otherwise.

• We have reserved 60% of bandwidth for UGS traffic in terms of bytes per seconds (Bps), and 20% is reserved for RTPS, and 10% is reserved for nRTPS and BE. However these are not rigid limits and are flexible if requests of another class are missing or are lesser.

• $\alpha$ value is assumed as 0.5.

Objective:

The objective here is to maximize the network throughput, while meeting the quality of service to each class of traffic requirement of WiMAX standard. The objective function to maximize the network throughput is defined as follows:

$$\begin{aligned} R_i= {\sum _{k=1}^{{M_i}^{ss}} B_{k,i}} \end{aligned}$$

(1)

$$\begin{aligned} Maximize \quad {\sum _{i}^N R_i *p} \end{aligned}$$

(2)

$p={\left\{ \begin{array}{ll} 1, &{} \text {if}\, R_{i}\, \text {is established}.\\ 0, &{} \text {otherwise}. \end{array}\right. }$

Subjected to:

Base station to relay station constraints

$$\begin{aligned} \sum _{\forall n\varepsilon BS} w_{Mn}=\gamma _{M} \quad where \quad \forall M \varepsilon ss \end{aligned}$$

(3)

$$\begin{aligned} w_{Mn} \le \beta _{n} \quad where \quad \forall M\varepsilon ss \quad n\varepsilon BS \end{aligned}$$

(4)

Equation 3 ensures the constraint that each relay station is connected to only one base station. Equation 4 assures the base station to relay station connection. The number of base station is less than or equal to the relay station installed.

$$\begin{aligned} \sum _{i=1}^n T_{ss_{i}}\le T \end{aligned}$$

(5)

$$\begin{aligned} \sum _{i=1}^n T_{ss_{i}}\times \beta \le T \end{aligned}$$

(6)

$\beta ={\left\{ \begin{array}{ll} 1, &{} \text {if}\, ss_{i}\, \text {used time slot}\, T_{ss_{i}}\, \text {and associated with base station BS}.\\ 0, &{} \text {otherwise}. \end{array}\right. }$

$ss_{i}$ refers to the number of subscriber station attached. BS refers to the number of base station. ${T_{{ss}_{i}}}$ refers to the time slot allocated to each subscriber station. Equation 5 indicates the number of time slot allocated to each subscriber station should be less than or equal to the total number of time slot(T) available with base station BS.

4 Proposed Approach

In this section, the proposed algorithm (APBS) is presented with the objective to maximize the throughput of given network. Our algorithm is categorized in two stages. The first stage of our algorithm is to assign the base station to subscriber stations/nodes under the coverage area. Base station executes the uplink scheduler at every frame interval of time (t) and sends the grant requests to subscriber station in uplink map message. In the second stage, each subscriber station associated with four different class of traffic, namely UGS, RTPS, nRTPS and BE are checked for the expire time and stored in the list $L_{req}$. The base station maintains four types of priority queues. The request is stored in respective priority queues (UGS, RTPS, nRTPS, BE). The scheduler function is called to schedule the requests of each base stations. This type of scheduling is known as grant per connection (GPC). The algorithm, namely Ageing and Priority-Based Scheduling (ABPS), is depicted in Algorithm 1, to schedule the traffic of different classes. The downlink scheduler at the base station schedules the entire bandwidth among the subscriber stations. Scheduling technique considers the two factors, while serving the request. The scheduler has the age and deadline associated with each class of traffic. The scheduler calculates the weight associated with each request in each queue and stores it in the priority queue of respective class. The scheduler schedules each request before the deadline. The early deadline requests are served first. When alpha is 0, then the priority of all the requests is same and only the time in which they arrive is the only measure that we use to sort the requests; hence this turns out to be FCFS scheduling. And for any other value of alpha, we have taken both age and deadline of the requests into consideration, so it turns out to be APBS algorithm.

$$\begin{aligned} Age = current_{timeof system}-start_{time of the request} \end{aligned}$$

(7)

$$\begin{aligned} Deadline={End_{time of request}}-{current_{time of system}} \end{aligned}$$

(8)

$$\begin{aligned} Weight = \frac{{\alpha \times (age+1)}}{(deadline+1)} \end{aligned}$$

(9)

$\alpha$ can vary between 0 and 1.

First, the UGS traffic is admitted in priority queue and calculate the weight associated with each request. The UGS connection is served depending on the bandwidth requirement. The request is served in queue depending on the deadline. The request with early deadline is served first. In this case, $\sum _{i=1}^n{B_{UGS}}$ are the total request with early deadline in UGS class, are served first. The remaining request of UGS class (in priority queue) are served in the next slot of frame allocation time. Thereafter, the RTPS connections are served by ordering them according to queue size information. In this case, $\sum _{i=1}^n{B_{RTPS}}$ are the total request with early deadline in RTPS class. The request which are waiting for a long time in a priority queue of RTPS are served according to their weight factor. The remaining request of RTPS class whose dead line is remaining are served in the next time slot of frame allocation. In our algorithm, we have fixed the percentage of bandwidth allocated to each class of traffic. If there is no higher priority traffic flows, the reserved bandwidth can be utilized by the lower class traffic including the intermediate queue.

4.1 Example

We have considered an WiMAX network connected to subscriber and mobile nodes shown in Fig. 2 to illustrate the working principle of APBS algorithm. There are just one base station and two subscriber stations that are connected to the base station. There are four nodes/end users, namely N0, N1, N2 and N3. The nodes N0 and N1 are connected directly to the base station. The N2 and N3 are connected via the subscriber stations. We have currently four requests for each class with bandwidth demand in kilo bytes. The traffic pattern are shown in Table 1 (and are graphically depicted in Fig. 1).

Fig. 1

Scheduler for uplink at base station

Fig. 2

The WiMAX network structure

We use the following example to explain our algorithm. We have set the frame size as 100 KBps (kilo bytes per second) and frame duration as 0.5 s.

Table 1 Bandwidth demanded from different class of traffic

Table 2 After running the scheduling algorithm, time $\mathrm{t}=0$s

This frame allocation in Table 2 shows very simple distribution of the frame size. An important thing to watch here is that the UGS class is allocated just 60% of the total frame size despite being the highest priority class. Hence, other classes also get their requests served.

Table 3 Frame allocation for time $\mathrm{t}=0.5$s

Table 4 Frame allocation for time $\mathrm{t}=1$s

This frame shows the competitive frame allocation among requests of same class. Here, we can see that there are two requests from RTPS class. However, the one with greater weight value gets served first. The frame allocation at $t=0.5$ as shown in Table 3. There is also competition for frame allocation between traffic requests from same class. Here, we can see that there are two requests from RTPS class. However, the one with greater weight value gets served first.

This frame allocation in Table 4 shows the reallocation property among the classes in terms of frame size for each class. We can observe that 46 KBps of RTPS request is satisfied despite the limit for RTPS request being 20 KBps initially. It is because of the reallocation of frame size. Hence, RTPS is able serve up to 50 KBps (initially limited to 20 KBps) request in the above frame, and nRTPS is able to serve up to 27 KBps (initially limited to 10 KBps). All requests are served in an efficient manner.

$RTPS{F.size} =\left[ \frac{RTPS \quad F.size + RTPS\quad frame \%}{Remaining\quad classes\quad F.size \%}* {F.size \quad leftout }\right]$

Example: RTPS frame size = $20 +\left[ \frac{20}{20 + 10 + 10}\times {60}\right] = 50\,\mathrm{KB}.$

Similarly for nRTPS = $10 + \left[ \frac{10}{20 + 10 +10}\times {60} \right] = 25\,\mathrm{KB}$.

Also after RTPS leaves out 4 KB:

nRTPS new size = $25 + \left[ \frac{10}{10 + 10}\times {4}\right] = 27\,\mathrm{KB}$. RTPS size actually reflects the extra bandwidth available for RTPS class, when no higher class traffic request are made.

5 Complexity Analysis

By algorithmic analysis, the total complexity of the algorithm is $O((no.BS)*((no.R_{N})*(ss_{n}) +(no.R_{N})*log(no.R_{N})))$. The algorithm is efficient and is feasible. We also notice that the complexity of the algorithm is eventually independent of the number of subscriber/relay stations. The ABPS algorithm based on multiple queues performs much better than the traditional first come first serve (FCFS) algorithm. We assume that number of requests is going to be much greater than number of base stations and subscriber stations. Hence, complexity reduces to $O(BS*(ss_{n}*R_{N} + R_{N}logR_{N}))$, where BS is the number of base stations, $ss_{n}$ is the number of nodes/end users, and $R_{N}$ is the number of requests generated.

Fig. 3

Relationship of total number of requests demanded versus total number of requests served in UGS class

6 Results

In this section, the simulation results are observed under several scenarios by varying the traffic request of different classes. Total traffic request generated by subscriber stations under categories UGS:RTPS:nRTPS and BE are in ratio of 20:20:60, and requests are generated between the range of 64 KBps–128 KBps, 30–64 KBps and 1 KBps–30 KBps, receptively.

Fig. 4

Relationship of total number of requests demanded versus total number of requests served in RTPS

Fig. 5

Relationship of total number of requests demanded versus total number of requests served in nRTPS class

Fig. 6

Relationship of total number of requests demanded versus total number of requests served in BE class

Figures 3, 4, 5 and 6 show the results of APBS with FCFS scheduling algorithm. They demonstrate the relationship between the number of the number of requests served in all four class with the number of requests demanded in all four class of traffic. The proposed algorithm outperforms the existing algorithm FCFS.

Figures 7, 8, 9 and 10 depict the results of APBS with FCFS scheduling algorithm. The proposed algorithm performed better in terms of serving the total bandwidth demanded in all classes compared to the existing algorithm FCFS.

Fig. 7

Relationship of total bandwidth demanded versus total bandwidth served in UGS class

Fig. 8

Relationship of total bandwidth demanded versus total bandwidth served in RTPS class

Fig. 9

Relationship of total bandwidth demanded versus total bandwidth served in nRTPS class

Fig. 10

Relationship of total bandwidth demanded versus total bandwidth served in BE class

7 Conclusion and Future Work

In this work, we have designed algorithm, Ageing and priority-Based Scheduling (APBS) to eliminated the bandwidth starvation due to the higher class monopolizing the lower class traffic. We have also significantly reduced starvation of requests, particularly of the less priority classes (like best effort traffic). The proposed algorithm can be extended to dynamic traffic demands in the hybrid networks in future.