We address the joint channel assignment and power allocation question in a multichannel wireless (access point) network where channel states differ across channels as well as users, and vary with time. Our goal is to obtain channel assignment and power allocation solutions that can dynamically adapt to changing channel conditions, and would maximize system throughput under per-user bandwidth (QoS) constraints, in a long-term sense. Using stochastic optimization techniques, we obtain an optimal scheduling policy that operates without knowledge of arrival rates and channel statistics (depending only on the instantaneous channel states and the queue lengths), and attains the overall system throughput that is arbitrarily close to the maximum achievable value with all per-user bandwidth constraints satisfied.

We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. We consider two classes of scheduling policies: 1) a maximum queue-length weighted independent set scheduling policy, and 2) a randomized independent set scheduling policy where the independent 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 and i.i.d. packet arrivals, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the overall load on the network. We also 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. Through simulations we examine the scaling of the average packet delay with respect to the overall load on the network, and the chromatic number of the link interference graph.

We consider the joint scheduling and power allocation problem for uplink transmissions in a multichannel access point network, and develop solutions to achieve the maximum system throughput under QoS constraints for each user. In this frame-based multi-channel OFDM system, our goal is to determine when in the frame and on which channels each user should transmit, and how the power of each user should be split across the channels it uses. Our goal is to maximize the overall effective data rate in the network, taking into account variations in channel rates across channels as well as users, while satisfying minimum rate constraints for each user. Although this problem is in general a complex non-linear mixed-integer optimization question, we show that the optimal schedule and power allocation can be computed in polynomial time under a high SINR approximation. Finally we propose and evaluate several simple heuristics for this problem, and show that some of these attain a performance that is very close to the optimum, at fairly low computational cost.

The question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the ldquointerference degreerdquo of the network, which is the maximum number of transmitter-receiver pairs that interfere with any given transmitter-receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove that in frequency division multiplexed systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, is throughput optimal. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

We consider the problem of uplink/downlink scheduling in a multichannel wireless access point network where channel states differ across channels as well as users, vary with time, and can be measured only infrequently. We demonstrate that, unlike the infrequent measurement of queue lengths, infrequent measurement of channel states reduce the maximum attainable throughput. We then prove in frequency division multiplexing systems, a dynamic scheduling policy that depends on both the channel rates (averaged over the measurement interval) and the queue lengths, attains the maximum possible throughput. We also generalize the scheduling policy to solve the joint power allocation and scheduling problem in orthogonal frequency division multiplexing systems. In addition, we provide simulation studies that demonstrate the impact of the frequency of channel and queue state measurements on the average delay and attained throughput.

We consider the uplink channel assignment problem in a multi-channel access point wireless network, with the goal of attaining maximum system throughput. In this setup, a set of orthogonal channels must be assigned to a set of users, where each user splits its power optimally across the channels allocated to it. While the optimal power allocation solution has a "water-filling" type structure, the optimal channel assignment problem is very challenging due to the non-linear dependence of user throughput on the set of channels assigned to it. Since the optimal channel allocations is computationally intensive to obtain in general, we analyze the system in the two extremal SINR regimes (very high and very low SINR) and show how the optimal solutions can be obtained in these regimes in a computationally efficient manner. Finally, we demonstrate that the best of the optimal solutions obtained for the two extremes shows excellent (close to optimal) performance over the entire SINR range.