[發(fā)明專利]一種基于免疫算法的電力通信網(wǎng)接入點的選址規(guī)劃方法

在審

• 申請?zhí)枺?/td>: 201610035168.5
• 申請日: 2016-01-19
• 公開（公告）號: CN105719016A
• 公開（公告）日: 2016-06-29
• 發(fā)明（設(shè)計）人: 霍朝輝;步冬靜;江龍才;湯中會;牛景平;程洪;陳亨波;朱曉東;吳齊
• 申請（專利權(quán)）人: 國家電網(wǎng)公司;國網(wǎng)安徽省電力公司池州供電公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/06;G06Q50/30;H02J13/00
• 代理公司: 安徽省合肥新安專利代理有限責任公司 34101
• 代理人: 陸麗莉;何梅生

1.一種基于免疫算法的電力通信網(wǎng)接入點的選址規(guī)劃方法，是應(yīng)用于電力通信網(wǎng)與外部業(yè)務(wù)系統(tǒng)進行數(shù)據(jù)通信的網(wǎng)絡(luò)環(huán)境中，其特征是，所述選址規(guī)劃方法是按如下步驟進行：

步驟1、使用無向圖G(E,L)表示電力通信網(wǎng)的拓撲結(jié)構(gòu)；E和L分別表示所述電力通信網(wǎng)的終端節(jié)點集和鏈路集；并有，E＝{e₁,e₂,…,e_i,…e_n}；e_i表示第i個終端節(jié)點；1≤i≤n；n表示終端節(jié)點的個數(shù)；將所述鏈路集L中任意一條鏈路表示為l，l∈L；

假設(shè)所述電力通信網(wǎng)的終端節(jié)點集E中部署N個接入點；則由N個接入點形成M條路由P；假設(shè)選擇第s個終端節(jié)點e_s為第j個接入點；1≤s≤n；1≤j≤N；則所述第i個終端節(jié)點e_i到第j個接入點的路由表示為p_i,j，并有表示所述第i個終端節(jié)點e_i到第j個接入點的路由p_i,j中第k條鏈路；1≤k≤m；m表示所述第i個終端節(jié)點e_i到第j個接入點的路由p_i,j中鏈路的總數(shù)；

步驟2、利用式(1)計算所述電力通信網(wǎng)的建設(shè)成本C：

C=Σi=1nci×xi---(1)]]>

式(1)中，c_i表示在第i個終端節(jié)點e_i上部署接入點的開銷；x_i∈{0,1}；當x_i＝1時，表示在第i個終端節(jié)點e_i上部署接入點，當x_i＝0時，表示第i個終端節(jié)點e_i不部署接入點；

步驟3、利用式(2)計算第i個終端節(jié)點e_i到第j個接入點e_j的路由p_i,j的可靠性r_i,j：

ri,j=Πvk∈pi,jrvk(i,j)---(2)]]>

式(2)中，表示所述第i個終端節(jié)點e_i到第j個接入點的路由p_i,j中第k條鏈路的可靠性；

步驟4、利用式(3)和式(4)計算所述電力通信網(wǎng)的平均可靠性

R‾=1M×Σpi,j∈PMΣi=1nyi,j×ri,j---(3)]]>

Σi=1nyi,j=1---(4)]]>

式(3)中，y_i,j∈{0,1}，當y_i,j＝1時，表示通過路由p_i,j轉(zhuǎn)發(fā)第i個終端節(jié)點e_i的流量；當y_i,j＝0時，表示沒有通過路由p_i,j轉(zhuǎn)發(fā)第i個終端節(jié)點e_i的流量；

式(4)表示任意個終端節(jié)點和第j個接入點之間只有一個路由；

步驟5、假設(shè)所述鏈路集L中任意一條鏈路l發(fā)生故障，則利用式(5)和式(6)計算所述電力通信網(wǎng)的平均可靠性

R‾l=1M×Σpi,j∈PlMΣi=1nyi,jl×ri,j---(5)]]>

Σi=1nyi,jl=1---(6)]]>

式(5)中，當時，表示當鏈路l發(fā)生故障時，通過路由p_i,j轉(zhuǎn)發(fā)第i個終端節(jié)點e_i的流量；當時，表示當鏈路l發(fā)生故障時，沒有通過路由p_i,j轉(zhuǎn)發(fā)第i個終端節(jié)點e_i的流量；P^l表示當鏈路l發(fā)生故障時，由N個接入點形成M條路由；

步驟6、利用式(7)計算數(shù)據(jù)包經(jīng)過路由p_i,j發(fā)送至外部業(yè)務(wù)系統(tǒng)的總時延

tpi,j=ta+m×ttra+tpro×Σk=1mlenk(i,j)---(7)]]>

式(7)中，表示數(shù)據(jù)包到達路由p_i,j中第k條鏈路時所需等到的隊列長度；t_tra表示數(shù)據(jù)包在一條鏈路中的傳輸時延；t_pro表示一個終端節(jié)點響應(yīng)數(shù)據(jù)包的處理時延；t_a表示數(shù)據(jù)包從接入點發(fā)送至外部業(yè)務(wù)系統(tǒng)的傳輸時延；

步驟7、利用式(8)計算經(jīng)過M條路由P傳送數(shù)據(jù)包到外部系統(tǒng)的平均時延

t‾=1M×ΣPi,j∈P(ta+m×ttra+tpro×Σk=1mlenk(i,j))---(8)]]>

步驟8、利用式(9)獲得接入點選址規(guī)劃的數(shù)學模型：

minC=Σi=1nci×xi]]>

s.t.R‾=1M×Σpi,j∈PMΣi=1nyi,j×ri,j≥μΣi=1nyi,j=1R‾l=1M×Σpi,j∈PlMΣi=1nyi,j′×ri,j≥μlΣi=1nyi,jl=1t‾=1M×ΣPi,j∈P(ta+m×ttra+tpro×Σk=1mlenk(i,j))≤τ---(9)]]>

式(9)中，μ表示網(wǎng)絡(luò)可靠性閾值，μ^l表示當鏈路l發(fā)生故障時，網(wǎng)絡(luò)可靠性閾值，τ表示網(wǎng)絡(luò)時延閾值；

步驟9、參數(shù)設(shè)置：

根據(jù)電力通信網(wǎng)的規(guī)模設(shè)定種群規(guī)模為N_R；

定義記憶細胞數(shù)量為N_m、最大迭代次數(shù)為ω、進化次數(shù)為t；

初始化N_R＝α、N_m＝β、ω＝λ、t＝0、θ＝a、

步驟10、以所述數(shù)學模型為抗原，將隨機生成α個抗體的初始抗體群；

步驟11、抗體評價

計算抗體與抗原間的親和度以及抗體與抗體之間的親和度，從而計算抗體濃度和期望繁殖概率；

步驟12、生成記憶細胞

將抗體與抗原的親和度進行降序排序，取前β個抗體作為記憶細胞；

步驟13、形成父代子群

根據(jù)抗體與抗原的親和度與抗體濃度的比值獲得抗體的遺傳率；將抗體的遺傳率按降序排序，并提取前α-β個抗體作為父代種群；對父代種群進行克隆形成父代子群；

步驟14、群體更新

對所述父代子群中的抗體進行變異，變異后的抗體按比例接種局部疫苗，從而生成新群體，將所述記憶細胞加入所述新群體組成新一代抗體群；

步驟15、判斷t＞λ是否成立，若成立，則將所述新一代抗體群作為最優(yōu)解輸出；否則，將t+1賦值給t，并返回步驟11順序執(zhí)行。