{'fraction_non_alphanumeric': 0.05936580447352717, 'fraction_numerical': 0.01491861637549643, 'mean_word_length': 4.168350526427735, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Joint Scheduling and Power Allocations for Traffic Offloading via Dual-Connectivity

With the rapid growth of mobile traffic demand, a promising approach to relieve cellular network congestion is to offload users' traffic to small-cell networks. In this paper, we investigate how the mobile users (MUs) can effectively offload traffic by taking advantage of the capability of dual-connectivity, which enables an MU to simultaneously communicate with a macro base station (BS) and a small-cell access point (AP) via two radio-interfaces. Offloading traffic to the AP usually reduces the MUs' mobile data cost, but often at the expense of suffering increased interferences from other MUs at the same AP. We thus formulate an optimization problem that jointly determines each MU's traffic schedule (between the BS and AP) and power control (between two radio-interfaces). The system objective is to minimize all MUs' total cost, while satisfying each MU's transmit-power constraints through proper interference control. In spite of the non-convexity of the problem, we design both a centralized algorithm and a distributed algorithm to solve the joint optimization problem. Numerical results show that the proposed algorithms can achieve the close-to-optimum results comparing with the ones achieved by the LINGO (a commercial optimization software), but with significantly less computational complexity. The results also show that the proposed adaptive offloading can significantly reduce the MUs' cost, i.e., save more than 75% of the cost without offloading traffic and 65% of the cost with a fixed offloading.


I. INTRODUCTION
With the rapid growth of smart handheld devices and mobile internet services, traffic demand in cellular networks has been growing tremendously [2], which causes frequent congestions and imposes a heavy burden on network operators. A cost effective approach to relieve network congestion is to offload the traffic of mobile users (MUs) to spatially spread small-cell networks, e.g., femtocells and WiFi access points (APs) [3] [4]. From the network operators' perspective, offloading traffic can effectively exploit the additional network capacities provided by the multi-tiers small cells and reduce the needs of costly and time-consuming network infrastructure upgrade. From the MUs' perspective, offloading traffic reduces their costs, since small cells usually offer a low price for mobile data than cellular operators. Traffic offloading becomes increasing attractive, as an increasing percentage of mobile devices are equipped with multiple radio-interfaces that facilitate to flexibly simultaneous connections to multiple networks [5]- [7].
In particular, a new paradigm of small-cell dual-connectivity is gaining momentum in both industry practice [8] [9] and the 3GPP LTE-A standardizing activities [1] [10]. Through the dual-connectivity, each MU can simultaneously communicate with a macro base station (BS) and a small-cell AP via two different radio-interfaces. This enables the MUs to flexibly schedule their traffic between two networks to achieve efficient traffic offloading. For instance, an MU can schedule its delay-sensitive small-volume data traffic (e.g., voice-over-IP traffic) to the macro BS, and offload its delay-tolerant large-volume traffic (e.g., file downloading/uploading) to a small-cell AP at the same time.
Nevertheless, different from the centralized resource management and orthogonal channel allocation in cellular networks, a small-cell AP (such as WiFi) often allows multiple MUs to share the same channels in a distributed fashion, which leads to significant mutual interferences among the MUs. It means that if each MU aggressively offloads its traffic to the AP, then each MU needs to spend significant amount of transmit-power to the AP to combat the mutual interferences, which might significantly reduce the benefit from offloading traffic.
Several prior studies have taken such interferences into consideration when designing data offloading algorithms [11] [12] [13]. However, the interference-aware traffic offloading design with dual-connectivity is still an open problem. This problem becomes especially complicated if we consider different transmitpower constraints at each MU's different radio-interfaces [28] [29], which require the MU to carefully allocate its transmit-powers to match the need of the scheduled traffic. To tackle the above challenging problem, we propose a joint optimization of the traffic scheduling and transmit-power allocations with the MUs' dual-connectivity. Our contributions can be summarized as follows.
• Novel Joint Optimization Formulation: We formulate a cost minimization problem, in which each MU jointly determines its traffic scheduling to the AP and BS and the transmit-powers at the two radio-interfaces. The objective is to minimize the total cost of all MUs, while meeting each MU's traffic demand and its transmit-power constraints. To the best of our knowledge, such a formulation targeted for the MUs' traffic offloading with dual-connectivity has not been studied before.
• Centralized Algorithm Design: We first propose a centralized algorithm for solving the joint traffic scheduling and power control problem. In spite of non-convexity of the problem, we perform a series of manipulations to transform the joint optimization into an equivalent SINR-assignment problem (here SINR denotes the signal-to-interference-plus-noise ratio). We then explore the hidden monotonicity of the SINR-assignment problem and design a two-layered algorithm to solve it. Based on the obtained SINRs at the AP, we derive the MUs' traffic scheduling and transmit-powers to minimize the total cost.
• Distributed Algorithm Design: We next propose a distributed algorithm to solve the joint optimization problem, by focusing on a practically important case that the channel bandwidth of the AP is no smaller than the BS's allocated bandwidth. In this case, we identify the hidden concave minimization property of the SINR-assignment problem and propose a distributed algorithm to compute each MU's SINR at the AP. Based on the obtained SINRs at the AP, we derive the MUs' traffic scheduling and transmit-powers to minimize the total cost in a distributed manner.
• Performance Improvement: Numerical results show that both the proposed algorithms can achieve the close-to-optimum results which are obtained by the LINGO (a commercial optimization software [40]) but with a significant less computational complexity. The numerical results also validate that the proposed traffic offloading can significantly reduce the MUs' cost, namely, saving more than 75% of the cost without performing any offloading and more than 65% of the cost with a fixed offloading scheme.
The rest of this paper is organized as follows. Section II describes the related studies. Section III presents the problem formulation. Section IV presents a series of transformations that facilitate the following algorithm designs. Sections V and VI propose the centralized and distributed algorithms, respectively, to solve the problem. Section VII presents the numerical results, and we conclude this study in Sect. VIII.

II. RELATED WORKS
Since the seminal studies [5] [6], there have been many studies that investigated traffic offloading via infrastructure-based small-cell networks 1 . They can be roughly categorized into two groups as follows: • Network-oriented traffic offloading. The first group of studies mainly focused on optimizing traffic offloading from the networks' perspectives. In [12], Ho et al. considered the inter-cell interference when accommodating the offloaded traffic. Taking into account the coupling effect due to the mutual interference, the authors formulated a utility optimization framework for distributing traffic loads among different macro-cells. In [13], Chen et al. also considered the interference among different small cells when offloading traffic, and proposed a framework that facilitates the macro BS to manage the small cells to minimize the energy consumption. In [15], Iosifidis et al. considered the coupled 1 Besides offloading traffic via infrastructure-based networks, it is also possible to offload traffic through peer-to-peer communications (e.g., the device-to-device communications [14]). This, however, is not the focus of this study. capacities of different APs due to interference, and proposed a double auction mechanism that matches the network operators with the most suitable APs for data offloading. In [16], considering the suffered interference due to serving macro-cell MUs, Yang et al. proposed a refund mechanism for network operator to motivate the small-cell APs to admit macro-cell MUs for traffic offloading.
• User-oriented traffic offloading. The second group of studies focused on optimizing the traffic offloading from the MUs' perspectives, with the key issues including interference management and delay-offloading tradeoff. For instance, in [11], Kang et al. considered the scenario of one BS and one third-party WiFi AP, and investigated how different MUs choose either the BS or the AP for offloading traffic. Considering the mutual interference among different MUs, the authors formulated the networks-selection problem as a binary nonlinear programming problem for maximizing the system-wise reward. Studies in [18] [19] proposed several different schemes to motivate the MUs to delay their traffic offloading by leveraging the delay tolerance and better future network conditions.
In [20], Im et al. proposed an MU-centric cost-aware WiFi offloading system, which considers the MU's throughput-delay tradeoff and cost budget to decide when to offload which type of traffic.
In spite of the above studies, only few studies investigated the paradigm of small-cell dual-connectivity (which has been gaining momentum in the industry practice [8] [9] and the 3GPP LTE-A standardizing activities [1] [10]) for offloading the MUs' traffic. In [22], Jha et al. discussed several technical challenges and potential solution directions regarding the small-cell dual-connectivity in cellular networks. However, to the best of our knowledge, there exists no existing study that investigated the optimal management of the MUs' traffic scheduling and transmit-power allocations for traffic offloading via the dual-connectivity.
We emphasize that although there are several studies investigating how the traffic offloading can benefit the network operators, it is less understood about how much the MUs can benefit from offloading traffic in terms of saving the mobile data cost. Our study sheds light on this benefit and illustrates how to optimize such benefit through both centralized and distributed approaches.  There also exists a small-cell AP that can provide traffic offloading services to the MUs through dual-connectivity. Each MU i has two radio-interfaces, one for sending traffic to the BS and one for offloading traffic to the AP. We use x iA and x iB to denote MU i's transmission rates to the AP and the BS, respectively. We use p iA and p iB to denote MU i's transmit-powers to the AP and the BS, respectively 3 . In the rest of this paper, the subscripts "A" and "B" denote "AP" and "BS", respectively. We consider that the macro BS and AP operate on different spectrums to provide service 4 .

A. System Model
The small-cell AP allows multiple MUs to share the same spectrum (channel) [23] [24], which results in mutual interference among the MUs when offloading traffic. To make the discussions more concrete, we adopt the throughput model under the interference channel as [11] [13] [16], i.e., given the MUs' transmit-powers {p iA } i∈I , MU i's transmission rate to the AP is where W denotes the AP's channel bandwidth, and g iA denotes the channel gain from MU i to the AP.
n A = W n 0 denotes the power of the background noise at the AP, with n 0 denoting the power density.
The BS allocates orthogonal sub-channels to different MUs for accommodating the uplink traffic (such as in OFDMA). Given MU i's transmit-power p iB , MU i's uplink transmission rate to the BS is where g iB is the channel power gain from MU i to the BS, and B is the bandwidth allocated to MU i by the BS (we consider that the BS's channel allocation is given in this study). n B = Bn 0 denotes the power of the background noise at the BS.
Each MU i needs to satisfy a traffic demand R req i through the transmissions to both BS and AP, i.e., Similar to [11] [16] [21], we consider usage-based pricing schemes by both the AP and the BS. Let π A and π B to denote the unit-prices announced by the AP and BS, respectively. Then, MU i's total transmission cost in one unit time is

B. Problem Formulation
We are interested in jointly optimizing all MUs' traffic scheduling {x iA , x iB } i∈I and the transmitpowers {p iA , p iB } i∈I , to minimize the total cost. Here, "CMP" stand for "Cost Minimization Problem".
Constraints (1), (2), and (3), The key challenge to solve Problem (CMP) is due to the intrinsic non-convexity of (1). In the rest of this paper, we will develop efficient algorithms to solve Problem (CMP) to achieve close-to-optimum performance. Before presenting the details, we make the following assumption. Assumption 1 can be satisfied by imposing an admission control policy that selects an appropriate group of MUs to serve, such that the MUs' traffic demands can be satisfied within their transmission power constraints 5 . Assumption 1 enables us to focus on evaluating the benefit of the traffic offloading via dual-connectivity and designing algorithms to achieve this benefit.
Before proposing the algorithms to solve Problem (CMP), we will first present a series of problem formulations equivalent to Problem (CMP). Specifically, we use Fig. 2 to show how these problem formulations are related and where they are located in this paper.

IV. EQUIVALENT TRANSFORMATIONS OF PROBLEM (CMP)
This section presents a series of problem formulations that facilitate our later algorithm designs. 5 A heuristic approach to perform admission control is that the MU (let us say MU i) with (2

A. Transforming Problem (CMP) into a Transmit-Power Allocation Problem
We first identify the following property of Problem (CMP).

Lemma 1: Constraint (3) is tight at any optimal solution of Problem (CMP).
Proof: We prove this by contradiction. Suppose that (3) is not tight for some MU i at an optimal solution. Then, we can reduce x iB by setting x iB = R req i − x iA , which will reduce the total cost (i.e., the objective function) without violating any constraint. This contradicts the fact that it is an optimal solution, and hence completes the proof.
By using Lemma 1 and eq. (2), we express x iB and p iB as functions of p iA for each MU i as follows: Similar to [16] [17], we consider the practical scenario that the price of the AP is lower than that of the BS (i.e., π A < π B ), which motivates the MUs to offload traffic to the AP. By using (1), (8), and (9), we transform Problem (CMP) into an equivalent Transmit-Power Allocation Problem (TPA-P): Variables: p iA , ∀i ∈ I.
Problem (TPA-P) only involves {p iA } i∈I as variables. Here, (10) comes from Lemma 1, i.e., each MU i's x iA cannot exceed R req i . Constraints (11), (12), and (13) come from (5), (6), and (7), respectively. Problem (TPA-P) indicates a tradeoff in offloading traffic as follows. To minimize the MUs' total cost, all MUs should offload their traffic to the AP as much as possible. However, aggressive traffic offloading causes a heavy interference at the AP, which increases the MUs' power consumptions (but satisfying (11), (12), and (13)). Notice that Problem (TPA-P) is more complicated than the well-studied power control problems over interference channels (e.g. [31] [32]), because it takes into account each MU's transmit-powers at two different radio-interfaces. This consequently yields the non-convex constraint (13) which couples each MU i's p iA and p iB together. We also recall that all MUs' {p iA } i∈I are also coupled due to the interference at the AP. Hence, Problem (TPA-P) is very difficult to solve.

B. Transforming Problem (TPA-P) into an SINR-Assignment Problem
To solve Problem (TPA-P), we need to make some further equivalent transformations. We use θ i to denote MU's achieved SINR at the AP as follows: Based on (14), we have the following result that connects {θ i } i∈I with {p iA } i∈I .

Proposition 1:
Given any profile of transmit-powers {p iA } i∈I which is feasible for Problem (TPA-P), the corresponding profile of {θ i } i∈I given by (14) ensures that the following result holds: and we always have i∈I θi 1+θi < 1. Proof: Please refer to Appendix I for the details.
Based on Proposition 1, we can use {θ i } i∈I to substitute {p iA } i∈I and transform Problem (TPA-P) into an equivalent SINR-assignment problem as follows: Variables: θ i , ∀i ∈ I.
Notice that we introduce constraint (20) in Problem (SINR-P) for the convenience of later discussions, and Proposition 1 shows that introducing such a constraint does not reduce the feasible set of Problem (TPA-P). Once we solve Problem (SINR-P), then the optimal solution {p * iA } i∈I of Problem (TPA-P) can be computed based on eq. (15).
In the special case where all MUs' traffic demands are small enough (see Fig. 6 in Sec. VII), it is optimal for all MUs to offload their entire traffic to the AP for minimizing the cost. The particular structure of Problem (SINR-P) enables us to derive a sufficient condition for this special case to happen.

Proposition 2: (Complete-Offloading Situation)
The optimal solution of Problem (SINR-P) is θ * i = 2 R req i W − 1, ∀i ∈ I when both of the following two conditions (i.e., (C1) and (C2)) hold: Proof: We first derive θ * i = 2 R req i W − 1 by setting constraint (16) tight, which corresponds to that each MU offloads its entire traffic to the AP. We then derive Conditions (C1) and (C2) by ensuring that {θ * i } i∈I is compatible with all constraints. We obtain Condition (C1) by substituting θ (20), (17) and (19). Notice that (18)  and (C2) together guarantee that the optimal solution of Problem (SINR-P) is C. Equivalent Form of the SINR-assignment Problem with {ρ i } i∈I and ρ 0 Problem (SINR-P), however, is still difficult to solve due its non-convexity. To solve it efficiently, we further introduce a one-to-one mapping as follows Since i∈I ρ i < 1 always holds (i.e., Proposition 1), we introduce another positive variable ρ 0 such that ρ 0 + i∈I ρ i = 1. Such a condition will help simplify the complicated denominators in (17) and (19).
By using {ρ i } i∈I and ρ 0 , we equivalently transform Problem (SINR-P) into Problem (SINR-M-P) as follows (the letter "M" means "Medium", and Appendix II presents the detailed procedures).
, ∀i ∈ I corresponds to an optimal solution of Problem (SINR-P) 6 .

Proof:
The key idea is to show that the feasible region of Problem (SINR-P) and that of (SINR-M-P) form a one-to-one mapping, if Problem (SINR-P) is feasible. Please see Appendix II for the details.
Proposition 3 allows us to solve Problem (SINR-P) by solving Problem (SINR-M-P). In particular, Problem (SINR-M-P) can be solved through a two-layered structure, i.e., we first solve the subproblem in which the value of ρ 0 is given, and then we find the best ρ * 0 ∈ (0, 1] to minimize the objective function.

V. CENTRALIZED ALGORITHM TO SOLVE PROBLEM (SINR-M-P)
We propose a centralized algorithm to solve Problem (SINR-M-P). Sec. V-A shows the two-layered structure. With the layered structure, we design an algorithm to solve a subproblem of Problem (SINR-M-P) in Sec. V-B, based on which we design an algorithm to solve the top problem in Sec. V-C.

A. Two-Layered Structure of Problem (SINR-M-P)
Problem (SINR-M-P) is still a non-convex optimization. Nevertheless, solving Problem (SINR-M-P) can be vertically separated into two steps, namely, solving a series of subproblems in which the value of ρ 0 is given in advance, and then solving a top-problem that finds the best ρ * 0 ∈ (0, 1] for minimizing the objective function. The details are as follows.
Proof: Please refer to Appendix III for the details.
2) (Top-problem to find ρ * 0 ): By solving the bottom problem and obtaining F sub (ρ 0 ) as a function of a given ρ 0 , we next solve the top-problem to find the best ρ * 0 for minimizing the objective function:

B. Monotonicity of Problem (SINR-M-SubP) and Algorithm (Cen-Sub) for Solution
We focus on solving Problem (SINR-M-SubP) in this subsection.

1) (Monotonicity of Problem (SINR-M-SubP)):
We solve Problem (SINR-M-SubP) by using techniques from monotonic optimization, which tackles a class of optimization problems with monotonic objective functions and monotonic constraints [33] [34]. The feasible region of a monotonic optimization problem can be represented by the intersection of a normal set (i.e., Definition 1 below) and a reversed normal set (Definition 2). Thanks to the monotonic property of the objective function and the constraints, the feasible region can be well approximated by a set of poly-blocks (with an arbitrary desirable precision), and an optimal solution can be attained at one of the vertexes of the poly-blocks. This yields an efficient approach, referred to as the polyblock-approximation, to solve the monotonic problems [34].
The advantage of the monotonic optimization is that it does not requires the problem to be convex, hence is widely applicable for solving a wide range of practical engineering problems (see [33] for more details).

Definition 1: (Normal Set)
A set G ⊂ R n + is normal, if for any two points x and x ′ ∈ R n + with x ′ ≤ x and x ∈ G, we always have x ′ ∈ G.

Definition 2: (Reversed Normal Set)
A set H ⊂ R n + is a reversed normal set, if for two points x and x ′ ∈ R n + with x ′ ≥ x and x ∈ H, we always have x ′ ∈ H. With the above terminologies, we can show the following result. Proof: We first note that the objective function (28) is increasing in {ρ i } i∈I . Moreover, the left hand sides of (23)- (26) are increasing in {ρ i } i∈I , i.e., G (ρ0) is a normal set and H (ρ0) is a reversed normal set.
Hence, Problem (SINR-M-SubP) involves the minimization of an increasing function, subject to a feasible region given by G (ρ0) ∩ H (ρ0) . Thus, according to [33], (SINR-M-SubP) is a monotonic optimization.  The key component of Algorithm (Cen-Sub) is the While-Loop (Lines 2-18), whose purpose is to iteratively construct the poly-blocks that approximate the lower-boundary of G (ρ0) ∩ H (ρ0) with an increasing precision. Figure 3 provides a sketch to illustrate the procedures. Specifically, in the k-th Construct a line between z k and point o whose

5:
Find the intersection point x k between the above constructed line and the lower boundary given in H (ρ0) by bisection search. 6: if V (x k ) < CBV then 7: Update CBV = V (x k ) and set CBS=x k . 8: end if 9: if x k − z k < ǫ then 10: Set f stop = 1.
18: end while 19: iteration, set T k denotes the current set of vertexes. In T k , we find a vertex z k that yields the smallest objective value (Line 3) 8 . Then we perform the following two tasks: • Task i): to update the current best solution (CBS) and the current best value (CBV). We first con-  (23), (24), and (27)). We then find the corresponding intersection point (denoted by x k ) between the constructed line and the lower boundary of the feasible region (Line 5) 9 . We use V (x k ) and x k to update the CBV and the CBS in the k-th iteration (Lines 6-8).
• Task ii): to construct poly-blocks T k+1 for the next round iteration. We use vertex z k and the intersection point x k to construct the new poly-blocks that can approximate G (ρ0) ∩ H (ρ0) closer (Line 12) 10 . The essence of Line 12 is to remove the region in which the optimum cannot exist.
Algorithm (Cen-Sub) terminates if z k and x k are close enough (Lines 9-11), or if we cannot expect to find a better solution (Lines 14-16). the one-dimensional linear search with a fixed step-size ∆ top to find ρ * 0 . A smaller step-size ∆ top will lead to a more accurate solution in the search. In Sec. VII, we adopt ∆ top = 0.005 (i.e., 200 samples within (0, 1]) for most of the simulations, since we find that a ∆ top smaller than 0.005 yields a very limited performance improvement with a significant increase in computational time (see Table III for details).
We emphasize that although the proposed Algorithm (Cen) provides an effective approach to solve Problem (SINR-M-P), we cannot claim the obtained {ρ * i } i∈I as the global optimum due to the use of linear search with a fixed step-size ∆ top . Nevertheless, we have the following asymptotical result. Proposition 6: Algorithm (Cen) can yield the asymptotically optimal solution (i.e., ρ * 0 and {ρ * i } i∈I ) for Problem (SINR-M-P), as ∆ top approaches to zero.
Proof: Using an extremely small step-size ∆ top going to zero enables us to enumerate all possible values of ρ 0 ∈ (0, 1]. For each enumerated ρ 0 , the subroutine (Cen-Sub) can find the corresponding 9 Thanks to the monotonicity of the constraints, we can use the bisection search to find x k efficiently. 10 In Line 12, scalar x k i (or z k i ) denotes the i-th element of vector x k (or vector z k ), and vector ei denotes the vector with the i-th element equal to 1, and all other elements equal to 0. All vectors in this paper are of dimension 1 × I.

