More Web Proxy on the site http://driver.im/

research-article

On Node Localizability Identification in Barycentric Linear Localization

Authors:

Wenping ChenAuthors Info & Claims

ACM Transactions on Sensor Networks, Volume 19, Issue 1

Article No.: 19, Pages 1 - 26

https://doi.org/10.1145/3547143

Published: 08 December 2022 Publication History

Abstract

Determining whether nodes can be uniquely localized, called localizability detection, is a concomitant problem in network localization. Localizability detection under the traditional Non-Linear Localization (NLL) schema has been well explored, whereas localizability under the emerging Barycentric coordinate-based Linear Localization (BLL) schema has not been well investigated. Non-awareness of the node localizability in BLL may cause theoretically localizable nodes to converge to wrong locations because their locations are impacted by the wrong locations of the unlocalizable nodes through the iterative location propagation. In this article, the deficiency of existing localizability theories and algorithms in BLL is firstly investigated and then a necessary condition and a sufficient condition for BLL node localizability detection are proposed. Based on these two conditions, an efficient Iterative Maximum Flow (IMF) algorithm is designed to identify BLL localizable nodes, and only localizable nodes are selected to enable a Localizability Aware Barycentric Linear Localization (LABLL) algorithm, which can guarantee the locations of the localizable nodes converging correctly. The proposed IMF and LABLL algorithms are validated by both theoretical analysis and experimental evaluations.

References

[1]

Apple. 2022. Ultra Wideband is Available on iPhone 11 and Later Models. Website. (2022). https://support.apple.com/en-sg/guide/iphone/iph771fd0aad/ios.

[2]

Stefania Bartoletti, Andrea Conti, Davide Dardari, and Andrea Giorgetti. 2018. 5G localization and context-awareness. University of Bologna, University of Ferrara (2018).

[3]

Soumya J. Bhat and Santhosh K. Venkata. 2020. An optimization based localization with area minimization for heterogeneous wireless sensor networks in anisotropic fields. Computer Networks 179 (2020), 107371.

[4]

Fine Ranging (FiRa) Consortium. 2022. Localization Cases Based on Distance Measurement Using UWB Technology. Website. (2022). https://www.firaconsortium.org/discover/use-cases.

[5]

Pablo Corbalán and Gian Pietro Picco. 2020. Ultra-wideband concurrent ranging. ACM Transactions on Sensor Networks (TOSN) 16, 4 (2020), 1–41.

Digital Library

[6]

Yingfei Diao, Zhiyun Lin, and Minyue Fu. 2014. A barycentric coordinate based distributed localization algorithm for sensor networks. IEEE Transactions on Signal Processing 62, 18 (2014), 4760–4771.

[7]

Tolga Eren. 2016. Graph invariants for unique localizability in cooperative localization of wireless sensor networks: Rigidity index and redundancy index. Ad Hoc Networks 44 (2016), 32–45.

Digital Library

[8]

Tolga Eren, O. K. Goldenberg, Walter Whiteley, Yang Richard Yang, A. Stephen Morse, Brian D. O. Anderson, and Peter N. Belhumeur. 2004. Rigidity, computation, and randomization in network localization. In Proceedings of the 2004 IEEE INFOCOM, Vol. 4. IEEE, 2673–2684.

[9]

Xu Fang, Xiaolei Li, and Lihua Xie. 2020. 3-D distributed localization with mixed local relative measurements. IEEE Transactions on Signal Processing 68 (2020), 5869–5881.

[10]

Infsoft GmbH. 2021. Indoor Positioning with UWB. Website. (2021). https://www.ultrawideband.io/en/technology.php.

[11]

Andrew V. Goldberg and Robert E. Tarjan. 2014. Efficient maximum flow algorithms. Commun. ACM 57, 8 (2014), 82–89.

Digital Library

[12]

David Kiyoshi Goldenberg, Arvind Krishnamurthy, Wesley C. Maness, Yang Richard Yang, Anthony Young, A. Stephen Morse, and Andreas Savvides. 2005. Network localization in partially localizable networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1. IEEE, 313–326.

[13]

Kexin Guo, Xiuxian Li, and Lihua Xie. 2020. Simultaneous cooperative relative localization and distributed formation control for multiple UAVs. Science China Information Sciences 63, 1 (2020), 1–3.

[14]

Kexin Guo, Xiuxian Li, and Lihua Xie. 2020. Ultra-wideband and odometry-based cooperative relative localization with application to multi-UAV formation control. IEEE Transactions on Cybernetics 50, 6 (2020), 2590–2603.

[15]

