José R Vidal
email: jrvidal@dcom.upv.es

Vicent Pla
email: vpla@dcom.upv.es

Luis Guijarro

Jorge Martinez-Bauset

Flexible Dynamic Spectrum Allocation in Cognitive Radio Networks Based on Game-theoretical Mechanism Design

Keywords: Cognitive radio, spectrum sharing, game theory, mechanism design

In this paper we present an approach based on game-theoretical mechanism design for dynamic spectrum allocation in cognitive radio networks. Secondary users (SU) detect when channels can be used without disrupting any primary user and try to use them opportunistically. When an SU detects a free channel, it estimates its capacity and sends the valuation of it to a central manager. The manager calculates a conflict-free allocation by implementing a truthful mechanism. The SUs have to pay for the allocation an amount which depends on the set of valuations, and they behave as benefit maximizers. We present and test two mechanisms implementing this idea which are proved to be truthful, and that are tractable and approximately efficient. We show the flexibility of these mechanisms by illustrating how they can be modified to achieve other objectives such as fairness and also how they can operate without really charging the SUs.

Introduction

Cognitive radio is the technology that enables dynamic spectrum access (DSA) networks to fully utilize the scarce spectrum resources. In DSA networks, users who have no spectrum licenses, known as SUs, are allowed to use the spectrum. In this paper, we will focus on DSA networks with hierarchical and overlay access [START_REF] Zhao | A survey of dynamic spectrum access: signal processing, networking, and regulatory policy[END_REF]. In the hierarchical access model, SUs use spectrum that is licensed to primary users (PUs). As PUs have priority in using the spectrum, when SUs coexist with PUs, they have to perform real-time wideband monitoring of the licensed spectrum to be used in order to avoid harmful interference to PUs. In overlay access, also referred to as opportunistic spectrum access, SUs only use the licensed spectrum when PUs are not transmitting. In order not to interfere with the PUs, SUs need to sense the licensed frequency band and detect the spectrum opportunities.

The availability and quality of spectrum opportunities may change rapidly over time due to PUs activity and competition between SUs. Therefore, dynamic spectrum allocation and sharing schemes are needed to achieve flexible spectrum access in long-run scenarios. They should be able to adapt to the spectrum dynamics, e.g., channel variations, based on local observations. In centralized spectrum allocation, the opportunistic spectrum access of SUs is coordinated by a central element serving as a spectrum manager. The spectrum manager collects operation information from each SU, and allocates the spectrum resources to achieve certain objectives such as efficiency or fairness. This kind of spectrum sharing is non-cooperative, since SUs only aim at maximizing their own benefit, so SUs might exchange false information about their channel conditions in order to get more access opportunities to the spectrum. Therefore, cheat-proof spectrum sharing schemes should be developed to meet the objectives.

Dynamic spectrum sharing has been extensively studied from a game theoretical perspective [START_REF] Wang | Game theory for cognitive radio networks: An overview[END_REF]. Mechanism design is a game theoretical approach that can be applied to dynamically redistribute spectrum across several players (PUs and SUs) to meet their demands. Mechanisms aim at achieving the desired equilibrium by enforcing SUs to play truthfully, so that the spectrum resources are allocated according to reliable information. This is attained by means of payments, which are collected and redistributed by a trusted entity. In spectrum auction games, a specific form of mechanism design, a spectrum manager collects bids and allocates spectrum resources to SUs and charges them according to some rules. By multiplexing spectrum supply and demand in time and space, dynamic auctions can improve spectrum utilization or fairness.

Most of works on spectrum auctions focus on the scenario where one or more PUs want to lease spectrum to SUs, and a monetary gain for PUs is involved. In [START_REF] Wang | Spectrum sharing in cognitive radio networks: an auction-based approach[END_REF], an auction model is proposed where a PU announces a portion of its licensed band and a unit price, and SUs bid for the desired amount of bandwidth. In [START_REF] Gandhi | Towards real-time dynamic spectrum auctions[END_REF], SUs bid for a pool of homogeneous channels announcing a demand curve, from which the auction is cleared using an approximation algorithm. A belief-assisted double auction is proposed in [START_REF] Ji | Belief-assisted pricing for dynamic spectrum allocation in wireless networks with selfish users[END_REF], with collusion-resistant strategies based on the use of optimal reserve prices. Another solution for double auctions is presented in [START_REF] Zhou | TRUST: A general framework for truthful double spectrum auctions[END_REF], where several PUs auction a channel each, while several SUs bid for just one of them, assuming that all the channels are homogeneous to the SUs.

Other works propose auctions for power allocation in spectrum sharing. In [START_REF] Bae | Sequential bandwidth and power auctions for distributed spectrum sharing[END_REF] sequential second price auctions are proposed assuming complete information. In [START_REF] Huang | Auction-based spectrum sharing[END_REF] an auction model is proposed where the utility of each SU is defined as a function of the received signal-to-noise-and-interference ratio (SINR). SUs are charged a unit price for their received SINR, so that the auction achieves the desired social utility. Mechanism design is used in [START_REF] Wu | Repeated open spectrum sharing game with cheat-proof strategies[END_REF]. There the underlay model is assumed, so SUs may transmit in the licensed spectrum when PUIs are also transmitting, and their power transmission is restricted by the interference temperature limit. The objective power allocation is calculated using channel infor-mation obtained locally by SUs. A truthful mechanism with monetary transfers enforces SUs to reveal this information.

Our work differs from those cited above in two major aspects. Firstly, we address the problem of sharing spectrum opportunities between SUs without the intervention of PUs. These opportunities appear sparse in time and space, therefore we propose mechanisms to allocate them in real time, i.e., mechanisms that have to be run every time that a spectrum opportunity appears. We present two mechanisms (one deterministic and one randomized) for dynamic spectrum allocation which are truthful, computationally tractable and approximately efficient and that are simple enough for its use in real-time allocations. They have the flexibility to achieve long-run objectives other than efficiency, such as fairness, maintaining their properties. Secondly, we investigate how these mechanisms can operate without monetary transactions, which would make the solution easier to implement. If monetary gain is not involved in the spectrum allocation problem, SU payments will no longer be chosen as money, but as and alternative form of 'virtual currency'. This internal currency will be managed by the spectrum manager, which will record the credit of every SU and will distribute it to them. In order that this currency retains its value for the SUs, the mechanism itself should consider the credit kept by any SU. That is, the choice and payment functions should depend on the credit so limiting what SUs spend, and a proper 'cash flow' should be redistributed to SUs. We investigate how this can be done and how it affects to the mechanisms properties.

The rest of the paper is organized as follows. In Section 2 we describe the model of spectrum sharing on networks with hierarchical and overlay access and with a central manager. In Section 3 we describe the mechanism design background applied to this problem, present two mechanisms based on the theoretical results and describe how these mechanisms can be modified to achieve fairness and to operate with a virtual currency. We show and discus experimental results in Section 4 and conclude in Section 5.

Spectrum Sharing Model

We assume that the spectrum is divided into non-overlapping orthogonal channels and that SUs are able to detect when a channel can be used without interrupt any PU. When one of these opportunities, called white spaces, appears, SUs may try to use it opportunistically. Every white space might be used by one or several SUs, with the condition of not conflict between them. We model the interference between SUs according to the protocol model [START_REF] Gupta | The capacity of wireless networks[END_REF][START_REF] Jain | Impact of interference on multihop wireless network performance[END_REF]. This model assumes that, for a given channel, SU i has a communication range R i and a larger interference range R i . The channel can be used by SU i if the receiver is a at distance smaller than R i . Two SUs i and j are in conflict if the distance between them is smaller than R i or smaller than R j , and in this case they cannot transmit simultaneously. In this network, R i and R i depend on the transmitting power, which is imposed by the position and channel usage of nearby PUs. Additionally, the transmitting power and the distance to the receiver determines the transmission rate, hence for a given white space, SU i will be able to transmit at B i bps. With these assumptions, the conflicts for a given white space can be modelled by a conflict graph whose vertices correspond to the SUs which are able to use the channel. There is an edge between vertices i and j if SUs i and j are in conflict. This graph can be written in matrix form:

C = c ij N ×N with c ij ∈ {0, 1} . (1)
Where c ij = 1 if SUs i and j are in conflict. The sharing problem in this scenario is, for each white space, to find an allocation compatible with the conflict graph:

X = x i N ×1 where x i ∈ {0, 1} and x i • x j = 0 if c ij = 1 . (2)
Where x i = 1 if the channel is allocated to SU i. The allocation cannot fulfil efficiency and fairness simultaneously, so the objective will be a trade-off between them. This objective should be achieved on long-term basis. Long-term efficiency is achieved if every white space is allocated efficiently. A single allocation is said to be efficient if

X eff = arg max X N i=1 x i B i . (3)
However, fairness cannot be achieved for each white space, so long-run fairness should be defined as a time-average. If denote by X j the allocation made at the j-th white space, the proportional fairness criterion for M consecutive allocations is

X fair = (X 1 fair , . . . , X M fair ) = arg max X M j=1 N i=1 log x j i B j i . (4)
In our proposal we assume that there is a spectrum manager whose rules are abided by SUs, and there is a control channel dedicated to the communication between manager and SUs [START_REF] Han | Addressing the control channel design problem: OFDM-based transform domain communication system in cognitive radio[END_REF]. Every time that a white space appears, the SUs detect it and estimate B i . Those SUs willing to use the channel send B i to the manager. They also detect and communicate which neighbours they conflict with (c ij ), and from this the manager derives the conflict graph. The manager then will calculate the allocation according to the objectives, and communicate the allocation to SUs.

