一种基于异层交叠分簇组网的 低压电力线蚁群路由方法

黄身增 王金龙 曲 加

（1. 国网福建省电力有限公司漳州供电公司，福州 353000； 2. 国网西藏电力有限公司那曲供电公司，西藏 那曲 852000）

0 引言

低压电力线通信（low voltage power line communication, LVPLC）具有覆盖面广、成本低及运行维护方便等特点，已被广泛应用于远程抄表、楼宇控制等领域[1]，但低压电力线具有噪声干扰[2]、阻抗不匹配[3]等信道问题，导致低压电力线通信可靠性偏低，限制其进一步大规模应用于其他电力通信领域，因此如何提高低压电力线通信可靠性是低压电力线通信领域的一大研究热点。

目前提高低压电力线通信可靠性的研究主要分为两个方面：①从物理层出发，在滤波设计[4]和调制解调方式[5-6]上进行改进；②从网络层出发，提出更优的动态路由组网算法，对如何快速组网、选择路由中继及出现故障时如何快速恢复等方面进行研究。目前在动态路由组网算法领域有较多研究，已经取得了大量有效的成果，但也存在一定的不足 之处。

文献[7]提出了先通过非交叠分簇对低压电力线进行组网，然后利用节点间通信信道质量动态建立节点间通信路由，具有一定的自愈能力，但由于采用的非交叠分簇节点之间仅存在单一路由，一旦路由失效，会频繁触发通信系统网络重构，大大降低网络通信的实时性，不满足低压电力线通信实时性的要求。

文献[8-9]利用蚁群算法、变异遗传算法等智能优化算法来进行组网，以服务质量（quality of service, QoS）为优化目标，建立较优的网络结构，但是存在组网速度慢及实时性不足等问题。

文献[10-13]将低压电力线网络分为一个个人工蛛网，并选出蜘网中心，构建分级网络，然后利用改进蚁群算法构建每一个蜘网中心的路由通信，相比基本蚁群算法，该算法大大提高了组网效率，从而提高了实时性。基本蚁群算法是指利用蚁群算法对低压电力线进行组网及路由通信。

文献[14]采用改进Q学习算法对低压电力线进行通信组网，并引入蚁群算法建立节点之间动态路由，提高低压电力线通信实时性及可靠性。

本文针对已有文献中蚁群算法应用于低压电力线通信存在收敛速度慢、容易陷入局部最优等问题，提出一种基于异层交叠分簇组网的低压电力线蚁群路由方法，详细说明低压电力线网络组网及路由构建过程。最后通过仿真与基本蚁群算法、基于分簇蛛网的蚁群路由算法[10-11]进行比较，验证该算法的有效性和优越性。

1 低压电力线通信网络模型

低压电力线网络从物理结构上看有树形结构，比如高层电力设备；有星形结构，比如农村一些电力设备；也有树形和星形混合结构[7]。典型的低压电力线通信系统结构如图1所示，每相节点通过网关与集中器进行通信，节点之间由于受信道强干扰、信号衰减等原因导致通信距离缩短，因此当节点距离网关较远时，必须采用其他节点作为中继才能和网关进行通信，因此如何选择较优中继路由及快速组网是实现大规模低压电力线通信的必要条件。

图1 低压电力线通信系统结构

2 异层交叠分簇组网算法原理

2.1 交叠分簇结构

分簇算法是指将网络依照某种规则分为一个个的簇，并从簇中选择一个簇头，簇内其他成员的通信及数据传输等都由簇头进行管理，簇头是簇内成员与外界通信的代理人。

交叠分簇结构是指加入一个簇的节点可以再加入另一个簇中，交叠分簇结构如图2所示，网络分为两个逻辑层，其中，节点3、5、6都加入两个簇中，网关节点到达节点6有0→4→6和0→7→6这两条路径，存在冗余路径，不存在非交叠分簇结构只具有单一通信链路的问题。

图2 交叠分簇结构

2.2 异层交叠分簇组网算法

基本蚁群算法可以在未知低压电力线网络拓扑的情况下，建立整个低压电力线网络的通信路由拓扑，该算法由于采用随机搜索，必然存在收敛速度慢及陷入局部最优解等实时性低的问题，故本文提出一种异层交叠分簇组网方法，它通过交叠分簇的方法将全部节点分为多个簇，簇与簇之间存在层次关系，消除同一层之间节点通信，只保留异层通信，解决了基本蚁群算法在同层路径迭代中可能存在无效搜索，以及在同层中迭代，不能快速地搜索全网络、收敛速度慢和容易陷入局部最优解的问题。

1）算法步骤

异层交叠分簇组网算法的步骤如下：

（1）上电后网关节点将节点所在的逻辑层数设置为0，网关节点和子节点的路由表为空。

（2）网关节点广播组网报文，组网报文包括节点的物理地址及所在的逻辑层数，子节点收到网关的组网报文后，将节点的逻辑层数设为1，并根据CSMA协议依次发送响应报文，响应报文包括节点的物理地址及所在的逻辑层数，网关节点收到子节点响应报文后，将子节点加入网关路由表中。

（3）已加入逻辑层1的节点广播组网报文，此时收到组网报文的节点分为四类：

①逻辑层数小于组网报文源节点（在这里只能是网关节点），节点丢弃该报文，不发送响应报文。

②逻辑层数等于组网报文源节点的，说明与源节点在同一逻辑层，节点也丢弃该报文，不发送响应报文。

