圖嵌入方法及其在網路虛擬化中套用研究

《圖嵌入方法及其在網路虛擬化中套用研究》是依託華南師範大學，由陳衛東擔任項目負責人的面上項目。

基本介紹

• 中文名：圖嵌入方法及其在網路虛擬化中套用研究
• 項目類別：面上項目
• 項目負責人：陳衛東
• 依託單位：華南師範大學

項目摘要

網路虛擬化是當前計算領域的研究熱點,有廣闊的套用前景，其關鍵技術之一是圖嵌入方法，即將由實際需求抽象所得虛擬邏輯拓撲結構圖如何有效嵌入到基礎物理網路結構圖中的方法。本項目研究兩類圖嵌入方法。一類是基於Cayley圖和陪集圖的圖嵌入方法，研究其在對等網路中用於設計高對稱性的虛擬拓撲結構圖並獲得高效路由方法等虛擬化問題；也探討其如何有助於設計現實複雜網路有效路由方法。另一類是基於k-pairs不相交路徑的圖嵌入方法，研究其在基於Swapped互連規則的兩類組合網路作為物理網路結構圖時的虛擬拓撲設計以及容錯路由方面的套用。這些組合網路有優良特性因而有較好套用前景。這些圖嵌入方法充分利用圖結構對稱性來簡化一些網路虛擬化問題，其研究對深化和發展網路中的代數和圖論方法，對網路虛擬化技術深入廣泛套用有深刻意義。

結題摘要

圖嵌入方法是實現網路虛擬化的關鍵技術之一，它是將由實際需求抽象所得虛擬邏輯拓撲圖嵌入到基礎物理網路結構圖中的一類方法。本項目主要研究利用圖結構對稱性簡化某些網路虛擬化問題的圖嵌入方法。研究內容包括三個方面。第一，研究了複雜網路的點度呈冪率分布的形成機制，得出了複雜網路的度序列長度（即不同點度的個數）的一般性結論，即網路度序列長度是網路點數的對數的量級；根據該結論，利用基於代數圖論的圖嵌入方法，探究了一般複雜網路中的路由策略。此外，利用代數圖論Cayley圖方法，提出了路由和容錯性能良好的網路拓撲結構，並討論其作為結構化數據中心的網路模型等方面的套用。第二，研究了環、不相交路、支配集、連通支配集等典型拓撲結構在基於Swapped互連規則的兩類組合網路中的嵌入問題，較圓滿解決了Biswapped網路中的泛圈性問題（網路泛圈性即為網路中包含各種長度的環的特性），得出了這兩類組合網路中不相交路、支配集、連通支配集等問題的計算複雜性結論（均為NP難度問題），並給出近似求解算法。第三，研究了無線感測器網路、社交網路中的相關問題，包括非干擾不相交路徑、最小干擾連通拓撲在無線網路中的嵌入問題，給出了有效的求解算法；為社交網路的正影響支配集問題得出了一個改進的貪心近似算法等。在本項目研究結論中，複雜網路度序列長度的結論揭示了複雜網路的一個較為普遍的規律，可以作為一般複雜網路的一個新特性；所提出的基於圖嵌入的路由策略的研究方法、Biswapped網路中泛圈性等問題的研究方法具有一定通用性，適用於研究相關問題。 本項目執行期間取得的主要成果為公開發表了21篇學術論文，包括在國際SCI刊物上發表7篇（《Physica A》上2篇，《Information Sciences》，《The Computer Journal》，《Chaos》，《Journal of Applied Analysis and Computation》和《Journal of Communications and Networks》上各1篇），國內一級刊物《計算機學報》和《軟體學報》上各1篇，國際EI刊物《Journal of Interconnection Networks》上1篇。培養了碩士生10名，正在培養的碩士生5名；合作單位培養了博士生1名。