论文部分内容阅读
当前,随着多用户同时参与的多媒体应用的快速发展和广泛普及,多播成为Internet上越来越重要的多媒体内容分发技术。在多媒体多播会晤中,各接收节点可能具有不同的接收带宽,需要以不同速率接收数据,称为“网络异构性”。在单速率多播中,各接收节点只能以相同的速率接收数据,不能充分利用网络带宽。而在分层媒体多播中,源节点将多媒体数据编码成若干分层,各接收节点按照各自的接收带宽接收相应个数的分层,能够实现不同速率接收数据,充分利用了网络带宽。在存储与转发的数据传输方式中,网络的中间节点只完成数据的存储与转发,不进行其他的处理操作。网络编码是一种新的数据传输方式,其允许网络中间节点对接收的信息进行编码后再转发,然后接收节点将接收的编码包通过解码操作恢复为源节点的原始包。相比存储与转发的数据传输方式,网络编码能够显著地改善网络性能,如提高网络吞吐量、平衡网络负载等。近年来,许多相关工作表明将网络编码与分层编码相结合可以极大地提高具有网络异构性的多媒体多播应用的性能。本文研究了基于网络编码的分层媒体多播的相关问题,主要研究内容与贡献如下:(1)基于网络编码的分层媒体多播的层速率优化分配问题在分层媒体多播中,各分层速率的大小决定了网络吞吐量的大小。本文旨在最大化所有接收节点的接收速率总和的目标下,优化分配各层速率。由于该问题是一个非线性整数规划的问题,本文设计了一个层速率优化分配的高效启发式算法。该算法首先将网络图按接收节点的总数分解成子图,然后将这些子图按分层层数进行合并,在合并后的各子图中从源节点到各接收节点的最大流的最小值即是优化分配的各层速率大小。模拟实验表明本文的算法相比已有算法对网络吞吐量提高15%—18%,对各接收节点的平均带宽利用率改善6%—10%。(2)基于网络编码的分层媒体多播的最优延时控制问题由于带宽限制网络的多媒体分发应用对带宽和延时的要求越来越严格,因此支持服务质量保障成为多媒体应用研究的重要内容。本文研究了基于网络编码的分层媒体多播中路径带宽分配的有效策略,以确保多播会晤的各接收节点的带宽需求得以满足,并使得所有接收节点接收分层数据的延时最短。本文首先给出了该问题的数学模型,并证明了其是NP-hard问题,因此提出了一个多项式时间的启发式算法。模拟实验表明本文的算法能够在保证接收节点的带宽需求的同时,降低基于网络编码的分层媒体多播的延时。(3)基于网络编码的多会晤分层媒体多播的公平带宽分配问题当前网络中多媒体应用众多,网络中通常存在多个不同的多媒体多播会晤,为不同的用户群提供不同的服务。因此如何保证各会晤的接收节点公平地使用带宽资源成为多媒体应用的重要研究课题。本文研究基于网络编码的多会晤多播的词典序公平带宽分配问题,以使得各会晤的各接收节点能够公平地分享网络带宽。本文首先将该问题模型化为一个整数线性规划,然后设计了一个多项式时间的近似算法。该近似算法通过一系列的线性规划来得到整数线性规划最优解的近似解。针对每一分层,用贪心的方法,即通过解线性规划,使得该层对应的各会晤中尽量多的接收节点能够接收到该分层数据。模拟实验表明本文算法能够在不损失过多吞吐量的情况下使得各会晤的各接收节点公平地利用网络带宽资源,且带宽利用率高。