基于改進(jìn)聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法

付佳佳　吳贊紅　施展

摘? ?要：隨著電力通信網(wǎng)規(guī)模的逐漸擴(kuò)大，已有電力通信網(wǎng)可靠性優(yōu)化算法的計(jì)算時(shí)間復(fù)雜度較高。為此，提出了基于改進(jìn)聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法。該算法首先采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個(gè)社團(tuán)。其次，通過社團(tuán)間可靠性分析與備份方法、社團(tuán)內(nèi)可靠性分析與備份方法兩個(gè)過程，對(duì)電力通信網(wǎng)的關(guān)鍵資源進(jìn)行識(shí)別和備份，從而提升了電力通信網(wǎng)的可靠性。在仿真實(shí)驗(yàn)部分，從備份資源數(shù)量在總資源中的占比、網(wǎng)絡(luò)連通度兩個(gè)方面，將本算法與已有算法進(jìn)行比較，驗(yàn)證了本文算法有效提升了電力通信網(wǎng)的可靠性。

關(guān)鍵詞：電力通信網(wǎng);可靠性;聚類;社團(tuán);SDN

中圖分類號(hào)：TP393? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Reliability Optimization Algorithm for Power Communication

Network Based on Improved Clustering Algorithm

FU Jia-jia ，WU Zan-hong，SHI Zhan

（Power Grid Dispatching Control Center，Guangdong Power Grid Co.，Ltd，Guangzhou，Guangdong 510600，China）

Abstract：With the gradual expansion of the scale of power communication networks，the time complexity of existing power communication network reliability optimization algorithms is relatively high. In order to solve this problem，this paper proposes a reliability optimization algorithm for power communication network based on improved clustering algorithm. The algorithm firstly uses the FCM algorithm combined with simulated annealing algorithm and genetic algorithm to divide large-scale network into multiple communities. Secondly，through the two processes of reliability analysis and backup method，intra-community reliability analysis and backup method，the key resources of the communication network are identified and backed up，thereby improving the reliability of the power communication network. In the simulation experiment，the algorithm is compared with the existing algorithms from the aspects of the proportion of backup resources in total resources and network connectivity. It is verified that the proposed algorithm effectively improves the reliability of the power communication network.

Key words：power communication network;reliability;clustering;community;SDN

隨著各種新型電力業(yè)務(wù)的快速發(fā)展和應(yīng)用，實(shí)際環(huán)境中電力通信網(wǎng)的管理和維護(hù)更加困難，迫切需要可以應(yīng)用于實(shí)際環(huán)境下的電力通信網(wǎng)的可靠性分析方法[1-2]。在網(wǎng)絡(luò)可靠性提升方面，典型的研究成果包括采用遺傳算法優(yōu)化路由策略從而實(shí)現(xiàn)路由均衡[3]、優(yōu)化網(wǎng)絡(luò)的關(guān)鍵資源從而提升網(wǎng)絡(luò)可靠性[4]、同時(shí)優(yōu)化電力通信網(wǎng)相關(guān)系統(tǒng)和通信網(wǎng)相關(guān)設(shè)備等研究方法[5]，在提升電力通信網(wǎng)可靠性方面取得了較好的結(jié)果。在電力設(shè)備可靠性提升方面，典型的研究成果包括采用優(yōu)化后的混合半云模型優(yōu)化配電系統(tǒng)可靠性[6]、采用頻率優(yōu)化策略實(shí)現(xiàn)電網(wǎng)可靠性評(píng)估[7]。另外，在電力設(shè)備可靠性提升方面引入了一些新技術(shù)，例如SDN技術(shù)已成為新型網(wǎng)絡(luò)可靠性的關(guān)鍵技術(shù)[8]、基于關(guān)聯(lián)規(guī)則的Apriori-AHP算法的主動(dòng)可靠性保障技術(shù)[9]、使用鏈路已使用情況進(jìn)行網(wǎng)絡(luò)可靠性研究的方法[10]。

