# Dynamic Spectrum Trade and Game-Theory Based Network Selection in LTE Virtualization Using Uniform Auctioning

Manzoor Ahmed Khan, Yasir Zaki

► To cite this version:

Manzoor Ahmed Khan, Yasir Zaki. Dynamic Spectrum Trade and Game-Theory Based Network Selection in LTE Virtualization Using Uniform Auctioning. 9th Wired/Wireless Internet Communications (WWIC), Jun 2011, Vilanova i la Geltrú, Spain. pp.39-55, 10.1007/978-3-642-21560-5_4. hal-01583632

HAL Id: hal-01583632

https://inria.hal.science/hal-01583632v1

Submitted on 7 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Dynamic Spectrum Trade and Game-theory Based Network Selection in
LTE Virtualization using Uniform Auctioning

Manzoor Ahmed Khan¹ and Yasir Zaki²

¹ DAI-Labor/Technical University, Berlin, Germany
manzoor-ahmed.khan@dai-labor.de
²ComNets, University of Bremen, Germany

**Abstract.** 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.

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

# 1 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.

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 op-

<figure><img src="image_2.png" /><figcaption>Fig. 1: Hierarchical position of telecommunication stakeholders and their objectives</figcaption></figure>

erators’ 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 user-centric 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).

## 2 Related Work

The concept of DSA first came up in the DARPA XG program [1], 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 [2], 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 [3] 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, [4] 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 [5] 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 [6], 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.

### 2.1 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 [9] [10] in the United States, AKARI [11] in Asia and 4WARD [12] 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 [13] 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 [14], 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.

# 3 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 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 into 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 an interdependent multi-level system.

## 3.1 Network Operator Resource Allocation Problem

Each operator seeks to optimize its total revenue $R_o := \sum_{k,c} \pi(o, k, c)n_{o,k}^c$ subject to the QoS constraints. For the accepted users, a bandwidth allocation between the users is established. Then, each operator $o$ designs the function $\pi$ for each type $k$ and each service class $c$.

## 3.2 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, \forall i \in K$. The expression of $U_i(.)$ is given as follows:
$$ U_{i,k,c}(o, n) := u_{i,o} \left( \frac{b_{o,k}^c}{n_{o,k}} \right) \prod_{l \in L} (\nu_{il,o}(k, c, n))^{w_{il}} \pi(o, k, c) + \sum_{j \in J} \omega_j v_{ij,o}(k, c, n, \psi), \quad (1) $$

The user utility function (equation-1) has four components:

- The term $u_{i,o} \left( \frac{b_{o,k}^c}{n_{o,k}} \right)$ is the function of network state $n = (n_{o,k}^c)_{o,k,c}$ 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.

- $\prod_{l \in L} (\nu_{il,o}(k, c, n))^{w_{il}}$ is the weighted multiplicative approach for dependent associated QoE attributes.

- $\sum_{j \in J} \omega_j v_{ij,o}(k, c, n, \psi)$ is the weighted sum of different independent QoE attributes.

- $\pi(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 \in \Theta$, where $\Theta$ is the finite set of user types. Each operator $o$ chooses its price vector $\pi_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 [15]

**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) := \begin{cases} 0 & \text{if } \frac{b_{o,k}^c}{n_{o,k}} \le \underline{b}_{o,k}^c \\ \alpha_k(n_{o,k}) \frac{1 - e^{-\beta(b_{o,k}^c - \underline{b}_{o,k}^c)}}{1 - e^{-\beta(b_{o,k}^c - \underline{b}_{o,k}^c)}} & \text{if } \underline{b}_{o,k}^c \le b_{o,k}^c \le \bar{b}_{o,k}^c \\ \alpha_k(n_{o,k}) \frac{1 - e^{-\beta(b_{o,k}^c - \bar{b}_{o,k}^c)}}{1 - e^{-\beta(b_{o,k}^c - \bar{b}_{o,k}^c)}} & \text{if } \bar{b}_{o,k}^c \le b_{o,k}^c \le \tilde{b}_{o,k}^c \\ \alpha_k(n_{o,k}) \frac{1 - e^{-\beta(b_{o,k}^c - \tilde{b}_{o,k}^c)}}{1 - e^{-\beta(b_{o,k}^c - \tilde{b}_{o,k}^c)}} & \text{if } \tilde{b}_{o,k}^c \le b_{o,k}^c \le \hat{b}_{o,k}^c \\ \alpha_k(n_{o,k}) & \text{if } b_{o,k}^c \ge \hat{b}_{o,k}^c \end{cases} \quad (2) $$

