基于遗传自适应蚁群系统算法的中继路由方法

陈可，胡晓光

(北京航空航天大学 自动化科学与电气工程学院，北京，100191)

摘 要：

载波抄表系统中现有中继路由算法的不足，提出一种基于遗传自适应蚁群系统算法的动态中继路由方法。利用遗传算法的快速全局搜索能力获得路径信息素的初始分布，再结合蚁群算法的正反馈收敛机制，同时依据搜索情况对状态转移概率因子、信息素挥发因子、信息素强度等参数进行自适应调整，最终获得最优路由线路。通过仿真实验验证该算法的收敛性、鲁棒性和抗毁性，算法能够根据电力线信道的变化情况以相对较少的迭代次数收敛到最优路径，提高整个抄表系统的时效性。

关键词：

抄表；遗传算法；自适应；蚁群系统算法；动态中继路由；

中图分类号：TN914.66          文献标志码：A         文章编号：1672-7207(2013)02-0571-09

Method of relay routing based on genetic adaptive ant colony system algorithm

CHEN Ke, HU Xiaoguang

(School of Automation Science and Electrical Engineering,

Beijing University of Aeronautics and Astronautics, Beijing 100191, China)

Abstract: In view of the shortcoming of the current relay routing algorithm in the actual power line carrier meter reading system, the method of dynamic relay routing based on genetic adaptive ant colony system (GAACS) algorithm was proposed. The global search capability of genetic algorithm was used to obtain the initial pheromone distribution about path and the positive feedback mechanism of ant colony algorithm was used to convergence. At the same time according to search situation, the state transform probability factor, the pheromone evaporation factor and the pheromone strength parameters were adaptively adjusted by GAACS algorithm, and finally the optimal routing path was obtained. Convergence, robustness, and invulnerability were analyzed and tested by simulation experiments. Algorithm can accord the changes of power line channel with relatively little iterations to obtain the optimal path, and the timeliness of the meter reading system is improved.

Key words: meter reading; genetic algorithm; adaptive; ant colony system algorithm; dynamic relay routing

近年来，采用低压电力线作为通信介质的传输技术具有充分利用现有资源、易施工、综合成本低、不受环境条件限制等优点，是电力部门实现远程自动抄表的发展趋势，具有广阔的应用前景。由于低压电力线具有高噪声、高衰减和高时变等特性^[1-3]，使得集中器节点和目标电表节点之间直接通信成功概率较低，这不仅制约了信号传输的距离，同时严重降低了电力线通信的可靠性，进而影响抄表范围和抄表成功率。因此在实际应用中，需要通过中继技术来弥补以上缺憾。许多学者在这一领域进行了深入研究，提出了多种中继路由方法，文献[4]提出了具有中继约束条件的自动中继路由算法；赵杰卫等^[5]采用蚁群算法及利用电气距离作为约束条件候选集策略提高了中继搜索的准确度和效率；刘晓胜等提出了一种适用于未知建筑物电力线拓扑结构条件下的蚁群电力线组网方法^[6]，并通过仿真验证了该组网算法的有效性和抗毁性；还提出了适用于低压配电网电力线载波通信的类蚁群算法^[7]，该方法可以有效延长电力线载波通信距离。以上这些方法在一定程度上解决了抄表范围与抄表成功率等问题，但均有一些缺点：文献[4]中的方法与一般自动中继方法相比，虽然节约了抄表时间，提高了抄表成功率，但不具有动态适应电力线环境的变化能力；文献[5-7]中的方法虽然能动态适应电力线环境的变化，但算法的收敛速度较慢，并且容易陷入局部极小值。针对以上问题，本文作者从提高抄表系统的时效性角度出发，将遗传算法(Genetic algorithm，GA)和蚁群系统(Ant colony system，ACS)算法有机融合，提出了一种遗传自适应蚁群系统(Genetic adaptive ant colony system，GAACS)算法。该算法利用GA 的随机搜索、快速性及全局收敛性等特点，获得集中器到目标电表的初始中继路由路径并将其运用到蚁群算法初期信息素分布中，再利用蚁群系统算法的并行性、正反馈机制以及求解效率高等特性求出最终解。在求解过程中，为了防止算法陷入局部最优解，依据搜索情况对ACS算法中的状态转移概率因子、信息素挥发因子以及信息素强度等参数采取自适应调节策略。通过将本文算法、遗传蚁群系统(Genetic ant colony system，GACS)算法、ACS和最大最小蚂蚁系统(Max-min ant system，MMAS)算法进行对比仿真实验，结果表明本文算法在收敛性、鲁棒性、抗毁性及算法运行时间等方面均优于其他3种算法。

