WIRELESS LINK SCHEDULING UNDER PHYSICAL INTERFERENCE MODEL

Latency minimization and capacity maximization are fundamental combinatorial optimization problems in wireless networks. Given a set of communication links in a multihop wireless network, the former computes a schedule satisfying all link demands with shortest latency, while the latter aims at selecting a maximum feasible subset of these links. We study both the Shortest Link Schedule (SLS) and Maximum Independent Set of Links (MISL) from a theoretical perspective, striving for generalized algorithmic treatments and provable approximation guarantees. Wireless devices are prone to radio frequency interference emanating from other devices. Interference can be major inhibitor to transmission performance, degrading the signal quality or even causing the communication to fail. Several models have been used for modeling wireless interference over the past decades. In contrast to graph-based protocol models, which assume the interference end at some boundary, we consider a more realistic SINR-based physical interference model. Under physical interference model, the problem SLS and MISL are hard to solve due to the technical obstacles caused by the ambient noise, non-local and additive nature of interference. In this dissertation, we consider both fixed transmission powers and power control. We explore interference natures under physical interference model and propose a generalization of independent set, which is capable of modeling the independent sets of wireless links. In addition, we present constant-approximation algorithm for MISL with monotone and sub-linear power assignment in both unidirectional and bidirectional mode, and for MISL with sub-mean power assignment in bidirectional mode. We also present constant-approximation algorithm for Maximum Weighted Independent Set of Links (MWISL) with linear power assignment in both unidirectional and bidirectional mode. For MISL with power control in unidirectional mode, we develop a constant-approximation algorithm with the canonical iterative power assignment.Ph.D. in Computer Science, July 201