# Combinatorial auction-based two-stage matching mechanism for mobile data offloading.

AbstractIn this paper, we study the problem of mobile data offloading for a network that contains multiple mobile network operators (MNOs), multiple WiFi or femtocell access points (APs) and multiple mobile users (MUs). MNOs offload their subscribed MUs' data traffic by leasing the unused Internet connection bandwidth of third party APs. We propose a combinatorial auction-based two-stage matching mechanism comprised of MU-AP matching and AP-MNO matching. The MU-AP matching is designed to match the MUs to APs in order to maximize the total offloading data traffic and achieve better MU satisfaction. Conversely, for AP-MNO matching, MNOs compete for APs' service using the Nash bargaining solution (NBS) and the Vickrey auction theories and, in turn, APs will receive monetary compensation. We demonstrated that the proposed mechanism converges to a distributed stable matching result. Numerical results demonstrate that the proposed algorithm well capture the tradeoff among the total data traffic, social welfare and the QoS of MUs compared to other schemes. Moreover, the proposed mechanism can considerably offload the total data traffic and improve the network social welfare with less computation complexity and communication overhead.

Keywords: Data Offloading, Matching, Bidding, NBS, Vickrey Auction

1. Introduction

As forecasted in Cisco's report, overall mobile data traffic is expected to reach 30.6 exabytes per month by 2020, for an eightfold increase over 2015 [1]. Consequently, mobile network operators (MNOs) have to increase their network capacities to address the explosive data traffic by upgrading the infrastructure including actions such as building new base stations or upgrading to 5G, which can be either too expensive or too time-consuming. Therefore, MNOs need to find novel methods to address this current urgent problem, and mobile data offloading appears to be an effective method by utilizing WiFi, femtocell or other access points to offload part of the data traffic generated by mobile users (MUs) in the cellular network. Mobile edge computing(MEC) can play a role in real-time computing services in limited areas [2-3]. MECs are deployed in the base station or at an aggregation point that is close to users in a specific limited area, and neighboring MECs within in the radio transfer will form a clustering MECs. In [4], A traffic counter for every MEC was used to calculate the generated traffic data by end users and check the MEC status in real time. One MEC checks the resource status to determine if it is overloaded. If overloaded, the MEC will send a notification message to the MEC cluster to prepare for the offloading procedure. The auction mechanism has been widely applied in resource allocation in cognitive radio networks [5-8], which is an effective way to solve the issue of how much to provide and how much to pay between demanders and suppliers. However, researchers have not paid much attention to using the auction mechanism to address the incentive issue of AP owners' service for MNOs on mobile data offloading. A distributed market framework to incentivize the offloading services of APs was developed in [9], which formulates a multileader multifollower Stackelberg game to model the interactions between MNOs and APs. In [10], a perfect competition market with more than one MNO and a monopoly market with only one MNO were considered and compared by using the non-cooperative game theory, and further studied the impact of price participation and competition on the market outcome. In [11], an iterative double auction while in an incomplete information market was proposed to derive the optimal amount of offloading data traffic that each AP should admit and payment that each operator should provide to maximize the social welfare. Additionally, a reverse auction mechanism was introduced for mobile data offloading in [12-14], which is only fit for one MNO and multiple APs. In [15], the authors formulate a distributed stable matching approach algorithm for an uplink communication network comprised of MUs, multiple femtocell access points and multiple MNOs. MUs were pre-allocated to femtocell access points through a matching algorithm, and MNOs through complete information competing win the offloading service of an AP thus serving the subscribed MUs of the winner MNO.

The wireless resource allocation problem can be posed as a matching problem between resources and users. Recently, matching theory has emerged as a useful analytic tool to study wireless resource allocation which can overcome some limitation of game theory and optimization, efficiently solving the optimization problem [16-18], depending on the individual information and the preference of the players on each side.

In this paper, we propose a two-stage matching algorithm combining the MU-AP matching mechanism and the AP-MNO matching game in which we not only research the relationship between APs and MNOs but also consider the QoS and demand of mobile users. In the MU-AP matching algorithm, we match the MUs with APs to maximize the total offloading traffic from APs as well as guarantee the QoS of users. Meanwhile, MNOs could estimate the probable payments to APs based on the total potential offloading traffic. Next, in the AP-MNO matching algorithm, this paper considers an incomplete information market where MNOs bid depending on the traffic amount generated by their respective customers for the service of the APs through a Nash bargaining solution (NBS) with only one MNO and a Vickrey auction with multiple MNOs. The main contribution of this paper can be summarized as follows:

a) This paper considers an incomplete information market to incentivize MNOs and APs to offload. This paper assumes each AP only provides service for one MNO at each time period, and each MNO can lease multiple APs for offloading.

b) The proposed scheme has low computational complexity and induces small communication overheads. This paper applies the matching theory to solve the centralized optimization problem. The MU-AP matching pre-allocates mobile users to APs to build possible communication connections. Then, MNOs will bid according to the traffic that each AP could offload, which ensures the final results benefit both MNOs and APs in the AP-MNO matching scenario.

c) Moreover, this paper also researches the effect of the radius range of the cell, which MNOs can exploit to achieve the largest social welfare profits.

The paper is structured as follows: Section 2 presents the system model considered in our work and formulates the optimization problem. The proposed algorithm is shown and analyzed in Section 3, and simulation results are provided in Section 4. The whole work is summarized in Section 5.

[FIGURE 1 OMITTED]

2. System Model

