# Fairness Time-Slot Allocation and Scheduling with QoS Guarantees in Multihop WiMAX Mesh Networks

Authors: Chien-Yu Wu; Hann-Jang Ho; Sing-Ling Lee; Liang Lung Chen
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The WiMAX technology has been defined to provide high throughput over long distance communications and support the quality of service (QoS) control applied on different applications. This paper studies the fairness time-slot allocation and scheduling problem for enhancing throughput and guaranteeing QoS in multihop WiMAX mesh networks. For allocating time slots to multiple subscribe stations (SSs), fairness is a key concern. The notion of max-min fairness is applied as our metric to define the QoS-based max-min fair scheduling problem for maximizing the minimum satisfaction ratio of each SS. We formulate an integer linear programming (ILP) model to provide an optimal solution on small-scale networks. For large-scale networks, several heuristic algorithms are proposed for better running time and scalability. The performance of heuristic algorithms is compared with previous methods in the literatures. Experimental results show that the proposed algorithms are better in terms of QoS satisfaction ratio and throughput.


---

## Body

## 1. Introduction

In recent years, worldwide interoperability for microwave access (WiMAX), the broadband wireless access technology based on IEEE 802.16 standard [1], has received enormous attention in wireless communication networks. Based on IEEE 802.16, WiMAX system has been defined to provide high throughput over long distance and to support the quality of service (QoS) control applied on different applications. The IEEE 802.16 standard supports both the point-to-multipoint (PMP) mode and the mesh mode. In PMP mode, stations are organized as a cellular network, where subscriber stations (SSs) are directly connected to base stations (BSs). Such networks require each SS to be within the communication range of its associated BS, thus greatly limiting the coverage range of the network. In the mesh mode, the mobile stations are connected as an ad hoc network. Moreover, the mobile stations send the packets to the neighbors; the neighbors relay the received packets to the base station. Thus, it is unnecessary to have a direct connection between each mobile station and the base station.In an IEEE 802.16 mesh network, transmissions can undergo a multihop manner. The standard specifies a centralized scheduling mechanism for the BS to manage the network. Stations will form a routing tree rooted at the BS for the communication purpose. SSs in the network will send request messages containing their traffic demands to the BS to ask for resources. The BS then uses the topology information along with SSs’ requests to determine the routing tree and to allocate resources. All next generation cellular wireless systems employ orthogonal frequency division multiple access (OFDMA) based multicarrier technology. An OFDMA frame consists of time slots in the time domain and subchannels in the frequency domain. A time-slot and subchannel combination, referred to as a tile, is the minimum allocable unit.In the wireless transmission technology, the schedule for data transmission is a very important research issue. The main purpose of the schedule includes:(1) increasing the network throughput, (2) shorting the scheduled time, (3) providing a guarantee QoS service, and (4) keeping transferring fairness in the network. Therefore, it is very important to have a good scheduling algorithm in the wireless transmission.Since current wireless network systems usually use the OFDMA as communication technology, they also plan to provide various QoS services for a large number of users. The high data transfer throughput and QoS assurance have become the main goal of the wireless network [2–4]. To get more efficient bandwidth usage and to provide better QoS services to users of the wireless network, dynamic resource allocation method has been widely studied in [2, 3]. When we consider the real-time service flows, such as VoIP and wireless multimedia communications, their quality of services (QoSs) should be satisfied. The real-time connections will periodically transmit or receive a constant amount of traffic.Recently, several literatures discuss the scheduling scheme for multihop transmissions in WiMAX mesh networks, since the standard protocol usually does not specify any particular scheduling scheme. For example, the throughput and fairness issues have been studied in [5]. However, the previous literature does not guarantee the QoS while considering the fairness scheduling of SSs in real time. It is worth exploring how the well-known fairness schemes such as max-min, max-flow, absolute, and proportional fairness can be implemented in 802.16j networks with the QoS constraint. This paper concentrates on the time-slot allocation and scheduling for WiMAX mesh networks with OFDMA protocol. The goal of this paper is to provide various scheduling schemes which optimize both QoS and fairness of resource allocations for the WiMAX mesh networks. From the experimental results, we show that our proposed schemes are better than the previous work in terms of QoS satisfaction ratio.This paper applies the concept of max-min fair scheduling to enhance the minimum satisfaction ratio over the WiMAX mesh networks. We propose an ILP model to solve the problem and provide heuristic methods to ensure the QoS priority of scheduling to achieve better overall QoS satisfaction ratio and throughput.The main contributions of our work are listed below.(1)
Propose a heuristic algorithm that can optimize the max-min fair and guarantee QoS. In our proposed method, QoS requirements are a primary consideration for allocating resources to various SSs. If there are remaining resources after stratifying the QoS requirements, we will then consider the max-min fair scheduling to improve the overall throughput and minimize the satisfaction ratio. In IEEE 802.16j mesh networks, the proposed algorithm can meet the QoS requirements of various SSs in a frame and enhance the network overall QoS satisfaction ratio.(2)
Exploit spectral reuse. The spectral reuse is adopted by our heuristic algorithm to avoid the packets collisions to improve the network throughput and QoS satisfaction ratio.(3)
Construct the ILP model. We construct an integer linear programming model which constraints on the QoS requirements and max-min fairness assignments for solving the optimization problem in multihop WiMAX mesh networks.


## 2. Network Model

### 2.1. MMR Infrastructure

This paper focuses on the time-slot allocation and scheduling on the network system with IEEE 802.16j mobile multihop relay-based (MMR) infrastructure. In accordance with the recommendation of WiMAX standard [6], BS is the root of the tree to assist the transmission of WiMAX mesh networks. The RSs are the intermediate nodes of the tree, and the SSs are the leaf node of the tree.We mainly focus on the scheduling between the SSs and RSs. Our goal is to find a scheduling method which can meet the QoS requirements of each SS and achieve a fair allocation of network resources. We also study how to allocate subchannels and time slots according to the bandwidth requirements of each SS in a frame. We assign the transmission schedule to maximize the minimum satisfaction ratio over all SSs to get the overall max-min fairness for the multihop relayed WiMAX mesh network.


### 2.2. Mesh Mode

We focus on the 802.16 mesh network which is composed by one BS and several SSs. The BS is responsible for connecting the back-end network. Each SS transfers data to neighboring SSs without the BS’s agreement. The data flow away from the BS is called downlink data flow; conversely, which toward the BS is called uplink data flow. For mesh networks, most studies focus on topology design [7]. In 802.16 mesh networks, some issues are studied for supporting QoS in [8, 9]. Shetiya and Sharma [8] studied the QoS routing problem of Central Scheduling. Hong and Pang [9] considered the multihop scheduling problem with bandwidth and delay constraints. In these researches, different approaches for establishing the routing tree of mesh networks are analyzed, and some issues of time-slot allocation are discussed.


### 2.3. Spectral Reuse

This paper applies spectral reuse to solve the resource allocation problem for the 802.16 mesh network. The advantage of using spectral reuse is to improve the transmission capacity and the throughput of network. Fu et al. [10] proposed an algorithm to maximize the usage of spectral reuse. Chen et al. [11] studied how to use the spectral reuse to solve the problem of resource allocation.


### 2.4. Interference Model

Scheduling strategies must ensure that transmissions in each time slot do not collide. There are two types of collision situations in the wireless network environment. They are called Primary Interference and Secondary Interference [12, 13]. Primary Interference occurs in a single time slot of scheduling; the SS cannot do more than one thing. In other words, the SS can only transfer or receive data in a single time slot. Secondary Interference occurs when the originally receiver X turns into the transfer, but the user X is still in the range of the transfer Y. The user X will affect the transmission of the user Y. There are some studies that focus on WiMAX mesh network interference problems [14, 15], Wei et al. [16] proposed an interference-aware multihop routing algorithm to maximize the degree of use of network bandwidth to maximize the network throughput.


### 2.5. Fairness Scheduling

Nowadays the related works on WiMAX mesh networks through a network of relay stations scheduling and resource allocation are concerned widely. It is common to study the fairness in many wireless networks in [17–20]. Sayenko et al. [19] studied the proportional fairness and considered the difference between frequency selections with multiuser scheduling problems. Andrews and Zhang [20] proposed a round-robin based scheduling method for IEEE 802.16 BS to ensure QoS requirements of the SS in uplink (UL) and downlink (DL) can be met. But the network bandwidth usage efficiently and bandwidth requirements were not considered in [19, 20].In this paper, we propose heuristic scheduling algorithms that identify each SS to maximize the minimum satisfaction ratio in the network and, meanwhile, to meet the bandwidth requirements for each SS. We compare the QoS satisfaction ratio, throughput, and min satisfaction ratio with the previous method proposed in [21]. Experimental results show that our method is better in terms of QoS satisfaction ratio.


## 2.1. MMR Infrastructure

This paper focuses on the time-slot allocation and scheduling on the network system with IEEE 802.16j mobile multihop relay-based (MMR) infrastructure. In accordance with the recommendation of WiMAX standard [6], BS is the root of the tree to assist the transmission of WiMAX mesh networks. The RSs are the intermediate nodes of the tree, and the SSs are the leaf node of the tree.We mainly focus on the scheduling between the SSs and RSs. Our goal is to find a scheduling method which can meet the QoS requirements of each SS and achieve a fair allocation of network resources. We also study how to allocate subchannels and time slots according to the bandwidth requirements of each SS in a frame. We assign the transmission schedule to maximize the minimum satisfaction ratio over all SSs to get the overall max-min fairness for the multihop relayed WiMAX mesh network.


