TY - JOUR
T1 - WCS
T2 - Weighted Component Stitching for Sparse Network Localization
AU - Sun, Tianyuan
AU - Wang, Yongcai
AU - Li, Deying
AU - Gu, Zhaoquan
AU - Xu, Jia
N1 - Publisher Copyright:
© 1993-2012 IEEE.
PY - 2018/10
Y1 - 2018/10
N2 - Network location is one of the critical issues and a challenge in wireless sensor and ad hoc networks, in particular when networks are sparse. However, even in highly sparse networks, there exist well-connected subgraphs while the distribution of the networks is random. This paper introduces weighted component stitching (WCS) to find redundantly rigid components with high redundant ratios, which can be used to generate reliable local realization. Finding and ranking the redundantly rigid components is an NP-hard problem (a reduction from maximum quasi-clique). Here, we introduce a series of theorems and algorithms to carry out WCS efficiently. More precisely, we prove that each graph has a determinant number of redundantly rigid components, each redundantly rigid component is covered by a set of basic redundant components (BRCs), and each BRC contains one redundant edge. We apply constraints to merge the BRCs to form components with higher redundancy ratio and develop a greedy algorithm to merge BRCs to form locally mostly redundant components (LMRCs). Finally, we give the approximation ratio. The local coordinates of nodes are calculated by optimization in each LMRC and are synchronized with weights to produce the global coordinates of nodes in the network to overcome the sparseness of subgraphs. Extensive experiments demonstrate significant improvements in accuracy (45%-64%) using our WCS method over the state-of-the-art algorithms under various settings of network sparseness and ranging noises.
AB - Network location is one of the critical issues and a challenge in wireless sensor and ad hoc networks, in particular when networks are sparse. However, even in highly sparse networks, there exist well-connected subgraphs while the distribution of the networks is random. This paper introduces weighted component stitching (WCS) to find redundantly rigid components with high redundant ratios, which can be used to generate reliable local realization. Finding and ranking the redundantly rigid components is an NP-hard problem (a reduction from maximum quasi-clique). Here, we introduce a series of theorems and algorithms to carry out WCS efficiently. More precisely, we prove that each graph has a determinant number of redundantly rigid components, each redundantly rigid component is covered by a set of basic redundant components (BRCs), and each BRC contains one redundant edge. We apply constraints to merge the BRCs to form components with higher redundancy ratio and develop a greedy algorithm to merge BRCs to form locally mostly redundant components (LMRCs). Finally, we give the approximation ratio. The local coordinates of nodes are calculated by optimization in each LMRC and are synchronized with weights to produce the global coordinates of nodes in the network to overcome the sparseness of subgraphs. Extensive experiments demonstrate significant improvements in accuracy (45%-64%) using our WCS method over the state-of-the-art algorithms under various settings of network sparseness and ranging noises.
KW - Network localization
KW - component stitching
KW - graph realization
KW - redundantly rigid
KW - sparse network
UR - http://www.scopus.com/inward/record.url?scp=85053335133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85053335133&partnerID=8YFLogxK
U2 - 10.1109/TNET.2018.2866597
DO - 10.1109/TNET.2018.2866597
M3 - Article
AN - SCOPUS:85053335133
SN - 1063-6692
VL - 26
SP - 2242
EP - 2253
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 5
M1 - 8464088
ER -