Wireless Network Scheduling with Discrete Propagation Delays: Theorems and Algorithms

Wireless network scheduling is studied for the scenario that the signal propagation delays between network nodes are multiples of a time interval. Such a network can be modeled as a hypergraph together with a matrix specifying the delays. The link scheduling problem is closely related to the independent sets of the periodic hypergraph induced by the network model. However, as the periodic hypergraph has infinitely many vertices, independent sets cannot be solved efficiently and explicitly using the existing algorithms designed for generic graphs or hypergraphs. In this paper, a sequence of directed graphs of a finite size called scheduling graphs are derived to provide an explicit characterization of the rate region of link scheduling. A collision-free schedule is equivalent to a path in a scheduling graph, and the rate region is equal to the convex hull of all the rate vectors associated with the cycles of a scheduling graph. For a special scheduling graph called the non-overlapping scheduling graph, a dominance property is studied to further simplify the rate region characterization, so that both the number and length of the cycles to be enumerated can be significantly reduced. For the common problems like calculating the rate region and maximizing a weighted sum of the scheduling rates, we derive algorithms that are more efficient than using the algorithms designed for generic graphs on the scheduling graphs directly.