基于子树分解的分数组播路由网络容量分析

摘要：

网络容量度量了网络的最大信息传输率,计算网络容量是网络信息论的基本任务.网络容量可以分为编码容量和路由容量,一重组播网络的编码容量已被证明等于信源和各个信宿之间最小割的最小值,但路由容量却由于受到网络拓扑、信源信宿的数目和位置等因素的影响不存在这样简单和一般化的结论,对具体网络需要做出具体分析.组播路由网络容量分析可建模为Packing Steiner Trees问题,但该问题是NP-hard的,目前尚缺乏计算组播路由网络容量的有效方法.讨论分数组播路由网络的容量分析问题,分数网络的信源消息和边容量都是整数维的,在这个范畴内,把组播路由网络的容量分析建模为组合设计问题并提出一种方法加以解决,该方法的关键点在于通过子树分解技术大大缩减了网络规模,由此降低了组合设计的复杂度,并通过对三层网络的分析演示了该方法的使用.

关键词：网络容量、组播、子树分解、组合设计

所属期刊栏目：54

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金61471045;辽宁省自然科学基金20170540008

在线出版日期：2018-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：7-13