基于生成树的低压电力线载波的STTDA算法*

索 剑，罗中良

(惠州学院计算机科学系，广东 惠州 516007)

近年来，基于扩频通信技术、OFDM 调制技术[1-3]，通过电力线载波PLC(Power Line Carrier)在低压电网环境中实现自动抄表已逐渐得到大量应用，PLC技术也被认为是“最后300 m”互联网接入的理想解决方案之一[4]。

网络拓扑标明了每一个智能电表在网络中的位置，同时映射终极用户；动态获取低压电网的网络拓扑在电表、电路故障诊断方面具有现实意义。

网络拓扑的获取对于信道传输质量有较高的依赖，此前的讨论大多基于中压PLC环境下。近几年随着低压PLC的应用拓展，文献对网络拓扑发现的探讨也逐渐增多，蚁群算法等启发式算法被引入此领域应用[5-8]。

本文基于生成树提出了一种低压PLC网络拓扑发现算法，给出了判定各类关系节点的规则，通过生成树的规则实现了网络拓扑的发现。

1 低压电力线载波通信模型

1.1 通信网路架构及特性

根据低压配电网二次布线和低压电力线通信结构可以把低压配电网络抽象为星形和树形混合拓扑模型[9-10]。不失一般性，可将其抽象为如图1所示，由主站、集中器和终端三层结构组成的基本架构。目前，通过载波电路已可有效地对抗频率选择性衰落[11]，因此可以通过统计的方法来计算分析低压电网通信信号的衰减特性[12]，以均值获取用以表示节点间距离的可比较的相对衰减量。集中器和终端通过载波电路沿通信线路发送广播信息，收到广播后的节点会返回地址以及本节点距离广播节点的衰减数据。

图1 PLC基本架构

在实际部署中，很多情况是若干电表放置在一个表箱里的，同一表箱的电表之间衰减远小于表箱内的电表与该表箱外的电表之间的衰减，不失一般性，可认为表箱内电表之间的衰减为0；表箱虽不能收发数据，但可依据表箱中的电表来确定。

1.2 问题描述

一个低压PLC子网就是一个多结点的多叉树，节点之间均可进行广播。图2为抽象后的模型树，其中A0为根节点亦即集中器，An(n<>0)为智能电表亦即树的节点，两节点之间的衰减量可用于描述节点间的距离，D0为包含若干终端的表箱。

图2 模型树

2 网络拓扑发现原理与算法设计

由图2可知，拓扑树实际是一个连通图G=(A，M)[13]，A为节点集合，M为边集合，节点之间通过M值来确定相互位置，以此构成整个网络。

2.1 相关定义与定理

为了便于描述拓扑发现的过程，作如下定义：

定义1 节点间的距离：设As、Ad∈G(A)，则Msd为As节点到Ad节点的距离。

定义2 最大允许距离：设Mmax为G中两节点可以通信的最大值，即能够稳定传输数据所需的最大距离值。因此若Msd<=Mmax，则As、Ad两节点可以通信；反之则不能通信。

在G中的任何节点As(s=0，1，2，……，n)均可发出广播信息，通过边连接的所有满足Msd≤Mmax的其它节点均可接受该信息，这样就形成了一个节点集合Ca，Ca中的节点接收到广播信息后，向As返回地址以及对应的距离值。

2.2 节点间判定规则

分析线路中各节点的距离，节点之间的关系存在如下判定规则：

规则1：父子节点判定规则。如图3(a)所示，若Ax发送广播信息，Ao、Ap、Aq为满足条件并返回数据的节点，距离最短的节点则为Ax的儿子；反之，则不能确定是Ax的儿子。若有几个节点距离信息源节点相等且均为最小，可判定这几个节点均是Ax的儿子。

规则2：兄弟节点判定规则。如图3(b)所示，若Ax发送广播信息，Ao、Ap、Aq为满足条件并返回数据的节点，其中Mxo

规则3：表箱内电表判定规则。如图3(c)所示，设Ax发送广播信息，Ao、Ap、Aq为满足条件并返回数据的节点，Ao、Ap根据规则1可确定为Ax的儿子即Mxo=Mxp；若再次对Ao做广播，存在Mop=0，则可判定Ao、Ap在同一表箱。

图3 拓扑发现判定规则

2.3 STTDA算法设计

