论文部分内容阅读
在科学技术蓬勃发展的基础上,全球信息化的建设不断深入和完善,网络给世界带来了巨大变化。现如今出现各种新型网络应用,网络用户也骤增,使得现有的网络资源异常紧张。怎么样充分利用网络资源,深度优化网络,成为迫切需要解决的问题。网络编码作为一种新型的数据传输技术,不仅能够在网络的中间节点对信息进行存储和转发,还能进行编码。网络编码可以有效改善网络性能,提高网络的吞吐量、均衡网络负载、降低节点的能耗和增强网络的健壮性等,但是由于在节点处进行编解码,增加了传输时延和计算复杂度。目前,单信源求和网络的网络编码容量以及线性网络编码算法的研究已经取得了一些突出成果。但在信源和信宿数量较多的网络中,网络编码容量与最小割以及可达速率的关系并不充分。除此之外,已有算法中判断全局编码向量线性无关需要耗费大量的时间,增加了算法的复杂度,而且大多数都是理论分析。鉴于上述问题,本文研究与分析求和网络的网络编码容量和线性网络编码算法。考虑m信源和n信宿的有向无环求和网络,规定网络中的边均为单位容量边,每个信源节点产生独立且同分布的消息,每个信宿节点都需要恢复出信源节点产生的信息的和,在网络的中间节点处能够进行网络编码的相关运算。本文主要工作如下:(1)针对多信源多信宿求和网络,研究其网络编码容量。已经证明,网络的网络编码容量的上限是网络的最小割界。本文首先对m信源和n信宿求和网络的网络编码容量下界进行分析。接着给出了满足min{m,n}=3的求和网络的网络编码容量的一个下界,并给出一个割为2的三信源三信宿求和网络的网络编码容量值及其证明。(2)针对三信源三信宿求和网络,我们给出了一种简单网络编码方式,先对网络进行分解(假设网络的中间节点的最大度不超过3),按网络节点连接的源宿数不同,将节点分为(3,3)、(3,2)、(2,3)和其他四种类型,分别给出它们的贪婪编码选取方式,再对信宿接收到的信息算术求和。接着用归纳法给出该编码传输方式从信源信宿间的路径角度的可行性分析。(3)利用图论中的最短路径算法,对线性网络编码算法进行深入研究和分析,提出了一种基于最短路径的线性网络编码多播算法。算法在信源处引入虚拟节点,将多源网络转化为单源网络,然后采用Dijkstra算法,并在Dijkstra约简网络中选取从信源到信宿的最短路径,简化全局编码向量的求取过程,保证信宿接收来自信源的消息,并准确进行解码。最后,通过仿真分析了算法性能,表明该算法在减少节点的能耗和均衡网络负载方面的优越性。