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

福建师范大学钟进发硕士学位论文 h ，： l 摘要 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k ( w s n ) t e c h n o l o g y , a so n eo ft h em o s te s s e n t i a l i n f o r m a t i o nt e c h n o l o g i e s ，h a sb e e nd e v e l o p e dr a p i d l ya n da p p l i e di nw i d ef i e l d sr e c e n t l y s e n s o rn o d e 。sl o c a t i o ni n f o r m a t i o ni sc r u c i a lt ot h en e t w o r k sp e r f o r m a n c ea n d f u n c t i o n a l i t i e s w i t h o u tn o d e sl o c a t i o ni n f o r m a t i o nt h e s e n s i n gd a t aw o u l db e m e a n i n g l e s si nm o s tw s na p p l i c a t i o i i s n 圮s t u d yi nt h i sp a p e rf o c u s e so nn o d e sl o c a l i z a t i o na l g o r i t h m si nw s n ，a n d m a i n l yd i s c u s s e so nt h ei m p r o v e m e n ts c h e m e so fr a n g e f r e el o c a l i z a t i o na l g o r i t h m sa n d s e c u r el o c a l i z a t i o ns c h e m e s f i r s t l y , a ni m p r o v e dd v - h o pl o c a l i z a t i o na l g o r i t h mb a s e d o nt h eo r d e r e dn e i g h b o r i n gn o d e si ns p a c ew a sp r o p o s e di no r d e rt oi m p r o v et h e p r e c i s i o no fn o d e s l o c a l i z a t i o nr e s u l t ，t h ep e r f o r m a n c ew o u l db eb e t t e rw h e nt h eb e a c o n n o d e sa r eu n d e ral o wr a t i oc o n d i t i o n s e c o n d l y ，ar a n g e f r e ea l g o r i t h mb a s e do nm o b i l e s i n kn o d ea n dd v - h o pl o c a l i z a t i o ns c h e m ew a sp r o p o s e di no r d e rt od e c r e a s et h e h a r d w a r ec o s ta n di m p l e m e n tc o m p l e x i t yi nw s n ，t h em o b i l es i n kn o d ed on o tr e q u i r e d t oc o v e rt h ew h o l en e t w o r ka r e aa n dw i t h o u ta t t a c ha n yd i s t a n c em e a s u r ee q u i p m e n t ，t h e l o c a l i z a t i o ni n a c c u r a c yw o u l db e c o m es m a l l e r 嬲t h ev i r t u a lb e a c o n sr a t i ob e c o m e g r e a t e r f i n a l l y , a s s u m e dt h a ts o m eo fb e a c o nn o d e sw e r ea t t a c k e da sar e s u l to ft h e s e c u r ev u l n e r a b i l i t yo fw s n ，as e c u r ed v - h o pl o c a l i z a t i o na l g o r i t h mb a s e do nb e a c o n s c r e d i t sw a sp r o p o s e d ，b yd i s t r i b u t e dc a l c u l a t i n gt h ec r e d i t so fb e a c o n s ，n o d e sc o u l d e f f e c t i v ee l i m i n a t et h em a l i c i o u sb e a c o ni n f o r m a t i o nt oe n s u r et h ec o r r e c t n e s so fb e a c o n l o c a t i o ni n f o r m a t i o nt h e yr e c e i v e d k e y w o r d s ：w s n ，l o c a l i z a t i o na l g o r i t h m ，d v - h o p ，v i r t u a lb e a c o n ，s e c u r i t yl o c a l i z a t i o n f 培 i i i 8洲7洲0 7081洲y 福建师范大学钟进发硕士学位论文 - l i _ - - _ _ - - l _ _ _ - _ - - - - _ - _ _ - _ _ - - l - - _ _ _ _ i _ _ l _ i _ _ - _ _ _ _ 一_ _ i v ? l l，j! f1硝p l ： 中文文摘 中文文摘 得益于微机电系统技术、通信技术和计算机技术的发展，无线传感器网络技术 也日益成熟，使其在国防、工农业、环境监测等众多领域都有着重大的应用价值和 科研价值。无线传感器网络的某些路由机制、覆盖信息、负载均衡及拓扑控制等都 依赖于网络中节点的位置信息，作为无线传感器网络应用的重要支撑技术之一的节 点定位技术正吸引着越来越多的研究者。 在获取无线传感器网络节点位置信息过程中，一方面由于无线传感器网络节点 数量庞大、随机分布且软硬件资源有限；另一方面，节点定位的希望能达到精度高、 安全性好。如何控制、平衡这两方面矛盾的对立方法之一便设计计算代价小、通信 量少的定位算法。本文正是基于无线传感器网络节点定位技术出发，特别是以无需 测距定位算法为主，在定位算法的设计和实现的过程中尽量平衡上述矛盾，其算法 设计目标有如下几个方面： ( 1 ) 实现节点定位功能的前提下无需增加额外的测距设备，免去了节点增 加额外设备带来的体积增大、硬件成本增加、灵活性减小等不良影响。 ( 2 ) 增加少量( 或不增加) 通信代价、计算代价的情况下有可观的定位精 度提高。 ( 3 )增加少量通信代价、计算代价实现网络节点间的协同，实现或提高节 点定位过程中的安全性。 本文在第一章将阐述目前无线传感器网络节点定位技术的分类，定位算法的相 关评判要素及当前传感器节点定位技术在现实社会中的应用例子，并对无需测距的 定位算法在无线传感器网络中实现定位的优势进行相关阐述和分析。第二章中将针 对典型的d v - h o p 定位算法中未知节点在计算与信标节点间距离时估算的不足之处， 提出一种基于邻节点空间顺序序列优化的d v - h o p 定位算法，该算法可以在增加少量 通信代价、计算代价的条件下实现提高定位精度的目标，特别是在网络信标节点比 例较低的情况下效果更明显。第三章中将提出一种基于虚拟信标的节点定位算法， 该算法无需真实物理信标节点，大大降低网络的硬件构造成本：移动s i n k 节点无需 覆盖整个网络部署区域便可以实现网络节点的定位，对移动路径、范围无特殊限制， 降低算法实现门槛；网络节点在获取与当前s i n k 节点距离过程中无需额外的测距设 v 福建师范大学钟进发硕士学位论文 备；不增加网络成本的情况下，网络中可以有高比例的虚拟信标节点，提高定位精 ； 度。第四章中针对d v - h o p 定位算法提出了一种基于安全信标节点的安全定位算法， ， 该算法能使未知节点有效剔除恶意信标节点发出的位置信息分组，从而排除误差很 大的参考位置信息分组，在一定程度上实现节点定位过程中的安全性，该算法采取 分布式计算实现，提高了本文算法在无线传感器网络中的实现意义，并且实现简单、 有效。第五章结论部分对本论文的无线传感器网络节点定位技术研究成果进行了总 结与展望其发展趋势及下一步的相关研究工作。! v i 冉 细 噜 目录 目录 中文摘要 a b s t r a c t 中文文摘 】【 i i i l i i 录 坌蕾论1 第一节课题研究背景1 第二节研究现状2 第三节研究目标5 第四节课题来源及内容结构5 第一章无线传感器网络节点定位机制7 第一节无线传感器网络节点定位机制概述7 第二节基于测距及无需测距的经典定位算法9 第三节无线传感器网络节点定位算法的评判要素1 2 第四节无线传感器网络节点定位技术的应用领域- 1 3 第二章基于邻节点空间顺序序列优化d v - h o p 算法1 7 第一节研究背景1 7 第二节d v - h o p 定位算法介绍。1 7 第三节优化方案的设计及实现1 8 第四节仿真实验结果及分析2 3 第五节本章小结：2 5 第三章基于虚拟信标节点的定位算法2 7 第一节网络部署成本对其应用的影响2 7 第二节移动信标及移动s i n k 节点的应用2 7 第三节相关原理及算法设计2 8 第四节仿真实验结果及分析。3 3 第五节本章小结。3 5 第四章基于安全信标节点的d v - h o p 定位算法3 7 v i i 福建师范大学钟进发硕士学位论文 第一节安全信标节点在定位过程中的需求3 7 第二节信标节点验证方案设计3 8 第三节基于安全信标节点的d v - h o p 定位算法设计3 9 第四节仿真实验结果及分析4 2 第五节本章小结4 4 第五章结论4 7 第一节本文工作总结4 7 第二节今后工作展望4 8 参考文献4 9 攻读学位期间承担的科研任务与主要成果5 3 致谢5 5 个人简历。5 7 v i i i 争 i 绪论 绪论 无线传感器网络能够通过节点间协同工作，实时获取监视区域各类工作对象的 信息。作为连接物理世界和数字世界的桥梁，网络中节点的位置信息对整个网络的 功能和性能起着至关重要的作用。对大多数的无线传感器网络而言，不知道传感器 节点位置而感知的数据是没有意义的【l 】。 第一节课题研究背景 无线传感器网络的应用有着非常广阔的应用领域，比如军事应用、环境科学监 测、安全监控、医疗保健、智能交通管理、目标跟踪、空间搜索、其他商业应用等。 在空间探索和灾难救援等特殊的领域，传感器网络有其得天独厚的技术优势【2 】。由于 有着巨大的科学研究价值和应用前景，传感器网络技术被美国技术评论杂志评 选为对人类未来生活产生深远影响的十大新兴技术之一，且被列为第一【3 l ；美国商 业周刊技术评论中也已经将传感器网络定位成2 1 世纪高技术领域的四大支柱型产 业之一。如果说因特网构成了逻辑上的信息世界，改变了人与人之间的沟通方式， 那么，无线传感器网络就是将逻辑上的信息世界与客观上的物理世界融合在一起， 改变了人类与自然界的交互方式【4 】。然而其应用的前提都离不开传感器网络节点的 位置信息，所以网络节点的定位技术便成为无线传感器网络技术中必须要解决的关 键技术之一。 作为无线传感器网络技术共性、关键支撑技术之一的节点定位技术对无线传感 器网络的应用和发展都具有重要的意义： 一方面，节点定位技术对无线传感器网络的应用起着关键的作用。 无线传感器节点为用户提供其所在环境的上下文相关信息过程中8 0 的信息与 位置信息有关【5 】，甚至在有些应用中只需发回单纯的位置信息即可【6 】。节点位置信 息作为无线传感器网络应用的基础信息之一【7 j ，很多上层的应用都需要节点的相关 位置信息。如在基于地理位置的路由协议中为了避免信息在整个网络中的泛洪，利 用节点位置信息进行定向数据分组发送或转发，也可以实现定向信息查询等相关任 务1 4 ；一些非基于节点地理位置信息的路由协议【8 观也可以利用节点位置信息来提 高路由效率：节点的位置信息可以在网络拓扑控制机制中构建网络拓扑结构图及评 估节点的分布情况等。 福建师范大学钟进发硕士学位论文 另一方面，节点定位技术面临的挑战也是无线传感器网络技术需要解决的难点 之一。 与其他网络节点相比较，无线传感器网络节点具有如下特点： 1 、网络节点体积小； 2 、节点能量有限； 3 、通信能力有限； 4 、计算和存储能力有限； 5 、节点数量大、节点部署密度大，分布区域可能广阔。 而在传感器网络节点中安装g p s 接收器不但受到节点造价成本、功耗、扩展 性等问题的限制，而且在某些室内场合可能根本无法实现。 在设计节点定位算法时不但要受到传感器网络节点自身特点带来的束缚，而且 传感器网络的部署环境在没有基础设施的协助【1 0 1 ，这对节点定位技术也提出了更高 的要求，应该保证定位精度、安全性的同时采用分布式计算方式并尽可能地减小节 点定位过程所耗的计算、通信代价。 第二节研究现状 无线传感器网络中的定位机制与算法包括两部分：节点自身定位和外部目标定 位，前者是后者的基础，在本文中的重心是节点自身定位技术。在现有的技术中， 一般利用在无线传感器网络中部署少量位置信息已知的信标节点作参考来获取其他 位置信息未知的未知节点的位置信息。目前，无线传感器网络节点定位技术的研究 人员已经根据不同的研究侧重点，对节点定位技术提出了不同的分类。主要分类如 下： 1 、绝对定位与相对定位【l l 】； 2 、紧密耦合与松散耦合【1 2 】： 3 、集中式计算与分布式计算【1 3 】；： 4 、基于测距的定位算法和无需测距的定位算法【1 4 1 。 当前的研究人员大多都采用基于测距的定位算法和无需测距的定位算法来对 具体的定位算法进行分类。基于测距的定位方法通过节点配备额外测量设备测量节 点间点到点的距离或角度信息，利用三边测量、三角测量或极大似然估计定位法计 算出未知节点的位置信息。基于测距的定位技术常用的测距算法有r s s i t l 5 1 、t o a 1 6 1 、 t d o a t l 7 1 及a o a 1 8 1 等。无需测距的定位方法则无需配备额外的设备来获取节点间点到 是 q j ： 绪论 点的距离或角度，仅根据网络的连通性和信标节点的位置信息实现相对精确的定位 功能。无需测距的定位技术典型的算法有：质心法n 9 1 、d v - h o p 算法【2 0 】、凸规划算 法 2 1 】、a p i t 算法瞄1 和m d s m a p 定位算法【2 3 】等。基于测距的定位方法精度相对较高， 但对节点的硬件要求很高，并且通常需要多次测量，循环定位求精，从而增加了大量 的计算开销和通信开销，所以这种方法虽然定位精度较高，但不适合低成本、低功 耗的无线传感器网络。虽然无需测距的定位精度一般不如基于测距的定位方法，但 无需配备额外的设备，在精度允许的情况下，更适合低成本、低功耗的无线传感器 网络，也是无线传感器网络节点定位技术发展与研究的趋势。 到目前为止，无线传感器网络节点定位算法的研究大致经过了以下两个主要阶 段： 第一阶段：主要偏重于基于基础设施( 如基站) 的定位系统。 第二阶段：主要是对于无需基础设施的定位技术的关注和研究。 目前，第二阶段已经成为无线传感器网络研究和应用领域的热点。 本文正是从无需基础设施的定位技术的研究出发，特别是对无需测距的节点定 位技术进行研究，并以d v - h o p 定位算法为主线贯穿全文。 在文献【2 4 】中，美国路特葛斯大学( r u t g e r su n i v e r s i t y ) 的d r a g o sn i c u l e s c u 等人利用距离矢量路由协议和g p s 定位的原理提出了一系列分布式定位算法，合称 为a p s ，其中的d v h o p 定位算法便成为研究无需测距定位算法的经典算法。很多 研究者都在该算法的基础上对其进行改进，比如文献 2 5 中，张晓龙等在d v - h o p 定位算法的基础上利用了节点的邻节点集重叠度估算夹角的大小来计算更精确的未 知节点到信标节点路径中相邻三个节点组成的夹角，使改进的d v - h o p 定位算法在 定位精度上有所提高。现有典型无需测距定位算法的性能比较如表0 1 ，它们均是 分布式算法。 近年来国内外也有研究者从定位安全性的角度出发，考虑安全定位算法对传感 器网络的影响。文献【2 6 】中，l i u 等人最先引入将信标节点作为检查点的思想来检测 和隔离恶意信标节点；文献【2 7 】中，e e k i e i 等人提出一种基于概率方法的节点位置 校验算法，根据转发广播报文的跳数与距离的概率关系评估节点位置信息的信任等 级；文献 2 8 】提出一种容忍攻击的安全定位机制与实现算法，该定位算法以方差的 无偏估计作为安全性的检验依据，采用随机方法挑出一个最小安全参照集来提高了 定位系统容忍攻击的能力。 福建师范大学钟进发硕士学位论文 表o 1典型无需测距定位算法的性能比较 名称信标比例定位误差通信代价特点描述 质心大约9 0 的节小易实现，但需要高比例的信标节 点误差为 占 3 3 凸规划小小大计算量大，可扩展性差 a p i t 大 4 0 大需要高比例信标节点 d v 。h o p小 3 3 大适用于各向同性网络 d v d is t a n c e 小 2 0 大适用于各向同性网络 m d s m a p小2 5 大依赖网络拓扑结构 不同的网络应用需求就需要相应的设计和部署，传感器网络节点定位技术的应 用也是如此，不同的应用需求要求我们在设计定位算法时的重心也不一样。比如对 定位精度要求、对节点位置信息保密程度、对节点定位过程的计算代价、通信代价 等。 目前，发达国家，如美国己有很多大学开展了无线传感器网络方面的研究，科研、 学术水平走在前面的有加州大学伯克利分校、哈佛大学、麻省理工学院等。国内对 基于传感器网络的定位技术研究还属起步阶段，但还是有一定的研究基础，如史龙 等人在综合分析大量无线传感器网络定位算法的技术文献和最新研究结果的基础 上，指出无线传感器网络自身定位问题的研究方向。国内在传感器节点定位技术方 面走在前面的有西北工业大学、国防科技大学、中国科学院、解放军理工大学等。 近十几年来，传感器网络节点定位技术由于在应用中的需求越来越多，要求越来 越高，其所面临的挑战问题越来越多，但相关的研究工作也取得了相对丰富的研究 成果。特别是进入2 1 世纪后，对节点定位问题有了许多新颖的解决方案和思想。随 着技术的不断发展，人们对应用的要求也越来越苛刻，无线传感器网络节点的定位 技术仍然面临着巨大挑战和技术瓶颈，总之，无线传感器网络节点定位问题的研究 仍然是无线传感器网络技术的难点、关键点之一。 掌 绪论 第三节研究目标 无线传感器网络由于其使用的目的以及要求不同，存在着许多特点【2 9 】，而不同 节点定位算法都有其各自的特点，这就使得无线网络的节点定位技术往往与其应用 密切相关，不同的应用可能选择不同的定位算法。实验表明，当定位误差小于传感 器节点无线通信半径的4 0 时，定位误差对路由性能和目标追踪精确度的影响不会 很大d o ，对定位要求不是特别严格的传感器网络的应用来说这种定位精度已经可以 满足应用要求了。无需测距定位机制在精度允许的情况下，更适合低成本、低功耗 的无线传感器网络，是无线传感器网络节点定位技术发展与研究的趋势，也是本文 内容的主要组成部分。 本文的主要研究目标有以下三点： ( 1 ) 优化定位算法、提高定位精度。 针对典型的d v - h o p 定位算法中未知节点在计算与信标节点间距离时估算的不 足之处，在d v - h 0 p 算法的基础上提出了一种优化定位精度的算法。 ( 2 ) 整合相关定位算法，在保证定位精度的同时降低定位代价。 利用无需测距定位算法的网络节点成本代价优势、r s s i 算法的短距离测距精度 优势及移动s i n k 节点为网络未知节点提供位置参考信息实现未知节点利用网络 多跳信息的低网络硬件成本定位。 ( 3 ) 基于d v - h o p 定位算法设计一种安全信标节点定位算法。 针对d v - h o p 定位算法中的信标节点被入侵攻击后发出错误或虚假的位置信息 分组后，接收到信标节点发出的位置信息分组的未知节点利用一种代价小的验证 方案来检验收到的位置信息分组是否可靠。 第四节课题来源及内容结构 本学位论文的研究工作主要得到如下项目的资助： ( 1 ) 国家自然科学基金：安全和能量感知的可编程复杂动态自组织网络研究 ( 6 0 5 0 2 0 4 7 ) ； ( 2 ) 福建省自然科学基金项目：无线传感器网络节点安全定位机制与算法的研究 ( 2 0 0 9 j o l 0 1 ) ： ( 3 ) 福建省自然科学基金项目：基于容错分簇和跨层协作的传感器网络安全匿名路由 技术( 2 0 0 8 j 0 0 1 4 ) ： 福建师范大学钟进发硕士学位论文 ( 4 ) 福建省科技计划项目：无线传感器网络节点安全定位关键技术( 2 0 0 8 f 5 0 2 0 ) 。 本学位论文的研究工作是围绕着无线传感器网络节点定位算法，特别是无需测 距定位算法这方向进行的，论文的研究内容安排如下： 绪论部分介绍了本课题相关的研究背景、目前国内外无线传感器网络节点定位 技术的研究现状、本论文的研究目标及课题来源，最后对本文的内容结构作简单的 介绍。 第一章介绍了目前无线传感器网络节点定位技术的分类，对无需测距的定位算 法在无线传感器网络中实现定位的优势进行相应阐述和分析，定位算法的相关评判 要素及当前传感器节点定位技术在现实社会中的应用例子等。 第二章针对典型的d v - h o p 定位算法定位过程中未知节点在计算与信标节点间 距离时估算的不足之处，提出一种基于邻节点空间顺序序列优化的d v - h o p 定位算 法，该算法可以在增加少量通信代价、计算代价的条件下实现提高定位精度的目标， 特别是在网络信标节点比例较低的情况下效果更明显。 第三章提出一种基于虚拟信标的节点定位算法，该算法无需真实物理信标节点， 大大降低网络的硬件构造成本；移动s i n k 节点无需覆盖整个网络部署区域便可以实 现网络节点的定位，对移动路径、范围无特殊限制，降低算法实现门槛；网络节点 在获取与当前s i n k 节点距离过程中无需额外的测距设备；不增加网络成本的情况 下，网络中可以有高比例的虚拟信标节点，提高定位精度。 第四章以无线传感器网络安全脆弱性出发，针对d v - h o p 定位算法提出了一种 基于安全信标节点的安全定位算法，该算法能使未知节点有效剔除恶意信标节点发 出的位置信息分组，从而排除误差很大的参考位置信息分组，在一定程度上实现节 点定位过程中的安全性，该算法采取分布式计算实现，提高了本章算法在无线传感 器网络中的实现意义，并且实现简单、有效。 第五章结论部分对本论文的研究内容进行了总结，展望无线传感器网络节点定 位技术的发展趋势及下一步的相关研究工作。 第一章无线传感器网络节点定位机制 第一章无线传感器网络节点定位机制 第一节无线传感器网络节点定位机制概述 对传感器网络节点定位的目的就是获取各传感器节点在平面或空间中的绝对或 相对位置信息，因为在传感器网络的许多应用中，用户关心的一个重要问题是：在 什么位置或区域发生了什么事件。因此传感器网络节点感知、采集的数据必须绑定 其位置信息，从而实现对感知、采集的数据有效应用。 1 1 1 节点定位机制的相关术语 本文中的相关术语概念定义如下： 信标节点( b e a c o nn o d e ) 信标节点是通过人工部署或配备g p s 接收机设备等手 段获得自身节点的精确位置信息，它们在整个网络中所占的比例比较小，其部署目 的是协助未知节点进行定位。 未知节点( u n k n o w nn o d e ) ：未知节点是部署在网络中位置信息未知的节点，它 们在整个网络中所占的比例比较大，它们与信标节点是组成整个无线传感器网络的 主要部分。 邻居节点( n e i g h b o rn o d e ) ：指某传感器节点通信半径内能直接通信的所有节点。 跳数( h o pc o u n t ) ：指两个网络节点间间隔的最小网络跳段数。 平均单跳跳距( h o ps i z e ) ：指两个节点之间的平均单跳距离值，即两个节点之间 间隔的距离除以它们间的跳数。 1 1 2 无线传感器网络节点典型结构 传感器节点的体积一般比较小，甚至小于1 c m 3 。在不同应用领域中，传感器节 点的具体硬件组成不尽相同，但基本结构大体相同。典型的节点结构如图1 1 所示， 主要包括感测单元、数据处理单元、数据收发单元和供电单元四个部分。 1 1 3 节点定位的基本原理 在现有的技术中，一般利用在无线传感器网络中部署少量位置信息已知的信标 节点作参考来获取其他位置信息未知的未知节点的位置信息。在传感器网络中的节 点定位与全球定位系统( g p s ) 原理一致，即在三维空间中，若某一节点获得了到另外 四个或四个以上的参考节点距离，便可以确定该节点的位置信息【3 l 】。同理，在二维 空间中，若某一节点获得了到另外三个以上( 包括三个) 参考节点的距离，便可以 确定该点的位置坐标。目前经常用的计算节点坐标的方法有：三边测量法、多边测 福建师范大学钟迸发硕士学位论文 量法的极大似然估计法、m i n m a x 法及三角测量法等。下面重点介绍一下三边测量 法及其变换形式多边测量法。 图1 1 传感器节点硬件组成 如图1 - 2 ( a ) 所示，三边测量定位法的基本原理是利用以三个信标节点为圆心， 及三个信标节点分别到该未知节点的距离为半径的三个圆在平面中的交点来推算出 未知节点的位置坐标。如图1 - 2 ( b ) 所示。假设某一未知节点”测得到，2 个信标节 点的距离( 佗3 ) ，其中第f 个信标节点的位置坐标为助且到节点“的距离为西。 则可以得到如下系统方程： ( x i x ) 2 + ( y i 一夕) 2 = d 1 2 ( x 2 一x ) 2 + ( j ，2 一夕) 2 = d ； ( 1 1 ) ( x 。一x ) 2 + ( y 。一j ，) 2 = d ： 其中( 毛y ) 为节点甜的坐标。为了使得问题线性化，上述方程组转换为用a x = b 形式，其中 a = 2 ( 五一而) 2 ( 一厂吒) 2 挑一只) 2 ( i 一) ， 6 。 吱一+ 识一记+ d ：一 丐2 - 一露+ y 2 ，一露+ 刃一d i 。 上述方程可用最小二乘方法解得更= ( 彳) 1 a r b 。从而解得位置的估计值启。 第一章无线传感器网络节点定位机制 。未知节点 信标节点 ( a ) 三边测量法示图 ( b ) 多边测量法 图1 2 三边测量法及多边测量法 第二节基于测距及无需测距的经典定位算法 基于测距的无线传感器网络节点定位技术： 基于测距的定位方法通过节点配备额外测量设备测量节点间点到点的距离或角 度信息，利用三边测量、三角测量或极大似然估计定位法计算出未知节点的位置信 息。基于测距的定位技术常用的测距方法有r s s i 、t o a 、t d o a 及a o a 等。 r s s i ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) ：r s s i 技术是将无线信号的传输损耗 转换成距离。常用的传播路径损耗模型有：自由空间传播模型，对数距离路径损耗 模型，哈它模型以及对数常态分布模型等【3 2 1 。r a d a r 3 3 】和s p o t o n 【3 4 】等许多项目 都应用r s s i 技术。r s s i 测距准确度依赖于信号的强度、传播模型和信号衰落模型， 通常被视为一种粗糙的测距技术，有士5 0 的测距误差【3 5 】。 t o a ( t i m eo fa r r i v a l ) ：根据发送器信号发出的时间和接收器收到信号的时间 差，乘以无线电波在介质中的传播速度，得到两者间距离。 t d o a ( t i m ed i f f e r e n c eo i la r r i v a l ) ：t d o a 技术通过记录两种不同信号在节点 中的传播时间差，由传播时间差计算得到距离的方法。 a o a ( a n g l eo fa r r i v a l ) 测距：将距离的测量转换为角度的测量，未知节点通 过天线阵列或其他特殊接收设备感知参考节点信号的到达方向，计算两节点之间的 相对方位角，最后通过三角测量法计算未知节点坐标的方法。如图1 3 所示，假定 未知节点分别测得与信标节点n l 和n 2 所构成的角度0 l 和0 2 ，且n l 、n 2 分别位于 ( x l ，y 1 ) 和( x 2 ，y 2 ) ，则t a i l ( 谚) = 立竺，f = 1 , 2 成立，通过求解该方程，可得到未 y o y 知节点的位置( x o ，y o ) 。 福建师范大学钟进发硕士学位论文 n l 图1 3a o a 定位示意 无需测距的无线传感器网络节点定位技术： 无需测距的定位方法则无需配备额外的设备，仅根据网络的连通性和信标节点 的位置信息实现相对精确的定位功能。无需测距的定位技术典型的方法有：质心法、 d v h o p 算法、凸规划算法、a p i t 算法等。 ( 1 ) 质心法 质心法( c e n t r o i da l g o r i t h m ) 是一种仅基于网络连通性的定位算法，节点通过通 过收到的位置广播信息，将自身位置确定为所有与之连通的信标节点所组成的多边 形的质心。设未知节点有后个连通信标节点，且其中第i 节点的坐标为伍i ，粥) ，则未 知节点的物理位置估计值为( 曼，刃可采用如下公式计算： ( 朔= c 壁产，业产) ( 1 - 2 ) ( 2 ) d v - h o p 算法 d v - h o p 定位方法是一种典型的利用多跳信标节点信息的定位策略。该算法包括 三个阶段。1 ) 网络中的节点利用距离矢量交换协议获取自身与每个信标节点的最小 跳数；2 ) 各信标节点利用式1 - 3 计算平均单跳距离校正值后广播至网络中： ( x ，一x + ( 少，一y j ) 2 却沏，= 堡l 1 石_ n _ 3 ) 其中，蚰，( 勃助分别是信标节点f 和_ 的坐标，h u j 是f 与之间的跳数。3 ) 未 知节点利用三边测量法或极大似然估计法计算自身位置。 ( 3 ) a p i t 算法 第一章无线传感器网络节点定位机制 a p i t ( a p p r o x i m a t ep i tt e s t ) 的主要思想是未知节点从所有邻居信标节点中任 选3 个构成一个三角形并判断自身是否处于该三角形中，然后对不同信标节点组合 进行重复测试，直到测试完所有组合或者精度满足要求为止。最后，计算所有包含 未知节点的三角形交集的质心，以此确定自身的大致位置。a p i t 的定位原理如图 1 _ 4 所示，其中每个三角形的顶点均为信标节点。 未知节点 图1 4a p i t 定位算法示意 ( 4 ) 凸规则定位法 凸规则定位法将节点间的通信连接视为节点位置的几何约束，把整个网络模型 化为一个凸集，从而将节点定位问题转化为凸约束优化问题，然后使用半定规划和 线性规划方法得到一个全局优化的解决方案，确定节点位置。如图1 5 所示图中交 汇部分便是节点可能存在的位置，并得到相应矩形区域，然后以矩形的质心作为未 知节点的位置。 o 信标节点 未知节点 图1 5 凸规划算法示意 通过上面的描述，可以看出基于测距的定位方法精度相对较高，但对节点的硬 件要求很高，并且通常需要多次测量，循环定位求精，从而增加了大量的计算开销和通 信开销，所以这种方法虽然定位精度较高，但不适合低成本、低功耗的无线传感器 网络。无需测距的定位精度一般不如基于测距的定位方法，但无需配备额外的设备， 在精度允许的情况下，更适合低成本、低功耗的无线传感器网络，也是无线传感器 福建师范大学钟迸发硕士学位论文 网络节点定位技术发展与研究的趋势。 第三节无线传感器网络节点定位算法的评判要素 无线传感器网络节点定位机制和算法的性能将直接影响其可用性，如何评价它们 是一个需要深入研究的问题。综合文献【3 6 】中王福豹，史龙，任丰原等提出的7 个 指标，下面讨论几个常用的评价要素。 ( 1 ) 定位精度 定位技术首要的评价指标就是定位精度，一般用误差值与节点无线通信半径的比 例表示，例如，定位精度为3 0 表示定位误差相当于节点通信半径的3 0 。 ( 2 ) 规模 不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个 房间内实现定位，网络覆盖区域可以在定程度上反映其规模。另外，给定一定数量 的基础设施或在一段时间内，可以定位多少目标也是一个重要的评价指标【3 6 1 。 ( 3 ) 信标节点密度 信标节点的位置信息通常依赖人工部署或g p s 获得。然而，使用g p s 定位，信 标节点的费用会比普通节点高两个数量级【3 7 1 ，这意味着即使仅有1 0 的节点是信标 节点，整个网络的价格也将增加1 0 倍。因此，信标节点密度也是评价定位系统和算法 性能的重要指标之一。 ( 4 ) 节点密度 在无线传感器网络中，节点密度通常以网络的平均连通度来表示许多定位算法 的精度受节点密度的影响，如d v - h o p 定位算法仅可在节点密集部署的情况下合理地 估算节点位置。 ( 5 ) 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设备， 但在真实应用场合中误差或失效的问题。因此，定位系统和算法的软、硬件必须具有 容错性和自适应性，能够通过自动调整或重构纠正错误、适应环境、减小各种误差的 影响，以提高定位精度。 ( 6 ) 功耗 功耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节点 电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算量、 通信开销、存储开销、时间复杂性是一组关键性指标。 第一章无线传感器网络节点定位机制 ( 7 ) 代价 定位系统或算法的代价可从几个不同方面来评价。如时间代价包括一个系统的 安装时间、配置时间、定位所需时间；空间代价包括一个定位系统或算法所需的基 础设施和网络节点的数量、硬件尺寸等：资金代价则包括实现一种定位系统或算法 的基础设施、节点设备的总费用。 ( 8 ) 安全定位 由于传感器网络自身以及定位机制均存在固有脆弱性，节点的定位过程很容易 遭受来自内部或外部的攻击。攻击所产生的错误定位结果可能导致网络功能的局部 失效和监测结果出错，进而破坏整个网络应用的有效性。因此，如何为存在敌对可 能的传感器网络应用提供安全的节点定位系统，也是评价定位算法性能的要素之一。 上述要素不仅是评价无线传感器网络节点定位算法的标准，也是其设计和实现的 优化目标。为了实现这些目标的优化，有大量的研究工作需要完成。同时，这些性能指 标是相互关联的，必须根据应用的具体需求做出权衡【3 8 1 ，以选择和设计合适的定位技 术。 第四节无线传感器网络节点定位技术的应用领域 传感器网络节点定位技术为整个网络系统获取大量详实而可靠的监测信息，提 供了网络应用中至关重要的节点地理位置信息。在传感器网络节点定位系统的应用 领域如环境监测、交通管理、现代物流、目标跟踪等应用中，节点的地理位置信息 是非常重要的，甚至直接影响整个网络系统的有效性。无线传感器网络中节点定位 机制及算法的研究有着重要的意义，无线传感器网络中不但有很多特定应用都依赖 于传感器节点或者目标物体的地理位置信息，而且很多网络运行和管理也需要节点 位置信息的辅助，如基于地理信息的路由、资源的有效配置、对外部目标的定位和 追踪、计算网络覆盖范围、控制网络的负载均衡等。 无线传感器网络近年来的发展和应用越来越广泛，以下是一些已经应用在我们 生活中的例子。 1 、森林防火应急监控。目前很多森林的防火监控都是利用无线传感器网络来实 现的，利用传感器网络节点部署在监控区域。通过传感器网络的回传至控制中心的 数据一旦发现有异常情况，便可以通过该节点的相关地理位置信息判断是哪块区域 发生了异常，以便工作人员施行相应的措施。 2 、动物活动追踪。野外动物学家为了能够更加了解其生活习性，有时需要跟踪 福建师范大学钟进发硕士学位论文 某些动物的活动路径，比如一些鸟类的迁徙路径。通过传感器节点固定或者植入该 动物身体的某个部位，并通过该节点周期性地把相关信息回传到基站或者控制中心 便可以得到其活动的路径信息。 3 、贵重文物的实时监控。在一些重要的文物保护单位，一些特别珍贵的文物就 利用传感器网络节点来实时监控，利用该节点的位置信息来判断该文物是否在原来 的位置，一旦节点位置信息有变动就有被盗的嫌疑。在网络节点回传的信息中还有 可能包括该文物的环境温湿度、光照度指标等，些信息方便为工作人员判断这样的 环境是否对该文物有大的影响。 4 、矿井定位系统。矿井的安全问题一直都是矿工人身的最大威胁，在矿井下部 署无线传感器网络节点来监控其周围的环境，比如一氧化碳的浓度，一旦发现某个 网络节点回传的数据有异常，监控系统或者工作人员便可以从该节点的位置信息来 通知相关矿工，以便采取后续措施。文献 3 9 】的实现平台是基于无线射频识别技术 和无线传感网络技术，实现井下工作人员、井下移动设备的三维定位，实现井下巷道工 作环境的各种参数的实时监测、分析并预警数据异常区域。图1 - 6 是矿井中部署的 一个传感器网络监控节点，已经有不少的煤矿进行了成功的井下定位技术应用测试 和示范。 图1 - 6 矿井中的网络监控节点 5 、目标追踪的应用。节点定位技术的应用在目标追踪的过程中为系统提供了重 要的目标位置信息参照，比如目标节点在无线a p ( a c c e s sp o i n t ) 间切换的时候，目标 的位置信息为其在各a p 中的无缝接入有着重要作用。 6 、节点定位技术在智能交通系统中的应用。节点定位技术是提供车辆所处的位 置信息基础，也是智能交通系统的基础信息获取车辆的位置信息可以为道路车辆提 供信息反馈、城内精确导航、目标跟踪等服务1 4 0 。图1 7 节点定位技术在智能交通 第一章无线传感器网络节点定位机制 系统中的应用。 7 、水下无线传感器网络应用。随着无线传感器网络在陆地上应用的成熟，目前， 其应用也拓展到了水下世界，但无论是陆地还是水下的应用，