We also assume that no SU can benefit from lying about the conflict graph. This is not strictly true but it is a reasonable assumption in most situations, because if SU i declares non-existing conflicts (it falsely declares c ij = 1), this will reduce the set of possible allocations, so it will reduce its chances to obtain the channel. On the other side, if it hides a conflict (it falsely declares c ij = 0), the resulting allocation may be useless for i and j. However, they could benefit from lying about the channel bitrate estimation; a higher declared value of B i rises the value of N i=1 x i B i if x i = 1, so rising the manager evaluation of allocations including SU i. We propose a solution based on mechanism design for enforcing the SUs to tell the truth to the spectrum manager driven by self-interest.

We model the allocation procedure of each white space as a mechanism in which the players are the SUs and a spectrum manager that implements the game rules. Formally, a mechanism is a game in which the players do not know the utilities of the other players, and the rules of the game are designed such that the equilibrium of the game is guaranteed to have certain desired properties. It is defined by the tuple (N, O, Θ, p, u, A, M ):

-N is a set of n players or, in the spectrum allocation problem, SUs.

-O is the set of possible outcomes and will include the allocations.

-Θ = Θ 1 × • • • × Θ n is the set of possible SU types. SU i type θ i ∈ Θ i is known
only by SU i and determines its utility function. Here, θ i is determined by B i . p is the probability distribution of Θ. Here p depends on the position of SUs and interference restrictions.

-u = (u 1 , . . . , u n ), where u i : O × Θ → R is the utility function of SU i
depending on the outcome o and on its type

θ i . -A = A 1 ו • •×A n is
the action profile, where A i is the set of actions available to SU i. In this problem, the action allowed to SU i is to declare its type θ i , i.e., A i = Θ i , what results in a so-called direct mechanism. -M : A → Π(O) maps each action profile to a distribution over outcomes. If the mechanism is deterministic, then M : A → O.

If we want the resulting allocations to have certain properties as efficiency or fairness, the mechanism should implement the corresponding social choice function C : u → Π(O), i.e. the game must have an equilibrium a * in which M (a * ) = C(u). We also want the SUs to reveal truthfully their types, what will be fulfilled if the equilibrium is a * = (θ 1 , . . . , θ n ). In this problem, the solution can be restricted to a so-called quasilinear mechanism [START_REF]Algorithmic game theory[END_REF], where the possible outcomes can be written as

O = X × R n , (5)
where X is a finite set. The outcome is then an allocation plus a vector of n real numbers. The i-th value of this vector is the price that SU i has to pay for the allocation. Thus, for a given vector of types θ ∈ Θ, the utility functions is

u i (o, θ) = u i (x, θ) -p i , (6)
where u i (x, θ) is the value that allocation x has for SU i, and p i is the price that SU i has to pay when the allocation is x. This mechanisms has the property of conditional utility independence, because the value u i depends only on SU i type and not on other SUs type. We refer to the value u i as valuation of SU i for allocation x, and we write it as v i (x), considering implicit its dependence on θ i . Then:

u i (o, θ) = v i (x) -p i . (7)
Here v i (x) can be interpreted as the maximum amount that SU i would be willing to pay for allocation x. Let v i denote the mapping that assigns a valuation v i (x) for each x ∈ X. Revealing type θ i is equivalent to revealing v i and the set of allowed actions for SU i is the set of possible values of v i . Let vi denote the declared valuation of SU i, which might be different from v i . The mechanism can be interpreted as an auction, being v = (v 1 • • • vn ) ∈ V the bids, and p = (p 1 • • • p n ) the prices that the bidders have to pay. Given v, the manager calculates allocation and payment from:

-A choice rule: f : V → Π(X), or f : V → X if deterministic. -A payment rule: p : V → R n .
Our objective is to design these rules so as to achieve truthfulness [START_REF]Algorithmic game theory[END_REF]. A truthful mechanism is in equilibrium when v = v, and no SU can benefit from declaring a false valuation. A theoretical result says that, for non-restricted quasilinear preferences domains, the only existing truthful mechanism is the weighted Vickrey Clarke Groves (VCG) mechanism. This is a well known mechanism that implements efficiency and is not computationally tractable. However, here we need a mechanism able to implement other criteria as fairness, and simple to compute. Fortunately, the valuation setting described before belongs to the family of single parameter valuations [START_REF]Algorithmic game theory[END_REF], in which a valuation v i is defined by a single value. Formally, for each SU i the set of allocations can be partitioned into a winning set W i and a losing set,

v i (x) = v i if x ∈ W i 0 if x / ∈ W i (8)
Here x ∈ W i if x i = 1, i.e., SU i wins if the channel is allocated to it, regardless what happens to other SUs. Let v-i denote the vector of valuations of all SUs except SU i. The mechanism has good properties if the choice function f is monotone:

∀v i , ∀v i , v i > vi , f (v i , v-i ) ∈ W i ⇒ f (v i , v-i ) ∈ W i . (9)
That is, if a SU wins with a given valuation, it wins also with all higher valuations. Given v-i , the critical value for SU i is defined as the minimum value of vi for which SU i wins:

c i (v -i ) = sup f (vi,v-i) ∈Wi v i . (10)
A deterministic single parameter domain mechanism is truthful if and only if every winning bid pays c i (v -i ) plus a function independent on its valuation. The mechanism is said to be normalized if losing bidders pay 0. Every truthful mechanism can be turned into a normalized one. Thus, the payment rule can be expressed, without loss of generality, as

p i (v i , v-i ) = c i (v -i ) + h i (v -i ) if x ∈ W i 0 if x / ∈ W i (11)
A randomized mechanism is truthful on expectation, if for all bidders, revealing its true valuation maximizes its expected benefit, i.e., ∀i ∀v i ∀v -i ∀v i :

E[v i (f (v i , v-i )) -p i (f (v i , v-i ))] ≥ E[v i (f (v i , v-i )) -p i (f (v i , v-i ))] . (12)
Let us denote by

ω i (v i , v-i ) = P r[f (v i , v-i ) ∈ W i ]
the probability that SU i wins. Then, the expected benefit for SU i is

u i (v i , v-i ) = v i ω i (v i , v-i ) -p i (f (v i , v-i )) . (13)
If ω i (v i , v-i ) is monotonically non-decreasing in vi and v 0 i is the valuation under which i cannot win, the truthfulness condition for a normalized mechanism is [START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF]

p i (v i , v-i ) = vi ω i (v i , v-i ) - vi v 0 i ω(t, v-i )dt + h i (v -i ) . (14)
Based on these results, we propose two simple truthful mechanisms for spectrum sharing: a deterministic one and a randomized one. As the experimental results in Sec. [START_REF] Gupta | The capacity of wireless networks[END_REF] show, the randomized one exhibits better properties. They are executed every time a white space appears. When SUs detect the white space, each of them estimates its valuation v i = B i . Then, each SU willing to use the channel sends a bid containing its declared valuation vi to the spectrum manager. The manager starts an auction when it receives the first bid and, after a fixed time interval, it closes the auction. The auction is cleared by applying the choice and paying rules to the vector v, resulting in a set of winning SUs and a vector p of payments. Finally, the manager sends a message to the winners SUs.

A Deterministic Truthful Mechanism

The following mechanism approximates efficiency by giving priority to higher valuations. The resulting choice function is monotone and then every winning bid has a critical value. The payment function is the critical bid, so the mechanism is truthful. Furthermore, both choice and payment functions are computationally tractable.

-Choice function. Given a list of bids: 1. Order the list from highest to lowest value of valuations. 2. From the beginning of the list until the end of the list: Allocate the channel to bidder i if it does not conflict with any preceding winning bidder: x i = 1 if c ij x j = 0, ∀j preceding i in the list. -Payment rule. Keep the order of the bid list above. For each bid i:

1. Remove bid i from the list. 2. Start a virtual allocation x with x j = 0 ∀j.

3.

From the beginning of the list until the end of the list or until a bidder j conflicting with i virtually wins: Allocate virtually the channel to bidder k if it does not conflict with any preceding virtual winner: x k = 1 if c kl x l = 0, ∀l preceding k in the list. Then:

• If the end of the list is reached, bidder i wins and pays 0.

• If vi > vj , bidder i wins and pays the critical value c i = vj .

• If vi < vj , bidder i losses and pays 0. 4. Insert bid i into the list at its original position.

A Randomized Truthful Mechanism

A randomization of the previous mechanism results in a more flexible choice function. The resulting winning probability function ω i (v i , v-i ) is monotonically non-decreasing. Equation ( 14) is applied to obtain the payment function, so ensuring the truthfulness of the mechanism. Both choice and payment functions are computationally tractable.

-Choice function. Given a list of bids:

1. For each bid j, calculate a random value k j with uniform distribution between 0 and vj . 2. Order the list from highest to lowest value of k j . 3. From the beginning of the list until the end of the list:

Allocate the channel to each bidder if it does not conflict with any preceding winning bidder: x i = 1 if c ij x j = 0, ∀j preceding i in the list. -Payment rule. Keep the order of the bid list. For each bid i:

1. Remove bid i from the list. 2. Start a virtual allocation x with x j = 0 ∀j.

