Strictly Localized Sensor Self-Deployment for Optimal Focused Coverage

摘要

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, {cal H}-polygon and {cal C}-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph 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 along locally computed {cal H}- or {cal C}-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.