Deploying Wireless Sensor Networks under Limited Mobility Constraints
Authors:
- Bin MaBMBin Ma
- Kaizhong ZhangKZKaizhong Zhang
- 27 August 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 6 (10) , 1142-1157
Abstract
In this paper, we study the issue of sensor network 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 a 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.Keywords
This publication has 26 references indexed in Scilit:
- Deploying Wireless Sensor Networks under Limited Mobility ConstraintsIEEE Transactions on Mobile Computing, 2007
- Movement-assisted sensor deploymentIEEE Transactions on Mobile Computing, 2006
- Sensor networks deployment using flip-based sensors2005
- Robomote: enabling mobility in sensor networks2005
- XYZ: a motion-enabled, power aware sensor node platform for distributed sensor network applications2005
- Uncertainty-aware sensor deployment algorithms for surveillance applications2004
- Event-based motion control for mobile-sensor networksIEEE Pervasive Computing, 2003
- Sensor deployment and target localization based on virtual forces2003
- Geography-informed energy conservation for Ad Hoc routing2001
- An Efficient Implementation of a Scaling Minimum-Cost Flow AlgorithmJournal of Algorithms, 1997