Deploying Wireless Sensor Networks under Limited Mobility Constraints


In this paper, we study the issue of sensor networks deployment using limited mobility sensors. by limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions, and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the Optimal Maximum Flow based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the Simple Peak-Pit based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements and messaging overhead under different initial deployment scenarios.


Computer Science

Keywords and Phrases

Deployment; Limited Mobility Sensors; Sensor Networks

Document Type

Article - Journal

Document Version


File Type





© 2007 Institute of Electrical and Electronics Engineers (IEEE) Computer Society, All rights reserved.

Publication Date

01 Oct 2007