Manzoor Ahmed Khan
email: manzoor-ahmed.khan@dai-labor.de

Jie Lu

Muhammad Amir Mehmood

Utility-based Analytical Model for representing user QoE

Keywords: Utility function, NGMN, QoE, VoIP

Next Generation Mobile Networks (NGMNs) together with smart phones evolution have opened new opportunities to deliver mobile services, including voice, data and multimedia applications to the users. However this conflation has brought several challenges in terms of Quality of Experience -QoE of users. Mainly due to degradations with timevarying characteristics in the presense of link heterogeneity, varying packet loss and codec switching. In this paper we propose an analytical quality prediction model which predicts user QoE for conditions that are typically occurring in NGNMs such as network handovers, codec switching and different packet loss rates due to adverse wireless networking conditions. We augment our model with service price as another key factor in QoE representation. We validate quality prediction of our model with subjective tests. Our results show that the quality prediction by our model has correlation of r = 0.923 with subjective ratings.

Introduction

Wireless internet access has grown significantly over the last decade from, a barely sufficient bandwidth provided by GRPS and EDGE, to the medium sized UMTS/HSDPA, UMTS/HSPA+, WiFi, WiMax and towards the high speed envisaged by LTE. Also smart phones such as iphone and Android are equipped with multiple wireless network interfaces e.g. 3G UMTS or WiFi. This has given users an opportunity to be always connected to the Internet anywhere and anytime. Moreover, it has provided users a choice to select the best network according to their own preference driven by their network choice, quality acceptance and cost effectiveness [START_REF] Ganchev | Always best connected enabled 4g wireless world[END_REF].

While bandwidth offered by these technologies is increasing, the link layer properties are also exhibiting time-varying characteristics. These factors may force users to react according to the network conditions. For instance, due to adverse nature of wireless medium it is imperative to change speech bandwidth inorder to maintain a certain quality of service. This action sometimes results in changing of speech codec during the ongoing call i.e., codec changeover and/or change of network point of attachment i.e., network handover. The study of the these new conditions and modeling the impact on speech quality prediction for NGMN is the key focus of this work.

On one hand, the availability of these high-speed access technologies have encouraged the users to use Mobile VoIP while they are on the move, on the other hand the physical layer implementation of these wireless technologies have different impact on real time applications. For instance, HSDPA link exhibits more fluctuations than WiFi due to shared downlink. The primary reasons for this is base station scheduling which allocate resources only to the users having good wireless link conditions. WiFi is also interference limited technology and link transmission is greatly dependent on the simultaneous demand of the wireless channel resources. However WiFi as compared to HSDPA performs better in terms of throughput and latency. These differences in access technologies are the key factor of different quality of experience of users for different services. Due to this fact, network service providers which are offering superior quality VoIP services by employing wideband codecs sampled at 16kHz in their network require service adaptation to narrowband codec at 8kHz when facing adverse network conditions.

The usage of voice services over IP networks has grown significantly. Skype for instance dominates the market with its over 521 Million accounts and over 40 million active users that generate most amount of international traffic. Mobile VoIP is also becoming popular and it is being incorporated into the mobile phones using SIP protocol. This protocol allows exchange of SIP messages into the device and then RTP may be used to manage voice path. Mobile VoIP demands high-speed wireless communications such as WiFi, WiMax or HSDPA. Also these access networks open opportunities to deliver new services to the mobile users.

Mobile service adoption is clearly dependent on quality received by the users as users expect same quality of fixed phone while on roaming. Thus call quality monitoring is really crucial for NGMN service providers. The call quality monitoring may be based on network transmission metrics, but also on the evaluation of the transmitted audio signal arriving at the user end terminal. This information can be further mapped into the quality experienced by the end user. Real user perception measurement requires time-consuming and expensive subjective tests but also provide the ground truth and most accurate Mean Opinion Score (MOS), which express the mean quality score of a group of users according to ITU-T Rec. P.800 [START_REF]Methods of Subjective Determination of Transmission Quality[END_REF]. The test complexity limits the applicability of such a quality measurement. These limitations form the basis and serve as the driving force for an alternate approach of instrumental quality prediction.

The functional principle of quality prediction models can rely on evaluation of transmission parameters measured in networking layer e.g. E-model [START_REF]The E-model[END_REF], or on the analysis of the signal waveform measured at the output of the transmission system e.g. Perceptual evaluation of speech quality -PESQ [START_REF]Perceptual Evaluation of Speech Quality(PESQ): An Objective Method for End-to-End Speech Quality Assessment of Narrow-Band Telephone Networks and Speech Codecs[END_REF]. These approach allow to derive the quality index without performing subjective tests and is based on either parametric approach or signal-based approach. However, these models have been tested for only certain conditions related to fixed networks and their applicability for NGMN typical networking conditions are still limited. This underscore the stark need of another modeling approach which can capture NGMN effects along with external factors such as service price. Our model is premised on the fact that along with typical conditions in NGMN's e.g., network handovers, codec switchovers and packet loss, service price offered by a particular provider plays a major role in mobility management based on QoE.

In this paper, we present analytical quality prediction model based on the utility function of a user, that predicts quality for NGMN typical conditions.Our main contributions are as follows:

-Analytical representation of user satisfaction using utility function specifically concentrating on impact of handover and codec switchover on the user satisfaction for heterogeneous services. -Validating the estimated satisfaction values attained from the proposed utility function for different scenarios (by comparing the estimated satisfaction values of utility function to the values attained from the experimental work).

We structure rest of the paper as follows. In Section 2, we discuss related work, next in Section 3 we present user satisfaction function. We continue with discussion on satisfaction criteria in Section 4. In Section 5 we show our experimental methodology and we compare experimental and model results in Section 6. We conclude the paper in Section 7.

Related work

Speech quality assessment has been the subject of many researchers [START_REF] Raake | Speech Quality of VoIP: Assessment and Prediction[END_REF]. Various different models and their modifications have been proposed for signal based speech quality prediction model such as PESQ and WB-PESQ [6][7]. Similarly many efforts have been made in parametric based model such as ITU-T E-model [START_REF]The E-model[END_REF] and its various extensions. In the context of speech quality assessment when network handovers and codec switchover are prevalent, a comprehensive quality assessment study has been carried out by Möller et al. [START_REF] Moller | Speech quality while roaming in next generation networks[END_REF], which encompasses the changes in the user quality of experience for various different roaming scenarios. Their study highlight the fact that packet loss is the most dominant factor in NGMN conditions and network handover (only) has minimal impact compared to packet loss and codec switching. Another interesting fact from that study reveals that when packet loss is high, changing codecs does not impact quality much. However, when the packet loss is low, changing codec has high impact on the quality.

In another recent study by Mehmood et al. [START_REF] Mehmood | Understanding signal-based speech quality prediction in future mobile communications[END_REF] authors show that WB-PESQ model failed to predict quality under some NGMN conditions. It was shown with experimental evidence that WB-PESQ underestimates quality due to (i) wideband-narrowband speech codec switching, (ii) speech signal fading during codec switching, and (iii) talk-spurt internal time-shifting due to jitter buffer instabilities. This highlights the fact that current signal based models are still not tuned for NGMN typical conditions and needs enhancement. Similar studies of NGMN conditions carried by Blazej et.al. [START_REF] Lewcio | E-model supported switching between narrowband and wideband speech quality[END_REF] pointed out that the parametric model such as E-model was unable to predict the quality where narrowband and wideband codecs are present in a single call. Their suggested codec-switching impairment factor to E-model improved the correlation of the E-model prediction to auditory tests to r = 0.937. Chen et.al. [START_REF] Chen | Quantifying Skype user satisfaction[END_REF] have tried to find out user satisfaction index of voip user, however their work is limited to Skype user satisfaction only.

Utility theory, basically a concept from economics has been greatly used in wireless communication. [START_REF] Winkler | Decision modeling and rational choice: Ahp and utility theory[END_REF][START_REF] Ormond | Utility-based intelligent network selection[END_REF] modeled network selection using utility functions, Das et al. [START_REF] Buyya | Economic models for resource management and scheduling in grid computing[END_REF] helps users take decision over service price by modeling users' utility that captures data delay considerations. A number of utility models with numerous technical / non-technical parameters such as QoS degree, service pricing, security, power consumption, throughput/bandwidth, delay, etc. are existent in the literature. The utility modeling and selection of parameters are basically driven by the scalability and their application to a specific problem. Expecting users as the center of all services in future wireless landscape, utility theory is a natural candidate that can be used to translate user satisfaction. Utility function answers the basic question, how much does a user value the service? Utility, when defined as the function that captures user satisfaction for communication service, user keeps on consuming services as long as the user's satisfaction is met [START_REF] Zhu | Vertical handoffs in fourth-generation multinetwork environments[END_REF]. The failure of signal-based and parametric-based models has prompted the need of an alternate model which could cover NGMN typical conditions and provide accurate prediction as compared to the existing models. Therefore in this paper, we endeavor to bridge this gap by taking advantage of analytical tools and present an analytical model. However, to the best of our knowledge, there are no current analytical quality models to estimate quality level fluctuations as a consequence of time-varying conditions such as network handovers and codec switchovers which are typical conditions in NGMN environments.

