Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks

详细信息    查看全文

• 作者：Dinesh Dash (1)
  Arijit Bishnu (2)
  Arobinda Gupta (1)
  Subhas C. Nandy (2)
  
• 关键词：Sensor ; Coverage ; Approximation algorithm
• 刊名：Wireless Networks
• 出版年：2013
• 出版时间：July 2013
• 年：2013
• 卷：19
• 期：5
• 页码：857-870
• 全文大小：642KB
• 参考文献：1. Agnetis, A., Grande, E., Mirchandani, P. B., & Pacifici, A. (2009). Covering a line segment with variable radius discs. / ACM Computers & Operations Research, 36(5), 1423-436. class="external" href="http://dx.doi.org/10.1016/j.cor.2008.02.013">CrossRef
  2. Bai, X., Kumar, S., Xuan, D., Yun, Z., & Lai, T. H. (2006). Deploying wireless sensors to achieve both coverage and connectivity. In / ACM international symposium on mobile ad hoc networking and computing (pp. 131-42). Florence, Italy.
  3. Balister, P., Zheng, Z., Kumar, S., & Sinha, P. (2009). Trap coverage: Allowing coverage holes of bounded dimeter in wireless sensor network. In / IEEE INFOCOM.
  4. Baumgartner, K., & Ferrari, S. (2008). A geometric transversal approach to analyzing track coverage in sensor networks. / IEEE Transactions on Computers, 57(8), 1113-128. class="external" href="http://dx.doi.org/10.1109/TC.2008.56">CrossRef
  5. Carmi, P., Katz, M., & Lev-Tov, N. (2007). Covering points by unit disks of fixed location. In / International Symposium on Algorithms and Computation. (pp. 644-55).
  6. Carmi, P., Katz, M. J., & Lev-Tov, N. (2008). Polynomial time approximation schemes for piercing and covering with applications in wireless networks. / Computational Geometry: Theory and Applications, 39(3), 209-18. class="external" href="http://dx.doi.org/10.1016/j.comgeo.2007.01.001">CrossRef
  7. Chakrabarty, K., Iyengar, S. S., Qi, H., & Cho, E. (2002). Grid coverage for surveillance and target location in distributed sensor networks. / IEEE Transactions on Computers, 51(12), 1448-453. class="external" href="http://dx.doi.org/10.1109/TC.2002.1146711">CrossRef
  8. Chan, T. M. (2003). Polynomial-time approximation schemes for packing and piercing fat objects. / Journal of Algorithms, 46(2), 178-89. class="external" href="http://dx.doi.org/10.1016/S0196-6774(02)00294-8">CrossRef
  9. Chan, T. M., & Mahmood, A.-A. (2005). Approximating the piercing number for unit-height rectangles. In / CCCG (pp. 15-8). Windsor, Ontario.
  10. Claude, F., Das, G. K., Dorrigiv, R., Durocher, S., Fraser, R., Lopez-Ortiz, A., Nickerson, B. G., & Salinger, A. (2010). An improved line-separable algorithm for discrete unit disk cover. / Discrete Mathematics, Algorithms, and Applications, 2(1), 1-1. class="external" href="http://dx.doi.org/10.1142/S1793830910000486">CrossRef
  11. Clouqueur, T., Phipatanasuphorn, V., Ramanathan, P., & Saluja, K. K. (2002). Sensor deployment strategy for target detection. In / WSNA (pp. 42-8). Atlanta, GA.
  12. Dash, D., Bishnu, A., Gupta, A., & Nandy, S.C. (2010). Approximation algorithm for line segment coverage for wireless sensor network. CoRR, abs/1006.2955.
  13. de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O. (2000). / Computational geometry: Algorithms and applications, second edition. Berlin: Springer.
  14. Fowler, R. J., Paterson, M. S., & Tanimoto, S. L. (1981). Optimal packing and covering in the plane are np-complete. / Information Processing Letters, 12(3), 133-37. class="external" href="http://dx.doi.org/10.1016/0020-0190(81)90111-3">CrossRef
  15. Galota, M., Reith, C. G. S., & Vollmer, H. (2001). A polynomial-time approximation scheme for base station positioning in UMTS networks. In / International workshop on discrete algorithms and methods for mobile computing and communications (pp. 52-0).
  16. Gonzalez T. F. (1991). Covering a set of points in multidimensional space. / Information Processing Letters, 40, 181-88. class="external" href="http://dx.doi.org/10.1016/0020-0190(91)90075-S">CrossRef
  17. Liu, H., Wan, P., & Jia, X. (2006). Maximal lifetime scheduling for k to 1 sensor–target surveillance networks. / Computer Networks, 50(15), 2839-854.
  18. Harada, J., Shioda, S., & Saito, H. (2009). Path coverage properties of randomly deployed sensors with finite data-transmission ranges. / Computer Networks, 53(7), 1014-026. class="external" href="http://dx.doi.org/10.1016/j.comnet.2008.12.003">CrossRef
  19. Hochbaum, D., & Maass, W. (1985). Approximation schemes for covering and packing problems in image processing and vlsi. / Journal ACM, 32(1), 130-36. class="external" href="http://dx.doi.org/10.1145/2455.214106">CrossRef
  20. Huang, C., & Tseng, Y. (2005). The coverage problem in wireless sensor network. / Mobile Network and Applications, 10(4), 519-28. class="external" href="http://dx.doi.org/10.1007/s11036-005-1564-y">CrossRef
  21. Kim, J.-E., Yoon, M.-K., Han, J., & Lee, C.-G. (2008). Sensor placement for 3-coverage with minimum separation requirements. In / Proceedings of the 4th IEEE international conference on distributed computing in sensor systems, DCOSS -8 (pp. 266-81). Berlin, Heidelberg: Springer.
  22. Kumar, S., Lai, T. H., & Arora, A. (2005). Barrier coverage with wireless sensors. In / ACM MOBICOM (pp. 284-98). Cologne, Germany.
  23. Megerian, S., Koushanfar, F., Potkonjak, M., & Srivastava, M. B. (2005). Worst and best-case coverage in sensor networks. / IEEE Transactions on Mobile Computing, 4(1), 753-63. class="external" href="http://dx.doi.org/10.1109/TMC.2005.15">CrossRef
  24. Ram, S. S., Manjunath, D., Iyer, S. K., & Yogeshwaran, D. (2007). On the path coverage properties of random sensor networks. / IEEE Transactions on Mobile Computing, 6(5), 446-58. class="external" href="http://dx.doi.org/10.1109/TMC.2007.1000">CrossRef
  25. Thai, M. T., Wang, F., & Du, D. (2008). Coverage problems in wireless sensor networks: Designs and analysis. / ACM Journal of Sensor Network, 3(3), 191-00. class="external" href="http://dx.doi.org/10.1504/IJSNET.2008.018482">CrossRef
  26. Wu, C., Lee, K. C., & Chung, Y. (2007). A delaunay triangulation based method for wireless sensor network deployment. / ACM Computer Communications, 30(14-5), 2744-752. class="external" href="http://dx.doi.org/10.1016/j.comcom.2007.05.017">CrossRef
  27. Xing, G., Wang, X., Zhang, Y., Lu, C., Pless, R., & Gill, C. (2005). Integrated coverage and connectivity configuration for energy conservation in sensor networks. / ACM Transactions on Sensor Networks, 1(1), 36-2. class="external" href="http://dx.doi.org/10.1145/1077391.1077394">CrossRef
  28. Xu, X., & Sahni, S. (2007). Approximation algorithms for sensor deployment. / IEEE Transactions on Computers, 56(12), 1681-695.
  29. Yick, J., Bharathidasan, A., Pasternack, G., Mukherjee, B., Ghosal, D. (2004). Optimizing placement of beacons and data loggers in a sensor network—a case study. In / Wireless communications and networking conference (pp. 2486-491) March 2004.
  30. Zhang, Z., & Du, D.-Z. (2011). Radar placement along banks of river. / Journal of Global Optimization (pp. 1-3). doi:class="a-plus-plus non-url-ref">10.1007/s10898-011-9704-3 .
  
• 作者单位：Dinesh Dash (1)
  Arijit Bishnu (2)
  Arobinda Gupta (1)
  Subhas C. Nandy (2)
  
  1. Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India
  2. Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India
  
• ISSN：1572-8196

文摘

The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment ?is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R. We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (polynomial time approximation scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the lengths of the line segments are bounded within a constant factor of the sensing radius of each sensor. Finally, we propose a constant factor approximation algorithm for k-covering axis-parallel line segments such that sensors maintain a minimum separation among them.