基于图论生成树的低压电力线通信路由方法＊

李 祥，刘宏立，刘述钢，2，谷志茹，陈 艳

（1.湖南大学电气与信息工程学院，湖南长沙410082；2.珠海中慧微电子有限公司，广东珠海519085）

1 引言

低压配电网具有电力线分布广泛、不用布线、投资成本低；而且电力线不易破坏，后期维护量小的特点。因此，低压电力线通信前景被十分看好。高可靠性、高速率已经成为电力线载波通信网络的重要目标。然而，由于低压配电网上输入阻抗变化复杂、噪声干扰使得信号衰减严重［1～4］；用户供电范围和供电对象的经常变化，以及负载加入退出的不确定性，使得低压配电网具有很大的时变性。这些因素都会严重影响低压电力载波通信的可靠性。

为了提高电力线通信的可靠性，目前国内外主要从物理层和网络层两方面来着手［5～7］。物理层方面主要通过信道估计、信道编码以及调制解调方法等方面来考虑；网络层方面主要通过选择合适的中继组网算法。

目前国内外已经有很多学者对于低压电力线载波的中继组网算法进行了研究［8～10］，比如类蚁群算法、分簇算法等。它们都能够实现中继组网，具有一定的适用性，同时也有一定的局限性。类蚁群算法，即是一种随机搜索算法，也是一种比较耗时的算法，同时容易陷入局部最优。分簇算法在网络的可靠性和抗毁性上具有一定的优势，但是对于网络节点要求具有一定的路由能力，在工程应用中会增加产品成本。

本文针对网络节点仅具有中继转发功能的低压电力线通信网络的路由方法进行研究，首先对低压配电网的物理拓扑结构和逻辑拓扑结构进行分析；然后结合低压集中抄表工程应用中对于网络节点能力的要求，通过对图论生成树的遍历搜索算法进行研究，提出了基于遍历搜索算法的中继组网策略和网络维护策略；最后进行了实验研究并做出了分析。

2 低压配电网通信网络模型

2.1 低压配电网物理结构

低压配电网电力线通信网络物理拓扑结构和应用场所紧密相关，物理拓扑复杂多变，但总体上可以归纳为星型拓扑和树型拓扑［11］。本文以配电网单相的树型拓扑结构作为重点研究对象，如图1所示，图中弧上的数字表示该网络的各点之间的距离。

Figure 1 A typical structure of single－phase tree topology of distributions图1 一种典型的配电网单相树型拓扑结构

2.2 低压配电网逻辑结构

由于受到低压电力线信道高衰减和强干扰的影响，使得原本物理连通的节点间的通信并不可靠，它们的可靠通信距离会受到影响。假设图1中集中器和单相表的最大有效通信距离是10，可以得出图2所示的逻辑拓扑结构。由图2可见，单相表1是连在四条分裂总线上的。因此，对于终端较多、分布不均匀的低压配电网来说，其拓扑结构是一个非常复杂的图［12］。

Figure 2 Single－phase logic topology structure of distributions图2 配电网单相逻辑拓扑结构

3 基于图论生成树的遍历搜索路由组网与重构算法

3.1 数学模型的建立

将图2所示的配电网逻辑拓扑结构抽象为连通图G（V，E），记为G（V（G），E（G））。如图3所示，其中，V（G）称为图G的顶点集，元素v∈V，称为图G的顶点。E（G）称为图G的边集，元素eij∈E为V中元素的有序对，称为图G从vi到vj的一条边。在低压电力线通信网络中，由于通信信道的变化，节点间的有效通信距离也是动态变化的，所以，集合E可以看作是动态的。

Figure 3 Routing model of power line communication network图3 电力线通信网络的路由模型

生成树是当且仅当一个图的生成子图是连通图且不含回路的。图4给出了图3中连通图的生成树。

因为在任何两个顶点之间都有生成树里的通路，所以有生成树的简单图必然是连通的，而且每个连通图都有生成树。那么，在连通图的数学模型构建之后，我们的目标就转化为如何在连通图中寻找它的一个生成树。由此，电力线通信网络中的节点通信问题就可以抽象为图论中怎样形成图的生成树的问题。

Figure 4 Spanning tree of routing model of power line communication network图4 电力线通信网络路由模型的生成树

3.2 广度优先搜索路由组网算法

一般情况下，一相电网内有一个中心节点，n个（n≥1）普通节点，电力线物理链路是连通的，且满足如下条件：

（1）中心节点的地址为0，普通节点的地址为1，2，3，…，n。

（2）中心节点具有路由功能，其他普通节点仅具有载波信号中继转发的功能。

（3）中心节点按照其存储的普通节点的物理地址进行通信组网。

（4）普通节点的通信中继级别不超过7级。