Zhongwen Guo, Ying Guo, Feng Hong, Zongke Jin, Yuan He, Yuan Feng, and Yunhao Liu. 2010. Perpendicular intersection: Locating wireless sensors with mobile beacon. IEEE Transactions on Vehicular Technology 59 (2010), 3501–3509.

[16]

Trevor Halsted, Ola Shorinwa, Javier Yu, and Mac Schwager. 2021. A survey of distributed optimization methods for multi-robot systems. arXiv preprint arXiv:2103.12840.

[17]

Tingrui Han, Zhiyun Lin, Ronghao Zheng, Zhimin Han, and Haitao Zhang. 2017. A barycentric coordinate based approach to three-dimensional distributed localization for wireless sensor networks. In 2017 13th IEEE International Conference on Control & Automation (ICCA). IEEE, 600–605.

[18]

Bruce Hendrickson. 1992. Conditions for unique graph realizations. SIAM Journal on Computing 21, 1 (1992), 65–84.

Digital Library

[19]

John E. Hopcroft and Robert Endre Tarjan. 1973. Dividing a graph into triconnected components. SIAM J. Comput. 2, 3 (1973), 135–158.

Digital Library

[20]

Bill Jackson and Tibor Jordán. 2005. Connected rigidity matroids and unique realizations of graphs. Journal of Combinatorial Theory, Series B 94, 1 (2005), 1–29.

Digital Library

[21]

Donald J. Jacobs and Bruce Hendrickson. 1997. An algorithm for two-dimensional rigidity percolation: The pebble game. J. Comput. Phys. 137, 2 (1997), 346–365.

Digital Library

[22]

Senshan Ji, Kam-Fung Sze, Zirui Zhou, Anthony Man-Cho So, and Yinyu Ye. 2013. Beyond convex relaxation: A polynomial-time non-convex optimization approach to network localization. In Proceedings of 2013 IEEE INFOCOM. IEEE, 2499–2507.

[23]

Fasih Ullah Khan, Adnan Noor Mian, and Muhammad Tahir Mushtaq. 2022. Experimental testbed evaluation of cell level indoor localization algorithm using Wi-Fi and LoRa protocols. Ad Hoc Networks 125 (2022), 102732.

Digital Library

[24]

Usman A. Khan, Soummya Kar, and José M. F. Moura. 2009. Distributed sensor localization in random environments using minimal number of anchor nodes. IEEE Transactions on Signal Processing 57, 5 (2009), 2000–2016.

Digital Library

[25]

Usman A. Khan, Soummya Kar, and José M. F. Moura. 2015. Linear theory for self-localization: Convexity, barycentric coordinates, and Cayley–Menger determinants. IEEE Access 3 (2015), 1326–1339.

[26]

Usman A. Khan, Soummya Kar, Bruno Sinopoli, and José M. F. Moura. 2008. Distributed sensor localization in euclidean spaces: Dynamic environments. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing. 361–366.

[27]

Rainer Kümmerle, Giorgio Grisetti, Hauke Strasdat, Kurt Konolige, and Wolfram Burgard. 2011. g2o: A general framework for graph optimization. In Proceedings of 2011 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 3607–3613.

[28]

Gerard Laman. 1970. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics 4, 4 (1970), 331–340.

[29]

Danyang Li, Jingao Xu, Zheng Yang, Chenshu Wu, Jianbo Li, and Nicholas D. Lane. 2021. Wireless localization with spatial-temporal robust fingerprints. ACM Transactions on Sensor Networks (TOSN) 18, 1 (2021), 1–23.

Digital Library

[30]

Yanjun Lin, Zhiyun Lin, and Zhiyong Sun. 2021. Distributed event-triggered approach for multi-agent formation based on cooperative localization with mixed measurements. Electronics 10, 18 (2021), 2265.

[31]

Zhiyun Lin, Tingrui Han, Ronghao Zheng, and Changbin Yu. 2017. Distributed localization with mixed measurements under switching topologies. Automatica 76 (2017), 251–257.

[32]

Zhiyun Lin, Zhimin Han, and Ming Cao. 2020. Distributed localization for multi-robot systems in presence of unlocalizable robots. In 59th IEEE Conference on Decision and Control (CDC). 1550–1555.

Digital Library

[33]

Jun Liu, Jiayao Gao, Sanjay Jha, and Wen Hu. 2021. Seirios: Leveraging multiple channels for LoRaWAN indoor and outdoor localization. In Proceedings of the 27th Annual International Conference on Mobile Computing and Networking. 656–669.

Digital Library

[34]

Qiang Liu, XiuJun Bai, Xingli Gan, and Shan Yang. 2022. Lora RTT ranging characterization and indoor positioning system. Wireless Communications and Mobile Computing (2022).

[35]

