2015/04/24 by Srinath Narasimha, Narasimha, Srinath, Joy Kuri +3
Engineering · Computer Science · Business, Management and Accounting · #Advanced Wireless Network Optimization #Age of Information Optimization #Advanced Queuing Theory Analysis
paper · pdf · doi:10.48550/arxiv.1504.06387
We consider the problem of distributed scheduling in wireless networks where\nheterogeneously delayed information about queue lengths and channel states of\nall links are available at all the transmitters. In an earlier work (by Reddy\net al. in Queueing Systems, 2012), a throughput optimal scheduling policy\n(which we refer to henceforth as the R policy) for this setting was proposed.\nWe study the R policy, and examine its two drawbacks -- (i) its huge\ncomputational complexity, and (ii) its non-optimal average per-packet queueing\ndelay. We show that the R policy unnecessarily constrains itself to work with\ninformation that is more delayed than that afforded by the system. We propose a\nnew policy that fully exploits the commonly available information, thereby\ngreatly improving upon the computational complexity and the delay performance\nof the R policy. We show that our policy is throughput optimal. Our main\ncontribution in this work is the design of two fast and near-throughput-optimal\npolicies for this setting, whose explicit throughput and runtime performances\nwe characterize analytically. While the R policy takes a few milliseconds to\nseveral tens of seconds to compute the schedule once (for varying number of\nlinks in the network), the running times of the proposed\nnear-throughput-optimal algorithms range from a few microseconds to only a few\nhundred microseconds, and are thus suitable for practical implementation in\nnetworks with heterogeneously delayed information.\n