（计算机软件与理论专业论文）无线传感器网络的拓扑控制算法研究.pdf

无线传感器网络的拓扑控制算法研究 中文摘要 中文摘要 无线传感器网络是近年来兴起的一种重要的信息获取技术，它可以使人们在任 何地点、任何时间和任何环境中获取大量实时可靠信息。因而，可被广泛应用于许 多领域，并已成为一个研究热点。 拓扑控制是无线传感器网络的一个关键基础技术，它在满足网络要求的覆盖度 和连通度的前提下，通过睡眠调度、功率控制和邻节点选择，形成一个优化的网络 结构，从而延长网络服务时间、降低干扰和提高吞吐量；同时，它也为其它功能模 块提供基础。本文从两个方面研究了拓扑控制问题。 许多高效的路由协议依赖于网络拓扑的可平面性，然而已有的可平面拓扑构造 均采用静态方式为整个网络构造一个固定的拓扑，忽略了随时间和空间变化的通信 量大小和信道状态以及节点的剩余能量的影响。针对该问题，本文提出一种可调节 的可平面拓扑( t a p ) 构造算法。该算法基于节点邻近关系，依据一定规则剔除网 络中的链路。运行构造算法的节点可根据变化的网络因素，通过一个参数r 动态调 节网络的拓扑结构。分析和仿真表明，t a p 是可平面的、连通的、对称的和稀疏的； 当所有节点的参数f = 1 时，能保留所有能耗最低路径；发射功率、干扰和节点度随 f 的增加而减少；当所有节点的参数f - 3 时，最大度不超过6 。 目前提出的在三维传感器网络中保持网络覆盖度和连通性的拓扑控制方法仅适 用于同构网络，且只能保证1 一连通。针对该问题，本文从理论上分析了在异构三维 传感器网络中保持m 覆盖、保持肛连通和降低发射功率的充分条件，并将这些充分 条件抽象为几条规则。基于这些规则，提出种综合的保持m 覆盖和肛连通的拓扑 控制算法，同时考虑了睡眠调度和功率控制。仿真表明，该拓扑控制算法在保证所 要求的连通度和覆盖度的前提下，可有效延长网络生存周期。 关键字：无线传感器网络；拓扑控制；自适应控制；可平面图；连通；覆盖 作者：张招亮 指导老师：张广泉 a b s t r a c tr e s e a r c ho na l g o r i t h m sf o rt o p o l o g yc o n t r o li nw i r e l e s ss e n s o rn e t w o r k s a b s t r a c t i nr e c e n ty e a r s ，w i r e l e s ss e n s o rn e t w o r kh a sb e c o m eap o p u l a ra n di m p o r t a n t t e c h n i q u eo fi n f o r m a t i o na c q u i s i t i o n ，w h i c he n a b l e sp e o p l et o c o l l e c tv a r i o u sr e l i a b l e ， r e a l - t i m ed a t aa n y w h e r e ，a n yt i m e ，u n d e ra n yc i r c u m s t a n c e s h e n c e ，i th a sl o t so f p o t e n t i a la p p l i c a t i o n si nv a r i o u sf i e l d s ，a n dt h u sh a sb e c o m ea l la c a d e m i ch o ts p o t t o p o l o g yc o n t r o li so n eo ft h ek e yf u n d a m e n t a lt e c h n i q u e si nt h ed e s i g no f w i r e l e s s s e n s o rn e t w o r k s ，w h i c h ，u n d e rt h ec o n d i t i o no fp r e s e r v i n gr e q u i r e dd e g r e eo fc o v e r a g e a n dc o n n e c t i v i t y , h e l p ss e n s o rn o d e st of o r ma no p t i m i z e dn e t w o r kt o p o l o g yt h r o u g h s l e e ps c h e d u l i n g ，p o w e rc o n t r o la n dn e i g h b o rs e l e c t i o n a f t e rt o p o l o g yc o n t r o li sa p p l i e d ， t h en e t w o r kl i f e t i m ei sp r o l o n g e d ，i n t e r f e r e n c er e d u c e d ，a n dt h r o u g h p u ti n c r e a s e d a tt h e s a n l et i m e ，t o p o l o g yc o n t r o lc a np r o v i d et h en e t w o r ki n f r a s t r u c t u r er e q u i r e db yo t h e r f u n c t i o n a lm o d u l e f o c u s i n go nt w op r o b l e m s ，w es t u d yo nt h et o p o l o g yc o n t r o li n w i r e l e s ss e n s o rn e t w o r k si nt h i st h e s i s m a n ye n e r g y - e f f i c i e n tr o u t i n gp r o t o c o l sd e p e n do nt h ep l a n a r i t yo ft h en e t w o r k t o p o l o g y , h o w e v e r , p r e v i o u sp l a n a rt o p o l o g i e sw e r ec o n s t r u c t e ds t a t i o n a r i l yi naf i x e d m a n n e ro n an e t w o r k w i s eb a s i s ，w h i c hn o to n l yn e g l e c t st h ei n f l u e n c e so ft h et r a f f i ca n d c h a n n e ls t a t u sv a r y i n ga c c o r d i n gt ot i m ea n ds p a c e ，b u ta l s ot h a to ft h er e s i d u a le n e r g yo f s e n s o rn o d e s t oa d d r e s st h i sp r o b l e m ，w ep r o p o s eat - a d j u s t a b l ep l a n a rs t r u c t u r e ， d e n o t e db yt a p , a n di t sc o n s t r u c t i o na l g o r i t h mi nt h i st h e s i s t h i ss t r u c t u r ei sb a s e do n t h ep r o x i m i t yo fn e i g h b o r i n gn o d e sa n dr e m o v e sl i n k sa c c o r d i n gt os p e c i f i cr u l e s s e n s o r n o d e sr u n n i n gt h ec o n s t r u c t i o na l g o r i t h mc a na d j u s tt h et o p o l o g yb yp a r a m e t e rf a c c o r d i n gt o l o c a ln e t w o r kd y n a m i c s w ep r o v e b ya n a l y s i sa n ds i m u l a t i o n s o m e i m p o r t a n tp r o p e r t i e so ft a p t a pi sp l a n a r , c o n n e c t e d ，s y m m e t r i ca n ds p a r s e ；t a pi s g u a r a n t e e dt oc o n t a i nt h em i n i m u me n e r g yc o n s u m p t i o np a t hb e t w e e na n yp a i ro fn o d e s w h e na l ln o d e sh a v e ，= 1 ；t h et r a n s m i s s i o np o w e r , i n t e r f e r e n c ea n dn o d ed e g r e ed e c r e a s e a sfi n c r e a s e s ；i na d d i t i o n ，m a x i m u mn o d ed e g r e ei nt a pi sb o u n d e db y6w h e na l ln o d e s h a v ef = 3 e x i s t i n ga p p r o a c h e s t om a i n t a i nn e t w o r k c o v e r a g e a n d c o n n e c t i v i t y i n u r e s e a r c ho na l g o r i t h m sf o rt o p o l o g yc o n t r o li nw i r e l e s ss e n s o rn e t w o r k sa b s t r a c t t h r e e - d i m e n s i o n a ls e n s o rn e t w o r k sa r eb a s e do nt h ea s s u m p t i o no fh o m o g e n e o u ss e n s o r n o d e sa n do n l yg u a r a n t e e1 - c o n n e c t i v i t y t or e s o l v et h i sp r o b l e m ，w et h e o r e t i c a l l y a n a l y z et h es u f f i c i e n tc o n d i t i o n st om a i n t a i nm c o v e r a g e ，k - c o n n e c t i v i t y , a n dr e d u c e t r a n s m i s s i o np o w e ri nt h r e e - d i m e n s i o n a lh e t e r o g e n e o u ss e n s o rn e t w o r k s ，d e r i v i n gs o m e d e s i g nr u l e s b a s e do nt h e s er u l e s ，w et h e nd e s i g n e da ni n t e g r a t e dt o p o l o g yc o n t r o l a l g o r i t h mt om a i n t a i nk - c o n n e c t i v i t ya n dm c o v e r a g ew h i c h t a k e si n t oa c c o u n tb o t hs l e e p s c h e d u l i n ga n dp o w e rc o n t r 0 1 t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m e f f i c i e n t l yp r o l o n g sn e t w o r kl i f e t i m ew h i l ep r e s e r v i n gr e q u i r e dn e t w o r kc o n n e c t i v i t ya n d c o v e r a g e k e y w o r d s ：w i r e l e s ss e n o rn e t w o r k s ；t o p o l o g yc o n t r o l ；a d a p t i v ec o n t r o l ；p l a n a rg r a p h ； c o n n e c t i v i t y ；c o v e r a g e i i i w r i t t e nb yz h a n gz h a o l i a n g s u p e r v i s e db yz h a n gg u a n g q u a n 图表索弓 无线传感器网络的拓扑控制算法研究 图表索引 图1 1无线传感器网络的体系结构1 图1 2 传感节点的组成2 图2 1图的概念示例7 图2 2 原始网络拓扑8 图2 3 平面式拓扑结构示例：。8 图2 4 分簇式拓扑结构示例9 图2 5支配集拓扑结构示例9 图3 1t a pb a s i c 定义的解释图2 0 图3 2 定理3 6 证明过程解释图_ 2 3 图3 3 定理3 7 证明过程解释图2 4 图3 4 二维仿真场景的原始拓扑3 0 图3 5 二维仿真场景的t a p 结构1 3 0 图3 - 6 二维仿真场景的t a p 结构2 3 1 图3 7 能量扩展因子3 2 图3 8 平均最大边长和平均边长3 2 图3 - 9 平均干扰3 3 图3 1 0 平均节点度3 3 图4 1c i r ( i ，力和c a p ( i ，d 3 9 图4 2 特殊情况3 9 图4 3c a p ( j ，0 被各曲线段分割4 1 图4 4c ct a b l e 的p a r t i a l 表项4 7 图4 5c a p ( i ，力球面覆盖度计算方法4 8 图4 6 三维拓扑控制算法状态转换图。5 2 图4 7 活节点数目的比较5 5 图4 8 连通度的比较5 5 图4 9 覆盖度的比较5 6 图4 1 0 网络生存周期的比较5 6 i v 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 鲨丝! 整 日 期：盘磐亟：主 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：雩苡招勃日 钠一：绁日 导师签名：“ 4 日 一7 一 无线传感器网络的拓扑控制算法研究第一章绪论 1 1 引言 第一章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 是随着传感器、嵌入式、分布 式信息处理技术和无线通信技术的飞速发展而新兴的一种信息获取技术，它允许人 们实时、直接地感知物理世界，获得人们想要的信息。因而，这种网络系统可被广 泛应用于国防军事、灾难预警、环境监测、精细农业、交通管理、仓储跟踪、入侵 检测、医疗卫生等许多领域，引起了各国军事部门、学术界和工业界的极大重视。 美国商业周刊将它称为未来四大高科技产业之一，m i t 技术评论也将其列入改 变世界的1 0 大新技术之一【1 1 。 无线传感器网络的典型体系结构如图1 1 所示，它通常包括大量传感节点( s e n s o r n o d e ) 矛i1 个汇聚节点( s i n kn o d e ) 。用户通过主机来获取信息和对网络进行控制，汇 聚节点和主机之间通过无线链路或有线链路相连。各传感节点部署在监测区域后， 以自组织的方式形成一定的网络拓扑，传感节点获取数据后以多跳方式将数据转发 给汇聚节点，汇聚节点再将数据发送给主机。用户也可以向网络发出命令，对网络 进行管理或发布监测任务。 汇聚节点 传感节点监测区域 服务器 管理员，用户 图1 1 无线传感器网络的体系结构 单个传感节点的组成如图1 2 所示【2 1 ，它通常包含传感器模块、处理器模块、 第一章绪论无线传感器网络的拓扑控制算法研究 无线通信模块和能量供应模块四部分。传感器模块负责采集数据和进行数据转换； 处理器模块负责加工数据和控制各模块；无线通信模块负责无线通信和收发数据； 能量供应模块通常采用电池供电。传感节点的设计都致力于使每个传感节点成本非 常低廉，所以节点所配置的处理器模块和无线通信模块性能都较低，此外，节点电 池电量也较少。 能量供应模块 图1 2 传感节点的组成 无线传感器网络的工作方式和廉价的硬件配置使无线传感器网络具有一些不同 于已有无线网络的显著特点，这些特点直接决定了如何为这种网络设计各种算法和 协议。其中，主要特点有： ( 1 ) 能量有限。能量限制是最大的约束，传感器网络的首要设计目标是降低能 耗。各模块中无线通信模块消耗的能量最大，而无线通信模块中发送数据和接收数 据时的能耗通常是最大的。因而，网络协议和算法的设计必须要尽量减少不必要的 收发，并尽量使节点处于睡眠状态。 ( 2 ) 计算和存储能力有限。要求各种协议和算法不能占用过多计算和存储资源。 ( 3 ) 通信能力有限。既是收发机硬件能力的约束，也是复杂的信号传播环境所 决定的。 ( 4 ) 多跳通信。主要是为了降低能量消耗，同时也是因为节点通信能力有限。 ( 5 ) 自组织自配置。网络必须能适应因通信环境的变化、节点死亡、节点移动 及新增节点等导致的网络拓扑的变化。 ( 6 ) 以数据为中心。用户关心的是感兴趣的数据，而不是从哪个节点获得的数 据。 ( 7 ) 节点数量多和密度高。网络设计时应该充分利用数量多和密度高带来的冗 余性优点来提高网络鲁棒性和服务质量。 2 无线传感器网络的拓扑控制算法研究第一章绪论 1 2 研究背景与意义 传感器网络的节点密度通常较高，如果每个节点都以最大功率进行通信，将会 使节点之间的通信相互干扰，不但造成巨大的重传能量开销，同时也影响网络的吞 吐量和延迟。此外，若与过多的邻节点直接通信，当节点移动时，节点为了维护邻 节点关系会带来许多不必要的能量开销，同时也会使路由协议频繁地更新路由。而 拓扑控制正是解决这些问题的重要手段之一。 拓扑控$ 1 j ( t o p o l o g yc o n t r 0 1 ) 是无线传感器网络的一个关键基础技术，它是在满 足应用要求的网络覆盖度和连通度的前提下，通过睡眠调度、功率控制和邻节点选 择，形成一个优化的数据转发网络结构，达到延长网络服务时间、提高吞吐量并为 其它功能模块提供基础的目的。 在无线传感器网络中，拓扑控制具有十分重要的意义，主要体现在以下几个方 面： ( 1 ) 延长网络生存时间。拓扑控制可以将部分冗余节点转入睡眠状态，以使节 点轮流工作。同时，也可以降低节点的发射功率以节省能量开销，所以延长了整个 网络的生存时间。 ( 2 ) 减少通信干扰。拓扑控制使节点降低发射功率，从而缩小了信号的干扰范 围，降低了节点之间的相互干扰。 ( 3 ) 提高吞吐量和减少网络延迟。当网络负载较高时，采用低发射功率比高发 射功率具有更小的竞争，因而就相对提高了吞吐量和减少了网络延迟。而低负载时， 网络中竞争较小，高发射功率可以减少数据转发的跳数，从而提高了吞吐量并减少 了延迟。 ( 4 ) 为m a c 层提供基础。许多无线传感器网络的m a c 协议【3 ，4 】都要求接收方 回复c t s 或a c k ，拓扑控制可以保证链路的对称性，从而避免了单向链路带来的 复杂性。而且，一些基于时分复用的m a c 协议【5 ，6 】依赖于簇或树状拓扑。 ( 5 ) 为路由协议提供基础。拓扑控制可以根据网络流量和信道状态动态调整网 络结构，剔除能量代价过大或干扰较大的路径，因而基于优化后的网络结构的路由 具有更高的能效和更好的性能。此外，有些路由协议对网络拓扑有一定的要求。比 如地理路由【7 9 1 依赖于网络拓扑的可平面性，虚拟极坐标路由【l o 】必须运行在以汇聚 节点为根的带环树拓扑上。 第一章绪论无线传感器网络的拓扑控制算法研究 ( 6 ) 为数据融合提供基础。簇或树状拓扑本质地有利于数据融合 1 1 , 1 2 1 ，数据融 合时传感节点将采集到的数据发给簇首节点( 或树中父节点) ，由簇首节点( 或树中 父节点) 进行数据融合，并将融合后的结果向汇聚节点转发。而成簇和构造树正是 拓扑控制的研究问题之一。 ( 7 ) 对其它模块的影响。例如可通过限制与被攻破节点通信为安全管理模块提 供协助1 3 1 。 1 3 本文研究内容 可平面拓扑的构造是传感器网络拓扑控制的一个重要问题，许多高效路由算法 7 , 8 1 都依赖于拓扑的可平面性。然而，目前提出的可平面拓扑的构造方法都采用静态 方式为整个网络构造一个固定的拓扑，无法适应动态变化的网络流量、信道状态和 节点剩余能量等因素，因而会导致能效降低，影响网络生存时间。针对这一现状， 本文将提出一种可用于节点自适应地控制拓扑的拓扑控制算法。三维传感器网络是 目前传感器网络领域前沿问题之一，这一领域的研究刚刚开始。目前已有的在三维 传感器网络中保持连通度和覆盖度的拓扑控制算法仅适用于同构网络，且只能保证 拓扑是1 连通的。因而无法解决在异构三维传感器网络中如何保持m 覆盖和红连通 的问题，本文将深入分析该问题，并提出有效的拓扑控制算法。具体的研究内容如 下： ( 1 ) 归纳了拓扑结构的评价指标，将已有拓扑控制算法进行了分类总结。 ( 2 ) 定义了一种新的二维可平面拓扑结构，并对其进行理论分析。基于这种新 的可平面结构提出一种二维可调节的可平面拓扑构造算法，对该拓扑结构各项指标 进行了理论分析，并通过仿真评估其可调节的特性。 ( 3 ) 对异构三维传感器网络中保持m 覆盖、肛连通和进行功率控制问题进行理 论分析，提出若干规则，这些规则从球面覆盖度的角度保证m 覆盖，从节点间不相 交路径数的角度保证舡连通和功率控制的有效性。这些规则反映了这些问题的本质， 既是对相关问题已有大多数工作的一般化，也可用于以后解决相关问题。 ( 4 ) 基于这些规则，提出了球面覆盖度的计算方法和功率控制算法。并设计了 一个综合考虑睡眠调度和功率控制的异构三维传感器网络的拓扑控制算法，该算法 能够保持m 覆盖和肛连通。最后，进行仿真证实了算法的有效性。 4 无线传感器网络的拓扑控制算法研究 第一章绪论 1 4 本文组织结构 本文内容组织如下： 第一章绪论，简要描述了传感器网络，介绍了课题的研究背景和意义，并对本 文的主要工作给出了概要说明。 第二章拓扑控制理论基础及相关研究，首先给出本文涉及到的主要图论知识， 并对拓扑控制的基本概念进行了介绍，然后归纳了拓扑结构的评价指标。最后对目 前的研究工作进行了分类总结。 第三章二维可调的可平面拓扑构造算法，在分析了二维可平面拓扑的构造应具 备可调节特点后，定义了一种简单的带参数的可平面结构，并对它的主要指标进行 了理论分析。然后基于这种可平面结构，提出了一种二维可调节的可平面拓扑结构 构造算法，并对各种指标进行了分析和证明。最后给出了仿真结果。 第四章三维异构m 覆盖舡连通的保持条件和算法，先对问题进行了描述，并介 绍了覆盖相关的一些研究背景。接着，对保持m 覆盖、肛连通和降低发射功率的条 件进行了分析，提出几条规则。然后，给出了本文实现对应规则的方法和算法，并 提出一个保持m 覆盖和红连通的拓扑控制算法，最后给出了仿真结果。 第五章对本文的工作进行了总结，并展望了本文工作中还需要进一步研究的地 方。 第二章拓扑控制理论基础及相关研究无线传感器网络的拓扑控制算法研究 第二章拓扑控制理论基础及相关研究 本章主要介绍与无线传感器网络拓扑控制相关的一些基本知识和对研究现状分 类总结。首先给出本文所涉及的主要的图论知识，并总结了拓扑控制的常用方法和 常见拓扑结构；然后归纳了拓扑结构的评价指标；最后对已有拓扑控制算法进行了 分类。 2 1 图论基础 网络的拓扑常以图的形式来描述，本文的讨论也将涉及一些图论知识，以下给 出相关的一些图论定义： 图：一个图g 是一个二元组 k 胗，其中y 是非空的顶点集合，e 是图中的边 集。通常将e 中的有向边记为 “，诊形式，而无向边( 或称双向边) 记为( “，v ) 形式。 关联：若e ee 是图中的一条边，且e = ，则称e 连接顶点“和顶点v ，或 者说顶点甜与边e 关联，同时也称顶点甜和顶点v 相邻接。 度：对于任一顶点f i e 以g 中与“相邻接的顶点的数目称为顶点的度，记作 硪甜) 。 子图：给定两个图g = 丁= ( e r ) 其中，g = ( k 目是原始网络结构，y 包含所有部署的且未死亡的传感节点，若节点 a 使用最大功率发射时可以将数据发送给节点b ，则有向边知，b e e ；t 为拓扑控制 后的网络结构，所圯e 7 1c e ，v r 中包含处于活动状态的传感节点，e 7 是拓扑控制 对e 精简后所得边集。 目前常用的拓扑控制方法主要包括：睡眠调度、功率控制和邻节点选择。 ( 1 ) 睡眠调度：因为传感器网络的布署成本相对于节点成本往往较大，所以初 始时常常冗余部署以免除增补节点带来的代价，另一方面传感器的覆盖范围和通信 范围难以精确确定，且常常动态变化，为保持足够的覆盖和连通必须要多布署一些 节点。因此传感器网络中节点通常具有冗余性，拓扑控制可以按照某种规则关闭部 分节点，使节点轮流工作，从而延长网络生存时间。采用这种方法后，l 吲si 吲。 ( 2 ) 功率控制：主要是指增加或减少节点的发射功率。节点无线信号的发射功 率与发送节点到接收节点的距离的幂函数成正比，所以降低发射功率有利于减少能 耗。此外，用大的发射功率通信会产生大的干扰，增加了冲突的概率。控制后的功 率可能被设置为足够到达最远的通信邻节点所需的功率，也可能在每次发送时，设 置为到达发送的目标通信邻节点所需的功率。通常采用该方法后，e 中与节点关联 7 第二章拓扑控制理论基础及相关研究无线传感器网络的拓扑控制算法研究 的长边被删去。 ( 3 ) 邻节点选择：指在所有物理邻节点中选择直接通信的逻辑邻节点，通常与 功率控制相配合。邻节点选择的目标有很多，例如为了降低发射功率，形成树、簇、 链结构，使拓扑具有对称性、可平面性等等。选择的规则取决于具体的目标。邻节 点选择体现为e 中与节点关联的某些边被删去。 事实上，借助移动节点修补拓扑也可能会成为一种不错的拓扑控制方法，但据 本文作者所知，目前国际上尚无相关研究。 借助这些方法，形成了传感器网络的目前主流的三类拓扑结构：平面式、分簇 式和支配集。这里没有考虑三维传感器网络拓扑结构，将在本章后面再介绍。 ( 1 ) 平面式拓扑结构：图2 。2 是一个原始拓扑结构，其中黑方块代表汇聚节点。 图2 3 是图2 2 的一个平面式拓扑结构示例。这类拓扑结构可能使用睡眠调度、功 率控制和邻节点选择三种方法中的一种或几种形成具有某些性质的拓扑结构，不一 定有v r = 以t 中节点通常属于平等关系。 图2 - 2 原始网络拓扑 图2 3 平面式拓扑结构示例 8 无线传感器网络的拓扑控制算法研究第二章拓扑控制理论基础及相关研究 ( 2 ) 分簇式拓扑结构：图2 4 为图2 2 的一个分簇式拓扑结构示例。通常只使 用邻节点选择，也可能使用功率控制。蜥= v ，通常将所中所有节点分成若干不相 交子集，每个子集称为一个簇( c l u s t e r ) ，每个簇中选取一个簇头节点。簇内结构有 两种：每个簇内节点到簇头只有一跳，簇内只保留簇内节点到簇头的边；簇内节点 到簇头有多跳。簇间连接也分两种：将簇头视为普通节点再分上层簇；通过簇内的 桥节点将簇连接起来保证网络的连通性。 图2 4 分簇式拓扑结构示例 ( 3 ) 支配集拓扑结构：图2 5 所示为图2 2 的个支配集拓扑结构示例。通常 只使用邻节点选择，也可能使用功率控制。蜥= n 存在连通节点子集d ，称为支 配集( d o m i n a t i n gs e t ) ，使得y 中的任意节点“要么在d 中，要么存在u 的l 跳邻节 点v 在d 中。同时，任意两个都不在d 中的节点之间不存在边属于e 7 。在例图2 5 中j 黑色节点为支配集中的节点。 图2 5 支配集拓扑结构示例 9 第二章拓扑控制理论基础及相关研究无线传感器网络的拓扑控制算法研究 2 3 评价指标 评价拓扑结构的主要指标如下： ( 1 ) 连通性。如果在原始拓扑图中，两个节点之间有一条路径存在，所构造的 拓扑结构必须也有一条路径连通这两个节点，但不一定是同一路径。连通性是必须 满足的，有的对可靠性要求较高的应用可能要求肛连通( 七 1 ) 。 ( 2 ) 能量效率。通常有两种方法可以减少能量消耗。一是尽量减少各个节点的 发射功率，减少邻节点数目。这样可将转发信包的能量消耗分摊在许多节点，且可 有效地避免热点发生，有利于延长网络生存周期，但是会导致路径长度增加。二是 在网络的层次上选择能耗最优路径以减少整个网络为传送单个信包所消耗的能量， 但是被反复使用的最优路径，及最优路径交叉的地方易造成热点，部分节点可能先 行耗尽能量，导致网络分裂，缩短了网络生存周期，尽管此时网络中总的剩余能量 不少。但是通过路由协议交替选择最优路径和次优路径可以减轻这种影响。两种方 法之间的折中取决于具体应用。 ( 3 ) 干扰。过大的干扰会引起大量信包冲突，导致重传，因而增加了能量消耗， 同时也抑制了通信量，延长了数据传送时间。但是，目前只有部分拓扑结构将低干 扰作为一个设计目标，许多工作都假设构造稀疏且节点度有界的拓扑可以降低干扰。 但是m a r t i nb 等人【1 4 】的结论表明这样的拓扑结构不足以降低干扰。 ( 4 ) 稀疏性。如果一个网络拓扑中链路的数目与节点数目成线性关系，称该拓 扑是稀疏的。许多传感器网络的路由协议建立在洪泛技术【1 5 ( f l o o d i n g ) 基石出i - ，保持 较少链路可以降低能量、计算和存储开销。而且，也有利于网络的可扩展性1 1 6 j 。 ( 5 ) 对称性。对称的拓扑结构要求所有的链路都是双向的。在非对称链路上的 通信不但复杂而且代价昂贵【1 7 】，所以许多通信原语要求通信链路必须是双向的。例 如，许多m a c 协议要求回复r t s 和a c k 给发送者。 ( 6 ) 节点度。拓扑的最大节点度应该是常数有界的，平均节点度也必须小。因 为，如果一个节点的度过高，会吸引过多的流量流向它，因而会加快它的能量消耗。 而且它也将消耗许多资源来保持这种邻居关系，比如当邻节点移动时，它需要更新 这些邻节点的位置。 ( 7 ) 可平面性。一个拓扑结构是可平面的仅当它可以被画在一个二维平面上， 且除了在端点外，任意两条边都不相交。许多地理路由协议，例如g p s r t ，a f r 列 l o 无线传感器网络的拓扑控制算法研究第二章拓扑控制理论基础及相关研究 等依赖于底层拓扑的可平面性来高效的转发信包。 ( 8 ) 分布式和局部化构造。一个算法是分布式和局部化的仅当算法所需要的所 有信息在它运行前都已经在数跳邻域内。所以，它不能进行迭代式的运算。只有分 布式和局部化的算法才适合传感器网络的规模大，能量、存储和计算资源有限的特 点。 除此之外，还有其它一些性质也很重要，例如，拓扑结构应具有较好的鲁棒性， 能够在位置信息估计不准确时仍有较好性能，能够处理节点移动性带来的问题，能 够在边界区域或节点分布不均匀时正常工作等等。 以上各种指标之间关系复杂，有的指标之间甚至存在冲突，因此，一个评价指 标的最优拓扑，不总是另一个评价指标的最优情况。如连通性和低节点度是矛盾的， 要保证较高的连通性通常意味着节点度不可能太小；稀疏性和能量效率之间存在矛 盾，如果希望保存所有能耗最低路径，网络通常不可能太稀疏；能量效率和低干扰 之间也是矛盾的，选择能量最优的路径不一定会是低干扰的。所以，不可能构造一 个固定的拓扑能同时优化所有指标，各种设计目标之间的取舍是应用相关的。 2 4 研究现状 目前关于拓扑控制的研究工作相当多， 拓扑；( 2 ) 分簇式拓扑；( 3 ) 支配集拓扑； 些有代表性的工作。 2 4 1 平面式拓扑控制 概括来说主要分为四大类：( 1 ) 平面式 ( 4 ) 三维网络拓扑。本节将分类介绍一 按照所采用的拓扑控制方法，可简单地将平面式拓扑控制算法分为功率控制、 邻节点选择和睡眠调度三种。 ( 1 ) 功率控制 这些算法只是在保持连通的前提下，尽最大的可能将发射功率降低，通常不做 其它考虑。 l m a 和l m n t l 8 】：l m a 使节点度保持在5 8 9 左右，然后将发射功率设置为一 个足以发射到最远的邻节点的功率。l m a 和l m n 只是计算邻节点的方法上略有不 第二章拓扑控制理论基础及相关研究无线传感器网络的拓扑控制算法研究 i 司。 l i n t i 挎】：l i n t 尝试把节点度保持在一个特定的值d d ( 实际上是保持在西、西 之间) 来保持网络的连通性。若当前度盔小于西或大于以时，调整发射功率为 岛= p c 一5 口l o g ( 竺9 “c 其中，肋为新功率值，鼽为当前功率值，反为信道损失指数。 l i l t 1 9 】：在一些情况下，可能有类似链路状态协议的全局信息存在，l i l t 算法 在l i n t 的基础上，充分利用这种全局信息。如果网络处于单连通状态下，则使离关 节点近的节点增大到最大能量。如果网络分裂了，所有节点将能量设置为最大值。再 慢慢将能量降低到一个合理值。 c o m p o w l 2 0 】：试图确定一个能保证网络连通性的最小公共发射功率。它是与 路由协议结合在一起的，每个节点为每个发射功率级别分别确定路由表，与最大发 射功率时的路由表有相同的入口数的最小发射功率将选为公共的发射功率。缺点是 需要保留所有潜在的邻节点的路由表。此外，某些孤立节点会导致很大的公共发射 功率，针对该问题，文献 2 1 提出了一种改进算法c l u s t e r p o w 。 ( 2 ) 邻节点选择 该类算法选择邻节点通常是依据某规则来构造一个邻近图。通常要与功率控制结 合。 r n g ( r e l a t i v en e i g h b o r h o o dg r a p h ) 2 2 】：对于任意节点甜，v 以边( 甜，v ) r n g ， 当且仅当不存在节点w ，使得i 删i l u v l 且1 w v l i u v l 。r n g 唯一且可平面。 g g ( g a b r i e lg r a p h ) 2 3 】：对于任意节点“，v v ，边( z ，v ) g g 当且仅当不存在节点 l u w l 2 + 1 w v l 2 l u v l 2 。g g 唯一且可平面，保留了所有能耗最低路径。 d t g ( d e l a u n a yt r i a n g u l a t i o ng r a p h ) ：是一个知名的邻近图结构，源自于d e l a u n a y b n 在2 0 世纪3 0 年代的研究工作。假设y 中任意4 个节点不共圆，若三角形a u v w d t g 仅当该三角形内不包含任何其他节点。x i a n g y a n gl i 等人给出了一个分布式算法构造 d t g l 2 4 ，2 5 1 。 y g ( y a og r a p h ) t 2 6 】：以任意节点“为中心画，z 条射线将平面等分为以个扇区，每个扇 区只保留一个离节点甜最近的邻节点做为通信的邻节点。通常n 芝6 ，y g 不唯一。 c b t c ( c o n e b a s e dt o p o l o g yc o n t r 0 1 ) 2 7 , 2 8 ：是第1 个仅依赖于角度信息而不需地 1 2 无线传感器网络的拓扑控制算法研究第二章拓扑控制理论基础及相关研究 理坐标的拓扑控制算法。任意节点1 1 不断增大发射功率，直到每个以a 为锥角的扇区内 存在一个邻节点或者已经达到最大发射功率。然后，再删去一些边：如果c o s t ( u ，v ) + c o s t ( v ，w ) q c o s t ( u ，w ) ，则去掉边( “，w ) 。c b t c 不唯一。 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 ) 1 2 9 】：任意节点甜首先收集它的一跳邻节点 1 ( “) ，然后，节点“计算最小生成树m s t ( n i ( u ) ) ，节点甜保持有向边 “，诊，当且 仅当( “，v ) m s t ( n 1 ( “) ) ，所有节点所得有向边就组成了l m s t 。l m s t 是非对称图， 但删除有向边可变对称图。l m s t 构造代价小，拓扑非常稀疏，平均节点度接近于2 ， 最大节点度不超过6 ，节点平均边长较小，且有利于降低m a c 层的竞争干扰。 e g ( e n c l o s u r eg r a p h ) 3 0 】：边( “，v ) e g ，当且仅当不存在节点r 使j ：导t l u r l 口+ t l r v l n + e t l u v l 口，其中f 为一常数。e g 保留了所有能耗最低路径，但不是可平面的，且非稀疏 图。 r - n e i g h b o r h o o dg r a p h 3q ：边( ”，v ) er - n e i g h b o r h o o dg r a p h ，当且仅当区域n r r ( u ， v ) 内不含其他节点。用d ( u ，i u v l ) 代表以u 为圆心，以l u v l 为半径的圆盘。区域n r ，(