基于蚁群遗传混合的载波路由方法研究

杨永，朱俊超，卫建均，许炫壕

（1.广东电网有限责任公司茂名供电局，广东茂名525000；2.广东工业大学自动化学院，广东广州510006）

基于蚁群遗传混合的载波路由方法研究

杨永1，朱俊超2，卫建均1，许炫壕2

（1.广东电网有限责任公司茂名供电局，广东茂名525000；2.广东工业大学自动化学院，广东广州510006）

针对集中抄表系统下行载波通信路由算法数据传输延时和丢包率高的问题，在分析集抄系统载波通信网络结构的基础上，提出了一种基于蚁群遗传混合的载波路由方法。该方法在蚁群算法中引入了遗传算法，使蚁群算法不至于陷入局部最优；对状态转移因子进行改进，加快了算法全局最优路径的收敛速度。仿真结果表明：与蚁群算法相比，该方法在降低数据传输延时和丢包率方面优势明显，可大大提高集中抄表系统数据采集的实时性和成功率。

电力线载波通信；集中抄表系统；混合路由算法；可靠性

将低压电力线作为数据通信的媒介，可极大地减少成本投资，方便用户安装，在电力行业已被用于集中抄表系统领域［1］。然而电力线设计的目的是传输电能而不是进行数据信息的传输，低压配电网中大量负载随机的投入与撤出带来电力线输入阻抗变化不确定、噪声干扰大以及信号选择性衰减等缺点［2-3］，常会加大电力线载波通信数据传输时延和丢包率，降低电力线载波通信的可靠性。

1 研究现状及需要解决的问题

1.1 研究现状

目前，国内外在提高低压电力线载波通信可靠性问题上，主要是从网络层自动路由组网技术方面做了相关的研究。文献［4-5］将遗传算法应用于路由寻址中，保证了路由路径选择的多样性，但搜索到最优路由需要花费较长时间。文献［6］采用蚁群算法构建了集中抄表系统的路由算法，仿真结果表明该算法具有抗毁性强和收敛速度快的优点，但是在算法搜索的后期容易陷入局部最优。文献［7］结合非交叠分簇算法与人工蛛网算法的优点提出了一种新型的分簇蛛网混合算法，实验结果表明该算法能够快速有效地实现低压电力线网络的组网和重构，在提高电力线通信可靠性方面有一定的优势。文献［8］提出了一种基于蚁群、粒子群算法的混合路由算法，仿真结果表明该算法能适应电力线通信信道的动态变化，快速收敛于全局最优路径。

1.2 需要解决的问题

上述研究方法普遍存在以下问题：

（1）通信网络结构复杂，算法在搜索路由过程中不能根据实际情况自适应调整搜索策略，减缓了算法收敛速度，进而加大了数据包传输时延。

（2）在搜寻最优路由路径时，容易陷入局部最优解，将增加数据包传输时的丢失率。

2 蚁群遗传混合路由算法

2.1 集抄系统载波通信网络结构

低压电力线载波集中抄表系统是一种以低压电力线作为数据传输介质，集现代计算机软、硬件技术，电能计量技术为一体的用户用电信息采集与分析处理系统，主要由载波电能表、集中器、主站系统以及连接上述设备的数据传输通道构成［9］。主要包括3层结构：第1层为主站系统，由现场应用服务器、数据库服务器构成，负责数据存储和提供人机交互界面；第2层为集中器，负责对主站的命令进行解析，然后下发给电表，收集电表返回的数据，并进行存储等待主站召测；第3层为载波电表，采集用电数据并通过低压电力线上传至集中器。其系统结构如图1所示。

图1 低压电力线载波集中抄表系统结构

由于低压电力线的噪声干扰、信号衰减和负载的投入与撤出等因素常会使信号在电力线上传输距离变短，同时也使得通信网络逻辑拓扑结构发生动态变化，从而导致集中器与某些电表节点不能直接通信。为了保证集中器能采集到所有电表节点的数据，必须先建立起集中器到部分电表节点的通信路径，然后再以这些电表节点作为中继，进行数据的转发，扩展通信距离，才能使所有的电表节点都包含在集中抄表系统通信网络内［10］。因此，路由算法的好坏将直接影响集中抄表系统数据采集的实时性和成功率。

2.2 混合算法目标函数设计

低压电力线载波通信网络信道具有噪声干扰大，信号衰减严重、时变性强的特点，使得通信网络拓扑不稳定，常常导致路由性能降低。对于集中抄表系统而言要求保证数据采集的实时性和成功率，因此为提高低压电力线载波集中抄表系统通信网络的路由性能，本文将网络服务质量（Quality of Service，QoS）中的传输时延和丢包率列入约束条件，作为数据传输可靠性的衡量标准［11］。

