基于电力线载波通信技术的自动抄表系统路由算法

高新贺，刘 萌，徐 广，王 锐

(中国海洋大学 计算机科学系，山东 青岛266100)

电力线通信 PLC(Power Line Communication)，又称电力线载波通信，是指利用电力线，通过载波方式将模拟或数字信号进行传输的技术，是电力系统特有的通信方式。通常所说的电力线载波通信多指窄带电力线通信技术，即指带宽限定在 3 kHz～500 kHz、通信速率小于1 Mb/s的电力线载波通信技术[1]。

目前电力线载波通信研究多集中在信道特性分析、估测、编/解码、功率控制和频谱管理等领域。虽然有部分文献[1-4]对电力线载波自动抄表系统路由技术进行了探讨，但开展有关电力线通信路由算法的研究还不够深入广泛。

本文着重介绍自动抄表系统中用于实现监控电表和例行抄读业务的路由算法——点名请求算法和数据收集算法。

1 电力线通信自动抄表系统

基于电力线通信技术的自动抄表系统是一个3级系统，由主站、集中器以及电能表组成，物理拓扑结构如图1所示。

主站是一个管理系统，每个电力公司设置一个主站系统统辖管理所有的集中器和电能表。每个配电台区（一台配电变压器供电的区域）中安装一只集中器，用于管理所在台区的用户电能表。集中器与主站之间通过公共网络（GPRS、PSTN、GSM等）通信。电力线通信限于配电台区内。集中器和电能表都具备电力线通信能力，它们之间通过220 V电力线交换数据，从而互连成一个通信网络。

在自动抄表领域，两个基本的功能需求是点名请求和数据收集。点名请求一般由人工从主站发起，指定监控某只电能表，例如读取电能表数据、状态，或者发送通/断电指令。数据收集是定期抄读全部电能表某一时刻的数据，用于每月的计费收费或者每日的线损计算考核。本文针对这两个最常用功能，介绍相关的路由算法。

由于电力线最初的设计是以传输电能为目的，与专门进行数据传输的双绞线、同轴电缆以及光纤等介质相比，具有自己的特点。当前电力线通信技术的发展状态和特点概述如下：

(1)低速率。为了应对电力线上固有的强噪声，电力线通信速率一般不太高，窄带电力线通信的有效速率通常都低于 1 kb/s。

(2)短距离。电力线对于载波信号衰减较高，直接通信距离通常是数百米甚至数十米。环境恶劣时，两节点之间的报文传递甚至需要10多个中间节点的中继转发。

(3)半双工。受成本所限，各节点的通信芯片上的接收和发送不能同时工作。当一个节点在发送报文时，它就不能侦听、接收报文，反之亦然。实际上，在任何时间，通信节点处于且仅处于以下4种状态之一：

①发送态：正在发送某个报文；

②侦听态：试图捕获其他节点发出的报文；

③接收态：正在接收某个报文；

④处理态：忙于节点内部的处理，例如报文的解析或组织、电能计量等。

(4)同频点。各节点工作在同一个通信频点，节点发送报文的本质方式是广播，发送的报文可以同时被多个节点接收。这意味着如果多个不同的报文同时到达同一个节点，这些报文会在该节点处发生冲突，该节点识别不出任何一个报文，甚至不能够判断出网络上有多少个节点在发送报文，因为通信节点不能够区别背景噪音与报文冲突的差异。

(5)时变性。由于随机干扰、用电器关停启动、环境温度变化、阻抗变化等原因，电力线通信具有不确定性，网络的通信拓扑结构不是恒定的。

(6)非对称。因为噪音分布的不均匀性、元器件的离散性，两节点之间通信往往具有不对称性。可能节点u能够正确地接收到节点v发送的报文，但是节点v接收不到节点u发送的报文。

当前基于电力线通信技术的自动抄表系统的重要特点是零知识初态。系统初始时，各电能表节点仅知道自己的通信编号(ID)，不知道除了自己之外还存在多少个通信节点，更不知道能够与哪些节点直接通信。集中器除了知道自己的编号，还知道台区内它所统辖的所有电能表节点及其编号，但对于拓扑结构等路由信息完全不知。

2 网络模型及问题描述

2.1 网络模型

