In this paper, we study distributed scheduling in multihop multiple-input–multiple-output (MIMO) networks. We first develop a “MIMO-pipe” model that provides the upper layers a set of rates and signal-to-interference-plus-noise ratio (SINR) requirements that capture the rate–reliability tradeoff in MIMO communications. The main thrust of this paper is then dedicated to developing distributed carrier sense multiple access (CSMA) algorithms for MIMO-pipe scheduling under the SINR interference model. We choose the SINR model over the extensively studied protocol-based interference models because it more naturally captures the impact of interference in wireless networks. The coupling among the links caused by the interference under the SINR model makes the problem of devising distributed scheduling algorithms very challenging. To that end, we explore the CSMA algorithms for MIMO-pipe scheduling from two perspectives. We start with an idealized continuous-time CSMA network, where control messages can be exchanged in a collision-free manner, and devise a CSMA-based link scheduling algorithm that can achieve throughput optimality under the SINR model. Next, we consider a discrete-time CSMA network, where the message exchanges suffer from collisions. For this more challenging case, we develop a “conservative” scheduling algorithm by imposing a more stringent SINR constraint on the MIMO-pipe model. We show that the proposed conservative scheduling achieves an efficiency ratio bounded from below.

We study the problem of distributed scheduling in multi-hop MIMO networks. We first develop a ``MIMO-pipe" model that provides the upper layers a set of rates and SINR requirements, which capture the rate-reliability tradeoff in MIMO communications. The main thrust of this study is then dedicated to developing CSMA-based MIMO-pipe scheduling under the SINR model. We choose the SINR model over the extensively studied matching or protocol-based interference models because it more naturally captures the impact of interference in wireless networks. The coupling among the links caused by the interference makes the problem of devising distributed scheduling algorithms particularly challenging. To that end, we explore CSMA-based MIMO-pipe scheduling, from two perspectives. First, we consider an idealized continuous time CSMA network. We propose a dual-band approach in which control messages are exchanged instantaneously over a channel separate from the data channel, and show that CSMA-based scheduling can achieve throughput optimality under the SINR model. Next, we consider a discrete time CSMA network. To tackle the challenge due to the coupling caused by interference, we propose a ``conservative" scheduling algorithm in which more stringent SINR constraints are imposed based on the MIMO-pipe model. We show that this suboptimal distributed scheduling can achieve an efficiency ratio bounded from below.

With the convergence of multimedia applications and wireless communications, there is an urgent need for developing new scheduling algorithms to support real-time traffic with stringent delay requirements. However, distributed scheduling under delay constraints is not well understood and remains an under-explored area. A main goal of this study is to take some steps in this direction and explore the distributed opportunistic scheduling (DOS) with delay constraints. Consider a network with M links which contend for the channel using random access. Distributed scheduling in such a network requires joint channel probing and distributed scheduling. Using optimal stopping theory, we explore DOS for throughput maximization, under two different types of average delay constraints: 1) a network-wide constraint where the average delay should be no greater than ?; or 2) individual user constraints where the average delay per user should be no greater than am, m = 1,..., M. Since the standard techniques for constrained optimal stopping problems are based on sample-path arguments and are not applicable here, we take a stochastic Lagrangian approach instead. We characterize the corresponding optimal scheduling policies accordingly, and show that they have a pure threshold structure, i.e. data transmission is scheduled if and only if the rate is above a threshold. Specifically, in the case with a network-wide delay constraint, somewhat surprisingly, there exists a sharp transition associated with a critical time constant, denoted by ?*. If a is less than ?*, the optimal rate threshold depends on ?; otherwise it does not depends on a at all, and the optimal policy is the same as that in the unconstrained case. In the case with individual user delay constraints, we cast the threshold selection problem across links as a non-cooperative game, and establish the existence of Nash equilibria. Again we observe a sharp transition associated with critical time constants {?m*}, in the sense that when ?m? am*for all users, the Nash equilibrium becomes the same one as if there were no delay constraints.