3.

From the beginning of the list until the end of the list or until a bidder j conflicting with i virtually wins: Allocate virtually the channel to bidder k if it does not conflict with any preceding virtually winner: x k = 1 if c kl x l = 0, ∀l preceding k in the list. Then:

• If the end of the list is reached, i wins and pays 0.

• If vi > k j , bidder i wins with probability1 :

ω i (v i , k -i ) = 1 - k j vi , (15)
and pays

p i = vi ω i (v i , k -i ) - vi kj ω i (t, k -i )dt = k j ln vi k j . ( 16
)
• If vi < k j , bidder i cannot win and pays 0. 4. Insert bid i into the list at its original position.

Fairness

Unfairness has two main causes. Firstly, all SUs may have not the same opportunities because physical restrictions and those SUs reporting higher valuations, if true, are favoured. This may be alleviated by limiting the budget of SUs, as described in the next section. Secondly, the mechanism itself does not treat all the bidders the same way. It is easy to see that bidders having more competition (more neighbours conflicting with) have less chances to win and when winning, they pay a higher price.

The previous mechanisms can be modified to compensate unfairness caused by the degree of competition. A simple way to do it is by weighting the valuations by a function increasing with the number of edges in the conflict graph. Simulation results are shown in Sec. 4. Clearly, this does not affect the truthfulness, because the original conditions still hold. The choice function is still monotonically non-decreasing and the payment function for the deterministic mechanism is the critical value and, for the randomized mechanism is given by

p i = vi ω i (v i , k -i ) - vi k j w i ω i (t, k -i )dt = k j w i ln w i vi k j . ( 17
)

Credit Restriction and Redistribution

So far we have considered that SUs behave as profit maximizers who value a unit of transmission rate the same as a monetary unit. Consequently, they obtain the maximum profit when the rate they get minus the money they pay is maximum. This approach is valid if SUs are effectively charged for the spectrum. Another possibility is that what they pay was not real money, but a virtual currency unit internal to the system. This could be useful if what we want is just to fairly share the spectrum, not to trade with it. This would also make the system simpler by avoiding monetary transactions. Furthermore, a limitation of the credit offered to SUs would help to achieve fairness. In this last approach, the manager should redistribute the payments and record the credit of each SU. The amount of credit given to each SU must be limited to approximately the amount of credit they would spend when it received the fair share of the spectrum. Credit limitation is the way to get them to value the credit and still behave as profit maximizers. To achieve this, the mechanism has to be modified in two ways:

-SUs need to receive a flow of credit along the time. For system stability, the total amount of credit received by them should be equal to the total amount of their payments. If this property holds for each auction, it is called budged balance.

Here we only need it to hold in the long term, and this is achieved if in every auction the expected value of what each bidder receives equals the expected value of what it pays. -SUs should be punished when they run out of credit. However, SUs with negative credit cannot be excluded from auctions, because they must still get their share of the redistribution and so recover credit for successive auctions. Instead, when a SU has low credit, the mechanism would grant it a lower winning probability.

There are several solutions for the redistribution problem that preserve truthfulness [START_REF] Moulin | Strategyproof sharing of submodular costs:budget balance versus efficiency[END_REF]. All of them satisfy the condition that what a bidder receives is independent of its valuation. Based on this idea, we have tested the following redistribution method. For every auction, a parallel auction is created with the same bidders and random valuations. Every bidder receives what it would pay in this parallel auction. If random valuations have a random distribution which approximates the distribution of real valuations, and if bidders play truthfully, long term budged balance is achieved.

For credit limitation, we have added to the previous mechanisms another weighting factor q i which depends on credit. Valuations are weighted by q i and the payment functions are modified accordingly. If we consider a single auction, this change preserves the truthfulness of the mechanism, as it did the weighting for fairness described in Sec. 3.3. However, this does not hold if we consider successive auctions, because q i depends on the credit of SU i, which in turn depends on vi . As a consequence the valuation on the current auction has an effect not only in the benefit obtained in this auction, but also in what happens in successive auctions. For this reason, it cannot be assured that SUs could not obtain a long term benefit from lying. Because successive auctions are not independent, this issue should be studied as a repeated game.

To alleviate this problem, the influence of credit in the mechanism should be as small as possible, that is, it should be q i = 1 most of time while q i < 1 is only required when SU i is close to run out of credit. Then, if the redistribution policy works properly, SUs will work most of time with q i = 1. When a SU overbids and spends all its credit it is punished. On the other side, a SU cannot benefit from saving credit because, once it reaches enough credit to have q i = 1, having more does not increase its winning probability. Simulation results shown in Sec. 4 suggest that the mechanism still behaves reasonably well, though truthfulness cannot be guaranteed in all situations.

Experimental Results and Discussion

We have evaluated the properties of previous mechanisms by means of discreteevent simulations. We have simulated a static configuration of 6 SUs with the conflict graph of Fig. 1, located into the interference range of a PU which conveys traffic bursts whose inter-arrival time is exponentially distributed with mean 20 time units and their duration is exponentially distributed with mean 10 units. The PU has a pool of 10 channels, and allocates traffic bursts randomly. Idle periods of these channels are detected by SUs as white spaces. SUs estimations of the bit rate of a white space is uniformly distribution between 0 an 2 bit-rate units. Every white space all SUs send a bid containing its valuation of the channel to the central manger, which executes the mechanism. Then it sends a message to the winners who occupy the channel until it is used by the PU again. The credit available for each SU is recorded and updated by the spectrum manager. We assume that SUs are backlogged and their objective is to send as much traffic as possible. All simulation runs have a length of 10 7 time units, what have been checked to yield statistically significant results

The plot in Fig. 2 illustrates the truthfulness of both mechanisms without credit restriction and confirms the theoretical result. Here, total benefit of SU c is the sum of the bit-rate of all the channels it won minus the total price it paid for them. This is plotted as a function of an over/under bidding factor h which measures the relation between the declared valuation and the true valuation: vc = hv c . When h > 1, c it is overbidding and when h < 1 it is underbidding. The rest of SUs are truthful. It can be seen that SU c maximizes its benefit when h = 1, i.e., when it declares the truth.

We have also tested the mechanisms with credit restriction an redistribution as described in Sec. 3.4. Here the weighting factor q i is set to 1 when credit i > 50, to 0 when credit i < -50, and it is varied linearly between 0 and 1 when -50 < credit i < 50. The initial credit is 100. By doing this, SUs are forced to keep its credit not far under 0, that is, they cannot spend much more than they receive. Since credit is not exceeded nor accumulated, now the benefit is the obtained bit-rate, i.e., the mean traffic. Some results for SU c are shown in Figs. 3 and4. We have run simulations varying h in other SUs and with other conflict graphs obtaining similar results not shown here. It can be seen that, with the deterministic mechanism, SU c can benefit from overbidding. This does not happen with the random mechanism. The reason of this different behaviour can be found in Fig. 5, which plots the unit price that SU c pays as a function of h. For the deterministic mechanism, the price grows up to a maximum for h = 1, because the payment function depends only on the critical value. Therefore, if a bid wins, the price does not depend on the bid value, that is, two winning bids with different valuations pay the same. In contrast, with the randomized mechanism the price function is given by ( 16) and depends on the valuation, so the unit price grows as it can be seen in the plot. This characteristic of the payment function adds stability to the random mechanism, because makes it more expensive to overbid.

The capability of the mechanisms to compensate the unfairness due to disadvantage in the conflict graph, as described in Sec. 3.3, has been evaluated in an experiment in which valuations vi are multiplied by a competition weight w i = e 1.5 i , where e i is the number of edges related to vertex i in the conflict graph of SU i. Figure 6 shows the result for SU c with the random mechanism. It can be seen that, compared with Fig. 4, a much more fair share is achieved.

We have also evaluated the efficiency of these mechanisms by comparing the sum of the mean traffic of the 6 SUs without fairness compensation with that obtained by another mechanism with an efficient choice function implemented

Conclusions

We present two truthful and low complexity mechanisms for real-time spectrum allocations. We show how they can be modified to implement social fairness, maintaining its properties. We also show how they can work when a virtual currency instead of money is used, by controlling the credit of the SUs, making the choice and payment functions dependent on the credit, and redistributing cash to SUs. However, when the mechanisms are dependent on credit, although they are still truthful on a single run, on repeated runs truthfulness does not hold, because successive runs become dependent. Although truthfulness cannot be guaranteed in all situations, our experimental results shown that under certain conditions they still behave truthfully. We are currently working in defining which are the conditions that the credit restriction and the redistribution policy have to fulfil so that the resulting repeated mechanism is truthful.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Conflict graph of simulation set.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Mean traffic of SU c as a function of its h. Deterministic mechanism.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Unit price paid by SU c as a function of its h.

Fig. 7 .

 7 Fig. 7. Mean traffic conveyed by all SUs as a function of h of SU c.

Here the function ωi(vi, k-i) has been used instead of ωi(vi, v-i). However, the proof of the condition expressed by[START_REF] Zhao | A survey of dynamic spectrum access: signal processing, networking, and regulatory policy[END_REF] holds for both functions[START_REF] Archer | Truthful mechanisms for one-parameter agents[END_REF].

This work was supported by the Spanish government through projects TIN2008-06739-C04-02 and TIN2010-21378-C02-02, and by Universitat Politècnica de València through PAID-06-09.


