Software Engineering and Applications 软件工程与应用, 2012, 1, 38-42 http://dx.doi.org/10.12677/sea.2012.12007 Published Online December 2012 (http://www.hanspub.org/journal/sea.html) Cluster Tree Routing Algorithm Design for Power Line Communication Networks* Ping Pan Department of Electronic Information Engineering, Changsha Normal College Hunan, Changsha Email: Panping15@qq.com Received: Oct. 8th, 2012; revised: Oct. 15th, 2012; accepted: Nov. 7th, 2012 Abstract: Physical topology of low-voltage networks is unpredictable and its Power Line Communication (PLC) chan- nel is changeable, reliab ility of communication limits badly the application scale of PLC in practice. In this paper, a new Router Algorithm is proposed for PLC. Considering the channel state which is exquisite change and the successful level which is very lower in communication, dynamic clustering based on node relevance is used. According to the intension of signal, the probability o f co mmunicatio n and con nectiv ity of nod e, the router selects cluster h ead an d the members o f cluster based on node relevance. In the stage of steady arithmetic, router completes the data collection through the way of fixed data transmission and gateway nodes initiating tran smission. When the communication of some network nodes is unusual, the router adopts mechanism of probabilistic flooding based on the number of nearby nodes to rebuild net- work. This method can guarantee real-time data transmission. The analysis shows that this router has the flexibility, practicality and effectiveness. Keywords: Low-Voltage Power Line Communication; Backbone Tree Routing; Clustering Routing; Strategy 电力线载波通信网络的树簇路由算法设计* 潘 萍 长沙师范高等专科学校,电子信息工程系,长沙 Email: Panping15@qq.com 收稿日期:2012 年10 月8日;修回日期:2012 年10 月15 日;录用日期:2012 年11 月7日 摘 要:电力线信道的剧烈变化使得节点之间的网络连接变的很不可靠,甚至影响网络的逻辑拓扑结构。该文 通过对现有电力线载波网络的路由结构进行分析比较,提出了适用于窄带低压电力载波通信的树簇路由算法, 给出了树簇路由算法的协议框架,设计了簇生成算法、簇维护算法、生成树维护算法以及树维护算法的具体实 现,最后给出了树簇路由策略。经过性能仿真与分析,树簇结合的动态路由适合低压窄带载波通信技术条件, 满足了其工程实施的需要。 关键词:低压电力载波通信;骨干树路由;分簇路由;策略 1. 引言 近年来,低压电力线作为通信媒介技术被广泛地 研究,并已应用于小区抄表系统、智能楼宇控制和路 灯控制[1-6]等工程中。目前基于电力载波组网的研究较 少主要有以下几个方面:如文献[6]中提出的基于蚁群 的最短路径路由算法,不过其大量的资源消耗在路径 探测上面,由于现有窄带载波速率的限制其很难达到 Qoc 的要求;在文献[2]中提出了基于传输矩阵的路由 算法,这种算法简单且易于使用,但树型结构的路由 表很难适应动态变化的载近年来,低压电力线作为通 *资助信息:湖南省教育厅科学研究项目,编号:11C0097。 Copyright © 2012 Hanspub 38 电力线载波通信网络的树簇路由算法设计 信媒介技术被广泛地研究,并已应用于小区抄表系 统、智能楼宇控制和路灯控制[1-6]等工程中。目前基于 电力载波组网的研究较少主要有以下几个方面:如文 献[6]中提出的基于蚁群的最短路径路由算法,不过其 大量的资源消耗在路径探测上面,由于现有窄带载波 速率的限制其很难达到 Qoc 的要求;在文献[2]中提出 了基于传输矩阵的路由算法,这种算法简单且易于使 用,但树型结构的路由表很难适应动态变化的载波网 络,所以在电力网络运用的前景也不明朗。 基于骨干树与分簇相结合的树簇路由算法以树 形骨干网作为电力线载波通信网络的骨架,树形拓扑 分支上的寻路简单,算法容易实现,并能避免反应式 路由的全局更新和先应式路由的网络时延,提高了骨 干树协议对大规模和强干扰网络的适应性,同时,也 可以使分簇路由算法协议更加高效。 2. 电力线载波网络结构分析 电力线载波网络的拓扑结构从通信角度分为:对 等式平面结构和分级结构。对等式平面结构采用完全 分布式的控制方法,所有节点的功能和地位平等,既 是普通节点又是路由器。它主要适用速度较高的小型 网络实验中。 分级结构采用分层的控制方式具有很强的抗毁 性。但是维护分级结构需要节点执行复杂的分簇算 法,簇首节点也可能成为网络瓶颈。 骨干树作为一种路由,采用分级结构,易于管理 和扩展,兼顾了路由维护信息量和寻路时延的要求, 具有巨大的发展前景。普通的分簇算法簇首节点之间 构成的是网状拓扑。如果在簇首上实现骨干树路由协 议,形成一个树形网络结构,不仅简化了簇间网络的 结构。这样为路由算法带来最直接的变化是降低了先 应式路由协议的开销,提高了路由算法的反应时间。 因此采用分簇算法和骨干树路由算法相结合,可以提 高骨干树协议对大规模和强干扰网络的适应性,同 时,也可以使分簇路由算法协议更加高效。 3. 树簇路由算法原理 基于树形骨干网和节点相关度分簇的树簇路由 算法主要由四部分组成:簇生成算法、簇维护算法、 生成树算法和生成树维护算法。图1是树簇算法结构 簇维护算法 节点加入网络 骨干网算法 骨干网维护算法 簇生成算法 Figure 1. Schematic diagram: tree clustering algorithm 图1. 树簇算法结构示意图 示意图,准备加入网络的节点首先运行簇生成算法, 簇生成算法完成后,网络节点被划分成多个簇。与此 同时簇维护算法开始运行,用于维护簇结构的有效性 和处理簇首失效或者簇内结构发生变化的情况。簇生 成算法的完成将会触发生成树算法的运行,生成树算 法将各个簇连接在一起,生成一个树形骨干网的簇树 网络。然后生成树维护算法开始运行,用于维护树形 骨干网的有效性和处理树形骨干网结构发生变化时 的情况。此时,簇维护算法和生成树维护算法同时运 作。 4. 树簇路由算法设计 对PLC网络的载波的分簇算法做以下约定: 1) 某相电网上有 n个通信节点,电力线物理链路 是连通的,根节点的地址编号为 0,其他物理变化依 次1, 。 2,, n 2) 任意节点至少可以与 1个其他节点通信,不存 在通信孤立点。 3) 最大限度的建立网络节点连接。 4) 已经获得逻辑编号的通信节点不再参与逻辑 节点分配。 5) 网络通信最长响应周期为 T,则 T/n 定义为时 隙,即时间片。每个节点在时隙内发生数据,发生的 具体时间和节点编号相关。 6) 短时间内通信,电力线通信网为对等网。 7) 忽略电信号在铜铝等导电介质的传播时间。 4.1. 簇生成算法 簇生成算法是根据网络需求按照某种规则将网 络划分成可以相互连通并覆盖所有节点的多个簇。在 Copyright © 2012 Hanspub 39 电力线载波通信网络的树簇路由算法设计 网络初始化阶段,由网络内根节点广播“竞选簇头” 的消息,所有接收到此消息的节点将根据接收信号强 度、历史抄通概率和网络连通度决定是否参加竞选。 节点首先计算信号强度与历史抄通概率的乘积,若该 值小于某一阈值,直接放弃竞争,并在接下来的时间 段内选择加入某一个簇;若该值大于某一阈值,则节 点向网络主节点发送“竞选簇头”的消息,该消息包 括本节点历史抄通概率和网络连通度信息。网络主节 点接收到所有参加竞选节点发送的“竞选簇头”消息 后,以接收信号强度主,竞选节点的历史抄通概率和 网络连通度 d为辅,选择 k个节点作为簇头,并广播 “任命簇头”消息。接收到此消息的节点如果发现任 命的簇头中有自己,就当选为簇头。节点当选簇头以 后,发送“重新加入簇”消息告知其它节点自己是新 簇头。非簇头节点根据与广播簇头的相关度值来选择 加入哪个簇,并发送“请求加入簇”消息告知该簇头。 由于载波网络节点的随机聚集性,因此必然存在许多 非簇头节点处于 2个或多个簇头的重复覆盖区域内, 此时簇头将根据自身的网络连通度以及与非簇头的 相关度值确定是否接收该节点加入本簇。具体原则如 下: 1) 若节点与簇头的相关度值等于1,说明该节点 是簇头的相邻节点,则允许加入该簇。 2) 若相关度值大于 2,则该节点优先加入网络连 通度较低的簇头所在簇。 4.2. 生成树算法 生成树算法将各个簇之间以树形拓扑的形式组 织在一起,同时将节点间路由提供足够的信息。首先 指定根簇簇首ID,这个根簇是发起生成树算法的源 头,产生一个且仅一个节点的一级骨干树。未加入骨 干树的簇首广播发出 Cluster_join_Require,收到该请 求的已加入骨干树的簇首单播发出 Cluster_Join_Re- ply。请求簇首根据收到的应答选择一个级别最小的簇 作为自己的父簇并且广播发出 Cluster_Join_Report, 并且将自己的级别设为父簇级别 + 1,Cluster_Join_Re- por 中包括了簇内所有节点的信息。收到 Cluster_Join_ Repor 的簇首根据其中的信息判断请求簇是否成为自 己的子簇,如果成立则将加入簇的信息向上级簇簇首 逐级通告。未加入网络的簇重复步骤,直到所有的簇 首都加入到骨干树上。 4.3. 簇维护算法 簇维护算法用于维护簇内节点之间链路的有效 性以及处理簇内链路失效的情况。如图 2所示。簇维 护算法不是一个顺序执行的算法,而是一个由事件触 发的算法,针对不同的事件作出不同的处理。 事件 1:担任簇首的邻居节点超时,该节点重新 启动簇生成算法。 事件 2:担任簇内成员的邻居节点超时,如果本 节点是簇首,则簇首启动生成树维护算法,从自己的 邻居表中删除该邻居节点的记录,并使用逐级向上通 告该簇内成员失效;如果本节点是簇内成员,则仅仅 从自己的邻居表中删除该邻居节点的记录。 4.4. 生成树维护算法 生成树维护算法中所有的簇之间保持树形拓扑 结构,簇首之间相互发送 Tree Hello的方式用来维持 邻居簇首之间的链路,同时为每个邻居簇首设置定时 器。当定时器超时后,将会触发节点执行相应的处理。 树形拓扑的维护和更新是以 Update 报文携带的信息 为依据的。 5. 树簇路由策略 在树簇路由中,算法执行完成的节点中掌握了足 够的信息可以为节点间的通信提供路由依据。下面从 启动生成树维护算 法,并向父节点报 告簇内成员失效 接收 Cluster_Join_ Report 删除该节点信息 超时的节点 是否簇首 本节点是否簇首 开始 结束 Figure 2. Flow chart: cluster maintenance algorithm 图2. 簇维护算法流程图 Copyright © 2012 Hanspub 40 电力线载波通信网络的树簇路由算法设计 簇间路由和簇内路由两个层次分别说明其中的路由 策略。 5.1. 簇内路由策略 由于在簇内每个节点都保存所有一跳邻居信息, 而簇的直径最多只有两跳,所以对于到达邻居的数据 采用直接投递,对于非邻居的簇内节点首先递交给簇 首,因为这是簇内相邻成员间最短的路径。例如在图 3中,簇内邻居之间可以直通,簇内成员 A可以直接 向B发送数据;簇内成员 B经过簇首 E与节点c或者 D通信。一般传到簇外的数据要么经过簇首,或者可 以传递给直连网关由网关决定路由。在图 3中,由节 点2发送到簇外的数据可以直接交给网关 A路由,而 节点 5只能先递交给簇首 1,由簇首 1决定交给哪个 网关路由。可能出现下面情况,节点 2将数据直接递 交给网关 A,但是节点 2的目的节点必须通过网关B 才能到达,这时网关 A必须要能根据簇间路由信息做 出判断,将数据通过簇首 1发送给网关 B。这就要求 网关掌握的簇间结构信息和簇首一样多,所以,一旦 簇首掌握的信息发生更新,一定要通告簇内的所有网 关。经过性能仿真与分析,树簇结合的动态路由适合 低压窄带载波通信技术条件,满足了其工程实施的需 要。 5.2. 簇间路由策略 在生成树算法中,我们已经说明了簇首为了将簇 之间组织成骨干树形拓扑而需要掌握的簇结构信息。 为了正确路由网络中每个节点的数据,簇首需要掌握 以下信息: 1) 与自己直连的父簇簇首,包括父簇簇首 A B C 1 2 3 4 5 簇成员 簇首网关 Figure 3. Flow chart: cluster routing strategies 图3. 簇内路由策略示意图 和子簇簇首;2) 自己的簇内节点和子簇簇内成员;3) 对于后代簇首和其簇内成员,仅知道在自己那个簇簇 首下,不关心级别。 只要掌握了这些信息,每个簇首就可以对网络中 的数据做出最短的路由。所以在生成树算法中,通告 簇加入的同时会将所有簇成员的信息逐级向上通告, 同时,下级任何节点的改变也会通告生成树维护算法 通告给各级簇首。 最后给出节点的选路规则: 1) 若目的节点是与自己直连的节点,包括父簇簇 首、子簇簇首和簇内邻居,则直接投递。 2) 若目的节点是自己的下级节点,则将报文投递 给其所属的子簇簇首。 3) 若没有目的节点路由信息,则将报文投递给父 簇簇首。 6. 路由性能分析 电力线载波网络和传统的 AD_HOC 网络具有很 大的相似之处,根据网络中路由发现策略的角度,可 将路由方式分为反应式路由先应式路由两种。 基于以上章节的内容,树簇路由中采用了分层网 络结构,与全对等的 PLC网络相比,组网和路由的开 销大大降低,有利于组建较大规模网络。从路由算法 的性能上来看,它具有以下的一些优点: 1) 能够妥善解决路由环路问题的:根据图论学的 知识可以知道,树形的拓扑图中是没有环路的。骨干 树算法的核心思想是主动地维护 PLC载波路由器的 逻辑拓扑结构为树形。这样大大降低了 PLC 网络由于 拓扑的变化过快而出现路由环路的概率。现有的各种 动态路由算法都采取了不同的避免路由环路的方法, 但是算法往往比较复杂,开销较大,而采用树形拓扑 是一个相对简单且有效的方案。 2) 先应式与反应式相结合的混合式路由协议:传 统的动态路由协议均有一些先天的缺陷。先应式路由 协议需要周期性地发布路由信息以维护路由表的一 致性。网络拓扑的任何变化都引起全网范围内路由更 新动作,维护路由所需的带宽开销太大;反应式路由 只有在节点有通信需求时才会查找路由,减少了路由 信息同步带来的带宽开销,但理论上每个未知的目的 节点都要花费时间重新寻径,因此开销的降低是以延 迟加大为代价的。在运行骨干树路由的自组织网络 Copyright © 2012 Hanspub 41 电力线载波通信网络的树簇路由算法设计 Copyright © 2012 Hanspub 42 中,每个 PLCR 仅仅需要掌握局部的拓扑结构,即它 仅知道哪些 PLCR 和自己直接相连,而对非直连的节 点,它只需知道要经过那些 PLCR 转交即可,并不关 心中间经过了多少级PLCR;而当网络的拓扑结构变 化时,只需通知汇聚点以下的PLCR。这样就避免了 先应式路由算法中当拓扑结构变化时的全网的路由 更新动作,减小了路由算法的开销;与反应式路由算 法相比,由于事先已经知道了目的节点的“大方向”, 所以不用每个分组都去重新寻径,降低了网络时延。 从上面的分析可以看出,树簇路由能够满足 PLC 网络中自组织组网、动态拓扑发现、和快速拓扑形成 的要求。但是在网络规模增大或者有较强干扰时,路 由性能将会迅速下降。 7. 结束语 本文提出的树簇结合的路由算法采用先应式和 反应式路由相结合的方式来提高路由的性能;在簇首 的骨干树结构中簇内网络结构的改变信息不用通告 给所有簇首,节点的加入和离开只需要通告给本簇到 根节点路径上的簇首,节点的位置改变也只需要通告 给前后位置和根节点之间路径上的簇首;而簇首掌握 了目的节点的“大方向”,不需要像反应式路由那样 作遍历路径探询。通过分析可以看出,分簇算法和骨 干树路由算法的结合,可以提高骨干树路由对大规模 和强干扰网络的适应性,同时,也可以使分簇路由算 法协议更加高效。 参考文献 (References) [1] 刘小波, 王俏华, 肖登明. 基于SSCP300 的居民智能小区抄 表系统的实现方案[J]. 电工技术杂志, 2004, 11: 47-50. [2] 孔令通. 电力线通信关键技术研究[D]. 北京交通大学, 2007. [3] 刘晓胜, 戚佳金, 宋其涛等. 基于蚁群s算法的低压配电网电 力线通信组网方法[J]. 中国电机工程学报, 2008, 28(1): 71- 76. [4] 刘海涛, 陈长德, 张保会. 低压电力线通信传输环境研究[J]. 电力自动化设备, 2001, 18(9): 14-17. [5] R. M. Vines. Noise on residential power distribution circuits. IEEE Transactions on Electron, 1994, 26(4): 13-21. [6] S. B. Zhang, Z. M. Liu. A QoS routing algorithm based on ant algorithm. Beijing: 25th Annual IEEE Conference on Local Computer Networks, 574-578. |