The problem of designing scheduling algorithms for a multichannel (e.g., orthogonal frequency division multiplexing-based) wireless downlink network is considered. The classic MaxWeight algorithm, although throughput-optimal, results in a very poor per-user delay performance in such systems. Hence, an alternate class of algorithms called iterated longest queues first (iLQF) is proposed for overcoming this issue. The iLQF-class algorithms are analyzed in a number of different system configurations. A particular algorithm in this class, called iLQF with pullup, is shown to be rate function optimal for the problem in an appropriate large deviations setting, and is shown to result in a strictly positive value of the rate function for a number of modifications to the basic system model. Thus, the proposed algorithm yields provable performance guarantees. The analytic results are confirmed through simulations.

Uplink scheduling/resource allocation under the single-carrier FDMA constraint is investigated, taking into account the queuing dynamics at the transmitters. Under the single-carrier constraint, the problem of MaxWeight scheduling, as well as that of determining if a given number of packets can be served from all the users, are shown to be NP-complete. Finally, a matching-based scheduling algorithm is presented that requires only a polynomial number of computations per timeslot, and in the case of a system with large bandwidth and user population, provably provides a good delay (small-queue) performance, even under the single-carrier constraint. In summary, the results in first part of the paper support the recent push to remove SCFDMA from the Standards, whereas those in the second part present a way of working around the single-carrier constraint if it remains in the Standards.

This paper looks at the problem of designing medium access algorithm for wireless networks with the objective of providing high throughput and low delay performance to the users, while requiring only a modest computational effort at the transmitters and receivers. Additive inter-user interference at the receivers is an important physical layer characteristic of wireless networks. Today's Wi-Fi networks are based upon the abstraction of physical layer where inter-user interference is considered as noise leading to the 'collision' model in which users are required to co-ordinate their transmissions through Carrier Sensing Multiple Access (CSMA)-based schemes to avoid interference. This, in turn, leads to an inherent performance trade-off [1]: it is impossible to obtain high throughput and low delay by means of low complexity medium access algorithm (unless P=NP). As the main result, we establish that this trade-off is primarily due to treating interference as noise in the current wireless architecture. Concretely, we develop a simple medium access algorithm that allows for simultaneous transmissions of users to the same receiver by performing joint decoding at receivers, over time. For a receiver to be able to decode multiple transmissions quickly enough, we develop appropriate congestion control where each transmitter maintains a "window" of undecoded transmitted data that is adjusted based upon the "feedback" from the receiver. In summary, this provides an efficient, low complexity "online" code operating at varying rate, and the system as a whole experiences only small amount of delay (including decoding time) while operating at high throughput.

This paper considers the problem of designing scheduling algorithms for multichannel (e.g., OFDM-based) wireless downlink networks, with a large number of users and proportionally large bandwidth. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iterated Heaviest matching with Longest Queues First (iHLQF) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function-optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF, however, has higher complexity than MaxWeight (n4versusn2, respectively). To overcome this issue, a new algorithm called Server-Side Greedy (SSG) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice tradeoff between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

This paper considers the problem of designing scheduling algorithms for multi-channel (e.g., OFDM-based) wireless downlink systems. We show that the Server-Side Greedy (SSG) rule introduced in earlier papers for ON-OFF channels performs well even for more general channel models. The key contribution in this paper is the development of new mathematical techniques for analyzing Markov chains that arise when studying general channel models. These techniques include a way of calculating the distribution of the maximum of a multi-dimensional Markov chain (note that the maximum does not have the Markov property on its own), and also a Markov chain stochastic dominance result using coupling arguments.

We are interested in the following question: given n numbers x1, ..., xn, what sorts of approximation of average xave= 1overn (x1+ ... + xn) can be achieved by knowing only r of these n numbers. Indeed the answer depends on the variation in these n numbers. As the main result, we show that if the vector of these n numbers satisfies certain regularity properties captured in the form of finiteness of their empirical moments (third or higher), then it is possible to compute approximation of xavethat is within 1 ±ε multiplicative factor with probability at least 1 - δ by choosing, on an average, r = r(ε, δ, σ) of the n numbers at random with r is dependent only on ε, δ and the amount of variation σ in the vector and is independent of n. The task of computing average has a variety of applications such as distributed estimation and optimization, a model for reaching consensus and computing symmetric functions. We discuss implications of the result in the context of two applications: load-balancing in a computational facility running MapReduce, and fast distributed averaging.

Scheduling for multi-channel (e.g., OFDM-based) wireless downlink systems is considered with the objective of providing low delay performance to users with real-time and stochastic traffic. The main contribution is the design of a low-complexity scheduling algorithm for the system with desired performance (in a large deviations sense). In particular, as the number of users and channels grows, the algorithm ensures an exponential decay of the probability of encountering significant delay at a near optimal decay rate when the arrivals are symmetric and the channel follows an ON-OFF model with multi-packet reception. The algorithm also provides consistently good performance in the larger set up by guaranteeing throughput optimality, and a non-zero decay rate if it is possible under any other algorithm.

This paper considers the problem of designing scheduling algorithms for multi-channel (e.g., OFDM) wireless downlink networks with n users/OFDM sub-channels. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, we show it has zero rate function in our setting). To address this, we propose a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) that is shown to be throughput optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF however has higher complexity than MaxWeight (n4vs. n2respectively). To overcome this issue, we propose a new algorithm called SSG (Server-Side Greedy). We show that SSG is throughput optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n2) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

Many routing protocols exist for mobile ad hoc networks. To select the most appropriate protocol, evaluation of candidate protocols must be performed with respect to a specific operating environment, which is not an easy task. However, selecting the best protocol can be a key factor in system behavior, determining whether the system successfully satisfies application requirements. Most of the relevant research in this area relies on simulation studies or empirical analysis to select a routing protocol, requiring an infeasible amount of time and resources for the approaches to be used in real-time decision making. In this paper we describe work toward analytically expressing protocol performance metrics in terms of environment-, protocol- , and application-dependent parameters. This work provides a foundation for adaptive protocol suites that will eventually enable an integrated context-aware communication paradigm.

This correspondence derives bounds on the jamming capacity of a slotted ALOHA system. A system with n legitimate users, each with a Bernoulli arrival process is considered. Packets are temporarily stored at the corresponding user queues, and a slotted ALOHA strategy is used for packet transmissions over the shared channel. The scenario considered is that of a pair ofillegitimateusers that jam legitimate transmissions in order to communicate over the slotted ALOHA channel. Jamming leads to binary signaling between the illegitimate users, with packet collisions due to legitimate users treated as (multiplicative) noise in this channel. Further, the queueing dynamics at the legitimate users stochastically couples the jamming strategy used by the illegitimate users and the channel evolution. By considering various independent and identically distributed (i.i.d.) jamming strategies, achievable jamming rates over the slotted ALOHA channel are derived. Further, an upper bound on the jamming capacity over the class of all ergodic jamming policies is derived. These bounds are shown to be tight in the limit where the offered system load approaches unity.