基于改进蚁群算法的电缆防盗网络组网方法

李姣军，贾智予，张亭亭，曾令果

(1.重庆理工大学 电气与电子工程学院， 重庆 400054； 2.重庆渝丰电线电缆公司， 重庆 402247)

基于改进蚁群算法的电缆防盗网络组网方法

李姣军1，贾智予1，张亭亭1，曾令果2

(1.重庆理工大学 电气与电子工程学院， 重庆 400054； 2.重庆渝丰电线电缆公司， 重庆 402247)

为了使应用于低压配电网络中的电缆防盗系统能够可靠、快速地实现系统中主从站点间的通信，在分析系统工作方法、主体结构及拓扑变化的前提下，给出一种基于改进蚁群算法的系统组网方法。该方法对蚁群算法中的信息素挥发系数进行数值大小的限制，尽可能地扩大搜索范围，降低算法陷入局部最优的可能性，从而在全局最优的情况下获得算法的最优解。仿真结果表明：改进的蚁群算法在网络状态正常及发生故障的情况下，都具有更快的寻优速度，且完成通信所需的节点跳数更少，有效地提高了电缆防盗系统的运行可靠性，从而保障了系统实时监控功能的实现。

电缆防盗； 电力线通信； 网络拓扑； 改进蚁群算法； 可靠性

应用于低压配电网的电缆防盗系统主要由控制中心、通信主站和通信从站3部分构成，其中通信主站与通信从站之间的通信方式即为电力载波通信。在系统中，除控制中心仅有一个外，通信主站与从站皆有多个，且按照单个主站来进行区域的划分，每个主站及其下属的所有从站为一个通信区域。因此，需要考虑一种合适的组网方式来实现区域中主、从站点间信息的快速、可靠交互。

文献[1]对高速公路电线电缆防盗系统进行研究，并采用Dijkstra(迪杰斯特拉)算法对系统进行组网，但该算法只适合规划静态路径，对电缆防盗网络这类动态组网问题在具体实现上有一定难度和缺陷。文献[2-3]对类似的路灯控制系统组网方法进行研究，采用基本蚁群算法进行组网，能够实现系统中站点信息的互通，且具有一定的抗毁性，但其收敛速度较慢，容易陷入局部最优。文献[4]对低压配电网的抄表系统组网方法进行研究，采取免疫-蚁群算法进行组网，在一定程度上改善了局部最优化的情况，但其收敛速度仍较慢[1-4]。

本文首先对电缆防盗系统网络进行分析，根据其结构和工作特性，讨论进行组网操作时需要注意的特点及相应的要求，在此基础上给出一种改进的蚁群算法，对蚁群系统算法中的信息素挥发系数进行改进，设置上下限值，以便扩大搜索范围，减缓局部收敛的速度，使得防盗系统网络在正常运行及发生故障的情况下都能够快速地找到最优路径，完成组网操作，实现系统监控的实时化。该算法操作简单，能够为动态变化的电缆防盗系统网络提供一种可靠、有效的路由寻找方法。

1 系统网络模型分析

电缆防盗系统是由各主站利用合适的检测技术对电缆的通断状态进行监测，并使用恰当的通信手段将状态信息发送给控制中心。在低压配电网中，一个区域变电站通过管辖多个变电器来实现电力的传输与控制。根据这种网络结构设计的电缆防盗系统由控制中心、通信主站和从站构成，如图1所示。系统仅有一个控制中心，其通过无线GPRS来接收各个主站上报的信息并下发相关的指令。系统按单个变电站来进行区域的划分，区内设置一个主站(即变电站)和若干个从站(即变电站管辖范围内的变电器)，主从站间通过电力载波通信方式进行数据的交互，只要电缆未被剪断，主、从站之间的通信就能够顺利进行。

图1 电缆防盗系统结构

目前，根据我国低压配电网的负荷等级、容量和分布等情况确定其线路接线方式主要有放射式、树干式和环形式3种。当在低压配电网中进行数据通信时，其网络结构通常可看做是以树形接线方式为基础的混合拓扑[5]，如图2所示。以一个变电站控制的区域为例，节点1代表系统中的主节点(主站)，2～40号节点都为从节点(从站)。

图2 电缆防盗系统网络拓扑图

2 电缆防盗网络的PLC组网

2.1 电缆防盗网络的组网特点

由于低压配电网的主要功能是传输电力，当其作为通信信道进行数据传输时，具有与专业通信信道不同的特点。

首先，尽管区域内的配电网线路是固定的，但需要考虑到各电气设备从网络中切除以进行定期检修等其他操作的情况，当有设备接入、切除时，网络拓扑的结构会随之发生相应的改变[6]。

