（计算机应用技术专业论文）基于发射功率调整的无线传感器网络的拓扑控制.pdf

摘要 摘要 无线传感器网络是由大量节点组成的特殊的无线网络，它实现了复杂环境 下的数据感测、收集与分析等功能。无线传感器网络中的节点具有体积小、计 算能力有限、依靠无线电波通讯、电池供电等特点，这些特性决定了无线传感 器网络要在具体环境中以最优的方式工作，还有许多亟待解决的问题。作为无 线传感器网络优化的方法，拓扑控制旨在降低介质访问冲突，限制节点的邻居 数目和减少每次通讯消耗的能量，并最终从整体上改善网络的扩展性、生命期、 能源效率和并发通讯能力等。调整节点信号发射功率和规划节点的睡眠是拓扑 控制中的主要方法。 本文分析了拓扑控制在协议栈中的位置及与其它协议的关系。通过引入概 率性的链路模型和链路质量估计的非确定性，提出了一种利用体现信号接收功 率的r s s i 信息的拓扑控制算法l q a t c 。在本文所描述的研究模型下，l q a t c 算法能够保证网络的连通性，链路的对称性，适当的平均邻居度数，并能够改 进网络能源效率和平均干扰度数等。在此基础上，提出了针对网络生命期的改 进方法l b a - t c 。该方法通过考虑拓扑控制可能带来节点间的转发负载的差别， 利用节点的剩余电量信息或保证最低邻居数目，进一步延长了拓扑控制下的网 络生命期。论文对所提出的各种算法进行了仿真实验，分析了算法中各种参数 对于评价指标的影响，并与其它算法进行了比较。仿真结果表明，l q a t c 在有 限提高网络中节点平均度数的同时，降低了节点的平均干扰度数和网络的路径 能量消耗，l b a t c 算法则在设置有效存活节点比例高于9 0 的条件下，明显延 长了网络的生命期。 关键词：拓扑控制，非确定性链路，链路质量估计，功率配置，网络生命期 a b s t r a c t a b s t r a c t w i r e l e s ss e n s o rn e t w o r k ( w s n ) ，c o n s i s t i n go fm a n yn o d e s 埘t l ll i m i t e dp o w e r a n dw o r k i n gi na dh o cm a n n e r ，i sd e s i g n e dt of i n i s hd a t es e n s i n g ，g a t h e r i n g ，a n d a n a l y z i n gt a s k si ns p e c i a le n v i r o n m e n t s i n c ew s n n o d e sa r ec h a r a c t e r i z e db ys m a l l s i z e ，l i m i t e dc o m p u t i n gc a p a c i t y , r a d i oc o m m u n i c a t i o na n dp o w e r e db yb a t t e r y , t h e r e a r es t i l lm a n yp r o b l e m st ob es o l v eo ri m p r o v e d , t om a k ew s nw o r ko p t i m a l l yi n s o m es p e c i f i cc o n d i t i o n s t o p o l o g yc o n t r o l ( t c ) ，o n eo fo p t i m i z a t i o nm e a s u r e s ，a i m s a ti m p r o v i n gt h es c a l a b i l i t y , l i f e t i m ea n dc o n c u r r e n c y , t h r o u g hd e c r e a s i n gt h em e d i a a c c e s sc o l l i s i o n , n e i g h b o r i n gd e g r e e ，a n dt h ee n e r g yc o n s u m e dp e rt r a n s m i s s i o n i t s m e t h o di n c l u d e st r a n s m i s s i o np o w e ra d j u s t m e n to rs l e e p s c h e d u l i n g b a s e do na n a l y z i n gt h ep o s i t i o no ft cp r o t o c o li n p r o t o c o ls t a c ka n di t s r e l a t i o n s h i p 谢mo t h e rp r o t o c o l s ，t h ea r t i c l ei n t r o d u c e dp r o b a b i l i s t i cl i n km o d e la n d s t o c h a s t i cl i n kq u a l i t ye s t i m a t i o n ，a n dp r o p o s e dt h el q a t ca l g o r i t h m ，w h i c hi s b a s e do nt h er s s i ，a l li n d i c a t o ro ft h er e c e i v i n gs i g n a lp o w e r i nt h em o d e ls p e c i f i e d i nt h ea r t i c l e ，l q a - t ce n s u r e sn e t w o r kc o n n e c t i v i t y , l i n ks y m m e t 巧, p r o p e ra v e r a g e n e i g h b o rn o d ed e g r e e ，a n di m p r o v e st h en e t w o r ke n e r g yc o n s u m p t i o n , a v e r a g e i n t e r f e r i n gn o d ed e g r e e ，w i t hl i m i t e de x t r ao v e r h e a d t o g e t h e r , t h ea r t i c l ep r o p o s e d a l l i m p r o v e da l g o r i t h ml b a - t c ，t op r o l o n gt h el i f e t i m eo fn e t w o r k l b a - t ct a k e si n t o c o n s i d e r a t i o nt h el o a db a l a n c i n gi s s u e si n 仃o d u c e db yt r a d i t i o n a lt cm e t h o da n di s i m p l e m e n t e db yu t i l i z i n gt h er e m a i n e db a t t e r ye n e r g yi n f o r m a t i o no re n s u r i n gt h e m i n i m a ln e i g h b o rn u m b e r b ys i m u l a t i n gt h ea l g o r i t h m s ，w ea n a l y z et h ee f f e c to f p a r a m e t e r sa n dc o m p a r et h ep e r f o r m a n c eo fr e l a t e da l g o r i t h m s b yl q a t c ，w h i l e n e i g h b o r i n gn o d ed e g r e ei n c r e a s e ss l i g h t l y , t o t a lp a t he n e r g yc o n s u m p t i o na n d i n t e r f e r i n gd e g r e ed e c r e a s e s b yl b a t c ，t h el i f e t i m eo fn e t w o r ki sp r o l o n g e d s i g n i f i c a n t l y , w h e nt h es t a n d a r do fl i f e t i m ei ss e t t i n ga st h ee n d i n gt i m ew h e nm o r e t h a n9 0 n o d e sa l es t i l la l i v e k e yw o r d s ：t o p o l o g yc o n t r o l ，u n d e t e r m i n i s t i cl i n k ，l i n kq u a l i t ye s t i m a t i o n ， p o w e r a s s i g n m e n t , l i f e t i m e i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库：( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系所专业 联系电话 e m a i l 通信地址( 邮编) ： 备注：是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月 日 第一章引言 第一章引言 第一节无线传感器网络的发展与意义 随着无线通讯技术和微电子机械系统( m i c r oe l e c t r om e c h a n i c a ls y s t e m s ，简 称为m e m s ) 的发展以及人类社会对于特殊环境下的自组织网络的需求，无线传 感器网络( w i r e l e s ss e n s o rn e t w o r k , 简称为w s n ) 被提出并获得了越来越广泛而 深入的关注。在救灾搜寻、自然环境检测、交通监控与管理、机器设备监视维 护、空间探测等领域，无线传感器网络都具有重大的应用价值。2 0 0 3 年，由美 国麻省理工大学创办的技术评论( t e c h n o l o g yr e v i e w ) ) ) 将无线传感器网络列为 十大新兴技术之首。作为一种崭新的技术，它还面临许多亟待解决的问题，因 此也向研究者提供了大量的研究课题。 无线传感器网络1 1 】1 2 】是由大量同时具有计算、存储、感测和通讯能力的小型 或微型节点组成的网络，它具有对等、多跳路由、自组织、无线通讯等特性。 节点通过传感器获取周围环境中有限距离内的信息，再通过网络将这一信息传 播到目的地；在信息从获取到传播结束的过程中，从传感器获得的原始信息可 能被筛选、聚合、分析或重组。这些小型节点具有功耗低、体积小、价格低的 特点，主要通过电池供电。由它们构成的无线传感器网络一般具有大规模、自 组织、随机部署、环境复杂、节点资源有限、网络拓扑经常发生变化的特点， 被大量部署和使用在特殊环境下，比如人员稀少的野外环境等。 目前，无线传感网络可以使用无线电波、红外线、光波作为传输媒介。在 国外已经建立起来的无线传感器网络中，多数传感器节点的通讯模块硬件设计 多采用无线电射频电路，使用在大多数国家都不需要向无线电管理部门申请的 9 0 2 m h z 、2 4 g h z 及5 8 g h z 的i s m ( t 业、科学、医疗) 无线电波频段。从网络 协议栈的角度，目前已经实际应用的w s n 节点的m a c 层和物理层通常采用由 i e e e 制定的z i g b e e 8 0 2 1 5 4 t 3 】协议或s m a c t 4 】协议。在传感器网络的发展中，典 型的节点类型包括：早期的m o t e 系列试验节点，选配a t m e g a1 2 8 作为微处理 器和c c l 0 0 0 作为射频芯片的m i c a 2 ，和用支持z i g b e e 8 0 2 1 5 4 标准的c c 2 4 2 0 芯片构成的m i c a z 节点等。这些节点的结构通常如图1 1 所示。研究数据h 7 】表 明：节点在时间同步下组网试验，用2 节a a 电池供电，每3 分钟进行次数据 第一章引言 发送，m i c a 2 和m i c a z 的工作时间分别是5 4 3 天和3 2 8 天，在工作时间上它们已 经初步实现了无线传感器网络最初提出时的目标。然而事实上，这只是在理想 工作情况下的表现，许多研列2 】【5 】表明，无线传感器网络在实际应用中仍然面临 的最大问题是野外实际环境下的生命期表现不佳或与实验环境下的结果存在显 著差距，要实现无线传感器网络的广泛应用，还需要研究上的继续推进。 图1 1 无线传感器网络节点的模块示意图 基于提高无线传感器网络生命期所具有的现实意义，许多研列8 】【1 8 】【1 9 】【3 1 1 旨 在通过优化地使用节点有限的计算能力、通讯能力、存储能力和能量资源，在 保证网络可靠性的前提下，改善节点的能源效率，从而提高网络的生命期。具 体来说，达到这一目标的方法，既包括从单个节点的角度，通过算法优化改进 单个节点的计算效率，降低感测获取信息的频率，使节点可控的睡眠减少无意 义的能量消耗；也包括从网络整体的角度，在应用层进行信息融合，在网络层 设计具有能量意识的路由协议，改善网络的拓扑结构，动态的调整节点发射功 率等。此外，也有很多研究针对传感器网络的安全认证【4 0 j ，节点的空间定位【4 l j ， 节点的状态监控与管理【4 2 j ，移动性管理1 4 3j 等问题。 在从网络整体的角度优化通讯代价的方案中，拓扑控制( t o p o l o g yc o n t r 0 1 ) 是改进w s n 生命期的关键途径，它也是传感器网络中许多其他研究领域的基础。 比如，在文章 6 1 1 9 1 3 3 2 q b ，作者通过仿真或实验指出在经过拓扑控制协议优 化的网络拓扑下，单个节点的能源效率、节点间干扰或冲突的概率、网络的生 命期和可扩展性等都得到改善。然而在这些研究中，还存在许多问题，诸如模 型过于简化且与实际存在差距，需要额外的硬件提供拓扑控制决策依据，因为 2 第一章引言 缺少跨层设计而忽略对于其它层协议的影响等。因此，关于拓扑控制的相关研 究，研究者还需要在改善研究模型的基础上，进一步分析造成通讯开销的各种 因素之间的关系，并在协议和算法设计等方面做出更多努力。 第二节无线传感器网络的拓扑控制 1 2 1 拓扑控制的定义 首先用如图2 1 所示的二维平面图来表示一个无线传感器网络的拓扑状态， 它被称作拓扑图。图中用点代表无线传感器网络的节点和它们地理上的相对位 置，用边代表两个节点可以直接的通讯或互为邻居，这样就用拓扑图表示了网 络在欧几里德二维平面中的拓扑结构。网络的拓扑结构反映了节点在逻辑上或 物理上的连通关系，这一关系是网络层进行路由实现节点间多跳通讯的基础。 当所有节点始终保持活跃，并使用最大信号发射功率发送数据，这时得到的拓 扑图被称作最大传输图。而所谓拓扑控制，就是通过使节点有规律的睡眠，或 者调整它们的信号发射功率，改变拓扑图中的有效点或有效边，这样就得到了 拓扑控制图，通常它是最大传输图的子图。 最大传输图 拓扑控制图 图1 2 最大传输图与拓扑控制图 一般来说，对于任意两个通讯节点z ，和，它们之间通讯的能量开销随着节 点间距离的增长而呈几何级数的增长。这样，在两个节点材和，之间如果存在某 个转发节点w ，就可能借助w 的转发而降低甜和1 ，之间通讯的总能源开销。从这 3 第章引言 一角度，拓扑控制算法的目的通常是使用若干个短距离的多跳连接来代替两个 节点间的长距离直接通讯，从而提高网络的能源效率。 从任意一个节点的角度，节点可以通过运行拓扑控制协议，降低自己的邻 居数量和信号发射功率，这样既实现了网络的稀疏性，也同时通过避免使用长 距离的链路通讯而提高节点的能源效率，从而降低网络整体的能源开销。但是， 在降低邻居数量或信号发射功率以实现网络稀疏性的同时，也可能带来网络连 通性的问题。因此拓扑控制研究本质上要解决的是，网络稀疏性与连通性的权 衡，能源效率与稳定性的权衡以及单个节点的能源消耗速度与网络整体生命期 的权衡。 从网络整体的角度，拓扑控制也可以被看作是通过改进传输媒介在时间或 空间上的重复利用，来提高网络的性能和能源效率。因此，拓扑控制可以被分 为基于空间利用的拓扑控制方法和基于时间利用的拓扑控制方法。对于这两类 方法，将在1 2 3 节和1 2 4 节中分别更进一步的描述。 1 2 2 拓扑控制研究的目标 根据【6 】，在无线传感器网络中，拓扑控制的主要目的是在保证网络连通性 的前提下，通过改善网络的拓扑结构，达到优化网络的性能、提高稳定性、降 低能量消耗、延长网络生命期等目的。在不同的研究【1 2 】【1 3 】【1 4 】【1 6 】【2 5 】【2 8 1 中，作者各 有侧重，现将这些目标总结如下： 连通性( c o n n e c t i v i t y ) ：拓扑控制的最基本要求是保证网络的连通性，否则， 破坏了网络的连通性的拓扑控制将会影响到更上层应用的可用性。这一目标可 以更明确地表示为，拓扑控制要保证在最大传输图中通过若干跳可达的节点在 生成的拓扑控制图中仍然可达。 能源效率( e n e r g ye f f i c i e n c y ) ：当发送节点向距离d 的接收节点传送数据，需 要消耗能量，根据【8 】中的结论，这种数据传送中的能量开销在节点的总能量开 销中比例很大，并且，保证正常通讯所需要的最小能量开销随着距离d 的增长呈 指数级增长。因此，尽量降低能量开销通常是拓扑控制在保证连通性的基础上 的最主要目标。 减少干扰( l o wi n t e r f e r e n c e ) ：节点间传播介质的共享性和开放性，可能带来 通讯干扰，也可能造成数据发送的冲突，从而产生大量重传，这些都会造成额 外的能量开销。所以许多拓扑控制研究的方案【1 4 】【1 5 】，也旨在通过合理设置节点 4 第一章引言 的信号发射功率降低节点间的通讯干扰。 提高空间重用性( h i g hs p a t i a lr e u s e ) - 对空间的重用性是评价无线传感器网 络容量的重要参数，它反映和决定了空间内可以同时发生的通讯的数量。它与 减少干扰的目标是存在区别的，区别在于前者可以通过增加网络的密度，即增 加冗余链路来提高重用性，但是这无疑增加了发生干扰的可能。 网络稀疏性( s p a r s e n e s s ) 无线节点的计算能力是有限的，所以保证网络的 稀疏性对于提高网络的可扩展性至关重要。通过保证网络的稀疏性，即链路数 和节点数的线性关系，可以降低路由协议进行路由选择时的复杂性，改善网络 的扩展性。 对称性( s y m m e t r y ) 在生成的拓扑图中，要保持节点间的对称通讯，即任意 两个节点间的通讯都可以是双方向的，这是为了保证和其它大量既有通讯协议 的相容性。比如按需路由算法，r t s c t s 机制等都需要链路的对称性保证。 低的节点度数( l o wn o d ed e g r e e ) 使每一个节点的邻居数降低，能够减少 有关网络层协议的存储和计算代价，从而节约传感器节点的有限资源。降低节 点度数也有助于达到网络的稀疏性。 本地性( l o c a l i z e dc o m m u n i c a t i o n ) ：所谓算法的本地性是指只通过和在最大 传输图中距离自己一跳的邻居进行有限次通讯就能完成拓扑控制。这样做的目 的是降低拓扑控制带来的额外开销，并降低节点移动对网络扩展性的负面影响。 有限的开销( l i m i t e do v e r h e a d ) ：拓扑控制协议本身在协议栈中的运行不可 避免的给节点带来额外开销，所以降低完成拓扑控制所必需的通讯和计算开销， 节约传感器网络有限的传输资源、计算资源和电池能量也是研究中的重要目标。 1 2 3 基于时间利用的拓扑控制 作为前文描述的拓扑控制分类中的一种，基于时间利用的拓扑控制方法主 要依赖于在许多应用中网络节点不必随时保持激活状态，它们可以有规划的周 期性睡眠和激活，并只在激活的时候和其它节点进行通讯。这样在某一时刻， 网络的拓扑结构因为只有一部分节点处于激活状态而被改变，这样保证了网络 的稀疏性，降低介质访问冲突的可能，减少重传次数，从而改善了网络的性能 和生命期。这一类方法的研究重点在于分簇算法的设计和簇头节点的选择算法， 比如l e a c h 1 9 】和h e e d 2 0 1 等。 分簇算法下，网络中的节点被分为普通节点和簇头节点。在一个执行周期 5 第一章引言 中，那些在整个周期始终保持激活状态并承担主要转发任务的节点被称为簇头 节点，它们通过簇头选择算法产生，它们的集合构成整个网络进行多跳通讯的 骨干；每一个普通节点主动选择或被安排一个簇头节点，它们可以通过一跳直 接和该簇头节点通讯；而借助簇头节点的转发功能，普通节点之间完成多跳通 讯；簇头节点定期更换，保证能源开销的均衡，簇头节点算法的优劣将影响拓 扑控制的有效性。 在l e a c h ”l 中，网络时间周期被分为拓扑建立期和状态稳定期，在拓扑建 立期，每个节点以一定的概率决定自己是否成为簇头节点。当节点选择自己成 为簇头节点时，利用c s m a m a c 发送广播通知自己周围的节点自己成为簇头， 当有多个邻近的节点在一个周期中同时推举自己成为簇头时，相关的普通节点 会选择那个在发送广播时信号强度最大的那个节点作为自己的簇头。该文中同 时提到，以上的方法可以被进一步利用到层次型的分簇算法中。 在h e a d t 2 0 j 中，簇头选择算法的设计同样是文章中讨论的重点。作者依然 令所有节点以一定的概率选择自己成为簇头节点，但同时将节点自身的剩余电 量占最大电量的比例作为簇头选择中的考虑因素。这样，那些随着网络运行而 具有较低电量的节点，会以更低的概率提议自己成为簇头节点，这样，不同节 点间消耗电量的速度在算法随着时间推移的不断执行中得到平衡，避免了人为 设置的节点成为簇头的初始概率可能给网路生命期带来的不确定性影响。 1 2 4 基于空间利用的拓扑控制 基于空间利用的拓扑控制本质上是在不破坏网络连通性的前提下，降低单 个节点的信号发射功率，从而减少它的单次通讯能量开销和邻居数目，最终改 善拓扑。然而节点发射功率的无限度降低，会破坏网络的连通性或可靠性。该 类研究的重点在于如何动态地、分布式地为每个节点确定能保证网络连通性和 可靠性的最小发射功率。 在 4 4 】中提出的最初始的拓扑控制研究模型将拓扑控制描述为发射区域配 置( r a n g ea s s i g n m e n t ，简称r a ) 问题，即为网络中所有节点配置最大可通讯距离， 使得在保证网络连通性的前提下，所有节点的最大可通讯距离和最小。该问题 是此后基于空间利用实现拓扑控制的大量研究的基础。 4 4 1 中提出，在一维空间 中，功率配置问题在多项式时间内可解，在三维及以上维度空间中是n p 类问题。 随后，c l e m e n t i 等在文章 4 5 】中证明了功率配置问题在二维空间中也是n p 类问 6 第一章引言 题，由于无法在多项式时间内找到最优解，可行的启发式算法或近似算法是该 类研究的重点。 此后有大量研究从模型改进、算法设计及协议设计等角度展开，旨在通过 建立更接近无线通讯本质特点的研究模型，找到能够优化节点能源效率并保持 正常传输的拓扑控制方法，以改善拓扑及无线传感器网络的数据通讯方式，从 而达到各种优化目的。比较有代表性的研究成果包括l m s t t l 3 】，x t c f l 2 】和 c b t c t 4 6 1 等，它们研究的侧重点和所使用的方法各有不同，我们将在第二章中进 一步分析这些相关的拓扑控制协议或算法的各自特点。本质上，这些更复杂模 型和目标下的拓扑问题都可以规约到r a 问题，因此它们同样具有n p 性。 相比于基于时间利用的拓扑控制，基于空间的拓扑控制在应用领域上更加 广泛。它不会破坏节点间数据传输的即时性，从而不要求网络应用能够接受网 络传输的高延迟。同时，它并没有改变网络通讯的基本方式，所以能够保证和 大量已有协议的兼容，比如路由协议，认证协议，传输控制协议等，这保证了 在无线传感器网络协议栈中引入了拓扑控制协议后，不需要对已有协议做出大 量修改。此外，它也可以和基于时间利用的拓扑控制结合使用，用来优化在基 于时间利用的方法中那些激活状态的节点所构成的网络的拓扑。所以基于空间 利用的拓扑控制具有十分重要的研究意义和现实意义，是本文讨论的主要内容。 第三节本文研究内容 通过调整发射功率来实现的基于空间利用的拓扑控制算法目前还有许多亟 待解决的问题。本文在模型改进的基础上，通过对拓扑控制相关目标和对实际 可行的拓扑控制协议框架的简要分析，提出了具有容错性和实用性的拓扑控制 算法及相关协议通讯流程，并对算法的有效性和复杂度等进行了分析。论文的 主要研究内容包括： 1 、在明确研究模型的基础上，分析了拓扑控制的主要目标及和其它相关协 议在协议栈中的关系。在此基础上提出了拓扑控制协议在调整期可以只进行粗 粒度的邻居选择的方法，在该方法中拓扑控制可以首先给网络层提供非最小数 目的邻居数，之后利用网络层的路由负载来实现更细粒度的链路选择。 2 、对研究模型进行了改进，使它更加贴近实际，更能反映出在应用中硬件 的实际能力和无线通讯的实际特性。基于这些模型上的变化，我们提出了一种 7 第一章引言 有链路质量保证的拓扑控制算法l q a t c ，其目标是在进一步改进网络性能和能 源效率的同时，保证算法对于硬件提供的信息具有定程度的容错性，同时尽 可能降低拓扑控制引入的通讯和计算开销。 3 、网络节点间负载的平衡性可能会被拓扑控制协议破坏，即某些节点可能 因为拓扑控制的存在而承担更多的转发任务而过早的耗尽能量，这将与拓扑控 制延长网络生命期的目标相悖。针对这一问题，本文提出了有针对性的拓扑控 制改进算法l b a t c l 和l b a t c 2 ，它们分别利用剩余能量信息和提高节点度数 改善了拓扑，使网络在保证网络能源效率的同时，兼顾节点间转发负载不同对 网络生命期的影响。 4 、对提出的算法和协议进行了计算复杂度和通讯开销的分析，都旨在针对 传感器网络节点能力的有限性，进一步讨论本文提出的方法的实用性。同时， 通过对算法的仿真，分析在不同参数条件下各种设计目标的实际表现，包括拓 扑特性、网络性能和节点能源消耗速度等，并对相关算法进行比较。 第四节论文结构 本文共分六个部分，具体的结构如下： 第一章介绍当前无线传感器网络的研究现状，以及其中拓扑控制研究的意 义、分类与目标，此外，也包括本文的主要研究方法和内容； 第二章中简要介绍与讨论相关研究，并提出本文中研究的模型基础和评价 模型，也分析了拓扑控制协议的基本框架和在协议栈中的位置； 第三章提出并分析了有链路质量保证的拓扑控制算法l q a t c ，它建立在更 反映无线链路本质的链路模型以及基于r s s i 信息的链路质量预测方法的基础 上，旨在更好的达到拓扑控制的目标； 第四章提出了两种针对提高网络生命期的拓扑控制改进算法，这两种算法 分别利用了节点剩余能量信息和冗余邻居数； 第五章主要通过仿真，对前面提出的算法的平均性能进行分析，主要讨论 了算法中参数的影响和选择，并在平均节点度数，平均干扰度数，网络路径能 量消耗和和网络生命期等方面与其它算法进行比较。 第六章对本文的研究加以总结和分析，并提出进一步完善的建议。 8 第二章相关研究与研究基础 第二章相关研究与研究基础 第一节相关研究 基于功率调整的拓扑控制的目的在于通过调整节点的邻居集合和配置信号 功率，尽可能减少网络通讯中的能量开销，并同时期望达到网络的其它特性， 比如连通性，可扩展性，链路冗余度等。前文中已经提到，有大量的研究从模 型改进、分布式算法的设计和拓扑控制协议的设计等角度出发，试图更好的分 析和解决无线传感器网络中的拓扑控制问题。对于这些有关研究的全面性综述 可以从【1 l 】中获得，下面只对些有代表性的方法进行回顾与讨论。 在【8 】中提出，基于节点的地理位置信息，任意节点可以找到对某个转发节 点的有价值转发区域，该节点只要通过集合运算维护它所在的部署区域内的节 点闭包集合中的节点作为邻居，整个网络就能保证双向的通讯，这一研究用多 项式复杂度的算法，解决了在节点本地实现分布式的拓扑控制的问题。【1 3 中作 者通过本地的最小支撑树算法( m i n i m u ms p a n n i n gt r e e ) 进一步降低了生成的拓 扑图中节点的平均度数，并证明它能保证网络的连通性。这两种算法都在已经 获得了准确的节点位置信息的假设下实现拓扑控制，节点的位置信息保证了算 法的执行效率和有效性，但在实际应用环境下可能面临无法获得准确位置信息 等问题。 也有一些算法没有利用节点的位置信息来实现拓扑控制，比如 4 6 1 q b ，作者 假设节点能够获得自身到所有邻居节点的方向度，通过保证在以自身为中心的 任意5 万6 的夹角上都有邻居节点，实现了保证网络连通性的拓扑控制。同时该 篇文章中提出了一种邻居发现协议，旨在检测和解决周围节点移动或周围节点 能量耗尽等网络状态变化对拓扑控制的影响。【1 2 q b 作者提出了x t c 算法，x t c 算法通过对节点到邻居之间的链路状态的好坏进行排列，利用节点本身的排序 结果和邻居的排序结果，选择那些足以保证网络连通性的好的链路构成网络。 这一研究的重大贡献之一在于将拓扑控制的研究基础从基于位置的欧几里德平 面图转入了有向权重图中。 研究 2 5 1 1 2 6 1 q 丁，基于信号发射功率调整的拓扑控制被和节点的睡眠规划与 能量感知路由相结合，作者分析了拓扑控制两种方法功率调整和睡眠规划的区 9 第二章相关研究与研究基础 别和联系，并提出一种算法使节点能根据网络中实际应用的特点，动态地选择 以下拓扑控制：单独利用功率调整、单独利用睡眠规划或两者结合实现。 r a m a n a t h a n 等在 7 】中提出了两种针对移动网络的启发式拓扑控制算法，作 者实现拓扑控制的方法是，通过算法的执行保证节点的实时活跃邻居数高于指 定的最低节点度数且低于指定的最高节点度数。该算法每次执行后都会得到当 前发射功率下的活跃邻居节点数，然后根据该值决定节点增大还是降低下一周 期的信号发射功率，这种方法有助于改善移动情况下的拓扑控制效果，但是并 没有严格的保证网络的连通性。 近期的很多研究【1 5 】【1 4 】【3 6 1 都将通讯干扰考虑进拓扑控制的研究中，因为随着 研究的深入，单纯的降低邻居节点度数被发现在实际中并不能降低节点间的通 讯干扰，也就不能实际带来网络吞吐力的提高。通过引入物理通讯中的信噪比 模型，这些研究有针对性的讨论了以提高网络吞吐力为目标的拓扑控制方法。 为了提供拓扑控制的容错性，【2 3 】中提出了保持节点的k 连通性的拓扑控制算 法，它保证了网络在k 一1 条链路失效情况下网络的可用性。在 2 1 l 中，作者利用 非确定性链路模型中的过渡区域，提出了保证最低路径数据包接收成功率的拓 扑控制算法，进一步降低了能源利用率，但是没有充分分析接收成功率下降带 来的额外数据通讯所产生的能量开销。 在 1 6 1 中作者提到，拓扑控制的目标是多方面的，目前没有一种拓扑控制方 法能够同时达到这多种目标，文章中作者在分析无线传感器拓扑控制的各种目 标的基础上，提出了一种基本的利用距离功率模型的拓扑控制算法，并分 析了该算法能够达到初始设定的目标中的大多数。 在不使用位置信息的拓扑控制方法中，进行节点间链路的质量预测是进行 拓扑控制的基础。利用信号接收功率反映节点之间的链路质量是目前已知的链 路质量估计方法中比较适合使用在拓扑控制中的方法。然而，许多关于无线传 输特性的研究2 7 】【3 6 】【3 7 】【3 9 1 都指出节点信号发射功率，节点传输距离，节点的接收 功率与链路质量指标之间是一个复杂的关系，且在时间和空间上存在不确定性， 这是由无线链路的易损耗的本质决定的。这种不确定性会影响到链路质量估计 的准确性，本文下面提出的拓扑控制方法l q a t c 将考虑链路质量估计的误差， 无线链路的质量和稳定性随通讯距离和信号发射功率的变化性。 无线传感器网络本身是基于实际需求的研究，因此在研究中应该注意现实 中的实际需求和硬件的实际能力，而不是一味的追求数学上的最优解。对此一 1 0 第二章相关研究与研究基础 个有代表性的例子是拓扑控制的研究从最初的以降低节点度数为目标，开始更 多的关注拓扑控制对网络性能的实际改变。过低的节点度数会带来网路冗余链 路的降低和网络负载的不均衡，因此，本文提出了针对延长网络生命期的改进 算法l b a t c l 和l b a t c 2 ，前者根据剩余电量动态调整链路的权重，在不明显 增加节点度数的情况下延长网络生命期，而后者通过提供更高邻居数以实现和 能量感知的路由算法的兼容，利用路由协议平衡节点间能量消耗速度的差异。 第二节研究模型 2 2 1 无线传感器网络的基础概念 下面定义本文所论述的无线传感器网络的基本含义并做出一些假设。无线 传感器网络是由一些节点通过无线电通讯组成的网络，我们假设这些节点具有 一致性，即所有节点具有完全相同的基本特性，比如初始能量、通讯特性、计 算能力、最大信号发射功率等。这些节点具有有限的能量，可能会移动但大多 数时间保持位置固定。每个节点的通讯范围是有限的，它们主要通过多跳的方 式来增加信息的传播距离。同时节点可以调节自己在通讯时的发射功率，这种 调整会影响到节点的有效通讯距离。每个节点的基本功能是计算、存储、感测 和通讯，其中通讯消耗了绝大多数的电能。当节点的能量耗尽，或者当某个节 点因为距离过远造成它不能和自己以外的任何节点进行通讯时，可以认为它在 网络中是不存在的，并且随着时间的前进，能量耗尽的节点数目将不断增加， 从而最终影响到这个网络的有效存在性。 2 2 2 拓扑控制问题的描述 首先将无线传感器网络模型化，它被描述为欧几里德平面下的有向图 g ( v ，e ) ，其中矿代表节点的集合，网络中每一个编号为，的节点都对应平面图 中的一个点v ，也可以用它在平面中的位置( ，咒) 或节点的编号，表示。网络中 的任意两个节点，和，如果可以进行一跳的直接通讯，就在平面图中用一条连接 它们的边e j ，来表示这种连通关系，这些连通关系的集合在平面图g 中体现为边 的集合e 。 然后，我们为集合矿中的每一个节点，的可调整的信号发射功率( s i g n a l t r a n s m i t t i n gp o w e r ) 设定一个值，记为尼( f ) ，这样就产生了网络中所有节点的发 第二章相关研究与研究基础 射功率的配置集合尸丁，定义为： p t = 只( 1 ) ，只( 2 ) ，p a n ) ，其中n 爿v ( 2 1 ) 用b ( ，j ) 来表示节点f 利用发送器发送数据后在节点_ ，处的接收器收到信 号的接收功率。节点f 和，的位置关系，节点i 的信号发射功率p t ( i ) 和信号传播 方式共同决定了b ( f ，歹) 的大小，表示为： b ( f ，) = p r o p ( i ，只( 功 ( 2 2 ) 其中函数朋d p 由信号传播模型决定。并且因为只有p r ( i ，j ) 大于一个阀值 r ，接收到的信号才能在物理层被正确解码，所以一般认为当满足接收功率大于 阀值丁的条件才认为在节点f 到，之间才可能存在一条链路( 或称作边) e i ，可 记作( f ，) ，在这一解释下，在给定的p 丁下，有向图g 的边的集合e 可以表示为： 廓r = ( f ，) ip r ( i ，) t a p , ( j ，f ) n ( 2 3 ) 在早期的研究【6 】【7 】中，拓扑控制问题被简单的描述为算法研究问题。它要 在保证网络连通性的前提下，找到最优的传输功率配置集合p r ，以使所有节点 的信号发射功率的和只( f ) 最小。 而随着研究的深入，拓扑控制研究所要改善的目标进一步深入和多样化， 同时也更多考虑无线网络尤其是无线链路的特性。但从本质上，基于功率调整 的拓扑控制研究的重点依然是通过分布式的算法调整所有节点的发射功率，试 图从所有节点采用最大发射功率时的拓扑图g ( 矿，e ) 得到它的子图g ( y ，e 9 。该 子图应该保持连通性，并且尽可能满足其它特性，比如能源效率的提高、节点 干扰度数和节点邻居度数的改善等，以达到整体上优化网络的目的。对于本文 中研究的拓扑控制问题的具体目标将在2 2 6 节中具体介绍。 2 2 3 信道传播模型 信道传播模型用来描述信号在传输信道传播过程中的衰减过程，它可以被 简单的理解为接收到的信号功率e 关于发射功率和距离节点间距离d 的函 数。在自由空间传播模型1 1 l ( f r e es p a c ep r o p a g a t i o nm o d e l ) q h ，用于传送数据包 的发射功率p 和接收到的功率的关系可以表示为 p r - - 嬲 ( 2 4 ) 其中，g f 是发射器的天线增益，g ，是接收器的天线增益，五是波长，d 是发射 天线到对应的接收天线的距离，三是系统损耗参数。 第二章相关研究与研究基础 而在地空二径传播模型1 1 1 1 ( t w o - r a y 觚u 1 1 dp r o p a g a t i o nm o d e l ) 中，用于传送 数据包的发射功率和接收到的功率e 的关系可以表示为 e ：p t g t g f , h , h , 兄2 ( 2 5 ) “l 其中，g f 是发射器的天线增益，g ，是接收器的天线增益，五是波长，d 是发射 天线到对应的接收天线的距离，三是系统损耗参数，忽是发射器天线高度，睡是 接收器天线高度。 本文将使用长距离路径损耗模型 1 3 l ( l o n gd i s t a n c ep a t hl o s sm o d e l ) ，来描述 信号在传输信道上的衰减。在这一模型下，当用，表示节点f 到，的信道增益 ( 通常假定它是一个独立于距离，只和节点特性相关的常数) ，则距离为d 的节 点f 和，之间信道的接收功率和发射功率的关系可以表示为 易( f ，舻粤掣 ( 2 6 ) u i j 其中，口是路径损耗参数，它通常取2 至5 中的值，具体取值与环境相关。 当口= 2 ，则该模型等价于采用了公式( 2 4 ) 的模型；当口= 4 ，等价于采用了公式 ( 2 5 ) 中的模型。 根据文章 1 7 】【3 6 】中的结果，当信号接收强度( 可以理解为接收信号功率p ) 高于一个阀值瓦功，链路能够提供高质量传输。在它从阀值瓦恸下降到的过 程中，数据包成功接收率和信号接收功率向相同方向发展，即两者存在一定的 比例关系，这种链路仍被认为是可靠的。随着接收信号强度从阀值进一步降 低，链路的不确定性，即数据包接收率的方差会突然变大，这意味着接收数据 包的成功率存在很大波动，对于链路的质量已经很难准确估计，事实上，造成 这一原因的本质是当p 处在较低值时，信号噪声成为决定数据包接收成功率的 主要原因，而噪声随时间存在较大的变化性。因此，当假定公式( 2 6 ) 中蜀。，= 1 ， 同时引入存在接收可能的最小功率阀值，则在长距离路径损耗模型下，保证 节点j 到，进行高质量传输、可靠传输和存在传输可能的条件分