A grid-based coverage approach for target tracking in hybrid sensor networks

Most existing work on the coverage problem of wireless sensor networks focuses on improving the coverage of the whole sensing field. In target tracking, the interested coverage area is the emerging region of a motorized target, not the whole sensing field. As the motorized target moves, the emerging region is also dynamically changed. In this paper, we propose a grid-based and distributed approach for providing large coverage for a motorized target in a hybrid sensor network. The large coverage is achieved by moving mobile sensor nodes in the network. To minimize total movement cost, the proposed approach needs to solve the following problems: the minimum number of mobile sensor nodes used for healing coverage holes and the best matching between mobile sensor nodes and coverage holes. In the proposed approach, the above two problems are first transformed into the modified circle covering and minimum cost flow problems, respectively. Then, two polynomial-time algorithms are presented to efficiently solve these two modified graph problems, respectively. Finally, we perform simulation experiments to show the effectiveness of proposed approach in providing the coverage for a motorized target in a hybrid sensor network.

► The proposed approach needs to solve the following two problems: the minimum number of mobile sensor nodes used for healing coverage holes and the best matching between mobile sensor nodes and coverage holes.
► In the proposed approach, the two concerned problems are transformed into the modified circle covering and minimum cost flow problems, respectively.
► We have also performed simulation experiments to examine the effectiveness of the proposed approach by comparing with a pseudo-ideal approach.