Advanced Wireless Networks - 4G Technologies

828 QUALITY-OF-SERVICE MANAGEMENT

particular connection in accordance with the channel quality. It will use the low service rate when an MS is within a high interference (high-IF) region to reduce bandwidth waste due to retransmissions, and use the high service rate when the MS is within a low interference (low-IF) region to fulfill the QoS requirements (e.g. delay bound and loss ratio) of the MS. The high and low service rates are both determined at connection setup time. Thus, the complexity of scheduling algorithm in wireless networks can be reduced.

21.3.1 DSMC functional blocks

An MS issues a connection request to the CAC controller by specifying its QoS requirements (De,k , Rp , Rm ), its priority level e, as well as the number of blocks m to be transmitted. De,k is the delay bound required for the requested session k with a priority of e on air interface, Um . Rp and Rm , respectively, denote the peak and the minimum data rates requested by the session k. In other words, the MS requests that m blocks of the session k should be scheduled in a queue of priority level e, and transmitted at a minimum rate higher than Rm or a peak rate not higher than Rp before the delay bound De,k is reached. The minimum data rate Rm is used as the low service rate when the MS is within a high interference region. On the other side, the peak data rate Rp is not taken for granted as the high service rate when the MS is within a low interference region. Instead, the high service rate is determined by a simple calculation performed by the service rate (SR) calculator inside the radio resource manager. The SR calculator determines the admissible peak data rate (high service rate) Rp that can be supported by the BSS according to the delay bound De,k , and the minimum data rate Rm under a hypothetical interference model of the MS.

As in many examples throughout the book, the interference model is based on a twostate Markov chain with transition probabilities α and β. These parameters α and β can be collected from a user behavior profile and can be updated dynamically. After receiving the Rp from the SR calculator, the CAC controller can optionally accept, reject or renegotiate with the MS. If the connection request is accepted, the CAC controller stores the parameters (Rp, Rm , m, e) to a parameter database. The rate selector can then select and send the current data rate R to the CCU (channel codec unit) associated with the MS according to the interference level measured by the interference monitor.

The DSMC scheduling architecture can be situated in a BSS of the GPRS networks and applied to either uplink or downlink transmission. The system will adopt a certain number of priority levels. As an example, in GPRS, block transmission is classified into five scheduling priority levels, including four data priority levels and a signal priority level, which is the highest priority level [47]. The DSMC scheduling architecture follows the specification but includes a new data priority level for the retransmission blocks. The DSMC scheduling architecture [45] consists of five scheduling servers for data block transmission, one server for each priority level. Each server is responsible for scheduling data blocks transmitting through a single packet data channel (PDCH). The highest priority level, P1, is for the retransmission blocks and the lowest priority level, P5, is for the best-effort data blocks. Both P1 and P5 schedule data blocks in a first-come-first-served order. However, the scheduling servers of priority levels P2–P4 adopt the SCFQ scheduling algorithm in scheduling data blocks of QoS specific connections. In other words, multiple queues may exist in each priority of P2–P4. The queues with the same priority will be served in accordance with the SCFQ scheduling algorithm, to be explained in below.

The block requests of a particular priority can not be served until all the blocks of the higher priority have been served. The transmission of a block is nonpreemptive.

The SCFQ scheduling algorithm is basically a packet-based general processor sharing scheme [48, 49] without the complex virtual clock tracking mechanism. The elimination of the virtual clock tracking mechanism makes SCFQ easier to implement on a high-speed network. In SCFQ, an arrival block request is tagged with a service finish time (FT) before it is placed in a queue. The service FT tag of a block request is computed from the service time and the service starting time of the block as

FT = block length + max(FT of the tail block, FT of the serving block)

The service starting time of the block can be the FT of the tail block of the queue if the queue is nonempty, or it is the FT of the serving block. The block requests among the heads of the queues will be picked up to be served one by one in accordance with the increasing order of FT tags, and in a round-robin fashion if more than two heading blocks have the same FT tags.

21.3.2 Calculating the high service rate

In order to determine the service rate, we need to first obtain the total delay of a block. The total delay depends on the service discipline and the input traffic. Owing to the bursty nature of multimedia traffic streams, a leaky-bucket regulator, as discussed in Chapter 8, is assumed at the network interface of the sender site to regulate the block request flow of each session.

In the DSMC scheduling scheme, a block of a connection will experience queueing delay, block transmission delay, and retransmission delay. A block at the head of a queue (henceforth referred to as a ‘heading block’) may experience a priority delay, which, in turn, consists of an interpriority delay caused by all block transmissions in the higher priority levels and an intrapriority delay resulted from the SCFQ scheduling.

