In single channel wireless networks, concurrent transmission at different links may interfere with each other. To improve system throughput, a scheduling algorithm is necessary to choose a subset of links at each time slot for data transmission. There are different network parameters which are affected by link scheduling algorithms such as throughput, delay, complexity and fairness. A throughput optimal algorithm, termed as maximum weight link scheduling (MWS) in such a wireless network is generally an NP-hard problem. We have investigated MWS and its approximation, Basic Randomized Algorithm (BRA), in terms of complexity and delay. We have developed a polynomial time algorithm for link scheduling problem provided that network conflict graph is line multigraph. It was shown that how the derived conditions can be satisfied by network designers through topology control of the network by prohibiting the construction of seven forbidden graphs in the conflict graph. We also study the relation between network topology and delay performance of the MWS algorithm by deriving two upper bound of delay which are related to topological parameters of the network. We also analyze and improve the delay performance of BRA. This algorithm is appropriate for distributed implementation. We first introduce a novel concept, the average hitting time, and analyze its impact on the upper bound of the average delay. It is then analytically shown that for two given randomized algorithms achieving the same throughput region, the one with a smaller average hitting time has a much less average delay bound. We also prove that by assigning traffic priorities in some specific applications, the achievable throughput region delivered by the BRA algorithm remains intact. This result is much valuable in the design of algorithms for some real-time applications by prioritizing the traffic to reduce the average delay of those applications. Simulation results confirm our analytical relations throughout the thesis. Keywords: Link Scheduling, Matching, Conflict Graph, Line Graph, Chromatic Number, Network Topology
