Non-convex Power Control and Scheduling in Wireless Ad hoc Networks

Due to the broadcast nature of wireless medium, simultaneous transmissions interfere with each other (especially transmissions on nearby links), thus adversely affecting data rates and Quality of Service (QoS) in the system. Interference mitigation is therefore a fundamental issue that must be addressed in next generation wireless networks. An important technique for this is to control the links' transmission power. Driven by the wide spread of broadband wireless data services, a system-wide efficiency metric (i.e., system utility) is typically used to characterize the advantage of power control.;Maximizing a system-wide utility through power control is an NP-hard problem in general due to the complicated coupling interference between links. Thus, it is difficult to solve despite its paramount importance. The first goal of this thesis is to find global optimal power allocations to a variety of system utility maximization (SUM) problems based on the recent advances in monotonic optimization. Instead of tackling the non-convexity issue head on, we bypass non-convexity by exploiting the monotonic nature of the power control problem. In particular, we establish a monotonic optimization framework to maximize a system utility through power control in single-carrier or multi-carrier wireless networks. Furthermore, MAPEL and M-MAPEL are respectively proposed to obtain the global optimal power allocation efficiently in single-carrier or multi-carrier wireless networks. The main benefit of MAPEL and M-MAPEL is to provide an important benchmark for performance evaluation of other heuristic algorithms targeting the same problem. With the help of MAPEL or M-MAPEL, we evaluate the performance of several existing algorithms through extensive simulations. On the other hand, by tuning the approximation factor in MAPEL and M-MAPEL, we could engineer a desirable tradeoff between optimality and convergence time.;In interference-limited wireless networks where simultaneous transmissions on nearby links heavily interfere with each other, however, power control alone is not sufficient to eliminate strong levels of interference between close-by links. In this case, scheduling, which allows close-by links to take turns to be active, plays a crucial role for achieving high system performance. Joint power control and scheduling that maximizes the system utility has long been a challenging problem. The complicated coupling between the signal-to-interference ratio of concurrently active links as well as the flexibility to vary power allocation over time gives rise to a series of non-convex optimization problems, for which the global optimal solution is hard to obtain. The second goal of this thesis is to solve the non-convex joint power control and scheduling problems efficiently in a global optimal manner. In particular, it is the monotonicity rather than the convexity of the problem that we exploit to devise an efficient algorithm, referred to as S-MAPEL, to obtain the global optimal solution. To further reduce the complexity, we propose an accelerated algorithm, referred to as A-S-MAPEL, based on the inherent symmetry of the optimal solution. The optimal joint-power-control-and-scheduling solution obtained by the proposed algorithms serves as a useful benchmark for evaluating other existing schemes. With the help of this benchmark, we find that on-off scheduling is of much practical value in terms of system utility maximization if "off-the-shelf' wireless devices are to be used.;With the proliferation of wireless infrastructureless networks such as ad hoc and sensor networks, it is increasingly crucial to devise an algorithm that solves the power control problem in a distributed fashion. In general, distributed power control is more complicated due to the lack of centralized infrastructure. As the third goal of this thesis, we consider a distributed power control algorithm for infrastructureless ad hoc wireless networks, where each link distributively and asynchronously updates its transmission power with limited message passing among links. This algorithm provably converges to the optimal strategy that picks global optimal solutions with probability 1 despite the non-convexity of the power control problem. In contrast with existing distributed power control algorithms, our algorithm makes no stringent assumptions on the system utility functions. In particular, the utility function is allowed to be concave or non-concave, differentiable or non-differentiable, continuous or discontinuous, and monotonic or non-monotonic.