（通信与信息系统专业论文）无线网络拓扑控制技术研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 拓扑控制是无线网络研究的核一i i , 技术之一，良好的拓扑控制算法可以构成特定 网络拓扑结构，从而提升网络吞吐量、路由协议的效率、链路容量和频谱资源复 用能力，并最终为网络用户和业务服务质量保障奠定网络基础。拓扑控制采用节 点功率分配算法以获得具有某种性质的拓扑结构和优化网络特定的目标函数。这 种功率控制技术在m e s h 拓扑中面临极大地挑战。本文以国家8 6 3 课题“层次化拓 扑控制的宽带无线自组网体系研究”需求为背景，研究其拓扑控制相关技术。主要 研究内容有： ( 1 ) 拓扑控制技术的基本概念、国内外发展现状、业界研究重点及方法、以 及其相关数学问题研究。探讨了拓扑控制技术及其在网络架构中的地位，重点分 析了节点功率控制算法、层次型拓扑控制算法以及网内节点协同启发机制的特性。 ( 2 ) 设计一种拓扑控制策略，提供无线网络频点空间复用的网络拓扑支持。 本文中通过拓扑控制技术构造一种虚拟的规则拓扑，从而实现了一种具备简洁性、 有效性和可靠性的层次化无线网络架构。研究将具备规则性的直接互连拓扑引入 宽带无线移动网络，通过拓扑控制维护相对稳定的规则拓扑，从而提供了频点资 源可复用性、提升了链路可靠性、提高路由算法的有效性。 ( 3 ) 异构无线网络已成为热点研究领域。本文重点分析异构网络中节点具有 不同发射和接收增益时对网络性能的影响，通过将信号的能量域s i n r 模型引入图 论模型，研究一种异构网络在不同接收增益条件下的拓扑控制改进算法。 关键词：无线网络，异构网络，拓扑控制 重庆大学硕士学位论文英文摘要 a b s t r a c t t o p o l o g yc o n t r o li so n eo ft h em o s ti m p o r t a n tt e c h n o l o g i e so fw i r e l e s sn e t w o r k s ， a n daf e a s i b l et o p o l o g yc o n t r o la l g o r i t h mg e n e r a t e sa l la p p r o p r i a t en e t w o r kt o p o l o g y w h i c hp o s s e s s e st h en e t w o r k si n d i v i d u a lc h a r a c t e r i s t i c s t h a ti st os a y , b yt o p o l o g y c o n t r o l l i n g ，t h en e t w o r kt h r o u g h p u t , m a cl a y e r , r o u t i n ge f f i c i e n c y , l i n kc a p a c i t ya n d s p e c t r u mr e s o u r c e sm u l t i p l e x i n gc a p a c i t y c a l lb ei m p r o v e d g e n e r a l l ys p e a k i n g ， t o p o l o g yc o n t r o l f o c u s e do nh o wt od e s i g ne f f i c i e n ta l g o r i t h m sf o rn o d e sp o w e r a l l o c a t i o n i no r d e rt oa c q u i r eap a r t i c u l a rt o p o l o g ya n do p t i m i z et h es p e c i f i c a l l y o b j e c t i v ef u n c t i o n p a r t i c u l a r l y , i ti sac h a l l e n g et od e s i g nam e s ht o p o l o g yn e t w o r k t h i sd i s s e r t a t i o ni ss u p p o r t e db yt h en a t i o n a l8 6 3p r o j e c t h i e r a r c h i c a lt o p o l o g yc o n t r o l o ft h eb r o a d b a n dw i r e l e s sa dh o cn e t w o r ks y s t e m a n df o c u s e so nt h et o p o l o g yc o n t r o l o fw i r e l e s sn e t w o r k t h ed i s s e r t a t i o n sm a j o rw o r ka n di n n o v a t i o n sa r es h o w na s f o l l o w s ： ( 1 ) s u m m a r i z e dt h ec o n c e p t so ft o p o l o g yc o n t r o lt e c h n o l o g y , t h ed e v e l o p m e n to f r e s e a r c h i n gw o r ki n c l u d i n gt h em a t h e m a t i c a lf o u n d a t i o n p r e s e n t e d t h ep r o a n dc o n o f t h et o p o l o g yc o n t r o la l g o r i t h m ，i n c l u d i n gn o d ep o w e rc o n t r o la l g o r i t h m ，h i e r a r c h i c a l t o p o l o g yc o n t r o la l g o r i t h ma n dt h ec o l l a b o r a t i o nm e c h a n i s mo fn e t w o r kn o d e s ( 2 ) s t u d y i n go n ek i n do fr e g u l a rt o p o l o g yc o n t r o ls t r a t e g yw h i c hf a c i l i t a t e s t h e f r e q u e n c ys p a c er e u s i n ga n dt r a f f i cr o u t i n g t h i sd i s s e r t a t i o np r o p o s e dat o p o l o g y c o n t r o l a l o g r i t h i n w h i c hi n t r o d u c e dav i r t u a l l a y e r e dr e g u l a rt o p o l o g y w i t h e n g i n e e r i n g v a l u e t h i sr e g u l a rt o p o l o g yi sa v a i l a b l ef o rf r e q u e n c yr e s o u r c er e u s i n g ， l i n kr e l i a b i l i t ya n dr o u t ea l g o r i t h mf o rb r o a d b a n dw i r e l e s sm o b i l en e t w o r k ( 3 ) t h eh e t e r o g e n e o u sw i r e l e s sn e t w o r ki sah o tt o p i cl a t e l y t h i sd i s s e r t a t i o n f o c u s e s0 1 1t h en e t w o r kw h e r ei t sn o d e sh a v ed i f f e r e n tt r a n s c e i v e rg a i na n ds u g g e s t e da t o p o l o g yc o n t r o ls t r a t e g yb yi n t e g r a t i n gs i n r - b a s e dm o d e li n t og r a p h b a s e dm o d e l t h en e wa l 鲥t h mc o u l di m p r o v et h eh e t e r o g e n e o u sn e t w o r kp e r f o r m a n c ee s p e c i a l l y w i t hd i f f e r e n tr e c e i v i n gg a i n s i m u l a t i o na l s ov e r i f i e dt h en e wa l g o r i t h m k e y w o r d s ：w i r e l e s sn e t w o r k s ，h e t e r o g e n e o u sn e t w o r k ，t o p o l o g yc o n t r o l 学位论文独创性声明 本人声明所 呈 交的虹 士 学位论文 盈缝! 困盛主亘斗翌塑j 垫! 缉鱼 是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人己经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 学位论文作者签名：勘；毪签字日期：硼1 王 导师签名： 学位论文使用授权书 本人完全了解重庆大学有关保留、使用学位论文的规定。本人完全同意中 国博士学位论文全文数据库、中国优秀硕士学位论文全文数据库出版章程( 以 下简称“章程) ，愿意将本人的衅学位论文垂驾图逝 麦蛔丛i ! ! 主妒 提交中国学术期刊( 光盘版) 电子杂志社( c n k i ) 在中国博士学位论文全文数 据库、中国优秀硕士学位论文全文数据库以及重庆大学博硕学位论文全文 数据库中全文发表。中国博士学位论文全文数据库、中国优秀硕士学位论 文全文数据库可以以电子、网络及其他数字媒体形式公开出版，并同意编入c 腿i 中国知识资源总库，在中国博硕士学位论文评价数据库中使用和在互联 网上传播，同意按“章程 规定享受相关权益和承担相应义务。本人授权重庆大 学可以采用影印、缩印或其他复制手段保存论文，可以公开论文的全部或部分内 容。 作者签名： 导师签名 备注，审核通过的涉密论文不得签署。授权书一，须填写以下内容： 该论文属于涉密论文，其密级是，涉密期限至年一月一日。 说明：本声明及授权书：蛆装订在提交的学位论文最后一页。 重庆大学硕士学位论文1 绪论 1 绪论 1 1 引言 无线网络的发展日新月异，新的标准和技术不断涌现。总的来说，由于覆盖 范围、传输速率和用途的不同，无线网络可以分为：无线广域网、无线城域网、 无线局域网、无线个人网络以及无线m e s h 网络【l j 。无线广域n ( w w a n ) 覆盖范围 最大，代表技术有3 g 以及未来的4 g 。无线城域n ( w m a n ) 可以覆盖城市中大部 分的地区，代表技术是i e e e 8 0 2 1 6 2 1 1 3 1 系列。无线局域网( w i ，a n ) 一般用于区域间 的无线通信，其覆盖范围较小，代表技术是i e e e8 0 2 1 1 【4 】系列。无线个人n ( w p a n ) 的无线传输距离一般在1 0 米左右，典型的技术是i e e e8 0 2 1 5 的b l u et o o t h 技术。 无线m e s h 网络是移动a dh o e 网络的一种特殊形式，是一种新型的宽带无线网络 结构，可以由固定节点和移动节点通过无线链路组成【5 】。无线m e s h 网通过接入点 a p 之间存储和转发消息以提供功能更强和可靠性更高的网络拓扑。 宽带无线接入解决了“最后一公里”网络接入瓶颈问题，目前w l a n 正扮演着 最突出的角色，它使用无需许可的公共频段，组网方式简单、灵活、快捷，部署 成本低，传输速率高( 目前主流的i e e e 8 0 2 1l a g 技术可实现高达5 4 m b s 的数据速 率) 。然而w l a n 每个接入点的覆盖范围比较小，而且不同w l a n 业务提供商之 间的网络没有漫游协议，同时缺乏充分的安全措施和完整的结构。另一方面， w i m a x 成为w m a n 领域的领先性技术，w i m a x 基于i e e e 8 0 2 1 6 d e 2 1 1 3 1 标准， 作为新型的宽带接入技术，将提供固定或移动无线宽带网络，最高的传输速率可 达7 5 m b s ，最大覆盖范围可以达到5 4 k i n 。 无线m e s h 网络采用网状结构，它的早期研究源于移动a dh o e 网络的研究与开 发，是一种新型的宽带无线网络结构，即一种高容量、高速率的分布式网络。最 新的i e e e 8 0 2 1l s 6 1 草案引入了m e s h 机制，促进了w l a n 的可持续发展，其方案 也写入i e e e 8 0 2 1 6 ( w i m a x ) 无线宽带接人网络标准中，匝e e 8 0 2 1 5m e s h 和正在 制定的i e e e 8 0 2 1 1m e s h 标准目前也在制订中。 为了满足不同的业务需求、提供更好的服务质量和更高网络效率，未来的无 线网络必然是朝着多种无线接入技术融合的方向发展【7 】。相对于结构单一、管理简 单的同构网络，异构网络具有更复杂的特性。不同的接入网络归属和不同的网络 技术带来了不同用户在不同服务区域内的身份认证问题、数据安全传输问题，以 及相应的计费问题等。然而，不同于有线网络，异构无线存在严重的无线信道之 间和网络之间的干扰。因此要实现真正意义上的异构融合，需要一个统一的异构 网络架构，并在统一的网络架构下，提供各个层次的网络融合，从而保证用户在 重庆大学硕士学位论文1 绪论 任何接入点都能安全、可靠地通信。 无线网络一般具有环境复杂、资源受限、网络拓扑变化的特点。不同于有线 网络，无线网络可以通过改变各个网络节点传输功率( 无线传输范围) 以改变网络的 拓扑结构，这就是拓扑控制的实现技术基础。同时，节点的位置对网络的性能也有 着重大的影响。如果拓扑结构过于松散，就容易产生网络分区以及增大端到端的时 延；相反的，非常密集的拓扑不利于频谱空间重利用，从而减小网络的容量【8 】。拓扑 管理和控制【9 】主要研究如何为节点分配功率以获得具有某种性质的拓扑结构和优 化一些网络目标函数，其目的就是提高网络的性能，降低通信干扰和延长网络的生 存时间【l o 】1 1 1 1 。 无线网络的特点使拓扑控制成为挑战性研究课题，同时，这些特点也决定了拓 扑控制在无线网络研究中的重要性。 1 2 课题研究目的和意义 当节点改变其传输功率时，其通信半径也随之改变，从而使无线网络的拓扑 结构发生变化。由节点的位置和传输范围确定的网络拓扑结构对网络的性能有着 重大的影响：如果节点使用大的传输功率，那么形成的拓扑结构密集，增加了网 络的连通性，减少分组中转的次数，但是加剧了节点之间的干扰，不利于带宽的 空间重利用。另外，多个节点在共享无线信道时将增大碰撞的概率，触发退避机 制，导致分组的延迟大【1 0 1 ；相反，如果节点的传输功率小，其形成的拓扑结构松 散，增加了网络的容量，减少了节点之间的干扰，但容易产生网络分区【1 1 1 。 拓扑控制主要研究如何在保证网络连通性的前提下，设计高效的节点功率分 配算法以获得具有某种性质的拓扑结构和优化网络目标函数。拓扑控制是无线网 络设计和规划的重要组成部分。拓扑控制技术保证覆盖质量和连通质量，能够降 低通信干扰、节省能量，提高m a c ( m e d i aa c c e s sc o n t r 0 1 ) 协议和路由协议的效率。 进一步，也可为无线网络融合提供拓扑基础。此外，拓扑控制还能够提高无线网络 的可靠性、可扩展性等性能。总之，拓扑控制对无线网络性能具有重大的影响，因而 其研究具有十分重要的意义。 1 3 项目需求背景 “新一代宽带无线移动通信网”是国家中长期科学和技术发展规划纲要中明 确的重大专项。宽带自组网是一种无需固定接入站的宽带无线移动网，成为目前 无线通信领域的热点，具有“建网迅速”、“抗毁能力强”、“带宽大”、“可靠性高”等 诸多优点。论文的研究工作是在国家高技术研究发展计划项目“层次化拓扑控制的 宽带无线自组网体系研究”的支持下完成。该课题研究一种宽带无线自组网架构体 2 重庆大学硕士学位论文1 绪论 系，从拓扑结构、交换机制、调度算法和管理策略方面，实现“高带宽”和“高可靠 性”的宽带无线移动通信。 在确定的网络架构下，控制和管理算法对系统性能起到重要作用。通常无线 网络协议划分为“三层二平面( 见图1 1 ) 。三层是指物理层、数据链路层和网络层； 二平面即为数据控制平面和管理平面。此外，还可以根据设计要求增加安全层协 议。 数据控制平面管理平面 图1 1 协议软件架构图 f i g1 1t h ep r o t o c o ls t a c ka r c h i t e c t u r e 网络的三大要素是：拓扑、节点和控制。拓扑是网络架构的基础，也是本课 题研究的首要问题。无线通信系统采用功率控制技术可以提高网络性能，减少站 点之间的无线信号干扰，提高无线信道的空间复用度，同时增加网络容量和减少 站点设备功耗。拓扑控制则是从整个网络拓扑角度层面来调整网络容量、减少拥 塞、控制系统功耗、保障q o s 指标。 通常，自组网研究多考虑“拓扑无关”的路由算法，该方案受限于网络规模和无 线链路质量。学术研究方面，拓扑控制研究重点也是控制网络节点连接度等方面， 其拓扑不具备确定的几何规则。而本研究将重点考虑具备规则拓扑的直接互连拓 扑引入宽带无线移动网络，通过拓扑控制维护相对稳定的直连拓扑，从而保障频 点资源的空间复用。 异构无线网络的关键性技术拓扑控制已成为热点研究领域。本文重点分析异构 网络中具有不同发射和接收增益的节点对网络性能的影响，将信号的能量域s i n r 模型引入图论模型，进一步研究异构网络在接收增益不同条件下的拓扑控制策略。 1 4 研究内容及要解决的问题 ( 1 ) 无线通信的理论基础和体系结构研究 重庆大学硕士学位论文1 绪论 体系结构是网络的基础，对整个网络起着至关重要的作用。本文研究分析宽 带无线移动网络的架构，讨论拓扑控制与网络协议各层的关系。 ( 2 ) 无线网络拓扑控制算法研究 拓扑控制是无线网络研究的核心技术之一，良好的拓扑控制算法可以生成合 适的、能及时适应网络变化的拓扑结构，可以提高网络的性能，为m a c 和路由效 率提升提供支持。本文研究拓扑控制相关理论，并以图论为基础分析其算法的控 制机制和性能特点。 ( 3 ) 提出一种层次化的拓扑控制方案 在国家高技术研究发展计划课题“层次化拓扑控制的宽带无线自组网体系研 究”中，需要提供一种层次化拓扑控制策略。本论文采用拓扑控制技术实现了一种 虚拟的规则拓扑，将规则拓扑的直接互连拓扑引入宽带无线移动网络，通过拓扑 控制维护相对稳定的直连拓扑，从而保障频点资源的有效利用和路由算法的优化。 ( 4 ) 异构网络算法的研究和提出 异构无线网络的关键性技术拓扑控制已成为热点研究领域。本文重点分析异 构网络中具有不同发射和接收增益的节点对网络性能的影响，将能量域s i n r 模型 引入图论模型，提出了异构网络在接收增益不同条件下的拓扑控制策略。 1 5 本论文的安排 全文分为六章，各章的具体内容安排如下： 第一章：绪论部分，介绍研究背景及意义，以及研究内容和需要解决的问题。 第二章：阐述了拓扑控制技术的基本概念、国内外发展现状、业界研究重点及方 法、以及其相关数学问题，并讨论一般情况下拓扑控制在协议层的关系，提出本 课题拓扑控制研究侧重点及其在系统研究中的地位。 第三章：根据研究方向的分类，重点分析节点功率控制算法，层次型拓扑控制算 法以及网内节点协同启发机制算法。 第四章：研究一种虚拟层次化的拓扑控制策略。提出了该网络的顶层和底层的拓 扑控制算法和规则。将规则拓扑的直接互联拓扑引入宽带无线移动网络，通过拓 扑控制技术实现一种虚拟的规则拓扑，从而设计与实施具备工程化的网络架构 第五章：提出现有拓扑控制算法在解决异构网络中的困境，并对经典的异构网络 算法进行分析。针对异构网络中节点的最大发射和接收增益不同对网络性能的影 响，将信号的能量域s i n r 模型引入图论模型中，提出了异构网络的节点在接收增 益不同条件下的拓扑控制策略。 第六章：总结本文的研究工作，提出未来的工作展望。 4 重庆大学硕士学位论文2 无线网络的拓扑控制 2 无线网络的拓扑控制 2 1 国内外发展现状 无线网络的拓扑控制自上个世纪7 0 年代就开始研究，但自2 0 0 0 年以来，许 多拓扑控制算法【1 0 】才被系统的提出，较为代表的有c o n n e c t 9 ，m i n r 1 2 1 ，l i n t 9 1 ， l m s t 1 0 1 。c o m p o w 【1 3 】等。 值得注意的是，这里所讲的算法是微观性质的拓扑控制算法，即算法以每个 具体的网络节点为出发点，考虑如何控制它们的传输功率以获取合理的拓扑结构。 通常所讲的拓扑控制算法都是微观性质的，而宏观性质的拓扑控制研究通常以整 个网络( 尤其是大规模网络) 为对象，研究如何获取一个合理的全网连通性的拓 扑结构。宏观性质的研究通常采用概率分析方法，分析算法所关注的网络特性。微 观性质的拓扑控制主要研究算法有：连通及能量关注型算法，网络吞吐率关注型 算法以及网络健壮及容错关注型算法。 ( 1 ) 连通及能量关注型算法 连通性是拓扑控制最基本的要求。这一类型的算法在追求网络连通的前提下， 尽可能的减少节点的度数，以此降低节点能量的开销。以下列举这一类型算法中 的几小类重要的算法 基于m i n i m u ms p a n n i n gt r e e ( m s t ) 的算法 m s t 图【3 1 】被定义为保持原图连通的情况下由最小边生成的子图。两个主要的 k m s k a l 1 4 】算法和p r i m t ”】算法可以用来计算m s t 。以m s t 为拓扑的网络能保证网 络的连通性。由于在分布式环境下构造m s t 开销很大，一种折中的方法是节点采 用局部m s t 方法( 即根据局部的邻居信息建立本地m s t ) ，以此为每个节点设置 传输范围。x y l i t ”】提出的l m s t 算法是一个经典的基于m s t 的分布式近似算法， 用该算法构建的拓扑中，每个节点的度至多为6 。 基于g a b r i e lg r a p h ( g g ) 的算法 在欧拉空间中，用，。代表节点，。的位置向量。g o t l 6 】被定义为任意两个节点和 1 ，之间存在边，当且仅当不存在节点心使得i - tl z 十| ，- 厶i2 一i ，i2 成立。其中 的i 厶厶i 表示m 与，之间的欧拉距离。g - g 算法适用于分布计算，也即使用本地信 息即可构造网络拓扑。在传输功率正比于传输距离的平方时，g o 图是最节能的拓 扑。 基于r e l a t i v en e i g h b o r h o o dg r a p h ( r n o ) 的算法 r n g 1 刀被定义为对于任意两个节点对( 砖，v ，) ，如果没有节点吒存在，使得 i 厶i d ( u 2 ，吃) o r ( d ( u l ，v 1 ) d ( u 2 ，吃) & & m a x i d ( u o ，i d ( v o m a x i d ( u 2 ) ，谢( 吃) ) 1 3 重庆大学硕士学位论文3 经典拓扑算法分析 o r ( d ( m ，m ) = d ( u 2 ，v 2 ) & & m a x i d ( u ! ) ，耐( v 1 ) m a x i d ( u 2 ) ，耐( 吃) ) & & m m i d ( u 1 ) ，澎( 啊) m i n i d ( u 2 ) ，谢( 吃) ) 双向性( b i d i r e c t i o n a l i t y ) - 如果任意两节点甜，y ( 嘭) ，“以( 1 ，) 且i t ，v ， 。( 1 ，) ，则算法a 产生的拓扑是双向的。也就是说，如果算法a 产生的拓扑中所有 得边都是双向的，则算法a 产生的拓扑是双向的。 双向连通性( b i d i r e c t i o n a lc o n n e c t i v i t y ) ：在由算法a 产生的拓扑中，如果存在 一条路( p o = u ，a ，1 p m = v ) 使得a 山b “， i = o ，l ，m - 1 ，其中 尼矿( q ) ，k = o ，1 ，m ，则节点“被称作与节点1 ，双向连通。( 表示为甜v ) 。并 且如果对于p y ( q ) ，u p 且p v , 贝i j u 营 ，。 3 2 网络模型 网络模型描述了无线网络及其节点设备的主要特征，如：设备位置、移动性 及其分布特征，设备无线发射接收能力。通过这些特征提取，从而获得网络的数 学描述。本研究首先假设一组节点矿= v l ，屹，) ，随机均匀分布在2 维空 间，表示节点v t 的最大传输距离( 在异构网络中，所有节点的最大传输距离不 一定相同) 。设：，血= 脚帆。y 瓴) ，雠= 耿砜。矿纯) 。通常，网络的初始拓扑由节点 的最大功率发射组成一个简单的有向图g = ( y ( g ) ，e ( g ) ) ，其中， e ( g ) = ( “，) ：d ( u ，1 ，) 吒，材，v y ( g ) ) 是图g 的边，d ( u ，v ) 表示节点甜和节点v 之间 的欧式距离。注意：( “，) 是一对有序的节点组，表示边从节点u 到节点v ，每个节 点有一个唯一的i d 号( 比如i p m a c 地址) ，文中，为了使讨论方便，假设r e ( v , ) = fo 假设无线信道是对称的，节点具有相同的路径损耗模型，即无线信号的功率 按照发送天线和接收天线之间距离的口次方衰减【3 9 1 ，a t 2 ，口取决于无线传播模 型。对于自由空间( f r e es p a c e ) 模型m 】，口- - 2 。发送功率# 与接收功率e 的关系为： z ：p , g , g , 2 - 2( 3 1 ) 。( 4 蒯) 乞 其中，g ，、g ，分别是发送、接收天线的增益，旯波长，d 是发送天线与接收 天线之间的距离。对于双线( t w o r a y ) 模型1 4 0 1 ，口发送功率与接收功率只的 关系为： p = 芈2 h 2 ( 3 2 ) 节点通过信道检测节点之间链路的状态从而发现拓扑的变化。如：采用邻节 点发现协议定期地发送h e l l o 消息来确定链路断开、单向链路、双向链路，h e l l o 消 息中可以包括节点i d 、位置以及其邻节点信息。对于双向链路( “，) ，材和1 ，之间 1 4 重庆大学硕士学位论文3 经典拓扑算法分析 相互可达，如果”可达v ，而v 不可达“则产生了“到v 的一条单向链路。例如，在 图3 1 中，衍日j 2 _ 间是一条双向链路，而z 到k 形成了一条单向链路。 图3 1 单向链路和双向链路 f i g3 1u n i d i r e c t i o n a ll i n ka n db i d i r e c t i o n a ll i n k 3 3 节点功率控制类型算法 拓扑控制算法是实现拓扑控制的计算方法，良好的拓扑控制算法将获得计算 时间、空间和通讯需求的优势。文献【lo 】提出一种基于邻近图m s t 模型的 l m s t ( l o c a lm i n i m u ms p a n n i n gt r e e ) 节点功率控制算法。文献中定义m s t 如下： 图g ( v ，毋的子图e 。为一棵包含了g 所有顶点的树。昱的所有边的权值的和称为 e 的权值，则最小权值树称作图g 的最小生成树( m i n i m u ms p a n n i n gt r e e ，m s t ) 。 在l m s t 算法中，任意一个节点“在发送半径范围r 内探测确定自身的邻居 节点集合孵，节点”及其邻居节点集合孵之间的连线构成邻居子图货。图雠中 边的权值是以边的长度，即边的两个端点之间的欧氏距离来确定的。因为无线通 信中，能量消耗e 和距离d 的关系满足式e = k d “，其中，参数刀的取值范围为 2 刀4 。这意味着随着通信距离的增加，能耗急剧增大。e 严格随d 增大而增大， 因此可以使用d 作为边的权值。对节点( 鞠，m ) ，( 嘞，坞) 通过以下的公式确定唯 一的权值d 。： d ( ，v 1 ) d 。( 甜2 ，v 2 ) 车d ( u l ，啊) d ( u 2 ，屹) o r ( d ( 嘶，m ) = d ( u 2 ，v 2 ) & & m a x i d ( u 1 ) ，搿( ) m a x i d ( u 2 ) ，i d ( v 2 ) o r ( d ( u l ，h ) = d ( u 2 ，v 2 ) & & m a x i d ( u 1 ) ，泫( v 1 ) ) m a x i d ( u 2 ) ，耐( 吃) & & m i n i d ( u 1 ) ，埘( m ) ) m i n i d ( u 2 ) ，i d ( v 2 ) 这样以d 作为权值，在钟范围内进行最小生成树算法得到本地最小生成树 瓦。磷中各节点将生成的最小生成树瓦上与自身距离为一跳的节点设为邻居节 点，并调整发射功率为达到最远邻居节点的功率，减少网络中不必要的链路，从 重庆大学硕士学位论文3 经典拓扑算法分析 而形成网络拓扑。 在l m s t 算法中，假设每一个节点都有个唯一的i d ，并且知道自身的位置， 具有全向天线。假设信道是对称的，无线信号在传播中无障碍。l m s t 算法中网络 拓扑的建立主要分为三个阶段： 信息交换：首先节点以最大功率发射，形成最大功率拓扑。每个节点材通过 周期性发送h e l l o 消息获得孵内所有节点的信息，包括节点的仍，方位。这些定 期的信息可以在任何数据信道或在一个单独的控制信道发送。发送h e l l o 信息的时 间间隔决定节点移动水平或者网络模型。 拓扑结构：可见邻近孵的信息获取之后，每个节点甜独立地用p r i m 算法在 图诺中获取它的本地最小生成树瓦= ( 1 ，( 瓦) ，e ( 瓦) ) ，p r i m 算法的时间复杂度为 o ( n l o g n + e l o g 功= o ( e l o g n ) ，在图瓯中刀是节点数，e 是边数。 传输功率的决定：磷中各节点将生成的最小生成树瓦上与自身距离为一跳 的节点设为邻居节点，并调整发射功率为达到最远邻居节点的功率， 算法特点总结：在l m s t 算法中，每个节点根据其本地拓扑结构( 由一跳邻 居节点形式的拓扑) ，计算最小生成树，然后使其直接的一跳内的节点成为其邻居， 最后把节点的传输半径设为到达其邻居最远的一跳邻节点所需距离。 l m s t 算法的缺点：l m s t 算法导出的拓扑维护了网络的连通性。节点的平均 传输半径小并且每个节点的节点度( d e g r e e ) 一般不超过6 。虽然l m s t 算法建立 的拓扑具有较高的功率有效性但维护困难，每个节点需要定期地运行该算法以保 障网络的连通性。 3 4 层次型拓扑控制算法 3 4 1 分簇结构的层次型网络拓扑控制算法 层次型拓扑控制方法，即重新安排活动链路或邻节点，形成一个层次型的网络 拓扑结构，并假设处于上层的节点具有特殊的功能。即在网络节点中形成一种层次 关系，构成一个层次型的网络。目前主要有两种研究手段，即采用支配集的层次型网 络和采用分簇结构的层次型网络。 采用簇结构的层次型结构：簇结构和支配集相关但略有不同，其思想就是将网 络划分成簇( c l u s t e r s ) 。簇是包括原始网络中所有节点的节点集的子集，每个簇中有 簇首( c l u s t e rh e a d s ) ，它是簇的代表，每个簇内的节点距离簇首一般只有一跳。把些 节点标记为具有特殊的功能，如控制其邻节点等，这样就形成了簇，这个具有特殊功 能的节点就叫做簇首。这种分簇方法的优点与骨干节点类似，但是更着重于本地资 源的优化使用，能够屏蔽网络高层的动态特性，使高层协议更具有可扩展性，另外簇 首还能够进行本地数据融合、压缩任务。 1 6 重庆大学硕士学位论文3 经典拓扑算法分析 文献【2 5 】提出的l e a c h ( 1 0 we n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 算法是第个 无线传感器网络分簇算法，也是最流行的分簇算法之一。其主要思想是：在簇的建立 阶段，相邻节点动态的形成簇，随机产生簇头；在数据通信阶段，簇内节点把数据发送 给簇头，簇头进行数据融合，最后把结果发送给汇聚节点。簇头要完成数据融合和汇 聚节点通信工作，其能量消耗必然大于其他节点。为了提高网络的生命周期，必须 均衡网络的能量分配，因此对簇头的选取必须是动态的。 l e a c h 中簇头选举算法如下：节点产生一个o 1 的随机数，如果这个数小于 阈值r ( 疗) ，则发布自己成为簇头的公告消息；在一轮循环中，如果节点已经当选 过簇头，则把7 ( 刀) 设置为0 ，这样该节点不会再次当选簇头；对于未当选过簇头的 节点，则将以丁( 刀) 的概率当选，t ( n ) 可用下列公式表示： f ! ，聘g 丁( 功= l 一研，m o d ( 1 p ) 】7( 3 3 ) i o ，其他 其中，p 是簇头在所有节点中所占的百分比，厂是选举轮数，r r o o d ( i p ) 代 表这一轮循环中当选过簇头的节点个数，g 是这一轮循环中未当选过簇头的节点集 厶 口o l e a c h 算法只是对簇头的选取做了说明，但是没有解决在随机簇头产生过程 中可能发生的网络分裂问题，即在某个节点的覆盖范围内可能没有可供使用的簇 头。另一个更为严重的问题是路由问题，使用分簇网络结构的目的是简化大型网络 中的寻址和路由问题，但目前还不清楚如何在多个簇头节点发生变化的情况下保持 路由信息的正确性。 3 4 2 支配集的层次型网络拓扑控制算法 采用支配集的层次型网络：在网络中选出一些虚拟骨干节点组成虚拟骨干网， 这些节点又叫做支配集。在图论中，支配集定义为：顶点集d 是图g = ( y ，目的 支配集当且仅当对任意“v d 存在1 ，d 使( u ，v ) e 。最小支配集问题是对给定 图g 找出使idi 最小的支配集d 。支配集节点之间相互通信以及支配集与其邻节点 之间可以进行通信，这样能够保证网络的连通性。而这个支配集在某种程度上应 该尽量小，这也是最小支配集问题( m i n i m u md o m i n a t i n gs e t ，m d s ) 。文中以t o p d i s c 算法【3 7 】为例进行分析。 t o p d i s e ( t o p o l o g yd i s c o v e r y ) 算法借鉴了图论中的思想，是基于最小支配集问 题【3 8 】的经典算法，在t o p d i s c 算法中，由网络中的一个节点启动发送用于发现邻居 节点的查询消息。查询消息携带发送节点的状态信息。随着查询消息在网络中传 播，t o p d i s c 算法依次为每个节点标记颜色。最后，按照节点颜色区分出簇头节点， 并通过反向寻找查询消息的传播路径在簇头节点之间建立通信链路。簇头节点管 1 7 重庆大学硕士学位论文3 经典拓扑算法分析 辖自己簇内的节点。 t o p d i s c 算法中提出了两种具体的节点状态标记办法，分别称为三色算法和四 色算法。这两种算法有两个相同特点： 利用颜色标记理论找到簇头节点； 利用与传输距离成反比的延时，使得一个黑色节点( 即簇头节点) 覆盖更 大区域。三色与四色算法的区别在于寻找簇头节点的标准不一样，所形成的拓扑 结构也有所不同。 这里我们重点讨论三色算法。在三色算法中，节点可以处于三种状态，分别 是自，黑和灰三种颜色表示。白色节点代表未被发现的节点；黑色节点代表成为 簇头的节点；灰色节点代表簇内结点。所有节点被初始化为白色，由一个初始节点 发起t o p d i s e 算法，算法执行完毕后所有节点都将被标记为黑色或者灰色。 三色算法的具体过程如下： 初始节点将自己标记为黑色，并广播查询消息。 白色节点收到黑色节点的查询消息时变为灰色，灰色节点等待一段时间， 再广播查询消息，等待时间的长度与它和黑色节点之间的距离成反比。 当自色节点收到一个灰色节点的查询消息时，先等待一段时间，等待时间 的长度与这个白色节点到向它发出查询消息的灰色节点的距离成反比。如果在等 待时间内，又收到来自黑色节点的查询消息，节点立即变成灰色节点，否则节点 变为黑色节点。 当节点变成黑色或者灰色后，它将忽略其他节点的查询消息。 通过反向查询消息的传播路径形成骨干网，黑色节点成为簇头，灰色节点 成为簇内节点。 下图3 2 所示的例子为算法执行完毕后网络拓扑结构的局部拓扑图，假设三色 算法由节点a 发起，它将自己标记为黑色，并发送查询消息；节点b ，c 收到节点a 发 送的查询消息，将自己标记为灰色，并等待一定时间再次广播这个查询消息。由 于节点b 比节点c 距离节点a 更远，所以节点b 先开始发送查询消息；节点岛d 收 到来自灰色节点b 的查询消息后，等待一段时间，由于节点d 比节点e 距离节点b 更 远，所以节点d 先超时，并将自己标识为黑色，继续向外发送查询消息；这时节点 e 收到来自节点d 的消息，所以停止自己的等待时间，变为灰色；算法如此进行下 去。算法运行到网络边缘后，将按照查询消息发送的路径进行回溯，构建网络的 转发链路。在此过程中，黑色节点将得知通过哪些灰色节点可以与周围的黑色节 点通信。算法执行完毕后，标记为黑色的节点a , d 成为簇头节点。标记为灰色的节 点c ，b ，e 成为簇内节点。从图中可以看到两个黑色簇头节点a , d 通过一个灰色簇内节 点b 进行通信，保证了簇与簇之间的连通。 1 8 重庆大学硕士学位论文3 经典拓扑算法分析 图3 2t o p d i s c 算法示意图 f i g3 2i l l u s t r a t i o nf o rt o p d i s ca l g o r i t h m t o p d i s c 算法很好地继承了图论中的经典思想，它使节点在密集部署的网络中 快速地形成分簇结构，并在簇头之间建立树型关系。但是由这种算法构建成的层次 型网络灵活性不强，重复执行算法收敛速度慢，开销过大，算法中也没有考虑到节点 的剩余能量。 3 5 休眠机制与拓扑管理算法 休眠机制中，一些节点按规律处于节能状态，这些休眠节点不参与网络拓扑。 拓扑管理算法在保证网络连通性前提下，实行节点休眠控制。文献【2 6 】设计了一种 覆盖配置协议( c o v e r a g ec o n f i g u r a t i o np r o t o c o lc c p ) 来达到网络睡眠节点数最大化 的休眠调度效果。 c c p 算法是一个典型的休眠调度算法。它的基本思想是在保持k 连通和k 覆 盖的条件下使睡眠节点最大化。这个算法目的是使睡眠节点最大化，这样就减少 了节点的不必要工作时间，也就降低了网络能量的消耗。c c p 基于这样一个定理( 当 然是理想情况下的结论) ：当发射半径大于或等于感知半径的2 倍时，如果一个网络 七覆盖一个凸区域，那么这个网络必然是k 连通的。这样，c c p 就可以通过保证覆 盖度来保证连通度。如果一个节点的监测区域已被其他节点k 覆盖，那么它就进入 睡眠状态，否则进入工作状态。 c c p 节点不必检查它的感知区域内的每一个点是否被其他节点k 覆盖。x i n g 等人通过一个定理给出了一个凸区域么被个节点的集合k 覆盖的充分条件： ( 1 ) 节点与节点之间以及节点与边界之间存在交点； ( 2 ) 节点间的所有交点至少是被k 一覆盖的： ( 3 ) 节点与边界之间的所有交点至少是被k 覆盖的。其中，两个节点的交点是 指两个节点的感知圆的交点，节点与边界的交点是指节点的感知圆与区域边缘的交 1 9 重庆大学硕士学位论文 3 经典拓扑算法分析 点。 基于这个定理，x i n g 等人给出了通过少数点来判断一个节点的感知区域是否被 其他节点七覆盖的算法。该算法的时间复杂度为o ( n 3 ) ，其中，是2 倍于感知半径 内的节点数。 c c p 协议中节点有3 个基本状态：工作状态、侦听状态和睡眠状态。此外，为 了避免由于每个节点根据局部信息独立进行调度而引起的冲突，c c p 引入了加入 和退出两个过渡状态。 初始时，网络中节点都处于工作状态。当处于工作状态的节点如果收到一个 h e l l o 消息，它就检查自己是否符合睡眠的条件，如果符合条件，就进入退出状 态并启动退出计时器。在退出状态，如果计