Research On Link Scheduling Problem Based On SINR Model In Wireless Sensor Networks

During the past several decades, wireless sensor networks have developed fastly and comprehensively, it has been widely used in many areas. In a wireless sensor networks, a fundamental problem is that how many communication links can be concurrently transmitted. This problem has attracted tremendous attention. Link scheduling determines which transmitterreceiver pairs(links) can be simultaneously activated at a given time slot. It is widely acknowledged that efficient scheduling can enhance the capacity, decrease delay and prolong the lifetime of wireless networks. Link scheduling is one of the major performance bottlenecks in wireless sensor networks.As transmissions utilize common medium in wireless communications environments, mutual interference among concurrently transmission links is an important issue. The choice of the interference model has a significant impact on the difficulty of developing algorithms with performances close to optimal. In the chapter 2, we introduce two main models. Compared to the graph-based model, the SINR(Signal-to-Interference-plus-Noise-Ratio) model has been recognized as a more realistic and accurate model for interference in wireless communications. Otherwise, it is vital to choose the right power assignment, in this paper, we use the oblivious assignment. The specific research contents are given as follow:(1) One-slot link scheduling includes two aspects: maximum links scheduling(MLS) and maximum weighted links scheduling(MWLS). One-slot link scheduling has been proved to be NP-hard, it is possible to design heuristic algorithms with better realistic performance. In third chapter we propose two heuristic algorithms for the two problems with obvious power assignments under the SINR model. For MLS, we propose an algorithm MTMA(Maximum Tolerance and Minimum Affectance), which improves the currently best approximation algorithm. For MWLS, we give an effective heuristic algorithm MWMA(Maximum Weighted and Minimum Affectance), which performs better on improving the throughput and reducing the running time. Our algorithm is more realistic for the noise is taken into consideration. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations. I also verify the importance of choosing the right power assignment and find out which power assignment performs better on our algorithms by simulation.(2) Distributed scheduling schemes have a drawback: the overhead incurred due to the control mini-slots. The more links need to be scheduled, the more control mini-slots are required. To reduce the overhead of the control mini-slot, in the chapter 4, introduce the concept of guard radius by using location information of nodes to screen the links and propose a distributed SINR-based scheduling scheme with pre-selection mechanism which deletes the links from random candidate links that can cause transmission failure. By this mechanism, algorithm can reduce the failure probability of choosing links to schedule. I proof our algorithm can achieve a product-form stationary distribution of the system showing throughput optimality. Theoretical analysis shows that the correctness of the algorithms. Otherwise, i design a heuristic scheduling algorithm with pre-selection mechanism.