Why is QoS ∼ QoE mapping needed?

The arguments justifying the QoS∼QoE mapping also serve to be the motivation force for this work. We now briefly list few of the arguments as follows; i) Owing to the short term contractual agreements of users with operators, the objective of network operators will be driven by the satisfied user pool. To attain this objective, network operators will be interested in knowing the user behavior towards service in different context. This provisions analytical function that can estimate user satisfaction for different services for online optimization. Having estimated the user QoE for any service, an operator is in better position to select the optimal strategy(ies) to increase its objective function both in competitive and cooperative market settings.

User Satisfaction Function

In this section, we present the primer on utility function and real-time applications followed by the proposed utility function.

Background on Utility Function

The concept of utility function is defined by the notation " ≽ ", which comes from the field of Economics. It is an abstract concept and is derived largely from Von Neumann and Morgenstern (1947). Utility function is designed to measure the user's satisfaction, which is subjective in nature. A satisfaction function measures users' relative preference for different levels of considered parameter values. For instance, given a number of items characterized by various parameters, a user decision of selecting any of these items will be based on relative values item specific parameters. Thus preference relation can be defined by the function, U : X → ℜ, that represents the preference ≽ for all x and y ∈ X, if and only if U (x) ≥ U (y). Here the concept of marginal satisfaction is worth mentioning, that represents the additional satisfaction gained from each extra unit of attribute. This concept is basic to demand theory which states that marginal satisfaction diminishes as the consumption of an item increases. Basically a satisfaction function should satisfy non-station and risk aversion properties [START_REF] Neumann | Theory of games and economic behavior[END_REF].

Definition 1 Let u(ρ i ) represent the satisfaction function for attribute i, from the attribute space Σ = {ρ 1 , . . . , ρ m }, then non-station property states that satisfaction u(ρ i ) increases with attribute value (given that attribute value has the expectancy the greater the better) i.e. u ′ (ρ i ) > 0.

Definition 2 Risk-aversion property states that satisfaction function is concave meaning thereby marginal satisfaction decreases with increasing value of attribute (provided that attribute value has the expectancy the greater the better),i.e. u ′′ (ρ i ) < 0. The proposed satisfaction function can capture the user-preferences over multiple attributes including those having major influence on user QoE. In the broader sense, these attributes may be categorized in three different expectancies, i) the larger the better, ii) the smaller the better, and iii) the nominal the better. The combined effect of these attributes dictate the user satisfaction level.

Background On Real-time Applications

Streaming and conversational traffic classes can be combined in real-time applications, which are commonly termed as inelastic or rigid applications. Examples of real-time symmetric applications include teleconferencing, Videophony and VoIP. Generally real-time applications are constrained by minimum amount of bandwidth i.e., application is admitted only when the demand for minimum required bandwidth is met. Such stringent requirement on bandwidth are typically represented by a step function, which means that as soon as the demand for application required bandwidth is met, users' maximum satisfaction is reached, and for a slight reduction in this bandwidth below the minimum required bandwidth, users satisfaction is zero. In our case, bandwidth offers may be defined by different codecs. However, bandwidth is not the only factor that affects the satisfaction of user, factors like packet loss, delay, handover, and codec switchover costs are important parameters to be considered specifically for mobile users.

Environment Assumptions

Heterogeneous applications have differing preferences over QoS parameters, such as delay, packet loss, and jitter etc. Values of these parameters can in turn be translated into consumer satisfaction. In this research work, we focus on real-time applications i.e., voice application. Basically as all other services real-time voice application can also be defined in terms of delay and packet loss rate, and its sensitivity to these parameters pose service quality requirements. We term application preferences as minimum application required QoS, whereas user preferences are represented by user-profile. Thus the lower bound on user preferences is set by the minimum application required QoS. We assume that different user profiles define user types. Such user distinction is an attractive solution of adaptive applications, however for real-time applications we assume that all users are equally treated. We further assume that delay impact is negligible, this assumption is strengthened by the fact that we are considering non-interactive speech, and also the assumption is in line with E-model, where below a certain delay threshold (<177ms) non-interactive communication is not affected. However, we assume that packet loss rate deteriorates the user satisfaction, as it varies in time and such time varying conditions are the consequence of varying wireless channel conditions, which in turn is influenced by the interference caused by users in the cell and other medium characteristics. We also assume that user experiences vertical handovers and codec switch overs during the life time of a call. We consider network technologies of different characteristics, let these be represented by the set W , that contains as elements the broadband and cellular network technologies. It is also assumed that handover execution delay is within permissible bounds, however we do capture its impact on the user satisfaction. In this section, we take into consideration the handover costs and codec switching costs in the formulation of the utility function. The proposed user utility function (satisfaction function) is the function of packet loss, handover, codec switchover costs but also reputation and security and reputation indexes of the operator. We summarize in Table-1 the notations and their description used in the paper. Let u j (.) be the utility function of user j, and is given by

Utility Function Representation of User Satisfaction

u j,k,o,c,co,w (pl, ψζ, φ) = ũo ( b k,o,c n o,k,c )µ co w,k,o,c e -σ(pl co w,k,o,c +ψ( b k,o,c n o,k,c )ζ w w ) -ψ( b k,o,c n o,k,c )μ co-→ co w-→ w e -pl co w,k,o,c φ co co -π k,o,c,co,w -f (r o , s o ) (1)
where µ co w,k,o,c represents the maximum achievable MOS value in the network technology w ∈ W = {W LAN, HSDP A} using codec co ∈ {G722, G722.2, G711} for operator o, pl represents the packet loss rate. Here ψ takes the value of 1, when the call handsover from high bandwidth to lower bandwidth technology or from wideband codec to narrowband codec, and -1 otherwise. μco-→ co w-→ w represents the constant gain or loss of MOS value when codec switch over takes place and their values are dictated by the network and codec characteristics. The function π represents the pricing function to the users. The term ũj,o

( b o,k,c n o,k
) is a function of network state n = (n o,k,co,w ) o,k,c,co,w and the offered bandwidth b o,k,c by the operator o. The collection n is the vector that represent the total number of users those request the service of specific class under specific codec and handover. The function f is a generic function that takes into consideration the reputation and the security of the operator (an increasing function in each of the component).

It is noted that

µ co w,k,o,c ̸ = µ co w,k,o,c
, where (co, w) ̸ = ( co, w), it shows that users quality rating is dependent on the networking conditions e.g., WiFi with stable network bandwidth along with a superior quality wideband codec sampled at 16kHz provides best results, whereas HSDPA with its fluctuating bandwidth due base station based scheduling and high link layer retransmissions is expected to provide lesser quality even if superior quality codecs are used [START_REF] Moller | Speech quality while roaming in next generation networks[END_REF]. Value of ζ is dictated by the handover type i.e., ζ bm > ζ mb , where bm, and mb represents the break before make, and make before break approaches respectively. Generally the value of σ is dictated by the application type and the underlying network technology.

Since the proposed utility function is monotonically decreasing in all the considered parameters i.e., with increase in a considered parameter value the user gets more irritated. We therefore, introduce the term cost value that represent the aggregated effect of different parameter values. Let L represents the set of considered parameters, then L = {pl, ζ, φ}. We define the cost value as: K = ∑ zm∈L z m , where z m is the individual cost contribution of parameter m. Thus the function can now be written as:

u j (K, pl, ψζ, φ) =      0 if K ≥ K max µ co w + ψ μco w if K < K ac µ co w e -σ(K-plφ) -ψ μ co w e K-(pl+ψζ) if K ac < K < K max ( 2
)
where µ co w + ψ μ co w represents the maximum achievable utility depending on the user context and users association with a technology and codec for the voice call, K max is the maximum tolerable cost by the user j , it can also be interpreted as cost threshold, above which user is no more satisfied. K ac represents the acceptable cost of the user, and it is taken as the ideal cost threshold for maximum satisfaction of user.

