Wireless Pers Commun (2013) 69:745–770 DOI 10.1007/s11277-012-0610-x

A Radio Resource Management Framework for Multi-User Multi-Cell OFDMA Networks Based on Game Theory Ioannis N. Stiakogiannakis · Dimitra I. Kaklamani

Published online: 10 April 2012 © Springer Science+Business Media, LLC. 2012

Abstract This work proposes a radio resource management framework employing game theoretic concepts for orthogonal frequency division multiple access, the most prevalent multiple access technique for the next generation wireless networks. The subcarrier allocation problem is encountered as a combinatorial auction, where the base station auctions the subcarriers and the users bid for and buy bundles of subcarriers, aiming at minimising their required transmit power. Subsequently, each allocated subcarrier is loaded with a number of bits, decided by each user independently, and the power control process is set up as a non-cooperative game. Each user responds to the interference sensed in his environment and, through a best responses process, the game converges to the unique, Pareto optimal, Nash equilibrium. In order to guarantee convergence, a limit is imposed to the maximum modulation level for each subcarrier. Simulation results show that the auction algorithm follows closely the performance of the optimal algorithm, whereas it is of lower computational complexity and requires less feedback information. Similarly, the proposed distributed bit loading and power control scheme achieves lower transmit power per offered bit rate unit. However, the distributed nature of the algorithm results in lower total offered bit rate, because of the partial knowledge and exploitation of channel state information. Keywords OFDMA · Radio resource management · Margin adaptive · Subcarrier allocation · Power control · Game theory · Combinatorial auctions

Financial support by National Technical University of Athens under the program PEVE 2009, grand no 65177200, is gratefully acknowledged. I. N. Stiakogiannakis (B) · D. I. Kaklamani School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece e-mail: [email protected] D. I. Kaklamani e-mail: [email protected]

123

746

I. N. Stiakogiannakis, D. I. Kaklamani

1 Introduction The development of field-programmable gate array (FPGA) technology and the implementation of fast fourier transform (FFT) on FPGAs made feasible the cost-effective employment of orthogonal frequency division multiplexing (OFDM). The adoption of OFDM and the corresponding multiple access technique, orthogonal frequency division multiple access (OFDMA), from various standardisation bodies, including IEEE [1] and 3GPP [2], launched an enormous research effort on issues related to both PHY and MAC layers of OFDM(A). This effort has provided with some seminal works, including [3–5], contributing to the establishment of radio resource management (RRM) for OFDMA networks as a standalone research area and a number of fruitful works appeared during the next few years. In [6], a comprehensive survey on OFDMA RRM, it is noted that the RRM problem can be formulated as either margin adaptive (MA), where the objective is to minimise the total transmit power, or rate adaptive (RA), where the objective is to maximise the sum capacity of the network. At the same time, a new analytical model is employed in telecommunications research, the mathematically mature game theory. Game theory aims to model situations where a number of entities interact, by means of following certain strategies, in order to maximise their own profit. In telecommunications, game theory has been employed to tackle problems such as power control, routing, call admission control, etc [7,8]. Game theory encompasses a wide variety of games, among them cooperative and non-cooperative games, repeated games, auctions, and useful concepts such as Nash equilibrium, Stackelberg equilibrium, truthfulness. Each of these game types and each of these concepts are appropriate for describing different types of interaction, in different kinds of networks [9,10]. In this work, we focus on the MA formulation of the downlink OFDMA RRM problem, considering a multi-user multi-cell OFDMA network. Specifically, in the following, a subcarrier allocation algorithm based on combinatorial auctions is presented, along with a bit loading and power control scheme based on non-cooperative games. 1.1 Related Work In the past few years, several research works have proposed the employment of auctions to tackle the subcarrier allocation problem. In [11], various schemes are presented, based on per-subcarrier auctions addressing both single-cell and multi-cell resource allocation algorithms for the uplink OFDMA RRM problem. In [12], the employment of Dutch auctions is proposed for the downlink OFDMA RRM problem. The base station (BS) sets up simultaneous Dutch auctions, one per subcarrier. For each subcarrier, a starting price is announced and, as time passes, this price is reduced according to a clock. Each user observes his “best” subcarrier and, when he decides that its price is low enough, based on his valuation on the specific subcarrier, he bids for and buys it at its current price. In [13–15], the RA formulation of OFDMA RRM is tackled and a subcarrier allocation algorithm is proposed based on per-subcarrier auctions. The users’ bidding and valuation functions are defined, so as to achieve a specific goal, such as system throughput maximisation or fairness maximisation. The users bid for one subcarrier at a time and the user with the highest bid wins his requested subcarrier. In [16], the subcarrier allocation problem is tackled in conjunction with the scheduling problem. A multi-unit auction is proposed, which consists of a multi-carrier proportional fairness algorithm as allocation method and the Vickrey–Clarke–Groves payment scheme. To the best of authors’ knowledge, it is only in [17] that the employment of combinatorial

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

747

auctions for the downlink OFDMA subcarrier allocation problem is introduced. Therein, a combinatorial clock auction is proposed, according to which the BS announces the price for each subcarrier and the users react to these prices by means of submitting the bundle of subcarriers willing to buy. If there is excessive demand for any subcarrier, the BS increases the price for this subcarrier and the users submit their new bundle of subcarriers. The process is terminated when there is no excessive demand for any subcarrier. Since power control is a typical field where game theory has been applied, in the following, the presentation is limited to recent advancements. In [18], a multi-user network is examined, with parallel Gaussian channels, where each user tries to achieve a specific bit rate with the minimum transmit power. The analysis is based on the notion of generalised Nash equilibrium, the existence and the uniqueness under certain circumstances of which are proved. Two distributed algorithms are presented, a sequential and a simultaneous iterative water filling algorithm, which converge to the generalised Nash equilibrium. [19] refers to the downlink of an OFDMA network with fractional frequency reuse, with a protected and a shared frequency band. The RA problem is formulated as a non-cooperative game, which is proved to have a unique Nash equilibrium under certain circumstances. A power control algorithm is presented, which is proved to be incentive compatible. In [20,21], the power control problem is addressed from a different point of view. In [20] at first, it is supposed that at least one user is able to collect information about the strategies and channel state information (CSI) of other users. Hence, a Stackelberg game is constructed, which is proved to lead to a more efficient equilibrium compared to the typical modelling of the game with only myopic users. In [21], the notion of conjectural equilibrium is introduced and it is shown that the leader does not have to have a priori information on the strategies and the CSI of the followers but this information can be acquired as the game evolves. It is proved that the game converges to an equilibrium comparable to the previous approach of Stackelberg equilibrium and, furthermore, that the Nash and Stackelberg equilibria of previous approaches are special cases of the conjectural equilibrium. 1.2 Paper Contributions and Outline Contributing to the previous research efforts, the present work proposes a novel combinatorial auctions algorithm to tackle the issue of subcarrier allocation. Contrary to the majority of previous approaches, the scheme of combinatorial auctions is employed, rather than per subcarrier auctions, in a completely different setup compared to [17]. This algorithm is an appealing alternative to the optimal algorithm for three reasons. Firstly, the proposed algorithm closely follows the performance of the optimal one, as measured by all the figures of merit examined. Secondly, it is of lower computational complexity, which results in faster decision making. Thirdly, due to its distributed nature, it causes less feedback overhead on the uplink. Furthermore, a bit loading and power control algorithm is proposed. The proposed scheme is based on non-cooperative games and it is proved to converge to the Pareto optimal Nash equilibrium if certain precautions are taken. Contrary to previous research efforts, the usage of infinity norm is proposed, which is accompanied with a proper channel probing scheme, achieving that way to guarantee the convergence while maintaining the distributed nature of the algorithm. The proposed scheme is proved to be of lower computational complexity, while at the same time it eliminates the feedback requirements. One of the main advantages of this work is the fact that the efficiency and suitability of the proposed schemes are evaluated in the frame of a multi-cell OFDMA network based on

123

748

I. N. Stiakogiannakis, D. I. Kaklamani

