Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

Robust Wireless Sensor Network Deployment

Milan Erdelj, Nathalie Mitton, Tahiry Razafindralambo


In this work we present a decentralized deployment algorithm for wireless mobile sensor networks. We assume that a group of mobile sensors is placed in the area of interest to be covered, without any prior knowledge of the environment. The goal of the deployment algorithm is to maximize the covered area and cope with sudden sensor failures. By relying on the locally available information regarding the environment and neighborhood, and without the need for any kind of synchronization in the network, each sensor iteratively chooses the next-step movement location so as to form a triangle lattice grid. Relying on the graph of wireless mobile sensors, we are able to provide the properties regarding the quality of coverage, the connectivity of the graph and the termination of the algorithm. We run extensive simulations to provide compactness properties of the deployment and evaluate the robustness against sensor failures. We show through the analysis and the simulations that our algorithm is robust to node failures and can restore the lattice grid. We also show that even after a failure, our algorithm call still provide a compact deployment.

Full Text: PDF