Abstract
Signaltointerferenceplusnoisebased power allocation in wireless ad hoc networks is inherently a nonconvex optimization problem because of the global coupling induced by the cochannel 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 backpressure 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.
Keywords:
Distributed power control; Nonconvex optimization; Extended duality theory; Simulated annealing; Queue stability; Unicast communications; Multicast communicationsIntroduction
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 [14]. However, maximizing the system utility, under the physical interference model, often involves nonconvex optimization and it is known to be NPhard, 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 [69] 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 logconcave utility functions). Another thread of work applied gametheoretic 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 branchandbound 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 signaltointerferenceplusnoise (SINR) for adaptation.
Next, we integrate the proposed distributed power control approach with the backpressure 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 backpressure 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.
Power control for unicast communications
System model
We consider an ad hoc wireless network with a set
where p = (p_{1},…,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}
Figure 1. System model.
Table 1. Summary of the notations and definitions
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
Let
Example
For the case with two links, Figure
2 illustrates the nonconvex feasible utility region
Figure 2. The feasible utility region
Table 2. The performance of the existing approaches for Case I and II
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 highSINR 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 lowcomplexity 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
Based on Lemma 1, if we can characterize the boundary of
Lemma 2
Problem (2) is equivalent to the following minimum weighted utility maximization:
Proof
Let
In order to maximize t, it suffices then to relax
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
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^{∗}.
Figure 3. An illustration of the max–min problem for the case with two links.
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
Figure 4. An illustration of the simplex cutting for the case with three links.
Algorithm 1
Initialization: Choose the approximation factor ε > 0, and construct the initial simplex
Repeat
1. Divide each simplex
2. For each new 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
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
Next, we use EDT to write the Lagrangian function for (6) as
where
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
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 timescale 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
Note that the target utility t_{l}x_{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
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
(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 {τ_{1}, τ_{2},…} 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,
Step 1: update primal variablesSet T = T_{0}, and select a sequence of time epochs {τ_{1}, τ_{2},…} in continuous time.
Repeat for each user l
1. Randomly pick
2. Keep sensing the change of
3. Compute Δ, and accept
4. Broadcast
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
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 α_{0} and β_{0} 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 nearoptimal
solutions. Based on EDT, we choose
Algorithm 3 EDSPC
Initialization: Choose ε > 0. Let α = α_{0}, β_{l }= β_{0l},
Repeat for each userl
1. Randomly pick
2. Keep sensing the change of
3. Compute Δ, and accept
4. Broadcast
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 10by10 m^{2} square area. The channel gains h_{lk} are equal to
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.
Figure 5. Convergence performance of DSPC, EDSPC, SEER, and ADP.
Figure 6. Comparison of the average utility performance (with confidence interval) of DSPC, EDSPC, SEER, and ADP.
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.
Joint scheduling and power control for stability of queueing systems
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 backpressure 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
where
Let ψ_{s} denote the first moment of
Definition 1
The stability region ∧ is the closure of the set of all
For the sake of comparison, the throughput region^{i}
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 backpressure 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
The proof is similar to that in [21,32], and is omitted for brevity.
Note that Algorithm 4 can be viewed as a dynamic backpressure 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
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
Algorithm 4 Joint scheduling and power allocation policy
Stage 1: For each link l, select a link weight according to
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
Performance evaluation
In this section, we present numerical results to illustrate the use of Algorithm 4
for stabilizing a queueing system. We consider a onehop network (i.e., E = {E_{sl}} is the identity matrix) with two users (classes), where the channel gains are h_{11} = 0.3, h_{12} = 0.5, h_{21} = 0.03, and h_{22} = 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
Figure 7. Comparison of the stability region and the throughput region.
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.
Figure 8. Comparison of sample paths of a user’s queue length for different traffic loads.
Figure 9. Average delay of the system versus system loads.
Power control for multicast communications
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
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
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
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
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
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,
Step 1: update primal variablesSet T = T_{0}, and select a sequence of time epochs {τ_{1}, τ_{2},…} in continuous time.
Repeat for each user l
1. Randomly pick
2. Keep sensing the change of
3. Let Δ be the difference between L(p, r_{l}r_{−l}, {α_{lm}}) and
4. Broadcast
5. For each time epoch τ_{i}, update
Until T < ε.
Step 2: update penalty variables
For each user l,
1. Update
2. Go to Step 1 until no constraint is violated.
Algorithm 6 EDSPC for multicast communications
Initialization: Choose ε > 0. Let
Set T = T_{0}, and select a sequence of time epochs {τ_{1}, τ_{2}, …} in continuous time.Repeat for each user l
1. Randomly pick
2. Keep sensing the change of
3. Let Δ be the difference between L(p, _{rl}r_{−l}, {α_{lm}}) and
4. Broadcast
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 10by10 m^{2} square area. The channel gains h_{lm} are equal to
Figure 10. Convergence performance of DSPC and EDSPC for multicast communications, where
Figure 11. Comparison of average performance (with confidence interval) of DSPC and EDSPC for multicast.
Conclusion
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 backpressure 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.
Endnotes
^{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.,
^{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
^{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 thresholdbased optimality condition.
^{i} Note that the feasible utility region
^{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.
Competing interests
The authors declare that they have no competing interests.
Acknowledgements
This study was supported in part by the DoD MURI Project FA95500910643 and the AFOSR grants FA955010C0026 and FA955011C0006.
References

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

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)

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)

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

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

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

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)

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

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

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

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

Y Xu, T LeNgoc, S Panigrahi, Global concave minimization for optimal spectrum balancing in multiuser DSL networks. IEEE Trans. Signal Process 56(7), 2875–2885 (2008)

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

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

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

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

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

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

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

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

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)

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

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

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

J Mo, J Walrand, Fair endtoend windowbased congestion control. IEEE/ACM Trans. Netw 8(5), 556–567 (2000). Publisher Full Text

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

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

X Lin, NB Shroff, R Srikant, On the connectionlevel stability of congestioncontrolled communication networks. IEEE Trans. Inf. Theory 54(5), 2317–2338 (2008)

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

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

R Loynes, The stability of a queue with noninterdependent interarrival and service times. Proc. Camb. Philos. Soc 58, 497–520 (1962). Publisher Full Text

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

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

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)