Distributed stochastic power control in ad hoc networks: a nonconvex optimization case

Signal-to-interference-plus-noise-based power allocation in wireless ad hoc networks is inherently a nonconvex optimization problem because of the global coupling induced by the co-channel interference. To tackle this challenge, we first show that the globally optimal point lies on the boundary of the feasible region. This property is utilized to transform the utility maximization problem into an equivalent max–min problem with more structure. By using extended duality theory, penalty multipliers are introduced for penalizing the constraint violations, and the minimum weighted utility maximization problem is then decomposed into subproblems for individual users to devise a distributed stochastic power control algorithm, where each user stochastically adjusts its target utility to improve the total utility by simulated annealing (SA). The proposed distributed power control algorithm can guarantee global optimality at the cost of slower convergence due to SA involved in the global optimization. The geometric cooling scheme with suitable choice of penalty parameters is then used to improve the convergence rate. Next, by integrating the stochastic power control approach with the back-pressure algorithm, we develop a joint scheduling and power allocation policy to stabilize the queueing systems under random packet traffic. Finally, we generalize the above distributed power control algorithms to multicast communications, and show their global optimality for multicast traffic.

The broadcast nature of wireless transmissions makes wireless networks susceptible to interference, which deteriorates quality of service (QoS) provisioning. Power control is considered as a promising technique to mitigate interference. One primary objective of power control is to maximize the system utility that can achieve a variety of fairness objectives among users [1-4]. However, maximizing the system utility, under the physical interference model, often involves nonconvex optimization and it is known to be NP-hard, due to the complicated coupling among users through mutual interference effects [5].

Due to the nonconvex nature of the power control problem, it is challenging to find the globally optimal power allocation in a distributed manner. Notably, the authors of [6-9] devised distributed power control algorithms to find power allocations that can only satisfy the local optimality conditions, but global optimality could not be guaranteed in general, except for some special convexifiable cases (e.g., with strictly increasing log-concave utility functions). Another thread of work applied game-theoretic approaches to power control by treating it as a noncooperative game among transmitters [10,11]. However, distributed solutions that converge to a Nash equilibrium may be suboptimal in terms of maximizing the total system utility. Different from these approaches, the authors of [12] transformed the power control problem into a DC (difference of convex functions) optimization problem [13]. Then, the global optimal solution can be solved in a centralized manner with the branch-and-bound algorithm. Recent study [14] proposed a globally optimal power control scheme, named MAPEL, by exploiting the monotonic nature of the underlying optimization problem. However, the complexity and the centralized nature of MAPEL hinder its applicability in practical scenarios, and thus it can be treated rather as a benchmark for performance evaluation in distributed networks.

To find the globally optimal power allocation in a distributed setting, recent study [15] has proposed the SEER algorithm based on Gibbs sampling [16], which can approach the globally optimal solution in an asymptotic sense when the control parameter in Gibbs sampling tends to infinity. Notably, for each iteration in the SEER algorithm, each user utilizes Gibbs sampling to compute its transition probability distribution for updating its transmission power, where the requirement for message passing and computing the transition probability distribution in each iteration can be demanding when applied to ad hoc communications without centralized control.

A challenging task in distributed power control in ad hoc networks is to reduce the amount of message passing while preserving the global optimality. To tackle this challenge, we first show that the globally optimal point lies on the boundary of the feasible region. This property is utilized to transform the utility maximization problem into an equivalent max–min problem with more structure, which can be solved by combining recent advances in extended duality theory (EDT) [17] with simulated annealing (SA) [18]. Compared with the classical duality theory with nonzero duality gap for nonconvex optimization problems, EDT can guarantee zero duality gap between the primal and dual problems by utilizing nonlinear Lagrangian functions. This property allows for solving the nonconvex problem by its extended dual while preserving the global optimality with distributed implementation. Furthermore, as will be shown in Section “Power control for unicast communications”, for the subproblem of each individual user, the extended dual can then be solved through stochastic search with SA. In particular, we first transform the original utility maximization problem into an equivalent max–min problem. This step is based on the key observation that in the case with continuous and strictly increasing utility functions, the globally optimal solution is always on the boundary of the feasible (utility) region. Then, appealing to EDT and SA, we develop a distributed stochastic power control (DSPC) algorithm that stochastically searches for the optimal power allocation in the neighborhood of the feasible region’s boundary, instead of bouncing around in the entire feasible region.

Specifically, we first show that DSPC can achieve the global optimality in the underlying nonconvex optimization problem, although the convergence rate can be slow (but this is clearly due to the slow convergence nature of SA with logarithmic cooling schedule). Then, to improve the convergence rate of DSPC, we propose an enhanced DSPC (EDSPC) algorithm that employs the geometric cooling schedule [19] and performs a careful selection of penalty parameters. As a benchmark for performance evaluation, we also develop a centralized algorithm to search for the globally optimal solution over simplices that cover the feasible region. The performance gain is further verified by comparing our distributed algorithms with MAPEL [14], SEER [15], and ADP [6] algorithms. Worth noting is that the proposed DSPC and EDSPC algorithms do not require any knowledge of channel gains, which is typically needed in existing algorithms, and instead they need only the standard feedback of signal-to-interference-plus-noise (SINR) for adaptation.

Next, we integrate the proposed distributed power control approach with the back-pressure algorithm [20] and devise a joint scheduling and power allocation policy for improving the queue stability in the presence of dynamic packet arrivals and departures. This policy fits into the dynamic back-pressure and resource allocation framework and enables distributed utility maximization under stochastic packet traffic [21,22]. Then, we generalize the study to consider multicast communications, where a single transmission may simultaneously deliver packets to multiple recipients [23,24]. Specifically, we extend DSPC and EDSPC algorithms to multicast communications with distributed implementation, and show that these algorithms can also achieve the global optimality in terms of jointly maximizing the minimum rates on bottleneck links in different multicast groups.

