Sensor Placement Algorithms for a Path Covering Problem
Sivakumar Rathinam, Rajnikant Sharma · 2017
This chapter presents two new approximation algorithms with an approximation ratio of 13 and 5, respectively, to solve the landmark placement problem (LPP). Numerical simulations are performed on thousands of problem instances to corroborate the performance of the proposed algorithms. These simulations show that the proposed algorithms produce solutions with bounds that are significantly better than the guarantees indicated by the approximation factor. Simulation results were also presented to corroborate the performance of the proposed algorithms. There are several future directions for this work. First, the chapter used simplistic assumptions on the model of a range sensor; more general models where the performance of a range sensor degrades more smoothly as a function of distance from the landmark can be more useful. Second, sensors may be heterogeneous; some sensors may be based on range while the other sensors may be based on bearing. Third, sensors may be heterogeneous; some sensorsmay be based on range while the other sensors may be based on bearing.