（信息与通信工程专业论文）电力载波传感器网络路由算法的研究.pdf

摘要 电力载波传感器网络( p o w e rl i n ec a r r i e rs e n s o rn e t w o r k ，p l c s n ) 是由传输介质 电力线及线上大量的载波节点所组成一种特殊的自组织传感器网络。由于电力线通信信 道的噪声干扰大，信号衰减严重，导致网络的拓扑结构复杂多变，载波节点多而复杂且 随机的加入或退出使得通信链路更加不稳定，甚至中断，降低了整个网络的通信可靠性。 如何在变化复杂的电力线上实现稳定可靠的数据传输成了电力载波传感器网络的热点 问题。因此，设计一种合理有效的动态路由算法，以适应电力载波传感器网络动态变化 的拓扑结构，实现稳定可靠的通信是至关重要的。 鉴于电力载波传感器网络的特点和逻辑拓扑结构，分析基于分簇思想的路由算法。 分簇算法能以较小的网络开销建立覆盖整个网络的簇结构，有利于节点的管理和数据的 融合，具有一定的灵活性和可扩张性，能适应动态变化的网络拓扑结构。基于此提出了 基于分簇动态路由( c l u s t e rb a s e dd y n a m i cr o u t i n g ，c b d r ) 算法。算法采用最小i d 分 簇算法的思想以局部遍历的方式快速、动态的建立网络的簇结构。在分簇的过程中，可 增大节点的有效通信距离进而简化簇结构和减少组网的时间。针对网络节点复杂通信链 路不稳定的特点，算法还引进了多路径的思想保证通信的可靠性。在维护簇结构时，采 用自适应的按需机制，减少簇结构的维护开销，尽量保持原有的簇结构。 接着在m a t l a b 仿真平台下对c b d r 算法进行仿真，仿真结果表明算法能有效地建 立网络的簇结构并减少了网络组网时间，当载波节点随机加入或退出网络时，算法能够 自适应地更新簇结构，维护有效的通信路由，提高了网络的可靠性和稳定性。最后总结 c b d r 算法特点并指出了进一步的研究工作。 关键词：电力载波传感器网络，分簇算法，局部遍历，动态路由算法，自适应 r e s e a r c ho nr o u t i n ga l g o r i t h mo fp o w e rl i n e c a r r i e rs e n s o rn e t w o r k w a n gk e n s h e n g ( i n f o r m a t i o na n dt e l c o m m u n i c a t i o ne n g i n e r i n g ) d i r e c t e db ya s s o c i a t ep r o f e s s o rh o n gl i a b s t r a c t t h ep o w e rl i n ec a r r i e rs e n s o rn e t w o r k ( p l c s n ) i sas p e c i a ls e l f - o r g a n i z i n gs e n s o r n e t w o r k , c o m p o s e do ft h ep o w e rl i n et r a n s m i s s i o nm e d i u ma n dal a r g en u m b e ro f t h ec a r r i e r n o d e s b e c a u s eo fs e v e r en o i s ei n t e r f e r e n c ea n ds i g n a la t t e n u a t i o n , t h en e t w o r kt o p o l o g y s t r u c t u r eb e c o m e sm o r ec o m p l e xa n de a s i l yc h a n g e a b l e i tm a k e sc o m m u n i c a t i o nl i n k sm o r e u n s t a b l ea n de v e nb r o k e no f fw h e nt h ec a r r i e rn o d e sr a n d o m l yj o i ni no rw i t h d r a wf r o mt h e n e t w o r k a c c o r d i n g l y , i td e c r e a s e st h er e l i a b i l i t yo fn e t w o r kc o m m u n i c a t i o n i ti sah o ti s s u e h o wt ot r a n s m i tt h ed a t as t a b l ya n d r e l i a b l yo np o w e r l i n ew h o s ec h a n n e li st i m e v a r i a n ta n d c o m p l e x t h e r e f o r e ，i ti sv e r yi m p o r t a n tt od e s i g nar a t i o n a la n de f f e c t i v ed y n a m i cr o u t i n g a l g o r i t h mf o rd y n a m i c a l l yc h a n g e a b l ep o w e rl i n ec a r r i e rs e n s o rn e t w o r kt o p o l o g y , i no r d e rt o a c h i e v es t a b l ea n dr e l i a b l ec o m m u n i c a t i o n i nv i e wo ft h ec h a r a c t e r i s t i c sa n dl o g i c a lt o p o l o g yo ft h ep o w e rl i n ec a r t i e rs e n s o r n e t w o r k s ，t h ea n a l y s i so nc l u s t e rr o u t i n ga l g o r i t h mi sc a r r i e do n c l u s t e r i n ga l g o r i t h mi sa b l e t oe s t a b l i s hc l u s t e r - b a s e ds t r u c t u r ef o rt h ew h o l en e t w o r ku s i n gl e s so v e r h e a d i ti sn o to n l y c o n d u c i v et ot h en o d em a n a g e m e n ta n dd a t ai n t e g r a t i o n , b u ta l s of l e x i b l ea n de x p a n s i v et o a d a p td y n a m i c a l l yc h a n g e a b l et o p o l o g y a sm e n t i o n e da b o v e ，ac u l s t e rb a s e dd y n a m i c r o u t i n g ( c b d r ) a l g o r i t h mi sp r e s e n t e d c b d ra l g o r i t h me s t a b l i s h e sc l u s t e rs t r u c t u r ef a s ta n d d y n a m i c a l l yb ym e a no fp a r t i a lt r a v e r a lb a s e d o nt h el o w e s ti d c l u s t e r i n ga l g o r i t h m i nt h e c l u s t e rp r o c e s s ，t h et h es t r u c t u r es i m p l i f ya n dt h et i m e - c o n s u m p t i o nr e d u c ea c c o r d i n g l ya st h e e f f e c t i v ec o m m u n i c a t i o nd i s t a n c ee n l a r g e s i no r d e rt oe n s u r et h er e l i a b i l i t yo fc o m m u n i c a t i o n , t h em u l t i p a t hi d e ai si n t r o d u c e d i nt h ep r o c e s so fm a i n t a i n i n gt h ec l u s t e rs t r u c t u r e ，t h e a d a p t i v eo n d e m a n dm e c h a n i s mi sa d o p t e dt or e d u c et h er o u t eo v e r h e a da n dk e 印t h eo r i g i n a l c l u s t e rs t r u c t u r e n e x t , c b d ra l g o r i t h mi ss i m u l a t e du n d e rm a t l a bs i m u l a t i o np l a t f o r m t h es i m u l a t i o n r e s u l t ss h o wt h a tc b d r a l g o r i t h mc o i ie f f e c t i v e l ye s t a b l i s hc l u s t e rs t r u c t u r ea n dr e d u c et h e t i m ec o n s u m p t i o nw h e nt h ec a r d e rn o d e sr a n d o m l yj o i ni no rq u i tf r o mt h en e t w o r k , t h e a l g o r i t h mc 锄a d a p t i v e l yu p d a t et h ec l u s t e rs t r u c t u r e m a i n t a i ne f f i c i e n tc o m m u n i c a t i o nr o u t e a n di m p r o v en e t w o r kr e l i a b i l i t ya n ds t a b i l i t y a tl a s t , c b d ra l g o r i t h mc h a r a c t e r i s t i c sa r e s u m m a r i z e da n dt h ef u r t h e rr e s e a r c hw o r ki sp u tf o r w a r d k e y w o r d s ：p o w e rl i n ec a r d e rs e n s o rn e t w o r k ( p l c s n ) ，c l u s t e r i n ga l g o r i t h m , p a r t i a lt r a v e r s a l ，d y n a m i cr o u t i n ga l g o r i t h m ，s e l f - a d a p t i v e 关于学位论文的独创性声明 本人郑晕声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数掘是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国彳i 油 入学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的i 司志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 同期：沙。年。5 月彳同 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查i 蒯、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使川授权i 司上。 学位论文作者签名： 羔交选 指导教师签名： 只期：劢p 年p 占月刁闩 鼽帅年寸月矿 中国石油大学( 华东) 硕学位论文 1 1 课题背景及意义 第一章前言弟一早刖苗 近年来，随着信号处理技术、通信技术、传感器技术以及电力载波技术的进步和突 破，电力载波通信得到很大程度的发展【i 卅。电力载波传感器网络( p o w e rl i n ec a r d e r s e n s o rn e t w o r k , p l c s n ) 以传感器技术、信息处理技术和电力载波通信技术为核心技术， 由作为传输介质的低压电力线及其线上大量的载波节点所组成一种特殊的自组织传感 器网络。它用载波节点进行数据的发送和接收，以单跳或多跳的形式传输特定区域内的 数据并对其进行相关的处理，使用户获悉准确的信息。随着社会的需要和技术的不断进 步，电力载波传感器网络的技术开发和应用吸引更多学者的关注和研究。 电力线是迄今为止用户最多且分布广泛的一种传输媒质，只要有电力线的地方就可 以自组形成单、多跳电力载波传感器网络实现数据通信，不需要铺设额外的通信线路， 有效利用了原有的线路资源，也简化整个网络的布局和减少建设投资。电力线的有效利 用缓解了目前通信领域里频带资源短缺的发展需求，也为信息通信网络提供了更多的信 息承载和更大的发展空间。 电力载波传感器网络作为一种具有广阔前景的通信网络，除了使用广泛、成本低、 见效快及不需要重新的线路铺设等优势外，网络支持永久在线，实现即插即拔功能，这 使网络在实时监控和智能家居网的应用上具有很大优势。此外，与一般的传感器网络和 自组网相比，网络节点不受能量的限制，这使得设计路由协议时无须考虑节点能量的问 题。 然而，电力线起初是作为供电信道而并非是传输信息的专用信道，线上连接着各种 负载且容易断开和加入。电力载波传感器网络具有负载复杂多变，噪声干扰强，信号衰 减大，信道具有时变性等特性【5 一。噪声干扰强将影响传输的质量，衰减过大将会制约 着信号的通信距离，而负载的变化引起通信信道的变化。这些使得网络的通信链路不稳 定和拓扑结构复杂多变，严重影响了通信的可靠性和稳定性，降低网络的通信性能。如 何在复杂多变的电力线上实现稳定可靠的数据通信问题亟待解决，解决网络中通信信道 的稳定性，维护通信的可靠性成了电力载波传感器网络研究中极具挑战性的一个课题。 目前，国际国内很多学者正在进行关于电力载波传感器网络方面的研究，有些公司正尝 试用这种新型网络进行商业运营、部门管理等工作，电力载波传感器网络具有非常广阔 第一章前言 的应用前景。 为了解决网络中通信信道的稳定性和网络通信的可靠性问题可以从网络路由协议 角度分析，设计合理的高效的网络路由算法来提高通信的稳定性和可靠性。电力载波传 感器网络的拓扑结构是动态变化的，在网络运行时，某些节点容易失效，不能连接到网 络中，从而导致链路的中断，需要采用一种高效的、具有自适应能力的动态路由算法， 调整中继节点，建立高效路由，并能及时的维护网络。为了减少网络的不稳定性和提高 可靠性，就需要动态处理这些问题，但是目前缺少适用于电力载波传感器网络的动态路 由算法，因此需要研究适用于此网络的具有自适应能力的动态分簇路由算法，从而从整 体上改善整个网络的性能和效率，使电力载波传感器网络能够得到更广泛的应用。 综上所述，通过研究电力载波传感器网络的自适应动态分簇路由算法，以达到高效 的建立路由，调整中继和维护路由，从而提高网络的稳定性和可靠性，具有重要的理论 意义与实用价值。 1 2 国内外研究现状 为了保证网络通信的可靠性和稳定性和确保信息的传送的快速性和准确性，设计的 路由算法必须具有对网络拓扑结构动态变化的快速应变能力，能高效的利用带宽，减少 路由控制开销和延时。对此，论文针对电力载波传感器网络与无线自组网的相似点，如 载波节点的随机退出和加入可以视为自组网的节点移动问题，进行路由算法的设计和研 究。一般自组网路由算法含有表驱动和按需路由算法，平面和层次路由算法等，将在后 面的章节进一步讲述。至今，国内外学者已在这方面进行不少的研究和实验，取得一定 的成果。 在国外，g e r db u m i l l e r 等人【g 】由于电力线随机的信道特性，提出了动态源路由和基 于洪泛路由两种不同动态中继算法。从理论上分析并给出两种算法在轮询中平均持续时 间的计算公式，最后在带宽占用率和路由开销两方面比较两种中继算法，仿真结果表明 基于洪泛的中继路由算法的性能要优于动态源路由中继算法。但是，两种算法并未考虑 到信道时变性和拓扑随机变化。 j o 酉n a n 等人1 9 l 提出了一种基于电力线信道状态的自适用路由算法( a c s r ) 。在该 算法中使用信道指示参数( c s i ) 和通信距离作为检测电力线信道的动态变化的度量。 同时为了减轻网络负载采用基于概率防洪算法。但是网络结构是星型结构，节点之间是 m a s t e r - s l a v e 关系，s l a v e s 之间的通信都要通过m a s t e r 。这种网络结构限制了网络规模的 2 中国石油大学( 华东) 硕士学位论文 扩展性。 r a u lb r i t o 等人【l o 】在m a s t e r - s l a v e 电力载波通信系统中提出了一种高效的 m a s t e r - s l a v e 洪泛路由协议，该协议采用了单频网络( s f n ) 使用概率的技术，降低了包 头大小的开销和网络管理时的数据冲突。同时也实现了快速收敛，能较快适应网络的变 化。但网络中节点增多时网络性能急剧下降，该网络结构不适合大规模网络。 m a r k u ss e b e c k 等人【l l 】提出了基于星型结构的多跳路由协议。系统基于拓扑树型拓 扑结构，每个节点都可以充当路由器转发别的节点发来的数据包。但是该系统底层仍然 是t d m a 协议，同样限制了网络规模，不适合大规模网络中的应用。 在国内，赵杰卫等人【1 2 l 在蚁群优化算法原理的基础上提出了一种新的动态路由算 法。算法根据信道的动态变化建立和维护有效的中继路由，保证通信的成功率，提高了 可靠性。算法不需周期性发送广播分组来维护路由的实时性，并引入了候选集策略加快 了搜索的速度。算法具有一定的实时性并提高了电力载波抄表成功率，但算法只是针对 抄表应用并无做其他考虑。 刘晓胜等人提出了低压电力线通信的自动路由算法。算法引进了类蚁群算法建立 自动路由模型。在网络运行时，根据信道的变化动态地维护有效路由，保证了通信的有 效性和延长了有效通信距离。但算法在寻找最优路由时比较耗时，需进一步改进。 随着网络规模的发展，要求设计路由算法具有良好的可扩展性和灵活性，基于分簇 的层次性路由算法极有可能成为今后路由协议研究的首选。 b a s a g n is 等人【1 4 】提出了一种用于动态网络的基于簇结构的路由算法，该算法的 性能取决于网络中簇的平均尺寸，并且簇为集团簇。l i ncr 等人【1 5 】提出了基于分簇结 构可以支持实时连接的带宽路由算法，簇中节点的带宽定义为一个节点允许通过的实时 连接的数目，它的目标是找到能够满足带宽要求的最短路径。 f i l i p ep a c h e c o 等人【1 6 】提出了基于电力载波拓扑动态变化的分层路由协议。该分层结 构通过加入网桥节点实现，节点与节点之间不能相互通信。发送数据时数据从节点通过 网桥并且必须经过网桥，经过两跳转发到达控制中心。因为电力线上节点直接通信的距 离有限，这种网桥的结构在远距离环境下并不适合。而且该系统底层采用轮询的方式工 作，在节点多的情况下系统效率很低。 国内郑凯等人【1 7 】提出了基于a o d v 的渐进式分簇路由协议，采用渐进的方式实现 a o d v 路由过渡到分簇路由，在分簇路由中融合了a o d v 机制，具备了根据簇结构和 洪泛两种路由发现机制，该协议性能优于a o d v 路由并提高了网络的可扩展性，尤其 3 第一章前言 在网络节点较多时，能有效的通信，提高了网络的效率。 戚佳金等人【i8 】提出了低压电力线通信的分簇路由算法，在非交叠分簇算法的基础上 实现分层管理的动态路由。算法根据信道的变化动态的建立和维护网络路由，保证网络 有效地通信。此外，还提出了时间序列分配算法是路由算法更加完善。最后通过仿真证 明算法具有较大的可扩展性和有效性。但算法未考虑节点的负载过大、频繁变动等情况。 总之，国内外越来越多的学者开始进行基于分簇的动态路由算法的研究，然而如何 将自适应动态路由算法有效地应用到电力载波传感器网络中仍在处于探索阶段，有待于 进一步理论研究和完善。鉴于电力载波传感器网络的特点，采用分簇算法动态的建立路 由，并引进a o d v 按需机制进行路由维护，能有效降低网络的路由开销。引进分簇算 法的思想，使网络具有良好的可扩展性，保证网络通信的可靠性并提高网络路由的效率。 本文将从这方面进行路由算法的研究。 1 3 研究内容与方法 为了提高电力载波传感器网络的稳定性和可靠性，在深入分析网络的结构特性的基 础上，引进分簇算法思想，并根据树状的网络拓扑结构对节点进行局部的遍历，从而快 速建立簇结构并进行路由发现，当载波节点变动，拓扑结构发生变化时，调整中继转发 载波节点及时维护路由保证链路的连通，实现稳定有效的通信，提高通信的可靠性，解 决电力载波传感器网络中的通信难题。基于以上思路，整个论文主要展开以下几个方面 的研究工作： ( 1 ) 从理论上讲述电力载波传感器网络的含义、构成及特点，并分析该网络拓扑结 构说明p l c s n 路由发现的意义。鉴于电力载波传感器网络自组织的特点，文中将介绍 典型的自组网路由协议并分析其中的优劣。 ( 2 ) 在分析网络拓扑结构和典型自组网路由算法的基础上，介绍分簇算法的原理及 其在分层路由中的重要性，接着分析研究现有典型的分簇算法，指出分簇算法在p l c s n 路由中的优越性。 ( 3 ) 在原有的基础上进一步分析基于簇树结构的分簇算法，充分结合p l c s n 的网 络特性，进一步地提高分簇算法的效率和性能。 ( 4 ) 提出基于分簇的动态路由( c b d r ) 算法。首先介绍c b d r 算法涉及到关于 树、图、遍历等基本概念。在此基础上，给出算法的基本思想、假设条件及算法的具体 实现步骤。 4 中国石油大学( 华东) 硕士学位论文 ( 5 ) 基于分簇的动态路由( c b d r ) 算法的仿真验证，通过设定环境的参数，在 m a t l a b 对算法进行仿真，分析仿真结果，验证算法的性能。最后简单介绍一下此算法在 电力载波控制系统网络中的应用。 1 4 论文的组织结构 全文共分六章，各章的研究内容如下： 第一章前言 介绍课题产生的背景以及研究的意义，讲述课题的国内外研究现状，最后简单介绍 下本文的主要研究内容和工作安排。 第二章电力载波传感器网络概述及路由算法 介绍电力载波传感器网络的概念、构成和特点，对网络拓扑结构进行分析，并指出 对网络进行路由的意义。同时，分析几种典型的网络路由算法，对比其中的优劣。 第三章路由协议中分簇算法的研究 介绍分簇算法的原理及衡量标准指出其在分层路由中的重要性。此外，分析研究现 有的典型分簇算法，对比其中的优劣。在原有的基础上进一步分析基于簇树结构的分簇 算法，并指出分簇算法在p l c s n 的优越性。 第四章p l c s n 中基于分簇的动态路由算法 基于前述篇章提出基于分簇的动态路由( c b d r ) 算法。介绍c b d r 算法涉及到的 基本概念。在所给的前提条件下，给出算法的基本思想、实例描述及具体的实现步骤。 第五章p l c s n 中c b d r 算法的仿真结果及分析 根据第四章的算法实现步骤，在m a t l a b 平台下给定的环境参数中进行仿真验证， 验证算法的可行性并从组网时间、可靠性等方面分析仿真结果，进而评价c b d r 算法。 最后总结算法的特点并介绍其理论应用。 结论总结与展望，对全文的主要研究内容和创新点进行总结并指出迸一步的研究 方向。 1 5 本章小结 本章主要介绍课题的研究背景和意义并总结了课题的国内外研究现状，给出全文的 结构和主要研究内容。 5 第二章p l c s n 概述及路由算法 第二章p l c s n 概述及路由算法 电力载波传感器网络( p l c s n ) 是以传感器技术、信息处理技术和电力载波通信技 术为核心技术，由低压电力线及其线上大量的收发数据的载波节点组成一种特殊的自组 织传感器网络，以单跳或多跳的形式传输特定区域内的数据并对其进行相关的处理，使 用户获悉准确的信息。电力线是迄今为止使用最普遍和分布广泛的传输介质，具有许多 的优势。但电力线上信号衰减大，载波节点随机加入或退出，信道时常变化导致通信逻 辑链路不稳定，拓扑结构复杂多交，影响了网络通信的可靠性。为此本章将详细地分析 电力载波传感器网络的结构及特点。 2 1p l c s n 概述 2 1 1p l c s n 结构 电力载波传感器网络以低压电力线作为传输介质，有大量的电力载波节点无规律地 分布在电力线上，电力线本身为多路分支的总线。电力载波节点根据所起作用的不同， 主要分为网关节点、中继节点和终端节点，网关节点是整个网络的中心节点，负责管理 和控制，中继节点是一种特殊的终端节点，具有中继转发数据的功能。电力载波传感器 的网络结构【1 2 j 如图2 1 所示。 图2 - i电力载波传感器网络结构图 f i 9 2 - 1a r c h i t e c t u r eo fp o w e rl i n ec a r d e rs e n s o rn e t w o r k 由图可知，p l c s n 的网络结构属于多级树状结构，由网关节点与终端节点进行通 信，实现数据的转发，完成数据的传输，但存在终端节点与网关节点距离较远时由于信 号衰减而无法直接通信的情况，此时一部分载波节点作为中继节点，利用中继多跳的方 式实现路由和数据的交互。相对应于图2 1 ，p l c s n 的逻辑结构为多级的树状网络拓扑， 6 中国石油大学( 华东) 硕士学位论文 如图2 - 2 所示。 图2 _ 2 电力载波传感器网络逻辑拓扑结构 f i 9 2 - 2 l o c a lt o p o l o g ya r c h i t e c t u r eo fp o w e rl i n ee a r r i e rs e n s o rn e t w o r k 图2 - 2 中，将与网关节点相连的节点称为第一级节点，依次类推。显而易见，网关 节点可以直接和第一级中的终端节点或中级节点进行通信，随着距离的增大，信号的衰 减越大导致网关节点无法与二、三级的节点进行直接地通信，这就需要一、二级中继节 点进行多跳的中继转发数据包了。 2 1 2p l c s n 的特点 传输数据的传输介质、连接设备形成拓扑结构和共享资源的介质控制方法等技术决 定网络特征【3 2 1 。与一般的计算机网络不同，电力线在设计的时候只考虑供电特性，并未 考虑其数据传输特性，其信道多变且干扰大，线上连有不同类型的负载，这些使得电力 载波传感器网络具有一些专有的特点，具体如下： ( 1 ) 网络范围广，实现成本低 电力线是目前用户最多和分布最广的一种传输媒介，有效地利用现有的电力线传输 数据可以实现大范围的通信且无须重新铺设线路，从而减少网络线路建设费用，大大降 低通信的成本。 ( 2 ) 节点能量不受限 在研究无线传感器网络路由协议时，节点的能量有限且无法补给成了网络的一个瓶 颈，如何有效地均衡节点能量延长网络生存周期成了路由算法设计的主要考虑因素。而 电力载波传感器网络中的载波节点与电力线相连，具有恒定的能量供应，并不受节点能 量的限制。因此在设计路由算法时主要着重考虑网络的稳定性和可靠性而无须考虑节点 的能量问题。 ( 3 ) 负载节点复杂，干扰大 低压电力线是一种负载的传输媒介，线上的负载节点多而复杂，易产生负载不均衡。 7 第二章p l c s n 概述及路由算法 此外电力线存在较大的噪声干扰，使信道具有很大频率选择性并随着时间的变化而变 化，从而导致信号的严重衰减和通信链路的不稳定，影响着通信的质量。如何在干扰严 重，信道时变的电力线上稳定准确地传输数据是低压电力载波传感器网络中需要解决的 问题。 ( 4 ) 网络拓扑结构复杂 电力载波传感器网络是由电力线和各种不同性质的负载节点( 网关节点、中继节点、 终端节点) 组成的。负载节点的随机加入和退出会导致某部分的通信逻辑链路中断，使 网络拓扑结构动态的变化并具有一定未知性。网络上的负载节点复杂多变，信道的时变 性和干扰决定了电力载波传感器网络拓扑结构的不稳定和复杂多变。 ( 5 ) 自组织且节点通信距离有限 与无线自组网相似，电力载波传感器网络也具有自组织的特性。此外，在信号的传 输过程中，由于信道的损耗、噪声和时变性导致信号的严重衰减，使得节点间通信距离 非常有限。一般而言，节点通信距离越大信号的衰减越厉害。因此在通信的过程中，相 距较远的两个载波节点因信号的衰减而无法直接通信，需要进行多跳中继才能实现通 信。如图2 3 所示，节点a 与e 进行通信，当信号发送功率足够大或信道状态良好时， 节点a 、e 可以直接通信，即路径0 。否则可以通过节点b 、c 、d 进行多跳中继，路径 l 、2 、3 均可到达节点e ，需要说明的是不同路径可能通信时其效果是不同，由于信道 不稳定有可能在路径2 无效时，路径l 、3 却能良好地通信。 图2 - 3 节点a 与e 的不同通信路径 f i 9 2 - 3 d i f f e r e n tp a t h sf r o mn o d eat oe 由以上所分析的网络特点可以看出，要提高整个网络通信的可靠性和稳定性，需要 确定一种高效的通信策略，自适应且动态的建立有效路由并及时维护传输路径，以保证 数据的传输准确性和稳定性，提高网络的可靠性能，这也是电力载波传感器网络路由算 法设计的所需重点解决的问题。 8 中国石油大学( 华东) 硕士学位论文 2 2 p l c s n 网络路由分析 网络路由是实现源节点和目的节点的路径选择并进行信息交互的过程。在电力载波 传感器网络中，由于网络负载节点的复杂和信道的时变性决定了网络的拓扑结构复杂且 具有时变性。并且，节点间有效通信距离( e f f e c t i v ec o m m u n i c a t i o nd i s t a n c e ，e c d ) 是 有限，网关节点向较远终端节点发送数据时通常需要中继节点的辅助。如何进行中继节 点和路径的选择，准确地转发数据和维护路径时p l c s n 路由算法的重要内容。在此之 前，简单介绍一下p l c s n 的网络拓扑结构。 2 2 1p l c s n 的拓扑结构 电力载波传感器网络中节点的连通性构成了网络的拓扑结构【1 9 1 ，一般采用图的表达 方式。在拓扑图中，每个顶点代表一个载波节点，每条边代表节点间的逻辑通信链路， 表明节点能进行直接的通信。 理想情况下，载波节点使用都是相同的通信资源且线路唯一，因此p l c s n 的网络 拓扑结构是单一的总线型拓扑，路由简单，如图2 4 所示。 图2 - - 4p l c s n 理想的逻辑拓扑结构 f i 9 2 - 4 a ni d e a ll o g i ct o p o l o g yo fp l c s n 一般情况下，电力线存在许多接线分支，如图2 1 所示，网络的拓扑结构不再是简 单的总线型拓扑，而是典型树状结构。随着分支的增多和总线分裂加剧，其网络拓扑结 构会变得更加复杂，甚至会从一棵树转变为一个图。在此将着重讨论一下树状的拓扑结 构，基于树形的电力载波传感器网络拓扑结构，是一种便于扩展且路由相对简单的拓扑 结构，数据沿着树的路径进行传输。如图2 5 所示，当网关节点与节点3 通信时需要节 点l 和1 2 的中继转发，随着有效通信距离的增大或信道状态愈加良好，网关节点极有 可能和节点3 直接通信。相反，当信道状态恶劣有效通信距离下降时，网关节点可能无 法与节点3 通信，这就出现节点不可达的现象，即孤岛问题。 9 第二章p l c s n 概述及路由算法 图2 5p l c s n 典型的逻辑拓扑结构 f i 9 2 - 5 a t y p i c a ll o g i ct o p o l o g yo fp l c s n 此外，电力载波传感器网络中信道随时间剧烈变化、噪声干扰，其载波节点随机的 加入和退出，尤其发挥中继作用的节点，也会使网络的拓扑结构发生重大的变化，而且 变化的速度和方式都是难以预测的。如：在网络运行时，载波节点l 突然从链路上脱离 或失效，导致网关节点与2 、1 2 和1 1 等节点链路的中断，出现暂时无法通信的情况， 降低了网络的性能。此时网关节点将重新发起路由，选择节点2 或者5 、6 作为中继节 点，建立新的拓扑结构保证节点间的稳定通信。 2 2 2p l c s n 路由的意义 在数据通信网络中，根据某种标准、应用要求或是考虑某些因素设计出合理高效的 路由协议能快速建立高效的通信路径并加以维护，从而提高了网络的通信性能。对于电 力载波传感器网络而言，由于网络的逻辑拓扑结构复杂，载波节点的随机加入和退出导 致通信链路的中断，使拓扑结构时常发生变化，具有与无线自组网相类似的特点。另外， 因信号衰减和噪声干扰使得载波节点间的通信距离非常有限，需要中继的辅助。因此， 路由协议是电力载波传感器网络不可缺少的一部分。 在设计电力载波传感器网络路由算法时，拓扑结构的时变性和复杂性，负载的多样 性和随机性，都是必须充分考虑的因素。合理高效的路由算法能降低p l c s n 中时变的 信道造成通信链路不稳定甚至中断所造成的影响；能在复杂的网络拓扑结构中动态地建 立有效的通信路由，减少组网时延，提高通信的有效性：能在节点失效或加入造成网络 拓扑发生变化时及时地维护路由，降低网络的维护开销，保证数据传输的准确性和稳定 性。 综上，合理高效路由算法的设计和研究对电力载波传感器网络有着十分重要的意 义。而一般的自组网和计算机网络的路由协议并不能很好的适用于电力载波传感器网 1 0 中国石油大学( 华东) 硕士学位论文 络。因此，需要在借鉴、研究的基础上设计出新的路由协议，以符合p l c s n 的特点和 用户的要求，是p l c s n 具有良好网络性能。 2 2 3p l c s n 路由算法特点 通过对网络拓扑结构的分析，并结合p l c s n 与无线自组网或传感器网络的相似点，如： 拓扑结构的快速变化、载波节点的处理能力和存储能力有限、网络规模可扩展性要求高， 路由过程中要求开销尽量小。因此，p l c s n 中的路由算法应具有以下特点n 蝴1 ： ( 1 ) 具有中继能力。p l c s n 中节点间的有效通信距离是有限的，这也是p l c s n 区别于其 他传统网络的一个重要方面。为了使更远更多的节点参与通信，设计路由算法应 具有中继转发的功能 ( 2 ) 具有动态自适应能力。鉴于p l c s n 网络特点，采用静态的路由方式是不可行的。 只有动态自适应的路由方式才能适应快速变化的网络拓扑结构。 ( 3 ) 路由开销小。当网络拓扑发生变化时，根据网络状态、动态调整路由算法及其参 数，从而提高网络的吞吐量。设计算法时应当尽量降低算法的复杂度减少节点的 计算开销，避免因节点处理能力有限出现网络的瓶颈问题。 ( 4 ) 无环路。路由无环路、避免造成有限带宽的浪费，严重影响路由协议的性能。 ( 5 ) 具有可扩展性。随着网络规模的扩大，要求算法具有一定灵活性和可扩展性，这 样才能满足网络的应用需求。 p l c s n 路由算法中，当载波节点间的链路中断，拓扑结构发生变化时，需要以最快的 速度重新调整路由，通常使用局部修复。在保持路由连通的情况下，减少路由开销缩短 路由修复的时间。当拓扑结构动态变化十分剧烈时，只能重新通过洪泛来实现路由。 第_ 二章p l c s n 概述及路由算法 2 3 典型自组织路由算法 2 3 1 路由协议分类 d s r 、s s r 、 a v 、1 d r 嘲y 、r p 、 陌r 图2 - 6 路由协议分类 r i g , 2 - 6c l a r i f yo fr o u t i n gp r o t o c o l 在自组织网络中，按照不同标准路由协议有着不同的分类方式【2 3 1 。按照触发的原理， 即路由建立的方式路由协议可分为：表驱动路由( 先应式) 、按需路由和混合路由三种； 按照逻辑结构可以分为：平面路由和层次路由两种协议；按照网络规模的不同，可以划 分了小、中规模和大规模路由协议；根据地理位置信息可分为：地理位置信息路由和非 地理位置信息路由协议；根据接收的目的节点数量可划分为：单播路由和多播路由协议。 除此以外，还有其他类型的路由协议，如：q o s 路由协议、功率感知路由协议等。下面 将介绍几类典型的路由协议算法。 2 3 2 表驱动路由 在表驱动路由中，每个节点无论是否通信，均要维护一张或多张的路由表，节点通 过周期性广播交换路由信息，主动发现路由，并进行周期性的更新、维护，以保证路由 信息的准确、及时。这类协议会不停检测网络拓扑的变化及链路的中断，所以通信开销 相对较大。一般有：d s d v ( 目的节点序列号距离矢量) 、w r p ( 无线路由协议) 、o l s r ( 最优链路状态路由) 、s t a r ( 源树自适应路由) 、t b r p f ( 基于逆向路径转发的拓扑 分发) 。 ( 1 ) d s d v d s d v 3 3 1 是从传统b e l l m a n f o r d 算法改进而来的，利用目的节点序列号避免了路由 环路的产生。在运行的过程中，每个节点保存一个路由表维护该节点到其他节点的跳数 和序列号等信息。序列号用于区分新旧路由的。为了维护路由及时更新信息，节点周期 1 2 中国石油大学( 华东) 硕士学位论文 性向邻居节点广播分组，接收节点将收到的每个目的节点的序列号与自身路由表中到该 目的节点的序列号进行比较，如果新的序列号较高，则接收节点更新自身的路由信息， 如果相同则选择跳数少的路由更新路由表，同时转发自身的路由表信息分组。路由表更 新方式有两种：全表更新与局部更新，当网络拓扑结构快速变化时，选择前者。反之， 网络拓扑结构相对稳定时选择局部更新。 与传统协议相比，d s d v 最大的优势就是利用序列号解决了算法中路由环路问题。 一般情况下，其收敛性能比较快，随着拓扑变化的加剧，收敛性能将会下降。此外无论 网络是否存在通信发送数据，d s d v 均要周期性广播更新信息，随着网络的节点增多， 路由开销和带宽将增大，在节点高速移动时，d s d v 协议的性能将急剧恶化；最后d s d v 只支持双向链路，这也影响其在网络的使用程度。 ( 2 ) o l s r o l s r 2 羽，最优链路状态路由，是为了适应自组网的需求由纯链路状态算法优化而 来的。o l s r 协议采用了多点中继机制缩小了控制分组的洪泛范围及其大小，继承了链 路状态算法的稳定性。多点中继机制减少了同一区域冗余重传信息。 当o l s r 协议进行洪泛时，节点从它的邻节点中选择一部分作为它的多点中继节点 ( m p r ) 并将它们记录在m p rs e l e c t o r 中，其他节点作为非m p r 节点。只有m p r 节 点才能转发控制分组，非m p r 节点只进行处理。这样，网络中控制分组的数量大大地 减少了。而在信息发布时，由于只需发布节点与m p r 间的链路信息缩减了控制分组的 大小。一个节点发送控制分组可以经过m p r 转发到两跳以外的节点处，而作为m p r 节 点需要周期性地在其控制分组中广播该信息和链路状态。在o l s r 协议中，m p r 集越 小，控制传输开销就越低，协议的性能就越好。 此外，o l s r 协议转发控制分组时不要求可靠性，节点会周期性的广播控制分组信 息，在这种情况下协议允许出现控制分组的丢失。同时，在o l s r 协议中可以通过缩短 周期性发送控制消息的最大间隔时间来改善对拓扑变化的反应。节点周期性地与其他节 点交换拓扑的信息，维护着到达网络所有节点的路由信息，一旦网络中需要通信，可以 立即获得路由。与传统的协议相比，当网络的规模越多，节点密度越高时，m p r 优化 的效果越佳，协议的性能就越好。 ( 3 ) s 嗽 s t a r 协议阴】是以最小开销算法( l o r a ) 为节点更新路由的原则，而不是最佳算 法。因此，协议在建立路径后并不需维护最佳路由，它允许使用次优的路径。在s t a r 1 3 第二章p l c s n 概述及路由算法 协议中使用路由树进行路由信息的存储，该路由树是以源节点作为根节点，称为“源树”， 当链路中断、新节点加入或网络拓扑结构发生变换导致出现路由环路时主动向相应的节 点发送更新控制信息，而并不要求周期性的检测和维护路由，从而大大减低了控制开销。 “源树保存着节点n 到目的节点的所有链路信息。节点n 以“源树 的方式向 其邻节点传递更新信息。邻节点接收到信息后将其自身与邻节点的链路信息添加到该 “源树 信息组成了“部分拓扑图 ，并通过低层协议或侦听的方式来检查自身与邻节 点之间的链路状态。当发现某段链路无效时，从拓