This paper considers a Heterogeneous Mobile Network (HMN), as depicted in Fig. 1, with multiple MNOs M = {1, ... m} and multiple APs A = {1, ... n}. Each AP can be a WiFi or other access point connected to the Internet and that is owned by third parties operating in a separate frequency band, which therefore does not interfere with the cellular network. Each BS serves a set of mobile users (MUs) [K.sub.i] subscribed to the corresponding MN[O.sub.i] which the BS belongs to. MUs are randomly distributed within the coverage of the BSs and have ample traffic to send. Each user might be covered by more than one AP or be covered by no APs. This paper assumes time is slotted and only research the network at each period of time, and within each time slot the MUs' locations and traffic remain fixed. We list several parameters used in this paper in Table 1.

This paper considers each AP owner j has an unused capacity of [C.sub.j] that he is willing to lease for the MNO in exchange for monetary compensation. At each time period, each AP j will serve several numbers of MUs belonging to the identical MNO i, denoted by [A.sub.j.sup.i], and the number depends on the total traffic that MUs would like to send. [A.sub.i] denotes the set of APs that are matched to MN[O.sub.i].

In our model, the BS's offloading benefit not only depends on the total traffic but also the location of the AP. Obviously, MUs which are located at the boundary coverage of the cellular signal will experience bad communication channel conditions, thus requiring more power to transmit. Therefore, APs located farther than those from the BS might bring higher profits for MNOs.

In the following subsections, we formulate the utilities of MUs, APs and MNOs.

A. Utility function of MUs

The aim of MUs is to enhance their QoS, and thus they select the best APs that have the best channel conditions. This paper only studies the MUs covered by the APs. Received signal strength indication(RSSI) can provide a quick and accurate estimate of whether a link is of very good quality (connected region). However, there is no standardized relationship of any particular physical parameter to the RSSI reading. SNR is a better link quality estimator than RSSI [19]. This paper denotes the Signal-to-noise ratio(SNR) as the utility, which is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

where [S.sub.k] is the transmission power of M[U.sub.k], [g.sub.kj] is the channel gain between M[U.sub.k] and A[P.sub.j], [[sigma].sup.2] is the power of the additive white Gaussian noise.

B. Utility function of APs

Given the amount of traffic [d.sub.k] of M[U.sub.k], [for all]j [member of] A, [for all]k [member of] [K.sub.i], [for all]i [member of] M, then the vector of channel utilizations is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where l represents the number of APs of which M[U.sub.k] is within the coverage. Channel utilizations are computed in [14] by

[o.sub.kj]=[[d.sub.k]]/[[r.sub.kj]] (2)

where [r.sub.kj] is the maximum achievable transmission rate of the wireless channel between M[U.sub.k] and A[P.sub.j]. [r.sub.kj] can be easily obtained through a periodic scanning of the wireless channels by all network devices. The element [o.sub.kj] represents the channel utilization of A[P.sub.j] when it is used to offload the data traffic demand [d.sub.k].

In MU-AP matching, APs aim to offload as much traffic as possible under the constraints of its capacity and channel utilization. Note that when the element [d.sub.k] is fixed, the higher the element [r.sub.kj] is, the lower [o.sub.kj] is. Therefore, the AP's utility function in MU-AP matching is given by

[U.sub.AP.sub.kj] = [r.sub.kj] (3)

In AP-MNO matching, APs are willing to gain more economic benefit from offloading, thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

While the utility function [U.sub.AP.sub.ij] is composed of receipts and expenditures, the receipt includes the payment [p.sub.ij] from MN[O.sub.i] based on the amount of offloaded data [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the expenditure is A[P.sub.j]'s offloading service cost. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the cost incurred by A[P.sub.j] for serving MN[O.sub.i].

C. Utility function of MNOs

The utility function of MN[O.sub.i], [for all]i [member of] M is composed of offloading benefit and its payment to A[P.sub.j], [for all]j [member of] A thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

where [V.sub.ij]([??]) denotes the MN[O.sub.i] profit gain when offloading traffic to A[P.sub.j], which is equal to MN[O.sub.i]'s cost reduction compared with when MN[O.sub.i] serves this traffic itself. [V.sub.ij]([??]) has been proven to be a concave function of the total offloading amount in [11]. And [p.sub.ij] is the payment of MN[O.sub.i] to A[P.sub.j].

D. Problem formulation

This paper defines the social welfare as the sum of the utilities of all MNOs and APs in the network, and the objective of our problem is to maximize the network's social welfare and find the proper payment P, where P isa |M| x |A| matrix. Next, the optimization problem can be stated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

In the objective function (6), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] represents the total reduction cost when MNOs serve their MUs directly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denotes the offloading cost caused by APs. Constraint (7) ensures each AP only can be allocated to one MNO. Constraints (8) and (9) ensure the maximum overall offloading traffic from an AP cannot exceed its unused available bandwidth and prevent the allocation of all traffic demand that cannot be satisfied by an AP. Constraints (10) ensures that [x.ij] is a binary variable. Clearly, the optimization function (6) is a binary linear programming problem, which is NP-hard. We can observe that payments do not influence the social welfare, but it is necessary for us to seek a more appropriate payment rule, incentivizing their participation on offloading. This paper introduces the NBS and Vickrey auction to incentive APs' participation and prevent MNOs from overpaying that they cannot make a profit.

3. Analysis of the Proposed Two-Stage Matching Algorithm

3.1 Matching Definitions

We note that the computational complexity of the centralized optimization problem in (6) increases exponentially over the network size. Thus, this paper proposes a distributed matching algorithm which can achieve sub-optimal performance but with less computation complexity. The matching game is an important function of the market to solve two-sided preference selection problems, which was introduced by Gale and Shapely, initially aimed at solving the stable marriage problem [20].

