基于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 ·

·748 工程科学学报，第40卷，第6期 别计算E值并作出图像，如图9.从图像中可以看 E /m 出各个位置的Em值并不相同，即锚节点的拓扑结 012 0.13 构对区域内各个位置的定位精度影响程度不同. 0.10 0.12 为了对比不同拓扑结构对定位结果精度的影 E0.08 0.11 响，同时考虑到地下巷道大多为狭长地带，本文设计 0.06 0.10 0.04 了一个长20m宽4m的区域，模拟巷道环境，并对 0.09 0.02 锚节点采用了5种拓扑结构，如图10所示，做出各 0.08 自的最大绝对定位误差分布图. 0.07 0.06 可以看出，不同拓扑结构对整个区域内的定位 xim 结果精度影响程度不同，所以寻找出一个最适合定 图9E分布图 位环境的拓扑结构可以在有限的条件下提高定位结 Fig.9 Distribution of E 果的精度.此外，由于矿车在地下巷道内多数情况 是沿着道路中心运行，故只要在中心地带的误差更 域，对其做出最大绝对定位误差分布图，如图11. 小则更有意义.因此下面只取了道路中心2m的区 计算行驶区域内各点的E值在评估应用在地 E /m E /m 0.25a) 0.25 0.25 0.25 0.20 0.20 0.15 0.20 0.15 0.20 0.10 0.15 0.10 0.15 0.05 0.05 0.10 0.10 9 10 2 10 E /m E m 0.25 0.40(d 0.25 0.40 0.20 0.30 0.20 020 0.15 0.10 0.10 0.10 10 0 10 -10 E /m (e) 0.24 0.20 0.22 0.20 0.15 0.18 0.10 0.16 0.14 D.5 0.12 0.10 0.08 10 -10 图10不同拓扑结构下（锚节点坐标）Em分布.(a)(-2,0),(2,0),(0,4):(b)(-4,0),(4,0),(0,4):(c)(-6,0),(6,0),(0, 4):(d)(-8,0),(8,0),(0,4):(e)(-10,0),(10,0),(0,4) Fig.10 Distribution of Eunder different topologies (anchor node coordinates):(a)(2,0),(2,0),(0,4)(b)(4,0),(4,0),(0,4) (c)(-6,0),(6,0),(0,4):(d)(-8,0),(8,0),(0,4):(e)(-10,0),(10,0),(0,4)

工程科学学报，第 40 卷，第 6 期 别计算 Emax值并作出图像，如图 9． 从图像中可以看 出各个位置的 Emax值并不相同，即锚节点的拓扑结 构对区域内各个位置的定位精度影响程度不同． 图 10 不同拓扑结构下( 锚节点坐标) Emax分布. ( a) ( － 2，0) ，( 2，0) ，( 0，4) ; ( b) ( － 4，0) ，( 4，0) ，( 0，4) ; ( c) ( － 6，0) ，( 6，0) ，( 0， 4) ; ( d) ( － 8，0) ，( 8，0) ，( 0，4) ; ( e) ( － 10，0) ，( 10，0) ，( 0，4) Fig． 10 Distribution of Emaxunder different topologies ( anchor node coordinates) : ( a) ( － 2，0) ，( 2，0) ，( 0，4) ; ( b) ( － 4，0) ，( 4，0) ，( 0，4) ; ( c) ( － 6，0) ，( 6，0) ，( 0，4) ; ( d) ( － 8，0) ，( 8，0) ，( 0，4) ; ( e) ( － 10，0) ，( 10，0) ，( 0，4) 为了对比不同拓扑结构对定位结果精度的影 响，同时考虑到地下巷道大多为狭长地带，本文设计 了一个长 20 m 宽 4 m 的区域，模拟巷道环境，并对 锚节点采用了 5 种拓扑结构，如图 10 所示，做出各 自的最大绝对定位误差分布图． 可以看出，不同拓扑结构对整个区域内的定位 结果精度影响程度不同，所以寻找出一个最适合定 位环境的拓扑结构可以在有限的条件下提高定位结 果的精度． 此外，由于矿车在地下巷道内多数情况 是沿着道路中心运行，故只要在中心地带的误差更 小则更有意义． 因此下面只取了道路中心 2 m 的区 图 9 Emax分布图 Fig． 9 Distribution of Emax 域，对其做出最大绝对定位误差分布图，如图 11． 计算行驶区域内各点的 Emax值在评估应用在地 · 847 ·

孟字等：基于UWB的地下定位算法和拓扑优化 ·749· E/m E /m 0.24 0.20 0.22 0.20 0.22 0.20 0.20 0.15 0.15 0.18 0.18 0.16 0.16 0.10 0.10 0.14 0.14 0.05 0.12 0.05 0.12 0.10 0.10 0.08 0.08 0.06 0.06 10 10 E./m E im 0.20外 0.20 0.18 0.16 0.14 012 0.14 0.12 0.10 0.10 0.08 0.08 0.06 10 x/m E/m 0.20(e ☐0.22 0.20 0.18 0.16 0.14 0.12 0.10 0.08 -10 图11不同拓扑结构下（错节点坐标）通行区域E分布.(a)(-2,0),(2,0),(0,4):(b)(-4,0),(4,0),(0,4):(c)(-6,0), (6,0),(0,4):(d)(-8,0),(8,0),(0,4):(©)(-10,0)，(10,0)，(0,4) Fig.11 Distribution of E in the driving zone under different topologies (anchor node coordinates):(a)(-2,0),(2,0),(0,4):(b)(-4, 0),(4,0),(0,4):(c)(-6,0),(6,0),(0,4):(d)(-8,0),(8,0),(0,4):(e)(-10.0),(10,0),(0,4) 下巷道定位的拓扑结构时更有针对性 4/ 2.2拓扑结构优化方法 2 本文采用遍历寻优的方法，在一定范围内搜索 出每个点的平均最大绝对定位误差最小的拓扑结 构，如图12所示. 0 5 10 x/ 算法2：拓扑结构优化算法 图12拓扑结构优化示意 输入：区域的长度a和宽度b,通行区域宽度c, Fig.12 Topology optimization method 搜索起点拓扑结构A,(x1yA),B,(xmy),C(xc, y)(由于拓扑结构是等腰三角形，故每次顶角坐标 )(受)(-受生)（受生）将 不变)，网格数n×m,搜索步长s. 通行区域划分为n×m个网格，取各网格交点坐标. 输出：最优拓扑结构锚节点坐标 Step2.以A1(x1-s·(i-1),0),B,(xm+s· Stp1.设测量区域的4个顶点坐标为(-2 (i-1),0),C(0,b)为锚节点

孟 宇等: 基于 UWB 的地下定位算法和拓扑优化 图 11 不同拓扑结构下( 锚节点坐标) 通行区域 Emax分布 . ( a) ( － 2，0) ，( 2，0) ，( 0，4) ; ( b) ( － 4，0) ，( 4，0) ，( 0，4) ; ( c) ( － 6，0) ， ( 6，0) ，( 0，4) ; ( d) ( － 8，0) ，( 8，0) ，( 0，4) ; ( e) ( － 10，0) ，( 10，0) ，( 0，4) Fig． 11 Distribution of Emax in the driving zone under different topologies ( anchor node coordinates) : ( a) ( － 2，0) ，( 2，0) ，( 0，4) ; ( b) ( － 4， 0) ，( 4，0) ，( 0，4) ; ( c) ( － 6，0) ，( 6，0) ，( 0，4) ; ( d) ( － 8，0) ，( 8，0) ，( 0，4) ; ( e) ( － 10，0) ，( 10，0) ，( 0，4) 下巷道定位的拓扑结构时更有针对性． 2. 2 拓扑结构优化方法 本文采用遍历寻优的方法，在一定范围内搜索 出每个点的平均最大绝对定位误差最小的拓扑结 构，如图 12 所示． 算法 2: 拓扑结构优化算法． 输入: 区域的长度 a 和宽度 b，通行区域宽度 c， 搜索起点拓扑结构 A1 ( xA1，yA1 ) ，B1 ( xB1，yB1 ) ，C( xC， yC ) ( 由于拓扑结构是等腰三角形，故每次顶角坐标 不变) ，网格数 n × m，搜索步长 s． 输出: 最优拓扑结构锚节点坐标． Step 1. 设测量区域的 4 个顶点坐标为 ( － a 2 ， 图 12 拓扑结构优化示意 Fig． 12 Topology optimization method b － c ) 2 ，( a 2 ， b － c ) 2 ，( － a 2 ， b + c ) 2 ，( a 2 ，b + c ) 2 ，将 通行区域划分为 n × m 个网格，取各网格交点坐标． Step 2. 以 A1 ( xA1 － s·( i － 1) ，0) ，B1 ( xB1 + s· ( i － 1) ，0) ，C( 0，b) 为锚节点． · 947 ·

·750· 工程科学学报，第40卷，第6期 Step3.计算各网格交点的Ex,并求平均值 组对比实验，每组在通行区域内随机取50个点作为 E 待定位点，同时使用改进前后的算法进行定位.在 Step4.重复Step2和Step3直到终点An（-a/ 这个区域内使用上文中的优化方法，在此区域内的最 2,0),Bn(a/2,0). 优拓扑结构为A(-6.25,0),B(6.25,0),C(0,4) Step5.求min{E;},其下标对应的A:B:C即寻 算法误差统计数据如图14(b)和(c)所示，其 优的结果 中图14(b)为其中一次实验中2种算法对50个点 E平均值的变化如图13所示，沿着搜索方 定位结果的误差曲线，比较能代表这两种算法在定 向，平均E变化曲线呈现开口向上的抛物线状，其 位中的平均表现；在每次实验中，对50个点的定位 最低点对应的拓扑结构便是所寻求的最佳拓扑 结果统计误差的最大最小和平均值，10次实验的统 结构 计数据在图（©）所示“平均数据”一栏表示的是总 共500个点的两种定位误差均值（其中每种颜色的 最高点对应的数值为该项的值).以图14(b)为代 表分析可以看到，改进后的算法定位误差有较大改 善，改进前后的平均误差分别是0.056m和0.044 m,误差的标准差则分别是0.031m和0.019m.与 改进前的算法相比，改进后的算法平均误差减小了 21.4%,误差的标准差减小了38.7%.由此可以认 ABC ABC A BC 为，改进的算法能够减小定位的误差，并能使误差的 波动更小，定位结果更稳定 图13Em平均值变化曲线 Fig.13 Change curve of average value of E 3.2实地实验 实地实验的设置选择了类似采场环境的区域， 3 仿真与实验 宽度大约为巷道宽度的两倍，因此实验区域的长和 宽分别是40m和8m.在相对道路中央的6m宽的 3.1算法检验仿真实验 范围内随机取50个点，仿照文中对拓扑结构优化的 为了检验算法的性能，本文采用MATLAB软件 方法，取了10种拓扑结构，在每种拓扑结构下分别 建立了一个类似于地下巷道的狭长环境，如图14 使用改进后的定位算法和普通的定位算法进行定 (a),是一个长20m、宽4m的狭长通道，共设置10 位，对比定位结果的误差 A新回 类C 0.2r 改进前 0 改进后 2中 5--900 600000 010-8 A 6 4-20 2 10 1015202530354045 50 x/m 测试数 (c) 改进前算法 改进后算法 平均数据 0.20 0.20 0.20 最大误差 平均误差 最小误差 0.15 0.15 0.15 0.10 0.10 0.05 0.05 0.05 12345678910 12345678910 改进前改进后 测试组数 测试组数 图14仿真实验结果.(a)锚节点与动点分布示意图：(b)误差曲线：(c)误差统计 Fig.14 Simulation results:(a)figure of anchor nodes and moving points;(b)error curves;(c)statistical erro

