（控制理论与控制工程专业论文）无线移动自组网中自定位算法的研究.pdf

摘要 无线移动自组网是一种多跳的临时性的自组织网络，它具有动态变化的拓扑 结构、多跳、无中心、移动终端的局限性等特点。目前无线移动自组网已成为移 动通信领域中的一个研究热点，而节点定位问题是无线移动自组网中的一个重要 研究课题。 本文首先阐述了无线自组网中的定位问题包括定位算法的基本原理以及测 量技术等，在此基础上，本文对现有的典型自定位算法进行了分类，着重阐述了 各类中具有代表性的算法及其原理和特点，并提出了自定位算法的性能评价指 标。针对现有的定位系统不能完全摆脱g p s 定位系统或者固定设施的辅助的缺 点，本文提出了一种完全利用自组网中节点本身进行自主定位的局部化定位系 统。 在局部化定位系统中，本文针对无线移动自组网的特点，提出了组的概念， 把整个多跳自组网看作是由若干个单跳自组网所组成，即将整个嘲络看成是由若 干个局部网络所组成，每个局部网络中的节点组成一个组。局部化定位系统的主 要思想是在每个组中建立一个局部坐标系，先确定每个节点在局部坐标系中的坐 标，然后根据坐标转换方法，将网络中所有节点的坐标都统一到一个全局坐标系 中，进而完成了对自组网中所有节点的定位。通过仿真试验，本文分析了局部化 定位系统在不同条件下的性能和代价。 关键字：自组网自定位局部化 a b s t r a c t m o b i l ea dh o cn e t w o r ki sas p e c i a lw i r e l e s sn e t w o r kt h a ti sat e m p o r a r yo n e w i t hc o m m u n i c a t i n ge a c ho t h e ru s i n gd i s t r i b u t e dp r o t o c 0 1 m o b i l ea dh o cn e t w o r kh a s m a n y b a s i c c h a r a c t e r s ，s u c h a s d y n a m i c n e t w o r k t o p o l o g y , m u l t i h o p ， s e l f - o r g a n i z a t i o na n dm o b i l i t y n o wm o b i l ea dh o cn e t w o r ki sw i d e l ys t u d i e di n m o b i l ec o m m u n i c a t i o nf i e l d a n dp o s i t i o n so fn o d ei nm o b i l ea dh o cn e t w o r ki sa n i m p o r t a n c ep r o b l e m ， t h eb a s i ct h e o r i e sa n dt e c h n o l o g i e sa b o u tt h ep o s i t i o ns y s t e mi na dh o en e t w o r k a r ed e s c r i b e di nt h i sd i s s e r t a t i o n ，s u c ha st h eb a s i c p r i n c i p l e a n dm e a s u r e m e n t t e c h n i q u e a n dt h ee v a l u a t i o nc r i t e r i o no ft h ep e r f o r m a n c ea n dt h et a x o n o m yo f s e l f - l o c a t i o ns y s t e m sf o ra dh o cn e t w o r k sa r ea l s od e s c r i b e di nt h i sd i s s e r t a t i o n t h e p r i n c i p l ea n dc h a r a c t e r i s t i c so fs o m et y p i c a la l g o r i t h m s a r ed i s c u s s e d ，a n dt h e d i r e c t i o n so fs e l f - l o c a t i o ns y s t e m sa r ea l s op r o p o s m ap o s i t i o ns y s t e mo n l yu s i n gt h e c o n n e c t i o no fn o d e si na dh o cn e t w o r ki sp r e s e n t e d t h ed i f f e r e n c eb e t w e e nt h i s p o s i t i o ns y s t e ma n do t h e rp o s i t i o ns y s t e m sl i e si nw h e t h e rt h e yn e e dt h eh e l po fg p s o rb a s i cs t a t i o n so rn o t b a s e do nt h ec h a r a c t e r sa fa dh o cn e t w o r k ，t h e “g r o u p ”i d e ai sp r o p o s e di nt h e d i s s e r t a t i o n ，n ew h o l em u l t i h o pn e t w o r ki sd e e m e dt ob em a d eo fl o t so fo n e h o p n e t w o r k s ，i no t i l e rw o r d ，t h ew h o l en e t w o r ki sd e e m e dt ob em a d eo fi o t so fl o c a la r e a n e t w o r k s a l lt h en o d e si nal o c a la r e an e t w o r km a k eu po fag r o u p al o c a la r e a c o o r d i n a t ei sc r e a t e di ne v e r yl o c a la r e an e t w o r k ，a n da l lt h en o d e sa r el o c a t e di ni t s e l f l o c a la r e ac o o r d i n a t e s a c c o r d i n gt ot h et r a n s i t i o no fc o o r d i n a t e s ，t h ec o o r d i n a t e so f a l lt h en o d e sa r eu n i f o r m e di nag l o b a lc o o r d i n a t e ，i n6 t h e rw o r d ，a l lt h en o d e si nt h e n e t w o r ka r el o c a t e d n ep e r f o r m a n c ea n dc o s ta b o u tm o b i l ea dh o cn e t w o r kw i t h p o s i t i o ns y s t e ma r es t u d i e da c c o r d i n gt ot h er e s u l t so fs i m u l a t i o n k e y ：a dh o cn e t w o r k ；s e l f - l o c a t i o n ；l o c a t e d i i 两北工业大学硕士学位论文 第一章绪论 第一章绪论 随着计算机网络技术、移动通信网络技术以及移动终端技术的发展，为移动 用户提供包括可以访问固定网络在内的各种网络的服务已经成为当今一大研究 的热点问题。传统的移动通信网络是集中式控制并依赖于预先部署的基础设施来 运行的，为大家所熟知的蜂窝移动通信网就是传统移动通信网络的典型代表。但 在军事作战、紧急和突发事件的处理、偏远的野外作业等一些特定的场景中，预 先部署基础设施是不现实的。为了弥补传统移动网络的不足，一种不依赖于基础 设施的、可以临时快速组网的移动网络技术应需产生，即a dh o c 网络技术。然 而a dh o c 网络的一些固有特性给网络通信也带来了许多新问题和挑战。在这些 诸多新挑战中，网络节点的定位问题就是其中的一个具有重要的意义研究课题。 1 1h dh o c 网络概述 di - i o a 网络的概念 a dh o c 网络是一种在没有基础设施的条件下，由一组带有无线收发装置的 移动终端通过分布式协议互连并组织在一起的一种临时性无中心的自组网络这 种网络可以随时随地快速的组建，不需要任何基础设施的支持，网络中每个节点 的地位都是平等的。移动终端的无线收发设备具有一定的有效通信范围，节点只 能与处在自己有效通信范围内的其它节点口j 以直接进行通信。如果需要同处于节 点本身有效通信范围之外的其它节点进行通信，就要通过中间节点来转发信息， 因此a dh o c 网络也是一种多跳网络。 同时a dh o c 网络也是一种移动通信和计算机网络相结合的网络，一方面， 网络的信息交换采用了计算机网络中的分组交换机制另一方面，用户终端是可 以移动的终端。a dh o c 网络中，移动终端兼备主机和路由器的两种功能：作为 主机，终端需要运行各种面向用户的应j l j 程序；作为路由器，终端需要运行相应 的路由协议，根据路由策略和路由表参与分组转发和路由的维护工作。当部分通 信网络遭到破坏时，这种分布式控制和无中心的网络结构能够维持剩余部分的通 信畅通，因此a dh o c 网络具有很强的鲁棒性和抗损性。 两北工业人学硕士学位论文第一章绪论 a dh o e 网络的特点 a dh o c 网络与其它传统移动通信网络相比，除了具有有限的无线传输带宽、 移动终端能源的有限性以及低服务质量等特点外还有以下显著特点： 1 、无中心分布式控制 a dh o c 网络中没有中，i i 控制节点的概念，网络中的每个节点的地位都是相 同的平等的，节点之间是通过分布式算法来协调通信的。 2 、动态网络拓扑结构 由于a dh o c 网络中的节点可以自由的移动，而且节点还可以随时加入或退 出网络，因此整个网络的拓扑结构呈现出动态性和不可预测性。 3 、动态连接的服务质量 由于信号的衰减、噪声的干扰以及单向通道等问题的存在节点之间的连接 处于一种不稳定的状态。而且与有线通信网络相比，无线通信网络的丢包率以及 错误率更高一些，因此网络的服务质量趋向于低质量状态。 4 、多跳路由 由于移动终端的有效通信范围有限节点只能与处在自己有效通信范围内的 其它节点可以直接进行通信。如果需要同处于节点本身有效通信范罔之外的其它 节点进行通信，就要通过中间节点来转发信息，这就形成了一个多跳路由网络。 5 、自由移动终端的主动性和局限性 移动终端具有便携轻便的优点，同时也具有c p u 处理能力低、存储空间小 和能源有限等不足，因此一系列的安全措施特别值得考虑如身份认证、信道加 密、密钥管理、访问控制等。 6 、安全性差 a dh o c 网络的固有特点使得它更容易受到主动的入侵、被动的监听、拒绝 服务、剥夺节点的休眠状态等网络攻击。 a d h o c 网络的应用 a dh o c 网络的组嘲快速、无需基础设施等许多优点使其在军用_ 手| l 民用通信 领域中的应用占有了一定的地位，日前主要的应用领域有：军用通信与指挥控制 系统、传感器网络、移动会议、移动网络、紧急和突发场合、野外作业、旅游指 南、交通导航管理系统以硬个人通信等。 两北工业大学硕士学位论文第一章绪论 a dh o e 网络中主要的研究方向 a dh o e 网络特有的一些特点既给实际应用带来了很大的方便，同时也给网 络的设计带来了新的挑战。应用于传统移动网络的各种技术不能直接的用到a d h o e 网络中，一些关键性的技术需要根据a dh o e 网络的特点来专门设计。目前 主要研究的方向有：物理层自适应技术、m a c 层技术、路由协议、传输层协议、 安全技术、网络管理技术、服务质量、可靠性技术以及自定位技术等。 1 2a dh o e 网络中的自定位问题 1 2 1 定位问题 网络节点的移动性是a dh o e 网络的本质特性之一，而位置的管理是针对a d h o c 网络移动性研究最为直接的课题之一。在a dh o e 网络的许多应用中都需要 提供节点的位置信息。 在民用领域中，作为a dh o c 网络技术的应用之的传感器网络1 2 】，具有广 阔的应用领域和市场价值前景。无线传感器网络通过感知、收集各种信息，包括 r f 、温度、湿度、气压、化学、生物等等，进而通过融合分析处理这些信息， 实现战区的防御和侦察、安全监控、环境监控以及目标的识别、跟踪和定位等功 能。但是对于大多数的应用来说，如果不知道是从何时何地感知来的数据是没有 多大意义的，因此每个传感器节点必须明确自己的位置才能说明在什么地方发生 了什么事情，从而实现应用的目的。为了提供有效的位置信息，随机部署的传感 器节点必须能够在布放后实时地进行定位，定位是传感器网络的基本功能之一。 在军事领域中，作为a dh o c 网络技术的应用之一的军用通信网络，具有极 其重要的作战价值。网络节点的位置管理是此通信网络中研究的一大课题。通过 网络节点之间的通信分布在海、陆、空的作战单元可以进行协同作战，而节点的 位置信息是进行协同作战的重要依据。因此网络中节点位置管理也是至关重要 的。 另一个方面，在a dh o e 嘲络中路由i 办议研究是一个核心课题之一，某些路 由协议，如l a r ( l o c a t i o n a i dr o u t i n g ) 1 5 1 1 6 1d r e a m ( d i s t a n c er o u t i n ge f f e c t a l g o r i t h mf o rm o b i l i t y ) 【7 1 以及g e o c a s t t 8 等，都是基于位置信息的路由协议， 这些路由协议根据事件区域的地则位置信息，建立优化路径，避免了洪泛传播方 式，从而减少了寻找和更新路由过程中的开销，提高路由的效率口】【”。 1 两北工业大学硕士学位论文第一章绪论 此外，提供a dh o c 网络中节点的位置信息还可以为网络提供命名空间 1 ，向部署者报告网络的覆盖质量，实现网络的负载均衡以及网 络拓扑的自配置” ，等等。 1 2 2 实现自定位的必要陛 目前应用最为广泛也是最为成熟的定位系统是全球定位系统g p s ( g l o b a l p o s i t i o ns y s t e m ) 【】”，g p s 系统是由2 4 颗人造卫星和3 颗后备卫星组成的可以在 任何时候为全球上的任何地方提供三维绝对坐标的定位系统，它具有定位精度 高、扰干扰能力强、实时性好等优点。但是受成本、功耗、可扩展性和使用环境 等条件的制约，g p s 定位系统不能直接应用于无线自组网中节点的定位。 例如，在传感器网络中的节点存在资源有限、随机部署、通信易受环境干扰 甚至节点失效等特点传感器网络的定位机制必须满足自组织性、健壮性、能量 高效、分布式计算等要求，而不能使用g p s 系统来进行定位。在某些特定的场 合也是无法使用g p s 进行定位的，例如部署在室内的通信网络节点是接受不到 g p s 信号的，因而g p s 失效。在战场环境下，g p s 系统可能会由于受到很强的 干扰信号的影响而无法使用。 结合无线自组网的特点和应用，采用一定的机制与算法实现a dh o c 网络中 节点的自组定位是十分必要的。 1 3 本文的工作 本文研究的无线移动自组网中自定位系统是我们课题组由航空科学基 金( 0 5 f 5 3 0 2 9 ) 和西北工业大学科技创新基金共同资助的“无线移动自组网中关 键技术研究”课题组中的一个重要的研究方向，本文针对课题组的需求以及 在对当前所存在的定位系统进行了综合研究的基础上提出了一种不依赖于g p s 而是完全利用自组网中节点本身进行自主定位的自定位系统m a n l p s ( m o b i l e a dh o cn e t w o r k sl o c a l i z e dp o s i t i o ns y s t e m ) 。m a n l p s 自定位系统主要是针对节 点具有较高性能的自组网络而提出的一个自定位系统，m a n l p s 要求网络中每 个节点都具有测量波达方向d o a ( d i r e c t i o no f a r r i a l ) 和t o a ( t i m eo f a t r i a l ) 的 能力。 在m a n l p s 中，我们提出j ，组( g r o u p ) 的概念，在每一个组中，再选定个 节点作为原点建立局部直角坐标系，仅利用该组内的信息对本组内的所有节点在 两北工业大学硕士学位论文第一章绪论 这个局部直角坐标系中进行定位。最后根据坐标转换的理论把整个网络中的节点 坐标统一到一个坐标系中。从而实现了对整个无线自组网中节点的定位。但在 m a n l p s 定位系统中确定的网络节点坐标只是本网络中的各个节点之间的相对 位置坐标，而不是绝对坐标。当应用需要时，我们可以把此相对坐标很方便地转 化为绝对坐标。 根据理论分析和仿真试验显示，m a n l p s 定位系统主要具有以下优点： 自组性：网络节点随机分布，完全不依赖g p s 以及其它任何基础设旄的辅助 进行定位。 精确性：根据应用的需要，可以适当提高硬件的要求以减少测量误差，提高 定位的精度，满足应用需求。 自适应性：可以适应网络拓扑结构的动态变化。 可扩展性：可以适应网络规模的变化。 实时性：能够及时地更新网络节点的位最信息。 分布式计算：每个节点自主计算自身的位置，不需要其它节点的辅助计算。 与a dh o c 网络中其它自定位系统相比，m a n l p s 定位系统主要具有以f 创新点： 减少了参与某节点定位所需的最少的其它节点的个数，如在二维空间中，定 位某个节点，最少需要3 个其它节点的位置信息而在m a n l p s 中只需要2 个其它节点的位置信息即可。 从对静态网络或者部分静态网络的定位转换为可以为纯动态网络进行定位， 完全实现了自组定位。 1 4 本文的结构 本文共分为五章内容： 第一章主要讲述a dh o c 网络的基本概念，包括a dh o c 网络的定义、特 点、应用以及其中的关键技术等；阐述了a dh o c 网络中定位问题以及自定 位a dh o c 网络中的必要性；最后描述了本文所作的主要工作。 第二章阐述了无线自组网络中的定位问题，包括定位系统中常用的测繁 技术( 距离测量技术和角度测量技术) 、定位算法的几何原理以及几种常见 的定位误差表示方法。 第三章分类介绍了月前典型的定位系统，对其进行了分类，详细阐述了 备类中具有典型代表的定位算法的基本原理：对各类定位系统进行了性能上 5 两北工业大学硕十学位论文 第一章绪论 的比较，同时，提出了定位系统的性能评价标准。 第四章从理论上提出了m a n l p s ，阐述了此定位系统的主要思想和定位 算法，并在此基础上对此定位系统进行了仿真试验，同时分析了此定位系统 的性能，给出了相应的评价。 第五章总结全文并提出了对未来工作的展望。 两北工业大学硕士学位论文 第二章无线自组网络中的定位问题 第二章无线自组网络中的定位问题 移动自组网中的定位技术是一种无线电定位技术，这种技术通常通过测定电 磁波从发送节点到接受节点的信号强弱、传播时间或者是时间差以及信号到达的 方位角等信息来确定接受节点的位置。实质上，就是通过测定电磁波信息，进而 推断出定位所需要的距离或者是角度信息，通过一定的几何原理计算出目标节点 的位置。 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 ) 、t d o a 1 2 2 ( t i m ed i f f e r e n c eo na r r i v a l ) 、t o a ( t i m eo fa r r i v a l ) 、d o a l 2 4 1 ( d i r e c t i o no fa r r i v a l ) 和a o a ( a n g l eo f a r r i v a l ) 。 属于距离测量方法技术的有： r s s i 是已知源节点发出的r f 信号的强度，目的节点根据接受到r f 信号的 强度，计算出r f 信号传播过程中的消耗，利用理论和经验模型将其转化为距离。 这种方法具有低功率、低成本的优点，在试验环境中能表现出良好的性能， 但是在实际的应用环境中，易受现实环境条件的影响，例如温度、障碍物、干扰 信号等，测量出的距离误差比较大，有时可能产生5 0 的误差m j 。 t o a 是通过测量从发射信号到接受到信号的时间差来计算距离的。在参考 文献 2 3 1 中提到了一个简单的基于t o a 测距的方案。如图2 一l 所示节点的 定位部分主要由c p u 模块、无线电模块、扬声器模块和麦克风模块组成。假设 信号波的传播速度为c ，发射信号和接受信号的时间差为出，则两个节点之间的 距离为r a t 。 这种测距法具有测距精度高的优点，但是这种方法要求节点间有精确的时间 同步。 两北丁业大学硕士学位论文 第二章无线自组网络中的定位问题 隆2 - i 便用声波测距 t d o a 是源节点同时发射两种不同的传播速度的信号，目的节点根据这两种 信号达到的时间差以及这两种信号的传播速度，计算出两个节点之间的距离。如 图2 2 所示，源节点同时发送无线射频信号和超声波信号，目的节点记录这两种 信号达到的时刻互和正，这两种信号的传播速度q 和c 2 是已知的，那么目的节 r ，1 ( i 一正) + 辫 点到源节点的距离为： l z l ，。 超甫波 i 仁：j 赶逆”尚价j ，接受舢： 漆 监2 2id o a 测口i 原媸小盥巨 t d o a 测量距离还有另一种表示的方法：通过测得节点a ( ，y 】) 和b ( x ：，y 2 ) 发送的信号( 假设信号的传播速度为c ) 到达节点c ( x 3 ，y 3 ) 的时间差f 来推算出 节点a 和b 距离节点c 的距离之差： 刖= 正i 了丽五y 一再了瓦i i 孑= c 这种方法测距的误差小，有较高的精度，但对硬什的要求比较高并且易受非 视距n l o s ( n o tl i n eo fs i g h t ) l h 题的影响。 章 高 一 两北工业大学硕士学位论文第二章无线自组网络中的定位问题 属于角度涮量方法技术的有： d o a 技术：测量波达方向的方法有很多，其中最为典型的算法是多重信号 分类m u s i c ( m u l t i p l es i g n a lc l a s s i f i c a t i o n ) 算法。其基本原理是利用智能天线 来测量信号的波达方向，从而估计出此信号来自的方向，基本原理如下：如图 2 - 3 ，天线阵列共有n 个性能相同的阵元组成，阵元之间的间距均为d 。共有 m ( m 、： 、 ； 图2 6 c ( l ，j y 。) 3 、双曲线相交法 基本原理：通过测量未知节点到多个锚的距离之差，未知节点一定位于以两 个锚为焦点，到这两个焦点的距离之差等于所测量的距离之差的双曲线上。采用 几条双曲线相交的方法得到未知节点的位置。如图2 7 所示： ； 在二维空间中，锚节点的坐标为( 五，y i ) ，未知节点坐标为( z ，y ) 。未知节点 到锚i 和锚j ( 其中i j ) 的距离之差为d i ，则有： ( 一x ) 2 + ( y 厂y ) 2 d u 2 ( 2 2 9 ) 1 3 卜9 两北工业大学硕士学位论文 第二章无线自组网络中的定位问题 多于三个锚节点参与距离差的测量就可以唯一确定未知节点的位置。 角度定位法 1 、相交圆定位法 基本原理：如图2 8 ，在三角形abc 中，已知a 、b 和c 三点的坐标，以及 觚b d c 和r 翻就可以确定节点d 的位置了。方法如下：已知节点a 和节点b 的坐标、z b d a 以及节点d 所在a b 的那一侧，就可以确定如图2 。9 所示的一个圆。 由此就获得节点d 可能所在的两个位置。同样的节点a 和节点c 以及zadc 、 节点b 和节点c 以及zbdc 都可以确定节点d 可能所在的位置。所有节点d 可能 所在位置的重合点就是节点d 所在的位置。 a bc 图2 8 d ( x a ，y a ，7 7 a ( x o ，y 臣2 9b ( 气，) 一dd ( 屯，) 2 、相交直线定位法 基本原理：如图2 一l o 所示，未知节点采用d o a ( d i r e c t i o n o f - a r r i v a l ) 技术 来确定来自位置己知节点i 的信息的方向噬( 其中i i ，2 ，3 ) ，根据角度 计算公式得到： 是 时一 0 & 。一 嘻 两北工业大学硕士学位论文第二章无线自组网络中的定位问题 t an 球，2 三一 即为： x t a n q y = t a n 僻一只 x t a n 住。y = x 。t a l l d t 一7 。 x t a n q y = t a n q x 整理得： x = b x= 解得： x = ( a 7 a ) 。1 a 7 b l = 上上上 (2二10)xx一 一。 2 3 典型求精定位算法 y y ， j 一 上 ( 2 2 - l1 ) ( 2 2 1 2 ) ( 2 2 - 1 3 ) ( 2 2 1 4 ) ( 2 2 - 1 5 ) ( 22 一1 6 ) 在实际的应用巾，定位系统所需要的参数难免存在误差。这些误差可分为系 统误差和随机误差，u ，采用一定的措施消除系统误差，但是随机误差才i 能完全的 消除，只能采用算法减小这种误差。由于误差的存在，所求的位置可能会出现 i l5 、， q 伽胁 h厂， 干 = 其 a 、， m n 一 一 喁： 咖 啪 k ，。，。l = 6 两北【业大学硕士学位论文第二章无线自组网络中的定位问题 止个。一般情况下，定位系统所获得的参数的个数都会多于所要求的最少个数。 另外，定位算法一般要求解非线性方程组，因此定位问题就转化为非线性方程组 的求解和最优估计的问题。最为常见的求解这类问题的算法有t a y l o r 级数法【2 8 】 和y t c h a n 2 9 法。下面分别来介绍这两种方法： 2 3 1 t a y i or 级数法 t a y l o r 级数法是一种基于t a y l o r 展开的加权最d - - 乘估计的递归算法。这种 方法利用所有的测量参数来提高定位的精度，并且适用于所有的定位系统。基本 原理是：在所求位置的初始估计处利用t a y l o r 公式展开，并忽略二次以及以上项， 线性化原始的非线性方程在每一次递归中采用最小二乘法对偏移量进行估计， 利用此估计值来修改位置估计。并进行多次的递归，使 卉计位置尽量逼近真实位 置，实现所求位置的最优化估计。 设未知节点的真实坐标为( x ，y ) ，锚的坐标为( ，只) ，其中i = l ，2 ，3 n ，n 为参与该未知节点定位的铺的个数，c 为第i 个锚测量的参数值，“为第 i 个锚测量参数的真实值，e 为测量误差，服从零均值的分布其协方差矩阵为 r 。我们定义一个函数建立上述参数之间的关系： f i ( z ，y ，y 。) = 鸬= c i e i i = 1 ，2 ，3 n ( 2 3 1 - 1 ) 设未知节点的初始估计位置为( x u ，y 。) ，误差为正，或- 有： x = 屯+ 正，y = 儿+ 戌 ( 2 3 1 2 ) t a y l o r 级数法的具体步骤如下： ( 1 ) 根据先验信息确定测量值的协方差矩阵r 。 ( 2 ) 在( 吒，咒) 处将f i 用t a y l o r 公式展开，仅展到一级导数为止。有： 一“，寺。正+ 札。憾飞 i = 1 ，2 ，3 n( 231 3 ) 化为矩阵表示形式为： a 5 圭z + e ( 2 31 4 ) 其中 两北工业大学硕士学位论文 第二章无线自组网络中的定位问题 a = ，z = 耋：2 ，。= 三 ，艿= ( 参) 则j 的加权最小二乘估计为： 艿= ( a 7 r 叫a ) 叫a 7 r z( 2 3 1 5 ) ( 3 ) 判断s = + 霹是否小于给定的门限值，如果此值小于门限值，则停止迭代。 最终的估计值为： x = x + 积，y = y 。+ 瓦 ( 2 3l 一6 ) 如果此值大于或者是等于门限值，则继续进行下面计算。 ( 4 ) 迭代计算，把初始位置的估计值重新赋值：无+ 4 - 气，咒+ 戌j 儿，然 后重复第( 2 ) ( 3 ) 步骤。 t a y l o r 级数法的优点是可适应于所有的定位系统，并且可以利用所有的测量 值来提高定位的精确度。但是这种方法也有其固有的缺点：需要先验信息确定测 量值的协方差矩阵而且在每一次递归中都需要进行矩阵的运算，故这种方法的 计算量比较大：另外如果初始位置的估计值与真实值相差较大，迭代的次数就会 很多，甚至是无法趋向于收敛。 2 3 2 y t c h a n 法 y t c h a n 法是基于t d o a 测量距离差的方法提出的一种视距传播环境下的非 递归方式的最大似然估计法。当测量的参数值很小时，能达到c r 下界。根据 锚节点数目n 的不同，可以分为如下两种算法： 1 、n = 3 时，此时可以得到两个t d o a 的测量值，据此可以建立下列关系式： ( ； = 一( 妻：笔i 4 ( ( 乏：) r + 互il ( r 月z ：z 。, - 一k k z ，一+ 足k , j ( 2 3 2 - 1 ) 其中：k ：x ? + ：，r ：如i 再可f 万。 通过求解上述方程式可以得到关于x ，y 的两对解，根据实际中的粗略f 训 1 7 k k 立屯 钆 儿：l 屯 屯 两北工业大学硕士学位论文第二章无线自组网络中的定位问题 选取一个正确的位置来作为估计位置。 2 、n 3 时， y t c h a n 法的基本原理是：二维空间中当锚的个数n 3 时，引入中间变量线 性化原始方程，并利用加权最小二乘法初步估计未知节点的位置；然后利用中间 变量和待定位置之间的确定关系，再次利用加权最小二乘法对待定位置进行更精 确的估计。 设参与某一个未知节点( y ) 定位的锚( 玉，y i ) 的个数为n 个这样就可以得 到n 一1 个独立的时间差，这n 一1 个时间差是距离未知节点( z ，y ) 最近的锚( 设定为 l 号节点) 的信号和其它n 1 个锚的信号到达未知节点( x ，y ) 的时间之差，用t 。来 表示，其中i = 2 ，3 n ：对应的距离之差表示为：= c t i “1 c = 3 + 1 0 8 m s ， 时间的测量误差用点。来表示。上述参数可以建立下列关系： i ，。= 硝+ c 4 i 一2 ，3 n ( 2 3 2 2 ) 利用两点间的距离公式以及距离之差的定义式可得： 瓜i 再而一厄i 再而= 嘴+ c 4 ， ( 2 3 2 3 ) 整理可得： c r 点l + c 2 既2 = ( j t + 七i ) ，2 + l l 互十y i l i y + 1 r t u ( 2 3 2 4 ) 其中： t = 一玉，y = y l - y ，k i = 寄+ 咒2 ，k i = 砰+ y ? ，= ( - x ) 2 + ( y 一y ) 2 引入中间变量的目的是线性化原始方程式。 将上式表示为向量形式为： 缈= h q z 。 ( 2 3 2 5 ) g 墨，iy 2 i 吃i x 3 ，iy 3 i l 妒= 扭n + 吉c 2 n n ( 2 _ 3 2 _ 6 ) b = d i a g ( r ；：，哼，喵) ，n = i n 2 码”n r ，表示s c h u r 乘积。 在实际当中式( 2 3 2 - 5 ) 为x ，y 的非线性方程式，若把r 看作与x , y 独立的变量， 初次估计z 。时，假定未知节点到各个锚的距离都是相等的，均为，此时 z 。= ( a 。t q “e ) “q “h ( 2 3 2 8 ) z 。= ( 嘭吒) 1 旷h ( 2 3 2 - 9 ) c o v ( z 。) = ( 嘭旷1 g o ) 。 ( 2 3 2 - 1 0 ) 卜面利用x , y 和r 中间的确切的关系来改善估计精度：初步得到的估计z 。与 乙1 = x + e i ，z = y + e 2 ，z “= 彳+ e 3 ( 2 3 ，2 1 1 ) 妒。= h 。一g o 。屯 ( 232 1 2 ) 其l = 隧x 菇2 卜= ( ； ，巧怨莩 两北工业犬学硕士学位论文第二章无线自组网络中的定位问题 妒。=【iz2c(：x麓-x1)警ei+e?”i 2(糕x-x；)ke, 艺的最小二乘估计为： z ：= ( 妒。1 晓) 谚y 。1 h z ：的协方差为： c b v ( 艺) 圭( y 。1 ) z = = e + ( i ) 开根号后的符号取决于乙。 妒= c o y ( z ) = c 2 ( ( 口一g 。b _ e 口) q _ 1 ( 曰叫q b 。1 晓曰“) ) 8 。= 。- 岍x + 0 ，、 a 这种方法的优点是计算量小，在视距环境中定位精度高，但是在非视距的环 境中定位精度明显下降。 2 4 几种的常见定位误差表示法 由j 二环境冈素以及设备的影响，测量误差会随机存在。测量值是输入定位算 法的参数值，测祭误差的随机存在必然引起定位误差的随机存在。定位误差是衡 量定位系统好土1 i 的一个重要的指标。采用的测量技术以及定位算法的不同，定位 两北工业人学硕士学位论文第二章无线自组网络中的定位问题 误差也就不同。常用的定位误差表示方法有均方误差法( m s e ) 、均方根误差法 ( r m s e ) 、平均定位误差以及累积分布函数法( c d f ) 等。 1 、均方误差法和均方根误差法 这种方法是最常用的一种定位误差表示法。均方误差法和均方根误差法分别 定义为： m s e = e 【( x x ) 2 + ( y y ) 2 】( 2 4 - 1 ) 厂_ r m s e = 、e 【( x z ) 二+ ( y y ) 2 】 ( 2 4 2 ) 通常用计算得到的m s e 值或者是r m s e 值与c r 界相比较，来评价某种 定位算法的性能的好坏，m s e 反应的是节点的估计位置与实际位置的偏差程 度，但是当估计值存在个别的较大误差时，m s e 会增大，所以m s e 不能很准确 的评价定位算法的性能，故有人提出了用圆概率误差衡量定位算法的性能。 2 、圆概率误差( c e p ) 期望未知节点坐标的估计值( x ，y ) 落在以其真实坐标( x ，y ) 为圆心半径为r 的 圆内的概率为5 0 ，那么称这个半径r 为圆概率误差。c e p 有以下几种估算式( 假 设最 点) ： c e p = o s ，c 口z 竹v ， 詈 0 5 ( 2 4 - 3 ) ( o 6 7 + 0 8 ( 旦) z ) 盯 旦 节点的位置不固定，处于运动状态。 自组网中节点的加入和退出都会给定位带来某种程度上的影响。节点的增加 在_ ；考虑给节点之间无线信号带来干扰的情况下，仍需要定位系统为新增节点进 行定位。这种操作在定位系统对整个网络中的节点位置进行周期性更新时可以完 成，因此节点的加入对整个定位系统的影响不大。相比而言，节点的退出会给定 位系统带来很大的影响，节点的退出会导致与之相邻的节点的邻居节点在数目上 的减少，甚至会造成网络的分割。另外节点的退出对定位的精度和坐标系的建立 也会带来影响。 由于节点的运动，定位系统需要重新计算运动节点的位置，这会增加网络的 通信量和节点的计算量。同时，节点的移动会给定位的实时性和定位的精度带来 更大的挑战。 针对动态自组网的特点，我们提出一种适合动态自组网的自定位系统局 部化自定位系统m a n l p s ( m o b i l e a dh o c n e t w o r k l o c a l i z e dp o s i t i o ns y s t e m