在电力线载波集中抄表系统通信网络中，集中器节点s到目标电表节点d之间的延时有两部分：一部分是数据包在相邻两节点之间传输时所耗费时延总和∑D（Mi，Mj），另一部分是中继节点处理数据包所耗费的时间∑D（Mi）。集中器节点到目标电表节点时延如公式（1）：

由于噪声干扰、信号衰减、信道变化等原因，导致数据包在电力线上传输时容易丢失。设路径上Mi与Mj之间的丢包率为P(Mi，Mj)，集中器节点s到目标电表节点d丢包率如公式（2）：

考虑集中抄表系统载波通信网络对服务质量要求的特殊性，将混合算法的目标函数定义如式（3）：

式中：ν，ω—相应的权重因子，可以根据实际需求改变延时和丢包率在目标函数中所占的比重。

2.3 路由算法原理

2.3.1 蚁群算法原理

蚁群算法（ant colony algorithm，ACA）［12］是由意大利学者Marco Dorigo提出的一种新的模拟进化算法，其灵感来源于蚂蚁在寻找食物过程中发现最佳路径的生物学行为。蚂蚁在寻找食物时会在经过的路径上释放一种叫信息素的物质，这对于后续的蚂蚁有引导作用，偏向于选择信息素堆积多的路径。蚂蚁从巢穴出发去觅食，有多条可以选择的路径时，整个蚁群追踪个体产生的信息素轨迹发现觅食过程中的最短路径，最后使得所有蚂蚁选择最短路径去觅食。该算法采用分布式并行计算机制，易与其他方法结合，具有较强的鲁棒性，但搜索时间长、易限入局部最优解是其突出的缺点［13-14］。蚁群算法中主要规则如下：

（1）改进状态转移规则。

在蚁群算法中，位于节点i的蚂蚁k，按照状态转移规则选择要访问的下一个节点j，转移规则公式如下：

式中：q—0到1之间的随机数；

ηij—启发式信息；

τij—路径（i，j）上的信息素的大小；

α—信息启发式因子；

β—期望启发式因子；若y=f（x），则argmax［y］表示当y取得最大值时x的值，当q≤q0时，按照先验规律选择路径；当q＞q0时，按公式（6）进行路径搜索。

NA—当前循环次数。在算法执行过程中q0值将逐渐增大。在算法早期获得较小的q0，以确保有更多的蚂蚁可以以随机的方式选择下一个节点访问，有利于全局搜索。相反，在算法后期，q0选择相对较大的值，有助于算法快速收敛及局部搜索，这样既可以保证前期搜索路径的多样性，又可以在算法后期使搜索集中在最优路径附近。

式中：Gk—第k只蚂蚁下一访问节点的集合。

（2）局部信息素更新规则。

采用蚁群系统的局部更新规则，即蚂蚁每经过一条边则马上按公式（7）更新该边上的信息素：

式中：τij—路径（i，j）上的信息素的大小；

ρl—局部信息素挥发因子；

τ0—初始信息素的含量。

局部更新规则的引入使蚂蚁倾向于选择没有走过的路经，避免搜索过于集中在同一条线路上，这种更新规则有利于发现新路径［15］。

（3）全局信息素更新规则。

全局信息素更新是对一次迭代所有蚂蚁走过路径中最优的那条载波逻辑链路进行信息素的更新。全局信息素更新规则如公式（8）：

式中：ρg—全局信息素挥发因子；

Δτij—本次迭代路径(i,j)上的信息素增量；

Q—信息素总量；

L(s,d)min—是本次循环最优路径对应的目标函数值。

2.3.2 遗传算法原理

遗传算法（genetic algorithm，GA）是一种仿效生物界生存法则和进化机制的随机、自适应搜索方法［16］，它是把问题参数编码为染色体，然后再利用个体迭代的方式进行适应度评估、选择、交叉、变异等操作［17］。其中适应度表明个体或解的优劣。在个体的适应度评估基础上进行选择操作，将当前种群中优良的个体选出直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。交叉是两父代个体在交叉点两两交换信息而得到新个体，促使其产生新的优良个体。变异是通过改变个体中某些信息而得到新个体，增加群体中解的个数，扩大搜索范围有效避免“早熟”。

（1）交叉操作。

交叉操作规则为：将种群中任意2条路径编码从除源节点外的第一个相同节点处断开，然后将断开处到目标节点的这段路径进行交换，重新组合得到2条新的路径。其中交叉概率为pc，pc能随着适应度值的变化而变化，公式如式（10）：

式中：fmax—种群中适应度值最大的个体的适应度值；

favg—种群所有个体适应度值的平均值；

f′—交叉的2个个体适应度值中较大的那个值；

pc1、pc2—2个参数初始化时给定的值。

（2）变异操作。