The rest of the article is organized as follows. In the following section, we first introduce the system model, establish the equivalence between the utility maximization problem and its max–min form, and then develop both centralized and distributed algorithms for the max–min problem. Next, building on these power control algorithms, we develop in Section “Joint scheduling and power control for stability of queueing systems” a joint scheduling and power allocation policy to stabilize queueing systems. The generalization to multicast communications is presented in Section “Power control for multicast communications”. We conclude the article in “Conclusion” Section.

System model

We consider an ad hoc wireless network with a set of links, where the channel is interference-limited, and all L links treat interference as noise, as illustrated in Figure 1. Such a model of communication is readily applicable to cellular networks [1]. Each link consists of a dedicated transmitter-receiver pair.^a We denote by h_lk the fixed channel gain between user l’s transmitter and user k’s receiver, and by p_l the transmission power of link l with being its maximum power constraint. It follows that the received SINR for the lth user with a matched filter receiver is given by

where p = (p₁,…,p_L) is a vector of the users’ transmission powers and n_l is the noise power. Accordingly, the lth user receives the utility U_l(γ_l), where U_l(·) is continuous and strictly increasing. We assume that each user l’s utility is zero when γ_l = 0, i.e., U_l(0) = 0. For ease of reference, the key notation of this article is listed in Table 1.^b

Network utility maximization

We seek to find the optimal power allocation p^∗ that maximizes the overall system utility subject to the individual power constraints, given by the following optimization problem^c:

In general, (2) is a nonconvex optimization problem.^d In particular, if the utility function is the Shannon rate achievable over Gaussian flat fading channels, namely , where w_l > 0 is a weight associated with user l, (2) boils down to the weighted sum rate maximization problem, which is known to be nonconvex and NP-hard [5]. Note that the weights in (2) can serve as the fairness measures [25] for different scenarios. In particular, in queueing systems, packet queues for arrival rates within the stability region can be stabilized by solving this weighted sum rate maximization problem, where the instantaneous queue lengths are chosen as the weights. In Section “Joint scheduling and power control for stability of queueing systems”, we will discuss how to stabilize the packet queues by integrating our distributed power control algorithms with the back-pressure algorithm.

Let denote the feasible utility region, where for each point U = (U₁,…,U_L) in , there exists a power vector p such that U_l = U_l(γ_l(p)) for all . The feasible utility region is nonconvex, and in general, finding the globally optimal solution to (2) in is challenging. In the following example, we illustrate the geometry of for the utility function and evaluate the solutions to (2) given by some existing power control approaches discussed in Section “Introduction”.

Example

For the case with two links, Figure 2 illustrates the nonconvex feasible utility region for different system parameters. We compare the performance of the existing approaches [3,6,14,15] in Table 2.

Remarks

The solutions to (2) given by the authors of [3,6,14] are either distributed but suboptimal or optimal but centralized. In particular, Chiang et al. [3] solve (2) by using geometric programming (GP) under the high-SINR assumption, which yields a suboptimal solution to (2) when this assumption does not hold (e.g., this is the case in the example above). The ADP algorithm [6] can guarantee only local optimality^e in a distributed manner. The MAPEL algorithm [14] can achieve the globally optimal solutions but it is centralized with high computational complexity. Compared with these algorithms, the SEER algorithm [15] can guarantee global optimality in a distributed manner but message passing needed in each iteration can be demanding, i.e., each link needs the knowledge of the channel gains, the receiver SINR and the signal power of all the other links. It is worth noting that the performance of SEER hinges heavily on the control parameter that can be challenging to choose on the fly.

From network utility maximization to minimum weighted utility maximization

In order to devise low-complexity distributed algorithms that can guarantee global optimality, we first study the basic properties for the solutions to (2), before transforming (2) into a more structured max–min problem.

Lemma 1

The optimal solution to (2) is on the boundary of the feasible utility region.

Proof

Let U^∗ denote a globally optimal solution to (2) over , and γ^∗ denote the corresponding SINR that supports U^∗. Since U_l(·) is continuous and strictly increasing, proving that U^∗ is on the boundary of is equivalent to showing that γ^∗ is on the boundary of the feasible SINR region. Suppose that γ^∗ is not on the boundary of the feasible SINR region, which indicates that there exists some point such that for all and for some . Since U_l(·) for any is strictly increasing in γ_l, we have for all and for some , which contradicts the fact that γ^∗ is a globally optimal solution. Hence, Lemma 1 follows. □

Based on Lemma 1, if we can characterize the boundary of , then it is possible to solve (2) efficiently. Thus motivated, we first establish, by introducing a “contribution weight” for each user, the equivalence between (2) and the minimum weighted utility maximization problem.

Lemma 2

Problem (2) is equivalent to the following minimum weighted utility maximization:

Proof

Let denote the total utility. Since U_l(·) is nonnegative, we define x_l∈[0, 1] as a ratio for the contribution of user l’s utility to t. Therefore, U_l(γ_l(p)) = tx_l and . Then (2) can be rewritten as

In order to maximize t, it suffices then to relax in (4) as , which is equivalent to . Therefore, (4) can be treated as the hypograph form of (3), i.e., (4) and (3) are equivalent [26], thereby concluding the proof. □

