窄带PLC 通信网络的树簇路由算法设计

潘 萍

（长沙师范学院电子信息工程系,长沙,410100）

0 引言

电力线载波通信技术目前国内外的研究热点主要集中在通信信道建模，噪声干扰特性，组网技术和阻抗匹配等方面。

由于配电网网络结构多样、负荷情况复杂，使得利用电力线进行高速数据信号传输时信号传输特性非常复杂。本文介绍了采用分簇算法和骨干树路由算法相结合，可以提高骨干树协议对大规模和强干扰网络的适应性，同时，也可以使分簇路由算法协议更加高效。

1 树簇路由算法原理

基于树形骨干网和节点相关度分簇的树簇路由算法主要由四部分组成:簇生成算法、簇维护算法、生成树算法和生成树维护算法。准备加入网络的节点首先运行簇生成算法，簇生成算法完成后，网络节点被划分成多个簇。与此同时簇维护算法开始运行，用于维护簇结构的有效性和处理簇首失效或者簇内结构发生变化的情况。簇生成算法的完成将会触发生成树算法的运行，生成树算法将各个簇连接在一起，生成一个树形骨干网的簇树网络。然后生成树维护算法开始运行，用于维护树形骨干网的有效性和处理树形骨干网结构发生变化时的情况。此时，簇维护算法和生成树维护算法同时运作。

2 树簇路由算法设计

本算法部分包括簇生成算法、树生成算法、簇维护算法和树维护算法四个部分。

2.1 簇生成算法

簇生成算法是根据网络需求按照某种规则将网络划分成可以相互连通并覆盖所有节点的多个簇。在网络初始化阶段,由网络内根节点广播“竞选簇头”的消息,所有接收到此消息的节点将根据接收信号强度、历史抄通概率和网络连通度决定是否参加竞选。节点首先计算信号强度与历史抄通概率的乘积，若该值小于某一阈值,直接放弃竞争,并在接下来的时间段内选择加入某一个簇；若该值大于某一阈值，则节点向网络主节点发送“竞选簇头”的消息。网络主节点接收到消息后,广播“任命簇头”消息。接收到此消息的节点如果发现任命的簇头中有自己,就当选为簇头,然后发送“重新加入簇”消息告知其它节点自己是新簇头。非簇头节点根据与广播簇头的相关度值来选择加入哪个簇, 并发送“请求加入簇”消息告知该簇头。

2.2 树生成算法

树生成算法将各个簇之间以树形拓扑的形式组织在一起，同时将节点间路由提供足够的信息。首先指定根簇簇首地址，这个根簇是发起生成树算法的源头，产生一个且仅一个节点的一级骨干树。未加入骨干树的簇首广播发出请求，收到该请求的已加入骨干树的簇首单播发出回应。请求簇首根据收到的应答选择一个级别最小的簇作为自己的父簇并且广播发出Cluster_Join_Report，并且将自己的级别设为父簇级别+1,Cluster_Join_Repor 中包括了簇内所有节点的信息。收到Cluster_Join_Repor的簇首根据其中的信息判断请求簇是否成为自己的子簇，如果成立则将加入簇的信息向上级簇簇首逐级通告。未加入网络的簇重复步骤，直到所有的簇首都加入到骨干树上。

2.3 簇维护算法

簇维护算法用于维护簇内节点之间链路的有效性以及处理簇内链路失效的情况。当簇生成算法完成后，簇内节点会记录它的所有邻居节点，并为每个已处于簇内的邻居节点设置一个定时器用于维护它们之间的链路，这个定时器由Hello 报文更新。同时，完成簇生成算法的节点仍然周期性的发送Hello 报文，与先前的报文不同的是，此时的Hello 报文中必须加入节点的簇号和簇内身份，以表示节点处与簇状态。当定时器超时后，节点执行相应的措施通告链路的变化。

