International Journal of Wireless and Microwave Technologies (IJWMT)
IJWMT Vol. 1, No. 3, 15 Jun. 2011
Cover page and Table of Contents: PDF (size: 187KB)
Polynomial Algorithm for Node Deployment in Hybrid Wireless Sensor Networks
Full Text (PDF, 187KB), PP.6-13
Views: 0 Downloads: 0
Author(s)
Lili Zhang
1,2,*
Jing Yuan
1
Yingchi Mao
2
Xiwei Zhang
1,2
Guihai Chen
1
Index Terms
Hybrid wireless sensor networks, node deployment, reaction delay
Abstract
When detecting a target or monitoring a physical phenomenon in a region, the deployment problem is fundamental in these applications. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. It is well known that the mobility of sensor nodes can improve the coverage and the probability of the detecting, so we deal with the problem of detecting a target using hybrid sensor networks which contain both stationary sensors and mobile sensors. In this paper, to begin with, we prove that the node deployment problem is NP-complete. Then, one polynomial algorithm for node deployment in hybrid wireless sensor networks is proposed, which aims at minimizing the number of all sensors to reduce the cost. The simulations verify the efficiency of our algorithm.
Cite This Paper
Lili Zhang,Jing Yuan,Yingchi Mao,Xiwei Zhang,Guihai Chen,"Polynomial Algorithm for Node Deployment in Hybrid Wireless Sensor Networks", IJWMT, vol.1, no.3, pp.6-13, 2011. DOI: 10.5815/ijwmt.2011.03.02
Reference
[1] S. S. Dhillon, K. Chakrabarty, and S. S. Iyengar, “Sensor placement for grid coverage under imprecise detections,” Proc. of the 15th Intel. Conference on Information Fusion, vol. 2, pp. 1581-1587, July 2002.
[2] S. S. Dhillon and K. Chakrabarty, “Sensor placement for effective coverage and surveillance in distributed sensor networks,” Proc. of IEEE WCNC, vol. 3, pp. 1609-1614, 2003.
[3] K. Chakrabarty, S. S. Iyengar, and H. Qi, “Grid coverage for surveillance and target location in distributed sensor networks,” IEEE Trans. Computers, vol. 51, pp. 1448-1453.
[4] X. Bai, D. Xuan, Z. Yun, T.H. Lai, and W. Jia, “Complete optimal deployment patterns for full-coverage and k-connectivity(k≤6)wireless sensor networks” , In ACM Mobihoc, pp. 401-410, 2008.
[5] T.-L. Chin, P. Pamanathan, and K. K. Saluja, “Analytic modeling of detection latency in mobile sensor networks,” In ACM IPSN, 2006.
[6] B. Liu, P. Brass, O. Dousse, P. Nain, and D. Towsley, “Mobility improve coverage of sensor networks,” In ACM MobiHoc, 2005.
[7] N. Bisnik, A. Abouzeid, and V. Isler, “Stochastic event capture using mobile sensors subject to a quality metric,” In ACM MobiCom, 2006.
[8] G. Xing, J. Wang, K. Shen, Q. Huang, X. Jia and H. C. So, “Mobility-assisted spatiotemporal detection in wireless sensor networks,” In IEEE ICDCS, 2008.
[9] S. Gandhi, S. Suri, and E. Welzl, “Catching elephants with mice: Sparse sampling for monitoring sensor networks,” In ACM SenSys, 2007.
[10] M. R. Garey, R. L. Graham, and D. S. Johnson, “The complexity of computing Steiner minimal trees,” SIAM J. Applied Math., 32(4): 835-859, 1977.
[11] J. B. Kruskal, “ On the shortest spanning subtree of a graph and the traveling salesman problem,” In Proc. of American Mathmatics Society, 7(1): 48-50, 1956.
[12] R. C. Prim, “Shortest connection networks and some generalization,” Bell System Technical Journal, 36: 1389-1401, 1957.
[13] H. Brönnimann and M. T. Goodrich, “Almost optimal set covers in finite VC-dimension,” In Proc. of the 10th Computational Geometry, pp. 293-302, 1994.
[14] C. Liao and S. Hu, “Polynomial time approximation schemes for minimum disk cover problems,” J. Comb. Optim, published online, February 28, 2009.
[15] G. Calinescu, I. I. Mandoiu, P.-J. Wan, and A. Z. Zelikovsky, “Selecting forwarding neighbors in wireless ad hoc networks,” ACM Mob. Netw. Appl. 9: 101-111, 2004.
[16] C.-S. Li, F. F. Tong, C. J. Georgiou, and M. Chen, “Grain equalization in metropolitan and wide area optical networks using optical amplifiers,” In Proc. IEEE INFOCOM, pp. 130-137, 1994.
[17] B. Bamamurthy, J. Iness, and B. Mukherjee, “ Minimizing the number optical amplifer needed to support a multi-wavelength optical LAN/MAN,” In Proc. IEEE INFOCOM, pp. 261-268, 1997.
[18] G. Lin and G. Xue, “Steiner tree problem with minimum number of Steiner points and bounded edge-length,” Information Processing Letters, 69: 53-57, 1999.
[19] D. Chen, D. Z. Du, X. D. Hu, L. Wang, and G. Xue, “Approximations for Steiner trees with minimum number of Steiner points,” Journal of Global Optimization, 18: 17-33, 2000.