在图论生成树的遍历搜索算法中包含深度优先搜索和广度优先搜索。深度优先搜索算法是从某一顶点开始尽可能深入到未搜索过的顶点中去，总是从一个顶点搜索到另一个新的顶点，直到不能进行才返回。广度优先搜索算法是按照由近及远的顺序去搜索每个顶点，在不产生简单回路的情况下搜索完所有的节点。由于深度优先搜索算法和广度优先搜索算法的复杂度为O（e），e为连通图的边数［13］。忽略电信号在铜介质中的传输时间，电力线通信网络中心节点到目的节点之间通信的时间消耗与目的节点深度成正比，且在某些实际工程中普通节点仅具有中继转发而不具备路由功能，为了快速地实现通信组网，本文选择广度优先搜索算法以得到最优解。

广度优先搜索路由组网算法主要包括以下步骤：

步骤1 由中心节点按照其存储的普通节点地址来顺序发送组网命令，接收到组网命令的普通节点通过地址识别，如果是本节点的地址就回复一个响应帧数据，如果不是本节点的地址就忽略本条命令。对于所有的普通节点都发送命令访问一遍之后，中心节点将回复响应帧的m个普通节点添加到生成树的第一层。

步骤2 如果普通节点都已经添加到生成树中，那么组网成功；否则，中心节点以生成树第一层节点作为一级中继节点来访问还未加入生成树的（n－m）个节点。中心节点发送组网命令帧中将包含中继节点地址和目的节点地址。组网访问顺序为：以第一层的第k个节点（k＝1，2，…，m）作为中继节点依次访问没有加入生成树的所有节点。接收到组网命令帧的普通节点判断目的地址是不是本节点的目的地址，如果是则发送响应帧，如果不是则忽略。中心节点将回复响应帧的j个普通节点添加到生成树的第二层，并记录它们的中继节点。

步骤3 如果此时普通节点都已经添加到生成树中，那么组网成功；否则，中心节点以生成树第二层节点作为二级中继节点来访问还未加入生成树的（n－m－j）个节点。具体中继组网访问顺序和方法与步骤2相同。

步骤4 中心节点通过增加中继级别来搜索剩余的普通节点，直到将所有n个普通节点都添加到生成树为止；若中继级别大于7级，还存在剩余节点，则组网结束，剩余节点为孤立节点。

广度搜索遍历算法组网流程图如图5所示。其伪代码如下：

3.3 路由重构算法

Figure 5 Flow chart of network organizing of breadth traversal search algorithm图5 广度遍历搜索算法组网流程图

由于低压电力线载波的时变性和未知性，在成功组网之后，如果发现节点k（中继级别为x）暂时不能通信，则中心节点开始发起路由重构过程。路由重构算法是基于广度优先搜索算法的改进，考虑到按照广度优先搜索算法组网建立的通信网络中，网络节点的深度最小，在路由重构时，首先考虑原中继级别中的其他节点作为中继，其次再考虑比原中继级别高一级的节点作为中继，然后再依次递减原中继级别。具体实现步骤如下：

步骤1 中心节点按照原路径m次（10≤m≤15）尝试通信节点k。由于低压载波网络具有时变性，频繁更换路由路径反而不利于通信的稳定和可靠。若多次尝试原路径通信成功，则路由重构成功。

步骤2 在原路径多次尝试失败的情况下，开始尝试历史路径k次（3≤k≤5）。历史路径为曾经通信成功的路径。若尝试历史路径通信成功，则路由重构成功。

步骤3 开始尝试新的路径。保持原中继级别，即通过x层节点来作为中继尝试探测节点k。若x层节点作为中继节点能够探测成功，则路由重构成功。

步骤4 其次，满足中继级别x＜7时，尝试新的路径，否则跳过此步骤。将原中继级别加1，即通过（x＋1）层的节点来作为中继尝试探测节点k。若（x＋1）层节点作为中继节点能够探测成功，则路由重构成功。

步骤5 再次，若满足中继级别x≥1，尝试新的路径，否则跳过此步骤，进入步骤7。将原中继级别减1，即通过（x－1）层的节点来作为中继尝试探测节点k。若（x－1）层节点作为中继节点能够探测成功，则路由重构成功。

步骤6 尝试新的路径策略。若上述方法都不能与节点k通信成功，则中继级别一直减少至直接通信。若能探测成功，则路由重构成功。

步骤7 重新搜索新的路径。按照直接通信、1级中继、…、7级中继的顺序尝试探测节点k。若能探测成功，则路由重构成功。

步骤8 若上述步骤都不能将路由重构成功，则判断节点k已经脱离低压电力线载波通信网络。

网络路由维护算法流程图如图6所示。其伪代码如下所示：

4 实验研究

4.1 虚拟电力线网络的实验研究