已有研究分析可知，在電力通信網(wǎng)的可靠性研究方面已經(jīng)取得了較好的研究成果。但是，已有算法主要關(guān)注新的方法和技術(shù)在電力通信網(wǎng)可靠性提升方面的應(yīng)用。在電力通信網(wǎng)規(guī)模越來越大的趨勢(shì)下，急需能夠有效解決大規(guī)模環(huán)境下網(wǎng)絡(luò)可靠性問題的研究成果。為此，采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個(gè)社團(tuán)，提出了基于改進(jìn)聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法。通過仿真實(shí)驗(yàn)，驗(yàn)證了本算法有效提升了電力通信網(wǎng)的可靠性。

1? ?問題描述

一般來說，網(wǎng)絡(luò)節(jié)點(diǎn)和網(wǎng)絡(luò)鏈路構(gòu)成電力通信網(wǎng)。網(wǎng)絡(luò)節(jié)點(diǎn)為電力業(yè)務(wù)提供計(jì)算服務(wù)，網(wǎng)絡(luò)鏈路為電力業(yè)務(wù)提供通信連接服務(wù)。使用G = （V，E）表示電力通信網(wǎng)，其中，V表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，E表示網(wǎng)絡(luò)鏈路集合。在電力通信網(wǎng)的可靠性方面，節(jié)點(diǎn)的度De（ni）是一個(gè)非常關(guān)鍵的屬性。度數(shù)越大，相連的邊越多，承載在其上的電力業(yè)務(wù)的可靠性越高。如果發(fā)掘度數(shù)少的節(jié)點(diǎn)，且該節(jié)點(diǎn)在網(wǎng)絡(luò)中處于重要位置，可以通過為其分配備份資源，提升網(wǎng)絡(luò)的可靠性。

因?yàn)殡娏νㄐ啪W(wǎng)的規(guī)模較大，如果通過算法對(duì)整個(gè)電力通信網(wǎng)的屬性進(jìn)行分析，會(huì)導(dǎo)致運(yùn)算復(fù)雜度較高。為此，采用聚類算法，發(fā)掘網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系，從而將電力通信網(wǎng)劃分為多個(gè)小規(guī)模的網(wǎng)絡(luò)。因?yàn)槟：鼵-均值聚類（FCM）具有運(yùn)算速度快、分類結(jié)果較好等優(yōu)點(diǎn)[11]，本文采用FCM算法對(duì)電力通信網(wǎng)進(jìn)行聚類分析。

使用V = {v1，v2，…，vn}表示網(wǎng)絡(luò)節(jié)點(diǎn)集合。假設(shè)將網(wǎng)絡(luò)節(jié)點(diǎn)劃分為c（2≤c≤n）個(gè)節(jié)點(diǎn)集合，則使用U = {A1，A2，…，Ac}表示劃分后的網(wǎng)絡(luò)節(jié)點(diǎn)子集合。子集合的中心使用{k1，k2，…，kc}表示。為了評(píng)判子集合的劃分效果，定義目標(biāo)函數(shù)Jb并使用公式（1）評(píng)判聚類劃分的效果。其中，μk（xi）表示各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)vi相對(duì)于類Ak的隸屬度（簡(jiǎn)化標(biāo)記為μk），dik表示網(wǎng)絡(luò)節(jié)點(diǎn)vi和類Ak的聚類中心ki的歐幾里得距離。b表示加權(quán)參數(shù)，1≤b≤∞。

Jb（U，v） = ∑ni=1∑ck=1（uik）b（dik）2? ? ? ?（1）

因?yàn)殡娏νㄐ啪W(wǎng)的規(guī)模較大，F(xiàn)CM算法屬于一種局部搜索算法，所以FCM算法搜索的結(jié)果可能是局部最優(yōu)。為此，基于模擬退火算法與遺傳算法對(duì)FCM算法進(jìn)行優(yōu)化，從而得到全局最優(yōu)的結(jié)果。

2? ?算? ?法

