基于邻节点覆盖的电力线通信组网路由算法

尹 萍，徐东明

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

0 引 言

低压电力线载波通信(low voltage power line communication，LVPLC)技术作为电力行业特有的通信技术，在智能配电领域有着广阔的应用前景，比如高速的窄带PLC上网、电力系统的智能抄表以及智能家居等[1]。作为数据传输的一种方式，电力线载波通信利用遍布城乡的供电线路进行数据传输，主要的优势是无需额外布线。然而，电力线设计的初衷是用来传输电能而非数据通信，当以电力线作为通信介质时，传输信道存在的强干扰噪声和较大的信号衰减都不利于信号传输，这些特有的信道状况使得通信的可靠性降低。为提升电力线通信的可靠性，当前的研究主要从两方面入手，即增强物理层的通信能力和建立网络中继[2]。有关物理层的研究主要从信道特性、信号调制与解调等方面入手，而网络中继则主要体现在网络拓扑中继的研究[3]。如文献[4]提出了基于非交叠分簇算法的电力线通信组网和重构算法，该算法能适应信道质量的实时变化进行自动组网，逻辑通信链路破坏时有一定的自愈能力；文献[5]提出的基于受限洪泛和分级的LPLC组网算法，可有效提升通信稳定性和通信效率。本文将融合非交叠分簇算法层次分明和洪泛算法的可靠性高的特点，提出一种基于邻节点覆盖的分簇洪泛路由组网算法，该算法首先采用覆盖优先策略为相邻节点分配不同的转发优先权，筛选出可能成为簇头的节点，然后为避免盲目洪泛出现的消息内爆和冗余现象，采用簇节点的转发抑制策略和动态延时转发机制，在有效降低信道的冲突碰撞的同时确立正式簇头，达到组网的目的，研究表明该算法可提升电力线通信系统的可靠性。

1 电力线通信组网算法基础

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

低压配电网拓扑结构因应用场所的不同而复杂多变，常见多用的拓扑主要有树形拓扑、星型拓扑、环形拓扑。在楼宇中低压配电网的结构主要是基于树形的混合拓扑结构，其电力通信系统可分为两部分：监控室内的主机和电网内的若干终端。低压配电网分为三相供电且对于电力线载波通信而言不能跨相通信，三相之间在逻辑拓扑上是并列且相互独立的，取其中一相拓扑进行研究就具有代表性[6]。为方便论述，本文以一相为基础，将此相电网上的主机称为网关，载波通信模块称为节点。图1为低压电力线通信网络逻辑拓扑，总网关下设网关A、B、C分别代表配电网中的一相，单相网关下由若干终端组成。由于低压电力线的载波通信特点，终端侧负载节点的临时加入或退出，使得电力线上信号的数据传输更加不稳定，造成节点之间往往在物理链路上连通而在数据链路上处于断开状态。如图2所示，节点0与1号链路的断裂，造成以3为中继的节点4、7、9退出通信。为了保障网络的完整通信，从网关节点到部分终端节点的数据传递需要借助部分节点充当中介(中继节点)才可有效扩展链路的通信距离，所有节点才有可能连入电力线通信网络。所以，中继技术在实现大规模的电力线通信中是必不可少[7]。

图1 低压电力线通信网络拓扑

图2 节点退出通信

1.2 非交叠分簇算法

分簇算法是从逻辑上将载波网络划分为“簇”状结构，由“簇头”和“簇员”构成完整一簇[8]。通过规定簇成员是否属于同一簇，分为交叠分簇和非交叠分簇。基于电力线载波网络的树状结构，采用非交叠分簇算法分簇过程为：如图3所示，由网关节点0向网络洪泛消息，收到消息的一跳通信范围内的节点1、2、3在回复网关节点后成为一级节点，一级节点依次按照节点编号顺序替代网关角色依次向网络洪泛消息探测网络的二级节点，依次类推，直到网络中所有节点被发现[9]。

图3 非交叠分簇算法分簇

2 基于邻节点覆盖的组网算法原理

2.1 网络节点角色定义