变异操作规则为：在个体路径内部随机选择1个节点编码，将其变为与其相邻的节点编码，然后组成新的路径。其中变异概率为pm，pm能随着适应度值的变化而变化，公式如式（11）：

式中：pm1、pm2—2个参数初始化时给定的值。

2.3.3 混合路由算法

蚁群算法具有分布并行计算、启发式搜索等优点，但算法后期信息素过于集中在某条路径，容易导致算法陷入局部最优。遗传算法虽然全局搜索能力强，但对系统中反馈信息利用不够，在运算迭代的过程中会出现冗余的迭代，求解速度慢。

蚁群遗传混合算法克服两种算法各自的缺点，形成优势互补［18］。蚁群算法的正反馈机制能有效克服遗传算法对系统中反馈信息利用不够、容易产生多余的迭代、求解效率低的缺点。遗传算法的选择、交叉、变异等运算能够产生新的路径避免蚁群算法陷入局部最优［19］。因此，结合两种算法的优点将能适应电力线载波通信网络的动态变化，快速找到集中器节点到目标电表节点的最优载波路径。

混合算法的搜索过程：算法中将特定探测数据包看作人工蚂蚁，集中器发出数据包看作人工蚂蚁的释放。将集中器发出数据包到目标电表节点返回确认数据帧看作是蚂蚁的一次觅食完成。算法首先通过蚁群算法初步搜索产生1组从集中器节点到目标电表节点的初始路径，即得到电力线载波通信网络的逻辑拓扑，同时各终端通过接受或监听电力线上的载波信号并根据信号噪声比计算出其与其他终端的电气距离，更新其原有电气距离表［20］。然后将这组路径作为遗传算法的初始种群，以目标函数作为适应度函数进行适应度评价，接着进行选择、交叉、变异等操作，产生1组较优通信路径，接着将本次迭代蚁群算法产生的全局最优路径与遗传算法产生的1组较优路径进行比较，选择1条较优路径作为本次迭代的全局最优，同时进行全局信息素的更新。最后经过多次迭代，算法将快速收敛到最优路由路径。

2.4 仿真验证

2.4.1 仿真环境与参数设置

本文采用MATLAB软件进行仿真，在100×100的区域内取坐标为（50,50）的点为1号点代表集中器节点，2～50号节点随机生成代表电表节点。

仿真参数设置：蚂蚁数量m=20；α=1、β=2、ρl=0.2、ρg=0.96、τ0=2、Q=250、ν=2、ω=3；节点(i,j)间传输时延D(Mi，Mj)=节点(i,j)间的电气距离×0.1 ms；节点i的时延D(Mi)=5(ms)；节点(i,j)间的丢包率P(Mi，Mj)=节点(i,j)间的电气距离×0.1%；蚁群迭代最大次数NA=100；遗传迭代最大次数NG=50；pc1=0.8、pc2=0.5、pm1=0.03，pm2=0.01。

2.4.2 仿真结果

蚁群遗传混合路由算法与传统蚁群路由算法在数据包传输时延、丢包率两方面进行仿真，结果如图2和图3所示。

图2 数据包传输时延

由图2可看出，混合路由算法的收敛速度明显快于传统蚁群路由算法，减少了数据传输时延；由图3可知，随着通信距离的增加，与蚁群路由算法相比混合路由算法的丢包率要更低且变换幅度不大。

图3 数据包丢失率

3 效果评价

将蚁群遗传混合路由算法与传统蚁群路由算法在数据包传输时延、丢包率两方面进行对比，结果如表1、表2所示。

表1 2种路由算法数据包传输时延结果对比

表2 2种路由算法数据包丢失率结果比较

3.1 数据包传输时延比较

从表1结果可以看出，随着运行时间的推移2种算法的数据包传输时延前期下降的比较快，最后趋于平缓。从数据明显可以看出运用混合路由算法后的数据包传输时延在运行时间的各个时刻都比蚁群算法要低大约2～4 ms，当运行时间达到220 s时，混合路由算法的传输时延为54 ms，比蚁群路由算法降低了3.5 ms，由此说明混合算法收敛的速度更快，因而混合算法在降低数据包传输时延方面效果更好。

3.2 数据包丢失率比较

2种算法随着通信距离增加，数据包丢失率都逐渐增加。由表2数据可以看出，当通信距离每增加60 m，混合路由算法丢包率变化幅度在1%～2%之间，而蚁群算法的变化幅度在2%～5%之间，由此可得，混合算法更能适应网络的动态变化减少丢包率；当通信距离为340 m时，运用混合路由算法后的丢包率比蚁群路由算法降低了17%，因此混合算法更适用于降低数据包在传输过程中的丢失率。

4 结论

（1）本文提出的混合路由算法可根据电力线载波通信网络的实际需求自动调整路由选择策略，加快了算法收敛于最优路由路径的速度，降低数据传输延时。

