智能网络与优化实验室王永才副教授团队论文被ACM Transactions on Sensor Networks录用
我院智能网络与优化实验室王永才副教授团队在无线测距定位领域中的可定位性研究被ACM Transactions on Sensor Networks (TOSN)长文录用。TOSN是计算机网络领域的知名国际学术期刊。
论文题目：On Node Localizability Identification in Barycentric Linear Localization
通讯作者：王永才
研究背景：
近期，Wi-Fi往返时间(RTT)测距、LoRa RTT测距、超宽带(UWB)测距等无线测距技术正在推动基于测距的定位方案快速发展。例如，在COVID-19流行期间，UWB测距技术已被用于社交距离监测；最新的Apple iPhone 11-14也配备了UWB收发器，这意味着测距技术是位置信息敏感的服务的新兴推动力。在无线测距定位技术中，基于重心坐标的线性定位(BLL)是一类有潜力的定位方案，具有分布式、保证收敛到全局最优的显著优点。然而，BLL的一个关键限制是全部节点都需是可定位的。否则，不可定位的节点会在位置更新过程中会不断地传播错误位置信息，使得理论上可定位的节点也会收敛到错误位置。目前，BLL中节点可定位性的研究仍非常缺乏，极大地限制了BLL的应用范围。因此，研究团队成员补充了关于BLL可定位性理论，并设计了相对应的判断算法，进而提高了BLL定位算法的实用性。
图1：现有BLL算法收敛结果。其中圆圈标记是真实位置，星号标记为计算位置。
解决方案：
本文首次系统性地探究了BLL定位性理论，包括BLL节点可定位性的充分条件和必要条件。我们得出，在BLL过程中，每个节点需要在d维空间中有不少于d+1个相互连接的邻居才能完成线性系统的构建，这也是节点BLL可定位的必要条件；关于充分条件，我们证明了如果节点满足1）在重心坐标生成图中到锚点有不少于d+1条节点不相交路径，2）路径上的点到锚点也有不少于d+1条节点不相交路径，那么它是BLL可定位的。
为了识别出这些BLL可定位性点，我们基于提出的充分条件设计了识别算法。其核心思想是将不相交路径的查找转换为网络最大流问题，识别出少于d+1条节点不相交路径的节点并将其剔除，然后重新构建重心坐标生成图、重新识别和剔除上述节点，迭代执行此过程，最终即可得到满足充分条件的全部BLL可定位节点。
识别出可定位点后，在BLL过程中，每个节点只从可定位的邻居接收信息来参与自己的位置更新，从而排除不可定位点的错误位置影响。实验结果表明，我们的先识别再剔除的BLL改进方案，在保留BLL显著优点的同时，解除了全部节点必须可定位的限制，提高了BLL的实用性。
图2：本文设计算法收敛结果。
图3：三维空间定位结果比较。
论文信息:
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.
作者简介：
第一作者：平皓弟，中国人民大学信息学院2018级博士生，计算机应用技术专业，主要研究方向包括无线定位、网络定位性、图优化等。
通讯作者：王永才，中国人民大学信息学院计算机系副教授，主要研究方向为大规模图结构挖掘与计算、智能物联网的感知、定位、建图算法与应用。
