Capacity Regions of Two-Receiver Broadcast Erasure Channels With Feedback and Memory
Capacity Regions of Two-Receiver Broadcast Erasure Channels With Feedback and Memory
复制标题
带反馈和记忆的双接收机广播擦除通道的容量区域
DOI：
10.1109/tit.2018.2818736
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
Shirin Saeedi Bidokhti
中科院分区：
文献类型：
--
作者：
M. Heindlmaier;Shirin Saeedi Bidokhti
研究了具有反馈和记忆的双接收机广播包删除信道。内存建模使用有限状态马尔可夫链表示信道状态。考虑两种情形：1）当发射机具有信道状态的因果知识时（即，状态是可见的）和2）当信道状态在发射机处是未知的，但是通过反馈在发射机处可以获得对它的观测时（即，状态是隐藏的）。在这两种情况下，匹配的外部和内部的通信速率的界限推导和容量区域的确定。结果表明，类似的结果结转到信道的记忆和延迟反馈和无记忆复合信道的反馈。当状态可见时，容量区域具有单字母特征，并且是线性规划。设计了两种最佳编码方案，使用反馈来跟踪通过队列网络发送/接收的数据包：概率方案和确定性反压算法。前者仅根据过去的信道状态信息进行决策，后者遵循基于最大权值的策略。算法的性能进行了分析，使用队列网络中的速率稳定性，网络中的最大流最小割对偶和有限时域李雅普诺夫漂移分析的框架。当状态被隐藏时，容量区域不具有单字母特征，并且在这种意义上是不可计算的。提供了容量区域的近似，并概述了两种最佳编码算法。第一个算法是一个概率编码方案，其决策的基础上，过去的$L$的重复，其可达到的速率区域接近容量区域指数快速在$L$。第二种算法是一种类似反压的算法，从长远来看性能最佳。
The two-receiver broadcast packet erasure channel with feedback and memory is studied. Memory is modeled using a finite-state Markov chain representing a channel state. Two scenarios are considered: 1) when the transmitter has causal knowledge of the channel state (i.e., the state is visible) and 2) when the channel state is unknown at the transmitter, but observations of it are available at the transmitter through feedback (i.e., the state is hidden). In both scenarios, matching outer and inner bounds on the rates of communication are derived and the capacity region is determined. It is shown that similar results carry over to channels with memory and delayed feedback and memoryless compound channels with feedback. When the state is visible, the capacity region has a single-letter characterization and is in terms of a linear program. Two optimal coding schemes are devised that use feedback to keep track of the sent/received packets via a network of queues: a probabilistic scheme and a deterministic backpressure-like algorithm. The former bases its decisions solely on the past channel state information and the latter follows a max-weight queue-based policy. The performance of the algorithms is analyzed using the frameworks of rate stability in networks of queues, max-flow min-cut duality in networks, and finite-horizon Lyapunov drift analysis. When the state is hidden, the capacity region does not have a single-letter characterization and is, in this sense, uncomputable. Approximations of the capacity region are provided and two optimal coding algorithms are outlined. The first algorithm is a probabilistic coding scheme that bases its decisions on the past $L$ acknowledgments and its achievable rate region approaches the capacity region exponentially fast in $L$ . The second algorithm is a backpressure-like algorithm that performs optimally in the long run.