## 2.2. Mesh Mode

We focus on the 802.16 mesh network which is composed by one BS and several SSs. The BS is responsible for connecting the back-end network. Each SS transfers data to neighboring SSs without the BS’s agreement. The data flow away from the BS is called downlink data flow; conversely, which toward the BS is called uplink data flow. For mesh networks, most studies focus on topology design [7]. In 802.16 mesh networks, some issues are studied for supporting QoS in [8, 9]. Shetiya and Sharma [8] studied the QoS routing problem of Central Scheduling. Hong and Pang [9] considered the multihop scheduling problem with bandwidth and delay constraints. In these researches, different approaches for establishing the routing tree of mesh networks are analyzed, and some issues of time-slot allocation are discussed.


## 2.3. Spectral Reuse

This paper applies spectral reuse to solve the resource allocation problem for the 802.16 mesh network. The advantage of using spectral reuse is to improve the transmission capacity and the throughput of network. Fu et al. [10] proposed an algorithm to maximize the usage of spectral reuse. Chen et al. [11] studied how to use the spectral reuse to solve the problem of resource allocation.


## 2.4. Interference Model

Scheduling strategies must ensure that transmissions in each time slot do not collide. There are two types of collision situations in the wireless network environment. They are called Primary Interference and Secondary Interference [12, 13]. Primary Interference occurs in a single time slot of scheduling; the SS cannot do more than one thing. In other words, the SS can only transfer or receive data in a single time slot. Secondary Interference occurs when the originally receiver X turns into the transfer, but the user X is still in the range of the transfer Y. The user X will affect the transmission of the user Y. There are some studies that focus on WiMAX mesh network interference problems [14, 15], Wei et al. [16] proposed an interference-aware multihop routing algorithm to maximize the degree of use of network bandwidth to maximize the network throughput.


## 2.5. Fairness Scheduling

Nowadays the related works on WiMAX mesh networks through a network of relay stations scheduling and resource allocation are concerned widely. It is common to study the fairness in many wireless networks in [17–20]. Sayenko et al. [19] studied the proportional fairness and considered the difference between frequency selections with multiuser scheduling problems. Andrews and Zhang [20] proposed a round-robin based scheduling method for IEEE 802.16 BS to ensure QoS requirements of the SS in uplink (UL) and downlink (DL) can be met. But the network bandwidth usage efficiently and bandwidth requirements were not considered in [19, 20].In this paper, we propose heuristic scheduling algorithms that identify each SS to maximize the minimum satisfaction ratio in the network and, meanwhile, to meet the bandwidth requirements for each SS. We compare the QoS satisfaction ratio, throughput, and min satisfaction ratio with the previous method proposed in [21]. Experimental results show that our method is better in terms of QoS satisfaction ratio.


## 3. QoS-Based Max-Min Fair Scheduling

### 3.1. Problem Definition

Based on the WiMAX standard [1], a tree network topology G=(V,E) is given. For readability, the following parameters and variables are listed in Table 1. A BS as the root, a set of subscriber users 𝕊={s1,s2,…,sn} as the leaf nodes, and a set of relay stations ℝ={r1,r2,…,rm} as the intermediate nodes. Let the parameter cl be the link capacity of each link l,  ∀l∈E. Let the parameter bri be the minimum bandwidth requirements of each SS si during a frame. Let the parameter BRi be the maximum bandwidth requirements of each SS si during a frame. The problem is limited to the following restrictions:(1)
no spectral reuse for any pair of links which interfere with each other;(2)
an RS cannot transmit and receive data at the same time;(3)
the total number of data delivered by an RS to BS during a frame must be equal to the number of data received from its children node during one frame;(4)
must satisfy the minimum bandwidth requirements of each SS to guarantee QoS.Table 1
Parameters and variables table.
Symbol
Description
G = (V, E)
Mesh network topologyG
V
The set of stations
E
The set of edges
T
The set of time slot in a frame
H
The set of subchannel in each time slot
h
The index parameter of subchannel,∀h∈H
𝕊
A set of all the SSs
s
i
A subscriber SSi, ∀si∈𝕊
ℝ
Set of all relay stations
r
i
A relay nodei, ∀ri∈ℝ
c
l
The link capacity of each linkl, ∀l∈E
h
p
i
The set of hops fromsi to BS
b
r
i
The minimum bandwidth requirement of thesi for guaranteeing QoS
B
R
i
The maximum bandwidth requirement of thesi
λ
i
The actual quantity of nodei upload the packet, ∀i∈𝕊∪ℝ
σ
i
The actual quantity of nodei upload the required tile, ∀i∈𝕊∪ℝ
y
i
s
i satisfaction ratio
t
r
i
The tile requirement ofsi for transmitting packets from si to BS during each hop
TR
The set of tile requirement,TR={tri∣∀si∈𝕊}
I
(
·
)
The subset of nodes which will interfere with node or link transceiving
I
-
i
The subset of nodes which will not interfere withsi′s transceiving
pa
(
i
)
The parent of nodei on the tree topology
cd
(
r
)
The set of children node SSs or RSs ofr
f
t
,
h
l
A decision variable, which is 1 if linkl is assigned with time slot t and subchannel h, and 0 otherwise
O
L
i
,
I
L
i
The set of output and input links of nodei, respectivelyTherefore, the multihop fair scheduling with QoS control problem is defined as to find a way to schedule the subchannel-time slot (tile) for a scheduling frame. After the tile scheduling, the minimum satisfaction ratioyi of each si will be maximized, and the bandwidth requirements of each si will be satisfied to guarantee QoS.


### 3.2. Integer Linear Programming for the Problem

In [22], it was proved that scheduling with channel capacity is NP-hard. Therefore, our scheduling problem with time-varying channel will be NP-hard. To find an optimal solution, we provide an Integer Linear Programming (ILP) for this problem.For each nodei∈𝕊∪R, pa(i) denotes the parent of node i on the tree topology. For each RS r∈ℝ, the parameter cd(r) is used to represent the set of children node (SSs or RSs) of r. For each node i in tree network G, the variable ft,hl denotes that whether the link l=(i,j) is assigned with time-slot t and subchannel h. We refer to the method [23, 24] to verify whether there are interferences between these two edges. I(l) represents the interference link set of link l:
(1)Maximizey(2)∑l′∈I(l)‍ft,hl′+ft,hl≤1,∀h∈H,∀t∈T,∀l∈OLi,oooooooooooooooooooooooo.ooo∀i∈𝕊∪ℝ,(3)∑∀h∈H‍∑∀l∈OLr‍ft,hl+∑∀h∈H‍∑∀l∈ILr‍ft,hl≤1,∀t∈T,oooooooooooooooooooooooooooo∀r∈ℝ,(4)∑∀l∈ILr‍(ft,hl∑∀h∈H‍∑∀t∈T‍ft,hl)×cl≤∑∀l∈OLr‍(ft,hl∑∀h∈H‍∑∀t∈T‍ft,hl)×cl,∀r∈ℝ,(5)∑∀l∈OLi‍(∑∀h∈H‍∑∀t∈T‍ft,hl)×cl≥bri,∀i∈𝕊,(6)y≤yi,∀i∈𝕊,(7)whereyi=1BRi∑∀l∈OLi‍(∑∀h∈H‍∑∀t∈T‍ft,hl)×cl,∀i∈𝕊,(8)ft,hl={0,1},∀t∈T,∀h∈H,∀l∈E.The objective function of QoS-based max-min fair scheduling problem is shown as (1). The goal is to maximize the minimum satisfaction ratio y. The satisfaction ratio yi is calculated by (7). In (7), the parameter BRi is the maximum bandwidth requirement of si, the parameter cl is the capacity of link l, and the decision variables ft,hl are defined in (8). If the time-slot (t,h) is allocated to link l, the value of decision variable ft,hl is 1. Otherwise, the value of decision variable ft,hl is 0. The QoS-based max-min fair scheduling problem has four constraints as follows.(i)
The spectral reuse constraints are shown as (2). For all link l in OLi, a tile can be used no more than once in each pair of interference links I(l). Where the OLi is the set of output links of all nodes i∈𝕊∪ℝ.(ii)
The single transceiver constraints are shown as (3). For all time-slot t in T, each RS r in R cannot transmit and receive data in the same time slot.(iii)
The flow constraints are shown as (4). All data that are accepted by RS r in a frame will be sent out in the same frame. Where the parameters OLr and ILr are the set of output and input links of RS r.(iv)
The minimum bandwidth requirement constraints are shown as (5). The minimum bandwidth requirements of each si must be satisfied to guarantee QoS in a frame.(v)
The satisfaction ratio constraints are shown as (6). The satisfaction yi of each ssi will be greater than the variable y.


### 3.3. Greedy Algorithm for QoS-Based Max-Min Fair Scheduling

