（计算机应用技术专业论文）电力载波传感器网络拓扑动态发现算法及应用.pdf

摘要 电力载波传感器网络采用低压电力线作为物理传输信道，通信信道的时变性、噪声 干扰强及信号衰减大等固有特点易造成网络链路不稳定、拓扑结构复杂。网络运行时， 某些节点容易失效或从数据链路上脱离，不能连接到网络中，从而导致网络的连通性遭 到破坏，严重降低了网络的通信可靠性。因此，需要设计适用于电力载波传感器网络的 拓扑动态发现算法，及时调整中继节点，自动实现网络拓扑的生成。 鉴于电力载波传感器网络的特点，采用基于智能优化算法的拓扑发现算法对网络 进行拓扑发现。蚁群算法计算简单，适用于解决动态问题，对网络拓扑结构的变化有良 好的适应性，并且能够在尽可能短的时间内找到新的路径。因此，结合网络信道的时变 和延时特性，在改进的蚁群算法中采用网络链路的端到端传输时延作为优化目标，设计 基于获得最小传输时延的优化目标函数，同时，将反映信道衰减特性的参数加入状态转 移概率公式中，提出基于改进蚁群算法的拓扑动态发现算法( d y n a m i ct o p o l o g y d i s c o v e r ya l g o r i t h mb a s e d o ni m p r o v e d a n tc o l o n ya l g o r i t h m ，i a c a - d t d ) 。从图论拓扑 结构上对网络进行分析，利用g - 代e ) 描述网络的拓扑结构，用图的一棵以中心节点为 根的最小生成树表示网络中节点的最优连通情况。这样，对于网络的拓扑发现问题即可 转化为通过蚂蚁的选路以寻优策略生成图的最小生成树问题，并与广度优先搜索思想结 合，以保证生成树的连通性。在m a t l a b 中对i a c a d t d 算法进行仿真，实验结果表明， i a c a d t d 算法减小了网络平均链路长度和端到端传输时延，增强了链路的稳定性，提 高了网络通信的可靠性。最后，将i a c a d t d 算法的思想和方法应用于电力载波抄表 系统中，通过理论分析推导出该算法可以完成系统的拓扑构建。 关键词：电力载波传感器网络，蚁群算法，拓扑发现算法，最小生成树 d y n a m i ct o p o l o g yd i s c o v e r ya l g o r i t h ma n da p p l i c a t i o no f 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 c h ud a n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) 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 l o w v o l t a g ep o w e rl i n ei su s e da sap h y s i c a lt r a n s m i s s i o nc h a n n e li np o w e rl i n ec a r r i e r s e n s o rn e t w o r k ( p l c s n ) i th a st i m e v a r y i n g ，s t r o n gn o i s ei n t e r f e r e n c ea n ds i g n a la a e n u a t i o n c h a r a c t e r i s t i c s t h a tc a r lc a u s el i n ki n s t a b i l i t ya n dc o m p l e xt o p o l o g yi nn e t w o r k s o m en o d e s m a yb ei n v a l i d a t eo rl e a v eo f f t h ed a t al i n k i tw i l ll e a dt od a m a g en e t w o r kc o n n e c t i v i t ya n d r e d u c en e t w o r kc o m m u n i c a t i o nr e l i a b i l i t y s oi ti sn e c e s s a r yt od e s i g nd y n a m i ct o p o l o g y d i s c o v e r ya l g o r i t h mo fp o w e rl i n ec a r r i e rs e n s o rn e t w o r kt oa d j u s tr e l a yn o d ea n di m p l e m e n t n e t w o r kt o p o l o g ya u t o m a t i c a l l y g i v e n 弱t h ec h a r a c t e r i s t i c so fp o w e rl i n ec a r t i e rs e n s o rn e t w o r k ，t o p o l o g yd i s c o v e r y a l g o r i t h mb a s e do ni n t e l l i g e n to p t i m i z a t i o na l g o r i t h mi sa d o p t e d a n tc o l o n ya l g o r i t h mi s s i m p l ea n da p p l i c a b l et os o l v i n gt h ed y n a m i cp r o b l e m i th a sg o o da d a p t a b i l i t yt on e t w o r k t o p o l o g ys t r u c t u r ec h a n g e sa n df i n d san e wp a t hi ns h o r tt i m e t h e r e f o r e ，e n d - t o e n dl i n k d e l a yi su s e da st h eo p t i m i z a t i o no b j e c t i v ea n d t h em i n i m u mt r a n s m i s s i o nd e l a yo p t i m i z a t i o n o b j e c t i v ef u n c t i o ni s d e s i g n e di ni m p r o v e da n tc o l o n ya l g o r i t h m a tt h es a m et i m e ，t h e a t t e n u a t i o nc h a r a c t e r i s t i c so ft h ec h a n n e lp a r a m e t e r sa r ea d d e di nt h es t a t u st r a n s i t i o n p r o b a b i l i t yf o r m u l a d y n a m i ct o p o l o g yd i s c o v e r ya l g o r i t h mb a s e do ni m p r o v e da n tc o l o n y a l g o r i t h mi sp r o p o s e d t h en e t w o r kt o p o l o g ys t r u c t u r ei sa n a l y z e df r o mg r a p ht h e o r y g2 ( v e ) i su s e dt od e s c r i b et h en e t w o r kt o p o l o g y t h em i n i m u ms p a n n i n gt r e ew h i c ha d o p t sa c e n _ c r a ln o d ea sr o o ti su s e df o rt h eb e s tc i r c u m s t a n c eo fn o d e si nn e t w o r k t h e n ，t h en e t w o r k t o p o l o g yd i s c o v e r yi s s u ei sc h a n g e di n t ot h em i n i m u ms p a n n i n gt r e eo fm a pb yo p t i m i z a t i o n s t r a t e g yw h i c hb a s e do na n t s e l e c t i o nr o a d s m o r e o v e r , t h ei d e ao fd e p t h - f i r s ts e a r c hi s c o m b i n e dw i t ht oe n s u r et h ec o n n e c t i v i t yo ft r e e al o to fs i m u l a t i o ne x p e r i m e n t so f i a c a 。d t da l g o r i t h mu n d e rm a t l a b s i m u l a t i o ni n d i c a t e st h a tt h i sa l g o r i t h mr e d u c e st h e a v e r a g el i n kl e n g t ha n d t h ea v e r a g ee n d - t o e n dd e l a y , e n h a n c e st h el i n ks t a b i l i t ya n di m p r o v e s t h en e t w o r kc o m m u n i c a t i o nr e l i a b i l i t y f i n a l l y , t h ei d e a sa n dm e t h o d so fi a c a - d t d a l g o r i t h mi sa p p l i e dt op o w e rl i n ec a r r i e rm e t e rr e a d i n gs y s t e m t h i sa l g o r i t h mc a nc o m p l e t e b u i l d i n gas y s t e mt o p o l o g yt h r o u g ht h e o r e t i c a la n a l y s i s k e yw o r d s ：p 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 ( p l c s n ) ，a n tc o l o n ya l g o r i t h m ， t o p o l o g yd i s c o v e r ya l g o r i t h m ，m i n i m u ms p a n n i n gt r e e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：歪盘盘 同期：2 。7 年4 月6 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部f - j ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：遮墨 指导教师签名： 4 - 月 归 6 e t 易日 k呱 纱 期 期 同 r 中国石油大学( 华东) 硕士学位论文 1 1 课题背景及意义 第一章前言 现代通讯技术、电子技术、传感技术及微电子系统的进步推动了电力载波传感器网 络( p o w e rl i n ec a r r i e rs e n s o r n e t w o r k ，p l c s n ) 的研究及应用。电力载波传感器网络 是以低压电力线作为物理传输通道，以传感器作为信息的发送和接收节点，以载波调制 方式来传输分布区域内的信息，并对信息中的相关数据进行处理，使用户获得更准确的 信息的一种新型传感器网络；是利用现有电力线路作为通信信道，不需要额外线路投资 的有线通信传感器网络。 低压电力线是目前最为普遍也是覆盖最为宽广的一种通信媒介，只要有电使用的地 方就可以有电力线网络。电力载波传感器网络克服了以传统传输介质如双绞线、同轴电 缆等需要重新布线的缺点，同时，不存在无线传感器网络中能量资源非常有限的问题， 具有成本低、实用方便等优点。利用现有的低压电力线作为传输介质实现数据通信，不 需要铺设额外的通信线路而直接利用已有的电力线资源进行数据或话音信号的传输，将 会大大地降低成本，简化了通信设备线路及整个网络的布局，迎合了目前通信领域解决 频带资源短缺的发展需求，开拓了新的通信信道承载资源。我国拥有世界长度排名第二 的电力输电线路，若利用现有的电力线网络进行通信，会对我国传感器网络的发展带来 很大的空间。然而，由于电力线通信信道的时变性、噪声干扰强及信号衰减大等固有特 点易造成链路不稳定、网络拓扑结构复杂，严重降低了电力载波传感器网络的通信可靠 性。因此，解决网络中通信信道的稳定性，保证网络通信的可靠性，并兼容现有应用平 台，是电力载波传感器网络研究中极具挑战性的一个课题。 为了解决网络通信的可靠性问题可以从网络拓扑发现的角度设计合理的拓扑发现 算法来保证网络的连通性。电力载波传感器网络的拓扑结构是动态变化的，在网络运行 时，某些节点容易失效或从数据链路上脱离，不能连接到网络中，从而导致网络的连通 性遭到破坏。因此，有必要采用网络拓扑发现算法，调整中继节点，自动实现网络拓扑 的生成。为了提高网络的稳定性，就需要动态处理这些问题，但是由于电力载波传感器 网络拓扑结构的动态变化和复杂性，传统的网络拓扑发现算法并不能完全适用于这种网 络。因此，需要研究适用于这种网络的、面向具体应用的、高效的拓扑动态发现算法， 从而从整体上改善整个网络的性能和效率，使电力载波传感器网络能够得到更广泛的应 第一章前言 用。 蚁群算法【2 】( a n tc o l o n ya l g o r i t h m ，a c a ) ，是受自然界蚂蚁觅食行为启发得到的随 机优化算法，目前已被广泛应用于网络路由、电力系统、故障诊断等方面。对网络拓扑 结构的变化具有良好的适应性，并能在尽可能短的时问内找到新的路径，比较适用于解 决动态问题，而且算法的实现比较简单。因此，结合低压电力线通信信道的具体特点， 考虑信号传输的衰减和延时特性，从优化目标函数和状态转移概率两方面改进基本蚁群 算法，并将改进后的蚁群算法应用于电力载波传感器网络的拓扑发现算法中，以达到当 网络拓扑结构发生变化时能有效地保证网络通信可靠性的目的。 1 2 国内外研究现状 随着网络规模的发展，人们开始对网络拓扑自动发现进行研究。网络拓扑发现需要 深入到网络体系结构的各个层次，涉及众多的网络协议。目前，常用的网络拓扑发现算 法主要有适用于计算机网络的基于s n m p 、o s p f 等协议的拓扑发现算法；适用于无线 传感器网络的基于邻近图、节点度的拓扑控制算法及l e a c h 算法、t o pd i s c 算法等； 以及适用于a dh o e 网络的基于o l s r 、a o d v 等协议的拓扑发现算法。 文献 3 对低压电力线载波通信网络的拓扑结构和特性进行分析，提出需要设计合 适的高层通信协议的观点。文中通过对低压电力线载波特殊性的研究，指出该网络的拓 扑结构是一个复杂的具有强时变性的有向图，传统的总线监听方案在该网络中也将失 效。文中总结了电力线通信网络总线分裂和动态路由的思想，提出必须采用一个全新的 具有很强自适应能力的网络协议才能满足低压电力线载波通信网络的需要。但并没有提 出有效的网络协议，也没有设计出具有自适应能力的网络拓扑发现算法。 鉴于电力载波传感器网络的特点，传统的网络拓扑发现算法并不能完全适用于这种 网络。很多专家学者开始探讨采用智能优化算法来进行网络拓扑发现。 蚁群算法是一种求解组合最优问题的内启发式方法，本质上是一个多代理算法，通 过单个代理之间的低级交互形成整个蚁群的复杂行为。蚂蚁本质上就是简单的携带经过 节点信息的智能代理。 基于移动代理的拓扑发现的最初策略是由m i tm e d i al a b 4 1 提出的，它的主要思路 就是利用移动代理为每个网络节点尽可能地收集与拓扑有关的信息，并通过移动代理进 行定期的分发和更新。但是该策略在移动代理的漫游策略中没有考虑节点所掌握的当前 网络拓扑信息量。 2 中国石油大学( 华东) 硕士学位论文 文献 5 】采用一种基于新的目标基的启发式信息分配技术，提出了加速蚁群算法 ( a c c e l e r a t e da n tc o l o n ya l g o r i t h m ，a a c a ) ，采用译码技术，使复杂非线性优化问题转 化为导向图搜索问题，提高了收敛性，更易获得全局最优解。但文中只以单纯的数学优 化作检验，而没有应用在具体的网络规划中。 j u s t i n b r o w n t 6 】等分析了电力载波通信的特点及目前的应用，指出该网络的拓扑模型 是基于树型的拓扑结构，并在此基础上提出基于蚁群算法和d i j k s t r a 算法的两种网络拓 扑发现算法。文中假设网络中一定范围内的每一节点都可以与周围的节点通信，指出将 蚁群算法应用与电力线网络进行拓扑发现，可以通过蚂蚁的遍历发现节点间的连接情 况，得到网络拓扑结构图。但是由于电力线信道的衰减等特性，文中提出的算法仅适用 于很小范围的节点通信，仍不能有效解决远距离通信节点之间的信息反馈情况。 刘晓胜【_ 7 】等指出低压电力线网络具有物理拓扑未知和电力线信道时变的特性。为了 提高低压电力网窄带电力载波通信系统的可靠性，提出了一种适用于未知电力线拓扑结 构条件下的蚁群电力线组网方法。该方法利用蚁群算法的启发式最优路由搜索，不仅保 证了电力线通信网络组网的成功建立，而且可以在低压配电网信道条件发生变化时，提 高网络通信的自愈性和可靠性。但这种算法存在组网耗时，容易导致延时。 总之，国内外越来越多的研究人员致力于网络拓扑发现算法的研究，关于将网络拓 扑动态发现算法应用到电力载波传感器网络中的研究尚处于探索阶段，很多相关理论的 提出还有待完善。目前，将蚁群算法应用于电网规划，对算法中收敛时间的处理、搜索 方向的确定、各元素转换概率的选取等都有待进一步的研究探讨。可以将改进后的蚁群 算法应用于电力载波传感器网络中，保证通信信道的稳定性，维持网络通信的可靠性。 1 3 研究内容与方法 为了提高电力载波传感器网络的通信可靠性，从图论拓扑结构上对网络进行分析， 将网络拓扑发现问题转化为通过蚂蚁以寻优策略选择最优路径生成图的最小生成树问 题，并与广度优先搜索的思想结合，以保证得到树的连通性。考虑电力线信道的衰减与 链路的信息素浓度来计算蚁群算法中的状态转移概率，以保证当网络拓扑发生变化时探 测蚂蚁能够及时地选择最优链路。同时，采用网络中链路的端到端传输时延作为优化目 标，可以减少网络平均链路长度和端到端的数据传输时延，从而增强网络中链路的稳定 性，保证网络的通信可靠性。基于以上思路，整个论文主要展开以下几个方面的研究工 作： 3 第一章前言 ( 1 ) 从理论上介绍了电力载波传感器网络的构成及特点，并从图论拓扑结构上对网 络进行分析，介绍对网络进行拓扑发现的意义。 ( 2 ) 研究适用于计算机网络、无线传感器网络、a dh o c 网络的几种典型的网络拓 扑发现算法，并结合电力载波传感器网络的特点分析这几种算法对电力载波传感器网络 的适用性及优缺点。 ( 3 ) 分析蚁群算法的基本原理、数学模型、涉及的参数及算法的实现，总结蚁群算 法应用于电力载波传感器网络的优越性和不足，结合电力载波传感器网络信道的特性， 对蚁群算法中的优化目标函数及状态转移概率公式进行改进。 ( 4 ) 提出基于改进蚁群算法的拓扑动态发现算法( i a c a d t d ) ，介绍算法涉及的 基本概念，研究算法的基本思想及具体实现过程。通过m a t l a b 实现电力载波传感器网 络i a c a d t d 算法，建立适当的模型进行相应的模拟实验，并将i a c a d t d 算法与其 它算法进行分析比较。 ( 5 ) 将电力载波传感器网络i a c a d t d 算法应用于电力载波抄表系统中，结合该 算法的思想及方法，通过理论分析构建出系统拓扑结构图。 1 4 论文的组织结构 全文共分为六章，各章的内容如下： 第一章为前言，介绍课题产生的背景及意义、研究现状、给出课题研究的主要内容 及研究方法。 第二章为p l c s n 及拓扑分析，介绍电力载波传感器网络的构成、特点及拓扑结构， 从图论拓扑结构上对网络进行分析，并概括对网络进行拓扑发现的意义。同时，分析几 种典型的网络拓扑发现算法对电力载波传感器网络的适用性。 第三章为蚁群算法的研究与改进，研究蚁群算法的原理、数学模型及实现，分析算 法中的参数，结合网络的信道特性，对蚁群算法中的优化目标函数及状态转移概率公式 进行改进。 第四章为基于改进蚁群算法的拓扑动态发现算法，首先介绍i a c a d t d 算法涉及 到关于图、广度优先搜索、最小生成树的基本概念，在此基础上，给出算法的基本思想 及算法的具体实现步骤。最后，用m a u a b 对算法进行仿真，分析仿真结果，验证算法 的性能。 第五章为i a c a d t d 算法在电力载波抄表系统中的应用，介绍电力载波抄表系统 4 中国石油大学( 华东) 硕士学位论文 的结构及功能特点，指出系统存在的问题，将i a c a d t d 算法应用于系统中，并通过 理论分析构建系统拓扑结构图。 最后为总结与展望，总结全文及创新点，并指出进一步研究的方向。 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 构成 低压电力载波传感器网络主要由中心节点( c e n t r a ln o d e 、中继节点( r e l a yn o d e ) 和终端节点( t e r m i n a ln o d e ) 组成f 9 ，埘。网络以中心节点为中心，电力线可以视为有多 路分支的总线，终端节点无规律的接入在总线的某个位置上。在实际应用中并不要求任 意两个终端节点进行数据传输，而只要求中心节点与每一个终端节点进行通讯，在终端 节点与中心节点距离较远时可能由于通信信号的衰减或受干扰而无法直接通讯，这时需 要在中心节点与终端节点之间加入中继节点来进行数据转发，完成数据传输。图2 1 表 示了低压电力载波传感器网络的一个典型的系统结构图。 图2 1 低压电力载波传感器网络结构 f i g z - 1 a r c h i t e c t u r eo fp o w e rl i n ec a r r i e r $ e i i s o rn e t w o r k 6 中国石油大学( 华东) 硕士学位论文 如图2 1 ，中心节点和终端节点3 之间加入中继节点3 ，当中心节点与终端节点3 无法直接通信时就利用中继节点3 转发中心节点与终端节点3 的数据包，以实现中心节 点与终端节点3 之间的数据通信。当中心节点与终端节点距离更远时可能必须经过多级 中继的转发，如中心节点与终端节点4 可能要经过中继节点3 和4 的转发才能进行数据 通信。同时由于分支复杂，某一个中继节点可能会有多个下一级中继，如图，中继节点 3 拥有下一级中继4 和5 ，这样中继节点和中心节点在结构上形成多级的树状结构。 其中，与中心节点较远的终端节点并不是每次通信都要进行数据包转发，例如，在 实际应用中，终端节点3 和中心节点在用电低谷期可以进行可靠的数据包传输，而在用 电高峰期则不得不经过中继节点3 转发，甚至终端节点4 和终端节点5 也可能出现类似 的情况，也就是说某一个终端节点在线路状况良好的情况下可以跨过一级或多级中继进 行数据包传输。 2 1 2p l c s n 分层结构 考虑电力载波传感器网络的数据传输特点，结合实际应用需要，根据国际标准化组 织i s o ( i n t e m a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n ) 的o s i ( o p e ns y s t e m i n t e r c o n n e c t i o n r e f e r e n c em o d e l ) 参考模型，将电力载波传感器网络的体系结构分为五 层抽象结构，由低到高依次为物理层、低压线路链路层、低压线路网络层、低压线路传 输层和应用层，如图2 2 所示： l 应用层 j 低压线路传输层 丫i 低压线路网络层 低压线路链路层 j物理层 应用层t 低压线路传输层t 低压线路网络层! 低压线路链路层i 物理层t l _ l 电啼力一线啼载一波一 图2 - 2 电力载波传感器协议分层 f i 9 2 2 l a y e r so fp o w e rl i n ec a r r i e rs e n s o rn e t w o r k 各层的功能和作用分别为： ( 1 ) 物理层 电力载波传感器网络物理层的设计要根据实际需要而定。以发送和接收信号为主 7 第二章p l c s n 及拓扑分析 要功能的物理层首先要考虑信号的传输介质，电力载波传感器网络是基于低压电力线网 络进行通信的，因此，物理层主要为基于通信模块的硬件和以低压电力线作为数据传输 的媒介。 ( 2 ) 低压线路链路层 低压线路链路层的研究重点是介质访问控 | 行j j ( m e d i u m a c c e s sc o n t r o l ，m a c ) ，m a c 协议的主要功能是在相互竞争的节点之间分配信道资源。电力载波传感器网络链路层主 要定义通讯模块在低压电力线上有效的发送和接收数据流，并保证数据流的正确性。 ( 3 ) 低压线路网络层 低压线路网络层的功能是根据路由协议在网络中任意需要通信的两点间建立并维 护数据传输路径。在网络层中规定如何确定数据包的目标地址，网络中节点数据包如何 发送到另一个节点，如何进行中继节点的选择，如何通过中继节点进行数据包的转发以 及系统如何更新选路信息。 ( 4 ) 低压线路传输层 低压线路传输层的主要功能是负责低压电力线上数据流的传输控制，解决通信节 点之间如何传输数据包等问题。在低压线路网络层的基础上为应用层提供一个可靠的、 高质量的数据传输服务。 ( 5 ) 应用层 应用层主要根据实际需求解决应用的共性问题，以满足用户的需要。 2 1 3p l c s n 特点 决定网络特征的主要技术有3 个：用以传输数据的传输介质，用以连接各种设备的 拓扑结构，用以共享资源的介质控制方法【1 1 】。电力载波传感器网络利用现有的低压配电 网络基础设施，无需任何布线，节约了资源，同时，电力线网络的覆盖范围广，为其应 用发展创造了极大的空间。但是，由于低压电力线不是专用的通讯线路，存在很多用电 设备的影响，与一般的计算机通信网络比较，具有以下特剧1 2 , 1 3 】： ( 1 ) 信道的阻抗随时间变化 电力线上负载的随机接入、切出等，使得电力线路的阻抗随时间、频率呈动态变化， 从而造成网络中各设备节点( 中心节点、中继节点、终端节点) 之间传输数据时阻抗无 法与线路匹配，线路信号衰减，直接影响传输质量。 ( 2 ) 信道的噪声干扰 8 中国石油大学( 华东) 硕士学位论文 电力线信道噪声特性较为复杂，与负载特性、时间范围和测量频段均有关。由于噪 声干扰可能会降低通信过程中的信噪比，导致误码率变大，影响通信质量。 ( 3 ) 信道衰减严重 网络接入节点的随机变化以及信道存在许多阻抗不匹配等问题，必然会造成信号 的多径传播，同一信号由不同路径传播时会造成不同的延时，从而造成衰减。 ( 4 ) 传输的质量随时间变化 由于干扰、衰减和线路阻抗是动态变化的，所以不同时间段的传输质量有很大的差 异。同时由于各个季节的用电设备有所不同，所以传输质量具有季节性。 ( 5 ) 节点之间的传输存在不确定性 一般而言，在计算机通信网络上两个节点间的通信存在要么成功要么不能成功两种 比较确定的状态，就低压电力线路上的两个节点而言，其传输的成功与否是随时间变化 的，并会受到信道干扰的影响。 由以上分析可知，要使整个网络达到最高的传输效率，必须确定一种高效的通信策 略使中心节点与终端节点进行数据传输，计算出最优传输路径，这是低压电力载波传感 器网络拓扑发现重点要解决的问题。 2 2p l c s n 拓扑分析 确定一个规模较大且经常变化的网络拓扑结构是很困难的，但准确的拓扑信息在网 络管理方面起着很重要的作用，通过网络拓扑信息我们可以判断当前节点的配置是否合 理，同时也为网络故障的排除提供了重要的依据。网络拓扑发现就是探测网络拓扑结构 信息，形象地描述网络设备间的互连关系。网络拓扑可表示为一张无向图g = ( n ，e ) ， 其中n 是节点集，表示网络中的互连节点，e 是边集，表示网络中节点之间的连接关系。 2 2 1p l c s n 的动态拓扑 在计算机网络领域中，网络拓扑反映了网络节点的几何排列或布局以及网络节点之 间的连接关系，可以划分为物理拓扑和逻辑拓扑。电力载波传感器网络的运行特点决定 了由于网络通信节点自身的变化和信道的变化而引起网络拓扑结构变化的特性。 从通信角度讲，电力载波传感器网络是基于树形的拓扑结构，具有未知、时变及 多样等特性【7 1 。本文采用图g = ，e ) 描述电力载波传感器网络的拓扑结构，其中，v 是 网络中一组节点的集合，每个节点i 表示一个传感器节点；e 是一组边的集合，每条边 9 第二章p l c s n 及拓扑分析 e i j 表示网络中节点间的通信链路。由于电力线上负载的随机动态变化，致使信道具有随 机动态变化的特性，在网络运行时，某些节点容易失效或从数据链路上脱离，不能连接 到网络中，从而导致原有的网络拓扑结构发生变化，连通性遭到破坏，降低了网络通信 的可靠性。如图2 2 所示： 图2 2 逻辑结构变化对电力载波传感器网络的影响 f i 9 2 - 2 t h ea f f e c t i o no np l c s nd u et ot h ec h a n g i n go fl o g i c a lt o p o l o g y 为了及时发现网络变化，调整链路中继节点，需要高效的网络拓扑发现算法来发现 和调整路由，生成新的网络拓扑，从而保证网络的健壮性和适应性，并兼容现有应用平 台，以较低的成本提高通信的可靠性【1 针。 2 2 2p l c s n 拓扑发现的意义 网络拓扑发现的主要目的是获取和维护网络节点的存在信息和它们之间的连接关 系信息，并在此基础上绘制出整个网络拓扑图，它是网络管理平台的一项重要功能。在 电力载波传感器网络中，传感器节点是体积微小的嵌入式设备，它的计算能力和通信能 力十分有限。因此，设计优化的网络拓扑发现算法有着十分重要的意义，主要表现在以 下几个方面： ( 1 ) 减小节点间通信干扰，提高网络通信效率 电力载波传感器网络以低压电力线作为传输信道，干扰大，会影响网络中节点之间 的通信效率和网络的连通性，通过优化的拓扑发现算法可以提高网络的通信效率。 ( 2 ) 为路由协议提供基础 在传感器网络中，只有活动的节点才能进行数据转发，而拓扑发现算法可以确定由 哪些节点作为转发节点，同时确定节点之间的邻居关系。 ( 3 ) 弥补节点失效的影响 1 0 中国石油大学( 华东) 硕士学位论文 电力载波传感器网络的拓扑结构是动态变化的，在网络运行时，某些节点不能连接 到网络中，从而导致网络的连通性遭到破坏，采用网络拓扑发现算法，及时调整网络中 继节点，自动实现拓扑的生成。 2 3 几种典型的网络拓扑发现算法 网络拓扑发现算法主要是利用各种网络路由搜索算法和相关协议来获取整个网络 中每个节点的路由信息，然后利用获取的路由信息来自动实现拓扑的生成。实现拓扑发 现的算法有很多种，但就性能和效率而言，判定其优劣的指标参数只有两项：网络负荷 和发现时延【l 引。具体地说，就是算法的实现过程本身不能过多地增加网络流量，同时也 应力求最大限度地减少发现所需的时间，否则就会从整体上影响网络的性能和效率。网 络拓扑自动发现的方法很多，归结起来主要有适用于计算机网络、无线传感器网络及无 线移动自组织网络的拓扑发现算法。分别介绍适用于这三种有代表性网络中的几种较为 典型和常用的拓扑发现算法。 2 3 1 计算机网络拓扑发现算法 在计算机网络中，拓扑反映了网络节点的几何排列或布局以及网络节点之间的连接 关系。网络节点代表网络的基本互连设备，如交换机，路由器等等。网络节点与主机有 区别，主机通常只是指网络中的计算机终端设备。链路将两个网络节点相连，提供它们 之间信息传递的通路。网络拓扑代表网络中直连对等实体( 如路由器或主机) 的相互连 接关系。比较典型的拓扑发现算法主要有以下几种： ( 1 ) 基于s n m p 的拓扑发现算法 简单网络管理协议s n m p t l 7 】( s i m p l en e t w o r km a n a g e m e mp r o t o c 0 1 ) 是计算机网络 中应用最为广泛的网络管理协议。基于s n m p 的拓扑发现算法的主要思想是所有的网络 节点维护一个管理信息库( m i b ) ，从m i b 的缺省路由器开始，读取路由器的路由表， 逐渐向下发现网络中的所有基于路由功能的网络节点，通过路由表的对象端口标识项， 就可以构建出整个网络的拓扑关系图。 该算法是完全基于标准的s n m p 协议实现的，发现过程简单，效率高，系统和网络 开销小，能够得到比较完整的网络关系。但这种算法却无法发现网络中无路由功能的网 络设备节点，而且路由表中包含了大量对拓扑发现来说是冗余的信息。因此，这种方法 主要适用于大型主干网络的拓扑发现，发现网络中的路由设备节点，反应网络的整体拓 第二章p l c s n 及拓扑分析 扑状况。 ( 2 ) 基于a r p 的拓扑发现算法 任何有以太网接口的网络设备节点都必须支持地址解析协议a r p ( a d d r e s s r e s o l u t i o np r o t o c 0 1 ) ，并在本机维护着一张a r p 表，用于i p 地址与以太网地址问的地 址解析和转换。a r p 表包括了响应端口对应网段内的所有网络设备的i p 地址、以太网 地址以及该表项的驻留时间等信息。根据任何一台路由器或交换机的a r p 表，可以发 现与其以太网端口相连的以太局域网中的所有网络设备节点。再根据其它信息判别网络 中的路由器和交换机，并继续根据其a r i a 表进行发现，可以得出整个以太网的拓扑结 构关系。 该算法发现效率较高，a r p 表中的冗余信息较少，但这种算法不能发现哪些不支 持a r p 协议的网络连接和设备节点，因此该算法一般只适用于局域网的拓扑发现。 ( 3 ) d 韬虹溉算法 d i j k s 仃a 算法是最短路径优先协议0 s p f i s 】( o p e ns h o r t e s tp a t hf i r s t ) 的基础。在基 于o s p f 的拓扑发现算法中，定期导出路由器配置文件或o s p f 的链路状态数据库实现 拓扑结构重现，或者使用协议侦听器侦听所有数据包从而分析拓扑结构的变化情况。 d i j k s t r a 算法将每一个路由器作为根来计算其到每一个目的地路由器的距离，每一个路 由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在 d i j k s t r a 算法中，被称为最短路径树。 该算法比较简单，容易实现，但是在实际应用中存在不足，若在网络模型大，结点 数目多的系统中采用d i k s 仃a 算法计算最短路径，其存储空间和计算时间都会相当庞大， 这将直接影响搜索效率。 2 3 2w s n 拓扑发现算法 在无线传感器网络中，一个节点有许多邻节点，如果发射功率足够大，就能实现它 们之间的直接通信。但是，高发射功率需要大量能量，众多邻节点对媒体接入控制协议 来说是负担，而且当节点不断移动，频繁建立或释放大量链接时，路由协议也会遭受到 网络多变性的影响。为了解决这些问题，可以使用拓扑控制，其主要思想是限制给定节 点的邻节点的个数。这可以通过控制发射功率来实现，或引入分层式网络选出某些节点 完成同等的任务，还可以通过在某段时间关掉某些节点来实现。较典型的拓扑控制算法 主要有： 1 2 中国石油大学( 华东) 硕士学位论文 ( 1 ) 基于临近图的算法 基于邻近图的拓扑算法中，所有节点都使用最大功率发射时形成的拓扑图为图g ， 按照一定的规则求出该图的邻近图g ，最后g 中每个节点以自己所邻接的最远通信节 点来确定发射功率。这是一种解决功率分配问题的近似解法【1 9 】。考虑到传感器网络中两 个节点形成的边是有向的，为了避免形成单向边，一般在运用基于邻近图的算法形成网 络拓扑之后，还要进行节点之间的增删，以使最后得到的网络拓扑是双向连通的。 在传感器网络中，基于邻近图的算法的作用是使节点确定自己的邻居集合，调整适 当的发射功率，从而在建立起一个连通网络的同时，达到节省能量的目的。在已有的传 感器网络拓扑算法中，比较完善的有d r n g 算法和d l s s 算法。d r n g 算法和d l s s 算法是两种以邻近图的观点考虑拓扑问题的算法，他们是较早的针对节点发射功率不一 致问题提出的拓扑方案。这两种算法以经典邻近图r n g 、l m s t 等理论为基础，全面考 虑了网络的连通性和双向性问题。 ( 2 ) l e a c h 算法 l e a c h 算法【2 0 】是无线传感器网络中一种经典的自适应分簇路由算法，算法的执行 过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段， 相邻节点动态地形成簇，随机产生簇头；在数据通信阶段，簇内节点把数据发送给簇头， 簇头进行数据融合并把结果发送给汇聚节点。由于簇头需要完成数据融合、与汇聚节点 通信等工作，所以能量消耗大。 l e a c h 算法能够保证各节点等概率地担任簇头，使得网络中的节点相对均衡地消 耗能量。簇头节点担负数据融合的任务，减少了数据通信量；分簇式的拓扑结构有利于 分布式算法的应用，但是由l e a c h 建立的网络拓扑过于简单化，簇内每个节点将采集 的数据直接发送给簇头而不是通过簇内某些节点转发，也就是说，拓扑结构中某些链路 不存在。 ( 3 ) t o p d i s c 算法 利用无线通信的广播性，d b e 等人提出了一种节能的拓扑发现算法【2 1 】( t o pd i s c ) ， 该算法通过监听广播域内的消息，每个节点可获取邻节点的信息。算法首先由一个初始 节点发出拓扑发现请求，通过广播消息逐渐确定网络中的“骨干 节点。只有这些“骨 干”节点响应初始节点发出的拓扑发现请求。结合“骨干 节点所收集的邻节点信息， 初始节点可以近似地构建出整个网络的拓扑结构。 t o pd i s c 算法利用颜色来区分节点状态，解决骨干网络拓扑结构的形成问题。继 1 3 第二章p l c s n 及拓扑分析 承了图论中的经典算法，是早期成簇算法的代表，可以使节点在密集部署的传感器网络 中快速地形成分簇结构，并在簇头之间建立树型关系。但是这种算法建成的网络灵活性 不强，重复执行算法的开销过大，此外，算法也没有考虑节点的剩余能量问题。 2 3 3a dh o c 网络拓扑发现算法 a dh o c 网络是由一组带有无线收发信息装置的移动节点组成的一个无线移动通信 网络，由于无线通信距离受限，自组织网内节点间的通信往往需要借助其它节点中继转 发才能实现。网络中节点间的互相连通性构成了网络的拓扑结构。由于自组织网络中的 节点可以随意移动，加上发射功率的变化，以及无线信道的干扰等因素，节点间通过无 线通信形成的网络拓扑结构可能会随时发生变化。因此，在a dh o c 网络中，采用高效 的网络拓扑发现算法来解决对网络拓扑动态性的适应问题是很有必要的。 ( 1 ) 基于o l s r 的拓扑发现算法 最优化链路状态协议o l s r l 2 5 】( o p t i m i z e dl i n ks t a t er o u t i n g ) 是由i e t f