基于有序树的电力线网络路由算法

何华冰　 姚婷婷　李云飞　贾俊铖

(苏州大学计算机科学与技术学院　江苏 苏州 215006)



基于有序树的电力线网络路由算法

何华冰 姚婷婷李云飞贾俊铖

(苏州大学计算机科学与技术学院江苏 苏州 215006)

摘要电力线通信(PLC)依靠现有的分布广泛的电力线路设施进行数据传输不需要额外布线开销，越来越受到人们的关注。但是，目前电力线网络路由效率不高，通信延迟较大。为解决以上问题，根据电力线网络的树型拓扑结构的特点，提出一种树路由算法(PLC-TR)。算法将电力线网络组织成一棵有序树，并通过地址比较进行路由选择，最大限度降低了因路由维护产生的网络开销。通过仿真表明，和传统上性能优异的最短路径算法(SPR)相比，在同等干扰情况下，PLC-TR具有较低的数据包平均传输时延和较高的数据包交付率。

关键词电力线网络有序树PLC-TR树路由算法最短路径算法

0引言

近年来，有关电力线载波通信技术的应用研究格外引人关注[1]，比如高速的宽带PLC上网、智能家居[2]、大型自动化系统[3]以及电力系统的远程抄表等。作为数据传输的一种方式，电力载波通信利用供电线路进行传输数据，不需要额外布线是其主要的应用优势。但是，配电网络电气负载环境复杂，强衰减，高噪声不利于信号的传输。比如，电力信道上负载的动态加入或离开网络导致输入阻抗不匹配引起较强的信号衰减。有色背景噪声、工频信号噪声和开关电源引起的脉冲噪声都严重影响了信号的传输质量。因此依靠物理层和数据链路层有限的点对点通信是难以实现的，其需要网络层的支持，如中继转发和路由选择等，来提高电力线通信的可靠性。

目前，应用于电力线路由方面的算法很少且其中大部分算法来源于无线网络[4-8]。国内外很多学者在无线移动自组网方面的研究较多，路由算法一般基于位置或基于拓扑。在信号的传播方式上，无线方式是以发送节点为中心向四周传播，而电力线上，信号只能沿着通信线缆进行传播，即使通信源宿节点在物理上很近也不一定能直接进行通信。因此，基于位置的路由算法不能很好地适用于有线网络。在应用于电力线网络的算法中，基于拓扑的最短路径算法SPR(Shortest Path Routing)[9]由Dijkstra算法将网络构造成一颗最小生成树。源宿节点间具有最短路由，在传统的路由算法中往往是表现最佳的一个，但是SPR需要定期与邻居节点交换路由信息。由Dijkstra算法计算最短路径，这无疑增加了网路开销，而且在节点数目较大时，这种开销将不容忽视。

Zigbee树路由算法[10-12]是一种分层的路由算法，其通过规定网络的最大层数和每个路由节点允许连接的最大节点数来限定网络。在本网络中，路由节点通过自身地址和网络层数及目的地址进行计算来选择下一跳路由，不需要定期与邻居节点交换路由信息。在很大程度上避免了多转发节点产生的数据碰撞，在理论上具有较高的数据包交付率和较低的通信时延。为减少网络中的信息交换提供了新的思路。

电力线网络在物理上是树型或星型结构，电力线上的设备绝大多数情况下都是静态的，因此，将电力线网络在逻辑上组织成树型结构[13-15]，在路由选择上具有一定优越性。Zigbee树路由算法应用于电力线网络中，将面临以下问题：其一，网络的最大深度与线路的最大长度和单跳有效通信距离有关，线路越长或单跳有效距离越短,需要的路由深度越大，反之越小。电力线信道具有较强的干扰，而且具有时变性，固定的路由深度难以适应时变的信道。其二，电力线网络中节点不一定均匀分布，有可能大量的节点集中在某个分支，导致节点稀疏区地址富裕，而在密集区地址不够分配。

本文主要在Zigbee树路由算法的基础上做出改进如下：其一，算法取消了路由层数，每个路由节点都将获得一个地址域，其最大值为本路由节点的地址，其最小值为以此节点为根节点的子树中最小的地址。其二，算法需要探索整个网络，根据节点分布密度分配地址域。称这种树为有序树，改进后的算法为基于有序树的电力线网络路由算法(PLC-TR)。

1电力线网络模型

电力线网络中将存在三种节点：网关节点、路由节点和普通节点。其中，网关节点为整个网络的中心，是与外网通信的枢纽节点；路由节点除了具有普通节点的功能外主要负责路由选择和选择转发节点和维护下级节点；普通节点和路由节点为基本的通信节点。

