（检测技术与自动化装置专业论文）基于信号强度室内定位技术的研究与实现.pdf

摘要 摘要 随着通信技术和无线网络的蓬勃发展，人们对无线定位的需求与日俱增。 确定用户的位置信息有利于向用户提供方便高效的服务，室内定位作为定位技 术研究的一个热点，越来越受到人们的关注。 室内环境相对复杂，信号微弱，且多径、反射现象严重，故要求定位算法 对各种误差的鲁棒性要强。对定位精度和安全性的特殊要求，使得室内无线定 位技术有着不同于普通定位系统的鲜明特点。因此，定位难度较大。目前常见 的方法就是在室内环境下搭建小范围的定位网络。 本文就是在z i g b e e 网络定位平台上，开发适用的定位算法，探索能够实现 建筑物内人员精确定位的理论和实现技术。重点研究了基于信号强度的定位算 法的关键技术和功能实现。主要有以下几个方面的研究成果： 1 、研究各种经典定位算法和室内无线传播模型，通过实测实验比较了模型 中不同参数对r s s i 测距的影响，采用曲线拟合的方法对模型的参数进行了优 化，得到了适合本文定位系统的距离损耗模型，减小了测距误差。 2 、针对初始获得的信号强度值存在较大误差的问题，采用滤波算法对r s s i 进行滤波处理。考虑当前时刻状态和前一时刻状态存在的相互关系，引入速度 常量。节点的匀速运动会导致信号强度的恒定变化率，从而达到对r s s i 滤波的 目的，进一步减小了误差。将处理后的r s s i 带入距离损耗模型，得到滤波后的 距离。 3 、在确立了模型的基础上，提出一种基于三边测量和t a y l o r 级数展开的 定位算法。首先利用三边测量法计算出一个估计坐标，作为t a y l o r 级数展开的 循环初值。然后用t a y l o r 级数展开距离差，进行矩阵计算，并反复迭代求精， 直到误差满足预先设定的门限，得出最终的位置坐标。对算法进行了软件实现， 仿真结果表明算法具有优越性。 4 、结合t i 公司的c c 2 4 3 1 z d k 定位系统开发平台，以实验室和走廊为应用 场景进行实测实验，完成了定位算法的实现。比较两种算法的定位效果，实验 结果令人满意，定位精度得到了提高，证明了本文算法的优越性。 关键词：无线网络；室内定位；r s s i 滤波算法；三边测量；t a y l o r 级数展开 北京工业人学工学硕士学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o na n dw i r e l e s sn e t w o r k p e o p l e ，s d e m a n df o rw i r e l e s sl o c a t i o ni si n c r e a s i n gg r o w sd a yb yd a y d e t e r m i n et h eu s e r s l o c a t i o ni n f o r m a t i o ni sc o n d u c i v et op r o v i d ef r i e n d l ya n de f f i c i e n ts e r v i c e a sf lh o t r e s e a r c ht o p i c ，i n d o o rl o c a t i o nt e c h n o l o g yr e c e i v i e sm o r ea n dm o r ea t t e n t i o n t h ei n d o o re n v i r o n m e n ti s c o m p l e x i t y , m u l t i p a t hf a d i n ga n da t t e n u a t i o no f s i g n a lt r a n s m i s s i o nc a l l e df o rav a r i e t yo fa l g o r i t h mw h i c hh a sab e t t e rr o b u s t n e s st o e r r o r t h ec o m p l e x i t yo ft h ei n d o o re n v i r o n m e n ta n dt h es p e c i a lr e q u i r e m e n t so f p o s i t i o na c c u r a c ym a k et h ei n d o o rw i r e l e s sp o s i t i o n i n gt e c h n o l o g yh a sd i s t i n c t c h a r a c t e r i s t i c sw h i c hi sd i f f e r e n tf r o mg e n e r a ll o c a t i o ns y s t e m t h e r e f o r e ，t h ed i f f i c u l t o fi n d o o rp o s i t i o n i n gi sr e l a t i v e l yh i g h e rt h a no t h e r s a tp r e s e n t ，c o m m o nm e t h o di s s t r u c t u r es m a l l - s c a l ep o s i t i o n i n gn e t w o r ku n d e ri n d o o re n v i r o n m e n t t h ea r t i c l ee m p l o d e r sl o c a t i o na l g o r i t h mi np o i n to nz i g b e ew i r e l e s sn e t w o r k p o s i t i o n i n gp l a t f o r m i te x p l o r e st h et h e o r ya n di m p l e m e n t a t i o nt e c h n o l o g yo f p r e c i s ep o s i t i o n i n gi nb u i l d i n g f o c u so nt h ek e yt e c h n i q u ea n df u n c t i o n a l i m p l e m e n t a t i o no fl o c a t i o na l g o r i t h mb a s e do ns i g n a ls t r e n g t h t h em a j o rr e s e a r c h f i n d i n g sa n di n n o v a t i o na r ea sf o l l o w s ： 1 ) i tr e s e a r c h e st y p i c a ll o c a t i o na l g o r i t h ma n di n d o o rw i r e l e s st r a n s m i s s i o n m o d e l s c o m p a r et h ei m p a c to nt h er s s io fd i f f e r e n tp a r a m e t e r si nt h em o d e i t h r o u g he x p e r i m e n t s u s i n gc u r v ef i t t i n gm e t h o dt oo p t i m i z e dm o d e lp a r a m e t e r sa n d g a i nt h ep r o p e rm o d e l i tr e d u c e st h er a n g i n ge r r o r 2 ) t h e r ei sab i ge r r o ri ni n i t i a v a l u ea b t a i n e d ，i tu s e ss m o o t h i n ga l g o r i t h mt o d e a lw i t ht h er a wr s s i c o n s i d e r i n gt h ec o r r e l a t i o nb e t w e e nc u r r e n ts t a t u sa n do n e t i m eb e f o r es t a t u s ，i ti m p o r t st h er a t ec o n s t a n t c o n s t a n tv e l o c i t ym o t i o nr e s u l t si n c o n s t a n td a t ac h a n g er a t e ，s oa st oa c h i e v et h ep u r p o s eo ft h er s s if i l t e r i n ga n d f u r t h e rr e d u c et h ee r r o r f i l l e dr s s ia r ec o n v e r t e dt o d i s t a n c e si nc a l i b r a t e d p r o p a g a t i o n 3 ) i tp r o p o s e sap o s i t i o n i n ga l g o r i t h mo ft r i l a t e r a t i o nm e t h o da n dt a y l o rs e r i e s e x p a n s i o nb a s e do nt h i sm o d e l u s i n gt r i l a t e r a t i o nm e t h o d ，i tc a l c u l a t e sa ne s t i m a t e c o o r d i n a t e sa sac y c l ei n i t i a lv a l u ef o rt a y l o rs e r i e se x p a n s i o n a l g o r i t h me x p a n d s d i s t a n c ee r r o ru s i n gt a y l o rs e r i e sa n dp r o c e e d sm a t r i xc a l c u l a t i o nu s i n gi t e r a t i v e m e t h o du n t i le r r o ri sa c c e p t a b l e ，t h ef i n a lp o s i t i o ni sc o m p u t e d i tp r o c e s s e ss o f t w a r e i i a b s t r a c t i m p l e m e n t a t i o n ，s i m u l a t i o nr e s u l t ss h o w t h a tt h ea l g o r i t h mh a st h es u p e n o n t y 4 1nm e ni n 缸d d u c e st h eh a r d w a r ei m p l e m e n t a t i o no fa l g o r i t h m i nt e 咖so t f e a s i b i l i t ya n ds u p e r i o r i t y e x p e r i m e n ti s d e s i g n e dt ov m f yt h ee 疏c t i v e n e s s a n d s u p e f i o 岫o ft h ep r o p o s e da l g o r i t h mo n t i sc c 2 4 3 1l o c a t i o ns y s t e md e v e l o p m 饥t d 1 a t f o r m t h er e s u i t sa r es a t i s f i e da n dr e v e a l st h ef e a s i b i l i t yo fp r o p o s e da i g o r i t h r a w h i c he f l e e t i v e l yi m p r o v e st h ep o s i t i o n i n ga c c u r a c y k e y w 。r d s ：w i r e l e s sn e t w 。r k ；h a d 。o rl o c a t i o n ；r s s is m o o t h i n ga l g o r i m m ； t r i l a t e r a t i o n ；t a y l o rs e r i e se x p a n s i o n - i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：! ! 丑金! 盍日期：娑2 ：岁 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 垂静 导师签名： 第1 章绪论 第1 章绪论 1 1 引言 随着无线网络、移动通信和普及计算技术的不断扩大和深入，位置感知计 算、基于位置的服务显得越来越重要，典型的例子有资源查找、参观导航、会 议指南、寻找老人儿童、节能控制、设备资产管理等。而如何确定室内物品以 及人员的位置是实现基于位置服务的核心问题。自从8 0 2 1 5 无线局域网标准问 世以来，无线通信市场一直增长迅猛。在现有高速无线局域网条件下，用户凭 借轻量级可移动的计算设备就能随时随地接入互联网。移动中的用户对信息的 即时性和就地性的需求越来越强烈。这就给基于位置的服务和应用提供了广阔 的市场空间。 基于g p s 1 】的室外定位系统的成功应用给室内定位系统研究和开发提供了 巨大的动力。全球定位系统是比较成功的定位技术，在户外空旷的地方有很好 的定位效果，已经成功运用于车辆船舶等交通工具导航。但是由于室内环境的 特殊性以及室内定位在精度及其它方面的要求，g p s 定位及蜂窝网无线定位等 方法都不能直接应用到室内定位中。基于接收信号强度的定位是根据接收信号 强度随距离变化的规律进行定位，与基于信号到达时间( t o a ) 和信号到达角度 ( a o a ) 的定位相比，它不需要添加额外的硬件设备来进行精确的时间同步和角 度测量，能充分利用现有的无线网设施，将定位系统的应用范围扩大到楼群和 室内，因此成为室内定位技术的研究热点。 室内定位的难点在于如何克服随机因素对信号的干扰，对静止和移动用户 进行准确、快速定位，使定位方法具有健壮性、适应性，因此对其研究涉及到 随机信号处理、跟踪与导航、无线传感器网络、计算机技术等众多交叉领域， 目前国内外对定位算法的研究主要集中在提高算法的精度和实用性。 1 2 课题背景 随着现代通信技术和无线网络的蓬勃发展，人们对无线定位的需求与日俱 增，无线定位的领域已由最初的g p s 导航逐渐深入了人们的日常生活，并作为 一项服务被人们接受。人们不仅希望通过无线网络随时随地获得话音、数据及 多媒体业务服务，还希望移动通信能带给他们更多诸如车载导航，紧急救援定 位等服务。无线定位服务是指通过无线终端和无线网络的配合，确定移动用户 的实际位置信息，从而提供用户所需的与位置和方向相关的服务。 室外定位技术提出较早，发展相当快，成果显著。相比而言，室内定位技 术起步较晚，是一个崭新的领域，但同时也是一个相当重要的领域。特别是美 国9 11 事件中，大量人员，包括后期进入大楼进行救援的消防人员，由于无法 北京工业火学丁学硕土学位论文 与外界通信以及在室内的位置不明确，最后纷纷葬身火海中。这出惨剧凸显出 室内定位系统的重要作用和对它的急迫的需要。1 9 9 6 年，美国联邦通信委员会 ( f e d e r a lc o m m u n i c a t i o n sc o m m i s s i o n ，f c c ) 制定了e - 9 1 1 【2 咱艮务，要求所有无 线通信运营者，在移动用户出发紧急呼叫时，必须向公共安全服务系统提供用 户的位置信息和终端号码，以便对用户实施紧急救援工作，并要求分阶段实施 定位精度不断提高的用户定位服务。此后，日本、德国、法国、瑞典、芬兰等 国家纷纷推出各种各具特色的商用定位服务。这些服务主要应用于公共安全， 如紧急救援，报警信息发布；跟踪业务，如犯罪嫌疑人的跟踪，走失老人和儿 童的寻找，车辆的防盗报警，交通监控；基于位置的信息业务，如车辆导航服 务，城市观光，基于位置的信息发布等。无线定位服务已经在军用、民用和商 用领域证明了其重要性。 随着无线网络的发展与普及，出现了不少与定位相关的技术和应用，就技 术的研究现况而言，室内定位由于障碍物的影响较为复杂，信号精准度较低， 因此难度较高。室外定位主要利用通信系统或全球化定位系统( g p s ) 所提供相关 的位置信息。g p s 已经是一套普遍应用的成熟室外定位技术，然而对于室内的定 位，由于g p s 系统的标准误差相对于较小的室内环境来说比较大，精度难以满 足实际要求，同时由于室内环境信号受到遮蔽，定位精度受到更大影响，因此 在室内使用g p s 变得十分困难。另外一个应用于室外定位的蜂窝系统也存在类 似的缺点。因此，针对室内特殊的环境，开发一种适用的定位技术是十分必要 的。 1 3 国内外研究现状 无线定位是指利用现有的无线通信网络资源，通过估计移动终端与各基站 之间的信号参数，并在网络或者移动终端借助一定的定位算法，确定移动终端 的位置。自从美国f c c 于1 9 9 6 年发布旷9 1 1 定位标准以来，无线定位技术就以 其蕴涵的无穷商业潜力掀起了研究的热潮。全球定位系统是比较成功的定位技 术，它通过g p s 接收器测量来自5 - , 2 4 个卫星信号的到达时间差估算位置，可 以提供接近全球的定位覆盖范围。但是，g p s 在室内和高楼密布的城市由于感 测不到卫星信号而无法定位。从2 0 世纪9 0 年代末期起，国外许多高校和研究 机构开始了室内定位技术的研究。近年来，国内越来越多的学者投入到无线定 位技术的研究中，出现了不少定位技术的发明专利和从事定位技术研究的专业 机构。目前，常用的无线定位技术是通过测量接收到的无线电波参数，根据特 定的算法以判断出被测物体的位置，测量参数一般包括传输时间、信号幅度、 到达角度等。 除了g p s 以外，典型的定位技术还有以下几种： l 、光跟踪技术 第1 章绪论 该技术要求所跟踪目标和探测器之间线性可视，这就把应用局限到了仅室 内的范围且需保证所监测的目标是不透明的。在视频监视系统中，往往在环境 中安装多台摄像设备，连接到一台或几台视频监控器上，对观察对象进行实时 动态地监控，有的甚至可以进行必要的数据储存。光定位技术也被应用于机器 人系统，通过红外线摄像机和红外线发光二极管的一系列协同配合，达到定位 的目的。但是要实现高精度的光定位技术，配备要求比较复杂。 2 、超声波定位技术 该技术由于成本低、结构简单易于实现而被人们广泛采用。超声波定位系统 由若干个应答器和一个主测距器组成，主测距器放置在被测物体上，在微机指令 信号的作用下向位置固定的应答器发射同频率的无线电信号，应答器在收到无线 电信号后同时向主测距器发射超声波信号，得到主测距器与各个应答器之间的距 离。当同时有三个或三个以上不在同一直线上的应答器做出回应时，可以根据相 关计算确定出被测物体所在的二维坐标系下的位置。c r i c k e tl o c a t i o ns u p p o r t s y s t e m 是目前成功使用该项技术的定位系统。但是这类系统需要大量的底层硬件 设施投资，成本太高，无法大面积推广。 3 、射频识别技术 典型的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 收发器发送出某一 频率的无线电波能量，当t a g 内的天线感应到无线电波能量时，会传回含有自身 种类识别码标志、制造商标志的识别资料给r e a d e r ，最后传回主机进行识别与管 理。该系统用活性参考标签t a g 替代离线数据采集，其动态参考信息能够实时捕 捉环境变化，提高定位精度和可信度。活性参考标签t a g 的应用免去了每个测试 点数百次的人工数据采集，且能更好的适应室内环境的波动，提高定位精度。 4 、无线蓝牙技术 该技术是一种短距离低功耗的无线传输技术，支持点到点的话音和数据业 务。在室内安装适当的蓝牙局域网接入点，把网络配置成基于多用户的基础网 络连接模式，就可以获得用户的位置信息，实现移用蓝牙技术定位的目的。采 用该技术作室内短距离定位，其优点是容易发现设备，且信号传输不受视距的 影响，缺点是目前蓝牙器件和设备比较昂贵。 此外，还有利用红外线等技术实现室内无线用户的定位服务，由于可测距 离受到限制，所以没有被广泛采用。 综合以上几种方法，它们都存在复杂度高，需要对现有的通信网络添加辅 助定位的测量设备，并且仍然无法解决在室内环境中存在严重的信号阻挡的问 题，所以有效性和实用性都不能令人满意。 北京工业人学工学硕士学位论文 国外研究成果中，在室内定位系统开发研究方面具有代表性的有： 0 1 i v e t t i 研究实验室研制的a c t i v eb a d g e 3 】室内定位感知系统，是最早的 室内定位跟踪系统之一。它采用了红外线技术实现室内定位，属于无线小区监视 接入的相邻法定位系统。每个待定位的物体使用红外发射机定期发送自身唯一的 i d 识别码。 剑桥大学a t & t 实验室开发的a c t i v eb a t m l 室内定位系统是一个室内超声波厌 线射频定位系统，该系统利用超声波的到达时间来实现定位，属于利用t o a 技术的 三角法定位系统。该系统主要由标识、接收机和监控中心组成。 微软公司研究团队开发的室内跟踪定位的r a d a r 原型系统，该系统结合经验 数据和衰减因子模型，在大量数据采集的基础上通过一定的匹配法则确定目标位 置，提供定位服务和应用。 由麻省理工学院开发的c r i c k e t 5 】是室内超声波无线射频定位系统，属于基 于时间法测距的三角法定位系统。c r i c k e t 的定位依据是空气中声波的传播速度 远低于无线电波的传播速度，可利用无线射频信号为控制参考信号，计算声波信 号的传播时间。 h a r v a r d 大学的m o t e t r a c k 定位系统，该系统最早将无线传感器网络( w s n ) 引入室内定位服务中，并充分展现了w s n 分布式系统的高鲁棒性优势。 s p o t o n 6 1 到系统是基于射频识别( r f i d ) 的室内定位系统。该系统基于信号强 度分析，发展了一种聚合算法对三维空间进行定位。s p o t o n 系统中硬件标签网络 状分布，无需中央控制单元，通过标签测试到的信号强弱来表征标签之间的几何 距离。但是，完整的s p o t o n 系统到目前为止还没有建成。 文献 7 、 8 设计了一种细粒度的定位系统。该系统设计了m e d u s a 平台， m e d u s a 采用m i c a 2 节点，装备超声波模块，超声波收发器有3 m 的传送范围，测量 精度达至1 2 m 。运行在m e d u c a 平台上的集中式和分布式算法用于推断节点位置。 目前国内从事室内定位技术研究的机构主要集中在科研院所和高校。复旦 大学的倪巍、王宗欣提出一种基于接收信号强度测量的室内定位算法【9 】，该算 法通过对现有的路径损耗模型进行修正，引入距离估计误差随机变量，推导出 一种迭代最大似然估计算法，通过有限次的迭代得到令人满意的位置估计；同 济大学的张洁颖分析了一种基于场景指纹的定位算法，这种算法通过在采样点 收集的无线信号的某种与位置有关的特征信息来建立有关目标场景数据库，并 以此来估计目标节点的位置【1 0 1 ；文献 1 1 1 中提出一种基于r s s i 均值的等边三角 形算法，引入信号强度指示敏感区和非敏感区概念，采用高斯模型对非敏感区 的r s s i 数据进行处理，解决了r s s i 易受干扰的问题。 1 4 课题的研究意义 由于在室内环境下对于不同的建筑物而言，室内布置，材料结构，建筑物 第l 章绪论 尺度的不同导致了信号的路径损耗很大，与此同时，建筑物的内在结构会引起 信号的反射，绕射，折射和散射，形成多径现象，使得接收信号的幅度，相位 和到达时间发生变化，造成信号的损失，+ 定位的难度大。其次，室内定位的研 究方法与室外定位不同，对于室内定位最重要的不是得到某个精确的坐标，而 是确定用户在哪个区域。虽然室内定位是定位技术的一种，和室外的无线定位 技术相比有一定的共性，但是室内环境的复杂性和对定位精度和安全性的特殊 要求，使得室内无线定位技术有着不同于普通定位系统的鲜明特点，而且这些 特点是户外定位技术所不具备的。因此，两者区域的标识和划分标准是不同的。 基于室内定位的诸多特点，室内定位技术和定位算法已成为各国科技工作者研 究的热点。如何提高定位精度仍将是今后研究的重点。因此，开发一套精确的 室内定位系统是非常必要的。 无线通信技术的成熟和发展，带动了新兴无线业务的出现，越来越多的应 用都需要自动定位服务。为解决自动定位的问题，基于卫星通信的全球定位系 统( g p s ) 出现了，其良好的定位精度解决了很多军事和民用的实际问题。但是， 当需要定位的物体位于建筑物内部，如办公大楼、仓库、矿道内，其定位精度 就明显下降了甚至无法进行工作。因此，必须研究新的室内定位技术以弥补g p s 的不足。研究针对室内特定环境的定位技术和定位系统是十分迫切和有意义的。 基于信号强度的定位【1 2 】与其它各种定位技术相比，最大的优点就是我们能够充 分利用现有的基本系统，只需要最少的辅助设备，就可以建立定位系统。显然， 获得r s s 信息比得到多径特征、到达时间( t o a ) 和到达角度( a o a ) 远远容易的 多，后三种信息的获得都需要额外的信号处理的过程。因此，基于接收信号强 度的无线局域网室内定位是定位领域的一个新的研究热点。 1 5 论文的研究思路与内容安排 课题的思路是以t i 公司的c c 2 4 3 1 z d k t l 3 】定位开发系统为硬件平台，研究和 探索能够实现建筑物内人员精确定位的理论和实现技术。论文研究了基于信号 强度的定位算法的关键技术和功能实现。主要内容包括： 第一章：绪论。介绍了论文的研究背景、国内外研究现状及课题的研究意 义，并对论文做了概括性的介绍。 第二章：无线定位技术概述及典型定位算法。阐述了典型的定位技术方案， 讨论了定位算法的分类，分析了定位性能的评价指标。 第三章：基于r s s i 的定位算法的研究。对经典的距离损耗模型进行研究， 找到适合本文算法的模型，在参数优化后的距离损耗模型的基础上，详细介绍 了本文提出的基于r s s i 的定位算法方案及算法流程，并对算法进行软件实现， 分析实验结果，验证了算法的可行性。 第四章：z i g b e e 网络定位系统及算法的硬件实现。首先介绍了z i g b e e 技 北京丁业大学工学硕十学位论文 术的协议架构、拓扑结构及应用前景，主要介绍了支持z i g b e e 协议的方案的片 上系统c c 2 4 3 1 和定位系统开发平台c c 2 4 3 1 z d k ，最后在此定位平台上完成了算 法的硬件实现，通过和系统自带算法的定位性能的比较，验证了本文算法在提 高定位精度方面的优越性。 第五章：对全文工作进行总结，提出今后研究的方向和建议。 1 6 本章小结 本章首先介绍了课题的背景、来源、意义，然后全面概括了无线定位中的 一些关键技术的发展状况和研究内容，最后，结合定位系统的主要模块和算法 流程框架介绍了论文的主要内容、组织结构及整体安排。 第2 章无线网络定位技术 第2 章无线网络定位技术 2 1 无线定位的基本原理和数学模型 1 定位问题的最小二乘法 在无线定位系统中，对移动节点进行位置估计采用最广泛的算法是最小二 乘算法( l s ) 1 4 】，该算法广泛应用于使用距离的定位系统中。在蜂窝网络中， 只要根据某种测量值建立了相应的特征方程，就能求解出移动节点的位置。 设根据测量值建立的方程为： r = a x( 2 1 ) 其中，y 是已知的n x l 维向量，a 是n m 矩阵。如果n m 则系统方程数大 于未知数数目，可以利用最小二乘法获得x 的最优估计。 最小二乘思想是使得误差的平方和最小，即 ( x ) = ( 么x 一】，) 2 = ( 似一y ) 7 ( 么x y ) ( 2 - 2 ) 对以上的代价函数求最小值，如果么7 彳是非奇异的，可得 x = ( 彳r 么) 1a 7 y ( 2 3 ) 在实际应用中可以根据每个测量值的精度，在最小二乘中采用不同的权值， 合理选择加权矩阵w ，可有效提高定位精度。理论证明，当测量之取误差方差 矩阵的逆矩阵时估计误差的方差最小，但实际应用中如何定义w 加权矩阵还有 待进一步研究。 2t o a 定位模型 图2 1t o a 定位模型 f i g 2 1t h ei d c a t i o nm o d e lo ft o am e t h o d - 7 - 北京丁业大学1 二学硕上学位论文 t o a 定位的圆周模型【1 5 1 如图2 1 所示，由m s 与各b s 的位置关系得： 巧- - 4 ( x , 一工) 2 + ( z y ) 2 ( 2 - 4 ) 将上式两边平方再移项，得： x i x + y i y 一0 5 r 2 = 寺( 曩2 + 】，2 一r 2 ) ，r = x 2 + y 2 ( 2 5 ) 把x 、y 、r 2 看作未知数，则上式为线性方程。 3t d o a 定位的双曲线模型 ( x 3 ，y 3 ) 图2 - 2t d o a 定位模型 f i g 2 - 2t h el o c a t i o nm o d e lo f t d o a t d o a 定位的双曲线模型如图2 - 2 所示。 ，；= ( 置一x ) 2 + ( 1 一y ) 2 ，；，：，；一巧：r 夏_ 二：了r ：而一e 夏_ 二：了f 而 利用这两个基本方程得到： ，；，1 2 + 2 ，1 吒= k 一2 五，l x 一2 r , 1 y k 其中k = t + z ，整理得： 五，l 工+ i ，y + 吒。，i = 去( k k 一，。2 ) 将工，y ，i 看成未知数，则化为线性方程。 4a o a 定位的方位线模型 ( 2 - 6 ) ( 2 7 ) ( 2 - 8 ) ( 2 9 ) 第2 章无线网络定位技术 b s lb s 2 图2 - 3a o a 定位 f i g 2 - 3t h el o c a t i o nm o d e lo f a o a a o a 测量的方位线模型如图2 3 所示，a o a 测量方程为： 1 ，一y t a n ( f l , ) = 等，f = 1 ( 2 1 0 ) x 一五i 求解上述非线性方程组，可以得到移动节点的位置。 由于非视距传播对a o a 的影响很大等原因，单纯的a o a 定位往往精度较低。 但h o h 与t o a 或t d o a 结合的混和定位可以达到较高精度，这时h o h 可被看作辅 助信息，既可以提高精度，又可以在基站数目较少时帮助定位。 2 2 衡量定位算法优劣的性能指标 对定位算法的性能评价指标主要有定位精度、节点密度、容错和自适应性、 功耗和代价、网络规模等几个部分【1 6 】。 1 、定位精度：定位技术首要的评价指标就是定位精度，目前最常用的指标 是均方误差( m s e ) 、均方根误差( i s e ) 、克拉美一罗下界( c r l b ) 圆误差 概率( c e p ) 、几何精度因子( g d o p ) 等。也可以用误差值与节点无线射程的 比例表示定位精度，例如，定位精度为2 0 表示定位误差相当于节点无线射程 的2 0 。 2 、锚节点密度：锚节点定位通常依赖人工部署或g p s 实现。人工部署锚 节点的方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展 性。锚节点密度的高低直接决定了定位精度。因此，锚节点密度也是评价定位 系统和算法性能的重要指标之一 3 、节点密度：节点密度增大不仅意味着网络部署费用的增加，而且会因为 节点间的通信冲突问题带来有限带宽的阻塞节点密度通常以网络的平均连通 度来表示。许多定位算法的精度受节点密度的影响，如d v - h o p 算法仅可在节 点密集部署的情况下合理地估算节点位置。 4 、容错和自适应性：通常，定位系统和算法都需要比较理想的无线通信环 北京t 业大学工学硕士学位论文 境和可靠的网络节点设备。但在真实应用场合中常会有以下的问题，外界环境 中存在严重的多径传播、衰减、非视距、通信盲点等问题。外界影响和节点硬 件精度限制造成节点间点到点的距离或角度测量误差增大的问题。由于环境、 能耗和其他原因，物理地维护或替换传感器节点或使用其他高精度的测量手段 常常是十分困难或不可行的。因此，定位系统和算法的软、硬件必须具有很强 的容错性和自适应性，能够通过自动调整或重构纠正错误、适应环境、减小各 种误差的影响，以提高定位精度。 5 、功耗和代价：功耗是对w s n 的设计和实现影响最大的因素之一。由于 传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的 定位所需的计算量、通信开销、存储开销、时间复杂性是一组关键性指标：定 位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系统的安装 时间、配置时间、定位所需时间和空间代价包括一个定位系统或算法所需的基 础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系统或 算法的基础设施、节点设备的总费用。 6 、网络规模：不同的定位系统或算法也许可在园区内、建筑物内、或仅仅 是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内，一 种技术可以定位多少目标也是一个重要的评价指标。 上述性能指标不仅是评价w s n 自身定位系统和算法的标准，也是其设计 和实现的优化目标。这些性能指标是相互关联的，必须根据应用的具体需求做 出权衡，综合考虑以上w s n 定位系统标准。以选择和设计合适的无线传感器 网路定位算法实现定位。 2 3 基于测距技术的定位算法 根据定位过程中是否测量实际节点的距离，把定位算法分为：基于距离的 ( r a n g e b a s e d ) 定位算法和距离无关的( r a n g e - f r e e ) 定位算法【1 7 】。前者需要测量 相邻节点间的绝对距离或方位，并利用节点间的实际距离来计算未知节点的位 置；后者无需测量节点的绝对距离或方位，而是利用节点间的估计距离计算节 点位置。 第2 章无线网络定位技术 2 3 1 三边测量定位技术 图2 - 4 三边定位法示意图 f i g 2 - 4t h ec h a r to f t r i l a t e r a ll o c a t i o n 三边测量法【1 8 1 ( t r i l a t e r a t i o n ) 如图2 4 所示，已知a 、b 、c 三个节点坐 标分别为( x 。，乃) 、( 恐，儿) 、( 而，此) ，以及它们到未知目标节点的距离分别为 吐，吃，吃，假设目标节点的坐标为( x ，y ) 。那么可以建立下列公式： ( x 一而) 2 + ( y y 1 ) 2 ( x 一而) 2 + ( y 一儿) 2 ( z 一而) 2 + ( j ，一乃) 2 盔2 彰 d ； ( 2 1 1 ) 通过求解上面的方程就可以有效获得目标节点的位置坐标。 2 3 2 三角测量法 三角定位法( t r i a n g u l a t i o n ) ，已知a 、b 、c 三个节点的坐标分别为 ( x 。，y 。) ，( x ：，y ：) ，( x 。，y 。) ，目标节点相对于节点a 、b 、c 角度分别为：z a d b ，a d c ， z b d c ，假设目标节点坐标( x ，y ) 。 对于节点a ，c 和角z a d c ，如果弧段a c 在z k a l 3 c 内，那么能够唯一确定一 个圆，设圆心为0 ( x 。，y 。) ，半径为r l ，那么o r - - z a o c - ( 2 7 【- - 2 z a c d ) ，并建立 下列公式： r 。= _ ( 嘞一西) 2 + ( 一m ) 2 = ，i ( 一恐) 2 + ( - y 2 ) 2 = r 2 ( 2 一1 2 ) ( x o 一屯) 2 + ( - y 0 2 = 2 ，i 2 2 ，i 2c o s 由上式能够确定圆心0 点的坐标和半径r 。同理可获得a 、b ，a d b 和b 、 北京t 业大学工学硕士学位论文 c ，z b d c 分别对应的圆心坐标和半径。最后利用三边测量法，根据求得的圆心 坐标就能求出目标节点的位置。 2 3 3 极大似然估计 ( a ) i ( 五- x ) 2 + ( m - y ) 2 = 砰 i ( 五- x ) 2 + ( m - y ) = f# 一一2 ( 一) x 一拜一谚- 2 ( y , - y ) y = 圻一 l ，一# 一2 ( 一- x ) x - y l ，一一- 2 ( y 一，- y ) y = 。一砰 彳慑_ 矧，b - x= e x 2 ：乏捌小 习 彳：i ； i ，= i ； i ，x = l 2 ( 一，) 2 ( 虬_ 一y 。) jl 川一+ 一q 一一+ 一，j uj 第2 章无线网络定位技术 2 4 与距离无关的定位算法 距离无关的定位技术无需测量节点间的绝对距离或方位，降低了对节点硬 件的要求，但定位的误差也相对有所增加。目前提出了两类主要的距离无关的 定位方法：一类方法是先对未知节点和信标节点之间的距离进行估计，然后利 用三边测量法或极大似然估计法进行定位；另一类方法是通过邻居节点和信标 节点确定包含未知节点的区域，然后把这个区域的质心作为未知节点的坐标。 2 4 1 质心算法 多边形的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐 标。质心定位算法首先确定包含未知节点的区域，计算这个区域的质心，并将 其作为未知节点的位置。设未知节点接收到来自参考节点a ( x 。，y 。) ，b ( x ：，y ：) ，c ( x 。，y 。) ，d ( x 。，y 。) ，e ( x 。，y 。) 的信号，则待定位节点的坐标为： f ( 训) = l t 五+ 屯+ 毛+ 而+ 毛m + 咒+ y 3 + y 4 + y s 5 ( 2 1 5 ) 在质心定位算法中，信标节点周期性地向临近节点广播信标分组，信标分 组中包含信标节点的标识号和位置信息。当未知节点接收到来自不同信标节点 的信标分组数量超过某一门限或接收一定时间后，就确定自身位置为这些信标 节点所组成的多边形的质心。由于质心算法完全基于网络连通性，无需信标节 点和未知节点之间的协调，因此简单、易于实现。 2 4 2d v - h o p 算法 d v h o p 算法的核心思想是用平均每跳距离与未知节点到锚节点跳数的乘 积，表示未知节点到锚节点的距离。算法的整个过程是：首先，网络中所有的 锚节点使用距离矢量交换协议，将锚节点的位置信息和跳数信息广播到整个网 络中，使网络中的所有的节点获取与锚节点的跳数。其次，锚节点根据正确接 收到的跳数信息，计算该锚节点的平均每跳距离，并将其广播到整个网络中非 锚节点利用接收到的跳数信息和平均每跳距离值计算与锚节点的距离。最后， 非锚节点执行三边测量实现定位。 2 4 3d d i s t a n c e 算法 d d i s t a n c e 算法与d h o p 类似，所不同的是相邻节点使用r s s i 测量节点 间点到点距离，然后利用类似于距离矢量路由的方法传播与锚节点的累计距离。 当未知节点获得与3 个或更多锚节点的距离后使用三边测量定位。d - d i s t a n c e 算法也仅适用于各向同性的密集网络。实验显示，该算法的定位精度为2 0 ( 网 络平均连通度为9 ，锚节点比例为1 0 ，测距误差小于1 0 ) ，但随着测距误差 的增大，定位误差也急剧增大。 北京t ! i r 大学t 学硕上学位论文 2 4 4 凸规划算法 加州大学d o h e r t y 等提出凸规划法将节点间点到点的通信连接视为节点位 置的几何约束，把整个网络模型化为一个凸集，从而将节点定位问题转化为凸 约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的定位解 决方案，同时也给出了一种计算未知节点有可能存在的矩形空间的方法。如图 2 6 所示，根据未知节点与锚节点间的通信连接和节点无线射程，计算出未知 节点可能存在的区域( 图中圆相交部分) ，并得到相应矩形区域，然