Ardışık enterferans silme özellikli kablosuz ağlarda çizelgenin optimize edilmesi

Scheduling in wireless networks determines the sets of transmitter-receiver pairs, i.e. links, to be activated at any given time. The interference model used in the simultaneous link activation speci es both the design and performance of the scheduling algorithm. Interference avoidance model that allows a receiver to only decode one transmission at a time by considering all other transmissions as interference has been widely used in link scheduling algorithms. When the neighboring transmissions overlap in time, collision occurs and reception is not successful. The scheduling algorithms avoiding such overlaps in time and space however limits the capacity of wireless networks. Interference cancellation model aims to solve this problem by allowing multiple transmissions in the same neighborhood at a time through the decomposition of all the signals in a composite signal at the receivers. Among many interference cancellation techniques, Successive Interference Cancellation (SIC) appears to be the most promising due to its simplicity, overall system robustness and existing prototypes. SIC is based on decoding and subtracting the signals successively from the composite received signal starting with the strongest signal. In this thesis, we study the optimal scheduling problem for minimizing the length of the schedule required to satisfy the tra c demands of the links in single-hop variable rate multiple access wireless networks and multi-hop xed rate wireless networks using SIC. The scheduling problems for both networks are proven to be NP-hard. In single-hop multiple access wireless networks, we propose a novel centralized algorithm based on Column Generation Method. This algorithm is based on decomposing the original problem into Restricted Master Problem (RMP) and Pricing Problem (PP), and approximating the exponentially complex PP by a greedy heuristic algorithm. In multi-hop wireless networks, we rst propose a novel centralized algorithm that includes the feasible links in the scheduled link set one by one in the increasing order of a novel metric called Interference E ect (IE). IE number of a link is de ned as the total Signal-to-Interference-plus-Noise Ratio (SINR) drop of scheduled links if the link is scheduled to the time slot. We then propose a novel distributed algorithm that extends the Request-to-Send (RTS)/Clear-to-Send (CTS) mechanism of Carrier Sense Multiple Access (CSMA) protocol to enable further transmissions exploiting SIC. We demonstrate via simulations that the proposed algorithms perform very close to the optimal solution and much better than the previously proposed algorithms with runtime robust to the increasing number of the links and much smaller than that of the optimal algorithm.