1  电力线载波抄表网络拓扑结构

在低压电力线载波抄表系统中，下行线路主要由集中器和一定数量的电表组成，在逻辑拓扑结构中可以将集中器视作网关，每个用户电表视为可通信的终端节点。由于低压电力线的干扰、信号衰减和负载的接入与切出等因素，使信号在电力线上的传输并不能和理想状态时的传输距离相比，某些电表节点将不能直接与集中器节点进行通信。为了实现集中器对每一个目标电表的抄收，必须先建立集中器到部分电表之间的路由路径，再将这些节点作为中继节点进行数据的转发，扩展通信距离，才可能将所有的节点连入低压电力线抄表系统中，达到自动抄表的目的。抄表系统中，集中器与电表之间的树形拓扑模型如图1所示，集中器位于树形拓扑结构的根部，即图1中的0号节点，1~60号节点分别代表抄表系统中各电能表。

图1  电力线载波抄表网络树形拓扑

Fig.1  Power line carrier meter reading network tree topology

2  算法原理

2.1  遗传算法原理

遗传算法是一类可用于复杂系统优化的鲁棒性搜索算法，它是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法。遗传算法是由可行解组成的群体逐代进化过程，选择、交叉、变异是遗传算法的3个主要过程^[8-10]。

2.1.1  适应度函数及优化目标函数

适应度函数应该能够反映出动态路由问题中解的优劣，通过群体的初始化，用式(1)计算每个个体的适应度F(X)，集中器到目标电表节点的路由路径中，跳数相对越少，其适应度值越高，适应度函数定义为：

F(X)=C_max-f(X)               (1)

式中：F(X)为个体适应度值；C_max为一个适当地相对比较大的数，本文所研究的抄表系统中，目标电表节点共60个，因此，C_max取值为100；f(X)为个体相应的目标函数值，即动态路由路径中源节点到目标节点的跳数。

2.1.2  选择运算

为了加快遗传算法的收敛速度，保留抄表过程中所获得的较好路径，本文采用精英选择方法，该方法使适应度函数值高的个体不受交叉和突然变异的影响，而是无条件的遗传给后代，由于作为最优个体的遗传因子在群体中可能急剧地增多，算法能较快收敛到最优解或局部最优解。

2.1.3  交叉运算

该运算是交换2个染色体中的子路径，其中用于交换的染色体必须拥有相同的源节点和目的节点。路径交叉运算的交叉位置限制在2个染色体中都含有的节点(不包含源节点和目标节点)，从潜在的交叉位置中随机选择节点作为交叉位置，交换子路径。图2所示为将交叉运算应用于从集中器节点0到目标电表节点15的一对父代A1和A2的情况，父代潜在的交叉位置是中继节点6，9和12，选择中继节点6作为交叉位置，图2通过交换子路径产生新的子代B1和B2。

图2  交叉运算框图

Fig.2  Crossover operation figure

当一对染色体中的公共点不存在时交叉位置就不能选择，因此也就不可能实施交叉运算。交叉概率p_c取值过大会破坏群体中的优良模式，对进化运算产生不利影响；若取值过小，产生新个体的速度较慢。本文为了加快遗传算法的收敛速度，交叉概率p_c取值为0.5。

2.1.4  变异运算

该运算是从一个染色体产生另一个染色体。为了实现变异，从染色体中随机选择节点，该节点称为变异节点，在满足最小通信距离的条件下从与变异点相邻节点中随机选择另一个节点，最后利用基于最小跳计数准则的Dijkstra算法分别产生从源节点到选择点和从选择点到目标节点的可选路径。路径变异运算如图3所示，假设中继节点6被选择作为变异点，从变异节点的邻点中选择节点7，根据Dijkstra最小跳数算法产生源节点0到节点7的子路径a及节点7到目标节点15的子路径b，连接a和b，完成变异操作。为了避免路径中的任何环，如果子路径a和b中存在重复节点，子代B就不能产生。变异概率p_m取值较大时，虽然能够产生较多的新个体，但可能破坏很多较好的路径，使得算法性能近似于随机搜索算法的性能；若取值过小，则变异操作产生新个体的能力和拟制早熟现象的能力就会较差。本文为了加快遗传算法的收敛速度，变异概率p_m取值为0.01。

图3  变异运算框图

Fig.3  Mutation operation figure

2.2  基本蚁群系统算法原理

