（通信与信息系统专业论文）无线传感器网络中基于多维标度的节点定位算法.pdf

硕士学位论文 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 通常布置在特定的区域完成 一些特定的功能，在军事、环境监测、灾难救援及其他商业领域有着广阔的应用 前景。定位是无线传感器网络诸多应用的基础。因此，定位是无线传感器网络研 究中的热点问题。 本文的研究工作就是围绕无线传感器网络的多维标度定位问题展开。目前提 出的定位算法对测距误差和网络的拓扑结构较为敏感，在较差的网络环境下容易 产生较大定位误差。多维标度作为多变量分析方法的一种，广泛应用于社会学、 数量心理学、统计学等领域。基于多维标度的定位方法是无线传感器网络节点定 位的一个新的研究方向。 以往的多维标度算法以网络连通性为基础用节点最短路径距离估计其欧氏距 离。如果网络拓扑不够理想，测距误差较大，这种近似方法将引入较大的定位误 差。本文探讨了矩阵近似问题在无线传感器网络定位中的应用，并提出了 n m d s l r a ( n o n m e t r i cm u l t i d i m e n s i o n a ls c a l i n g - l o wr a n ka p p r o x i m a t i o n ) 定位 算法。该算法不再使用节点最短路径估计距离，而是通过矩阵低秩逼近方法，充 分利用测得的距离信息构建出网络的相异性矩阵，然后采用非度量多维标度技术 进行定位。算法一方面利用矩阵的低秩逼近得到节点距离矩阵，另一方面利用了 非度量多维标度的对象相异性只需满足单调关系的特性，从而有效的降低了严重 的测距误差对定位精度的影响，提高了算法的环境适应性。 在n m d s l r a 的基础上提出了应用于移动传感器网络的n m d s l r a ( m ) 移 动辅助定位算法。通常定位算法对网络的连通性有一定要求，在稀疏的传感器网 络环境下难以取得令人满意的性能。n m d s l r a ( m ) 通过节点的移动添加虚节点， 增加网络的拓扑约束关系来提高定位性能。 通过仿真分别与m d s m a p ( p o ) 和m a m d s m a p ( p ) 算法进行了比较。结果 显示，本文提出的算法能有效提高定位精度，并且在误差较大和低网络连通度的 环境下表现出较好的健壮性。 关键词：无线传感器网络；多维标度；定位；矩阵近似；虚节点 无线传感器网络中基于多维标度的节点定位算法 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 sc a nb e u s e di nv a r i o u sa r e a s ，r a n g i n gf r o mm i l i t a r y a p p l i c a t i o n t o p e o p l et r a c k i n g a n de n v i r o n m e n tm o n i t o r i n g l o c a l i z a t i o ni sa f u n d e r m e n t a li s s u eo fm a n yw i r e l e s ss e n s o rn e t w o r ka p p l i c a t i o n s i n t h i sd i s s e r t a t i o n ，m u l t i d i m e n s i o n a ls c a l i n g ( m d s ) s e n s o rl o c a l i z a t i o nl e c h n i q u ei n w i r e l e s ss e n s o rn e t w o r k si ss t u d i e d f i r s t ，t h es e n s o rl o c a l i z a t i o na l g o r i t h m s ，w h i c ha r e u s e dt od e t e r m i n es e n s o r s p o s i t i o n s ，a r ee x a m i n e d m o s te x i s t i n gs e n s o rl o c a l i z a t i o n m e t h o d ss u f f e rf r o mv a r i o u sl o c a t i o ne s t i m a t i o ne 玎o r st h a tr e s u l tf r o mr a n g i n ge r r o r s ， c o m p l e xn e t w o r kt o p o l o g i e sa n da n i s o t r o p i ct e r r a i n t h ec h a r a c t e r i s t i c so fm d s a r e e x p l o r e d m d s ，w h i c hi sad a t aa n a l y s i st e c h n i q u e ，h a sb e e np r o v e dt ob ea ne f f i c i e n t l o c a l i z a t i o ns c h e m e h o w e v e r ， p r e s e n tm d sl o c a l i z a t i o na l g o r i t h m si n c l u d i n gm e t r i c m d sa n d n o n m e t r i c - m d s ，w i t h o u ta n ye x c e p t i o n ，m a k eu s eo fs h o r t e s tp a t ha l g o r i t h mi n n e t w o r kt oc o n s t r u c td i s t a n c em a t f i x i nt h a tw a y ，i tc a nu n d o u b t e d l yd e t e r i o r a t et h e 1 0 c a t i n gp e r f o r m a n c eo fa 1 9 0 r i t h mi nc o n d i t i o no fa n i s o t r o p i ct o p o l o g ya n dl o w c o n n e c t i v i t yl e v e l i nt h i sp a p e r ，w es t u d yt h em a t r i xa p p r o x i m a t i o np r o b l e ma n di t s a p p l i c c a t i o ni nw i r e l e s ss e n s o rn e t w o r k sa n di n t r o d u c ean o v e ln o n m e t r i cl o c a l i z a t i o n a l g o r i t h m ，c a l l e dn m d s l r a ，w h i c hb a s e do nm a t r i xa p p r o x i m a t i o n t h ea l g o r i t h m r u n sn o n m e t r i cm d so nt h em a t r i xw h i c hc o n s t r u c t e db ym a t r i xa p p r o x i m a t i o n ，i t c a ne f f e c t i v e l ya v o i dt h en e g a t i v ei m p a c to fd i s t a n c ee r r o ra n da n i s o t r o p i ct o p o l o g y o nl o c a l i z a t i o np e r f o r m a n c e b a s e do nn m d s l r a ，t h en m d s l r a ( m ) a l g o r i t h m ，u s e di nm o b i l es e n s o r n e t w o r k s ，i sp r e s e n t e d t h ec u f r e n tl o c a l i z a t i o nm e t h o d sd e p e n do nt h ec o n n e c t i v i t y o ft h en e t w o r k ，w h i c hl e a d st op o o rp e r f o r m a n c ei ns p a r s en e t w o r k s i nt h ep r o p o s e d a p p r o a c h ， m o r ei n f o r m a t i o na r ea v a i l a b l eb ya d d i n gv i r t u a ln o d e s d u f i n g t h e m 0 v e m e n t w ec o m p a r e do u rw o r kw i t h m d s - m a p ( p ，o ) a n dm a m d s m a p ( p ) v i a s i m u l a t i o nt os h o wt h a to u rw o r kc a np r o m o t el o c a l i z a t i o np r e c i s i o ne f f e c t i v e l y ，a n d m o s ti m p o r t a n t ly ，p e r f o r m sw e l lo nr a n g ee r r o ra n da n i s o t r o p i ct o p o l o g y k e yw o r d s ：w i r e l e 鼹s e n s o rn e t 、o r l 【s ；m u l t i d i m e n s i o n a ls c a l i n g ； s e n s o rh c a l i z a i t o n ； m a t r i xa p p r o x i m a t i o n ；r t u a ln o d e 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 引庞 日期：泖争年，月才日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名：彭鑫 导师签名。氟冶、， l ，产 日期：御矿年r 月矿日 日期：年月 日 硕士学位论文 1 1 项目来源 第1 章绪论 本研究课题来源于国家自然科学基金项目：一类复杂环境下的无线传感器网 络定位算法研究( 批准号：6 0 6 7 3 0 6 1 ) ；湖南省自然科学基金项目：矿井无线传感 器网络移动节点定位与动态轨迹跟踪研究( 批准号：0 6 j j 5 0 1 1 1 _ ) 。 1 2 研究目的及意义 传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 1 1 ，2 】涉及传感技术、网络通信技 术、无线传输技术、嵌入式计算技术、分布式信息处理技术、微电子制造技术、 软件设计技术等多学科交叉的研究领域，具有鲜明的跨学科研究特点。无线传感 器网络虽然与无线自组网( a d h o cn e t w o r k ) 有相似之处，但也存在差别。传感器网 络是集成了监测、控制以及无线通信的网络系统，节点数目更为庞大( 上千甚至上 万) ，节点分布更为密集。由于环境影响和能量受限，节点更容易出现故障。环境 干扰和节点故障易造成网络拓扑结构的变化。通常情况下，大多数传感器节点是 固定不动的【4 1 。传感器节点处理能力、存储能力和通信能力等都十分有限。另外， 传感器节点体积微小，通常携带能量十分有限的电池，且由于节点个数多、成本 要求低廉、分布区域广，部署区域复杂，有些区域甚至人员不能到达。所以相对 于传统无线网络的首要设计目标是提供高质量服务和带宽利用率。传感器网络以 数据采集为中心，首要设计目标是能量的高效利用，这也是传感器网络和传统网 络最重要的区别之一。无线传感器网络的典型应用是部署在特定区域完成环境监 测、目标追踪与定位等功能。在这些应用中，传感器节点把采集到的数据传递给 服务器端处理。为了保证数据的有效性，节点的位置信息往往是必不可少的。 定位是无线传感器网络研究中的关键问题。传感器网络的大多数应用中，采 集到的数据都需要结合节点定位信息才有实际意义。对节点定位技术的研究主要 出于以下几方面的考虑。首先，无线传感器网络采用分层网络协议栈的形式。在 应用层，节点位置信息对定位相关业务是必不可少的。例如，利用传感器网络对 目标定位与追踪，我们必须知道响应节点的准确位置。在网络层，很多通信协议 都要以节点位置信息为基础，例如地理路由协议。其次，由于传感器网络的特殊 布设方式，比如飞机抛撒，我们难以事先获知节点的准确位置。再次，广泛使用 的g p s 定位系统易受非视距传播( n l o s ) 影响无法在室内工作，而且其设备成本 高能耗大不能应用在传感器节点上。此外，定位可以缩短网络初始化过程降低系 统开销和运行成本。 无线传感器嘲络中基于多维标度的节点定位算法 无线传感器网络中的定位包括两个方面：一是对网络外的监测目标定位，确 定目标的位置或坐标，也叫跟踪检测；二是对网络中传感器节点的定位，获取传 感器本身的位置或坐标，即节点的自定位技术和方法。节点的自定位是实现跟踪 监测的基础，也是本文重点研究的内容。 由于无线传感器网络的特殊性，设计合适的定位方案是一个比较棘手的问题。 传感器节点尺寸小，计算资源和能源极大受限，现有网络中的许多技术并不能直 接应用于无线传感器网络。理想的定位系统应当有较小的计算开销和较低的能耗。 传感器网络布设以后，自组织成一个分布式a d - h o c 网络。因此，定位系统还要能 够在缺少基础设施支撑的条件下实现节点自定位，并能运行在任何复杂环境下。 1 3 研究内容 本文主要研究无线传感器网络的基于多维标度技术的分布式定位算法。在分 析研究现有的多维标度定位算法的基础上，针对以往定位算法采用最短路径算法 构建网络节点距离矩阵过程中存在距离误差较大的问题，提出了采用矩阵低秩近 似和非度量多维标度多维标度的定位策略一n m d s l r a 。降低了以往多维标度定 位算法中存在的距离误差过大的问题，提高了算法在复杂环境下的适应性。 本文的另一个研究内容是无线传感器网络的移动定位问题。在前面 n m d s l r a 算法基础上，提出了采用移动辅助定位方案的n m d s l r a ( m ) 定位算 法。该算法通过节点移动补偿网络的拓扑约束，提高定位算法的适应性。 1 4 本文主要工作 本文主要工作如下： 1 介绍了无线传感器网络的基本概念、特点和研究现状。 2 研究了现有的无线网络测距方法和技术，详细分析了现有的定位算法以 及无线传感器定位所面临的问题和解决方案。 3 研究了采用多维标度技术的无线传感器定位算法，研究了矩阵近似方法 在无线传感器网络中的应用，并且提出了新的非度量多维标度定位算法。 4 研究了移动传感器网络定位问题，并提出了适应性较好的移动辅助定位 算法。 1 5 论文结构 全文共分5 个章节，除了绪论部分外其余各章内容如下：第二章主要阐述无 线传感器网络以及几种典型的测距方法。第三章介绍了定位相关的背景信息，详 细阐述了现有的定位算法和定位系统。第四章介绍了应用多维标度技术的无线传 2 硕士学位论文 感器网络定位技术，提出了基于非度量多维标度技术的n m d s l r a 定位算法并 通过实验分析了算法性能。第五章在n m d s l r a 算法的基础上提出了可用于移 动传感器网络定位的n m d s - l r a ( m ) 定位算法，并通过实验研究了算法性能。 图1 1 论文结构 3 无线传感器m 络中坫十多维标度的节点定位算法 2 1 无线传感器网络 第2 章相关研究综述 微机电系统( m i c r o e 1 e c t r o m e c h a n i s ms y s t e m ，m e m s ) 、片上系统( s y s t e mo n c h i p ，s o c ) 、无线通信和低功耗嵌入式技术的飞速发展孕育出无线传感器网络 ( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 【1 ，引。上世纪七十年代，就出现了将传统传感器采 用点对点传输方式连接传感控制器而构成的传感器网络雏形，我们把它归之为第 一代传感器网络。无线传感器网络是新一代的传感器网络，它由部署在监测区域 内大量的廉价微型传感器节点组成，通过无线通信方式形成一个多跳自组织网络。 无线传感器网络以其低功耗、低成本、分稚式和自组织的特点带来了计算领域的 一场变革，具有非常广泛的应用前景，其发展和应用，将会给人类的生活和生产 的各个领域带来深远影响。 首先，无线传感器网络无需布线，大大节省了网络建设成本。其次，传感器 节点可以通过飞机抛撒布设到战场和存在辐射污染等高危险环境中去。再次，无 线传感器节点由电池驱动，可以布置在没有电源或其他基础设施的地区。总之， 无线传感器网络有着广泛的应用范围，它可以大规模布撒在特定区域，每个传感 器节点感知周围信息，比如振动、温度、辐射等其他参数，并且通过不断转发， 将采集到的数据传送到处理中心【3 】。早在越南战争时期，美国军队就在战略要地 部署震动传感器，侦测越南军队的动向。这些传感器被伪装成石块，当感知到 1 4 0 m h z 的震动时会发出无线信号，这应该是无线传感器网络应用的雏形。英国 b p 石油公司成功的将无线传感器网络用于一艘巨型油轮上。总共1 6 0 个传感器， 监控船身的振动，压缩机和引擎，并将数据通过无线链路发送到处理中心，帮助 船上的工作人员准确把握设备运行状态。 图2 1m i c a 2 无线传感器网络的兴起引起了学术界和工业界的极大兴趣。2 0 0 2 年1 0 月 z i 曲e e 联盟形成，这是无线传感器网络发展史上具有里程碑意义的事件。z i 曲e e 规定了无线传感器网络的通信标准。目自订有超过9 0 家企业支持这个标准，其中 4 硕上学位论文 c r o s s b o w 公司在业界居于领先地位。图2 1 是c r o s s b o w 公司的第三代低功耗传 感器节点m i c a 2 。伯克利( u cb e r k e l e y ) 的英特尔研究实验室，伯克利研究中心和 加州大学尔湾分校( u ci r v i n ) 的嵌入式网络传感实验室是学术界具有代表性的研 究机构，他们在无线传感器网研究中均取得了令人瞩目的成绩。 2 1 1 无线传感器节点体系结构 传感器节点通常由传感单元、数据处理单元、数据收发单元、电源单元等功 能模块构成。传感单元由各类传感器及数模转换器件组成，传感器的类型可以根 据特定的应用环境选定，数据处理通常选用低功耗嵌入式微控制器，数据传输单 元主要由相应的通信协议( 主要是m a c 协议) 及低功耗、短距离的无线通信模块组 成。因为需要进行较复杂的任务调度与管理，系统还需要一个微型化的实时操作 系统，加州大学伯克利分校为此专门开发了t i n v o s 【5 1 ，此外还有m i c r i u m 公司的 u c o s i i 【7 】等。电源是影响节点寿命的关键因素。图2 2 描述了无线传感器节点 的结构。除此之外，根据具体应用的需要，可能还会有定位系统、电源再生单元 和移动单元等。 图2 2 传感器节点体系结构【8 l 2 1 2 无线传感器网络体系结构 传感器节点 图2 3无线传感器网络体系结构【8 j 典型的无线传感器网络由传感器节点、汇聚节点( s i n k ) 、因特网或通信卫星、 任务管理节点等部分构成。传感器节点可以通过飞机抛撒、人工埋置等方式任意 5 无线传感器网络中桀于多维标度的节点定位算法 布设在监测区域内，然后自组织成一个网络。每个节点都可以采集数据，并通过 多跳路由把数据传送到汇聚节点，也可用同样的方式将信息发送给其它节点。汇 聚节点直接与因特网或通信卫星相连，实现任务管理节点( 即观察者) 与传感器之 间的通信。用户通过管理节点对传感器网络进行配置和管理，发布监测任务以及 收集监测数据。图2 3 描述了无线传感器网络的基本体系结构，但是针对特定的 应用环境，无线传感器网络的体系结构有所不同。 2 1 3 无线传感器网络协议栈 根据网络的体系结构和具体应用范围的不同，传感器网络的协议层次也不完 全相同。迄今为止，还没有形成标准的协议栈。最典型的情况是自下而上包括物 理层、数据链路层、网络层、传输层、应用层。另外，协议栈还包括能量管理平 台、移动管理平台和任务管理平台。如图2 4 ( 口) 所示： ( 口) ( 6 ) 图2 4无线传感器网络协议栈【1 l 物理层：负责提供简单而健壮的信号调制和无线收发技术。 数据链路层：负责介质访问控制( m a c ) 和差错控制。 网络层：负责路由协议发现和维护，是无线传感器网络的重要协议层，也 是目前研究的热点之一。 传输层：负责将传感器网络的数据提供给外部网络，比如因特网。 应用层：包括一系列基于监测任务的应用软件。 能量管理平台：管理传感器节点如何使用能源，在各个协议层都需要考虑 能量因素。 移动管理平台：监测并注册传感器节点的移动，维护到汇聚节点的路由， 使传感器节点能动态跟踪其邻居的位置。 任务管理平台：在一个给定的区域内平衡和调度监测任务。 图2 4 ( 6 ) 是在上一种协议栈的基础上经过改进得到的另一种协议栈模型。 6 一 网络管理 一 一 能量安伞移动 一 硕士学位论文 2 2 节点测距方法 2 2 1 无线信号强度 基于接收信号强度指示( 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 ) 的定位中，已 知发射节点的信号发送强度，接收节点根据收到的信号强度，计算出信号的传播 损耗，然后利用经验模型或理论模型用传输损耗来计算节点的距离。 使用经验模型的定位方案进行定位之前，在定位区域内选取若干测试点，记 录在这些点上各基站收到的信号强度，建立在各个点上的位置和信号强度关系的 离线数据库。实际定位时，根据测得的信号强度和数据库中记录的信号强度进行 对比，将信号强度均方差最小的那个点的坐标作为节点的坐标。为提高精度，可 将多次测得的值取平均值，也可以取均方差最小的几个点计算这些点的质心。采 用该信号传播模型可使算法具有较高的精度，但是要预先建立位置和信号强度关 系数据库，当基站移动时要重新建立数据库。 0 口 i l o 唇 孥2 0 蝤 心 越垦3 0 0 口 i 2 0 督 擎舶 鲻 心 j ! 坚 接收端功率n ：1 51 01 5柏2 5 距离( i ( m ) 接收端功率n = 2 f j o 0 要1 0 篓珈 喾i 3 0 辎 呻、4 0 船5 0 接收端功率n = 1 5 r 51 01 52 02 53 0 距离( k m ) 接收端功率n = 2 5 l 、 一 51 01 52 02 551 01 52 02 5 距离( k m )距离( k m ) 图2 5 无线信号衰减图 无线信号在自由空间传播过程中，一个重要特性就是信号强度与传播距离呈 指数衰减。只要知道发送端的发射功率和无线信号衰减模型，接收机就可以根据 信号衰减估计信号的传播距离，这就是基于理论模型的无线信号强度指示( r s s i ) 测距技术。通常无线射频芯片都提供了读取r s s i 的功能，因此r s s i 测距对硬件 要求最低。r a p p a p o r t 对无线信号传播特性作了深入研究【19 1 ，提出了自由空间中 的无线信号传播模型： p ) = 学筹 ( 2 1 ) 说明了接收到的信号功率与传输距离的函数关系。其中p ，是发送功率，g 是发送 7 无线传感器网络中堆f 多维标度的节点定位算法 端的天线增益，g ，是接收机天线增益，是系统损耗，a 是波长。图2 5 表示甩取 值从1 到2 5 的无线信号功率水平随距离衰减图。 由于多径传播( m u l t i p a t h ) 、衰落( f a d i n g ) 等因素影响，无线信号传输的理论模 型方法不如经验模型精确，但是可以节省费用，不必提前建立数据库，在基站移 动后不必重新计算参数。哈佛大学m o t e t r a c k 定位系统【1 8 l 就是一个基于r s s i 技 术的室内定位方案。 2 2 2 信号传播时间 传感器节点之间的距离可以通过测量信号从发送端到达接收端所用的时间和 信号传播速度估计出来。这种测距方法可以采用多种不同的信号，比如：无线射 频信号、声波信号、红外线等等。这就是信号到达时间测距技术一t o a ( t i m eo f a r r i v a l ) 【2 0 1 。t o a 可以通过网络中精确的时钟同步实现。 全球定位系统( g p s ) 【6 j 就是采用这种测距技术。每一颗导航卫星发送的信号都 有其特定的编码方式。信号传到用户端之后会在本地创建一个信号的副本，然后 接收端会根据接收到的信号编码自动调整本地时钟，我们把这个过程称为锁定 ( l o c ko n ) 。接收端锁定一颗导航卫星之后，能够精确判定信号的到达时间，然后 减去信号的发射时间就可以计算出信号传播时间。 通过测量不同通信媒介信号的到达时间差也可以估计收发双方的距离，这就 是信号到达时间差测距( t d o a ：t i m ed i f f e r e n c eo fa r r i v a l ) 。例如，在传感器网络 中可以通过测量超声波信号和无线射频信号的到达时间实现测距功能。超声波和 无线信号的传播速度存在极大差异。因此，我们可以用无线射频信号作为同步的 基准，而用超声波测量两个节点之间的距离。这用测距技术已经应用在美国麻省 理工学院( m i t ) 的c r i c k e t 【1 7 】定位系统和加州大学洛杉矶分校( u c l a ) 的a h l o s 【2 1 l 定位系统中。 虽然t o a 技术可以提供精确的测距功能，但是在节点距离相对较近的传感器 网络中，必然要求传感器节点具备极高的时钟同步能力，这样会带来额外的系统 开销。 2 2 3 利用网络连通性测距 利用无线传感器网络的连通性可以估计节点之间的距离。通常节点通信覆盖 范围可以近似看作以通信距离r 为半径的圆形区域。如果节点f 和f 可以直接通 信，我们可以判定f 和f 的距离d ( f ，f ) s 厂。如果节点f 和f 不能直接通信，那么可 以采用最短路径算法求得f 和，之间的一条最短路径，然后利用平均每一跳的距离 和跳数求出最短路径的长度作为节点之间距离的估计。 如果网络布设在复杂地形条件下，节点的通信覆盖范围可能极不规则，这样 容易导致对节点距离的估计产生较大误差。但是采用网络连通性估计距离无需添 8 硕： ：学位论文 加额外的设备，降低了系统开销。 2 2 4 节点距离的估计 对于一个无线传感器网络，令y 是所有节点的集，节点个数为，一m ，a 是锚节点集。节点f 的真实位置为p ( f ) ，测得的位置为p ( f ) ，定位误差 e ( f ) ：；( f ) 一p o ) 。节点f 和_ 的真实距离为d ( f ，j ) ，测量距离为孑( f ，j ) ，且 孑( f ，j ) 一孑( _ ，f ) ，测距误差e ( f ，j ) = 孑( f ，j ) 一d “，歹) ，a ( f ，j ) 一怯( f ) 一；( 州i o 假设孑( f ，_ ) 、 孑( f ，_ ) 和a ( f ，j ) 的联合概率密度函数为厂，可知： 6 ( f ，j ) 一a 唱m a x 厂( d o ，j ) ，d ( f ，j ) ，d ( j ，f ) ld o ，_ ) )( 2 2 ) 6 ( j ) 是对真实距离d ( f ，j ) 的估计。假设p ( f ) ，e ( f ，j ) 和e ( 歹，f ) 是独立高斯随机变量， 即 e ( f ) 一( 0 ，巳) ， e ( 1 ，j ) ；( 0 ，吼盯) 并 且 e ( j ，f ) 一( o ，吼声) 。由 于 v r a r 孑o ，j ) 1 一v a r f e o ) 1 + v a r f e ( _ ) 1 ，因此d “，j ) - ( d o ，歹) ，幻p ) 。6 ( f ，j ) 是d ( f ，j ) 的最 大似然估计，可得： ；否而1 n 厂( d o ，歹) ，d o ，j ) ，d ( j ) i 6 0 ，) ) o( 2 3 ) 不难得到： 盟掣+ 堕蝴+ 盟蝴：o ( 2 4 ) 厶up u 蛔 u d j i 不难求出： 6 ( f ，护墅趟业尝掣塑喾幽 ( 2 5 ) ( 】m l o d 镕+ 2 0 夕m i + z 0 口o d 2 3 小结 本章主要介绍了无线传感器网络及其研究现状和几种典型的节点测距方法， 包括无线信号强度、信号传播时间和网络连通性。最后，阐述了无线传感器网络 中节点距离估计的数学模型。 9 无线传感器网络中基于多维标度的节点定位算法 第3 章无线传感器网络定位理论 无线传感器网络定位算法存在着多种分类方法，本章详细阐述了无线传感器 网络定位算法的基本理论，包括定位算法的几种分类方法、定位算法的性能评价 指标、基本的定位方法以及典型的定位算法和系统，最后介绍了无线传感器网络 定位过程中所面临的问题。 3 1 无线传感器网络定位算法分类 目前已提出多种定位算法和系统，他们各自基于不同的技术模式。但是对无 线传感器网络定位算法的分类还没有统一的标准，通常依据算法的技术特点进行 分类。本节阐述了几种常见的无线传感器网络定位算法的分类方法。 3 1 1 基于测距( r a n g e - b a s e d ) 和( r a n g e f r e e ) 不基于测距的定位算法 基于测距( r a n g e - b a s e d ) 的定位算法在定位过程中需要测量传感器节点之间的 欧氏距离，并以此为依据估计节点的位置；不基于测距的定位算法( r a n g e f r e e ) 在定位过程中不需要获知传感器节点问的距离，而是利用网络的连通性来获得节 点的相对位置。 r a n g e - b a s e d 定位算法中常用的测距技术有无线信号强度指示( r s s i ) 、信号到 达时间( t o a ) 、信号到达时间差( t d o a ) f 2 1 l 和到达角度( a o a ：a n g l eo f a r r i v a l ) 【14 1 。 通常无线射频芯片都具备了读取r s s i 的能力，因此这种测距技术不用给节点添 加额外的设备，降低了硬件开销而且功耗较低，但是容易受到环境因素的影响，误 差较大。t o a 需要网络节点能够实现精准的时钟同步，因此会带来额外的系统开 销。t d o a 降低了t o a 对同步性能的要求，但是对非视距传播( n l o s ) 等因素较 为敏感。a o a 对系统的天线有较高要求，因此增加了硬件复杂度，也容易受到环 境的影响。除了各种测距技术自身固有的局限性外，r a n g e - b a s e d 定位机制还要使 用其它方法减小测距误差对定位精度的影响，比如反复测量、迭代求精，这些算 法都会增加计算开销。所以在对精度要求不是很高的场合中往往采用r a n g e f r e e 定位算法。 目前提出的r a n g e f r e e 定位算法主要有两类，一种是首先对未知节点和信标 节点之间的距离进行估计，然后利用三边测量法或极大似然估计法进行定位；另 一种是通过邻居节点和信标节点确定包含未知节点的区域，然后求出这个区域的 质心作为未知节点的坐标。r a n g e f r e e 定位算法精度虽低，但仍然能够满足很多 应用需求。质心定位【9 1 、d v h o p 【13 1 、a m o r p h o u s 【2 2 1 、a p i t 【16 1 、凸规划( c o n v e x p o s i t i o n ) 【1 0 】和m d s m a p 【2 3 】是典型的r a n g e f r e e 定位算法。 1 0 硕上学位论文 3 1 2 绝对定位与相对定位 绝对定位要求定位算法能够求出传感器节点或是目标的物理位置，而相对定 位通常以网络中部分节点为参考，建立整个网络的相对坐标位置。绝对定位可以 为网络提供唯一的命名空间，受节点移动性影响较小，应用领域非常广泛。但是 在实际工作中，某些应用，比如地理路由( g e o r o u t i n g ) ，无需知道节点的绝对位 置，而只要知道节点之间的相对位置即可。相对定位不需要锚节点，有其特定的 应用领域。大多数定位算法都可以实现绝对定位，比较典型的相对定位算法和系 统主要是s p a ( s e l f p o s i t i o n i n ga l g o r i t h m ) 【1 1 1 ，l p s ( l o c a lp o s i t i o n i n gs y s t e m ) 【2 4 1 ， 此外m d s m a p 定位算法可以依据实际情况实现绝对定位和相对定位。 3 1 3 集中式与分布式定位 集中式定位是指把所需信息传送到某个中心节点，如服务器或汇聚节点，并 由该节点进行位置计算的定位方式。分布式定位是指通过节点间的信息交换和协 调，由节点自行计算位置的定位方式。 集中式定位的优势在于从全局统筹规划，计算量和存储量不受节点硬件条件 的限制，可以获得较精确的定位估计。不足之处在于与中心节点位置较近的节点 会因为通信流量过大而消耗更多电能，导致整个网络与中心节点通信的中断，此 外这种定位方式无法保证实时性要求。分布式定位算法则在各个节点进行，整个 网络的流量与计算量分布能够保持一个较为均匀的水平。凸规划和m d s m a p 等 算法都属于集中式定位算法。 无线传感器网络的各种应用要求定位系统采用不同的信息采集和计算策略。 其网络架构即可以是分布式的a d - h o c 网络也可以是集中式网络。当前的定位算法 研究工作主要是针对分布式a d - h o c 网络展开的。在集中式网络中，节点采集数据 然后传送到数据处理中心，因此所有节点测得的距离和位置信息在处理中心统一 运算，这样有助于提高定位精度。 3 1 4 粗粒度与细粒度 依据定位所需信息的粒度可将定位算法和系统分为粗粒度定位技术和细粒度 定位技术两大类。根据信号强度或时间、信号模式匹配( s i g n a lp a t t e mm a t c h i n g ) 等来度量与锚节点距离的称为细粒度定位技术：根据与锚节点的接近度来度量的 称为粗粒度定位技术。一般而言，细粒度的定位技术大部分是r a n g e - b a s e d ，还可 细分为基于距离和方向性测量两类；粗粒度通常是r a n g e f r e e 的，其原理是利用 某种物理现象来感知是否有目标接近一个已知的位置。 无线传感器网络中綦于多维标度的节点定位算法 3 2 性能评价指标 无线传感器网络自身定位系统和算法的性能直接影响其可用性，如何评价， 是一个需要深入研究的问题。下面讨论几个常用的评价标准。 ( 1 ) 定位误差和定位精度。定位技术首要的评价指标就是定位精度，一般用定 位误差与节点无线射程的比值表示。例如，定位精度为2 0 表示定位误差相当于节 点通信半径的2 0 。还有一些定位系统，将二维空间划分为网格，然后用网格的 大小衡量定位精度。 ( 2 ) 可定位节点的覆盖度。指可定位的节点占所有节点的比例。 ( 3 ) 锚节点密度和部署。锚节点密度是指锚节点个数占总节点数的比例。锚 节点往往通过人工部署或g p s 定位，导致其成本远高于普通节点。因此，锚节点 密度也成为定位算法和系统的重要指标。 ( 4 ) 节点密度。在w s n 中节点密度增大不仅意味着网络部署费用的增加，而 且会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平 均连通度来表示。许多定位算法的精度受节点密度的影响。 ( 5 ) 容错性和自适应性。通常，定位系统和算法在真实应用场合中常会有多径 传播、衰减、非视距、通信盲点等问题；网络节点由于周围环境或自身原因( r 如电 池耗尽、物理损伤) 而出现失效的问题，而且物理维护或替换传感器节点往往不可 行。因此，定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能够通 过自动调整或重构纠正错误，适应环境，减小各种误差的影响以提高定位精度。 ( 6 ) 功耗。功耗是对w s n 的设计和实现影响最大的因素之一。由于传感器节 点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的 计算量、通信开销、存储开销、时间复杂性是一组关键性指标。 ( 7 ) 代价。定位系统或算法的代价可从几个不同方面来评价。时间代价包括 一个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或 算法所需的基础设施和网络节点的数量、硬件尺寸等。成本代价则包括实现一种 定位系统或算法的基础设施、节点设备的总费用。 以上7 个性能指标不仅是评价无线传感器网络自定位算法和系统的标准，也 是研究工作的着力点和设计和实现的优化目标。同时，这些性能指标是相互制约 的，必须根据应用的具体情况做出取舍，以设计适用于特定领域的定位方案。 3 3 基本定位方法 大多数定位方法都是先估计未知节点和锚节点之间的距离或角度，然后通过 一些几何算法实现定位。因此，距离估计、角估计和几何关系往往是定位算法的 基础。本节主要介绍基本的定位技术。 硕士学位论文 3 3 1 信号到达时间差 如果锚节点和待定位节点之间没有精确的时钟同步，而锚节点之间具备同步 能力，那么可以采用信号到达时间差( t d o a ：t i m ed i f f e r e n c eo fa r r i v a l ) 【2 5 j 定位， 又称为双曲线定位。这种定位技术的原理是，估计出两个参考节点信号到达未知 节点的时间差，可以确定未知节点在以两个参考节点为焦点的双曲线上。只要有 第三个节点就可以确定待定位节点的位置。 假设有尺个锚节点，位置分别为( ，儿) ，七一1 ，2 ，尺。未知节点到锚节点之 间的距离为 以。t ；( 一五) 2 + ( 咒一y i ) 2 ( 3 1 ) 以第一个锚节点为参考节点，则其他锚节点的信号在未知节点的到达时间差为 h f ，一一( 忙一l ，p 一j 1 ) y ( 3 2 ) 式中：r 一2 ，3 ，r ； ，为信号传播速度。待定位节点( 砟，外) 到锚节点的距离满足 ( 昂一再) 2 + ( 蚱一m ) 2 一( 嵋) 2( 3 3 ) 将( 3 3 ) 写为矩阵形式，可得a y 一6 ，其中 a 。 三兰三二；三二三二：二乏 ，y 。r 昂) ，_ 嵋- r ，6 i 。，2 ， 2 一2 一( v f 2 1 ) 2 ； 2 一2 一( y k 。) 2 根据最小二乘法可得待定位节点的位置估计：夕t 似7 a ) 。1 a r 6 。 3 3 2 信号到达角度 a o a ( a n g l eo fa r r i v a l ) 是一种估算邻居节点信号发送方向的技术。天线阵列 或多个接收器的结合可以估计信号发送端到接收端的角度，并且通过简单的几何 关系就可以实现对信号发送端的定位。a o a 定位系统的实现要依赖于智能天线技 术。智能天线是与数字信号处理器相连的天线阵列。智能天线能够结合发散增益、 天线增益并且抑制干扰，有效提升了无线信道容量。除定位外，还能提供节点的 方向信息，如m i t 的t h ec r i c k e tc o m p a s s t 项目就采用多个接收器的a o a 硬件解 决方案，其原型系统可在4 0 。角内以5 。的误差确定接收信号的方向。同样，a o a 技术也受外界环境影响，如噪声、n l o s 问题等都会对测量结果产生不良影响。 同时，a o a 需要额外硬件，可能无法用于硬件尺寸和功耗受限的传感器节点。 3 3 3 三边测量法 三边测量法( t r i l a t e r a t i o n ) 通过测量待定位节点到三个锚节点的距离来判定其 一。 1 。垂竺丝矍堂里丝兰窒耋垒丝丝堑竺丝堡垒童童丝丝型二。；。一 位置。如图3 1 所示，己知a 、b 、c 三个锚节点的坐标分别为( 葺，魏) 、( x z ，y z ) 、( 而，y ，) ，