Algorithm (Cen): to solve Problem (SINR-M-TopP)
1: Initialization: Set a small step-size ∆ top . Set ρ 0 = ∆ top . Set the CBV as a very large number.
respectively. Moreover, based on (8) and (9), MU i's rate and transmit-power at the BS are respectively. Thus, we solve Problem (CMP) completely.
To perform Algorithm (Cen), the BS needs to collect each MU's private information, e.g., the channel gains {g iA , g iB }, the transmit-power capacities {P max iA , P max iB , P max i }, and the demand R req i . This may not be always feasible in practice, due to privacy concerns and consideration of communications overhead.
This motivates us to study whether it is possible to solve Problem (SINR-M-P) in a distributed fashion.

VI. DISTRIBUTED ALGORITHM FOR SOLVING PROBLEM (SINR-M-P)
We first consider implementing Algorithm (Cen) in a distributed manner, which turns out to be challenging due to the centralized nature of the subroutine (Cen-Sub) to solve the monotonic optimization.
Hence, we will focus on a practical network scenario as follows where a distributed algorithm is possible.

Assumption 2:
The channel bandwidth of the small-cell AP is no smaller than the allocated bandwidth by the BS, i.e., W ≥ B.
Assumption 2 is motivated by the fact that a small-cell AP often provides a larger bandwidth than the cellular BS. For example, IEEE 802.11ac enables a total channel bandwidth up to 160MHz [27], which is larger than that of 60MHz in the 3GPP LTE-A standard [8] [9]. We will later show that Assumption 2 helps convexify (26) such that Problem (SINR-M-P) becomes a concave minimization problem. This involves some additional equivalent problem transformations as follows.
Based on (27), the above (32), (33), and (34) are equivalent to (22), (25), and (26), respectively (that is why we add additional letter "E" after "M" to label the problem). Problem (SINR-ME-P) also has a two-layered structure, namely, we can first solve the subproblem with a given ρ 0 , and then solve the top-problem to determine the best ρ * 0 ∈ (0, 1]. The subproblem and the top-problem are given as follows.
We emphasize that different from solving Problem (SINR-M-P) in a centralized manner as in Section V, we will solve the above Problems (SINR-ME-SubP) and (SINR-ME-TopP) in a distributed manner.

