tceic.com

学霸学习网 这下你爽了

学霸学习网 这下你爽了

- A BICRITERION APPROACH FOR ROUTING PROBLEMS IN MULTIMEDIA NETWORKS
- A Hybrid Routing Approach for Opportunistic Networks
- 3 Mining Heterogeneous Information Networks A Structural Analysis Approach--V14-02-03-Sun
- a hybrid approach for feature subset selection using neural networks and ant colony optimization
- Distributed Clustering in Ad-hoc Sensor Networks：A Hybrid, Energy-Efficient Approach
- A Hybrid Evolutionary Approach to the University Course Timetabling Problem
- A route-directed hybrid genetic approach for the vehicle routing problem with time windows
- A Hybrid Framework for Image Segmentation Using Probabilistic Integration of Heterogeneous
- A hybrid approach for location-based service discovery in vehicular ad hoc networks
- Hybrid schemes of homogeneous and heterogeneous classifiers for cursive word recognition

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the Mini-Conference at IEEE INFOCOM 2010

A hybrid decision approach for the association problem in heterogeneous networks

Salah Eddine Elayoubi Eitan Altman Majed Haddad, Zwi Altman

Orange Labs INRIA Sophia Antipolis Orange Labs 38-40 Rue du General Leclerc 10 route des Lucioles 38-40 Rue du General Leclerc 92130 Issy-Les-Moulineaux, France 06902 Sophia Antipolis, France 92130 Issy-Les-Moulineaux, France salaheddine.elayoubi@orange-ftgroup.com Eitan.Altman@sophia.inria.fr {majed.haddad,zwi.altman}@orange-ftgroup.com

Abstract—The area of networking games has had a growing impact on wireless networks. This re?ects the recognition in the important scaling advantages that the service providers can bene?t from by increasing the autonomy of mobiles in decision making. This may however result in inef?ciencies that are inherent to equilibria in non-cooperative games. Due to the concern for ef?ciency, centralized protocols keep being considered and compared to decentralized ones. From the point of view of the network architecture, this implies the co-existence of network-centric and terminal centric radio resource management schemes. Instead of taking part within the debate among the supporters of each solution, we propose in this paper hybrid schemes where the wireless users are assisted in their decisions by the network that broadcasts aggregated load information. We derive the utilities related to the Quality of Service (QoS) perceived by the users and develop a Bayesian framework to obtain the equilibria. Numerical results illustrate the advantages of using our hybrid game framework in an association problem in a network composed of HSDPA and 3G LTE systems.

I. I NTRODUCTION In order to handle the growing wireless traf?c demand, operators are often faced with the need to install new base stations. This could result in splitting cells into smaller ones, or in having several base stations covering the same cell. The second option may be preferred when the traf?c has high variability (in time and space) in which case it may be advantageous to have the possibility to allocate resources from both base stations to any point in the cell. This ?exibility comes at a cost of having to include an access control that takes the proper association decisions for the mobiles, that of deciding to which base station (BS) to connect. To achieve ef?cient use of the resources, these decisions should be based not only on the current system state but also on expected future demand which may interact with traf?c assigned in the present. We wish to avoid completely decentralized solutions of the association problem in which all decisions are taken by the mobiles, due to well known inef?ciency problems that may arise when each mobile is allowed to optimize its own utility. This inef?ciency is inherent to the non-cooperative nature of the decision making. On the other hand, we wish to delegate to the mobiles a large part in the decision making in order to alleviate the burden from the base stations. The association schemes actually implemented are fully centralized: the operator tries to maximize his utility (revenue)

