智能网络与优化实验室（InLab）论文被计算机网络顶级期刊连续录用

我院智能网络与优化实验室王永才副教授团队在分布式定位算法方面可定位性研究被计算机网络领域期刊ACM Transactions on Sensor Networks (TOSN)和IEEE/ACM Transactions on Networking(TON)长文录用。TON、TOSN是计算机网络领域的国际顶级学术期刊。

研究背景：

随着诸如Received Signal Strength, UWB, LoRa RTT等无线测距技术的发展，基于测距的定位技术取得了广泛应用。基于无线测距的定位在位置敏感的服务中的应用前景广大。在无线测距定位技术中，基于重心坐标的线性定位(BLL)是一种新型的、轻量级的定位方案，具有分布式、保证收敛到全局最优的显著优点。然而，BLL的一个关键限制是节点都需是可定位的。否则，不可定位的节点会在位置更新过程中会不断地传播错误位置信息，使得理论上可定位的节点也会收敛到错误位置。目前，BLL中节点可定位性的研究仍非常缺乏，极大地限制了BLL的应用范围。因此，研究团队成员补充了关于BLL可定位性理论，并设计了相对应的判断算法，进而提高了BLL定位算法的实用性。

首先在TOSN的工作中，我们设计了一种集中式的BLL可定位性判定方法，提出了一种基于迭代最大流的高效的可定位性判定策略。之后再TON的工作中，我们进一步改进，提出一种完全分布式的BLL可定位性的判定策略，系统的解决了BLL定位算法可定位性判定的相关工作。

论文题目：On Node Localizability Identification in Barycentric Linear Localization

论文作者：平皓弟，王永才，申兴发，李德英，陈文萍

通讯作者：王永才

中心式解决方案[1]：

本文首次系统地探究了BLL定位性理论，包括BLL节点可定位性的充分条件和必要条件。我们观察得出，在BLL过程中，每个节点需要在d维空间中有不少于d+1个相互连接的邻居才能完成线性系统的构建，这也是节点BLL可定位的必要条件；关于充分条件，我们证明了如果节点满足1）在重心坐标生成图中到锚点有不少于d+1条节点不相交路径，2）路径上的点到锚点也有不少于d+1条节点不相交路径，那么它是BLL可定位的。

为了进一步识别出这些BLL可定位性点，我们基于提出的充分条件设计了识别算法。其核心思想是将不相交路径的查找转换为最大流问题，识别出少于d+1条节点不相交路径的节点并将其剔除，然后重新构建重心坐标生成图、重新识别和剔除上述节点，迭代执行此过程，最终即可得到满足充分条件的全部BLL可定位节点。

识别出可定位点后，即可在BLL过程中，只从可定位的邻居接收信息来参与自己的位置更新，从而排除不可定位点的影响。实验结果表明，我们的先识别再剔除的BLL算法，在保留BLL显著优点的同时，解除了全部节点必须可定位的限制，提高了BLL的实用性。

图1：现有BLL算法收敛结果。其中圆圈标记是真实位置，星号标记为计算位置。

图2：本文设计算法收敛结果

(a)现有算法收敛结果	(b)本文提出算法收敛结果
图3：三维空间定位结果比较

论文题目：Understanding Node Localizability in Barycentric Linear Localization

论文作者：平皓弟，王永才，李德英，陈文萍

通讯作者：王永才

分布式解决方案[2]：

考虑到BLL是分布式定位方案，而文章[1]中提出迭代最大流查找算法为中心式，我们进一步设计了分布式算法(Path Extension and Pruning, PEP)来查找BLL可定位节点。核心思想是每个节点维持一个列表来记录自己到锚点的不相交路径集合，此列表初始化为空，节点在邻域范围交换和拓展这张表，最终在列表收敛不再更新时，即可获得不相交路径的完整信息。同时，此分布式算法从理论上被证明可以取得和中心式算法相同的查找结果。为了降低通信开销，我们设计了加速版本的分布式算法(Fast-PEP)，优化了路径列表的交换和更新规则。实验结果表明，在降低大量开销的同时，Fast-PEP还能保证接近于PEP的查找结果，几乎不会丢失BLL可定位节点。此外，我们还设计了隐藏边推断算法(NEI)来加强连通性。NEI算法由于以下特性，与BLL方案契合度高：1)NEI是完全分布式的；2)NEI面向节点邻域，专门加强邻域连通性。

图4：PEP/Fast-PEP与现有定位性节点查找算法的时间开销比较

图5：PEP/Fast-PEP与现有定位性节点查找算法的可定位点检测性能比较

另外，我们部署了一个小型UWB系统，验证得出：同中心式算法一样，分布式PEP/Fast-PEP算法也能帮助BLL收敛到正确位置。

图6：UWB定位系统验证结果，其中圆圈标记为真实位置，星号为算法收敛位置。

论文信息：

[1] Haodi Ping, Yongcai Wang, Xingfa Shen, Deying Li, Wenping Chen. On Node Localizability Identification in Barycentric Linear Localization, ACM Transactions on Sensor Networks (TOSN), 2022.

[2] Haodi Ping, Yongcai Wang, Deying Li, Wenping Chen. Understanding Node Localizability in Barycentric Linear Localization, IEEE/ACM Transactions on Networking(TON), 2022.

作者简介：

平皓弟，中国人民大学信息学院2018级博士生，计算机应用技术专业，主要研究方向包括无线定位、网络定位性、图优化等。

王永才，中国人民大学信息学院计算机系副教授，主要研究方向为大规模图结构挖掘与计算、智能物联网的感知、定位、建图算法与应用。