This paper models the system composed of MUs, APs and MNOs as a two-stage matching game, respectively are the MU-AP matching and the AP-MNO matching. The MU-AP matching is defined as an assignment of MUs in [k.sub.i] to APs in A, and the AP-MNO matching is an assignment of APs in A to MNOs in M.

Definition 1. A many-to-one matching [[mu].sub.1] is a mapping from the set of [K.sub.i] [union] A into the subsets of [K.sub.i] [union] A such that [21]:

1) |[[mu].sub.1] (k)| = {0,1}, for every MU k [member of] [K.sub.i];

2) |[[mu].sub.1] (j)| [less than or equal to],[Q.sub.j](k), for every AP j [member of] A;

3) [[mu].sub.1] (k) = j if and only if k is in [[mu].sub.1] (j).

Definition 2. A many-to-one matching [[mu].sub.2] is a mapping from the set of A [union] M into the subsets of A [union] M such that

1) |[[mu].sub.2](j)| = 1, for every AP j [member of] A;

2) |[[mu].sub.2](i)| [less than or equal to] [q.sub.i], for every MNO i [member of] M;

3) [[mu].sub.2](j) = i if and only if j is in [[mu].sub.2](i);

where [Q.sub.j](k) is the number of MUs that can be connected to A[P.sub.j], [q.sub.i] denotes the number of APs serving MN[O.sub.i]. This paper defines a preference relation > over the set of MU(AP): [[mu].sub.1] (MU) > [[mu].sub.1]'(MU) ([[mu].sub.2](AP) > [[mu].sub.2]'(AP)) to denote that MU(AP) prefers its matched AP(MNO) obtained by matching [[mu].sub.1]([[mu].sub.2]) over its matched AP(MNO) obtained by matching [[mu].sub.1]'([[mu].sub.2]').

3.2 Payment Rule

This paper uses auction theory to solve the second matching problem of which set of temporarily matched MUs will be served by each AP. Clearly, there are n auctions with APs. Each AP only serves one MNO, thus offloading their MUs' data traffic. This paper considers an incomplete information market where MNOs bid for the service of AP[s.sub.o]

This paper defines [b.sub.ij] as the MN[O.sub.i]'s bidding price, [[alpha].sub.ij] as the offloading cost of A[P.sub.j] and [v.sub.ij] as the valuation of A[P.sub.j]'s offloading service to MN[O.sub.i], namely, the offloading gain [V.sub.ij]([??]) in this paper.

First this paper considers a special scenario where there is only one MNO competing for a certain AP, which means only the MNO's MUs are in the coverage of the AP at the time slot. This paper formulates the auction as a basic two-person, one-to-one bargaining scenario. Nash in [22] proved that there is a unique bargaining solution, the Nash bargaining solution (NBS) which satisfies the four axioms: Pareto efficiency, symmetry, invariance to affine transformations and independence of irrelevant alternatives.

This paper assumes MN[O.sub.i] and A[P.sub.j] as two players, the utilities ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) is an NBS by solving the

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

s. t. [U.sub.MN[O.sub.ij]]([b.ij]) [greater than or equal to] 0, [U.sub.A[P.sub.ij]]([b.sub.ij]) [greater than or equal to] 0 (12)

which equivalently formulation is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

s. t ([v.sub.ij]-[b.sub.ij]) [greater than or equal to] 0, ([b.sub.ij]-[[alpha].sub.ij]) [greater than or equal to] 0 (14)

Clearly, the NBS ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) for the one-to-one bargaining is [b.sub.ij] = [[v.sub.ij]-[[alpha].sub.j]]/[2] Next, if there are at least two MNOs competing for an AP, this paper introduces the Vickrey auction, which is a type of sealed-bid auction where bidders submit bids without knowing the bids of other participants submitted in the auction, and the highest bidder wins the auction and only pays the second-highest bid [20]. The valuation of offloading revenue [v.sub.ij] is only known by MN[O.sub.i] itself, thus different bidders' estimating valuations are private information. In our auction mechanism, this paper assumes all MNOs are rational, thus [v.sub.ij] [greater than or equal to] [b.sub.ij], [for all]i [member of] M, [for all]j [member of] A, and not colluding with each other.

Proposition 1: The Vickrey auction is Pareto-optimal and there is no further gain to be had from improvement by changing the bidding. The Vickrey auction gives the bidders incentive to submit their true value, guaranteeing the truthfulness of bidders.

Proof: this paper assumes that MN[O.sub.i], [for all]i [member of] M competes for a certain AP, it should satisfy [v.sub.i] [greater than or equal to] [b.sub.i]. The payoff of MN[O.sub.i] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

If [max.sub.z[not equal to]i] [b.sub.z] > [b.sub.i], MN[O.sub.i] will lose the auction, and the strategies have the equal payoff for this case; if [max.sub.z[not equal to]i] [b.sub.z] > [b.sub.i], MN[O.sub.i] will win the auction and the strategies have the equal payoff [v.sub.i]--[max.sub.z[not equal to]i] [b.sub.z]; if [b.sub.i] < [max.sub.z[not equal to]i] [b.sub.z] < [v.sub.i], only when MN[O.sub.i] bids truthfully will it win the auction. Truthful bidding ([b.sub.i] = [v.sub.i]) increase the probability of winning the auction, the payoff is always positive, equaling to [v.sub.i]--[max.sub.z[not equal to]i] [b.sub.z]. However, when bid [b.sub.i] is lower than [max.sub.z[not equal to]i] [b.sub.z], the payoff of MN[O.sub.i] is always zero. Truthful bidding dominates other strategies, therefore it is optimal.

