A Survey of Scheduling Theory in Wireless Data Networks.- Wireless Channel Parameters Maximizing TCP Throughput.- Heavy Traffic Methods in Wireless Systems: Towards Modeling Heavy Tails and Long Range Dependence.- Structural Results on Optimal Transmission Scheduling over Dynamical Fading Channels: A Constrained Markov Decision Process Approach.- Entropy, Inference, and Channel Coding.- Optimization of Wireless Multiple Antenna Communication System Throughput Via Quantized Rate Control.- Communication Strategies and Coding for Relaying.- Scheduling and Control of Multi-Node Mobile Communications Systems with Randomly-Varying Channels by Stability Methods.- A Game Theoretic Approach to Interference Management in Cognitive Networks.- Enabling Interoperability of Heterogeneous ad hoc Networks.- Overlay Networks for Wireless ad hoc Networks.- Dimensionality Reduction, Compression and Quantization for Distributed Estimation with Wireless Sensor Networks.- Fair Allocation of A Wireless Fading Channel: An Auction Approach.- Modelling and Stability of Fast TCP.
"SCHEDULING AND CONTROL OF MULTI-NODE MOBILE COMMUNICATIONS SYSTEMS WITH RANDOMLY-VARYING CHANNELS BY STABILITY METHODS (p. 177-178)
HAROLD J. KUSHNER*
Abstract. We consider a communications network consisting of many mobiles. There are random external data processes arriving at some of the mobiles, each destined for a unique destination or set of destinations. Each mobile can serve as a node in the possibly multi-hop (and not necessarily unique) path from source to destination. At each mobile the data is queued according to the source-destination pair.. Time is divided into small scheduling intervals.
The capacity of the connecting channels are randomly varying. The system resources such as transmission power and/or time, bandwidth, and perhaps antennas, must be allocated to the various queues in a queue and channelstate dependent way to assure stability and good operation. Lost packets might or might not have to be retransmitted. At the beginning of the intervals, the channels are estimated via pilot signals and this information is used for the scheduling decisions, which are made at the beginning of the intervals. Stochastic stability methods are used to develop scheduling policies.
The resulting controls are readily implementable and allow a range of tradeoffs between current rates and queue lengths, under very weak conditions. The basic methods are an extension of recent works for a system with one transmitter that communicates with many mobiles. The choice of Liapunov function allows a choice of the effective performance criteria. All essential factors are incorporated into a "mean rate" function, so that the results cover many different systems. Because of the non-Markovian nature of the problem, we use the perturbed Stochastic Liapunov function method, which is designed for such problems. Various extensions (such as the requirement of acknowledgments) are given, as well as a useful method for getting the a priori routes.
Key words. Scheduling in stochastic networks, randomly varying link capacities, mobile networks, stochastic stability, stability of networks with randomly varying links, routing in ad-hoc networks, perturbed stochastic Liapunov functions.
AMS(MOS) subject classifications. 49Q05, 49K40, 60K25, 90B15, 93D09, 93E15.
1. Introduction.
The paper considers the problem of scheduling in a network of M mobiles (to be referred to as nodes) with time varying link capacities. There are many (8) external sources with bursty data processes, each sending its data to its unique origin node, to be sent through the network to a unique (except for the multicasting case) destination node.
At each mobile, the data is queued until transmitted, in an infinite buffer depending on the source-destination pair. Some mobiles serve as intermediaries in the possibly multi-hop connections between sources and destinations. The routes between source and destination need not be unique.
We are concerned with the efficient and stabilizing allocation of the systern resources, say, transmission power, time and bandwidth, to the various queues at each mobile in a queue and channel-state dependent way. Time is divided into small scheduling intervals. The capacities of the connecting channels in each interval form a correlated random process. At the beginning of the intervals, the capacities (or surrogates such as the S/N ratios) are estimated where possible via pilot signals and this information is used for the scheduling during that interval. The resource allocation decisions are made at the beginning of the intervals. Owing to the random nature of the arrival and channel processes, the computation or even the existence of stabilizing policies is not at all obvious."