1.1电力线网络模型及相关定义

如图1所示，我们将电力线网络表示成图G={N,E}。

图1　电力线网络模型

其中N={n1,n2,…,nj,…,nM},ni表示第i单个节点，M表示网络中节点的个数，E表示节点间的边集，在初始状态下为空。我们定义一个和节点连通的节点集，表示为：Ni= {nj|Eij>Emin;j= 0,1,2,…,M}。其中nj表示第j个节点，Eij表示ni和nj两个节点之间传送信号的能量值，Emin表示保障正常通信的最小能量值。

1.2相关定义

1.2.1有序树

如果一棵树满足，任意两个以节点ni和nj为头结点的独立子树(其中一棵树不是另一棵树的一部分)，i ≠ j，ni子树中有一个节点的值大于nj子树其中一个节点的值，那么ni子树中的任一节点的值都将大于nj子树中的所有节点的值。那么，这棵树是一棵有序树。

1.2.2分支权重

如果节点ni为路由节点，则节点ni的分支权重Wi是以节点ni为头结点的分支树上所有路由节点的个数总和。在图 2中，节点ni为头结点的分支树上有ni， nk为路由节点，Wi=2，同样的Wk=1。

1.2.3能量值

是指信号的接收节点所接收到数据信号的能量大小。节点使用相同的能量发送数据信号，信号在电力线上传输过程中逐渐衰减，因此节点间的距离越远接收到信号的能量值越小，反之越大。可以使用能量值来表示点对点的最大有效距离。能量值E可以表示为：

(1)

其中δ表示一个常数，其意义为能量计算模块的等效阻值，t1和t2表示接收数据帧的起始和结束时间，f(t) 表示帧中数据幅值随时间的变化曲线。

能量值的计算也可以依靠功率谱密度经验式(2)进行计算。功率谱密度经验公式如下：

μ(f,D)=(0.0034D+1.0893)f+0.1295D+17.3481

(2)

其中，f表示低压电力线频率,单位KHz，D表示距离，单位为m。

为了降低路由维护开销，提高点对点通信效率，在如图1所示的网络模型中，我们将以网关节点为头结点构造一棵有序树，这棵树必须满足两个条件：(1)具有最短的平均路径长度，利于降低通信时延，提高包递率。(2)有序，便于路由选择。在下文中，拓扑探索过程将使得这棵树满足第一个条件，地址分配策略使其满足第二个条件。

2有序树构建策略

2.1拓扑探索和路由节点选取策略

在路由节点选取策略中用能量值表征两节点间的距离来代替传统算法中使用跳数来表示的距离，使得本算法更能适应时变的电力线网络。本文使用树的广度优先搜索算法探索未知拓扑的电力线网络，算法优先将能量值小的节点分配为候选路由节点。如果此节点可以探索到未加入网络的节点，则其成为路由节点，否则成为普通节点，以便探测更远的距离。在拓扑探索过程中，节点间使用载波监听多点接入碰撞避免(CSMA/CA)算法[16]来提高节点数据链路层的通信质量。拓扑探索前状态如图2所示。

图2　拓扑探索前状态

能量值确定和候选路由节点选取过程如下：

第一步节点ni广播发送拓扑探索帧进行探索网络，假如某节点收到探索帧并且没有加入网络，则节点nk计算探索帧的能量值Eik(见式(1))。并和正常通信所要求的最小能量值Emin进行比较，Eik>Emin则以nk节点自身的MAC地址和能量值Eik回复节点ni。如果节点ni收到其他节点的回复，则通知其父节点将其分配为路由节点。如图3所示，假如有节点nkj、nn、nk回复了节点ni，则ni将节点nj、nn、nk按能量值EijEin、Eik从小到大排列并加入ni的子节点集Ni。

图3　拓扑探索后状态

第二步节点ni使用树的广度优先搜索策略，优先选择节点集Ni中能量值最小，即距离节点ni最远的节点nk为候选路由节点。nk重复第一步中节点ni的过程。如果没有收到任何未加入网络的节点的回复，则被分配为普通节点。

第三步在子节点集Ni中选择能量值次小的节点重复第二步的过程直到节点集Ni中所有的节点都被选为候选路由节点并且执行了搜索过程。

在算法执行完成之后，图3中的节点ni搜索到了节点nj、nn、nk，节点nk搜索到节点nm、np,则ni和nk成为路由节点并分别获得节点集Ni={ni，nn，nk}和Nk={nm，np}。其他节点因没有搜索到任何未加入网络的节点成为了普通节点。探索完成后的网络如图3所示将电力线网络在逻辑上构造成树型拓扑。

