1、2097-3012(2023)03-0450-07 Journal of Spatio-temporal Information 时空信息学报 收稿日期:2022-08-30；修订日期:2023-06-30 基金项目:浙江省自然资源厅 2021 年度科技项目（2021-55）作者简介:曹昌磊，研究方向为测绘地理信息数据处理。E-mail:cao_ 通信作者:陈志达，研究方向为摄影测量与遥感应用。E-mail: 定位传感器基站部署优化方案研究 曹昌磊1，陈志达1，龚小宇2，洪年祥2 1.绍兴市上虞区自然资源监测中心，绍兴 312300；2.浙江省测绘科学技术研究院，杭州 310012 摘 要：室
2、内定位技术是卫星定位的辅助定位补充手段，能克服卫星信号难以穿越建筑物等缺点，而传感器基站的合理部署是实现高精度室内定位的关键内容。为进一步改善传感器综合定位性能，本文基于改进的遗传算法优化基站部署方案，以精度衰减因子作为评估指标，分析不同基站数量、位置和环境条件等因素对定位综合性能的影响，并以仿真球形体育馆为例，进行了验证。结果表明，采用 4 个流动站和 1 个固定站方案的综合效益最高，能够很好地应用于快速组网场景，具有较好的参考价值。关键词：精度衰减因子；定位传感器；组网优化；室内定位 引用格式：曹昌磊,陈志达,龚小宇,洪年祥.2023.定位传感器基站部署优化方案研究.时空信息学报,30(3
3、):450-456 Cao C L,Chen Z D,Gong X Y,Hong N X.2023.Research on optimization of deployment plans for positioning sensor base stations.Journal of Spatio-temporal Information,30(3):450-456,doi:10.20117/j.jsti.202303018 1 引 言 室内定位是一项对全球导航卫星系统在遮蔽地区的补充导航定位技术，为办公大楼、超市和室内外过渡区域的位置服务提供了极大的便利（薛伟莲等，2020）。室内定位主要采
4、用无线通信、基站定位、惯导测量和影像导航等方式，而基站定位方式具有信号传输距离远、精度高和可行性高等优点，在多种场景中能发挥出独特优势。因此，传感器基站定位方式在城镇火灾、地震和倒塌等多种室内灾害场景下的应急导航问题处理中获得了广泛应用（黄瑞贞，2020；施志荣，2019；孙公德等，2017）。精度衰减因子（dilution of precision，DOP）是评估导航定位精度高低的关键参数，表示测量误差与定位精度的相对几何关系。当 DOP 值较大时，组网强度较低，表示在该区域使用传感器定位技术得到的位置精度较低。由于在利用伪距进行空间定位中，需要三个方向位置信息才能确定点位坐标（不对接收器的
5、钟差进行估计），同时需要多余观测量提高计算成果的精度，因此，通常需要 4 个以上的基站观测数据才能完成空间定位。根据定位区域的环境特征，以及信号的连续、可靠、多重覆盖和探测空间最大化特点，优化传统单因子静态组网，建立兼顾多因子动态组网技术，缩短组网时间并改善综合定位精度。已有研究多集中在物流仓库、地下综采面和办公大楼等不同场景下的基站组网方式，分析在对应区域中的 DOP 分布情况，讨论基站几何布设对定位误差的影响（何琦敏和王坚，2017；王宁等，2020；杨燈等，2020）。但这些布设方案过于理想化，仅考虑单个因素 DOP 的误差影响，忽略信号连续和重叠等多因素作用。其中，这些因素导致基站组网
6、优化本质上是一个组合优化问题。因此，在实际组网过程中，上述方法通常难以满足最优布设基站要求。近些年，有不少研究提出使用遗传算法优化基站组网布设，对传统的布设方案进行优化（何琦敏等，2017；Wang 等，2022；周宇泰等，2022）。遗 曹昌磊 等：定位传感器基站部署优化方案研究 451 传算法是一种全局寻优算法，最早由美国科学家John Holland 在 20 世纪 70 年代提出，由于算法的全局搜索能力和稳健性特点，在解决较为复杂的组合优化问题上能够较快地获得优化结果（刘修宇等，2021；缑慧娟和杨成龙，2020）。然而，这些方法中没有考虑信号的通信距离与覆盖区域的几何关系及相关的应急
7、条件。因此，本文以改进的自适应遗传算法对基站组网进行优化，综合考虑信号的连续、可靠、多重覆盖和探测空间最大化特征，分析优化方案后的组网强度，为应急救援等情况下的定位组网提供参考依据。2 组网部署方法 按照观测模式分类，使用定位传感器观测数据进行导航定位的方式主要有双向测距（two way ranging,TWR）模式、时间到达（time of arrival，TOA）模式和时间到达差（time difference of arrival，TDOA）模式。其中，TOA 算法具有精度较高、定位收敛和基站构建简单优势，因此，常用于基站测距定位的实践应用。2.1 TOA 定位原理简述 TOA 是一种通
8、过测量终端至基站之间的信号传输距离推测终端位置的定位方法，根据基站发送至终端接收电磁波信号的传输时间计算两点之间距离，建立基站与终端距离的观测方程。对于终端的空间位置共三个未知参数，因此接收到至少 3 个基站的信号数据，即可实现空间定位。根据最小二乘准则和间接平差原理可知（刘大杰等，2003）：T1TT11()=()xxxB PBB PfQB Q B (1)式中，P 为观测值权阵，由于观测值均为相对独立，因此，可设为单位阵；x 为待求参数的估计值；B 为 x 的雅可比矩阵；f 为残差项；Qxx为待求参数的协因数阵；Q 为观测值协因数阵，满足P=Q1。由此，可得到 x 的协因数阵 Qxx。假设定
9、位传感器的测距单位中误差为 0，即有 x 的方差阵为 Dxx=0Qxx。2.2 精度衰减因子 用于估计二维平面的精度可用HDOP表示：12220HDOP(1,1)(2,2)xyxxxx2+=+QQ (2)用于估计高程方向的精度可用VDOP表示：2200(3,3)VDOPxxz2=Q (3)用于估计三维空间的精度可用PDOP表示：122220PDOP(1,1)(2,2)(3,3)xyzxxxxxx2+=+QQQ(4)式中，x、y、z为坐标在三个方向上的误差；0为传感器测距中误差。假定信号在传输过程中的定位传感器单位测距误差保持不变，DOP将由基站和终端位置的几何关系确定，是一个无量纲值。式(2)
10、式(4)表明，当待求坐标协因数阵上的对角线元素值较大时，DOP较大，表示点位的定位精度较差。因此，根据HDOP、VDOP和PDOP值所代表的区域二维、高程和三维精度，从而可评估最终组网的稳健性。2.3 基站组网的基本准则 在一个已知的封闭空间中，基站数量和部署形式（矩形、星形和菱形）将直接影响空间定位精度。由于实际室场景中存在较为密集的人流和物体，同时需要考虑封闭空间的几何构造，因此，需要通过分析多种部署方案的实验结果，选择最佳的布设方案以达到相应的定位要求。基站的信号传输距离通常有限，为保证信号持续传输，必须保证信号的连续性。由于采用传感器定位技术进行定位需要同时接收多个基站的信号，因此，基
11、站的布设方式应满足一定的区域重叠。为了进一步扩大研究区域的范围，应使用一定数量的基站以保证定位区域最大化。此外，为了保证连续跟踪的终端目标精度达到相应要求，避免错误定位，要求组网方式具有一定可靠性。综上，基站组网的布设方式需要满足信号连续性、多重信号覆盖、责任区域最大化、可靠性原则（陈秉试，2021）。由于基站的部署受到上述几种因素的影响，因此，基站的部署优化问题是一种组合优化问题。针对每一种组网准则，应满足如下特点。1）信号连续性 假定基站的最大通信距离为d，基站至终端的452 Journal of Spatio-temporal Information 时空信息学报 2023,30(3)距
12、离为l，为了确保基站能够连续接收无线信号完成定位工作，要求ld。2）多重信号覆盖 假定所有的基站数量为k，完成定位工作的最少接收基站数为N0：01ijkdlinN (5)式中，1ijkd lin为终端能够收到有效信号的基站数目；i、j分别为基站号和终端号。3）可靠性 假定任务要求点位的DOP阈值为FDOP，为了保证精度达到要求，即有待定点DOPFDOP)为指定区域i中的盲点数量（即盲点面积），即区域内大于FDOP的点数（DOP值较大时，定位精度低）；wi为对应的num(DOPiFDOP)权重系数。3 基于改进的自适应遗传算法基站部署 通过基站的组网部署原理可知，优化基站网络的性能需要实现目标函
13、数式（6）达到最小完成，本质上是一种组合优化问题（刘永信等，2021）。目前解决组合优化问题的算法主要有多项式时间算法（曲明等，2022）、近似算法（廖玉婕，2022）、启发式搜索算法（梅志虎和唐志波，2023）和遗传算法（杨雄和吴东，2021）等。多项式时间算法、近似算法和启发式算法普遍存在枚举数量过多、时间效率低、算法计算复杂度高和与最优解的偏差较大等问题（但开和段隆振，2022；李豪等，2023；鄢伦等，2023）。遗传算法是一种高度并行、随机且具备自适应能力的迭代方法，能够有效避免陷入局部最优，最大化缩短与最优结果的差距（李作山等，2019；文传奇等，2023；方占萍等，2023）。但
14、传统遗传算法也存在对初始解与遗传算子设计依赖性和局部收敛性等缺点。为了克服上述问题，本文采用改进的自适应遗传算法用于基站组网方案设计。算法需要对基站的位置坐标进行编码，经过种群配对与迭代计算后，提取最佳基站坐标解集。具体方法为，首先，需要分析定位区域的空间环境条件，作为参数的输入源，以多种常用的组网方式（菱形或方形布设等）形成初步方案；其次，结合改良圈算法优化初步方案，求得初始方案适应度，并选择改良后的基站方案开始进行迭代运算；最后，基于改进的自适应遗传算法生产新的子代解集，并对子代解集进行适应度优化，提高算法解算效率。如图1所示。图 1 基于改进的自适应遗传算法基站部署方案 Fig.1 Ba
15、se station deployment plan based on improved adaptive genetic algorithm 1）染色体编码 在使用遗传算法时，需要先将解算空间的具体 曹昌磊 等：定位传感器基站部署优化方案研究 453 参数转换为染色体表示，也称为编码。编码方式主要有二进制编码法、实数编码法、排列编码法和复数编码法等方式。在满足完备性、健全性和非冗余性的前提下，二进制编码结构简单，且便于遗传和变异操作，在遗传算法中应用最广。因此，本文采用二进制编码方式开展后续研究工作。2）种群的初代优化 遗传算法的解空间主要由种群数目确定，而初始种群决定了算法的初始解及收敛效
16、率。为了保证取得最优解，初始种群应具有一定的规模，需要避免由于大规模搜索空间引起的遗传算法收敛时间过长的问题。同时，初始种群的优劣也直接影响到结果的准确性和算法效率。本文采用Hamilton改良圈算法（薛慧和许苗峰，2020）对初始种群进行优化，以获得较好的父代。3）交叉与变异 改进的自适应遗传算法染色体交叉配对主要采用“门当户对”的方式进行，也就是根据样本的适应度大小确定种群优劣排序，适应度小的父本与适应度小的父本交配，适应度大的父本与适应度大的父本交配。染色体交叉点的节点位置根据Logistic函数序列确定，在选定的父代样本指定位置上完成上述交叉操作。在算法实现中，可以预先指定交叉概率值P
17、j（01）。一般情况下，当所有父本均存在交叉行为时，概率值为1，反之不发生则概率值为0，通常情况概率值较大。每一次实现交叉行为算法时，先产生一个区间大小为01均匀分布的随机数，当概率值小于Pj时，则在对应的序列点上进行交叉操作，反之则不进行操作。此外，与交叉操作类似，在变异操作上可先从交叉后的个体中选择变异个体，预先设定一个介于01的变异概率值Pb，为了保证收敛过程平稳进行，因此，通常变异概率较小，在规定父本的容量N的条件下，则发生变异体的个数Nb=PbN。4）自适应优化 为了提升子代最优解的质量，减小局部最优解的概率，可对遗传变异概率进行自适应改正，避免在变异函数时间序列大空间范围内进行搜索
18、时陷入局部极值，因此，采用式（7）、式（8）进行修正：00averavermaxaveraver()/()，jjjjjjPffffffPPff(7)00averavermaxaveraver()/()，bbbbbbPffffffPPff(8)式中，0jP、0bP 分别为设置的初代交叉和变异概率值；、分别为区间0，1的常数；fj、fb分别为父代交叉和变异样本中的最大适应度值；faver、fmax分别为全体样本的平均和最大适应度。使用遗传算法自适应函数式（6）计算目标函数值（适应度值为该值相反数），当该值越大时，表示此时的个体适应度越小，组网效果较差，反之组网效果较好。4 模拟实验与结果分析 4.
19、1 模拟实验参数预设值 本文以模拟仿真的多层球形体育馆为例，假定球体的最底层圆直径为200 m，共分为四类不同高度层的重点定位区域。其中，四类不同高度层的区域分别为05 m、510 m、1015 m和1520 m，基站信号的最大传输距离为250 m。考虑两种基站布设方案：一是存在固定站（位于顶端），其余为流动站（位于区域的外侧地面）；二是均为流动站（位于区域的外侧地面）。其中，地面站点的基站伸缩长度不高于2 m。图2为基站布设方案示意图。改进的自适应遗传算法参数设置如下：初始样本大小为 N=50，初始交叉和变异概率值0jP、0bP 分别为0.95和0.1；在适应度函数中，最大容忍的 FDOP值
20、为12，四个区域的DOP加权值为 k=1，2，3，4，四个区域DOP越值的加权值为 w=1，2，3，4，即随着楼层高度增加，高层区域为重点定位区域。以各个流动基站坐标为待求参数，进行编码，设置迭代次数为50次，基于组网部署基本准则的整体目标函数，即式（6）值小于10或次数达到最大迭代次数即可停止运算，输出最优基站坐标序列。4.2 结果分析 使用改进的自适应遗传算法对两种布设方案的基站部署进行优化。下表为两种方案和改变基站数量后，各层的平均HDOP、VDOP和PDOP，以及适应度函数值，如表1所示。由表1可知，设立的固定站点能够有效减小VDOP和PDOP，改善在高程方向的精度，不使用 454 J
21、ournal of Spatio-temporal Information 时空信息学报 2023,30(3)图 2 基站布设方案示意图 Fig.2 Base station deployment plan 表 1 改进的自适应遗传算法运算结果 Tab.1 Calculation results of improved adaptive genetic algorithm 有固定站的分层 无固定站的分层 基站数量 HDOP VDOP PDOP 函数值 HDOP VDOP PDOP 函数值 4 1.38 1.42 1.48 1.54 3.70 4.46 6.09 11.00 3.98 4.70
22、6.29 11.16 7.91 1.26 1.25 1.25 1.25 294.79 19.87 9.63 6.39 294.79 19.93 9.74 6.54 80.01 5 1.20 1.18 1.13 1.12 2.83 3.11 3.44 3.48 3.10 3.36 3.65 3.69 3.65 1.10 1.08 1.08 1.09 253.48 17.54 8.54 5.67 253.48 17.59 8.63 5.81 74.16 6 1.08 1.07 1.03 1.04 2.33 2.46 3.15 3.02 2.59 2.71 3.34 3.23 3.18 0.97 0
23、.97 0.97 0.97 216.70 14.45 7.05 4.71 216.70 14.5 7.16 4.85 68.14 7 0.96 0.94 0.91 0.92 2.20 2.35 3.00 2.70 2.42 2.55 3.16 2.88 2.93 0.89 0.88 0.88 0.88 175.48 11.76 5.74 3.83 175.49 11.81 5.84 3.97 61.93 固定站的情况下，两者的HDOP基本相当。同时，随着基站数量增加，终端观测条件得到一定改善，当基站数量从4个增加到7个时，在固定站方案中，HDOP、VDOP和PDOP分别减小20.4%、27.4
24、%、35.9%，49.0%、56.5%、59.4%，47.1%、54.5%、57.8%；在无固定站方案中，HDOP、VDOP和PDOP分别减小了13.1%、22.5%、29.5%，13.7%、26.5%、40.4%，13.7%、26.5%、40.4%。此外，随着高度增加，VDOP和PDOP呈现增减趋势，在固定站方案中，VDOP和PDOP呈现增大的趋势，随着基站数量增加后，这种趋势不明显；在无固定站方案中，VDOP和PDOP呈现减小的趋势。分析出现上述情况的原因主要是，在固定站方案中，由于基站数目增加后，观测条件得到了极大的改善，即使在恶劣的网络结构条件下，仍然能够保持较高的精度；而针对无固定站
25、方案中，由于所有站点位于地面，此时低层的空间高度角基本趋于0，整体观测条件较差，随着高度增加，高度角的改善使得位于高层的观测条件达到最佳。综上所述，基站数量由4到5时，组网效果显著提升，而继续增加基站数量后，DOP值没有明显降低，因此，在兼顾基站成本情况下，选择5个基站更加符合大多数的工程定位应用需求。为了进一步分析组网方式的空间位置精度分布特征，以组网综合情况最佳的5个基站（具备固定站）方案为例，绘制了分层的PDOP等值线图，如图3所示。曹昌磊 等：定位传感器基站部署优化方案研究 455 图 3 5 个基站布设方案的 PDOP 空间分布 Fig.3 Spatial distribution
26、of PDOP for 5 base station deployment plans 随着楼层增加，PDOP整体呈现减小趋势，分布由单一中心区域PDOP最小对称结构变为多中心最小结构，在考虑整体定位范围前提下，重点兼顾高楼层定位区域的精度。因此，在解决组网定位中的基站布设问题时，需要综合考虑固定站与底部流动站和定位区域高度的关系，保证应急情况下作业人员进入室内搜救路线设计安排。5 结 论 本文介绍了定位传感器组网部署的优化方案原理与设计，以模拟的多层球形体育馆仿真实验为例，利用改进的自适应遗传算法对基站组网设计进行优化。分别讨论有固定基站和无固定基站的组网部署方式的DOP分布，分析了基站数量
27、对基站组网的性能影响。结果表明，在建筑物顶端设立固定站能够有效改善VDOP和PDOP，针对一般的二维定位可不需设立固定站，采用无固定站的方式具有较好的平面定位性能；随着基站数量的增加，DOP值得到一定程度的改善，但改进效果越来越不明显。因此，在达到定位条件的情况下，可以综合考虑基站组网的成本，减少基站的数量，在使用4个流动站和1个固定站的方案下，可以使最终的综合效益达到最高，同时定位精度可向重点定位区域方向倾斜，为相关的组网布设提供参考依据。参考文献 陈秉试.2021.基于能耗均衡的无人机集群组网算法.通信技术,54(1):109-114 但开,段隆振.2022.基于最优插入子集的动态规划算法
28、求解旅行商问题.计算机应用与软件,39(12):260-265,297 方占萍,冯黎成,甄亮.2023.新型变截面涡旋型线的多目标遗传算法优化.机床与液压,51(6):97-101 缑慧娟,杨成龙.2020.基于间接平差法的大型烟囱垂直度监测方法的研究.测绘与空间地理信息,43(8):195-197 何琦敏,王坚.2017.一种基于仓库物流定位传感器布设方案.激光杂志,38(4):113-117 何琦敏,王坚,敖佳敏,余航,徐博,杨海潮.2017.IAGA 模型支持下的灾区基站组网优化.测绘通报,(8):7-12 黄瑞贞.2020.非线性最小二乘超宽带 TOA 法在室内定位测量中的研究与实现.
29、测绘与空间地理信息,43(4):214-217,224 李豪,汪磊,张元侨,武越,公茂果.2023.演化多任务优化研究综述.软件学报,34(2):509-538 李作山,李英博,张盈,刘思琦,田雅涵.2019.遗传算法在企业车辆调度优化中的应用研究.内燃机与配件,(18):208-209 廖玉婕.2022.多仓库带容量约束弧路径问题的近似算法和多项式算法.硕士学位论文.上海:华东理工大学 刘大杰,施一民,过静珺.2003.全球定位系统(GPS)的原理与数据处理.上海:同济大学出版社 刘永信,王玲琳,张晖,王朝霞,杨治.2021.遥感卫星组网观测资源调度中的数学建模与优化问题.内蒙古师范大学学报
30、(自然科学汉文版),50(4):308-313 刘修宇,江涛,厉彦一.2021.基于机器学习中分辨率遥感影像分类456 Journal of Spatio-temporal Information 时空信息学报 2023,30(3)应用研究.地理信息世界,28(4):66-73 梅志虎,唐志波.2023.求解三维装箱问题的启发式搜索算法.中国水运,(3):92-94 曲明,丁涛,李立,迟方德,贺元康,陈天恩,王凤宇.2022.从NP-Hard 到多项式时间算法的大规模机组组合近似线性规划:双重凸包模型.中国电机工程学报,42(9):3261-3276 施志荣.2019.基于 UWB 技术的无线
31、火警定位系统的研究.闽南师范大学学报(自然科学版),32(4):51-56 孙公德,郭勇,沈建,赵蕾莛,张忠元.2017.分布式超宽带雷达地震被困人员协同探测技术.震灾防御技术,12(4):966-977 王宁,王坚,韩厚增.2020.UWB 应急组网定位系统的设计与实现.测绘科学,45(6):73-79 文传奇,月敏丁,杨鑫,何友苗.2023.基于遗传算法与仿真联合的车间调度方案优化.制造业自动化,45(5):55-59 薛慧,许苗峰.2020.Hamilton 模型在智慧文旅设计中的应用研究.邮电设计技术,(2):28-31 薛伟莲,赵娣,张颖超.2020.室内定位研究综述.计算机与现代化
32、,(5):80-88 鄢伦,耿攀,文书礼.2023.基于启发式算法的智能机舱储能优化配置研究.船电技术,43(5):25-28 杨燈,王坚,韩厚增,刘飞.2020.地下综采面超宽带自组网人员定位系统.测绘科学,45(1):11-18,41 杨雄,吴东.2021.遗传算法在经典密码分析中的应用综述.信息工程大学学报,22(5):577-583 周宇泰,徐岳,李宇,蒋国韬.2022.基于遗传算法的干扰态势下三维雷达网优化布站方法.空天防御,5(1):52-59 Wang C Y,Ning Y P,Wang J,Zhang L P,Wan J,He Q M.2022.Optimized deploy
33、ment of anchors based on GDOP minimization for ultra-wideband positioning.Journal of Spatial Science,67(3):455-472 Research on optimization of deployment plans for positioning sensor base stations CAO Changlei1,CHEN Zhida1,GONG Xiaoyu2,HONG Nianxiang2 1.Natural Resources Monitoring Center of Shangyu
34、 District,Shaoxing 312300,China;2.Zhejiang Academy of Surveying and Mapping Science and Technology,Hangzhou 310012,China Abstract:Indoor positioning technology serve as a complementary solution to satellite positioning,overcoming the shortcomings posed by satellite signals that struggle to pass thro
35、ugh buildings.The reasonable deployment of sensor base stations is the key to achieve high-precision indoor positioning.To improve the accuracy of location services provided by sensors,this paper studies a base station deployment scheme based on utilizing an improved genetic algorithm.Taking dilutio
36、n of precision(DOP)as the evaluation index,we analyze the influence of base stations with different numbers,locations,and environmental conditions on the location performance.Taking a simulated spherical gymnasium as an example,the proposed optimization scheme is well applied to the scene of rapid networking and has a good reference value.Key words:DOP;positioning sensor;network optimization;indoor positioning Supported by 2021 Science and Technology Project of Zhejiang Provincial Department of Natural Resources(2021-55)