以中慧公司开发的电力线网络虚拟平台《配电台区仿真测试系统》来验证算法的可行性。该虚拟平台是针对低压电力线集中抄表系统专门设计与开发的，能够虚拟载波网络的拓扑环境，并经华北电科院测试通过。在整个实验环境中，采用威胜集团研发的DJGZ33－WFET1600集中器，并搭载中慧公司生产的路由模块，本文的路由算法已经在路由模块中实现。通过UART串口将路由模块与PC机相连，在PC机中虚拟载波网络结构。实验环境如图7所示。

Figure 7 Experimental environment of virtual network图7 虚拟网络实验环境

为验证算法的有效性，建立一个与实际系统近似的简化网络结构，该结构是一个具有6级的网络结构，其中第一级包含5个节点，第二级包含7个节点，第三级包含2个节点，第四级包含1个节点，第五级包含1个节点，第六级包含1个节点。虚拟电力线网络物理拓扑结构如图8所示，虚拟电力线网络逻辑拓扑结构如图9所示。

Figure 8 Physical topology structure of virtual power line network图8 虚拟电力线网络物理拓扑结构

实验1 通过集中器下发抄表命令，启动路由模块开始抄表组网，运行于路由模块中的路由算法通过UART串口抄读PC机中的虚拟表，最终所有虚拟表组网成功，如图10所示，组网时间为11分59秒，组网成功率为100%。其组网生成树如图11所示。

Figure 6 Flow chart of routing reconfiguration algorithm图6 路由重构算法流程图

Figure 9 Logic topology structure of virtual power line network图9 虚拟电力线网络逻辑拓扑结构

Figure 10 Chart of network organizing success of experiment 1图10 实验1组网成功图

Figure 11 Spanning tree of network organizing图11 组网生成树

实验2 在实验1的基础上，删除节点37，此时网络生成树如图12所示。由于节点51需要节点37作为中继节点进行通信，网络出现通信故障，需要进行网络重构。此时当路由模块多次按原路径与节点51进行通信失败，则开始变换路径进行试探，按照前面讲述的路由重构策略进行试探。在同级中继中尝试以节点36、38、39、40作为中继，通信均失败；然后再在高一级中继中尝试以节点41作为中继，通信成功；节点51添加到生成树中。重构后生成树如图13所示。重构时间为18分32秒，重构成功率为100%。

Figure 12 Spanning tree after deleting node37图12 删除节点37后生成树

Figure 13 Spanning tree after reconfiguration图13 重构后生成树

虚拟电力线网络的实验结果表明：利用遍历搜索算法能够实现低压电力线载波通信组网，同时能根据网络节点的变化实现动态路由，以保证网络通信的可靠性。

4.2 实验研究

测试环境为威胜集团厂房，共挂载104块载波电能表，该载波电能表仅具有中继转发功能。使用DJGZ33－WFET1600集中器进行抄表，路由模块采用ARM Cotex－M4为MCU，并外扩8M Flash用于存储路由表。

实验1 组网测试。在路由未知的情况下进行第一次抄表，即网络组网，其每个时段的抄表数如图14所示，该算法在10个小时内将104块表全部抄回，即组网成功。其逻辑拓扑结构如图15所示，其中方框中括号外和括号内的数字分别表示电表的物理地址和网络地址。由实验可见该算法具有较强的路由组网能力。

Figure 14 Statistic chart of meter reading图14 抄表统计图

Figure 15 Logic topology structure after network organizing图15 组网后逻辑拓扑结构

实验2 日抄读测试。在成功组网之后，每日的抄读情况如图16和图17所示。由图可以看出，在0：00～0：59的时间段内能抄到大多数的表，说明组网后的路由很稳定；剩下的表也能在5小时内抄回，抄表成功率为100%。实验说明该算法具有很强的路由维护能力，能够进行网络重构。

Figure 16 Chart of daily meter reading图16 日抄表情况图

Figure 17 Chart of daily meter reading（continued）图17 日抄表情况图（续）

5 结束语

本文针对工程实践中载波网络节点仅具有中继转发功能的路由方法进行研究，提出了一种基于图论生成树的路由方法。该方法采用遍历搜索算法中的广度优先搜索算法，能够简单、可靠地实现低压电力线载波的通信组网。以改进的广度优先遍历搜索算法作为路由重构策略，能够有效增强网络的抗毁性，快速实现网络的重构。由于该方法在组网过程中需要一层一层轮询每一个未组网的节点，故存在组网比较耗时的缺点，对于组网实时性要求不是很高的集中抄表系统，以耗时来换取可靠性的办法还是适用的。

本文提出的方法相比于类蚁群算法来说，类蚁群算法需要考虑节点信息素的挥发等，组网搜索和工程实现相对比较复杂，而本方法实现过程比较简单，具有更强的可靠性和稳定性；相比于分簇算法，对网络节点的要求比较低，仅需要支持中继转发功能即可，而分簇算法需要网络节点具有一定的路由组网能力，网络节点成本相对较高。

