SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Recent advances in optimization techniques in wireless communication networks.

Open Access Research

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

Lei Yang1*, Yalin E Sagduyu2, Junshan Zhang1 and Jason H Li2

Author Affiliations

1 School of ECEE, Arizona State University, Tempe, AZ 85287, USA

2 Intelligent Automation, Inc., Rockville, MD 20855, USA

For all author emails, please log on.

EURASIP Journal on Wireless Communications and Networking 2012, 2012:231  doi:10.1186/1687-1499-2012-231


The electronic version of this article is the complete one and can be found online at: http://jwcn.eurasipjournals.com/content/2012/1/231


Received:15 February 2012
Accepted:4 July 2012
Published:24 July 2012

© 2012 Yang et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License ( http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

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.

Keywords:
Distributed power control; Nonconvex optimization; Extended duality theory; Simulated annealing; Queue stability; Unicast communications; Multicast communications

Introduction

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.

Power control for unicast communications

System model

We consider an ad hoc wireless network with a set <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M1">View MathML</a> 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 hlk the fixed channel gain between user l’s transmitter and user k’s receiver, and by pl the transmission power of link l with <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M2">View MathML</a> being its maximum power constraint. It follows that the received SINR for the lth user with a matched filter receiver is given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M3">View MathML</a>

(1)

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

thumbnailFigure 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 problemc:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M5">View MathML</a>

(2)

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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M6">View MathML</a>, where wl > 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M7">View MathML</a> denote the feasible utility region, where for each point U = (U1,…,UL) in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M8">View MathML</a>, there exists a power vector p such that Ul = Ul(γl(p)) for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M9">View MathML</a>. The feasible utility region <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M10">View MathML</a> is nonconvex, and in general, finding the globally optimal solution to (2) in <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M11">View MathML</a> is challenging. In the following example, we illustrate the geometry of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M12">View MathML</a> for the utility function <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M13">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M14">View MathML</a> for different system parameters. We compare the performance of the existing approaches [3,6,14,15] in Table 2.

thumbnailFigure 2. The feasible utility region<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M16','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M16">View MathML</a>. Case (I): the channel gains are given by h11 = 0.73, h12 = 0.04, h21 = 0.03, and h22 = 0.89, and the maximum power are <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M17">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M18">View MathML</a>; Case (II): the channel gains are given by h11 = 0.30, h12 = 0.50, h21 = 0.03, and h22 = 0.80, and the maximum power are <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M19">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M20">View MathML</a>. In both cases, the noise power is 0.1 for each link, and the weights are w1 = 0.57, w2 = 0.43.

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 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 optimalitye 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<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M21">View MathML</a>.

Proof

Let U denote a globally optimal solution to (2) over <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M22">View MathML</a>, and γ denote the corresponding SINR that supports U. Since Ul(·) is continuous and strictly increasing, proving that U is on the boundary of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M23">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M24">View MathML</a> such that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M25">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M26">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M27">View MathML</a> for some <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M28">View MathML</a>. Since Ul(·) for any <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M29">View MathML</a> is strictly increasing in γl, we have <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M30">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M31">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M32">View MathML</a> for some <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M33">View MathML</a>, 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M34">View MathML</a>, 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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M35">View MathML</a>

(3)

Proof

Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M36">View MathML</a> denote the total utility. Since Ul(·) is nonnegative, we define xl∈[0, 1] as a ratio for the contribution of user l’s utility to t. Therefore, Ul(γl(p)) = txl and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M37','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M37">View MathML</a>. Then (2) can be rewritten as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M38','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M38">View MathML</a>

(4)

In order to maximize t, it suffices then to relax <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M39">View MathML</a> in (4) as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M40">View MathML</a>, which is equivalent to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M41">View MathML</a>. 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M42">View MathML</a>, as illustrated in Figure 3. Intuitively speaking, x represents a search direction. Once we find the best search direction xp 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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M43','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M43">View MathML</a>

(5)

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.

thumbnailFigure 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M44">View MathML</a> into many small simplices, the algorithm can find the optimal point on the boundary of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M45">View MathML</a>. 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.

thumbnailFigure 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M46">View MathML</a> with the vertex set V = {v1,…,vL}, where vl = el and el is the lth unit coordinate vector. Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M47">View MathML</a> be the center of S. Compute p by solving (5) at the point x = vc. Denote <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M48">View MathML</a> as the diameter of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M49">View MathML</a>.

Repeat

1. Divide each simplex <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M50">View MathML</a> by using bisection method, which chooses the midpoint of one of the longest edges of the simplex <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M51','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M51">View MathML</a>, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M52','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M52">View MathML</a>, where vr and vs are the end points of a longest edge of the simplex. In this case, the simplex <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M53">View MathML</a> is subdivided into two simplices <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M54">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M55">View MathML</a>.

2. For each new simplex <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M56">View MathML</a>, compute the diameter <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M57">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M58">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M59">View MathML</a>, 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M60">View MathML</a> and rewrite (3) as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M61">View MathML</a>

(6)

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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M62">View MathML</a>

(7)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M63">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M64">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M65">View MathML</a> are the penalty multipliers for penalizing the constraint violations. Based on EDT [17], there exist finite α ≥ 0 and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M66">View MathML</a>, for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M67">View MathML</a>, such that, for any α > α and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M68">View MathML</a><a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M69','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M69">View MathML</a>, the solution to (7) is the same as (6). Note that (7) does not include the constraints of pl, xl, and tl 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 tl, xl, and pl denote the primal values of the lth user, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M70">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M71">View MathML</a> denote the new values randomly chosen by the lth user. Accordingly, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M72">View MathML</a> can be treated as a new target utility for the lth user. To achieve this target utility, the lth user updates <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M73','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M73">View MathML</a> by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M74">View MathML</a>

(8)

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 pl at a faster time-scale than tl and xl such that pl always converges before the next update of tl and xl. Next, we use SA to update tl and xl 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(pl, xl, tl|pl, xl, tl, α, β) and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M75">View MathML</a>, where yl is the vector y without the lth user’s variable. If Δ ≥ 0, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M76">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M77">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M78">View MathML</a> reduce Lagrangian (7), then they are accepted with probability 1; otherwise, they are accepted with probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M79','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M79">View MathML</a>, 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 tl, xl and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M80">View MathML</a>, whenever any of these terms changes.

Note that the target utility tlxl 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M81','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M81">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M82','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M82">View MathML</a>. Therefore, each user l also needs to update α and βl. In particular, if any constraint is violated, α and βl are updated as follows:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M83">View MathML</a>

(9)

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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M84">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M85','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M85">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M86">View MathML</a>. Note that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M87','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M87">View MathML</a> can be computed by each user locally. Further, we assume that each user broadcasts <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M88">View MathML</a> before running the algorithm so that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M89">View MathML</a> 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 {τ1, τ2,…} to update tl and xl, which can be determined and informed to each user offline.

Algorithm 2 DSPC

Initialization: Choose ε > 0. Let α = 0, βl = 0, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M90">View MathML</a>, and randomly choose p, x and t.

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

Repeat for each user l

1. Randomly pick <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M91">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M92">View MathML</a>, and update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M93">View MathML</a> according to (8).

2. Keep sensing the change of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M94">View MathML</a> broadcast by other users.

3. Compute Δ, and accept <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M95">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M96">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M97">View MathML</a> with probability 1, if Δ≥0, or with probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M98">View MathML</a>, otherwise.

4. Broadcast <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M99">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M100">View MathML</a>, if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M101">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M102">View MathML</a> are updated.

5. For each time epoch τi, update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M103">View MathML</a>.

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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M104">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M105','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M105">View MathML</a>, 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M106">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M107','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M107">View MathML</a>[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 tl and xl, 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 near-optimal solutions. Based on EDT, we choose <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M108','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M108">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M109','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M109">View MathML</a>, to satisfy the optimality conditions for penalty variables. Obviously, by choosing large α0 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M110','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M110">View MathML</a> for the constraint tlxl ≤ Ul(γl(p)).

Algorithm 3 EDSPC

Initialization: Choose ε > 0. Let α = α0, βl = β0l, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M111','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M111">View MathML</a>, and randomly choose p, x and t.Set T = T0, and select a sequence of time epochs {τ1, τ2,…} in continuous time.

Repeat for each userl

1. Randomly pick <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M112">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M113">View MathML</a>, and update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M114','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M114">View MathML</a> according to (8).

2. Keep sensing the change of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M115">View MathML</a> broadcast by other users.

3. Compute Δ, and accept <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M116','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M116">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M117','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M117">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M118">View MathML</a> with probability 1, if Δ ≥ 0, or with probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M119">View MathML</a>, otherwise.

4. Broadcast <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M120">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M121">View MathML</a>, if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M122">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M123">View MathML</a> 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 (DSPCh and EDSPC). We consider a wireless network with six links randomly distributed on a 10-by-10 m2 square area. The channel gains hlk are equal to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M124','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M124">View MathML</a>, where dlk represents the distance between the transmitter of user l and the receiver of user k. We assume <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M125">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M126">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M127">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M128">View MathML</a>, and consider one randomly generated realization of channel gains given by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M129">View MathML</a>

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.

thumbnailFigure 5. Convergence performance of DSPC, EDSPC, SEER, and ADP.

thumbnailFigure 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 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M130">View MathML</a>, which are i.i.d. sequences of random variables for all l = 1,…,L and s = 1,…,S, where Asl(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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M131">View MathML</a> are finite. Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M132">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M133">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M134">View MathML</a> evolves over time as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M135">View MathML</a>

(10)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M136">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M137">View MathML</a> forms a Markov chain.

Let ψs denote the first moment of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M138">View MathML</a>, 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 all<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M139">View MathML</a>for which there exists some feasible power allocation policy under which the system is stable, i.e.,<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M140">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M141">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M142">View MathML</a>denotes the set of feasible power allocation, rl(p) denotes the rate of link l under power allocationp, and Esl = 1 is the indicator that the path of users of class s uses link l, and Esl = 0, otherwise.

For the sake of comparison, the throughput regioni<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M143">View MathML</a> of the corresponding saturated case is defined as the set of all feasible link rates, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M144">View MathML</a>. In general, the throughput region <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M145">View MathML</a> 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<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M146">View MathML</a>, when the traffic load<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M147">View MathML</a>is strictly interior to the stability region ∧, i.e., there exists some ε > 0 such that <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M148">View MathML</a>.

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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M149">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M150">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M151">View MathML</a>, where the difference of queue lengths of class s is <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M152">View MathML</a>, if the receiver of link l is not the destination of class s’s traffic, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M153">View MathML</a>, otherwise.

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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M154">View MathML</a>

(11)

Thus, the transmission rate of link l in slot t is given by <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M155">View MathML</a>.

Stage 3: Let <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M156">View MathML</a> denote the class scheduled in slot t; if multiple classes satisfy this condition, then <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M157">View MathML</a>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 = {Esl} is the identity matrix) with two users (classes), where the channel gains are h11 = 0.3, h12 = 0.5, h21 = 0.03, and h22 = 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M158">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M159">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M160">View MathML</a>, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M161">View MathML</a>, achievable by timesharing across different transmission modes.j

thumbnailFigure 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.

thumbnailFigure 8. Comparison of sample paths of a user’s queue length for different traffic loads.

thumbnailFigure 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M162">View MathML</a> of receivers. The corresponding transmission rate, rl, is determined by the bottleneck link among these transmitter–receiver pairs, i.e., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M163">View MathML</a>, where rlm denotes the link rate between the transmitter of user l and its receiver m, and it is calculated from the Shannon rate <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M164">View MathML</a> 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:

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M165">View MathML</a>

(12)

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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M166','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M166">View MathML</a> in (12) as <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M167','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M167">View MathML</a>, in order to devise distributed algorithms solving (12). Thus, (12) can be rewritten as

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M168','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M168">View MathML</a>

(13)

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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M169','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M169">View MathML</a>

(14)

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

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M170','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M170">View MathML</a>

(15)

where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M171','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M171">View MathML</a> are the penalty multipliers. From EDT, there exist finite <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M172','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M172">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M173">View MathML</a> such that, for any <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M174">View MathML</a><a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M175','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M175">View MathML</a>, the solution to (15) is the same as (14) [17]. Note that (15) does not include the constraint of pl 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 rl and pl denote the primal values of the lth user, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M176','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M176">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M177">View MathML</a> by

<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M178">View MathML</a>

(16)

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 rl 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M179">View MathML</a>, where <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M180">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M181">View MathML</a> 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, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M182">View MathML</a> and randomly choose rand p.

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

Repeat for each user l

1. Randomly pick <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M183">View MathML</a>, and update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M184">View MathML</a> according to (16).

2. Keep sensing the change of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M185">View MathML</a> broadcast by other users.

3. Let Δ be the difference between L(p, rl|rl, {αlm}) and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M186">View MathML</a>, and accept <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M187">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M188','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M188">View MathML</a> with probability 1, if Δ ≥ 0, or with probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M189">View MathML</a>, otherwise.

4. Broadcast <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M190">View MathML</a>, if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M191">View MathML</a> is accepted.

5. For each time epoch τi, update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M192">View MathML</a>.

Until T < ε.

Step 2: update penalty variables

For each user l,

1. Update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M193">View MathML</a>, 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M194">View MathML</a>, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M195','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M195">View MathML</a> and randomly choose r and p.

Set T = T0, and select a sequence of time epochs {τ1, τ2, …} in continuous time.Repeat for each user l

1. Randomly pick <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M196','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M196">View MathML</a>, and update <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M197','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M197">View MathML</a> according to (16).

2. Keep sensing the change of <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M198','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M198">View MathML</a> broadcast by other users.

3. Let Δ be the difference between L(p, rl|rl, {αlm}) and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M199','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M199">View MathML</a>, and accept <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M200','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M200">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M201','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M201">View MathML</a> with probability 1, if Δ ≥ 0, or with probability <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M202','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M202">View MathML</a>, otherwise.

4. Broadcast <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M203','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M203">View MathML</a>, if <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M204','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M204">View MathML</a> 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 m2 square area. The channel gains hlm are equal to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M205','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M205">View MathML</a>, where dlm represents the distance between the transmitter l and the receiver m. The channel gains hlm are equal to <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M206','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M206">View MathML</a>, where dlmrepresents the distance between the transmitter l and the receiver m. We assume Ul(rl) = rl, <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M207','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M207">View MathML</a>, and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M208','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M208">View MathML</a> for all <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M209','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M209">View MathML</a> and <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M210','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M210">View MathML</a>. 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.

thumbnailFigure 10. Convergence performance of DSPC and EDSPC for multicast communications, where<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M213','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M213">View MathML</a>,<a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M214','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M214">View MathML</a>.

thumbnailFigure 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 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.

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., <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M215','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M215">View MathML</a>) 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 Ul(·), (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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M216','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M216">View MathML</a> is quasi-convex, if its domain dom f and all its sublevel sets <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M217','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M217">View MathML</a>, for <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M218','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M218">View MathML</a>, 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.

i Note that the feasible utility region <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M219','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M219">View MathML</a> 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 <a onClick="popup('http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M220','MathML',630,470);return false;" target="_blank" href="http://jwcn.eurasipjournals.com/content/2012/1/231/mathml/M220">View MathML</a>.

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 FA9550-09-1-0643 and the AFOSR grants FA9550-10-C-0026 and FA9550-11-C-0006.

References

  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) OpenURL

  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 OpenURL

  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 OpenURL

  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 OpenURL

  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) OpenURL

  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 OpenURL

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

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

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

  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 OpenURL

  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) OpenURL

  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 OpenURL

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

  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 OpenURL

  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 OpenURL

  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 OpenURL

  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 OpenURL

  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) OpenURL