[發(fā)明專利]一種基于模塊度劃分通信社團(tuán)的全端可靠性計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201711201952.X
• 申請(qǐng)日: 2017-11-27
• 公開(kāi)（公告）號(hào): CN107944705B
• 公開(kāi)（公告）日: 2022-03-11
• 發(fā)明（設(shè)計(jì)）人: 董剛松;郝洋;邵奇;王正;宋騰;趙景隆;申京
• 申請(qǐng)（專利權(quán)）人: 國(guó)網(wǎng)河南省電力公司信息通信公司;國(guó)家電網(wǎng)公司
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06Q50/00;G06Q50/06
• 代理公司: 鄭州博派知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 41137
• 代理人: 榮永輝

1.一種基于模塊度劃分通信社團(tuán)的全端可靠性計(jì)算方法，包括基于模塊度的電力通信網(wǎng)社團(tuán)劃分和基于最小路集的全端可靠性計(jì)算，其特征在于，基于模塊度的電力通信網(wǎng)社團(tuán)劃分包括如下步驟，

S1，網(wǎng)絡(luò)G中，記任意節(jié)點(diǎn)i的度數(shù)為k_i＝∑_jA_ij,其中A代表圖G的鄰接矩陣；C表示包含節(jié)點(diǎn)i的一個(gè)社區(qū)，則節(jié)點(diǎn)i的度數(shù)可以分為兩部分：

其中，表示i與社團(tuán)C之外的節(jié)點(diǎn)的連接邊的數(shù)目，表示i與C內(nèi)其他節(jié)點(diǎn)之間的邊的數(shù)目；

如果C滿足條件：則稱子圖C為強(qiáng)社團(tuán)；

如果C滿足條件：則稱子圖C為弱社團(tuán)；

S2，劃分通信社團(tuán)需要定義模塊度，模塊度是衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的方法，在本文中，模塊度衡量的是通信社團(tuán)內(nèi)部通信節(jié)點(diǎn)的相互通信健壯性，健壯性表示通信節(jié)點(diǎn)之間連通的概率大??；

模塊度Q定義如下：

其中，

P_ij表示通信節(jié)點(diǎn)i,j之間光纖正常工作的概率，M表示網(wǎng)絡(luò)中所有光纖正常工作的概率之和，t_i表示與通信節(jié)點(diǎn)i相連的所有光纖正常工作的概率之和，模塊度公式表示的是網(wǎng)絡(luò)中連接社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的邊所占的比例，減去在同樣的社團(tuán)結(jié)構(gòu)下任意連接這兩個(gè)節(jié)點(diǎn)的比例的期望值；

S3，使用Fast Unfolding算法將電力通信網(wǎng)中聯(lián)系緊密的通信站點(diǎn)進(jìn)行聚類形成一個(gè)通信“社團(tuán)”，包括三個(gè)階段：

假設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，

a，初始狀態(tài)下，為每個(gè)節(jié)點(diǎn)i分配一個(gè)社團(tuán)號(hào)i，此時(shí)網(wǎng)絡(luò)就有N個(gè)社團(tuán)；

b，對(duì)每個(gè)節(jié)點(diǎn)i，考慮將其鄰接節(jié)點(diǎn)j加入i的對(duì)應(yīng)社團(tuán)下,此動(dòng)作下，計(jì)算模塊度Q，加入模塊度變化量ΔQ為正，則接納這種變化；

c，當(dāng)?shù)螖?shù)小于總迭代次數(shù)時(shí)，重復(fù)步驟b；

在所述基于模塊度的電力通信網(wǎng)社團(tuán)劃分的基礎(chǔ)之上，進(jìn)行基于最小路集的全端可靠性計(jì)算，利用基于模塊度的電力通信網(wǎng)社團(tuán)劃分算法將整張電力通信網(wǎng)劃分成若干個(gè)規(guī)模較小的通信社團(tuán)，基于電力通信網(wǎng)的小世界網(wǎng)絡(luò)特性，利用復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)將整張復(fù)雜網(wǎng)絡(luò)分解成為多個(gè)規(guī)模較小且相互獨(dú)立的網(wǎng)絡(luò)，對(duì)這些規(guī)模較小且相互獨(dú)立的網(wǎng)絡(luò)求解其內(nèi)部全端可靠性，再將這些小規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)化，節(jié)點(diǎn)權(quán)值為小規(guī)模網(wǎng)絡(luò)全端可靠性的值，之后對(duì)小規(guī)模網(wǎng)絡(luò)之間的全端可靠性進(jìn)行求解，最后得出的全端可靠性代表整張網(wǎng)絡(luò)的全端可靠性，利用最小路集來(lái)求解網(wǎng)絡(luò)的全端可靠性，路集是確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)連通的邊的集合，如果一個(gè)路集去掉任何一邊不再是一個(gè)路集，則這個(gè)路集稱為最小路集，在全端可靠性的情況下，至少有一個(gè)最小路集正常工作，全端可靠性由最小路集決定；

所述基于最小路集的全端可靠性計(jì)算具體步驟如下；

A，對(duì)于概率基本公式Pr(A₁∪A₂∪...∪A_n)，在無(wú)向圖G＝(V,E)中，其中V代表圖中頂點(diǎn)構(gòu)成的集合，E代表圖中所有邊所構(gòu)成的集合，A_i表示最小路集i中邊e∈E_i全部正常工作的事件，E_i表示最小路集i中所有邊構(gòu)成的集合，表示邊e∈(E-E_i)全部正常工作的事件；由概率基本公式可知：

其中：

Pr(A_i)＝∏Pr(e)e∈E_i(10)；

公式(10)表示最小路集i中所有邊e都正常工作的概率；

B，根據(jù)公式：

可以將公式Pr(A₁∪A₂∪…∪A_n)進(jìn)一步轉(zhuǎn)換為：

根據(jù)下列布爾代數(shù)式還可以進(jìn)一步減少運(yùn)算步驟：

C，不交和算法是根據(jù)公式(12)求得不交積的和，并利用公式(13)化簡(jiǎn)運(yùn)算過(guò)程，將不交和算法寫(xiě)成函數(shù)SDP(P,Edge,N)，P為存儲(chǔ)最小路集的集合的結(jié)構(gòu)體，N表示最小路集個(gè)數(shù)，Edge中存儲(chǔ)了邊的有效概率；返回值為可靠性R；

函數(shù)SDP(P,Edge,N)的步驟如下：

1、如果只輸入一個(gè)最小路集N＝1，則計(jì)算該路集的可靠性R；否則，執(zhí)行步驟2；

2、求出第一個(gè)最小路集的概率R；

3、對(duì)于第2到第N個(gè)最小路集，循環(huán)執(zhí)行步驟4到7；

4、分別將前i-1個(gè)最小路集與第i個(gè)做差，得到num個(gè)集合；

5、根據(jù)公式(13)去掉冗余的集合；

6、遞歸調(diào)用SDP函數(shù)求num個(gè)集合的并集的概率R₁；

7、求出第i個(gè)最小路集的概率R₂，返回可靠性R＝R+R₂*(1-R₁)。