无线删除网的容量-Capacity of Wireless Erasure Networks

1、无线删除网的容量无线删除网的容量Capacity of Wireless Erasure NetworksR. Gowaikar, A. F. Dana. R Palanki. B. Hassibi and M. Effros, Capacity of wireless erasure networks, IEEE Trans. Inform. Theory, March 2006, 52(3), 789-804.无线删除网的容量无线删除网的容量一种特殊的无线通信网无线删除网得到了在一定条件下无线删除网的容量证明线性编码能够获得容量区域分析几个不同的编码方法的性能1研究背景研究准备网络模型问题

2、描述主要结论定理证明线性编码讨论总结展望无线删除网的容量无线删除网的容量2研究背景研究背景目标：确定一般多端网络的容量区域 1提出了一个容量区域，它的外边界完美符合最小割理论。 存在问题：这个边界不够“紧”。 最小割理论：信息流通过任何割的速率小于相应的割容量。 割：把一个网络分成两部分的一种分割。 割容量：割的两边的节点完全协调时能获得的最大速率。1 T. M. Cover and J. A. Thomas, Elements of Information Theory. New York: Wiley, 1991.3研究背景研究背景目标：确定一般多端网络的容量区域 论文3-5研究了有线网络

3、的组播问题，可以得到符合最大流最小割的容量区域的外边界。 组播问题：由一个或多个源节点，多个目的端节点，中继节点和节点间直接通信的信道组成的通信问题。3 R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 12041216, Jul 2000.4 S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Trans. Inf

4、. Theory, vol. 49, no. 2, pp. 371381, Feb. 2003.5 R. Koetter and M. Mdard, “An algebraic approach to network coding,” IEEE/ACM Trans. Netw., vol. 11, no. 5, pp. 782795, Oct. 2003.4研究背景研究背景目标：确定一般多端网络的容量区域 结论：最大可达速率是所有将源节点和目的节点分开的割的割流量中的最小值。 割流量：对于有线网，割流量等于所有穿过割的信道的容量的和。5研究背景研究背景目标：确定一般多端网络的容量区域 无线通信

5、：通信媒介是共享的广播和干扰。 无线网中的所有传输都是广播。 任何用户间的通信可以对其他节点间的通信产生干扰。 有这些特征的无线通信网的容量区域还不知道。6研究背景研究背景本文研究一种特殊的无线网络无线删除网 节点之间通过可能相关的无记忆删除信道连接； 每个节点向其所有输出信道发送同样的信息（无线环境的广播性质）； 假设在接收的时候使用没有干扰的多路接入模型（TDMA，FDMA，CDMA）； 目的端能获得所有关于每条链路上的删除位置的边信息。 无线删除网：由删除信道构成，删除信道是指在信道中传输的内容要么无误接收，要么被删除。7研究背景研究背景本文研究一种特殊的无线网络无线删除网 主要结论：

6、一种符合最大流最小割的结果适用于此无线删除网的组播问题。 线性编码能够使容量达到容量区域中的所有点。8研究准备研究准备9研究准备研究准备10网络模型网络模型11网络模型网络模型12网络模型网络模型组播问题 多源|多终端组播：每个目的端需要获得所有的信息源 ：源节点集合，假设每个源节点产生独立同分布的等概率分布随机过程消息。 ：目的节点集合。 ：不一定是空集，一个节点既可以是一个信息源的目的节点，也可以是另一个的源节点，目的节点也可以作为其他目的节点的中继节点。13网络模型网络模型14网络模型网络模型割容量 s-d割：由 表示，定义： 割容量：15网络模型网络模型割容量 例：网络如图，则割容量为

7、：16问题描述问题描述17问题描述问题描述18问题描述问题描述19主要结论主要结论20主要结论主要结论21主要结论主要结论定理2 例： 容量区域是：22主要结论主要结论23主要结论主要结论定理4 考虑多源多目的的组播问题，线性分组码能够使网络获得定理3定义的容量区域 中的任何速率向量24定理证明定理证明25定理证明定理证明定理1和2的证明 可达性：即证明当速率向量 满足定理1和2描述的容量区域内时，网络错误译码概率可以无限接近0 为证明可达性，设计一种编码和译码过程，使速率可达26定理证明定理证明27定理证明定理证明28定理证明定理证明29线性编码线性编码 从源到目的端的等价转换函数是线性的

8、优势：译码过程更简单码长为n的线性分组编码策略 ：消息集合，消息之间是等概独立的 ： ，用位二进制表示 的值 编码操作：每个节点i生成一个随机二进制矩阵 ，矩阵为 阶（，若i表示信息源）。若节点i收到且需要发送的消息是 ，则它发出的信息为30线性编码线性编码31线性编码线性编码线性编码的可达性 线性编码的错误译码概率和前面随机编码的错误译码概率表达式相同，所以线性编码足够使速率向量满足容量区域。32讨论讨论包的大小和环 本文的结果对任何的包长度都适用，文章定理给出的最大可达速率的单位是包，假设每个包长为Lbits，则用L乘以定理中的容量可以得到单位是bits的最大可达速率 本文假设的是无环网，

9、容量定理同样适用于有环的情况33讨论讨论目的节点的边信息 每次分组编码后，有 个包在网络上传输，所以网络链路上的删除位置可以用 bits表示，可以用每个包的一部分作为头部来传输这个信息。如果相对于网络的大小 ，包长L很大，则包中的边信息产生的开销可以忽略。34讨论讨论无边信息的可达速率 当目的端不能获得边信息时，研究单源|单目的无线删除网在几种编码方法下的可达速率35讨论讨论无边信息的可达速率 “转移”和“译码”方法：源节点对信息进行编码，所有其他节点进行下面操作中的一种： 转移：节点不改变接收到的序列，进行转移 译码和重编码：节点对源节点发送的信息进行译码，再进行编码发送，此时中继节点对其他

10、节点来说相当于信息源 仅使用“译码”操作时情况下，本文的无线删除网的最大速率等于网络中链路的最小容量： 为了获得最优速率，允许使用“转移”操作，此时最大速率为36讨论讨论无边信息的可达速率 分块马尔科夫叠加编码：10对单中继信道发展了一种基于马尔科夫编码和随机分割的编码方法，这种方法在1112中被推广到多中继的情况 这种编码方法下的最大可达速率是：10 T. M. Cover and A. A. El Gamal, “Capacity theorems for the relay channel,” IEEE Trans. Inf. Theory, vol. IT-25, no. 5, pp.

11、 572584, Sep. 1979.11 L.-L. Xie and P. R. Kumar, “An achievable rate for multiple level relay channel,” IEEE Trans. Inf. Theory, vol. 51, no. 4, pp. 13481358, Apr. 2005.12 G. Kramer, M. Gastpar, and P. Gupta, “Cooperative strategies and capacity theorems for relay networks,” IEEE Trans. Inf. Theory, vol. 51, no. 9, pp. 30373063, Sep. 2005.37讨论讨论无边信息的可达速率 一个简单的例子 Slepian-Wolf编码方法：中继节点编码并压缩收到的信号，并把它可靠的传输给目的节点 其中 ，当 很大时，有 =0.38讨论讨论无边信息的可达速率 几种方法在4种不同条件下