Though the ILP solution can be used to obtain optimal solutions for small-sized problem, but if the network scale grows larger, it has large time and space consumption for large-sized network. The heuristics algorithm is needed for better running time in large-sized network. In the following, we designed a heuristic algorithm.


#### 3.3.1. Heuristic Algorithm

The strategy of the proposed heuristic algorithm is smallest total bandwidth requirement first and then applying spectral reuse scheme to assign resource. After QoS of all SSs is guaranteed, the max-min fair scheduling scheme is used to enhance the overall throughput and satisfaction ratio. The proposed heuristic algorithm has four steps as follows.Step  1 (allocate limited resources to meet the QoS requirements of each SS). At first, the total number of tile requirements (tri×hpi) of each si is estimated. Then, the resources are allocated to all SSs by Algorithm 2  QoS_Scheduling() in increasing order of total tile requirements. Until the resources are not enough allocated or the requirements of all SSs are met, the scheduler will terminate the process of QoS_Scheduling().Step  2 (increase the number of meeting QoS requirements). If the bandwidth requirements of si are not satisfied, the spectral reuse mechanism is used to find available resource for each unmet SS in Algorithm 3  QoS_Spectral_Reuse(). The strategy of spectral reuse is to gain tiles from all allocated tiles of sj; there is no link between each sj and the picked si. Hence, the satisfaction rate has an opportunity to increase.Step  3 (remaining resources to do the max-min fair scheduling). When the first two steps are finished, then some remaining resources are available. Then, the available tiles are allocated to the SSs that have lowest satisfaction, and satisfaction ratio is upgraded by Algorithm 4   Maxmin_Scheduling().Step  4 (upgrade the min satisfaction ratio). Finally, Algorithm 5  Maxmin_Spectral_Reuse() finds out an si which has lowest satisfaction ratio among all SSs to increase its satisfaction ratio. Until all the SSs are allocated, available tiles by the spectral reuse mechanism or the satisfaction ratio of si are equal to 1. Then, the procedure of scheduling algorithm will be finished.


#### 3.3.2. Scheduling Algorithm Description with an Example

As shown in Figure1, the networks are composed of one BS, three RSs ={r1,r2,r3}, and six SSs ={s1,s2,s3,s4,s5,s6}. The number of maximum bandwidth requirements of each SSs BRi are {10, 10, 8, 8, 8, and 10}. The bandwidth requirements of SSs bri are {7, 2, 4, 5, 6, and 3} for guaranteeing QoS. The capacity of each link cl is set to 1. The number of time-slots t is set to 7. The number of subchannels h is set to 3. The interference of each RS and SS is defined as follows:
(9)I(r1)={s1,s2,r2,r3},I(r2)={r1,r3,s3,s4},I(r3)={r2,s5,s6},I(s1)={s2,r1},I(s6)={s5,r3}I(s2)={s1,r1,s3},I(s3)={s2,r4,s4},I(s4)={s3,r2,s5},I(s5)={s4,r3,s6}.Figure 1
The network topology.At first, the value oftri(=⌈BRi/ci⌉+∑∀j∈hpi∖{si}‍⌈BRi/cj⌉) of each si is calculated at lines (2)–(7) in Algorithm 1. Then, the value of TR is sorted by increasing order at line (8) in Algorithm 1. The value of parameter At is initialized as |H| for all time-slot t.Algorithm 1:Heuristic Algorithm.
Input:
G
,
𝕊
,
ℝ
,
H
,
T
,
br
,
BR
Output:
min_satisfaction_ratio,  QoS_satisfaction_ratio,  throughput
(1)Initialization: λi←0, σi←0, ∀si∈SS;
(2)for all SS node vi on G do
(3) tri←⌈BRici⌉
(4) for all RS vj on the path hpi from vi to BS do
(5) tri←tri+⌈BRicj⌉
(6) endfor
(7)endfor
(8)Sort (TR);
(9)At←|H|,∀t∈T
(10)Set all ssi.QoSAllocated = false;
(11)QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR);
(12)QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR);
(13)Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR);
(14)Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR);Algorithm 2:QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)Step  2.
(3)index←1
(4)for k=1→|hpi|
(5)  req←⌈brick⌉
(6) for t=index→|T|
(7)  if At≥req
(8)    At←At-req; req←0; k←k+1
(9)    index←t; t←|T|
(10)  else
(11)    if  (|T|-t)<(hpi-k)
(12)      free all tiles which allocated to si
(13)       SS←SS∖{si}
(14)      go to Step  1
(15)    else
(16)       At←0; req←req-At; index←t; t←|T|
(17)Step  3. if all hops of si are allocated successfully
(18) 𝕊←𝕊∖{si}
(19) σi←⌈brici⌉; λi←σi×ci;
(20) for all RS rsj on the path from si to BS do
(21)  σj←⌈bricj⌉; λj←σj×cj;
(22) endfor
(23) yi←λi+∑∀rsj∈hpiλjBRi×|hpi|;
(24)Step  4. if all SSs meet requirement or no sufficient resources can be allocated
(25)   terminate scheduling
(26)   else go to Step  1Algorithm 3:QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)  Recover all allocated tiles of sj to set R, ∀sj∈I-i
(3)Step  2.
(4)index←1
(5)for k=1→|hpi|
(6) req←⌈brick⌉
(7) for  t=index→|T|
(8)  if  (At+Rt)>req, then
(9)   if At≥req
(10)     At←At-req
(11)      else
(12)      At←0; Rt←Rt-(req-At)
(13)      req←0; index←t; t←|T|
(14)  else if  (|T|-t)<(hpi-k)
(15)      free all tiles which allocated to si during this step
(16)      SS←SS∖{si}
(17)      go to Step  1
(18)Step  3.
(19)if the resource is fully allocated successfully to all hops of si, then
(20) 𝕊←𝕊∖{si}
(21)  σi←⌈brici⌉; λi←λi+σi×ci;
(22) for all RS rsj on the path from si to BS do
(23)  σj←⌈bricj⌉; λj←λj+σj×cj;
(24) endfor
(25) yi←λi+∑∀rsj∈hpi‍λjBRi×|hpi|;
(26)Step  4. if all SSs meet QoS or no sufficient resources can be allocated, then
(27)   Termination
(28) else go to Step  1Algorithm 4:Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR).
Output:Y,A
(1)Step  1.
(2)Choose a si with the smallest satisfaction;
(3)if yi == 1, then terminate scheduling
(4)else go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→|hpi|
(8) req←⌈BRick⌉-σk
(9)  for t=index→|T|
(10) if At≥req
(11)    At←At-req; req←0; k←k+1
(12)    index←t; t←|T|
(13) else if At<req
(14)    At←0; tri←req-At
(15) else if  (|T|-t)<(|hpi|-k)
(16)    free all tiles which allocated to si in Step  2
(17)    SS←SS∖{si}
(18)    go to Step  1
(19)Step  3.
(20) if the resource is fully allocated successfully to all hops of si, then
(21) 𝕊←𝕊∖{si}
(22) σi←σi+1; λi←λi+ci; yi←λiBRi
(23)  for all RS rsj on the path from si to BS do
(24)  λj←λj+ci;
(25)  σj←σj+⌈λjcj⌉;
(26)Step  4.
(27)if yi = 1 or 𝕊 is empty, then
(28) terminate scheduling
(29)else go to Step  1Algorithm 5:Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR).
Output:Y
(1)Step  1. Choose a si with the smallest satisfaction;
(2)if yi = 1, then terminate scheduling
(3)else Recover all allocated tiles of sj to set R, ∀sj∈Ii-
(4)  go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→hpi
(8) req←tri
(9) for t=index→|T|
(10)  ifAt≥req, then
(11)  At←At-req; req←0; k←k+1
(12)  index←t; t←|T|
(13)  else
(14)   if (At+Rt)≥req, then
(15)    assign req available tiles to kth hop of si
(16)  else if (|T|-t)<(hpi-k), then
(17)    free all tiles which allocated to si in Step  2
(18)    𝕊←𝕊∖{si}
(19)    go to Step  1
(20)  else
(21)    At←0; Rt←0; req←req-At
(22)Step  3. if all hops of si are fully allocated successfully, then
(23) σi←σi+1; λi←λi+ci; yi←λiBRi;
(24) for all RS rsj on the path from si to BS do
(25) λj←λj+ci;
(26) σj←σj+⌈λjcj⌉;
(27) end for
(28)Step  4.
(29)if yi = 1 or 𝕊 is empty, then
(30) terminate scheduling
(31)else go to Step  1The limited resources are allocated by Algorithm2. The si is selected with minimum total tile requirement tri at line (1) of Algorithm 2. Then, the resources are allocated at lines (2)–(16) of Algorithm 2. After resources allocation are completed, the parameters and variables of the SS and RS will be updated at lines (17)–(23) of Algorithm 2. At lines (24)–(26) of Algorithm 2 if no available resources are able to allocate to each SS, the procedure goes back to the main algorithm. Otherwise, the scheduler continue to find the next SS which can allocate resources to meet the QoS requirements of the SS. In our example, the total number of tiles is 21. In Algorithm 2, the sequence of si will be selected as {s2,s6,s3}. The value of parameter tri is estimated as follows.                                      (10)tr1=⌈BR1c1⌉+∑∀j∈hp1∖{s1}‍⌈BR1cj⌉=14,tr2=⌈BR2c2⌉+∑∀j∈hp2∖{s2}‍⌈BR2cj⌉=4,tr3=⌈BR3c3⌉+∑∀j∈hp3∖{s3}‍⌈BR3cj⌉=8,tr4=⌈BR4c4⌉+∑∀j∈hp4∖{s4}‍⌈BR4cj⌉=10,tr5=⌈BR5c5⌉+∑∀j∈hp5∖{s5}‍⌈BR5cj⌉=12,tr6=⌈BR6c6⌉+∑∀j∈hp6∖{s6}‍⌈BR6cj⌉=6.The scheduling results of Algorithm2 are shown in Figure 2.Figure 2
The allocation of resources meets the QoS requirements ofs2, s3, and s6.Moreover, if the bandwidth requirements of some SSs are still unsatisfied, the number ofSS with QoS guarantee will be raised by Algorithm 3. The bandwidth requirement unsatisfied si will be found with the minimum tri at line (1) of Algorithm 3. All allocated tiles of sj, ∀sj∈I-i, are recovered to set R at line (2) of Algorithm 3. Then, the spectral reuse strategy is used to maximize satisfaction ratio at lines (3)–(17) in Algorithm 3 for picked si. If the available tiles At+Rt can meet the requirement of si at time slot t for kth hop, the required tiles are allocated at lines (8)–(13) of Algorithm 3. While the requirements of all hops are met, the parameters and variables of the SS and RS will be updated at lines (18)–(25) in Algorithm 3. Otherwise, all acquired tiles of si are freed at line (15) of Algorithm 3. If the resources allocation have not been finished, the scheduler will find out the next one to meet the bandwidth requirements of si to guarantee QoS by the spectral reuse strategy. Until the minimum bandwidth requirements of all SSs are satisfied or the available tiles are not enough to allocate, then this step will be terminated. The results of first hop of s4 are scheduled by spectral reuse strategy of Algorithm 3 as shown in Figure 3. Because the available tiles are insufficient at second hop, s4 cannot be assigned as shown in Figure 4. Hence, all acquired tiles of s4 need to be freed. Due to the available tiles which are not enough to assign, this step is terminated.Figure 3
s
4 performs the spectral reuse.Figure 4
When lacking resources,s4 cannot perform spectral reuse.If the remaining available tiles have not been allocated completely, then these remaining resources can increase the network minimum satisfaction ratio by Algorithm4. The SS would be picked with lowest satisfaction ratio in sequence at line (2) of Algorithm 4. While the lowest satisfaction ratio is equal to 1, the scheduling of Algorithm 4 is terminated.Otherwise, the scheduler will check whether there available tiles can be assigned to thesi at lines (5)–(18) of Algorithm 4, if the resources could be allocated to the SS. After the parameters and variables of SS and RS are updated at lines (19)–(26) of Algorithm 4, the scheduler continue to find out the lowest satisfaction ratio of SS and to assign available tiles to increase satisfaction ratio. Until no available tiles can be allocated or the requirements of all SSs are met, the scheduling procedure is terminated. The max-min fair scheduling is performed with remaining tiles in Algorithm 4. The satisfaction ratio of {s1,s4,s5} is 0. Because the second hop has no enough available tiles, the schedule fails for {s1,s4,s5}. The scheduling results of Algorithm 4 are shown in Figure 5.Figure 5
No remaining resources can be used to perform max-min fair scheduling.Finally, the spectral reuse strategy is operated on the SS which has lowest satisfaction ratio for increasing the minimum satisfaction ratio in Algorithm5. At line (1) of Algorithm 5, the scheduler pick a si that has lowest satisfaction ratio. If the lowest satisfaction ratio equals to 1 at line (2) of Algorithm 5, the scheduling of Algorithm 5 is terminated. Otherwise, all allocated tiles of sj are recovered to set R, ∀sj∈I-i at line (3) of Algorithm 5. Then, the spectral reuse strategy is used to allocate tiles to si for maximizing satisfaction ratio at lines (5)–(21) of Algorithm 5. When the available tiles set At enough to assign to kth hop, the tiles of At set are firstly allocated at lines (10)–(12)of Algorithm 5. When the set At cannot fulfill the req of si, both the set At and Rt are applied to allocate at lines (13)–(21) of Algorithm 5. When both the set At and Rt cannot satisfy the req of si at time slot t at line (21) of Algorithm 5, the difference of required tiles would be found at next time slot. If the requirement of all hops cannot be met, all acquired tiles of si have to be freed at lines (16)–(19) of Algorithm 5. Then, the scheduler continue to find out next SS until no resources can be allocated. By Algorithm 4, the scheduled satisfaction ratio of {s1,s4,s5} is 0. Algorithm 5 enhances satisfaction ratio of {s1,s4,s5} to {0.1,0.125,0.125}. The scheduling results of Algorithm 5 are shown in Figure 6.Figure 6
Using spectral reuse to perform max-min fair scheduling.Finally, we get min satisfaction ratio = 0.1, QoS satisfaction ratio = 0.5, and throughput = 12, as shown in Figure7.Figure 7
The result of example.