為解決大規(guī)模環(huán)境下網(wǎng)絡(luò)可靠性優(yōu)化算法性能低的問題，提出了優(yōu)化算法包括社團(tuán)劃分、社團(tuán)間可靠性分析與備份方法、社團(tuán)內(nèi)可靠性分析與備份方法三個(gè)步驟。下面首先對(duì)三個(gè)步驟的關(guān)鍵知識(shí)進(jìn)行詳細(xì)描述，之后對(duì)算法過程進(jìn)行分析。

2.1? ? 社團(tuán)劃分

在社團(tuán)劃分時(shí)，采用基于模擬退火算法與遺傳算法的FCM算法對(duì)電力通信網(wǎng)進(jìn)行劃分。劃分時(shí)包括三個(gè)過程：（1）初始化控制參數(shù);（2）對(duì)每個(gè)聚類中心計(jì)算個(gè)體的適應(yīng)度值;（3）對(duì)群體實(shí)施選擇、交叉和變異等遺傳操作。

在初始化控制參數(shù)時(shí)，控制參數(shù)包括種群大小SP、最大優(yōu)化代數(shù)MG、變異概率Pm、交叉概率Pc、溫度降低系數(shù)k、退火開始溫度T0、退火結(jié)束溫度Tend。首先通過隨機(jī)生成c個(gè)聚類中心，并劃分為初始種群CM。為評(píng)價(jià)每個(gè)聚類的劃分是否合適，需要給每個(gè)聚類中心應(yīng)用公式（1）求解個(gè)體的目標(biāo)函數(shù)Jb，并將其值賦值給適應(yīng)度fi，其中i=1，2，…，SP。其次，使用公式（2）計(jì)算每個(gè)個(gè)體的隸屬度，對(duì)群體CM進(jìn)行選擇、交叉和變異等后，使用公式（3）計(jì)算聚類的新中心。在判定是否結(jié)束方面，從遺傳代數(shù)、降溫兩個(gè)維度對(duì)算法是否結(jié)束進(jìn)行判定。

μik = ■? ? ?（2）

vij = ■? ? ?（3）

2.2? ?社團(tuán)間可靠性分析與備份方法

將電力通信網(wǎng)劃分為多個(gè)子網(wǎng)絡(luò)（即多個(gè)社團(tuán)）時(shí)，每個(gè)子網(wǎng)絡(luò)內(nèi)部關(guān)系比較緊密，各個(gè)子網(wǎng)絡(luò)之間的鏈路比較稀疏。此時(shí)，各個(gè)子網(wǎng)絡(luò)之間鏈路的可靠性對(duì)于電力通信網(wǎng)的整體連通性起到了非常關(guān)鍵的作用。當(dāng)任意兩個(gè)子網(wǎng)絡(luò)之間的鏈路出現(xiàn)故障時(shí)，子網(wǎng)絡(luò)之間失去連通性。所以，如何確保子網(wǎng)絡(luò)之間鏈路的可靠性，對(duì)于電力通信網(wǎng)的可靠性至關(guān)重要。

在社團(tuán)間可靠性提升時(shí)，以當(dāng)前社團(tuán)的外鏈邊數(shù)在所有社團(tuán)的外鏈邊數(shù)的比值進(jìn)行衡量，稱為社團(tuán)外鏈能力。此時(shí)，社團(tuán)外鏈能力越強(qiáng)，電力通信網(wǎng)的可靠性越高。使用Vxy = {（u，v）∈E，u∈Cx，v∈Cy，x≠y}表示社團(tuán)x和社團(tuán)y的鏈路集合。使用v（x，y） = Vxy表示社團(tuán)x和社團(tuán)y之間的鏈路數(shù)量?；谏鲜龇治?，使用公式（4）計(jì)算社團(tuán)x的可靠性。其中，Vx = ∑y∈EVxy表示與社團(tuán)x相連接的所有社團(tuán)的外鏈鏈路之和。通過社團(tuán)間可靠性分析，將可靠性最低的社團(tuán)的邊及其相連的節(jié)點(diǎn)進(jìn)行備份，從而提升網(wǎng)絡(luò)的可靠性。

