Abstract
Compared with the two-dimensional deployment, the three-dimensional deployment of sensor networks is more challenging. We studied the problem of 3D repositioning of sensor nodes in wireless sensor networks. We aim essentially to add a set of nodes to the initial architecture. The positions of the added nodes are determined by the proposed algorithms while optimizing a set of objectives. In this paper, we suggest two main contributions. The first one is an analysis contribution where the modelling of the problem is given and a set of modifications is incorporated on the tested multi-objective evolutionary algorithms to resolve the issues encountered when resolving many-objective problems. These modifications concern essentially an adaptive mutation and recombination operators with neighbourhood mating restrictions, the use of a multiple scalarizing functions concept and the incorporation of the reduction in dimensionality. The second contribution is an application one, where an experimental study on real testbeds is detailed to test the behaviour of the enhanced algorithms on a real-world context. Experimental tests followed by numerical results prove the efficiency of the proposed modifications against original algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Saipulla, A.; Cui, J.; Fu, X.; Liu, B.; Wang J.: Barrier coverage: foundations and design. In: The Art of Wireless Sensor Networks, Volume 2: Advanced Topics and Applications, 1st ed., pp. 59–115. Springer, Berlin. eBook ISBN 978-3-642-40066-7. Hardcover ISBN 978-3-642-40065-0. Series ISSN 1860-4862 (2014). https://doi.org/10.1007/978-3-642-40066-7
Cheng, X.; Du, D.Z.; Wang, L.; Xu, B.: Relay sensor placement in wireless sensor networks. ACM/Springer J. Wirel. Netw. 14(3), 347–355 (2008). https://doi.org/10.1007/s11276-006-0724-8
Mansoor, U.; Ammari, H. M.: Coverage and connectivity in 3D wireless sensor networks. In: The Art of Wireless Sensor Networks, Volume 2: Advanced Topics and Applications, 1st ed., Springer, Berlin, pp. 273–324 (2014). https://doi.org/10.1007/978-3-642-40066-7
Shah, B.; Kim, K.: A survey on three-dimensional wireless ad hoc and sensor networks. Int. J. Distrib. Sens. Netw. 10(7), 616014 (2014). https://doi.org/10.1155/2014/616014
Jiang, J.A.; Wan, J.J.; Zheng, X.Y.; Chen, C.P.; Lee, C.H.; Su, L.K.; Huang, W.C.: A novel weather information-based optimization algorithm for thermal sensor placement in smart grid. IEEE Trans. Smart Grid PP(99), 1–11 (2016). https://doi.org/10.1109/TSG.2016.2571220
Alia, O.M.; Al-Ajouri, A.: Maximizing wireless sensor network coverage with minimum cost using harmony search algorithm. IEEE Sens. J. 17(3), 882–896 (2017). https://doi.org/10.1109/JSEN.2016.2633409
Sweidan, H.I.; Havens, T. C.: Coverage optimization in a terrain-aware wireless sensor network. In: Proceedings of the 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, pp. 3687–3694 (2016). https://doi.org/10.1109/CEC.2016.7744256
Khalfallah, Z.; Fajjari, N.; Aitsaadi, Rubin P.; Pujolle, G.: A novel 3D underwater WSN deployment strategy for full-coverage and connectivity in rivers. In: IEEE International Conference on Communications (ICC), Kuala Lumpur, 2016, pp. 1–7. https://doi.org/10.1109/ICC.2016.7510979
Brown, T.; Wang, Z.; Shan, T.; Wang, F.; Xue, J.: On wireless video sensor network deployment for 3D indoor space coverage, SoutheastCon, Norfolk, VA, 2016, pp. 1–8. https://doi.org/10.1109/SECON.2016.7506744
Liu, Z.; Ouyang, Z.: k-Coverage estimation problem in heterogeneous camera sensor networks with boundary deployment. IEEE Access 6, 2825–2833 (2018). https://doi.org/10.1109/ACCESS.2017.2785393
Cotta, C.; Gallardo, J.E.: Metaheuristic approaches to the placement of suicide bomber detectors. J. Heuristics 24(3), 483–513 (2018). https://doi.org/10.1007/s10732-017-9335-z
Wu, C.Q.; Wang, L.: On efficient deployment of wireless sensors for coverage and connectivity in constrained 3D space. Sensors (Basel) 17(10), 2304 (2017). https://doi.org/10.3390/s17102304
Hu, J.; Luo, J.; Zheng, Y.; Li, K.: Graphene-grid deployment in energy harvesting cooperative wireless sensor networks for green IoT. IEEE Trans. Ind. Inform. (2018)
Zhang, S; Jiajia, L.: Analysis and Optimization of Multiple Unmanned Aerial Vehicle-Assisted Communications in Post-Disaster Areas. IEEE Transactions on Vehicular Technology. pp(99):1-1, (2019). https://doi.org/10.1109/TVT.2018.2871614
Zhang, S.; Jiajia, L.: Analysis and optimization of multiple unmanned aerial vehicle-assisted communications in post-disaster areas. IEEE Trans. Veh. Technol. 99, 1–1 (2019). https://doi.org/10.1109/TVT.2018.2871614
Cao, B.; Zhao, J.; Yang, P.; Ge Lv, Z.; Liu, X.; Min, G.: 3D multi-objective deployment of an industrial wireless sensor network for maritime applications utilizing a distributed parallel algorithm. IEEE Trans. Ind. Inform. (2018). https://doi.org/10.1109/TII.2018.2803758
Cui, W.; Zeng, L.; Li, Q.; Zhang, Y.; Liang, J.: Deployment of 3D wireless sensors within forest based on genetic algorithm. In: Liang, Q.; Mu, J.; Jia, M.; Wang, W.; Feng, X.; Zhang, B. (eds.) Communications, Signal Processing, and Systems. CSPS. Lecture Notes in Electrical Engineering, vol. 463 (2019) Springer, Singapore
Zhou, Y.; Wang, H.; Li, S.: Research on the deployment algorithm of distributed detection network. In: Liang, Q.; Mu, J.; Jia, M.; Wang, W.; Feng, X.; Zhang, B. (eds.) Communications, Signal Processing, and Systems. CSPS 2017. Lecture Notes in Electrical Engineering, vol. 463. (2019). Springer, Singapore
Hildmann, H.; Atia, D.Y.; Ruta, D.; Poon, K.; Isakovic, A. F.: Nature-Inspired optimization in the era of IoT: particle swarm optimization (PSO) applied to indoor distributed antenna systems (I-DAS). In: Elfadel, I.; Ismail, M. (eds.) The IoT physical layer. Springer, Cham (2019) (forthcoming). https://doi.org/10.1007/978-3-319-93100-5_11
Asorey-Cacheda, R.; Garcia-Sanchez, A.-J.; Garcia-Sanchez, F.; Garcia-Haro, J.: A survey on non-linear optimization problems in wireless sensor networks. J. Netw. Comput. Appl. 82, 1–20 (2017). https://doi.org/10.1016/j.jnca.2017.01.001
Das, S.; Debbarma, M.K.: A survey on coverage problems in wireless sensor network based on monitored region. In: Kolhe, M.; Trivedi, M.; Tiwari, S.; Singh, V. (eds.) Advances in Data and Information Sciences. Lecture Notes in Networks and Systems, vol. 39. (2019). Springer, Singapore. https://doi.org/10.1007/978-981-13-0277-0_29
Maheshwari, A.; Chand, N.: A survey on wireless sensor networks coverage problems. In: Krishna, C.; Dutta, M.; Kumar R. (eds.) Proceedings of 2nd International Conference on Communication, Computing and Networking. Lecture Notes in Networks and Systems, vol. 46. pp 153–164 (2019). Springer, Singapore. https://doi.org/10.1007/978-981-13-1217-5_16
Meribout, M.; Al Naamany, A.: A collision free data link layer protocol for wireless sensor networks and its application in intelligent transportation systems. In: Wireless Telecommunications Symposium, Prague, pp. 1-6. (2009). https://doi.org/10.1109/WTS.2009.5068957
Kollat, J.B.; Reed, P.: Comparison of multi-objective evolutionary algorithms for long-term monitoring design. Adv. Water Resour. 29(6), 792–807 (2006)
Seada, H.; Deb, K.: A unified evolutionary optimization procedure for single, multiple, and many objectives. IEEE Trans. Evol. Comput. 20(03), 358–369 (2016). https://doi.org/10.1109/TEVC.2015.2459718
Li, K.; Deb, K.; Zhang, Q.; Kwong, S.: An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. Evol. Comput. 19(5), 694–716 (2015). https://doi.org/10.1109/TEVC.2014.2373386
Ishibuchi, H.; Akedo, N.; Nojima, Y.: Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems. IEEE Trans. Evol. Comput. 19(2), 264–283 (2015)
Qu, B.Y.; Suganthan, P.N.; Liang, J.J.: Differential evolution with neighborhood mutation for multimodal optimization. IEEE Trans. Evol. Comput 16(5), 601–614 (2012)
Vrugt, J.A.; Robinson, B.A.: Improved evolutionary optimization from genetically adaptive multimethod search. Proc. Natl. Acad. Sci. U.S.A. 104(3), 708–711 (2007). https://doi.org/10.1073/pnas.0610471104
Ishibuchi, H.; Sakane, Y.; Tsukamoto, N.; Nojima, Y.: simultaneous use of different scalarizing functions in MOEA/D. In: 12th Annual Conference on Genetic and Evolutionary Computation GECCO, pp. 519–526 (2010)
Ishibuchi, H.; Sakane, Y.; Tsukamoto, N.; Nojima, Y.: Adaptation of scalarizing functions in MOEA/D: an adaptive scalarizing function-based multiobjective evolutionary algorithm. In: Proceedings of the EMO 2009, LNCS 5467, pp. 438–452 (2009)
Sato., H.: Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization. In: Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 645–652 (2014)
Tan, Y.; Jiao, Y.; Li, H.; Wang, X.: MOEA/D + uniform design: A new version of MOEA/D for optimization problems with many objectives. Comput. Oper. Res. 40(6), 1648–1660 (2013)
Mitra, P.; Murthy, C.A.; Pal, S.K.: Unsupervised feature selection using feature similarity. IEEE Trans. Pattern Anal. Mach. Intell 24(3), 301–312 (2002). https://doi.org/10.1109/34.990133
Bader, J.; Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1), 45–76 (2011)
The IOTLab platform: software available at http://www.iot-lab.info (2018). Accessed on October 08\(^{\text{th}}\) (2018)
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Mnasri, S., Nasri, N., van den Bossche, A. et al. Improved Many-Objective Optimization Algorithms for the 3D Indoor Deployment Problem. Arab J Sci Eng 44, 3883–3904 (2019). https://doi.org/10.1007/s13369-018-03712-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13369-018-03712-7