Consider the u j (K) of user j, where K is the aggregated cost computed from the technical characteristics of operators' offers. This dictates that there always exists an upper bound for the considered parameters due to technological constraints or user preferences / requirements. Such bounds define different regions of utilities as shown in Equation-2. Where the two obvious regions are translated as fully satisfied and fully irritated regions bounded by K < K ac and K ≥ K max respectively. Third region bounded by K ac < K < K max shows the satisfaction behavior of user following the function given in Equation 2. All the three regions define the user satisfaction of users. Let us scale the user satisfaction on the same lines as the ITU standard for QoE measurements. We scale the satisfaction function between 0 ∼ 5, where 5 represents the maximum and 0 minimum user satisfaction, i.e. u j (K) ∈ [0, 5].

The region of proposed utility function represented by µ c w e -σ(K+plφ) -ψ μc w e K-(pl+ψζ) should be twice differentiable on interval [K ac , K max ]. Fulfilling this requirement guarantees that the user satisfaction level does not change drastically with a small change in the K value and marginal satisfaction is regular. Similarly, increase in value of considered parameter, say packet loss ratio above certain threshold results in near zero user satisfaction, therefore user behaves indifferently for parameters values above some threshold value. This implies the convexity of the satisfaction curve.

In addition the utility function should also satisfy the following requirements:

u j (K) = 0 ∀ K ≥ K max (3) u j (K) = µ max ∀K < K ac ( 4
)
where µ max represents the maximum user utility.

User Equilibrium Characterization

We denote the second term in Equation 1 by ν j , which is expressed as function of pl, ψ, ζ, φ and the type, the class, the codec and the handover. We assume that the performance index pl decreases with the number of users n o,k,c . We propose the following form:

ν j,o,k,c,co,w (pl, ψ, ζ, φ) = µ co w,k,o,c e -σ(pl co w,k,o,c +ψ( b k,o,c n o,k,c )ζ w w ) -ψ( b k,o,c n o,k,c )μ co-→ co w-→ w e -pl co w,k,o,c φ co co (5)
Now, we formulate the user problem based on the utility functions. Each user j optimizes u j depending on its codec, handover, type, class of services, and operator. By fixing the operators offer (prices, technology, network availability etc), we analyze the interaction between the users in an autonomous and self-optimizing manner. We use the notion of equilibrium (Cournot, Nash, correlated, sequential, hierarchy etc.) which characterizes the outcomes. Here we restrict our attention to the packet loss pl component but the delay function can be incorporated as well.

1. The equilibria in absence of handover: In this case, we omit the index w. A pure equilibrium is a configuration of choices of users, the total number of user profiles with specific codec, type, class represented by (n o,k,c,co ) o,k,c,co such that if user j moves to (ō, co)

u j,o,k,c,co (n o,k,c,co ) ≥ u j,ō,k,c, co (n ′ ō,k,c, co )
where For the mixed equilibria of the selection problem with strict support are characterized by the indifference conditions. This means that one needs the solve the system u j,o,k,c,co,w (x * ) = max ō,co,w u j,ō,k,c,co,w(x * ) where x * the vector with component x * o,k,c,co,w of probabilities of being in the configuration (o,k,c,co,w).

n ′ o,k,c,co = n o,k,c,
In real world scenarios user satisfaction is influenced by different technical and non-technical parameters, however non-technical parameters are out of the scope of this paper. Concentrating further on technical parameters, the effect of these parameters can either be dependent on each other or independent of each other. In the scope of this research work, we consider the parameters that are mutually independent in terms of its impact on the users satisfaction. We model the utility function so that it captures the codec switch over handover costs independently, and their independent impact is added to the degradation caused by the packet loss costs. Such utility function modeling can be understood following lemma-1.

Lemma 1

The proposed satisfaction function is invariant under various independent parameters. Proof. Assume that user i ′ s satisfaction is the function of packet loss only. Let it be represented by U i (pl), and is given by U (pl) = e -σ(pl) , then for any constant parameter x it is straight forward to prove U (x + pl) = e -σ(pl+x) , which results in U (x + pl) = U (pl)e -σ(x) .

Remark 1 Having known the expected MOS value of a user in different user contexts, a decision maker is provided with suitable and necessary information for policy making, taking different quality improvement measures, and adopting certain service price offering strategies that in turn increases the operators' payoffs. Given the utility function the proportion of MOS degradation by different parameters can also be estimated.

Remark 1 is true for both the scenarios, i) where individual MOS effecting parameters are considered, ii) combined impact of various MOS effect parameters are considered. However when it comes to the later case, the proposed satisfaction function can be generalized for a number of dependent and independent parameters by introducing the relevant functions of newly introduced parameters and associating it to the satisfaction function using additive sum concept. In this case associating weights to parameters is intuitive, which takes into account the sensitivity of the parameter.

Remark 2 The satisfaction function can be replaced by an equivalent satisfaction function for

u(y) = Au(y) + B ( 6
)
where A > 0 and B is arbitrary. Hence it is possible to standardize the satisfaction function for a particular point ς.

Example -1 Let the the standardization of satisfaction function is required for ς = 0, the for the satisfaction (simplified form of equation-1). u(y) = µ.e -σ(y) [START_REF] Côté | Analysis of a Quality Prediction Model for Wideband Speech Quality, the WB-PESQ[END_REF] It can be noted that for y → ∞, the satisfaction is bounded and tends to the finite value zero.

Satisfaction Criteria

In this section, we investigate the performance of proposed utility function for single and multiple criteria.

Single attribute utility function

In a single criterion utility function, the utility function captures user satisfaction for the possible degradation effect introduced by the criterian. Consider an ideal scenario, where a static user experiences zero delay, no vertical handover and no codec switchovers. In such a case users satisfaction is fully dependent on the packet loss rate.

u i (pl) := µ co w e -σ.pl ∀pl ∈ [pl ac , pl max ] (8)
Let us consider that user the is associated to a specific codec say co = G711, and with network technology w = HSDP A, here µ co w represents the maximum achieveable MOS value in this scenario, which is achievable for packet loss less than pl ac . We plot the MOS curve for this scenario in Fig 1a . In addition we also investigate single attribute utility function for a different network technology w = W LAN , and broadband codec G722, and plot the user satisfaction curve for this scenario as well 1a. As can be observed that µ G722 W LAN > µ G711 HSDP A , this strengthens the argument presented in section 3. One more point to be noticed here is that σ-value in WLAN is greater than in HSDPA, which results in greater decay of MOS value with increasing packet loss. The proposed utility function behavior is validated for various scenarios in later sections; i.e., keeping the mentioned setting for experiments we obtain values for different values of packet loss (0%, 10%, 20%). In a multiple attribute utility function, the utility function captures user satisfaction for the possible degradation effect introduced by the combined effect of multiple criteria. Now we consider a scenario, where a user experiences vertical handovers, and his satisfaction is influenced by both packet loss and handover costs, which is represented by:

u i (pl) := µ co w e -σ.(pl+ψζ) ∀pl ∈ [pl ac , pl max ] (9)
Let us consider a specific scenario, where a user is initially associated with network technology WLAN and codec G722.2. The maximum achieveable MOS value for this user is µ G722.2 W LAN , now that user experiences a vertical handover to HSDP A, he experiences a further degradation (this degradation is represented by ψζ, in this case ψ = -1). We plot the MOS curve for this scenario as shown in Fig 1b.

Experiments

In this section, we discuss our experimental methodology for carrying out the controlled experiments and then conduct auditory tests for NGMN conditions.

Mobisense Testbed

In order to perform quality of experience study, we rely on Mobisense testbed which was designed to investigate user perceived quality in NGMN using VoIP as the primary application. The testbed depicted in Figure 2 allows mobile clients to perform network handovers and voice codec changeover while keeping on-going calls. The testbed uses Mobile IPv4 as a solution to enable seamless handovers between different radio access technologies [START_REF] Perkins | IP Mobility Support for IPv4. RFC 3344[END_REF]. Thus, the main network elements of the testbed are the Mobile Node (MN), the Corresponding node (CN) and the Mobile IPv4 Home Agent (HA). The setup includes various different access technologies such as WLAN/WiFi, UMTS/HSDPA and Flash-OFDM (pre-WiMax release) that are used to emulate an integrated NGMN environment.

The CN and MN were deployed on laptops with linux 2.6.18.2 and HA was configured on a Cisco 2620XM router with Cisco IOS 12.2(18r). Based on SIP protocol we choose PJPROJECT [START_REF] Prijono | Open Source SIP Stack and Media Stack for Presence, Instant Messaging, and Multimedia Communication[END_REF] framework as voip client to play speech files. We employed seamless codec switching scheme by Wältermann et al. [START_REF] Wältermann | A Technique for Seamless VoIP-Codec Switching in Next Generation Networks[END_REF]. The detailed description of design and the capabilities of Mobisense testbed are outlined in [START_REF] Vidales | Mobisense Testbed: Merging User Perception and Network Performance[END_REF].