工程科学学报，第 40 卷，第 6 期 Step 3. 计算各网格交点的 Emax，并求平均值 Ei ． Step 4. 重复 Step 2 和 Step 3 直到终点 An ( － a / 2，0) ，Bn ( a /2，0) ． Step 5. 求 min { Ei} ，其下标对应的 AiBiC 即寻 优的结果． Emax平均值的变化如图 13 所示，沿着搜索方 向，平均 Emax变化曲线呈现开口向上的抛物线状，其 最低点对应的拓扑结构便是所寻求的最佳拓扑 结构． 图 13 Emax平均值变化曲线 Fig． 13 Change curve of average value of Emax 图 14 仿真实验结果 . ( a) 锚节点与动点分布示意图; ( b) 误差曲线; ( c) 误差统计 Fig． 14 Simulation results: ( a) figure of anchor nodes and moving points; ( b) error curves; ( c) statistical error 3 仿真与实验 3. 1 算法检验仿真实验 为了检验算法的性能，本文采用 MATLAB 软件 建立了一个类似于地下巷道的狭长环境，如图 14 ( a) ，是一个长 20 m、宽 4 m 的狭长通道，共设置 10 组对比实验，每组在通行区域内随机取 50 个点作为 待定位点，同时使用改进前后的算法进行定位． 在 这个区域内使用上文中的优化方法，在此区域内的最 优拓扑结构为 A( － 6. 25，0) ，B( 6. 25，0) ，C( 0，4) ． 算法误差统计数据如图 14 ( b) 和( c) 所示，其 中图 14( b) 为其中一次实验中 2 种算法对 50 个点 定位结果的误差曲线，比较能代表这两种算法在定 位中的平均表现; 在每次实验中，对 50 个点的定位 结果统计误差的最大最小和平均值，10 次实验的统 计数据在图( c) 所示，“平均数据”一栏表示的是总 共 500 个点的两种定位误差均值( 其中每种颜色的 最高点对应的数值为该项的值) ． 以图 14( b) 为代 表分析可以看到，改进后的算法定位误差有较大改 善，改进前后的平均误差分别是 0. 056 m 和 0. 044 m，误差的标准差则分别是 0. 031 m 和 0. 019 m． 与 改进前的算法相比，改进后的算法平均误差减小了 21. 4% ，误差的标准差减小了 38. 7% ． 由此可以认 为，改进的算法能够减小定位的误差，并能使误差的 波动更小，定位结果更稳定． 3. 2 实地实验 实地实验的设置选择了类似采场环境的区域， 宽度大约为巷道宽度的两倍，因此实验区域的长和 宽分别是 40 m 和 8 m． 在相对道路中央的 6 m 宽的 范围内随机取 50 个点，仿照文中对拓扑结构优化的 方法，取了 10 种拓扑结构，在每种拓扑结构下分别 使用改进后的定位算法和普通的定位算法进行定 位，对比定位结果的误差． · 057 ·