本文将给出2个面向点名请求问题的路由算法和3个面向数据收集问题的路由算法。假设电力线通信是对称的，这样一个配电台区内组成的电力线通信网络可以抽象为简单无向图 G=(V，E)。 其中，V={v0，v1，v2，…，vn}为全部通信节点的集合，包括集中器节点v0和n个电能表节点 v1，v2，…，vn；E=V2为 G 的边集合，如果边(u，v)∈E，则表示节点u与v可以互相直接通信。否则，u与v之间的通信报文必须通过其他一个或多个节点中继转发。

两个节点 u、v之间的距离（跳数）是图 G中 u、v之间最短路径 u=u0u1…uk=v的长度 k，记为 d(u，v)。如果两节点之间的距离为k，其中一个节点发出的报文至少需要经过k次跳转才能到达另一个节点。

如果d(v0，u)=k，即节点 u距离集中器节点 v0为 k跳，则称节点u为k跳节点。在此定义下，集中器节点v0是0跳节点，能够与集中器直接通信的节点称为1跳节点。

2.2 问题描述

在上述模型下，自动抄表系统的2个基本功能需求的路由问题可以叙述为：

(1)点名请求：集中器节点v0有一个发往电能表节点u的请求报文Q，节点u收到Q后将回应报文R发送给节点v0，要求给出传送此类报文的算法和协议。

(2)数据收集：集中器节点 v0发出请求，要求所有电能表节点向v0发送各自的回应报文，给出执行此功能的算法和协议。

本文主要从时间效率和能量损耗两方面考察算法的性能。由于电力线通信的速率低，报文旅程的时间主要耗费在报文跳转的过程中，途经各节点的本地处理时间可以忽略不计，以所需报文的跳数衡量其时间复杂性。当节点静默时几乎不耗电，能量主要耗费在发送报文的过程中，所以以各节点报文发送次数之和衡量能量耗费。

由于电力线通信的时变性和不确定性，评估算法的平均或最坏时间、能量耗费需要引入合理的概率模型和复杂的概率分析。为了简便，本文只估测算法能够达到的最好情况。

3 点名请求算法

集中器节点v0向一个k跳的电能表节点发出请求报文，请求报文至少需要k次跳转才能到达u。同样，u的回应报文也至少需要k次跳转才能到达v0。于是给出点名请求问题的时间和能量下界。

定理1如果v0点名请求u，则任何正确完成该请求的算法所需的时间和能量皆不小于2d(v0，u)。

以下分别给出2个算法：第一个是单路径路由SPR（Single-Path Routing）算法，第二个是全路径路由APR（All-Path Routing）算法。

3.1 单路径算法SPR

在单路径算法SPR下，如果集中器节点v0点名请求电能表节点 u，v0首先决定一条到达 u的路径v0=w0w1…wk=u，然后附加请求指令q形成单路径点名请求报文Q={w0w1…wk，q}。v0在发出Q之后的2k跳时间内等待由 u发送回来的回应报文R（如果超时，可断定执行失败）。

单路径点名请求报文Q由集中器节点v0发出后，将按照v0规定的路径依次经过中继节点w1…wk-1，直到目的节点u。电能表节点u的回应报文R将沿Q的来路返回。

Q在旅途中已经跳过的路径被删除，若路途中被转发的 Q={w0w1…wk，q}，则其中的 w0w1…wk只是含当前跳(w0，w1)的剩余路径。

电能表节点执行如下算法：

(1)电能表节点收到单路径点名请求报文Q={w0w1…wk，q}：

①如果 myID=w1、k＞1（本节点是中继节点）：记录节点 w0和 w2，删除路径中的节点 w0，发出报文 Q={w1w2…wk，q}，设置2k跳的计时器，进入计时等待状态；

②如果 myID=w1、k=1(本节点是目的节点)：记录节点 w0，交应用程序处理 Q，将响应结果 r组成回应报文R={myID，myID，w0，r}，其中头部的 3个节点标识分别表示R的源节点、当前发送节点、当前接收节点；

③否则忽略。

(2)电能表节点在计时等待状态的算法如下：

①如果超时事件发生：退出等待状态；

②如果收到回应报文R={ID0，ID1，ID2，r}， 并 且myID=ID2、w2=ID1：修改 R={ID0，myID，w0，r}，发送该报文。

SPR算法的主要优点在于简单直接。如果集中器能够确定出有效的最短路径，可以在时间和能量上与理论下界匹配，但实际上这一点却往往不能保证。