Naeem Khademi
email: naeemk@ifi.uio.no

Michael Welzl

Renato Lo Cigno
email: locigno@disi.unitn.it

On the Uplink Performance of TCP in Multi-rate 802.11 WLANs

Keywords: TCP, 802.11 WLAN, Auto-Rate Fallback

IEEE 802.11 defines several physical layer data rates to provide more robust communication by falling back to a lower rate in the presence of high noise levels. The choice of the current rate can be automatized; e.g., Auto-Rate Fallback (ARF) is a well-known mechanism in which the sender adapts its transmission rate in response to link noise using up/down thresholds. ARF has been criticized for not being able to distinguish MAC collisions from channel noise. It has however been shown that, in the absence of noise and in the face of collisions, ARF does not play a significant role for TCP's downlink performance. The interactions of ARF, DCF and uplink TCP have not yet been deeply investigated. In this paper, we demonstrate our findings on the impact of rate fallback caused by collisions in ARF on the uplink performance of various TCP variants using simulations.

Introduction

Rate adaptation is a mechanism that exploits the multi-rate capability of the physical layer defined in IEEE 802.11 standards to provide more robust communication in the presence of channel failures (e.g. noise, fading, interference). This is achieved by adapting the physical layer (PHY) rate selection based on the channel quality. Four (1∼11 Mbps) and eight (6∼54 Mbps) PHY rates are mandated by 802.11b and 802.11g standards, respectively. The choice of the specific adaptation algorithm is however left up to the vendor in the standard -but this is critical to the system performance.

Several rate adaptation algorithms have been proposed in the literature, most notably Auto-Rate Fallback (ARF) [START_REF] Kamerman | WaveLAN-II: A high-performance wireless LAN for the unlicensed band[END_REF], which chooses the rate based on the number of consecutive successful or unsuccessful transmission attempts (up/down thresholds). For instance, it falls back to a lower rate after two consecutive transmission failures (e.g. ACK frame is not received) and increases the rate after ten successful transmission attempts in Cisco Aironet 350 cards [START_REF] Choi | Cross-layer analysis of rate adaptation, DCF and TCP in multi-rate WLANs[END_REF].

ARF is well known and widely adopted in wireless cards due to its simplicity, but it has been criticized for not being able to distinguish losses due to collision from losses due to channel noise which, in combination with DCF, may affect the overall system performance in typical multi-user wireless scenarios. There has been a significant amount of research on the interaction of DCF and ARF indicating ARF's poor performance at the MAC level, considering constant bitrate UDP traffic scenarios [START_REF] Mathieu Lacage | IEEE 802.11 rate adaptation: a practical approach[END_REF][START_REF] Maguolo | Efficient collision detection for auto rate fallback algorithm[END_REF][START_REF] Xi | Adaptive multirate auto rate fallback protocol for IEEE 802.11 WLANs[END_REF]. However, less work has been done to study the inter-layer dependencies of ARF, DCF and TCP; exceptions are [START_REF] Choi | Cross-layer analysis of rate adaptation, DCF and TCP in multi-rate WLANs[END_REF][START_REF] Choi | On the performance characteristics of WLANs: revisited[END_REF]. These references reveal that, in scenarios with downlink traffic, TCP throughput hardly depends on the number of contending stations.

It has been shown that, in pure TCP downlink scenarios, the number of active stations participating in multiple access contention at an instant of time stays extremely low due to the n:1 traffic ratio of TCP ACK to data packets, resulting in a very low collision rate and therefore gaining the maximum achievable throughput. These results are valid for many typical client-server (e.g. http access) scenarios. Considering today's popular p2p file sharing, VoIP, email attachments and multimedia streaming applications, there is a need to study the overall behavior of the system in the presence of ARF in TCP uplink traffic scenarios, where several stations are contending to access the medium to upload large data packets simultaneously. In this paper we will address such scenarios.

The rest of this paper is organized as follows: in section II we provide some background on the current research trend of rate adaptation mechanisms and their pro's and con's compared to ARF as well as cross-layer interactions of ARF, DCF and TCP. In section III we will evaluate the uplink performance of TCP in presence of ARF with simulations; in section IV we extend our scope to high speed TCP variants and finally, in section V, we propose future work and conclude.

Background

Rate adaptation mechanisms in 802.11 WLANs adapt the PHY transmission rate based on the channel conditions to optimize network parameters such as application-level throughput or power consumption. The former is the main focus of this paper. There have been several proposed algorithms in the literature aiming to achieve this goal [START_REF] Kamerman | WaveLAN-II: A high-performance wireless LAN for the unlicensed band[END_REF][START_REF] Kim | CARA: Collision-aware rate adaptation for 802.11 WLANs[END_REF][START_REF] Mathieu Lacage | IEEE 802.11 rate adaptation: a practical approach[END_REF][START_REF] Pang | A rate adaptation algorithm for IEEE 802.11 WLANs based on MAC-layer loss differentiation[END_REF][START_REF] Holland | A rate-adaptive MAC protocol for multi-hop wireless networks[END_REF].

ARF [START_REF] Kamerman | WaveLAN-II: A high-performance wireless LAN for the unlicensed band[END_REF] is the first published rate adaptation algorithm basically designed for WaveLan II devices and later employed by several 802.11 Wi-Fi NICs. The basic idea of ARF is to increase the PHY transmission rate after a certain number of successful attempts (up threshold) and falling back to a lower rate after a certain number of consecutive failures (down threshold) in addition to setting a timer. After fallback, when the number of per-frame ACKs reaches the up threshold or the timer expires, the PHY rate will be increased. If the first frame transmission after increasing the rate (probing frame) fails, ARF immediately switches back to the previous rate and restarts the timer.

Several problematic issues arise when deploying ARF. First: it takes frame loss as an indication of high channel noise and therefore mistakes collisions for noise. Second: it is too aggressive in rate reduction due to the normally small down threshold value (e.g. one or two) and it can therefore not utilize the total available bandwidth. Third: it attempts to increase the rate after each up threshold (e.g. ten) number of successful transmissions, but this may not be an indication that channel conditions have in fact improved.

Some work has been done to solve these problems [START_REF] Kim | CARA: Collision-aware rate adaptation for 802.11 WLANs[END_REF][START_REF] Mathieu Lacage | IEEE 802.11 rate adaptation: a practical approach[END_REF][START_REF] Pang | A rate adaptation algorithm for IEEE 802.11 WLANs based on MAC-layer loss differentiation[END_REF]. The Collision-Aware Rate Adaptation (CARA) algorithm proposed in [START_REF] Kim | CARA: Collision-aware rate adaptation for 802.11 WLANs[END_REF] exploits the RTS/CTS frames' functionality to differentiate frame collisions from frame transmission failures due to noise. The main idea behind CARA is that a transmission failure of a small RTS frame which is normally encoded at the lowest rate is less likely to be caused by channel noise and most probably the result of a collision, while the transmission failure of a larger data frame followed by a successful RTS/CTS handshake is probably due to channel noise. CARA's practicality in infrastructure-based WLANs is limited because of the mandatory usage of RTS/CTS.

Adaptive ARF (AARF) [START_REF] Mathieu Lacage | IEEE 802.11 rate adaptation: a practical approach[END_REF] is an extension of ARF which decreases the number of probing packet failures to use a higher rate by multiplying the default up threshold (e.g. 10) by two after a probing packet failure. The up threshold is set to its default value after a rate fallback. While AARF decreases the number of failed transmissions and retransmissions, it still inherits other weaknesses of ARF.

Rather than ARF, other rate adaptation mechanisms such as [START_REF] Holland | A rate-adaptive MAC protocol for multi-hop wireless networks[END_REF] require incompatible changes to the 802.11 standard, and therefore they are out of our scope. In this paper we focus on ARF only since it is one of the few open-source and 802.11-compatible mechanisms which is widely employed in wireless NICs.

As already mentioned, ARF's performance has been studied extensively at the PHY/MAC level. However, few works are available that investigate this at the transport layer level focusing on cross-layer interaction of ARF, DCF and TCP [START_REF] Choi | Cross-layer analysis of rate adaptation, DCF and TCP in multi-rate WLANs[END_REF][START_REF] Choi | On the performance characteristics of WLANs: revisited[END_REF]. In these references, it is claimed that ARF has a negligible impact of the performance of TCP thanks to TCP's self-clocking mechanism and the 1/n chance of the AP to gain access to the channel, which decreases the number of stations actively competing for channel access. Since the cases studied in these works are strictly based on download traffic scenarios, they lack a generic conclusion about whether ARF plays a significant role for TCP or not. The impact of ARF on uplink TCP traffic is discussed in the next section.

TCP performance in Multi-rate WLANs

To study the behavior of ARF in the presence of uplink and downlink flows, we performed a set of simulations using ns-2 [START_REF]The Network Simulator NS-2[END_REF] and an extension [START_REF]Wireless Update Patch[END_REF] to provide Auto-Rate Fallback support (AARF) 1 . Ten stations are located at the same 1 Performance evaluations of this paper are made using an improved variant of ARF (AARF) [START_REF] Mathieu Lacage | IEEE 802.11 rate adaptation: a practical approach[END_REF] and mentioned as ARF hereafter. Since AARF inherits the two major problems of ARF (being collision-reactive and aggressive in rate reduction) and only reduces the number of failed probing frames, any problem found in AARF applies to ARF as well.