## 3.1. Problem Definition

Based on the WiMAX standard [1], a tree network topology G=(V,E) is given. For readability, the following parameters and variables are listed in Table 1. A BS as the root, a set of subscriber users 𝕊={s1,s2,…,sn} as the leaf nodes, and a set of relay stations ℝ={r1,r2,…,rm} as the intermediate nodes. Let the parameter cl be the link capacity of each link l,  ∀l∈E. Let the parameter bri be the minimum bandwidth requirements of each SS si during a frame. Let the parameter BRi be the maximum bandwidth requirements of each SS si during a frame. The problem is limited to the following restrictions:(1)
no spectral reuse for any pair of links which interfere with each other;(2)
an RS cannot transmit and receive data at the same time;(3)
the total number of data delivered by an RS to BS during a frame must be equal to the number of data received from its children node during one frame;(4)
must satisfy the minimum bandwidth requirements of each SS to guarantee QoS.Table 1
Parameters and variables table.
Symbol
Description
G = (V, E)
Mesh network topologyG
V
The set of stations
E
The set of edges
T
The set of time slot in a frame
H
The set of subchannel in each time slot
h
The index parameter of subchannel,∀h∈H
𝕊
A set of all the SSs
s
i
A subscriber SSi, ∀si∈𝕊
ℝ
Set of all relay stations
r
i
A relay nodei, ∀ri∈ℝ
c
l
The link capacity of each linkl, ∀l∈E
h
p
i
The set of hops fromsi to BS
b
r
i
The minimum bandwidth requirement of thesi for guaranteeing QoS
B
R
i
The maximum bandwidth requirement of thesi
λ
i
The actual quantity of nodei upload the packet, ∀i∈𝕊∪ℝ
σ
i
The actual quantity of nodei upload the required tile, ∀i∈𝕊∪ℝ
y
i
s
i satisfaction ratio
t
r
i
The tile requirement ofsi for transmitting packets from si to BS during each hop
TR
The set of tile requirement,TR={tri∣∀si∈𝕊}
I
(
·
)
The subset of nodes which will interfere with node or link transceiving
I
-
i
The subset of nodes which will not interfere withsi′s transceiving
pa
(
i
)
The parent of nodei on the tree topology
cd
(
r
)
The set of children node SSs or RSs ofr
f
t
,
h
l
A decision variable, which is 1 if linkl is assigned with time slot t and subchannel h, and 0 otherwise
O
L
i
,
I
L
i
The set of output and input links of nodei, respectivelyTherefore, the multihop fair scheduling with QoS control problem is defined as to find a way to schedule the subchannel-time slot (tile) for a scheduling frame. After the tile scheduling, the minimum satisfaction ratioyi of each si will be maximized, and the bandwidth requirements of each si will be satisfied to guarantee QoS.


## 3.2. Integer Linear Programming for the Problem