Chengqi Ma, Bang Wu, Stefan Poslad, and David R. Selviah. 2020. Wi-Fi RTT ranging performance characterization and positioning system design. IEEE Transactions on Mobile Computing1 (2020), 1–1.

[36]

Israel Martin-Escalona and Enrica Zola. 2020. Ranging estimation error in WiFi devices running IEEE 802.11mc. In 2020 IEEE Global Communications Conference. 1–7.

[37]

Gary L. Milkri. 1988. A new graph triconnectivity algorithm and its parallelization. (1988).

[38]

Lufeng Mo, Yuan He, Yunhao Liu, Jizhong Zhao, Shaojie Tang, Xiang-Yang Li, and Guojun Dai. 2009. Canopy closure estimates with GreenOrbs: Sustainable sensing in the forest. Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, 99–112.

Digital Library

[39]

Thien-Minh Nguyen, Zhirong Qiu, Thien Hoang Nguyen, Muqing Cao, and Lihua Xie. 2020. Persistently excited adaptive relative localization and time-varying formation of robot swarms. IEEE Transactions on Robotics 36, 2 (2020), 553–560.

[40]

James B. Orlin. 2013. Max flows in o (nm) time, or better. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 765–774.

Digital Library

[41]

Haodi Ping, Yongcai Wang, and Deying Li. 2020. HGO: Hierarchical graph optimization for accurate, efficient, and robust network localization. In Proceedings of the 29th International Conference on Computer Communications and Networks (ICCCN). 1–9.

[42]

Haodi Ping, Yongcai Wang, and Deying Li. 2021. DCG: Distributed conjugate gradient for efficient linear equations solving. arXiv preprint arXiv: 2107.13814.

[43]

Haodi Ping, Yongcai Wang, Deying Li, and Tianyuan Sun. 2020. Flipping free conditions and their application in sparse network localization. IEEE Transactions on Mobile Computing (2020), 1–1.

[44]

Haodi Ping, Zhangbing Zhou, Zhensheng Shi, and Taj Rahman. 2018. Accurate and energy-efficient boundary detection of continuous objects in duty-cycled wireless sensor networks. Personal and Ubiquitous Computing 22, 3 (2018), 597–613.

Digital Library

[45]

Kun Qian, Xinyu Zhang, Zheng Yang, and Yunhao Liu. 2020. AoD-based localization with cots millimeter-wave devices. SCIENTIA SINICA Informationis 51, 1 (2020), 122.

[46]

August Ferdinand Möbius. 1827. Der Barycentrische Calcul. Leipzig.

[47]

Sam Safavi, Usman A. Khan, Soummya Kar, and José M. F. Moura. 2018. Distributed localization: A linear theory. Proc. IEEE 106, 7 (2018), 1204–1223.

[48]

Yannic Schröder and Lars Wolf. 2022. InPhase: Phase-based ranging and localization. ACM Transactions on Sensor Networks (TOSN) 18, 2 (2022), 1–39.

Digital Library

[49]

Yi Shang and Wheeler Ruml. 2004. Improved MDS-based localization. In Proceedings of the 2004 IEEE INFOCOM, Vol. 4. IEEE, 2640–2651.

[50]

Xingfa Shen, Chuang Li, Weijie Chen, Yongcai Wang, and Quanbo Ge. 2022. Transition model-driven unsupervised localization framework based on crowd-sensed trajectory data. ACM Transactions on Sensor Networks (TOSN) 18, 2 (2022), 1–21.

Digital Library

[51]

Anthony Man-Cho So and Yinyu Ye. 2007. Theory of semidefinite programming for sensor network localization. Mathematical Programming 109, 2–3 (2007), 367–384.

Digital Library

[52]

Tianyuan Sun, Yongcai Wang, Deying Li, Zhaoquan Gu, and Jia Xu. 2018. WCS: Weighted component stitching for sparse network localization. IEEE/ACM Transactions on Networking 26, 5 (2018), 2242–2253.

Digital Library

[53]

Pedro P. V. Tecchio, Nikolay Atanasov, Shahin Shahrampour, and George J. Pappas. 2019. N-dimensional distributed network localization with noisy range measurements and arbitrary anchor placement. In Proceedings of 2019 American Control Conference (ACC). 1195–1201.

[54]

Tsingoal. 2022. Precise Locating Core Algorithm. Website. (2022). http://www.tsingoal.com/index.php?lang=en.

[55]

Tsingoal. 2022. Social Distancing and Contact Tracing to Anti COVID-19. Website. (2022). https://www.social-distancing-contact-tracing.com/.

[56]

