（控制理论与控制工程专业论文）基于遗传算法的无线传感器网络节点的自定位技术研究.pdf

浙江工业大学硕士学位论文 基于遗传算法的无线传感器网络节点的 自定位技术研究 摘要 无线传感器网络是一门综合了传感、计算、通信、信息处理等多学科交叉技术，在军 事、民用等各领域有着广泛的应用。在众多的应用研究中，节点首先必须确认自身位置信 息。因而，节点自定位技术是无线传感器网络的基础而关键的技术。 本文就无线传感器网络节点的自定位技术展开了研究，质心定位算法依赖于节点密度 和网络的连通性，故其定位误差极大；但质心定位算法简单，这对于能量有限的节点，是 其优势。为保持质心算法优势，本文提出了基于极大似然估计法测距方法的改进模型，对 质心算法坐标值进行修正，并用遗传算法对所改进的模型进行优化。算法简单的节点定位 能够节约能量，延长网络使用寿命。论文的主要工作和成果如下： 1 研究了质心算法思想、数学模型，讨论了该算法在节点定位精度上受节点密度、 连通性等因素的影响。 2 针对在质心算法思想的节点自定位技术中，坐标值估算与实际值之间存在较大误 差，提出了基于极大似然估计法的测距技术误差模型，讨论了将该算法模型用于计算节点 自定位的坐标误差值，最后，将该误差值用于对质心算法的定位坐标值进行修正。 3 在介绍遗传算法( g e n c t i c 灿9 0 r i t h m ，g a ) 的基础上，将遗传算法用于对极大似然估 计法测距的模型上，建立了遗传算法的仿真模型，设计了算法流程，得出了仿真结果。结 果表明：传感器节点的密度较大或连通性较好时，误差值较小。此外，迭代计算次数较多 时，误差值较小。 经过遗传算法优化过的基于极大似然估计法测距的改进模型，在节点坐标的误差值优 化方面，有着较好的结果。但是，由于遗传算法本身需较大的迭代计算，运算量较大，对 硬件要求较高，不太适合能量有限、计算能力有限的单个传感器节点，故该优化模型仅仅 适合于集中式定位方式。 关键词：无线传感器网络，节点自定位，质心算法，遗传算法，极大似然估计法 浙江工业大学硕士学位论文 、t h er e s e a r c ho ns e l f l o c a l i z a t i o no fn o d e i nw i r e l e s ss e n s o rn t e w o r kb a s e do n g e n e t i ca l g o r i t h m a b s t r a c t l ti s柚i n t e 麟娥i a lt e c h i q u e0 f m u l t i p l c轴b j e c t s s u c h舔 粥i n g ，m p u 痂g ， 0 0 m m u n i c a t i n 吕i n f o m a l i 伽p 眦e s s i n gt l l a tt l l et e c h n o l o g y0 fw i r c l e 豁s e n s o fn e 伯，m kh 勰 w i d ca p p l i 叫i i nb o t hm i l i t a r ) ，锄dc i v i la r c 孤n et e c h n o l o g yo fn o d e l f 1 0 c a l i z a t i 伽i s c n l c i a lb u tb a s i c0 n c0 fw i r c l c s ss e n s o rn e t 、v o r kt h a tt h cn o d cl o c a t i o ns h o u l db ek n o w 田f i i s t 锄咖g 肌m e r o u ss t u d y 伽a p p l i c a t i 伽 c c n 们i da l g o r i t l l l l ll o c a l i 盈t i 咖d e p c n d su p 佃c d 衄c x i t y0 fn e t w o r k 柚dn o d ed e n s i t y 粗d 龇e n o f0 fn o d e 嘶e n t a t i o ni sh i 曲t 0f i i i i t en o d ee 鹏r 鳜as i i i l p l e1 0 c a l 鼢l ca r i t h m e t i c0 f 玳妇ei si t sp r e p o n d e r a n c c 1 0k e e pt h ea d v 柚t a g c ，t l l i st h e s j sb r i n g sf o 研a r d 锄e l i o r a t e dm o d e l b a s c d 册0 0 m p u t i n gm o d e lo fm 觚i m u ml i l 【e l i l l 0 0 d 镐t i m a t i 伽柚d 册i s e sc c n t m i da 1 9 0 r i t h l n v a l u c0 f 伽d f d i n a t e s 柚dt l l e no p t i m i z e st h cm o d e lb 弱c d 伽c e n t r o i da 1 9 0 r i t l l m o r d i n a r ) r a f i t l l m e t i c 彻n o d e l f - l 斌i z a t i 佃i sc a p a b l eo fs a v i n g 如e r g yo fn o d ea n dp r o l 佃舀n gn a t u r a l l i f c0 f n e m 0 r k t h em a i nr e s e a r c hw o f ka n dr e s u l t sa r ea sf b l l o w s ： 1 t h i st o p i cs t u d i e sc c n t r o i da 1 9 0 r i t l l l ni d e a 柚dm a t h e m a t i 岱f 0 叻廿觚dd i 湖蹴st h c i l l f ：c c t i a b o u tt h ep r e c i s i o fn o d e 嘶e n t a t i b yn o d ed e n s i t y ，c o n n c c t e d n e 豁e t c 2 t h et c c l l i l o l o g y0 fn o d es e l f - l o c a l i z a t i o nb 弱e d0 nc c n t r o i da 1 9 0 r i t l l l nt a ：k e sm a x i m u m l i k e l i h 0 0 de s t i m a t i o nm o d e lw h i c hi st h ec o m m o nd i s t 锄o cm e 弱u r i n gi np r a d i c cb e c a u o ft h c e r r o fa m o n g p r a c t i c a lv a l u e 柚dc 0 m p u t i n go n e ，m 觚i m u ml i k e l i h 0 0 de s t i m a t i 彻m o d e li su d 衄c o m p u t e 血gt h ee 仃0 rv a l u eo fn o d el o c a t i o n ，n l ec 盯o r l e s sv a l u ei sm o d i f i e do nt h ci k 坩e s e l f 1 0 c a l i z a t i o nc 0 1 0 r d i l l a t e sv a l u ew h i c hb a s e d c e n t f o i da l g o r i t h mi d e a 3 1 t 叩t i m i z e st h ec o m p u t i n go nm a x i m u ml i k e l i h o o de s t i m a t i o nm e a s u 血gm o d e lb y g e n e t i ca l g o r i t l l n l 柚de s t a b l i s ht h ee m u l a t i o n a lf o 加e ra n dd e s i g n st h ea r i t l l i n a t i cn o w 柚da l s o e l i c i t se m u l a t i o n a lc o n c l u s i o no fg e n e t i ca l g o r i t h m t h eo u t c o m es h o w st h em o r cn o d ed e n s i t y 锄dc 0 n n e c t i v i t y ，t h el e s se 1 1 r o rf u r t h e 姗o r ci t e r a t i v et i m eb e t t e ra n dt h ee o rl e s s nh a sab e t t e rc o n c l u s i o nt h a tt h em a x i m u ml i k e l i h o o de s t i m a t i o nm e a s u r i n gm o d e l 0 p t i m i z e db yg e n e t i ca l g o r i t h mo no p t i r n z e i n go ft h ee l t 0 rv a l u e0 fn o d el o c a t i o n b u t ，g e n e t i c i i 浙江工业大学硕士学位论文 a l g o r i t l l mn e e dm u c hm o r ei l e r a t i v ec a l c i l l a t i i l g 锄dt ot h ef i n i t en o d e 锄e r g yi td o e 跚tf i t0 d d n o d eb e c a u s eo fe x a c th 钺1 w a r c ，t h eo p t i m 娩i n gm o d e lf i tc c n t r a l1 0 c a l i z a t i o n0 n l y k 对w b m s ：w i r e l e 豁s e n s o rn e t 、o 咄n o d c l f 1 0 l i z a t i o i l c c n t r o i da 1 9 0 r i t h m ，g e n e t i c a l 鲥t l l m ，m a 】【i l n u ml i k e l i l l o o de s t i m a t i o n 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名： 日期：砂瞬舾月如日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被杏阅和借阅。本 人授权浙江r 业大学可以将本学位论文的全部或部分内容编入有天数据库进行检 索，町以采影e f j 、缩e i j 或扫描等复制手段保存和? 厂编本学化论艾。， 奉学位沦文属于 1 、保密口，在年解密后适用本授杖f 0 。 2 、不保密口。 ( 请在以上相应方框内打“v ”) 作j 并咎z ： ! | j i f j 答z ： 日期：矽舒f 日期：印 ，djj 如| | j 】 l 浙江工业大学硕士学位论文 1 1 引言 第1 章绪论 “传感器网络是由大量自治的微型感知设备以a d h o c 等方式构建形成，并能够协同 地对某种物理现象进行感知的网络。一心面l a l 【2 】 无线传感器网络( w i r e l e 鼹s 蛐s n e 晰0 r l 【w s 综合了微电子技术、传感器技术、嵌 入式计算技术、分布式信息处理技术和无线通信技术等技术，能够协作地实时监测、感知 和采集网络分布区域内的各种环境或监测对象的信息( 如温度、湿度、噪声、光强度、压力 等信息) 。网络能够对这些数据进行处理，获得详尽准确的信息，把信息传送到需要的用户。 因特网( h t e m e t ) 已经改变了人与人之间交流、沟通的方式，并将继续持续的改变这种 交互方式。无线传感器网络是因特网从虚拟世界到现实世界的延伸，它将逻辑上的信息世 界与真实物理世界紧密的连接到一起，这必然会改变人与自然的交互方式【1 4 ，5 刀。 无线传感器网络被认为是2 1 世纪最重要的技术之一，它将会对人类未来的生活方式 产生巨大影响。麻省理工学院的技术评论杂志( ，r e c l l l l o l o g yr e v i e w ) 评出了对人类未来 生活产生深远影响的十大新兴技术，其中，无线传感器网络位于这十种新兴技术之首【9 1 0 】。 1 2 无线传感器网络发展历史及应用前景 1 2 1 发展历史 根据对无线传感器网络研究侧重点的不同，从2 0 世纪9 0 年代开始到现在，无线传感 器网络的发展历程划分为三个阶段。第一阶段属于起步研究阶段，主要致力于小型化、低 功耗、低成本的传感器节点的开发和研制，出现了众多的传感器节点。研究学者们主要研 究了来自美国军方和自然基金委的资助一些项目，如1 9 9 3 年开始的无线集成网络传感器 ( w i r e l e s sh l t e g 隐t e dn e 觚o r ks e n s o r s ，w i n s ) 项目1 8 1 ；1 9 9 8 年开始的大规模分布式军事传感 一1 一 浙江工业大学硕士学位论文 系统的无线专用网络的s e n s i t ( s e n s o rh l f 0 珊a t i o nt e c l l n o l o g y ) 项目1 3 】等等。第二阶段，则对 无线传感器网络作为通信网络的特性研究，特别是通信协议的设计和实现i 侧。这个阶段， 研究学者们设计提出了许多的通信协议，特别是数据链路层的m a c 协议和网络层的路由 协议。此时，除了美国各大高校和科研机构外，法国、英国、日本、意大利等其它各国的 一些大学和研究机构也纷纷开展了该领域的研究工作，2 0 0 0 年起，国际上开始出现有关无 线传感器网络研究结果的报道，2 0 0 3 年开始，有关无线传感器网络的国际会议和杂志大量 涌现。第三阶段，侧重于对无线传感器网络的群体智能行为的研究。目前，这方面的研究 相对较少，大量的问题还没有涉及到，可以说，未来的研究工作任重而道远m 。目前的研 究正处于第二、第三阶段。 中国国家自然科学基金于2 0 0 3 年开始对无线传感器网络方面的研究进行了资助，2 0 0 4 年将其列为重点项目，而2 0 0 5 年以来陆续有相关项目被列为重点项目。 1 2 2 应用前景 基于传感技术和无线联网技术的无线传感器网络，由于具有众多类型的传感器，故能 探测包括地震波、电磁波、压力、土壤成分、温度、湿度、噪声、光强度等周边环境中多 种多样的参数。故有着如下领域的应用： 1 军事领域对我军兵力部署、物资装备、重要军事地区等进行监控；对敌我冲突区、 敌方地形、敌方首脑区或临时指挥所等进行布防和侦察等； 2 航空领域使用传感器网络对外太空的星球表面进行长时间的监测，以了解其表面 水、土壤等成分，为进一步开发使用太空资源作准备； 3 救灾领域比如在易爆场所，部署一些对气体浓度具有敏感性的传感器节点，实施 监控，并把检测的数据传送给监控中心，一旦发现异常，立即采取措施；还可对已发生灾 难的区域进行通信支援，比如今年南方的雪灾，在电力设备受损，通信中断的情况，可及 时部署传感器网络，掌握现场情况，以便于指挥部能够全面掌握状况，发布及时的指令； 4 工业自动化领域对设备进行故障监测、诊断( 如对高炉内的温度、湿度进行监测) ， 恶劣的生产环境过程监控以及仓库管理( 如一些大超市使用的射频识别条型码) ； 5 其他领域包含了其他社会生活的许多方面，如商业应用，反恐监测系统，智能家 居系统，农业现代化进程中对植物生长的监测等。 无线传感器网络作为一种新的信息获取方式，在许多领域，它有着不可比拟的优势， 浙江工业大学硕士学位论文 可以预见，在未来传感器网络必将成为人们生活中不可或缺的一部分，这一趋势，也引起 了科技界和商业界的广泛关注【1 ，4 9 】。 1 3 无线传感器网络的一些关键技术 无线传感器网络是当今的研究热点技术之一，涉及了许多交叉学科，有很多关键技术 有待于深入研究。传感器节点本身就是一个微型的嵌入式系统，携带的硬件资源非常有限， 需要操作系统能够高效的使用其有限的内存模块，处理器模块和通信模块。w s n 具有两个 突出的特点：可能存在多个需要同时执行的逻辑控制；模块化程度高，操作系统能够让应 用程序方便的对硬件进行控制，应用程序中的各个部分能够进行重新组合。 1 网络协议 传感器节点携带的能量有限，因而节点的计算、存储、通信能力也有限，节点只能获 取局部网络的拓扑信息，故网络协议不能太复杂；由于节点失效、环境影响等，使得自建 网络不断发生变化，对网络协议提出了高的要求。 传感器网络协议负责使得各个独立的节点形成一个多跳的数据传输网络，网络层和数 据链路层协议是研究的重点。网络层的路由协议决定了监测信息的传输路径；数据链路层 的介质访问控制( m a i c ) 节点的通信过程和工作模式1 5 一。 传感器网络以数据为中心，每个节点没有全网统一的编址，选择路径根据感兴趣的数 据建立数据源到中心节点之间的转发路径。已有的路由协议，包括能量感知路由协议，定 向扩散和谣传路由协议，地理位置路由协议等。m a c 层协议，首要考虑节能和可扩展， 其次才是公平性、利用率和实用性等，如基于竞争的眦协议，基于分时复用的m a c 协议等【1 ，5 是9 】。 无线传感器网络是面向应用型的网络，针对应用的不同，网络协议需要根据应用的类 型或目标环境制定。目前，还没有任何一种网络协议能够适合所有的不同的应用环境。 2 网络拓扑技术 通过拓扑控制方式构建的网络，节省节点能量，提高路由协议和眦协议的效率， 延长网络生命期。拓扑控制研究在满足网络覆盖度和连通度前提下，通过控制功率和骨干 节点的选择，剔除多余的通信链路，生成一个高效的数据转发的网络。拓扑控制包括节点 功率控制和层次型拓扑结构。节点功率控制研究在满足连通度时，减少节点的发送功率； 层次型拓扑结构利用分簇机制，使部分节点成为簇头节点，构建成骨干网络。 浙江工业大学硕士学位论文 3 时间同步 时间同步是协同工作的传感器网络的一个关键机制，如测量移动物体速度时，需要计 算不同传感器检测事件时间差。目前，i n t 啪e t 使用的n r l l p 网络时间协议和g p s 使用的 u t c 同步机制，不适合微节点。在已提出的时间同步机制中，r b s 、，兀n y m i n l s y n c 和 1 r i s n 是三种基本的时间同步机制f 9 - 1 8 l 。 4 定位技术 确定事件发生的位置或采集数据的节点位置是传感器网络最基本的功能之一，可以 说，没有确切位置的监测消息毫无意义1 1 ，埘。随机部署的传感器节点必须能够在部署后， 及时确定自身的位置。然而，传感器节点受资源限制、部署影响、通信受环境影响，节点 失效等原因，定位机制必须满足自组织性、健壮性等技术要求【1 ，1 2 ，川。 5 无线通信技术 传感器网络需要低功耗、短距离的无线通信技术。超宽带技术具有对信道衰落不敏感、 发射信号功率谱密度低、系统复杂度低等优点，非常适合传感器网络。目前，有两种方案， 一种是d s c d m a 单频带方式，一种是o h ) m 方案，但还没有方案成为国际通用标准。 6 数据融合和管理 传感器网络存在能量约束，减少数据传输量能够节省能量，在节点数据收集过程中， 尽量用节点本地计算的能力处理数据。数据融合技术协议可与网络的多个层次协议结合， 如应用层可用分布式数据库；网络层与路由协议结合等。 无线传感器网络的数据库管理系统的结构主要有集中式、半分布式、分布式以及层次 式结构。它与传统的分布式数据库有很大区别：节点能量受到限制容易失效，数据库系统 尽量减少能量消耗；当节点数量庞大，传统的分布式数据库的管理技术则无法分析；对节 点的查询往往是随机的或者连续的查询。目前，大多数研究集中在半分布式结构方面。 7 其他相关技术 无线传感器网络作为任务型的网络，除了传输数据，还有数据采集、融合和任务的协 同控制【2 ，6 l 等。为保证任务的机密布置和任务执行的安全传递1 1 7 l 和融合，网络需要最基本的 安全机制：机密性、点到点的消息认证、完整性鉴别、新鲜性、认证广播和安全管理等。 无线传感器网络应用层由各种面向应用的软件构成，而部署的网络往往要执行多种任 务。应用层的研究主要针对各种传感器网络应用系统开发和多任务之间的协调。 浙江工业大学硕士学位论文 1 4 本文研究主要内容 无线传感网络最基本的功能之一是能够确定自身的位置进而确定事件、消息发生的位 置或采集数据的节点位置，可以说，不能确定具体位置的监测数据，只能是一堆无用的数 据，不能代表任何消息，因而显得毫无意义。 本论文研究了无线传感网络节点的自定位技术，主要内容包括如下： 1 研究无线传感网络节点的自定位算法中的已有的各种算法，讨论自定位算法性能评 价及自定位算法方式分类等； 2 按南加州大学的n 讥p a m ab u l u 鲫等人提出的质心算法思想，建立出其数学模型并 计算出质心算法模型下的质心坐标( 未知节点) 的数学表达式； 3 质心算法算法简单，但精度不高，为保留算法简单的优点( 算法简单能够节约节点 处理数据的时间和复杂度，从而计算能量) ，本文采用了极大似然估计方法计算节点的测距 误差，用该差值来修正原质心坐标； 4 极大似然估计测节点误差值受节点数、通信能力等影响，因而采用遗传算法进行叠 代计算，对极大似然估计中的节点误差值进一步优化； 5 分别对提出的算法改进模型进行仿真，并对相应的仿真结果进行分析和讨论。 在本学位论文中，第3 章的内容是根据作者已经录用( 被现代电子技术录用，将于 2 0 0 9 年8 月发表) 的一篇文章整理而成。 1 5 论文结构安排 无线传感器网络作为一种全新的信息获取方式和处理技术，具有广阔的应用前景。节 点自定位技术作为其支撑技术之一，对国内外学者提出了许多挑战，成为目前研究和讨论 的传感器网络关键技术的热点之一1 1 ，8 ，1 2 ，1 卯。 无线传感器网络节点自定位算法有多种，每一类定位算法都有其自身的特点和适用范 围，没有哪一种是绝对优越。在算法中，按计算方式可分为集中式算法或分布式算法；按 定位效果可分为绝对式算法和相对式算法；按定位手段可分为基于测距技术和非测距等。 本文共分5 章，论文的组织结构如下： 第1 章介绍了无线传感器网络的发展历史和应用前景以及网络协议与关键技术、节 点自定位技术研究状况。 浙江工业大学硕士学位论文 第2 章研究了已有无线传感器网络节点的节点间距离测量方法、定位计算方法以及 计算分类，讨论了现有的节点自定位算法，对自定位算法的算法性能和指标作了相应的分 析比较。 第3 章介绍了质心算法思想，结合两种已有改进模型，提出了基于极大似然估计法 测距的改进模型，研究了改进模型的算法思想，数学模型、算法流程，给出了改进模型的 仿真结果，并作了相应的分析。 第4 章在介绍遗传算法的基本原理及方法的基础上，建立了遗传算法优化的节点改 进方案的模型，设计了算子及适应度函数，设计遗传算法模型流程图，显示仿真结果，讨 论了节点的密度，节点之间的连通性以及算法的迭代次数对极大似然估计模型的平均误差 值的影响。 第5 章总结本文所作工作，并展望未来定位技术尚需要做的工作。 浙江工业大学硕士学位论文 2 1引言 第2 章无线传感器网络的节点自定位算法 无线传感器网络就是由大量微型传感器节点以a d h o c 方式组成的无线网络，随着微 电机系统( m i 啪e l e c t m m e c h 柚i s ms y s t e m ，m e m s ) 、无线通信技术和微电子技术等的快速 发展，使得具有数据采集、计算处理、无线通信能力的低成本、低功耗、微型传感器的研 制和生产得以成为现实。传感器网络是通过所部署的大量节点相互协作地感知、采集和处 理网络覆盖范围内的各种监测对象的信息，再通过无线方式传送到数据处理中心。因而， 传感器、感知对象和观察者构成了w s n 的三个要素。无线传感器网络作为一种全新的信 息获取方式，在军事、国防、环境监测、危险区域的远程控制等许多领域都具有广泛的应 用前景，但它的特殊性也给研究人员提出了大量具有挑战性的研究课题。 在w s n 的应用中，监测到事件之后，所关心的一个最重要问题就是该事件发生的具 体位置，如在大鸭岛生态环境监测实验中，需要知道采集的环境生态信息所对应的具体区 域位置；其他事件如森林火灾的现场位置，战场上敌方车辆运动的区域具体地点等；即传 感器节点首先必须知道自身的地理位置信息，这也是采取进一步措施和做出决策的基础。 研究节点自定位技术时，常常用到以下的一些基本术语1 1 4 1 8 】： 邻居节点( n e i g l l b o fn o d e s ) ：传感器节点通信半径内得所有其他节点； 跳数( h o pc o u n t ) ：两个节点之间的跳段总数： 跳段距离( h o pd i s t 锄c e ) ：两个节点之间间隔的各跳段距离之和； 基础设施( ( i n 仃弱t n i c t u r e ) ：协助节点得己知自身位置得固定设备，如卫星，基站等； 达到时间( t i m eo fa 埘v a l ，t o a ) ：信号从一个节点传播到另外一个节点所需要得时间； 达到时间差( t i m ed i 彘r e n c eo fa 玎i v a l ，t d o a ) ：两种不同传播速度的信号从节点传播 到另外一个节点所需要的时间之差； 接收信号强度指示( r c c e i v e ds i 印a ls t r e n 舀h i n d i c a t o r ，r s s d ：节点接收到的无线信号 的强度的大小，称为接收信号的强度指示； 浙江工业大学硕士学位论文 到达角度( 强酉e0 f a r r i v a l ，a o a ) ：节点接收到的信号相对于自身轴线的角度； 视线关系( 1 i 鹏0 fs i g l i t ，l o s ) ：两个节点之间没有障碍物，能够直接通信； 非视线关系( n o u n e o f - s i 曲t ，n i d s ，l 0 s ) ：两个节点之间有障碍物。 2 2 无线传感网络节点间的距离测量方法 在无线传感器网络节点自定位技术中，需要对节点之间的距离或方位进行测量，以便 于知道两节点间的估算距离。常用的节点间距离的测量方法有r s s i ，t o 八t d o a 和a o a 。 r s s l ( r e c c i v e ds i 炉a ls t r c n g l hh l d i c a t o r ) 1 3 1 j ：己知发射功率，在接收节点测量接收功率， 计算传播损耗，使用理论或经验传播模型将传播损耗转化为距离，该技术主要用r f 信号， r a d a r ，s p o t o n 等许多项引加，2 5 ，2 7 l 中使用了该技术。r s s l 的主要误差是环境影响所造成 的信号传播模型的建模复杂性：反射、多径传播、非视距、天线增益等，通常将其看作为 一种粗糙的测距技术，有可能产生5 0 的测距误差1 2 7 1 。 m 技术是通过测量信号的传播时间来测量距离。使用m 技术最基本的定位系统 是g p s ，该系统需要昂贵、高能耗的电子设备以及精确同步卫星时钟。由于无线传感器网 络节点硬件尺寸、价格和功耗限制，g p s 技术对无线传感器网络而言几乎是不可行的。 ，n ) o a 技术广泛应用在无线传感器网络的定位方案中，已有多种定位算法使用1 1 ) o a 实现测距【勰，2 9 捌。在节点上安装超声波收发器和r f 收发器，在发射端两种收发器同时发 射信号，利用声波与电磁波在空气中传播速度的巨大差异在接收端通过记录两种不同信号 的到达时间差异，己知信号传播速度，直接把时间转化为距离。该技术的测距精度较r s s i 耐3 ，可达到厘米级，但受限于超声波传播距离有限和n l o s 问题对超声波信号的传播影； 虽己有发现并减轻n l o s 影响的技术，都需要大量计算和通信开销，不适合低功耗的w s n 。 a o a 是一种估算邻居节点发送信号方向的技术，可以通过天线阵列或多个接收器结合 来实现，如m r r 的t 1 l e 例c k e tc o m p 弱s 等项目1 3 2 】中就利用多个接收器提出了基于a o i a 的 硬件解决方案。a o a 技术受外界环境影响，如噪声、n l o s 问题等；此外，a o a 需要额 外硬件，在硬件尺寸和功耗上限制了传感器节点的应用。 以上四种测距方法各有利弊，以r s s i 和t d o a 两种方法最为常用。 浙江工业大学硕士学位论文 2 3 无线传感器网络节点的定位方式分类及定位算法 2 3 1 节点的定位方式分类 无线传感器网络现有多种定位方式，按照不同的标准，有不同的定位形式： ( 1 ) 绝对定位与相对定位【1 9 l 绝对定位指一个标准的坐标位置( 如经纬度) ，可为网络提供唯一的命名空间( 如g p s 定 位系统) ，受节点移动性影响较小，有着广泛的应用领域。目前，大多数定位系统和定位算 法都可以实现绝对定位服务。 相对定位通常是以网络中部分节点作为参考，建立依赖于整个网络的相对坐标系统， 但不需要信标节点。典型的相对定位算法和系统有s 蹦l f - p o s i t i o n i n ga l 鲥t h m ) 【1 9 1 ， l p s ( h 锄p o s i t i o n i n gs y s t e m ) 阎，s p o t o 垌。 ( 2 ) 集中式计算与分布式计算【2 l l 按对基础设施的依赖程度，分为集中式和分布式定位方式。集中式定位是指把所需信 息传送到某个中心节点，并在该中心节点处进行计算的定位方式；分布式定位是指依赖节 点问的信息交换和协调，由节点自行计算的定位方式。集中式优点在于从全局角度统筹规 划，计算量和存储量要求没有限制，能够获得相对精确的位置估算；缺点在于与中心节点 较近的节点会因为通信开销大而过早地消耗完电能，导致整个网络信息中断，无法定位。 ( 3 ) 基于距离有关的定位算法和基于距离无关的定位算法【2 7 1 按定位中，是否需要测量节点的距离，把现有无线传感器网络自身定位算法分为两大 类r 卸g - b a d 和r 锄g 舶e ，即基于距离有关的定位算法和基于距离无关的定位算法。前者 通过测量节点间的距离或角度信息，常用三边测量法、三角测量法或最大似然估计法计算 节点位置；后者仅根据网络连通性等信息实现。 ( 4 ) 递增式和并发式 根据节点是否已知自身位置，把节点分为信标节点仳a c o nn o d e ) 和未知节点( u n l 【i l o w n n o d e ) 【1 ，1 2 嘲。根据节点定位的先后次序不同，算法分为：递增式( i n c r c m e n t a l ) 定位算法和并 发式汹n c l i 玎e n t ) 定位算法。递增式从信标节点开始，信标节点附近的未知节点首先开始， 依次向外延伸，各节点逐次进行定位；在并发式计算中，所有节点同时进行位置计算1 1 8 】。 浙江工业大学硕士学位论文 2 3 2 节点定位算法 实现任何一种节点定位算法时都必须考虑网络的基础设施、网络的连通性、节点密度、 信标节点密度、测距精度、通信开销和计算开销等因数，还要考虑不良节点和毁坏的节点 对定位算法的影响，保证定位算法的可靠性。 ( 1 ) 三边测量法和极大似然估计法 三边测量法( ，蹦l a t e m t i o n ) 1 1 6 1 在三维空间中，我们知道一个点到四个信标节点的距离，就可以确定该点的坐标。在 无线传感器网络中，坐标系大多是二维空间。因此，只要知道了一个节点到三个信标节点 的距离就可以完全确定节点的位置。 极大似然估计法( m a x i m u ml i k c l i h o o de s t i m a t i o n ) 【5 6 1 极大似然估计法是求估计的一种方法。无线传感器网络节点的硬件和能耗限制，通常 节点问测距误差较大，因此经常出现三边测量法中三个圆无法交于一点的情况，这时就需 要使用极大似然估计法，其基本原理就是寻找一个使测距距离与估算距离之间差异最小的 点，以该点的坐标作为未知节点的位置。 ( 2 ) 三角测量定位方法 三角测量定位方法【1 捌也称为信号到达角度( a o a ) 定位法或方位测量定位法，该方法是 通过未知节点接收器天线或天线阵列测出信标节点发射电波的入射角，从而构成一根从未 知节点到信标节点的径向连线，即方位线。在二维平面中，利用两个或更多信标节点的a o a 测量值，按照a o a 定位算法确定多条方位线的交点，即可计算出末知节点的估计位置。 ( 3 ) 质心算法 质心算法【2 3 】是南加州大学的n i m p 锄ab u l u s u 等提出的一种仅基于网络连通性的室外 定位算法，该算法的核心思想是：信标节点每隔一段时间，向邻居节点广播一个信标信号， 信号中包含自身i d 和位置信息。当未知节点接收到来自不同信标节点的信标信号数量超 过某一个预设门限或接收一定时间后，该节点就确定自身位置为这些信标节点所组成的多 边形的质心。试验表明，大约有9 0 未知节点定位精度低于信标节点间距的1 3 。 ( 4 ) s p a ( s e l f - p o s i t i o n i n g 砧g o r i t h m ) 的相对定位算法 s p a 的相对定位算法：它选择网络中密度最大处的一组节点作为建立网络全局坐标系 统的参考点( 1 0 c a t i o nr c f e r e l l c eg r o u p ) ，并在其中选择连通度最大的一个节点作为坐标系统的 原点【5 ，1 8 】。首先根据节点间的测距结果在各个节点建立局部坐标系统，通过节点间的信息 交换与协调，以参考点为基准通过坐标变换( 旋转、平移、翻转) 建立全局坐标系统。 1 0 浙江工业大学硕士学位论文 ( 5 ) 凸规划定位算法 加州大学伯克利分校的d o h e r t y 等将节点间点到点的通信连接视为节点位置的几何约 束，把网络模型化为一个凸集，将节点定位问题转化为凸约束优化问题，使用半定规划和 线性规划得到一个全局优化的方案，确定节点位置瞄2 5 l 。根据节点间的通信连接和节点无 线通信射程，估算节点可能存在的区域，以矩形的质心作为未知节点的位置。 凸规划是一种集中式定位算法，定位误差约等于节点的无线射程。为了高效工作，信 标节点需要被部署在网络的边缘。 ( 6 ) a p s ( a d - h o cp o s i t i o n i n gs y s t e m ) a p s 【1 3 7 1 引，是美国路特葛斯大学的d r a 9 0 sn i 伽l e s c i i 教授等利用距离矢量( d v - d i s t 柚 v e c t o r ) 路由和g p s 定位的思想提出的一系列分布式定位算法的合称。包括d v - h o p ， d v 二d i s t 柚，d v - c 柑i n a t c 等一系列算法。d v 二h o p 是该算法的基础，由三个阶段组成。 首先使网络中所有节点获得距信标节点跳数；在获得其他信标节点位置和相隔跳距之后，信 标节点计算网络平均每跳距离，将其作为校正值( c ( 撇t i 彻) 广播至网络中，如下式所示： q 犁 ( 2 - 1 ) 其中，矢量厶、，为信标节点坐标，为厶到l ，的跳数。接受校正值后，未知节点 选择最适合的一个；然后按跳数计算与信标节点之间的距离；当未知节点获取与三个以上 时，用三边测量计算出节点坐标。如图2 2 ，已知信标节点厶、厶与厶之间的距离和跳数。 图2 1 d v 二h o p 、k 、匕所计算得到校正值分别为： 屡二：篡：y ，譬：) 二：? ( 2 2 ) c ：- ( 4 5 + 跖) ( 2 + 5 ) - 1 8 彻 卜卅 l c j 一( 8 6 + 1 1 2 ) ( 5 + 6 ) - 1 跏 。 按照就近原则，未知节点a 从乞获得校正值c 2 ，则它与3 个信标节点之间的距离分 浙江工业大学硕士学位论文 别为：墨一3 c 2 ；是一2 c 2 ；s c 2 。然后使用三边测量法确定节点a 的位置。 f 7 ) a m o 印h o u s 定位算法 a m o 叩h 伽s 定位算法【1 2 ，1 7 ，1 8 】同d l 、，h 0 p 类似，也分为三个阶段：计算信标节点与未知 节点的最小跳数；未知节点计算到每个信标节点的距离：计算未知节点的位置。a m o r p h o 璐 将通信半径作为每跳的距离，误差较大。 对算法从两个方面进行的改进：重新计算平均每跳距离，采用下式计算平均每段距离； 利用局部跳数平均值代替跳数，用下面的式子对跳数进行改进。 ( 8 ) c 0 0 p e r a t i v e 姗舀n g 算法和t w o p h a p i t i o n i n g 算法1 1 3 1 5 】 这两个算法是利用循环求精提高定位精度的算法，都分为启始和循环求精两个阶段。 启始阶段着重于获得节点位置的粗略估算；循环求精阶段，每一次循环开始时每个节点向 其邻居节点广播它的位置估算，并根据从邻居节点接收的位置信息和节点间测距结果，重 新执行三边测量，计算自身位置，直至位置更新的变化可接受时循环停止。 ( 9 ) a h l o s ( a d 1 1 0 cl o c a l i z a t i s y s t e m ) 和n - h o pm u l t i l a t e r a t i 加皿m i t i v c 定位算法【2 2 矧 这是由u c l a ( u n i v e r s i t y0 fc a l i f o m i a ，i 腮a n g c l e s ) 在t d o a 测距的平台上提出的两 个算法，其中后者是前者的改进。这两种算法的提出了一种思维模式，即把已定位的未知 节点升级为信标节点，并进行继续迭代定位。 ( 1 0 ) g 蛐c f i ci j d l i z e d g 嘶t h m s 算法 ( 奴哩地m t i v em 百n g 算法使用循环求精来降低测距误差影响，a h l o s 算法利用将已定 位的未知节点升级为信标节点来解决信标节点稀疏问题。在此基础上，u c l a 的s c a p a l l l l m e g i l e r d i c h i 柚l 等人提出了通用型定位算法( g e n e r i cl o c a l i z e da l g o r i t h m ) i ”列，它的特点在 于，详细指定了未知节点位置估算并升级为信标节点的条件，以减少误差累计的影响。 ( 1 1 ) e c o b 跏i o n 算法 e c o l o c a t i 咖算法是一种基于测量无线电信号和距离进行转化的描述方式，并且在这种 描述方式上提出了自己的一种算法【2 1 ，2 4 】。该算法是利用信标节点与未知节点之间的距离， 得到它们之间r s s 值，并且将它们存储在节点的存储器中，再通过这些值构成各个节点的 约束矩阵，然后找出最大约束匹配矩阵，通过最大约束匹配矩阵得出未知节点的位置坐标。 ( 1 2 ) a p i t 定位算法 弗吉尼亚大学的面柚h e 等提出的a p l 一1 7 ，1 8 】也是一种通过求解约束集合以实现定位的 方法。定位过程为：每个未知节点进行数据收集；从与之通信的信标节点中选择3 个节点， 运用p i t 测试判断它是在这3 个信标节点所组成的三角形内部还是在其外部；未知节点将 浙江工业大学硕士学位论文 包含自己的所有三角形的相交区域( 图中阴影区域) 的质心作为自己的估计位置( 如图2 3 ) 。 图2 2a p l l r 定位原理 a p 盯测试是通过与信标节点交换信息，模拟节点的运动来实现的。如下图所示，信标 节点构成了a b c ，完备p r r 测试原理( p e m ：c tp r r t c s t1 n b c 0 呦的两条原则如下： 待测试节点m 向任何一个方向移动，都会使其靠近其中至少一个信标节点，那么节 点m 处于a b c 内部，；如果存在一个方向待测试节点m 向该方向移动，使其同时靠 近或远离三个信标节点，那么节点m 处于a b c 外部。 ( 1 3 ) 恒模算法( c m a ) 恒模算法作为信号处理领域的热点问题之一，主要应用于盲均衡、多用户检测、盲信 干扰抑制和波束形成等领域。复旦大学的一些学者【2 4 1 首次将其应用于w s n 节点自定位， 提出了基于恒模算法的新定位方法c m a m a p 以及它的一种增强型算法( c m a m d s ) 。 从定位算法理论研究到具体实现并不是一跋而就的，对节点定位算法从理论到实现过 程中的细节进行反复研究，并最终在实体环境中进行测试。 2 4 无线传感器网络定位算法性能评价指标 特别的特性使得无线传感器网络的定位算法必须需要具备一些特点：自组织性即节点 随机部署，不依赖全局基础设施；健壮性即指在节点硬