typical figures of merit for wireless networks. As a matter of fact, a series of simulations measures the performance of the network under the employment of the proposed algorithms based on offered bit rate, transmit power, and several other metrics. The rest of this work is organised as follows. Section 2 presents a complete RRM framework, addressing the MA formulation for downlink multi-user multi-cell OFDMA. Thence, in Sect. 3, a subcarrier allocation algorithm based on combinatorial auctions is presented. Section 4 presents a non-cooperative power control game. The existence under certain circumstances of a unique Nash equilibrium is proved and a distributed bit loading and power control algorithm is built upon this game. Section 5 includes the simulation results and the corresponding analysis on them. Finally, the presented work is summarised and the conclusions are drawn in Sect. 6. 2 Radio Resource Management Framework for Multi-User Multi-Cell OFDMA Networks 2.1 Problem Definition The OFDMA system under consideration encompasses K BSs (k ∈ K = {1, . . . , K }), with total available power PBmax S each, and U users (u ∈ U = {1, . . . , U }). Each user u requires bit rate Ru under bit error rate (BER) Peu . The available bandwidth BW is divided into N OFDM subcarriers (n ∈ N = {1, . . . , N }) and each subcarrier occupies bandwidth  f = BW/N . The MA formulation for the downlink RRM problem is based on the definition of three allocation matrices: – Subcarrier allocation matrix C = [Cu,n,k ]. Cu,n,k = 1 (Cu,n,k = 0) indicates that subcarrier n of BS k is (not) allocated to user u. – Bit loading matrix B = [bn,k ]. bn,k ∈ {0, bmin , . . . , bmax } indicates the number of bits that the BS k loads on subcarrier n where bmin (bmax ) stands for the minimum (maximum) modulation level that can be employed. In the scope of this work, it is assumed that the network employs exclusively square M-QAM (quadrature amplitude modulation) modulations, and, as a result, bn,k is an even integer. – Power allocation matrix P = [Pn,k ]. Pn,k ∈ R+ indicates the power that the BS k transmits on subcarrier n. As stated earlier, the MA formulation aims at minimising the total transmit power of the network, while fulfilling the requirements of individual users. The corresponding optimisation problem is defined by (1)–(5). minimise

N K  

Pn,k

(1)

k=1 n=1

subject to Ru ≤ Ruo =  f

K  N 

Cu,n,k bn,k , ∀u ∈ U

k=1 n=1

Peu ≥ Peuo = 4Cu,n,k

⎛  ⎜ Q ⎝ 

(2) ⎞

G u,n,k Pn,k 3 ⎟ ⎠ K 2 2bn,k − 1 m=1 G u,n,m Pn,m + σ m =k

∀u ∈ U , ∀n ∈ N , ∀k ∈ K

123

(3)

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

t PBmax S ≥ Pk =

N 

Pn,k , ∀k ∈ K

749

(4)

n=1 U 

Cu,n,k ≤ 1, ∀n ∈ N , ∀k ∈ K

(5)

u=1

where Ruo stands for the offered bit rate, Peuo is the measured BER. G u,n,k is the channel gain for subcarrier n between the BS k and user u, including transmit and receive antenna gains, path losses, shadowing and fading effects, and σ 2 is the received noise power in the bandwidth of subcarrier n. Since the network employs exclusively square M-QAM modulations, it has been proven [22] that the BER can be closely approximated by (3), where Q (·) is the Q-function. Equation (3) is the so-called link to system-level interface [23] employed herein. Finally, Pkt is the total transmit power of the BS k. It must be noted that each BS allocates each subcarrier to a unique user, as constraint (5) implies, a practice that has been proved optimal for any adaptive bit loading scheme [24]. 2.2 RRM Framework The problem (1)–(5) is a non-linear, non-convex, three-dimensional optimisation problem that belongs to the NP-hard complexity class [25]. In order to achieve a solution within reasonable complexity, following the established approach in the research field [4,5,25], the initial problem is tackled as a series of sub-problems, which are solved sequentially, concluding thus to a sub-optimal solution. Hence, the RRM framework has to define a solution for the BS selection problem, the subcarrier allocation problem and, finally, the bit loading and power control problem [26]. Figure 1 depicts the flowchart of the simulation process employed herein in order to evaluate the performance of the proposed RRM framework.Up to Vklim new users ask for admittance for each BS k ∈ K. It must be noticed that, when a user is denied admittance, the network returns to the previous steady state and the allocation matrices remain intact. On the contrary, when the user is admitted, the allocation matrices are updated according to the decisions of the RRM framework. The components and the corresponding nomenclature are explained in the following. 2.2.1 Base Station Selection When a new user, denoted as u, ¯ requests access to the network resources, the very first issue to tackle is the assignment of a BS from the set K. Towards this direction, diverse solutions have been proposed and evaluated. Among them, [25] proposes a selection criterion based on normalised channel to interference plus noise ratio (nCINR), whereas [27,28] employ a criterion based on average (over all subcarriers) channel gain. In the approach adopted herein, as it has been noticed that the Base Station Selection process plays a minor role on system performance, the new user u¯ is served by BS k¯ if he lies in the geographical area served by BS ¯ As a result, the terms BS and cell are used interchangeably. For notational convenience, k. ¯ including the new user u, the set of users served by cell k, ¯ is denoted as Uk¯ with Uk¯ elements. 2.2.2 Subcarrier Allocation The second step on the RRM process is the subcarrier allocation. In multi-carrier networks, as OFDMA, the problem of subcarrier allocation is usually divided into two separate successive

123

750

Fig. 1 Simulation process flowchart

123

I. N. Stiakogiannakis, D. I. Kaklamani

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

751

problems [4], where the first one deals with the definition of the number of subcarriers to be allocated to each user, and the second one performs the subcarrier allocation, based on the outcome of the former. Number of Subcarriers Definition The bandwidth assignment based on SNR (BABS) algorithm of [4], extended to the multi-cell scenario, is employed herein. In brief, the number of  Ru subcarriers su for each user u in cell k¯ is initialised with the minimum one sumin = bmax f . ¯ ie. u∈U sumin > N , the new If there are not enough subcarriers to serve the users of cell k, k¯ user u¯ is rejected and the network returns to the previous steady state. For the distribution of the remaining subcarriers, if any, another subcarrier will be allocated to the user uˆ that will gain the maximum power reduction, formally,   uˆ = arg max P¯u,k¯ (su ) − P¯u,k¯ (su + 1) (6) u∈Uk¯

where, Ru

2 su  f − 1 P¯u,k¯ (su ) = su T¯u,k¯

(7)

is a rough estimation on the total required power for user u. The average nCINR T¯u,k¯ is N Tu,n,k¯ , whereas the nCINR Tu,n,k is defined as, derived as T¯u,k¯ = N1 n=1 G u,n,k

Tu,n,k = K m=1 m =k

G u,n,m Pn,m

+ σ2

1 u

(8)

u is the SNR gap which defines the gap between a practical modulation scheme and the channel capacity, given by [22],    Peu 2 1 Q −1 u = (9) 3 4 where Q −1 (·) is the inverse Q-function. Although (8) implies so, it is not necessary for the user to be able to distinguish the sources of interference in order to calculate Tu,n,k but rather K G u,n,m Pn,m + σ 2 as a whole. calculate the interference m=1 m=k

The process is ended when the subcarriers are depleted  or all users have achieved the maximum number of subcarriers needed, sumax = bminRu f . Subcarrier Allocation Algorithm Given su , the allocation problem can be seen as a matching problem. The “cost” for user u to be allocated subcarrier n is defined as the average required power to be transmitted on this subcarrier, formally, Ru

P¯u,n,k¯

2 su  f − 1 = Tu,n,k¯

(10)

Based on this definition, a cost matrix can be constructed of dimensions u∈U ¯ su × N , k where each user is represented by su rows whereas columns represent the subcarriers. This transformation of the allocation problem to the matching problem allows  to employ the optimal Hungarian algorithm [29,30], with computational complexity O N 3 , which achieves

123

752

I. N. Stiakogiannakis, D. I. Kaklamani

to minimise the sum average required power. If Cu ⊆ N is the set of subcarriers allocated to user u (n ∈ Cu ⇔ Cu,n,k¯ = 1), the Hungarian algorithm solves optimally the problem, minimise P¯k¯ =

 

P¯u,n,k¯

(11)

u∈Uk¯ n∈Cu

subject to |Cu | = su

(12)