By transforming (2) to this more structured max–min problem (3), the problem is reduced to finding a globally optimal x^∗, given which we can efficiently obtain a globally optimal solution, i.e., the tangent point of the hyperplane and , as illustrated in Figure 3. Intuitively speaking, x represents a search direction. Once we find the best search direction x^∗p^∗ can be obtained efficiently by searching along the direction of x^∗. Actually, for given x, (3) is quasi-convex.^f By introducing an auxiliary variable t, we obtain the following equivalent formulation:

which can be solved in polynomial time through binary search on t[26]. However, the optimal search direction x^∗ is difficult to find due to the nonconvex nature of the problem. In the following section, we study how to find the globally optimal search direction x^∗.

Centralized versus distributed algorithms

In this section, we study algorithms achieving global optimality for (3). First, we propose a centralized algorithm for (3), which will serve as a benchmark for performance comparison. Then, by using EDT and SA, we propose a distributed algorithm, DSPC, for the problem (3). Building on this, we propose an EDSPC algorithm to improve the convergence rate of DSPC.

A centralized algorithm

Based on Lemmas 1 and 2, we develop a centralized algorithm (Algorithm 1) to solve the max–min optimization problem (3) under consideration. Roughly speaking, by dividing the simplex into many small simplices, the algorithm can find the optimal point on the boundary of . Figure 4 illustrates how the simplex cutting is performed for the case with three links. Compared with the MAPEL algorithm [14], Algorithm 1 directly computes the points on the boundary, instead of constructing a series of polyblocks to approximate the boundary of the feasible region.

Algorithm 1

Initialization: Choose the approximation factor ε > 0, and construct the initial simplex with the vertex set V = {v₁,…,v_L}, where v_l = e_l and e_l is the lth unit coordinate vector. Let be the center of S. Compute p^∗ by solving (5) at the point x = v_c. Denote as the diameter of .

Repeat

1. Divide each simplex by using bisection method, which chooses the midpoint of one of the longest edges of the simplex , i.e., , where v_r and v_s are the end points of a longest edge of the simplex. In this case, the simplex is subdivided into two simplices and .

2. For each new simplex , compute the diameter and p^∗ by solving (5) at x given by the center point of the simplex.

3. Find the current best solution to (3) and the maximal diameter δ^m in these new subdivided simplices.

Until δ^m < ε.

Proposition 1

Algorithm 1 converges monotonically to the globally optimal solution to (3) as the approximation factor ε approaches zero.

Proof

For given ε, Algorithm 1 divides the simplex until the maximal diameter of the subdivided simplices δ^m is less than ε. Let d(ε) denote the maximum distance between the optimal solution x^∗ and the center point of the simplex that contains x^∗. Obviously, d(ε) is bounded by δ^m. Since δ^m decreases with the decreasing of ε, therefore d(ε) decreases monotonically with the decreasing of ε, i.e., the solution given by Algorithm 1 monotonically converges to x^∗. As εapproaches zero, Algorithm 1 exhaustively searches every point in the simplex , thereby concluding the proof. □

Remarks

Algorithm 1 can be used to obtain an ε-optimal solution with |x − x^∗| ≤ ε. That is to say, by controlling ε, one can strike a balance between the optimality and the computation time. Since finding the globally optimal solution requires centralized implementation, Algorithm 1 will be used only as a benchmark for performance evaluation of distributed algorithms.

DSPC algorithm

Next, we devise a DSPC algorithm based on EDT [17] and SA [18]. Compared to the classical duality theory with nonzero duality gap for nonconvex optimization problems, EDT can guarantee zero duality gap between the primal and dual problems by utilizing nonlinear Lagrangian functions. This property allows for solving the nonconvex problem by its extended dual while preserving the global optimality in distributed implementation. To this end, we first introduce auxiliary variables and use EDT to transform (3) with the auxiliary variables into an unconstrained problem. Then, we solve the unconstrained problem by using the SA mechanism. Specifically, we define and rewrite (3) as

Next, we use EDT to write the Lagrangian function for (6) as

where , and and are the penalty multipliers for penalizing the constraint violations. Based on EDT [17], there exist finite α^∗ ≥ 0 and , for all , such that, for any α > α^∗ and , the solution to (7) is the same as (6). Note that (7) does not include the constraints of p_l, x_l, and t_l for each user, and there will be no constraint violation when each user updates these variables locally. Therefore, the minimization of (7) with respect to the primal variables (p, x, and t) can be carried out individually by each user in a distributed fashion.

The next key step is to perform a stochastic local search by each user based on SA. Let t_l, x_l, and p_l denote the primal values of the lth user, and and denote the new values randomly chosen by the lth user. Accordingly, can be treated as a new target utility for the lth user. To achieve this target utility, the lth user updates by

where γ_l is the current SINR measured at the lth user’s receiver. Note that (8) does not need any information of channel gains, except the feedback of SINR γ_l. Since (8) corresponds to the distributed power control algorithm of standard form as described in [27],^g it converges geometrically fast to the target utility. Thus, we assume that each user l updates p_l at a faster time-scale than t_l and x_l such that p_l always converges before the next update of t_l and x_l. Next, we use SA to update t_l and x_l in a stochastic operation. By using the analogy with annealing in metallurgy, SA was proposed in [18] to mimic the behavior of the microscopic constituents in heating and controlled cooling of a material. By allowing occasional uphill moves, SA is able to escape from the local optimal points. In particular, let Δ denote the difference between L(p_l, x_l, t_l|p_−l, x_−l, t_−l, α, β) and , where y_−l is the vector y without the lth user’s variable. If Δ ≥ 0, i.e., , and reduce Lagrangian (7), then they are accepted with probability 1; otherwise, they are accepted with probability , where T is a control parameter and sometimes it is called temperature. Note that, as T decreases, the acceptance of uphill move becomes less and less probable, and therefore a fine-grained search is needed. It has been shown that, as T approaches 0 according to a logarithmic cooling schedule, SA converges to a globally optimal point [16,19]. To compute Δ locally by each user l, user l needs to broadcast the terms t_l, x_l and , whenever any of these terms changes.