孟字等：基于UWB的地下定位算法和拓扑优化 751· 本文取其中比较具有代表性的5种拓扑结构作 过全站仪测量，使用的全站仪为“拓普康OS- 分析.拓扑结构坐标如表1所示，其中实际坐标通 600G” 表1拓扑结构的坐标 Table 1 Coordinates of different topologies 拓扑结构编码 设计坐标/m 实际坐标/m 1 A(-6.25,0),B(6.25,0),C(0,8) A(-6.266,0.002),B(6.234,0.003),C(0.005,8.008) 3 A(-8,0),B(8,0),C(0,8) A(-8.045,0.003),B(8.029,0.005),C(0.004,8.012) 3# A(-11.25,0),B(11.25,0),C(0,8) A(-11.252,0.006),B(11.261,0.004),C(-0.008,8.015) 4* A(-15,0),B(15,0),C(0,8) A(-14.986,0.005),B(15.029,0.002),C(-0.002,7.969) 5# A(-20,0),B(20,0),C(0,8) A(-20.058,-0.004),B(-19.9840,0.003),C(-0.008,7.979) 各拓扑结构与点如图15所示，其中各个拓扑结 构下点的选取均相同 0% 8 0 0 o00 6 0 08 000 21 081 0C二二二二二A之 -20 -15 -10 5 0 10 1520 -20 -15 -10 -5 0 5 10 1520 x/m x/m 00 08a 21 c0 21 ∠08-----0 D 0二12 B二] -20 -15 -10 0 10 15 20 20 -15-10 10 15 20 x/m x/m 8L(e) 4 二二6--60 0 0工 -20 -15-10-50 5101520 x/m 图15拓扑结构与点示意图.(a)1拓扑结构：(b)2*拓扑结构：(c)3*拓扑结构：(d)4拓扑结构：()5*拓扑结构 Fig.15 Topologies and points:(a)topology 1:(b)topology 2:(c)topology3:(d)topology 4:(e)topology 5 定位结果的误差如图16所示，图中曲线“改进多能够减小超过60%，误差的标准差同样也更小， 前”表示普通定位算法“改进后”表示本文提出的 最多能够减小达70%以上：说明该拓扑结构在减小 改进算法.从图中可以明显地看出3拓扑结构相比 定位误差同时也使得定位结果波动更小结果更稳 另外4种拓扑结构的定位误差更小，而在选取的拓 定.从表4对比2种定位算法，可以看到改进后的 扑结构中，3拓扑结构与通过优化方法在这个区域 算法能将误差减小15%以上，最多能达到43.2%， 中得到的最优拓扑结构一致，这说明拓扑结构优化 其中在拓扑结构3下误差的减幅最大；误差的标准 对定位结果精度有影响，且根据环境选择最优的拓 差同样得以减小，最高能达到54.4%，说明改进的 扑结构能够在其他条件不变的情况下大大减小定位 算法同样能够使误差变化幅度减小，结果更稳定 结果的误差 在本实验中，使用优化后的拓扑结构与改进的 表2统计了使用不同拓扑结构和算法的定位误 算法组合相比未优化的拓扑结构和普通算法，即拓 差：表3将1、2”、4、5拓扑结构分别与3拓扑结构 扑结构3和改进后的算法组合（误差为0.025m)与 进行对比，比较了相同算法下平均误差和误差的标 拓扑结构1和普通算法的组合（误差为0.096m)相 准差的减少量：表4将2种算法在不同拓扑结构下 比，误差能够减小74.0%之多，这表明当结合使用 的平均误差和误差的标准差的比较进行了统计.可 改进的定位算法和优化的拓扑结构，能够将定位精 以看到在相同的算法下，使用拓扑结构3的定位结 度进一步提高.且从表4中可以看到，3"拓扑结构 果误差均比其余拓扑结构能够减小16.7%以上，最 相比其余拓扑结构，因算法的改进而减小的误差比