蚁群系统算法是近年发展起来、受自然界蚂蚁搜寻食物行为启发得到的并行优化算法^[11-15]。该算法具有采用分布式并行计算机制、易于与其他方法结合、具有较强的鲁棒性等优点，但搜索时间长、易陷入局部最优解是其最为突出的缺点。

2.2.1  路径构建

在ACS算法中，位于城市i的蚂蚁k，根据伪随机比例规则选择城市j作为下一个访问的城市，路径转移规则如下：

       (2)

式中：q₀(0＜q₀＜1)是状态转移因子；q为0到1之间的随机数；η_il为启发式信息；β为期望启发式因子；若y=f(x)，则argmax[y]表示当y取得最大值时x的值。当q≤q₀时，按照先验规律选择路径；当q＞q₀时，按照概率进行路径搜索。

转移概率计算公式如下：

     (3)

式中：τ_ij为路径(i，j)上的信息素大小；η_ij为路径(i，j)上的启发式信息大小；α为信息启发式因子；β为期望启发式因子。

2.2.2  局部信息素更新

在路径构建过程中，蚂蚁每经过一条边(i，j)，都将立刻调用局部信息素规则更新该边上的信息素，规则如下：

             (4)

式中：τ_ij为路径(i，j)上的信息素含量；ξ为局部更新挥发因子；τ₀为信息素初始值。ξ的引入使被选择过的路径上的信息素减少。局部更新规则使蚂蚁倾向于选择没有走过的路径，避免搜索过于集中到同一条线路上，使得算法不会陷入停滞状态，这种更新规则有利于新路径的发现。

2.2.3  全局信息素更新

在ACS算法中，只有一只蚂蚁(至今最优蚂蚁)被允许在每一次迭代之后释放信息素，全局信息素更新规则如下：

             (5)

       (6)

式中：τ_ij为路径(i，j)上的信息素含量；△τ_ij为路径(i，j)上的信息素增量；ρ为信息素挥发因子；Q为信息素强度；L_bs为至今最优路径长度。对至今最优线路进行信息素增加，可使搜索过程具有指导性，搜索范围集中在至今最优线路。

2.3  自适应蚁群系统算法原理

基本蚁群系统算法在搜索初期，各条路径上的信息素分布比较分散，在经过一定的迭代步数后，信息素会逐渐集中到少数路径上，搜索的大致方向也就随之确定，由于ACS算法的正反馈机制旨在强化性能较好的解，因此，在搜索后期，当某些路径上的信息素强度明显高于其余路径时，继续搜索将会总在少数路径上进行，这样会使解的结构过于相似，搜索过程也会停顿下来，算法容易陷入局部最优解。

本文采用遗传算法得到集中器到某目标电表的初始路径，并将其运用到蚁群系统算法初期信息素分布中，这将导致在算法初期，少数路径上的信息素强度会明显高于其余路径，算法极易出现停滞现象并陷入局部最优解而无法跳出。为了解决这个问题，本文在ACS算法的基础上，提出了根据解的搜索情况，动态自适应调整状态转移概率因子、信息素挥发因子、信息量强度等因素，可在一定程度上有效地克服ACS算法的一些不足。

2.3.1  转移概率因子的改进

在式(2)中，状态转移因子q₀是一个非常重要的参数。当q≤q₀时，蚂蚁依据信息素的积累量和启发式信息值确定要移动的下一节点；当q＞q₀时，蚂蚁依据概率有偏向性地探索各条边。在基本蚁群算法中，q₀是区间[0，1]上的固定常数，缺乏自适应性。本文通过自适应调整参数q₀来调节算法对新路径的探索度，从而决定算法是应该集中搜索至今最优路径附近的区域，还是应该搜索其他区域，q₀按下式进行选择：

         (7)

式中： 为q₀(t)的最小值；σ为正参数，控制q₀(t)的下降及上升速度。

由于抄表系统中，终端电表的数量较多，因此，在算法执行初期，选择相对较大的q₀能加快算法的收敛速度，降低算法的随机性，利于局部搜索；在算法执行中期，选择相对较小的q₀能提高算法随机性，利于全局搜索；在算法执行后期，重新恢复q₀的初始值，进一步提升收敛速度并最终找到全局最优解。

2.3.2  信息素挥发因子的改进

蚁群系统算法中信息素挥发因子ρ的大小直接关系到ACS算法的全局搜索能力及其收敛速度。在自动抄表系统中，如果终端电表数量比较多，由于ρ的存在，会使那些从来未被搜索到的路径上的信息量减小到接近于0，因而降低了算法的全局搜索能力，而且当ρ过大时，以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力；反之，通过减小ρ虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。基于以上分析，本文采取自适应调整信息素挥发因子ρ的方法，在提高收敛速度的同时避免陷入局部最优解，当算法在连续N次循环迭代过程中，最优解都没有变化，表明搜索过程可能陷入了局部最优解，此时ρ按照下式作自适应调整：

          (8)

