付佳佳　吳贊紅　施展

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

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

中圖分類號：TP393? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：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]、同時優(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)可靠性評估[7]。另外，在電力設(shè)備可靠性提升方面引入了一些新技術(shù)，例如SDN技術(shù)已成為新型網(wǎng)絡(luò)可靠性的關(guān)鍵技術(shù)[8]、基于關(guān)聯(lián)規(guī)則的Apriori-AHP算法的主動可靠性保障技術(shù)[9]、使用鏈路已使用情況進(jìn)行網(wǎng)絡(luò)可靠性研究的方法[10]。

已有研究分析可知，在電力通信網(wǎng)的可靠性研究方面已經(jīng)取得了較好的研究成果。但是，已有算法主要關(guān)注新的方法和技術(shù)在電力通信網(wǎng)可靠性提升方面的應(yīng)用。在電力通信網(wǎng)規(guī)模越來越大的趨勢下，急需能夠有效解決大規(guī)模環(huán)境下網(wǎng)絡(luò)可靠性問題的研究成果。為此，采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個社團(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ù)提供計算服務(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）是一個非常關(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ī)模較大，如果通過算法對整個電力通信網(wǎng)的屬性進(jìn)行分析，會導(dǎo)致運(yùn)算復(fù)雜度較高。為此，采用聚類算法，發(fā)掘網(wǎng)絡(luò)節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系，從而將電力通信網(wǎng)劃分為多個小規(guī)模的網(wǎng)絡(luò)。因?yàn)槟：鼵-均值聚類（FCM）具有運(yùn)算速度快、分類結(jié)果較好等優(yōu)點(diǎn)[11]，本文采用FCM算法對電力通信網(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）個節(jié)點(diǎn)集合，則使用U = {A1，A2，…，Ac}表示劃分后的網(wǎng)絡(luò)節(jié)點(diǎn)子集合。子集合的中心使用{k1，k2，…，kc}表示。為了評判子集合的劃分效果，定義目標(biāo)函數(shù)Jb并使用公式（1）評判聚類劃分的效果。其中，μk（xi）表示各個網(wǎng)絡(luò)節(jié)點(diǎn)vi相對于類Ak的隸屬度（簡化標(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)。為此，基于模擬退火算法與遺傳算法對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)可靠性分析與備份方法三個步驟。下面首先對三個步驟的關(guān)鍵知識進(jìn)行詳細(xì)描述，之后對算法過程進(jìn)行分析。

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

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

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

μik = ■? ? ?（2）

vij = ■? ? ?（3）

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

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

在社團(tuán)間可靠性提升時，以當(dāng)前社團(tuán)的外鏈邊數(shù)在所有社團(tuán)的外鏈邊數(shù)的比值進(jìn)行衡量，稱為社團(tuán)外鏈能力。此時，社團(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）計算社團(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)劃分的計算過程可知，在每個社團(tuán)內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)的距離較近，關(guān)聯(lián)性較高。所以，在分析社團(tuán)內(nèi)的可靠性時，采用內(nèi)部節(jié)點(diǎn)中心度進(jìn)行衡量。使用公式（5）計算每個社團(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)化算法包括三個步驟。（1）、采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為K個社團(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個社團(tuán);

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

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

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

和f? ′i。

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

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

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

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

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

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

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

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

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

在步驟1中，主要包括控制參數(shù)初始化（過程a）、計算適應(yīng)度值（過程b）、個體的隸屬度評價（過程c）、更新個體（過程d）四個主要過程。在步驟2中，主要包括計算社團(tuán)的可靠性（過程a）、對可靠性最低的W個社團(tuán)的外鏈邊及其相連的節(jié)點(diǎn)進(jìn)行備份（過程b）兩個主要過程。在步驟3中，主要包括計算內(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個到500個之間變化的網(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)行模擬。

在算法性能分析時，將本算法ROAoIC與傳統(tǒng)算法ROAnoC進(jìn)行比較。其中，傳統(tǒng)算法ROAnoC是指僅僅基于網(wǎng)絡(luò)節(jié)點(diǎn)的特性進(jìn)行備份，而不采用聚類算法對網(wǎng)絡(luò)進(jìn)行劃分。評價指標(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）計算。其中，Sf （G） = ■表示網(wǎng)絡(luò)故障后的網(wǎng)絡(luò)連通度，So （G）表示網(wǎng)絡(luò)無故障時的網(wǎng)絡(luò)連通度。

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

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

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%左右。說明兩種算法對網(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)化已成為一個重要的研究內(nèi)容。為解決大規(guī)模環(huán)境下的網(wǎng)絡(luò)可靠性優(yōu)化問題，采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個社團(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)重要度的評估算法[J]. 智能電網(wǎng)，2017，5（07）：656-659.

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

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

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

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

[7]? ? 郭經(jīng)，劉文霞，張建華，等. 計及控制功能失效的微電網(wǎng)信息物理系統(tǒ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)險評估中的研究及應(yīng)用[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/.