Knapsack-Based Sensor Selection for Target Localization Under Energy and Error Constraints

The sensor selection problem is formulated as a multiobjective optimization problem in which the cost function incorporates required and resulting localization errors in addition to the transmission energy consumed by the network. It is required that the total transmission energy of the selected sensors not to exceed a certain ratio of the total network energy. The difficulty in addressing this problem arises from the nonlinearity, nonconvexity and submodularity of the localization error in relation to the set of selected sensors. Thus, even for the same sensor, its effect on the localization error depends on how early/late it is to be selected as well as the set of previously activated sensors. To solve this problem, we first propose approximating the relative error effect of sensor selection as a function of its distance to the target. Using this approximation, sensor selection is then reformulated as a linear knapsack problem that can be easily solved. Additionally, an iterative refinement of the resulting solution is proposed in which the knapsack solution is reordered to account for submodularity. Two selection algorithms are proposed; KP-Based and naive greedy. In the KP-Based, widely available solvers can be used to generate the knapsack solution. Alternatively, in the naive algorithm, the solution is generated in a sequential greedy fashion. Finally, the performance of the proposed algorithms is examined to show their effectiveness.