证明：以网关节点为头结点的这棵拓扑树具有最短的平均路径长度。如果可以证明，对于网络中的任一节点ni(0

假设以最远距离选出的转发序列为P1，转发节点数为x1，并且假设存在一个转发序列P2，其每一次并不一定选择相距最远的节点作为转发节点，经过的转发节点数为x2，x2m，则在dmax范围内节点nin包含更远的可选下一跳节点。因此每一跳P1序列都比P2序列更接近目的节点T，所以P2序列的转发节点个数不可能小于P1，x2

2.2地址域分配策略

算法主要是路由节点根据其子节点表中路由节点的个数和对应的权重，将其获得的地址域划分为多个连续的的地址段并将这些地址段分配给相应的子节点。且这些地址段在个数上等于子路由节点的个数，大小上和对应的子路由节点权重成正比使得以网关节点为头结点的整个电力线网络是一棵有序树。

假设：某路由节点ns获得的地址域为[A1,AN],ns的子节点集Ns中的路由节点的个数为K，路由节点集为R={ns+1，ns+2，…，ns+k}，对应的分支权重集为W={Ws+1，Ws+2，…，Ws+k}。节点ns地址预留百分比为p，其中0

1) 节点ns获得地址域中值最小的地址作为自身网络地址。即节点ns获得的地址为A1，所有ns节点集中的非路由节点共享ns的网络地址。

(3)

(4)

考虑到电力线信道的特性，虽然有线网络中的节点是静态的，但是随着信道的波动，节点故障或人为因素的影响，任何节点在某一时刻都有可能加入或离开网络。为了保证节点能够快速入网和网络连通性，首先使普通节点共享父节点网络地址，任何节都作为普通节点加入网络。由于普通节点只是通信终端不进行路由过程，其加入或离开都不影响网络连通性。所以共享地址方式更简单，更快速。

在地址分配过程中每个路由节点都保留了一定比例的预留空间，为新的路由节点加入保留地址。

3有序树路由策略

3.1节点网络地址和MAC地址对应关系维护

节点间为了能够通信，源节点需要知道目的节点的网络地址，在网络拓扑发生变化时，同一个节点的网络地址可能发生变化。而节点的MAC地址是节点的硬件地址，不会随网络拓扑的变化而变化，在具体应用中，MAC 地址通常和应用相关。从网络地址的分配策略可知：网关节点一定是网络地址为零的节点且固定不变。因此任何节点都知道网关节点的网络地址可以和网关节点通信。和IP网络类似，本文使用网关节点提供地址解析服务，即任何节点都可通过目的节点MAC地址向网关节点请求目的节点的网络地址。为了使网关节点包含整个网络的最新地址对应关系，网络中的节点行为规定如下：

1) 网关节点要维护一张网络中所有节点MAC地址和网络地址对应关系的解析表。

2) 节点新加入网络，发送自身的网络地址和MAC地址对应关系到网关节点。

3) 网关节点收到地址解析请求，如果解析表没有对应的网络地址则通过广播方式请求目的节点网络地址。为了减少网络中的通信数据量，和无线网络中的源驱动路由(AODV)相似，网关节点在收到地址解析请求且无对应地址表项时，才广播获取对应的网络地址，更新地址表项。

3.2有序树路由策略

经过上文阐述的基于分支权重的地址分配方法之后，整个电力线网络构成一棵有序树。任何子路由节点地址域是其父路由节点地址域的细化，任何父节点的地址域都是其子节点的泛化。因此，路由选择过程就是细化过程和泛化过程的组合。

树型网络的数据帧按传输方向可以分为由父节点到子节点的下行帧(细化过程)和由子节点到父节点的上行帧(泛化过程)。任意两个节点进行通信存在图4所示三种通信模型即上行通信(b)，下行通信(a)，先上行再下行的通信(c)。

图4　树型网络通讯模型

路由策略描述：路由节点收到的数据帧有可能是父节点发送的下行帧或子节点发送的上行帧。对于下行帧，如果目的节点网络地址在路由节点地址域内，则进行转发，否则不转发；对于上行帧，如果目的节点网络地址在路由节点的地址域内，则将数据帧类型转为下行帧，然后转发，否则不转发。如果目的节点网络地址与路由节点地址相同，则根据目的节点的MAC地址一跳内到达目的节点 。路由算法的伪代码表示如下所示：

树路由算法(PLC-TR)

