Studying the multiobjective variable neighbourhood search algorithm when solving the relay node placement problem in Wireless Sensor Networks

详细信息    查看全文

• 作者：Jose M. Lanza-Gutierrez ; Juan A. Gomez-Pulido
• 关键词：Coverage ; Energy efficiency ; Metaheuristic ; Multiobjective optimisation ; Relay node ; Wireless sensor network
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：20
• 期：1
• 页码：67-86
• 全文大小：1,909 KB
• 参考文献：Akyildiz I, Su W, Sankarasubramaniam Y, Cayirci E (2002) A survey on sensor networks. IEEE Commun Mag 40:102–114CrossRef
  Back T (1996) Evolutionary algorithms in theory and practice: evolution strategies. In: Evolutionary programming. Genetic algorithms. Oxford University Press, Cambridge
  Cardei M, Du DZ (2005) Improving wireless sensor network lifetime through power aware organization. Wirel Netw 11:333–340CrossRef
  Chang JH, Tassiulas L (2004) Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans Netw 12:609–619CrossRef
  Cheng X, Narahari B, Simha R, Cheng M, Liu D (2003) Strong minimum energy topology in wireless sensor networks: Np-completeness and heuristics. IEEE Trans Mobile Comput 2:248–256CrossRef
  Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, Cambridge
  Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast elitist multi-objective genetic algorithm: Nsga-ii. IEEE Trans Evol Comput 6:182–197CrossRef
  Fonseca CM, Fleming PJ (1996) On the performance assessment and comparison of stochastic multiobjective optimizers. In: Proceedings of PPNS IV, pp 584–593
  Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman & Co, New YorkMATH
  Geiger MJ (2008) Randomised variable neighbourhood search for multi objective optimisation. In: Proceedings of EU/ME workshop, pp 34–42. arXiv:​0809.​0271
  Han X, Cao X, Lloyd EL, Shen CC (2010) Fault-tolerant relay node placement in heterogeneous wireless sensor networks. IEEE Trans Mobile Comput 9:643–656CrossRef
  Hays W, Winkler R (1970) Statistics: probability, inference, and decision. Holt, Rinehart and Winston, USA
  Hou Y, Shi Y, Sherali H, Midkiff S (2005) On energy provisioning and relay node placement for wireless sensor networks. IEEE Trans Wirel Commun 4:2579–2590CrossRef
  Hu XM, Zhang J, Yu Y, Chung HH, Li YL, Shi YH, Luo XN (2010) Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks. IEEE Trans Evol Comput 14:766–781CrossRef
  Jia J, Chen J, Chang G, Tan Z (2009a) Energy efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm. Comput Math Appl 57:1756–1766MathSciNet CrossRef MATH
  Jia J, Chen J, Chang G, Wen Y, Song J (2009b) Multi-objective optimization for coverage control in wireless sensor network with adjustable sensing radius. Comput Math Appl 57:1767–1775MathSciNet CrossRef MATH
  Konstantinidis A, Yang K (2011) Multi-objective k-connected deployment and power assignment in wsns using a problem-specific constrained evolutionary algorithm based on decomposition. Comput Commun 34:83–98CrossRef
  Konstantinidis A, Yang K, Zhang Q (2008) An evolutionary algorithm to a multi-objective deployment and power assignment problem in wireless sensor networks. In: Proceedings of IEEE GLOBECOM, pp 1–6
  Lanza-Gutierrez J, Gomez-Pulido J, Vega-Rodriguez M (2013a) A trajectory algorithm to solve the relay node placement problem in wireless sensor networks. In: Theory and practice of natural computing. Lecture notes in computer science, vol 8273. Springer, Berlin, pp 145–156
  Lanza-Gutierrez JM, Gomez-Pulido JA (2011) Instance sets for optimization in wireless sensor networks. http://​arco.​unex.​es/​wsnopt
  Lanza-Gutierrez JM, Gomez-Pulido JA, Vega-Rodriguez MA, Sanchez-Perez JM (2012) Relay node positioning in wireless sensor networks by means of evolutionary techniques. In: Autonomous and intelligent systems. Lecture notes in computer science, vol 7326. Springer, Berlin, pp 18–25
  Lanza-Gutierrez JM, Gomez-Pulido JA, Vega-Rodriguez MA, Sanchez-Perez JM (2013b) A parallel evolutionary approach to solve the relay node placement problem in wireless sensor networks. In: Proceeding of GECCO, pp 1157–1164
  Le Berre M, Hnaien F, Snoussi H (2011) Multi-objective optimization in wireless sensors networks. Proc ICM 1:1–4
  Lilliefors HW (1967) On the kolmogorov–smirnov test for normality with mean and variance unknown. J Am Stat Assoc 62:399–402CrossRef
  Liu L, Hu B, Li L (2010) Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks. IET Commun 4:786–800MathSciNet CrossRef
  Lloyd EL, Xue G (2007) Relay node placement in wireless sensor networks. IEEE Trans Comput 56:134–138MathSciNet CrossRef
  Mahboubi H, Moezzi K, Aghdam A, Sayrafian-Pour K, Marbukh V (2014) Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors. IEEE Trans Ind Inf 10:163–174CrossRef
  Mann HB, Whitney DR (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 1:50–60MathSciNet CrossRef
  Martins F, Carrano E, Wanner E, Takahashi R, Mateus G (2011) A hybrid multiobjective evolutionary approach for improving the performance of wireless sensor networks. IEEE Sens J 11:545–554CrossRef
  Mini S, Udgata S, Sabat S (2014) Sensor deployment and scheduling for target coverage problem in wireless sensor networks. IEEE Sens J 14:636–644CrossRef
  Misra S, Majd N, Huang H (2011) Constrained relay node placement in energy harvesting wireless sensor networks. In: Proceedings of IEEE MASS 2011, vol 1, pp 25–34
  Misra S, Majd NE, Huang H (2013) Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks. In: IEEE Transactions on Computers, vol 99 (PrePrints)
  Mukherjee JYB, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52:2292–2330CrossRef
  Nigam A, Agarwal YK (2014) Optimal relay node placement in delay constrained wireless sensor network design. Eur J Oper Res 233:220–233MathSciNet CrossRef
  Peiravi A, Mashhadi HR, Hamed Javadi S (2013) An optimal energy-efficient clustering method in wireless sensor networks using multi-objective genetic algorithm. Int J Commun Syst 26:114–126CrossRef
  Perez A, Labrador M, Wightman P (2011) A multiobjective approach to the relay placement problem in wsns. Proc IEEE WCNC 1:475–480
  ur Rehman A, Abbasi AZ, Islam N, Shaikh ZA (2014) A review of wireless sensors and networks: applications in agriculture. Comput Standards Interf 36(2):263–270CrossRef
  Sha K, Gehlot J, Greve R (2013) Multipath routing techniques in wireless sensor networks: a survey. Wirel Pers Commun 70:807–829CrossRef
  Shapiro SS, Wilk MB (1965) An analysis of variance test for normality (complete samples). Biometrika 52:591–611
  Tang J, Hao B, Sen A (2006) Relay node placement in large scale wireless sensor networks. Comput Commun 29:490–501CrossRef
  Wang B (2011) Coverage problems in sensor networks: a survey. ACM Comput Surv 43:32:1–32:53
  Wang Q, Xu K, Takahara G, Hassanein H (2007) Device placement for heterogeneous wireless sensor networks: minimum cost with lifetime constraints. IEEE Trans Wirel Commun 6:2444–2453CrossRef
  Xu K, Hassanein H, Takahara G, Wang Q (2010) Relay node deployment strategies in heterogeneous wireless sensor networks. IEEE Trans Mobile Comput 9:145–159CrossRef
  Ye W, Heidemann J, Estrin D (2002) An energy-efficient mac protocol for wireless sensor networks. Proc INFOCOM 3:1567–1576
  Yoon Y, Kim YH (2013) An efficient genetic algorithm for maximum coverage deployment in wireless sensor networks. IEEE Trans Cybern 43:1473–1483CrossRef
  Zhang H, Hou J (2005) Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc & Sensor, wireless networks 1
  Zhao C, Chen P (2007) Particle swarm optimization for optimal deployment of relay nodes in hybrid sensor networks. Proc IEEE CEC 1:3316–3320
  Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications
  Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans Evol Comput 3:257–271CrossRef
  Zitzler E, Laumanns M, Thiele L (2001) Spea 2: improving the strength pareto evolutionary algorithm Tech. rep. Computer Engineering and Networks Laboratory (TIK), ETH Zurich
  
• 作者单位：Jose M. Lanza-Gutierrez (1)
  Juan A. Gomez-Pulido (1)
  
  1. Department of Technologies of Computers and Communications, Polytechnic School, University of Extremadura, Campus Universitario s/n, 10003, Caceres, Spain
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

Nowadays, wireless sensor networks (WSNs) are considered in many fields of application. In this paper, we study how to efficiently deploy relay nodes into previously established static WSNs, with the purpose of optimising two relevant factors for the industry: average energy consumption of the sensors and average sensitivity area provided by the network. This is the so-called relay node placement problem, which is a known NP-hard optimisation problem in the literature. With the purpose of tackling this multiobjective (MO) optimisation problem, we consider two different approaches of the trajectory algorithm MO-VNS, assuming a wide range of stop conditions. Two additional standard genetic algorithms are included in this study, NSGA-II and SPEA2, which belong to evolutionary algorithms. The aim is to analyse the behaviour of MO-VNS compared to traditional methodologies. To this end, the four metaheuristics are applied to solve a freely available data set. The results obtained are analysed following a widely accepted statistical methodology and considering three MO quality metrics: hypervolume, set coverage, and attainment surface. After studying the results, we conclude that MO-VNS provides better performance than the standard algorithms NSGA-II and SPEA2. Moreover, we verify that the addition of relay nodes is a good way to optimise traditional WSNs. Keywords Coverage Energy efficiency Metaheuristic Multiobjective optimisation Relay node Wireless sensor network