其次，电力网络中没有专用的中继器或交换机，难以实现通信信号的转发和放大，且电力线信道具有噪声干扰、阻抗输入、信号衰减等特性。因此，数据信号的传输距离会随着网络中信道质量的变化而发生改变。

此外，考虑到防盗系统的结构和相关设备部分需要实现的功能，如控制中心需要监控整个网络中的数据采集情况，并在发生故障时下发相应的操作指令，主站在完成收发数据并上报的任务外还需具备相对复杂的判断功能等，二者都需具备较强的CPU数据处理能力； 而从站仅需完成接收数据请求和发送数据应答的简单操作，其CPU处理能力很弱甚至仅具有执行器或数据采集器。因此，常用的计算机网络路由算法不能直接应用于电力网络组网。

2.2 电缆防盗网络的组网要求

结合以上所述的组网特点，所设计的电缆防盗系统网络组网算法应能满足以下4个要求[7]：

1) 采用改进蚁群算法对电缆防盗系统网络进行组网的首要任务是：找到一条可供数据从源节点(主站)传送到目标节点(从站)的最优路径。

2) 当通信网络结构发生变化，如某些通信节点损坏或进行其他操作导致节点退出逻辑网络，致使部分路径通信失效时，组网算法能够重新找到一条数据传送的路径，从而实现通信网络的重组。

3) 在网络进行通信的过程中，任意时刻都只能有一个通信节点进行数据发送操作。考虑到系统网络的盲结构，在组网时，只有主节点具有所有从节点的路由表，各从节点仅知晓向主节点回复的路径及附近能够直接通信的节点信息。

4) 能够满足目标节点的即插即用功能。网络中的所有节点都拥有自己的物理ID来与其他节点进行区别，除此之外的通信过程完全相同。当系统网络发生变化时，仅需增加或删除网络中的节点即可。

2.3 电缆防盗系统组网过程

正常情况下，电缆防盗系统在每次上电后都会立即开始进行自动组网操作。主节点会向每一个从节点发送广播数据包，并根据从节点的数据应答帧中的地址信息建立、更新其节点可通信路由表[8]。

当系统网络中发生故障，如低压电力线上产生的各种衰减、干扰或某些从节点无规律地接入、切除时，原有的网络逻辑拓扑就可能遭到破坏，从而导致通信路径发生改变。某次系统网络的动态变化如图3所示：18～24号节点间的通信链路在某一时刻因发生断线或强烈噪声干扰而无法有效传输数据，这将导致以18号节点为中继的24号、25号及其后的节点在逻辑上退出通信。

图3 发生动态变化的局部网络拓扑

为了解决以上网络问题，需要采用自动组网路由算法来进行网络的动态重组，使24、25号节点能够重新加入网络并继续进行通信工作，实现网络的自愈。

3 算法原理及实现步骤

3.1 蚁群算法基本原理

蚁群算法(ant colony algorithm,ACA)，也称为蚁群优化算法(ant colony optimization,ACO)，是一种受自然界中蚂蚁搜寻食物行为启发而得到的优化算法[9]。蚁群算法通过信息素更新和启发式信息来指导人工蚂蚁寻找优秀候选解，并通过多次迭代获得最优解。蚂蚁在搜寻路径时会留下信息素，因此较为理想的路径(如路径长度较短)能从更多的蚂蚁处得到信息素，从而增加了后续蚂蚁经过该路径的可能。同时，路径上的信息素会按照某一系数ρ挥发掉，以此来避免搜索过程的过早停止。最终，能够找出最优解。由算法实现原理可以看出：该种算法是一种性能优良的启发式随机优化算法，它采用正反馈和负反馈相结合的方法来实现分布式全局优化，通过信息素的释放和挥发来获取搜索路径的不断改善，从而使结果最终收敛于最优解[10]。

3.2 蚁群算法实现

当需要考察网络的通信效果时，可以采用路径长度、信道带宽、丢包率、平均通信量和时延等作为优化目标。本文中将主节点到目标从节点所需要的“跳数”作为优化目标，以“通信距离”作为约束条件。“跳数”在本文中是指数据由主节点向目标从节点发送时需要被转发的次数。例如两个可以直接进行通信的节点，二者间发送数据时的跳数为0； 若需要一个中继节点进行转发才能够到达目标节点，则跳数为1。“通信距离”在本文中指两个可以直接进行通信的节点所跨过的节点数加1，以图3中的部分网络为例，2号节点能跨过5号节点与11号节点直接通信而无需中转，二者通信距离为2。

3.2.1 全局更新规则

