CTN Issue: August 2013

The rapid growth of wireless networks and the data access demands put in place have resulted in significant interest in designing highly optimized (cross-layer) resource allocation algorithms. A critical factor affecting the reliable end-to-end connectivity and quality-of-service for information exchange in wireless networks is the rapidly-changing network topology resulting from users’ mobility. Hence, distributed network control schemes and optimization algorithms with fast convergence speed are not only highly desirable but also critical for good wireless networks design.

However, thus far, standard distributed cross-layer approaches in the literature are based on first-order Lagrangian decomposition and the subgradient methods, which suffer from very slow convergence rates. Generally speaking, an optimization algorithm is called “first-order” if its search directions are based only on the first derivative information of the objective function and constraints (assuming that they are differentiable). In this paper, the authors develop a distributed Newton’s method, which is second-order (i.e., exploiting the second derivative information of the objective function and constraints) and enjoys a quadratic convergence rate.

Developing second-order distributed algorithms for the optimization of resource usage wireless networks is highly challenging, and results in this area remain elusive. Broadly speaking, in a distributed second-order algorithm, computing the primal and dual search directions (for updating the resource allocation in a wireless network) typically requires decomposing the inverses of the Hessian matrix (the matrix that contains all second derivatives of the objective function) and a weighted network Laplacian matrix (in spectral graph theory, Laplacian matrix is the quadratic form of the node-arc incidence matrix that represents the topology of the network graph) of the optimization problem, which would then be used to decentralize or localize decisions on flow control, routing, and time sharing by each node/link in the network. Unfortunately, the Hessian's structure in wireless networks is non-separable due to the inherent interference in wireless networks. What is worse is that the obtained inverses also have no sparsity structure in general. Hence, developing distributed algorithms for wireless networks are notoriously hard and have long been considered impossible.

However, in this paper, the authors show the surprising result that, by appropriately reformulating, rearranging, and exploiting special problem structures, it is indeed possible to decompose such computations into each node and each link of wireless communications networks. Based on these encouraging insights, the authors have successfully developed a series of new second-order techniques, which have led to a class of second-order distributed algorithms under a unifying framework. The most attractive feature of their proposed second-order distributed approach is that it requires almost the same order of information exchange as in the first-order subgradient method, while achieving the same quadratic rate of convergence as in centralized second-order methods. Collectively, their results serve as an important step towards the development of an analytical foundation for wireless networked systems design that provides second-order convergence speed.

This paper is a Best Paper Runner-Up for IEEE INFOCOM 2013.

Title and author(s) of the original paper in IEEE Xplore:
Title: Distributed Cross-Layer Optimization in Wireless Networks: A Second-Order Approach
Author: Jia Liu, Cathy H. Xia, Ness B. Shroff, and Hanif D. Sherali
This paper appears in: IEEE INFOCOM 2013
Issue Date: April 2013

Statements and opinions given in a work published by the IEEE or the IEEE Communications Society are the expressions of the author(s). Responsibility for the content of published articles rests upon the authors(s), not IEEE nor the IEEE Communications Society.