无线电区域定位系统的分布式空间基准自主建立技术

窦子铮，姚 铮，2，陆明泉，2

（1. 清华大学电子工程系，北京 100084；2. 北京国家信息科学技术研究中心，北京 100084）

1 引言

随着大数据和物联网技术的发展，环境监测、物流管控、智慧城市等基于位置服务的应用被大量催生［1，2］，而以无线传感器网络（Wireless Sensor Network，WSN）和伪卫星定位系统（Pseudolite Positioning System，PPS）为代表的无线电区域定位系统（Radio Local Positioning System，RLPS）也受到了广泛的关注［3］. 传统的RLPS 在初始布设时，需要先利用一些坐标已知的点作为锚点在区域内建立空间基准，然后通过节点之间的信号收发，测量节点与锚点之间的空间关系，比如距离或方位等，进而算出节点的位置坐标［4～6］. 一般来说，锚点的位置可以利用全球卫星导航系统（Global Navigation Satellite Systems，GNSS）获得［7］，或者直接通过人工测绘将锚点放置在坐标已知的位置. 但是在很多应用场景下，节点的位置并不容易提前获得. 比如在地震灾区、火灾现场、外星探索等应用场景下，无法通过GNSS信号或提前测绘获取参考点的坐标［8］；或者对于大范围的RLPS，手动测绘节点的位置费时费力，极大地限制了RLPS 的应用范围. 因此，为了实现RLPS 的灵活、快速部署，迫切需要研究利用节点之间测距完成节点坐标估计的空间基准自主建立技术［9，10］.

在复杂的应用场景下，节点间的无线通信可能会受到较强的干扰，甚至会出现节点损坏的情况，这就对RLPS 空间基准自主建立技术的鲁棒性和可扩展性提出了更高的要求. 相对于需要测距结果集中在中心处理器上进行运算的集中式算法［11～14］，仅利用相邻节点的测距和定位信息并将计算任务分摊在每个节点的分布式算法在鲁棒性、计算复杂度和通信能耗等方面具有更大的优势［15］，更能满足大范围RLPS 的需要. 但是由于分析局部行为与全局行为关系的复杂性［16］，高精度的分布式算法设计是基准自主建立技术面临的重要挑战. 除此之外，为了支持RLPS 的快速部署以及多定位体系系统的融合，基准自主建立技术还需要满足低耗时、低复杂度的要求，并能够在部分锚点存在的情况下，支持分布式的节点绝对坐标获取.

近年来，分布式的基准自主建立技术开始受到更多的关注. DV-Hop（Distance Vector-Hop）算法［17］从几个位置已知的锚点出发，将位置信息发送给系统中的其他节点，每一个节点用一个表来记录与各个锚点的最短距离，之后再用三边定位的方法估计出每个节点的位置. Hop-Refinement 算法［18］将定位分成了两个阶段，在第一个阶段中，采用类似于DV-Hop 的算法获得各个点位置的初值，第二个阶段中，通过迭代来更新优化各个点的坐标，直到收敛得到系统中节点最终的坐标. VNDV-Hop（Volume Node Distance Vector-Hop）算法［19］使用更精确的连跳数值对算法进行了改进以提升定位的精度. Ji 等人［20］将一个大的区域分成几个小的区域，在每个小区域内分别计算出各个节点的相对坐标，再利用区域之间重叠部分的点将各个小区域拼起来形成一个完整的区域坐标图. 以上4 种分布式方法并没有分析每个节点的局部优化行为与系统的全局优化行为之间的关系，最终得到的定位结果并不是全局最优的，定位误差较大. 相比于上述关注局部最优化的算法，也有一些分布式算法是以全局最优为目标求解节点坐标. 非参数的置信传播（Nonparametric Belief Propagation，NBP）算法［21］从概率图的角度入手，将联合后验分布边缘化的计算分解至节点间的置信度传播来进行，利用蒙特卡洛思想，将粒子化的坐标概率分布在节点之间传递，最终能够得到与集中式算法接近的定位精度. 但算法的计算复杂度高，定位精度受粒子数影响大，对节点的计算能力要求高. 交替坐标下降法（Alternating Coordinate Descent，ACD）［22］以处处可微的sstress［23］为代价函数，将全局优化函数分解到各个节点的各个坐标来进行迭代优化，每次更新特定点的单个坐标，收敛后即可得到全局最优的高精度定位结果. 该算法已经在麦克风阵列定位［24］等领域得到了应用. 但是该算法需要节点依次在坐标更新后将结果广播给相邻节点，并没有发挥分布式算法在各节点的算力优势并且定位耗时长；同时算法未考虑部分节点坐标已知的情况，无法直接得到各节点的绝对坐标.