In [22], it was proved that scheduling with channel capacity is NP-hard. Therefore, our scheduling problem with time-varying channel will be NP-hard. To find an optimal solution, we provide an Integer Linear Programming (ILP) for this problem.For each nodei∈𝕊∪R, pa(i) denotes the parent of node i on the tree topology. For each RS r∈ℝ, the parameter cd(r) is used to represent the set of children node (SSs or RSs) of r. For each node i in tree network G, the variable ft,hl denotes that whether the link l=(i,j) is assigned with time-slot t and subchannel h. We refer to the method [23, 24] to verify whether there are interferences between these two edges. I(l) represents the interference link set of link l:
(1)Maximizey(2)∑l′∈I(l)‍ft,hl′+ft,hl≤1,∀h∈H,∀t∈T,∀l∈OLi,oooooooooooooooooooooooo.ooo∀i∈𝕊∪ℝ,(3)∑∀h∈H‍∑∀l∈OLr‍ft,hl+∑∀h∈H‍∑∀l∈ILr‍ft,hl≤1,∀t∈T,oooooooooooooooooooooooooooo∀r∈ℝ,(4)∑∀l∈ILr‍(ft,hl∑∀h∈H‍∑∀t∈T‍ft,hl)×cl≤∑∀l∈OLr‍(ft,hl∑∀h∈H‍∑∀t∈T‍ft,hl)×cl,∀r∈ℝ,(5)∑∀l∈OLi‍(∑∀h∈H‍∑∀t∈T‍ft,hl)×cl≥bri,∀i∈𝕊,(6)y≤yi,∀i∈𝕊,(7)whereyi=1BRi∑∀l∈OLi‍(∑∀h∈H‍∑∀t∈T‍ft,hl)×cl,∀i∈𝕊,(8)ft,hl={0,1},∀t∈T,∀h∈H,∀l∈E.The objective function of QoS-based max-min fair scheduling problem is shown as (1). The goal is to maximize the minimum satisfaction ratio y. The satisfaction ratio yi is calculated by (7). In (7), the parameter BRi is the maximum bandwidth requirement of si, the parameter cl is the capacity of link l, and the decision variables ft,hl are defined in (8). If the time-slot (t,h) is allocated to link l, the value of decision variable ft,hl is 1. Otherwise, the value of decision variable ft,hl is 0. The QoS-based max-min fair scheduling problem has four constraints as follows.(i)
The spectral reuse constraints are shown as (2). For all link l in OLi, a tile can be used no more than once in each pair of interference links I(l). Where the OLi is the set of output links of all nodes i∈𝕊∪ℝ.(ii)
The single transceiver constraints are shown as (3). For all time-slot t in T, each RS r in R cannot transmit and receive data in the same time slot.(iii)
The flow constraints are shown as (4). All data that are accepted by RS r in a frame will be sent out in the same frame. Where the parameters OLr and ILr are the set of output and input links of RS r.(iv)
The minimum bandwidth requirement constraints are shown as (5). The minimum bandwidth requirements of each si must be satisfied to guarantee QoS in a frame.(v)
The satisfaction ratio constraints are shown as (6). The satisfaction yi of each ssi will be greater than the variable y.


## 3.3. Greedy Algorithm for QoS-Based Max-Min Fair Scheduling

Though the ILP solution can be used to obtain optimal solutions for small-sized problem, but if the network scale grows larger, it has large time and space consumption for large-sized network. The heuristics algorithm is needed for better running time in large-sized network. In the following, we designed a heuristic algorithm.


### 3.3.1. Heuristic Algorithm

The strategy of the proposed heuristic algorithm is smallest total bandwidth requirement first and then applying spectral reuse scheme to assign resource. After QoS of all SSs is guaranteed, the max-min fair scheduling scheme is used to enhance the overall throughput and satisfaction ratio. The proposed heuristic algorithm has four steps as follows.Step  1 (allocate limited resources to meet the QoS requirements of each SS). At first, the total number of tile requirements (tri×hpi) of each si is estimated. Then, the resources are allocated to all SSs by Algorithm 2  QoS_Scheduling() in increasing order of total tile requirements. Until the resources are not enough allocated or the requirements of all SSs are met, the scheduler will terminate the process of QoS_Scheduling().Step  2 (increase the number of meeting QoS requirements). If the bandwidth requirements of si are not satisfied, the spectral reuse mechanism is used to find available resource for each unmet SS in Algorithm 3  QoS_Spectral_Reuse(). The strategy of spectral reuse is to gain tiles from all allocated tiles of sj; there is no link between each sj and the picked si. Hence, the satisfaction rate has an opportunity to increase.Step  3 (remaining resources to do the max-min fair scheduling). When the first two steps are finished, then some remaining resources are available. Then, the available tiles are allocated to the SSs that have lowest satisfaction, and satisfaction ratio is upgraded by Algorithm 4   Maxmin_Scheduling().Step  4 (upgrade the min satisfaction ratio). Finally, Algorithm 5  Maxmin_Spectral_Reuse() finds out an si which has lowest satisfaction ratio among all SSs to increase its satisfaction ratio. Until all the SSs are allocated, available tiles by the spectral reuse mechanism or the satisfaction ratio of si are equal to 1. Then, the procedure of scheduling algorithm will be finished.


### 3.3.2. Scheduling Algorithm Description with an Example