B. Subproblem (SINR-ME-SubP): A Concave Minimization Problem
To solve Problem (SINR-ME-SubP) in a distributed manner, we first prove the following. The concave minimization problem is known as a multi-extremal global optimization. For the general concave minimization optimizations, it is very difficult to characterize an optimality condition, and we only know that the optimal solution(s) exist at one or multiple vertices of the feasible region [37]. Motivated by this observation, several numerical schemes (see [38] for more details) have been proposed for enumerating the vertexes of feasible region. However, these schemes suffer from two common drawbacks: the high computational complexity and the centralized implementation. For instance, in [36], the authors proposed a parameterized branch-and-bound algorithm to solve the spectrum balancing problem (which was proved as a concave minimization problem). However, the proposed algorithm is centralized without an upper-bound characterization of the computational complexity.
Therefore, to exploit the concave minimization property to solve Problem (SINR-ME-SubP), we need to identify some additional structural properties of the feasible region in our problem. Fortunately, in Problem (SINR-ME-SubP), only constraint (27)  and M i,(ρ0) , we first define the following function: such that function J i (ρ i ) decreases within ρ i ∈ (0, χ i,(ρ0) ] and increases within ρ i ∈ [χ i,(ρ0) , 1].
Proof: Please refer to Appendix V for the details.
Based on Lemma 2, we obtain the following results regarding M i,(ρ0) and M i,(ρ0) .
Proof: Please refer to Appendix VI for the details. Note that in the third case when Condition (C3) does not hold, we need to calculate arg min v|χ i,(ρ0) ≤ v ≤ 1, J i (v) = P max i + nB giB . This can be efficiently computed by a bisection search, as J i (ρ i ) is increasing for ρ i ∈ [χ i,(ρ0) , 1] (Lemma 2) in this case. For the other similar cases in Proposition 8, the bisection search is also applicable.
Using Proposition 8, we can re-write Problem (SINR-ME-SubP) in the following equivalent form.
constraint (27), In Problem (SINR-MES-SubP), each MU i can calculate its M i,(ρ0) and M i,(ρ0) using only its private information without communicating with the BS.  37)). The BS's objective is to allocate its budget to the MUs to minimize the total dis-utility.

