一種考慮認知不確定性的網絡連通可靠度算法
2024-04-13 08:44:05 1
1.本發明涉及網絡可靠度技術領域，具體而言，涉及一種考慮認知不確定性的網絡連通可靠度算法。
背景技術：
2.網絡系統，如供應鏈網絡，通信網絡和交通網絡等，在人們的日常生活中起到至關重要的作用。隨著社會進步和科學發展，這些網絡的結構越來越複雜，規模越來越龐大，進而使得網絡中不可避免會有故障發生。網絡連通可靠度是網絡可靠度的基礎指標，其關注的是指網絡中指定節點間存在連通路徑的可能性。
3.傳統的網絡連通可靠度算法通常是基於概率論展開的。這些評價方法假設網絡中節點故障時間分布是已知的，或者是精確測量的。然而對於很多現實世界中的網絡，如衛星網絡、無線傳感器網絡等，由於網絡結構複雜，又受時間或資金約束等原因，缺乏足夠的觀測數據，進而使得網絡中的故障數據主要存在認知不確定性。因此，傳統的基於概率論的網絡可靠度算法在解決上述問題時有自身的局限性。
4.本專利涉及的定理包括如下：
5.不確定測度：設γ是一個非空集合，是γ上的一個σ-代數，則中的元素被稱λ為事件。將三元組稱作一個不確定空間。不確定測度時從到[0,1]的一個滿足以下4條公理的集函數：
[0006]
公理1(規範性)對於全集γ，有
[0007]
公理2(對偶性)對於任意事件λ，有
[0008]
公理3(次可加性)對於一列可數的事件序列λ1，λ2，λ3，
…
，有
[0009]
公理4對一系列不確定空間記乘積σ-代數為對於任意中任意選取λg，乘積σ-代數上的乘積不確定測度滿足
[0010]
不確定變量：設ξ是從不確定空間到實數集r的一個函數，如果對於任意的borel集合b，集合{ξ∈b}＝{γ∈γ|ξ(γ)∈β}是一個事件，則稱ξ是一個不確定變量。
[0011]
如果一個不確定變量取值0或者1，那麼該不確定變量稱為布爾不確定變量。例如，下述ξ是一個布爾不確定變量，
[0012][0013]
其中是一個0到1之間的實數。
[0014]
不確定分布：一個不確定變量的不確定分布φ被定義為其中x為任意實數。
[0015]
定理1假設ξ1，ξ2，
…
，ξn是獨立的布爾不確定變量，對於i＝1，2，
…
，有
[0016][0017]
如果f是一個單增的布爾函數，則對於布爾不確定變量ξ＝f(ξ1，ξ2，
…
，ξn)有
[0018][0019]
其中bi是集合{0,1}的子集，i＝1，2，
…
，。
[0020]
為此提出一種認知不確定性的網絡連通可靠度算法，以解決上述提出的問題。
技術實現要素：
[0021]
本發明旨在提供一種考慮認知不確定性的網絡連通可靠度算法，以解決或改善現實世界中的網絡，如衛星網絡、無線傳感器網絡等，由於網絡結構複雜，又受時間或資金約束等原因，缺乏足夠的觀測數據，進而使得網絡中的故障數據主要存在認知不確定性問題。
[0022]
有鑑於此，本發明的第一方面在於提供一種考慮認知不確定性的網絡連通可靠度算法。
[0023]
本發明的第一方面提供了一種考慮認知不確定性的網絡連通可靠度算法，包括如下步驟：s1，根據網絡中各個節點以及節點之間連接的鏈路，建立網絡拓撲圖；s2，對網絡拓撲圖中加入考慮節點和鏈路是否正常的變量，獲得擴展不確定圖；s3，通過連通函數對所述變量構建所述擴展不確定圖的連通狀態模式，建立考慮所述連通狀態模式的可靠度的網絡連通可靠度模型；s4，將連通狀態模式的可靠度等效轉化為最可靠連通路徑；s5，在擴展不確定圖中，尋找兩個節點之間的最可靠連通路徑；s6，計算所述最可靠連通路徑的連通可靠度，完成網絡連通可靠度模型的求解；其中，所述連通狀態模式表示所述擴展不確定圖中任意兩個節點之間是否連通。
[0024]
本發明提供的一種考慮認知不確定性的網絡連通可靠度算法，根據網絡中各個節點及其之間的連接關係建立網絡拓撲圖，包括節點集合和表示節點之間聯繫的鏈路集合；
[0025]
基於網絡中各個節點和鏈路的故障數據，根據不確定統計方法，得到各個節點和邊是否正常的布爾不確定分布，在網絡拓撲的基礎上，建立擴展不確定圖；
[0026]
對於一個二態網絡，網絡中的節點與節點之間只有連通和不連通兩種狀態，用連通狀態模式來描述節點與節點是否連通；
[0027]
根據網絡連通可靠度模型，計算網絡的連通可靠度，首先需要計算連通狀態模式，擴展不確定圖中節點與節點之間的連通可靠度與最可靠連通路徑連通可靠度相等。因此，計算連通狀態模式轉化為尋找最可靠連通路徑；
[0028]
對於最可靠連通路徑，若且唯若路徑上的所有鏈路和節點都存在時，路徑才是連通的；
[0029]
通過將網絡中節點和邊的狀態，正常或故障，描述為布爾不確定分布來考慮認知不確定性，通過建立擴展不確定圖，定量計算網絡的連通可靠度。
[0030]
另外，根據本發明的實施例提供的技術方案還具有如下附加技術特徵：
[0031]
上述任一技術方案中，所述連通狀態模式具體為下述公式：c
sn
＝f
sn
(c1，c2，
…
，c
m+n
)；其中，c
sn
為連通狀態模式、f
sn
為連通函數、c1，c2，
…
，c
m+n
為擴展不確定圖中考慮節點
和鏈路是否正常的布爾不確定變量。
[0032]
在該技術方案中，用連通狀態模式c
sn
來描述節點vs與節點v
t
是否連通。當c
sn
＝1時，節點vs與節點v
t
之間是連通的，當c
sn
＝0時，節點vs與節點v
t
之間是不連通的。在擴展不確定圖g(v，e，c)中，連通狀態模式c
sn
表示為上述公式，f
sn
是一個單增的布爾函數。
[0033]
上述任一技術方案中，所述連通可靠度模型具體為下述公式：其中，r
sn，g
表示在擴展不確定圖中的從節點vs到節點v
t
的連通可靠度，vs和v
t
為所述網絡中的任意點。
[0034]
上述任一技術方案中，在所述擴展不確定圖中選擇節點vs和節點v
t
，所述s4中的等效轉化具體為下述公式：其中，表示路徑p
*
中從節點vs到節點v
t
的連通可靠度。
[0035]
在該技術方案中，p
*
為擴展不確定圖g中從節點vs到節點v
t
的一條路徑，如果對於擴展不確定圖g中任意一條從節點vs到節點v
t
的路徑p，都有那麼稱p
*
為擴展不確定圖g中從節點vs到節點v
t
的最可靠連通路徑。其中和r
sn，p
分別表示路徑p
*
和路徑p的連通可靠度；
[0036]
在擴展不確定圖g中，p
*
表示擴展不確定圖g中節點vs與節點v
t
之間的最可靠連通路徑，則有：
[0037][0038]
其中r
sn，g
表示在擴展不確定圖g中從節點vs到節點v
t
的連通可靠度，表示路徑p
*
中從節點vs到節點v
t
的連通可靠度；
[0039]
具體地，假設g(v,e,c)是一個擴展不確定圖，其中v＝{v1，v2，
…
，vn},e＝{e1，e2，
…
，em},c＝{c1，c2，
…
，c
m+n
}。擴展不確定圖g中的連通可靠度為：
[0040][0041]
其中，bi是集合{0，1}的子集，i＝1，2，
…
，m+n。
[0042]
在擴展不確定圖g中存在因此，需要證明
[0043]
由於f
sn
是一個單增的函數，當f
sn
(b1，b2，
…
，{0}，
…
，b
m+n
)＝1
[0044]
成立時，下式也成立
[0045]fsn
(b1，b2，
…
，{1，0}，
…
，b
m+n
)＝1
[0046]
存在一組取值{1}或者{0，1}，使得
[0047][0048]
考慮到當為{0，1}時，因此上式寫作
[0049][0050]
其中j和j分別是中元素和規模。
[0051]
那麼由總數為j的邊和節點組成的子圖s包含一條從節點vs到節點v
t
路徑，將子圖s中不屬於該路徑的邊或節點移除掉，得到一個新的子圖s1，包含總數為j-1的邊和節點。此時s1包含一條路徑，且滿足
[0052][0053]
其中j
′
是被移除的邊或頂點的索引。
[0054]
因此得到
[0055][0056]
重複以上過程，直到子圖中不存在除了路徑中邊和節點的其他邊和節點。得到一條路徑p滿足
[0057]rsn，g
＝r
sn，p
[0058]
由於p
*
是最可靠連通路徑，因此有
[0059][0060]
綜上所述，得到
[0061][0062]
因此
[0063]
上述任一技術方案中，所述擴展不確定圖為g(v，e，c)；其中，v＝{v1，v2，
…
，vn}為節點集合、e＝{e1，e2，
…
，em}為鏈路集合、c＝{c1，c2，
…
，c
m+n
}為考慮節點和鏈路是否正常的變量集合。
[0064]
在該技術方案中，其中，i＝1，2，
…
，m+n；表示節點或邊i正常的不確定測度，即節點或邊i的確信可靠度；
[0065]
基於擴展不確定圖，擴展不確定圖的鄰接矩陣表示為：
[0066][0067]
其中0≤α
ij
≤1，i，j＝1，2，
…
，n。當i＝j時，α
ij
表示節點vi存在的不確定測度，當i≠j時，α
ij
表示節點vi與節點vj之間有鏈路存在的不確定測度。
[0068]
上述任一技術方案中，所述s5的步驟，具體為：s501，分別設置最可靠連通路徑的節點集合s、其他節點集合u和最可靠連通路徑的鏈路集合l；其中，s包含節點vs，u包含v中除外vs的節點vi；s502，以vs為起點；s503，對所有滿足vi∈u的鏈路e
s，i
，選擇使得α
s，i
∧α
i，i
值最大的鏈路e
s，i
和節點vi，並分別放入l和s；s504，令節點vs＝s503的vi，並從u中刪除s503的節點vi，返回s502直至s503的節點vi為節點v
t
；其中，α
s，i
為節點vs與節點vi之間有鏈路存
在的不確定測度、α
i，i
為節點vi存在的不確定測度。
[0069]
在該技術方案中，在預先期望的vs和v
t
之間尋找最可靠連通路徑，根據步驟s502能夠尋找到某個節點與s502中的vs最可靠連通路徑及vi，並在s503中以當前找到的vi為起點vs，直至s503尋找到的vi為期望的v
t
。
[0070]
上述任一技術方案中，所述連通可靠度採用下述公式計算：其中，evi為路徑p
*
上鏈路或節點，ci為路徑p
*
上節點或者鏈路的狀態模式、為不確定測度。
[0071]
在該技術方案中，對於最可靠連通路徑p
*
，若且唯若路徑p
*
上的所有鏈路和節點都存在時，路徑p
*
才是連通的。
[0072]
本發明與現有技術相比所具有的有益效果：
[0073]
通過將網絡中節點和邊的狀態，正常或故障，描述為布爾不確定分布來考慮認知不確定性，通過建立擴展不確定圖，定量計算網絡的連通可靠度。
[0074]
根據本發明的實施例的附加方面和優點將在下面的描述部分中變得明顯，或通過根據本發明的實施例的實踐了解到。
附圖說明
[0075]
附圖僅用於示出具體實施例的目的，而並不認為是對本發明的限制。
[0076]
圖1為本發明的算法流程圖；
[0077]
圖2為本發明的骨幹網示意圖。
具體實施方式
[0078]
為了更清楚地理解本發明的上述目的、特徵和優點，下面結合附圖和具體實施方式對本發明進行進一步的詳細描述。需要說明的是，在不衝突的情況下，本技術的實施例及實施例中的特徵相互組合。
[0079]
在下面的描述中闡述了很多具體細節以便於充分理解本發明，但是，本發明還採用其他不同於在此描述的其他方式來實施，因此，本發明的保護範圍並不受下面公開的具體實施例的限制。
[0080]
請參閱圖1，本發明的第一方面提供了一種考慮認知不確定性的網絡連通可靠度算法，包括如下步驟：。
[0081]
s1：建立網絡拓撲g(v，e)；
[0082]
根據網絡中各個節點之間的連接關係，建立網絡拓撲g(v，e)，其中，v＝{v1，v3，
…
，vn}為節點集合，e＝{e1，e2，
…
，em}為鏈路集合。
[0083]
s2：建立擴展不確定圖g(v，e，c)；
[0084]
基於網絡中各個節點和鏈路的故障數據，根據不確定統計方法，得到各個節點和鏈路是否正常的布爾不確定分布。在網絡拓撲g(v，e)的基礎上，建立擴展不確定圖g(v，e，c)，其中，v＝{v1，v3，
…
，vn}為節點集合，e＝{e1，e2，
…
，em}為鏈路集合，c＝{c1，c2，
…
，c
m+n
}為描述節點和鏈路是否正常的布爾不確定變量集合，其中，
[0085][0086]
這裡，i＝1，2，
…
，m+n。表示節點或鏈路i正常的不確定測度，即節點或鏈路i的確信可靠度。
[0087]
基於擴展不確定圖，擴展不確定圖的鄰接矩陣表示為：
[0088][0089]
其中0≤α
ij
≤1，i，j＝1，2，
…
，n。當i＝j時，α
ij
表示節點vi存在的不確定測度，當i≠j時表示節點vi與節點vj之間有鏈路存在的不確定測度α
ij
。
[0090]
s3：建立網絡連通可靠度模型；
[0091]
對於一個二態網絡，網絡中的節點vs與節點v
t
之間只有連通和不連通兩種狀態。採用連通狀態模式c
sn
來描述節點vs與節點v
t
是否連通。當c
sn
＝1時，節點vs與節點v
t
之間是連通的，當c
sn
＝0時，節點vs與節點v
t
之間是不連通的。在擴展不確定圖g(v，e，c)中，連通狀態模式c
sn
表示為
[0092]csn
＝f
sn
(c1，c2，
…
，c
m+n
)
[0093]
其中，c1，c2，
…
，c
m+n
表示擴展不確定圖g中節點和鏈路是否正常的布爾不確定變量，f
sn
為連通函數，表徵擴展不確定圖g中節點和鏈路的狀態模式c1，c2，
…
，c
m+n
對節點vs與節點v
t
之間連通狀態模式c
sn
的影響。很明顯f
sn
是一個單增的布爾函數。
[0094]
因此，網絡的連通可靠度模型為：
[0095][0096]
s4：計算連通狀態模式；
[0097]
根據網絡連通可靠度模型，計算網絡的連通可靠度，首先需要計算連通狀態模式c
sn
。擴展不確定圖g中節點vs與節點v
t
之間的連通可靠度與最可靠連通路徑連通可靠度相等。因此，計算連通狀態模式c
sn
轉化為尋找最可靠連通路徑。
[0098]
最可靠連通路徑：p
*
為擴展不確定圖g中從節點vs到節點v
t
的一條路徑，如果對於擴展不確定圖g中任意一條從節點vs到節點v
t
的路徑p，都有那麼稱p
*
為擴展不確定圖g中從節點vs到節點v
t
的最可靠連通路徑。其中和r
sn，p
分別表示路徑p
*
和路徑p的連通可靠度。
[0099]
在擴展不確定圖g中，p
*
表示擴展不確定圖g中節點vs與節點v
t
之間的最可靠連通路徑，則有
[0100][0101]
其中r
sn，g
表示在擴展不確定圖g中從節點vs到節點v
t
的連通可靠度，表示路徑p
*
中從節點vs到節點v
t
的連通可靠度。
[0102]
具體地，假設g(v,e,c)是一個擴展不確定圖，其中v＝{v1，v2，
…
，vn},e＝{e1，
e2，
…
，em},c＝{c1，c2，
…
，c
m+n
}。擴展不確定圖g中的連通可靠度為：
[0103][0104]
其中，bi是集合{0，1}的子集，i＝1，2，
…
，m+n。
[0105]
在擴展不確定圖g中存在因此，我們只需證明
[0106]
由於f
sn
是一個單增的函數，當f
sn
(b1，b2，
…
，{0}，
…
，b
m+n
)＝1成立時，下式也成立
[0107]fsn
(b1，b2，
…
，{1，0}，
…
，b
m+n
)＝1
[0108]
存在一組取值{1}或者{0，1}，使得
[0109][0110]
考慮到當為{0，1}時，因此上式寫作
[0111][0112]
其中j和j分別是中元素和規模。
[0113]
那麼由總數為j的邊和節點組成的子圖s包含一條從節點vs到節點v
t
路徑，將子圖s中不屬於該路徑的邊或節點移除掉，得到一個新的子圖s1，包含總數為j-1的邊和節點。此時s1包含一條路徑，且滿足
[0114][0115]
其中j
′
是被移除的邊或頂點的索引。
[0116]
因此得到
[0117][0118]
重複以上過程，直到子圖中不存在除了路徑中邊和節點的其他邊和節點。得到一條路徑p滿足
[0119]rsn，g
＝r
sn，p
[0120]
由於p
*
是最可靠連通路徑，因此有
[0121][0122]
綜上所述，得到
[0123][0124]
因此
[0125]
s5：尋找最可靠連通路徑。
[0126]
在擴展不確定圖g(v，e，c)中，尋找節點vs與節點v
t
之間的最可靠連通路徑。進一步地，所述步驟s5的具體過程為：
[0127]
s5-1：取三個集合s、u和l。分別令s只包含節點，即s＝{vs}，u包含v中除vs外的其他節點，即u＝v-s，
[0128]
s5-2：以為起點vs，對所有滿足vi∈u的鏈路e
s，i
，選擇使得α
s，i
∧α
i，i
值最大的鏈路和頂點。比方說vi′
和e
s，i
′
。更新集合s、u和l，使得s＝s∪{vi′
}，u＝u-{vi′
}，l＝l∪{e
s，i
′
}；
[0129]
s5-3：以i
′
為新的起點，重複上述步驟直到節點v
t
包含在集合s中。最後所得到的集合s即為最可靠連通路徑的節點集合，集合l為最可靠連通路徑的鏈路集合。
[0130]
s6：計算最可靠連通路徑的連通可靠度
[0131]
對於最可靠連通路徑p
*
，若且唯若路徑p
*
上的所有鏈路和節點都存在時，路徑p
*
才是連通的。因此，路徑p
*
的連通可靠度通過下式計算得出：
[0132][0133]
其中，evi表示路徑p
*
上鏈路或節點，ci表示路徑p
*
上節點或者鏈路的狀態模式。
[0134]
實施例1
[0135]
如圖2所示，以nsfnet網絡為例說明本發明的應用過程。nsfnet是一個科研骨幹網絡，由14個節點和21條鏈路組成。在網絡中，每一個節點表示一個計算中心，每一條鏈路表示節點之間的通信線路。nsfnet網絡中的節點和鏈路只有故障和正常工作兩種狀態，且節點與鏈路上的故障相互獨立。下面給出網絡中幾個指定節點間的連通可靠度計算過程。
[0136]
首先根據nsfnet中各個節點之間的連接關係構建網路拓撲g(v，e)，該拓撲g(v，e)包含14個節點和21條鏈路。
[0137]
然後基於不確定統計方法，根據故障數據或專家經驗獲取網絡中各個節點和鏈路的布爾不確定分布，nsfnet網絡的節點信息和鏈路信息分別如表1和表2所示。
[0138]
表1節點信息
[0139][0140][0141]
表2鏈路信息
[0142][0143]
基於網絡拓撲g(v，e)和表1、2中的信息，建立擴展不確定圖g(v，e，c)該擴展不確定圖的鄰接矩陣為：
[0144][0145]
基於擴展不確定圖，首先尋找節點vs與節點v
t
之間的最可靠連通路徑，然後計算其對應的連通可靠度。表3給出了幾組節點對之間的最可靠連通路徑和連通可靠度。
[0146]
表3網絡連通可靠度
[0147][0148][0149]
在本發明的描述中，需要理解的是，術語「縱向」、「橫向」、「上」、「下」、「前」、「後」、「左」、「右」、「豎直」、「水平」、「頂」、「底」、「內」、「外」等指示的方位或位置關係為基於附圖所
示的方位或位置關係，僅是為了便於描述本發明，而不是指示或暗示所指的裝置或元件必須具有特定的方位、以特定的方位構造和操作，因此不能理解為對本發明的限制。
[0150]
以上所述的實施例僅是對本發明的優選方式進行描述，並非對本發明的範圍進行限定，在不脫離本發明設計精神的前提下，本領域普通技術人員對本發明的技術方案做出的各種變形和改進，均應落入本發明權利要求書確定的保護範圍內。