簇维护算法不是一个顺序执行的算法，而是一个由事件触发的算法，针对不同的事件作出不同的处理。

事件1：担任簇首的邻居节点超时，该节点重新启动簇生成算法。

事件2：担任簇内成员的邻居节点超时，如果本节点是簇首，则簇首启动生成树维护算法，从自己的邻居表中删除该邻居节点的记录，并使用逐级向上通告该簇内成员失效；如果本节点是簇内成员，则仅仅从自己的邻居表中删除该邻居节点的记录。

2.4 树维护算法

树维护算法的主要是维护簇首之间链路的有效性，进而维护和更新整个树形骨干网的逻辑结构。在该算法中，所有的簇之间保持成树形拓扑结构，簇首之间相互发送Tree Hello 的方式用来维持邻居簇首之间的链路，同时为每个邻居簇首设置定时器。当定时器超时后，将会触发节点执行相应的处理。在生成树维护算法中，树形拓扑的维护和更新是以Update 报文携带的信息为依据的。

3 树簇路由策略

在树簇路由中，算法执行完成的节点中掌握了足够的信息可以为节点间的通信提供路由依据。下面从簇间路由和簇内路由两个层次分别说明其中的路由策略。

3.1 簇内路由策略

由于在簇内每个节点都保存所有一跳邻居信息，而簇的直径最多只有两跳，所以对于到达邻居的数据采用直接投递，对于非邻居的簇内节点首先递交给簇首，因为这是簇内相邻成员间最短的路径。一般传到簇外的数据要么经过簇首，或者可以传递给直连网关由网关决定路由。一旦簇首掌握的信息发生更新，一定要通告簇内的所有网关。经过性能仿真与分析，树簇结合的动态路由适合低压窄带载波通信技术条件，满足了其工程实施的需要。

3.2 簇间路由策略

在生成树算法中，我们已经说明了簇首为了将簇之间组织成骨干树形拓扑而需要掌握的簇结构信息。为了正确路由网络中每个节点的数据，簇首需要掌握以下信息:1.与自己直连的父簇簇首，包括父簇簇首和子簇簇首；2.自己的簇内节点和子簇簇内成员；3.对于后代簇首和其簇内成员，仅知道在自己那个簇簇首下，不关心级别。

只要掌握了这些信息，每个簇首就可以对网络中的数据做出最短的路由。所以在生成树算法中，通告簇加入的同时会将所有簇成员的信息逐级向上通告，同时，下级任何节点的改变也会通告生成树维护算法通告给各级簇首。

4 结束语

本文提出的树簇结合的路由算法采用先应式和反应式路由相结合的方式来提高路由的性能；在簇首的骨干树结构中簇内网络结构的改变信息不用通告给所有簇首，节点的加入和离开只需要通告给本簇到根节点路径上的簇首，节点的位置改变也只需要通告给前后位置和根节点之间路径上的簇首；而簇首掌握了目的节点的“大方向”，不需要像反应式路由那样作遍历路径探询。通过分析可以看出，分簇算法和骨干树路由算法的结合，可以提高骨干树路由对大规模和强干扰网络的适应性，同时，也可以使分簇路由算法协议更加高效。

[1] 蔡伟等.电力线载波通信信道建模技术综述[J].电力系统保护与控制, 2012, 40(10): 149-154.

[2] 吴军基等.电力线通信信道背景噪声建模研究[J].电力系统保护与控制, 2011,39(23):6-10.

[3] MENG Ju-lian.Noise analysis of power-pine communications using spread-spectrum odulation[J].IEEE Trans on Power Delivery,2007,22(3):1470-1476.

[4] 冉庆华,吴玉成,祁美娟.低压电力线载波通信网络自动组网方法研究[J].电力系统保护与控制,2011,39(10): 53-58, 63.

[5] 范函等.一种电力线载波通信自适应阻抗匹配方案[J]. 电力系统保护与控制,2009,37(8):79-82.