Mobility Limited Flip-Based Sensor Networks Deployment
Authors:
- 8 January 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 18 (2) , 199-211
Abstract
An important phase of sensor networks operation is deployment of sensors in the field of interest. Critical goals during sensor networks deployment include coverage, connectivity, load balancing, etc. A class of work has recently appeared, where mobility in sensors is leveraged to meet deployment objectives. In this paper, we study deployment of sensor networks using mobile sensors. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. We call such sensors as flip-based sensors. Given an initial deployment of flip-based sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage and minimize the number of flips. We propose a minimum-cost maximum-flow-based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors due to the limitations on sensor mobilityKeywords
This publication has 21 references indexed in Scilit:
- Energy-efficient communication protocol for wireless microsensor networks2005
- Relaxation on a mesh: a formalism for generalized localization2002
- An Incremental Self-Deployment Algorithm for Mobile Sensor NetworksAutonomous Robots, 2002
- Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem2002
- Geography-informed energy conservation for Ad Hoc routing2001
- GPSR2000
- New polynomial-time cycle-canceling algorithms for minimum-cost flowsNetworks, 2000
- Routing with guaranteed delivery in ad hoc wireless networks1999
- An Efficient Implementation of a Scaling Minimum-Cost Flow AlgorithmJournal of Algorithms, 1997
- Solving minimum-cost flow problems by successive approximation1987