基于UWB的地下定位算法和拓扑优化

工程科学学报，第40卷，第6期：743-753,2018年6月 Chinese Journal of Engineering,Vol.40,No.6:743-753,June 2018 DOI:10.13374/j.issn2095-9389.2018.06.013:http://journals.ustb.edu.cn 基于UWB的地下定位算法和拓扑优化 孟 宇四，肖小凤，赵坤 北京科技大学机械工程学院，北京100083 ☒通信作者，E-mail:myu@ustb.cdu.cn 摘要地下定位面对环境恶劣、干扰、多径等影响，常规算法难以获得高精度的定位结果，同时井下环境多为狭长的巷道， 不利于布置定位所需的锚节点，而井下锚节点的布置通常对定位结果有较大影响，因而使用普通的定位方法不足以满足智能 采矿所需的高精度定位需求.本文对传统的三边定位算法进行分析，总结了传统三边定位结果产生误差的原因，并提出了改 进的算法，通过仿真实验验证了改进算法的有效性.同时通过理论分析误差带，使用最大绝对定位误差用于仿真分析拓扑结 构对定位结果精度的影响，提出了对拓扑结构的优化原则，能够根据环境特点以实现定位区域内平均最大绝对定位误差最小 为原则得出最优拓扑结构.文中设置了仿真实验和实地实验对改进的算法和拓扑结构优化方法进行了验证，实验结果中，改 进的算法能够在相同拓扑结构下减小15%~43%的误差，而在相同算法下优化的拓扑结构能够减小17%~65%，二者结合能 够减小误差达74%.结果表明，在相同的定位条件下，改进的定位算法能够明显提高定位结果的精度，同时定位结果与拓扑结 构之间也有着密切的联系，根据实际环境灵活布置拓扑结构能够使定位结果的精度进一步提高，将改进的算法与拓扑结构优 化方法结合可以实现更高的定位精度. 关键词地下定位：定位算法：拓扑优化：算法优化：超宽带无线定位 分类号TP393.1 An underground localization algorithm and topology optimization based on ultra-wide- band MENG Yu,XIAO Xiao-feng,ZHAO Kun School of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:myu@ustb.edu.cn ABSTRACT Development of context-aware technologies and rapid advancement in communication are essential parts of most indus- tries,such as underground mining,pervasive medical care,smart space,and wireless sensor network surveillance.On occasions that require positioning services,location techniques offer convenience and may even save lives.In underground mining,not only do the miners work in a hostile environment but the environment itself threatens their lives.Thus,determining the precise location of people and objects in underground environments is essential.However,GPS cannot be used for practical application underground and under- ground localization seems to be the most feasible way to provide positional information to mining vehicles.The localization of under- ground vehicles has been a critical obstacle in the development of intelligent mining vehicles.Faced with the bad environment,interfer- ence,and multipaths among other effects,it is difficult to obtain high-precision positioning results using conventional algorithms.In addition,the underground environment is mostly made up of long narrow tunnels,which is not conducive to an arrangement of anchor nodes,and the layout of underground anchor nodes usually has great influence on the positioning results.Therefore,ordinary positio- ning methods do not meet the high-precision positioning requirements of intelligent mining.In this paper,traditional trilateration was analyze,the reasons for error was summarized,and an improved algorithm was proposed.Simulation results showed the effectiveness of 收稿日期：201707-16 基金项目：国家高技术研究发展计划(863计划)资助项目(2011AA060408):国家重点研发计划资助项目(2016YFC0802905)

