DocumentCode :
1433904
Title :
Sensor Placement for Triangulation-Based Localization
Author :
Tekdas, Onur ; Isler, Volkan
Author_Institution :
Dept. of Comput. Sci. & Eng., Univ. of Minnesota, Minneapolis, MN, USA
Volume :
7
Issue :
3
fYear :
2010
fDate :
7/1/2010 12:00:00 AM
Firstpage :
681
Lastpage :
685
Abstract :
Robots operating in a workspace can localize themselves by querying nodes of a sensor-network deployed in the same workspace. This paper addresses the problem of computing the minimum number and placement of sensors so that the localization uncertainty at every point in the workspace is less than a given threshold. We focus on triangulation-based state estimation, where measurements from two sensors must be combined for an estimate. This problem is NP-hard in its most general from. For the general version, we present a solution framework based on integer linear programming and demonstrate its application in a fire-tower placement task. Next, we study the special case of bearing-only localization and present an approximation algorithm with a constant factor performance guarantee.
Keywords :
approximation theory; computational complexity; integer programming; linear programming; robots; sensors; NP-hard problem; approximation algorithm; bearing-only localization; constant factor performance guarantee; integer linear programming; localization uncertainty; sensor placement; triangulation-based localization; triangulation-based state estimation; Approximation algorithms; localization; sensor network deployment;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2009.2037135
Filename :
5427001
Link To Document :
بازگشت