As shown in Figure1, the networks are composed of one BS, three RSs ={r1,r2,r3}, and six SSs ={s1,s2,s3,s4,s5,s6}. The number of maximum bandwidth requirements of each SSs BRi are {10, 10, 8, 8, 8, and 10}. The bandwidth requirements of SSs bri are {7, 2, 4, 5, 6, and 3} for guaranteeing QoS. The capacity of each link cl is set to 1. The number of time-slots t is set to 7. The number of subchannels h is set to 3. The interference of each RS and SS is defined as follows:
(9)I(r1)={s1,s2,r2,r3},I(r2)={r1,r3,s3,s4},I(r3)={r2,s5,s6},I(s1)={s2,r1},I(s6)={s5,r3}I(s2)={s1,r1,s3},I(s3)={s2,r4,s4},I(s4)={s3,r2,s5},I(s5)={s4,r3,s6}.Figure 1
The network topology.At first, the value oftri(=⌈BRi/ci⌉+∑∀j∈hpi∖{si}‍⌈BRi/cj⌉) of each si is calculated at lines (2)–(7) in Algorithm 1. Then, the value of TR is sorted by increasing order at line (8) in Algorithm 1. The value of parameter At is initialized as |H| for all time-slot t.Algorithm 1:Heuristic Algorithm.
Input:
G
,
𝕊
,
ℝ
,
H
,
T
,
br
,
BR
Output:
min_satisfaction_ratio,  QoS_satisfaction_ratio,  throughput
(1)Initialization: λi←0, σi←0, ∀si∈SS;
(2)for all SS node vi on G do
(3) tri←⌈BRici⌉
(4) for all RS vj on the path hpi from vi to BS do
(5) tri←tri+⌈BRicj⌉
(6) endfor
(7)endfor
(8)Sort (TR);
(9)At←|H|,∀t∈T
(10)Set all ssi.QoSAllocated = false;
(11)QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR);
(12)QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR);
(13)Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR);
(14)Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR);Algorithm 2:QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)Step  2.
(3)index←1
(4)for k=1→|hpi|
(5)  req←⌈brick⌉
(6) for t=index→|T|
(7)  if At≥req
(8)    At←At-req; req←0; k←k+1
(9)    index←t; t←|T|
(10)  else
(11)    if  (|T|-t)<(hpi-k)
(12)      free all tiles which allocated to si
(13)       SS←SS∖{si}
(14)      go to Step  1
(15)    else
(16)       At←0; req←req-At; index←t; t←|T|
(17)Step  3. if all hops of si are allocated successfully
(18) 𝕊←𝕊∖{si}
(19) σi←⌈brici⌉; λi←σi×ci;
(20) for all RS rsj on the path from si to BS do
(21)  σj←⌈bricj⌉; λj←σj×cj;
(22) endfor
(23) yi←λi+∑∀rsj∈hpiλjBRi×|hpi|;
(24)Step  4. if all SSs meet requirement or no sufficient resources can be allocated
(25)   terminate scheduling
(26)   else go to Step  1Algorithm 3:QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)  Recover all allocated tiles of sj to set R, ∀sj∈I-i
(3)Step  2.
(4)index←1
(5)for k=1→|hpi|
(6) req←⌈brick⌉
(7) for  t=index→|T|
(8)  if  (At+Rt)>req, then
(9)   if At≥req
(10)     At←At-req
(11)      else
(12)      At←0; Rt←Rt-(req-At)
(13)      req←0; index←t; t←|T|
(14)  else if  (|T|-t)<(hpi-k)
(15)      free all tiles which allocated to si during this step
(16)      SS←SS∖{si}
(17)      go to Step  1
(18)Step  3.
(19)if the resource is fully allocated successfully to all hops of si, then
(20) 𝕊←𝕊∖{si}
(21)  σi←⌈brici⌉; λi←λi+σi×ci;
(22) for all RS rsj on the path from si to BS do
(23)  σj←⌈bricj⌉; λj←λj+σj×cj;
(24) endfor
(25) yi←λi+∑∀rsj∈hpi‍λjBRi×|hpi|;
(26)Step  4. if all SSs meet QoS or no sufficient resources can be allocated, then
(27)   Termination
(28) else go to Step  1Algorithm 4:Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR).
Output:Y,A
(1)Step  1.
(2)Choose a si with the smallest satisfaction;
(3)if yi == 1, then terminate scheduling
(4)else go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→|hpi|
(8) req←⌈BRick⌉-σk
(9)  for t=index→|T|
(10) if At≥req
(11)    At←At-req; req←0; k←k+1
(12)    index←t; t←|T|
(13) else if At<req
(14)    At←0; tri←req-At
(15) else if  (|T|-t)<(|hpi|-k)
(16)    free all tiles which allocated to si in Step  2
(17)    SS←SS∖{si}
(18)    go to Step  1
(19)Step  3.
(20) if the resource is fully allocated successfully to all hops of si, then
(21) 𝕊←𝕊∖{si}
(22) σi←σi+1; λi←λi+ci; yi←λiBRi
(23)  for all RS rsj on the path from si to BS do
(24)  λj←λj+ci;
(25)  σj←σj+⌈λjcj⌉;
(26)Step  4.
(27)if yi = 1 or 𝕊 is empty, then
(28) terminate scheduling
(29)else go to Step  1Algorithm 5:Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR).
Output:Y
(1)Step  1. Choose a si with the smallest satisfaction;
(2)if yi = 1, then terminate scheduling
(3)else Recover all allocated tiles of sj to set R, ∀sj∈Ii-
(4)  go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→hpi
(8) req←tri
(9) for t=index→|T|
(10)  ifAt≥req, then
(11)  At←At-req; req←0; k←k+1
(12)  index←t; t←|T|
(13)  else
(14)   if (At+Rt)≥req, then
(15)    assign req available tiles to kth hop of si
(16)  else if (|T|-t)<(hpi-k), then
(17)    free all tiles which allocated to si in Step  2
(18)    𝕊←𝕊∖{si}
(19)    go to Step  1
(20)  else
(21)    At←0; Rt←0; req←req-At
(22)Step  3. if all hops of si are fully allocated successfully, then
(23) σi←σi+1; λi←λi+ci; yi←λiBRi;
(24) for all RS rsj on the path from si to BS do
(25) λj←λj+ci;
(26) σj←σj+⌈λjcj⌉;
(27) end for
(28)Step  4.
(29)if yi = 1 or 𝕊 is empty, then
(30) terminate scheduling
(31)else go to Step  1The limited resources are allocated by Algorithm2. The si is selected with minimum total tile requirement tri at line (1) of Algorithm 2. Then, the resources are allocated at lines (2)–(16) of Algorithm 2. After resources allocation are completed, the parameters and variables of the SS and RS will be updated at lines (17)–(23) of Algorithm 2. At lines (24)–(26) of Algorithm 2 if no available resources are able to allocate to each SS, the procedure goes back to the main algorithm. Otherwise, the scheduler continue to find the next SS which can allocate resources to meet the QoS requirements of the SS. In our example, the total number of tiles is 21. In Algorithm 2, the sequence of si will be selected as {s2,s6,s3}. The value of parameter tri is estimated as follows.                                      (10)tr1=⌈BR1c1⌉+∑∀j∈hp1∖{s1}‍⌈BR1cj⌉=14,tr2=⌈BR2c2⌉+∑∀j∈hp2∖{s2}‍⌈BR2cj⌉=4,tr3=⌈BR3c3⌉+∑∀j∈hp3∖{s3}‍⌈BR3cj⌉=8,tr4=⌈BR4c4⌉+∑∀j∈hp4∖{s4}‍⌈BR4cj⌉=10,tr5=⌈BR5c5⌉+∑∀j∈hp5∖{s5}‍⌈BR5cj⌉=12,tr6=⌈BR6c6⌉+∑∀j∈hp6∖{s6}‍⌈BR6cj⌉=6.The scheduling results of Algorithm2 are shown in Figure 2.Figure 2
The allocation of resources meets the QoS requirements ofs2, s3, and s6.Moreover, if the bandwidth requirements of some SSs are still unsatisfied, the number ofSS with QoS guarantee will be raised by Algorithm 3. The bandwidth requirement unsatisfied si will be found with the minimum tri at line (1) of Algorithm 3. All allocated tiles of sj, ∀sj∈I-i, are recovered to set R at line (2) of Algorithm 3. Then, the spectral reuse strategy is used to maximize satisfaction ratio at lines (3)–(17) in Algorithm 3 for picked si. If the available tiles At+Rt can meet the requirement of si at time slot t for kth hop, the required tiles are allocated at lines (8)–(13) of Algorithm 3. While the requirements of all hops are met, the parameters and variables of the SS and RS will be updated at lines (18)–(25) in Algorithm 3. Otherwise, all acquired tiles of si are freed at line (15) of Algorithm 3. If the resources allocation have not been finished, the scheduler will find out the next one to meet the bandwidth requirements of si to guarantee QoS by the spectral reuse strategy. Until the minimum bandwidth requirements of all SSs are satisfied or the available tiles are not enough to allocate, then this step will be terminated. The results of first hop of s4 are scheduled by spectral reuse strategy of Algorithm 3 as shown in Figure 3. Because the available tiles are insufficient at second hop, s4 cannot be assigned as shown in Figure 4. Hence, all acquired tiles of s4 need to be freed. Due to the available tiles which are not enough to assign, this step is terminated.Figure 3
s
4 performs the spectral reuse.Figure 4
When lacking resources,s4 cannot perform spectral reuse.If the remaining available tiles have not been allocated completely, then these remaining resources can increase the network minimum satisfaction ratio by Algorithm4. The SS would be picked with lowest satisfaction ratio in sequence at line (2) of Algorithm 4. While the lowest satisfaction ratio is equal to 1, the scheduling of Algorithm 4 is terminated.Otherwise, the scheduler will check whether there available tiles can be assigned to thesi at lines (5)–(18) of Algorithm 4, if the resources could be allocated to the SS. After the parameters and variables of SS and RS are updated at lines (19)–(26) of Algorithm 4, the scheduler continue to find out the lowest satisfaction ratio of SS and to assign available tiles to increase satisfaction ratio. Until no available tiles can be allocated or the requirements of all SSs are met, the scheduling procedure is terminated. The max-min fair scheduling is performed with remaining tiles in Algorithm 4. The satisfaction ratio of {s1,s4,s5} is 0. Because the second hop has no enough available tiles, the schedule fails for {s1,s4,s5}. The scheduling results of Algorithm 4 are shown in Figure 5.Figure 5
No remaining resources can be used to perform max-min fair scheduling.Finally, the spectral reuse strategy is operated on the SS which has lowest satisfaction ratio for increasing the minimum satisfaction ratio in Algorithm5. At line (1) of Algorithm 5, the scheduler pick a si that has lowest satisfaction ratio. If the lowest satisfaction ratio equals to 1 at line (2) of Algorithm 5, the scheduling of Algorithm 5 is terminated. Otherwise, all allocated tiles of sj are recovered to set R, ∀sj∈I-i at line (3) of Algorithm 5. Then, the spectral reuse strategy is used to allocate tiles to si for maximizing satisfaction ratio at lines (5)–(21) of Algorithm 5. When the available tiles set At enough to assign to kth hop, the tiles of At set are firstly allocated at lines (10)–(12)of Algorithm 5. When the set At cannot fulfill the req of si, both the set At and Rt are applied to allocate at lines (13)–(21) of Algorithm 5. When both the set At and Rt cannot satisfy the req of si at time slot t at line (21) of Algorithm 5, the difference of required tiles would be found at next time slot. If the requirement of all hops cannot be met, all acquired tiles of si have to be freed at lines (16)–(19) of Algorithm 5. Then, the scheduler continue to find out next SS until no resources can be allocated. By Algorithm 4, the scheduled satisfaction ratio of {s1,s4,s5} is 0. Algorithm 5 enhances satisfaction ratio of {s1,s4,s5} to {0.1,0.125,0.125}. The scheduling results of Algorithm 5 are shown in Figure 6.Figure 6
Using spectral reuse to perform max-min fair scheduling.Finally, we get min satisfaction ratio = 0.1, QoS satisfaction ratio = 0.5, and throughput = 12, as shown in Figure7.Figure 7
The result of example.


## 3.3.1. Heuristic Algorithm

The strategy of the proposed heuristic algorithm is smallest total bandwidth requirement first and then applying spectral reuse scheme to assign resource. After QoS of all SSs is guaranteed, the max-min fair scheduling scheme is used to enhance the overall throughput and satisfaction ratio. The proposed heuristic algorithm has four steps as follows.Step  1 (allocate limited resources to meet the QoS requirements of each SS). At first, the total number of tile requirements (tri×hpi) of each si is estimated. Then, the resources are allocated to all SSs by Algorithm 2  QoS_Scheduling() in increasing order of total tile requirements. Until the resources are not enough allocated or the requirements of all SSs are met, the scheduler will terminate the process of QoS_Scheduling().Step  2 (increase the number of meeting QoS requirements). If the bandwidth requirements of si are not satisfied, the spectral reuse mechanism is used to find available resource for each unmet SS in Algorithm 3  QoS_Spectral_Reuse(). The strategy of spectral reuse is to gain tiles from all allocated tiles of sj; there is no link between each sj and the picked si. Hence, the satisfaction rate has an opportunity to increase.Step  3 (remaining resources to do the max-min fair scheduling). When the first two steps are finished, then some remaining resources are available. Then, the available tiles are allocated to the SSs that have lowest satisfaction, and satisfaction ratio is upgraded by Algorithm 4   Maxmin_Scheduling().Step  4 (upgrade the min satisfaction ratio). Finally, Algorithm 5  Maxmin_Spectral_Reuse() finds out an si which has lowest satisfaction ratio among all SSs to increase its satisfaction ratio. Until all the SSs are allocated, available tiles by the spectral reuse mechanism or the satisfaction ratio of si are equal to 1. Then, the procedure of scheduling algorithm will be finished.


## 3.3.2. Scheduling Algorithm Description with an Example