工程科学学报，第 40 卷，第 6 期: 743--753，2018 年 6 月 Chinese Journal of Engineering，Vol． 40，No． 6: 743--753，June 2018 DOI: 10． 13374 /j． issn2095--9389． 2018． 06． 013; http: / /journals． ustb． edu． cn 基于 UWB 的地下定位算法和拓扑优化 孟 宇，肖小凤，赵 坤 北京科技大学机械工程学院，北京 100083 通信作者，E-mail: myu@ ustb． edu． cn 摘 要 地下定位面对环境恶劣、干扰、多径等影响，常规算法难以获得高精度的定位结果，同时井下环境多为狭长的巷道， 不利于布置定位所需的锚节点，而井下锚节点的布置通常对定位结果有较大影响，因而使用普通的定位方法不足以满足智能 采矿所需的高精度定位需求． 本文对传统的三边定位算法进行分析，总结了传统三边定位结果产生误差的原因，并提出了改 进的算法，通过仿真实验验证了改进算法的有效性． 同时通过理论分析误差带，使用最大绝对定位误差用于仿真分析拓扑结 构对定位结果精度的影响，提出了对拓扑结构的优化原则，能够根据环境特点以实现定位区域内平均最大绝对定位误差最小 为原则得出最优拓扑结构． 文中设置了仿真实验和实地实验对改进的算法和拓扑结构优化方法进行了验证，实验结果中，改 进的算法能够在相同拓扑结构下减小 15% ～ 43% 的误差，而在相同算法下优化的拓扑结构能够减小 17% ～ 65% ，二者结合能 够减小误差达 74% ． 结果表明，在相同的定位条件下，改进的定位算法能够明显提高定位结果的精度，同时定位结果与拓扑结 构之间也有着密切的联系，根据实际环境灵活布置拓扑结构能够使定位结果的精度进一步提高，将改进的算法与拓扑结构优 化方法结合可以实现更高的定位精度． 关键词 地下定位; 定位算法; 拓扑优化; 算法优化; 超宽带无线定位 分类号 TP393. 1 收稿日期: 2017--07--16 基金项目: 国家高技术研究发展计划( 863 计划) 资助项目( 2011AA060408) ; 国家重点研发计划资助项目( 2016YFC0802905) An underground localization algorithm and topology optimization based on ultra-wide￾band MENG Yu ，XIAO Xiao-feng，ZHAO Kun School of Mechanical Engineering，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: myu@ ustb． edu． cn ABSTＲACT Development of context-aware technologies and rapid advancement in communication are essential parts of most indus￾tries，such as underground mining，pervasive medical care，smart space，and wireless sensor network surveillance． On occasions that require positioning services，location techniques offer convenience and may even save lives． In underground mining，not only do the miners work in a hostile environment but the environment itself threatens their lives． Thus，determining the precise location of people and objects in underground environments is essential． However，GPS cannot be used for practical application underground and under￾ground localization seems to be the most feasible way to provide positional information to mining vehicles． The localization of under￾ground vehicles has been a critical obstacle in the development of intelligent mining vehicles． Faced with the bad environment，interfer￾ence，and multipaths among other effects，it is difficult to obtain high-precision positioning results using conventional algorithms． In addition，the underground environment is mostly made up of long narrow tunnels，which is not conducive to an arrangement of anchor nodes，and the layout of underground anchor nodes usually has great influence on the positioning results． Therefore，ordinary positio￾ning methods do not meet the high-precision positioning requirements of intelligent mining． In this paper，traditional trilateration was analyze，the reasons for error was summarized，and an improved algorithm was proposed． Simulation results showed the effectiveness of

·744 工程科学学报，第40卷，第6期 the improved algorithm.In addition,the principle of topology optimization was proposed by theoretically analyzing the error band and u- sing the maximum absolute positioning error to simulate the influence of topology on positioning accuracy.According to the characteris- tics of the environment,minimizing the average maximum absolute positioning error was the principle of topology optimization.Here, simulation and field experiments were carried out to verify the improved algorithm and topology optimization method.The experimental results show that the improved algorithm can reduce the error by 15%-43%under the same topology,the optimized topology can re- duce the error by 17%-65%,and a combination of the two can reduce the error by 74%.The results show that under the same locali- zation conditions,the proposed algorithm can significantly improve the accuracy of the localization results.In addition,there is a close relationship between localization result and topology structure.Based on the actual environment,choosing a flexible topology layout can further improve positioning accuracy,and combining the improved algorithm with the topology optimization method can achieve a higher positioning accuracy. KEY WORDS underground localization:localization algorithm:topology optimizing:algorithm optimizing:ultra-wideband localiza- tion UWB技术最早出现于1960年的雷达应用，如 区域同时获得精准的定位结果.仿真结果显示其组 今己发展成为集无线数据通信和实时感知定位于一 合方案能有较好的定位表现.Bialer等因提出一种 体的新兴技术.相比其他测距手段，UWB信号具有 利用最大似然估计法进行UWB定位的方案，有效 传输速率高、系统容量大、抗干扰能力强、多径分辨 对抗了室内低信噪比环境下的多路径效应，取得了 率高等优点，非常适合用于精确测距和定位，因此利 不错的定位效果.Ershadh提出了一种UWB传感 用UWB技术的定位方案己经越来越广泛.目前使 器天线的设计方案，提升了UWB室内定位的整体 用UWB进行定位的算法多种多样，使用最多的是 性能，但是该方案评价整体定位精度时并没有将定 基于TOA、TDOA、AOA等的方法，算法上多为三边 位区域的空间特性考虑在内，并且所用的硬件成本 定位、三角形定位、最小二乘法等 较高，不适合大范围的普及利用.英国Ubisense公 在室外应用方面，Takahara等将UWB技术 司开发的基于UWB的室内位置感知系统，以超宽 应用于车载雷达，协助雷达通信和测量前车车距，以 带信号为载体，通过TDOA和AOA定位技术相结 提高行车安全性.Fall等回研究了将UWB技术和 合，利用标签设备向UWB接收器发送UWB信号， Time Reversal(TR)技术应用于铁路运输的定位系 测距范围达到50m,精度可达l5cm.Zebra推出 统，利用UWB在精度方面的不错表现，和TR通道 了Dart UWB系统，精度达到30cm,测距范围达到 预滤波有利于信号的检测以及增加在目标区域所接 IO0m回.Chehri等a针对在像地下煤矿井道这样 收的信号的能量的优点，仿真实验表明其定位精度 的狭长环境中的定位，用UWB采集距离信号和 优于UWB单独定位的方法. TOA作定位算法，提出了信号分类算法，对接收到 在室内定位方面，Salman和Willms使用UWB 的UWB信号强度进行分类，并将第一次采集的信 技术设计了一种名为CoLORbot的移动机器人，利 号和信号强度等级高的信号应用到定位计算中，实 用UWB-Radar遥感成像算法和天线的组合，以完 验结果显示，采用信号分类算法要比普通算法定位 成在未知的室内环境的定位.在UWB平均功率延 在可视距离和非可视距离下的定位结果精度高 迟分布不总是可知的情况下，Shang等向提出一种 国内超宽带定位研究起步晚，但是受到了国家 将TOA与APDP联合的方法，首先建立以APDP为 的高度重视，很多科研机构和高校将目光投向了这 参量的模型，并用最小二乘法逼近求解，再用估计的 一极具发展潜力的技术.南京唐恩科技公司开 APDP值建立似然方程和TOA的最大似然估计量， 发出了国内第一套民用的UWB定位系统：Loca- 仿真结果显示，改进的TOA算法能得到更精确的定 teTM UWB定位系统，该系统实现了2D/3D的实时 位结果.Chu和Ganz介绍了一种室内三维定位系 定位，该公司于近几年陆续开发了用于仓储物流、机 统，该系统由分层定位方案和由UWB传感器及标 场人员定位、工业自动化的系统.成都昂迅电子有 签组成的基于UWB技术的定位网络.UWB网络可 限公司的LINK UWB无线联网高精度定位系统首 以利用UWB信号的低功率传输、多路径衰落的鲁 创性的采用全无线技术解决了定位数据传输，网络 棒性、超细时间分辨率和多径同时传输特性.将 同步控制，标签定位时序安排等技术难题，提供用户 UWB的特性与分层定位方案组合可充分扩大定位 极大的组网灵活性和工程便利性.真正实现了快

