| In mobile sensor networks, node mobility can be wisely used to improve coverage. There are two approaches, sensor self-deployment and sensor relocation, which aim respectively at achieving maximized hole-free coverage from a randomized node dropping and at maintaining constant coverage in face of node failure. In this thesis, we study in depth existing sensor self-deployment algorithms and sensor relocation protocols. We pinpoint a new problem of focused coverage formation around a Point of Interest (POI) and formalize an emerging distance-sensitive service discovery problem.;For the first problem, we devise two solutions, GA and GRG, which are the first localized sensor self-deployment algorithms that provide coverage guarantee. They drive sensors to move along a triangle tessellation to surround the POI. In GA, sensors greedily proceed as close to the POI as they can; in GRG, when their greedy advance is blocked, they rotate around the POI to a vertex where greedy advance can resume. For the second problem, we devise a localized solution iMesh, where service providers construct a novel planar structure, information mesh, with good proximity property; service consumers conduct a lookup process restricted within their home mesh cells to discover nearby services.;Last but not least, we also develop two localized sensor relocation protocols, ZONER and MSRP, both of which have significant advantages over previous similar algorithms. |
