Optimal Design of Sequential Real-Time Communication Systems

被引:57
作者
Mahajan, Aditya [1 ]
Teneketzis, Demosthenis [1 ]
机构
[1] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA
关键词
Dynamic teams; information states; joint source-channel coding; nonclassical information structures; real-time communication; zero-delay communication; INDIVIDUAL SEQUENCES; DELAY; FEEDBACK; CHANNEL; POMDPS;
D O I
10.1109/TIT.2009.2030462
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Optimal design of sequential real-time communication of a Markov source over a noisy channel is investigated. In such a system, the delay between the source output and its reconstruction at the receiver should equal a fixed prespecified amount. An optimal communication strategy must minimize the total expected symbol-by-symbol distortion between the source output and its reconstruction. Design techniques or performance bounds for such real-time communication systems are unknown. In this paper a systematic methodology, based on the concepts of information structures and information states, to search for an optimal real-time communication strategy is presented. This methodology trades off complexity in communication length (linear in contrast to doubly exponential) with complexity in alphabet sizes (doubly exponential in contrast to exponential). As the communication length is usually order of magnitudes bigger than the alphabet sizes, the proposed methodology simplifies the search for an optimal communication strategy. In spite of this simplification, the resultant optimality equations cannot be solved efficiently using existing algorithmic techniques. The main idea is to formulate a zero-delay communication problem as a dynamic team with nonclassical information structure. Then, an appropriate choice of information states converts the dynamic team problem into a centralized stochastic control problem in function space. Thereafter, Markov decision theory is used to derive nested optimality equations for choosing an optimal design. For infinite horizon problems, these optimality equations give rise to a fixed point functional equation. Communication systems with fixed finite delay constraint, a higher-order Markov source, and channels with memory are treated in the same manner after an appropriate expansion of the state space. Thus, this paper presents a comprehensive methodology to study different variations of real-time communication.
引用
收藏
页码:5317 / 5338
页数:22
相关论文
共 60 条
[1]   DISCRETE-TIME CONTROLLED MARKOV-PROCESSES WITH AVERAGE COST CRITERION - A SURVEY [J].
ARAPOSTATHIS, A ;
BORKAR, VS ;
FERNANDEZGAUCHERAND, E ;
GHOSH, MK ;
MARCUS, SI .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1993, 31 (02) :282-344
[2]   AGREEING TO DISAGREE [J].
AUMANN, RJ .
ANNALS OF STATISTICS, 1976, 4 (06) :1236-1239
[3]   SIMULTANEOUS DESIGN OF MEASUREMENT AND CONTROL STRATEGIES FOR STOCHASTIC-SYSTEMS WITH FEEDBACK [J].
BANSAL, R ;
BASAR, T .
AUTOMATICA, 1989, 25 (05) :679-694
[4]   OPTIMUM DESIGN OF MEASUREMENT CHANNELS AND CONTROL POLICIES FOR LINEAR-QUADRATIC STOCHASTIC-SYSTEMS [J].
BASAR, T ;
BANSAL, R .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 73 (02) :226-236
[5]  
Bernstein D.S., 2000, P 16 C UNC ART INT, P32
[6]   Optimal sequential vector quantization of Markov sources [J].
Borkar, VS ;
Mitter, SK ;
Tatikonda, S .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2001, 40 (01) :135-148
[7]   Parametric POMDPs for planning in continuous state spaces [J].
Brooks, Alex ;
Makarenko, Alexei ;
Williams, Stefan ;
Durrant-Whyte, Hugh .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2006, 54 (11) :887-897
[8]  
BRUNSKILL E, 2008, P 10 INT S ART INT M
[9]   NOTE ON OBSERVATION OF A MARKOV SOURCE THROUGH A NOISY CHANNEL [J].
DEVORE, JL .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1974, 20 (06) :762-764
[10]  
Drake A. W., 1962, Observation of a Markov process through a noisy channel