by assigning the users to the different systems [1]-[3]. However, distributed RRM mechanisms are gaining in importance: Users may be allowed to make autonomous decisions in a distributed way. This has lead to game theoretic approaches to the association problems in wireless networks, as can be found in [4]-[8]. The potential inef?ciency of such approaches have been known for a long time. The term ”The Tragedy of the Commons” has been frequently used for this inef?ciency [9]; it describes a dilemma in which multiple individuals acting independently in their own self-interest can ultimately destroy a shared limited resource even when it is clear that it is not in anyone’s long term interest for this to happen. We propose in this paper association methods that combine bene?ts from both decentralized and centralized design. Central intervention is needed during severe congestion periods. At those instants, we assume that the mobiles follow the instructions of the base stations. Otherwise the association decision is left to the mobiles, who make the decision based on aggregated state information from the base stations. The decision making is thus based on partial information that is signaled to the mobiles by the base station. A central design aspect is then for the base stations to decide how to aggregate information which then determines what to signal to the users. Note that this decision making at the BS can be viewed as a mechanism design problem, or as a Bayesian game. II. P ROBLEM STATEMENT A. System description We consider a network composed of S systems operated by the same operator. Even if the model we develop is applicable to different kinds of situations, we will focus on the more realistic and cost effective case where the operator uses the same cell sites to deploy the new system (e.g. 3G LTE), while keeping the old ones (e.g. HSDPA). As, in each cell, there are different radio conditions following the position of the user regarding the cell site, the peak throughput that can be obtained by the user connected to system s, if served alone by a cell, differs following his position in the cell, as illustrated in Figure 1 for a cell served by HSDPA and 3G LTE. For simplicity, we consider that there are N classes of radio conditions and that s users with radio condition n have a peak rate Dn if connected to system s. The network state is then de?ned by the vector:

978-1-4244-5837-0/10/$26.00 ?2010 IEEE

Authorized licensed use limited to: BEIHANG UNIVERSITY. Downloaded on July 17,2010 at 15:13:35 UTC from IEEE Xplore. Restrictions apply.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the Mini-Conference at IEEE INFOCOM 2010

1 1 S S s M = (M1 , ..., MN , ..., M1 , ..., MN ), Mn being the number of users with radio condition n connected to system s.

user connected to a system stays within it until the end of his communication in order to avoid vertical handovers and their signaling overhead. Furthermore, even if the decision is distributed, all users will have the same policy and learn together how to enhance it. However, a policy change will occur after an observation time, long enough to insure that the steady state of the network has been reached. Note also that users can connect to a system only if there is room in it, otherwise they are directed by the network to an available system or blocked if all systems are saturated. III. U TILITIES We analyze a system offering streaming calls. The goal of a streaming user is to achieve the best throughput, knowing that the different codecs allow a throughput between an upper (best) Tmax and a lower (minimal) Tmin bounds. His utility is thus expressed by the quality of the streaming ?ow he receives, which is in turn closely related to his throughput. Indeed, a streaming call with a higher throughput will use a better codec offering a better video quality. This throughput depends not only on the peak throughput, but also on the evolution of the number of calls in the system where the user decides to connect. Note that a user that cannot be offered this minimal throughput in neither of the available systems is blocked in order to preserve the overall network performance. A. Steady state analysis 1) Instantaneous throughput: The instantaneous throughput obtained by a user in a system depends on the state of the system. The throughput of a user with radio condition class n connected to system s is given by:

s ts (M) = min Dn n

Fig. 1.

LTE and HSDPA peak throughputs for different user positions.

We assume that the network broadcasts a partial load information l (1 ≤ l ≤ L), e.g., an aggregated load information indicating for each system if it is in low, medium, or high load state. An example of this load information is described in Figure 2 for a network composed of HSDPA and LTE systems.

G(M)

N m=1 S r=1 r Mm

, Tmax

(1)

Fig. 2.

Aggregated load information.

B. Policy de?nition As stated before, users are only aware of the load information l sent by the network. Their policies are then based on this information. Let P be a policy de?ned by the actions taken by mobiles in the different load conditions. P is a N × L matrix whose element Pnl is equal to s if class-n users connect to system s when the network broadcasts information l. Let A be the space of feasible states, P be the set of all possible policies and let L be the set of load information. An assignment f : A → L speci?es for each network state M the corresponding load information f (M). On the other hand, when the load information is equal to l and the policy is P, we can determine the system to which users of class n will connect by the value Pnl . As an example, knowing the function f (.) and the policy P, if the network is in state M, a class n user will connect to system Pnl , where l = f (M). There are some important remarks to keep in mind when speaking about policies. The ?rst is that we suppose that a

