|
Research /
Optimal wireless communication and networkingIn their classical work on limit distributions Gnedenko and Kolmogorov wrote that the "epistemological value of the theory of probability is based on this: that large-scale random phenomena in their collective action create strict, nonrandom regularity." In simpler words, randomness generates structure. It is often possible to infer properties of large-scale stochastic systems even if analogous deterministic counterparts are intractable. Randomness, in the form of fading -- random variations in propagation coefficients between network nodes --, is inherent in wireless networks. My technical approach to the optimal design of wireless systems is to explore the structure introduced by fading so as to understand their fundamental properties. An example of the desired outcomes are recent results concerning the optimality of separating wireless networking problems in layers and per-fading state subproblems.  Figure 1. Wired network. In wired networks communication is possible between nodes sharing a physical connection. The goal of the communication network is to administer link resources to support information flows with some required level of service. To explain these results consider a communication network deployed to support information flows with some required level of service. The goal of the communication network is to administer given resources to sustain said flows. In conventional wired networks the resource given is a set of physical connections between nodes; see Fig. 1. Supporting information flows requires finding routes between source and destination, determining link sharing strategies, and controlling the amount of traffic injected into the network. It was an early design specification to separate these problems in layers -- routing, link and transport for the problems in the previous sentence -- that operate more or less independently, and interact through standardized interfaces. While this was mostly a matter of ensuring inter-operability it is remarkable that this separation can be optimal. Specifically, it is possible to define separate per-layer optimization problems whose outcome coincides with the solution of a joint non-layered optimization. Mathematically, separability comes from the fact that the wired networking problem is convex -- a linear program in fact. The Lagrangian dual problem can thus be solved instead. As it often happens, the Lagrangian exhibits a separable structure, which, as it turns out coincides with the conventional layers. In a wireless network the given resources are not connections but bandwidth and power; see Fig. 2. Therefore, on top of routes, link shares, and rate control, a wireless networking problem entails determining which connections, among those possible for the given bandwidth and power, should be established to support the required level of service. Earlier approaches to wireless networking migrated the conventional layers and defined the power and frequency assignment as physical layer subproblems. This yields poor results though, and over time lead to the surge of cross-layer design as synonym of joint optimization across layers. Ultimately, the poor performance of layered wireless networks stems from the non-convexity of the joint cross-layer networking problem. As in wired networks, the Lagrangian exhibits a separable structure that can be mapped to layers. But non-convex problems have positive duality gap explaining the poor results of layered wireless networks.  Figure 2. Wireless networks. In wireless networks (middle and bottom) links are established by a resource allocation decision to spend power and bandwidth on a specific connection for a specific fading state. Links can be different at different times and have time varying capacities. In what constitutes an interesting example of structure introduced by randomness, we have proven that general wireless networking problems in the presence of fading, while non-convex, have zero Lagrangian duality gap. Exploiting the separability of the Lagrangian, this result yields the following principles: First separation principle. This principle pertains to the separability of wireless networking problems into layers. It states that it is possible to define separate optimization problems to obtain optimal routes, optimal link capacity allocations, and optimal power/frequency assignments. Second separation principle. Another difficulty in optimal wireless networking is the need to optimize jointly for all fading states. Given that fading coefficients take on a continuum of values, this is a variational problem that requires finding optimal functions of the fading coefficients. This principle states that network optimization is further separable in per-fading-state subproblems. The practical importance of this result is that it is not necessary to find optimal functions but only the values of the functions for those channels actually observed. The separation principles hold under specific assumptions, e.g., networks operating in an ergodic setting and availability of perfect channel state information that restrict applicability of the separation principles to particular settings. Part of the research undertaken in the context of this project is to study the extent to which these assumptions can be lifted and what implications follow when this is not possible. Nonetheless, it has to be recognized that they do establish a fundamental property of wireless networks in the presence of fading that is not true for networks in a deterministic setting. Our current research agenda utilizes the separation principles as motivation for part of the proposed research and as an example of the types of result that can be expected from the combination of optimization techniques and stochastic structure. Specific research activities include the construction of a generic framework to reduce the complexity of finding optimal operating points for wireless systems and the development of stochastic optimization algorithms to operate in environments where channel probability distributions are not known. We also apply this framework to the solution of specific problems in optimal wireless communications and networking. Of particular notice is the work on cognitive access algorithms and protocols. This is an effort to understand optimal wireless networking when terminals have different beliefs about the global state of the network. Optimal wireless system design: Dual functions, duality gap, and separabilityOperating variables of a wireless system can be separated in two types. Resource allocation variables $\mathbf{p}(\mathbf{h})$ determine instantaneous allocation of resources like frequencies and transmitted powers as a function of the fading coefficient $\mathbf{h}$. Average variables $\mathbf{x}$ capture system's performance over a large period of time and are related to instantaneous resource allocations via ergodic averages. A generic representation of the relationship between instantaneous and average variables is $\qquad\qquad\qquad \mathbf{x}\leq\mathbf{E}\left[\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)\right], $ where $\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)$ is a vector function that maps channel $\mathbf{h}$ and resource allocation $\mathbf{p}(\mathbf{h})$ to instantaneous performance $\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)$. The system's design goal is to select resource allocations $\mathbf{p}(\mathbf{h})$ to maximize ergodic variables $\mathbf{x}$ in some sense. An example of a relationship having the form in the equation above is a code division multiple access channel in which case $\mathbf{h}$ denotes the vector of channel coefficients, $\mathbf{p}(\mathbf{h})$ the instantaneous transmitted power, $\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)$ the instantaneous communication rate determined by the signal to interference plus noise ratio, and $\mathbf{x}$ the ergodic rates determined by the expectation of the instantaneous rates. The design goal is to allocate instantaneous power $\mathbf{p}(\mathbf{h})$ subject to a power constraint so as to maximize a utility of the ergodic rate vector $\mathbf{x}$. This interplay of instantaneous actions to optimize long term performance is pervasive in wireless systems. A brief list of examples includes optimization of orthogonal frequency division multiplexing, cognitive radio, random access, communication with imperfect channel state information, and various flavors of wireless network optimization.  Figure 3. Power allocations in a wireless network using adaptive modulation and coding over an interference limited physical layer. Optimal power distribution consists of transitions between AMC modes and within each mode a cloud of allocations roughly proportional to the inverse channel. In many cases of interest the functions $\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)$ are nonconcave and as a consequence finding the resource allocation distribution $\mathbf{p}^*(\mathbf{h})$ that maximizes $\mathbf{x}$ requires solution of a nonconvex optimization problem. This is further complicated by the fact that since fading channels $\mathbf{h}$ take on a continuum of values there is an infinite number of $\mathbf{p}^*(\mathbf{h})$ variables to be determined. A simple escape to this problem is to allow for time sharing in order to make the range of $\mathbf{E}\left[{\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)\right]$ convex and permit solution in the dual domain without loss of optimality. While the nonconcave function $\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)$ still complicates matters, working in the dual domain makes solution, if not necessarily simple, at least substantially simpler. However, time sharing is not easy to implement in fading channels. At the heart of this research endeavor there is a general methodology that can be used to solve optimal resource allocation problems in wireless communications and networking without resorting to time sharing. The fundamental observation is that the range of the expectation $\mathbf{E}\left[\mathbf{f}_1\big(\mathbf{h},\mathbf{p}(\mathbf{h})\big)\right]$ is convex if the probability distribution of the channel $\mathbf{h}$ contains no points of positive probability. This observation can be leveraged to show lack of duality gap of general optimal resource allocation problems making primal and dual problems equivalent. The dual problem is simpler to solve and its solution can be used to recover primal variables with reduced computational complexity due to the inherently separable structure of the problem Lagrangians. The separation principles outlined above are a direct consequence of these observations but these properties can also be used to develop specific algorithms and protocols for optimal wireless communication and networking. An example of that is the ergodic stochastic optimization algorithm that we explain next. Ergodic stochastic optimization algorithmsWireless link capacities are expressed as expected values over fading channel realizations. Their evaluation, therefore, requires access to the channel probability distribution function (pdf). Assuming a particular fading model the channel pdf is acquired by estimating channel moments; e.g., for Raleigh fading estimating mean channels is sufficient. While this is a possible approach it does restrict practical applicability as fading models are only rough approximations of distributions observed in field deployments. To overcome this limitation we developed the ergodic stochastic optimization algorithm that learns channel distributions simultaneously with the determination of optimal operating points.  Figure 4. Optimal routes to node 7. Circles' areas are proportional to the amount of traffic terminals handle on behalf of terminal 7. Line widths are proportional to the packets routed through that link. Links of lower average quality are exploited, e.g., nodes 4 and 11 deliver information directly to node 7 bypassing the better quality links to nodes 5 and 9. These algorithms are obtained through the implementation of stochastic subgradient descent in the dual domain and have been shown to exhibit almost sure convergence to optimal operating points in an ergodic sense. The ergodic stochastic optimization algorithm is implemented to find optimal operating variables for the network in Fig. 2 using adaptive modulation and coding over an interference limited physical layer. Nodes operate on 5 frequency bands, using direct sequence spread spectrum in each of them with spreading gain $S=16$. Three AMC modes corresponding to capacities 1, 2 and 3 bits/s/Hz are used with transitions at SINR 1, 3 and 7. Fading channels are generated as i.i.d. Rayleigh with average powers $1/2$ for the links $4\leftrightarrow7$, $5\leftrightarrow9$, $7\leftrightarrow11$, $9\leftrightarrow10$, $11\leftrightarrow8$, $10\leftrightarrow6$, $8\leftrightarrow4$ and $6\leftrightarrow5$ and 1 for the remaining links. Noise power is $N_{i}^{f}=0.1$ for all terminals and frequency bands. The maximum average power consumption per terminal is $p_{\max}=2$ -- chosen so that if a terminal with 4 neighbors spreads power uniformly across all neighbors and frequencies the signal to noise ratio is 0dB. Powers $p_{i}$ are also constrained to be positive, i.e., $p_{\min}=0$. Link capacities and routing variables are constrained by $c_{\min}=r_{\min}=0$ bits/s/Hz and $c_{\max}=r_{\max} = 6$ bits/s/Hz. Four flows with destination at terminals 1, 7, 8 and 14 are considered with all other terminals required to deliver at least $a_{\min}=0.5$ bits/s/Hz and at most $a_{\max}=2$ bits/s/Hz to each of these flows. Beyond that, the optimality criteria is sum rate maximization. Simulation results are presented in Figs. 3, 4, and 5.  Figure 5. Optimal link capacities. The width of the link is proportional to the capacity of the link. For each pair of terminals $i<j$ the capacity $c_{ij}$ between the smaller index $i$ and the larger index $j$ is shown first (in blue) and the capacity $c_{ji}$ second (in red). Links to nodes 1, 7, 8 and 14 have the largest capacities as it should be of flows' destinations. Notice how some links, e.g. 11 to 9, despite having good average values are assigned small powers, thus having small capacity. Power allocation for the link from terminal 1 to terminal 4 is shown in Fig. 3. Optimal power distribution consists of transitions between AMC modes and within each mode a cloud of allocations roughly proportional to the inverse channel. Routes to terminal 7 are sketched in Fig. 4. The circles' area is proportional to the amount of traffic that each terminal handles on behalf of the flow with destination at terminal 7. It is apparent that packets are indeed being delivered to the destination. It is also worth noting that links of lower average quality are exploited. E.g., nodes 4 and 11 deliver information directly to node 7 bypassing the better quality links to nodes 5 and 9. Ergodic link capacities are shown in Fig. 5. The width of the link is proportional to the capacity of the link. For each pair of terminals $i<j$ the capacity $c_{ij}$ between the smaller index $i$ and the larger index $j$ is shown first (in blue) and the capacity $c_{ji}$ second (in red). Links to nodes 1, 7, 8 and 14 have the largest capacities as it should be of flows' destinations. Also notice how some links, e.g. 11 to 9, despite having good average values are assigned small powers, thus having small capacity. This is a consequence of the joint -- albeit separable -- optimization of routes, link capacities and power allocations. Acknowledgments and referencesI started working on this project my last year at the University of Minnesota. Sincere thanks are therefore due to Prof. Georgios Giannakis. I also had the privilege of counting on the collaboration of Dr. Nikolaos Gatsis. After moving to the University of Pennsylvania this project morphed and expanded into the Ph. D. work of Yichuan Hu. The list of journal papers published in the context of this project is the following:
The separation principles were introduced in [6] and the ergodic stochastic optimization algorithm in [5]. Both of these topics are covered in the tutorial paper [3], which is the best starting point to understand this project. This project is also the basis of my CAREER award. Paper [7] deals with how to solve optimal resource allocation problems in networks with interference limited physical layers. Papers [1], [2], and [4] are the work of Yichuan Hu on understanding optimal wireless networking when terminals have different beliefs about the global state of the network. |