针对上述分布式算法定位存在的精度低、定位耗时长以及绝对坐标获取复杂的问题，本文在ACD 算法的基础上进行了改进，提出了并行坐标下降法（Paralleled Coordinate Descent，PCD）. 所提算法在对并行优化收敛性分析的基础上，通过寻找节点拓扑中的独立集，提出了节点分组算法与并行优化策略，提高了可同时更新坐标的节点数量，缩短了定位耗时；同时通过深度融合距离测量信息和锚点位置信息，支持对锚点信息的分布式利用，可以得到各节点的绝对坐标并进一步提升了定位精度. 仿真和实测实验表明，本文提出的PCD 算法可以支持高效率、高精度的节点绝对坐标获取，能够快速、分布式地完成RLPS 的空间基准自主建立任务.

2 问题描述与相关工作

2.1 问题描述

考虑在RLPS 覆盖的P维空间内（P一般取2 或者3），有N个无线电节点，第i个节点的坐标为xi=(xi，1，xi，2，…，xi，P)，则 系 统 中 节 点 的 坐 标 集 合 为X=[x1，x2，…，xN] ∈RN×P. 第i个节点和第j个节点之间的欧氏距离dij可以表示为

但是在实际的测量中，噪声、功率和遮挡等问题会使得观测到的距离是带噪声的，并可能存在缺失的情况. 因此可以将测距结果表示为

其中，εij表示测距的噪声；eij表示第i个节点与第j个节点间距离是否可以测得，1表示可以测得，0表示无法测得. 以s-stress准则［23］定义代价函数f(X)为

RLPS 的空间基准自主建立过程可以建模为求解式（4）所示的优化问题：

2.2 ACD算法原理

ACD 算法将代价函数f(X)在每一个节点上进行了分解，得到

其中，fi(X)表示第i个节点与其相邻节点的坐标估计误差，即

在此基础上，式（4）所示的全局优化行为与单个节点的局部优化行为存在着简单的对应关系，即

式（7）意味着当每一个局部代价函数fi(X)对每一个坐标xi都导数为零达到最小值时，全局代价函数f(X)也就达到了最小值. 因此只需依次在每个节点上对每个坐标进行独立优化更新求出当前条件下的最小值，并将更新后的结果发送给相邻节点，通过迭代即可完成对整个优化问题的求解.

2.3 ACD算法缺陷分析

根据第2.2 节对ACD 算法原理的介绍可以看出，该算法需要所有节点依次完成坐标更新并广播更新结果. 也就是说，当一个节点进行计算和广播时，其他节点都不进行计算. 这样的串行处理对于节点的计算资源是非常浪费的，尤其是在大范围定位系统中，该算法需要经过较长的时间来依次遍历每一个节点来完成一次迭代，大大延长了系统完成基准建立的时间.

