推荐星级：

均匀分数路由网络容量域分析

更新时间：2019-12-25 09:35:19 大小：1M 上传用户：守着阳光1985 查看TA发布的资源 标签：网络容量域 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

均匀分数路由网络是指网络边传输的数据包具有相同的维数,且该维数与信源消息的维数可以不同.已知分数路由网络的容量域是多维欧式空间中的多胞体,但对各种业务模式网络的容量域的计算尚缺乏有效的可操作方法.本文研究了三种业务模式的容量域计算方法:针对多重单播,提出了基于缩减图、合并缩减图和虚拟节点的方法;针对一重组播,提出了基于子树分解和组合设计的方法;针对二重混合网络,提出了基于凸多边形极点的方法.除了理论证明之外,还举了大量样例演示这些方法的正确性.

部分文件列表

文件名	大小
均匀分数路由网络容量域分析.pdf	1M

立即下载

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）

Vol． 46 No． 8

Aug． 2018

第

期

电

子

学

报

2018

ACTA ELECTRONICA SINICA

年

月

均匀分数路由网络容量域分析

，

刘宴涛刘珩

( 1.

，

渤海大学工学院辽宁锦州

121013; 2.

，

北京理工大学信息与电子学院北京

100081)

，

均匀分数路由网络是指网络边传输的数据包具有相同的维数且该维数与信源消息的维数可以不同

．

摘

要

，

已知分数路由网络的容量域是多维欧式空间中的多胞体但对各种业务模式网络的容量域的计算尚缺乏有效的可操

． : ，、

作方法本文研究了三种业务模式的容量域计算方法针对多重单播提出了基于缩减图合并缩减图和虚拟节点的方

; ， ; ，．

法针对一重组播提出了基于子树分解和组合设计的方法针对二重混合网络提出了基于凸多边形极点的方法除

，

了理论证明之外还举了大量样例演示这些方法的正确性

．

;

关键词

中图分类号

URL: http: / /www． ejournal． org． cn

分数路由容量域多胞体组合设计子树分解

TN915

: 0372-2112 ( 2018) 08-1876-08

DOI: 10． 3969 /j． issn． 0372-2112． 2018． 08． 011

文献标识码

文章编号

电子学报

Rate Region Analysis for Uniform Fractional Routing Networks

LIU Yan-tao ，LIU Heng

( 1. College of Engineering，Bohai University，Jinzhou，Liaoning 121013，China;

2. School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China)

Abstract: If packets are with identical dimensions，which may be different from the dimensions of source messa-

ges，the network is called uniform fractional routing network． The rate region of a fractional routing network is a polytope

in a multidimensional Euclidean space，but effective implementable methods are still missing to calculate the region for

networks with different traffic patterns． This paper studied rate region analysis methods for three traffic patterns: For multi-

ple unicasts，a method based on reduced graph，union reduced graph，and virtual node was proposed; For a single multi-

cast，it was based on subtree decomposition and combinatorial design; For a pattern mixed of two flows，the polygon region

was drawn by determining all extreme points． Correctness of these methods was proved in theory and illustrated by exam-

ples．

Key words: fractional routing; rate region; polytope; combinatorial design; subtree decomposition

，

的路由容量服从最大流最小割定理即网络能传输的

引言

，

最大流等于信源信宿间的最小割这被称为最小割限

．

，

网络容量是指网络能传输的最大信息率它度量

，

由于编码不能提高一重单播网络的吞吐量因此一重

，

了网络的最大传输能力是网络通信的一项关键指标

．

． 2000 ，Ahl-

年

单播网络的编码容量也等于最小割限

［1］

网络容量在网络信息论中的地位和作用可以比拟于信

swede

等

证明一重组播网络的编码容量等于信源信

，

道容量在香农信息论中的地位和作用计算网络容量

．

宿间最小割的最小值除了这三种由最小割限确定的

．

是网络信息论的一项基本任务当网络中包含多个业

，

容量域之外对于一重组播网络的路由容量域和各种

混合网络的路由容量域和编码容量域不存在像最小割

，．

务流时其传输能力由多维的容量域刻画分组网络从

、，

业务模式上分为单播组播和混合网络从传输机制上

、、．

限那样明确简单一般的结论这些网络的容量域受很

，

分为路由和编码网络对应的容量域分别被称为路由

，、、、

多因素的影响比如网络拓扑传输机制业务模式信

．

容量域和编码容量域从业务模式和传输机制的角度

，

源信宿的数目和位置等等因此对这些网络容量域需

1 ． :

对容量域的研究现状如表所示其中一重单播网络

．

要具体分析

: 2017-03-31;

: 2018-01-17; :

责任编辑蓝红杰

收稿日期

修回日期

基金项目国家自然基金

( No． 61471045) ;

( No． 20170540008)

辽宁省自然科学基金

1877

刘宴涛均匀分数路由网络容量域分析

第

期

表

分组网络的两种容量域

路由容量域

最小割限

．，

们并没有总结出这样的算法目前对路由容量域的分

．

析尚缺乏普适性和操作性高的方法

，

由于网络容量域的影响因素众多拓扑多种多样

业务传输模式

一重单播网络

一重组播网络

多重单播网络

编码容量域

最小割限

未解决

，

网络规模差异很大所以对网络容量域的分析一直是

未解决

．， 1

比较复杂的问题目前表中还有几种容量域没有被

