利用network coding的多速率多播最大吞吐量问题研究 on the optimal multi-rate throughput for multicast with network coding.pdfVIP

第12卷第3期 电路与系统学报 V01．12No．3 OF 2007年6月 JOURNALCIRCUITSANDSYSTeMS June，2007 文章编号：1007-0249(2007)03．0078-06 利用netWork coding的多速率多播最大吞吐量问题研究★ 张牧， 张顺颐， 刘伟彦 (南京邮电大学江苏省通信与网络技术工程研究中心，江苏南京2l0003) 摘要t本文研究了利用networkcoding的多速率多播最大吞吐量问题。与以往研究重点集中在单速率多播中的 network coding研究工作不同，本文考虑了链路的异构性问题并采用多速率多播来解决该问题。首先文中形式化地描 述了多速率多播最大可得吞吐量问题，并证明了在分层独立和层速率固定条件下，利用network coding的多速率多播 最大吞吐量问题是NP_hard类问题，同时给出了最大吞吐量的上界。此外本文同时也研究了分层相关和层速率可变情 况下的最大吞吐量问题。 关键词t多播；吞吐量；Networkcoding 中圈分类号。TP393 文献标识码tA 1 引言 在一个给定的网络中，求一个多播连接的最大吞吐量是图论中的一个经典问题。Menger【1】证明了 从发送者s到接收者f的单播连接的最大速率等于s与f之间的最小切，这也是图论中的最大流一最小 可以作为多播连接转发的节点。一棵以发送者为根节点，连接所有接收者的多播分发树称为Steiner 树。如果网络中存在Steiner节点，那么求整个多播组的最大吞吐量是Packing 是在网络中寻找能提供最大速率之和的多棵 Steiner树的集合，Jain【3J证明了这个问题是 NP-hard类问题。 Ahlswede【4J等人在2000年提出的network coding理论表明，传统多播网络中中间节点的复 制一转发式的传输方式不能最大限度地发挥网络 的性能。从网络信息流的角度看，网络中的任何 节点都可以对收到的数据信息进行编码操作，而 不仅限于简单的转发，与信源编码和信道编码相 对应，在网络的中间节点对收到的数据信息进行 (a)传统多播 (b)ne铆orkcoding 图1 发送者s发送口，6到接收者fl，如 编解码称为network coding。一个简单的network 个。而利用network 样f1和f2就可以同时恢复出口和6。 随着network coding理论的提出，将Networkcoding利用到多播网络中，可以提高多播传输的最 那么利用networkcoding，整个组也可以达到速率1，，也就是说networkcoding能够保证整个多播组的 +收稿日期·2006．06一19修订日期：2006．09．13 万方数据 张牧等：利用net、)lrork 79 第4期 coding的多速率多播最大吞吐量问题研究 进一步证明了利用线性netWork 法来找到线性network coding的解决办法。 现有的利用networkcoding的多播最大吞吐量研究工作都是建立在单速率多播的基础上的，即发 送者以相同的速率发送数据到所有接收者[8~101。然而，由于接收者可用带宽的异构性，比如拨号和局 域网用户，即使利用networkcoding，单速率多播的吞吐量依然受到可用带宽最差的接收者的限制， 整个多播组并不能获得最优吞吐量。因此用相同的速率发送数据到所有接收者是不公平的，而且效率 不高。 本文研究利用network 可以提供分层的数据，通过发送更