除此之外，ACD 算法由于仅利用了节点间的测距结果，只能得到节点的相对坐标. 但是当其中一些锚点的绝对坐标已知，希望获得所有节点的绝对坐标时，普遍的方法是使用坐标匹配技术［25］，将算法得到的相对坐标变换为绝对坐标. 但是这个过程并不能很好地利用锚点的位置信息，因为当相对坐标求出之后，系统的拓扑结构已经被决定了，之后的匹配工作只是将系统整体移动到某一固定的位置，但是定位精度并不会再次提升. 除此之外，坐标匹配需要将锚点的信息汇聚到一个处理器上计算，计算出结果之后再分发给各个节点. 这个过程非常明显是属于集中式的方法，而与我们希望建立的分布式系统存在直接的矛盾.

本文在提出改进后的PCD 算法时，分析了算法并行更新的条件，提出了并行更新的策略，另外，针对可能存在的锚点位置信息，提出了适合于分布式系统的绝对坐标获取方式.

3 PCD算法

3.1 坐标下降法

PCD 算法采用坐标下降法来完成每个节点的坐标迭代更新. 假设经过了k次更新迭代，在第k+1 次迭代中，坐标被更新，则有

多项式各阶次的系数分别是

其中，Ni是第i个节点相邻的节点个数.

当fi(X(k+1))取得最小值时导数应该为0，于是就得到了一个三次方程，相应的，最多只有3 个解. 由于其他量的数值在之前的更新或者已知条件中已经给出，可以直接解出所有的解. 然后将各个解带入

fi(X()

k+1)中找到使其最小的解，即为本次对坐标xi，p的更新增量，则可以得到经过k+1 次更新的坐标为

在更新完坐标xi，p之后，继续更新第i个节点其余的坐标以及其他节点的坐标. 所有节点均完成更新，视为完成一次迭代. 经过多次迭代收敛后，即可得到式（4）所示优化问题的解

通过上述流程可以看出，在使用坐标下降法求解节点坐标的过程中，所需要的只是各个节点与其相邻节点测距和坐标更新结果，因此可以仅仅通过相邻节点的单跳通信来完成，能够适应于分布式的系统布设.

3.2 并行更新条件

如2.2 节中所述，在ACD 算法中，节点需要串行地依次完成坐标的更新与广播，因为该算法的思路是将代价函数f(X)分解到各个节点上计算，即转变为f(x1，x2，…，xN)，对每一个节点的坐标进行迭代. 假设第k次迭代后，函数结果为在串行的计算过程中，第k+1 次迭代开始，首先计算得到，使得

在发送新的坐标后，计算，使得

以此类推，完成第k+1 次迭代之后，得到了代价函数的结果f(X()

k+1)，同时保证如下结果：

因此串行的计算过程能够保证算法在各个节点有足够的邻接节点的情况下收敛到一个稳定的结果. 在并行更新策略的设计中，这样迭代收敛的一致性也是需要得到保证的.

由式（9）可知，当eij=0，即第i个节点和第j个不相邻时，更新坐标xi的过程不会受到坐标xj的影响，因此当两个节点同时更新坐标时，计算结果将与它们依次更新的结果相同，从而能够保证式（13）所示的迭代收敛的一致性. 由此便得到了坐标下降法并行更新的条件：当一组节点互不相邻时，可以同时使用坐标下降法更新它们的坐标，而不会影响优化函数整体的收敛结果.

值得注意的是，在并行更新条件的约束下，越稀疏的节点连接，能够支持越多的节点同时完成坐标更新结算而不影响算法的最终收敛，也就能够比串行的ACD算法节约更多的通信和计算时间.

3.3 节点分组算法

根据第3.2节提出的并行更新条件，为了使多个节点能够并行完成坐标下降更新，需要根据节点的相邻情况将节点集合划分成互不相连的子集. 这一问题类似于组合优化问题中的最大独立集问题，是一个NP 难问题［26］. 因此本文结合系统的分布式设计和计算复杂度，提出了一种启发式的节点分组算法.

节点的分组利用节点之间的通信来完成. 各个节点按照编号依次进行如下两步操作：

（1）选择除了已收到的相邻节点组号之外的最小正整数作为自己的组号；

