We are concerned with the scheduling of transmitter time, bandwidth and power for multi-access mobile communications for data communications when the channels are randomly time varying. Time is divided into small scheduling intervals, called slots, and information on the current channel rates for the various users is available at the start of the slot, when the user selections are made. The proportional fair sharing method (PFS) balances the conflict between selecting the users with the best immediate rates and helping those with poor average throughputs. We have analyzed the convergence and basic qualitative properties (Kushner, H.J. and Whiting, P.A., Proc. Allerton Conf., 2002; IEEE Trans. Wireless Commun., vol.3, p.1250-9, 2004). The paths of the throughputs converge to the solution of an ODE, akin to a mean flow. The behavior of the ODE describes the behavior of PFS. It has a unique equilibrium point that is asymptotically stable and optimal for PFS in that it is the maximizer of a concave utility function. Most past work assumed an infinite backlog of data. The data arrival process is often bursty with the data queued until transmitted, minimal throughput constraints, or a balance between queue length (or delay) and throughput, might be sought. There might be preemption by priority users. Natural modifications of PFS for these cases are shown to have some of the same properties. Simulations illustrate many of the features and the possible tradeoffs.

We are concerned with the allocation of the base station transmitter time in time-varying mobile communications with many users who are transmitting data. Time is divided into small scheduling intervals, and the channel rates for the various users are available at the start of the intervals. Since the rates vary randomly, in selecting the current user there is a conflict between full use (by selecting the user with the highest current rate) and fairness (which entails consideration for users with poor throughput to date). The proportional fair scheduler of the Qualcomm High Data Rate system and related algorithms are designed to deal with such conflicts. The aim here is to put such algorithms on a sure mathematical footing and analyze their behavior. The available analysis, while obtaining interesting information, does not address the actual convergence for arbitrarily many users under general conditions. Such algorithms are of the stochastic approximation type and results of stochastic approximation are used to analyze the long-term properties. It is shown that the limiting behavior of the sample paths of the throughputs converges to the solution of an intuitively reasonable ordinary differential equation, which is akin to a mean flow. We show that the ordinary differential equation (ODE) has a unique equilibrium and that it is characterized as optimizing a concave utility function, which shows that PFS is not ad-hoc, but actually corresponds to a reasonable maximization problem. These results may be used to analyze the performance of PFS. The results depend on the fact that the mean ODE has a special form that arises in problems with certain types of competitive behavior. There is a large set of such algorithms, each one corresponding to a concave utility function. This set allows a choice of tradeoffs between the current rate and throughout. Extensions to multiple antenna and frequency systems are given. Finally, the infinite backlog assumption is dropped and the data is allowed to arrive at random. This complicates the analysis, but the same results hold.

The authors consider the forward link of a one-cell mobile communications system with a single transmitter, a fixed number (K) of mobiles, and randomly time-varying channels. Data arrives at the base in some random way (which might have a bursty character) and is queued according to the destination until transmitted. We consider CDMA with control over the bit interval and power per bit, TDMA with control over the time allocated, bit interval, and power per bit. The control problem is the allocation of power and time to the K queues to assure stability of the queues. The control decisions are made at the beginning of the (small) scheduling intervals. The Liapunov function based stability methods are used to determine time and power allocations. The system and channel process are scaled by speed. Under a stability assumption on the fluid model obtained from the "mean drift," and some other natural conditions, it is shown that the scaled physical system can be controlled to be stable, uniformly in the speed, for fast enough speeds. Owing to the non-Markov nature of the problem, we use the perturbed Liapunov function method in order to obtain the control allocations. Each such function corresponds loosely to a performance criteria for some optimization problem. Part of the power of the analysis is due to the rather general conditions under which it works.

