Controlled Matching Game for User Association and Resource Allocation in Multi-Rate WLANs

Mikael Touati † ‡ , Rachid El-Azouzi ‡ , Marceau Coupechoux , Eitan Altman ± and Jean-Marc Kelif † Abstract-The deployment of IEEE 802.11 based WLANs in populated areas is such that many mobile terminals are covered by several Access Points (APs). These mobiles have the possibility to associate to the AP with the strongest signal (best-RSSI association scheme).This can lead to poor performances and overloaded APs. Moreover, the well known anomaly in the protocol at the MAC layer may also lead to very unpredictable performances and affect the system throughput due to the presence of heterogeneous data rate nodes and the shared nature of the 802.11 medium. The goal of this paper is to propose an alternative approach for the association. We model the joint resource allocation and mobile user association as a matching game with complementarities, peer effects and selfish players 1 . We focus on the throughput fairness allocation induced by the saturated regime with equal packet sizes. We propose a novel three-stages mechanism for the modeling and control of load balancing, resource allocation and user association. We show that the proposed mechanism can greatly improve the efficiency of 802.11 with heterogeneous nodes and reduce the negative impact of peer effects such as the anomaly in IEEE 802.11.

I. INTRODUCTION

The IEEE 802.11 based wireless local area networks (WLANs) have attained a huge popularity in dense areas as public places, universities and city centers. In such environments, devices have the possibility to use many Access Points (APs) and usually a device selects an AP with the highest received Radio Signal Strength Indicator (best-RSSI association scheme). In this context, the performance of IEEE 802.11 may be penalized by the so called 802.11 anomaly and by an imbalance in AP loads (congestion). When using the Distributed Coordination Function (DCF) of 802.11, under the assumptions of multi-rates, saturated regime, equal packet sizes and similar losses, all users get the same throughput whatever their radio conditions and physical data rates. The protocol thus follows an equal sharing and induces a throughput-based fairness. Moreover, some APs may be overloaded while others are underutilized because of the association rule.

In this paper, we consider a fully distributed IEEE 802.11 network, in which selfish mobile users and APs look for the associations maximizing their individual throughputs. We analyze this scenario using coalition and matching game theory and develop a unified analysis of the joint mobile user association and resource allocation problem for the reduction of the anomaly and for load balancing in IEEE 802.11 WLANs. In a network characterized by a state of nature (user locations, channel conditions, physical data rates), composed of a set W of mobile users and a set F of APs, the user association problem consists in finding a mapping µ that associates every mobile user to an AP. We call the set formed by an AP and its associated mobile users a cell, or a coalition in the game framework. The set of coalitions induced by µ is called a structure. Once mobile user association has been performed, a resource allocation scheme (also called a sharing rule in this paper) allocates radio resources of a cell to the associated mobile users. This matching game is characterized by complementarities in the sense that APs have preferences over groups of mobile users and peer effects in the sense that mobile users care who their peers are in a cell 2 . Indeed, a user's throughput does not only depend on its physical data rate but also on the coalition size and composition. We are thus facing the classical association problem with the additional property that the players (mobile users and APs) are selfish and solely interested in the association maximizing their own throughput. The following questions are raised: does there exist associations (or structures) in which no subset of players prefer deviating and associate with each others? Do these associations always exist? Is there unicity? How to reach these equilibria in a decentralized way? Finally, how to provide the players the incentive to make the system converge to another association point with interesting properties in terms of load balancing? Applying this framework to the IEEE 802.11 in the aforementioned saturated regime, the cell total throughput is shared according to the equal sharing rule. Assuming that players associate solely w.r.t their individual throughputs many mobile users may remain unassociated since every AP has the incentive to associate with a single mobile user having the best data rate. We call this problem the unemployment problem. To counter this side effect and provide the nodes the incentives to associate with each others, we design a decentralized three steps mechanism for the control of the set of stable structures. In a first step, the APs balance the load (e.g. define the number of connections that each should accept). In the second step, the players play a controlled coalition game with individual payoffs resulting from the equal sharing rule. The control of the game is designed so as to provide the players the incentives to form coalitions (match) according to the objective defined by the load balancing. We use here a modified version of the Deferred Acceptance Algorithm (DAA), called Backward Deferred Acceptance Algorithm (BDAA), for matching games with complementarities, peer effects and pairwise alignment. Similarly to the DAA, the complexity of the BDAA is polynomial. We show through numerical simulations that our mechanism not only ensures that a stable structure will form but is also a way to reduce the WiFi anomaly. This mechanism allows us to exploit the overlapping of APs as an opportunity to reduce the anomaly of 802.11.

A. Related Work