Methodology

We pre-selected NGMN conditions with the combination of (i) Network handovers between different technologies, (ii) Codec-switching between narrowband codec and wideband codec, and (iii) Different packet loss rates. We use ITU-T G.711 log PCM codec at 64 kb/s for narrowband (NB) with native packet loss concealment and ITU-T G.722.2 (AMR-WB) codec at 23.05 kb/s for wideband transmission. For benchmarking purposes we select few conditions with a single network, a single codec and 0% packet loss. We establish the quality bounds by using these benchmark conditions. Of course one could argue why not to test all combinations but carrying out a full factorial combination of subjective tests is practically infeasible. We use netem packet shaper for degrading VoIP packets as shown in Figure 2.

All calls were initiated at CN and terminated at MN. During on-going calls network conditions were imposed depending upon the requirements of network handovers or codec switching. At MN, speech samples were collected and processed for subjected tests according to ITU-T P.800 [START_REF]Methods of Subjective Determination of Transmission Quality[END_REF]. Further we select speech samples for both male and female speakers to obtain a balance set of speech samples. These samples were then presented to 24 subjects for quality assessment. For the quality rating, 5-point Mean Opinion Score (MOS) scale was used. More details of these tests can be found in [START_REF] Moller | Speech quality while roaming in next generation networks[END_REF]. The overall assessment along with conditions is listed in Table 2.

Results and Model Validation

In this section, we compare subjective ratings with our model predictions. In principle the model should be able to predict estimations for most of the conditions. We first check correlation of the predicted values of our model with the subjective test ratings obtained in Table 2. The results are shown in Figure 3. The concentration of most of the points around the diagonal line is an indicator of a good match between model predicted values and the actual ground truth obtained from We note that for the conditions # 1, 2, 3, 8 10 and 12 in Table 2, our model perfectly match the subjective ratings. For conditions #5, 9, 11, 14 and 15 model is off by maximum of 0.26 MOS value. However, inspite the fact that we see a high correlation we have certain conditions e.g., condition #4 and 7 where our model deviates from the subjective ratings. We plot different curves for both the utility function and experimental data in different scenarios so that behavior of utility function for different parameters can be investigated. In Figure -5, we consider the scenario where the user is associated to WLAN and G722.2, in this scenario we study the impact of packet loss rate. As evident from the Figure-5 proposed utility function almost overlaps the experimental results for low packet loss values, very small deviation is observed, when packet loss rate approaches 20%. Although experimental results are not available for greater packet loss than 20%, the proposed model can confidently estimate the behavior for higher packet loss values. A number of similar curves were obtained for scenarios like i) user associated to HSDPA and G711 with experiencing no handover and codec switch over, ii) user associated to WLAN, G722.2 and experiencing handover to HSDPA, iii) user associated with HSDPA and handsover to WLAN, iv) Codec switchover, v) Simultaneous codec switchover and network handover etc. In all the mentioned scenario user utility function was validated against the experimental results.

Fig. 1 :

 1 Fig. 1: Impact of various attributes on user satisfaction

F l a r i o n 1 Fig. 2 :Fig. 3 :

 123 Fig. 2: Mobisense experimental setup for VoIP services in NGMNs

Fig. 4 :Fig. 5 :

 45 Fig. 4: Plots of Utility for single and multi-attribute scenarios

Table 1 :

 1 Notations and their description

	Notation Description
	uj(.)	Utility function of user j
	k	Index of service type
	c	The class of service (VoIP in this case)
	co	Index of codec
	w	Index of network technology
	π	the price user pays against the service
	n o,k,c,co,w Number of users (k, c, co, w) with operator o
	b	Bandwidth
	pl	Packet loss
	σ	Measures the rate of decay of user's satisfaction.
	ζ	Handover costs.
	r0	Index of operator reputation
	so	Index of operator offered security
	φ	Codec-switchover costs respectively.

  if user moves to (o, co) and equal to n o,k,c,co if user does not move. 2. The equilibria in absence of codec switchover: In this case, we omit the index co. A pure equi-

co -1 if user j has moved from (o, co), n o,k,c,co + 1 librium is a configuration of choices of users, the total number of user profiles with specific handover, type, class represented by (n o,k,c,w ) o,k,c,w such that if user j moves to (ō, w)

u j,o,k,c,w (n o,k,c,w ) ≥ u j,ō,k,c, w(n ′ ō,k,c, w) where n ′ o,k,c,w = n o,k,c,

w -1 if user j has moved from (o, w), n o,k,c,w + 1 if user moves to (o, w) and equal to n o,k,c,co,w if no moves. 3. The equilibria in presence of both handover and codec switchover: In this case, we take on both indexes w, co. A pure equilibrium is a configuration of choices of users, the total number of user profiles with specific codec, type, class represented by (n o,k,c,co,w ) o,k,c,co,w such that if user j moves to (ō, co, w) u j,o,k,c,co,w (n o,k,c,co,w ) ≥ u j,ō,k,c, co, w(n ′ ō,k,c, co, w) where n ′ o,k,c,co,w = n o,k,c,co,w -1 if user j has moved from (o, co, w), n o,k,c,co,w + 1 if user moves to (o, co, w) and equal to n o,k,c,co,w if no move.

Table 2 :

 2 Comparison of Analytical Model estimates and Auditory Judgments (MOS).

The emergence of new access technologies along with evolution of smart phones have paved a way of any time anywhere connectivity for mobile users. However this new paradigm has brought along many challenges for network service providers. The biggest of them is to maintain a certain level of quality for multimedia streams of their customers.

With this context, in this paper we propose a utility-based analytical quality prediction model which predicts user QoE for conditions that are typical to NGNMs such as network handovers, codec switching and different packet loss rates due to adverse wireless networking conditions. We validate quality prediction of our model with subjective tests. Our results show that the quality prediction by our model has correlation of r = 0.923 with subjective ratings.

In future, we plan to include more NGMN typical conditions and to extend our model for new services e.g. IPTV, video conferencing and video telephony.


Manzoor Ahmed Khan
email: manzoor-ahmed.khan@dai-labor.de

Yasir Zaki

Dynamic Spectrum Trade and Game-theory Based Network Selection in LTE Virtualization using Uniform Auctioning

Keywords: LTE, Wireless virtualization, Spectrum sharing, Uniform auctioning format

It is expected that in future user-centric wireless network scenario the concept of dynamic spectrum trade will provide operators with opportunities to utilize the spectrum more efficiently. Wireless market players (both incumbent and new entrants) trade the spectrum chunks on the provide, when needed basis with the spectrum broker. In this paper, we model the interaction between different stake-holders such as users, operators and spectrum brokers at different hierarchical level and investigate the equilibria. We also model the utility functions of all the stake-holders. We propose and implement the realization framework for the proposed dynamic spectrum allocation approach using Long Term Evolution (LTE) virtualization.

Introduction

The evolution of wireless communication technologies places the scarce radio spectrum as the main pillar of future wireless communication, which in turn dictates that spectrum should be efficiently managed. The current practices for spectrum management in any country is regulated by the governmental body (e.g., FCC in USA or ECC in Europe) and the current trend of spectrum allocation is driven by the rigid frequency distribution through auctioning. Such spectrum allocation approaches are static and specific to the usage parameters (i.e., power, geographical scope etc.) and usage purposes (i.e., cellular communication, TV broadcasting, radio broadcasting etc.). Although spectrum auctions have been a success in this regard by putting essential spectrum in the hands of those who best value it. Upstream Market

Downstream Market

