Research On Delay Improvement Of Backpressure Scheduling Algorithm In Multi-hop Wireless Networks

In recent years,with the popularity of wireless networks,the use of mobile terminals is becoming more common.However,the shortage of bandwidth resources,resulting in the existing wireless network can not meet the needs of users in wireless network.A good link scheduling algorithm can make full use of bandwidth resources and improve network throughput and stability,so that the user experience greatly improved.In the paper,the BP link scheduling algorithm is a dynamic and efficient algorithm for allocating bandwidth resources,which has the characteristics of optimal throughput and keeping the network stable.However,considering the actual application,there are still many areas to be improved,especially the delay performance of BP algorithm.In this paper,we analyze the delay performance of BP algorithm by simulation experiments and find out the reason of poor delay performance.We propose the two improved algorithms,HDBP algorithm based on hop count and queuing delay and PBP algorithm based on average delay.In order to reduce the delay and improve the network throughput,both two algorithm mainly use the different factors to calculate the link weights.The simulation results also show that the improved HDBP and PBP algorithm can improve well the delay performance of BP algorithm.Then,with the development of network technology,the transmission service provided by wireless network extends from single data to various real-time business,such as voice calls and multimedia.Different services on the quality of service(QoS)have different requirements,how reasonable allocation of resources according to business characteristics to meet the QoS of the business is also increasingly important.Therefore,in this paper,we studies how BP,HDBP and PBP algorithms guarantee QoS of real-time service.By analyzing the queue scheduling characteristics of BP,HDBP and PBP algorithm,we use different data flow weighting methods for real-time data and non-real-time data flow to improve the priority of real-time flow and guarantee its QoS requirements.The simulation results show that the BP,HDBP and PBP algorithm with QoS guarantee can effectively improve the delay performance and throughput of real-time data stream.Finally,in this paper,we need to solve an NP-hard problem,that is,in the implementation of BP,HDBP and PBP link scheduling algorithms,it is necessary to find a set of link scheduling with the sum of maximum link weights.We use a local greedy scheduling(LGS)approximation algorithm to obtain a link scheduling set with maximum sum of link weight and greatly reduce the implementation complexity.On the basis of the LGS,the specific implementation process of BP,HDBP and PBP link scheduling algorithm is designed in detail.