工程科学学报，第 40 卷，第 6 期 the improved algorithm． In addition，the principle of topology optimization was proposed by theoretically analyzing the error band and u￾sing the maximum absolute positioning error to simulate the influence of topology on positioning accuracy． According to the characteris￾tics of the environment，minimizing the average maximum absolute positioning error was the principle of topology optimization． Here， simulation and field experiments were carried out to verify the improved algorithm and topology optimization method． The experimental results show that the improved algorithm can reduce the error by 15% --43% under the same topology，the optimized topology can re￾duce the error by 17% --65% ，and a combination of the two can reduce the error by 74% ． The results show that under the same locali￾zation conditions，the proposed algorithm can significantly improve the accuracy of the localization results． In addition，there is a close relationship between localization result and topology structure． Based on the actual environment，choosing a flexible topology layout can further improve positioning accuracy，and combining the improved algorithm with the topology optimization method can achieve a higher positioning accuracy． KEY WOＲDS underground localization; localization algorithm; topology optimizing; algorithm optimizing; ultra-wideband localiza￾tion UWB 技术最早出现于 1960 年的雷达应用，如 今已发展成为集无线数据通信和实时感知定位于一 体的新兴技术． 相比其他测距手段，UWB 信号具有 传输速率高、系统容量大、抗干扰能力强、多径分辨 率高等优点，非常适合用于精确测距和定位，因此利 用 UWB 技术的定位方案已经越来越广泛． 目前使 用 UWB 进行定位的算法多种多样，使用最多的是 基于 TOA、TDOA、AOA 等的方法，算法上多为三边 定位、三角形定位、最小二乘法等． 在室外应用方面，Takahara 等［1］ 将 UWB 技术 应用于车载雷达，协助雷达通信和测量前车车距，以 提高行车安全性． Fall 等［2］研究了将 UWB 技术和 Time Ｒeversal( TＲ) 技术应用于铁路运输的定位系 统，利用 UWB 在精度方面的不错表现，和 TＲ 通道 预滤波有利于信号的检测以及增加在目标区域所接 收的信号的能量的优点，仿真实验表明其定位精度 优于 UWB 单独定位的方法． 在室内定位方面，Salman 和 Willms［3］使用 UWB 技术设计了一种名为 CoLOＲbot 的移动机器人，利 用 UWB--Ｒadar 遥感成像算法和天线的组合，以完 成在未知的室内环境的定位． 在 UWB 平均功率延 迟分布不总是可知的情况下，Shang 等［4］提出一种 将 TOA 与 APDP 联合的方法，首先建立以 APDP 为 参量的模型，并用最小二乘法逼近求解，再用估计的 APDP 值建立似然方程和 TOA 的最大似然估计量， 仿真结果显示，改进的 TOA 算法能得到更精确的定 位结果． Chu 和 Ganz［5］介绍了一种室内三维定位系 统，该系统由分层定位方案和由 UWB 传感器及标 签组成的基于 UWB 技术的定位网络． UWB 网络可 以利用 UWB 信号的低功率传输、多路径衰落的鲁 棒性、超细时间分辨率和多径同时传输特性． 将 UWB 的特性与分层定位方案组合可充分扩大定位 区域同时获得精准的定位结果． 仿真结果显示其组 合方案能有较好的定位表现． Bialer 等［6］提出一种 利用最大似然估计法进行 UWB 定位的方案，有效 对抗了室内低信噪比环境下的多路径效应，取得了 不错的定位效果． Ershadh［7］提出了一种 UWB 传感 器天线的设计方案，提升了 UWB 室内定位的整体 性能，但是该方案评价整体定位精度时并没有将定 位区域的空间特性考虑在内，并且所用的硬件成本 较高，不适合大范围的普及利用． 英国 Ubisense 公 司开发的基于 UWB 的室内位置感知系统，以超宽 带信号为载体，通过 TDOA 和 AOA 定位技术相结 合，利用标签设备向 UWB 接收器发送 UWB 信号， 测距范围达到 50 m，精度可达 15 cm［8］． Zebra 推出 了 Dart UWB 系统，精度达到 30 cm，测距范围达到 100 m［9］． Chehri 等［10］针对在像地下煤矿井道这样 的狭长 环 境 中 的 定 位，用 UWB 采集距离信号和 TOA 作定位算法，提出了信号分类算法，对接收到 的 UWB 信号强度进行分类，并将第一次采集的信 号和信号强度等级高的信号应用到定位计算中，实 验结果显示，采用信号分类算法要比普通算法定位 在可视距离和非可视距离下的定位结果精度高． 国内超宽带定位研究起步晚，但是受到了国家 的高度重视，很多科研机构和高校将目光投向了这 一极具发展潜力的技术［11］． 南京唐恩科技公司开 发出了国内第一套民用的 UWB 定位系统: iLoca￾teTM UWB 定位系统，该系统实现了 2D /3D 的实时 定位，该公司于近几年陆续开发了用于仓储物流、机 场人员定位、工业自动化的系统． 成都昂迅电子有 限公司的 LINK UWB 无线联网高精度定位系统首 创性的采用全无线技术解决了定位数据传输，网络 同步控制，标签定位时序安排等技术难题，提供用户 极大的组网灵活性和工程便利性． 真正实现了快 · 447 ·