C. Distributed Algorithm (Dis-Sub) for Solving Problem (SINR-MES-SubP)
The concave minimization property of Problem (SINR-MES-SubP) together with its simple form • The BS quantizes Θ effective with a small step-size ∆ sub , which yields Θ effective ∆sub units of currency. The BS performs an iterative process to allocate these units to the MUs (the While-Loop on Lines 2-8).
• In each iteration, the BS allocates one unit of currency (in the amount ∆ sub ) to an appropriate MU based on the MUs' bids. To compete for this unit, MU i calculates its bid b i (Line 3) representing 20 how eager MU i is to get the unit 11 and submits the bid to the BS. MU i also sends the BS a signaling f i indicating whether it can further increase its ρ current i or not. After receiving all MUs' {b i , f i } i∈I , the BS selects the MU (let us say MU k) which submits the largest bid with f i = 1, and grants MU k the unit (Line 4). Correspondingly, MU k increases its ρ current k by ∆ sub (Line 5).
The iteration process will terminate if either the BS uses up its effective budget or the BS finds that every MU's f i = 0, i.e., every MU has reached the maximum value of ρ current i . In a nutshell, Algorithm (Dis-Sub) provides an efficient approach to determine the best vertex of the feasible region that can minimize all MUs' total dis-utility (under a given ρ 0 ). The BS collects each MU's tuple of (b i , f i ).