The subcarrier allocation algorithm proposed by this work is presented in Sect. 3. 2.2.3 Bit Loading and Power Control The bit loading process is usually performed in conjunction with the power control process, since the power transmitted on a subcarrier depends directly on the bits per symbol to be loaded and vice-versa, under a BER constraint. In [5], a greedy bit loading and power control process is proposed, based on a completely centralised scheme. This algorithm searches exhaustively among the subcarriers allocated to each user and increases the modulation level of subcarrier nˆ that leads to the smallest power increment, until the requested bit rate is reached. Taking into consideration the fact that in a multi-cell network the transmit power from a BS on a subcarrier interferes to the users served by other BSs on the same subcarrier, specific precautions must be taken in order to guarantee the BER of all users using the specific subcarrier network-wide. As a result, the increment on transmit power is calculated, considering all the co-channel BSs. In the following, it is assumed that there are κ ≤ K co-channel users/BSs on subcarrier n. For notational convenience, the co-channel users are enumerated as u 1 , . . . , u κ , and their serving BSs are denoted as k1 , . . . , kκ , with an one-to-one correspondence (index i ∈ In = {1, . . . , κ}). The subcarrier nˆ is derived as,  κ  κ       nˆ = arg min Pn,ki bn,k¯ + 2 − Pn,ki bn,k¯ (13) n∈Cu

i=1

i=1





The derivation of the transmit power Pn,ki bn,k¯ is explained in the following. Since only square M-QAM modulations are considered, bn,k¯ increases in step of 2 bits per symbol. In order for the network to guarantee the requested BER of the users, the received signal to interference plus noise ratio (SINR) on each subcarrier n must be higher than a SINR threshold, imposed by the BER requirements. Formally, κ

j=1 j=i

G u i ,n,ki Pn,ki ≥ γu i ,n,ki , ∀n ∈ N , ∀i ∈ In G u i ,n,k j Pn,k j + σ 2

(14)

where γu i ,n,ki is the SINR threshold, imposed by the requested BER and the modulation scheme, derived as,   γu i ,n,ki = u i 2bn,ki − 1 (15) As the aim is the minimisation of transmit power, it is adequate to ensure that (14) is satisfied with equality for all co-channel users. The transmit power of these users is mutually

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

753

dependent and, by collecting the κ equations, the following system of linear equations is built-up, (I − DF) P = v

(16)

where, I = κ × κ identity matrix   D = diag γu 1 ,n,k1 , . . . , γu i ,n,ki , . . . , γu κ ,n,kκ ⎧ ⎨0 if i = j,   F = Fi, j 1≤i, j≤κ , where Fi, j = G ui ,n,k j ⎩G if i  = j u i ,n,ki T  P = Pn,k1 , . . . , Pn,ki , . . . , Pn,kκ   γu 1 ,n,k1 γu i ,n,ki γu κ ,n,kκ T 2 v= ,..., ,..., σ G u 1 ,n,k1 G u i ,n,ki G u κ ,n,kκ   The aforementioned transmit power Pn,ki bn,k¯ is derived by solving (16). By PerronFrobenius theorem [31], the system of linear equations (16) has a unique, non-negative solution, if and only if, ρ (DF) < 1, where ρ (DF) stands for the spectral radius, ie. the largest eigenvalue of matrix DF. The bit loading and power control algorithm proposed by this work is presented in Sect. 4.

3 Subcarrier Allocation Algorithm Based on Combinatorial Auctions An auction requires the existence of three elements: owners willing to sell the goods they own, goods for sale, and buyers willing to buy these goods. In combinatorial auctions sets of goods are auctioned and the potential buyers bid for one or more subsets (combinations) of these goods. In the present work, the focus is on a subclass of combinatorial auctions, namely sealed-bid combinatorial auctions with single-minded bidders. Each bidder submits a single bid (single-minded), which defines the subset of goods he is interested in and the price he is willing to pay for. The other participating users cannot be informed about this bid (interception is not included in the model) and, thus, the bid is considered as sealed. The auctioneer collects all the bids, decides the allocation of goods to bidders and the corresponding prices to be paid, and announces the result of the auction. The design of the proposed subcarrier allocation algorithm is based on the auction theoretic results of [32]. The subcarrier allocation problem can be encountered as a combinatorial auction problem, where the role of auctioneer is played by the BS, the subcarriers are the goods for sale and the users are the bidders, anticipating for the subcarriers. The BS charges for the transmit power, employing a flat rate, denoted herein as α monetary units per power unit [12]. This charging scheme may be conjuncted with the pricing and billing system that the service provider employs. However, the analysis of such a perspective is out of scope for this work. Each user has an infinite amount of these monetary units but, as a rational entity, he tries to satisfy his needs with the lowest possible cost.

123

754

I. N. Stiakogiannakis, D. I. Kaklamani

3.1 Definition and Algorithm Presentation From the game theoretic perspective, this auction constitutes a game    !  = k¯ ∪ Uk¯ , V ∪ Bur , gko¯ (·) ∪ guo (·) The players participating in this game are the BS k¯ and the users u ∈ Uk¯ , thus, the set of players is k¯ ∪ Uk¯ . On the one hand, the BS defines the price per power unit α ∈ R+ , thus, the strategy space for the participating BS is V = R+ . On the other hand, each user u ∈ Uk¯ expresses his preferences by reporting a subset of the available subcarriers Cur ⊆ "N and# his valuation vur ∈ R+ on this subcarrier set. The bid, designated as the pair bur = Cur , vur , is r the strategy for player $ $ u. Taking into consideration the fact that Cu can be any subset of N with su elements ($Cur $ = su , cf. § 2.2.2), it follows that Cur is member of the su -subset of N that contains all the subsets of N with cardinality su , formally Cur ∈ Psu (N ). As a result, the strategy space for user u is Bur = Psu (N ) × R+ and bur ∈ Bur , and the strategy space for !  r r r r r r the game is designated as V ∪ Bu . Finally, if pu (b ), b = b1 , . . . , bu , . . . , bU ¯ , is the k  + payment paid by user u ∈ Uk¯ , the payoff function guo (br ) = vur − pu (br ) describes the outcome for each user participating in the auction, where, %  r + vr if bur is granted, vu = u (17) 0 otherwise. Accordingly, the payoff function for the BS is the total income from users’ payments, ie. gko¯ (br ) = u∈U ¯ pu (br ). The payoff for both the BS and the users depends on the bids of k all users br and the rules of the auction, the allocation and payment schemes, as described in Algorithm 1. At the initialisation phase, the set of allocated subcarriers Cu is empty (ln. 1) and the payment is zero (ln. 2) for all users. At the user side, each user makes a set Cur , which contains the su best available subcarriers, in terms of nCINR Tu,n,k¯ (ln. 5–6). This is the set of subcarriers to apply for. Thence, the average power needed to be transmitted on these subcarriers in Ru su  f (ln. 7). Since order to meet the bit rate constraint Ru is derived as P¯ur = n∈Cur 2 T −1 u,n,k¯ the distribution of bits to subcarriers has not been defined yet, this is the best approximation on the required power. Consequently, the valuation for the" bundle # to request is defined as vur = α P¯ur (ln. 8). Thence, each user submits his bid bur = Cur , vur . At the BS side, the BS collects the submitted bids and makes an ordered list Uˆk¯ , which vr contains the users in descending order of ratio √su (ln. 9). This ratio is a measure expressing u a kind of average value per subcarrier [32]. The BS maintains also a winner list W (ln. 10) containing the users whose request has been accepted at the auction, whereas their payment has not been defined yet. Then, the list Uˆk¯ is scanned sequentially (ln. 11–12). If all the subcarriers that the user under consideration requires are in the set of available subcarriers (ln. 13), then they are allocated to the user (ln. 14) and they are removed from the set of available subcarriers (ln. 15). Since the user has covered his needs in bandwidth, he is removed from the set of anticipating users (ln. 16), and he is added in the winner list (ln. 17). If the user’s request is not granted (ln. 18), this is due to the fact that one or more of his requested subcarriers have already been allocated to a user/winner with higher priority. The winner list is scanned sequentially (ln. 19–20) in order to find the first winner w that caused the denial of bid of the current user u (ln. 21). The payment for this winner is then defined as

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

755

Algorithm 1: Subcarrier Allocation Algorithm based on Combinatorial Auctions ¯ U ¯ , su , ∀u ∈ U ¯ , Ru , ∀u ∈ U ¯ , T Input: k, k k k u,n,k¯ , ∀u ∈ Uk¯ Output: Cu , ∀u ∈ Uk¯ 1 2 3 4 5 6