Each preceding block of the newly arrived block will experience a priority delay and a block transmission delay when the preceding block becomes a heading block. In addition, the newly arrived block will experience an intrapriority delay when it becomes the heading block of the queue itself. Hence, the queueing delay of a block is, thus, the summation that the priority delay and the block transmission delay experienced by all preceding blocks, plus the intrapriority delay experienced by the block. In analytical modeling the following notation will be used:

sj, session j

L, block length (b);

Phibe, block error probability when the block is transmitting within a high interference region;

Plibe, block error probability when the block is transmitting within a low-interference region;

Phi, stationary probability that the MS is within a high-interference region;

Pli, stationary probability that the MS is within a low-interference region;

where σg,g is the leaky-bucket size and ρg, j is the token arrival rate for the session j of the priority g. Therefore, from the above leaky-bucket constraint, we can derive the following inequality:

Since the retransmission of data blocks has the highest priority and there is only one retransmission queue, we can denote the arrival traffic to the retransmission queue during the period (t1, t2) as A1,1[t1, t2]. The retransmission traffic is the aggregated traffic of the retransmission of all sessions. By observing the system over a substantially long period of time, we can find that A1,1[t1, t2] also conforms to the leaky-bucket constraint, and we rewrite the above inequality Equation (21.1) as

Finally, if Ci is the link capacity of the radio band (channel) i, by applying the inequality Equation (21.13) we have

From the above inequality, we calculate the maximum value of te.

The intrapriority delay is delay contributed from the SCFQ scheduling delay. It is the delay during which a heading block of a session waits for the heading blocks of some other sessions with the same priority to be served. Following the results presented by

832 QUALITY-OF-SERVICE MANAGEMENT

Golestani [51], we can derive the maximum intrapriority delay of the heading block of a session k with priority e as (|κe| − 1) · (L/Ci ), where Ci represents the capacity (b/s) of link (band) i, κe represents the set of backlog sessions for priority e, and |κe| represents the number of backlog sessions in the priority e.

21.3.3 Heading-block delay

A heading block will encounter an intrapriority delay, an interpriority delay, and a block transmission delay of its own. The heading-block delay, denoted HD, for an MS depends on the transmission rates and can be derived as

where (re,k )li and (re,k )hi are the service rate (b/s) of session k of priority e, i.e. the high and low service rate, within low-IF region and high-IF region, respectively. The item on the further right-hand side in each of the above equations represents the transmission delay of the heading block of the session k with the priority e. Since te is likely to be short under the control of the leaky-bucket regulator, HD is relatively small compared with the mean duration that an MS will stay in an interference region. Therefore, it was assumed that the interference condition will not change during a heading-block delay.

The queueing delay of a data block is the time during which the block waits until the block is selected for transmission. Clearly, a data block newly arrived in a queue cannot be served by the corresponding SCFQ server until all the proceeding data blocks in the same queue have been served. Therefore, the queueing delay of a data block includes the time that the block waits for it to become a heading block itself, plus the interpriority and intrapriority delays that the block encounters when it becomes a heading block.

If be,k represent the mean queue length of a session k with a priority e then from Little’s result, from Chapter 6, the mean queue length encountered by a newly arrived data block is equal to the block arrival rate multiplied by the mean heading-block delay time. Parameter be,k is given as

Now, the mean queueing delay w¯ e,k for the session k with a priority e can be calculated as

21.3.4 Interference model

We assume that the general interference model is an interrupted poisson process with transition probabilities of α and β. Hence, the duration that an MS is within the lowregion

or the high-interferece region can be represented, respectively, by an exponential distribution 1 − e−α·t , denoted L(t), or 1 − e−β·t , denoted H (t).

The interference state in which a block is served is determined by the starting state and the waiting time of the block. Therefore, we use an alternating renewal process to calculate

834 QUALITY-OF-SERVICE MANAGEMENT

21.3.6 High service rate of a session

By summing up the normal delay, Equation (21.22), and the retransmission delay, Equation (21.23), of a newly arrived block, the SR calculator can calculate the total delay (TDe,k ) for a newly arrived block in a session k with a priority e. For simplicity it is assumed that the low service rate of a session when the MS is within a high-IF region is a predefined value. The value of this low service rate can be chosen by a user application in accordance with the required characteristics of the media stream used in the application. For example, the low service rate can be assigned as the minimum tolerable decoding rate of a Motion Pictures Expert Group (MPEG) video stream.

If we assume that a session k with a priority e has a QoS specification for m block transmissions with air-interface delay bound De,k , then the SR calculator can calculate the high service rate of the session k with a priority e under the constraint of the inequality

TDe,k ≤ De,k /m.

21.3.6.1 Performance example

The three algorithms are compared by simulation with the same parameters as in Yang et al. [45]. The results are shown in Figure 21.8.

21.4 QoS IN OFDMA-BASED BROADBAND WIRELESS ACCESS SYSTEMS

