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

来源：计算机工程与应用杂志2018年第5期北京时间：

作者：刘宴涛1，刘 珩2

单位：1.渤海大学 工学院，辽宁 锦州 121013；2.北京理工大学 信息与电子学院，北京 100081

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

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