where G(M) is the scheduler gain. Note here that the admission control will insure that ts (M) ≥ Tmin by blocking new n arrivals. The space of feasible states A is thus the set of all states M where this constraint is ensured:

N m=1

G(M)

S r=1

r Mm

≤

Tmin s , ?n, s|Mn > 0 s Dn

(2)

2) Steady state probabilities: The throughput achieved by a user depends on the number of ongoing calls. This latter is a random variable whose evolution is governed by the arrival and departure processes. We assume that the arrival process of new connections with radio condition n is Poisson with rate λn . Each arriving user makes a streaming connection whose duration is exponentially distributed with parameter 1/μ. Within the space of feasible states A, transitions are due to: ? Arrivals of users of radio condition n. Let s Gn (M) denote the state of the system if we add one mobile of radio conditions n to system H 1 1 s s = (M1 , ..., MN , ..., M1 , ..., Mn + s: Gn (M) s S S 1, ..., MN , ..., M1 , ..., MN ). The transition from state M s to Gn (M) happens if the policy implies that system s is to be chosen for the load information corresponding to

Authorized licensed use limited to: BEIHANG UNIVERSITY. Downloaded on July 17,2010 at 15:13:35 UTC from IEEE Xplore. Restrictions apply.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the Mini-Conference at IEEE INFOCOM 2010

s state M, and if the state Gn (M) is an admissible state. The corresponding transition rate is thus equal to: s s q(M, Gn (M)|P) = λn · IPn,f (M) =s · IGn (M)∈A

The remaining transition rates remain equal to the original transitions:

s s qn (M, Gn (M)|P) = q(M, Gn (M)|P), ?s

(3)

?n , s

?

where IC is the indicator function equal to 1 if condition C is satis?ed and to 0 otherwise. s Departures of users of radio condition n. Let Dn (M) denote the state with one less mobile of class (n, s). The s transition from state M to Dn (M) is equal to:

s s s q(M, Dn (M)|P) = Mn · μ · IMn >0

and

s s qn (M, Dn (M)|P) = q(M, Dn (M)|P), ?n , s = s ?s ? ?s 2) De?ne matrix Qs of elements qn (M, M ) de?ned above n and with diagonal elements as in equation (5):

(4)

qn (M, M|P) = q(M, M|P) ?s

s Under policy P , the volume of information In (M|P) sent by system s users subject to radio conditions n starting from state M is then equal to the volume of information sent between state M and the absorbing state As . These values can be calculated by solving the n set of linear equations for all states M: s qn (M, M |P)In (M |P) = ?ts (M) ?s n

The transition matrix Q(P) of the Markov process is written for each policy P knowing that its diagonal element is:

N S

q(M, M|P) = ?

n=1 s=1

s s (q(M, Dn (M)|P)+q(M, Gn (M)|P))

(5)

The steady-state distribution is then obtained by solving: Π(P) · Q(P) = 0 Π(P) · e = 1; (6)

(11)

Π(P) being the vector of the steady-state probabilities π(M|P) under policy P and e is a vector of ones. Once the vector Π is obtained, the global performance indicators can be calculated, e.g., the blocking rate of class-n calls knowing that the load information is equal to l: bn (l|P) =

s M∈A;Gn (M)∈A,?s∈[1,S] π(M|P) /

s knowing that In (As ) = 0. n 3) The utility of a class-n user that has found the network in state M and chosen to connect to system s is the s volume of information sent starting from state Gn (M). s Recall that Gn (M) is de?ned as the state with one more class-n call connected to system s: s s us (M|P) = In (Gn (M)|P) n

(12)

M∈A;f (M)=l

π(M|P)

(7)

In this equation, we consider as blocked all calls that arrive in states where both systems are saturated, i.e., where ts (M) < n Tmin , ?j ∈ H, L. We also obtain the overall blocking rate:

N

b(P) =

n=1