The paper demonstrates the usefulness of numerical methods of stochastic control theory for the design, analysis and control of multiplexing type systems and networks, as well as ATM type systems. The sources are of the Markov-modulated type, although the final results hold for other types (e.g. low-order AR schemes). Control problems arise when we wish to control cell loss due to buffer overflows by regulating the sources. The basic control mechanism is the deletion of selected low-priority cells, according to an appropriate state dependent rule. But the same results hold for many other schemes (e.g. purchasing incremental bandwidth). By exploiting the large size of the system (large number of users), the systems can be efficiently approximated by diffusion type processes, whether there is a control term or not, and for many types of control mechanisms. The basic controls are of the "low-priority cell deletion" type, and various extensions. They might be state dependent, and we can obtain optimal controls for cost functions that weigh buffer overflow, controller cell deletion loss as well as queue length. The limit equations are an effective aggregation of the original system. It is shown that there are substantial savings in losses with the use of optimal control techniques. The numerical methods can be used to balance the losses at the control with those due to buffer overflow, to minimize losses at the controller subject to constraints on buffer overflow, and to explore various approximations, systems aggregations, the interaction of multiple source classes of different priorities.>

The paper discusses a powerful approach to the routing problem in large networks of the trunk line type. The approximations are based on heavy traffic limit theorems. The sequence of suitably scaled available circuits converges to a reflected diffusion process as the network size grows, under reasonable conditions. This limit model contains the basic features of the original network, and provides a very useful basis for a good control strategy for the physical system. The optimal ergodic cost problem for a three (link) dimensional system is solved numerically via the Markov chain approximation method to get the optimal controls. These “three link” results can be approximated in such a way that they can be applied to a physical network of arbitrary size, using only “local” information. Indeed, the numerical approximations have the interpretation of a type of simplified or “aggregated” network, which allows the use of physical intuition in its application. The resulting polities are compared in simulations (on systems with hundreds of links) to other current approaches, and found to be quite competitive and have many advantages. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

The basic adaptive filtering algorithmX_{n+1}^{\epsilon} = X_{n}^{\epsilon} - \epsilon Y_{n}(Y_{n}^{'}X_{n}^{\epsilon} - \psi_{n})is analyzed using the theory of weak convergence. Apart from some very special cases, the analysis is hard when done for each fixed\epsilon > 0. But the weak convergence techniques are set up to provide much information for small\epsilon. The relevant facts from the theory are given. Definex^{\epsilon}(\cdot)byx^{\epsilon}(t) = X_{n}^{\epsilon}on[n\epsilon, n\epsilon + \epsilon). Then weak (distributional) convergence of\{x^{\epsilon}(\cdot)\}and of\{x^{\epsilon}(\cdot + t_{\epsilon})\}is proved under very weak assumptions, wheret_{\epsilon} \rightarrow \inftyas\epsilon \rightarrow 0. The normalized errors\{(X_{n}^{\epsilon} - \theta ) / \sqrt{\epsilon} \}are analyzed, where\thetais a "stable" point for the "mean" algorithm. The asymptotic properties of a projection algorithm are developed, where theX_{n}^{\epsilon}are truncated at each iteration, if they fall outside of a given set.

Recent results for getting diffusion limits of a sequence of suitably scaled stochastic processes are applied to the synchronization problem for a digital phase locked loop (DPLL). For small filter gains and symbol intervals a diffusion (Gauss-Markov) process approximation is rigorously obtained. This approximation yields approximate error variances, passage time distributions, and correlation properties (among other properties) for the DPLL. The problem of tracking a drifting clock is also treated.

Many problems in communication theory involve approximations of a Markov type to outputs of nonlinear systems (with or without feedback) often so that Fokker-Planck techniques can be used. A general and powerful method is presented for getting diffusion approximations to outputs of systems with wide-band inputs. The input is parametrized by\varepsilonand as\varepsilon \rightarrow 0the bandwidth goes to infinity. It is proved that the sequence of system output processes converges weakly to a Markov diffusion process which is completely characterized. Many communication systems fit this model. The assumptions are of a type commonly used either explicitly or implicitly in either current methods of analysis of similar systems. The usefulness and relative simplicity of the method is illustrated by its application to three examples: a) a phase-locked loop (PPL), where a Markov-dfffusion approximation of the error process is developed, b) an adaptive antenna system, where an asymptotic analysis of the equations for the system is given, and c) a diffusion approximation to the output of a hard limiter followed by a bandpass filter; input-output S/N ratios are developed. Since weak convergence methods are used, the approximate "limits" yield approximations to many types of functionals of the actual systems.