الگوریتم های زمان بندی توزیع در احتمالات صف سرریز از یک رده.
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|79287||2011||13 صفحه PDF||سفارش دهید||11181 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computer Networks, Volume 55, Issue 1, 7 January 2011, Pages 343–355
In this paper, we are interested in using large-deviations theory to characterize the asymptotic decay-rate of the queue-overflow probability for distributed wireless scheduling algorithms, as the overflow threshold approaches infinity. We consider ad hoc wireless networks where each link interferes with a given set of other links, and we focus on a distributed scheduling algorithm called Q-SCHED, which is introduced by Gupta et al. First, we derive a lower bound on the asymptotic decay rate of the queue-overflow probability for Q-SCHED. We then present an upper bound on the decay rate for all possible algorithms operating on the same network. Finally, using these bounds, we are able to conclude that, subject to a given constraint on the asymptotic decay rate of the queue-overflow probability, Q-SCHED can support a provable fraction of the offered loads achievable by any algorithms.