Note that the target utility t_lx_l may not be feasible, i.e., the target utility cannot be achieved even though the user transmits at the maximum power. In this case, it can be shown that the power of those users with feasible target utilities will converge to a feasible solution, whereas the other users that cannot achieve the target utility will continue to transmit at maximum power [1]. If some target utility is not feasible as T tends to 0, based on EDT, the current values of α and β do not satisfy α > α^∗ or for all . Therefore, each user l also needs to update α and β_l. In particular, if any constraint is violated, α and β_l are updated as follows:

where σ and ϱ_l are used to control the rate of updating α and β_l. A detailed description of DSPC algorithm is given in Algorithm 2.

Remarks:

(1) In Algorithm 2, each user randomly picks , where denotes the maximum utility of the user l when the user l transmits at the maximum power while the other users do not transmit, and . Note that can be computed by each user locally. Further, we assume that each user broadcasts before running the algorithm so that is also known by each user.

(2) In practice, after initialization, α and β_l increase in proportion to the violation of the corresponding constraint, which may lead to excessively large penalty values. Since it is beneficial to periodically scale down the penalty values to ease the unconstrained optimization, α and β_l are scaled down by multiplying with a random value (it can be chosen between 0.7 and 0.95 according to [17]), if the penalty decrease condition is satisfied, i.e., the maximum violation of constraints is not decreased after consecutively running Step 1 in Algorithm 2 several times, e.g., five times in [17].

(3) In Algorithm 2, each user requires the knowledge of T and time epochs {τ₁, τ₂,…} to update t_l and x_l, which can be determined and informed to each user offline.

Algorithm 2 DSPC

Initialization: Choose ε > 0. Let α = 0, β_l = 0, , and randomly choose p, x and t.

Step 1: update primal variablesSet T = T₀, and select a sequence of time epochs {τ₁, τ₂,…} in continuous time.

Repeat for each user l

1. Randomly pick and , and update according to (8).

2. Keep sensing the change of broadcast by other users.

3. Compute Δ, and accept , , and with probability 1, if Δ≥0, or with probability , otherwise.

4. Broadcast and , if and are updated.

5. For each time epoch τ_i, update .

Until T < ε.

Step 2: update penalty variables

For each user l,

1. Update α and β_l according to (9), and scale down α and β_l, if the penalty decrease condition is satisfied.

2. Go to Step 1 until no constraint is violated.

Proposition 2

The DSPC algorithm (Algorithm 2) converges almost surely to a globally optimal solution to (3), as temperature T in SA decreases to zero.

Proof

To show that Algorithm 2 converges almost surely to a globally optimal solution to (3), we only need to show that when α > α^∗ and for all , Algorithm 2 can converge almost surely to a globally optimal solution to (6), since (3) is equivalent to (6), and if the solution does not satisfy the constraints of (6), α and β_l will increase in proportion to the violation of the corresponding constraint. Since Algorithm 2 uses SA with the logarithmic cooling schedule, based on [16,19] it can converge almost surely to a globally optimal solution to (7), which is also a globally optimal solution to (6) based on EDT when α > α^∗ and for all [17]. Hence, Proposition 2 follows. □

Remarks

The DSPC algorithm can guarantee global optimality in a distributed manner without the need of channel information. In particular, it needs the information of t_l and x_l, and can adapt to channel variations by utilizing the SINR feedback. However, the convergence rate of DSPC is slow due to the use of logarithmic cooling schedule.

EDSPC algorithm

It can be seen from Algorithm 2 that it is critical to find the optimal penalty variables α and β for computing (7). Moreover, a logarithmic cooling schedule is used to ensure convergence to a global optimum. To improve the convergence rate, we propose next an EDSPC algorithm by empirically choosing the initial penalty values α₀ and β₀ and employing a geometric cooling schedule[18], which reduces the temperature T in SA by T = ξT, 0 < ξ < 1, at each time epoch. Compared with the logarithmic cooling schedule, T converges to 0 much faster under the geometric cooling schedule, which in turn improves the convergence rate beyond DSPC. The resulting solution is given in Algorithm 3.

We note that although EDSPC converges much faster than DSPC, it may yield only near-optimal solutions. Based on EDT, we choose and , to satisfy the optimality conditions for penalty variables. Obviously, by choosing large α₀ and β_0l, these conditions can be always satisfied. Nevertheless, very large penalties introduce heavy costs for constraint violations such that EDSPC may end up with a feasible but suboptimal solution. Therefore, the selection of initial penalty values plays a critical role in the performance of EDSPC and deserves more attention in future work. In practice, we can choose the initial penalties based on the maximum value of the constraint that is associated with each of the penalty variables. This choice performs well in the simulations. For example, we can choose for the constraint t_lx_l ≤ U_l(γ_l(p)).

Algorithm 3 EDSPC

Initialization: Choose ε > 0. Let α = α₀, β_l = β_0l, , and randomly choose p, x and t.Set T = T₀, and select a sequence of time epochs {τ₁, τ₂,…} in continuous time.

Repeat for each userl

1. Randomly pick and , and update according to (8).

2. Keep sensing the change of broadcast by other users.

3. Compute Δ, and accept , , and with probability 1, if Δ ≥ 0, or with probability , otherwise.

4. Broadcast and , if and are updated.

5. For each time epoch τ_i, update T = ξT.

Until T < ε.

Performance evaluation

