This paper studies a wireless network consisting of multiple transmitter-receiver pairs where interference is treated as noise. Previously, the throughput region of such networks was characterized for either one time slot or an infinite time horizon. We aim to fill the gap by investigating the throughput region for transmissions over a finite time horizon. Unlike the infinite-horizon throughput region, which is simply the convex hull of the throughput region of one time slot, the finite-horizon throughput region is generally non-convex. Instead of directly characterizing all achievable rate-tuples in the finite-horizon throughput region, we propose a metric termed the rate margin, which not only determines whether any given rate-tuple is within the throughput region (i.e., achievable or unachievable), but also tells the amount of scaling that can be done to the given achievable (unachievable) rate-tuple such that the resulting rate-tuple is still within (brought back into) the throughput region. Furthermore, we derive an efficient algorithm to find the rate-achieving policy for any given rate-tuple in the finite-horizon throughput region.
@cite_14: 
@cite_9: 
@cite_6: We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. Two classes of scheduling policies are considered: 1) a maximum queue-length weighted independent set scheduling policy and 2) a randomized independent set scheduling policy where the set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the arrival slack in the system-a metric representing the overall load on the network. We prove that this upper bound is asymptotically tight in the sense that there exist classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. We extend our upper bounds to the case of multi-hop sessions. Through simulations, we study how our analysis compares with actual delays computed for i.i.d., Markovian, and trace-driven packet arrival processes.
@cite_0: We provide bounds for the expectations of the stationary delay and the sum of the stationary queue sizes under the approximate maximum weight scheduling (MWS) policy and under the longest-queue-first (LQF) policy in one-hop wireless networks. For MWS, our results improves the previously provided bounds; for LQF, the results are new. In the derivation of the new bounds, a connection with certain graph theory quantities has been established. We also derive bounds for the sum of the second moments of the stationary queue sizes, which are also bounds for the sum of the queue-size variances. The method is general and it can be used to derive bounds for the sum of even higher moments of the stationary queue sizes. However, for the approximate MWS policy, the bounds for the second or higher moments are only valid when the average arrival rate vector is confined to a subset of the capacity region that depends on the order of the moment.
@cite_24: It is well known that max-weight policies based on a queue backlog index can be used to stabilize stochastic networks, and that similar stability results hold if a delay index is used. Using Lyapunov optimization, we extend this analysis to design a utility maximizing algorithm that uses explicit delay information from the head-of-line packet at each user. The resulting policy is shown to ensure deterministic worst-case delay guarantees and to yield a throughput utility that differs from the optimally fair value by an amount that is inversely proportional to the delay guarantee. Our results hold for a general class of 1-hop networks, including packet switches and multiuser wireless systems with time-varying reliability .
@cite_19: In this paper, we propose a distributed cross-layer scheduling algorithm for wireless networks with single-hop transmissions that can guarantee finite buffer sizes and meet minimum utility requirements. The algorithm can achieve a utility arbitrarily close to the optimal value with a tradeoff in the buffer sizes. The finite buffer property is not only important from an implementation perspective, but, along with the algorithm, also yields superior delay performance. In addition, another extended algorithm is provided to help construct the upper bounds of per-flow average packet delays. A novel structure of Lyapunov function is employed to prove the utility optimality of the algorithm with the introduction of novel virtual queue structures. Unlike traditional back-pressure-based optimal algorithms, our proposed algorithm does not need centralized computation and achieves fully local implementation without global message passing. Compared to other recent throughput utility-optimal CSMA distributed algorithms, we illustrate through rigorous numerical and implementation results that our proposed algorithm achieves far better delay performance for comparable throughput utility levels.
@cite_13: In this paper, we propose a cross-layer scheduling algorithm that achieves a throughput “ e-close” to the optimal throughput in multihop wireless networks with a tradeoff of O([1 (e)]) in average end-to-end delay guarantees. The algorithm guarantees finite buffer sizes and aims to solve a joint congestion control, routing, and scheduling problem in a multihop wireless network while satisfying per-flow average end-to-end delay constraints and minimum data rate requirements. This problem has been solved for both backlogged as well as arbitrary arrival rate systems. Moreover, we discuss the design of a class of low-complexity suboptimal algorithms, effects of delayed feedback on the optimal algorithm, and extensions of the proposed algorithm to different interference models with arbitrary link capacities.
Some recent studies focused on reducing the delay by shrinking the infinite-horizon throughput region @cite_6 @cite_0 @cite_24 @cite_13 , where the average delay was studied in @cite_6 @cite_0 , and the worst-case delay was analyzed in @cite_24 @cite_13 . It was observed by @cite_6 @cite_0 @cite_24 @cite_13 that choosing a rate-tuple closer to the boundary of the infinite-horizon throughput region causes a larger delay, and hence, shrinking the throughput region removes those rate-tuples near the boundary corresponding to large delays. Furthermore, the effect of finite buffer size was consider in @cite_14 @cite_9 @cite_19 , and it turned out that the required buffer size increases with the rate-tuple. Indeed, by Little's law, the average length of data queue is proportional to the delay. Hence, this line of work also demonstrated the delay caused by the rate-tuples in the infinite-horizon throughput region.