Research On Link Scheduling In STDMA Wireless Mesh Networks

Rapid growth in wireless networks has resulted in a great demand for fast and ubiquitous connectivity. Fast and reliable wireless connectivity with a wider range many times exceeding the range of the transmitter has become a reality, by the mesh mode extension to the existing wireless technologies such as WiFi (IEEE 802.11) and WiMax (IEEE 802.16). However, as wireless mesh networks have very limited resource, it is necessary to provide high-efficiency resource allocation by a careful scheduling of links over long time horizon. The aim of this thesis is to provide a complete understanding of link scheduling issues in spatial reused time division multiplexing access (STDMA) mesh networks and explore the various link scheduling aspects that affect the performance of such networks. We have made our contributions in a number of phases as follows:1. We address the link scheduling problem based on the protocol interference model which is the simplest and most popularly applied model for investigating wireless mesh networks. Under the protocol interference model, Deploying the directed graph that represents the network topology, the conflict graph that specifies the interference relationship among the links and the graph-based coloration theory, we derive a basic link scheduling scheme that allows concurrent transmission over links at each timeslot. As the extensions of the basic scheme, diversified link scheduling frameworks are further proposed to address various aspects of influences and demands on the network performance, including fairness guarantee, dependence on traffic appearance and relay option, and the applications for multicast service. Corresponding simulations are conducted for each study and the results show the effectiveness and merits of our designed algorithms.2. We conduct extensive investigations on link scheduling issues by characterizing the interference introduced by concurrent transmissions with the physical interference model and design a so-called minimum network cost descrepency link scheduling algorithm. It involves two categories of scheduling scheme design, which are classified dependently on whether the wireless channel fading is deterministic or not. We formulate the link scheduling operation in the network with deterministic fading channels as the solution to an underlying link-rate vectors based network utility maximization (NUM) model that has been proved to be a convex optimization problem. A novel solution to this NUM model is proposed based on a direct dual decomposition to the convex optimization problem, followed by a scheduling algorithm designed to reduce the discrepancy between the anticipated network cost and the optimal value at each timeslot. Corresponding numerical results demonstrate the improvement of network utility and the convergence property of our solution.3. For the network with non-deterministic fading channels, we build extensive NUM models and design heuristic link scheduling algorithms that can be deployed in STDMA mesh networks. According to the availability of instantaneous channel status (ICS) information, rate region of the network with non-deterministic fading channels can be derived separately by integrating the channel fading with the link scheduling. And two extensive NUM models are formulated respectively for the networks with or without ICS. The variations of the two types of popular fading channels (i.e., Rayleigh fading channel and Ricean fading channel) are statistically computed to achieve the convex set of our two extensive NUM models. Moreover, two heuristic algorithms are developed based on the NUM models respectively, so as to handle the links more effectively in the STDMA mesh networks. The effectiveness of the algorithms is proved in the terms of network utility. And it is also shown that diversified performance demands can be met through numerical validation.