式中：ρ_min为ρ的最小值，为了防止ρ过小降低算法的收敛速度；λ为预先设定的衰减系数，根据抄表规模调整。式(8)使得信息素挥发因子ρ从最大值逐渐降低，但又不至于太低而影响算法的收敛速度。与式(5)对比可以看出：改进前的ρ是一个固定值，而改进之后，在算法运行初期，ρ取相对较大值，提高算法的收敛速度，快速找到局部最优解；在算法运行后期，ρ取相对较小值，可以进一步提高随机性能和全局搜索能力。

2.3.3  信息素强度的改进

信息素强度Q为蚂蚁循环一周时释放在所经过路径上的信息素总量，其作用是为了充分利用路径上的全局信息反馈量，使得算法在正反馈机制作用下以合理的演化速度搜索到所求问题的全局最优解。Q越大，则在蚂蚁已遍历路径上信息素的累积加快，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛，但此时算法的全局搜索能力变差，极易陷入局部最优解，计算性能也变得很不稳定；Q过小又会影响算法的收敛速度。针对以上问题，本文提出了一种根据蚁群算法搜索情况来自适应动态修改信息素强度的方法，可在一定程度上有效地解决扩大搜索空间和寻找最优解之间的矛盾，从而使得算法跳离局部最优解。当算法在连续N次循环迭代过程中，最优解都没有变化，表明搜索过程可能陷入了局部最优解，则采用强制机制，减小要添加的信息素，使算法从局部极小值中逃脱出来。此时Q按照下式作自适应调整：

     (9)

式中：ζ为正参数，控制Q(t)的下降速度；Q(0)为信息素强度的初始值；Q_min为Q(t)的最小值。采用时变递减函数代替常数项Q，可以保证在路径上的信息素随搜索过程逐渐增多的情况下，继续保持随机搜索和路径信息的启发作用间的平衡，使算法能跳出局部最优，继续寻找全局最优解。

3  基于GAACS路由算法的特点及步骤

3.1  路由算法特点

电力线载波抄表系统中，集中器与各用户电表的连接关系通常未知，通信网络逻辑拓扑结构处于盲态，路由算法须具有如下特点：

(1) 算法能适应盲网络状态要求。在盲网络状态下，指定中继方式已经不能满足路由要求，路由算法须具有对抄表系统网络探索和辨识的能力，找到集中器节点和目标电表节点之间路由线路，同时算法应具有路由优化能力，搜索并收敛于优良的路由线路。

(2) 路由算法能够适应抄表系统中网络逻辑拓扑的变化。抄表系统中不断有新的用户接入网络，导致系统的逻辑拓扑不断变化，路由算法要能够适应该变化，对变化前后的逻辑拓扑结构，算法的路由能力不变。

(3) 路由算法有较强的抗毁性。低压电力线具有负载多、噪声强、衰减大、时延长等特征，抄表通信路径易失效，网络中电表节点本身也存在硬件故障等异常情况。要求路由算法能够在抄表通信线路被破坏时迅速重构，提高抄表系统的抗毁性。

3.2  基于GAACS路由算法实现步骤

在阐述利用GAACS算法实现抄表系统动态路由过程之前，对本文常用的名词进行定义。

定义1 搜索蚂蚁寿命：是指搜索蚂蚁数据帧能够被中继电表节点转发次数的上限。在实际抄表系统中，数据帧不能被无限次转发，尤其是对于窄带电力线载波通信，通信速率较低，数据帧转发次数受到较大限制，否则占用信道时间过长，同时也容易产生错误。考虑该约束条件，算法中定义蚂蚁寿命变量为7，表示每只搜索蚂蚁最多能够经历7个不同的中继节点，每转发一次该值减1。如果在经历了7个电表节点之后，该搜索蚂蚁没有找到目标电表节点，则设定该蚂蚁死亡，不再继续寻找，工程应用中表现为舍弃该数据帧不再转发。

定义2 跳数：是指集中器节点与任意一个目标电表节点通信时，搜索蚂蚁数据帧到达目标电表节点所需被转发的次数。可以直接通信的节点，跳数为0；需要通过1个中间电表节点转发数据帧，跳数为1，以此类推。