CR（x） = ■? ? ? ?（4）

2.3? ?社團(tuán)內(nèi)可靠性分析與備份方法

從社團(tuán)劃分的計(jì)算過程可知，在每個(gè)社團(tuán)內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)的距離較近，關(guān)聯(lián)性較高。所以，在分析社團(tuán)內(nèi)的可靠性時(shí)，采用內(nèi)部節(jié)點(diǎn)中心度進(jìn)行衡量。使用公式（5）計(jì)算每個(gè)社團(tuán)內(nèi)的網(wǎng)絡(luò)節(jié)點(diǎn)ni∈N的可靠性。其中，dij表示節(jié)點(diǎn)ni和節(jié)點(diǎn)nj之間最少的鏈路數(shù)量，nj∈ψ（ni）表示電力通信網(wǎng)刪除ni∈N后的節(jié)點(diǎn)集合。通過社團(tuán)內(nèi)可靠性分析，將可靠性最低的內(nèi)部節(jié)點(diǎn)進(jìn)行備份。

CC（ni） = ∑nj∈Ψ（ni）dij? ? ? ?（5）

2.4? ?算法描述

為解決大規(guī)模環(huán)境下網(wǎng)絡(luò)可靠性優(yōu)化算法性能低的問題，提出的優(yōu)化算法包括三個(gè)步驟。（1）、采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為K個(gè)社團(tuán);（2）、社團(tuán)間可靠性分析與備份;（3）、社團(tuán)內(nèi)可靠性分析與備份。算法描述如表1所示。

算法：基于改進(jìn)聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法

（1）采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)

絡(luò)劃分為K個(gè)社團(tuán);

（a）初始化SP、MG、Pc、Pm、T0、Tend等控制參數(shù);

（b）采用公式（1）求解各個(gè)聚類中個(gè)體的fi;

（c）采用公式（2）、（3）計(jì)算新個(gè)體的μik，以及各個(gè)聚類的新中心

和f? ′i。

（d）如果f? ′i > fi，說明新個(gè)體的劃分比舊個(gè)體更優(yōu)，用其代替舊個(gè)體。反之，采用P = exp（（fi - f? ′i）T）的概率從新舊個(gè)體中進(jìn)行選擇。

（e）如果存在gen < MG，此時(shí)gen = gen + 1，向上跳轉(zhuǎn)到c。

（f）如果存在Ti < Tend，此時(shí)的解就是最優(yōu)解;反之，向上跳轉(zhuǎn)到c。

（2）社團(tuán)間可靠性分析與備份方法：

（a）使用公式（4）計(jì)算社團(tuán)的可靠性;

（b）將可靠性最低的W個(gè)社團(tuán)的外鏈邊及其相連的節(jié)點(diǎn)，進(jìn)行備份;

（3）對(duì)每一個(gè)社團(tuán)，進(jìn)行社團(tuán)內(nèi)可靠性分析與備份：

（a）使用公式（5）計(jì)算內(nèi)部節(jié)點(diǎn)可靠性;

（b）將可靠性最低的Z個(gè)內(nèi)部節(jié)點(diǎn)，進(jìn)行備份。

在步驟1中，主要包括控制參數(shù)初始化（過程a）、計(jì)算適應(yīng)度值（過程b）、個(gè)體的隸屬度評(píng)價(jià)（過程c）、更新個(gè)體（過程d）四個(gè)主要過程。在步驟2中，主要包括計(jì)算社團(tuán)的可靠性（過程a）、對(duì)可靠性最低的W個(gè)社團(tuán)的外鏈邊及其相連的節(jié)點(diǎn)進(jìn)行備份（過程b）兩個(gè)主要過程。在步驟3中，主要包括計(jì)算內(nèi)部節(jié)點(diǎn)中心度（過程a）、可靠性最低的內(nèi)部節(jié)點(diǎn)進(jìn)行備份（過程b）。

3? ?仿? ?真