孟 宇等: 基于 UWB 的地下定位算法和拓扑优化 本文取其中比较具有代表性的 5 种拓扑结构作 分析． 拓扑结构坐标如表 1 所示，其中实际坐标通 过全 站 仪 测 量，使用的全站仪为“拓 普 康 OS-- 600G”． 表 1 拓扑结构的坐标 Table 1 Coordinates of different topologies 拓扑结构编码 设计坐标/m 实际坐标/m 1# A( － 6. 25，0) ，B( 6. 25，0) ，C( 0，8) A( － 6. 266，0. 002) ，B( 6. 234，0. 003) ，C( 0. 005，8. 008) 2# A( － 8，0) ，B( 8，0) ，C( 0，8) A( － 8. 045，0. 003) ，B( 8. 029，0. 005) ，C( 0. 004，8. 012) 3# A( － 11. 25，0) ，B( 11. 25，0) ，C( 0，8) A( － 11. 252，0. 006) ，B( 11. 261，0. 004) ，C( － 0. 008，8. 015) 4# A( － 15，0) ，B( 15，0) ，C( 0，8) A( － 14. 986，0. 005) ，B( 15. 029，0. 002) ，C( － 0. 002，7. 969) 5# A( － 20，0) ，B( 20，0) ，C( 0，8) A( － 20. 058，－ 0. 004) ，B( － 19. 9840，0. 003) ，C( － 0. 008，7. 979) 各拓扑结构与点如图 15 所示，其中各个拓扑结 构下点的选取均相同． 图 15 拓扑结构与点示意图 . ( a) 1# 拓扑结构; ( b) 2# 拓扑结构; ( c) 3# 拓扑结构; ( d) 4# 拓扑结构; ( e) 5# 拓扑结构 Fig． 15 Topologies and points: ( a) topology 1# ; ( b) topology 2# ; ( c) topology 3# ; ( d) topology 4# ; ( e) topology 5# 定位结果的误差如图 16 所示，图中曲线“改进 前”表示普通定位算法，“改进后”表示本文提出的 改进算法． 从图中可以明显地看出 3# 拓扑结构相比 另外 4 种拓扑结构的定位误差更小，而在选取的拓 扑结构中，3# 拓扑结构与通过优化方法在这个区域 中得到的最优拓扑结构一致，这说明拓扑结构优化 对定位结果精度有影响，且根据环境选择最优的拓 扑结构能够在其他条件不变的情况下大大减小定位 结果的误差． 表 2 统计了使用不同拓扑结构和算法的定位误 差; 表 3 将 1# 、2# 、4# 、5# 拓扑结构分别与 3# 拓扑结构 进行对比，比较了相同算法下平均误差和误差的标 准差的减少量; 表 4 将 2 种算法在不同拓扑结构下 的平均误差和误差的标准差的比较进行了统计． 可 以看到在相同的算法下，使用拓扑结构 3 的定位结 果误差均比其余拓扑结构能够减小 16. 7% 以上，最 多能够减小超过 60% ，误差的标准差同样也更小， 最多能够减小达 70% 以上; 说明该拓扑结构在减小 定位误差同时也使得定位结果波动更小结果更稳 定． 从表 4 对比 2 种定位算法，可以看到改进后的 算法能将误差减小 15% 以上，最多能达到 43. 2% ， 其中在拓扑结构 3 下误差的减幅最大; 误差的标准 差同样得以减小，最高能达到 54. 4% ，说明改进的 算法同样能够使误差变化幅度减小，结果更稳定． 在本实验中，使用优化后的拓扑结构与改进的 算法组合相比未优化的拓扑结构和普通算法，即拓 扑结构 3 和改进后的算法组合( 误差为 0. 025 m) 与 拓扑结构 1 和普通算法的组合( 误差为 0. 096 m) 相 比，误差能够减小 74. 0% 之多，这表明当结合使用 改进的定位算法和优化的拓扑结构，能够将定位精 度进一步提高． 且从表 4 中可以看到，3# 拓扑结构 相比其余拓扑结构，因算法的改进而减小的误差比 · 157 ·