Since this paper introduces the NBS and Vickrey auction, the bid of MN[O.sub.i] proposing to A[P.sub.j] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

Stage 1 The MU-AP Step 1: Initialization Construct the preference list of MUs based on (1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for k [member of] [K.sub.i], i [member of] M; Construct the preference list of APs based on (3) P[L.sub.A[P.sub.j]], for j [member of] A; Construct the list of unmatched MUs [matchlist.sub.i], set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Step 2: Find suitable MUs for each AP While [matchlist.sub.i] [not equal to] [empty set] do MUs propose to APs; for all M[U.sub.k] [member of] [matchlist.sub.i] do if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] do M[U.sub.k] is connected to its subscribed BS; Remove M[U.sub.k] from [matchlist.sub.i]; else Propose to the first A[P.sub.j] in its preference list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; Remove A[P.sub.j] from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; end if end for APs make decisions; for all A[P.sub.j] do A[P.sub.j] keeps the most preferred [Q.sub.j] (k) MUs connected to it that satisfy the condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and rejects the rest; Remove these [Q.sub.j] (k) MUs from [matchlist.sub.i]; else A[P.sub.j] keeps all of the proposed MUs connected to it; Remove these M[U.sub.k] from [matchlist.sub.i]; end if end for end while

where w is the number of MNOs bidding for A[P.sub.j].

3.3 Implementation of the Proposed Algorithm

Based on the given analysis, below is a detailed description showing how the proposed algorithm works in networks.

1) Stage 1: The MU-AP matching

In this instance, this paper defines two preference lists for MUs and APs. For each MU k [member of] [K.sub.i] will form a descending order preference list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] according to its utility (1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Each AP also has a descending order preference list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in terms of its utility (3) over the MUs that are located in the coverage of each AP. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The MU-AP matching is summarized in Stage 1, and it consists of two main phases. Step 1: MUs propose to APs. In the iteration of proposal, M[U.sub.k] first chooses the best AP that maximizes its utility and sends its offer to its preferred AP in its preference list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then remove the AP from the preference list. Step 2: APs make decisions, since each AP has an available capacity limitation and channel utilization limitation, the AP only chooses the most preferred MUs in its preference list that satisfy the condition that the received MUs' traffic demands do not exceed the AP's limitation. The proposing continues until either all MUs were accepted or all APs are full. The resulting matching is a stable matching, which does not admit any blocking pair [21]. At the end of the stage each AP has a set of temporarily matched MUs corresponding to each MNO. However, MUs that were rejected to connect with any of APs in [A.sub.l.sup.i] as a result of limited capacities of APs. These rejected MUs then keep connecting with their subscribed BSs.

Since the MU-AP matching occurs between MUs of different MNOs and APs, each AP has m different lists of temporarily matched MUs. The AP-MNO matching will determine which set of temporarily matched MUs will be served by each AP.

Stage 2 The AP-MNO matching Step 1: Initialization Each A[P.sub.j] send [A.sub.j.sub.i] provided from Stage 1 to all MNOs. Construct the preference list of MNOs based on (5) MNO[list.sub.i], for [for all]i [member of] M; Construct the preference list of APs based on (4) AP[list.sub.j], for [for all]j [member of] A; Calculate the bid price vector [b.sub.i] based on (15), for [for all]i [member of] M; Step 2: Find suitable APs for MNOs MNOs propose bids to APs Each MN[O.sub.i], [for all]i [member of] M sends its bid [b.sub.i] to the APs in its list MNO[list.sub.i]; APs make decisions; if A[P.sub.j] [member of] A receives no bid do nothing; else if A[P.sub.j] [member of] A receives only one bid from MN[O.sub.i] do if MN[O.sub.i] is in its list AP[list.sub.j]do A[P.sub.j] is matched with MN[O.sub.i]; else A[P.sub.j] rejected the bid offer; end if else if A[P.sub.j] receives the most preferred MN[O.sub.i] in its list AP[list.sub.j], and rejects the rest; end if

2) Stage 2: The AP-MNO matching

Next, in the AP-MNO matching, this paper will focus on the allocation of which AP will offload data traffic for which MNO. We also define two preference lists separately for MNOs and APs. For each MN[O.sub.i], [for all]i [member of] M will form a descending order preference list MNO[list.sub.i] over APs according to its utility (5). We need to note that an AP is not included in the list MNO[list.sub.i] when the AP potentially serves no MUs belonged to MN[O.sub.i]. Thus, only APs that satisfy the condition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are in the list. In addition, A[P.sub.j], [for all]j [member of] A also has a descending order preference list AP[list.sub.j] according to its utility (4) over MNOs. Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [for all]i [member of] M should be satisfied in AP[list.sub.j]. Additionally, the first MNO in the list AP[list.sub.j] maximizes the utility of A[P.sub.j]. The AP-MNO matching is summarized in Stage 2. First MN[O.sub.i], [for all]i [member of] M will be informed of other competitors and the set of its MUs that will potentially be served by each AP. Then MN[O.sub.i], [for all]i [member of] M will construct its preference list MNO[list.sub.i] and calculate the bid vector [b.sub.i]{[b.sub.ij], [for all]j [member of] MNO[list.sub.i]}, then propose its bids to APs that are in the list MNO[list.sub.i]. Next, each AP will form its preference list AP[list.sub.j]. When A[P.sub.j], [for all]j [member of] A receives one bid, if the corresponding MNO is in its list AP[list.sub.j], A[P.sub.j] is matched with the MNO. If A[P.sub.j] receives more than one bid from MNOs, it receives the most preferred MNO in its preference list and rejects the rest. At last, if A[P.sub.j] is matched with MN[O.sub.i], then A[P.sub.j] will serve A[P.sub.J.sup.i] MUs and reject the rest. The rejected MUs will continue to connect to their serving BSs.

