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

付佳佳　吳贊紅　施展

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

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

中圖分類號：TP393? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：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)用，實際環(huán)境中電力通信網(wǎng)的管理和維護更加困難，迫切需要可以應(yīng)用于實際環(huán)境下的電力通信網(wǎng)的可靠性分析方法[1-2]。在網(wǎng)絡(luò)可靠性提升方面，典型的研究成果包括采用遺傳算法優(yōu)化路由策略從而實現(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)化策略實現(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]、使用鏈路已使用情況進行網(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ò)劃分為多個社團，提出了基于改進聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法。通過仿真實驗，驗證了本算法有效提升了電力通信網(wǎng)的可靠性。

1? ?問題描述

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

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

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

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

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

2? ?算? ?法

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

2.1? ? 社團劃分

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

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

μik = ■? ? ?（2）

vij = ■? ? ?（3）

2.2? ?社團間可靠性分析與備份方法

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

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

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

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

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

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個社團;（2）、社團間可靠性分析與備份;（3）、社團內(nèi)可靠性分析與備份。算法描述如表1所示。

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

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

絡(luò)劃分為K個社團;

（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）的概率從新舊個體中進行選擇。

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

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

（2）社團間可靠性分析與備份方法：

（a）使用公式（4）計算社團的可靠性;

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

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

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

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

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

3? ?仿? ?真

3.1? ?環(huán)境

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

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

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

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

3.2? ?結(jié)果分析

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

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

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

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

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

選擇性攻擊環(huán)境下的網(wǎng)絡(luò)連通度比較的實驗結(jié)果如圖3所示，其中，x軸表示網(wǎng)絡(luò)節(jié)點規(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ī)模逐漸擴大，電力通信網(wǎng)在智能電網(wǎng)中的作用越來越重要。電力通信網(wǎng)的可靠性優(yōu)化已成為一個重要的研究內(nèi)容。為解決大規(guī)模環(huán)境下的網(wǎng)絡(luò)可靠性優(yōu)化問題，采用模擬退火算法與遺傳算法結(jié)合的FCM算法將大規(guī)模網(wǎng)絡(luò)劃分為多個社團，提出了基于改進聚類算法的電力通信網(wǎng)可靠性優(yōu)化算法。通過仿真實驗，驗證了本算法有效提升了電力通信網(wǎng)的可靠性。但是在資源備份方面，與已有算法一樣，需要備份較多的資源，導(dǎo)致網(wǎng)絡(luò)資源利用率降低。

參考文獻

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

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

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

[4]? ? 朱明波. 基于遺傳算法的計算機網(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ī)則風速概率分布特性的配電系統(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].? 江蘇電機工程，2018，（03）：134-144.

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

[10]? 尹軍，李炅菊，黃宏光. 基于鏈路已用率的電力通信網(wǎng)脆弱性分析[J].? 電力系統(tǒng)保護與控制，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/.