Abstract: We study improvement of the sensor network coverage using mobile sensors. A movement-assisted sensor deployment algorithm for maximizing the network coverage is proposed. First, the whole deployment area is divided into many small regions called grids, and the initial deployment network is represented as a bipartite graph G in which the vertex set of G can be partitioned into two sets: the set of mobile sensors and the set of grids needed to be covered. If one mobile node can cover another grid, then there is one edge between them. The cost of the movement can be measured by the movement distance, the energy consumed by the movement, or the number of flips by the node. Then, a matching of maximum cardinality of G corresponds to an optimal movement plan which maximizes the network coverage subject to minimizing the movement costs.

Key words: sensor networks, movement-assisted deployment, bipartite, matching of maximum cardinality