算法SPR存在的问题是：强烈依赖路由知识，算法要求集中器节点掌握全局的路由信息，需要靠专门的智能学习算法探索路径或者在日常工作过程中总结积累；其结果是系统初始时性能低下，需要较长一段时间的运行才能趋于稳定；不能应对时变性，路由知识获取和使用不在同一时间，在时变性高的环境下，过时的路由知识反而浪费时间；成功率低，当集中器节点决定沿一条长度为k的路径访问请求一个电能表节点时，需要报文来回连续成功跳转2k次。由于通信的不确定性，实际上一次跳转成功的概率p＜1。于是点名请求的成功概率为p2k，成功率随着路径的变长急剧下降。

3.2 全路径点名请求算法APR

全路径点名请求算法APR使请求/回应报文在旅行过程中衍生成多路[5]，同时沿着所有可能的路径向目的节点推进。该算法又称为泛洪算法，该算法具有简单易实现、时间最优、成功率高、零知识运行、克服时变性和随机干扰能力强的优点。

如果电力线上多个节点同时发送不同的报文，会导致在这些节点通信范围重叠的区域发生冲突。但是，如果这些节点同时发送同一个报文，电力线上传播的信号会因叠加而加强，其他节点能正确接收这个报文。APR算法正是基于这一论断。试验表明，这一论断至少在FSK扩频通信的方式下是成立的。

在APR算法下实现的点名请求及其回应报文的格式形如{x，y，k，l，p}。 其中的 p 是请求指令或应答结果。x是报文的源节点ID，如果是请求报文，它应该是集中器节点v0，如果是回应报文，它应该是一个电能表节点。y是报文的目的节点ID，如果是请求报文，它应该是一个电能表节点，如果是回应报文，它应该是集中器节点v0。k是报文的可以旅行的距离（跳数）。l是报文的已经旅行的距离（跳数）。

当集中器节点v0点名请求电能表节点u时，v0首先估测u距离它的跳数k，将有关信息和点名请求指令q一起组成全路径点名请求报文 Q={v0，u，k，1，q}发出，然后在2k跳时间内等待以u为源节点的回应报文R(如果超时，可断定执行失败)。

各电能表节点上的APR算法如下：

(1)事件“收到全路径点名请求报文 Q={x，y，k，l，q}”：

①如果 myID≠y、k＞l：将 Q 中 l+1，发出报文 Q={x，y，k，l+1，q}，在 k-l-1 跳时间内屏蔽事件“收到全路径点名请求报文Q”；

②如果 myID=y：记录 x，k，l，将 q交给应用程序处理，取应用程序返回结果r形成回应给节点x的报文R={myID，x，l，1，r}, 等待 k-l跳时间后发出报文 R。

(2)事件“收到全路径点名回应报文 R={x，y，k，l，r}”：

如果 myID≠y、k＞l：将 Q 中 l+1，发出报 文 R={x，y，k，l+1，r},在 k-l-1跳时间内屏蔽事件 “收到全路径点名回应报文R”。

由于多个节点可能同时收到全路径点名请求报文Q={x，y，k，l，q}， 算法实现的关键点在于保证那些满足条件 myID≠y和 k＞l的节点必须在同一时刻转发报文Q={x，y，k，l+1，q}， 以确保这些节点发送到电力线上的的信号是相互叠加而不是相互抵消。同样，对于事件“收到全路径点名回应报文 R={x，y，k，l，r}”的实现，必须使那些满足条件myID≠y和 k＞l的节点在同一时刻发送报文 R={x，y，k，l+1，r}。

算法APR的唯一缺点是高能耗。最坏情况下，网络中的每个电能表节点都要参与两次报文发送（请求和回应各一次），能量消耗达到2n+1。

算法APR的时间复杂性为k+d(v0，u)，如果集中器能够使 k=d(v0，u)，时间复杂性可降至 2d(v0，u)，达到最优，同时能量消耗也得到改善。这一点容易做到，只需要集中器节点增加总结积累和管理各节点跳数的算法即可。

4 数据收集算法

集中器v0发出数据收集请求，网络中的n个电能表节点向集中器发送回应报文。对一个k跳的电能表节点，回应报文至少需要k次跳转才能到达集中器。下面给出数据收集问题的时间和能量下界。