In this section, we evaluate the utility and convergence performance of Algorithms 2 and 3 (DSPC^h and EDSPC). We consider a wireless network with six links randomly distributed on a 10-by-10 m² square area. The channel gains h_lk are equal to , where d_lk represents the distance between the transmitter of user l and the receiver of user k. We assume , and for all , and consider one randomly generated realization of channel gains given by

Figure 5 shows how the total utility in the EDSPC algorithm converges over time, when we choose all the initial penalty values equal to 10. Also, we choose ξ = 0.9, ρ = 1, and ϱ = 1, and use Algorithm 1 as a benchmark to evaluate the optimal performance. As shown in Figure 5, the EDSPC algorithm approaches the optimal utility, when the initial penalty values are carefully chosen. Moreover, the convergence rate of the EDSPC algorithm is much faster than DSPC, since DSPC continues updating the penalty values even after the optimal solution is found for the current penalty values. Figure 6 illustrates the average performance (with confidence interval) of DSPC, EDSPC, SEER, and ADP under 100 random initializations, with the same system parameters as used in Figure 5. As shown in Figure 6, both DSPC and EDSPC are robust against the variations of initial values.

Figures 5 and 6 compare the proposed algorithms with the SEER and ADP. As mentioned in Section “Introduction”, ADP can only guarantee local optimality. Therefore, for nonconvex problems (e.g., in this example), ADP may converge to a suboptimal solution. As noted in [15], the performance of SEER heavily hinges on the control parameter that can be challenging to choose in online operation. In contrast, DSPC can approach the globally optimal solution regardless of the initial parameter selection, but the convergence rate may be slower. Furthermore, EDSPC improves the convergence rate, but in this case the initial penalty values would impact how close it can approach the optimal point. In terms of message passing, our algorithms do not require individual links to know the channel gains (including its own channel gain), the receiver SINR of the other links and the signal power of the other links, which are all needed in the SEER algorithm.

In Section “Power control for unicast communications”, we studied the distributed power allocation, by using DSPC and EDSPC, for utility maximization in the saturated case with uninterrupted packet traffic. In this section, we generalize the study by considering a queueing system with dynamic packet arrivals and departures. Specifically, we develop a joint scheduling and power allocation policy to stabilize packet queues by integrating our power control algorithms with the celebrated back-pressure algorithm [20].

Stability region and throughput optimal power allocation policy

Consider the same wireless network model with L links as in Section “Power control for unicast communications”. We assume that there are S classes of users in the system, and that the traffic brought by users of class s follows , which are i.i.d. sequences of random variables for all l = 1,…,L and s = 1,…,S, where A_sl(t) denotes the amount of traffic generated by users of class s that enters the link l in slot t. We assume that the second moments of the arrival process are finite. Let and denote the current backlog in the queue of class s in slot t on the transmitter and receiver sides of link l, respectively. The queue length evolves over time as

where denotes the transmission rate of link l for users of class s. The third term in (10) denotes the traffic from the other links. The queue length process forms a Markov chain.

Let ψ_s denote the first moment of , i.e., the load brought by users of class s. As is standard [20,21,28], the stability region is defined as follows.

Definition 1

The stability region ∧ is the closure of the set of allfor which there exists some feasible power allocation policy under which the system is stable, i.e.,, where , denotes the set of feasible power allocation, r_l(p) denotes the rate of link l under power allocationp, and E_sl = 1 is the indicator that the path of users of class s uses link l, and E_sl = 0, otherwise.

For the sake of comparison, the throughput regionⁱ of the corresponding saturated case is defined as the set of all feasible link rates, i.e., . In general, the throughput region may be different from the stability region ∧, except for some special cases (e.g., in slotted ALOHA systems the throughput region and the stability region are the same [29] for two links and in a multiple-access channel the information theoretic capacity region is equivalent to its stability region under specific feedback assumptions [30]).

The queueing system is stable if the arrival rates of packet queues are less than the service rates such that the queue lengths do not grow to infinity [31]. In order to stabilize packet queues, it is critical to find the optimal scheduling and power allocation policy that maximizes the weighted sum rate given by (11). By integrating our power control algorithms with the back-pressure algorithm, we propose a joint scheduling and power allocation policy presented in Algorithm 4 to stabilize the queueing system.

Proposition 3

The joint scheduling and power allocation policy (Algorithm 4) can stabilize the system such that, when the traffic loadis strictly interior to the stability region ∧, i.e., there exists some ε > 0 such that .

The proof is similar to that in [21,32], and is omitted for brevity.

Note that Algorithm 4 can be viewed as a dynamic back-pressure and resource allocation policy [32], crafted towards solving the weighted sum rate maximization problem (11). Specifically, by using the DSPC algorithm, Algorithm 4 can be implemented distributively to find the globally optimal resource allocation. We should caution that EDSPC can be applied to improve the convergence rate of Stage 2 in Algorithm 4 but it may render a suboptimal schedule (i.e., it can not stabilize all possible within ∧), due to the fact that EDSPC may not always find the global optimal power allocation.

To reduce the complexity, we can consider a policy that computes (11) periodically every few slots, and it can be shown that this policy can also stabilize the system, when is strictly interior to the stability region ∧[33,34].

Algorithm 4 Joint scheduling and power allocation policy

Stage 1: For each link l, select a link weight according to , where the difference of queue lengths of class s is , if the receiver of link l is not the destination of class s’s traffic, and , otherwise.

Stage 2: Compute the optimal power allocation p^∗ in each slot t by solving the following problem with DSPC algorithm

Thus, the transmission rate of link l in slot t is given by .