3.1? ?環(huán)境

實(shí)驗(yàn)部分使用BRITE工具生成電力通信網(wǎng)環(huán)境[12]。為了驗(yàn)證不同網(wǎng)絡(luò)規(guī)模下算法的性能。實(shí)驗(yàn)中，使用了100個(gè)到500個(gè)之間變化的網(wǎng)絡(luò)節(jié)點(diǎn)環(huán)境。為了驗(yàn)證網(wǎng)絡(luò)的可靠性，采用端到端的最短路徑模擬電力通信業(yè)務(wù)。其中，電力業(yè)務(wù)的源節(jié)點(diǎn)使用隨機(jī)選擇的10%網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行模擬，電力業(yè)務(wù)的終點(diǎn)使用除源節(jié)點(diǎn)之外的互不相同的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行模擬。

在算法性能分析時(shí)，將本算法ROAoIC與傳統(tǒng)算法ROAnoC進(jìn)行比較。其中，傳統(tǒng)算法ROAnoC是指僅僅基于網(wǎng)絡(luò)節(jié)點(diǎn)的特性進(jìn)行備份，而不采用聚類算法對(duì)網(wǎng)絡(luò)進(jìn)行劃分。評(píng)價(jià)指標(biāo)包括備份資源數(shù)量在總資源中的占比、網(wǎng)絡(luò)連通度。其中，備份資源數(shù)量在總資源中的占比是指社團(tuán)中的備份資源、社團(tuán)之間的備份資源在總的資源中的比例。網(wǎng)絡(luò)連通度是指電力通信網(wǎng)節(jié)點(diǎn)和鏈路產(chǎn)生故障后，網(wǎng)絡(luò)最大連通分量的節(jié)點(diǎn)數(shù) 與電力通信網(wǎng)的節(jié)點(diǎn)總數(shù) 的比值，使用S（G）表示，采用公式（6）計(jì)算。其中，Sf （G） = ■表示網(wǎng)絡(luò)故障后的網(wǎng)絡(luò)連通度，So （G）表示網(wǎng)絡(luò)無故障時(shí)的網(wǎng)絡(luò)連通度。

S（G） = ■? ? ? ?（6）

為了驗(yàn)證網(wǎng)絡(luò)的可靠性，采用的攻擊模型分為隨機(jī)性攻擊和選擇性攻擊兩種。隨機(jī)性攻擊的對(duì)象是從網(wǎng)絡(luò)資源中隨機(jī)選取。選擇性攻擊是以較大的概率從社團(tuán)間的可靠性較低的鏈路中、或從社團(tuán)內(nèi)部可靠性較低的網(wǎng)絡(luò)資源中選擇被攻擊的對(duì)象。

3.2? ?結(jié)果分析

（1）備份資源數(shù)量

備份資源數(shù)量比較的實(shí)驗(yàn)結(jié)果如圖1所示，其中，x軸表示網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模，y軸表示備份資源數(shù)量。從圖可知，本算法ROAoIC的備份資源量與傳統(tǒng)算法ROAnoC的備份資源量都維持在25%左右。說明兩種算法對(duì)網(wǎng)絡(luò)資源的利用率相近。

（2）隨機(jī)性攻擊環(huán)境下的網(wǎng)絡(luò)連通度

隨機(jī)性攻擊環(huán)境下的網(wǎng)絡(luò)連通度比較的實(shí)驗(yàn)結(jié)果如圖2所示，其中，x軸表示網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模，y軸表示隨機(jī)性攻擊環(huán)境下的網(wǎng)絡(luò)連通度。從圖可知，本算法ROAoIC的網(wǎng)絡(luò)連通度維持在0.77左右，傳統(tǒng)算法ROAnoC的網(wǎng)絡(luò)連通度維持在0.57左右。說明本算法有效提升了隨機(jī)性攻擊環(huán)境下的網(wǎng)絡(luò)連通度。

（3）選擇性攻擊環(huán)境下的連通度

