积分商城

最新搜索： MDK 万用表 B码 hr9111105 52832SDK OV2640
您现在的位置是：首页 > 技术资料 > 均匀分数路由网络容量域分析
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

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

资料介绍

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


部分文件列表

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

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

部分页面预览

（完整内容请下载后查看）
8
Vol． 46 No． 8  
Aug． 2018  
第
期
电
子
学
报
2018  
8
ACTA ELECTRONICA SINICA  
年
月
均匀分数路由网络容量域分析  
1
2
，
刘宴涛 刘 珩  
( 1.  
，
渤海大学工学院 辽宁锦州  
121013; 2.  
，
北京理工大学信息与电子学院 北京  
100081)  
:
，
均匀分数路由网络是指网络边传输的数据包具有相同的维数 且该维数与信源消息的维数可以不同  
．
摘
要
，
已知分数路由网络的容量域是多维欧式空间中的多胞体 但对各种业务模式网络的容量域的计算尚缺乏有效的可操  
． : ， 、  
作方法 本文研究了三种业务模式的容量域计算方法 针对多重单播 提出了基于缩减图 合并缩减图和虚拟节点的方  
; ， ; ， ．  
法 针对一重组播 提出了基于子树分解和组合设计的方法 针对二重混合网络 提出了基于凸多边形极点的方法 除  
，
了理论证明之外 还举了大量样例演示这些方法的正确性  
．
:
;
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
分数路由 容量域 多胞体 组合设计 子树分解  
:
TN915  
:
A
: 0372-2112 ( 2018) 08-1876-08  
DOI: 10． 3969 /j． issn． 0372-2112． 2018． 08． 011  
文献标识码  
文章编号  
电子学报  
Rate Region Analysis for Uniform Fractional Routing Networks  
1
2
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  
，
的路由容量服从最大流最小割定理 即网络能传输的  
1
引言  
，
最大流等于信源信宿间的最小割 这被称为最小割限  
．
，
网络容量是指网络能传输的最大信息率 它度量  
，
由于编码不能提高一重单播网络的吞吐量 因此一重  
，
了网络的最大传输能力 是网络通信的一项关键指标  
．
． 2000 ，Ahl-  
年
单播网络的编码容量也等于最小割限  
［1］  
网络容量在网络信息论中的地位和作用可以比拟于信  
swede  
等
证明一重组播网络的编码容量等于信源信  
，
道容量在香农信息论中的地位和作用 计算网络容量  
．
宿间最小割的最小值 除了这三种由最小割限确定的  
．
是网络信息论的一项基本任务 当网络中包含多个业  
，
容量域之外 对于一重组播网络的路由容量域和各种  
混合网络的路由容量域和编码容量域不存在像最小割  
， ．  
务流时 其传输能力由多维的容量域刻画 分组网络从  
、 ，  
业务模式上分为单播 组播和混合网络 从传输机制上  
、 、 ．  
限那样明确 简单 一般的结论 这些网络的容量域受很  
，
分为路由和编码网络 对应的容量域分别被称为路由  
， 、 、 、  
多因素的影响 比如网络拓扑 传输机制 业务模式 信  
．
容量域和编码容量域 从业务模式和传输机制的角度  
，
，
源信宿的数目和位置等等 因此对这些网络容量域需  
1 ． :  
对容量域的研究现状如表 所示 其中 一重单播网络  
．
要具体分析  
: 2017-03-31;  
: 2018-01-17; :  
责任编辑 蓝红杰  
收稿日期  
修回日期  
:
基金项目 国家自然基金  
( No． 61471045) ;  
( No． 20170540008)  
辽宁省自然科学基金  
1877  
8
:
刘宴涛 均匀分数路由网络容量域分析  
第
期
1
表
分组网络的两种容量域  
路由容量域  
最小割限  
． ，  
们并没有总结出这样的算法 目前 对路由容量域的分  
．
析尚缺乏普适性和操作性高的方法  
，
由于网络容量域的影响因素众多 拓扑多种多样  
业务传输模式  
一重单播网络  
一重组播网络  
多重单播网络  
编码容量域  
最小割限  
最小割限  
未解决  
，
，
网络规模差异很大 所以对网络容量域的分析一直是  
未解决  
． ， 1  
比较复杂的问题 目前 表 中还有几种容量域没有被  
未解决  
，
解决 图论和信息论等领域的理论学者和网络工程技  
单播组播混合网络  
未解决  
未解决  
术人员亟待一套有效方法来分析通信网络的传输性  
，
从传输机制上看 路由网络中非源节点的输出是  
， ，  
能 刻画网络的本质特征 解决网络信息论的基本问题  
．
，
其输入的子集 编码网络中非源节点的输出是其输入  
［5］ ［15］ ， ，  
本文受文献 和 启发 讨论网络的路由容量域  
． ，  
的线性函数 因此 对路由容量域和编码容量域的分析  
提出分析路由容量域的具有一般性和可操作性的方  
．
，Dougherty  
方法有着根本不同 在编码容量域方面  
等通  
进行了深入研究 他们 指出线性编  
码对于达到诸如多重单播等非组播模式的编码容量是  
，
法 我们的研究扩展和完善了文献  
［15］ ．  
的工作  
［2 ～ 5］  
［2］  
．
过一系列论文  
2
网络模型与问题描述  
［5］  
． ［3］ ，  
不充分的 文献 研究了网络容量与字符集的关系  
，
均匀分数网络 是分组网络很恰当的模型 该网  
． ［4］  
证明有些网络的容量是不可达的 文献 提出了拟阵  
G = ( V，E) ，V  
E
络属于有向无环图  
和
分别代表节点集  
网络的概念并把非香农信息不等式应用于网络容量的  
． ，  
和边集 所有网络边是等容量的 每条边最多只允许传  
． ［5］  
计算 文献 把编码网络的可达容量域定义为有限维  
n
， ．  
个符号 故称之为均匀网络 节点间允许存在重边  
，
输
，
空间中的凸多面体 并应用信息不等式计算了蝶形网  
、Fano Fano Vámos  
网络的编码容量  
， ．  
在一次传输中 每条边只允许使用一次 消息符号集为  
、
网络 非  
络
网络和  
． h  
有限字符集 假设网络传输 个独立的消息  
X ，…，X ，  
h
1
，
域 但是文献  
［5］  
并没有总结出计算编码容量域的一般  
h
1，  
≥ 维数分别等于  
k ，…，k ，n  
h
k ，  
可以不同 但都取  
i
和
1
［6］  
*
． Yeung  
方法  
基于熵域 Γ 定义了多源编码网络的可  
N
． ， ［5］  
自整数 基于该模型 文献 定义分数码和容量域  
*
，
达容量域 但由于多于三个变量的 Γ 的特征尚未知  
N
，
．
如下  
［7］  
1(  
定义 分数码  
) : ( k ，…，k ，n)  
分数码由一组边函  
h
． Thakor  
该定义缺乏计算的可操作性  
采用函数相关图  
1
，
数和译码函数构成 中间节点应用边函数把输入的  
n
维
，
的方法 通过寻找最大不可约集建立网络随机变量的  
n ，  
数据包映射为输出的 维数据包 信宿节点应用译码函  
、 ，  
熵 条件熵和互信息等测度需要满足的不等式 从而得  
［8，9］  
n ．  
数把收到的 维数据包映射为该节点订购的消息 如果  
． Li  
到编码容量域的外限  
到非同构网络的编码容量域研究中 提出了一种基于  
Shannon  
等
把计算机辅助工具引入  
，
这些函数的输出是输入的线性组合 则称该码为分数  
，
; ，  
线性码 如果输出拷贝自一部分输入符号 则称其为分  
．
外限和几种线性码内限 进一  
枚举的方法计算  
［10］  
;
数路由 如果某分数码能够满足所有信宿节点的订购  
，
步 他们 基于群变换把不同的网络编码问题划分为  
，
需求 则称该码是可达的  
．
若干等价类并提出算法计算少于五个源节点的小型网  
［11］  
2( ) :  
定义 容量域 对于  
( k ，…，k ，n)  
h
，
分数码 定义  
． Apte  
络的编码容量域  
等
应用对称性把多源多宿编  
1
k
k
，
码网络划分为网络对称群 将其与多面体对称群相关  
1
h
r = ( r ，…，r ) = ( ，…， )  
h
n
( 1)  
1
n
，
联 并应用多面体计算中使用的对称性方法来降低对  
r
，
为信息率矢量 全部可达的信息率矢量构成的区域  
称
．
编码容量域分析的复杂度  
［12］  
．
称为该分数码的容量域  
，Yazdi  
在路由容量域方面  
提出了不等式消去技  
k
n
， r  
只取值于整数 所以信息率 一  
i
由于规定  
和
Japanese  
术来缓解应用  
定理求解多商品流容量域复杂  
i
［13］  
，
定是有理数 且满足如下线性不等式组  
．
．
度过高的问题 黄佳庆 基于上行链路共享模型讨论  
r
0，…，r  
0
≥
( 2)  
( 3)  
≥
P2P  
，
文件共享网络的编码容量和路由容量 并证明  
了
1
h
［14］  
a r + a r + … + a r  
2
b
≤
1
． Liang  
二者的理论上界是一致的  
把组播路由建模为  
11  
1
12  
1h  
h
…
两个参与者以网络边和组播树为策略集的混合策略博  
a r + a r + … + a r b  
≤
h l  
( 4)  
， ，  
弈 通过计算该博弈可得组播路由容量 这种博弈论思  
l1  
1
l2  
2
lh  
( 2)  
， ( 3) ～ ( 4)  
是显然的 式  
、
则取决于网络拓扑 业务  
，
想为容量域研究提供了有益的思路 但在实际应用中  
，
式
、 ．  
模式 信源信宿的数目和位置等因素 根据式  
( 2) ～  
* ，  
需要建立的收益矩阵的维数等于边数 组播树数 即  
( 4) ， r ， 0 r' r r' ，  
如果 可达 则满足 ≤ ≤ 的 一定可达 因此  
，
使对于很多小规模的网络 该矩阵也是非常庞大的  
．
［15］  
． ， ( 2) ～ ( 4)  
分数码的容量域是凸集 此外 式  
Cannons  
，
证明路由容量域是可计算的 并通过对样  
中各个不等  
等
h ，  
式分别对应着 维欧式空间中的一个半空间 根据凸集  
，
例网络的分析指出存在计算路由容量域的算法 但他  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

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

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号