where $\alpha_k(n_{o,k})$, represent the maximum utility of user types $k$ and $n_{o,k} = \sum_c n_{o,k}^c$ 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 $\alpha$ as strictly decreasing function in the number of users that request services at the same operator. The number $b_{o,k}^c$ represents the offered bandwidth to user type $k$ for application quality of service class $c$, similarly $\underline{b}_{o,k}^c$, $\bar{b}_{o,k}^c$ etc represents the minimum and maximum required bandwidth by the application quality of service class $c$ and user type $k$.

Now, we examine the outcome of the network selection in a competitive manner at the user level with the utility $t_i(o, n)$. 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.

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 [16]. 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 $\pi$ 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 [16, 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 [18] 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 [18], 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 - \epsilon)$ if the performance is greater or try another strategy with probability $\epsilon$. All this is done for a well-chosen $\epsilon \in (0, 1)$.

**Proposition 2** *The interactive trial and error learning algorithm implements a pure Nash equilibrium of the user-centric game with high proportion of times.*

*Proof.* We verify that the conditions in [18] are satisfied. First, the user-centric game is a finite game for any fixed pricing function $\pi$. 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 [18] 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 [19] 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 [19].

**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 $\pi$, 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 $\pi$. For more details on the associated dependent and independent utilities refer to [15].
## 4 Upstream Market

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 [20]. In a uniform-price auction, small bidders can simply bid their valuations and be assured of paying only the market-clearing price [21]. The fact highlighted in [22] 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 use the uniform price auctioning for spectrum trade. More on auction clearing algorithms can be found in [23].

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 strengthened 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 $\tilde{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 non-increasing 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 $\tilde{v}_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 $\tilde{v}_{i,k}$ such that $\tilde{v}_{i,k} \neq \tilde{v}_{i,k} \forall k \neq 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 \in N$ is non-increasing function $X_i : [0, \infty) \rightarrow [0, X_{max}]$, and the his private valuation $\tilde{v}_{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}, \tilde{v}_{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 seen 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 influenced by its simplicity and wide presence in the literature.

$$ \tilde{\pi}(x) := -\zeta x + \zeta, \quad (3) $$

where $\zeta$ and $\zeta$ are positives, the negative gradient represents the sensitivity of market towards the price, and $\zeta$ 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 Fig 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

<figure><img src="image_3.png" /><figcaption>Fig. 2: figure representing the valuation of the operators for different services</figcaption></figure>
trade market. The operator's the valuation function, given by Equation 4.

$$ \tilde{\pi}_{i,k}(x) = \frac{x_{i,k}}{\gamma_k} \qquad (4) $$

where $\gamma_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 $\gamma_k$ takes comparatively lower value than that of lower importance service. $\gamma_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., $\gamma(k, \mathcal{N} - 1)$. Although one may come up with any suitable $\gamma(.)$ function, in this work, we simply represent it by a real-value exposed to simple constraint of $\gamma_{k,i} \neq \gamma_{\tilde{k},i} \forall k \neq \tilde{k}$ and $\gamma_{k,i} \neq \gamma_{k,\tilde{i}} \forall i \neq \tilde{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 $\gamma_{i,k}$ is directly translated into $\tilde{\pi}_{i,k}$ i.e., based on service types and downstream market demands the operator reflects its valuation as $\tilde{\pi}_{i,k}$ such that $\gamma_{k,u} = \tilde{\pi}_{i,k}$. Intuitively the false valuation $\tilde{\pi}_{i,k}$ is given by $\gamma_{k,u} \neq \tilde{\pi}_{i,k}$.

Let $f$ be the mapping function that maps the downstream demands $Y$ over the upstream demand function $X$, such that $f(Y) \mapsto 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, \pi)$.

**Allocation Rule** Given the uniform price auctioning format, let $\bar{d}$ represents the highest bid, and $p$ represents the stop out price;

$$ a_i(X_i, d_i) := \begin{cases} X_i & \text{if } d_{i,k} = \bar{d} \land X_i \le \tilde{C} \land d_{i,k} > p \\ \min\{X_i, \tilde{C} - \sum_{\tilde{d}_{-i} \in B, \tilde{d}_{-i} \setminus d_i} X_{\tilde{d}_{-i}}\} & \text{otherwise} \end{cases} \qquad (5) $$

As can be seen from Equation 5 the 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 $\tilde{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 \in \mathcal{N}$ and the stop-out price be $p$ as:

$$ u_i(a, p) := (\gamma_k - p)x_k + (\gamma_{\tilde{k}} - p)x_{\tilde{k}} \qquad (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(\sum_{i \in \mathcal{N}} X_i, p) := \sum_{\tilde{d} \in B} a_{\tilde{d}} \times (p - \frac{\sqrt{x}}{\lambda}) \qquad (7) $$
where $\sqrt{\frac{x}{\lambda}}$ represents the incurring cost of auctioneer, $\lambda$ is the 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 detailed 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}(\sum_{i \in 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 \left\{ p | \sum_{i \in N} X_i \ge K \right\}$. We also present the algorithm that is implemented by the auctioneer to take the decision over resource allocation and stop-out price as follows:

**Algorithm 1 Calculate $p$ and $a_i$**

Given the available spectrum $\tilde{C}$, clock index $t = 0$, the auctioneer (LTE virtualization framework) sets the reservation price $R$. Set $t = 0$ // Bids submissions start

**Ensure:** $d_i \ge R$ // Ensure that bids are equal or above the Reserve price (R)

**while** $t \ne t_{max}$ **do**

B $\leftarrow d_i \forall i \in N$ // Update the bid vector B for every income bid $d_i$

**end while**

Determine the set of winning bids $LIST\overline{B} \leftarrow d_i$ // The set of highest bids of B that do not violate the capacity constraint

$$ \sum_{i \in N} a_i \le \tilde{C} $$

SORT $LIST\overline{B}$ in ascending order.

p $\leftarrow LIST\overline{B} \cdot d_i(\tilde{\pi})$ // select the price of lowest winning bidder as stop-out price.

**while** $\tilde{C} \ne 0$ $\&$ $LIST\overline{B} \ne$ empty **do**

**Ensure:** $d_i \in \overline{B}$

if $\tilde{C} > d_i(X)$ then

$$ \overline{B} \cdot B_i(a) = X_i $$

else

$$ \overline{B} \cdot B_i(a) = \tilde{C}_r \quad \text{if } \tilde{C}_r \text{ is the residual capacity} $$

**end if**

**end while**

## 4.1 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,t_1} := \gamma_{i,t_1,k} \qquad (8) $$

$$ \text{and } d_{i,t_2} := \min\{R, \gamma_{i,t_2,\tilde{k}}\}. $$

*Proof.* Proof omitted due to space restrictions.

## 4.2 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 $\delta t$ expires.
# 5 Dynamic Spectrum Trade Realization Framework

In this section, we present 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.

## 5.1 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 [24] 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.

# 6 Simulation Model and Results Analysis

<table><caption>Table 1: Simulation configurations</caption><thead><tr><th>Parameter</th><th>Assumption</th></tr></thead><tbody><tr><td>Number of virtual operators</td><td>4 virtual operators with circular cells of 375 meters radius</td></tr><tr><td>Total Number of PRBs (Spectrum)</td><td>75 PRBs, i.e., about 15 MHz</td></tr><tr><td>Mobility model</td><td>Random Way Point (RWP) with vehicular speed (120 Km/h)</td></tr><tr><td>Number of active users per virtual operator</td><td>VO1: 16 GBR (video users) and 4 non-GBR (FTP users)<br>VO2: 10 GBR (video users) and 10 non-GBR (FTP users)<br>VO3: 4 GBR (video users) and 16 non-GBR (FTP users)</td></tr><tr><td>VO1 price valuation</td><td>γ1=2 and γ2=(2, 4, 6, 8, 10 and 20)</td></tr><tr><td>VO2 price valuation</td><td>γ1=2 and γ2=4</td></tr><tr><td>VO3 price valuation</td><td>γ1=2 and γ2=2</td></tr><tr><td>Video traffic model</td><td>24 frames per second with frame size = 1562 Bytes<br>Video call duration = Exponential with 60 seconds mean<br>Inter video call time = Poison with 30 seconds mean</td></tr><tr><td>FTP traffic model</td><td>FTP file size = 8M bytes<br>Inter request time = uniform between 50 and 75 seconds</td></tr><tr><td>Auctioning parameters</td><td>Auction done every 20 seconds with γ = 0.25</td></tr><tr><td>Simulation runtime</td><td>1000 seconds</td></tr></tbody></table>
The LTE virtualization simulation model is developed using OPNET [25] based on the 3GPP 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. Two scenarios are investigated based on the Auctioneer's (Infrastructure Provider) reserved price "R". The reserved

<figure><img src="image_4.png" /><figcaption>Fig. 3: Figure representing the OPNET based LTE eNodeB virtualization framework</figcaption></figure>

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 = \gamma \cdot \sqrt[3]{\sum_{i} \sum_{k} x_{i,k}} \qquad (9)$$

The rest of the configurations can be seen in Table 1.

## 6.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

<figure><img src="image_5.png" /><figcaption>Fig. 4: Virtual Operator 1 profit and relative profit gain</figcaption></figure>
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.

<figure><img src="image_6.png" /><figcaption>Fig. 5: Figure presenting the profit and relative profit results and virtual operator resources</figcaption></figure>

# 7 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-the-art 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.

# References

1. DARPA Next Generation Communication Program. http://www.sharedspectrum.com/resources/darpa-next-generation-communications-program/.

2. Milind M. Buddhikot, Paul Kolodzy, Scott Miller, Kevin Ryan, and Jason Evans. Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access. In *in IEEE WoWMoM05*, pages 78–85, 2005.
3. Virgilio Rodriguez, Klaus Moessner, and Rahim Tafazolli. Market-driven dynamic spectrum allocation: Optimal end-user pricing and admission control for cdma. In *In the proceedings of IST Mobile and Wireless Communication Summit*, 2005.

4. Virgilio Rodriguez, Klaus Moessner, and Rahim Tafazolli. Auction driven dynamic spectrum allocation: optimal bidding, pricing and service priorities for multi-rate, multi-class cdma. In *In the proceedings of 16th Internation Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)*, pages 1850–1854, 2005.

5. Kevin Ryan, Elias Aravantinos, and Milind M. Buddhikot. A new pricing model for next generation spectrum access. In *Proceedings of the first international workshop on Technology and policy for accessing spectrum*, TAPAS '06, New York, NY, USA, 2006. ACM.

6. Sorabh G, Chiranjeeb Buragohain, Lili Cao, Haitao Zheng, and Subhash Suri. A general framework for wireless spectrum.

7. "IST-DRIVE Project". http://www.ist-drive.org.

8. http://smartradioview.blogspot.com/2007/07/overdrive-project homepage.html. Link last accessed on febraury 24, 2011.

9. A. Bavier, M. Bowman, D. Culler, B. Chun, S. Karlin, S. Muir, L. Peterson, T. Roscoe, T. Spalink, and M. Wawrzoniak. Operating system support for planetary-scale network services, March 2004.

10. S. Paul and S. Seshan. Geni technical document on wireless virtualization, September 2006.

11. AKARI architecture conceptual design for new generation network.

12. Stephan Bauck and Carmelita Görg. Virtualisation as a co-existence tool in a future internet. In *ICT Mobile Summit - 4WARD Workshop*, Stockholm, Sweden, June 2008.

13. Yasir Zaki, Liang Zhao, Andreas Timm-Giel, and Carmelita Görg. A Novel LTE Wireless Virtualization Framework. In *Second International ICST Conference on Mobile Networks And Management (Monami)*, pages 1–13 CD publication), Santander, Spain, September 2010.

14. Yasir Zaki, Liang Zhao, Andreas Timm-Giel, and Carmelita Görg. LTE Wireless Virtualization and Spectrum Management. In *Third Joint IFIP Wireless and Mobile Networking Conference (WMNC)*, Budapest, Hungary, October 2010.

15. Manzoor Ahmed Khan and Umar Toseef. User utility function as quality of experience (qoe). In *Proceedings of the ICN'11*, pages 99–104, 2011.

16. Robert W. Rosenthal. A class of games possessing pure-strategy nash equilibria. *International Journal of Game Theory*, DOI: 10.1007/BF01737559, 2:65–67, 1973.

17. D. Monderer and L. S. Shapley. Games and economic behavior. 14:124–143, 1996.

18. H. P. Young. Learning by trial and error. *Games and Economic Behavior*, 65:626–643, March 2009.

19. H. Tembine. Distributed learning in dynamic robust games: dynamics, algorithms and network applications. *Lecture notes*, 2010.

20. Peter Cramton. The efficiency of the fcc spectrum auctions. In *Journal of Law and Economics*, volume 41, October 1998.

21. Spectrum auctions. Auction design issues for spectrum awards market analysis ltd.

22. Richard French. Spectrum auctions 101. In *the Journal of Public Sector Management*, 2008.

23. Tuomas Sandholm and Subhash Suri. Market clearability. In *In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence*, pages 1145–1151, 2001.

24. David E. Williams and Juan Garcia. *Virtualization with Xen™: Including XenEnterprise™, XenServer™, and XenExpress™*. SYNGRESS, 2007.

25. OPNET website. http://www.opnet.com.