·752 工程科学学报，第40卷，第6期 0.25 025(间 一改进前 一改进前 0.20 一改进后 0.20 一改进后 0.10 AA 20 30 30 测试数 测试数 0.25fe 025d 一改进前 一改进前 0.20 改进后 0.20 改进后 0.15 015 0.10 0.10 30 测试数 测试数 0.25r e 改进前 0.20 二改进后 015 .05 20 30 40 50 测试数 图165种拓扑结构下定位结果的误差曲线.(a)1“拓扑结构：(b)2拓扑结构：(c)3拓扑结构：(d)4拓扑结构：（©）5*拓扑结构 Fig.16 Error curves of the 5 topologies:(a)topology 1:(b)topology 2 (c)topology 3 (d)topology 4:(e)topology 5 表2实地实验误差统计 表4改进后的算法相比普通算法的结果提升 Table 2 Error of field tests Table 4 Improvement in results by the improved algorithm compared 拓扑结构 普通算法 改进后算法 with the normal algorithm % 编码 平均误差误差的标准差平均误差误差的标准差 拓扑结构编码 平均误差 误差的标准差 19 0.096 0.059 0.072 0.041 1# 25.0 30.5 2* 0.073 0.055 0.062 0.041 2* 15.1 25.5 3# 0.037 0.021 0.025 0.012 4 0.048 0.033 0.030 0.015 3* 43.2 42.9 0.076 0.046 0.053 0.028 4* 31.3 54.5 39.5 47.2 表33拓扑结构相比其他拓扑结构减小的误差和误差的标准差 Table 3 Decrease in mean error and standard deviation of Topology3 例最高，达43.2%，说明这两种方法结合时能够最 compared with the other topologies 大程度提高精度.因此本文建议在实际使用中，根 拓扑结构 普通算法 改进后算法 据实际情况结合使用这两种方法. 编码 平均误差误差的标准差平均误差误差的标准差 1+ 61.5 64.4 65.3 70.7 4结论 2# 49.3 61.8 59.7 70.7 4 22.9 36.4 16.7 20.0 (1)对普通的三边定位提出了改进，在相同的 5* 51.3 60.4 45.7 57.1 测距环节下，通过改变从距离求解坐标的方法，使结

工程科学学报，第 40 卷，第 6 期 图 16 5 种拓扑结构下定位结果的误差曲线 . ( a) 1# 拓扑结构; ( b) 2# 拓扑结构; ( c) 3# 拓扑结构; ( d) 4# 拓扑结构; ( e) 5# 拓扑结构 Fig． 16 Error curves of the 5 topologies: ( a) topology 1# ; ( b) topology 2# ; ( c) topology 3# ; ( d) topology 4# ; ( e) topology 5# 表 2 实地实验误差统计 Table 2 Error of field tests m 拓扑结构 编码 普通算法 改进后算法 平均误差 误差的标准差 平均误差 误差的标准差 1# 0. 096 0. 059 0. 072 0. 041 2# 0. 073 0. 055 0. 062 0. 041 3# 0. 037 0. 021 0. 025 0. 012 4# 0. 048 0. 033 0. 030 0. 015 5# 0. 076 0. 046 0. 053 0. 028 表 3 3# 拓扑结构相比其他拓扑结构减小的误差和误差的标准差 Table 3 Decrease in mean error and standard deviation of Topology 3# compared with the other topologies % 拓扑结构 编码 普通算法 改进后算法 平均误差 误差的标准差 平均误差 误差的标准差 1# 61. 5 64. 4 65. 3 70. 7 2# 49. 3 61. 8 59. 7 70. 7 4# 22. 9 36. 4 16. 7 20. 0 5# 51. 3 60. 4 45. 7 57. 1 表 4 改进后的算法相比普通算法的结果提升 Table 4 Improvement in results by the improved algorithm compared with the normal algorithm % 拓扑结构编码 平均误差 误差的标准差 1# 25. 0 30. 5 2# 15. 1 25. 5 3# 43. 2 42. 9 4# 31. 3 54. 5 5# 39. 5 47. 2 例最高，达 43. 2% ，说明这两种方法结合时能够最 大程度提高精度． 因此本文建议在实际使用中，根 据实际情况结合使用这两种方法． 4 结论 ( 1) 对普通的三边定位提出了改进，在相同的 测距环节下，通过改变从距离求解坐标的方法，使结 · 257 ·