电力线载波网络簇的建立是由中心节点向外发送消息开始的，网络中接收到消息的簇节点给予相应的反应，其角色(发送状态/接收状态)的动态变化使得在不同时刻簇节点扮演的角色不同[10]。为了方便描述算法形成过程，将有关节点定义如下：

中心节点(网关)：电力线载波网络与外网的中转节点，起到网关的作用，通过网关可以管理电力线载波网络。

邻节点：在当前发送节点的有效通信范围内的一跳邻节点，构成当前节点的准簇成员。

准簇头节点：可能成为簇头的节点，一般某簇头一跳通信范围内某分枝上具有最大覆盖域的节点可能成为准簇头节点。

正式簇头节点：分簇过程中被选择为簇头负责转发数据信息的节点。

2.2 相邻覆盖优先策略

簇节点覆盖域是指在当前发送节点(网关节点/转发节点)洪泛入簇消息时，收到入簇消息的邻居节点组成的集合，这些节点成为某级准簇头节点。相邻覆盖优先是指发送节点指定收到消息的节点的优先转发权，而优先转发权由当前节点的覆盖域大小决定。覆盖新区域越大，转发优先权就越高[11]。因此，相邻覆盖优先的关键在于相邻覆盖域的确立和转发优先权的计算。

2.2.1 簇节点相邻覆盖域

通过发送节点的物理ID来确定本节点的邻居节点的覆盖状态，因此每个簇节点都会存有本地路由表和邻居信息表，邻居信息表内存储了邻居节点的位置信息，发送节点的物理ID在洪泛入簇消息数据包中获知。假设所有节点有效通信距离为R，任意节点i位置坐标为(xi,yi)，物理ID记为i。借助图4，簇节点的相邻覆盖域确立过程如下：

网关节点M洪泛入簇消息，收到消息的节点构成以M为簇头的一级邻节点集合U={T、K、X、Y、L}。 依据洪泛算法扩散的方向性，距离簇头M最远的节点K覆盖新域最大，具有优先转发数据包的权利。节点K依据来自M洪泛数据包中的ID，先与自身的ID对比，如果一致，则在规定时间内回复簇头确立自身角色，如果不一致，则替代簇头M的角色转发该数据包。直到在有效时间内找到目的终端为止。当前转发节点可依据邻居表查询得到节点M的位置坐标(xm,ym)。从图4可知，M节点作为K节点的邻居，节点K的邻节点中部分节点与M邻节点重叠，重叠的节点即为M的邻节点与K的邻节点的交集。即位于K邻节点中的任意节点j若满足下列条件

则称K的邻节点j处于相邻覆盖状态。

图4 相邻覆盖优先数据转发

2.2.2 簇节点转发优权与中继节点

当筛选出位于相邻覆盖域内的簇节点之后，发送节点的邻节点就被分为两类，即处于覆盖域之内与覆盖域之外的。位于相邻覆盖状态的节点构成的集合记为U1={T、K、X}，U1集合中的簇节点将优先确立自身是否能成为一级簇头节点。非相邻覆盖状态的节点构成集合U2={A、E、W}，U2集合中的节点构成以当前转发节点K为准簇头的一级准簇成员。如图4所示，由于洪泛算法扩散的方向性，处于U2中的簇节点要比位于U1中的簇节点的覆盖新域的能力要强,且在U2中，A节点比节点E的覆盖新域要大。所以，距离K节点最远的A节点具有优先转发权。所以，节点转发优先权的确立需要依据簇节点所在的集合及距离当前发送节点的距离来决定。当簇节点位于集合U1/U2时，转发优先权Qi计算如下

2.3 簇节点的动态延时机制

相邻覆盖优先策略使得洪泛消息快速覆盖网络的同时，对准簇头节点给予了有效筛选，避免了冗余数据包的传递。在成簇算法过程中，未经限制的洪泛数据包往往会发生信息碰撞，增加消息的重传机率。为了尽可能避免消息的碰撞引入基于节点优先转发权的动态延时机制，即结合节点的转发优先权给节点分配不同的转发时延。动态延时的分配首先需要判断当前节点是否具有转发权。同时规定成为中继的节点不在具有转发权。对于具有转发权的节点，假设节点i收到来自节点n的洪泛入簇消息，则按照下式进行数据包延时转发：若首次收到数据包，转发时延为