定义3 通信距离：是指抄表系统中可以相互通信的两个节点所跨过的节点个数加1。该距离会随着电力线信道质量而变化。本文规定任意一个节点最小可通信距离可以跨过2个节点，即通信距离为3，实际抄表系统中，各个电表节点的通信距离会远大于3。

GAACS算法设计了合理有效地适应度函数和优化目标函数，并且采用通信距离、蚂蚁寿命作为约束条件，力求在保证抄表正确和可靠的前提下尽量提高路由效率。在该算法中，约定如下：①在集中器节点控制范围内每个电表节点有一个唯一的地址编号；②抄表系统逻辑拓扑图为无向图；③任意相邻的两个电表节点都能够保证可靠通信。GAACS算法流程如下，其中，步骤1~8利用遗传算法的快速全局搜索能力生成路径初始信息素分布，步骤9~15利用蚁群算法的正反馈收敛机制完成最终集中器到目标电表之间最优路径的建立。

步骤1  参数初始化。主要包括以下几方面：① 群体规模M、交叉概率p_c、变异概率p_m、信息启发式因子α、期望启发式因子β、信息素常量τ_C、等效信息素τ_G、信息素强度初始值Q(0)、信息素强度最小值Q_min、信息素挥发因子最小值ρ_min、转移概率因子最小值q_min、局部更新挥发因子ξ、系数σ，λ和ζ；② 集中器及各电表节点通信信息表、转移概率表、启发信息表、禁忌表初始化；③ 遗传迭代次数N_G、蚁群迭代次数N_A、迭代蚂蚁数m初始化；

步骤2  编码。利用序列编码方法，编码位串的首个字符代表集中器编号，设定为0，编码位串最后一个字符代表目标电表节点编号，中间字符按照抄表路由路径顺序依次排列。如果路径不符合最小通信距离的约束条件，则不能被编译成一个染色体，这意味着路径中的每一步都必须经过抄表系统中实质上的 连接；

步骤3  初始化群体。针对某一目标电表节点，利用基于最小跳计数准则的Dijkstra算法产生从集中器节点到目标节点的路径作为初始路径。为了提高遗传算法的运行效率，避免搜索中继路由路径的时间过长，初始群体规模不宜太大；

步骤4  根据式(1)计算种群内个体适应度值、判断迭代次数n_G，若n_G＞N_G，获得优化抄表路由路径并转向步骤9，否则转向步骤5；

步骤5  记录父代的精英个体，将父代中的精英个体直接复制到子代种群中；

步骤6  以概率p_c对种群进行路径杂交运算；

步骤7  以概率p_m对种群进行路径变异运算；

步骤8  由精英复制个体、交叉、变异后的个体构成下一代种群个体，转入步骤4；

步骤9  经过遗传算法得到集中器到目标电表的优化抄表路径，并运用到蚁群算法初期信息素分布中，用下式更新各条路径上的初始信息素分布：

τ₀=τ_C+τ_G                  (10)

式中：τ_C是给定的一个信息素常数；τ_G则是根据遗传算法求得的初始抄表路径所对应的等效信息素。

步骤10  集中器节点发起探索蚂蚁数据帧。该数据帧包括集中器地址、目标电表地址、路由区及搜索蚂蚁寿命。路由区在数据帧到达目标电表节点之前不断填充其所经历路由节点地址信息。依据算法运行时间，按式(7)自适应调整状态转移概率因子q₀(t)，蚂蚁按式(2)选择下一个访问的节点，并立即按式(4)更新局部信息素浓度；

步骤11  判断是否为目标节点，如果是目标节点转入步骤12，否则转入步骤10；

步骤12  对每一只蚂蚁执行步骤10和11，直到所有的蚂蚁均迭代完成；

步骤13  找出至今最优蚂蚁，并按式(5)和(6)进行至今最优路径的全局信息素浓度更新；

步骤14  当算法在连续N次循环迭代过程中，最优解都没有变化，表明搜索过程可能陷入了局部最优解，根据式(8)和(9)自适应调整信息素挥发因子ρ(t)及信息素强度Q(t)；

步骤15  判定算法是否达到设定的迭代次数N_A，达到则记录集中器节点到目标电表节点的最优路径，并把最优路径存到集中器节点的路由表中，否则转向步骤10。

4  仿真结果

本文仿真实验中各参数选择为：种群规模M=20，交叉概率P_c=0.5，变异概率p_m=0.01，C_max=100，N_G=8，等效信息素τ_G=2，每次迭代蚂蚁数m=15，蚂蚁寿命l_A=7，ξ=0.1，α=1，β=1，η_ij=1，τ_C=15，σ=25，ζ=0.02，q_min=0.018 3，λ=0.9，ρ_min=0.05，Q(0)=4 000，Q_min=2 000，N=4，N_A=42。说明，在4.2和4.3中遗传算法迭代次数N_G取值为4；蚁群算法迭代次数N_A取值为26；参数自适应调整时最大迭代次数N取值为3。

