不相交QoS路径与斯坦纳网络的近似算法研究

Since video applications are growing along with the development of networks, robust video streaming is attracting more and more research interest. To meet the quality of service (QoS) requirements for robust video unicast and multicast, this project will investigate efficient method for constructing disjoint QoS paths and Steiner networks. First, this project will design efficient approximation algorithms for the disjoint QoS path problem, with approximation ratio and time complexity better than the known best results. Meanwhile this project will investigate the inapproximability of the disjoint QoS path problem and analyze the theoretically best approximation ratio. Secondly, based on our previous approximation algorithms for the 2,3-connected Steiner network problem and combining together with the k disjoint shortest paths algorithm, this project will design an efficient approximation algorithm for k-edge connectivity minimum Steiner network, and then improve the known best approximation ratio for the k-vertex connected Steiner network problem. Finally, this project will combine the method for constructing disjoint QoS paths and k-connected Steiner networks to obtain efficient approximation algorithms for the minimum QoS Steiner network problem. This project is interdisciplinary and involving both computer science and mathematics. These approximation algorithms investigated above are with theoretical significance, and could be used to improve the video transmission in current networks immediately and hence has great practical value.

随着网络的发展，视频应用日益增多，鲁棒视频流传输受到越来越多重视。为进行满足服务质量 (QoS）要求的鲁棒视频单播与多播，本课题拟研究不相交QoS路径与斯坦纳网络的高效构造方法。首先，本研究拟设计不相交QoS 路径的高效近似算法，其预期近似比与时间复杂度都优于当前最好结果；同时拟证明不相交QoS路径的不可近似性，从理论上分析可达到的最佳近似比。其次，基于申请人之前的2,3连通斯坦纳网络的近似算法成果，本研究将结合k不相交路径算法，设计k边连通最小斯坦纳网络的高效近似算法，并改进k点连通斯坦纳网络的近似比。最后，本研究将融合不相交QoS路径与k连通斯坦纳网络的近似算法，设计满足QoS约束的最小斯坦纳网络的高效近似算法。本项目处于计算机科学与数学的交叉领域，所研究的上述问题的近似算法不但具有重要的理论意义，而且可以直接用来改良当前网络中的视频传输方法，具有较大的实用价值。

本项目设计了带服务质量(Quality of Service，QoS)的不相交路径问题与QoS斯坦纳网络问题理论上可行的高效近似算法。在不相交QoS路径问题中，针对k不相交的双约束路径(k-disjoint bi-constrained path, kBCP)设计了一个基于辅助层图构造方法的改进消圈算法，从而将kBCP问题转换为层图中的圈构造问题，并基于此设计了kBCP问题的近似比为O(1+r, 1+ln(1/r))的双因子近似算法，改进了之前的最好近似比O(1+r, 1+1/r)。针对k不相交的受限最短路径问题(k-disjoint constrained shortest path, kCSP)，设计了一个线性规划取整算法，得到一个伪近似比(pseudo approximation ratio)为(r, 2-r)的近似算法，其中r∈[0, 2]；并进一步设计了一个近似比为O(ln n)的单因子近似算法。提出了一个改良的消圈算法，允许图中每条边有双权值并且图中可存在负圈。该消圈算法可将kBCP问题与kCSP问题的近似比进步至(1+ε, 2+ε)，但缺点是时间复杂度较高。在QoS斯坦纳网络问题中，本项目集中研究k=1时的情况。当QoS约束为cost与delay时，基于辅助图构造技术，本项目设计了一个近似比为(1+ε)参数近似算法，其缺点亦为较高的时间复杂度。针对线性相关的cost与delay，本项目提出了一个折衷cost与delay的近似算法，近似比为(r, 1.39+2.78/(r-1))。当QoS约束为cost与energy时，本项目设计了一个近似比为(2，2+ε)的双因子近似算法。由于最短路径问题与斯坦纳树问题是计算机科学中的两个重要基础问题，QoS不相交路径与QoS斯坦纳网络问题作为更一般的问题模型，其近似算法研究与计算复杂性分析显然有良好的理论价值。在应用方面由于软件定义网络(Software Defined Networking, SDN)的发展，QoS不相交路径由于其数据传输的低拥塞与负载均衡的优势，渐渐得到了计算机科学家与工业界的关注。本项目所设计的QoS不相交路径及QoS斯坦纳网络的近似算法，虽主要为理论算法，但预期可用于辅助设计可部署于基于SDN的真实网络的高效路由算法，以处理视频传输等应用。