Schedule Algorithms For Data Packet With Time-dependent Revenue And Nonuniform Bandwidth Limits

This thesis investigates the on-demand packets scheduling problem under nonuniform bandwidth for cellular/infostation integrated network in high speed railway system.In the cellular/infostation integrated network,cellular network is usually used to provide seamless coverage with a low data transmission rate,but infestations deployed besides the railway support a high data transmission rate which can deliver data services for high-speed trains.The integrated network can mix the advantage of cellular network and infostation together to provide a high data transmission rate in the wide travelling area of trains.In cellular/infostation integrated network,service requests and acknowledgements are sent through the cellular network to a content server,while data delivery is achieved via trackside infostations.In order to improve the user network service experience,to provide users with stable,low latency network services and to achieve efficient resource allocation with low computational complexity,the on-demand request scheduling problem is proposed which aims to find the optimal solution to maximum the whole revenue.This thesis analyzes two formulations of the problem: scheduling of requests with and without user-specific bandwidth restrictions.According to analyze the special structure of the problem,the two problems are both formulated into integer linear programs and furthermore equivalent binary linear program with the virtual time slot mapping.We prove that the problem is NP-hard.By exploring the special structure of the binary linear program,we propose two new algorithms: greedy algorithm based on new utility function and a rescheduling algorithm based on the 'checker router'.For the scheduling problem with user-specific bandwidth constraints,we transform the NP-hard problem into a maximum weight matching problem in the weighted binary graph,which can be solved with Kuhn-Munkres algorithm.Firstly,a more universal price model is adopted.Secondly,greedy algorithm is proposed and analyzed.Then we ingeniously transform the problem into a weighted bipartite graph which can fulfill all the restrictions and then the Kuhn-Munkres algorithm is used in the bipartite graph to approximately maximize the revenue while reducing the complexity.An online algorithm is also developed.Simulation results are provided to demonstrate the merit of the proposed algorithms.