distance of 10m from an access point to gain an equal signal power. Noise and interference effects are omitted from the scenarios in order to isolate the frame collision events from the other sources of frame loss. The main focal point of this work is to study the potential negative impact of collisions coupling with ARF on TCP performance when the channel condition is relatively good in a simplified and idealized scenario; therefore we have left this study under noisy channel condition which is harder to model as our future work. Common parameters used in different sets of simulations in this paper are brought in Table 1. Figure 1(a) shows the per-second aggregate goodput of these stations under 802.11b channel when each of them is downloading unlimited FTP data carried by a TCP NewReno flow from a server which is connected to the AP via a 100 Mbps wired link2 . As observed, ARF does not affect the performance of download flows for the whole simulation period keeping the aggregate goodput at the maximum level compared to when ARF is disabled. This phenomenon is due to TCP's self-clocking mechanism and the 1/n probability ratio of the AP to gain access to the shared channel.

Simply put, data packets depart from the AP's downstream queue to the wireless stations. Upon successfully receiving a data packet at the destination's NIC, this station's queue will be backlogged with an ACK packet to be sent back after winning in medium access contention. Since the AP has equal probability of access to the channel as any other stations and it is in charge of transferring all data packets, stations' backlogged queues grow only as a consequence of AP's successful contention to access the channel. Collision occur only when already backlogged stations and the AP compete to concurrently access the channel. Using birth-death Markov chains in [START_REF] Choi | Cross-layer analysis of rate adaptation, DCF and TCP in multi-rate WLANs[END_REF][START_REF] Choi | On the performance characteristics of WLANs: revisited[END_REF], it has been shown that TCP's selfclocking mechanism keeps the number of backlogged stations (stations actively participating in contention) in equilibrium at 2-3 contending stations for scenarios with 2-100 wireless stations. This level of contention provides a very low likelihood of collision, which mitigates the negative effect of ARF on downlink's TCP performance. In addition, the almost fixed collision rate causes what the authors called TCP's "scalable performance" for a varying number of nodes.

In contrast to these findings, in upload scenarios, wireless stations are participating in contention to transfer data to the AP and their queues are backlogged with data packets in accordance with their window size. A collision -in this case, between data packets -can be more harmful than in the download scenario, where ACK packets are colliding with each other or with data packets sent from the AP. The packet size also plays a role in determining the impact of collisions. The possible rate downshift triggered by ARF, affecting the transmission of a subsequent large data packet will lead to the under-utilization of the wireless channel bandwidth for a longer period of time compared to the transmission of a short ACK packet. Possibly, this may also result in the other stations' backlogged queue to grow larger resulting in a higher level of collisions.

Figure 1(b) shows the per-second aggregate goodput of uploading stations. It reveals that, when ARF is disabled, uploading stations perceive more fluctuations than the downloading stations because of the earlier mentioned difference in collision probability and impact. However, they achieve a better total performance because they more aggressively try to obtain access to the medium [START_REF] Khademi | Size-based and direction-based TCP fairness issues in IEEE 802.11 WLANs[END_REF]. With enabled ARF in the upload scenarios, we observe a significant goodput reduction where the occurrence of collisions between data packets leads to the rate downshifts (falling to 15-20% of achievable goodput on average). This admits our argument about upload flows being more prone to ARF than download flows. To better understand the characteristics of cross-layer interaction between TCP and ARF, it is necessary to investigate the impact of collisions (packet losses) on TCP dynamism when ARF is enabled or disabled. The impact of the PHY transmission rate on the cwnd size for a single NewReno flow is plotted in Figure 2. Based on a rule-of-thumb the maximum cwnd size is equal to the bandwidth-delay product, which means that a lower PHY transmission rate (channel bandwidth) will lead to a lower maximum cwnd as depicted in Figure 2. Collisions at the MAC layer are perceived as packet errors (bit errors at the PHY layer). Hence, the impact of packet errors on cwnd of a single NewReno upload flow is investigated in Figure 3. The packet error rate perceived at the MAC layer of NICs was chosen to be high enough (PER=0.1) and uniformly distributed in order to present a clearly observable effect. An error model was defined at the MAC layer of AP and each of the wireless nodes to discard the received frames randomly with the uniform probability of e.g. 10%.

