Focused-coverage by mobile sensor networks

We pinpoint a new sensor self-deployment problem, constructing focused coverage around a point of interest (POI), and introduce an evaluation metric, coverage radius. We propose two solutions, greedy advance (GA) and greedy-rotation-greedy (GRG), which are to our knowledge the first sensor self-deployment algorithms that operate in a purely localized manner and yet provide coverage guarantee. The two algorithms drive sensors to move along a locally-computed equilateral triangle tessellation (TT) to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI to a TT vertex where greedy advance can resume. They both yield a connected network of TT layout with hole-free coverage; GRG furthermore assures a hexagon coverage shape centered at POI. We prove their correctness and analyze their coverage radius property. Our study shows that GRG guarantees optimal hexagonal coverage radius and near optimal circular coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.