A State Action Frequency Approach to Throughput Maximization over Uncertain Wireless Channels

被引:7
作者
Jagannathan, Krishna [1 ]
Mannor, Shie [2 ]
Menache, Ishai [3 ]
Modiano, Eytan [4 ]
机构
[1] IIT Madras, Dept Elect Engn, Madras 600036, Tamil Nadu, India
[2] Technion, Fac Elect Engn, IL-32000 Haifa, Israel
[3] Microsoft, EXtreme Comp Grp, Redmond, WA 98052 USA
[4] MIT, Cambridge, MA 02139 USA
基金
美国国家科学基金会;
关键词
D O I
10.1080/15427951.2011.601934
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider scheduling over a wireless system in which the channel state information is not available a priori to the scheduler but can be inferred from past history. Specifically, the wireless system is modeled as a network of parallel queues. We assume that the channel state of each queue evolves stochastically as an independent on/off Markov chain. The scheduler, which is aware of the queue lengths but is ignorant of the channel states, has to choose at most one queue at a time for transmission. The scheduler has no information regarding the current channel states but can estimate them from the acknowledgment history. We first characterize the capacity region of the system using tools from the theory of Markov decision processes (MDPs). Specifically, we prove that the capacity region boundary is the uniform limit of a sequence of linear programming (LP) solutions. Next, we combine the LP solution with a queue-length-based scheduling mechanism that operates over long frames to obtain a throughput optimal policy for the system. By incorporating results from MDP theory within the Lyapunov-stability framework, we show that our frame-based policy stabilizes the system for all arrival rates that lie in the interior of the capacity region.
引用
收藏
页码:136 / 160
页数:25
相关论文
共 18 条
[1]   Optimality of Myopic Sensing in Multichannel Opportunistic Access [J].
Ahmad, Sahand Haji Ali ;
Liu, Mingyan ;
Javidi, Tara ;
Zhao, Qing ;
Krishnamachari, Bhaskar .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2009, 55 (09) :4040-4050
[2]  
Altman E, 1999, STOCH MODEL SER
[3]  
Bertsimas D., 1997, INTRO LINEAR OPTIMIZ
[4]   On Wireless Scheduling With Partial Channel-State Information [J].
Gopalan, Aditya ;
Caramanis, Constantine ;
Shakkottai, Sanjay .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (01) :403-420
[5]   Indexability of Restless Bandit Problems and Optimality of Whittle Index for Dynamic Multichannel Access [J].
Liu, Keqin ;
Zhao, Qing .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (11) :5547-5567
[6]   A novel objects of interest extraction approach using attention-driven model for content-based image retrieval [J].
Lu, Yinghua ;
Zhang, Xiaohua ;
Kong, Jun ;
Wang, Xuefeng ;
Zhang, Jinbo .
CISP 2008: FIRST INTERNATIONAL CONGRESS ON IMAGE AND SIGNAL PROCESSING, VOL 1, PROCEEDINGS, 2008, :339-343
[7]   On the empirical state-action frequencies in Markov decision processes under general policies [J].
Mannor, S ;
Tsitsiklis, JN .
MATHEMATICS OF OPERATIONS RESEARCH, 2005, 30 (03) :545-561
[8]  
Neely M. J., 2011, PERFORM EVALUATION, DOI [10.1016/j.peva.2011.01.007, DOI 10.1016/J.PEVA.2011.01.007,2011]
[9]   Dynamic power allocation and routing for time-varying wireless networks [J].
Neely, MJ ;
Modiano, E ;
Rohrs, CE .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2005, 23 (01) :89-103
[10]  
Ouyang W., 2010, ARXIV10093959