As shown in Figure1, the networks are composed of one BS, three RSs ={r1,r2,r3}, and six SSs ={s1,s2,s3,s4,s5,s6}. The number of maximum bandwidth requirements of each SSs BRi are {10, 10, 8, 8, 8, and 10}. The bandwidth requirements of SSs bri are {7, 2, 4, 5, 6, and 3} for guaranteeing QoS. The capacity of each link cl is set to 1. The number of time-slots t is set to 7. The number of subchannels h is set to 3. The interference of each RS and SS is defined as follows:
(9)I(r1)={s1,s2,r2,r3},I(r2)={r1,r3,s3,s4},I(r3)={r2,s5,s6},I(s1)={s2,r1},I(s6)={s5,r3}I(s2)={s1,r1,s3},I(s3)={s2,r4,s4},I(s4)={s3,r2,s5},I(s5)={s4,r3,s6}.Figure 1
The network topology.At first, the value oftri(=⌈BRi/ci⌉+∑∀j∈hpi∖{si}‍⌈BRi/cj⌉) of each si is calculated at lines (2)–(7) in Algorithm 1. Then, the value of TR is sorted by increasing order at line (8) in Algorithm 1. The value of parameter At is initialized as |H| for all time-slot t.Algorithm 1:Heuristic Algorithm.
Input:
G
,
𝕊
,
ℝ
,
H
,
T
,
br
,
BR
Output:
min_satisfaction_ratio,  QoS_satisfaction_ratio,  throughput
(1)Initialization: λi←0, σi←0, ∀si∈SS;
(2)for all SS node vi on G do
(3) tri←⌈BRici⌉
(4) for all RS vj on the path hpi from vi to BS do
(5) tri←tri+⌈BRicj⌉
(6) endfor
(7)endfor
(8)Sort (TR);
(9)At←|H|,∀t∈T
(10)Set all ssi.QoSAllocated = false;
(11)QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR);
(12)QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR);
(13)Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR);
(14)Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR);Algorithm 2:QoS_Scheduling (G,𝕊,ℝ,A,T,TR,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)Step  2.
(3)index←1
(4)for k=1→|hpi|
(5)  req←⌈brick⌉
(6) for t=index→|T|
(7)  if At≥req
(8)    At←At-req; req←0; k←k+1
(9)    index←t; t←|T|
(10)  else
(11)    if  (|T|-t)<(hpi-k)
(12)      free all tiles which allocated to si
(13)       SS←SS∖{si}
(14)      go to Step  1
(15)    else
(16)       At←0; req←req-At; index←t; t←|T|
(17)Step  3. if all hops of si are allocated successfully
(18) 𝕊←𝕊∖{si}
(19) σi←⌈brici⌉; λi←σi×ci;
(20) for all RS rsj on the path from si to BS do
(21)  σj←⌈bricj⌉; λj←σj×cj;
(22) endfor
(23) yi←λi+∑∀rsj∈hpiλjBRi×|hpi|;
(24)Step  4. if all SSs meet requirement or no sufficient resources can be allocated
(25)   terminate scheduling
(26)   else go to Step  1Algorithm 3:QoS_Spectral_Reuse (G,𝕊,ℝ,A,T,TR,I-,br,BR).
Output:Y,A
(1)Step  1. Choose a si from SS set with the minimal total tile requirement tri
(2)  Recover all allocated tiles of sj to set R, ∀sj∈I-i
(3)Step  2.
(4)index←1
(5)for k=1→|hpi|
(6) req←⌈brick⌉
(7) for  t=index→|T|
(8)  if  (At+Rt)>req, then
(9)   if At≥req
(10)     At←At-req
(11)      else
(12)      At←0; Rt←Rt-(req-At)
(13)      req←0; index←t; t←|T|
(14)  else if  (|T|-t)<(hpi-k)
(15)      free all tiles which allocated to si during this step
(16)      SS←SS∖{si}
(17)      go to Step  1
(18)Step  3.
(19)if the resource is fully allocated successfully to all hops of si, then
(20) 𝕊←𝕊∖{si}
(21)  σi←⌈brici⌉; λi←λi+σi×ci;
(22) for all RS rsj on the path from si to BS do
(23)  σj←⌈bricj⌉; λj←λj+σj×cj;
(24) endfor
(25) yi←λi+∑∀rsj∈hpi‍λjBRi×|hpi|;
(26)Step  4. if all SSs meet QoS or no sufficient resources can be allocated, then
(27)   Termination
(28) else go to Step  1Algorithm 4:Maxmin_Scheduling (G,𝕊,ℝ,A,T,Y,BR).
Output:Y,A
(1)Step  1.
(2)Choose a si with the smallest satisfaction;
(3)if yi == 1, then terminate scheduling
(4)else go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→|hpi|
(8) req←⌈BRick⌉-σk
(9)  for t=index→|T|
(10) if At≥req
(11)    At←At-req; req←0; k←k+1
(12)    index←t; t←|T|
(13) else if At<req
(14)    At←0; tri←req-At
(15) else if  (|T|-t)<(|hpi|-k)
(16)    free all tiles which allocated to si in Step  2
(17)    SS←SS∖{si}
(18)    go to Step  1
(19)Step  3.
(20) if the resource is fully allocated successfully to all hops of si, then
(21) 𝕊←𝕊∖{si}
(22) σi←σi+1; λi←λi+ci; yi←λiBRi
(23)  for all RS rsj on the path from si to BS do
(24)  λj←λj+ci;
(25)  σj←σj+⌈λjcj⌉;
(26)Step  4.
(27)if yi = 1 or 𝕊 is empty, then
(28) terminate scheduling
(29)else go to Step  1Algorithm 5:Maxmin_Spectral_Reuse (G,𝕊,ℝ,A,T,Y,I-,BR).
Output:Y
(1)Step  1. Choose a si with the smallest satisfaction;
(2)if yi = 1, then terminate scheduling
(3)else Recover all allocated tiles of sj to set R, ∀sj∈Ii-
(4)  go to Step  2
(5)Step  2.
(6)index←1
(7)for k=1→hpi
(8) req←tri
(9) for t=index→|T|
(10)  ifAt≥req, then
(11)  At←At-req; req←0; k←k+1
(12)  index←t; t←|T|
(13)  else
(14)   if (At+Rt)≥req, then
(15)    assign req available tiles to kth hop of si
(16)  else if (|T|-t)<(hpi-k), then
(17)    free all tiles which allocated to si in Step  2
(18)    𝕊←𝕊∖{si}
(19)    go to Step  1
(20)  else
(21)    At←0; Rt←0; req←req-At
(22)Step  3. if all hops of si are fully allocated successfully, then
(23) σi←σi+1; λi←λi+ci; yi←λiBRi;
(24) for all RS rsj on the path from si to BS do
(25) λj←λj+ci;
(26) σj←σj+⌈λjcj⌉;
(27) end for
(28)Step  4.
(29)if yi = 1 or 𝕊 is empty, then
(30) terminate scheduling
(31)else go to Step  1The limited resources are allocated by Algorithm2. The si is selected with minimum total tile requirement tri at line (1) of Algorithm 2. Then, the resources are allocated at lines (2)–(16) of Algorithm 2. After resources allocation are completed, the parameters and variables of the SS and RS will be updated at lines (17)–(23) of Algorithm 2. At lines (24)–(26) of Algorithm 2 if no available resources are able to allocate to each SS, the procedure goes back to the main algorithm. Otherwise, the scheduler continue to find the next SS which can allocate resources to meet the QoS requirements of the SS. In our example, the total number of tiles is 21. In Algorithm 2, the sequence of si will be selected as {s2,s6,s3}. The value of parameter tri is estimated as follows.                                      (10)tr1=⌈BR1c1⌉+∑∀j∈hp1∖{s1}‍⌈BR1cj⌉=14,tr2=⌈BR2c2⌉+∑∀j∈hp2∖{s2}‍⌈BR2cj⌉=4,tr3=⌈BR3c3⌉+∑∀j∈hp3∖{s3}‍⌈BR3cj⌉=8,tr4=⌈BR4c4⌉+∑∀j∈hp4∖{s4}‍⌈BR4cj⌉=10,tr5=⌈BR5c5⌉+∑∀j∈hp5∖{s5}‍⌈BR5cj⌉=12,tr6=⌈BR6c6⌉+∑∀j∈hp6∖{s6}‍⌈BR6cj⌉=6.The scheduling results of Algorithm2 are shown in Figure 2.Figure 2
The allocation of resources meets the QoS requirements ofs2, s3, and s6.Moreover, if the bandwidth requirements of some SSs are still unsatisfied, the number ofSS with QoS guarantee will be raised by Algorithm 3. The bandwidth requirement unsatisfied si will be found with the minimum tri at line (1) of Algorithm 3. All allocated tiles of sj, ∀sj∈I-i, are recovered to set R at line (2) of Algorithm 3. Then, the spectral reuse strategy is used to maximize satisfaction ratio at lines (3)–(17) in Algorithm 3 for picked si. If the available tiles At+Rt can meet the requirement of si at time slot t for kth hop, the required tiles are allocated at lines (8)–(13) of Algorithm 3. While the requirements of all hops are met, the parameters and variables of the SS and RS will be updated at lines (18)–(25) in Algorithm 3. Otherwise, all acquired tiles of si are freed at line (15) of Algorithm 3. If the resources allocation have not been finished, the scheduler will find out the next one to meet the bandwidth requirements of si to guarantee QoS by the spectral reuse strategy. Until the minimum bandwidth requirements of all SSs are satisfied or the available tiles are not enough to allocate, then this step will be terminated. The results of first hop of s4 are scheduled by spectral reuse strategy of Algorithm 3 as shown in Figure 3. Because the available tiles are insufficient at second hop, s4 cannot be assigned as shown in Figure 4. Hence, all acquired tiles of s4 need to be freed. Due to the available tiles which are not enough to assign, this step is terminated.Figure 3
s
4 performs the spectral reuse.Figure 4
When lacking resources,s4 cannot perform spectral reuse.If the remaining available tiles have not been allocated completely, then these remaining resources can increase the network minimum satisfaction ratio by Algorithm4. The SS would be picked with lowest satisfaction ratio in sequence at line (2) of Algorithm 4. While the lowest satisfaction ratio is equal to 1, the scheduling of Algorithm 4 is terminated.Otherwise, the scheduler will check whether there available tiles can be assigned to thesi at lines (5)–(18) of Algorithm 4, if the resources could be allocated to the SS. After the parameters and variables of SS and RS are updated at lines (19)–(26) of Algorithm 4, the scheduler continue to find out the lowest satisfaction ratio of SS and to assign available tiles to increase satisfaction ratio. Until no available tiles can be allocated or the requirements of all SSs are met, the scheduling procedure is terminated. The max-min fair scheduling is performed with remaining tiles in Algorithm 4. The satisfaction ratio of {s1,s4,s5} is 0. Because the second hop has no enough available tiles, the schedule fails for {s1,s4,s5}. The scheduling results of Algorithm 4 are shown in Figure 5.Figure 5
No remaining resources can be used to perform max-min fair scheduling.Finally, the spectral reuse strategy is operated on the SS which has lowest satisfaction ratio for increasing the minimum satisfaction ratio in Algorithm5. At line (1) of Algorithm 5, the scheduler pick a si that has lowest satisfaction ratio. If the lowest satisfaction ratio equals to 1 at line (2) of Algorithm 5, the scheduling of Algorithm 5 is terminated. Otherwise, all allocated tiles of sj are recovered to set R, ∀sj∈I-i at line (3) of Algorithm 5. Then, the spectral reuse strategy is used to allocate tiles to si for maximizing satisfaction ratio at lines (5)–(21) of Algorithm 5. When the available tiles set At enough to assign to kth hop, the tiles of At set are firstly allocated at lines (10)–(12)of Algorithm 5. When the set At cannot fulfill the req of si, both the set At and Rt are applied to allocate at lines (13)–(21) of Algorithm 5. When both the set At and Rt cannot satisfy the req of si at time slot t at line (21) of Algorithm 5, the difference of required tiles would be found at next time slot. If the requirement of all hops cannot be met, all acquired tiles of si have to be freed at lines (16)–(19) of Algorithm 5. Then, the scheduler continue to find out next SS until no resources can be allocated. By Algorithm 4, the scheduled satisfaction ratio of {s1,s4,s5} is 0. Algorithm 5 enhances satisfaction ratio of {s1,s4,s5} to {0.1,0.125,0.125}. The scheduling results of Algorithm 5 are shown in Figure 6.Figure 6
Using spectral reuse to perform max-min fair scheduling.Finally, we get min satisfaction ratio = 0.1, QoS satisfaction ratio = 0.5, and throughput = 12, as shown in Figure7.Figure 7
The result of example.