Fig. 1: Hierarchical position of telecommunication stakeholders and their objectives However, such spectrum management may not cope with the growing and dynamic needs of spectrum, particularly in environments, where the network selection decision is delegated to users (user-centric paradigm) and /or where market is shared by the small scaled new entrants such as Mobile Virtual Network Operators (MVNO) etc. We now make an attempt to define the spectrum inefficiency by discussing a prevalent bidding procedures. In the current fixed spectrum allocation scenario, the telecommunication operators bid for the amount of frequencies they are interested in, when declared winner, the bidding operators are allocated with some amount of frequencies for periods spanning over years. This dictates that the operators frequency demands are the results of their peak traffic planning i.e., busy hour, which represents the peak network usage time. It should be noted that bandwidth demands are exposed to variation not only with respect time, but also depends on location (spatial variation). This, in a way addresses the issue of satisfying the operators' demands and reducing the call blocking at the operator end, but at the same time it causes temporal underutilization in less busy periods. Hence the static spectrum allocation often leads to low spectrum utilization and results in fragmentation of the spectrum creating white space that can not be used for either licensed or unlicensed. Thus the potential candidate solution that one could think of is the Dynamic Spectrum Allocation (DSA) approach. DSA can significantly improve the spectrum utilization and provide a more flexible spectrum management method and promises much higher spectrum utilization efficiency. DSA concept brings a good news for the wireless service providers, as the flexible spectrum acquisition gives a particular provider the chance to easily adapt its system capacity to fit the end users demands. One could wish for situations, where solutions are not accompanied by the issues. The DSA solution is also brings few challenges e.g., frequency interference problem and DSA implementation in usercentric wireless communication paradigm etc. In this paper, we confine our discussion more on dynamic spectrum allocation in user-centric paradigm, the interaction of stake-holders in the mentioned paradigm, and the related issues. Obviously the DSA problems turns out to be more complicated, when it comes to user-centric network selection scenarios, where the operators' associated size of user pool is dynamic, in this case the operators are faced with two obvious competitions. We term these competitions with respect to their positions in the telecommunication hierarchical figure i.e., Fig 1. The competition or the interaction that takes place vertically between spectrum provider and operators is termed as upstream competition and the competition vertically between users and operators is termed as downstream competition. Our focus in this paper is to capture the interaction among spectrum broker, wireless service providers and end users. Intuitively all the stake-holders in this scenario aim at maximizing their own profits (the objectives of each stake-holders are mentioned on the respective level in the Fig 1).

Related Work

The concept of DSA first came up in the DARPA XG program [START_REF]DARPA Next Generation Communication Program[END_REF], the project aims to develop, integrate, and evaluate the technology. The emphasis is on enabling the user equipment that automatically selects spectrum and operating modes to both minimize disruption of existing users, and to ensure operation of U.S. systems. In [START_REF] Milind | Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access[END_REF], the authors propose a spectrum broker model that controls and provides operators the time bound access to a spectrum band. The authors investigated spectrum allocation algorithms for spectrum allocation in homogeneous CDMA networks and executed spectrum measurements in order to study the realizable spectrum gain that can be achieved using DSA. Authors in [START_REF] Rodriguez | Market-driven dynamic spectrum allocation: Optimal end-user pricing and admission control for cdma[END_REF] propose a scheme, where the spectrum manager periodically allocates short-term spectrum licenses. The spectrum rights are traded amongst the operators for a fixed amount of time, the license for the allocated spectrum automatically expires after the predefined time period. However, [START_REF] Rodriguez | Auction driven dynamic spectrum allocation: optimal bidding, pricing and service priorities for multi-rate, multi-class cdma[END_REF] assumes that the operators follow the multi-unit auction format for the spectrum trade, where the sealed bids are submitted for the spectrum resources and the winner operator pays the second highest price (the price of resource is assumed to be charged on per unit basis). Buddhikot and Ryans [START_REF] Ryan | A new pricing model for next generation spectrum access[END_REF] in their seminal work discuss the DSA management, where the authors focus on spectrum allocation and pricing. The paper introduces the concept of coordinated DSA and the spectrum broker, the paper illustrates over various allocation algorithm types e.g., online vs. batched, in addition it also highlights the notion of interference conflict graph, and the cascading effects among brokers on blocked list. Linear programming formulation is used to solve the problem of the spectrum allocation with feasibility constraints i.e., maximal service vs. minimal interference, maximal broker revenue vs. max-min fairness. A deviation from the use of distributed approaches is observed in the centralized auction based approach [START_REF] Sorabh | A general framework for wireless spectrum. 7[END_REF], where authors assume pairwise interference conflict graph, piece-wise linear bidding functions, and homogeneous non-overlapping channels. The efficiency of spectrum utilization is also addressed in European Union projects such as Dynamic Radio for IP Services in Vehicular Environments (DRiVE) [7] and overDRiVE [8], that investigates co-existence, sharing rules with broadcast and military systems and scenarios for a dynamic regional/temporal spectrum allocation.

Motivation

The hierarchical business model presented in Fig 1 dictates interdependency of the stake-holders i.e., the stake-holders at the operators' level depend on the service demands pattern from underlying common user-pool for formulating their (operators') spectrum demand at different times and for different geographical locations. The service demands do not only influence the operators spectrum demands but also the operators valuation for the spectrum. On the similar lines, the offered service prices and service quality by the operator drive the user demands, which in turn has impact on the spectrum demands and consequently on the profit of spectrum broker and the operators. As can be seen in the Fig 1, the consequence of such interdependency is the integration of two markets (upstream and downstream). Thus investigating the efficiency (e.g., resource utilization at operator level, user satisfaction maximization at user-level etc.) at one of the hierarchical level and not considering their dependency at different levels may not lead to realistic efficient solution. Considering the future user-centric wireless network paradigm, the characteristics of attractive LTE like technologies, and the interaction among all the stake-holders, one can think of a more realistic spectrum distribution. We are also convinced that the interaction model is different for different geographical regions, hence there is a need for a generic model that captures the interaction for the regions and define all the markets on granule level. In the current literature, these aspects are widely oversimplified and many frameworks have been presented lacking to fulfill the basic requirements of general distribution systems, where limited resource is to be divided among the participants. Although the existing literature that discusses the possible spectrum allocation models and related issues is vast, our work focuses on modeling the interaction at different levels, we also take an opportunity here to justify the technical feasibility of dynamic spectrum allocation concept i.e., investigating the support of flexible transmission frequencies in new generation technologies e.g., LTE promises the flexible operational frequencies. Future wireless network communication is boosted by the concept of technology virtualization. When it comes to technical realization of the dynamic spectrum allocation concept, one of the attractive solutions is virtualization. The choice of Virtualization as a technical solution is driven by the widespread and yet growing presence of this concept in the research literature e.g., many research projects including PlanetLab and GENI [START_REF] Bavier | Operating system support for planetary-scale network services[END_REF] [10] in the United States, AKARI [START_REF]AKARI architecture conceptual design for new generation network[END_REF] in Asia and 4WARD [START_REF] Bauck | Virtualisation as a co-existence tool in a future internet[END_REF] in Europe. The basic definition of virtualization comes from the environment, where the technical setup with under-utilized resources can share its unused resources with other entities and processes (which require resources), this argument forms the basis for the growing importance and existence of virtualization in the time to come. There is a number of research activities in virtualization as well as a number of commercial solutions using virtualization: e.g., Server Virtualization, Router Virtualization, XEN, Cloud Computing etc.

Wireless virtualization is yet another very important aspect specially for the future. The best candidate for applying virtualization in the wireless domain is mobile networks. In [START_REF] Zaki | A Novel LTE Wireless Virtualization Framework[END_REF] it was shown that virtualization in mobile networks (represented by the LTE) has a number of advantages. Multiplexing gain as well as better overall resource utilization were the key gains achieved. In [START_REF] Zaki | LTE Wireless Virtualization and Spectrum Management[END_REF], a more practical framework was investigated for LTE virtualization and spectrum sharing among multiple virtual network operators. The framework focused on a contract based algorithm to share the spectrum between the operators.

Downstream Market

In this market, we model the interaction between operators and users. We propose the user and operator utilities, focus on the learning aspects of the proposed utilities, and study the interactive trial and error learning for finding equilibria. Extending the concept of service priorities i.e., Guaranteed Bit Rate (GBR and Non-Guaranteed Bit Rate (Non-GBR) in LTE, we assume that there are three different types of users namely; i) Excellent, ii) Good, and iii) Fair. These users are characterized by the their preference profiles e.g., an excellent user prefers the service quality, whereas a fair user is interested in the service costs. We further assume that users broadcast the application requests in an abstract area a for three different types of applications namely; i) Voice over IP (VoIP), ii) File Transfer Protocol (FTP), and iii) Video streaming. The modeling in this market is decomposed as following:

-Operator level: Each operator uses a network pricing scheme and allocates the resource to the users under the associated quality of service constraints (which is translated in to users QoE). Operators with lowest cost but with good QoS will be more and more congested. This will lead to saturation and bad QoS. When, increasing the prices, the users will switch to another class or operator in order to get better utility. This means that strategy of the operators are interdependent (the pricing of operator influence the others via the network repartition of users for each user type and service class). -User level: At this level, each user seeks to maximize his utility with as low cost as possible.

-Interdependency between the levels: The prices fixed by the operators influence the user decisions: network selection based the set of operators that are the QoS requirement with lowest costs. In parallel, the decision of the users leads to a subnetwork for each operator. When maximizing his revenue, the operator needs to readapt its price in function of the user choice and the other operators. This leads to a interdependent multi-level system.