算法的基本思想是从根节点开始确定一对父子关系，通过分析其他节点与这对父子节点的距离，得到一个节点，它要么是父亲的儿子，要么是儿子的后代；对于新确定的父子关系进行递归搜索，直到不再搜索出新的节点为止，每一个父子关系最终都得到确定。作如下数据结构定义：

T：为目标树集合，其结构为(parent，child，attenuation，box)其中parent为父亲节点，child为儿子节点，attenuation为两个节点间距离，box为表箱标志；

S：为构造集合，其结构为(parent，child，attenuation)，属性含义同上；

A：为候选节点，即准备广播的节点，是每一次递归被最新确定出来的儿子；

Data：为候选节点A广播后，满足条件的数据返回集合，其结构为(parent，child，attenuation)，含义同S集合；

L：为一组父子节点关系，其结构为(Ax，Ay，Mxy)，其中Ax为父亲节点，Ay为儿子节点，两节点间距离为Mxy。

从根节点A0开始发出广播命令Broadcasting(A0)，则获得一个节点集合C0，C0中任意一个距离最短的节点Ak被认为是A0的儿子，即为候选节点，并将该节点以及与A0的距离记录在目标树集合T中，所有C0中其他节点以及与A0的距离值被记录在构造集合S中；从Ak再次发出广播命令Broadcasting(Ak)，则可获得节点集合C1，将C1集合的所有节点以及和Ak的距离值也添加进S中；从S集合中，可以分析出哪些节点距离Ak和A0更近一些，删除距离远的父子关系，在S中找到距离最近的节点关系，节点关系取决于某一节点Ak+1(即新的候选节点)与目标树中A0和Ak之间的距离值，亦即Ak+1是A0或Ak的儿子，将此节点以及和目标树中节点的距离记录在目标树中；这样每次都可求出一个父子关系，并以子节点再次广播，依次递归，可求出所有节点的父子关系。

2.4 STTDA算法实现

根据上述拓扑发现思想，定义如下方法：

PutIntoS(Data)：将返回的数据集合送入在构造集合S中；

PutIntoT(L，Dxy)：从S集合中将父子关系L复制到T集合中。若Mxy=0，则Ax、Ay在同一表箱，记录同一表箱的标志Dxy；否则为空；

Delete(L，Q)：从Q集合中删除L父子关系；

Broadcasting(A)：A节点发送广播信息的命令；

GetData(A)：A节点发送广播信息的命令后，得到相应的各节点返回数据Data集合；

GetMinRelationship(Q)：Q为父子关系集合，此命令返回在Q集合中最短距离的一组父子关系，若有多个相等最小距离，则随机取一组；

GetChild(L)：在一组父子关系中取出儿子节点；

GetParent(L)：在一组父子关系中取出父亲节点；

GetAttenuation(L)：在一组父子关系中取出距离值；

拓扑发现算法实现如下：

PutIntoT(Φ，A0，0)/*将根节点A0送入在目标树中*/

A=A0/*将候选节点设为A0*/

Do

Broadcasting(A)/*A节点发出广播信息*/

Data=GetData(A)/*得到数据返回集合*/

PutIntoS(Data)/*将返回的数据集合送入在构造集合S中*/

For everyLinS/*在S集合中若存在同一表箱的电表，则读入T集合中*/

If GetAttenuation(L)=0 then

PutIntoT(L，D)

Delete(L，S)

For everyLinS/*在S集合中若存在某一记录L，该子节点已经在T集合中出现，则删除L*/

If GetChild(L)inTDelete(L，S)

For everyLinS/*在S集合中若存在某一记录L1，其父亲节点和L不同，但儿子节点相同，而距离值小于L，则删除L*/

If Exist GetParent (L1)<> GetParent (L) and GetChild(L1)= GetChild(L) and GetAttenuation(L1)< GetAttenuation(L) then Delete(L，S)

L=GetMinRelationship(S) /*在构造表S中求出最短距离关系*/

PutIntoT(L)/*将最短距离关系送入在目标树中*/

Delete(L，S)

A=GetChild(L)/*取得下一个候选节点*/

UntilS=Φ

PrintT/*输出目标树*/

3 实验与结果分析

根据上述思想，设计模拟系统进行N个节点网络拓扑发现的实验。设有节点逻辑如图4所示。

图4 逻辑节点图