4.1  算法收敛性分析

算法的收敛性是衡量算法性能优劣的重要指标之一，本文采用MATLAB7.01为仿真平台，对GAACS，GACS，ACS和MMAS 4种算法下，集中器节点0到目标电表节点60的抄表路由路径寻优进行验证，仿真采用的物理拓扑结构如图1所示，仿真结果如图4所示。

图4  搜索电表节点60的仿真结果

Fig.4  Result of simulation about searching meter node 60

从图4可以看出：4种算法经过不同次数的迭代运算后均能收敛到最优路由路径：0→19→51→60或者0→19→50→60，从搜寻到最佳路由路径的效率方面比较，显然GAACS算法搜寻到最优解的效率最高，仅仅经过22次迭代运算就收敛到最优解；其次是GACS算法，经过27次迭代运算收敛到最优解；再是ACS算法，经过32次迭代运算收敛到最优解；搜索效率最低的是MMAS算法，经过42次迭代运算才最终找到最优解。因此，相比其他3种算法，GAACS算法能更好地适用于电力线载波抄表系统中继路由问题，该算法具有较高的动态路由寻优效率，能够确保抄表路由路径的质量。

4.2  算法鲁棒性分析

算法鲁棒性是指算法适应不同网络拓扑结构的能力，在实际抄表系统中，集中器与各电表之间的物理拓扑结构非常复杂，由于低压电力线信道质量的变化引起电表节点通信距离的变化，导致抄表系统的物理拓扑结构随之变化；此外，随着电表节点的加入与退出也会导致物理拓扑结构的变化。GAACS算法能否适应这种复杂性，是该算法能否运用到实际电力线载波抄表系统的重要评判标准。

为了更好地反映电力线载波抄表系统中通信网络逻辑拓扑的时变性，设某时刻各电表节点通信距离是在一定范围内的随机值，仿真分析这种情况下GAACS算法搜索最佳路由路径的能力。仿真中仍然采用图1所示的拓扑结构，但每个电表节点的通信距离为1~5之间的一个随机值。表1所示为仿真实验中各电表节点随机产生的通信距离表，其中N表示电表节点号，D表示该电表节点通信距离。

图5所示为采用表1中的电表节点随机通信距离(集中器节点的通信距离设定为2)，运用GAACS，GACS，ACS和MMAS等算法求取集中器节点0到目标电表节点60的抄表路由路径寻优仿真结果。

表1  各电表节点通信距离随机值

Table 1  Random value of meter node communication distance

图5  随机通信距离仿真结果

Fig.5  Result of simulation about random communication distance

从图5可以看出：在实际低压电力线载波抄表系统各电表节点通信距离随机的情况下，只有GAACS算法能够最终搜索到最优路由路径，即：0→8→41→60或0→2→41→60，算法收敛到最少路由跳数2跳时所需的迭代数仅为13次。而GACS，ACS和MMAS3种算法对于节点通信距离随机的抄表系统，均未能收敛到最优路由路径并全部陷入局部最优解。原因是GAACS算法能够依据当前的搜索情况自适应地改变状态转移因子、信息素挥发因子、信息素强度等参数，使得在算法陷入局部最优解后，仍然能够跳出局部最优解，继续寻找全局最优解，在保证收敛速度的条件下提高了解的全局性。因此，可以得出以下结论：GAACS算法的鲁棒性能最好，GACS，ACS和MMAS3种算法的鲁棒性能大致相当。

4.3  算法抗毁性分析

低压电力线具有噪声强、衰减大、负载多、时延长等特征，通信路径易失效，抄表系统中，电表节点本身也存在硬件故障等异常情况。要求路径寻优算法能够在系统中部分通信线路被破坏时迅速重构，提高抄表系统的抗毁性。

仿真中仍然采用图1所示的拓扑结构，假设某个时刻19号电表节点发生故障，丧失通信功能，则此电表节点在系统网络逻辑拓扑中消失，此时含有19号电表节点的路由线路将不再适用，某些集中器到目标电表节点的抄表路径需要重新组建。对该情况进行仿真实验，假设节点的通信距离为3，以60号电表节点作为目标节点，分别采用GAACS，GACS，ACS和MMAS算法，仿真结果如图6所示。

图6  节点失效仿真结果

