Rate Region of Scheduling a Wireless Network with Discrete Propagation Delays

We study the link scheduling problem of wireless networks where signal propagation delays are multiples of certain time interval. The problem can be modeled as a character of the independent sets of periodic graphs, which have infinitely many vertices. We show that the rate region of scheduling a network can be achieved using collision-free, periodic schedules, and derive a graphical approach to explicitly characterize the rate region. In particular, a collision-free schedule can be equivalent to a path in a graph called the scheduling graph induced by the network collision profile and the propagation delays, and hence the rate region is equal to the convex hull of the rate vectors associated with the cycles of the scheduling graph, which have bounded length. With the maximal independent set problem as a special case, calculating the whole rate region is NP hard and also hard to approximate. By exploring a partial order on the paths, we derive an algorithm to calculate a subset of the rate region more efficiently. Our results are also of independent interest for periodic graphs.