الگوریتم های زمان بندی در شبکه های بی سیم
Abstract
1- Introduction
2- Network model and problem formulation
3- Scheduling with uncertain channel statistics
4- Learning greedy maximal matchings
5- Performance analysis under primary interference
6- Stochastic network control
7- Extensions to other scheduling constraints
8- Simulation results
9- Conclusion
References
Abstract
We study the problem of learning channel statistics to efficiently schedule transmissions in wireless networks subject to interference constraints. We propose an algorithm that uses greedily-constructed schedules in order to learn the channels’ transmission rates, while simultaneously exploiting previous observations to obtain high throughput. Comparison to the offline solution shows our algorithm to have good performance that scales well with the number of links in the network. We then turn our attention to the stochastic setting where packets randomly arrive to the network and await transmission in queues at the nodes. We develop a queue-length-based scheduling policy that uses the channel learning algorithm as a component. We analyze our method in time-varying environments and show that it achieves the same stability region as that of a greedy policy with full channel knowledge.
Introduction
A major challenge in the design of wireless networks is the need to schedule transmissions so that the nodes in the network can efficiently share the common spectrum. Nodes that are nearby can interfere with one another, and, therefore, network controllers must choose simultaneous link activations that do not violate interference constraints. Additionally, scheduling decisions must take channel state information into account. In many settings, it is not possible to know the channel in advance. The nodes can only learn the channel statistics by transmitting on the channels and using receiver feedback to observe the results. Due to multi-path fading and environmental interference, the channel state is often time-varying, and multiple observations are needed in order to obtain an accurate estimate of the channel statistics. This introduces a tradeoff between exploration and exploitation. The nodes may have to forgo scheduling those channels that, so far, have given the highest throughput in order to improve their understanding of under-observed channels. With perfect channel knowledge, it is well known that the maxweight policy, first explored in [2], provides a throughput optimal scheduling scheme that activates edges based on queue length and channel conditions, subject to interference constraints. The maxweight policy weights each edge by the product of its queue backlog and channel rate and chooses a link activation that maximizes the summation of weights in the set [3]. Depending on the interference constraints imposed on the network, this requires that the controller solves a complex combinatorial optimization problem at each time step of the algorithm. A drawback of the max-weight policy is that it is heavily centralized and assumes that the network controller knows the queue backlog at every edge in the network. For this reason, the use of greedy scheduling methods have been explored in the literature [4–8]. Under these methods, at each time step, the activation set is chosen according to a greedy combinatorial algorithm. In many settings, this construction can be performed in a distributed manner by the nodes of the network. The cost of using greedy algorithms is that, in general, they are not able to guarantee throughput optimality. However, under certain interference constraints, they can obtain network stability over a guaranteed fraction of the network’s throughput region.