（2）该混合路由算法可在算法陷入局部最优时，通过交叉、变异等运算产生新的路径，保证算法跳出局部最优，直至收敛到全局最优路由路径，降低了数据传输的丢包率。

［1］王伊瑾,张文静,李亚南.低压电力线载波抄表系统路由算法研究[J].河北农业大学学报,2013(3)∶120-124.

［2］赵永辉,张建伟,李仕林,等.基于低压电力线载波通信信道特性的分析[J].自动化与仪器仪表,2016(10)∶216-218.

［3］肖勇,房莹,张捷,党三磊.低压电力线载波通信信道特性研究[J].电力系统保护与控制,2012(20)∶20-25.

［4］林景栋,秦玉龙,廖孝勇.电力载波通信动态组网算法的研究[J].控制工程,2013(5)∶841-843+，848.

［5］朱斌泉.基于改进遗传算法的电力载波通信动态组网研究[J].南京工程学院学报(自然科学版),2012(1)∶29-33.

［6］戚佳金,刘晓胜,张良.一种低压配电网电力线载波通信网络中继算法[J].电力系统保护与控制,2010(14)∶73-78.

［7］刘晓胜,李延祥,王娟,等.低压电力线分簇蛛网混合多径盲路由算法及通信协议设计[J].电工技术学报,2015(S1)∶337-345.

［8］宋涛,蒋伟,赵勤学.低压配电网电力线载波通信路由算法研究[J].科学技术与工程,2016(2)∶169-173.

［9］樊建学,盛新富.低压电力线载波集中抄表系统的研究[J].继电器,2005(17)∶49-52.

［10］C.Ke,Q.Chenxi,Z.Tingtao，et al.Research of automat⁃ic meter reading system based on broadband carrier in the power line[C].2011 6th IEEE Conference on Indus⁃trial Electronics and Applications,Beijing,2011∶2763-2767.

［11］刘萍,高飞,杨云.基于遗传算法和蚁群算法融合的QoS路由算法[J].计算机应用研究,2007(9)∶224-227.

［12］SHTOVBA S D.Ant algorithms∶theory and applications[J].Programming and Computer Software,2005,31(4)∶167-178.

［13］段海滨,王道波,朱家强,等.蚁群算法理论及应用研究的进展[J].控制与决策,2004(12)∶1321-1326+1340.

［14］柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011(5)∶1220-1224.

［15］陈可,胡晓光.基于遗传自适应蚁群系统算法的中继路由方法[J].中南大学学报(自然科学版),2013,44(2)∶571-579.

［16］刘志,林坚海,金拓.基于改进遗传算法的必经点最短路径算法[J].信息通信,2017(2)∶46-48.

［17］尹向东.基于遗传蚁群算法的QoS路由算法研究[J].计算机工程与应用,2009(17)∶113-115.

［18］张晓玲,黄力.融入遗传算子的蚁群算法求解TSP问题[J].广西民族大学学报(自然科学版),2009(3)∶81-87.

［19］袁杰.基于蚁群遗传混合智能算法求解TSP问题[D].长春：长春工业大学,2014.

［20］冉庆华,吴玉成,祁美娟.低压电力线载波通信网络自动组网方法研究[J].电力系统保护与控制,2011(10)∶53-58，63.

A routing algorithm of power line carrier based on ant colony genetic hybridization

YANG Yong1,ZHU Junchao2,WEI Jianjun1，XU Xuanhao2
(1.Maoming Power Supply Bureau of Guangdong Power Grid Co.,Ltd.,Maoming Guangdong 525000,China;2.School of Automation,Guangdong University of Technology,GuangZhou Guangdong 510006,China)

Aiming at the problem of high delay and the high data packet loss rate in the data transmission of carrier routing algorithm for the power meter remote data acquisition system,on the basis of analyzing the carrier communication network structure of the power meter remote data acquisition system,puts forward a carrier routing method based on ant colony genetic hybridization.This method introduces the genetic algorithm in the ant colony algorithm so that the ant colony algorithm does not fall into the local optimum.And this method also improves the state transition factor and accelerates global optimal path convergence velocity of the algorithm.The simulation result shows that∶compared with ant colony algorithm,this method has obvious advantages in reducing the data transmission delay and data packet loss rate,and can improve greatly the real-time and success rate of data acquisition for the power meter remote data acquisition system.

power line carrier communication;the power meter remote data acquisition system;hybrid routing algorithm;reliability

TM714.1

A

1672-3643（2017）04-0052-06

有效访问地址：http∶//dx.doi.org/10.3969/j.issn.1672-3643.2017.04.010

10.3969/j.issn.1672-3643.2017.04.010

2017-05-12

杨永（1986），男，工程师，主要从事电力系统生产及供电运行管理工作。