（计算机应用技术专业论文）无线传感器网络覆盖与节点部署问题研究.pdf

摘要 摘要 近年来，集成了传感器技术、微电子技术和无线通信技术的无线传感器网络已 引起各国政府、研究机构和企业的高度关注，在军事、环境科学、医疗健康和其 他商业领域都有着广阔的应用前景。本文主要研究了w s n 的覆盖和节点部署问 题。 覆盖是无线传感器网络研究的基本问题之一。无线传感器网络一般由大量自供 电的传感器节点组成，传感器节点一般依靠电池供电。电池电源是有限的，并且 传感器节点一旦配置后，由于其工作环境等因素的限制就很难对电池进行充电或 更换电池，这就使得无线传感器网络的寿命受到影响，从而不能长时间的使用。 覆盖问题不仅能够保证无线传感器网络正常工作，而且还在很大程度上影响着整 个网络的能耗、生存时间和服务质量等重要参数。因此，对w s n 覆盖问题的研究 是十分有意义的。 节点部署是传感器网络设计考虑的第一步，是传感器网络正常工作的基础，只 有将传感器节点在目标区域部署好，才能进一步进行其它的工作和优化。传感器 节点的部署分为随机部署和人工部署，在一些特殊的应用环境中，必须人工部署。 本文简要介绍了无线传感器网络的起源和研究背景，对目前国内外无线传感器 网络的研究现状进行了分析，阐述了无线传感器网络的相关技术，总结了无线传 感器网络的特点。 论文介绍了无线传感器网络的几种覆盖模型，总结了无线传感器网络覆盖问题 的分类，分析了几个典型算法的基本理论、实现方法和优缺点。然后利用所建立 的数学模型，结合图论、概率论和统计学等方面的知识，提出了基于k 覆盖度的 覆盖控制算法，给出了节点覆盖度的计算公式。 在现有算法的基础上，论文提出了一种基于蜂窝网格的传感器节点部署算法， 并通过仿真实验证明了蜂窝网格在节点部署上能够最大化监测面积。对传感器网 络内外层节点寿命进行了研究，从理论上提出了一种理想分布模型。 关键字：无线传感器网络，覆盖度，节点部署，网格 a b s t r a c t a b s t r a c t w i r e l e s ss 饥s o r n e t 、7 l r o r k s ( w s n ) 、) l 加c hi n t e g r a t e s 血et e c l l l l o l o g y o fs e l l s o r t e c i l l l o l o g y ，m j c r 0 一e l e c 缸d - m e c h a n i c a ls y s t e i i l st e c t m o l o g y w i r e l e s sc o m m 疵c a t i o n s ， a n dd i 西t a le l e c 仃o i l i c s ，h a sb e 饥h i g i l l yn o t i c e db y9 0 v 踟m e n t s ，r e s e a r c hi n s t i 嘶o n s 锄dc o m p a i l i e s i th a sb e 饥p r c d i c t e dt oh a v eaw i d e 础1 9 eo fa p p l i c a t i o l l sr e l a t e dt 0 n a t i o n a ls e c u 矗t y ，m i l i t a r y ，a i r 0 啪e n t ，h e a l t l lc a r e ，t l o m e 甜l do t l l e rc o m m e r c i a la r e 弱 1 1 l i sm e s i sf o c u s e so nt h ep r o b l e m so fc o v e 强萨a 1 1 ds e i l s o rd 印l o y m e i l ti n l ew s n c o v e r a g ci so n eo f 廿l eb a l s i cp r o b l e m so fw s n w s na r ec o m p o s e do fal a r g e m m l b e ro fs e l f p o w e r e ds e n s o rn o d 懿w h i c ha r er e l i o do nb a 仕e 巧p o w 筑t h en e t w o r k s l i f ei si n f l u e n c e db y l eb a t t e r yc a p a d 够a 1 1 di t sd i 伍c u l tt oc h a f g eo rr 印1 a c em eb a t t e 阱 c o v e r a g ec a n1 1 0 to i l l ye n s u r e l en o m a lw o r k ，b u ta l s 0a f 诧c t st h ee n t i r ee 1 1 e 喀y c 0 n s 切m p t i o 玛s u l 啊v a lt i i i l ea n d 删i t yo fs e r v i c e s o ，r e s e a r d ho nm ei s s l l eo fc 0 v e r a g e i sv e r ym e a n i n g 缸1 n o d ed 印1 0 y m e n ti st l l e 丘r s ts t 印i nd e s i 嘶n gs e n s o rn e t w o d 【sa n dm ef o u n d a t i o n o fn o m a lw o r k o m yt l l es e n s o rn o d e sa r ea 彻n g e di nm et 鹕e ta r e 毛o t l l e rj o b s 甜1 dt h e o p t i l l l i z a t i o nc a i lb ec 枷e do n t h es e n s o rn o d e sd 印l o m e n td i v i d e si n t o 廿l er a n d o m d 印l o y m e l l ta i l dm 觚u a ld 印l o y m e i l t i ti sn e c e s s a r ) ，t 0u s em 锄u a ld 印1 0 y m e n ti i ls o m e s p e c i a la p p l i c a t i o na i r o l l i i l e i 崎 t m st 1 1 e s i sf i r s tn r o d u c e s 舭耐g m 柚dr e s e a r c hb a c k g r o u l l do fw s n ，a i l a l y z e s l ep r e s e n ts i t u a t i o no fd o m e s t i ca i l df o r e i 弘r e s e 铷池o nw s n ，i 1 1 l 船a t e st 1 1 er e l a t i v e t e d m 0 1 0 舀e sa 芏1 ds l 肋m 撕z e st h ec h a r a c t 耐s t i c so f w s n n e x t ，i ti n 乜0 d u c e ss 删k i n d so fc 0 v e r a g em o d e l sa n da l l a l y z e st h e i rb a s i c m e o r i e s ，m e m o d so fi m p l e m 咖a t i o n ，a d v a n t a g e sa i l dd i s a d v a i l t a g e s b y 廿1 e s ea i l a l y s e s ， ac o v e r a g ec o 劬r o la l g o r i b a s e do nk - c o v e r a g ed e 冒c ei sp r o p o s e d t 嫩r d l y ，i tp r o p o s e sas e n s o rn o d ed e p l o ) i n l e n ta l g o r i m mb a u s e do nh o n e y c o m b 鲥d a n d p r o v e si t se 虢c t i v e n e s sm r o u 曲s i m u l a t i o ne x p 酬血e i l t f i n a l l y ，i tr e s e a r c h e sm el i f eo fi i m e rl a y e rn o d e sa n do u t e fl a y e rn o d e s 觚d p f o p o s e sa ni d e a ld 印1 0 y n l e n tm o d e l k e y w o r d s ：w i r e l e s ss e l l s o rn e 咐o r k s ，c o v e r a g ed e 黟e e ，n o d ed e p l o y m e n t ，矾d 缩略语目录 缩略语目录 英文缩写英文全称中文释义 w s nw i r e l e s ss c i l s o rn 酣帕r k 无线传感器网络 a n sw _ i r e l e s sl o c a la r e an e t w o 血s 无线局域网 g p sg 1 0 b a lp o s i t i o n i n gs y s t 锄 全球定位系统 q o sq 咀a l i t yo fs e i c e服务质量 f s mf i n i s h s t a t e m a 蛳n e 有限状态自动机 i 】l w bu l n 磕w i d eb a i l d 超宽带技术 n s sn o d es e l f - s c h e d u l i n g 节点自组织算法 m b pm a x i m a lb r e a c hp a 吐l最大突破路径 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：鳖堕i日期：2 帕年牵月，笋日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盘幽导师签名：望盘 日期：2 i ) 胡年4 月j l ；日 第一章引言 第一章引言 1 1 无线传感器网络概念及其研究意义 1 1 1 无线传感器网络 随着“后p c 时代丹的到来，计算机的设计冲破了传统高性能计算机和服务器 的设计模式，开始向小型化、低功耗、分布式方向发展，v l s i 设计的普及化和半 导体芯片制造工艺的迅速发展使得在一块芯片上集成一个完整的计算机系统已经 成为可能；微机电技术和传感技术的进步导致了传感器的微型化；无线通信技术 和分布式计算技术的成熟带来了难以估量的计算处理能力。这些方面的高度集成 又孕育出了无线传感器网络这一全新的信息获取和处理模式。 根据不同的任务需求，低成本、微型化的传感器节点集成了不同类型的传感器， 以感知和测量所在周边环境的温度、湿度、噪声、光强度、压力、速度、加速度 等。数量巨大的传感器节点通过飞机抛撒或其他特定的方式分散在监控区域内， 通过无线通信自主地构成a d h o c 网络，并通过铷作式的感知、数据采集和分布式 的计算，实现对监控区域内用户所感兴趣的物理量的监测，并将监测结果通过网 络传送给用户。 无线传感器网络是由大量传感器节点通过无线通信技术自组织构成的网络。无 线传感器网络可实现数据的采集量化、处理融合和传输应用，它是信息技术中的 一个新领域，在军事和民用领域均有着非常广阔的应用前景，如军事侦察、环境 监测、医疗监护、空间探索、城市交通管理、仓储管理等。 无线传感器网络与传统的无线网络有着不同的设计目标。后者在高度移动的环 境中通过路由和资源管理策略最大化带宽的利用率，同时为用户提供一定的服务 质量保证。在无线传感器网络中，除了少数节点需要移动以外，大部分节点都是 静止的。因为无线传感器网络中的节点一般采用电池供电，可以使用的电量非常 有限，而且对于成千上万节点的传感器节点来说，对电池的更换是非常困难甚至 是不可能的。但是无线传感器网络的生存时间却要求长达数月甚至数年，因此， 如何在不影响功能的前提下，尽可能节约无线传感器网络的电池能量成为无线传 感器网络软硬件设计中的核心问题，也是当前国内外研究机构关注的焦点。 电子科技大学硕士学位论文 为了解决传感器网络的能量有限问题，研究者提出了新的算法，他们大体上可 以分为两类：第一类是拓扑控制，拓扑控制依靠控制每个节点的传输能量并且因 此建立从传感器节点( s e n s o r s ) 到汇节点( s i n k s ) 的多跳路径来最小化传感器的 能量消耗。第二类是数据传输控制，即在数据链路层、网络层、传输层降低能量 消耗。拓扑控制与数据传输控制在降低传感器网络能量消耗方面有着同样重要的 作用【。 由于传感器网络中传感器节点的密度较大，引起了下述问题：感知区域的交叉、 数据冗余、通信冲突和能量消耗。降低能量消耗广泛使用的策略是关掉一些冗余 的传感器节点。为了更加有效的使用有限的能源，就需要研究传感器网络的覆盖 问题。 1 1 2 无线传感器网络的研究意义 无线传感器网络的应用前景非常广阔，能够广泛应用于军事、环境监测和预报、 健康护理、智能家电、建筑物状态监控、城市交通、空间探索、大型车间和仓库 管理，以及机场、大型工业园区的安全监测等领域。随着传感器网络的深入研究 和广泛应用，传感器网络将逐渐深入到人类生活的各个领域。 ( 1 ) 军事应用 传感器网络具有可快速部署、可自组织、隐蔽性强和高容错性的特点，因此非 常适合在军事上应用。利用传感器网络能够实现对敌军兵力和装备的监控、战场 的实时监视、目标的定位、战场评估、核攻击和生物化学攻击的监测和搜索等功 能。通过飞机或者炮弹直接将传感器节点播撒到敌方阵地内部，或者在公共隔离 带部署传感器网络，就能够非常隐蔽而且近距离准确地收集战场信息，迅速获取 有利于作战的信息。传感器网络可以通过分析采集到的数据，得到十分准确的目 标定位，从而为火控和制导系统提供精确的制导。传感器网络已经成为军事c 4 i s i h ( c o i i l 】 n a i l d ，c o n 缸d 1 ，c o 舢叭l l l i c a t i o n ，c 0 m p u t i n g ，i n t e l l i g e n c e ，s u e i l l a n c e r e c o 皿a i s s a n c ea n dt a r g e t i n g ) 系统必不可少的一部分，受到军事发达国家的普遍重 视，各国均投入了大量的人力和财力进行研究。美国d a r p a ( d e f ；。i l s ea d v a i l c e d r e s e a r c hp r o j e c t sa g e n c y ) 很早就启动了s e n s i t ( s e n s o rh l f o 衄a t i o nt e c h n 0 1 0 9 y ) 计划。该计划的目的就是将多种类型的传感器、可重编程的通用处理器和无线通 信技术组合起来，建立一个廉价的无处不在的网络系统，用以监测化学、声学、 震动、磁场、湿度、污染、毒物等信息。 2 第一章引言 ( 2 ) 环境监测和预报系统 传感器网络在环境研究方面可以用于监视农作物灌溉情况、土壤空气情况，也 可以用于行星探测、气象和地理研究、洪水监测等，还可以通过跟踪鸟类、小型 动物和昆虫进行种群复杂度的研究等。基于传感器网络的a l e r _ t 系统中就有数种 传感器用来监测降雨量、河水水位和土壤水分，并依此监测爆发山洪的可能性。 类似地，传感器网络可实现对森林环境监测和火灾报告，传感器节点被随机密布 在森林之中，平常状态下定期报告森林环境数据，当发生火灾时，这些传感器节 点通过协同合作会在很短的时间内将火源的具体地点、火势的大小等信息传递给 相关部门。 ( 3 ) 医疗护理 传感器网络在医疗系统和健康护理方面的应用包括监测人体的各种生理数据， 跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病人身上 安装特殊用途的传感器节点，如心率和血压监测设备，医生利用传感器网络就可 以随时了解被监护病人的病情，发现异常能够迅速抢救。还可以利用传感器网络 长时间地收集人体的生理数据，这些数据对了解人体活动机理和研制新药品都是 爿# 常有用的。人工视网膜就是一项生物医学的应用项目。在s s 蹦( s m 积s s o r sa n d i n t e 掣a t e dm i c r o s y s t 锄s ) 计划中，替代视网膜的芯片由1 0 0 个微型的传感器组成， 并置入人眼，目的是使得失明者或者视力极差者能够恢复到一个可以接受的视力 水平。传感器的无线通信满足反馈控制的需要，有利于图像的识别和确认。 ( 4 ) 智能家电 传感器网络能够应用在家电中，在家电和家具中嵌入传感器节点，通过无线网 络与h l t e m e t 连接在一起，将会为人们提供更加舒适、方便和更具人性化的智能家 居环境。利用远程监控系统，可完成对家电的远程遥控，例如可以在回家之前半 小时打开空调，这样回家的时候就可以直接享受舒适的室温，也可以遥控电饭煲、 微波炉、电冰箱等家电。利用传感器网络可以建立智能幼儿园，监测孩童的早期 教育环境，跟踪孩童的活动轨迹，可以让父母和老师全面地研究学生的学习过程。 ( 5 ) 空间探索 探索外部星球一直是人类梦寐以求的理想，借助于航天器布撒的传感器网络节 点实现对星球表面长时间的监测，应该是一种经济可行的方案。美国国家航空和 宇宙航行局( n a s a ) 的j p l ( j e tp r o p u l s i o nl 曲o r a t o f y ) 实验室研制的s e n s o rw 曲s 就是为将来的火星探测进行技术准各的，已在佛罗里达宇航中心周围的环境监测 项目中进行测试和完善。 电子科技大学硕士学位论文 普遍网络化孕育的无线传感器网络是一种新的信息获取和处理技术，在各种领 域，它有着传统技术不可比拟的优势，同时也必将开辟出不少新颖而有价值的商 业应用。现今的信息系统是基于人类的输入或计算机产生的数据的，而未来的信 息系统将建立在现实世界的物理数据。在未来，无线传感器网络会成为人们生活 中不可或缺的一部分，这引起了科技界和商业界的广泛关注。著名的美国商业 周刊早在1 9 9 9 年就在预测未来技术发展中将无线传感器网络列为2 1 世纪最具 影响的2 l 项技术之一。m i t 技术评论在2 0 0 3 年2 月版中认为，有1 0 种新兴 技术在不远的将来会对世界产生巨大影响。排在这十种技术首位的就是无线传感 器网络。 总之，无线传感器网络是继i n t e m d 之后的r r 热点技术，具有广阔的应用前景， 将对2 1 世纪人类的活动产生重大的影响，研究无线传感器网络的意义重大而深远。 1 2 无线传感器网络关键技术及其国内外研究现状 无线传感器网络作为当今信息领域新得研究热点，涉及多学科交叉的研究领 域，有非常多的关键技术有待发现和研究，下面仅列出部分关键技术。 ( 1 ) 网络拓扑控制 对于无线的自组织的传感器网络而言，网络拓扑控制具有特别重要的意义。通 过拓扑控制自动生成的良好的网络拓扑结构，能够提高路由协议和m a x 协议的效 率，可为数据融合、时间同步和目标定位等多方面奠定基础，有利于节省节点的 能量来延长网络的生存期。所以，拓扑控制是无线传感器网络研究的核心技术之 o 传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度前提 下，通过功率控制和骨干网节点选择，剔除节点之间不必要的无线通信链路，生 成一个高效的数据转发的网络拓扑结构。拓扑控制可以分为节点功率控制和层次 型拓扑结构形成两个方面。功率控制机制调节网络中每个节点的发射功率，在满 足网络连通度的前提下，减少节点的发送功率，均衡节点单跳可达的邻居数目： 已经提出了c o m p o w 等统一功率分配算法，l i n w l i l t 和l m n l m a 等基于节 点度数的算法，c b t c 、l m s t 、r n g 、d r n g 和d l s s 等基于邻近图的近似算法。 层次型的拓扑控制利用分簇机制，让一些节点作为簇头节点，由簇头节点形成一 个处理并转发数据的骨干网，其他非骨干网节点可以暂时关闭通信模块，进入休 眠状态以节省能量；目前提出了t o p d i s c 成簇算法，改进的g a f 虚拟地理网格分 4 第一章引言 簇算法，以及l e a c h 和h e e d 等自组织成簇算法【。 除了传统的功率控制和层次型拓扑控制，人们也提出了启发式的节点唤醒和休 眠机制。该机制能够使节点在没有事件发生时设置通信模块为睡眠状态，而在有 事件发生时及时自动醒来并唤醒邻居节点，形成数据转发的拓扑结构。这种机制 重点在于解决节点在睡眠状态和活动状态之间的转换问题，不能够独立作为一种 拓扑结构控制机制，因此需要与其他拓扑控制算法结合使用。 ( 2 ) 网络协议 由于传感器节点的计算能力、存储能力、通信能量以及携带的能量都十分有限， 每个节点只能获取局部网络的拓扑信息，其上运行的网络协议也不能太复杂。同 时，传感器拓扑结构动态变化，网络资源也在不断变化，这些都对网络协议提出 了更高的要求。传感器网络协议负责使各个独立的节点形成一个多跳的数据传输 网络，目前研究的重点是网络层协议和数据链路层协议。网络层的路由协议决定 监测信息的传输路径；数据链路层的介质访问控制用来构建底层的基础机构，控 制传感器节点的通信过程和工作模式。 在无线传感器网络中，路由协议不仅关心单个节点的能量消耗，更关心整个网 络能量的均衡消耗，这样才能有效延长整个网络的生存期。同时，无线传感器网 络是以数据为中心的，这在路由协议中表现得更为突出，每个节点没有必要采用 全网统一的编址，选择路径可以不用根据节点的编址，更多的是根据感兴趣的数 据建立数据源到汇聚节点之间的转发路径。目前提出了多种类型的传感器网络路 由协议，如多个能量感知的路由协议，定向扩散和谣传路由等基于查询的路由协 议，g e a r 和g e m 等基于地理位置的路由协议，s p e e d 和r e h 谭o r l 等支持q o s 的路由协议。 传感器网络的m a c 协议首先要考虑节省能源和可扩展性，其次才考虑公平性、 利用率和实时性等。在m a c 层的能量消费主要表现在空闲侦听、接收不必要数据 和碰撞重传等。为了减少能量的消耗，撇协议通常采用“侦听睡眠交替的无 线信道侦听机制，传感器节点在需要收发数据时才侦听无线信道，没有数据需要 收发时就尽量进入睡眠状态。由于传感器网络是应用相关的网络，应用需求不同 时，网络协议往往需要根据应用类型或应用目标环境特征定制，没有任何一个协 议能够高效适应所有不同的应用。 ( 3 ) 网络安全 无线传感器网络作为任务型的网络，不仅要进行数据的传输，而且要进行数据 采集和融合、任务的协同控制等。如何保证任务执行的机密性、数据产生的可靠 电子科技大学硕士学位论文 性、数据融合的高效性以及数据传输的安全性，就成为无线传感器网络安全问题 需要全面考虑的内容。 为了保证任务的机密布置和任务执行结果的安全传递和融合，无线传感器网络 需要实现一些最基本的安全控制：机密性、点到点的消息认证、完整性鉴别、新 鲜性、认证广播和安全管理。除此之外，为了确保数据融合后数据源信息的保留， 水印技术也成为无线传感器网络安全的研究内容。 虽然在安全研究方面，无线传感器网络没有引入太多的内容，但无线传感器网 络的特点决定了它的安全与传统网络安全在研究方法和计算手段上有很大的不 同。首先，无线传感器网络的单元节点的各方面能力都不能与目前h n 锄e t 的任何 一种网络终端相比，所以必然存在算法计算强度和安全强度之间的权衡问题，如 何通过更简单的算法实现尽量坚固的安全外壳是无线传感器网络安全的主要挑 战；其次，有限的计算资源和能量资源往往需要系统的各种技术综合考虑，以减 少系统代码的数量，如安全路由技术等；另外，无线传感器网络任务的协作特性 和路由的局部特性使节点之间存在安全耦合，单个节点的安全泄漏必然威胁整个 网络的安全，所以在考虑安全算法的时候要尽量减小这种耦合性。 无线传感器网络s p i n s 安全框架在机密性、点到点的消息认证、完整性鉴别、 新鲜性、认证广播方面定义了完整有效的机制和算法。安全管理方面目前以密钥 预分布模型作为安全初始化和维护的主要机制，其中随机密钥对模型、基于多项 式的密钥对模型等目前最有代表性的算法。 ( 4 ) 时间同步 时间同步是需要协同工作的传感器网络系统的一个关键机制。如测量移动车辆 速度需要计算不同传感器检测事件时间差，通过波束阵列确定声源位置节点间时 间同步。n r p 协议是i i l t 锄e t 上广泛使用的网络时间协议，但只适用于结构相对稳 定、链路很少失败的有线网络系统；g p s 系统能够以纳秒级精度与世界标准时间 u t c 保持同步，但需要配置固定的高成本接收机，同时在室内、森林或水下等有 掩体的环境中无法使用g p s 系统。因此，它们都不适合应用在传感器网络中。 ( 5 ) 定位技术 位置信息是传感器节点采集数据中不可缺少的部分，没有位置信息的监测消息 通常毫无意义。确定事件发生的位置或采集数据的节点位置是传感器网络最基本 的功能之一。为了提供有效的位置信息，随机部署的传感器节点必须能够在布置 后确定自身位置。由于传感器节点存在资源有限、随机部署、通信易受环境干扰 甚至节点失效等特点，定位机制必须满足自组织性、健壮性、能量高效、分布式 6 第一章引言 计算等要求。 根据节点位置是否确定，传感器节点分为信标节点和位置未知节点。信标节点 的位置是已知的，位置未知节点需要根据少数信标节点，按照某种定位机制确定 自身的位置。在传感器网络定位过程中，通常会使用三边测量法、三角测量法或 极大似然估计法确定节点位置。根据定位过程中是否实际测量节点的距离或角度， 把传感器网络中的定位分类为基于距离的定位和距离无关的定位。 基于距离的定位机制就是通过测量相邻节点问的实际距离或方位来确定未知 节点的位置，通过采用测距、定位和修正等步骤实现。根据测量节点间距离或方 位时所采用的方法，基于距离的定位分为基于删l 的定位、基于t d o a 的定位、 基于a o a 的定位、基于r s s i 的定位等。由于要实际测量节点间的距离或角度， 基于距离的定位机制通常定位精度相对较高，所以对节点的硬件也提出了很高的 要求。距离无关的定位机制无须实际测量节点间的绝对距离或方位就能够确定未 知节点的位置，目前提出的定位机制主要有质心算法、d v _ h 叩算法、a m o r p h o l l s 算法、仙i t 算法等。由于无须测量节点间的绝对距离或方位，因而降低了对节点 硬件的要求，使得节点成本更适合于大规模传感器网络。距离无关的定位机制的 定位性能受环境因素的影响小，虽然定位误差相应有所增加，但定位精度能够满 足多数传感器网络应用的要求，是目前大家重点关注的定位机制。 ( 6 ) 数据融合 传感器网络存在能力约束。减少传输的数据量能够有效地节省能量，因此在从 各个传感器节点收集数据的过程中，可利用节点的本地计算和存储能力处理数据 的融合，去除冗余信息，从而达到节省能量的目的。由于传感器节点的易失效性， 传感器网络也需要数据融合技术对多份数据进行综合，提高信息的准确度。 数据融合技术可以与传感器网络的多个协议层次进行结合。在应用层设计中， 可以利用分布式数据库技术，对采集到的数据进行逐步筛选，达到融合的效果； 在网络层中，很多路由协议均结合了数据融合机制，以期减少数据传输量；此外， 还有研究者提出了独立于其他协议层的数据融合协议层，通过减少m a c 层的发送 冲突和头部开销达到节省能量的目的，同时又不损失时间性能和信息的完整性。 数据融合技术已经在目标跟踪、目标自动识别等领域得到了广泛的应用。在传感 器网络的设计中，只有面向应用需求设计针对性强的数据融合方法，才能最大限 度地获益。 数据融合技术在节省能量、提高信息准确度的同时，要以牺牲其他方面的性能 为代价。首先是延迟的代价，在数据传送过程中寻找易于进行数据融合的路由、 电子科技大学硕士学位论文 进行数据融合、为融合而等待其他数据的到来，这三个方面都可能增加网络的平 均延迟。其次是鲁棒性的代价，传感器网络相对于传统网络有更高的节点失效率 以及数据丢失率，数据融合可以大幅度降低数据的冗余性，但丢失相同的数据量 可能丢失更多的信息，因此相对而言也降低了网络的鲁棒性。 ( 7 ) 数据管理 从数据存储的角度来看，传感器网络可被视为一种分布式数据库。以数据库的 方法在传感器网络中进行数据管理，可以将存储在网络中的数据的逻辑视图与网 络中的实现进行分离，使得传感器网络的用户只需要关心数据查询的逻辑结构， 无需关心实现细节。虽然对网络所存储的数据进行抽象会在一定程度上影响执行 效率，但可以显著增强传感器网络的易用性。美国加州大学伯克利分校的t i n v d b 系统和c o m e n 大学的c o u g a r 系统是目前具有代表性的传感器网络数据管理系统。 传感器网络的数据管理与传统的分布式数据库有很大的差别。由于传感器节点 能量受限，且容易失效，数据管理系统必须在尽量减少能量消耗的同时提供有效 的数据服务。同时，传感器网络中节点数量庞大，且传感器节点产生的是无限的 数据流，无法通过传统的分布式数据库的数据管理技术进行分析处理。此外，对 传感器网络数据的查询经常是连续的查询或随机抽样的查询，这也使得传统分布 式数据库的数据管理技术不适用于传感器网络。 传感器网络的数据管理系统的结构主要有集中式、半分布式、分布式以及层次 式结构，目前大多数研究工作均集中在半分布式结构方面。传感器网络中数据的 存储采用网络外部存储、本地存储和以数据为中心的存储三种方式。相对于其他 两种方式，以数据为中心的存储方式可以在通信效率和能量消耗两个方面获得很 好的折中。基于地理散列表的方法便是一种常用的以数据为中心的数据存储方式。 传感器网络中，可以为数据建立一维索引方法。传感器网络的数据查询语言目前 多采用类s q l 的语言。查询操作可以按照集中式、分布式或流水式查询进行设计。 集中式查询由于传送了冗余数据而消耗额外的能量；分布式查询利用聚集技术可 以显著降低通信开销；而流水线式聚集技术可以提高分布式查询的聚集正确性。 传感器网络中，对连续查询的处理也是需要考虑的方面，c a c q 技术可以处理传 感器网络节点上的单连续查询和多连续查询。 ( 8 ) 无线通信技术 传感器网络需要低功耗短距离的无线通信技术。正e e8 0 2 1 5 4 标准是针对低速 无线个人域网络的无线通信标准，把低功耗、低成本作为设计的主要目标，旨在 为个人或者家庭范围内不同设备之间低速联网提供统一标准。由于i e e e 8 0 2 1 5 4 第一章引言 标准的网络特征与无线传感器网络存在很多相似之处，故很多研究机构把它作为 无线传感器网络的无线通信平台。 超宽带技术( 【脚b ) 是一种极具潜力的无线通信技术。超宽带技术具有对信道 衰落不敏感、发射信号功率谱密度低、低截获能力、系统复杂度低、能提供数厘 米的定位精度等优点，非常适合应用在无线传感器网络中。迄今为止关于u w b 有 两种技术方案，一种是以f r e e s c a l e 公司为代表的d s c d m a 单频带方式，另一种 是由英特尔、德州仪器等公司共同提出的多频带o f d m 方案。 1 3 论文研究内容 无线传感器网络的覆盖问题和部署问题作为无线传感器网络的两个比较基础 的课题，对其的研究是非常有必要的。本文对无线传感器网络的覆盖与部署问题 进行了较为深入的研究，主要做了以下工作： ( 1 ) 对随机部署的无线传感器网络的覆盖性问题进行了研究，介绍了无线传 感器网络的几种覆盖模型，总结了无线传感器网络覆盖问题的分类，详细研究了 较为典型的最坏与最佳情况、暴露穿越等几种覆盖算法，分析了它们的基本理论、 实现方法和优缺点。最后利用所建立的数学模型，结合图论、概率论和统计学等 方面的知识，提出了基于k 覆盖度的覆盖控制算法，给出了节点覆盖度的计算公 式。 ( 2 ) 总结了传感器节点部署问题的国内外研究现状，总结了较为典型的几种 算法。在现有算法的基础上，论文提出了一种基于蜂窝网格的传感器节点部署算 法，并通过仿真实验证明了蜂窝网格在节点部署上能够最大化覆盖面积。 ( 3 ) 对传感器网络内外层节点寿命进行了研究，从理论上提出了一种理想分 布模型。该方法把网络中的冗余节点从内层到外层依次部署，能够有效提高网络 的寿命。 1 4 论文组织结构 本论文分为六章，其中： 第1 章：叙述了无线传感器网络产生背景，同时介绍了无线传感器网络主要应 用领域和国内外研究现状，并对本论文的主要研究工作和论文组织结构进行了说 明。 电子科技大学硕士学位论文 第2 章：介绍了无线传感器网络相关技术，如无线传感器网络的体系结构、无 线传感器网络的特点，最后介绍了无线传感器网络的性能评价指标。 第3 章：介绍了无线传感器网络覆盖和部署相关技术，对无线传感器网络覆盖 问题进行了分类，最后总结了传感器节点部署的评价指标。 第4 章：介绍了无线传感器网络的几种覆盖模型，详细研究了几种较为典型的 覆盖算法。最后提出了基于k 覆盖度的覆盖控制算法，给出了节点覆盖度的计算 公式，并论证了算法的有效性。 第5 章：分析了覆盖问题上较为典型的几种算法，并在现有算法的基础上，提 出了一种基于蜂窝网格的传感器节点部署算法，并通过仿真实验证明了蜂窝两格 在节点部署上能够最大化覆盖面积。对传感器网络内外层节点寿命进行了研究， 从理论上提出了一种理想分布模型。 第6 章：总结了论文所做的工作，并对未来工作进行了展望。 1 5 小结 无线传感器网络有非常广阔的应用前景。本章叙述了无线传感器网络的研究背 景，分析了无线传感器网络主要应用领域和国内外研究现状，并对本论文的主要 研究内容和论文组织结构进行了说明。 1 0 第二章无线传感器网络相关技术 第二耄无线传感器网络相关技术 2 1 无线传感器网络的体系结构 2 1 1 无线传感器网络的形成过程 一般两言，无线传感器两络节点的放置方式主要有两种：第一种是按一定要求 和规律进行放置，这种情况下，往往手动配置节点，信息通过预定路径传输；第 二种是按一定统计撬律随视放置，如空投撤布等，这种情况在模型形式上具有随 机性和不确定性。前者与一般的传感网络基本类似，没有太大区别。而后者的节 点闻通过自维织的方式构成网络，体现了无线传感器溺络的鲁组织特性，可以看 成是无线传感器网络的典型代表。因此，随机形成的无线传感器网络是论文的主 要砑究对象。 图2 1 描述了无线传感器网络的形成过程。首先，随机抛撒传感器节点，可以 采取人工、机械和空投等方法；第二步是抛撒后豹传感器节点进入到鑫检启动的 唤醒状态，每个传感器节点会发出信号侦测周围传感器节点并记录；第三步是这 些传感器节点会根据偾测刘的周圈传感器带点的情况，采用一定的组圈算法，形 成按一定规律组合的网络；第四步是组成网络的传感器节点根据一定的路由算法 选择合适的路径进行数据通讯。 镱 。舞 随机抛撒节点 唤醒和互相侦测 自组织成网络 选择路由进行通讯 疆2 i l 无线黄感器嬲络熬形成过程 电子科技大学硕士学位论文 2 1 2 网络体系结构 传感器网络是由为数众多的传感器节点所构成的网络系统，而传感器节点之间 的通讯方式则是采用无线通讯方式，极为方便。在传感器网络的架构下，传感器 的设计以省电、价格低廉、体积小、且具有感知环境的能力为目标，传感器本身 就像是一台小型计算机，并配备了简单的感知、运算处理、无线传输等装置，而 感知装置可以针对环境中我们所感兴趣的事务( 如温度、声音、光源等) 进行侦 测，并将所收集的数据先做简单运算处理后，再通过无线传输装置将数据回传给 基站，最后，我们就可以根据基站所收集的资料，了解环境的状态，并开发出相 应的应用。 传感器网络的基本架构如图2 2 所示，首先将大量的传感器部署在待感知的感 知区域，组织成簇结构的网络，用来搜集各种环境数据，所侦测数据可以为温度、 湿度、光度、压力、声音、二氧化碳浓度等，再将搜集到的信息通过基站传回给 管理者或使用者。 图2 2 传感器网络体系结构 每个传感器并不知道自己与其它传感器的相对位置，因此传感器网络必须使用 自组织协议，将传感器之间自动组织起一个通讯网络，使得所有感知区域中的感 知数据，皆能通过自组织所建立的网络，将信息送到基站。基站的功能则类似网 关，将感知网络的数据透过i n t e n l e t 、卫星或是其它传输媒介，传送到后端的服务 器，即应用程序或管理者手中。 1 2 第二章无线传感器网络相关技术 2 1 3 节点组成 在不同应舟中，传感器网络节点的组成不尽相同，但一般都由数据采集、数据 处理、数据传输和电源这4 部分组成。被检测物理信号的形式决定了传感器的类 型。处理器通常选用嵌入式c p u ，如m o t o r o h 的6 8 h c l 6 、a r m 公司的删7 和h l t d 的8 0 8 6 等。数据传输单元主要由低功耗、短距离的无线通信模块组成，比 如r f m 公司的t r l o 等。因为需要进行较复杂的任务调度与管理，系统需要一 个微型化的操作系统，u cb 诎d e y 为此专门开发了1 诅y o s ，当然，u c o s _ n 和嵌 入式等也是不错的选择1 2 】。 一般来说，无线传感器节点由以下几个物理部分构成： ( 1 )由微处理器或微控制器构成的计算子系统，负责控制传感器、执行通信 协议及处理传感数据的算法 ( 2 ) 用于无线通信的短距离无线收发电路，即通信子系统： ( 3 )由一组传感器和激励装置构成的传感子系统； ( 4 ) 能量供应子系统，包括电池和交壹流转换器。 实际应用中，并不是所有的节点都需要控制模块。一般而言，包括传感器、 a d c 、c p u 及存储器、通信模块、控制模块及电源( 髓量) 等，当不需要控制作 用时，节点组成如图2 3 中粗线框内部分所示。所有这些模块组装成一个火柴盒大 小甚至更小的传感器节点，各模块相互协作以完成一项共同的任务。 图2 0 传感器节点的基本构成 除此之外，根据具体应用的需要，节点可能还会有定位系统、电源再生单元和 移动单元等，其中电源再生单元是最重要的模块之一，有的系统可能采用太阳能 电子科技大学硕士学位论文 电池等方式来补充能量，但是大多数情况下传感器节点的电池是不可补充的。定 位系统可咀使用g p s 模块，但是g p s 模块价格昂贵且体积难以减少，所以不可能 全部节点都使用g p s 来进行定位。除此之外，g p s 定位还受到其他限制，如网络 放置于建筑物内部等。通常情况下是在整个网络中会有某些传感器节点配有g p s 系统，其它节点通过局部定位算法得到它们与配有g p s 的节点之间的相对位置， 这样所有节点都能知道各自的具体位置了。除借助g p s 的定位方式外，还有离散 梯度法等间接定位方式。 无线传感器网络中的节点不但要完成信息的采集、传输、预处理等，有时还涉 及到较为复杂的任务调度及管理，因此在传感器网络中节点还可能带有嵌入式操 作系统以进行更有效的管理，嵌入式操作系统可以是通用的如u c o s i i 等，也可以 是专门针对传感器网络开发的操作系统，如u cb 础翻e y 开发的弛y o s 。 目前，无线传感网络的节点设计主要有两种方法：一种是利用市场上可以获得 的商业元器件构建传感器节点，如围绕t i n y o s 项目设计的系列硬件平台；另一种 方法是采用m e m s 和集成电路技术，设计包含微处理器、通信电路、传感器等模 块的高度集成化传感器节点，如s m a nd u s t 、w i n s 等。 节点都具有传感、信号处理和无线通信功能。根据应用的需求，节点的体积和 质量都应比较小，比如要小到足以使它悬浮在空中进行数据采集。因此，节点的 电源模块采用只能携带有限能量的电池来实现。同时，更换节点电池的成本比重 新布放节点还要高，这就决定了无线传感器在使用过程中不太可能更换电池，因 而节能成为无线传感器网络设计的核心，在进行节点设计时应尽量采用寿命较长 的电池及低功耗器件。 2 2 无线传感器网络的特点 无线传感器网络与传统的无线网络以及在组网形式上相似的移动a dh o c 网络 相比，它们有着明显不同的设计目标、技术要求和应用要求。 传统的无线网络和m a n e t 网络都是以传输数据，完成通信为目的的，中间节 点仅仅负责分组数据的转发，它们注重在高度移动的环境中通过优化路由和资源 管理策略，最大化带宽的利用率，同时为用户提供定的服务质量。 而无线传感器网络是以数据为中心，获取信息为目的的，中间节点不但要转发 数据，还要进行与具体应用相关的数据处理、融合和缓存，除了少数节点可能移 动外，大部分节点都是静止的。无线传感器网络有时运行在恶劣甚至危险的远程 1 4 第二章无线传感器网络相关技术 环境中，传感器节点的电池无法补充更新；即使无线传感器网络工作在友好的环 境中，对数量巨大的传感器节点进行电池更换也是不现实的。因此设计有效的策 略延长网络的生存寿命是无线传感器网络的核心闯题，能量有效的设计准则贯彻 在无线传感器网络的硬件、软件、算法和协议等各个层面。无线传感器网络的主 要特点如下： ( 1 ) 网络节点密度高，传感器带点数量众多，单位面积内所拥有的网络节点 数较多，