（计算机科学与技术专业论文）无线传感器网络节点定位算法研究(1).pdf

国防科技大学研究生院学位论文 ff, 摘要 无线传感器网络是由大量随机分布的集成有传感器、数据处理单元和通信模 块的微小节点通过自组织方式构成的网络。近年来，无线传感器网络技术取得了 飞速发展，在工农业、军事国防、环境监测等许多领域都有着重要的科研价值和 实用价值，而网络中传感器节点自身定位是无线传感器网络大多数应用的基础， 因此在无线传感器网络的各个研究方向中，节点定位已经成了非常重要的一个研 究方向。 本论文的研究工作紧紧围绕无线传感器网络节点定位算法研究这一课题进 行，主要包含以下工作： 1 介绍了无线传感器网络节点定位的研究背景及意义、应用价值和国内外研 究现状。 2 介绍了无线传感器网络的相关技术和节点定位概念及定位基本原理。 3 分析了无线传感器网络节点定位技术的研究现状，讨论了定位算法的各项 性能评价指标，并将当前各种定位算法及现有的典型定位系统按不同标准 分类讨论，然后介绍了目前节点定位技术尚需考虑的问题。 4 在r o c r s s i 节点定位算法的基础上，为了减小无线电传播的各向异性对 算法定位精度的影响并减少网络中锚节点的数目，分别提出了基于交叠环 思想的f t p l 算法和d m e l 算法。对三种算法进行了理论分析，然后结 合加权质心定位算法，对四种算法分别进行了仿真验证，并对仿真结果作 了进一步分析比较。 5 ，工作总结及下一步工作方向的展望。 主题词：无线传感器网络，锚节点，节点定位，定位算法，定位系统 第i 页 国防科技大学研究生院学位论文 a b s t r a c t w i r e l e s s $ c n $ o rn e t w o r k s ( w a r cs e l f - 0 r g a n i z e dn e t w o r k sw i t hag r e a td e a lo f s m a l lr a n d o md i s t r i b u t e d 辩锄峨w h i c ha r ec o m p o s e do fs a 贼d a t ap r o c e s s i n gu n i t a n dc o m m u n i c a t i o nm o d u l e f o rt h e p a s tf e wy e a r s , w s nh a s a c c e s s e dr a p i d d e v e l o p m e n t , a n dh a si m p o r t a n tv a l u eo fr e s e a r c ha n du s ei nm a n yf i e l d s , j u s t1 i l ( c m i l i t a r ya f f a i r s , i n d u s t r y , a g r i c u l t u r e ，e n v i r o m e 肛t m e d i c 司t r e a t m e n ta n ds oo i l h o w e v e r , s e l f - l o c a l i z a t i o no fw s n h a sb e e nt h eb a s i so fm o s to ft 1 5 0 $ i nw s n ，n o d e l o c a l i z a t i o nh a sb e e na ni m p o r t a n ta n dc r i t i c a lr e s e a r c hd i 托c 出mi nt h es t u d yo f w s n t h er e s e a r c ho ft h i sp a p e ri sb a s e do nt h ea n a l y s i so fag r e a td e a lo fr e c e n t t e c h n i c a lr e l x ) r t sa n dr e s e a r c hr e s u l t so nw s n i t sm a i nw o r ki 4 c l u d e s ： 1 t h er e s e a r c hb a c k g r o u n d , p r a c t i c a lu t i h t ya n dp r e s e n ti n v e s t i g a t o r yh e a d w a y o f w s na th o m ea n da b r o a da r ei n t r o d u c e d 2 s o m er e l a t o dt e c h n i q u e so f w s na n dt h e n c e p ta n db a s i cp r i n c i p l e so f n e d e l o c a l i z a t i o ni n 、) l r s na r ca l s oi n t r o d u o x l 3 1 1 坞r e s e a r c hs t a t u sa n ds o m em a i np e r f o r m a n c ee v a l u a t i n gc r i t e r i o n so f s e l f - l o c a l i z a t i o ni nw s na r ea n a l y z e d , a n dc u r r e n tl a l i z a t i o na l g o r i t h m sa n d l o c a l i z a t i o ns y s t e m sa r ec l a s s i f i e di n t om a n yc a m g o r i e s o r d i n gt od i f f e r e n t s t a n d a r d s t h e n , s 嘲ei s 3 u e sw h i c hn e e dt ob er e s o l v e di nf u t u r e 黜 d i s c u s s e d 4 b a s e d0 1 1t h es h o r t a g eo fr o c r s s ia l g o r i t h m , f t p lu l g o f i t h ma n dd 正l a l g o r i t h ma r cp r o p o s e di n0 r d e rt od e c r e a s eh a r d w 却ec o s ta n dt h ee f f e c to f r a d i oa n i s o t r o p y t h e n , p o m b i n e dw i t hw e i g h t e dc e n t r o i dl o c a l i z a t i o n a l g o r i t h mb a s e d0 1 1r s s if o rw s n ，t h et h e o r e t i c a l 删y s i sa n de m u l a t i o no f t h e s ea l g o r i t h m sa r ei m p l e m e n t e d 5 s u m m a r ya n dt h ed i r e c t i o no f r e s e a r c ha r em a d e k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ，a n c h o rn o d e ，n o d el o c a l i z a t i o n ， l o c a l i z a t i o na l g o r i t h m ，l o c a l i z a t i o ns y s t e m 第i i 页 国防科技大学研究生院学位论文 表3 1 四种测距技术性能比较。 表目录 表3 2 四种距离无关节点定位算法的性能比较3 0 表4 1 三种定位算法理论分析比较 5 6 表4 2k = 3 2 时，四种算法在不同信标数目下的定位误差5 8 表4 3k = 5 时，四种算法在不同信标数目下的定位误差。5 9 表4 4n - - - 2 5 时，不同信道衰减因子下的定位误差变化比较。5 9 表4 5 四种算法通信开销比较 第页 国防科技大学研究生院学位论文 图目录 图1 1典型的无线传感器网络系统结构和节点组成 图2 1 传感器节点的组成。 图2 2 平面结构示意图 图2 3 分级结构示意图 图2 4a c e 经过三次迭代后的网络。 。3 8 9 1 0 图2 5 自组织形成网络简要流程图1 5 图2 6 三边测量法图示 图2 7 三角测量法图示 图2 8 极大似然估计法图示 图3 1 使用声波进行测距 图3 2t d o a 定位原理图示 1 7 图3 3 原予多边算法与多边协作算法图示2 5 图3 4 到达角定位法图示 图3 5 d v - h o p 算法举例 图3 6 图3 7 图3 8 图3 9 p i t 原理图示。 a p i t 测试举例 凸规划算法图示 非多跳节点定位算法图示。 图3 1 0 多跳方式定位三阶段图示 图3 1 1s p a 定位算法图示 图3 1 2a f l 算法图示 图3 1 3 利用r i n g - o v e r l a p p l n g 定位节点图示 图3 1 4 利用移动锚节点定位图示 图3 1 5 利用网络分簇定位节点图示 2 8 2 9 3 0 3 4 。3 5 ，。，。3 7 3 9 4 1 图3 1 6 利用网络分簇定位节点图示4 3 图3 1 7 ( a ) 网格一扇区图示( b ) 网格记分表及相应的交叠区图示。4 4 图3 1 8 测距后网络的可能形态 图4 1r o c r s s i 算法图示。 图4 2f t p l 算法图示 图4 3d m e l 算法图示。 图4 4 接受信号强度与距离关系图示 图4 5 理想空间中四种算法的定位误差 4 8 5 0 5 2 5 7 5 8 第页 国防科技大学研究生院学位论文 图4 6 复杂空间中四种算法的定位误差5 9 图4 7 不同传播空间中定位误差变化比较 图4 8 四种算法通信开销比较图示 6 0 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材科与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：玉缮笾盛墨圜鳖芏直宝焦差洼盈塞 学位论文作者签名：缝盘盘敬日期：知彭年乜月l 日 学位论文版权使用授权书 本人完全了解国防哥 学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：丕堡佳盛墨圜鳖堇直基：焦篡洼丑窥 学位论文作者签名：遏基詹敬日期：知侔月f 7 日 作者指导教师签名：j 避旨期： 彩年i 1 月f 7 日 国防科技大学研究生院学位论文 第一章绪论 1 1 课题背景 无线传感器网络是当前在国际上备受关注的、涉及多学科高度交叉、知识高 度集成的前沿热点研究领域。它综合了传感器技术、嵌入式计算技术、现代网络 及无线通信技术、分布式信息处理技术等，能够通过各类集成化的微型传感器协 作地实时监测、感知和采集各种环境或监测对象的信息，这些信息通过无线方式 被发送，并以自组多跳的网络方式传送到用户终端，从而实现物理世界、计算世 界以及人类社会三元世界的连通。传感器网络具有十分广阔的应用前景，在军事 国防、工农业、城市管理、生物医学、环境监测、抢险救灾、防恐反恐、危险区 域远程控制等许多重要领域都有潜在的实用价值，已经引起了许多国家学术界和 工业界的高度重视，被认为是对2 1 世纪产生巨大影响力的技术之一。 无线传感器网络作为一种新型的信息获取和处理模式，其典型的工作方式如 下：使用飞行器将大量的传感器节点抛撒到感兴趣的区域( 节点数量通常为几百 到几千个) ，节点通过自组织方式快速形成一个无线网络。随机分布的集成有传 感器、数据处理单元和通信模块的节点借助于内置的形式多样的传感器测量其所 在周边环境中的热、红外、声纳、雷达和地震波信号，从而探测包括温度、湿度、 噪声、光强度、压力、土壤成分、移动物体的大小、速度和方向等众多两络部署 者感兴趣的物质现象。在网络中，节点既是信息的采集和发出者，也是信息的路 由者，采集的数据通过多跳路由到网关。网关( s i n k ) 是一个特殊的节点，它可通 过i n t e m e t 、移动通信网络、卫星等与监控中心通信，也可利用无人机飞越网络上 空，通过网关采集数据。 1 2 课题研究意义及应用价值 随着无线传感器网络技术的逐渐成熟，它在军事、医疗、环保、空问探索及 其他工商业领域均产生了广泛的应用前景。 1 2 1 军事应用 在军事应用中，无线传感器网络将成为伽s i 玎( c o m m a n d , c o n t r o l , c o m m u n i c a t i o n , c o m p u t i n g , i n t e l l i g e n c e ，s u r v e i l l a n c e , r e c o n n a i s s a n c ea n dt a r g e t i n g ) 系统不可或缺的一部分。c 4 i s r t 系统的目标是利用先进的高科技技术，为未来的 现代化战争设计一个集命令、控制、通信、计算、智能、监视、侦察和定位于一 第1 页 国防科技大学研究生院学位论文 体的战场指挥系统，受到了军事发达国家的普遍重视。无线传感器网络的自组织 性和容错能力使其不会因为某些节点在恶意攻击中的损坏而导致整个系统的崩 溃，这使得它非常适合应用在恶劣的战场环境中，包括：监控敌方部署、装备、 军火情况，战场监视，定位，战场损失评估，核、生化武器攻击监测和侦察。 1 监控我军兵力，装备和物资。指挥官可以实时地监控我方部队的状况，在 战场上通过传感器网络监控我军装备和物资的状态和可用性。在每个部队、车辆、 装备和关键物资上安装传感器，这些传感器可以报告相应的状态。所有这些数据 通过汇聚节点最终发送给终端的指挥官，最后融合来自各战场的数据后再将数据 发送到更高层的指挥官。 2 战场监控。对关键的区域、可通过的路线，可以快速地部署传感器来严密 监控这些军事要地的各种情况。随着监控方法的发展和新方案的提出，新型传感 器网络可以随时部署到军事要地。 3 侦察敌方兵力部署和地形。传感器网络可以部署在敌军前线，以更隐蔽的 方式近距离地观察敌方的布防；也可以直接将传感器节点撒向敌方阵地，在敌方 还未来得及反应时迅速收集利于作战的信息。 4 目标定位。传感器网络可以嵌入导航系统，来提供精确的定位信息。 5 侦察和探测核、生物和化学攻击。在化学和生物战中，在爆炸中心附近及 时、准确地采集数据非常重要，传感器网络可以部署在我军前沿来作为化学和生 物攻击的预警系统，这样就可以为我军提供宝贵的反应时间，大幅度降低人员伤 亡。传感器网络也可以在核、生物和化学攻击后提供精确的探测数据，我们可以 部署传感器网络来探测数据从而避免核反应部队探测数据时受到核辐射1 4 】。 1 2 2 环保应用 在环保领域，可以在应用区域部署无线传感器网络以进行森林防火、洪水监 测、污染监控、精确农业和生物种群研究等。 1 森林火灾预报。由于传感器节点可以有针对性地、随机地、密集地部署在 森林中，传感器节点可以准确地测量出火灾开始的位置，并在火灾发展到不可控 制前将数据发送到终端的监控中心。数以干计的传感器节点都集成了无线电收发 装置，并且它们都采取有效的节能方式工作。可以采用太阳能电池，因为传感器 在部署好了后可能几个月甚至几年都不需要人为管理。传感器节点之间相互合作 来执行分布式的感知，可以克服由于树木、岩石等物体的阻碍而造成的无线通讯 困难。 2 复杂生态环境的测绘。复杂生态环境的测绘需要集成复杂的时间和空间的 信息。远距离感知和自动的数据采集技术的发展使得在空间、光强、温度的测量 第2 页 国防科技大学研究生院学位论文 方面有较大的进步，并且单位面积内的成本可以减少很多除了这些优势外，传 感器节点还可以与因特网相连，从而使得远端的客户可以监控和观察环境中的复 杂生态情况。 3 洪水检测。洪水检测的一个例子是美国的a l e r t 系统，系统中有数种类 型的传感器来监测降雨量、河水水位和气候。这些节点以预先指定的方式将数据 发送给数据库中心。其它研究项目，如c o m e l l 大学的c o u g a r 设备数据库项目， r u t g e r s 的d a t a s p a c e 项目，都在研究分布式的方法和传感器网络节点的相互关系 来提供即时的和长时间的查询 4 1 。 1 2 3 其他应用 在医疗领域，无线传感器网络可以用来无线监测人体生理数据、老年人健康 状况监控、远程医疗和医院药品管理等。同时，无线传感器网络可以用在进行星 球表面大范围、长时期、近距离的监测和探索以及选择着陆场地等空间探索领域 中。另外，无线传感器网络的其他应用还包括紧急和临时场合应急通信( 如在地 震、水灾、强热带风暴灾害地区、边远或偏僻野外地区) 、交通流量监控及智能 化房屋等。 图1 1 典型的无线传感器网络系统结构和节点组成 第3 页 国防科技大学研究生院学位论文 1 3 国内外研究现状 由于无线传感器网络巨大的科研意义和实用价值，它已经受到世界主要科技 大国的高度关注，并在国家层面上制订了相关的政策和战略。从2 0 0 0 年起，国际 上开始出现一些有关传感器网络研究成果的报道，美国自然科学基金委员会( n s f ) 2 0 0 3 年制定了传感器网络研究计划，支持相关基础理论的研究美国国防部和各 军事部门都对传感器网络给予了高度重视，把传感器网络作为一个重要研究领域， 并设立了一系列的军事传感器网络研究项( c 4 k i s r 计划、s m a r ts e n s o rw e b 、灵 巧传感器网络通信、无入值守地面传感器群、传感器组网系统、网状传感器系统 c e c 等) 。美国英特尔公司、微软公司等信息业巨头也开始了传感器网络方面的研 究工作。日本、德国、英国、意大利等科技发达国家也纷纷展开该领域的研究工 作。 美国五角大楼提出了。智能尘埃”的设计思想，目的是在战场上抛洒数千个 微小的具有无线通信功能的传感器模块，用于监控敌人的活动情况。分布在战场 各个角落的节点采集相关原始数据并进行滤波，再通过自组织的无线传感器网络 把重要的信息发送回指挥部。该智能传感器模块正处于原型开发阶段，由如州大 学伯克利分校和英特尔公司共同研制。 美国陆军已确定努力开发多层次集成式传感器复杂系统灵巧传感器网络 通信，并认为这是建成未来目标部队的关键之一。“灵巧传感器网络通信( s s n c ) ” 概念已被批准为2 0 0 1 年的一项科学技术目标( s 1 d ) 计划。该科学与技术目标计 划将在2 0 0 1 2 0 0 5 年期间实施。灵巧传感器网络通信的目标是一个通用的通信基 础结构，是支援前方部署，将无人值守式弹药、传感器和未来战斗系统所用的机 器人系统连成网络的一套灵巧网络积装各。换句话说，s s n c 将成倍地提高单一传 感器的能力，使作战指挥员能够更好、更快地做出决策，从而改进未来战斗系统 的生存能力。 民用方面，由加州大学伯克利分校d a v i dc u l l e r 教授领导的科研小组在缅因州 的大鸭岛上布置了3 2 个节点组成的传感器网络，实现对一种海燕生活习性的监测。 节点有分布在环境中的，有分布在鸟巢里面的。每个节点具有温度、光线、气压、 湿度传感器，感知各种信息，通过网络传送给岛上的基站，基站与笔记本电脑相 连，电脑再通过通信卫星将数据传回给伯克利的实验中心。实验中心的专家通过 各种数据的融合，可以获知海燕的生活习性。例如通过分析巢内的温度值，可以 了解海燕觅食的习性，因为海鸟在不在巢内温度有差异川。 我国2 0 1 0 年远景规划和“十五”计划中将传感器列为重点发展的产业之一，与 此同时，中国下一代互联网( c n o i ) 项目、国家自然基金项目鄱十分支持w s n 研究， 第4 页 国防科技大学研究生院学位论文 包括无线传感器节点的硬件设计、操作系统、网络路由技术、节能技术、覆盖控 制技术的研究等。 1 4 无线传感器网络节点定位问题 对于大多数应用，不知道传感器位置而感知的数据是没有意义的。传感器节 点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现 对外部目标的定位和追踪。另一方面，了解传感器节点位置信息还可提高路由效 率，为网络提供命名空闻，向部署者报告网络的部署质量，实现网络的负载均衡 和网络拓扑的自配置。定位技术作为无线传感器网络大多数应用的基础，是无线 传感器网络的关键技术之一，它分为两大类：一类是无线传感器网络对自身传感 器节点的定位，另一类是无线传感器网络对外部目标的定位，其中前者是后者的 基础，本文主要讨论前者。 从1 9 9 2 年a t & tl a b o r a t o r i e sc a m b r i d g e 开发出室内定位系统a c t i v eb a d g e 至 今，研究者们一直致力于这一领域的研究，事实上，已有许多系统和算法能够解 决w s n 自身定位问题。但是，每种系统和算法都用来解决不同的问题或支持不同 的应用，它们在用于定位的物理现象、网络组成、能量需求、基础设施和时空的 复杂性等许多方面有所不同。这个领域的研究从总体上说尚处于一个起步的阶段， 需要继续深入研究开发，提出更多的高效算法，促进无线传感器网络进一步的普 及应用嗍。 由于传感器节点的体积和质量都应比较小，比如要小到足以使它悬浮在空中 进行数据采集，而节点的电源模块只能采用携带有限能量的电池来实现，因此电 池携带能量的能力是传感器网络发展的瓶颈之一。受节点能源条件的限制，节点 定位技术当前要解决的主要问题是如何以最小的通信开销和硬件代价实现节点定 位。本文以此为目标，对无线传感器网络节点定位问题进行了深入的研究。 1 5 论文的组织结构 本章的论文组织如下： 第一章绪论 介绍本课题的研究背景和意义，联系比较国内外发展现状，阐述本课题的主 要研究内容。 第二章无线传感器网络及节点定位原理 本章首先介绍了无线传感器网络的特点、体系结构、组织和部署，然后阐述 了节点定位的基本概念，根据计算节点位置的基本方法，介绍了无线传感器网络 第5 页 国防科技大学研究生院学位论文 节点定位的基本原理。 第三章无线传感器网络节点定位系统和定位算法综述 首先论述了无线传感器网络节点定位算法的各项性能评价指标。详细介绍了 当前典型的无线传感器网络节点定位算法及其优缺点，按不同分类标准将其分类， 并介绍了与典型算法相关的一些定位系统，然后指出了当前无线传感器网络节点 定位算法尚待解决的问题。 第四章兀甲l 算法和d m e l 算法的提出及实现 在r o c r s s i 定位算法的基础上，为了减小无线电各向异性传播对算法定位精 度的影响并减少网络硬件代价和节点通信的开销，分别提出了基于交叠环思想的 f r p l 算法和d m e l 算法。对三种算法进行了理论分析，然后结合加权质心节点定 位算法对四种算法分别进行了仿真验证，并对仿真结果作了进一步分析比较。 第五章结束语 总结全文，展望下一步研究工作。 第6 页 国防科技大学研究生院学位论文 第二章无线传感器网络及节点定位原理 本章首先介绍了无线传感器网络的特点、体系结构，描述了无线传感器网络 的部署及自组织，然后介绍了无线传感器网络节点定位相关的基本概念、术语， 最后介绍了节点定位技术的基本原理及目标。 2 1 无线传感器网络 无线传感器网络由大量高密度分布的处于被观测对象内部或周围的传感器节 点组成。其节点不需要预先安装或预先决定位置，这样提高了动态随机部署于不 可达或危险地域的可行性。 2 1 1 无线传感器网络的特点 无线传感器网络属于一种特殊的a d - h o c 网络，它的实现需要自组织网络技术， 它虽然与传统的a d - h o c 网络有很多相似的地方，但无线传感器网络与传统无线网 络( 如，ia n 和蜂窝移动电话网络) 有着不同的设计目标，后者在高度移动的环 境中通过优化路由和资源管理策略最大化带宽的利用率，同时为用户提供一定的 服务质量保证。而无线传感器网络中除少数节点需要移动外，大部分节点都是静 止的。由于它们通常部署在人类无法接近的恶劣甚至危险的远程环境中，对电池 的更换是非常困难甚至是不可能的，但是无线传感器网络的生存时间却要求长达 数月甚至数年，因此，如何在不影响功能的前提下，尽可能节约无线传感器网络 的电池能量成为无线传感器网络软硬件设计中的核心问题。 随着研究的不断深入，人们发现无线传感器网络与传统无线网络有着明显不 同的技术要求，前者以数据为中心，数据是被分散处理的，系统会根据需要尽早 对数据进行处理，这样可以减少网络的流量，降低功耗并提高系统利用率。而后 者以传输数据为目的，一些为a d - h o c 网络设计的协议和算法并不适合传感器网络 的特点和应用的需求。和网络中单个节点上的信息相比，无线传感器网络的应用 程序更关心与其相关的中间节点上的数据处理、融合和缓存等。在密集的无线传 感器网络中，相邻节点间的距离非常短，低功耗的多跳通信模式节省功耗，同时 增加了通信的隐蔽性，避免了长距离的无线通信易受外界干扰的影响，这些独特 的要求和制约因素为无线传感器网络的研究提出了新的技术难题嗍。 与传统的无线网络相比，无线传感器网络具有以下特点： i 电源容量有限。无线传感器网络节点一般由电池供电，而且在使用过程中 也不能给电池充电或更换电池。因此无线传感器网络设计的基本原则就是要以节 第7 页 国防科技大学研究生院学位论文 能为前提。 2 传感器节点由于受到低成本、小体积和低功耗的限制，其硬件、软件资源 非常有限。 3 无中心。无线传感器网络一般是一个对等式的网络 4 自组织。无线传感器网络的布设和展开无需依赖于任何预设的基础设施。 5 多跳路由。网络中节点通信距离有限，如果希望与较远的节点进行通信， 则需要通过中间节点多跳路由来实现。 6 动态拓扑。无线传感器网络是一个动态的网络，节点可以随处移动，网络 的拓扑结构会随时发生变化，因此网络应该具有动态拓扑组织功能。 7 节点数量众多，分布密集。为了对一个区域执行监测任务，传感器节点往 往分布得非常密集，利用节点之间高度连接性来保证系统的容错性和抗毁性。 2 1 2 无线传感器网络的体系结构 2 12 1 节点组成 在不同应用中，传感器网络节点的组成不尽相同，但一般都由数据采集、数 据处理、数据传输和电源这4 部分组成，如图2 1 所示。被监测物理信号的形式决 定了传感器的类型。处理器通常选用嵌入式c p u ，如m o t o r o l a 的6 8 h c l 6 ，a r m 公司的a r m 7 和i n t e l 的8 0 8 6 等。数据传输单元主要由低功耗、短距离的无线通 信模块组成，比如r f m 公司的t r l 0 0 0 等。因为需要进行较复杂的任务调度与管 理，系统需要一个微型化的操作系统，u cb e r k e l e y 为此专门开发了t i n y o s ，当然， u c o s - 和嵌入式l i n u x 等也是不错的选择【4 】。 图2 1 传感器节点的组成 根据具体应用需求，节点还可能会有定位系统以确定传感器节点的位置，有 移动单元使得传感器可以在待监测地域中移动，或具有供电装置以从环境中获得 第8 页 国防科技大学研究生院学位论文 必要的能源。此外，还必须有一些应用相关部分，例如，某些传感器节点有可能 在深海或者海底，也有可能出现在化学污染或生物污染的地方，这就需要在传感 器节点的设计上采用一些特殊的防护措施。图2 1 描述了节点的组成，其中实心箭 头的方向表示数据在节点中的流动方向。 2 1 2 0 体系结构 在传感器网络中，节点任意散落在被监测区域内，这一过程是通过飞行器撒 播，人工埋置和火箭弹射等方式完成的，节点以自组织方式构成网络。根据节点 数目的多少，传感器网络可按平面结构和分级结构来构建。平面结构比较健壮， 但是控制开销大，可扩展性不佳，主要适用于中小型网络。在分级结构中，网络 被划分成簇，每个簇包含一个簇头和多个簇成员，簇头和网关构成虚拟骨干网。 分级结构的优点是网络可扩充性好，容易实现网络的管理和同步，主要用于大规 模的无线传感器网络。 1 平面结构 4 1 在平面结构的无线传感器网络中，所有节点具有相同的地位，所以又被称为 对等式结构。平面结构的网络比较简单，源节点和目的节点间一趱存在多条路径， 网络负荷由这些路径共同承担，一般情况下不存在瓶颈，网络比较健壮。但是在 无线传感器网络中，由于节点数量较大，密度较高，平面结构在节点的组织、定 位、节点与基站之间的路由建立、控制与维持的报文开销上都存在着很大的问题， 这些开销会占用很大的带宽，影响网络数据的传输速率，严重情况下甚至会造成 整个网络的崩溃。另外，节点在进行报文传输时，由于所有节点都起着路由的作 用，因此，某个节点在产生并发送报文之后，在这个节点和基站接收器之间会使 得大量的节点参与存储转发工作，很难进入休眠状态，从而使整个系统在宏观上 将损耗很多能量。平面结构的可扩充性差，每个节点都需要知道到达其它所有节 点的路由，维护这些动态变化的路由信息则需要大量的控制信息。图2 2 所示为平 面结构。 图2 2 平面结构示意图 第9 页 国防科技大学研究生院学位论文 2 分级结构 4 1 在分级结构中，网络被划分为多个簇。每个簇由一个簇头和多个簇成员组成， 这些簇头形成了高一级的网络。分级后的网络如图2 3 所示。簇成员负责数据的采 集，而簇头节点负责簇问数据的转发，这大大减少了网络中路由控制信息的数量， 因此具有很好的可扩充性。簇头可以预先指定，也可以通过分簇算法选举产生。 由于簇头可以通过选举随时产生，所以分级结构具有很强的抗毁性，维护分级结 构需要节点执行分簇算法。 分级结构存在的一个明显问题就是簇头的能量消耗问题，簇头的发送和接收 报文的频率要高出普通节点几倍甚至十几倍，此时簇头在发送、接收报文时会消 耗很多能量，而且很难进入休眠状态，从而相对普通节点，其寿命要短的多。这 就需要在簇内执行合适的算法以更新簇头 分级结构比平面结构复杂的多，由此也产生了很多相应的算法和协议。分级 结构解决了平面结构中的网络堵塞问题，整体能量消耗较少，实用性也较高。下 面我们首先通过典型的层次路由协议i e a c h 协议的分簇过程来了解分簇思想，然 后介绍两种典型的网络分簇算法：a c e 算法和h e e d 算法。 图2 3 分级结构示意图 1 ) l e a c h ( l o we n e r g ya d 删v fc l u s t e r i n gh i e r a r c h ) l e a c h 协议是由m i t 的h e i n z e l m a n 等人提出的。它的主要思想是基于接 收信号的强度来形成簇，使用本地簇头作为到s i n k 节点的路由器。协议将所有节 点分为若干簇，每个簇选举一个簇头节点，簇头还可以组成更高层次的簇。簇头 接收本簇中节点发送的数据，实现数据融合功能，并向基站发送数据。由于向基 站发送数据需要很高能耗，每隔一段时间需要重新选举簇头，以保证功耗在所有 节点的平均分配。 在簇建立阶段，将所有节点划分为若干簇，每个簇选举一个簇头。每个节点 第1 0 页 国防科技大学研究生院学位论文 选取一个介于0 和l 之间的随机数。如果这个数大于门限值矸。，该节点成为簇 头。门限值计算方法如下： f ! i fn c o = 1 - p + r m o d ( 1 p ) ( 2 - 1 ) 。l o o t h e r 其中p 是簇头节点占全部节点的比例；，是现在的轮次；g 是在最近1 p 轮没有 成为簇头的节点集合。选举结束之后，新当选的簇头节点向所有节点广播自己成 为簇头的消息。根据收到广播信号的强弱，每个节点决定加入哪个簇，并通知该 簇的簇头。 在分簇完成后，簇中的所有节点按照t d m a 的方式向簇头发送数据，在持续 工作一段时间之后，网络进入下一轮工作周期，重新划分簇并选举簇头。 l e a c h 的优点是采用动态分簇，而且l e a c h 是完全分布式的，与一般的平 面多跳路由协议和静态分簇算法相比，l e a c h 可以将网络生命周期延长1 5 9 6 。但 是，动态分簇带来了额外的开销，如簇头更换等，它可能会抵消能耗上的收益。 p e g a s l s ( p o w e r - e 岱c i e n tq i l h e r i n gi ns e n s o ri n f o r m a t i o ns y s t e m ) 协议是在 l e a c h 协议基础上建立的协议，仍然采用动态选举簇头的思想，但为避免频繁选 举簇头带来的通信开销，采用无通信量的簇头选举方法，且网络中所有节点只形 成一个簇。t e e n ( t h r e s h o l d s e n s i t i v e e n e r g y e f f i c i e n t s e n s o r n e t w o r k p r o t o c 0 1 ) 协议 采用与l e a c h 协议相同的聚簇方式，但簇头根据与s i n k 点距离的不同形成层次 结构。 2 、a c e ( a ne m e r g e n ta l g o r i t h mf o rh i g h l yu 砸f o r mc l u s t e rf o r m a t i o n ) a c e 算法【5 0 】包含两个阶段：簇的形成和为了减少簇间重叠所需的簇的移动控 制。第一阶段：当一个节点满足一定条件决定升级为簇头时，它向它的邻居节点 广播一条脚 u i t 消息，接收到消息的邻居节点成为它的簇成员，在a c e 分簇过程 中，一个节点可以同时成为几个簇的成员，在最后阶段这个节点才选择它最终所 在的簇。第二阶段：一个簇的移动由它的簇头控制，每个簇头周期性的检测它的 成员来判断哪个成员更适成为这个簇的新簇头，判断的标准是假如这个节点成为 簇头后，簇内成员数目最大且与其它簇的交叠区域最小。一旦当前簇头找到新簇 头，它发送一条p r o m o t e 消息给新簇头，并广播一条a b d i c a t e 声明它已不是簇头。 这将使得原簇内的一些节点不再属于这个簇而一些新的节点也将会加入这个簇， 这使得簇看起来由原簇头移动到了新簇头的位置。 a c e 通过网络中每个节点的三次迭代来进行分簇，不同节点的迭代不需要同 步，迭代间隔服从均匀随机分布。节点有三种可能的状态：不属于任何簇，是一 个或多个簇的成员，簇头。在算法开始，每个节点经过随机迭代间隔等待下一次 第l l 页 国防科技大学研究生院学位论文 迭代，迭代开始时，节点的行为取决于它当前所处的状态。当下一个迭代开始时： ( 1 ) 若节点a 不属于任何簇，它将计算如果它升级为簇头后它的忠实成员的个数 l 。在这种情况下，这个数目就是节点a 的不属于任何簇的邻居节点的数目。 a 知道它已运行算法的时间t ，这时a 按式( 2 - 2 ) 计算形成新簇的极限函数 丘( f ) ，如果工2 厶，那么a 将通过产生一个随机的簇头d 并广播一条 r e c r u i t 消息来产生一个新簇，a 的邻居节点将会收到这条消息并加入到这个 簇中 一t 三 丘= 一乞w ( 2 - 2 ) 其中：t 是从算法开始已经经过的时问，“是算法执行的时间，d 是估计 的网络平均每个节点的度数，毛和如是决定指数曲线的常数，一般毛= 2 3 ， 如= 0 1 或乞= o 。 c 2 ) 若a 是一个簇头，a 将考虑移动簇的位置。它将检测所有的邻居节点以找出 新簇头。新簇头是指在其邻居节点中，或不属于任何簇或只在a 簇内部的节 点度数最大的节点由于新簇头不会是属于两个或多个簇的共同节点，新簇 头将会产生在簇间交叠较小的地方。如果新簇头是a 自身，a 继续原来的状 态；如果新簇头是b ，a 发送一条p r o m o t e 信息给b ，b 在接收到p r o m o t e 之 后，将发出一条带有a 簇头m 的r e c r u i t 消息。然后，b 的不在这个簇内的邻 居节点将以b 为头节点加入至4 簇内，同时簇内原有的且是b 的邻居节点的成 员将以b 作为它们的新头节点。一旦a 检测到b 的r e c r u i t 消息，a 将给它的 邻居发送一条a b d i c a t e 消息，属于a 而不属于b 的邻居节点在收到a b d i c a t e 后将离开这个簇。 ( 3 ) 如果a 是一个或多个簇的成员，经过随机迭代间隔等待下一个迭代。 节点通过记录每个邻居节点所在的簇可以快速得到它的忠实成员的个数。假 设每个节点运行a c e 需c l 个时间，c 是期望的每个节点迭代的平均次数，l 是 期望的迭代间隔的长度。在节点完成它的迭代过程后，如果c l 尚未终止，它将等 待另一随机迭代间隔直至它的下一个迭代；如果节点已经运行了c l 个时间，它将 结束运行此时，如果节点是簇头，它将立刻终止算法并通知它的邻居节点；如 果节点从属于一个或多个簇，它将等待它的所有簇头完成迭代，然后以他们作为 自身的最终头节点集合。 a c e 属于分布式可扩展的无线传感器网络分簇算法，算法收敛时间只与网络 节点密度相关，和网络规模大小无关，所形成的簇为高度规则、大小均匀的六边 形闭包且簇交叠很小，分簇所需的网络通信开销较小。 第1 2 页 国防科技大学研究生院学位论文 图2 4a c e 经过三次迭代后的网络 3 ) 珈b e d ( h y b r i de n e r g y - e f f i c i e n td i s t r i b u t e dc l u s t e r i n g ) h e e d 算法【5 1 】根据节点的剩余能量与节点度数或其与邻居节点的相邻度周期 性地选择簇头。h e e d 协议的网络模型如下：1 ) 节点是类静止的( 可以有少量的移 动) 2 ) 节点位置是未知的3 ) 所有节点具有相同的处理和通信能力，具有同等的 地位4 ) 每个节点具有固定数量的传输功率级别 簇头选择主要基于节点的剩余能量，为了进一步延长网络寿命，将簇内的通 信开销作为选择簇头的第二个参数。首先根据节点的剩余能量选出可能的初始簇 头集合，乖j 用第二参数进行筛选。簇内通信开销与簇的大小和簇内节点是否可用 可变发射功率进行通信有关。如果簇内节点使用相同功率与簇头通信，则此时簇 内的通信开销只与该簇头的节点度数相关；如果簇内通信时，节点的传输功率是 可调的，则该簇内的通信开销与刎煅p 相关。式( 3 ) 中m 表示簇内的节点数； 卉np l 忧表示节点v ，与簇头越通信所需的最小传输功率。 村 撕 a m r p = 旦1 。厂一( 2 - 3 ) 必 1 印：执行一次分簇的时间；i 坤：分簇间的时间间隔，1 k 1 印。每1 b + 1 k 个时间，网络进行一次分簇，分簇在每个节点需要地。个迭代操作，每一步需要 时间f c ，这个时间可以保证该节点能接收到每个邻居的信息。假设簇头节点所占比 例为c 耐，节点在执行h e e d 协议前，设置它升级为簇头的概率为c ! 瞄； f 口= = 詈型( 2 - 4 ) d m 其中点二。是节点当前的剩余能量，面至。是节点电池的最大能量。c 耐不能低 于阈值p 曲( 与k 成反比) 第1 3 页 国防科技大学研究生院学位论文 第i 个分簇完成后，簇头集合s o r t 为第i - 1 个迭代完成后的簇头集合与第1 个 迭代新加入的簇头集合的并集。节点选择s c h 中与其通信开销最低的节点作为 它的簇头( 如果是当前的一个簇头节点，sa i 中包含v i ) ，然后每个节点将其c 日耐 增加一倍。进入下一迭代。 如果一个节点升级为簇头，它需要发送一条c l u s t e rh e a dm s g 烈o d e ，id s e l e c t i o ns t a t u s ，c o s t ) ，如果它的c 日 1 ，则消息中的状态为t e n t a t i v e c h ，如 果c 日棚- - i ，则状态为f m a l _ c h 。如果节点在执行完h e e d 后，其簇头状态不是 f i n a lc h ，则它升级为簇头，状态为五n a l c h 。当一个状态为t c n t a t i v c的簇头 发现簇内有使得簇内通信开销更低的节点时，则降级为普通节点。 _ c h h e e d 协议是能量高效的分布式分簇算法，对网络节点分布、密度及功能无特 殊需求，分簇在o ( 1 ) 个迭代内完成，与网络拓扑及大小无关，且网络在节点分簇 后具有相当规则的簇头分布，可较好的实现延长