Home
Speakers
Schedule
Location and Directions
Hotel Information
Saswati Sarkar
University of Pennsylvania
Title: Asymptotic Delay Properties for Wireless Link Scheduling
Abstract: We consider the question of delay-optimal link scheduling in arbitrary topology wireless ad-hoc networks, and obtain delay guarantees that are asymptotically tight. We consider two classes of scheduling policies: 1) a maximum queue-length weighted independent set scheduling policy, and 2) a randomized independent set scheduling policy where the independent set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies and i.i.d. packet arrivals, we show that the average packet delay is bounded by a constant that depends on the \textit{chromatic number} of the interference graph, and the overall load on the network. We also prove that this upper bound is asymptotically tight as there exists classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. This is a joint work with Koushik Kar and Xiang Luo.