Distributed opportunistic scheduling (DOS) is studied for wireless ad hoc networks in which many links contend for a channel using random access before data transmission. Simply put, DOS involves a process of joint channel probing and distributed scheduling for ad hoc (peer-to-peer) communications. Since, in practice, link conditions are estimated with noisy observations, the transmission rate must be backed off from the estimated rate in order to avoid transmission outages. Then, a natural question to ask is whether or not it is worthwhile for the link with successful contention to perform further channel probing to mitigate estimation errors, at the cost of additional probing. Thus motivated, this work investigates DOS with two-level channel probing by optimizing the tradeoff between the throughput gain from more accurate rate estimation and the resulting additional delay. By capitalizing on optimal stopping theory with incomplete information, it is shown that the optimal scheduling policy is threshold-based and is characterized by either one or two thresholds, depending on network settings. Necessary and sufficient conditions for both cases are rigorously established. In particular, this analysis reveals that performing second-level channel probing is optimal when the first-level estimated channel condition falls in between the two thresholds. Numerical results are provided to illustrate the effectiveness of the proposed DOS with two-level channel probing. This study is also extended to the case with limited feedback, in which the feedback from the receiver to its transmitter takes the form of$(0,1,e)$.

In this paper, we study distributed opportunistic scheduling (DOS) in an ad hoc network, where many links contend for the same channel using random access. In such a network, DOS involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence yield higher throughput. The desired tradeoff boils down to judiciously choosing the optimal stopping rule for channel probing and distributed scheduling. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal scheme for DOS turns out to be apurethresholdpolicy, where the rate threshold can be obtained by solving a fixed-point equation. We further devise iterative algorithms for computing the threshold. We also generalize the studies to take into account fairness requirements. Next, we explore DOS from a user-centric perspective, where each link seeks to maximize its own throughput. We treat the problem of threshold selection across different links as a noncooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. Since the best response strategy requires message passing from neighboring nodes, we then develop an online stochastic iterative algorithm based on local observations only, and establish its convergence to the Nash equilibrium. Because there is an efficiency loss at the Nash equilibrium, we then study pricing-based mechanisms to mitigate the loss. Our results reveal that rich physical layer/MAC layer (PHY/MAC) diversities are available for exploitation in ad hoc networks. We believe that these initial steps open a new avenue for channel-aware distributed scheduling.

Distributed opportunistic scheduling (DOS) protocols are proposed for multiple-input multiple-output (MIMO) ad-hoc networks with contention-based medium access. The proposed scheduling protocols distinguish themselves from other existing works by their explicit design for system throughput improvement through exploiting spatial multiplexing and diversity in a distributed manner. As a result, multiple links can be scheduled to simultaneously transmit over the spatial channels formed by transmit/receiver antennas. Taking into account the tradeoff between feedback requirements and system throughput, we propose and compare protocols with different levels of feedback information. Furthermore, in contrast to the conventional random access protocols that ignore the physical channel conditions of contending links, the proposed protocols implement a pure threshold policy derived from optimal stopping theory, i.e. only links with threshold-exceeding channel conditions are allowed for data transmission. Simulation results confirm that the proposed protocols can achieve impressive throughput performance by exploiting spatial multiplexing and diversity.

Distributed opportunistic scheduling is studied for wireless ad-hoc networks, where many links contend for one channel using random access. In such networks, distributed opportunistic scheduling (DOS) involves a process of joint channel probing and distributed scheduling. It has been shown that under perfect channel estimation, the optimal DOS for maximizing the network throughput is a pure threshold policy. In this paper, this formalism is generalized to explore DOS under noisy channel estimation, where the transmission rate needs to be backed off from the estimated rate to reduce the outage. It is shown that the optimal scheduling policy remains to be threshold-based, and that the rate threshold turns out to be a function of the variance of the estimation error and be a functional of the backoff rate function. Since the optimal backoff rate is intractable, a suboptimal linear backoff scheme that backs off the estimated signal-to-noise ratio (SNR) and hence the rate is proposed. The corresponding optimal backoff ratio and rate threshold can be obtained via an iterative algorithm. Finally, simulation results are provided to illustrate the tradeoff caused by increasing training time to improve channel estimation at the cost of probing efficiency.

