Reduced-complexity delay-efficient throughput-optimal distributed scheduling with heterogeneously delayed network-state information

We consider the problem of distributed scheduling in wireless communication networks where heterogeneously delayed queue lengths and channel states of all links are available at all the transmitters. In an earlier work (by Reddy et al. in Queueing Systems, 2012), a throughput-optimal scheduling policy (which we refer to henceforth as the R policy) for this setting was proposed. We study the R policy, and examine its two drawbacks - (i) its huge computational complexity, and (ii) its non-optimal average per-packet queueing delay. We show that the R policy unnecessarily constrains itself to work with information that is more delayed than that afforded by the system. We propose a new distributed scheduling policy that fully exploits the common state information available to all transmitters, thereby greatly improving upon the computational complexity and the delay performance relative to those of the R policy. We also establish the throughput optimality of our policy analytically. We evaluate the performance of the proposed policy and validate our analytical results through extensive numerical simulation. Thus, our work enlarges the ambit of networks for which throughput-optimal scheduling is practicable.