• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >A Hypergraph Approach to Linear Network Coding in Multicast Networks
【24h】

A Hypergraph Approach to Linear Network Coding in Multicast Networks

机译：组播网络中线性网络编码的超图方法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. A typical scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose an approach to transforming the linear coding problem into a graph theory problem. By utilizing hypergraphs, we model the linear codes by constructing a pseudodual graph of the multicast network. Then, a valid linear code is equivalent to a cover in the pseudodual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, we propose several preprocessing algorithms to further reduce the computation time required by the iterative refinements by reducing the graph size before transformation. An important contribution of this work is that the proposed approach can be readily extended to solve many minimal network coding problems. By assigning different weights to edges, minimal network coding problems are reduced to the shortest path problem in the pseudodual graph. Our simulation results show that the proposed preprocessing algorithms can reduce the computation time by about 40-50 percent in a medium size multicast network compared to the scheme without preprocessing algorithms, and the throughput of the system with network coding is 25 percent higher than that with the traditional approach of multiple multicast trees.
机译：网络编码是路由的一种有希望的概括，它允许节点通过对接收到的消息进行编码来生成输出消息。网络编码提供独特优势的典型情况是多播网络，其中源节点生成消息，多个接收者收集消息。在多播网络中，线性网络代码由于其充分性和简单性而被优选。在本文中，我们提出了一种将线性编码问题转换为图论问题的方法。通过使用超图，我们通过构造多播网络的伪对偶图来对线性代码进行建模。然后，有效的线性代码等效于满足某些约束的伪对偶图中的覆盖。通过迭代改进，可以在多项式时间内找到合格的覆盖。此外，我们提出了几种预处理算法，以通过减少变换前的图形大小来进一步减少迭代细化所需的计算时间。这项工作的重要贡献是，可以很容易地将提出的方法扩展为解决许多最小的网络编码问题。通过为边缘分配不同的权重，将最小的网络编码问题减少为伪对偶图中的最短路径问题。仿真结果表明，与没有预处理算法的方案相比，该算法在中等规模的组播网络中可以减少40-50％的计算时间，采用网络编码的系统的吞吐量比采用预处理算法的系统的吞吐量高25％。多个多播树的传统方法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号