Network utility maximization is often applied for the cross-layer design of wireless networks considering known wireless channels. However, realistic wireless channel capacities are stochastic bearing time-varying statistics, necessitating the redesign and solution of NUM problems to capture such effects. Based on NUM theory we develop a framework for scheduling, routing, congestion control and power control in wireless multihop networks that considers stochastic long or short term fading wireless channels. Specifically, the wireless channel is modeled via stochastic differential equations alleviating several assumptions that exist in state-of-the-art channel modeling within the NUM framework such as the finite number of states or the stationarity. Our consideration of wireless channel modeling leads to a NUM problem formulation that accommodates non-convex and time-varying utilities. We consider both cases of non orthogonal and orthogonal access of users to the medium. In the first case, scheduling is performed via power control, while the latter separates scheduling and power control and the role of power control is to further increase users' optimal utility by exploiting random reductions of the stochastic channel power loss while also considering energy efficiency. Finally, numerical results evaluate the performance and operation of the proposed approach and study the impact of several involved parameters on convergence.
This paper considers jointly optimal design of crosslayer congestion control, routing and scheduling for ad hoc wireless networks. We first formulate the rate constraint and scheduling constraint using multicommodity flow variables, and formulate resource allocation in networks with fixed wireless channels (or single-rate wireless devices that can mask channel variations) as a utility maximization problem with these constraints. By dual decomposition, the resource allocation problem naturally decomposes into three subproblems: congestion control, routing and scheduling that interact through congestion price. The global convergence property of this algorithm is proved. We next extend the dual algorithm to handle networks with timevarying channels and adaptive multi-rate devices. The stability of the resulting system is established, and its performance is characterized with respect to an ideal reference system which has the best feasible rate region at link layer. We then generalize the aforementioned results to a general model of queueing network served by a set of interdependent parallel servers with time-varying service capabilities, which models many design problems in communication networks. We show that for a general convex optimization problem where a subset of variables lie in a polytope and the rest in a convex set, the dual-based algorithm remains stable and optimal when the constraint set is modulated by an irreducible finite-state Markov chain. This paper thus presents a step toward a systematic way to carry out cross-layer design in the framework of “layering as optimization decomposition” for time-varying channel models. Distributed network utility maximization (NUM) has received an increasing intensity of interest over the past few years. Distributed solutions (e.g., the primal-dual gradient method) have been intensively investigated under fading channels. As such distributed solutions involve iterative updating and explicit message passing, it is unrealistic to assume that the wireless channel remains unchanged during the iterations. Unfortunately, the behavior of those distributed solutions under time-varying channels is in general unknown. In this paper, we shall investigate the convergence behavior and tracking errors of the iterative primal-dual scaled gradient algorithm (PDSGA) with dynamic scaling matrices (DSC) for solving distributive NUM problems under time-varying fading channels. We shall also study a specific application example, namely the multicommodity flow control and multicarrier power allocation problem in multihop ad hoc networks. Our analysis shows that the PDSGA converges to a limit region rather than a single point under the finite state Markov chain (FSMC) fading channels. We also show that the order of growth of the tracking errors is given by O(T N), where T and N are the update interval and the average sojourn time of the FSMC, respectively. Based on this analysis, we derive a low complexity distributive adaptation algorithm for determining the adaptive scaling matrices, which can be implemented distributively at each transmitter. The numerical results show the superior performance of the proposed dynamic scaling matrix algorithm over several baseline schemes, such as the regular primal-dual gradient algorithm.  There has been considerable work developing a stochastic network utility maximization framework using Backpressure algorithms, also known as MaxWeight. A key open problem has been the development of utility-optimal algorithms that are also delay-efficient. In this paper, we show that the Backpressure algorithm, when combined with the last-in-first-out (LIFO) queueing discipline (called LIFO-Backpressure), is able to achieve a utility that is within O(1 V) of the optimal value, for any scalar V ≥ 1, while maintaining an average delay of O([log(V)]2) for all but a tiny fraction of the network traffic. This result holds for a general class of problems with Markovian dynamics. Remarkably, the performance of LIFO-Backpressure can be achieved by simply changing the queueing discipline; it requires no other modifications of the original Backpressure algorithm. We validate the results through empirical measurements from a sensor network testbed, which show a good match between theory and practice. Because some packets may stay in the queues for a very long time under LIFO-Backpressure, we further develop the LIFOp-Backpressure algorithm, which generalizes LIFOp-Backpressure by allowing interleaving between first-in-first-out (FIFO) and LIFO. We show that LIFOp Backpressure also achieves the same O(1 V) close-to-optimal utility performance and guarantees an average delay of O([log(V)]2) for the packets that are served during the LIFO period.