## 4. Simulation

In this section, we implement our heuristic algorithms and the algorithm proposed in [21] for performance comparison. We compare three parameters in the experimental results, namely, average minimum satisfaction ratio, average QoS satisfaction ratio, and average throughput.


### 4.1. Environmental Setup

For experimental environment setting, SS transmission range and interference range are set 1000 and 1000; RS and the BS transmission range and interference range are set 1000 and 2000. BS was deployed at the center of the field. Multihop shortest path routing was adopted to obtain the network topology. SS is distributed in the field by random, each data packet requirement and QoS requirement of SS are set randomly among 2 to 8, and the QoS requirements of each SS must be less than or equal to the data packet requirement.In the beginning, we use our heuristic algorithm and scheduling method of [21] in 1500 × 1500 square units and deployed 4 RSs to compare with three goals. These three goals are minimum satisfaction ratio, QoS satisfaction ratio, and throughput. For OFDMA setting, the number of time slots and subchannels are 12 and 5 in a frame. Then, we consider another large scale network which has 3000 × 3000 square units and deploy 16 RSs. For OFDMA setting, time-slots and subchannels number are 48 and 5 in a frame.


### 4.2. Experiment Results

Then we compare heuristic method with [21] on the experimental results of these two methods by three goals. The three goals are the ratio of average minimum satisfaction, average QoS satisfaction ratio, and average throughput.When the number of SSs is increasing in Figure8(a), it will lead to insufficient resources to allocate for all SSs then make min satisfaction ratio decrease. Our method allocates the resources to the proposed QoS requirements of SS at first priority and does the max-min fair allocation scheduling on the remaining resources. We find that the method of [21] is better than our method in terms of average min satisfaction ratio.Average min satisfaction ratio comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RSWhen the field changed to 3000 × 3000, then 16 RSs are placed for experiment, and the number of SSs increased from 10 to 100. We can find that the number of SSs increased and the number of hops increased in Figure8(b), then the overall average min satisfaction ratio will decline obviously.In Figure9, our heuristic algorithm will be higher than the method of [21] when comparing with average QoS satisfaction ratio. In order to arrange the QoS requirements in increasing order and allocate resources in increasing order, our heuristic algorithm is better than [21] in terms of QoS satisfaction ratio.Average QoS satisfaction ratio comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RSFrom Figure10, we can find that the average throughput of the two methods is almost equal. When the number of hops increase, the average throughput of two methods is also almost equal.Average network throughput comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RS


## 4.1. Environmental Setup

For experimental environment setting, SS transmission range and interference range are set 1000 and 1000; RS and the BS transmission range and interference range are set 1000 and 2000. BS was deployed at the center of the field. Multihop shortest path routing was adopted to obtain the network topology. SS is distributed in the field by random, each data packet requirement and QoS requirement of SS are set randomly among 2 to 8, and the QoS requirements of each SS must be less than or equal to the data packet requirement.In the beginning, we use our heuristic algorithm and scheduling method of [21] in 1500 × 1500 square units and deployed 4 RSs to compare with three goals. These three goals are minimum satisfaction ratio, QoS satisfaction ratio, and throughput. For OFDMA setting, the number of time slots and subchannels are 12 and 5 in a frame. Then, we consider another large scale network which has 3000 × 3000 square units and deploy 16 RSs. For OFDMA setting, time-slots and subchannels number are 48 and 5 in a frame.


## 4.2. Experiment Results

Then we compare heuristic method with [21] on the experimental results of these two methods by three goals. The three goals are the ratio of average minimum satisfaction, average QoS satisfaction ratio, and average throughput.When the number of SSs is increasing in Figure8(a), it will lead to insufficient resources to allocate for all SSs then make min satisfaction ratio decrease. Our method allocates the resources to the proposed QoS requirements of SS at first priority and does the max-min fair allocation scheduling on the remaining resources. We find that the method of [21] is better than our method in terms of average min satisfaction ratio.Average min satisfaction ratio comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RSWhen the field changed to 3000 × 3000, then 16 RSs are placed for experiment, and the number of SSs increased from 10 to 100. We can find that the number of SSs increased and the number of hops increased in Figure8(b), then the overall average min satisfaction ratio will decline obviously.In Figure9, our heuristic algorithm will be higher than the method of [21] when comparing with average QoS satisfaction ratio. In order to arrange the QoS requirements in increasing order and allocate resources in increasing order, our heuristic algorithm is better than [21] in terms of QoS satisfaction ratio.Average QoS satisfaction ratio comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RSFrom Figure10, we can find that the average throughput of the two methods is almost equal. When the number of hops increase, the average throughput of two methods is also almost equal.Average network throughput comparison.
(a)
Field: 1500 × 1500, 4 RS
(b)
Field: 3000 × 3000, 16 RS


## 5. Conclusion

In this paper, we study the multihop fairness scheduling problem with QoS control for enhancing throughput and guaranteeing QoS in WiMAX mesh networks. For allocating resource to multiple SSs, fairness is a key concern. The notion of max-min fairness is applied as our metric to define the QoS-based max-min fair scheduling problem for maximizing the minimum satisfaction ratio of each SS. We formulate an integer linear programming (ILP) model to provide an optimal solution on small-scale networks. Although the ILP solution can be used to obtain optimal solutions for small-scale network, it has high operation time and space consumption for large-scale networks.Therefore, in the paper, several heuristic scheduling algorithms are proposed to maximize both the minimum satisfaction ratio and the QoS satisfaction ratio based on Orthogonal Frequency-Division Multiple Access (OFDMA) model in the networks. The strategy of proposed heuristic algorithm is smallest total bandwidth requirement first and then applying spectral reuse scheme to assign resource. After QoS of all SSs is guaranteed, the max-min fair scheduling scheme is used to enhance the overall throughput and satisfaction ratio. Experimental results show that our method is better than previous work in terms of QoS satisfaction ratio and throughput.



---

*Source: 293962-2013-12-04.xml*