選擇性攻擊環(huán)境下的網(wǎng)絡(luò)連通度比較的實(shí)驗(yàn)結(jié)果如圖3所示，其中，x軸表示網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模，y軸表示選擇性攻擊環(huán)境下的網(wǎng)絡(luò)連通度。從圖可知，本算法ROAoIC的網(wǎng)絡(luò)連通度維持在0.62左右，傳統(tǒng)算法ROAnoC的網(wǎng)絡(luò)連通度維持在0.43左右。說明本算法有效提升了選擇性攻擊環(huán)境下的網(wǎng)絡(luò)連通度。

4? ?結(jié)? ?論

隨著電力通信網(wǎng)的規(guī)模逐漸擴(kuò)大，電力通信網(wǎng)在智能電網(wǎng)中的作用越來越重要。電力通信網(wǎng)的可靠性優(yōu)化已成為一個(gè)重要的研究?jī)?nèi)容。為解決大規(guī)模環(huán)境下的網(wǎng)絡(luò)可靠性優(yōu)化問題，采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個(gè)社團(tuán)，提出了基于改進(jìn)聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法。通過仿真實(shí)驗(yàn)，驗(yàn)證了本算法有效提升了電力通信網(wǎng)的可靠性。但是在資源備份方面，與已有算法一樣，需要備份較多的資源，導(dǎo)致網(wǎng)絡(luò)資源利用率降低。

參考文獻(xiàn)

[1]? ? 石天偉.電力通信網(wǎng)可靠性分析[J]. 通訊世界，2016，（10）：20-22.

[2]? ? 楊林慧，孫少華.電力通信網(wǎng)節(jié)點(diǎn)重要度的評(píng)估算法[J]. 智能電網(wǎng)，2017，5（07）：656-659.

[3]? ? 孫方楠，梁后健，張課，等. 基于改進(jìn)遺傳算法的電力通信網(wǎng)路由優(yōu)化研究[J].? 自動(dòng)化與儀器儀表，2018，（6）：25-28.

[4]? ? 朱明波. 基于遺傳算法的計(jì)算機(jī)網(wǎng)絡(luò)可靠性優(yōu)化設(shè)計(jì)[J].? 課程教育研究，2018，（19）：232-234.

[5]? ? 曾偉忠，袁詠詩. 兼顧可靠性與通信效率的電力通信網(wǎng)絡(luò)協(xié)調(diào)優(yōu)化方法[J].? 電氣自動(dòng)化，2018，40（4）：102-104.

[6]? ? 陳紹南，李克文，秦麗文，等. 考慮不規(guī)則風(fēng)速概率分布特性的配電系統(tǒng)可靠性評(píng)估[J].? 廣西電力，2019，42（2）：17-21.

[7]? ? 郭經(jīng)，劉文霞，張建華，等. 計(jì)及控制功能失效的微電網(wǎng)信息物理系統(tǒng)可靠性評(píng)估[J].? 現(xiàn)代電力，2019，36（2）：73-80.

[8]? ? 吳路明，裘愉濤，陳琦. 基于 SDN 的電力通信網(wǎng)絡(luò)關(guān)鍵技術(shù)綜述[J].? 江蘇電機(jī)工程，2018，（03）：134-144.

[9]? ? 呂順利，楊濟(jì)海，鄧偉，等. Apriori-AHP 算法在電力通信網(wǎng)業(yè)務(wù)風(fēng)險(xiǎn)評(píng)估中的研究及應(yīng)用[J].? 計(jì)算機(jī)與數(shù)字工程，2018，46（4）：667-671.

[10]? 尹軍，李炅菊，黃宏光. 基于鏈路已用率的電力通信網(wǎng)脆弱性分析[J].? 電力系統(tǒng)保護(hù)與控制，2018，46（2）：31-36.

[11]? WU X，KUMAR V，QUINLAN J R，et al. Top 10 algorithms in data mining[J].Knowledge & Information Systems，2008，14（ 1）：15-36.

[12]? Brite. http：//www.cs.bu.edu/brite/.