Limited wireless resources, such as spectrum and maximum power, give rise to various resource allocation problems that are interesting both from theoretical and application viewpoints. While the problems in some of the wireless networking applications are amenable to general resource allocation methods, others require a more specialized approach suited to their unique structural characteristics. We study both types of the problems in this thesis.
We start with a general problem of alpha-fair packing, namely, the problem of maximizing sum_j {w_j f_α(x_j)}, where w_j > 0, ∀j, and (i) f_α(x_j)=ln(x_j), if α = 1, (ii) f_α(x_j)= {x_j^(1-α)}/{1-α}, if α ≠ 1,α > 0, subject to positive linear constraints of the form Ax ≤ b, x ≥ 0, where A and b are non-negative. This problem has broad applications within and outside wireless networking. We present a distributed algorithm for general alpha that converges to an epsilon-approximate solution in time (number of distributed iterations) that has an inverse polynomial dependence on the approximation parameter epsilon and poly-logarithmic dependence on the problem size. This is the first distributed algorithm for weighted alpha-fair packing with poly-logarithmic convergence in the input size. We also obtain structural results that characterize alpha-fair allocations as the value of alpha is varied. These results deepen our understanding of fairness guarantees in alpha-fair packing allocations, and also provide insights into the behavior of alpha-fair allocations in the asymptotic cases when alpha tends to zero, one, and infinity.
With these general tools on hand, we consider an application in wireless networks where fairness is of paramount importance: rate allocation and routing in energy-harvesting networks. We discuss the importance of fairness in such networks and cases where our results on alpha-fair packing apply. We then turn our focus to rate allocation in energy harvesting networks with highly variable energy sources and that are used for applications such as monitoring and tracking. In such networks, it is essential to guarantee fairness over both the network nodes and the time slots and to be as fair as possible -- in particular, to require max-min fairness. We first develop an algorithm that obtains a max-min fair rate assignment for any routing that is specified at the input. Then, we consider the problem of determining a "good'' routing. We consider various routing types and either provide polynomial-time algorithms for finding such routings or prove that the problems are NP-hard. Our results reveal an interesting trade-off between the complexities of computation and implementation. The results can also be applied to other related fairness problems.
The second part of the thesis is devoted to the study of resource allocation problems that require a specialized approach. The problems we focus on arise in wireless networks employing full-duplex communication -- the simultaneous transmission and reception on the same frequency channel. Our primary goal is to understand the benefits and complexities tied to using this novel wireless technology through the study of resource (power, time, and channel) allocation problems. Towards that goal, we introduce a new realistic model of a compact (e.g., smartphone) full-duplex receiver and demonstrate its accuracy via measurements. First, we focus on the resource allocation problems with the objective of maximizing the sum of uplink and downlink rates, possibly over multiple orthogonal channels. For the single-channel case, we quantify the rate improvement as a function of the remaining self-interference and signal-to-noise ratios and provide structural results that characterize the sum of uplink and downlink rates on a full-duplex channel. Building on these results, we consider the multi-channel case and develop a polynomial time algorithm which is nearly optimal in practice under very mild restrictions. To reduce the running time, we develop an efficient nearly-optimal algorithm under the high SINR approximation.
Then, we study the achievable capacity regions of full-duplex links in the single- and multi-channel cases. We present analytical results that characterize the uplink and downlink capacity region and efficient algorithms for computing rate pairs at the region's boundary. We also provide near-optimal and heuristic algorithms that "convexify'' the capacity region when it is not convex. The convexified region corresponds to a combination of a few full-duplex rates (i.e., to time sharing between different operation modes). The analytical results provide insights into the properties of the full-duplex capacity region and are essential for future development of fair resource allocation and scheduling algorithms in Wi-Fi and cellular networks incorporating full-duplex.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/D85T3KP0 |
| Date | January 2016 |
| Creators | Marasevic, Jelena Rajko |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.0024 seconds