3.4 Existence and optimality analysis

The following propositions were presented, and the following results are given as:

Proposition 2: The proposed algorithm produces a stable distributed matching. Proof: We first illustrate that the MU-AP (AP-MNO) matching is stable if it cannot be improved by any individual MU-AP (AP-MNO) pair. When an MU is only covered by one AP, its best selection is to propose to the AP. When MUs have substitutable preferences over APs, the set of stable matching is always nonempty. Because MUs have substitutable preferences in each subsequent step, each MU proposes to its most preferred set of APs that do not contain any APs which have previously rejected it. Consider A[P.sub.j], [for all]j [member of] A not matched to an MU k at [[mu].sub.1] such that j [member of] ([[mu].sub.1](k) [union] j). At some step of the matching, k proposed to A[P.sub.j] and was subsequently rejected, therefore A[P.sub.j] prefers [[mu].sub.1] (j) to k, and [[mu].sub.1] is not improvable by the pair (j,k). Since j and k are arbitrary, and since [[mu].sub.1] is not improvable by any individual, [[mu].sub.1] is stable.

It is proven that either the NBS or Vickrey auction is Pareto-optimal [22-23], namely, there is no further gain to be had from improvement in the allocation of MUs(APs). Therefore, the AP-MNO matching is also stable. Finally, the proposed algorithm converges to a stable distributed matching.

4. Simulation

In this section, an uplink communication network was considered with m mobile network operators, where each MNO owns a base station. This paper considers a single cell network with a coverage radius R, the location of BS is uniformly distributed and located 25 m away from the cell center. MUs and APs are randomly distributed in the cell. The transmission coverage of each AP is less than 20 m. This paper sets all MUs' transmit powers as identical, that is [s.sub.k] = 20mW and set the path loss exponent to 4 and the power of the additive white Gaussian noise to -110 dBm, and [C.sub.j] for all APs is identical to 20 Mbps.

In this paper, MUs' traffic demand [d.sub.k], [for all]k [member of] [K.sub.i], [for all]i [member of] M is distributed uniformly in the range [2,5] Mbps and the maximum achievable rate [r.sub.kj] between M[U.sub.k], [for all]k [member of] [K.sub.i] and their surrounding A[P.sub.j], [for all]j [member of] A is distributed uniformly in the range [12,15] Mbps. To take into consideration that the uncertain fluctuation of traffic and prevent throughput collapse caused by the contention level, we increase the traffic [d.sub.k] slightly in the simulation phase and discount the access bandwidth of all APs by 75%. Notably, our above assumptions do not influence the proposed algorithm, which are general and can be used for any other network scenario. Our model can also be used to consider other types of SBS or FAP by modifying the expression (2). Our numerical results are performed based on over 1000 cycles of the algorithm on average. The study can be easily extended to a large-scale network. The profit gains of V([??]),[for all]i [member of] M, [for all]j [member of] A and cost functions [W.sub.ij ([??]), [for all]i [member of] M, [for all]j [member of] A in [11] are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

where [[theta].sub.ij][greater than or equal to] 0 represents the offloading efficiency of A[P.sub.j] for MN[O.sub.i]. As mentioned above, APs which are located farther from the BS can provide more benefit. Therefore, this paper assumes the offloading efficiency coefficient [[theta].sub.ij] is proportional to the distance that is between A[P.sub.j] and MN[O.sub.i] , thus [[theta].sub.ij]= [dis.sub.ij][??] [beta], where [dis.sub.ij] represents the distance between A[P.sub.j] and MN[O.sub.i]. The larger the coefficient [beta] is, the larger the offloading efficiency [[theta].sub.ij] is, which results a larger profit gains and doesn't impact the system performance. This paper sets [beta] = 0.01. [[rho].sub.ij] [greater than or equal to] 0 captures the fact that each AP may incur different cost by serving a different MNO. Parameter [[rho].sub.ij] was chosen within uniform independent probabilities from interval [0.1,0.5].

Another four schemes were used in the simulation phase for comparison purposes, which, respectively are the maximum social welfare(MSW) scheme, Maximum offloading data traffic(MODT) scheme, the greedy reverse auction(GRA) scheme and the random scheme. The MSW method clearly aims to obtain the maximum social welfare. In the MSW, the system first compute the best traffic allocation to different MNOs neglecting the MUs, then the AP serve several MNOs at the same time and offload the traffic of MUs subscribed to different MNOs, which is the most difficult to implement. And the MODT scheme is a centralized computation of the optimization problem (6), aims to achieve the most offloading data traffic. The MSW and MODT schemes incur a lot of computation overheads due to their centralized computation. Also, the GRA method proposed in [14] first forms a reverse auction where APs propose bids to the MNO, the MNO selects the most preferred APs and reject the rest, and pay APs based on a critical price, then the winning APs will serve its MUs. Due to the GRA method only applies to the condition when there is one MNO, in this paper, we added a step that APs proposed bids to multiple MNOs, when MNOs chose the winning APs and decided the paid price to each AP, each AP then accepted the price which maximize its utility and served for the corresponding MNO.

