（计算机应用技术专业论文）无线传感器网络节点定位技术研究.pdf

嚷 爹 ， 毡 彰 陲 彰 蓼 i 蕴 鹱 黍 薹 扩 独创性声明 | i l l l l l | | l 舢l | | l l 刚l l l i i 咖 ! y 18 2 4 8 2 7 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得重废整电态堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名专辱 签字醐：1 铂鼽日 学位论文版权使用授权书 本学位论文作者完全了解重废邮电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权重麽邮电太堂可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：茏咤 昏 导师签名：幸影2 签字醐：砷私胁日签字日翌。1 年_ 月瑚 心 po孝拳鬻p笃纂麓擎蛾藉赣赫嚣脚镶一0中-蓥=气o，删嚏缳 _。vt誊，罐 重庆邮电大学硕士论文摘要 摘要 无线传感器网络集嵌入式技术、传感器技术、微机电技术、无线通信技术和分 布式信息处理技术于一体，是一种全新的信息获取和处理模式。网络布局和覆盖、 节点自身定位、网络通信协议是无线传感器网络研究中的几个基本问题。其中，节 点定位问题是无线传感器网络进行目标识别、监控和跟踪等众多应用的前提，也是 无线传感器网络研究中的热点问题之一。 本文就无线传感器网络的节点定位技术展开深入探讨。节点定位技术的基本途 径是在传感区域中部署少量已知坐标的锚节点，其他未知坐标的节点通过测量与锚 节点间的距离、角度，或者依据相对位置关系、网络连通性进行一定的计算得出自 身的坐标。 d v h 0 p ( d i s t 锄c ev c c t o r _ h o p ) 是典型的无需测距的多跳定位算法，本文讨论 了该算法的适用环境和产生误差的各种因素，并对其进行了仿真实现。仿真实验结 果表明：d v - h 0 p 适用于节点分布各向同性的网络结构，其定位精度依赖于节点在 网络中的布局情况，单纯地增加锚节点比例对定位精度的提高有限；由于采用多跳 的方式传播锚节点信息，未知节点的定位覆盖率较高。 针对d v - h 0 p 定位算法的局限性，本文引入虚拟力导向的节点移动方式，将未 知节点获得的锚节点信息个数作为计算节点受力的参数，以优化网络布局的方式改 进了定位过程中平均每跳距离的精确度，提高了节点定位精度，并能够保证良好的 网络覆盖率。仿真实验结果表明，改进后的算法在三种不同的应用环境无障碍 物存在、仅锚节点移动和存在障碍物的传感区域中，均具有较高的定位精度。 关键词：无线传感器网络，节点定位，d v - h 0 p 定位算法，虚拟力 冰扎，毒舭一峨h”学w越霄黛，葛。名礴m谚，碱秘哆一o嚏：麓-蕾。誊?。_t节尊_、： 舟，o，0案，一曲。，i蔓霪：姑 霉 秀 i l 重庆邮电大学硕士论文 a b s t r a c t a b s tr a c t w i l e l e s s n s o r 玳婀v o f k ，an e wp a t t e mo fi n f o n l l a t i o ng a m e r i n g 舭dp r o c e s s i i i 舀 w l l i c hi i l t e g r a t e st e c t l i l o l o 西e so fe m b e d i d c dc o m p u t i n 舀s e i l s i n g ，w i r e l e s sc o m m u i l i c a t i o i l m i c 一e l e c t m m e c h a i l i s m 觚dd i s t r i b u t e di 1 1 f 0 i n n a t i o np c e s s i i l g t h e 血嘲锄e m 融 p r o b l 伽【l so fw i i _ e l e s ss e i l s o r 饿帆o r k sa r ed e p l l e ma n dc o v e r a g e ，1 0 c a l i z a l i o 坞觚d m 婀r ! i 趣p r o t o c o l s l 0 c a l i z a t i o i l ，w 量l i c hf b c u s e d 硒ab 嬲i cp r o b l e l n ，i st l l ep r e c o n m t i o n o fm 锄ya p p l i c a t i o i l so fw i r e l e 蹒n s o r 玳= t 、矾 r l 【s ，s u c h 弱t a 唱e ti d e m i f i c a t i o i l s 眦v e i n a n c e 锄dt r a c l d n g ， 1 ks e l f l o c a l i z a t i o nt i e c h n o l o 科i sd i s c u s s e di n 吐l i st l l e s i s 1 kb 嬲i ca p p m a c ho f s e l f l o c a l i z a t i o ni su s i n gb e a c o i l s l a ta w 蜀啪o fm e i rp 0 s i t i o i l s 鹊r e f 咖c e ，觚d 凼w l n o d e sc o n l p u ：t em e i rp o s i t i o i l st h 彻l 曲n 伧r e l a t i o n 幽po fd i s 眦e ，a n g e l ，o rn 娟o r k c 0 衄e c t i v i 锣t o t l l eb e a c o 璐 。 d v m o p ( d i s t 锄c ev e c t o n l o p ) i sac l a s s i c a l 捌1 j 薛- 舶el o c a l i 删o na l g o r i t h mb 嬲e d o nm m - h o p s h lt l l i st l l e s i s ，t l l ep r o p e rs i n 埘o no fl l s i l l gm em g o r i m m 锄dm ef a c t o ro f l o c a l i z a t i o n 锄rb e e nd i s c u s s e d ，a n d 吐圮s i i i l u l 撕0 no fd v h o pi si i n p l e m e i l ：t e d 1 k s i r 硼l a t i l d n 蕾e 砌t ss h o w 也砒d v h 0 pw o d 娼丘n e 诵t 1 1 趾i 咖i cn 确釉r k 、 ，i m o l i t o b s t a c l e s t h e1 0 c a l i 刎0 n 阳i s i 0 i ld e p e n d so nn l ed 印l o y z i l 锄to fn o d e s t h ep f e c i s i 0 豇 缸噼0 v 删i sl 酬b yi n c r e 嬲i n gp e r c e n t a g eo fb e a c 6 璐 砧i i l i n ga t 圮e x i s t i n gp f o b l e n l so fd v h 0 p ，n l i s 圮s i s 硫r o d u c e dav i r t l j a lf o r c e l e a d i i 培m 砸o no fs l e n s o rn o d e si i l ：t 0 l o c a t i o np r o c e s s b yu s i n gm e 删m t ) e ro fm e s s a g e t l l 越l l r l k n o w nn o d eo t ，t a i l l e df h nb e 觚o n s 鹪t h ep a r 缸n c 屯c ro ff o r c ec 0 哪p u t i i l g ，m e a l 鲥m mc 觚i m p r o v em el o c a l i z a l i o na c 删a n d 妇n e r l 【c o v e 瑚l g e s i i l l u 蜥 r e s u l t sg h o w l a ln l ep r o p o s e da l g o r m l mh 嬲g o o da c c u r a c yi i l 铭c ha p p l i c a t i o n 疵i l i i l e n t s ：n oo b s t a c l e s ，b e a 0 0 ni n o v c0 1 1 l yo r0 b s t a c l e s 耐s t c 眦n e 呲 k e yw o r d s ：w n l e 路s e l l s o rn e t 、0 d 嗡s e l f k a l i z a t i o 玛d v h 叩l 0 c a l i z a ：c i o n 灿9 0 r i n l i n ，v i r t i l a lf c e i i 矿喜。靠。_一。1蟑。动“詹垮秘，盘繁一鞘融汹泌酝龄秽黪协菘。焉鹰萋鼍；，；o，。蔫；摹0_；墨雾；毒 第一章绪论l 1 1 研究背景1 1 2 无线传感网络概述2 1 3 节点定位技术及其研究现状3 1 4 论文主要工作6 1 5 论文组织结构7 第二章节点定位技术基础8 2 1 节点间距离测量方法8 2 2 节点坐标的估算方法1 0 2 2 1 三角测量法1 0 2 2 2 三边测量法1 0 2 2 3 极大似然估计法1 1 2 2 4m j n - m 觚法1 5 2 3 节点定位算法的分类1 5 2 4 节点定位算法的性能指标1 8 2 5 本章小结1 9 第三章无需测距的多跳定位机制研究“2 0 3 1 引言2 0 3 2d v 二h 0 p 定位算法2 0 3 2 1 距离矢量交换阶段”2 1 3 2 2 校正值计算与广播阶段“2 2 3 2 3 节点坐标估算阶段“2 3 3 3 算法仿真实现”2 3 3 4 相关讨论分析2 5 3 4 1 对网络布局的依赖2 5 3 4 2 不良节点问题2 6 3 4 3 障碍物的影响”2 6 i i i 鼍r。搴。一鼍， 重庆邮电大学硕士论文 目录 3 5 本章小结”2 7 第四章基于虚拟力的无线传感器网络多跳定位算法2 9 4 1 引言2 9 4 2 网络模型定义2 9 4 3 虚拟力导向的节点移动方式3 0 4 3 1 未知节点对锚节点的排斥力3 1 4 3 2 同类节点问的排斥力3 1 4 3 3 传感区域边缘对节点的排斥力3 1 4 3 4 障碍物对节点的排斥力3 2 4 3 5 节点所受合力计算3 2 4 4 基于虚拟力的无线传感器网络多跳定位算法3 3 4 5 仿真实验与分析3 4 4 5 1 无障碍物传感区域中的仿真实验3 5 4 5 2 仅锚节点移动的仿真实验3 7 4 5 3 存在障碍物传感区域中的仿真实验。3 9 4 6 本章小结4 0 第五章总结及未来工作4 1 5 1 总结4 1 5 2 未来工作展望4 l 致谢4 3 攻硕期间从事的科研工作及取得的研究成果“4 4 参考文献”4 5 i v 重庆邮电大学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 无线传感器网络( w h l e s ss e 璐o rn e t w o r k ，w s n ) 是传感器技术、片上系统 ( s y s t e i i lo i lac h i p ，s o c ) 、微机电技术( m m e l e c 仃d - m e c h a i l i s i i ls y s t e i n ，m e m s ) 、 无线通信技术和分布式计算技术的高度集成，是一种全新的信息获取和处理模式【l 】。 通过将大量的成本低廉的，具有感知能力、无线通讯能力以及一定计算能力的传感 器节点以无线、多跳的方式自组织成网络，无线传感器网络能够协作地实时监测、 感知和采集传感器节点分布区域内的各种环境或监测对象的信息，并对这些信息进 行处理，获得详尽而准确的信息，最终传送到需要这些信息的用户。 无线传感器网络可以使人们在任何时间、地点和任何环境条件下获取大量详实 而可靠的信息。其应用领域包括：国防军事、环境监测、交通管理、抗灾救灾、智 能家居、医疗卫生等。无线传感器网络是信息感知和采集的一场革命，正如因特网 使得计算机能够访问各种数字信息而可以不管其保存在什么地方，无线传感器网络 能够扩展人们与现实世界进行远程交互的能力，它在未来的更多应用将超出我们的 想象力【。 ， 美国橡树岭实验室曾断言，时代正在从“c 0 m p u t e ri sm ei l e t 、0 r k ”向“s e n s o ri s m en 舐0 r k ，转变；2 0 0 3 年2 月，美国技术评论提出无线传感网络技术将是未来 改变人们生活的十大技术之首；同年8 月，美国商业周刊的技术评论中将无线 传感器网络定位成人类未来四大高新技术产业之一。著名的福布斯杂志曾评论 说：“未来的传感器网络将比现有的i n t 锄c t 大得多”。 我国现代意义的无线传感器网络及其应用研究几乎与发达国家同步。首次正式 出现于1 9 9 9 年中科院知识创新工程试点领域方向研究的“信息与自动化领域研 究报告”中，作为该领域的提出的五个重大项目之一。2 0 0 5 年，“传感器网络系统的 基础软件及数据管理关键技术的研究”已被列为国家自然科学基金委员会信息科学 部与微软亚洲研究院正式签署的第二期联合资助项目之一；2 0 0 6 年，国务院在国 家中长期科学与技术发展规划( 2 0 0 6 屯0 2 0 年) 中的重大专项、优先发展主题、前 沿技术中均将无线传感器网络这一研究领域列入其中，在重大专项“新一代宽带移动 无线通信网”中更是将其列为重要方向之一。 重庆邮电大学硕士论文 第一章绪论 1 2 无线传感网络概述 无线传感器网络系统结构的一般形式如图1 1 所示【2 1 。节点随机部署在被监测 区域内，除了监测特定的对象，还进行简单的计算并维持互相之间的网络连接。无 线传感器网络具有自组织的功能，各节点间通过初始的通信和协商，形成一个传输 信息的多跳网络。每个无线传感器网络装备有一个连接到传输网络的网关，传输网 络是由一个单跳链接或一系列的无线网络节点组成的。网关通过这个传输网络把监 测数据从传感区域发送到提供远程连接和数据处理的基站，基站通过i n t e m e t 连接 到远程数据库。最后，采集到的数据经过分析、挖掘后通过一个界面提供给终端用 户。 图1 1 无线传感器网络的系统结构 简单的讲，无线传感器网络就是由大量的能与物理环境进行交互，同时具有数 据处理功能和无线通信功能的新型传感器节点构成的互连的系统，该系统可以完成 复杂的监控任务。这里的传感器节点，并不是传统意义上的单纯的对物理信号进行 感知并转化为数字信号的传感器，它是将感应模块，数据处理模块和无线通信模块 集成在了一块很小的物理单元上，功能比传统的传感器大了许多，不仅能够对环境 信息进行感知，而且具有数据处理及无线通信的功能。 图1 2 所示为传感器节点的硬件结构原理图【4 】。其中，传感器负责监测区域内 信息的采集和数据转换；处理器模块负责d 转换，控制整个传感器节点的操作， 存储和处理本身采集的数据以及其它节点发送来的数据；无线通信模块负责与其它 传感器节点进行通信，交换控制信息和收发采集数据；能量供应模块为传感器节点 提供运行所需的能量，通常采用微型电池。 2 重庆邮电大学硕士论文 第一章绪论 图1 2 传感器节点硬件原理图 将大量的这类传感器节点高密度的分散在需要监测的某个场景环境里，通过无 线通信进行自组织，从整体上构成了一种特殊的网络。每个节点都有自己控制的一 个区域，通过感知设备，如声学光学设备，化学分析装置，电磁感应装置等，来监 测热、红外、声纳、雷达和地震波信号，从而探测包括温度、湿度、噪声、光强度、 压力、化学成分、移动物体的大小、速度和方向等众多部署者感兴趣的物质现象。 作为一种新兴的网络形态，同时又是传感技术、通信技术、微机电技术、嵌入 式技术、分布式计算技术等多学科交叉的领域，无线传感器网络一经提出便引起了 多方面的关注，这也意味着有众多关键技术有待研列2 1 ，其主要研究领域包括：无 线传感器网络路由协议、网络拓扑控制、节点定位技术、时间同步、节点数据融合、 嵌入式操作系统，等等。 1 3 节点定位技术及其研究现状 在无线传感器网络中，位置信息对传感器网络的监测活动至关重要，事件发生 的位置或获取信息的节点位置是传感器节点监测消息中所必须包含的重要信息，不 包含位置信息的监测消息往往毫无意义【6 】。传感器网络必须提供定位服务，使节点 能够明确自身的位置，才能详细说明“在什么位置发生了什么事件【7 】。因此，确定 事件发生的位置或确定获取消息的节点位置是传感器网络最基本的功能之一，对传 感器网络应用的有效性起着关键性的作用。因而，定位技术是无线传感器网络应用 必不可少的支撑技术。 无线传感器网络中的定位服务包含两个部分【8 】：节点自身定位与外部目标跟踪， 前者是后者的基础，本文着重研究节点自身定位。图1 3 说明了定位服务在传感器 重庆邮电大学硕士论文 第一章绪论 网络体系结构中所处的重要位置。 图1 3 定位服务在传感器网络体系结构中的位置 簦 嚣 络 特 定 雾 无线传感器网络的绝大多数应用都与位置信息密切相关，对于这些应用来说， 位置信息是系统完成任务的目标或是必要手段。特别是军事应用中，监控我军兵力、 装备和物资，监视冲突区，侦查敌方地形和布防等任务都离不开定位服务。同样， 对外部目标的定位和追踪、救护队如何走才能安全快速的完成救助任务、对交通状 况的监测控制等也都需要得到定位服务的支持。另外，定位服务还能为系统的其他 服务提供支持。例如，无线传感器网络的地理路由协议是以位置信息为基础的，不 需要大量地维护路由表，提高了路由效率【9 】【1 0 】；定位服务还可以为网络提供命名空 间【1 1 1 3 1 ，向部署者报告网络的覆盖质量【1 4 】【1 5 1 ，实现网络负载均衡以及网络拓扑的自 配置【1 6 。1 8 1 。 无线传感器网络通常需要在无人干预的情况下，大规模地随机部署在环境较为 恶劣、人类无法或不宜接近的区域，如战场、灾害现场等。因此，在部署时确定节 点位置是不现实的，如果在每个节点上都装备g p s 定位装置，其昂贵的造价将不符 合传感器网络节点廉价且需大量部署的特点【2 1 。因此，必须针对节点的计算、存储 和通信能力都十分有限的特点设计有效的低功耗的定位算法。 事实上，研究者们一直致力于这一领域的研究，已有许多系统和算法能够解决 无线传感器网络自身定位问题【1 9 4 。它们的基本思路大致相同：在无线传感器网络 中部署一定比例的特殊节点，这类节点拥有足够的能源并可通过g p s 或其它方式获 取自身坐标，称为锚节点( 觚h o r ) 或信标节点( b e a c o n ) ；需要进行定位的节点称 为未知节点( i n 蛔0 v mn o d e ) ，通过直接测量与锚节点的距离、角度，或者依据相 4 通信协议栈 重庆邮电大学硕士论文 第一章绪论 对位置关系、网络连通性进行一定的计算得出自身的坐标。通常一个节点定位算法 包括距离或方位角测量、坐标计算两个基本阶段。其中，距离或方位角可以通过直 接测量的方式得到，也可以根据网络的连通性间接计算得到。不同的定位系统和算 法都用来解决不同的问题或支持不同的应用，它们在用于定位的物理现象、网络组 成、能量需求、基础设施和复杂性等方面均有所区别。 从1 9 9 2 年a t & tl a b o r a t o r i e sc 嬲姗d g e 开发出室内定位系统6 i v eb a d g e 【加j 【2 1 j 至今，研究者们一直致力于这一领域的研究。 加州大学伯克利分校的d o h e r t ) r 等人【1 0 】【2 2 j 将节点间点到点的通信连接视为节点 位置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸约 束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，称 为凸规划定位算法。 美国路特葛斯大学的d r a 9 0 sn i c u l c s c u 等人利用距离矢量路由( d i s t a n c ev 龇r r 0 u 缸g ) 和g p s 定位的原理提出了一系列分布式定位算法，合称为a p s 【2 3 1 【2 4 】【3 1 1 。 它包括6 种定位算法：d v - h 0 p ，d v - d i s t a n c e ，e u c l i d e 肌，d v - c o o r 曲1 a t e ，d v - b e 疵g 和d v - r a d i a l 。 i d l l i l 【an a g p a l 等人在文献【5 】中根据完美三角形内点测试理论( p 酬融 p o 缸h 卜t r i 趾g i l i a t i o nt e s tn e 0 p i t ) 设计提出了近似三角形内点测试法( a i 删 m a t ep o 硫h t r i a n 鲥a t i o nt c 瓯a p r r ) 。一个未知节点任选三个邻居锚节点，测试自 己是否在它们所组成的三角形中，使用不同锚节点组合重复测试直到穷尽所有组合 或达到所需定位精度。最后计算出包含目标节点的所有三角形的交集质心，并以这 一点作为未知节点的位置估计。 加州大学伯克利分校的c h r i ss a v a r e 等人从减小测距误差对定位的影响出发， 提出了两种循环求精定位算法c 0 0 p c r 撕v er 加g i l l 9 7 】和n - p l l a s ep o s i t i o l l i i l 誊2 6 1 ，通 过多次迭代求精，算法最后能够收敛到节点的真实位置。 近年来，随着对无线传感器网络研究的深入，研究者们结合图论，机器人等各 学科的研究结果，提出了各种适用范围更广的节点定位算法。 k e z h o n g “u 等人【2 7 】在图论的基础上提出了定位协作体( l o c a h z a b l e c o l l a b o r a t i v cb o d 弘l c b ) 的概念，通过节点信息的多跳传播来协助定位未知节点， 克服了需要三个邻居锚节点才能定位的苛刻条件。算法首先将网络构造成一棵 b n _ t r ，然后将b n t r e e 分解成不同的定位协作体，进而达到定位的目的。 文献 2 8 中将a p r r 定位算法从二维空间扩展到了三维空间，提出了一种基于球 壳交集的三维定位算法a p i s 。以锚节点为球心，分别以其到邻居锚节点之间的距离 为半径画球，把整个空间划分为大大小小的同心球体。未知节点通过判断自己是否 在这些同心球体区域内，最终找到包含自己的最薄的一层球壳”，并以不同的锚节 重庆邮电大学硕士论文 第一章绪论 点作球心找到一系列这样的“球党，将这些球壳的交集作为待定位节点最可能存在 的区域，取该区域的重心作为这个未知节点的位置估计。 m i l l a i ll s i c l l 弛等人【2 9 】从减少锚节点成本开销的角度出发，提出了对l ( 姗i o 如q u 姐c yb 硒e dl o c a l i z 撕0 n ) 定位算法，仅使用一个移动的锚节点辅助定 位，移动锚节点可由机器人或其它方式驱动，走遍整个传感区域，不断广播自己的 位置信息，未知节点利用r s s i 测距技术，测得收到的每个位置信号到自己的距离， 再用贝叶斯公式求得自身的位置估计。 r f l 定位算法是较早地考虑到无线传感器网络的动态特性，并将移动锚节点运 用到无线传感器网络节点位置估计的节点定位机制之一，它能够适用于任意未知节 点密度的传感器网络。但是，该算法并未考虑移动锚节点的能量限制以及节点移动 的路径选择等问题，使得其在实际应用中具有较大局限性。然而这种思想为传感器 网络节点定位算法的研究打开了一条新的思路。 k y 吼出丽耻n 等人【划受到i 疆l 定位算法思路的启发，提出了具有一定移动策 略的移动锚节点辅助定位算法m b a l ( m 0 b i l eb e a 0 0 n 缸s i s t a n c el 0 c a h z 撕o n ) 。首先， 移动锚节点在传感区域中进行一次三角规则移动，在移动锚节点覆盖区域中的待定 位节点首先完成定位。随后，这些节点充当锚节点，发送自己的位置信息，辅助其 它未知节点完成定位。仍未完成位置估计的节点会发送附加需求信息给移动锚节点， 从而决定移动锚节点的移动路径，最终完成所有节点的定位。 1 4 论文主要工作 无线传感器网络是一种新的信息获取和处理技术，在特殊领域，它有着传统技 术不可比拟的优势，同时也必将开辟出不少新颖而有价值的商业应用。作为重要的 共性支撑技术之一，无线传感器网络节点定位问题极具研究价值。 本文主要工作包括： 1 ) 归纳和总结了已有的无线传感器网络节点定位算法的研究工作，深入分析了 无需测距的节点定位机制，对其中典型的多跳定位算法d v h o p ，进行了仿真实现， 并从其对网络布局的依赖、不良节点和障碍物对定位精度的影响三个方面提出改进 和提高。 2 ) 通过引入虚拟力导向的节点移动方式，改进了基于多跳的w s n 节点多跳定 位算法d v h 0 p 。仿真实验表明，改进后的算法在三种不同的应用环境无障碍 物存在、仅锚节点移动和存在障碍物的传感区域中均具有较高的定位精度。 3 ) 设计实现了通用性较强的仿真程序，能够针对上述三种应用环境设置不同的 6 重庆邮电大学硕士论文 第一章绪论 参数，从而对新提出的算法进行分析和比较。 1 5 论文组织结构 论文的组织结构如下： 第一章主要介绍了本文的研究背景，概述了无线传感器网络及节点定位技术， 以及节点定位技术的研究现状； 第二章主要介绍了无线传感器网络节点定位的理论基础，节点定位算法的不同 分类方式，以及评价节点定位算法的各项性能指标； 第三章详细阐述了d v 二h 0 p 定位算法各阶段的理论流程，并对其进行了仿真实 现，最后对影响该算法的定位精度的各项因素进行了深入地分析； 第四章利用d 呦定位算法定位覆盖率较高的特点，引入虚拟力导向的节点移 动方式，提出基于虚拟力的w s n 节点多跳定位算法，并分别针对三种不同的应用环 境一无障碍物存在、仅锚节点移动和存在障碍物的传感区域，进行了算法的仿真 验证； 第五章对全文进行了总结，展望了未来的研究工作。 7 重庆邮电大学硕士论文 第二章节点定位技术基础 第二章节点定位技术基础 2 1 节点间距离测量方法 在无线传感器网络中，常用的节点间距离的测量技术有r s s i 、t c i a 、) c i a 、 和a o a 。 1 r s s i 测距 r s s i ( r e c e i v e ds i 萨a ls 慨g n lh l d i c a c o r ) ，接收信号强度指示。已知发射功率 凡、路径损耗模型、路径损失系数口，信号接收方从路径损耗方程中利用接收到的 信号强度p r c v d 来确定传播距离出 = 专营d = 荐 r s s i 测距方式利用无线电的信号强度即可完成测距，传感器节点本身具有无线 通信能力，不需要额外的硬件和数据交换，是一种低功率、廉价的测距技术。因此， 这种方法估计距离是非常有吸引力的。其缺点是r s s i 的数值不是常数，即使发送 和接收双方都不移动，也可能出现严重的震荡。通常将其看作为一种粗糙的测距技 术，s a v a r e 等人闭认为它有可能产生士5 0 的测距误差。 2 t o a 测距 t o a ( 凰【n eo f a r r i v a l ) ，信号到达时间。如图2 1 所示，信号传播速度y 是已 知的，假设信号发送方和接收方都知道信号传输开始的时间而，接收方利用信号到 达时间来计算信号在介质中的传播时间，然后再计算传播距离。 发射机接收机 t o 口= ( 霉一乙) y 图2 1t o a 测距示意图 8 t l 重庆邮电大学硕士论文 第二章节点定位技术基础 t o a 要求较高精度的时钟，以获得可以接受的估计精度。因无线传感器网络节 点硬件尺寸、价格和功耗限制，实际应用t o a 技术的定位方案较少，但近期i m ，b 技术的发展以及在无线传感器网络中的应用，使得利用t o a 定位具有了广阔的前 景。 3 t d o a 测距 t d o a ( t i m ed e f ；珧n c eo n a 而v a l ) ，信号到达时间差。1 d o i a 测距技术被广泛 应用在无线传感器网络节点定位方案中。无线传感器网络在利用) o a 技术测量节 点间距时与蜂窝无线网络的移动台定位和机器人导航定位不同。如图2 2 所示，一 般是在节点上安装超声波收发器和无线电收发器。测距时，发射端的两种收发器同 时发射信号，利用声波与电磁波在空气中传播速度的巨大差异在接收端通过记录两 种不同的信号到达时间差异，基于己知信号传播速度，直接把时间转化为距离。该 技术的测距精度较高，可达到厘米级，但受限于超声波传播距离有限和n i d s 问题 对超声波信号的传播影响。虽然已有发现并减轻n l o s 影响的技术，但都需要大量 计算和通信开销，不一定适用于低功耗的无线传感器网络应用。 发射机接收机 t 0 t 2 t l d ( h ) 一( 乃圳 糟 图2 2 1 1 ) o a 测距示意图 4 a o a 测距 蛾( a n 西eo f 缸t i v a l ) ，信号到达角度。一种估算邻居节点发送信号方向的技 术，可通过天线阵列或多个接收器结合来实现，除定位外，还能提供节点的方向信 息，如麻省理工学院的，i 1 l e 翻c k e tc 伽叩私s 项目就利用多个接收器提出了基于a o a 的硬件解决方案，其原型系统可在士4 0 0 角内以士5 0 的误差确定接收信号的方向。同样， a o a 技术也受外界环境影响，如噪声、n i 力s 问题等都会对测量结果产生不同影响。 同时，a o a 需要额外硬件，在硬件尺寸和功耗上可能无法用于传感器节点。 以上四种测距方法各有利弊，以r s s i 和t d c i a 两种方法最为常用。基于i 峪s i 9 重庆邮电大学硕士论文 第二章节点定位技术基础 的方法相对简单，几乎不需要额外的硬件；基于t d o i a 的方法定位精度最高，但是 需要复杂的、额外的硬件，也增加了能量消耗。 2 2 节点坐标的估算方法 未知节点在获得与锚节点间的距离( 或方位角) 后就可以采用三角测量法 ( t r i a n g u l 撕0 n ) 、三边测量法( t r i l a t 酬i o n ) 、极大似然估计法( m a x i l l l 啪l i k e l i h 0 0 d e s t i m a t i o n ) 或m n m 瓤法估算节点位置。 2 2 1 三角测量法 三角测量法是通过为直接点接收器天线或天线阵列测出锚节点发射电波的入射 角，从而构成一根从未知节点到锚节点的径向连线，即方位线。在二维平面中，利 用两个或更多锚节点的a o a 测量值，按照j 蛾定位算法确定多条方位线的交点， 即可计算出未知节点的位置估计。如图2 3 所示， 图2 3 三角测量法示意图 假设未知节点a 的坐标为( ，) ，锚节点b 、c 的坐标分别为( 五，m ) 、( 屯，咒) 发出信号的到达角度分别为鼠和幺，则有式2 1 成立， t a i l ( 谚) = 业，f = 1 ，2 ( 2 1 ) y o y t 通过求解上述非线性方程组，可以得到未知节点的位置坐标( ，) 。 2 2 2 三边测量法 在基于测距的定位算法中，三边测量法( t r i l a ：t c r ，m o n ) 是计算位置节点坐标的 基本途径，其基本原理如图2 4 所示：若未知节点n 到锚节点l 1 的距离西，那么n 可能出现在以l l 为圆心，西为半径的圆上。若再知道n 到另一锚节点k 的距离必， l o 重庆邮电大学硕士论文 第二章节点定位技术基础 那么n 也可能出现在以k 为圆心，玉为半径的圆上。即n 可能出线在两圆的交点 上。此时，如果再知道n 与第三个锚节点l 3 的距离西，在测距精准的前提下，以 l 3 为圆心，西为半径的圆一定与上述两个圆交于一点，该点即为n 的坐标。 一一一一、 、 i l 、 l | 图2 4 三边测量法示意图 假设锚节点l l 、k 、l 3 的坐标分别为瓴，乃) 、瓴，蜴) 、( 屯，乃) ，到未知节点n 的距离分别为西、函、西，n 的位置估计为( j c o ，) ，根据毕达哥拉斯( p 灿a 9 0 r a s ) 定理，有下列方程组成立： ( 而一五) 2 + ( 儿一乃) 2 = 砰 ( 一而) 2 + ( 一儿) 2 = 彰 ( 2 2 ) ( 而一恐) 2 + ( 一乃) 2 = 露 为了求解这个方程组，把它转换成关于孙肋的线性方程组。因此要消除二次项 和诟。式2 2 中前两个方程分别减去第一个方程，得到方程组： f ( 而一而) 2 一( 而一而) 2 + 饥一乃) 2 一( 儿一乃) 2 = 砰一霹，、 【一而) 2 一( 一弓) 2 + ( 一耽) 2 一( 一乃) 2 = 彰一彰 上式很容易写为线性矩阵方程，整理后解出未知节点n 的坐标( 而，儿) 为： 蠹 = 主 三二三j 主 羔二羔j 。1 要二妻：要二要：墨二荔 c 2 4 ， 【- 甄j 【2 ( 吃一而) 2 ( 奶一乃) j1 # 一+ 正一露+ 彰一彰j “ 三边测量法的缺点是：若在测距过程中存在误差，上述三个圆不会只产生一个 交点。为了克服这个缺陷，可以测量未知节点到多个锚节点的距离，这样定位问题 就成了一个多边定位( m u l t i l a t e m d o n ) 问题了。 2 2 3 极大似然估计法 在进行三边测量时，由于无线传感器网络节点的硬件和能耗限制，节点间测距 重庆邮电大学硕士论文 第二章节点定位技术基础 误差通常较大，因此经常出现三个圆不止一个交点的情况，这时就需要使用多边测 量( m u l t i l a 魄a t i o n ) 的极大似然估计法求最优解，其基本原理就是寻找一个使测距 距离与估算距离之间差异最小的点，以该点为未知节点的位置。 图2 5 极大似然估计法示意图 如图2 5 所示，n 为未知节点，求其位置估计( 而，) ，l l 、k 、l 3 和l 4 均为锚 节点，坐标为“，咒) 、( 恐，耽) 、瓴，乃) 和( _ ，儿) ，测得未知节点n 到四个锚节点 的距离分别是n 、岛、岛和风，则有： 石。= 岛一( ( 五一而) 2 + ( m 一) 2 ) ( 2 5 ) 五i o = 见一( 也一而) 2 + ( 奶一) 2 ) ( 2 6 ) 五o = 岛一( ( 而一) 2 + ( 乃一) 2 ) ( 2 7 ) 工o = 成一( ( 一而) 2 + ( 儿一蜘) 2 ) ( 2 8 ) 其中，a 为未知节点n 与锚节点k 的间测量距离，( 而一) 2 + ( 一) 2 表示锚节点 l i 与未知n 的估算距离，其中i - 1 ，2 ，3 ，4 。需要求得未知节点n 的坐标( 而，) ，使得 4 彳o 之和最小。即：石，。= l i l i n ( 石，。+ 五，。+ 六。+ 工，。) 。 j = 】 根据二维空间距离计算公式，可以获得下面的方程组： 只= 正i 了瓦f 万 岛2 ! 兰二兰! ：! 兰二兰! ：。2 9 ， 岛= ( 坞一而) 2 + ( 乃一) 2 以= 订f 了瓦f 孑 式2 9 中，( ，儿) 是未知量，这是非线性方程组，可以采用线性化方法来求解。 如果近似知道节点的估计位置，可以将其真实位置( 砌枷和近似位置( 磊，允) 之间的 偏离用位移( ，缄) 来标记。将式2 9 按泰勒级数绕近似位置展开，那么便可将位 置偏移( 瓴，峨) 表示为已知坐标和距离测量值的线性函数。 1 2 重庆邮电大学硕士论文第二章节点定位技术基础 单一测量距离可表示为： 屏= 瓜i 了瓦鬲了 纠，2 ，3 ，4 ( 2 - l o ) 单一距离近似可表示为： a = ；i _ i 了i 石丽= ( 袁，丸) f = 1 ，2 ，3 ，4 ( 2 1 1 ) 如上所述，节点的真实位置由近似分量和增量两个部分组成，即： 睢羔：麓 泣m 因此，有 厂( 而，) = 厂( 南+ 瓴，允+ 峨) ( 2 1 3 ) 上式右边函数用泰勒级数展开成： 厂( 式+ 瓴，允+ 峨) 厂( 毛，九) + 掣瓴+ 掣舰 ( 2 - 1 4 ) 以。叫。 为了消除非线性，上述展开式中截去了一阶偏导数之后的各项。偏导数计算如下： ：一世 疋 江1 ，2 ，3 ，4 ( 2 1 5 ) 式2 1 5 中，霉= ( 蕾一岛) 2 + 一允) 2 。将式2 1 l 、2 1 4 和2 1 5 带入式2 1 0 ，可以 得到： 岛= a 一# 卑缸一譬善砂 ( 2 1 6 ) 7 j 这样就完成了式2 9 相对于未知数( 瓴，峨) 的线性化。整理上述表达式，得到： a 一届= 至尝缸一譬丝缈 ( 2 1 7 ) _吒 为表达方便，引进下述新变量以简化上述公式： = 三尝 ，i 辟= a 一辟 f = 1 ，2 ，3 ，4 ( 2 1 8 ) 口埘= 譬兰 乃 这样，式2 1 8 可以表示为： 蛔= 瓴+ 峨 ( 2 1 9 ) 九一 一 一瓯一豌 可一 矿一 重庆邮电大学硕士论文 第二章节点定位技术基础 要在二维空间中确定一个点的坐标，必须有至少三个参考点，在无线传感器网 络中，节点之间的连接很多，大多数节点部可以直接或间接的获得三个以上参考点 的不精确距离。因此可以得到一个方程组： 翰= q l 瓴+ 口y l 峨 舰= 口，2 瓴+ q 2 鲰 确= q 3 瓴+ 如3 鲰 ( 2 2 0 ) 厶p n = a 讯k q 七q 州驽q 上述过定义方程组2 2 0 司以使用最小二乘法来求解，具体步骤如f ： 窆 舰一瓴+ 砒 2 ( 2 2 1 ) 为了求得函数厂( 峨，峨) 取得最小值时的瓴和哦，对函数求导并令之等于 o ，即： 掣= 喜 舰一瓴+ 峨 = 。 ( 2 - 2 2 ) 掣= 喜 m 一瓴+ 峨 = 。 ( 2 ) 式2 2 2 、2 2 3 绎过整理可得2 由此，可以得到： 岛= 幽，口三+ 匈。 2 1“ 、。1( 2 2 4 ) “hh 辟= 蚝+