实验室论文被IEEE/ACM Transactions on Networking录用
实验室在在线性定位可定位性研究被IEEE/ACM Transactions on Networking (TON)长文录用。TON是计算机网络领域的顶级国际学术期刊。
论文题目：Understanding Node Localizability in Barycentric Linear Localization
研究背景：
随着诸如Received Signal Strength, UWB, LoRa RTT等无线测距技术的发展，基于测距的定位技术取得了广泛应用。例如，在COVID-19流行期间，UWB测距技术已被用于社交距离监测和接触者追踪；UWB模块也已被部署在最新的智能手机、智能手表和物联网设备中。这意味着测距技术在位置敏感的服务中的应用前景广大。在无线测距定位技术中，基于重心坐标的线性定位(BLL)是一种新型的、轻量级的定位方案，具有分布式、保证收敛到全局最优的显著优点。BLL仍存在关键限制：全部节点都需是可定位的。否则，不可定位的节点会在位置更新过程中会不断地传播错误位置信息，使得可定位的节点也会收敛到错误位置。我们探究了分布式节点定位性理论和算法，保留BLL固有优点的同时，提高了BLL定位方案的适用范围。
解决方案：
我们分析得出，BLL可定位性降低的本质原因是对节点邻域连通性要求高，否则无法完成线性定位系统的构建。因此，我们设计了隐藏边推断算法(NEI)来加强连通性。NEI算法由于以下特性，与BLL方案契合度高：1)NEI是完全分布式的；2)NEI面向节点邻域，专门加强邻域连通性。
图1：NEI通过加强邻域连通性提高了BLL可定位性。其中圆圈标记表示可定位节点，叉号标记表示不可定位节点。
考虑到BLL是分布式定位方案，我们基于本团队之前提出的中心式节点定位性理论和算法，进一步设计了分布式路径拓张与剪枝算法(Path Extension and Pruning, PEP)来查找BLL可定位节点。核心思想是每个节点维持一个列表来记录自己到锚点的不相交路径集合，此列表初始化为空，节点在邻域范围交换和拓展这张表，最终在列表收敛不再更新时，即可获得不相交路径的完整信息。同时，此分布式算法从理论上被证明可以取得和中心式算法相同的查找结果。为了降低通信开销，我们设计了加速版本的分布式算法(Fast-PEP)，优化了路径列表的交换和更新规则。实验结果表明，在降低大量开销的同时，Fast-PEP还能保证接近于PEP的查找结果，几乎不会丢失BLL可定位节点。
图2：PEP/Fast-PEP与现有定位性节点查找算法的时间开销比较
图3：PEP/Fast-PEP与现有定位性节点查找算法的可定位点检测性能比较
另外，我们部署了一个小型UWB系统，验证得出：分布式PEP/Fast-PEP算法能帮助BLL收敛到正确位置。
图4：UWB定位系统验证结果，其中圆圈标记为真实位置，星号标记为算法收敛位置。
论文信息：
Haodi Ping, Yongcai Wang, Deying Li, Wenping Chen. Understanding Node Localizability in Barycentric Linear Localization, IEEE/ACM Transactions on Networking (TON), 2022.
作者简介：
第一作者：平皓弟，中国人民大学信息学院2018级博士生，计算机应用技术专业，主要研究方向包括无线定位、网络定位性、图优化等。
通讯作者：王永才，中国人民大学信息学院计算机系副教授，主要研究方向为大规模图结构挖掘与计算、智能物联网的感知、定位、建图算法与应用。