[FIGURE 2 OMITTED]

Fig. 2 shows three performance metrics as a function of the number of MUs under five schemes, in a network with m = 2,n = 6,R = 100 m and [[Pipe][K.sub.1][Pipe]] = [[Pipe][K.sub.2][Pipe]]. Fig. 2 shows the MSW scheme can achieve the most social welfare and the MODT achieves the most traffic offloading amount. And the proposed algorithm achieves a social welfare close to the MODT scheme and a total offloading amount close to the MSW scheme. Notably, the proposed algorithm achieves the best QoS compared to the other schemes. Fig. 2 shows that the proposed algorithm achieve the best tradeoff among total offloading traffic, social welfare and the QoS of MUs. The MSW can offload more traffic than the proposed algorithm in low density of MUs and less than the proposed algorithm in high density of MUs. This is because in low density of MUs, APs can serve different MNOs' MUs at the same time, thus offloading more traffic than the proposed algorithm. However, when the APs reach a saturated condition in high density of MUs, the MSW aims at obtaining the maximum social welfare neglecting the true traffic demand of MUs and QoS of MUs, which leads to less offloading traffic and worse QoS than the proposed algorithm. Compared to the MODT scheme, with the increasing number of MUs, the gap between the MODT and the proposed scheme gradually decreases. According to the proposed algorithm, APs choose their most preferred MUs after MUs choose their most preferred APs, and results in MUs-centric matching in low density of MUs which could not perform well. When the total offloading data amount of each AP is far from reaching their capacities, the MUs-centric matching algorithm cannot guarantee MUs' choices always choose the AP with the highest offloading efficiency. As the number of MUs increases, the total offloading data amount gradually reaches each AP's capacity, and APs have more choices to choose the best MUs to maximize the offloading benefit. However, this MUs' first-selection matching can guarantee MUs' quality of services though at the cost of social welfare. Due to the large overhead and high complexity computation of the MSW and MODT schemes, it is nearly impossible to apply the algorithms to the large network with many APs and MUs. Moreover, the proposed algorithm achieves better in any performance metric than the GRA and Random schemes.

[FIGURE 3 OMITTED]

In Fig. 3, figure (a) plots the social welfare as a function of the same MUs subscribed to each MNOs while figure (b) fixes [[Pipe][K.sub.1][Pipe]] = 70 and [[Pipe][K.sub.2][Pipe]] vaires. Figure (b) plots the social welfare as a function of the number of MUs subscribed to [MNO.sub.2]. Compared to in figure (a), the proposed algorithm in figure (b) only achieve higher social welfare when n=6 APs in low density of MUs. Because the number of MUs subscribed to [MNO.sub.i] is fixed to 70 in figure (b), the APs stayed in an unsaturated condition in low density of MUs in figure (a), thus offloading less data traffic than in figure (b). However, when the number of APs n=3, the social welfares both in figure (a) and (b) are nearly the same due to the APs stayed in an saturated condition. We can conclude that the unequal number of MUs only affects the social welfare when the number of MUs is low and the number of APs is high. We can also observe that the social welfare in our proposed algorithms with six APs is nearly double the social welfare with three APs because it can bring double the offloading data amount with six APs. Additionally, the total social welfare increases quickly when the number of MUs is in the range of [20,40]. However, the increase flattens off when the number exceeds 40. When the number of MUs varies between [20,40], as the number of MUs increases, the offloading traffic to APs has not yet reach a saturation condition. The offloading traffic to APs starts to saturate when the number exceeds 40 MUs, resulting in a slow increase.

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Fig. 4 shows a three-dimensional plot where the average social welfare of the network for m [member of] {2,4,6} MNOs, n [member of] [2,10] APs and R [member of] [50,500] m with [[Pipe][K.sub.i][Pipe]] = 70 MUs, [for all]i [member of] M. We can observe that the social welfare increases with an increase in the number of APs or the number of MNOs when other variables remain constant. The increasing number of APs can bring a higher offloading data amount and the increasing number of MNOs raises the probability of offering higher bids thus leading to higher social welfare. In addition, Fig. 5 shows the side view from Fig. 4 while the number of APs is fixed to six. We observe that the social welfare in Fig. 5 first goes up at the radius range [50,200] m and then falls beginning at the radius range [200,250] m, since in the radius range [50,200] m the density of MUs is high and thus APs' offloading abilities are in a saturated state. With an increase in the radius range, the offloading efficiency increases while the APs' total offloading data amount remains constant, which leads to the social welfare increasing. When the radius range exceeds 200 m, the density of MUs drops and APs' offloading abilities are in an unsaturated state, resulting in the lower density of MUs and the lower total offloading amount. Although the offloading efficiency increases, the social welfare falls. Fig. 5 indicates that the cell of its radius also has a large amount of influence on the social welfare of the network.

[FIGURE 6 OMITTED]

Fig. 6 shows the average number of iterations needed for convergence as [[Pipe][K.sub.i][Pipe]], [for all]i [member of] M and n varies. Fig. 6 shows that, the average number of iterations increases very slowly as the number of MUs and the number of APs increase. Even though for a large network with 180 MUs and 15 APs, it only needs around 9 iterations. In fact, Fig. 6 also shows that, as the number of MUs becomes large relative to the number of APs, i.e., at [[Pipe][K.sub.i][Pipe]] > 100, [for all]i [member of] M for n = 5 APs and [[Pipe][K.sub.i][Pipe]] > 120, [for all]i [member of] M for n = 10 APs, the average number of iterations becomes almost constant. This is due to the fact that, as [[Pipe][K.sub.2][Pipe]], [for all]i [member of] M becomes largely relative to n, it is likely that each AP's preferred MUs would still submit their applications at about the same iteration, hence, not requiring many extra rounds till convergence. However, the MSW and MODT schemes' computation complexity exponential increases with the number of MUs and APs. Thus, Fig. 6 shows that the proposed algorithm presents a reasonable convergence time and its complexity grows relatively slow with [[Pipe][K.sub.2][Pipe]], [for all]i [member of] M and n.

