期刊
IEEE TRANSACTIONS ON MOBILE COMPUTING
卷 21, 期 3, 页码 986-1003出版社
IEEE COMPUTER SOC
DOI: 10.1109/TMC.2020.3015480
关键词
Network localization; negative edges; sparse networks; flipping free condition; tree of non-flipping components; component synchronization
资金
- National Natural Science Foundation of China [61972404, 61672524, 11671400]
- Fundamental Research Funds for the Central University
- Research Funds of Renmin University of China [2015030273]
This paper investigates the problem of inferring network topology using inter-node distance measurements. It proposes local flipping-free condition, global flipping-free condition, and component-based flipping free condition to disambiguate flipping ambiguities caused by separators. A disambiguating framework based on these conditions is proposed, and a residue-based weighted component stitching algorithm is used to generate global coordinates of the network.
Inferring network topology via inter-node distance measurements is an important problem. It is challenging when the distance measurements are sparse because the lack of edge constraints may lead to ambiguous realizations that differ greatly from the ground truth. The flipping ambiguities are caused by binary vertex cut sets in 2D and triple vertex cut sets in 3D, which are called separators. This paper investigates conditions on whether the flipping ambiguities caused by these separators can be disambiguated using neighborhood, full graph, and component-level conditions. Accordingly, local flipping-free condition (LFFC), global flipping-free condition (GFFC), and component-based flipping free condition (CFFC) are proposed. Then a disambiguating framework based on a combinatorial application of these conditions is proposed. It detects separators and first disambiguate separators locally by LFFC, which converts the graph to a binary tree, whose leaf nodes are flipping-free components and edges are LFFC unsolvable separators. Then the CFFC condition is further applied to disambiguate LFFC unsolvable separators between components. If k and g separators are disambiguated by LFFC and CFFC respectively, the number of ambiguous solutions for network localization will be reduced by 2(k+g) times. Finally, the flipping-free components realize node coordinates in their local coordinate systems and a residue-based weighted component stitching algorithm (RWCS) is proposed to iteratively synchronize components' local coordinates to generate global coordinates of the network. Extensive simulations show the LFFC, CFFC and RWCS frameworks are efficient, which resolve a major portion of flipping ambiguities and greatly improve the localization accuracy than the state of art algorithms in various sparse network settings.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据