Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks

DOI10.1109/TCNS.2015.2512678MaRDI QIDQ5358508zbMATH OpenOpenAlexFDO

Authors Qing He, Vangelis Angelakis, Anthony Ephremides, Di Yuan

Publication date 21 September 2017

Published in IEEE Transactions on Control of Network Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.4144

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Deterministic scheduling theory in operations research (90B35) Applications of design theory to circuits and networks (94C30)

Abstract: We consider a wireless network with a set of transmitter-receiver pairs, or links, that share a common channel, and address the problem of emptying finite traffic volume from the transmitters in minimum time. This, so called, minimum-time scheduling problem has been proved to be NP-hard in general. In this paper, we study a class of minimum-time scheduling problems in which the link rates have a particular structure consistent with the assumed environment and topology. We show that global optimality can be reached in polynomial time and derive optimality conditions. Then we consider a more general case in which we apply the same approach and thus obtain approximation as well as lower and upper bounds to the optimal solution. Simulation results confirm and validate our approach.

Cited in

(2)

• On the Complexity of Scheduling in Half-Duplex Diamond Networks
• Link scheduling in polynomial time

This page was built for publication: Polynomial Complexity Minimum-Time Scheduling in a Class of Wireless Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358508)