图4中，An为节点标志，连接线上的数据表示衰减，若设衰减40为可搜索的最大衰减度，则A0可广播搜索的范围如图5(a)所示；进行4次搜索后，A1、A6、A12和A2节点被搜索出来，如图5(b)所示；图5(c)所示为相应的搜索过程，高亮的部分A2表示刚找出的节点，它是由A1搜索到的。

以此类推，发现所有节点。在此作如下假设：载波频率40 k，9 600波特率发送，则发送一个字节约需1 ms，若一个消息包24字节，应答消息包8个字节，一个应答过程则需32 ms；在真实情况下，载波传输很受到很多干扰因素的影响，应答电表需要一段时间才能发出应答信号，同时为了保证传输质量往往需要3-4次发送才能完成准确传输，因此可设一次可靠的完整传输需要200 ms。

图5 搜索过程及结果

由于在搜索前无法确定到底有多少节点，也无法确定哪些节点是叶子节点，理论上只有遍历树中的每一个节点，才能确定整体结构；从根自顶向下的搜索时，对于每一个候选节点，不对已知所有父辈进行广播并接收数据，可有效提高效率。表1为依次搜索出的节点及相应广播得到的节点个数。

表1 节点及搜索个数

可求得在理想状况下，该网络所有广播次数为13，反馈的节点次数46，从而可以得到这个网络拓扑理论发现的时间为46*200 ms,多次实验后总衰减量、节点个数和反馈次数之间的关系如图6(a)(b)所示。

图6 实验结果

由图6(a)和(b)可以看出，节点个数D和总衰减量Msum虽然不易确定和反馈次数Sum之间的函数关系，但随着节点个数D和总衰减量Msum的增加反馈次数Sum呈近似线性增加状态。

实际部署中，电表多位于表箱中，对于同一个表箱内的若干电表来说，仅一次广播就可以确定相互的关系，表箱内的其它电表只记录无需再发出广播信息，这样就可大大减少反馈次数。

4 结 语

由于智能电表电网需要多次广播才能得到节点间的关系，本文没有采取多叉树深度或广度优先遍历的算法，而是根据电网的延展以生成树来进行节点的逐步发现。智能电表低压电网拓扑发现的意义不仅能够实时的了解网络结构，而且能够通过已知的网络有效地确定故障电表和故障线路，同时在已知拓扑结构的情况下，更高效的数据传输也成为可能。在未来智能家电、智能楼宇不断的发展中，载波电路可植入不同的受控设备中，其网络拓扑发现思想类同。

参考文献：

[1] 张平泽，赵振勇. 基于低压电力线载波通信方法的比较[J]. 电子设计工程，2010，2(2):26-28.

[2] 张广驰, 江艳敏, 秦家银. OFDM系统中基于有限反馈的余量自适应比特加载[J].中山大学学报：自然科学版，2009，48(5)：39-42.

[3] 李峰,苏爱国,吴茂初，等.自适应频域判决-反馈迫零均衡的 OFDM系统[J].中山大学学报：自然科学版，2008，47(4)：38-41.

[4] SILVA J M，WHITNEY B. Evaluation of the potential for powerline carrier to interfere with use of the nationwide differential GPS network[J]. IEEE Trans Power Delivery，2002，4(17):348-352.

[5] 罗中良,易明珠,刘小勇.最优化问题的蚁群混合差分进化算法研究[J].中山大学学报：自然科学版，2008，47(3)：33-36.

[6] 杨佳,许强,张金荣，等. 一种新的量子蚁群优化算法[J].中山大学学报：自然科学版，2009，48(3)：34-37.

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

[8] 高柏臣，高俊英，潘政刚，等. 基于动态自适应路由技术的低压PLC 集抄系统[J].电力系统通信，2009.10:23-27.

[9] GEORGE Jee, CON Edison. Demonstration of the technical viability of PLC systems on medium-and low-voltage lines in the United States [J].IEEE Communications,2003(5):108-112.

[10] HALID Hrasnica, ABDELFATTEH Haidine,RALF Lehnert.宽带电力线通信网络设计[M]. 宋健,赵丙镇,李晓,译.北京：人民邮电出版社, 2008.

[11] 樊建学，盛新富.低压电力线载波通信技术的研究[J].电测与仪表，2005(2)：36-38.

[12] 谢飞，熊立翔, 杨士中.低压电力网载波通信信号衰减特性的研究[J].电子技术应用,1998(1):36-37.

[13] 陈松，王珊，周明天.一种新的物理网络拓扑发现算法[J] .电子与信息学报，2010，1(1)：172-176.