功能:路由节点通过比较目的网络地址与自身地址域,进行数据转发。参数:D_ADDR目的节点的网络地址D_MAC目的节点的物理地址ns_MAC路由节点物理地址Amins路由节点地址段最小值Amaxs路由节点地址段最小值START 收到数据帧F IF(D_ADDR=Amins)数据帧F一跳之内可达目的节点IF(D_MAC=ns_MAC)路由节点为目的节点ELSE:通过D_MAC直接发送数据帧F到目的节点ENDIF ELSEIF(D_ADDR>AminsANDD_ADDR

如图4(c)所示源节点S发送数据到目的节点D，由前文地址分配策略可知，父节点的地址域包含所有子节点的地址域，兄弟节点之间地址域不相交。所以，节点的地址域不包含D地址域，在n1的路由表中找不到任何转发节点可到达节点D，数据帧继续上行。在节点n2处，由于节点n2是节点D的父节点，其地址域包含节点D的地址域，所以在n2的路由算法中可以找到到达节点D的转发节点。上行帧在节点n2处转为下行帧。

在路由过程中，算法执行两次比较用以确定目的网络地址是否在转发节点的地址域内，再根据数据帧的上下行属性即可选择是否转发。因此，算法时间复杂度为O(1)，算法的空间复杂度为O(n)，n的值与其子节点的个数正相关。

4仿真和仿真结果分析

为了验证PLC-TR算法的性能，本文在NS2环境下对其进行仿真。由于实际情况下电力线网络存在时变的干扰，源节点发送的节点可能因干扰问题不能正确到达转发节点或目的节点。为了模拟此种情况，我们建立双状态马尔科夫模型。定义电力线网络模型中的任意节点ns都有无法接收数据包Serror的状态和正常收发数据包的Srun状态，线路影响因子为p(0

为测试PLC-TR和SPR在不同节点数量和线路影响因子下，网络的平均路由跳数、数据包分组的平均传输时延和交付率。仿真模型如图1所示，模拟电力线总长度为6 km，初始节点个数为19个沿电力线均匀分布，其中节点0为网关节点，节点间的有效传播距离为200 m，数据发送速率为20 kb/s，每个数据包大小为64 byte，类型为CBR数据包。实验首先将1至18号节点随机分配为9对源、目的节点。在节点个数增加到40、80、120、160、200、240时分别以PLC-TR和SPR构建网络，并使9对源，目的节点进行300秒数据传输。仿真数据统计结果如图5、图6所示。仿真结果显示，相比于SPR，PLC-TR平均路由跳数较少了4.3%，在p=0.02和p=0.2下，平均端到端时延分别降低了29.7%和41.4%。PLC-TR在数据包交付率和吞吐量上也有了明显提高。

图5　平均路由跳数和节点数量关系　图6　平均端到端时延和节点数量关系

从图5中可以看出平均路由跳数(源节点与目的节点间经过的路由节点的个数)PLC-TR算法明在节点增加的过程中平均路由跳数相对稳定，在节点个数达到120以前明显高于SPR算法。SPR算法中的所有节点都有可能在其他源宿节点的最短路径上，由于信道干扰，每个节点的失联都有可能导致失去多条最短路径，使得平均路由跳数逐渐上升。PLC-TR路由节点的选取是根据能量值进行的，增加节点的数量只能增加普通节点的数量而对路由的深度影响较小，在节点数增加的过程中平均路由跳数相对稳定。

从图6中可以看出平均端到端通信时延(包括发送时延、传播时延、处理时延)随着节点密度的增加而逐渐增高，在p=0.02和p=0.2两种干扰程度下PLC-TR也明显低于SPR。由于干扰的原因，SPR算法平均路由跳数高于PLC-TR，需要更多的转发次数，加大了数据包发生碰撞的概率。除此之外，SPR还有因维护最短路径的网络开销，进一步使得数据包在网络中碰撞重传次数加大。随着节点数的增加，这种开销快速上升，使得端到端的通信时延越来越大。由于PLC-TR成功地减少了这种维护开销，因此在端到端通信时延方面大幅降低。也由于同样的原因，在数据包交付率和吞吐量方面PLC-TR也有了较大提高，如图7、图8所示。

图7　数据包交付率和节点数量关系　　　图8　网络吞吐量与节点数量关系

5结语

本文提出的电力线组网算法PLC-TR充分利用了电力线网络拓扑结构进行网络组建和路由选择在一定程度上解决了电力线网络路由效率不高的问题，在很大程度上降低了网络开销。通过仿真实验表明，PLC-TR在线路质量变化的过程中依然能够在端到端时延，数据包交付率等方面表现出较好的性能。

参考文献

[1] Slootweg H.Smart Grids - the future or fantasy?[C]// Smart Metering-making It Happen,Iet.IET,2009:1 - 19.

[2] Lin Y,Latchman H A,Lee M,et al.A power line communication network infrastructure for the smart home [J].Wrl Ommnaon, 2002,9:104 -111.

[3] Bumiller G,Lampe L,Hrasnica H.Power line communication networks for large-scale control and automation systems [J].Ommnaon Magazn,2010,48(4):106 - 113.

[4] Li H,Kensheng W,Li H,et al.Cluster Based Dynamic Routing on Powerline Carrier Network[C]//Wireless Communications,Networking and Mobile Computing,2009.WiCom’09.5th International Conference on.IEEE,2009:1 - 4.

[5] Biagi M,Greco S,Lampe L.Neighborhood-knowledge based geo-routing in PLC[C]//Power Line Communications and Its Applications,IEEE International Symposium on.IEEE,2012:7-12.

[6] Yoon S,Jang S,Kim Y,et al.Opportunistic Routing for Smart Grid With Power Line Communication Access Networks[J].Mar Grd Ranaon on,2014,5(1):303 - 311.

[7] Biagi M,Lampe L.Location Assisted Routing Techniques for Power Line Communication in Smart Grids[C]// Smart Grid Communications,First IEEE International Conference on.IEEE,2010:274-278.

[8] Sanchez J A,Ruiz P M,Marin-Perez R.Beacon-less geographic routing made practical:challenges,design guidelines,and protocols [J].Ommnaon Magazn,2009,47(8):85 - 91.

[9] Galli S,Scaglione A,Wang Z.For the Grid and Through the Grid:The Role of Power Line Communications in the Smart Grid[J].Rodng of H,2011,99:998 - 1027.

[10] Kim T,Kim S H,Yang J,et al.Neighbor Table Based Shortcut Tree Routing in ZigBee Wireless Networks[J].Aralll and Drbd Ym Ranaon on,2014,25(3):706 - 716.

[11] Kim T,Kim D,Park N,et al.Shortcut Tree Routing in ZigBee Networks[C]//Wireless Pervasive Computing,Iswpc 07,International Symposium on.IEEE,2007.

[12] Ren Z,Tian L,Cao J,et al.An efficient hybrid routing algorithm for ZigBee networks[C]// Instrumentation and Measurement,Sensor Network and Automation,International Symposium on.IEEE,2012:415 - 418.

[13] Delestre C,Ndo G,Labeau F.A binary tree network topology for statistical and physical PLC channel modeling[C]//Power Line Communications and Its Applications (ISPLC),2013 17th IEEE International Symposium on.IEEE,2013:327 - 332.

[14] Tripathi S,Dwivedi J K,Shukla M.Power Line Communication with Tree Based Interleaver in Iterative IDMA Systems[C]// Computational Intelligence and Communication Networks,International Conference on.IEEE,2013:286 - 290.

[15] Mirabella O,Raucea A.Tree based routing in power line communication networks[C]//Iecon-annual Conference on IEEE Industrial Electronics Society.IEEE,2010:1398 - 1403.

[16] Pinero-Escuer P J,Malgosa-Sanahuja J,Manzanares-Lopez P,et al.Homeplug-AV CSMA/CA Evaluation in a Real In-Building Scenario [J].Communications Letters,IEEE,2011,(6):683-685.

ORDERED TREE-BASED ROUTING ALGORITHM FOR POWER LINE COMMUNICATION NETWORK

He HuabingYao Tingting Li Yunfei Jia Juncheng

(SchoolofComputerScienceandTechnology,SoochowUniversity,Suzhou215006,Jiangsu,China)

AbstractPower line communication (PLC) is getting more and more attentions because it transmits data only relying on existing widespread power line facilities without additional wiring cost.However,current power line network still has the problems of low routing efficiency and high communication delay.To overcome these problems,we propose a tree routing algorithm,short for PLC-TR,according to the characteristics of tree topology of power line network.Specifically,PLC-TR first organises the power line networks into an ordered tree,and then selects the routes by comparing their addresses,this minimises the network overhead caused by routing maintenance.It is shown through simulation that compared with the shortest path routing (SPR) which is traditionally one of the optimal algorithms,under the same disturbance the PLC-TR has lower average packet transmission delay and higher packet delivery rate.

KeywordsPower line networkOrdered treePLC-TRTree routing algorithmSPR

收稿日期：2014-12-01。国家自然科学基金(61272449,61201212)。何华冰，硕士生，主研领域：无线传感器网络，嵌入式系统，电力线通信技术。姚婷婷，硕士生。李云飞。教授。贾俊铖，副教授。

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.029