（通信与信息系统专业论文）基于rangebased的无线传感器网络定位算法研究与改进.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 在无线传感器网络中，位置信息对传感器节点的监测活动至关重要，不包含位置 信息的监测报告通常作用有限。另外，无线传感器网络的一些协议比如基于地理信息 的路由也需要定位信息作为支撑，因此节点定位问题是无线传感器网络的重要研究内 容。 通常按照是否需要预先通过测量来获得节点之间的距离( 或角度) 信息，把节点定位 算法分为基于测距的定位算法和无需测距的定位算法。论文是围绕两种基于测距的定 位算法：基于r s s i 的定位算法和d v - d i s t a n e e 定位算法展开研究的。首先，论文对无 线传感器网络节点定位技术进行了概述，介绍了与节点定位相关的概念、分类方式及 测边定位的基本原理。 其次，对基于r s s i 的定位算法进行了深入研究和仿真分析，该算法对节点的硬件 要求低，实现简单，但是容易受锚节点稀疏、测距误差及通信功率有限的影响而导致 定位覆盖率和定位精度不理想，为此，论文提出了一种分级迭代协作定位算法。该改 进算法采用协作定位方式来提高定位覆盖率，通过加入锚节点位置优选策略和分级设 置邻居节点数量阀值来减少定位误差，m a t l a b 仿真表明，分级迭代协作定位算法相 比传统的基于r s s i 定位算法，具有更高的定位覆盖率和定位精度。 再次，论文针对d v - d i s t a n c e 定位算法由于利用节点间多跳累积跳段距离表示欧式 距离从而导致定位误差较大的问题，提出了一种进行循环迭代修正计算的改进算法。 通过仿真，论文比较了改进的d v - d i s t a n c e 定位算法和传统的d v - d i s t a n c e 定位算法的 性能，结果表明改进的d v - d i s t a n c e 算法提高了定位精度，且在继承了传统d v - d i s t a n c e 算法高定位覆盖率同时，还能更好地适应各向异性的网络结构，但是，改进算法的通 信开销和计算量还有待改进。 最后，论文对相关研究工作进行了总结，并对未来的研究工作进行了展望。 关键词无线传感器网络；定位算法；基于测距；r s s i ；d v - d i s t a n c e 西南交通大学硕士研究生学位论文第1 i 页 _ 一1 1 a b s t r a c t i nw i r e l e s ss e n s o rn e t w o r k s ( w s n ) ，l o c a l i z a t i o ni n f o r m a t i o no fs e n s o rn o d e sa r c e s s e n t i a lf o rw s n m o n i t o r i n g ，s e n s e dd a t ai sa l w a y sm e a n i n g l e s sw i t h o u tr e l a t m gt o i t s p h y s i c a ll o c a t i o n i na d d i t i o n , s o m em i d d l e w a r es e r v i c e ss u c ha sl o c a t i o na i d e dr o u t i n gn e e d l o c a l i z a t i o ni n f o r m a t i o n t h e r e f o r e ，i ti sv e r yi m p o r t a n tt og a i nl o c a l i z a t i o no fs e n s o rn o d e a u t o m a t i c a l l y g e n e r a l l yp o s i t i o n i n ga l g o r i t h mi sd i v i d e di n t or a n g e - b a s e da l g o r i t h ma n dr a n g e - f l e e a l g o r i t h ma c c o r d i n gt ow h e t h e ri t n e e d sp h y s i c a lm e a s u r e m e n tt oo b t a i nt h ei n f o r m a t i o n a b o u tt h ed i s t a n c eb e t w e e nt h en o d c so rn o t t h et h e s i sf o c u s e so nt h er a n g e - b a s e da l g o r i t h m o fr s s i - b a s e dp o s i t i o n i n ga l g o r i t h ma n dd v - d i s t a n c ep o s i t i o n i n ga l g o r i t h m f i r s t ，t h et h e s i s s u m m a r i z e sn o d ep o s i t i o n i n gt e c h n o l o g yo ft h ew s n ，a n dt h e nm a i n l yi n t r o d u c e sn o d e p o s i t i o n i n g - r e l a t e dc o n c e p t sa n dt e r m i n o l o g y , c l a s s i f i c a t i o na n dt h eb a s i cp r i n c i p l e so f m e a s u r e m e n te d g ep o s i t i o n i n g s e c o n d l y , t h er s s ia l g o r i t h mi sd e e p l yd i s c u s s e da n ds i m u l a t i o na n a l y z e di nt h i st h e s i s t h ea l g o r i t h mr e q u i r e sl o wn o d eh a r d w a r ea n di t s i m p l e m e n ti ss i m p l e h o w e v e r t h e a l g o r i t h mi sv u l n e r a b l et ot h ei m p a c to ft h es p a r s ea n c h o rn o d e s ，r a n g i n g e f r o ra n d c o m m u n i c a t i o np o w e r , w h i c hr e s u l t e dp o s i t i o n i n gc o v e r a g ea n dp o s i t i o n i n ga c c u r a c yn o t i d e a l s ot h i st h e s i sp r o p o s e sah i e r a r c h i c a li t e r a t i v ec o o p e r a t i v ep o s i t i o n i n ga l g o r i t h m n l e i m p r o v e da l g o r i t h mu s e sc o o p e r a t i v em e t h o dt oi m p r o v ep o s i t i o n i n gc o v e r a g ea n da d o p t s p o s i t i o no p t i m i z a t i o ns t r a t e g yo f t h ea n c h o rn o d e sa n dg r a d m gs e t st h et h r e s h o l do f n e i g h b o r n u m b e rt or e d u c ep o s i t i o n i n ge r r o r m a t l a bs i m u l a t i o ns h o w st h a tt h ei m p r o v e da l g o r i t h m h a sah i g h e rp o s i t i o n i n gc o v e r a g ea n dp o s i t i o n i n gp r e c i s i o nt h a nt h et r a d i t i o n a lr s s i a l g o r i t h r r l t h i r d l y , t h ed v - d i s t a n c ep o s i t i o n i n ga l g o r i t h mi sf u r t h e rs t u d i e da n ds i m u l a t i o n a n a l y z e d d u et ot h ea l g o r i t h ma d o p t sm u l t i - h o pd i s t a n c ei n s t e a do fi n t e r - n o d ee u c l i d e a n d i s t a n c e ，i tr e s u l t sb i g g i s hp o s i t i o n i n ge r r o r i no r d e rt os o l v et h i sp r o b l e m ，t h et h e s i s p r o p o s e sa ni m p r o v e dd v - d i s t a n c ea l g o r i t h m , w h i c hr e f i n e si n i t i a lp o s i t i o n i n gr e s u l t sb y i t e r a t i o nc a l c u l a t i o n c o m p a r e dw k ht h et r a d i t i o n a ld v - d i s t a n c ea l g o r i t h m , p o s i t i o n i n g p e r f o r m a n c er e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mi m p r o v e sp o s i t i o n i n ga c c u r a c y , i n h e r i t st h et r a d i t i o n a ld v - d i s t a n c ea l g o r i t h me x c e l l e n tp o s i t i o n i n gc o v e r a g e ，a n da l s ob e t t e r t oa d a p tt ot h ea n i s o t r o p yo ft h en e t w o r ks t r u c t u r e h o w e v e r , c o m m u n i c a t i o no v e r h e a da n d c o m p u t a t i o no f t h ei m p r o v e da l g o r i t h ms h o u l db ei m p r o v e d f i n a l l y , t h ew o r k o f t h i st h e s i si sc o n c l u d e da n df u t u r er e s e a r c hw o r ki sp r o s p e c t e d k e y w o r d sw i r e l e s s s e n s o rn e t w o r k s ；p o s i t i o n i n ga l g o r i t h m ；r a n g e - b a s e d ；r s s i ； d 弘d i s t a n c e 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 无线定位通常是指利用无线定位终端通过对无线电波信号进行测量，再根据一组 参考节点提供的辅助信息，从而确定某物体在设定的坐标系中的位置。无线定位技术 是保障人类日常生活和生产活动的一项重要技术，在现代社会中发挥着越来越重要的 作用。 1 1 课题的背景及意义 近年来，随着信息技术持续向高性能、低成本、普适计算和智能化等方向的高速 发展，人类社会和国民经济的各个领域日趋数字化、智能化，特别是受到高度重视的 物联n ( y h ei n t e r n c to f t h i n g s ，i o t ) 技术在日常生活中的广泛运用，使得人们对无线定位 服务的需求日益剧增【1 1 。其中，对于物联网典型应用的无线传感器网络( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 来说，能否获得节点的定位信息是至关重要的。无线传感器网络最初 是由美国军方提出，由于其具有电池供电、机动部署、自组织组网、不依赖固定设施 等特点，使其在战场监控、灾难监测、预防与救援、生态环境监测、先进制造、医疗 健康、紧急事件响应、建筑物安全监控、精细农业等领域中有着不可替代的作用【23 1 。 而在上述这些实际应用中，传感器节点的位置信息都是不可或缺的一部分。因为用户 仅仅知道发生什么事件而不知道事件发生地点是毫无意义的。比如，在森林火灾监控 系统中，火灾在哪里发生与仅仅知道有火灾发生有着质变的意义。在医疗监护中，仅 仅知道有病人需要紧急救护而不知道其具体位置将严重影响抢救时间。另外，传感器 节点位置信息的获得还可以用于协助路由、网络拓扑的自配置和实现网络功率控制等1 4 5 】 o 目前，无线传感器网络节点定位技术作为w s n 应用领域中重要的核心支撑技术之 一，对其的研究已经得到国内外学者和机构的高度重视【6 1 。但是，由于无线传感器网络 节点数量规模庞大，节点通过抛洒随机部署，节点计算、存储容量、通信能力及电池 能量有限等一些特征，使得基于w s n 的节点定位研究面临着诸多挑战，虽然很多其他 领域的定位技术也相对成熟，但是一般无法直接应用于无线传感器网络【7 】。如全球定位 系统( g l o b a lp o s i t i o ns y s t e m 。g p s ) 成本和能耗高，而且g p s 对于一些特定环境，如水下 或室内是无法使用的，这些因素都限制了g p s 在无线传感器网络中大规模的应用【8 】。 因此，必须针对无线传感器网络节点的低成本、低能耗和通信能力有限的特点，设计 精度高、分布式、复杂度低和容错能力强的定位算法来获取节点位置信息。 西南交通大学硕士研究生学位论文第2 页 1 2 无线传感器网络定位技术国内外研究现状 1 9 9 6 年，美国e 9 l l 定位需求的颁布宣告了无线定位的起源。目前，随着物联网 技术以前所未有的速度向前发展，无线传感器网络定位技术作为在该应用领域中一项 不可或缺的支撑性技术，也同样受到了国内外学者的高度重视，并且已经取得了丰富 的研究成果。通过检索国内外的学术期刊和会议，有大量关于w s n 定位技术的研究论 文，同时，许多的机构和公司也在开展与无线传感器网络定位相关的研究项目，其中， 比较有代表性的项目有a t & tc a m b r i d g e 的c r i c k e t 项目【9 】，微软的e a s yl i v i n g 项目【l o 】 以及g e o r g i at e c h 公司的s m a r tf l o o r 项引1 1 j 等。 在定位算法的研究方面，国外学者提出了许多经典的定位算法。如在基于 r a n g e b a s e d 定位算法的研究方面，y e d a v a l l i 等人在“s e q u e n c e b a s e dl o c a l i z a t i o n i n w i r e l e s ss e n s o rn e t w o r k s ”论文中提出的一种新颖的基于序列的w s n 定位算法 ( s e q u e n c e b a s e dl o c a l i z a t i o n , s b l ) ，该算法首先利用r s s i 的大小来对空间的区域进行 划分，建立一个位置顺序表，然后根据r s s i 的测量值来进行匹配定位，s b l 算法可以 大大的减少节点定位的计算量【1 2 1 。d r a g o sn i c u l e s c u 等人在 a d h o cp o s i t i o n i n gs y s t e m s ( a p s ) ”和 d vb a s e dp o s i t i o n i n gi na d h o cn e t w o r k s ”论文中提出的利用距离矢量路由和 g p s 定位的原理的一系列分布式定位算法，其包括6 种算法，分别为d v - h o p 、 d v - d i s t a n c e 、d v - e u c l i d e a n 、d v - c o o r d i n a t e 、d v - b e a r i n g 和d v - 黜l d i a l 【1 31 4 1 。 c h r i s s a v a r e s e 等人提出了两种循环求精定位算法，即c o o p e r a t i v er a n g i n g 定位算法和 t w o p h a s ep o s i t i o n i n g 定位算法【1 6 】。除此之外，还有许多的学者和研究组织提出了很 多有研究价值的成果。 在国内，尽管对w s n 定位技术的研究起步稍晚，但随着我国政府对物联网的推进 和高校及研究机构对w s n 定位技术研究的重视，从事无线传感器网络定位研究的人数 正在迅速增加。目前，国内的研究内容主要为经典定位算法的改进和定位技术的应用 等，主要的研究和开发单位为清华大学、北京大学、西安交通大学、上海交通大学、 复旦大学、东南大学、北京邮电大学、电子科技大学、西南交通大学、北京交通大学 等高校。国家发改委的下一代互联网c n g i 项目和国家9 7 3 基础项目“无线传感器网络 的基础理论及关键技术研究”集中了国内多个实力雄厚的研究团队重点攻关，力求取得 具有国际影响力的理论成果。 国内学者对w s n 定位算法的研究也取得了不错的成绩，在国内外刊物发表了大量 的研究成果。如在基于r s s i 的定位算法研究方面，任维政等人提出了一种基于r s s i 的测距差分修正定位算法，通过利用离未知节点最近的锚节点的信息来对r s s i 测距值 进行差分修正，从而实现提高定位精度【1 7 】。杜亚江等人通过利用锚节点间的相互协作， 提出了一种基于最小二乘法的r s s i 测距环境参数修正方法，提高了r s s i 测距的精度， 取得了良好的定位性能【l8 1 。在d v - d i s t a n c e 定位算法研究方面，熊少英等人针对 西南交通大学硕士研究生学位论文第3 页 d v - d i s t a n e e 算法不适用于各向异性网络的缺点，通过设置约束条件，排除一些误差较 大的锚节点组合，然后利用质心算法估计最终坐标值，从而提高d v - d i s t a n c e 在各向异 性网络环境下的定位精剧1 9 1 。付华等人在d v - d i s t a n e e 定位算法中，将锚节点间的真实 距离与这些锚节点问的跳段距离之和的比值作为修正权值来提高定位所需距离值的精 确度，达到了提高定位的精度目的【2 0 】。 尽管国内外研究人员对w s n 定位研究取得了很大的进展，提出了许多w s n 节点 定位算法和开发了一些实用定位系统，但是由于w s n 定位与具体应用有很大联系，根 据具体应用的需要，所选用的定位算法和定位方案会有所不同，这也给我们留下了很 大的研究和改善的空间。 1 3 论文研究内容和组织安排 论文主要围绕无线传感器网络中基于测距的定位算法展开，分析了无线传感器网 络经典的定位技术，然后着重研究并改进了基于r s s i 的定位算法和d v - d i s t a n e e 定位 算法，并利用m a t l a b 进行了性能仿真评估。 第l 章绪论部分。主要介绍了无线传感器网络定位技术的研究背景和研究意义， 然后分析了w s n 定位技术在国内外的研究现状，最后阐述了论文的主要研究内容和论 文基本结构。 第2 章无线传感器网络定位基本理论。首先介绍了无线传感器网络节点定位技术 所涉及基本术语和概念，概述了现有的几种具有代表性的节点定位算法的分类；然后 阐述了几种典型的基于测距的定位算法，并且就如何衡量无线传感器网络定位算法的 几个性能指标予以介绍和给出量化公式。 第3 章仿真环境概述和测边定位理论分析。首先对m a t l a b 仿真中的模拟环境、 网络拓扑结构及仿真标识进行了设定，然后阐述了测边定位的数学原理，介绍了利用 冗余锚节点信息来减少测距误差影响的方法；最后利用m a t l a b 对利用冗余锚节点信 息提高定位精度的方法进行了仿真验证。 第4 章基于r s s i 的定位算法的研究与改进。阐述了基于r s s i 的定位算法的基本 思想及实现步骤，并对其在不同网络拓扑下的性能进行了仿真分析。针对基于r s s i 的 定位算法在锚节点稀疏、测距误差影响及通信功率受限时，定位精度和定位覆盖率较 低的问题，提出了分级迭代协作算法，并进行了性能的仿真分析。 第5 章d v - d i s t a n c e 定位算法的研究与改进。阐述了d v - d i s t a n c e 定位算法的基本 思想及实现步骤，并对其在不同网络拓扑下的性能进行了仿真分析。针对d v - d i s t a n c e 定位算法利用节点间多跳累积跳段距离表示欧式距离从而导致定位误差较大的问题， 提出了一种进行循环迭代修正的改进算法，并对其性能进行了仿真分析。 第6 章结论与展望。对全文内容进行了回顾总结，结合已有工作中的不足之处提 西南交通大学硕士研究生学位论文第4 页 出了对下一步工作的展望。 本章小结 本章首先阐述了课题研究的背景和意义，然后介绍了国内外对无线传感器网络定 位技术的研究情况，其中着重阐述了基于r s s i 定位算法和d v - d i s t a n c 圮定位算法的研 究情况，最后介绍了论文的主要的研究内容和组织结构。 西南交通大学硕士研究生学位论文第5 页 第2 章无线传感器网络定位基本理论 2 1 无线传感器网络定位基本概念与术语 在无线传感器网络定位过程中，通过配备g p s 定位设备或手工配置等方式预先获 得位置信息的节点，被称为锚节点( a n c h o rn o d e ) ，如图2 1 所示，节点2 、3 为锚 节点，其在网络中所占比例很小；除了锚节点外，就是未知节点( u n k n o w nn o d e ) ， 如节点u ，、n 。等，其不能预先获得自身位置信息7 2 1 2 2 1 。我们研究定位技术的目 的就是为了通过利用已知位置信息的锚节点，根据一定的算法获得未知节点的位置。 n o d e o 图2 1 无线传感器网络示意图 无线传感器网络定位技术中的基本术语： 邻居节点( n e i g h b o rn o d e s ) ：对于一个传感器节点，如果在其无线通信半径 范围内，存在一些能与其直接通信的节点，就称这些节点为该传感器节点的邻居节 点，如节点，、2 、，为节点u 。的邻居节点； 连通度( c o n n e c t i o nd e g r e e ) ：包括节点连通度和网络连通度两种含义。节点 连通度是指某个节点通信覆盖区域的邻居节点个数，如节点u ，的节点连通度为3 ； 网络连通度也称作网络密度，它是网络中所有节点的邻居节点数目的平均值，反映 了传感器节点配置的密集程度【2 3 】； 跳数( h o pc o u n t ) ：指两个节点之间的跳段总数，如节点u 。到节点的跳 数为3 ； 跳距( h o pd i s t a n c e ) ：指两个节点之间的各跳段距离之和，如节点u 到节点 玑的跳距为3 + 2 + 2 = 7 ； 2 2 无线传感器网络定位方法的分类 无线传感器网络定位方法按所需的测量技术、定位形式、定位效果或实现成本等 西南交通大学硕士研究生学位论文第6 页 不同【2 4 2 52 6 1 ，通常有如图2 - 2 所示几种类别： 无线传感器网络 定位算法 是否测量节点之 间的距离或角度 处理的待定位节 点先后顺序不同 是否在定位过程 中使用锚节点 根据不同的 定位结果 ( r 蕊a 雌o - l m 。d ) 峪( r , m g e 驯- f r 。) ( c 淼o m u a m 呲) l | 0 淼m m 。m u g ) i i ( 戮m r , h o r b s * dil 震( a n e h o 嚣r - f i , 。) 怍划符若 定位算法i l定位算法i i 定位算法| i 定位算法| | 定位算法 | i 定位算法ll ”；嚣“l i “釜“ l lll li) | fii 一l i 图2 2 无线传感器网络定位算法分类示意图 除了上面公认的分类以外，还有如被动定位2 7 3 ( p a s s i v el o c a l i z a t i o n ) ，干涉定位 2 s ( r a d i oi n t e r f e r e n c el o c a l i z a t i o n ) ，移动传感网络定位算法【2 9 】等定位算法。 2 3 基于测距的定位算法概述 基于测距( r a n g e b a s e d ) 定位算法是通过测量未知节点与锚节点之间的距离或角 度，然后利用上面介绍的节点位置计算方法来估计出未知节点的位置。其常用到的测 量技术有：信号强度指示( 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 ) 、方位角测量( a n g l e o f a r r i v a l ，a o a ) 、到达时间( t i m eo f a r r i v a l ，t o a ) 及到达时间差( t i m ed i f f e r e n c e o f a r r i v a l 。t d o a ) 。 1 基于信号强度指示的定位【3 0 3 1 】 无线电波在空间的传输过程中信号强度是按一定的规律衰减的。在自由空间中， 距离发射节点d 米处的节点接收到的信号强度可以由理论模型式( 2 1 ) 给出【3 2 】： p ( d ) = e , g ，g ，2 2 ( 4 万) 2d 2 l ( 2 - 1 ) 式中，z 为发射节点处发射信号功率，只( d ) 是在距离d 处的接收功率，q 、g ，分 别为天线增益，三为与传播无关的系统损耗因子，五为无线电波波长。当未知节点获 得了足够多邻居锚节点的信号强度衰减信息后，就可以估计自身与锚节点之间的距离， 然后利用三边测量法或者最大似然估计法可计算出未知节点的位置。 2 基于到达时间的定位 无线电波在自由空间中是以一定的速度( c = 3 1 0 s m s ) 传播，如果获得了某个节 点发射信号到达邻居节点的时间，就能够得到对应节点之间的距离，即 r f = c x t f ，= 1 , 2 ，以 ( 2 2 ) 式中，足为节点间的测量距离，t 为无线电波传播时间。如果同时测量到信号在 未知节点与3 个或以上邻居节点间的传播时间，就可以建立t o a 定位方程组，然后求 解方程组就可以定位出未知节点【3 3 】。 t o a 定位的典型应用就是g p s 定位系统，但是当该技术运用在w s n 中时，由于 西南交通大学硕士研究生学位论文第7 页 需要锚节点与未知节点之间有非常精确的同步时钟，对于节点成本和功耗受到限制的 无线传感器网络，这一点实现起来是相当困难，也就决定了基于t o a 定位在w s n 中 是不可行的。 3 基于到达时间差的定位 基于到达时间差的定位是通过检测不同信号( 如无线电波和超声波) 到达未知节 点的传播时间差，而不是像t o a 定位一样测量到达的绝对时间来确定未知节点的位置， 降低了时间同步要求【3 4 1 。t d o a 定位无需同步锚节点与未知节点的时间，只需在网络 节点部署完成后，实现锚节点之间的时间同步，由于锚节点在整个w s n 中所占的比例 很小，因此实现t d o a 的时间同步比t o a 代价要小。t d o a 定位精度高，易于实现， 在w s n 将会有较多的应用。目前，基于t d o a 的定位技术已经在飞行器导航、卫星 定位等多个领域得到了广泛应用【3 5 1 。 4 基于方位角测量的定位 基于a o a 的定位是利用测量的到达角实现定位。该方法通过接收节点天线阵列测 出发射节点的无线电波的入射角，从而构成一条从接收节点到发射节点的径向连线， 即方位线，发射节点位于方位线上，在不考虑噪声影响的情况下，两条或两条以上方 位线的交点即为发射节点的位置【3 6 】。 基于a o a 定位需要天线阵列或多个接收器，硬件系统设备复杂，并不适用于对成 本敏感的大规模w s n 。而且a o a 定位需要2 节点之间存在视线传输( l o s ) ，即使是 在l o s 传输为主的情况下，无线传播的多径效应依然会干扰a o a 的定位。 2 4 无线传感器网络定位算法评价标准 衡量无线传感器网络定位算法性能有多个指标，如可用性、自组织性、实时性、 功耗、规模、精确度、覆盖率等。这些性能指标是相互联系的，一个定位算法很难在 有效减少节省网络节点数量和降低功耗的同时获得较高的定位精度和覆盖率，实际应 用中必须根据相应的定位需求进行取舍【3 73 8 1 。接下来，我们将本论文中重点考察的几 个无线传感网络定位算法性能指标予以介绍和给出量化计算公式： 1 定位精度 定位精度是定位算法最重要的指标，定位精度越高，技术要求越高，成本也越高。 定位的精度通常由定位误差来表示，分为相对定位误差和绝对定位误差。绝对定位误 差是指未知节点实际估测的位置和节点真实位置之间的距离值，计算方法见式( 2 3 ) 。 广_ 。= _ - - - _ p 舢厶= 。一矗) 。+ 侈。- y 。) 2 ( 2 3 ) 式中，( x 。，y 。) 为节点，l 的实际坐标，( 叠。，多。) 为定位算法估计出的未知节点坐标。 相对定位误差一般用估计位置与实际位置的距离与节点通信半径r 的比值来表 示。计算方法见( 2 - 4 ) 。 西南交通大学硕士研究生学位论文第8 页 ：盟100(2-4)aerror =卫 1 0 0 ” 尺 由于w s n 中各个节点的定位误差并不相同，为了相对公平地评价定位算法的性 能，通常把所有节点的定位误差求平均值作为该算法的平均定位误差。显然，平均定 位误差越小，说明该算法的定位精度越高，该算法越好。在本论文中，我们选择平均 定位误差来衡量定位精度。平均定位误差计算方法见式( 2 5 ) ， 一e r r o r l 一) 2 + 皖叫) 2 e r r o r = 二= ! 一= 2 生一 ( 2 5 ) nn 式中，为已经定位出来的未知节点数量。 2 定位覆盖率 定位覆盖率是用已经被定位的未知节点的数量与未知节点总数的比值来表示。该 指标的计算方法见式( 2 6 ) ， 删r = 二l 一l 0 0 ( 2 6 ) 彳l ln o d e sn u m a n c h o r sn u m 式中，为已经定位出来的未知节点数量，a l ln o d e sn u m 为网络中节点总数， a n c h o r sn u m 为网络中锚节点总数。对于一个定位算法，就是在保证一定定位精度的 前提下，尽可能多地实现未知节点的定位，定位覆盖率越高越好。 3 锚节点密度 锚节点通常靠配备g p s 装置来获得位置信息，其成本比普通节点要高的多，所以 要尽可能使用较少的锚节点实现更精确的定位。 4 功耗 在无线传感器网络中，节点通常是通过电池提供电力的，能量十分有限，所以在 保证一定要求的定位精度和覆盖率前提下，要充分考虑定位算法的算法计算量、通信 开销等关键性指标，从而降低节点定位时的功耗。 5 容错性 在无线传感器网络的实际应用中，通常会存在着多径传播、非视距传输、噪声干 扰等问题，而且节点也会因为自身和周围环境等原因而导致不能正常工作，所以无线 传感器网络定位算法需要具有很强的容错性，即定位算法通过自身的调整，能够纠正 错误，从而减小各种误差带来的影响。 本章小结 本章首先介绍了无线传感器网络节点定位技术所涉及基本术语和概念，接着概述 西南交通大学硕士研究生学位论文第9 页 了现有的几种具有代表性的节点定位算法的分类，然后阐述了几种典型的基于测距的 定位算法，并且就如何衡量无线传感器网络定位算法的几个性能指标予以介绍和给出 量化公式。 西南交通大学硕士研究生学位论文第1 0 页 第3 章仿真环境概述和测边定位理论分析 3 1 仿真环境概述 在无线传感器定位算法的仿真分析中，m a t l a b 软件是较好的仿真工具。 m 棚，a b 能模拟定位算法仿真环境，完成定位算法的测试，并能完成算法性能的分析。 本论文全部采用了m a t l a b 对定位算法进行性能验证，下面设定的仿真条件和网络标 识适用于论文中所有章节。 3 1 。1 仿真模拟网络环境设置 m a t l a b 用于w s n 定位算法的仿真是以整个无线传感器网络的行为作为模拟对 象，而不是以网络中单个节点作为仿真单位f 3 9 】。所以，需要首先要模拟一个无线传感 器网络环境，对仿真环境进行设置，以便能模拟仿真定位算法的运行，才能更好地完 成算法性能的分析。根据无线传感器网络及论文研究的定位算法的特点，在m a t l a b 模拟的网络环境中，需要对节点及无线传感器网络做如下设置： 1 无线传感器网络节点部署在2 维的平面区域上，这样未知节点自身定位时仅需 3 个锚节点的位置和距离信息就可以完成定位； 2 网络中节点都具有相同的通信能力、存储能力和计算能力等，节点通信模型采 用自由空间电波传播模型，所有节点具有相同的通信半径灭，即节点的辐射范围是以 自身为圆点，以尺为半径的圆； 3 无线传感器网络节点能够搜索到其邻居节点，邻居节点间可以互相通信； 4 节点之间的连接是双向的，网络节点间具有对称的通信能力，并且所有的消息 最终都能被正确接收； 5 锚节点通过配备g p s 接收器或人工部署已经实现定位，其他节点的位置未知， 需要通过相关定位方法实现定位。 3 1 2 仿真模拟的网络拓扑和标识 在无线传感器网络的实际应用中，网络节点的部署通常是随机的，为了仿真实验 的结果能更全面的反映实际的情况，在本论文的m a t l a b 仿真中，选用了两种类型的 仿真网络拓扑结构：各向同性网络和各向异性网络【删。对于这两种网络形式，它们的 定义如下： 西南交通大学硕士研究生学位论文第11 页 对于一个无线传感器网络，存在函数以可以将空间中任意两点置和x 的距离 用p 驴表示为岛= ( z ，x j ) e 4 1 1 。如梨存在这样的函数使得p 扩正比于空间两节点 五、x j 的欧氏距离，这种网络称之为各向同性网络。反之，对于全部网络节点若不 存在这样的函数关系，就称这种网络为各向异性网络。 论文选用如图3 - 1 所示的方形区域进行各向同性网络的仿真， o 亏魏乏 蛰? $ 0 o1 1 5 02 0 02 s 00 鲫i 曩熏臻翳 0卯1 1 2 2 5 d3 图3 - i 各向同性的网络结构仿真示例图 如图3 2 所示的c 形区域进行各向异性网络的仿真。 c 形区域节点分布示例圈 三 , 5 0t 鳓拣 1 隧一 图3 2 各向异性的网络结构仿真示例图 在这里主要针对第4 章和第5 章的仿真实验的标识进行约定。在上面的两个节点分布 图中，用星号表示锚节点：菱形表示待定位的未知节点。 如图3 3 所示的定位节果图中，用星号表示锚节点；菱形表示定位过程结束后， 无法被定位的未知节点：圆圈表示定位出来的未知节点，其后面的直线表示定位误差， 直线越长定位误差越大。 铷 期 抛 伽 伽 o 西南交通大学硕士研究生学位论文 第12 页 毒 定位结果示例图( c 形区域) ；凝；气二 漤善秘+ 雾零 蠹q 0 0 。0 ：翌三兰趋竺全 图3 3 仿真定位结果示例图 3 2 测边定位的数学原理与测距误差分析 测边定位方法是无线传感器网络定位中应用最为广泛的方法，该方法能够利用相 对简单的方式来确定未知节点的大概位置，下面对它的数学原理进行阐述【4 2 1 。 3 2 1 三边定位的计算方法 已知在2 维平面中，有3 个锚节点，位置坐标分别为( t ，只) ，i = 1 ，2 ，3 ，未知节点的 坐标为( x 。，几) ，与3 个锚节点的距离为，i = 1 ，2 ，3 ，如图3 4 所示。 、 4 ) 、 j j ! ， 。 = 8 ，y = 2 )， 、， 、， 、- - 一一一一， 图3 4 三边定位实例 根据距离计算公式，可以建立如下方程组： “一x 。) 2 + 抚一y 。) 2 = ，；2 ，o = 1 ，2 ，3 ) ( 3 1 ) 现在可以利用线性代数的方法来求解上面的非线性方程组。首先，要把它转换成 狮 瑚 俩 伽 o 湖 黜 瑚 伽 佃 o 西南交通大学硕士研究生学位论文第13 页 关于屯和儿的线性方程组，消除二次项和y ：。因此，我们把前面2 个方程分别减去 第3 个方程，得到下面的方程组： f 受二王蓄2 一蠢一三j 1 2 2 + 夏j 2 ：一蠢勒2 = ：2 一r 2 c 3 彩 【g ：一屯) 2 一( 秘一黾) 2 + ：一y 。) 2 一仳一儿) 2 = 考一芎 分别展开，再合并整理后得到： f 2 g ，一而) 屯+ 2 ，一y ly u = ( ，1 2 一芬) 一g ? 一x ；) 一i 2 一露) 1 2 沁一x ：k + 2 ，一陟。= ( 七一孑) 一g ；一工；) 一( y ；一y ；) 式( 3 3 ) 可以写成如式( 3 - 4 ) 的线性方程组： 2 x , x y l l xl = 隧蕊黜二劫 ( 3 3 ) ( 3 - 4 ) 这样就可以求出未知节点坐标( 毛，儿) ，在图3 - 4 所示的例子中，4 ：( 而，乃) = ( 2 , 1 ) ， 鸣：( 而，儿) = ( 5 ，4 ) ， ：( 而，乃) = ( 8 ，2 ) ，未知节点与它们的距离分别为吒= 而，= 2 ， 气= 3 ，于是有： 2 h 斟圈 协5 ) 所以可以解得未知节点的坐标为( 吒，儿) = ( 5 ，2 ) 。 3 2 2 测距误差的影响与抑制方法 2 匪= 计篙麓麓卜) 矗一x ly 。一y 1 1fg 2 一e ) 一k 一) 一撕一y ：) 彳= 2 l ； ； i ，b = i ； i k x 州y n - - y 剃j【- r 2 n _ i 一砰) 一雠。一) 一坛一) j 西南交通大学硕士研究生学位论文第14 页 下面我们将通过m a t l a b 仿真来验证分析上述方法的有效性。 3 3 测距误差抑制方法的仿真分析 仿真环境：仿真区域为l m l m 的单位方形区域，未知节点位于仿真区域的中心位 置，真实坐标值为( 0 5 ，0 5 ) ；全部锚节点采用随机分布，位置坐标值为 ，”) 且为真实 值不存在误差，相应的到未知节点的测量距离为，带有伪随机噪声误差岛。全部采 用最4 x - 乘法求解未知节点的估计坐标值h 3 1 。 图3 5 测距误差抑制方法仿真实验示例图 图3 5 示例了有1 2 个随机分布锚节点的分组进行定位的仿真。其中，“，表示锚节 点，o ”表示未知节点的真实位置，“x ，表示不同的测距误差下，估计的未知节点坐标， “口”是所有位置估计坐标值的平均值，这些约定同样适用于后面的章节。 仿真1 ：不同锚节点数的定位分组效果比较 在图3 - 6 中，分别给出了锚节点数为3 、6 、1 2 、3 5 个的不同定位分组，在测距误 差都为5 0 的情况下，每个定位分组在同一种节点布局下仿真5 0 0 0 次的定位结果。从 图3 - 6 右半部分的仿真结果图中可以看出，定位结果坐标值覆盖区域以真实坐标为中 心进行收敛。在相同测距误差下，随着参与定位的锚节点数量的增加，区域也越小， 表示定位估计值越接近真实值，即定位误差减少了。 1 厶n c h or s1 厶n c h or s 西南交通大学硕士研究生学位论文第15 页 i ii _ _ _ _ _ _ _ _ - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ - _ 1 0 8 0 6 吒 呈o 4 o 2 0 6a n c h or s 00 2 0 8 0 6 v 皂0 4 0 2 0 5a n c h o r s o 4o 6o 81o0 2 x ( 口0 1 2a n c h o r s 3 5