Based on Figure 3(a) it is obvious that frame losses due to packet error have a minimal impact on the cwnd size in the absence of ARF. This is because of the 802.11 MAC retransmission mechanism which ensures the receipt of a packet within a time that is normally shorter a TCP retransmission timeout (RTO). Therefore an unsuccessful transmission of a MAC frame and/or its corresponding ACK frame will be compensated for by a frame retransmission, and consequently TCP cwnd will be kept almost intact at moderate values of the MAC frame error rate (PER of 0.1 is high here) . On the contrary, in the presence of ARF, the maximum cwnd drops to 60 packets (Figure 3 There is a difference in the sawtooth behavior of cwnd : with enabled ARF, cwnd growth is slower. This is because the delay (RTT) is increased by the MAC frame transmission and retransmission attempts with a reduced PHY rate; it therefore takes a longer time for a flow under ARF to fill up the AP buffer and experience a TCP packet drop. Figure 4 shows TCP's RTT for this scenario, revealing that retransmission attempts have a negligible impact on the RTT in the absence of ARF while rate downshifts significantly increase the RTT and consequently lead to slower cwnd growth in the presence of ARF. 4 Performance of High-speed TCPs TCP as the dominant transport protocol in the Internet has evolved in recent years to better utilize higher physical layer link speeds. Standard TCP performs poorly in networks with a large bandwidth×delay product. There is a vast number of proposals for overcoming this limitation; some of them have been suggested for standardization in the Internet Engineering Task Force (IETF), and one of them (CUBIC [START_REF] Ha | CUBIC: a new TCP-friendly high-speed TCP variant[END_REF]) is the default mechanism in Linux at the time of writing. These proposals are usually called high speed TCP flavors; in addition to CU-BIC, we pick HTCP [START_REF] Leith | H-TCP: TCP for high-speed and long-distance networks[END_REF] and HSTCP [START_REF] Floyd | Highspeed TCP for large congestion windows[END_REF] for our evaluation (because HTCP is commonly compared with CUBIC, and HSTCP is standardized). These variants can all achieve very large cwnd sizes compared to standard NewReno in long-distance networks.

To give a short overview of these TCP variants, in CUBIC the cwnd is a cubic function of time since the last congestion event with the inflection point set to the cwnd prior to the event. HTCP uses Additive Increase/Multiplicative Decrease (AIMD) to control TCP's cwnd. It increases its aggressiveness (in par-ticular, the rate of additive increase) as the time since the previous loss increases. Finally, in HSTCP, when an ACK is received in the congestion avoidance phase, cwnd is increased by a(w)/w, and when a loss is detected via a triple duplicate ACK, cwnd is decreased by (1-b(w))w, where w is the current window size and the values of the functions a and b get larger and smaller with a growing w, respectively. We evaluated the performance of these high speed TCP flavors under the aforementioned uplink wireless-cum-wired scenario by using the ns-2 Linux TCP patch [START_REF]A Linux TCP implementation for NS2[END_REF] with the original Linux kernel 2.6.16.3 source code.

Figure 5 shows the average aggregate throughput of each TCP variant for a duration of 1000 seconds for a varying number of uploading stations where the wired delay is set to 100ms. In the absence of ARF, all high speed TCP variants perform almost the same and gain the maximum achievable throughput of 650-700 KB/s (Figure 5(a)) and 3.3 Mbps (Figure 5(b)) on average, which are the achievable throughputs associated to the maximum used wireless channel PHY rates of 802.11b and 802.11g (11 Mbps and 54 Mbps) respectively. Due to the limitation of the wireless channel bandwidth, they are not able to perform better than NewReno by letting the cwnd grow to a high value. The lines of HSTCP and New Reno are not distinguishable because their values are almost exactly the same.

When coupled with ARF, their aggregate throughput decline significantly, down to 100-200 KB/s on average in 802.11b (at the same level as NewReno), revealing the fact that rate downshifts as a consequence of collisions supersede the possible performance improvement of high speed TCP variants caused by their faster cwnd growth. It is worth to notice that these high speed TCP variants are designed to perform the same as NewReno for small cwnd sizes. Therefore, having an small cwnd because a low PHY rate (e.g. 1 Mbps in 802.11b) is used most of the time leads the same achievable throughput as with NewReno. In 802.11g, HSTCP performs slightly better than the rest of TCP variants achieving only 1.4 Mbps on average while the throughput of other TCP variants decline to 1 Mbps on average.

It is observable that the total aggregate throughput is almost invariant to the number of wireless nodes participating in contention due to "scalable performance" of TCP in uplink scenarios caused by TCP's self-clocking mechanism (similar to downlink scenarios). However, as justified previously, the impact of the collisions between data packets in uplink scenarios and their consequent effect of rate downshifts on cwnd size is totally different from the collisions between ACK packets in downlink scenarios.

To validate these results for larger bandwidth-delay products, where cwnd is expected to reach larger values, we repeated the simulations for different values of wired delay, ranging from 10 to 500ms with 10 uploading stations. Based on Figure 6 an extensive performance deterioration with enabled ARF is observable. Although different TCP variants perform almost the same in low bandwidth 802.11b wireless channel (Figure 6(a)), they behave differently under 802.11g channel with higher bandwidth where surprisingly, HSTCP and NewReno stand at the better throughput level compared to CUBIC and HTCP (Figure 6(b)).

Without ARF, however, CUBIC and HTCP are able to exploit almost the total provided bandwidth by 802.11g channel while the throughput of NewReno and HSTCP decline as wired delay increases. In 802.11b, all TCP variants gain the total achievable throughput. Conjointly, our results reveal the poor uplink TCP performance in general, and also for high speed TCP variants, in multi-rate 802.11 networks.

Conclusive remarks and future work

The uplink performance of TCP in multi-rate 802.11 networks has been studied and evaluated in this paper. It has been shown that ARF can significantly impede the TCP performance in uplink scenarios in contrast to the assumption that TCP's self-clocking behavior mitigates the impact of ARF in previous work. Real-life tests to validate these findings are left as our future work. Further, newer 802.11 standards with higher available bandwidth must be taken into consideration (e.g. 802.11n) and an analytical model will be proposed in the future. The impact of collisions on TCP performance with ARF under the noisy channel conditions should be studied analytically and experimentally. In addition, TCP could be modified in a way to perform better in the presence of ARF (e.g., we found that a buggy, severely rate limited version of HSTCP in the Linux kernel 2.6.16.3 sometimes performed better than the rest of the TCP variants).

A performance improvement could therefore consider active queue management policies that make use of such a window size limitation; this will be investigated in the future.

Fig. 1 .

 1 Fig. 1. Per-second aggregate goodput of 10 stations in 802.11b (wired delay= 50ms).

Fig. 2 .

 2 Fig. 2. cwnd of a single NewReno upload flow vs. PHY rate.

Fig. 3 .Fig. 4 .

 34 Fig. 3. cwnd of a single NewReno upload flow.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Aggregate throughput of TCP variants vs. number of nodes.

Table 1 .

 1 Simulation parameters

	MAC protocol IEEE 802.11b IEEE 802.11g
	Packet size	1500 bytes
	Propagation model	TwoRayGround
	Interface queue	DropTail (50 packets size)
	CWMin	32	16
	CWMax	1024
	SIFS	10 µs
	DIFS	50 µs	28 µs
	Slot time	20 µs	9 µs
	RTS/CTS option	Disabled

Unless otherwise noted, the same parameter settings are also applied in all other simulations in this paper.


Diego Pacheco-Paramo

Vicent Pla
email: vpla@dcom.upv.es

Vicente Casares-Giner

Jorge Martinez-Bauset

Optimal Joint Call Admission Control with Vertical Handoff on Heterogeneous Networks

Keywords: Heterogeneous networks, Markov decision process, Joint call admission control

A joint management of radio resources in heterogeneous networks is considered to raise efficiency. In this paper we focus on joint schemes for admission control and access technology selection using vertical handoff. We study a system where both streaming and elastic traffic are supported, and two radio access technologies covering the same areas are available: TDMA and WCDMA. Optimal solutions for different optimization criteria which can be expressed in terms of blocking probabilities and throughput are found and properly described, and a new heuristic policy is proposed. Finally, in order to provide some understanding of the cost of a single vertical handoff, a new optimization criteria is defined where its cost is found in relation to that of voice and data blocking.

Introduction

Coexistence of several access technologies demands the study of joint radio resource management (JRRM), given the objective of providing users with a permanent connection with the best possible performance [START_REF] Wu | A survey on common radio resource management[END_REF]. Since coordinated control of several radio access technologies improves the use of limited resources [START_REF] Tolli | Performance Evaluation of Common Radio Resource Management[END_REF], a challenge that arises is to find the most appropiate scheme for the main functions of JRRM, such as joint call admission control (JCAC) and vertical handoff (VH). Joint call admission control (JCAC) proposals such as those in [START_REF] Pillekeit | Force-based Load Balancing in Co-located UMTS/GSM Networks[END_REF] and [START_REF] Suleiman | Load Balancing in the call admission control of heterogeneous wireless networks[END_REF], show the improvement in network's stability based on a load balancing scheme for a heterogeneous network, but they do not make use of the advantages of vertical handoff. The complexity that vertical handoff adds to the system is commented in [START_REF] Falowo | Joint Call Admission Control Algorithms: Requirements, Approaches, and Design Considerations[END_REF] and several vertical handoff characteristics and algorithms are reviewed in [START_REF] Márquez-Barja | An Overview of Vertical Handover Techniques: Algorithms, Protocols and Tools[END_REF]. Most of vertical handoff schemes like [START_REF] Stevens-Navarro | Comparison between Vertical Handoff Decision Algorithms for Heterogeneous Wireless Networks[END_REF][START_REF] Goyal | A Dynamic Decision Model for Vertical Handoffs across Heterogeneous Wireless Networks[END_REF] base decisions on user preferences. We believe that the study of vertical handoff decision from the operator's point of view is a constructive and important issue.

In this article, we are interested in finding an optimal scheme for a heterogeneous network with two technologies, and where both streaming and elastic traffic are supported. In [START_REF] Yu | Optimal Joint Session Admission Control in Integrated WLAN and CDMA Cellular Networks with Vertical Handoff[END_REF] a Markov model is used for an heterogeneous network (WLAN and CDMA), and a linear programming method is used to solve the optimization problem. That paper explicitly acknowledges the inherent complexity of the problem, which could make it computationally intractable for large systems. This is a main concern in this work. Therefore, we have simplified some characteristics of the system in such a way that results can be extrapolated to more complex systems. Several solution methods for similar problems have been used, such as genetic algorithms [START_REF] Karabudak | A call admission control scheme using genetic algorithms[END_REF] or fuzzy-based solutions [START_REF] Agusti | A fuzzy-neural based approach for joint radio resource management in a beyond 3G framework. 1st Internation Conference on Quality of Service in heterogeneous in Wire/Wireless networks[END_REF], [START_REF] Falowo | Fuzzy Logic Based Call Admission Control for Next Generation Wireless Networks[END_REF]. In this work, policy iteration is used since it allows to discern the main characteristics of the optimal policies in a per iteration basis as several parameters vary.

The last part of the article is focused on the cost of a single vertical handoff, and how it relates to other costs such as those of blocking voice or data calls. Other solutions define a monetary cost of vertical handoff, and users decide according to this and other parameters [START_REF] Hasswa | Generic Vertical Handoff Decision Function for Heterogeneous Wireless Networks[END_REF]. In contrast, our interest is to explore the impact of this cost from the operator's point of view in relation to other performance parameters such as the blocking probabilities. The paper is structured as follows. In Section 2 we describe the Markov model of the system and the types of vertical handoff used. The solution method is described in Section 3. In Section 4 the optimal policies are analyzed and some heuristics are proposed and compared with optimal solutions. A study of the cost of performing a vertical handoff in relation to those of blocking voice and data calls is done in Section 5. Finally, Section 6 concludes the work.

System description and Markov model

The system of our interest is composed by two radio access technologies, TDMA and WCDMA. Additionally, both technologies provide voice and data services in the same area as it was proposed in [START_REF] Gelabert | A Markovian Approach to Radio Access Technology Selection in Heterogeneous Multiaccess/Multiservice Wireless Networks[END_REF]. As a call arrives to the system, a decision has to be made about if it is served in one or another technology.

Both service users (voice and data) are defined by a Poisson arrival process, with rate λ v (λ d ) for voice (data). The service time for voice is exponentially distributed with mean 1/µ v . On the other hand, because data is best modelled as elastic traffic, its sojourn times will depend on the available resources. Therefore, the mean service time for data is exponentially distributed with mean 1/F (σ), where σ is the average size of the information sent and F refers to its division by the transmission rate.

State space

The state vector of the continuous time Markov chain (CTMC), is s = (s 1 ,s 2 ,s 3 ,s 4 ) where s 1 represents the number of ongoing voice sessions on TDMA, s 2 the data sessions on TDMA, s 3 the voice sessions on WCDMA and s 4 the data sessions on WCDMA. We define C as the fixed number of channels per slot in TDMA. A voice session will always use a whole channel, so there can only be C simultaneous voice sessions on this technology. On the other hand, data sessions can share a channel when TDMA is at full capacity, in such a way that n c data sessions can be served per channel. This means that we can have a maximum of C • n c simultaneous data sessions in TDMA. According to this, the first condition that a state must fulfill to be feasible is given by

s 1 • n c + s 2 ≤ n c • C. (1)
The capacity on WCDMA is defined by

s 3 W/BR w,v (E b /N 0 ) v + 1 -1 + s 4 W/BR w,d (E b /N 0 ) d + 1 -1 ≤ η ul , (2)
where W is the chip rate, BR w,x is the bit rate used for transmitting service x in WCDMA, (E b /N 0 ) x is the bit energy to noise density required for service x, and η ul is the uplink cell load factor. This is the same expression used in [START_REF] Gilhousen | On the Capacity of a Cellular CDMA System[END_REF]. Considering that each technology has independent resources, the feasible combination of data and voice users can be calculated for each technology separately. We define S as the set of feasible states, that is all the state vectors s that fulfill the conditions defined in (1) and (2).

System Metrics

The parameters that define performance are the voice blocking probability, the data blocking probability, and the total throughput. The total blocking probability refers to the probability that the system is in a state where all calls are blocked, independent of the service it requires. In the same way the voice (data) blocking probability refers to the probability of being in those states where voice (data) calls are blocked. To calculate the throughput we have to consider that the bit rate is independent for each service and technology and that data sessions in TDMA can share a channel, which is reflected in the min (C -s 1 , s 2 ) factor of the following equation:

T h = s∈S P (s) s 1 BR t,v + s 3 BR w,v + min(C -s 1 , s 2 )BR t,d + s 4 BR w,d , (3)
where BR x,y is the bit rate used for transmitting service y (voice or data) in technology x (TDMA or WCDMA).

Vertical Handoff

Inferred from the optimal policies obtained in [START_REF] Pacheco-Paramo | Optimal Radio Access Techology Selection on Heterogeneous Networks[END_REF] The system that uses vertical handoff types I and II is called VH-A, the one that uses all types is called VH-B, and the one that does not use vertical handoff is called NVH.

Optimization problem

For each state s ∈ S, a decision must be made about if an arriving call should be admitted according to the service required. In a Markov decision process, a policy π defines which actions a=(a v s ,a d s ) should be taken at each state s for voice a v s and data a d s arrivals. It should be clear that decision epochs occur only at arrivals. The main objective is to find among the possible policies the one that optimizes a chosen function.

The set of actions A defines the possible values for a v s and a d s , and it is defined in Table 1. Table 2 shows the transition rates r su from state s to state u (s, u ∈ S).

a v s u rsu 1 s + e1 λv 2 s + e3 λv 3 s + N • e2 + e3 -N • e4 λv a d s u rsu 1 s + e2 λ d 2 s + e4 λ d 4 s -e1 + e2 + e3 λ d

Cost function

Since our interest relies on data and voice blocking probabilities, as well as the total throughput, we have defined two different objective functions. The first one, is the weighted sum of the voice and data blocking probabilities,

F BP = BP voice • α + BP data • (1 -α). (4)
The parameter α, 0 ≤ α ≤ 1, is the one responsible for giving more or less weight to each blocking probability. Thus, α relates the way in which the blocking probabilities will be minimized. The cost function associated to the objective function for each feasible state s is

cost(s) = 1 -(α • F v (a s ) + (1 -α) • F d (a s )), (5)
where F x (a s )=1 if a s is 1 or 2, and 0 otherwise, being x the service. The second objective function is the aggregated throughput, so in that case we try to maximize the value defined by (3). The reward for each state s is

cost(s) = s 1 BR t,v + s 3 BR w,v + min(C -s 1 , s 2 )BR t,d + s 4 BR w,d . (6)

Solution method

The method used to find the optimal policy π opt is policy iteration [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. This method can search among the finite group of possible policies for the MDP and find the optimal in a finite number of steps. The relative values V allow to relate the cost obtained in the actual state with costs expected from future actions, and are found using the next equation:

c π -c π • e + V π R T π = 0. ( 7
)
The c π in the previous expression is the vector of costs associated to being in each state, R π is the transition matrix, and c π is the value of the objective function for policy π. Once V and c π are found using [START_REF] Stevens-Navarro | Comparison between Vertical Handoff Decision Algorithms for Heterogeneous Wireless Networks[END_REF], it is possible to find the action on each state that will minimize the objective function using the next expression:

min a c a s -c π + s =u r a s,u (v u π -v s π ) , (8)
where v u π and v s π are the relative values for states u and s respectively when the policy π is used, c a s is the cost associated to state s when action a is taken, r a s,u

is the transition rate from state s to state u, when the action for state s is a.

The set of actions will define a new policy and the process is repeated until the optimal policy is found.

Optimal Policy Analysis

To obtain and analyze the optimal solutions, the scenario that will be used unless otherwise stated is defined in When using both optimization functions, the blocking function defined in (4) and the throughput function defined in (3), while varying λ v and λ d the main characteristics of the optimal policies for both MDPs can be summarized as follows: service action voice Send to WCDMA or use VH type I. data Send to TDMA while no sharing is needed.

If so, use VH type II or send to WCDMA.

However, there are differences for each case that should be analysed.

Blocking Function Optimization

When the blocking function is optimized and λ v varies from 0.005 to 0.095, the number of states that are left unused grows with λ v for both MDPs. For MDP VH-B it grows from 32.1% to 50.4% and for MDP VH-A grows from 10.4% to 41.7%. Therefore, MDP VH-B organizes calls in a more effective way given the impact of vertical handoff for departures. Also, there is some blocking of voice calls even when there is space left for the highest values of λ v , when its influence is bigger on the optimization function. When λ v =0.095, 1.2% of usable states block voice calls with MDP VH-B, while 1% do it with MDP VH-A. When λ d grows from 0.05 to 0.225, the percentage of unused states for MDP VH-A remains constant in 41.6%, while it decreases from 49.4% to 39.6% with MDP VH-B. This decrease occurs because of vertical handoff type III, which is used more often as λ d grows. Also for high values of λ d , there is some blocking of data calls even when there is space available. For λ d =0.225, 2.56% of usable states block data calls for MDP VH-A and 2.98% of states do this for MDP VH-B.

Throughput Optimization

When the throughput is optimized and λ v grows from 0.005 to 0.095, the percentage of unused states also grows from 16 % to 41.7% for MDP VH-A, but decreases from 61.2% to 49.5% for MDP VH-B. Also, there is some voice calls blocking while there is available space left when λ v is low. For λ v =0.005, 0.71% of the usable states block voice calls for MDP VH-A while 0.25% of states do it for MDP VH-B. Therefore MDP VH-B manages resources in a more organized way, since the number of states left unused is always higher.

When λ d grows from 0.05 to 0.225, the percentage of unused states also grows from 41.6% to 43% for MDP VH-A and from 45.4% to 47.2% for MDP VH-B. Also, since voice calls contribute less to the total throughput, some states block voice calls when there is space left. This occurs for high values of λ d . When λ d =0.225, 0.7% of usable states block voice calls for MDP VH-A, while 0.56% of states do it for MDP VH-B.

Result Analysis for Vertical Handoff MDPs

Based on the results obtained in sections 4.1 and 4.2 we propose two new heuristic policies that make use of their main characteristics. Heuristic VH-A makes use of vertical handoff types I and II, as it was seen for the optimal policies found using MDP VH-A. On the other hand, Heuristic VH-B also includes vertical handoff types III and IV, as it was done by the optimal policies obtained using MDP VH-B.

Heuristic

Event Action

Heuristic

Voice arrival • Send to WCDMA. In this section we compare the results obtained by the two new heuristic policies with those of the MDPs that use vertical handoff and the one that does not (MDP NVH). In Fig. 1(a) it is shown the blocking function for the MDPs and the two heuristic policies when λ v varies from 0.005 to 0.095. It is evident that the use of vertical handoff enhances the system behavior, since both heuristic have a lower optimal value for all λ v . Also, if we restrict BP v and P B d below 2%, λ v can grow up to 0.07 for Heuristic VH-A, while for MDP NVH the maximum λ v was of 0.062, a difference of about 1 Erl. However, it is difficult to notice the effect of vertical handoff for service completion in Fig. 1(a), since the improvement is not as pronounced as one could expect.

In Fig. 1(b) is shown the blocking function as λ d varies from 0.05 to 0.225. Again, the performance of the heuristic policies is better than that of MDP NVH. When λ d =0.225, the value of the blocking function for the heuristics VH-A and VH-B is very similar, and 85 % of the value obtained by MDP NVH. As λ d grows, the difference between the solution found by the MDPs with vertical handoff differ more from the heuristics and from the optimal solution found using MDP NVH. This is due to the rise of P B v on the heuristic policies, which is managed by the optimal policies by creating some data blocking states. When optimizing throughput, there is only a significant improvement of the solutions with vertical handoff over MDP NVH for the highest values of λ v as can be seen on Fig. 2(a). When λ v =0.095, the throughput of the policies that use vertical handoff are very similar among them and above the value of MDP NVH for about 1.7 %. This improvement represents about 44.3 kbps, almost 1 data channel or 4 voice channels. However, for this value of λ v , P B v and P B d are way above acceptable levels, with 7.5% and 3.8% respectively for the solution of MDP VH-B, the one with the best results. Also, vertical handoff improves P B v and P B d . Restricting these values to 2%, the maximum acceptable λ v for MDP VH-A is around 0.068, while for MDP NVH is of 0.064. This clearly indicates that the rearrangemet done by vertical handoff improves the throughput by raising the maximum load capacity of the system. In Fig. 2(b) appears the throughput for the same policies as λ d varies from 0.05 to 0.225. In this case, the improvement in throughput of the new policies over MDP NVH is very low. Also, the values for P B d are very similar, showing how difficult it is for the system to deal with high rates of λ d . However, there is a significant difference in the values obtained for P B v . When P B v reaches 2% for the solution obtained with MDP NVH, the value of Heuristic VH-A is of 0.5 %, so there is a considerable reduction. This result also shows that the improvement on the throughput as λ d grows is given by voice calls, which contribute less to the total throughput given their data rate.

Cost of the Vertical Handoff

In this section, a new objective function based on the blocking rates and the vertical handoff rate is defined as:

F V H = θ • ζ V B + (1 -θ) • ζ DB + C V H • ζ V H , (9)
where θ, 0 ≤ θ ≤ 1, is the factor that defines the cost for blocking a single voice or data call, and ζ V B and ζ DB are the mean voice and data blocking rates. In the same way, C V H is the cost of performing a single vertical handoff, and ζ V H is the mean rate of vertical handoffs performed. Hence, by assigning values to θ and C V H , a new optimal policy that minimizes F V H can be found using a Markov decision process.

Markov decision process for VH cost

In this section we define three new MDPs based on [START_REF] Yu | Optimal Joint Session Admission Control in Integrated WLAN and CDMA Cellular Networks with Vertical Handoff[END_REF]. The first one does not use vertical handoff (MDP BR), the second one uses vertical handoff types I and II (MDP C-1), and the last one uses all four types of vertical handoff (MDP C-2). These MDPs are different from those exposed before because of their objective functions. The state space for all of them S is defined by ( 1) and ( 2) and the set of actions A is that of Table 1 for MDP C-1 and MDP C-2, while the set of actions for MDP BR does not include actions 3 and 4 from A of Table 1. The cost function associated to the objective function for each feasible state s for MDP BR is

cost(s) = λ v • G(a v s ) • θ + λ d • G(a d s ) • (1 -θ), (10)
for MDP C1 is [START_REF] Agusti | A fuzzy-neural based approach for joint radio resource management in a beyond 3G framework. 1st Internation Conference on Quality of Service in heterogeneous in Wire/Wireless networks[END_REF] and for MDP C2 is

cost(s) = λ v • G(a v s ) • θ + λ d • G(a d s ) • (1 -θ) + C V H • (λ v • R(a v s ) + λ d • R(a d s )),
cost(s) = λ v • G(a v s ) • θ + λ d • G(a d s ) • (1 -θ) + C V H • (λ v • R(a v s ) + λ d • R(a d s )) + C V H • (T (s v T DM A ) + T (s d T DM A ) + T (s v W CDM A ) + T (s d W CDM A )), ( 12
)
where the coefficients are explained in Table 4.

. T (s v W CDM A ) = s3 • µv. • Otherwise T (s v W CDM A ) = 0. T (s d W CDM A )
Indicates the rate of calls that • If the conditions for vertical handoff suffer vertical handoff when a type III are fulfilled once a data call data call is served on WCDMA is served on WCDMA, while the system is on state s.

T (s d W CDM A ) = s4 • BR w,d /σ. • Otherwise T (s d W CDM A ) = 0.

Results Analysis

In this section, policy iteration is used to solve the MDPs. The reference scenario is defined in Table 3 with θ= 0.5, which means that the cost of blocking voice and data calls is the same.

In Fig. 3 we can see the optimal values for each of the MDPs introduced in the last section for different values of C V H . MDP C2 has the lowest optimal value when C V H =0 and is followed closely by MDP C1. However, as C V H grows, the value of MDP-R2 rapidly grows surpassing MDP C1 and MDP BR because of the large amount of vertical handoff of types III and IV performed. In fact, for values of C V H as low as 0.01, the optimal value of MDP C2 is higher than that of MDP BR. This means that when C V H is higher than this, it is not justified to use the policy this MDP uses. Keeping in mind that the cost of blocking voice and data calls is of 0.5, we could say that it is necessary that the cost of blocking voice and data calls to be about 50 times higher than that of vertical handoff for this policy to be useful. On the other hand, results found using MDP C1 vary slowly and are limited by those of MDP BR. This occurs because if it is the vertical handoff which causes the objective function to grow, MDP C1 can always choose not to use it, and then its optimal policy will be identical to that of MDP BR. The interesting point here is to find that value of C V H that makes both MDPs to reach the same optimal policy and therefore the same results. For Fig. 3, when C V H =0.9, both policies are the same. This means that when the cost of vertical handoff is about 1.8 times higher than that of blocking voice or data calls, vertical handoff is not useful anymore. It is interesting to notice that when C V H =0, the optimal policies of MDP C1 and MDP C2 are very similar to those of MDP VH-A and MDP VH-B, even though the objective functions are different. Therefore, the values of parameters such as throughput and blocking probabilities (BP v and BP d ) are similar as well. As C V H grows, the performance of these parameters degrade, and this happens at a faster rate for MDP C2 than for MDP C1. Hence, while the ratio of voice/data blocking cost to C V H is high, one could expect that the heuristic policies VH-A and VH-B will fairly represent the optimal policies. This last remark is true even for a higher rank of ratios in the case of MDP C1 and the heuristic VH-A, for the reasons explained earlier.

Conclusions

We have studied the optimal joint call admission control policy with vertical handoff in a system with heterogeneous technologies (WCDMA and TDMA) and services (voice and data). Two optimization functions were used, a blocking function and a throughput function. Four vertical handoff types are defined according to the service and the event that triggers them. Some simplifications such as technologies' capacity or coverage areas were restricted in order to obtain computational tractability. However, the solutions found apply for bigger systems and are useful as an starting point for more complex problems where areas do not always overlap or more networks are available. The analysis of the optimal policies allowed us to define new heuristic solutions that are simple enough as it is required, while at the same time improve the performance of other schemes that do not use vertical handoff. At the same time, it was shown how heuristic solutions perform very close to the optimal solutions for a wide range of arrival rates and both optimization criteria. Finally, a study that combines the cost of blocking voice and data calls to that of performing vertical handoff was done. It should be noted that this is a very important topic when resource availability and utilization efficiency are main concerns, that is, the optimization and decisions are made from the operator's point of view, whose needs are important to understand. We concluded that only certain types of vertical handoff are useful, and only while the ratio blocking cost/handoff cost is between a specific range.

  λ d variation.

Fig. 1 .

 1 Fig. 1. Blocking Function Optimization.

  λ d variation.

Fig. 2 .

 2 Fig. 2. Throughput Optimization.

Fig. 3 .

 3 Fig. 3. Optimization values for various CV H .

Table 1 .

 1 set of actions A for MDPs with vertical handoff

	value action
	0 Block call
	1 Send call to TDMA
	2 Send call to WCDMA
	3 Vertical Handoff type I
	4 Vertical Handoff type II

Table 2 .

 2 Transition rates from state s to u

Table 3 .

 3 The values are chosen in order to keep the problem computationally tractable while at the same time keeping capacity proportionality among the technologies used. In this section we study MDP VH-

A and MDP VH-B which are based on the systems defined in section 2.3. Since MDP VH-B performs vertical handoff types III and IV each time a departure occurs, they share the same action set A of Table

1

. The state space S for both MDPs is defined by (

1

) and (

2

).

Table 3 .

 3 Initial Scenario for Policy Iteration.

	WCDMA	TDMA
	W =3.84 Mcps	C = 4
	(E b /N0)v=14 dB	nc= 2
	(E b /N0) d =14 dB BRt,v=12.2 kbps
	BRw,v=12.2 kbps BR t,d =44.8 kbps
	BR w,d =44.8 kbps
	η ul = 1
	Clients
	λv= 0.025
	λ d = 0.134
	µv= 0.0083
	σ= 1 Mb

  • If it is not possible, use VH type I. • If it is not possible, send to TDMA. VH-A Data arrival • Send to TDMA if no channel sharing is needed. • If there is channel sharing, use VH type II. • If it is not possible, send to WCDMA. • If it is not possible, send to TDMA.

Heuristic Voice arrival • Send to WCDMA. • If it is not possible, use VH type I. • If it is not possible, send to TDMA. VH-B Data arrival • Send to TDMA if no channel sharing is needed. • If there is channel sharing, use VH type II. • If it is not possible, send to WCDMA. • If it is not possible, send to TDMA. Voice departure • Use VH type III if departs from WCDMA • Use VH type IV if departs from TDMA Data departure • Use VH type III if departs from WCDMA • Use VH type IV if departs from TDMA

Table 4 .

 4 Coefficients for optimization function ) Indicates the rate of calls that • If the conditions for vertical handoff suffer vertical handoff when a type III are fulfilled once a voice call voice call is served on WCDMA is served on WCDMA, while the system is on state s

	SYMBOL DEFINITION	VALUE
	G(a x s )	Indicates if s is a blocking	• If action a x s is blocking, G(a x s )=1.
		state for service x	• Otherwise G(a x s )=0.
	R(a x s )	Indicates the number of calls	• If a x s =3, and all the conditions for
		that suffer vertical handoff	vertical handoff type I are fulfilled,
		when a call of service x arrives R(a v s ) = N .
		while the system is on	• If a x s =4, and all the conditions for
		state s.	vertical handoff type II are fulfilled,
			R(a d s ) = 1.
			• Otherwise, R(a x s ) = 0.
	T (s v T DM A ) Indicates the rate of calls that • If the conditions for vertical handoff
		suffer vertical handoff when a type IV are fulfilled once a voice call is
		voice call is served on TDMA served on TDMA, T (s v T DM A ) = s1 • µv.
		while the system is on state s. • Otherwise T (s v T DM A ) = 0.
	T (s d T DM A ) Indicates the rate of calls that • If the conditions for vertical handoff
		suffer vertical handoff when a type IV are fulfilled once a data call is
		data call is served on TDMA	served on TDMA,
		while the system is on state s. T (s d T DM A ) = min(C-s1,s2) • BR t,d /σ.
			• Otherwise T (s d T DM A ) = 0.
	T (s v W CDM A

Acknowledgements

This work was supported by the Spanish Government, the European Commission and Universidad Politécnica de Valencia through projects TIN2010-21378-C02-02, TIN2008-06739-C04-02/TSI and PAID-06-09.