Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.14365/1964
Title: Complexity of Energy Efficient Localization With the Aid of a Mobile Beacon
Authors: Akcan, Hüseyin
Evrendilek, Cem
Keywords: Localization
trilateration
NP-hardness
integer linear programming
Publisher: IEEE-Inst Electrical Electronics Engineers Inc
Abstract: Localization is an essential service in wireless sensor networks. Trilateration is a commonly used solution to range-based localization for providing such services. It might be, however, impossible to localize the entire network at once using trilateration due to low connectivity on sparse deployments. In such scenarios, a mobile beacon with a known position is used to move among and locate the nodes with low connectivity to aid trilateration. Given a network graph, finding a minimum energy route traveled by the mobile beacon is a key problem in many real-world applications. We prove in this letter that this problem called mobile assisted trilateration based energy optimum localization is NP-hard. To the best of our knowledge, this is the first such result in an attempt to computationally classify this important problem. We also provide a compact integer linear programming formulation for the problem.
URI: https://doi.org/10.1109/LCOMM.2017.2772876
https://hdl.handle.net/20.500.14365/1964
ISSN: 1089-7798
1558-2558
Appears in Collections:Scopus İndeksli Yayınlar Koleksiyonu / Scopus Indexed Publications Collection
WoS İndeksli Yayınlar Koleksiyonu / WoS Indexed Publications Collection

Files in This Item:
File SizeFormat 
1964.pdf
  Restricted Access
345.5 kBAdobe PDFView/Open    Request a copy
Show full item record



CORE Recommender

SCOPUSTM   
Citations

9
checked on Dec 18, 2024

WEB OF SCIENCETM
Citations

8
checked on Dec 18, 2024

Page view(s)

120
checked on Dec 16, 2024

Download(s)

2
checked on Dec 16, 2024

Google ScholarTM

Check




Altmetric


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.