Yongcai Wang, Tianyuan Sun, Guoyao Rao, and Deying Li. 2018. Formation tracking in sparse airborne networks. IEEE Journal on Selected Areas in Communications 36, 9 (2018), 2000–2014.

Digital Library

[57]

Hejun Wu, Ao Ding, Weiwei Liu, Lvzhou Li, and Zheng Yang. 2017. Triangle extension: Efficient localizability detection in wireless sensor networks. IEEE Transactions on Wireless Communications 16, 11 (2017), 7419–7431.

[58]

Na Xia, Yuanxiao Ou, Shiliang Wang, Rong Zheng, Huazheng Du, and Chaonong Xu. 2016. Localizability judgment in UWSNs based on skeleton and rigidity theory. IEEE Transactions on Mobile Computing 16, 4 (2016), 980–989.

Digital Library

[59]

Zheng Yang and Yunhao Liu. 2011. Understanding node localizability of wireless Ad hoc and sensor networks. IEEE Transactions on Mobile Computing 11, 8 (2011), 1249–1260.

Digital Library

[60]

Zheng Yang, Yunhao Liu, and Xiangyang Li. 2009. Beyond trilateration: On the localizability of wireless Ad-hoc networks. In Proceedings of the 2009 IEEE INFOCOM. 2392–2400.

[61]

Yuan Zhang, Shutang Liu, Xiuyang Zhao, and Zhongtian Jia. 2012. Theoretic analysis of unique localization for wireless sensor networks. Ad Hoc Networks 10, 3 (2012), 623–634.

Digital Library

[62]

Shiyu Zhao and Daniel Zelazo. 2016. Localizability and distributed protocols for bearing-based network localization in arbitrary dimensions. Automatica 69 (2016), 334–341.

Digital Library

Cited By

Ping HWang YZhang YLi DXie L(2024)Understanding Hidden Knowledge in Generic GraphsIEEE/ACM Transactions on Networking10.1109/TNET.2024.336417732:3(2631-2645)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3364177
Chen LLin ZXie L(2024)Angle-Based Distributed Node Localizability and LocalizationIEEE Transactions on Automatic Control10.1109/TAC.2023.333943769:3(1890-1897)Online publication date: Mar-2024
https://doi.org/10.1109/TAC.2023.3339437
Islam MIkram MAlhussein MAyub MKhan MAurangzeb K(2024)A Component-Based Localization Algorithm for Sparse 3-D Wireless Sensor NetworksIEEE Access10.1109/ACCESS.2024.335888912(51904-51918)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3358889
Show More Cited By

Index Terms

On Node Localizability Identification in Barycentric Linear Localization
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Sensor networks
2. Networks
  1. Network services
    1. Location based services

Recommendations

Understanding Node Localizability in Barycentric Linear Localization
The barycentric linear localization (BLL) methods provide a lightweight, distributed way to calculate locations for resource-limited IoT devices. A crucial requirement for BLL is that the nodes participating in the iterative location propagation are ...
Range-free sensor localisation with ring overlapping based on comparison of received signal strength indicator

Sensor localisation has become an essential requirement for many applications over wireless sensor networks. Radio irregularity and stringent constraints on hardware cost and battery power, however, make localisation very challenging. Range-based ...
Localization and localizability in sensor and ad-hoc networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 19, Issue 1

February 2023

565 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/3561987

Editor:
Yunhao Liu
Tsinghua University, China

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 08 December 2022

Online AM: 07 July 2022

Accepted: 01 July 2022

Revised: 13 May 2022

Received: 21 February 2022

Published in TOSN Volume 19, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Natural Science Foundation of China
Public Computing Cloud, Renmin University of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)6

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ping HWang YZhang YLi DXie L(2024)Understanding Hidden Knowledge in Generic GraphsIEEE/ACM Transactions on Networking10.1109/TNET.2024.336417732:3(2631-2645)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3364177
Chen LLin ZXie L(2024)Angle-Based Distributed Node Localizability and LocalizationIEEE Transactions on Automatic Control10.1109/TAC.2023.333943769:3(1890-1897)Online publication date: Mar-2024
https://doi.org/10.1109/TAC.2023.3339437
Islam MIkram MAlhussein MAyub MKhan MAurangzeb K(2024)A Component-Based Localization Algorithm for Sparse 3-D Wireless Sensor NetworksIEEE Access10.1109/ACCESS.2024.335888912(51904-51918)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3358889
Zhang YWei QWang YPing HLi D(2023)GPART: Partitioning Maximal Redundant Rigid and Maximal Global Rigid Components in Generic Distance GraphsACM Transactions on Sensor Networks10.1145/359466819:4(1-26)Online publication date: 9-Jun-2023
https://dl.acm.org/doi/10.1145/3594668

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents