Abstract
Barrier coverage focuses on detecting intruders in an attempt to cross a specific region, in which limited-power sensors in these scenarios are supposed to be distributed remotely in an indeterminate way. In this paper, we consider a scenario where sensors with adjustable ranges and a few sink nodes are deployed to form a virtual sensor barrier for monitoring a belt-shaped region and gathering incidents data. The problem takes into account three relevant objectives: minimizing power consumption while meeting the barrier coverage requirement, minimizing the number of active sensors (reliability) and minimizing the transmission distances between active sensors and the nearest sink node (efficiency of data gathering). It is shown that these three objectives are conflicting in some degree. A Problem Specific MOEA/D with local search methods is proposed for finding optimal tradeoff solutions and compared with a classical algorithm. Experimental results indicate that knee regions exist, and these knee regions may provide the best possible tradeoff for decision makers.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Yu, Z., Teng, J., Li, X., Xuan, D.: On wireless network coverage in bounded areas. In: Proceedings of the IEEE Conference on Computer Communications, pp. 1195–1203. IEEE (2013)
Fan, H., Lee, V.C.S., Li, M., Zhang, X., Zhao, Y.: Barrier coverage using sensors with offsets. In: Cai, Z., Wang, C., Cheng, S., Wang, H., Gao, H. (eds.) WASA 2014. LNCS, vol. 8491, pp. 389–400. Springer, Heidelberg (2014)
Fan, H., LI, M., Sun, X., Wan, P.J., Zhao, Y.: Barrier coverage by sensors with adjustable ranges. ACM Transactions on Sensor Networks 11(1), 14(1)–14(20) (2014)
Konstantinidis, A., Yang, K., Zhang, Q., Zeinalipour-Yazti, D.: A multi-objective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks. Computer Networks 54(6), 960–976 (2010)
Yoon, Y., Kim, Y.H.: An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks. IEEE Transactions on Cybernetics 43(5), 1473–1483 (2013)
Zhang, Q., Li, H.: Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11(6), 712–731 (2007)
Mhatre, V.P., Rosenberg, C., Kofman, D., Mazumdar, R., Shroff, N.: A minimum cost heterogeneous sensor network with a lifetime constraint. IEEE Transactions on Mobile Computing 4(1), 4–15 (2005)
Onur, E., Ersoy, C., Deliç, H., Akarun, L.: Surveillance wireless sensor networks: deployment quality analysis. IEEE Network 21(6), 48–53 (2007)
Sun, Z., Wang, P., Vuran, M.C., Al-Rodhaan, M.A., Al-Dhelaan, A.M., Akyildiz, I.F.: Bordersense: Border patrol through advanced wireless sensor networks. Ad Hoc Networks 9(3), 468–477 (2011)
Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of Annual International Conference on Mobile Computing And Networking, pp. 284–298. ACM (2005)
Saipulla, A., Westphal, C., Liu, B., Wang, J.: Barrier coverage with line-based deployed mobile sensors. Ad Hoc Networks 11(4), 1381–1391 (2013)
He, S., Gong, X., Zhang, J., Chen, J., Sun, Y.: Curve-based deployment for barrier coverage in wireless sensor networks. IEEE Transactions on Wireless Communications 13(2), 724–735 (February 2014)
Lee, E., Park, S., Lee, J., Oh, S., Kim, S.H.: Novel service protocol for supporting remote and mobile users in wireless sensor networks with multiple static sinks. Wireless Networks 17(4), 861–875 (2011)
Chen, J., Li, J., He, S., He, T., Gu, Y., Sun, Y.: On energy-efficient trap coverage in wireless sensor networks. ACM Transactions on Sensor Networks 10(1), 2–29 (2013)
Shakkottai, S., Srikant, R., Shroff, N.: Unreliable sensor grids: coverage, connectivity and diameter. Proceedings of the IEEE Conference on Computer Communications 2, 1073–1083 (March 2003)
Sengupta, S., Das, S., Nasir, M., Vasilakos, A.V., Pedrycz, W.: An evolutionary multiobjective sleep-scheduling scheme for differentiated coverage in wireless sensor networks. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 42(6), 1093–1102 (2012)
Martins, F.V., Carrano, E.G., Wanner, E.F., Takahashi, R.H., Mateus, G.R.: A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks. IEEE Sensors Journal 11(3), 545–554 (2011)
Lanza-Gutierrez, J.M., Gomez-Pulido, J.A., Vega-Rodriguez, M.A., Sanchez-Perez, J.M.: A parallel evolutionary approach to solve the relay node placement problem in wireless sensor networks. In: Proceeding of Annual Conference on Genetic and Evolutionary Computation, pp. 1157–1164. ACM (2013)
Coello, C.C., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary algorithms for solving multi-objective problems. Springer (2007)
Miettinen, K.: Nonlinear multiobjective optimization, vol. 12. Springer (1999)
Smith, J., Fogarty, T.C.: Self adaptation of mutation rates in a steady state genetic algorithm. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 318–323. IEEE (1996)
Zhang, Q., Liu, W., Li, H.: The performance of a new version of moea/d on cec09 unconstrained mop test instances. In: IEEE Congress on Evolutionary Computation, pp. 203–208 (2009)
Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation 3(4), 257–271 (1999)
Czyzżak, P., Jaszkiewicz, A.: Pareto simulated annealing a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis 7(1), 34–47 (1998)
Deb, K., Miettinen, K., Sharma, D.: A hybrid integrated multi-objective optimization procedure for estimating nadir point. In: Ehrgott, M., Fonseca, C.M., Gandibleux, X., Hao, J.-K., Sevaux, M. (eds.) EMO 2009. LNCS, vol. 5467, pp. 569–583. Springer, Heidelberg (2009)
Rachmawati, L., Srinivasan, D.: Multiobjective evolutionary algorithm with controllable focus on the knees of the pareto front. IEEE Transactions on Evolutionary Computation 13(4), 810–824 (2009)
Bechikh, S., Ben Said, L., Ghédira, K.: Searching for knee regions in multi-objective optimization using mobile reference points. In: Proceedings of the ACM Symposium on Applied Computing, pp. 1118–1125. ACM (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zhang, X., Zhou, Y., Zhang, Q., Lee, V.C.S., Li, M. (2015). Multi-objective Optimization of Barrier Coverage with Wireless Sensors. In: Gaspar-Cunha, A., Henggeler Antunes, C., Coello, C. (eds) Evolutionary Multi-Criterion Optimization. EMO 2015. Lecture Notes in Computer Science(), vol 9019. Springer, Cham. https://doi.org/10.1007/978-3-319-15892-1_38
Download citation
DOI: https://doi.org/10.1007/978-3-319-15892-1_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15891-4
Online ISBN: 978-3-319-15892-1
eBook Packages: Computer ScienceComputer Science (R0)