5:
The BS selects MU k = arg max i∈I b i × f i , and notices MU k for allocating ∆ sub . 6: MU k, which is noticed by the BS, updates its ρ current i = ρ current i + ∆ sub . 7: The BS updates its budget as Θ current = Θ current − ∆ sub . 8: end while 9: Output: The BS sets F sub (ρ 0 ) = (π B − π A )W i∈I log 2 ( 1 bi ln 2 ). Each MU i sets ρ * ,sub i,(ρ0) = ρ current i .

D. Distributed Algorithm (Dis) for Solving Problem (SINR-ME-TopP)
We next propose a distributed Algorithm (Dis) to solve Problem (SINR-ME-TopP). In Algorithm (Dis), the BS performs a one-dimensional linear search over ρ 0 ∈ (0, 1]. For each enumerated ρ 0 , the BS and the MUs invoke Algorithm (Dis-Sub) as a subroutine. Algorithm (Dis) works as follows.
• In Line 5, the BS determines the feasibility of Subproblem (SINR-MES-SubP). 11 Each MU's bid corresponds to its marginal decrease in the dis-utility when obtaining one more unit of the currency. Here, we assume that MUs will truthfully report their bids, and we will leave the study about the incentive issues in a future study.

• If Subproblem (SINR-MES-SubP) is feasible, the BS and the MUs perform Algorithm (Dis-Sub)
to evaluate F sub (ρ 0 ), based on which the BS and the MUs update their respective currently best solutions (Lines 7-9). Otherwise, the BS continues to evaluate the next value of ρ 0 (Line 11).

