《網路可靠性及其最佳化的研究》是依託中國科學技術大學，由呂敏擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：網路可靠性及其最佳化的研究
- 項目類別：青年科學基金項目
- 項目負責人：呂敏
- 依託單位：中國科學技術大學
中文摘要,結題摘要,
中文摘要
網路的可靠性是衡量網路性能的重要方面，從而成為網路設計和分析必須考慮的重要因素之一。我們通常用一個連通的無向圖或強連通有向圖G=(V,E)作為網路的拓撲結構，圖的連通度是度量網路可靠性的重要參數，它表明對應的網路可以容許多少個結點或多少條信息傳輸信道同時發生故障仍能保證剩餘子網路中各結點之間的正常通信。. 為了克服傳統連通度在度量網路性能方面的缺陷，本項目研究能更精確度量網路實時可靠性的重要參數- - - - 條件連通度。該參數自上世紀八十年代提出以後，獲得了計算機和數學科學理論工作者的廣泛關注和研究興趣。我們主要從組合論的角度，利用圖論工具，對這個參數進行研究和最佳化：1. 研究文獻中較少涉及到的有向網路的條件連通度；2. 刻劃其達到最優值的條件；3. 將理論結果套用到網路可靠性的最佳化設計中，結合現有的進化算法、智慧型算法構造滿足一定約束條件的高可靠網路。
結題摘要
21 世紀以來，以信息技術的飛速發展為基礎，計算機網路、交通網路、複雜網路無時無刻不包圍著我們。一旦網路出現故障,可能會造成重大甚至是災難性的影響,網路可靠性成為了網路分析和設計中的重要問題。 網路可靠性是指：網路在規定條件下和規定時間內，能在用戶期望的時間範圍內將物質、信息、能量按用戶需求完整、正確地在網路中傳輸的能力。對於一個網路，是指至少需要破壞幾個節點或幾條鏈路才能中斷部分節點之間的通信。可以通過兩個確定測度——連通度κ和邊連通度λ來表示。要使一個網路解體，至少需要去掉κ個節點或者λ條鏈路。這種解體，可能把一個網路分解為兩個或多個子網路，也可能把一個節點從網路中分離出來。對於網路業務來說，前者比後者帶來更嚴重的後果。傳統連通度並不能做出區分。 考慮到實際套用，本項目重點研究能更精確度量網路可靠性的參數——條件連通度及其推廣：h 條件連通度，並將研究成果套用到網路可靠性的最佳化設計中。具體研究內容如下： 1．條件連通度確定問題 2. 最優連通圖的刻劃問題 這兩類問題是相輔相成的，在研究過程中通常是同時考慮的。很多典型網路的條件連通度尤其是條件邊連通度已經確定，但是在連通度方面的結論卻很少。強積圖是一種大規模網路的構造方式，並且保持其因子圖的諸多性質，尤其是可靠性方面。我們主要結論是： 給出了以強積圖網路可靠性的確切度量，並且刻畫了其達到最優值的條件，即該類網路在不考慮其他要求時達到最可靠的條件。 考慮到網路實際運行時與同一台處理器直接連線的各處理器同時發生故障的可能性很小，所以在強積圖點可靠性達到最優值的基礎上我們進一步分析該類網路的可靠性，我們給出了強積圖的條件連通度的界及其達到最優值的條件。 網路鏈路發生故障時的可靠性則需要用邊連通度來度量，考慮實際意義，我們也研究了強積圖的條件邊連通度，給出了在網路鏈路發生故障的情況下網路達到最可靠的條件。 3. 網路可靠性最佳化設計問題：設計了算法以強積圖方式構造滿足一定約束條件下的高可靠性網路。 4. 高可靠性網路上的一些實際套用：如交通網路上的距離查詢、中國網際網路的物理定位、社交網路上的問答系統等。