(1)

否则

Tdelay(i) =max{Tc-delay(i),Tm-delay×Qi}

(2)

其中，Tm-delay是转发数据包时的最大延时，Tc-delay是当前转发节点收到数据包时的剩余延时时间。当节点第一次收到需要转发的数据包时，需要等待的延时时间如式(1)所示，第一次收到数据包的节点是集中在相邻覆盖域之外的节点中，相邻覆盖域之内的节点会出现多次数据包的接收转发，此时则需要按照式(2)，在本次最大延时和当前剩余延时中选取最大值，以保证有足够的时间进行准簇头的筛选。

2.4 算法步骤描述

相邻覆盖域、优先转发权和动态延时机制是本文算法的核心，成簇算法的具体步骤如下：

步骤1 网关节点洪泛入簇消息，确定其邻节点，计算邻节点的相邻覆盖域，选取优先权最小的邻节点作为转发节点，转发节点洪泛入簇消息。

步骤2 当前转发节点依据相邻覆盖优先原则和簇节点动态延时标准，依次转发洪泛包，确定自身的准簇成员，同时筛除不能成为簇头的节点。

步骤3 成为准簇成员的节点回复网关确立当前转发节点为正式簇头。若在一定的时间内未收到准簇成员的回复，则发送节点降级为网关的簇成员。

步骤4 当前转发簇节点自身角色确立及准簇成员确立完毕，一级簇头剩余节点替代网关节点的角色进行洪泛入簇广播，处理方式同上。

步骤5 依次类推，直到所有节点都收到过数据包，确立了角色，则分簇组网完成。

步骤6 组网完成后，在网络运行过程中如果发现链路出现断裂的少数节点，通过洪泛分簇算法为其重新寻找路由。

成簇算法实现的流程如图5所示。

图5 成簇算法流程

3 算法仿真及结果分析

为了验证算法的有效性，利用Matlab对文中算法进行了仿真。在100m*100m的区域，40个节点随机分布，无孤立节点。假设节点0为网关节点，位于区域正中间。剩余39个节点代表载波节点，编号为1，……39。为了模拟电力线载波通信逻辑结构的时变性和随机性，假设载波节点间有效通信距离在20m～25m内随机变化。分别对非交叠分簇算法和改进分簇算法进行仿真，结果分别如图6～图8 所示。

图6 非交叠分簇算法仿真

图7 改进分簇算法仿真

图8 传输延时随传输半径的变化

图6显示，采用非交叠分簇算法和改进分簇算法进行组网时，组网结构有明显差异。图6组网结构层次分明，节点之间路径唯一，簇头数目达到20个。图7节点之间路径有所增加，如图中0→8的路径除原有的路径0→7→32→8之外，增加了一条新路径0→7→23→8。簇头总数为14。这是由于在簇节点角色确定过程中，不满足条件的节点成为相邻节点之间的中继。降低了簇头的数量，增加了簇间的路径，从而改善了簇间路径的唯一性，避免了簇间路径失效时网络的频繁重构。

图8是采用非交叠分簇算法和改进分簇算法进行组网时，节点端到端传输延时随传输半径变化的仿真结果。如图8所示，当传输半径从20 m均匀增加到50 m时，两种算法的传输延时均呈下降状态。相比之下，本文算法的传输延时优于非交叠分簇算法，这是由于传统算法在成簇过程中并未对洪泛的范围及数据包的转发有所限定，而本文算法在成簇过程中对节点采取了优先覆盖和动态延时机制，有效避免了消息洪泛的盲目性，降低冗余数据包的产生从而避免了信道冲突。使得端到端传输延时得以有效降低。

4 结束语

本文提出了一种基于邻居节点覆盖的分簇路由组网算法，该算法通过利用相邻覆盖优先策略为相邻节点分配不同的转发优先权，先筛选出可能成为簇头的节点，为提高数据传输效率及避免消息的冗余，结合节点的转发优先权引入了基于簇节点的数据转发抑制策略和动态延时转发机制，在有效降低信道的冲突碰撞的同时确立正式簇头，达到组网的目的。仿真结果表明，该算法可以有效降低节点端对端传输延时，减少簇头，建立多条通信路径，进而提升系统的可靠性。此算法为低压电力线载波通信组网提供了一种可参考的方法。