（2）将自己的组号广播发送给所有相邻节点.

经过一次遍历操作，所有节点即可获得自己的组号，完成分组. 该算法操作简单，易于分布式实现. 在各节点得到自己组号之后，相同组号的节点即可在收到仅次于自己组号的节点更新结果后，同时开始计算和广播，完成同组节点的并行坐标更新.

3.4 绝对坐标获取

当RLPS 中存在部分绝对坐标已知的锚点时，需要为式（4）所示的优化问题添加相应的约束条件. 假设锚点的集合为A，对于锚点i∈A，已知其绝对坐标为ai=(ai，1，ai，2，…，ai，P)，则各节点获取绝对坐标的空间基准建立可以建模为

在添加的约束条件下，优化问题解得的系统拓扑结构与无约束优化情况的解是基本相同的，但是由于锚点已经约束固定在了绝对坐标的位置，其余各节点也就收敛到了各自的绝对坐标位置上.

当使用坐标下降法求解式（14）所示的优化问题时，因为每一步的迭代都是将相邻节点的当前更新值作为已知约束来计算，所以只需要将各个锚点的坐标作为其相邻节点更新值即可，即将式（8）改为

在此基础上，通过坐标下降完成节点坐标的更新，经过迭代即可完成对式（14）所示问题的求解，以分布式的方式获得各个节点的绝对坐标.

3.5 PCD算法流程

PCD 算法的流程如图1 所示. 在系统节点布设完成后，先经过节点之间的通信和测距，得到测距结果和节点拓扑，并利用本文提出的分组算法完成节点分组，接着使用算法1 所示的坐标更新算法，输入测距结果、节点分组和锚点坐标等信息，计算得到各个节点的绝对坐标，完成空间基准的自主建立.

图1 PCD算法流程示意图

算法1 坐标更新算法输入:距离测量结果、节点分组结果、锚点坐标信息输出:节点的绝对坐标算法步骤:1. 将锚点坐标信息赋值给对应节点;3. DO 4. 按照节点分组结果遍历各组互不相连的点集;5. 基于式(15)使用坐标下降法同时完成组内所有节点的坐标更新;6. 将更新后的坐标广播发送给相邻节点;7. 完成一次迭代;8. UNTIL 结果收敛或达到最大迭代次数

4 仿真与实测结果

4.1 仿真实验

为了验证本文提出的PCD 算法的性能，使用MATLAB 平台对三维空间中的定位情况进行了仿真.随机布设N个节点，其中有A个坐标已知的锚点. 假设每个节点只能在半径为R的圆形范围内进行通信，距离大于R则认为两个节点不是邻接节点，无法相互测距.得到的测距结果带有服从标准差为σ的高斯噪声. 定位误差为

为了展现PCD 算法的定位精度，在10×10×10 的立方体区域内，进行了100 次蒙特卡洛实验. 每次实验中，随机布设N=100 个节点，并选择R=15 作为最大测量半径. 图2 绘制了ACD 算法和PCD 算法在取10 个和30 个锚点时，在不同噪声标准差σ下，100 次实验的平均定位误差，并与集中式的SDR（Semidefinite Programming Relaxation）算法［12］进行了对比. 从图2 可以看出，在锚点数目相同时，本文提出的分布式的PCD 算法具有比集中式的SDR 算法更优的定位精度；而与ACD 算法相比，PCD 算法中锚点的位置信息得到了更好的利用，能够利用自身携带的位置信息减小整个系统的定位误差，因此随着锚点数目的增多，定位精度得到了显著的提升.

图2 不同算法定位误差对比图