4. Conclusions

This paper proposed a distributed two-stage matching algorithm that combines the matching game and auction mechanism for mobile data offloading. The MU-AP matching assigns the MUs to APs that are available to MUs, the AP-MNO matching determines the assignment of APs to MNOs by using NBS and Vikrey auctions. The offloading problem was formulated as a combinatorial auction and the payment rule was designed to guarantee both individual rationality and truthfulness for realistic scenarios in which only part of the data traffic can be offloaded. Numerical results demonstrate that the proposed algorithm well capture the total data traffic, social welfare as well as the QoS of MUs, thus representing a promising solution to implement a trading marketplace for next-generation access networks composed of heterogeneous systems. Moreover, we also researched the impact of the radius of the cell on total social welfare, which is important for future research work.

References

[1] Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update, 2015-2020," white paper, Cisco, Feb. 2016. [Online]. Available: http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html

[2] Linghe Kong, Muhammad Khurram Khan, Fan Wu, Guihai Chen, Peng Zeng. "Millimeter-Wave Wireless Communications for IoT-Cloud Supported Autonomous Vehicles: Overview, Design, and Challenges," IEEE Communications Magazine, Vol. 55, No. 1, pp. 62-68, Jan., 2017.Article (CrossRef Link)

[3] Linghe Kong, Daqiang Zhang, Zongjian He, Qiao Xiang, Jiafu Wan, Meixia Tao, "Embracing Big Data with Compressive Sensing: A Green Approach in Industrial Wireless Networks," IEEE Communications Magazine, Vol. 54, No. 10, pp. 53-59, Oct., 2016. Article (CrossRef Link)

[4] D. Staria, D. Park, M. Jo, "Recovery for Overloaded Mobile Edge Computing," Future Generation Computing Systems, vol. 70, pp. 138-147, May, 2017. Article (CrossRef Link)

[5] G.S. Kasbekar, S. Sarkar, "Spectrum auction framework for access allocation in cognitive radio networks," IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp.1841-1854, June, 2010. Article (CrossRef Link)

[6] S. Gandhi, C. Buragohain, L. Cao, H. Zheng, "A General Framework for Wireless Spectrum Auctions," in Proc. of 2007 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, pp. 22-33, April 17-20, April 17-20, 2007. Article (CrossRef Link)

[7] M. Dramitinos, G.D. Stamoulis, C. Courcoubetis, "An auction mechanism for allocating the bandwidth of networks to their users," Computer Networks the International Journal of Computer and Telecommunications Networking, vol. 51, no. 18, pp. 4979-4996, Sep., 2007. Article (CrossRef Link)

[8] Q. Wang, B. Ye, S. Lu, S. Guo, "A Truthful QoS-Aware Spectrum Auction with Spatial Reuse for Large-Scale Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 10, pp.2499-2508, Sep., 2013. Article (CrossRef Link)

[9] K. Wang, F.C.M Lau, L Chen, R Schober, "Pricing Mobile Data Offloading: A Distributed Market Framework," IEEE Transactions on Wireless Communications, vol. 15, no. 2, pp. 913-927, Sep., 2015. Article (CrossRef Link)

[10] L. Gao, G. Iosifidis, J. Huang, L. Tassiulas, "Economics of mobile data offloading," in Proc. of Computer Communications Workshops (INFOCOM WKSHPS), 2013 IEEE Conference on, pp. 351-356, April 14-19, 2013. Article (CrossRef Link)

[11] G. Iosifidis, L. Gao, J. Huang, L. Tassiulas, "A double-auction mechanism for mobile data-offloading markets," IEEE/ACM Transactions on Networking, Vol. 23, No. 5, pp. 1634-1647, Sep., 2014. Article (CrossRef Link)

[12] X. Zhuo, W. Gao, G. Cao, S. Hua, "An Incentive Framework for Cellular Traffic Offloading," IEEE Transactions on Mobile Computing, vol. 13, no. 3, pp. 541-555, Jan., 2013. Article (CrossRef Link)

[13] Y. Jia, M. Zhao, K. Wang, W. Zhou, "An incentivized offloading mechanism via truthful auction in heterogeneous networks," in Proc. of Wireless Communications and Signal Processing (WCSP), Sixth International Conference on, pp. 1-6, 2014. Article (CrossRef Link)

[14] S. Paris, F. Martignon, I. Filippini, L. Chen, "An Efficient Auction-based Mechanism for Mobile Data Offloading," IEEE Transactions on Mobile Computing, vol. 14, no. 8, pp. 1573-1586, Oct. 23-15, 2014. Article (CrossRef Link)

[15] S. Bayat, R.H.Y. Louie, Z. Han, Y. Li, B. Vucetic, "Multiple operator and multiple femtocell networks: Distributed stable matching," in Proc. of IEEE International Conference on Communications, pp. 5140-5145, June 10-15, 2012. Article (CrossRef Link)