Fig.6  Result of simulation about node failure

从图6可以看出：在19号节点发生故障的情况下，GAACS，GACS，ACS和MMAS算法再次搜索到最优路由路径所需的迭代数分别为9，14，17和23次，显然GAACS算法具有更高的搜索效率。GAACS算法仅仅需要9次迭代搜索，路由跳数就最终收敛到2跳，多次仿真实验输出的路由线路均为以下7条线路中的1条，即0→8→41→60，0→8→50→60，0→8→51→60，0→30→41→60，0→30→50→60，0→30→51→60和0→30→57→60。这些路径均为最优路由路径。因此，在实际低压电力线载波抄表系统中，因某电表节点自身发生故障或线路故障引起整个抄表系统拓扑结构发生变化时，GAACS算法不仅能够针对新的拓扑结构迅速找到最优路由路径，提高抄表系统的抗毁性，而且与其他3种算法相比，GAACS算法能够以相对较少的迭代次数收敛到最优路径，从而缩减集中器到目标电表的中继路由路径寻优时间，提升整个抄表系统的时效性。

4.4  算法性能指标比较

为了综合比较GAACS，GACS，ACS和MMAS4种算法的性能，本文依然采用图1所示的网络拓扑结构，分别选取31~60号节点作为目标节点，采用上面4种算法对每一个目标节点进行一次路径寻优实验，实验结果如表2所示。

表2  实验结果

Table 2  Experimental results

从表2可以看出：对30个目标电表节点路由路径寻优实验中，在收敛到最优解节点数量方面，如果采用GAACS算法，集中器节点对其中25个目标电表节点能搜索到最优路由路径，仅对5个目标电表的寻优陷入了局部最优解，而采用GACS，ACS和MMAS3种算法，收敛到最优解的节点个数分别为23，20和19，收敛到次优解的节点个数分别为7，10和10；对于所有节点收敛时迭代次数平均值方面，GAACS算法所需的迭代数平均值最少，仅为12.16次，远低于MMAS算法的36.28次；对于收敛到最优解所需平均运算时间方面，GAACS算法的平均运算时间也明显优于其他3种算法。这是因为GAACS算法利用了遗传算法的快速全局搜索能力，并在迭代过程中依据搜索情况对蚁群系统算法的相关参数作自适应调整，有效地克服了蚁群算法搜索时间长、易陷入局部最优解等缺点。

5  结论

(1) 针对实际电力线载波抄表系统中现有中继路由算法的不足，提出了一种基于遗传自适应蚁群系统算法的动态中继路由方法，利用遗传算法的快速全局搜索能力获得路径信息素的初始分布，再结合蚁群算法的正反馈收敛机制，同时依据搜索情况对状态转移概率因子、信息素挥发因子、信息素强度等参数进行自适应调整，最终获得最优路由线路。

(2) 将GAACS与GACS，ACS和MMAS算法在算法收敛性、鲁棒性、抗毁性以及运算时间方面进行了比较。结果表明GAACS算法不仅具有动态路由路径寻优功能，而且有效地克服了基本蚁群系统算法收敛速度慢、易陷入局部极小值等问题，提高了整个抄表系统的时效性。随着抄表系统中目标电表节点的规模增大，改进的效果越明显。

参考文献：

[1] 赵阳, 董颖华, 陆婋泉, 等. EMI噪声分离网络在电力线噪声分析中的应用[J]. 中国电机工程学报, 2010, 30(21): 114-120.

ZHAO Yang, DONG Yinghua, LU Xiaoquan, et al. EMI noise discrimination network applied to power-line EMI noise analysis[J]. Proceedings of the CSEE, 2010, 30(21): 114-120.

[2] 罗文亮, 柯熙政, 马鸣. 基于低压电力线通信信道的自适应估计研究[J]. 仪器仪表学报, 2009, 30(8): 1623-1629.

LUO Wenliang, KE Xizheng, MA Ming. Study of adaptive estimation based on low-voltage power-line communication channel[J]. Chinese Journal of Scientific Instrument, 2009, 30(8): 1623-1629.

[3] 徐志强, 翟明岳, 赵宇明. 基于电力线信道作用的能量时频分布及其能量分配[J]. 电力系统自动化, 2009, 33(1): 75-80.

XU Zhiqiang, ZHAI Mingyue, ZHAO Yuming. Energy time frequency distribution based on power line channel effect and its application in energy assignment[J]. Automation of Electric Power Systems, 2009, 33(1): 75-80.

[4] 陈可, 胡晓光. 基于电力线宽带载波集中器设计与中继算法[J]. 电力自动化设备, 2011, 31(9): 115-120.