算法中的人工蚂蚁个数需根据网络的复杂程度来进行选择，考虑到图2中每条支路的长度有限，因此选择每批蚂蚁为10只。在进行全局信息素更新时，选用最大最小蚁群算法的更新规则，对信息素的大小进行限制，设置信息素数值的上限和下限[11]，以此来防止算法的过早停滞和陷入局部最优。由于电缆防盗系统组网仅需建立中心节点到各从节点的路由，因此将人工蚂蚁均放在中心。每完成一次迭代，就按式(1)进行全局信息素更新：

τij(t+1)=ρτij(t)+Δτbestij

(1)

其中：ρ为当前次迭代中全局信息素的挥发系数； Δτbestij为在当前次迭代中获得的最优路径上的信息素增量，可根据式(2)获得。

(2)

其中：Lib表示当前次迭代中的最优解，K为系数，它与ρ值的选择都可以调整迭代最优路径信息素的增长速度。算法在进行过程中仅对迭代最优线路进行信息素的增加，对其他路径上的信息素作挥发处理，这可以使搜索过程更具指导性，能够使蚂蚁的搜索主要集中在迭代最优路线的周围。

3.2.2 局部更新规则

本算法采用蚁群系统算法(ACS)中的局部信息素更新规则，对每只蚂蚁走过的路径都进行更新，当前一批蚂蚁完成路径寻找后，更新途经路径上的信息素，以此来影响后续蚂蚁的寻优行为，使它们有更大的可能找到较好(即信息素较多)的路径。

局部信息素按式(3)进行更新：

τ(r,s)=(1-ξ)·τ(r,s)+ξ·τ(0)

(3)

其中：ξ(0<ξ<1)为局部更新时的信息素挥发系数。τ(0)为局部信息素的初始值，若两个节点间能直接通信，则该条线路上的信息素初值为τ(0)=10。ξ越大，搜索范围越大，但算法的收敛效果会变差。

3.2.3 路径转移

某一时刻，一只位于节点r的蚂蚁根据式(4)中给出的规则选择下一个要经过的城市u。

(4)

其中：q0为算法中设置的参数，q为(0,1)范围内的一随机数。当q≤q0时，蚂蚁将根据信息素浓度τ(r,u)和启发式信息η(r,u)选择下一节点u，启发式信息η(r,u)为城市r、u之间距离的倒数； 当不需根据先验知识进行路径选择时，路径选择概率按式(5)获得：

(5)

在式(5)中：α、β分别为信息素和启发式信息的重要度参数，二者的取值大小分别表明了信息素浓度和启发式信息对路径选择的重要性。

4 算法仿真验证

仿真实验模拟电缆防盗系统网络的拓扑结构，利用Matlab仿真软件在一个100×100的范围内随机产生40个节点，依次给节点编号。1号节点作为载波主节点，表示防盗系统网络中的通信主站； 2～40号节点作为普通载波从节点，表示防盗系统网络中的通信从站。假设：网络中的任意两个相邻节点可以进行可靠的数据通信； 通信的逻辑拓扑图为无向图； 每个节点都有其唯一的地址编码。仿真实验中参数值的设置如表1中所示。

表1 仿真参数设置

采用基本蚁群算法和改进蚁群算法进行组网操作时的跳数对比，如图4、5所示。图4为网络正常情况下由源节点至目标节点35所需的跳数对比； 图5为网络中节点19因故退出通信时所需的跳数对比。

图4 搜索35号节点所需跳数对比

图5 节点19退出通信时所需跳数对比

4.1 算法收敛性比较

收敛性是评价算法性能优劣的基本指标。在图4由源节点到达单一目标节点35的跳数对比图中能够看出：采用基本蚁群算法时，常会陷入局部最优，使搜索一度陷入停滞，导致进程较慢，取得最优解所需的次数为39次，远多于改进蚁群算法的18次。相比之下，采用改进蚁群算法进行路径寻优时，由于改进了信息素的更新原则，使搜索的范围更为全面，不容易陷入局部最优，因此搜索过程几乎无停滞，并且更早地搜索到最优路径，有效提高了路由组网的效率，能够更好地进行电缆防盗系统中的组网与通信。

4.2 算法抗毁性比较

由于电缆防盗系统是基于低压配电网建立的，因此低压电力线信道的时变、噪声等特性都会影响电缆防盗网络的拓扑结构。这就要求电缆防盗系统能够在网络状态发生变化时迅速地进行网络重组，以减小网络动态变化对通信可靠性的影响。因此，算法的抗毁性也是评价算法性能的一项重要指标。

