Movement-assisted sensor redeployment scheme for network lifetime increase

ABSTRACT

Sensor deployment in mobile sensor networks has received significant attention in recent years. Goals during sensor deployment include improving coverage, achieving load balance, and prolonging the network lifetime. To improve the initial deployment, one possible method is to use mobile sensors, thus allowing sensors to relocate. In this paper, we present a sensor deployment strategy in mobile sensor networks. Our goal is to improve coverage and prolong network lifetime through sensor relocation after the initial deployment. The problem in this paper is defined as Movement-assisted Sensor Positioning (MSP) for network lifetime increase problem. With the observation that the sensors closer to the sink tend to consume more energy than those farther away from the sink, we first compute the desired non-uniform sensor density in the monitored area to reduce the energy holes near the sink and to prolong network lifetime. Assuming that sensors can move only once, we then propose a centralized algorithm to relocate mobile sensors to satisfy the density requirement with minimum cost. We construct the virtual multi-flow graph and solve the sensor relocation problem using a maximum-flow minimum-cost algorithm. The improvement in network lifetime is proved both mathematically and by simulations.

References

1. I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: a survey, Computer Networks, 38(4), pp. 393--422, 2002.
2. S. Chellappan, X. Bai, B. Ma, D. Xuan, and C. Xu, Mobility limited flip-based sensor networks deployment, IEEE Transactions of Parallel and Distributed Systems, 18(2), pp. 199--211, 2007.
3. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to algorithms, MIT Press, 2001.
4. D. Culler, D. Estrin, and M. Srivastava, Overview of sensor networks, IEEE Computer, 37(8), pp. 41--49, 2004.
5. K. Dantu, M. H. Rahimi, H. Shah, S. Babel, A. Dhariwal, and G. S. Sukhatme, Robomote: enabling mobility in sensor networks, IPSN 2005, pp. 404--409, 2005.
6. J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19(2), pp. 248--264, 1972.
7. A. V. Goldberg and R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of ACM Symposium on Theory of Computing (STOC), New York, 1987.
8. A. Howard, M. J. Mataric, and G. S. Sukhatme, An incremental self deployment algorithm for mobile sensor networks, Autonomous Robots, Special Issue on Intelligent Embedded Systems, Sep. 2002.
9. U. Lee, E. O. Magistretti, B. O. Zhou, M. Gerla, P. Bellavista, and A. Corradi, Efficient data harvesting in mobile sensor platforms, PerCom Workshops, pp. 352--356, 2006.
10. S. Olariu and I. Stojmenovic, Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting, IEEE INFOCOM, 2006.
11. G. Wang, G. Cao, and T. F. LaPorta, Movement-assisted sensor deployment, IEEE Transactions on Mobile Computing, 5(6), pp. 640--652, 2006.
12. G. Wang, G. Cao, T. F. La Porta, and W. Zhang, Sensor relocation in mobile sensor networks, IEEE INFOCOM, pp. 2302--2312, 2005.
13. J. Wu and S. Yang, SMART: a scan-based movement-assisted sensor deployment method in wireless sensor networks, IEEE INFOCOM, pp. 2313--2324, 2005.
14. Y. Zou and K. Chakrabarty, Sensor deployment and target localization based on virtual forces, IEEE INFOCOM, 2003.

Index Terms

• Networks

  • Network protocols