| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Approximation Algorithms for Sensor Deployment
December 2007 (vol. 56 no. 12)
pp. 1681-1695
We develop an integer linear programming formulation to find a minimum cost deployment of sensors that provides the desired coverage of a target point set and propose a greedy heuristic for this problem. Our formulation permits heterogeneous multimodal sensors and is extended easily to account for nonuniform sensor detection resulting from blockages, noise, fading and so on. A greedy algorithm to solve the proposed general ILP is developed. Additionally ε-approximation algorithms and a polynomial time approximation scheme are proposed for the case of grid coverage. Experiments demonstrate the superiority of our proposed algorithms over earlier algorithms for point coverage of grids using heterogeneous sensors.
[1] K. Chakrabarty, S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Trans. Computers, vol. 51, no. 12, pp. 1448-1453, Dec. 2002.
[2] E.J. Cockayne, E.O. Hare, S.T. Hedetniemi, and E.V. Wimer, “Bounds for the Domination Number of Grid Graphs,” Congressus Numerantium, vol. 47, pp. 217-228, 1985.
[3] S. Commuri and M. Watfa, “Coverage Strategies for Wireless Sensor Networks,” Int'l J. Distributed Sensor Networks, vol. 2, pp.333-353, 2006.
[4] D. Culler and W. Hong, “Wireless Sensor Networks,” Comm. ACM, vol. 47, special issue, p. 6, 2004.
[5] S. Funke, A. Kesselman, F. Kuhn, and Z. Lotker, “Improved Approximation Algorithms for Connected Sensor Cover,” Proc. Third Int'l Conf. AD-HOC Networks and Wireless (ADHOC-NOW), 2004.
[6] A. Howard, M. Mataric, and G. Sukhatme, “An Incremental Self-Deployment Algorithm for Mobile Sensor Networks,” Autonomous Robots, special issue on intelligent embedded systems, 2002.
[7] A. Howard, M. Mataric, and G. Sukhatme, “Mobile Sensor Network Deployment Using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem,” Proc. Sixth Int'l Symp. Distributed Autonomous Robotics Systems (DARS '02), 2002.
[8] C. Huang and Y. Tseng, “The Coverage Problem in a Wireless Sensor Network,” Proc. Second ACM Int'l Conf. Wireless Sensor Networks and Applications (WSNA), 2003.
[9] S. Iyengar and R. Brooks, “Computing and Communications in Distributed Sensor Networks,” J. Parallel and Distributed Computing, vol. 64, special issue, p. 7, 2004.
[10] S. Iyengar and R. Brooks, Handbook of Distributed Sensor Networks. Chapman and Hall/CRC, 2005.
[11] S. Iyengar, A. Tandon, Q. Wu, E. Cho, N. Rao, and V. Vaishnavi, “Deployment of Sensors: An Overview,” Handbook of Distributed Sensor Networks, S. Iyengar and R. Brooks, eds. Chapman and Hall/CRC, 2005.
[12] K. Kar and S. Banerjee, “Node Placement for Connected Coverage in Sensor Networks,” Proc. First Workshop Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt '03), 2003.
[13] http://corpus.canterbury.ac.nzhttp://groups.yahoo.com/ grouplp_solve/, 2007.
[14] V. Mhatre, C.P. Rosenberg, R.R. Mazumdar, and N.B. Shroff, “A Minimum Cost Heterogeneous Sensor Network with a Lifetime Constraint,” IEEE Trans. Mobile Computing, vol. 4, no. 1, pp. 4-15, Jan./Feb. 2005.
[15] S. Poduri and G. Sukhatme, “Constrained Coverage for Mobile Sensor Networks,” Proc. IEEE Int'l Conf. Robotics and Automation (ICRA '04), pp. 165-171, 2004.
[16] S. Sahni and X. Xu, “Algorithms for Wireless Sensor Networks,” Int'l J. Distributed Sensor Networks, preview issue, pp. 35-56, 2004.
[17] X. Wang et al., “Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks,” Proc. First Int'l Conf. Embedded Networked Sensor Systems (SenSys '03), 2003.
[18] J. Wang and N. Zhong, “Efficient Point Coverage in Wireless Sensor Networks,” Combinatorial Optimization, vol. 11, pp. 291-304, 2006.
[19] Q. Wu, S. Iyengar, N. Rao, J. Bahren, K. Chakrabarty, V. Vaishvavi, and H. Qi, “On Efficient Deployment of Sensors on Planar Grid,” Louisiana State Univ., 2002.
[20] Q. Wu, S.S. Iyengar, S.V.N. Rao, X. Du, and V.K. Vaishnavi, “On Efficient Deployment of Sensors on Planar Grid,” Computer Comm., 2007.
[21] K. Xu et al., “Relay Node Deployment Strategies in Heterogeneous Wireless Sensor Networks: Multiple-Hop Communication Case,” Proc. Second Ann. IEEE Comm. Soc. Conf. Sensor and Ad Hoc Comm. and Networks (IEEE SECON), 2005.
[22] H. Zhang and J. Hou, “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” Technical Report UIUCDCS-R-2003-2351, Univ. of Illinois at Urbana-Champaign, 2003.
[23] Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Trans. Embedded Computing Systems, vol. 3, no. 1, pp. 61-91, 2004.
[24] Y. Zou and K. Chakrabarty, “Coverage-Oriented Sensor Deployment,” Handbook of Distributed Sensor Networks, S. Iyengar and R.Brooks, eds. Chapman and Hall/CRC, 2005.
Index Terms:
Wireless sensor networks, point coverage, multimodal sensors, approximation algorithm.
Citation:
Xiaochun Xu, Sartaj Sahni, "Approximation Algorithms for Sensor Deployment," IEEE Transactions on Computers, vol. 56, no. 12, pp. 1681-1695, June 2007, doi:10.1109/TC.2007.1063