CHEN Ke, HU Xiaoguang. Design of concentrator based on electric line broadband carrier and relay routing algorithm[J]. Electric Power Automation Equipment, 2011, 31(9): 115-120.

[5] 赵杰卫, 卢文冰, 李贤亮. 电力线载波自动抄表动态路由技术研究[J]. 电力系统通信, 2007, 28(11): 1-5.

ZHAO Jiewei, LU Wenbing, LI Xianliang. Research of dynamic routing technology in automatic meter reading system based on power line carrier[J]. Telecommunications for Electric Power System, 2007, 28(11): 1-5.

[6] 刘晓胜, 戚佳金, 宋其涛, 等. 基于蚁群算法的低压配电网电力线通信组网方法[J]. 中国电机工程学报, 2008, 28(1): 71-76.

LIU Xiaosheng, QI Jiajin, SONG Qitao, et al. Method of constructing power line communication networks over low-voltage distribution networks based on ant colony optimization[J]. Proceedings of the CSEE, 2008, 28(1): 71-76.

[7] 刘晓胜, 周岩, 戚佳金. 电力线载波通信的自动路由方法研究[J]. 中国电机工程学报, 2006, 26(21): 76-81.

LIU Xiaosheng, ZHOU Yan, QI Jiajin. Method study of automatic routing for power line communication[J]. Proceedings of the CSEE, 2006, 26(21): 76-81.

[8] Murat A, Novruz A. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithm[J]. Expert Systems with Applications, 2011, 38(3): 1313-1320.

[9] Semya E, Jacques T, Taicir L. Multiple crossover genetic algorithm for the multiobjective traveling salesman problem[J]. Electronic Notes in Discrete Mathematics, 2010, 36(1): 939-946.

[10] 雷友诚, 涂祖耀, 桂卫华, 等. 基于遗传蚁群算法的树枝型铁路取送车问题优化[J]. 中南大学学报: 自然科学版, 2011, 42(8): 2356-2362.

LEI Youcheng, TU Zuyao, GUI Weihua, et al. Optimization of placing-in and taking-out wagons on branch-shaped railway lines based on genetic and ant colony algorithm[J]. Journal of Central South University: Science and Technology, 2011, 42(8): 2356-2362.

[11] YANG Jingan, ZHUANG Yanbin. An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem[J]. Applied Soft Computing, 2010, 10(2): 653-660.

[12] ZHAO Dongming, LUO Liang, ZHANG Kai. An improved ant colony optimization for the communication network routing problem[J]. Mathematical and Computer Modelling, 2010, 52(11): 1976-1981.

[13] WANG Hua, XU Dong, YI Shanwen, et al. A tree-growth based ant colony algorithm for QoS multicast routing problem[J]. Expert Systems with Applications, 2011, 38(9): 11787-11795.

[14] 焦亚萌, 黄建国, 侯云山. 基于蚁群算法的最大似然方位估计快速算法[J]. 系统工程与电子技术, 2011, 33(8): 1718-1721.

JIAO Yameng, HUANG Jianguo, HOU Yunshan. Fast maximum likelihood direction-of-arrival estimation based on ant colony optimization[J]. Systems Engineering and Electronics, 2011, 33(8): 1718-1721.

[15] 张煜东, 吴乐南, 韦耿, 等. 基于自适应蚁群算法的软硬件划分[J]. 控制与决策, 2009, 24(9): 1385-1389.

ZHANG Yudong, WU Lenan, WEI Geng, et al. Hardware/software partition using adaptive ant colony algorithm[J]. Control and Decision, 2009, 24(9): 1385-1389.

(编辑  杨幼平)

收稿日期：2012-02-12；修回日期：2012-04-18

通信作者：陈可(1981-)，男，江西九江人，博士研究生，从事智能控制与优化研究；电话：13401196322；E-mail：coco_chen81925@yahoo.com.cn

摘要：针对实际电力线载波抄表系统中现有中继路由算法的不足，提出一种基于遗传自适应蚁群系统算法的动态中继路由方法。利用遗传算法的快速全局搜索能力获得路径信息素的初始分布，再结合蚁群算法的正反馈收敛机制，同时依据搜索情况对状态转移概率因子、信息素挥发因子、信息素强度等参数进行自适应调整，最终获得最优路由线路。通过仿真实验验证该算法的收敛性、鲁棒性和抗毁性，算法能够根据电力线信道的变化情况以相对较少的迭代次数收敛到最优路径，提高整个抄表系统的时效性。