Research On Link Scheduling Problem Based On Hypergraph Model And Interference Cancellation

The application of Wireless Sensor Networks(WSNs) has been shifted from the military arena to the people’s ordinary business life along with the development and maturation of wireless technology. One’s life has earthshaking changed with the application of WSNs.Compared to a wired network, a wireless network has a fundamental property of sharing the common(radio) communication channels. Therefore, this will inevitably interfere with each other and even prevent the corrected reception of signals as parallel transmission. We have to retransmit those conflicting signals for the purpose of transmitting of the intended information which reduces the throughput of the network. Link scheduling is an important approach to decrease interference among the transmission links and enhance the throughput of the network.Link scheduling problem in a wireless network can roughly include two sub-problems. One is maximum link scheduling problem(Max LSP) and the other is the shortest link scheduling(SLS). That is, for a given set of links1 2{,,..., }nL ?l l l, the purpose of the former is computing the largest possible subset of links S ?L that can be scheduled simultaneously without conflicts.The latter is to schedule all the links in the minimum slots.In this paper, based on the large amount of works for the scheduling problem, we improve the related algorithms under the hypergraph and SINR models or with the successive interference cancellation(SIC) for the shortest link scheduling problem. We prove the correctness and effectiveness for them. For the maximum link scheduling problem, we improved the algorithm with SIC and present the ratio of improved algorithm to the existing algorithm; the simulation results present the effectiveness for the improved algorithm.This paper includes five chapters. In the first chapter, we briefly introduce the concepts of wireless networks, common application and the significance of the topic researched. In the second chapter, we present the models of link scheduling problems and the terminology and technique which is used in this paper. In the third chapter, we focus on the shortest link scheduling problem under hypergarph and SINR models, propose an approximation algorithm with obvious power assignment for the better performance than the existing algorithm. We present the correctness, scheduling length, the time complexity and the approximation ratio of the improved algorithm of the existing algorithm in this chapter. At the end of this chapter, we show the simulation of improved algorithm. In the chapter forth, combining the results of chapter three and SIC we improve another algorithm for the problem of the shortest link scheduling problem and propose approximation algorithm with SIC for the maximum link schedulingproblem. Moreover, we prove the correctness and effectiveness of the improved algorithms and show the simulation of them.At the end of the paper, we conclude the shortest link scheduling problem and the maximum link scheduling problem and look ahead the problem of those in the further.