Stage 3: Let denote the class scheduled in slot t; if multiple classes satisfy this condition, then is randomly chosen as one of these classes. Then, schedule these classes according to the solution given by Stage 2.

Performance evaluation

In this section, we present numerical results to illustrate the use of Algorithm 4 for stabilizing a queueing system. We consider a one-hop network (i.e., E = {E_sl} is the identity matrix) with two users (classes), where the channel gains are h₁₁ = 0.3, h₁₂ = 0.5, h₂₁ = 0.03, and h₂₂ = 0.8, and the noise power is 0.1 for each link. The maximum transmission power is set to 1 and 2 for links 1 and 2, respectively. Besides, we assume that the users of class s arrive at the network according to a Poisson process with rate λ_s, and that the size of packet batch for users of class s follows an exponential distribution with mean ν_s. The load brought by users of class s is then ψ_s = λ_sν_s. Figure 7 shows the stability region ∧ and compares it with the throughput region of the corresponding saturated case. The stability region follows from the union of link rates that are conditioned on whether the other link is backlogged or not [29,30]. First, we derive the stability region for the given power allocation. Then, we vary power allocation in the feasible region, and by taking the envelope of these regions, we obtain the overall stability region shown in Figure 7. However, different from the previous cases, where the throughput region is the same as the stability region, e.g., in a slotted ALOHA system with two links [29] and in a multiple-access channel [30], the throughput region under the SINR model is strictly smaller than the stability region (due to the underlying nonconvex optimization problem), as observed from Figure 7, which is the convex hull of , i.e., , achievable by timesharing across different transmission modes.^j

Then, we vary the arrival rate λand the average batch size ν to change the traffic intensity ψ = λν. Assuming that the arrival rate and the average batch size of each user are the same, we compare in Figure 8 the sample paths of each user’s queue length for ψ = 1 (λ = 1, ν = 1) with ψ = 1.5 (λ = 1.5, ν = 1). When ψ = 1, which falls in the stability region shown in Figure 7, the system is stabilized by using Algorithm 4. On the other hand, the system becomes unstable when ψ = 1.5, which is outside the stability region. Figure 9 illustrates the average delay of the system as a function of the arrival rates. The delay is finite for small loads and grows unbounded when the loads are outside the stability region.

Due to wireless multicast advantage [23], multicasting enables efficient data delivery to multiple recipients with a single transmission. In this section, we extend the DSPC algorithms in Section “Power control for unicast communications” to support multicast communications.

System model

Beyond the model described in Section “Power control for unicast communications”, we consider that each user l has one transmitter and a set of receivers. The corresponding transmission rate, r_l, is determined by the bottleneck link among these transmitter–receiver pairs, i.e., , where r_lm denotes the link rate between the transmitter of user l and its receiver m, and it is calculated from the Shannon rate for Gaussian, flat fading channels. Here, we do not consider the general broadcast capacity region but rather focus on maximizing the bottleneck link rates.

Network utility maximization

We seek to find the optimal power allocation p^∗ that maximizes the overall system utility subject to the power constraints in multicast communications, as follows:

Similar to (2), (12) is nonconvex due to the complicated interference coupling between individual links. Different from the techniques used in Section “Power control for unicast communications”, we relax in (12) as , in order to devise distributed algorithms solving (12). Thus, (12) can be rewritten as

Distributed global optimization algorithms

We develop next distributed algorithms that can find the globally optimal solutions to (13) based on EDT and SA. To this end, we first rewrite the optimization problem (13) as

Next, we use EDT to write the Lagrangian function for (14) as

where are the penalty multipliers. From EDT, there exist finite for all such that, for any , the solution to (15) is the same as (14) [17]. Note that (15) does not include the constraint of p_l for each user. Therefore, there will be no constraint violation when each user updates the transmission power locally, while minimizing (15) in a distributed operation.

As in Section “Power control for unicast communications”, the key step is to let each user perform a local stochastic search based on SA. Let r_l and p_l denote the primal values of the lth user, and denote the new value randomly chosen by the lth user, which is treated as a new target transmission rate for the lth user. Different from the unicast communications case, the lth user updates by

where γ_lm is the current SINR measured at the receiver m of user l. Note that (16) does not need any information of the channel gains, except the feedback of SINR γ_lm from the intended receivers. Since (16) is in standard form as described in [27], it converges geometrically fast to the target transmission rate. The steps to update _rl and α_lm are similar to DSPC Algorithm 2 in Section “Power control for unicast communications”. Note that the target transmission rate r_l may not be feasible, i.e., the target utility cannot be achieved even though the user transmits at the maximum power. In this case, it can be shown that the power of those users with feasible target transmission rates will converge to a feasible solution, whereas the other users that cannot achieve the target transmission rate will continue to transmit at maximum power [1]. A detailed description of DSPC algorithm for multicast communications is presented in Algorithm 5.

Remarks

In Algorithm 5, each user randomly picks , where , and is the maximum link rate between the transmitter of the user l and its receiver m, when the user l transmits at the maximum power while the other users do not transmit.

Proposition 4

The DSPC algorithm for multicast communications (Algorithm 5) converges almost surely to a globally optimal solution to (13), as temperature T in SA approaches zero.

Proof

The proof is based on EDT and SA arguments, and follows similar steps used in the proof of Proposition 2, and it is omitted here for brevity. □

To improve the convergence rate, we also propose an enhanced algorithm for Algorithm 5 by empirically choosing the initial penalty values and employing a geometric cooling schedule. The resulting algorithm is given in Algorithm 6. Similar to the unicast case, Algorithms 5 and 6 do not need any knowledge of channel information (or the bottleneck link) and they are dynamically updated by the SINR feedback from the intended receivers.

Algorithm 5 DSPC for multicast communications