Cu ← ∅, ∀u ∈ Uk¯ ; pu ← 0, ∀u ∈ Uk¯ ; repeat foreach u ∈ Uk¯ do Nˆ ← arg sortin∈N Tu,n,k¯ ; ' & Cur ← Nˆ (i) : 1 ≤ i ≤ su ; Ru



7

P¯ur ←

8

vur ← α P¯ur ;

9 10 11 12 13 14 15 16 17 18 19 20 21 22

vr Uˆk¯ ← arg sorti √su ; u

W ← ∅; for i = 1 to |Uˆk¯ | do u ← Uˆk¯ (i); if Cur ⊆ N then Cu ← Cur ; N ← N \Cur ; Uk¯ ← Uk¯ \{u}; W ← W ∪ {u}; else for j = 1 to |W| do w ← W( j); if Cur ∩ Cw  = ∅ then √ vr pw ← sw √su ; u

W ← W\{w}; break;

23 24

25

2 su  f −1 ; Tu,n,k¯

n∈Cur

until Uk¯ = ∅;

√ vr pw = sw √suu (ln. 22). Since the payment for this winner is decided, he is removed from the winner list (ln. 23) and the scan of the winner list is terminated (ln. 24). The payment scheme employed by the BS could be summarised as follows: the winner will pay per subcarrier the average value of the first bid that is denied because of him, reminding thus the second-price auctions [33]. Reaching the end of the ordered list of participating users Uˆk¯ , the algorithm is repeated with the updated set of available subcarriers (ln. 3) and only the users that have not been allocated yet the defined number of subcarriers (ln. 4) take part in the auction. The allocation process ends when each user u ∈ Uk¯ has been allocated su subcarriers, which means that the set of anticipating users is empty (ln. 25). 3.2 Remarks It must be highlighted that the subcarrier allocation process described previously is distributed to both the users and the BS. The first part (ln. 4–8) is executed by each user independently. The subcarriers that form the set Cur are selected based on the simple but rational concept of

123

756

I. N. Stiakogiannakis, D. I. Kaklamani

selfishness; each user seeks the best available subcarriers in order to cover his needs in bit rate at the lowest possible cost. The definition of the metrics P¯ur and vur is imposed by the nature of the problem under consideration; the objective of each user is not the maximisation of his bit rate but the fulfilment of his bit rate requirements with the minimum required power, and consequently at the minimum cost. The second part of the algorithm (ln. 9–24) is executed at the BS. The BS collects the bids vr from all the participating users and starts serving users in descending order of √su . From u the auction perspective, this is equivalent to prioritising the bidder willing to pay the most per subcarrier whereas, from the network perspective, this results in giving priority to the user who requires more power. This choice is based on two reasons. The first one is related to the cell-edge users. Usually, these users encounter problems due to low channel quality and, consequently, require high power. Therefore, this choice aims at prioritising users with worse channel conditions. The second reason is related to the structure of the algorithm. The model that Algorithm 1 follows consists of successive combinatorial auctions. If a user u is not satisfied at an iteration, this is due to the fact that one or more subcarriers from the set Cur have already been allocated to a user with higher priority. As a result, user u will come back at the next iteration with an updated request Cur , where the unavailable subcarriers will be replaced with worse ones. Consequently, the required average power P¯ur will be higher. In other words, the algorithm gives priority to users with high required power, because if they are not served, they will come back requiring even higher power. It is worth noticing that the auction algorithm is able to reduce the feedback overhead, in comparison to schemes that require full channel knowledge at the BS, thanks to multi-user diversity and the consequent differentiated preferences of users on subcarriers. In the proposed solution, a processed, reduced form of CSI is communicated only when there is need for it. The structure of the algorithm implies that the users must inform the BS for their bids by sending Cur and vur . Furthermore, at a next iteration, the users that still take part in the auction must update their bids, by replacing the unavailable subcarriers with available ones and updating their valuation. It is clear that the success of the proposed algorithm is based mainly on the multi-user diversity. If the physical environment does not contribute towards this direction, for example in rural areas, multi-user diversity can be achieved using dumb antennas, as described in [34]. Finally, the allocation algorithm guarantees truth revelation, ie. the anticipating users have no interest to lie about their preferences and valuations. In order to establish this claim, it can be shown that the allocation algorithm satisfies the four sufficient conditions for truth revelation for single-minded bidders, described in [32, Theorem 9.6], namely Exactness, Monotonicity, Critical and Participation. Concluding, a thorough analysis on the  proposed algorithm shows that its computational complexity can be described as O Uk¯2 N under the assumption that log N ≤ Uk¯ ≤ N . 3.3 Two users—Two subcarriers—One BS In order to gain deeper comprehension on the different approaches to the subcarrier allocation process, this section examines the simple scenario of a single BS that serves two users (u = 1 and u = 2). The BS has two subcarriers (n = 1 and n = 2) and each user requires bps one subcarrier (s1 = s2 = 1). For convenience, it is assumed that R1 = R2 =  f Hz , so Ru

that 2 su f − 1 = 1, u = 1, 2.

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory Table 1 Subcarrier allocation algorithms for the simple scenario of two users—two subcarriers—one BS

Hungarian Adaptive

  P¯T ← min T 1 + T 1 , T 1 + T 1 1,1 2,2 1,2 2,1 n 1 ← arg maxn T1,n n2 ← 3 − n1 P¯T ← 1 +

Auction

757

T1,n 1

1 T2,n 2

n 1 ← arg maxn T1,n , n 2 ← arg maxn T2,n if T 1 ≥ T 1 then 1,n 1 2,n 2 if n 2 = n 1 then n 2 ← 3 − n 1 else

Random

if n 1 = n 2 then n 1 ← 3 − n 2 P¯T ← T 1 + T 1 1,n 2,n 2  1   P¯T ← p T 1 + T 1 + (1 − p) T 1 + T 1 1,1 2,2 1,2 2,1

In this case, the subcarrier allocation algorithm must choose between the two possible allocations:   1 1 – User 1 gets subcarrier 1 whereas user 2 gets subcarrier 2 P¯T = T1,1 . + T2,2   1 1 – User 1 gets subcarrier 2 whereas user 2 gets subcarrier 1 P¯T = T1,2 . + T2,1 where P¯T = P¯1 + P¯2 stands for the total average transmit power, and P¯u , u = 1, 2 denotes the average power transmitted for user u. The index of BS has been omitted for clarity. Apart from the Hungarian and the proposed auction algorithm, two more algorithms are considered in this section, namely the adaptive and the random one. The adaptive algorithm was presented in [35]. In this approach, each user takes the token in a round-robin fashion, based on a sequence defined by their introduction to the system. When the user has the token, he is allocated the best, in terms of nCINR, subcarrier from the subcarriers that have not been allocated yet, and then passes the token to the next user. The process is ended up when each user u has been allocated the number of subcarriers su . The algorithmic  predefined  complexity of this approach is O N 2 [28]. Both the Hungarian and the adaptive algorithms require full knowledge of CSI, ie. it is necessary for the BS k¯ to know the nCINR for each user u ∈ Uk¯ on each subcarrier n ∈ N . In order to avoid this overhead in uplink due to feedback, a widely used solution is the random distribution of subcarriers among users, in order to achieve averaging of channel quality. In this approach, each user is allocated su subcarriers randomly selected from the set of available subcarriers, an algorithm with complexity O (N ) [28]. Table 1 describes how the subcarrier allocation is performed and the total average power is derived for each of the algorithms under consideration. As far as notation is concerned, n u , u = 1, 2 is the subcarrier allocated to user u, while p is a binary random variable, equal to 0 or 1. In order to evaluate the performance of the algorithms, 105 Monte Carlo iterations of the subcarrier allocation process have been conducted, according to the parameters given in Table 2, unless it has already been defined differently. The two subcarriers, for which the two users anticipate, are randomly chosen from the set of subcarriers. The remark drawn from Fig. 2 is the ranking of the algorithms on the total average transmit power. The optimal Hungarian algorithm requires the least power, the auction algorithm follows, very close to the optimal curve, the adaptive algorithm comes third, and finally, the

123

758

I. N. Stiakogiannakis, D. I. Kaklamani

Table 2 OFDMA network simulation parameters Number of cells

K =7

Cell radius

R = 1 km

Central frequency

f c = 2.5 GHz

Available bandwidth

BW = 10 MHz

Number of OFDM subcarriers

