Scheduling in Wireless Networks with Oblivious Power Assignments: Analyzing the Physical Interference Model

This thesis studies the capacity of multipoint radio networks. One is given a set of requests for connections between pairs of devices. We need to assign each request a time slot and a transmission power such that the requests in each time slot can be scheduled simultaneously. The feasibility of simultaneous communication is defined by the widely accepted SINR interference model. We strive to minimize the time needed to schedule all requests. Our focus lies on algorithms using distance-based power assignments, for which the power of a request relies only on the distance between the devices. Such assignments are inherently local and particularly useful in distributed settings. Our analysis reveals that algorithms applying a clever, nontrivial choice of the transmission powers significantly outperform currently implemented algorithms. We further present good scheduling strategies when restricting to energy-efficient power assignments.