基于免疫－蚁群算法的电力线载波抄表动态路由方法.pdf

基于免疫-蚁群算法的电力线载波抄表动态路由方法 高 庆， 等 基于免疫基于免疫-蚁群算法的电力线载波抄表动态路由方法蚁群算法的电力线载波抄表动态路由方法 高庆，吕霞付 （重庆邮电大学重庆，400065） 摘要：针对低压电力线载波抄表系统中现有的中继路由算法的不足，提出了一种基于免疫-蚁群算法的低压电力线载 波抄表动态路由方法。免疫算法把目标函数和约束条件作为抗原，目标函数的优化解对应为抗体，利用蚁群算法产生和更 新抗体，抗体的交叉操作及其对与抗原具有高亲和力的抗体的记忆，均能促进快速求解。该算法结合了人工免疫算法与蚁 群算法两者的优点。通过仿真实验验证该算法的收敛性、抗毁性和运算性能，算法能够根据低压电力线信道的变化情况以 相对较少的迭代次数收敛到最优路径，提高整个低压电力线载波抄表系统的时效性。 关键词：低压电力线载波；抄表；免疫-蚁群算法；动态中继路由 AbstractAbstract： In view of the shortcoming of the current relay routing algorithm in the low-voltage power line carrier meter reading system, the method of relay routing based on immune-ant algorithm was proposed. Immune algorithm makes object function and subject term as antigen and the object function corresponds to the antibody, Ant algorithm generates and renews antibody, the cross of antibody and the memory of antibody of high affinity can promote the solving process. The immune-ant algorithm has advantages of both. Covergence, invulnerability and performance were analyzed and tested by simulation experiments. Algorithm can accord the changes of low-voltage power line channel with relatively little iterations to obtain the optimal path, and the timeliness of the meter reading system is improved. Key words:Key words: Low-voltage power line carrier; Meter reading; Immune-ant algorithm; Dynamic relay routing 中图分类号：TM74文献标识码：B文章编号：1001-9227（2014）01-0108-04 收稿日期：2013-11-13 作者简介：高庆（1986-） ，男，硕士研究生，主要研究方 向为电力线载波通信、智能仪器仪表。 0引言 电力线载波通信，是以输电线路为载波信号的传输媒介的 电力系统通信，是电力系统特有的通信方式。由于采用电力线 通信综合成本低、易施工、不受环境条件限制等优点，是自动 抄表系统的发展趋势。低压电力线具有高噪声、高衰减和高时 变等特性，不仅制约了信号传输的距离，也使得低压电力线通 信的可靠性大大降低，进而影响抄表范围和抄表成功率。提高 电力线通信可靠性方面的研究主要有两大方向，即增强物理层 通信能力和建立网络中继（路由） 。对提高物理层通信能力的 研究主要集中在信道特性、噪声、衰减、信道编码和信号调制 方式等方面1-3。目前，许多学者对低压电力线载波通信自动中 继进行了深入研究，提出了多种中继方法，俞天白等针对楼宇 控制系统中的电力线载波通信提出了一种基于传输矩阵的动态 路由算法4，实现了节点的即插即用。刘晓胜等提出了一种基 于蚁群算法的自动组网方法5，并通过仿真验证该算法的有效 性和抗毁性，可有效延长电力线载波通信距离。以上方法从一 定程度上解决了抄表范围和抄表成功率等问题，但均有一些缺 陷：文献4中的方法虽然实现了节点的即插即用，但是算法的 效率较低；文献5中的方法虽然能动态适应电力线环境的变 化，但算法的收敛速度较慢，并且容易陷入局部极小值。针对 以上问题，本文提出了一种基于免疫-蚁群算法的低压电力线 载波抄表动态路由方法，在蚁群算法的基础上，免疫算法把目 标函数和约束条件作为抗原，目标函数的优化解对应为抗体， 并记忆与抗原具有高亲和力的抗体，交叉操作增强了抗原识 别、记忆和调节功能，促进快速求解，最终获得最优的路由线 路。该方法简单易行，为低压电力线载波通信抄表系统的动态 组网和通信可靠性，提供了一种有效的方法。 1低压电力线载波抄表系统网络拓扑结构 一般而言，楼宇内低压电力线网络的典型拓扑结构为混合 树型拓扑结构。在抄表系统中，下行线路的整个网络主要由集 中器和一定数量的电表组成，在逻辑拓扑结构中可以将集中器 视作网关，每个电表视为可通信的终端节点。值得注意的是， 10KV高压上行线路经过变压器降压后，为三相220V的低压 线路，然而电力线通信是不能跨相的。从逻辑拓扑结构来说， 三相之间为并列且相对独立的关系，那么以其中一相的逻辑拓 扑作为研究对象，则可以代表其他两相线路的拓扑结构。图1 给出了树型结构的低压电力线载波抄表网络逻辑拓扑结构图， 1号节点为集中器，2-50号节点代表抄表系统中的载波电表。 1 2 3 5 4 6 7 1 5 1 6 2 4 2 5 3 2 3 3 4 0 4 1 8 9 1 0 1 1 1 72 63 44 2 1 83 54 34 7 4 44 81 92 7 2 02 83 6 1 22 12 93 7 1 3 1 4 2 2 2 3 3 0 3 1 3 8 3 94 5 4 6 4 9 5 0 图1低压电力线载波抄表网络树形拓扑 108 学兔兔 w w w .x u e t u t u .c o m 自动化与仪器仪表 2014年第1期 （总第171期） 2算法原理 2.1免疫算法原理 免疫算法6中的抗原通常是目标函数；抗体通常是指目标 函数的优化解。算法的具体步骤如下： （1）识别抗原：对实际问题进行抽象，产生最优化问题的 目标函数和约束条件。 （2）初始抗体的产生：如果记忆库中有初始抗体，则将记 忆库中的抗体看成是初始抗体的一部分，不足的部分，系统随 机产生。 （3）亲和力计算：计算抗原和抗体之间的亲和力。 （4）记忆细胞分化：与抗原有最大亲和力的抗体加入记忆 库。由于记忆库规模有限，新产生的与抗原具有更高亲和力的 抗体将替换与抗原具有较低亲和力的抗体。 （5）抗体促进和抑制：高亲和力抗体受到促进，高密度抗 体受到抑制。 （6）抗体更新：通过交叉和变异操作来产生新的抗体。 （7）若满足终止条件则结束，否则转（3） 。 2.2蚁群算法原理 蚁群算法7(antcolonyoptimization,ACO)，又称蚂蚁算 法，是受自然界中蚂蚁搜寻食物行为的启发而提出的一种并行 优化算法，由MacroDorigo 于1992年在他的博士论文中提出 的。蚁群算法利用单个人工蚂蚁迭代构筑和优化最优候选解； 人工信息素和基于问题的启发式信息指导人工蚂蚁寻找最优 解；当一只蚂蚁完成了它的一次完整搜寻过程，则它将在走过 的路径上释放信息素，作为比较理想的路径将从更多的蚂蚁处 得到信息素，从而使该部分路径得以加强；同时为了避免搜索 停止，路径上的信息素会按照某一系数挥发掉。该算法通过正 反馈、分布式协作来寻找最优路径，这是一种基于种群寻优的 启发式搜索算法。蚁群算法具有自组织性、并行性、正反馈性 和较强的鲁棒性，路由问题是该算法典型应用领域之一8。 3基于免疫-蚁群路由算法的特点及实现步骤 3.1路由算法的特点 由于低压电力线载波通信信道具有时变性、噪声高、衰减 大等特征，低压电力线载波抄表系统中集中器和载波电表之间 的连接关系是未知的，通信网络逻辑拓扑结构未知，因此路由 算法必须具有以下特点： (1)算法能够应对未知的、时变的低压电力线信道特征。由 于安装节点时并不清楚电力线的走线路径，且节点的通信距离 易受电力线上噪声的影响，电力线通道的时变性又有可能会破 坏节点间的传输路径，因此许多固定的网络路由算法并不能满 足抄表系统要求。路由算法需有对抄表系统网络探索和辨别的 能力，能够快速找到集中器到目标电表节点的之间的路由线 路，同时算法用具有路由优化能力，搜索并收敛于最优路径。 (2)算法具有较强的抗毁性。由于低压电力线具有噪声强、 衰减大、负载多、时延长等特征，以及抄表系统中网络电表节 点的接入、删除、存在硬件故障等情况，要求算法能够在通信 线路被改变或破坏时迅速重构，提高抄表系统的抗毁性。 3.2基于免疫-蚁群路由算法的实现步骤 3.2.1常用名词定义 （1）蚂蚁寿命：是指搜索蚂蚁数据帧能够被中继电表节点 转发的次数的上限。在实际抄表系统中，数据帧不能被无限制 的转发，尤其是对于窄带电力线载波通信，通信速率低，数据 帧转发次数受到较大的限制，否则占用信道时间过长，同时也 容易产生错误。考虑到约束条件，算法中定义蚂蚁寿命为7， 每转发一次该值减1，如果经历了7个电表节点之后，该搜索 蚂蚁没有找到目标电表节点，则设定该蚂蚁死亡，不在继续寻 找，工程应用中表现为舍弃该数据帧不再转发。 （2）跳数：是指集中器节点与目的电表节点通信时，数据 帧到达目的电表节点所需转发的次数。可以直接通信的节点， 跳数为0；需要通过1个中间电表节点转发通信的两个节点， 跳数为1，以此类推。 （3）通信距离：是指抄表系统中可以互相通信的两个节点 所跨过的节点个数加1。相邻两个节点的通信距离为1。该通 信距离随着低压电力线信道质量而变化。 3.2.2算法规则 （1） 抗体的编码形式为：A(L(f,n1,n2,.nk,a), life, jump, distance)，其中L(f,n1,n2,.nk,a)、life、jump、distance分别 表示路径、蚂蚁寿命、路由跳数、通信距离。 （2）抗原的编码形式为：R(from,aim,life,jump,distance)， 其中from、aim、life、jump、distance分别表示路由请求 的源节点、目的节点、蚂蚁寿命、路由跳数、通信距离。 （3）抗体与抗原的匹配规则：如果某抗体是以抗原的from 为起点、aim为终点，且满足上述的约束条件，则认为匹配， 否则认为不匹配。 （4）抗体的评价方法：对于多个抗体，通常根据抗体和抗 原间的亲和力的大小来判断哪一个是最优抗体（最优解） ，亲 和力的定义为： affinity=maxconst+llife-jjump-ddistance (1) 式中：maxconst是一个比较大的常数，l，j，d是常 数，算法中根据life、jump和distance的相对重要性来选择他 们的值。 （5）新抗体的产生和新群体的形成规则：利用蚁群算法产 生一批新的抗体，再把它们和局部记忆库中的现有抗体一起进 行配对、交叉产生一批新抗体；最后从新产生的抗体和局部记 忆库中的抗体中选取affinity值大的一批作为新抗体群。 （6）记忆库的设计和使用：算法中采用两个记忆库：局部 记忆库和全局记忆库。局部记忆库存储求解某个抗原过程中的 局部最优抗体，规模为10；全局记忆库存储针对某个抗原求得 的最优抗体，规模为5。 （7）抗体交叉规则：多个抗体随机配对后，在一对抗体中 寻找相同节点（源节点和目的节点除外） ，若有多个相同节点 就随机选择一个作为交叉点。例如A(2,5,6,9)和B(2,3,5,9)是配 对后的一对抗体，如果选择节点5作为交叉点，则交叉后将得 到两个新抗体C(2,5,9)和D(2,3,5,6,9)。 蚁群算法的三种主要规则： （1）状态转移规则 蚂蚁在节点i选择节点j的路径转移规则为： 109 学兔兔 w w w .x u e t u t u .c o m j= argmax ilil ,qq 0 pij k,qq 0 (2) pij k= ij ij lallowedk il il ,jallowedk 0,otherwise (3) 式中：q0(0q0q0时按照概率选择路径。 （2）局部信息素更新 对于第k只蚂蚁，如果节点i，j是它所选路径上的两个节 点，则 ij= (1-)ij+0,若i，j在路径上相邻 (1-)ij+b00，否则 （4） 式中：为局部信息挥发因子,且01；0为信息素初 始值；b0为常数,且0b01，是为了避免不同边上的信息素 两极分化，从而减少陷入局部极小点。局部更新规则有利于探 索未知的路径。 （3）全局信息素更新 当所有蚂蚁全部成功完成一次寻径行为后，选择最优路径 进行全局信息素的更新，规则如下： ij= (1-)ij+affinity，若i，j在路径上相邻 (1-)ij+b1affinity，否则 (5) 式中：为信息素挥发因子；b1为常数，且0b11，是 为了避免不同边上的信息素两极分化，从而减少陷入局部极小 点；affinity为最优抗体和抗原间的亲和力9。 3.2.3算法的实现步骤： （1）输入请求：输入请求R(from,aim,life,jump,distance)， 即路由请求的起点、终点、蚂蚁寿命、通信距离； （2）产生初始抗体：采用蚁群算法按照状态转移规则产生 一批初始抗体，并按公式（4）进行局部信息素更新； （3）抗体更新：利用蚁群算法对具体的路由请求产生一批 新抗体，并把它们和局部记忆库中现有的抗体进行配对，以概 率pc进行交叉运算，产生新抗体； （4）计算亲和力：按公式（1）计算新抗体中各个抗体和 抗原间的亲和力affinity； （5）局部记忆库更新：从本次新产生的抗体中，根据亲和 力的大小，选取一批较优的抗体存入局部记忆库中，根据本次 新加入局部记忆库中的那些抗体（局部最优抗体） ，按公式 （5）进行全局信息素更新； （6）判断终止条件：判断算法是否达到设定的迭代次数， 达到则转第8）步，否则转第3）步； （7）全局记忆库更新：用全局最优抗体取代全局记忆库中 最少被选为初始抗体的那个记忆细胞，并输出结果，结束循 环。 4仿真结果 本实验采用图1的逻辑拓扑结构，以MATLAB7.14为仿真 平台。假设：任意相邻的两个节点都能够保证电力线通信正确 可靠；通信逻辑拓扑图为无向图；每个节点有一个唯一的地址 编码。仿真实验中参数选择：maxconst=10000，l=100， j=100，d=10，b0=0.05，b1=0.05，蚂蚁数量m=35，交 叉概率pc=0.5，局部记忆库规模为10，全局记忆库规模为5， 蚂蚁寿命为la=7，信息启发式因子=1，期望启发式因子 =1， 状 态 转 移 因 子q0=0.05， 局 部 信 息 素 挥 发 因 子 =0.02， 全 局 信 息 素 挥 发 因 子=0.05， 信 息 素 强 度 Q=200，迭代次数T=50。 4.1算法的收敛性分析 算法的收敛性是衡量算法性能优劣的重要指标之一。分别 采用蚁群算法（ACA）和免疫-蚁群算法（I-A） ，从集中器节 点1到目的电表节点50的抄表路由路径进行仿真验证，假设节 点的通信距离为2，仿真结果如图2和图3所示。 图2搜索载波电表节点50的路由寻优结果 图3搜索载波电表节点50的仿真结果 图2为路由寻优结果，在100m100m的范围内放置50个 节点，分别对应图1逻辑拓扑结构中的节点150，节点的直接 通信距离为020m，连线部分即为算法的最终寻优路径。图3 中虚线部分表示蚁群算法(ACA)寻优结果，实线部分为免疫- 蚁群算法(I-A)仿真结果。由图3可知，两种算法经过不同的迭 代次数均能收敛到最优路径：1-8-26-44-50，免疫-蚁群算 法经16次迭代运算后收敛到最优解，而蚁群算法要经过22次 迭代后才能收敛到最优解。由仿真结果可知免疫-蚁群算法较 蚁群算法以更少的迭代次数收敛到最优路径，提高了效率，能 更好的适应于低压电力线载波抄表系统中继路由问题。 4.2算法的抗毁性分析 低压电力线的时变性和信道的时变性都会导致通信网络拓 扑结构发生变化，电表本身节点也存在硬件故障等异常情况， 要求路由算法能够在部分通信线路破坏时迅速重构，提高低压 电力线载波抄表系统的抗毁性。 仿真中仍采用图1所示的拓扑结构，假设某时刻节点8发 基于免疫-蚁群算法的电力线载波抄表动态路由方法 高 庆， 等 110 学兔兔 w w w .x u e t u t u .c o m 自动化与仪器仪表 2014年第1期 （总第171期） 生故障，丧失通信能力，即电表节点8从网络拓扑中消失，此 时含有电表节点8的路由线路需要重新组建。假设通信距离不 变，分别采用蚁群算法（ACA）和免疫-蚁群算法（I-A） ，从 集中器节点1到目的电表节点50的抄表路由路径进行仿真试 验，结果如图4和图5所示。 图4节点失效路由寻优结果 图5节点失效仿真结果 从图4和图5可以看出：在8号节点发生故障的情况下， 免疫-蚁群算法（I-A）和蚁群算法（ACA）均能在新网络环 境下搜索到最优路径：1-3-17-26-44-50，迭代次数分别为 15和22次，显然免疫-蚁群算法具有更高的搜索效率。在实际 低压电力线载波抄表系统中，因低压电力线的时变性、信道的 时变性或载波电表节点的硬件故障引起的网络拓扑结构的变化 时，免疫-蚁群算法不仅能够针对新的拓扑迅速找到最优路由 线路，提高抄表系统的抗毁性，而且与蚁群算法相比，免疫- 蚁群算法能够以相对较少的迭代次数收敛到最优路由线路，缩 短了集中器到目的电表的路径寻优时间，提高了抄表系统的实 效性。 4.3算法的性能比较 为了综合比较免疫-蚁群算法和蚁群算法的性能，仍采用 图1所示的拓扑结构，分别采用免疫-蚁群算法和蚁群算法， 从集中器节点1到目的电表节点50的抄表路由路径进行50次 仿真试验。试验结果如表1所示。 表1实验结果对比 算法 免疫-蚁群 算法 收敛到最优解 次数 41 收敛到次优解 次数 9 其他结果 0 平均迭代 次数 16.68 蚁群算法2822025.39 从表1可以看出：在收敛到最优解方面，如果采用免疫- 蚁群算法，50次实验中有41次能够收敛到最优路径，仅有9次 寻优陷入局部最优解，而采用蚁群算法，收敛到最优解的次数 为28次，收敛到次优解的次数为22次；对于所有节点收敛时 迭代次数平均值方面，免疫-蚁群算法所需的平均迭代次数较 小，仅为16.68次，而蚁群算法为25.39次。这是因为免疫-蚁 群算法融合了免疫算法和蚁群算法的优点，在蚁群算法的基础 上增加了交叉操作以及对较优路径的记忆功能，有效克服了蚁 群算法搜索时间长、易陷入局部最优解等缺点。 5结论 针对实际低压电力线载波抄表系统中继路由算法的不足， 借鉴人工免疫系统的适应能力和蚁群算法的全局寻优能力提出 了一种基于免疫-蚁群算法的低压电力载波抄表系统动态路由 方法。在蚁群算法的基础上，免疫算法把目标函数和约束条件 作为抗原，记忆与抗原具有高亲和力的抗体，促进快速求解。 算法中的交叉操作增强了抗原识别、记忆和调节功能。该算法 结合了人工免疫算法与蚁群算法两者的优点。通过仿真对免 疫-蚁群算法和蚁群算法在算法的收敛性、抗毁性和运算性能 方面进行了比较，结果表明，免疫-蚁群算法不仅具有动态路 由寻优功能，而且还有效地克服了蚁群算法搜索时间长、易陷 入局部最优解等缺点。算法能够根据低压电力线信道的变化情 况以相对较少的迭代次数收敛到最优路径，提高整个低压电力 载波抄表系统的时效性。 参考文献 1 罗春风， 程时杰， 熊 兰等. 基于多层感知器的低压电力线时变信道 非线性均衡方法J. 中国机电工程学报， 2005， 25(4)： 71-75. 2 Yang Xiaoxian, Zheng Tao, Zhang Baohui. Measurement and research of the characteristics of noise distribution in three-phase four-wire low-voltage power network channelsJ. IEEE Transactions on Power Delivery, 2007， 22(1)： 122-128. 3 赵 阳， 董颖华， 陆虓泉等. EMI噪声分离网络在电力线噪声分析中 的应用J. 中国机电工程学报， 2010， 30(21)： 114-120. 4 俞天白， 杨将新， 赵玉玺. 楼宇控制系统中的电力线载波通信路由方 法J. 电网技术， 2006， 30(9)： 88-91. 5 刘晓胜， 戚佳金， 宋其韬等. 基于蚁群算法的低压配电网电力线通信 组网方法J. 中国机电工程学报， 2008， 28(1)： 71-86. 6 莫宏伟. 人工免疫系统原理与应用M. 哈尔滨： 哈尔滨工业大学出 版社， 2002， 187-236. 7 段海滨. 蚁群算法原理及其应用M. 北京： 科学出版社， 2005， 24-39. 8 刘士新， 宋健海， 唐加福. 蚁群最优化模型、 算法及应用综述J. 系 统工程学报， 2004， 19(5)： 496-502. 9 蒋加伏， 陈荣元， 唐贤瑛， 谭 旭. 基于免疫-蚁群算法的多约束QoS路 由选择J. 通信学报， 2004， 25(8):89-95. 111 学兔兔 w w w .x u e t u t u .c o m