[發明專利]一種保持網絡性能可靠度的網絡簡化方法

有效

• 申請號: 201710134204.8
• 申請日: 2017-03-08
• 公開（公告）號: CN107018011B
• 公開（公告）日: 2020-10-20
• 發明（設計）人: 黃寧;李碧薇;張薈;張朔;孫利娜
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26
• 代理公司: 北京慧泉知識產權代理有限公司 11232
• 代理人: 王順榮;唐愛華

1.一種保持網絡性能可靠度的網絡簡化方法，其特征在于：包括如下步驟：

步驟一：建立基于馬爾科夫獎勵模型的網絡性能模型，確定網絡性能指標；

首先建立節點的連續時間馬爾科夫鏈模型；節點CTMC模型考慮節點的狀態空間，每個節點視為一個獨立的M/M/1/n_i排隊模型，節點的數據包達到服從泊松分布，服務時間服從指數分布，共有n_i個存儲空間；將節點中數據包個數不同看作節點不同的狀態，把所有網絡中可能出現的狀態全部列出，并確定了各個狀態間轉換的概率；接著建立基于馬爾科夫獎勵模型的網絡性能模型，即在連續時間馬爾科夫鏈的狀態空間的基礎上，通過賦予系統每個狀態不同的獎勵值，將網絡中單節點連續時間馬爾科夫鏈模型結合起來，計算網絡的性能度量：平均到達數據包總時延；

步驟二：蒙特卡洛仿真方法評估網絡性能可靠度；

首先假設網絡中節點容量有限，鏈路存在一定的故障概率，以無故障網絡時延為閾值，對邊和節點的狀態進行隨機抽樣，接著由步驟一的平均到達數據包總時延計算網絡時延，將網絡時延與閾值進行比較判斷是否出現故障，多次仿真后的統計結果得到基于時延的網絡性能可靠度；

步驟三：保持連通可靠性的圖變化簡化方法的基礎上，針對網絡性能可靠度不變進行網絡簡化；

首先根據網絡的鄰接矩陣，路由矩陣，邊可靠度矩陣，以及節點的容量和節點服務率，判斷網絡是否可以簡化；接著依次找到網絡中的度一節點，度二節點和平行邊，基于時延進行度一簡化，度二簡化和并聯簡化直至網絡不能再簡化；

步驟四：利用提出的性能可靠性評估方法進行仿真驗證；

利用步驟三提出的簡化方法對網絡進行簡化，然后計算網絡的性能可靠度；利用步驟二中仿真方法對網絡的性能可靠度進行仿真；對比上述兩個可靠度值來驗證網絡簡化方法對保持該網絡的性能可靠度的有效性；

其中，所述的步驟三具體實現方法為：

首先判斷網絡是否存在度一節點，度二節點和并聯結構，若存在，則網絡可以簡化；對于度為一的節點，如果不為起始點s或者終點d，顯然與其相連地鏈路的路由概率r＝0，流量到達率Γ＝0；此時，直接刪除度一節點與相關邊，對網絡性能沒有影響，如果度一節點為起始點或者終點，該節點可視為度二節點，則按照基于時延的度二縮減原則進行簡化；

刪除度二節點將導致網絡解析計算的時延值變化；需要改變路由矩陣，還需改變相應節點的存儲空間n和服務率μ，由于精確求解的復雜性采用近似處理，故節點的存儲空間和服務率在簡化網絡后按照如下規則：

n′₃＝n₃+n₂/(k₃-k_ariv₃+1) (8)

μ′₃＝μ₃-μ₂/n₂-ln(k₃-k_ariv₃+1) (9)

其中k₃為度二節點相鄰節點的度數，k_ariv₃為路由矩陣中流量流入該節點的邊數，n₂為度二節點的存儲空間，μ₂為度二節點的服務率；

對于并聯縮減只刪除邊，而沒有改動網絡中的節點，因此只需相對地改變鏈路的路由概率，節點1和2之間有兩條邊，路由概率分別為r(a)和r(b)，將此結構縮減為一條路由概率為r₁₂＝r(a)+r(b)的邊，簡化前后有關節點的流量與性能參數不變；按照上述規則進行網絡簡化直至網絡中不存在度一，度二節點和并聯結構。