孟字等：基于UWB的地下定位算法和拓扑优化 ·745· 速、高效搭建定位系统，满足多种复杂环境和应急状 合记为A().只要存在3个或更多的锚节点，就有 态下的定位需求回 可能估计所有节点的坐标，如图1所示.己知信息 国内外对UWB的研究仍在继续，但目前仍然 包括测距结果集合D和锚节点位置集合P: 没有专门针对地下采矿环境的高精度定位算法.其 [D=(dlieSUF,jeA,(i)} 中Chehri等a提出的信号分类算法虽然是针对地 (1) IP={(x,y)lieF) 下煤矿井道的狭长环境中的定位，但是其在视距下 定位的目的就是要依据D与P。重构出集合S, 的定位的误差高达1m,非视距下更高达1.5m以 即： 上，范围远远无法达到智能采矿的定位要求.因此 Ps={(xi,y:)lieS}=f(D,Pp) (2) 本文致力于提高此类环境下的定位精度 式中，f(·)代表位置定位算法，(x:,y)是锚节点i的 1基于三边定位的算法改进 坐标，dn是节点i与节点j之间的测距结果，通过估 计测距信号的TOA获得，即： 三边定位算法基于几何学的原理来计算待测目 d,=c听 (3) 标的位置，利用三个锚节点为圆心，以锚节点到目标 式中，为节点i,j之间的到达时间的估计结果，c 点的距离为半径做圆，得到三个圆的交点，通过方程 为UWB信号在空气中的传播速度 组求解.该方法在实现上分为测距和定位两个 则未知节点j的坐标求解为： 阶段.三边定位算法由于其原理简单、容易实现等 (-x)2+(y-y)2=正 (4) 优点，在定位中得到了广泛应用，但其精度则难以保 障.采用增加锚节点数量的方法可以在一定程度上 提高三边定位精度，但由于超宽带无线定位锚节点 错节点2 单价较高，在超宽带无线定位中通过增加锚节点数 量的方法来提高定位精度不可取，因此需要改进算 真实值 估计值 法，使其在相同条件下的定位结果精度更高. ● 1.1三角测量法和质心算法 锚节点1 错节点3 三角测量法使用三角形的几何特征来定位目标 节点，它有两种派生算法：最小二乘法和角度测量算 法.最小二乘法通过测量目标节点与多个参考节点 图1TOA原理 之间的距离来对目标节点进行定位.故最小二乘法 Fig.1 Principle of TOA 也被称为测距技术.目前较为常用的测距方法 1.1.2质心算法 主要有基于接收信号强度(received signal strength, 质心算法是基于几何关系的定位算法，应用在 RSS)测量的方法、基于到达时间(time of arrival, 三边定位中，利用3个圆相交的交点形成的三角形 TOA)测量的方法、基于到达时间差(time difference 的几何质心来估计目标位置，如图2所示. of arrival,TDOA)测量的方法.其中TOA和TDOA 是目前使用较多的方法.角度测量一般采用基于信 号到达角度(angle of arrival,AOA)测量的方法，指 纹信息的获取一般采用RSS. 1.1.1TOA测距原理 交点2厦 UWB信号的脉冲的时间宽度在纳秒级，占用 真实值 的带宽在1GHz以上，因此具有高精度的测距能 交点1 力.基于TOA测距估计技术，可以从UWB信号的 交点3 高时间分辨率中受益，充分利用UWB极宽带宽的 特性. 图2质心算法原理 在一个二维平面上，设有N个未知节点i(i=1, Fig.2 Principle of the centroiding algorithm …,N),构成集合S;有M个参考节点jG=1,…,M) (锚节点)，组成集合F.每个节点i只能产生有限 假设这3个交点的坐标分别为Q(x1,）,Q2 功率的信号，与锚节点j能够通信的节点组成的集 (x2y2）,Q3(x3y3),则动点的坐标(x,y)计算式为：

孟 宇等: 基于 UWB 的地下定位算法和拓扑优化 速、高效搭建定位系统，满足多种复杂环境和应急状 态下的定位需求［12］． 国内外对 UWB 的研究仍在继续，但目前仍然 没有专门针对地下采矿环境的高精度定位算法． 其 中 Chehri 等［10］提出的信号分类算法虽然是针对地 下煤矿井道的狭长环境中的定位，但是其在视距下 的定位的误差高达 1 m，非视距下更高达 1. 5 m 以 上，范围远远无法达到智能采矿的定位要求． 因此 本文致力于提高此类环境下的定位精度． 1 基于三边定位的算法改进 三边定位算法基于几何学的原理来计算待测目 标的位置，利用三个锚节点为圆心，以锚节点到目标 点的距离为半径做圆，得到三个圆的交点，通过方程 组求解［13］． 该方法在实现上分为测距和定位两个 阶段． 三边定位算法由于其原理简单、容易实现等 优点，在定位中得到了广泛应用，但其精度则难以保 障． 采用增加锚节点数量的方法可以在一定程度上 提高三边定位精度，但由于超宽带无线定位锚节点 单价较高，在超宽带无线定位中通过增加锚节点数 量的方法来提高定位精度不可取，因此需要改进算 法，使其在相同条件下的定位结果精度更高． 1. 1 三角测量法和质心算法 三角测量法使用三角形的几何特征来定位目标 节点，它有两种派生算法: 最小二乘法和角度测量算 法． 最小二乘法通过测量目标节点与多个参考节点 之间的距离来对目标节点进行定位． 故最小二乘法 也被称为测距技术［14］． 目前较为常用的测距方法 主要有基于接收信号强度( received signal strength， ＲSS) 测量的方法、基于到达时间( time of arrival， TOA) 测量的方法、基于到达时间差( time difference of arrival，TDOA) 测量的方法． 其中 TOA 和 TDOA 是目前使用较多的方法． 角度测量一般采用基于信 号到达角度( angle of arrival，AOA) 测量的方法，指 纹信息的获取一般采用 ＲSS． 1. 1. 1 TOA 测距原理 UWB 信号的脉冲的时间宽度在纳秒级，占用 的带宽在 1 GHz 以上，因此具有高精度的测距能 力． 基于 TOA 测距估计技术，可以从 UWB 信号的 高时间分辨率中受益，充分利用 UWB 极宽带宽的 特性． 在一个二维平面上，设有 N 个未知节点 i( i = 1， …，N) ，构成集合 S; 有 M 个参考节点 j( j = 1，…，M) ( 锚节点) ，组成集合 F． 每个节点 i 只能产生有限 功率的信号，与锚节点 j 能够通信的节点组成的集 合记为 Aj ( i) ． 只要存在 3 个或更多的锚节点，就有 可能估计所有节点的坐标，如图 1 所示． 已知信息 包括测距结果集合 D 和锚节点位置集合 PF : D = { ^ dij | i∈S∪F，j∈Aj ( i) } PF = { ( xi，yi { ) | i∈F} ( 1) 定位的目的就是要依据 D 与 PF 重构出集合 S， 即: PS = { ( xi，yi ) | i∈S} = f( D，PF ) ( 2) 式中，f(·) 代表位置定位算法，( xi，yi ) 是锚节点 i 的 坐标，^ dij是节点 i 与节点 j 之间的测距结果，通过估 计测距信号的 TOA 获得，即: ^ dij = c^ τij ( 3) 式中，^ τij为节点 i，j 之间的到达时间的估计结果，c 为 UWB 信号在空气中的传播速度． 则未知节点 j 的坐标求解为: ( xj － xi ) 2 + ( yj － yi ) 2 = ^ d2 ij ( 4) 图 1 TOA 原理 Fig． 1 Principle of TOA 1. 1. 2 质心算法 质心算法是基于几何关系的定位算法，应用在 三边定位中，利用 3 个圆相交的交点形成的三角形 的几何质心来估计目标位置，如图 2 所示． 图 2 质心算法原理 Fig． 2 Principle of the centroiding algorithm 假设这 3 个交点的坐标分别为 Q1 ( x1，y1 ) ，Q2 ( x2，y2 ) ，Q3 ( x3，y3 ) ，则动点的坐标( x，y) 计算式为: · 547 ·

·746· 工程科学学报，第40卷，第6期 (x,y= (5) Q 1.2改进的三边算法 Q2 在距离测量中，由于锚节点测量本身的误差以 图4改进算法示意 及环境的干扰，三个圆在P附近的相交的情况如图 Fig.4 Illustration of the proved algorithm 3所示.而像(d)中有未相交的情况时，使用质心算 法则无法求解 Step 1.将A,B,C,D1,D2,D3代入式(4)，计算 若相交存在唯一交点，则通过式(4)，即可求解 出3个交点Q,Q2,Q3 出P的坐标；若交点如图3(a)、(b)和(c)所示，通 Step2.计算Q1,Q2,Q3分别与A,B,C的距离 过式(5)即可求解P的坐标：若交点如(d)所示，则 之和，S=lAQ:1+1BQ1+1CQ:1,i=1,2,3. 需要改进算法以求解。 Step3.计算测量的距离之和，D=sum(D:) Step4.计算IS:-Dl,并求出最小值，其对应的 a Q:即为P的坐标，即P=Q,仁min{IS:-Dl}. 2拓扑结构优化 在实际的定位中，由于定位环境本身复杂多样， 并富于变化，出于成本考虑，使用者对锚节点的布置 往往比较随意，大多情况只考虑如何使用有限的锚 节点将整个定位区域覆盖，而忽略了锚节点的拓扑 结构对定位结果的影响.Han等的通过几何关系 证明了在正三角形的拓扑结构下具有最高的定位精 度.但此发现并不适合在实际中应用，否则成本将 图3实际测量相交情况.(a),(b)有3个交点：(c)有2个交 成倍增加.因此在保障精度的要求下，如何使成本 点和1个切点：(d)有2个交点 最低化是目前研究超宽带无线定位的重要问题.定 Fig.3 Cases of intersections in reality:(a),(b)three intersec- 位精度受算法和锚节点拓扑结构的直接影响，因此 tions:(c)two intersections and one point of tangeney:(d)two inter- 除了提高算法精度，研究拓扑结构对定位结果精度 sections 的影响也具有同等的重要性 普通的质心算法是将求得的3个点的坐标取均 2.1拓扑结构评估 值作为结果.而在多次定位分析中，结果有如下规 为了避免其他因素对评估效果的影响，本文将 律：每次定位计算得到的更靠近真值点的3个交点 提出一种评估方法来对拓扑结构进行评估. 并不是较均匀地分布在真值点周围，即每个点与真 2.1.1误差带 值点的误差不一，其中误差最小的点大多数情况下 在使用UWB定位时，虽然其精度较其他方法 甚至比平均之后的误差更小.基于此发现，本文将 高，但UWB模块测量的锚节点与动点之间的距离 该误差最小点作为定位结果对普通三边定位算法做 仍然存在一定误差，这个误差多以真值为中心上下 出改进，改进的算法便是选择出这个误差最小的点， 浮动，如图5所示.图中红色的圆圈表示测量的值， 并将其作为定位结果.如图4，A、B和C为3个锚节 d为真实距离数值，±e为误差范围，d。±e为有误 点，Q、Q2和Q3为一次定位中得出的3个交点，算 0.30 dote 法描述如算法1所示. 0.25 0 0 算法1：改进的三边定位算法. 整0.20 、 0 000 0 00 输入： 0.15 d。-e (a)3个锚节点坐标A(xA,ya),B(xB'yg),C 0.10 10 20 (xcyc）; 测量数 (b)传感器测量的3个距离D,D2,D3· 图5误差带 输出：动点坐标P(x,y). Fig.5 Error band

工程科学学报，第 40 卷，第 6 期 ( x，y) ( = ∑ n i = 1 xi n ， ∑ n i = 1 yi n ) ( 5) 1. 2 改进的三边算法 在距离测量中，由于锚节点测量本身的误差以 及环境的干扰，三个圆在 P 附近的相交的情况如图 3 所示． 而像( d) 中有未相交的情况时，使用质心算 法则无法求解． 若相交存在唯一交点，则通过式( 4) ，即可求解 出 P 的坐标; 若交点如图 3( a) 、( b) 和( c) 所示，通 过式( 5) 即可求解 P 的坐标; 若交点如( d) 所示，则 需要改进算法以求解． 图 3 实际测量相交情况 . ( a) ，( b) 有 3 个交点; ( c) 有 2 个交 点和 1 个切点; ( d) 有 2 个交点 Fig． 3 Cases of intersections in reality: ( a) ，( b) three intersec￾tions; ( c) two intersections and one point of tangency; ( d) two inter￾sections 普通的质心算法是将求得的 3 个点的坐标取均 值作为结果． 而在多次定位分析中，结果有如下规 律: 每次定位计算得到的更靠近真值点的 3 个交点 并不是较均匀地分布在真值点周围，即每个点与真 值点的误差不一，其中误差最小的点大多数情况下 甚至比平均之后的误差更小． 基于此发现，本文将 该误差最小点作为定位结果对普通三边定位算法做 出改进，改进的算法便是选择出这个误差最小的点， 并将其作为定位结果． 如图 4，A、B 和 C 为 3 个锚节 点，Q1、Q2 和 Q3 为一次定位中得出的 3 个交点，算 法描述如算法 1 所示． 算法 1: 改进的三边定位算法 . 输入: ( a) 3 个锚节点坐标 A( xA，yA ) ，B( xB，yB ) ，C ( xC，yC ) ; ( b) 传感器测量的 3 个距离 D1，D2，D3 ． 输出: 动点坐标 P( x，y) ． 图 4 改进算法示意 Fig． 4 Illustration of the proved algorithm Step 1. 将 A，B，C，D1，D2，D3 代入式( 4) ，计算 出 3 个交点 Q1，Q2，Q3. Step 2. 计算 Q1，Q2，Q3 分别与 A，B，C 的距离 之和，Si = | AQ→ i | + | BQ→ i | + | CQ→ i |，i = 1，2，3． Step 3. 计算测量的距离之和，D = sum( Di ) ． Step 4. 计算| Si － D|，并求出最小值，其对应的 Qi 即为 P 的坐标，即 P = Qimin { | Si － D| } ． 2 拓扑结构优化 在实际的定位中，由于定位环境本身复杂多样， 并富于变化，出于成本考虑，使用者对锚节点的布置 往往比较随意，大多情况只考虑如何使用有限的锚 节点将整个定位区域覆盖，而忽略了锚节点的拓扑 结构对定位结果的影响． Han 等［15］通过几何关系 证明了在正三角形的拓扑结构下具有最高的定位精 度． 但此发现并不适合在实际中应用，否则成本将 成倍增加． 因此在保障精度的要求下，如何使成本 最低化是目前研究超宽带无线定位的重要问题． 定 位精度受算法和锚节点拓扑结构的直接影响，因此 除了提高算法精度，研究拓扑结构对定位结果精度 的影响也具有同等的重要性． 2. 1 拓扑结构评估 为了避免其他因素对评估效果的影响，本文将 提出一种评估方法来对拓扑结构进行评估． 2. 1. 1 误差带 图 5 误差带 Fig． 5 Error band 在使用 UWB 定位时，虽然其精度较其他方法 高，但 UWB 模块测量的锚节点与动点之间的距离 仍然存在一定误差，这个误差多以真值为中心上下 浮动，如图 5 所示． 图中红色的圆圈表示测量的值， d0 为真实距离数值，± e 为误差范围，d0 ± e 为有误 · 647 ·

孟字等：基于UWB的地下定位算法和拓扑优化 ·747· 差存在的情况下实际测量距离数值的范围，实际测 积越大，能够得到小误差定位结果的概率越小.这 量数值的区域为误差带. 也是测距精度越高，得到的定位结果精度越高的原 在正常情况下，测量值的误差始终在这个范围 因.但是提高测距精度并不是提高定位结果精度的 之内，并且随机分布，而误差带的宽度往往直接决定 唯一方法，因为即便是相同的误差带，相交的位置不 了定位结果的精度.即定位时的3个圆相交时是3同，重叠面积的大小也不一.因此即使误差带很窄， 个圆环相交，会有一个重叠的区域，如图6所示.由 也会有较大误差的结果，图6中(a)与(b)的重叠面 于误差在误差带内随机分布，因此若重叠区域的面 积不相同. 2.10m (al 2.10 2.05 2.05 2.00 2.00 1.95 1.95 L.90 100L 0.10-0.05 0 0.05 0.10 0.90 0.951.00 1.05 1.10 x/m x/1 图6重叠面积示意.(a)动点坐标P(0,2):(b)动点坐标P(1,2) Fig.6 Overlap area:(a)moving point P(0,2):(b)moving point P(1,2) 2.1.2评估指标 部分形成一个近六边形的区域，该区域是定位结果 为了评价不同拓扑结构对定位结果的影响，本 可能出现的区域在这个区域内，与真实P点相距 文提出使用最大绝对定位误差作为指标来对比分 最远的点为最大误差点，这个距离称为最大绝对定 析.如图7，在一次定位中，三个误差带相交的重叠 位误差E,如图7所示. 2.10 (a) 2.10 2.05 2.05 52.00 且2.00 1.95 195 1910005 1.9 0 0.05 .1 0.900951.00 1.05 1.10 w/m x/m 图7Em示意.(a)动点坐标P(O,2):(b)动点坐标P(1,2) Fig.7 E diagrammatic:(a)moving point P(0,2):(b)moving point P(1,2) 假设在两次定位中，相交所得的六边形如图8 (a) b (a)和(b)所示，六边形可拆分成6个三角形.三角 形的顶点中有一个为六边形的中心O,以该点为圆 心，以另两条边为半径画圆，容易得出面积最大的圆 为最长的边所画，如图8(b)中OW2所示，即Ex= 1OW1:图8(a)为正六边形，每条边均相等，则 Ex=IOW1,W表示任意一个顶点.Em的计算方 法为下式，W,表示六边形的6个顶点： 图8E。.计算示意图 Enmx=max{10W1},i=1,2,…,6 Fig.8 Calculation of E (6) 取一个长16m,宽8m的矩形区域，将锚节点的 坐标定为(0,8)，（-4,0)，（4,0)，对区域内各点分

孟 宇等: 基于 UWB 的地下定位算法和拓扑优化 差存在的情况下实际测量距离数值的范围，实际测 量数值的区域为误差带． 在正常情况下，测量值的误差始终在这个范围 之内，并且随机分布，而误差带的宽度往往直接决定 了定位结果的精度． 即定位时的 3 个圆相交时是 3 个圆环相交，会有一个重叠的区域，如图 6 所示． 由 于误差在误差带内随机分布，因此若重叠区域的面 积越大，能够得到小误差定位结果的概率越小． 这 也是测距精度越高，得到的定位结果精度越高的原 因． 但是提高测距精度并不是提高定位结果精度的 唯一方法，因为即便是相同的误差带，相交的位置不 同，重叠面积的大小也不一． 因此即使误差带很窄， 也会有较大误差的结果，图 6 中( a) 与( b) 的重叠面 积不相同． 图 6 重叠面积示意 . ( a) 动点坐标 P ( 0，2) ; ( b) 动点坐标 P ( 1，2) Fig． 6 Overlap area: ( a) moving point P( 0，2) ; ( b) moving point P( 1，2) 2. 1. 2 评估指标 为了评价不同拓扑结构对定位结果的影响，本 文提出使用最大绝对定位误差作为指标来对比分 析． 如图 7，在一次定位中，三个误差带相交的重叠 部分形成一个近六边形的区域，该区域是定位结果 可能出现的区域． 在这个区域内，与真实 P 点相距 最远的点为最大误差点，这个距离称为最大绝对定 位误差 Emax，如图 7 所示． 图 7 Emax示意． ( a) 动点坐标 P( 0，2) ; ( b) 动点坐标 P( 1，2) Fig． 7 Emax diagrammatic: ( a) moving point P( 0，2) ; ( b) moving point P( 1，2) 假设在两次定位中，相交所得的六边形如图 8 ( a) 和( b) 所示，六边形可拆分成 6 个三角形． 三角 形的顶点中有一个为六边形的中心 O，以该点为圆 心，以另两条边为半径画圆，容易得出面积最大的圆 为最长的边所画，如图 8( b) 中OW→ 2 所示，即 Emax = |OW→ 2 | ; 图 8 ( a ) 为正 六 边 形，每 条 边 均 相 等，则 Emax = | →OW |，W 表示任意一个顶点． Emax 的计算方 法为下式，Wi 表示六边形的 6 个顶点: Emax = max { |OW→ i |} ，i = 1，2，…，6 ( 6) 取一个长 16 m，宽 8 m 的矩形区域，将锚节点的 图 8 Emax计算示意图 Fig． 8 Calculation of Emax 坐标定为( 0，8) ，( － 4，0) ，( 4，0) ，对区域内各点分 · 747 ·