[16] M. Islam, A.E.M. Taha, S. Akl, M. Abu-Elkheir, "A stable matching algorithm for resource allocation for underlying device-to-device communications," in Proc. of IEEE International Conference on Communications (ICC), pp. 1-6, May 22-27, 2016. Article (CrossRef Link)

[17] Y. Gu, Y. Zhang, M. Pan, Z. Han, "Student admission matching based content-cache allocation," in Proc. of IEEE Wireless Communications and Networking Conference(WCNC), pp. 2179-2184, March 9-12, 2015. Article (CrossRef Link)

[18] Y.Gu, W. Saad, M. Bennis, M. Debbah, "Matching theory for future wireless networks: fundamentals and applications," IEEE Communications Magazine, vol. 53, no. 5, pp.52-59, May, 2015. Article (CrossRef Link)

[19] K. Srinivasan, P. Dutta, A. Tavakoli, P. Levis, "An empirical study of low-power wireless," Acm Transactions on Sensor Networks, vol. 6, no. 2, pp 1-49, Feb., 2010. Article (CrossRef Link)

[20] D. Gale, "College Admissions and the Stability of Marriage," American Mathematical Monthly, vol. 69, no. 69, pp.9-15, Jan., 1962. Article (CrossRef Link)

[21] A. E. Roth, A. Oliveira, "Two-sided matching. A study in game-theoretic modeling and analysis," Journal of Economics, vol. 4, no. 1, pp. 161-165, Jan, 1992. Article (CrossRef Link)

[22] J.F. Nash, "The Bargaining Problem," Econometrica, vol. 18, no. 18, pp.155-162, April, 1950. Article (CrossRef Link)

[23] W. Vickrey, "Counterspeculation, auctions, and competitive sealed tenders," Journal of finance, vol. 16, no. 1, pp.8-37, March, 1961. Article (CrossRef Link)

[ILLUSTRATION OMITTED]

Gang Wang is currently an associate professor at Beihang University, Beijing, Beijing, P. R. China. He received his B.E. degree from Qufu Normal University, Qufu, Shandong, P. R. China, and a PhD degree from Beihang University, Beijing, Beijing, P. R. China. His current research interests include wireless networks, with a particular focus on network coding, information dissemination, and resource allocation.

[ILLUSTRATION OMITTED]

Zhao Yang received his B.E. degree in Communication Engineering from Hebei Normal University, Shijiazhuang, Hebei, P. R. China. He is currently pursuing a master degree at Beihang University, Beijing, Beijing, P. R. China. His current research interests include information network economics, with a particular focus on game theory, congestion networks, network coding, and resource allocation optimization.

[ILLUSTRATION OMITTED]

Cangzhou Yuan is currently an associate professor at Beihang University, Beijing, Beijing, P. R. China. He received his B.E. degree from Central South University of Technology, Changsha, Hunan, P. R. China, and a PhD degree from Beihang University, Beijing, Beijing, P. R. China. His current research interests include wireless communications, with a particular focus on embedded system security, mobile cloud computing and cyber-physical systems.. He was the Australian Queen Elizabeth II Fellow and is currently the Australian Future Fellow. He serves as an Executive Editor for the EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS.

[ILLUSTRATION OMITTED]

Peizhen Liu received his B.E. degree in Changsha University of Science and Technology, Changsha, Hunan, P. R. China. He is currently pursuing a master degree at Beihang University, Beijing, Beijing, P. R. China. His current research interests include information network economics, with a particular focus on game theory, congestion networks, network coding, and resource allocation optimization.

Gang Wang (1), Zhao Yang (1), Cangzhou Yuan (2) and Peizhen Liu (1)

(1) School of Electrical and Information Engineering, Beihang University Beijng, BJ 100191--P. R. China

[e-mail: gwang@buaa.edu.cn]

(2) School of Software, Beihang University

Beijng, BJ 100191--P. R. China

(*) Corresponding author: Cangzhou Yuan

Received December 25, 2016; revised March 18, 2017; accepted April 9, 2017; published June 30, 2017

This work was supported by the National Natural Science Foundation of China (No.61271194,No.91438207), by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No.61521091).

Table 1. Basic Notation used in the Paper Notation Description M Set of MNOs, |M| = m A Set of APs, |A| = n [K.sub.i] Set of MUs subscribed to MN[O.sub.i] [K.sub.i.sup.j] Set of MUs subscribed to MN[O.sub.i] in the coverage of A[P.sub.j] [A.sub.j.sup.i] Set of MN[O.sub.i]'s MUs connected to A[P.sub.j] [A.sub.i] Set of APs matched to MN[O.sub.i] [C.sub.j] Unused capacity of AP owner j [d.sub.k] Bandwidth demand of M[U.sub.k] [P.sub.ij] Price paid to A[P.sub.j] by MN[O.sub.i] [b.sub.ij] Bid offered by MN[O.sub.i] to A[P.sub.j] [r.sub.kj] Maximum transmission rate of the wireless link between M[U.sub.k] and A[P.sub.j] [O.sub.kj] Channel utilization of A[P.sub.j] to satisfy the bandwidth demand of M[U.sub.k] [x.sub.ij] Binary variable that indicates if MN[O.sub.i] owns the service of A[P.sub.j]

Printer friendly Cite/link Email Feedback | |

Author: | Wang, Gang; Yang, Zhao; Yuan, Cangzhou; Liu, Peizhen |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Jun 1, 2017 |

Words: | 8287 |

Previous Article: | UTrustDisk: An efficient data protection scheme for building trusted USB flash disk. |

Next Article: | Joint destination-relay selection and antenna mode selection in Full-Duplex Relay Network. |

Topics: |