N = 128

Subcarrier spacing

Requested bit rate

 f = 78.125 kHz   bits QPSK bmin = 2 symbol   bits 16-QAM b = 4 symbol   bits 64-QAM bmax = 6 symbol Ru = 2,048 kbps

Bit error rate

Peu = 10−4

BS maximum transmit power

PBmax S = 43 dBm

BS antenna gain

G TB xS = 16 dBi; omnidirectional

Modulation types

MS antenna gain

Rx = 0 dBi; omnidirectional GM S

Propagation model

COST-Hata-model [40]

BS antenna height

h B S = 32 m

MS antenna height

h M S = 1.5 m

Shadowing

σshadowing = 8.9 dB

Channel model

MS noise figure

ITU Pedestrian B [41] N0 = −174 dBm Hz Rx = 7 dB FM S

Report length

l p = 6 bits [1, Sect. 8.4.12.3]

Noise spectral power density

random algorithm is the one that requires the most power. Furthermore, from the numerical results, it is shown that the adaptive algorithm performs the same allocation as the optimal one in 75 % of the cases, this percentage raises to 91 % for the auction algorithm, whereas it falls to 50 % for the random algorithm, as it is statistically expected. For further analysis and comparative results, cf. [36].

4 Bit Loading and Power Control Based on Non-cooperative Games Considering the power control from another perspective, if the initiative is left to the users, it is expected that each user would aim at minimising his own transmit power, while meeting his requested BER. This behaviour can be imposed by a power pricing scheme, similar to the one described in the previous section, where the BSs charge per transmit power unit. Formally, this could be written as a minimisation problem for each subcarrier n, minimise Pn,ki

∀i ∈ In

(18)

∀i ∈ In

(19)

subject to G u i ,n,ki Pn,ki ≥ γu i ,n,ki 2 j=1 G u i ,n,k j Pn,k j + σ

κ

j =i

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

759

1

Pr[PT < abscissa]

0.8

0.6

0.4

Hungarian Adaptive

0.2

Auction Random

0 −20

0

_ PT (dBm)

20

40

Fig. 2 Cumulative distribution function of total average transmit power for subcarrier allocation algorithms for the simple scenario of two users—two subcarriers—one BS

For convenience and clarity, a simplified notation is used in the following, Pi = Pn,ki , G i, j = G u i ,n,k j

  i = u i , bi = bn,ki , γi = γu i ,n,ki = i 2bi − 1 Furthermore, in order to rewrite the per subcarrier minimisation problem in a more compact form, we define the interfering power vector P−i and interfering gain vector Gi,−i as, P−i = [P j ]κj=1 = [P1 , . . . , Pi−1 , Pi+1 , . . . , Pκ ]T j=i

Gi,−i = [G i, j ]κj=1 = [G i,1 , . . . , G i,i−1 , G i,i+1 , . . . , G i,κ ] j =i

Utilising this notation, constraint (19) can be written as  γi  Pi ≥ Pimin = Gi,−i P−i + σ 2 , ∀i ∈ In G i,i

(20)

where Pimin = Pimin (P−i ) stands for the minimum transmit power to meet BER constraint. The user on the one hand has to meet constraint (19), while on the other hand tries to minimise his transmit power. This can be interpreted as an attempt to reduce the distance between Pi and Pimin . In order to follow the typical game theoretic notation, where each player tries$to maximise his $utility function, the utility function for each user is defined as vi (P) = − $ Pi − Pimin (P−i )$. Furthermore, the action of each user is the transmit power he asks for from his serving BS, Pi ∈ Pi = R+ . Summarising, the power problem on  control  κ , {P } , {v (·)} , each subcarrier can be formulated as a non-cooperative game G = {u i }i=1 i i where the parameters stand for the players, the strategy space and the utility functions, respectively. Each user maximises his utility function by playing his minimum transmit power, ie. when (20) is satisfied with equality. As a result,  γi  Pi∗ = br (P−i ) = (21) Gi,−i P−i + σ 2 , ∀i ∈ In G i,i

123

760

I. N. Stiakogiannakis, D. I. Kaklamani

where br (P−i ) stands for the best response of user u i to the actions P−i of his opponents. In a Nash equilibrium point, all users’ actions are their best responses to the actions of their opponents [37,38]. As a result, in equilibrium,   ∗  γi  ∗ Pi∗ = br P−i = Gi,−i P−i + σ 2 , ∀i ∈ In (22) G i,i Writing (22) in matrix form, it derives that, P∗ = DFP∗ + v  ∞ From (23), it becomes clear that if the sequence P(l) l=0 defined by, P(l) = DFP(l−1) + v

(23)

(24)

converges, it converges to the Nash equilibrium of the power control game. As derived from [31, Theorem 7.19], the aforementioned sequence converges to the unique Nash equilibrium if and only if ρ (DF) < 1. However, if the value of ρ (DF) is to be used as the convergence criterion, a centralised control entity is necessary for collecting from all the co-channel users the information needed to built matrices D and F, calculating the eigenvalues of DF and deciding whether ρ (DF) < 1 holds or not. On the contrary, taking into consideration the fact that ρ (DF) ≤ DF for any natural norm · [31, Theorem 7.15], the convergence condition ρ (DF) < 1 can be replaced by the stricter condition DF < 1, which is sufficient but not necessary. In order to guarantee the distributed nature of power control, it is necessary to employ a natural norm that considers only the lines of the matrix DF (own CSI information). A natural norm $that $meets this constraint is the infinity norm ·∞ , defined as, A∞ = max1≤i≤κ κj=1 $ Ai, j $. Consequently, DF∞ = max

1≤i≤κ

κ γi  G i, j G i,i

(25)

j=1 j=i

In order to achieve convergence based on the infinity norm, it is sufficient to demand, κ γi  G i, j < 1, ∀i ∈ In G i,i

(26)

j=1 j=i

From (26), γi <

G i,i (15) ⇔ κ G i, j j=1 j=i

⎛

⎞

1⎟ G i,i ⎜ bi < bilim = log2 ⎝1 + κ ⎠ G  j=1 i, j i

(27)

j=i

