Trade-offs between mobility and density for coverage in wireless sensor networks

ABSTRACT

In this paper, we study the coverage problem for hybrid networks which comprise both static and mobile sensors. We consider mobile sensors with limited mobility, i.e., they can move only once over a short distance. Such mobiles are simple and cheap compared to sophisticated mobile robots. In conventional static sensor networks, for a random deployment, the sensor density should increase as O(log L + k log log L) to provide k-coverage in a network with a size of L. As an alternative, an all mobile sensor network can provide k-coverage over the field with a constant density of O(k), independent of network size L. We show that the maximum distance that any mobile sensor will have to move is O(1 over √k log ^{3 over 4} (kL)). We then propose a hybrid network structure, comprising static sensors and a small fraction of O(1 over √(k)) of mobile sensors. For this network structure, we prove that k-coverage is achievable with a constant sensor density of O(k), independent of network size L. Furthermore, for this hybrid structure, we prove that the maximum distance which any mobile sensor has to move is bounded as O(log^{3 over 4} L). We then propose a distributed relocation algorithm, where each mobile sensor only requires local information in order to optimally relocate itself and characterize the algorithm's computational complexity and message overhead. Finally, we verify our analysis via extensive numerical evaluations.

REFERENCES

• 1: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Coverage problems in wireless ad-hoc sensor network," in Proceedings of IEEE INFOCOM, 2001.
• 2: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
• 3: Honghai Zhang , Jennifer Hou, On deriving the upper bound of α-lifetime for large sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989475]
• 4: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
• 5: Peng-Jun Wan , Chih-Wei Yi, Coverage by randomly deployed wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2658-2669, June 2006 [doi>10.1109/TIT.2005.862092]
• 6: G. Wang, G. Cao, and T. L. Porta, "Movement-assisted sensor deployment," in Proceedings of IEEE INFOCOM, 2004.
• 7: Y. Zou and K. Chakrabarty, "Sensor deployment and target localization based on virtual forces," in all Proceedings of IEEE INFOCOM, 2003.
• 8: S. Chellappan, X. Bai, B. Ma, and D. Xuan, "Sensor Networks Deployment Using Flip-Based Sensors," inallProceedings of IEEE MASS, 2005.
• 9: J. T. Feddema, R. H. Byrne, J. J. Harrington, D. M. Kilman, C. L. Lewis, R. D. Robinett, B. P. V. Leeuwen, and J. G. Young, "Advanced mobile networking, sensing, and controls," Technical Report SAND2005-1661, Sandia National Laboratories, 2005.
• 10: T. Leighton and P. W. Shor, "Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms," Combinatorica, vol. 9, no. 2, pp. 161--187, 1989.
• 11: Benyuan Liu , Peter Brass , Olivier Dousse , Philippe Nain , Don Towsley, Mobility improves coverage of sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062728]
• 12: M. Zhang, X. Du, and K. Nygard, "Improving coverage performance in sensor networks by using mobile sensors," in Proceedings of IEEE MILCOM, 2005.
• 13: J. Wu and S. Yang, "SMART: A scan-based movement-assisted sensor deployment method in wireless sensor networks," in Proceedings of IEEE INFOCOM, 2005.
• 14: J. Luo and J. P. Hubaux, "Joint mobility and routing for lifetime elongation in wireless sensor networks," in Proceedings of IEEE INFOCOM, 2005.
• 15: Wei Wang , Vikram Srinivasan , Kee-Chaing Chua, Using mobile relays to prolong the lifetime of wireless sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080858]
• 16: Z. Maria Wang , Stefano Basagni , Emanuel Melachrinoudis , Chiara Petrioli, Exploiting Sink Mobility for Maximizing Sensor Networks Lifetime, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 9, p.287.1, January 03-06, 2005 [doi>10.1109/HICSS.2005.259]
• 17: Sriram Chellappan , Wenjun Gu , Xiaole Bai , Dong Xuan , Bin Ma , Kaizhong Zhang, Deploying Wireless Sensor Networks under Limited Mobility Constraints, IEEE Transactions on Mobile Computing, v.6 n.10, p.1142-1157, October 2007 [doi>10.1109/TMC.2007.1032]
• 18: Zvi Lotker , Alfredo Navarra, Unbalanced Points and Vertices Problem, Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops, p.96, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.137]
• 19: Z. Lotker and A. Navarra, "Managing random sensor networks by means of grid emulation," in Proceedings of Networking (LNCS 3976), 2006, pp. 856--867.
• 20: P. Hall, Introduction to the theory of coverage processes. John Wiley & Sons, Inc, 1988.
• 21: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 22: R. Williams, The Geometrical Foundation of Natural Structure: A Source Book of Design. Dover Publications, 1979.
• 23: G. Wang, G. Cao, and T. L. Porta, "Proxy-based sensor deployment for mobile sensor networks," in Proceedings of IEEE MASS, 2004.
• 24: G. Wang, G. Cao, T. L. Porta, and W. Zhang, "Sensor relocation in mobile sensor networks," in Proceedings of IEEE INFOCOM, 2005.
• 25: E. Kratzel, Lattice points. Kluwer Academic Publishers, 1989.
• 26: A. Papoulis and S. U. Pillai, Probability, Random Variables and Stochastic Processes. 4th Ed. McGraw Hill, 2002.
• 27: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 28: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 29: S. Janson, T. Luczak, and A. Rucinski, Random Graphs. John Wiley & Sons, Inc, 2000.
• 30: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 31: Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
• 32: M. Cardei, M. Thai, Y. Li, and W. Wu, "Energy-Efficient Target Coverage in Wireless Sensor Networks," in Proceedings of IEEE INFOCOM, 2005.
• 33: Ashish Goel , Sanatan Rai , Bhaskar Krishnamachari, Sharp thresholds For monotone properties in random geometric graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007441]
• 34: W. Hoeffding, "Probability inequalities for sums of bounded random variables," Journal of the American Statistical Association, vol. 58, no. 301, pp. 13--30, 1963.
• 35: Web based demo for mobile sensors, http://cnds.ece.nus.edu.sg/mobile/mobile.html.
• 36: MIT Cricket platform, http://cricket.csail.mit.edu/.
• 37: Parallax Boe-Bot, http://www.parallax.com/html pages/robotics/boebot/boebot.asp.
• 38: Video for mobile implementations, http://cnds.ece.nus.edu.sg/mobile/mobile4.mpg.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Theory

Keywords:
coverage, mobility, sensor networks