λn N m=1

λm

π(M|P) (8)

s M∈A;Gn (M)∈A,?s∈[1,S] /

B. Transient analysis The steady-state analysis described above is not suf?cient to describe the utility of the users as the throughput obtained by a user at his arrival is not a suf?cient indication about the quality of his communication because of the dynamics of arrivals/departures. In order to obtain the utility, we modify the Markov chain in order to allow tracking mobiles during their connection time. For users of radio condition n connected to system s, only states where there is at least one user (n, s) are considered. The calculation is as follows: 1) Introduce absorbing states As corresponding to the n departure of mobiles that have terminated their connections. Additional transitions are thus added between M and As with rate equal to: n

s qn (M, As ) = μ · IMn >0 ?s n

IV. O PTIMALITY, GAME AND CONTROL In this section, we use the utilities of users that we obtained above to derive the association policies. We ?rst search for the optimal policy, i.e. the policy that maximizes the global utility of the network. Nevertheless, as it is not realistic to consider that the users will seek the global optimum, we show how to ?nd the policy that corresponds to the Nash equilibrium, knowing that users will try to maximize their individual utility. We will next show how the operator can control, by sending appropriate load information, the equilibrium of its wireless users to maximize its own utility. A. Optimality 1) Global utility: When a global optimum is sought, it is important to maximize the QoS of all users. The global utility function can be written as:

N

U (P) =

n=1

λn N i=1

λi

[(1 ? bn (l|P)) ×

(13)

l∈L (Pn,l ) un (M|P)π(M|P)]

M|f (M)=l

(9)

The transitions to the neighboring states with one less user are then modi?ed accordingly by subtracting μ from the original transition rates de?ned in equation (4):

s s s qn (M, Dn (M)|P) = (Mn ? 1) · μ · IMn >0 ?s

(10)

knowing that Pn,l ∈ [1, S] is the system where new users of class-n connect when they receive the load information l and have the policy P. Note that, in this utility, we consider not only the QoS of accepted users (throughput), but also the blocking rate as the aim is also to maximize the number of accepted users. We also weight the users with different radio conditions with their relative arrival rates.

Authorized licensed use limited to: BEIHANG UNIVERSITY. Downloaded on July 17,2010 at 15:13:35 UTC from IEEE Xplore. Restrictions apply.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the Mini-Conference at IEEE INFOCOM 2010

2) Optimal policy: Knowing the utility in equation (13), the optimal policy is the one among all possible policies that maximizes this utility: P = arg max U (P)

P ?

aim of the operator is to maximize its revenues by maximizing the acceptance ratio, the optimal solution is: f ? = arg max

f

(14)

1 b(P? (f ))

(17)

B. Equilibrium 1) Individual utility: If the aim is to maximize the individual utility, users of different radio conditions are interested by maximizing the QoS they obtain given the load information broadcast by the network. The utility that a class n user might obtain if he chooses system s when the load information is l, while all other users follow policy P is then:

s Unl (P) = M|f (M)=l

with blocking de?ned as in equation (8). V. R ESULTS For illustration, we consider the case of a network composed of HSDPA and 3G LTE systems. Users are classi?ed between users with good radio conditions (or cell center users) and users with bad radio conditions (or cell edge users). The network sends aggregated load information as shown in Figure 2 with the following thresholds: [H1 = 0.3, H2 = 0.7, L1 = 0.3, L2 = 0.7], meaning that a system is considered as highly loaded if its load exceeds 0.7 and as low-loaded if its load is below 0.3. We also consider a streaming service where users require a minimal throughput of 1 Mbps and can pro?t from throughputs up to 2 Mbps in order to enhance video quality (Dmin = 1M bps and Dmax = 2M bps). We consider an offered traf?c that varies from 1 to 10 Erlangs and obtain numerically the equilibrium points. A. Equilibrium We focus on the Nash equilibrium when wireless users aim at maximizing their individual utility. For comparison purposes, we study three different association approaches: ? Hybrid decision approach: The proposed hybrid scheme where users receive aggregated load information and aim at maximizing their individual utility. We illustrate the global utility corresponding to the Nash equilibrium policy. ? Peak rate maximization approach: This is a simple association scheme where users do not have any information about the load of the systems. They connect to the system offering them the best peak rate:

s s? = arg max Dn s

us (M|P)π(M|P) n π(M|P)

(15)

M|f (M)=l

2) Nash equilibrium: A policy P? corresponds to a Nash equilibrium if, for all radio conditions and all load information, the individual utility obtained when following P? is the largest possible utility under P? . Mathematically, this can be expressed by the following inequality for all radio conditions n ∈ [1, N ] and all load information l ∈ [1, L]:

s Unl n,l (P? ) ≥ Unl (P? ), ?s ∈ [1, S] (P ? )

(16)

C. Control In the previous section, we derived the policy that corresponds to the Nash equilibrium for a game where players are the wireless users that aim at maximizing their utility. However, there is another dimension of the problem related to the information sent by the network and corresponding to the different load information. Motivated by the fact that the network may guide users to an equilibrium that optimizes its own utility if he chooses the adequate information to send, we introduce a control problem, that can also be modeled as a game between the base station and its users. At the core lies the idea that introducing a certain degree of hierarchy in non-cooperative games not only improves the individual ef?ciency of all the users but can also be a way of reaching a desired trade-off between the global network performance at the equilibrium and the requested amount of signaling. More formally, the way of aggregating the loads in the broadcast information (expressed by the function f (.)) is inherent to the previous analysis. In particular, the utilities of individual users, calculated in equation (15), is function of f (.):

s Unl (P|f ) = M|f (M)=l

?

us (M|P)π(M|P) n π(M|P)

Note that this peak rate can be known by measuring the quality of the receiving signal. Instantaneous rate maximization approach: The network broadcasts M, the exact numbers of connected users with different radio conditions. Based on this information and on the measured signal strength, the wireless users estimate the throughput they will obtain in both systems. A new user with radio condition n will then connect to the system s? offering him the best throughput: s? = arg max

s

M|f (M)=l

This leads the wireless users to a Nash equilibrium that depends on the way the network aggregates the load information: P = P (f ) The control problem is thus de?ned as the maximization of the utility of the network by tuning the function f (.). If the

? ?

1+

N m=1

s Dn

S r=1

r Mm

Note that this scheme is not realistic as the network operator will not divulge the exact number of connected users in each system and each position of the cell. We plot in Figure 3 the global utility for the three cases. This global utility is the one de?ned in equation (13) and

Authorized licensed use limited to: BEIHANG UNIVERSITY. Downloaded on July 17,2010 at 15:13:35 UTC from IEEE Xplore. Restrictions apply.

This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE INFOCOM 2010 proceedings This paper was presented as part of the Mini-Conference at IEEE INFOCOM 2010

expressed in Mbits, as users are interested in maximizing the information they send during their transfer time. As intuition would expect, the results show that the peak rate maximization approach has the worst performance as a system that offers the largest peak throughput may be highly-loaded, resulting in a bad QoS. However, a surprising result is that the hybrid scheme, based on partial information, is comparable and even outperforms the full information scheme when traf?c increases. This is due to the fact that streaming users will have relatively long sessions, visiting thus a large number of network states; knowing the instantaneous throughput at arrival will not bring complete information about the QoS during the whole connection. On the contrary, the proposed hybrid, game theoretic, approach aims at maximizing the QoS during the connection time.

0.24 0.238 0.236 0.234 Global utility (Mbit) 0.232 0.23 0.228 0.226 0.224 0.222 0.22 0.8 1 hybrid approach maximizing peak rate maximizing instantaneous rate

1 0.9 0.8 0.7 Blocking rate 0.6 0.5 0.4 0.3 0.2 0.1 0

x 10

?3

[0.42 0.51 0.5 0.9] [0.23 0.51 0.7 0.9] [0.28 0.7 0.23 0.9]

1

1.2

1.4

1.6 1.8 2 2.2 Offered traffic (Erlang)

2.4