Algorithm (Dis): to solve Problem (SINR-ME-TopP)
1: Initialization: The BS sets a small step-size ∆ top for updating ρ 0 , and initializes ρ 0 = ∆ top . The BS sets the current best value (CBV) as a very large number. The BS collects each MU i's tuple of (M i,(ρ0) , M i,(ρ0) ).

5:
if M i,(ρ0) ≤ M i,(ρ0) , ∀i ∈ I and i∈I M i,(ρ0) ≤ 1 − ρ 0 ≤ i∈I M i,(ρ0) are met then 6: The BS and the MUs perform Algorithm (Dis-Sub). As a result, the BS obtains F sub (ρ 0 ), and each MU i obtains ρ * ,sub i,(ρ0) . 7: if F sub (ρ 0 ) < CBV then 8: The BS sets CBV = F sub (ρ 0 ), and each MU i sets its ρ * i = ρ * ,sub i,(ρ0) .  Considering that Algorithm (Dis-Sub) requires no more than 1−ρ0 ∆sub iterations, the overall number of iterations required by Algorithm (Dis) will be no more than 1 2 1 ∆sub 1 ∆top . As a comparison, we emphasize that the centralized Algorithm (Cen) proposed in Sec. V does not require Assumption 2 and can be applied to more general settings than the distributed Algorithm (Dis).
However, the downside of Algorithm (Cen) is that it only exploits the monotonic structure of Problem (SINR-M-P), and thus requires a longer computational time than Algorithm (Dis). The numerical results in Table I and Fig. 5 will verify this point.

E. Distributed Power Control Algorithm for Achieving {θ * i } i∈I
After obtaining ρ * i , each MU i can derive the solution for Problem (CMP). MU i's SINR at the AP is (21)), and the transmission rate to the AP is (1)). Meanwhile, MU i's transmission rate to the BS is x * iB = R req i + W log 2 (1 − ρ * i ) (according to (8)), and the transmit-power to the BS is p * iB = nB giB 2 (9)).
However, as shown in (15), all MUs' {p * iA } i∈I are coupled together. Fortunately, by setting θ * i as MU i's targeted SINR, the MUs can adopt the minimum power control scheme [39] to reach {p * iA } i∈I in a distributed manner. In the minimum power control scheme, each MU initializes its p iA = 0 and then keeps on updating p iA based on its measured SINR for achieving θ * i targeted. Due to the space limitation, we skip the detailed description of this power control scheme, and interested readers please refer to [39] for the details. We emphasize that, as the solution for Problem (SINR-P), {θ * i } i∈I is guaranteed to be feasible to all MUs' transmit-power constraints, which guarantees that the resulting {p * iA } i∈I (obtained by the minimum power control scheme) is also feasible to the original Problem (CMP).

VII. NUMERICAL RESULTS
We consider a network scenario that the BS is located at the origin, and the small-cell AP is located at (350m, 0m). The MUs are randomly located within a circle, whose center is (320m, 0m) and the radius is 20m. This means that the MUs are closer to the AP than to the BS (otherwise, there is little benefit of considering traffic offloading). We use the similar method as [26] to model the channel power gain, i.e., g iA = ̺iA l κ iA , where l iA denotes the distance between MU i and the AP, and κ denotes the power-scaling factor for the path-loss (we set κ = 4). We further assume that ̺ iA follows an exponential distribution with unit mean due to channel fading. Figure 4 plots two examples of the network scenarios (namely, an 8-MU scenario and a 12-MU scenario), which will be used in the following simulations.
We set the total channel bandwidth of the AP shared by all MUs as W = 20MHz (802.11a/b/g/n standard [27]) and the channel bandwidth of the BS to a single MU as B = 5MHz (close to a WCDMA channel [28]). For each MU, we set P max iB = 0.25W (i.e., Power Class-3 of mobile devices) , P max iA = 0.2W [28], P max i = 0.35W, and n 0 = 1 × 10 −15 W/Hz. To account for the economic cost, we set π B = $10/GB [30] and π A = $2/GB. As stated earlier, we use ∆ top = 0.005 in Algorithms (Cen) and (Dis), and we validate the choice of ∆ top = 0.005 at the end of this section by comparing different ∆ top .    infeasible when R req i = 9Mbps). For each tested case, the first number represents the minimum total cost and the second number represents the computational time (measured in seconds and obtained by a PC with Intel Core i7-4610M CPU@3.00GHz and 8.00GB RAM). To validate Algorithms (Cen) and (Dis), we adopt the global-solver of LINGO to solve Problem (CMP) and obtain the minimum cost. Due to the non-convexity of Problem (CMP), it often takes LINGO a very long time to get an result.

