[发明专利]一种基于免疫算法的电力通信网接入点的选址规划方法

摘要

本发明公开了一种基于免疫算法的电力通信网接入点的选址规划方法，其特征包括：1、确定接入点选址网络模型；2、建立接入点选址数学模型，包括成本、可靠性、时延和N‑1原则约束；3、对免疫算法中抗体、抗原相关概念进行定义，使其符合接入点选址问题的要求；4、设置免疫算法的参数，初始化抗体种群；5、对抗体种群进行克隆、变异和选择，形成新一代种群；6、判断迭代终止条件，若满足则结束迭代，否则继续步骤；7、获得最优接入点选址方案。本发明能够在综合考虑经济建设成本、网络可靠性、N‑1原则以及网络时延约束下保证电力通信网可靠有效的通信。

主权项

一种基于免疫算法的电力通信网接入点的选址规划方法，是应用于电力通信网与外部业务系统进行数据通信的网络环境中，其特征是，所述选址规划方法是按如下步骤进行：步骤1、使用无向图G(E,L)表示电力通信网的拓扑结构；E和L分别表示所述电力通信网的终端节点集和链路集；并有，E＝{e₁,e₂,…,e_i,…e_n}；e_i表示第i个终端节点；1≤i≤n；n表示终端节点的个数；将所述链路集L中任意一条链路表示为l，l∈L；假设所述电力通信网的终端节点集E中部署N个接入点；则由N个接入点形成M条路由P；假设选择第s个终端节点e_s为第j个接入点；1≤s≤n；1≤j≤N；则所述第i个终端节点e_i到第j个接入点的路由表示为p_i,j，并有表示所述第i个终端节点e_i到第j个接入点的路由p_i,j中第k条链路；1≤k≤m；m表示所述第i个终端节点e_i到第j个接入点的路由p_i,j中链路的总数；步骤2、利用式(1)计算所述电力通信网的建设成本C：$C=\underset{i=1}{\overset{n}{\Σ}}{c}_i\×x_i---\left(1\right)$式(1)中，c_i表示在第i个终端节点e_i上部署接入点的开销；x_i∈{0,1}；当x_i＝1时，表示在第i个终端节点e_i上部署接入点，当x_i＝0时，表示第i个终端节点e_i不部署接入点；步骤3、利用式(2)计算第i个终端节点e_i到第j个接入点e_j的路由p_i,j的可靠性r_i,j：$r_{i,j}=\underset{v_k\∈p_{i,j}}{\Π}{r}_{v_k}^{(i,j)}---\left(2\right)$式(2)中，表示所述第i个终端节点e_i到第j个接入点的路由p_i,j中第k条链路的可靠性；步骤4、利用式(3)和式(4)计算所述电力通信网的平均可靠性$\stackrel{\‾}{R}=\frac{1}{M}\×\underset{p_{i,j}\∈P}{\overset{M}{\Σ}}\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}\×r_{i,j}---\left(3\right)$$\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}=1---\left(4\right)$式(3)中，y_i,j∈{0,1}，当y_i,j＝1时，表示通过路由p_i,j转发第i个终端节点e_i的流量；当y_i,j＝0时，表示没有通过路由p_i,j转发第i个终端节点e_i的流量；式(4)表示任意个终端节点和第j个接入点之间只有一个路由；步骤5、假设所述链路集L中任意一条链路l发生故障，则利用式(5)和式(6)计算所述电力通信网的平均可靠性${\stackrel{\‾}{R}}^l=\frac{1}{M}\×\underset{p_{i,j}\∈P^l}{\overset{M}{\Σ}}\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}^l\×r_{i,j}---\left(5\right)$$\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}^l=1---\left(6\right)$式(5)中，当时，表示当链路l发生故障时，通过路由p_i,j转发第i个终端节点e_i的流量；当时，表示当链路l发生故障时，没有通过路由p_i,j转发第i个终端节点e_i的流量；P^l表示当链路l发生故障时，由N个接入点形成M条路由；步骤6、利用式(7)计算数据包经过路由p_i,j发送至外部业务系统的总时延$t_{p_{i,j}}=t_a+m\×t_{tra}+t_{pro}\×\underset{k=1}{\overset{m}{\Σ}}{\mathrm{len}}_k^{(i,j)}---\left(7\right)$式(7)中，表示数据包到达路由p_i,j中第k条链路时所需等到的队列长度；t_tra表示数据包在一条链路中的传输时延；t_pro表示一个终端节点响应数据包的处理时延；t_a表示数据包从接入点发送至外部业务系统的传输时延；步骤7、利用式(8)计算经过M条路由P传送数据包到外部系统的平均时延$\stackrel{\‾}{t}=\frac{1}{M}\×\underset{P_{i,j}\∈P}{\Σ}(t_a+m\×t_{tra}+t_{pro}\×\underset{k=1}{\overset{m}{\Σ}}{\mathrm{len}}_k^{(i,j)})---\left(8\right)$步骤8、利用式(9)获得接入点选址规划的数学模型：$\min C=\underset{i=1}{\overset{n}{\Σ}}{c}_i\×x_i$$s.t.\left\{\begin{array}{c}\stackrel{\‾}{R}=\frac{1}{M}\×\underset{p_{i,j}\∈P}{\overset{M}{\Σ}}\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}\×r_{i,j}\≥\mathrm{\μ}\\ \underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}=1\\ {\stackrel{\‾}{R}}^l=\frac{1}{M}\×\underset{p_{i,j}\∈P^l}{\overset{M}{\Σ}}\underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}^{\′}\×r_{i,j}\≥{\mathrm{\μ}}^l\\ \underset{i=1}{\overset{n}{\Σ}}{y}_{i,j}^l=1\\ \stackrel{\‾}{t}=\frac{1}{M}\×\underset{P_{i,j}\∈P}{\Σ}(t_a+m\×t_{tra}+t_{pro}\×\underset{k=1}{\overset{m}{\Σ}}{\mathrm{len}}_k^{(i,j)})\≤\mathrm{\τ}\end{array}\right.---\left(9\right)$式(9)中，μ表示网络可靠性阈值，μ^l表示当链路l发生故障时，网络可靠性阈值，τ表示网络时延阈值；步骤9、参数设置：根据电力通信网的规模设定种群规模为N_R；定义记忆细胞数量为N_m、最大迭代次数为ω、进化次数为t；初始化N_R＝α、N_m＝β、ω＝λ、t＝0、θ＝a、步骤10、以所述数学模型为抗原，将随机生成α个抗体的初始抗体群；步骤11、抗体评价计算抗体与抗原间的亲和度以及抗体与抗体之间的亲和度，从而计算抗体浓度和期望繁殖概率；步骤12、生成记忆细胞将抗体与抗原的亲和度进行降序排序，取前β个抗体作为记忆细胞；步骤13、形成父代子群根据抗体与抗原的亲和度与抗体浓度的比值获得抗体的遗传率；将抗体的遗传率按降序排序，并提取前α‑β个抗体作为父代种群；对父代种群进行克隆形成父代子群；步骤14、群体更新对所述父代子群中的抗体进行变异，变异后的抗体按比例接种局部疫苗，从而生成新群体，将所述记忆细胞加入所述新群体组成新一代抗体群；步骤15、判断t＞λ是否成立，若成立，则将所述新一代抗体群作为最优解输出；否则，将t+1赋值给t，并返回步骤11顺序执行。