Due to the inherent complexity of the power-controlled scheduling problem, finding optimal schedules and power allocations for large-size networks will still consume extraordinary large amounts of time despite the performance of our method. We therefore propose an approximation algorithm, called the Guaranteed and Greedy Scheduling (GGS), which can find near optimal solutions within a short runtime. GGS is a polynomial time algorithm with a provable upper bound for the approximation ratio relative to the optimal solution. / For the distributed scheduling algorithm design, we focus on the CSMA (Carrier-Sense Multiple-Access) network, which is the most widely used distributed wireless network in practice. We establish a rigorous conceptual framework, upon which effective solutions to interference-safe transmissions can be constructed under the physical interference model. Specifically, we propose to use the concept of "safe carrier sensing range", which guarantees interference-safe transmissions under the physical interference model. We further propose a novel carrier-sensing mechanism, called Incremental-Power Carrier-Sensing (IPCS), which implements the safe carrier-sensing range concept in a simple way. Extensive simulation results show that IPCS can boost spatial reuse and network throughput by more than 60% relative to the conventional carrier-sensing mechanism. / This thesis studies the wireless link scheduling problem under the physical interference model. Such problem is more realistic than the widely studied wireless scheduling problem under the protocol interference model. However, it is a challenging problem because the physical interference model considers the cumulative effect of the interference powers from all the other concurrent transmitters. This thesis covers the complexity analysis and algorithm design (both centralized and distributed) for such a challenging problem. / We first give a rigorous NP-completeness proof for the power-controlled scheduling with consecutive transmission constraint under the physical interference model. We then present a centralized scheduling algorithm based on a column generation method which finds the optimal schedules and transmit powers. We further consider an integer constraint that requires the number of time slots allocated to a link to be an integer. Building upon the column generation method, we propose a branch-and-price method which can find the optimal integer solution. By simplifying the pricing problem and designing a new branching rule, we significantly improve the efficiency of both the column generation and the branch-and-price methods. For example, the average runtime is reduced by 99.86% in 18-link networks compared with the traditional column generation method. / Fu, Liqun. / Advisers: Soung Chang Liew; Jianwei Huang. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 133-144). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Furthermore, we show that geometric retransmission algorithm is intrinsically unstable for large population sizes. On the other hand, exponential backoff algorithm is more robust and scalable. Even for infinity population sizes, the stable throughput and bounded delay region still exists under certain conditions. / In the light of the concern, we propose a queueing model of the general CSMA protocol with probability-based backoff scheduling algorithm. The input buffer of each node is modeled as a Geo/G/1 queue, in which the service time distribution of each individual head-of-line (HOL) packet can be described by a Markov chain. By means of this queueing model, we can obtain the characteristic equation of throughput, the packet queueing delay as well as the stable conditions with admissible input traffic. We also specify stable throughput and bounded delay regions with respect to the retransmission factor and input rate. / Last but not least, the proposed queueing model can be systematically generalized to investigate various types of MAC protocols, such as ALOHA, CSMA protocols, IEEE 802.11 protocols. Specifically, we illustrate the methodology by full analyses of the non-persistent CSMA and 1-persistent CSMA protocols in this thesis. / Medium Access Control (MAC) protocols have been continuously updated to keep up with the emerging new services and QoS requirements. Despite of the rapid changes of MAC protocols, a comprehensive performance analysis of any MAC protocol remains an open issue for over several decades. / Most of existing analysis of MAC protocols focused on the network throughput and packet access delay under the assumption that the network is saturated which is not realistic. We know very little about the stability of MAC protocol under the normal network operation for lack of a systematic model that can be adaptively applied to various MAC protocols with different service requirements and backoff scheduling algorithms. / Other than the probability-based backoff algorithm, this thesis also includes the study of window-based backoff algorithm. It is shown that the probability-based and window-based backoff algorithms are equivalent to each other. Moreover, we find that the characteristic equation of network throughput is invariant to backoff scheduling algorithms. / Wong, Pui King. / Adviser: Tony T. Lee. / Source: Dissertation Abstracts International, Volume: 73-06, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 125-133). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.