On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks
Abstract : In this paper, we consider the problem of scheduling real-time traffic in wireless networks under a conflict-graph interference model and single-hop traffic. The objective is to guarantee that at least a certain fraction of packets of each link are delivered within their deadlines, which is referred to as delivery ratio . This problem has been studied before under restrictive frame-based traffic models, or greedy maximal scheduling schemes like LDF (Largest-Deficit First) that can lead to poor delivery ratio for general traffic patterns. In this paper, we pursue a different approach through randomization over the choice of maximal links that can transmit at each time. We design randomized policies in collocated networks, multi-partite networks, and general networks, that can achieve delivery ratios much higher than what is achievable by LDF. Further, our results apply to any traffic (arrival and deadline) process that evolves as an unknown positive recurrent Markov chain. Hence, this work is an improvement with respect to both efficiency and traffic assumptions compared to the past work. We further present extensive simulation results over various traffic patterns and interference graphs to illustrate the gains of our randomized policies over LDF variants.
? Most of the current research on opportunistic scheduling focus on the downlink of a cellular system.
? In such a system, there exists a natural central controller, the base station.
? An interesting question is whether and how to exploit the time domain diversity in a distributed environment, such as an ad-hoc network.
? The opportunistic scheduling problems studied have the net effect of increasing the overall effective capacity of the wireless network.
? This means that the network can now accommodate more users or higher-data-rate users.
? In this problem, packets arrive to a single link, each with a non-negative constant weight and a deadline.
? Besides the works above on providing QoS guarantees for wireless networks, there is literature on approximation algorithms for single-link buffer management problem.
? The problem is interesting and challenging when the packet arrival rate is not too high so that the optimal policy can fundamentally achieve a high p.
? If the packet deadlines become very large, the problem is reduced to the regular non real-time scheduling and deadline-oblivious algorithms like LDF should perform reasonably well.
• An optimal algorithm that fulfills any feasible minimum delivery ratio requirements is proposed.
• We propose a feasibility optimal algorithm, i.e. an algorithm which fulfills any feasible requirement.
• Multicast traffic could be approached with the simplifications proposed, in which the system model can be adapted, without loss of generality, to consider each client subscribing to a single flow.
• A near optimal, offline, polynomial time algorithm is proposed to minimize the maximum stretch under the assumption of continuous rates, and various online algorithms for continuous-rates/discrete-rates are studied with simulations.
? The performance of LDF in the non-frame-based setting has been studied in terms of the efficiency ratio, which is the fraction of the real-time throughput region guaranteed by LDF.
? A key technique in analyzing the achievable efficiency ratio in our model is to look at the return times of the traffic Markov chain and analyze the performance of scheduling algorithms over long enough cycles consisting of multiple return times.
? We compare the performance of our randomized algorithms, AMIX-ND and AMIX-MS with LDF.
? In particular, our proposed randomized algorithms significantly outperform the well-known LDF policy in terms of efficiency ratio.
|