Initialization: Choose ε > 0. Let α_lm = 0, and randomly choose rand p.

Step 1: update primal variablesSet T = T₀, and select a sequence of time epochs {τ₁, τ₂,…} in continuous time.

Repeat for each user l

1. Randomly pick , and update according to (16).

2. Keep sensing the change of broadcast by other users.

3. Let Δ be the difference between L(p, r_l|r_−l, {α_lm}) and , and accept and with probability 1, if Δ ≥ 0, or with probability , otherwise.

4. Broadcast , if is accepted.

5. For each time epoch τ_i, update .

Until T < ε.

Step 2: update penalty variables

For each user l,

1. Update , and scale down α_lm, if the condition of penalty decrease is satisfied.

2. Go to Step 1 until no constraint is violated.

Algorithm 6 EDSPC for multicast communications

Initialization: Choose ε > 0. Let , and randomly choose r and p.

Set T = T₀, and select a sequence of time epochs {τ₁, τ₂, …} in continuous time.Repeat for each user l

1. Randomly pick , and update according to (16).

2. Keep sensing the change of broadcast by other users.

3. Let Δ be the difference between L(p, _rl|r_−l, {α_lm}) and , and accept and with probability 1, if Δ ≥ 0, or with probability , otherwise.

4. Broadcast , if is accepted.

5. For each time epoch τ_i, update T = ξT.

Until T < ε.

Performance evaluation

In this section, we evaluate the performance of Algorithms 5 and 6 for multicast communications. We consider a wireless network with four transmitters and each transmitter has two receivers. These transmitters and receivers are randomly placed on a 10-by-10 m² square area. The channel gains h_lm are equal to , where d_lm represents the distance between the transmitter l and the receiver m. The channel gains h_lm are equal to , where d_lmrepresents the distance between the transmitter l and the receiver m. We assume U_l(r_l) = r_l, , and for all and . Figure 10 illustrates the fast convergence performance of Algorithms 5 and 6 in multicast communications.^k Besides, we examine the average performance (with confidence interval) of DSPC and EDSPC for multicast communications under 100 random initializations with the same system parameters as in the case shown in Figure 10. As illustrated in Figure 11, both Algorithms 5 and 6 are robust against the initial value variations.

We studied the distributed power control problem of optimizing the system utility as a function of the achievable rates in wireless ad hoc networks. Based on the observation that the global optimum lies on the boundary of the feasible region for unicast communications, we focused on the equivalent but more structured problem in the form of maximizing the minimum weighted utility. Appealing to EDT, we decomposed the minimum weighted utility maximization problem into subproblems by using penalty multipliers for constraint violations. We then proposed a DSPC algorithm to seek a globally optimal solution, where each user stochastically announces its target utility to improve the total system utility via SA. In spite of the nonconvexity of the underlying problem, the DSPC algorithm can guarantee global optimality, but only with a slow convergence rate. Therefore, we proposed an EDSPC to improve the convergence rate with geometric cooling schedule in SA. We then compared DSPC and EDSPC with the existing power control algorithms and verified the optimality and complexity reduction.

Next, we proposed the joint scheduling and power allocation policy for queueing systems by integrating our distributed power control algorithms with the back-pressure algorithm. The stability region was evaluated, which is shown to be strictly greater than the throughput region in the corresponding saturated case. Beyond unicast communications, we generalized our power control algorithms to multicast communications by jointly maximizing the minimum rates on bottleneck links in different multicast groups. Our DSPC approach guarantees global optimality without the need of channel information, while reducing the computation complexity, in general systems with unicast and multicast communications, and applies to both backlogged and random traffic patterns.

^a We use the terms “user” and “link” interchangeably throughout the article.

^b We use bold symbols (e.g., p) to denote vectors and calligraphic symbols (e.g., ) to denote sets.

^c The QoS constraint for each link can be incorporated in (2), and the proposed algorithms in the following section can easily be adapted to this case at the cost of added notational complexity.

^d For some special utility functions U_l(·), (2) can be transformed into a convex problem [3]. In this article, we focus on the nonconvex case that cannot be transformed to a convex problem by change of variables.

^e The local optimal solution found by ADP matches the globally optimal solution only in one of the cases that are illustrated in Table 2.

^f By definition, a function is quasi-convex, if its domain dom f and all its sublevel sets , for , are convex [26].

^g A power control algorithm is of standard form, if the interference function (the effective interference each link must overcome) is positive, monotonic and scalable in power allocation [27].

^h The geometric cooling schedule is employed to accelerate the convergence rate of DSPC in the simulation. DSPC updates penalty values until they satisfy the threshold-based optimality condition.

ⁱ Note that the feasible utility region defined in Section “Power control for unicast communications” is the throughput region, when the utility function is the same as the rate function.

^j The transmission mode is defined as the transmission rate pair within the throughput region .

^k The other existing algorithms have specifically been designed for unicast communications; therefore, they are excluded here from the performance comparison.

The authors declare that they have no competing interests.

This study was supported in part by the DoD MURI Project FA9550-09-1-0643 and the AFOSR grants FA9550-10-C-0026 and FA9550-11-C-0006.

1. M Chiang, P Hande, T Lan, CW Tan, Power control in wireless cellular networks. Found. Trends Netw 2(4), 381–553 (2008)

2. D Julian, M Chiang, D O’Neill, S Boyd, Qos and fairness constrained convex optimization of resource allocation for wireless cellular and ad hoc networks. Proc. IEEE INFOCOM, vol. 2, 477–486 (2002) (New York, USA)

3. M Chiang, CW Tan, D Palomar, D O’Neill, D Julian, Power control by geometric programming. IEEE Trans. Wirel. Commun 1(7), 2640–2651 (2007)

