Packet scheduling for on-demand data services to high-speed trains over wireless links

In this paper, we consider a cellular/infostation integrated network which supports on-demand data service delivery over a wireless link to users in a high-speed train. For the requests with different lifetimes and prices that they are willing to pay, we develop the optimal packet schedule that aims at earning the maximum revenue. To this end, we formulate the problem as an integer linear program (ILP) which is in general NP-hard. However, by exploring the special structure of the formulated ILP, we show that this problem can be turned into a P problem that admits efficient solvers. Specifically, we propose a novel Checker algorithm and prove that this algorithm is guaranteed to find the offline optimal schedule for the intended problem in polynomial time, when the number of total requests is proportional to the length of the total transmission time span. Based on the relevant insights, a class of efficient online Checker algorithms are then developed to approach the optimal schedule when a-priori knowledge of service demands and/or wireless channel capacities is not available in practical systems. It is shown that these online algorithms have a competitive ratio of 1/2, i.e., total revenue earned by them is at least half as much as the revenue earned by offline optimal schedule. Simulation results are provided to demonstrate the merit of the proposed algorithms.