为了比较大范围RLPS 中算法的运行时间，假设系统覆盖的区域随节点数目的增大而增大，并保持一定的节点布设密度. 该设置在实际的大规模RLPS布设中也是非常合理的. 假设节点完成一次更新计算与广播的耗时为1，图3 绘制了在选取布设密度为1，最大测量半径R=7 的条件下，ACD 算法和PCD 算法在不同节点数下的总耗时的变化. 可以看出，两种算法的总耗时存在明显的差异，并且差异随着节点数目的增多，耗时差异愈发显著. 当节点总数N=1600 时，ACD 算法的耗时是PCD 算法的25 倍左右. 可以预见，随着节点数目的增加，PCD算法对时间的节约效果将会更加明显.

图3 两种算法定位耗时对比图

4.2 实测实验

为了证明论文所提技术在实际使用场景下的有效性，在楼道场景和泳池场景中，分别对PCD 算法在二维和三维空间中的表现进行了实测实验. 本实验使用Decawave TREK1000完成节点之间的相互测量，这是一个基于超宽带技术［27］使用双向传播时间进行测距的开发板. 超宽带技术具有较高的测距精度和较好的抗多径效果，也是现在常用的无线通信测距技术.

楼道场景的实验如图4所示，在有拐角的楼道中布设Decawave TREK1000 开发板作为RLPS 节点，并利用无线通信完成测距. 在此场景下，受楼道墙体遮挡的影响，直线连接经过墙体的两节点无法相互测距. 假设楼道两段的节点是位置已知的锚点，利用得到的距离信息，分别使用PCD 算法、ACD 算法和SDR 算法进行分析、定位.PCD 算法的定位结果与实际布设位置的对比如图5 所示. 可以看出二维定位的效果非常接近于节点的实际位置.

图4 楼道布设示意图

图5 楼道定位效果示意图

图6为3种算法各节点定位误差的累积分布图. 可以看出，在楼道场景下，PCD 算法对各节点的定位误差不超过0.3 m，其精度优于ACD 算法和SDR 算法. 经过计算，PCD 算法的平均定位误差为0.14 m，明显优于ACD算法的0.22 m和SDR算法的0.58 m.

图6 楼道节点定位误差累积分布图

泳池场景的实验如图7所示，在一个空旷泳池的周围和中心布设开发板作为RLPS节点完成测距. 其中各节点坐标真值利用全站仪测量得到，用以锚点赋值和对比定位误差. 假设在泳池四周和中心选取部分节点作为位置已知的锚点，利用得到的距离信息，分别使用PCD 算法、ACD 算法和SDR 算法进行分析和定位.PCD算法的定位结果与实际布设位置的对比如图8 所示.可以看出，三维定位的效果非常接近于节点的实际位置.

图7 泳池布设示意图

图8 泳池定位效果示意图

图9为3种算法各节点定位误差的累积分布图. 可以看出，在泳池场景下，PCD 算法对各节点的定位误差不超过0.6 m，其精度优于ACD 算法和SDR 算法. 经过计算，PCD 算法的平均定位误差为0.29 m，明显优于ACD算法的0.34 m和SDR算法的0.63 m.

图9 泳池节点定位误差累积分布图

通过上述两组实测实验可以看出，不论是在二维还是三维的实际定位应用中，本文提出的PCD 算法都能够得到高精度的节点绝对坐标估计结果，从而支持RLPS的空间基准自主建立.

5 结论

为了解决RLPS 的分布式空间基准自主建立问题，本文在ACD 算法的基础上提出了PCD 算法. 在对收敛约束下节点并行更新条件分析的基础上，提出了启发式的节点拓扑独立集分组算法，设计了节点坐标的并行更新策略，使得算法能够有效缩短系统定位耗时. 同时，为了在锚点的辅助下获得各节点的绝对坐标，该算法将锚点信息与测距信息进行了深度融合，完善了优化模型，实现了分布式的绝对坐标获取. 仿真和实测实验表明，与传统ACD算法相比，分布式的PCD算法可以得到高精度的节点绝对坐标估计，完成空间基准自主建立任务，并且大幅缩短RLPS 的空间基准自主建立任务的定位耗时.