IEEE 802.11 (WiFi) anomaly is a well documented issue in the literature, see e.g. [START_REF] Tan | Time-based Fairness Improves Performance in Multi-Rate WLANs[END_REF], [START_REF] Babu | Performance Analysis of IEEE 802.11 Multirate WLANs: Time Based Fairness vs Throughput Based Fairness[END_REF], [START_REF] Banchs | Proportional Fair Throughput Allocation in Multirate IEEE 802.11e[END_REF]. The first idea to improve the overall performance of a single cell system is to modify the MAC so as to achieve a time-based fairness [START_REF] Tan | Time-based Fairness Improves Performance in Multi-Rate WLANs[END_REF], [START_REF] Babu | Performance Analysis of IEEE 802.11 Multirate WLANs: Time Based Fairness vs Throughput Based Fairness[END_REF]. Authors of [START_REF] Tan | Time-based Fairness Improves Performance in Multi-Rate WLANs[END_REF] propose a leaky-bucket like approach. Banchs et al. [START_REF] Banchs | Proportional Fair Throughput Allocation in Multirate IEEE 802.11e[END_REF] achieve proportional fairness by adjusting the transmission length or the contention window parameters of the stations depending on their physical data rate. In a multiple cell WLAN network, mobile user-AP association plays a crucial role for improving the network performance and can be seen as a means to mitigate the WiFi anomaly without modifying the MAC layer. The maximum RSSI association approach, though very simple, may cause an imbalanced traffic load among APs, so that many devices can connect to few APs and obtain low throughput, while few of them benefit from the remaining radio resource. Kumar et al. [START_REF] Kumar | Optimal Association of Stations and APs in an IEEE 802.11 WLAN[END_REF] investigate the problem of maximizing the sum of logarithms of the throughputs. Bejerano et al. [START_REF] Bejerano | Fairness and Load Balancing in Wireless LANs Using Association Control[END_REF] formulate a mobile user-AP association problem guaranteeing a maxmin fair bandwidth allocation for mobile user. This problem is shown to be NP-hard and constant-factor approximation algorithms are proposed.

Arguing for ease of implementation, scalability and robustness, several papers have proposed decentralized heuristics to solve this issue, see e.g. [START_REF] Korakis | Link Quality Based Association Mechanism in IEEE 802.11h Compliant Wireless LANs, WiOpt RAWNET Workshop[END_REF], [START_REF] Gong | Distributed Fair Access Point Selection for Multi-Rate IEEE 802.11 WLANs[END_REF], [START_REF] Bonald | The Impact of Association on the Capacity of WLANs[END_REF]. Reference [START_REF] Korakis | Link Quality Based Association Mechanism in IEEE 802.11h Compliant Wireless LANs, WiOpt RAWNET Workshop[END_REF] proposes to enhance the basic RSSI scheme by an estimation of the Signal to Interference plus Noise Ratio (SINR) on both the uplink and the downlink. Bonald et al. in [START_REF] Bonald | The Impact of Association on the Capacity of WLANs[END_REF] show how performance strongly depends on the frequency assignment to APs and propose to use both data rate and MAC throughput in a combined metric to select the AP. In [START_REF] Xu | Designing a Practical Access Point Association Protocol[END_REF], mobile users select their AP so as to minimize the L pnorm of loads of the APs in its vicinity. Several papers have approached the problem using game theory. The selfish AP selection based on individual MAC throughput can indeed be modeled as a non-cooperative game. Due to the WiFi anomaly, this is not a classical crowding game in the sense that the mobile user achieved throughput is not necessary a monotonically decreasing function of the number of attached devices, as it can be the case in cellular networks [START_REF] Xu | Designing a Practical Access Point Association Protocol[END_REF].

Compared to proposed decentralized approaches, we do not intend to optimize some network wide objective function, but rather to study the equilibria resulting from selfish behaviors and manipulate these behaviors. Compared to other game theoretical approaches, we consider a fully distributed scenario, in which APs are also players able to accept or reject mobile users. This requires the study of the core stability. Moreover, there is a need in understanding the fundamental interactions between mobile user association and resource allocation in the presence of complementarities and peer effects.

In this paper, we tackle the mobile user-AP association problem using the framework of matching games with individual selfish players. This framework provides powerful tools for analyzing the stability of associations resulting from decentralized mechanisms. Matching games [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF] is a field of game theory that have proved to be successful in explaining achievements and failures of matching and allocation mechanisms in decentralized markets. Gale and Shapley published one of the earliest and probably most successful paper on the subject [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF] and solved the stable marriage and college admissions association problem with a polynomial time algorithm called DAA. Some very recent papers in the field of wireless networks have exploited the theoretical results and practical methods of matching games [START_REF] Pantisano | Matching with Externalities for Context Aware User Cell Association in Small Cell Networks[END_REF], [START_REF] Hamidouche | Many-to-many Matching Games for Proactive Social-Caching in Wireless Small Cell Networks[END_REF], [START_REF] Saad | A College Admissions Game for Uplink User Association in Wireless Small Cell Networks[END_REF], although none has considered the WLAN association problem and its related WiFi anomaly. Authors of [START_REF] Pantisano | Matching with Externalities for Context Aware User Cell Association in Small Cell Networks[END_REF] address the problem of downlink association in wireless small-cell networks with device context awareness. The relationship between resource allocation and stability is not investigated and APs are not allowed to reject users. Hamidouche et al. in [START_REF] Hamidouche | Many-to-many Matching Games for Proactive Social-Caching in Wireless Small Cell Networks[END_REF] tackle the problem of video caching in small-cell networks. They propose an algorithm that results in a many-to-many pairwise stable matching. Preferences emitted by servers exhibit complementarities between videos and vice versa. Nevertheless, the model doesn't take into account peer effects within each group. Reference [START_REF] Saad | A College Admissions Game for Uplink User Association in Wireless Small Cell Networks[END_REF] addresses the problem of uplink user association in heterogeneous wireless networks. Invoking a high complexity, complementarities are taken into account by a transfer mechanism that results in a Nash-stable matching, a concept weaker than pairwise stability or core stability.