4. M Xiao, NB Shroff, EKP Chong, A utility-based power control scheme in wireless cellular systems. IEEE/ACM Trans. Netw 11(2), 210–221 (2003). Publisher Full Text

5. Z-Q Luo, S Zhang, Dynamic spectrum management: complexity and duality. IEEE J. Sel. Topics Signal Process 2(1), 57–73 (2008)

6. J Huang, R Berry, M Honig, Distributed interference compensation for wireless networks. IEEE J. Sel. Areas Commun 24(5), 1074–1084 (2006)

7. P Hande, S Rangan, M Chiang, X Wu, Distributed uplink power control for optimal SIR assignment in celluar data networks. IEEE/ACM Trans. Netw 16(6), 1420–1433 (2008)

8. J Papandriopoulos, S Dey, J Evans, Optimal and distributed protocols for cross-layer design of physical and transport layers in MANETs. IEEE/ACM Trans. Netw 16(6), 1392–1405 (2008)

9. J Papandriopoulos, JS Evans, SCALE: a low-complexity distributed protocol for spectrum balancing in multiuser DSL networks. IEEE Trans. Inf. Theory 55(8), 3711–3724 (2009)

10. CU Saraydar, NB Mandayam, DJ Goodman, Efficient power control via pricing in wireless data networks. IEEE Trans. Commun 50(2), 291–303 (2002). Publisher Full Text

11. T Alpcan, T Basar, R Srikant, E Altman, Wirel. Netw 8(6), 659–670

12. Y Xu, T Le-Ngoc, S Panigrahi, Global concave minimization for optimal spectrum balancing in multi-user DSL networks. IEEE Trans. Signal Process 56(7), 2875–2885 (2008)

13. R Horst, H Tuy, in Global Optimization—Deterministic Approaches (Springer, New York, 2006) PubMed Abstract | Publisher Full Text

14. L Qian, YJ Zhang, J Huang, MAPEL: achieving global optimality for a non-convex power control problem. IEEE Trans. Wirel. Commun 8(3), 1553–1563 (2009)

15. L Qian, YJ Zhang, M Chiang, Globally optimal distributed power control for nonconcave utility maximization. Proc. IEEE GLOBECOM, 1–6 (2010) (Miami, USA)

16. S Geman, D Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell 6(6), 721–741 (1984). PubMed Abstract

17. Y Chen, M Chen, Extended duality for nonlinear programming. Comput. Optim. Appl 47(1), 33–59 (2010). Publisher Full Text

18. S Kirkpatrick, CD Gelatt, JMP Vecchi, Optimization by simulated annealing. Science 220(4598), 671–680 (1983). PubMed Abstract | Publisher Full Text

19. B Hajek, Cooling schedules for optimal annealing. Math. Oper. Res 13(2), 311–329 (1988). Publisher Full Text

20. L Tassiulas, A Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 37(12), 1936–1948 (1992). Publisher Full Text

21. MJ Neely, E Modiano, CE Rohrs, Dynamic power allocation and routing for time varying wireless networks. IEEE J. Sel. Areas Commun 23(1), 89–103 (2005)

22. H-W Lee, E Modiano, LB Le, Distributed throughput maximization in wireless networks via random power allocation. IEEE Trans. Mob. Comput 11(4), 577–590 (2011)

23. JE Wieselthier, GD Nguyen, A Ephremides, On construction of energy-efficient broadcast and multicast trees in wireless networks. Proc. IEEE INFOCOM, vol. 2, 585–594 (2000) (Tel Aviv, Israel)

24. K Wang, CF Chiasserini, JG Proakis, RR Rao, Joint scheduling and power control supporting multicasting in wireless ad hoc networks 4(4), 532–546 Ad Hoc Netw

25. J Mo, J Walrand, Fair end-to-end window-based congestion control. IEEE/ACM Trans. Netw 8(5), 556–567 (2000). Publisher Full Text

26. S Boyd, L Vandenberghe, in Convex Optimization (Cambridge University Press, Cambridge, UK, 2004)

27. RD Yates, A framework for uplink power control in cellular radio systems. IEEE J. Sel. Areas Commun 13(7), 1341–1347 (1995). Publisher Full Text

28. X Lin, NB Shroff, R Srikant, On the connection-level stability of congestion-controlled communication networks. IEEE Trans. Inf. Theory 54(5), 2317–2338 (2008)

29. R Rao, A Ephremides, On the stability of interacting queues in a multiple-access system. IEEE Trans. Inf. Theory 34(5), 918–930 (1988). Publisher Full Text

30. A ParandehGheibi, M Medard, A Ozdaglar, A Eryilmaz, Information theory vs. queueing theory for resource allocation in multiple access channels. Proc. IEEE Pers. Ind. Mob. Radio Commun, 1–5 (2008) ((Nice, France), pp, 2008), . 1–5

31. R Loynes, The stability of a queue with non-interdependent inter-arrival and service times. Proc. Camb. Philos. Soc 58, 497–520 (1962). Publisher Full Text

32. L Georgiadis, MJ Neely, L Tassiulas, Resource allocation and cross-layer control in wireless networks. Found. Trends Netw 1(1), 1–149 (2006)

33. P Chaporkar, S Sarkar, Stable scheduling policies for maximizing throughput in generalized constrained queueing systems. IEEE Trans. Autom. Control 53(8), 1913–1931 (2008)

34. Y Yi, J Zhang, M Chiang, Delay and effective throughput of wireless scheduling in heavy traffic regimes: vacation model for complexity. Proc. ACM Mobihoc, 55–64 (2009) (New York, USA)