Optimal Scheduling for Wireless On-Demand Data Packet Delivery to High-Speed Trains

被引:11
作者
Chen, Tianyi [1 ]
Shan, Hangguan [2 ]
Wang, Xin [3 ,4 ]
机构
[1] Univ Minnesota, Dept Elect & Comp Engn, Minneapolis, MN 55455 USA
[2] Zhejiang Univ, Dept Informat Sci & Elect Engn, Hangzhou 310027, Zhejiang, Peoples R China
[3] Fudan Univ, Dept Commun Sci & Engn, Key Lab Informat Sci Electmagnet Waves, Shanghai 200433, Peoples R China
[4] Florida Atlantic Univ, Dept Comp & Elect Engn & Comp Sci, Boca Raton, FL 33431 USA
基金
中国国家自然科学基金;
关键词
Algorithm analysis; integer linear program (ILP); on-demand services; packet schedule; wireless link; ALGORITHM; SYSTEMS;
D O I
10.1109/TVT.2014.2362912
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, we consider a cellular/infostation integrated network that 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). The problem cannot be solved efficiently by existing ILP solvers with guaranteed polynomial-time complexity in the worst case. By exploring the special structure of the formulated ILP, we propose a novel Checker algorithm and prove that this algorithm is guaranteed to find the offline optimal schedule in polynomial time. Based on the relevant insights, we further develop a class of online Checker algorithms that require only causal knowledge of service demands and wireless channel capacities. It is established that these online algorithms have a worstcase competitive ratio of 1/2, i.e., total revenue earned by them is at least half as much as the revenue earned by an offline optimal schedule that knows the complete a priori knowledge of future requests and channel conditions. Simulation results are provided to demonstrate the merit of the proposed algorithms.
引用
收藏
页码:4101 / 4112
页数:12
相关论文
共 22 条
[1]  
Agarwal M, 2002, IEEE INFOCOM SER, P487, DOI 10.1109/INFCOM.2002.1019293
[2]  
Ahmad A, 2010, PROCEEDINGS OF KNOWLEDGE MANAGEMENT 5TH INTERNATIONAL CONFERENCE 2010, P1
[3]   A NEW DISTRIBUTED ALGORITHM TO FIND BREADTH 1ST SEARCH-TREES [J].
AWERBUCH, B ;
GALLAGER, RG .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1987, 33 (03) :315-322
[4]   A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices [J].
Barbehenn, M .
IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (02) :263-263
[5]  
Barbu G., 2010, Tech. Rep.
[6]  
Bin Chen B, 2009, IEEE INFOCOM SER, P1404, DOI 10.1109/INFCOM.2009.5062056
[7]  
Chen TY, 2013, IEEE GLOB COMM CONF, P4507, DOI 10.1109/GLOCOMW.2013.6855661
[8]   Development and impact of the modern high-speed train: A review [J].
Givoni, Moshe .
TRANSPORT REVIEWS, 2006, 26 (05) :593-611
[9]   Information raining and optimal link-layer design for mobile hotspots [J].
Ho, DH ;
Valaee, S .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2005, 4 (03) :271-284
[10]  
Japan Central Railway Company, JAP CENTR RAILW CO S