电力线通信PLC（Power Line Communication），又称电力线载波通信，是指利用电力线，通过载波方式将模拟或数字信号进行传输的技术，是电力系统特有的通信方式。通常所说的电力线载波通信多指窄带电力线通信技术，即指带宽限定在3kHz~500kHz、通信速率小于1Mb/s的电力线载波通信技术。目前电力线载波通信研究多集中在信道特性分析、估测、编/解码、功率控制和频谱管理等领域。虽然有部分对电力线载波自动抄表系统路由技术进行了探讨，但开展有关电力线通信路由算法的研究还不够深入广泛。

    1 典型的PLCAMR体系

    典型的PLCAMR体系由三级系统构成：主站、集中器和电能表终端。主站负责管理全局的集中器与电能表信息，可通过光纤、GPRS、公话网或其他方式与集中器通信；集中器一般每个配电台区安装一个，管理所在台区的全部电能表，其日常工作是通过电力线通信采集各电能表数据；电能表负责计量用电户的各类用电量。

    当前的集中器虽然不同程度地具备了自学习路由知识和自组网络的能力，但还不能基于纯零知识开始工作。只有在了解了要管辖的电能表编号及其计量项目后才能工作，这就要求电力营销部门理清配电台区的用电户档案，尤其是电能表编号，通过主站将这些资料下发到台区集中器，才能启动自动抄表。同样，在抄表系统运行过程中，当台区内发生更换电能表、新增用电户或者台区之间发生线路切换等业务时，必须及时正确地维护集中器中的用户资料。由于电力公司通常是按照面向人工抄表的习惯划分组织用户资料（例如按街道顺序组织），理清配电台区与用电户的关系往往需要耗费很大的人力。所以经常因为台区集中器装入了错误的表号而导致费时费力的现场排查工作，尤其对于用电历史长的老城区，理清电能表与台区的关系极其困难，成为普及自动抄表技术的关键瓶颈。

    解决上述问题的本质在于系统能够从零知识开始工作。所谓零知识是指初始时主站只知道有哪些配电台区和集中器，但是并不清楚哪些电能表属于哪个台区的集中器；集中器仅知道自己的编号（ID），但不知道有哪些，有多少电能表隶属自己；电能表仅知道自己的编号（还有自己的计量项目），但不知管辖自己的集中器是谁。但目前国家电网关于自动抄表的通信协议都是主从结构的，电能表作为通信节点只有被动应答的能力，不能主动发起通信任务[1-4].为了适应主从体系结构，本文设计了专门的电能表捕获算法。该算法的优点在于不需要额外的空间资源，线性时间，倘若台区内有n个电能表，算法可在O（n）次报文跳转时间内完成搜索任务。

    2 表号捕获算法

    假设电能表编号的区间为[a,b]（实际应用中a=0,b=1012,或者说是6 B的BCD码）。表号捕获算法的思想比较简单，有2点：

    （1）对于给定的表号区间I=[a,b],利用报文冲突判断出3种情况：在区间I中恰有1只电能表；在区间I中无电能表；在区间I中存在多只电能表。

    （2）利用二分搜索技术快速缩减查找空间。

    以下分4个子节描述基于上述思想的表号捕获算法。为了简明本文略去实现细节。在以后的叙述中，集中器和电能表统称为节点。

    2.1 判定给定区间的邻居分布情况

    首先定义一种查询报文Q={IDsource,a,b}.其中IDsource为报文源节点（发出者）的编号，IDmin≤a≤b≤IDmax.报文Q向编号在区间[a,b]内的节点发出查询请求，凡是编号在此区间的节点（即编号IDme满足a≤IDme≤b的节点）收到该报文后立即回应一个报文R={IDme,r},报出自己的编号IDme和自己的属性r.

    定义了以上2种报文，节点IDsource判定给定区间[a,b]的邻居情况的方法是依靠区别冲突信号与背景噪音的能力。这种能力是指当有多个节点同时发送报文时，接收节点虽然由于报文冲突不能正确地收到任何一个报文，但不会和无报文（线路上只有背景噪音）混为一谈，接收者能够根据冲突信号与背景噪音的特征差异判断出有多个报文同时到达并造成了冲突。正如当多人同时讲话时，可能听不清楚任何一个人说的内容，但能够断定有多人在讲话。如果PLC的物理层能够将冲突信号与背景噪音区分出来，则一个节点IDsource就可以发送报文Q={IDsource,a,b},然后利用载波侦听判定其周围节点的编号。在给定编号区间[a,b]内的3种分布情况为：

    （1）正确完整地侦听到一个报文R={IDme,r}:说明存在编号为IDme的节点，且是的一个编号在a和b之间的节点。

    （2）未能正确地侦听到任何一个报文，并且线路只有背景噪音：说明没有节点其编号在a和b之间；

    （3）未能正确地侦听到任何一个报文，但是存在冲突信号：说明存在多个节点，其编号在a和b之间。

    然而，目前的PLC技术还不能提供区分冲突信号与背景噪音的能力，从而分辨不清情况（2）、（3）。目前的低成本技术仅能做到接收到报文或者接收不到报文。在未收到报文时，区分不出是情况（2）还是情况（3）。对于低成本的载波芯片，实现这一功能目前还是一项极具挑战性的任务。在此，本文给出一个方法可绕过这一难题。该方法利用报文冲突实现这一功能，在收不到报文时，利用报文冲突进一步区分出是的确没有报文，还是由于多个节点同时发送报文造成了冲突。采用该方法需要付出额外的代价是：多报文应答过程；源节点需要事先知道一个确实存在的节点IDknown;需要定义一种新型的报文S={IDsource,IDknown,a,b}.

    S型报文比Q型报文多了一个已知节点的编号IDknown,该报文的功能是令编号为IDknown的节点或编号处于a、b之间的节点收到该S报文后立即回应R型报文，报出自己的编号和属性。区分上述3种情况的算法如下：

    算法1 WhoIn（a,b）：

    算法说明：该算法的输入是两个非负整数 a、b,使得[a,b]形成节点ID区间； 设运行该算法的节点的ID为IDsource,节点IDsource已知其一个邻居节点IDknown,算法要求IDknown不属于区间[a,b];该算法判定节点IDsource有一个、还是没有、还是有多个邻居其ID属于区间[a,b];对应这三种情况，算法分别邻居的ID、或者ZERO、或者MANY.

    send out a packet Q={IDsource,a,b}

    wait for a packet R

    if a packet R={IDme,r} arrived

    then return IDme    //*IDme is the unique neighbor

    in[a,b]*/

    else if a=b

    then return ZERO

    else send out a packet S={IDsource,IDknown,a,b}

    wait for a packet R

    if a packet R={IDme,r} arrived

    then return ZERO  //*Dme must be IDknown

    and whose packet has not been

    collided*//

    else if no packet received

    then return MANY //*IDme must have been interfered with some neighbors

    in[a,b]*//

    end if

    end if

    显然，该算法坏情况下也能在4次报文跳转的时间内作出正确判断。

    2.2 搜索编号的邻居节点

    使用普通的二分搜索技术，节点IDsource在表号区间[a,b]上重复地调用算法WhoIn,可以快速地搜索出编号的邻居节点（若存在）。算法可递归描述如下：

    算法2 MinID（a,b）：

    算法说明：该算法的输入及要求同算法WhoIn（a,b）；如果区间[a,b]有邻居节点，算法返回其中的ID,否则返回ZERO.

    let result=WhoIn（a,b）

    if result is a valid ID or result=ZERO

    then return result

    let result=MinID（a,[（a+b）/2]）

    if result is a valid ID

    then return result

    else return MinID（[（a+b）/2],b）

    该算法log（b-a）次调用算法WhoIn,其总的时间复杂度不大于4log（b-a）次报文跳。

    2.3 搜索全部邻居节点编号

    有了MinID算法，节点IDsource通过在表号区间[a,b]重复地搜索的未知表号，直至获得ZERO值。算法如下：

    算法3  IDsIn（a,b）：

    result=MinID（a,b）

    while result≠ZERO do

    report result

    result=MinID（result+1,b）

    end while

    该算法多每4log（b-a）跳时间搜索到一个节点。若节点IDsource在区间[a,b]上有n个邻居节点，节点IDsource在4nlog（b-a）跳时间内可完成捕获这n只电能表的任务。

    2.4 集中器捕获全部电能表节点

    假设一个台区内存在n个电能表节点，由集中器节点直接运行算法IDsIn（0,248），可在 4nlog（248-0）≤192n跳时间内搜索到全部一跳（直抄）电能表节点。然后由集中器通知一跳表，二跳表，……运行同一算法，并将发现的节点编号上报集中器，于是集中器可以继续搜索到二跳表，三跳表，……全部过程进行完多用192n2跳时间。

    为了简单易读，上述的2.1~2.4节中只是在思路层叙述算法设计，忽略了很多重要的实现细节。

    时间界192n2在2.4节中估计得很粗略。将一些精细的实现细节纳入考虑后，该时间界可下降。例如在任何节点执行该算法时，如果其他节点记录侦听到的节点，则时间可降至192n跳。

    在青岛东软公司的一个实验台区运行本文所述算法，捕获全部的620只电能表需要1.5 h.算法实现细节上可以进一步优化，使捕获效率更高。