A. Accuracy and Efficiency of Algorithm (Cen) and Algorithm (Dis)
The results in Table I show that Algorithms (Cen) and (Dis) can achieve the results very close to LINGO (with the average relative error equal to 2.89%), while both algorithms consume a significantly less computational time than LINGO, because they exploit the special structural properties of the corresponding problems. In Table II, we compare the performance of Algorithm (Cen) and LINGO when W < B. The simulation setup is the same as Table I, except that we change W = 4MHz. In this case, the average relative error of Algorithm (Cen) (compared to LINGO) is 0.67%. Notice that Algorithm (Dis) is not applicable in this case because Assumption 2 does not hold. Table I shows that Algorithm (Dis) requires an even shorter time than Algorithm (Cen), because Algorithm (Dis) avoids the complicated procedures for poly-block approximation but exploiting the concave minimization property. Figure 5 presents a detailed comparison of the computational time used by Algorithms (Cen) and (Dis). We use the above 8-MU scenario and another 12-MU scenario in Figure 5.   {g iB } i∈I = [3.3164, 2.8765, 1.4029, 2.7934] × 10 −8 . We vary each MU's R req i from 1Mbps to 14Mbps (as Problem (CMP) is infeasible when R req i = 15Mbps). In Fig. 6, the top subplot shows the traffic to the AP and the BS. The middle subplot shows the corresponding total transmit-powers to the AP and the BS, and the bottom subplot shows the offloading ratio (i.e., the traffic delivered to the AP over the total demand) and the consequent total cost.   As shown in the top subplot, when the MUs' traffic demands are low (i.e., R req i ≤ 8Mbps), all demands are offloaded to the AP, yielding the complete-offloading situation (i.e., Proposition 2). Accordingly, the bottom subplot shows the offloading-ratio equal to 1. In fact, we can verify that when R req i ≤ 8Mbps, the conditions in Proposition 2 are satisfied. In the complete-offloading situation, the MUs' transmit-powers to the AP are usually very small, which correspond to the enlarged view in the middle subplot.
However, when the MUs' traffic demands further increase (i.e., R req i ≥ 9Mbps), the mutual interference among the MUs becomes significant. As a result, the MUs' transmit-power constraints can no longer afford offloading all demands to the AP. In fact, we can verify that the two conditions in Proposition 2 fail to hold when R req i ≥ 9Mbps. As a result, some MU starts to deliver its traffic to the BS (as shown in the top subplot), and the offloading ratio starts to decrease (as shown in the bottom subplot).
Correspondingly, the MU needs to allocate their transmit-powers to the AP and BS for accommodating its traffic scheduling, and the MUs' transmit-powers to the BS increases (as shown in the middle subplot).
To gain deeper insights of the results in Fig. 6, we further plot each individual MU's traffic scheduling in Fig. 7(a) and the transmit-powers in Fig. 7(b). The two figures show that the MUs' traffic offloading decisions and the transmit-power allocations are strongly correlated due to the mutual interference at the AP. In particular, we observe that as the MUs' traffic demands increase (i.e., R req i ≥ 8Mbps), MU 1 (whose channel gain g 1B is the largest) first starts to re-direct its traffic to the BS, and then MU 2 (whose g 2B is the second largest) follows. Such a result is consistent with the intuition, because a larger channel gain to the BS requires a smaller transmit-power to achieve the same data rate to the BS. The middle and bottom subplots of Fig. 7(b) also show that each MU's transmit-power limit to the BS (i.e., P max iB = 0.25W) and total power budget (i.e., P max i = 0.25W) eventually become tight as the MUs' demands increase. That is why Problem (CMP) is infeasible when R req i = 15Mbps. We use the 4-MU and 8-MU scenarios used before to evaluate the performances of these two schemes. Figure 8 validates that the total cost can be greatly reduced by using our proposed traffic offloading scheme 12 . In both subplots, the proposed offloading can save more than 75% of the total cost obtained by the zero-offloading scheme, and more than 65% of the total cost of the fixed-offloading scheme.  cannot support a demand more than 3Mbps for each MU, and the fixed-offloading cannot support a demand more than 7Mbps for each MU. In comparison, the proposed traffic offloading can accommodate each MU's demand up to R req i = 14Mbps. Similar results also appear in the right subplot. 12 We use the result of Algorithm (Dis) to denote the proposed traffic offloading scheme in this figure, since the performances of Algorithm (Cen) and Algorithm (Dis) are very close.

D. Performance under Different Locations of the MUs
We further evaluate the performance of the proposed offloading under different locations of the MUs.
To this end, we vary the center of the circle within which the MUs are randomly located (as described at the beginning of Section VII) according to (170m, 0m), (220m, 0m), (270m, 0m) and (320m, 0m). This corresponds to that the MUs are gradually moving away from the BS and closer to the AP. For each location, we independently and randomly generate 100 different sets of the MUs' locations. Figure 9 shows the corresponding average results, in which we plot the results for three cases, i.e., each MU's demand R req i = 4, 8, and 12Mbps. Subplot 9(a) shows the average total traffic offloaded to the AP versus different locations. It shows that when the MUs are closer to the AP, more traffic demands are offloaded to the AP, which is attributed to the better channel gains between the MUs and the AP. Subplot 9(b) shows that less traffic are delivered through the BS as MUs move closer to the AP. Finally, Subplot 9(c) shows the total cost decreases when the MUs are closer to the AP due to effective offloading.  An interesting observation in Subplot 9(a) is that the difference of offloaded traffic is marginal when the traffic demand increases from R req i = 8Mbps (the line marked with circles) to R req i = 12Mbps (the line marked with triangles). However, the difference is very significant when the demand increases from R req i = 4Mbps (the line marked with squares) to R req i = 8Mbps. The result is consistent with the intuition that offloading traffic to AP becomes less attractive due to the heavy interference at the AP when the MUs' traffic demands are high. In fact, as shown in Subplot 9(b), most traffic demands are delivered to the BS when each MU's demand increases from 8Mbps to 12Mbps.