We study channel aware distributed scheduling in ad hoc networks where many links contend for the common channel using random access, and the focus here is on the model where each transmitter node has multiple intended receivers. In such a network, channel probing takes place in two phases: 1) in phase I, all transmitters contend for the channel using random access to reserve the channel, and the probing to accomplish a successful channel contention takes a random duration; and 2) in phase II, subsequent probings are carried out to estimate the link conditions from the successful transmitter in phase I to its intended receivers, according to specific probing mechanisms, and the probing for each receiver takes a constant duration. We shall study various probing mechanisms for utilizing multi-receiver diversity in phase II and multiuser diversity in phase I for ad hoc (peer-to-peer) communications. Clearly, further probing increases the likelihood of seeing better channel conditions for exploiting diversities, but at the cost of additional time. Therefore, channel probing must be done efficiently to balance the tradeoff between the throughput gain from better channel conditions and the probing cost. One main objective of this study is to characterize this tradeoff in a stochastic decision making framework. Specifically, we cast network throughput optimization as an optimal stopping problem, and then explore channel aware distributed scheduling to leverage multi-receiver diversity and multiuser diversity in a joint manner. We show that the optimal scheduling policies for all proposed probing mechanisms exhibit threshold structures, indicating that they are amenable to easy distributed implementation. We show that the optimal thresholds and the maximum network throughput can be obtained off-line by solving fixed point equations. We further develop iterative algorithms to compute the optimal thresholds and the throughput.

The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. In this paper, we investigate the impact of noisy feedback on distributed NUM. We first study the distributed NUM algorithms based on the Lagrangian dual method, and focus on the primal-dual (P-D) algorithm, which is a single time-scale algorithm in the sense that the primal and dual parameters are updated simultaneously. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of the P-D algorithms in the presence of noisy feedback. When the gradient estimators are unbiased, we establish, via a combination of tools in Martingale theory and convex analysis, that the iterates generated by distributed P-D algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimators are biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Next, we study the impact of noisy feedback on distributed two time-scale NUM algorithms based on primal decomposition. We establish, via the mean ODE method, the convergence of the stochastic two time-scale algorithm under mild conditions, for the cases where the gradient estimators in both time scales are unbiased. Numerical examples are used to illustrate the finding that compared to the single time-scale counterpart, the two time-scale algorithm, although having lower complexity, is less robust to noisy feedback.

Distributed opportunistic scheduling is studied for wireless ad-hoc networks, where many links contend for one channel using random access. In such networks, distributed opportunistic scheduling (DOS) involves a process of joint channel probing and distributed scheduling. It has been shown that under perfect channel estimation, the optimal DOS for maximizing the network throughput is a pure threshold policy. In this paper, this formalism is generalized to explore DOS under noisy channel estimation. In such cases, the transmission rate needs to be backed off from the estimated rate to reduce outages. It is shown that the optimal scheduling policy remains threshold-based, and that the rate threshold turns out to hinge on the variance of the estimation error and be a functional of the backoff rate function. Since the optimal backoff rate is intractable, we devise suboptimal linear backoff schemes that back off the estimated signal-to-noise ratio (SNR) and hence the rate. The corresponding optimal backoff ratios and rate thresholds can be obtained via iterative algorithms. Finally, simulation results are provided to illustrate the tradeoff between increased training time to improve channel estimation and probing efficiency.