定理2如果v0收集网络中的n个电能表节点的数据，则任何正确完成该数据收集算法所需的时间和能量皆不小于

在本节中首先利用已有的点名请求算法实现数据收集算法，而后提出一个新的数据收集算法：并行路由算法 PRA（Parallel Routing Algorithm）。PRA算法中的报文都是并行传输的，并且使用临时路由信息，可以减少发送报文的数量，缩短抄表时间。

4.1 利用点名请求算法实现数据收集算法

重复n次点名请求算法就可以收集网络中所有电能表的数据，实现数据收集算法。

4.2 并行式路由算法PRA

PRA算法的报文在传输过程中采用存储转发机制。每一个收到报文的节点，首先向发送方回复一个确认，然后将报文保存到当地的一个待发队列中。报文当前所在节点根据报文的目的地和线路状况来决定将报文发送给哪一个节点。没有节点为该类报文确定出全部的路径，下一步跳往哪个节点是由当前转发节点临时决定的。节点转发报文后，等待接收方回复一个确认。只有得到确认后，发送方才能将报文从自己的待发队列中删除，从而解除它对该报文所负的责任。否则，若在规定的时间内没有收到接收方的确认，则需寻机再次转发。

PRA 算法报文的格式形如{x，u，v，y，q，r}，其中的 q是请求指令，而r是节点的应答结果，x是报文的源节点ID，u是报文的当前发送节点 ID，v是报文的当前接收节点ID，y是报文的目的节点 ID，在 PRA算法中y一直是集中器节点v0。

当集中器v0要收集网络中所有电能表节点的某项数据时，v0会发送报文{v0，v0，v0，v0，q}。

各电能表节点上的PRA算法如下：

(1)电能表节点收到报文 P={x，u，v，v0，q，r}：

①如果 myID≠v：记录 preID=u，将 q交给应用程序处理，取返回结果r形成发送到节点u的报文P={myID，myID，u，v0，q，r}。 节点将该报文存放到待发队列尾，并等待发送报文P。电能表节点屏蔽该事件直到算法结束；

②如果 myID=v：向节点 u发送确认，修改 P={x，myID，preID，v0，q，r}，将该报文存放到待发队列尾，并等待发送报文P。

(2)电能表节点发送待发队列头的报文，然后进入计时等待状态。在计时等待状态的算法如下：

①超时发生：重新发送待发队列头报文；

②收到确认：从待发队列头删除报文，发送下一个报文。

当忽略发送确认报文给算法带来的影响，并假设在报文的传输过程中，没有重传现象发生，并且报文按最优路径到达集中器，PRA算法的时间复杂性为1+能量消耗为时间和能量损耗都达到理论下界。但在实际应用中很难达到这种理想状态。

PRA算法的主要优点是：使用临时路由，可以更好地应对电力线网络的时变性，本地的临时路由信息随着报文的传递快速更新，可以更准确地反应网络的拓扑结构；报文可并行传输，并且传输的都是上行回应报文，减少了发送报文的数量，节约了抄表时间；多任务机制，在网络中可以发送不同的报文，因此在同一时间可以执行不同的任务。

本文提出了2种自动抄表系统路由算法，其中点名请求算法能够很好地解决电力线载波抄表系统中对某块表的点名抄读任务，PRA算法能显著减少整个网络发送的报文数量，缩短抄表时间。 由于电力线信道环境的特殊性，使得应用单一的路由算法在抄表过程中表现不理想。对于不同的线路状况和通信要求应采用不同的路由算法来提高抄表成功率，这就给电力线通信路由算法带来了新的问题。目前，电力线通信路由算法的研究中还存在着许多亟待解决的问题，有待于进一步深入研究。

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

[2]赵杰卫，卢文冰，李贤亮.电力线载波自动抄表动态路由技术研究[J].电力系统通信，2007，28(181)：1-5.

[3]丹梅.自动抄表系统帧中继技术及其实现[J].仪表技术，2002，(1)：15-17．

[4]赵建军，侯彦东，张苗辉.基于网络技术的电力载波抄表系统[J].计算技术与自动化，2006，25(2)：52-54．

[5]CHROBAK M，GPIENIECT L，RYTTER W.Fast broadcasting and gossiping in radio networks.Proceedings of the 41st Annual Symposium on Foundations of Computer Science，2000 IEEE：575-581.