[1]XIE Zhiyuan,WU Xiaoyan,HU Zhengwei,et al.10 kV powerline communication automatic relay algorithm research and application[J].Electric Power in China,2012,45(11):82-85(in Chinese).[谢志远,吴晓燕,胡正伟,等.10 kV电力线通信自动中继算法研究与应用[J].中国电力,2012,45(11):82-85.]

[2]LIU Xiaosheng,LI Yanxiang,WANG Juan,et al.Low vol-tage powerline clustering web mixed multipath routing algorithm and the communication protocol design[J].Journal of Elect-rical Engineering Technology,2015,30(s1):337-345(in Chinese).[刘晓胜,李延祥,王娟,等.低压电力线分簇蛛网混合多径盲路由算法及通信协议设计[J].电工技术学报,2015,30(s1):337-345.]

[3]Huang C,Ning Y.Study on cluster-based dynamic routing algorithm in power line communication network[C]//IEEE International Conference on Automation and Logistics.IEEE,2012:461-465.

[4]WANG Zhenchao,WANG Yijin,WANG Jing.A kind of sui-table for Ad hoc network of overlapping clustering routing algorithm[J].Computer Engineering and Application,2012,48(7):88-91(in Chinese).[王振朝,王伊瑾,王静.一种适用于Ad hoc网络的交叠分簇路由算法[J].计算机工程与应用,2012,48(7):88-91.]

[5]Liu X S,Li Y X,Wang J,et al.Multipath blind routing algorithm for low-voltage power line communication based on improved clustering[C]//Fourth International Conference on Instrumentation and Measurement,Computer,Communication and Control.IEEE,2014:578-583.

[6]BAO Weidong.Based on the limited and flooding the network algorithm[J].Power Line Carrier-Current Communication Power of Information and Communication Technology,2014,12(3):41-44(in Chinese).[鲍卫东.基于受限和洪泛的电力线载波通信组网算法[J].电力信息与通信技术,2014,12(3):41-44.]

[7]Liu X S,Li Y X,Wang J,et al.Multipath blind routing algorithm for low-voltage power line communication based on improved clustering[C]//Fourth International Conference on Instrumentation and Measurement,Computer,Communication and Control.IEEE,2014:578-583.

[8]Xie Z Y,Wu X Y,Liu J N,et al.Study on automatic routing algorithm for medium voltage powerline communication[C]//International Conference on Systems and Informatics.IEEE,2012:1577-1580.

[9]LIN Jingdong,QIN Yulong,LIAO Xiaoyong.Electric power carrier communication research dynamic network algorithm[J].Journal of Control Engineering,2013,20(5):841-843(in Chinese).[林景栋,秦玉龙,廖孝勇.电力载波通信动态组网算法的研究[J].控制工程,2013,20(5):841-843.]

[10]HONG Li.Low voltage power carrier network media access control and clustering routing protocol research[D].Qingdao:China University of Petroleum (East China),2010:71-84(in Chinese).[洪利.低压电力载波网络介质访问控制与分簇路由协议研究[D].青岛:中国石油大学(华东),2010:71-84.]

[11]LI Fangmin,LIU Xinhua,KUANG Hailan.An energy efficient wireless sensor network low latency flooding algorithm study[J].Journal of Communications,2007,28(8):46-53(in Chinese).[李方敏,刘新华,旷海兰.无线传感器网络中一种高能效低延时的泛洪算法研究[J].通信学报,2007,28(8):46-53.]

[12]ZHAO Tao,LI Jianqi,WANG Zhihui,et al.A clustering routing algorithm based on flooding probability and statistics in the application of low voltage power carrier network research[C]//Power Communication Management and Smart Grid Communication Technology BBS,2013(in Chinese).[赵涛,李建岐,王智慧,等.一种基于洪泛概率统计的分簇路由算法在低压电力载波组网中的应用研究[C]//电力通信管理暨智能电网通信技术论坛,2013.]