Upper and lower bounds for dynamic cluster assignment for multi-target tracking in heterogeneous WSNs

• Modeling a cluster-based target tracking problem in WSNs as an Integer Linear Programming model.
• Lagrangian relaxation upper bound shows a better bound than pure LP relaxation.
• LP relaxation with Randomized Rounding provides a good lower bound.
• Results of heuristic clustering methods remain between the upper and lower bounds.
• Dynamic clustering methods are better than hybrid ones in small numbers of targets.

In this paper, we consider the problem of cluster task assignment to maximize total utilities of nodes for target coverage in heterogeneous Wireless Sensor Networks. We define this problem as assigning the tasks of Cluster Head (CH) and Cluster Members (CM) to nodes for each target and requiring communication connectivity between every CH with its members. The utility of each node for each target is defined as a function of its distance to the target and its remaining energy. We propose an upper bound based on Lagrangian Relaxation (LR) and a lower bound by Linear Programming (LP) relaxation with a combination of Randomized Rounding (RR) and a greedy-based heuristic. Furthermore, we propose a distributed heuristic algorithm based on matching and a general assignment problem. Dynamic movements of targets are taken into account by intra/inter-cluster task reassignments. Simulation results, compared with optimal values, reveal that the LR upper bound performs better than the bound reached by pure LP relaxation. The lower bound obtained by LP relaxation combined with the RR technique provides close results in comparison with the distributed heuristic algorithm. Furthermore, the results of the distributed heuristic algorithm remain between the upper and lower bounds and close to optimal values.