E. Evaluating the Impact of ∆ top used in Algorithms (Cen) and (Dis)
Tables III and IV validate the use of ∆ top = 0.005 in Algorithms (Cen) and (Dis) for the linear search.
We show that using an ∆ top smaller than 0.005 yields a very limited improvement on the performance but incurs a significant increase in the computational time. To this end, we use the 4-MU scenario, and try  Table III, using ∆ top = 0.005 in Algorithm (Cen) yields a small average  Regarding the future work, we will consider the more general case that the MUs' traffic demands requirements might not be feasible, and propose an admission control scheme to ensure the feasibility of Problem (CMP). Moreover, we will consider multiple coexisting APs and explore the possibility of allowing different MUs to offload traffic through different APs.
Then, we continue to show that, given {p iA } i∈I feasible for Problem (TPA-P), {θ iA } i∈I given by (14) always yields i∈I θi 1+θi < 1. The details are as follows. First, let us consider a profile {p iA } i∈I feasible for Problem (TPA-P). In particular, in this {p iA } i∈I , there exists at least two different MUs allocating positive transmit-powers to the AP. We thus can obtain {θ i } i∈I based on (14). Such {θ i } i∈I always yields i∈I θi 1+θi < 1. Otherwise, some MU's transmit-power must be negative according to the reversed mapping (15). Second, let us consider another {p iA } i∈I feasible for Problem (TPA-P), in which only one MU (e.g., MU i) allocating positive transmit-power to the AP. Then, the resulting θ i (based on (14)) can always ensure i∈I θi 1+θi < 1. In summary, any {p iA } i∈I feasible for Problem (TPA-P) will yield {θ i } i∈I (based on (14)) which can ensure i∈I θi 1+θi < 1.

APPENDIX II: PROOF OF PROPOSITION 3
By using ρ i to replace θ i , Problem (SINR-P) can be transformed into the following equivalent form Variables: ρ i , ∀i ∈ I.
By using ρ 0 that ensures ρ 0 + i∈I ρ i = 1, we can obtain the form of Problem (SINR-M-P) exactly.
We next prove Proposition 3. In particular, let ρ * 0 and {ρ * i } i∈I together denote an optimal solution of Problem (SINR-M-P). To prove Proposition 3, it suffices to show that {ρ * i } i∈I corresponds to an optimal solution of Problem (P1) (notice that since ρ i and θ i form a one-to-one mapping given in (21), the equivalence between Problem (SINR-P) and Problem (P1) directly follows). We thus prove that {ρ * i } i∈I corresponds to an optimal solution of Problem (P1). Our key idea is to illustrate that the feasible region of Problem (P1) and that of Problem (SINR-M-P) form a one-to-one mapping exactly, if Problem (SINR-P) (i.e., Problem (P1)) is feasible. The details are illustrated by the following three points.
• First, Problem (SINR-P) and Problem (P1) are feasible, since they are based on the series of equivalent transformations from Problem (CMP). The feasibility of Problem (P1) enables us to introduce a ρ 0 > 0 such that ρ 0 + i∈I ρ i = 1.
Summarizing the above three points, there exists a one-to-one mapping between each point in the feasible region R ′ of Problem (SINR-M-P) and each point in the feasible region R of Problem (P1).
Moreover, the objective function of Problem (SINR-M-P) is equal to that of Problem (P1) under (27).
is an optimal solution of Problem (SINR-M-P), {ρ * i } i∈I ensures to maximize the objective function of Problem (P1) while being feasible.
The normal set G (ρ0) is given in (30), and the reversed normal set H ′ (ρ0) is given by H ′ (ρ0) = {ρ i } i∈I |0 ≤ ρ i ≤ 1 − ρ 0 , ∀i ∈ I . Based on the monotonicity of Problem (P2-E), we can also design a poly-block approximation based algorithm (which is similar to Algorithm (Cen-Sub) in Sec. V-B) to solve Problem (P2-E) and obtain L (ρ0) . Due to space limitation, we skip the details of this algorithm. In summary, a sketch (i.e., Algorithm (Cen-Sub-FC)) to check the feasibility of Problem (SINR-M-SubP) is provided. Subcase ii) (as shown in Fig. 11(b)) If J i (χ i,(ρ0) ) ≤ P max i + nB giB , J i (0) ≤ P max i + nB giB , and J i (1) ≤ P max i + nB giB , then constraint (34) holds for ρ i ∈ (0, 1], which consequently yields the second case. Subcase iii) (as shown in Fig. 11(c)) If J i (χ i,(ρ0) ) ≤ P max i + nB giB , J i (0) ≤ P max i + nB giB , and J i (1) > P max i + nB giB , then there exists a special point v ∈ [χ i,(ρ0) , 1] such that J i (v) = P max i + nB giB , and (34) holds for ρ i ∈ (0, v]. As a result, we obtain the third case. Subcase iv) (as shown in Fig. 11(d)) If J i (χ i,(ρ0) ) ≤ P max i + nB giB , J i (0) > P max i + nB giB , and J i (1) ≤ P max i + nB giB , then there exists a special point v ∈ (0, χ i,(ρ0) ] such that J i (v) = P max i + nB giB and constraint (34) holds for ρ i ∈ [v, 1]. As a result, we obtain the fourth case.