Network Operator Resource Allocation Problem

Each operator seeks to optimize its total revenue R o := k,c π(o, k, c)n c o,k subject to the QoS constraints. For the accepted users, a bandwidth allocation between the users is established. Then, each operator o designs the function π for each type k and each service class c.

User Centric Network Selection Problem

At user level, the user problem is to select the suitable network operator. In this connection we need to model the user preferences and performance metrics. This will be captured by the utility function. Let K be the set of three different types of users, and U i represents the utility of user i, ∀i ∈ K. The expression of U i (.) is given as follows:

U i,k,c (o, n) := u i,o b c o,k n o,k l∈L (ν il,o (k, c, n)) w il .π(o, k, c) + j∈J ω j v ij,o (k, c, n, ψ), (1)
The user utility function (equation-1) has four components:

-The term u i,o b c o,k n o,k is the function of network state n = (n c o,k ) o,k,c
and the offered bandwidth b c o,k by the operator o. The collection n is the vector that represent the total number of users those request the service of specific class.

- l∈L (ν il,o (k, c, n)) w il
is the weighted multiplicative approach for dependent associated QoE attributes.

- j∈J ω j v ij,o (k, c, n, ψ) is the weighted sum of different independent QoE attributes.
π(o, k, c) is the price of operator o to the user type k for service class c.

The first two multiplicative terms take into account both the congestion level of the operator and expected QoE, which is translated from the Operators QoS indices. The weight values w are dictated by the sensitivity of user type, service class to the attribute j. Here k ∈ Θ, where Θ is the finite set of user types. Each operator o chooses its price vector π o in a competitive way.

In order to formulate a utility function that respect the preference of the users and the performance metric of the network we use an experimental approach. The expression of utility functions are given by experimental observations. The objective measurement validation of the proposed utility function can be seen in [START_REF] Manzoor | User utility function as quality of experience (qoe)[END_REF] Bandwidth dependent utility Availability of bandwidth / transmission data rate plays the key role in evaluating the user QoE, therefore most of the literature work focus on the impact of varying data rate/bandwidth over QoE. However the user satisfaction should be analyzed with respect to different technical and non-technical attributes, and QoE evaluation metric vary with respect to application used by the user. We capture the bandwidth dependent user satisfaction with the following utility function:

t i,k,c (o, n) :=                      0 if b c o,k n o,k ≤ b c o,k α k (n o,k ) 1-e -β(b c o,k -b c o,k ) 1-e -β(b c o,k -b c o,k ) if b c o,k ≤ b c o,k ≤ b c o,k α k (n o,k ) 1-e -β(b c o,k -b c o,k ) 1-e -β( bc o,k -b c o,k ) if b c o,k ≤ b c o,k ≤ bc o,k α k (n o,k ) 1-e -β(b c o,k -bc o,k ) 1-e -β( b c o,k -bc o,k ) if bc o,k ≤ b c o,k ≤ b c o,k α k (n o,k ) if b c o,k ≥ b c o,k (2)
where Now, we examine the outcome of the network selection in a competitive manner at the user level with the utility t i (.). At this level, each type of user seeks to maximize its utility t i,k (o, n). In this setting a well-studied solution concept is the called Cournot-Nash equilibrium. It is network configuration n * such that for any i, k, the utility t i,k,c (o, n) is maximized by fixing the choice of the other users.

α k (n 0,k ),
Next, we show that the user-centric game (the game at the user-level when the pricing functions chosen the operators are fixed) is in the class of congestion game [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF]. A finite game in strategic form is a potential game [17] if the incentive of all players to change their strategy can be expressed in one global function called the potential function.

Proposition 1 The user-centric game is a finite potential game.

Proof. Let π the pricing function chosen the operators. Since the utility t i,k,c contains only a congestion part via the total number of users n o,k for each range of bandwidth, one gets a standard congestion game which is known to be isomorphic to a potential game. The exact expression of the potential function can be obtained from [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF]17].

Corollary 1 The user-centric game has at least one pure Nash equilibrium. This result follows from the fact that the existence of pure Cournot-Nash equilibria holds in finite potential game [17].

Here we apply it for each range of bandwidth.

The second issue that we address is the computation and the learning aspect of such equilibrium configurations. Different learning techniques have been developed for this specific class of games: finite improvement path, fictitious play, best response dynamics, stochastic fictitious play etc. Most of these learning schemes require at least the information of the network states at the previous step which seems to be very strong assumption in our context.

Because the number of users in the hull network can be arbitrary large, observing and responding to the individual choice of all users on a frame of time units would be a formidable task for any individual user. Therefore, the standard fictitious play and the iterative best reply are not directly applicable. Note that in the finite improvement path procedure (FIP) only one user moves at a given time slot (simultaneous moves are not allowed). For this reason, the FIP is not adapted when the network does not follows a prescribed rule evolution.

One of the well-known learning scheme for simultaneous-move games is the trial and error learning. Interactive trial and error learning is a recent version of standard trial and error learning studied in [START_REF] Young | Learning by trial and error[END_REF] that takes into account the interactive and dynamic nature of the learning environment. In ordinary trial and error learning, users occasionally try out new operators and classes and accept them if and only if they lead to higher performance. In an interactive situation, however, "errors" can arise in two different ways:

the active errors, those done by trying some new operator that turns out to be not better (in terms of QoS, price and performance) than what one was chosen, or the passive errors, those done by continuing to keep the old strategy that turns out to be worse than it was before (due to congestion, new traffic conditions etc) .

In [START_REF] Young | Learning by trial and error[END_REF], it is shown that the interactive trial and error learning, implements Nash equilibrium behavior in any game with generic utilities and which has at least one pure Nash equilibrium. The interactive trial and error learning is a fully distributed learning rule such that, when used by all users in a game, period-by-period play comes close to pure Nash equilibrium play a high proportion of the time, provided that the game has such an equilibrium and the payoffs satisfy an interdependency condition. Since our finite utility given by the t i (.) has at least one equilibrium, the learning procedure implements one of the equilibrium with proportion of the time.

We assume that each user makes selection and service request decisions in random frames to optimize its own objectives in response to their own observations and local clocks and is able to measure a numerical value of its benefit and pay a cost for the service that he/she consumed. He is able to evaluate t i,k,o if the tried operator is o. Based on this measurement the user update his/her strategy when he/she will be active: keep the strategy with probability (1 -) if the performance is greater or try another strategy with probability . All this is done for a well-chosen ∈ (0, 1).

Proposition 2

The interactive trial and error learning algorithm implements a pure Nash equilibrium of the usercentric game with high proportion of times.

Proof. We verify that the conditions in [START_REF] Young | Learning by trial and error[END_REF] are satisfied. First, the user-centric game is a finite game for any fixed pricing function π. Second, the game is not degenerated because the utility functions are strongly interdependent via the network state. Third, we know that the game has at least one equilibrium from the corollary 1. Combining together all the conditions in [START_REF] Young | Learning by trial and error[END_REF] are satisfied. The result follows.

Learning in dynamic environment Since the network is dynamic the associated game model should capture the variabilities, network traffic and the randomness in the environment. To this end, we extend the learning framework to dynamic game. For more details, we refer to [START_REF] Tembine | Distributed learning in dynamic robust games: dynamics, algorithms and network applications[END_REF] in which the number of active users may be random, new users come in, and exit etc. Without knowledge of the network state, without knowledge of the distribution of users, each active user tries to find out his/her utility function and associated payoff in the long-term [START_REF] Tembine | Distributed learning in dynamic robust games: dynamics, algorithms and network applications[END_REF].

Price of Anarchy and Suboptimality Note that, even if this learning algorithm implements Nash equilibria of the game, the convergence time to be close to an equilibrium can be arbitrary high. Moreover, it is known that the equilibrium can be inefficient in term social welfare. The performance gap between the total equilibria utilities and global optimum is sometimes referred to price of anarchy.

In order to reduce this gap, the operators can design new game via their pricing functions. Under appropriate pricing functions π, one can design a game such that the equilibrium configuration of the new game (the utility is the difference between profit and cost) is near-optimal. This leads to the utility U i (instead of t i ). Important components of U i are the attributes dependent utilities v ij and the cost functions π. For more details on the associated dependent and independent utilities refer to [START_REF] Manzoor | User utility function as quality of experience (qoe)[END_REF].

