[發明專利]一種面向全部需求的多狀態網絡最小路集向量免重復搜索算法

有效

• 申請號: 202010574027.7
• 申請日: 2020-06-22
• 公開（公告）號: CN111726254B
• 公開（公告）日: 2022-05-24
• 發明（設計）人: 白光晗;許貝;陳曉光;方依寧;張云安;陶俊勇
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L41/14
• 分類號: H04L41/14
• 代理公司: 長沙國科天河知識產權代理有限公司 43225
• 代理人: 董惠文

本申請涉及一種面向全部需求的多狀態網絡最小路集向量免重復搜索算法。所述方法包括：根據多狀態網絡的最小路集向量和邊最大狀態向量計算該多狀態網絡的最大需求值，并獲得需求值d＝2時的最小路集向量2?MP。當d≥3時，利用對于一個MP_i，當集合ρ(MP_i)和集合中包含相同的元素時，MP_i與疊加形成的d?MP必然是一個重復項的定理，僅獲得兩個集合的交集為空時疊加形成的d?MP。上述面向全部需求的多狀態網絡最小路集向量免重復搜索算法，基于多狀態網絡中d?MP重復項的產生機制定義了一種MP_i與疊加獲得不重復的d?MP候選項的方法，可以預防產生重復的d?MP候選項，有效地提高d?MP搜索過程的效率。

技術領域

本申請涉及多狀態網絡可靠性評估領域，特別是涉及一種面向全部需求的多狀態網絡最小路集向量免重復搜索算法。

背景技術

隨著科學和技術的發展，網絡系統的復雜度快速增長，可靠性成為了評價網絡性能的重要指標。對于傳統的網絡可靠性模型而言，網絡及組成網絡的節點和邊都只有完好和失效兩種狀態，網絡的可靠度也就是網絡的連通度。但隨著網絡結構和應用場景的復雜化，網絡的可靠運行不止反映在連通上，而是更多地反映在網絡中的部件是否能夠滿足流量傳輸需求上。此時，整個系統傳輸的流量是否滿足要求就成為衡量網絡可靠性的一個重要指標，同時網絡中的每條線路也表現出和實際傳輸情況對應的多狀態特性。

基于最小路集向量(d-MP)的可靠性計算方法是多狀態網絡可靠性計算的主要方法之一，能夠更準確地描述多狀態網絡的狀態和可靠度，使網絡管理者能夠在此基礎上設計多狀態網絡的運行方案，并對其進行管理。目前已有多種d-MP搜索算法，其中具有代表性的包括：以MP為先驗信息的隱枚舉方法來搜索所有d-MP候選項的方法，通過探測網絡中循環的方法來剔除不滿足要求的d-MP候選項的方法，基于快速枚舉法的d-MP搜索算法，基于廣度優先搜索的面向全部需求值(d)的d-MP的搜索算法等。

這些算法雖然能夠獲得多狀態網絡的d-MP，但其在搜索過程中均會生成大量重復的d-MP候選項，并且只能在重復項產生之后通過逐對對比來剔除。隨著多狀態網絡的規模和復雜程度的提高，這些算法中重復的d-MP候選項數量也將隨之大幅增加。這將使算法所需的時間和數據存儲空間隨之增大，并且嚴重影響算法效率。

發明內容

基于此，有必要針對上述技術問題，研究多狀態網絡中d-MP重復項產生的機制，提供一種能夠預防重復d-MP候選項產生的面向全部需求的多狀態網絡最小路集向量免重復搜索算法。

一種面向全部需求的多狀態網絡最小路集向量免重復搜索算法，所述算法包括：

獲取多狀態網絡的最小路集向量MP和邊最大狀態向量。

根據獲取的最小路集向量MP和邊最大狀態向量，獲得需求值d＝2時的最小路集向量2-MP，獲得當最小路集向量MP_i與MP_j疊加為重復2-MP項，且j≥i時MP_j的下標集合ρ(MP_i)，獲得組成2-MP的MP_i的下標集合其中，MP_i表示第i個所述最小路集向量MP，表示第j個2-MP最小路集向量。

當需求值d≥3時，獲取MP_i，獲取最小值不小于i的并獲取該與該ρ(MP_i)的交集，當交集為空集時，將該疊加到該MP_i上，獲得不重復的d-MP的候選項，去除含有環的d-MP候選項，獲得需求值d≥3時的真實最小路集向量d-MP。

其中一個實施例中，還包括：根據獲取的最小路集向量MP和邊最大狀態向量，計算該多狀態網絡的最大需求值d_max。