= bulim posed by (27) during the bit Concluding, if each user u i respects the limit i ,n,ki loading phase, then the power control game converges to the unique Nash equilibrium. Furthermore, from (23) and (24), using the infinity norm, it can be shown that, ( ( ( ( ( ∗ ( ( ( (28) (P − P(l) ( ≤ DFl∞ (P∗ − P(0) ( bilim

∞

123

∞

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

761

proving, thus, that the convergence to the Nash equilibrium is exponentially fast. The error between the power calculated at current iteration of (24) and the equilibrium one is bounded as, ( ( ( DF∞ ( ( ∗ ( ( (l) ( (29) (P − P(l) ( ≤ (P − P(l−1) ( ∞ ∞ 1 − DF∞ which is also valid element-wise, in case of infinity norm, $ $ $ 2bi − 1 $$ (l) $ ∗ (l) $ (l−1) $ $Pi − Pi $ $Pi − Pi $ ≤ lim 2bi − 2bi

(30)

The iterative process (24) and the power control game will terminate when all users stop to update their transmit power, based on a predefined upper bound for the estimation error, as designated by (30). 4.1 Channel Probing When a BS k¯ decides to use a subcarrier n that was not in use, the set of co-channel BSs on lim is invalidated subcarrier n is altered and, as a consequence, the current estimation of bu,n,k for all the co-channel users. In order to maintain the distributed nature of the algorithm, all the co-channel users must be informed that BS k¯ is intended to use subcarrier n and respond appropriately to this intention. The employed scheme for tackling this problem is as follows: – The BS k¯ transmits on all the subcarriers that were not in use up to now. For this procedure a low spectral efficiency modulation should be used, for example binary phase shift keying (BPSK), so as to minimise power waste. – The co-channel users sense that the number of co-channel BSs has changed and re-callim , based on the updated set of co-channel BSs. culate the limit bu,n,k – If (27) is violated for a user on subcarrier n, this user asks his serving BS to block the ¯ usage of this subcarrier n from BS k. – The BS that receives such a message from one of its serving users, forwards the message to BS k¯ through the backbone network. – The BS k¯ accepts the request and does not allocate subcarrier n. 4.2 Algorithm Presentation The proposed distributed bit loading and power control algorithm is given in Algorithm 2. The algorithm follows the greedy approach of the centralised algorithm of [5]. The main difference is that the proposed algorithm is performed by each user independently, by exploiting the CSI knowledge on his own subcarriers. The Input of the algorithm indicates all the necessary quantities that must be defined prior to the execution of the distributed bit loading and power control. It must be clarified that, thanks to the distributed nature of the algorithm, there is no need for communicating all this information among BSs and users. On the contrary, much of the CSI information is exploited only locally, at users’ end. Initially, all the subcarriers of the BS k¯ are unloaded (ln. 1–2). The algorithm is executed independently by each user of BS k¯ (ln. 3). While the requested bit rate has not been reached yet for the user u under consideration (ln. 4), he tries to increase the modulation level for f each of his allocated subcarriers from bn,k¯ to bn,k¯ + 2. The set Cu (ln. 5) is the subset of the subcarriers allocated to user u that it is feasible to increase their modulation level by 2 bits per symbol, ie. the new modulation level does not exceed the maximum modulation level

123

762

I. N. Stiakogiannakis, D. I. Kaklamani f

lim ). If C is empty (ln. 6), the (bn,k¯ + 2 ≤ bmax ) or the convergence limit (bn,k¯ + 2 < bu,n, u k¯ requested bit rate cannot be provided, as there is no subcarrier able to increase its modulation level. As a result, the BS k¯ rejects the newly added user u¯ (ln. 7), since the latter cannot be f served without causing problems to already accepted users. For the subcarriers in Cu , the increment in transmit power is calculated in order to support the increased modulation level (ln. 9). The increment in transmit power is calculated as,     Pn = Pn,k¯ bn,k¯ + 2 − Pn,k¯ bn,k¯

=

2bn,k¯ +2 − 1 2bn,k¯ − 1 − Tu,n,k¯ Tu,n,k¯

=3

2bn,k¯ Tu,n,k¯

The necessary increment in transmit power is calculated considering the CSI information available at this phase, before the execution of power control. The subcarrier requiring the least transmit power increment is selected (ln. 10) and its modulation level is increased by 2 bits per symbol (ln. 11). The bit loading is followed by the power control process. For each loaded subcarrier (ln. 12), a power control game is initiated. Each co-channel user (ln. 16) updates his transmit power, based on the interference he undergoes (ln. 17). As previously noticed, it is not necessary for the user to be able to distinguish the sources of interference but rather calculate the interference as a whole. Thence, the co-channel BS checks whether it is possible to transmit the required power by checking the maximum available power limitation (ln. 18). If the required power overcomes this limit, the BS k¯ is asked to reject user u¯ (ln. 19). The process is terminated when the users has approximated the equilibrium by a factor , by applying the convergence criterion (30) (ln. 20). $ Specifically, $ herein, it is chosen to evaluate the con∗ −P (l) $ $ Pn,k n,k vergence based on the relevant error $$ i (l) i $$ rather than the absolute error of (30). The P n,ki

iteration counter l (ln. 13,15) is not necessary in practice, but it is used herein for presentation reasons. In fact, each user responds spontaneously, through the process of best responses, to the increment of undergoing interference up to achieving the desired convergence precision. Concluding, it must noticed that  the computational complexity of the proposed, distributed algorithm can be described as O N 2 , whereas the complexity for the centralised algorithm   of [5] is O N 2 K 3 .

5 Simulation Results 5.1 Parameters The basic parameters of the simulated OFDMA network are summarised in Table 2, mainly derived from [39]. At this point, the approximation of equilibrium in power control game must be addressed. Since l p bits are used for transmit power report, 2l p different states can be encoded. Due to large cell radius, large variations are expected in transmit power, thus a direct association between transmit power value and a codeword would lead to low accuracy in power reporting. Instead, differential reporting is adopted [1]. Initially, the user sends explicitly his required power (in dBm), based on a scale of length l p . In the following iterations, he sends the required increment in transmit power (in dB), relevant to the previous

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

763

Algorithm 2: Distributed Bit Loading and Power Control Algorithm ¯ U ¯ , Cu , ∀u ∈ U ¯ , Ru , ∀u ∈ U ¯ , blim , ∀u ∈ U ¯ , ∀n ∈ Cu , T Input: k, u,n,k¯ , ∀u ∈ Uk¯ , ∀n ∈ Cu , k k k u,n,k¯ k γu,n,k , ∀u ∈ U , ∀n ∈ N , ∀k ∈ K, G u,n,k , ∀u ∈ U , ∀n ∈ N , ∀k ∈ K, Pn,k , ∀n ∈ N , ∀k ∈ K, lim , ∀u ∈ U , ∀n ∈ N , ∀k ∈ K bn,k , ∀n ∈ N , ∀k ∈ K, bu,n,k Output: bn,k¯ , ∀u ∈ Uk¯ , Pn,k , ∀n ∈ N , ∀k ∈ K 1 2 3 4 5 6 7 8

bn,k¯ ← 0, ∀n ∈ N ; Pn,k¯ ← 0, ∀n ∈ N ; foreach u ∈ Uk¯ do while Ruo <& Ru do    ' f Cu ← n ∈ Cu : bn,k¯ + 2 ≤ bmax ∧ bn,k¯ + 2 < blim ¯ ; u,n,k f

if Cu = ∅ then Reject u; ¯ else b ¯ n,k

f

9

Pn ← 3 T2

10

nˆ ← arg min

11

bn, ˆ k¯ ← bn, ˆ k¯ + 2;

12 13 14 15 16

u,n,k¯

f

n∈Cu

Pn ;

foreach n ∈ Cu do l ← 0; repeat l ← l + 1; foreach i ∈ In do

  κ γu ,n,k (l) (l−1) 2 ; Pn,k ← G i i G P + σ j=1 u i ,n,k j n,k j i u i ,n,ki j =i N (l) if n=1 Pn,k > PBmax then S i Reject u; ¯

17

18 19

 20

, ∀n ∈ Cu ;

until

b 2 n,ki −1

lim

b b 2 u i ,n,ki −2 n,ki

$ (l) $  $ P −P (l−1) $ $ n,ki n,ki $ < , ∀i ∈ I ; $ $ n (l) $ $ Pn,k i

value. By choosing to encode changes up to 1 dB, the power can be changed by a step of 2−l p dB. Considering this limitation, it becomes clear that the Nash equilibrium cannot be approximated as close as desired, but the is subject to this limitation of quan$ approximation $ ∗ −P (l) $ $ Pn,k n,k tisation. From (30), the relative error $$ i (l) i $$ < can be limited up to the point the P n,ki −l p

− 2 10

desirable accuracy satisfies ≥ 1 − 10 . In the following, the equality is chosen in order to achieve the maximum accuracy, thus, with l p = 6 bits, = 3.6 · 10−3 . 5.2 Results The following results have been obtained through Monte Carlo simulations, with 5,000 iterations and the presented quantities are average values of the corresponding metrics. Although the operation of the multi-cell OFDMA network has been simulated, in the following, the metrics presented correspond to the central cell of the network (k¯ = 1), in order to study the performance of a cell that operates under realistic interference conditions. As far as notation is concerned, ‘Hungarian-CNT’ and ‘Auction-CNT’ stands for the Hungarian and the proposed

123

764

I. N. Stiakogiannakis, D. I. Kaklamani 16 14

Ro (Mbps)

12 10 8 Hungarian−CNT

6

Auction−CNT Hungarian−DST

4

Auction−DST 2

2

6

10

14

18

22

26

30

34

38

42

R (Mbps) Fig. 3 Offered bit rate versus requested bit rate

auction algorithm with centralised bit loading and power control, whereas ‘Hungarian-DST’ and ‘Auction-DST’ represent, respectively the two algorithms with the proposed distributed bit loading and power control. Offered bit rate Figure 3 depicts the offered bit rate of the central cell k¯ R o =  f n∈N bn,k¯ Vk¯ versus the requested bit rate R = u=1 Ru for the different simulated RRM schemes. R increases as the number of users Vk¯ asking for admittance in cell k¯ increases from 1 to Vk¯lim = 20. Comparing the subcarrier allocation algorithms under the same power control scheme, it can be noted that the auction algorithm closely follows the optimal Hungarian algorithm. Specifically, under centralised power control, the auction algorithm reaches at least the 94.24 % of the offered bit rate of the optimal algorithm, whereas this percentage is 91.59 % for the distributed power control. Comparing the different power control schemes under the same subcarrier allocation algorithm, it is noticed that the distributed scheme is inferior to the centralised one at saturation by 3.31 Mbps (79.20 %) for the Hungarian algorithm and 3.45 Mbps (76.98 %) for the auction algorithm. As previously noticed, the distributed scheme tends to be more conservative in power consumption. Hence, the a priori exclusion of specific subcarriers, because they violate the convergence criterion, reduces the available bandwidth of the cell, which leads eventually to reduction in offered bit rate. The strictness of the convergence criterion, imposed by the partial knowledge of CSI, causes the inferior performance of the distributed power control compared to the centralised scheme. Concluding the analysis on the offered bit rate, from the numerical results, it is shown that when the introduction of new users is terminated at Vklim = 20, ∀k ∈ K and R = 40.96 Mbps, o the rate of change of the offered bit rate R R for the simulated schemes varies from 3.38 to 4.70 %, indicating, thus, that the network could hardly serve more incoming traffic, in other words the network is saturated. Transmit Power The transmit power of the central cell P t = n∈N Pn,k¯ versus the offered bit rate R o is depicted in Fig. 4. Comparing the Hungarian and auction algorithms under the same power control scheme, it can be noticed that the auction algorithm is slightly worse than

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory 43 42

765

Hungarian−CNT Auction−CNT

40

Hungarian−DST

Pt (dBm)

38

Auction−DST

36 34 32 30 28 26

2

4

6

8 o

10

12

14

16

R (Mbps) Fig. 4 Transmit power versus offered bit rate

the Hungarian algorithm. Specifically, the auction algorithm requires at worst case 0.46 dB more transmit power than the Hungarian algorithm under centralised power control, whereas this difference is 0.15 dB under distributed power control. Comparing the two power control schemes, it is clear that the distributed power control leads to lower power consumption than the centralised scheme. As the offered bit rate increases, the distributed algorithm, more conservative on power consumption, increases the required transmit power per offered bit rate unit less rapidly than the centralised scheme, leading, however, at the same time to lower offered bit rate. Specifically, the Hungarian algorithm under distributed power control requires up to 3.34 dB less transmit power than the centralised scheme. This difference is 2.70 dB for the auction algorithm. A final remark concerns the gap between the total transmit power at saturation and the available transmit power of the cell PBmax S = 43 dBm. From the numerical results, it is shown that there is a power surplus of approximately 3.5 dB for the centralised scheme and 9.5 dB for the distributed one. This power surplus could lead to the employment of lower power radio frequency (RF) amplifiers and thus lower cost, and, if the available spectrum can also be used secondarily by cognitive networks, this could lead to lower cost for bandwidth occupation for the network operator [42]. Uplink overhead Figure 5 depicts the total overhead caused by the feedback information for each of the examined schemes. This overhead includes the required information that the users send back to their serving BS, both at subcarrier allocation and bit loading and power control processes. A first remark refers to the fact that the Hungarian algorithm requires greater amount of feedback information in comparison to the auction algorithm, whereas the gap between them broadens as the offered bit rate increases. This gap is due to the full CSI knowledge that the Hungarian algorithm requires, contrary to the partial knowledge required by the auction algorithm. Comparing the schemes under the same subcarrier allocation algorithm, first for the Hungarian algorithm, it is observed that the centralised power control requires greater amount of feedback, compared to the distributed scheme, a gap which broadens as the offered bit rate increases. The smaller requirements of the distributed power control are attributed to two facts. The first one concerns the subcarrier allocation process. Since the set of available subcarriers is smaller than the one in the case of the centralised scheme, the

123

766

I. N. Stiakogiannakis, D. I. Kaklamani

Hungarian−CNT

8

Auction−CNT

UL OH (kbits)

Hungarian−DST Auction−DST

6

4

2

0

2

4

6

8

10

12

14

16

o

R (Mbps) Fig. 5 Uplink overhead versus offered bit rate

algorithm feedbacks a smaller amount of CSI. The second fact is related to the bit loading and power control process. The centralised scheme requires the users to feedback the channel gain on their subcarriers, as perceived from all the BSs. At the distributed scheme, the user simply informs the serving BS about the modulation level for each allocated subcarrier and the required transmit power per allocated subcarrier for each iteration of the power control game. As far as the auction algorithm is concerned, it is noticed that the curve of the distributed scheme is slightly higher, compared to the one of the centralised scheme. Considering that at the subcarrier allocation process the algorithm requires reporting CSI only for the required subcarriers, the reduction of available subcarriers does not seem to affect the uplink overhead. On the contrary, the power control process contributes mainly to the increment of uplink overhead. Hence, from Fig. 5, it is shown that the overhead caused by the feedback of the modulation level for each allocated subcarrier and, mainly, the iterative feedback of the updated transmit power during the power control game results in a greater amount of overhead overall. Number of auctions Figure 6 depicts the required number of auctions for the completion of the subcarrier allocation process. A first remark is that the number of auctions increases linearly with the offered bit rate, with a slope approximately 0.38 auctions per Mbps. Comparing the two curves, a slight increment in number of auctions occurs for the distributed power control. This increment is attributed to the smaller set of available subcarriers. A smaller set leads to more overlaps among the required subcarrier sets, increasing, thus, the number of the necessary auctions. This slight increment in the number of auctions contributes, in minor, to the increment of feedback, as already explained. Power control iterations The number of iterations required for the convergence of the power control game is depicted in Fig. 7. First of all, it can be noticed that the number of iterations varies from 2.4 to 14.4. It should be noted that the minimum number of iterations is 2, since in the first iteration the user of cell k¯ defines his power and at the next iteration the cochannel users from the other cells respond by updating their transmit power. In the following iterations, all the users respond simultaneously to the updated interference environment. The

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

767

6

Hungarian−CNT Auction−CNT

5

Auction Iterations

Hungarian−DST Auction−DST 4

3

2

1

2

4

6

8

10

12

14

16

Ro (Mbps) Fig. 6 Number of auctions versus offered bit rate

Power Control Convergence Iterations

16 14 12 10 8 6

Hungarian−CNT 4

Auction−CNT Hungarian−DST

2

Auction−DST

0 2

4

6

8

10

12

14

16

Ro (Mbps) Fig. 7 Power control iterations versus offered bit rate

upper limit that exceeds 14 iterations is mainly defined by the desirable accuracy in the approximation of the equilibrium. In the simulations conducted, the maximum accuracy was demanded, leading, thus, to a relatively large number of iterations. Finally, the relatively large number of iterations is the major factor that burdens the uplink overhead, due to the transmission of the updated power at each iteration.

6 Conclusions In this work, an RRM framework, tackling the MA problem for the downlink of multi-user multi-cell OFDMA networks, has been presented. Specifically, the present work proposes a subcarrier allocation algorithm based on combinatorial auctions and a bit loading and power

123

768

I. N. Stiakogiannakis, D. I. Kaklamani

control algorithm based on non-cooperative games. Firstly, the auction-based subcarrier allocation algorithm is shown to be an appealing alternative to the optimal Hungarian subcarrier allocation algorithm. It shows comparable performance with slightly lower offered bit rate and slightly higher required transmit power, whereas it is of lower computational complexity and alleviates the overhead on reverse link, since it requires less feedback information. Secondly, the main advantage of the proposed bit loading and power control scheme is the fact that it can be executed in a distributed way, transferring, thus, part of the complexity to the users end and resulting in a reduced feedback overhead. The distributed nature of the proposed solution contributes also to the scalability of the network, since there is no need for a single entity to control and coordinate in a centralised way all the network links. The proposed scheme achieves lower transmit power per offered bit rate unit but the distributed nature of the algorithm results in a lower total offered bit rate, because of the partial knowledge and exploitation of the channel state information.

References 1. IEEE. (2009). IEEE standard for local and metropolitan area networks part 16: Air interface for broadband wireless access systems. IEEE Std 802.16-2009 (Revision of IEEE Std 802.16-2004). 2. 3GPP. (2009). Evolved universal terrestrial radio access (E-UTRA); long term evolution (LTE) physical layer; general description. Technical Report 3GPP TS 36.201 V9.0.0. 3. Wong, C. Y., Cheng, R. S., Lataief, K. B., & Murch, R. D. (1999). Multiuser OFDM with adaptive subcarrier, bit, and power allocation. IEEE Journal on Selected Areas in Communications, 17(10), 1747– 1758. 4. Kivanc, D., Li, G., & Liu, H. (2003). Computationally efficient bandwidth allocation and power control for OFDMA. IEEE Transactions on Wireless Communications, 2(6), 1150–1158. 5. Kulkarni, G., Adlakha, S., & Srivastava, M. (2005). Subcarrier allocation and bit loading algorithms for OFDMA-based wireless networks. IEEE Transactions on Mobile Computing, 4(6), 652–662. 6. Sadr, S., Anpalagan, A., & Raahemifar, K. (2009). Radio resource allocation algorithms for the downlink of multiuser OFDM communication systems. IEEE Communications Surveys & Tutorials, 11(3), 92–106. 7. Altman, E., Boulogne, T., El-Azouzi, R., Jimnez, T., & Wynter, L. (2006). A survey on networking games in telecommunications. Computers & Operations Research, 33(2), 286–311. 8. Charilas, D. E., & Panagopoulos, A. D. (2010). A survey on game theory applications in wireless networks. Computer Networks, 54(18), 3421–3430. 9. Felegyhazi, M., & Hubaux J. P. (2006). Game theory in wireless networks: A tutorial. Technical report LCA-REPORT-2006-002, Ecole Polytechnique Federale de Lausanne. 10. MacKenzie, A. B., & DaSilva, L. A. (2006). Game theory for wireless engineers (Synthesis lectures on communications). San Francisco Bay Area, CA: Morgan & Claypool Publishers. 11. Yang, K., Prasad, N., & Wang, X. (2009). An auction approach to resource allocation in uplink OFDMA systems. IEEE Transactions on Signal Processing, 57(11), 4482–4496. 12. Rodriguez, V., & Mathar, R. (2010). Simple decentralised market-oriented allocation of sub-channels and power for access-point to terminal multi-carrier communication. In 44th Annual conference on information sciences and systems, 2010 (CISS 2010), pp. 1–5. 13. Han, S. W., & Han, Y. (2007). A competitive fair subchannel allocation for OFDMA system using an auction algorithm. In IEEE 66th vehicular technology conference, 2007 (VTC 2007 Fall), pp. 1787–1791. 14. Oh, J., Han, S. W., & Han, Y. (2008). Efficient and fair subchannel allocation based on auction algorithm. In IEEE 19th international symposium on personal, indoor and mobile radio communications, 2008 (PIMRC 2008), pp. 1–5. 15. Gai, Y., Gong, P., Lv, J., & Wu, W. (2009). Auction-based radio resource allocation for OFDMA systems. In 5th international conference on wireless communications, networking and mobile computing, 2009 (WiCom 2009), pp. 1–4. 16. Kong, Z., Kwok, Y.-K., & Wang, J. (2009). Auction-based scheduling in non-cooperative multiuser OFDM systems. In IEEE 69th vehicular technology conference, 2009 (VTC Spring 2009), pp. 1–4.

123

A RRM Framework for Multi-User Multi-Cell OFDMA Based on Game Theory

769

17. Forde, T. K., & Doyle, L. E. (2008). A combinatorial clock auction for OFDMA-based cognitive wireless networks. In 3rd international symposium on wireless pervasive computing, 2008 (ISWPC 2008), pp. 329–333. 18. Pang, J.-S., Scutari, G., Facchinei, F., & Wang, C. (2008). Distributed power allocation with rate constraints in gaussian parallel interference channels. IEEE Transactions on Information Theory, 54(8), 3471–3489. 19. Jorswieck, E., & Mochaourab, R. (2009). Power control game in protected and shared bands: Manipulability of Nash equilibrium. In International conference on game theory for networks, 2009 (GameNets 2009), pp. 428–437. 20. Su, Y., & van Der Schaar, M. (2009). A new perspective on multi-user power control games in interference channels. IEEE Transactions on Wireless Communications, 8(6), 2910–2919. 21. Su, Y., & van der Schaar, M. (2009). Conjectural equilibrium in multiuser power control games. IEEE Transactions on Signal Processing, 57(9), 3638–3650. 22. Cioffi, J. M. (1991). A multicarrier primer. ANSI T1E1, 4. 23. Fernekess, A., Klein, A., Wegmann, B., & Dietrich, K. (2009). Modular system-level simulator concept for ofdma systems—[Modeling and simulation: A practical guide for network designers and developers]. IEEE Communications Magazine, 47(3), 150–156. 24. Li, G., & Liu, H. (2005). On the optimality of the OFDMA network. IEEE Communications Letters, 9(5), 438–440. 25. Pietrzyk, S. (2006). OFDMA for broadband wireless access. Artech House mobile communications series. Boston, MA: Artech House. 26. Zander, J. (1997). Radio resource management in future wireless networks: Requirements and limitations. IEEE Communications Magazine, 35(8), 30–36. 27. Stiakogiannakis, I. N., Zarbouti, D. A., Tsoulos, G. V., & Kaklamani, D. I. (2008). Subcarrier allocation algorithms for multicellular OFDMA snetworks without channel state information. In 3rd International symposium on wireless pervasive computing, 2008 (ISWPC 2008), pp. 73–77. 28. Zarbouti, D., Stiakogiannakis, I., Tsoulos, G., Athanasiadou, G., & Kaklamani, D. (2009). OFDMA techniques in multicellular networks with total frequency reuse. Computer Communications, 32(3), 522–530. 29. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 83–97. 30. Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38. 31. Burden, R., & Faires, J. D. (1997). Numerical analysis, 6th Edn. Pacific Grove, CA: Brooks/Cole Pub. Co. 32. Lehmann, D., O’Callaghan, L. I., & Shoham, Y. (2002). Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49(5), 577–602. 33. Krishna, V. (2002). Auction theory. London: Academic Press. 34. Viswanath, P., Tse, D. N. C., & Laroia, R. (2002). Opportunistic beamforming using dumb antennas. IEEE Transactions on Information Theory, 48(6), 1277–1294. 35. Pietrzyk, S., & Janssen, G. J. M. (2004). Radio resource allocation for cellular networks based on OFDMA with QoS guarantees. In IEEE global telecommunications conference, 2004 (GLOBECOM 2004), Vol. 4, pp. 2694–2699. 36. Stiakogiannakis, I. N., & Kaklamani, D. I. (2011). A combinatorial auction based subcarrier allocation algorithm for multiuser OFDMA. In IEEE 73rd vehicular technology conference, 2011 (VTC Spring 2011), pp. 1–5. 37. Fudenberg, D., & Tirole, J. (1991). Game theory. Cambridge, MA: MIT Press. 38. Osborne, M. J. (2004). An introduction to game theory. New York: Oxford University Press. 39. WiMAX Forum. (2008). WiMAX system evaluation methodology. Technical Report Version 2.1. 40. European Cooperation in Science and Technology. (1999). Digital mobile radio towards future generation systems. COST 231 Final Report. 41. ITU. (2006). Guidelines for evaluation of radio transmission technologies for IMT-2000. Technical Report Rec. ITU-R M.1225. 42. Chapin, J. M., & Lehr, W. H. (2007). Cognitive radios for dynamic spectrum access—the path to market success for dynamic spectrum access technology. IEEE Communications Magazine, 45(5), 96–103.

123

770

I. N. Stiakogiannakis, D. I. Kaklamani

Author Biographies Ioannis N. Stiakogiannakis received the Dipl.Ing. and Dr. Ing. degrees in Electrical and Computer Engineering from National Technical University of Athens in 2007 and 2011, respectively. For his academic progress he has been awarded by the Rotary Club, Heraklion, and the Special Account for Research Grants, National Technical University of Athens. His research interest focuses on wireless communication networks with emphasis on radio resource allocation for OFDMA systems and its applications on WiMAX networks.

Dimitra I. Kaklamani was born in Athens, Greece, in 1965. She received the PhD degree from the National Technical University of Athens (NTUA) in Electrical and Computer Engineering (ECE), in 1992. In April 1995, April 2000, October 2004, and February 2009, she was elected Lecturer, Assistant Professor, Associate Professor, and Professor, respectively, with the School of ECE, NTUA. She has more than 260 publications in the fields of software development for information transmission systems modeling, microwave networks, mobile and satellite communications, and has coordinated the NTUA activities in the framework of several EU and National projects in the same areas. She is Editor of one international book by Springer-Verlag (2000) in applied CEM and reviewer for several IEEE journals.

123