针对本方法路由组网耗时缺点，可以考虑结合其他算法的思想进行改进；本文没有在路径优化方面做工作，可以考虑对于路由表采用基于传输矩阵或其他方法进行路径优化。这些问题的改善还需要进一步地研究。

［1］ Zhen Xiang－yu，Yang Qing－qing，Zhou Xiao－fang，et al.A－nalysis and modeling of the indoor low voltage power－line channel noise［J］.Journal of Circuits and Systems，2011，16（4）：58－62.（in Chinese）

［2］ Yang Xiao－xian，Zheng Tao，Zhang Bao－hui.Measurement and research of the characteristics of noise distribution in three－phase four－wire low－voltage power network channels［J］.IEEE Transactions on Power Delivery，2007，22（1）：122－128.

［3］ Cortes J A，Diez L，Canete F J，et al.Analysis of the indoor broadband power－line noise scenario［J］.IEEE Transactions on Electromagnetic Compatibility，2010，52（4）：849－858.

［4］ Ling Cheng，Ferreira H C.Time－diversity permutation coding scheme for narrow－band power－line channels［C］∥Proc of 2012 16th IEEE International Symposium on Power Line Communications and Its Applications（ISPLC），2012：120－125.

［5］ Liu Xiao－sheng，Zhou Yan，Qi Jia－jin.Method study of automatic routing for power line communication［J］.Proceedings of the Chinese Society for Electrical Engineering，2006，26（21）：76－81.（in Chinese）

［6］ Qi Jia－jin，Liu Xiao－sheng，Xu Dian－guo，et al.Simulation study on cluster－based routing algorithm and reconstruction method of power line communication over lower－voltage distribution［J］.Proceedings of the Chinese Society for Electrical Engineering，2008，28（4）：65－71.（in Chinese）

［7］ Qi Jia－jin，Liu Xiao－sheng，Wu Di，et al.Study on power line communication routing method for low－voltage distribution［J］.Chinese Journal of Electron Devices，2008，31（3）：1033－1038.（in Chinese）

［8］ Ran Qing－hua，Wu Yu－cheng，Qi Mei－juan.Research on automatic routing method of low－voltage power line carrier network［J］.Power System Protection and Control，2011，39（10）：53－58.（in Chinese）

［9］ Huo Feng－cai，Ren Wei－jian，Han Bo.An improved ant colony algorithm and its application in power route optimization［J］.Science Technology and Engineering，2009，9（21）：6371－6373.（in Chinese）

［10］ Hong Li.Research on medium access control and cluster routing protocols in low voltage power line carrier network［D］.Qingdao：China University of Petroleum，2010.（in Chinese）［11］ Qi Jia－jin.Research on dynamic routing methods for power line communication over lower voltage distributions［D］.Harbin：Harbin Institute of Technology，2009.（in Chinese）［12］ Dong Ya－bo，Gao Feng.Analysis of structure of carrier communication network for low voltage power［J］.Power System Technology，2003，27（2）：58－62.（in Chinese）

［13］ Rosen K H.Discrete mathematics and its applications［M］.Beijing：China Machine Press，2011.（in Chinese）

附中文参考文献：

［1］ 甄翔宇，杨庆庆，周晓方，等.室内低压电力线信道噪声分析与建模［J］.电路与系统学报，2011，16（4）：58－62.

［5］ 刘晓胜，周岩，戚佳金.电力线载波通信的自动路由方法研究［J］.中国电机工程学报，2006，26（21）：76－81.

［6］ 戚佳金，刘晓胜，徐殿国，等.低压电力线通信分簇路由算法及网络重构［J］.中国电机工程学报，2008，28（4）：65－71.

［7］ 戚佳金，刘晓胜，吴迪，等.低压电力线载波通信网络组网方法研究［J］.电子器件，2008，31（3）：1033－1038.

［8］ 冉庆华，吴玉成，祁美娟.低压电力线载波通信网络自动组网方法研究［J］.电力系统保护与控制，2011，39（10）：53－58.

［9］ 霍凤财，任伟建，韩博.改进蚁群算法及在电力线路优化问题中的应用［J］.科学技术与工程，2009，9（21）：6371－6373.

［10］ 洪利.低压电力载波网络介质访问控制与分簇路由协议研究［D］.青岛：中国石油大学（华东），2010.

［11］ 戚佳金.低压配电网电力线载波通信动态组网方法研究［D］.哈尔滨：哈尔滨工业大学，2009.

［12］ 董亚波，高锋.低压电力线载波通信网络结构分析［J］.电网技术，2003，27（2）：58－62.

［13］ Rosen K H.离散数学及其应用［M］.北京：机械工业出版社，2011.