In this market, we model the interaction between operators and the spectrum broker using the uniform price auctioning theory. The motivation for choosing the mentioned auction format is it common use in financial and other markets, which is evident by a large economic literature devoted to its study (e.g., Ofcom, Award of available spectrum: 1781.7-1785 MHz paired with 1876.7-1880 MHz: A Consultation, 16 September 2005.). It is also argued that to a large extent, the FCC spectrum auctions can be viewed as a uniform-price auction [START_REF] Cramton | The efficiency of the fcc spectrum auctions[END_REF]. In a uniform-price auction, small bidders can simply bid their valuations and be assured of paying only the market-clearing price [START_REF]Auction design issues for spectrum awards market analysis ltd[END_REF]. The fact highlighted in [START_REF] French | Spectrum auctions 101[END_REF] that in uniform price auctions the downstream playing field is level, in the sense that each licensee begins with the same foundational asset at the same price is also one of the motivating force to user the uniform price auctioning for spectrum trade. More on auction clearing algorithms can be found in [START_REF] Sandholm | Market clearability[END_REF].

In our formulation, the spectrum broker (virtualized LTE framework) is analogous to auctioneer, network operators are analogous to bidders, and the resource to be auctioned is analogous to auctioned-item. We assume that the auctioned-items are homogeneous and perfectly divisible. This assumption is strengthen by the fact that current trend of introducing flexibility in frequencies licensing i.e., providing operators with the technology neutral spectrum allocation. Let the distribution of auctioned item size has support in the range [X min , X max ], which defines the resource limits, where X min is a single PRB (Physical Resource Block) size and X max is the total capacity of the spectrum resource, hereafter we use C to represent the total resource capacity of the infrastructure provider. Let there are N symmetric risk-neutral bidders (operators), who compete by simultaneously submitting their nonincreasing demand functions x i,k . These bidders have independent private valuation function of the auctioned item, which is driven by the bidders' demand and the service types. Although the resource is homogeneous, the bidders have different valuations for different amounts of the resource. Such valuation is strictly influenced and is the consequence of service types for which the resource is required. We assume that the market comprises of demands of two service types namely Guaranteed service and Non-guaranteed, intuitively the former has more strict resource requirements when compared with the later. Let the νi be the bidder private valuation of the auctioned item. Influenced by the comment given in the preceding sentence, the bidder valuation varies for demands of different service types, this is captured by the index k, thus the bidder valuation now can be represented by νi,k such that νi,k = νi, k∀k = k. To illustrate this one has to consider the service demand patterns of the operators or putting it the other way operators spectrum valuation is driven by the operators' target market segment e.g., an operator targeting the fair users values the amount of spectrum demands for fair users more than the amount of spectrum for other user (service) types, the similar argument holds for the converse situation. Thus the strategy for bidder i ∈ N is non-increasing function X i : [0, ∞) → [0, X max ], and the his private valuation νi,k , which is the evaluated spectrum price by the operator, the details of computing such valuation is given later in this section. Thus the operator bid is given by {x i,k , νi,k }. It should be noted that the valuation is computed as price per unit of the spectrum. We assume that the market behavior is represented by Equation 3, and we term this market as spectrum trade market hereafter. As can be see that the demand curve is linear that expresses the demand as a linear function of the unit price. The choice of this market behavior is influence by its simplicity and wide presence in the literature.

π(x) := -ζx + ς, (3)
where ζ and ς are positives, the negative gradient represents the sensitivity of market towards the price, and ς represents the bound on price. We know that the gradient introduces the elasticity in the curve. However, the proposed problem formulation dictates an inelastic spectrum demand behavior i.e., irrespective of how price may change the demand remains the same. This is represented by a perpendicular to the quantity axis in

where γ k tunes the operators' valuation for the given demand and the service type such that; if the service type is of higher importance to the operator γ k takes comparatively lower value than that of lower importance service. γ k further can be translated as the function of number of operators in the spectrum competition and demands of service type i.e., real time service has higher value than that of background or non-real-time values i.e., γ(k, N -1). Although one may come up with any suitable γ(.) function, in this work, we simply represent it by a real-value exposed to simple constraint of γ k,i = γ k,i ∀k = k and γ k,i = γ k, ĩ∀i = ĩ. Furthermore, it should be noted from the Fig 2 that the price given by the intersection of the demand perpendicular and the negative slope of market curve is the upper bound on the prices set by the regulatory body.

Remark 1 We observe that downstream market demands (user service demands) influences the operator demands (operator resource demands). Although the optimal estimation of the service demands by users can be computed analytically, in this paper, we adopt the methodology for estimating the downstream demands based on the carried out simulation runs for all the virtual operators. In this connection we use the Exponential Moving Average (EMA) function to compute the estimated demands based on 20 seconds time intervals. Given the downstream demand, the upstream demand function can be computed.

Definition 1

The operator valuation γ i,k is directly translated in to πi,k i.e., based on service types and downstream market demands the operator reflects its valuation as πi,k such that γ k,u = πi,k . Intuitively the false valuation πi,k is given by γ k,u = πi,k .

Let f be the mapping function that maps the downstream demands Y over the upstream demand function X, such that f (Y ) → X. For simplicity we assume that the mapping is bijective. Given the upstream demand function an operator computes its valuation of resource using Equation 4. Realizing the upstream demand and by Definition 1 the operator formulates its bid for the resource, which is given by d i (X, π).

Allocation Rule Given the uniform price auctioning format, let d represents the highest bid, and p represents the stop out price;

a i (X i , d i ) :=      X i if d i,k = d ∧ X i ≤ C ∧ d i,k > p min{X i , C - d-i∈B, d-i\di X d-i } otherwise (5)
As can be seen from Equation 5the operator which is declared as the highest bidder gets the resources equivalent to its demands. In case the operator does not occupy the highest bidder position and resides in the winner list then it is allocated the residual resources not necessarily equivalent to its demands. The operator gets the residual demand when the infrastructure resource capacity is less than the operator demands(lower part of Equation 5). The resource allocated to each operator is independent of the auctioning format, however the payments do depend on the auction format.

Operator utility function As we know that operators have different valuation of different amounts (i.e., spectrum for k and k type services) of spectrum. However, the allocation rule dictates that operators are allocated according to their aggregated demand request. Thus the operator profit function involves both spectrum amounts of different operator valuation values. We define the operator utility function for resource allocation a i to operator i ∈ N and the stop-out price be p as:

u i (a, p) := (γ k -p)x k + (γ k -p)x k (6)
As can be seen that operator utility increases in its valuation and demands and decreases in stop-out price.

Auctioneer utility function

The profit function or utility function of auctioneer (LTE virtualition framework) is the function of bidder demands and stop-out price and is given by:

u( i∈N X i , p) := d∈B a d × (p - √ x λ ) (7)
where √ x λ represents the incurring cost of auctioneer, λ is controller that enables the auctioneer to scale the cost that follows the operator specific deployment pattern (i.e., co-location, site rentals, tower rental etc.), the detail modeling of cost function (modeling operational and maintenance, deployment costs etc.) is out of the scope of this paper. However the choice of square-root function to capture the operator cost function is influenced by the continuous nature of the function for all non-negative numbers and differentiable for all positive numbers, the function also capture the realistic nature of the operator cost i.e., the operator initially incur more cost on improving service and such cost decreases with increase in demands. Spectrum broker maximizes its utility i.e., max p u j ( i∈N X i , p), which increases in p and allocated resources and constrained by the operators' capacities. Thus the problem that the auctioneer solves is to decide the auction clearing or stop-out price and resource allocation (for allocation rule see Equation 5) i.e., p = sup p| i∈N X i ≥ K . We also present the algorithm that is implemented by the auctioneer to take the decision over resource allocation and stop-out price as follows:

Equilibrium Analysis -A Two States Tale

We characterize the Nash equilibria in the mentioned model in weakly dominant strategies.

Lemma 1 In an homogeneous item uniform price auctions, the operators with multiple bids have a unique dominant strategy for each bid in different instances i.e.,

d i,t1 := γ i,t1,k (8)
and d i,t2 := min{R, γ i,t2, k}.

Proof. Proof omitted due to space restrictions.

Sequence of Actions

1. Each bidder observes the demands (based on EMA, mentioned earlier). 2. Infrastructure provider announces the start of auction time t init and duration of bid submission i.e., t init -t max .

3. Bidders submit their demands to the auctioneer at each per-unit price, which is the valuation of the bidder and attained from the Equation-4. 4. After the elapse of the submission time, the infrastructure provider observes the aggregated demand and sets the stop out price, which is equal or greater than the incurring cost over the unit resource. The auctioneer also decides each bidder's allocation. 5. The allocation is executed through the hypervisor 6. The process iterates over 1 -4, after the inter-auction time δt expires.