The implementation of distributed network utility maximization (NUM) algorithms hinges heavily on information feedback through message passing among network elements. In practical systems the feedback is often obtained using error-prone measurement mechanisms and suffers from random errors. There has been little work in this direction, and by and large the impact of noisy feedback remains unclear. A main objective of this study is to fill this void and to obtain a rigorous and systematic understanding of the impact of stochastic noisy feedback. In this paper, we consider distributed NUM in multi-hop wireless networks, and focus on the impact of noisy feedback on the distributed algorithms based on the Lagrangian dual method. These algorithms can in general be regarded as some form of gradient (or sub-gradient) based methods. Assuming strong duality, we study both cases when the stochastic gradients are unbiased or biased, and develop a general theory on the stochastic stability of these algorithms in the presence of noisy feedback. When the gradient estimator is unbiased, we establish, via a combination of the stochastic Lyapunov Stability Theorem and local analysis, that the iterates generated by distributed NUM algorithms converge with probability one to the optimal point, under standard technical conditions. In contrast, when the gradient estimator is biased, we show that the iterates converge to a contraction region around the optimal point, provided that the biased terms are asymptotically bounded by a scaled version of the true gradients. We also investigate the rate of convergence for the unbiased case, and find that, in general, the limit process of the interpolated process corresponding to the normalized iterate sequence is a stationary reflected linear diffusion process, not necessarily a Gaussian diffusion process. We also apply the above general theory to investigate stability of cross-layer rate control for joint congestion control and random access. Our numerical examples corroborate the theoretic findings well.

We consider a collocated wireless network where all links contend for a given channel and each link can hear others' transmissions. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or bad. In the latter case, further channel probing may lead to better channel conditions, which in turn yields higher throughput. There is clearly a tradeoff between the throughput gain from better channel conditions and the cost for further channel probing. The desired tradeoff can be achieved by choosing the optimal stopping time for channel probing and the transmission rate, in the sense of maximizing the overall average throughput. Using optimal stopping theory, we show that the joint optimal channel probing and transmission (JOCPT) strategy is a pure threshold policy, and interestingly, the threshold turns out to be the optimal average throughput, which is the solution to a fixed point equation. Since the optimal throughput usually cannot be obtained in closed form, we derive a lower bound and an upper bound on the optimal throughput, and devise an iterative algorithm to compute it. Finally, we use numerical examples to show that significant throughput gain can be achieved by the JOCPT strategy.

We consider distributed opportunistic scheduling (DOS) in wireless ad-hoc networks, where many links contend for the same channel using random access. In such networks, distributed opportunistic scheduling involves a process of joint channel probing and distributed scheduling. Due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. In the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence higher transmission rates. The desired tradeoff boils down to judiciously choosing the optimal stopping strategy for channel probing and the rate threshold. In this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. We first consider DOS from a network-centric point of view, where links cooperate to maximize the overall network throughput. Using optimal stopping theory, we show that the optimal strategy turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed point equation. We further devise an iterative algorithm for computing the threshold. Next, we explore DOS from a user-centric perspective, where each links seeks to maximize its own throughput. We treat the problem of rate threshold selections for different links as a non-cooperative game. We explore the existence and uniqueness of the Nash equilibrium, and show that the Nash equilibrium can be approached by the best response strategy. We then develop an online stochastic iterative algorithm using local observations only, and establish its convergence. Finally, we observe that there is an efficiency loss in terms of the throughput at the Nash equilibrium, and introduce apricing-based mechanism to mitigate the loss.

In multi-hop wireless networks, the optimal medium access control (MAC) design is challenging, partially due to the time-varying nature of the PHY-layer communication channels and the network topology. In this paper, we take a utility maximization approach to study fair MAC design towards QoS provisioning. To this end, we first identify two key challenges of wireless access control, namely the topology dependency and the channel dependency, therein. Based on the observation that the topology change and channel variation occur on different time scales, we decompose the utility maximization to two phases: a "global" optimization phase addresses the topology dependency, and arbitrates fair channel access across the links by adapting the persistence probability to achieve long-term fairness, and a "local" optimization phase deals with the channel dependence, and determines the transmission duration based on local channel conditions while maintaining short-term fairness. Observing that the MAC throughput depends on the realizations of channel contention in random access networks, we use stochastic approximation to investigate in depth the MAC design with the adaptive persistence mechanism in the global phase. Using Lyapunov's Stability Theorems and LaSalle's Invariance Theorem, we establish the stability of the proposed algorithm for the global phase and analyze the fairness under (omegaoarr, kappa)-fair utility functions. Our findings reveal that under the large network assumption, there exists a single equilibrium point for the proposed (omegaoarr, kappa)-fair MAC algorithm provided that kappa > 1. We also present the solution to the local optimization phase under general fairness constraints.