B. Contributions

Our contributions can be summarized as follows: 1-We provide a matching game-theoretic unified approach of mobile user association and resource allocation in IEEE 802.11 WLANs in the presence of complementarities and peer effects. We propose to go a step further in the understanding of the theoretic constraints induced by the presence of complementarities and peer effects, in the solutions developed by game theorists and in their applications in wireless networks and the design of resource allocation schemes. 2-We use existing theoretical results to show that if the scheduling and/or the MAC protocol induce an equal sharing rule then there exists stable mobile user associations, whatever the user data rates or locations. 3-In order to control the matching game, we design a three steps mechanism, which includes 1) a load balancing, 2) the modifications to be applied to the characteristic function 3 in order to provide the incentives to enforce the result of the load balancing, 3) a stable matching mechanism. We show through numerical examples that our mechanism achieves good performances compared to the optimal solution. 4-We show that our BDAA can be efficiently used to find a stable structure in a many-to-one matching game with complementarities, peer-effects and pairwise alignment. BDAA has been originally proposed in a short paper [START_REF] Touati | Core stable algorithms for coalition games with complementarities and peer effects[END_REF].

The rest of the paper is organized as follows. In Section II, we define the system model. In Section III, we formulate the IEEE 802.11 WLANs resource allocation and decentralized association problem. In Section IV, we show that there exists stable coalition structures under certain conditions whatever the individual data rates. Section V presents our three-steps mechanism. Section VI shows numerical results. Section VII concludes the paper and provides perspectives.

II. SYSTEM MODEL

We summarize in payoff of player i in coalition C u i (.) utility function of player i q i quota of player i P (i) preferences list of player i over individuals P # (i) preferences list of player i over groups TABLE I. NOTATIONS of cardinality N as the union of the disjoint sets of mobile users W of cardinality W and APs F of cardinality F . We assume that orthogonal channels are assigned to different APs. This is an interference-free model; in game-theoretic terms, this implies that there are no externalities. The mobile user association is a mapping µ that associates every mobile user to an AP and every AP to a subset of mobile users.

The IEEE 802.11 standard MAC protocol has been set up to enable any node in N to access a common medium in order to transmit its packets. The physical data rate between a transmitter and a receiver depends on their respective locations and on the channel conditions. For each mobile user i ∈ W, let θ if be the (physical) data rate with an AP f where θ if ∈ Θ = {θ 1 , . . . , θ m }, a finite rate set resulting from the finite set of Modulation and Coding Schemes. If i is not within the coverage of f , θ if = 0. Given an association µ, let θ C = (θ wf ) (f,w)∈(C∩F )×(C∩W) denote the data rate vector of mobiles users in cell C served by AP f . Let n C be the normalized composition vector of C, whose k-th component is the proportion of users in C with data rate θ k ∈ Θ. Note that an AP is defined in the model as a player with the additional property of having maximum data rate on the downlink. Within each cell, a resource allocation scheme (e.g. induced by the CSMA/CA MAC protocol) may be seen as a sharing rule for the cell overall resource. This overall resource may be the total cell throughput (as considered in the saturated regime) or the amount of radio resources in time or frequency in the general case. More precisely, a sharing rule is a set of functions D = (D i,C ) C∈C,i∈C , where D i,C allocates a part of the resource of C to user i ∈ C. Equal sharing, proportional fairness, α-fairness are examples of sharing rules. In this paper, we assume the saturated regime with a single flow per user and equal packet sizes. Using the results of Altman et a.l. [START_REF] Kumar | New Insights From a Fixed-Point Analysis of Single Cell IEEE 802.11 WLANs[END_REF], each user in cell receives the same share of the total cell throughput. The sharing rule is equal sharing. The total cell throughput is a function of the composition vector n C and of the cardinality |C|. We denote r i,C the throughput obtained by user i in cell C. From the game-theoretical point of view, r i,C is understood as i's share of the worth of coalition C denoted v(C).

III. MATCHING GAMES FORMULATION

A. Matching Games for Mobile User Association

In this paper, the mobile user association is modeled as a matching game (in the class of coalition games). The matching theory relies on the existence of individual's order relations { i } i∈N giving the player's ordinal ranking of alternative choices. Each player emits preferences over some subsets of players of the opposite side of the matching, this resulting in individuals preference lists. As an example, w 1 f1 [w 2 , w 3 ] f1 w 4 indicates that the AP f 1 prefers to be associated to mobile user w 4 to any other mobile user, is indifferent between w 2 and w 3 , and prefers to be associated to mobile user w 2 or w 3 rather than to be associated to w 1 . Following the notations of Roth and Sotomayor in [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF], let us denote P the set of preference lists P = (P w1 , . . . , P w W , P f1 , . . . , P f F ).