2.6

2.8

Fig. 4. Blocking rate for different broadcast load information; a vector of thresholds [H1 , H2 , L1 , L2 ] means that system s will be considered as highly loaded if its load exceeds s2 and as low-loaded if its load is below s1 (s = H for HSDPA and L for LTE).

1.2

1.4 1.6 1.8 2 Offered traffic (Erlang/cell)

2.2

2.4

2.6

system. We ?rst show how to derive the utilities of ?ows that are related to the QoS they receive under the different association policies. We then derive the policy that corresponds to the Nash equilibrium. Finally, we show how the operator, by sending appropriate information about the state of the network, can optimize its own utility. The proposed hybrid decision approach for the association problem can reach a good tradeoff between the global network performance at the equilibrium and the requested amount of signaling. ACKNOWLEDGMENT This work was supported by the ANR project WiNEM. R EFERENCES

Fig. 3.

Global utility.

B. Control We now turn to the second stage of our problem, where the network tries to control the users’ behavior by broadcasting appropriate information, expected to maximize its utility while individual users maximize their own utility. We plot in Figure 4 the blocking rate for different ways of aggregating load information, obtained when users follow the policy corresponding to Nash equilibrium. In this ?gure, we plot the results for three cases: the optimal thresholds (in red stars) and two other sets of thresholds. We can observe that the utility of the network (expressed in the acceptance rate) varies signi?cantly depending on the load information that is broadcast. Such an accurate modeling of the control problem is a key to understand the actual bene?ts brought by the proposed hybrid decision approach. VI. C ONCLUSION In this paper, we studied hybrid association schemes in heterogeneous networks. By hybrid schemes we mean distributed decision schemes assisted by the network, where the wireless users aim at maximizing their own utility, guided by information broadcast by the network about the load of each

[1] E. Stevens-Navarro, Yuxia Lin, V. W. S. Wong, ”An MDP-Based Vertical Handoff Decision Algorithm for Heterogeneous Wireless Networks”, IEEE Transactions on In Vehicular Technology, , Vol. 57, No. 2. (2008), pp. 1243-1254. [2] D. Kumar, E. Altman, J.-M. Kelif, ”Globally Optimal User-Network Association in an 802.11 WLAN and 3G UMTS Hybrid Cell”, in: Proc. of 20th International Teletraf?c Congress (ITC 20), Ottawa, Canada, Selected for Plenary Presentation, June 17-21, 2007. [3] S. Horrich, S-E. Elayoubi and S. Ben Jamaa, ”On the impact of mobility and joint RRM policies on a cooperative WiMAX/HSDPA network”, IEEE WCNC 2008, Las Vegas, April 2008. [4] Ercetin Ozgur, ”Association Games in IEEE 802.11 Wireless Local Area Networks”, IEEE transactions on wireless communications, 2008, vol. 7 (1), no12, pp. 5136-5143. [5] Srinivas Shakkottai, Eitan Altman, and Anurag Kumar, ”Multihoming of Users to Access Points in WLANs: A Population Game Perspective”, IEEE Journal on Selected Areas in Communications, Vol. 25, No. 6, 2007 , August 2007. [6] S. Shakkottai, E. Altman and A. Kumar, ”The Case for Non-cooperative Multihoming of Users to Access Points in IEEE 802.11 WLANs”, IEEE Infocom, 2006. [7] Libin Jiang, Shyam Parekh and Jean Walrand, ”Base Station Association Game in Multi-cell Wireless Networks”, [8] D. Kumar, E. Altman, J.-M. Kelif. User-Network Association in an 802.11 WLAN & 3G UMTS Hybrid Cell: Individual Optimality, in: Proc. of IEEE Sarnoff Symposium, Princeton, NJ, USA, April 30 - May 2, 2007. [9] Garrett Hardin, ”The Tragedy of the Commons,” Science, 162(1968):1243-1248.

Authorized licensed use limited to: BEIHANG UNIVERSITY. Downloaded on July 17,2010 at 15:13:35 UTC from IEEE Xplore. Restrictions apply.