Time-varying channel conditions, due to multipath fading, present a unique challenge for wireless network design. In this paper, we take a cross-layer approach to study frequency-agile medium access control design for ad hoc networks. Specifically, building on the IEEE 802.11 standard, we propose an opportunistic multi-channel MAC protocol (OMC-MAC), with three key features: 1) by exploiting the channel variations across multiple channels, OMC-MAC achieves selection diversity gain in an opportunistic and distributed manner; 2) the size of the contention window is adjusted adaptively based on the estimate of the number of competing stations, which is obtained via using a sequential Monte Carlo technique; and 3) OMC-MAC achieves "resource pooling" and thus improves the stability of the network. Analysis results reveal that OMC-MAC in wireless LANs achieves significant throughput gain, even under heavy traffic conditions. Extensive simulation studies show that OMC-MAC can achieve efficient channel utilization for each added channel, compared with the standard 802.11 MAC protocol and other multichannel protocols such as DCA and MMAC. Finally, we show via examples that the sequential Monte Carlo method is effective for the adaptation of the contention window size

The number of competing stations has great impact on the network performance of wireless LANs. It is therefore of great interest to obtain accurate estimation of the number of competing stations so that adaptive control mechanisms can be carried out accordingly. Based on the observation that this estimation problem is nonlinear/non-Gaussian in nature, we propose to use a sequential Monte Carlo technique, namely, the particle filtering to improve the estimation accuracy. One key step in the proposed scheme is to exploit the unscented particle filter, which combines the merits of unscented transformation and particle filtering. Our simulation results indicate that the unscented particle filter can increase the accuracy of the estimation upto 33% in terms of the root mean square error (RMSE), compared with the extended Kalman filter (EKF), the unscented Kalman filter (UKF) and the SIR-particle filter

MIMO techniques using multiple antennas for both transmitting and receiving have recently manifested themselves to be very promising for future broadband wireless networks. Aiming to leverage the impact of these MIMO techniques on network protocol design in wireless LANs (WLANs), we take a utility approach to study channel-aware weighted proportional fair medium access control (WPF MAC) for QoS provisioning. Simply put, in this utility based approach, every user in a WLAN attempts to maximize its own utility, and the optimization procedure takes place in two stages: a channel contention phase that arbitrates fair channel access across the users via combining adaptive persistence mechanism with random backoff, and a data transmission phase that determines the transmission duration based on the channel conditions in each transmission round. Furthermore, adaptive beamforming is carried out by using the training signals embedded in the RTS/CTS handshake to enhance the spectral efficiency of the MIMO links. Using a stochastic approximation method, together with the Lyapunov stability theorems, we establish the stability of the adaptive persistence mechanism in the proposed WPF MAC and analyze the fairness across the users therein.

Deep shadowing and "hot-spots" are two challenging issues in wireless networks. Aiming to resolve these issues, we take a cross-layer design approach and devise a hierarchical multiuser diversity (HMD) transmission scheme, in which a user can choose to communicate with the base station either directly or using multiple hops via relay stations. Using a throughput-based criterion, we develop a direct/relay link construction algorithm. We then explore opportunistic scheduling under performance-based fairness constraints, for both direct links and relay links; a key goal is to achieve multiuser diversity in both tiers. Our results show that the HMD scheme can combat shadowing and "hot-spots" effectively in the sense that the total system throughput is increased significantly while the throughput requirements of the users are met.