论文研究-无线传感器网络的拓扑控制研究.pdf

所需积分/C币:15 2019-07-22 20:33:09 476KB .PDF
15
收藏 收藏
举报

讨论了拓扑控制的目标,利用随机图理论研究了无线传感器网络拓扑控制的模型及代表性算法;基于网络结构的不同,分析和比较了无线传感器网络中各种拓扑控制机制的特征;深层剖析了无线传感器网络拓扑控制与连通、调度之间的关系;最后对拓扑控制亟待解决的问题进行了总结和展望。
3216 计算机应用研究 过控制节点睴眠或活动状态来控制活动节点数量;b)通过控 4)CBTC算法 制某些链路的使用状态来减少通信链路的数量。从路由的方 LIi等人提出了基于方向的拓扑控制算法CBTC。该 面考虑,恻络拓扑应侏持全局连通,使任意两个传感器节点间算法的思想是节点首先发送Ilo消息,并收集其他节点的回 存在可通信链路。为∫实现数据转发过程中节点或区域的能复信息;然后节点独立调节发射功率,以保证在每a角度内至 量平衝,网络中能量相对充足的节点间的链路在路由时被优先少有一个邻居节点;最后删除冗余链路以维持拓扑的对称性。 选择。从MAC协议效率角度来看,网络拓扑的连通冗余度过该算法能达到全局连通、对称性、节点度受限等特点的拓扑,但 高,节点的信号覆盖范围可能过大,会造成隐藏或暴露终端问(BTC未能对低能耗节点采取保护措施,忽略了节点在路由中 题,从而引发数据通信碰撞,继而导致数据重传或串扰及其带的能耗不平衡冋题。 来的不必要的能耗。具体来说,拓扑控制机制可以从平面网 5)STFM算法 络、支配集和分簇的网络结构三方面分别讨论,如图4所示。 STFM算法是一种典型的启发式拓扑控制方法,采用低占 无线传感器网络 空比的节点唤醒机制,并使用监听和数据通信双信道。算法思 想是节点周期性地进入监听阶段探测是否有邻居节点要发送 平面网络)(分簇网络 支配集网络 数据,当其想与其他节点通信时,就作为主动节点先向目标节 邻居节点控制)(通信范围控制 点发送唤包,然后再进行通信。STEM算法节点的唤醒速度 K连通)〔统一功率控制不同发射功率簇的形成)(节点选择) 能满足应用的需要,可以适用于类似环境监测等应用,但该算 法在实际应用中需在节点的睡眠周期、部署密度以及通信延迟 图4无线传感器网络拓扑控制机的分类 3.1平面网络的拓扑控制 等之间进行权衡。 6)连通性覆盖问题 平面网络结构是WSNs中最简单的一类拓扑结构,其所有 网络连通性覆盖问题常常是与网络拓扑相互联系的,其所 节点的地位相同、功能对等,每个节点均包含相同的MAC、路解决的是如何保证监测区域内所有节点形成的监测范围可以 由、管理等协议。平面网络拓扑结构较为简单、易维护,具有较满足应用要求,同时节点都可以向simk转发数据,而不会产生 好的健壮性。平面网络没有中心管理节点,所以节点都能够与网络分割。WSN许多的重要的技术如拓扑控制、目标定位目 sik通信,数据包通过一跳或多跳转发至si,通常其拓扑是标跟踪等都是依赖于网络有效的连通性覆盖范围。网络连通 通过功率控制或网内节点协同启发机制来产生。功率控制机性覆盖控制的主要思想是利用节点的冗余性,通过节点状态转 制的思想是调整网络中传感器节点的发射功率,在保证网络连换、密度控制等机制,在不影响网络连通和覆盖的条件下让 通和均衡节点的单跳可达邻居数目的同时,降低节点间的无线部分节点处于活动状态承担数据采集转发等任务,使另一部 通信干扰。网内节点协同启发机制的思想是节点根据自身周分节点处于睡眠状态,以减少网络能量开销。 Zhang hong-hai 边环境的变化进行自主控制以及与邻居节点进行交互的机制,等人提出当节点密度有限时,节点通信半径r需不小于节 当有通信要求时能够及时自动醒来并唤醒邻居节点,形成数据点感应距离d的两倍,即r≥2d是连通性覆盖的充分必要条 转发的拓扑结构。下面介绍平面网络拓扑控制的典型算法。 件。 Xue fen等人4证明了在k覆盖和k连通情况下,且r≥ 1) COMPOW算法 2d时,一个凸区域的k阶覆盖必然包含k迕通。 Gao yong等 COMPOW算法是一种典型功率控制算法。该算法中节人证明了如果要覆盖某个节点的整个监测区域,该节点需 点采用同构方式,所有节点具有统一的传输功率,并且该功率要3-5个一跳的邻居节点。 是能确保整体网络连通的最小功率。虽然最小传输功率在降3.2分簇网络的拓扑控制 低能耗的同时提升了网络谷量、减少了通信干扰,但也约束了 在WSNs中,为了节约无线通信模块的能耗,可以将网络 COMPOW的适用范围,尤其当网内节点分布不均匀时节点被拓扑划分为相连的簇区域,并依据一定的机制选择部分节点作 迫使用较大功率,这电是该算法的致命弱点。 为骨干节点。骨干节点的通信模块处于工作状态,并由其构建 2)K- Neil算法 连通网络来处理和传输数据,让非骨十节点处于睡眠状态并属 K-Negih算法是一种典型的基丁邻居集合和距离估测丁骨下节点管理,从而大幅度降低空闲状态时侦听对节点能量 技术的分布式算法。K-Negh算法思想是节点首先以最大功率的消耗,进而延长网络寿命。分簇算法融合了聚类管理的理 播D,并根据接收到的广播报文运用距离估测技术进行由念,弥补了空闲状态节点无谓能耗过高的缺陷。分簇的网络拓 近至远的排序,因而确定K个最近节点置入邻居集,最后交互扑有利丁分布式算法的应用,适合大规模部署的网络。 邻居集合,对单向链接实施删除或增加以满足链接的双向对称 LEACH、HED等都是很具代表性的分簇拓扑算法 性。 K-Negih算法具有迕通性、节点度受限、算法执行简单等良 1) LEACH算法 好特性。 LEACH是一种很重要的分簇算法,许多拓扑控制的分簇 3)R&M算法 算法都是在 LEACH的基础上改进的。算法先选簇头后划 Rodoplu等人提出了一种基于闭包图的功率分配算法分区域,节点周期性地轮换充当簇头来实现网络的负载均衡 R&M,它是一种基于节点地理位置信息的拓扑算法。算法思 LEACH算法中,节点产生[0,1]的随机数,若随机数小于阈值 想是在每个节点周围确定一个称做 enclosure的区域,在 enc:- T,则宣布自己成为簇头,普通节点选择离其最近的簇头并加 sure区域中的节点称为该节点的真正邻居。通过计算转发区人该簇头管辖的区域。未被选为簇头的节点随着时间的推移 域和衠量转发代价,以低能耗实现网络连通。R&M算法是一能量比簇头愈显充足,成为簇头的可能性就越大。 种强连通、稀疏性、低能耗的高效拓扑算法,但是算法本身的计 LEACH轮换选举簇头,易保证网络获取统一的能量分布, 算复杂度较高,给网络带来较大的开销。 且集中、周期地采集数据,因此其非常适合要求连续监控的应 第9期 甘从辉,等:无线传感器网终的拓扑控制研究 3217 用系统。但簇头的选择没有考虑节点的地理位詈信息,且需要法应考志到干扰对拓扑造成的影响,并将干扰降低到最小程 较为严格的时间同步,更致命的是LACI不能保让簇头均匀度。Jain等人分析了干扰对无线多跳网络性能的影响,将网络 分布,这可能直接会影响骨十网的形成。 中的十梡进行建模,得出「计算络最优春吐量的上下限方 2)IED算法 法。HeYn-xing等人提出了减少干扰的次优最小连通 基于 LEACIL的缺陷,LACI的改过算法IED"应运而支配集的骨干网络拓扑算法(CD),算法构建了一个连通支 生。IEED算法思想是综合考虑剩余能量和簇内通信代价两配集,而且该连通支配集有效地减少了网络干扰,并讨论了干 级因素周期性地通过迭代的方法实现分簇。HFD用最小平扰对网络拓扑造成的影响。若区域内有n个节点m条链路 均叫达功率(AMP作为某个节点被选为簇头时的簇内通信则LCDs算法具有O(n)的消息复杂度和O(m+n)的时间复 代价的度量。 杂度。 HFFD不依赖丁网络的规模,有效地改善了 LEACH簇头3.4拓扑控制算法的比较 可能分布不均的缺陷。HFFD通过O(1)次迭代实现分簇,迭 代每一步的时间要足够长,使得节点能够收到来自邻居节点的 由于WSN网络依赖于应用,节点的硬件结构呈现多样性 消息。每个节点要确定在一簇范围内的邻居节点的集合,计算特征,许多的协议和标准也不统一,不同的应用对底层网络的 并广播AMRP,训算自己成为临时簇头的初始概率。虽然, 拓扑控制的要求也不尽相同,很难直接评判拓扑算法的优劣 HEED考虑了负载均衡和扩展性,但其执行不依赖时间同步可只能根据实际应用的需要权衡选择。基于以上对各种拓扑算 能会严重影响分簇的质量。 法的讨论和分析,从节点密度、复杂度等指标上进行比较,结果 3)GAF算法 如表1所示。 GAF是一种基于地理位置的分簇算法,该算法思想是 表1各种拓扑控制算法比较 首先将事件区域划分为若干虚拟网格,节点依据自身所处的位 算法 理论依据基于位置复杂度节点密度刚络规模同步 COMPOW统一功率分配 中等稀疏 置加人相应的格内,然后定期在格内选取簇头。簇头节点始终 K-NEIGH K邻居 低 稀疏 中等 保持清醒状态,非簇头节点进入睡眠状态。节点在休眠状态过 闭包图 稀疏 后会再次与本格内其他芍点交换信息来重选簇头,簇头通常由 邻近图 是低稀疏 节点产生的定时随机值决定。出于簇头的选取具有一定的随 STEM节点唤醒机制 密集 LEACH随机数确定簇头 中等 密集 机性,方格边长的选取必须能使相邻两格内任意节点可直接通 HEED AMRP 高密集 信。GAF显著降低了节点侦听能耗,但仅适用于网络数据流 量较小的场景。另外,GAF对GⅨ的依赖也会使节点部署受 DRNG RNO 到限制。 DLMST MST 否是是是否 GAF虚拟地理网格是 中等密集 中等稀 小大大小大大大大 中等稀疏 Wu ie连通支配集 密集 中等 是是否否否否否 3.3支配集网络的拓扑控制 连通支配集否 密集 节点的无线通信模块的能耗占节点总能耗的绝大部分,基 于此,尽可能地减少冗余广播是降低节点能耗的重要方汰。如4拓扑控制与调度、连诵之间的关系 何在广播信息能够覆盖网内所有节点的前提下使参与广播的 节点的数目最少,于是就引出了WSNs中另外一类拓扑间 在WSNs中,拓扑控制与调度、连通三者是相互紧密联系 题——构造最小连通支配集(MCDS)。 的,并通过不同的方式共同完成WSNs的既定功能。如何利用 3.3.1MCDS的构造 有限的能量最大化网络寿命是WSNs的核心问题。为达到这 构造MCS一般有两种方法:)基于删除冗余节点法个目标,就需要综合考虑能量有效和负载均衡合理化网络能 DRN)。首先生成最大连通的子集,然后逐一地删除节点,直量分配,而拓扑控制、词度和连通三者共同作用足能够实现这 到再删除节点就不能满足网络连通性为止。b)基干最大独立一日标的重要途径。 集法。先产生规模为mis(G)的最大独立集(M),然后添加 节点调度是WsNs拓扑控制重要的研究方向,是在一定的 节点,直到实现连通,从而形成规模为cv(G)的连通支配集时间阶段和空间范围内只使一部分节点保持工作状态,而使另 CS)。基丁DRN的算法复杂度相对较低,但构造的Cs没一部分节点进入睡眠状态,其根本目的是节省空闲侦听时的能 有明确上界;基丁Ms的算法复杂度较高,但能获得明确上界耗。非层次调度中每个节点均不属于某个簇,节点根据自己所 的CDS 能获得的信息,独立地控制自己在工作状态与睡眠状态之间的 3.3.2代表性算法 转换;层次型网络节点调度是由簇头节点组成骨干网络,让其 WuJe算法的基本思想是首先生成一个较大的CDs,然后他节点进入睡眠状态。通常情况下,节点在没有获悉兴趣数据 采用修剪去除冗余节点。节点发送信令学习网络中的两跳拓和承担数据转发任务时并不关闭通信模块,而节点的通信模块 扑结构信息,生成存在冗余的CD,然后根据一定的规则去除在空闲状仍然会侦听无线信道的占用情况和探测兴趣数据 CDS的冗余节点。该算法只利用了局部信息,具有较好的扩展的传递需求,空內状态的能耗与节点在收发状态时相当,覆盖 性。KY算法也是一种典型的CDs的构造算法。算法思想是冗余也造成∫很大的能量浪费,所以,只有使节点进入睡眠状 采用节点编号的组合作为节点的权值,其口的是减小CDs的态才能大幅度地降低网络的能量消耗。相对整体网络而言,节 规模,删除具有较小度的节点而保留较大度的节点。 点调度只能从微观层面上进行控制,哪些区域需要较多的工作 考虑到无线网络的特点,每个节点侦听到的通信信道状态节点采集、处理信息,哪些区域保持较少的工作节点就能完成 是不同的。距离上邻近的链路如果同时传输数据,可能会造成任务,只使用节点调度显然是不能够很好地解决问题。如此势 干扰导致信号碰撞。在wSNs中,设计一个高效的拓扑控制算必会造成资源不足或资源严重浪费的不平衡现象,这时就需要 3218 计算机应用研究 采用拓扑控制策略从全局方面控制某些Ⅸ域链路的使用状态, challenges: scalable coordinate in sensor network[C//Proc of the 从而形成一个良好的网络拓扑结构 5th ACM/IEEE International Conference on Mobile Computing Networking. Washington: ACM Press. 1999: 263-270 为∫有效地实现节点间的相互通信,要求网络生成的拓扑 [2 AKYILDIZ I F SU Wei-liall, SANKARASU BRAMA NIAM Y, et a 本身必须保证连通性。非层次型网络节点需要获知邻居节点 A survey on sensor netwarks[J]. IEEE Communication Maga 是否处于活动状态或当节点发生丢包现象时需要向邻居节点 zine,2002,40(8):102-114 发送求救信息,所以要求拓扑具有连通性;层次型网络节点需 [3]路纲,周明天,牛新征,等.无线网络邻近图综述[J].软件学报, 2008,19(4):888-991 要节点轮流工作,必然存在转发节点睡眠,继而要重新建立路4」 LI Xiang-yan, SONG Wen-zhan, WANG Yu. Loc alized toplogy con 由,所以拓扑的连通性也是实现这一过程的必要条件。传感器 trol for heterogeneous wireless sensor netw orks J. ACM Trans on 节点的邻居节点太少,会造成消息可达率过低,出现较多没有 Sensor Networks, 2006. 2(1):129-153 邻居节点的伪孤立点,降低了网络的连通性和容错能力,增加5]贺路,李建东,装于 Delaunay角剖分的Adh网络路由法[ 软件学报,2006,17(5):1149-1156 了网络分割的可能;若邻居节点过多,则会造成信息的大量冗[61郭庆胜,郑本燕,胡华科基于邻近图的点群层次聚类方法的研 余,增曾加网络的干扰,带来通信负担和计算资源的浪费,从而违 究[J],测绘学报,2008,37(2):256-261 背节约能量的初衷。因此,通常要根据实际需要选取合适的节 [7] LI Ning, HOU J G. Topology control in heterogeneous wireless net works: problems and solutions C//Proc of the 23 rd IEEE Confe 点连通度。另外,高冗余性也是wSNs的主要特点之一,节点 rence un CoImlpuler CollIn unications. New York: IEEE Press, 2004 部署密度大,节点连通度高,数据冗余度大,部分节点采集的数 232-243 据与仝局节点采集的数据效果相差不大。同时,激活所有节点 [8]郑囯强,李建东无线传感器网络MAC协议研究进展[J].自动 容易造成大量的网络拥塞,一方面造成数据丢失,另一方面使9)化学报,08,34(3):306-313 N ARAYANSWAMY S, KAWADIA V, SREENIVAS R S. et a Power control in Ad hoc networks: theory, architecture, algorithm and 效的拓扑控制技术来消除不必要的冗余数据,保证满足应用需 implementation of the COMPOW protocol C 1//Proc of European 求的数据被传送到基站,减少网络拥塞的出现,并尽可能地将 Wireless Conference. 2002: 156-162 [10 BLOUGH D, LEONCINI M, RESTA G, et al. The K-Neigh protocol ⊥作平均分配给各个节点,以平衡网络的能量分布,从而达到 for symmetric topology control in Ad hoc networks[ C//Proc of the 提高能效、延长网络寿命的目的。 4th ACM International Symposium on Mobile Ad hoc Networking WsNs是资源受限网络,为了提高有限资源的有效性和可 Com puting. New York: ACM Press, 2003: 141-152 11 RODOPLL V, MENG T H. Minimum energy mobile wireless netwoks 靠性,网内链路上的通信业务要分布均匀,避免在薄弱链路上 LJ. Sclected Areas in Communications, 1999, 17(8): 1333- 有太大的业务密度。恻络需要通过有效的睡眠调度来搾制节 1344 点的状态转换缓解网络干扰,使中间节点能够高效地传送上121L., HALPERN J Y, BAHL H,ea, Analysis of a cone-hased o 行链路和下行链路上的数据。同时,还需婁利用拓扑控制算法 ributed topology control algorithm for wireless multi-hop networks [C]//Proc of the 20 th ACM Symposium an Principles of Distributed 控制网络宏观状态,并实现节点间的可靠连接和负载均衡,以 Com puting. New Y ork: ACM Press, 2001: 264-273 降低网络不必要的能量消耗。设计者要根据实际应用场景在131 ZHANG Hong-hai, HOU C. Maintaining sensing coverage und con 调度、连接与拓扑控制间平衡地作出选择,将点、线、面有机结 nativity in sensor netwarks J. Ad hoc Sensor Wireless Networks 1(3):89-124 合,共同作用形成节能高效的拓扑结构,如图5所示 [14 XUE Feng, KUMAR P R. The number of neighbors needed for con 提供 nectivity of wireless net works[ J]. Wireless Networks, 2004,10 连通 调度 拓扌控制 [15 GAO Yong. WU Kui, LI Fu-lu. Analysis on the redundancy of wire 负载均衡 less sensor networks[C]//Proc of the 2 nd ACM International Confe 保持 rence on Wireless Sensor Networks and Applications. New York 图5拓扑控制和连通、调度之问的关系 ACM Press,2003:108-114 [16 HEINZELMAN W R. CHANDRAKASAN A, BALAKRISHNAN H 5结束语 An application specific protocol architecture for wire less microsensor networks[J- IEEE Trans on Wireless Communications, 2002 拓扑搾制是实现WSNs有限资源高效利用的关键技术,其 1(4):660-670 算汏的评价标准圾决于算汰的效率。高效的算法应同时表现17] YOUNIS O, FAHMY S. Distrihuted clustering in Ad hoc sensor net 在降低单位节点传输数据的能耗和降低算法本身的实现成本 works: a hybrid energy-efficient approach[ C//Proc of the 23rd An nual Joint Conference on Computer and Communications Societie 两个方面。虽然WsNs的拓扑掉制技术已经取得了一定的进 2004:46-63. 展,出现了一些代表性的算法,并且研究领域和覆盖而也在逐18]XUYa, HEIDEMANN J, ESTRIN D. Geography-Informed energy 步扩大,但拓扑控制算法目前还处于理论研究或实验模拟阶 conservation for Ad hoc routing[C]//Proc of the 7 th Annual Interna 段,离应用丁实际尚有一定的距离。目前对拓扑控制的研究大 tional Conference on Mobile Computing and Networking. New York ACM Press. 2001:70-84 多过丁理想化,没有充分考虑实际的网络环境,对算法的收敛19JANK, PADHYE J, PADMANABHAN V,cta. Impact of interfe 速度、节点移动的影响、迫加节点数目的预测、节点精确位置信 rence on multihop wireless network performance C//Proc of the 息的确定、三维空问区域部署等方面均有待深入考虑,特别是 9 th Annual International Conference on Mobile Computing and Net working. New York. ACM Press. 2003. 66-80 需要多种机制相结合,探索更接近现实环境的拓扑控制技(201 HE Yan-xian, ENG Yuan-yuan. Interference-aware topology cor 术,增强建立在模型基础上的理论分析的说服力,这些也是 trol problem in wireless sensor networks[C//Proc of the 6th Interna- WSNs拓扑控制进一步的研究方向。 tional Conference an ITS Telecommunications Proceedings. 2006 969972 参考文献: 「21]郑囯强,李建东.用于多跳无线传感器网络的能量有效数据转发 [1 ESTRIN D, GOVINDAN R, HEIDEMANN J, et al. Next century 协议[J].计算机科学,2007,34(8):24-29

...展开详情
试读 5P 论文研究-无线传感器网络的拓扑控制研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-无线传感器网络的拓扑控制研究.pdf 15积分/C币 立即下载
1/5
论文研究-无线传感器网络的拓扑控制研究.pdf第1页

试读结束, 可继续读1页

15积分/C币 立即下载