In this section, we the LTE virtualization framework that we implement extensively to realize the proposed dynamic spectrum allocation concept. We virtualize the LTE network infrastructure (i.e., eNodeB, routers, ethernet links, and aGW etc.) so that multiple mobile network operators can create their own virtual network (depending on their requirements) on a common infrastructure. In the proposed virtualized network, we mainly foresee two different aspects; i) Physical infrastructure virtualization: virtualizing the LTE nodes and links and ii) Air interface virtualization: being able to virtualize the LTE spectrum. However, we in this paper focus on the later aspect, since virtualizing the air interface of the LTE system is a completely new concept and also the earlier aspect is extensively investigated in the research literature.

Air Interface Virtualization

The eNodeB is the entity responsible for accessing the radio channel and scheduling the air interface resources between the users. The eNodeB has to be virtualized so as to virtualize the LTE air interface. Virtualizing the eNodeB is similar to node virtualization. The physical resource of the node (e.g., CPU, memory, I/O devices ... etc.) are shared between multiple virtual instances. XEN [START_REF] Williams | Virtualization with Xen TM : Including XenEnterprise TM , XenServer TM , and XenExpress TM[END_REF] is a well known PC virtualization solution that insert a layer called "Hypervisor" on top of the physical hardware to schedule the resources. From that, our LTE virtualization framework follows the same principle. A hypervisor is added on top of the PHY layer of the eNodeB, it is responsible for virtualizing the eNodeB node as well as the spectrum. The proposed framework can be seen in Figure 3b.

The architecture shows the physical eNodeB virtualized into a number of virtual eNodeBs. This is achieved by the hypervisor that sits on top of the physical resources of the eNodeB. In addition, the hypervisor is responsible for scheduling the spectrum, i.e., scheduling the air interface resources (OFDMA sub-carriers) between the virtual eNodeBs running on top. In the framework architecture two new entities should be highlighted: the "Spectrum configuration and Bandwidth estimation" which is responsible for setting the spectrum the virtual eNodeB is supposed to operate in as well as estimating the required bandwidth of the operator. And the "Spectrum allocation unit" which is responsible for scheduling the spectrum among the different virtual eNodeBs. LTE uses OFDMA in the downlink, which means that the frequency band is divided into a number of sub-bands that are called Physical Resource Blocks (PRBs). A PRB is the smallest unit the LTE MAC scheduler can assign to a user. The Hypervisor schedule the PRBs between the different virtual operators, this process could be done by different mechanisms. In this paper, an auction based mechanism is used in the "Spectrum allocation unit" to auction the PRBs to the different virtual operators that bid for them. The LTE virtualization simulation model is developed using OPNET [START_REF]OPNET website[END_REF] based on the specifications. As explained earlier, the focus of the model is on the air interface virtualization and spectrum sharing between multiple virtual operators (all sharing the same eNodeB). An example scenario of the simulation model can be seen in Figure -3a price is the minimum price the Auctioneer is willing to sell the resources with, and any bid with a price lower than the reserved one will be rejected. The first scenario is configured no reserved price (i.e., R = 0). The second scenario is configured with a dynamic reserved price that is a function of the total resources demand, this is calculated as follows:

R = γ • 3 i k x i,k (9)
The rest of the configurations can be seen in Table 1.

Results and Analysis

The idea behind the simulations is to show how the uniform auctioning framework performs in a practical scenario, highlight some of the foreseen problems and how it can be solved. First, what happens if the infrastructure provider does not set any reserved price. Since the resources are homogeneous (in the perspective of the infrastructure provider) and they are soled by a uniform price determined by the lowest winner price, there is a possibility that the virtual operators try to exploit this by reducing their bidding prices in order to maximize their profit. This could be seen in Figure 4, where virtual operator 1 manipulates the price and maximizes his profit (blue curve of the figure). Since the spectrum broker (or infrastructure provider) has no reserved price set in that scenario, the virtual operator succeeds in reducing the resource price and thus increasing his profit. On the other hand, in the 2nd scenario (red curve of the figure) even though the virtual operator tries to manipulate his bidding price he is unable to increase his profit. This is because the spectrum broker sets a reserved price that the operator can not bid below. Figure 5a shows the spectrum broker (or infrastructure provider) profit. The profit decreases in the case with no reserved price due to the virtual operator's price manipulation, but when the spectrum broker (infrastructure provider) sets a reserved price he can stop the operator manipulation. Figure 5b and 5c show the average profit of virtual operator 2 and 3 respectively. The results are similar to virtual operator 1 results. The average number of PRBs (spectrum utilization) for both the spectrum broker (infrastructure provider) as well as virtual operator 1 can be seen in Figure 5d. Similar trend as before can be observed, in the scenario with no reserved price the amount of resources is the same in all cases because the virtual operator gets all of his demand but with different prices. In the scenario with a reserved price it can be seen that the overall resources granted to the virtual operator starts decreasing, this is because when the virtual operator starts manipulating the bidding price he will not be granted his demand if the price is lower than the reserved one.

Conclusion

In this paper, we discussed different market dynamics, the strategies of involved stake-holders at different hierarchical levels of telecommunication landscape, and investigated the equilibria in the upstream and downstream market. We also discussed the infrastructure resource auctioning in future wireless paradigm by focusing on both technical and theoretical aspects. We provide the technical realization of the proposed future market behavior with the state-of-theart technical solution on the granule level. We have investigated how the uniform auctioning format performs when used to trade the spectrum between different virtual operators in a virtualized LTE system environment.

  represent the maximum utility of user types k and n o,k = c n c o,k is the number of users of type k for application quality of service class c from the operator o. In order to capture the congestion level, we choose the function α as strictly decreasing function in the number of users that request services at the same operator. The number b c o,k represents the offered bandwidth to user type k for application quality of service class c, similarly b c o,k , b c o,k etc represents the minimum and maximum required bandwidth by the application quality of service class c and user type k.

Fig. 2 :

 2 Fig. 2: figure representing the valuation of the operators for different services

Fig 2 .

 2 Given such inelastic scenario, what about the operators' valuation computation? So far the valuation is the price value at the intersection of the demand perpendicular and normal negatively sloped (going down from left to right) linear demand curve. However, this does not capture the operator preference for different services. To address this issue, we introduce the operator valuation function. Thus now the operator valuation corresponds to the intersection of operator valuation function slope and the demand perpendicular. As depicted in Fig 2,we map the operator demands over the spectrum trade market. The operator's the valuation function, given by Equation πi,k (x) =x i,k γ k

Algorithm 1

 1 Calculate p and a i Given the available spectrum C, clock index t = 0, the auctioneer (LTE virtualization framework) sets the reservation price R. Set t = 0 // Bids submissions start Ensure: di ≥ R // Ensure that bids are equal or above the Reserve price (R) while t = tmax do B ← di∀i ∈ N // Update the bid vector B for every income bid di end while Determine the set of winning bids LIST B ← di // The set of highest bids of B that do not violate the capacity constraint i∈N ai ≤ C SORT LIST B in ascending order. p← LIST B.di(π) // select the price of lowest winning bidder as stop-out price. while C = 0 &&LIST B = empty do Ensure: di ∈ B if C > di(X) then B.Bi(a) = Xi else B.Bi(a) = Cr // Cr is the residual capacity end if end while

Fig. 3 :

 3 Fig. 3: Figure representing the OPNET based LTE eNodeB virtualization framework

Fig. 4 :

 4 Fig.4: Virtual Operator 1 profit and relative profit gain

Fig. 5 :

 5 Fig. 5: Figure presenting the profit and relative profit results and virtual operator resources

Table 1 :

 1 Simulation configurations

	6 Simulation Model and Results Analysis
	Parameter	Assumption
	Number of virtual operators	4 virtual operators with circular cells of 375 meters radius
	Total Number of PRBs (Spectrum) 75 PRBs, i.e., about 15 MHz
	Mobility model	Random Way Point (RWP) with vehicular speed (120 Km/h)
	Number of active users	VO1: 16 GBR (video users) and 4 non-GBR (FTP users)
	per virtual operator	VO2: 10 GBR (video users) and 10 non-GBR (FTP users)
		VO3: 4 GBR (video users) and 16 non-GBR (FTP users)
	VO1 price valuation	γ1=2 and γ2=(2, 4, 6, 8, 10 and 20)
	VO2 price valuation	γ1=2 and γ2=4
	VO3 price valuation	γ1=2 and γ2=2
	Video traffic model	24 frames per second with frame size = 1562 Bytes
		Video call duration = Exponential with 60 seconds mean
		Inter video call time = Poison with 30 seconds mean
	FTP traffic model	FTP file size = 8M bytes
		Inter request time = uniform between 50 and 75 seconds
	Auctioning parameters	Auction done every 20 seconds with γ = 0.25
	Simulation runtime	1000 seconds