（模式识别与智能系统专业论文）室内定位算法的改进及其应用研究.pdf

摘要 摘要 随着无线通信技术的发展，人们对定位业务的需求越来越多，特别是对室内 定位的需求。然而，由于室内环境的特殊性，如拐角及障碍物较多，多径衰落非 常严重，非视距传播普遍存在等，使得室内定位技术成为新的研究热点和难点。 本文对现有的定位技术进行了分析和研究，尤其对基于z i g b e e 的室内定位 技术进行了分析和研究，主要开展了以下几个方面的研究： 第一，提出了基于接收信号强度r s s i 和链路质量l q i 的测距模型，该模型 减小了信号波动带来的距离误差。 首先比较了现有的无线信号传播损耗测距模型中的经验模型和确定性模型， 从定位的精确度和快速性等方面综合考虑，本文采用了经验模型中的简化模型， 并对其进行了如下的改进：通过大量的实验数据研究了r s s i 和l q i 之间的相关 性，提出了改进的基于r s s i 和l q i 的测距模型。实验结果表明，该模型的测距 性能要优于单变量模型，减小了信号波动给测距过程带来的距离误差，具有定位 精确度高的优点。 第二，提出了用改进的卡尔曼滤波器( k f ) 对测距模型中的r s s i 信号值和 l q i 信号值进行滤波的方法，该方法减小了信号中的噪声干扰以及非视距误差。 针对测距模型中使用的r s s i 值和l q i 值中存在噪声干扰、非视距( n l o s ) 误 差等问题设计了改进的卡尔曼滤波器，对检测到的信号进行处理，并对滤波前后 的波形图进行了比较，结果表明，改进后的卡尔曼滤波器可以较好的减小信号传 播过程中引入的噪声干扰，尤其是在n l o s 环境下，可以减小信号中存在的n l o s 误差，达到了较好的滤波效果。 第三，对所提出的基于r s s i 和l q i 测距模型的定位算法进行了仿真。 在m a t l a b 7 6 环境下搭建了仿真平台来模拟室内环境下的无线定位网络，进 行了仿真实验来验证所提出算法的可行性以及定位性能的优劣，并分析了信标节 点数目的增加对定位精确度的影响，仿真结果表明，改进后定位算法的定位精确 度有了明显的提高，通过增加信标节点的布局密度可以提高系统的定位性能。 第四，在t i 公司的硬件平台c c 2 4 3 1 z d k 上实现了所提出的定位算法。 在i a r 环境下编写了相关的定位算法程序，并通过z - l o c a t i o n 软件下载到 t i 公司的硬件平台c c 2 4 3 1 z d k 上，最终实现了所提出的定位算法，并分析了信 标节点数目的增加对定位精确度的改善。该硬件平台主要包括信标节点，待定位 节点和路由节点。实验结果表明，改进后的定位算法比硬件自带定位算法的定位 精确度有所提高。 关键词：室内定位；r s s i ；l q i ；k a l m a n 滤波器 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fw i r e l e s sc o m m t m i c a t i o n t e c h n o l o g y , p e o p l en e e dm o r e a n dm o r el o c a t i o n b a s e ds e r v i c e ，e s p e c i a l l yt h ei n d o o rl o c a t i o nb a s e d h o w e v e r , d u e t ot h es p e c i a lc h a r a c t e r i s t i c so ft h ei n d o o re n v i r o n m e n t ，s u c ha sc o n s t r a i n e ds p a c e ， c o m e r sa n db a r r i e r s ，t h ea t t e n u a t i o no fs i g n a lt r a n s m i s s i o n ，t h ef a d i n go f m u l t i p a t h , t h ee x i s t i n go f n o n l i n e o f - s i g h t , t h er e s e a r c hm e t h o do fi n d o o rl o c a t i o nt e c l u l o l o g yi s t o t a l l yd i f f e r e n tf r o mo u t d o o rl o c a t i o nt e c h n o l o g ya n db e c o m e san e w 肌dd i f f i c u l t r e s e a r c hf i e l d t h i sp a p e ri n t e n d st oa n a l y z et h ee x i s t i n gp o s i t i o n i n gt e c h n o l o g y , i np a t t i e u l a r , t h ei n d o o rp o s i t i o n i n gb a s e do n z i g b e e t h er e s e a r c hm a i n l yf o c u s e so nt h ef o l l o 、加n g a s p e c t s ： 1 t h em o d e lb a s e do nr s s ia n dl q ih a sb e e na d v a n c e d ，w h i c he l i 面n a t e s d i s t a n c ee r r o r sc a u s e db yt h ef l u c t u a t i o n so fs i g n a l f i r s to f a l l ，i tm a k e sac o m p a r a t i v e s t u d y o ne x p e r i m e n t a lm o d c la 1 1 d d e t e r m i n i s t i cm o d e lw i t h i nt h ee x i s t i n gw i r e l e s s s i g n a lp r o p a g a t i o nl o s sm o d e l s c o n s i d e r i n gt h ea c c u r a c ya n ds p e e d ，i tu s e st h es i m p l i f i e dm o d e lo fe x p e r i m e 删 m o d e la n di m p r o v e st h es i m p l i f i e d m o d e l t h r o u g hl o t so fe x p e r i m e n t a ld a 饥i t s t u d i e st h er e l e v a n c eo fr s s ia n d l q ia n da d v a n c e st h em e a s u r e m e n tm o d e lb 2 l s e do n r s s ia n dl q i t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h em o d e li ss u p e r i o rt ot h es i n g l e v a r i a b l em o d e l ，w h i c he l i m i n a t e st h ed i s t a n c ee r r o r sb yt h ef l u c t u a t i o n so f s i g n a lw i t h t h ea d v a n t a g e so fh i g ha c c u r a c y 2 i ta d v a n c e saf i l t e rm e t h o do nr s s ia n dl q l w i t hak i n do fi m p r o v e dk a l ：m a l l f i l t e r t h em e t h o de l i m i n a t e st h en o i s e s i g n a la n dn l o se r r o r i td e s i g n st h ei m p r o v e dk a l m a nf i l t e rb e c a u s eo ft h en o i s es i g n a la n dn l o s e r r o r t h r o u g ht h i sd e s i g n a t i o n ，i tp r o c e s s e st h ed e t e c t e ds i g n a la n dc o m p a r e st h e w a v eb e f o r ea n da f t e rf i l t e r i n g t h er e s u l t ss h o w t h a tt h ei m p r o v e dk a l m a 玎矗1 t e rc a n b e t t e rf i l t e ro u tt h en o i s ei n t e r f e r e n c ea n da c h i e v eab e t t e r f i l t e r i n ge f i e c t 3 i ts i m u l a t e st h e p o s i t i o n i n ga l g o r i t h mb a s e do nt h em e a s u r e m e mm o d e lo f r s s ia n dl q i w i t hm a t l a b 7 6 ，i tb u i l d st h es i m u l a t i n gp l a t f o r mt oe m u l a t et h eh l ( 1 0 0 r 、俯e l e s s l o c a t i o nn e t w o r ka n dc a r r i e so u tt h es i m u l a t i n ge x p e r i m e n tt op r o v et h ep o s s i b i l i t yo f p o s i t i o n i n ga l g o r i t h m m e a n w h i l e ，i ta n a l y z e st h ei n f l u e n c eo nt h e a c c u r a c vo f i 北京工业大学工学硕士学位论文 p o s i t i o n i n gb yt h ei n c r e a s i n go fb e a c o nn o d e t h er e s u l t ss h o wt h a tt h ea c c u r a c yo f p o s i t i o n i n ga l g o r i t h mh a sb e e ni m p r o v e d 4 i ti m p l e m e n t st h ep r o p o s e dp o s i t i o n i n ga l g o r i t h mo nt h eh a r d w a r ep l a t f o r mo f c c 2 4 31 z d k i tp r o g r a m st h er e l e v a n tp r o c e d u r e sw i t hl 域a n dd o w n l o a d st h eh a r d w a r e p l a t f o r mc c 2 4 3 1z d kt h r o u g ht h es o f t w a r eo fz - l o c a t i o n t h eh a r d w a r ep l a t f o r m i n c l u d e st h eb e a c o nn o d e ，t h eb l i n dn o d ea n dt h er o u t i n gn o d e t h ep o s i t i o n i n gr e s u l t s s h o wt h a tt h ei m p r o v e da l g o r i t h mh a sab e t t e ra c c u r a c y k e y w o r d s ：i n d o o rl o c a t i o n ；r s s i ；l q i ；k a l m a nf i l t e r 则 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 多：早 日期：星翌仝么：2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 毋审 寸导师躲q 蝴吼 o - 00 6 z | 第1 章绪论 - 1 1 课题的研究背景 第1 章绪论 随着现代移动通信技术蓬勃发展，人们对无线定位的需求与日俱增，无线定 位的领域己由最初的g p s 导航逐渐深入了人们的日常生活，并作为一项服务被人 们接受。人们不仅希望通过无线网络随时随地获得话音、数据及多媒体业务服务， 还希望移动通信能带给他们更多诸如车载导航，紧急救援定位等服务。无线定位 服务已经在军用、民用和商用领域证明了其重要性。 无线定位服务是指通过无线终端和无线网络的配合，确定移动用户的实际位 置信息，从而提供用户所需的与位置和方向相关的服务。无线定位服务的发展始 于美国。1 9 9 6 年，美国联邦通信委员会( f c c ) 制定了e - 9 1 1 服务n 3 ，要求所有无线 通信运营者，在移动用户出发紧急呼叫时，必须向公共安全服务系统提供用户的 位置信息和终端号码，以便对用户实施紧急救援工作，并要求分阶段实施定位精 度不断提高的用户定位服务。此后，日本、德国、法国、瑞典、芬兰等国家纷纷 推出各种各具特色的商用定位服务。这些服务主要应用于：公共安全，如紧急救 援，报警信息发布；跟踪业务，如犯罪嫌疑人的跟踪，走失老人和儿童的寻找， 车辆的防盗报警，交通监控控：基于位置的信息业务，如车辆导航服务，城市观光， 基于位置的信息发布等。 尽管g p s 定位系统为开阔的室外环境中工作的各类用户提供了越来越多的帮 助，但是出于成本、能源等因素，许多情况下它们不适合在室内环境中使用心1 。 近年来，随着无线局域网络口一( w i r e l e s sl o c a la r e an e t w o r k ，w l a n ) 的快速发 展，室内定位系统的开发与设计也引起了人们的关注。超级市场、博物馆、机场 等地方都需要依赖室内定位信息来实现高效的管理和提高更优质的服务，w l a n 网络是一种高速无线i p 通信网络，也就是人们常说的i e e e8 0 2 11 。主要针对室 内应用环境的w l a n ，切合了现代社会对移动办公、移动生活娱乐的需求，在世界 范围内得到了广泛的部署，推动了室内无线定位的发展。 无线传感器网络碡脚( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 的出现，无论是为室 外还是室内的无线定位注入了新的活力。综合了传感器技术、嵌入式计算技术、 现代网络及无线通信技术、分布式信息处理等技术的无线传感器网络是在监控区 域内部署大量的廉价微型传感器，通过无线通信方式形成的一个多跳的、自组织 的网络系统，感知、采集和处理网络覆盖区域中可感知对象的信息，并发送给用 户终端。无线传感器网络中，位置信息对传感器网络的监测活动至关重要，也是 传感器节点监测消息中所包含的重要信息盯1 。 无线传感器网络由于其灵活、成本低、易于布置等特性，能够方便、及时、 北京工业大学工学硕士学位论文 准确的采集各类信息，而受到了广泛的重视。在军事领域，无线传感器网络的自 组织性和容错能力，使其不会因为某些节点在攻击中的损坏而导致整个系统的崩 溃，这使得它非常适合应用于恶劣的野外环境中。在民用领域，无线传感器网络 以其功耗低、体积小、成本小的特点，在环境、健康、家庭和其他商业领域显示 了出广阔的应用前景。 i e e e 标准委员会确定的个人域网络3 标准便是一种应用于家庭连接各种家 电、娱乐设备的无线网络。这种短距离的无线通信技术主要应用于家庭、办公室、 商场等室内场所。它为近距离范围内的设备建立无线连接，把几米到几十米范围 内的多个设备通过无线方式连接在一起，使他们可以相互通信甚至接入l a n 或者 i n t e r n e t 。和长距离的无线通信技术相比，短距离无线通信技术以牺牲通信距离 为代价，来换取更低的成本和更大的服务范围，用户无需支付通信使用费用，不 受基站等通信基础设施的制约。这种技术的应用大大改善了人们的生活和工作质 量，对现有的无线长距离通信技术是一个良好的补充。在这个平台之上，w i f i 、 z i g b e e 睁】、b l u e t o o t h n 们、u w b n u ( u l t r aw i d eb a n d ) 等一系列短距离无线技术 不断涌现。 1 2 国内外研究现状 近年来，定位技术在国外受到高度重视和深入研究，在i e e e 的期刊和会议 上出现了不少定位技术的发明专利以及一些专门从事定位技术的研究与开发的 公司，如美嘉、t r u e p o s i t i o n 等。各大跨国公司，如西门子、诺基亚、爱立信、 三星、中兴、华为等也积极开展对基于g s m 、i s 一9 5 和3 g 中的w c d m a 、c d m a 2 0 0 0 、 t d s c d m a 等网络采用的定位技术的研究。目前研究的内容涉及了定位技术的方方 面面，并且更侧重于常见定位算法的研究、定位方法和技术的研究、定位技术实 施方法的研究、定位系统的性能评估等，尤其是定位算法的研究。 在定位算法的研究方面，国外研究成果中具有代表性的有：t h o m a s h i e i n e - o s t m a n n 扩充了数据融合技术的应用范围，提出了一种应用于定位估计 的数据融合模型n 别，拓宽了定位技术的研究范畴；s m a n g o l d 将基于隐马尔可夫 模型( h m m ) 的模式识别技术应用于定位估计n 钔。b a t t i t i 等人在文献钔中提出了 从神经网络的角度考虑，以多个节点的r s s i 为输入，位置坐标为输出，训练多层 感知机( m l p ) ，达到推理位置信息的目的。p e t r im y l l y m a k i 等人在文献n 司中提出 将位置估计问题看作机器学习的问题，即基于在已知区域收集的样本建立r s s i 在不同地理区域上的分布模型，并提出了一个概率性的框架解决定位问题， p i - c h u nc h e n 在其发表的论文及博士论文n 盯中提出利用残差加权的方式消除 n l o s 误差；y t c h a n 提出一种在t d o a 误差服从理想高斯分布时性能优良的t d o a 定位算法n 引；m p w y l i e 在文献n 踟中则提出了一种判断及消除n l o s 误差的经典 第1 章绪论 方法，目前很多针对n l o s 误差消除的研究都是对该方法的进一步深入；m c g u i r e 提出了一种鲁棒估计函数n 9 1 ，用于改进n l o s 环境下的定位估计：还提出了一种 基于时间差测量值观测得到的测量值非参数近似的定位估计算法乜叫，在n l o s 环 境下也取得了较好的定位性能。 在室内定位系统开发研究方面，常用的方法是利用t o a 、t d o a 、a o a 、r s s i 中 的一种或者多种方法来进行联合定位。主要研究成果包括：微软公司研究团队开 发的室内跟踪定位的r a d a r 乜原型系统，该系统结合经验数据和衰减因子模型， 在大量数据采集的基础上通过一定的匹配法则确定目标位置，提供定位服务和应 用。h a r v a r d 大学的m o t e t r a c k 口列定位系统，该系统最早将w s n 引入室内定位服 务中，并充分展现了w s n 分布式系统的高鲁棒性优势。由o l i v e t t i 研究实验室 研制的a c t i v eb a d g e 业3 1 室内定位感知系统。a t & t 研究人员开发的a c t i v eb a t 乜町 定位系统，该系统利用超声波的到达时间来实现定位。 国内对定位技术的研究起步较晚，但随着时间的推移，目前国内从事这项技 术研究的人已经大大增加，涌现了不少研究与开发定位技术的单位，如清华大学、 北京邮电大学、中国科技大学、复旦大学、西安电子科技大学、华中科技大学、 吉林大学、西南交通大学、国防科大、重庆邮电大学等高校以及大唐、华为、中 兴等通信公司，在国际上以及国内刊物发表了大量的研究成果，其中具有代表性 的有：重庆邮电大学袁正午等人在文献舱5 3 提出的基于多元线性回归快速迭代的室 内定位算法，该算法利用多元线性回归方法得出信号传播模型中相应的参数，进 而利用该模型求出移动终端的初始位置，再采用快速迭代方法和各移动端相互矫 正提高定位精度。西南交通大学的孙瑜、范平志在文献乜印中介绍了基于r f i d 技 术的l a n d m a r c 室内定位系统，并在此基础上提出了一种最近邻居改进算法和基 于误差多级处理的数据融合定位方法；复旦大学的倪巍、王宗欣在文献妇7 3 中提出 一种基于r s s i 测量的室内定位算法，该算法通过对现有的路径损耗模型进行修 正，引入距离估计误差随机变量，推导出一种迭代最大似然估计算法，通过有限 次的迭代得到令人满意的位置估计结果。 1 3 现有室内定位系统和算法的总结 从整体上看，近年来提出的一些循环求精算法，如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 、n h o pm u l t i l a t e r a t i o np r i m i t i v e ，更加充分发挥了 w s n 的特点，即利用节点间的协同工作实现单个节点无法完成的任务。它们在初 始阶段着重于获得节点位置的粗略估算，并在求精阶段根据用户预设的精度门限 循环求精；甚至还可根据应用需求，将整个求精阶段作为一个可选阶段。这些算 法不仅提高了定位精度，还给予用户更大的自由度，正逐渐形成一个新的类别。 但我们还应看到，现有的定位算法还存在如下一些问题： 北京工业大学工学硕士学位论文 ( 1 ) 未知节点必须与锚节点直接相邻，锚节点密度过高，例如c r i c k e t 、 c o o p e r a t i v er a n g i n g 。 ( 2 ) 定位精度依赖于网络部署条件。例如：d v h o p 、d v - d i s t a n c e ，仅适用于 密集部署的各向同性的网络。 ( 3 ) n - h o pm u l t i l a t e r a t i o np r i m i t i v e 和凸规划算法要求锚节点必须部署 在网络的边缘。 ( 4 ) 没有对距离角度测量误差采取抑制措施，造成误差传播和误差积累，定 位精度依赖于距离角度测量的精度。例如a h l o s 、d v - d i s t a n c e 、d v - b e a r i n g 、 d v - r a d i a l 、s p a 及其改进算法。 ( 5 ) 依靠循环求精过程抑制测距误差和提高定位精度。虽然循环求精过程可 以明显减小测距误差的影响，但不仅产生了大量的通信和计算开销，而且因无法 预估循环的次数而增加了算法的不确定性。例如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 、n h o pm u l t i l a t e r a t i o np r i m i t i v e 。 ( 6 ) 算法收敛速度较慢。例如g e n e r i cl o c a l i z e da l g o r i t h m 算法在每次循 环中，相邻节点中仅有一个可实现定位并升级为锚节点。 从硬件支持的部署和维护成本，软件性能的计算复杂度和系统鲁棒性及网络 形式、信号类型的角度对上述定位系统作汇总表格，如表卜1 所示， 表卜1 典型定位系统比较 t a b l e1 - 1t h ec o m p a r i s i o no f t y p i c a ll o c a t i o ns y s t e m 系统信号类型网路形式信号地图构建计算复杂度其它 r a d a rr s s i、l a n 人工采集简单环境特定 离线数据集中式 c ：r i c k e t t o aw s n s 否简单部署严格 测距非集中式 m o t e t r a c kr s s iw s n s 人工采集简单环境特定 离线数据分布式 从表i - i 中可知，r a d a r 、m o t e t r a c k 都需要人工部署节点或采集参考信息， 系统构建成本相当高；c r i c k e t 是测距再定位的典型系统，测距对定位精度影响 较大。 许多算法和系统的定位精度都还有很大的提高空间。总之，无线传感器网络 定位问题的研究仍旧是w s n 的一个技术难点，也是关键点之一。 1 4 论文研究思路与内容安排 论文通过对目前各种无线定位技术的分析研究，借鉴了无线局域网的经典定 位技术，并结合z i g b e e 硬件所提供的链路质量l o i ，提出了基于l q i 的辅助定位思 第1 章绪论 想，最后在t i 公司的z i g b e e 硬件平台上实现了该定位算法。 论文在内容组织上分为6 章，具体安排如下： 第1 章绪论 首先，论文在查阅了大量相关文献的基础上，阐述了课题的研究背景，从无 线局域网、移动通信网络等较为成熟的无线网络定位技术探讨了无线定位技术及 无线定位系统的发展，综述了基于无线网络定位技术的国内外研究现状，最后总 结了本文的主要工作和论文的框架结构。 第2 章室内定位技术 重点讨论了目前较为成熟的室内无线定位技术方案，定位算法的分类以及基 于测距技术定位算法的数学模型，并对定位性能评价指标进行了简单介绍。随后 从z i g b e e 网络组成和协议结构两个方面入手，最后介绍了无线技术的应用前景。 第3 章基于无线信号传播损耗模型的室内定位算法 首先比较了现有的无线信号传播损耗测距模型中的经验模型和确定性模型， 从定位的精确度和快速性等方面综合考虑，本文采用了经验模型中的简化模型， 并对其进行了如下的改进：通过大量的实验数据研究了r s s i 和l q i 之间的相关 性，提出了改进的基于r s s i 和l q i 的测距模型。实验结果表明，该模型的测距 性能要优于单变量模型，减小了信号波动给测距过程带来的距离误差，具有定位 精确度高的优点。 第4 章用改进的卡尔曼滤波器减小非视距误差 介绍了n l o s 误差产生的原因、对无线定位的影响以及n l o s 误差模型，并对 n l o s 误差的鉴别和消除算法进行了总结和分析。基于对n l o s 误差特点的分析， 提出了用改进的卡尔曼滤波器来实现减小n l o s 误差算法。 第5 章定位算法的软件仿真与定位性能比较 在m a t l a b 7 6 环境下编写相关的定位算法程序，进行仿真实验，并分析了信 标节点数目的增加对定位精度的改善，仿真结果表明，改进后定位算法的定位精 度有了明显的提高，通过增加信标节点的布局密度可以在一定程度上提高系统定 位性能。 第6 章定位系统的开发平台及算法的实验验证 介绍了基于z i g b e e 的c c 2 4 3 1 z d k 定位开发平台，其中包括软硬件平台的简单 介绍，并在此平台上实现了所提出的定位算法，室内实测表明，节点的定位误差 在2 米左右，定位精度有了一定的提高，能够满足室内定位的应用要求，并且分析 了加入网络的信标节点数量对定位精度的影响。 结论与展望：对论文的内容和创新点作了总结，分析了目前研究的局限性， 指出了可以进一步展开研究的问题。 北京工业大学工学硕士学位论文 2 1 室内定位技术 第2 章室内定位技术 2 1 1 室内定位技术概述 1 、w i f i 定位技术 w i f i 定位技术是利用日益增多的w i f i 网络和设备来为用户提供价格低廉的 定位功能。该定位技术适用于室内或室外定位、保密性好、可被应用于现有的具 有w i f i 功能的设备上。在公共场合，w i f i 的覆盖密度很大，只要用户的设备上有 一张本地w i f i 接入点的分布图，设备就会通过接收w i f i 信标和分布图确定自己的 位置，得到所处位置的信息后，用户可以根据相关信息更好地开展不同的应用。 著名无线局域网设备提供商a i r e s p a c e 公司于2 0 0 4 年开发出了一种利用常规的 w i f i 无线网络进行个人定位系统。这种无线定位服务采用无线电波定位的技术， 其定位精度可以达n i o 米以内。 2 、超声波定位技术 超声波定位系统由若干个应答器和一个主测距器组成，主测距器放置在被测 物体上，在微机指令信号的作用下向位置固定的应答器发射同频率的无线电信 号，应答器在收到无线电信号后同时向主测距器发射超声波信号，得到主测距器 与各个应答器之间的距离。同时有三个或三个以上不在同一直线上的应答器做出 回应时，可以根据相关计算确定出被测物体所在的二维坐标系下的位置。c r i c k e t l o c a t i o ns u p p o r ts y s t e m 汹1 是目前成功使用该项技术的定位系统。但是这类系 统需要大量的底层硬件设施投资，成本太高，无法大面积推广。 3 、红外线室内定位技术 红外线室内定位技术的原理是红外线i r 标识发射调制的红外射线，通过安装 在室内的光学传感器接收进行定位。虽然红外线具有相对较高的室内定位精度， 但是由于光线不能穿过障碍物，使得红外射线仅能视距传播。直线视距和传输距 离较短这两大主要缺点使其室内定位的效果很差。当标识放在口袋里或者有墙壁 及其他遮挡时就不能正常工作，需要在每个房间、走廊安装接收天线，造价较高。 因此，红外线只适合短距离传播，而且容易被荧光灯或者房间内的灯光干扰，在 精确定位上有局限性。 4 、射频识别技术( r f i d ) 典型的r f i d 系统包括：读卡器( r e a d e r ) 、电子标签( t a g ) 、主机( h o s t ) 及数 据库。当系统要进行物体识别工作时，主机通过有线或无线方式下达控制命令给 r e a d e r ，r e a d e r 接收到控制命令后，其内部的控制器会通过r f 收发器发送出某一 6 - 第2 章室内定位技术 频率的无线电波能量，当t a g 内的天线感应到无线电波能量时，会传回含有自身 种类识别码标志、制造商标志的识别资料给r e a d e r ，最后传回主机进行识别与管 理。该项定位技术最典型的例子就是l a n d m a r c 定位系统汹3 ，该系统用活性参考标 签t a g 替代离线数据采集，其动态参考信息能够实时捕捉环境变化，提高定位精 度和可信度。活性参考标签t a g 的应用免去了每个测试点数百次的人工数据采集， 且能更好的适应室内环境的波动，提高定位精度。目前，关于r f i d 定位技术研究 的热点和难点在于理论传播模型的建立，用户的安全隐私和国际化标准等方面。 5 、室内g p s 定位技术 当g p s 接收机在室内工作时，由于信号受建筑物的影响而大大衰减到十分微 弱的地步，要想达到室外一样直接从卫星广播中提取导航数据和时间信息是不可 能的。a - g p s 技术1 为这个问题的解决提供了可能性。其定位的机制是a - g p s 手机 首先将本身的基站地址通过网络传输到位置服务器，位置服务器根据该手机的大 概位置传输与该位置相关的g p s 辅助信息到手机，该手机的a - g p s 模块根据辅助信 息接收g p s 原始信号，计算手机到卫星的伪距，并将有关信息通过网络传输到位 置服务器，位置服务器根据传来的g p s 的伪距信息和来自其他定位设备的辅助信 息完成对g p s 信息的处理，并估算该手机的位置。虽然该项技术可以达到令人满 意的定位精度，但是定位实现必须通过多次网络传输，占用了大量的空中资源。 此p b a g p s 定位技术由于需要在手机内集成g p s 接收器，比一般手机在耗电上有一 定的额外负担，决定了它的应用受限性。 2 1 2 定位算法的分类 无线网络可以在广泛的应用领域内实现复杂的大规模监测和追踪任务，而网 络节点的自身位置是大多数应用的基础。一方面，网络节点必须明确自身位置才 能详细说明“在什么位置或区域发生了特定事件 ，从而实现对目标的定位和追 踪；另一方面，了解网络节点的位置分布状况可以有助于提高网络的路由效率， 实现网络的负载均衡以及网络拓扑的自动配置，从而有助于改善整个网络的覆盖 质量。因此，必须采取一定的机制或算法来实现无线网络节点的自身定位口。 根据节点是否己知自身的位置，节点可分为信标节点和未知节点。信标节点 通过携带g p s 定位设备等手段获得自身的精确位置，在网络节点中占的比例很小。 不是信标节点的其它节点就是未知节点，它们通过信标节点来确定自身位置。 大致来说，定位算法分为两大类m 1 ：基于测距技术( r a n g e b a s e d ) 的定位算 法和与距离无关( r a n g e f r e e ) 的定位算法。前者通过测量节点间点到点的距离或 角度信息来计算未知节点的位置，通常采用测距、定位和修正等步骤。根据测量 节点间距离或方位时所采用的方法，基于测距技术定位算法分为基于t o a 的定位、 基于t d o a 的定位、基于a o a 的定位、基于r s s i 的定位等。后者则无需距离和角度 北京工业大学工学硕士学位论文 信息，而利用节点间的邻近关系和连通性实现定位，其典型的定位算法有质心法、 凸规划算法，a p i t 算法等。一般来说基于测距技术的定位算法的精度要高于与距 离无关的定位算法。 1 、与距离无关的定位算法 距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬件 的需求。与距离无关的定位算法通常包括侧m 1 ： ( 1 ) 自适应网络定位算法a p s ( a dh o cp o s i t i o ns y s t e m ) 美国路特葛斯大学的d r a g o sn i c u l e s c u 等利用距离矢量路由和g p s 定位的思 想提出了一系列分布式定位算法合称为a p s ，一共包括了5 种定位算法：d v h o p ， d v d i s t a n c e ，e u c li 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 r a d i a l 。 d v - h o p 算法的基本思想是将待定位节点到锚节点之间的距离用网络平均每 跳距离和两者间跳数的乘积表示，使用三边定位算法获得待定位节点的位置信 息。虽然待定位节点通信范围内的锚节点数量不多，但是采用该方法可以获得到 通信范围外多个锚节点的距离估计值，利用大量的信息获得该节点的位置。如图 2 1 所示，每个锚节点( 墨，咒) 从其他锚节点( x ，y j ) ( 歹= 1 ，2 ，玎) 收集到足够数量 的跳数信息来估算平均每跳距离，并向整个网络广播该信息，锚节点i 的平均每 跳距离如式( 2 - 1 ) 所示， q 2 厄i 再而 l ( 2 - 1 ) j 式( 2 - 1 ) 中为节点i 和节点j 之间的跳数。 假定某个待定位节点与锚节点i 的跳数最少，则锚节点i 的平均每跳距离就是 它的平均每跳距离，从而可以得到该待定位节点与其他锚节点之间的距离。当该 待定位节点获得三个以上与锚节点的距离时就可以用三边定位法估算自己的位 置坐标。 图2 1d v - h o p 算法示意图 f i g 2 - 1t h ec h a r to f d v - h o pa l g o r i t h m d v d i s t a n c e 算法与d v h o p 算法类似，所不同的是相邻节点使用r s s i i 贝i 量节 第2 章室内定位技术 点间点到点距离，然后利用类似于距离矢量路由的方法传播与信标节点的累计距 离。当未知节点获得与三个或更多信标节点的距离后使用三边测量定位。其优点 是测距比d v - h o p 要精细，缺点是同样也仅适用各向同性的密集网络中、定位误差 随测距误差增大而增大。 e u c l i d e a n 算法基于围绕在信标节点周围的节点的局部几何拓扑，给出了计 算与信标节点相隔两跳的未知节点位置的方法。如图2 2 所示，未知节点b ，c 与信 标节点l 两两相邻；节点a 与b ，c 相邻。对于四边形a b c l ，所有边长和一条对角线 b c 已知，根据简单的几何原理可计算出a l 的长度。但节点a 有两个可能的位置彳和 4 ，假如a 还有其他邻居节点d 与信标节点l 相邻，并与b 或c 之一相邻，那么可以 使用d 来替换b 或c ，再次计算a l 的距离，则a 节点就能在两个可能的位置中选择出 正确的一个。使用这种方法，当未知节点获得与三个或更多信标节点距离后定位 自身。 图2 - 2e u c l i d e a n 算法示意图 f i g 2 - 2t h ec h a r to f e u c l i d e a na l g o r i t h m 在d v - c o o r d i n a t e 算法中，每个节点首先利用e u c li d e a n 算法计算两跳以内的 邻近节点的距离，建立局部坐标系统( 以自身位置作为原点) 。随后，相邻节点交 换信息，节点从邻居那里接收到信标节点的信息并将其转化为自身坐标系统中的 坐标后，再在自身坐标系统中计算出距离，并使用这些距离进行三边测量定位或 将自身坐标系统转换为全局坐标系统，这两种方法具有相同的性能。 d v - b e a r i n g 算法和d v - r a d i a l 算法提出了以逐跳方式( h o pb yh o p ) 跨越两跳 甚至三跳来计算与信标节点的相对角度，最后使用三角测量定位的方法。两者的 区别在于，d v r a d i a l 算法中每个信标节点或节点都安装有指南针( c o m p a s s ) ，从 而可以获得绝对角度信息( 例如与正北方向的夹角) ，并达到减少通信量和提高定 位精度的目的。实验显示，d v - b e a r i n g 和d v - r a d i a l 算法在网络平均连通度为 1 0 5 ，信标节点比例为2 0 。a o a 测量误差小于5 度的条件下，9 0 以上的节点可以 北京工业大学工学硕士学位论文 实现定位，定位精度分别为4 0 和2 5 。 ( 2 ) 质心算法 该算法的核心思想是：锚节点每隔一段时间，向邻居节点广播一个信标信号， 信号中包含自身i d 和位置信息，当待定位节点接收到来自不同锚节点的信标信号 数量超过某一预设门限或接收一定时间后，该节点就确定自身位置为这些锚节点 所组成的多边形的质心。设未知节点接收到来自锚节点a ，b ，c ，d ，e 的信号，锚节 点的坐标分别为么( 矗，儿) ，b ( ，儿) ，c ( t ，儿) ，d ( x a ，y a ) ，e ( t ，儿) ，则待定 位节点的坐标如公式( 2 2 ) 所示， o ，y ) ：芦垫鼍掣，盐盈翟业) ( 2 2 ) 3) 质心算法完全基于网络连通性，无需锚节点和待定位节点之间的协调，实现 较为简单，定位计算量小。但用质心作为实际位置本身就是一种估计，这种估计 的精确度和信标节点的密度以及分布有很大关系：密度越大，分布越均匀，定位 精度越高。 ( 3 ) 近似三角形内点测试( a p i t ) 算法 首先确定多个包含未知节点的三角形区域，未知节点从邻近信标节点组成的 集合中任意选取三个信标节点，测试未知节点是否位于三角形内部，使用不同信 标节点组合重复测试，直到穷尽所有组合或达到所需定位精度，最后确定包含未 知节点所有三角形的重叠区域的质心作为未知节点的位置。该算法要求每个待定 位节点的周围要有若干个相邻的锚节点，这就对锚节点的密度提出了较高的要 求，除此之外，应该避免由于待定位节点处于网络的边缘而导致无法定位的情况 出现。 2 、基于测距技术的定位算法 该类定位算法依托节点之间的距离或角度进行定位，显然，它得到的是节点 之间的相对位置信息，因此，要获知节点的绝对位置信息，就要知道某个或某些 节点的绝对位置坐标值。目前，比较常用的方法有以下几种：信号达到时间( t o a ) 、 信号到达时间差( t d o a ) 和信号到达角度( a o a ) 和接收信号强度( r s s i ) 等定位方 法。 ( 1 ) 基于r s s i 定位 己知发射功率，在接收节点测量接收功率，计算传播损耗，使用理论或经验 的信号传播模型将传播损耗转化为距离，该技