Definition 1 (Many-to-one bi-partite matching [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). A matching µ is a function from the set W ∪ F into the set of all subsets of W ∪ F such that: (i) |µ(w)| = 1 for every mobile user w ∈ W and µ(w

) = w if µ(w) ∈ F; (ii) |µ(f )| ≤ q f for every AP f ∈ F (µ(f ) = ∅ if f isn't matched to any mobile user in W); (iii) µ(w) = f if and only if w is in µ(f ).
Condition (i) of the above definition means that a mobile user can be associated to at most one AP and that it is by convention associated to itself if it is not associated to any AP. Condition (ii) states that an AP f cannot be associated to more than q f mobile users. Condition (iii) means that if a mobile user w is associated to an AP f then the reverse is also true. In this definition, q f ∈ N * is called the quota of AP f and it gives the maximum number of mobile users the AP f can be associated to.

For the rest of the paper, we focus on many-to-one matchings. In this setting, stability plays the role of equilibrium solution. More than ten different stabilities have been defined in the framework of the game-theoritical coalition formation problem. Nevertheless, matchings have focused on four solution concepts, namely: individual rationality (noncooperative), pairwise stability (cooperative), group stability (cooperative), core stability (cooperative) and weak core stability (cooperative). In this paper, we particularly have an interest in the pairwise and core stabilities. For more details we refer the reader to the reference book [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]. We say that a matching µ is blocked by a player if this player prefers to be unmatched rather than being matched at µ. We say that it is blocked by a pair if there exists a pair of unmatched players that prefer to be matched together.

Definition 2 (Pairwise sability [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). A matching µ is pairwise stable if it is not blocked by any player or any pair of players. The set of pairwise stable matchings is denoted S(P).

Definition 3 (Domination [2]

). A matching µ dominates another matching µ via a coalition C contained in W ∪ F if for all mobile users w and APs

f in C, (i) if f = µ (w) then f ∈ C, and if w ∈ µ (f ) then w ∈ C; and (ii) µ (w) w µ(w) and µ (f ) f µ(f ).
Definition 4 (Weak Domination [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). A matching µ weakly dominates another matching µ via a coalition C contained in W ∪ F if for all mobile users w and APs f in C, (i) if f = µ (w) then f ∈ C, and if w ∈ µ (f ) then w ∈ C; and (ii) µ (w) w µ(w) and µ (f ) f µ(f ); and (iii) µ (w) w µ(w) for some w in C, or µ (f ) f µ(f ) for some f in C.

Definition 5 (Cores of the game [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). The core C(P) (resp. the core defined by weak domination C W (P)) of the matching game is the set of matchings that are not dominated (resp. weakly dominated) by any other matching.

In the general case, the core of the game C(P) contains C W (P). When the game does not exhibit complementarities or peer effects, it is sufficient for its description that the preferences are emitted over individuals only. In the presence of complementarities or peer effects, players in the same coalition (i.e. the set of mobile users matched to the same AP) have an influence on each others. In such a case, the preferences need to be emitted over subsets of players and are denoted P # .

In the classical case of matchings with complementarities, the preference lists are of the form P = (P w1 , . . . , P w W , P # f1 , . . . , P # f F ), i.e., preferences over groups are emitted only by the APs (see the firms and workers problem in [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). Moreover, it may happen that the preferences over groups may be responsive to the individual preferences in the sense that they are aligned with the individual preferences in the preferences over groups differing from at most one player. The preferences over groups may also satisfy the substitutability property. The substitutability of the preferences of a player rules out the possibility that this player considers others as complements.

Definition 6 (Responsive preferences [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). The preferences relation P # (i) of player i over sets players is responsive to the preferences P (i) over individual players if, whenever µ (i) = µ(i) ∪ {k}\{l} for l in µ(i) and k not in µ(i), then i prefers µ (i) to µ(i) (under P # (i)) if and only if i prefers k to l (under P (i)).

Definition 7 (Substitutable preferences [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]). A player i's (i ∈ W ∪F) preferences over sets of players has the property of substitutability if, for any set S that contains players k and l, if k is in Ch i (S) then k is in Ch i (S\l) (where, Ch i (S) is i's choice set from S, the subset of S that player i most prefers).

Considering preference lists of the form P = (P w1 , . . . , P w W , P # f1 , . . . , P # f F ) and assuming either responsive or substitutable strict preferences, we have the result that C W (P) equals S(P). Any many-to-one matching problem with these properties has an equivalent one-to-one matching problem, which can be solved by considering preferences over individuals only. The set of pairwise stable matching is non-empty.

If the preferences are neither responsive nor substitutable, the equality S(P) = C W (P) does not hold in general and the sets of pairwise, weak core and core stable matchings may be empty. An additional difficulty appears if the preferences over groups have to be considered on the mobile users side, i.e., if we have preference lists of the form P = (P # w1 , . . . , P # w W , P # f1 , . . . , P # f F ). Complementarities and peer effect may arise in both sides of the matching. The user association problem in IEEE 802.11 WLANs falls in this category because the performance of any mobile user in a coalition may depend on the other mobiles in the coalition. To break the indifference, we use the following rule: a mobile user prefers a coalition with AP with the lowest index and an AP prefers coalitions in lexicographic order of users indices.

To see that preferences may not be responsive, consider an example with only uplink communications, two APs f 1 and f 2 and three mobile users w 1 , w 2 , w 3 such that θ 11 = 300 Mbps, θ 12 = θ 22 = 54 Mbps, θ 21 = θ 32 = 1 Mbps. Assuming saturated regime and equal packet size, we can show that P # (w

1 ) = f 1 f 2 {w 3 ; f 1 } {w 2 ; f 2 } {w 2 ; f 1 } {w 3 ; f 2 },
which is not responsive. After the game has been controlled according the proposed mechanism, preferences of w 1 can be modified as follows:

P # (w 1 ) = {w 3 ; f 1 } {w 2 ; f 2 } {w 2 ; f 1 } {w 3 ; f 2 } f 1 f 2 . Considering S = {w 2 , w 3 ; f 1 , f 2 }, we have Ch w1 (S) = {w 3 ; f 1 }, while Ch w1 (S\w 3 ) = {w 2 ; f 2 }.
Preferences are thus not substitutable. This general many-to-one matching problem has been considered by authors of [START_REF] Echenique | A solution to matching with preferences over colleagues[END_REF], who propose a fixed-point formulation and an algorithm to enumerate the set of stable matchings. Complementarities and peer effects are analyzed in [START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF]. Note that in this paper, we use the Individually Rational Coalition Lists (IRCLs) to represent preferences. It can indeed easily be shown that other representations (addi-tively separable preferences, B-preferences, W-preferences) are not adapted to our problem, see [START_REF] Keinanen | Algorithms for coalitional games[END_REF] for more details.

B. Sharing Rules and Matching Game Formulation

We now assume that a player i in a given coalition C obtains a payoff s i,C , which is perceived through a utility function u i : R → R. In this paper, we assume that functions u i are positive, concave (thus log-concave), increasing and differentiable. The individual preferences are induced by the player's utilities of these payoffs. We extend our model to the framework of finite coalition games in characteristic form Γ = (N ; v), where v is a function valued in R + defined over a set of coalitions (v(C) is the worth of C). An even particular case of coalition games in characteristic form concerns games with an exogenous sharing rule Γ = (N ; v; E N ; D), where E N is the set of all payoff vectors and D is a sharing rule.

Definition 8 (Sharing Rule).

A sharing rule is a collection of functions D i,C : R + → R + , one for each coalition C and each of its members i ∈ C, that maps the worth v(C) of C into the share of output obtained by player i. We denote the sharing rule given by functions

D i,C as D = (D i,C ) C∈C,i∈C .
From this definition, the payoff of user i in coalition C is given by s i,C = D i,C • v(C) and his utility of this payoff is given by u i (s i,C ). We now formulate the IEEE 802.11 joint user association and resource allocation problem as a matching game. Definition 9 (Resource Allocation and User Association Game). Using the above notations, the resource allocation and users association game is defined as a N -player many-to-one matching game in characteristic form with sharing rule D and rates θ = {θ wf } (w,f )∈W×F : Γ = (W ∪ F, v, R +N , D, θ). Each pair of players of the form (w, f ) ∈ W ∪ F is endowed with a rate θ wf from the rates space Θ = {θ 1 , . . . , θ m }. For this game, we define the set of possible coalitions C:

C = {{f }∪J, f ∈ F, J ⊆ W, |J| ≤ q f }∪{{w}, w ∈ W}. (1)
Note that for IEEE 802.11 MAC protocol and for the saturated regime, s i,C r i,C . For other time sharing MAC approaches, s i,C α i,C .

IV. EXISTENCE OF CORE STABLE STRUCTURES

A. On the Existence of Core Stable Structures

In this section, we show the existence of stable coalition structures (matchings or users-AP association) when preferences are obtained under some regularity conditions over the set of coalitions and some assumptions over the monotonicity of the sharing rules. There exists a stable structure of coalitions (matching) whatever the state of nature θ if and only if the sharing rules may be formulated as arising from the maximization of the product of increasing, differentiable and strictly log-concave individual utility functions in all coalitions.

Definition 10 (Regularity [START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF]). A set of coalitions is regular if there is a partition of the set of agents N into two disjoint, possibly empty, subsets F and W that satisfy the following three assumptions: C1. For any two different players, there exists a coalition containing them if and only if at least one of the players is a player of W. C2. For any players a 1 , a 2 ∈ W and player a 3 , there exist proper coalitions

C 1,2 , C 2,3 , C 3,1 such that a k , a k+1 ∈ C k,k+1 and C 1,2 ∩ C 2,3 ∩ C 3,1 = ∅.
C3. (i) For any player w ∈ W and player a, if {a, w} is not a coalition then there are two different players f 1 , f 2 ∈ F such that {f 1 , a, w} and {f 2 , a, w} are coalitions. (ii) No coalition, which is different from N contains W.

Lemma 1 ([15]

). The set of coalitions C defined in ( 1) is regular if q f ∈ {2, . . . , W -1} and F ≥ 2.

Proposition 1 ([15]

). If the set of coalitions C is such that q f ∈ {2, . . . , W -1} and F ≥ 2, then there is a stable coalition structure for each preference profile induced by the sharing rule D and the state of nature θ iff there exist increasing, differentiable, and strictly log-concave functions u i : R + → R + , i ∈ N , such that ui(0) u i (0) = 0 and

(D i,C • v(C)) i∈C = argmax s C ∈B C i∈C u i (s i,C ), (2)
where C ∈ C and

B C = {s C = (s i,C ) i∈C | i∈C s i,C ≤ v(C)}.
According to Lemma 1, the conditions of regularity for a set of coalitions boil down to two simple conditions: (i) we consider scenarios with at least two APs (which is reasonable when talking about load balancing) and (ii) every AP is supposed to be able to serve at least two users and should not be able to serve the whole set of users. Proposition 1 ensures that there exist stable coalition structures when the resource allocation results from [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]. The equal sharing resulting from CSMA/CA MAC protocol in saturated regime is obtained by considering s i,C = r i,C and the identity function for the u i .

Assuming CSMA/CA and saturated regime, the cell throughput is increasing with the individual physical data rates and individual throughputs r i,C are sub-additive, i.e., decreasing with the addition of users. Assuming that the payoff is the individual throughput, i.e., s i,C = r i,C , then each player has the incentive to match by pairs with highest composition vector. In this case, the unique stable structure is a one-to-one matching, in which APs are associated to their best mobile user. This will further be mentioned in the name of the unemployment problem since it leaves some mobiles users unassociated (unmatched).

V. MECHANISM

In order to reduce both the anomaly and the unemployment problem in a decentralized way, we propose in this section a mechanism to control the players incentives for coalitions (matchings). The mechanism can be decomposed in three steps. The first step is a load balancing resulting in the size of the coalitions that should be enforced by the mechanism. The second step is a control that provides the players the incentives for the objective defined by the first step. In this paper, the incentives are given for coalitions of given cardinalities. The last step is a stable matching mechanism resulting in a stable structure induced by the individual preferences provided by the controlled coalitional game (two previous steps).

Our mechanism can be implemented as a virtual layer on top of the IEEE 802.11 MAC protocol. Mobile users and APs form coalitions based on the "virtual rates" provided by this virtual layer. Once associated, users access the channel using the unmodified 802.11 MAC protocol.

A. Load Balancing

In this paper, we focus on providing the players the incentives for both solving the unemployment problem and reducing the impact of the anomaly in the IEEE 802.11 protocol. The proposed mechanism only requires the definition of a quota vector of the form q = (q 1 , . . . , qF ) that defines the size of the coalitions the players should be incentivized to w.r.t. each AP. In other words, q gives the number of connections the players should be incentivized to create w.r.t. each AP. The objectives of the control are defined in terms of cardinalities of the coalitions. From now on, we assume the following objective quotas vector q = (q 1 , . . . , qF ). Remark that the mechanism is more general than described and holds w.r.t. other objectives.

B. Control

We search for the set of transformations of the characteristic function v mapping the original coalition game in an another one that provides the players the incentives to form stable structures with coalitions of cardinalities q.

Proposition 2. In a coalition game with the equal sharing rule, the set of transformations Ω from the set of characteristic functions in itself that induce single-peaked preferences in cardinalities over the coalitions with an AP f ∈ F must satisfy,

         min C∈C f s.t.|C|=q Ω(v)(C) q > max C∈C f s.t.|C|=q+1 Ω(v)(C) q+1 , ∀q ≥ qf min C∈C f s.t.|C|=q Ω(v)(C) q > max C∈C f s.t.|C|=q-1 Ω(v)(C) q-1 , ∀q ≤ qf (3)
Proof: See the technical report [START_REF] Touati | Controlled Matching Game for User Association and Resource Allocation in Multi-Rate WLANs[END_REF].

These inequalities show how the controller(s) would have to change the characteristic function v in order to change the players preferences over the coalitions and create incentives for some stable structures. We now define the transformation using a multiplicative cost function c f (•) applied to coalitions that contain f as follows:

ṽ(C) = Ω(v)(C) c f (|C|)v(C), (4)
s.t. ṽ(C) verifies (3) and f ∈ C

C. Stable Matching Mechanism

We now show that a modified version of the Gale and Shapley's deferred acceptance algorithm in its collegeadmission form with APs preferences over groups of users Algorithm 1: Backward Deferred Acceptance Data: For each AP: The set of acceptable (covered) users and AP-user data rates. For each user: The set of acceptable (covering) APs. Result: A core stable structure S 1 begin 2

Step 1: Initialization; Step 1.a: All APs and users are marked unengaged.

L(f ) = L * (f ) = ∅, ∀f ;
Step 1.c: Every AP f transmits to its acceptable users the highest payoff they can achieve in coalitions involving f ; 6

Step 1.d: Every user w emits its reduced list of preference P (w);

7
Step 2 (BDAA);

8
Step 2.a, Mobiles proposals: According to P (w), every unengaged user w proposes to its most preferred acceptable AP for which it has not yet proposed. If this AP is engaged in a coalition, all players of this coalition are marked unengaged ; Step 2.b, Lists update: Every AP f updates its list with the set of its proposers:

L(f ) ←-L(f ) ∪ {proposers} and L * (f ) ←-L(f ); 10
Step 2.c, Counter-proposals: Every AP f computes the set of coalitions with users in the dynamic list L * (f ) and counter-proposes to the users of their most preferred coalition according to P # (f ); Step 2.e: If all users of the most preferred coalition accept the counter-proposal of an AP f , all these users and f defect from their previous coalitions; 13 all players of these coalitions are marked unengaged; and users preferences over individual APs is a stable matching mechanism for the many-to-one matching games with complementarities, peer effects and pairwise alignment of the preferences (see Algorithm 1: Backward Deferred Acceptance).

BDAA is similar to the DAA in many aspects. It involves two sets of players that have to be matched. Every player from one side has a set of unacceptable players from the other side. In our case, an AP and a mobile user are acceptable to each others if the user is under the AP coverage. As in DAA, the algorithm proceeds by proposals and corresponding acceptances or rejections. The main difference resides in the notion of counter-proposals, introduced to tackle the problem of complementarities. To go in more details see [START_REF] Touati | Core stable algorithms for coalition games with complementarities and peer effects[END_REF].

Proposition 3. Given a many-to-one matching game, BDAA converges, i.e., outputs a matching in a finite number of steps.

Proof: After initialization, BDAA is made of two loops. The first one is a loop of proposals from users. At each iteration of this outer loop, there is an inner loop of counterproposals from the APs to the users. We show that these two loops stop after a finite number of iterations. Let's first consider the inner loop. At each iteration of the inner loop, the following events can occur:

• An engaged AP remains engaged. Its dynamic list is left unchanged (in Step 2.f, only the dynamic lists of unengaged APs are updated).

• An unengaged AP is now engaged. Its dynamic list is left unchanged (in Step 2.f, only the dynamic lists of unengaged APs are updated).

• An unengaged AP remains unengaged. This is the case when some of the users it counter-proposed in Step 2.d have rejected its counter-proposal and either (a) none of them is engaged with another AP, or (b) some of them are engaged. In (a) the dynamic list remains unchanged. In (b) it is strictly decreasing.

• An engaged AP becomes unengaged. This means that some users in the coalition it was engaged to defected. This is only possible if they are engaged in a new coalition with another AP (Step 2.e). These defecting users are thus removed from the AP dynamic list, which is strictly decreasing.

In all cases, all the dynamic lists are weakly decreasing in the sense of inclusion. The inner loop thus converges in a finite number of steps.

We now consider the outer loop. We immediately have the convergence by finiteness of the number of APs each mobile can propose to and the fact that no mobile can propose more than once to any AP. The algorithm converges in a finite number of steps.

Proposition 4. In a many-to-one matching game with complementarities, peer effects and pairwise alignment of the preferences, the Backward Deferred Acceptance Algorithm (BDAA) is a core stable matching mechanism.

Proof: See the technical report [START_REF] Touati | Controlled Matching Game for User Association and Resource Allocation in Multi-Rate WLANs[END_REF].

Proposition 5. The complexity of BDAA is O(n 5 ) in the number of proposals of the players, where n = max(F, W ).

Proof: See the technical report [START_REF] Touati | Controlled Matching Game for User Association and Resource Allocation in Multi-Rate WLANs[END_REF].

VI. NUMERICAL RESULTS

A. Simulations Parameters and Scenarios

The numerical computations are performed under the assumption of equal packet sizes and saturated queues (each node always has packet to transmit). Under this assumption the sharing rule is equal sharing. Analytical expressions of the throughputs (individual and total throughputs) are taken from [START_REF] Kumar | New Insights From a Fixed-Point Analysis of Single Cell IEEE 802.11 WLANs[END_REF] with the parameters of Table II. We further assume that a node compliant with a IEEE 802.11 standard (in chronological order: b, g, n) is compliant with earliest ones. By convention, if all nodes of a cell have the same data rate, we use the MAC parameters of the standard whose maximum physical data rate is the common data rate. Otherwise, we use the MAC parameters of the standard whose maximum physical data rate is the lowest data rate in the cell.

Assume the spatial distributions of nodes of Figure 1. The first scenario (a) shows the case of 5 APs with a uniform spatial distribution of 20 mobile users. The second scenario (b) has non-uniform distribution of 10 mobile users in the plane. The green (inner), red (intermediate) and black (outer) circles show the spatial region where the mobiles achieve a data rate of 300 Mbits/s, 54 Mbits/s and 11 Mbits/s respectively. Scenario 2 exhibits a high overlap between AP coverages.

B. Numerical Work

Example: No mechanism: We show in Figure 2 Uncontrolled matching game in scenario 1. Stable matching resulting from BDAA when no cost is applied to control the game.

shows the natural incentives of the system in forming low cardinalities coalitions with good compositions. As a result, a one-to-one matching is obtained. Using our mechanism, the structure of throughputs will be changed so as to change the incentives according to the vector q and thus provide the players the incentives to associate according to a many-toone matching rather than a one-to-one.

Example: Mechanism with multiplicative gaussian cost:

As an example of family of cost functions, we can use symmetric unimodal cost functions. In this section in particular, we consider Gaussian cost functions of the form:

c f (l) = e - (l-qf ) 2 2σ 2 f ∀f ∈ F. (5)
The Gaussian cost function is convenient in the sense that it does not penalize the mean-sized coalitions and it provides a great amount of flexibility by the way of its variance. Decreasing or increasing the variance indeed allows for a strict or relaxed control of the quotas.

Focusing on the first scenario (Figure 1 (a)),we consider the two matchings shown in Figure 3. The first one (a) is the stable matching resulting from the mechanism with BDAA, the second matching (b) results from the mechanism with the search for the structure maximizing the total sum of the throughputs.

We first observe that the proposed mechanism implies a drastic reduction of the unemployment problem w.r.t. the result of Figure 2 (b). The natural incentives of the system resulting in a one-to-one matching have been countered and a many-to-one matching is obtained. The unemployment has been reduced from 73, 6% to 0% in this particular scenario. The second point to be raised is that the proposed mechanism allows to obtain a high total throughput, close to the optimal total throughput with polynomial time complexity. For this scenario, we achieve through our mechanism 88.80% of the total maximum throughput. The third point is that the quotas have been enforced by the mechanism (via the cost function) since the quotas vector from the load sharing is q = (8.0, 4.5, 3.33, 3.83, 4.33) (obtained by Nash bargaining 4 over the share [0, 1] of the players at the intersection of the coverages of the APs) and the formed coalitions are of sizes 8, 4, 3, 4 and 4.

We now compare our approach to the best-RSSI scheme. The two matchings are compared Figure 4. We observe that the load is effectively shared among the APs and that the individual throughputs are greatly increased from 527 kbits/s when using best-RSSI to 1.64 Mbits/s for the coalition with AP1, 1.93 Mbits/s for the coalition with AP2, 2.59 Mbits/s for the coalition with AP3, 1.64 Mbits/s for the coalition with AP4 and 2.59 Mbits/s for the coalition with AP5. The individual performances are multiplied by a factor 3 to 5 in 4 Achieves a proportional fair allocation in the utility space of the APs. Induces the number of players to be connected to each AP. this particular scenario.

VII. CONCLUSION

In this paper, we have presented a novel AP association mechanism in multi-rate IEEE 802.11 WLANs. We have formulated the problem as a coalition matching game with complementarities and peer effects and we have provided a new practical control mechanism that provides the nodes the incentive to form coalitions both resolving the unemployment problem and reducing the impact of the anomaly in IEEE 802.11. Simulation results have shown that the proposed mechanism can provide significant gains in terms of increased throughput by minimizing the impact of the anomaly through the overlapping between APs. We have also proposed a polynomial complexity algorithm for computing a stable structure in a many-to-one matching game with complementarities, peer effects and pairwise alignment. This work is a first step in the field of controlled coalition games for achieving core stable associations in distributed wireless networks. Further works include for example the study of a dynamic number of users or the impact of interference.

3

 3

9

 9

11 Step 2

 112 .d, Acceptance/Rejections: Based on these counter-proposals and the best achievable payoffs offered by APs in Step 1.c to which they have not yet proposed, users accept or reject the counter-proposals;

12

 12

14 users 16 L

 1416 that have accepted the counter-proposal and f are marked engaged in this new coalition;15Step 2.f: Every unengaged AP f updates its dynamic list by removing users both having rejected the counter-proposal and being engaged to another AP: * (f ) ←-L * (f )\{engaged rejecters}; 17Step 2.g: Go to Step 2.c while the dynamic list L * of at least one AP has been strictly decreased (in the sense of inclusion) in Step 2.f;18Step 2.h: Go to Step 2.a while there are unengaged users that can propose;19Step 2.i: All players engaged in some coalition are matched.

Fig. 1 .

 1 Fig. 1. Scenario 1 : A spatial distribution of APs (smallest red circles) F = {f 1 , . . . , f 5 } and devices (black points) W = {w 1 , . . . , w 20 }. Scenario 2 : A spatial distribution of APs (smallest red circles) F = {f 1 , . . . , f 5 } and devices (black points) W = {w 1 , . . . , w 10 }. Circles show the coverage areas corresponding to different data rates.

  Fig. 2.Uncontrolled matching game in scenario 1. Stable matching resulting from BDAA when no cost is applied to control the game.

Fig. 3 .

 3 Fig. 3. Controlled matching game in scenario 1. Comparison of the association obtained from (a) BDAA with Gaussian costs of variance σ = 0.2, (b) the global optimum.

  Stable matching resulting from Gaussian cost and BDAA. Matching resulting from the best-RSSI scheme.

Fig. 4 .

 4 Fig. 4. Comparison of the association obtained from (a)Gaussian cost and BDAA, and (b) the best-RSSI scheme in scenario 2. Figure in (b) is zoomed towards the center AP.

  Table I the notations used in this paper. We use both game-theoretic definitions and their networking interpretation. Throughout the paper, they are used indifferently. Let define the set of players (nodes) N

|set| cardinality of the set set N set of players (mobile users and APs) W set of mobile users F set of Access Points (APs) W f set of mobile users with strictly positive data rate w.r.t. f ∈ F W {f } maximal subset of mobile users with strictly positive data rate w.r.t. f ∈ F only W J maximal subset of mobile users with strictly positive data rate w.r.t. all f ∈ J ⊂ F only C set of coalitions (cells) C f set of coalitions containing AP f ∈ F C coalition (cell) µ matching (AP-mobile user association) Θ set of feasible data rates θ wf data rate between w and f r i,C throughput of node (user or AP) i in cell C α i,C proportion of radio resources (time, frequency) of i in cell C D sharing rule (resource allocation scheme) v(C) worth of coalition C s i,C

  a stable matching. No associated player has an incentive to deviate and form a coalition of size superior to two. The figure

		802.11n	802.11g	802.11b
	Parameter		value		unit
	Θ	{300, 54, 11} {54, 11}	{11}	Mbits/s
	slot duration	9	9	20	µs
	T0	3	5	50	slots
	TC	2	10	20	slots
	L	8192	8192	8192	bits
	K	2	2	2
	b0	16	16	16
	p	2	2	2

Mapping any coalition to its worth.

Step 1.b: Every AP f computes possible coalitions with its acceptable users, the respective users payoffs and emits its preference list P # (f );

Rachid El-Azouzi and Eitan Altman are partly supported by the European Commission within the framework of the CONGAS project FP7-ICT-2001-8-317672.. J.-M. Kelif and M. Coupechoux are partly supported by the french ANR project NETLEARN ANR-13-INFR-004.