《不相交QoS路徑與斯坦納網路的近似算法研究》是依託福州大學，由郭龍坤擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：不相交QoS路徑與斯坦納網路的近似算法研究
- 依託單位：福州大學
- 項目類別：青年科學基金項目
- 項目負責人：郭龍坤
項目摘要,結題摘要,
項目摘要
隨著網路的發展，視頻套用日益增多，魯棒視頻流傳輸受到越來越多重視。為進行滿足服務質量 （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的真實網路的高效路由算法，以處理視頻傳輸等套用。
