IEEE Copyright. This is a post-print author's version. Final published version is available at: https://ieeexplore.ieee.org/ document/4699829.
Common Radio Resource Management Policy for Multimedia Traffic in Beyond 3G Heterogeneous Wireless Systems M.Carmen Lucas-Estañ(1), Javier Gozalvez(1), Joaquin Sanchez-Soriano(2) (1)
Ubiquitous Wireless Communications Research (Uwicore) Laboratory University Miguel Hernandez Elche, Spain [email protected]
Abstract—Beyond 3G wireless systems will be composed of a variety of Radio Access Technologies (RATs) with different, but also complementary, performance and technical characteristics. To exploit such diversity while guaranteeing the interoperability and efficient management of the different RATs, common radio resource management (CRRM) techniques need to be defined. This work proposes and evaluates a CRRM policy that simultaneously assigns to each user an adequate combination of RAT and number of radio resources within such RAT to guarantee its QoS requirements. The proposed CRRM technique is based on linear objective functions and programming tools. Keywords-component; Common Radio Resource Management, Heterogeneous wireless systems, multimedia traffic, Beyond 3G.
I. INTRODUCTION There is a wide consensus in the research community that Beyond 3G wireless systems will consist of heterogeneous mobile and wireless Radio Access Technologies (RATs) physically coexisting, but with distinct performance and technical characteristics. Ensuring their interoperability would allow an efficient use of their common radio resources to guarantee the user required Quality of Service (QoS) levels and the maximum systems’ revenue. To achieve these objectives, a key feature of heterogeneous Beyond 3G wireless systems will be the definition of adequate Common Radio Resource Management (CRRM) policies. CRRM techniques are aimed at deciding the RAT over which to convey a user transmission (RAT selection), and the number of resources from the selected RAT (intra-RAT RRM) that the transmission would require to satisfy the QoS requirements. Several studies separately tackle the RAT selection and the intra-RAT RRM dilemmas. For example, [1] and [2] propose intra-RAT RRM policies based on utility functions and economic laws. While the authors in [1] suggest applying auctions principles to maximize the operator’s benefit, [2] proposes the use of bankruptcy-based resource allocation policies to guarantee user fairness and avoid channel access stagnation under heterogeneous traffic environments. In terms of RAT selection techniques, [3] proposes a general framework for their definition, and some specific examples based on pre-established service/RAT assignments. Additional RAT selection principles based on signal strength and instantaneous loads are proposed and evaluated in [4].
This work has been supported by the Ministry of Education and Science (Spain) and FEDER funds under the projects TEC2005-08211-C02-02 and MTM2005-09184-C02-02.
(2)
Operations Research Center
Initial proposals to jointly address the RAT selection and intra-RAT RRM dilemmas have been recently proposed. For example, [5] proposes a CRRM algorithm based on neural networks and fuzzy logic that simultaneously determines the most appropriate RAT and bit rate allocation, considering, among other factors, the user QoS constraints. While [5] determines the necessary bit rate at the assigned RAT, it does not tackle the problem of intra-RAT radio resources assignment. In this context, this work proposes and evaluates a CRRM policy that simultaneously assigns to each user an adequate combination of RAT and number of radio resources within such RAT to guarantee the user/service QoS requirements. The proposed algorithm is based on linear programming optimization techniques, which have shown significant benefits in other areas, and have been recently applied for the first time to CRRM in [6] to address the RAT selection dilemma. The work reported in [6] proposes a joint call admission control scheme for minimizing call blocking probability in heterogeneous wireless networks. In this context, [6] used linear programming optimization techniques to determine the optimal splitting of arriving calls among available RATs. The objectives of the work reported in [6] significantly differ to those of this paper, where a CRRM policy jointly addressing the RAT selection and intra-RAT RRM dilemmas is proposed. II. UTILITY FUNCTIONS The operation of the proposed RAT and resource assignment policy is based on service-dependent utility functions. These utility functions define the user-perceived QoS for a varying number of assigned radio resources per available RAT. As demonstrated in [2], properly chosen utility functions are capable to adequately reflect the user-perceived QoS levels. In addition, these utility functions can allow for a dynamic and efficient policy-dependent resource assignment that achieves its QoS objectives independently of the system load. Given the length restrictions, this paper will not describe in detail the process followed to establish the utility functions, but will rather present its main characteristics. This work considers an heterogeneous multimedia traffic scenario with email, web and real-time H.263 video (with different bit rates) users. The utility values (Fig. 1) have been established considering minimum, medium and maximum QoS
requirements (Table I). While web and email utility values refer to achievable throughputs, the video utility figure corresponds to the percentage of video frames transmitted before the next video frame is to be transmitted. This video utility representation has been chosen to define utility functions independent of the H.263 video bit rates. For all services, utility values equal to zero are assigned if the minimum QoS requirement cannot be achieved. Although the use of utility values to estimate the user satisfaction is a subjective process, it is important to note that the authors demonstrated in [2] that the utility functions reported in Fig. 1 adequately reflect the user needs, validating the procedure employed to define them. Once the utility functions are established, it is then necessary to define the relation between radio resources and utility values. Since this work focuses on heterogeneous wireless systems (GPRS, EDGE and HSDPA), such relation would need to consider the selected RAT and the number of radio resources within such RAT that are been assigned. GPRS and EDGE systems have been implemented with a single carrier (i.e. eight timeslots) each. For HSDPA, this work considers the transmission modes defined in the CQI (Channel Quality Indicator) mapping table for User Equipment category 10, which does not consider transmission modes employing 6, 9, 11, 13 and 14 codes, and defines a total of 30 different transmission modes [7]; each transmission mode corresponds to a combination of codes, modulation and coding schemes. To relate the utility functions defined in Fig. 1 to the various possible RAT and resources combination, a transmission rate is selected per radio resource in each RAT. For real-time H.263 video users, an additional step is necessary. A cumulative distribution function (cdf) of the throughput needed to transmit each video frame before the next video frame is to be transmitted is derived following the H.263 video model proposed in [8]. With this cdf, the percentage of TABLE I. USER QOS LEVELS
1
1 0.9
0.8
0.8
0.7
0.7
0.6 0.5 0.4 0.3
H263 video service
0.6 0.5 0.4
0.2
email service
0.1 0
Max. QoS 128kbps 64kbps 0.95 100% 1
0.3 WWW service
0.2
0
100 200 Throughput (kbps)
0.1 300
It is important to note that all emulated RATs implement Adaptive Modulation and Coding (AMC), which can then result in varying, and difficult to predict, transmission rates for the same number of radio resources. In this scenario, it has been chosen to consider transmission modes providing a balance between data rates and error correction. In particular, average data rates of 13.4 kbps (corresponding to the coding scheme CS2) and 22.4kbps (corresponding to the modulation and coding scheme MCS5) have been selected for a timeslot in GPRS and EDGE, respectively. In HSDPA, various transmission modes can be defined per assigned code. To achieve the sought data rate/error correction balance, the selected transmission rate per assigned HSDPA code corresponds to that achieved by the ‘intermediate’ transmission mode out of all possible modes for a given number of HSDPA codes. Such transmission modes would correspond to CQI value 3 for 1 HSDPA code, and CQI 8 for 2 HSDPA codes in the example shown in Table II. Once an average data rate is established per radio resource for all possible RATs, it is then possible to represent the utility values that can be achieved for each RAT and number of resources being assigned. Table III shows an example for realtime 64 kbps H.263 video users with the RAT/resources combination shown in increasing throughput order. The resources/RAT combination is denoted as xY, corresponding to x radio resources (timeslots or codes) from RAT Y (GPRS is represented as G, EDGE as E, and HSDPA as H). It is interesting to note that certain RAT/resources combinations cannot achieve utility values greater than zero, and that from a certain RAT/resources combination, the utility value does not increase despite raising transmission throughputs. TABLE II. EXTRACT OF CQI MAPPING TABLE FOR UE CATEGORY 10
Mean QoS 64kbps 32kbps 0.95/2 95% 0.95/2
0.9
Utility value
Utility value
WWW Email Established utility values H.263 video Established utility values
Min. QoS 32kbps 16kbps 0.95/4 75% 0.95/4
video frames reported in Fig. 1 can be related to the corresponding necessary throughputs for the various video bit rates considered in this work (16, 64, 128, 256 and 512kbps).
0 60 70 80 90 100 Percentage of correctly transmitted video frames
Figure 1. Utility functions per traffic service.
CQI value 1 2 3 4 5
Data Rate (kbps) 68.5 86.5 116.5 158.5 188.5
Codes
CQI value
1 1 1 1 1
6 7 8 9
Data Rate (kbps) 230.5 325 396 465.5
Codes 1 2 2 2
TABLE III. 64KBPS VIDEO UTILITY VALUES Data Utility Res./ rate value RAT (kbps) 1G 13.4 0.0000 1E 22.4 0.0000 2G 26.8 0.0000 3G 40.2 0.0000 2E 44.8 0.0000 4G 53.6 0.0000 5G 67 0.0000 3E 67.2 0.0000 6G 80.4 0.0000
Res./ RAT 4E 7G 8G 5E 1H 6E 7E 8E 2H
Data rate (kbps) 89.6 93.8 107.2 112 116.5 134.4 156.8 179.2 396
Utility value
Res./ RAT
0.2983 0.3127 0.3532 0.3654 0.3775 0.4350 0.9338 0.9819 1.0000
3H 4H 5H 7H 8H 10H 12H 15H
Data Utility rate value (kbps) 741 1.0000 1139.5 1.0000 2332 1.0000 4859.5 1.0000 5709 1.0000 7205.5 1.0000 8618.5 1.0000 11685 1.0000
III. COMMON RADIO RESOURCE ASSIGNMENT PROPOSAL This work is aimed at defining a CRRM policy that maximizes the channel’s efficiency while guaranteeing the adequate user-perceived QoS levels based on the established operator’s service policy. As it has been previously explained, the proposed policy jointly addresses the RAT selection and the decision on the number of radio resources within the selected RAT that need to be assigned to each user. However, it is important to note that this work does not yet consider the possibility that one user is simultaneously assigned resources from various RATs. The proposed policy is based on the previously established utility functions and linear programming optimization tools. While it is evaluated under a fairness user policy with service priorisation when radio resources are limited under high system loads, the proposed CRRM mechanism could be easily extended to other operator’s strategies.
with uj defined in (4). In (4), urj(sr) represents the utility value obtained by user j when assigned s radio resources (codes or timeslots) of RAT r (r is equal to 0, 1 or 2 for GPRS, EDGE and HSDPA respectively), and s ∈ [1,cr] with cr corresponding to the maximum number of radio resources available at each RAT. y rj , s is a binary variable equal to one if user j is assigned s radio resources of RAT r, and equal to 0 if not. The proposed CRRM policy focuses then on deciding for each user which y rj , s variable is equal to one, considering that only
y rj , s variables achieving an utility value greater than zero are allowed. Given that only one y rj , s variable can be equal to one for each user, the following expression applies:
∑ ln u = ∑ ln ∑∑ u (s )⋅ y r j
j
A. CRRM objective function As previously explained, each service type has different resource requirements to achieve similar QoS levels. Such requirements have been defined by means of the utility functions described in Section II, where it was shown that similar user satisfaction levels (represented here by means of utility values) can be achieved through various resources/RAT combinations. The proposed CRRM policy exploits such flexibility to decide on the optimum resources/RAT assignments following a user fairness approach. In fact, the proposed technique aims at providing similar, and highest possible, user satisfaction levels for all service types. Only when the number of available radio resources is lower than the demand will the implemented policy priorise certain traffic classes. In this context, the proposed CRRM objective function can be denoted as follows: max ∏ u j , j ∈ [0 , N − 1]
(1)
j
which is equivalent to: max ln ∏ u j , j
j ∈ [0 , N − 1]
(2)
where uj represents the utility value assigned to user j in a combined RAT/resources distribution round, and N corresponds to the total system user load. Under equal service and operative constraints, (1) or (2) is achieved when utility values are equally distributed among users. The established CRRM objective function then can be expressed as: ln ∏ u j = ∑ ln u j j
( )
u j = ∑ ∑ u rj s r ⋅ y rj , s r s
(3)
j
(4)
j
j
r
r
s
r ,s j
( ( )
= ∑∑ ∑ ln u rj s r ⋅ y rj , s j
r
s
) (5)
If we assume that all users must have a variable y rj , s equal to one, (5) becomes:
( ( )
)
( ( ))
r r r ,s r r r,s ∑ ∑ ∑ ln u j s ⋅ y j = ∑ ∑ ∑ ln u j s ⋅ y j j r s
j r s
(6)
Our CRRM objective function can then be expressed as:
( ( ))
max ∑ ∑ ∑ ln u rj s r ⋅ y rj , s j r s
(7)
B. CRRM service constraints Given that (7) is a linear equation, it can then be resolved using linear programming tools. However, before describing the linear programming resolution, it is important to complete the problem statement with some service-specific constraints. To obtain a linear objective function, it has been assumed that each user will obtain a y rj , s variable equal to one. However, this condition might not be feasible under high system loads where the number of radio resources is lower than the user demands. In this case, the number of users requesting resources will be reduced so that: r ,s ∑ ∑ y j = 1, ∀j
(8)
r r,s ∑ ∑ s ⋅ y j ≤ c r , ∀r
(9)
r s
j sr
Whenever a user requests resources for a new transmission or a given transmission ends, the developed CRRM policy is applied. In this case, only real-time video active users that were assigned resources in the previous CRRM distribution round maintain those corresponding to the minimum QoS level and compete for additional ones, which can be expressed as:
(10)
r ,s ∑ ∑ E s r ⋅ y j ≥ E min , ∀j h 263 r sr
where Es r represents the RAT/resources combination index in utility tables (e.g. Table III), corresponding to the assignment of s radio resources for RAT r. Similarly, Emin represents the index of the RAT/resources combination achieving the minimum QoS level. In case the available resources do not allow achieving equal utility values for all users, users are served based on the following service priorisation: real-time H.263 video (higher priority), web, and email. Within the real-time video service class, users with higher video bit rates are served first. If the lowest priority user (m) is a video user that obtained radio resources in the previous CRRM distribution round, the condition established in (10) comes first and the video user would be assigned the smin radio resources from RAT rmin necessary to achieve the minimum QoS level defined by Emin. When such level is achieved, the lowest priority user will not be assigned additional resources until the highest priority user (k) surpasses its utility value ( umr (sm ) ). This condition can be summarized in (11): min
min
(
)
( )
r r r r ,s r,s ∑ ∑ u mmin s mmin ⋅ y k + ∑ ∑ u k s ⋅ y k ra sa
rb sb
( )
≥ ∑ ∑ u mr s r ⋅ y mr ,s r s
(11)
This condition is only applied when the priority of user k is higher than that of user m, where (ra,sa) represent the RAT/resources assignments that verify u mrmin (smmin ) − u kra (sa ) > 0
(
and (rb,sb) the assignments that verify umrmin sm
) − ukr (sb ) ≤ 0 . b
min
It has been previously explained that to obtain a linear objective function, it is necessary that all users participating in the CRRM resources distribution round obtain a y rj ,s variable equal to one. If this is not possible due to resources shortage, it was mentioned that the number of users requesting resources will be reduced to satisfy all imposed constraints. Following (11), it can be established that if present users cannot even obtain their minimum QoS demand, the linear objective function does not have a solution, and users with the lowest priority are eliminated from the CRRM distribution round until such solution can be achieved.
C. CRRM linear programming resolution Linear programming tools have been shown to represent an attractive solution in optimization problems looking at identifying the most suitable solution following a previously established objective function. In this context, this work proposes its use to address the CRRM problem in heterogeneous wireless systems, where policies are needed to determine which RAT, and with how many radio resources, is assigned to each user. The previous section has mathematically expressed the problem statement with all its system and service constraints (III.B.), and has derived a linear objective function to solve,
with a binary integer unknown variable y rj ,s . In operations research, this type of problems is referred to as Binary Integer Programming (BIP) [9], and can be solved using different approaches. One of the most popular approaches due to its performance and computational properties, and the one used in this work, is the Branch and Bound method [9]. This technique solves an ordered sequence of reduced linear programming problems until an optimum solution is achieved. Such reduced linear programming problems are obtained when the condition that the unknown variable must be an integer variable is relaxed and real variables are allowed. To solve such reduced linear programming problems, this work proposes to use the simplex method [9], which is regularly employed in problems, with a large number of variables, which require computationally efficient solutions. The simplex method is an algebraic procedure that makes use of the fact that the system and user constraints present in the problem statement reduce the range of possible solutions to a limited spatial region. The interested reader is referred to [9] for additional details on the simplex method and its operation. IV.
CRRM PERFORMANCE
A. Simulation conditions The performance of the proposed CRRM technique has been evaluated in Matlab. The implemented simulator is not aimed at accurately modeling radio transmissions, but at measuring the efficiency of the resource distribution proposals and optimizing them according to each RAT operational characteristics and specific system constraints. The implemented platform emulates the distribution of GPRS, EDGE and HSDPA resources among real-time H.263 video, email and web users for various system loads. In terms of service distribution, email, web and real-time video transmissions represent each one third of the total load. Within the real-time H.263 video system load, users are equally distributed among three different bit rates selected from the emulated ones: 16, 64, 128, 256 and 512kbps. A single cell with same GPRS, EDGE and HSDPA coverage is modelled. B. Results The proposed CRRM policy has been evaluated under two different multimedia traffic scenarios. In the first one (E1), web, email and real-time H.263 video transmissions at 16, 64 and 128kbps bit rates are emulated. The second evaluation scenario (E2) also considers web and email transmissions, but real-time H.263 video applications operate at 64, 256 and 512kbps bit rates. For both scenarios, cell loads of 20 and 30 users have been simulated following the traffic distributions reported in Section IV.A Fig. 2 depicts the achieved utility values for E1 under a 20 and 30 users cell load, respectively. The figure shows the percentage of users per service class that achieved the utility values corresponding to the minimum, medium and maximum QoS levels defined in II. To understand why maximum QoS levels cannot be achieved for all service classes, it is important to note the limited available resources per RAT, and the fact that several service classes required more than one radio resource to obtain a utility value greater than zero. In this context, Fig. 2 shows that the implemented CRRM policy achieves its various objectives; for example, the fact that under
resource shortage scenarios such as the ones simulated, the service priorities criteria defined in (11) is correctly applied. In this respect, it should be emphasized that the discrete nature of the utility functions preclude the possibility to achieve identical utility levels for all service types, and the traffic priorities previously defined need to be applied. It is also very important to note that the majority of services achieve their minimum QoS levels, and only when such levels are guaranteed, resources are additionally assigned to higher priority users. This does not always apply to the lowest priority services (i.e. email and web) due to the resource shortages, the service priorisation and the service continuity applied to video transmissions that were assigned resources in previous CRRM distribution rounds. Table IV shows, per service class, the selected RAT and the assigned number of radio resources within the selected RAT for the E1 scenario under the two emulated cell loads, and for the E2 scenario under a 20 users cell load. In this table, ‘0RS’ indicates a user has not been assigned any resource. The results depicted in Table IV show that when the cell load increases, email
www
Users (%)
32kbps video
64kbps video
50
0
min QoS
mean QoS
max QoS
E1 30 users cell load
100
Users (%)
16kbps video
E1 20 users cell load
100
50
0
min QoS
mean QoS
max QoS
Figure 2. Assigned utility values per service class.
the combined RAT/radio resources distribution is modified. In particular, the CRRM policy looks to satisfy a higher percentage of users with the highest possible QoS level, instead of satisfying a lower percentage of users with their higher QoS requirements. This approach results in that, as the load increases, the distribution better adjusts the assignments to the minimum and medium QoS requirements in order to provide the minimum QoS requirements for the higher possible percentage of users. If we look at the 64kbps video transmissions, Table IV shows that under a load of 20 users per cell in the E1 scenario, 76% of its transmissions have been assigned 2 HSDPA codes and the minimum resource assignment corresponds to 1H for 10.5% of the transmissions. According to Table III, 2H and 1H provided utility values of 1 and 0.38 for 64kbps video transmissions, which shows that all transmissions guarantee their minimum QoS requirements but when possible higher QoS levels are assigned. As the load increases to 30 users per cell, the lowest 64kbps resource assignment is 4E (just above the minimum QoS requirements) and the percentage of users with higher utility values decreases, highlighting the CRRM resource distribution adaptation with the traffic load. A similar trend to that observed when increasing the load is also experienced when increasing the service QoS requirements. In fact, a similar resources distribution is obtained when passing from the E1 scenario with a 20 users load to the E2 scenario with the same system load. The higher QoS requirements of video services under the E2 scenario force a new resources distribution that, for example, reduces the resources assignment (and its corresponding utility values) for the 64kbps video, web and email users; these services also increase their probability of not being assigned any radio resource due to the resource shortage caused by the higher minimum QoS requirements of higher bit rate video services.
TABLE IV. RADIO RESOURCE ASSIGNMENT PER SERVICE CLASS
www
16kbps video
64kbps video
128kbps video
E1 – 20 users Res. % 0RS 46.1 2G 4.9 3G 6.0 2E 24.4 4G 6.9 1H 10.3 0RS 8.5 2E 4.6 8G 1.4 1H 78.4 8E 1.7 2H 1.8 0RS 0.0 2G 9.1 3G 20.8 2E 15.0 1H 43.1 0RS 0.0 1H 10.5 7E 0.4 8E 12.7 2H 75.9
E1 – 30 users Res. % 0RS 96.3 1E 2.1 2G 0.9 3G 0.1 2E 0.2 1H 0.2 0RS 37.5 2E 7.8 4G 1.7 5G 2.2 8G 0.9 1H 45.6 0RS 3.2 2G 10.8 3G 27.4 2E 30.0 1H 17.1 0RS 0.0 4E 2.3 1H 16.8 8E 8.5 2H 67.0
0RS 2H 3H
0RS 2H 3H
0.0 52.0 48.0
0.0 55.8 44.2
www
64kbps video
256kbps video
512kbps video
E2 – 20 users Res. % 0RS 58.8 2G 7.0 3G 2.5 2E 16.9 4G 5.4 1H 7.9 0RS 17.4 3G 2.8 2E 8.4 4G 1.6 8G 2.6 1H 64.2 0RS 5.6 4E 4.1 1H 27.6 8E 11.1 2H 44.9 0RS 5.6 2H 9.0 3H 52.0 4H 6.6 5H 26.6 0RS 3.2 4H 14.3 5H 57.1 7H 15.1
REFERENCES [1]
[2]
[3]
[4]
[5]
[6]
[7] [8]
[9]
M. Dramatinos, G.G. Stamoulis, C. Coucoubetis, “Auction-based resource allocation in UMTS High Speed Downlink Packet Access (HSDPA)”, in Proc. of the Next Generation Internet Networks conference, 2005, pp. 434-441. M. C. Lucas-Estañ, J. Gozálvez, J. Sánchez-Soriano, “Multi-channel radio resource distribution policies in heterogeneous traffic scenarios”, in Proc. 66th IEEE VTC2007-Fall, pp. 1674-1678. J. Pérez-Romero, O. Sallent, R. Agustí, “Policy-based initial RAT selection algorithms in heterogeneous networks”, in Proc. of MWCN2005, pp. 1–5. O. Yilmaz, A. Furuskar, J. Pettersson, A. Simonsson, “Access selection in WCDMA and WLAN multi-access networks”, in Proc of IEEE 61st VTC2005-Spring, vol. 4, pp. 2220-2224. L. Giupponi, R. Agusti, J. Perez-Romero, O. Sallent, “A novel approach for joint radio resource management based on fuzzy neural methodology”, IEEE Transactions on Vehicular Technology, pp. 17891805, May 2008. O. E. Falowo, H. Anthony Chan, “Optimal joint radio resource management to improve connection-level QoS in next generation wireless networks”, in Proc. of IEEE RWS 2008, pp. 243-246. 3GPP, Technical Specification Group Radio Access Network; Physical layer procedures (FDD), 3GPP TS 22.214, version 7.3.0, 2006. O. Lázaro, D. Girma, J. Dunlop, “H.263 video traffic modelling for low bit rate wireless communications”, in Proc. IEEE PIMRC 2004, vol. 3, pp. 2124-2128. F. S. Hillier, G. J. Lieberman, Introduction to operations research, 7th edition, McGraw-Hill, 2001.