Vector orthogonal frequency division multiplexing (VOFDM) is considered as a base for BWA systems by the Broadband Wireless Internet Forum (BWIF) [1]. The BWA system is used with existing wireless LAN technologies such as IEEE802.11 (a, b) and IEEE 802.16 Group aims to unify the BWA solutions [56]. 802.16 Group issued standards in the 10–66 GHz bands and IEEE802.16a Group was formed to develop standards to operate in the 2–11 GHz bands in which channel impairments, multipath fading and path loss become more significant with the increase in the number of subscribers.

System performance at high transmission rates depends on the ability of BWA system to provide efficient and flexible resource allocation. Recent studies [55,57] on resource allocation demonstrate that significant performance gains can be obtained if frequency hopping and adaptive modulation are used in subcarrier allocation, assuming knowledge of the channel gain in the transmitter.

The resource allocation problem has been considered in many studies. Almost all of them define the problem as a real-time resource allocation problem in which QoS requirements are fixed by the application. QoS requirement is defined as achieving a specified data transmission rate and BER of each user in each transmission. In this regard, the problem differs from the water-feeling schemes wherein the aim is to achieve Shannon capacity under the power constraint [57].

Therefore, in this section we consider the problem where K users are involved in the OFDMA system to share N subcarriers. Each user allocates nonoverlapping set of subcarriers Sk where the number of subcarriers per user is J (k). In the following, Xk (l) represents the lth subcarrier of the FFT block belonging to the kth user. Xk (l) is obtained by coding the assigned c bits with the corresponding modulation scheme. In the downlink the Xk (l) are multiplexed to form the OFDM symbol of length (N + L) with the appended guard

where Hj (n) := kth user.

The allocation module of the transmitter assigns subcarriers to each user according to some QoS criteria. QoS metrics in the system are rate and BER. Each user’s bit stream is transmitted using the assigned subcarriers and adaptively modulated for the number of bits assigned to the subcarrier. The power level of the modulation is adjusted to meet QoS for given fading of the channel. The transmission power for the AWGN channel can be predicted. In addition the channel gain of subcarrier n to the corresponding user k should be known. The channel gain of the subcarrier is defined as αk,n = Hk (n) PLk ,where PL is the

path loss, defined by PLk = PL (do) + 10α log10 (dk /do) + Xσ . Parameter do is the reference distance, dk is the distance between transmitter and receiver, α is the path loss component

and Xσ is a Gaussian random variable for shadowing with a standard deviation σ [58, 59].

With the known channel information, the objective of resource allocation problem can be defined as maximizing the throughput subject to a given total power constraint regarding the user’s QoS requirements.

If γk,n is the indicator of allocating the nth subcarrier to the kth user, the trans-

for reliable reception of ck,n bits per symbol. Therefore, the resource allocation problem with an imposed power constraint can be formulated as

The limit on the total transmission power is expressed as Pmax for all n {1, . . . , N }, k {1, . . . , K } and ck,n {1, . . . , M}. If there is no power constraint, Equation (21.27) is changed in order to minimize PT subject to allocating Rk bits for all k. In other words problem is to find the values of the γk,n and the corresponding ck,n while minimizing PT .

The optimal solution in a multiuser environment with multiple modulation techniques is complicated since it needs to pick the subcarriers in balance. The problem can be classified according to each set of bits assigned to a subcarrier. For a user k, fk (ck,n ) { fk (1, BERk ), . . . , fk (M, BERk )}and M times [K N ] power matrices { Pc} can be constructed for each c. For a constant c, { f (c)} can be computed and the transmission power requirement can be found. The dimension of the indicator function is incremented and represented now by γk,n,c and defined as

The above problem can be solved with integer programming (IP). We refer to the IP approach as the optimal solution to the resource allocation problem. There are K · N · M indicator

variables and M power matrices where the entries of each matrix for a given c can be found from

Although the optimal solution gives the exact results, from an implementation point of view, it is too complex. This leads to searching suboptimal solutions that are fast and close to the optimal solution. Suboptimal solutions, in most attempts to simplify the resource allocation, decompose the problem into two procedures, a subcarrier allocation with fixed modulation, and bit loading. Subcarrier allocation with fixed modulation deals with one Pc matrix with fixed c and then, by using bit loading scheme, the number of bits is incremented.

by decrementing Rk properly. Then the solution to this problem can be solved with Linear Programming or Hungarian problem.

Linear programming

For simplicity, we briefly restate the problem description,

After linear programming, the [K · N ] allocation matrix has entries ranging between 0 and

1. The entries are converted to integers by selecting the highest ¯ k nonzero values from

R N

columns for each k and assigning them to the kth user.

Hungarian algorithm

The problem described above can also be solved by an assignment method such as the Hungarian algorithm [58]. The Hungarian algorithm works with square matrices. Entries