③未分配逻辑层数的节点，将该节点加入以组网报文源节点为簇头的簇中，并将该节点的逻辑层数设为组网报文的逻辑层数加1，根据CSMA协议发送响应报文。

④逻辑层数大于组网报文源节点的，说明该节点已加入某个簇，为了实现交叠分簇，收到组网报文的节点发送响应报文给组网报文源节点，将节点加入以组网报文源节点为簇头的簇中。发送组网报文的节点收到子节点响应报文后，将该子节点加入发送组网报文的节点的路由表中。

（4）重复步骤（3），直到不存在未分配逻辑层数的节点，则组网完成。

按照此算法进行组网，无需知道整个网络的拓扑结构，实现对未知网络进行组网，并将组网后的信息保存在路由表中，供下一步蚁群算法寻找最优路径使用。

2）仿真分析

采用Matlab进行仿真研究，在100m×100m区域随机分布1个网关和39个节点，网关节点位于坐标原点，物理ID设为1，其他节点的物理ID分别为2, 3, …, 40，节点之间有效通信距离为30m，则低压电力线网络拓扑如图3所示，根据异层交叠分簇组网算法，组网结果如图4所示，它将网络分割为具有层次关系的多个交叠簇，只保留异层通信，网络结构优化，为后续蚁群算法路由寻优创造条件。

图3 低压电力线网络拓扑

图4 异层交叠分簇组网拓扑

3 基于异层交叠分簇组网的蚁群路由算法

基于异层交叠分簇组网的蚁群路由算法流程如图5所示。

图5 基于异层交叠分簇组网的蚁群路由算法流程

1）利用异层交叠分簇组网对低压电力线网络进行组网，消除同一层之间节点通信，只保留异层通信，优化网络路径。

2）初始化蚁群个数、迭代次数、信息素矩阵及禁忌表等参数。

3）每一只蚂蚁从网关出发寻找目标节点，并将网关节点加入禁忌表中。

4）计算可以到达的下一跳节点，并对下一跳节 点集合进行重排采样，计算下一跳转移概率，采用轮盘赌方法选择下一跳。

5）判断是否到达目标节点，若没达到目标节点，则转到4）；若到达目标节点，则保存当前蚂蚁行走路径，并清空禁忌表。

6）判断是否所有蚂蚁都到达目标节点，若没有，则转到3）；若已全部到达目标节点，从蚂蚁行走路径选择一条最优路径，并对最优路径进行全局信息素更新。这里不同于基本蚁群算法，仅更新最优路径的信息素，而不是对蚂蚁在此次迭代中的所有路径进行信息素更新。

7）判断当前最优路径是否已收敛，若收敛，则得到最优路径，算法结束；若没有收敛，将迭代次数加1，并判断当前迭代次数是否已达到最大值，若已达到最大值，则算法结束；若没有达到最大值，则转到3）。

4 仿真实验

4.1 仿真环境与参数

采用Matlab进行仿真研究，仿真参数见表1，在100m×100m内的区域内随机分布着40个节点，网关节点位于坐标原点，物理ID设为1，其他节点的物理ID分别为2, 3,…, 40，节点之间有效通信距离为30m，低压电力线网络拓扑如图3所示。

表1 仿真参数

分别采用基本蚁群算法、分簇蛛网蚁群路由算法及异层交叠分簇蚁群路由算法搜寻网关节点到节点31之间的最优路由，对三种算法的最优路径距离及最优路径节点个数这两个指标进行仿真分析。

4.2 仿真结果与分析

图6所示为三种算法迭代次数、最优路径距离的分析比较。从图6曲线中可以看出，随着迭代次数增加，这三种算法最优路径距离都逐渐下降，最终收敛；基本蚁群算法经过12次迭代后，最优路径距离从194m缩短到120.9m，分簇蛛网蚁群路由算法经过7次迭代后，最优路径距离从150.4m缩短到133.1m，而异层交叠分簇蚁群路由算法经过2次迭代后，最优路径距离从121.6m缩短到120.9m，相比基本蚁群算法、分簇蛛网蚁群路由算法，异层交叠分簇蚁群路由算法优化了网络，收敛速度更快，且最终的最优路径为全局最优。

图6 最优路径距离迭代分析比较

图7为三种算法最优路径节点个数的分析比较，基本蚁群算法与分簇蛛网蚁群路由算法在迭代过程中，最优路径节点个数有所变化，但最终收敛，基本蚁群算法经过12轮迭代，最优路径节点个数收敛于7，分簇蛛网蚁群路由算法经过7次迭代，最优路径个数收敛于8，而异层交叠分簇蚁群路由算法在第一轮迭代最优路径节点个数就已收敛于7，充分表明了异层交叠分簇蚁群路由算法收敛速度更快，且最优路径节点个数为全局最优解。

图7 最优路径节点个数分析比较

5 结论

针对蚁群算法应用于低压电力线通信领域存在收敛速度慢、容易陷入局部最优等问题，本文提出了一种基于异层交叠分簇组网的蚁群路由算法，该算法通过交叠分簇的方法将全部节点分为多个簇，消除同一层之间节点通信，减少了蚁群算法在同层路径迭代中可能存在无效搜索，以及在同层中迭代，不能快速地搜索全网络的情况，优化了网络结构。经过仿真分析，相比基本蚁群算法及分簇蛛网蚁群路由算法，该算法的收敛速度大幅度提高，且收敛的最优路径为全局最优，为蚁群算法进一步应用于低压电力线领域提供了坚实的基础，具有一定的实际意义。