仿真采用与正常情况相同的基本网络条件，令节点19因故退出网络，分别采用基本蚁群算法与改进蚁群算法对电缆防盗系统网络进行通信路线的重建，所需跳数的对比如图5所示。从图中能够看出：基本蚁群算法需25次搜索到最优路径，改进蚁群算法仅需10次即可搜索到最优路径。改进蚁群算法在搜索速度上明显优于普通蚁群算法，且搜索空间较广，能够在电缆防盗系统网络拓扑发生变化时实现网络的动态重组，使网络具有一定的抗毁性，进而保证网络在发生故障时，依旧能较快地找到新的通信路径以保证数据的可靠传输。

5 结束语

基于低压配电网建立的电缆防盗系统，根据其网络的特点需要采用动态组网方式来保证系统的正常通信。本文中采用改进的蚁群算法对电缆防盗系统网络进行组网的仿真操作，其结果表明：该算法能够有效改善基本蚁群算法进行组网操作时易陷入局部最优、搜索易停滞及搜索速度较慢的缺点，并使该系统在网络状态发生变化时具有一定的抗毁性和重组能力，能够较好地保障电缆防盗系统的可靠运行，为实现电缆防盗的实时监控提供了一种有效的技术方案。

[1] 唐妍.高速公路电力电缆、电力设备的智能监测防盗系统研究[D].重庆：重庆大学，2011.

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

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

[4] 高庆,吕霞付.基于免疫-蚁群算法的电力线载波抄表动态路由方法[J].自动化与仪器仪表,2014(1):108-111.

[5] 野莹莹,付丽君,程立英.基于MATLAB的蚁群算法仿真研究[J].装备制造技术,2008(11):13-14.

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

[7] 吴兆平,杨俊杰,高聪慧,等.低压电力线载波通信路由算法研究[J].电测与仪表,2015,52(15):108-112.

[8] 徐东明,李育泽.低压电力线通信的双种群遗传蚁群路由算法[J].西安邮电大学学报,2017,22(1):23-27.

[9] VLACHOU C,BANCHS A,HERZEN J,et al.How CSMA/CA with deferral affects performance and dynamics in power-line communications[J].IEEE/ACM Transactions on Networking,2017,PP(99):1-14.

[10] TSOKALO I,RADEKE R,LEHNERT R.Enhancement of backoff algorithm in CSMA/CA protocols for broadband PLC[C]//IEEE International Symposium on Power Line Communications and ITS Applications.[S.l.],IEEE,2013:47-52.

[11] 陈晓娟,耿雪莹.低压电力线载波通信的动态路由算法[J].黑龙江电力,2013,35(1):6-8.

NetworkConstructionMethodofCableAnti-TheftNetworkBasedonImprovedAntColonyAlgorithm

LI Jiaojun1, JIA Zhiyu1, ZHANG Tingting1, ZENG Lingguo2

(1.College of Electrical and Electronic Engineering, Chongqing University of Technology, Chongqing 400065, China; 2.Chongqing Yufeng Wire & Cable Company, Chongqing 402247, China)

Under the premise of analyzing the working method, main structure and topology of the system, it gave a network construction method based on improved ant colony algorithm, in order to make the cable anti-theft system applied in low voltage distribution network quickly and reliably realize the communication between the master and slave sites in system. This method limits the size of parameter which represents the volatilize speed of pheromone, and expands the searching scope as far as possible, and reduces the possibility of falling into local optimum, and finally obtains the global optimal solution of the algorithm. The simulation results of algorithm show that the improved ant colony algorithm has faster optimization speed in the case of normal and unnormal network state, and the number of nodes required to complete the communication is less. This algorithm effectively improved the reliability of cable anti-theft system, and ensure the realization of real-time monitoring function.

cable anti-theft; power line communication; network topology; improved ant colony algorithm; reliability

2017-06-20

重庆市科委基础与前沿研究一般项目(cstc2014jcyjA40003)

贾智予(1993—)，女，江苏无锡人，硕士研究生，主要从事电力线载波通信研究，E-mail：505534432@qq.com。

李姣军，贾智予，张亭亭，等.基于改进蚁群算法的电缆防盗网络组网方法[J].重庆理工大学学报(自然科学)，2017(12):160-165.

formatLI Jiaojun, JIA Zhiyu, ZHANG Tingting, et al.Network Construction Method of Cable Anti-Theft Network Based on Improved Ant Colony Algorithm[J].Journal of Chongqing University of Technology(Natural Science)，2017(12):160-165.

10.3969/j.issn.1674-8425(z).2017.12.028

TM76

A

1674-8425(2017)12-0160-06

(责任编辑陈 艳)