Top

Journal of Reliable Intelligent Environments

Published in:

01-12-2016 | Original Article

Optimization of sensor deployment using multi-objective evolutionary algorithms

Authors: Arouna Ndam Njoya, Wahabou Abdou, Albert Dipanda, Emmanuel Tonye

Published in: Journal of Reliable Intelligent Environments | Issue 4/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many designs of wireless sensor network applications require the determination of the optimal locations of sensor nodes to be placed in a sensor field. Coverage enables us to evaluate the supervision quality of each point within an area of interest. In this paper, we address the problem of target coverage in wireless sensor networks. This concern is trivial if each target must be covered by a single sensor. However, it becomes an NP-complete problem when the choice of the position of the sensor must take into account the targets that it should cover in its vicinity. Using a multi-objective evolutionary-based approach, we propose a stochastic method to search for network configurations that achieve good coverage with the fewest sensors. A comparative experimental study of the model with well-known multi-objective algorithms such as NSGA-II, SPEA2, SMSEMOA and MOEA/D indicate that NSGA-II performs better than others on most of the test instances.

previous article Self-adaptive deployment of services in mobile environments: a study of the communication reliability on the host election algorithm

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Cai W, Chen M, Hara T, Shu L, Kwon T (2011) A genetic algorithm approach to multi-agent itinerary planning in wireless sensor networks. Mob Netw Appl 16(6):782–793CrossRef

Wang B (2011) Coverage problems in sensor networks: survey. ACM Comput Surv 43(4):32-1–32-53CrossRef

Yoon Y, Kim Y-H (2013) An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks. IEEE Trans Cybern 43(5):1473–1483MathSciNetCrossRef

Zorbas D, Glynos D, Kotzanikolaou P, Douligeris C (2010) Solving coverage problems in wireless sensor networks using cover sets. Ad Hoc Netw 8(4):400–415CrossRef

Deif DS, Gadallah Y (2014) Classification of wireless sensor networks deployment techniques. IEEE Commun Surv Tuts 16(2):834–855CrossRef

Liu X (2015) A deployment strategy for multiple types of requirements in wireless sensor networks. IEEE Trans Cybern 45(10):2364–2376CrossRef

Zhu H, Luo H, Peng H, Li L, Luo Q (2009) Complex networks-based energy-efficient evolution model for wireless sensor networks. Chaos Solitons Fractals 41(4):1828–1835CrossRef

Li S, Li L, Yang Y (2011) A local-world heterogeneous model of wireless sensor networks with node and link diversity. Phys A 390(6):1182–1191CrossRef

Ruela A, Cabral R, Aquino A, Guimaraes F (2009) Evolutionary design of wireless sensor networks based on complex networks. In: Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), pp 237–242

10.

Gu Y, Liu H, Zhao B (2007) Target coverage with QoS requirements in wireless sensor networks. In: The 2007 International Conference on Intelligent Pervasive Computing, 2007. IPC, pp 35–38

11.

Singh A, Rossi A (2013) A genetic algorithm based exact approach for lifetime maximization of directional sensor networks. Ad Hoc Netw 11(3):1006–1021CrossRef

12.

Slijepcevic S, Potkonjak M (2001) Power efficient organization of wireless sensor networks. In: IEEE international conference on Wireless Communications, vol 2, Helsinki, Finland, pp 472–476

13.

Cardei M, Thai MT, Li Y, Wu W (2005) Energy-efficient target coverage in wireless sensor networks. In: Proceedings IEEE INFOCOM, (2005) 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol 3, pp 1976–1984

14.

Cardei M, Du DZ (2005) Improving wireless sensor network lifetime through power aware organization. Wirel Netw 11(3):333–340CrossRef

15.

Lai C-C, Ting C-K, Ko R-S (2007) An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications. In: IEEE Congress on Evolutionary Computation, CEC, pp 3531–3538

16.

Chen J, Jia J, Wen Y, Zhao D, Liu D (2009) Modeling and extending lifetime of wireless sensor networks using genetic algorithm. In: Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation, Shanghai, China, pp 47–54

17.

Gil J-M, Han Y-H (2011) A target coverage scheduling scheme based on genetic algorithms in directional sensor networks. Sensors 11(2):1888–1906MathSciNetCrossRef

18.

Mini S, Udgata SK, Sabat SL (2014) Sensor deployment and scheduling for target coverage problem in wireless sensor networks. IEEE Sens J 14(3):636–644CrossRef

19.

Njoya AN, Abdou W, Dipanda A, Tonye E (2015) Evolutionary-based wireless sensor deployment for target coverage. In: Proc. IEEE SITIS, 2015, pp 739–745

20.

Zdemir S, Baraa AA, Khalil A (2013) Multi-objective evolutionary algorithm based on decomposition for energy efficient coverage in wireless sensor networks. Wirel Pers Commun 71(1):195–215CrossRef

21.

Dhillon SS, Chakrabarty K (2003) Sensor placement for effective coverage and surveillance in distributed sensor networks. In: IEEE Wireless Communications and Networking Conference, 2003, pp 1609–1614

22.

Lin F, Chiu P (2005) A near-optimal sensor placement algorithm to achieve complete coverage-discrimination in sensor networks. IEEE Commun Lett 9(1):43–45

23.

Jourdan DB, de Weck OL (2004) Layout optimization for a wireless sensor network using a multi-objective genetic algorithm. In: Proceedings 59th IEEE Veh. Technology Conferrence, vol 5, pp 2466–2470

24.

Y. Xu and X. Yao, “A ga approach to the optimal placement of sensors in wireless sensor networks with obstacles and preferences,” in Proc. 3rd IEEE Consumer Commun. Networking Conf., 2006, pp. 127–131

25.

Zhao JC, Yu Z, Chen P (2007) Optimal deployment of nodes based on genetic algorithm in heterogeneous sensor networks. In: Proceedings of Sept, IEEE Interantional Conference Wireless Communication Networking Mobile Comput., pp 2743–2746

26.

Wu Q, Rao NSV, Du X, Sitharama S, Vaishnavi VK (2007) On efficient deployment of sensors on planar grid. Comput Commun 30:2721–2734CrossRef

27.

Seo J-H, Kim Y-H, Ryou H-B, Cha S-H, Jo M (2008) Optimal sensor deployment for wireless surveillance sensor networks by a hybrid steady-state genetic algorithm. IEICE Trans Commun E91–B(11):3534–3543CrossRef

28.

Yildirim K, Kalayci T, Ugur A (2008) Optimizing coverage in a k-covered and connected sensor network using genetic algorithms. In: 9th WSEAS International Conference on Evolutionary Computing (EC08), Sofia, Bulgaria, pp 21–26

29.

Kalayci TE, Ugur A (2011) Genetic algorithm-based sensor deployment with area priority. Cybern Syst 42(8):605–620CrossRef

30.

Banimelhem O, Mowafi M, Aljoby W (2013) Genetic algorithm based node deployment in hybrid wireless sensor networks. Commun Netw 5(4):273–279CrossRef

31.

Zou Y, Chakrabarty K (2003) Sensor deployment and target localization based on virtual forces. In: Proceedings of IEEE Infocom Conference, pp 1293–1303

32.

Akyildiz IF, Vuran MC (2010) Wireless sensor networks. Wiley, New York

33.

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: Nsga-ii. Trans Evol Comput 6(2):182–197. doi:10.1109/4235.996017 CrossRef

34.

Zitzler E, Laumanns M, Thiele L (2001) Spea2: Improving the strength pareto evolutionary algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH). Zurich, Switzerland

35.

Beume N, Naujoks B, Emmerich M (2007) Sms-emoa: Multiobjective selection based on dominated hypervolume. Eur J Oper Res 181(3):1653–1669CrossRefMATH

36.

Zhang Q, Li H (2007) Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731CrossRef

37.

Abdou W (2011) Optimisation évolutionniste multi-objectifs pour des réseaux ad hoc mobiles : la diffusion robuste et le routage multi-chemins non recouvrant (Ph.D.thesis). Université de Franche-Comté, France

Title: Optimization of sensor deployment using multi-objective evolutionary algorithms
Authors: Arouna Ndam Njoya
Wahabou Abdou
Albert Dipanda
Emmanuel Tonye
Publication date: 01-12-2016
Publisher: Springer International Publishing
Published in: Journal of Reliable Intelligent Environments / Issue 4/2016
Print ISSN: 2199-4668
Electronic ISSN: 2199-4676
DOI: https://doi.org/10.1007/s40860-016-0030-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2016

Unobtrusive silhouette extraction using multivariate analysis and shadow removal in RGB color model

Real time vision/sensor based features processing for efficient HCI employing canonical correlation analysis

Editorial

Self-adaptive deployment of services in mobile environments: a study of the communication reliability on the host election algorithm

Premium Partner