未解决

，

解决图论和信息论等领域的理论学者和网络工程技

单播组播混合网络

未解决

术人员亟待一套有效方法来分析通信网络的传输性

，

从传输机制上看路由网络中非源节点的输出是

，，

能刻画网络的本质特征解决网络信息论的基本问题

．

，

其输入的子集编码网络中非源节点的输出是其输入

［5］［15］，，

本文受文献和启发讨论网络的路由容量域

．，

的线性函数因此对路由容量域和编码容量域的分析

提出分析路由容量域的具有一般性和可操作性的方

．

，Dougherty

方法有着根本不同在编码容量域方面

等通

进行了深入研究他们指出线性编

码对于达到诸如多重单播等非组播模式的编码容量是

，

法我们的研究扩展和完善了文献

［15］．

的工作

［2 ～ 5］

［2］

．

过一系列论文

网络模型与问题描述

［5］

．［3］，

不充分的文献研究了网络容量与字符集的关系

，

均匀分数网络是分组网络很恰当的模型该网

．［4］

证明有些网络的容量是不可达的文献提出了拟阵

G = ( V，E) ，V

络属于有向无环图

和

分别代表节点集

网络的概念并把非香农信息不等式应用于网络容量的

．，

和边集所有网络边是等容量的每条边最多只允许传

．［5］

计算文献把编码网络的可达容量域定义为有限维

，．

个符号故称之为均匀网络节点间允许存在重边

，

输

，

空间中的凸多面体并应用信息不等式计算了蝶形网

、Fano Fano Vámos

网络的编码容量

，．

在一次传输中每条边只允许使用一次消息符号集为

、

网络非

络

网络和

． h

有限字符集假设网络传输个独立的消息

X ，…，X ，

，

域但是文献

［5］

并没有总结出计算编码容量域的一般

1，

≥ 维数分别等于

k ，…，k ，n

k ，

可以不同但都取

和

［6］

． Yeung

方法

基于熵域 Γ 定义了多源编码网络的可

．，［5］

自整数基于该模型文献定义分数码和容量域

，

达容量域但由于多于三个变量的 Γ 的特征尚未知

，

．

如下

［7］

定义分数码

) : ( k ，…，k ，n)

分数码由一组边函

． Thakor

该定义缺乏计算的可操作性

采用函数相关图

，

数和译码函数构成中间节点应用边函数把输入的

维

，

的方法通过寻找最大不可约集建立网络随机变量的

n ，

数据包映射为输出的维数据包信宿节点应用译码函

、，

熵条件熵和互信息等测度需要满足的不等式从而得

［8，9］

n ．

数把收到的维数据包映射为该节点订购的消息如果

． Li

到编码容量域的外限

到非同构网络的编码容量域研究中提出了一种基于

Shannon

等

把计算机辅助工具引入

，

这些函数的输出是输入的线性组合则称该码为分数

，

; ，

线性码如果输出拷贝自一部分输入符号则称其为分

．

外限和几种线性码内限进一

枚举的方法计算

［10］

;

数路由如果某分数码能够满足所有信宿节点的订购

，

步他们基于群变换把不同的网络编码问题划分为

，

需求则称该码是可达的

．

若干等价类并提出算法计算少于五个源节点的小型网

［11］

2( ) :

定义容量域对于

( k ，…，k ，n)

，

分数码定义

． Apte

络的编码容量域

等

应用对称性把多源多宿编

，

码网络划分为网络对称群将其与多面体对称群相关

r = ( r ，…，r ) = ( ，…， )

( 1)

，

联并应用多面体计算中使用的对称性方法来降低对

，

为信息率矢量全部可达的信息率矢量构成的区域

称

．

编码容量域分析的复杂度

［12］

．

称为该分数码的容量域

，Yazdi

在路由容量域方面

提出了不等式消去技

， r

只取值于整数所以信息率一

由于规定

和

Japanese

术来缓解应用

定理求解多商品流容量域复杂

［13］

，

定是有理数且满足如下线性不等式组

．

度过高的问题黄佳庆基于上行链路共享模型讨论

0，…，r

≥

( 2)

( 3)

≥

P2P

，

文件共享网络的编码容量和路由容量并证明

了

［14］

a r + a r + … + a r

≤

． Liang

二者的理论上界是一致的

把组播路由建模为

…

两个参与者以网络边和组播树为策略集的混合策略博

a r + a r + … + a r b

≤

h l

( 4)

，，

弈通过计算该博弈可得组播路由容量这种博弈论思

( 2)

， ( 3) ～ ( 4)

是显然的式

、

则取决于网络拓扑业务

，

想为容量域研究提供了有益的思路但在实际应用中

，

式

、．

模式信源信宿的数目和位置等因素根据式

( 2) ～

* ，

需要建立的收益矩阵的维数等于边数组播树数即

( 4) ， r ， 0 r' r r' ，

如果可达则满足 ≤ ≤ 的一定可达因此

，

使对于很多小规模的网络该矩阵也是非常庞大的

．

［15］

．， ( 2) ～ ( 4)

分数码的容量域是凸集此外式

Cannons

，

证明路由容量域是可计算的并通过对样

中各个不等

等

h ，

式分别对应着维欧式空间中的一个半空间根据凸集

，

例网络的分析指出存在计算路由容量域的算法但他

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

均匀分数路由网络容量域分析

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页